Bug 880088 - Introduce check_spidermonkey_style.py, which currently checks SpiderMonkey header and #include hygiene, and some tests for it. code=njn,jorendorff. r=gps.
authorNicholas Nethercote <nnethercote@mozilla.com>
Thu, 27 Jun 2013 19:15:59 -0700
changeset 141353 eb3e049e7558f21c93c771bd66a6d7bec21161ee
parent 141352 abc285ee0cd1a191bb20e1be3d0e89d83fcb6bc6
child 141354 d144ffab454362f834974dc1a1c843dee85212c2
push id1
push userroot
push dateMon, 20 Oct 2014 17:29:22 +0000
reviewersgps
bugs880088
milestone25.0a1
Bug 880088 - Introduce check_spidermonkey_style.py, which currently checks SpiderMonkey header and #include hygiene, and some tests for it. code=njn,jorendorff. r=gps.
config/check_spidermonkey_style.py
js/src/Makefile.in
js/src/config/check_spidermonkey_style.py
js/src/tests/style/BadIncludes.h
js/src/tests/style/BadIncludes2-inl.h
js/src/tests/style/BadIncludes2.h
js/src/tests/style/HeaderCycleA1.h
js/src/tests/style/HeaderCycleA2.h
js/src/tests/style/HeaderCycleA3.h
js/src/tests/style/HeaderCycleB1-inl.h
js/src/tests/style/HeaderCycleB2-inl.h
js/src/tests/style/HeaderCycleB3-inl.h
js/src/tests/style/HeaderCycleB4-inl.h
js/src/tests/style/jsheadercycleB5inlines.h
new file mode 100644
--- /dev/null
+++ b/config/check_spidermonkey_style.py
@@ -0,0 +1,396 @@
+# 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.
+#   - It should be in the vanilla form and have no tokens before/after it so
+#     that GCC and clang can avoid multiple-inclusion.
+#   - 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. "ion/Ion.h", not "Ion.h". 
+#
+# - #includes should use the appropriate form for system headers (<...>) and
+#   local headers ("...").
+#
+# - #includes should be ordered correctly. (XXX: not yet implemented;  see bug
+#   888088)
+#   - Each one should be in the correct section.
+#   - Alphabetical order should be used within sections.
+#   - Sections should be in the right order.
+#----------------------------------------------------------------------------
+
+from __future__ import print_function
+
+import difflib
+import os
+import re
+import subprocess
+import sys
+import traceback
+
+# 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
+]
+
+# 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/sharkctl.h',      # we ignore devtools/ in general
+    'devtools/Instruments.h',   # we ignore devtools/ in general
+    'double-conversion.h',      # strange MFBT case
+    'javascript-trace.h',       # generated in $OBJDIR if HAVE_DTRACE is defined
+    'jsautokw.h',               # generated in $OBJDIR
+    'jsautooplen.h',            # generated in $OBJDIR
+    'jscustomallocator.h',      # provided by embedders;  allowed to be missing
+    'js-config.h',              # generated in $OBJDIR
+    'pratom.h',                 # NSPR
+    'prcvar.h',                 # NSPR
+    'prinit.h',                 # NSPR
+    'prlink.h',                 # NSPR
+    'prlock.h',                 # NSPR
+    'prprf.h',                  # NSPR
+    'prthread.h',               # NSPR
+    'prtypes.h',                # NSPR
+    'selfhosted.out.h',         # generated in $OBJDIR
+    'unicode/locid.h',          # ICU
+    'unicode/numsys.h',         # ICU
+    'unicode/ucal.h',           # ICU
+    'unicode/uclean.h',         # ICU
+    'unicode/ucol.h',           # ICU
+    'unicode/udat.h',           # ICU
+    'unicode/udatpg.h',         # ICU
+    'unicode/uenum.h',          # ICU
+    'unicode/unum.h',           # ICU
+    'unicode/ustring.h',        # ICU
+    'unicode/utypes.h',         # ICU
+    'vtune/VTuneWrapper.h'      # VTune
+])
+
+# 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/BadIncludes2.h:1: error:
+    vanilla header includes an inline-header file "tests/style/BadIncludes2-inl.h"
+
+js/src/tests/style/BadIncludes.h:1: error:
+    the file includes itself
+
+js/src/tests/style/BadIncludes.h:3: 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:4: error:
+    <tests/style/BadIncludes2.h> should be included using
+    the #include "..." form
+
+js/src/tests/style/BadIncludes.h:5: error:
+    "stdio.h" is included using the wrong path;
+    did you forget a prefix, or is the file not yet committed?
+
+(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 != 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 get_all_filenames():
+    """Get a list of all the files in the (Mercurial or Git) repository."""
+    cmds = [['hg', 'manifest'], ['git', 'ls-files']]
+    for cmd in cmds:
+        try:
+            all_filenames = subprocess.check_output(cmd, universal_newlines=True,
+                                                    stderr=subprocess.PIPE).split('\n')
+            return all_filenames
+        except:
+            continue
+    else:
+        raise Exception('failed to run any of the repo manifest commands', cmds)
+
+
+def check_style():
+    # 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"
+    # - "js/public/Vector.h" -> "js/Vector.h"
+    # - "js/src/vm/String.h" -> "vm/String.h"
+
+    mfbt_inclnames = set()      # type: set(inclname)
+    js_names = dict()           # type: dict(filename, inclname)
+
+    # Select the appropriate files.
+    for filename in get_all_filenames():
+        if filename.startswith('mfbt/') and filename.endswith('.h'):
+            inclname = 'mozilla/' + filename[len('mfbt/'):]
+            mfbt_inclnames.add(inclname)
+
+        if filename.startswith('js/public/') and filename.endswith('.h'):
+            inclname = 'js/' + filename[len('js/public/'):]
+            js_names[filename] = inclname
+
+        if filename.startswith('js/src/') and \
+           not filename.startswith(tuple(ignored_js_src_dirs)) and \
+           filename.endswith(('.c', '.cpp', '.h', '.tbl', '.msg')):
+            inclname = filename[len('js/src/'):]
+            js_names[filename] = inclname
+
+    all_inclnames = mfbt_inclnames | set(js_names.values())
+
+    edges = dict()      # type: dict(inclname, set(inclname))
+
+    # We don't care what's inside the MFBT files, but because they are
+    # #included from JS files we have to add them to the inclusion graph.
+    for inclname in mfbt_inclnames:
+        edges[inclname] = set()
+
+    # Process all the JS files.
+    for filename in 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)
+
+            # This script is run in js/src/, so prepend '../../' to get to the root of the Mozilla
+            # source tree.
+            with open(os.path.join('../..', filename)) as f:
+                do_file(filename, inclname, file_kind, f, 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_spider_monkey_style.py expected output',
+                                       tofile='check_spider_monkey_style.py actual output')
+    ok = True
+    for diffline in difflines:
+        ok = False
+        print(diffline, end='')
+
+    return ok
+
+
+def do_file(filename, inclname, file_kind, f, all_inclnames, included_h_inclnames):
+    for linenum, line in enumerate(f, start=1):
+        # Look for a |#include "..."| line.
+        m = re.match(r'\s*#\s*include\s+"([^"]*)"', line)
+        if m is not None:
+            included_inclname = m.group(1)
+
+            if included_inclname not in included_inclnames_to_ignore:
+                included_kind = FileKind.get(included_inclname)
+
+                # Check the #include path has the correct form.
+                if included_inclname not in all_inclnames:
+                    error(filename, linenum,
+                          '"' + included_inclname + '" 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(included_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, linenum,
+                          'vanilla header includes an inline-header file "' + included_inclname + '"')
+
+                # Check a file doesn't #include itself.  (We do this here because the
+                # cycle detection below doesn't detect this case.)
+                if inclname == included_inclname:
+                    error(filename, linenum, 'the file includes itself')
+
+        # Look for a |#include <...>| line.
+        m = re.match(r'\s*#\s*include\s+<([^>]*)>', line)
+        if m is not None:
+            included_inclname = m.group(1)
+
+            # Check it is not a known local file (in which case it's
+            # probably a system header).
+            if included_inclname in included_inclnames_to_ignore or \
+               included_inclname in all_inclnames:
+                error(filename, linenum,
+                      '<' + included_inclname + '> should be included using',
+                      'the #include "..." form')
+
+
+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():
+    ok = check_style()
+
+    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')
+
+    sys.exit(0 if ok else 1)
+
+
+if __name__ == "__main__":
+    main()
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -293,22 +293,25 @@ ifeq ($(MOZ_DEBUG),1)
 endif
 
 ifdef MOZ_VALGRIND
 ifndef MOZ_ASAN
 JITTEST_VALGRIND_FLAG = --valgrind
 endif
 endif
 
