001package daikon.inv; 002 003import daikon.ProglangType; 004import daikon.VarInfo; 005import java.io.Serializable; 006import java.util.Arrays; 007import org.plumelib.util.LimitedSizeLongSet; 008 009// It is a thin wrapper around LimitedSizeLongSet. 010// (Actually, maybe it will just subclass that.) 011 012/** 013 * ValueSet stores a set of values. The implementation only stores integers. When adding a value, 014 * for efficiency its hash code is added rather than the value itself. If the set size exceeds a 015 * specified limit, then its rep is nulled. 016 * 017 * <p>The size of this class is used for efficient justification tests. 018 * 019 * <p>Relevant subclasses are: 020 * 021 * <ul> 022 * <li>ValueSetScalar 023 * <li>ValueSetFloat 024 * <li>ValueSetScalarArray 025 * <li>ValueSetFloatArray 026 * <li>ValueSetString 027 * <li>ValueSetStringArray 028 * </ul> 029 * 030 * These subclasses store a hashcode. 031 * 032 * <p><b>Caveat:</b> The size is an approximation, because if two values happen to have the same 033 * hash value, then the sets size reflects only one of them. (As an example, the hash codes of 0L 034 * and -1L are the same. This implementation has a special case to avoid that problem for long 035 * values, but the hash codes of the arrays {0L} and {-1L} are also the same and this implementation 036 * does not work around that problem.) 037 * 038 * <p>An alternative approach would be to store actual values, rather than approximating. That would 039 * use more space than the current implementation does, but it would give a more accurate 040 * approximation of the size, Here are some possible implementation approaches: 041 * 042 * <ul> 043 * <li>use a TreeSet with a special comparator 044 * <li>use a HashSet that stores wrappers, where the wrappers redefine hashCode. (That is 045 * necessary because arrays don't override {@code Object.hashCode}. 046 * </ul> 047 */ 048public abstract class ValueSet extends LimitedSizeLongSet implements Serializable, Cloneable { 049 static final long serialVersionUID = 20020122L; 050 051 protected ValueSet(int max_values) { 052 super(max_values); 053 } 054 055 // There is one ValueSet per variable (not one per slice or invariant), 056 // so pre-allocating an array with 44 slots should not be a problem. If 057 // it is, then change LimitedSizeLongSet to optionally not pre-allocate 058 // the entire array. 059 /** 060 * The number 44 comes from the fact that .9^44 < .01. So, if the confidence limit is .01 and 061 * the probability of a given event is set at .1, then 44 values is enough to demonstrate that 062 * never seeing the event is statistically justified (not a coincidence). 063 */ 064 static final int DEFAULT_MAX_VALUES = 44; 065 066 public static ValueSet factory(VarInfo var_info) { 067 ProglangType rep_type = var_info.rep_type; 068 boolean is_scalar = rep_type.isScalar(); 069 if (is_scalar) { 070 return new ValueSet.ValueSetScalar(DEFAULT_MAX_VALUES); 071 } else if (rep_type == ProglangType.INT_ARRAY) { 072 return new ValueSet.ValueSetScalarArray(DEFAULT_MAX_VALUES); 073 } else if (rep_type == ProglangType.DOUBLE) { 074 return new ValueSet.ValueSetFloat(DEFAULT_MAX_VALUES); 075 } else if (rep_type == ProglangType.DOUBLE_ARRAY) { 076 return new ValueSet.ValueSetFloatArray(DEFAULT_MAX_VALUES); 077 } else if (rep_type == ProglangType.STRING) { 078 return new ValueSet.ValueSetString(DEFAULT_MAX_VALUES); 079 } else if (rep_type == ProglangType.STRING_ARRAY) { 080 return new ValueSet.ValueSetStringArray(DEFAULT_MAX_VALUES); 081 } else { 082 throw new Error( 083 "Can't create ValueSet for " + var_info.name() + " with rep type " + rep_type); 084 } 085 } 086 087 /** Add the specified object (really, its hashcode) to the set. */ 088 public abstract void add(Object v1); 089 090 /** Add stats from the specified value set. */ 091 protected abstract void add_stats(ValueSet other); 092 093 /** Returns a short description of the values seen. */ 094 public abstract String repr_short(); 095 096 public void add(ValueSet other) { 097 if (this.getClass() != other.getClass()) { 098 throw new Error("ValueSet type mismatch: " + this.getClass() + " " + other.getClass()); 099 } 100 addAll(other); 101 add_stats(other); 102 } 103 104 public static class ValueSetScalar extends ValueSet { 105 // We are Serializable, so we specify a version to allow changes to 106 // method signatures without breaking serialization. If you add or 107 // remove fields, you should change this number to the current date. 108 static final long serialVersionUID = 20031017L; 109 110 long min_val = Long.MAX_VALUE; 111 long max_val = Long.MIN_VALUE; 112 113 public ValueSetScalar(int max_values) { 114 super(max_values); 115 } 116 117 @Override 118 public void add(Object v1) { 119 assert v1 != null; 120 long val = ((Long) v1).longValue(); 121 if (val < min_val) { 122 min_val = val; 123 } 124 if (val > max_val) { 125 max_val = val; 126 } 127 add(val); 128 } 129 130 @Override 131 protected void add_stats(ValueSet other) { 132 ValueSetScalar vs = (ValueSetScalar) other; 133 min_val = Math.min(min_val, vs.min_val); 134 max_val = Math.max(max_val, vs.max_val); 135 } 136 137 public long min() { 138 return min_val; 139 } 140 141 public long max() { 142 return max_val; 143 } 144 145 @Override 146 public String repr_short() { 147 if (size() > 0) { 148 return (size() + " values " + min_val + ".." + max_val); 149 } else { 150 return "0 values"; 151 } 152 } 153 } 154 155 public static class ValueSetFloat extends ValueSet { 156 // We are Serializable, so we specify a version to allow changes to 157 // method signatures without breaking serialization. If you add or 158 // remove fields, you should change this number to the current date. 159 static final long serialVersionUID = 20031017L; 160 161 double min_val = Double.MAX_VALUE; 162 double max_val = -Double.MAX_VALUE; 163 boolean can_be_NaN = false; 164 165 public ValueSetFloat(int max_values) { 166 super(max_values); 167 } 168 169 @Override 170 public void add(Object v1) { 171 assert v1 != null; 172 double val = ((Double) v1).doubleValue(); 173 if (val < min_val) { 174 min_val = val; 175 } 176 if (val > max_val) { 177 max_val = val; 178 } 179 if (Double.isNaN(val)) { 180 can_be_NaN = true; 181 // use the canonical NaN value 182 val = Double.NaN; 183 } 184 add(Double.doubleToLongBits(val)); 185 } 186 187 @Override 188 protected void add_stats(ValueSet other) { 189 ValueSetFloat vs = (ValueSetFloat) other; 190 min_val = Math.min(min_val, vs.min_val); 191 max_val = Math.max(max_val, vs.max_val); 192 can_be_NaN = can_be_NaN || vs.can_be_NaN; 193 } 194 195 public double min() { 196 return min_val; 197 } 198 199 public double max() { 200 return max_val; 201 } 202 203 public boolean canBeNaN() { 204 return can_be_NaN; 205 } 206 207 @Override 208 public String repr_short() { 209 if (size() > 0) { 210 return (size() 211 + " values " 212 + min_val 213 + ".." 214 + max_val 215 + "; " 216 + (can_be_NaN ? "can be " : "never ") 217 + "NaN"); 218 } else { 219 return "0 values"; 220 } 221 } 222 } 223 224 public static class ValueSetScalarArray extends ValueSet { 225 // We are Serializable, so we specify a version to allow changes to 226 // method signatures without breaking serialization. If you add or 227 // remove fields, you should change this number to the current date. 228 static final long serialVersionUID = 20031017L; 229 230 long min_val = Long.MAX_VALUE; 231 long max_val = Long.MIN_VALUE; 232 int max_length = 0; 233 int elem_cnt = 0; 234 int nonsingleton_arr_cnt = 0; // number of arrays with 2 or more elements 235 236 public ValueSetScalarArray(int max_values) { 237 super(max_values); 238 } 239 240 @Override 241 public void add(Object v1) { 242 assert v1 != null; 243 long[] val = (long[]) v1; 244 for (int i = 0; i < val.length; i++) { 245 if (val[i] < min_val) { 246 min_val = val[i]; 247 } 248 if (val[i] > max_val) { 249 max_val = val[i]; 250 } 251 } 252 elem_cnt += val.length; 253 if (val.length > 1) { 254 nonsingleton_arr_cnt++; 255 } 256 if (val.length > max_length) { 257 max_length = val.length; 258 } 259 add(Arrays.hashCode((long[]) v1)); 260 } 261 262 @Override 263 protected void add_stats(ValueSet other) { 264 ValueSetScalarArray vs = (ValueSetScalarArray) other; 265 min_val = Math.min(min_val, vs.min_val); 266 max_val = Math.max(max_val, vs.max_val); 267 elem_cnt += vs.elem_cnt; 268 nonsingleton_arr_cnt += vs.nonsingleton_arr_cnt; 269 max_length = Math.max(max_length, vs.max_length); 270 } 271 272 public long min() { 273 return min_val; 274 } 275 276 public long max() { 277 return max_val; 278 } 279 280 public int elem_cnt() { 281 return elem_cnt; 282 } 283 284 public int nonsingleton_arr_cnt() { 285 return nonsingleton_arr_cnt; 286 } 287 288 public int max_length() { 289 return max_length; 290 } 291 292 @Override 293 public String repr_short() { 294 if (size() > 0) { 295 return (size() + " values " + min_val + ".." + max_val); 296 } else { 297 return "0 values"; 298 } 299 } 300 } 301 302 public static class ValueSetFloatArray extends ValueSet { 303 // We are Serializable, so we specify a version to allow changes to 304 // method signatures without breaking serialization. If you add or 305 // remove fields, you should change this number to the current date. 306 static final long serialVersionUID = 20031017L; 307 308 double min_val = Long.MAX_VALUE; 309 double max_val = Long.MIN_VALUE; 310 boolean can_be_NaN = false; 311 int max_length = 0; 312 int elem_cnt = 0; 313 int nonsingleton_arr_cnt = 0; // number of arrays with 2 or more elements 314 315 public ValueSetFloatArray(int max_values) { 316 super(max_values); 317 } 318 319 @Override 320 public void add(Object v1) { 321 assert v1 != null; 322 double[] val = (double[]) v1; 323 for (int i = 0; i < val.length; i++) { 324 if (val[i] < min_val) { 325 min_val = val[i]; 326 } 327 if (val[i] > max_val) { 328 max_val = val[i]; 329 } 330 if (Double.isNaN(val[i])) { 331 can_be_NaN = true; 332 } 333 } 334 elem_cnt += val.length; 335 if (val.length > 1) { 336 nonsingleton_arr_cnt++; 337 } 338 if (val.length > max_length) { 339 max_length = val.length; 340 } 341 add(Arrays.hashCode(val)); 342 } 343 344 @Override 345 protected void add_stats(ValueSet other) { 346 ValueSetFloatArray vs = (ValueSetFloatArray) other; 347 min_val = Math.min(min_val, vs.min_val); 348 max_val = Math.max(max_val, vs.max_val); 349 can_be_NaN = can_be_NaN || vs.can_be_NaN; 350 elem_cnt += vs.elem_cnt; 351 nonsingleton_arr_cnt += vs.nonsingleton_arr_cnt; 352 max_length = Math.max(max_length, vs.max_length); 353 } 354 355 public double min() { 356 return min_val; 357 } 358 359 public double max() { 360 return max_val; 361 } 362 363 public boolean canBeNaN() { 364 return can_be_NaN; 365 } 366 367 public int elem_cnt() { 368 return elem_cnt; 369 } 370 371 public int nonsingleton_arr_cnt() { 372 return nonsingleton_arr_cnt; 373 } 374 375 public int max_length() { 376 return max_length; 377 } 378 379 @Override 380 public String repr_short() { 381 if (size() > 0) { 382 return (size() 383 + " values " 384 + min_val 385 + ".." 386 + max_val 387 + "; " 388 + (can_be_NaN ? "can be " : "never ") 389 + "NaN"); 390 } else { 391 return "0 values"; 392 } 393 } 394 } 395 396 public static class ValueSetString extends ValueSet { 397 // We are Serializable, so we specify a version to allow changes to 398 // method signatures without breaking serialization. If you add or 399 // remove fields, you should change this number to the current date. 400 static final long serialVersionUID = 20031017L; 401 402 public ValueSetString(int max_values) { 403 super(max_values); 404 } 405 406 @Override 407 public void add(Object v1) { 408 assert v1 != null; 409 add(((String) v1).hashCode()); 410 } 411 412 @Override 413 protected void add_stats(ValueSet other) {} 414 415 @Override 416 public String repr_short() { 417 return (size() + " values "); 418 } 419 } 420 421 public static class ValueSetStringArray extends ValueSet { 422 // We are Serializable, so we specify a version to allow changes to 423 // method signatures without breaking serialization. If you add or 424 // remove fields, you should change this number to the current date. 425 static final long serialVersionUID = 20031017L; 426 427 int elem_cnt = 0; 428 int nonsingleton_arr_cnt = 0; // number of arrays with 2 or more elements 429 430 public ValueSetStringArray(int max_values) { 431 super(max_values); 432 } 433 434 @Override 435 public void add(Object v1) { 436 assert v1 != null; 437 String[] val = (String[]) v1; 438 elem_cnt += val.length; 439 if (val.length > 1) { 440 nonsingleton_arr_cnt++; 441 } 442 add(Arrays.deepHashCode(val)); 443 } 444 445 @Override 446 protected void add_stats(ValueSet other) { 447 ValueSetStringArray vs = (ValueSetStringArray) other; 448 elem_cnt += vs.elem_cnt; 449 nonsingleton_arr_cnt += vs.nonsingleton_arr_cnt; 450 } 451 452 public int elem_cnt() { 453 return elem_cnt; 454 } 455 456 public int nonsingleton_arr_cnt() { 457 return nonsingleton_arr_cnt; 458 } 459 460 @Override 461 public String repr_short() { 462 return (size() + " values "); 463 } 464 } 465}