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