THashMap.remove() throws IAE

[Johan Parent]

Hi all,

I ran into a minor issue (illustrated below) in a situation where the call to
remove throws an exception. I'm using rc1.

Now, I must confess not having looked at the rehash() method at all so I may
be way out of my league here. But from the output I'd be tempted to say this
is the same object twice cfr "object #1 =485255936; object #2 =485255936" or
am I not understanding this right.

Best regards,

Johan

ps: Some more context about the usage of trove4j in this case. It is standard
maven where the HashMap instances where replaced on the fly with bytecode
instrumentation with THashMap instances (wrapped). The issue does not occur
with the jdk HashMap impl.


java.lang.IllegalArgumentException: Equal objects must have equal hashcodes.
During rehashing, Trove discovered that the following two objects claim to be
equal (as in java.lang.Object.equals()) but their hashCodes (or those
calculated by your TObjectHashingStrategy) are not equal.This violates the
general contract of java.lang.Object.hashCode(). See bullet point two in that
method's documentation. object #1 =485255936; object #2 =485255936
at gnu.trove.impl.hash.TObjectHash.throwObjectContractViolation(TObjectHash.ja
va:276)
at gnu.trove.map.hash.THashMap.rehash(THashMap.java:400)
at gnu.trove.impl.hash.THash.compact(THash.java:201)
at gnu.trove.impl.hash.THash.removeAt(THash.java:271)
at gnu.trove.impl.hash.TObjectHash.removeAt(TObjectHash.java:95)
at gnu.trove.map.hash.THashMap.removeAt(THashMap.java:462)
at gnu.trove.map.hash.THashMap.remove(THashMap.java:449)
at be.biggerbytes.patch4j.delegates.trove.DHashMap.remove(DHashMap.java:67)
at java.util.Collections$SynchronizedMap.remove(Collections.java:1982)
at org.codehaus.plexus.component.manager.DefaultComponentManagerManager.unasso
ciateComponentWithComponentManager(DefaultComponentManagerManager.java:156)
at org.codehaus.plexus.DefaultPlexusContainer.release(DefaultPlexusContainer.j
ava:549)
at org.codehaus.plexus.DefaultPlexusContainer.releaseAll(DefaultPlexusContaine
r.java:572)
at org.apache.maven.profiles.DefaultProfileManager.isActive(DefaultProfileMana
ger.java:293)
at org.apache.maven.profiles.DefaultProfileManager.getActiveProfiles(DefaultPr
ofileManager.java:209)
at org.apache.maven.project.DefaultMavenProjectBuilder.injectActiveProfiles(De
faultMavenProjectBuilder.java:1496)
at org.apache.maven.project.DefaultMavenProjectBuilder.assembleLineage(Default
MavenProjectBuilder.java:1194)
at org.apache.maven.project.DefaultMavenProjectBuilder.assembleLineage(Default
MavenProjectBuilder.java:1407)
at org.apache.maven.project.DefaultMavenProjectBuilder.assembleLineage(Default
MavenProjectBuilder.java:1407)
at org.apache.maven.project.DefaultMavenProjectBuilder.buildInternal(DefaultMa
venProjectBuilder.java:823)
at org.apache.maven.project.DefaultMavenProjectBuilder.buildFromRepository(Def
aultMavenProjectBuilder.java:255)
at org.apache.maven.project.artifact.MavenMetadataSource.retrieveRelocatedProj
ect(MavenMetadataSource.java:163)
at org.apache.maven.project.artifact.MavenMetadataSource.retrieveRelocatedArti
fact(MavenMetadataSource.java:94)
at org.apache.maven.artifact.resolver.DefaultArtifactCollector.recurse(Default
ArtifactCollector.java:387)
at org.apache.maven.artifact.resolver.DefaultArtifactCollector.recurse(Default
ArtifactCollector.java:435)
at org.apache.maven.artifact.resolver.DefaultArtifactCollector.recurse(Default
ArtifactCollector.java:435)
at org.apache.maven.artifact.resolver.DefaultArtifactCollector.collect(Default
ArtifactCollector.java:74)
at org.apache.maven.artifact.resolver.DefaultArtifactResolver.resolveTransitiv
ely(DefaultArtifactResolver.java:316)
at org.apache.maven.artifact.resolver.DefaultArtifactResolver.resolveTransitiv
ely(DefaultArtifactResolver.java:304)
at org.apache.maven.plugin.DefaultPluginManager.ensurePluginContainerIsComplet
e(DefaultPluginManager.java:835)
at org.apache.maven.plugin.DefaultPluginManager.getConfiguredMojo(DefaultPlugi
nManager.java:647)
at org.apache.maven.plugin.DefaultPluginManager.executeMojo(DefaultPluginManag
er.java:468)
at org.apache.maven.lifecycle.DefaultLifecycleExecutor.executeGoals(DefaultLif
ecycleExecutor.java:694)
at org.apache.maven.lifecycle.DefaultLifecycleExecutor.executeGoalWithLifecycl
e(DefaultLifecycleExecutor.java:556)
at org.apache.maven.lifecycle.DefaultLifecycleExecutor.executeGoal(DefaultLife
cycleExecutor.java:535)
at org.apache.maven.lifecycle.DefaultLifecycleExecutor.executeGoalAndHandleFai
lures(DefaultLifecycleExecutor.java:387)
at org.apache.maven.lifecycle.DefaultLifecycleExecutor.executeTaskSegments(Def
aultLifecycleExecutor.java:348)
at o


