projects / repair.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Added minimum size analysis.
[repair.git] / Repair / RepairCompiler / MCC / IR / Termination.java
diff --git a/Repair/RepairCompiler/MCC/IR/Termination.java b/Repair/RepairCompiler/MCC/IR/Termination.java
index 764453f239535d979d072aa28fea54d0c94d9060..0d074f6a3146bdfeeb19e50c5852878ff4198d2d 100755 (executable)
--- a/Repair/RepairCompiler/MCC/IR/Termination.java
+++ b/Repair/RepairCompiler/MCC/IR/Termination.java
@@ -31,6 +31,12 @@ public class Termination {
     ExactSize exactsize;
     ArrayAnalysis arrayanalysis;
     Sources sources;
+    static String conjoption="style=bold";
+    static String absrepoption="shape=box,color=blue,style=bold";
+    static String updateoption="shape=box,color=red,style=bold";
+    static String scopeoption="color=brown";
+    static String conseqoption="style=bold,color=green";
+    static String compoption="shape=box,color=purple,style=bold";
 
     public Termination(State state) {
        this.state=state;
@@ -67,19 +73,20 @@ public class Termination {
        generateconjunctionnodes();
        constraintdependence=new ConstraintDependence(state,this);
 
-        debugmsg("Generating scope nodes");
+        debugmsg("*****Generating scope nodes*****");
        generatescopenodes();
-        debugmsg("Generating repair nodes");
+        debugmsg("*****Generating repair nodes*****");
        generaterepairnodes();
-        debugmsg("Generating data structure nodes");
+        debugmsg("*****Generating data structure nodes*****");
        generatedatastructureupdatenodes();
-        debugmsg("Generating compensation nodes");
-       generatecompensationnodes();
-        debugmsg("Generating abstract edges");
+        debugmsg("*****Generating compensation nodes*****");
+       if (!Compiler.OMITCOMP)
+           generatecompensationnodes();
+        debugmsg("*****Generating abstract edges*****");
        generateabstractedges();
-        debugmsg("Generating scope edges");
+        debugmsg("*****Generating scope edges*****");
        generatescopeedges();
-        debugmsg("Generating update edges");
+        debugmsg("*****Generating update edges*****");
        generateupdateedges();
 
 
@@ -170,6 +177,7 @@ public class Termination {
                GraphNode gn=new GraphNode("Conj"+i+"A"+j,
                                           "Conj ("+i+","+j+") "+dnf.get(j).name()
                                           ,tn);
+               gn.setOption(conjoption);
                conjunctions.add(gn);
                if (!conjunctionmap.containsKey(c))
                    conjunctionmap.put(c,new HashSet());
@@ -190,6 +198,7 @@ public class Termination {
                    GraphNode gn=new GraphNode("Conj"+i+"AQ"+j,
                                               "Conj ("+i+","+j+") "+dconst.get(0).name()
                                               ,tn);
+                   gn.setOption(conjoption);
                    conjunctions.add(gn);
                    if (!conjunctionmap.containsKey(c))
                        conjunctionmap.put(c,new HashSet());
@@ -207,6 +216,7 @@ public class Termination {
                    GraphNode gn=new GraphNode("Conj"+i+"AQ"+j,
                                               "Conj ("+i+","+j+") "+dconst.get(0).name()
                                               ,tn);
+                   gn.setOption(conjoption);
                    conjunctions.add(gn);
                    if (!conjunctionmap.containsKey(c))
                        conjunctionmap.put(c,new HashSet());
@@ -233,22 +243,22 @@ public class Termination {
                            TupleOfExpr toe=(TupleOfExpr)e;
                            if (negated) {
                                GraphNode agn=(GraphNode)abstractremove.get(toe.relation);
-                               GraphNode.Edge edge=new GraphNode.Edge("requires",agn);
+                               GraphNode.Edge edge=new GraphNode.Edge("requirestupleremove",agn);
                                gn.addEdge(edge);
                            } else {
                                GraphNode agn=(GraphNode)abstractadd.get(toe.relation);
-                               GraphNode.Edge edge=new GraphNode.Edge("requires",agn);
+                               GraphNode.Edge edge=new GraphNode.Edge("requirestupleadd",agn);
                                gn.addEdge(edge);
                            }
                        } else if (e instanceof ElementOfExpr) {
                            ElementOfExpr eoe=(ElementOfExpr)e;
                            if (negated) {
                                GraphNode agn=(GraphNode)abstractremove.get(eoe.set);
-                               GraphNode.Edge edge=new GraphNode.Edge("requires",agn);
+                               GraphNode.Edge edge=new GraphNode.Edge("requireselementremove",agn);
                                gn.addEdge(edge);
                            } else {
                                GraphNode agn=(GraphNode)abstractadd.get(eoe.set);
-                               GraphNode.Edge edge=new GraphNode.Edge("requires",agn);
+                               GraphNode.Edge edge=new GraphNode.Edge("requireselementadd",agn);
                                gn.addEdge(edge);
                            }
                        } else throw new Error("Unrecognized Abstract Update");
@@ -258,14 +268,20 @@ public class Termination {
            /* Cycle through the rules to look for possible conflicts */
            for(int i=0;i<state.vRules.size();i++) {
                Rule r=(Rule) state.vRules.get(i);
+                if (Compiler.DEBUGGRAPH) {
+                    System.out.println(gn.getLabel()+"--->"+((GraphNode)scopesatisfy.get(r)).getLabel());
+                }
                if (concreteinterferes.interferes(mun,r,true)) {
                    GraphNode scopenode=(GraphNode)scopesatisfy.get(r);
-                   GraphNode.Edge e=new GraphNode.Edge("interferes",scopenode);
+                   GraphNode.Edge e=new GraphNode.Edge("satisfyscopeinterferes",scopenode);
                    gn.addEdge(e);
                }
+                if (Compiler.DEBUGGRAPH) {
+                    System.out.println(gn.getLabel()+"--->"+((GraphNode)scopefalsify.get(r)).getLabel());
+                }
                if (concreteinterferes.interferes(mun,r,false)) {
                    GraphNode scopenode=(GraphNode)scopefalsify.get(r);
-                   GraphNode.Edge e=new GraphNode.Edge("interferes",scopenode);
+                   GraphNode.Edge e=new GraphNode.Edge("falsifyscopeinterferes",scopenode);
                    gn.addEdge(e);
                }
            }
@@ -288,7 +304,7 @@ public class Termination {
                if (abstractinterferes.checkrelationconstraint(ar, cons))
                    continue;
                 if (AbstractInterferes.interferesquantifier(ar,cons)) {
-                    GraphNode.Edge e=new GraphNode.Edge("interferes",gn2);
+                    GraphNode.Edge e=new GraphNode.Edge("interferesquantifier",gn2);
                     gn.addEdge(e);
                 } else {
                     for(int i=0;i<conj.size();i++) {
@@ -298,7 +314,7 @@ public class Termination {
                             continue;
                         if (getConstraint(gn)==null||
                             !abstractinterferes.interferemodifies(ar,getConstraint(gn),dp,cons)) {
-                            GraphNode.Edge e=new GraphNode.Edge("interferes",gn2);
+                            GraphNode.Edge e=new GraphNode.Edge("interferesmodify",gn2);
                             gn.addEdge(e);
                             break;
                         }
@@ -310,7 +326,7 @@ public class Termination {
                TermNode tn2=(TermNode)gn2.getOwner();
                ScopeNode sn2=tn2.getScope();
                if (AbstractInterferes.interfereswithrule(ar,sn2.getRule(),sn2.getSatisfy())) {
-                   GraphNode.Edge e=new GraphNode.Edge("interferes",gn2);
+                   GraphNode.Edge e=new GraphNode.Edge("interfereswithrule",gn2);
                    gn.addEdge(e);
                }
            }
@@ -335,9 +351,13 @@ public class Termination {
            ScopeNode satisfy=new ScopeNode(r,true);
            TermNode tnsatisfy=new TermNode(satisfy);
            GraphNode gnsatisfy=new GraphNode("SatisfyRule"+i,tnsatisfy);
+           gnsatisfy.setOption(scopeoption);
+            if (Compiler.MERGENODES)
+                gnsatisfy.setMerge();
            ConsequenceNode cnsatisfy=new ConsequenceNode();
            TermNode ctnsatisfy=new TermNode(cnsatisfy);
            GraphNode cgnsatisfy=new GraphNode("ConseqSatisfyRule"+i,ctnsatisfy);
+           cgnsatisfy.setOption(conseqoption);
            consequence.put(satisfy,cgnsatisfy);
            GraphNode.Edge esat=new GraphNode.Edge("consequencesatisfy"+i,cgnsatisfy);
            gnsatisfy.addEdge(esat);
@@ -348,9 +368,13 @@ public class Termination {
            ScopeNode falsify=new ScopeNode(r,false);
            TermNode tnfalsify=new TermNode(falsify);
            GraphNode gnfalsify=new GraphNode("FalsifyRule"+i,tnfalsify);
+           gnfalsify.setOption(scopeoption);
+            if (Compiler.MERGENODES)
+                gnfalsify.setMerge();
            ConsequenceNode cnfalsify=new ConsequenceNode();
            TermNode ctnfalsify=new TermNode(cnfalsify);
            GraphNode cgnfalsify=new GraphNode("ConseqFalsifyRule"+i,ctnfalsify);
+           cgnfalsify.setOption(conseqoption);
            consequence.put(falsify,cgnfalsify);
            GraphNode.Edge efals=new GraphNode.Edge("consequencefalsify"+i,cgnfalsify);
            gnfalsify.addEdge(efals);
@@ -376,7 +400,7 @@ public class Termination {
                    DNFPredicate dp=conj.get(i);
                    if (abstractinterferes.scopeinterfereswithpredicate(sn,dp)||
                        AbstractInterferes.interfereswithquantifier(sn.getDescriptor(),sn.getSatisfy(),constr)) {
-                       GraphNode.Edge e=new GraphNode.Edge("interferes",gn2);
+                       GraphNode.Edge e=new GraphNode.Edge("interferesconjunction",gn2);
                        GraphNode gnconseq=(GraphNode)consequence.get(sn);
                        gnconseq.addEdge(e);
                        break;
@@ -389,13 +413,13 @@ public class Termination {
                Rule r=(Rule) state.vRules.get(i);
                if (AbstractInterferes.interfereswithrule(sn.getDescriptor(),sn.getSatisfy(),r,true)) {
                    GraphNode scopenode=(GraphNode)scopesatisfy.get(r);
-                   GraphNode.Edge e=new GraphNode.Edge("interferes",scopenode);
+                   GraphNode.Edge e=new GraphNode.Edge("interferesscopesatisfy2",scopenode);
                    GraphNode gnconseq=(GraphNode)consequence.get(sn);
                    gnconseq.addEdge(e);
                }
                if (AbstractInterferes.interfereswithrule(sn.getDescriptor(),sn.getSatisfy(),r,false)) {
                    GraphNode scopenode=(GraphNode)scopefalsify.get(r);
-                   GraphNode.Edge e=new GraphNode.Edge("interferes",scopenode);
+                   GraphNode.Edge e=new GraphNode.Edge("interferesscopefalsify2",scopenode);
                    GraphNode gnconseq=(GraphNode)consequence.get(sn);
                    gnconseq.addEdge(e);
                }
@@ -440,10 +464,40 @@ public class Termination {
                }
 
                for(int j=0;j<array.length;j++) {
+                    if (array[j]==AbstractRepair.ADDTOSET) {
+
+                        System.out.println("1");
+                        if ((dp.getPredicate() instanceof ExprPredicate)&&
+                            (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
+                            System.out.println("2");
+                            boolean neg=dp.isNegated();
+                            Opcode op=((ExprPredicate)dp.getPredicate()).getOp();
+                            int size=((ExprPredicate)dp.getPredicate()).rightSize();
+                            op=Opcode.translateOpcode(neg,op);
+                            Descriptor des=((ExprPredicate)dp.getPredicate()).getDescriptor();
+                            if (des instanceof SetDescriptor) {
+                                System.out.println("3");
+
+                                int minsize=exactsize.minSize((SetDescriptor)des);
+                                Constraint reqc=exactsize.ensuresMinSize((SetDescriptor)des);
+                                if (((size==minsize)&&(op==Opcode.EQ))||
+                                    ((size<=minsize)&&(op==Opcode.GE))||
+                                    ((size<minsize)&&(op==Opcode.GT))) {
+                                    System.out.println("4");
+                                    constraintdependence.requiresConstraint(gn,reqc);
+                                    //force good ordering
+                                    continue; //no repair action needed here...
+                                }
+                            }
+                        }
+                    }
+
                    AbstractRepair ar=new AbstractRepair(dp,array[j],d,sources);
                    TermNode tn2=new TermNode(ar);
-                   GraphNode gn2=new GraphNode(gn.getLabel()+"A"+i+"B"+ar.type(),gn.getTextLabel()+" #"+i+" "+ar.type(),tn2);
-                   GraphNode.Edge e=new GraphNode.Edge("abstract",gn2);
+                   //              GraphNode gn2=new GraphNode(gn.getLabel()+"A"+i+"B"+ar.type(),gn.getTextLabel()+" #"+i+" "+ar.type(),tn2);
+                   GraphNode gn2=new GraphNode(gn.getLabel()+"A"+i+"B"+ar.type(),dp.name()+" "+ar.type(),tn2);
+                   gn2.setOption(absrepoption);
+                   GraphNode.Edge e=new GraphNode.Edge("abstractedge1",gn2);
                    gn.addEdge(e);
                    if (!predtoabstractmap.containsKey(dp))
                        predtoabstractmap.put(dp,new HashSet());
@@ -463,6 +517,7 @@ public class Termination {
            AbstractRepair ar=new AbstractRepair(tp, AbstractRepair.ADDTOSET, sd,sources);
            TermNode tn=new TermNode(ar);
            GraphNode gn=new GraphNode("AbstractAddSetRule"+i,tn);
+           gn.setOption(absrepoption);
            if (!predtoabstractmap.containsKey(tp))
                predtoabstractmap.put(tp,new HashSet());
            ((Set)predtoabstractmap.get(tp)).add(gn);
@@ -474,6 +529,7 @@ public class Termination {
            AbstractRepair ar2=new AbstractRepair(tp2, AbstractRepair.REMOVEFROMSET, sd,sources);
            TermNode tn2=new TermNode(ar2);
            GraphNode gn2=new GraphNode("AbstractRemSetRule"+i,tn2);
+           gn2.setOption(absrepoption);
            if (!predtoabstractmap.containsKey(tp2))
                predtoabstractmap.put(tp2,new HashSet());
            ((Set)predtoabstractmap.get(tp2)).add(gn2);
@@ -494,6 +550,7 @@ public class Termination {
            AbstractRepair ar=new AbstractRepair(tp, AbstractRepair.ADDTORELATION, rd,sources);
            TermNode tn=new TermNode(ar);
            GraphNode gn=new GraphNode("AbstractAddRelRule"+i,tn);
+           gn.setOption(absrepoption);
            if (!predtoabstractmap.containsKey(tp))
                predtoabstractmap.put(tp,new HashSet());
            ((Set)predtoabstractmap.get(tp)).add(gn);
@@ -505,6 +562,7 @@ public class Termination {
            AbstractRepair ar2=new AbstractRepair(tp2, AbstractRepair.REMOVEFROMRELATION, rd,sources);
            TermNode tn2=new TermNode(ar2);
            GraphNode gn2=new GraphNode("AbstractRemRelRule"+i,tn2);
+           gn2.setOption(absrepoption);
            if (!predtoabstractmap.containsKey(tp2))
                predtoabstractmap.put(tp2,new HashSet());
            ((Set)predtoabstractmap.get(tp2)).add(gn2);
@@ -527,6 +585,7 @@ public class Termination {
                MultUpdateNode mun=new MultUpdateNode(sn);
                TermNode tn2=new TermNode(mun);
                GraphNode gn2=new GraphNode("CompRem"+compensationcount,tn2);
+               gn2.setOption(compoption);
                UpdateNode un=new UpdateNode(r);
 
                if (j<r.numQuantifiers()) {
@@ -540,7 +599,7 @@ public class Termination {
                        un.addUpdate(u);
                        if (abstractremove.containsKey(rq.relation)) {
                            GraphNode agn=(GraphNode)abstractremove.get(rq.relation);
-                           GraphNode.Edge e=new GraphNode.Edge("requires",agn);
+                           GraphNode.Edge e=new GraphNode.Edge("requiresremove1",agn);
                            gn2.addEdge(e);
                        } else {
                            continue; /* Abstract repair doesn't exist */
@@ -553,7 +612,7 @@ public class Termination {
                        un.addUpdate(u);
                        if (abstractremove.containsKey(sq.set)) {
                            GraphNode agn=(GraphNode)abstractremove.get(sq.set);
-                           GraphNode.Edge e=new GraphNode.Edge("requires",agn);
+                           GraphNode.Edge e=new GraphNode.Edge("requiresremove2",agn);
                            gn2.addEdge(e);
                        } else {
                            continue; /* Abstract repair doesn't exist */
@@ -572,7 +631,7 @@ public class Termination {
                    continue;
 
                mun.addUpdate(un);
-               GraphNode.Edge e=new GraphNode.Edge("abstract"+compensationcount,gn2);
+               GraphNode.Edge e=new GraphNode.Edge("abstractcomp"+compensationcount,gn2);
                compensationcount++;
                gn.addEdge(e);
                updatenodes.add(gn2);
@@ -632,6 +691,7 @@ public class Termination {
            MultUpdateNode mun=new MultUpdateNode(ar,MultUpdateNode.REMOVE);
            TermNode tn=new TermNode(mun);
            GraphNode gn2=new GraphNode("UpdateRem"+removefromcount,tn);
+           gn2.setOption(updateoption);
 
            boolean goodflag=true;
            for(int i=0;i<possiblerules.size();i++) {
@@ -649,7 +709,7 @@ public class Termination {
                        un.addUpdate(u);
                        if (abstractremove.containsKey(rq.relation)) {
                            GraphNode agn=(GraphNode)abstractremove.get(rq.relation);
-                           GraphNode.Edge e=new GraphNode.Edge("requires",agn);
+                           GraphNode.Edge e=new GraphNode.Edge("requiresremove3",agn);
                            gn2.addEdge(e);
                        } else {
                            goodflag=false;break; /* Abstract repair doesn't exist */
@@ -662,7 +722,7 @@ public class Termination {
                        un.addUpdate(u);
                        if (abstractremove.containsKey(sq.set)) {
                            GraphNode agn=(GraphNode)abstractremove.get(sq.set);
-                           GraphNode.Edge e=new GraphNode.Edge("requires",agn);
+                           GraphNode.Edge e=new GraphNode.Edge("requiresremove4",agn);
                            gn2.addEdge(e);
                        } else {
                            goodflag=false;break; /* Abstract repair doesn't exist */
@@ -681,7 +741,7 @@ public class Termination {
                mun.addUpdate(un);
            }
            if (goodflag) {
-               GraphNode.Edge e=new GraphNode.Edge("abstract"+(removefromcount++),gn2);
+               GraphNode.Edge e=new GraphNode.Edge("abstract3"+(removefromcount++),gn2);
                gn.addEdge(e);
                updatenodes.add(gn2);
            }
@@ -747,6 +807,7 @@ public class Termination {
            MultUpdateNode mun=new MultUpdateNode(ar,MultUpdateNode.MODIFY);
            TermNode tn=new TermNode(mun);
            GraphNode gn2=new GraphNode("UpdateMod"+modifycount,tn);
+           gn2.setOption(updateoption);
 
            boolean goodflag=true;
            for(int i=0;i<possiblerules.size();i++) {
@@ -801,7 +862,7 @@ public class Termination {
                mun.addUpdate(un);
            }
            if (goodflag) {
-               GraphNode.Edge e=new GraphNode.Edge("abstract"+modifycount,gn2);
+               GraphNode.Edge e=new GraphNode.Edge("abstract4"+modifycount,gn2);
                modifycount++;
                gn.addEdge(e);
                updatenodes.add(gn2);
@@ -975,6 +1036,7 @@ public class Termination {
                    MultUpdateNode mun=new MultUpdateNode(ar,MultUpdateNode.ADD);
                    TermNode tn=new TermNode(mun);
                    GraphNode gn2=new GraphNode("UpdateAdd"+addtocount,tn);
+                   gn2.setOption(updateoption);
 
                    if (debugmsg("Start processing quantifiers")&&
                        processquantifiers(gn2,un, r,setmapping)&&
@@ -984,7 +1046,7 @@ public class Termination {
                        un.checkupdates()&&
                        debugmsg("Updates checked")) {
                        mun.addUpdate(un);
-                       GraphNode.Edge e=new GraphNode.Edge("abstract"+addtocount,gn2);
+                       GraphNode.Edge e=new GraphNode.Edge("abstract5"+addtocount,gn2);
                        addtocount++;
                        gn.addEdge(e);
                        updatenodes.add(gn2);
@@ -1238,7 +1300,7 @@ public class Termination {
                un.addUpdate(u);
                if (abstractadd.containsKey(rq.relation)) {
                    GraphNode agn=(GraphNode)abstractadd.get(rq.relation);
-                   GraphNode.Edge e=new GraphNode.Edge("requires",agn);
+                   GraphNode.Edge e=new GraphNode.Edge("requiresadd5",agn);
                    gn.addEdge(e);
                } else {
                    return false;
@@ -1262,7 +1324,7 @@ public class Termination {
                un.addUpdate(u);
                if (abstractadd.containsKey(sq.set)) {
                    GraphNode agn=(GraphNode)abstractadd.get(sq.set);
-                   GraphNode.Edge e=new GraphNode.Edge("requires",agn);
+                   GraphNode.Edge e=new GraphNode.Edge("requiresadd6",agn);
                    gn.addEdge(e);
                } else {
                    return false;
Data structure repair