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}