001package daikon.dcomp; 002 003import daikon.DynComp; 004import daikon.chicory.ArrayInfo; 005import daikon.chicory.ClassInfo; 006import daikon.chicory.ComparabilityProvider; 007import daikon.chicory.DaikonClassInfo; 008import daikon.chicory.DaikonVariableInfo; 009import daikon.chicory.DaikonWriter; 010import daikon.chicory.DeclReader; 011import daikon.chicory.DeclWriter; 012import daikon.chicory.FieldInfo; 013import daikon.chicory.MethodInfo; 014import daikon.chicory.ParameterInfo; 015import daikon.chicory.ReturnInfo; 016import daikon.chicory.RootInfo; 017import daikon.chicory.StaticObjInfo; 018import daikon.chicory.StringInfo; 019import daikon.chicory.ThisObjInfo; 020import daikon.plumelib.bcelutil.SimpleLog; 021import daikon.plumelib.util.WeakIdentityHashMap; 022import java.io.PrintWriter; 023import java.lang.reflect.Array; 024import java.lang.reflect.Field; 025import java.lang.reflect.InvocationTargetException; 026import java.lang.reflect.Method; 027import java.lang.reflect.Modifier; 028import java.time.LocalDateTime; 029import java.time.ZoneId; 030import java.util.ArrayDeque; 031import java.util.ArrayList; 032import java.util.Collections; 033import java.util.Deque; 034import java.util.HashMap; 035import java.util.HashSet; 036import java.util.IdentityHashMap; 037import java.util.LinkedHashMap; 038import java.util.List; 039import java.util.Map; 040import java.util.Set; 041import java.util.concurrent.ConcurrentHashMap; 042import java.util.regex.Matcher; 043import java.util.regex.Pattern; 044import org.checkerframework.checker.lock.qual.GuardSatisfied; 045import org.checkerframework.checker.mustcall.qual.MustCall; 046import org.checkerframework.checker.nullness.qual.Nullable; 047import org.checkerframework.checker.nullness.qual.PolyNull; 048import org.checkerframework.dataflow.qual.Pure; 049 050/** 051 * Runtime support for DynComp, a comparability front end for Chicory. This class is a collection of 052 * methods; it should never be instantiated. 053 */ 054@SuppressWarnings({"nullness", "interning"}) // tricky code, skip for now 055public final class DCRuntime implements ComparabilityProvider { 056 057 /** List of all instrumented methods. */ 058 public static final List<MethodInfo> methods = new ArrayList<>(); 059 060 /** 061 * Keep track of whether or not we are already processing an enter/exit so we can avoid recursion. 062 * Only really necessary during debugging (where we call toString()). 063 */ 064 private static boolean in_enter_exit = false; 065 066 /** Object used to represent nonsensical values. */ 067 private static final Object nonsensical = new Object(); 068 069 /** Object used to represent nonsensical list values. */ 070 private static final Object nonsensical_list = new Object(); 071 072 /** Depth to follow fields in classes. */ 073 public static int depth = 2; 074 075 /** static count of tags in the JDK. Used as an offset for non-JDK code. */ 076 static int max_jdk_static = 100000; 077 078 /** If the application exits with an exception, it should be placed here. */ 079 @SuppressWarnings("StaticAssignmentOfThrowable") // for debugging (I presume) 080 public static @Nullable Throwable exit_exception = null; 081 082 /** Storage for each static tag. */ 083 public static List<@Nullable Object> static_tags = new ArrayList<>(); 084 085 /** 086 * Object used to mark procedure entries in the tag stack. It is pushed on the stack at entry and 087 * checked on exit to make sure it is in on the top of the stack. That allows us to determine 088 * which method caused a tag stack problem. 089 */ 090 public static Object method_marker = new Object(); 091 092 /** Control debug printing. */ 093 public static boolean debug = false; 094 095 /** Log comparability tage stack operations. */ 096 public static boolean debug_tag_frame = false; 097 098 /** Log object compare operations. */ 099 public static boolean debug_objects = false; 100 101 /** Log variable comparability operations. */ 102 public static SimpleLog merge_dv = new SimpleLog(false); 103 104 /** Log array comparability operations. */ 105 public static SimpleLog debug_arr_index = new SimpleLog(false); 106 107 /** Log primitive operations. */ 108 public static SimpleLog debug_primitive = new SimpleLog(false); 109 110 /** Log comparability merges. */ 111 public static SimpleLog debug_merge_comp = new SimpleLog(false); 112 113 /** Log excution time. */ 114 public static SimpleLog debug_timing = new SimpleLog(false); 115 116 /** Log decl output. */ 117 public static SimpleLog debug_decl_print = new SimpleLog(false); 118 119 /** Log excution time. */ 120 public static SimpleLog time_decl = new SimpleLog(false); 121 122 /** Log internal data structure sizes. */ 123 public static SimpleLog map_info = new SimpleLog(false); 124 125 /** If true, merge arrays and their indices. */ 126 private static boolean merge_arrays_and_indices = true; 127 128 /** Decl writer to share output code with Chicory. */ 129 // Set in Premain.premain(). 130 static DeclWriter declWriter; 131 132 /** Used for calling {@link ComparabilityProvider#getComparability}. */ 133 // Set in Premain.premain(). 134 static ComparabilityProvider comparabilityProvider; 135 136 /** Whether the header has been printed. */ 137 private static boolean headerPrinted = false; 138 139 /** Class to hold per-thread comparability data. */ 140 private static class ThreadData { 141 /** Tag stack. */ 142 Deque<Object> tag_stack; 143 144 /** Number of methods currently on tag_stack. */ 145 int tag_stack_call_depth; 146 147 /** class initializer. */ 148 ThreadData() { 149 tag_stack = new ArrayDeque<Object>(); 150 tag_stack_call_depth = 0; 151 } 152 } 153 154 /** Map from Thread to ThreadData. */ 155 private static Map<Thread, ThreadData> thread_to_data = 156 new ConcurrentHashMap<Thread, ThreadData>(); 157 158 /** Map from each object to the tags used for each primitive value in the object. */ 159 public static WeakIdentityHashMap<Object, Object[]> field_map = 160 new WeakIdentityHashMap<Object, Object[]>(); 161 162 /** List of all classes encountered. These are the classes that will have comparability output. */ 163 private static List<ClassInfo> all_classes = new ArrayList<>(); 164 165 /** Set of classes whose static initializer has run. */ 166 private static Set<String> initialized_eclassses = new HashSet<>(); 167 168 /** 169 * Class used as a tag for primitive constants. Only different from Object for debugging purposes. 170 */ 171 private static class Constant {} 172 173 /** 174 * Class used as a tag for uninitialized instance fields. Only different from Object for debugging 175 * purposes. 176 */ 177 @SuppressWarnings("UnusedVariable") // used only for debugging 178 private static class UninitFieldTag { 179 String descr; 180 Throwable stack_trace; 181 182 public UninitFieldTag(String descr, Throwable stack_trace) { 183 this.descr = descr; 184 this.stack_trace = stack_trace; 185 } 186 } 187 188 /** 189 * Class used as a tag for uninitialized array elements. Only different from Object for debugging 190 * purposes. 191 */ 192 private static class UninitArrayElem {} 193 194 /** Either java.lang.DCompMarker or daikon.dcomp.DCompMarker */ 195 private static Class<?> dcomp_marker_class; 196 197 /** java.lang.Object */ 198 private static Class<Object> java_lang_Object_class; 199 200 /** Perform any initialization required before instrumentation begins. */ 201 public static void init() { 202 203 debug_decl_print.enabled = DynComp.debug_decl_print; 204 if (Premain.debug_dcruntime) { 205 debug = true; 206 debug_tag_frame = true; 207 debug_primitive.enabled = true; 208 } 209 if (Premain.debug_dcruntime_all) { 210 debug = true; 211 debug_tag_frame = true; 212 debug_objects = true; 213 merge_dv.enabled = true; 214 debug_arr_index.enabled = true; 215 debug_primitive.enabled = true; 216 debug_merge_comp.enabled = true; 217 debug_decl_print.enabled = true; 218 } 219 220 try { 221 if (!DCInstrument.jdk_instrumented) { 222 dcomp_marker_class = Class.forName("daikon.dcomp.DCompMarker"); 223 } else { 224 dcomp_marker_class = Class.forName("java.lang.DCompMarker"); 225 } 226 @SuppressWarnings("unchecked") 227 Class<Object> tmp = (Class<Object>) Class.forName("java.lang.Object"); 228 java_lang_Object_class = tmp; 229 } catch (Exception e) { 230 throw new RuntimeException("Unexpected error initializing DCRuntime:", e); 231 } 232 233 // Initialize the array of static tags 234 ((ArrayList<@Nullable Object>) static_tags).ensureCapacity(max_jdk_static); 235 while (static_tags.size() <= max_jdk_static) { 236 static_tags.add(null); 237 } 238 } 239 240 public static void debug_print_call_stack() { 241 if (!debug) { 242 return; 243 } 244 245 StackTraceElement[] stack_trace; 246 stack_trace = Thread.currentThread().getStackTrace(); 247 // [0] is getStackTrace 248 // [1] is debug_print_call_stack 249 for (int i = 2; i < stack_trace.length; i++) { 250 System.out.printf("call stack: %s%n", stack_trace[i]); 251 } 252 System.out.println(); 253 } 254 255 /** 256 * Handles calls to instrumented equals() methods. Makes the arguments comparable, and returns 257 * true if they are equals() to one another. 258 * 259 * @param o1 the first argument to equals() 260 * @param o2 the second argument to equals() 261 * @return whether the two values are equal 262 */ 263 public static boolean dcomp_equals(Object o1, Object o2) { 264 // Make obj1 and obj2 comparable 265 if ((o1 != null) && (o2 != null)) { 266 TagEntry.union(o1, o2); 267 } 268 269 if (debug) { 270 System.out.printf("In dcomp_equals%n"); 271 } 272 273 Method m; 274 try { 275 m = 276 o1.getClass() 277 .getMethod("equals_dcomp_instrumented", new Class<?>[] {java_lang_Object_class}); 278 } catch (NoSuchMethodException e) { 279 m = null; 280 } catch (Exception e) { 281 throw new RuntimeException("unexpected error locating equal_dcomp_instrumented", e); 282 } 283 284 if (m != null) { 285 try { 286 // In case the class containing "equals_dcomp_instrumented" is not accessible: 287 m.setAccessible(true); 288 return (Boolean) m.invoke(o1, o2); 289 } catch (Exception e) { 290 throw new RuntimeException("unexpected error invoking equal_dcomp_instrumented", e); 291 } 292 } 293 294 // Push tag for return value, and call the uninstrumented version 295 ThreadData td = thread_to_data.get(Thread.currentThread()); 296 td.tag_stack.push(new Constant()); 297 if (debug_tag_frame) { 298 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 299 } 300 return o1.equals(o2); 301 } 302 303 /** 304 * This map keeps track of active super.equals() calls. 305 * 306 * <p>Each time we make a call on a particular Object, we keep track of which superclass's equals 307 * method we called last. If that Object makes another call to super.equals before the original 308 * call is done, then invoke the equals method of the next-higher class in the class hierarchy 309 * (i.e. the next superclass). 310 * 311 * <p>The map maps an Object to the last Class whose equals method we invoked while invoking that 312 * Object's original super.equals call. Once the equals call terminates, whether by returning a 313 * value or by throwing an exception, the corresponding key is removed from this map. 314 */ 315 static Map<Object, Class<?>> active_equals_calls = new HashMap<>(); 316 317 /** 318 * Handles {@code super.equals(Object)} calls. Makes the arguments comparable, and returns true if 319 * super.equals() returns true for them 320 * 321 * @param o1 the first argument to super.equals() 322 * @param o2 the second argument to super.equals() 323 * @return whether the two values are equal, according to super.equals() 324 * @see #active_equals_calls 325 */ 326 public static boolean dcomp_super_equals(Object o1, Object o2) { 327 // Make obj1 and obj2 comparable 328 if ((o1 != null) && (o2 != null)) { 329 TagEntry.union(o1, o2); 330 } 331 332 if (debug) { 333 System.out.printf("In dcomp_super_equals%n"); 334 } 335 336 Class<?> o1c = o1.getClass(); 337 Class<?> o1super; 338 339 // Check to see if we're already in the middle of a super.equals 340 // call for this Object 341 if (null == active_equals_calls.get(o1)) { 342 // No, we are not 343 o1super = o1c.getSuperclass(); 344 } else { 345 // Yes, we are -- continue up the class hierarchy 346 o1super = active_equals_calls.get(o1).getSuperclass(); 347 } 348 349 // Update the active_equals_calls map 350 active_equals_calls.put(o1, o1super); 351 352 Class<?>[] o1superifaces = o1super.getInterfaces(); 353 354 boolean instrumented = false; 355 for (Class<?> c : o1superifaces) { 356 if (c.getName().equals(DCInstrument.instrumentation_interface)) { 357 instrumented = true; 358 break; 359 } 360 } 361 362 boolean return_val; 363 try { 364 // if the superclass whose method we are calling is instrumented... 365 if (instrumented) { 366 // call the instrumented version 367 Method m = 368 o1super.getMethod( 369 "equals", new Class<?>[] {java_lang_Object_class, dcomp_marker_class}); 370 return_val = ((Boolean) m.invoke(o1, o2, null)); 371 } else { 372 // Push tag for return value, and call the uninstrumented version 373 @MustCall() ThreadData td = thread_to_data.get(Thread.currentThread()); 374 td.tag_stack.push(new Constant()); 375 Method m = o1super.getMethod("equals", new Class<?>[] {java_lang_Object_class}); 376 return_val = ((Boolean) m.invoke(o1, o2)); 377 if (debug_tag_frame) { 378 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 379 } 380 } 381 } catch (NoSuchMethodException e) { 382 System.err.printf("dcomp_super_equals(%s, %s)%n", obj_str(o1), obj_str(o2)); 383 System.err.printf("o1super %s%n", o1super); 384 for (Class<?> c : o1superifaces) { 385 System.err.printf(" o1super interface %s%n", c); 386 } 387 for (Method m : o1super.getDeclaredMethods()) { 388 System.err.printf(" o1super method %s%n", m); 389 } 390 throw new RuntimeException(e); 391 } catch (IllegalAccessException e) { 392 throw new RuntimeException(e); 393 } catch (InvocationTargetException e) { 394 e.printStackTrace(); 395 throw new RuntimeException(e); 396 } catch (Exception e) { 397 throw new RuntimeException("unexpected error locating equals method", e); 398 } 399 400 // We are now done with the call, so remove the entry for this 401 // call from the active_equals_calls map 402 active_equals_calls.remove(o1); 403 return return_val; 404 } 405 406 /** 407 * Clone an object and return the cloned object. 408 * 409 * <p>DCInstrument guarantees we will not see a clone of an array. If the object has been 410 * instrumented, call the instrumented version of clone; if not, call the uninstrumented version 411 * and make the objects comparable. Really should make all of their fields comparable instead. 412 * 413 * @param orig_obj object being cloned 414 * @param target_class class to search for clone method 415 * @return the result of the clone 416 * @throws Throwable if unable to clone object 417 */ 418 public static Object dcomp_clone(Object orig_obj, Class<?> target_class) throws Throwable { 419 if (debug) { 420 System.out.printf("In dcomp_clone%n"); 421 System.out.printf("orig: %s, target: %s%n", orig_obj.getClass(), target_class); 422 } 423 424 Object clone_obj = null; 425 while (true) { 426 try { 427 clone_obj = dcomp_clone_worker(orig_obj, target_class); 428 assert (clone_obj != null); 429 break; 430 } catch (Exception e) { 431 if (e.getCause() == null) { 432 // Some exception other than NoSuchMethod. 433 throw e; 434 } 435 if (e.getCause() instanceof java.lang.NoSuchMethodException) { 436 if (debug) { 437 System.out.println("NoSuchMethod " + target_class.getName()); 438 } 439 440 // Should never reach top of class heirarchy without finding a clone() method. 441 assert !target_class.getName().equals("java.lang.Object"); 442 443 // We didn't find a clone method, get next higher super and try again. 444 target_class = target_class.getSuperclass(); 445 } else { 446 // Some exception other than NoSuchMethod. 447 throw e; 448 } 449 } 450 } 451 452 // Make orig_obj and its clone comparable. 453 if ((orig_obj != null) && (clone_obj != null)) { 454 TagEntry.union(orig_obj, clone_obj); 455 } 456 return clone_obj; 457 } 458 459 /** 460 * Tracks active {@code super.clone()} calls. 461 * 462 * @see active_equals_calls 463 */ 464 static Map<Object, Class<?>> active_clone_calls = new HashMap<>(); 465 466 /** 467 * Handles {@code super.clone()} calls. 468 * 469 * <p>Clone an object using its superclass, and returns the cloned object. 470 * 471 * <p>DCInstrument guarantees we will not see a clone of an array. If the object has been 472 * instrumented, call the instrumented version of clone; if not, call the uninstrumented version 473 * and make the objects comparable. TODO: This really should make all of their fields comparable 474 * instead. 475 * 476 * @param orig_obj object being cloned 477 * @param target_class class to search for clone method 478 * @return the result of the clone 479 * @throws Throwable if unable to clone object 480 * @see #active_clone_calls 481 */ 482 public static Object dcomp_super_clone(Object orig_obj, Class<?> target_class) throws Throwable { 483 if (debug) { 484 System.out.printf("In dcomp_super_clone%n"); 485 System.out.printf("orig: %s, target: %s%n", orig_obj.getClass(), target_class); 486 } 487 488 // Check to see if we're already in the middle of a super.clone call for this object. 489 if (null != active_clone_calls.get(orig_obj)) { 490 // Yes, we are -- continue up the class hierarchy 491 target_class = active_clone_calls.get(orig_obj).getSuperclass(); 492 } 493 // Update the active_clone_calls map 494 active_clone_calls.put(orig_obj, target_class); 495 496 Object clone_obj = null; 497 while (true) { 498 try { 499 clone_obj = dcomp_clone_worker(orig_obj, target_class); 500 assert (clone_obj != null); 501 break; 502 } catch (Exception e) { 503 504 if (e.getCause() == null) { 505 // Some exception other than NoSuchMethod. 506 active_clone_calls.remove(orig_obj); 507 throw e; 508 } 509 if (e.getCause() instanceof java.lang.NoSuchMethodException) { 510 if (debug) { 511 System.out.println("NoSuchMethod " + target_class.getName()); 512 } 513 514 // Should never reach top of class heirarchy without finding a clone() method. 515 assert !target_class.getName().equals("java.lang.Object"); 516 517 // We didn't find a clone method, get next higher super and try again. 518 target_class = active_clone_calls.get(orig_obj).getSuperclass(); 519 // Update the active_clone_calls map 520 active_clone_calls.put(orig_obj, target_class); 521 } else { 522 // Some exception other than NoSuchMethod. 523 active_clone_calls.remove(orig_obj); 524 throw e; 525 } 526 } 527 } 528 529 // Make orig_obj and its clone comparable. 530 if ((orig_obj != null) && (clone_obj != null)) { 531 TagEntry.union(orig_obj, clone_obj); 532 } 533 active_clone_calls.remove(orig_obj); 534 return clone_obj; 535 } 536 537 /** 538 * Clone an object and return the cloned object. Throws an exception if unable to clone object. 539 * 540 * <p>DCInstrument guarantees we will not see a clone of an array. If the object has been 541 * instrumented, call the instrumented version of clone; if not, call the uninstrumented version. 542 * 543 * <p>Note: we use getDeclaredMethod as clone is often protected; also, in the case of 544 * dcomp_super_clone we do not want to automatically find clone in a superclass. We will search 545 * the hierarchy ourselves. 546 * 547 * @param orig_obj object being cloned 548 * @param target_class class to search for clone method 549 * @return the result of the clone 550 * @throws Throwable if unable to clone object 551 */ 552 public static Object dcomp_clone_worker(Object orig_obj, Class<?> target_class) throws Throwable { 553 if (debug) { 554 System.out.printf("In dcomp_clone_worker%n"); 555 System.out.printf("orig_obj: %s, target_class: %s%n", obj_str(orig_obj), target_class); 556 } 557 558 Method m = null; 559 try { 560 m = target_class.getDeclaredMethod("clone", new Class<?>[] {dcomp_marker_class}); 561 } catch (NoSuchMethodException e) { 562 m = null; 563 } catch (Exception e) { 564 throw new RuntimeException("unexpected error locating clone(DCompMarker)", e); 565 } 566 567 if (m != null) { 568 try { 569 if (debug) { 570 System.out.printf("found: %s%n", m); 571 } 572 // In case the class containing "clone()" is not accessible 573 // or clone() is protected. 574 m.setAccessible(true); 575 // Since invoke takes a variable number of arguments, we use an array containing null 576 // as the DCompMarker to distinguish from just null, which indicates 0 arguments. 577 return m.invoke(orig_obj, new Object[] {null}); 578 } catch (InvocationTargetException e) { 579 // This might happen - if an exception is thrown from clone(), 580 // propagate it by rethrowing it. 581 throw e.getCause(); 582 } catch (Exception e) { 583 throw new RuntimeException( 584 "unexpected error invoking clone(DCompMarker) on object of class " 585 + orig_obj.getClass(), 586 e); 587 } 588 } 589 590 // No instrumented clone(), try for uninstrumented version. 591 try { 592 m = target_class.getDeclaredMethod("clone", new Class<?>[] {}); 593 } catch (NoSuchMethodException e) { 594 throw new RuntimeException("unable to locate clone()", e); 595 } catch (Exception e) { 596 throw new RuntimeException("unexpected error locating clone()", e); 597 } 598 try { 599 if (debug) { 600 System.out.printf("found: %s%n", m); 601 } 602 // In case the class containing "clone()" is not accessible 603 // or clone() is protected. 604 m.setAccessible(true); 605 return m.invoke(orig_obj); 606 } catch (InvocationTargetException e) { 607 // This might happen - if an exception is thrown from clone(), 608 // propagate it by rethrowing it. 609 throw e.getCause(); 610 } catch (Exception e) { 611 throw new RuntimeException( 612 "unexpected error invoking clone() on object of class " + orig_obj.getClass(), e); 613 } 614 } 615 616 /** 617 * Handle object comparison. Marks the two objects as comparable and returns whether or not they 618 * are equal. Used as part of a replacement for IF_ACMPEQ. 619 */ 620 public static boolean object_eq(Object obj1, Object obj2) { 621 622 if (debug_objects) { 623 System.out.printf("comparing (eq) '%s' and '%s'%n", obj_str(obj1), obj_str(obj2)); 624 } 625 626 // Note that obj1 and obj2 are comparable 627 if ((obj1 != null) && (obj2 != null)) { 628 TagEntry.union(obj1, obj2); 629 } 630 631 return (obj1 == obj2); 632 } 633 634 /** 635 * Handle object comparison. Marks the two objects as comparable and returns whether or not they 636 * are equal. Used as part of a replacement for IF_ACMPNE. 637 */ 638 public static boolean object_ne(Object obj1, Object obj2) { 639 640 if (debug_objects) { 641 System.out.printf("comparing (ne) '%s' and '%s'%n", obj_str(obj1), obj_str(obj2)); 642 } 643 // Note that obj1 and obj2 are comparable 644 if ((obj1 != null) && (obj2 != null)) { 645 TagEntry.union(obj1, obj2); 646 } 647 648 return (obj1 != obj2); 649 } 650 651 static Map<String, Integer> methodCountMap = new HashMap<>(64); 652 653 /** 654 * Create the tag frame for this method. Pop the tags for any primitive parameters off of the tag 655 * stack and store them in the tag frame. 656 * 657 * @param params encodes the position of the primitive parameters into a string. The first 658 * character is size of the tag frame. The remaining characters indicate where each parameter 659 * on the tag stack should be stored into the frame. For example "20" allocates a tag frame 660 * with two elements and stores the top of the tag stack into element 0. A string is used for 661 * simplicity in code generation since strings can easily be placed into the constant portion 662 * of the class file. Note that characters are determined by adding the integer value to '0'. 663 * Values greater than 9 will have unintuitive (but printable) values. 664 * @return the allocated and initialized tag frame 665 */ 666 public static Object[] create_tag_frame(String params) { 667 if (debug) { 668 System.out.printf("%nEnter: %s%n", caller_name()); 669 } 670 671 if (DynComp.verbose) { 672 String method_name = caller_name(); 673 Integer count = methodCountMap.get(method_name); 674 if (count == null) { 675 count = 1; 676 } else { 677 count = count.intValue() + 1; 678 } 679 methodCountMap.put(method_name, count); 680 } 681 682 // create_tag_frame is the first DCRuntime method called for an 683 // instrumented user method. Since it might be on a new thread 684 // we need to check/set the per-thread data map. 685 Thread t = Thread.currentThread(); 686 ThreadData td = thread_to_data.computeIfAbsent(t, __ -> new ThreadData()); 687 688 int frame_size = ((int) params.charAt(0)) - '0'; 689 // Character.digit (params.charAt(0), Character.MAX_RADIX); 690 Object[] tag_frame = new Object[frame_size]; 691 if (debug_tag_frame) { 692 System.out.printf( 693 "Creating tag frame of size %d [%s] for %s%n", frame_size, params, caller_name()); 694 } 695 for (int ii = 1; ii < params.length(); ii++) { 696 int offset = params.charAt(ii) - '0'; 697 // Character.digit (params.charAt(ii), Character.MAX_RADIX); 698 assert td.tag_stack.peek() != method_marker; 699 tag_frame[offset] = td.tag_stack.pop(); 700 if (debug_tag_frame) { 701 System.out.printf("popped %s into tag_frame[%d]%n", tag_frame[offset], offset); 702 } 703 } 704 705 // Push the method marker on the tag stack (now that we have removed 706 // the parameters 707 td.tag_stack.push(method_marker); 708 // save the tag stack call_depth for debugging 709 tag_frame[frame_size - 1] = ++td.tag_stack_call_depth; 710 if (debug_tag_frame) { 711 System.out.printf("push method marker tag: %s%n", method_marker); 712 System.out.printf("tag stack call_depth: %d%n", td.tag_stack_call_depth); 713 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 714 } 715 716 // debug_print_call_stack(); 717 718 return tag_frame; 719 } 720 721 /** 722 * Make sure the tag stack for this method is empty before exit. 723 * 724 * @param tag_frame the tag frame 725 */ 726 public static void normal_exit(Object[] tag_frame) { 727 if (debug) { 728 System.out.printf("Begin normal exit from %s%n", caller_name()); 729 } 730 731 ThreadData td = thread_to_data.get(Thread.currentThread()); 732 if (td.tag_stack.peek() != method_marker) { 733 // Something has gone wrong. It's probably an exception that 734 // was handled by an exception handler other than one added by 735 // DCInstrument. From an <init> method or native code, for example. 736 if (debug_tag_frame) { 737 System.out.printf("tag stack value mismatch! top not method marker%n"); 738 Thread.dumpStack(); 739 } 740 // discard tags until we get to a method marker 741 while (td.tag_stack.peek() != method_marker) td.tag_stack.pop(); 742 } 743 744 int orig_tag_stack_call_depth = ((Integer) tag_frame[tag_frame.length - 1]).intValue(); 745 if (td.tag_stack_call_depth != orig_tag_stack_call_depth) { 746 // Something has gone wrong. It's almost certainly an exception that 747 // was handled by an exception handler other than one added by 748 // DCInstrument. From an <init> method or native code, for example. 749 if (debug_tag_frame) { 750 System.out.printf( 751 "tag stack call_depth mismatch! at %d expected %d%n", 752 td.tag_stack_call_depth, orig_tag_stack_call_depth); 753 Thread.dumpStack(); 754 } 755 } 756 while (td.tag_stack_call_depth > orig_tag_stack_call_depth) { 757 td.tag_stack.pop(); // discard marker 758 td.tag_stack_call_depth--; 759 // discard tags until we get to a method marker 760 while (td.tag_stack.peek() != method_marker) td.tag_stack.pop(); 761 } 762 763 // now do normal exit process 764 td.tag_stack.pop(); // discard marker 765 td.tag_stack_call_depth--; 766 if (debug_tag_frame) { 767 System.out.printf("tag stack call_depth: %d%n", td.tag_stack_call_depth); 768 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 769 } 770 if (debug) { 771 System.out.printf("Normal exit from %s%n%n", caller_name()); 772 } 773 } 774 775 /** 776 * Called for exits from methods with a primitive return type. Pop the return type off of the tag 777 * stack, make sure the tags stack is empty for this method and then put the return value back on 778 * the tag stack. 779 * 780 * @param tag_frame the tag frame 781 */ 782 public static void normal_exit_primitive(Object[] tag_frame) { 783 if (debug) { 784 System.out.printf("Begin normal exit primitive from %s%n", caller_name()); 785 } 786 787 ThreadData td = thread_to_data.get(Thread.currentThread()); 788 Object ret_tag = td.tag_stack.pop(); // save what we hope is the return value tag 789 assert ret_tag != null; 790 791 if (td.tag_stack.peek() != method_marker) { 792 // Something has gone wrong. It's probably an exception that 793 // was handled by an exception handler other than one added by 794 // DCInstrument. From an <init> method or native code, for example. 795 if (debug_tag_frame) { 796 System.out.printf("tag stack value mismatch! top not method marker%n"); 797 Thread.dumpStack(); 798 } 799 // discard tags until we get to a method marker 800 while (td.tag_stack.peek() != method_marker) td.tag_stack.pop(); 801 } 802 803 int orig_tag_stack_call_depth = ((Integer) tag_frame[tag_frame.length - 1]).intValue(); 804 if (td.tag_stack_call_depth != orig_tag_stack_call_depth) { 805 // Something has gone wrong. It's almost certainly an exception that 806 // was handled by an exception handler other than one added by 807 // DCInstrument. From an <init> method or native code, for example. 808 if (debug_tag_frame) { 809 System.out.printf( 810 "tag stack call_depth mismatch! at %d expected %d%n", 811 td.tag_stack_call_depth, orig_tag_stack_call_depth); 812 Thread.dumpStack(); 813 } 814 } 815 while (td.tag_stack_call_depth > orig_tag_stack_call_depth) { 816 td.tag_stack.pop(); // discard marker 817 td.tag_stack_call_depth--; 818 // discard tags until we get to a method marker 819 while (td.tag_stack.peek() != method_marker) td.tag_stack.pop(); 820 } 821 822 // now do normal exit process 823 td.tag_stack.pop(); // discard marker 824 td.tag_stack_call_depth--; 825 if (debug_tag_frame) { 826 System.out.printf("tag stack call_depth: %d%n", td.tag_stack_call_depth); 827 } 828 if (debug) { 829 System.out.printf("Normal exit primitive from %s%n%n", caller_name()); 830 } 831 td.tag_stack.push(ret_tag); 832 if (debug_tag_frame) { 833 System.out.printf("push return value tag: %s%n", ret_tag); 834 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 835 } 836 } 837 838 /** 839 * Clean up the tag stack on an exception exit from a method. Pops items off of the tag stack 840 * until the method marker is found. 841 * 842 * @param throwable cause of the exception 843 */ 844 public static void exception_exit(Object throwable) { 845 if (debug) { 846 System.out.printf("Begin exception exit from %s%n", caller_name()); 847 ((Throwable) throwable).printStackTrace(); 848 } 849 850 ThreadData td = thread_to_data.get(Thread.currentThread()); 851 td.tag_stack_call_depth--; 852 if (debug_tag_frame) { 853 System.out.printf("tag stack call_depth: %d%n", td.tag_stack_call_depth); 854 } 855 if (debug) { 856 System.out.printf("Exception exit from %s%n", caller_name()); 857 } 858 while (!td.tag_stack.isEmpty()) { 859 if (td.tag_stack.pop() == method_marker) { 860 if (debug_tag_frame) { 861 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 862 } 863 return; 864 } 865 } 866 867 System.err.printf("Method marker not found in exception exit%n"); 868 } 869 870 /** Cleans up the tag stack when an exception is thrown. */ 871 public static void throw_op() { 872 if (debug) { 873 System.out.printf("In throw_op%n"); 874 } 875 ThreadData td = thread_to_data.get(Thread.currentThread()); 876 while (td.tag_stack.peek() != method_marker) td.tag_stack.pop(); 877 if (debug_tag_frame) { 878 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 879 } 880 } 881 882 /** Pushes the tag at tag_frame[index] on the tag stack. */ 883 public static void push_local_tag(Object[] tag_frame, int index) { 884 885 ThreadData td = thread_to_data.get(Thread.currentThread()); 886 debug_primitive.log("push_local_tag[%d] %s%n", index, tag_frame[index]); 887 assert tag_frame[index] != null : "index " + index; 888 td.tag_stack.push(tag_frame[index]); 889 if (debug_tag_frame) { 890 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 891 } 892 } 893 894 /** Pops the top of the tag stack into tag_frame[index] */ 895 public static void pop_local_tag(Object[] tag_frame, int index) { 896 897 ThreadData td = thread_to_data.get(Thread.currentThread()); 898 assert td.tag_stack.peek() != method_marker; 899 tag_frame[index] = td.tag_stack.pop(); 900 assert tag_frame[index] != null : "index " + index; 901 debug_primitive.log("pop_local_tag[%d] %s%n", index, tag_frame[index]); 902 if (debug_tag_frame) { 903 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 904 } 905 } 906 907 /** Pushes the tag associated with the static static_num on the tag stack. */ 908 public static void push_static_tag(int static_num) { 909 910 ThreadData td = thread_to_data.get(Thread.currentThread()); 911 Object static_tag = static_tags.get(static_num); 912 if (static_tag == null) { 913 static_tag = new Object(); 914 static_tags.set(static_num, static_tag); 915 } 916 td.tag_stack.push(static_tag); 917 debug_primitive.log("push_static_tag[%d] %s%n", static_num, static_tag); 918 if (debug_tag_frame) { 919 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 920 } 921 } 922 923 /** 924 * Pushes an array reference on the tag stack. 925 * 926 * @param arr_ref array being accessed 927 */ 928 public static void push_array_tag(Object arr_ref) { 929 930 ThreadData td = thread_to_data.get(Thread.currentThread()); 931 td.tag_stack.push(arr_ref); 932 if (debug_arr_index.enabled()) { 933 debug_arr_index.log("push_array_tag %s%n", obj_str(arr_ref)); 934 } 935 if (debug_tag_frame) { 936 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 937 } 938 } 939 940 /** 941 * Pops the top of the tag stack into the tag storage for static_num. 942 * 943 * @param static_num identifies the static variable being accessed 944 */ 945 public static void pop_static_tag(int static_num) { 946 947 ThreadData td = thread_to_data.get(Thread.currentThread()); 948 assert td.tag_stack.peek() != method_marker; 949 static_tags.set(static_num, td.tag_stack.pop()); 950 assert static_tags.get(static_num) != null; 951 debug_primitive.log("pop_static_tag[%d] %s%n", static_num, static_tags.get(static_num)); 952 if (debug_tag_frame) { 953 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 954 } 955 } 956 957 /** 958 * Discard the tag on the top of the tag stack. Called when primitives are pushed but not used in 959 * expressions (such as when allocating arrays). (No longer used?) 960 * 961 * @param cnt number of tags to discard 962 */ 963 public static void discard_tag(int cnt) { 964 if (debug) { 965 System.out.printf("In discard_tag%n"); 966 } 967 968 ThreadData td = thread_to_data.get(Thread.currentThread()); 969 // debug_print_call_stack(); 970 while (--cnt >= 0) { 971 assert td.tag_stack.peek() != method_marker; 972 if (debug) { 973 System.out.printf(" discard a tag%n"); 974 } 975 td.tag_stack.pop(); 976 } 977 if (debug_tag_frame) { 978 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 979 } 980 } 981 982 /** 983 * Manipulate the tags for an array store instruction. The tag at the top of stack is stored into 984 * the tag storage for the array. Mark the array and the index as comparable. 985 * 986 * @param arr_ref array being accessed 987 * @param length size of the array 988 * @param index index of the array element being accessed 989 */ 990 private static void primitive_array_store(Object arr_ref, int length, int index) { 991 if (debug) { 992 System.out.printf("In primitive_array_store%n"); 993 } 994 995 // This is a helper routine always called as the first step 996 // so we can set the per-thread data here. 997 ThreadData td = thread_to_data.get(Thread.currentThread()); 998 999 // look for the tag storage for this array 1000 Object[] obj_tags = field_map.get(arr_ref); 1001 1002 // If none has been allocated, allocate the space and associate it with 1003 // the array 1004 if (obj_tags == null) { 1005 obj_tags = new Object[length]; 1006 field_map.put(arr_ref, obj_tags); 1007 } 1008 1009 // Pop the tag off of the stack and assign it into the tag storage for 1010 // this index 1011 assert td.tag_stack.peek() != method_marker; 1012 obj_tags[index] = td.tag_stack.pop(); 1013 if (debug_primitive.enabled()) { 1014 debug_primitive.log("array store %s[%d] = %s%n", obj_str(arr_ref), index, obj_tags[index]); 1015 } 1016 1017 // Mark the arry and its index as comparable 1018 assert td.tag_stack.peek() != method_marker; 1019 Object index_tag = td.tag_stack.pop(); 1020 if (debug_arr_index.enabled()) { 1021 debug_arr_index.log("Merging array '%s' and index '%s'", obj_str(arr_ref), index_tag); 1022 } 1023 if (merge_arrays_and_indices) { 1024 TagEntry.union(arr_ref, index_tag); 1025 } 1026 if (debug_tag_frame) { 1027 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 1028 } 1029 } 1030 1031 /** Execute an aastore instruction and mark the array and its index as comparable. */ 1032 public static void aastore(Object[] arr, int index, Object val) { 1033 1034 ThreadData td = thread_to_data.get(Thread.currentThread()); 1035 // Mark the array and its index as comparable 1036 assert td.tag_stack.peek() != method_marker; 1037 Object index_tag = td.tag_stack.pop(); 1038 debug_arr_index.log("Merging array '%s' and index '%s'", arr, index_tag); 1039 if (merge_arrays_and_indices) { 1040 TagEntry.union(arr, index_tag); 1041 } 1042 1043 // Store the value 1044 arr[index] = val; 1045 if (debug_tag_frame) { 1046 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 1047 } 1048 } 1049 1050 /** 1051 * The JVM uses bastore for both boolean and byte data types. With the addition of StackMap 1052 * verification in Java 7 we can no longer use the same runtime routine for both data types. 1053 * Hence, the addition of zastore below for boolean. 1054 * 1055 * <p>Execute an bastore instruction and manipulate the tags accordingly. The tag at the top of 1056 * stack is stored into the tag storage for the array. 1057 */ 1058 public static void bastore(byte[] arr, int index, byte val) { 1059 1060 // Store the tag for val in the tag storage for array and mark 1061 // the array and the index as comparable. 1062 primitive_array_store(arr, arr.length, index); 1063 1064 // Execute the array store 1065 arr[index] = val; 1066 } 1067 1068 public static void zastore(boolean[] arr, int index, boolean val) { 1069 1070 // Store the tag for val in the tag storage for array and mark 1071 // the array and the index as comparable. 1072 primitive_array_store(arr, arr.length, index); 1073 1074 // Execute the array store 1075 arr[index] = val; 1076 } 1077 1078 /** 1079 * Execute an castore instruction and manipulate the tags accordingly. The tag at the top of stack 1080 * is stored into the tag storage for the array. 1081 */ 1082 public static void castore(char[] arr, int index, char val) { 1083 1084 // Store the tag for val in the tag storage for array and mark 1085 // the array and the index as comparable. 1086 primitive_array_store(arr, arr.length, index); 1087 1088 // Execute the array store 1089 arr[index] = val; 1090 } 1091 1092 /** 1093 * Execute an dastore instruction and manipulate the tags accordingly. The tag at the top of stack 1094 * is stored into the tag storage for the array. 1095 */ 1096 public static void dastore(double[] arr, int index, double val) { 1097 1098 // Store the tag for val in the tag storage for array and mark 1099 // the array and the index as comparable. 1100 primitive_array_store(arr, arr.length, index); 1101 1102 // Execute the array store 1103 arr[index] = val; 1104 } 1105 1106 /** 1107 * Execute an fastore instruction and manipulate the tags accordingly. The tag at the top of stack 1108 * is stored into the tag storage for the array. 1109 */ 1110 public static void fastore(float[] arr, int index, float val) { 1111 1112 // Store the tag for val in the tag storage for array and mark 1113 // the array and the index as comparable. 1114 primitive_array_store(arr, arr.length, index); 1115 1116 // Execute the array store 1117 arr[index] = val; 1118 } 1119 1120 /** 1121 * Execute an iastore instruction and manipulate the tags accordingly. The tag at the top of stack 1122 * is stored into the tag storage for the array. 1123 */ 1124 public static void iastore(int[] arr, int index, int val) { 1125 1126 // Store the tag for val in the tag storage for array and mark 1127 // the array and the index as comparable. 1128 primitive_array_store(arr, arr.length, index); 1129 1130 // Execute the array store 1131 arr[index] = val; 1132 } 1133 1134 /** 1135 * Execute an lastore instruction and manipulate the tags accordingly. The tag at the top of stack 1136 * is stored into the tag storage for the array. 1137 */ 1138 public static void lastore(long[] arr, int index, long val) { 1139 1140 // Store the tag for val in the tag storage for array and mark 1141 // the array and the index as comparable. 1142 primitive_array_store(arr, arr.length, index); 1143 1144 // Execute the array store 1145 arr[index] = val; 1146 } 1147 1148 /** 1149 * Execute an sastore instruction and manipulate the tags accordingly. The tag at the top of stack 1150 * is stored into the tag storage for the array. 1151 */ 1152 public static void sastore(short[] arr, int index, short val) { 1153 1154 // Store the tag for val in the tag storage for array and mark 1155 // the array and the index as comparable. 1156 primitive_array_store(arr, arr.length, index); 1157 1158 // Execute the array store 1159 arr[index] = val; 1160 } 1161 1162 /** 1163 * Make the count arguments to multianewarray comparable to the corresponding array indices. 1164 * count1 is made comparable to the index of the given array (arr), and count2 is made comparable 1165 * to the index of each array that is an element of arr. 1166 * 1167 * @param count1 number items in 1st dimension (unused, associated tag value is on tag stack) 1168 * @param count2 number items in 2nd dimension (unused, associated tag value is on tag stack) 1169 * @param arr the new array 1170 */ 1171 public static void multianewarray2(int count1, int count2, Object[] arr) { 1172 if (debug) { 1173 System.out.printf("In multianewarray2%n"); 1174 } 1175 1176 ThreadData td = thread_to_data.get(Thread.currentThread()); 1177 assert td.tag_stack.peek() != method_marker; 1178 Object count2tag = td.tag_stack.pop(); 1179 assert td.tag_stack.peek() != method_marker; 1180 Object count1tag = td.tag_stack.pop(); 1181 1182 TagEntry.union(count1tag, arr); 1183 1184 for (Object subarr : arr) { 1185 TagEntry.union(count2tag, subarr); 1186 } 1187 if (debug_tag_frame) { 1188 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 1189 } 1190 } 1191 1192 /** 1193 * Called when a user method is entered. Any daikon variables whose current values are comparable 1194 * are marked as comparable. 1195 * 1196 * @param tag_frame tag_frame containing the tags for the primitive arguments of this method 1197 * @param obj value of 'this', or null if the method is static 1198 * @param mi_index index into the list of all methods (methods) 1199 * @param args array of the arguments to the method 1200 */ 1201 public static void enter(Object[] tag_frame, @Nullable Object obj, int mi_index, Object[] args) { 1202 1203 // Don't be recursive 1204 if (in_enter_exit) { 1205 return; 1206 } 1207 in_enter_exit = true; 1208 1209 if (debug) { 1210 Throwable stack = new Throwable("enter"); 1211 StackTraceElement[] ste_arr = stack.getStackTrace(); 1212 StackTraceElement ste = ste_arr[1]; 1213 System.out.printf("%n%s.%s():::ENTER%n", ste.getClassName(), ste.getMethodName()); 1214 System.out.printf("this = %s%nmi = %s%n", obj_str(obj), methods.get(mi_index)); 1215 System.out.printf("args: "); 1216 for (Object arg : args) { 1217 System.out.printf("'%s' ", obj_str(arg)); 1218 } 1219 System.out.println(); 1220 } 1221 1222 MethodInfo mi = methods.get(mi_index); 1223 mi.call_cnt++; 1224 ClassInfo ci = mi.class_info; 1225 if (ci.clazz == null) { 1226 ci.initViaReflection(); 1227 if (debug) { 1228 System.out.printf("DCRuntime.enter adding %s to all class list%n", ci); 1229 } 1230 all_classes.add(ci); 1231 // Moved to DCInstrument.instrument() 1232 // daikon.chicory.Runtime.all_classes.add (ci); 1233 merge_dv.log("initializing traversal for %s%n", ci); 1234 ci.init_traversal(depth); 1235 } 1236 if (mi.traversalEnter == null) { 1237 mi.init_traversal(depth); 1238 } 1239 1240 // Merge comparability information for the Daikon variables 1241 merge_dv.log("processing method %s:::ENTER%n", mi); 1242 merge_dv.indent(); 1243 process_all_vars(mi, mi.traversalEnter, tag_frame, obj, args, null); 1244 merge_dv.exdent(); 1245 1246 in_enter_exit = false; 1247 } 1248 1249 /** 1250 * Called when a user method exits. Any daikon variables whose current values are comparable are 1251 * marked as comparable. 1252 * 1253 * @param tag_frame tag_frame containing the tags for the primitive arguments of this method 1254 * @param obj value of 'this', or null if the method is static 1255 * @param mi_index index into the list of all methods (methods) 1256 * @param args array of the arguments to the method 1257 * @param ret_val value returned by the method, or null if the method is a constructor or void 1258 * @param exit_line_number the source line number of this exit point 1259 */ 1260 public static void exit( 1261 Object[] tag_frame, 1262 @Nullable Object obj, 1263 int mi_index, 1264 Object[] args, 1265 Object ret_val, 1266 int exit_line_number) { 1267 1268 // Don't be recursive 1269 if (in_enter_exit) { 1270 return; 1271 } 1272 in_enter_exit = true; 1273 1274 if (debug) { 1275 Throwable stack = new Throwable("exit"); 1276 StackTraceElement[] ste_arr = stack.getStackTrace(); 1277 StackTraceElement ste = ste_arr[1]; 1278 System.out.printf("%n%s.%s():::EXIT%n", ste.getClassName(), ste.getMethodName()); 1279 System.out.printf("this = %s%nmi = %s%n", obj_str(obj), methods.get(mi_index)); 1280 System.out.printf("args: "); 1281 for (Object arg : args) { 1282 System.out.printf("'%s' ", obj_str(arg)); 1283 } 1284 System.out.println(); 1285 System.out.printf("ret_val = %s%nexit_line_number= %d%n%n", ret_val, exit_line_number); 1286 } 1287 1288 MethodInfo mi = methods.get(mi_index); 1289 1290 // Merge comparability information for the Daikon variables 1291 merge_dv.log("processing method %s:::EXIT%n", mi); 1292 merge_dv.indent(); 1293 process_all_vars(mi, mi.traversalExit, tag_frame, obj, args, ret_val); 1294 merge_dv.exdent(); 1295 1296 in_enter_exit = false; 1297 } 1298 1299 /** 1300 * Process all of the daikon variables in the tree starting at root. If the values referenced by 1301 * those variables are comparable mark the variables as comparable. 1302 */ 1303 public static void process_all_vars( 1304 MethodInfo mi, RootInfo root, Object[] tag_frame, Object obj, Object[] args, Object ret_val) { 1305 1306 debug_timing.log("process_all_vars for %s%n", mi); 1307 1308 merge_dv.log("this: %s%n", obj); 1309 // For some reason the following line causes DynComp to behave incorrectly. 1310 // I have not take the time to investigate. 1311 // merge_dv.log("arguments: %s%n", Arrays.toString(args)); 1312 1313 // Map from an Object to the Daikon variable that currently holds 1314 // that object. 1315 IdentityHashMap<Object, DaikonVariableInfo> varmap = 1316 new IdentityHashMap<Object, DaikonVariableInfo>(2048); 1317 1318 for (DaikonVariableInfo dv : root.children) { 1319 if (dv instanceof ThisObjInfo) { 1320 merge_comparability(varmap, null, obj, dv); 1321 } else if (dv instanceof ParameterInfo) { 1322 ParameterInfo pi = (ParameterInfo) dv; 1323 Object p = args[pi.getArgNum()]; 1324 // Class arg_type = mi.arg_types[pi.getArgNum()]; 1325 // if (arg_type.isPrimitive()) 1326 if (pi.isPrimitive()) { 1327 p = tag_frame[pi.get_param_offset() + ((obj == null) ? 0 : 1)]; 1328 } 1329 merge_comparability(varmap, null, p, pi); 1330 } else if (dv instanceof ReturnInfo) { 1331 if (mi.return_type().isPrimitive()) { 1332 ThreadData td = thread_to_data.get(Thread.currentThread()); 1333 ret_val = td.tag_stack.peek(); 1334 } 1335 merge_comparability(varmap, null, ret_val, dv); 1336 } else if (dv instanceof FieldInfo) { 1337 assert ((FieldInfo) dv).isStatic() : "non static field at root " + dv; 1338 merge_comparability(varmap, null, null, dv); 1339 } else if (dv instanceof StaticObjInfo) { 1340 for (DaikonVariableInfo static_dv : dv.children) { 1341 assert ((FieldInfo) static_dv).isStatic() : "non static field at root " + dv; 1342 merge_comparability(varmap, null, null, static_dv); 1343 } 1344 } else { 1345 throw new Error("unexpected node " + dv); 1346 } 1347 } 1348 debug_timing.log("exit process_all_vars for %s%n%n", mi); 1349 map_info.log("varmap size: %d%n", varmap.size()); 1350 } 1351 1352 /** 1353 * Returns the tag for the specified field. If that field is an array, a list of tags will be 1354 * returned. 1355 * 1356 * @param fi a field 1357 * @param parent object that contains the field (if any) 1358 * @param obj value of the field itself (if available and if it's an object) 1359 * @return the tag for the specified field 1360 */ 1361 static Object get_field_tag(FieldInfo fi, Object parent, Object obj) { 1362 1363 // Initialize the code that gets the tag for various field types 1364 if (fi.field_tag == null) { 1365 if (fi.isStatic()) { 1366 if (fi.isPrimitive()) { 1367 // a static final primitive is a constant and there is no tag accessor 1368 if (fi.isFinal()) { 1369 return null; 1370 } 1371 fi.field_tag = new StaticPrimitiveTag(fi); 1372 } else { 1373 fi.field_tag = new StaticReferenceTag(fi); 1374 } 1375 } else { // not static 1376 if (fi.isPrimitive() && fi.isArray()) { 1377 fi.field_tag = new PrimitiveArrayTag(fi); 1378 } else if (fi.isPrimitive()) { 1379 fi.field_tag = new PrimitiveTag(fi); 1380 } else { 1381 fi.field_tag = new ReferenceTag(fi); 1382 } 1383 } 1384 } 1385 1386 // get the tag 1387 return fi.field_tag.get_tag(parent, obj); 1388 } 1389 1390 /** 1391 * Gets the object in field f in object obj. Exceptions are turned into Errors. 1392 * 1393 * @param f which field to return 1394 * @param obj the object that contains the field 1395 * @return the specified object 1396 */ 1397 public static Object get_object_field(Field f, Object obj) { 1398 if (debug) { 1399 System.out.printf("In get_object_field%n"); 1400 } 1401 try { 1402 return f.get(obj); 1403 } catch (Exception e) { 1404 throw new Error("can't get field " + f + " in " + obj_str(obj), e); 1405 } 1406 } 1407 1408 /** 1409 * Merges the comparability of the daikon variable dv and its children whose current values are 1410 * comparable. 1411 * 1412 * @param varmap map from value set leaders to the first daikon variable encountered with that 1413 * leader. Whenever a second daikon variable is encountered whose value has the same leader, 1414 * that daikon variable is merged with the first daikon variable. 1415 * @param parent value of dv's parent 1416 * @param obj value of dv 1417 * @param dv DaikonVariable to process 1418 */ 1419 static void merge_comparability( 1420 IdentityHashMap<Object, DaikonVariableInfo> varmap, 1421 Object parent, 1422 Object obj, 1423 DaikonVariableInfo dv) { 1424 1425 // merge_dv.enabled = dv.getName().contains ("mtfFreq"); 1426 1427 long start_millis = 0; 1428 if (debug_timing.enabled()) { 1429 start_millis = System.currentTimeMillis(); 1430 } 1431 if (merge_dv.enabled()) { 1432 merge_dv.log("merge_comparability: checking var %s = '%s' %n", dv, obj_str(obj)); 1433 } 1434 1435 // Ignore ClassInfo and StringInfo variables. These are not real 1436 // variables in the program 1437 if ((dv instanceof DaikonClassInfo) || (dv instanceof StringInfo)) { 1438 debug_timing.log(" Variable %s : %d msecs%n", dv, System.currentTimeMillis() - start_millis); 1439 return; 1440 } 1441 1442 // Get the tag for this object. For non-primitives this is normally the 1443 // object itself. For static fields, the object is not passed in, but is 1444 // obtained via reflection. 1445 Object tag = obj; 1446 if (dv instanceof FieldInfo) { 1447 tag = get_field_tag((FieldInfo) dv, parent, obj); 1448 } 1449 1450 if (!dv.declShouldPrint()) { 1451 // do nothing 1452 } else if (dv.isArray() && (tag instanceof List<?>)) { 1453 @SuppressWarnings("unchecked") 1454 List<Object> elements = (List<Object>) tag; 1455 if (debug_timing.enabled()) { 1456 debug_timing.log(" ArrayInfo %d elements", elements.size()); 1457 } 1458 for (Object atag : elements) { 1459 // Ignore null and nonsensical tags. There is no reason to process 1460 // their children, because they can't have any with reasonable values 1461 if ((atag == null) || (atag == nonsensical) || (atag == nonsensical_list)) { 1462 continue; 1463 } 1464 1465 // Look up this object. If it already is associated with a 1466 // DaikonVariable merge those variables. Otherwise, add it to 1467 // the map 1468 Object leader = TagEntry.find(atag); 1469 if (merge_dv.enabled()) { 1470 merge_dv.log("Leader for atag '%s' is '%s'%n", obj_str(atag), obj_str(leader)); 1471 } 1472 DaikonVariableInfo current = varmap.get(leader); 1473 merge_dv.log("Daikon variable for leader = %s%n", current); 1474 if (current != null) { 1475 merge_dv.log("**Merging %s and %s%n", current, dv); 1476 TagEntry.union(current, dv); 1477 } else { 1478 varmap.put(leader, dv); 1479 } 1480 } 1481 } else if (dv.isArray()) { 1482 if (tag == null) { 1483 if (debug_timing.enabled()) { 1484 debug_timing.log( 1485 " no array tags for Variable %s : %d msecs%n", 1486 dv, System.currentTimeMillis() - start_millis); 1487 } 1488 return; 1489 } 1490 Object[] elements = (Object[]) tag; 1491 if (debug_timing.enabled()) { 1492 debug_timing.log(" Prim ArrayInfo %d elements", elements.length); 1493 } 1494 Object prev_tag = null; 1495 for (Object atag : elements) { 1496 // Ignore null and nonsensical tags. There is no reason to process 1497 // their children, because they can't have any with reasonable values 1498 if ((atag == null) || (atag == nonsensical) || (atag == nonsensical_list)) { 1499 continue; 1500 } 1501 1502 // No need to handle the same tag twice 1503 if (prev_tag == atag) { 1504 continue; 1505 } 1506 prev_tag = atag; 1507 1508 // Look up this object. If it already is associated with a 1509 // DaikonVariable merge those variables. Otherwise, add it to 1510 // the map 1511 Object leader = TagEntry.find(atag); 1512 if (merge_dv.enabled()) { 1513 merge_dv.log("Leader for atag '%s' is '%s'%n", obj_str(atag), obj_str(leader)); 1514 } 1515 DaikonVariableInfo current = varmap.get(leader); 1516 merge_dv.log("Daikon variable for leader = %s%n", current); 1517 if (current != null) { 1518 merge_dv.log("**Merging %s and %s%n", current, dv); 1519 TagEntry.union(current, dv); 1520 } else { 1521 varmap.put(leader, dv); 1522 } 1523 } 1524 } else { 1525 // Ignore null and nonsensical tags. There is no reason to process 1526 // their children, because they can't have any with reasonable values 1527 if ((tag == null) || (tag == nonsensical) || (tag == nonsensical_list)) { 1528 debug_timing.log( 1529 " Variable %s : %d msecs%n", dv, System.currentTimeMillis() - start_millis); 1530 return; 1531 } 1532 1533 // Look up this object. If it already is associated with a 1534 // DaikonVariable merge those variables. Otherwise, add it to 1535 // the map 1536 Object leader = TagEntry.find(tag); 1537 if (merge_dv.enabled()) { 1538 merge_dv.log("Leader for tag '%s' is '%s'%n", obj_str(tag), obj_str(leader)); 1539 } 1540 DaikonVariableInfo current = varmap.get(leader); 1541 assert leader != null : "null leader for " + obj_str(tag); 1542 merge_dv.log("Daikon variable for leader = %s%n", current); 1543 if (current != null) { 1544 merge_dv.log("**Merging variable '%s' and '%s'%n", current, dv); 1545 TagEntry.union(current, dv); 1546 } else { 1547 varmap.put(leader, dv); 1548 } 1549 } 1550 1551 debug_timing.log(" Variable %s : %d msecs%n", dv, System.currentTimeMillis() - start_millis); 1552 1553 // Process all of the children 1554 for (DaikonVariableInfo child : dv) { 1555 Object child_obj; 1556 if ((child instanceof ArrayInfo) && ((ArrayInfo) child).getType().isPrimitive()) { 1557 // It's a primitive array. 1558 // System.out.printf("child array type %s = %s%n", ai, ai.getType()); 1559 Object[] arr_tags = field_map.get(tag); 1560 // System.out.printf("found arr_tag %s for arr %s%n", arr_tags, tag); 1561 // System.out.printf("tag values = %s%n", Arrays.toString (arr_tags)); 1562 child_obj = arr_tags; 1563 } else { 1564 // It's not a primitive array. 1565 child_obj = child.getMyValFromParentVal(obj); 1566 } 1567 merge_dv.indent(); 1568 merge_comparability(varmap, obj, child_obj, child); 1569 merge_dv.exdent(); 1570 } 1571 } 1572 1573 /** 1574 * Dumps out comparability information for all classes that were processed. 1575 * 1576 * @param pw PrintWriter to write on 1577 */ 1578 public static void printAllComparable(PrintWriter pw) { 1579 1580 for (ClassInfo ci : all_classes) { 1581 merge_class_comparability(ci); 1582 for (MethodInfo mi : ci.method_infos) { 1583 if (mi.is_class_initializer()) { 1584 continue; 1585 } 1586 // skip our added method 1587 if (mi.method_name.equals("equals_dcomp_instrumented")) { 1588 continue; 1589 } 1590 pw.println(); 1591 printComparable(pw, mi); 1592 } 1593 } 1594 } 1595 1596 /** 1597 * Dumps out comparability trace information for all classes that were processed. 1598 * 1599 * @param pw PrintWriter to write on 1600 */ 1601 public static void traceAllComparable(PrintWriter pw) { 1602 1603 for (ClassInfo ci : all_classes) { 1604 merge_class_comparability(ci); 1605 for (MethodInfo mi : ci.method_infos) { 1606 if (mi.is_class_initializer()) { 1607 continue; 1608 } 1609 if (mi.method_name.equals("equals_dcomp_instrumented")) { 1610 continue; 1611 } 1612 pw.println(); 1613 printComparableTraced(pw, mi); 1614 } 1615 } 1616 } 1617 1618 /** 1619 * Prints header information to the decls file. Should be called once before emitting any other 1620 * declarations. 1621 * 1622 * @param pw where to write output 1623 * @param className name of the top-level class (used only for printing comments) 1624 */ 1625 public static void printHeaderInfo(PrintWriter pw, String className) { 1626 1627 // Write the file header 1628 pw.println("// Declarations for " + className); 1629 pw.println( 1630 "// Declarations written " 1631 + LocalDateTime.now(ZoneId.systemDefault()) 1632 + " by daikon.DynComp"); 1633 pw.println(); 1634 pw.println("decl-version 2.0"); 1635 pw.println("var-comparability implicit"); 1636 pw.println(); 1637 } 1638 1639 /** 1640 * Dumps out .decl file information for all classes that were processed. 1641 * 1642 * @param pw where to write output 1643 */ 1644 public static void printDeclFile(PrintWriter pw) { 1645 1646 // Write the information for each class 1647 for (ClassInfo ci : all_classes) { 1648 if (!headerPrinted) { 1649 printHeaderInfo(pw, ci.class_name); 1650 headerPrinted = true; 1651 } 1652 printClassDecl(pw, ci); 1653 } 1654 debug_decl_print.log("finished %d classes%n", all_classes.size()); 1655 } 1656 1657 static int class_cnt = 0; 1658 static int method_cnt = 0; 1659 static int instance_var_cnt = 0; 1660 static int static_final_cnt = 0; 1661 static int hashcode_var_cnt = 0; 1662 static int hashcode_arr_cnt = 0; 1663 static int primitive_var_cnt = 0; 1664 static int tostring_cnt = 0; 1665 static int class_var_cnt = 0; 1666 static int this_instance_cnt = 0; 1667 static int other_instance_cnt = 0; 1668 static int other_cnt = 0; 1669 static int parameter_cnt = 0; 1670 static int static_cnt = 0; 1671 static int synthetic_cnt = 0; 1672 static int enum_cnt = 0; 1673 1674 /** Prints statistics about the number of decls to stdout. */ 1675 public static void decl_stats() { 1676 1677 for (ClassInfo ci : all_classes) { 1678 class_cnt++; 1679 System.out.printf("processing class %s%n", ci); 1680 add_dv_stats(ci.traversalClass); 1681 add_dv_stats(ci.traversalObject); 1682 for (MethodInfo mi : ci.method_infos) { 1683 if (mi.is_class_initializer()) { 1684 continue; 1685 } 1686 method_cnt++; 1687 System.out.printf(" Processing method %s [%d calls]%n", mi, mi.call_cnt); 1688 if (mi.traversalEnter == null) { 1689 System.out.printf(" Skipping method %s%n", mi); 1690 continue; 1691 } 1692 System.out.printf(" Enter%n"); 1693 add_dv_stats(mi.traversalEnter); 1694 for (Integer ii : mi.exit_locations) { 1695 System.out.printf(" Exit%d%n", ii); 1696 add_dv_stats(mi.traversalExit); 1697 } 1698 } 1699 } 1700 1701 // The section above output method count data for non-omitted user code. 1702 // The section below outputs method count data for all methods - including java runtime. 1703 System.out.printf("%ndisplaying all method counts%n"); 1704 for (String key : methodCountMap.keySet()) { 1705 System.out.printf(" method %s [%d calls]%n", key, methodCountMap.get(key)); 1706 } 1707 System.out.println(); 1708 1709 System.out.printf("Classes = %,d%n", class_cnt); 1710 System.out.printf("Methods = %,d%n", method_cnt); 1711 System.out.printf("------------------------------%n"); 1712 System.out.printf("Hashcodes = %,d%n", hashcode_var_cnt); 1713 System.out.printf("Hashcode arrays = %,d%n", hashcode_arr_cnt); 1714 System.out.printf("primitives = %,d%n", primitive_var_cnt); 1715 System.out.printf("------------------------------%n"); 1716 System.out.printf("tostring vars = %,d%n", tostring_cnt); 1717 System.out.printf("class vars = %,d%n", class_var_cnt); 1718 System.out.printf("Enums = %,d%n", enum_cnt); 1719 System.out.printf("Synthetic = %,d%n", synthetic_cnt); 1720 System.out.printf("static final vars = %,d%n", static_final_cnt); 1721 System.out.printf("static vars = %,d%n", static_cnt); 1722 System.out.printf("this instance vars = %,d%n", this_instance_cnt); 1723 System.out.printf("other instance vars = %,d%n", other_instance_cnt); 1724 System.out.printf("Parameters = %,d%n", parameter_cnt); 1725 System.out.printf("Others = %,d%n", other_cnt); 1726 } 1727 1728 private static void add_dv_stats(RootInfo root) { 1729 1730 if (root == null) { 1731 return; 1732 } 1733 List<DaikonVariableInfo> dv_list = root.tree_as_list(); 1734 for (DaikonVariableInfo dv : dv_list) { 1735 if (dv instanceof RootInfo) { 1736 continue; 1737 } 1738 if (!dv.declShouldPrint()) { 1739 continue; 1740 } 1741 // System.out.printf(" processing dv %s [%s]%n", dv, 1742 // dv.getTypeName()); 1743 if (dv.isHashcode()) { 1744 hashcode_var_cnt++; 1745 } else if (dv.isHashcodeArray()) { 1746 hashcode_arr_cnt++; 1747 } else { 1748 primitive_var_cnt++; 1749 } 1750 if (dv.getName().contains(".toString")) { 1751 tostring_cnt++; 1752 } else if (dv.getName().contains(DaikonVariableInfo.class_suffix)) { 1753 class_var_cnt++; 1754 } else if (dv instanceof FieldInfo) { 1755 Field field = ((FieldInfo) dv).getField(); 1756 int modifiers = field.getModifiers(); 1757 if (field.isEnumConstant()) { 1758 enum_cnt++; 1759 } else if (field.isSynthetic()) synthetic_cnt++; 1760 else if (Modifier.isStatic(modifiers) && Modifier.isFinal(modifiers)) static_final_cnt++; 1761 else if (Modifier.isStatic(modifiers)) static_cnt++; 1762 else if (dv.getName().startsWith("this")) this_instance_cnt++; 1763 else { 1764 other_instance_cnt++; 1765 } 1766 } else if (dv instanceof ParameterInfo) { 1767 parameter_cnt++; 1768 } else { 1769 other_cnt++; 1770 } 1771 } 1772 } 1773 1774 /** 1775 * Calculates and prints the declarations for the specified class. 1776 * 1777 * @param pw where to produce output 1778 * @param ci the class to write 1779 */ 1780 public static void printClassDecl(PrintWriter pw, ClassInfo ci) { 1781 1782 time_decl.log("Printing decl file for class %s%n", ci.class_name); 1783 time_decl.indent(); 1784 debug_decl_print.log("class %s%n", ci.class_name); 1785 1786 // Make sure that two variables have the same comparability at all 1787 // program points 1788 merge_class_comparability(ci); 1789 1790 // Write the class ppt 1791 String classPptName = ci.class_name + ":::CLASS"; 1792 pw.println("ppt " + classPptName); 1793 pw.println("ppt-type class"); 1794 printDeclVars(get_comparable(ci.traversalClass), ci.traversalClass, classPptName); 1795 pw.println(); 1796 time_decl.log("printed class ppt"); 1797 1798 // Write the object ppt 1799 String objectPptName = ci.class_name + ":::OBJECT"; 1800 pw.println("ppt " + objectPptName); 1801 pw.println("ppt-type object"); 1802 printDeclVars(get_comparable(ci.traversalObject), ci.traversalObject, objectPptName); 1803 pw.println(); 1804 time_decl.log("printed object ppt"); 1805 1806 // Print the information for each enter/exit point 1807 for (MethodInfo mi : ci.method_infos) { 1808 if (mi.is_class_initializer()) { 1809 continue; 1810 } 1811 debug_decl_print.log(" method %s%n", mi.method_name); 1812 printMethod(pw, mi); 1813 } 1814 1815 time_decl.log("finished class %s%n", ci.class_name); 1816 time_decl.exdent(); 1817 } 1818 1819 static long comp_list_ms = 0; 1820 static long ppt_name_ms = 0; 1821 static long decl_vars_ms = 0; 1822 static long total_ms = 0; 1823 1824 // static Stopwatch watch = new Stopwatch(); 1825 1826 /** 1827 * Prints a decl ENTER/EXIT records with comparability. Returns the list of comparabile DVSets for 1828 * the exit. 1829 * 1830 * @param pw where to produce output 1831 * @param mi the class to output 1832 * @return the list of comparabile DVSets for the exit 1833 */ 1834 public static List<DVSet> printMethod(PrintWriter pw, MethodInfo mi) { 1835 1836 // long start = System.currentTimeMillis(); 1837 // watch.reset(); 1838 1839 time_decl.log("Print decls for method '%s'", mi.method_name); 1840 time_decl.indent(); 1841 List<DVSet> l = get_comparable(mi.traversalEnter); 1842 // comp_list_ms += watch.snapshot(); watch.reset(); 1843 if (l == null) { 1844 return null; 1845 } 1846 time_decl.log("got %d comparable sets", l.size()); 1847 1848 // Print the enter point 1849 String enterPptName = clean_decl_name(DaikonWriter.methodEntryName(mi.member)); 1850 pw.println("ppt " + enterPptName); 1851 pw.println("ppt-type enter"); 1852 // ppt_name_ms += watch.snapshot(); watch.reset(); 1853 printDeclVars(l, mi.traversalEnter, enterPptName); 1854 // decl_vars_ms += watch.snapshot(); watch.reset(); 1855 pw.println(); 1856 time_decl.log("after enter"); 1857 1858 // Print the exit points 1859 l = get_comparable(mi.traversalExit); 1860 // comp_list_ms += watch.snapshot(); watch.reset(); 1861 1862 time_decl.log("got exit comparable sets"); 1863 for (Integer ii : mi.exit_locations) { 1864 String exitPptName = clean_decl_name(DaikonWriter.methodExitName(mi.member, ii)); 1865 pw.println("ppt " + exitPptName); 1866 pw.println("ppt-type subexit"); 1867 // ppt_name_ms += watch.snapshot(); watch.reset(); 1868 1869 time_decl.log("after exit clean_decl_name"); 1870 printDeclVars(l, mi.traversalExit, exitPptName); 1871 pw.println(); 1872 // decl_vars_ms += watch.snapshot(); watch.reset(); 1873 1874 } 1875 1876 // total_ms += System.currentTimeMillis() - start; 1877 time_decl.log("Finished processing method '%s'", mi.method_name); 1878 time_decl.exdent(); 1879 return l; 1880 } 1881 1882 /** Map from array name to comparability for its indices (if any). */ 1883 private static Map<String, Integer> arr_index_map; 1884 1885 /** Map from variable to its comparability. */ 1886 private static IdentityHashMap<DaikonVariableInfo, Integer> dv_comp_map; 1887 1888 /** Comparability value for a variable. */ 1889 private static int base_comp; 1890 1891 /** 1892 * Print the variables in sets to pw in DECL file format. Each variable in the same set is given 1893 * the same comparability. Constructed classname variables are made comparable to other classname 1894 * variables only. 1895 * 1896 * @param sets the comparability sets 1897 * @param dv_tree the tree of variables 1898 * @param pptName used only for debugging output 1899 */ 1900 private static void printDeclVars(List<DVSet> sets, RootInfo dv_tree, String pptName) { 1901 1902 time_decl.indent(); 1903 time_decl.log("printDeclVars start"); 1904 1905 debug_decl_print.log("printDeclVars(%s)%n", pptName); 1906 1907 // Map from array name to comparability for its indices (if any) 1908 arr_index_map = new LinkedHashMap<>(); 1909 1910 // Map from daikon variable to its comparability 1911 dv_comp_map = new IdentityHashMap<DaikonVariableInfo, Integer>(256); 1912 1913 // Initial comparability values 1914 int class_comp = 1; 1915 base_comp = 2; 1916 1917 // Loop through each set of comparable variables 1918 for (DVSet set : sets) { 1919 1920 if ((set.size() == 1) && (set.get(0) instanceof StaticObjInfo)) { 1921 continue; 1922 } 1923 1924 // Determine if the set has both hashcode variables and integer 1925 // variables. If it does, it is indicating index comparability 1926 boolean hashcode_vars = false; 1927 boolean non_hashcode_vars = false; 1928 // System.out.printf("Checking dv set %s%n", set); 1929 for (DaikonVariableInfo dv : set) { 1930 if (dv.isHashcode() || dv.isHashcodeArray()) { 1931 hashcode_vars = true; 1932 } else { 1933 non_hashcode_vars = true; 1934 } 1935 // System.out.printf("dv = %s, hashcode_var = %b%n", 1936 // dv, dv.isHashcode() || dv.isHashcodeArray()); 1937 } 1938 debug_decl_print.log( 1939 " %d vars in set, hashcode/non = %b/%b%n", 1940 set.size(), hashcode_vars, non_hashcode_vars); 1941 1942 // Loop through each variable and assign its comparability 1943 // Since hashcodes and their indices are in the same set, assign 1944 // hashcodes one higher comparability number. Note that there is 1945 // not necessarily an array child for a hashcode that is comparable 1946 // to an integer. This can happen when an array and a non-array object 1947 // become comparable to one another. An integer that is comparable 1948 // to the array will also be comparable to the non-array object, but 1949 // that comparability isn't interesting (and it can't be expressed) 1950 for (DaikonVariableInfo dv : set) { 1951 debug_decl_print.log(" dv %s [%s]%n", dv, System.identityHashCode(dv)); 1952 if (dv instanceof DaikonClassInfo) { 1953 dv_comp_map.put(dv, class_comp); 1954 assert set.size() == 1 : "odd set " + set; 1955 base_comp--; // negate increment of base_comp below 1956 } else if (dv.isHashcode() && non_hashcode_vars) { 1957 assert !dv_comp_map.containsKey(dv) : dv + " " + base_comp; 1958 dv_comp_map.put(dv, base_comp + 1); 1959 DaikonVariableInfo array_child = dv.array_child(); 1960 if (array_child != null) { 1961 // System.out.printf("array_index_map put: %s, %d%n", array_child.getName(), 1962 // base_comp); 1963 arr_index_map.put(array_child.getName(), base_comp); 1964 } 1965 } else { 1966 assert !dv_comp_map.containsKey(dv) : dv + " " + base_comp; 1967 dv_comp_map.put(dv, base_comp); 1968 } 1969 } 1970 1971 // Increment the comparability number to the next valid number 1972 base_comp++; 1973 if (hashcode_vars && non_hashcode_vars) { 1974 base_comp++; 1975 } 1976 } 1977 1978 time_decl.log("finished filling maps%n"); 1979 1980 // Loop through each variable and print out its comparability 1981 // Use the dv_tree rather than sets so that we print out in the 1982 // same order each time. Note that arrays get two comparablities, one 1983 // for the elements of the array and one for indices. Normally, these 1984 // comparabilities will be different, but if an index is placed in the 1985 // array the comparabilities can be the same. 1986 List<DaikonVariableInfo> dv_list = dv_tree.tree_as_list(); 1987 time_decl.log("built tree as list with %d elements", dv_list.size()); 1988 for (DaikonVariableInfo dv : dv_list) { 1989 if ((dv instanceof RootInfo) || (dv instanceof StaticObjInfo) || !dv.declShouldPrint()) { 1990 continue; 1991 } 1992 1993 declWriter.printDecl(null, dv, null, comparabilityProvider); 1994 } 1995 1996 time_decl.log("printDeclVars end%n"); 1997 map_info.log("dv_comp_map size: %d%n", dv_comp_map.size()); 1998 time_decl.exdent(); 1999 } 2000 2001 /** 2002 * Calculates a comparability value. 2003 * 2004 * @param dv variable to calculate comparability for 2005 * @param compare_ppt (not used) 2006 * @return string containing comparability value 2007 */ 2008 @Override 2009 public String getComparability(DaikonVariableInfo dv, DeclReader.DeclPpt compare_ppt) { 2010 int comp = dv_comp_map.get(dv); 2011 String comp_str = Integer.toString(comp); 2012 if (dv.isArray()) { 2013 String name = dv.getName(); 2014 // If we an array of CLASSNAME or TO_STRING get the index 2015 // comparability from the base array. 2016 if (name.endsWith(DaikonVariableInfo.class_suffix)) { 2017 name = name.substring(0, name.length() - DaikonVariableInfo.class_suffix.length()); 2018 } else if (name.endsWith(".toString")) { 2019 name = name.substring(0, name.length() - ".toString".length()); 2020 } 2021 Integer index_comp = arr_index_map.get(name); 2022 // System.out.printf("compare: %d [ %s ] ", comp, index_comp); 2023 if (index_comp != null) { 2024 // System.out.println(comp + "[" + index_comp + "]"); 2025 comp_str = comp_str + "[" + index_comp + "]"; 2026 } else { 2027 // There is no index comparability, so just set it to a unique value. 2028 // System.out.println(comp + "[" + base_comp + "]"); 2029 comp_str = comp_str + "[" + base_comp++ + "]"; 2030 } 2031 } 2032 return comp_str; 2033 } 2034 2035 /** 2036 * Prints comparability information for the enter and exit points of the specified method. By 2037 * default, outputs to {@code foo.txt-cset}. 2038 * 2039 * @param pw where to produce output 2040 * @param mi the method whose comparability to output 2041 */ 2042 /* TO DO: Find a way to make this work correctly without using normal 2043 * get_comparable. 2044 */ 2045 public static void printComparable(PrintWriter pw, MethodInfo mi) { 2046 2047 List<DVSet> l = get_comparable(mi.traversalEnter); 2048 pw.printf("Variable sets for %s enter%n", clean_decl_name(mi.toString())); 2049 if (l == null) { 2050 pw.printf(" not called%n"); 2051 } else { 2052 for (DVSet set : l) { 2053 if ((set.size() == 1) && (set.get(0) instanceof StaticObjInfo)) { 2054 continue; 2055 } 2056 ArrayList<String> stuff = skinyOutput(set, daikon.DynComp.abridged_vars); 2057 // To see "daikon.chicory.FooInfo:variable", change true to false 2058 pw.printf(" [%d] %s%n", stuff.size(), stuff); 2059 } 2060 } 2061 2062 l = get_comparable(mi.traversalExit); 2063 pw.printf("Variable sets for %s exit%n", clean_decl_name(mi.toString())); 2064 if (l == null) { 2065 pw.printf(" not called%n"); 2066 } else { 2067 for (DVSet set : l) { 2068 if ((set.size() == 1) && (set.get(0) instanceof StaticObjInfo)) { 2069 continue; 2070 } 2071 ArrayList<String> stuff = skinyOutput(set, daikon.DynComp.abridged_vars); 2072 // To see "daikon.chicory.FooInfo:variable", change true to false 2073 pw.printf(" [%d] %s%n", stuff.size(), stuff); 2074 } 2075 } 2076 } 2077 2078 /** 2079 * Dumps out comparability trace information for a single method. 2080 * 2081 * @param pw where to write output 2082 * @param mi the method to process 2083 */ 2084 public static void printComparableTraced(PrintWriter pw, MethodInfo mi) { 2085 List<DVSet> l = get_comparable(mi.traversalEnter); 2086 Map<DaikonVariableInfo, DVSet> t = get_comparable_traced(mi.traversalEnter); 2087 pw.printf("DynComp Traced Tree for %s enter%n", clean_decl_name(mi.toString())); 2088 if (t == null) { 2089 pw.printf(" not called%n"); 2090 } else { 2091 for (DVSet set : l) { 2092 if ((set.size() == 1) && (set.get(0) instanceof StaticObjInfo)) { 2093 continue; 2094 } 2095 printTree(pw, t, (DaikonVariableInfo) TagEntry.troot_find(set.get(0)), 0); 2096 pw.println(); 2097 } 2098 } 2099 pw.println(); 2100 2101 l = get_comparable(mi.traversalExit); 2102 t = get_comparable_traced(mi.traversalExit); 2103 pw.printf("DynComp Traced Tree for %s exit%n", clean_decl_name(mi.toString())); 2104 if (t == null) { 2105 pw.printf(" not called%n"); 2106 } else { 2107 for (DVSet set : l) { 2108 if ((set.size() == 1) && (set.get(0) instanceof StaticObjInfo)) { 2109 continue; 2110 } 2111 printTree(pw, t, (DaikonVariableInfo) TagEntry.troot_find(set.get(0)), 0); 2112 pw.println(); 2113 } 2114 } 2115 pw.println(); 2116 } 2117 2118 /** 2119 * Prints to [stream] the segment of the tree that starts at [node], interpreting [node] as 2120 * [depth] steps from the root. Requires a Map [tree] that represents a tree though key-value sets 2121 * of the form {@code <}parent, set of children{@code >}. 2122 * 2123 * @param pw where to write output 2124 * @param tree map parents to children 2125 * @param node starting point of tree to print 2126 * @param depth distance from node to root of tree 2127 */ 2128 static void printTree( 2129 PrintWriter pw, Map<DaikonVariableInfo, DVSet> tree, DaikonVariableInfo node, int depth) { 2130 2131 /* This method, for some reason, triggers a segfault due to the way 2132 * DVSets are handled conceptually. A trace-tree of one element creates 2133 * a key-value pair DVI foo → DVSet {foo}, whereas a trace-tree of 2134 * two elements creates a key-value pair DVI foo → DVSet {bar}. 2135 */ 2136 2137 if (depth == 0) { 2138 pw.printf("%s%n", skinyOutput(node, daikon.DynComp.abridged_vars)); 2139 if (tree.get(node) == null) { 2140 return; 2141 } 2142 for (DaikonVariableInfo child : tree.get(node)) { 2143 if (child != node) { 2144 printTree(pw, tree, child, depth + 1); 2145 } 2146 } 2147 } else { 2148 for (int i = 0; i < depth; i++) { 2149 pw.printf("--"); 2150 } 2151 pw.printf( 2152 "%s (%s)%n", 2153 skinyOutput(node, daikon.DynComp.abridged_vars), TagEntry.get_line_trace(node)); 2154 if (tree.get(node) == null) { 2155 return; 2156 } 2157 for (DaikonVariableInfo child : tree.get(node)) { 2158 if (child != node) { 2159 printTree(pw, tree, child, depth + 1); 2160 } 2161 } 2162 } 2163 } 2164 2165 /** 2166 * If on, returns an ArrayList of Strings that converts the usual DVInfo.toString() output to a 2167 * more readable form 2168 * 2169 * <p>e.g. "daikon.chicory.ParameterInfo:foo" becomes "Parameter foo" 2170 * 2171 * <p>"daikon.chicory.FieldInfo:this.foo" becomes "Field foo" 2172 */ 2173 private static ArrayList<String> skinyOutput(DVSet l, boolean on) { 2174 ArrayList<String> o = new ArrayList<>(); 2175 for (DaikonVariableInfo dvi : l) { 2176 o.add(skinyOutput(dvi, on)); 2177 } 2178 return o; 2179 } 2180 2181 private static String skinyOutput(DaikonVariableInfo dv, boolean on) { 2182 if (!on) { 2183 return dv.toString(); 2184 } 2185 String dvtxt = dv.toString(); 2186 String type = dvtxt.split(":")[0]; 2187 type = type.substring(type.lastIndexOf(".") + 1); 2188 String name = dvtxt.split(":")[1]; 2189 if (type.equals("ThisObjInfo")) { 2190 dvtxt = "this"; 2191 } else if (type.equals("ReturnInfo")) { 2192 dvtxt = "return"; 2193 } else if (type.endsWith("Info")) { 2194 type = type.substring(0, type.length() - 4); 2195 if (name.endsWith(DaikonVariableInfo.class_suffix)) { 2196 name = name.substring(0, name.length() - DaikonVariableInfo.class_suffix.length()); 2197 type = "Class of"; 2198 } 2199 if (name.startsWith("this.")) { 2200 name = name.substring(5); 2201 if (!type.endsWith("Field")) { 2202 type = (type + " Field").trim(); 2203 } 2204 } 2205 dvtxt = type + " " + name; 2206 } 2207 return dvtxt; 2208 } 2209 2210 /** Set of Daikon variables. Implements comparable on first DaikonVariable in each set. */ 2211 private static class DVSet extends ArrayList<DaikonVariableInfo> implements Comparable<DVSet> { 2212 static final long serialVersionUID = 20050923L; 2213 2214 @Pure 2215 @Override 2216 public int compareTo(@GuardSatisfied DVSet this, DVSet s1) { 2217 if (s1.size() == 0) { 2218 return 1; 2219 } else if (size() == 0) { 2220 return -1; 2221 } else { 2222 return this.get(0).compareTo(s1.get(0)); 2223 } 2224 } 2225 2226 public void sort() { 2227 Collections.sort(this); 2228 } 2229 } 2230 2231 /** 2232 * Gets a list of comparability sets of Daikon variables. If the method has never been executed 2233 * returns null (it would probably be better to return each variable in a separate set, but I 2234 * wanted to differentiate this case for now). 2235 * 2236 * <p>The sets are calculated by processing each daikon variable and adding it to a list 2237 * associated with the leader of that set. 2238 */ 2239 static @Nullable List<DVSet> get_comparable(RootInfo root) { 2240 2241 if (root == null) { 2242 return null; 2243 } 2244 2245 // List of all of the sets of comparable daikon variables 2246 IdentityHashMap<DaikonVariableInfo, DVSet> sets = 2247 new IdentityHashMap<DaikonVariableInfo, DVSet>(); 2248 2249 for (DaikonVariableInfo dv : root) { 2250 add_variable(sets, dv); 2251 } 2252 map_info.log("sets size: %d%n", sets.size()); 2253 2254 // Get each set, sort it, and add it to the list of all sets. Then sort 2255 // the list of all sets. The sorting is not critical except to create 2256 // a reproducible order. 2257 List<DVSet> set_list = new ArrayList<>(sets.size()); 2258 for (DVSet dvs : sets.values()) { 2259 dvs.sort(); 2260 set_list.add(dvs); 2261 } 2262 Collections.sort(set_list); 2263 2264 return set_list; 2265 } 2266 2267 /** 2268 * Returns a map representing the tree of tracers. Represents the tree as entries in a map with 2269 * each parent node as the key to a set contains all its children. The parameter RootInfo node is 2270 * included as a key to all its children. 2271 */ 2272 static @PolyNull Map<DaikonVariableInfo, DVSet> get_comparable_traced(@PolyNull RootInfo root) { 2273 if (root == null) { 2274 return null; 2275 } 2276 2277 // List of all of the parent-child relationships, where parent-child 2278 // represents the equivalence relation of being comparable. 2279 // The keyset of this Map is exactly the RootInfo node and the set of all 2280 // nodes that have children. 2281 // The valueset of this Map is exactly the set of all nodes. 2282 IdentityHashMap<DaikonVariableInfo, DVSet> sets = 2283 new IdentityHashMap<DaikonVariableInfo, DVSet>(256); 2284 2285 for (DaikonVariableInfo child : root) { 2286 if (child.declShouldPrint()) { 2287 add_variable_traced(sets, child); 2288 } 2289 } 2290 for (DVSet dvs : sets.values()) { 2291 dvs.sort(); 2292 } 2293 2294 return sets; 2295 } 2296 2297 static void add_variable_traced(Map<DaikonVariableInfo, DVSet> sets, DaikonVariableInfo dv) { 2298 try { 2299 DaikonVariableInfo parent = (DaikonVariableInfo) TagEntry.tracer_find(dv); 2300 DVSet set = sets.computeIfAbsent(parent, __ -> new DVSet()); 2301 set.add(dv); 2302 } catch (NullPointerException e) { 2303 throw new Error(e); 2304 } 2305 2306 for (DaikonVariableInfo child : dv) { 2307 add_variable_traced(sets, child); 2308 } 2309 } 2310 2311 /** 2312 * Merges comparability so that the same variable has the same comparability at all points in the 2313 * program point hierarchy. The comparability at the class/object points is calculated by merging 2314 * the comparability at each exit point (i.e., if two variables are in the same set at any exit 2315 * point, they are in the same set at the class point). That comparability is then applied back to 2316 * the exit points so that if two class variables are comparable at any exit point they are 2317 * comparable at each exit point. Finally exit point comparability is merged to the enter point so 2318 * that their comparabilities are the same. 2319 * 2320 * <p>This is not the only valid definition of comparability but it is the one that Daikon expects 2321 * because of how equality sets are handled. 2322 */ 2323 static void merge_class_comparability(ClassInfo ci) { 2324 2325 // Get the variables at the object and class point 2326 assert ci.traversalObject != null : ci; 2327 assert ci.traversalClass != null : ci; 2328 // ci.init_traversal (depth); 2329 2330 // If any methods have not been executed, create their information 2331 // now (which will note all of their variables as not comparable) 2332 for (MethodInfo mi : ci.method_infos) { 2333 if (mi.is_class_initializer()) { 2334 continue; 2335 } 2336 if (mi.traversalEnter == null) { 2337 // mi.initViaReflection(); 2338 mi.init_traversal(depth); 2339 // System.out.printf("Warning: Method %s never executed%n", mi); 2340 } 2341 } 2342 2343 // Merge the comparability from each exit point into the object point 2344 for (MethodInfo mi : ci.method_infos) { 2345 if (mi.is_class_initializer()) { 2346 continue; 2347 } 2348 merge_dv_comparability(mi.traversalExit, mi.traversalEnter, "Merging exit to enter: " + mi); 2349 merge_dv_comparability(mi.traversalExit, ci.traversalObject, "Merging exit to object: " + mi); 2350 merge_dv_comparability(mi.traversalEnter, ci.traversalObject, "Merging enter to object" + mi); 2351 } 2352 2353 // Merge the comparability from the object point back to each exit point 2354 for (MethodInfo mi : ci.method_infos) { 2355 if (mi.is_class_initializer()) { 2356 continue; 2357 } 2358 merge_dv_comparability(ci.traversalObject, mi.traversalExit, "Merging object to exit: " + mi); 2359 } 2360 2361 // Merge the comparability for each exit point back to the enter 2362 for (MethodInfo mi : ci.method_infos) { 2363 if (mi.is_class_initializer()) { 2364 continue; 2365 } 2366 merge_dv_comparability(mi.traversalExit, mi.traversalEnter, "Merging exit to enter: " + mi); 2367 } 2368 2369 // Merge the object comparability to the class 2370 merge_dv_comparability(ci.traversalObject, ci.traversalClass, "Merging object to class: " + ci); 2371 } 2372 2373 /** 2374 * Merges any variables in the dest tree that are in the same set in the source tree. The source 2375 * tree's comparability is unchanged. Variables are identified by name. 2376 * 2377 * @param src the comparability to read 2378 * @param dest the comparability to modify 2379 * @param debuginfo information about this method call, for debugging 2380 */ 2381 static void merge_dv_comparability(RootInfo src, RootInfo dest, String debuginfo) { 2382 2383 debug_merge_comp.log("merge_dv_comparability: %s%n", debuginfo); 2384 2385 debug_merge_comp.indent(); 2386 2387 // Create a map relating destination names to their variables 2388 Map<String, DaikonVariableInfo> dest_map = new LinkedHashMap<>(); 2389 for (DaikonVariableInfo dest_var : varlist(dest)) { 2390 dest_map.put(dest_var.getName(), dest_var); 2391 } 2392 2393 // Get the variable sets for the source 2394 List<DVSet> src_sets = get_comparable(src); 2395 2396 // Merge any destination variables that are in the same source set 2397 for (DVSet src_set : src_sets) { 2398 if (src_set.size() == 1) { 2399 continue; 2400 } 2401 DaikonVariableInfo dest_canonical = null; 2402 for (DaikonVariableInfo src_var : src_set) { 2403 if (dest_canonical == null) { 2404 dest_canonical = dest_map.get(src_var.getName()); 2405 continue; 2406 } 2407 DaikonVariableInfo dest_var = dest_map.get(src_var.getName()); 2408 if (dest_var != null) { 2409 TagEntry.union(dest_canonical, dest_var); 2410 debug_merge_comp.log( 2411 "merged '%s' [%s] and '%s' [%s]%n", 2412 dest_canonical, 2413 System.identityHashCode(dest_canonical), 2414 dest_var, 2415 System.identityHashCode(dest_var)); 2416 } 2417 } 2418 } 2419 debug_merge_comp.exdent(); 2420 } 2421 2422 /** 2423 * Adds this daikon variable and all of its children into their appropriate sets (those of their 2424 * leader) in sets. 2425 */ 2426 static void add_variable(Map<DaikonVariableInfo, DVSet> sets, DaikonVariableInfo dv) { 2427 2428 // Add this variable into the set of its leader 2429 if (dv.declShouldPrint()) { 2430 DaikonVariableInfo leader = (DaikonVariableInfo) TagEntry.find(dv); 2431 DVSet set = sets.computeIfAbsent(leader, __ -> new DVSet()); 2432 set.add(dv); 2433 } 2434 2435 // Process the children 2436 for (DaikonVariableInfo child : dv) { 2437 add_variable(sets, child); 2438 } 2439 } 2440 2441 /** 2442 * Pushes the tag associated with field_num in obj on the tag stack. A tag value must have been 2443 * previously stored for this field. 2444 * 2445 * @param obj where to store tag 2446 * @param field_num which field within obj to store into 2447 */ 2448 public static void push_field_tag(Object obj, int field_num) { 2449 if (debug) { 2450 System.out.printf("In push_field_tag%n"); 2451 } 2452 // Since instance variables by default initialize to zero, any field 2453 // can possibly be read before it is set. 2454 push_field_tag_null_ok(obj, field_num); 2455 } 2456 2457 /** 2458 * Pushes the tag associated with field_num in obj on the tag stack. If tag storage for this 2459 * object has not been previously allocated it is allocated now and a tag is allocated for this 2460 * field. This should only be called for objects whose fields can be read without having been 2461 * previously written (in Java). 2462 * 2463 * @param obj where to store tag 2464 * @param field_num which field within obj to store into 2465 */ 2466 public static void push_field_tag_null_ok(Object obj, int field_num) { 2467 if (debug) { 2468 System.out.printf("In push_field_tag_null_ok%n"); 2469 } 2470 2471 ThreadData td = thread_to_data.get(Thread.currentThread()); 2472 Object[] obj_tags = field_map.get(obj); 2473 if (obj_tags != null) { 2474 Object tag = obj_tags[field_num]; 2475 if (tag == null) { 2476 Throwable stack_trace = new Throwable(); 2477 obj_tags[field_num] = 2478 tag = 2479 new UninitFieldTag( 2480 obj.getClass().getName() + ":uninit-field:" + field_num, stack_trace); 2481 } 2482 td.tag_stack.push(tag); 2483 if (debug_primitive.enabled()) { 2484 debug_primitive.log( 2485 "push_field_tag %s %d = %s%n", obj_str(obj), field_num, obj_tags[field_num]); 2486 } 2487 } else { 2488 int fcnt = num_prim_fields(obj.getClass()); 2489 assert field_num < fcnt : obj.getClass() + " " + field_num + " " + fcnt; 2490 obj_tags = new Object[fcnt]; 2491 field_map.put(obj, obj_tags); 2492 debug_primitive.log("push_field_tag: Created tag storage%n"); 2493 Throwable stack_trace = new Throwable(); 2494 Object tag = 2495 new UninitFieldTag(obj.getClass().getName() + ":uninit-field" + field_num, stack_trace); 2496 obj_tags[field_num] = tag; 2497 td.tag_stack.push(tag); 2498 if (debug_primitive.enabled()) { 2499 debug_primitive.log("push_field_tag %s %d = %s%n", obj_str(obj), field_num, tag); 2500 } 2501 } 2502 if (debug_tag_frame) { 2503 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2504 } 2505 } 2506 2507 /** 2508 * Pops the tag from the top of the tag stack and stores it in the tag storage for the specified 2509 * field of the specified object. If tag storage was not previously allocated, it is allocated 2510 * now. 2511 * 2512 * @param obj where to store tag 2513 * @param field_num which field within obj to store into 2514 */ 2515 public static void pop_field_tag(Object obj, int field_num) { 2516 if (debug) { 2517 System.out.printf("In pop_field_tag%n"); 2518 } 2519 2520 ThreadData td = thread_to_data.get(Thread.currentThread()); 2521 // Look for the tag storage for this object 2522 Object[] obj_tags = field_map.get(obj); 2523 2524 // If none has been allocated, determine how many locations are 2525 // required (the number of primitive fields), allocate the space, 2526 // and associate it with the object. 2527 if (obj_tags == null) { 2528 int fcnt = num_prim_fields(obj.getClass()); 2529 assert field_num < fcnt : obj.getClass() + " " + field_num + " " + fcnt; 2530 obj_tags = new Object[fcnt]; 2531 field_map.put(obj, obj_tags); 2532 debug_primitive.log("pop_field_tag: Created tag storage%n"); 2533 } 2534 2535 // Pop the tag off of the stack and assign into the tag storage for 2536 // this field. 2537 assert td.tag_stack.peek() != method_marker; 2538 Object tag = td.tag_stack.pop(); 2539 assert tag != null : "Object " + obj.getClass() + " '" + obj + "' field_num " + field_num; 2540 obj_tags[field_num] = tag; 2541 if (debug_primitive.enabled()) { 2542 debug_primitive.log( 2543 "pop_field_tag (%s %d = %s%n", obj_str(obj), field_num, obj_tags[field_num]); 2544 } 2545 if (debug_tag_frame) { 2546 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2547 } 2548 } 2549 2550 /** Return the number of primitive fields in clazz and all of its superclasses. */ 2551 public static int num_prim_fields(Class<?> clazz) { 2552 if (clazz == Object.class) { 2553 return 0; 2554 } else { 2555 int field_cnt = num_prim_fields(clazz.getSuperclass()); 2556 for (Field f : clazz.getDeclaredFields()) { 2557 if (f.getType().isPrimitive()) { 2558 field_cnt++; 2559 } 2560 } 2561 return field_cnt; 2562 } 2563 } 2564 2565 /** 2566 * Handle a binary operation on the two items at the top of the tag stack. Binary operations pop 2567 * the two items off of the top of the stack perform an operation and push the result back on the 2568 * stack. The tags of the two items on the top of the stack must thus be merged and a 2569 * representative tag pushed back on the stack. 2570 */ 2571 public static void binary_tag_op() { 2572 ThreadData td = thread_to_data.get(Thread.currentThread()); 2573 debug_primitive.log("binary tag op%n"); 2574 assert td.tag_stack.peek() != method_marker; 2575 Object tag1 = td.tag_stack.pop(); 2576 assert td.tag_stack.peek() != method_marker; 2577 TagEntry.union(tag1, td.tag_stack.peek()); 2578 if (debug_tag_frame) { 2579 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2580 } 2581 } 2582 2583 /** 2584 * Handles an i_cmpXX operation. This opcode compares the two integers on the top of the stack and 2585 * jumps accordingly. Thus the two tags on the top of the stack are popped from the tag stack and 2586 * merged. Very similar to binary_tag_op except that nothing is pushed back on the tag stack. 2587 */ 2588 public static void cmp_op() { 2589 ThreadData td = thread_to_data.get(Thread.currentThread()); 2590 debug_primitive.log("cmp_op%n"); 2591 assert td.tag_stack.peek() != method_marker; 2592 Object tag1 = td.tag_stack.pop(); 2593 assert td.tag_stack.peek() != method_marker; 2594 TagEntry.union(tag1, td.tag_stack.pop()); 2595 if (debug_tag_frame) { 2596 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2597 } 2598 // debug_print_call_stack(); 2599 } 2600 2601 /** Handles a dup opcode on a primitive. */ 2602 public static void dup() { 2603 ThreadData td = thread_to_data.get(Thread.currentThread()); 2604 debug_primitive.log("dup%n"); 2605 assert td.tag_stack.peek() != method_marker; 2606 td.tag_stack.push(td.tag_stack.peek()); 2607 if (debug_tag_frame) { 2608 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2609 } 2610 } 2611 2612 /** Handles a dup_x1 opcode on a primitive. */ 2613 public static void dup_x1() { 2614 ThreadData td = thread_to_data.get(Thread.currentThread()); 2615 debug_primitive.log("dup_x1%n"); 2616 assert td.tag_stack.peek() != method_marker; 2617 Object top = td.tag_stack.pop(); 2618 assert td.tag_stack.peek() != method_marker; 2619 Object nxt = td.tag_stack.pop(); 2620 td.tag_stack.push(top); 2621 td.tag_stack.push(nxt); 2622 td.tag_stack.push(top); 2623 if (debug_tag_frame) { 2624 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2625 } 2626 } 2627 2628 /** 2629 * Handles a dup_x2 opcode on a primitive. Currently only support category 1 computational types. 2630 */ 2631 public static void dup_x2() { 2632 ThreadData td = thread_to_data.get(Thread.currentThread()); 2633 debug_primitive.log("dup_x2%n"); 2634 assert td.tag_stack.peek() != method_marker; 2635 Object top = td.tag_stack.pop(); 2636 assert td.tag_stack.peek() != method_marker; 2637 Object tag1 = td.tag_stack.pop(); 2638 assert td.tag_stack.peek() != method_marker; 2639 Object tag2 = td.tag_stack.pop(); 2640 td.tag_stack.push(top); 2641 td.tag_stack.push(tag2); 2642 td.tag_stack.push(tag1); 2643 td.tag_stack.push(top); 2644 if (debug_tag_frame) { 2645 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2646 } 2647 } 2648 2649 /** Handles a dup2 opcode on a primitive. */ 2650 public static void dup2() { 2651 ThreadData td = thread_to_data.get(Thread.currentThread()); 2652 debug_primitive.log("dup2%n"); 2653 assert td.tag_stack.peek() != method_marker; 2654 Object top = td.tag_stack.pop(); 2655 assert td.tag_stack.peek() != method_marker; 2656 Object tag1 = td.tag_stack.pop(); 2657 td.tag_stack.push(tag1); 2658 td.tag_stack.push(top); 2659 td.tag_stack.push(tag1); 2660 td.tag_stack.push(top); 2661 if (debug_tag_frame) { 2662 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2663 } 2664 } 2665 2666 /** Handles a dup2_x1 opcode on a primitive. */ 2667 public static void dup2_x1() { 2668 ThreadData td = thread_to_data.get(Thread.currentThread()); 2669 debug_primitive.log("dup2_x1%n"); 2670 assert td.tag_stack.peek() != method_marker; 2671 Object top = td.tag_stack.pop(); 2672 assert td.tag_stack.peek() != method_marker; 2673 Object tag1 = td.tag_stack.pop(); 2674 assert td.tag_stack.peek() != method_marker; 2675 Object tag2 = td.tag_stack.pop(); 2676 td.tag_stack.push(tag1); 2677 td.tag_stack.push(top); 2678 td.tag_stack.push(tag2); 2679 td.tag_stack.push(tag1); 2680 td.tag_stack.push(top); 2681 if (debug_tag_frame) { 2682 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2683 } 2684 } 2685 2686 /** Handles a dup2_x2 opcode on a primitive. */ 2687 public static void dup2_x2() { 2688 ThreadData td = thread_to_data.get(Thread.currentThread()); 2689 debug_primitive.log("dup2_x2%n"); 2690 assert td.tag_stack.peek() != method_marker; 2691 Object top = td.tag_stack.pop(); 2692 assert td.tag_stack.peek() != method_marker; 2693 Object tag1 = td.tag_stack.pop(); 2694 assert td.tag_stack.peek() != method_marker; 2695 Object tag2 = td.tag_stack.pop(); 2696 assert td.tag_stack.peek() != method_marker; 2697 Object tag3 = td.tag_stack.pop(); 2698 td.tag_stack.push(tag1); 2699 td.tag_stack.push(top); 2700 td.tag_stack.push(tag3); 2701 td.tag_stack.push(tag2); 2702 td.tag_stack.push(tag1); 2703 td.tag_stack.push(top); 2704 if (debug_tag_frame) { 2705 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2706 } 2707 } 2708 2709 /** Swaps the two elements on the top of the tag stack. */ 2710 public static void swap() { 2711 ThreadData td = thread_to_data.get(Thread.currentThread()); 2712 debug_primitive.log("swap%n"); 2713 assert td.tag_stack.peek() != method_marker; 2714 Object top = td.tag_stack.pop(); 2715 assert td.tag_stack.peek() != method_marker; 2716 Object tag1 = td.tag_stack.pop(); 2717 td.tag_stack.push(top); 2718 td.tag_stack.push(tag1); 2719 if (debug_tag_frame) { 2720 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2721 } 2722 } 2723 2724 /** 2725 * Handles the various primitive (int, double, etc) array load instructions. The array and its 2726 * index are made comparable. The tag for the index is removed from the tag stack and the tag for 2727 * the array element is pushed on the stack. 2728 * 2729 * @param arr_ref array reference 2730 * @param index index into array 2731 */ 2732 public static void primitive_array_load(Object arr_ref, int index) { 2733 debug_primitive.log("primitive_array_load%n"); 2734 // Since instance variables by default initialize to zero, any field 2735 // can possibly be read before it is set. 2736 primitive_array_load_null_ok(arr_ref, index); 2737 } 2738 2739 /** 2740 * Handles the various primitive (int, double, etc) array load instructions. The array and its 2741 * index are made comparable. The tag for the index is removed from the tag stack and the tag for 2742 * the array element is pushed on the stack. Unlike primitive_array_load(), this method handles 2743 * array elements whose tags have not previously been set. This can happen when the JVM sets an 2744 * array element directly and there is no corresponding java code that can set the tag. 2745 * 2746 * @param arr_ref array reference 2747 * @param index index into array 2748 */ 2749 public static void primitive_array_load_null_ok(Object arr_ref, int index) { 2750 ThreadData td = thread_to_data.get(Thread.currentThread()); 2751 debug_primitive.log("primitive_array_load_null_ok%n"); 2752 // Get the tag for the index and mark it as comparable with the array 2753 assert td.tag_stack.peek() != method_marker; 2754 Object index_tag = td.tag_stack.pop(); 2755 if (arr_ref == null) { 2756 if (debug_tag_frame) { 2757 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2758 } 2759 return; 2760 } 2761 if (debug_arr_index.enabled()) { 2762 debug_arr_index.log("Merging array '%s' and index '%s'", obj_str(arr_ref), index_tag); 2763 } 2764 if (merge_arrays_and_indices) { 2765 TagEntry.union(arr_ref, index_tag); 2766 } 2767 2768 // Push the tag for the element on the tag stack. 2769 Object[] obj_tags = field_map.get(arr_ref); 2770 if (obj_tags != null) { 2771 Object tag = obj_tags[index]; 2772 if (tag == null) { 2773 obj_tags[index] = tag = new UninitArrayElem(); 2774 } 2775 td.tag_stack.push(tag); 2776 if (debug_primitive.enabled()) { 2777 debug_primitive.log( 2778 "arrayload null-ok %s[%d] = %s%n", obj_str(arr_ref), index, obj_str(obj_tags[index])); 2779 } 2780 } else { 2781 int length = Array.getLength(arr_ref); 2782 obj_tags = new Object[length]; 2783 field_map.put(arr_ref, obj_tags); 2784 Object tag = new UninitArrayElem(); 2785 obj_tags[index] = tag; 2786 td.tag_stack.push(tag); 2787 if (debug_primitive.enabled()) { 2788 debug_primitive.log("arrayload null-ok %s[%d] = null%n", obj_str(arr_ref), index); 2789 } 2790 } 2791 if (debug_tag_frame) { 2792 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2793 } 2794 } 2795 2796 /** 2797 * Handles the aaload instruction. The arry and its index are made comparable. The tag for the 2798 * index is removed from the tag stack. 2799 * 2800 * @param arr_ref array reference 2801 * @param index index into array 2802 */ 2803 public static void ref_array_load(Object arr_ref, int index) { 2804 ThreadData td = thread_to_data.get(Thread.currentThread()); 2805 debug_primitive.log("ref_array_load%n"); 2806 // Get the tag for the index and mark it as comparable with the array 2807 assert td.tag_stack.peek() != method_marker; 2808 Object index_tag = td.tag_stack.pop(); 2809 if (debug_tag_frame) { 2810 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2811 } 2812 if (arr_ref == null) { 2813 return; 2814 } 2815 if (debug_arr_index.enabled()) { 2816 debug_arr_index.log("Merging array '%s' and index '%s'", obj_str(arr_ref), index_tag); 2817 } 2818 if (merge_arrays_and_indices) { 2819 TagEntry.union(arr_ref, index_tag); 2820 } 2821 } 2822 2823 /** 2824 * Allocate a new tag for the constant and push it on the tag stack. Note that this allocates a 2825 * new tag each time the constant is pushed. If the same code is executed multiple time (eg, in a 2826 * loop), and different values interact with the constant each time, those values will not end up 2827 * comparable to each other. 2828 */ 2829 public static void push_const() { 2830 ThreadData td = thread_to_data.get(Thread.currentThread()); 2831 Object tag = new Constant(); 2832 debug_primitive.log("push literal constant tag: %s%n", tag); 2833 td.tag_stack.push(tag); 2834 if (debug_tag_frame) { 2835 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 2836 } 2837 2838 // debug_print_call_stack(); 2839 } 2840 2841 /** 2842 * Marks the specified class as initialized. We don't look at static variables in classes until 2843 * they are initialized. 2844 * 2845 * @param classname class to mark initialized 2846 */ 2847 public static void set_class_initialized(String classname) { 2848 debug_primitive.log("set_class_initialized: %s%n", classname); 2849 initialized_eclassses.add(classname); 2850 } 2851 2852 /** 2853 * Returns whether or not the specified class is initialized. 2854 * 2855 * @param clazz class to check 2856 * @return true if clazz has been initialized 2857 */ 2858 @Pure 2859 public static boolean is_class_initialized(Class<?> clazz) { 2860 debug_primitive.log("is_class_initialized%n"); 2861 return initialized_eclassses.contains(clazz.getName()); 2862 } 2863 2864 /** Returns the name of the method that called the caller of caller_name(). */ 2865 private static String caller_name() { 2866 2867 Throwable stack = new Throwable("caller"); 2868 StackTraceElement[] ste_arr = stack.getStackTrace(); 2869 StackTraceElement ste = ste_arr[2]; 2870 // If JDK 11 runtime transfer method, need to skip another level. 2871 if (ste.getClassName().equals("java.lang.DCRuntime")) { 2872 ste = ste_arr[3]; 2873 } 2874 return ste.getClassName() + "." + ste.getMethodName(); 2875 } 2876 2877 /** 2878 * Returns a string description of the object that includes its class, identity hash code, and the 2879 * result of its toString() function - if it differs from the default implementation. Note that 2880 * the call to toString() may have unintended side effects. Hence, all calls to obj_str are 2881 * protected by debug flag checks or debug logging enabled() checks. 2882 * 2883 * @param obj object to be described 2884 * @return object description 2885 */ 2886 private static String obj_str(Object obj) { 2887 2888 if (obj == null) { 2889 return "<null>"; 2890 } else { 2891 String tostring; 2892 try { 2893 tostring = obj.toString(); 2894 } catch (Exception e) { 2895 // We use System.identityHashCode(obj) as obj.hashCode() can fail. 2896 tostring = 2897 "toString of " 2898 + obj.getClass().getName() 2899 + "@" 2900 + Integer.toHexString(System.identityHashCode(obj)) 2901 + " failed"; 2902 } 2903 String default_tostring = 2904 String.format("%s@%s", obj.getClass().getName(), System.identityHashCode(obj)); 2905 if (tostring.equals(default_tostring)) { 2906 return tostring; 2907 } else { 2908 // Limit display of object contents to 60 characters. 2909 return String.format( 2910 "%s [%s]", 2911 default_tostring, org.apache.commons.lang3.StringUtils.abbreviate(tostring, 60)); 2912 } 2913 } 2914 } 2915 2916 /** 2917 * Returns all of the daikonvariables in the tree rooted at dvi. 2918 * 2919 * @param dvi the tree of variables 2920 * @return all the daikonvarables in the tree 2921 */ 2922 private static List<DaikonVariableInfo> varlist(DaikonVariableInfo dvi) { 2923 2924 List<DaikonVariableInfo> list = new ArrayList<>(); 2925 list.add(dvi); 2926 for (DaikonVariableInfo child : dvi) { 2927 list.addAll(varlist(child)); 2928 } 2929 return list; 2930 } 2931 2932 /** 2933 * Returns the name of the tag field that corresponds to the specified field. 2934 * 2935 * @param field_name field name 2936 * @return tag field name 2937 */ 2938 public static String tag_field_name(String field_name) { 2939 debug_primitive.log("tag_field_name: %s%n", field_name); 2940 return (field_name + "__$tag"); 2941 } 2942 2943 private static Matcher jdk_decl_matcher = 2944 Pattern.compile("(, )?java.lang.DCompMarker( marker)?").matcher(""); 2945 private static Matcher non_jdk_decl_matcher = 2946 Pattern.compile("(, )?daikon.dcomp.DCompMarker( marker)?").matcher(""); 2947 2948 /** Removes DCompMarker from the signature. */ 2949 public static String clean_decl_name(String decl_name) { 2950 2951 if (DCInstrument.jdk_instrumented) { 2952 jdk_decl_matcher.reset(decl_name); 2953 return jdk_decl_matcher.replaceFirst(""); 2954 } else { 2955 non_jdk_decl_matcher.reset(decl_name); 2956 return non_jdk_decl_matcher.replaceFirst(""); 2957 } 2958 } 2959 2960 /** 2961 * Abstract base class for code that gets the tag associated with a particular field. There are 2962 * specific implementors for the various types of fields. FieldTag instances are stored in 2963 * FieldInfo so that tags can be efficiently obtained. 2964 */ 2965 public abstract static class FieldTag { 2966 2967 /** 2968 * Gets the tag for the field. 2969 * 2970 * @param parent object that contains the field (if any) 2971 * @param obj value of the field itself (if available and if it's an object) 2972 * @return the tag for the field 2973 */ 2974 abstract Object get_tag(Object parent, Object obj); 2975 } 2976 2977 /** 2978 * Class that gets the tag for static primitive fields. We retrieve the static tag by using the 2979 * same method as we use during run time to push the tag on the tag stack. 2980 */ 2981 public static class StaticPrimitiveTag extends FieldTag { 2982 2983 Method get_tag; 2984 2985 /** Initialize with information from the field. */ 2986 StaticPrimitiveTag(FieldInfo fi) { 2987 assert fi.isStatic(); 2988 assert fi.isPrimitive(); 2989 Field field = fi.getField(); 2990 Class<?> clazz = field.getDeclaringClass(); 2991 String name = 2992 DCInstrument.tag_method_name(DCInstrument.GET_TAG, clazz.getName(), field.getName()); 2993 try { 2994 get_tag = clazz.getMethod(name); 2995 } catch (Exception e) { 2996 throw new Error("can't find tag method " + name, e); 2997 } 2998 } 2999 3000 /** Return the tag associated with this field. */ 3001 @Override 3002 Object get_tag(Object parent, Object obj) { 3003 Object tag; 3004 // jhp - not sure why these are not null... 3005 // assert parent == null && obj == null 3006 // : " parent/obj = " + obj_str(parent) + "/" + obj_str(obj); 3007 try { 3008 ThreadData td = thread_to_data.get(Thread.currentThread()); 3009 Object ret_val = get_tag.invoke(parent); 3010 assert ret_val == null; 3011 assert td.tag_stack.peek() != method_marker; 3012 tag = td.tag_stack.pop(); 3013 assert tag != null; 3014 if (debug_tag_frame) { 3015 System.out.printf("tag stack size: %d%n", td.tag_stack.size()); 3016 } 3017 } catch (Exception e) { 3018 throw new Error("can't execute tag method " + get_tag, e); 3019 } 3020 return tag; 3021 } 3022 } 3023 3024 /** 3025 * Class that gets the tag for a static reference variable. The tag for a reference variable is 3026 * the object itself, so that is obtained via reflection. 3027 */ 3028 public static class StaticReferenceTag extends FieldTag { 3029 3030 /** Corresponding java field. */ 3031 Field field; 3032 3033 /** Set to true when the class containing the field is initialized. */ 3034 boolean is_class_initialized = false; 3035 3036 /** Class that contains the field. */ 3037 Class<?> declaring_class; 3038 3039 /** Initialize for this field. */ 3040 public StaticReferenceTag(FieldInfo fi) { 3041 3042 assert fi.isStatic(); 3043 assert !fi.isPrimitive(); 3044 field = fi.getField(); 3045 declaring_class = field.getDeclaringClass(); 3046 } 3047 3048 /** Gets the tag for this static reference. */ 3049 @Override 3050 @SuppressWarnings("deprecation") // in Java 9+, use canAccess instead of isAccessible 3051 public Object get_tag(Object parent, Object obj) { 3052 3053 // assert parent == null && obj == null; 3054 if (!is_class_initialized) { 3055 if (is_class_initialized(declaring_class)) { 3056 if (!field.isAccessible()) { 3057 field.setAccessible(true); 3058 } 3059 is_class_initialized = true; 3060 } else { 3061 return nonsensical; 3062 } 3063 } 3064 3065 try { 3066 return field.get(null); 3067 } catch (Exception e) { 3068 throw new RuntimeException("Can't get val for static field " + field, e); 3069 } 3070 } 3071 } 3072 3073 /** 3074 * Class that gets the list of tags for primitive arrays. Note that primitive arrays can both be 3075 * actual arrays of primitives and also arrays of classes containing primitives. In the second 3076 * case, there is a separate object that contains each of the 'array' values. 3077 */ 3078 public static class PrimitiveArrayTag extends FieldTag { 3079 3080 /** The field number for this field inside its object. */ 3081 int field_num; 3082 3083 public PrimitiveArrayTag(FieldInfo fi) { 3084 assert !fi.isStatic() && fi.isPrimitive() && fi.isArray(); 3085 field_num = fi.get_field_num(); 3086 } 3087 3088 /** Returns a list of object tags. */ 3089 @Override 3090 public Object get_tag(Object parent, Object obj) { 3091 3092 // Object is an array of objects containing each item 3093 // assert obj == null: "primitive array object = " + obj_str (obj); 3094 @SuppressWarnings("unchecked") 3095 List<Object> parent_list = (List<Object>) parent; 3096 List<Object> tag_list = new ArrayList<>(parent_list.size()); 3097 for (Object parent_element : parent_list) { 3098 Object[] tags = field_map.get(parent_element); 3099 if (tags == null) { 3100 tag_list.add(nonsensical); 3101 } else { 3102 tag_list.add(tags[field_num]); 3103 } 3104 } 3105 return tag_list; 3106 } 3107 } 3108 3109 /** 3110 * Class that gets the tag for a primitive instance field. Each object with primitive fields has a 3111 * corresponding tag array in field map. The tag for a particular field is stored at that fields 3112 * offset in the tag array. 3113 */ 3114 public static class PrimitiveTag extends FieldTag { 3115 3116 int field_num; 3117 3118 public PrimitiveTag(FieldInfo fi) { 3119 assert !fi.isStatic() && fi.isPrimitive() && !fi.isArray(); 3120 field_num = fi.get_field_num(); 3121 } 3122 3123 @Override 3124 public Object get_tag(Object parent, Object obj) { 3125 3126 // obj is the wrapper for the primitive 3127 // assert obj == null: "primitive object = " + obj_str (obj); 3128 Object[] tags = field_map.get(parent); 3129 if (tags == null) { 3130 return nonsensical; // happens if field has never been assigned to 3131 } else { 3132 return tags[field_num]; 3133 } 3134 } 3135 } 3136 3137 /** 3138 * Class that returns the tag for a reference instance field. In this case, the tag is just the 3139 * object itself. 3140 */ 3141 public static class ReferenceTag extends FieldTag { 3142 3143 public ReferenceTag(FieldInfo fi) { 3144 assert !fi.isStatic() && !fi.isPrimitive(); 3145 } 3146 3147 @Override 3148 public Object get_tag(Object parent, Object obj) { 3149 return obj; 3150 } 3151 } 3152}