Home | History | Annotate | Download | only in scripts 
      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         'namespace': '',
    102         'namespacePrefix': '',
    103         'namespaceURI': '',
    104         'fallbackInterfaceName': '',
    105         'fallbackJSInterfaceName': '',
    106     }
    107 
    108     def __init__(self, in_file_paths):
    109         super(ElementLookupTrieWriter, self).__init__(in_file_paths)
    110         self._tags = [entry['name'] for entry in self.in_file.name_dictionaries]
    111         self._namespace = self.in_file.parameters['namespace'].strip('"')
    112         self._outputs = {
    113             (self._namespace + 'ElementLookupTrie.h'): self.generate_header,
    114             (self._namespace + 'ElementLookupTrie.cpp'): self.generate_implementation,
    115         }
    116 
    117     @template_expander.use_jinja('ElementLookupTrie.h.tmpl')
    118     def generate_header(self):
    119         return {
    120             'namespace': self._namespace,
    121         }
    122 
    123     @template_expander.use_jinja('ElementLookupTrie.cpp.tmpl')
    124     def generate_implementation(self):
    125         # First sort, so groupby works
    126         self._tags.sort(key=lambda tag: (len(tag), tag))
    127         # Group tags by length
    128         length_tags = ((k, g) for k, g in groupby(self._tags, len))
    129 
    130         return {
    131             'namespace': self._namespace,
    132             'length_tries': ((length, _trie(tags, 0))
    133                              for length, tags in length_tags),
    134         }
    135 
    136 
    137 if __name__ == '__main__':
    138     in_generator.Maker(ElementLookupTrieWriter).main(sys.argv)
    139