starting implementation for access paths to improve edge mapping

diff --git a/Robust/src/Analysis/OwnershipAnalysis/AccessPath.java b/Robust/src/Analysis/OwnershipAnalysis/AccessPath.java
new file mode 100644 (file)
index 0000000..afab114
--- /dev/null
+++ b/Robust/src/Analysis/OwnershipAnalysis/AccessPath.java
@@ -0,0 +1,57 @@
+package Analysis.OwnershipAnalysis;
+
+import IR.*;
+import IR.Flat.*;
+import java.util.*;
+
+// An access path is relevant in a callee method to
+// a caller's heap.  When mapping edges from a callee
+// into the caller, if the caller's heap does not have
+// any matching access paths, then the edge could not
+// exist in that context and is ignored.
+
+public class AccessPath {
+
+  public AccessPath() {
+  }
+
+  public boolean equals( Object o ) {
+    if( o == null ) {
+      return false;
+    }
+
+    if( !(o instanceof AccessPath) ) {
+      return false;
+    }
+
+    return true;
+    /*
+    VariableSourceToken vst = (VariableSourceToken) o;
+
+    // the reference vars have no bearing on equality
+    return    sese.equals( vst.sese    ) &&
+           addrVar.equals( vst.addrVar ) &&
+           seseAge.equals( vst.seseAge );
+    */
+  }
+
+  public int hashCode() {
+    // the reference vars have no bearing on hashCode
+    return 1; //(sese.hashCode() << 3) * (addrVar.hashCode() << 4) ^ seseAge.intValue();
+  }
+
+  public String toString() {
+    return "ap";
+  }
+
+  public String toStringForDOT() {
+    /*
+    if( disjointId != null ) {
+      return "disjoint "+disjointId+"\\n"+toString()+"\\n"+getType().toPrettyString();
+    } else {
+      return                              toString()+"\\n"+getType().toPrettyString();
+    }
+    */
+    return "do";
+  }  
+}

diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
index 6df454bcea0a6db76cc50f9cf86b15ecc962fb1a..feca5776a328256e7dfd0cc0cbbf211ab17abbf2 100644 (file)
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
@@ -2,6 +2,7 @@ package Analysis.OwnershipAnalysis;
 
 import IR.*;
 import IR.Flat.*;
+import Util.UtilAlgorithms;
 import java.util.*;
 import java.io.*;
 
