package MCC.IR;
import java.util.*;
+import java.io.*;
import MCC.State;
public class GraphAnalysis {
public Set doAnalysis() {
HashSet cantremove=new HashSet();
HashSet mustremove=new HashSet();
+
cantremove.addAll(termination.scopenodes);
cantremove.addAll(termination.abstractrepair);
GraphNode.computeclosure(nodes,mustremove);
Set cycles=GraphNode.findcycles(nodes);
Set couldremove=new HashSet();
- couldremove.addAll(termination.conjunctions);
+ couldremove.addAll(termination.conjunctions);
couldremove.addAll(termination.updatenodes);
couldremove.addAll(termination.consequencenodes);
couldremove.retainAll(cycles);
-
/* Look for constraints which can only be satisfied one way */
Vector constraints=termination.state.vConstraints;
change=true;
}
}
+
+
+ /* Search through conjunction which must be satisfied, and attempt
+ to generate appropriate repair actions.
+ */
HashSet newset=new HashSet();
for(Iterator cit=cantremove.iterator();cit.hasNext();) {
GraphNode gn=(GraphNode)cit.next();
GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
GraphNode gn2=e.getTarget();
TermNode tn2=(TermNode)gn2.getOwner();
- if (tn2.getType()==TermNode.ABSTRACT) {
- AbstractRepair ar=tn2.getAbstract();
- if (ar.getType()==AbstractRepair.MODIFYRELATION) {
- nomodify=false;
- break;
- }
+ if (nodes.contains(gn2)&&
+ tn2.getType()==TermNode.ABSTRACT) {
+
HashSet updateset=new HashSet();
for(Iterator upit=gn2.edges();upit.hasNext();) {
GraphNode.Edge e2=(GraphNode.Edge)upit.next();
toremove.addAll(updateset);
}
}
- if (nomodify) {
- newset.addAll(toremove);
- }
+ newset.addAll(toremove);
}
}
+
{
int oldsize=cantremove.size();
cantremove.addAll(newset);
Set cycles2=GraphNode.findcycles(cantremove);
for(Iterator it=cycles2.iterator();it.hasNext();) {
GraphNode gn=(GraphNode)it.next();
- if (termination.conjunctions.contains(gn))
+ if (termination.conjunctions.contains(gn)) {
+ System.out.println("Cycle through conjunction "+gn.getTextLabel() +" which can't be removed.");
return null; // Out of luck
+ }
}
-
-
- for(Iterator it=termination.conjunctions.iterator();it.hasNext();) {
+
+ /* Search through abstract repair actions & correspond data structure updates */
+ for(Iterator it=termination.abstractrepairadd.iterator();it.hasNext();) {
GraphNode gn=(GraphNode)it.next();
- if (!cantremove.contains(gn)) {
+ TermNode tn=(TermNode)gn.getOwner();
+
+ for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
+ GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
+ GraphNode gn2=e.getTarget();
+ TermNode tn2=(TermNode)gn2.getOwner();
+ if (tn2.getType()!=TermNode.UPDATE)
+ continue;
+
+ boolean containsgn=cantremove.contains(gn);
+ boolean containsgn2=cantremove.contains(gn2);
+
cantremove.add(gn);
+ cantremove.add(gn2);
+
Set cycle=GraphNode.findcycles(cantremove);
- if (cycle.contains(gn)) {
- if (!mustremove.contains(gn)) {
+ if (cycle.contains(gn2)) {
+ if (!mustremove.contains(gn2)) {
change=true;
- mustremove.add(gn);
+ mustremove.add(gn2);
+ }
+ }
+ if (!containsgn)
+ cantremove.remove(gn);
+ if (!containsgn2)
+ cantremove.remove(gn2);
+ }
+ }
+
+ /* Searches individual conjunctions + abstract action +updates for cycles */
+ for(Iterator it=termination.conjunctions.iterator();it.hasNext();) {
+ GraphNode gn=(GraphNode)it.next();
+ boolean foundnocycle=false;
+
+ for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
+ GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
+ GraphNode gn2=e.getTarget();
+ TermNode tn2=(TermNode)gn2.getOwner();
+ if (tn2.getType()!=TermNode.ABSTRACT)
+ continue;
+ AbstractRepair ar=tn2.getAbstract();
+ boolean ismodify=ar.getType()==AbstractRepair.MODIFYRELATION;
+ int numadd=0;int numremove=0;
+
+ for (Iterator edgeit2=gn2.edges();edgeit2.hasNext();) {
+ GraphNode.Edge e2=(GraphNode.Edge)edgeit2.next();
+ GraphNode gn3=e2.getTarget();
+ TermNode tn3=(TermNode)gn3.getOwner();
+ if (tn3.getType()!=TermNode.UPDATE)
+ continue;
+
+ boolean containsgn=cantremove.contains(gn);
+ boolean containsgn2=cantremove.contains(gn2);
+ boolean containsgn3=cantremove.contains(gn3);
+ cantremove.add(gn);
+ cantremove.add(gn2);
+ cantremove.add(gn3);
+ Set cycle=GraphNode.findcycles(cantremove);
+ if (cycle.contains(gn3)) {
+ if (!mustremove.contains(gn3)) {
+ change=true;
+ mustremove.add(gn3);
+ }
+ }
+ if (!mustremove.contains(gn3)&&!cycle.contains(gn)) {
+ foundnocycle=true;
+ if (ismodify) {
+ MultUpdateNode mun=tn3.getUpdate();
+ if (mun.getType()==MultUpdateNode.ADD)
+ numadd++;
+ if (mun.getType()==MultUpdateNode.REMOVE)
+ numremove++;
+ }
+ }
+ if (!containsgn)
+ cantremove.remove(gn);
+ if (!containsgn2)
+ cantremove.remove(gn2);
+ if (!containsgn3)
+ cantremove.remove(gn3);
+ }
+ if (ismodify&&((numadd==0)||(numremove==0))) {
+ for (Iterator edgeit2=gn2.edges();edgeit2.hasNext();) {
+ GraphNode.Edge e2=(GraphNode.Edge)edgeit2.next();
+ GraphNode gn3=e2.getTarget();
+ TermNode tn3=(TermNode)gn3.getOwner();
+ if (tn3.getType()!=TermNode.UPDATE)
+ continue;
+ MultUpdateNode mun=tn3.getUpdate();
+ if (((mun.getType()==MultUpdateNode.ADD)||
+ (mun.getType()==MultUpdateNode.REMOVE))&&
+ (!mustremove.contains(gn3)))
+ mustremove.add(gn3);
+ }
+ }
+ }
+
+ if(!foundnocycle) {
+ if (!mustremove.contains(gn)) {
+ change=true;
+ mustremove.add(gn);
+ }
+ }
+ }
+
+ /* Searches scope nodes + compensation nodes */
+ for(Iterator it=termination.scopenodes.iterator();it.hasNext();) {
+ GraphNode gn=(GraphNode)it.next();
+ boolean foundcompensation=false;
+ if (nodes.contains(gn)) {
+ for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
+ GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
+ GraphNode gn2=e.getTarget();
+ TermNode tn2=(TermNode)gn2.getOwner();
+
+ if (tn2.getType()!=TermNode.UPDATE)
+ continue;
+ /* We have a compensation node */
+ boolean containsgn=cantremove.contains(gn);
+ boolean containsgn2=cantremove.contains(gn2);
+ cantremove.add(gn);
+ cantremove.add(gn2);
+
+ Set cycle=GraphNode.findcycles(cantremove);
+ if (cycle.contains(gn2)) {
+ if (!mustremove.contains(gn2)) {
+ change=true;
+ mustremove.add(gn2);
+ }
+ } else {
+ if (!mustremove.contains(gn2))
+ foundcompensation=true;
+ }
+ if (!containsgn)
+ cantremove.remove(gn);
+ if (!containsgn2)
+ cantremove.remove(gn2);
+ }
+ }
+ if (!foundcompensation) {
+ for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
+ GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
+ GraphNode gn2=e.getTarget();
+ TermNode tn2=(TermNode)gn2.getOwner();
+ if (tn2.getType()==TermNode.UPDATE) {
+ cantremove.add(gn2);
+ break;
}
}
- cantremove.remove(gn);
}
}
couldremove.removeAll(mustremove);
if(change)
continue; //recalculate
+ try {
+ GraphNode.DOTVisitor.visit(new FileOutputStream("graphsearch.dot"),nodes);
+ } catch (Exception e) {
+ e.printStackTrace();
+ System.exit(-1);
+ }
+
System.out.println("Searching set of "+couldremove.size()+" nodes.");
- System.out.println("Eliminated "+mustremove.size()+" nodes");
+ System.out.println("Eliminated must "+mustremove.size()+" nodes");
+ System.out.println("Eliminated cant "+cantremove.size()+" nodes");
System.out.println("Searching following set:");
for(Iterator it=couldremove.iterator();it.hasNext();) {
GraphNode gn=(GraphNode)it.next();
if (illegal(combination,couldremovevector))
break;
Set combinationset=buildset(combination,couldremovevector);
+ checkmodify(combinationset);
combinationset.addAll(mustremove);
if (combinationset!=null) {
System.out.println("Checkabstract="+checkAbstract(combinationset));
}
increment(combination,couldremovevector);
}
+ System.out.println("Search failed!");
return null;
}
}
+ private void checkmodify(Set removednodes) {
+ for (Iterator it=termination.abstractrepair.iterator();it.hasNext();) {
+ GraphNode gn=(GraphNode)it.next();
+ TermNode tn=(TermNode)gn.getOwner();
+ AbstractRepair ar=tn.getAbstract();
+
+ /* Has MODIFYRELATION */
+ if (ar.getType()==AbstractRepair.MODIFYRELATION) {
+ int numadd=0;
+ int numremove=0;
+ for(Iterator it2=gn.edges();it2.hasNext();) {
+ GraphNode.Edge edge=(GraphNode.Edge)it2.next();
+ GraphNode gn2=edge.getTarget();
+ TermNode tn2=(TermNode)gn2.getOwner();
+ if (!removednodes.contains(gn2)&&
+ tn2.getType()==TermNode.UPDATE) {
+ MultUpdateNode mun=tn2.getUpdate();
+
+ if (mun.getType()==MultUpdateNode.ADD)
+ numadd++;
+ if (mun.getType()==MultUpdateNode.REMOVE)
+ numremove++;
+ }
+ }
+ if ((numadd==0)||(numremove==0)) {
+ for(Iterator it2=gn.edges();it2.hasNext();) {
+ GraphNode.Edge edge=(GraphNode.Edge)it2.next();
+ GraphNode gn2=edge.getTarget();
+ TermNode tn2=(TermNode)gn2.getOwner();
+ if (!removednodes.contains(gn2)&&
+ tn2.getType()==TermNode.UPDATE) {
+ MultUpdateNode mun=tn2.getUpdate();
+ if ((mun.getType()==MultUpdateNode.ADD)
+ ||(mun.getType()==MultUpdateNode.REMOVE)) {
+ removednodes.add(gn2);
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
private static Set buildset(Vector combination, Vector couldremove) {
Set s=new HashSet();
for(int i=0;i<combination.size();i++) {
if (!foundrepair)
return ERR_NOREPAIR;
}
+
+
Set abstractnodes=new HashSet();
abstractnodes.addAll(termination.conjunctions);
abstractnodes.removeAll(removed);