+check-style::
+	(cd $(srcdir) && $(PYTHON) config/check_spidermonkey_style.py);
+
 check-jit-test::
 	$(wildcard $(RUN_TEST_PROGRAM)) $(PYTHON) -u $(srcdir)/jit-test/jit_test.py \
 	        --no-slow --no-progress --tinderbox --tbpl $(JITTEST_VALGRIND_FLAG) \
 	        $(DIST)/bin/$(JS_SHELL_NAME)$(BIN_SUFFIX)
 
-check:: check-jit-test
+check:: check-style check-jit-test
 
 # jstests doesn't have a --jitflags option, so we need to loop, updating the
 # exit code (RC) after each invocation.
 # FIXME: MethodJIT doesn't work for 1 test case (bug 644393), so
 # --no-extensions is set to skip that test. Remove as soon as possible.
 check-jstests:
 	RC=0; \
 	for f in `echo "$(JITFLAGS)" | tr ',' '\n'`; \
new file mode 100644
--- /dev/null
+++ b/js/src/config/check_spidermonkey_style.py
@@ -0,0 +1,396 @@
+# 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.
+#   - It should be in the vanilla form and have no tokens before/after it so
+#     that GCC and clang can avoid multiple-inclusion.
+#   - 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. "ion/Ion.h", not "Ion.h". 
+#
+# - #includes should use the appropriate form for system headers (<...>) and
+#   local headers ("...").
+#
+# - #includes should be ordered correctly. (XXX: not yet implemented;  see bug
+#   888088)
+#   - Each one should be in the correct section.
+#   - Alphabetical order should be used within sections.
+#   - Sections should be in the right order.
+#----------------------------------------------------------------------------
+
+from __future__ import print_function
+
+import difflib
+import os
+import re
+import subprocess
+import sys
+import traceback
+
+# 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
+]
+
+# 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/sharkctl.h',      # we ignore devtools/ in general
+    'devtools/Instruments.h',   # we ignore devtools/ in general
+    'double-conversion.h',      # strange MFBT case
+    'javascript-trace.h',       # generated in $OBJDIR if HAVE_DTRACE is defined
+    'jsautokw.h',               # generated in $OBJDIR
+    'jsautooplen.h',            # generated in $OBJDIR
+    'jscustomallocator.h',      # provided by embedders;  allowed to be missing
+    'js-config.h',              # generated in $OBJDIR
+    'pratom.h',                 # NSPR
+    'prcvar.h',                 # NSPR
+    'prinit.h',                 # NSPR
+    'prlink.h',                 # NSPR
+    'prlock.h',                 # NSPR
+    'prprf.h',                  # NSPR
+    'prthread.h',               # NSPR
+    'prtypes.h',                # NSPR
+    'selfhosted.out.h',         # generated in $OBJDIR
+    'unicode/locid.h',          # ICU
+    'unicode/numsys.h',         # ICU
+    'unicode/ucal.h',           # ICU
+    'unicode/uclean.h',         # ICU
+    'unicode/ucol.h',           # ICU
+    'unicode/udat.h',           # ICU
+    'unicode/udatpg.h',         # ICU
+    'unicode/uenum.h',          # ICU
+    'unicode/unum.h',           # ICU
+    'unicode/ustring.h',        # ICU
+    'unicode/utypes.h',         # ICU
+    'vtune/VTuneWrapper.h'      # VTune
+])
+
+# 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/BadIncludes2.h:1: error:
+    vanilla header includes an inline-header file "tests/style/BadIncludes2-inl.h"
+
+js/src/tests/style/BadIncludes.h:1: error:
+    the file includes itself
+
+js/src/tests/style/BadIncludes.h:3: 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:4: error:
+    <tests/style/BadIncludes2.h> should be included using
+    the #include "..." form
+
+js/src/tests/style/BadIncludes.h:5: error:
+    "stdio.h" is included using the wrong path;
+    did you forget a prefix, or is the file not yet committed?
+
+(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 != 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 get_all_filenames():
+    """Get a list of all the files in the (Mercurial or Git) repository."""
+    cmds = [['hg', 'manifest'], ['git', 'ls-files']]
+    for cmd in cmds:
+        try:
+            all_filenames = subprocess.check_output(cmd, universal_newlines=True,
+                                                    stderr=subprocess.PIPE).split('\n')
+            return all_filenames
+        except:
+            continue
+    else:
+        raise Exception('failed to run any of the repo manifest commands', cmds)
+
+
+def check_style():
+    # 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"
+    # - "js/public/Vector.h" -> "js/Vector.h"
+    # - "js/src/vm/String.h" -> "vm/String.h"
+
+    mfbt_inclnames = set()      # type: set(inclname)
+    js_names = dict()           # type: dict(filename, inclname)
+
+    # Select the appropriate files.
+    for filename in get_all_filenames():
+        if filename.startswith('mfbt/') and filename.endswith('.h'):
+            inclname = 'mozilla/' + filename[len('mfbt/'):]
+            mfbt_inclnames.add(inclname)
+
+        if filename.startswith('js/public/') and filename.endswith('.h'):
+            inclname = 'js/' + filename[len('js/public/'):]
+            js_names[filename] = inclname
+
+        if filename.startswith('js/src/') and \
+           not filename.startswith(tuple(ignored_js_src_dirs)) and \
+           filename.endswith(('.c', '.cpp', '.h', '.tbl', '.msg')):
+            inclname = filename[len('js/src/'):]
+            js_names[filename] = inclname
+
+    all_inclnames = mfbt_inclnames | set(js_names.values())
+
+    edges = dict()      # type: dict(inclname, set(inclname))
+
+    # We don't care what's inside the MFBT files, but because they are
+    # #included from JS files we have to add them to the inclusion graph.
+    for inclname in mfbt_inclnames:
+        edges[inclname] = set()
+
+    # Process all the JS files.
+    for filename in 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)
+
+            # This script is run in js/src/, so prepend '../../' to get to the root of the Mozilla
+            # source tree.
+            with open(os.path.join('../..', filename)) as f:
+                do_file(filename, inclname, file_kind, f, 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_spider_monkey_style.py expected output',
+                                       tofile='check_spider_monkey_style.py actual output')
+    ok = True
+    for diffline in difflines:
+        ok = False
+        print(diffline, end='')
+
+    return ok
+
+
+def do_file(filename, inclname, file_kind, f, all_inclnames, included_h_inclnames):
+    for linenum, line in enumerate(f, start=1):
+        # Look for a |#include "..."| line.
+        m = re.match(r'\s*#\s*include\s+"([^"]*)"', line)
+        if m is not None:
+            included_inclname = m.group(1)
+
+            if included_inclname not in included_inclnames_to_ignore:
+                included_kind = FileKind.get(included_inclname)
+
+                # Check the #include path has the correct form.
+                if included_inclname not in all_inclnames:
+                    error(filename, linenum,
+                          '"' + included_inclname + '" 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(included_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, linenum,
+                          'vanilla header includes an inline-header file "' + included_inclname + '"')
+
+                # Check a file doesn't #include itself.  (We do this here because the
+                # cycle detection below doesn't detect this case.)
+                if inclname == included_inclname:
+                    error(filename, linenum, 'the file includes itself')
+
+        # Look for a |#include <...>| line.
+        m = re.match(r'\s*#\s*include\s+<([^>]*)>', line)
+        if m is not None:
+            included_inclname = m.group(1)
+
+            # Check it is not a known local file (in which case it's
+            # probably a system header).
+            if included_inclname in included_inclnames_to_ignore or \
+               included_inclname in all_inclnames:
+                error(filename, linenum,
+                      '<' + included_inclname + '> should be included using',
+                      'the #include "..." form')
+
+
+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():
+    ok = check_style()
+
+    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')
+
+    sys.exit(0 if ok else 1)
+
+
+if __name__ == "__main__":
+    main()
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/BadIncludes.h
@@ -0,0 +1,5 @@
+#include "tests/style/BadIncludes.h"    // bad: self-include
+#include "tests/style/BadIncludes2.h"   // ok
+#include "BadIncludes2.h"               // bad: not a full path
+#include <tests/style/BadIncludes2.h>   // bad: <> form used for local file
+#include "stdio.h"                      // bad: "" form used for system file
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/BadIncludes2-inl.h
@@ -0,0 +1,1 @@
+// (this file is deliberately empty)
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/BadIncludes2.h
@@ -0,0 +1,1 @@
+#include "tests/style/BadIncludes2-inl.h" // bad: vanilla header #includes an inline-header
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/HeaderCycleA1.h
@@ -0,0 +1,1 @@
+#include "tests/style/HeaderCycleA2.h"
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/HeaderCycleA2.h
@@ -0,0 +1,1 @@
+#include "tests/style/HeaderCycleA3.h"
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/HeaderCycleA3.h
@@ -0,0 +1,1 @@
+#include "tests/style/HeaderCycleA1.h"
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/HeaderCycleB1-inl.h
@@ -0,0 +1,1 @@
+#include "tests/style/HeaderCycleB2-inl.h"
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/HeaderCycleB2-inl.h
@@ -0,0 +1,2 @@
+#include "tests/style/HeaderCycleB3-inl.h"
+#include "tests/style/HeaderCycleB4-inl.h"
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/HeaderCycleB3-inl.h
@@ -0,0 +1,1 @@
+#include "tests/style/HeaderCycleB4-inl.h"
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/HeaderCycleB4-inl.h
@@ -0,0 +1,2 @@
+#include "tests/style/HeaderCycleB1-inl.h"
+#include "tests/style/jsheadercycleB5inlines.h"
new file mode 100644
--- /dev/null
+++ b/js/src/tests/style/jsheadercycleB5inlines.h
@@ -0,0 +1,1 @@
+#include "tests/style/HeaderCycleB1-inl.h"