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