2 def foo(): pass # keep the line number constant
5 from StringIO import StringIO
6 from twisted.trial import unittest
7 from twisted.internet import defer, reactor
8 from twisted.python.failure import Failure
9 from twisted.python import log
10 from hashlib import md5
12 from allmydata.util import base32, idlib, humanreadable, mathutil, hashutil
13 from allmydata.util import assertutil, fileutil, deferredutil, abbreviate
14 from allmydata.util import limiter, time_format, pollmixin, cachedir
15 from allmydata.util import statistics, dictutil, pipeline
16 from allmydata.util import log as tahoe_log
17 from allmydata.util.spans import Spans, overlap, DataSpans
19 class Base32(unittest.TestCase):
20 def test_b2a_matches_Pythons(self):
22 y = "\x12\x34\x45\x67\x89\x0a\xbc\xde\xf0"
23 x = base64.b32encode(y)
24 while x and x[-1] == '=':
27 self.failUnlessEqual(base32.b2a(y), x)
29 self.failUnlessEqual(base32.b2a("\x12\x34"), "ci2a")
30 def test_b2a_or_none(self):
31 self.failUnlessEqual(base32.b2a_or_none(None), None)
32 self.failUnlessEqual(base32.b2a_or_none("\x12\x34"), "ci2a")
34 self.failUnlessEqual(base32.a2b("ci2a"), "\x12\x34")
35 self.failUnlessRaises(AssertionError, base32.a2b, "b0gus")
37 class IDLib(unittest.TestCase):
38 def test_nodeid_b2a(self):
39 self.failUnlessEqual(idlib.nodeid_b2a("\x00"*20), "a"*32)
41 class NoArgumentException(Exception):
45 class HumanReadable(unittest.TestCase):
48 self.failUnlessEqual(hr(foo), "<foo() at test_util.py:2>")
49 self.failUnlessEqual(hr(self.test_repr),
50 "<bound method HumanReadable.test_repr of <allmydata.test.test_util.HumanReadable testMethod=test_repr>>")
51 self.failUnlessEqual(hr(1L), "1")
52 self.failUnlessEqual(hr(10**40),
53 "100000000000000000...000000000000000000")
54 self.failUnlessEqual(hr(self), "<allmydata.test.test_util.HumanReadable testMethod=test_repr>")
55 self.failUnlessEqual(hr([1,2]), "[1, 2]")
56 self.failUnlessEqual(hr({1:2}), "{1:2}")
61 hr(e) == "<ValueError: ()>" # python-2.4
62 or hr(e) == "ValueError()") # python-2.5
64 raise ValueError("oops")
67 hr(e) == "<ValueError: 'oops'>" # python-2.4
68 or hr(e) == "ValueError('oops',)") # python-2.5
70 raise NoArgumentException
73 hr(e) == "<NoArgumentException>" # python-2.4
74 or hr(e) == "NoArgumentException()") # python-2.5
80 class Math(unittest.TestCase):
81 def test_div_ceil(self):
83 self.failUnlessEqual(f(0, 1), 0)
84 self.failUnlessEqual(f(0, 2), 0)
85 self.failUnlessEqual(f(0, 3), 0)
86 self.failUnlessEqual(f(1, 3), 1)
87 self.failUnlessEqual(f(2, 3), 1)
88 self.failUnlessEqual(f(3, 3), 1)
89 self.failUnlessEqual(f(4, 3), 2)
90 self.failUnlessEqual(f(5, 3), 2)
91 self.failUnlessEqual(f(6, 3), 2)
92 self.failUnlessEqual(f(7, 3), 3)
94 def test_next_multiple(self):
95 f = mathutil.next_multiple
96 self.failUnlessEqual(f(5, 1), 5)
97 self.failUnlessEqual(f(5, 2), 6)
98 self.failUnlessEqual(f(5, 3), 6)
99 self.failUnlessEqual(f(5, 4), 8)
100 self.failUnlessEqual(f(5, 5), 5)
101 self.failUnlessEqual(f(5, 6), 6)
102 self.failUnlessEqual(f(32, 1), 32)
103 self.failUnlessEqual(f(32, 2), 32)
104 self.failUnlessEqual(f(32, 3), 33)
105 self.failUnlessEqual(f(32, 4), 32)
106 self.failUnlessEqual(f(32, 5), 35)
107 self.failUnlessEqual(f(32, 6), 36)
108 self.failUnlessEqual(f(32, 7), 35)
109 self.failUnlessEqual(f(32, 8), 32)
110 self.failUnlessEqual(f(32, 9), 36)
111 self.failUnlessEqual(f(32, 10), 40)
112 self.failUnlessEqual(f(32, 11), 33)
113 self.failUnlessEqual(f(32, 12), 36)
114 self.failUnlessEqual(f(32, 13), 39)
115 self.failUnlessEqual(f(32, 14), 42)
116 self.failUnlessEqual(f(32, 15), 45)
117 self.failUnlessEqual(f(32, 16), 32)
118 self.failUnlessEqual(f(32, 17), 34)
119 self.failUnlessEqual(f(32, 18), 36)
120 self.failUnlessEqual(f(32, 589), 589)
122 def test_pad_size(self):
123 f = mathutil.pad_size
124 self.failUnlessEqual(f(0, 4), 0)
125 self.failUnlessEqual(f(1, 4), 3)
126 self.failUnlessEqual(f(2, 4), 2)
127 self.failUnlessEqual(f(3, 4), 1)
128 self.failUnlessEqual(f(4, 4), 0)
129 self.failUnlessEqual(f(5, 4), 3)
131 def test_is_power_of_k(self):
132 f = mathutil.is_power_of_k
133 for i in range(1, 100):
134 if i in (1, 2, 4, 8, 16, 32, 64):
135 self.failUnless(f(i, 2), "but %d *is* a power of 2" % i)
137 self.failIf(f(i, 2), "but %d is *not* a power of 2" % i)
138 for i in range(1, 100):
139 if i in (1, 3, 9, 27, 81):
140 self.failUnless(f(i, 3), "but %d *is* a power of 3" % i)
142 self.failIf(f(i, 3), "but %d is *not* a power of 3" % i)
144 def test_next_power_of_k(self):
145 f = mathutil.next_power_of_k
146 self.failUnlessEqual(f(0,2), 1)
147 self.failUnlessEqual(f(1,2), 1)
148 self.failUnlessEqual(f(2,2), 2)
149 self.failUnlessEqual(f(3,2), 4)
150 self.failUnlessEqual(f(4,2), 4)
151 for i in range(5, 8): self.failUnlessEqual(f(i,2), 8, "%d" % i)
152 for i in range(9, 16): self.failUnlessEqual(f(i,2), 16, "%d" % i)
153 for i in range(17, 32): self.failUnlessEqual(f(i,2), 32, "%d" % i)
154 for i in range(33, 64): self.failUnlessEqual(f(i,2), 64, "%d" % i)
155 for i in range(65, 100): self.failUnlessEqual(f(i,2), 128, "%d" % i)
157 self.failUnlessEqual(f(0,3), 1)
158 self.failUnlessEqual(f(1,3), 1)
159 self.failUnlessEqual(f(2,3), 3)
160 self.failUnlessEqual(f(3,3), 3)
161 for i in range(4, 9): self.failUnlessEqual(f(i,3), 9, "%d" % i)
162 for i in range(10, 27): self.failUnlessEqual(f(i,3), 27, "%d" % i)
163 for i in range(28, 81): self.failUnlessEqual(f(i,3), 81, "%d" % i)
164 for i in range(82, 200): self.failUnlessEqual(f(i,3), 243, "%d" % i)
168 self.failUnlessEqual(f([1,2,3]), 2)
169 self.failUnlessEqual(f([0,0,0,4]), 1)
170 self.failUnlessAlmostEqual(f([0.0, 1.0, 1.0]), .666666666666)
172 def test_round_sigfigs(self):
173 f = mathutil.round_sigfigs
174 self.failUnlessEqual(f(22.0/3, 4), 7.3330000000000002)
176 class Statistics(unittest.TestCase):
177 def should_assert(self, msg, func, *args, **kwargs):
179 func(*args, **kwargs)
181 except AssertionError:
184 def failUnlessListEqual(self, a, b, msg = None):
185 self.failUnlessEqual(len(a), len(b))
186 for i in range(len(a)):
187 self.failUnlessEqual(a[i], b[i], msg)
189 def failUnlessListAlmostEqual(self, a, b, places = 7, msg = None):
190 self.failUnlessEqual(len(a), len(b))
191 for i in range(len(a)):
192 self.failUnlessAlmostEqual(a[i], b[i], places, msg)
194 def test_binomial_coeff(self):
195 f = statistics.binomial_coeff
196 self.failUnlessEqual(f(20, 0), 1)
197 self.failUnlessEqual(f(20, 1), 20)
198 self.failUnlessEqual(f(20, 2), 190)
199 self.failUnlessEqual(f(20, 8), f(20, 12))
200 self.should_assert("Should assert if n < k", f, 2, 3)
202 def test_binomial_distribution_pmf(self):
203 f = statistics.binomial_distribution_pmf
206 pmf_stat = [0.81, 0.18, 0.01]
207 self.failUnlessListAlmostEqual(pmf_comp, pmf_stat)
209 # Summing across a PMF should give the total probability 1
210 self.failUnlessAlmostEqual(sum(pmf_comp), 1)
211 self.should_assert("Should assert if not 0<=p<=1", f, 1, -1)
212 self.should_assert("Should assert if n < 1", f, 0, .1)
215 statistics.print_pmf(pmf_comp, out=out)
216 lines = out.getvalue().splitlines()
217 self.failUnlessEqual(lines[0], "i=0: 0.81")
218 self.failUnlessEqual(lines[1], "i=1: 0.18")
219 self.failUnlessEqual(lines[2], "i=2: 0.01")
221 def test_survival_pmf(self):
222 f = statistics.survival_pmf
223 # Cross-check binomial-distribution method against convolution
225 p_list = [.9999] * 100 + [.99] * 50 + [.8] * 20
226 pmf1 = statistics.survival_pmf_via_conv(p_list)
227 pmf2 = statistics.survival_pmf_via_bd(p_list)
228 self.failUnlessListAlmostEqual(pmf1, pmf2)
229 self.failUnlessTrue(statistics.valid_pmf(pmf1))
230 self.should_assert("Should assert if p_i > 1", f, [1.1]);
231 self.should_assert("Should assert if p_i < 0", f, [-.1]);
233 def test_repair_count_pmf(self):
234 survival_pmf = statistics.binomial_distribution_pmf(5, .9)
235 repair_pmf = statistics.repair_count_pmf(survival_pmf, 3)
236 # repair_pmf[0] == sum(survival_pmf[0,1,2,5])
237 # repair_pmf[1] == survival_pmf[4]
238 # repair_pmf[2] = survival_pmf[3]
239 self.failUnlessListAlmostEqual(repair_pmf,
240 [0.00001 + 0.00045 + 0.0081 + 0.59049,
245 def test_repair_cost(self):
246 survival_pmf = statistics.binomial_distribution_pmf(5, .9)
247 bwcost = statistics.bandwidth_cost_function
248 cost = statistics.mean_repair_cost(bwcost, 1000,
249 survival_pmf, 3, ul_dl_ratio=1.0)
250 self.failUnlessAlmostEqual(cost, 558.90)
251 cost = statistics.mean_repair_cost(bwcost, 1000,
252 survival_pmf, 3, ul_dl_ratio=8.0)
253 self.failUnlessAlmostEqual(cost, 1664.55)
255 # I haven't manually checked the math beyond here -warner
256 cost = statistics.eternal_repair_cost(bwcost, 1000,
258 discount_rate=0, ul_dl_ratio=1.0)
259 self.failUnlessAlmostEqual(cost, 65292.056074766246)
260 cost = statistics.eternal_repair_cost(bwcost, 1000,
264 self.failUnlessAlmostEqual(cost, 9133.6097158191551)
266 def test_convolve(self):
267 f = statistics.convolve
271 v1v2result = [ 4, 13, 28, 27, 18 ]
272 # Convolution is commutative
275 self.failUnlessListEqual(r1, r2, "Convolution should be commutative")
276 self.failUnlessListEqual(r1, v1v2result, "Didn't match known result")
277 # Convolution is associative
278 r1 = f(f(v1, v2), v3)
279 r2 = f(v1, f(v2, v3))
280 self.failUnlessListEqual(r1, r2, "Convolution should be associative")
281 # Convolution is distributive
282 r1 = f(v3, [ a + b for a, b in zip(v1, v2) ])
285 r2 = [ a + b for a, b in zip(tmp1, tmp2) ]
286 self.failUnlessListEqual(r1, r2, "Convolution should be distributive")
287 # Convolution is scalar multiplication associative
289 r1 = [ a * 4 for a in tmp1 ]
290 tmp2 = [ a * 4 for a in v1 ]
292 self.failUnlessListEqual(r1, r2, "Convolution should be scalar multiplication associative")
294 def test_find_k(self):
295 f = statistics.find_k
296 g = statistics.pr_file_loss
297 plist = [.9] * 10 + [.8] * 10 # N=20
300 self.failUnlessEqual(k, 10)
301 self.failUnless(g(plist, k) < t)
303 def test_pr_file_loss(self):
304 f = statistics.pr_file_loss
306 self.failUnlessEqual(f(plist, 3), .0546875)
308 def test_pr_backup_file_loss(self):
309 f = statistics.pr_backup_file_loss
311 self.failUnlessEqual(f(plist, .5, 3), .02734375)
314 class Asserts(unittest.TestCase):
315 def should_assert(self, func, *args, **kwargs):
317 func(*args, **kwargs)
318 except AssertionError, e:
321 self.fail("assert failed with non-AssertionError: %s" % e)
322 self.fail("assert was not caught")
324 def should_not_assert(self, func, *args, **kwargs):
326 func(*args, **kwargs)
327 except AssertionError, e:
328 self.fail("assertion fired when it should not have: %s" % e)
330 self.fail("assertion (which shouldn't have failed) failed with non-AssertionError: %s" % e)
334 def test_assert(self):
335 f = assertutil._assert
336 self.should_assert(f)
337 self.should_assert(f, False)
338 self.should_not_assert(f, True)
340 m = self.should_assert(f, False, "message")
341 self.failUnlessEqual(m, "'message' <type 'str'>", m)
342 m = self.should_assert(f, False, "message1", othermsg=12)
343 self.failUnlessEqual("'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
344 m = self.should_assert(f, False, othermsg="message2")
345 self.failUnlessEqual("othermsg: 'message2' <type 'str'>", m)
347 def test_precondition(self):
348 f = assertutil.precondition
349 self.should_assert(f)
350 self.should_assert(f, False)
351 self.should_not_assert(f, True)
353 m = self.should_assert(f, False, "message")
354 self.failUnlessEqual("precondition: 'message' <type 'str'>", m)
355 m = self.should_assert(f, False, "message1", othermsg=12)
356 self.failUnlessEqual("precondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
357 m = self.should_assert(f, False, othermsg="message2")
358 self.failUnlessEqual("precondition: othermsg: 'message2' <type 'str'>", m)
360 def test_postcondition(self):
361 f = assertutil.postcondition
362 self.should_assert(f)
363 self.should_assert(f, False)
364 self.should_not_assert(f, True)
366 m = self.should_assert(f, False, "message")
367 self.failUnlessEqual("postcondition: 'message' <type 'str'>", m)
368 m = self.should_assert(f, False, "message1", othermsg=12)
369 self.failUnlessEqual("postcondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
370 m = self.should_assert(f, False, othermsg="message2")
371 self.failUnlessEqual("postcondition: othermsg: 'message2' <type 'str'>", m)
373 class FileUtil(unittest.TestCase):
374 def mkdir(self, basedir, path, mode=0777):
375 fn = os.path.join(basedir, path)
376 fileutil.make_dirs(fn, mode)
378 def touch(self, basedir, path, mode=None, data="touch\n"):
379 fn = os.path.join(basedir, path)
386 def test_rm_dir(self):
387 basedir = "util/FileUtil/test_rm_dir"
388 fileutil.make_dirs(basedir)
389 # create it again to test idempotency
390 fileutil.make_dirs(basedir)
391 d = os.path.join(basedir, "doomed")
393 self.touch(d, "a/b/1.txt")
394 self.touch(d, "a/b/2.txt", 0444)
395 self.touch(d, "a/b/3.txt", 0)
397 self.touch(d, "a/c/1.txt")
398 self.touch(d, "a/c/2.txt", 0444)
399 self.touch(d, "a/c/3.txt", 0)
400 os.chmod(os.path.join(d, "a/c"), 0444)
402 self.touch(d, "a/d/1.txt")
403 self.touch(d, "a/d/2.txt", 0444)
404 self.touch(d, "a/d/3.txt", 0)
405 os.chmod(os.path.join(d, "a/d"), 0)
408 self.failIf(os.path.exists(d))
409 # remove it again to test idempotency
412 def test_remove_if_possible(self):
413 basedir = "util/FileUtil/test_remove_if_possible"
414 fileutil.make_dirs(basedir)
415 self.touch(basedir, "here")
416 fn = os.path.join(basedir, "here")
417 fileutil.remove_if_possible(fn)
418 self.failIf(os.path.exists(fn))
419 fileutil.remove_if_possible(fn) # should be idempotent
420 fileutil.rm_dir(basedir)
421 fileutil.remove_if_possible(fn) # should survive errors
423 def test_open_or_create(self):
424 basedir = "util/FileUtil/test_open_or_create"
425 fileutil.make_dirs(basedir)
426 fn = os.path.join(basedir, "here")
427 f = fileutil.open_or_create(fn)
430 f = fileutil.open_or_create(fn)
437 self.failUnlessEqual(data, "stuff.more.")
439 def test_NamedTemporaryDirectory(self):
440 basedir = "util/FileUtil/test_NamedTemporaryDirectory"
441 fileutil.make_dirs(basedir)
442 td = fileutil.NamedTemporaryDirectory(dir=basedir)
444 self.failUnless(basedir in name)
445 self.failUnless(basedir in repr(td))
446 self.failUnless(os.path.isdir(name))
448 # it is conceivable that we need to force gc here, but I'm not sure
449 self.failIf(os.path.isdir(name))
451 def test_rename(self):
452 basedir = "util/FileUtil/test_rename"
453 fileutil.make_dirs(basedir)
454 self.touch(basedir, "here")
455 fn = os.path.join(basedir, "here")
456 fn2 = os.path.join(basedir, "there")
457 fileutil.rename(fn, fn2)
458 self.failIf(os.path.exists(fn))
459 self.failUnless(os.path.exists(fn2))
462 basedir = "util/FileUtil/test_du"
463 fileutil.make_dirs(basedir)
464 d = os.path.join(basedir, "space-consuming")
466 self.touch(d, "a/b/1.txt", data="a"*10)
467 self.touch(d, "a/b/2.txt", data="b"*11)
469 self.touch(d, "a/c/1.txt", data="c"*12)
470 self.touch(d, "a/c/2.txt", data="d"*13)
472 used = fileutil.du(basedir)
473 self.failUnlessEqual(10+11+12+13, used)
475 def test_abspath_expanduser_unicode(self):
476 self.failUnlessRaises(AssertionError, fileutil.abspath_expanduser_unicode, "bytestring")
478 saved_cwd = os.path.normpath(os.getcwdu())
479 abspath_cwd = fileutil.abspath_expanduser_unicode(u".")
480 self.failUnless(isinstance(saved_cwd, unicode), saved_cwd)
481 self.failUnless(isinstance(abspath_cwd, unicode), abspath_cwd)
482 self.failUnlessEqual(abspath_cwd, saved_cwd)
484 # adapted from <http://svn.python.org/view/python/branches/release26-maint/Lib/test/test_posixpath.py?view=markup&pathrev=78279#test_abspath>
486 self.failUnlessIn(u"foo", fileutil.abspath_expanduser_unicode(u"foo"))
487 self.failIfIn(u"~", fileutil.abspath_expanduser_unicode(u"~"))
491 cwds.append(u'\xe7w\xf0'.encode(sys.getfilesystemencoding()
493 except UnicodeEncodeError:
494 pass # the cwd can't be encoded -- test with ascii cwd only
500 for upath in (u'', u'fuu', u'f\xf9\xf9', u'/fuu', u'U:\\', u'~'):
501 uabspath = fileutil.abspath_expanduser_unicode(upath)
502 self.failUnless(isinstance(uabspath, unicode), uabspath)
506 class PollMixinTests(unittest.TestCase):
508 self.pm = pollmixin.PollMixin()
510 def test_PollMixin_True(self):
511 d = self.pm.poll(check_f=lambda : True,
515 def test_PollMixin_False_then_True(self):
516 i = iter([False, True])
517 d = self.pm.poll(check_f=i.next,
521 def test_timeout(self):
522 d = self.pm.poll(check_f=lambda: False,
526 self.fail("poll should have failed, not returned %s" % (res,))
528 f.trap(pollmixin.TimeoutError)
529 return None # success
530 d.addCallbacks(_suc, _err)
533 class DeferredUtilTests(unittest.TestCase):
534 def test_gather_results(self):
535 d1 = defer.Deferred()
536 d2 = defer.Deferred()
537 res = deferredutil.gatherResults([d1, d2])
538 d1.errback(ValueError("BAD"))
540 self.fail("Should have errbacked, not resulted in %s" % (res,))
542 thef.trap(ValueError)
543 res.addCallbacks(_callb, _errb)
546 def test_success(self):
547 d1, d2 = defer.Deferred(), defer.Deferred()
550 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
551 dlss.addCallbacks(good.append, bad.append)
554 self.failUnlessEqual(good, [[1,2]])
555 self.failUnlessEqual(bad, [])
557 def test_failure(self):
558 d1, d2 = defer.Deferred(), defer.Deferred()
561 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
562 dlss.addCallbacks(good.append, bad.append)
563 d1.addErrback(lambda _ignore: None)
564 d2.addErrback(lambda _ignore: None)
566 d2.errback(ValueError())
567 self.failUnlessEqual(good, [])
568 self.failUnlessEqual(len(bad), 1)
570 self.failUnless(isinstance(f, Failure))
571 self.failUnless(f.check(ValueError))
573 class HashUtilTests(unittest.TestCase):
575 def test_random_key(self):
576 k = hashutil.random_key()
577 self.failUnlessEqual(len(k), hashutil.KEYLEN)
579 def test_sha256d(self):
580 h1 = hashutil.tagged_hash("tag1", "value")
581 h2 = hashutil.tagged_hasher("tag1")
585 self.failUnlessEqual(h1, h2a)
586 self.failUnlessEqual(h2a, h2b)
588 def test_sha256d_truncated(self):
589 h1 = hashutil.tagged_hash("tag1", "value", 16)
590 h2 = hashutil.tagged_hasher("tag1", 16)
593 self.failUnlessEqual(len(h1), 16)
594 self.failUnlessEqual(len(h2), 16)
595 self.failUnlessEqual(h1, h2)
598 h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
599 h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
602 self.failUnlessEqual(h1, h2)
604 def test_hashers(self):
605 h1 = hashutil.block_hash("foo")
606 h2 = hashutil.block_hasher()
608 self.failUnlessEqual(h1, h2.digest())
610 h1 = hashutil.uri_extension_hash("foo")
611 h2 = hashutil.uri_extension_hasher()
613 self.failUnlessEqual(h1, h2.digest())
615 h1 = hashutil.plaintext_hash("foo")
616 h2 = hashutil.plaintext_hasher()
618 self.failUnlessEqual(h1, h2.digest())
620 h1 = hashutil.crypttext_hash("foo")
621 h2 = hashutil.crypttext_hasher()
623 self.failUnlessEqual(h1, h2.digest())
625 h1 = hashutil.crypttext_segment_hash("foo")
626 h2 = hashutil.crypttext_segment_hasher()
628 self.failUnlessEqual(h1, h2.digest())
630 h1 = hashutil.plaintext_segment_hash("foo")
631 h2 = hashutil.plaintext_segment_hasher()
633 self.failUnlessEqual(h1, h2.digest())
635 def test_constant_time_compare(self):
636 self.failUnless(hashutil.constant_time_compare("a", "a"))
637 self.failUnless(hashutil.constant_time_compare("ab", "ab"))
638 self.failIf(hashutil.constant_time_compare("a", "b"))
639 self.failIf(hashutil.constant_time_compare("a", "aa"))
641 def _testknown(self, hashf, expected_a, *args):
643 got_a = base32.b2a(got)
644 self.failUnlessEqual(got_a, expected_a)
646 def test_known_answers(self):
647 # assert backwards compatibility
648 self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
649 self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
650 self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
651 self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
652 self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
653 self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
654 self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
655 self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
656 self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
657 self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
658 self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
659 self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
660 self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
661 self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
662 self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
663 self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
664 self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
665 self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
666 self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
667 self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
668 self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
669 self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
670 self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
673 class Abbreviate(unittest.TestCase):
675 a = abbreviate.abbreviate_time
676 self.failUnlessEqual(a(None), "unknown")
677 self.failUnlessEqual(a(0), "0 seconds")
678 self.failUnlessEqual(a(1), "1 second")
679 self.failUnlessEqual(a(2), "2 seconds")
680 self.failUnlessEqual(a(119), "119 seconds")
682 self.failUnlessEqual(a(2*MIN), "2 minutes")
683 self.failUnlessEqual(a(60*MIN), "60 minutes")
684 self.failUnlessEqual(a(179*MIN), "179 minutes")
686 self.failUnlessEqual(a(180*MIN), "3 hours")
687 self.failUnlessEqual(a(4*HOUR), "4 hours")
690 self.failUnlessEqual(a(2*DAY), "2 days")
691 self.failUnlessEqual(a(2*MONTH), "2 months")
693 self.failUnlessEqual(a(5*YEAR), "5 years")
695 def test_space(self):
696 tests_si = [(None, "unknown"),
703 (20*1000, "20.00 kB"),
704 (1024*1024, "1.05 MB"),
705 (1000*1000, "1.00 MB"),
706 (1000*1000*1000, "1.00 GB"),
707 (1000*1000*1000*1000, "1.00 TB"),
708 (1000*1000*1000*1000*1000, "1.00 PB"),
709 (1234567890123456, "1.23 PB"),
711 for (x, expected) in tests_si:
712 got = abbreviate.abbreviate_space(x, SI=True)
713 self.failUnlessEqual(got, expected)
715 tests_base1024 = [(None, "unknown"),
722 (20*1024, "20.00 kiB"),
723 (1000*1000, "976.56 kiB"),
724 (1024*1024, "1.00 MiB"),
725 (1024*1024*1024, "1.00 GiB"),
726 (1024*1024*1024*1024, "1.00 TiB"),
727 (1000*1000*1000*1000*1000, "909.49 TiB"),
728 (1024*1024*1024*1024*1024, "1.00 PiB"),
729 (1234567890123456, "1.10 PiB"),
731 for (x, expected) in tests_base1024:
732 got = abbreviate.abbreviate_space(x, SI=False)
733 self.failUnlessEqual(got, expected)
735 self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
736 "(1.23 MB, 1.18 MiB)")
738 def test_parse_space(self):
739 p = abbreviate.parse_abbreviated_size
740 self.failUnlessEqual(p(""), None)
741 self.failUnlessEqual(p(None), None)
742 self.failUnlessEqual(p("123"), 123)
743 self.failUnlessEqual(p("123B"), 123)
744 self.failUnlessEqual(p("2K"), 2000)
745 self.failUnlessEqual(p("2kb"), 2000)
746 self.failUnlessEqual(p("2KiB"), 2048)
747 self.failUnlessEqual(p("10MB"), 10*1000*1000)
748 self.failUnlessEqual(p("10MiB"), 10*1024*1024)
749 self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
750 self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
751 e = self.failUnlessRaises(ValueError, p, "12 cubits")
752 self.failUnless("12 cubits" in str(e))
754 class Limiter(unittest.TestCase):
755 timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
757 def job(self, i, foo):
758 self.calls.append( (i, foo) )
759 self.simultaneous += 1
760 self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
763 self.simultaneous -= 1
764 d.callback("done %d" % i)
765 reactor.callLater(1.0, _done)
768 def bad_job(self, i, foo):
769 raise ValueError("bad_job %d" % i)
771 def test_limiter(self):
773 self.simultaneous = 0
774 self.peak_simultaneous = 0
775 l = limiter.ConcurrencyLimiter()
778 dl.append(l.add(self.job, i, foo=str(i)))
779 d = defer.DeferredList(dl, fireOnOneErrback=True)
781 self.failUnlessEqual(self.simultaneous, 0)
782 self.failUnless(self.peak_simultaneous <= 10)
783 self.failUnlessEqual(len(self.calls), 20)
785 self.failUnless( (i, str(i)) in self.calls)
789 def test_errors(self):
791 self.simultaneous = 0
792 self.peak_simultaneous = 0
793 l = limiter.ConcurrencyLimiter()
796 dl.append(l.add(self.job, i, foo=str(i)))
797 d2 = l.add(self.bad_job, 21, "21")
798 d = defer.DeferredList(dl, fireOnOneErrback=True)
801 for (success, result) in res:
802 self.failUnlessEqual(success, True)
803 results.append(result)
805 expected_results = ["done %d" % i for i in range(20)]
806 expected_results.sort()
807 self.failUnlessEqual(results, expected_results)
808 self.failUnless(self.peak_simultaneous <= 10)
809 self.failUnlessEqual(len(self.calls), 20)
811 self.failUnless( (i, str(i)) in self.calls)
813 self.fail("should have failed, not got %s" % (res,))
816 self.failUnless("bad_job 21" in str(f))
817 d2.addCallbacks(_good, _err)
819 d.addCallback(_most_done)
821 self.failUnlessEqual(self.simultaneous, 0)
822 self.failUnless(self.peak_simultaneous <= 10)
823 self.failUnlessEqual(len(self.calls), 20)
825 self.failUnless( (i, str(i)) in self.calls)
826 d.addCallback(_all_done)
829 class TimeFormat(unittest.TestCase):
830 def test_epoch(self):
831 return self._help_test_epoch()
833 def test_epoch_in_London(self):
834 # Europe/London is a particularly troublesome timezone. Nowadays, its
835 # offset from GMT is 0. But in 1970, its offset from GMT was 1.
836 # (Apparently in 1970 Britain had redefined standard time to be GMT+1
837 # and stayed in standard time all year round, whereas today
838 # Europe/London standard time is GMT and Europe/London Daylight
839 # Savings Time is GMT+1.) The current implementation of
840 # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
841 # Europe/London. (As soon as this unit test is done then I'll change
842 # that implementation to something that works even in this case...)
843 origtz = os.environ.get('TZ')
844 os.environ['TZ'] = "Europe/London"
845 if hasattr(time, 'tzset'):
848 return self._help_test_epoch()
853 os.environ['TZ'] = origtz
854 if hasattr(time, 'tzset'):
857 def _help_test_epoch(self):
858 origtzname = time.tzname
859 s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
860 self.failUnlessEqual(s, 1.0)
861 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
862 self.failUnlessEqual(s, 1.0)
863 s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
864 self.failUnlessEqual(s, 1.0)
866 self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
867 self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
868 "1970-01-01 00:00:01")
871 isostr = time_format.iso_utc(now)
872 timestamp = time_format.iso_utc_time_to_seconds(isostr)
873 self.failUnlessEqual(int(timestamp), int(now))
877 self.failUnlessEqual(time_format.iso_utc(t=my_time),
878 "1970-01-01_00:00:01")
879 e = self.failUnlessRaises(ValueError,
880 time_format.iso_utc_time_to_seconds,
881 "invalid timestring")
882 self.failUnless("not a complete ISO8601 timestamp" in str(e))
883 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
884 self.failUnlessEqual(s, 1.5)
886 # Look for daylight-savings-related errors.
887 thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
888 self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
889 self.failUnlessEqual(origtzname, time.tzname)
891 def test_iso_utc(self):
892 when = 1266760143.7841301
893 out = time_format.iso_utc_date(when)
894 self.failUnlessEqual(out, "2010-02-21")
895 out = time_format.iso_utc_date(t=lambda: when)
896 self.failUnlessEqual(out, "2010-02-21")
897 out = time_format.iso_utc(when)
898 self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
899 out = time_format.iso_utc(when, sep="-")
900 self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
902 def test_parse_duration(self):
903 p = time_format.parse_duration
905 self.failUnlessEqual(p("1 day"), DAY)
906 self.failUnlessEqual(p("2 days"), 2*DAY)
907 self.failUnlessEqual(p("3 months"), 3*31*DAY)
908 self.failUnlessEqual(p("4 mo"), 4*31*DAY)
909 self.failUnlessEqual(p("5 years"), 5*365*DAY)
910 e = self.failUnlessRaises(ValueError, p, "123")
911 self.failUnlessIn("no unit (like day, month, or year) in '123'",
914 def test_parse_date(self):
915 self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
917 class CacheDir(unittest.TestCase):
918 def test_basic(self):
919 basedir = "test_util/CacheDir/test_basic"
921 def _failIfExists(name):
922 absfn = os.path.join(basedir, name)
923 self.failIf(os.path.exists(absfn),
924 "%s exists but it shouldn't" % absfn)
926 def _failUnlessExists(name):
927 absfn = os.path.join(basedir, name)
928 self.failUnless(os.path.exists(absfn),
929 "%s doesn't exist but it should" % absfn)
931 cdm = cachedir.CacheDirectoryManager(basedir)
932 a = cdm.get_file("a")
933 b = cdm.get_file("b")
934 c = cdm.get_file("c")
935 f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
936 f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
937 f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
939 _failUnlessExists("a")
940 _failUnlessExists("b")
941 _failUnlessExists("c")
945 _failUnlessExists("a")
946 _failUnlessExists("b")
947 _failUnlessExists("c")
950 # this file won't be deleted yet, because it isn't old enough
952 _failUnlessExists("a")
953 _failUnlessExists("b")
954 _failUnlessExists("c")
956 # we change the definition of "old" to make everything old
961 _failUnlessExists("b")
962 _failUnlessExists("c")
970 _failUnlessExists("b")
971 _failUnlessExists("c")
973 b2 = cdm.get_file("b")
977 _failUnlessExists("b")
978 _failUnlessExists("c")
983 def __init__(self, x):
988 return "<%s %s>" % (self.__class__.__name__, self.x,)
991 def __le__(self, other):
992 return self.x <= other
993 def __lt__(self, other):
994 return self.x < other
995 def __ge__(self, other):
996 return self.x >= other
997 def __gt__(self, other):
998 return self.x > other
999 def __ne__(self, other):
1000 return self.x != other
1001 def __eq__(self, other):
1002 return self.x == other
1004 class DictUtil(unittest.TestCase):
1005 def _help_test_empty_dict(self, klass):
1009 self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1010 self.failUnless(len(d1) == 0)
1011 self.failUnless(len(d2) == 0)
1013 def _help_test_nonempty_dict(self, klass):
1014 d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1015 d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1017 self.failUnless(d1 == d2)
1018 self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1019 self.failUnless(len(d2) == 3)
1021 def _help_test_eq_but_notis(self, klass):
1022 d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1027 d['b'] = EqButNotIs(3)
1032 d['b'] = EqButNotIs(3)
1038 d['a'] = EqButNotIs(3)
1043 fake3 = EqButNotIs(3)
1044 fake7 = EqButNotIs(7)
1048 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1049 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1050 # The real 7 should have been ejected by the d[3] = 8.
1051 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1052 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1053 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1058 fake3 = EqButNotIs(3)
1059 fake7 = EqButNotIs(7)
1062 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1063 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1064 # The real 7 should have been ejected by the d[3] = 8.
1065 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1066 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1067 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1071 self._help_test_eq_but_notis(dictutil.UtilDict)
1072 self._help_test_eq_but_notis(dictutil.NumDict)
1073 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1074 self._help_test_nonempty_dict(dictutil.UtilDict)
1075 self._help_test_nonempty_dict(dictutil.NumDict)
1076 self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1077 self._help_test_eq_but_notis(dictutil.UtilDict)
1078 self._help_test_eq_but_notis(dictutil.NumDict)
1079 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1081 def test_dict_of_sets(self):
1082 ds = dictutil.DictOfSets()
1087 self.failUnlessEqual(ds[1], set(["a"]))
1088 self.failUnlessEqual(ds[2], set(["b", "c"]))
1089 ds.discard(3, "d") # should not raise an exception
1091 self.failUnlessEqual(ds[2], set(["c"]))
1093 self.failIf(2 in ds)
1095 ds.union(1, ["a", "e"])
1097 self.failUnlessEqual(ds[1], set(["a","e"]))
1098 self.failUnlessEqual(ds[3], set(["f"]))
1099 ds2 = dictutil.DictOfSets()
1104 self.failUnlessEqual(ds[1], set(["a","e"]))
1105 self.failUnlessEqual(ds[3], set(["f", "g"]))
1106 self.failUnlessEqual(ds[4], set(["h"]))
1108 def test_move(self):
1109 d1 = {1: "a", 2: "b"}
1110 d2 = {2: "c", 3: "d"}
1111 dictutil.move(1, d1, d2)
1112 self.failUnlessEqual(d1, {2: "b"})
1113 self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1115 d1 = {1: "a", 2: "b"}
1116 d2 = {2: "c", 3: "d"}
1117 dictutil.move(2, d1, d2)
1118 self.failUnlessEqual(d1, {1: "a"})
1119 self.failUnlessEqual(d2, {2: "b", 3: "d"})
1121 d1 = {1: "a", 2: "b"}
1122 d2 = {2: "c", 3: "d"}
1123 self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1125 def test_subtract(self):
1126 d1 = {1: "a", 2: "b"}
1127 d2 = {2: "c", 3: "d"}
1128 d3 = dictutil.subtract(d1, d2)
1129 self.failUnlessEqual(d3, {1: "a"})
1131 d1 = {1: "a", 2: "b"}
1133 d3 = dictutil.subtract(d1, d2)
1134 self.failUnlessEqual(d3, {1: "a"})
1136 def test_utildict(self):
1137 d = dictutil.UtilDict({1: "a", 2: "b"})
1140 self.failUnlessEqual(d, {2: "b"})
1143 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1145 d = dictutil.UtilDict({1: "b", 2: "a"})
1146 self.failUnlessEqual(d.items_sorted_by_value(),
1147 [(2, "a"), (1, "b")])
1148 self.failUnlessEqual(d.items_sorted_by_key(),
1149 [(1, "b"), (2, "a")])
1150 self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1151 self.failUnless(1 in d)
1153 d2 = dictutil.UtilDict({3: "c", 4: "d"})
1154 self.failUnless(d != d2)
1155 self.failUnless(d2 > d)
1156 self.failUnless(d2 >= d)
1157 self.failUnless(d <= d2)
1158 self.failUnless(d < d2)
1159 self.failUnlessEqual(d[1], "b")
1160 self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1163 self.failUnlessEqual(d, d3)
1164 self.failUnless(isinstance(d3, dictutil.UtilDict))
1166 d4 = d.fromkeys([3,4], "e")
1167 self.failUnlessEqual(d4, {3: "e", 4: "e"})
1169 self.failUnlessEqual(d.get(1), "b")
1170 self.failUnlessEqual(d.get(3), None)
1171 self.failUnlessEqual(d.get(3, "default"), "default")
1172 self.failUnlessEqual(sorted(list(d.items())),
1173 [(1, "b"), (2, "a")])
1174 self.failUnlessEqual(sorted(list(d.iteritems())),
1175 [(1, "b"), (2, "a")])
1176 self.failUnlessEqual(sorted(d.keys()), [1, 2])
1177 self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1178 x = d.setdefault(1, "new")
1179 self.failUnlessEqual(x, "b")
1180 self.failUnlessEqual(d[1], "b")
1181 x = d.setdefault(3, "new")
1182 self.failUnlessEqual(x, "new")
1183 self.failUnlessEqual(d[3], "new")
1187 self.failUnless(x in [(1, "b"), (2, "a")])
1189 self.failUnless(x in [(1, "b"), (2, "a")])
1190 self.failUnlessRaises(KeyError, d.popitem)
1192 def test_numdict(self):
1193 d = dictutil.NumDict({"a": 1, "b": 2})
1195 d.add_num("a", 10, 5)
1196 d.add_num("c", 20, 5)
1198 self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1200 d.subtract_num("a", 10)
1201 d.subtract_num("e", 10)
1202 d.subtract_num("f", 10, 15)
1203 self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1206 self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1208 d = dictutil.NumDict()
1212 self.failUnlessEqual(d, {"a": 2, "b": 6})
1216 self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1217 self.failUnlessEqual(d.items_sorted_by_key(),
1218 [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1219 self.failUnlessEqual(d.items_sorted_by_value(),
1220 [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1221 self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1223 d = dictutil.NumDict({"a": 1, "b": 2})
1224 self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1225 self.failUnless("a" in d)
1227 d2 = dictutil.NumDict({"c": 3, "d": 4})
1228 self.failUnless(d != d2)
1229 self.failUnless(d2 > d)
1230 self.failUnless(d2 >= d)
1231 self.failUnless(d <= d2)
1232 self.failUnless(d < d2)
1233 self.failUnlessEqual(d["a"], 1)
1234 self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1237 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1240 self.failUnlessEqual(d, d3)
1241 self.failUnless(isinstance(d3, dictutil.NumDict))
1243 d4 = d.fromkeys(["a","b"], 5)
1244 self.failUnlessEqual(d4, {"a": 5, "b": 5})
1246 self.failUnlessEqual(d.get("a"), 1)
1247 self.failUnlessEqual(d.get("c"), 0)
1248 self.failUnlessEqual(d.get("c", 5), 5)
1249 self.failUnlessEqual(sorted(list(d.items())),
1250 [("a", 1), ("b", 2)])
1251 self.failUnlessEqual(sorted(list(d.iteritems())),
1252 [("a", 1), ("b", 2)])
1253 self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1254 self.failUnlessEqual(sorted(d.values()), [1, 2])
1255 self.failUnless(d.has_key("a"))
1256 self.failIf(d.has_key("c"))
1258 x = d.setdefault("c", 3)
1259 self.failUnlessEqual(x, 3)
1260 self.failUnlessEqual(d["c"], 3)
1261 x = d.setdefault("c", 5)
1262 self.failUnlessEqual(x, 3)
1263 self.failUnlessEqual(d["c"], 3)
1267 self.failUnless(x in [("a", 1), ("b", 2)])
1269 self.failUnless(x in [("a", 1), ("b", 2)])
1270 self.failUnlessRaises(KeyError, d.popitem)
1273 d.update({"c": 4, "d": 5})
1274 self.failUnlessEqual(d, {"c": 4, "d": 5})
1276 def test_del_if_present(self):
1277 d = {1: "a", 2: "b"}
1278 dictutil.del_if_present(d, 1)
1279 dictutil.del_if_present(d, 3)
1280 self.failUnlessEqual(d, {2: "b"})
1282 def test_valueordereddict(self):
1283 d = dictutil.ValueOrderedDict()
1288 self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1289 self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1290 self.failUnlessEqual(d.values(), [1, 2, 3])
1291 self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1292 self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1295 self.failIf(d == {"a": 4})
1296 self.failUnless(d != {"a": 4})
1298 x = d.setdefault("d", 0)
1299 self.failUnlessEqual(x, 0)
1300 self.failUnlessEqual(d["d"], 0)
1301 x = d.setdefault("d", -1)
1302 self.failUnlessEqual(x, 0)
1303 self.failUnlessEqual(d["d"], 0)
1305 x = d.remove("e", "default", False)
1306 self.failUnlessEqual(x, "default")
1307 self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1308 x = d.remove("d", 5)
1309 self.failUnlessEqual(x, 0)
1311 x = d.__getitem__("c")
1312 self.failUnlessEqual(x, 1)
1313 x = d.__getitem__("e", "default", False)
1314 self.failUnlessEqual(x, "default")
1315 self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1317 self.failUnlessEqual(d.popitem(), ("c", 1))
1318 self.failUnlessEqual(d.popitem(), ("b", 2))
1319 self.failUnlessEqual(d.popitem(), ("a", 3))
1320 self.failUnlessRaises(KeyError, d.popitem)
1322 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1323 x = d.pop("d", "default", False)
1324 self.failUnlessEqual(x, "default")
1325 self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1327 self.failUnlessEqual(x, 2)
1328 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1330 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1331 x = d.pop_from_list(1) # pop the second item, b/2
1332 self.failUnlessEqual(x, "b")
1333 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1335 def test_auxdict(self):
1336 d = dictutil.AuxValueDict()
1337 # we put the serialized form in the auxdata
1338 d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1340 self.failUnlessEqual(d.keys(), ["key"])
1341 self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1342 self.failUnlessEqual(d.get_aux("key"), "serialized")
1343 def _get_missing(key):
1345 self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1346 self.failUnlessEqual(d.get("nonkey"), None)
1347 self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1348 self.failUnlessEqual(d.get_aux("nonkey"), None)
1349 self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1351 d["key"] = ("filecap2", "metadata2")
1352 self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1353 self.failUnlessEqual(d.get_aux("key"), None)
1355 d.set_with_aux("key2", "value2", "aux2")
1356 self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1358 self.failUnlessEqual(d.keys(), ["key"])
1359 self.failIf("key2" in d)
1360 self.failUnlessRaises(KeyError, _get_missing, "key2")
1361 self.failUnlessEqual(d.get("key2"), None)
1362 self.failUnlessEqual(d.get_aux("key2"), None)
1363 d["key2"] = "newvalue2"
1364 self.failUnlessEqual(d.get("key2"), "newvalue2")
1365 self.failUnlessEqual(d.get_aux("key2"), None)
1367 d = dictutil.AuxValueDict({1:2,3:4})
1368 self.failUnlessEqual(sorted(d.keys()), [1,3])
1369 self.failUnlessEqual(d[1], 2)
1370 self.failUnlessEqual(d.get_aux(1), None)
1372 d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1373 self.failUnlessEqual(sorted(d.keys()), [1,3])
1374 self.failUnlessEqual(d[1], 2)
1375 self.failUnlessEqual(d.get_aux(1), None)
1377 d = dictutil.AuxValueDict(one=1, two=2)
1378 self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1379 self.failUnlessEqual(d["one"], 1)
1380 self.failUnlessEqual(d.get_aux("one"), None)
1382 class Pipeline(unittest.TestCase):
1383 def pause(self, *args, **kwargs):
1384 d = defer.Deferred()
1385 self.calls.append( (d, args, kwargs) )
1388 def failUnlessCallsAre(self, expected):
1391 self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1392 for i,c in enumerate(self.calls):
1393 self.failUnlessEqual(c[1:], expected[i], str(i))
1395 def test_basic(self):
1398 p = pipeline.Pipeline(100)
1400 d = p.flush() # fires immediately
1401 d.addCallbacks(finished.append, log.err)
1402 self.failUnlessEqual(len(finished), 1)
1405 d = p.add(10, self.pause, "one")
1406 # the call should start right away, and our return Deferred should
1408 d.addCallbacks(finished.append, log.err)
1409 self.failUnlessEqual(len(finished), 1)
1410 self.failUnlessEqual(finished[0], None)
1411 self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1412 self.failUnlessEqual(p.gauge, 10)
1417 d = p.add(20, self.pause, "two", kw=2)
1418 # pipeline: [one, two]
1420 # the call and the Deferred should fire right away
1421 d.addCallbacks(finished.append, log.err)
1422 self.failUnlessEqual(len(finished), 1)
1423 self.failUnlessEqual(finished[0], None)
1424 self.failUnlessCallsAre([ ( ("one",) , {} ),
1425 ( ("two",) , {"kw": 2} ),
1427 self.failUnlessEqual(p.gauge, 30)
1429 self.calls[0][0].callback("one-result")
1431 self.failUnlessEqual(p.gauge, 20)
1434 d = p.add(90, self.pause, "three", "posarg1")
1435 # pipeline: [two, three]
1438 fd.addCallbacks(flushed.append, log.err)
1439 self.failUnlessEqual(flushed, [])
1441 # the call will be made right away, but the return Deferred will not,
1442 # because the pipeline is now full.
1443 d.addCallbacks(finished.append, log.err)
1444 self.failUnlessEqual(len(finished), 0)
1445 self.failUnlessCallsAre([ ( ("one",) , {} ),
1446 ( ("two",) , {"kw": 2} ),
1447 ( ("three", "posarg1"), {} ),
1449 self.failUnlessEqual(p.gauge, 110)
1451 self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1453 # retiring either call will unblock the pipeline, causing the #3
1455 self.calls[2][0].callback("three-result")
1458 self.failUnlessEqual(len(finished), 1)
1459 self.failUnlessEqual(finished[0], None)
1460 self.failUnlessEqual(flushed, [])
1462 # retiring call#2 will finally allow the flush() Deferred to fire
1463 self.calls[1][0].callback("two-result")
1464 self.failUnlessEqual(len(flushed), 1)
1466 def test_errors(self):
1468 p = pipeline.Pipeline(100)
1470 d1 = p.add(200, self.pause, "one")
1474 d1.addBoth(finished.append)
1475 self.failUnlessEqual(finished, [])
1478 d2.addBoth(flushed.append)
1479 self.failUnlessEqual(flushed, [])
1481 self.calls[0][0].errback(ValueError("oops"))
1483 self.failUnlessEqual(len(finished), 1)
1485 self.failUnless(isinstance(f, Failure))
1486 self.failUnless(f.check(pipeline.PipelineError))
1487 self.failUnlessIn("PipelineError", str(f.value))
1488 self.failUnlessIn("ValueError", str(f.value))
1490 self.failUnless("ValueError" in r, r)
1492 self.failUnless(f2.check(ValueError))
1494 self.failUnlessEqual(len(flushed), 1)
1496 self.failUnless(isinstance(f, Failure))
1497 self.failUnless(f.check(pipeline.PipelineError))
1499 self.failUnless(f2.check(ValueError))
1501 # now that the pipeline is in the failed state, any new calls will
1504 d3 = p.add(20, self.pause, "two")
1507 d3.addBoth(finished.append)
1508 self.failUnlessEqual(len(finished), 1)
1510 self.failUnless(isinstance(f, Failure))
1511 self.failUnless(f.check(pipeline.PipelineError))
1513 self.failUnless("ValueError" in r, r)
1515 self.failUnless(f2.check(ValueError))
1519 d4.addBoth(flushed.append)
1520 self.failUnlessEqual(len(flushed), 1)
1522 self.failUnless(isinstance(f, Failure))
1523 self.failUnless(f.check(pipeline.PipelineError))
1525 self.failUnless(f2.check(ValueError))
1527 def test_errors2(self):
1529 p = pipeline.Pipeline(100)
1531 d1 = p.add(10, self.pause, "one")
1532 d2 = p.add(20, self.pause, "two")
1533 d3 = p.add(30, self.pause, "three")
1536 # one call fails, then the second one succeeds: make sure
1537 # ExpandableDeferredList tolerates the second one
1540 d4.addBoth(flushed.append)
1541 self.failUnlessEqual(flushed, [])
1543 self.calls[0][0].errback(ValueError("oops"))
1544 self.failUnlessEqual(len(flushed), 1)
1546 self.failUnless(isinstance(f, Failure))
1547 self.failUnless(f.check(pipeline.PipelineError))
1549 self.failUnless(f2.check(ValueError))
1551 self.calls[1][0].callback("two-result")
1552 self.calls[2][0].errback(ValueError("three-error"))
1556 class SampleError(Exception):
1559 class Log(unittest.TestCase):
1561 if not hasattr(self, "flushLoggedErrors"):
1562 # without flushLoggedErrors, we can't get rid of the
1563 # twisted.log.err that tahoe_log records, so we can't keep this
1564 # test from [ERROR]ing
1565 raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1567 raise SampleError("simple sample")
1570 tahoe_log.err(format="intentional sample error",
1571 failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1572 self.flushLoggedErrors(SampleError)
1576 # this is a simple+inefficient form of util.spans.Spans . We compare the
1577 # behavior of this reference model against the real (efficient) form.
1579 def __init__(self, _span_or_start=None, length=None):
1581 if length is not None:
1582 for i in range(_span_or_start, _span_or_start+length):
1584 elif _span_or_start:
1585 for (start,length) in _span_or_start:
1586 self.add(start, length)
1588 def add(self, start, length):
1589 for i in range(start, start+length):
1593 def remove(self, start, length):
1594 for i in range(start, start+length):
1595 self._have.discard(i)
1599 return sorted(self._have)
1602 items = sorted(self._have)
1606 if prevstart is None:
1607 prevstart = prevend = i
1612 yield (prevstart, prevend-prevstart+1)
1613 prevstart = prevend = i
1614 if prevstart is not None:
1615 yield (prevstart, prevend-prevstart+1)
1618 # this also gets us bool(s)
1619 return len(self._have)
1621 def __add__(self, other):
1622 s = self.__class__(self)
1623 for (start, length) in other:
1624 s.add(start, length)
1627 def __sub__(self, other):
1628 s = self.__class__(self)
1629 for (start, length) in other:
1630 s.remove(start, length)
1633 def __iadd__(self, other):
1634 for (start, length) in other:
1635 self.add(start, length)
1638 def __isub__(self, other):
1639 for (start, length) in other:
1640 self.remove(start, length)
1643 def __and__(self, other):
1644 s = self.__class__()
1645 for i in other.each():
1650 def __contains__(self, (start,length)):
1651 for i in range(start, start+length):
1652 if i not in self._have:
1656 class ByteSpans(unittest.TestCase):
1657 def test_basic(self):
1659 self.failUnlessEqual(list(s), [])
1661 self.failIf((0,1) in s)
1662 self.failUnlessEqual(len(s), 0)
1664 s1 = Spans(3, 4) # 3,4,5,6
1670 s2.add(10,2) # 10,11
1672 self.failUnless((10,1) in s2)
1673 self.failIf((10,1) in s1)
1674 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1675 self.failUnlessEqual(len(s2), 6)
1677 s2.add(15,2).add(20,2)
1678 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1679 self.failUnlessEqual(len(s2), 10)
1681 s2.remove(4,3).remove(15,1)
1682 self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1683 self.failUnlessEqual(len(s2), 6)
1685 s1 = SimpleSpans(3, 4) # 3 4 5 6
1686 s2 = SimpleSpans(5, 4) # 5 6 7 8
1688 self.failUnlessEqual(list(i.each()), [5, 6])
1690 def _check1(self, s):
1691 self.failUnlessEqual(list(s), [(3,4)])
1693 self.failUnlessEqual(len(s), 4)
1694 self.failIf((0,1) in s)
1695 self.failUnless((3,4) in s)
1696 self.failUnless((3,1) in s)
1697 self.failUnless((5,2) in s)
1698 self.failUnless((6,1) in s)
1699 self.failIf((6,2) in s)
1700 self.failIf((7,1) in s)
1701 self.failUnlessEqual(list(s.each()), [3,4,5,6])
1703 def test_math(self):
1704 s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1705 s2 = Spans(5, 3) # 5,6,7
1706 s3 = Spans(8, 4) # 8,9,10,11
1709 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1711 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1713 self.failUnlessEqual(list(s.each()), [5,6,7])
1715 self.failUnlessEqual(list(s.each()), [5,6,7])
1717 self.failUnlessEqual(list(s.each()), [5,6,7])
1719 self.failUnlessEqual(list(s.each()), [8,9])
1721 self.failUnlessEqual(list(s.each()), [8,9])
1723 self.failUnlessEqual(list(s.each()), [])
1725 self.failUnlessEqual(list(s.each()), [])
1727 self.failUnlessEqual(list(s.each()), [])
1729 self.failUnlessEqual(list(s.each()), [])
1732 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1734 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1736 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1740 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1743 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1746 self.failUnlessEqual(list(s.each()), [5,6,7])
1750 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1753 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1756 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1758 def test_random(self):
1759 # attempt to increase coverage of corner cases by comparing behavior
1760 # of a simple-but-slow model implementation against the
1761 # complex-but-fast actual implementation, in a large number of random
1765 s1 = S1(); s2 = S2()
1767 def _create(subseed):
1768 ns1 = S1(); ns2 = S2()
1770 what = md5(subseed+str(i)).hexdigest()
1771 start = int(what[2:4], 16)
1772 length = max(1,int(what[5:6], 16))
1773 ns1.add(start, length); ns2.add(start, length)
1777 for i in range(1000):
1778 what = md5(seed+str(i)).hexdigest()
1781 start = int(what[2:4], 16)
1782 length = max(1,int(what[5:6], 16))
1785 if subop in "01234":
1786 s1 = S1(); s2 = S2()
1787 elif subop in "5678":
1788 s1 = S1(start, length); s2 = S2(start, length)
1790 s1 = S1(s1); s2 = S2(s2)
1791 #print "s2 = %s" % s2.dump()
1793 #print "s2.add(%d,%d)" % (start, length)
1794 s1.add(start, length); s2.add(start, length)
1796 #print "s2.remove(%d,%d)" % (start, length)
1797 s1.remove(start, length); s2.remove(start, length)
1799 ns1, ns2 = _create(what[7:11])
1800 #print "s2 + %s" % ns2.dump()
1801 s1 = s1 + ns1; s2 = s2 + ns2
1803 ns1, ns2 = _create(what[7:11])
1804 #print "%s - %s" % (s2.dump(), ns2.dump())
1805 s1 = s1 - ns1; s2 = s2 - ns2
1807 ns1, ns2 = _create(what[7:11])
1808 #print "s2 += %s" % ns2.dump()
1809 s1 += ns1; s2 += ns2
1811 ns1, ns2 = _create(what[7:11])
1812 #print "%s -= %s" % (s2.dump(), ns2.dump())
1813 s1 -= ns1; s2 -= ns2
1815 ns1, ns2 = _create(what[7:11])
1816 #print "%s &= %s" % (s2.dump(), ns2.dump())
1817 s1 = s1 & ns1; s2 = s2 & ns2
1818 #print "s2 now %s" % s2.dump()
1819 self.failUnlessEqual(list(s1.each()), list(s2.each()))
1820 self.failUnlessEqual(len(s1), len(s2))
1821 self.failUnlessEqual(bool(s1), bool(s2))
1822 self.failUnlessEqual(list(s1), list(s2))
1824 what = md5(what[12:14]+str(j)).hexdigest()
1825 start = int(what[2:4], 16)
1826 length = max(1, int(what[5:6], 16))
1827 span = (start, length)
1828 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1834 # s.add(start,length) : returns s
1835 # s.remove(start,length)
1836 # s.each() -> list of byte offsets, mostly for testing
1837 # list(s) -> list of (start,length) tuples, one per span
1838 # (start,length) in s -> True if (start..start+length-1) are all members
1839 # NOT equivalent to x in list(s)
1840 # len(s) -> number of bytes, for testing, bool(), and accounting/limiting
1842 # s = s1+s2, s1-s2, +=s1, -=s1
1844 def test_overlap(self):
1849 self._test_overlap(a,b,c,d)
1851 def _test_overlap(self, a, b, c, d):
1852 s1 = set(range(a,a+b))
1853 s2 = set(range(c,c+d))
1855 #self._show_overlap(s1, "1")
1856 #self._show_overlap(s2, "2")
1857 o = overlap(a,b,c,d)
1858 expected = s1.intersection(s2)
1860 self.failUnlessEqual(o, None)
1863 so = set(range(start,start+length))
1864 #self._show(so, "o")
1865 self.failUnlessEqual(so, expected)
1867 def _show_overlap(self, s, c):
1871 for i in range(max(s)):
1878 def extend(s, start, length, fill):
1879 if len(s) >= start+length:
1881 assert len(fill) == 1
1882 return s + fill*(start+length-len(s))
1884 def replace(s, start, data):
1885 assert len(s) >= start+len(data)
1886 return s[:start] + data + s[start+len(data):]
1888 class SimpleDataSpans:
1889 def __init__(self, other=None):
1890 self.missing = "" # "1" where missing, "0" where found
1893 for (start, data) in other.get_chunks():
1894 self.add(start, data)
1897 return len(self.missing.translate(None, "1"))
1899 return [i for (i,c) in enumerate(self.missing) if c == "0"]
1900 def _have(self, start, length):
1901 m = self.missing[start:start+length]
1902 if not m or len(m)<length or int(m):
1905 def get_chunks(self):
1906 for i in self._dump():
1907 yield (i, self.data[i])
1908 def get_spans(self):
1909 return SimpleSpans([(start,len(data))
1910 for (start,data) in self.get_chunks()])
1911 def get(self, start, length):
1912 if self._have(start, length):
1913 return self.data[start:start+length]
1915 def pop(self, start, length):
1916 data = self.get(start, length)
1918 self.remove(start, length)
1920 def remove(self, start, length):
1921 self.missing = replace(extend(self.missing, start, length, "1"),
1923 def add(self, start, data):
1924 self.missing = replace(extend(self.missing, start, len(data), "1"),
1925 start, "0"*len(data))
1926 self.data = replace(extend(self.data, start, len(data), " "),
1930 class StringSpans(unittest.TestCase):
1931 def do_basic(self, klass):
1933 self.failUnlessEqual(len(ds), 0)
1934 self.failUnlessEqual(list(ds._dump()), [])
1935 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
1937 self.failUnlessEqual(ds.get(0, 4), None)
1938 self.failUnlessEqual(ds.pop(0, 4), None)
1942 self.failUnlessEqual(len(ds), 4)
1943 self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
1944 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
1946 self.failUnless((2,2) in s)
1947 self.failUnlessEqual(ds.get(0, 4), None)
1948 self.failUnlessEqual(ds.pop(0, 4), None)
1949 self.failUnlessEqual(ds.get(4, 4), None)
1952 self.failUnlessEqual(len(ds2), 4)
1953 self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
1954 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
1955 self.failUnlessEqual(ds2.get(0, 4), None)
1956 self.failUnlessEqual(ds2.pop(0, 4), None)
1957 self.failUnlessEqual(ds2.pop(2, 3), "fou")
1958 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
1959 self.failUnlessEqual(ds2.get(2, 3), None)
1960 self.failUnlessEqual(ds2.get(5, 1), "r")
1961 self.failUnlessEqual(ds.get(2, 3), "fou")
1962 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
1965 self.failUnlessEqual(len(ds), 6)
1966 self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
1967 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
1968 self.failUnlessEqual(ds.get(0, 4), "23fo")
1969 self.failUnlessEqual(ds.pop(0, 4), "23fo")
1970 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
1971 self.failUnlessEqual(ds.get(0, 4), None)
1972 self.failUnlessEqual(ds.pop(0, 4), None)
1977 self.failUnlessEqual(ds.get(2, 4), "fear")
1979 def do_scan(self, klass):
1980 # do a test with gaps and spans of size 1 and 2
1981 # left=(1,11) * right=(1,11) * gapsize=(1,2)
1982 # 111, 112, 121, 122, 211, 212, 221, 222
1991 # 11 1 1 11 11 11 1 1 111
1992 # 0123456789012345678901234567
1993 # abcdefghijklmnopqrstuvwxyz-=
1994 pieces = [(1, "bc"),
2004 p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2005 S = "abcdefghijklmnopqrstuvwxyz-="
2006 # TODO: when adding data, add capital letters, to make sure we aren't
2007 # just leaving the old data in place
2011 for start, data in pieces:
2016 # wow, this is the first time I've ever wanted ?: in python
2017 # note: this requires python2.5
2018 d = "".join([(S[i] if i in p else " ") for i in range(l)])
2022 for start in range(0, l):
2023 for end in range(start+1, l):
2024 # add [start-end) to the baseline
2025 which = "%d-%d" % (start, end-1)
2026 p_added = set(range(start, end))
2030 print dump(b), which
2031 add = klass(); add.add(start, S[start:end])
2033 b.add(start, S[start:end])
2036 # check that the new span is there
2037 d = b.get(start, end-start)
2038 self.failUnlessEqual(d, S[start:end], which)
2039 # check that all the original pieces are still there
2040 for t_start, t_data in pieces:
2042 self.failUnlessEqual(b.get(t_start, t_len),
2043 S[t_start:t_start+t_len],
2044 "%s %d+%d" % (which, t_start, t_len))
2045 # check that a lot of subspans are mostly correct
2046 for t_start in range(l):
2047 for t_len in range(1,4):
2048 d = b.get(t_start, t_len)
2050 which2 = "%s+(%d-%d)" % (which, t_start,
2052 self.failUnlessEqual(d, S[t_start:t_start+t_len],
2054 # check that removing a subspan gives the right value
2056 b2.remove(t_start, t_len)
2057 removed = set(range(t_start, t_start+t_len))
2059 exp = (((i in p_elements) or (i in p_added))
2060 and (i not in removed))
2061 which2 = "%s-(%d-%d)" % (which, t_start,
2063 self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2066 def test_test(self):
2067 self.do_basic(SimpleDataSpans)
2068 self.do_scan(SimpleDataSpans)
2070 def test_basic(self):
2071 self.do_basic(DataSpans)
2072 self.do_scan(DataSpans)
2074 def test_random(self):
2075 # attempt to increase coverage of corner cases by comparing behavior
2076 # of a simple-but-slow model implementation against the
2077 # complex-but-fast actual implementation, in a large number of random
2079 S1 = SimpleDataSpans
2081 s1 = S1(); s2 = S2()
2083 def _randstr(length, seed):
2086 while created < length:
2087 piece = md5(seed + str(created)).hexdigest()
2088 pieces.append(piece)
2089 created += len(piece)
2090 return "".join(pieces)[:length]
2091 def _create(subseed):
2092 ns1 = S1(); ns2 = S2()
2094 what = md5(subseed+str(i)).hexdigest()
2095 start = int(what[2:4], 16)
2096 length = max(1,int(what[5:6], 16))
2097 ns1.add(start, _randstr(length, what[7:9]));
2098 ns2.add(start, _randstr(length, what[7:9]))
2102 for i in range(1000):
2103 what = md5(seed+str(i)).hexdigest()
2106 start = int(what[2:4], 16)
2107 length = max(1,int(what[5:6], 16))
2110 if subop in "0123456":
2111 s1 = S1(); s2 = S2()
2113 s1, s2 = _create(what[7:11])
2114 #print "s2 = %s" % list(s2._dump())
2115 elif op in "123456":
2116 #print "s2.add(%d,%d)" % (start, length)
2117 s1.add(start, _randstr(length, what[7:9]));
2118 s2.add(start, _randstr(length, what[7:9]))
2119 elif op in "789abc":
2120 #print "s2.remove(%d,%d)" % (start, length)
2121 s1.remove(start, length); s2.remove(start, length)
2123 #print "s2.pop(%d,%d)" % (start, length)
2124 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2125 self.failUnlessEqual(d1, d2)
2126 #print "s1 now %s" % list(s1._dump())
2127 #print "s2 now %s" % list(s2._dump())
2128 self.failUnlessEqual(len(s1), len(s2))
2129 self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2130 for j in range(100):
2131 what = md5(what[12:14]+str(j)).hexdigest()
2132 start = int(what[2:4], 16)
2133 length = max(1, int(what[5:6], 16))
2134 d1 = s1.get(start, length); d2 = s2.get(start, length)
2135 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))