Experimental lexer generator: make tests pass again + style fixes.

tools/lexer_generator/transition_keys.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 12 matching lines @@
 # 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 string import printable
 
 class TransitionKey:
 
   __class_bounds = {
-    "latin_1" : (1, 255),
-    # These are not "real" ranges; they just need to be separate.
-    "whitespace" : (256, 256),
-    "literal" : (257, 257),
-    "eos" : (258, 258),
-    "zero" : (259, 259),
+    'latin_1' : (1, 255),
+    # These are not real ranges; they just need to be separate from any real
+    # ranges.
+    'whitespace' : (256, 256),
+    'literal' : (257, 257),
+    'eos' : (258, 258),
+    'zero' : (259, 259),
   }
   __lower_bound = 1
   __upper_bound = reduce(lambda acc, (k, v): max(acc, v[1]), __class_bounds.items(), 0)
 
   __cached_keys = {}
 
   __unique_key_counter = -1
 
   @staticmethod
   def __in_latin_1(char):
-    bound = TransitionKey.__class_bounds["latin_1"]
+    bound = TransitionKey.__class_bounds['latin_1']
     return (bound[0] <= char and char <= bound[1])
 
   @staticmethod
   def __is_class_range(r):
     return r[0] == r[1] and not TransitionKey.__in_latin_1(r[0])
 
   @staticmethod
   def __is_unique_range(r):
     return r[0] == r[1] and r[0] < TransitionKey.__lower_bound
 
   @staticmethod
   def __verify_ranges(ranges, check_merged):
     assert ranges
     if len(ranges) == 1 and TransitionKey.__is_class_range(ranges[0]):
       return
     last = None
     for r in ranges:
       assert TransitionKey.__lower_bound <= r[0]
       assert r[1] <= TransitionKey.__upper_bound
       assert r[0] <= r[1]
       r_is_class = TransitionKey.__is_class_range(r)
+      # Assert that the ranges are in order.
       if last != None and check_merged:
         assert last[1] + 1 < r[0] or r_is_class
       if not TransitionKey.__in_latin_1(r[0]):
         assert r_is_class
       if not TransitionKey.__in_latin_1(r[1]):
         assert r_is_class
       last = r
 
   @staticmethod
   def __create(ranges, name = None):
@@ skipping 13 matching lines @@
 
   @staticmethod
   def __cached_key(name, bounds_getter):
     if not name in TransitionKey.__cached_keys:
       bounds = bounds_getter(name)
       TransitionKey.__cached_keys[name] = TransitionKey.__create(bounds, name)
     return TransitionKey.__cached_keys[name]
 
   @staticmethod
   def epsilon():
-    return TransitionKey.__cached_key("epsilon", lambda name : [])
+    return TransitionKey.__cached_key('epsilon', lambda name : [])
 
   @staticmethod
   def any():
-    return TransitionKey.__cached_key("any",
-      lambda name : TransitionKey.__class_bounds.values())
+    def bounds_getter(name):
+      bounds = TransitionKey.__class_bounds.values()
+      bounds.sort()
+      return bounds
+    return TransitionKey.__cached_key('any', bounds_getter)
 
   @staticmethod
   def single_char(char):
     char = ord(char)
     assert TransitionKey.__in_latin_1(char)
     return TransitionKey.__create([(char, char)])
 
   @staticmethod
   def unique(name):
     def get_bounds(name):
       bound = TransitionKey.__unique_key_counter
       TransitionKey.__unique_key_counter -= 1
       return [(bound, bound)]
