Cython/Compiler/ControlFlow.py

   1 import bisect
   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 class ControlFlow:
  17
  18     def __init__(self, start_pos, incoming, parent):
  19         self.start_pos = start_pos
  20         self.incoming = incoming
  21         if parent is None and incoming is not None:
  22             parent = incoming.parent
  23         self.parent = parent
  24         self.tip = {}
  25         self.end_pos = ((),)
  26
  27     def start_branch(self, pos):
  28         self.end_pos = pos
  29         branch_point = BranchingControlFlow(pos, self)
  30         if self.parent is not None:
  31             self.parent.branches[-1] = branch_point
  32         return branch_point.branches[0]
  33
  34     def next_branch(self, pos):
  35         self.end_pos = pos
  36         return self.parent.new_branch(pos)
  37
  38     def finish_branch(self, pos):
  39         self.end_pos = pos
  40         self.parent.end_pos = pos
  41         return LinearControlFlow(pos, self.parent)
  42
  43     def get_state(self, item, pos=((),())):
  44         return self.get_pos_state(item, pos)[1]
  45
  46     def get_pos_state(self, item, pos=((),())):
  47         # do some caching
  48         if pos > self.end_pos:
  49             try:
  50                 return self.tip[item]
  51             except KeyError:
  52                 self.tip[item] = pos_state = self._get_pos_state(item, pos)
  53                 return pos_state
  54         else:
  55             return self._get_pos_state(item, pos)
  56
  57 class LinearControlFlow(ControlFlow):
  58
  59     def __init__(self, start_pos=(), incoming=None, parent=None):
  60         ControlFlow.__init__(self, start_pos, incoming, parent)
  61         self.events = {}
  62
  63     def set_state(self, pos, item, state):
  64         if self.tip.has_key(item):
  65             del self.tip[item]
  66         if pos < self.start_pos:
  67             if self.incoming is not None:
  68                 self.incoming.set_state(pos, item, state)
  69         else:
  70             if self.events.has_key(item):
  71                 event_list = self.events[item]
  72             else:
  73                 event_list = []
  74                 self.events[item] = event_list
  75             bisect.insort(event_list, (pos, state))
  76
  77
  78     def _get_pos_state(self, item, pos):
  79         if pos > self.start_pos:
  80             if self.events.has_key(item):
  81                 event_list = self.events[item]
  82                 for event in event_list[::-1]:
  83                     if event[0] < pos:
  84                         return event
  85
  86         if self.incoming is not None:
  87             return self.incoming.get_pos_state(item, pos)
  88
  89         else:
  90             return None, None
  91
  92     def to_string(self, indent='', limit=None):
  93
  94         if len(self.events) == 0:
  95             s = indent + "[no state changes]"
  96
  97         else:
  98             all = []
  99             for item, event_list in self.events.items():
 100                 for pos, state in event_list:
 101                     all.append((indent, pos, item, state))
 102             all.sort()
 103             all = ["%s%s: %s <- %s" % data for data in all]
 104             s = "\n".join(all)
 105         if self.incoming is not limit and self.incoming is not None:
 106             s = "%s\n%s" % (self.incoming.to_string(indent, limit=limit), s)
 107         return s
 108
 109
 110 class BranchingControlFlow(ControlFlow):
 111
 112     def __init__(self, start_pos, incoming, parent=None):
 113         ControlFlow.__init__(self, start_pos, incoming, parent)
 114         self.branches = [LinearControlFlow(start_pos, incoming, parent=self)]
 115         self.branch_starts = [start_pos]
 116
 117     def set_state(self, pos, item, state):
 118
 119         if self.tip.has_key(item):
 120             del self.tip[item]
 121
 122         if pos < self.start_pos:
 123             self.incoming.set_state(pos, item, state)
 124         else:
 125             for branch_pos, branch in zip(self.branch_starts[::-1], self.branches[::-1]):
 126                 if pos >= branch_pos:
 127                     branch.set_state(pos, item, state)
 128                     return
 129
 130     def _get_pos_state(self, item, pos):
 131         if pos <= self.start_pos:
 132             return self.incoming.get_pos_state(item, pos)
 133         elif pos < self.end_pos:
 134             for branch_pos, branch in zip(self.branch_starts[::-1], self.branches[::-1]):
 135                 if pos >= branch_pos:
 136                     return branch.get_pos_state(item, pos)
 137         else:
 138             last_pos, last_state = self.branches[0].get_pos_state(item, pos)
 139             if last_state is None:
 140                 return None, None
 141             for branch in self.branches[1:]:
 142                 other_pos, other_state = branch.get_pos_state(item, pos)
 143                 if other_state is None or other_state != last_state:
 144                     return None, None
 145                 elif last_pos is not other_pos:
 146                     last_pos = max(last_pos, other_pos)
 147             return last_pos, last_state
 148
 149     def new_branch(self, pos):
 150         self.branches.append(LinearControlFlow(pos, self.incoming, parent=self))
 151         self.branch_starts.append(pos)
 152         return self.branches[-1]
 153
 154     def to_string(self, indent='', limit=None):
 155         join = "\n%sor\n" % indent
 156         s = join.join([branch.to_string(indent+"    ", limit=self.incoming) for branch in self.branches])
 157         if self.incoming is not limit and self.incoming is not None:
 158             s = "%s\n%s" % (self.incoming.to_string(indent, limit=limit), s)
 159         return s
 160
 161