Repair/RepairCompiler/MCC/IR/ComputeMaxSize.java

   1 package MCC.IR;
   2 import MCC.State;
   3 import java.util.*;
   4
   5 /** This class computes the maximum size of sets and relations */
   6
   7 public class ComputeMaxSize {
   8     State state;
   9     Hashtable sizemap; /* -1 means infinity */
  10     static int KBOUND=100;
  11
  12     public ComputeMaxSize(State state) {
  13         this.state=state;
  14         sizemap=new Hashtable();
  15         computesizes();
  16         postprocess();
  17         printsizes();
  18     }
  19
  20     /** This method compute relation and set maximum sizes */
  21     private void computesizes() {
  22         Vector rules=state.vRules;
  23         boolean change=true;
  24         Set descriptorset=new HashSet();
  25         descriptorset.addAll(state.stSets.getAllDescriptors());
  26         descriptorset.addAll(state.stRelations.getAllDescriptors());
  27         while(change) {
  28             change=false;
  29             for(Iterator dit=descriptorset.iterator();dit.hasNext();) {
  30                 Descriptor d=(Descriptor)dit.next();
  31                 if (d instanceof ReservedSetDescriptor)
  32                     continue;
  33                 int totalstarts=0;
  34                 int totalchains=0;
  35                 Rule chainrule=null;
  36                 for(int i=0;i<rules.size();i++) {
  37                     Rule r=(Rule)rules.get(i);
  38                     if (r.getInclusion().getTargetDescriptors().contains(d)) {
  39                         /* This rule may add items to this set or relation */
  40                         int rulesize=1;
  41                         boolean start=true;
  42                         for(int j=0;j<r.numQuantifiers();j++) {
  43                             Quantifier q=r.getQuantifier(j);
  44                             int size=0;
  45                             if (q instanceof RelationQuantifier) {
  46                                 Descriptor d2=((RelationQuantifier)q).getRelation();
  47                                 if (sizemap.containsKey(d2)) {
  48                                     size=getsize(d2);
  49                                 }
  50                                 if (d==d2) {
  51                                     if (!start)
  52                                         size=-1;
  53                                     else
  54                                         size=1;
  55                                     start=false;
  56                                 }
  57                             } else if (q instanceof SetQuantifier) {
  58                                 Descriptor d2=((SetQuantifier)q).getSet();
  59                                 if (sizemap.containsKey(d2)) {
  60                                     size=getsize(d2);
  61                                 }
  62                                 if (d==d2) {
  63                                     if (!start)
  64                                         size=-1;
  65                                     else
  66                                         size=1;
  67                                     start=false;
  68                                 }
  69                             } else if (q instanceof ForQuantifier) {
  70                                 ForQuantifier fq=(ForQuantifier)q;
  71                                 boolean lowint=OpExpr.isInt(fq.lower);
  72                                 boolean highint=OpExpr.isInt(fq.upper);
  73                                 if (lowint&&highint) {
  74                                     size=1+OpExpr.getInt(fq.upper)-OpExpr.getInt(fq.lower);
  75                                     if (size<=0) /* Catch sneaky bounds */
  76                                         throw new Error("Funny bounds in: "+fq);
  77                                 } else size=-1;
  78                             } else
  79                                 throw new Error("Unrecognized Quantifier");
  80
  81                             if ((rulesize!=0)&&((size==-1)||(rulesize==-1)))
  82                                 rulesize=-1;
  83                             else
  84                                 rulesize=rulesize*size;
  85                         }
  86
  87                         if (start) {
  88                             if ((rulesize==-1)||(totalstarts==-1))
  89                                 totalstarts=-1;
  90                             else
  91                                 totalstarts+=rulesize;
  92                         } else {
  93                             if (totalchains==0)
  94                                 chainrule=r;
  95                             else
  96                                 chainrule=null;
  97                             if ((rulesize==-1)||(totalchains==-1))
  98                                 totalchains=-1;
  99                             else
 100                                 totalchains+=rulesize;
 101                         }
 102                     }
 103                 }
 104                 if (totalstarts>=KBOUND)
 105                     totalstarts=-1;
 106                 if (totalchains>=KBOUND)
 107                     totalchains=-1;
 108
 109                 if (!sizemap.containsKey(d)||getstarts(d)!=totalstarts||getchains(d)!=totalchains) {
 110                     change=true;
 111                     MaxSizeObject so=new MaxSizeObject(totalstarts,totalchains,chainrule);
 112                     sizemap.put(d,so);
 113                 }
 114             }
 115         }
 116     }
 117
 118     void printsizes() {
 119         Set descriptorset=new HashSet();
 120         descriptorset.addAll(state.stSets.getAllDescriptors());
 121         descriptorset.addAll(state.stRelations.getAllDescriptors());
 122         for(Iterator dit=descriptorset.iterator();dit.hasNext();) {
 123             Descriptor d=(Descriptor)dit.next();
 124             if (d instanceof ReservedSetDescriptor)
 125                 continue;
 126             System.out.println("size("+d+")="+getsize(d));
 127         }
 128     }
 129
 130     private void postprocess() {
 131         Vector rules=state.vRules;
 132         boolean change=true;
 133         Set descriptorset=new HashSet();
 134         descriptorset.addAll(state.stSets.getAllDescriptors());
 135         descriptorset.addAll(state.stRelations.getAllDescriptors());
 136         while(change) {
 137             change=false;
 138             for(Iterator dit=descriptorset.iterator();dit.hasNext();) {
 139                 Descriptor d=(Descriptor)dit.next();
 140                 if (d instanceof ReservedSetDescriptor)
 141                     continue;
 142                 int totalstarts=0;
 143                 int totalchains=0;
 144                 Rule chainrule=null;
 145                 for(int i=0;i<rules.size();i++) {
 146                     Rule r=(Rule)rules.get(i);
 147                     if (r.getInclusion().getTargetDescriptors().contains(d)) {
 148                         /* This rule may add items to this set or relation */
 149                         int rulesize=1;
 150                         boolean start=true;
 151                         for(int j=0;j<r.numQuantifiers();j++) {
 152                             Quantifier q=r.getQuantifier(j);
 153                             int size=0;
 154                             if (q instanceof RelationQuantifier) {
 155                                 Descriptor d2=((RelationQuantifier)q).getRelation();
 156                                 if (sizemap.containsKey(d2)) {
 157                                     size=getsize(d2);
 158                                 }
 159                                 if (d==d2) {
 160                                     if (!start)
 161                                         size=-1;
 162                                     else
 163                                         size=1;
 164                                     start=false;
 165                                 } else {
 166                                     if (getchainrule(d2)!=null) {
 167                                         if (isMutuallyExclusive(r, getchainrule(d2)))
 168                                             size=getstarts(d2);
 169                                     }
 170                                 }
 171                             } else if (q instanceof SetQuantifier) {
 172                                 Descriptor d2=((SetQuantifier)q).getSet();
 173                                 if (sizemap.containsKey(d2)) {
 174                                     size=getsize(d2);
 175                                 }
 176                                 if (d==d2) {
 177                                     if (!start)
 178                                         size=-1;
 179                                     else
 180                                         size=1;
 181                                     start=false;
 182                                 } else {
 183                                     if (getchainrule(d2)!=null) {
 184                                         if (isMutuallyExclusive(r, getchainrule(d2)))
 185                                             size=getstarts(d2);
 186                                     }
 187                                 }
 188                             } else if (q instanceof ForQuantifier) {
 189                                 ForQuantifier fq=(ForQuantifier)q;
 190                                 boolean lowint=OpExpr.isInt(fq.lower);
 191                                 boolean highint=OpExpr.isInt(fq.upper);
 192                                 if (lowint&&highint) {
 193                                     size=1+OpExpr.getInt(fq.upper)-OpExpr.getInt(fq.lower);
 194                                     if (size<=0) /* Catch sneaky bounds */
 195                                         throw new Error("Funny bounds in: "+fq);
 196                                 } else size=-1;
 197                             } else
 198                                 throw new Error("Unrecognized Quantifier");
 199
 200                             if ((rulesize!=0)&&((size==-1)||(rulesize==-1)))
 201                                 rulesize=-1;
 202                             else
 203                                 rulesize=rulesize*size;
 204                         }
 205
 206                         if (start) {
 207                             if ((rulesize==-1)||(totalstarts==-1))
 208                                 totalstarts=-1;
 209                             else
 210                                 totalstarts+=rulesize;
 211                         } else {
 212                             if (totalchains==0)
 213                                 chainrule=r;
 214                             else
 215                                 chainrule=null;
 216                             if ((rulesize==-1)||(totalchains==-1))
 217                                 totalchains=-1;
 218                             else
 219                                 totalchains+=rulesize;
 220                         }
 221                     }
 222                 }
 223                 if (totalstarts>=KBOUND)
 224                     totalstarts=-1;
 225                 if (totalchains>=KBOUND)
 226                     totalchains=-1;
 227
 228                 if (!sizemap.containsKey(d)||getstarts(d)!=totalstarts||getchains(d)!=totalchains) {
 229                     change=true;
 230                     MaxSizeObject so=new MaxSizeObject(totalstarts,totalchains,chainrule);
 231                     sizemap.put(d,so);
 232                 }
 233             }
 234         }
 235
 236     }
 237
 238     int getstarts(Descriptor d) {
 239         MaxSizeObject so=(MaxSizeObject)sizemap.get(d);
 240         return so.maxstarts;
 241     }
 242     int getchains(Descriptor d) {
 243         MaxSizeObject so=(MaxSizeObject)sizemap.get(d);
 244         return so.numberchains;
 245     }
 246     int getsize(Descriptor d) {
 247         MaxSizeObject so=(MaxSizeObject)sizemap.get(d);
 248         if (so.maxstarts==0)
 249             return 0;
 250         if (so.numberchains!=0)
 251             return -1;
 252         return so.maxstarts;
 253     }
 254
 255     private Rule getchainrule(Descriptor d) {
 256         MaxSizeObject so=(MaxSizeObject)sizemap.get(d);
 257         return so.chainrule;
 258     }
 259
 260     public static boolean isMutuallyExclusive(Rule r1,Rule r2) {
 261         // Building a map between quantifier variables
 262         if (r1.numQuantifiers()!=r2.numQuantifiers())
 263             return false;
 264         Set usedDescriptors=new HashSet();
 265         Hashtable varmap=new Hashtable();
 266
 267     outerloop:
 268         for(int i=0;i<r1.numQuantifiers();i++) {
 269             Quantifier q1=r1.getQuantifier(i);
 270             if (!(q1 instanceof SetQuantifier))
 271                 return false;
 272             if (usedDescriptors.contains(((SetQuantifier)q1).getSet()))
 273                 return false;
 274             usedDescriptors.add(((SetQuantifier)q1).getSet());
 275             for(int j=0;j<r2.numQuantifiers();j++) {
 276                 Quantifier q2=r2.getQuantifier(j);
 277                 if (!(q2 instanceof SetQuantifier))
 278                     return false;
 279                 if (((SetQuantifier)q1).getSet()==((SetQuantifier)q2).getSet()) {
 280                     varmap.put(((SetQuantifier)q1).getVar(),((SetQuantifier)q2).getVar());
 281                     continue outerloop;
 282                 }
 283             }
 284             return false;
 285         }
 286         DNFRule dr1=r1.getDNFGuardExpr();
 287         DNFRule dr2=r2.getDNFGuardExpr();
 288         for(int i=0;i<dr1.size();i++) {
 289             for(int j=0;j<dr2.size();j++) {
 290                 RuleConjunction rc1=dr1.get(i);
 291                 RuleConjunction rc2=dr2.get(j);
 292                 if (!exclusive(varmap,rc1,rc2))
 293                     return false;
 294             }
 295         }
 296         return true;
 297     }
 298
 299     private static boolean exclusive(Hashtable varmap, RuleConjunction rc1, RuleConjunction rc2) {
 300         for (int i=0;i<rc1.size();i++) {
 301             for (int j=0;j<rc2.size();j++) {
 302                 DNFExpr de1=rc1.get(i);
 303                 DNFExpr de2=rc2.get(j);
 304                 if ((de1.getNegation()!=de2.getNegation())&&
 305                     (de1.getExpr().equals(varmap,de2.getExpr())))
 306                     return true;
 307             }
 308         }
 309         return false;
 310     }
 311 }
 312 class MaxSizeObject {
 313     int maxstarts;
 314     int numberchains;
 315     Rule chainrule;
 316
 317     public MaxSizeObject(int start,int chain, Rule r) {
 318         maxstarts=start;
 319         numberchains=chain;
 320         chainrule=r;
 321     }
 322 }