1# DExTer : Debugging Experience Tester 2# ~~~~~~ ~ ~~ ~ ~~ 3# 4# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5# See https://llvm.org/LICENSE.txt for license information. 6# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7"""Calculate a 'score' based on some dextIR. 8Assign penalties based on different commands to decrease the score. 91.000 would be a perfect score. 100.000 is the worst theoretical score possible. 11""" 12 13from collections import defaultdict, namedtuple, Counter 14import difflib 15import os 16from itertools import groupby 17from dex.command.StepValueInfo import StepValueInfo 18 19 20PenaltyCommand = namedtuple('PenaltyCommand', ['pen_dict', 'max_penalty']) 21# 'meta' field used in different ways by different things 22PenaltyInstance = namedtuple('PenaltyInstance', ['meta', 'the_penalty']) 23 24 25def add_heuristic_tool_arguments(parser): 26 parser.add_argument( 27 '--penalty-variable-optimized', 28 type=int, 29 default=3, 30 help='set the penalty multiplier for each' 31 ' occurrence of a variable that was optimized' 32 ' away', 33 metavar='<int>') 34 parser.add_argument( 35 '--penalty-misordered-values', 36 type=int, 37 default=3, 38 help='set the penalty multiplier for each' 39 ' occurrence of a misordered value.', 40 metavar='<int>') 41 parser.add_argument( 42 '--penalty-irretrievable', 43 type=int, 44 default=4, 45 help='set the penalty multiplier for each' 46 " occurrence of a variable that couldn't" 47 ' be retrieved', 48 metavar='<int>') 49 parser.add_argument( 50 '--penalty-not-evaluatable', 51 type=int, 52 default=5, 53 help='set the penalty multiplier for each' 54 " occurrence of a variable that couldn't" 55 ' be evaluated', 56 metavar='<int>') 57 parser.add_argument( 58 '--penalty-missing-values', 59 type=int, 60 default=6, 61 help='set the penalty multiplier for each missing' 62 ' value', 63 metavar='<int>') 64 parser.add_argument( 65 '--penalty-incorrect-values', 66 type=int, 67 default=7, 68 help='set the penalty multiplier for each' 69 ' occurrence of an unexpected value.', 70 metavar='<int>') 71 parser.add_argument( 72 '--penalty-unreachable', 73 type=int, 74 default=4, # XXX XXX XXX selected by random 75 help='set the penalty for each line stepped onto that should' 76 ' have been unreachable.', 77 metavar='<int>') 78 parser.add_argument( 79 '--penalty-misordered-steps', 80 type=int, 81 default=2, # XXX XXX XXX selected by random 82 help='set the penalty for differences in the order of steps' 83 ' the program was expected to observe.', 84 metavar='<int>') 85 parser.add_argument( 86 '--penalty-missing-step', 87 type=int, 88 default=4, # XXX XXX XXX selected by random 89 help='set the penalty for the program skipping over a step.', 90 metavar='<int>') 91 parser.add_argument( 92 '--penalty-incorrect-program-state', 93 type=int, 94 default=4, # XXX XXX XXX selected by random 95 help='set the penalty for the program never entering an expected state' 96 ' or entering an unexpected state.', 97 metavar='<int>') 98 99 100class Heuristic(object): 101 def __init__(self, context, steps): 102 self.context = context 103 self.penalties = {} 104 105 worst_penalty = max([ 106 self.penalty_variable_optimized, self.penalty_irretrievable, 107 self.penalty_not_evaluatable, self.penalty_incorrect_values, 108 self.penalty_missing_values, self.penalty_unreachable, 109 self.penalty_missing_step, self.penalty_misordered_steps 110 ]) 111 112 # Get DexExpectWatchType results. 113 try: 114 for command in steps.commands['DexExpectWatchType']: 115 command.eval(steps) 116 maximum_possible_penalty = min(3, len( 117 command.values)) * worst_penalty 118 name, p = self._calculate_expect_watch_penalties( 119 command, maximum_possible_penalty) 120 name = name + ' ExpectType' 121 self.penalties[name] = PenaltyCommand(p, 122 maximum_possible_penalty) 123 except KeyError: 124 pass 125 126 # Get DexExpectWatchValue results. 127 try: 128 for command in steps.commands['DexExpectWatchValue']: 129 command.eval(steps) 130 maximum_possible_penalty = min(3, len( 131 command.values)) * worst_penalty 132 name, p = self._calculate_expect_watch_penalties( 133 command, maximum_possible_penalty) 134 name = name + ' ExpectValue' 135 self.penalties[name] = PenaltyCommand(p, 136 maximum_possible_penalty) 137 except KeyError: 138 pass 139 140 try: 141 penalties = defaultdict(list) 142 maximum_possible_penalty_all = 0 143 for expect_state in steps.commands['DexExpectProgramState']: 144 success = expect_state.eval(steps) 145 p = 0 if success else self.penalty_incorrect_program_state 146 147 meta = 'expected {}: {}'.format( 148 '{} times'.format(expect_state.times) 149 if expect_state.times >= 0 else 'at least once', 150 expect_state.program_state_text) 151 152 if success: 153 meta = '<g>{}</>'.format(meta) 154 155 maximum_possible_penalty = self.penalty_incorrect_program_state 156 maximum_possible_penalty_all += maximum_possible_penalty 157 name = expect_state.program_state_text 158 penalties[meta] = [PenaltyInstance('{} times'.format( 159 len(expect_state.encounters)), p)] 160 self.penalties['expected program states'] = PenaltyCommand( 161 penalties, maximum_possible_penalty_all) 162 except KeyError: 163 pass 164 165 # Get the total number of each step kind. 166 step_kind_counts = defaultdict(int) 167 for step in getattr(steps, 'steps'): 168 step_kind_counts[step.step_kind] += 1 169 170 # Get DexExpectStepKind results. 171 penalties = defaultdict(list) 172 maximum_possible_penalty_all = 0 173 try: 174 for command in steps.commands['DexExpectStepKind']: 175 command.eval() 176 # Cap the penalty at 2 * expected count or else 1 177 maximum_possible_penalty = max(command.count * 2, 1) 178 p = abs(command.count - step_kind_counts[command.name]) 179 actual_penalty = min(p, maximum_possible_penalty) 180 key = ('{}'.format(command.name) 181 if actual_penalty else '<g>{}</>'.format(command.name)) 182 penalties[key] = [PenaltyInstance(p, actual_penalty)] 183 maximum_possible_penalty_all += maximum_possible_penalty 184 self.penalties['step kind differences'] = PenaltyCommand( 185 penalties, maximum_possible_penalty_all) 186 except KeyError: 187 pass 188 189 if 'DexUnreachable' in steps.commands: 190 cmds = steps.commands['DexUnreachable'] 191 unreach_count = 0 192 193 # Find steps with unreachable in them 194 ureachs = [ 195 s for s in steps.steps if 'DexUnreachable' in s.watches.keys() 196 ] 197 198 # There's no need to match up cmds with the actual watches 199 upen = self.penalty_unreachable 200 201 count = upen * len(ureachs) 202 if count != 0: 203 d = dict() 204 for x in ureachs: 205 msg = 'line {} reached'.format(x.current_location.lineno) 206 d[msg] = [PenaltyInstance(upen, upen)] 207 else: 208 d = { 209 '<g>No unreachable lines seen</>': [PenaltyInstance(0, 0)] 210 } 211 total = PenaltyCommand(d, len(cmds) * upen) 212 213 self.penalties['unreachable lines'] = total 214 215 if 'DexExpectStepOrder' in steps.commands: 216 cmds = steps.commands['DexExpectStepOrder'] 217 218 # Form a list of which line/cmd we _should_ have seen 219 cmd_num_lst = [(x, c.lineno) for c in cmds 220 for x in c.sequence] 221 # Order them by the sequence number 222 cmd_num_lst.sort(key=lambda t: t[0]) 223 # Strip out sequence key 224 cmd_num_lst = [y for x, y in cmd_num_lst] 225 226 # Now do the same, but for the actually observed lines/cmds 227 ss = steps.steps 228 deso = [s for s in ss if 'DexExpectStepOrder' in s.watches.keys()] 229 deso = [s.watches['DexExpectStepOrder'] for s in deso] 230 # We rely on the steps remaining in order here 231 order_list = [int(x.expression) for x in deso] 232 233 # First off, check to see whether or not there are missing items 234 expected = Counter(cmd_num_lst) 235 seen = Counter(order_list) 236 237 unseen_line_dict = dict() 238 skipped_line_dict = dict() 239 240 mispen = self.penalty_missing_step 241 num_missing = 0 242 num_repeats = 0 243 for k, v in expected.items(): 244 if k not in seen: 245 msg = 'Line {} not seen'.format(k) 246 unseen_line_dict[msg] = [PenaltyInstance(mispen, mispen)] 247 num_missing += v 248 elif v > seen[k]: 249 msg = 'Line {} skipped at least once'.format(k) 250 skipped_line_dict[msg] = [PenaltyInstance(mispen, mispen)] 251 num_missing += v - seen[k] 252 elif v < seen[k]: 253 # Don't penalise unexpected extra sightings of a line 254 # for now 255 num_repeats = seen[k] - v 256 pass 257 258 if len(unseen_line_dict) == 0: 259 pi = PenaltyInstance(0, 0) 260 unseen_line_dict['<g>All lines were seen</>'] = [pi] 261 262 if len(skipped_line_dict) == 0: 263 pi = PenaltyInstance(0, 0) 264 skipped_line_dict['<g>No lines were skipped</>'] = [pi] 265 266 total = PenaltyCommand(unseen_line_dict, len(expected) * mispen) 267 self.penalties['Unseen lines'] = total 268 total = PenaltyCommand(skipped_line_dict, len(expected) * mispen) 269 self.penalties['Skipped lines'] = total 270 271 ordpen = self.penalty_misordered_steps 272 cmd_num_lst = [str(x) for x in cmd_num_lst] 273 order_list = [str(x) for x in order_list] 274 lst = list(difflib.Differ().compare(cmd_num_lst, order_list)) 275 diff_detail = Counter(l[0] for l in lst) 276 277 assert '?' not in diff_detail 278 279 # Diffs are hard to interpret; there are many algorithms for 280 # condensing them. Ignore all that, and just print out the changed 281 # sequences, it's up to the user to interpret what's going on. 282 283 def filt_lines(s, seg, e, key): 284 lst = [s] 285 for x in seg: 286 if x[0] == key: 287 lst.append(int(x[2:])) 288 lst.append(e) 289 return lst 290 291 diff_msgs = dict() 292 293 def reportdiff(start_idx, segment, end_idx): 294 msg = 'Order mismatch, expected linenos {}, saw {}' 295 expected_linenos = filt_lines(start_idx, segment, end_idx, '-') 296 seen_linenos = filt_lines(start_idx, segment, end_idx, '+') 297 msg = msg.format(expected_linenos, seen_linenos) 298 diff_msgs[msg] = [PenaltyInstance(ordpen, ordpen)] 299 300 # Group by changed segments. 301 start_expt_step = 0 302 end_expt_step = 0 303 to_print_lst = [] 304 for k, subit in groupby(lst, lambda x: x[0] == ' '): 305 if k: # Whitespace group 306 nochanged = [x for x in subit] 307 end_expt_step = int(nochanged[0][2:]) 308 if len(to_print_lst) > 0: 309 reportdiff(start_expt_step, to_print_lst, 310 end_expt_step) 311 start_expt_step = int(nochanged[-1][2:]) 312 to_print_lst = [] 313 else: # Diff group, save for printing 314 to_print_lst = [x for x in subit] 315 316 # If there was a dangling different step, print that too. 317 if len(to_print_lst) > 0: 318 reportdiff(start_expt_step, to_print_lst, '[End]') 319 320 if len(diff_msgs) == 0: 321 diff_msgs['<g>No lines misordered</>'] = [ 322 PenaltyInstance(0, 0) 323 ] 324 total = PenaltyCommand(diff_msgs, len(cmd_num_lst) * ordpen) 325 self.penalties['Misordered lines'] = total 326 327 return 328 329 def _calculate_expect_watch_penalties(self, c, maximum_possible_penalty): 330 penalties = defaultdict(list) 331 332 if c.line_range[0] == c.line_range[-1]: 333 line_range = str(c.line_range[0]) 334 else: 335 line_range = '{}-{}'.format(c.line_range[0], c.line_range[-1]) 336 337 name = '{}:{} [{}]'.format( 338 os.path.basename(c.path), line_range, c.expression) 339 340 num_actual_watches = len(c.expected_watches) + len( 341 c.unexpected_watches) 342 343 penalty_available = maximum_possible_penalty 344 345 # Only penalize for missing values if we have actually seen a watch 346 # that's returned us an actual value at some point, or if we've not 347 # encountered the value at all. 348 if num_actual_watches or c.times_encountered == 0: 349 for v in c.missing_values: 350 current_penalty = min(penalty_available, 351 self.penalty_missing_values) 352 penalty_available -= current_penalty 353 penalties['missing values'].append( 354 PenaltyInstance(v, current_penalty)) 355 356 for v in c.encountered_values: 357 penalties['<g>expected encountered watches</>'].append( 358 PenaltyInstance(v, 0)) 359 360 penalty_descriptions = [ 361 (self.penalty_not_evaluatable, c.invalid_watches, 362 'could not evaluate'), 363 (self.penalty_variable_optimized, c.optimized_out_watches, 364 'result optimized away'), 365 (self.penalty_misordered_values, c.misordered_watches, 366 'misordered result'), 367 (self.penalty_irretrievable, c.irretrievable_watches, 368 'result could not be retrieved'), 369 (self.penalty_incorrect_values, c.unexpected_watches, 370 'unexpected result'), 371 ] 372 373 for penalty_score, watches, description in penalty_descriptions: 374 # We only penalize the encountered issue for each missing value per 375 # command but we still want to record each one, so set the penalty 376 # to 0 after the threshold is passed. 377 times_to_penalize = len(c.missing_values) 378 379 for w in watches: 380 times_to_penalize -= 1 381 penalty_score = min(penalty_available, penalty_score) 382 penalty_available -= penalty_score 383 penalties[description].append( 384 PenaltyInstance(w, penalty_score)) 385 if not times_to_penalize: 386 penalty_score = 0 387 388 return name, penalties 389 390 @property 391 def penalty(self): 392 result = 0 393 394 maximum_allowed_penalty = 0 395 for name, pen_cmd in self.penalties.items(): 396 maximum_allowed_penalty += pen_cmd.max_penalty 397 value = pen_cmd.pen_dict 398 for category, inst_list in value.items(): 399 result += sum(x.the_penalty for x in inst_list) 400 return min(result, maximum_allowed_penalty) 401 402 @property 403 def max_penalty(self): 404 return sum(p_cat.max_penalty for p_cat in self.penalties.values()) 405 406 @property 407 def score(self): 408 try: 409 return 1.0 - (self.penalty / float(self.max_penalty)) 410 except ZeroDivisionError: 411 return float('nan') 412 413 @property 414 def summary_string(self): 415 score = self.score 416 isnan = score != score # pylint: disable=comparison-with-itself 417 color = 'g' 418 if score < 0.25 or isnan: 419 color = 'r' 420 elif score < 0.75: 421 color = 'y' 422 423 return '<{}>({:.4f})</>'.format(color, score) 424 425 @property 426 def verbose_output(self): # noqa 427 string = '' 428 string += ('\n') 429 for command in sorted(self.penalties): 430 pen_cmd = self.penalties[command] 431 maximum_possible_penalty = pen_cmd.max_penalty 432 total_penalty = 0 433 lines = [] 434 for category in sorted(pen_cmd.pen_dict): 435 lines.append(' <r>{}</>:\n'.format(category)) 436 437 for result, penalty in pen_cmd.pen_dict[category]: 438 if isinstance(result, StepValueInfo): 439 text = 'step {}'.format(result.step_index) 440 if result.expected_value: 441 text += ' ({})'.format(result.expected_value) 442 else: 443 text = str(result) 444 if penalty: 445 assert penalty > 0, penalty 446 total_penalty += penalty 447 text += ' <r>[-{}]</>'.format(penalty) 448 lines.append(' {}\n'.format(text)) 449 450 lines.append('\n') 451 452 string += (' <b>{}</> <y>[{}/{}]</>\n'.format( 453 command, total_penalty, maximum_possible_penalty)) 454 for line in lines: 455 string += (line) 456 string += ('\n') 457 return string 458 459 @property 460 def penalty_variable_optimized(self): 461 return self.context.options.penalty_variable_optimized 462 463 @property 464 def penalty_irretrievable(self): 465 return self.context.options.penalty_irretrievable 466 467 @property 468 def penalty_not_evaluatable(self): 469 return self.context.options.penalty_not_evaluatable 470 471 @property 472 def penalty_incorrect_values(self): 473 return self.context.options.penalty_incorrect_values 474 475 @property 476 def penalty_missing_values(self): 477 return self.context.options.penalty_missing_values 478 479 @property 480 def penalty_misordered_values(self): 481 return self.context.options.penalty_misordered_values 482 483 @property 484 def penalty_unreachable(self): 485 return self.context.options.penalty_unreachable 486 487 @property 488 def penalty_missing_step(self): 489 return self.context.options.penalty_missing_step 490 491 @property 492 def penalty_misordered_steps(self): 493 return self.context.options.penalty_misordered_steps 494 495 @property 496 def penalty_incorrect_program_state(self): 497 return self.context.options.penalty_incorrect_program_state 498