Factor and simplify generation of the lookup trie used for HTMLLookupTrie.

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

Index: third_party/WebKit/Source/build/scripts/make_element_lookup_trie.py
diff --git a/third_party/WebKit/Source/build/scripts/make_element_lookup_trie.py b/third_party/WebKit/Source/build/scripts/make_element_lookup_trie.py
index 90b696d0c22b83aa0eb1de8fc69b3b559431e477..5d86ffc26db1bd7d4bd2efe95f24303620cc70c9 100755
--- a/third_party/WebKit/Source/build/scripts/make_element_lookup_trie.py
+++ b/third_party/WebKit/Source/build/scripts/make_element_lookup_trie.py
@@ -27,64 +27,12 @@
 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
-from itertools import groupby, islice
 import sys
 
 import in_generator
+import trie_builder
 import template_expander
 
-PARAMETER_NAME = 'data'
-
-
-def _trie(tags, index):
-    """Make a trie from list of tags, starting at index.
-
-    Resulting trie is partly space-optimized (semi-radix tree): once have only
-    one string left, compact the entire branch to one leaf node.
-    However, does not compact branch nodes with a single child. (FIXME)
-
-    Returns:
-        (char, subtrie, tag, conditions): (char, trie, str, list)
-            code generation differs between branch nodes and leaf nodes,
-            hence need different data for each.
-
-    Arguments:
-        tags: sorted list
-            (sorted needed by groupby, list needed by len)
-        index: index at which to branch
-            (assumes prior to this index strings have a common prefix)
-    """
-    def trie_node(char, subtags_iter):
-        # Pass in |char| so we can include in same tuple without unpacking
-        subtags = list(subtags_iter)  # need list for len
-        if len(subtags) == 1:  # terminal node, no subtrie
-            subtrie = None
-            tag = subtags[0]
-            conditions = _conditions(tag, index + 1)
-        else:
-            subtrie = _trie(subtags, index + 1)
-            tag = None
-            conditions = None
-        return char, subtrie, tag, conditions
-
-    # Group by char at index
-    def char_at_index(tag):
-        return tag[index].lower()
-
-    char_subtags = ((k, g) for k, g in groupby(tags, char_at_index))
-
-    # FIXME: if all subtags have a common prefix, merge with child
-    # and skip the switch in the generated code
-
-    return (trie_node(char, subtags) for char, subtags in char_subtags)
-
-
-def _conditions(tag, index):
-    # boolean conditions to check suffix; corresponds to compacting branch
-    # with a single leaf
-    return ["%s[%d] == '%c'" % (PARAMETER_NAME, i, c.lower())
-            for i, c in islice(enumerate(tag), index, None)]
-
 
 class ElementLookupTrieWriter(in_generator.Writer):
     # FIXME: Inherit all these from somewhere.
@@ -108,7 +56,9 @@ class ElementLookupTrieWriter(in_generator.Writer):
 
     def __init__(self, in_file_paths):
         super(ElementLookupTrieWriter, self).__init__(in_file_paths)
-        self._tags = [entry['name'] for entry in self.in_file.name_dictionaries]
+        self._tags = {}
+        for entry in self.in_file.name_dictionaries:
+            self._tags[entry['name']] = entry['name']
         self._namespace = self.in_file.parameters['namespace'].strip('"')
         self._outputs = {
             (self._namespace + 'ElementLookupTrie.h'): self.generate_header,
@@ -123,15 +73,9 @@ class ElementLookupTrieWriter(in_generator.Writer):
 
     @template_expander.use_jinja('ElementLookupTrie.cpp.tmpl')
     def generate_implementation(self):
-        # First sort, so groupby works
-        self._tags.sort(key=lambda tag: (len(tag), tag))
-        # Group tags by length
-        length_tags = ((k, g) for k, g in groupby(self._tags, len))
-
         return {
             'namespace': self._namespace,
-            'length_tries': ((length, _trie(tags, 0))
-                             for length, tags in length_tags),
+            'length_tries': trie_builder.trie_list_by_str_length(self._tags)
         }