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