001package daikon; 002 003import java.io.Serializable; 004import java.util.Collection; 005import java.util.Collections; 006import java.util.Iterator; 007import java.util.LinkedHashMap; 008import java.util.List; 009import java.util.Map; 010import java.util.TreeSet; 011import org.checkerframework.checker.lock.qual.GuardSatisfied; 012import org.checkerframework.checker.nullness.qual.EnsuresNonNullIf; 013import org.checkerframework.checker.nullness.qual.KeyFor; 014import org.checkerframework.checker.nullness.qual.Nullable; 015import org.checkerframework.dataflow.qual.Pure; 016import org.checkerframework.dataflow.qual.SideEffectFree; 017import org.plumelib.util.CollectionsPlume; 018 019/** 020 * Maps from a program point name (a String) to a PptTopLevel. 021 * 022 * <p>This is the major data structure of Daikon. All the invariants can be found in it, and an 023 * {@code .inv} file contains (only) the serialized form of this object. 024 */ 025// Why doesn't this implement Map<String,PptTopLevel> or extend 026// LinkedHashMap<String,PptTopLevel>? 027public class PptMap implements Serializable { 028 /** If you add or remove fields, change this number to the current date. */ 029 static final long serialVersionUID = 20040921L; 030 031 /** The map that represents this PptMap. */ 032 @SuppressWarnings("serial") 033 private final Map<String, PptTopLevel> nameToPpt = new LinkedHashMap<>(); 034 035 public void add(PptTopLevel ppt) { 036 nameToPpt.put(ppt.name(), ppt); 037 } 038 039 public void addAll(List<PptTopLevel> ppts) { 040 for (PptTopLevel ppt : ppts) { 041 add(ppt); 042 } 043 } 044 045 /** 046 * Get the pptname named 'name' from the map. Note that conditional program points are not stored 047 * in the map by name. They are only available through their parent. 048 */ 049 @Pure 050 public @Nullable PptTopLevel get(String name) { 051 return nameToPpt.get(name); 052 } 053 054 /** 055 * Get the pptname 'name' from the map. Note that conditional program points are not stored in the 056 * map by name. They are only available through their parent. 057 */ 058 @Pure 059 public @Nullable PptTopLevel get(PptName name) { 060 return get(name.toString()); 061 } 062 063 /** 064 * Returns whether or not 'name' is the name of a Ppt in the map. Note that conditional program 065 * points are not stored in the map by name. They are only available through their parent. 066 */ 067 @Pure 068 @SuppressWarnings("nullness") // postcondition: linked maps 069 @EnsuresNonNullIf(result = true, expression = "get(#1)") 070 // get(#1) == nameToPpt.get(#1) 071 public boolean containsName(String name) { 072 return nameToPpt.containsKey(name); 073 } 074 075 /** Returns all of the program points in the map. */ 076 public Collection<PptTopLevel> all_ppts() { 077 return nameToPpt.values(); 078 } 079 080 /** 081 * Returns unstably-ordered collection of PptTopLevels. 082 * 083 * @return unstably-ordered collection of PptTopLevels 084 * @see #pptIterator() 085 */ 086 public Collection<PptTopLevel> asCollection() { 087 return Collections.unmodifiableCollection(nameToPpt.values()); 088 } 089 090 /** 091 * Returns an unmodifiable version of the keySet. 092 * 093 * @return an unmodifiable version of the keySet 094 */ 095 public Collection<@KeyFor("nameToPpt") String> nameStringSet() { 096 return Collections.unmodifiableSet(nameToPpt.keySet()); 097 } 098 099 /** 100 * Returns an iterator over the PptTopLevels in this, sorted by Ppt.NameComparator on their names. 101 * The sorting makes the iterator deterministic. 102 * 103 * <p>If you wish to merely iterate over the result in a foreach loop, use {@link #pptIterable()} 104 * instead. 105 * 106 * @return an iterator over the PptTopLevels in this, sorted by Ppt.NameComparator on their names 107 * @see #pptIterable() 108 */ 109 // See https://bugs.openjdk.java.net/browse/JDK-8195645 and 110 // https://bugs.openjdk.java.net/browse/JDK-8195646 111 @SuppressWarnings("lock") // JLS bug: can't write receiver annotation on method of anonymous class 112 public Iterator<PptTopLevel> pptIterator() { 113 TreeSet<PptTopLevel> sorted = new TreeSet<>(new Ppt.NameComparator()); 114 sorted.addAll(nameToPpt.values()); 115 // Use a (live) view iterator to get concurrent modification 116 // exceptions, and an iterator over sorted to get consistency. 117 final Iterator<PptTopLevel> iter_view = nameToPpt.values().iterator(); 118 final Iterator<PptTopLevel> iter_sort = sorted.iterator(); 119 return new Iterator<PptTopLevel>() { 120 @Override 121 public boolean hasNext(/*! >>>@GuardSatisfied Iterator<PptTopLevel> this*/ ) { 122 boolean result = iter_view.hasNext(); 123 assert result == iter_sort.hasNext(); 124 return result; 125 } 126 127 @Override 128 public PptTopLevel next(/*! >>>@GuardSatisfied Iterator<PptTopLevel> this*/ ) { 129 iter_view.next(); // to check for concurrent modifications 130 return iter_sort.next(); 131 } 132 133 @Override 134 public void remove(/*! >>>@GuardSatisfied Iterator<PptTopLevel> this*/ ) { 135 throw new UnsupportedOperationException(); 136 } 137 }; 138 } 139 140 /** 141 * Returns an iterable over the PptTopLevels in this, sorted by Ppt.NameComparator on their names. 142 * The sorting makes the iterator deterministic. 143 * 144 * <p>It is a wrapper around {@link #pptIterator()} that can be used in a foreach loop. 145 * 146 * @return an iterable over the PptTopLevels in this, sorted by Ppt.NameComparator on their names 147 * @see #pptIterator() 148 */ 149 public Iterable<PptTopLevel> pptIterable() { 150 return CollectionsPlume.iteratorToIterable(pptIterator()); 151 } 152 153 /** 154 * Returns an iterator over the PptTopLevels in this, sorted by Ppt.NameComparator on their names. 155 * This differs from pptIterator() in that it includes all ppts (including conditional ppts). 156 * 157 * <p>If you wish to merely iterate over the result in a Java new-style for loop ("foreach loop"), 158 * use {@link #ppt_all_iterable()} instead. 159 * 160 * @return an iterator over the PptTopLevels in this, sorted by Ppt.NameComparator on their names 161 * @see #ppt_all_iterable() 162 */ 163 // See https://bugs.openjdk.java.net/browse/JDK-8195645 and 164 // https://bugs.openjdk.java.net/browse/JDK-8195646 165 @SuppressWarnings("lock") // JLS bug: can't write receiver annotation on method of anonymous class 166 public Iterator<PptTopLevel> ppt_all_iterator() { 167 TreeSet<PptTopLevel> sorted = new TreeSet<>(new Ppt.NameComparator()); 168 sorted.addAll(nameToPpt.values()); 169 // Use a (live) view iterator to get concurrent modification 170 // exceptions, and an iterator over sorted to get consistency. 171 final Iterator<PptTopLevel> iter_view = nameToPpt.values().iterator(); 172 final Iterator<PptTopLevel> iter_sort = sorted.iterator(); 173 return new Iterator<PptTopLevel>() { 174 @Nullable Iterator<PptConditional> cond_iterator = null; 175 176 @Override 177 public boolean hasNext(/*! >>>@GuardSatisfied Iterator<PptConditional> this*/ ) { 178 if ((cond_iterator != null) && cond_iterator.hasNext()) { 179 return true; 180 } 181 boolean result = iter_view.hasNext(); 182 assert result == iter_sort.hasNext(); 183 return result; 184 } 185 186 @Override 187 public PptTopLevel next(/*! >>>@GuardSatisfied Iterator<PptTopLevel> this*/ ) { 188 if ((cond_iterator != null) && cond_iterator.hasNext()) { 189 return cond_iterator.next(); 190 } 191 iter_view.next(); // to check for concurrent modifications 192 PptTopLevel ppt = iter_sort.next(); 193 if ((ppt != null) && ppt.has_splitters()) cond_iterator = ppt.cond_iterator(); 194 return ppt; 195 } 196 197 @Override 198 public void remove(/*! >>>@GuardSatisfied Iterator<PptTopLevel> this*/ ) { 199 throw new UnsupportedOperationException(); 200 } 201 }; 202 } 203 204 /** 205 * Returns an iterable over the PptTopLevels in this, sorted by Ppt.NameComparator on their names. 206 * This differs from pptIterable() in that it includes all ppts (including conditional ppts). 207 * 208 * <p>It is a wrapper around {@link #ppt_all_iterator()} that can be used in a Java new-style for 209 * loop ("foreach loop"). 210 * 211 * @return an iterable over the PptTopLevels in this, sorted by Ppt.NameComparator on their names 212 * @see #ppt_all_iterator() 213 */ 214 public Iterable<PptTopLevel> ppt_all_iterable() { 215 return CollectionsPlume.iteratorToIterable(ppt_all_iterator()); 216 } 217 218 /** Iterate over the PptTopLevels and trim them. */ 219 public void trimToSize() { 220 for (PptTopLevel ppt : nameToPpt.values()) { 221 ppt.trimToSize(); 222 } 223 } 224 225 /** Check the rep invariant of this. Throws an Error if incorrect. */ 226 public void repCheck() { 227 for (PptTopLevel ppt : this.pptIterable()) { 228 ppt.repCheck(); 229 } 230 } 231 232 /** Return the number of active PptSlices. */ 233 @Pure 234 public int countSlices() { 235 int result = 0; 236 for (PptTopLevel ppt : this.pptIterable()) { 237 result += ppt.numViews(); 238 } 239 return result; 240 } 241 242 @Pure 243 public int size() { 244 return nameToPpt.size(); 245 } 246 247 @SideEffectFree 248 @Override 249 public String toString(@GuardSatisfied PptMap this) { 250 return "PptMap: " + nameToPpt.toString(); 251 } 252 253 /** Blow away any PptTopLevels that never saw any samples (to reclaim space). */ 254 public void removeUnsampled() { 255 Iterator<PptTopLevel> iter = nameToPpt.values().iterator(); 256 while (iter.hasNext()) { 257 PptTopLevel ppt = iter.next(); 258 if ((ppt.num_samples() == 0) && !FileIO.has_unmatched_procedure_entry(ppt)) iter.remove(); 259 } 260 } 261}