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