• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
30from itertools import groupby, islice
31import sys
32
33import in_generator
34import template_expander
35
36PARAMETER_NAME = 'data'
37
38
39def _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
82def _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
89class ElementLookupTrieWriter(in_generator.Writer):
90    # FIXME: Inherit all these from somewhere.
91    defaults = {
92        'JSInterfaceName': None,
93        'constructorNeedsCreatedByParser': None,
94        'constructorNeedsFormElement': None,
95        'contextConditional': None,
96        'interfaceName': None,
97        'noConstructor': None,
98        'runtimeEnabled': None,
99    }
100    default_parameters = {
101        'attrsNullNamespace': None,
102        'namespace': '',
103        'namespacePrefix': '',
104        'namespaceURI': '',
105        'fallbackInterfaceName': '',
106        'fallbackJSInterfaceName': '',
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
138if __name__ == '__main__':
139    in_generator.Maker(ElementLookupTrieWriter).main(sys.argv)
140