Merge branch 'lukeshu/measurestack-fixes-round1'

1 files changed, 183 insertions, 42 deletions

diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py
index a93874f..67c44ce 100644
--- a/build-aux/measurestack/analyze.py
+++ b/build-aux/measurestack/analyze.py
@@ -3,24 +3,103 @@
 # Copyright (C) 2024-2025  Luke T. Shumaker <lukeshu@lukeshu.com>
 # SPDX-License-Identifier: AGPL-3.0-or-later
 
+import random
 import re
 import sys
 import typing
 
 from . import vcg
 
+# Whether to print "//dbg-cache:" on cache writes
+dbg_cache = False
+# Whether to print the graph in a /* comment */ before processing it
+dbg_dumpgraph = False
+# Whether to print "//dbg-nstatic:" lines that trace nstatic() execution
+dbg_nstatic = False
+# Whether to disable nstatic() caching (but does NOT disable any cache-related debug logging)
+dbg_nocache = False
+# Whether to sort things for consistently-ordered execution, or shuffle things to detect bugs
+dbg_sort: typing.Literal["unsorted", "sorted", "shuffled"] = "unsorted"
+
 # pylint: disable=unused-variable
 __all__ = [
     "BaseName",
     "QName",
     "UsageKind",
     "Node",
+    "maybe_sorted",
     "AnalyzeResultVal",
     "AnalyzeResultGroup",
     "AnalyzeResult",
     "analyze",
 ]
 
+
+def dumps(x: typing.Any, depth: int = 0, compact: bool = False) -> str:
+    match x:
+        case int() | str() | None:
+            return repr(x)
+        case dict():
+            if len(x) == 0:
+                return "{}"
+            ret = "{"
+            if not compact:
+                ret += "\n"
+            for k, v in x.items():
+                if not compact:
+                    ret += "\t" * (depth + 1)
+                ret += dumps(k, depth + 1, True)
+                ret += ":"
+                if not compact:
+                    ret += " "
+                ret += dumps(v, depth + 1, compact)
+                ret += ","
+                if not compact:
+                    ret += "\n"
+            if not compact:
+                ret += "\t" * depth
+            ret += "}"
+            return ret
+        case list():
+            if len(x) == 0:
+                return "[]"
+            ret = "["
+            if not compact:
+                ret += "\n"
+            for v in x:
+                if not compact:
+                    ret += "\t" * (depth + 1)
+                ret += dumps(v, depth + 1, compact)
+                ret += ","
+                if not compact:
+                    ret += "\n"
+            if not compact:
+                ret += "\t" * depth
+            ret += "]"
+            return ret
+        case set():
+            if len(x) == 0:
+                return "set()"
+            ret = "{"
+            if not compact:
+                ret += "\n"
+            for v in x:
+                if not compact:
+                    ret += "\t" * (depth + 1)
+                ret += dumps(v, depth + 1, compact)
+                ret += ","
+                if not compact:
+                    ret += "\n"
+            if not compact:
+                ret += "\t" * depth
+            ret += "}"
+            return ret
+        case _:
+            if hasattr(x, "__dict__"):
+                return f"{x.__class__.__name__}(*{dumps(x.__dict__, depth, compact)})"
+            return f"TODO({x.__class__.__name__})"
+
+
 # types ########################################################################
 
 
@@ -152,28 +231,39 @@ class AnalyzeResult(typing.NamedTuple):
 
 class SkipModel(typing.NamedTuple):
     """Running the skipmodel calls `.fn(chain, ...)` with the chain
-    consisting of the last `.nchain` items (if .nchain is an int), or
-    the chain starting with the *last* occurance of `.nchain` (if
-    .nchain is a collection).  If the chain is not that long or does
-    not contain a member of the collection, then .fn is not called and
-    the call is *not* skipped.
+    consisting of the last few items of the input chain.
+
+    If `.nchain` is an int:
+
+     - the chain is the last `.nchain` items or the input chain.  If
+       the input chain is not that long, then `.fn` is not called and
+       the call is *not* skipped.
 
+    If `.nchain` is a collection:
+
+     - the chain starts with the *last* occurance of `.nchain` in the
+       input chain.  If the input chain does not contain a member of
+       the collection, then .fn is called with an empty chain.
     """
 
     nchain: int | typing.Collection[BaseName]
