Repair/RepairCompiler/MCC/IR/GraphAnalysis.java

   1 package MCC.IR;
   2 import java.util.*;
   3 import MCC.State;
   4
   5 public class GraphAnalysis {
   6     Termination termination;
   7     static final int WORKS=0;
   8     static final int ERR_NOREPAIR=1;
   9     static final int ERR_CYCLE=2;
  10     static final int ERR_RULE=3;
  11     static final int ERR_ABSTRACT=4;
  12
  13     public GraphAnalysis(Termination t) {
  14         termination=t;
  15     }
  16     /* This function checks that
  17        1) All abstract repairs have a corresponding data structure update
  18           that isn't removed.
  19        2) All scope nodes have either a consequence node or a compensation
  20           node that isn't removed.
  21      */
  22     public int checkRepairs(Set removed) {
  23         Set nodes=new HashSet();
  24         nodes.addAll(termination.conjunctions);
  25         nodes.removeAll(removed);
  26         GraphNode.computeclosure(nodes,removed);
  27         Set toretain=new HashSet();
  28         toretain.addAll(termination.abstractrepair);
  29         toretain.addAll(termination.scopenodes);
  30         nodes.retainAll(toretain);
  31         /* Nodes is now the reachable set of abstractrepairs */
  32         /* Check to see that each has an implementation */
  33         for(Iterator it=nodes.iterator();it.hasNext();) {
  34             GraphNode gn=(GraphNode)it.next();
  35             TermNode tn=(TermNode)gn.getOwner();
  36             if (tn.getType()==TermNode.RULESCOPE) {
  37                 boolean foundnode=false;
  38                 for (Iterator edgeit=gn.edges();it.hasNext();) {
  39                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
  40                     GraphNode gn2=edge.getTarget();
  41                     if (!removed.contains(gn2)) {
  42                         TermNode tn2=(TermNode)gn2.getOwner();
  43                         if (tn2.getType()==TermNode.CONSEQUENCE||
  44                             tn2.getType()==TermNode.UPDATE) {
  45                             foundnode=true;
  46                             break;
  47                         }
  48                     }
  49                 }
  50                 if (!foundnode)
  51                     return ERR_RULE;
  52             } else if (tn.getType()==TermNode.ABSTRACT) {
  53                 boolean foundnode=false;
  54                 for (Iterator edgeit=gn.edges();it.hasNext();) {
  55                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
  56                     GraphNode gn2=edge.getTarget();
  57                     if (!removed.contains(gn2)) {
  58                         TermNode tn2=(TermNode)gn2.getOwner();
  59                         if (tn2.getType()==TermNode.UPDATE) {
  60                             foundnode=true;
  61                             break;
  62                         }
  63                     }
  64                 }
  65                 if (!foundnode)
  66                     return ERR_ABSTRACT;
  67             } else throw new Error("Unanticipated Node");
  68         }
  69         return WORKS;
  70     }
  71     /* This method checks that all constraints have a conjunction nodes
  72        and that there are no bad cycles in the abstract portion of the graph.
  73      */
  74     public int checkAbstract(Set removed) {
  75         Vector constraints=termination.state.vConstraints;
  76         for(int i=0;i<constraints.size();i++) {
  77             Constraint c=(Constraint)constraints.get(i);
  78             Set conjunctionset=(Set)termination.conjunctionmap.get(c);
  79
  80             boolean foundrepair=false;
  81             for(Iterator it=conjunctionset.iterator();it.hasNext();) {
  82                 GraphNode gn=(GraphNode)it.next();
  83                 if (!removed.contains(gn)) {
  84                     foundrepair=true;
  85                 }
  86             }
  87             if (!foundrepair)
  88                 return ERR_NOREPAIR;
  89         }
  90         Set abstractnodes=new HashSet();
  91         abstractnodes.addAll(termination.conjunctions);
  92         abstractnodes.removeAll(removed);
  93         GraphNode.computeclosure(abstractnodes,removed);
  94
  95         Set tset=new HashSet();
  96         tset.addAll(termination.conjunctions);
  97         tset.addAll(termination.abstractrepair);
  98         tset.addAll(termination.scopenodes);
  99         tset.addAll(termination.consequencenodes);
 100         abstractnodes.retainAll(tset);
 101         Set cycles=GraphNode.findcycles(abstractnodes);
 102
 103         for(Iterator it=cycles.iterator();it.hasNext();) {
 104             GraphNode gn=(GraphNode)it.next();
 105             TermNode tn=(TermNode)gn.getOwner();
 106             switch(tn.getType()) {
 107             case TermNode.CONJUNCTION:
 108             case TermNode.ABSTRACT:
 109                 return ERR_CYCLE;
 110             case TermNode.UPDATE:
 111                 throw new Error("No Update Nodes should be here");
 112             default:
 113             }
 114         }
 115         return WORKS;
 116     }
 117 }