Repair/RepairCompiler/MCC/IR/UpdateNode.java

   1 package MCC.IR;
   2 import java.util.*;
   3
   4 class UpdateNode {
   5     Vector updates;
   6     Vector bindings;
   7     Hashtable binding;
   8
   9     public UpdateNode() {
  10         updates=new Vector();
  11         bindings=new Vector();
  12         binding=new Hashtable();
  13     }
  14
  15     public String toString() {
  16         String st="";
  17         for(int i=0;i<bindings.size();i++)
  18             st+=bindings.get(i).toString()+"\n";
  19         st+="---------------------\n";
  20         for(int i=0;i<updates.size();i++)
  21             st+=updates.get(i).toString()+"\n";
  22         return st;
  23     }
  24
  25     public void addBindings(Vector v) {
  26         for (int i=0;i<v.size();i++) {
  27             addBinding((Binding)v.get(i));
  28         }
  29     }
  30
  31     public boolean checkupdates() {
  32         if (!checkconflicts()) /* Do we have conflicting concrete updates */
  33             return false;
  34         if (computeordering()) /* Ordering exists */
  35             return true;
  36         return false;
  37     }
  38
  39     private boolean computeordering() {
  40         /* Build dependency graph between updates */
  41         HashSet graph=new HashSet();
  42         Hashtable mapping=new Hashtable();
  43         for(int i=0;i<updates.size();i++) {
  44             Updates u=(Updates)updates.get(i);
  45             GraphNode gn=new GraphNode(String.valueOf(i),u);
  46             mapping.put(u, gn);
  47             graph.add(gn);
  48         }
  49         for(int i=0;i<updates.size();i++) {
  50             Updates u1=(Updates)updates.get(i);
  51             if (u1.isAbstract())
  52                 continue;
  53             for(int j=0;j<updates.size();j++) {
  54                 Updates u2=(Updates)updates.get(j);
  55                 if (!u2.isExpr())
  56                     continue;
  57                 Descriptor d=u1.getDescriptor();
  58                 if (u2.getRightExpr().usesDescriptor(d)) {
  59                     /* Add edge for dependency */
  60                     GraphNode gn1=(GraphNode) mapping.get(u1);
  61                     GraphNode gn2=(GraphNode) mapping.get(u2);
  62                     GraphNode.Edge e=new GraphNode.Edge("dependency",gn2);
  63                     gn1.addEdge(e);
  64                 }
  65             }
  66         }
  67
  68         if (!GraphNode.DFS.depthFirstSearch(graph))  /* DFS & check for acyclicity */
  69             return false;
  70
  71         TreeSet topologicalsort = new TreeSet(new Comparator() {
  72                 public boolean equals(Object obj) { return false; }
  73                 public int compare(Object o1, Object o2) {
  74                     GraphNode g1 = (GraphNode) o1;
  75                     GraphNode g2 = (GraphNode) o2;
  76                     return g2.getFinishingTime() - g1.getFinishingTime();
  77                 }
  78             });
  79         topologicalsort.addAll(graph);
  80         Vector sortedvector=new Vector();
  81         for(Iterator sort=topologicalsort.iterator();sort.hasNext();) {
  82             GraphNode gn=(GraphNode)sort.next();
  83             sortedvector.add(gn.getOwner());
  84         }
  85         updates=sortedvector; //replace updates with the sorted array
  86         return true;
  87     }
  88
  89     private boolean checkconflicts() {
  90         Set toremove=new HashSet();
  91         for(int i=0;i<updates.size();i++) {
  92             Updates u1=(Updates)updates.get(i);
  93             for(int j=0;j<updates.size();j++) {
  94                 Updates u2=(Updates)updates.get(j);
  95                 if (i==j)
  96                     continue;
  97                 if (u1.isAbstract()||u2.isAbstract())
  98                     continue;  /* Abstract updates are already accounted for by graph */
  99                 if (u1.getDescriptor()!=u2.getDescriptor())
 100                     continue; /* No interference - different descriptors */
 101
 102                 if ((u1.getOpcode()==Opcode.GT||u1.getOpcode()==Opcode.GE)&&
 103                     (u2.getOpcode()==Opcode.GT||u2.getOpcode()==Opcode.GE))
 104                     continue; /* Can be satisfied simultaneously */
 105
 106                 if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
 107                     (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
 108                     continue;
 109                 if ((u1.getOpcode()==u2.getOpcode())&&
 110                     u1.isExpr()&&u2.isExpr()&&
 111                     u1.getRightExpr().equals(null, u2.getRightExpr())) {
 112                     /*We'll remove the second occurence*/
 113                     if (i>j)
 114                         toremove.add(u1);
 115                     else
 116                         toremove.add(u2);
 117                     continue;
 118                 }
 119
 120                 /* Handle = or != NULL */
 121                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
 122                      ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
 123                     (((u1.isExpr()&&u1.getRightExpr().isNull())&&(!u2.isExpr()||u2.getRightExpr().isNonNull()))
 124                      ||((!u1.isExpr()||u1.getRightExpr().isNonNull())&&(u2.isExpr()&&u2.getRightExpr().isNull())))) {
 125                     if (u1.getOpcode()==Opcode.NE)
 126                         toremove.add(u1);
 127                     else
 128                         toremove.add(u2);
 129                     continue;
 130                 }
 131
 132                 /* Handle = and != to different constants */
 133                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
 134                     ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
 135                     (u1.isExpr()&&u1.getRightExpr() instanceof LiteralExpr)&&
 136                     (u2.isExpr()&&u2.getRightExpr() instanceof LiteralExpr)&&
 137                     !u1.getRightExpr().equals(u2.getRightExpr())) {
 138                     if (u1.getOpcode()==Opcode.NE)
 139                         toremove.add(u1);
 140                     else
 141                         toremove.add(u2);
 142                     continue;
 143                 }
 144
 145                 /* Compatible operations < & <= */
 146                 if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
 147                     ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
 148                     continue;
 149
 150                 /* Compatible operations > & >= */
 151                 if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
 152                     ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
 153                     continue;
 154                 /* Ranges */
 155
 156                 //XXXXXX: TODO
 157                 /* Equality & Comparisons */
 158                 //XXXXXX: TODO
 159
 160                 return false; /* They interfere */
 161             }
 162         }
 163         updates.removeAll(toremove);
 164         return true;
 165     }
 166
 167     public void addBinding(Binding b) {
 168         bindings.add(b);
 169         binding.put(b.getVar(),b);
 170     }
 171
 172     public Binding getBinding(VarDescriptor vd) {
 173         if (binding.containsKey(vd))
 174             return (Binding)binding.get(vd);
 175         else
 176             return null;
 177     }
 178
 179     public void addUpdate(Updates u) {
 180         updates.add(u);
 181     }
 182
 183     public int numUpdates() {
 184         return updates.size();
 185     }
 186     public Updates getUpdate(int i) {
 187         return (Updates)updates.get(i);
 188     }
 189 }