Experimental parser: better eos handling

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 36 matching lines @@
       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']
+  __jump_labels = ['state_entry', 'after_entry_code', 'before_match']
 
   @staticmethod
   def __transform_state(encoding, state):
     # action data
     action = state.action()
     entry_action = None if not action else action.entry_action()
     match_action = None if not action else action.match_action()
     # generate ordered transitions
     transitions = map(lambda (k, v) : (k, v.node_number()),
                       state.transitions().items())
@@ skipping 17 matching lines @@
           ranges += 1
           keys.append((t, r))
         elif t == 'UNIQUE':
           assert r == 'no_match' or r == 'eos'
           assert r not in unique_transitions
           unique_transitions[r] = transition_id
         else:
           raise Exception()
       if keys:
         transitions.append((keys, transition_id))
-    # eos_transitions is for a followup cl
     return {
       'node_number' : None,
       'original_node_number' : state.node_number(),
       'transitions' : transitions,
       # flags for code generator
       'can_elide_read' : len(transitions) == 0,
       'is_eos_handler' : False,
       'inline' : None,
       'must_not_inline' : False,
       # transitions for code generator
@@ skipping 16 matching lines @@
   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 __set_inline(self, count, state):
     assert state['inline'] == None
     inline = False
-    # inline terminal states
     if state['must_not_inline']:
       inline = False
+    # inline terminal states
     elif not state['transitions']:
       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
       for key, state_id in state['transitions']:
         if self.__dfa_states[state_id]['transitions']:
           inline = False
           break
@@ skipping 41 matching lines @@
 
   def __rewrite_deferred_transitions(self, state):
     assert not state['long_char_transitions']
     transitions = state['deferred_transitions']
     if not transitions:
       return
     encoding = self.__dfa.encoding()
     bom = 'byte_order_mark'
     catch_all = 'non_primary_everything_else'
     all_classes = set(encoding.class_name_iter())
-    fast_classes = set(['eos', 'zero'])
+    fast_classes = set([])
     call_classes = all_classes - fast_classes - set([bom, catch_all])
     def remap_transition(class_name):
       if class_name in call_classes:
         return ('LONG_CHAR_CLASS', 'call', self.__call_map[class_name])
       if class_name == bom:
         return ('LONG_CHAR_CLASS', class_name)
       raise Exception(class_name)
     fast_transitions = []
     long_class_transitions = []
     long_class_map = {}
@@ skipping 44 matching lines @@
     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)
 
+  @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['transitions']
+      assert not state['unique_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)
+    # store states
+    eos_states = set([])
     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'])
+      state['unique_transitions'] = {k : id_map[v]['node_number']
+          for k, v in state['unique_transitions'].items()}
+      if 'eos' in state['unique_transitions']:
+        eos_states.add(state['unique_transitions']['eos'])
     assert id_map[self.__start_node_number]['node_number'] == 0
     assert len(dfa_states) == self.__dfa.node_count()
-    # store states
+    # 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'] and
           state['match_action'][0] == 'do_stored_token'):
         assert not state['match_action'][1] in goto_map
         goto_map[state['match_action'][1]] = state['node_number']
@@ skipping 17 matching lines @@
           label = 'state_entry'
         jump_label = self.__register_jump(target_id, label)
         state['match_action'] = (action, tuple(list(value[:-1]) + [jump_label]))
 
   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 inline as none, to be correctly handled below
     state['inline'] = None
-    # clear transitions, they shouldn't be used anymore
-    state['transitions'] = []
     # clear entry points
     state['entry_points'] = {k : False for k in CodeGenerator.__jump_labels}
     return state['node_number']
 
   def __rewrite_transitions_to_jumps(self, start_id, count, inline_mapping_in):
     # order here should match the order of code generation
     transition_names = [
       'switch_transitions',
       'if_transitions',
       'long_char_transitions',
@@ skipping 17 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 'eos' in state['unique_transitions']:
+        # eos state is not inlined
+        eos_state_id = state['unique_transitions']['eos']
+        jump = self.__register_jump(eos_state_id, 'state_entry')
+        state['unique_transitions']['eos'] = jump
+      elif state['transitions']:
+        jump = self.__register_jump(state_id, 'before_match')
+        state['jump_before_match'] = 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
@@ skipping 39 matching lines @@
 
     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])