Experimental parser: some tuple removal

tools/lexer_generator/dfa_optimizer.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
 #       with the distribution.
 #     * Neither the name of Google Inc. nor the names of its
 #       contributors may be used to endorse or promote products derived
 #       from this software without specific prior written permission.
 #
 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 # (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 transition_keys import TransitionKey
-from automaton import Action
+from automaton import Term, Action
 from dfa import Dfa
 
 # --- Optimization: Replacing tokens with gotos ---
 #
 # This optimization reduces the code size for grammars which have constructs
 # similar to keywords and identifiers. Consider the following grammar:
 #
 # "baz" <|token(BAZ)|>
 # "bazz" <|token(BAZZ)|>
 #
@@ skipping 128 matching lines @@
       for key, transition_state in state.key_state_iter():
         if not transition_state in incoming_transitions:
           incoming_transitions[transition_state] = []
         incoming_transitions[transition_state].append((key,state))
     dfa.visit_all_states(build_incoming_transitions)
 
     def is_replacement_candidate(state):
       action = state.action()
       if not action or not action.match_action():
         return False
-      if (action.match_action()[0] == 'token' or
-          action.match_action()[0] == 'harmony_token'):
+      if (action.match_action().name() == 'token' or
+          action.match_action().name() == 'harmony_token'):
         return True
       return False
 
     replacements = {}
     for state, incoming in incoming_transitions.items():
       if len(incoming) < 10:
         continue
       if not is_replacement_candidate(state):
         continue
       # check to see if incoming edges are matched by an outgoing edge
@@ skipping 28 matching lines @@
       'removals' : 0,
       'goto_start' : 0,
       'store_token_and_goto' : 0,
       'store_harmony_token_and_goto' : 0,
       }
     store_states = set([])
     # generate a store action to replace an existing action
     def replacement_action(old_action, transition_state):
       assert old_action.match_action()
       state_id = name(transition_state)
-      if old_action.match_action()[0] == 'token':
-        old_token = old_action.match_action()[1]
-        if (transition_state.action().match_action()[0] == 'token' and
-            transition_state.action().match_action()[1] == old_token):
+      if old_action.match_action().name() == 'token':
+        old_token = old_action.match_action().args()[0]
+        if (transition_state.action().match_action().name() == 'token' and
+            transition_state.action().match_action().args()[0] == old_token):
           # no need to store token
-          match_action = ('goto_start', (state_id,))
+          match_action = Term('goto_start', state_id)
           counters['goto_start'] += 1
         else:
           counters['store_token_and_goto'] += 1
-          match_action = ('store_token_and_goto', (old_token, state_id))
-      elif old_action.match_action()[0] == 'harmony_token':
-        match_action = ('store_harmony_token_and_goto',
-                        (old_action.match_action()[1][0],
-                         old_action.match_action()[1][1],
-                         old_action.match_action()[1][2],
-                         state_id))
+          match_action = Term('store_token_and_goto', old_token, state_id)
+      elif old_action.match_action().name() == 'harmony_token':
+        new_args = list(old_action.match_action().args()) + [state_id]
+        match_action = Term('store_harmony_token_and_goto', *new_args)
         counters['store_harmony_token_and_goto'] += 1
       else:
         raise Exception(old_action.match_action())
       return Action(old_action.entry_action(), match_action,
                     old_action.precedence())
     # map the old state to the new state, with fewer transitions and
     # goto actions
     def replace_state(state, acc):
       new_state = {
         'transitions' : {},
@@ skipping 17 matching lines @@
         new_state['action'] = replacement_action(state.action(), replacement)
         # will need to patch up transition_state
         store_states.add(name(transition_state))
       assert not state_replacements
     self.__dfa.visit_all_states(replace_state)
     # now patch up all states with stores
     start_name = name(self.__dfa.start_state())
     for state_id in store_states:
       old_action = states[state_id]['action']
       assert not old_action.entry_action()
-      assert old_action.match_action()[0] == 'token', 'unimplemented'
-      entry_action = ('store_token', old_action.match_action()[1])
-      match_action = ('do_stored_token', state_id)
+      assert old_action.match_action().name() == 'token', 'unimplemented'
+      entry_action = Term('store_token', old_action.match_action().args()[0])
+      match_action = Term('do_stored_token', state_id)
       precedence = old_action.precedence()
       states[state_id]['action'] = Action(
         entry_action, match_action, precedence)
       # The state might be only reachable via gotos; make sure it's connected in
       # the state graph by adding a bogus transition from the start state. This
       # transition doens't match any character.
       states[start_name]['transitions'][
           TransitionKey.unique('no_match')] = state_id
 
     if self.__log:
       print 'goto_start inserted %s' % counters['goto_start']
       print 'store_token_and_goto inserted %s' % (
         counters['store_token_and_goto'])
       print 'store_harmony_token_and_goto %s' % (
         counters['store_harmony_token_and_goto'])
       print 'transitions removed %s' % counters['removals']
       print 'do_stored_token actions added %s' % len(store_states)
     self.__dfa = Dfa(self.__dfa.encoding(), start_name, states)
 
   @staticmethod
   def optimize(dfa, log):
     optimizer = DfaOptimizer(dfa, log)
     optimizer.replace_tokens_with_gotos()
     return optimizer.__dfa