Simply finder for deterministic cujs

Instead of choosing directories to run tests on, hardcode them
such that changes to source code (i.e. addition of new files or
directories don't change the targets for CUJs run

Bug: NA
Test: NA
Change-Id: I62c49bad86d8c3031b5220ff00c9784162a234c3

3 files changed, 150 insertions, 157 deletions

diff --git a/scripts/incremental_build/cuj_catalog.py b/scripts/incremental_build/cuj_catalog.py
index 76bbe122..36e863de 100644
--- a/scripts/incremental_build/cuj_catalog.py
+++ b/scripts/incremental_build/cuj_catalog.py
@@ -17,7 +17,6 @@ import io
 import logging
 import shutil
 import tempfile
-import textwrap
 import uuid
 from pathlib import Path
 from typing import Final, Optional
@@ -358,41 +357,35 @@ def create_delete_unkept_build_file(build_file) -> CujGroup:
     )
 
 
-NON_LEAF = "*/*"
-"""If `a/*/*` is a valid path `a` is not a leaf directory"""
-LEAF = "!*/*"
-"""If `a/*/*` is not a valid path `a` is a leaf directory, i.e. has no other
-non-empty sub-directories"""
-PKG = ["Android.bp", "!BUILD", "!BUILD.bazel"]
-"""limiting the candidate to Android.bp file with no sibling bazel files"""
-PKG_FREE = ["!**/Android.bp", "!**/BUILD", "!**/BUILD.bazel"]
-"""no Android.bp or BUILD or BUILD.bazel file anywhere"""
-
-
 def _kept_build_cujs() -> list[CujGroup]:
     # Bp2BuildKeepExistingBuildFile(build/bazel) is True(recursive)
     kept = src("build/bazel")
-    pkg = finder.any_dir_under(kept, *PKG)
-    examples = [pkg.joinpath("BUILD"), pkg.joinpath("BUILD.bazel")]
+    finder.confirm(
+        kept,
+        "compliance/Android.bp",
+        "!compliance/BUILD",
+        "!compliance/BUILD.bazel",
+        "rules/python/BUILD",
+    )
 
     return [
-        *[create_delete_kept_build_file(build_file) for build_file in examples],
-        create_delete(pkg.joinpath("BUILD/kept-dir"), InWorkspace.SYMLINK),
-        modify_revert_kept_build_file(finder.any_file_under(kept, "BUILD")),
+        *[
+            create_delete_kept_build_file(kept.joinpath("compliance").joinpath(b))
+            for b in ["BUILD", "BUILD.bazel"]
+        ],
+        create_delete(kept.joinpath("BUILD/kept-dir"), InWorkspace.SYMLINK),
+        modify_revert_kept_build_file(kept.joinpath("rules/python/BUILD")),
     ]
 
 
 def _unkept_build_cujs() -> list[CujGroup]:
     # Bp2BuildKeepExistingBuildFile(bionic) is False(recursive)
-    unkept = src("bionic")
-    pkg = finder.any_dir_under(unkept, *PKG)
+    unkept = src("bionic/libm")
+    finder.confirm(unkept, "Android.bp", "!BUILD", "!BUILD.bazel")
     return [
         *[
-            create_delete_unkept_build_file(build_file)
-            for build_file in [
-                pkg.joinpath("BUILD"),
-                pkg.joinpath("BUILD.bazel"),
-            ]
+            create_delete_unkept_build_file(unkept.joinpath(b))
+            for b in ["BUILD", "BUILD.bazel"]
         ],
         *[
             create_delete(build_file, InWorkspace.OMISSION)
@@ -401,7 +394,7 @@ def _unkept_build_cujs() -> list[CujGroup]:
                 unkept.joinpath("bogus-unkept/BUILD.bazel"),
             ]
         ],
-        create_delete(pkg.joinpath("BUILD/unkept-dir"), InWorkspace.SYMLINK),
+        create_delete(unkept.joinpath("BUILD/unkept-dir"), InWorkspace.SYMLINK),
     ]
 
 
