[Soot-list] [soot] AbstractFlowSet equals/hashCode contract issues (#11)

[Eric Bodden]

Hi Tarsis.

Thanks a lot for those hints. I think personally think your assessment is
correct. Having said that, Soot has quite some code that depends on those
set implementations and there may be some good reason for seeing the
implementation we have today. (For instance I seem to remember that there
were some parts of Spark that use instance-equality for performance reasons.

Does anyone remember? Ondrej or Patrick maybe?

Cheers,
Eric


On 8 November 2012 21:23, Tarsis Toledo <notifications at github.com> wrote:

> Hello,
>
> First of all, thanks for the wonderful open source framework.
>
> I'd like to draw your attention to the current implementation of the
> AbstractFlowSet implementation and its subclasses wrt to the
> equals/hashCode contract. I've encountered several issues:
>
> 1) Violation of the hashCode contract (equal objects must have the same
> hashCode).
> For example, take the following snippet:
>
> ArraySparseSet ars1 = new ArraySparseSet();ars1.add("a");ars1.add("b");
> ArraySparseSet ars2 = new ArraySparseSet();ars2.add("b");ars2.add("a");
> System.out.println(ars1.equals(ars2)); // trueSystem.out.println(ars1.hashCode() == ars2.hashCode()); // false; violates the hashCode contract
>
> AbstractFlowSet also accept intertype equality, but fails to comply to the
> hashCode contract:
>
> ArrayPackedSet aps = new ArrayPackedSet(new CollectionFlowUniverse<String>(Arrays.asList("a","b")));aps.add("b");aps.add("a");
> System.out.println(ars1.equals(aps)); // trueSystem.out.println(ars1.hashCode() == aps.hashCode()); // false; violates the hashCode contract
>
> This happens because the hashCode is calculated based on the iteration
> order, whereas the equals checks for equality independent of order.
>
> One way to fix this could be to relax the hashCode implementation below:
>
> public int hashCode() {
>     final int PRIME = 31;
>     int result = 1;
>     Iterator iter = iterator();
>     while(iter.hasNext()) {
>         Object o = iter.next();
>         result = PRIME * result + o.hashCode();
>     }
>     return result;}
>
> to something like:
>
> public int hashCode() {
>     int result = 1;
>     Iterator iter = iterator();
>     while(iter.hasNext()) {
>         Object o = iter.next();
>         result += o.hashCode();
>     }
>     return result;}
>
> 2) One consequence of allowing intertype equality (like the comparisson
> between ArrayPackedSet and ArraySparseSet above) is that it is very hard to
> comply with the simmetry clause of the equals contract:
>
> ToppedSet ts1 = new ToppedSet(ars1);System.out.println(ts1.equals(ars1)); // falseSystem.out.println(ars1.equals(ts1)); // true; violates the simmetry clause of the equals contract
>
> 3) and also to comply with the transitivity clause. Suppose the following
> class:
>
> class MyFlowSet extends ArraySparseSet {
>     private int myState = 0;
>
>     public void setState(int state) {
>         myState = state;
>     }
>
>     @Override
>     public boolean equals(Object otherFlow) {
>         if (otherFlow instanceof MyFlowSet) {
>             MyFlowSet other = (MyFlowSet) otherFlow;
>             if (other.numElements != this.numElements || other.myState != this.myState)
>                 return false;
>
>             for(int i = 0; i < this.numElements; i++)
>                 if(!other.contains(this.elements[i]))
>                     return false;
>             return true;
>         }
>
>         return super.equals(otherFlow);
>     }
>
>     @Override
>     public List toList() {
>         return super.toList();
>     }}
>
> Because intertype equality is allowed, the following case can emerge:
>
> MyFlowSet mfs1 = new MyFlowSet();mfs1.add("a");mfs1.add("b");
> MyFlowSet mfs2 = new MyFlowSet();mfs2.add("a");mfs2.add("b");mfs2.setState(1);
> System.out.println(mfs1.equals(ars1)); // trueSystem.out.println(mfs2.equals(ars1)); // trueSystem.out.println(mfs1.equals(mfs2)); // false; violates the transitivity clause of the equals contract
>
> I believe that many of these issues could be avoided by separating the
> object equality from the "content equality", maybe using the EquivTo
> interface, or by disallowing intertype equality. Both of these alternatives
> will most likely break backwards compatibility wth existing code.
>
> Are any of these two alternatives viable options? What are the developers
> position on this?
>
> Thanks!
>
> —
> Reply to this email directly or view it on GitHub<https://github.com/Sable/soot/issues/11>.
>
>



-- 
Eric Bodden, Ph.D., http://sse.ec-spride.de/ http://bodden.de/
Head of Secure Software Engineering Group at EC SPRIDE
Tel: +49 6151 16-75422    Fax: +49 6151 16-72051
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20121108/2417c466/attachment.html