Experimental parser: add everything_else class

tools/lexer_generator/code_generator.py

 # Copyright 2013 the V8 project authors. All rights reserved.
 # Redistribution and use in source and binary forms, with or without
 # modification, are permitted provided that the following conditions are
 # met:
 #
 #     * Redistributions of source code must retain the above copyright
 #       notice, this list of conditions and the following disclaimer.
 #     * Redistributions in binary form must reproduce the above
 #       copyright notice, this list of conditions and the following
 #       disclaimer in the documentation and/or other materials provided
@@ skipping 112 matching lines @@
       elif t == 'LATIN_1':
         distinct_keys += r[1] - r[0] + 1
         ranges += 1
       else:
         raise Exception()
     return {
       'node_number' : state.node_number(),
       'original_node_number' : state.node_number(),
       'transitions' : transitions,
       'switch_transitions' : [],
+      'deferred_transitions' : [],
       'disjoint_keys' : disjoint_keys,
       'inline' : None,
       'depth' : None,
       'action' : action,
       'entry_action' : entry_action,
       'match_action' : match_action,
       'class_keys' : class_keys,
       'distinct_keys' : distinct_keys,
       'ranges' : ranges
     }
@@ skipping 17 matching lines @@
     elif state['distinct_keys'] < 3 and state['class_keys'] == 0:
       inline = True
       # ensure state terminates in 1 step
       for key, state_id in state['transitions']:
         if self.__dfa_states[state_id]['transitions']:
           inline = False
           break
     state['inline'] = inline
     return count + 1 if inline else count
 
-  @staticmethod
-  def __split_transitions(split_count, state):
+  def __split_transitions(self, split_count, state):
     '''Goes through the transitions for 'state' and decides which of them should
     use the if statement and which should use the switch statement.'''
     assert not state['switch_transitions']
     (distinct_keys, ranges) = (state['distinct_keys'], state['ranges'])
-    if distinct_keys <= 7 or float(distinct_keys)/float(ranges) >= 7.0:
-      return split_count
+    no_switch = distinct_keys <= 7 or float(distinct_keys)/float(ranges) >= 7.0
+    if_transitions = []
     switch_transitions = []
-    if_transitions = []
+    deferred_transitions = []
     for (ranges, node_id) in state['transitions']:
       i = []
       s = []
+      d = []
       for r in ranges:
+        # all class checks will be deferred to after all other checks
         if r[0] == 'CLASS':
+          d.append(r)
+        elif no_switch:
           i.append(r)
         else:
           s.append(r[1])
       if i:
         if_transitions.append((i, node_id))
       if s:
         switch_transitions.append((s, node_id))
+      if d:
+        deferred_transitions.append((d, node_id))
     state['transitions'] = if_transitions
     state['switch_transitions'] = switch_transitions
-    return split_count + 1
+    state['deferred_transitions'] = deferred_transitions
+    return split_count + (0 if no_switch else 1)
 
   def __canonicalize_traversal(self):
     dfa_states = []
     self.__dfa.visit_all_states(lambda state, acc: dfa_states.append(state))
     dfa_states = map(CodeGenerator.__transform_state, dfa_states)
     id_map = {x['original_node_number'] : x for x in dfa_states}
     CodeGenerator.__compute_depths(self.__start_node_number, 1, id_map)
     dfa_states = sorted(dfa_states, cmp=self.__state_cmp)
     # remap all node numbers
     for i, state in enumerate(dfa_states):
       state['node_number'] = i
     def f((key, original_node_number)):
       return (key, id_map[original_node_number]['node_number'])
     for state in dfa_states:
       state['transitions'] = map(f, state['transitions'])
     assert id_map[self.__start_node_number]['node_number'] == 0
     assert len(dfa_states) == self.__dfa.node_count()
     # store states
     self.__dfa_states = dfa_states
     # set nodes to inline
     if self.__inline:
       inlined = reduce(self.__set_inline, dfa_states, 0)
       if self.__log:
         print "%s states inlined" % inlined
     elif self.__log:
       print "no inlining"
     # split transitions
-    if self.__switching:
-      switched = reduce(CodeGenerator.__split_transitions, dfa_states, 0)
-      if self.__log:
-        print "%s states use switch (instead of if)" % switched
-    elif self.__log:
-      print "no switching"
+    switched = reduce(self.__split_transitions, dfa_states, 0)
+    if self.__log:
+      print "%s states use switch (instead of if)" % switched
 
   def process(self):
 
     self.__canonicalize_traversal()
 
     dfa_states = self.__dfa_states
 
     default_action = self.__default_action
     assert(default_action and default_action.match_action())
     default_action = default_action.match_action()
@@ skipping 10 matching lines @@
       char_type = 'uint16_t'
     else:
       raise Exception('Unsupported encoding %s' % encoding)
     return template.render(
       start_node_number = 0,
       debug_print = self.__debug_print,
       default_action = default_action,
       dfa_states = dfa_states,
       encoding = self.__encoding,
       char_type = char_type)