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