config/check_spidermonkey_style.py

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