[Johan Parent]

Similar issue but with a7 using the same javaagent to spice up IntelliJ10
performance just a bit more. Works great, worked great for 6days but just now
I got a similar glitch. A click did not trigger any action in the UI. On the
2nd time it did. So I found this output (matching the previous post).

At first I though my previous post's result was because I was not using rc1
after all but the line numbers in the stack trace are indeed different.

Regards,

Johan


ERROR - com.intellij.ide.IdeEventQueue - Error during dispatching of
java.awt.event.InvocationEvent on sun.awt.windows.WToolkit
@1d201c8
java.lang.IllegalArgumentException: Equal objects must have equal hashcodes.
During rehashing, Trove discovered that the following two objec
ts claim to be equal (as in java.lang.Object.equals()) but their hashCodes (or
those calculated by your TObjectHashingStrategy) are not equa
l.This violates the general contract of java.lang.Object.hashCode(). See
bullet point two in that method's documentation. object #1 =null;
object #2 =null
at gnu.trove.impl.hash.TObjectHash.throwObjectContractViolation(TObjectHash.ja
va:277)
at gnu.trove.map.hash.THashMap.rehash(THashMap.java:401)
at gnu.trove.impl.hash.THash.postInsertHook(THash.java:387)
at gnu.trove.map.hash.THashMap.doPut(THashMap.java:174)
at gnu.trove.map.hash.THashMap.put(THashMap.java:139)
at be.biggerbytes.patch4j.delegates.trove.DHashMap.put(DHashMap.java:62)
at com.intellij.ide.util.treeView.AbstractTreeUi.createMapping(AbstractTreeUi.
java:4249)
at com.intellij.ide.util.treeView.AbstractTreeUi.access$1600(AbstractTreeUi.ja
va:56)
at
com.intellij.ide.util.treeView.AbstractTreeUi$41.run(AbstractTreeUi.java:2132)
at com.intellij.openapi.util.ExecutionCallback.callback(ExecutionCallback.java
:72)
at com.intellij.openapi.util.ExecutionCallback.doWhenExecuted(ExecutionCallbac
k.java:53)
at com.intellij.openapi.util.ActionCallback.doWhenDone(ActionCallback.java:85)
at com.intellij.ide.util.treeView.AbstractTreeUi.collectNodesToInsert(Abstract
TreeUi.java:2115)
at com.intellij.ide.util.treeView.AbstractTreeUi.access$4700(AbstractTreeUi.ja
va:56)
at
com.intellij.ide.util.treeView.AbstractTreeUi$28.run(AbstractTreeUi.java:1255)
at com.intellij.openapi.util.ExecutionCallback.callback(ExecutionCallback.java
:72)
at com.intellij.openapi.util.ExecutionCallback.setExecuted(ExecutionCallback.j
ava:37)
at com.intellij.openapi.util.ActionCallback.setDone(ActionCallback.java:63)
at com.intellij.openapi.util.ActionCallback$4.run(ActionCallback.java:119)
at com.intellij.openapi.util.ExecutionCallback.callback(ExecutionCallback.java
:72)
at com.intellij.openapi.util.ExecutionCallback.doWhenExecuted(ExecutionCallbac
k.java:53)
at com.intellij.openapi.util.ActionCallback.doWhenDone(ActionCallback.java:85)
at com.intellij.openapi.util.ActionCallback.notify(ActionCallback.java:117)
at
com.intellij.ide.util.treeView.AbstractTreeUi$32.run(AbstractTreeUi.java:1601)
at com.intellij.ide.util.treeView.AbstractTreeUi.executeYieldingRequest(Abstra
ctTreeUi.java:1901)
at com.intellij.ide.util.treeView.AbstractTreeUi.access$6000(AbstractTreeUi.ja
va:56)
at com.intellij.ide.util.treeView.AbstractTreeUi$36$1.run(AbstractTreeUi.java:
1797)
at com.intellij.util.ui.UIUtil.invokeLaterIfNeeded(UIUtil.java:1366)
at com.intellij.ide.util.treeView.AbstractTreeBuilder.runOnYeildingDone(Abstra
ctTreeBuilder.java:315)
at com.intellij.ide.util.treeView.AbstractTreeUi.runOnYieldingDone(AbstractTre
eUi.java:2002)
at
com.intellij.ide.util.treeView.AbstractTreeUi$36.run(AbstractTreeUi.java:1793)
at java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:209)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:597)
at com.intellij.ide.IdeEventQueue.e(IdeEventQueue.java:652)
at com.intellij.ide.IdeEventQueue._dispatchEvent(IdeEventQueue.java:505)
at com.intellij.ide.IdeEventQueue.b(IdeEventQueue.java:404)
at com.intellij.ide.IdeEventQueue.dispatchEvent(IdeEventQueue.java:368)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.jav
a:269)
at
java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:184)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.jav
a:174)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:169)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:161)
at java.awt.EventDispatchThread.run(EventDispatchThread.java:122)