-    fn: typing.Callable[[typing.Sequence[QName], QName], bool]
-
-    def __call__(self, chain: typing.Sequence[QName], call: QName) -> tuple[bool, int]:
-        if isinstance(self.nchain, int):
-            if len(chain) >= self.nchain:
-                _chain = chain[-self.nchain :]
-                return self.fn(_chain, call), len(_chain)
-        else:
-            for i in reversed(range(len(chain))):
-                if chain[i].base() in self.nchain:
-                    _chain = chain[i - 1 :]
-                    return self.fn(_chain, call), len(_chain)
-        return False, 0
+    fn: typing.Callable[[typing.Sequence[QName], Node, QName], bool]
+
+    def __call__(
+        self, chain: typing.Sequence[QName], node: Node, call: QName
+    ) -> tuple[bool, int]:
+        match self.nchain:
+            case int():
+                if len(chain) >= self.nchain:
+                    _chain = chain[-self.nchain :]
+                    return self.fn(_chain, node, call), len(_chain) + 1
+                return False, 0
+            case _:
+                for i in reversed(range(len(chain))):
+                    if chain[i].base() in self.nchain:
+                        _chain = chain[i:]
+                        return self.fn(_chain, node, call), len(_chain) + 1
+                return self.fn([], node, call), 1
 
 
 class Application(typing.Protocol):
@@ -235,6 +325,39 @@ class _Graph:
         return self._resolve_cache[funcname]
 
 
