[Soot-list] Bug with FlowSet.difference()?

[Ondrej Lhotak]

Hi Rhodes...

It's nice to hear from you.

On Tue, Oct 18, 2005 at 08:51:26PM -0700, Rhodes H. F. Brown wrote:
> The FlowSet spec (javadoc) says:
>      "Returns the set difference (this join ~other) of this FlowSet  
> and other..."
> 
> Based on the usual definition of "join" and "~", I read this as, "the  
> union of this set and the complement of other." Is this a correct  
> interpretation? If so, I believe that it is an incorrect definition  
> (see http://mathworld.wolfram.com/SetDifference.html).
> 
> It would seem that FlowSet.difference() should be defined as, "the  
> intersection of this set and the complement of other." Or, "this meet  
> ~other."

You're right. I've changed the javadoc to say "this intersect ~other".

> It appears that both ArrayPackedSet.difference() and  
> ArraySparseSet.difference() actually implement the second (correct)  
> definition, however AbstractFlowSet.difference() does not. A simple  
> correction should fix it though:
> 
> --- corrected   2005-10-18 20:30:30.000000000 -0700
> +++ AbstractFlowSet.java        2003-06-03 05:12:25.000000000 -0700
> @@ -131,7 +131,6 @@
>       Iterator it = this.toList().iterator();
>       FlowSet flowSet = (other == dest)? (FlowSet)other.clone(): other;
> -    dest.clear(); // now safe, since we have copies of this & other
> 
>       while (it.hasNext()) {
>         Object o = it.next();

I think this bug was just an error of omission rather than a
misunderstanding of the definition of set difference (ie someone meant
to put that line of code in but forgot). Anyway, I've applied your
patch.

> Why the nit-picking? Well, I'm in the process of re-writing the  
> FlowSet hierarchy to add several enhancements including (but limited  
> to):
> - update to use Java 5 generics to specify the type of a FlowSet element
> - make FlowSet implement java.util.Set (and thus java.lang.Iterable,  
> allowing one to use foreach with FlowSets)
> - enforce an implementation of hashCode() to make FlowSets hashable
> - provide faster amortized iteration over (unmodified) FlowSets
> 
> Should these updates prove stable and pleasant, I will happily offer  
> them back to the soot community.

That would be great.

Ondrej