f7175fec4f0c54dcc7eb06f8c852a1cf616b22ac
[repair.git] / Repair / RepairCompiler / MCC / IR / UpdateNode.java
1 package MCC.IR;
2 import java.util.*;
3 import MCC.State;
4
5 class UpdateNode {
6     Vector updates;
7     Vector bindings;
8     Hashtable binding;
9     Rule rule;
10     
11
12     public UpdateNode(Rule r) {
13         updates=new Vector();
14         bindings=new Vector();
15         binding=new Hashtable();
16         rule=r;
17     }
18
19     public Rule getRule() {
20         return rule;
21     }
22
23     public String toString() {
24         String st="";
25         for(int i=0;i<bindings.size();i++)
26             st+=bindings.get(i).toString()+"\n";
27         st+="---------------------\n";
28         for(int i=0;i<updates.size();i++)
29             st+=updates.get(i).toString()+"\n";
30         return st;
31     }
32
33     public void addBindings(Vector v) {
34         for (int i=0;i<v.size();i++) {
35             addBinding((Binding)v.get(i));
36         }
37     }
38
39     public boolean checkupdates() {
40         if (!checkconflicts()) /* Do we have conflicting concrete updates */
41             return false;
42         if (computeordering()) /* Ordering exists */
43             return true;
44         return false;
45     }
46
47     private boolean computeordering() {
48         /* Build dependency graph between updates */
49         HashSet graph=new HashSet();
50         Hashtable mapping=new Hashtable();
51         for(int i=0;i<updates.size();i++) {
52             Updates u=(Updates)updates.get(i);
53             GraphNode gn=new GraphNode(String.valueOf(i),u);
54             mapping.put(u, gn);
55             graph.add(gn);
56         }
57         for(int i=0;i<updates.size();i++) {
58             Updates u1=(Updates)updates.get(i);
59             if (u1.isAbstract())
60                 continue;
61             for(int j=0;j<updates.size();j++) {
62                 Updates u2=(Updates)updates.get(j);
63                 if (!u2.isExpr())
64                     continue;
65                 Descriptor d=u1.getDescriptor();
66                 if (u2.getRightExpr().usesDescriptor(d)) {
67                     /* Add edge for dependency */
68                     GraphNode gn1=(GraphNode) mapping.get(u1);
69                     GraphNode gn2=(GraphNode) mapping.get(u2);
70                     GraphNode.Edge e=new GraphNode.Edge("dependency",gn2);
71                     gn1.addEdge(e);
72                 }
73             }
74         }
75
76         if (!GraphNode.DFS.depthFirstSearch(graph))  /* DFS & check for acyclicity */
77             return false;
78
79         TreeSet topologicalsort = new TreeSet(new Comparator() {
80                 public boolean equals(Object obj) { return false; }
81                 public int compare(Object o1, Object o2) {
82                     GraphNode g1 = (GraphNode) o1;
83                     GraphNode g2 = (GraphNode) o2;
84                     return g2.getFinishingTime() - g1.getFinishingTime();
85                 }
86             });
87         topologicalsort.addAll(graph);
88         Vector sortedvector=new Vector();
89         for(Iterator sort=topologicalsort.iterator();sort.hasNext();) {
90             GraphNode gn=(GraphNode)sort.next();
91             sortedvector.add(gn.getOwner());
92         }
93         updates=sortedvector; //replace updates with the sorted array
94         return true;
95     }
96
97     private boolean checkconflicts() {
98         Set toremove=new HashSet();
99         for(int i=0;i<updates.size();i++) {
100             Updates u1=(Updates)updates.get(i);
101             for(int j=0;j<updates.size();j++) {
102                 Updates u2=(Updates)updates.get(j);
103                 if (i==j)
104                     continue;
105                 if (u1.isAbstract()||u2.isAbstract())
106                     continue;  /* Abstract updates are already accounted for by graph */
107                 if (u1.getDescriptor()!=u2.getDescriptor())
108                     continue; /* No interference - different descriptors */
109                 
110                 if ((u1.getOpcode()==Opcode.GT||u1.getOpcode()==Opcode.GE)&&
111                     (u2.getOpcode()==Opcode.GT||u2.getOpcode()==Opcode.GE))
112                     continue; /* Can be satisfied simultaneously */
113
114                 if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
115                     (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
116                     continue;
117                 if ((u1.getOpcode()==u2.getOpcode())&&
118                     u1.isExpr()&&u2.isExpr()&&
119                     u1.getRightExpr().equals(null, u2.getRightExpr())) {
120                     /*We'll remove the second occurence*/
121                     if (i>j)
122                         toremove.add(u1);
123                     else
124                         toremove.add(u2);
125                     continue;
126                 }
127
128                 /* Handle = or != NULL */
129                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
130                      ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
131                     (((u1.isExpr()&&u1.getRightExpr().isNull())&&(!u2.isExpr()||u2.getRightExpr().isNonNull()))
132                      ||((!u1.isExpr()||u1.getRightExpr().isNonNull())&&(u2.isExpr()&&u2.getRightExpr().isNull())))) {
133                     if (u1.getOpcode()==Opcode.NE)
134                         toremove.add(u1);
135                     else
136                         toremove.add(u2);
137                     continue;
138                 }
139
140                 /* Handle = and != to different constants */
141                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
142                     ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
143                     (u1.isExpr()&&u1.getRightExpr() instanceof LiteralExpr)&&
144                     (u2.isExpr()&&u2.getRightExpr() instanceof LiteralExpr)&&
145                     !u1.getRightExpr().equals(u2.getRightExpr())) {
146                     if (u1.getOpcode()==Opcode.NE)
147                         toremove.add(u1);
148                     else
149                         toremove.add(u2);
150                     continue;
151                 }
152                 
153                 /* Compatible operations < & <= */
154                 if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
155                     ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
156                     continue;
157
158                 /* Compatible operations > & >= */
159                 if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
160                     ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
161                     continue;
162                 /* Ranges */
163
164                 //XXXXXX: TODO
165                 /* Equality & Comparisons */
166                 //XXXXXX: TODO
167
168                 return false; /* They interfere */
169             }
170         }
171         updates.removeAll(toremove);
172         return true;
173     }
174
175     public void addBinding(Binding b) {
176         bindings.add(b);
177         binding.put(b.getVar(),b);
178     }
179
180     public int numBindings() {
181         return bindings.size();
182     }
183
184     public Binding getBinding(int i) {
185         return (Binding)bindings.get(i);
186     }
187     
188     public Binding getBinding(VarDescriptor vd) {
189         if (binding.containsKey(vd))
190             return (Binding)binding.get(vd);
191         else
192             return null;
193     }
194
195     public void addUpdate(Updates u) {
196         updates.add(u);
197     }
198
199     public int numUpdates() {
200         return updates.size();
201     }
202     public Updates getUpdate(int i) {
203         return (Updates)updates.get(i);
204     }
205
206     private MultUpdateNode getMultUpdateNode(boolean negate, Descriptor d, RepairGenerator rg) {
207         Termination termination=rg.termination;
208         MultUpdateNode mun=null;
209         GraphNode gn;
210         if (negate)
211             gn=(GraphNode)termination.abstractremove.get(d);
212         else
213             gn=(GraphNode)termination.abstractadd.get(d);
214         TermNode tn=(TermNode)gn.getOwner();
215         for(Iterator edgeit=gn.edges();edgeit.hasNext();) {
216             GraphNode gn2=((GraphNode.Edge) edgeit.next()).getTarget();
217             if (!rg.removed.contains(gn2)) {
218                 TermNode tn2=(TermNode)gn2.getOwner();
219                 if (tn2.getType()==TermNode.UPDATE) {
220                     mun=tn2.getUpdate();
221                     break;
222                 }
223             }
224         }
225         if (mun==null)
226             throw new Error("Can't find update node!");
227         return mun;
228     }
229
230     public void generate_abstract(CodeWriter cr, Updates u, RepairGenerator rg) {
231         State state=rg.state;
232         Expr abstractexpr=u.getLeftExpr();
233         boolean negated=u.negate;
234         Descriptor d=null;
235         Expr left=null;
236         Expr right=null;
237         boolean istuple=false;
238         if (abstractexpr instanceof TupleOfExpr) {
239             TupleOfExpr toe=(TupleOfExpr) abstractexpr;
240             d=toe.relation;
241             left=toe.left;
242             right=toe.right;
243             istuple=true;
244         } else if (abstractexpr instanceof ElementOfExpr) {
245             ElementOfExpr eoe=(ElementOfExpr) abstractexpr;
246             d=eoe.set;
247             left=eoe.element;
248             istuple=false;
249         } else {
250             throw new Error("Unsupported Expr");
251         }
252         MultUpdateNode mun=getMultUpdateNode(negated,d,rg);
253         VarDescriptor leftvar=VarDescriptor.makeNew("leftvar");
254         VarDescriptor rightvar=VarDescriptor.makeNew("rightvar");
255         left.generate(cr, leftvar);
256         if (istuple)
257             right.generate(cr,rightvar);
258
259         if (negated) {
260             if (istuple) {
261                 RelationDescriptor rd=(RelationDescriptor)d;
262                 boolean usageimage=rd.testUsage(RelationDescriptor.IMAGE);
263                 boolean usageinvimage=rd.testUsage(RelationDescriptor.INVIMAGE);
264                 if (usageimage)
265                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hash->remove((int)" + leftvar.getSafeSymbol() + ", (int)" + rightvar.getSafeSymbol() + ");");
266                 if (usageinvimage)
267                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hashinv->remove((int)" + rightvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
268                 
269                 for(int i=0;i<state.vRules.size();i++) {
270                     Rule r=(Rule)state.vRules.get(i);
271                     if (r.getInclusion().getTargetDescriptors().contains(rd)) {
272                         for(int j=0;j<mun.numUpdates();j++) {
273                             UpdateNode un=mun.getUpdate(i);
274                             if (un.getRule()==r) {
275                                 /* Update for rule rule r */
276                                 String name=(String)rg.updatenames.get(un);
277                                 cr.outputline(rg.strepairtable+"->addrelation("+rd.getNum()+","+r.getNum()+","+leftvar.getSafeSymbol()+","+rightvar.getSafeSymbol()+",(int) &"+name+");");
278                             }
279                         }
280                     }
281                 }
282             } else {
283                 SetDescriptor sd=(SetDescriptor) d;
284                 cr.outputline(rg.stmodel+"->"+sd.getJustSafeSymbol() + "_hash->remove((int)" + leftvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
285
286                 for(int i=0;i<state.vRules.size();i++) {
287                     Rule r=(Rule)state.vRules.get(i);
288                     if (r.getInclusion().getTargetDescriptors().contains(sd)) {
289                         for(int j=0;j<mun.numUpdates();j++) {
290                             UpdateNode un=mun.getUpdate(j);
291                             if (un.getRule()==r) {
292                                 /* Update for rule rule r */
293                                 String name=(String)rg.updatenames.get(un);
294                                 cr.outputline(rg.strepairtable+"->addset("+sd.getNum()+","+r.getNum()+","+leftvar.getSafeSymbol()+",(int) &"+name+");");
295                             }
296                         }
297                     }
298                 }
299             }
300         } else {
301             /* Generate update */
302             if (istuple) {
303                 RelationDescriptor rd=(RelationDescriptor) d;
304                 boolean usageimage=rd.testUsage(RelationDescriptor.IMAGE);
305                 boolean usageinvimage=rd.testUsage(RelationDescriptor.INVIMAGE);
306                 if (usageimage)
307                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hash->add((int)" + leftvar.getSafeSymbol() + ", (int)" + rightvar.getSafeSymbol() + ");");
308                 if (usageinvimage)
309                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hashinv->add((int)" + rightvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
310
311                 UpdateNode un=mun.getUpdate(0);
312                 String name=(String)rg.updatenames.get(un);
313                 cr.outputline(name+"(this,"+rg.stmodel+","+rg.strepairtable+","+leftvar.getSafeSymbol()+","+rightvar.getSafeSymbol()+");");
314             } else {
315                 SetDescriptor sd=(SetDescriptor)d;
316                 cr.outputline(rg.stmodel+"->"+sd.getJustSafeSymbol() + "_hash->add((int)" + leftvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
317
318                 UpdateNode un=mun.getUpdate(0);
319                 /* Update for rule rule r */
320                 String name=(String)rg.updatenames.get(un);
321                 cr.outputline(name+"(this,"+rg.stmodel+","+rg.strepairtable+","+leftvar.getSafeSymbol()+");");
322             }
323         }
324         
325     }
326
327     public void generate(CodeWriter cr, boolean removal, boolean modify, String slot0, String slot1, String slot2, RepairGenerator rg) {
328         if (!removal&&!modify)
329             generate_bindings(cr, slot0,slot1);
330         for(int i=0;i<updates.size();i++) {
331             Updates u=(Updates)updates.get(i);
332             VarDescriptor right=VarDescriptor.makeNew("right");
333             if (u.getType()==Updates.ABSTRACT) {
334                 generate_abstract(cr, u, rg);
335                 return;
336             }
337
338             switch(u.getType()) {
339             case Updates.EXPR:
340                 u.getRightExpr().generate(cr,right);
341                 break;
342             case Updates.POSITION:
343             case Updates.ACCESSPATH:
344                 if (u.getRightPos()==0)
345                     cr.outputline("int "+right.getSafeSymbol()+"="+slot0+";");
346                 else if (u.getRightPos()==1)
347                     cr.outputline("int "+right.getSafeSymbol()+"="+slot1+";");
348                 else if (u.getRightPos()==2)
349                     cr.outputline("int "+right.getSafeSymbol()+"="+slot2+";");
350                 else throw new Error("Error w/ Position");
351                 break;
352             default:
353                 throw new Error();
354             }
355
356             if (u.getType()==Updates.ACCESSPATH) {
357                 VarDescriptor newright=VarDescriptor.makeNew("right");
358                 generate_accesspath(cr, right,newright,u);
359                 right=newright;
360             }
361             VarDescriptor left=VarDescriptor.makeNew("left");
362             u.getLeftExpr().generate(cr,left);
363             Opcode op=u.getOpcode();
364             cr.outputline("if (!("+left.getSafeSymbol()+op+right.getSafeSymbol()+"))");
365             cr.startblock();
366
367             if (op==Opcode.GT)
368                 cr.outputline(right.getSafeSymbol()+"++;");
369             else if (op==Opcode.GE)
370                 ;
371             else if (op==Opcode.EQ)
372                 ;
373             else if (op==Opcode.NE)
374                 cr.outputline(right.getSafeSymbol()+"++;");
375             else if (op==Opcode.LT)
376                 cr.outputline(right.getSafeSymbol()+"--;");
377             else if (op==Opcode.LE)
378                 ;
379             else throw new Error();
380             if (u.isGlobal()) {
381                 VarDescriptor vd=((VarExpr)u.getLeftExpr()).getVar();
382                 cr.outputline(vd.getSafeSymbol()+"="+right.getSafeSymbol()+";");
383             } else if (u.isField()) {
384                 /* NEED TO FIX */
385                 Expr subexpr=((DotExpr)u.getLeftExpr()).getExpr();
386                 Expr intindex=((DotExpr)u.getLeftExpr()).getIndex();
387                 VarDescriptor subvd=VarDescriptor.makeNew("subexpr");
388                 VarDescriptor indexvd=VarDescriptor.makeNew("index");
389                 subexpr.generate(cr,subvd);
390                 if (intindex!=null)
391                     intindex.generate(cr,indexvd);
392                 FieldDescriptor fd=(FieldDescriptor)u.getDescriptor();
393                 StructureTypeDescriptor std=(StructureTypeDescriptor)subexpr.getType();
394                 if (fd instanceof ArrayDescriptor) {
395                     fd = ((ArrayDescriptor) fd).getField();
396                 }
397
398                 Expr offsetbits = std.getOffsetExpr(fd);
399                 if (intindex != null) {
400                     Expr basesize = fd.getBaseSizeExpr();
401                     offsetbits = new OpExpr(Opcode.ADD, offsetbits, new OpExpr(Opcode.MULT, basesize, intindex));
402                 }
403                 Expr offsetbytes = new OpExpr(Opcode.SHR, offsetbits,new IntegerLiteralExpr(3));
404                 Expr byteaddress=new OpExpr(Opcode.ADD, offsetbytes, subexpr);
405                 VarDescriptor addr=VarDescriptor.makeNew("byteaddress");
406                 byteaddress.generate(cr,addr);
407
408                 if (fd.getType() instanceof ReservedTypeDescriptor && !fd.getPtr()) {
409                     ReservedTypeDescriptor rtd=(ReservedTypeDescriptor)fd.getType();
410                     if (rtd==ReservedTypeDescriptor.INT) {
411                         cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
412                     } else if (rtd==ReservedTypeDescriptor.SHORT) {
413                         cr.outputline("*((short *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
414                     } else if (rtd==ReservedTypeDescriptor.BYTE) {
415                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
416                     } else if (rtd==ReservedTypeDescriptor.BIT) {
417                         Expr tmp = new OpExpr(Opcode.SHL, offsetbytes, new IntegerLiteralExpr(3));
418                         Expr offset=new OpExpr(Opcode.SUB, offsetbits, tmp);
419                         Expr mask=new OpExpr(Opcode.SHR, new IntegerLiteralExpr(1), offset);
420                         VarDescriptor maskvar=VarDescriptor.makeNew("mask");
421                         mask.generate(cr,maskvar);
422                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")|="+maskvar.getSafeSymbol()+";");
423                         cr.outputline("if (!"+right.getSafeSymbol()+")");
424                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")^="+maskvar.getSafeSymbol()+";");
425                     } else throw new Error();
426                 } else {
427                     /* Pointer */
428                     cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
429                 }
430             }
431             cr.endblock();
432         }
433     }
434
435
436     private void generate_accesspath(CodeWriter cr, VarDescriptor right, VarDescriptor newright, Updates u) {
437         Vector dotvector=new Vector();
438         Expr ptr=u.getRightExpr();
439         VarExpr rightve=new VarExpr(right);
440         right.td=ReservedTypeDescriptor.INT;
441
442         while(true) {
443             /* Does something other than a dereference? */
444             dotvector.add(ptr);
445             if (ptr instanceof DotExpr)
446                 ptr=((DotExpr)ptr).left;
447             else if (ptr instanceof CastExpr)
448                 ptr=((CastExpr)ptr).getExpr();
449             if (ptr instanceof VarExpr) {
450                 /* Finished constructing vector */
451                 break;
452             }
453         }
454         ArrayAnalysis.AccessPath ap=u.getAccessPath();
455         VarDescriptor init=VarDescriptor.makeNew("init");
456         if (ap.isSet()) {
457             cr.outputline("int "+init.getSafeSymbol()+"="+ap.getSet().getSafeSymbol()+"_hash->firstkey();");
458             init.td=ap.getSet().getType();
459         } else {
460             init=ap.getVar();
461         }
462         Expr newexpr=new VarExpr(init);
463         int apindex=0;
464         for(int i=dotvector.size()-1;i>=0;i--) {
465             Expr e=(Expr)dotvector.get(i);
466             if (e instanceof CastExpr) {
467                 newexpr=new CastExpr(((CastExpr)e).getType(),newexpr);
468             } else if (e instanceof DotExpr) {
469                 DotExpr de=(DotExpr)e;
470                 if (de.getField() instanceof ArrayDescriptor) {
471                     DotExpr de2=new DotExpr(newexpr,de.field,new IntegerLiteralExpr(0));
472                     de2.fd=de.fd;
473                     de2.fieldtype=de.fieldtype;
474                     OpExpr offset=new OpExpr(Opcode.SUB,rightve,de2);
475                     OpExpr index=new OpExpr(Opcode.DIV,offset,de.fieldtype.getSizeExpr());
476                     if (u.getRightPos()==apindex) {
477                         index.generate(cr,newright);
478                         return;
479                     } else {
480                         DotExpr de3=new DotExpr(newexpr,de.field,index);
481                         de3.fd=de.fd;
482                         de3.fieldtype=de.fieldtype;
483                         newexpr=de3;
484                     }
485                 } else {
486                     DotExpr de2=new DotExpr(newexpr,de.field,null);
487                     de2.fd=de.fd;
488                     de2.fieldtype=de.fieldtype;
489                     newexpr=de2;
490                 }
491                 apindex++;
492             } else throw new Error();
493         }
494         throw new Error();
495     }
496
497     private void generate_bindings(CodeWriter cr, String slot0, String slot1) {
498         for(int i=0;i<bindings.size();i++) {
499             Binding b=(Binding)bindings.get(i);
500
501             if (b.getType()==Binding.SEARCH) {
502                 VarDescriptor vd=b.getVar();
503                 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+b.getSet().getSafeSymbol()+"->firstkey();");
504             } else if (b.getType()==Binding.CREATE) {
505                 throw new Error("Creation not supported");
506                 //              source.generateSourceAlloc(cr,vd,b.getSet());
507             } else {
508                 VarDescriptor vd=b.getVar();
509                 switch(b.getPosition()) {
510                 case 0:
511                     cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot0+";");
512                     break;
513                 case 1:
514                     cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot1+";");
515                     break;
516                 default:
517                     throw new Error("Slot >1 doesn't exist.");
518                 }
519             }
520         }
521     }
522 }