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

[Rhodes H. F. Brown]

Hi,

I've been poking through the soot.toolkits.scalar.FlowSet (and  
related classes), and I've come across some inconsistencies in the  
spec & implementations of FlowSet.difference().

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."

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();

Assuming the new definition is correct, all relevant javadocs in the  
hierarchy need to be updated. Also any analyses that use a sub-class  
of AbstractFlowSet that is not ArrayPackedSet or ArraySparseSet  
should be checked since they may be using an invalid difference  
operation.

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.

Cheers,
Rhodes