001package daikon.inv.filter; 002 003import daikon.Daikon; 004import daikon.PrintInvariants; 005import daikon.VarInfo; 006import daikon.inv.GuardingImplication; 007import daikon.inv.Implication; 008import daikon.inv.Invariant; 009import daikon.inv.OutputFormat; 010import java.util.ArrayList; 011import java.util.Iterator; 012import java.util.List; 013import java.util.logging.Level; 014import java.util.logging.Logger; 015import org.checkerframework.checker.initialization.qual.UnknownInitialization; 016import org.checkerframework.checker.nullness.qual.MonotonicNonNull; 017import org.checkerframework.checker.nullness.qual.Nullable; 018 019// This class contains a collection of invariant filters, and allows other 020// code to perform invariant filtering. To filter invariants, do the 021// following: 022// o Instantiate an InvariantFilters object. 023// o At any time, adjust the filters as necessary using the public methods. 024// o Call: invariantFilters.shouldKeep( invariant ); 025// 026// There are two main kinds of filters: property filters and variable 027// filters. Property filters attempt to eliminate irrelevant invariants, 028// and are all turned on by default. Variable filters only keep 029// invariants which contain all or any of a set of variables (depending on 030// variableFilterType). There are no variable filters by default. See 031// the manual for more information on property and variable filters. 032 033public class InvariantFilters { 034 public static final int ANY_VARIABLE = 1; 035 public static final int ALL_VARIABLES = 2; 036 int variableFilterType = ANY_VARIABLE; 037 038 // propertyFilters is a map from filter description to filter object. We 039 // need this mapping so that the GUI can easily tell InvariantFilters -- 040 // by passing in a filter description -- which filter was de/selected. 041 // Use TreeMap to preserve order of filters (eg, so that 042 // ControlledInvariantFilter will always be last). 043 044 // annoyingly, this doesn't actually do what the original author 045 // intended. TreeMap orders things based on the keys, which in this 046 // case is the description of the filter (a string). What we'd 047 // actually like is to order them in order of something like 048 // [probability of eliminating an inv]/[expected running time]...in 049 // other words, based on a benefit to cost measurement. hence, this 050 // will become a list (in particular a ArrayList). This does increase 051 // the running time of lookups based on the descriptions from O(log 052 // n) to O(n), but that functionality isn't used a whole lot and 053 // there are only ~10 filters anyway. 054 055 List<InvariantFilter> propertyFilters = new ArrayList<>(); 056 List<VariableFilter> variableFilters = new ArrayList<>(); 057 058 public InvariantFilters() { 059 060 addPropertyFilter(new UnjustifiedFilter()); 061 addPropertyFilter(new ParentFilter()); 062 addPropertyFilter(new ObviousFilter()); 063 064 // This set of filters is invoked when preparing invariants for processing 065 // by Simplify, but before Simplify actually runs this will just not 066 // filter anything, so no need to fear recursiveness here. 067 addPropertyFilter(new SimplifyFilter()); 068 069 addPropertyFilter(new OnlyConstantVariablesFilter()); 070 addPropertyFilter(new DerivedParameterFilter()); 071 if (Daikon.output_format == OutputFormat.ESCJAVA) { 072 addPropertyFilter(new UnmodifiedVariableEqualityFilter()); 073 } 074 075 // Filter out invariants that contain certain types of derived variables 076 // By default, all derived variales are accepted. 077 addPropertyFilter(new DerivedVariableFilter()); 078 079 addPropertyFilter(new ReadonlyPrestateFilter()); 080 081 addPropertyFilter(new DotNetStringFilter()); 082 } 083 084 private static @MonotonicNonNull InvariantFilters default_filters = null; 085 086 public static InvariantFilters defaultFilters() { 087 if (default_filters == null) { 088 default_filters = new InvariantFilters(); 089 } 090 return default_filters; 091 } 092 093 void addPropertyFilter( 094 @UnknownInitialization(InvariantFilters.class) InvariantFilters this, 095 InvariantFilter filter) { 096 propertyFilters.add(filter); 097 } 098 099 public @Nullable InvariantFilter shouldKeepVarFilters(Invariant invariant) { 100 // Logger df = PrintInvariants.debugFiltering; 101 if (variableFilters.size() != 0) { 102 if (variableFilterType == InvariantFilters.ANY_VARIABLE) { 103 boolean hasAnyVariable = false; 104 for (VariableFilter filter : variableFilters) { 105 if (!filter.shouldDiscard(invariant)) { 106 hasAnyVariable = true; 107 } 108 } 109 if (!hasAnyVariable) { 110 if (Invariant.logOn()) { 111 invariant.log("Failed ANY_VARIABLE filter"); 112 } 113 return variableFilters.get(0); 114 } 115 } else if (variableFilterType == InvariantFilters.ALL_VARIABLES) { 116 for (VariableFilter filter : variableFilters) { 117 if (filter.shouldDiscard(invariant)) { 118 if (Invariant.logOn()) { 119 invariant.log("Failed ALL_VARIABLES filter %s", filter.getClass().getName()); 120 } 121 return filter; 122 } 123 } 124 } 125 } 126 return null; 127 } 128 129 public @Nullable InvariantFilter shouldKeepPropFilters(Invariant invariant) { 130 Logger df = PrintInvariants.debugFiltering; 131 for (InvariantFilter filter : propertyFilters) { 132 if (Invariant.logDetail() || df.isLoggable(Level.FINE)) { 133 invariant.log(df, "applying " + filter.getClass().getName()); 134 } 135 if (filter.shouldDiscard(invariant)) { 136 if (Invariant.logOn() || df.isLoggable(Level.FINE)) { 137 invariant.log( 138 df, 139 "failed " 140 + filter.getClass().getName() 141 // + " num_values = " 142 // + ",num_unmod_missing_samples==" + invariant.ppt.num_mod_samples() 143 + ": " 144 + invariant.format()); 145 } 146 return filter; 147 } 148 } 149 return null; 150 } 151 152 public @Nullable InvariantFilter shouldKeep(Invariant invariant) { 153 Logger df = PrintInvariants.debugFiltering; 154 155 if (Invariant.logOn() || df.isLoggable(Level.FINE)) { 156 invariant.log(df, "filtering"); 157 } 158 159 if (invariant instanceof GuardingImplication) { 160 invariant = ((Implication) invariant).right; 161 } 162 163 // Do variable filters first since they eliminate more invariants. 164 InvariantFilter result = shouldKeepVarFilters(invariant); 165 if (result != null) { 166 return result; 167 } 168 169 // Property filters. 170 invariant.log("Processing %s Prop filters", propertyFilters.size()); 171 return shouldKeepPropFilters(invariant); 172 } 173 174 public Iterator<InvariantFilter> getPropertyFiltersIterator() { 175 return propertyFilters.iterator(); 176 } 177 178 private InvariantFilter find(String description) { 179 InvariantFilter answer = null; 180 for (InvariantFilter filter : propertyFilters) { 181 if (filter.getDescription().equals(description)) { 182 answer = filter; 183 } 184 } 185 if (answer == null) { 186 throw new Error("Bad filter description: " + description); 187 } 188 return answer; 189 } 190 191 // Description must be a valid description of a filter 192 public boolean getFilterSetting(String description) { 193 return find(description).getSetting(); 194 } 195 196 // Description must be a valid description of a filter 197 public void changeFilterSetting(String description, boolean turnOn) { 198 InvariantFilter filter = find(description); 199 if (turnOn) { 200 filter.turnOn(); 201 } else { 202 filter.turnOff(); 203 } 204 } 205 206 public void turnFiltersOn() { 207 for (InvariantFilter filter : propertyFilters) { 208 filter.turnOn(); 209 } 210 } 211 212 public void turnFiltersOff() { 213 for (InvariantFilter filter : propertyFilters) { 214 filter.turnOff(); 215 } 216 } 217 218 public void addVariableFilter(String variable) { 219 variableFilters.add(new VariableFilter(variable)); 220 } 221 222 public boolean containsVariableFilter(String variable) { 223 for (VariableFilter vf : variableFilters) { 224 if (vf.getVariable().equals(variable)) { 225 return true; 226 } 227 } 228 return false; 229 } 230 231 public void removeVariableFilter(String variable) { 232 boolean foundOnce = false; 233 for (Iterator<VariableFilter> iter = variableFilters.iterator(); iter.hasNext(); ) { 234 VariableFilter vf = iter.next(); 235 if (vf.getVariable().equals(variable)) { 236 iter.remove(); 237 foundOnce = true; 238 } 239 } 240 if (foundOnce) { 241 return; 242 } 243 244 throw new Error( 245 "InvariantFilters.removeVariableFilter(): filter for variable '" 246 + variable 247 + "' not found"); 248 } 249 250 // variableFilterType is either InvariantFilters.ANY_VARIABLE or InvariantFilters.ALL_VARIABLES 251 public void setVariableFilterType(int variableFilterType) { 252 this.variableFilterType = variableFilterType; 253 } 254 255 // I wasn't sure where to put this method, but this class seems like the 256 // best place. Equality invariants only exist to make invariant output 257 // more readable, so this shouldn't be in the main Daikon engine code. 258 // Equality invariants aren't *directly* related to filtering, but their 259 // existence allows us to filter out certain invariants containing 260 // non-canonical variables ("x=y", "x=z", etc). Also, I am hesitant to 261 // put code dealing with the internal workings of invariants/daikon in 262 // the GUI package. Therefore, I put the method here rather than in 263 // InvariantsGUI.java. 264 265 /** 266 * This function takes a list of invariants, finds the equality Comparison invariants (x==y, 267 * y==z), and deletes and replaces them with Equality invariants (x==y==z). The first variable in 268 * an Equality invariant is always the canonical variable of the group. The Equality invariants 269 * are inserted into the beginning. Equality invariants are useful when it comes to displaying 270 * invariants. 271 */ 272 public static List<Invariant> addEqualityInvariants(List<Invariant> invariants) { 273 274 return invariants; 275 } 276 277 // For debugging (not very efficient) 278 static String reprVarInfoList(List<VarInfo> vis) { 279 String result = ""; 280 for (int i = 0; i < vis.size(); i++) { 281 if (i != 0) { 282 result += " "; 283 } 284 VarInfo vi = vis.get(i); 285 result += vi.name(); 286 } 287 return "[ " + result + " ]"; 288 } 289}