1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
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()
|
