src/third_party/WebKit/Source/bindings/scripts/blink_idl_parser.py

   1 # Copyright (C) 2013 Google Inc. All rights reserved.
   2 #
   3 # Redistribution and use in source and binary forms, with or without
   4 # modification, are permitted provided that the following conditions are
   5 # met:
   6 #
   7 #     * Redistributions of source code must retain the above copyright
   8 # notice, this list of conditions and the following disclaimer.
   9 #     * Redistributions in binary form must reproduce the above
  10 # copyright notice, this list of conditions and the following disclaimer
  11 # in the documentation and/or other materials provided with the
  12 # distribution.
  13 #     * Neither the name of Google Inc. nor the names of its
  14 # contributors may be used to endorse or promote products derived from
  15 # this software without specific prior written permission.
  16 #
  17 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28
  29 """Parser for Blink IDL.
  30
  31 The parser uses the PLY (Python Lex-Yacc) library to build a set of parsing
  32 rules which understand the Blink dialect of Web IDL.
  33 It derives from a standard Web IDL parser, overriding rules where Blink IDL
  34 differs syntactically or semantically from the base parser, or where the base
  35 parser diverges from the Web IDL standard.
  36
  37 Web IDL:
  38     http://www.w3.org/TR/WebIDL/
  39 Web IDL Grammar:
  40     http://www.w3.org/TR/WebIDL/#idl-grammar
  41 PLY:
  42     http://www.dabeaz.com/ply/
  43
  44 Design doc:
  45 http://www.chromium.org/developers/design-documents/idl-compiler#TOC-Front-end
  46 """
  47
  48 # Disable check for line length and Member as Function due to how grammar rules
  49 # are defined with PLY
  50 #
  51 # pylint: disable=R0201
  52 # pylint: disable=C0301
  53 #
  54 # Disable attribute validation, as lint can't import parent class to check
  55 # pylint: disable=E1101
  56
  57 import os.path
  58 import sys
  59
  60 # PLY is in Chromium src/third_party/ply
  61 module_path, module_name = os.path.split(__file__)
  62 third_party = os.path.join(module_path, os.pardir, os.pardir, os.pardir, os.pardir)
  63 # Insert at front to override system libraries, and after path[0] == script dir
  64 sys.path.insert(1, third_party)
  65 from ply import yacc
  66
  67 # Base parser is in Chromium src/tools/idl_parser
  68 tools_dir = os.path.join(module_path, os.pardir, os.pardir, os.pardir, os.pardir, os.pardir, 'tools')
  69 sys.path.append(tools_dir)
  70 from idl_parser.idl_parser import IDLParser, ListFromConcat
  71 from idl_parser.idl_parser import ParseFile as parse_file
  72
  73 from blink_idl_lexer import BlinkIDLLexer
  74 import blink_idl_lexer
  75
  76
  77 # Explicitly set starting symbol to rule defined only in base parser.
  78 # BEWARE that the starting symbol should NOT be defined in both the base parser
  79 # and the derived one, as otherwise which is used depends on which line number
  80 # is lower, which is fragile. Instead, either use one in base parser or
  81 # create a new symbol, so that this is unambiguous.
  82 # FIXME: unfortunately, this doesn't work in PLY 3.4, so need to duplicate the
  83 # rule below.
  84 STARTING_SYMBOL = 'Definitions'
  85
  86 # We ignore comments (and hence don't need 'Top') but base parser preserves them
  87 # FIXME: Upstream: comments should be removed in base parser
  88 REMOVED_RULES = ['Top',  # [0]
  89                  'Comments',  # [0.1]
  90                  'CommentsRest',  # [0.2]
  91                 ]
  92
  93 # Remove rules from base class
  94 # FIXME: add a class method upstream: @classmethod IDLParser._RemoveRules
  95 for rule in REMOVED_RULES:
  96     production_name = 'p_' + rule
  97     delattr(IDLParser, production_name)
  98
  99
 100 class BlinkIDLParser(IDLParser):
 101     # [1]
 102     # FIXME: Need to duplicate rule for starting symbol here, with line number
 103     # *lower* than in the base parser (idl_parser.py).
 104     # This is a bug in PLY: it determines starting symbol by lowest line number.
 105     # This can be overridden by the 'start' parameter, but as of PLY 3.4 this
 106     # doesn't work correctly.
 107     def p_Definitions(self, p):
 108         """Definitions : ExtendedAttributeList Definition Definitions
 109                        | """
 110         if len(p) > 1:
 111             p[2].AddChildren(p[1])
 112             p[0] = ListFromConcat(p[2], p[3])
 113
 114     # Below are grammar rules used by yacc, given by functions named p_<RULE>.
 115     # * The docstring is the production rule in BNF (grammar).
 116     # * The body is the yacc action (semantics).
 117     #
 118     # The PLY framework builds the actual low-level parser by introspecting this
 119     # parser object, selecting all attributes named p_<RULE> as grammar rules.
 120     # It extracts the docstrings and uses them as the production rules, building
 121     # the table of a LALR parser, and uses the body of the functions as actions.
 122     #
 123     # Reference:
 124     # http://www.dabeaz.com/ply/ply.html#ply_nn23
 125     #
 126     # Review of yacc:
 127     # Yacc parses a token stream, internally producing a Concrete Syntax Tree
 128     # (CST), where each node corresponds to a production rule in the grammar.
 129     # At each node, it runs an action, which is usually "produce a node in the
 130     # Abstract Syntax Tree (AST)" or "ignore this node" (for nodes in the CST
 131     # that aren't included in the AST, since only needed for parsing).
 132     #
 133     # The rules use pseudo-variables; in PLY syntax:
 134     # p[0] is the left side: assign return value to p[0] instead of returning,
 135     # p[1] ... p[n] are the right side: the values can be accessed, and they
 136     # can be modified.
 137     # (In yacc these are $$ and $1 ... $n.)
 138     #
 139     # The rules can look cryptic at first, but there are a few standard
 140     # transforms from the CST to AST. With these in mind, the actions should
 141     # be reasonably legible.
 142     #
 143     # * Ignore production
 144     #   Discard this branch. Primarily used when one alternative is empty.
 145     #
 146     #   Sample code:
 147     #   if len(p) > 1:
 148     #       p[0] = ...
 149     #   # Note no assignment if len(p) == 1
 150     #
 151     # * Eliminate singleton production
 152     #   Discard this node in the CST, pass the next level down up the tree.
 153     #   Used to ignore productions only necessary for parsing, but not needed
 154     #   in the AST.
 155     #
 156     #   Sample code:
 157     #   p[0] = p[1]
 158     #
 159     # * Build node
 160     #   The key type of rule. In this parser, produces object of class IDLNode.
 161     #   There are several helper functions:
 162     #   * BuildProduction: actually builds an IDLNode, based on a production.
 163     #   * BuildAttribute: builds an IDLAttribute, which is a temporary
 164     #                     object to hold a name-value pair, which is then
 165     #                     set as a Property of the IDLNode when the IDLNode
 166     #                     is built.
 167     #   * BuildNamed: Same as BuildProduction, and sets the 'NAME' property.
 168     #   * BuildTrue: BuildAttribute with value True, for flags.
 169     #   See base idl_parser.py for definitions and more examples of use.
 170     #
 171     #   Sample code:
 172     #   # Build node of type NodeType, with value p[1], and children.
 173     #   p[0] = self.BuildProduction('NodeType', p, 1, children)
 174     #
 175     #   # Build named node of type NodeType, with name and value p[1].
 176     #   # (children optional)
 177     #   p[0] = self.BuildNamed('NodeType', p, 1)
 178     #
 179     #   # Make a list
 180     #   # Used if one node has several children.
 181     #   children = ListFromConcat(p[2], p[3])
 182     #   p[0] = self.BuildProduction('NodeType', p, 1, children)
 183     #
 184     #   # Also used to collapse the right-associative tree
 185     #   # produced by parsing a list back into a single list.
 186     #   """Foos : Foo Foos
 187     #           |"""
 188     #   if len(p) > 1:
 189     #       p[0] = ListFromConcat(p[1], p[2])
 190     #
 191     #   # Add children.
 192     #   # Primarily used to add attributes, produced via BuildTrue.
 193     #   # p_StaticAttribute
 194     #   """StaticAttribute : STATIC Attribute"""
 195     #   p[2].AddChildren(self.BuildTrue('STATIC'))
 196     #   p[0] = p[2]
 197     #
 198     # Numbering scheme for the rules is:
 199     # [1] for Web IDL spec (or additions in base parser)
 200     #     These should all be upstreamed to the base parser.
 201     # [b1] for Blink IDL changes (overrides Web IDL)
 202     # [b1.1] for Blink IDL additions, auxiliary rules for [b1]
 203     # Numbers are as per Candidate Recommendation 19 April 2012:
 204     # http://www.w3.org/TR/2012/CR-WebIDL-20120419/
 205
 206     # [3] Override action, since we distinguish callbacks
 207     # FIXME: Upstream
 208     def p_CallbackOrInterface(self, p):
 209         """CallbackOrInterface : CALLBACK CallbackRestOrInterface
 210                                | Interface"""
 211         if len(p) > 2:
 212             p[2].AddChildren(self.BuildTrue('CALLBACK'))
 213             p[0] = p[2]
 214         else:
 215             p[0] = p[1]
 216
 217     # [b27] Add strings, more 'Literal' productions
 218     # 'Literal's needed because integers and strings are both internally strings
 219     def p_ConstValue(self, p):
 220         """ConstValue : BooleanLiteral
 221                       | FloatLiteral
 222                       | IntegerLiteral
 223                       | StringLiteral
 224                       | null"""
 225         # Standard is (no 'string', fewer 'Literal's):
 226         # ConstValue : BooleanLiteral
 227         #            | FloatLiteral
 228         #            | integer
 229         #            | NULL
 230         p[0] = p[1]
 231
 232     # [b27.1]
 233     def p_IntegerLiteral(self, p):
 234         """IntegerLiteral : integer"""
 235         p[0] = ListFromConcat(self.BuildAttribute('TYPE', 'integer'),
 236                               self.BuildAttribute('NAME', p[1]))
 237
 238     # [b27.2]
 239     def p_StringLiteral(self, p):
 240         """StringLiteral : string"""
 241         p[0] = ListFromConcat(self.BuildAttribute('TYPE', 'DOMString'),
 242                               self.BuildAttribute('NAME', p[1]))
 243
 244     # [b47]
 245     def p_ExceptionMember(self, p):
 246         """ExceptionMember : Const
 247                            | ExceptionField
 248                            | Attribute
 249                            | ExceptionOperation"""
 250         # Standard is (no Attribute, no ExceptionOperation):
 251         # ExceptionMember : Const
 252         #                 | ExceptionField
 253         # FIXME: In DOMException.idl, Attributes should be changed to
 254         # ExceptionFields, and Attribute removed from this rule.
 255         p[0] = p[1]
 256
 257     # [b47.1]
 258     def p_ExceptionOperation(self, p):
 259         """ExceptionOperation : Type identifier '(' ')' ';'"""
 260         # Needed to handle one case in DOMException.idl:
 261         # // Override in a Mozilla compatible format
 262         # [NotEnumerable] DOMString toString();
 263         # Limited form of Operation to prevent others from being added.
 264         # FIXME: Should be a stringifier instead.
 265         p[0] = self.BuildNamed('ExceptionOperation', p, 2, p[1])
 266
 267     # Extended attributes
 268     # [b49] Override base parser: remove comment field, since comments stripped
 269     # FIXME: Upstream
 270     def p_ExtendedAttributeList(self, p):
 271         """ExtendedAttributeList : '[' ExtendedAttribute ExtendedAttributes ']'
 272                                  | '[' ']'
 273                                  | """
 274         if len(p) > 3:
 275             items = ListFromConcat(p[2], p[3])
 276             p[0] = self.BuildProduction('ExtAttributes', p, 1, items)
 277
 278     # [b50] Allow optional trailing comma
 279     # Blink-only, marked as WONTFIX in Web IDL spec:
 280     # https://www.w3.org/Bugs/Public/show_bug.cgi?id=22156
 281     def p_ExtendedAttributes(self, p):
 282         """ExtendedAttributes : ',' ExtendedAttribute ExtendedAttributes
 283                               | ','
 284                               |"""
 285         if len(p) > 3:
 286             p[0] = ListFromConcat(p[2], p[3])
 287
 288     # [b51] Add ExtendedAttributeStringLiteral and ExtendedAttributeStringLiteralList
 289     def p_ExtendedAttribute(self, p):
 290         """ExtendedAttribute : ExtendedAttributeNoArgs
 291                              | ExtendedAttributeArgList
 292                              | ExtendedAttributeIdent
 293                              | ExtendedAttributeIdentList
 294                              | ExtendedAttributeNamedArgList
 295                              | ExtendedAttributeStringLiteral
 296                              | ExtendedAttributeStringLiteralList"""
 297         p[0] = p[1]
 298
 299     # [59]
 300     # FIXME: Upstream UnionType
 301     def p_UnionType(self, p):
 302         """UnionType : '(' UnionMemberType OR UnionMemberType UnionMemberTypes ')'"""
 303         members = ListFromConcat(p[2], p[4], p[5])
 304         p[0] = self.BuildProduction('UnionType', p, 1, members)
 305
 306     # [60]
 307     def p_UnionMemberType(self, p):
 308         """UnionMemberType : NonAnyType
 309                            | UnionType TypeSuffix
 310                            | ANY '[' ']' TypeSuffix"""
 311         if len(p) == 2:
 312             p[0] = self.BuildProduction('Type', p, 1, p[1])
 313         elif len(p) == 3:
 314             p[0] = self.BuildProduction('Type', p, 1, ListFromConcat(p[1], p[2]))
 315         else:
 316             any_node = ListFromConcat(self.BuildProduction('Any', p, 1), p[4])
 317             p[0] = self.BuildProduction('Type', p, 1, any_node)
 318
 319     # [61]
 320     def p_UnionMemberTypes(self, p):
 321         """UnionMemberTypes : OR UnionMemberType UnionMemberTypes
 322                             |"""
 323         if len(p) > 2:
 324             p[0] = ListFromConcat(p[2], p[3])
 325
 326     # [70] Override base parser to remove non-standard sized array
 327     # FIXME: Upstream
 328     def p_TypeSuffix(self, p):
 329         """TypeSuffix : '[' ']' TypeSuffix
 330                       | '?' TypeSuffixStartingWithArray
 331                       |"""
 332         if len(p) == 4:
 333             p[0] = self.BuildProduction('Array', p, 1, p[3])
 334         elif len(p) == 3:
 335             p[0] = ListFromConcat(self.BuildTrue('NULLABLE'), p[2])
 336
 337     # Blink extension: Add support for string literal Extended Attribute values
 338     def p_ExtendedAttributeStringLiteral(self, p):
 339         """ExtendedAttributeStringLiteral : identifier '=' StringLiteral """
 340         def unwrap_string(ls):
 341             """Reach in and grab the string literal's "NAME"."""
 342             return ls[1].value
 343
 344         value = self.BuildAttribute('VALUE', unwrap_string(p[3]))
 345         p[0] = self.BuildNamed('ExtAttribute', p, 1, value)
 346
 347     # Blink extension: Add support for compound Extended Attribute values over string literals ("A","B")
 348     def p_ExtendedAttributeStringLiteralList(self, p):
 349         """ExtendedAttributeStringLiteralList : identifier '=' '(' StringLiteralList ')' """
 350         value = self.BuildAttribute('VALUE', p[4])
 351         p[0] = self.BuildNamed('ExtAttribute', p, 1, value)
 352
 353     # Blink extension: one or more string literals. The values aren't propagated as literals,
 354     # but their by their value only.
 355     def p_StringLiteralList(self, p):
 356         """StringLiteralList : StringLiteral ',' StringLiteralList
 357                              | StringLiteral"""
 358         def unwrap_string(ls):
 359             """Reach in and grab the string literal's "NAME"."""
 360             return ls[1].value
 361
 362         if len(p) > 3:
 363             p[0] = ListFromConcat(unwrap_string(p[1]), p[3])
 364         else:
 365             p[0] = ListFromConcat(unwrap_string(p[1]))
 366
 367     def __init__(self,
 368                  # common parameters
 369                  debug=False,
 370                  # local parameters
 371                  rewrite_tables=False,
 372                  # idl_parser parameters
 373                  lexer=None, verbose=False, mute_error=False,
 374                  # yacc parameters
 375                  outputdir='', optimize=True, write_tables=False,
 376                  picklefile=None):
 377         if debug:
 378             # Turn off optimization and caching, and write out tables,
 379             # to help debugging
 380             optimize = False
 381             outputdir = None
 382             picklefile = None
 383             write_tables = True
 384         if outputdir:
 385             picklefile = picklefile or os.path.join(outputdir, 'parsetab.pickle')
 386             if rewrite_tables:
 387                 try:
 388                     os.unlink(picklefile)
 389                 except OSError:
 390                     pass
 391
 392         lexer = lexer or BlinkIDLLexer(debug=debug,
 393                                        outputdir=outputdir,
 394                                        optimize=optimize)
 395         self.lexer = lexer
 396         self.tokens = lexer.KnownTokens()
 397         # Using SLR (instead of LALR) generates the table faster,
 398         # but produces the same output. This is ok b/c Web IDL (and Blink IDL)
 399         # is an SLR grammar (as is often the case for simple LL(1) grammars).
 400         #
 401         # Optimized mode substantially decreases startup time (by disabling
 402         # error checking), and also allows use of Python's optimized mode.
 403         # See: Using Python's Optimized Mode
 404         # http://www.dabeaz.com/ply/ply.html#ply_nn38
 405         #
 406         # |picklefile| allows simpler importing than |tabmodule| (parsetab.py),
 407         # as we don't need to modify sys.path; virtually identical speed.
 408         # See: CHANGES, Version 3.2
 409         # http://ply.googlecode.com/svn/trunk/CHANGES
 410         self.yaccobj = yacc.yacc(module=self,
 411                                  start=STARTING_SYMBOL,
 412                                  method='SLR',
 413                                  debug=debug,
 414                                  optimize=optimize,
 415                                  write_tables=write_tables,
 416                                  picklefile=picklefile)
 417         self.parse_debug = debug
 418         self.verbose = verbose
 419         self.mute_error = mute_error
 420         self._parse_errors = 0
 421         self._parse_warnings = 0
 422         self._last_error_msg = None
 423         self._last_error_lineno = 0
 424         self._last_error_pos = 0
 425
 426
 427 ################################################################################
 428
 429 def main(argv):
 430     # If file itself executed, cache lex/parse tables
 431     try:
 432         outputdir = argv[1]
 433     except IndexError as err:
 434         print 'Usage: %s OUTPUT_DIR' % argv[0]
 435         return 1
 436     blink_idl_lexer.main(argv)
 437     # Important: rewrite_tables=True causes the cache file to be deleted if it
 438     # exists, thus making sure that PLY doesn't load it instead of regenerating
 439     # the parse table.
 440     parser = BlinkIDLParser(outputdir=outputdir, rewrite_tables=True)
 441
 442
 443 if __name__ == '__main__':
 444     sys.exit(main(sys.argv))