Experimental parser: break KeyEncoding off into its own file

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
 #       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 types import IntType
 from itertools import chain
+from encoding import KeyEncoding
 from action import Term
-from string import printable
-
-class KeyEncoding(object):
-
-  __encodings = {}
-
-  @staticmethod
-  def get(name):
-    if not KeyEncoding.__encodings:
-      Latin1Encoding()
-      Utf16Encoding()
-      Utf8Encoding()
-    return KeyEncoding.__encodings[name]
-
-  def __init__(self, name, primary_range, named_ranges, predefined_ranges):
-    assert not name in KeyEncoding.__encodings
-    assert primary_range[0] <= primary_range[1]
-    KeyEncoding.__encodings[name] = self
-    self.__name = name
-    self.__primary_range = primary_range
-    self.__lower_bound = primary_range[0]
-    self.__upper_bound = primary_range[1]
-    self.__primary_range_component = self.numeric_range_term(primary_range[0],
-                                                             primary_range[1])
-    self.__named_ranges = {
-      k : Term('NAMED_RANGE_KEY', k) for k in named_ranges }
-    def f(v):
-      if len(v) == 2:
-        return self.numeric_range_term(v[0], v[1])
-      elif len(v) == 1:
-        assert v[0] in self.__named_ranges
-        return self.__named_ranges[v[0]]
-      else:
-        raise Exception()
-    self.__predefined_ranges = {
-      k : map(f, v) for k, v in predefined_ranges.iteritems() }
-
-  def name(self):
-    return self.__name
-
-  def lower_bound(self):
-    return self.__lower_bound
-
-  def upper_bound(self):
-    return self.__upper_bound
-
-  def primary_range(self):
-    return self.__primary_range
-
-  def named_range(self, name):
-    ranges = self.__named_ranges
-    return Term.empty_term() if not name in ranges else ranges[name]
-
-  def named_range_iter(self):
-    return self.__named_range.iteritems()
-
-  def named_range_key_iter(self):
-    return self.__named_ranges.iterkeys()
-
-  def named_range_value_iter(self):
-    return self.__named_ranges.itervalues()
-
-  def predefined_range_iter(self, name):
-    ranges = self.__predefined_ranges
-    return None if not name in ranges else iter(ranges[name])
-
-  def __primary_range_iter(self):
-    yield self.__primary_range_component
-
-  def all_components_iter(self):
-    return chain(self.__primary_range_iter(), self.__named_ranges.itervalues())
-
-  def is_primary_range(self, r):
-    assert len(r) == 2
-    return self.in_primary_range(r[0], r[1])
-
-  def in_primary_range(self, a, b):
-    return self.lower_bound() <= a and b <= self.upper_bound()
-
-  def numeric_range_term(self, a, b):
-    assert type(a) == IntType and type(b) == IntType
-    assert self.in_primary_range(a, b)
-    return Term('NUMERIC_RANGE_KEY', a, b)
 
 class TransitionKey(object):
   '''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.'''
 
@@ skipping 168 matching lines @@
 
   def __hash__(self):
     return hash(self.__term)
 
   def __ne__(self, other):
     return not self == other
 
   def __eq__(self, other):
     return isinstance(other, TransitionKey) and self.__term == other.__term
 
-  @staticmethod
-  def __class_name(encoding, r):
-    for name, v in encoding.class_range_iter():
-      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):
     for c in self.__flatten():
       if c.name() == 'NUMERIC_RANGE_KEY':
         yield ('PRIMARY_RANGE', (c.args()[0], c.args()[1]))
       elif c.name() == 'NAMED_RANGE_KEY':
         yield ('CLASS', c.args()[0])
       elif c.name() == 'TERM_KEY':
         yield ('UNIQUE', c.args()[0])
       else:
         assert False, 'unimplemented %s' % c
 
-  __printable_cache = {
-    ord('\t') : '\\t',
-    ord('\n') : '\\n',
-    ord('\r') : '\\r',
-  }
-
   @staticmethod
   def __component_str(encoding, component):
     if component.name() == 'TERM_KEY':
       return component.args()[0]
     elif component.name() == 'NAMED_RANGE_KEY':
       return component.args()[0]
     elif component.name() == 'EPSILON_KEY':
       return 'epsilon'
     elif component.name() == 'OMEGA_KEY':
       return 'omega'
-    elif component.name() != 'NUMERIC_RANGE_KEY':
-      raise Exception('unprintable %s' % component)
-    r = component.args()
-    def to_str(x):
-      assert not encoding or encoding.in_primary_range(x, 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]
-    if r[0] == r[1]:
-      return '%s' % to_str(r[0])
-    else:
+    elif component.name() == 'NUMERIC_RANGE_KEY':
+      r = component.args()
+      to_str = lambda x: KeyEncoding.to_str(encoding, x)
+      if r[0] == r[1]:
+        return '%s' % to_str(r[0])
       return '[%s-%s]' % (to_str(r[0]), to_str(r[1]))
+    raise Exception('unprintable %s' % component)
 
   def __flatten(self):
     return self.__flatten_components([self.__term])
 
   @staticmethod
   def __flatten_components(components):
     for component in components:
       if component.name() != 'COMPOSITE_KEY':
         yield component
       else:
@@ skipping 41 matching lines @@
       (a, b, sign) = (b, a, 1) # normalize ordering so that a0 < b0
     assert a[0] < b[0]
     if b[1] <= a[1]:  # subset
       return 3 * sign
     if a[1] < b[0]:  # non overlap
       return 2 * sign
     return 5 * sign  # partial overlap
 
   @staticmethod
   def __construct(encoding, components):
