Package lepl :: Package core :: Module manager
[hide private]
[frames] | no frames]

Source Code for Module lepl.core.manager

  1   
  2  # The contents of this file are subject to the Mozilla Public License 
  3  # (MPL) Version 1.1 (the "License"); you may not use this file except 
  4  # in compliance with the License. You may obtain a copy of the License 
  5  # at http://www.mozilla.org/MPL/ 
  6  # 
  7  # Software distributed under the License is distributed on an "AS IS" 
  8  # basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 
  9  # the License for the specific language governing rights and 
 10  # limitations under the License. 
 11  # 
 12  # The Original Code is LEPL (http://www.acooke.org/lepl) 
 13  # The Initial Developer of the Original Code is Andrew Cooke. 
 14  # Portions created by the Initial Developer are Copyright (C) 2009-2010 
 15  # Andrew Cooke (andrew@acooke.org). All Rights Reserved. 
 16  # 
 17  # Alternatively, the contents of this file may be used under the terms 
 18  # of the LGPL license (the GNU Lesser General Public License, 
 19  # http://www.gnu.org/licenses/lgpl.html), in which case the provisions 
 20  # of the LGPL License are applicable instead of those above. 
 21  # 
 22  # If you wish to allow use of your version of this file only under the 
 23  # terms of the LGPL License and not to allow others to use your version 
 24  # of this file under the MPL, indicate your decision by deleting the 
 25  # provisions above and replace them with the notice and other provisions 
 26  # required by the LGPL License.  If you do not delete the provisions 
 27  # above, a recipient may use your version of this file under either the 
 28  # MPL or the LGPL License. 
 29   
 30  ''' 
 31  Manage resources. 
 32   
 33  We can attempt to control resource consumption by closing generators - the 
 34  problem is which generators to close? 
 35   
 36  At first it seems that the answer is going to be connected to tree traversal, 
 37  but after some thought it's not so clear exactly what tree is being traversed, 
 38  and how that identifies what generators should be closed.  In particular, an  
 39  "imperative" implementation with generators does not have the same meaning of  
 40  "depth" as a recursive functional implementation (but see the related  
 41  discussion in the `manual <../advanced.html#search-and-backtracking>`_). 
 42   
 43  A better approach seems to be to discard those that have not been used "for a 
 44  long time".  A variation on this - keep a maximum number of the youngest  
 45  generators - is practical.  But care is needed to both in identifying what is  
 46  used, and when it starts being unused, and in implementing that efficiently. 
 47   
 48  Here all generators are stored in a priority queue using weak references.  The  
 49  "real" priority is given by the "last used date" (epoch), but the priority in  
 50  the queue is frozen when inserted.  So on removing from the queue the priority  
 51  must be checked to ensure it has not changed (and, if so, it must be updated 
 52  with the real value and replaced). 
 53   
 54  Note that the main aim here is to restrict resource consumption without  
 55  damaging performance too much.  The aim is not to control parse results by  
 56  excluding certain matches.  For efficiency, the queue length is increased  
 57  (doubled) whenever the queue is filled by active generators. 
 58  ''' 
 59   
 60  from heapq import heappushpop, heappop, heappush 
 61  from weakref import ref, WeakKeyDictionary 
 62   
 63  from lepl.core.monitor import StackMonitor, ValueMonitor 
 64  from lepl.support.lib import LogMixin, fmt, str 
