config/check_spidermonkey_style.py

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