001package daikon.inv.filter; 002 003import daikon.Debug; 004import daikon.PptRelation; 005import daikon.PptSlice; 006import daikon.VarInfo; 007import daikon.inv.Invariant; 008import java.util.Arrays; 009import java.util.List; 010import org.checkerframework.checker.nullness.qual.Nullable; 011 012/** Filter for not printing invariants that have a matching invariant at their parent PPT. */ 013public class ParentFilter extends InvariantFilter { 014 @Override 015 public String getDescription() { 016 return "Filter invariants that match a parent program point invariant"; 017 } 018 019 /** Boolean. If true, ParentFilter is initially turned on. */ 020 public static boolean dkconfig_enabled = true; 021 022 public ParentFilter() { 023 isOn = dkconfig_enabled; 024 } 025 026 private static boolean debug = false; 027 028 // private static boolean debug = true; 029 030 @Override 031 boolean shouldDiscardInvariant(Invariant inv) { 032 033 // System.out.printf("shouldDiscardInvariant(%s)%n", inv.format()); 034 035 if (Debug.logDetail()) { 036 if (inv.ppt.parent.parents != null) { 037 inv.log( 038 "%s has PptTopLevel %s which has %d parents", 039 inv.format(), inv.ppt.parent.name, inv.ppt.parent.parents.size()); 040 for (PptRelation rel : inv.ppt.parent.parents) { 041 inv.log("--%s%n", rel); 042 inv.log("--variables: %s", Arrays.toString(rel.parent.var_infos)); 043 inv.log("--map: %s", rel.child_to_parent_map); 044 } 045 } else { 046 inv.log("%s has PptTopLevel %s which has 0 parents", inv.format(), inv.ppt.parent.name); 047 } 048 } 049 050 // If there are no parents, can't discard 051 if (inv.ppt.parent.parents == null) { 052 return false; 053 } 054 055 // Loop through each parent ppt getting the parent/child relation info 056 outer: 057 for (PptRelation rel : inv.ppt.parent.parents) { 058 059 if (Debug.logDetail()) { 060 inv.log(" considering parent %s [%s]", rel, rel.parent.name()); 061 } 062 063 // Look up each variable in the parent, skip this parent if any 064 // variables don't exist in the parent. 065 @Nullable VarInfo[] pvis_raw = new VarInfo[inv.ppt.var_infos.length]; 066 for (int j = 0; j < pvis_raw.length; j++) { 067 pvis_raw[j] = rel.parentVar(inv.ppt.var_infos[j]); 068 // pvis_raw[j] *can* be null. Why, and is that a problem? -MDE 069 if (pvis_raw[j] == null) { 070 if (Debug.logDetail()) { 071 inv.log( 072 "variable %s [%s] cannot be found in %s", 073 inv.ppt.var_infos[j], inv.ppt.var_infos[j].get_equalitySet_vars(), rel); 074 for (VarInfo evi : inv.ppt.var_infos[j].get_equalitySet_vars()) { 075 inv.log( 076 "var %s index %d, dp %b, depth %d, complex %d, idp %s, name %s, param vars %s", 077 evi, 078 evi.varinfo_index, 079 evi.isDerivedParamAndUninteresting(), 080 evi.derivedDepth(), 081 evi.complexity(), 082 evi.isDerivedParam(), 083 evi.get_VarInfoName(), 084 evi.ppt.getParamVars()); 085 } 086 } 087 continue outer; 088 } 089 } 090 @SuppressWarnings("nullness") // at this point, pvis contains only non-null elements 091 VarInfo[] pvis = pvis_raw; 092 093 if (Debug.logDetail()) { 094 inv.log(" got variables"); 095 } 096 097 // Sort the parent variables in index order 098 Arrays.sort(pvis, VarInfo.IndexComparator.getInstance()); 099 if (Debug.logDetail()) { 100 inv.log("Found parent vars: %s", Arrays.toString(pvis)); 101 } 102 103 // Lookup the slice, skip if not found 104 PptSlice pslice = rel.parent.findSlice(pvis); 105 if (pslice == null) { 106 continue; 107 } 108 if (Debug.logDetail()) { 109 inv.log("Found parent slice: %s", pslice.name()); 110 } 111 112 // System.out.printf(" found parent slice (%d invs): %s%n", pslice.invs.size(), 113 // pslice.name()); 114 115 // Look for a matching invariant in the parent slice. 116 for (Invariant pinv : pslice.invs) { 117 // System.out.printf(" inv in parent slice: %s%n", pinv.format()); 118 if (pinv.isGuardingPredicate) { 119 continue; 120 } 121 if (pinv.getClass() != inv.getClass()) { 122 continue; 123 } 124 if (!pinv.isSameFormula(inv)) { 125 continue; 126 } 127 128 // Check that all the guard variables correspond. 129 List<VarInfo> guardedVars = inv.getGuardingList(); 130 List<VarInfo> pGuardedVars = pinv.getGuardingList(); 131 // Optimization: bail our early if size of list is different. 132 if ((guardedVars.size() != pGuardedVars.size()) 133 && (guardedVars.size() != pGuardedVars.size() + 1)) { 134 continue; 135 } 136 boolean var_mismatch = false; 137 for (VarInfo v : guardedVars) { 138 VarInfo pv = rel.parentVarAnyInEquality(v); 139 // VarInfo pv = rel.parentVar(v); 140 if (pv == null) { 141 if (debug) { 142 System.out.printf(" ParentFilter %s, parent %s%n", inv.format(), pslice.name()); 143 System.out.printf(" No parent var for %s via %s%n", v.name(), rel); 144 System.out.printf(" Equality set: %s%n", v.equalitySet.shortString()); 145 } 146 var_mismatch = true; 147 break; 148 } 149 if (!(pv.name().equals("this") || pGuardedVars.contains(pv))) { 150 if (debug) { 151 System.out.printf( 152 "Not in guarding list %s for %s: parent var %s at %s for %s at %s%n", 153 guardedVars, pinv, pv, rel.parent, v.name(), rel.child); 154 } 155 VarInfo pgv = pGuardedVars.size() > 0 ? pGuardedVars.get(0) : null; 156 assert (pgv != pv); 157 if (debug && pgv != null) { 158 System.out.printf( 159 "%s is index %d at %s, %s is index %d at %s%n", 160 pgv, pgv.varinfo_index, pgv.ppt.name, pv, pv.varinfo_index, pv.ppt.name); 161 } 162 var_mismatch = true; 163 break; 164 } 165 } 166 if (var_mismatch) { 167 continue; 168 } 169 170 if (Invariant.logOn()) { 171 inv.log( 172 "Filtered by parent inv '%s' at ppt %s with rel %s", 173 pinv.format(), pslice.name(), rel); 174 for (VarInfo cvi : inv.ppt.var_infos) { 175 inv.log("child variable %s matches parent variable %s", cvi, rel.parentVar(cvi)); 176 for (VarInfo evi : cvi.get_equalitySet_vars()) { 177 inv.log( 178 "var %s index %d, dp %b, depth %d, complex %d", 179 evi, 180 evi.varinfo_index, 181 evi.isDerivedParamAndUninteresting(), 182 evi.derivedDepth(), 183 evi.complexity()); 184 } 185 } 186 } 187 return true; 188 } 189 } 190 191 return false; 192 } 193}