Debian Codegraph @

libdrgn/build-aux/gen_strswitch.py

raw
1 #!/usr/bin/env python3
2 # Copyright (c) Meta Platforms, Inc. and affiliates.
3 # SPDX-License-Identifier: LGPL-2.1-or-later
4
5 """
6 This script generates code for a "string switch", i.e., a switch statement
7 where the controlling expression is a string rather than an integer.
8
9 For example, the following input would generate code that calls handle_foo() if
10 name is "foo", handle_bar() if name is "bar", and handle_other() otherwise:
11
12 @strswitch (name)@
13 @case "foo"@
14 handle_foo();
15 break;
16 @case "bar"@
17 handle_bar();
18 break;
19 @default@
20 handle_other();
21 break;
22 @endswitch@
23
24 strswitch takes a null-terminated const char *string, like strcmp(). This
25 script also provides memswitch, which takes a const void *string and a
26 size_t length, analogously to memcmp():
27
28 @memswitch (name, name_len)@
29 @case "asdf"@
30 return 1;
31 @case "jkl"@
32 return 2;
33 @endswitch@
34
35 You must #include <string.h> before using strswitch or memswitch.
36
37 The generated code is more efficient than an if-else ladder of
38 strcmp()/memcmp() calls when there are many cases or the cases have common
39 prefixes. Note that for null-terminated strings, memswitch is usually faster
40 than strswitch if the length is already available, but strswitch is usually
41 faster than calling strlen() and using memswitch.
42
43 The generated code is compatible with a "normal" switch statement. Namely:
44
45 * Cases fall through to the next case.
46 * Break statements break out of the enclosing string switch.
47
48 The arguments to strswitch and memswitch may be arbitrary expressions.
49 The argument to the case directive is a string literal.
50 String switches may be nested.
51 """
52
53 import argparse
54 import operator
55 import re
56 import sys
57 from typing import Any, Dict, List, NamedTuple, Optional, TextIO, Union
58
59 from codegen_utils import (
60 CodeGenError,
61 c_bytes_literal,
62 c_char_ord_literal,
63 c_string_literal,
64 parse_c_string_literal,
65 )
66
67
68 class StrSwitchOptions(NamedTuple):
69 # These defaults were determined empirically with GCC 11 and Clang 13 on
70 # x86-64.
71
72 # GCC and Clang seem to compile constant strcmp() and strncmp() calls to
73 # actual function calls except for very short strings (1-3 bytes), but the
74 # function call overhead is only worth it for longer strings.
75 strcmp_threshold: int = 8
76 strncmp_threshold: int = 8
77 # GCC and Clang seem to inline all constant memcmp() calls to code that
78 # compares multiple bytes at a time, so it's almost always worth it to use
79 # memcmp().
80 memcmp_threshold: int = 2
81
82
83 class InputLine(NamedTuple):
84 line: str
85 filename: str
86 lineno: int
87
88
89 class OutputWriter:
90 def __init__(self, file: TextIO, filename: str) -> None:
91 self.file = file
92 self.filename = filename
93 self.filename_literal = c_string_literal(filename)
94 self.lineno = 0
95 self.last_filename: Optional[str] = None
96 self.last_lineno: Optional[int] = None
97
98 def _sync_line_directive(self) -> None:
99 if self.last_filename is not None:
100 self.lineno += 1
101 self.file.write(f"#line {self.lineno + 1} {self.filename_literal}\n")
102 self.last_filename = None
103 self.last_lineno = None
104
105 def write_line(self, line: str) -> None:
106 self._sync_line_directive()
107 self.file.write(line)
108 self.file.write("\n")
109 self.lineno += 1
110
111 def _write_line_directive(self, filename: str, lineno: int) -> None:
112 if filename != self.last_filename:
113 self.file.write(f"#line {lineno} {c_string_literal(filename)}\n")
114 self.lineno += 1
115 self.last_filename = filename
116 elif lineno - 1 != self.last_lineno:
117 self.file.write(f"#line {lineno}\n")
118 self.lineno += 1
119 self.last_lineno = lineno
120
121 def echo_line(self, line: InputLine) -> None:
122 if line.filename == "-":
123 self._sync_line_directive()
124 else:
125 self._write_line_directive(line.filename, line.lineno)
126 self.file.write(line.line)
127 self.file.write("\n")
128 self.lineno += 1
129
130
131 # A body read from the input file comprises lines copied directly from the
132 # input file and possible nested string switches.
133 InputBody = List[Union[InputLine, "StrSwitch"]]
134
135
136 class StrSwitchCase:
137 def __init__(self, index: int):
138 self.index = index
139 self.body: InputBody = []
140
141
142 class StrSwitch:
143 def __init__(self, type: str, index: int, indent: str, args: InputLine) -> None:
144 # Type of switch (strswitch or memswitch).
145 self.type = type
146 self._ident_prefix = f"{type}{index}_"
147 # Indentation before the first @ of the switch directive.
148 self.indent = indent
149 # Argument to the switch directive.
150 self.args = args
151
152 # Body between the switch directive and the first case or default
153 # directive.
154 self.switch_body: InputBody = []
155 # Mapping from case values to the case itself.
156 self.cases: Dict[bytes, StrSwitchCase] = {}
157 # Body of the default directive, or None if this switch does not have a
158 # default directive.
159 self.default_body: Optional[InputBody] = None
160 # Index of the case after the default directive or len(self.cases) if
161 # there is no case after the default directive.
162 self.default_index = -1
163 # The body that we're currently reading.
164 self.current_body = self.switch_body
165
166 def has_default(self) -> bool:
167 return self.default_body is not None
168
169 def ident(self, name: str) -> str:
170 return self._ident_prefix + name
171
172
173 def handle_switch_directive(
174 line: InputLine,
175 directive: str,
176 switches: List[StrSwitch],
177 switch_counts: Dict[str, int],
178 ) -> None:
179 match = re.fullmatch(r"((\s*)@\s*" + directive + r"\s*\()(.*)\)\s*@\s*", line.line)
180 if not match:
181 raise CodeGenError(f"invalid {directive} directive", line.filename, line.lineno)
182
183 index = switch_counts.setdefault(directive, 0)
184 switch_counts[directive] += 1
185
186 # We want to record that the switch arguments came from the input file, so
187 # get rid of the directive, but replace it with whitespace so that the
188 # arguments are in the same column as in the input file.
189 args = InputLine(
190 re.sub(r"\S", " ", match.group(1)) + match.group(3), line.filename, line.lineno
191 )
192
193 switches.append(StrSwitch(directive, index, match.group(2), args))
194
195
196 def handle_case_directive(line: InputLine, switches: List[StrSwitch]) -> None:
197 match = re.fullmatch(r'\s*@\s*case\s*("(?:[^\"]|\\")*")\s*@\s*', line.line)
198 error = False
199 if match:
200 try:
201 case_value = parse_c_string_literal(match.group(1)).encode()
202 except Exception:
203 error = True
204 else:
205 error = True
206 if error:
207 raise CodeGenError("invalid case directive", line.filename, line.lineno)
208
209 if not switches:
210 raise CodeGenError("case outside of switch", line.filename, line.lineno)
211 switch = switches[-1]
212
213 if case_value in switch.cases:
214 raise CodeGenError("duplicate case value", line.filename, line.lineno)
215 if switch.type == "strswitch" and 0 in case_value:
216 raise CodeGenError(
217 "null byte in strswitch case value", line.filename, line.lineno
218 )
219 case = StrSwitchCase(len(switch.cases))
220 switch.cases[case_value] = case
221 switch.current_body = case.body
222
223
224 def handle_default_directive(line: InputLine, switches: List[StrSwitch]) -> None:
225 match = re.fullmatch(r"\s*@\s*default\s*@\s*", line.line)
226 if not match:
227 raise CodeGenError("invalid default directive", line.filename, line.lineno)
228
229 if not switches:
230 raise CodeGenError("default outside of switch", line.filename, line.lineno)
231 switch = switches[-1]
232
233 if switch.has_default():
234 raise CodeGenError(
235 "multiple default directives in one switch", line.filename, line.lineno
236 )
237 switch.default_body = []
238 switch.current_body = switch.default_body
239 switch.default_index = len(switch.cases)
240
241
242 def char_eq(switch: StrSwitch, str_index: int, c: int) -> str:
243 return f"{switch.ident('str')}[{str_index}] == {c_char_ord_literal(c)}"
244
245
246 def str_eq(
247 options: StrSwitchOptions, switch: StrSwitch, str_index: int, s: bytes
248 ) -> str:
249 if switch.type == "memswitch" and len(s) >= options.memcmp_threshold:
250 literal = c_bytes_literal(s)
251 return f"memcmp(&{switch.ident('str')}[{str_index}], {literal}, sizeof({literal}) - 1) == 0"
252 elif (
253 switch.type == "strswitch" and s[-1] == 0 and len(s) >= options.strcmp_threshold
254 ):
255 literal = c_bytes_literal(s[:-1])
256 return f"strcmp(&{switch.ident('str')}[{str_index}], {literal}) == 0"
257 elif (
258 switch.type == "strswitch"
259 and s[-1] != 0
260 and len(s) >= options.strncmp_threshold
261 ):
262 literal = c_bytes_literal(s)
263 return f"strncmp(&{switch.ident('str')}[{str_index}], {literal}, sizeof({literal}) - 1) == 0"
264 else:
265 char_eqs = [char_eq(switch, i, c) for i, c in enumerate(s, str_index)]
266 return " && ".join(char_eqs)
267
268
269 def output_switch_args(output: OutputWriter, switch: StrSwitch, indent: str) -> None:
270 output.write_line(f"{indent}{switch.ident('args')}(")
271 output.echo_line(switch.args)
272 output.write_line(f"{indent})")
273
274
275 def output_body(
276 output: OutputWriter, options: StrSwitchOptions, body: InputBody, indent: str
277 ) -> None:
278 for fragment in body:
279 if isinstance(fragment, StrSwitch):
280 output_switch(output, options, fragment, indent)
281 else:
282 output.echo_line(fragment)
283
284
285 def output_case_body(
286 output: OutputWriter,
287 options: StrSwitchOptions,
288 switch: StrSwitch,
289 case: StrSwitchCase,
290 indent: str,
291 ) -> None:
292 if case.index > 0:
293 output.write_line(f"{indent}{switch.ident('case')}{case.index}:")
294
295 output_body(output, options, case.body, indent)
296
297 # Emulate fallthrough.
298 if case.index + 1 == switch.default_index:
299 output.write_line(f"{indent}goto {switch.ident('default')};")
300 elif case.index + 1 < len(switch.cases):
301 output.write_line(f"{indent}goto {switch.ident('case')}{case.index + 1};")
302
303
304 def output_default(
305 output: OutputWriter,
306 options: StrSwitchOptions,
307 switch: StrSwitch,
308 body: bool,
309 indent: str,
310 ) -> None:
311 assert switch.default_body is not None
312 if body:
313 if switch.default_index > 0:
314 output.write_line(f"{indent}{switch.ident('default')}:")
315
316 output_body(output, options, switch.default_body, indent)
317
318 # Emulate fallthrough.
319 if switch.default_index < len(switch.cases):
320 output.write_line(
321 f"{indent}goto {switch.ident('case')}{switch.default_index};"
322 )
323 else:
324 output.write_line(f"{indent}goto {switch.ident('default')};")
325
326
327 # This should be Dict[int, TrieNode], but mypy doesn't support recursive types
328 # (see python/mypy#731).
329 TrieInternalNode = Dict[int, Any]
330 # Trie which maps case values to cases.
331 TrieNode = Union[StrSwitchCase, TrieInternalNode]
332
333
334 def output_trie(
335 output: OutputWriter,
336 options: StrSwitchOptions,
337 switch: StrSwitch,
338 node: TrieNode,
339 str_index: int,
340 indent: str,
341 ) -> None:
342 # Compress nodes with only one edge into their children.
343 prefix = bytearray()
344 while not isinstance(node, StrSwitchCase) and len(node) == 1:
345 char, node = next(iter(node.items()))
346 prefix.append(char)
347
348 if prefix:
349 output.write_line(
350 f"{indent}if ({str_eq(options, switch, str_index, prefix)}) {{"
351 )
352 prefix_indent = "\t"
353 else:
354 prefix_indent = ""
355
356 if isinstance(node, StrSwitchCase):
357 output_case_body(output, options, switch, node, indent + prefix_indent)
358 else:
359 # We use an if-else ladder here rather than a switch statement so that
360 # break statements break out of the enclosing string switch. GCC and
361 # Clang generate very similar or identical code for if-else and switch.
362 first = True
363 for char, child in sorted(node.items(), key=operator.itemgetter(0)):
364 else_str = "" if first else "} else "
365 first = False
366 output.write_line(
367 f"{indent}{prefix_indent}{else_str}if ({char_eq(switch, str_index + len(prefix), char)}) {{"
368 )
369 output_trie(
370 output,
371 options,
372 switch,
373 child,
374 str_index + len(prefix) + 1,
375 indent + prefix_indent + "\t",
376 )
377
378 if switch.has_default():
379 output.write_line(f"{indent}{prefix_indent}}} else {{")
380 output_default(
381 output,
382 options,
383 switch,
384 switch.type == "strswitch" and str_index + len(prefix) == 0,
385 indent + prefix_indent + "\t",
386 )
387
388 output.write_line(f"{indent}{prefix_indent}}}")
389
390 if prefix:
391 if switch.has_default():
392 output.write_line(f"{indent}}} else {{")
393 output_default(
394 output,
395 options,
396 switch,
397 switch.type == "strswitch" and str_index == 0,
398 indent + "\t",
399 )
400
401 output.write_line(f"{indent}}}")
402
403
404 def output_strswitch(
405 output: OutputWriter, options: StrSwitchOptions, switch: StrSwitch, indent: str
406 ) -> None:
407 # Define a local macro to parse the switch arguments into variables for us.
408 # This accomplishes a couple of things:
409 # 1. It allows us to accept arbitrary expressions for the switch arguments
410 # without having to parse them ourselves.
411 # 2. It ensures that we only evaluate the arguments once.
412 output.write_line(f"{indent}\t#define {switch.ident('args')}(str) \\")
413 output.write_line(f"{indent}\t\tconst char *{switch.ident('str')} = (str);")
414 output_switch_args(output, switch, indent + "\t")
415 output.write_line(f"{indent}\t#undef {switch.ident('args')}")
416
417 if switch.cases:
418 # Convert the case dictionary into a trie. For strswitch, this includes
419 # the null terminator.
420 trie: TrieInternalNode = {}
421 for key, value in switch.cases.items():
422 node = trie
423 for c in key:
424 if c not in node:
425 node[c] = {}
426 node = node[c]
427 node[0] = value
428 output_trie(output, options, switch, trie, 0, indent + "\t")
429 else:
430 # Suppress unused variable warnings.
431 output.write_line(f"{indent}\t(void){switch.ident('str')};")
432 if switch.has_default():
433 output_default(output, options, switch, True, indent + "\t")
434
435
436 def output_memswitch_tries(
437 output: OutputWriter,
438 options: StrSwitchOptions,
439 switch: StrSwitch,
440 tries: TrieInternalNode,
441 indent: str,
442 ) -> None:
443 first = True
444 for n, trie in sorted(tries.items(), key=operator.itemgetter(0)):
445 else_str = "" if first else "} else "
446 first = False
447 output.write_line(f"{indent}{else_str}if ({switch.ident('len')} == {n}) {{")
448 output_trie(output, options, switch, trie, 0, indent + "\t")
449
450 if switch.has_default():
451 output.write_line(f"{indent}}} else {{")
452 output_default(output, options, switch, True, indent + "\t")
453
454 output.write_line(f"{indent}}}")
455
456
457 def output_memswitch(
458 output: OutputWriter, options: StrSwitchOptions, switch: StrSwitch, indent: str
459 ) -> None:
460 output.write_line(f"{indent}\t#define {switch.ident('args')}(ptr, len) \\")
461 # Implicitly convert ptr to const void * for consistency with memcmp(),
462 # then convert it to const char *.
463 output.write_line(f"{indent}\t\tconst void *{switch.ident('ptr')} = (ptr); \\")
464 output.write_line(
465 f"{indent}\t\tconst char *{switch.ident('str')} = {switch.ident('ptr')}; \\"
466 )
467 output.write_line(f"{indent}\t\tsize_t {switch.ident('len')} = (len);")
468 output_switch_args(output, switch, indent + "\t")
469 output.write_line(f"{indent}\t#undef {switch.ident('args')}")
470
471 if switch.cases:
472 # Convert the case dictionary into a trie. For memswitch, the first
473 # edge is the length of the case value, and there is no null
474 # terminator.
475 tries: TrieInternalNode = {}
476 for key, value in switch.cases.items():
477 node = tries
478 c = len(key)
479 for i in range(len(key)):
480 if c not in node:
481 node[c] = {}
482 node = node[c]
483 c = key[i]
484 node[c] = value
485 output_memswitch_tries(output, options, switch, tries, indent + "\t")
486 else:
487 # Suppress unused variable warnings.
488 output.write_line(f"{indent}\t(void){switch.ident('str')};")
489 output.write_line(f"{indent}\t(void){switch.ident('len')};")
490 if switch.has_default():
491 output_default(output, options, switch, True, indent + "\t")
492
493
494 def output_switch(
495 output: OutputWriter, options: StrSwitchOptions, switch: StrSwitch, indent: str
496 ) -> None:
497 # This "no-op" switch serves a few purposes:
498 # 1. It a makes a string switch statement syntactically equivalent to a normal
499 # switch statement.
500 # 2. It makes break statements inside of a string switch work as expected.
501 # 3. It gives us somewhere to put the body between the switch directive and
502 # the first case or default directive.
503 output.write_line(f"{indent}switch (1) {{")
504 output_body(output, options, switch.switch_body, indent)
505 output.write_line(f"{indent}default: {{")
506
507 if switch.type == "strswitch":
508 output_strswitch(output, options, switch, indent)
509 else: # switch.type == "memswitch"
510 output_memswitch(output, options, switch, indent)
511
512 output.write_line(f"{indent}}}")
513 output.write_line(f"{indent}}}")
514
515
516 def handle_endswitch_directive(
517 line: InputLine,
518 switches: List[StrSwitch],
519 output: OutputWriter,
520 options: StrSwitchOptions,
521 ) -> None:
522 match = re.fullmatch(r"\s*@\s*endswitch\s*@\s*", line.line)
523 if not match:
524 raise CodeGenError("invalid endswitch directive", line.line, line.lineno)
525 if not switches:
526 raise CodeGenError("unmatched endswitch", line.filename, line.lineno)
527
528 switch = switches.pop()
529 if switches:
530 switches[-1].current_body.append(switch)
531 else:
532 output.write_line(
533 f"{switch.indent}/* Generated by libdrgn/build-aux/gen_strswitch.py. */"
534 )
535 output_switch(output, options, switch, switch.indent)
536
537
538 def gen_strswitch(
539 in_file: TextIO,
540 in_filename: str,
541 out_file: TextIO,
542 out_filename: str,
543 options: StrSwitchOptions,
544 ) -> None:
545 switches: List[StrSwitch] = []
546 switch_counts: Dict[str, int] = {}
547 output = OutputWriter(out_file, out_filename)
548 for in_lineno, in_line in enumerate(in_file, 1):
549 line = InputLine(in_line.rstrip("\n"), in_filename, in_lineno)
550 match = re.match(
551 r"\s*@\s*((?:str|mem)switch|case|default|endswitch)", line.line
552 )
553 if match:
554 directive = match.group(1)
555 if directive == "strswitch" or directive == "memswitch":
556 handle_switch_directive(line, directive, switches, switch_counts)
557 elif directive == "case":
558 handle_case_directive(line, switches)
559 elif directive == "default":
560 handle_default_directive(line, switches)
561 else: # directive == "endswitch"
562 handle_endswitch_directive(line, switches, output, options)
563 elif switches:
564 switches[-1].current_body.append(line)
565 else:
566 output.echo_line(line)
567
568 if switches:
569 raise CodeGenError(
570 f"unclosed {switches[-1].type}",
571 switches[-1].args.filename,
572 switches[-1].args.lineno,
573 )
574
575
576 def main() -> None:
577 parser = argparse.ArgumentParser(
578 description="Generate code for string switch statements",
579 formatter_class=argparse.ArgumentDefaultsHelpFormatter,
580 )
581 parser.add_argument(
582 "input", metavar="FILE", help="input file, or - to read standard input"
583 )
584 parser.add_argument(
585 "-o",
586 "--output",
587 metavar="FILE",
588 default=argparse.SUPPRESS,
589 help="output file, or - to write to standard output (default: input filename with .strswitch suffix removed, or standard output if input file is standard input)",
590 )
591 codegen_group = parser.add_argument_group("code generation options")
592 codegen_group.add_argument(
593 "--strcmp-threshold",
594 metavar="N",
595 type=int,
596 default=StrSwitchOptions._field_defaults["strcmp_threshold"],
597 help="minimum number of characters to compare using strcmp()",
598 )
599 codegen_group.add_argument(
600 "--strncmp-threshold",
601 metavar="N",
602 type=int,
603 default=StrSwitchOptions._field_defaults["strncmp_threshold"],
604 help="minimum number of characters to compare using strncmp()",
605 )
606 codegen_group.add_argument(
607 "--memcmp-threshold",
608 metavar="N",
609 type=int,
610 default=StrSwitchOptions._field_defaults["memcmp_threshold"],
611 help="minimum number of characters to compare using memcmp()",
612 )
613 args = parser.parse_args()
614
615 options = StrSwitchOptions(
616 strcmp_threshold=args.strcmp_threshold,
617 strncmp_threshold=args.strncmp_threshold,
618 memcmp_threshold=args.memcmp_threshold,
619 )
620
621 if not hasattr(args, "output"):
622 if args.input == "-":
623 args.output = "-"
624 else:
625 if not args.input.endswith(".strswitch"):
626 sys.exit("input file name must end in .strswitch unless -o is given")
627 args.output = args.input[: -len(".strswitch")]
628
629 in_file = None
630 out_file = None
631 try:
632 if args.input == "-":
633 in_file = sys.stdin
634 else:
635 in_file = open(args.input, "r")
636 if args.output == "-":
637 out_file = sys.stdout
638 else:
639 out_file = open(args.output, "w")
640
641 gen_strswitch(in_file, args.input, out_file, args.output, options)
642 except CodeGenError as e:
643 sys.exit(e)
644 finally:
645 if args.output != "-" and out_file:
646 out_file.close()
647 if args.input != "-" and in_file:
648 in_file.close()
649
650
651 if __name__ == "__main__":
652 main()