Experimental parser: cleanup code generator a bit

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 57 matching lines @@
     def cmp(left, right):
       return TransitionKey.canonical_compare(left[0], right[0])
     transitions = sorted(transitions, cmp)
     # 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
+    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, don't bother updating stats
+          # 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 not in unique_transitions
           unique_transitions[r] = transition_id
+          if r != 'no_match':
+            total_transitions += 1
         else:
           raise Exception()
       if keys:
         transitions.append((keys, transition_id))
     # delay zero transition until last
     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' : len(transitions) == 0,
+      'can_elide_read' : total_transitions == 0,
       'is_eos_handler' : False,
       'inline' : False,
       'must_not_inline' : False,
       # transitions for code generator
       'if_transitions' : [],
       'switch_transitions' : [],
       'deferred_transitions' : [],
       'unique_transitions' : unique_transitions,
       # state actions
       'entry_action' : entry_action,
       'match_action' : match_action,
-      # statistics for states
+      # 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 __set_inline(self, count, state):
     inline = False
     if state['must_not_inline']:
       inline = False
     # inline terminal states
-    elif not state['transitions']:
+    elif not state['total_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']:
+        if self.__dfa_states[state_id]['total_transitions']:
           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 93 matching lines @@
       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']
+      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)
@@ skipping 39 matching lines @@
         else:
           states[target_id]['can_elide_read'] = False
           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
+    # 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']
 
   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',
       'deferred_transitions']
     end_offset = start_id + count
     assert len(self.__dfa_states) == end_offset
     total_nodes_created = 0
     for state_id in range(start_id, end_offset):
       state = self.__dfa_states[state_id]
-      # this will be ignored during code generation,
-      # and it's needed as a template, so don't rewrite
-      if state['inline'] == True:
-        continue
-      # these is a new inline state, now mark as inline and rewrite
-      if state['inline'] == None:
-        state['inline'] = True
+      if state['inline']:
+        if not 'just_generated_inline_state' in state:
+          # this will be ignored during code generation,
+          # and it's needed as a template, so don't rewrite
+          continue
+        # these is a new inline state, rewrite
+        del state['just_generated_inline_state']
+      assert not 'just_generated_inline_state' in state
       inline_mapping = inline_mapping_in.copy()
       def generate_jump((key, target_id)):
         jump_type = 'state_entry'
         if self.__dfa_states[target_id]['inline']:
           # 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']
+        # 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)
@@ skipping 41 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])