Cython/Compiler/ControlFlow.py

   1 import bisect, sys
   2
   3 # This module keeps track of arbitrary "states" at any point of the code.
   4 # A state is considered known if every path to the given point agrees on
   5 # its state, otherwise it is None (i.e. unknown).
   6
   7 # It might be useful to be able to "freeze" the set of states by pushing
   8 # all state changes to the tips of the trees for fast reading. Perhaps this
   9 # could be done on get_state, clearing the cache on set_state (assuming
  10 # incoming is immutable).
  11
  12 # This module still needs a lot of work, and probably should totally be
  13 # redesigned. It doesn't take return, raise, continue, or break into
  14 # account.
  15
  16 from Cython.Compiler.Scanning import StringSourceDescriptor
  17 try:
  18     _END_POS = (StringSourceDescriptor(unichr(sys.maxunicode)*10, ''),
  19                 sys.maxint, sys.maxint)
  20 except AttributeError: # Py3
  21     _END_POS = (StringSourceDescriptor(unichr(sys.maxunicode)*10, ''),
  22                 sys.maxsize, sys.maxsize)
  23
  24 class ControlFlow(object):
  25
  26     def __init__(self, start_pos, incoming, parent):
  27         self.start_pos = start_pos
  28         self.incoming = incoming
  29         if parent is None and incoming is not None:
  30             parent = incoming.parent
  31         self.parent = parent
  32         self.tip = {}
  33         self.end_pos = _END_POS
  34
  35     def start_branch(self, pos):
  36         self.end_pos = pos
  37         branch_point = BranchingControlFlow(pos, self)
  38         if self.parent is not None:
  39             self.parent.branches[-1] = branch_point
  40         return branch_point.branches[0]
  41
  42     def next_branch(self, pos):
  43         self.end_pos = pos
  44         return self.parent.new_branch(pos)
  45
  46     def finish_branch(self, pos):
  47         self.end_pos = pos
  48         self.parent.end_pos = pos
  49         return LinearControlFlow(pos, self.parent)
  50
  51     def get_state(self, item, pos=_END_POS):
  52         return self.get_pos_state(item, pos)[1]
  53
  54     def get_pos_state(self, item, pos=_END_POS):
  55         # do some caching
  56         if pos > self.end_pos:
  57             try:
  58                 return self.tip[item]
  59             except KeyError:
  60                 pass
  61         pos_state = self._get_pos_state(item, pos)
  62         if pos > self.end_pos:
  63             self.tip[item] = pos_state
  64         return pos_state
  65
  66     def _get_pos_state(self, item, pos):
  67         current = self
  68         while current is not None and pos <= current.start_pos:
  69             current = current.incoming
  70         if current is None:
  71             return (None, None)
  72         state = current._get_pos_state_local(item, pos)
  73         while (state is None or state == (None, None)) and current.incoming is not None:
  74             current = current.incoming
  75             state = current._get_pos_state_local(item, pos)
  76         if state is None:
  77             return (None, None)
  78         return state
  79
  80     def set_state(self, pos, item, state):
  81         if item in self.tip:
  82             del self.tip[item]
  83         current = self
  84         while pos < current.start_pos and current.incoming is not None:
  85             current = current.incoming
  86             if item in current.tip:
  87                 del current.tip[item]
  88         current._set_state_local(pos, item, state)
  89
  90
  91 class LinearControlFlow(ControlFlow):
  92
  93     def __init__(self, start_pos=(), incoming=None, parent=None):
  94         ControlFlow.__init__(self, start_pos, incoming, parent)
  95         self.events = {}
  96
  97     def _set_state_local(self, pos, item, state):
  98         if item in self.events:
  99             event_list = self.events[item]
 100         else:
 101             event_list = []
 102             self.events[item] = event_list
 103         bisect.insort(event_list, (pos, state))
 104
 105     def _get_pos_state_local(self, item, pos):
 106         if item in self.events:
 107             event_list = self.events[item]
 108             for event in event_list[::-1]:
 109                 if event[0] < pos:
 110                     return event
 111         return None
 112
 113     def to_string(self, indent='', limit=None):
 114
 115         if len(self.events) == 0:
 116             s = indent + "[no state changes]"
 117
 118         else:
 119             all = []
 120             for item, event_list in self.events.items():
 121                 for pos, state in event_list:
 122                     all.append((indent, pos, item, state))
 123             all.sort()
 124             all = ["%s%s: %s <- %s" % data for data in all]
 125             s = "\n".join(all)
 126         if self.incoming is not limit and self.incoming is not None:
 127             s = "%s\n%s" % (self.incoming.to_string(indent, limit=limit), s)
 128         return s
 129
 130
 131 class BranchingControlFlow(ControlFlow):
 132
 133     def __init__(self, start_pos, incoming, parent=None):
 134         ControlFlow.__init__(self, start_pos, incoming, parent)
 135         self.branches = [LinearControlFlow(start_pos, incoming, parent=self)]
 136         self.branch_starts = [start_pos]
 137
 138     def _set_state_local(self, pos, item, state):
 139         for branch_pos, branch in zip(self.branch_starts[::-1], self.branches[::-1]):
 140             if pos >= branch_pos:
 141                 branch._set_state_local(pos, item, state)
 142                 return
 143
 144     def _get_pos_state_local(self, item, pos, stop_at=None):
 145         if pos < self.end_pos:
 146             for branch_pos, branch in zip(self.branch_starts[::-1], self.branches[::-1]):
 147                 if pos >= branch_pos:
 148                     return branch._get_pos_state_local(item, pos)
 149         else:
 150             state = self.branches[0]._get_pos_state_local(item, pos)
 151             if state is None:
 152                 return None, None
 153             last_pos, last_state = state
 154             if last_state is None:
 155                 return None, None
 156             for branch in self.branches[1:]:
 157                 state = branch._get_pos_state_local(item, pos)
 158                 if state is None:
 159                     return None, None
 160                 other_pos, other_state = state
 161                 if other_state != last_state:
 162                     return None, None
 163                 elif last_pos is not other_pos:
 164                     last_pos = max(last_pos, other_pos)
 165             return last_pos, last_state
 166         return None
 167
 168     def new_branch(self, pos):
 169         self.branches.append(LinearControlFlow(pos, self.incoming, parent=self))
 170         self.branch_starts.append(pos)
 171         return self.branches[-1]
 172
 173     def to_string(self, indent='', limit=None):
 174         join = "\n%sor\n" % indent
 175         s = join.join([branch.to_string(indent+"    ", limit=self.incoming) for branch in self.branches])
 176         if self.incoming is not limit and self.incoming is not None:
 177             s = "%s\n%s" % (self.incoming.to_string(indent, limit=limit), s)
 178         return s