Coverage for src / competitive_verifier / oj / languages / cplusplus_bundle.py: 70%
197 statements
« prev ^ index » next coverage.py v7.13.1, created at 2026-10-03 23:40 +0900
1# Python Version: 3.x
2import contextlib
3import functools
4import json
5import os
6import pathlib
7import re
8import shutil
9from logging import getLogger
10from typing import Any
12from competitive_verifier.exec import command_stdout
14logger = getLogger(__name__)
16BITS_STDCXX_H = "bits/stdc++.h"
18CXX_STANDARD_LIBS = {
19 "algorithm",
20 "any",
21 "array",
22 "atomic",
23 "barrier",
24 "bit",
25 "bitset",
26 "charconv",
27 "chrono",
28 "codecvt",
29 "compare",
30 "complex",
31 "concepts",
32 "condition_variable",
33 "contracts",
34 "coroutine",
35 "debugging",
36 "deque",
37 "exception",
38 "expected",
39 "filesystem",
40 "flat_map",
41 "flat_set",
42 "format",
43 "forward_list",
44 "fstream",
45 "functional",
46 "future",
47 "generator",
48 "initializer_list",
49 "inplace_vector",
50 "iomanip",
51 "ios",
52 "iosfwd",
53 "iostream",
54 "istream",
55 "iterator",
56 "latch",
57 "limits",
58 "list",
59 "locale",
60 "map",
61 "mdspan",
62 "memory",
63 "memory_resource",
64 "meta",
65 "mutex",
66 "new",
67 "numbers",
68 "numeric",
69 "optional",
70 "ostream",
71 "print",
72 "queue",
73 "random",
74 "ranges",
75 "ratio",
76 "regex",
77 "scoped_allocator",
78 "semaphore",
79 "set",
80 "shared_mutex",
81 "source_location",
82 "span",
83 "spanstream",
84 "sstream",
85 "stack",
86 "stacktrace",
87 "stdexcept",
88 "stdfloat",
89 "stop_token",
90 "streambuf",
91 "string",
92 "string_view",
93 "syncstream",
94 "system_error",
95 "text_encoding",
96 "thread",
97 "tuple",
98 "type_traits",
99 "typeindex",
100 "typeinfo",
101 "unordered_map",
102 "unordered_set",
103 "utility",
104 "valarray",
105 "variant",
106 "vector",
107 "version",
108}
110C_STANDARD_LIBS = {
111 "assert.h",
112 "complex.h",
113 "ctype.h",
114 "errno.h",
115 "fenv.h",
116 "float.h",
117 "inttypes.h",
118 "iso646.h",
119 "limits.h",
120 "locale.h",
121 "math.h",
122 "setjmp.h",
123 "signal.h",
124 "stdalign.h",
125 "stdarg.h",
126 "stdatomic.h",
127 "stdbit.h",
128 "stdbool.h",
129 "stdckdint.h",
130 "stddef.h",
131 "stdint.h",
132 "stdio.h",
133 "stdlib.h",
134 "stdnoreturn.h",
135 "string.h",
136 "tgmath.h",
137 "threads.h",
138 "time.h",
139 "uchar.h",
140 "wchar.h",
141 "wctype.h",
142}
144CXX_C_ORIGIN_LIBS = {"c" + name[: -len(".h")] for name in C_STANDARD_LIBS}
146BITS_EXTCXX_H = "bits/extc++.h"
148EXT_LIBS = {
149 "ext/algorithm",
150 "ext/array_allocator.h",
151 "ext/atomicity.h",
152 "ext/bitmap_allocator.h",
153 "ext/cast.h",
154 "ext/concurrence.h",
155 "ext/debug_allocator.h",
156 "ext/extptr_allocator.h",
157 "ext/functional",
158 "ext/iterator",
159 "ext/malloc_allocator.h",
160 "ext/memory",
161 "ext/mt_allocator.h",
162 "ext/new_allocator.h",
163 "ext/numeric",
164 "ext/pod_char_traits.h",
165 "ext/pointer.h",
166 "ext/pool_allocator.h",
167 "ext/rb_tree",
168 "ext/rope",
169 "ext/slist",
170 "ext/stdio_filebuf.h",
171 "ext/stdio_sync_filebuf.h",
172 "ext/throw_allocator.h",
173 "ext/typelist.h",
174 "ext/type_traits.h",
175 "ext/vstring.h",
176 "ext/pb_ds/assoc_container.hpp",
177 "ext/pb_ds/priority_queue.hpp",
178 "ext/pb_ds/exception.hpp",
179 "ext/pb_ds/hash_policy.hpp",
180 "ext/pb_ds/list_update_policy.hpp",
181 "ext/pb_ds/tree_policy.hpp",
182 "ext/pb_ds/trie_policy.hpp",
183}
185BITS_STDTR1CXX_H = "bits/stdtr1c++.h"
187TR1_LIBS = {
188 "tr1/array",
189 "tr1/cctype",
190 "tr1/cfenv",
191 "tr1/cfloat",
192 "tr1/cinttypes",
193 "tr1/climits",
194 "tr1/cmath",
195 "tr1/complex",
196 "tr1/cstdarg",
197 "tr1/cstdbool",
198 "tr1/cstdint",
199 "tr1/cstdio",
200 "tr1/cstdlib",
201 "tr1/ctgmath",
202 "tr1/ctime",
203 "tr1/cwchar",
204 "tr1/cwctype",
205 "tr1/functional",
206 "tr1/random",
207 "tr1/tuple",
208 "tr1/unordered_map",
209 "tr1/unordered_set",
210 "tr1/utility",
211}
214@functools.cache
215def _check_compiler(compiler: str) -> str:
216 # Executables named "g++" are not always g++, due to the fake g++ of macOS
217 version = command_stdout([compiler, "--version"])
218 if "clang" in version.lower() or "Apple LLVM".lower() in version.lower(): 218 ↛ 219line 218 didn't jump to line 219 because the condition on line 218 was never true
219 return "clang"
220 if "g++" in version.lower(): 220 ↛ 222line 220 didn't jump to line 222 because the condition on line 220 was always true
221 return "gcc"
222 return "unknown" # default
225@functools.cache
226def _get_uncommented_code(
227 path: pathlib.Path, *, iquotes_options: tuple[str, ...], compiler: str
228) -> bytes:
229 # `iquotes_options` must be a tuple to use `lru_cache`
231 if shutil.which(compiler) is None: 231 ↛ 232line 231 didn't jump to line 232 because the condition on line 231 was never true
232 raise BundleError(f"command not found: {compiler}")
233 if _check_compiler(compiler) != "gcc": 233 ↛ 234line 233 didn't jump to line 234 because the condition on line 233 was never true
234 if compiler == "g++":
235 raise BundleError(
236 f"A fake g++ is detected. Please install the GNU C++ compiler.: {compiler}"
237 )
238 raise BundleError(
239 f"It's not g++. Please specify g++ with $CXX envvar.: {compiler}"
240 )
241 command = [
242 compiler,
243 "-x",
244 "c++",
245 *iquotes_options,
246 "-fpreprocessed",
247 "-dD",
248 "-E",
249 str(path),
250 ]
251 return command_stdout(command, text=False)
254def get_uncommented_code(
255 path: pathlib.Path, *, iquotes: list[pathlib.Path], compiler: str
256) -> bytes:
257 iquotes_options: list[str] = []
258 for iquote in iquotes:
259 iquotes_options.extend(["-I", str(iquote.resolve())])
260 code = _get_uncommented_code(
261 path.resolve(), iquotes_options=tuple(iquotes_options), compiler=compiler
262 )
263 lines: list[bytes] = []
264 for line in code.splitlines(keepends=True):
265 m = re.match(rb'# (\d+) ".*"', line.rstrip())
266 if m:
267 lineno = int(m.group(1))
268 while len(lines) + 1 < lineno: 268 ↛ 269line 268 didn't jump to line 269 because the condition on line 268 was never true
269 lines.append(b"\n")
270 else:
271 lines.append(line)
272 return b"".join(lines)
275class BundleError(Exception):
276 pass
279class BundleErrorAt(BundleError): # noqa: N818
280 def __init__(
281 self, path: pathlib.Path, line: int, message: str, *args: Any, **kwargs: Any
282 ):
283 with contextlib.suppress(ValueError):
284 path = path.resolve().relative_to(pathlib.Path.cwd())
285 message = f"{path!s}: line {line}: {message}"
286 super().__init__(message, *args, **kwargs)
289class Bundler:
290 iquotes: list[pathlib.Path]
291 pragma_once: set[pathlib.Path]
292 pragma_once_system: set[str]
293 result_lines: list[bytes]
294 path_stack: set[pathlib.Path]
295 compiler: str
297 def __init__(
298 self,
299 *,
300 iquotes: list[pathlib.Path] | None = None,
301 compiler: str = os.environ.get("CXX", "g++"),
302 ) -> None:
303 if iquotes is None: 303 ↛ 304line 303 didn't jump to line 304 because the condition on line 303 was never true
304 iquotes = []
305 self.iquotes = iquotes
306 self.pragma_once = set()
307 self.pragma_once_system = set()
308 self.result_lines = []
309 self.path_stack = set()
310 self.compiler = compiler
312 # これをしないと __FILE__ や __LINE__ が壊れる
313 def _line(self, line: int, path: pathlib.Path) -> None:
314 while self.result_lines and self.result_lines[-1].startswith(b"#line "):
315 self.result_lines.pop()
316 with contextlib.suppress(ValueError):
317 path = path.relative_to(pathlib.Path.cwd())
318 # パス中の特殊文字を JSON style にエスケープしてから生成コードに記述
319 # quick solution to this: https://github.com/online-judge-tools/verification-helper/issues/280
320 self.result_lines.append(f"#line {line} {json.dumps(str(path))}\n".encode())
322 # path を解決する
323 # see: https://gcc.gnu.org/onlinedocs/gcc/Directory-Options.html#Directory-Options
324 def _resolve(
325 self, path: pathlib.Path, *, included_from: pathlib.Path
326 ) -> pathlib.Path:
327 if (included_from.parent / path).exists(): 327 ↛ 329line 327 didn't jump to line 329 because the condition on line 327 was always true
328 return (included_from.parent / path).resolve()
329 for dir_ in self.iquotes:
330 if (dir_ / path).exists():
331 return (dir_ / path).resolve()
332 raise BundleErrorAt(path, -1, "no such header")
334 def update(self, path: pathlib.Path) -> None:
335 if path.resolve() in self.pragma_once: 335 ↛ 336line 335 didn't jump to line 336 because the condition on line 335 was never true
336 logger.debug(
337 "%s: skipped since this file is included once with include guard",
338 path,
339 )
340 return
342 # 再帰的に自分自身を #include してたら諦める
343 if path in self.path_stack: 343 ↛ 344line 343 didn't jump to line 344 because the condition on line 343 was never true
344 raise BundleErrorAt(path, -1, "cycle found in inclusion relations")
345 self.path_stack.add(path)
346 try:
347 code = path.read_bytes()
348 if not code.endswith(b"\n"): 348 ↛ 350line 348 didn't jump to line 350 because the condition on line 348 was never true
349 # ファイルの末尾に改行がなかったら足す
350 code += b"\n"
352 # include guard のまわりの変数
353 # NOTE: include guard に使われたマクロがそれ以外の用途にも使われたり #undef されたりすると壊れるけど、無視します
354 non_guard_line_found = False
355 pragma_once_found = False
356 include_guard_macro = None
357 include_guard_define_found = False
358 include_guard_endif_found = False
359 preprocess_if_nest = 0
361 lines = code.splitlines(keepends=True)
362 uncommented_lines = get_uncommented_code(
363 path, iquotes=self.iquotes, compiler=self.compiler
364 ).splitlines(keepends=True)
365 uncommented_lines.extend(
366 [b""] * (len(lines) - len(uncommented_lines))
367 ) # trailing comment lines are removed
368 assert len(lines) == len(uncommented_lines)
369 self._line(1, path)
370 for i, (line, uncommented_line) in enumerate(
371 zip(lines, uncommented_lines, strict=False)
372 ):
373 # nest の処理
374 if re.match(rb"\s*#\s*(if|ifdef|ifndef)\s.*", uncommented_line):
375 preprocess_if_nest += 1
376 if ( 376 ↛ 380line 376 didn't jump to line 380 because the condition on line 376 was never true
377 re.match(rb"\s*#\s*(else\s*|elif\s.*)", uncommented_line)
378 and preprocess_if_nest == 0
379 ):
380 raise BundleErrorAt(path, i + 1, "unmatched #else / #elif")
381 if re.match(rb"\s*#\s*endif\s*", uncommented_line):
382 preprocess_if_nest -= 1
383 if preprocess_if_nest < 0: 383 ↛ 384line 383 didn't jump to line 384 because the condition on line 383 was never true
384 raise BundleErrorAt(path, i + 1, "unmatched #endif")
385 is_toplevel = preprocess_if_nest == 0 or (
386 preprocess_if_nest == 1 and include_guard_macro is not None
387 )
389 # #pragma once
390 if re.match(
391 rb"\s*#\s*pragma\s+once\s*", line
392 ): # #pragma once は comment 扱いで消されてしまう
393 logger.debug("%s: line %s: #pragma once", path, i + 1)
394 if non_guard_line_found: 394 ↛ 396line 394 didn't jump to line 396 because the condition on line 394 was never true
395 # 先頭以外で #pragma once されてた場合は諦める
396 raise BundleErrorAt(
397 path, i + 1, "#pragma once found in a non-first line"
398 )
399 if include_guard_macro is not None: 399 ↛ 400line 399 didn't jump to line 400 because the condition on line 399 was never true
400 raise BundleErrorAt(
401 path,
402 i + 1,
403 "#pragma once found in an include guard with #ifndef",
404 )
405 if path.resolve() in self.pragma_once: 405 ↛ 406line 405 didn't jump to line 406 because the condition on line 405 was never true
406 return
407 pragma_once_found = True
408 self.pragma_once.add(path.resolve())
409 self._line(i + 2, path)
410 continue
412 matched: re.Match[bytes] | None
413 # #ifndef HOGE_H as guard
414 if (
415 not pragma_once_found
416 and not non_guard_line_found
417 and include_guard_macro is None
418 ):
419 matched = re.match(rb"\s*#\s*ifndef\s+(\w+)\s*", uncommented_line)
420 if matched:
421 include_guard_macro = matched.group(1).decode()
422 logger.debug(
423 "%s: line %s: #ifndef %s",
424 path,
425 i + 1,
426 include_guard_macro,
427 )
428 self.result_lines.append(b"\n")
429 continue
431 # #define HOGE_H as guard
432 if include_guard_macro is not None and not include_guard_define_found:
433 matched = re.match(rb"\s*#\s*define\s+(\w+)\s*", uncommented_line)
434 if matched and matched.group(1).decode() == include_guard_macro: 434 ↛ 447line 434 didn't jump to line 447 because the condition on line 434 was always true
435 self.pragma_once.add(path.resolve())
436 logger.debug(
437 "%s: line %s: #define %s",
438 path,
439 i + 1,
440 include_guard_macro,
441 )
442 include_guard_define_found = True
443 self.result_lines.append(b"\n")
444 continue
446 # #endif as guard
447 if (
448 include_guard_define_found
449 and preprocess_if_nest == 0
450 and not include_guard_endif_found
451 ) and re.match(rb"\s*#\s*endif\s*", uncommented_line):
452 include_guard_endif_found = True
453 self.result_lines.append(b"\n")
454 continue
456 if uncommented_line and not re.match(rb"^\s*$", uncommented_line):
457 non_guard_line_found = True
458 if ( 458 ↛ 463line 458 didn't jump to line 463 because the condition on line 458 was never true
459 include_guard_macro is not None
460 and not include_guard_define_found
461 ):
462 # 先頭に #ifndef が見付かっても #define が続かないならそれは include guard ではない
463 include_guard_macro = None
464 if include_guard_endif_found: 464 ↛ 466line 464 didn't jump to line 466 because the condition on line 464 was never true
465 # include guard の外側にコードが書かれているとまずいので検出する
466 raise BundleErrorAt(
467 path, i + 1, "found codes out of include guard"
468 )
470 # #include <...>
471 matched = re.match(rb"\s*#\s*include\s*<(.*)>\s*", uncommented_line)
472 if matched:
473 included = matched.group(1).decode()
474 logger.debug(
475 "%s: line %s: #include <%s>", path, i + 1, str(included)
476 )
477 if included in self.pragma_once_system: 477 ↛ 478line 477 didn't jump to line 478 because the condition on line 477 was never true
478 self._line(i + 2, path)
479 elif not is_toplevel: 479 ↛ 481line 479 didn't jump to line 481 because the condition on line 479 was never true
480 # #pragma once 系の判断ができない場合はそっとしておく
481 self.result_lines.append(line)
482 elif ( 482 ↛ 492line 482 didn't jump to line 492 because the condition on line 482 was always true
483 included in C_STANDARD_LIBS
484 or included in CXX_STANDARD_LIBS
485 or included in CXX_C_ORIGIN_LIBS
486 ):
487 if BITS_STDCXX_H in self.pragma_once_system: 487 ↛ 488line 487 didn't jump to line 488 because the condition on line 487 was never true
488 self._line(i + 2, path)
489 else:
490 self.pragma_once_system.add(included)
491 self.result_lines.append(line)
492 elif included in EXT_LIBS:
493 if BITS_EXTCXX_H in self.pragma_once_system:
494 self._line(i + 2, path)
495 else:
496 self.pragma_once_system.add(included)
497 self.result_lines.append(line)
498 elif included in TR1_LIBS:
499 if BITS_STDTR1CXX_H in self.pragma_once_system:
500 self._line(i + 2, path)
501 else:
502 self.pragma_once_system.add(included)
503 self.result_lines.append(line)
504 else:
505 # possibly: bits/*, tr2/* boost/*, c-posix library, etc.
506 self.pragma_once_system.add(included)
507 self.result_lines.append(line)
508 if included in [BITS_EXTCXX_H, BITS_STDTR1CXX_H]:
509 self.pragma_once_system.add(BITS_STDCXX_H)
510 continue
512 # #include "..."
513 matched = re.match(rb'\s*#\s*include\s*"(.*)"\s*', uncommented_line)
514 if matched:
515 included = matched.group(1).decode()
516 logger.debug('%s: line %s: #include "%s"', path, i + 1, included)
517 if not is_toplevel: 517 ↛ 519line 517 didn't jump to line 519 because the condition on line 517 was never true
518 # #if の中から #include されると #pragma once 系の判断が不可能になるので諦める
519 raise BundleErrorAt(
520 path,
521 i + 1,
522 "unable to process #include in #if / #ifdef / #ifndef other than include guards",
523 )
524 self.update(
525 self._resolve(pathlib.Path(included), included_from=path)
526 )
527 self._line(i + 2, path)
528 # #include "iostream" みたいに書いたときの挙動をはっきりさせる
529 # #include <iostream> /* とかをやられた場合を落とす
530 continue
532 # otherwise
533 self.result_lines.append(line)
535 # #if #endif の対応が壊れてたら諦める
536 last_index = i + 1 # pyright: ignore[reportPossiblyUnboundVariable]
538 if preprocess_if_nest != 0: 538 ↛ 539line 538 didn't jump to line 539 because the condition on line 538 was never true
539 raise BundleErrorAt(
540 path, last_index, "unmatched #if / #ifdef / #ifndef"
541 )
542 if include_guard_macro is not None and not include_guard_endif_found: 542 ↛ 543line 542 didn't jump to line 543 because the condition on line 542 was never true
543 raise BundleErrorAt(path, last_index, "unmatched #ifndef")
545 finally:
546 # 中で return することがあるので finally 節に入れておく
547 self.path_stack.remove(path)
549 def get(self) -> bytes:
550 return b"".join(self.result_lines)