Experimental parser: remove match actions

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 31 matching lines @@
                switching = True,
                debug_print = False,
                log = False):
     if minimize_default:
       dfa = rule_processor.default_automata().minimal_dfa()
     else:
       dfa = rule_processor.default_automata().dfa()
     self.__dfa = dfa
     self.__default_action = rule_processor.default_action()
     self.__debug_print = debug_print
-    self.__start_node_number = self.__dfa.start_state().node_number()
     self.__log = log
     self.__inline = inline
     self.__switching = switching
     self.__jump_table = []
 
   __jump_labels = ['state_entry', 'after_entry_code']
 
   @staticmethod
   def __transform_state(encoding, state):
     # action data
-    action = state.action()
-    entry_action = action.entry_action()
-    match_action = action.match_action()
     # generate ordered transitions
     transitions = map(lambda (k, v) : (k, v.node_number()),
                       state.key_state_iter())
     transitions = sorted(
       transitions, cmp = TransitionKey.compare, key = lambda x : x[0])
     # map transition keys to disjoint ranges and collect stats
     disjoint_keys = []
     unique_transitions = {}
     old_transitions = transitions
     transitions = []
     (class_keys, distinct_keys, ranges) = (0, 0, 0)
     zero_transition = None
+    omega_transition = None
     total_transitions = 0
     for key, transition_id in old_transitions:
       keys = []
       for (t, r) in key.range_iter(encoding):
         if t == 'CLASS':
           class_keys += 1
           keys.append((t, r))
         elif t == 'PRIMARY_RANGE':
           distinct_keys += r[1] - r[0] + 1
           ranges += 1
           # split 0 out of range
           assert r[0] >= 0
           if r[0] == 0:
             assert zero_transition == None
             zero_transition = transition_id
             if r[0] == r[1]:
               continue
             r = (r[0] + 1, r[1])
           keys.append((t, r))
         elif t == 'UNIQUE':
-          assert r == 'no_match' or r == 'eos'
+          assert r == 'eos'
           assert r not in unique_transitions
           unique_transitions[r] = transition_id
           if r != 'no_match':
             total_transitions += 1
+        elif t == 'OMEGA':
+          assert not omega_transition
+          omega_transition = transition_id
+          assert transition_id  # TODO(dcarney): fix
+          total_transitions += 1
         else:
           raise Exception()
       if keys:
         transitions.append((keys, transition_id))
-    # delay zero transition until last
+    # delay zero transition until after all encoded keys
     if zero_transition != None:
       transitions.append(([('PRIMARY_RANGE', (0, 0))], transition_id))
       ranges += 1
     total_transitions += len(transitions)
     return {
       'node_number' : None,
       'original_node_number' : state.node_number(),
       'transitions' : transitions,
       # flags for code generator
-      'can_elide_read' : total_transitions == 0,
+      'elide_read' : (total_transitions == 0 or
+                      (total_transitions == 1 and omega_transition)),
       'is_eos_handler' : False,
       'inline' : False,
       'must_not_inline' : False,
       # transitions for code generator
       'if_transitions' : [],
       'switch_transitions' : [],
       'deferred_transitions' : [],
       'unique_transitions' : unique_transitions,
+      'omega_transition' : omega_transition,
       # state actions
-      'entry_action' : entry_action,
-      'match_action' : match_action,
+      'action' : state.action(),
       # statistics for state
       'total_transitions' : total_transitions,
       'class_keys' : class_keys,
       'distinct_keys' : distinct_keys,
       'ranges' : ranges,
       # record of which entry points will be needed
       'entry_points' : {k : False for k in CodeGenerator.__jump_labels}
     }
 
   def __register_jump(self, node_id, label):
     if label != 'inline':
       assert label in CodeGenerator.__jump_labels
       state = self.__dfa_states[node_id]['entry_points'][label] = True
     self.__jump_table.append((node_id, label))
     return len(self.__jump_table) - 1
 
