001package daikon.diff; 002 003import daikon.PptConditional; 004import daikon.PptTopLevel; 005import daikon.inv.Invariant; 006import daikon.inv.OutputFormat; 007import java.io.PrintStream; 008import java.util.HashMap; 009import java.util.HashSet; 010import java.util.StringTokenizer; 011import org.checkerframework.checker.nullness.qual.EnsuresNonNullIf; 012import org.checkerframework.checker.nullness.qual.Nullable; 013 014/** 015 * MatchCountVisitor is a visitor that almost does the opposite of PrintDifferingInvariantsVisitor. 016 * MatchCount prints invariant pairs if they are the same, and only if they are a part of a 017 * conditional ppt. The visitor also accumulates some state during its traversal for statistics, and 018 * can report the match precision. 019 * 020 * @author Lee Lin 021 */ 022public class MatchCountVisitor extends PrintAllVisitor { 023 024 // invariants found by the splitting 025 private HashSet<String> cnt = new HashSet<>(); 026 // target set of invariants 027 private HashSet<String> targSet = new HashSet<>(); 028 // invariants found matching 029 private HashSet<String> recall = new HashSet<>(); 030 031 private HashMap<String, HashSet<String>> goodMap = new HashMap<>(); 032 033 public MatchCountVisitor(PrintStream ps, boolean verbose, boolean printEmptyPpts) { 034 super(ps, verbose, printEmptyPpts); 035 } 036 037 // throw out Program points that are not Conditional, 038 // meaning they were NOT added from our splitters 039 @Override 040 public void visit(PptNode node) { 041 PptTopLevel ppt = node.getPpt1(); 042 if (!(ppt instanceof PptConditional)) { 043 return; 044 } else { 045 super.visit(node); 046 } 047 } 048 049 @Override 050 public void visit(InvNode node) { 051 Invariant inv1 = node.getInv1(); 052 Invariant inv2 = node.getInv2(); 053 String key1 = ""; 054 String key2 = ""; 055 056 if (inv1 != null && inv1.justified() && !filterOut(inv1)) { 057 String thisPptName1 = inv1.ppt.name(); 058 // System.out.println ("NAME1: " + thisPptName1); 059 // Contest.smallestRoom(II)I:::EXIT;condition="not(max <= num)" 060 String bucketKey = thisPptName1.substring(0, thisPptName1.lastIndexOf(";condition")); 061 key1 = bucketKey + "$" + inv1.format_using(OutputFormat.JAVA); 062 // checks for justification 063 if (shouldPrint(inv1, inv1)) { // [???] 064 cnt.add(key1); 065 } 066 } 067 068 if (inv2 != null && inv2.justified() && !filterOut(inv2)) { 069 String thisPptName2 = inv2.ppt.name(); 070 String thisPptName2_substring = thisPptName2.substring(0, thisPptName2.lastIndexOf('(')); 071 key2 = thisPptName2_substring + "$" + inv2.format_using(OutputFormat.JAVA); 072 targSet.add(key2); 073 } 074 075 if (shouldPrint(inv1, inv2)) { 076 // inv1 and inv2 should be the same, so it doesn't matter 077 // which one we choose when adding to recall -LL 078 recall.add(key1); 079 080 // System.out.println("K1: " + key1); 081 // System.out.println ("K2: " + key2); 082 083 String thisPptName1 = inv1.ppt.name(); 084 // System.out.println ("NAME1: " + thisPptName1); 085 // Contest.smallestRoom(II)I:::EXIT;condition="not(max <= num)" 086 String bucketKey = thisPptName1.substring(0, thisPptName1.lastIndexOf(";condition")); 087 String predicate = extractPredicate(thisPptName1); 088 HashSet<String> bucket = goodMap.computeIfAbsent(bucketKey, __ -> new HashSet<String>()); 089 bucket.add(predicate + " ==> " + inv1.format()); 090 } 091 } 092 093 /** Grabs the splitting condition from a pptname. */ 094 private String extractPredicate(String s) { 095 int cut = s.indexOf(";condition="); 096 return s.substring(cut + 12, s.lastIndexOf('"')); 097 } 098 099 /** Returns true if the pair of invariants should be printed. */ 100 @EnsuresNonNullIf( 101 result = true, 102 expression = {"#1", "#2"}) 103 protected static boolean shouldPrint(@Nullable Invariant inv1, @Nullable Invariant inv2) { 104 105 int rel = DetailedStatisticsVisitor.determineRelationship(inv1, inv2); 106 if (rel == DetailedStatisticsVisitor.REL_SAME_JUST1_JUST2) { 107 // determineRelationship returns REL_SAME_JUST1_JUST2 only if inv1 and inv2 are nonnull 108 assert inv1 != null : "@AssumeAssertion(nullness): dependent: called determineRelationship()"; 109 assert inv2 != null : "@AssumeAssertion(nullness): dependent: called determineRelationship()"; 110 111 // got rid of unjustified 112 // rel == DetailedStatisticsVisitor.REL_SAME_UNJUST1_UNJUST2) 113 114 // Added to get rid of constants other than -1, 0, 1 in the 115 // invariant's format_java() string... this change was made to 116 // filter out targets that could never really be achived 117 // example: num >= 10378 118 119 if (filterOut(inv1) || filterOut(inv2)) { 120 return false; 121 } 122 123 // now you have a match 124 125 return true; 126 } 127 128 return false; 129 } 130 131 /** 132 * Returns true iff any token of {@code inv.format_java()} contains a number other than -1, 0, 1 133 * or is null. 134 */ 135 private static boolean filterOut(Invariant inv) { 136 assert inv != null : "@AssumeAssertion(nullness): precondition"; 137 String str = inv.format_using(OutputFormat.JAVA); 138 StringTokenizer st = new StringTokenizer(str, " ()"); 139 while (st.hasMoreTokens()) { 140 String oneToken = st.nextToken(); 141 try { 142 char firstChar = oneToken.charAt(0); 143 // remember identifiers can not begin with [0-9\-] 144 if (Character.isDigit(firstChar) || firstChar == '-') { 145 if (acceptableNumber(oneToken)) { 146 continue; 147 } else { 148 return true; 149 } 150 } 151 152 } catch (NumberFormatException e) { 153 System.out.println( 154 "Should never get here... NumberFormatException in filterOut: " + oneToken); 155 continue; 156 } 157 } 158 return false; 159 } 160 161 public double calcRecall() { 162 System.out.println("Recall: " + recall.size() + " / " + targSet.size()); 163 if (targSet.size() == 0) { 164 // avoids divide by zero 165 return -1; 166 } 167 return (double) recall.size() / targSet.size(); 168 } 169 170 /** 171 * Returns true iff numLiteral represents a numeric literal string of integer or float that we 172 * believe will be useful for a splitting condition. Usually that includes -1, 0, 1, and any other 173 * numeric literal found in the source code. 174 */ 175 private static boolean acceptableNumber(String numLiteral) { 176 177 // need to make sure that it is an integer vs. floating 178 // point number 179 180 // could be float, look for "." 181 if (numLiteral.indexOf(".") > -1) { 182 // float fnum = Float.parseFloat(numLiteral); 183 // for now, accept all floats (ignore return value of parseFloat) 184 return true; 185 } 186 // not float, must be int 187 else { 188 int num = Integer.parseInt(numLiteral); 189 190 // accept -1, 0, 1 191 return (num == -1 || num == 0 || num == 1); 192 } 193 } 194 195 public double calcPrecision() { 196 197 System.out.println("Prec: " + recall.size() + " / " + cnt.size()); 198 if (cnt.size() == 0) { 199 // to avoid a divide by zero 200 return -1; 201 } 202 return (double) recall.size() / cnt.size(); 203 } 204 205 /** Prints the results of the correct set in a human-readable format. */ 206 public void printFinal() { 207 for (String ppt : goodMap.keySet()) { 208 System.out.println(); 209 System.out.println("*****************" + ppt); 210 for (String s : goodMap.get(ppt)) { 211 System.out.println(s); 212 } 213 } 214 } 215}