[Rob Eden]

Not sure there's much I can do about this. If they're not correctly
implementing the hashCode contract then all bets are off on how we'd function.
So, that's why the check was put in place.

[Johan Parent]

Hi Rob,

Thanks for your reply. I'm happy to report that I solved the problem! It was
under my nose all the time. No, it was not a broken hashCode issue at all. In
fact the keys in the cases reported above are Integer instances. Come to think
of it why would a rehash() after a remove() cause a sudden issue. That's what
kept puzzling me. And so I digged for a few evenings till I found the naughty
optimization that was the proverbial root for this evil.

It is too late for me right now to produce a usable patch with all the probing
and changes I made in the code. I'll post something tomorrow evening (CET). I
also want to suggest some minor performance patches related to unnecessary
rehash() operations as well.

Best regards,

Johan

[Johan Parent]

Hi Rob & all,

As promised the patch. Can this be reviewed please. It fixes the reported
issues and offer some minor speed improvements.

Best regards,

Johan

Index: src/gnu/trove/impl/hash/TObjectHash.java
===================================================================
--- src/gnu/trove/impl/hash/TObjectHash.java    (revision 46)
+++ src/gnu/trove/impl/hash/TObjectHash.java    (revision )
@@ -178,7 +178,7 @@
                 }
                 cur = set[index];
             } while ( cur != FREE
-                      && ( cur == REMOVED || !equals( cur, obj ) ) );
+                      && ( cur == REMOVED || !( cur == obj || equals( cur, obj) ) ) ); // Patched Johan Parent
         }

         return cur == FREE ? -1 : index;
@@ -232,8 +232,8 @@
                     cur = set[index];
                 } while ( cur != FREE
                           && cur != REMOVED
-                          && cur != obj
-                          && !equals( cur, obj ) );
+                          && !(cur == obj || equals( cur, obj )) // Patched Johan Parent
+                        );
             }

             // if the index we found was removed: continue probing until we
@@ -242,7 +242,7 @@
             if ( cur == REMOVED ) {
                 int firstRemoved = index;
                 while ( cur != FREE
-                        && ( cur == REMOVED || cur != obj || !equals( cur, obj ) ) ) {
+                        && ( cur == REMOVED || !(cur == obj || equals( cur, obj) ) ) ) { // Patched Johan Parent
                     index -= probe;
                     if ( index < 0 ) {
                         index += length;
@@ -250,7 +250,8 @@
                     cur = set[index];
                 }
                 // NOTE: cur cannot == REMOVED in this block
-                return ( cur != FREE ) ? -index - 1 : firstRemoved;
+                // Patched Johan Parent: if FREE return index instead of firstRemoved
+                return ( cur != FREE ) ? -index - 1 : index;
             }
             // if it's full, the key is already stored
             // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)