65 66 67 # pylint: disable-msg=C0103 68 -def GeneratorManager(queue_len):
69 ''' 70 A 'Monitor' (implements `MonitorInterface`, can be supplied 71 to `Configuration`) that tracks (and can limit the number of) 72 generators. It is also coupled to the size of stacks during search 73 (via the generator_manager_queue_len property). 74 75 This is a helper function that "escapes" the main class via a function 76 to simplify configuration. 77 ''' 78 return lambda: _GeneratorManager(queue_len)
79
80 81 -class _GeneratorManager(StackMonitor, ValueMonitor, LogMixin):
82 ''' 83 A 'Monitor' (implements `MonitorInterface`, can be supplied 84 to `Configuration`) that tracks (and can limit the number of) 85 generators. 86 ''' 87
88 - def __init__(self, queue_len):
89 ''' 90 `queue_len` is the number of generators that can exist. When the 91 number is exceeded the oldest generators are closed, unless currently 92 active (in which case the queue size is extended). If zero then no 93 limit is applied. 94 ''' 95 super(_GeneratorManager, self).__init__() 96 self.__queue = [] 97 self.__initial_queue_len = queue_len 98 self.queue_len = queue_len 99 self.__known = WeakKeyDictionary() # map from generator to ref 100 self.epoch = 0
101
102 - def next_iteration(self, epoch, value, exception, stack):
103 ''' 104 Store the current epoch. 105 ''' 106 self.epoch = epoch
107
108 - def push(self, generator):
109 ''' 110 Add a generator if it is not already known, or increment it's ref count. 111 ''' 112 if generator not in self.__known: 113 self.__add(generator) 114 # this sets the attribute on everything, but most instances simply 115 # don't care... (we can be "inefficient" here as the monitor is 116 # only used when memory use is more important than cpu) 117 if self.__initial_queue_len: 118 generator.matcher.generator_manager_queue_len = \ 119 self.__initial_queue_len 120 self._debug(fmt('Clipping search depth to {0}', 121 self.__initial_queue_len)) 122 else: 123 self.__known[generator].push()
124
125 - def pop(self, generator):
126 ''' 127 Decrement a ref's count and update the epoch. 128 ''' 129 self.__known[generator].pop(self.epoch)
130
131 - def __add(self, generator):
132 ''' 133 Add a generator, trying to keep the number of active generators to 134 that given in the constructor. 135 ''' 136 reference = GeneratorRef(generator, self.epoch) 137 self.__known[generator] = reference 138 self._debug(fmt('Queue size: {0}/{1}', 139 len(self.__queue), self.queue_len)) 140 # if we have space, simply save with no expiry 141 if self.queue_len == 0 or len(self.__queue) < self.queue_len: 142 self.__add_unlimited(reference) 143 else: 144 self.__add_limited(reference)
145
146 - def __add_unlimited(self, reference):
147 ''' 148 Add the new reference and discard any unused candidates that happen 149 to be on the top of the heap. 150 ''' 151 self._debug(fmt('Free space, so add {0}', reference)) 152 candidate = heappushpop(self.__queue, reference) 153 # clean out any unused references and make sure ordering correct 154 while candidate: 155 candidate.deletable(self.epoch) 156 if candidate.gced: 157 candidate = heappop(self.__queue) 158 else: 159 heappush(self.__queue, candidate) 160 break
161
162 - def __add_limited(self, reference):
163 ''' 164 Add the new reference, discarding an old entry if possible. 165 ''' 166 while reference: 167 candidate = heappushpop(self.__queue, reference) 168 self._debug(fmt('Exchanged {0} for {1}', reference, candidate)) 169 if candidate.order_epoch == self.epoch: 170 # even the oldest generator is current 171 break 172 elif candidate.deletable(self.epoch): 173 self._debug(fmt('Closing {0}', candidate)) 174 generator = candidate.generator 175 if generator: 176 del self.__known[generator] 177 candidate.close() 178 return 179 else: 180 # try again (candidate has been updated) 181 reference = candidate 182 # if we are here, queue is too small 183 heappush(self.__queue, candidate) 184 # this is currently 1 too small, and zero means unlimited, so 185 # doubling should always be sufficient. 186 self.queue_len = self.queue_len * 2 187 self._warn(fmt('Queue is too small - extending to {0}', self.queue_len))
188
189 190 -class GeneratorRef(object):
191 ''' 192 This contains the weak reference to the GeneratorWrapper and is stored 193 in the GC priority queue. 194 ''' 195
196 - def __init__(self, generator, epoch):
197 self.__hash = hash(generator) 198 self.__wrapper = ref(generator) 199 self.__last_known_epoch = epoch 200 self.order_epoch = epoch # readable externally 201 self.__count = 1 # add with 1 as we test for discard immediately after 202 self.gced = False 203 self.__describe = str(generator)
204
205 - def __lt__(self, other):
206 assert isinstance(other, GeneratorRef) 207 return self.order_epoch < other.order_epoch
208
209 - def __eq__(self, other):
210 return self is other
211
212 - def __hash__(self):
213 return self.__hash
214 215 @property
216 - def generator(self):
217 ''' 218 Provide access to the generator (or None, if it has been GCed). 219 ''' 220 return self.__wrapper()
221
222 - def pop(self, epoch):
223 ''' 224 When no longer used, safe epoch and decrement count. 225 ''' 226 self.__last_known_epoch = epoch 227 self.__count -= 1
228
229 - def push(self):
230 ''' 231 Added to stack, so increment count. 232 ''' 233 self.__count += 1
234
235 - def deletable(self, epoch):
236 ''' 237 Check we can delete the wrapper. 238 ''' 239 if not self.__wrapper(): 240 assert self.__count == 0, \ 241 fmt('GCed but still on stack?! {0}', self.__describe) 242 # already disposed by system 243 # this never happens because the monitor contains a reference 244 # in the value of the "known" dictionary 245 self.gced = True 246 return True 247 else: 248 # not on stack and ordering in queue was correct 249 if self.__count == 0 \ 250 and self.order_epoch == self.__last_known_epoch: 251 return True 252 # still on stack, or ordering was incorrect 253 else: 254 if self.__count: 255 self.__last_known_epoch = epoch 256 self.order_epoch = self.__last_known_epoch 257 return False
258
259 - def close(self):
260 ''' 261 This terminates the enclosed generator. 262 ''' 263 generator = self.generator 264 if generator: 265 generator.stream = None 266 generator.generator.close()
267
268 - def __str__(self):
269 generator = self.generator 270 if generator: 271 return fmt('{0} ({1:d}/{2:d})', 272 self.__describe, self.order_epoch, 273 self.__last_known_epoch) 274 else: 275 return fmt('Empty ref to {0}', self.__describe)
276
277 - def __repr__(self):
278 return str(self)
279