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 cantremove=new HashSet();
  19         HashSet mustremove=new HashSet();
  20         cantremove.addAll(termination.scopenodes);
  21         cantremove.addAll(termination.abstractrepair);
  22
  23         while(true) {
  24             boolean change=false;
  25             HashSet nodes=new HashSet();
  26             nodes.addAll(termination.conjunctions);
  27             nodes.removeAll(mustremove);
  28             GraphNode.computeclosure(nodes,mustremove);
  29             Set cycles=GraphNode.findcycles(nodes);
  30             Set couldremove=new HashSet();
  31             couldremove.addAll(termination.conjunctions);
  32             couldremove.addAll(termination.updatenodes);
  33             couldremove.addAll(termination.consequencenodes);
  34             couldremove.retainAll(cycles);
  35
  36
  37             /* Look for constraints which can only be satisfied one way */
  38
  39             Vector constraints=termination.state.vConstraints;
  40             for(int i=0;i<constraints.size();i++) {
  41                 Constraint c=(Constraint)constraints.get(i);
  42                 Set conjunctionset=(Set)termination.conjunctionmap.get(c);
  43                 HashSet tmpset=new HashSet();
  44                 tmpset.addAll(conjunctionset);
  45                 tmpset.removeAll(mustremove);
  46                 if (tmpset.size()==1) {
  47                     int oldsize=cantremove.size();
  48                     cantremove.addAll(tmpset);
  49                     if (cantremove.size()!=oldsize)
  50                         change=true;
  51                 }
  52             }
  53             HashSet newset=new HashSet();
  54             for(Iterator cit=cantremove.iterator();cit.hasNext();) {
  55                 GraphNode gn=(GraphNode)cit.next();
  56                 boolean nomodify=true;
  57                 HashSet toremove=new HashSet();
  58                 if (termination.conjunctions.contains(gn)) {
  59                     for(Iterator edgeit=gn.edges();edgeit.hasNext();) {
  60                         GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
  61                         GraphNode gn2=e.getTarget();
  62                         TermNode tn2=(TermNode)gn2.getOwner();
  63                         if (tn2.getType()==TermNode.ABSTRACT) {
  64                             AbstractRepair ar=tn2.getAbstract();
  65                             if (ar.getType()==AbstractRepair.MODIFYRELATION) {
  66                                 nomodify=false;
  67                                 break;
  68                             }
  69                             HashSet updateset=new HashSet();
  70                             for(Iterator upit=gn2.edges();upit.hasNext();) {
  71                                 GraphNode.Edge e2=(GraphNode.Edge)upit.next();
  72                                 GraphNode gn3=e2.getTarget();
  73                                 TermNode tn3=(TermNode)gn3.getOwner();
  74                                 if (tn3.getType()==TermNode.UPDATE)
  75                                     updateset.add(gn3);
  76                             }
  77                             updateset.removeAll(mustremove);
  78                             if (updateset.size()==1)
  79                                 toremove.addAll(updateset);
  80                         }
  81                     }
  82                     if (nomodify) {
  83                         newset.addAll(toremove);
  84                     }
  85                 }
  86             }
  87             {
  88                 int oldsize=cantremove.size();
  89                 cantremove.addAll(newset);
  90                 if (cantremove.size()!=oldsize)
  91                     change=true;
  92             }
  93
  94             /* Look for required actions for scope nodes */
  95             for(Iterator scopeit=termination.scopenodes.iterator();scopeit.hasNext();) {
  96                 GraphNode gn=(GraphNode)scopeit.next();
  97                 HashSet tmpset=new HashSet();
  98                 for(Iterator edgeit=gn.edges();edgeit.hasNext();) {
  99                     GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
 100                     tmpset.add(e.getTarget());
 101                 }
 102                 tmpset.removeAll(mustremove);
 103                 if (tmpset.size()==1) {
 104                     int oldsize=cantremove.size();
 105                     cantremove.addAll(tmpset);
 106                     if (cantremove.size()!=oldsize)
 107                         change=true;
 108                 }
 109             }
 110
 111             Set cycles2=GraphNode.findcycles(cantremove);
 112             for(Iterator it=cycles2.iterator();it.hasNext();) {
 113                 GraphNode gn=(GraphNode)it.next();
 114                 if (termination.conjunctions.contains(gn))
 115                     return null; // Out of luck
 116             }
 117
 118
 119             for(Iterator it=termination.conjunctions.iterator();it.hasNext();) {
 120                 GraphNode gn=(GraphNode)it.next();
 121                 boolean foundnocycle=false;
 122
 123                 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
 124                     GraphNode.Edge e=(GraphNode.Edge)edgeit.next();
 125                     GraphNode gn2=e.getTarget();
 126                     TermNode tn2=(TermNode)gn2.getOwner();
 127                     if (tn2.getType()!=TermNode.ABSTRACT)
 128                         continue;
 129                     for (Iterator edgeit2=gn2.edges();edgeit2.hasNext();) {
 130                         GraphNode.Edge e2=(GraphNode.Edge)edgeit2.next();
 131                         GraphNode gn3=e2.getTarget();
 132                         TermNode tn3=(TermNode)gn3.getOwner();
 133                         if (tn3.getType()!=TermNode.UPDATE)
 134                             continue;
 135                         boolean containsgn=cantremove.contains(gn);
 136                         boolean containsgn3=cantremove.contains(gn3);
 137                         cantremove.add(gn);
 138                         cantremove.add(gn3);
 139                         Set cycle=GraphNode.findcycles(cantremove);
 140                         if (cycle.contains(gn3)) {
 141                             if (!mustremove.contains(gn3)) {
 142                                 change=true;
 143                                 mustremove.add(gn3);
 144                             }
 145                         }
 146                         if (!mustremove.contains(gn3)&&!cycle.contains(gn)) {
 147                             foundnocycle=true;
 148                         }
 149                         if (!containsgn)
 150                             cantremove.remove(gn);
 151                         if (!containsgn3)
 152                             cantremove.remove(gn3);
 153                     }
 154                 }
 155                 if(!foundnocycle) {
 156                     if (!mustremove.contains(gn)) {
 157                         change=true;
 158                         mustremove.add(gn);
 159                     }
 160                 }
 161             }
 162             couldremove.removeAll(mustremove);
 163             couldremove.removeAll(cantremove);
 164
 165             Vector couldremovevector=new Vector();
 166             couldremovevector.addAll(couldremove);
 167             Vector combination=new Vector();
 168             if(change)
 169                 continue; //recalculate
 170
 171             System.out.println("Searching set of "+couldremove.size()+" nodes.");
 172             System.out.println("Eliminated must "+mustremove.size()+" nodes");
 173             System.out.println("Eliminated cant "+cantremove.size()+" nodes");
 174             System.out.println("Searching following set:");
 175             for(Iterator it=couldremove.iterator();it.hasNext();) {
 176                 GraphNode gn=(GraphNode)it.next();
 177                 System.out.println(gn.getTextLabel());
 178             }
 179
 180
 181             while(true) {
 182                 if (illegal(combination,couldremovevector))
 183                     break;
 184                 Set combinationset=buildset(combination,couldremovevector);
 185                 combinationset.addAll(mustremove);
 186                 if (combinationset!=null) {
 187                     System.out.println("Checkabstract="+checkAbstract(combinationset));
 188                     System.out.println("Checkrepairs="+checkRepairs(combinationset));
 189                     System.out.println("Checkall="+checkAll(combinationset));
 190
 191                     if (checkAbstract(combinationset)==0&&
 192                         checkRepairs(combinationset)==0&&
 193                         checkAll(combinationset)==0) {
 194                         return combinationset;
 195                     }
 196                 }
 197                 increment(combination,couldremovevector);
 198             }
 199             return null;
 200         }
 201     }
 202
 203     private static Set buildset(Vector combination, Vector couldremove) {
 204         Set s=new HashSet();
 205         for(int i=0;i<combination.size();i++) {
 206             int index=((Integer)combination.get(i)).intValue();
 207             Object o=couldremove.get(index);
 208             if (s.contains(o))
 209                 return null;
 210             else
 211                 s.add(o);
 212         }
 213         return s;
 214     }
 215
 216     private static boolean illegal(Vector combination, Vector couldremove) {
 217         if (combination.size()>couldremove.size())
 218             return true;
 219         else return false;
 220     }
 221     private static void increment(Vector combination, Vector couldremove) {
 222         boolean incremented=false;
 223         boolean forcereset=false;
 224         for(int i=0;i<combination.size();i++) {
 225             int newindex=((Integer)combination.get(i)).intValue()+1;
 226             if (newindex==couldremove.size()||forcereset) {
 227                 forcereset=false;
 228                 if ((i+1)==combination.size()) {
 229                     newindex=1;
 230                 } else
 231                     newindex=((Integer)combination.get(i+1)).intValue()+2;
 232                 for(int j=i;j>=0;j--) {
 233                     combination.set(j,new Integer(newindex));
 234                     newindex++;
 235                 }
 236                 if (newindex>couldremove.size())
 237                     forcereset=true;
 238             } else {
 239                 incremented=true;
 240                 combination.set(i,new Integer(newindex));
 241                 break;
 242             }
 243         }
 244         if (incremented==false) /* Increase length */ {
 245             combination.add(new Integer(0));
 246             System.out.println("Expanding to :"+combination.size());
 247         }
 248     }
 249
 250     /* This function checks the graph as a whole for bad cycles */
 251     public int checkAll(Collection removed) {
 252         Set nodes=new HashSet();
 253         nodes.addAll(termination.conjunctions);
 254         nodes.removeAll(removed);
 255         GraphNode.computeclosure(nodes,removed);
 256         Set cycles=GraphNode.findcycles(nodes);
 257         for(Iterator it=cycles.iterator();it.hasNext();) {
 258             GraphNode gn=(GraphNode)it.next();
 259             TermNode tn=(TermNode)gn.getOwner();
 260             switch(tn.getType()) {
 261             case TermNode.UPDATE:
 262             case TermNode.CONJUNCTION:
 263                 return ERR_CYCLE;
 264             case TermNode.ABSTRACT:
 265             case TermNode.RULESCOPE:
 266             case TermNode.CONSEQUENCE:
 267             default:
 268                 break;
 269             }
 270         }
 271         return WORKS;
 272     }
 273
 274     /* This function checks that
 275        1) All abstract repairs have a corresponding data structure update
 276           that isn't removed.
 277        2) All scope nodes have either a consequence node or a compensation
 278           node that isn't removed.
 279      */
 280     public int checkRepairs(Collection removed) {
 281         Set nodes=new HashSet();
 282         nodes.addAll(termination.conjunctions);
 283         nodes.removeAll(removed);
 284         GraphNode.computeclosure(nodes,removed);
 285         Set toretain=new HashSet();
 286         toretain.addAll(termination.abstractrepair);
 287         toretain.addAll(termination.scopenodes);
 288         nodes.retainAll(toretain);
 289         /* Nodes is now the reachable set of abstractrepairs */
 290         /* Check to see that each has an implementation */
 291         for(Iterator it=nodes.iterator();it.hasNext();) {
 292             GraphNode gn=(GraphNode)it.next();
 293             TermNode tn=(TermNode)gn.getOwner();
 294             if (tn.getType()==TermNode.RULESCOPE) {
 295                 boolean foundnode=false;
 296                 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
 297                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
 298                     GraphNode gn2=edge.getTarget();
 299                     if (!removed.contains(gn2)) {
 300                         TermNode tn2=(TermNode)gn2.getOwner();
 301                         if ((tn2.getType()==TermNode.CONSEQUENCE)||
 302                             (tn2.getType()==TermNode.UPDATE)) {
 303                             foundnode=true;
 304                             break;
 305                         }
 306                     }
 307                 }
 308                 if (!foundnode) {
 309                     System.out.println(gn.getTextLabel());
 310                     return ERR_RULE;
 311                 }
 312             } else if (tn.getType()==TermNode.ABSTRACT) {
 313                 boolean foundnode=false;
 314                 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
 315                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
 316                     GraphNode gn2=edge.getTarget();
 317                     if (!removed.contains(gn2)) {
 318                         TermNode tn2=(TermNode)gn2.getOwner();
 319                         if (tn2.getType()==TermNode.UPDATE) {
 320                             foundnode=true;
 321                             break;
 322                         }
 323                     }
 324                 }
 325                 if (!foundnode)
 326                     return ERR_ABSTRACT;
 327             } else throw new Error("Unanticipated Node");
 328         }
 329         return WORKS;
 330     }
 331     /* This method checks that all constraints have conjunction nodes
 332        and that there are no bad cycles in the abstract portion of the graph.
 333      */
 334     public int checkAbstract(Collection removed) {
 335         Vector constraints=termination.state.vConstraints;
 336         for(int i=0;i<constraints.size();i++) {
 337             Constraint c=(Constraint)constraints.get(i);
 338             Set conjunctionset=(Set)termination.conjunctionmap.get(c);
 339
 340             boolean foundrepair=false;
 341             for(Iterator it=conjunctionset.iterator();it.hasNext();) {
 342                 GraphNode gn=(GraphNode)it.next();
 343                 if (!removed.contains(gn)) {
 344                     foundrepair=true;
 345                 }
 346             }
 347             if (!foundrepair)
 348                 return ERR_NOREPAIR;
 349         }
 350         Set abstractnodes=new HashSet();
 351         abstractnodes.addAll(termination.conjunctions);
 352         abstractnodes.removeAll(removed);
 353         GraphNode.computeclosure(abstractnodes,removed);
 354
 355         Set tset=new HashSet();
 356         tset.addAll(termination.conjunctions);
 357         tset.addAll(termination.abstractrepair);
 358         tset.addAll(termination.scopenodes);
 359         tset.addAll(termination.consequencenodes);
 360         abstractnodes.retainAll(tset);
 361         Set cycles=GraphNode.findcycles(abstractnodes);
 362
 363         for(Iterator it=cycles.iterator();it.hasNext();) {
 364             GraphNode gn=(GraphNode)it.next();
 365             System.out.println("NODE: "+gn.getTextLabel());
 366             TermNode tn=(TermNode)gn.getOwner();
 367             switch(tn.getType()) {
 368             case TermNode.CONJUNCTION:
 369             case TermNode.ABSTRACT:
 370                 return ERR_CYCLE;
 371             case TermNode.UPDATE:
 372                 throw new Error("No Update Nodes should be here");
 373             default:
 374             }
 375         }
 376         return WORKS;
 377     }
 378 }