+if typing.TYPE_CHECKING:
+    from _typeshed import SupportsRichComparisonT as _T_sortable
+
+_T = typing.TypeVar("_T")
+
+
+@typing.overload
+def maybe_sorted(
+    unsorted: typing.Iterable["_T_sortable"], /, *, key: None = None
+) -> typing.Iterable["_T_sortable"]: ...
+@typing.overload
+def maybe_sorted(
+    unsorted: typing.Iterable[_T], /, *, key: typing.Callable[[_T], "_T_sortable"]
+) -> typing.Iterable[_T]: ...
+
+
+def maybe_sorted(
+    unsorted: typing.Iterable[_T],
+    /,
+    *,
+    key: typing.Callable[[_T], "_T_sortable"] | None = None,
+) -> typing.Iterable[_T]:
+    match dbg_sort:
+        case "unsorted":
+            return unsorted
+        case "sorted":
+            return sorted(unsorted, key=key)  # type: ignore
+        case "shuffled":
+            ret = [*unsorted]
+            random.shuffle(ret)
+            return ret
+
+
 def _make_graph(
     ci_fnames: typing.Collection[str],
     app: Application,
@@ -297,7 +420,7 @@ def _make_graph(
                     raise ValueError(f"unknown caller: {caller}")
                 if callee == QName("__indirect_call"):
                     callees, missing_ok = app.indirect_callees(elem)
-                    for callee in callees:
+                    for callee in maybe_sorted(callees):
                         if callee not in graph[caller].calls:
                             graph[caller].calls[callee] = missing_ok
                 else:
@@ -305,12 +428,15 @@ def _make_graph(
             case _:
                 raise ValueError(f"unknown elem type {elem.typ!r}")
 
-    for ci_fname in ci_fnames:
+    for ci_fname in maybe_sorted(ci_fnames):
         with open(ci_fname, "r", encoding="utf-8") as fh:
             for elem in vcg.parse_vcg(fh):
                 handle_elem(elem)
 
-    for node in app.extra_nodes():
+    def sort_key(node: Node) -> QName:
+        return node.funcname
+
+    for node in maybe_sorted(app.extra_nodes(), key=sort_key):
         if node.funcname in graph:
             raise ValueError(f"duplicate node {node.funcname}")
         graph[node.funcname] = node
@@ -332,33 +458,33 @@ def analyze(
     cfg_max_call_depth: int,
 ) -> AnalyzeResult:
     graphdata = _make_graph(ci_fnames, app)
+    if dbg_dumpgraph:
+        print(f"/* {dumps(graphdata)} */")
 
     missing: set[QName] = set()
     dynamic: set[QName] = set()
     included_funcs: set[QName] = set()
 
-    dbg = False
-
     track_inclusion: bool = True
 
     skipmodels = app.skipmodels()
     for name, model in skipmodels.items():
-        if isinstance(model.nchain, int):
-            assert model.nchain > 1
-        else:
+        if not isinstance(model.nchain, int):
             assert len(model.nchain) > 0
 
     _nstatic_cache: dict[QName, int] = {}
 
     def _nstatic(chain: list[QName], funcname: QName) -> tuple[int, int]:
-        nonlocal dbg
         nonlocal track_inclusion
 
         assert funcname in graphdata.graph
 
+        def putdbg(msg: str) -> None:
+            print(f"//dbg-nstatic: {'- '*len(chain)}{msg}")
+
         node = graphdata.graph[funcname]
-        if dbg:
-            print(f"//dbg: {'- '*len(chain)}{funcname}\t{node.nstatic}")
+        if dbg_nstatic:
+            putdbg(f"{funcname}\t{node.nstatic}")
         if node.usage_kind == "dynamic" or node.ndynamic > 0:
             dynamic.add(funcname)
         if track_inclusion:
@@ -378,37 +504,52 @@ def analyze(
                 call_qname = graphdata.resolve_funcname(call_orig_qname)
                 if not call_qname:
                     if skipmodel:
-                        skip, _ = skipmodel(chain, call_orig_qname)
+                        skip, _ = skipmodel(chain[:-1], node, call_orig_qname)
                         if skip:
-                            if dbg:
-                                print(
-                                    f"//dbg: {'- '*len(chain)}{call_orig_qname}\tskip missing"
-                                )
+                            if dbg_nstatic:
+                                putdbg(f"{call_orig_qname}\tskip missing")
                             continue
                     if not call_missing_ok:
                         missing.add(call_orig_qname)
-                    if dbg:
-                        print(f"//dbg: {'- '*len(chain)}{call_orig_qname}\tmissing")
+                    if dbg_nstatic:
+                        putdbg(f"{call_orig_qname}\tmissing")
                     continue
 
                 # 2. Skip
                 if skipmodel:
-                    skip, skip_nchain = skipmodel(chain, call_qname)
+                    skip, skip_nchain = skipmodel(chain[:-1], node, call_qname)
                     max_call_nchain = max(max_call_nchain, skip_nchain)
                     if skip:
-                        if dbg:
-                            print(f"//dbg: {'- '*len(chain)}{call_qname}\tskip")
+                        if dbg_nstatic:
+                            putdbg(f"{call_qname}\tskip")
                         continue
 
                 # 3. Call
-                if skip_nchain == 0 and call_qname in _nstatic_cache:
-                    max_call_nstatic = max(max_call_nstatic, _nstatic_cache[call_qname])
+                if (
+                    (not dbg_nocache)
+                    and skip_nchain == 0
+                    and call_qname in _nstatic_cache
+                ):
+                    call_nstatic = _nstatic_cache[call_qname]
+                    if dbg_nstatic:
+                        putdbg(f"{call_qname}\ttotal={call_nstatic} (cache-read)")
+                    max_call_nstatic = max(max_call_nstatic, call_nstatic)
                 else:
                     call_nstatic, call_nchain = _nstatic(chain, call_qname)
                     max_call_nstatic = max(max_call_nstatic, call_nstatic)
                     max_call_nchain = max(max_call_nchain, call_nchain)
                     if skip_nchain == 0 and call_nchain == 0:
-                        _nstatic_cache[call_qname] = call_nstatic
+                        if dbg_nstatic:
+                            putdbg(f"{call_qname}\ttotal={call_nstatic} (cache-write)")
+                        if call_qname not in _nstatic_cache:
+                            if dbg_cache:
+                                print(f"//dbg-cache: {call_qname} = {call_nstatic}")
+                            _nstatic_cache[call_qname] = call_nstatic
+                        else:
+                            assert dbg_nocache
+                            assert _nstatic_cache[call_qname] == call_nstatic
+                    elif dbg_nstatic:
+                        putdbg(f"{call_qname}\ttotal={call_nstatic} (do-not-cache)")
             chain.pop()
         return node.nstatic + max_call_nstatic, max(0, max_call_nchain - 1)