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}