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/.
6 # ----------------------------------------------------------------------------
7 # This script checks various aspects of SpiderMonkey code style. The current checks are as
10 # We check the following things in headers.
12 # - No cyclic dependencies.
14 # - No normal header should #include a inlines.h/-inl.h file.
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.
20 # We check the following things in all files.
22 # - #includes should have full paths, e.g. "jit/Ion.h", not "Ion.h".
24 # - #includes should use the appropriate form for system headers (<...>) and
25 # local headers ("...").
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 # ----------------------------------------------------------------------------
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
55 # We ignore #includes of these files, because they don't follow the usual rules.
56 included_inclnames_to_ignore
= set(
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/ProfilingCategoryList.h", # comes from mozglue/baseprofiler
72 "jscustomallocator.h", # provided by embedders; allowed to be missing
73 "js-config.h", # generated in $OBJDIR
75 "FuzzerDefs.h", # included without a path
76 "FuzzingInterface.h", # included without a path
77 "mozmemory.h", # included without a path
83 "private/pprio.h", # NSPR
89 "selfhosted.out.h", # generated in $OBJDIR
90 "shellmoduleloader.out.h", # generated in $OBJDIR
91 "unicode/locid.h", # ICU
92 "unicode/uchar.h", # ICU
93 "unicode/uniset.h", # ICU
94 "unicode/unistr.h", # ICU
95 "unicode/utypes.h", # ICU
96 "vtune/VTuneWrapper.h", # VTune
97 "wasm/WasmBuiltinModuleGenerated.h", # generated in $OBJDIR"
98 "zydis/ZydisAPI.h", # Zydis
102 deprecated_inclnames
= {
103 "mozilla/Unused.h": "Use [[nodiscard]] and (void)expr casts instead.",
106 # JSAPI functions should be included through headers from js/public instead of
107 # using the old, catch-all jsapi.h file.
108 deprecated_inclnames_in_header
= {
109 "jsapi.h": "Prefer including headers from js/public.",
112 # Temporary exclusions for files which still need to include jsapi.h.
113 deprecated_inclnames_in_header_excludes
= {
114 "js/src/vm/Compartment-inl.h", # for JS::InformalValueTypeName
115 "js/src/jsapi-tests/tests.h", # for JS_ValueToSource
118 # These files have additional constraints on where they are #included, so we
119 # ignore #includes of them when checking #include ordering.
120 oddly_ordered_inclnames
= set(
122 "ctypes/typedefs.h", # Included multiple times in the body of ctypes/CTypes.h
123 # Included in the body of frontend/TokenStream.h
124 "frontend/ReservedWordsGenerated.h",
125 "gc/StatsPhasesGenerated.h", # Included in the body of gc/Statistics.h
126 "gc/StatsPhasesGenerated.inc", # Included in the body of gc/Statistics.cpp
127 "psapi.h", # Must be included after "util/WindowsWrapper.h" on Windows
128 "machine/endian.h", # Must be included after <sys/types.h> on BSD
129 "process.h", # Windows-specific
130 "winbase.h", # Must precede other system headers(?)
131 "windef.h", # Must precede other system headers(?)
132 "windows.h", # Must precede other system headers(?)
136 # The files in tests/style/ contain code that fails this checking in various
137 # ways. Here is the output we expect. If the actual output differs from
138 # this, one of the following must have happened.
139 # - New SpiderMonkey code violates one of the checked rules.
140 # - The tests/style/ files have changed without expected_output being changed
142 # - This script has been broken somehow.
144 expected_output
= """\
145 js/src/tests/style/BadIncludes.h:3: error:
146 the file includes itself
148 js/src/tests/style/BadIncludes.h:6: error:
149 "BadIncludes2.h" is included using the wrong path;
150 did you forget a prefix, or is the file not yet committed?
152 js/src/tests/style/BadIncludes.h:8: error:
153 <tests/style/BadIncludes2.h> should be included using
154 the #include "..." form
156 js/src/tests/style/BadIncludes.h:10: error:
157 "stdio.h" is included using the wrong path;
158 did you forget a prefix, or is the file not yet committed?
160 js/src/tests/style/BadIncludes.h:12: error:
161 "mozilla/Unused.h" is deprecated: Use [[nodiscard]] and (void)expr casts instead.
163 js/src/tests/style/BadIncludes2.h:1: error:
164 vanilla header includes an inline-header file "tests/style/BadIncludes2-inl.h"
166 js/src/tests/style/BadIncludesOrder-inl.h:5:6: error:
167 "vm/JSScript-inl.h" should be included after "vm/Interpreter-inl.h"
169 js/src/tests/style/BadIncludesOrder-inl.h:6:7: error:
170 "vm/Interpreter-inl.h" should be included after "js/Value.h"
172 js/src/tests/style/BadIncludesOrder-inl.h:7:8: error:
173 "js/Value.h" should be included after "ds/LifoAlloc.h"
175 js/src/tests/style/BadIncludesOrder-inl.h:9: error:
176 "jsapi.h" is deprecated: Prefer including headers from js/public.
178 js/src/tests/style/BadIncludesOrder-inl.h:8:9: error:
179 "ds/LifoAlloc.h" should be included after "jsapi.h"
181 js/src/tests/style/BadIncludesOrder-inl.h:9:10: error:
182 "jsapi.h" should be included after <stdio.h>
184 js/src/tests/style/BadIncludesOrder-inl.h:10:11: error:
185 <stdio.h> should be included after "mozilla/HashFunctions.h"
187 js/src/tests/style/BadIncludesOrder-inl.h:20: error:
188 "jsapi.h" is deprecated: Prefer including headers from js/public.
190 js/src/tests/style/BadIncludesOrder-inl.h:28:29: error:
191 "vm/JSScript.h" should be included after "vm/JSFunction.h"
193 (multiple files): error:
194 header files form one or more cycles
196 tests/style/HeaderCycleA1.h
197 -> tests/style/HeaderCycleA2.h
198 -> tests/style/HeaderCycleA3.h
199 -> tests/style/HeaderCycleA1.h
201 tests/style/HeaderCycleB1-inl.h
202 -> tests/style/HeaderCycleB2-inl.h
203 -> tests/style/HeaderCycleB3-inl.h
204 -> tests/style/HeaderCycleB4-inl.h
205 -> tests/style/HeaderCycleB1-inl.h
206 -> tests/style/jsheadercycleB5inlines.h
207 -> tests/style/HeaderCycleB1-inl.h
208 -> tests/style/HeaderCycleB4-inl.h
219 actual_output
.append(line
+ "\n")
222 def error(filename
, linenum
, *lines
):
224 if linenum
is not None:
225 location
+= ":" + str(linenum
)
226 out(location
+ ": error:")
232 class FileKind(object):
242 if filename
.endswith(".c"):
245 if filename
.endswith(".cpp"):
248 if filename
.endswith(("inlines.h", "-inl.h")):
249 return FileKind
.INL_H
251 if filename
.endswith(".h"):
254 if filename
.endswith(".tbl"):
257 if filename
.endswith(".msg"):
260 error(filename
, None, "unknown file kind")
263 def check_style(enable_fixup
):
264 # We deal with two kinds of name.
265 # - A "filename" is a full path to a file from the repository root.
266 # - An "inclname" is how a file is referred to in a #include statement.
268 # Examples (filename -> inclname)
269 # - "mfbt/Attributes.h" -> "mozilla/Attributes.h"
270 # - "mozglue/misc/TimeStamp.h -> "mozilla/TimeStamp.h"
271 # - "memory/mozalloc/mozalloc.h -> "mozilla/mozalloc.h"
272 # - "js/public/Vector.h" -> "js/Vector.h"
273 # - "js/src/vm/String.h" -> "vm/String.h"
281 non_js_inclnames
= set() # type: set(inclname)
282 js_names
= dict() # type: dict(filename, inclname)
284 # Process files in js/src.
285 js_src_root
= os
.path
.join("js", "src")
286 for dirpath
, dirnames
, filenames
in os
.walk(js_src_root
):
287 if dirpath
== js_src_root
:
288 # Skip any subdirectories that contain a config.status file
291 for dirname
in dirnames
:
292 path
= os
.path
.join(dirpath
, dirname
, "config.status")
293 if os
.path
.isfile(path
):
294 builddirs
.append(dirname
)
295 for dirname
in builddirs
:
296 dirnames
.remove(dirname
)
297 for filename
in filenames
:
298 filepath
= os
.path
.join(dirpath
, filename
).replace("\\", "/")
299 if not filepath
.startswith(
300 tuple(ignored_js_src_dirs
)
301 ) and filepath
.endswith((".c", ".cpp", ".h", ".tbl", ".msg")):
302 inclname
= filepath
[len("js/src/") :]
303 js_names
[filepath
] = inclname
305 # Look for header files in directories in non_js_dirnames.
306 for non_js_dir
in non_js_dirnames
:
307 for dirpath
, dirnames
, filenames
in os
.walk(non_js_dir
):
308 for filename
in filenames
:
309 if filename
.endswith(".h"):
310 inclname
= "mozilla/" + filename
311 if non_js_dir
== "intl/components/":
312 inclname
= "mozilla/intl/" + filename
313 non_js_inclnames
.add(inclname
)
315 # Look for header files in js/public.
316 js_public_root
= os
.path
.join("js", "public")
317 for dirpath
, dirnames
, filenames
in os
.walk(js_public_root
):
318 for filename
in filenames
:
319 if filename
.endswith((".h", ".msg")):
320 filepath
= os
.path
.join(dirpath
, filename
).replace("\\", "/")
321 inclname
= "js/" + filepath
[len("js/public/") :]
322 js_names
[filepath
] = inclname
324 all_inclnames
= non_js_inclnames |
set(js_names
.values())
326 edges
= dict() # type: dict(inclname, set(inclname))
328 # We don't care what's inside the MFBT and MOZALLOC files, but because they
329 # are #included from JS files we have to add them to the inclusion graph.
330 for inclname
in non_js_inclnames
:
331 edges
[inclname
] = set()
333 # Process all the JS files.
334 for filename
in sorted(js_names
.keys()):
335 inclname
= js_names
[filename
]
336 file_kind
= FileKind
.get(filename
)
338 file_kind
== FileKind
.C
339 or file_kind
== FileKind
.CPP
340 or file_kind
== FileKind
.H
341 or file_kind
== FileKind
.INL_H
343 included_h_inclnames
= set() # type: set(inclname)
345 with
open(filename
, encoding
="utf-8") as f
:
349 code
= code
.sorted(inclname
)
350 with
open(filename
, "w") as f
:
351 f
.write(code
.to_source())
354 filename
, inclname
, file_kind
, code
, all_inclnames
, included_h_inclnames
357 edges
[inclname
] = included_h_inclnames
359 find_cycles(all_inclnames
, edges
)
361 # Compare expected and actual output.
362 difflines
= difflib
.unified_diff(
365 fromfile
="check_spidermonkey_style.py expected output",
366 tofile
="check_spidermonkey_style.py actual output",
369 for diffline
in difflines
:
371 print(diffline
, end
="")
376 def module_name(name
):
377 """Strip the trailing .cpp, .h, inlines.h or -inl.h from a filename."""
380 name
.replace("inlines.h", "")
381 .replace("-inl.h", "")
387 def is_module_header(enclosing_inclname
, header_inclname
):
388 """Determine if an included name is the "module header", i.e. should be
389 first in the file."""
391 module
= module_name(enclosing_inclname
)
393 # Normal case, for example:
394 # module == "vm/Runtime", header_inclname == "vm/Runtime.h".
395 if module
== module_name(header_inclname
):
398 # A public header, for example:
400 # module == "vm/CharacterEncoding",
401 # header_inclname == "js/CharacterEncoding.h"
403 # or (for implementation files for js/public/*/*.h headers)
405 # module == "vm/SourceHook",
406 # header_inclname == "js/experimental/SourceHook.h"
407 m
= re
.match(r
"js\/.*?([^\/]+)\.h", header_inclname
)
408 if m
is not None and module
.endswith("/" + m
.group(1)):
414 class Include(object):
415 """Important information for a single #include statement."""
417 def __init__(self
, include_prefix
, inclname
, line_suffix
, linenum
, is_system
):
418 self
.include_prefix
= include_prefix
419 self
.line_suffix
= line_suffix
420 self
.inclname
= inclname
421 self
.linenum
= linenum
422 self
.is_system
= is_system
424 def is_style_relevant(self
):
425 # Includes are style-relevant; that is, they're checked by the pairwise
426 # style-checking algorithm in check_file.
429 def section(self
, enclosing_inclname
):
430 """Identify which section inclname belongs to.
432 The section numbers are as follows.
433 0. Module header (e.g. jsfoo.h or jsfooinlines.h within jsfoo.cpp)
436 3. jsfoo.h, prmjtime.h, etc
440 7. non-.h, e.g. *.tbl, *.msg (these can be scattered throughout files)
446 if not self
.inclname
.endswith(".h"):
449 # A couple of modules have the .h file in js/ and the .cpp file elsewhere and so need
451 if is_module_header(enclosing_inclname
, self
.inclname
):
454 if "/" in self
.inclname
:
455 if self
.inclname
.startswith("mozilla/"):
458 if self
.inclname
.endswith("-inl.h"):
463 if self
.inclname
.endswith("inlines.h"):
470 return "<" + self
.inclname
+ ">"
472 return '"' + self
.inclname
+ '"'
474 def sort_key(self
, enclosing_inclname
):
475 return (self
.section(enclosing_inclname
), self
.inclname
.lower())
478 return self
.include_prefix
+ self
.quote() + self
.line_suffix
+ "\n"
481 class CppBlock(object):
482 """C preprocessor block: a whole file or a single #if/#elif/#else block.
484 A #if/#endif block is the contents of a #if/#endif (or similar) section.
485 The top-level block, which is not within a #if/#endif pair, is also
488 Each kid is either an Include (representing a #include), OrdinaryCode, or
489 a nested CppBlock."""
491 def __init__(self
, start_line
=""):
492 self
.start
= start_line
496 def is_style_relevant(self
):
499 def append_ordinary_line(self
, line
):
500 if len(self
.kids
) == 0 or not isinstance(self
.kids
[-1], OrdinaryCode
):
501 self
.kids
.append(OrdinaryCode())
502 self
.kids
[-1].lines
.append(line
)
504 def style_relevant_kids(self
):
505 """Return a list of kids in this block that are style-relevant."""
506 return [kid
for kid
in self
.kids
if kid
.is_style_relevant()]
508 def sorted(self
, enclosing_inclname
):
509 """Return a hopefully-sorted copy of this block. Implements --fixup.
511 When in doubt, this leaves the code unchanged.
514 def pretty_sorted_includes(includes
):
515 """Return a new list containing the given includes, in order,
516 with blank lines separating sections."""
517 keys
= [inc
.sort_key(enclosing_inclname
) for inc
in includes
]
518 if sorted(keys
) == keys
:
519 return includes
# if nothing is out of order, don't touch anything
522 current_section
= None
523 for (section
, _
), inc
in sorted(zip(keys
, includes
)):
524 if current_section
is not None and section
!= current_section
:
525 output
.append(OrdinaryCode(["\n"])) # blank line
527 current_section
= section
530 def should_try_to_sort(includes
):
531 if "tests/style/BadIncludes" in enclosing_inclname
:
532 return False # don't straighten the counterexample
533 if any(inc
.inclname
in oddly_ordered_inclnames
for inc
in includes
):
534 return False # don't sort batches containing odd includes
535 if includes
== sorted(
536 includes
, key
=lambda inc
: inc
.sort_key(enclosing_inclname
)
538 return False # it's already sorted, avoid whitespace-only fixups
541 # The content of the eventual output of this method.
544 # The current batch of includes to sort. This list only ever contains Include objects
545 # and whitespace OrdinaryCode objects.
549 """Sort the contents of `batch` and move it to `output`."""
552 isinstance(item
, Include
)
553 or (isinstance(item
, OrdinaryCode
) and "".join(item
.lines
).isspace())
557 # Here we throw away the blank lines.
558 # `pretty_sorted_includes` puts them back.
560 last_include_index
= -1
561 for i
, item
in enumerate(batch
):
562 if isinstance(item
, Include
):
563 includes
.append(item
)
564 last_include_index
= i
565 cutoff
= last_include_index
+ 1
567 if should_try_to_sort(includes
):
568 output
.extend(pretty_sorted_includes(includes
) + batch
[cutoff
:])
573 for kid
in self
.kids
:
574 if isinstance(kid
, CppBlock
):
576 output
.append(kid
.sorted(enclosing_inclname
))
577 elif isinstance(kid
, Include
):
580 assert isinstance(kid
, OrdinaryCode
)
581 if kid
.to_source().isspace():
589 result
.start
= self
.start
590 result
.end
= self
.end
595 return self
.start
+ "".join(kid
.to_source() for kid
in self
.kids
) + self
.end
598 class OrdinaryCode(object):
599 """A list of lines of code that aren't #include/#if/#else/#endif lines."""
601 def __init__(self
, lines
=None):
602 self
.lines
= lines
if lines
is not None else []
604 def is_style_relevant(self
):
608 return "".join(self
.lines
)
611 # A "snippet" is one of:
613 # * Include - representing an #include line
614 # * CppBlock - a whole file or #if/#elif/#else block; contains a list of snippets
615 # * OrdinaryCode - representing lines of non-#include-relevant code
619 block_stack
= [CppBlock()]
621 # Extract the #include statements as a tree of snippets.
622 for linenum
, line
in enumerate(f
, start
=1):
623 if line
.lstrip().startswith("#"):
624 # Look for a |#include "..."| line.
625 m
= re
.match(r
'(\s*#\s*include\s+)"([^"]*)"(.*)', line
)
627 prefix
, inclname
, suffix
= m
.groups()
628 block_stack
[-1].kids
.append(
629 Include(prefix
, inclname
, suffix
, linenum
, is_system
=False)
633 # Look for a |#include <...>| line.
634 m
= re
.match(r
"(\s*#\s*include\s+)<([^>]*)>(.*)", line
)
636 prefix
, inclname
, suffix
= m
.groups()
637 block_stack
[-1].kids
.append(
638 Include(prefix
, inclname
, suffix
, linenum
, is_system
=True)
642 # Look for a |#{if,ifdef,ifndef}| line.
643 m
= re
.match(r
"\s*#\s*(if|ifdef|ifndef)\b", line
)
646 new_block
= CppBlock(line
)
647 block_stack
[-1].kids
.append(new_block
)
648 block_stack
.append(new_block
)
651 # Look for a |#{elif,else}| line.
652 m
= re
.match(r
"\s*#\s*(elif|else)\b", line
)
654 # Close the current block, and open an adjacent one.
656 new_block
= CppBlock(line
)
657 block_stack
[-1].kids
.append(new_block
)
658 block_stack
.append(new_block
)
661 # Look for a |#endif| line.
662 m
= re
.match(r
"\s*#\s*endif\b", line
)
664 # Close the current block.
665 block_stack
.pop().end
= line
666 if len(block_stack
) == 0:
667 raise ValueError("#endif without #if at line " + str(linenum
))
670 # Otherwise, we have an ordinary line.
671 block_stack
[-1].append_ordinary_line(line
)
673 if len(block_stack
) > 1:
674 raise ValueError("unmatched #if")
675 return block_stack
[-1]
679 filename
, inclname
, file_kind
, code
, all_inclnames
, included_h_inclnames
681 def check_include_statement(include
):
682 """Check the style of a single #include statement."""
684 if include
.is_system
:
685 # Check it is not a known local file (in which case it's probably a system header).
687 include
.inclname
in included_inclnames_to_ignore
688 or include
.inclname
in all_inclnames
693 include
.quote() + " should be included using",
694 'the #include "..." form',
698 msg
= deprecated_inclnames
.get(include
.inclname
)
703 include
.quote() + " is deprecated: " + msg
,
706 if file_kind
== FileKind
.H
or file_kind
== FileKind
.INL_H
:
707 msg
= deprecated_inclnames_in_header
.get(include
.inclname
)
708 if msg
and filename
not in deprecated_inclnames_in_header_excludes
:
712 include
.quote() + " is deprecated: " + msg
,
715 if include
.inclname
not in included_inclnames_to_ignore
:
716 included_kind
= FileKind
.get(include
.inclname
)
718 # Check the #include path has the correct form.
719 if include
.inclname
not in all_inclnames
:
723 include
.quote() + " is included using the wrong path;",
724 "did you forget a prefix, or is the file not yet committed?",
727 # Record inclusions of .h files for cycle detection later.
728 # (Exclude .tbl and .msg files.)
729 elif included_kind
== FileKind
.H
or included_kind
== FileKind
.INL_H
:
730 included_h_inclnames
.add(include
.inclname
)
732 # Check a H file doesn't #include an INL_H file.
733 if file_kind
== FileKind
.H
and included_kind
== FileKind
.INL_H
:
737 "vanilla header includes an inline-header file "
741 # Check a file doesn't #include itself. (We do this here because the cycle
742 # detection below doesn't detect this case.)
743 if inclname
== include
.inclname
:
744 error(filename
, include
.linenum
, "the file includes itself")
746 def check_includes_order(include1
, include2
):
747 """Check the ordering of two #include statements."""
750 include1
.inclname
in oddly_ordered_inclnames
751 or include2
.inclname
in oddly_ordered_inclnames
755 section1
= include1
.section(inclname
)
756 section2
= include2
.section(inclname
)
757 if (section1
> section2
) or (
758 (section1
== section2
)
759 and (include1
.inclname
.lower() > include2
.inclname
.lower())
763 str(include1
.linenum
) + ":" + str(include2
.linenum
),
764 include1
.quote() + " should be included after " + include2
.quote(),
767 # Check the extracted #include statements, both individually, and the ordering of
768 # adjacent pairs that live in the same block.
769 def pair_traverse(prev
, this
):
770 if isinstance(this
, Include
):
771 check_include_statement(this
)
772 if isinstance(prev
, Include
):
773 check_includes_order(prev
, this
)
775 kids
= this
.style_relevant_kids()
776 for prev2
, this2
in zip([None] + kids
[0:-1], kids
):
777 pair_traverse(prev2
, this2
)
779 pair_traverse(None, code
)
782 def find_cycles(all_inclnames
, edges
):
783 """Find and draw any cycles."""
785 SCCs
= tarjan(all_inclnames
, edges
)
787 # The various sorted() calls below ensure the output is deterministic.
794 out(" " * indent
+ ("-> " if indent
else " ") + v
)
798 for succ
in sorted(edges
[v
]):
800 draw(succ
, indent
+ 1)
802 draw(sorted(c
)[0], 0)
805 have_drawn_an_SCC
= False
806 for scc
in sorted(SCCs
):
808 if not have_drawn_an_SCC
:
809 error("(multiple files)", None, "header files form one or more cycles")
810 have_drawn_an_SCC
= True
815 # Tarjan's algorithm for finding the strongly connected components (SCCs) of a graph.
816 # https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
824 def strongconnect(v
, index
):
825 # Set the depth index for v to the smallest unused index
826 vertex_index
[v
] = index
827 vertex_lowlink
[v
] = index
831 # Consider successors of v
833 if w
not in vertex_index
:
834 # Successor w has not yet been visited; recurse on it
835 index
= strongconnect(w
, index
)
836 vertex_lowlink
[v
] = min(vertex_lowlink
[v
], vertex_lowlink
[w
])
838 # Successor w is in stack S and hence in the current SCC
839 vertex_lowlink
[v
] = min(vertex_lowlink
[v
], vertex_index
[w
])
841 # If v is a root node, pop the stack and generate an SCC
842 if vertex_lowlink
[v
] == vertex_index
[v
]:
851 if v
not in vertex_index
:
852 index
= strongconnect(v
, index
)
858 if sys
.argv
[1:] == ["--fixup"]:
859 # Sort #include directives in-place. Fixup mode doesn't solve
860 # all possible silliness that the script checks for; it's just a
861 # hack for the common case where renaming a header causes style
864 elif sys
.argv
[1:] == []:
868 "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | unexpected command "
869 "line options: " + repr(sys
.argv
[1:])
873 ok
= check_style(fixup
)
876 print("TEST-PASS | check_spidermonkey_style.py | ok")
879 "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | "
880 + "actual output does not match expected output; diff is above."
883 "TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | "
884 + "Hint: If the problem is that you renamed a header, and many #includes "
885 + "are no longer in alphabetical order, commit your work and then try "
886 + "`check_spidermonkey_style.py --fixup`. "
887 + "You need to commit first because --fixup modifies your files in place."
890 sys
.exit(0 if ok
else 1)
893 if __name__
== "__main__":