+  def __terminates_immediately(self, state_id):
+    transition_count = self.__dfa_states[state_id]['total_transitions']
+    if transition_count == 0:
+      return True
+    omega_transition_id = self.__dfa_states[state_id]['omega_transition']
+    if transition_count == 1 and omega_transition_id:
+      return self.__terminates_immediately(omega_transition_id)
+    return False
+
   def __set_inline(self, count, state):
     inline = False
     if state['must_not_inline']:
       inline = False
     # inline terminal states
-    elif not state['total_transitions']:
+    elif self.__terminates_immediately(state['node_number']):
       inline = True
     # inline next to terminal states with 1 or 2 transitions
     elif state['distinct_keys'] < 3 and state['class_keys'] == 0:
       inline = True
-      # ensure state terminates in 1 step
+      # ensure state terminates in 1 step, excluding omega transitions
       for key, state_id in state['transitions']:
-        if self.__dfa_states[state_id]['total_transitions']:
+        if not self.__terminates_immediately(state_id):
           inline = False
           break
     state['inline'] = inline
     return count + 1 if inline else count
 
   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'])
@@ skipping 81 matching lines @@
   def __reorder(current_node_number, id_map, dfa_states):
     current_node = id_map[current_node_number]
     if current_node['node_number'] != None:
       return
     current_node['node_number'] = len(dfa_states)
     dfa_states.append(current_node)
     for (key, node_number) in current_node['transitions']:
       CodeGenerator.__reorder(node_number, id_map, dfa_states)
     for node_number in current_node['unique_transitions'].values():
       CodeGenerator.__reorder(node_number, id_map, dfa_states)
+    if current_node['omega_transition'] != None:
+      CodeGenerator.__reorder(
+        current_node['omega_transition'], id_map, dfa_states)
 
   @staticmethod
   def __mark_eos_states(dfa_states, eos_states):
     for state_id in eos_states:
       state = dfa_states[state_id]
       state['is_eos_handler'] = True
       state['must_not_inline'] = True
-      assert state['match_action']
-      assert not state['entry_action']
-      assert not state['total_transitions']
+      # TODO(dcarney): bring back
+      # assert state['action']
+      # assert not state['total_transitions']
 
   def __build_dfa_states(self):
     dfa_states = []
     self.__dfa.visit_all_states(lambda state, acc: dfa_states.append(state))
     encoding = self.__dfa.encoding()
     f = lambda state : CodeGenerator.__transform_state(encoding, state)
     dfa_states = map(f, dfa_states)
     id_map = {x['original_node_number'] : x for x in dfa_states}
     dfa_states = []
-    CodeGenerator.__reorder(self.__start_node_number, id_map, dfa_states)
+    start_node_number = self.__dfa.start_state().node_number()
+    CodeGenerator.__reorder(start_node_number, id_map, dfa_states)
     # store states
     eos_states = set([])
+    remap = lambda state_id : id_map[state_id]['node_number']
     def f((key, original_node_number)):
-      return (key, id_map[original_node_number]['node_number'])
+      return (key, remap(original_node_number))
     for state in dfa_states:
       state['transitions'] = map(f, state['transitions'])
