Debian Codegraph @

tests/dagpool_test.py

raw
1 """\
2 @file dagpool_test.py
3 @author Nat Goodspeed
4 @date 2016-08-26
5 @brief Test DAGPool class
6 """
7
8 import eventlet
9 from eventlet.dagpool import DAGPool, Collision, PropagateError
10 from contextlib import contextmanager
11 import itertools
12
13
14 def assert_equals(a, b):
15 """Backwards compatibility so we don't have to touch a bunch of tests."""
16 assert a == b
17
18
19 assert_equal = assert_equals
20
21
22 # Not all versions of nose.tools.assert_raises() support the usage in this
23 # module, but it's straightforward enough to code that explicitly.
24 @contextmanager
25 def assert_raises(exc):
26 """exc is an exception class"""
27 try:
28 yield
29 except exc:
30 pass
31 else:
32 raise AssertionError("failed to raise expected exception {}"
33 .format(exc.__class__.__name__))
34
35
36 def assert_in(sought, container):
37 assert sought in container, "{} not in {}".format(sought, container)
38
39
40 # ****************************************************************************
41 # Verify that a given operation returns without suspending
42 # ****************************************************************************
43 # module-scope counter allows us to verify when the main greenthread running
44 # the test does or does not suspend
45 counter = None
46
47
48 def incrementer():
49 """
50 This function runs as a background greenthread. Every time it regains
51 control, it increments 'counter' and relinquishes control again. The point
52 is that by testing 'counter' before and after a particular operation, a
53 test can determine whether other greenthreads were allowed to run during
54 that operation -- in other words, whether that operation suspended.
55 """
56 global counter
57 # suspend_checker() initializes counter to 0, so the first time we get
58 # control, set it to 1
59 for counter in itertools.count(1):
60 eventlet.sleep(0)
61
62
63 @contextmanager
64 def suspend_checker():
65 """
66 This context manager enables check_no_suspend() support. It runs the
67 incrementer() function as a background greenthread, then kills it off when
68 you exit the block.
69 """
70 global counter
71 # make counter not None to enable check_no_suspend()
72 counter = 0
73 coro = eventlet.spawn(incrementer)
74 yield
75 coro.kill()
76 # set counter back to None to disable check_no_suspend()
77 counter = None
78
79
80 @contextmanager
81 def check_no_suspend():
82 """
83 Within a 'with suspend_checker()' block, use 'with check_no_suspend()' to
84 verify that a particular operation does not suspend the calling
85 greenthread. If it does suspend, incrementer() will have regained control
86 and incremented the global 'counter'.
87 """
88 global counter
89 # It would be an easy mistake to use check_no_suspend() outside of a
90 # suspend_checker() block. Without the incrementer() greenthread running,
91 # 'counter' will never be incremented, therefore check_no_suspend() will
92 # always be satisfied, possibly masking bugs.
93 assert counter is not None, "Use 'with suspend_checker():' to enable check_no_suspend()"
94 current = counter
95 yield
96 assert counter == current, "Operation suspended {} times".format(counter - current)
97
98
99 def test_check_no_suspend():
100 with assert_raises(AssertionError):
101 # We WANT this to raise AssertionError because it's outside of a
102 # suspend_checker() block -- that is, we have no incrementer()
103 # greenthread.
104 with check_no_suspend():
105 pass
106
107 # Here we use check_no_suspend() the right way, inside 'with
108 # suspend_checker()'. Does it really do what we claim it should?
109 with suspend_checker():
110 with assert_raises(AssertionError):
111 with check_no_suspend():
112 # suspend, so we know if check_no_suspend() asserts
113 eventlet.sleep(0)
114
115
116 # ****************************************************************************
117 # Verify that the expected things happened in the expected order
118 # ****************************************************************************
119 class Capture:
120 """
121 This class is intended to capture a sequence (of string messages) to
122 verify that all expected events occurred, and in the expected order. The
123 tricky part is that certain subsequences can occur in arbitrary order and
124 still be correct.
125
126 Specifically, when posting a particular value to a DAGPool instance
127 unblocks several waiting greenthreads, it is indeterminate which
128 greenthread will first receive the new value.
129
130 Similarly, when several values for which a particular greenthread is
131 waiting become available at (effectively) the same time, it is
132 indeterminate in which order they will be delivered.
133
134 This is addressed by building a list of sets. Each set contains messages
135 that can occur in indeterminate order, therefore comparing that set to any
136 other ordering of the same messages should succeed. However, it's
137 important that each set of messages that occur 'at the same time' should
138 itself be properly sequenced with respect to all other such sets.
139 """
140 def __init__(self):
141 self.sequence = [set()]
142
143 def add(self, message):
144 self.sequence[-1].add(message)
145
146 def step(self):
147 self.sequence.append(set())
148
149 def validate(self, sequence):
150 # Let caller pass any sequence of grouped items. For comparison
151 # purposes, turn them into the specific form we store: a list of sets.
152 setlist = []
153 for subseq in sequence:
154 if isinstance(subseq, str):
155 # If this item is a plain string (which Python regards as an
156 # iterable of characters) rather than a list or tuple or set
157 # of strings, treat it as atomic. Make a set containing only
158 # that string.
159 setlist.append({subseq})
160 else:
161 try:
162 iter(subseq)
163 except TypeError:
164 # subseq is a scalar of some other kind. Make a set
165 # containing only that item.
166 setlist.append({subseq})
167 else:
168 # subseq is, as we expect, an iterable -- possibly already
169 # a set. Make a set containing its elements.
170 setlist.append(set(subseq))
171 # Now that we've massaged 'sequence' into 'setlist', compare.
172 assert_equal(self.sequence, setlist)
173
174
175 # ****************************************************************************
176 # Canonical DAGPool greenthread function
177 # ****************************************************************************
178 def observe(key, results, capture, event):
179 for k, v in results:
180 capture.add("{} got {}".format(key, k))
181 result = event.wait()
182 capture.add("{} returning {}".format(key, result))
183 return result
184
185
186 # ****************************************************************************
187 # DAGPool test functions
188 # ****************************************************************************
189 def test_init():
190 with suspend_checker():
191 # no preload data, just so we know it doesn't blow up
192 pool = DAGPool()
193
194 # preload dict
195 pool = DAGPool(dict(a=1, b=2, c=3))
196 # this must not hang
197 with check_no_suspend():
198 results = pool.waitall()
199 # with no spawn() or post(), waitall() returns preload data
200 assert_equal(results, dict(a=1, b=2, c=3))
201
202 # preload sequence of pairs
203 pool = DAGPool([("d", 4), ("e", 5), ("f", 6)])
204 # this must not hang
205 with check_no_suspend():
206 results = pool.waitall()
207 assert_equal(results, dict(d=4, e=5, f=6))
208
209
210 def test_wait_each_empty():
211 pool = DAGPool()
212 with suspend_checker():
213 with check_no_suspend():
214 for k, v in pool.wait_each(()):
215 # shouldn't yield anything
216 raise AssertionError("empty wait_each() returned ({}, {})".format(k, v))
217
218
219 def test_wait_each_preload():
220 pool = DAGPool(dict(a=1, b=2, c=3))
221 with suspend_checker():
222 with check_no_suspend():
223 # wait_each() may deliver in arbitrary order; collect into a dict
224 # for comparison
225 assert_equal(dict(pool.wait_each("abc")), dict(a=1, b=2, c=3))
226
227 # while we're at it, test wait() for preloaded keys
228 assert_equal(pool.wait("bc"), dict(b=2, c=3))
229
230
231 def post_each(pool, capture):
232 # distinguish the results wait_each() can retrieve immediately from those
233 # it must wait for us to post()
234 eventlet.sleep(0)
235 capture.step()
236 pool.post('g', 'gval')
237 pool.post('f', 'fval')
238 eventlet.sleep(0)
239 capture.step()
240 pool.post('e', 'eval')
241 pool.post('d', 'dval')
242
243
244 def test_wait_each_posted():
245 capture = Capture()
246 pool = DAGPool(dict(a=1, b=2, c=3))
247 eventlet.spawn(post_each, pool, capture)
248 # use a string as a convenient iterable of single-letter keys
249 for k, v in pool.wait_each("bcdefg"):
250 capture.add("got ({}, {})".format(k, v))
251
252 capture.validate([
253 ["got (b, 2)", "got (c, 3)"],
254 ["got (f, fval)", "got (g, gval)"],
255 ["got (d, dval)", "got (e, eval)"],
256 ])
257
258
259 def test_wait_posted():
260 # same as test_wait_each_posted(), but calling wait()
261 capture = Capture()
262 pool = DAGPool(dict(a=1, b=2, c=3))
263 eventlet.spawn(post_each, pool, capture)
264 gotten = pool.wait("bcdefg")
265 capture.add("got all")
266 assert_equal(gotten,
267 dict(b=2, c=3,
268 d="dval", e="eval",
269 f="fval", g="gval"))
270 capture.validate([
271 [],
272 [],
273 ["got all"],
274 ])
275
276
277 def test_spawn_collision_preload():
278 pool = DAGPool([("a", 1)])
279 with assert_raises(Collision):
280 pool.spawn("a", (), lambda key, results: None)
281
282
283 def test_spawn_collision_post():
284 pool = DAGPool()
285 pool.post("a", "aval")
286 with assert_raises(Collision):
287 pool.spawn("a", (), lambda key, results: None)
288
289
290 def test_spawn_collision_spawn():
291 pool = DAGPool()
292 pool.spawn("a", (), lambda key, results: "aval")
293 # hasn't yet even started
294 assert_equal(pool.get("a"), None)
295 with assert_raises(Collision):
296 # Attempting to spawn again with same key should collide even if the
297 # first spawned greenthread hasn't yet had a chance to run.
298 pool.spawn("a", (), lambda key, results: "bad")
299 # now let the spawned eventlet run
300 eventlet.sleep(0)
301 # should have finished
302 assert_equal(pool.get("a"), "aval")
303 with assert_raises(Collision):
304 # Attempting to spawn with same key collides even when the greenthread
305 # has completed.
306 pool.spawn("a", (), lambda key, results: "badagain")
307
308
309 def spin():
310 # Let all pending greenthreads run until they're blocked
311 for x in range(10):
312 eventlet.sleep(0)
313
314
315 def test_spawn_multiple():
316 capture = Capture()
317 pool = DAGPool(dict(a=1, b=2, c=3))
318 events = {}
319 for k in "defg":
320 events[k] = eventlet.event.Event()
321 pool.spawn(k, (), observe, capture, events[k])
322 # Now for a greenthread that depends on ALL the above.
323 events["h"] = eventlet.event.Event()
324 # trigger the last event right away: we only care about dependencies
325 events["h"].send("hval")
326 pool.spawn("h", "bcdefg", observe, capture, events["h"])
327
328 # let all the spawned greenthreads get as far as they can
329 spin()
330 capture.step()
331 # but none of them has yet produced a result
332 for k in "defgh":
333 assert_equal(pool.get(k), None)
334 assert_equal(set(pool.keys()), set("abc"))
335 assert_equal(dict(pool.items()), dict(a=1, b=2, c=3))
336 assert_equal(pool.running(), 5)
337 assert_equal(set(pool.running_keys()), set("defgh"))
338 assert_equal(pool.waiting(), 1)
339 assert_equal(pool.waiting_for(), dict(h=set("defg")))
340 assert_equal(pool.waiting_for("d"), set())
341 assert_equal(pool.waiting_for("c"), set())
342 with assert_raises(KeyError):
343 pool.waiting_for("j")
344 assert_equal(pool.waiting_for("h"), set("defg"))
345
346 # let one of the upstream greenthreads complete
347 events["f"].send("fval")
348 spin()
349 capture.step()
350 assert_equal(pool.get("f"), "fval")
351 assert_equal(set(pool.keys()), set("abcf"))
352 assert_equal(dict(pool.items()), dict(a=1, b=2, c=3, f="fval"))
353 assert_equal(pool.running(), 4)
354 assert_equal(set(pool.running_keys()), set("degh"))
355 assert_equal(pool.waiting(), 1)
356 assert_equal(pool.waiting_for("h"), set("deg"))
357
358 # now two others
359 events["e"].send("eval")
360 events["g"].send("gval")
361 spin()
362 capture.step()
363 assert_equal(pool.get("e"), "eval")
364 assert_equal(pool.get("g"), "gval")
365 assert_equal(set(pool.keys()), set("abcefg"))
366 assert_equal(dict(pool.items()),
367 dict(a=1, b=2, c=3, e="eval", f="fval", g="gval"))
368 assert_equal(pool.running(), 2)
369 assert_equal(set(pool.running_keys()), set("dh"))
370 assert_equal(pool.waiting(), 1)
371 assert_equal(pool.waiting_for("h"), set("d"))
372
373 # last one
374 events["d"].send("dval")
375 # make sure both pool greenthreads get a chance to run
376 spin()
377 capture.step()
378 assert_equal(pool.get("d"), "dval")
379 assert_equal(set(pool.keys()), set("abcdefgh"))
380 assert_equal(dict(pool.items()),
381 dict(a=1, b=2, c=3,
382 d="dval", e="eval", f="fval", g="gval", h="hval"))
383 assert_equal(pool.running(), 0)
384 assert not pool.running_keys()
385 assert_equal(pool.waiting(), 0)
386 assert_equal(pool.waiting_for("h"), set())
387 capture.validate([
388 ["h got b", "h got c"],
389 ["f returning fval", "h got f"],
390 ["e returning eval", "g returning gval",
391 "h got e", "h got g"],
392 ["d returning dval", "h got d", "h returning hval"],
393 [],
394 ])
395
396
397 def spawn_many_func(key, results, capture, pool):
398 for k, v in results:
399 # with a capture.step() at each post(), too complicated to predict
400 # which results will be delivered when
401 pass
402 capture.add("{} done".format(key))
403 # use post(key) instead of waiting for implicit post() of return value
404 pool.post(key, key)
405 capture.step()
406 spin()
407
408
409 def waitall_done(capture, pool):
410 pool.waitall()
411 capture.add("waitall() done")
412
413
414 def test_spawn_many():
415 # This dependencies dict sets up a graph like this:
416 # a
417 # / \
418 # b c
419 # \ /|
420 # d |
421 # \|
422 # e
423
424 deps = dict(e="cd",
425 d="bc",
426 c="a",
427 b="a",
428 a="")
429
430 capture = Capture()
431 pool = DAGPool()
432 # spawn a waitall() waiter externally to our DAGPool, but capture its
433 # message in same Capture instance
434 eventlet.spawn(waitall_done, capture, pool)
435 pool.spawn_many(deps, spawn_many_func, capture, pool)
436 # This set of greenthreads should in fact run to completion once spawned.
437 spin()
438 # verify that e completed (also that post(key) within greenthread
439 # overrides implicit post of return value, which would be None)
440 assert_equal(pool.get("e"), "e")
441
442 # With the dependency graph shown above, it is not guaranteed whether b or
443 # c will complete first. Handle either case.
444 sequence = capture.sequence[:]
445 sequence[1:3] = [{sequence[1].pop(), sequence[2].pop()}]
446 assert_equal(sequence,
447 [{"a done"},
448 {"b done", "c done"},
449 {"d done"},
450 {"e done"},
451 {"waitall() done"},
452 ])
453
454
455 # deliberately distinguish this from dagpool._MISSING
456 _notthere = object()
457
458
459 def test_wait_each_all():
460 # set up a simple linear dependency chain
461 deps = dict(b="a", c="b", d="c", e="d")
462 capture = Capture()
463 pool = DAGPool([("a", "a")])
464 # capture a different Event for each key
465 events = {key: eventlet.event.Event() for key in deps.keys()}
466 # can't use spawn_many() because we need a different event for each
467 for key, dep in deps.items():
468 pool.spawn(key, dep, observe, capture, events[key])
469 keys = "abcde" # this specific order
470 each = iter(pool.wait_each())
471 for pos in range(len(keys)):
472 # next value from wait_each()
473 k, v = next(each)
474 assert_equal(k, keys[pos])
475 # advance every pool greenlet as far as it can go
476 spin()
477 # everything from keys[:pos+1] should have a value by now
478 for k in keys[:pos + 1]:
479 assert pool.get(k, _notthere) is not _notthere, \
480 "greenlet {} did not yet produce a value".format(k)
481 # everything from keys[pos+1:] should not yet
482 for k in keys[pos + 1:]:
483 assert pool.get(k, _notthere) is _notthere, \
484 "wait_each() delayed value for {}".format(keys[pos])
485 # let next greenthread complete
486 if pos < len(keys) - 1:
487 k = keys[pos + 1]
488 events[k].send(k)
489
490
491 def test_kill():
492 pool = DAGPool()
493 # nonexistent key raises KeyError
494 with assert_raises(KeyError):
495 pool.kill("a")
496 # spawn a greenthread
497 pool.spawn("a", (), lambda key, result: 1)
498 # kill it before it can even run
499 pool.kill("a")
500 # didn't run
501 spin()
502 assert_equal(pool.get("a"), None)
503 # killing it forgets about it
504 with assert_raises(KeyError):
505 pool.kill("a")
506 # so that we can try again
507 pool.spawn("a", (), lambda key, result: 2)
508 spin()
509 # this time it ran to completion, so can no longer be killed
510 with assert_raises(KeyError):
511 pool.kill("a")
512 # verify it ran to completion
513 assert_equal(pool.get("a"), 2)
514
515
516 def test_post_collision_preload():
517 pool = DAGPool(dict(a=1))
518 with assert_raises(Collision):
519 pool.post("a", 2)
520
521
522 def test_post_collision_post():
523 pool = DAGPool()
524 pool.post("a", 1)
525 with assert_raises(Collision):
526 pool.post("a", 2)
527
528
529 def test_post_collision_spawn():
530 pool = DAGPool()
531 pool.spawn("a", (), lambda key, result: 1)
532 # hasn't yet run
533 with assert_raises(Collision):
534 # n.b. This exercises the code that tests whether post(key) is or is
535 # not coming from that key's greenthread.
536 pool.post("a", 2)
537 # kill it
538 pool.kill("a")
539 # now we can post
540 pool.post("a", 3)
541 assert_equal(pool.get("a"), 3)
542
543 pool = DAGPool()
544 pool.spawn("a", (), lambda key, result: 4)
545 # run it
546 spin()
547 with assert_raises(Collision):
548 pool.post("a", 5)
549 # can't kill it now either
550 with assert_raises(KeyError):
551 pool.kill("a")
552 # still can't post
553 with assert_raises(Collision):
554 pool.post("a", 6)
555
556
557 def test_post_replace():
558 pool = DAGPool()
559 pool.post("a", 1)
560 pool.post("a", 2, replace=True)
561 assert_equal(pool.get("a"), 2)
562 assert_equal(dict(pool.wait_each("a")), dict(a=2))
563 assert_equal(pool.wait("a"), dict(a=2))
564 assert_equal(pool["a"], 2)
565
566
567 def waitfor(capture, pool, key):
568 value = pool[key]
569 capture.add("got {}".format(value))
570
571
572 def test_getitem():
573 capture = Capture()
574 pool = DAGPool()
575 eventlet.spawn(waitfor, capture, pool, "a")
576 # pool["a"] just waiting
577 capture.validate([[]])
578 pool.spawn("a", (), lambda key, results: 1)
579 # still waiting: hasn't yet run
580 capture.validate([[]])
581 # run it
582 spin()
583 capture.validate([["got 1"]])
584
585
586 class BogusError(Exception):
587 pass
588
589
590 def raiser(key, results, exc):
591 raise exc
592
593
594 def consumer(key, results):
595 for k, v in results:
596 pass
597 return True
598
599
600 def test_waitall_exc():
601 pool = DAGPool()
602 pool.spawn("a", (), raiser, BogusError("bogus"))
603 try:
604 pool.waitall()
605 except PropagateError as err:
606 assert_equal(err.key, "a")
607 assert isinstance(err.exc, BogusError), \
608 "exc attribute is {}, not BogusError".format(err.exc)
609 assert_equal(str(err.exc), "bogus")
610 msg = str(err)
611 assert_in("PropagateError(a)", msg)
612 assert_in("BogusError", msg)
613 assert_in("bogus", msg)
614
615
616 def test_propagate_exc():
617 pool = DAGPool()
618 pool.spawn("a", (), raiser, BogusError("bogus"))
619 pool.spawn("b", "a", consumer)
620 pool.spawn("c", "b", consumer)
621 try:
622 pool["c"]
623 except PropagateError as errc:
624 assert_equal(errc.key, "c")
625 errb = errc.exc
626 assert_equal(errb.key, "b")
627 erra = errb.exc
628 assert_equal(erra.key, "a")
629 assert isinstance(erra.exc, BogusError), \
630 "exc attribute is {}, not BogusError".format(erra.exc)
631 assert_equal(str(erra.exc), "bogus")
632 msg = str(errc)
633 assert_in("PropagateError(a)", msg)
634 assert_in("PropagateError(b)", msg)
635 assert_in("PropagateError(c)", msg)
636 assert_in("BogusError", msg)
637 assert_in("bogus", msg)
638
639
640 def test_wait_each_exc():
641 pool = DAGPool()
642 pool.spawn("a", (), raiser, BogusError("bogus"))
643 with assert_raises(PropagateError):
644 for k, v in pool.wait_each("a"):
645 pass
646
647 with assert_raises(PropagateError):
648 for k, v in pool.wait_each():
649 pass
650
651
652 def test_post_get_exc():
653 pool = DAGPool()
654 bogua = BogusError("bogua")
655 pool.post("a", bogua)
656 assert isinstance(pool.get("a"), BogusError), \
657 "should have delivered BogusError instead of raising"
658 bogub = PropagateError("b", BogusError("bogub"))
659 pool.post("b", bogub)
660 with assert_raises(PropagateError):
661 pool.get("b")
662
663 # Notice that although we have both "a" and "b" keys, items() is
664 # guaranteed to raise PropagateError because one of them is
665 # PropagateError. Other values don't matter.
666 with assert_raises(PropagateError):
667 pool.items()
668
669 # Similar remarks about waitall() and wait().
670 with assert_raises(PropagateError):
671 pool.waitall()
672 with assert_raises(PropagateError):
673 pool.wait()
674 with assert_raises(PropagateError):
675 pool.wait("b")
676 with assert_raises(PropagateError):
677 pool.wait("ab")
678 # but if we're only wait()ing for success results, no exception
679 assert isinstance(pool.wait("a")["a"], BogusError), \
680 "should have delivered BogusError instead of raising"
681
682 # wait_each() is guaranteed to eventually raise PropagateError, though you
683 # may obtain valid values before you hit it.
684 with assert_raises(PropagateError):
685 for k, v in pool.wait_each():
686 pass
687
688 # wait_each_success() filters
689 assert_equal(dict(pool.wait_each_success()), dict(a=bogua))
690 assert_equal(dict(pool.wait_each_success("ab")), dict(a=bogua))
691 assert_equal(dict(pool.wait_each_success("a")), dict(a=bogua))
692 assert_equal(dict(pool.wait_each_success("b")), {})
693
694 # wait_each_exception() filters the other way
695 assert_equal(dict(pool.wait_each_exception()), dict(b=bogub))
696 assert_equal(dict(pool.wait_each_exception("ab")), dict(b=bogub))
697 assert_equal(dict(pool.wait_each_exception("a")), {})
698 assert_equal(dict(pool.wait_each_exception("b")), dict(b=bogub))