Started adding analysis for modifyrelation nodes.
[repair.git] / Repair / RepairCompiler / MCC / IR / ConcreteInterferes.java
1 package MCC.IR;
2 import java.util.*;
3
4 class ConcreteInterferes {
5
6     static public boolean interferesinclusion(UpdateNode un, Updates update, Rule r) {
7         Descriptor updated_des=update.getDescriptor();
8         Inclusion inclusion=r.getInclusion();
9         if (inclusion instanceof RelationInclusion) {
10             RelationInclusion ri=(RelationInclusion)inclusion;
11             if (ri.getLeftExpr().usesDescriptor(updated_des)&&interferesinclusion(un,update,r,ri.getLeftExpr()))
12                 return true;
13             if (ri.getRightExpr().usesDescriptor(updated_des)&&interferesinclusion(un,update,r,ri.getRightExpr()))
14                 return true;
15         } else if (inclusion instanceof SetInclusion) {
16             SetInclusion si=(SetInclusion)inclusion;
17             if (si.getExpr().usesDescriptor(updated_des)&&interferesinclusion(un,update,r,si.getExpr()))
18                 return true;
19         } else throw new Error();
20         return false;
21     }
22
23     static public boolean interferesinclusion(UpdateNode un, Updates update, Rule r, Expr inclusionexpr) {
24         Descriptor updated_des=update.getDescriptor();
25         if (updated_des instanceof FieldDescriptor) {
26             /* Build variable correspondance */
27             HashSet set=new HashSet();
28             inclusionexpr.findmatch(updated_des,set);
29             
30             for(Iterator matchit=set.iterator();matchit.hasNext();) {
31                 DotExpr dotexpr=(DotExpr)matchit.next();
32                 DotExpr updateexpr=(DotExpr)update.getLeftExpr();
33                 while(true) {
34                     if (dotexpr.getField()!=updateexpr.getField())
35                         return true;
36                     Expr de=dotexpr.getExpr();
37                     Expr ue=updateexpr.getExpr();
38                     if ((de instanceof DotExpr)&&(ue instanceof DotExpr)) {
39                         dotexpr=(DotExpr)de;
40                         updateexpr=(DotExpr)ue;
41                     } else if ((de instanceof VarExpr)&&(ue instanceof VarExpr)) {
42                         VarDescriptor dvd=((VarExpr)de).getVar();
43                         VarDescriptor uvd=((VarExpr)ue).getVar();
44                         if (interferesinclusion(un,r,dvd,uvd))
45                             return true;
46                         else
47                             break;
48                     } else
49                         return true;
50                 }
51             }
52         } else if (updated_des instanceof VarDescriptor) {
53             /* We have a VarDescriptor - no correspondance necessary */
54             VarDescriptor vd=(VarDescriptor)updated_des;
55             if (interferesinclusion(un,r,vd,vd))
56                 return true;
57         } else throw new Error();
58         return false;
59     }
60
61     static public boolean interferesinclusion(UpdateNode un, Rule r, VarDescriptor dvd, VarDescriptor uvd) {
62         DNFRule negrule=r.getDNFNegGuardExpr();
63         HashMap remap=new HashMap();
64         remap.put(dvd,uvd);
65
66         for(int i=0;i<negrule.size();i++) {
67             RuleConjunction rconj=negrule.get(i);
68             boolean good=true;
69             for(int j=0;j<rconj.size();j++) {
70                 DNFExpr dexpr=rconj.get(j);
71                 if (dexpr.getExpr() instanceof OpExpr) {
72                     OpExpr expr=(OpExpr)dexpr.getExpr();
73                     Expr lexpr=expr.getLeftExpr();
74                     Expr rexpr=expr.getRightExpr();
75
76                     boolean varok=true;
77                     Set vars=rexpr.freeVars();
78                     if (vars!=null) 
79                         for(Iterator it=vars.iterator();it.hasNext();) {
80                             VarDescriptor vd=(VarDescriptor) it.next();
81                             if (!vd.isGlobal()) {
82                                 /* VarDescriptor isn't a global */
83                                 if (dvd!=vd) {
84                                     varok=false;
85                                     break;
86                                 }
87                             }
88                         }
89                     
90                     if (!varok)
91                         continue;
92
93
94
95                     Opcode op=expr.getOpcode();
96
97                     if (dexpr.getNegation()) {
98                         /* remove negation through opcode translation */
99                         if (op==Opcode.GT)
100                             op=Opcode.LE;
101                         else if (op==Opcode.GE)
102                             op=Opcode.LT;
103                         else if (op==Opcode.EQ)
104                             op=Opcode.NE;
105                         else if (op==Opcode.NE)
106                             op=Opcode.EQ;
107                         else if (op==Opcode.LT)
108                             op=Opcode.GE;
109                         else if (op==Opcode.LE)
110                             op=Opcode.GT;
111                     }
112                     boolean match=false;
113                     for(int k=0;k<un.numUpdates();k++) {
114                         Updates update=un.getUpdate(k);
115                         if(update.isExpr()) {
116                             Set uvars=update.getRightExpr().freeVars();
117                             boolean freevarok=true;
118                             if (uvars!=null)
119                             for(Iterator it=uvars.iterator();it.hasNext();) {
120                                 VarDescriptor vd=(VarDescriptor) it.next();
121                                 if (!vd.isGlobal()) {
122                                     /* VarDescriptor isn't a global */
123                                     if (uvd!=vd) {
124                                         freevarok=false;
125                                         break;
126                                     }
127                                 }
128                             }
129                             if (!freevarok)
130                                 continue;
131
132                             Opcode op2=update.getOpcode();
133                             if ((op2==op)||
134                                 ((op2==Opcode.GT)&&(op==Opcode.GE))||
135                                 ((op2==Opcode.LT)&&(op==Opcode.LE))||
136                                 ((op2==Opcode.EQ)&&((op==Opcode.GE)||(op==Opcode.LE)))) {
137                                 /* Operations match*/
138                                 if (lexpr.equals(remap,update.getLeftExpr())&&
139                                     rexpr.equals(remap,update.getRightExpr())) {
140                                     match=true;
141                                     break;
142                                 }                                   
143                             }
144                         } 
145                     }
146                     if (!match) {
147                         good=false;
148                         break;
149                     }
150                 } else {
151                     /* TODO: Check to see if there is an abstract repair */
152                     good=false;
153                     break; /* try next conjunction */
154                 }
155             }
156             if (good)
157                 return false;
158         }
159         return true;
160     }
161
162     static public boolean interferes(MultUpdateNode mun, Rule r, boolean satisfy) {
163         if (!initialinterferes(mun,r,satisfy)) /* Can't falsify a rule adding something to a set on an initial addition*/
164             return false;
165         for(int i=0;i<mun.numUpdates();i++) {
166             UpdateNode un=mun.getUpdate(i);
167             for (int j=0;j<un.numUpdates();j++) {
168                 Updates update=un.getUpdate(j);
169                 
170                 DNFRule drule=r.getDNFGuardExpr();
171                 if (satisfy)
172                     drule=r.getDNFNegGuardExpr();
173
174
175                 if (!update.isAbstract()) {
176                     Descriptor updated_des=update.getDescriptor();
177                     assert updated_des!=null;
178                     /* Update is local to this rule, and the effect is intentional */
179                     /* If we're adding something, a side effect could be to falsify some other binding
180                        If we're removing something, there is no similar side effect */
181                     if ((un.getRule()==r)&&
182                         (((mun.op==MultUpdateNode.ADD)&&satisfy)||(mun.op==MultUpdateNode.REMOVE))&&
183                         (r.numQuantifiers()==1)&&
184                         (r.getQuantifier(0) instanceof SetQuantifier)&&
185                         update.isField()&&
186                         (((DotExpr)update.getLeftExpr()).getExpr() instanceof VarExpr)&&
187                         ((SetQuantifier)r.getQuantifier(0)).getVar()==((VarExpr)((DotExpr)update.getLeftExpr()).getExpr()).getVar())
188                         continue;
189                     if ((un.getRule()==r)&&
190                         (((mun.op==MultUpdateNode.ADD)&&satisfy)||(mun.op==MultUpdateNode.REMOVE))&&
191                         (r.numQuantifiers()==0))
192                         continue;
193
194
195                     if (r.getInclusion().usesDescriptor(updated_des)) {
196                         if (satisfy) {
197                             if (interferesinclusion(un, update, r))
198                             return true;
199                         } else
200                             return true; /* Interferes with inclusion condition */
201                     }
202                     
203                     for(int k=0;k<drule.size();k++) {
204                         RuleConjunction rconj=drule.get(k);
205                         for(int l=0;l<rconj.size();l++) {
206
207
208                             DNFExpr dexpr=rconj.get(l);
209                             /* See if update interferes w/ dexpr */
210                             if (interferes(un,update, r,dexpr))
211                                 return true;
212                         }
213                     }
214                 }
215             }
216         }
217         return false;
218     }
219
220     static private boolean initialinterferes(MultUpdateNode mun, Rule r, boolean satisfy) {
221         AbstractRepair ar=mun.getRepair();
222         if (satisfy)
223             return true;
224         if (ar==null)
225             return true;
226         if (ar.getType()!=AbstractRepair.ADDTOSET)
227             return true;
228         //      if (mun.op!=MultUpdateNode.ADD)  (Redundant)
229         //    return true;
230         if (!r.getInclusion().getTargetDescriptors().contains(ar.getDescriptor()))
231             return true;
232         boolean negated=ar.getPredicate().isNegated();
233         Predicate p=ar.getPredicate().getPredicate();
234         if (!(p instanceof ExprPredicate))
235             return true;
236         ExprPredicate ep=(ExprPredicate)p;
237         if (ep.getType()!=ExprPredicate.SIZE)
238             return true;
239         if ((ep.getOp()==Opcode.EQ)&&(ep.leftsize()==1)&&!negated)
240             return false;
241         if ((ep.getOp()==Opcode.NE)&&(ep.leftsize()==1)&&negated)
242             return false;
243
244         if ((ep.getOp()==Opcode.NE)&&(ep.leftsize()==0)&&!negated)
245             return false;
246         if ((ep.getOp()==Opcode.EQ)&&(ep.leftsize()==0)&&negated)
247             return false;
248
249
250
251         if ((ep.getOp()==Opcode.GT)&&(ep.leftsize()==0)&&!negated)
252             return false;
253         if ((ep.getOp()==Opcode.LE)&&(ep.leftsize()==0)&&negated)
254             return false;
255
256         if ((ep.getOp()==Opcode.GE)&&(ep.leftsize()==1)&&!negated)
257             return false;
258         if ((ep.getOp()==Opcode.LT)&&(ep.leftsize()==1)&&negated)
259             return false;
260         
261         return true;
262
263         
264     }
265
266     static private boolean interferes(UpdateNode un,Updates update, Rule r,DNFExpr dexpr) {
267         Descriptor descriptor=update.getDescriptor();
268         if (!dexpr.getExpr().usesDescriptor(descriptor))
269             return false;
270             
271         /* We need to pair the variables */
272         if (update.isExpr()) {
273             Set vars=update.getRightExpr().freeVars();
274             Opcode op1=update.getOpcode();
275             Expr lexpr1=update.getLeftExpr();
276             Expr rexpr1=update.getRightExpr();
277             boolean good=true;
278             if (vars!=null)
279                 for(Iterator it=vars.iterator();it.hasNext();) {
280                     VarDescriptor vd=(VarDescriptor) it.next();
281                     if (!vd.isGlobal()) {
282                         /* VarDescriptor isn't a global */
283                         if (update.getVar()!=vd) {
284                             good=false;
285                             break;
286                         }
287                     }
288                 }
289             if (good&&(dexpr.getExpr() instanceof OpExpr)) {
290                 OpExpr expr=(OpExpr)dexpr.getExpr();
291                 Expr lexpr2=expr.getLeftExpr();
292                 Expr rexpr2=expr.getRightExpr();
293                 Opcode op2=expr.getOpcode();
294                 if (dexpr.getNegation()) {
295                     /* remove negation through opcode translation */
296                     if (op2==Opcode.GT)
297                         op2=Opcode.LE;
298                     else if (op2==Opcode.GE)
299                         op2=Opcode.LT;
300                     else if (op2==Opcode.EQ)
301                         op2=Opcode.NE;
302                     else if (op2==Opcode.NE)
303                         op2=Opcode.EQ;
304                     else if (op2==Opcode.LT)
305                         op2=Opcode.GE;
306                     else if (op2==Opcode.LE)
307                         op2=Opcode.GT;
308                 }
309                 good=true;
310                 vars=rexpr2.freeVars();
311                 VarDescriptor leftdescriptor=null;
312                 if (lexpr2 instanceof VarExpr)
313                     leftdescriptor=((VarExpr)lexpr2).getVar();
314                 else if (lexpr2 instanceof DotExpr) {
315                     Expr e=lexpr2;
316                     for(;e instanceof DotExpr;e=((DotExpr)e).getExpr()) ;
317                     leftdescriptor=((VarExpr)e).getVar();
318                 } else throw new Error("Bad Expr");
319                 
320                 if (vars!=null)
321                     for(Iterator it=vars.iterator();it.hasNext();) {
322                         VarDescriptor vd=(VarDescriptor) it.next();
323                         if (!vd.isGlobal()) {
324                             /* VarDescriptor isn't a global */
325                             if (leftdescriptor!=vd) {
326                                 good=false;
327                                 break;
328                             }
329                         }
330                     }
331                 if (good) {
332                     HashMap remap=new HashMap();
333                     remap.put(update.getVar(),leftdescriptor);
334                     if ((op1==op2)&&
335                         lexpr1.equals(remap,lexpr2)&&
336                         rexpr1.equals(remap,rexpr2))
337                         return false;
338                 }
339             }
340         }
341         return true;
342     }
343 }