-      state['unique_transitions'] = {k : id_map[v]['node_number']
+      state['unique_transitions'] = {k : remap(v)
           for k, v in state['unique_transitions'].items()}
+      if state['omega_transition'] != None:
+        state['omega_transition'] = remap(state['omega_transition'])
       if 'eos' in state['unique_transitions']:
         eos_states.add(state['unique_transitions']['eos'])
-    assert id_map[self.__start_node_number]['node_number'] == 0
+    assert id_map[start_node_number]['node_number'] == 0
     assert len(dfa_states) == self.__dfa.node_count()
     # mark eos states
     self.__mark_eos_states(dfa_states, eos_states)
     self.__dfa_states = dfa_states
 
-  def __rewrite_gotos(self):
-    goto_map = {}
-    states = self.__dfa_states
-    for state in states:
-      if (state['match_action'].name() == 'do_stored_token'):
-        assert not state['match_action'].args()[0] in goto_map
-        goto_map[state['match_action'].args()[0]] = state['node_number']
-    mapped_actions = set([
-      'store_harmony_token_and_goto',
-      'store_token_and_goto',
-      'goto_start'])
-    for state in states:
-      if not state['match_action']:
-        continue
-      action = state['match_action'].name()
-      if action in mapped_actions:
-        value = state['match_action'].args()
-        target_id = goto_map[value[-1]]
-        states[target_id]['must_not_inline'] = True
-        if action != 'goto_start':
-          state['can_elide_read'] = False
-          label = 'after_entry_code'
-        else:
-          states[target_id]['can_elide_read'] = False
-          label = 'state_entry'
-        jump_label = self.__register_jump(target_id, label)
-        new_args = list(value[:-1]) + [str(jump_label)]
-        state['match_action'] = Term(action, *new_args)
-
   def __inlined_state(self, target_id):
     state = deepcopy(self.__dfa_states[target_id])
     state['node_number'] = len(self.__dfa_states)
     self.__dfa_states.append(state)
     # mark as just generated, so it will correctly rewritten
     state['just_generated_inline_state'] = True
     # clear entry points
     state['entry_points'] = {k : False for k in CodeGenerator.__jump_labels}
     return state['node_number']
 
@@ skipping 23 matching lines @@
           # generate at most one inline state for all transitions
           if not target_id in inline_mapping:
             inline_mapping[target_id] = self.__inlined_state(target_id)
             jump_type = 'inline'
           target_id = inline_mapping[target_id]
         else:
           assert not target_id in inline_mapping
         return (key, self.__register_jump(target_id, jump_type))
       for name in transition_names:
         state[name] = map(generate_jump, state[name])
+      if state['omega_transition'] != None:
+        state['omega_transition'] = generate_jump(
+          (None, state['omega_transition']))[1]
       if 'eos' in state['unique_transitions']:
         eos_state_id = state['unique_transitions']['eos']
         # eos state is not inlined, don't need to look in map
         assert not self.__dfa_states[eos_state_id]['inline']
         jump = self.__register_jump(eos_state_id, 'state_entry')
         state['unique_transitions']['eos'] = jump
       # now rewrite all nodes created
       nodes_created = len(inline_mapping) - len(inline_mapping_in)
       assert len(self.__dfa_states) == (
         end_offset + total_nodes_created + nodes_created)
       if nodes_created == 0:
         continue
       created = self.__rewrite_transitions_to_jumps(
         end_offset + total_nodes_created, nodes_created, inline_mapping)
       total_nodes_created += nodes_created + created
     return total_nodes_created
 
   def process(self):
 
     self.__build_dfa_states()
     dfa_states = self.__dfa_states
     # split transitions
     switched = reduce(self.__split_transitions, dfa_states, 0)
     if self.__log:
       print "%s states use switch (instead of if)" % switched
     # rewrite deferred transitions
     for state in dfa_states:
       self.__rewrite_deferred_transitions(state)
-    # rewrite gotos
-    self.__rewrite_gotos()
     # set nodes to inline
     if self.__inline:
       inlined = reduce(self.__set_inline, dfa_states, 0)
       if self.__log:
         print "%s states inlined" % inlined
     # rewrite transitions to use jumps
     inlined_nodes = self.__rewrite_transitions_to_jumps(0, len(dfa_states), {})
     if self.__log:
       print "%s inlined nodes created" % inlined_nodes
     # mark the entry point in case there are implicit jumps to it
     self.__dfa_states[0]['entry_points']['state_entry'] = True
 
     default_action = self.__default_action
-    assert(default_action and default_action.match_action())
-    default_action = default_action.match_action()
+    assert default_action
 
     sys.path.append(os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
     template_env = jinja2.Environment(
       loader = jinja2.PackageLoader('lexer_generator', '.'),
       undefined = jinja2.StrictUndefined)
     template = template_env.get_template('code_generator.jinja')
 
     encoding = self.__dfa.encoding()
     char_types = {'latin1': 'uint8_t', 'utf16': 'uint16_t', 'utf8': 'int8_t'}
     char_type = char_types[encoding.name()]
 
     return template.render(
       start_node_number = 0,
       debug_print = self.__debug_print,
       default_action = default_action,
       dfa_states = dfa_states,
       jump_table = self.__jump_table,
       encoding = encoding.name(),
       char_type = char_type,
       upper_bound = encoding.primary_range()[1])