Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

TypeBinding hashCode may be bad #3412

Open
jukzi opened this issue Dec 6, 2024 · 9 comments
Open

TypeBinding hashCode may be bad #3412

jukzi opened this issue Dec 6, 2024 · 9 comments
Assignees

Comments

@jukzi
Copy link
Contributor

jukzi commented Dec 6, 2024

Especially UnresolvedReferenceBinding.hashCode()
See discussion around #3387 (comment)
It is not obvious if the method violates equals contract or is a good hashCode(), given that ReferenceBindingSetWrapper tries to work around it.
I will investigate.

@jukzi jukzi self-assigned this Dec 6, 2024
@jukzi
Copy link
Contributor Author

jukzi commented Dec 6, 2024

  • ArrayBinding overrides hashCode() but not equals() without explanation.
  • LocalTypeBinding overrides hashCode() but not equals() without explanation.
  • WildcardBinding overrides hashCode() but not equals() without explanation.
  • ReferenceBinding overrides hashCode() but not equals() - comment that it should hash same as UnresolvedReferenceBinding
  • TypeSystem.HashedParameterizedTypes.PTBKey overrides hashCode() using System.identityHashCode for some cases only (looks inconsistent)
  • InferenceVariable overrides equals() and hashCode() symmetrically

There where 2 commits that introduced similar workarounds: PTBKey (https://bugs.eclipse.org/bugs/show_bug.cgi?id=521438, ReferenceBindingSetWrapper (https://bugs.eclipse.org/bugs/show_bug.cgi?id=544921) for noticed performance problems.

A clean solution would be to not require UnresolvedReferenceBindings have same hashCode as ReferenceBinding or to copy the hashCode from the unresolved to the resolved one.
The question is where that property is used. @stephan-herrmann

@jukzi
Copy link
Contributor Author

jukzi commented Dec 6, 2024

property is used in org.eclipse.jdt.internal.compiler.lookup.TypeSystem.updateCaches(UnresolvedReferenceBinding, ReferenceBinding) to update keys in a org.eclipse.jdt.internal.compiler.util.SimpleLookupTable TypeSystem.annotationTypes

jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 6, 2024
@carstenartur
Copy link
Contributor

Maybe while at it some hashcode implementions could be updated in case they are not updated already (did not check)

https://git.eclipse.org/r/c/jdt/eclipse.jdt.core/+/170961

@stephan-herrmann
Copy link
Contributor

property is used in org.eclipse.jdt.internal.compiler.lookup.TypeSystem.updateCaches(UnresolvedReferenceBinding, ReferenceBinding) to update keys in a org.eclipse.jdt.internal.compiler.util.SimpleLookupTable TypeSystem.annotationTypes

This is not the full story. Class TypeSystem was introduced in 2013 (Java 8). The design decision behind hashCode for ReferenceBinding dates from 2004 (Java 5). In some ways TypeSystem "inherited" the responsibilities of former fields like SimpleLookupTable uniqueParameterizedTypeBindings (in LookupEnvironment), but 20 years after the design was made, there may be many more locations relying on its guarantees.

To get a full picture, all hash collections (incl. SimpleLookupTable) over TypeBinding must be considered. In all of them an initial UnresolvedReferenceBinding must occupy the same slot that eventually its resolved version will assume.

I suggest that any changes in this area must at the very least be thoroughly reviewed by @srikanth-sankaran , ideally also by Philipe Mulet :)

@stephan-herrmann
Copy link
Contributor

Maybe while at it some hashcode implementions could be updated in case they are not updated already (did not check)

https://git.eclipse.org/r/c/jdt/eclipse.jdt.core/+/170961

That would be a separate issue, because the quality/reviewing requirements for the compiler differ from other code areas.

@stephan-herrmann
Copy link
Contributor

While it's great to try to understand the true intention behind this admittedly irregular design, I'm not sure there is an actual flaw to be corrected.

@srikanth-sankaran
Copy link
Contributor

A clean solution would be to not require UnresolvedReferenceBindings have same hashCode as ReferenceBinding or to copy the hashCode from the unresolved to the resolved one.

If they don't have the same hashcode then "in place" resolution won't work. An UnresolvedReferenceBinding gets resolved automagically without perturbing the container semantics today.

@srikanth-sankaran
Copy link
Contributor

A clean solution would be to not require UnresolvedReferenceBindings have same hashCode as ReferenceBinding or to copy the hashCode from the unresolved to the resolved one.

If they don't have the same hashcode then "in place" resolution won't work. An UnresolvedReferenceBinding gets resolved automagically without perturbing the container semantics today.

I vaguely recall some super complex scenario defects 15 years ago involving UnresolvedReferenceBinding where we would end up with two or more ReferenceBindings after resolution for the same URB - a design violation triggered by something to do with hashcode 😊

Here be dragons!

jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 9, 2024
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 9, 2024
@jukzi
Copy link
Contributor Author

jukzi commented Dec 9, 2024

Currently compiler.codegen.ObjectCache as used in ExceptionHandlingFlowContext constructor (and only there) uses ReferenceBinding.hashCode() but not equals(), it uses == for comparison.
That's inefficient: Checking for identity does not require any hashcode other then System.identityHashCode() or it may suffer from needless hash collisions. One could even use java.util.IdentityHashMap<K, V> if identity is meant.

jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 9, 2024
SuperTypeTest.test016(), SuperTypeTest.test017() failed when
implementation of ReferenceBinding.hashCode() changed.

The message was either
"already defined by IChangeRulerColumn" or
"already defined by IRevisionRulerColumn"
depending on which Interface had the lower hashCode.

relates to
eclipse-jdt#3412
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 9, 2024
SuperTypeTest.test016(), SuperTypeTest.test017() failed when
implementation of ReferenceBinding.hashCode() changed.

The message was either
"already defined by IChangeRulerColumn" or
"already defined by IRevisionRulerColumn"
depending on which Interface had the lower hashCode.

Now using a LinkedHashMap to rely on the insertion order rather then the
hashcode.

relates to
eclipse-jdt#3412
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 9, 2024
* avoids raw types
* deletes custom ObjectCache

ObjectCache implemented a HashMap using hashCode() but not equals().
Instead it used == identity. JDK offers a special Map for identity since
1.4, consistently using System.identityHashCode().

relates to eclipse-jdt#3412
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 10, 2024
* avoids raw types
* deletes custom ObjectCache

ObjectCache implemented a HashMap using hashCode() but not equals().
Instead it used == identity. JDK offers a special Map for identity since
1.4, consistently using System.identityHashCode().

relates to eclipse-jdt#3412

Also solved follow up
* LambdaExpression "Redundant specification of type arguments"
jukzi pushed a commit to jukzi/eclipse.jdt.core that referenced this issue Dec 10, 2024
Environment is only used during put

relates to
eclipse-jdt#3412
jukzi pushed a commit that referenced this issue Dec 11, 2024
SuperTypeTest.test016(), SuperTypeTest.test017() failed when
implementation of ReferenceBinding.hashCode() changed.

The message was either
"already defined by IChangeRulerColumn" or
"already defined by IRevisionRulerColumn"
depending on which Interface had the lower hashCode.

Now using a LinkedHashMap to rely on the insertion order rather then the
hashcode.

relates to
#3412
jukzi pushed a commit that referenced this issue Dec 11, 2024
* avoids raw types
* deletes custom ObjectCache

ObjectCache implemented a HashMap using hashCode() but not equals().
Instead it used == identity. JDK offers a special Map for identity since
1.4, consistently using System.identityHashCode().

relates to #3412

Also solved follow up
* LambdaExpression "Redundant specification of type arguments"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants