Cython/Plex/Transitions.py

   1 #
   2 #   Plex - Transition Maps
   3 #
   4 #   This version represents state sets direcly as dicts
   5 #   for speed.
   6 #
   7
   8 from copy import copy
   9 import string
  10 from sys import maxint
  11 from types import TupleType
  12
  13 class TransitionMap:
  14   """
  15   A TransitionMap maps an input event to a set of states.
  16   An input event is one of: a range of character codes,
  17   the empty string (representing an epsilon move), or one
  18   of the special symbols BOL, EOL, EOF.
  19
  20   For characters, this implementation compactly represents
  21   the map by means of a list:
  22
  23     [code_0, states_0, code_1, states_1, code_2, states_2,
  24       ..., code_n-1, states_n-1, code_n]
  25
  26   where |code_i| is a character code, and |states_i| is a
  27   set of states corresponding to characters with codes |c|
  28   in the range |code_i| <= |c| <= |code_i+1|.
  29
  30   The following invariants hold:
  31     n >= 1
  32     code_0 == -maxint
  33     code_n == maxint
  34     code_i < code_i+1 for i in 0..n-1
  35     states_0 == states_n-1
  36
  37   Mappings for the special events '', BOL, EOL, EOF are
  38   kept separately in a dictionary.
  39   """
  40
  41   map = None     # The list of codes and states
  42   special = None # Mapping for special events
  43
  44   def __init__(self, map = None, special = None):
  45     if not map:
  46       map = [-maxint, {}, maxint]
  47     if not special:
  48       special = {}
  49     self.map = map
  50     self.special = special
  51     #self.check() ###
  52
  53   def add(self, event, new_state,
  54     TupleType = TupleType):
  55     """
  56     Add transition to |new_state| on |event|.
  57     """
  58     if type(event) == TupleType:
  59       code0, code1 = event
  60       i = self.split(code0)
  61       j = self.split(code1)
  62       map = self.map
  63       while i < j:
  64         map[i + 1][new_state] = 1
  65         i = i + 2
  66     else:
  67       self.get_special(event)[new_state] = 1
  68
  69   def add_set(self, event, new_set,
  70     TupleType = TupleType):
  71     """
  72     Add transitions to the states in |new_set| on |event|.
  73     """
  74     if type(event) == TupleType:
  75       code0, code1 = event
  76       i = self.split(code0)
  77       j = self.split(code1)
  78       map = self.map
  79       while i < j:
  80         map[i + 1].update(new_set)
  81         i = i + 2
  82     else:
  83       self.get_special(event).update(new_set)
  84
  85   def get_epsilon(self,
  86     none = None):
  87     """
  88     Return the mapping for epsilon, or None.
  89     """
  90     return self.special.get('', none)
  91
  92   def items(self,
  93     len = len):
  94     """
  95     Return the mapping as a list of ((code1, code2), state_set) and
  96     (special_event, state_set) pairs.
  97     """
  98     result = []
  99     map = self.map
 100     else_set = map[1]
 101     i = 0
 102     n = len(map) - 1
 103     code0 = map[0]
 104     while i < n:
 105       set = map[i + 1]
 106       code1 = map[i + 2]
 107       if set or else_set:
 108         result.append(((code0, code1), set))
 109       code0 = code1
 110       i = i + 2
 111     for event, set in self.special.items():
 112       if set:
 113         result.append((event, set))
 114     return result
 115
 116   # ------------------- Private methods --------------------
 117
 118   def split(self, code,
 119     len = len, maxint = maxint):
 120     """
 121     Search the list for the position of the split point for |code|,
 122     inserting a new split point if necessary. Returns index |i| such
 123     that |code| == |map[i]|.
 124     """
 125     # We use a funky variation on binary search.
 126     map = self.map
 127     hi = len(map) - 1
 128     # Special case: code == map[-1]
 129     if code == maxint:
 130       return hi
 131     # General case
 132     lo = 0
 133     # loop invariant: map[lo] <= code < map[hi] and hi - lo >= 2
 134     while hi - lo >= 4:
 135       # Find midpoint truncated to even index
 136       mid = ((lo + hi) / 2) & ~1
 137       if code < map[mid]:
 138         hi = mid
 139       else:
 140         lo = mid
 141     # map[lo] <= code < map[hi] and hi - lo == 2
 142     if map[lo] == code:
 143       return lo
 144     else:
 145       map[hi:hi] = [code, map[hi - 1].copy()]
 146       #self.check() ###
 147       return hi
 148
 149   def get_special(self, event):
 150     """
 151     Get state set for special event, adding a new entry if necessary.
 152     """
 153     special = self.special
 154     set = special.get(event, None)
 155     if not set:
 156       set = {}
 157       special[event] = set
 158     return set
 159
 160   # --------------------- Conversion methods -----------------------
 161
 162   def __str__(self):
 163     map_strs = []
 164     map = self.map
 165     n = len(map)
 166     i = 0
 167     while i < n:
 168       code = map[i]
 169       if code == -maxint:
 170         code_str = "-inf"
 171       elif code == maxint:
 172         code_str = "inf"
 173       else:
 174         code_str = str(code)
 175       map_strs.append(code_str)
 176       i = i + 1
 177       if i < n:
 178         map_strs.append(state_set_str(map[i]))
 179       i = i + 1
 180     special_strs = {}
 181     for event, set in self.special.items():
 182       special_strs[event] = state_set_str(set)
 183     return "[%s]+%s" % (
 184       string.join(map_strs, ","),
 185       special_strs
 186     )
 187
 188   # --------------------- Debugging methods -----------------------
 189
 190   def check(self):
 191     """Check data structure integrity."""
 192     if not self.map[-3] < self.map[-1]:
 193       print self
 194       assert 0
 195
 196   def dump(self, file):
 197     map = self.map
 198     i = 0
 199     n = len(map) - 1
 200     while i < n:
 201       self.dump_range(map[i], map[i + 2], map[i + 1], file)
 202       i = i + 2
 203     for event, set in self.special.items():
 204       if set:
 205         if not event:
 206           event = 'empty'
 207         self.dump_trans(event, set, file)
 208
 209   def dump_range(self, code0, code1, set, file):
 210     if set:
 211       if code0 == -maxint:
 212         if code1 == maxint:
 213           k = "any"
 214         else:
 215           k = "< %s" % self.dump_char(code1)
 216       elif code1 == maxint:
 217         k = "> %s" % self.dump_char(code0 - 1)
 218       elif code0 == code1 - 1:
 219         k = self.dump_char(code0)
 220       else:
 221         k = "%s..%s" % (self.dump_char(code0),
 222           self.dump_char(code1 - 1))
 223       self.dump_trans(k, set, file)
 224
 225   def dump_char(self, code):
 226     if 0 <= code <= 255:
 227       return repr(chr(code))
 228     else:
 229       return "chr(%d)" % code
 230
 231   def dump_trans(self, key, set, file):
 232     file.write("      %s --> %s\n" % (key, self.dump_set(set)))
 233
 234   def dump_set(self, set):
 235     return state_set_str(set)
 236
 237 #
 238 #   State set manipulation functions
 239 #
 240
 241 #def merge_state_sets(set1, set2):
 242 #               for state in set2.keys():
 243 #                       set1[state] = 1
 244
 245 def state_set_str(set):
 246   state_list = set.keys()
 247   str_list = []
 248   for state in state_list:
 249     str_list.append("S%d" % state.number)
 250   return "[%s]" % string.join(str_list, ",")
 251
 252
 253