-    name = "__" + name
+    name = '__' + name
     return TransitionKey.__cached_key(name, get_bounds)
 
   @staticmethod
   def __process_graph(graph, ranges, key_map):
     key = graph[0]
     if key == 'RANGE':
       ranges.append((ord(graph[1]), ord(graph[2])))
     elif key == 'LITERAL':
       ranges.append((ord(graph[1]), ord(graph[1])))
     elif key == 'CAT':
       for x in [graph[1], graph[2]]:
         TransitionKey.__process_graph(x, ranges, key_map)
     elif key == 'CHARACTER_CLASS':
       class_name = graph[1]
       if class_name == 'ws':
         ranges.append(TransitionKey.__class_bounds['whitespace'])
       elif class_name == 'lit':
         ranges.append(TransitionKey.__class_bounds['literal'])
       elif class_name == 'eos':
         ranges.append(TransitionKey.__class_bounds['eos'])
       elif class_name == 'zero':
         ranges.append(TransitionKey.__class_bounds['zero'])
       elif class_name in key_map:
         ranges += key_map[class_name].__ranges
       else:
-        raise Exception("unknown character class [%s]" % graph[1])
+        raise Exception('unknown character class [%s]' % graph[1])
     else:
-      raise Exception("bad key [%s]" % key)
+      raise Exception('bad key [%s]' % key)
 
   @staticmethod
   def character_class(graph, key_map):
     ranges = []
     assert graph[0] == 'CLASS' or graph[0] == 'NOT_CLASS'
     invert = graph[0] == 'NOT_CLASS'
     TransitionKey.__process_graph(graph[1], ranges, key_map)
     return TransitionKey.__key_from_ranges(invert, ranges)
 
   def matches_char(self, char):
@@ skipping 69 matching lines @@
   def __range_str(r):
     if TransitionKey.__is_class_range(r):
       return TransitionKey.__class_name(r)
     def to_str(x):
       assert TransitionKey.__in_latin_1(x)
       if not x in TransitionKey.__printable_cache:
         res = "'%s'" % chr(x) if chr(x) in printable else str(x)
         TransitionKey.__printable_cache[x] = res
       return TransitionKey.__printable_cache[x]
     if r[0] == r[1]:
-      return "%s" % to_str(r[0])
+      return '%s' % to_str(r[0])
     else:
-      return "[%s-%s]" % (to_str(r[0]), to_str(r[1]))
+      return '[%s-%s]' % (to_str(r[0]), to_str(r[1]))
 
   def __str__(self):
     if self.__name:
       return self.__name
-    return ", ".join(TransitionKey.__range_str(x) for x in self.__ranges)
+    return ', '.join(TransitionKey.__range_str(x) for x in self.__ranges)
 
   @staticmethod
   def __disjoint_keys(range_map):
     sort = lambda x : sorted(set(x))
     range_map = sorted(map(lambda (k, v): (k, sort(v)), range_map.items()))
     ranges = []
     upper_bound = TransitionKey.__upper_bound + 1
     for i in range(len(range_map)):
       (left, left_values) = range_map[i]
       next = range_map[i + 1][0] if i != len(range_map) - 1 else upper_bound
@@ skipping 74 matching lines @@
   @staticmethod
   def merged_key(keys):
     f = lambda acc, key: acc + list(key.__ranges)
     return TransitionKey.__key_from_ranges(False, reduce(f, keys, []))
 
   @staticmethod
   def __invert_ranges(ranges):
     inverted = []
     last = None
     classes = set(TransitionKey.__class_bounds.values())
-    latin_1 = TransitionKey.__class_bounds["latin_1"]
+    latin_1 = TransitionKey.__class_bounds['latin_1']
     classes.remove(latin_1)
     for r in ranges:
       assert not TransitionKey.__is_unique_range(r)
       if TransitionKey.__is_class_range(r):
         classes.remove(r)
         continue
       if last == None:
         if r[0] != TransitionKey.__lower_bound:
           inverted.append((TransitionKey.__lower_bound, r[0] - 1))
       elif last[1] + 1 < r[0]:
         inverted.append((last[1] + 1, r[0] - 1))
       last = r
     upper_bound = latin_1[1]
     if last == None:
       inverted.append(latin_1)
     elif last[1] < upper_bound:
       inverted.append((last[1] + 1, upper_bound))
     inverted += list(classes)
     return inverted