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
  17     public Set doAnalysis() {
  18         HashSet nodes=new HashSet();
  19         nodes.addAll(termination.conjunctions);
  20         GraphNode.computeclosure(nodes,null);
  21         Set cycles=GraphNode.findcycles(nodes);
  22         Set couldremove=new HashSet();
  23         couldremove.addAll(termination.conjunctions);
  24         couldremove.addAll(termination.updatenodes);
  25         couldremove.addAll(termination.consequencenodes);
  26         couldremove.retainAll(cycles);
  27         Vector constraints=termination.state.vConstraints;
  28         for(int i=0;i<constraints.size();i++) {
  29             Constraint c=(Constraint)constraints.get(i);
  30             Set conjunctionset=(Set)termination.conjunctionmap.get(c);
  31             if (conjunctionset.size()==1)
  32                 couldremove.removeAll(conjunctionset);
  33         }
  34
  35
  36         Vector couldremovevector=new Vector();
  37         couldremovevector.addAll(couldremove);
  38         Vector combination=new Vector();
  39
  40         while(true) {
  41             if (illegal(combination,couldremovevector))
  42                 break;
  43             Set combinationset=buildset(combination,couldremovevector);
  44             if (combinationset!=null) {
  45                 System.out.println("Checkabstract="+checkAbstract(combinationset));
  46                 System.out.println("Checkrepairs="+checkRepairs(combinationset));
  47                 System.out.println("Checkall="+checkAll(combinationset));
  48
  49                 if (checkAbstract(combinationset)==0&&
  50                     checkRepairs(combinationset)==0&&
  51                     checkAll(combinationset)==0) {
  52                     return combinationset;
  53                 }
  54             }
  55             increment(combination,couldremovevector);
  56         }
  57         return null;
  58     }
  59
  60     private static Set buildset(Vector combination, Vector couldremove) {
  61         Set s=new HashSet();
  62         for(int i=0;i<combination.size();i++) {
  63             int index=((Integer)combination.get(i)).intValue();
  64             Object o=couldremove.get(index);
  65             if (s.contains(o))
  66                 return null;
  67             else
  68                 s.add(o);
  69         }
  70         return s;
  71     }
  72
  73     private static boolean illegal(Vector combination, Vector couldremove) {
  74         if (combination.size()>couldremove.size())
  75             return true;
  76         else return false;
  77     }
  78     private static void increment(Vector combination, Vector couldremove) {
  79         boolean incremented=false;
  80         for(int i=0;i<combination.size();i++) {
  81             int newindex=((Integer)combination.get(i)).intValue()+1;
  82             while(combination.contains(new Integer(newindex)))
  83                 newindex++;
  84             if (newindex==couldremove.size()) {
  85                 newindex=0;
  86                 combination.set(i,new Integer(newindex));
  87             } else {
  88                 incremented=true;
  89                 combination.set(i,new Integer(newindex));
  90                 break;
  91             }
  92         }
  93         if (incremented==false) /* Increase length */
  94             combination.add(new Integer(0));
  95     }
  96
  97     /* This function checks the graph as a whole for bad cycles */
  98     public int checkAll(Collection removed) {
  99         Set nodes=new HashSet();
 100         nodes.addAll(termination.conjunctions);
 101         nodes.removeAll(removed);
 102         GraphNode.computeclosure(nodes,removed);
 103         Set cycles=GraphNode.findcycles(nodes);
 104         for(Iterator it=cycles.iterator();it.hasNext();) {
 105             GraphNode gn=(GraphNode)it.next();
 106             TermNode tn=(TermNode)gn.getOwner();
 107             switch(tn.getType()) {
 108             case TermNode.UPDATE:
 109             case TermNode.CONJUNCTION:
 110                 return ERR_CYCLE;
 111             case TermNode.ABSTRACT:
 112             case TermNode.RULESCOPE:
 113             case TermNode.CONSEQUENCE:
 114             default:
 115                 break;
 116             }
 117         }
 118         return WORKS;
 119     }
 120
 121     /* This function checks that
 122        1) All abstract repairs have a corresponding data structure update
 123           that isn't removed.
 124        2) All scope nodes have either a consequence node or a compensation
 125           node that isn't removed.
 126      */
 127     public int checkRepairs(Collection removed) {
 128         Set nodes=new HashSet();
 129         nodes.addAll(termination.conjunctions);
 130         nodes.removeAll(removed);
 131         GraphNode.computeclosure(nodes,removed);
 132         Set toretain=new HashSet();
 133         toretain.addAll(termination.abstractrepair);
 134         toretain.addAll(termination.scopenodes);
 135         nodes.retainAll(toretain);
 136         /* Nodes is now the reachable set of abstractrepairs */
 137         /* Check to see that each has an implementation */
 138         for(Iterator it=nodes.iterator();it.hasNext();) {
 139             GraphNode gn=(GraphNode)it.next();
 140             TermNode tn=(TermNode)gn.getOwner();
 141             if (tn.getType()==TermNode.RULESCOPE) {
 142                 boolean foundnode=false;
 143                 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
 144                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
 145                     GraphNode gn2=edge.getTarget();
 146                     if (!removed.contains(gn2)) {
 147                         TermNode tn2=(TermNode)gn2.getOwner();
 148                         if ((tn2.getType()==TermNode.CONSEQUENCE)||
 149                             (tn2.getType()==TermNode.UPDATE)) {
 150                             foundnode=true;
 151                             break;
 152                         }
 153                     }
 154                 }
 155                 if (!foundnode) {
 156                     System.out.println(gn.getTextLabel());
 157                     return ERR_RULE;
 158                 }
 159             } else if (tn.getType()==TermNode.ABSTRACT) {
 160                 boolean foundnode=false;
 161                 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
 162                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
 163                     GraphNode gn2=edge.getTarget();
 164                     if (!removed.contains(gn2)) {
 165                         TermNode tn2=(TermNode)gn2.getOwner();
 166                         if (tn2.getType()==TermNode.UPDATE) {
 167                             foundnode=true;
 168                             break;
 169                         }
 170                     }
 171                 }
 172                 if (!foundnode)
 173                     return ERR_ABSTRACT;
 174             } else throw new Error("Unanticipated Node");
 175         }
 176         return WORKS;
 177     }
 178     /* This method checks that all constraints have conjunction nodes
 179        and that there are no bad cycles in the abstract portion of the graph.
 180      */
 181     public int checkAbstract(Collection removed) {
 182         Vector constraints=termination.state.vConstraints;
 183         for(int i=0;i<constraints.size();i++) {
 184             Constraint c=(Constraint)constraints.get(i);
 185             Set conjunctionset=(Set)termination.conjunctionmap.get(c);
 186
 187             boolean foundrepair=false;
 188             for(Iterator it=conjunctionset.iterator();it.hasNext();) {
 189                 GraphNode gn=(GraphNode)it.next();
 190                 if (!removed.contains(gn)) {
 191                     foundrepair=true;
 192                 }
 193             }
 194             if (!foundrepair)
 195                 return ERR_NOREPAIR;
 196         }
 197         Set abstractnodes=new HashSet();
 198         abstractnodes.addAll(termination.conjunctions);
 199         abstractnodes.removeAll(removed);
 200         GraphNode.computeclosure(abstractnodes,removed);
 201
 202         Set tset=new HashSet();
 203         tset.addAll(termination.conjunctions);
 204         tset.addAll(termination.abstractrepair);
 205         tset.addAll(termination.scopenodes);
 206         tset.addAll(termination.consequencenodes);
 207         abstractnodes.retainAll(tset);
 208         Set cycles=GraphNode.findcycles(abstractnodes);
 209
 210         for(Iterator it=cycles.iterator();it.hasNext();) {
 211             GraphNode gn=(GraphNode)it.next();
 212             System.out.println("NODE: "+gn.getTextLabel());
 213             TermNode tn=(TermNode)gn.getOwner();
 214             switch(tn.getType()) {
 215             case TermNode.CONJUNCTION:
 216             case TermNode.ABSTRACT:
 217                 return ERR_CYCLE;
 218             case TermNode.UPDATE:
 219                 throw new Error("No Update Nodes should be here");
 220             default:
 221             }
 222         }
 223         return WORKS;
 224     }
 225 }