1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 '''
31 Matchers that combine sub-matchers (And, Or etc).
32 '''
33
34
35
36
37
38
39
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
54
55
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 '''
64 '''
65 Common base class (used by smart separators).
66 '''
67
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))
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
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
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
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)
249 '''
250 Support for `And` and `Or`.
251 '''
252
256
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
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
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
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:
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
433 count -= 1
434 except StopIteration:
435 pass
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