using HashCodeComparator in class loading may and does cause instabilities

[mohrm]

In ClassLoaderImpl, the method getClassFiles is responsible for retrieving all the module entries from a module and returning them as a set. For this, first the iterator is converted into a list and then this list is inserted into a TreeSet, using a comparator which compares two module entries by hash code (!).
I think this is highly fragile. The Java API doc clearly says that TreeSet relies on the used compareTo method being consistent with equals. In particular, TreeSet uses compareTo == 0 as eqality check. The used HashCodeComparator is not consistent with equals as there may be collisions. So, using a HashCodeComparator in getClassFiles may accidentally delete module entries.

I also think that there is a connection of this issue to #88. The dalvik front-end class DexClassLoaderImpl contains a method which is similar to getClassFiles (getDexFiles). The bad thing is that the DexModuleEntry class it processes does not implement hashCode or equals. I think this causes the flakiness, since now System.identityHashCode is used which is completely unpredictable.
One simple fix would be to implement hashCode and equals consistently for DexModuleEntry.

Another possible solution would be to not use TreeSet and HashCodeComparator but a LinkedHashSet.

I am in favor of the latter solution because it is more robust. I also don't think that it is really necessary to first unroll an iterator into a list and then insert all list items into a set, so removing this code would not only make it more robust but also faster and simpler.

@juliandolby @msridhar What do you think?

[juliandolby]

Martin, This seems like an important issue; thanks for finding it. I think making sure equals, hahsCode and compareTo are all consistent is good to do anyway, so that seems like the right fix to me. — Julian

…

On Jan 26, 2017, at 5:32 AM, Martin Mohr ***@***.***> wrote: In ClassLoaderImpl, the method getClassFiles is responsible for retrieving all the module entries from a module and returning them as a set. For this, first the iterator is converted into a list and then this list is inserted into a TreeSet, using a comparator which compares two module entries by hash code (!). I think this is highly fragile. The Java API doc <https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html> clearly says that TreeSet relies on the used compareTo method being consistent with <https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html> equals. In particular, TreeSet uses compareTo == 0 as eqality check. The used HashCodeComparator is not consistent with equals as there may be collisions. So, using a HashCodeComparator in getClassFiles may accidentally delete module entries. I also think that there is a connection of this issue to #88 <#88>. The dalvik front-end class DexClassLoaderImpl contains a method which is similar to getClassFiles (getDexFiles). The bad thing is that the DexModuleEntry class it processes does not implement hashCode or equals. I think this causes the flakiness, since now System.identityHashCode is used which is completely unpredictable. Another simple fix would be to implement hashCode and equals properly (i.e. consistent) for DexModuleEntryI cannot say for sure what happens exactly, but my experiments show that WALAs whole behaviour becomes more predictable after I tried this. Another possible solution would be to not use TreeSet and HashCodeComparator but a LinkedHashSet. @juliandolby <https://github.com/juliandolby> @msridhar <https://github.com/msridhar> What do you think? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#133>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABk3fhvsaD2Wsy73clwizyKNXG2KJnbPks5rWHY4gaJpZM4Lufe7>.

[mohrm]

@juliandolby What do you think about getting rid of HashCodeComparator, as proposed in #134? This not only seems more robust to me but also simpler and faster.

[juliandolby]

That seems like a good idea too.

…

On Jan 26, 2017, at 9:02 AM, Martin Mohr ***@***.***> wrote: @juliandolby <https://github.com/juliandolby> What do you think about getting rid of HashCodeComparator, as proposed in #134 <#134>? This not only seems more robust to me but also simpler and faster. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#133 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABk3fpQlYySYh1rke4unz_P3-O_zjsfiks5rWKd_gaJpZM4Lufe7>.

[msridhar]

Fixed by #134