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