Checking in code to perform safety checks on repair dependency graph.

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

diff --git a/Repair/RepairCompiler/MCC/IR/UpdateNode.java b/Repair/RepairCompiler/MCC/IR/UpdateNode.java
index 31e954c03c053ca3764d979346fb627fb3075326..5bb92367fb1f67dcd78a77e2e774ee2bf3327ae2 100755 (executable)
--- a/Repair/RepairCompiler/MCC/IR/UpdateNode.java
+++ b/Repair/RepairCompiler/MCC/IR/UpdateNode.java
@@ -5,19 +5,172 @@ class UpdateNode {
     Vector updates;
     Vector bindings;
     Hashtable binding;
+    Rule rule;
+    
 
-    public UpdateNode() {
+    public UpdateNode(Rule r) {
        updates=new Vector();
        bindings=new Vector();
        binding=new Hashtable();
+       rule=r;
+    }
+
+    public Rule getRule() {
+       return rule;
+    }
+
+    public String toString() {
+       String st="";
+       for(int i=0;i<bindings.size();i++)
+           st+=bindings.get(i).toString()+"\n";
+       st+="---------------------\n";
+       for(int i=0;i<updates.size();i++)
+           st+=updates.get(i).toString()+"\n";
+       return st;
     }
 
     public void addBindings(Vector v) {
        for (int i=0;i<v.size();i++) {
-           bindings.add((Binding)v.get(i));
+           addBinding((Binding)v.get(i));
        }
     }
 
+    public boolean checkupdates() {
+       if (!checkconflicts()) /* Do we have conflicting concrete updates */
+           return false;
+       if (computeordering()) /* Ordering exists */
+           return true;
+       return false;
+    }
+
+    private boolean computeordering() {
+       /* Build dependency graph between updates */
+       HashSet graph=new HashSet();
+       Hashtable mapping=new Hashtable();
+       for(int i=0;i<updates.size();i++) {
+           Updates u=(Updates)updates.get(i);
+           GraphNode gn=new GraphNode(String.valueOf(i),u);
+           mapping.put(u, gn);
+           graph.add(gn);
+       }
+       for(int i=0;i<updates.size();i++) {
+           Updates u1=(Updates)updates.get(i);
+           if (u1.isAbstract())
+               continue;
+           for(int j=0;j<updates.size();j++) {
+               Updates u2=(Updates)updates.get(j);
+               if (!u2.isExpr())
+                   continue;
+               Descriptor d=u1.getDescriptor();
+               if (u2.getRightExpr().usesDescriptor(d)) {
+                   /* Add edge for dependency */
+                   GraphNode gn1=(GraphNode) mapping.get(u1);
+                   GraphNode gn2=(GraphNode) mapping.get(u2);
+                   GraphNode.Edge e=new GraphNode.Edge("dependency",gn2);
+                   gn1.addEdge(e);
+               }
+           }
+       }
+
+       if (!GraphNode.DFS.depthFirstSearch(graph))  /* DFS & check for acyclicity */
+           return false;
+
+        TreeSet topologicalsort = new TreeSet(new Comparator() {
+                public boolean equals(Object obj) { return false; }
+                public int compare(Object o1, Object o2) {
+                    GraphNode g1 = (GraphNode) o1;
+                    GraphNode g2 = (GraphNode) o2;
+                    return g2.getFinishingTime() - g1.getFinishingTime();
+                }
+            });
+       topologicalsort.addAll(graph);
+       Vector sortedvector=new Vector();
+       for(Iterator sort=topologicalsort.iterator();sort.hasNext();) {
+           GraphNode gn=(GraphNode)sort.next();
+           sortedvector.add(gn.getOwner());
+       }
+       updates=sortedvector; //replace updates with the sorted array
+       return true;
+    }
+
+    private boolean checkconflicts() {
+       Set toremove=new HashSet();
+       for(int i=0;i<updates.size();i++) {
+           Updates u1=(Updates)updates.get(i);
+           for(int j=0;j<updates.size();j++) {
+               Updates u2=(Updates)updates.get(j);
+               if (i==j)
+                   continue;
+               if (u1.isAbstract()||u2.isAbstract())
+                   continue;  /* Abstract updates are already accounted for by graph */
+               if (u1.getDescriptor()!=u2.getDescriptor())
+                   continue; /* No interference - different descriptors */
+               
+               if ((u1.getOpcode()==Opcode.GT||u1.getOpcode()==Opcode.GE)&&
+                   (u2.getOpcode()==Opcode.GT||u2.getOpcode()==Opcode.GE))
+                   continue; /* Can be satisfied simultaneously */
+
+               if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
+                   (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
+                   continue;
+               if ((u1.getOpcode()==u2.getOpcode())&&
+                   u1.isExpr()&&u2.isExpr()&&
+                   u1.getRightExpr().equals(null, u2.getRightExpr())) {
+                   /*We'll remove the second occurence*/
+                   if (i>j)
+                       toremove.add(u1);
+                   else
+                       toremove.add(u2);
+                   continue;
+               }
+
+               /* Handle = or != NULL */
+               if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
+                    ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
+                   (((u1.isExpr()&&u1.getRightExpr().isNull())&&(!u2.isExpr()||u2.getRightExpr().isNonNull()))
+                    ||((!u1.isExpr()||u1.getRightExpr().isNonNull())&&(u2.isExpr()&&u2.getRightExpr().isNull())))) {
+                   if (u1.getOpcode()==Opcode.NE)
+                       toremove.add(u1);
+                   else
+                       toremove.add(u2);
+                   continue;
+               }
+
+               /* Handle = and != to different constants */
+               if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
+                   ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
+                   (u1.isExpr()&&u1.getRightExpr() instanceof LiteralExpr)&&
+                   (u2.isExpr()&&u2.getRightExpr() instanceof LiteralExpr)&&
+                   !u1.getRightExpr().equals(u2.getRightExpr())) {
+                   if (u1.getOpcode()==Opcode.NE)
+                       toremove.add(u1);
+                   else
+                       toremove.add(u2);
+                   continue;
+               }
+               
+               /* Compatible operations < & <= */
+               if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
+                   ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
+                   continue;
+
+               /* Compatible operations > & >= */
+               if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
+                   ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
+                   continue;
+               /* Ranges */
+
+               //XXXXXX: TODO
+               /* Equality & Comparisons */
+               //XXXXXX: TODO
+
+               return false; /* They interfere */
+           }
+       }
+       updates.removeAll(toremove);
+       return true;
+    }
+
     public void addBinding(Binding b) {
        bindings.add(b);
        binding.put(b.getVar(),b);
@@ -30,7 +183,6 @@ class UpdateNode {
            return null;
     }
 
-
     public void addUpdate(Updates u) {
        updates.add(u);
     }