summaryrefslogtreecommitdiffstats
path: root/config/check_spidermonkey_style.py
diff options
context:
space:
mode:
Diffstat (limited to 'config/check_spidermonkey_style.py')
-rw-r--r--config/check_spidermonkey_style.py871
1 files changed, 871 insertions, 0 deletions
diff --git a/config/check_spidermonkey_style.py b/config/check_spidermonkey_style.py
new file mode 100644
index 0000000000..41d0866cd3
--- /dev/null
+++ b/config/check_spidermonkey_style.py
@@ -0,0 +1,871 @@
+# vim: set ts=8 sts=4 et sw=4 tw=99:
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+# ----------------------------------------------------------------------------
+# This script checks various aspects of SpiderMonkey code style. The current checks are as
+# follows.
+#
+# We check the following things in headers.
+#
+# - No cyclic dependencies.
+#
+# - No normal header should #include a inlines.h/-inl.h file.
+#
+# - #ifndef wrappers should have the right form. (XXX: not yet implemented)
+# - Every header file should have one.
+# - The guard name used should be appropriate for the filename.
+#
+# We check the following things in all files.
+#
+# - #includes should have full paths, e.g. "jit/Ion.h", not "Ion.h".
+#
+# - #includes should use the appropriate form for system headers (<...>) and
+# local headers ("...").
+#
+# - #includes should be ordered correctly.
+# - Each one should be in the correct section.
+# - Alphabetical order should be used within sections.
+# - Sections should be in the right order.
+# Note that the presence of #if/#endif blocks complicates things, to the
+# point that it's not always clear where a conditionally-compiled #include
+# statement should go, even to a human. Therefore, we check the #include
+# statements within each #if/#endif block (including nested ones) in
+# isolation, but don't try to do any order checking between such blocks.
+# ----------------------------------------------------------------------------
+
+from __future__ import absolute_import, print_function
+
+import difflib
+import os
+import re
+import sys
+
+# We don't bother checking files in these directories, because they're (a) auxiliary or (b)
+# imported code that doesn't follow our coding style.
+ignored_js_src_dirs = [
+ "js/src/config/", # auxiliary stuff
+ "js/src/ctypes/libffi/", # imported code
+ "js/src/devtools/", # auxiliary stuff
+ "js/src/editline/", # imported code
+ "js/src/gdb/", # auxiliary stuff
+ "js/src/vtune/", # imported code
+ "js/src/zydis/", # imported code
+]
+
+# We ignore #includes of these files, because they don't follow the usual rules.
+included_inclnames_to_ignore = set(
+ [
+ "ffi.h", # generated in ctypes/libffi/
+ "devtools/Instruments.h", # we ignore devtools/ in general
+ "double-conversion/double-conversion.h", # strange MFBT case
+ "javascript-trace.h", # generated in $OBJDIR if HAVE_DTRACE is defined
+ "frontend/ReservedWordsGenerated.h", # generated in $OBJDIR
+ "frontend/smoosh_generated.h", # generated in $OBJDIR
+ "gc/StatsPhasesGenerated.h", # generated in $OBJDIR
+ "gc/StatsPhasesGenerated.inc", # generated in $OBJDIR
+ "jit/CacheIROpsGenerated.h", # generated in $OBJDIR
+ "jit/LOpcodesGenerated.h", # generated in $OBJDIR
+ "jit/MOpcodesGenerated.h", # generated in $OBJDIR
+ "js/ProfilingCategoryList.h", # comes from mozglue/baseprofiler
+ "jscustomallocator.h", # provided by embedders; allowed to be missing
+ "js-config.h", # generated in $OBJDIR
+ "fdlibm.h", # fdlibm
+ "FuzzerDefs.h", # included without a path
+ "FuzzingInterface.h", # included without a path
+ "mozmemory.h", # included without a path
+ "pratom.h", # NSPR
+ "prcvar.h", # NSPR
+ "prerror.h", # NSPR
+ "prinit.h", # NSPR
+ "prio.h", # NSPR
+ "private/pprio.h", # NSPR
+ "prlink.h", # NSPR
+ "prlock.h", # NSPR
+ "prprf.h", # NSPR
+ "prthread.h", # NSPR
+ "prtypes.h", # NSPR
+ "selfhosted.out.h", # generated in $OBJDIR
+ "shellmoduleloader.out.h", # generated in $OBJDIR
+ "unicode/basictz.h", # ICU
+ "unicode/locid.h", # ICU
+ "unicode/plurrule.h", # ICU
+ "unicode/putil.h", # ICU
+ "unicode/timezone.h", # ICU
+ "unicode/ucal.h", # ICU
+ "unicode/uchar.h", # ICU
+ "unicode/uclean.h", # ICU
+ "unicode/ucol.h", # ICU
+ "unicode/ucurr.h", # ICU
+ "unicode/udat.h", # ICU
+ "unicode/udata.h", # ICU
+ "unicode/udateintervalformat.h", # ICU
+ "unicode/udatpg.h", # ICU
+ "unicode/udisplaycontext.h", # ICU
+ "unicode/uenum.h", # ICU
+ "unicode/ufieldpositer.h", # ICU
+ "unicode/uformattedvalue.h", # ICU
+ "unicode/ulistformatter.h", # ICU
+ "unicode/uldnames.h", # ICU
+ "unicode/uloc.h", # ICU
+ "unicode/umachine.h", # ICU
+ "unicode/uniset.h", # ICU
+ "unicode/unistr.h", # ICU
+ "unicode/unorm2.h", # ICU
+ "unicode/unum.h", # ICU
+ "unicode/unumberformatter.h", # ICU
+ "unicode/unumsys.h", # ICU
+ "unicode/upluralrules.h", # ICU
+ "unicode/ureldatefmt.h", # ICU
+ "unicode/ures.h", # ICU
+ "unicode/ustring.h", # ICU
+ "unicode/utypes.h", # ICU
+ "unicode/uversion.h", # ICU
+ "vtune/VTuneWrapper.h", # VTune
+ "zydis/ZydisAPI.h", # Zydis
+ ]
+)
+
+# These files have additional constraints on where they are #included, so we
+# ignore #includes of them when checking #include ordering.
+oddly_ordered_inclnames = set(
+ [
+ "ctypes/typedefs.h", # Included multiple times in the body of ctypes/CTypes.h
+ # Included in the body of frontend/TokenStream.h
+ "frontend/ReservedWordsGenerated.h",
+ "gc/StatsPhasesGenerated.h", # Included in the body of gc/Statistics.h
+ "gc/StatsPhasesGenerated.inc", # Included in the body of gc/Statistics.cpp
+ "psapi.h", # Must be included after "util/Windows.h" on Windows
+ "machine/endian.h", # Must be included after <sys/types.h> on BSD
+ "winbase.h", # Must precede other system headers(?)
+ "windef.h", # Must precede other system headers(?)
+ ]
+)
+
+# The files in tests/style/ contain code that fails this checking in various
+# ways. Here is the output we expect. If the actual output differs from
+# this, one of the following must have happened.
+# - New SpiderMonkey code violates one of the checked rules.
+# - The tests/style/ files have changed without expected_output being changed
+# accordingly.
+# - This script has been broken somehow.
+#
+expected_output = """\
+js/src/tests/style/BadIncludes.h:3: error:
+ the file includes itself
+
+js/src/tests/style/BadIncludes.h:6: error:
+ "BadIncludes2.h" is included using the wrong path;
+ did you forget a prefix, or is the file not yet committed?
+
+js/src/tests/style/BadIncludes.h:8: error:
+ <tests/style/BadIncludes2.h> should be included using
+ the #include "..." form
+
+js/src/tests/style/BadIncludes.h:10: error:
+ "stdio.h" is included using the wrong path;
+ did you forget a prefix, or is the file not yet committed?
+
+js/src/tests/style/BadIncludes2.h:1: error:
+ vanilla header includes an inline-header file "tests/style/BadIncludes2-inl.h"
+
+js/src/tests/style/BadIncludesOrder-inl.h:5:6: error:
+ "vm/JSScript-inl.h" should be included after "vm/Interpreter-inl.h"
+
+js/src/tests/style/BadIncludesOrder-inl.h:6:7: error:
+ "vm/Interpreter-inl.h" should be included after "js/Value.h"
+
+js/src/tests/style/BadIncludesOrder-inl.h:7:8: error:
+ "js/Value.h" should be included after "ds/LifoAlloc.h"
+
+js/src/tests/style/BadIncludesOrder-inl.h:8:9: error:
+ "ds/LifoAlloc.h" should be included after "jsapi.h"
+
+js/src/tests/style/BadIncludesOrder-inl.h:9:10: error:
+ "jsapi.h" should be included after <stdio.h>
+
+js/src/tests/style/BadIncludesOrder-inl.h:10:11: error:
+ <stdio.h> should be included after "mozilla/HashFunctions.h"
+
+js/src/tests/style/BadIncludesOrder-inl.h:28:29: error:
+ "vm/JSScript.h" should be included after "vm/JSFunction.h"
+
+(multiple files): error:
+ header files form one or more cycles
+
+ tests/style/HeaderCycleA1.h
+ -> tests/style/HeaderCycleA2.h
+ -> tests/style/HeaderCycleA3.h
+ -> tests/style/HeaderCycleA1.h
+
+ tests/style/HeaderCycleB1-inl.h
+ -> tests/style/HeaderCycleB2-inl.h
+ -> tests/style/HeaderCycleB3-inl.h
+ -> tests/style/HeaderCycleB4-inl.h
+ -> tests/style/HeaderCycleB1-inl.h
+ -> tests/style/jsheadercycleB5inlines.h
+ -> tests/style/HeaderCycleB1-inl.h
+ -> tests/style/HeaderCycleB4-inl.h
+
+""".splitlines(
+ True
+)
+
+actual_output = []
+
+
+def out(*lines):
+ for line in lines:
+ actual_output.append(line + "\n")
+
+
+def error(filename, linenum, *lines):
+ location = filename
+ if linenum is not None:
+ location += ":" + str(linenum)
+ out(location + ": error:")
+ for line in lines:
+ out(" " + line)
+ out("")
+
+
+class FileKind(object):
+ C = 1
+ CPP = 2
+ INL_H = 3
+ H = 4
+ TBL = 5
+ MSG = 6
+
+ @staticmethod
+ def get(filename):
+ if filename.endswith(".c"):
+ return FileKind.C
+
+ if filename.endswith(".cpp"):
+ return FileKind.CPP
+
+ if filename.endswith(("inlines.h", "-inl.h")):
+ return FileKind.INL_H
+
+ if filename.endswith(".h"):
+ return FileKind.H
+
+ if filename.endswith(".tbl"):
+ return FileKind.TBL
+
+ if filename.endswith(".msg"):
+ return FileKind.MSG
+
+ error(filename, None, "unknown file kind")
+
+
+def check_style(enable_fixup):
+ # We deal with two kinds of name.
+ # - A "filename" is a full path to a file from the repository root.
+ # - An "inclname" is how a file is referred to in a #include statement.
+ #
+ # Examples (filename -> inclname)
+ # - "mfbt/Attributes.h" -> "mozilla/Attributes.h"
+ # - "mozglue/misc/TimeStamp.h -> "mozilla/TimeStamp.h"
+ # - "memory/mozalloc/mozalloc.h -> "mozilla/mozalloc.h"
+ # - "js/public/Vector.h" -> "js/Vector.h"
+ # - "js/src/vm/String.h" -> "vm/String.h"
+
+ non_js_dirnames = ("mfbt/", "memory/mozalloc/", "mozglue/") # type: tuple(str)
+ non_js_inclnames = set() # type: set(inclname)
+ js_names = dict() # type: dict(filename, inclname)
+
+ # Process files in js/src.
+ js_src_root = os.path.join("js", "src")
+ for dirpath, dirnames, filenames in os.walk(js_src_root):
+ if dirpath == js_src_root:
+ # Skip any subdirectories that contain a config.status file
+ # (likely objdirs).
+ builddirs = []
+ for dirname in dirnames:
+ path = os.path.join(dirpath, dirname, "config.status")
+ if os.path.isfile(path):
+ builddirs.append(dirname)
+ for dirname in builddirs:
+ dirnames.remove(dirname)
+ for filename in filenames:
+ filepath = os.path.join(dirpath, filename).replace("\\", "/")
+ if not filepath.startswith(
+ tuple(ignored_js_src_dirs)
+ ) and filepath.endswith((".c", ".cpp", ".h", ".tbl", ".msg")):
+ inclname = filepath[len("js/src/") :]
+ js_names[filepath] = inclname
+
+ # Look for header files in directories in non_js_dirnames.
+ for non_js_dir in non_js_dirnames:
+ for dirpath, dirnames, filenames in os.walk(non_js_dir):
+ for filename in filenames:
+ if filename.endswith(".h"):
+ inclname = "mozilla/" + filename
+ non_js_inclnames.add(inclname)
+
+ # Look for header files in js/public.
+ js_public_root = os.path.join("js", "public")
+ for dirpath, dirnames, filenames in os.walk(js_public_root):
+ for filename in filenames:
+ if filename.endswith((".h", ".msg")):
+ filepath = os.path.join(dirpath, filename).replace("\\", "/")
+ inclname = "js/" + filepath[len("js/public/") :]
+ js_names[filepath] = inclname
+
+ all_inclnames = non_js_inclnames | set(js_names.values())
+
+ edges = dict() # type: dict(inclname, set(inclname))
+
+ # We don't care what's inside the MFBT and MOZALLOC files, but because they
+ # are #included from JS files we have to add them to the inclusion graph.
+ for inclname in non_js_inclnames:
+ edges[inclname] = set()
+
+ # Process all the JS files.
+ for filename in sorted(js_names.keys()):
+ inclname = js_names[filename]
+ file_kind = FileKind.get(filename)
+ if (
+ file_kind == FileKind.C
+ or file_kind == FileKind.CPP
+ or file_kind == FileKind.H
+ or file_kind == FileKind.INL_H
+ ):
+ included_h_inclnames = set() # type: set(inclname)
+
+ with open(filename, encoding="utf-8") as f:
+ code = read_file(f)
+
+ if enable_fixup:
+ code = code.sorted(inclname)
+ with open(filename, "w") as f:
+ f.write(code.to_source())
+
+ check_file(
+ filename, inclname, file_kind, code, all_inclnames, included_h_inclnames
+ )
+
+ edges[inclname] = included_h_inclnames
+
+ find_cycles(all_inclnames, edges)
+
+ # Compare expected and actual output.
+ difflines = difflib.unified_diff(
+ expected_output,
+ actual_output,
+ fromfile="check_spidermonkey_style.py expected output",
+ tofile="check_spidermonkey_style.py actual output",
+ )
+ ok = True
+ for diffline in difflines:
+ ok = False
+ print(diffline, end="")
+
+ return ok
+
+
+def module_name(name):
+ """Strip the trailing .cpp, .h, inlines.h or -inl.h from a filename."""
+
+ return (
+ name.replace("inlines.h", "")
+ .replace("-inl.h", "")
+ .replace(".h", "")
+ .replace(".cpp", "")
+ ) # NOQA: E501
+
+
+def is_module_header(enclosing_inclname, header_inclname):
+ """Determine if an included name is the "module header", i.e. should be
+ first in the file."""
+
+ module = module_name(enclosing_inclname)
+
+ # Normal case, for example:
+ # module == "vm/Runtime", header_inclname == "vm/Runtime.h".
+ if module == module_name(header_inclname):
+ return True
+
+ # A public header, for example:
+ #
+ # module == "vm/CharacterEncoding",
+ # header_inclname == "js/CharacterEncoding.h"
+ #
+ # or (for implementation files for js/public/*/*.h headers)
+ #
+ # module == "vm/SourceHook",
+ # header_inclname == "js/experimental/SourceHook.h"
+ m = re.match(r"js\/.*?([^\/]+)\.h", header_inclname)
+ if m is not None and module.endswith("/" + m.group(1)):
+ return True
+
+ return False
+
+
+class Include(object):
+ """Important information for a single #include statement."""
+
+ def __init__(self, include_prefix, inclname, line_suffix, linenum, is_system):
+ self.include_prefix = include_prefix
+ self.line_suffix = line_suffix
+ self.inclname = inclname
+ self.linenum = linenum
+ self.is_system = is_system
+
+ def is_style_relevant(self):
+ # Includes are style-relevant; that is, they're checked by the pairwise
+ # style-checking algorithm in check_file.
+ return True
+
+ def section(self, enclosing_inclname):
+ """Identify which section inclname belongs to.
+
+ The section numbers are as follows.
+ 0. Module header (e.g. jsfoo.h or jsfooinlines.h within jsfoo.cpp)
+ 1. mozilla/Foo.h
+ 2. <foo.h> or <foo>
+ 3. jsfoo.h, prmjtime.h, etc
+ 4. foo/Bar.h
+ 5. jsfooinlines.h
+ 6. foo/Bar-inl.h
+ 7. non-.h, e.g. *.tbl, *.msg (these can be scattered throughout files)
+ """
+
+ if self.is_system:
+ return 2
+
+ if not self.inclname.endswith(".h"):
+ return 7
+
+ # A couple of modules have the .h file in js/ and the .cpp file elsewhere and so need
+ # special handling.
+ if is_module_header(enclosing_inclname, self.inclname):
+ return 0
+
+ if "/" in self.inclname:
+ if self.inclname.startswith("mozilla/"):
+ return 1
+
+ if self.inclname.endswith("-inl.h"):
+ return 6
+
+ return 4
+
+ if self.inclname.endswith("inlines.h"):
+ return 5
+
+ return 3
+
+ def quote(self):
+ if self.is_system:
+ return "<" + self.inclname + ">"
+ else:
+ return '"' + self.inclname + '"'
+
+ def sort_key(self, enclosing_inclname):
+ return (self.section(enclosing_inclname), self.inclname.lower())
+
+ def to_source(self):
+ return self.include_prefix + self.quote() + self.line_suffix + "\n"
+
+
+class CppBlock(object):
+ """C preprocessor block: a whole file or a single #if/#elif/#else block.
+
+ A #if/#endif block is the contents of a #if/#endif (or similar) section.
+ The top-level block, which is not within a #if/#endif pair, is also
+ considered a block.
+
+ Each kid is either an Include (representing a #include), OrdinaryCode, or
+ a nested CppBlock."""
+
+ def __init__(self, start_line=""):
+ self.start = start_line
+ self.end = ""
+ self.kids = []
+
+ def is_style_relevant(self):
+ return True
+
+ def append_ordinary_line(self, line):
+ if len(self.kids) == 0 or not isinstance(self.kids[-1], OrdinaryCode):
+ self.kids.append(OrdinaryCode())
+ self.kids[-1].lines.append(line)
+
+ def style_relevant_kids(self):
+ """ Return a list of kids in this block that are style-relevant. """
+ return [kid for kid in self.kids if kid.is_style_relevant()]
+
+ def sorted(self, enclosing_inclname):
+ """Return a hopefully-sorted copy of this block. Implements --fixup.
+
+ When in doubt, this leaves the code unchanged.
+ """
+
+ def pretty_sorted_includes(includes):
+ """Return a new list containing the given includes, in order,
+ with blank lines separating sections."""
+ keys = [inc.sort_key(enclosing_inclname) for inc in includes]
+ if sorted(keys) == keys:
+ return includes # if nothing is out of order, don't touch anything
+
+ output = []
+ current_section = None
+ for (section, _), inc in sorted(zip(keys, includes)):
+ if current_section is not None and section != current_section:
+ output.append(OrdinaryCode(["\n"])) # blank line
+ output.append(inc)
+ current_section = section
+ return output
+
+ def should_try_to_sort(includes):
+ if "tests/style/BadIncludes" in enclosing_inclname:
+ return False # don't straighten the counterexample
+ if any(inc.inclname in oddly_ordered_inclnames for inc in includes):
+ return False # don't sort batches containing odd includes
+ if includes == sorted(
+ includes, key=lambda inc: inc.sort_key(enclosing_inclname)
+ ):
+ return False # it's already sorted, avoid whitespace-only fixups
+ return True
+
+ # The content of the eventual output of this method.
+ output = []
+
+ # The current batch of includes to sort. This list only ever contains Include objects
+ # and whitespace OrdinaryCode objects.
+ batch = []
+
+ def flush_batch():
+ """Sort the contents of `batch` and move it to `output`."""
+
+ assert all(
+ isinstance(item, Include)
+ or (isinstance(item, OrdinaryCode) and "".join(item.lines).isspace())
+ for item in batch
+ )
+
+ # Here we throw away the blank lines.
+ # `pretty_sorted_includes` puts them back.
+ includes = []
+ last_include_index = -1
+ for i, item in enumerate(batch):
+ if isinstance(item, Include):
+ includes.append(item)
+ last_include_index = i
+ cutoff = last_include_index + 1
+
+ if should_try_to_sort(includes):
+ output.extend(pretty_sorted_includes(includes) + batch[cutoff:])
+ else:
+ output.extend(batch)
+ del batch[:]
+
+ for kid in self.kids:
+ if isinstance(kid, CppBlock):
+ flush_batch()
+ output.append(kid.sorted(enclosing_inclname))
+ elif isinstance(kid, Include):
+ batch.append(kid)
+ else:
+ assert isinstance(kid, OrdinaryCode)
+ if kid.to_source().isspace():
+ batch.append(kid)
+ else:
+ flush_batch()
+ output.append(kid)
+ flush_batch()
+
+ result = CppBlock()
+ result.start = self.start
+ result.end = self.end
+ result.kids = output
+ return result
+
+ def to_source(self):
+ return self.start + "".join(kid.to_source() for kid in self.kids) + self.end
+
+
+class OrdinaryCode(object):
+ """ A list of lines of code that aren't #include/#if/#else/#endif lines. """
+
+ def __init__(self, lines=None):
+ self.lines = lines if lines is not None else []
+
+ def is_style_relevant(self):
+ return False
+
+ def to_source(self):
+ return "".join(self.lines)
+
+
+# A "snippet" is one of:
+#
+# * Include - representing an #include line
+# * CppBlock - a whole file or #if/#elif/#else block; contains a list of snippets
+# * OrdinaryCode - representing lines of non-#include-relevant code
+
+
+def read_file(f):
+ block_stack = [CppBlock()]
+
+ # Extract the #include statements as a tree of snippets.
+ for linenum, line in enumerate(f, start=1):
+ if line.lstrip().startswith("#"):
+ # Look for a |#include "..."| line.
+ m = re.match(r'(\s*#\s*include\s+)"([^"]*)"(.*)', line)
+ if m is not None:
+ prefix, inclname, suffix = m.groups()
+ block_stack[-1].kids.append(
+ Include(prefix, inclname, suffix, linenum, is_system=False)
+ )
+ continue
+
+ # Look for a |#include <...>| line.
+ m = re.match(r"(\s*#\s*include\s+)<([^>]*)>(.*)", line)
+ if m is not None:
+ prefix, inclname, suffix = m.groups()
+ block_stack[-1].kids.append(
+ Include(prefix, inclname, suffix, linenum, is_system=True)
+ )
+ continue
+
+ # Look for a |#{if,ifdef,ifndef}| line.
+ m = re.match(r"\s*#\s*(if|ifdef|ifndef)\b", line)
+ if m is not None:
+ # Open a new block.
+ new_block = CppBlock(line)
+ block_stack[-1].kids.append(new_block)
+ block_stack.append(new_block)
+ continue
+
+ # Look for a |#{elif,else}| line.
+ m = re.match(r"\s*#\s*(elif|else)\b", line)
+ if m is not None:
+ # Close the current block, and open an adjacent one.
+ block_stack.pop()
+ new_block = CppBlock(line)
+ block_stack[-1].kids.append(new_block)
+ block_stack.append(new_block)
+ continue
+
+ # Look for a |#endif| line.
+ m = re.match(r"\s*#\s*endif\b", line)
+ if m is not None:
+ # Close the current block.
+ block_stack.pop().end = line
+ if len(block_stack) == 0:
+ raise ValueError("#endif without #if at line " + str(linenum))
+ continue
+
+ # Otherwise, we have an ordinary line.
+ block_stack[-1].append_ordinary_line(line)
+
+ if len(block_stack) > 1:
+ raise ValueError("unmatched #if")
+ return block_stack[-1]
+
+
+def check_file(
+ filename, inclname, file_kind, code, all_inclnames, included_h_inclnames
+):
+ def check_include_statement(include):
+ """Check the style of a single #include statement."""
+
+ if include.is_system:
+ # Check it is not a known local file (in which case it's probably a system header).
+ if (
+ include.inclname in included_inclnames_to_ignore
+ or include.inclname in all_inclnames
+ ):
+ error(
+ filename,
+ include.linenum,
+ include.quote() + " should be included using",
+ 'the #include "..." form',
+ )
+
+ else:
+ if include.inclname not in included_inclnames_to_ignore:
+ included_kind = FileKind.get(include.inclname)
+
+ # Check the #include path has the correct form.
+ if include.inclname not in all_inclnames:
+ error(
+ filename,
+ include.linenum,
+ include.quote() + " is included using the wrong path;",
+ "did you forget a prefix, or is the file not yet committed?",
+ )
+
+ # Record inclusions of .h files for cycle detection later.
+ # (Exclude .tbl and .msg files.)
+ elif included_kind == FileKind.H or included_kind == FileKind.INL_H:
+ included_h_inclnames.add(include.inclname)
+
+ # Check a H file doesn't #include an INL_H file.
+ if file_kind == FileKind.H and included_kind == FileKind.INL_H:
+ error(
+ filename,
+ include.linenum,
+ "vanilla header includes an inline-header file "
+ + include.quote(),
+ )
+
+ # Check a file doesn't #include itself. (We do this here because the cycle
+ # detection below doesn't detect this case.)
+ if inclname == include.inclname:
+ error(filename, include.linenum, "the file includes itself")
+
+ def check_includes_order(include1, include2):
+ """Check the ordering of two #include statements."""
+
+ if (
+ include1.inclname in oddly_ordered_inclnames
+ or include2.inclname in oddly_ordered_inclnames
+ ):
+ return
+
+ section1 = include1.section(inclname)
+ section2 = include2.section(inclname)
+ if (section1 > section2) or (
+ (section1 == section2)
+ and (include1.inclname.lower() > include2.inclname.lower())
+ ):
+ error(
+ filename,
+ str(include1.linenum) + ":" + str(include2.linenum),
+ include1.quote() + " should be included after " + include2.quote(),
+ )
+
+ # Check the extracted #include statements, both individually, and the ordering of
+ # adjacent pairs that live in the same block.
+ def pair_traverse(prev, this):
+ if isinstance(this, Include):
+ check_include_statement(this)
+ if isinstance(prev, Include):
+ check_includes_order(prev, this)
+ else:
+ kids = this.style_relevant_kids()
+ for prev2, this2 in zip([None] + kids[0:-1], kids):
+ pair_traverse(prev2, this2)
+
+ pair_traverse(None, code)
+
+
+def find_cycles(all_inclnames, edges):
+ """Find and draw any cycles."""
+
+ SCCs = tarjan(all_inclnames, edges)
+
+ # The various sorted() calls below ensure the output is deterministic.
+
+ def draw_SCC(c):
+ cset = set(c)
+ drawn = set()
+
+ def draw(v, indent):
+ out(" " * indent + ("-> " if indent else " ") + v)
+ if v in drawn:
+ return
+ drawn.add(v)
+ for succ in sorted(edges[v]):
+ if succ in cset:
+ draw(succ, indent + 1)
+
+ draw(sorted(c)[0], 0)
+ out("")
+
+ have_drawn_an_SCC = False
+ for scc in sorted(SCCs):
+ if len(scc) != 1:
+ if not have_drawn_an_SCC:
+ error("(multiple files)", None, "header files form one or more cycles")
+ have_drawn_an_SCC = True
+
+ draw_SCC(scc)
+
+
+# Tarjan's algorithm for finding the strongly connected components (SCCs) of a graph.
+# https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
+def tarjan(V, E):
+ vertex_index = {}
+ vertex_lowlink = {}
+ index = 0
+ S = []
+ all_SCCs = []
+
+ def strongconnect(v, index):
+ # Set the depth index for v to the smallest unused index
+ vertex_index[v] = index
+ vertex_lowlink[v] = index
+ index += 1
+ S.append(v)
+
+ # Consider successors of v
+ for w in E[v]:
+ if w not in vertex_index:
+ # Successor w has not yet been visited; recurse on it
+ index = strongconnect(w, index)
+ vertex_lowlink[v] = min(vertex_lowlink[v], vertex_lowlink[w])
+ elif w in S:
+ # Successor w is in stack S and hence in the current SCC
+ vertex_lowlink[v] = min(vertex_lowlink[v], vertex_index[w])
+
+ # If v is a root node, pop the stack and generate an SCC
+ if vertex_lowlink[v] == vertex_index[v]:
+ i = S.index(v)
+ scc = S[i:]
+ del S[i:]
+ all_SCCs.append(scc)
+
+ return index
+
+ for v in V:
+ if v not in vertex_index:
+ index = strongconnect(v, index)
+
+ return all_SCCs
+
+
+def main():
+ if sys.argv[1:] == ["--fixup"]:
+ # Sort #include directives in-place. Fixup mode doesn't solve
+ # all possible silliness that the script checks for; it's just a
+ # hack for the common case where renaming a header causes style
+ # errors.
+ fixup = True
+ elif sys.argv[1:] == []:
+ fixup = False
+ else:
+ print(
+ "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | unexpected command "
+ "line options: " + repr(sys.argv[1:])
+ )
+ sys.exit(1)
+
+ ok = check_style(fixup)
+
+ if ok:
+ print("TEST-PASS | check_spidermonkey_style.py | ok")
+ else:
+ print(
+ "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | "
+ + "actual output does not match expected output; diff is above."
+ )
+ print(
+ "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | "
+ + "Hint: If the problem is that you renamed a header, and many #includes "
+ + "are no longer in alphabetical order, commit your work and then try "
+ + "`check_spidermonkey_style.py --fixup`. "
+ + "You need to commit first because --fixup modifies your files in place."
+ )
+
+ sys.exit(0 if ok else 1)
+
+
+if __name__ == "__main__":
+ main()