001package daikon;
002
003import java.io.Serializable;
004import java.util.Arrays;
005import java.util.BitSet;
006import org.checkerframework.checker.initialization.qual.UnknownInitialization;
007import org.checkerframework.checker.nullness.qual.NonNull;
008import org.checkerframework.checker.nullness.qual.Nullable;
009import org.checkerframework.checker.signedness.qual.Signed;
010
011// "ModBitTracker" is a poor name for this class, since it tracks
012// whether a value is missing, not whether it is modified.
013/**
014 * ModBitTracker maintains a BitSet for each variable at a program point. The BitSet indicates, for
015 * each sample seen in order, whether that variable was present or not.
016 */
017public class ModBitTracker implements Serializable, Cloneable {
018  // We are Serializable, so we specify a version to allow changes to
019  // method signatures without breaking serialization.  If you add or
020  // remove fields, you should change this number to the current date.
021  static final long serialVersionUID = 20031014L;
022
023  // Should make this a configuration option.
024  private static boolean debug = false;
025
026  /** The maximum number of BitSets; the size of modbits_arrays. */
027  private int num_vars;
028
029  /** The size of each BitSet in modbits_arrays. */
030  private int num_samples;
031
032  /** The BitSets themselves. */
033  // In the future, I could imagine trying to optimize this with (say)
034  // run-length encoding; but it's probably not worth it.
035  // All elements of modbits_arrays at or past num_sets are null.
036  private @Nullable BitSet[] modbits_arrays;
037
038  /**
039   * Conceptually, there is a BitSet per variable. In actuality, when two different variables have
040   * the same modbits, they can share a single BitSet; we say the variables are in an equivalence
041   * set. "index" indicates, for each variable, which BitSet it should use; it is the identifier of
042   * the variable's equivalence set.
043   */
044  private int[] index;
045
046  /**
047   * The number of BitSets (equivalence sets) in use. All elements of modbits_arrays before this
048   * index are non-null, and all elements at or past this index are null.
049   */
050  private int num_sets;
051
052  // Member variables to avoid re-allocating every time "add" is entered.
053  /** The bits for this ValueTuple (indexed by equivalence set. */
054  private boolean[] this_bits;
055
056  /** True if the corresponding element of this_bits has a valid value. */
057  private boolean[] this_bits_valid;
058
059  /**
060   * The equivalence set for when an equivalence set is split: if a variable has a conflicting bit,
061   * then it goes to the specified index instead.
062   */
063  private int[] this_bits_exception_index;
064
065  /**
066   * Creates a ModBitTracker.
067   *
068   * @param num_vars number of variables to allocate space for
069   */
070  public ModBitTracker(int num_vars) {
071    assert num_vars >= 0;
072    this.num_vars = num_vars;
073    modbits_arrays = new @Nullable BitSet[num_vars];
074    if (num_vars > 0) {
075      modbits_arrays[0] = new BitSet();
076      num_sets = 1;
077    } else {
078      num_sets = 0;
079    }
080    num_samples = 0;
081    index = new int[num_vars];
082    this_bits = new boolean[num_vars];
083    this_bits_valid = new boolean[num_vars];
084    this_bits_exception_index = new int[num_vars];
085    if (debug) checkRep();
086  }
087
088  public int num_vars() {
089    return num_vars;
090  }
091
092  public int num_samples() {
093    return num_samples;
094  }
095
096  /** Accessor for testing only. */
097  public int num_sets() {
098    return num_sets;
099  }
100
101  /** Check the representation invariant. */
102  public void checkRep(@UnknownInitialization(ModBitTracker.class) ModBitTracker this) {
103    assert index.length == num_vars;
104    assert modbits_arrays.length == num_vars;
105    for (int i = 0; i < num_vars; i++) {
106      int this_index = index[i];
107      assert this_index >= 0;
108      assert this_index < num_sets;
109      assert modbits_arrays[this_index] != null;
110    }
111    for (int i = 0; i < num_vars; i++) {
112      if (i < num_sets) {
113        assert modbits_arrays[i] != null;
114        // Can't make this assertion, as there is no method that tells
115        // the highest index that has been used in the BitSet.  (size()
116        // gives physical size.)
117        // assert modbits_arrays[i].size() == num_samples
118        //                   : "modbits_arrays.[" + i + "].size() == "
119        //                   + modbits_arrays[i].size()
120        //                   + ", num_samples == " + num_samples;
121      } else {
122        assert modbits_arrays[i] == null;
123      }
124    }
125  }
126
127  /**
128   * Returns a BitSet of modbit values for the given variable. The caller must not modify the
129   * returned value!
130   */
131  @SuppressWarnings(
132      "nullness") // application invariant: index[varindex] is an index for a non-null BitSet in
133  // modbits_arrays
134  public BitSet get(int varindex) {
135    return modbits_arrays[index[varindex]];
136  }
137
138  /** Returns the modbit for the given variable and sample number. */
139  public boolean get(int varindex, int sampleno) {
140    return get(varindex).get(sampleno);
141  }
142
143  /**
144   * Split the specified equivalence set into two pieces. Returns the index of the copy.
145   *
146   * @param split_index where to split modbits_arrays
147   * @return the index of the copy
148   */
149  private int split(int split_index) {
150    @SuppressWarnings("nullness") // application invariant: split_index is in range
151    @NonNull BitSet bs = (BitSet) modbits_arrays[split_index].clone();
152    modbits_arrays[num_sets] = bs;
153    num_sets++;
154    return num_sets - 1;
155  }
156
157  /** Add to this the modbits for the given ValueTuple. */
158  public void add(ValueTuple vt, int count) {
159    if (debug) checkRep();
160    assert vt.size() == num_vars : "vt.size()=" + vt.size() + ", num_vars = " + num_vars;
161    if (num_vars == 0) {
162      num_samples += count;
163      return;
164    }
165    Arrays.fill(this_bits_valid, false);
166    Arrays.fill(this_bits_exception_index, (@Signed int) -1);
167    for (int i = 0; i < num_vars; i++) {
168      int this_index = index[i];
169      // Should this use the whole modbit, not just a boolean?
170      boolean modbit = !vt.isMissing(i);
171      if (!this_bits_valid[this_index]) {
172        // This is the first variable belonging to this equivalence set
173        // that we have seen so far.
174        this_bits[this_index] = modbit;
175        this_bits_valid[this_index] = true;
176        assert this_bits_exception_index[this_index] == -1;
177      } else {
178        // We have seen some other variable belonging to this equivalence set.
179        if (this_bits[this_index] == modbit) {
180          // This bit has the same value as we saw previously for its
181          // equivalence set.
182        } else {
183          // This bit has a different value than we have previously seen
184          // for its equivalence set.
185          if (this_bits_exception_index[this_index] == -1) {
186            // We have't previously seen an exception.
187            this_bits_exception_index[this_index] = split(this_index);
188          }
189          index[i] = this_bits_exception_index[this_index];
190          this_index = index[i];
191          this_bits[this_index] = modbit;
192          this_bits_valid[this_index] = true;
193        }
194      }
195    }
196    for (int i = 0; i < num_sets; i++) {
197      @SuppressWarnings("nullness") // application invariant: non-null up to index=num_sets
198      @NonNull BitSet bs = modbits_arrays[i];
199      bs.set(num_samples, num_samples + count, this_bits[i]);
200    }
201    num_samples += count;
202
203    if (debug) checkRep();
204  }
205}