001package daikon; 002 003import daikon.inv.DiscardInfo; 004import daikon.inv.Invariant; 005import daikon.suppress.NIS; 006import java.util.ArrayList; 007import java.util.Arrays; 008import java.util.Comparator; 009import java.util.Iterator; 010import java.util.List; 011import java.util.logging.Level; 012import java.util.logging.Logger; 013import org.checkerframework.checker.initialization.qual.UnknownInitialization; 014import org.checkerframework.checker.lock.qual.GuardSatisfied; 015import org.checkerframework.checker.nullness.qual.EnsuresNonNullIf; 016import org.checkerframework.checker.nullness.qual.Nullable; 017import org.checkerframework.checker.nullness.qual.RequiresNonNull; 018import org.checkerframework.dataflow.qual.Pure; 019import org.checkerframework.dataflow.qual.SideEffectFree; 020import org.plumelib.util.ArraysPlume; 021 022/** 023 * A Slice is a view of some of the variables for a program point. A program point (that is, 024 * PptTopLevel) does not directly contain invariants. Instead, slices contain the invariants that 025 * involve (all) the Slice's variables. 026 * 027 * <p>Suppose a program point has variables A, B, C, and D.<br> 028 * There would be 4 unary slices -- one each for variables A, B, C, and D.<br> 029 * There would be 6 binary slices -- for {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, and {C,D}.<br> 030 * There would be 4 ternary slices -- for {A,B,C}, {A,B,D}, {A,C,D}, and {B,C,D}. 031 */ 032public abstract class PptSlice extends Ppt { 033 static final long serialVersionUID = 20040921L; 034 035 // Permit subclasses to use it. 036 protected static final String lineSep = Global.lineSep; 037 038 /** Debug tracer. */ 039 public static final Logger debug = Logger.getLogger("daikon.PptSlice"); 040 041 /** Debug tracer for debugging both this and PptSlices. */ 042 public static final Logger debugGeneral = Logger.getLogger("daikon.PptSlice.general"); 043 044 public static final Logger debugFlow = Logger.getLogger("daikon.flow.flow"); 045 046 public static final Logger debugGuarding = Logger.getLogger("daikon.guard"); 047 048 // A better name would perhaps be "container", as this has nothing to do 049 // with the program point hierarchy. 050 /** This is a slice of the 'parent' ppt. */ 051 public PptTopLevel parent; 052 053 public abstract int arity(@UnknownInitialization(PptSlice.class) PptSlice this); 054 055 /** 056 * The invariants contained in this slice. This should not be used directly, in general. In 057 * particular, subclasses such as PptSlice0 need to synchronize it with other values. Therefore, 058 * it should be manipulated via {@link #addInvariant} and {@link #removeInvariant}. 059 */ 060 @SuppressWarnings("serial") 061 public List<Invariant> invs; 062 063 PptSlice(PptTopLevel parent, VarInfo[] var_infos) { 064 super(var_infos); 065 this.parent = parent; 066 invs = new ArrayList<Invariant>(); 067 // Ensure that the VarInfo objects are in order (and not duplicated). 068 for (int i = 0; i < var_infos.length - 1; i++) { 069 assert var_infos[i].varinfo_index <= var_infos[i + 1].varinfo_index; 070 } 071 assert this instanceof PptSliceEquality || arity() == var_infos.length; 072 073 if (debugGeneral.isLoggable(Level.FINE)) { 074 debugGeneral.fine(Arrays.toString(var_infos)); 075 } 076 } 077 078 @SideEffectFree 079 @Override 080 @SuppressWarnings("nullness:override.receiver") // see comment on overridden definition in Ppt 081 public final String name(@GuardSatisfied @UnknownInitialization(PptSlice.class) PptSlice this) { 082 return parent.name + varNames(var_infos); 083 } 084 085 public boolean usesVar(VarInfo vi) { 086 return (ArraysPlume.indexOfEq(var_infos, vi) != -1); 087 } 088 089 // This is only called from inv.filter.VariableFilter. 090 public boolean usesVar(String name) { 091 for (int i = 0; i < var_infos.length; i++) { 092 // mistere: I'm not sure is this is the right thing for 093 // the gui, but it's probably close 094 if (var_infos[i].name().equals(name)) { 095 return true; 096 } 097 } 098 return false; 099 } 100 101 /** 102 * Returns true if any of our variables is named NAME, or is derived from a variable named NAME. 103 * 104 * @return true if any of our variables is named NAME, or is derived from a variable named NAME 105 */ 106 // Only called right now from tools/ExtractConsequent 107 public boolean usesVarDerived(String name) { 108 for (VarInfo vi : var_infos) { 109 if (vi.includes_simple_name(name)) { 110 return true; 111 } 112 } 113 return false; 114 } 115 116 /** 117 * Returns true if all of this slice's variables are orig() variables. 118 * 119 * @return true if all of this slice's variables are orig() variables 120 */ 121 public boolean allPrestate() { 122 for (VarInfo vi : var_infos) { 123 if (!vi.isPrestateDerived()) { 124 return false; 125 } 126 } 127 return true; 128 } 129 130 public abstract void addInvariant(Invariant inv); 131 132 /** This method actually removes the invariant from its PptSlice. */ 133 // I don't just use ppt.invs.remove because I want to be able to defer 134 // and to take action if the vector becomes void. 135 public void removeInvariant(Invariant inv) { 136 137 if (Debug.logDetail()) { 138 log("Removing invariant '" + inv.format() + "'"); 139 } 140 if (Debug.logOn()) { 141 inv.log("Removed from slice: %s", inv.format()); 142 } 143 boolean removed = invs.remove(inv); 144 assert removed : "inv " + inv + " not in ppt " + name(); 145 Global.falsified_invariants++; 146 if (invs.size() == 0) { 147 if (Debug.logDetail()) { 148 log("last invariant removed"); 149 } 150 } 151 } 152 153 // This can be called with very long lists by the conditionals code. 154 // At least until that's fixed, it's important for it not to be 155 // quadratic. 156 public void removeInvariants(List<Invariant> to_remove) { 157 if (to_remove.size() < 10) { 158 for (Invariant trinv : to_remove) { 159 removeInvariant(trinv); 160 } 161 } else { 162 int old_invs_size = invs.size(); 163 invs.removeAll(to_remove); 164 assert old_invs_size - invs.size() == to_remove.size(); 165 Global.falsified_invariants += to_remove.size(); 166 if (invs.size() == 0) { 167 if (Debug.logDetail()) { 168 log("last invariant removed"); 169 } 170 } 171 } 172 } 173 174 /** 175 * This procedure accepts a sample (a ValueTuple), extracts the values from it, casts them to the 176 * proper types, and passes them along to the invariants proper. (The invariants accept typed 177 * values rather than a ValueTuple that encapsulates objects of any type whatever.) 178 * 179 * @return a List of Invariants that weakened due to the processing 180 */ 181 abstract List<Invariant> add(ValueTuple full_vt, int count); 182 183 /** Removes any falsified invariants from our list. */ 184 @RequiresNonNull("daikon.suppress.NIS.suppressor_map") 185 protected void remove_falsified() { 186 187 // Remove the dead invariants 188 for (Iterator<Invariant> iFalsified = invs.iterator(); iFalsified.hasNext(); ) { 189 Invariant inv = iFalsified.next(); 190 if (inv.is_false()) { 191 iFalsified.remove(); 192 NIS.falsified(inv); 193 } 194 } 195 } 196 197 /** Return an approximation of the number of samples seen on this slice. */ 198 public abstract int num_samples(@UnknownInitialization @GuardSatisfied PptSlice this); 199 200 /** Return an approximation of the number of distinct values seen on this slice. */ 201 public abstract int num_values(); 202 203 /** Instantiate invariants on the VarInfos this slice contains. */ 204 abstract void instantiate_invariants(); 205 206 /** 207 * This class is used for comparing PptSlice objects. It orders by arity, then by variable names. 208 * It's somewhat less efficient than ArityPptnameComparator. 209 */ 210 public static final class ArityVarnameComparator implements Comparator<PptSlice> { 211 @Pure 212 @Override 213 public int compare(PptSlice slice1, PptSlice slice2) { 214 if (slice1 == slice2) { 215 return 0; 216 } 217 // Don't do this assert, which prevents comparison across different Ppts. 218 // (The assert check may be useful in some situations, though.) 219 // assert slice1.parent == slice2.parent; 220 if (slice1.arity() != slice2.arity()) { 221 return slice2.arity() - slice1.arity(); 222 } 223 return Ppt.varNames(slice1.var_infos).compareTo(Ppt.varNames(slice2.var_infos)); 224 } 225 } 226 227 /** 228 * This class is used for comparing PptSlice objects. It orders by arity, then by name. Because of 229 * the dependence on name, it should be used only for slices on the same Ppt. 230 */ 231 public static final class ArityPptnameComparator implements Comparator<PptSlice> { 232 @Pure 233 @Override 234 public int compare(PptSlice slice1, PptSlice slice2) { 235 if (slice1 == slice2) { 236 return 0; 237 } 238 // Don't do this, to permit comparison across different Ppts. 239 // (The check may be useful in some situations, though.) 240 // assert slice1.parent == slice2.parent; 241 if (slice1.arity() != slice2.arity()) { 242 return slice2.arity() - slice1.arity(); 243 } 244 return slice1.name().compareTo(slice2.name()); 245 } 246 } 247 248 /////////////////////////////////////////////////////////////////////////// 249 /// Invariant guarding 250 251 public boolean containsOnlyGuardingPredicates() { 252 for (Invariant inv : invs) { 253 if (!inv.isGuardingPredicate) { 254 return false; 255 } 256 } 257 return true; 258 } 259 260 /////////////////////////////////////////////////////////////////////////// 261 /// Miscellaneous 262 263 /** Remove the invariants noted in omitTypes. */ 264 public void processOmissions(boolean[] omitTypes) { 265 if (invs.size() == 0) { 266 return; 267 } 268 List<Invariant> toRemove = new ArrayList<>(); 269 for (Invariant inv : invs) { 270 if (omitTypes['r'] && inv.isReflexive()) { 271 toRemove.add(inv); 272 } 273 } 274 removeInvariants(toRemove); 275 } 276 277 /** 278 * Check the internals of this slice. Each invariant in the slice is checked for consistency and 279 * each inv.ppt must equal this. 280 */ 281 public void repCheck() { 282 283 // System.out.printf("Checking slice %s%n", this); 284 285 // Make sure that each variable is a leader. There is one exception to this 286 // rule. Post processing of equality sets creates equality invariants between the 287 // various members of the equality set. Thus one non-leader is acceptable 288 // in binary (two variable) slices if it is in the same equality set as the 289 // other variable. 290 for (VarInfo vi : var_infos) { 291 // System.out.printf("equality set for vi %s = %s%n", vi, vi.equalitySet); 292 if (!vi.isCanonical()) { 293 assert var_infos.length == 2 : this + " - " + vi; 294 assert var_infos[0].canonicalRep() == var_infos[1].canonicalRep() : this + " - " + vi; 295 } 296 } 297 298 for (Invariant inv : invs) { 299 inv.repCheck(); 300 if (inv.ppt != this) { 301 throw new Error( 302 String.format( 303 "inv.ppt != this. inv.ppt=%s; this=%s; for inv=%s [%s] in invs=%s", 304 inv.ppt, this, inv, inv.getClass(), invs)); 305 } 306 } 307 } 308 309 /** 310 * Clone self and replace this.var_infos with newVis. Do the same in all invariants that this 311 * holds. Return a new PptSlice that's like this except with the above replacement, along with 312 * correct flow pointers for varInfos. Invariants are also pivoted so that any VarInfo index order 313 * swapping is handled correctly. 314 * 315 * @param newVis to replace this.var_infos 316 * @return a new PptSlice that satisfies the characteristics above 317 */ 318 PptSlice cloneAndPivot(VarInfo[] newVis) { 319 throw new Error("Shouldn't get called"); 320 } 321 322 public PptSlice copy_new_invs(PptTopLevel ppt, VarInfo[] vis) { 323 throw new Error("Shouldn't get called"); 324 } 325 326 /** For debugging only. */ 327 @Override 328 @SuppressWarnings("all:purity") // string creation 329 @SideEffectFree 330 public String toString(@GuardSatisfied PptSlice this) { 331 StringBuilder sb = new StringBuilder(); 332 for (VarInfo vi : var_infos) { 333 sb.append(" " + vi.name()); 334 } 335 return this.getClass().getName() 336 + ": " 337 + parent.ppt_name 338 // sb starts with a space 339 + sb 340 + " samples: " 341 + num_samples(); 342 } 343 344 /** 345 * Returns whether or not this slice already contains the specified invariant. Whether not 346 * invariants match is determine by Invariant.match() This will return true for invariants of the 347 * same kind with different formulas (eg, one_of, bound, linearbinary). 348 */ 349 public boolean contains_inv(Invariant inv) { 350 351 for (Invariant mine : invs) { 352 if (mine.match(inv)) { 353 return true; 354 } 355 } 356 return false; 357 } 358 359 /** 360 * Returns whether or not this slice contains an exact match for the specified invariant. An exact 361 * match requires that the invariants be of the same class and have the same formula. 362 */ 363 @EnsuresNonNullIf(result = true, expression = "find_inv_exact(#1)") 364 public boolean contains_inv_exact(Invariant inv) { 365 366 return (find_inv_exact(inv) != null); 367 } 368 369 /** 370 * Returns the invariant that matches the specified invariant if it exists. Otherwise returns 371 * null. An exact match requires that the invariants be of the same class and have the same 372 * formula. 373 */ 374 @Pure 375 public @Nullable Invariant find_inv_exact(Invariant inv) { 376 377 for (Invariant mine : invs) { 378 if ((mine.getClass() == inv.getClass()) && mine.isSameFormula(inv)) { 379 return mine; 380 } 381 } 382 return null; 383 } 384 385 /** 386 * Returns the invariant that matches the specified class if it exists. Otherwise returns null. 387 */ 388 public @Nullable Invariant find_inv_by_class(Class<? extends Invariant> cls) { 389 390 for (Invariant inv : invs) { 391 if ((inv.getClass() == cls)) { 392 return inv; 393 } 394 } 395 return null; 396 } 397 398 /** 399 * Returns true if the invariant is true in this slice. This can occur if the invariant exists in 400 * this slice, is suppressed, or is obvious statically. 401 */ 402 @Pure 403 public boolean is_inv_true(Invariant inv) { 404 405 if (contains_inv_exact(inv)) { 406 if (Debug.logOn() && (Daikon.current_inv != null)) { 407 Daikon.current_inv.log("inv %s exists", inv.format()); 408 } 409 return true; 410 } 411 412 // Check to see if the invariant is obvious statically over the leaders. 413 // This check should be sufficient since if it isn't obvious statically 414 // over the leaders, it should have been created. 415 DiscardInfo di = inv.isObviousStatically(var_infos); 416 if (di != null) { 417 if (Debug.logOn() && (Daikon.current_inv != null)) { 418 Daikon.current_inv.log("inv %s is obv statically", inv.format()); 419 } 420 return true; 421 } 422 423 boolean suppressed = inv.is_ni_suppressed(); 424 if (suppressed && Debug.logOn() && (Daikon.current_inv != null)) { 425 Daikon.current_inv.log("inv %s is ni suppressed", inv.format()); 426 } 427 return suppressed; 428 } 429 430 /** 431 * Output specified log information if the PtpSlice class, and this ppt and variables are enabled 432 * for logging. 433 */ 434 public void log(String msg) { 435 Debug.log(getClass(), this, msg); 436 } 437}