001 package daikon;
002
003 import daikon.derive.*;
004
005 import java.util.logging.Logger;
006
007 import java.util.*;
008
009 import utilMDE.*;
010
011
012 /**
013 * This data structure holds a tuple of values for a particular program
014 * point. VarInfo objects can use this to get the values of the variables
015 * they represent.
016 * <p>
017 *
018 * It has two fields: vals and mods.
019 * While the arrays and their elements are interned, the ValueTuple objects
020 * themselves are not interned.
021 **/
022 public final class ValueTuple implements Cloneable {
023
024 /** Debug tracer. **/
025 public static Logger debug = Logger.getLogger("daikon.ValueTuple");
026
027 // These arrays are interned, and so are their elements.
028 // Each element is null only if it is missing (according to the mods array).
029 public /*@Nullable*/ /*@Interned*/ Object /*@Interned*/ [] vals;
030
031 // Could consider putting this in the first slot of "vals", to avoid the
032 // Object overhead of a pair of val and mods.
033
034 /**
035 * Modification bit per value, possibly packed into fewer ints than the
036 * vals field. Don't use a single int because that won't scale to (say)
037 * more than 16 values.
038 **/
039 public int /*@Interned*/ [] mods;
040
041
042 // Right now there are only three meaningful values for a mod:
043 /** Not modified. **/
044 public static final int UNMODIFIED = 0;
045 /** Modified. **/
046 public static final int MODIFIED = 1;
047 /** Missing value because the expression doesn't make sense: x.a
048 * when x is null. Data trace files can contain this modbit. **/
049 public static final int MISSING_NONSENSICAL = 2;
050 /** Missing value because of data flow: this.x.x isn't available
051 * from a ppt. Data trace files must not contain this modbit. **/
052 public static final int MISSING_FLOW = 3;
053 /** Maximum mod bit value. Always set to 1+ last modbit value. **/
054 public static final int MODBIT_VALUES = 4;
055 // Out of the range of MODBIT_VALUES because this won't appear in the
056 // tables; it gets converted to UNMODIFIED or MODIFIED, depending on
057 // whether this is the first sample. (Not sure whether that is the right
058 // strategy in the long term; it does let me avoid changing code in the
059 // short term.)
060 public static final int STATIC_CONSTANT = 22;
061
062 // Implementation for unpacked representation.
063 // (An alternate representation would pack the mod values into fewer ints
064 // than the vals field.)
065
066 public int getModified(VarInfo vi) { return vi.getModified(this); }
067 public boolean isUnmodified(VarInfo vi) { return vi.isUnmodified(this); }
068 public boolean isModified(VarInfo vi) { return vi.isModified(this); }
069 public boolean isMissingNonsensical(VarInfo vi) { return vi.isMissingNonsensical(this); }
070 public boolean isMissingFlow(VarInfo vi) { return vi.isMissingFlow(this); }
071 public boolean isMissing(VarInfo vi) { return vi.isMissing(this); }
072
073 int getModified(int value_index) { return mods[value_index]; }
074 boolean isUnmodified(int value_index) { return mods[value_index] == UNMODIFIED; }
075 boolean isModified(int value_index) { return mods[value_index] == MODIFIED; }
076 boolean isMissingNonsensical(int value_index) { return mods[value_index] == MISSING_NONSENSICAL; }
077 boolean isMissingFlow(int value_index) { return mods[value_index] == MISSING_FLOW; }
078 boolean isMissing(int value_index) { return (isMissingNonsensical(value_index)
079 || isMissingFlow(value_index)); }
080
081 // The arguments ints represent modification information.
082 static boolean modIsUnmodified(int mod_value) { return mod_value == UNMODIFIED; }
083 static boolean modIsModified(int mod_value) { return mod_value == MODIFIED; }
084 static boolean modIsMissingNonsensical(int mod_value) { return mod_value == MISSING_NONSENSICAL; }
085 static boolean modIsMissingFlow(int mod_value) { return mod_value == MISSING_FLOW; }
086
087 // A tuplemod is summary modification information about the whole tuple
088 // rather than about specific elements of the tuple.
089 // There are two potentially useful abstractions for mod bits over an
090 // entire tuple in aggregate:
091 // * return missing if any is missing (good for slices;
092 // indicates that we can't use that value)
093 // * return missing is all are missing (good for non-slices;
094 // the number that are guaranteed to be missing in slices
095 // The same thing can be argued about "unmodified", actually.
096 // So there are 8 states corresponding to 3 booleans:
097 // modified, unmodified, missing
098 // * has modified, has unmodified, has missing
099 // * has modified, has unmodified, no missing
100 // * has modified, no unmodified, has missing
101 // * has modified, no unmodified, no missing
102 // ie, all modified
103 // * no modified, has unmodified, has missing
104 // * no modified, has unmodified, no missing
105 // ie, all unmodified
106 // * no modified, no unmodified, has missing
107 // ie, all missing; probably impossible
108 // * no modified, no unmodified, no missing
109 // impossible
110
111 public static final int TUPLEMOD_VALUES = MathMDE.pow(2, MODBIT_VALUES);
112 public static final int UNMODIFIED_BITVAL = MathMDE.pow(2, UNMODIFIED);
113 public static final int MODIFIED_BITVAL = MathMDE.pow(2, MODIFIED);
114 public static final int MISSING_NONSENSICAL_BITVAL = MathMDE.pow(2, MISSING_NONSENSICAL);
115 public static final int MISSING_FLOW_BITVAL = MathMDE.pow(2, MISSING_FLOW);
116 // Various slices of the 8 (=TUPLEMOD_VALUES) possible tuplemod values.
117 // The arrays are filled up in a static block below.
118 // (As of 1/9/2000, tuplemod_modified_not_missing is used only in
119 // num_mod_samples(), and tuplemod_not_missing is not used.)
120 public static final int[] tuplemod_not_missing = new int[TUPLEMOD_VALUES/2];
121 public static final int[] tuplemod_modified_not_missing = new int[TUPLEMOD_VALUES/4];
122
123 static {
124 int i1 = 0, i2 = 0;
125 for (int tm=0; tm<TUPLEMOD_VALUES; tm++) {
126 if (!tuplemodHasMissingFlow(tm) && !tuplemodHasMissingNonsensical(tm) ) {
127 tuplemod_not_missing[i1] = tm;
128 i1++;
129 }
130 if (tuplemodHasModified(tm) && !tuplemodHasMissingFlow(tm) && !tuplemodHasMissingNonsensical(tm)) {
131 tuplemod_modified_not_missing[i2] = tm;
132 i2++;
133 }
134 }
135 }
136
137 static int make_tuplemod(boolean unmodified, boolean modified, boolean missingNonsensical, boolean missingFlow) {
138 int result = 0;
139 if (unmodified) result += UNMODIFIED_BITVAL;
140 if (modified) result += MODIFIED_BITVAL;
141 if (missingNonsensical) result += MISSING_NONSENSICAL_BITVAL;
142 if (missingFlow) result += MISSING_FLOW_BITVAL;
143 return result;
144 }
145
146 static boolean tuplemodHasModified(int tuplemod) {
147 return ((tuplemod & MODIFIED_BITVAL) != 0);
148 }
149 static boolean tuplemodHasUnmodified(int tuplemod) {
150 return ((tuplemod & UNMODIFIED_BITVAL) != 0);
151 }
152 static boolean tuplemodHasMissingNonsensical(int tuplemod) {
153 return ((tuplemod & MISSING_NONSENSICAL_BITVAL) != 0);
154 }
155
156 static boolean tuplemodHasMissingFlow(int tuplemod) {
157 return ((tuplemod & MISSING_FLOW_BITVAL) != 0);
158 }
159
160 /**
161 * In output, M=modified, U=unmodified, X=missing.
162 * Capital letters indicate the specified modbit does occur,
163 * lowercase letters indicate it does not occur.
164 **/
165 static String tuplemodToStringBrief(int tuplemod) {
166 return ((tuplemodHasModified(tuplemod) ? "M" : "m")
167 + (tuplemodHasUnmodified(tuplemod) ? "U" : "u")
168 + (tuplemodHasMissingNonsensical(tuplemod) ? "X" : "x")
169 + (tuplemodHasMissingFlow(tuplemod) ? "F" : "f"));
170 }
171
172
173 static int tupleMod(int[] mods) {
174 boolean[] has_modbit_val = new boolean[MODBIT_VALUES];
175 // Extraneous, as the array is initialized to all zeroes.
176 Arrays.fill(has_modbit_val, false);
177 for (int i=0; i<mods.length; i++) {
178 has_modbit_val[mods[i]] = true;
179 }
180 return make_tuplemod(has_modbit_val[UNMODIFIED],
181 has_modbit_val[MODIFIED],
182 has_modbit_val[MISSING_NONSENSICAL],
183 has_modbit_val[MISSING_FLOW]);
184 }
185
186 int tupleMod() {
187 return ValueTuple.tupleMod(mods);
188 }
189
190 public static int parseModified(String raw) {
191 int result = Integer.parseInt(raw);
192 assert (result >= 0) && (result < MODBIT_VALUES);
193 return result;
194 }
195
196
197 /**
198 * Get the value of the variable vi in this ValueTuple.
199 * @param vi the variable whose value is to be returned
200 * @return the value of the variable at this ValueTuple
201 **/
202 public /*@Interned*/ Object getValue(VarInfo vi) {
203 assert vi.value_index < vals.length : vi;
204 return vi.getValue(this);
205 }
206
207 /**
208 * Get the value of the variable vi in this ValueTuple, or null if it is missing.
209 * Use of this method is discouraged.
210 * @param vi the variable whose value is to be returned
211 * @return the value of the variable at this ValueTuple
212 * @see #getValue(VarInfo)
213 **/
214 public /*@Nullable*/ /*@Interned*/ Object getValueOrNull(VarInfo vi) {
215 assert vi.value_index < vals.length : vi;
216 return vi.getValueOrNull(this);
217 }
218
219 /**
220 * Get the value at the val_index, which should not have a missing value.
221 * Note: For clients, getValue(VarInfo) is preferred to getValue(int).
222 * @see #getValue(VarInfo)
223 **/
224 /*@Interned*/ Object getValue(int val_index) {
225 Object result = vals[val_index];
226 assert result != null;
227 return result;
228 }
229
230 /**
231 * Get the value at the val_index, or null if it is missing.
232 * Use of this method is (doubly) discouraged.
233 * @see #getValue(int)
234 **/
235 /*@Nullable*/ /*@Interned*/ Object getValueOrNull(int val_index) {
236 Object result = vals[val_index];
237 return result;
238 }
239
240 public void checkRep() {
241 assert vals.length == mods.length;
242 for (int i=0; i<vals.length; i++) {
243 assert 0 <= mods[i] && mods[i] < MODBIT_VALUES;
244 assert (isMissing(i) ? vals[i] == null : true);
245 }
246 }
247
248
249 /** Default constructor that interns its argument. */
250 public ValueTuple(/*@Nullable*/ /*@Interned*/ Object[] vals, int[] mods) {
251 this.vals = Intern.intern(vals);
252 this.mods = Intern.intern(mods);
253 checkRep();
254 }
255
256 // Private constructor that doesn't perform interning.
257 @SuppressWarnings("interning") // interning constructor
258 private ValueTuple(/*@Nullable*/ Object[] vals, int[] mods, boolean check) {
259 assert (!check) || Intern.isInterned(vals);
260 assert (!check) || Intern.isInterned(mods);
261 this.vals = vals;
262 this.mods = mods;
263 checkRep();
264 }
265
266 /** Creates and returns a copy of this. **/
267 // Default implementation to quiet Findbugs.
268 public ValueTuple clone() throws CloneNotSupportedException {
269 return (ValueTuple) super.clone();
270 }
271
272 /**
273 * More convenient name for the constructor that doesn't intern.
274 * That is, the result is an <b>uninterned</b> ValueTuple.
275 *
276 * This is not private because it is used (only) by read_data_trace_file,
277 * which makes a partial ValueTuple, fills it in with derived variables,
278 * and only then interns it; the alternative would be for derived
279 * variables to take separate vals and mods arguments. No one else
280 * should use it!
281 **/
282 @SuppressWarnings("interning") // interning constructor
283 public static ValueTuple makeUninterned(/*@Nullable*/ Object[] vals, int[] mods) {
284 return new ValueTuple(vals, mods, false);
285 }
286
287
288 /** Constructor that takes already-interned arguments. */
289 static ValueTuple makeFromInterned(/*@Nullable*/ /*@Interned*/ Object /*@Interned*/ [] vals, int[] mods) {
290 return new ValueTuple(vals, mods, true);
291 }
292
293
294 // Like clone(), but avoids its problems of default access and returning
295 // an Object.
296 public ValueTuple shallowcopy() {
297 return ValueTuple.makeFromInterned(vals, mods);
298 }
299
300 // These definitions are intended to make different ValueTuples with the
301 // same contents compare identically.
302 public boolean equals(/*@Nullable*/ Object obj) {
303 if (! (obj instanceof ValueTuple))
304 return false;
305 ValueTuple other = (ValueTuple) obj;
306 return (vals == other.vals) && (mods == other.mods);
307 }
308 public int hashCode() {
309 return vals.hashCode() * 31 + mods.hashCode();
310 }
311
312
313 public int size() {
314 assert vals.length == mods.length
315 : "vals = " + vals + " mods = " + mods;
316 return vals.length;
317 }
318
319 /** Return a new ValueTuple containing this one's first len elements. **/
320 public ValueTuple trim(int len) {
321 // @SuppressWarnings({"interning","nullness"}) // XXX checker bug with polymorphism
322 /*@Nullable*/ /*@Interned*/ Object[] new_vals = ArraysMDE.subarray(vals, 0, len);
323 int[] new_mods = ArraysMDE.subarray(mods, 0, len);
324 return new ValueTuple(new_vals, new_mods);
325 }
326
327
328 public String toString() {
329 return toString(null);
330 }
331
332 /**
333 * Return the values of this tuple.
334 * If vis is non-null, the values are annotated with the VarInfo name that
335 * would be associated with the value.
336 **/
337 // @SuppressWarnings("nullness")
338 public String toString(VarInfo /*@Nullable*/ [] vis) {
339 StringBuffer sb = new StringBuffer("[");
340 assert vals.length == mods.length;
341 assert vis == null || vals.length == vis.length;
342 for (int i=0; i<vals.length; i++) {
343 if (i>0)
344 sb.append("; ");
345 if (vis != null) {
346 sb.append (vis[i].name() + "=");
347 }
348 Object val = vals[i];
349 int mod = mods[i];
350 switch (mod) {
351 case UNMODIFIED:
352 case MODIFIED:
353 if (val instanceof String)
354 sb.append("\"" + val + "\"");
355 else if (val instanceof long[])
356 sb.append(ArraysMDE.toString((long[])val));
357 else if (val instanceof int[])
358 // shouldn't reach this case -- should be long[], not int[]
359 // sb.append(ArraysMDE.toString((int[])val));
360 throw new Error("should be long[], not int[]");
361 else if (val instanceof double[])
362 sb.append(ArraysMDE.toString ((double[])val));
363 else if (val instanceof String[])
364 sb.append(ArraysMDE.toString((String[])val));
365 else
366 sb.append(val);
367 if (mod == UNMODIFIED) {
368 sb.append("(U)");
369 }
370 break;
371 case MISSING_NONSENSICAL:
372 sb.append("(missing)");
373 break;
374 case MISSING_FLOW:
375 sb.append("(missing-flow)");
376 break;
377 default:
378 throw new Error("bad modbit " + mod);
379 }
380 }
381 sb.append("]");
382 return sb.toString();
383 }
384
385 public static String valsToString(/*@Nullable*/ Object[] vals) {
386 StringBuffer sb = new StringBuffer("[");
387 for (int i=0; i<vals.length; i++) {
388 if (i>0)
389 sb.append(", ");
390 sb.append (valToString (vals[i]));
391 }
392 sb.append("]");
393 return sb.toString();
394 }
395
396 public static String valToString (/*@Nullable*/ Object val) {
397 if (val == null) return "null";
398 if (val instanceof long[])
399 return(ArraysMDE.toString((long[])val));
400 else if (val instanceof int[])
401 // shouldn't reach this case -- should be long[], not int[]
402 return(ArraysMDE.toString((int[])val));
403 else
404 return(val.toString());
405 }
406
407 /**
408 * Return a new ValueTuple consisting of the elements of this one with
409 * indices listed in indices.
410 **/
411 public ValueTuple slice(int[] indices) {
412 int new_len = indices.length;
413 /*@Nullable*/ /*@Interned*/ Object[] new_vals = new /*@Nullable*/ /*@Interned*/ Object[new_len];
414 int[] new_mods = new int[new_len];
415 for (int i=0; i<new_len; i++) {
416 new_vals[i] = vals[indices[i]];
417 new_mods[i] = mods[indices[i]];
418 }
419 return new ValueTuple(new_vals, new_mods);
420 }
421
422 }