1# vim: set ts=8 sts=4 et sw=4 tw=99: 2# This Source Code Form is subject to the terms of the Mozilla Public 3# License, v. 2.0. If a copy of the MPL was not distributed with this 4# file, You can obtain one at http://mozilla.org/MPL/2.0/. 5 6# ---------------------------------------------------------------------------- 7# This script checks various aspects of SpiderMonkey code style. The current checks are as 8# follows. 9# 10# We check the following things in headers. 11# 12# - No cyclic dependencies. 13# 14# - No normal header should #include a inlines.h/-inl.h file. 15# 16# - #ifndef wrappers should have the right form. (XXX: not yet implemented) 17# - Every header file should have one. 18# - The guard name used should be appropriate for the filename. 19# 20# We check the following things in all files. 21# 22# - #includes should have full paths, e.g. "jit/Ion.h", not "Ion.h". 23# 24# - #includes should use the appropriate form for system headers (<...>) and 25# local headers ("..."). 26# 27# - #includes should be ordered correctly. 28# - Each one should be in the correct section. 29# - Alphabetical order should be used within sections. 30# - Sections should be in the right order. 31# Note that the presence of #if/#endif blocks complicates things, to the 32# point that it's not always clear where a conditionally-compiled #include 33# statement should go, even to a human. Therefore, we check the #include 34# statements within each #if/#endif block (including nested ones) in 35# isolation, but don't try to do any order checking between such blocks. 36# ---------------------------------------------------------------------------- 37 38from __future__ import absolute_import, print_function 39 40import difflib 41import os 42import re 43import sys 44 45# We don't bother checking files in these directories, because they're (a) auxiliary or (b) 46# imported code that doesn't follow our coding style. 47ignored_js_src_dirs = [ 48 "js/src/config/", # auxiliary stuff 49 "js/src/ctypes/libffi/", # imported code 50 "js/src/devtools/", # auxiliary stuff 51 "js/src/editline/", # imported code 52 "js/src/gdb/", # auxiliary stuff 53 "js/src/vtune/", # imported code 54 "js/src/zydis/", # imported code 55] 56 57# We ignore #includes of these files, because they don't follow the usual rules. 58included_inclnames_to_ignore = set( 59 [ 60 "ffi.h", # generated in ctypes/libffi/ 61 "devtools/Instruments.h", # we ignore devtools/ in general 62 "double-conversion/double-conversion.h", # strange MFBT case 63 "javascript-trace.h", # generated in $OBJDIR if HAVE_DTRACE is defined 64 "frontend/ReservedWordsGenerated.h", # generated in $OBJDIR 65 "frontend/smoosh_generated.h", # generated in $OBJDIR 66 "gc/StatsPhasesGenerated.h", # generated in $OBJDIR 67 "gc/StatsPhasesGenerated.inc", # generated in $OBJDIR 68 "jit/AtomicOperationsGenerated.h", # generated in $OBJDIR 69 "jit/CacheIROpsGenerated.h", # generated in $OBJDIR 70 "jit/LIROpsGenerated.h", # generated in $OBJDIR 71 "jit/MIROpsGenerated.h", # generated in $OBJDIR 72 "js/ProfilingCategoryList.h", # comes from mozglue/baseprofiler 73 "jscustomallocator.h", # provided by embedders; allowed to be missing 74 "js-config.h", # generated in $OBJDIR 75 "fdlibm.h", # fdlibm 76 "FuzzerDefs.h", # included without a path 77 "FuzzingInterface.h", # included without a path 78 "mozmemory.h", # included without a path 79 "pratom.h", # NSPR 80 "prcvar.h", # NSPR 81 "prerror.h", # NSPR 82 "prinit.h", # NSPR 83 "prio.h", # NSPR 84 "private/pprio.h", # NSPR 85 "prlink.h", # NSPR 86 "prlock.h", # NSPR 87 "prprf.h", # NSPR 88 "prthread.h", # NSPR 89 "prtypes.h", # NSPR 90 "selfhosted.out.h", # generated in $OBJDIR 91 "shellmoduleloader.out.h", # generated in $OBJDIR 92 "unicode/locid.h", # ICU 93 "unicode/uchar.h", # ICU 94 "unicode/uniset.h", # ICU 95 "unicode/unistr.h", # ICU 96 "unicode/utypes.h", # ICU 97 "vtune/VTuneWrapper.h", # VTune 98 "wasm/WasmIntrinsicGenerated.h", # generated in $OBJDIR" 99 "zydis/ZydisAPI.h", # Zydis 100 ] 101) 102 103deprecated_inclnames = { 104 "mozilla/Unused.h": "Use [[nodiscard]] and (void)expr casts instead.", 105} 106 107# JSAPI functions should be included through headers from js/public instead of 108# using the old, catch-all jsapi.h file. 109deprecated_inclnames_in_header = { 110 "jsapi.h": "Prefer including headers from js/public.", 111} 112 113# Temporary exclusions for files which still need to include jsapi.h. 114deprecated_inclnames_in_header_excludes = { 115 "js/src/vm/Compartment-inl.h", # for JS::InformalValueTypeName 116 "js/src/jsapi-tests/tests.h", # for JS_ValueToSource 117} 118 119# These files have additional constraints on where they are #included, so we 120# ignore #includes of them when checking #include ordering. 121oddly_ordered_inclnames = set( 122 [ 123 "ctypes/typedefs.h", # Included multiple times in the body of ctypes/CTypes.h 124 # Included in the body of frontend/TokenStream.h 125 "frontend/ReservedWordsGenerated.h", 126 "gc/StatsPhasesGenerated.h", # Included in the body of gc/Statistics.h 127 "gc/StatsPhasesGenerated.inc", # Included in the body of gc/Statistics.cpp 128 "psapi.h", # Must be included after "util/WindowsWrapper.h" on Windows 129 "machine/endian.h", # Must be included after <sys/types.h> on BSD 130 "winbase.h", # Must precede other system headers(?) 131 "windef.h", # Must precede other system headers(?) 132 ] 133) 134 135# The files in tests/style/ contain code that fails this checking in various 136# ways. Here is the output we expect. If the actual output differs from 137# this, one of the following must have happened. 138# - New SpiderMonkey code violates one of the checked rules. 139# - The tests/style/ files have changed without expected_output being changed 140# accordingly. 141# - This script has been broken somehow. 142# 143expected_output = """\ 144js/src/tests/style/BadIncludes.h:3: error: 145 the file includes itself 146 147js/src/tests/style/BadIncludes.h:6: error: 148 "BadIncludes2.h" is included using the wrong path; 149 did you forget a prefix, or is the file not yet committed? 150 151js/src/tests/style/BadIncludes.h:8: error: 152 <tests/style/BadIncludes2.h> should be included using 153 the #include "..." form 154 155js/src/tests/style/BadIncludes.h:10: error: 156 "stdio.h" is included using the wrong path; 157 did you forget a prefix, or is the file not yet committed? 158 159js/src/tests/style/BadIncludes.h:12: error: 160 "mozilla/Unused.h" is deprecated: Use [[nodiscard]] and (void)expr casts instead. 161 162js/src/tests/style/BadIncludes2.h:1: error: 163 vanilla header includes an inline-header file "tests/style/BadIncludes2-inl.h" 164 165js/src/tests/style/BadIncludesOrder-inl.h:5:6: error: 166 "vm/JSScript-inl.h" should be included after "vm/Interpreter-inl.h" 167 168js/src/tests/style/BadIncludesOrder-inl.h:6:7: error: 169 "vm/Interpreter-inl.h" should be included after "js/Value.h" 170 171js/src/tests/style/BadIncludesOrder-inl.h:7:8: error: 172 "js/Value.h" should be included after "ds/LifoAlloc.h" 173 174js/src/tests/style/BadIncludesOrder-inl.h:9: error: 175 "jsapi.h" is deprecated: Prefer including headers from js/public. 176 177js/src/tests/style/BadIncludesOrder-inl.h:8:9: error: 178 "ds/LifoAlloc.h" should be included after "jsapi.h" 179 180js/src/tests/style/BadIncludesOrder-inl.h:9:10: error: 181 "jsapi.h" should be included after <stdio.h> 182 183js/src/tests/style/BadIncludesOrder-inl.h:10:11: error: 184 <stdio.h> should be included after "mozilla/HashFunctions.h" 185 186js/src/tests/style/BadIncludesOrder-inl.h:20: error: 187 "jsapi.h" is deprecated: Prefer including headers from js/public. 188 189js/src/tests/style/BadIncludesOrder-inl.h:28:29: error: 190 "vm/JSScript.h" should be included after "vm/JSFunction.h" 191 192(multiple files): error: 193 header files form one or more cycles 194 195 tests/style/HeaderCycleA1.h 196 -> tests/style/HeaderCycleA2.h 197 -> tests/style/HeaderCycleA3.h 198 -> tests/style/HeaderCycleA1.h 199 200 tests/style/HeaderCycleB1-inl.h 201 -> tests/style/HeaderCycleB2-inl.h 202 -> tests/style/HeaderCycleB3-inl.h 203 -> tests/style/HeaderCycleB4-inl.h 204 -> tests/style/HeaderCycleB1-inl.h 205 -> tests/style/jsheadercycleB5inlines.h 206 -> tests/style/HeaderCycleB1-inl.h 207 -> tests/style/HeaderCycleB4-inl.h 208 209""".splitlines( 210 True 211) 212 213actual_output = [] 214 215 216def out(*lines): 217 for line in lines: 218 actual_output.append(line + "\n") 219 220 221def error(filename, linenum, *lines): 222 location = filename 223 if linenum is not None: 224 location += ":" + str(linenum) 225 out(location + ": error:") 226 for line in lines: 227 out(" " + line) 228 out("") 229 230 231class FileKind(object): 232 C = 1 233 CPP = 2 234 INL_H = 3 235 H = 4 236 TBL = 5 237 MSG = 6 238 239 @staticmethod 240 def get(filename): 241 if filename.endswith(".c"): 242 return FileKind.C 243 244 if filename.endswith(".cpp"): 245 return FileKind.CPP 246 247 if filename.endswith(("inlines.h", "-inl.h")): 248 return FileKind.INL_H 249 250 if filename.endswith(".h"): 251 return FileKind.H 252 253 if filename.endswith(".tbl"): 254 return FileKind.TBL 255 256 if filename.endswith(".msg"): 257 return FileKind.MSG 258 259 error(filename, None, "unknown file kind") 260 261 262def check_style(enable_fixup): 263 # We deal with two kinds of name. 264 # - A "filename" is a full path to a file from the repository root. 265 # - An "inclname" is how a file is referred to in a #include statement. 266 # 267 # Examples (filename -> inclname) 268 # - "mfbt/Attributes.h" -> "mozilla/Attributes.h" 269 # - "mozglue/misc/TimeStamp.h -> "mozilla/TimeStamp.h" 270 # - "memory/mozalloc/mozalloc.h -> "mozilla/mozalloc.h" 271 # - "js/public/Vector.h" -> "js/Vector.h" 272 # - "js/src/vm/String.h" -> "vm/String.h" 273 274 non_js_dirnames = ( 275 "mfbt/", 276 "memory/mozalloc/", 277 "mozglue/", 278 "intl/components/", 279 ) # type: tuple(str) 280 non_js_inclnames = set() # type: set(inclname) 281 js_names = dict() # type: dict(filename, inclname) 282 283 # Process files in js/src. 284 js_src_root = os.path.join("js", "src") 285 for dirpath, dirnames, filenames in os.walk(js_src_root): 286 if dirpath == js_src_root: 287 # Skip any subdirectories that contain a config.status file 288 # (likely objdirs). 289 builddirs = [] 290 for dirname in dirnames: 291 path = os.path.join(dirpath, dirname, "config.status") 292 if os.path.isfile(path): 293 builddirs.append(dirname) 294 for dirname in builddirs: 295 dirnames.remove(dirname) 296 for filename in filenames: 297 filepath = os.path.join(dirpath, filename).replace("\\", "/") 298 if not filepath.startswith( 299 tuple(ignored_js_src_dirs) 300 ) and filepath.endswith((".c", ".cpp", ".h", ".tbl", ".msg")): 301 inclname = filepath[len("js/src/") :] 302 js_names[filepath] = inclname 303 304 # Look for header files in directories in non_js_dirnames. 305 for non_js_dir in non_js_dirnames: 306 for dirpath, dirnames, filenames in os.walk(non_js_dir): 307 for filename in filenames: 308 if filename.endswith(".h"): 309 inclname = "mozilla/" + filename 310 if non_js_dir == "intl/components/": 311 inclname = "mozilla/intl/" + filename 312 non_js_inclnames.add(inclname) 313 314 # Look for header files in js/public. 315 js_public_root = os.path.join("js", "public") 316 for dirpath, dirnames, filenames in os.walk(js_public_root): 317 for filename in filenames: 318 if filename.endswith((".h", ".msg")): 319 filepath = os.path.join(dirpath, filename).replace("\\", "/") 320 inclname = "js/" + filepath[len("js/public/") :] 321 js_names[filepath] = inclname 322 323 all_inclnames = non_js_inclnames | set(js_names.values()) 324 325 edges = dict() # type: dict(inclname, set(inclname)) 326 327 # We don't care what's inside the MFBT and MOZALLOC files, but because they 328 # are #included from JS files we have to add them to the inclusion graph. 329 for inclname in non_js_inclnames: 330 edges[inclname] = set() 331 332 # Process all the JS files. 333 for filename in sorted(js_names.keys()): 334 inclname = js_names[filename] 335 file_kind = FileKind.get(filename) 336 if ( 337 file_kind == FileKind.C 338 or file_kind == FileKind.CPP 339 or file_kind == FileKind.H 340 or file_kind == FileKind.INL_H 341 ): 342 included_h_inclnames = set() # type: set(inclname) 343 344 with open(filename, encoding="utf-8") as f: 345 code = read_file(f) 346 347 if enable_fixup: 348 code = code.sorted(inclname) 349 with open(filename, "w") as f: 350 f.write(code.to_source()) 351 352 check_file( 353 filename, inclname, file_kind, code, all_inclnames, included_h_inclnames 354 ) 355 356 edges[inclname] = included_h_inclnames 357 358 find_cycles(all_inclnames, edges) 359 360 # Compare expected and actual output. 361 difflines = difflib.unified_diff( 362 expected_output, 363 actual_output, 364 fromfile="check_spidermonkey_style.py expected output", 365 tofile="check_spidermonkey_style.py actual output", 366 ) 367 ok = True 368 for diffline in difflines: 369 ok = False 370 print(diffline, end="") 371 372 return ok 373 374 375def module_name(name): 376 """Strip the trailing .cpp, .h, inlines.h or -inl.h from a filename.""" 377 378 return ( 379 name.replace("inlines.h", "") 380 .replace("-inl.h", "") 381 .replace(".h", "") 382 .replace(".cpp", "") 383 ) # NOQA: E501 384 385 386def is_module_header(enclosing_inclname, header_inclname): 387 """Determine if an included name is the "module header", i.e. should be 388 first in the file.""" 389 390 module = module_name(enclosing_inclname) 391 392 # Normal case, for example: 393 # module == "vm/Runtime", header_inclname == "vm/Runtime.h". 394 if module == module_name(header_inclname): 395 return True 396 397 # A public header, for example: 398 # 399 # module == "vm/CharacterEncoding", 400 # header_inclname == "js/CharacterEncoding.h" 401 # 402 # or (for implementation files for js/public/*/*.h headers) 403 # 404 # module == "vm/SourceHook", 405 # header_inclname == "js/experimental/SourceHook.h" 406 m = re.match(r"js\/.*?([^\/]+)\.h", header_inclname) 407 if m is not None and module.endswith("/" + m.group(1)): 408 return True 409 410 return False 411 412 413class Include(object): 414 """Important information for a single #include statement.""" 415 416 def __init__(self, include_prefix, inclname, line_suffix, linenum, is_system): 417 self.include_prefix = include_prefix 418 self.line_suffix = line_suffix 419 self.inclname = inclname 420 self.linenum = linenum 421 self.is_system = is_system 422 423 def is_style_relevant(self): 424 # Includes are style-relevant; that is, they're checked by the pairwise 425 # style-checking algorithm in check_file. 426 return True 427 428 def section(self, enclosing_inclname): 429 """Identify which section inclname belongs to. 430 431 The section numbers are as follows. 432 0. Module header (e.g. jsfoo.h or jsfooinlines.h within jsfoo.cpp) 433 1. mozilla/Foo.h 434 2. <foo.h> or <foo> 435 3. jsfoo.h, prmjtime.h, etc 436 4. foo/Bar.h 437 5. jsfooinlines.h 438 6. foo/Bar-inl.h 439 7. non-.h, e.g. *.tbl, *.msg (these can be scattered throughout files) 440 """ 441 442 if self.is_system: 443 return 2 444 445 if not self.inclname.endswith(".h"): 446 return 7 447 448 # A couple of modules have the .h file in js/ and the .cpp file elsewhere and so need 449 # special handling. 450 if is_module_header(enclosing_inclname, self.inclname): 451 return 0 452 453 if "/" in self.inclname: 454 if self.inclname.startswith("mozilla/"): 455 return 1 456 457 if self.inclname.endswith("-inl.h"): 458 return 6 459 460 return 4 461 462 if self.inclname.endswith("inlines.h"): 463 return 5 464 465 return 3 466 467 def quote(self): 468 if self.is_system: 469 return "<" + self.inclname + ">" 470 else: 471 return '"' + self.inclname + '"' 472 473 def sort_key(self, enclosing_inclname): 474 return (self.section(enclosing_inclname), self.inclname.lower()) 475 476 def to_source(self): 477 return self.include_prefix + self.quote() + self.line_suffix + "\n" 478 479 480class CppBlock(object): 481 """C preprocessor block: a whole file or a single #if/#elif/#else block. 482 483 A #if/#endif block is the contents of a #if/#endif (or similar) section. 484 The top-level block, which is not within a #if/#endif pair, is also 485 considered a block. 486 487 Each kid is either an Include (representing a #include), OrdinaryCode, or 488 a nested CppBlock.""" 489 490 def __init__(self, start_line=""): 491 self.start = start_line 492 self.end = "" 493 self.kids = [] 494 495 def is_style_relevant(self): 496 return True 497 498 def append_ordinary_line(self, line): 499 if len(self.kids) == 0 or not isinstance(self.kids[-1], OrdinaryCode): 500 self.kids.append(OrdinaryCode()) 501 self.kids[-1].lines.append(line) 502 503 def style_relevant_kids(self): 504 """Return a list of kids in this block that are style-relevant.""" 505 return [kid for kid in self.kids if kid.is_style_relevant()] 506 507 def sorted(self, enclosing_inclname): 508 """Return a hopefully-sorted copy of this block. Implements --fixup. 509 510 When in doubt, this leaves the code unchanged. 511 """ 512 513 def pretty_sorted_includes(includes): 514 """Return a new list containing the given includes, in order, 515 with blank lines separating sections.""" 516 keys = [inc.sort_key(enclosing_inclname) for inc in includes] 517 if sorted(keys) == keys: 518 return includes # if nothing is out of order, don't touch anything 519 520 output = [] 521 current_section = None 522 for (section, _), inc in sorted(zip(keys, includes)): 523 if current_section is not None and section != current_section: 524 output.append(OrdinaryCode(["\n"])) # blank line 525 output.append(inc) 526 current_section = section 527 return output 528 529 def should_try_to_sort(includes): 530 if "tests/style/BadIncludes" in enclosing_inclname: 531 return False # don't straighten the counterexample 532 if any(inc.inclname in oddly_ordered_inclnames for inc in includes): 533 return False # don't sort batches containing odd includes 534 if includes == sorted( 535 includes, key=lambda inc: inc.sort_key(enclosing_inclname) 536 ): 537 return False # it's already sorted, avoid whitespace-only fixups 538 return True 539 540 # The content of the eventual output of this method. 541 output = [] 542 543 # The current batch of includes to sort. This list only ever contains Include objects 544 # and whitespace OrdinaryCode objects. 545 batch = [] 546 547 def flush_batch(): 548 """Sort the contents of `batch` and move it to `output`.""" 549 550 assert all( 551 isinstance(item, Include) 552 or (isinstance(item, OrdinaryCode) and "".join(item.lines).isspace()) 553 for item in batch 554 ) 555 556 # Here we throw away the blank lines. 557 # `pretty_sorted_includes` puts them back. 558 includes = [] 559 last_include_index = -1 560 for i, item in enumerate(batch): 561 if isinstance(item, Include): 562 includes.append(item) 563 last_include_index = i 564 cutoff = last_include_index + 1 565 566 if should_try_to_sort(includes): 567 output.extend(pretty_sorted_includes(includes) + batch[cutoff:]) 568 else: 569 output.extend(batch) 570 del batch[:] 571 572 for kid in self.kids: 573 if isinstance(kid, CppBlock): 574 flush_batch() 575 output.append(kid.sorted(enclosing_inclname)) 576 elif isinstance(kid, Include): 577 batch.append(kid) 578 else: 579 assert isinstance(kid, OrdinaryCode) 580 if kid.to_source().isspace(): 581 batch.append(kid) 582 else: 583 flush_batch() 584 output.append(kid) 585 flush_batch() 586 587 result = CppBlock() 588 result.start = self.start 589 result.end = self.end 590 result.kids = output 591 return result 592 593 def to_source(self): 594 return self.start + "".join(kid.to_source() for kid in self.kids) + self.end 595 596 597class OrdinaryCode(object): 598 """A list of lines of code that aren't #include/#if/#else/#endif lines.""" 599 600 def __init__(self, lines=None): 601 self.lines = lines if lines is not None else [] 602 603 def is_style_relevant(self): 604 return False 605 606 def to_source(self): 607 return "".join(self.lines) 608 609 610# A "snippet" is one of: 611# 612# * Include - representing an #include line 613# * CppBlock - a whole file or #if/#elif/#else block; contains a list of snippets 614# * OrdinaryCode - representing lines of non-#include-relevant code 615 616 617def read_file(f): 618 block_stack = [CppBlock()] 619 620 # Extract the #include statements as a tree of snippets. 621 for linenum, line in enumerate(f, start=1): 622 if line.lstrip().startswith("#"): 623 # Look for a |#include "..."| line. 624 m = re.match(r'(\s*#\s*include\s+)"([^"]*)"(.*)', line) 625 if m is not None: 626 prefix, inclname, suffix = m.groups() 627 block_stack[-1].kids.append( 628 Include(prefix, inclname, suffix, linenum, is_system=False) 629 ) 630 continue 631 632 # Look for a |#include <...>| line. 633 m = re.match(r"(\s*#\s*include\s+)<([^>]*)>(.*)", line) 634 if m is not None: 635 prefix, inclname, suffix = m.groups() 636 block_stack[-1].kids.append( 637 Include(prefix, inclname, suffix, linenum, is_system=True) 638 ) 639 continue 640 641 # Look for a |#{if,ifdef,ifndef}| line. 642 m = re.match(r"\s*#\s*(if|ifdef|ifndef)\b", line) 643 if m is not None: 644 # Open a new block. 645 new_block = CppBlock(line) 646 block_stack[-1].kids.append(new_block) 647 block_stack.append(new_block) 648 continue 649 650 # Look for a |#{elif,else}| line. 651 m = re.match(r"\s*#\s*(elif|else)\b", line) 652 if m is not None: 653 # Close the current block, and open an adjacent one. 654 block_stack.pop() 655 new_block = CppBlock(line) 656 block_stack[-1].kids.append(new_block) 657 block_stack.append(new_block) 658 continue 659 660 # Look for a |#endif| line. 661 m = re.match(r"\s*#\s*endif\b", line) 662 if m is not None: 663 # Close the current block. 664 block_stack.pop().end = line 665 if len(block_stack) == 0: 666 raise ValueError("#endif without #if at line " + str(linenum)) 667 continue 668 669 # Otherwise, we have an ordinary line. 670 block_stack[-1].append_ordinary_line(line) 671 672 if len(block_stack) > 1: 673 raise ValueError("unmatched #if") 674 return block_stack[-1] 675 676 677def check_file( 678 filename, inclname, file_kind, code, all_inclnames, included_h_inclnames 679): 680 def check_include_statement(include): 681 """Check the style of a single #include statement.""" 682 683 if include.is_system: 684 # Check it is not a known local file (in which case it's probably a system header). 685 if ( 686 include.inclname in included_inclnames_to_ignore 687 or include.inclname in all_inclnames 688 ): 689 error( 690 filename, 691 include.linenum, 692 include.quote() + " should be included using", 693 'the #include "..." form', 694 ) 695 696 else: 697 msg = deprecated_inclnames.get(include.inclname) 698 if msg: 699 error( 700 filename, 701 include.linenum, 702 include.quote() + " is deprecated: " + msg, 703 ) 704 705 if file_kind == FileKind.H or file_kind == FileKind.INL_H: 706 msg = deprecated_inclnames_in_header.get(include.inclname) 707 if msg and filename not in deprecated_inclnames_in_header_excludes: 708 error( 709 filename, 710 include.linenum, 711 include.quote() + " is deprecated: " + msg, 712 ) 713 714 if include.inclname not in included_inclnames_to_ignore: 715 included_kind = FileKind.get(include.inclname) 716 717 # Check the #include path has the correct form. 718 if include.inclname not in all_inclnames: 719 error( 720 filename, 721 include.linenum, 722 include.quote() + " is included using the wrong path;", 723 "did you forget a prefix, or is the file not yet committed?", 724 ) 725 726 # Record inclusions of .h files for cycle detection later. 727 # (Exclude .tbl and .msg files.) 728 elif included_kind == FileKind.H or included_kind == FileKind.INL_H: 729 included_h_inclnames.add(include.inclname) 730 731 # Check a H file doesn't #include an INL_H file. 732 if file_kind == FileKind.H and included_kind == FileKind.INL_H: 733 error( 734 filename, 735 include.linenum, 736 "vanilla header includes an inline-header file " 737 + include.quote(), 738 ) 739 740 # Check a file doesn't #include itself. (We do this here because the cycle 741 # detection below doesn't detect this case.) 742 if inclname == include.inclname: 743 error(filename, include.linenum, "the file includes itself") 744 745 def check_includes_order(include1, include2): 746 """Check the ordering of two #include statements.""" 747 748 if ( 749 include1.inclname in oddly_ordered_inclnames 750 or include2.inclname in oddly_ordered_inclnames 751 ): 752 return 753 754 section1 = include1.section(inclname) 755 section2 = include2.section(inclname) 756 if (section1 > section2) or ( 757 (section1 == section2) 758 and (include1.inclname.lower() > include2.inclname.lower()) 759 ): 760 error( 761 filename, 762 str(include1.linenum) + ":" + str(include2.linenum), 763 include1.quote() + " should be included after " + include2.quote(), 764 ) 765 766 # Check the extracted #include statements, both individually, and the ordering of 767 # adjacent pairs that live in the same block. 768 def pair_traverse(prev, this): 769 if isinstance(this, Include): 770 check_include_statement(this) 771 if isinstance(prev, Include): 772 check_includes_order(prev, this) 773 else: 774 kids = this.style_relevant_kids() 775 for prev2, this2 in zip([None] + kids[0:-1], kids): 776 pair_traverse(prev2, this2) 777 778 pair_traverse(None, code) 779 780 781def find_cycles(all_inclnames, edges): 782 """Find and draw any cycles.""" 783 784 SCCs = tarjan(all_inclnames, edges) 785 786 # The various sorted() calls below ensure the output is deterministic. 787 788 def draw_SCC(c): 789 cset = set(c) 790 drawn = set() 791 792 def draw(v, indent): 793 out(" " * indent + ("-> " if indent else " ") + v) 794 if v in drawn: 795 return 796 drawn.add(v) 797 for succ in sorted(edges[v]): 798 if succ in cset: 799 draw(succ, indent + 1) 800 801 draw(sorted(c)[0], 0) 802 out("") 803 804 have_drawn_an_SCC = False 805 for scc in sorted(SCCs): 806 if len(scc) != 1: 807 if not have_drawn_an_SCC: 808 error("(multiple files)", None, "header files form one or more cycles") 809 have_drawn_an_SCC = True 810 811 draw_SCC(scc) 812 813 814# Tarjan's algorithm for finding the strongly connected components (SCCs) of a graph. 815# https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm 816def tarjan(V, E): 817 vertex_index = {} 818 vertex_lowlink = {} 819 index = 0 820 S = [] 821 all_SCCs = [] 822 823 def strongconnect(v, index): 824 # Set the depth index for v to the smallest unused index 825 vertex_index[v] = index 826 vertex_lowlink[v] = index 827 index += 1 828 S.append(v) 829 830 # Consider successors of v 831 for w in E[v]: 832 if w not in vertex_index: 833 # Successor w has not yet been visited; recurse on it 834 index = strongconnect(w, index) 835 vertex_lowlink[v] = min(vertex_lowlink[v], vertex_lowlink[w]) 836 elif w in S: 837 # Successor w is in stack S and hence in the current SCC 838 vertex_lowlink[v] = min(vertex_lowlink[v], vertex_index[w]) 839 840 # If v is a root node, pop the stack and generate an SCC 841 if vertex_lowlink[v] == vertex_index[v]: 842 i = S.index(v) 843 scc = S[i:] 844 del S[i:] 845 all_SCCs.append(scc) 846 847 return index 848 849 for v in V: 850 if v not in vertex_index: 851 index = strongconnect(v, index) 852 853 return all_SCCs 854 855 856def main(): 857 if sys.argv[1:] == ["--fixup"]: 858 # Sort #include directives in-place. Fixup mode doesn't solve 859 # all possible silliness that the script checks for; it's just a 860 # hack for the common case where renaming a header causes style 861 # errors. 862 fixup = True 863 elif sys.argv[1:] == []: 864 fixup = False 865 else: 866 print( 867 "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | unexpected command " 868 "line options: " + repr(sys.argv[1:]) 869 ) 870 sys.exit(1) 871 872 ok = check_style(fixup) 873 874 if ok: 875 print("TEST-PASS | check_spidermonkey_style.py | ok") 876 else: 877 print( 878 "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | " 879 + "actual output does not match expected output; diff is above." 880 ) 881 print( 882 "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | " 883 + "Hint: If the problem is that you renamed a header, and many #includes " 884 + "are no longer in alphabetical order, commit your work and then try " 885 + "`check_spidermonkey_style.py --fixup`. " 886 + "You need to commit first because --fixup modifies your files in place." 887 ) 888 889 sys.exit(0 if ok else 1) 890 891 892if __name__ == "__main__": 893 main() 894