1#!/usr/bin/env python 2 3""" 4CmpRuns - A simple tool for comparing two static analyzer runs to determine 5which reports have been added, removed, or changed. 6 7This is designed to support automated testing using the static analyzer, from 8two perspectives: 9 1. To monitor changes in the static analyzer's reports on real code bases, 10 for regression testing. 11 12 2. For use by end users who want to integrate regular static analyzer testing 13 into a buildbot like environment. 14 15Usage: 16 17 # Load the results of both runs, to obtain lists of the corresponding 18 # AnalysisDiagnostic objects. 19 # 20 resultsA = load_results_from_single_run(singleRunInfoA, delete_empty) 21 resultsB = load_results_from_single_run(singleRunInfoB, delete_empty) 22 23 # Generate a relation from diagnostics in run A to diagnostics in run B 24 # to obtain a list of triples (a, b, confidence). 25 diff = compare_results(resultsA, resultsB) 26 27""" 28import json 29import os 30import plistlib 31import re 32import sys 33 34from math import log 35from collections import defaultdict 36from copy import copy 37from enum import Enum 38from typing import (Any, DefaultDict, Dict, List, NamedTuple, Optional, 39 Sequence, TextIO, TypeVar, Tuple, Union) 40 41 42Number = Union[int, float] 43Stats = Dict[str, Dict[str, Number]] 44Plist = Dict[str, Any] 45JSON = Dict[str, Any] 46# Diff in a form: field -> (before, after) 47JSONDiff = Dict[str, Tuple[str, str]] 48# Type for generics 49T = TypeVar('T') 50 51STATS_REGEXP = re.compile(r"Statistics: (\{.+\})", re.MULTILINE | re.DOTALL) 52 53 54class Colors: 55 """ 56 Color for terminal highlight. 57 """ 58 RED = '\x1b[2;30;41m' 59 GREEN = '\x1b[6;30;42m' 60 CLEAR = '\x1b[0m' 61 62 63class HistogramType(str, Enum): 64 RELATIVE = "relative" 65 LOG_RELATIVE = "log-relative" 66 ABSOLUTE = "absolute" 67 68 69class ResultsDirectory(NamedTuple): 70 path: str 71 root: str = "" 72 73 74class SingleRunInfo: 75 """ 76 Information about analysis run: 77 path - the analysis output directory 78 root - the name of the root directory, which will be disregarded when 79 determining the source file name 80 """ 81 def __init__(self, results: ResultsDirectory, 82 verbose_log: Optional[str] = None): 83 self.path = results.path 84 self.root = results.root.rstrip("/\\") 85 self.verbose_log = verbose_log 86 87 88class AnalysisDiagnostic: 89 def __init__(self, data: Plist, report: "AnalysisReport", 90 html_report: Optional[str]): 91 self._data = data 92 self._loc = self._data['location'] 93 self._report = report 94 self._html_report = html_report 95 self._report_size = len(self._data['path']) 96 97 def get_file_name(self) -> str: 98 root = self._report.run.root 99 file_name = self._report.files[self._loc['file']] 100 101 if file_name.startswith(root) and len(root) > 0: 102 return file_name[len(root) + 1:] 103 104 return file_name 105 106 def get_root_file_name(self) -> str: 107 path = self._data['path'] 108 109 if not path: 110 return self.get_file_name() 111 112 p = path[0] 113 if 'location' in p: 114 file_index = p['location']['file'] 115 else: # control edge 116 file_index = path[0]['edges'][0]['start'][0]['file'] 117 118 out = self._report.files[file_index] 119 root = self._report.run.root 120 121 if out.startswith(root): 122 return out[len(root):] 123 124 return out 125 126 def get_line(self) -> int: 127 return self._loc['line'] 128 129 def get_column(self) -> int: 130 return self._loc['col'] 131 132 def get_path_length(self) -> int: 133 return self._report_size 134 135 def get_category(self) -> str: 136 return self._data['category'] 137 138 def get_description(self) -> str: 139 return self._data['description'] 140 141 def get_location(self) -> str: 142 return f"{self.get_file_name()}:{self.get_line()}:{self.get_column()}" 143 144 def get_issue_identifier(self) -> str: 145 id = self.get_file_name() + "+" 146 147 if "issue_context" in self._data: 148 id += self._data["issue_context"] + "+" 149 150 if "issue_hash_content_of_line_in_context" in self._data: 151 id += str(self._data["issue_hash_content_of_line_in_context"]) 152 153 return id 154 155 def get_html_report(self) -> str: 156 if self._html_report is None: 157 return " " 158 159 return os.path.join(self._report.run.path, self._html_report) 160 161 def get_readable_name(self) -> str: 162 if "issue_context" in self._data: 163 funcname_postfix = "#" + self._data["issue_context"] 164 else: 165 funcname_postfix = "" 166 167 root_filename = self.get_root_file_name() 168 file_name = self.get_file_name() 169 170 if root_filename != file_name: 171 file_prefix = f"[{root_filename}] {file_name}" 172 else: 173 file_prefix = root_filename 174 175 line = self.get_line() 176 col = self.get_column() 177 return f"{file_prefix}{funcname_postfix}:{line}:{col}" \ 178 f", {self.get_category()}: {self.get_description()}" 179 180 KEY_FIELDS = ["check_name", "category", "description"] 181 182 def is_similar_to(self, other: "AnalysisDiagnostic") -> bool: 183 # We consider two diagnostics similar only if at least one 184 # of the key fields is the same in both diagnostics. 185 return len(self.get_diffs(other)) != len(self.KEY_FIELDS) 186 187 def get_diffs(self, other: "AnalysisDiagnostic") -> JSONDiff: 188 return {field: (self._data[field], other._data[field]) 189 for field in self.KEY_FIELDS 190 if self._data[field] != other._data[field]} 191 192 # Note, the data format is not an API and may change from one analyzer 193 # version to another. 194 def get_raw_data(self) -> Plist: 195 return self._data 196 197 def __eq__(self, other: object) -> bool: 198 return hash(self) == hash(other) 199 200 def __ne__(self, other: object) -> bool: 201 return hash(self) != hash(other) 202 203 def __hash__(self) -> int: 204 return hash(self.get_issue_identifier()) 205 206 207class AnalysisRun: 208 def __init__(self, info: SingleRunInfo): 209 self.path = info.path 210 self.root = info.root 211 self.info = info 212 self.reports: List[AnalysisReport] = [] 213 # Cumulative list of all diagnostics from all the reports. 214 self.diagnostics: List[AnalysisDiagnostic] = [] 215 self.clang_version: Optional[str] = None 216 self.raw_stats: List[JSON] = [] 217 218 def get_clang_version(self) -> Optional[str]: 219 return self.clang_version 220 221 def read_single_file(self, path: str, delete_empty: bool): 222 with open(path, "rb") as plist_file: 223 data = plistlib.load(plist_file) 224 225 if 'statistics' in data: 226 self.raw_stats.append(json.loads(data['statistics'])) 227 data.pop('statistics') 228 229 # We want to retrieve the clang version even if there are no 230 # reports. Assume that all reports were created using the same 231 # clang version (this is always true and is more efficient). 232 if 'clang_version' in data: 233 if self.clang_version is None: 234 self.clang_version = data.pop('clang_version') 235 else: 236 data.pop('clang_version') 237 238 # Ignore/delete empty reports. 239 if not data['files']: 240 if delete_empty: 241 os.remove(path) 242 return 243 244 # Extract the HTML reports, if they exists. 245 if 'HTMLDiagnostics_files' in data['diagnostics'][0]: 246 htmlFiles = [] 247 for d in data['diagnostics']: 248 # FIXME: Why is this named files, when does it have multiple 249 # files? 250 assert len(d['HTMLDiagnostics_files']) == 1 251 htmlFiles.append(d.pop('HTMLDiagnostics_files')[0]) 252 else: 253 htmlFiles = [None] * len(data['diagnostics']) 254 255 report = AnalysisReport(self, data.pop('files')) 256 diagnostics = [AnalysisDiagnostic(d, report, h) 257 for d, h in zip(data.pop('diagnostics'), htmlFiles)] 258 259 assert not data 260 261 report.diagnostics.extend(diagnostics) 262 self.reports.append(report) 263 self.diagnostics.extend(diagnostics) 264 265 266class AnalysisReport: 267 def __init__(self, run: AnalysisRun, files: List[str]): 268 self.run = run 269 self.files = files 270 self.diagnostics: List[AnalysisDiagnostic] = [] 271 272 273def load_results(results: ResultsDirectory, delete_empty: bool = True, 274 verbose_log: Optional[str] = None) -> AnalysisRun: 275 """ 276 Backwards compatibility API. 277 """ 278 return load_results_from_single_run(SingleRunInfo(results, 279 verbose_log), 280 delete_empty) 281 282 283def load_results_from_single_run(info: SingleRunInfo, 284 delete_empty: bool = True) -> AnalysisRun: 285 """ 286 # Load results of the analyzes from a given output folder. 287 # - info is the SingleRunInfo object 288 # - delete_empty specifies if the empty plist files should be deleted 289 290 """ 291 path = info.path 292 run = AnalysisRun(info) 293 294 if os.path.isfile(path): 295 run.read_single_file(path, delete_empty) 296 else: 297 for dirpath, dirnames, filenames in os.walk(path): 298 for f in filenames: 299 if not f.endswith('plist'): 300 continue 301 302 p = os.path.join(dirpath, f) 303 run.read_single_file(p, delete_empty) 304 305 return run 306 307 308def cmp_analysis_diagnostic(d): 309 return d.get_issue_identifier() 310 311 312AnalysisDiagnosticPair = Tuple[AnalysisDiagnostic, AnalysisDiagnostic] 313 314 315class ComparisonResult: 316 def __init__(self): 317 self.present_in_both: List[AnalysisDiagnostic] = [] 318 self.present_only_in_old: List[AnalysisDiagnostic] = [] 319 self.present_only_in_new: List[AnalysisDiagnostic] = [] 320 self.changed_between_new_and_old: List[AnalysisDiagnosticPair] = [] 321 322 def add_common(self, issue: AnalysisDiagnostic): 323 self.present_in_both.append(issue) 324 325 def add_removed(self, issue: AnalysisDiagnostic): 326 self.present_only_in_old.append(issue) 327 328 def add_added(self, issue: AnalysisDiagnostic): 329 self.present_only_in_new.append(issue) 330 331 def add_changed(self, old_issue: AnalysisDiagnostic, 332 new_issue: AnalysisDiagnostic): 333 self.changed_between_new_and_old.append((old_issue, new_issue)) 334 335 336GroupedDiagnostics = DefaultDict[str, List[AnalysisDiagnostic]] 337 338 339def get_grouped_diagnostics(diagnostics: List[AnalysisDiagnostic] 340 ) -> GroupedDiagnostics: 341 result: GroupedDiagnostics = defaultdict(list) 342 for diagnostic in diagnostics: 343 result[diagnostic.get_location()].append(diagnostic) 344 return result 345 346 347def compare_results(results_old: AnalysisRun, results_new: AnalysisRun, 348 histogram: Optional[HistogramType] = None 349 ) -> ComparisonResult: 350 """ 351 compare_results - Generate a relation from diagnostics in run A to 352 diagnostics in run B. 353 354 The result is the relation as a list of triples (a, b) where 355 each element {a,b} is None or a matching element from the respective run 356 """ 357 358 res = ComparisonResult() 359 360 # Map size_before -> size_after 361 path_difference_data: List[float] = [] 362 363 diags_old = get_grouped_diagnostics(results_old.diagnostics) 364 diags_new = get_grouped_diagnostics(results_new.diagnostics) 365 366 locations_old = set(diags_old.keys()) 367 locations_new = set(diags_new.keys()) 368 369 common_locations = locations_old & locations_new 370 371 for location in common_locations: 372 old = diags_old[location] 373 new = diags_new[location] 374 375 # Quadratic algorithms in this part are fine because 'old' and 'new' 376 # are most commonly of size 1. 377 for a in copy(old): 378 for b in copy(new): 379 if a.get_issue_identifier() == b.get_issue_identifier(): 380 a_path_len = a.get_path_length() 381 b_path_len = b.get_path_length() 382 383 if a_path_len != b_path_len: 384 385 if histogram == HistogramType.RELATIVE: 386 path_difference_data.append( 387 float(a_path_len) / b_path_len) 388 389 elif histogram == HistogramType.LOG_RELATIVE: 390 path_difference_data.append( 391 log(float(a_path_len) / b_path_len)) 392 393 elif histogram == HistogramType.ABSOLUTE: 394 path_difference_data.append( 395 a_path_len - b_path_len) 396 397 res.add_common(a) 398 old.remove(a) 399 new.remove(b) 400 401 for a in copy(old): 402 for b in copy(new): 403 if a.is_similar_to(b): 404 res.add_changed(a, b) 405 old.remove(a) 406 new.remove(b) 407 408 # Whatever is left in 'old' doesn't have a corresponding diagnostic 409 # in 'new', so we need to mark it as 'removed'. 410 for a in old: 411 res.add_removed(a) 412 413 # Whatever is left in 'new' doesn't have a corresponding diagnostic 414 # in 'old', so we need to mark it as 'added'. 415 for b in new: 416 res.add_added(b) 417 418 only_old_locations = locations_old - common_locations 419 for location in only_old_locations: 420 for a in diags_old[location]: 421 # These locations have been found only in the old build, so we 422 # need to mark all of therm as 'removed' 423 res.add_removed(a) 424 425 only_new_locations = locations_new - common_locations 426 for location in only_new_locations: 427 for b in diags_new[location]: 428 # These locations have been found only in the new build, so we 429 # need to mark all of therm as 'added' 430 res.add_added(b) 431 432 # FIXME: Add fuzzy matching. One simple and possible effective idea would 433 # be to bin the diagnostics, print them in a normalized form (based solely 434 # on the structure of the diagnostic), compute the diff, then use that as 435 # the basis for matching. This has the nice property that we don't depend 436 # in any way on the diagnostic format. 437 438 if histogram: 439 from matplotlib import pyplot 440 pyplot.hist(path_difference_data, bins=100) 441 pyplot.show() 442 443 return res 444 445 446def compute_percentile(values: Sequence[T], percentile: float) -> T: 447 """ 448 Return computed percentile. 449 """ 450 return sorted(values)[int(round(percentile * len(values) + 0.5)) - 1] 451 452 453def derive_stats(results: AnalysisRun) -> Stats: 454 # Assume all keys are the same in each statistics bucket. 455 combined_data = defaultdict(list) 456 457 # Collect data on paths length. 458 for report in results.reports: 459 for diagnostic in report.diagnostics: 460 combined_data['PathsLength'].append(diagnostic.get_path_length()) 461 462 for stat in results.raw_stats: 463 for key, value in stat.items(): 464 combined_data[str(key)].append(value) 465 466 combined_stats: Stats = {} 467 468 for key, values in combined_data.items(): 469 combined_stats[key] = { 470 "max": max(values), 471 "min": min(values), 472 "mean": sum(values) / len(values), 473 "90th %tile": compute_percentile(values, 0.9), 474 "95th %tile": compute_percentile(values, 0.95), 475 "median": sorted(values)[len(values) // 2], 476 "total": sum(values) 477 } 478 479 return combined_stats 480 481 482# TODO: compare_results decouples comparison from the output, we should 483# do it here as well 484def compare_stats(results_old: AnalysisRun, results_new: AnalysisRun, 485 out: TextIO = sys.stdout): 486 stats_old = derive_stats(results_old) 487 stats_new = derive_stats(results_new) 488 489 old_keys = set(stats_old.keys()) 490 new_keys = set(stats_new.keys()) 491 keys = sorted(old_keys & new_keys) 492 493 for key in keys: 494 out.write(f"{key}\n") 495 496 nested_keys = sorted(set(stats_old[key]) & set(stats_new[key])) 497 498 for nested_key in nested_keys: 499 val_old = float(stats_old[key][nested_key]) 500 val_new = float(stats_new[key][nested_key]) 501 502 report = f"{val_old:.3f} -> {val_new:.3f}" 503 504 # Only apply highlighting when writing to TTY and it's not Windows 505 if out.isatty() and os.name != 'nt': 506 if val_new != 0: 507 ratio = (val_new - val_old) / val_new 508 if ratio < -0.2: 509 report = Colors.GREEN + report + Colors.CLEAR 510 elif ratio > 0.2: 511 report = Colors.RED + report + Colors.CLEAR 512 513 out.write(f"\t {nested_key} {report}\n") 514 515 removed_keys = old_keys - new_keys 516 if removed_keys: 517 out.write(f"REMOVED statistics: {removed_keys}\n") 518 519 added_keys = new_keys - old_keys 520 if added_keys: 521 out.write(f"ADDED statistics: {added_keys}\n") 522 523 out.write("\n") 524 525 526def dump_scan_build_results_diff(dir_old: ResultsDirectory, 527 dir_new: ResultsDirectory, 528 delete_empty: bool = True, 529 out: TextIO = sys.stdout, 530 show_stats: bool = False, 531 stats_only: bool = False, 532 histogram: Optional[HistogramType] = None, 533 verbose_log: Optional[str] = None): 534 """ 535 Compare directories with analysis results and dump results. 536 537 :param delete_empty: delete empty plist files 538 :param out: buffer to dump comparison results to. 539 :param show_stats: compare execution stats as well. 540 :param stats_only: compare ONLY execution stats. 541 :param histogram: optional histogram type to plot path differences. 542 :param verbose_log: optional path to an additional log file. 543 """ 544 results_old = load_results(dir_old, delete_empty, verbose_log) 545 results_new = load_results(dir_new, delete_empty, verbose_log) 546 547 if show_stats or stats_only: 548 compare_stats(results_old, results_new) 549 if stats_only: 550 return 551 552 # Open the verbose log, if given. 553 if verbose_log: 554 aux_log: Optional[TextIO] = open(verbose_log, "w") 555 else: 556 aux_log = None 557 558 diff = compare_results(results_old, results_new, histogram) 559 found_diffs = 0 560 total_added = 0 561 total_removed = 0 562 total_modified = 0 563 564 for new in diff.present_only_in_new: 565 out.write(f"ADDED: {new.get_readable_name()}\n\n") 566 found_diffs += 1 567 total_added += 1 568 if aux_log: 569 aux_log.write(f"('ADDED', {new.get_readable_name()}, " 570 f"{new.get_html_report()})\n") 571 572 for old in diff.present_only_in_old: 573 out.write(f"REMOVED: {old.get_readable_name()}\n\n") 574 found_diffs += 1 575 total_removed += 1 576 if aux_log: 577 aux_log.write(f"('REMOVED', {old.get_readable_name()}, " 578 f"{old.get_html_report()})\n") 579 580 for old, new in diff.changed_between_new_and_old: 581 out.write(f"MODIFIED: {old.get_readable_name()}\n") 582 found_diffs += 1 583 total_modified += 1 584 diffs = old.get_diffs(new) 585 str_diffs = [f" '{key}' changed: " 586 f"'{old_value}' -> '{new_value}'" 587 for key, (old_value, new_value) in diffs.items()] 588 out.write(",\n".join(str_diffs) + "\n\n") 589 if aux_log: 590 aux_log.write(f"('MODIFIED', {old.get_readable_name()}, " 591 f"{old.get_html_report()})\n") 592 593 total_reports = len(results_new.diagnostics) 594 out.write(f"TOTAL REPORTS: {total_reports}\n") 595 out.write(f"TOTAL ADDED: {total_added}\n") 596 out.write(f"TOTAL REMOVED: {total_removed}\n") 597 out.write(f"TOTAL MODIFIED: {total_modified}\n") 598 599 if aux_log: 600 aux_log.write(f"('TOTAL NEW REPORTS', {total_reports})\n") 601 aux_log.write(f"('TOTAL DIFFERENCES', {found_diffs})\n") 602 aux_log.close() 603 604 # TODO: change to NamedTuple 605 return found_diffs, len(results_old.diagnostics), \ 606 len(results_new.diagnostics) 607 608 609if __name__ == "__main__": 610 print("CmpRuns.py should not be used on its own.") 611 print("Please use 'SATest.py compare' instead") 612 sys.exit(1) 613