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 print_function
  39
  40 import difflib
  41 import os
  42 import re
  43 import subprocess
  44 import sys
  45 import traceback
  46 from check_utils import get_all_toplevel_filenames
  47
  48 # We don't bother checking files in these directories, because they're (a) auxiliary or (b)
  49 # imported code that doesn't follow our coding style.
  50 ignored_js_src_dirs = [
  51    'js/src/config/',            # auxiliary stuff
  52    'js/src/ctypes/libffi/',     # imported code
  53    'js/src/devtools/',          # auxiliary stuff
  54    'js/src/editline/',          # imported code
  55    'js/src/gdb/',               # auxiliary stuff
  56    'js/src/vtune/'              # imported code
  57 ]
  58
  59 # We ignore #includes of these files, because they don't follow the usual rules.
  60 included_inclnames_to_ignore = set([
  61     'ffi.h',                    # generated in ctypes/libffi/
  62     'devtools/sharkctl.h',      # we ignore devtools/ in general
  63     'devtools/Instruments.h',   # we ignore devtools/ in general
  64     'double-conversion.h',      # strange MFBT case
  65     'javascript-trace.h',       # generated in $OBJDIR if HAVE_DTRACE is defined
  66     'jsautokw.h',               # generated in $OBJDIR
  67     'jscustomallocator.h',      # provided by embedders;  allowed to be missing
  68     'js-config.h',              # generated in $OBJDIR
  69     'fdlibm.h',                 # fdlibm
  70     'pratom.h',                 # NSPR
  71     'prcvar.h',                 # NSPR
  72     'prerror.h',                # NSPR
  73     'prinit.h',                 # NSPR
  74     'prlink.h',                 # NSPR
  75     'prlock.h',                 # NSPR
  76     'prprf.h',                  # NSPR
  77     'prthread.h',               # NSPR
  78     'prtypes.h',                # NSPR
  79     'selfhosted.out.h',         # generated in $OBJDIR
  80     'shellmoduleloader.out.h',  # generated in $OBJDIR
  81     'unicode/locid.h',          # ICU
  82     'unicode/numsys.h',         # ICU
  83     'unicode/timezone.h',       # ICU
  84     'unicode/ucal.h',           # ICU
  85     'unicode/uclean.h',         # ICU
  86     'unicode/ucol.h',           # ICU
  87     'unicode/udat.h',           # ICU
  88     'unicode/udatpg.h',         # ICU
  89     'unicode/uenum.h',          # ICU
  90     'unicode/unorm.h',          # ICU
  91     'unicode/unum.h',           # ICU
  92     'unicode/ustring.h',        # ICU
  93     'unicode/utypes.h',         # ICU
  94     'vtune/VTuneWrapper.h'      # VTune
  95 ])
  96
  97 # These files have additional constraints on where they are #included, so we
  98 # ignore #includes of them when checking #include ordering.
  99 oddly_ordered_inclnames = set([
 100     'ctypes/typedefs.h',        # Included multiple times in the body of ctypes/CTypes.h
 101     'jsautokw.h',               # Included in the body of frontend/TokenStream.h
 102     'jswin.h',                  # Must be #included before <psapi.h>
 103     'machine/endian.h',         # Must be included after <sys/types.h> on BSD
 104     'winbase.h',                # Must precede other system headers(?)
 105     'windef.h'                  # Must precede other system headers(?)
 106 ])
 107
 108 # The files in tests/style/ contain code that fails this checking in various
 109 # ways.  Here is the output we expect.  If the actual output differs from
 110 # this, one of the following must have happened.
 111 # - New SpiderMonkey code violates one of the checked rules.
 112 # - The tests/style/ files have changed without expected_output being changed
 113 #   accordingly.
 114 # - This script has been broken somehow.
 115 #
 116 expected_output = '''\
 117 js/src/tests/style/BadIncludes2.h:1: error:
 118     vanilla header includes an inline-header file "tests/style/BadIncludes2-inl.h"
 119
 120 js/src/tests/style/BadIncludes.h:3: error:
 121     the file includes itself
 122
 123 js/src/tests/style/BadIncludes.h:6: error:
 124     "BadIncludes2.h" is included using the wrong path;
 125     did you forget a prefix, or is the file not yet committed?
 126
 127 js/src/tests/style/BadIncludes.h:8: error:
 128     <tests/style/BadIncludes2.h> should be included using
 129     the #include "..." form
 130
 131 js/src/tests/style/BadIncludes.h:10: error:
 132     "stdio.h" is included using the wrong path;
 133     did you forget a prefix, or is the file not yet committed?
 134
 135 js/src/tests/style/BadIncludesOrder-inl.h:5:6: error:
 136     "vm/Interpreter-inl.h" should be included after "jsscriptinlines.h"
 137
 138 js/src/tests/style/BadIncludesOrder-inl.h:6:7: error:
 139     "jsscriptinlines.h" should be included after "js/Value.h"
 140
 141 js/src/tests/style/BadIncludesOrder-inl.h:7:8: error:
 142     "js/Value.h" should be included after "ds/LifoAlloc.h"
 143
 144 js/src/tests/style/BadIncludesOrder-inl.h:8:9: error:
 145     "ds/LifoAlloc.h" should be included after "jsapi.h"
 146
 147 js/src/tests/style/BadIncludesOrder-inl.h:9:10: error:
 148     "jsapi.h" should be included after <stdio.h>
 149
 150 js/src/tests/style/BadIncludesOrder-inl.h:10:11: error:
 151     <stdio.h> should be included after "mozilla/HashFunctions.h"
 152
 153 js/src/tests/style/BadIncludesOrder-inl.h:27:28: error:
 154     "jsobj.h" should be included after "jsfun.h"
 155
 156 (multiple files): error:
 157     header files form one or more cycles
 158
 159    tests/style/HeaderCycleA1.h
 160    -> tests/style/HeaderCycleA2.h
 161       -> tests/style/HeaderCycleA3.h
 162          -> tests/style/HeaderCycleA1.h
 163
 164    tests/style/HeaderCycleB1-inl.h
 165    -> tests/style/HeaderCycleB2-inl.h
 166       -> tests/style/HeaderCycleB3-inl.h
 167          -> tests/style/HeaderCycleB4-inl.h
 168             -> tests/style/HeaderCycleB1-inl.h
 169             -> tests/style/jsheadercycleB5inlines.h
 170                -> tests/style/HeaderCycleB1-inl.h
 171       -> tests/style/HeaderCycleB4-inl.h
 172
 173 '''.splitlines(True)
 174
 175 actual_output = []
 176
 177
 178 def out(*lines):
 179     for line in lines:
 180         actual_output.append(line + '\n')
 181
 182
 183 def error(filename, linenum, *lines):
 184     location = filename
 185     if linenum is not None:
 186         location += ':' + str(linenum)
 187     out(location + ': error:')
 188     for line in (lines):
 189         out('    ' + line)
 190     out('')
 191
 192
 193 class FileKind(object):
 194     C = 1
 195     CPP = 2
 196     INL_H = 3
 197     H = 4
 198     TBL = 5
 199     MSG = 6
 200
 201     @staticmethod
 202     def get(filename):
 203         if filename.endswith('.c'):
 204             return FileKind.C
 205
 206         if filename.endswith('.cpp'):
 207             return FileKind.CPP
 208
 209         if filename.endswith(('inlines.h', '-inl.h')):
 210             return FileKind.INL_H
 211
 212         if filename.endswith('.h'):
 213             return FileKind.H
 214
 215         if filename.endswith('.tbl'):
 216             return FileKind.TBL
 217
 218         if filename.endswith('.msg'):
 219             return FileKind.MSG
 220
 221         error(filename, None, 'unknown file kind')
 222
 223
 224 def check_style():
 225     # We deal with two kinds of name.
 226     # - A "filename" is a full path to a file from the repository root.
 227     # - An "inclname" is how a file is referred to in a #include statement.
 228     #
 229     # Examples (filename -> inclname)
 230     # - "mfbt/Attributes.h"         -> "mozilla/Attributes.h"
 231     # - "mfbt/decimal/Decimal.h     -> "mozilla/Decimal.h"
 232     # - "mozglue/misc/TimeStamp.h   -> "mozilla/TimeStamp.h"
 233     # - "memory/mozalloc/mozalloc.h -> "mozilla/mozalloc.h"
 234     # - "js/public/Vector.h"        -> "js/Vector.h"
 235     # - "js/src/vm/String.h"        -> "vm/String.h"
 236
 237     non_js_dirnames = ('mfbt/',
 238                        'memory/mozalloc/',
 239                        'mozglue/')  # type: tuple(str)
 240     non_js_inclnames = set()        # type: set(inclname)
 241     js_names = dict()               # type: dict(filename, inclname)
 242
 243     # Select the appropriate files.
 244     for filename in get_all_toplevel_filenames():
 245         for non_js_dir in non_js_dirnames:
 246             if filename.startswith(non_js_dir) and filename.endswith('.h'):
 247                 inclname = 'mozilla/' + filename.split('/')[-1]
 248                 non_js_inclnames.add(inclname)
 249
 250         if filename.startswith('js/public/') and filename.endswith('.h'):
 251             inclname = 'js/' + filename[len('js/public/'):]
 252             js_names[filename] = inclname
 253
 254         if filename.startswith('js/src/') and \
 255            not filename.startswith(tuple(ignored_js_src_dirs)) and \
 256            filename.endswith(('.c', '.cpp', '.h', '.tbl', '.msg')):
 257             inclname = filename[len('js/src/'):]
 258             js_names[filename] = inclname
 259
 260     all_inclnames = non_js_inclnames | set(js_names.values())
 261
 262     edges = dict()      # type: dict(inclname, set(inclname))
 263
 264     # We don't care what's inside the MFBT and MOZALLOC files, but because they
 265     # are #included from JS files we have to add them to the inclusion graph.
 266     for inclname in non_js_inclnames:
 267         edges[inclname] = set()
 268
 269     # Process all the JS files.
 270     for filename in js_names.keys():
 271         inclname = js_names[filename]
 272         file_kind = FileKind.get(filename)
 273         if file_kind == FileKind.C or file_kind == FileKind.CPP or \
 274            file_kind == FileKind.H or file_kind == FileKind.INL_H:
 275             included_h_inclnames = set()    # type: set(inclname)
 276
 277             # This script is run in js/src/, so prepend '../../' to get to the root of the Mozilla
 278             # source tree.
 279             with open(os.path.join('../..', filename)) as f:
 280                 do_file(filename, inclname, file_kind, f, all_inclnames, included_h_inclnames)
 281
 282         edges[inclname] = included_h_inclnames
 283
 284     find_cycles(all_inclnames, edges)
 285
 286     # Compare expected and actual output.
 287     difflines = difflib.unified_diff(expected_output, actual_output,
 288                                      fromfile='check_spider_monkey_style.py expected output',
 289                                        tofile='check_spider_monkey_style.py actual output')
 290     ok = True
 291     for diffline in difflines:
 292         ok = False
 293         print(diffline, end='')
 294
 295     return ok
 296
 297
 298 def module_name(name):
 299     '''Strip the trailing .cpp, .h, inlines.h or -inl.h from a filename.'''
 300
 301     return name.replace('inlines.h', '').replace('-inl.h', '').replace('.h', '').replace('.cpp', '')
 302
 303
 304 def is_module_header(enclosing_inclname, header_inclname):
 305     '''Determine if an included name is the "module header", i.e. should be
 306     first in the file.'''
 307
 308     module = module_name(enclosing_inclname)
 309
 310     # Normal case, e.g. module == "foo/Bar", header_inclname == "foo/Bar.h".
 311     if module == module_name(header_inclname):
 312         return True
 313
 314     # A public header, e.g. module == "foo/Bar", header_inclname == "js/Bar.h".
 315     m = re.match(r'js\/(.*)\.h', header_inclname)
 316     if m is not None and module.endswith('/' + m.group(1)):
 317         return True
 318
 319     return False
 320
 321
 322 class Include(object):
 323     '''Important information for a single #include statement.'''
 324
 325     def __init__(self, inclname, linenum, is_system):
 326         self.inclname = inclname
 327         self.linenum = linenum
 328         self.is_system = is_system
 329
 330     def isLeaf(self):
 331         return True
 332
 333     def section(self, enclosing_inclname):
 334         '''Identify which section inclname belongs to.
 335
 336         The section numbers are as follows.
 337           0. Module header (e.g. jsfoo.h or jsfooinlines.h within jsfoo.cpp)
 338           1. mozilla/Foo.h
 339           2. <foo.h> or <foo>
 340           3. jsfoo.h, prmjtime.h, etc
 341           4. foo/Bar.h
 342           5. jsfooinlines.h
 343           6. foo/Bar-inl.h
 344           7. non-.h, e.g. *.tbl, *.msg
 345         '''
 346
 347         if self.is_system:
 348             return 2
 349
 350         if not self.inclname.endswith('.h'):
 351             return 7
 352
 353         # A couple of modules have the .h file in js/ and the .cpp file elsewhere and so need
 354         # special handling.
 355         if is_module_header(enclosing_inclname, self.inclname):
 356             return 0
 357
 358         if '/' in self.inclname:
 359             if self.inclname.startswith('mozilla/'):
 360                 return 1
 361
 362             if self.inclname.endswith('-inl.h'):
 363                 return 6
 364
 365             return 4
 366
 367         if self.inclname.endswith('inlines.h'):
 368             return 5
 369
 370         return 3
 371
 372     def quote(self):
 373         if self.is_system:
 374             return '<' + self.inclname + '>'
 375         else:
 376             return '"' + self.inclname + '"'
 377
 378
 379 class HashIfBlock(object):
 380     '''Important information about a #if/#endif block.
 381
 382     A #if/#endif block is the contents of a #if/#endif (or similar) section.
 383     The top-level block, which is not within a #if/#endif pair, is also
 384     considered a block.
 385
 386     Each leaf is either an Include (representing a #include), or another
 387     nested HashIfBlock.'''
 388     def __init__(self):
 389         self.kids = []
 390
 391     def isLeaf(self):
 392         return False
 393
 394
 395 def do_file(filename, inclname, file_kind, f, all_inclnames, included_h_inclnames):
 396     block_stack = [HashIfBlock()]
 397
 398     # Extract the #include statements as a tree of IBlocks and IIncludes.
 399     for linenum, line in enumerate(f, start=1):
 400         # We're only interested in lines that contain a '#'.
 401         if not '#' in line:
 402             continue
 403
 404         # Look for a |#include "..."| line.
 405         m = re.match(r'\s*#\s*include\s+"([^"]*)"', line)
 406         if m is not None:
 407             block_stack[-1].kids.append(Include(m.group(1), linenum, False))
 408
 409         # Look for a |#include <...>| line.
 410         m = re.match(r'\s*#\s*include\s+<([^>]*)>', line)
 411         if m is not None:
 412             block_stack[-1].kids.append(Include(m.group(1), linenum, True))
 413
 414         # Look for a |#{if,ifdef,ifndef}| line.
 415         m = re.match(r'\s*#\s*(if|ifdef|ifndef)\b', line)
 416         if m is not None:
 417             # Open a new block.
 418             new_block = HashIfBlock()
 419             block_stack[-1].kids.append(new_block)
 420             block_stack.append(new_block)
 421
 422         # Look for a |#{elif,else}| line.
 423         m = re.match(r'\s*#\s*(elif|else)\b', line)
 424         if m is not None:
 425             # Close the current block, and open an adjacent one.
 426             block_stack.pop()
 427             new_block = HashIfBlock()
 428             block_stack[-1].kids.append(new_block)
 429             block_stack.append(new_block)
 430
 431         # Look for a |#endif| line.
 432         m = re.match(r'\s*#\s*endif\b', line)
 433         if m is not None:
 434             # Close the current block.
 435             block_stack.pop()
 436
 437     def check_include_statement(include):
 438         '''Check the style of a single #include statement.'''
 439
 440         if include.is_system:
 441             # Check it is not a known local file (in which case it's probably a system header).
 442             if include.inclname in included_inclnames_to_ignore or \
 443                include.inclname in all_inclnames:
 444                 error(filename, include.linenum,
 445                       include.quote() + ' should be included using',
 446                       'the #include "..." form')
 447
 448         else:
 449             if include.inclname not in included_inclnames_to_ignore:
 450                 included_kind = FileKind.get(include.inclname)
 451
 452                 # Check the #include path has the correct form.
 453                 if include.inclname not in all_inclnames:
 454                     error(filename, include.linenum,
 455                           include.quote() + ' is included using the wrong path;',
 456                           'did you forget a prefix, or is the file not yet committed?')
 457
 458                 # Record inclusions of .h files for cycle detection later.
 459                 # (Exclude .tbl and .msg files.)
 460                 elif included_kind == FileKind.H or included_kind == FileKind.INL_H:
 461                     included_h_inclnames.add(include.inclname)
 462
 463                 # Check a H file doesn't #include an INL_H file.
 464                 if file_kind == FileKind.H and included_kind == FileKind.INL_H:
 465                     error(filename, include.linenum,
 466                           'vanilla header includes an inline-header file ' + include.quote())
 467
 468                 # Check a file doesn't #include itself.  (We do this here because the cycle
 469                 # detection below doesn't detect this case.)
 470                 if inclname == include.inclname:
 471                     error(filename, include.linenum, 'the file includes itself')
 472
 473     def check_includes_order(include1, include2):
 474         '''Check the ordering of two #include statements.'''
 475
 476         if include1.inclname in oddly_ordered_inclnames or \
 477            include2.inclname in oddly_ordered_inclnames:
 478             return
 479
 480         section1 = include1.section(inclname)
 481         section2 = include2.section(inclname)
 482         if (section1 > section2) or \
 483            ((section1 == section2) and (include1.inclname.lower() > include2.inclname.lower())):
 484             error(filename, str(include1.linenum) + ':' + str(include2.linenum),
 485                   include1.quote() + ' should be included after ' + include2.quote())
 486
 487     # Check the extracted #include statements, both individually, and the ordering of
 488     # adjacent pairs that live in the same block.
 489     def pair_traverse(prev, this):
 490         if this.isLeaf():
 491             check_include_statement(this)
 492             if prev is not None and prev.isLeaf():
 493                 check_includes_order(prev, this)
 494         else:
 495             for prev2, this2 in zip([None] + this.kids[0:-1], this.kids):
 496                 pair_traverse(prev2, this2)
 497
 498     pair_traverse(None, block_stack[-1])
 499
 500
 501 def find_cycles(all_inclnames, edges):
 502     '''Find and draw any cycles.'''
 503
 504     SCCs = tarjan(all_inclnames, edges)
 505
 506     # The various sorted() calls below ensure the output is deterministic.
 507
 508     def draw_SCC(c):
 509         cset = set(c)
 510         drawn = set()
 511         def draw(v, indent):
 512             out('   ' * indent + ('-> ' if indent else '   ') + v)
 513             if v in drawn:
 514                 return
 515             drawn.add(v)
 516             for succ in sorted(edges[v]):
 517                 if succ in cset:
 518                     draw(succ, indent + 1)
 519         draw(sorted(c)[0], 0)
 520         out('')
 521
 522     have_drawn_an_SCC = False
 523     for scc in sorted(SCCs):
 524         if len(scc) != 1:
 525             if not have_drawn_an_SCC:
 526                 error('(multiple files)', None, 'header files form one or more cycles')
 527                 have_drawn_an_SCC = True
 528
 529             draw_SCC(scc)
 530
 531
 532 # Tarjan's algorithm for finding the strongly connected components (SCCs) of a graph.
 533 # https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
 534 def tarjan(V, E):
 535     vertex_index = {}
 536     vertex_lowlink = {}
 537     index = 0
 538     S = []
 539     all_SCCs = []
 540
 541     def strongconnect(v, index):
 542         # Set the depth index for v to the smallest unused index
 543         vertex_index[v] = index
 544         vertex_lowlink[v] = index
 545         index += 1
 546         S.append(v)
 547
 548         # Consider successors of v
 549         for w in E[v]:
 550             if w not in vertex_index:
 551                 # Successor w has not yet been visited; recurse on it
 552                 index = strongconnect(w, index)
 553                 vertex_lowlink[v] = min(vertex_lowlink[v], vertex_lowlink[w])
 554             elif w in S:
 555                 # Successor w is in stack S and hence in the current SCC
 556                 vertex_lowlink[v] = min(vertex_lowlink[v], vertex_index[w])
 557
 558         # If v is a root node, pop the stack and generate an SCC
 559         if vertex_lowlink[v] == vertex_index[v]:
 560             i = S.index(v)
 561             scc = S[i:]
 562             del S[i:]
 563             all_SCCs.append(scc)
 564
 565         return index
 566
 567     for v in V:
 568         if v not in vertex_index:
 569             index = strongconnect(v, index)
 570
 571     return all_SCCs
 572
 573
 574 def main():
 575     ok = check_style()
 576
 577     if ok:
 578         print('TEST-PASS | check_spidermonkey_style.py | ok')
 579     else:
 580         print('TEST-UNEXPECTED-FAIL | check_spidermonkey_style.py | actual output does not match expected output;  diff is above')
 581
 582     sys.exit(0 if ok else 1)
 583
 584
 585 if __name__ == '__main__':
 586     main()