12 public UpdateNode(Rule r) {
14 bindings=new Vector();
15 binding=new Hashtable();
19 public Rule getRule() {
23 public String toString() {
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";
33 public void addBindings(Vector v) {
34 for (int i=0;i<v.size();i++) {
35 addBinding((Binding)v.get(i));
39 public boolean checkupdates() {
40 if (!checkconflicts()) /* Do we have conflicting concrete updates */
42 if (computeordering()) /* Ordering exists */
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);
57 for(int i=0;i<updates.size();i++) {
58 Updates u1=(Updates)updates.get(i);
61 for(int j=0;j<updates.size();j++) {
62 Updates u2=(Updates)updates.get(j);
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);
76 if (!GraphNode.DFS.depthFirstSearch(graph)) /* DFS & check for acyclicity */
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();
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());
93 updates=sortedvector; //replace updates with the sorted array
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);
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 */
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 */
114 if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
115 (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
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*/
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)
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)
153 /* Compatible operations < & <= */
154 if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
155 ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
158 /* Compatible operations > & >= */
159 if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
160 ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
165 /* Equality & Comparisons */
168 return false; /* They interfere */
171 updates.removeAll(toremove);
175 public void addBinding(Binding b) {
177 binding.put(b.getVar(),b);
180 public int numBindings() {
181 return bindings.size();
184 public Binding getBinding(int i) {
185 return (Binding)bindings.get(i);
188 public Binding getBinding(VarDescriptor vd) {
189 if (binding.containsKey(vd))
190 return (Binding)binding.get(vd);
195 public void addUpdate(Updates u) {
199 public int numUpdates() {
200 return updates.size();
202 public Updates getUpdate(int i) {
203 return (Updates)updates.get(i);
206 private MultUpdateNode getMultUpdateNode(boolean negate, Descriptor d, RepairGenerator rg) {
207 Termination termination=rg.termination;
208 MultUpdateNode mun=null;
211 gn=(GraphNode)termination.abstractremove.get(d);
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) {
226 throw new Error("Can't find update node!");
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;
237 boolean istuple=false;
238 if (abstractexpr instanceof TupleOfExpr) {
239 TupleOfExpr toe=(TupleOfExpr) abstractexpr;
244 } else if (abstractexpr instanceof ElementOfExpr) {
245 ElementOfExpr eoe=(ElementOfExpr) abstractexpr;
250 throw new Error("Unsupported Expr");
252 MultUpdateNode mun=getMultUpdateNode(negated,d,rg);
253 VarDescriptor leftvar=VarDescriptor.makeNew("leftvar");
254 VarDescriptor rightvar=VarDescriptor.makeNew("rightvar");
255 left.generate(cr, leftvar);
257 right.generate(cr,rightvar);
261 RelationDescriptor rd=(RelationDescriptor)d;
262 boolean usageimage=rd.testUsage(RelationDescriptor.IMAGE);
263 boolean usageinvimage=rd.testUsage(RelationDescriptor.INVIMAGE);
265 cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hash->remove((int)" + leftvar.getSafeSymbol() + ", (int)" + rightvar.getSafeSymbol() + ");");
267 cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hashinv->remove((int)" + rightvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
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+");");
283 SetDescriptor sd=(SetDescriptor) d;
284 cr.outputline(rg.stmodel+"->"+sd.getJustSafeSymbol() + "_hash->remove((int)" + leftvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
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+");");
301 /* Generate update */
303 RelationDescriptor rd=(RelationDescriptor) d;
304 boolean usageimage=rd.testUsage(RelationDescriptor.IMAGE);
305 boolean usageinvimage=rd.testUsage(RelationDescriptor.INVIMAGE);
307 cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hash->add((int)" + leftvar.getSafeSymbol() + ", (int)" + rightvar.getSafeSymbol() + ");");
309 cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hashinv->add((int)" + rightvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
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()+");");
315 SetDescriptor sd=(SetDescriptor)d;
316 cr.outputline(rg.stmodel+"->"+sd.getJustSafeSymbol() + "_hash->add((int)" + leftvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
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()+");");
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);
338 switch(u.getType()) {
340 u.getRightExpr().generate(cr,right);
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");
356 if (u.getType()==Updates.ACCESSPATH) {
357 VarDescriptor newright=VarDescriptor.makeNew("right");
358 generate_accesspath(cr, right,newright,u);
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()+"))");
368 cr.outputline(right.getSafeSymbol()+"++;");
369 else if (op==Opcode.GE)
371 else if (op==Opcode.EQ)
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)
379 else throw new Error();
381 VarDescriptor vd=((VarExpr)u.getLeftExpr()).getVar();
382 cr.outputline(vd.getSafeSymbol()+"="+right.getSafeSymbol()+";");
383 } else if (u.isField()) {
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);
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();
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));
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);
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();
428 cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
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;
443 /* Does something other than a dereference? */
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 */
454 ArrayAnalysis.AccessPath ap=u.getAccessPath();
455 VarDescriptor init=VarDescriptor.makeNew("init");
457 cr.outputline("int "+init.getSafeSymbol()+"="+ap.getSet().getSafeSymbol()+"_hash->firstkey();");
458 init.td=ap.getSet().getType();
462 Expr newexpr=new VarExpr(init);
464 for(int i=dotvector.size()-1;i>=0;i--) {
465 Expr e=(Expr)dotvector.get(i);
466 if (e instanceof CastExpr) {
468 newexpr=new CastExpr(((CastExpr)e).getType(),newexpr);
469 } else if (e instanceof DotExpr) {
470 DotExpr de=(DotExpr)e;
471 if (de.getField() instanceof ArrayDescriptor) {
472 DotExpr de2=new DotExpr(newexpr,de.field,new IntegerLiteralExpr(0));
474 de2.fieldtype=de.fieldtype;
476 OpExpr offset=new OpExpr(Opcode.SUB,rightve,de2);
477 OpExpr index=new OpExpr(Opcode.DIV,offset,de.fieldtype.getSizeExpr());
478 if (u.getRightPos()==apindex) {
479 index.generate(cr,newright);
482 DotExpr de3=new DotExpr(newexpr,de.field,index);
485 de3.fieldtype=de.fieldtype;
489 DotExpr de2=new DotExpr(newexpr,de.field,null);
491 de2.fieldtype=de.fieldtype;
496 } else throw new Error();
501 private void generate_bindings(CodeWriter cr, String slot0, String slot1) {
502 for(int i=0;i<bindings.size();i++) {
503 Binding b=(Binding)bindings.get(i);
505 if (b.getType()==Binding.SEARCH) {
506 VarDescriptor vd=b.getVar();
507 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+b.getSet().getSafeSymbol()+"_hash->firstkey();");
508 } else if (b.getType()==Binding.CREATE) {
509 throw new Error("Creation not supported");
510 // source.generateSourceAlloc(cr,vd,b.getSet());
512 VarDescriptor vd=b.getVar();
513 switch(b.getPosition()) {
515 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot0+";");
518 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot1+";");
521 throw new Error("Slot >1 doesn't exist.");