Added more comments. Fixed some bugs.
[repair.git] / Repair / RepairCompiler / MCC / IR / GraphAnalysis.java
index 16a51f781861c0a263d3f88e263f629778309427..878f9392c108b68140434479ca871e6a54a6c042 100755 (executable)
@@ -15,15 +15,22 @@ public class GraphAnalysis {
     public GraphAnalysis(Termination t) {
        termination=t;
     }
-
+    /**  This method returns true if leaving node gn in the repair
+     *  dependence graph will not result in cycles.
+     gn = updatenode, conjunctionnode, consequence node
+    */
     private boolean safetransclosure(GraphNode gn, Set removed, Set cantremove, Set couldremove) {
        Stack workset=new Stack();
        HashSet closureset=new HashSet();
        boolean needcyclecheck=false;
        HashSet cantremovetrans=new HashSet();
        workset.push(gn);
+
+       /* Iterating over everything reachable from gn */
        while(!workset.empty()) {
            GraphNode gn2=(GraphNode)workset.pop();
+
+           /* Closureset is everything we've already iterated over */
            if (!closureset.contains(gn2)) {
                closureset.add(gn2);
                boolean goodoption=false;
@@ -31,11 +38,15 @@ public class GraphAnalysis {
                    GraphNode gn3=((GraphNode.Edge)edgeit.next()).getTarget();
                    if (removed.contains(gn3))
                        continue;
+
+                   /* Consider only the nodes in the graph */
+
+                   
                    if (((cantremove.contains(gn2)||!couldremove.contains(gn2))
                         &&termination.conjunctions.contains(gn2))||
                        cantremovetrans.contains(gn2))
                        cantremovetrans.add(gn3);
-                   
+
                    if (termination.abstractrepair.contains(gn3)||
                        termination.conjunctions.contains(gn3)||
                        termination.updatenodes.contains(gn3)) {
@@ -55,7 +66,7 @@ public class GraphAnalysis {
                if (!goodoption) {
                    if (termination.scopenodes.contains(gn2))
                        return false;
-               }                   
+               }
            }
        }
        if (needcyclecheck) {
@@ -97,7 +108,7 @@ public class GraphAnalysis {
            for(Iterator it=termination.consequencenodes.iterator();it.hasNext();) {
                GraphNode gn=(GraphNode) it.next();
                if (safetransclosure(gn, mustremove,cantremove, couldremove)) {
-                           couldremove.remove(gn);
+                   couldremove.remove(gn);
                }
            }
 
@@ -105,8 +116,8 @@ public class GraphAnalysis {
 
            for(Iterator it=termination.updatenodes.iterator();it.hasNext();) {
                GraphNode gn=(GraphNode) it.next();
-               if (safetransclosure(gn, mustremove,cantremove, cantremove)) {
-                       couldremove.remove(gn);
+               if (safetransclosure(gn, mustremove,cantremove, couldremove)) {
+                   couldremove.remove(gn);
                }
            }
 
@@ -116,6 +127,8 @@ public class GraphAnalysis {
                GraphNode gn=(GraphNode) it.next();
                if (mustremove.contains(gn)||cantremove.contains(gn))
                    continue;
+               if (!safetransclosure(gn, mustremove,cantremove, couldremove))
+                    continue;
 
                boolean allgood=true;
                for(Iterator edgeit=gn.edges();edgeit.hasNext();) {
@@ -124,7 +137,7 @@ public class GraphAnalysis {
                    assert tn2.getType()==TermNode.ABSTRACT;
                    boolean foundupdate=false;
                    for(Iterator edgeit2=gn2.edges();edgeit2.hasNext();) {
-                       GraphNode gn3=((GraphNode.Edge)edgeit2.next()).getTarget();                 
+                       GraphNode gn3=((GraphNode.Edge)edgeit2.next()).getTarget();
                        if (!couldremove.contains(gn3)&&!mustremove.contains(gn3)) {
                            TermNode tn3=(TermNode)gn3.getOwner();
                            if (tn3.getType()==TermNode.UPDATE)
@@ -153,7 +166,7 @@ public class GraphAnalysis {
 
 
            /* Look for constraints which can only be satisfied one way */
-           
+
            Vector constraints=termination.state.vConstraints;
            for(int i=0;i<constraints.size();i++) {
                Constraint c=(Constraint)constraints.get(i);
@@ -170,9 +183,10 @@ public class GraphAnalysis {
            }
 
 
-           /* Search through conjunction which must be satisfied, and attempt
-              to generate appropriate repair actions.
-            */
+           /* Search through conjunction nodes which must be
+              satisfied, and see if there are any data structure
+              updates that must exist. */
+
            HashSet newset=new HashSet();
            for(Iterator cit=cantremove.iterator();cit.hasNext();) {
                GraphNode gn=(GraphNode)cit.next();
@@ -226,7 +240,7 @@ public class GraphAnalysis {
                        change=true;
                }
            }
-           
+
            if (Compiler.AGGRESSIVESEARCH) {
                /* Aggressively remove compensation nodes */
                for(Iterator scopeit=termination.scopenodes.iterator();scopeit.hasNext();) {
@@ -311,7 +325,7 @@ public class GraphAnalysis {
            for(Iterator it=termination.conjunctions.iterator();it.hasNext();) {
                GraphNode gn=(GraphNode)it.next();
                boolean foundnocycle=false;
-
+               
                for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
                    GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
                    GraphNode gn2=e.getTarget();
@@ -328,7 +342,7 @@ public class GraphAnalysis {
                        TermNode tn3=(TermNode)gn3.getOwner();
                        if (tn3.getType()!=TermNode.UPDATE)
                            continue;
-
+                       
                        boolean containsgn=cantremove.contains(gn);
                        boolean containsgn2=cantremove.contains(gn2);
                        boolean containsgn3=cantremove.contains(gn3);
@@ -386,17 +400,11 @@ public class GraphAnalysis {
            /* Searches scope nodes + compensation nodes */
            for(Iterator it=termination.scopenodes.iterator();it.hasNext();) {
                GraphNode gn=(GraphNode)it.next();
-               int count=0;
                if (nodes.contains(gn)) {
                    for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
                        GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
                        GraphNode gn2=e.getTarget();
                        TermNode tn2=(TermNode)gn2.getOwner();
-                       
-                       if ((tn2.getType()==TermNode.CONSEQUENCE)&&
-                           !mustremove.contains(gn2))
-                           count++;
-                           
 
                        if (tn2.getType()!=TermNode.UPDATE)
                            continue;
@@ -405,42 +413,24 @@ public class GraphAnalysis {
                        boolean containsgn2=cantremove.contains(gn2);
                        cantremove.add(gn);
                        cantremove.add(gn2);
-                       
+
                        Set cycle=GraphNode.findcycles(cantremove);
                        if (cycle.contains(gn2)) {
                            if (!mustremove.contains(gn2)) {
                                change=true;
                                mustremove.add(gn2);
                            }
-                       } else {
-                           if (!mustremove.contains(gn2))
-                               count++;
-                       }
+                       } 
                        if (!containsgn)
                            cantremove.remove(gn);
                        if (!containsgn2)
                            cantremove.remove(gn2);
                    }
-               
-                   if (count==1) {
-                       for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
-                           GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
-                           GraphNode gn2=e.getTarget();
-                           TermNode tn2=(TermNode)gn2.getOwner();
-                           if ((tn2.getType()==TermNode.UPDATE||tn2.getType()==TermNode.CONSEQUENCE)&&
-                               !mustremove.contains(gn2)) {
-                               if (!cantremove.contains(gn2)) {
-                                   cantremove.add(gn2);
-                                   change=true;
-                               }
-                           }
-                       }
-                   }
                }
            }
            couldremove.removeAll(mustremove);
            couldremove.removeAll(cantremove);
-           
+
            Vector couldremovevector=new Vector();
            couldremovevector.addAll(couldremove);
            Vector combination=new Vector();
@@ -460,7 +450,7 @@ public class GraphAnalysis {
                e.printStackTrace();
                System.exit(-1);
            }
-           
+
            System.out.println("Searching set of "+couldremove.size()+" nodes.");
            System.out.println("Eliminated must "+mustremove.size()+" nodes");
            System.out.println("Eliminated cant "+cantremove.size()+" nodes");
@@ -479,22 +469,31 @@ public class GraphAnalysis {
                GraphNode gn=(GraphNode)it.next();
                System.out.println(gn.getTextLabel());
            }
-           
-           
+
+           System.out.println("==================================================");
            while(true) {
                if (illegal(combination,couldremovevector))
                    break;
                Set combinationset=buildset(combination,couldremovevector);
+                System.out.println("---------------------------");
+                for(Iterator it=combinationset.iterator();it.hasNext();) {
+                    System.out.println(((GraphNode)it.next()).getTextLabel());
+                }
+                System.out.println("---------------------------");
                checkmodify(combinationset);
                combinationset.addAll(mustremove);
                if (combinationset!=null) {
-                   System.out.println("Checkabstract="+checkAbstract(combinationset));
-                   System.out.println("Checkrepairs="+checkRepairs(combinationset));
-                   System.out.println("Checkall="+checkAll(combinationset));
-                   
-                   if (checkAbstract(combinationset)==0&&
-                       checkRepairs(combinationset)==0&&
-                       checkAll(combinationset)==0) {
+                    int checkabstract=checkAbstract(combinationset);
+                    int checkrep=checkRepairs(combinationset);
+                    int checkall=checkAll(combinationset);
+
+                   System.out.println("Checkabstract="+checkabstract);
+                   System.out.println("Checkrepairs="+checkrep);
+                   System.out.println("Checkall="+checkall);
+
+                   if (checkabstract==0&&
+                       checkrep==0&&
+                       checkall==0) {
                        return combinationset;
                    }
                }
@@ -522,7 +521,7 @@ public class GraphAnalysis {
                    if (!removednodes.contains(gn2)&&
                        tn2.getType()==TermNode.UPDATE) {
                        MultUpdateNode mun=tn2.getUpdate();
-                       
+
                        if (mun.getType()==MultUpdateNode.ADD)
                            numadd++;
                        if (mun.getType()==MultUpdateNode.REMOVE)
@@ -709,7 +708,7 @@ public class GraphAnalysis {
        tset.addAll(termination.consequencenodes);
        abstractnodes.retainAll(tset);
        Set cycles=GraphNode.findcycles(abstractnodes);
-       
+
        for(Iterator it=cycles.iterator();it.hasNext();) {
            GraphNode gn=(GraphNode)it.next();
            System.out.println("NODE: "+gn.getTextLabel());