#!/usr/bin/env python3
# build-aux/stack.c.gen - Analyze stack sizes for compiled objects
#
# Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com>
# SPDX-License-Identifier: AGPL-3.0-or-later
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
################################################################################
# Main application
class Node:
# from .title (`static` and `__weak` functions are prefixed with
# the compilation unit .c file. For static functions that's fine,
# but we'll have to handle it specially for __weak.).
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]
re_location = re.compile(r"(?P<filename>.+):(?P<row>[0-9]+):(?P<col>[0-9]+)")
def read_source(location: str) -> str:
m = re_location.fullmatch(location)
if not m:
raise ValueError(f"unexpected label value {repr(location)}")
filename = m.group("filename")
row = int(m.group("row")) - 1
col = int(m.group("col")) - 1
with open(m.group("filename"), "r") as fh:
return fh.readlines()[row][col:].rstrip()
def main(ci_fnames: list[str]) -> None:
re_node_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,
)
re_call_vcall = re.compile(r"VCALL\((?P<obj>[^,]+), (?P<meth>[^,)]+)[,)].*")
re_call_other = re.compile(r"(?P<func>[^(]+)\(.*")
graph: dict[str, Node] = dict()
qualified: dict[str, set[str]] = dict()
def handle_elem(elem: VCGElem) -> None:
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_node_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
if ":" in node.funcname:
_, shortname = node.funcname.rsplit(":", 1)
if shortname not in qualified:
qualified[shortname] = set()
qualified[shortname].add(node.funcname)
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}")
if callee == "__indirect_call":
callstr = read_source(elem.attrs.get("label", ""))
if m := re_call_vcall.fullmatch(callstr):
callee += f":{m.group('obj')}->vtable->{m.group('meth')}"
elif m := re_call_other.fullmatch(callstr):
callee += f":{m.group('func')}"
else:
callee += f':{elem.attrs.get("label", "")}'
graph[caller].calls.add(callee)
case _:
raise ValueError(f"unknown elem type {repr(elem.typ)}")
for ci_fname in ci_fnames:
with open(ci_fname, "r") as fh:
for elem in parse_vcg(fh):
handle_elem(elem)
missing: set[str] = set()
cycles: set[str] = set()
print("/*")
dbg = False
def nstatic(funcname: str, chain: list[str] = []) -> int:
nonlocal dbg
if funcname not in graph:
if f"__wrap_{funcname}" in graph:
# Handle `ld --wrap` functions
funcname = f"__wrap_{funcname}"
elif funcname in qualified and len(qualified[funcname]) == 1:
# Handle `__weak` functions
funcname = sorted(qualified[funcname])[0]
else:
missing.add(funcname)
return 0
if funcname in chain:
if "__assert_msg_fail" in chain:
if funcname == "__wrap_printf":
return 0
pass
else:
cycles.add(f"{chain[chain.index(funcname):] + [funcname]}")
return 9999999
node = graph[funcname]
if dbg:
print(f"//dbg: {funcname}\t{node.nstatic}")
return node.nstatic + max(
[0, *[nstatic(call, chain + [funcname]) for call in node.calls]]
)
def thread_filter(name: str) -> bool:
return name.endswith("_cr") or name == "main"
namelen = max(len(name) for name in graph if thread_filter(name))
numlen = max(len(str(nstatic(name))) for name in graph if name.endswith("_cr"))
print(("=" * namelen) + " " + "=" * numlen)
for funcname in graph:
if thread_filter(funcname):
# dbg = "dhcp" in funcname
print(f"{funcname.ljust(namelen)} {str(nstatic(funcname)).rjust(numlen)}")
print(("=" * namelen) + " " + "=" * numlen)
for funcname in sorted(missing):
print(f"warning: missing: {funcname}")
for cycle in sorted(cycles):
print(f"warning: cycle: {cycle}")
print("*/")
if __name__ == "__main__":
re_suffix = re.compile(r"\.c\.o(bj)?$")
main(
[
re_suffix.sub(".c.ci", fname)
for fname in sys.argv[1:]
if re_suffix.search(fname)
]
)