diff options
Diffstat (limited to 'stack.py')
| -rw-r--r-- | stack.py | 184 |
1 files changed, 184 insertions, 0 deletions
diff --git a/stack.py b/stack.py new file mode 100644 index 0000000..c1e36d3 --- /dev/null +++ b/stack.py @@ -0,0 +1,184 @@ +#!/usr/bin/env python3 +import re +import sys +import typing + +# Parse the "VCG" language +# +# https://www.rw.cdl.uni-saarland.de/people/sander/private/html/gsvcg1.html +# +# The formal syntax is found at +# ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/vcg.tgz `doc/grammar.txt`. + + +class VCGElem: + typ: str + lineno: int + attrs: dict[str, str] + + +def parse_vcg(reader: typing.TextIO) -> typing.Iterator[VCGElem]: + re_beg = re.compile(r"(edge|node):\s*\{\s*") + _re_tok = r"[a-zA-Z_][a-zA-Z0-9_]*" + _re_str = r'"(?:[^\"]|\\.)*"' + re_attr = re.compile( + "(" + _re_tok + r")\s*:\s*(" + _re_tok + "|" + _re_str + r")\s*" + ) + re_end = re.compile(r"\}\s*$") + re_skip = re.compile(r"(graph:\s*\{\s*title\s*:\s*" + _re_str + r"\s*|\})\s*") + re_esc = re.compile(r"\\.") + + for lineno, line in enumerate(reader): + pos = 0 + + def _raise(msg: str) -> typing.NoReturn: + nonlocal lineno + nonlocal line + nonlocal pos + e = SyntaxError(msg) + e.lineno = lineno + e.offset = pos + e.text = line + raise e + + if re_skip.fullmatch(line): + continue + + elem = VCGElem() + elem.lineno = lineno + + m = re_beg.match(line, pos=pos) + if not m: + _raise("does not look like a VCG line") + elem.typ = m.group(1) + pos = m.end() + + elem.attrs = {} + while True: + if re_end.match(line, pos=pos): + break + m = re_attr.match(line, pos=pos) + if not m: + _raise("unexpected character") + k = m.group(1) + v = m.group(2) + if k in elem.attrs: + _raise(f"duplicate key: {repr(k)}") + if v.startswith('"'): + + def unesc(esc: re.Match[str]) -> str: + match esc.group(0)[1:]: + case "n": + return "\n" + case '"': + return '"' + case "\\": + return "\\" + case _: + _raise(f"invalid escape code {repr(esc.group(0))}") + + v = re_esc.sub(unesc, v[1:-1]) + elem.attrs[k] = v + pos = m.end() + + yield elem + + +class Node: + # from .title (`static` functions are prefixed with the + # compilation unit .c file, which is fine, we'll just leave it). + funcname: str + # .label is "{funcname}\n{location}\n{nstatic} bytes (static}\n{ndynamic} dynamic objects" + location: str + nstatic: int + ndynamic: int + + # edges with .sourcename set to this node + calls: set[str] + +def main() -> None: + re_label = re.compile( + r"(?P<funcname>[^\n]+)\n" + + r"(?P<location>[^\n]+:[0-9]+:[0-9]+)\n" + + r"(?P<nstatic>[0-9]+) bytes \(static\)\n" + + r"(?P<ndynamic>[0-9]+) dynamic objects", + flags=re.MULTILINE, + ) + + graph: dict[str, Node] = dict() + + for elem in parse_vcg(sys.stdin): + match elem.typ: + case "node": + node = Node() + node.calls = set() + skip = False + for k, v in elem.attrs.items(): + match k: + case "title": + node.funcname = v + case "label": + if elem.attrs.get("shape", "") != "ellipse": + m = re_label.fullmatch(v) + if not m: + raise ValueError( + f"unexpected label value {repr(v)}" + ) + node.location = m.group("location") + node.nstatic = int(m.group("nstatic")) + node.ndynamic = int(m.group("ndynamic")) + case "shape": + if v != "ellipse": + raise ValueError(f"unexpected shape value {repr(v)}") + skip = True + case _: + raise ValueError(f"unknown edge key {repr(k)}") + if not skip: + if node.funcname in graph: + raise ValueError(f"duplicate node {repr(node.funcname)}") + graph[node.funcname] = node + case "edge": + caller: str | None = None + callee: str | None = None + for k, v in elem.attrs.items(): + match k: + case "sourcename": + caller = v + case "targetname": + callee = v + case "label": + pass + case _: + raise ValueError(f"unknown edge key {repr(k)}") + if caller is None or callee is None: + raise ValueError(f"incomplete edge: {repr(elem.attrs)}") + if caller not in graph: + raise ValueError(f"unknown caller: {caller}") + graph[caller].calls.add(callee) + case _: + raise ValueError(f"unknown elem type {repr(elem.typ)}") + + # x + + missing: set[str] = set() + def nstatic(funcname: str) -> int: + if funcname not in graph: + missing.add(funcname) + return 0 + node = graph[funcname] + return node.nstatic + max([0, *[nstatic(call) for call in node.calls]]) + + namelen = max(len(name) for name in graph if name.endswith("_cr")) + print(("="*namelen)+" =======") + + for funcname in graph: + if funcname.endswith("_cr"): + print(f"{funcname}\t{nstatic(funcname)}") + + print(("="*namelen)+" =======") + + for funcname in sorted(missing): + print(f"{funcname}\tmissing") + +if __name__ == "__main__": + main() |