scripts/affected_tests.py - external/gitlab.com/libeigen/eigen - Git at Google

 #!/usr/bin/env python3
 # SPDX-FileCopyrightText: The Eigen Authors
 # SPDX-License-Identifier: MPL-2.0

 """Select the tests affected by a set of changed files.

 Eigen is header-only, so a test is affected by a change exactly when its
 translation unit textually includes the changed file.  This script builds the
 include graph over ``Eigen/``, ``unsupported/Eigen/`` and the test trees, then
 maps changed paths to the CMake test targets that reach them.

 The graph follows every ``#include`` regardless of preprocessor guards, so the
 closure is a strict superset of the true compile dependency and no test is
 dropped because a conditional branch was not taken.  Over-approximation is the
 safe direction here: the point is to widen coverage relative to the fixed smoke
 list, not to minimise work.  Changes that invalidate the mapping itself (CMake,
 CI, the BLAS/LAPACK shims) fall back to the full ``buildtests`` target.

 Two output files are written, both consumed by the build and test scripts of each
 platform in the tier -- ``ci/scripts/build.linux.script.sh`` and
 ``ci/scripts/test.linux.script.sh``, and their ``.windows.script.ps1``
 counterparts:

   targets.txt       ``NONE``, a newline-separated target list, or the
                     full-suite list of ``buildtests`` and the targets it does
                     not aggregate
   ctest_regex.txt   ``ALL``, ``NONE``, or a CTest ``-R`` regex

 The selected names are CMake target names, not CTest test names: a split test
 ``foo`` registers ``foo_1``..``foo_N`` as tests but a single ``foo`` target that
 aggregates them, so selecting ``foo`` builds and runs every part.  Targets that
 a given configuration does not register (optional dependencies such as CHOLMOD
 or SYCL) are filtered out by the build scripts, the only place that knows what
 CMake actually configured.

 Two registrations do not fit that shape:

 * Each compile-failure test under ``failtest/`` compiles its own target from
   inside CTest, so those are selected as CTest names and never handed to the
   build job.
 * ``buildtests`` aggregates the ``ei_add_test`` targets only.  A bare
   ``add_executable`` such as ``bug1213`` is attached to nothing, so the
   full-suite mode has to name those targets next to ``buildtests``.

 A registered target need not compile a ``.cpp``, and need not be named by a
 literal: ``ei_add_test`` takes the source extension from
 ``EIGEN_ADD_TEST_FILENAME_EXTENSION``, which the GPU blocks set to ``cu``, and
 the GPU module registers families of tests from ``foreach`` item lists.  Both
 are read out of the CMake source, so a translation unit under a test root with
 no registration the parser can see is an error rather than an assumption.
 Those targets are selected like any other; the build script drops them in
 configurations that did not register them.  ``test/buildsystem/`` is skipped:
 its consumer projects are separate CMake projects configured by their own CI
 job, so an ``add_executable`` there is not a test registration.
 """

 import argparse
 import collections
 import fnmatch
 import os
 import re
 import subprocess
 import sys

 # Directories scanned to build the include graph.
 SCAN_ROOTS = ("Eigen", "unsupported/Eigen", "test", "unsupported/test", "failtest")

 # Directories whose .cpp files are test translation units.
 TEST_ROOTS = ("test", "unsupported/test")

 # Subtrees of TEST_ROOTS that are not part of this build.  test/buildsystem/
 # holds standalone CMake projects that test:linux:buildsystem configures on
 # their own, so their add_executable() calls register targets no configuration
 # here has, and their sources are not test translation units.
 EXCLUDED_TEST_DIRS = ("test/buildsystem",)

 # Compile-failure suite.  ei_add_failtest registers <name>_ok and <name>_ko as
 # CTest tests whose test action is a build of an EXCLUDE_FROM_ALL target.
 FAILTEST_ROOT = "failtest"

 # Extensions a registered test translation unit can have.  ".cu" comes from the
 # GPU registrations; see CMAKE_REGISTRATION_RE.
 TEST_SOURCE_SUFFIXES = (".cpp", ".cu")

 # Share of the test suite above which an explicit selection is replaced by the
 # full ``buildtests`` target.
 DEFAULT_MAX_FRACTION = 0.85

 # Changes matching these patterns cannot affect which tests exist or what they
 # cover, so they select nothing.
 IGNORED_PATTERNS = (
     ".gitattributes",
     ".gitignore",
     ".clang-format",
     ".clang-tidy",
     "*.md",
     "*.dox",
     "AGENTS.md",
     "COPYING*",
     "INSTALL",
     "README*",
     "REUSE.toml",
     ".agents/*",
     ".gitlab/*",
     "LICENSES/*",
     "benchmarks/*",
     # The CI YAML is orchestration -- rules, tags, artifacts, job names -- and
     # cannot change which test includes which header, which is the only mapping
     # this selector maintains.  Ignored rather than merely dropped from
     # FULL_REBUILD_PATTERNS below: these files are not under SCAN_ROOTS, so an
     # un-forced path would instead fall through to "not in the include graph"
     # and force the full suite anyway.
     "ci/*.gitlab-ci.yml",
     "ci/CTest2JUnit.xsl",
     "debug/*",
     "demos/*",
     "doc/*",
     "unsupported/benchmarks/*",
     "unsupported/doc/*",
 )

 # Changes matching these patterns invalidate the include-graph mapping itself
 # (test registration, split counts, the CI drivers, or shim libraries whose
 # tests are not modelled here), so they force the full test suite.  Checked
 # after IGNORED_PATTERNS, so a benchmark's or the docs' own CMakeLists.txt does
 # not drag in the whole suite.
 FULL_REBUILD_PATTERNS = (
     "CMakeLists.txt",
     "*/CMakeLists.txt",
     "*.cmake",
     "*.cmake.in",
     # Keeps forcing: it defines the selector-to-driver contract itself
     # (EIGEN_CI_BUILD_TARGET_FILE, EIGEN_CI_CTEST_REGEX_FILE).
     ".gitlab-ci.yml",
     # ci/ splits: the scripts and the image definitions can change what a build
     # produces or how a test runs.  The *.gitlab-ci.yml files cannot, and are
     # ignored above.
     "ci/scripts/*",
     "ci/docker/*",
     "cmake/*",
     "scripts/*",
     "blas/*",
     "lapack/*",
 )

 INCLUDE_RE = re.compile(r'^[ \t]*#[ \t]*include[ \t]*[<"]([^>"]+)[>"]', re.MULTILINE)
 # One pass over a test CMakeLists.txt, in source order, because what a
 # registration means depends on the state at that point: the source extension
 # comes from EIGEN_ADD_TEST_FILENAME_EXTENSION, which the CUDA and HIP blocks
 # set to "cu" and unset again, so gpu_basic is test/gpu_basic.cu while its
 # neighbours are .cpp; and a name spelled ${var} resolves against the item list
 # of the enclosing foreach(), which is how the GPU module registers its
 # cusolver_* and cudss_* tests.
 CMAKE_REGISTRATION_RE = re.compile(
     r"^[ \t]*(?:"
     r'(?P<scope>set|unset)\([ \t]*EIGEN_ADD_TEST_FILENAME_EXTENSION[ \t]*"?(?P<extension>[A-Za-z_0-9]*)"?'
     r"|(?:ei_add_test|ei_add_gpu_test)\([ \t]*"
     r"(?P<test>[A-Za-z_][A-Za-z_0-9]*|\$\{[A-Za-z_][A-Za-z_0-9]*\})"
     r"|add_executable\([ \t]*(?P<executable>[A-Za-z_][A-Za-z_0-9]*)[ \t\r\n]+(?P<sources>[^)]*)\)"
     r"|foreach\((?P<loop>[^)]*)\)"
     r"|(?P<endloop>endforeach)\("
     r")",
     re.MULTILINE,
 )
 # A bare CMake identifier, used to recognise a foreach loop variable.
 CMAKE_NAME_RE = re.compile(r"[A-Za-z_][A-Za-z_0-9]*\Z")
 CMAKE_FAILTEST_RE = re.compile(
     r'^[ \t]*ei_add_failtest\([ \t]*"?([A-Za-z_][A-Za-z_0-9]*)"?',
     re.MULTILINE,
 )


 def _matches(path, patterns):
     return any(fnmatch.fnmatch(path, p) for p in patterns)


 def _under(path, roots):
     return any(path.startswith(root + "/") for root in roots)


 class IncludeGraph:
     """Textual ``#include`` graph over the scanned source roots."""

     def __init__(self, source_dir):
         self.source_dir = source_dir
         self.files = set()
         self._direct = {}
         self._by_suffix = {}
         self._scan()

     def _scan(self):
         for root in SCAN_ROOTS:
             abs_root = os.path.join(self.source_dir, root)
             if not os.path.isdir(abs_root):
                 continue
             for dirpath, dirnames, filenames in os.walk(abs_root):
                 dirnames[:] = [d for d in dirnames if not d.startswith(".")]
                 for name in filenames:
                     rel = os.path.relpath(os.path.join(dirpath, name), self.source_dir)
                     self.files.add(rel)
         # Index every path suffix so that an include spelled relative to a
         # directory outside the scanned roots still resolves.  Ambiguous
         # suffixes are dropped rather than guessed.
         candidates = {}
         for rel in self.files:
             parts = rel.split("/")
             for i in range(len(parts)):
                 candidates.setdefault("/".join(parts[i:]), []).append(rel)
         self._by_suffix = {suffix: matches[0]
                            for suffix, matches in candidates.items() if len(matches) == 1}

     def read_text(self, rel):
         """Contents of a file in the tree, or ``''`` if it cannot be read."""
         try:
             with open(os.path.join(self.source_dir, rel), "r", errors="ignore") as handle:
                 return handle.read()
         except OSError:
             return ""

     def direct_includes(self, rel):
         """Resolved includes of a single file."""
         cached = self._direct.get(rel)
         if cached is not None:
             return cached
         resolved = set()
         self._direct[rel] = resolved  # placed first: the graph has cycles
         directory = os.path.dirname(rel)
         for spelling in INCLUDE_RE.findall(self.read_text(rel)):
             candidate = os.path.normpath(os.path.join(directory, spelling))
             if candidate in self.files:
                 resolved.add(candidate)
             elif spelling in self.files:
                 resolved.add(spelling)
             elif spelling in self._by_suffix:
                 resolved.add(self._by_suffix[spelling])
         return resolved

     def closure(self, rel):
         """Every file reachable from ``rel`` through includes."""
         seen = set()
         stack = [rel]
         while stack:
             for nxt in self.direct_includes(stack.pop()):
                 if nxt not in seen:
                     seen.add(nxt)
                     stack.append(nxt)
         return seen


 # targets     -- test translation unit -> the CMake target that compiles it
 # standalone  -- targets the ``buildtests`` aggregate does not depend on
 # failtests   -- failtest translation unit -> the CTest names that compile it
 Registrations = collections.namedtuple("Registrations", "targets standalone failtests")


 def _loop_binding(arguments):
     """Names a ``foreach(...)`` binds, or ``None`` when they are not literal."""
     tokens = [token.strip('"') for token in arguments.split()]
     if not tokens or not CMAKE_NAME_RE.match(tokens[0]):
         return None
     variable, items = tokens[0], tokens[1:]
     if items[:2] == ["IN", "ITEMS"]:
         items = items[2:]
     elif items[:1] == ["IN"]:
         # IN LISTS and IN ZIP_LISTS iterate variables, not literal names.
         return None
     return variable, [item for item in items if "$" not in item]


 def _loop_expand(token, loops):
     """Resolve a registration name against the enclosing ``foreach`` bindings."""
     if not token.startswith("$"):
         return [token]
     name = token[2:-1]
     for binding in reversed(loops):
         if binding is not None and binding[0] == name:
             return binding[1]
     return []


 def test_registrations(graph):
     """Map registered translation units to what CI has to build or run."""
     source_targets = {}
     standalone = set()

     def register(source, target):
         previous = source_targets.get(source)
         if previous is not None and previous != target:
             raise ValueError("%s is registered by both %s and %s" % (source, previous, target))
         source_targets[source] = target

     cmake_files = sorted(
         rel
         for rel in graph.files
         if os.path.basename(rel) == "CMakeLists.txt"
         and _under(rel, TEST_ROOTS)
         and not _under(rel, EXCLUDED_TEST_DIRS)
     )
     for cmake_file in cmake_files:
         directory = os.path.dirname(cmake_file)
         extension = "cpp"
         # foreach() bindings in effect, innermost last.  A loop over anything
         # but a literal item list pushes None so endforeach() stays balanced.
         loops = []
         for match in CMAKE_REGISTRATION_RE.finditer(graph.read_text(cmake_file)):
             if match.group("scope"):
                 # unset(), or a set() with no value, restores the default.
                 extension = match.group("extension") if match.group("scope") == "set" else ""
                 extension = extension or "cpp"
                 continue
             if match.group("loop") is not None:
                 loops.append(_loop_binding(match.group("loop")))
                 continue
             if match.group("endloop"):
                 if loops:
                     loops.pop()
                 continue
             if match.group("test"):
                 for target in _loop_expand(match.group("test"), loops):
                     source = os.path.normpath(
                         os.path.join(directory, "%s.%s" % (target, extension)))
                     if source in graph.files:
                         register(source, target)
                 continue
             target = match.group("executable")
             for token in re.findall(r'"[^"]*"|[^\s]+', match.group("sources")):
                 token = token.strip('"')
                 if not token.endswith(TEST_SOURCE_SUFFIXES) or "$" in token:
                     continue
                 source = os.path.normpath(os.path.join(directory, token))
                 if source in graph.files:
                     register(source, target)
                     standalone.add(target)

     failtests = {}
     for name in CMAKE_FAILTEST_RE.findall(graph.read_text(FAILTEST_ROOT + "/CMakeLists.txt")):
         source = "%s/%s.cpp" % (FAILTEST_ROOT, name)
         if source in graph.files:
             failtests[source] = (name + "_ok", name + "_ko")

     return Registrations(source_targets, standalone, failtests)


 def full_suite(graph, reasons):
     """Full-suite selection, naming the targets ``buildtests`` does not build."""
     try:
         standalone = test_registrations(graph).standalone
     except ValueError:
         # A broken registration is reported by the paths that depend on the
         # mapping; the full suite stays available without it.
         standalone = ()
     return Selection("all", reasons=reasons, standalone=standalone)


 def reverse_map(graph, sources):
     """Map each included file to the test sources that reach it."""
     reverse = {}
     for src in sources:
         for dep in graph.closure(src):
             reverse.setdefault(dep, set()).add(src)
     return reverse


 class Selection:
     """Outcome: the full suite, explicit targets, no tests, or an error."""

     def __init__(self, mode, targets=(), reasons=(), ctest_names=(), standalone=()):
         self.mode = mode  # "all", "targets", "none", or "error"
         self.targets = set(targets)
         self.reasons = list(reasons)
         # CTest names with no build target of their own.
         self.ctest_names = set(ctest_names)
         # Targets to name alongside ``buildtests`` in "all" mode.
         self.standalone = set(standalone)

     @property
     def targets_file(self):
         if self.mode == "error":
             raise ValueError("an invalid selection has no target file")
         if self.mode == "all":
             return "".join(name + "\n" for name in ["buildtests"] + sorted(self.standalone))
         if self.mode == "none":
             return "NONE\n"
         return "".join(name + "\n" for name in sorted(self.targets))

     @property
     def regex_file(self):
         if self.mode == "error":
             raise ValueError("an invalid selection has no regex file")
         if self.mode == "all":
             return "ALL\n"
         if self.mode == "none":
             return "NONE\n"
         names = sorted(self.targets) + sorted(self.ctest_names)
         return "^(%s)(_[0-9]+)?$\n" % "|".join(re.escape(name) for name in names)


 def select(graph, changed_files, max_fraction=DEFAULT_MAX_FRACTION):
     """Map changed paths to the tests that must run."""
     paths = []
     for path in changed_files:
         path = path.strip()
         if path and not _matches(path, IGNORED_PATTERNS):
             paths.append(path)
     if not paths:
         return Selection("none", reasons=["no change reaches a test"])
     for path in paths:
         if _matches(path, FULL_REBUILD_PATTERNS):
             return full_suite(graph, ["%s forces the full suite" % path])

     try:
         registered = test_registrations(graph)
     except ValueError as error:
         return Selection("error", reasons=[str(error)])
     sources = sorted(registered.targets)
     reverse = reverse_map(graph, sources)
     failtest_reverse = reverse_map(graph, sorted(registered.failtests))

     selected = set()
     selected_failtests = set()
     reasons = []
     for path in paths:
         reached_by = set(reverse.get(path, ()))
         if path in registered.targets:
             reached_by.add(path)
         failtests = set(failtest_reverse.get(path, ()))
         if path in registered.failtests:
             failtests.add(path)
         if reached_by or failtests:
             selected |= reached_by
             selected_failtests |= failtests
             continue
         if path in graph.files:
             # A source file in the tree that nothing includes: either a new
             # header not yet wired up or an unregistered translation unit.
             roots = TEST_ROOTS + (FAILTEST_ROOT,)
             if (_under(path, roots) and not _under(path, EXCLUDED_TEST_DIRS)
                     and path.endswith(TEST_SOURCE_SUFFIXES)):
                 return Selection("error", reasons=["%s has no CMake test target" % path])
             reasons.append("%s is in the tree but reaches no test" % path)
             continue
         # Deleted, renamed, or outside every scanned root: the graph cannot say
         # what it affected, so do not guess.
         return full_suite(graph, ["%s is not in the include graph" % path])

     if not selected and not selected_failtests:
         return Selection("none", reasons=reasons or ["no change reaches a test"])

     if len(selected) > max_fraction * len(sources):
         reasons.append(
             "%d of %d test sources selected (>%.0f%%)"
             % (len(selected), len(sources), 100 * max_fraction)
         )
         return full_suite(graph, reasons)

     ctest_names = set()
     for source in sorted(selected_failtests):
         ctest_names.update(registered.failtests[source])
     if ctest_names:
         reasons.append("%d compile-failure test(s) build from inside CTest"
                        % len(selected_failtests))
     return Selection("targets", (registered.targets[s] for s in selected), reasons,
                      ctest_names=ctest_names)


 def changed_files_from_git(source_dir, base_sha, head="HEAD"):
     """Paths changed between ``base_sha`` and ``head``."""
     result = subprocess.run(
         ["git", "diff", "--no-renames", "--name-only", "%s...%s" % (base_sha, head)],
         cwd=source_dir,
         capture_output=True,
         text=True,
     )
     if result.returncode != 0:
         raise RuntimeError("git diff failed: %s" % result.stderr.strip())
     return [line for line in result.stdout.splitlines() if line.strip()]


 def parse_args(argv):
     parser = argparse.ArgumentParser(description=__doc__,
                                      formatter_class=argparse.RawDescriptionHelpFormatter)
     default_source = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
     parser.add_argument("--source-dir", default=default_source,
                         help="Eigen source tree (default: the tree containing this script)")
     parser.add_argument("--base-sha",
                         help="compute changed files from 'git diff BASE...HEAD'")
     parser.add_argument("--head", default="HEAD", help="head revision for --base-sha")
     parser.add_argument("--changed-files",
                         help="read newline-separated changed paths from this file ('-' for stdin)")
     parser.add_argument("--output-dir",
                         help="write targets.txt and ctest_regex.txt here")
     parser.add_argument("--max-fraction", type=float, default=DEFAULT_MAX_FRACTION,
                         help="degrade to the full suite above this fraction (default: %(default)s)")
     return parser.parse_args(argv)


 def main(argv=None):
     args = parse_args(argv)

     if args.changed_files:
         if args.changed_files == "-":
             changed = sys.stdin.read().splitlines()
         else:
             with open(args.changed_files) as handle:
                 changed = handle.read().splitlines()
     elif args.base_sha:
         try:
             changed = changed_files_from_git(args.source_dir, args.base_sha, args.head)
         except RuntimeError as error:
             # Without a usable diff there is no basis for narrowing.
             print("%s; selecting the full suite" % error, file=sys.stderr)
             changed = None
     else:
         print("one of --base-sha or --changed-files is required", file=sys.stderr)
         return 2

     graph = IncludeGraph(args.source_dir)
     if changed is None:
         selection = full_suite(graph, ["the merge-base diff is unavailable"])
     else:
         selection = select(graph, changed, args.max_fraction)

     print("mode: %s" % selection.mode, file=sys.stderr)
     for reason in selection.reasons:
         print("  %s" % reason, file=sys.stderr)
     if selection.mode == "error":
         return 1
     if selection.mode == "targets":
         print("  %d targets: %s" % (len(selection.targets),
                                     " ".join(sorted(selection.targets))), file=sys.stderr)
         if selection.ctest_names:
             print("  %d CTest-only: %s" % (len(selection.ctest_names),
                                            " ".join(sorted(selection.ctest_names))),
                   file=sys.stderr)

     if args.output_dir:
         os.makedirs(args.output_dir, exist_ok=True)
         with open(os.path.join(args.output_dir, "targets.txt"), "w") as handle:
             handle.write(selection.targets_file)
         with open(os.path.join(args.output_dir, "ctest_regex.txt"), "w") as handle:
             handle.write(selection.regex_file)
     else:
         sys.stdout.write(selection.targets_file)

     return 0


 if __name__ == "__main__":
     sys.exit(main())
	#!/usr/bin/env python3
	# SPDX-FileCopyrightText: The Eigen Authors
	# SPDX-License-Identifier: MPL-2.0

	"""Select the tests affected by a set of changed files.

	Eigen is header-only, so a test is affected by a change exactly when its
	translation unit textually includes the changed file. This script builds the
	include graph over ``Eigen/``, ``unsupported/Eigen/`` and the test trees, then
	maps changed paths to the CMake test targets that reach them.

	The graph follows every ``#include`` regardless of preprocessor guards, so the
	closure is a strict superset of the true compile dependency and no test is
	dropped because a conditional branch was not taken. Over-approximation is the
	safe direction here: the point is to widen coverage relative to the fixed smoke
	list, not to minimise work. Changes that invalidate the mapping itself (CMake,
	CI, the BLAS/LAPACK shims) fall back to the full ``buildtests`` target.

	Two output files are written, both consumed by the build and test scripts of each
	platform in the tier -- ``ci/scripts/build.linux.script.sh`` and
	``ci/scripts/test.linux.script.sh``, and their ``.windows.script.ps1``
	counterparts:

	targets.txt ``NONE``, a newline-separated target list, or the
	full-suite list of ``buildtests`` and the targets it does
	not aggregate
	ctest_regex.txt ``ALL``, ``NONE``, or a CTest ``-R`` regex

	The selected names are CMake target names, not CTest test names: a split test
	``foo`` registers ``foo_1``..``foo_N`` as tests but a single ``foo`` target that
	aggregates them, so selecting ``foo`` builds and runs every part. Targets that
	a given configuration does not register (optional dependencies such as CHOLMOD
	or SYCL) are filtered out by the build scripts, the only place that knows what
	CMake actually configured.

	Two registrations do not fit that shape:

	* Each compile-failure test under ``failtest/`` compiles its own target from
	inside CTest, so those are selected as CTest names and never handed to the
	build job.
	* ``buildtests`` aggregates the ``ei_add_test`` targets only. A bare
	``add_executable`` such as ``bug1213`` is attached to nothing, so the
	full-suite mode has to name those targets next to ``buildtests``.

	A registered target need not compile a ``.cpp``, and need not be named by a
	literal: ``ei_add_test`` takes the source extension from
	``EIGEN_ADD_TEST_FILENAME_EXTENSION``, which the GPU blocks set to ``cu``, and
	the GPU module registers families of tests from ``foreach`` item lists. Both
	are read out of the CMake source, so a translation unit under a test root with
	no registration the parser can see is an error rather than an assumption.
	Those targets are selected like any other; the build script drops them in
	configurations that did not register them. ``test/buildsystem/`` is skipped:
	its consumer projects are separate CMake projects configured by their own CI
	job, so an ``add_executable`` there is not a test registration.
	"""

	import argparse
	import collections
	import fnmatch
	import os
	import re
	import subprocess
	import sys

	# Directories scanned to build the include graph.
	SCAN_ROOTS = ("Eigen", "unsupported/Eigen", "test", "unsupported/test", "failtest")

	# Directories whose .cpp files are test translation units.
	TEST_ROOTS = ("test", "unsupported/test")

	# Subtrees of TEST_ROOTS that are not part of this build. test/buildsystem/
	# holds standalone CMake projects that test:linux:buildsystem configures on
	# their own, so their add_executable() calls register targets no configuration
	# here has, and their sources are not test translation units.
	EXCLUDED_TEST_DIRS = ("test/buildsystem",)

	# Compile-failure suite. ei_add_failtest registers <name>_ok and <name>_ko as
	# CTest tests whose test action is a build of an EXCLUDE_FROM_ALL target.
	FAILTEST_ROOT = "failtest"

	# Extensions a registered test translation unit can have. ".cu" comes from the
	# GPU registrations; see CMAKE_REGISTRATION_RE.
	TEST_SOURCE_SUFFIXES = (".cpp", ".cu")

	# Share of the test suite above which an explicit selection is replaced by the
	# full ``buildtests`` target.
	DEFAULT_MAX_FRACTION = 0.85

	# Changes matching these patterns cannot affect which tests exist or what they
	# cover, so they select nothing.
	IGNORED_PATTERNS = (
	".gitattributes",
	".gitignore",
	".clang-format",
	".clang-tidy",
	"*.md",
	"*.dox",
	"AGENTS.md",
	"COPYING*",
	"INSTALL",
	"README*",
	"REUSE.toml",
	".agents/*",
	".gitlab/*",
	"LICENSES/*",
	"benchmarks/*",
	# The CI YAML is orchestration -- rules, tags, artifacts, job names -- and
	# cannot change which test includes which header, which is the only mapping
	# this selector maintains. Ignored rather than merely dropped from
	# FULL_REBUILD_PATTERNS below: these files are not under SCAN_ROOTS, so an
	# un-forced path would instead fall through to "not in the include graph"
	# and force the full suite anyway.
	"ci/*.gitlab-ci.yml",
	"ci/CTest2JUnit.xsl",
	"debug/*",
	"demos/*",
	"doc/*",
	"unsupported/benchmarks/*",
	"unsupported/doc/*",
	)

	# Changes matching these patterns invalidate the include-graph mapping itself
	# (test registration, split counts, the CI drivers, or shim libraries whose
	# tests are not modelled here), so they force the full test suite. Checked
	# after IGNORED_PATTERNS, so a benchmark's or the docs' own CMakeLists.txt does
	# not drag in the whole suite.
	FULL_REBUILD_PATTERNS = (
	"CMakeLists.txt",
	"*/CMakeLists.txt",
	"*.cmake",
	"*.cmake.in",
	# Keeps forcing: it defines the selector-to-driver contract itself
	# (EIGEN_CI_BUILD_TARGET_FILE, EIGEN_CI_CTEST_REGEX_FILE).
	".gitlab-ci.yml",
	# ci/ splits: the scripts and the image definitions can change what a build
	# produces or how a test runs. The *.gitlab-ci.yml files cannot, and are
	# ignored above.
	"ci/scripts/*",
	"ci/docker/*",
	"cmake/*",
	"scripts/*",
	"blas/*",
	"lapack/*",
	)

	INCLUDE_RE = re.compile(r'^[ \t]#[ \t]include[ \t]*[<"]([^>"]+)[>"]', re.MULTILINE)
	# One pass over a test CMakeLists.txt, in source order, because what a
	# registration means depends on the state at that point: the source extension
	# comes from EIGEN_ADD_TEST_FILENAME_EXTENSION, which the CUDA and HIP blocks
	# set to "cu" and unset again, so gpu_basic is test/gpu_basic.cu while its
	# neighbours are .cpp; and a name spelled ${var} resolves against the item list
	# of the enclosing foreach(), which is how the GPU module registers its
	# cusolver_* and cudss_* tests.
	CMAKE_REGISTRATION_RE = re.compile(
	r"^[ \t]*(?:"
	r'(?P<scope>set\|unset)\([ \t]EIGEN_ADD_TEST_FILENAME_EXTENSION[ \t]"?(?P<extension>[A-Za-z_0-9]*)"?'
	r"\|(?:ei_add_test\|ei_add_gpu_test)\([ \t]*"
	r"(?P<test>[A-Za-z_][A-Za-z_0-9]\|\$\{[A-Za-z_][A-Za-z_0-9]\})"
	r"\|add_executable\([ \t](?P<executable>[A-Za-z_][A-Za-z_0-9])[ \t\r\n]+(?P<sources>[^)]*)\)"
	r"\|foreach\((?P<loop>[^)]*)\)"
	r"\|(?P<endloop>endforeach)\("
	r")",
	re.MULTILINE,
	)
	# A bare CMake identifier, used to recognise a foreach loop variable.
	CMAKE_NAME_RE = re.compile(r"[A-Za-z_][A-Za-z_0-9]*\Z")
	CMAKE_FAILTEST_RE = re.compile(
	r'^[ \t]ei_add_failtest\([ \t]"?([A-Za-z_][A-Za-z_0-9]*)"?',
	re.MULTILINE,
	)


	def _matches(path, patterns):
	return any(fnmatch.fnmatch(path, p) for p in patterns)


	def _under(path, roots):
	return any(path.startswith(root + "/") for root in roots)


	class IncludeGraph:
	"""Textual ``#include`` graph over the scanned source roots."""

	def __init__(self, source_dir):
	self.source_dir = source_dir
	self.files = set()
	self._direct = {}
	self._by_suffix = {}
	self._scan()

	def _scan(self):
	for root in SCAN_ROOTS:
	abs_root = os.path.join(self.source_dir, root)
	if not os.path.isdir(abs_root):
	continue
	for dirpath, dirnames, filenames in os.walk(abs_root):
	dirnames[:] = [d for d in dirnames if not d.startswith(".")]
	for name in filenames:
	rel = os.path.relpath(os.path.join(dirpath, name), self.source_dir)
	self.files.add(rel)
	# Index every path suffix so that an include spelled relative to a
	# directory outside the scanned roots still resolves. Ambiguous
	# suffixes are dropped rather than guessed.
	candidates = {}
	for rel in self.files:
	parts = rel.split("/")
	for i in range(len(parts)):
	candidates.setdefault("/".join(parts[i:]), []).append(rel)
	self._by_suffix = {suffix: matches[0]
	for suffix, matches in candidates.items() if len(matches) == 1}

	def read_text(self, rel):
	"""Contents of a file in the tree, or ``''`` if it cannot be read."""
	try:
	with open(os.path.join(self.source_dir, rel), "r", errors="ignore") as handle:
	return handle.read()
	except OSError:
	return ""

	def direct_includes(self, rel):
	"""Resolved includes of a single file."""
	cached = self._direct.get(rel)
	if cached is not None:
	return cached
	resolved = set()
	self._direct[rel] = resolved # placed first: the graph has cycles
	directory = os.path.dirname(rel)
	for spelling in INCLUDE_RE.findall(self.read_text(rel)):
	candidate = os.path.normpath(os.path.join(directory, spelling))
	if candidate in self.files:
	resolved.add(candidate)
	elif spelling in self.files:
	resolved.add(spelling)
	elif spelling in self._by_suffix:
	resolved.add(self._by_suffix[spelling])
	return resolved

	def closure(self, rel):
	"""Every file reachable from ``rel`` through includes."""
	seen = set()
	stack = [rel]
	while stack:
	for nxt in self.direct_includes(stack.pop()):
	if nxt not in seen:
	seen.add(nxt)
	stack.append(nxt)
	return seen


	# targets -- test translation unit -> the CMake target that compiles it
	# standalone -- targets the ``buildtests`` aggregate does not depend on
	# failtests -- failtest translation unit -> the CTest names that compile it
	Registrations = collections.namedtuple("Registrations", "targets standalone failtests")


	def _loop_binding(arguments):
	"""Names a ``foreach(...)`` binds, or ``None`` when they are not literal."""
	tokens = [token.strip('"') for token in arguments.split()]
	if not tokens or not CMAKE_NAME_RE.match(tokens[0]):
	return None
	variable, items = tokens[0], tokens[1:]
	if items[:2] == ["IN", "ITEMS"]:
	items = items[2:]
	elif items[:1] == ["IN"]:
	# IN LISTS and IN ZIP_LISTS iterate variables, not literal names.
	return None
	return variable, [item for item in items if "$" not in item]


	def _loop_expand(token, loops):
	"""Resolve a registration name against the enclosing ``foreach`` bindings."""
	if not token.startswith("$"):
	return [token]
	name = token[2:-1]
	for binding in reversed(loops):
	if binding is not None and binding[0] == name:
	return binding[1]
	return []


	def test_registrations(graph):
	"""Map registered translation units to what CI has to build or run."""
	source_targets = {}
	standalone = set()

	def register(source, target):
	previous = source_targets.get(source)
	if previous is not None and previous != target:
	raise ValueError("%s is registered by both %s and %s" % (source, previous, target))
	source_targets[source] = target

	cmake_files = sorted(
	rel
	for rel in graph.files
	if os.path.basename(rel) == "CMakeLists.txt"
	and _under(rel, TEST_ROOTS)
	and not _under(rel, EXCLUDED_TEST_DIRS)
	)
	for cmake_file in cmake_files:
	directory = os.path.dirname(cmake_file)
	extension = "cpp"
	# foreach() bindings in effect, innermost last. A loop over anything
	# but a literal item list pushes None so endforeach() stays balanced.
	loops = []
	for match in CMAKE_REGISTRATION_RE.finditer(graph.read_text(cmake_file)):
	if match.group("scope"):
	# unset(), or a set() with no value, restores the default.
	extension = match.group("extension") if match.group("scope") == "set" else ""
	extension = extension or "cpp"
	continue
	if match.group("loop") is not None:
	loops.append(_loop_binding(match.group("loop")))
	continue
	if match.group("endloop"):
	if loops:
	loops.pop()
	continue
	if match.group("test"):
	for target in _loop_expand(match.group("test"), loops):
	source = os.path.normpath(
	os.path.join(directory, "%s.%s" % (target, extension)))
	if source in graph.files:
	register(source, target)
	continue
	target = match.group("executable")
	for token in re.findall(r'"[^"]*"\|[^\s]+', match.group("sources")):
	token = token.strip('"')
	if not token.endswith(TEST_SOURCE_SUFFIXES) or "$" in token:
	continue
	source = os.path.normpath(os.path.join(directory, token))
	if source in graph.files:
	register(source, target)
	standalone.add(target)

	failtests = {}
	for name in CMAKE_FAILTEST_RE.findall(graph.read_text(FAILTEST_ROOT + "/CMakeLists.txt")):
	source = "%s/%s.cpp" % (FAILTEST_ROOT, name)
	if source in graph.files:
	failtests[source] = (name + "_ok", name + "_ko")

	return Registrations(source_targets, standalone, failtests)


	def full_suite(graph, reasons):
	"""Full-suite selection, naming the targets ``buildtests`` does not build."""
	try:
	standalone = test_registrations(graph).standalone
	except ValueError:
	# A broken registration is reported by the paths that depend on the
	# mapping; the full suite stays available without it.
	standalone = ()
	return Selection("all", reasons=reasons, standalone=standalone)


	def reverse_map(graph, sources):
	"""Map each included file to the test sources that reach it."""
	reverse = {}
	for src in sources:
	for dep in graph.closure(src):
	reverse.setdefault(dep, set()).add(src)
	return reverse


	class Selection:
	"""Outcome: the full suite, explicit targets, no tests, or an error."""

	def __init__(self, mode, targets=(), reasons=(), ctest_names=(), standalone=()):
	self.mode = mode # "all", "targets", "none", or "error"
	self.targets = set(targets)
	self.reasons = list(reasons)
	# CTest names with no build target of their own.
	self.ctest_names = set(ctest_names)
	# Targets to name alongside ``buildtests`` in "all" mode.
	self.standalone = set(standalone)

	@property
	def targets_file(self):
	if self.mode == "error":
	raise ValueError("an invalid selection has no target file")
	if self.mode == "all":
	return "".join(name + "\n" for name in ["buildtests"] + sorted(self.standalone))
	if self.mode == "none":
	return "NONE\n"
	return "".join(name + "\n" for name in sorted(self.targets))

	@property
	def regex_file(self):
	if self.mode == "error":
	raise ValueError("an invalid selection has no regex file")
	if self.mode == "all":
	return "ALL\n"
	if self.mode == "none":
	return "NONE\n"
	names = sorted(self.targets) + sorted(self.ctest_names)
	return "^(%s)(_[0-9]+)?$\n" % "\|".join(re.escape(name) for name in names)


	def select(graph, changed_files, max_fraction=DEFAULT_MAX_FRACTION):
	"""Map changed paths to the tests that must run."""
	paths = []
	for path in changed_files:
	path = path.strip()
	if path and not _matches(path, IGNORED_PATTERNS):
	paths.append(path)
	if not paths:
	return Selection("none", reasons=["no change reaches a test"])
	for path in paths:
	if _matches(path, FULL_REBUILD_PATTERNS):
	return full_suite(graph, ["%s forces the full suite" % path])

	try:
	registered = test_registrations(graph)
	except ValueError as error:
	return Selection("error", reasons=[str(error)])
	sources = sorted(registered.targets)
	reverse = reverse_map(graph, sources)
	failtest_reverse = reverse_map(graph, sorted(registered.failtests))

	selected = set()
	selected_failtests = set()
	reasons = []
	for path in paths:
	reached_by = set(reverse.get(path, ()))
	if path in registered.targets:
	reached_by.add(path)
	failtests = set(failtest_reverse.get(path, ()))
	if path in registered.failtests:
	failtests.add(path)
	if reached_by or failtests:
	selected \|= reached_by
	selected_failtests \|= failtests
	continue
	if path in graph.files:
	# A source file in the tree that nothing includes: either a new
	# header not yet wired up or an unregistered translation unit.
	roots = TEST_ROOTS + (FAILTEST_ROOT,)
	if (_under(path, roots) and not _under(path, EXCLUDED_TEST_DIRS)
	and path.endswith(TEST_SOURCE_SUFFIXES)):
	return Selection("error", reasons=["%s has no CMake test target" % path])
	reasons.append("%s is in the tree but reaches no test" % path)
	continue
	# Deleted, renamed, or outside every scanned root: the graph cannot say
	# what it affected, so do not guess.
	return full_suite(graph, ["%s is not in the include graph" % path])

	if not selected and not selected_failtests:
	return Selection("none", reasons=reasons or ["no change reaches a test"])

	if len(selected) > max_fraction * len(sources):
	reasons.append(
	"%d of %d test sources selected (>%.0f%%)"
	% (len(selected), len(sources), 100 * max_fraction)
	)
	return full_suite(graph, reasons)

	ctest_names = set()
	for source in sorted(selected_failtests):
	ctest_names.update(registered.failtests[source])
	if ctest_names:
	reasons.append("%d compile-failure test(s) build from inside CTest"
	% len(selected_failtests))
	return Selection("targets", (registered.targets[s] for s in selected), reasons,
	ctest_names=ctest_names)


	def changed_files_from_git(source_dir, base_sha, head="HEAD"):
	"""Paths changed between ``base_sha`` and ``head``."""
	result = subprocess.run(
	["git", "diff", "--no-renames", "--name-only", "%s...%s" % (base_sha, head)],
	cwd=source_dir,
	capture_output=True,
	text=True,
	)
	if result.returncode != 0:
	raise RuntimeError("git diff failed: %s" % result.stderr.strip())
	return [line for line in result.stdout.splitlines() if line.strip()]


	def parse_args(argv):
	parser = argparse.ArgumentParser(description=__doc__,
	formatter_class=argparse.RawDescriptionHelpFormatter)
	default_source = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
	parser.add_argument("--source-dir", default=default_source,
	help="Eigen source tree (default: the tree containing this script)")
	parser.add_argument("--base-sha",
	help="compute changed files from 'git diff BASE...HEAD'")
	parser.add_argument("--head", default="HEAD", help="head revision for --base-sha")
	parser.add_argument("--changed-files",
	help="read newline-separated changed paths from this file ('-' for stdin)")
	parser.add_argument("--output-dir",
	help="write targets.txt and ctest_regex.txt here")
	parser.add_argument("--max-fraction", type=float, default=DEFAULT_MAX_FRACTION,
	help="degrade to the full suite above this fraction (default: %(default)s)")
	return parser.parse_args(argv)


	def main(argv=None):
	args = parse_args(argv)

	if args.changed_files:
	if args.changed_files == "-":
	changed = sys.stdin.read().splitlines()
	else:
	with open(args.changed_files) as handle:
	changed = handle.read().splitlines()
	elif args.base_sha:
	try:
	changed = changed_files_from_git(args.source_dir, args.base_sha, args.head)
	except RuntimeError as error:
	# Without a usable diff there is no basis for narrowing.
	print("%s; selecting the full suite" % error, file=sys.stderr)
	changed = None
	else:
	print("one of --base-sha or --changed-files is required", file=sys.stderr)
	return 2

	graph = IncludeGraph(args.source_dir)
	if changed is None:
	selection = full_suite(graph, ["the merge-base diff is unavailable"])
	else:
	selection = select(graph, changed, args.max_fraction)

	print("mode: %s" % selection.mode, file=sys.stderr)
	for reason in selection.reasons:
	print(" %s" % reason, file=sys.stderr)
	if selection.mode == "error":
	return 1
	if selection.mode == "targets":
	print(" %d targets: %s" % (len(selection.targets),
	" ".join(sorted(selection.targets))), file=sys.stderr)
	if selection.ctest_names:
	print(" %d CTest-only: %s" % (len(selection.ctest_names),
	" ".join(sorted(selection.ctest_names))),
	file=sys.stderr)

	if args.output_dir:
	os.makedirs(args.output_dir, exist_ok=True)
	with open(os.path.join(args.output_dir, "targets.txt"), "w") as handle:
	handle.write(selection.targets_file)
	with open(os.path.join(args.output_dir, "ctest_regex.txt"), "w") as handle:
	handle.write(selection.regex_file)
	else:
	sys.stdout.write(selection.targets_file)

	return 0


	if __name__ == "__main__":
	sys.exit(main())