Experimental parser: more verification

tools/lexer_generator/dfa.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 71 matching lines @@
   def __init__(self, encoding, start_name, mapping):
     super(Dfa, self).__init__(encoding)
     self.__terminal_set = set()
     name_map = {}
     for name, node_data in mapping.items():
       transitions = {}
       node = DfaState(name, node_data['action'], transitions)
       name_map[name] = (node, transitions)
       if node_data['terminal']:
         self.__terminal_set.add(node)
+    all_keys = []
     for name, node_data in mapping.items():
       (node, transitions) = name_map[name]
       inversion = {}
       for key, state in node_data['transitions'].items():
         if not state in inversion:
           inversion[state] = []
         inversion[state].append(key)
       for state, keys in inversion.items():
+        all_keys += keys
         merged_key = TransitionKey.merged_key(encoding, keys)
         self.__add_transition(transitions, merged_key, name_map[state][0])
     self.__start = name_map[start_name][0]
     self.__node_count = len(mapping)
+    self.__disjoint_keys = sorted(
+      TransitionKey.disjoint_keys(encoding, all_keys))
     self.__verify()
 
   def __verify(self):
     assert self.__terminal_set
     state_count = self.visit_all_states(lambda state, count: count + 1, 0)
     assert self.__node_count == state_count
+    # assert keys are disjoint
+    def f(state, remaining):
+      remaining = set(TransitionKey.disjoint_keys(self.encoding(),
+                                                  state.key_iter()))
+      for key in state.key_iter():
+        to_drop = set(filter(lambda x : key.is_superset_of_key(x), remaining))
+        assert to_drop
+        remaining -= to_drop
+      assert not remaining
+    self.visit_all_states(f, set(self.disjoint_keys_iter()))
+
+  def disjoint_keys_iter(self):
+    return iter(self.__disjoint_keys)
 
   def node_count(self):
     return self.__node_count
 
   def start_state(self):
     return self.__start
 
   def terminal_set(self):
     return set(self.__terminal_set)