Package lepl :: Package matchers :: Module combine
[hide private]
[frames] | no frames]

Source Code for Module lepl.matchers.combine

  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  Matchers that combine sub-matchers (And, Or etc). 
 32  ''' 
 33   
 34  # pylint: disable-msg=C0103,W0212 
 35  # (consistent interfaces) 
 36  # pylint: disable-msg=E1101 
 37  # (_args create attributes) 
 38  # pylint: disable-msg=R0901, R0904, W0142 
 39  # lepl conventions 
 40   
 41  from abc import ABCMeta 
 42  from collections import deque 
 43  from operator import __add__ 
 44   
 45  from lepl.matchers.core import Literal 
 46  from lepl.matchers.matcher import add_children 
 47  from lepl.matchers.support import coerce_, sequence_matcher_factory, \ 
 48      trampoline_matcher_factory, to 
 49  from lepl.matchers.transform import Transformable 
 50  from lepl.support.lib import lmap, fmt, document 
 51   
 52   
 53  # pylint: disable-msg=C0103, W0105 
 54  # Python 2.6 
 55  #class BaseSearch(metaclass=ABCMeta): 
 56  _BaseSearch = ABCMeta('_BaseSearch', (object, ), {}) 
 57  ''' 
 58  ABC used to identify matchers.   
 59   
 60  Note that graph traversal assumes subclasses are hashable and iterable. 
 61  ''' 
62 63 -class BaseSearch(_BaseSearch):
64 ''' 65 Common base class (used by smart separators). 66 '''
67
68 69 -def search_factory(factory):
70 ''' 71 Add the arg processing common to all searching. 72 ''' 73 def new_factory(first, start, stop, rest=None, 74 generator_manager_queue_len=None): 75 rest = first if rest is None else rest 76 return factory(first, start, stop, rest, generator_manager_queue_len)
77 return document(new_factory, factory) 78
79 80 @trampoline_matcher_factory(first=to(Literal), rest=to(Literal)) 81 @search_factory 82 -def DepthFirst(first, start, stop, rest, generator_manager_queue_len):
83 ''' 84 (Post order) Depth first repetition (typically used via `Repeat`). 85 ''' 86 def match(support, stream): 87 stack = deque() 88 try: 89 stack.append((0, [], stream, first._match(stream))) 90 stream = None 91 while stack: 92 (count1, acc1, stream1, generator) = stack[-1] 93 extended = False 94 if stop == None or count1 < stop: 95 count2 = count1 + 1 96 try: 97 (value, stream2) = yield generator 98 acc2 = acc1 + value 99 stack.append((count2, acc2, stream2, rest._match(stream2))) 100 extended = True 101 except StopIteration: 102 pass 103 if not extended: 104 if count1 >= start and (stop == None or count1 <= stop): 105 yield (acc1, stream1) 106 stack.pop() 107 while support.generator_manager_queue_len \ 108 and len(stack) > support.generator_manager_queue_len: 109 stack.popleft()[3].generator.close() 110 finally: 111 while stack: 112 stack.popleft()[3].generator.close()
113 114 return match 115
116 117 @trampoline_matcher_factory(first=to(Literal), rest=to(Literal)) 118 @search_factory 119 -def BreadthFirst(first, start, stop, rest, generator_manager_queue_len):
120 ''' 121 (Level order) Breadth first repetition (typically used via `Repeat`). 122 ''' 123 def match(support, stream): 124 queue = deque() 125 try: 126 queue.append((0, [], stream, first._match(stream))) 127 stream = None 128 while queue: 129 (count1, acc1, stream1, generator) = queue.popleft() 130 if count1 >= start and (stop == None or count1 <= stop): 131 yield (acc1, stream1) 132 count2 = count1 + 1 133 try: 134 while True: 135 (value, stream2) = yield generator 136 acc2 = acc1 + value 137 if stop == None or count2 <= stop: 138 queue.append((count2, acc2, stream2, 139 rest._match(stream2))) 140 except StopIteration: 141 pass 142 while support.generator_manager_queue_len \ 143 and len(queue) > support.generator_manager_queue_len: 144 queue.popleft()[3].generator.close() 145 finally: 146 while queue: 147 queue.popleft()[3].generator.close()
148 149 return match 150 151 152 @trampoline_matcher_factory(matcher=to(Literal))
153 -def OrderByResultCount(matcher, ascending=True):
154 ''' 155 Modify a matcher to return results in length order. 156 ''' 157 def match(support, stream): 158 generator = matcher._match(stream) 159 results = [] 160 try: 161 while True: 162 # syntax error if this on one line?! 163 result = yield generator 164 results.append(result) 165 except StopIteration: 166 pass 167 for result in sorted(results, 168 key=lambda x: len(x[0]), reverse=ascending): 169 yield result
170 return match 171
172 173 @sequence_matcher_factory(first=to(Literal), rest=to(Literal)) 174 @search_factory 175 -def DepthNoTrampoline(first, start, stop, rest, generator_manager_queue_len):
176 ''' 177 A more efficient search when all matchers are functions (so no need to 178 trampoline). Depth first (greedy). 179 ''' 180 def matcher(support, stream): 181 stack = deque() 182 try: 183 stack.append((0, [], stream, first._untagged_match(stream))) 184 stream = None 185 while stack: 186 (count1, acc1, stream1, generator) = stack[-1] 187 extended = False 188 if stop == None or count1 < stop: 189 count2 = count1 + 1 190 try: 191 (value, stream2) = next(generator) 192 acc2 = acc1 + value 193 stack.append((count2, acc2, stream2, 194 rest._untagged_match(stream2))) 195 extended = True 196 except StopIteration: 197 pass 198 if not extended: 199 if count1 >= start and (stop == None or count1 <= stop): 200 yield (acc1, stream1) 201 stack.pop() 202 while support.generator_manager_queue_len \ 203 and len(stack) > support.generator_manager_queue_len: 204 stack.popleft()[3].close() 205 finally: 206 while stack: 207 stack.popleft()[3].close()
208 209 return matcher 210
211 212 @sequence_matcher_factory(first=to(Literal), rest=to(Literal)) 213 @search_factory 214 -def BreadthNoTrampoline(first, start, stop, rest, generator_manager_queue_len):
215 ''' 216 A more efficient search when all matchers are functions (so no need to 217 trampoline). Breadth first (non-greedy). 218 ''' 219 def matcher(support, stream): 220 queue = deque() 221 try: 222 queue.append((0, [], stream, first._untagged_match(stream))) 223 stream = None 224 while queue: 225 (count1, acc1, stream1, generator) = queue.popleft() 226 if count1 >= start and (stop == None or count1 <= stop): 227 yield (acc1, stream1) 228 count2 = count1 + 1 229 for (value, stream2) in generator: 230 acc2 = acc1 + value 231 if stop == None or count2 <= stop: 232 queue.append((count2, acc2, stream2, 233 rest._untagged_match(stream2))) 234 while support.generator_manager_queue_len \ 235 and len(queue) > support.generator_manager_queue_len: 236 queue.popleft()[3].close() 237 finally: 238 while queue: 239 queue.popleft()[3].close()
240 241 return matcher 242 243 244 add_children(BaseSearch, DepthFirst, BreadthFirst, \ 245 DepthNoTrampoline, BreadthNoTrampoline)
246 247 248 -class _BaseCombiner(Transformable):
249 ''' 250 Support for `And` and `Or`. 251 ''' 252
253 - def __init__(self, *matchers):
254 super(_BaseCombiner, self).__init__() 255 self._args(matchers=lmap(coerce_, matchers))
256
257 - def compose(self, wrapper):
258 ''' 259 Generate a new instance with the composed function from the Transform. 260 ''' 261 copy = type(self)(*self.matchers) 262 copy.wrapper = self.wrapper.compose(wrapper) 263 return copy
264
265 266 @trampoline_matcher_factory(args_=to(Literal)) 267 -def And(*matchers):
268 ''' 269 Match one or more matchers in sequence (**&**). 270 It can be used indirectly by placing ``&`` between matchers. 271 ''' 272 def match(support, stream_in): 273 if matchers: 274 stack = deque([([], 275 matchers[0]._match(stream_in), 276 matchers[1:])]) 277 append = stack.append 278 pop = stack.pop 279 stream_in = None 280 try: 281 while stack: 282 (result, generator, queued) = pop() 283 try: 284 (value, stream_out) = yield generator 285 append((result, generator, queued)) 286 if queued: 287 append((result+value, 288 queued[0]._match(stream_out), 289 queued[1:])) 290 else: 291 yield (result+value, stream_out) 292 except StopIteration: 293 pass 294 finally: 295 for (result, generator, queued) in stack: 296 generator.generator.close()
297 return match 298
299 300 @sequence_matcher_factory(args_=to(Literal)) 301 -def AndNoTrampoline(*matchers):
302 ''' 303 Used as an optimisation when sub-matchers do not require the trampoline. 304 ''' 305 def matcher(support, stream_in): 306 if matchers: 307 stack = deque([([], matchers[0]._untagged_match(stream_in), matchers[1:])]) 308 append = stack.append 309 pop = stack.pop 310 try: 311 while stack: 312 (result, generator, queued) = pop() 313 try: 314 (value, stream_out) = next(generator) 315 append((result, generator, queued)) 316 if queued: 317 append((result+value, 318 queued[0]._untagged_match(stream_out), 319 queued[1:])) 320 else: 321 yield (result+value, stream_out) 322 except StopIteration: 323 pass 324 finally: 325 for (result, generator, queued) in stack: 326 generator.close()
327 328 return matcher 329
330 331 @trampoline_matcher_factory(args_=to(Literal)) 332 -def Or(*matchers):
333 ''' 334 Match one of the given matchers (**|**). 335 It can be used indirectly by placing ``|`` between matchers. 336 337 Matchers are tried from left to right until one succeeds; backtracking 338 will try more from the same matcher and, once that is exhausted, 339 continue to the right. String arguments will be coerced to 340 literal matches. 341 ''' 342 def match(support, stream_in): 343 for matcher in matchers: 344 generator = matcher._match(stream_in) 345 try: 346 while True: 347 yield (yield generator) 348 except StopIteration: 349 pass
350 return match 351
352 353 @sequence_matcher_factory(args_=to(Literal)) 354 -def OrNoTrampoline(*matchers):
355 ''' 356 Used as an optimisation when sub-matchers do not require the trampoline. 357 ''' 358 def match(support, stream_in): 359 for matcher in matchers: 360 for result in matcher._untagged_match(stream_in): 361 yield result
362 return match 363
364 365 @trampoline_matcher_factory() 366 -def First(*matchers):
367 ''' 368 Match the first successful matcher only (**%**). 369 It can be used indirectly by placing ``%`` between matchers. 370 Note that backtracking for the first-selected matcher will still occur. 371 372 Matchers are tried from left to right until one succeeds; backtracking 373 will try more from the same matcher (only). String arguments will be 374 coerced to literal matches. 375 ''' 376 def match(support, stream): 377 matched = False 378 for matcher in support.matchers: 379 generator = matcher._match(stream) 380 try: 381 while True: 382 yield (yield generator) 383 matched = True 384 except StopIteration: 385 pass 386 if matched: 387 break
388 389 return match 390
391 392 @trampoline_matcher_factory(args_=to(Literal)) 393 -def Difference(matcher, exclude, count=-1):
394 ''' 395 Match with `matcher`, but exclude any matches that would be made by 396 `exclude`. This is implemented by comparing the remaining stream after 397 matching, so will not be affected by any transform associated with 398 `exclude`. The `count` parameter gives the number of different matches 399 from `exclude`. By default (-1) all matches are used. A positive 400 value restricts that to the number given. 401 ''' 402 def match(support, stream, count=count): 403 404 # by default use a set; fall back to a list for unhashable streams 405 bad = [None] 406 grow_bad = None 407 def append_bad(value, bad=bad): 408 bad[0].append(value)
409 def add_bad(value, bad=bad): 410 if bad[0] is None: 411 bad[0] = set() 412 try: 413 bad[0].add(value) 414 except TypeError: 415 assert not bad[0] 416 bad[0] = [] 417 grow_bad = append_bad 418 grow_bad(value) 419 grow_bad = add_bad 420 421 generator = matcher._match(stream) 422 while True: 423 (value, stream1) = yield generator 424 425 if bad[0] is None: # build bad on demand, once 426 bad_generator = exclude._match(stream) 427 try: 428 while count: 429 (excluded, stream2) = yield bad_generator 430 support._debug(fmt('Exclude: {0!r}', excluded)) 431 grow_bad(stream2) 432 # limit number of matchers, if requested 433 count -= 1 434 except StopIteration: 435 pass # all matches for exclude 436 437 if stream1 not in bad[0]: 438 yield (value, stream1) 439 else: 440 support._debug(fmt('Excluding: {0!r}', value)) 441 442 return match 443
444 445 @trampoline_matcher_factory(args_=to(Literal)) 446 -def Limit(match, count=1):
447 ''' 448 Limit the backtracking for a given matcher. A negative `count` means no 449 limit. 450 ''' 451 def matcher(support, stream, count=count): 452 generator = match._match(stream) 453 try: 454 while count: 455 yield (yield generator) 456 count -= 1 457 except StopIteration: 458 pass
459 return matcher 460