summaryrefslogtreecommitdiff
path: root/build-aux/measurestack/analyze.py
diff options
context:
space:
mode:
Diffstat (limited to 'build-aux/measurestack/analyze.py')
-rw-r--r--build-aux/measurestack/analyze.py225
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)
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2025-05-12 07:58:31 +0000