+    if isinstance(components, Term):
+      components = [components]
     is_unique = False
     acc = []
     last = Term.empty_term()
     for current in TransitionKey.__flatten_components(components):
       name = current.name()
       if last:
         assert name != 'EPSILON_KEY' and name != 'OMEGA_KEY', 'cannot merge'
         c = TransitionKey.__component_compare(last, current)
         assert c == -1 or c == -2, 'bad order %s %s' % (str(last), str(current))
       if name == 'EPSILON_KEY' or name == 'OMEGA_KEY' or name == 'TERM_KEY':
         pass
       elif name == 'NUMERIC_RANGE_KEY':
         assert encoding.is_primary_range(current.args())
         if last.name() == 'NUMERIC_RANGE_KEY':
           assert last.args()[1] + 1 < current.args()[0], 'ranges must be merged'
       elif name == 'NAMED_RANGE_KEY':
         assert encoding.named_range(current.args()[0])
       else:
         raise Exception('illegal component %s' % str(current))
       acc.append(current)
       last = current
     assert acc, "must have components"
     return acc[0] if len(acc) == 1 else Term('COMPOSITE_KEY', *acc)
 
   def __init__(self, encoding, components):
-    if isinstance(components, Term):
-      components = [components]
     self.__term = TransitionKey.__construct(encoding, components)
     self.__cached_hash = None
 
   def to_string(self, encoding):
     return ', '.join(map(lambda x : TransitionKey.__component_str(encoding, x),
                          self.__flatten()))
 
   def __str__(self):
     return self.to_string(None)
 
@@ skipping 96 matching lines @@
     return TransitionKey.__key_from_components(
       encoding, True, TransitionKey.__flatten_keys(keys))
 
   @staticmethod
   def merged_key(encoding, keys):
     return TransitionKey(encoding,
       TransitionKey.__disjoint_components_from_keys(encoding, keys, True))
 
   @staticmethod
   def __invert_components(encoding, components):
-    def key(x, y):
-      return encoding.numeric_range_term(x, y)
+    key = lambda x, y: encoding.numeric_range_term(x, y)
     last = None
     classes = set(encoding.named_range_value_iter())
     for c in components:
       if c in classes:
         classes.remove(c)
         continue
       assert c.name() == 'NUMERIC_RANGE_KEY', 'unencoded key not invertible'
       r = c.args()
       assert encoding.is_primary_range(r)
       if last == None:
         if r[0] != encoding.lower_bound():
           yield key(encoding.lower_bound(), r[0] - 1)
       elif last[1] + 1 < r[0]:
         yield key(last[1] + 1, r[0] - 1)
       last = r
     upper_bound = encoding.primary_range()[1]
     if last == None:
       r = encoding.primary_range()
       yield key(r[0], r[1])
     elif last[1] < upper_bound:
       yield key(last[1] + 1, upper_bound)
     for c in sorted(classes, TransitionKey.__component_compare):
       yield c
-
-class Latin1Encoding(KeyEncoding):
-
-  def __init__(self):
-    super(Latin1Encoding, self).__init__(
-      'latin1',
-      (0, 255),
-      [],
-      {
-        'whitespace':
-          [(9, 9), (11, 12), (32, 32), (133, 133), (160, 160)],
-        'letter':
-          [(65, 90), (97, 122), (170, 170), (181, 181),
-           (186, 186), (192, 214), (216, 246), (248, 255)],
-        'line_terminator':
-          [(10, 10), (13, 13)],
-        'identifier_part_not_letter':
-          [(48, 57), (95, 95)]
-      })
-
-class Utf16Encoding(KeyEncoding):
-
-  def __init__(self):
-    super(Utf16Encoding, self).__init__(
-      'utf16',
-      (0, 255),
-      ['non_primary_whitespace',
-       'non_primary_letter',
-       'non_primary_identifier_part_not_letter',
-       'non_primary_line_terminator',
-       'non_primary_everything_else'],
-      {
-        'whitespace':
-          [(9, 9), (11, 12), (32, 32), (133, 133), (160, 160),
-           ('non_primary_whitespace',)],
-        'letter':
-          [(65, 90), (97, 122), (170, 170), (181, 181),
-           (186, 186), (192, 214), (216, 246), (248, 255),
-           ('non_primary_letter',)],
-        'line_terminator':
-          [(10, 10), (13, 13), ('non_primary_line_terminator',)],
-        'identifier_part_not_letter':
-          [(48, 57), (95, 95), ('non_primary_identifier_part_not_letter',)],
-      })
-
-class Utf8Encoding(KeyEncoding):
-
-  def __init__(self):
-    super(Utf8Encoding, self).__init__(
-      'utf8',
-      (0, 127),
-      ['non_primary_whitespace',
-       'non_primary_letter',
-       'non_primary_identifier_part_not_letter',
-       'non_primary_line_terminator',
-       'non_primary_everything_else'],
-      {
-        'whitespace':
-          [(9, 9), (11, 12), (32, 32), ('non_primary_whitespace',)],
-        'letter':
-          [(65, 90), (97, 122), ('non_primary_letter',)],
-        'line_terminator':
-          [(10, 10), (13, 13), ('non_primary_line_terminator',)],
-        'identifier_part_not_letter':
-          [(48, 57), (95, 95), ('non_primary_identifier_part_not_letter',)],
-      })