cachegrind/cg_diff.in

   1 #! /usr/bin/env python3
   2 # pyright: strict
   3
   4 # --------------------------------------------------------------------
   5 # --- Cachegrind's differencer.                         cg_diff.in ---
   6 # --------------------------------------------------------------------
   7
   8 # This file is part of Cachegrind, a high-precision tracing profiler
   9 # built with Valgrind.
  10 #
  11 # Copyright (C) 2002-2023 Nicholas Nethercote
  12 #    njn@valgrind.org
  13 #
  14 # This program is free software; you can redistribute it and/or
  15 # modify it under the terms of the GNU General Public License as
  16 # published by the Free Software Foundation; either version 2 of the
  17 # License, or (at your option) any later version.
  18 #
  19 # This program is distributed in the hope that it will be useful, but
  20 # WITHOUT ANY WARRANTY; without even the implied warranty of
  21 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  22 # General Public License for more details.
  23 #
  24 # You should have received a copy of the GNU General Public License
  25 # along with this program; if not, see <http://www.gnu.org/licenses/>.
  26 #
  27 # The GNU General Public License is contained in the file COPYING.
  28
  29 # This script diffs Cachegrind output files.
  30 #
  31 # Use `make pydiff` to "build" this script every time it is changed. This runs
  32 # the formatters, type-checkers, and linters on `cg_diff.in` and then generates
  33 # `cg_diff`.
  34 #
  35 # This is a cut-down version of `cg_annotate.in`.
  36
  37 from __future__ import annotations
  38
  39 import re
  40 import sys
  41 from argparse import ArgumentParser, Namespace
  42 from collections import defaultdict
  43 from typing import Callable, DefaultDict, NewType, NoReturn
  44
  45 SearchAndReplace = Callable[[str], str]
  46
  47
  48 # A typed wrapper for parsed args.
  49 class Args(Namespace):
  50     # None of these fields are modified after arg parsing finishes.
  51     mod_filename: SearchAndReplace
  52     mod_funcname: SearchAndReplace
  53     cgout_filename1: str
  54     cgout_filename2: str
  55
  56     @staticmethod
  57     def parse() -> Args:
  58         # We support Perl-style `s/old/new/flags` search-and-replace
  59         # expressions, because that's how this option was implemented in the
  60         # old Perl version of `cg_diff`. This requires conversion from
  61         # `s/old/new/` style to `re.sub`. The conversion isn't a perfect
  62         # emulation of Perl regexps (e.g. Python uses `\1` rather than `$1` for
  63         # using captures in the `new` part), but it should be close enough. The
  64         # only supported flags are `g` (global) and `i` (ignore case).
  65         def search_and_replace(regex: str | None) -> SearchAndReplace:
  66             if regex is None:
  67                 return lambda s: s
  68
  69             # Extract the parts of an `s/old/new/tail` regex. `(?<!\\)/` is an
  70             # example of negative lookbehind. It means "match a forward slash
  71             # unless preceded by a backslash".
  72             m = re.match(r"s/(.*)(?<!\\)/(.*)(?<!\\)/(g|i|gi|ig|)$", regex)
  73             if m is None:
  74                 raise ValueError
  75
  76             # Forward slashes must be escaped in an `s/old/new/` expression,
  77             # but we then must unescape them before using them with `re.sub`.
  78             pat = m.group(1).replace(r"\/", r"/")
  79             repl = m.group(2).replace(r"\/", r"/")
  80             tail = m.group(3)
  81
  82             if "g" in tail:
  83                 count = 0  # unlimited
  84             else:
  85                 count = 1
  86
  87             if "i" in tail:
  88                 flags = re.IGNORECASE
  89             else:
  90                 flags = re.RegexFlag(0)
  91
  92             return lambda s: re.sub(re.compile(pat, flags=flags), repl, s, count=count)
  93
  94         desc = (
  95             "Diff two Cachegrind output files. Deprecated; use "
  96             "`cg_annotate --diff` instead."
  97         )
  98         p = ArgumentParser(description=desc)
  99
 100         p.add_argument("--version", action="version", version="%(prog)s-@VERSION@")
 101
 102         p.add_argument(
 103             "--mod-filename",
 104             type=search_and_replace,
 105             metavar="REGEX",
 106             default=search_and_replace(None),
 107             help="a search-and-replace regex applied to filenames, e.g. "
 108             "`s/prog[0-9]/progN/`",
 109         )
 110         p.add_argument(
 111             "--mod-funcname",
 112             type=search_and_replace,
 113             metavar="REGEX",
 114             default=search_and_replace(None),
 115             help="like --mod-filename, but for function names",
 116         )
 117
 118         p.add_argument(
 119             "cgout_filename1",
 120             nargs=1,
 121             metavar="cachegrind-out-file1",
 122             help="file produced by Cachegrind",
 123         )
 124         p.add_argument(
 125             "cgout_filename2",
 126             nargs=1,
 127             metavar="cachegrind-out-file2",
 128             help="file produced by Cachegrind",
 129         )
 130
 131         return p.parse_args(namespace=Args())  # type: ignore [return-value]
 132
 133
 134 # Args are stored in a global for easy access.
 135 args = Args.parse()
 136
 137
 138 # A single instance of this class is constructed, from `args` and the `events:`
 139 # line in the cgout file.
 140 class Events:
 141     # The event names.
 142     events: list[str]
 143
 144     def __init__(self, text: str) -> None:
 145         self.events = text.split()
 146         self.num_events = len(self.events)
 147
 148     # Raises a `ValueError` exception on syntax error.
 149     def mk_cc(self, str_counts: list[str]) -> Cc:
 150         # This is slightly faster than a list comprehension.
 151         counts = list(map(int, str_counts))
 152
 153         if len(counts) == self.num_events:
 154             pass
 155         elif len(counts) < self.num_events:
 156             # Add zeroes at the end for any missing numbers.
 157             counts.extend([0] * (self.num_events - len(counts)))
 158         else:
 159             raise ValueError
 160
 161         return counts
 162
 163     def mk_empty_cc(self) -> Cc:
 164         # This is much faster than a list comprehension.
 165         return [0] * self.num_events
 166
 167
 168 # A "cost centre", which is a dumb container for counts. Always the same length
 169 # as `Events.events`, but it doesn't even know event names. `Events.mk_cc` and
 170 # `Events.mk_empty_cc` are used for construction.
 171 #
 172 # This used to be a class with a single field `counts: list[int]`, but this
 173 # type is very hot and just using a type alias is much faster.
 174 Cc = list[int]
 175
 176
 177 # Add the counts in `a_cc` to `b_cc`.
 178 def add_cc_to_cc(a_cc: Cc, b_cc: Cc) -> None:
 179     for i, a_count in enumerate(a_cc):
 180         b_cc[i] += a_count
 181
 182
 183 # Subtract the counts in `a_cc` from `b_cc`.
 184 def sub_cc_from_cc(a_cc: Cc, b_cc: Cc) -> None:
 185     for i, a_count in enumerate(a_cc):
 186         b_cc[i] -= a_count
 187
 188
 189 # A paired filename and function name.
 190 Flfn = NewType("Flfn", tuple[str, str])
 191
 192 # Per-function CCs.
 193 DictFlfnCc = DefaultDict[Flfn, Cc]
 194
 195
 196 def die(msg: str) -> NoReturn:
 197     print("cg_diff: error:", msg, file=sys.stderr)
 198     sys.exit(1)
 199
 200
 201 def read_cgout_file(cgout_filename: str) -> tuple[str, Events, DictFlfnCc, Cc]:
 202     # The file format is described in Cachegrind's manual.
 203     try:
 204         cgout_file = open(cgout_filename, "r", encoding="utf-8")
 205     except OSError as err:
 206         die(f"{err}")
 207
 208     with cgout_file:
 209         cgout_line_num = 0
 210
 211         def parse_die(msg: str) -> NoReturn:
 212             die(f"{cgout_file.name}:{cgout_line_num}: {msg}")
 213
 214         def readline() -> str:
 215             nonlocal cgout_line_num
 216             cgout_line_num += 1
 217             return cgout_file.readline()
 218
 219         # Read "desc:" lines.
 220         while line := readline():
 221             if m := re.match(r"desc:\s+(.*)", line):
 222                 # The "desc:" lines are unused.
 223                 pass
 224             else:
 225                 break
 226
 227         # Read "cmd:" line. (`line` is already set from the "desc:" loop.)
 228         if m := re.match(r"cmd:\s+(.*)", line):
 229             cmd = m.group(1)
 230         else:
 231             parse_die("missing a `command:` line")
 232
 233         # Read "events:" line.
 234         line = readline()
 235         if m := re.match(r"events:\s+(.*)", line):
 236             events = Events(m.group(1))
 237         else:
 238             parse_die("missing an `events:` line")
 239
 240         fl = ""
 241         flfn = Flfn(("", ""))
 242
 243         # Different places where we accumulate CC data.
 244         dict_flfn_cc: DictFlfnCc = defaultdict(events.mk_empty_cc)
 245         summary_cc = None
 246
 247         # Line matching is done in order of pattern frequency, for speed.
 248         while line := readline():
 249             if line[0].isdigit():
 250                 split_line = line.split()
 251                 try:
 252                     # The line_num isn't used.
 253                     cc = events.mk_cc(split_line[1:])
 254                 except ValueError:
 255                     parse_die("malformed or too many event counts")
 256
 257                 # Record this CC at the function level.
 258                 add_cc_to_cc(cc, dict_flfn_cc[flfn])
 259
 260             elif line.startswith("fn="):
 261                 flfn = Flfn((fl, args.mod_funcname(line[3:-1])))
 262
 263             elif line.startswith("fl="):
 264                 # A longstanding bug: the use of `--mod-filename` makes it
 265                 # likely that some files won't be found when annotating. This
 266                 # doesn't matter much, because we use line number 0 for all
 267                 # diffs anyway. It just means we get "This file was unreadable"
 268                 # for modified filenames rather than a single "<unknown (line
 269                 # 0)>" CC.
 270                 fl = args.mod_filename(line[3:-1])
 271                 # A `fn=` line should follow, overwriting the "???".
 272                 flfn = Flfn((fl, "???"))
 273
 274             elif m := re.match(r"summary:\s+(.*)", line):
 275                 try:
 276                     summary_cc = events.mk_cc(m.group(1).split())
 277                 except ValueError:
 278                     parse_die("malformed or too many event counts")
 279
 280             elif line == "\n" or line.startswith("#"):
 281                 # Skip empty lines and comment lines.
 282                 pass
 283
 284             else:
 285                 parse_die(f"malformed line: {line[:-1]}")
 286
 287     # Check if summary line was present.
 288     if not summary_cc:
 289         parse_die("missing `summary:` line, aborting")
 290
 291     # Check summary is correct.
 292     total_cc = events.mk_empty_cc()
 293     for flfn_cc in dict_flfn_cc.values():
 294         add_cc_to_cc(flfn_cc, total_cc)
 295     if summary_cc != total_cc:
 296         msg = (
 297             "`summary:` line doesn't match computed total\n"
 298             f"- summary: {summary_cc}\n"
 299             f"- total:   {total_cc}"
 300         )
 301         parse_die(msg)
 302
 303     return (cmd, events, dict_flfn_cc, summary_cc)
 304
 305
 306 def main() -> None:
 307     filename1 = args.cgout_filename1[0]
 308     filename2 = args.cgout_filename2[0]
 309
 310     (cmd1, events1, dict_flfn_cc1, summary_cc1) = read_cgout_file(filename1)
 311     (cmd2, events2, dict_flfn_cc2, summary_cc2) = read_cgout_file(filename2)
 312
 313     if events1.events != events2.events:
 314         die("events in data files don't match")
 315
 316     # Subtract file 1's CCs from file 2's CCs, at the Flfn level.
 317     for flfn, flfn_cc1 in dict_flfn_cc1.items():
 318         flfn_cc2 = dict_flfn_cc2[flfn]
 319         sub_cc_from_cc(flfn_cc1, flfn_cc2)
 320     sub_cc_from_cc(summary_cc1, summary_cc2)
 321
 322     print(f"desc: Files compared:   {filename1}; {filename2}")
 323     print(f"cmd: {cmd1}; {cmd2}")
 324     print("events:", *events1.events, sep=" ")
 325
 326     # Sort so the output is deterministic.
 327     def key(flfn_and_cc: tuple[Flfn, Cc]) -> Flfn:
 328         return flfn_and_cc[0]
 329
 330     for flfn, flfn_cc2 in sorted(dict_flfn_cc2.items(), key=key):
 331         # Use `0` for the line number because we don't try to give line-level
 332         # CCs, due to the possibility of code changes causing line numbers to
 333         # move around.
 334         print(f"fl={flfn[0]}")
 335         print(f"fn={flfn[1]}")
 336         print("0", *flfn_cc2, sep=" ")
 337
 338     print("summary:", *summary_cc2, sep=" ")
 339
 340
 341 if __name__ == "__main__":
 342     main()