Adding code to generate repair algorithms. Its not complete yet...

[repair.git] / Repair / RepairCompiler / MCC / IR / GraphAnalysis.java

diff --git a/Repair/RepairCompiler/MCC/IR/GraphAnalysis.java b/Repair/RepairCompiler/MCC/IR/GraphAnalysis.java
index fd3276752e3c28544c276b5e828498737363f68d..3488a66ab383d29183a3a1db02a447a8ffd13acd 100755 (executable)
--- a/Repair/RepairCompiler/MCC/IR/GraphAnalysis.java
+++ b/Repair/RepairCompiler/MCC/IR/GraphAnalysis.java
@@ -13,13 +13,118 @@ public class GraphAnalysis {
     public GraphAnalysis(Termination t) {
        termination=t;
     }
+
+    public Set doAnalysis() {
+       HashSet nodes=new HashSet();
+       nodes.addAll(termination.conjunctions);
+       GraphNode.computeclosure(nodes,null);
+       Set cycles=GraphNode.findcycles(nodes);
+       Set couldremove=new HashSet();
+       couldremove.addAll(termination.conjunctions);
+       couldremove.addAll(termination.updatenodes);
+       couldremove.addAll(termination.consequencenodes);
+       couldremove.retainAll(cycles);
+       Vector constraints=termination.state.vConstraints;
+       for(int i=0;i<constraints.size();i++) {
+           Constraint c=(Constraint)constraints.get(i);
+           Set conjunctionset=(Set)termination.conjunctionmap.get(c);
+           if (conjunctionset.size()==1)
+               couldremove.removeAll(conjunctionset);
+       }
+
+
+       Vector couldremovevector=new Vector();
+       couldremovevector.addAll(couldremove);
+       Vector combination=new Vector();
+
+       while(true) {
+           if (illegal(combination,couldremovevector))
+               break;
+           Set combinationset=buildset(combination,couldremovevector);
+           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) {
+                   return combinationset;
+               }
+           }
+           increment(combination,couldremovevector);
+       }
+       return null;
+    }
+
+    private static Set buildset(Vector combination, Vector couldremove) {
+       Set s=new HashSet();
+       for(int i=0;i<combination.size();i++) {
+           int index=((Integer)combination.get(i)).intValue();
+           Object o=couldremove.get(index);
+           if (s.contains(o))
+               return null;
+           else
+               s.add(o);
+       }
+       return s;
+    }
+
+    private static boolean illegal(Vector combination, Vector couldremove) {
+       if (combination.size()>couldremove.size())
+           return true;
+       else return false;
+    }
+    private static void increment(Vector combination, Vector couldremove) {
+       boolean incremented=false;
+       for(int i=0;i<combination.size();i++) {
+           int newindex=((Integer)combination.get(i)).intValue()+1;
+           while(combination.contains(new Integer(newindex)))
+               newindex++;
+           if (newindex==couldremove.size()) {
+               newindex=0;
+               combination.set(i,new Integer(newindex));
+           } else {
+               incremented=true;
+               combination.set(i,new Integer(newindex));
+               break;
+           }
+       }
+       if (incremented==false) /* Increase length */
+           combination.add(new Integer(0));
+    }
+
+    /* This function checks the graph as a whole for bad cycles */
+    public int checkAll(Collection removed) {
+       Set nodes=new HashSet();
+       nodes.addAll(termination.conjunctions);
+       nodes.removeAll(removed);
+       GraphNode.computeclosure(nodes,removed);
+       Set cycles=GraphNode.findcycles(nodes);
+       for(Iterator it=cycles.iterator();it.hasNext();) {
+           GraphNode gn=(GraphNode)it.next();
+           TermNode tn=(TermNode)gn.getOwner();
+           switch(tn.getType()) {
+           case TermNode.UPDATE:
+           case TermNode.CONJUNCTION:
+               return ERR_CYCLE;
+           case TermNode.ABSTRACT:
+           case TermNode.RULESCOPE:
+           case TermNode.CONSEQUENCE:
+           default:
+               break;
+           }
+       }
+       return WORKS;
+    }
+
     /* This function checks that
        1) All abstract repairs have a corresponding data structure update
           that isn't removed.
        2) All scope nodes have either a consequence node or a compensation
           node that isn't removed.
      */
-    public int checkRepairs(Set removed) {
+    public int checkRepairs(Collection removed) {
        Set nodes=new HashSet();
        nodes.addAll(termination.conjunctions);
        nodes.removeAll(removed);
@@ -35,23 +140,25 @@ public class GraphAnalysis {
            TermNode tn=(TermNode)gn.getOwner();
            if (tn.getType()==TermNode.RULESCOPE) {
                boolean foundnode=false;
-               for (Iterator edgeit=gn.edges();it.hasNext();) {
+               for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
                    GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
                    GraphNode gn2=edge.getTarget();
                    if (!removed.contains(gn2)) {
                        TermNode tn2=(TermNode)gn2.getOwner();
-                       if (tn2.getType()==TermNode.CONSEQUENCE||
-                           tn2.getType()==TermNode.UPDATE) {
+                       if ((tn2.getType()==TermNode.CONSEQUENCE)||
+                           (tn2.getType()==TermNode.UPDATE)) {
                            foundnode=true;
                            break;
                        }
                    }
                }
-               if (!foundnode)
+               if (!foundnode) {
+                   System.out.println(gn.getTextLabel());
                    return ERR_RULE;
+               }
            } else if (tn.getType()==TermNode.ABSTRACT) {
                boolean foundnode=false;
-               for (Iterator edgeit=gn.edges();it.hasNext();) {
+               for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
                    GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
                    GraphNode gn2=edge.getTarget();
                    if (!removed.contains(gn2)) {
@@ -68,10 +175,10 @@ public class GraphAnalysis {
        }
        return WORKS;
     }
-    /* This method checks that all constraints have a conjunction nodes
+    /* This method checks that all constraints have conjunction nodes
        and that there are no bad cycles in the abstract portion of the graph.
      */
-    public int checkAbstract(Set removed) {
+    public int checkAbstract(Collection removed) {
        Vector constraints=termination.state.vConstraints;
        for(int i=0;i<constraints.size();i++) {
            Constraint c=(Constraint)constraints.get(i);
@@ -99,9 +206,10 @@ 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());
            TermNode tn=(TermNode)gn.getOwner();
            switch(tn.getType()) {
            case TermNode.CONJUNCTION: