AbstractFlowSet equals/hashCode contract issues about soot

[ericbodden]

Hi Tarsis. Thanks for this. I will move the discussion to the Soot mailing list, though, because that will give us a broader and more informed audience... Please check back there...

[ericbodden]

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 [email protected] 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(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 GitHubhttps://github.com//issues/11.

Eric Bodden, Ph.D., http://sse.ec-spride.de/ http://bodden.de/
Head of Secure Software Engineering Group at EC SPRIDE
Tel: [phone] Fax: [phone]
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt

[ericbodden]

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 [email protected] 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: [phone]    Fax: [phone]
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt

[ericbodden]

Hi all.

Tarsis I have committed a fix as you suggested: hashCode now ignores
the order, equals checks that the runtime types are the same (using
getClass()). We will see in our nightly test runs if this breaks
something. Hopefully not...

Eric

On 9 November 2012 18:08, Ondřej Lhoták [email protected] wrote:

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 [email protected] 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: [phone] Fax: [phone]
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt

Eric Bodden, Ph.D., http://sse.ec-spride.de/ http://bodden.de/
Head of Secure Software Engineering Group at EC SPRIDE
Tel: [phone] Fax: [phone]
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt

[tarsiswt]

Thanks a lot Eric. I'm glad to be of help.
Em 11/11/2012 06:06, "Eric Bodden" [email protected] escreveu:

Hi all.

Tarsis I have committed a fix as you suggested: hashCode now ignores
the order, equals checks that the runtime types are the same (using
getClass()). We will see in our nightly test runs if this breaks
something. Hopefully not...

Eric

On 9 November 2012 18:08, Ondřej Lhoták [email protected] wrote:

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 [email protected]
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(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: [phone] Fax: [phone]
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt

Eric Bodden, Ph.D., http://sse.ec-spride.de/ http://bodden.de/
Head of Secure Software Engineering Group at EC SPRIDE
Tel: [phone] Fax: [phone]
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/11#issuecomment-10264519.

[ericbodden]

Seems to have worked. I am closing this thread. Thanks again Tarsis!