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