001// ***** This file is automatically generated from NoDuplicates.java.jpp 002 003package daikon.inv.unary.sequence; 004 005import daikon.*; 006import daikon.Quantify.QuantFlags; 007import daikon.derive.binary.SequencesJoin; 008import daikon.derive.binary.SequencesPredicate; 009import daikon.inv.*; 010import daikon.inv.binary.twoSequence.*; 011import daikon.inv.unary.scalar.*; 012import daikon.suppress.*; 013import java.util.*; 014import java.util.logging.*; 015import org.checkerframework.checker.interning.qual.Interned; 016import org.checkerframework.checker.lock.qual.GuardSatisfied; 017import org.checkerframework.checker.nullness.qual.Nullable; 018import org.checkerframework.dataflow.qual.Pure; 019import org.checkerframework.dataflow.qual.SideEffectFree; 020import org.plumelib.util.Intern; 021import typequals.prototype.qual.NonPrototype; 022import typequals.prototype.qual.Prototype; 023 024/** 025 * Represents sequences of long that contain no duplicate elements. Prints as 026 * {@code x[] contains no duplicates}. 027 */ 028 029public class NoDuplicates extends SingleScalarSequence { 030 // We are Serializable, so we specify a version to allow changes to 031 // method signatures without breaking serialization. If you add or 032 // remove fields, you should change this number to the current date. 033 static final long serialVersionUID = 20040204L; 034 035 // Variables starting with dkconfig_ should only be set via the 036 // daikon.config.Configuration interface. 037 /** Boolean. True iff NoDuplicates invariants should be considered. */ 038 public static boolean dkconfig_enabled = false; 039 040 /** Debug tracer. */ 041 public static final Logger debug = Logger.getLogger("daikon.inv.unary.sequence.NoDuplicates"); 042 043 protected NoDuplicates(PptSlice ppt) { 044 super(ppt); 045 } 046 047 protected @Prototype NoDuplicates() { 048 super(); 049 } 050 051 private static @Prototype NoDuplicates proto = new @Prototype NoDuplicates(); 052 053 /** Returns the prototype invariant for NoDuplicates */ 054 public static @Prototype NoDuplicates get_proto() { 055 return proto; 056 } 057 058 /** returns whether or not this invariant is enabled */ 059 @Override 060 public boolean enabled() { 061 return dkconfig_enabled; 062 } 063 064 /** instantiate an invariant on the specified slice */ 065 @Override 066 public NoDuplicates instantiate_dyn(@Prototype NoDuplicates this, PptSlice slice) { 067 return new NoDuplicates(slice); 068 } 069 070 @Override 071 public String repr(@GuardSatisfied NoDuplicates this) { 072 return "NoDuplicates" + varNames() + ": "; 073 } 074 075 @SideEffectFree 076 @Override 077 public String format_using(@GuardSatisfied NoDuplicates this, OutputFormat format) { 078 if (debug.isLoggable(Level.FINE)) { 079 debug.fine(repr()); 080 } 081 082 if (format == OutputFormat.DAIKON) { 083 return var().name() + " contains no duplicates"; 084 } 085 086 if (format == OutputFormat.SIMPLIFY) { 087 return format_simplify(); 088 } 089 090 if (format.isJavaFamily()) { 091 return format_java_family(format); 092 } 093 094 if (format == OutputFormat.CSHARPCONTRACT) { 095 return format_csharp_contract(); 096 } 097 098 return format_unimplemented(format); 099 } 100 101 public String format_simplify(@GuardSatisfied NoDuplicates this) { 102 String[] form = VarInfo.simplify_quantify(QuantFlags.distinct(), var(), 103 var()); 104 return form[0] + "(NEQ " + form[1] + " " + form[2] + ")" 105 + form[3]; 106 } 107 108 public String format_java_family(@GuardSatisfied NoDuplicates this, OutputFormat format) { 109 return "daikon.Quant.noDups(" + var().name_using(format) + ")"; 110 } 111 112 public String format_csharp_contract(@GuardSatisfied NoDuplicates this) { 113 String collection = var().csharp_collection_string(); 114 return collection + ".Distinct().Count() == " + collection + ".Count()"; 115 } 116 117 @Override 118 public InvariantStatus check_modified(long @Interned [] a, int count) { 119 // if (logDetail()) 120 // log ("sample " + Arrays.toString (a)); 121 for (int i = 1; i < a.length; i++) { 122 for (int j = 0; j < i; j++) { 123 if ((a[i] == a[j])) { 124 return InvariantStatus.FALSIFIED; 125 } 126 } 127 } 128 return InvariantStatus.NO_CHANGE; 129 } 130 131 @Override 132 public InvariantStatus add_modified(long @Interned [] a, int count) { 133 InvariantStatus status = check_modified(a, count); 134 if (debug.isLoggable(Level.FINE) && (status == InvariantStatus.FALSIFIED)) { 135 debug.fine("Destroying myself with: " + var().name()); 136 debug.fine(Arrays.toString(a)); 137 } 138 return status; 139 } 140 141 @Override 142 protected double computeConfidence() { 143 // num_no_dup_values() would be more appropriate 144 // return 1 - Math.pow(.9, ((PptSlice1) ppt).num_no_dup_values()); 145 return 1 - Math.pow(.9, ((PptSlice1) ppt).num_samples()); 146 } 147 148 @Pure 149 @Override 150 public @Nullable DiscardInfo isObviousStatically(VarInfo[] vis) { 151 if (!vis[0].aux.hasDuplicates()) { 152 return new DiscardInfo(this, DiscardCode.obvious, "Obvious statically"); 153 } 154 return super.isObviousStatically(vis); 155 } 156 157 /** 158 * Checks to see if this is obvious over the specified variables Implements the following checks: 159 * 160 * <pre> 161 * (A[] subsequence B[]) ^ (B[] has nodups) ⇒ A[] has nodups 162 * (A[] sorted by >) v (A[] sorted by <) ⇒ A[] has nodups 163 * </pre> 164 * 165 * JHP: The first check is not valid because we can't rely on transitive checks because of missing 166 * (if B[] is missing, A[] could have dups on those samples), 167 */ 168 @Pure 169 @Override 170 public @Nullable DiscardInfo isObviousDynamically(VarInfo[] vis) { 171 DiscardInfo super_result = super.isObviousDynamically(vis); 172 if (super_result != null) { 173 return super_result; 174 } 175 176 // If the maximum size of the array is <= 1, then this is 177 // obvious 178 ValueSet.ValueSetScalarArray vs = (ValueSet.ValueSetScalarArray) vis[0].get_value_set(); 179 if (vs.max_length() <= 1) { 180 return new DiscardInfo(this, DiscardCode.obvious, "Size of " + vis[0] 181 + " is <= " + vs.max_length()); 182 } 183 184 // For every other NoDuplicates at this program point, see if there is a 185 // subsequence relationship between that array and this one. 186 VarInfo v1 = vis[0]; 187 188 PptTopLevel parent = ppt.parent; 189 190 for (Iterator<Invariant> itor = parent.invariants_iterator(); itor.hasNext(); ) { 191 Invariant inv = itor.next(); 192 if ((inv instanceof NoDuplicates) && (inv != this) && inv.enoughSamples()) { 193 VarInfo v2 = inv.ppt.var_infos[0]; 194 if (SubSequence.isObviousSubSequenceDynamically(this, v1, v2)) { 195 // System.out.println("obvious: " + format() + " because of " + inv.format()); 196 log("Obvious- Obvious sub sequence with %s", inv.format()); 197 return new DiscardInfo(this, DiscardCode.obvious, "Invariant holds over a supersequence"); 198 } 199 } 200 } 201 202 // If the sequence is sorted by < or >, then there are obviously no duplicates 203 204 PptSlice slice = this.ppt.parent.findSlice_unordered(vis); 205 if (slice != null) { 206 for (Invariant inv : slice.invs) { 207 if ((inv instanceof EltwiseIntLessThan) 208 || (inv instanceof EltwiseFloatLessThan) 209 || (inv instanceof EltwiseIntGreaterThan) 210 || (inv instanceof EltwiseFloatGreaterThan)) { 211 return new DiscardInfo(this, DiscardCode.obvious, "Sequence is sorted: " + inv.format()); 212 } 213 } 214 } 215 216 return null; 217 } 218 219 @Pure 220 @Override 221 public boolean isSameFormula(Invariant other) { 222 assert other instanceof NoDuplicates; 223 return true; 224 } 225}