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())
 132
 133
 134 # Args are stored in a global for easy access.
 135 args = Args.parse()
 136
 137 # A single instance of this class is constructed, from `args` and the `events:`
 138 # line in the cgout file.
 139 class Events:
 140     # The event names.
 141     events: list[str]
 142
 143     def __init__(self, text: str) -> None:
 144         self.events = text.split()
 145         self.num_events = len(self.events)
 146
 147     # Raises a `ValueError` exception on syntax error.
 148     def mk_cc(self, str_counts: list[str]) -> Cc:
 149         # This is slightly faster than a list comprehension.
 150         counts = list(map(int, str_counts))
 151
 152         if len(counts) == self.num_events:
 153             pass
 154         elif len(counts) < self.num_events:
 155             # Add zeroes at the end for any missing numbers.
 156             counts.extend([0] * (self.num_events - len(counts)))
 157         else:
 158             raise ValueError
 159
 160         return counts
 161
 162     def mk_empty_cc(self) -> Cc:
 163         # This is much faster than a list comprehension.
 164         return [0] * self.num_events
 165
 166
 167 # A "cost centre", which is a dumb container for counts. Always the same length
 168 # as `Events.events`, but it doesn't even know event names. `Events.mk_cc` and
 169 # `Events.mk_empty_cc` are used for construction.
 170 #
 171 # This used to be a class with a single field `counts: list[int]`, but this
 172 # type is very hot and just using a type alias is much faster.
 173 Cc = list[int]
 174
 175 # Add the counts in `a_cc` to `b_cc`.
 176 def add_cc_to_cc(a_cc: Cc, b_cc: Cc) -> None:
 177     for i, a_count in enumerate(a_cc):
 178         b_cc[i] += a_count
 179
 180
 181 # Subtract the counts in `a_cc` from `b_cc`.
 182 def sub_cc_from_cc(a_cc: Cc, b_cc: Cc) -> None:
 183     for i, a_count in enumerate(a_cc):
 184         b_cc[i] -= a_count
 185
 186
 187 # A paired filename and function name.
 188 Flfn = NewType("Flfn", tuple[str, str])
 189
 190 # Per-function CCs.
 191 DictFlfnCc = DefaultDict[Flfn, Cc]
 192
 193
 194 def die(msg: str) -> NoReturn:
 195     print("cg_diff: error:", msg, file=sys.stderr)
 196     sys.exit(1)
 197
 198
 199 def read_cgout_file(cgout_filename: str) -> tuple[str, Events, DictFlfnCc, Cc]:
 200     # The file format is described in Cachegrind's manual.
 201     try:
 202         cgout_file = open(cgout_filename, "r", encoding="utf-8")
 203     except OSError as err:
 204         die(f"{err}")
 205
 206     with cgout_file:
 207         cgout_line_num = 0
 208
 209         def parse_die(msg: str) -> NoReturn:
 210             die(f"{cgout_file.name}:{cgout_line_num}: {msg}")
 211
 212         def readline() -> str:
 213             nonlocal cgout_line_num
 214             cgout_line_num += 1
 215             return cgout_file.readline()
 216
 217         # Read "desc:" lines.
 218         while line := readline():
 219             if m := re.match(r"desc:\s+(.*)", line):
 220                 # The "desc:" lines are unused.
 221                 pass
 222             else:
 223                 break
 224
 225         # Read "cmd:" line. (`line` is already set from the "desc:" loop.)
 226         if m := re.match(r"cmd:\s+(.*)", line):
 227             cmd = m.group(1)
 228         else:
 229             parse_die("missing a `command:` line")
 230
 231         # Read "events:" line.
 232         line = readline()
 233         if m := re.match(r"events:\s+(.*)", line):
 234             events = Events(m.group(1))
 235         else:
 236             parse_die("missing an `events:` line")
 237
 238         fl = ""
 239         flfn = Flfn(("", ""))
 240
 241         # Different places where we accumulate CC data.
 242         dict_flfn_cc: DictFlfnCc = defaultdict(events.mk_empty_cc)
 243         summary_cc = None
 244
 245         # Line matching is done in order of pattern frequency, for speed.
 246         while line := readline():
 247             if line[0].isdigit():
 248                 split_line = line.split()
 249                 try:
 250                     # The line_num isn't used.
 251                     cc = events.mk_cc(split_line[1:])
 252                 except ValueError:
 253                     parse_die("malformed or too many event counts")
 254
 255                 # Record this CC at the function level.
 256                 add_cc_to_cc(cc, dict_flfn_cc[flfn])
 257
 258             elif line.startswith("fn="):
 259                 flfn = Flfn((fl, args.mod_funcname(line[3:-1])))
 260
 261             elif line.startswith("fl="):
 262                 # A longstanding bug: the use of `--mod-filename` makes it
 263                 # likely that some files won't be found when annotating. This
 264                 # doesn't matter much, because we use line number 0 for all
 265                 # diffs anyway. It just means we get "This file was unreadable"
 266                 # for modified filenames rather than a single "<unknown (line
 267                 # 0)>" CC.
 268                 fl = args.mod_filename(line[3:-1])
 269                 # A `fn=` line should follow, overwriting the "???".
 270                 flfn = Flfn((fl, "???"))
 271
 272             elif m := re.match(r"summary:\s+(.*)", line):
 273                 try:
 274                     summary_cc = events.mk_cc(m.group(1).split())
 275                 except ValueError:
 276                     parse_die("malformed or too many event counts")
 277
 278             elif line == "\n" or line.startswith("#"):
 279                 # Skip empty lines and comment lines.
 280                 pass
 281
 282             else:
 283                 parse_die(f"malformed line: {line[:-1]}")
 284
 285     # Check if summary line was present.
 286     if not summary_cc:
 287         parse_die("missing `summary:` line, aborting")
 288
 289     # Check summary is correct.
 290     total_cc = events.mk_empty_cc()
 291     for flfn_cc in dict_flfn_cc.values():
 292         add_cc_to_cc(flfn_cc, total_cc)
 293     if summary_cc != total_cc:
 294         msg = (
 295             "`summary:` line doesn't match computed total\n"
 296             f"- summary: {summary_cc}\n"
 297             f"- total:   {total_cc}"
 298         )
 299         parse_die(msg)
 300
 301     return (cmd, events, dict_flfn_cc, summary_cc)
 302
 303
 304 def main() -> None:
 305     filename1 = args.cgout_filename1[0]
 306     filename2 = args.cgout_filename2[0]
 307
 308     (cmd1, events1, dict_flfn_cc1, summary_cc1) = read_cgout_file(filename1)
 309     (cmd2, events2, dict_flfn_cc2, summary_cc2) = read_cgout_file(filename2)
 310
 311     if events1.events != events2.events:
 312         die("events in data files don't match")
 313
 314     # Subtract file 1's CCs from file 2's CCs, at the Flfn level.
 315     for flfn, flfn_cc1 in dict_flfn_cc1.items():
 316         flfn_cc2 = dict_flfn_cc2[flfn]
 317         sub_cc_from_cc(flfn_cc1, flfn_cc2)
 318     sub_cc_from_cc(summary_cc1, summary_cc2)
 319
 320     print(f"desc: Files compared:   {filename1}; {filename2}")
 321     print(f"cmd: {cmd1}; {cmd2}")
 322     print("events:", *events1.events, sep=" ")
 323
 324     # Sort so the output is deterministic.
 325     def key(flfn_and_cc: tuple[Flfn, Cc]) -> Flfn:
 326         return flfn_and_cc[0]
 327
 328     for flfn, flfn_cc2 in sorted(dict_flfn_cc2.items(), key=key):
 329         # Use `0` for the line number because we don't try to give line-level
 330         # CCs, due to the possibility of code changes causing line numbers to
 331         # move around.
 332         print(f"fl={flfn[0]}")
 333         print(f"fn={flfn[1]}")
 334         print("0", *flfn_cc2, sep=" ")
 335
 336     print("summary:", *summary_cc2, sep=" ")
 337
 338
 339 if __name__ == "__main__":
 340     main()