@@ -410,23 +403,15 @@ def get_cujgroups() -> list[CujGroup]:
     # we are choosing "package" directories that have Android.bp but
     # not BUILD nor BUILD.bazel because
     # we can't tell if ShouldKeepExistingBuildFile would be True or not
-    pkg, p_why = finder.any_match(NON_LEAF, *PKG)
-    pkg_free, f_why = finder.any_match(NON_LEAF, *PKG_FREE)
-    leaf_pkg_free, _ = finder.any_match(LEAF, *PKG_FREE)
-    ancestor, a_why = finder.any_match(
-        "!Android.bp", "!BUILD", "!BUILD.bazel", "**/Android.bp"
-    )
-    logging.info(
-        textwrap.dedent(
-            f"""\
-                Choosing:
-                          package: {de_src(pkg)} has {p_why}
-                 package ancestor: {de_src(ancestor)} has {a_why} but no direct Android.bp
-                     package free: {de_src(pkg_free)} has {f_why} but no Android.bp anywhere
-                leaf package free: {de_src(leaf_pkg_free)} has neither Android.bp nor sub-dirs
-            """
-        )
-    )
+    non_empty_dir = "*/*"
+    pkg = src("art")
+    finder.confirm(pkg, non_empty_dir, "Android.bp", "!BUILD*")
+    pkg_free = src("bionic/docs")
+    finder.confirm(pkg_free, non_empty_dir, "!**/Android.bp", "!**/BUILD*")
+    ancestor = src("bionic")
+    finder.confirm(ancestor, "**/Android.bp", "!Android.bp", "!BUILD*")
+    leaf_pkg_free = src("bionic/build")
+    finder.confirm(leaf_pkg_free, f"!{non_empty_dir}", "!**/Android.bp", "!**/BUILD*")
 
     android_bp_cujs = [
         modify_revert(src("Android.bp")),
@@ -502,8 +487,8 @@ def get_cujgroups() -> list[CujGroup]:
         *[
             delete_restore(f, InWorkspace.SYMLINK)
             for f in [
-                finder.any_file("version_script.txt"),
-                finder.any_file("AndroidManifest.xml"),
+                src("bionic/libc/version_script.txt"),
+                src("external/cbor-java/AndroidManifest.xml"),
             ]
         ],
         *unreferenced_file_cujs,
diff --git a/scripts/incremental_build/finder.py b/scripts/incremental_build/finder.py
index 5d3e34ca..3b4b5dcc 100644..100755
--- a/scripts/incremental_build/finder.py
+++ b/scripts/incremental_build/finder.py
@@ -1,3 +1,4 @@
+#!/usr/bin/env python3
 # Copyright (C) 2023 The Android Open Source Project
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
@@ -11,11 +12,13 @@
 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 # See the License for the specific language governing permissions and
 # limitations under the License.
-import functools
+import argparse
 import glob
 import os
 import subprocess
 from pathlib import Path
+import textwrap
+from typing import Generator, Iterator
 
 from util import get_out_dir
 from util import get_top_dir
@@ -32,73 +35,107 @@ def is_git_repo(p: Path) -> bool:
     return git.returncode == 0
 
 
-def any_file(pattern: str) -> Path:
-    return any_file_under(get_top_dir(), pattern)
+def confirm(root_dir: Path, *globs: str):
+    for g in globs:
+        disallowed = g.startswith("!")
+        if disallowed:
+            g = g[1:]
+        paths = glob.iglob(g, root_dir=root_dir, recursive=True)
+        path = next(paths, None)
+        if disallowed:
+            if path is not None:
+                raise RuntimeError(f"{root_dir}/{path} unexpected")
+        else:
+            if path is None:
+                raise RuntimeError(f"{root_dir}/{g} doesn't match")
 
 
-def any_file_under(root: Path, pattern: str) -> Path:
-    if pattern.startswith("!"):
-        raise RuntimeError(f"provide a filename instead of {pattern}")
-    d, files = any_match_under(get_top_dir() if root is None else root, pattern)
-    files = [d.joinpath(f) for f in files]
-    try:
-        file = next(f for f in files if f.is_file())
-        return file
-    except StopIteration:
-        raise RuntimeError(f"no file matched {pattern}")
-
-
-def any_dir_under(root: Path, *patterns: str) -> Path:
-    d, _ = any_match_under(root, *patterns)
-    return d
-
-
-def any_match(*patterns: str) -> tuple[Path, list[str]]:
-    return any_match_under(get_top_dir(), *patterns)
+def _should_visit(c: os.DirEntry) -> bool:
+    return c.is_dir() and not (
+        c.is_symlink()
+        or "." in c.name
+        or "test" in c.name
+        or Path(c.path) == get_out_dir()
+    )
 
 
-@functools.cache
-def any_match_under(root: Path, *patterns: str) -> tuple[Path, list[str]]:
+def find_matches(root_dir: Path, *globs: str) -> Generator[Path, None, None]:
     """
     Finds sub-paths satisfying the patterns
-    :param patterns glob pattern to match or unmatch if starting with "!"
-    :param root the first directory to start searching from
-    :returns the dir and sub-paths matching the pattern
+    :param root_dir the first directory to start searching from
+    :param globs glob patterns to require or disallow (if starting with "!")
+    :returns dirs satisfying the glbos
     """
-    bfs: list[Path] = [root]
+    bfs: list[Path] = [root_dir]
     while len(bfs) > 0:
         first = bfs.pop(0)
         if is_git_repo(first):
-            matches: list[str] = []
-            for pattern in patterns:
-                negate = pattern.startswith("!")
-                if negate:
-                    pattern = pattern.removeprefix("!")
-                try:
-                    found_match = next(
-                        glob.iglob(pattern, root_dir=first, recursive=True)
-                    )
-                except StopIteration:
-                    found_match = None
-                if negate and found_match is not None:
-                    break
-                if not negate:
-                    if found_match is None:
-                        break
-                    else:
-                        matches.append(found_match)
-            else:
-                return Path(first), matches
-
-        def should_visit(c: os.DirEntry) -> bool:
-            return c.is_dir() and not (
-                c.is_symlink()
-                or "." in c.name
-                or "test" in c.name
-                or Path(c.path) == get_out_dir()
-            )
-
-        children = [Path(c.path) for c in os.scandir(first) if should_visit(c)]
+            try:
+                confirm(first, *globs)
+                yield first
+            except RuntimeError:
+                pass
+        children = [Path(c.path) for c in os.scandir(first) if _should_visit(c)]
         children.sort()
         bfs.extend(children)
-    raise RuntimeError(f"No suitable directory for {patterns}")
+
+
+def main():
+    p = argparse.ArgumentParser(
+        formatter_class=argparse.RawTextHelpFormatter,
+        description=textwrap.dedent(
+            f"""\
+            A utility to find a directory that have descendants that satisfy
+            specified required glob patterns and have no descendent that
+            contradict any specified disallowed glob pattern.
+
+            Example:
+                {Path(__file__).name} '**/Android.bp'
+                {Path(__file__).name} '!**/BUILD' '**/Android.bp'
+
+            Don't forget to SINGLE QUOTE patterns to avoid shell glob expansion!
+            """
+        ),
+    )
+    p.add_argument(
+        "globs",
+        nargs="+",
+        help="""glob patterns to require or disallow(if preceded with "!")""",
+    )
+    p.add_argument(
+        "--root_dir",
+        "-r",
+        type=lambda s: Path(s).resolve(),
+        default=get_top_dir(),
+        help=textwrap.dedent(
+            """\
+                top dir to interpret the glob patterns relative to
+                defaults to %(default)s
+            """
+        ),
+    )
+    p.add_argument(
+        "--max",
+        "-m",
+        type=int,
+        default=1,
+        help=textwrap.dedent(
+            """\
+                maximum number of matching directories to show
+                defaults to %(default)s
+            """
+        ),
+    )
+    options = p.parse_args()
+    results = find_matches(options.root_dir, *options.globs)
+    max: int = options.max
+    while max > 0:
+        max -= 1
+        path = next(results, None)
+        if path is None:
+            break
+        print(f"{path.relative_to(get_top_dir())}")
+
+
+if __name__ == "__main__":
+    main()
diff --git a/scripts/incremental_build/finder_test.py b/scripts/incremental_build/finder_test.py
index eb7e9508..b04031c4 100644
--- a/scripts/incremental_build/finder_test.py
+++ b/scripts/incremental_build/finder_test.py
@@ -11,70 +11,41 @@
 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 # See the License for the specific language governing permissions and
 # limitations under the License.
-import os
 import unittest
 
-from finder import any_match
+from finder import confirm
 from finder import is_git_repo
-from util import get_top_dir
+from cuj import src
 
 
 class UtilTest(unittest.TestCase):
     def test_is_git_repo(self):
-        self.assertFalse(is_git_repo(get_top_dir()))
-        self.assertTrue(is_git_repo(get_top_dir().joinpath("build/soong")))
+        self.assertFalse(is_git_repo(src(".")))
+        self.assertTrue(is_git_repo(src("build/soong")))
 
     def test_any_match(self):
-        with self.subTest("root.bp"):
-            path, matches = any_match("root.bp")
-            self.assertEqual(matches, ["root.bp"])
-            self.assertEqual(path, get_top_dir().joinpath("build/soong"))
+        with self.subTest("required"):
+            with self.subTest("literal"):
+                confirm(src("build/soong"), "root.bp")
+            with self.subTest("wildcarded"):
+                confirm(src("build"), "*/root.bp")
+
+        with self.subTest("disallowed"):
+            with self.subTest("literal"):
+                confirm(src("build/bazel"), "!Android.bp", "!BUILD")
+            with self.subTest("wildcarded"):
+               confirm(src("bionic"), "!*.bazel", "*")
+
+        with self.subTest("disallowed and required"):
+            with self.subTest("literal"):
+                confirm(
+                    src("build/bazel/scripts/incremental_build"),
+                    "BUILD.bazel",
+                    "!BUILD",
+                )
+            with self.subTest("wildcarded"):
+                confirm(src("bionic/libm"), "!**/BUILD", "**/*.cpp")
 
-        with self.subTest("non-package"):
-            path, matches = any_match(
-                "!Android.bp",
-                "!BUILD",
-                "scripts/incremental_build/incremental_build.py",
-            )
-            self.assertEqual(
-                matches, ["scripts/incremental_build/incremental_build.py"]
-            )
-            self.assertEqual(path, get_top_dir().joinpath("build/bazel"))
-
-        with self.subTest("BUILD and README.md"):
-            path, matches = any_match("BUILD", "README.md")
-            self.assertEqual(matches, ["BUILD", "README.md"])
-            self.assertTrue(path.joinpath("BUILD").exists())
-            self.assertTrue(path.joinpath("README.md").exists())
-
-        with self.subTest("BUILD without README.md"):
-            path, matches = any_match("BUILD", "!README.md")
-            self.assertEqual(matches, ["BUILD"])
-            self.assertTrue(path.joinpath("BUILD").exists())
-            self.assertFalse(path.joinpath("README.md").exists())
-
-        with self.subTest("dir without *.bazel"):
-            path, matches = any_match("!*.bazel", "*")
-            self.assertGreater(len(matches), 0)
-            children = os.listdir(path)
-            self.assertGreater(len(children), 0)
-            for child in children:
-                self.assertFalse(child.endswith(".bazel"))
-
-        with self.subTest("no BUILD or README.md"):
-            path, matches = any_match("*/BUILD", "*/README.md")
-            self.assertGreater(len(matches), 0)
-            for m in matches:
-                self.assertTrue(path.joinpath(m).exists())
-
-        with self.subTest('no BUILD or cpp file in tree"'):
-            path, matches = any_match("!**/BUILD", "**/*.cpp")
-            self.assertEqual(len(matches), 1)
-            self.assertTrue(path.joinpath(matches[0]).exists())
-            self.assertTrue(matches[0].endswith(".cpp"))
-            for _, dirs, files in os.walk(path):
-                self.assertFalse("BUILD" in dirs)
-                self.assertFalse("BUILD" in files)
 
 
 if __name__ == "__main__":