Experimental parser: handling unique keys in merges

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 108 matching lines @@
 
   @staticmethod
   def __is_unique_range(r):
     return (r[0] == r[1] and
             r[0] < 0 and
             r[1] > TransitionKey.__unique_key_counter)
 
   @staticmethod
   def __verify_ranges(encoding, ranges, check_merged):
     assert ranges
-    if len(ranges) == 1 and TransitionKey.__is_unique_range(ranges[0]):
-      return
     last = None
     for r in ranges:
-      assert not TransitionKey.__is_unique_range(r)
-      r_is_class = encoding.is_class_range(r)
+      r_is_class = (TransitionKey.__is_unique_range(r) or
+                    encoding.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
-      last = r
-
-  def __is_unique(self):
-    return len(self.__ranges) == 1 and self.__is_unique_range(self.__ranges[0])
+      if r_is_class:
+        last = None
+      else:
+        last = r
 
   @staticmethod
   def __cached_key(encoding, name, bounds_getter):
     encoding_name = encoding.name() if encoding else 'no_encoding'
     cache = TransitionKey.__cached_keys[encoding_name]
     if not name in cache:
       bounds = bounds_getter(name)
       cache[name] = TransitionKey(encoding, bounds, name)
     return cache[name]
 
@@ skipping 78 matching lines @@
   def matches_char(self, char):
     char = ord(char)
     assert char < 128
     for r in self.__ranges:
       if r[0] <= char and char <= r[1]: return True
     return False
 
   def is_superset_of_key(self, key):
     '''Returns true if 'key' is a sub-key of this TransitionKey.'''
     assert isinstance(key, self.__class__)
-    assert key != TransitionKey.epsilon() and not key.__is_unique()
+    assert key != TransitionKey.epsilon()
     assert len(key.__ranges) == 1
     subkey = key.__ranges[0]
     matches = False
     for k in self.__ranges:
       if k[0] <= subkey[0]:
         assert subkey[1] <= k[1] or subkey[0] > k[1]
       if subkey[0] < k[0]:
         assert subkey[1] < k[0]
       if k[0] <= subkey[0] and k[1] >= subkey[1]:
         assert not matches
@@ skipping 20 matching lines @@
     if self.__cached_hash == None:
       self.__cached_hash = hash(self.__ranges)
     return self.__cached_hash
 
   def __eq__(self, other):
     return isinstance(other, self.__class__) and self.__ranges == other.__ranges
 
   @staticmethod
   def __class_name(encoding, r):
     for name, v in encoding.class_range_iter():
-      if r == v: return name
+      if r == v:
+        return name
+    assert False
+
+  @staticmethod
+  def __unique_name(r):
+    for name, v in TransitionKey.__cached_keys['no_encoding'].items():
+      if v.__ranges and r == v.__ranges[0]:
+        return name[2:]
     assert False
 
   def range_iter(self, encoding):
-    assert not self == TransitionKey.epsilon() and not self.__is_unique()
+    assert not self == TransitionKey.epsilon()
     for r in self.__ranges:
-      if encoding.is_class_range(r):
-        yield ('CLASS', TransitionKey.__class_name(encoding, r))
+      if self.__is_unique_range(r):
+        yield ('UNIQUE', self.__unique_name(r))
+      elif encoding.is_class_range(r):
+        yield ('CLASS', self.__class_name(encoding, r))
       else:
         yield ('PRIMARY_RANGE', r)
 
   __printable_cache = {
     ord('\t') : '\\t',
     ord('\n') : '\\n',
     ord('\r') : '\\r',
   }
 
   @staticmethod
   def __range_str(encoding, r):
+    if TransitionKey.__is_unique_range(r):
+      return TransitionKey.__unique_name(r)
     if encoding and encoding.is_class_range(r):
       return TransitionKey.__class_name(encoding, r)
     def to_str(x):
       assert not encoding or encoding.in_primary_range(x)
       if x > 127:
         return str(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]
@@ skipping 47 matching lines @@
         current = range_map[i + 1]
         range_map[i + 1] = (current[0], sort(current[1] + to_push))
     return ranges
 
   @staticmethod
   def __disjoint_ranges_from_key_set(encoding, key_set):
     if not key_set:
       return []
     range_map = {}
     for x in key_set:
-      assert not x.__is_unique()
       assert x != TransitionKey.epsilon()
       for r in x.__ranges:
         if not r[0] in range_map:
           range_map[r[0]] = []
         range_map[r[0]].append(r[1])
     ranges = TransitionKey.__disjoint_keys(encoding, range_map)
     TransitionKey.__verify_ranges(encoding, ranges, False)
     return ranges
 
   @staticmethod
@@ skipping 19 matching lines @@
     ranges = TransitionKey.__disjoint_ranges_from_key_set(encoding, key_set)
     inverse = TransitionKey.__invert_ranges(encoding, ranges)
     if not inverse:
       return None
     return TransitionKey(encoding, inverse)
 
   @staticmethod
   def __key_from_ranges(encoding, invert, ranges):
     range_map = {}
     for r in ranges:
+      assert r
       if not r[0] in range_map:
         range_map[r[0]] = []
       range_map[r[0]].append(r[1])
     ranges = TransitionKey.__disjoint_keys(encoding, range_map)
     ranges = TransitionKey.__merge_ranges(encoding, ranges)
     if invert:
       ranges = TransitionKey.__invert_ranges(encoding, ranges)
     return TransitionKey(encoding, ranges)
 
   @staticmethod
   def __merge_ranges(encoding, ranges):
     merged = []
     last = None
     for r in ranges:
-      assert not TransitionKey.__is_unique_range(r)
       if last == None:
         last = r
-      elif (last[1] + 1 == r[0] and not encoding.is_class_range(r)):
+      elif (last[1] + 1 == r[0] and
+            not TransitionKey.__is_unique_range(r) and
+            not encoding.is_class_range(r)):
         last = (last[0], r[1])
       else:
         merged.append(last)
         last = r
     if last != None:
       merged.append(last)
     return merged
 
   @staticmethod
   def merged_key(encoding, keys):
@@ skipping 90 matching lines @@
         self.class_range('non_primary_whitespace')])
     self.add_predefined_range(
       'letter', [(65, 90), (97, 122), self.class_range('non_primary_letter')])
     self.add_predefined_range(
       'line_terminator',
       [(10, 10), (13, 13), self.class_range('non_primary_line_terminator')])
     self.add_predefined_range(
       'identifier_part_not_letter',
       [(48, 57), (95, 95),
        self.class_range('non_primary_identifier_part_not_letter')])