@@ -75,6 +76,17 @@ public class OwnershipGraph {
   public Hashtable<Integer, TokenTuple> paramIndex2paramTokenSecondaryStar;
 
 
+  // consult these sets in algorithms when considering what
+  // to do with temps or their label nodes found in the graph
+  public Set<TempDescriptor> outOfScopeTemps;
+  public Set<LabelNode>      outOfScopeLabels;
+  public Set<TempDescriptor> parameterTemps;
+  public Set<LabelNode>      parameterLabels;
+
+  // this is kept to allow edges created from variables (a src and dst)
+  // to know the access paths that allowed it, to prune edges when
+  // mapping them back into the caller--an access path must appear
+  public Hashtable< TempDescriptor, Set<AccessPath> > temp2accessPaths;
 
 
 
@@ -100,6 +112,16 @@ public class OwnershipGraph {
     paramIndex2paramTokenSecondaryStar = new Hashtable<Integer,        TokenTuple    >();
 
     allocationSites = new HashSet <AllocationSite>();
+
+    outOfScopeTemps  = new HashSet<TempDescriptor>(); 
+    outOfScopeLabels = new HashSet<LabelNode>();      
+    parameterTemps   = new HashSet<TempDescriptor>(); 
+    parameterLabels  = new HashSet<LabelNode>();
+
+    outOfScopeTemps.add( tdReturn );
+    outOfScopeLabels.add( getLabelNodeFromTemp( tdReturn ) );
+
+    temp2accessPaths = new Hashtable< TempDescriptor, Set<AccessPath> >();
   }
 
 
@@ -644,12 +666,19 @@ public class OwnershipGraph {
                                                         null,       // reachability set                 
                                                         "param"+paramIndex+" obj" );
 
+    parameterTemps.add( td );
+    parameterLabels.add( lnParam );
+
+
     // this is a non-program-accessible label that picks up beta
     // info to be used for fixing a caller of this method
     TempDescriptor tdParamQ = new TempDescriptor( td+qString );
     paramIndex2tdQ.put( paramIndex, tdParamQ );    
     LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
 
+    outOfScopeTemps.add( tdParamQ );
+    outOfScopeLabels.add( lnParamQ );
+
     // keep track of heap regions that were created for
     // parameter labels, the index of the parameter they
     // are for is important when resolving method calls
@@ -659,11 +688,11 @@ public class OwnershipGraph {
     s.add( paramIndex );
     idPrimary2paramIndexSet.put( newPrimaryID, s );
     paramIndex2idPrimary.put( paramIndex, newPrimaryID );
-
     
     TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
                                           false, // multi-object
                                           TokenTuple.ARITY_ONE ).makeCanonical();    
+
         
     HeapRegionNode hrnSecondary   = null;
     Integer        newSecondaryID = null;
@@ -676,6 +705,9 @@ public class OwnershipGraph {
       paramIndex2tdR.put( paramIndex, tdParamR );    
       lnParamR = getLabelNodeFromTemp( tdParamR );
 
+      outOfScopeTemps.add( tdParamR );
+      outOfScopeLabels.add( lnParamR );
+
       hrnSecondary = createNewHeapRegionNode( null,  // id or null to generate a new one  
                                              false, // single object?                   
                                              false, // summary?                         
@@ -796,6 +828,10 @@ public class OwnershipGraph {
   public void makeAliasedParamHeapRegionNode() {
 
     LabelNode lnBlob = getLabelNodeFromTemp( tdAliasBlob );
+
+    outOfScopeTemps.add( tdAliasBlob );
+    outOfScopeLabels.add( lnBlob );
+
     HeapRegionNode hrn = createNewHeapRegionNode( null,  // id or null to generate a new one 
                                                  false, // single object?                       
                                                  false, // summary?                     
@@ -833,6 +869,9 @@ public class OwnershipGraph {
     LabelNode lnParam   = getLabelNodeFromTemp( tdParam );    
     LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob );
 
+    parameterTemps.add( tdParam );
+    parameterLabels.add( lnParam );
+
     // this is a non-program-accessible label that picks up beta
     // info to be used for fixing a caller of this method
     TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString );
@@ -844,6 +883,11 @@ public class OwnershipGraph {
     LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
     LabelNode lnParamR = getLabelNodeFromTemp( tdParamR );
 
+    outOfScopeTemps.add( tdParamR );
+    outOfScopeLabels.add( lnParamR );
+    outOfScopeTemps.add( tdParamQ );
+    outOfScopeLabels.add( lnParamQ );
+
     // the lnAliased should always only reference one node, and that
     // heap region node is the aliased param blob
     assert lnAliased.getNumReferencees() == 1;
@@ -3719,6 +3763,8 @@ public class OwnershipGraph {
     mergeReferenceEdges(og);
     mergeParamIndexMappings(og);
     mergeAllocationSites(og);
+    mergeAccessPaths(og);
+    mergeTempAndLabelCategories(og);
   }
 
 
@@ -3949,6 +3995,18 @@ public class OwnershipGraph {
     allocationSites.addAll(og.allocationSites);
   }
 
+  protected void mergeAccessPaths(OwnershipGraph og) {
+    UtilAlgorithms.mergeHashtablesWithHashSetValues(temp2accessPaths,
+                                                   og.temp2accessPaths);
+  }
+
+  protected void mergeTempAndLabelCategories(OwnershipGraph og) {
+    outOfScopeTemps.addAll(og.outOfScopeTemps);
+    outOfScopeLabels.addAll(og.outOfScopeLabels);
+    parameterTemps.addAll(og.parameterTemps);
+    parameterLabels.addAll(og.parameterLabels);
+  }
+
 
 
   // it is necessary in the equals() member functions
@@ -3983,10 +4041,18 @@ public class OwnershipGraph {
       return false;
     }
 
+    if( !areAccessPathsEqual(og) ) {
+      return false;
+    }
+
     // if everything is equal up to this point,
     // assert that allocationSites is also equal--
     // this data is redundant and kept for efficiency
-    assert allocationSites.equals(og.allocationSites);
+    assert allocationSites .equals(og.allocationSites );
+    assert outOfScopeTemps .equals(og.outOfScopeTemps );
+    assert outOfScopeLabels.equals(og.outOfScopeLabels);
+    assert parameterTemps  .equals(og.parameterTemps  );
+    assert parameterLabels .equals(og.parameterLabels );
 
     return true;
   }
@@ -4187,6 +4253,12 @@ public class OwnershipGraph {
   }
 
 
+  protected boolean areAccessPathsEqual(OwnershipGraph og) {
+    return temp2accessPaths.equals( og.temp2accessPaths );
+  }
+
+
+
   public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
     assert hrn1 != null;
     assert hrn2 != null;

diff --git a/Robust/src/Makefile b/Robust/src/Makefile
index 35b1bc32d494c3095ba2ad57764b66f2b7f36678..2c00241650ba4bfadcc89e589ee6c56df8beceaf 100644 (file)
--- a/Robust/src/Makefile
+++ b/Robust/src/Makefile
@@ -88,12 +88,14 @@ Analysis/OwnershipAnalysis/ChangeTupleSet.class                         \
 Analysis/OwnershipAnalysis/Canonical.class                              \
 Analysis/OwnershipAnalysis/MethodContext.class                          \
 Analysis/OwnershipAnalysis/ParameterDecomposition.class                        \
+Analysis/OwnershipAnalysis/AccessPath.class                             \
 Analysis/MLP/MLPAnalysis.class                                                 \
 Analysis/MLP/VariableSourceToken.class                                         \
 Analysis/MLP/SVKey.class                                               \
 Analysis/MLP/VarSrcTokTable.class                                      \
 Analysis/MLP/CodePlan.class                                            \
 Util/GraphNode.class Util/Namer.class Util/Relation.class              \
+Util/UtilAlgorithms.class                                               \
 Interface/HTTPHeader.class Interface/HTTPResponse.class                        \
 Interface/HTTPServices.class Interface/HashStrings.class               \
 Interface/JhttpServer.class Interface/JhttpWorker.class                        \

diff --git a/Robust/src/Tests/OwnershipAnalysisTest/mappingWeakness/test.java b/Robust/src/Tests/OwnershipAnalysisTest/mappingWeakness/test.java
index b5d6ffa0de4e098545a2f6a11590f82d010cc07c..e0a29a808435e12fec78123a5d6897e5aa9b7048 100644 (file)
--- a/Robust/src/Tests/OwnershipAnalysisTest/mappingWeakness/test.java
+++ b/Robust/src/Tests/OwnershipAnalysisTest/mappingWeakness/test.java
@@ -1,5 +1,5 @@
 public class Test {
-  static public void main( String[] args ) {    
+  static public void main( String[] args ) {
     int n = 10;
     Vector v1 = new Vector( n );
     for( int i = 0; i < n; ++i ) {

diff --git a/Robust/src/Util/UtilAlgorithms.java b/Robust/src/Util/UtilAlgorithms.java
new file mode 100644 (file)
index 0000000..fd021d0
--- /dev/null
+++ b/Robust/src/Util/UtilAlgorithms.java
@@ -0,0 +1,34 @@
+package Util;
+import java.util.*;
+
+// this class has static methods that implement useful,
+// non-trivially algorithms to prevent code duplication
+// and reduce bugs
+
+public class UtilAlgorithms {
+
+  // This method merge hashtable b into a, where the
+  // tables both have HashSets as the values.  If both
+  // tables have a common key, the new value is the
+  // union of the sets the key mapped to in each one.
+  // Note: the reason it must be a HashSet instead of
+  // a Set is that we want to clone sets of table b, so
+  // only a is modified.  Set does not provide clone().
+  static public void mergeHashtablesWithHashSetValues( Hashtable a,
+                                                      Hashtable b ) {
+    Iterator itr = b.entrySet().iterator();
+    while( itr.hasNext() ) {
+      Map.Entry me  = (Map.Entry) itr.next();
+      Object    key = (Object)    me.getKey();
+      HashSet   s1  = (HashSet)   me.getValue();
+      HashSet   s2  = (HashSet)   a.get( key );
+
+      if( s2 == null ) {
+       a.put( key, s1.clone() );
+      } else {
+       s2.addAll( s1 );
+      }
+    }
+  }
+
+}