third_party/WebKit/Source/build/scripts/make_element_lookup_trie.py

   1 #!/usr/bin/env python
   2 # Copyright (C) 2013 Google Inc. All rights reserved.
   3 #
   4 # Redistribution and use in source and binary forms, with or without
   5 # modification, are permitted provided that the following conditions are
   6 # met:
   7 #
   8 #     * Redistributions of source code must retain the above copyright
   9 # notice, this list of conditions and the following disclaimer.
  10 #     * Redistributions in binary form must reproduce the above
  11 # copyright notice, this list of conditions and the following disclaimer
  12 # in the documentation and/or other materials provided with the
  13 # distribution.
  14 #     * Neither the name of Google Inc. nor the names of its
  15 # contributors may be used to endorse or promote products derived from
  16 # this software without specific prior written permission.
  17 #
  18 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30 from itertools import groupby, islice
  31 import sys
  32
  33 import in_generator
  34 import template_expander
  35
  36 PARAMETER_NAME = 'data'
  37
  38
  39 def _trie(tags, index):
  40     """Make a trie from list of tags, starting at index.
  41
  42     Resulting trie is partly space-optimized (semi-radix tree): once have only
  43     one string left, compact the entire branch to one leaf node.
  44     However, does not compact branch nodes with a single child. (FIXME)
  45
  46     Returns:
  47         (char, subtrie, tag, conditions): (char, trie, str, list)
  48             code generation differs between branch nodes and leaf nodes,
  49             hence need different data for each.
  50
  51     Arguments:
  52         tags: sorted list
  53             (sorted needed by groupby, list needed by len)
  54         index: index at which to branch
  55             (assumes prior to this index strings have a common prefix)
  56     """
  57     def trie_node(char, subtags_iter):
  58         # Pass in |char| so we can include in same tuple without unpacking
  59         subtags = list(subtags_iter)  # need list for len
  60         if len(subtags) == 1:  # terminal node, no subtrie
  61             subtrie = None
  62             tag = subtags[0]
  63             conditions = _conditions(tag, index + 1)
  64         else:
  65             subtrie = _trie(subtags, index + 1)
  66             tag = None
  67             conditions = None
  68         return char, subtrie, tag, conditions
  69
  70     # Group by char at index
  71     def char_at_index(tag):
  72         return tag[index].lower()
  73
  74     char_subtags = ((k, g) for k, g in groupby(tags, char_at_index))
  75
  76     # FIXME: if all subtags have a common prefix, merge with child
  77     # and skip the switch in the generated code
  78
  79     return (trie_node(char, subtags) for char, subtags in char_subtags)
  80
  81
  82 def _conditions(tag, index):
  83     # boolean conditions to check suffix; corresponds to compacting branch
  84     # with a single leaf
  85     return ["%s[%d] == '%c'" % (PARAMETER_NAME, i, c.lower())
  86             for i, c in islice(enumerate(tag), index, None)]
  87
  88
  89 class ElementLookupTrieWriter(in_generator.Writer):
  90     # FIXME: Inherit all these from somewhere.
  91     defaults = {
  92         'JSInterfaceName': None,
  93         'constructorNeedsCreatedByParser': None,
  94         'constructorNeedsFormElement': None,
  95         'interfaceName': None,
  96         'noConstructor': None,
  97         'runtimeEnabled': None,
  98     }
  99     default_parameters = {
 100         'attrsNullNamespace': None,
 101         'export': '',
 102         'fallbackInterfaceName': '',
 103         'fallbackJSInterfaceName': '',
 104         'namespace': '',
 105         'namespacePrefix': '',
 106         'namespaceURI': '',
 107     }
 108
 109     def __init__(self, in_file_paths):
 110         super(ElementLookupTrieWriter, self).__init__(in_file_paths)
 111         self._tags = [entry['name'] for entry in self.in_file.name_dictionaries]
 112         self._namespace = self.in_file.parameters['namespace'].strip('"')
 113         self._outputs = {
 114             (self._namespace + 'ElementLookupTrie.h'): self.generate_header,
 115             (self._namespace + 'ElementLookupTrie.cpp'): self.generate_implementation,
 116         }
 117
 118     @template_expander.use_jinja('ElementLookupTrie.h.tmpl')
 119     def generate_header(self):
 120         return {
 121             'namespace': self._namespace,
 122         }
 123
 124     @template_expander.use_jinja('ElementLookupTrie.cpp.tmpl')
 125     def generate_implementation(self):
 126         # First sort, so groupby works
 127         self._tags.sort(key=lambda tag: (len(tag), tag))
 128         # Group tags by length
 129         length_tags = ((k, g) for k, g in groupby(self._tags, len))
 130
 131         return {
 132             'namespace': self._namespace,
 133             'length_tries': ((length, _trie(tags, 0))
 134                              for length, tags in length_tags),
 135         }
 136
 137
 138 if __name__ == '__main__':
 139     in_generator.Maker(ElementLookupTrieWriter).main(sys.argv)