440 lines · python
1#!/usr/bin/env python32# -*- coding: utf-8 -*-3# ===----------------------------------------------------------------------===##4#5# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.6# See https://llvm.org/LICENSE.txt for license information.7# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception8#9# ===----------------------------------------------------------------------===##10"""Checks for reverts of commits across a given git commit.11 12To clarify the meaning of 'across' with an example, if we had the following13commit history (where `a -> b` notes that `b` is a direct child of `a`):14 15123abc -> 223abc -> 323abc -> 423abc -> 523abc16 17And where 423abc is a revert of 223abc, this revert is considered to be 'across'18323abc. More generally, a revert A of a parent commit B is considered to be19'across' a commit C if C is a parent of A and B is a parent of C.20 21Please note that revert detection in general is really difficult, since merge22conflicts/etc always introduce _some_ amount of fuzziness. This script just23uses a bundle of heuristics, and is bound to ignore / incorrectly flag some24reverts. The hope is that it'll easily catch the vast majority (>90%) of them,25though.26 27This is designed to be used in one of two ways: an import in Python, or run28directly from a shell. If you want to import this, the `find_reverts`29function is the thing to look at. If you'd rather use this from a shell, have a30usage example:31 32```33./revert_checker.py c47f97169 origin/main origin/release/12.x34```35 36This checks for all reverts from the tip of origin/main to c47f97169, which are37across the latter. It then does the same for origin/release/12.x to c47f97169.38Duplicate reverts discovered when walking both roots (origin/main and39origin/release/12.x) are deduplicated in output.40"""41 42import argparse43import collections44import itertools45import logging46import re47import subprocess48import sys49from typing import Dict, Generator, Iterable, List, NamedTuple, Optional, Tuple50 51assert sys.version_info >= (3, 6), "Only Python 3.6+ is supported."52 53# People are creative with their reverts, and heuristics are a bit difficult.54# At a glance, most reverts have "This reverts commit ${full_sha}". Many others55# have `Reverts llvm/llvm-project#${PR_NUMBER}`.56#57# By their powers combined, we should be able to automatically catch something58# like 80% of reverts with reasonable confidence. At some point, human59# intervention will always be required (e.g., I saw60# ```61# This reverts commit ${commit_sha_1} and62# also ${commit_sha_2_shorthand}63# ```64# during my sample)65 66_CommitMessageReverts = NamedTuple(67 "_CommitMessageReverts",68 [69 ("potential_shas", List[str]),70 ("potential_pr_numbers", List[int]),71 ],72)73 74 75def _try_parse_reverts_from_commit_message(76 commit_message: str,77) -> _CommitMessageReverts:78 """Tries to parse revert SHAs and LLVM PR numbers form the commit message.79 80 Returns:81 A namedtuple containing:82 - A list of potentially reverted SHAs83 - A list of potentially reverted LLVM PR numbers84 """85 if not commit_message:86 return _CommitMessageReverts([], [])87 88 sha_reverts = re.findall(89 r"This reverts commit ([a-f0-9]{40})\b",90 commit_message,91 )92 93 first_line = commit_message.splitlines()[0]94 initial_revert = re.match(r'Revert ([a-f0-9]{6,}) "', first_line)95 if initial_revert:96 sha_reverts.append(initial_revert.group(1))97 98 pr_numbers = [99 int(x)100 for x in re.findall(101 r"Reverts llvm/llvm-project#(\d+)",102 commit_message,103 )104 ]105 106 return _CommitMessageReverts(107 potential_shas=sha_reverts,108 potential_pr_numbers=pr_numbers,109 )110 111 112def _stream_stdout(113 command: List[str], cwd: Optional[str] = None114) -> Generator[str, None, None]:115 with subprocess.Popen(116 command,117 cwd=cwd,118 stdout=subprocess.PIPE,119 encoding="utf-8",120 errors="replace",121 ) as p:122 assert p.stdout is not None # for mypy's happiness.123 yield from p.stdout124 125 126def _resolve_sha(git_dir: str, sha: str) -> str:127 if len(sha) == 40:128 return sha129 130 return subprocess.check_output(131 ["git", "-C", git_dir, "rev-parse", sha],132 encoding="utf-8",133 stderr=subprocess.DEVNULL,134 ).strip()135 136 137_LogEntry = NamedTuple(138 "_LogEntry",139 [140 ("sha", str),141 ("commit_message", str),142 ],143)144 145 146def _log_stream(git_dir: str, root_sha: str, end_at_sha: str) -> Iterable[_LogEntry]:147 sep = 50 * "<>"148 log_command = [149 "git",150 "-C",151 git_dir,152 "log",153 "^" + end_at_sha,154 root_sha,155 "--format=" + sep + "%n%H%n%B%n",156 ]157 158 stdout_stream = iter(_stream_stdout(log_command))159 160 # Find the next separator line. If there's nothing to log, it may not exist.161 # It might not be the first line if git feels complainy.162 found_commit_header = False163 for line in stdout_stream:164 if line.rstrip() == sep:165 found_commit_header = True166 break167 168 while found_commit_header:169 sha = next(stdout_stream, None)170 assert sha is not None, "git died?"171 sha = sha.rstrip()172 173 commit_message = []174 175 found_commit_header = False176 for line in stdout_stream:177 line = line.rstrip()178 if line.rstrip() == sep:179 found_commit_header = True180 break181 commit_message.append(line)182 183 yield _LogEntry(sha, "\n".join(commit_message).rstrip())184 185 186def _shas_between(git_dir: str, base_ref: str, head_ref: str) -> Iterable[str]:187 rev_list = [188 "git",189 "-C",190 git_dir,191 "rev-list",192 "--first-parent",193 f"{base_ref}..{head_ref}",194 ]195 return (x.strip() for x in _stream_stdout(rev_list))196 197 198def _rev_parse(git_dir: str, ref: str) -> str:199 return subprocess.check_output(200 ["git", "-C", git_dir, "rev-parse", ref],201 encoding="utf-8",202 ).strip()203 204 205Revert = NamedTuple(206 "Revert",207 [208 ("sha", str),209 ("reverted_sha", str),210 ],211)212 213 214def _find_common_parent_commit(git_dir: str, ref_a: str, ref_b: str) -> str:215 """Finds the closest common parent commit between `ref_a` and `ref_b`.216 217 Returns:218 A SHA. Note that `ref_a` will be returned if `ref_a` is a parent of219 `ref_b`, and vice-versa.220 """221 return subprocess.check_output(222 ["git", "-C", git_dir, "merge-base", ref_a, ref_b],223 encoding="utf-8",224 ).strip()225 226 227def _load_pr_commit_mappings(228 git_dir: str, root: str, min_ref: str229) -> Dict[int, List[str]]:230 git_log = ["git", "log", "--format=%H %s", f"{min_ref}..{root}"]231 results = collections.defaultdict(list)232 pr_regex = re.compile(r"\s\(#(\d+)\)$")233 for line in _stream_stdout(git_log, cwd=git_dir):234 m = pr_regex.search(line)235 if not m:236 continue237 238 pr_number = int(m.group(1))239 sha = line.split(None, 1)[0]240 # N.B., these are kept in log (read: reverse chronological) order,241 # which is what's expected by `find_reverts`.242 results[pr_number].append(sha)243 return results244 245 246# N.B., max_pr_lookback's default of 20K commits is arbitrary, but should be247# enough for the 99% case of reverts: rarely should someone land a cleanish248# revert of a >6 month old change...249def find_reverts(250 git_dir: str,251 across_ref: str,252 root: str,253 max_pr_lookback: int = 20000,254 stop_at_sha: Optional[str] = None,255) -> List[Revert]:256 """Finds reverts across `across_ref` in `git_dir`, starting from `root`.257 258 These reverts are returned in order of oldest reverts first.259 260 Args:261 git_dir: git directory to find reverts in.262 across_ref: the ref to find reverts across.263 root: the 'main' ref to look for reverts on.264 max_pr_lookback: this function uses heuristics to map PR numbers to265 SHAs. These heuristics require that commit history from `root` to266 `some_parent_of_root` is loaded in memory. `max_pr_lookback` is how267 many commits behind `across_ref` should be loaded in memory.268 stop_at_sha: If non-None and `stop_at_sha` is encountered while walking269 to `across_ref` from `root`, stop checking for reverts. This allows for270 faster incremental checking between `find_reverts` calls.271 """272 across_sha = _rev_parse(git_dir, across_ref)273 root_sha = _rev_parse(git_dir, root)274 275 common_ancestor = _find_common_parent_commit(git_dir, across_sha, root_sha)276 if common_ancestor != across_sha:277 raise ValueError(278 f"{across_sha} isn't an ancestor of {root_sha} "279 "(common ancestor: {common_ancestor})"280 )281 282 intermediate_commits = set(_shas_between(git_dir, across_sha, root_sha))283 assert across_sha not in intermediate_commits284 285 logging.debug(286 "%d commits appear between %s and %s",287 len(intermediate_commits),288 across_sha,289 root_sha,290 )291 292 commit_log_stream: Iterable[_LogEntry] = _log_stream(git_dir, root_sha, across_sha)293 if stop_at_sha:294 commit_log_stream = itertools.takewhile(295 lambda x: x.sha != stop_at_sha, commit_log_stream296 )297 298 all_reverts = []299 # Lazily load PR <-> commit mappings, since it can be expensive.300 pr_commit_mappings = None301 for sha, commit_message in commit_log_stream:302 reverts, pr_reverts = _try_parse_reverts_from_commit_message(303 commit_message,304 )305 if pr_reverts:306 if pr_commit_mappings is None:307 logging.info(308 "Loading PR <-> commit mappings. This may take a moment..."309 )310 pr_commit_mappings = _load_pr_commit_mappings(311 git_dir, root_sha, f"{across_sha}~{max_pr_lookback}"312 )313 logging.info(314 "Loaded %d PR <-> commit mappings", len(pr_commit_mappings)315 )316 317 for reverted_pr_number in pr_reverts:318 reverted_shas = pr_commit_mappings.get(reverted_pr_number)319 if not reverted_shas:320 logging.warning(321 "No SHAs for reverted PR %d (commit %s)",322 reverted_pr_number,323 sha,324 )325 continue326 logging.debug(327 "Inferred SHAs %s for reverted PR %d (commit %s)",328 reverted_shas,329 reverted_pr_number,330 sha,331 )332 reverts.extend(reverted_shas)333 334 if not reverts:335 continue336 337 resolved_reverts = sorted(set(_resolve_sha(git_dir, x) for x in reverts))338 for reverted_sha in resolved_reverts:339 if reverted_sha in intermediate_commits:340 logging.debug(341 "Commit %s reverts %s, which happened after %s",342 sha,343 reverted_sha,344 across_sha,345 )346 continue347 348 try:349 object_type = subprocess.check_output(350 ["git", "-C", git_dir, "cat-file", "-t", reverted_sha],351 encoding="utf-8",352 stderr=subprocess.DEVNULL,353 ).strip()354 except subprocess.CalledProcessError:355 logging.warning(356 "Failed to resolve reverted object %s (claimed to be reverted "357 "by sha %s)",358 reverted_sha,359 sha,360 )361 continue362 363 if object_type != "commit":364 logging.error(365 "%s claims to revert the %s %s, which isn't a commit",366 sha,367 object_type,368 reverted_sha,369 )370 continue371 372 # Rarely, reverts will cite SHAs on other branches (e.g., revert373 # commit says it reverts a commit with SHA ${X}, but ${X} is not a374 # parent of the revert). This can happen if e.g., the revert has375 # been mirrored to another branch. Treat them the same as376 # reverts of non-commits.377 if _find_common_parent_commit(git_dir, sha, reverted_sha) != reverted_sha:378 logging.error(379 "%s claims to revert %s, which is a commit that is not "380 "a parent of the revert",381 sha,382 reverted_sha,383 )384 continue385 386 all_reverts.append(Revert(sha, reverted_sha))387 388 389 # Since `all_reverts` contains reverts in log order (e.g., newer comes before390 # older), we need to reverse this to keep with our guarantee of older =391 # earlier in the result.392 all_reverts.reverse()393 return all_reverts394 395 396def _main() -> None:397 parser = argparse.ArgumentParser(398 description=__doc__, formatter_class=argparse.RawDescriptionHelpFormatter399 )400 parser.add_argument("base_ref", help="Git ref or sha to check for reverts around.")401 parser.add_argument("-C", "--git_dir", default=".", help="Git directory to use.")402 parser.add_argument("root", nargs="+", help="Root(s) to search for commits from.")403 parser.add_argument("--debug", action="store_true")404 parser.add_argument(405 "-u",406 "--review_url",407 action="store_true",408 help="Format SHAs as llvm review URLs",409 )410 opts = parser.parse_args()411 412 logging.basicConfig(413 format="%(asctime)s: %(levelname)s: %(filename)s:%(lineno)d: %(message)s",414 level=logging.DEBUG if opts.debug else logging.INFO,415 )416 417 # `root`s can have related history, so we want to filter duplicate commits418 # out. The overwhelmingly common case is also to have one root, and it's way419 # easier to reason about output that comes in an order that's meaningful to420 # git.421 seen_reverts = set()422 all_reverts = []423 for root in opts.root:424 for revert in find_reverts(opts.git_dir, opts.base_ref, root):425 if revert not in seen_reverts:426 seen_reverts.add(revert)427 all_reverts.append(revert)428 429 sha_prefix = (430 "https://github.com/llvm/llvm-project/commit/" if opts.review_url else ""431 )432 for revert in all_reverts:433 sha_fmt = f"{sha_prefix}{revert.sha}"434 reverted_sha_fmt = f"{sha_prefix}{revert.reverted_sha}"435 print(f"{sha_fmt} claims to revert {reverted_sha_fmt}")436 437 438if __name__ == "__main__":439 _main()440