001package daikon; 002 003import static daikon.Global.lineSep; 004import static java.util.logging.Level.INFO; 005 006import daikon.inv.Invariant; 007import daikon.inv.InvariantStatus; 008import daikon.inv.ValueSet; 009import daikon.suppress.NIS; 010import java.io.File; 011import java.io.FileNotFoundException; 012import java.io.IOException; 013import java.util.ArrayList; 014import java.util.Iterator; 015import java.util.LinkedHashMap; 016import java.util.List; 017import java.util.Map; 018import java.util.Set; 019import java.util.logging.Logger; 020import org.checkerframework.checker.interning.qual.Interned; 021import org.checkerframework.checker.nullness.qual.Nullable; 022import org.checkerframework.dataflow.qual.Pure; 023 024/** 025 * DaikonSimple reads a declaration file and trace file and outputs a list of likely invariants 026 * using the simple incremental algorithm. Its methods parallel those of Daikon but oftentimes 027 * certain checks are eliminated from DaikonSimple's methods because there is less filtering of 028 * invariants and variables. 029 * 030 * <p>DaikonSimple was written to check the implementation of the optimizations in Daikon. 031 * DaikonSimple does not use any optimizations, and its processing will produce a complete set of 032 * true invariants. Daikon does have flags to "turn off" some of its optimizations but there are 033 * some optimizations are built into the way Daikon processes the samples (e.g. variable hierarchy 034 * and bottom up processing). In addition, we want to check the optimizations, so we don't want to 035 * bypass them. In Daikon, code was written to "undo" the optimizations, so we could recover the 036 * invariants that were previously filtered out or not created (see Daikon.dkconfig_undo_opts flag). 037 * By comparing the output from the two, we can find problems with the optimization implementation 038 * by tracking the cause of the differences. 039 */ 040@SuppressWarnings("nullness") // not actively maintained 041public class DaikonSimple { 042 043 // logging information 044 public static final Logger debug = Logger.getLogger("daikon.DaikonSimple"); 045 046 public static final Logger debug_detail = Logger.getLogger("daikon.DaikonSimple.Detail"); 047 048 // // inv file for storing the invariants in serialized form 049 // public static File inv_file = null; 050 051 /** Usage message to be displayed for help. */ 052 private static String usage = 053 String.join( 054 lineSep, 055 "", 056 "Usage: java daikon.DaikonSimple [OPTION]... <decls_file> <dtrace_file>", 057 " -h, --" + Daikon.help_SWITCH, 058 " Display this usage message", 059 // " -o, <inv_file> ", 060 // " Writes output to <inv_file>", 061 " --" + Daikon.debugAll_SWITCH, 062 " Turns on all debug flags (voluminous output)", 063 " --" + Daikon.debug_SWITCH + " logger", 064 " Turns on the specified debug logger", 065 " --" + Daikon.track_SWITCH + " class<var1,var2,var3>@ppt", 066 " Print debug info on the specified invariant class, vars, and ppt"); 067 068 // a pptMap that contains all the program points 069 public static PptMap all_ppts; 070 071 public static void main(final String[] args) throws IOException, FileNotFoundException { 072 073 try { 074 mainHelper(args); 075 } catch (Daikon.DaikonTerminationException e) { 076 Daikon.handleDaikonTerminationException(e); 077 } 078 } 079 080 /** 081 * This does the work of {@link #main}, but it never calls System.exit, so it is appropriate to be 082 * called programmatically. 083 * 084 * <p>Difference from {@link daikon.Daikon#mainHelper(String[])}Helper: turn off optimization 085 * flags (equality, dynamic constants, NIS suppression). 086 */ 087 public static void mainHelper(final String[] args) throws IOException, FileNotFoundException { 088 089 // set up logging information 090 daikon.LogHelper.setupLogs(INFO); 091 092 // No optimizations used in the simple incremental algorithm so 093 // optimizations are turned off. 094 Daikon.use_equality_optimization = false; 095 DynamicConstants.dkconfig_use_dynamic_constant_optimization = false; 096 NIS.dkconfig_enabled = false; 097 098 // The flag tells FileIO and Daikon to use DaikonSimple 099 // specific methods (e.g. FileIO.read_declaration_file). 100 // When FileIO reads and processes 101 // samples, it must use the SimpleProcessor rather than the 102 // default Processor. 103 Daikon.using_DaikonSimple = true; 104 105 // Read command line options 106 Daikon.FileOptions files = Daikon.read_options(args, usage); 107 // DaikonSimple does not supply nor use the spinfo_files and map_files 108 Set<File> decls_files = files.decls; 109 Set<String> dtrace_files = files.dtrace; 110 111 if ((decls_files.size() == 0) && (dtrace_files.size() == 0)) { 112 throw new Daikon.UserError("No .decls or .dtrace files specified"); 113 } 114 115 // Create the list of all invariant types 116 Daikon.setup_proto_invs(); 117 118 // Create the program points for enter and numbered exits and 119 // initializes the points (adding orig and derived variables) 120 all_ppts = FileIO.read_declaration_files(decls_files); 121 122 // Create the combined exits (and add orig and derived vars) 123 // Daikon.create_combined_exits(all_ppts); 124 125 // Read and process the data trace files 126 SimpleProcessor processor = new SimpleProcessor(); 127 FileIO.read_data_trace_files(dtrace_files, all_ppts, processor, true); 128 129 // System.exit(0); 130 131 // Print out the invariants for each program point (sort first) 132 for (PptTopLevel ppt : all_ppts.pptIterable()) { 133 134 // We do not need to print out program points that have not seen 135 // any samples. 136 if (ppt.num_samples() == 0) { 137 continue; 138 } 139 List<Invariant> invs = PrintInvariants.sort_invariant_list(ppt.invariants_vector()); 140 List<Invariant> filtered_invs = Daikon.filter_invs(invs); 141 // The dkconfig_quiet printing is used for creating diffs between 142 // DaikonSimple 143 // and Daikon's output. The second kind of printing is used for 144 // debugging. Since the names of the program points are the same for both 145 // Daikon and DaikonSimple, diffing the two output will result in 146 // only differences in the invariants, but we can not see at which program 147 // points these differing invariants appear. Using the second kind of 148 // printing, 149 // Daikon's output does not have the '+' in the program point name, so in 150 // addition 151 // to the invariants showing up in the diff, we will also see the program 152 // point 153 // names. 154 155 if (Daikon.dkconfig_quiet) { 156 System.out.println("===================================================="); 157 System.out.println(ppt.name()); 158 } else { 159 System.out.println("===================================================+"); 160 System.out.println(ppt.name() + " +"); 161 } 162 163 // Sometimes the program points actually differ in number of 164 // samples seen due to differences in how Daikon and DaikonSimple 165 // see the variable hierarchy. 166 System.out.println(ppt.num_samples()); 167 168 for (Invariant inv : filtered_invs) { 169 System.out.println(inv.getClass()); 170 System.out.println(inv); 171 } 172 } 173 } 174 175 /** 176 * Install views and the invariants. Duplicated from PptTopLevel's version because DaikonSimple 177 * needs to use its own version of slice checking code. 178 * 179 * <p>Difference from PptTopLevel's version: 180 * 181 * <ol> 182 * <li>canonical (leader of equality set) check of variables is turned off because every 183 * variable is in its own equality set 184 * <li>debugging information turned off because DaikonSimple's code is more contained 185 * <li>less constraints on the slices 186 * </ol> 187 * 188 * @see daikon.PptTopLevel#instantiate_views_and_invariants() 189 */ 190 191 // Note that some slightly inefficient code has been added to aid 192 // in debugging. When creating binary and ternary views and debugging 193 // is on, the outer loops will not terminate prematurely on inappropriate 194 // (i.e., non-canonical) variables. This allows explicit debug statements 195 // for each possible combination, simplifying determining why certain 196 // slices were not created. 197 // 198 // Note that '///*' indicates code duplicated from PptTopLevel's 199 // version but commented out because DaikonSimple does not need 200 // to perform these checks 201 public static void instantiate_views_and_invariants(PptTopLevel ppt) { 202 203 // used only for debugging 204 int old_num_vars = ppt.var_infos.length; 205 206 // / 1. all unary views 207 208 // Unary slices/invariants. 209 // Currently, there are no constraints on the unary 210 // slices. Since we are trying to create all of the invariants, the 211 // variables does not have to be a leader and can be a constant. 212 // Note that the always missing check is only applicable when the 213 // dynamic constants optimization is turned on (so we do not do the 214 // check here). 215 216 List<PptSlice> unary_views = new ArrayList<>(ppt.var_infos.length); 217 for (VarInfo vi : ppt.var_infos) { 218 219 // /* if (!is_slice_ok(vi)) 220 // /* continue; 221 222 PptSlice1 slice1 = new PptSlice1(ppt, vi); 223 slice1.instantiate_invariants(); 224 225 unary_views.add(slice1); 226 } 227 ppt.addViews(unary_views); 228 unary_views = null; 229 230 // / 2. all binary views 231 232 // Binary slices/invariants. 233 List<PptSlice> binary_views = new ArrayList<>(); 234 for (int i1 = 0; i1 < ppt.var_infos.length; i1++) { 235 VarInfo var1 = ppt.var_infos[i1]; 236 237 // Variables can be constant and missing in DaikonSimple invariants 238 // /* if (!is_var_ok_binary(var1)) 239 // /* continue; 240 241 for (int i2 = i1; i2 < ppt.var_infos.length; i2++) { 242 VarInfo var2 = ppt.var_infos[i2]; 243 244 // Variables can be constant and missing in DaikonSimple invariants 245 // /* if (!is_var_ok_binary(var2)) 246 // /* continue; 247 248 if (!(var1.compatible(var2) 249 || (var1.type.isArray() && var1.eltsCompatible(var2)) 250 || (var2.type.isArray() && var2.eltsCompatible(var1)))) { 251 continue; 252 } 253 254 PptSlice2 slice2 = new PptSlice2(ppt, var1, var2); 255 slice2.instantiate_invariants(); 256 257 binary_views.add(slice2); 258 } 259 } 260 ppt.addViews(binary_views); 261 binary_views = null; 262 263 // 3. all ternary views 264 List<PptSlice> ternary_views = new ArrayList<>(); 265 for (int i1 = 0; i1 < ppt.var_infos.length; i1++) { 266 VarInfo var1 = ppt.var_infos[i1]; 267 268 if (!is_var_ok(var1)) { 269 continue; 270 } 271 272 for (int i2 = i1; i2 < ppt.var_infos.length; i2++) { 273 VarInfo var2 = ppt.var_infos[i2]; 274 275 if (!is_var_ok(var2)) { 276 continue; 277 } 278 279 for (int i3 = i2; i3 < ppt.var_infos.length; i3++) { 280 VarInfo var3 = ppt.var_infos[i3]; 281 282 if (!is_var_ok(var3)) { 283 continue; 284 } 285 286 if (!is_slice_ok(var1, var2, var3)) { 287 continue; 288 } 289 PptSlice3 slice3 = new PptSlice3(ppt, var1, var2, var3); 290 slice3.instantiate_invariants(); 291 ternary_views.add(slice3); 292 } 293 } 294 } 295 296 ppt.addViews(ternary_views); 297 298 // This method didn't add any new variables. 299 assert old_num_vars == ppt.var_infos.length; 300 ppt.repCheck(); 301 } 302 303 // This method is exclusively for checking variables participating 304 // in ternary invariants. The variable must be integer or float, and 305 // can not be an array. 306 @Pure 307 public static boolean is_var_ok(VarInfo var) { 308 309 return (var.file_rep_type.isIntegral() || var.file_rep_type.isFloat()) 310 && !var.rep_type.isArray(); 311 } 312 313 /** 314 * Returns whether or not the specified binary slice should be created. The slice should not be 315 * created if the vars are not compatible. 316 * 317 * <p>Since we are trying to create all of the invariants, the variables does not have to be a 318 * leader and can be a constant. Note that the always missing check is only applicable when the 319 * dynamic constants optimization is turned on (so we do not do the check here). 320 * 321 * @see daikon.PptTopLevel#is_slice_ok(VarInfo, VarInfo) 322 */ 323 @Pure 324 public static boolean is_slice_ok(VarInfo v1, VarInfo v2) { 325 326 return v1.compatible(v2); 327 } 328 329 /** 330 * Returns whether or not the specified ternary slice should be created. The slice should not be 331 * created if any of the following are true 332 * 333 * <ul> 334 * <li>Any var is an array 335 * <li>Any of the vars are not compatible with the others 336 * <li>Any var is not (integral or float) 337 * </ul> 338 * 339 * Since we are trying to create all of the invariants, the variables does not have to be a leader 340 * and can be a constant. Note that the always missing check is only applicable when the dynamic 341 * constants optimization is turned on (so we do not do the check here). In addition, we do want 342 * to create the reflexive ones and partially reflexive invariants. 343 * 344 * @see daikon.PptTopLevel#is_slice_ok(VarInfo, VarInfo, VarInfo) 345 */ 346 @Pure 347 public static boolean is_slice_ok(VarInfo v1, VarInfo v2, VarInfo v3) { 348 349 // Vars must be compatible 350 return v1.compatible(v2) && v1.compatible(v3) && v2.compatible(v3); 351 } 352 353 /** 354 * The Call class helps the SimpleProcessor keep track of matching enter and exit program points 355 * and also object program points. Each Call object represents one entry in the dtrace file, i.e. 356 * enter, exit, object entry. 357 */ 358 static final class Call { 359 360 public PptTopLevel ppt; 361 362 public ValueTuple vt; 363 364 public Call(PptTopLevel ppt, ValueTuple vt) { 365 366 this.ppt = ppt; 367 this.vt = vt; 368 } 369 } 370 371 /** The SimpleProcessor class processes each sample in the dtrace file. */ 372 public static class SimpleProcessor extends FileIO.Processor { 373 PptMap all_ppts; 374 375 /** {@code nonce -> List<Call,Call>} */ 376 // The first Call is the enter entry and the second is the object entry 377 Map<Integer, List<Call>> call_map = new LinkedHashMap<>(); 378 379 // Flag for whether there are out of order entries in the 380 // dtrace file. For unterminated calls (enter but 381 // not exit entry in the dtrace file), because DaikonSimple had 382 // processed each entry separately (not bottom up like Daikon), 383 // DaikonSimple applied the enter and object call before seeing the 384 // exit call, which is not consistent with Daikon. Daikon does not 385 // process unterminated method calls. 386 387 // The method of holding the enter and object calls until finding 388 // a matching exit call assumes: 389 // - enter always comes before exit 390 // - first entry in dtrace is an enter 391 // - order in dtrace is enter, exit, object [for constructors] or 392 // enter, object, exit, object [for methods] but not necessarily 393 // sequential 394 boolean wait = false; 395 396 // pointer to last nonce so we can associate the object entry 397 // with the right enter entry 398 Integer last_nonce = -1; 399 400 /** 401 * Creates a ValueTuple for the receiver using the vt of the original. The method copies over 402 * the values of variables shared by both program points and sets the rest of the variables in 403 * the receiver's ValueTuple as missing. Also, adds the orig and derived variables to the 404 * receiver and returns the newly created ValueTuple. 405 */ 406 private static ValueTuple copySample( 407 PptTopLevel receiver, PptTopLevel original, ValueTuple vt, int nonce) { 408 409 // Make the vt for the receiver ppt 410 // Object[] values = new Object[receiver.num_tracevars]; 411 // int[] mods = new int[receiver.num_tracevars]; 412 @Nullable @Interned Object[] values = 413 new @Interned Object[receiver.var_infos.length - receiver.num_static_constant_vars]; 414 int[] mods = new int[receiver.var_infos.length - receiver.num_static_constant_vars]; 415 416 // Build the vt for the receiver ppt by looking through the current 417 // vt and filling in the gaps. 418 int k = 0; 419 for (VarInfo var : receiver.var_infos) { 420 if (var.is_static_constant) { 421 continue; 422 } 423 boolean found = false; 424 for (VarInfo var2 : original.var_infos) { 425 if (var.name().equals(var2.name())) { 426 values[k] = vt.getValueOrNull(var2); 427 mods[k] = vt.getModified(var2); 428 found = true; 429 break; 430 } 431 } 432 433 if (!found) { 434 values[k] = null; 435 mods[k] = 2; 436 } 437 k++; 438 } 439 440 ValueTuple receiver_vt = new ValueTuple(values, mods); 441 442 FileIO.compute_orig_variables(receiver, receiver_vt.vals, receiver_vt.mods, nonce); 443 FileIO.compute_derived_variables(receiver, receiver_vt.vals, receiver_vt.mods); 444 445 return receiver_vt; 446 } 447 448 /** 449 * Process the sample by checking it against each existing invariant at the program point and 450 * removing the invariant from the list of possibles if any invariant is falsified. 451 */ 452 @Override 453 public void process_sample( 454 PptMap all_ppts, PptTopLevel ppt, ValueTuple vt, @Nullable Integer nonce) { 455 this.all_ppts = all_ppts; 456 457 // Add samples to orig and derived variables 458 FileIO.compute_orig_variables(ppt, vt.vals, vt.mods, nonce); 459 FileIO.compute_derived_variables(ppt, vt.vals, vt.mods); 460 461 // Intern the sample 462 vt = new ValueTuple(vt.vals, vt.mods); 463 464 // DaikonSimple must make the object program point manually because 465 // the new Chicory produced dtrace files do not contain object ppts 466 // in the dtrace part of the file (the program point is declared). 467 468 // Make the object ppt 469 PptName ppt_name = ppt.ppt_name; 470 471 PptTopLevel object_ppt = null; 472 PptTopLevel class_ppt = null; 473 ValueTuple object_vt = null; 474 ValueTuple class_vt = null; 475 476 if ((ppt_name.isEnterPoint() && !ppt_name.isConstructor()) || ppt_name.isExitPoint()) { 477 object_ppt = all_ppts.get(ppt_name.makeObject()); 478 class_ppt = all_ppts.get(ppt_name.makeClassStatic()); 479 } 480 481 // C programs do not have object ppts 482 // check whether the ppt is a static or instance method 483 // that decides whether the sample is copied over to the object and/or 484 // class ppt 485 if (object_ppt != null) { 486 487 // the check assumes that static fields are not stored first in the 488 // object ppt 489 if (ppt.find_var_by_name(object_ppt.var_infos[0].name()) != null) { 490 // object and class ppt should be created 491 object_vt = copySample(object_ppt, ppt, vt, nonce); 492 493 if (class_ppt != null) { 494 class_vt = copySample(class_ppt, ppt, vt, nonce); 495 } 496 497 } else { 498 // only class ppt should be created 499 if (class_ppt != null) { 500 class_vt = copySample(class_ppt, ppt, vt, nonce); 501 } 502 503 object_vt = null; 504 object_ppt = null; 505 } 506 } 507 508 // If this is an enter point, just remember it for later 509 if (ppt_name.isEnterPoint()) { 510 assert nonce != null; 511 assert call_map.get(nonce) == null; 512 List<Call> value = new ArrayList<>(); 513 value.add(new Call(ppt, vt)); 514 515 if (object_ppt != null) { 516 value.add(new Call(object_ppt, object_vt)); 517 } 518 519 if (class_ppt != null) { 520 value.add(new Call(class_ppt, class_vt)); 521 } 522 523 call_map.put(nonce, value); 524 last_nonce = nonce; 525 wait = true; 526 return; 527 } 528 529 // If this is an exit point, process the saved enter (and sometimes 530 // object) point 531 if (ppt_name.isExitPoint()) { 532 assert nonce != null; 533 List<Call> value = call_map.remove(nonce); 534 535 add(ppt, vt, nonce); 536 537 for (Call ec : value) { 538 add(ec.ppt, ec.vt, nonce); 539 } 540 wait = false; 541 } 542 543 if (object_ppt != null) { 544 add(object_ppt, object_vt, nonce); 545 } 546 547 if (class_ppt != null) { 548 add(class_ppt, class_vt, nonce); 549 } 550 } 551 552 /** 553 * The method iterates through all of the invariants in the ppt and manually adds the sample to 554 * the invariant and removing the invariant if it is falsified. 555 */ 556 private void add(PptTopLevel ppt, ValueTuple vt, int nonce) { 557 558 // if this is a numbered exit, apply to the combined exit as well 559 if (ppt.ppt_name.isNumberedExitPoint()) { 560 561 // Daikon.create_combined_exits(all_ppts); 562 PptTopLevel parent = all_ppts.get(ppt.ppt_name.makeExit()); 563 if (parent != null) { 564 parent.get_missingOutOfBounds(ppt, vt); 565 add(parent, vt, nonce); 566 567 } else { 568 // make parent and apply 569 570 // this is a hack. it should probably filter out orig and derived 571 // vars instead of taking the first n. 572 int len = ppt.num_tracevars + ppt.num_static_constant_vars; 573 VarInfo[] exit_vars = new VarInfo[len]; 574 for (int j = 0; j < len; j++) { 575 @SuppressWarnings("interning") // newly created, about to be used in a program point 576 @Interned VarInfo exit_var = new VarInfo(ppt.var_infos[j]); 577 exit_vars[j] = exit_var; 578 exit_vars[j].varinfo_index = ppt.var_infos[j].varinfo_index; 579 exit_vars[j].value_index = ppt.var_infos[j].value_index; 580 exit_vars[j].equalitySet = null; 581 } 582 583 parent = new PptTopLevel(ppt.ppt_name.makeExit().getName(), exit_vars); 584 Daikon.init_ppt(parent, all_ppts); 585 all_ppts.add(parent); 586 parent.get_missingOutOfBounds(ppt, vt); 587 add(parent, vt, nonce); 588 } 589 } 590 591 // If the point has no variables, skip it 592 if (ppt.var_infos.length == 0) { 593 // The sample should be skipped but Daikon does not do this so 594 // DaikonSimple will not do this to be consistent. 595 // The better idea is for Daikon to assert that these valuetuples are 596 // empty and then skip the sample. 597 assert vt.size() == 0; 598 return; 599 } 600 601 // Instantiate slices and invariants if this is the first sample 602 if (ppt.num_samples() == 0) { 603 instantiate_views_and_invariants(ppt); 604 } 605 606 // manually inc the sample number because DaikonSimple does not 607 // use any of PptTopLevel's add methods which increase the sample 608 // number 609 ppt.incSampleNumber(); 610 611 // Loop through each slice 612 for (PptSlice slice : ppt.views_iterable()) { 613 Iterator<Invariant> k = slice.invs.iterator(); 614 boolean missing = false; 615 616 for (VarInfo v : slice.var_infos) { 617 // If any var has encountered out of array bounds values, 618 // stop all invariants in this slice. The presumption here is that 619 // an index out of bounds implies that the derived variable (eg a[i]) 620 // doesn't really make any sense (essentially that i is not a valid 621 // index for a). Invariants on the derived variable are thus not 622 // relevant. 623 // If any variables are out of bounds, remove the invariants 624 if (v.missingOutOfBounds()) { 625 while (k.hasNext()) { 626 k.next(); 627 k.remove(); 628 } 629 missing = true; 630 break; 631 } 632 633 // If any variables are missing, skip this slice 634 if (v.isMissing(vt)) { 635 missing = true; 636 break; 637 } 638 } 639 640 // keep a list of the falsified invariants 641 if (!missing) { 642 while (k.hasNext()) { 643 644 Invariant inv = k.next(); 645 for (VarInfo vi : inv.ppt.var_infos) { 646 assert vt.getValue(vi) != null : vi; 647 } 648 if (inv.ppt instanceof PptSlice2) { 649 assert inv.ppt.var_infos.length == 2; 650 } 651 InvariantStatus status = inv.add_sample(vt, 1); 652 if (status == InvariantStatus.FALSIFIED) { 653 k.remove(); 654 } 655 } 656 } 657 658 // update num_samples and num_values of a slice manually 659 // because DaikonSimple does not call any of PptTopLevel's 660 // add methods 661 for (int j = 0; j < vt.vals.length; j++) { 662 if (!vt.isMissing(j)) { 663 ValueSet vs = ppt.value_sets[j]; 664 vs.add(vt.vals[j]); 665 } 666 } 667 ppt.mbtracker.add(vt, 1); 668 } 669 } 670 } 671}