Experimental lexer generator: refactor(TransitionKey) += comments.

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 10 matching lines @@
 # 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 string import printable
 
 class TransitionKey:
+  '''Represents a transition from a state in DFA or NFA to another state.
+
+  A transition key has a list of character ranges and a list of class ranges
+  (e.g., "whitespace"), defining for which characters the transition
+  happens. When we generate code based on the transition key, the character
+  ranges generate simple checks and the class ranges generate more complicated
+  conditions, e.g., function calls.'''
 
   __class_bounds = {
     '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)
+  __upper_bound = max(__class_bounds.values(), key=lambda item: item[1])[1]
 
   __cached_keys = {}
 
   __unique_key_counter = -1
 
   @staticmethod
   def __in_latin_1(char):
     bound = TransitionKey.__class_bounds['latin_1']
     return (bound[0] <= char and char <= bound[1])
 
@@ skipping 18 matching lines @@
       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):
-    if not ranges:
-      assert name == 'epsilon'
-      assert not name in TransitionKey.__cached_keys
-    else:
-      TransitionKey.__verify_ranges(ranges, True)
-    key = TransitionKey()
-    key.__ranges = tuple(ranges) # immutable
-    key.__name = name
-    key.__cached_hash = None
-    return key
-
   def __is_unique(self):
     return len(self.__ranges) == 1 and self.__is_unique_range(self.__ranges[0])
 
   @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)
+      TransitionKey.__cached_keys[name] = TransitionKey(bounds, name)
     return TransitionKey.__cached_keys[name]
 
   @staticmethod
   def epsilon():
+    '''Returns a TransitionKey for the epsilon (empty) transition.'''
     return TransitionKey.__cached_key('epsilon', lambda name : [])
 
   @staticmethod
   def any():
+    '''Returns a TransitionKey which matches any character.'''
     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):
+    '''Returns a TransitionKey for a single-character transition.'''
     char = ord(char)
     assert TransitionKey.__in_latin_1(char)
-    return TransitionKey.__create([(char, char)])
+    return TransitionKey([(char, char)])
 
   @staticmethod
   def unique(name):
+    '''Returns a unique TransitionKey for the given name (and creates it if it
+    doesn't exist yet). The TransitionKey won't have any real character range,
+    but a newly-created "mock" character range which is separate from all other
+    character ranges.'''
     def get_bounds(name):
       bound = TransitionKey.__unique_key_counter
       TransitionKey.__unique_key_counter -= 1
       return [(bound, bound)]
     name = '__' + name
     return TransitionKey.__cached_key(name, get_bounds)
 
   @staticmethod
   def __process_graph(graph, ranges, key_map):
     key = graph[0]
@@ skipping 16 matching lines @@
         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])
     else:
       raise Exception('bad key [%s]' % key)
 
   @staticmethod
   def character_class(graph, key_map):
+    '''Processes 'graph' (a representation of a character class in the rule
+    file), and constructs a TransitionKey based on it. 'key_map' contains
+    already constructed aliases for character classes (they can be used in the
+    new character class). It is a map from strings (character class names) to
+    TransitionKeys. For example, graph might represent the character class
+    [a-z:digit:] where 'digit' is a previously constructed characte class found
+    in "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):
     char = ord(char)
     # TODO class checks
     for r in self.__ranges:
       if r[0] <= char and char <= r[1]: return True
     return False
 
-  def matches_key(self, key):
+  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 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]
@@ skipping 56 matching lines @@
       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])
     else:
       return '[%s-%s]' % (to_str(r[0]), to_str(r[1]))
 
+  def __init__(self, ranges, name = None):
+    if not ranges:
+      assert name == 'epsilon'
+      assert not name in TransitionKey.__cached_keys
+    else:
+      TransitionKey.__verify_ranges(ranges, True)
+    self.__name = name
+    self.__ranges = tuple(ranges) # immutable
+    self.__cached_hash = None
+
   def __str__(self):
     if self.__name:
       return self.__name
     return ', '.join(TransitionKey.__range_str(x) for x in self.__ranges)
 
   @staticmethod
   def __disjoint_keys(range_map):
+    '''Takes a set of possibly overlapping ranges, returns a list of ranges
+    which don't overlap and which cover the same points as the original
+    set. range_map is a map from lower bounds to a list of upper bounds.'''
     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
       to_push = []
       for v in left_values:
         assert left <= next
@@ skipping 20 matching lines @@
       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(range_map)
     TransitionKey.__verify_ranges(ranges, False)
     return ranges
 
   @staticmethod
   def disjoint_keys(key_set):
+    '''Takes a set of possibly overlapping TransitionKeys, returns a list of
+    TransitionKeys which don't overlap and whose union is the same as the union
+    of the original key_set. key_set is a set of TransitionKeys.'''
     ranges = TransitionKey.__disjoint_ranges_from_key_set(key_set)
-    return map(lambda x : TransitionKey.__create([x]), ranges)
+    return map(lambda x : TransitionKey([x]), ranges)
 
   @staticmethod
   def inverse_key(key_set):
+    '''Returns a TransitionKey which matches represents the inverse of the union
+    of 'key_set'. The TransitionKeys contain a set of character ranges and a set
+    of classes. The character ranges are inverted in relation to the latin_1
+    character range, and the character classes are inverted in relation to all
+    character classes in __class_bounds.'''
     ranges = TransitionKey.__disjoint_ranges_from_key_set(key_set)
     inverse = TransitionKey.__invert_ranges(ranges)
     if not inverse:
       return None
-    return TransitionKey.__create(inverse)
+    return TransitionKey(inverse)
 
   @staticmethod
   def __key_from_ranges(invert, ranges):
     range_map = {}
     for r in ranges:
       if not r[0] in range_map:
         range_map[r[0]] = []
       range_map[r[0]].append(r[1])
     ranges = TransitionKey.__disjoint_keys(range_map)
     ranges = TransitionKey.__merge_ranges(ranges)
     if invert:
       ranges = TransitionKey.__invert_ranges(ranges)
-    return TransitionKey.__create(ranges)
+    return TransitionKey(ranges)
 
   @staticmethod
   def __merge_ranges(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 TransitionKey.__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(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
+    # Extract character classes (as opposed to character ranges) from
+    # __class_bounds. Since latin_1 is the only real character range, we can do
+    # this.
     classes = set(TransitionKey.__class_bounds.values())
     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