Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8
   9 public class ReachabilitySet extends Canonical {
  10
  11     private HashSet<TokenTupleSet> possibleReachabilities;
  12
  13     public ReachabilitySet() {
  14         possibleReachabilities = new HashSet<TokenTupleSet>();
  15         //TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
  16         //possibleReachabilities.add( ttsEmpty );
  17     }
  18
  19     public ReachabilitySet( TokenTupleSet tts ) {
  20         this();
  21         assert tts != null;
  22         possibleReachabilities.add( tts );
  23     }
  24
  25     public ReachabilitySet( TokenTuple tt ) {
  26         this( new TokenTupleSet( tt ).makeCanonical() );
  27     }
  28
  29     public ReachabilitySet( HashSet<TokenTupleSet> possibleReachabilities ) {
  30         this.possibleReachabilities = possibleReachabilities;
  31     }
  32
  33     public ReachabilitySet( ReachabilitySet rs ) {
  34         assert rs != null;
  35         possibleReachabilities = (HashSet<TokenTupleSet>) rs.possibleReachabilities.clone(); // again, DEEP COPY?!
  36     }
  37
  38     public ReachabilitySet makeCanonical() {
  39         return (ReachabilitySet) Canonical.makeCanonical( this );
  40     }
  41
  42     public boolean contains( TokenTupleSet tts ) {
  43         assert tts != null;
  44         return possibleReachabilities.contains( tts );
  45     }
  46
  47     public ReachabilitySet add( TokenTupleSet tts ) {
  48         ReachabilitySet rsOut = new ReachabilitySet( tts );
  49         return this.union( rsOut );
  50     }
  51
  52     public ReachabilitySet increaseArity( Integer token ) {
  53         assert token != null;
  54
  55         HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
  56
  57         Iterator itr = iterator();
  58         while( itr.hasNext() ) {
  59             TokenTupleSet tts = (TokenTupleSet) itr.next();
  60             possibleReachabilitiesNew.add( tts.increaseArity( token ) );
  61         }
  62
  63         return new ReachabilitySet( possibleReachabilitiesNew ).makeCanonical();
  64     }
  65
  66     public Iterator iterator() {
  67         return possibleReachabilities.iterator();
  68     }
  69
  70     public ReachabilitySet union( ReachabilitySet rsIn ) {
  71         assert rsIn != null;
  72
  73         ReachabilitySet rsOut = new ReachabilitySet( this );
  74         rsOut.possibleReachabilities.addAll( rsIn.possibleReachabilities );
  75         return rsOut.makeCanonical();
  76     }
  77
  78     public ReachabilitySet union( TokenTupleSet ttsIn ) {
  79         assert ttsIn != null;
  80
  81         ReachabilitySet rsOut = new ReachabilitySet( this );
  82         rsOut.possibleReachabilities.add( ttsIn );
  83         return rsOut.makeCanonical();
  84     }
  85
  86     public ReachabilitySet intersection( ReachabilitySet rsIn ) {
  87         assert rsIn != null;
  88
  89         ReachabilitySet rsOut = new ReachabilitySet();
  90
  91         Iterator i = this.iterator();
  92         while( i.hasNext() ) {
  93             TokenTupleSet tts = (TokenTupleSet) i.next();
  94             if( rsIn.possibleReachabilities.contains( tts ) ) {
  95                 rsOut.possibleReachabilities.add( tts );
  96             }
  97         }
  98
  99         return rsOut.makeCanonical();
 100     }
 101
 102     /*
 103     public ReachabilitySet unionUpArity( ReachabilitySet rsIn ) {
 104         assert rsIn != null;
 105
 106         ReachabilitySet rsOut = new ReachabilitySet();
 107         Iterator itrIn;
 108         Iterator itrThis;
 109
 110         itrIn = rsIn.iterator();
 111         while( itrIn.hasNext() ) {
 112             TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next();
 113
 114             boolean foundEqual = false;
 115
 116             itrThis = this.iterator();
 117             while( itrThis.hasNext() ) {
 118                 TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next();
 119
 120                 if( ttsIn.equalWithoutArity( ttsThis ) ) {
 121                     rsOut.possibleReachabilities.add( ttsIn.unionUpArity( ttsThis ) );
 122                     foundEqual = true;
 123                     continue;
 124                 }
 125             }
 126
 127             if( !foundEqual ) {
 128                 rsOut.possibleReachabilities.add( ttsIn );
 129             }
 130         }
 131
 132         itrThis = this.iterator();
 133         while( itrThis.hasNext() ) {
 134             TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next();
 135
 136             boolean foundEqual = false;
 137
 138             itrIn = rsIn.iterator();
 139             while( itrIn.hasNext() ) {
 140                 TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next();
 141
 142                 if( ttsThis.equalWithoutArity( ttsIn ) ) {
 143                     foundEqual = true;
 144                     continue;
 145                 }
 146             }
 147
 148             if( !foundEqual ) {
 149                 rsOut.possibleReachabilities.add( ttsThis );
 150             }
 151         }
 152
 153         return rsOut.makeCanonical();
 154     }
 155     */
 156
 157     public ChangeTupleSet unionUpArityToChangeSet( ReachabilitySet rsIn ) {
 158         assert rsIn != null;
 159
 160         ChangeTupleSet ctsOut = new ChangeTupleSet();
 161
 162         Iterator itrO = this.iterator();
 163         while( itrO.hasNext() ) {
 164             TokenTupleSet o = (TokenTupleSet) itrO.next();
 165
 166             Iterator itrR = rsIn.iterator();
 167             while( itrR.hasNext() ) {
 168                 TokenTupleSet r = (TokenTupleSet) itrR.next();
 169
 170                 TokenTupleSet theUnion = new TokenTupleSet();
 171
 172                 Iterator itrRelement = r.iterator();
 173                 while( itrRelement.hasNext() ) {
 174                     TokenTuple e = (TokenTuple) itrRelement.next();
 175
 176                     if( o.containsToken( e.getToken() ) ) {
 177                         theUnion = theUnion.union( new TokenTupleSet( e.increaseArity() ) ).makeCanonical();
 178                     } else {
 179                         theUnion = theUnion.union( new TokenTupleSet( e                 ) ).makeCanonical();
 180                     }
 181                 }
 182
 183                 Iterator itrOelement = o.iterator();
 184                 while( itrOelement.hasNext() ) {
 185                     TokenTuple e = (TokenTuple) itrOelement.next();
 186
 187                     if( !theUnion.containsToken( e.getToken() ) ) {
 188                         theUnion = theUnion.union( new TokenTupleSet( e ) ).makeCanonical();
 189                     }
 190                 }
 191
 192                 if( !theUnion.isEmpty() ) {
 193                     ctsOut = ctsOut.union(
 194                       new ChangeTupleSet( new ChangeTuple( o, theUnion ) )
 195                                           );
 196                 }
 197             }
 198         }
 199
 200         return ctsOut.makeCanonical();
 201     }
 202
 203
 204     public ReachabilitySet ageTokens( AllocationSite as ) {
 205         assert as != null;
 206
 207         ReachabilitySet rsOut = new ReachabilitySet();
 208
 209         Iterator itrS = this.iterator();
 210         while( itrS.hasNext() ) {
 211             TokenTupleSet tts = (TokenTupleSet) itrS.next();
 212             rsOut.possibleReachabilities.add( tts.ageTokens( as ) );
 213         }
 214
 215         return rsOut.makeCanonical();
 216     }
 217
 218
 219     public ReachabilitySet pruneBy( ReachabilitySet rsIn ) {
 220         assert rsIn != null;
 221
 222         ReachabilitySet rsOut = new ReachabilitySet();
 223
 224         Iterator itrB = this.iterator();
 225         while( itrB.hasNext() ) {
 226             TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
 227
 228             boolean subsetExists = false;
 229
 230             Iterator itrA = rsIn.iterator();
 231             while( itrA.hasNext() && !subsetExists ) {
 232                 TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
 233
 234                 if( ttsA.isSubset( ttsB ) ) {
 235                     subsetExists = true;
 236                     rsOut.possibleReachabilities.add( ttsB );
 237                 }
 238             }
 239         }
 240
 241         return rsOut.makeCanonical();
 242     }
 243
 244
 245     public boolean equals( Object o ) {
 246         if( !(o instanceof ReachabilitySet) ) {
 247             return false;
 248         }
 249
 250         ReachabilitySet rs = (ReachabilitySet) o;
 251         return possibleReachabilities.equals( rs.possibleReachabilities );
 252     }
 253
 254     public int hashCode() {
 255         return possibleReachabilities.hashCode();
 256     }
 257
 258
 259     public String toStringEscapeNewline() {
 260         String s = "[";
 261
 262         Iterator i = this.iterator();
 263         while( i.hasNext() ) {
 264             s += i.next();
 265             if( i.hasNext() ) {
 266                 s += "\\n";
 267             }
 268         }
 269
 270         s += "]";
 271         return s;
 272     }
 273
 274     public String toString() {
 275         String s = "[";
 276
 277         Iterator i = this.iterator();
 278         while( i.hasNext() ) {
 279             s += i.next();
 280             if( i.hasNext() ) {
 281                 s += "\n";
 282             }
 283         }
 284
 285         s += "]";
 286         return s;
 287     }
 288 }