001package daikon.derive; 002 003import daikon.Quantify; 004import daikon.ValueTuple; 005import daikon.VarInfo; 006import java.io.Serializable; 007import java.util.logging.Logger; 008import org.checkerframework.checker.nullness.qual.MonotonicNonNull; 009import org.checkerframework.checker.nullness.qual.RequiresNonNull; 010import org.checkerframework.dataflow.qual.Pure; 011import org.checkerframework.dataflow.qual.SideEffectFree; 012 013/** 014 * Structure that represents a derivation; can generate values and derived variables from base 015 * variables. A Derivation has a set of base VarInfo from which the Derivation is derived. Use 016 * getVarInfo() to get the VarInfo representation of this Derivation. When we want the actual value 017 * of this derivation, we pass in a ValueTuple; the Derivation picks out the values of its base 018 * variables and finds the value of the derived variable. Use computeValueandModified() to get 019 * value. Derivations are created by DerivationFactory. 020 */ 021public abstract class Derivation implements Serializable, Cloneable { 022 // We are Serializable, so we specify a version to allow changes to 023 // method signatures without breaking serialization. If you add or 024 // remove fields, you should change this number to the current date. 025 static final long serialVersionUID = 20020122L; 026 027 // This definition is here so that it will show up in the manual 028 // with the other options for controlling derived variables 029 /** 030 * Boolean. If true, Daikon will not create any derived variables. Derived variables, which are 031 * combinations of variables that appeared in the program, like {@code array[index]} if {@code 032 * array} and {@code index} appeared, can increase the number of properties Daikon finds, 033 * especially over sequences. However, derived variables increase Daikon's time and memory usage, 034 * sometimes dramatically. If false, individual kinds of derived variables can be enabled or 035 * disabled individually using configuration options under {@code daikon.derive}. 036 */ 037 public static boolean dkconfig_disable_derived_variables = false; 038 039 /** Debug tracer. */ 040 public static final Logger debug = Logger.getLogger("daikon.derive.Derivation"); 041 042 // This is static, so we can't mention it here. 043 // It's in DerivationFactory, though. // really? 044 // public boolean applicable(); 045 046 // This is essentially a clone() method that also switches the variables. 047 public abstract Derivation switchVars(VarInfo[] old_vars, VarInfo[] new_vars); 048 049 /** 050 * Returns array of the VarInfos this was derived from. 051 * 052 * @return array of the VarInfos this was derived from 053 */ 054 @SideEffectFree 055 public abstract VarInfo[] getBases(); 056 057 /** 058 * Returns the {@code i}th VarInfo this was derived from. 059 * 060 * @param i index into the array of Varinfos this was derived from 061 * @return the {@code i}th VarInfo this was derived from 062 */ 063 @Pure 064 public abstract VarInfo getBase(int i); 065 066 /** 067 * Returns a pair of: the derived value and whether the variable counts as modified. 068 * 069 * @return a pair of: the derived value and whether the variable counts as modified 070 * @param full_vt the set of values in a program point that will be used to derive the value 071 */ 072 // I don't provide separate computeModified and computeValue 073 // functions: they aren't so useful, and the same computation must 074 // usually be done in both functions. 075 // A value whose derivation doesn't make sense is considered 076 // MISSING_NONSENSICAL, not MISSING_FLOW. 077 public abstract ValueAndModified computeValueAndModified(ValueTuple full_vt); 078 079 /** 080 * Get the VarInfo that this would represent. However, the VarInfo can't be used to obtain values 081 * without further modification -- use computeValueAndModified() for this. 082 * 083 * @return the VarInfo hat this would represent 084 * @see Derivation#computeValueAndModified 085 */ 086 public VarInfo getVarInfo() { 087 if (this_var_info == null) { 088 this_var_info = makeVarInfo(); 089 makeVarInfo_common_setup(this_var_info); 090 } 091 return this_var_info; 092 } 093 094 private @MonotonicNonNull VarInfo this_var_info; 095 096 /** 097 * Used by all child classes to actually create the VarInfo this represents, after which it is 098 * interned for getVarInfo(). 099 */ 100 // This is in each class, but I can't have a private abstract method. 101 protected abstract VarInfo makeVarInfo(); 102 103 @RequiresNonNull("this_var_info") 104 protected void makeVarInfo_common_setup(VarInfo vi) { 105 // Common tasks that are abstracted into here. 106 vi.derived = this; 107 vi.canBeMissing = canBeMissing(); 108 if (isParam()) { 109 this_var_info.set_is_param(); 110 // VIN 111 // this_var_info.aux = vi.aux.setValue(VarInfoAux.IS_PARAM, 112 // VarInfoAux.TRUE); 113 } 114 } 115 116 // Set whether the derivation is a param according to aux info 117 @Pure 118 protected abstract boolean isParam(); 119 120 public boolean missing_array_bounds = false; 121 122 /** 123 * True if we have encountered to date any missing values in this derivation due to array indices 124 * being out of bounds. This can happen with both simple subscripts and subsequences. Note that 125 * this becomes true as we are running, it cannot be set in advance (which would require a first 126 * pass). 127 */ 128 public boolean missingOutOfBounds() { 129 return missing_array_bounds; 130 } 131 132 /* * 133 * For debugging only; returns true if the variables from which this 134 * one was derived are all non-canonical (which makes this derived 135 * variable uninteresting). We might not have been able to know 136 * before performing the derivation that this would be the case -- 137 * for instance, when deriving before any values are seen. 138 */ 139 @Pure 140 public abstract boolean isDerivedFromNonCanonical(); 141 142 /** 143 * Returns how many levels of derivation this Derivation is based on. The depth counts this as 144 * well as the depths of its bases. 145 */ 146 public abstract int derivedDepth(); 147 148 /** 149 * Returns true iff other and this represent the same derivation (modulo the variable they are 150 * applied to). Default implentation will just checks run-time type, but subclasses with state 151 * (e.g. SequenceInitial index) should match that, too. 152 * 153 * @param other the Derivation to compare to 154 * @return true iff other and this represent the same derivation 155 */ 156 @Pure 157 public abstract boolean isSameFormula(Derivation other); 158 159 /** 160 * See {@link VarInfo#canBeMissing}. 161 * 162 * @see VarInfo#canBeMissing 163 */ 164 public abstract boolean canBeMissing(); 165 166 /** 167 * Returns the lower bound of a slice. Throws an error if this is not a slice. Slices should 168 * override. 169 */ 170 public Quantify.Term get_lower_bound() { 171 throw new RuntimeException("not a slice derivation: " + this); 172 } 173 174 /** 175 * Returns the lower bound of a slice. Throws an error if this is not a slice. Slices should 176 * override. 177 */ 178 public Quantify.Term get_upper_bound() { 179 throw new RuntimeException("not a slice derivation: " + this); 180 } 181 182 /** 183 * Returns the array variable that underlies this slice. Throws an error if this is not a slice. 184 * Slices should override. 185 */ 186 public VarInfo get_array_var() { 187 throw new RuntimeException("not a slice derivation: " + this); 188 } 189 190 /** 191 * Returns the name of this variable in ESC format. If an index is specified, it is used as an 192 * array index. It is an error to specify an index on a non-array variable. 193 */ 194 @SideEffectFree 195 public String esc_name(String index) { 196 throw new RuntimeException("esc_name not implemented for " + this); 197 } 198 199 /** 200 * Returns the name of this variable in JML format. If an index is specified, it is used as an 201 * array index. It is an error to specify an index on a non-array variable. 202 */ 203 public String jml_name(String index) { 204 return esc_name(index); 205 } 206 207 /** 208 * Returns the name of this variable in CSHARPCONTRACT format. If an index is specified, it is 209 * used as an array index. It is an error to specify an index on a non-array variable. 210 */ 211 @SideEffectFree 212 public String csharp_name(String index) { 213 throw new RuntimeException("csharp_name not implemented for " + this); 214 } 215 216 /** Returns the name of this variable in simplify format. */ 217 @SideEffectFree 218 public String simplify_name() { 219 throw new RuntimeException( 220 "simplify_name not implemented for " + this.getClass() + " (" + this + ")"); 221 } 222 223 /** 224 * Returns true if d is the prestate version of this. Returns true if this and d are of the same 225 * derivation with the same formula and have the same bases. 226 */ 227 @Pure 228 public boolean is_prestate_version(Derivation d) { 229 230 // The derivations must be of the same type 231 if (getClass() != d.getClass()) { 232 return false; 233 } 234 235 // Each base of vi must be the prestate version of this 236 VarInfo[] base1 = getBases(); 237 VarInfo[] base2 = d.getBases(); 238 for (int ii = 0; ii < base1.length; ii++) { 239 if (!base1[ii].is_prestate_version(base2[ii])) { 240 return false; 241 } 242 } 243 244 // The derivations must have the same formula (offset, start_from, etc) 245 return isSameFormula(d); 246 } 247 248 /** 249 * Return the complexity of this derivation. This is only for the derivation itself and not for 250 * the variables included in the derivation. The default implementation returns 1 (which is the 251 * added complexity of an derivation). Subclasses that add additional complexity (such as an 252 * offset) should override. 253 */ 254 public int complexity() { 255 return 1; 256 } 257 258 /** 259 * Returns a string that corresponds to the specified shift. 260 * 261 * @param shift how much to shift the string 262 * @return the shifted string 263 */ 264 protected String shift_str(int shift) { 265 String shift_str = ""; 266 if (shift != 0) shift_str = String.format("%+d", shift); 267 return shift_str; 268 } 269 270 /** 271 * Returns the esc name of a variable which is included inside an expression (such as 272 * orig(a[vi])). If the expression is orig, the orig is implied for this variable. 273 */ 274 protected String inside_esc_name(VarInfo vi, boolean in_orig, int shift) { 275 if (vi == null) { 276 return ""; 277 } 278 279 if (in_orig) { 280 if (vi.isPrestate()) { 281 assert vi.postState != null; // because isPrestate() = true 282 return vi.postState.esc_name() + shift_str(shift); 283 } else { 284 return String.format("\\new(%s)%s", vi.esc_name(), shift_str(shift)); 285 } 286 } else { 287 return vi.esc_name() + shift_str(shift); 288 } 289 } 290 291 /** 292 * Returns the jml name of a variable which is included inside an expression (such as 293 * orig(a[vi])). If the expression is orig, the orig is implied for this variable. 294 */ 295 protected String inside_jml_name(VarInfo vi, boolean in_orig, int shift) { 296 if (vi == null) { 297 return ""; 298 } 299 300 if (in_orig) { 301 if (vi.isPrestate()) { 302 assert vi.postState != null; // because isPrestate() = true 303 return vi.postState.jml_name() + shift_str(shift); 304 } else { 305 return String.format("\\new(%s)%s", vi.jml_name(), shift_str(shift)); 306 } 307 } else { 308 return vi.jml_name() + shift_str(shift); 309 } 310 } 311 312 /** 313 * Returns the csharp name of a variable which is included inside an expression (such as 314 * orig(a[vi])). If the expression is orig, the orig is implied for this variable. 315 */ 316 protected String inside_csharp_name(VarInfo vi, boolean in_orig, int shift) { 317 if (vi == null) { 318 return ""; 319 } 320 321 if (in_orig) { 322 if (vi.isPrestate()) { 323 assert vi.postState != null; // because isPrestate() = true 324 return vi.postState.csharp_name() + shift_str(shift); 325 } else { 326 // return String.format ("\\new(%s)%s", vi.csharp_name(), shift_str(shift)); 327 return String.format("%s%s", vi.csharp_name(), shift_str(shift)); 328 } 329 } else { 330 return vi.csharp_name() + shift_str(shift); 331 } 332 } 333}