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                 if (!cantremove.contains(gn)) {
 122                     cantremove.add(gn);
 123                     Set cycle=GraphNode.findcycles(cantremove);
 124                     if (cycle.contains(gn)) {
 125                         if (!mustremove.contains(gn)) {
 126                             change=true;
 127                             mustremove.add(gn);
 128                         }
 129                     }
 130                     cantremove.remove(gn);
 131                 }
 132             }
 133             couldremove.removeAll(mustremove);
 134             couldremove.removeAll(cantremove);
 135
 136             Vector couldremovevector=new Vector();
 137             couldremovevector.addAll(couldremove);
 138             Vector combination=new Vector();
 139             if(change)
 140                 continue; //recalculate
 141
 142             System.out.println("Searching set of "+couldremove.size()+" nodes.");
 143             System.out.println("Eliminated "+mustremove.size()+" nodes");
 144             System.out.println("Searching following set:");
 145             for(Iterator it=couldremove.iterator();it.hasNext();) {
 146                 GraphNode gn=(GraphNode)it.next();
 147                 System.out.println(gn.getTextLabel());
 148             }
 149
 150
 151             while(true) {
 152                 if (illegal(combination,couldremovevector))
 153                     break;
 154                 Set combinationset=buildset(combination,couldremovevector);
 155                 combinationset.addAll(mustremove);
 156                 if (combinationset!=null) {
 157                     System.out.println("Checkabstract="+checkAbstract(combinationset));
 158                     System.out.println("Checkrepairs="+checkRepairs(combinationset));
 159                     System.out.println("Checkall="+checkAll(combinationset));
 160
 161                     if (checkAbstract(combinationset)==0&&
 162                         checkRepairs(combinationset)==0&&
 163                         checkAll(combinationset)==0) {
 164                         return combinationset;
 165                     }
 166                 }
 167                 increment(combination,couldremovevector);
 168             }
 169             return null;
 170         }
 171     }
 172
 173     private static Set buildset(Vector combination, Vector couldremove) {
 174         Set s=new HashSet();
 175         for(int i=0;i<combination.size();i++) {
 176             int index=((Integer)combination.get(i)).intValue();
 177             Object o=couldremove.get(index);
 178             if (s.contains(o))
 179                 return null;
 180             else
 181                 s.add(o);
 182         }
 183         return s;
 184     }
 185
 186     private static boolean illegal(Vector combination, Vector couldremove) {
 187         if (combination.size()>couldremove.size())
 188             return true;
 189         else return false;
 190     }
 191     private static void increment(Vector combination, Vector couldremove) {
 192         boolean incremented=false;
 193         boolean forcereset=false;
 194         for(int i=0;i<combination.size();i++) {
 195             int newindex=((Integer)combination.get(i)).intValue()+1;
 196             if (newindex==couldremove.size()||forcereset) {
 197                 forcereset=false;
 198                 if ((i+1)==combination.size()) {
 199                     newindex=1;
 200                 } else
 201                     newindex=((Integer)combination.get(i+1)).intValue()+2;
 202                 for(int j=i;j>=0;j--) {
 203                     combination.set(j,new Integer(newindex));
 204                     newindex++;
 205                 }
 206                 if (newindex>couldremove.size())
 207                     forcereset=true;
 208             } else {
 209                 incremented=true;
 210                 combination.set(i,new Integer(newindex));
 211                 break;
 212             }
 213         }
 214         if (incremented==false) /* Increase length */ {
 215             combination.add(new Integer(0));
 216             System.out.println("Expanding to :"+combination.size());
 217         }
 218     }
 219
 220     /* This function checks the graph as a whole for bad cycles */
 221     public int checkAll(Collection removed) {
 222         Set nodes=new HashSet();
 223         nodes.addAll(termination.conjunctions);
 224         nodes.removeAll(removed);
 225         GraphNode.computeclosure(nodes,removed);
 226         Set cycles=GraphNode.findcycles(nodes);
 227         for(Iterator it=cycles.iterator();it.hasNext();) {
 228             GraphNode gn=(GraphNode)it.next();
 229             TermNode tn=(TermNode)gn.getOwner();
 230             switch(tn.getType()) {
 231             case TermNode.UPDATE:
 232             case TermNode.CONJUNCTION:
 233                 return ERR_CYCLE;
 234             case TermNode.ABSTRACT:
 235             case TermNode.RULESCOPE:
 236             case TermNode.CONSEQUENCE:
 237             default:
 238                 break;
 239             }
 240         }
 241         return WORKS;
 242     }
 243
 244     /* This function checks that
 245        1) All abstract repairs have a corresponding data structure update
 246           that isn't removed.
 247        2) All scope nodes have either a consequence node or a compensation
 248           node that isn't removed.
 249      */
 250     public int checkRepairs(Collection removed) {
 251         Set nodes=new HashSet();
 252         nodes.addAll(termination.conjunctions);
 253         nodes.removeAll(removed);
 254         GraphNode.computeclosure(nodes,removed);
 255         Set toretain=new HashSet();
 256         toretain.addAll(termination.abstractrepair);
 257         toretain.addAll(termination.scopenodes);
 258         nodes.retainAll(toretain);
 259         /* Nodes is now the reachable set of abstractrepairs */
 260         /* Check to see that each has an implementation */
 261         for(Iterator it=nodes.iterator();it.hasNext();) {
 262             GraphNode gn=(GraphNode)it.next();
 263             TermNode tn=(TermNode)gn.getOwner();
 264             if (tn.getType()==TermNode.RULESCOPE) {
 265                 boolean foundnode=false;
 266                 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
 267                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
 268                     GraphNode gn2=edge.getTarget();
 269                     if (!removed.contains(gn2)) {
 270                         TermNode tn2=(TermNode)gn2.getOwner();
 271                         if ((tn2.getType()==TermNode.CONSEQUENCE)||
 272                             (tn2.getType()==TermNode.UPDATE)) {
 273                             foundnode=true;
 274                             break;
 275                         }
 276                     }
 277                 }
 278                 if (!foundnode) {
 279                     System.out.println(gn.getTextLabel());
 280                     return ERR_RULE;
 281                 }
 282             } else if (tn.getType()==TermNode.ABSTRACT) {
 283                 boolean foundnode=false;
 284                 for (Iterator edgeit=gn.edges();edgeit.hasNext();) {
 285                     GraphNode.Edge edge=(GraphNode.Edge)edgeit.next();
 286                     GraphNode gn2=edge.getTarget();
 287                     if (!removed.contains(gn2)) {
 288                         TermNode tn2=(TermNode)gn2.getOwner();
 289                         if (tn2.getType()==TermNode.UPDATE) {
 290                             foundnode=true;
 291                             break;
 292                         }
 293                     }
 294                 }
 295                 if (!foundnode)
 296                     return ERR_ABSTRACT;
 297             } else throw new Error("Unanticipated Node");
 298         }
 299         return WORKS;
 300     }
 301     /* This method checks that all constraints have conjunction nodes
 302        and that there are no bad cycles in the abstract portion of the graph.
 303      */
 304     public int checkAbstract(Collection removed) {
 305         Vector constraints=termination.state.vConstraints;
 306         for(int i=0;i<constraints.size();i++) {
 307             Constraint c=(Constraint)constraints.get(i);
 308             Set conjunctionset=(Set)termination.conjunctionmap.get(c);
 309
 310             boolean foundrepair=false;
 311             for(Iterator it=conjunctionset.iterator();it.hasNext();) {
 312                 GraphNode gn=(GraphNode)it.next();
 313                 if (!removed.contains(gn)) {
 314                     foundrepair=true;
 315                 }
 316             }
 317             if (!foundrepair)
 318                 return ERR_NOREPAIR;
 319         }
 320         Set abstractnodes=new HashSet();
 321         abstractnodes.addAll(termination.conjunctions);
 322         abstractnodes.removeAll(removed);
 323         GraphNode.computeclosure(abstractnodes,removed);
 324
 325         Set tset=new HashSet();
 326         tset.addAll(termination.conjunctions);
 327         tset.addAll(termination.abstractrepair);
 328         tset.addAll(termination.scopenodes);
 329         tset.addAll(termination.consequencenodes);
 330         abstractnodes.retainAll(tset);
 331         Set cycles=GraphNode.findcycles(abstractnodes);
 332
 333         for(Iterator it=cycles.iterator();it.hasNext();) {
 334             GraphNode gn=(GraphNode)it.next();
 335             System.out.println("NODE: "+gn.getTextLabel());
 336             TermNode tn=(TermNode)gn.getOwner();
 337             switch(tn.getType()) {
 338             case TermNode.CONJUNCTION:
 339             case TermNode.ABSTRACT:
 340                 return ERR_CYCLE;
 341             case TermNode.UPDATE:
 342                 throw new Error("No Update Nodes should be here");
 343             default:
 344             }
 345         }
 346         return WORKS;
 347     }
 348 }