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()) {
194          cond_iterator = ppt.cond_iterator();
195        }
196        return ppt;
197      }
198
199      @Override
200      public void remove(/*! >>>@GuardSatisfied Iterator<PptTopLevel> this*/ ) {
201        throw new UnsupportedOperationException();
202      }
203    };
204  }
205
206  /**
207   * Returns an iterable over the PptTopLevels in this, sorted by Ppt.NameComparator on their names.
208   * This differs from pptIterable() in that it includes all ppts (including conditional ppts).
209   *
210   * <p>It is a wrapper around {@link #ppt_all_iterator()} that can be used in a Java new-style for
211   * loop ("foreach loop").
212   *
213   * @return an iterable over the PptTopLevels in this, sorted by Ppt.NameComparator on their names
214   * @see #ppt_all_iterator()
215   */
216  public Iterable<PptTopLevel> ppt_all_iterable() {
217    return CollectionsPlume.iteratorToIterable(ppt_all_iterator());
218  }
219
220  /** Iterate over the PptTopLevels and trim them. */
221  public void trimToSize() {
222    for (PptTopLevel ppt : nameToPpt.values()) {
223      ppt.trimToSize();
224    }
225  }
226
227  /** Check the rep invariant of this. Throws an Error if incorrect. */
228  public void repCheck() {
229    for (PptTopLevel ppt : this.pptIterable()) {
230      ppt.repCheck();
231    }
232  }
233
234  /** Return the number of active PptSlices. */
235  @Pure
236  public int countSlices() {
237    int result = 0;
238    for (PptTopLevel ppt : this.pptIterable()) {
239      result += ppt.numViews();
240    }
241    return result;
242  }
243
244  @Pure
245  public int size() {
246    return nameToPpt.size();
247  }
248
249  @SideEffectFree
250  @Override
251  public String toString(@GuardSatisfied PptMap this) {
252    return "PptMap: " + nameToPpt.toString();
253  }
254
255  /** Blow away any PptTopLevels that never saw any samples (to reclaim space). */
256  public void removeUnsampled() {
257    Iterator<PptTopLevel> iter = nameToPpt.values().iterator();
258    while (iter.hasNext()) {
259      PptTopLevel ppt = iter.next();
260      if ((ppt.num_samples() == 0) && !FileIO.has_unmatched_procedure_entry(ppt)) {
261        iter.remove();
262      }
263    }
264  }
265}