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

[Ondřej Lhoták]

I don't know. Those implementations and design decisions are from before
my time.

On Thu, Nov 08, 2012 at 09:55:35PM +0100, Eric Bodden wrote:
> 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)); // true
>     System.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)); // true
>     System.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)); // false
>     System.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)); // true
>     System.out.println(mfs2.equals(ars1)); // true
>     System.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.
> 
> 
> 
> 
> --
> 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