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 pycryptopp.hash.sha256 import SHA256 as _hash
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
18 from allmydata.test.common_util import ReallyEqualMixin
21 class Base32(unittest.TestCase):
22 def test_b2a_matches_Pythons(self):
24 y = "\x12\x34\x45\x67\x89\x0a\xbc\xde\xf0"
25 x = base64.b32encode(y)
26 while x and x[-1] == '=':
29 self.failUnlessEqual(base32.b2a(y), x)
31 self.failUnlessEqual(base32.b2a("\x12\x34"), "ci2a")
32 def test_b2a_or_none(self):
33 self.failUnlessEqual(base32.b2a_or_none(None), None)
34 self.failUnlessEqual(base32.b2a_or_none("\x12\x34"), "ci2a")
36 self.failUnlessEqual(base32.a2b("ci2a"), "\x12\x34")
37 self.failUnlessRaises(AssertionError, base32.a2b, "b0gus")
39 class IDLib(unittest.TestCase):
40 def test_nodeid_b2a(self):
41 self.failUnlessEqual(idlib.nodeid_b2a("\x00"*20), "a"*32)
43 class NoArgumentException(Exception):
47 class HumanReadable(unittest.TestCase):
50 self.failUnlessEqual(hr(foo), "<foo() at test_util.py:2>")
51 self.failUnlessEqual(hr(self.test_repr),
52 "<bound method HumanReadable.test_repr of <allmydata.test.test_util.HumanReadable testMethod=test_repr>>")
53 self.failUnlessEqual(hr(1L), "1")
54 self.failUnlessEqual(hr(10**40),
55 "100000000000000000...000000000000000000")
56 self.failUnlessEqual(hr(self), "<allmydata.test.test_util.HumanReadable testMethod=test_repr>")
57 self.failUnlessEqual(hr([1,2]), "[1, 2]")
58 self.failUnlessEqual(hr({1:2}), "{1:2}")
63 hr(e) == "<ValueError: ()>" # python-2.4
64 or hr(e) == "ValueError()") # python-2.5
66 raise ValueError("oops")
69 hr(e) == "<ValueError: 'oops'>" # python-2.4
70 or hr(e) == "ValueError('oops',)") # python-2.5
72 raise NoArgumentException
75 hr(e) == "<NoArgumentException>" # python-2.4
76 or hr(e) == "NoArgumentException()") # python-2.5
82 class Math(unittest.TestCase):
83 def test_div_ceil(self):
85 self.failUnlessEqual(f(0, 1), 0)
86 self.failUnlessEqual(f(0, 2), 0)
87 self.failUnlessEqual(f(0, 3), 0)
88 self.failUnlessEqual(f(1, 3), 1)
89 self.failUnlessEqual(f(2, 3), 1)
90 self.failUnlessEqual(f(3, 3), 1)
91 self.failUnlessEqual(f(4, 3), 2)
92 self.failUnlessEqual(f(5, 3), 2)
93 self.failUnlessEqual(f(6, 3), 2)
94 self.failUnlessEqual(f(7, 3), 3)
96 def test_next_multiple(self):
97 f = mathutil.next_multiple
98 self.failUnlessEqual(f(5, 1), 5)
99 self.failUnlessEqual(f(5, 2), 6)
100 self.failUnlessEqual(f(5, 3), 6)
101 self.failUnlessEqual(f(5, 4), 8)
102 self.failUnlessEqual(f(5, 5), 5)
103 self.failUnlessEqual(f(5, 6), 6)
104 self.failUnlessEqual(f(32, 1), 32)
105 self.failUnlessEqual(f(32, 2), 32)
106 self.failUnlessEqual(f(32, 3), 33)
107 self.failUnlessEqual(f(32, 4), 32)
108 self.failUnlessEqual(f(32, 5), 35)
109 self.failUnlessEqual(f(32, 6), 36)
110 self.failUnlessEqual(f(32, 7), 35)
111 self.failUnlessEqual(f(32, 8), 32)
112 self.failUnlessEqual(f(32, 9), 36)
113 self.failUnlessEqual(f(32, 10), 40)
114 self.failUnlessEqual(f(32, 11), 33)
115 self.failUnlessEqual(f(32, 12), 36)
116 self.failUnlessEqual(f(32, 13), 39)
117 self.failUnlessEqual(f(32, 14), 42)
118 self.failUnlessEqual(f(32, 15), 45)
119 self.failUnlessEqual(f(32, 16), 32)
120 self.failUnlessEqual(f(32, 17), 34)
121 self.failUnlessEqual(f(32, 18), 36)
122 self.failUnlessEqual(f(32, 589), 589)
124 def test_pad_size(self):
125 f = mathutil.pad_size
126 self.failUnlessEqual(f(0, 4), 0)
127 self.failUnlessEqual(f(1, 4), 3)
128 self.failUnlessEqual(f(2, 4), 2)
129 self.failUnlessEqual(f(3, 4), 1)
130 self.failUnlessEqual(f(4, 4), 0)
131 self.failUnlessEqual(f(5, 4), 3)
133 def test_is_power_of_k(self):
134 f = mathutil.is_power_of_k
135 for i in range(1, 100):
136 if i in (1, 2, 4, 8, 16, 32, 64):
137 self.failUnless(f(i, 2), "but %d *is* a power of 2" % i)
139 self.failIf(f(i, 2), "but %d is *not* a power of 2" % i)
140 for i in range(1, 100):
141 if i in (1, 3, 9, 27, 81):
142 self.failUnless(f(i, 3), "but %d *is* a power of 3" % i)
144 self.failIf(f(i, 3), "but %d is *not* a power of 3" % i)
146 def test_next_power_of_k(self):
147 f = mathutil.next_power_of_k
148 self.failUnlessEqual(f(0,2), 1)
149 self.failUnlessEqual(f(1,2), 1)
150 self.failUnlessEqual(f(2,2), 2)
151 self.failUnlessEqual(f(3,2), 4)
152 self.failUnlessEqual(f(4,2), 4)
153 for i in range(5, 8): self.failUnlessEqual(f(i,2), 8, "%d" % i)
154 for i in range(9, 16): self.failUnlessEqual(f(i,2), 16, "%d" % i)
155 for i in range(17, 32): self.failUnlessEqual(f(i,2), 32, "%d" % i)
156 for i in range(33, 64): self.failUnlessEqual(f(i,2), 64, "%d" % i)
157 for i in range(65, 100): self.failUnlessEqual(f(i,2), 128, "%d" % i)
159 self.failUnlessEqual(f(0,3), 1)
160 self.failUnlessEqual(f(1,3), 1)
161 self.failUnlessEqual(f(2,3), 3)
162 self.failUnlessEqual(f(3,3), 3)
163 for i in range(4, 9): self.failUnlessEqual(f(i,3), 9, "%d" % i)
164 for i in range(10, 27): self.failUnlessEqual(f(i,3), 27, "%d" % i)
165 for i in range(28, 81): self.failUnlessEqual(f(i,3), 81, "%d" % i)
166 for i in range(82, 200): self.failUnlessEqual(f(i,3), 243, "%d" % i)
170 self.failUnlessEqual(f([1,2,3]), 2)
171 self.failUnlessEqual(f([0,0,0,4]), 1)
172 self.failUnlessAlmostEqual(f([0.0, 1.0, 1.0]), .666666666666)
174 def test_round_sigfigs(self):
175 f = mathutil.round_sigfigs
176 self.failUnlessEqual(f(22.0/3, 4), 7.3330000000000002)
178 class Statistics(unittest.TestCase):
179 def should_assert(self, msg, func, *args, **kwargs):
181 func(*args, **kwargs)
183 except AssertionError:
186 def failUnlessListEqual(self, a, b, msg = None):
187 self.failUnlessEqual(len(a), len(b))
188 for i in range(len(a)):
189 self.failUnlessEqual(a[i], b[i], msg)
191 def failUnlessListAlmostEqual(self, a, b, places = 7, msg = None):
192 self.failUnlessEqual(len(a), len(b))
193 for i in range(len(a)):
194 self.failUnlessAlmostEqual(a[i], b[i], places, msg)
196 def test_binomial_coeff(self):
197 f = statistics.binomial_coeff
198 self.failUnlessEqual(f(20, 0), 1)
199 self.failUnlessEqual(f(20, 1), 20)
200 self.failUnlessEqual(f(20, 2), 190)
201 self.failUnlessEqual(f(20, 8), f(20, 12))
202 self.should_assert("Should assert if n < k", f, 2, 3)
204 def test_binomial_distribution_pmf(self):
205 f = statistics.binomial_distribution_pmf
208 pmf_stat = [0.81, 0.18, 0.01]
209 self.failUnlessListAlmostEqual(pmf_comp, pmf_stat)
211 # Summing across a PMF should give the total probability 1
212 self.failUnlessAlmostEqual(sum(pmf_comp), 1)
213 self.should_assert("Should assert if not 0<=p<=1", f, 1, -1)
214 self.should_assert("Should assert if n < 1", f, 0, .1)
217 statistics.print_pmf(pmf_comp, out=out)
218 lines = out.getvalue().splitlines()
219 self.failUnlessEqual(lines[0], "i=0: 0.81")
220 self.failUnlessEqual(lines[1], "i=1: 0.18")
221 self.failUnlessEqual(lines[2], "i=2: 0.01")
223 def test_survival_pmf(self):
224 f = statistics.survival_pmf
225 # Cross-check binomial-distribution method against convolution
227 p_list = [.9999] * 100 + [.99] * 50 + [.8] * 20
228 pmf1 = statistics.survival_pmf_via_conv(p_list)
229 pmf2 = statistics.survival_pmf_via_bd(p_list)
230 self.failUnlessListAlmostEqual(pmf1, pmf2)
231 self.failUnlessTrue(statistics.valid_pmf(pmf1))
232 self.should_assert("Should assert if p_i > 1", f, [1.1]);
233 self.should_assert("Should assert if p_i < 0", f, [-.1]);
235 def test_repair_count_pmf(self):
236 survival_pmf = statistics.binomial_distribution_pmf(5, .9)
237 repair_pmf = statistics.repair_count_pmf(survival_pmf, 3)
238 # repair_pmf[0] == sum(survival_pmf[0,1,2,5])
239 # repair_pmf[1] == survival_pmf[4]
240 # repair_pmf[2] = survival_pmf[3]
241 self.failUnlessListAlmostEqual(repair_pmf,
242 [0.00001 + 0.00045 + 0.0081 + 0.59049,
247 def test_repair_cost(self):
248 survival_pmf = statistics.binomial_distribution_pmf(5, .9)
249 bwcost = statistics.bandwidth_cost_function
250 cost = statistics.mean_repair_cost(bwcost, 1000,
251 survival_pmf, 3, ul_dl_ratio=1.0)
252 self.failUnlessAlmostEqual(cost, 558.90)
253 cost = statistics.mean_repair_cost(bwcost, 1000,
254 survival_pmf, 3, ul_dl_ratio=8.0)
255 self.failUnlessAlmostEqual(cost, 1664.55)
257 # I haven't manually checked the math beyond here -warner
258 cost = statistics.eternal_repair_cost(bwcost, 1000,
260 discount_rate=0, ul_dl_ratio=1.0)
261 self.failUnlessAlmostEqual(cost, 65292.056074766246)
262 cost = statistics.eternal_repair_cost(bwcost, 1000,
266 self.failUnlessAlmostEqual(cost, 9133.6097158191551)
268 def test_convolve(self):
269 f = statistics.convolve
273 v1v2result = [ 4, 13, 28, 27, 18 ]
274 # Convolution is commutative
277 self.failUnlessListEqual(r1, r2, "Convolution should be commutative")
278 self.failUnlessListEqual(r1, v1v2result, "Didn't match known result")
279 # Convolution is associative
280 r1 = f(f(v1, v2), v3)
281 r2 = f(v1, f(v2, v3))
282 self.failUnlessListEqual(r1, r2, "Convolution should be associative")
283 # Convolution is distributive
284 r1 = f(v3, [ a + b for a, b in zip(v1, v2) ])
287 r2 = [ a + b for a, b in zip(tmp1, tmp2) ]
288 self.failUnlessListEqual(r1, r2, "Convolution should be distributive")
289 # Convolution is scalar multiplication associative
291 r1 = [ a * 4 for a in tmp1 ]
292 tmp2 = [ a * 4 for a in v1 ]
294 self.failUnlessListEqual(r1, r2, "Convolution should be scalar multiplication associative")
296 def test_find_k(self):
297 f = statistics.find_k
298 g = statistics.pr_file_loss
299 plist = [.9] * 10 + [.8] * 10 # N=20
302 self.failUnlessEqual(k, 10)
303 self.failUnless(g(plist, k) < t)
305 def test_pr_file_loss(self):
306 f = statistics.pr_file_loss
308 self.failUnlessEqual(f(plist, 3), .0546875)
310 def test_pr_backup_file_loss(self):
311 f = statistics.pr_backup_file_loss
313 self.failUnlessEqual(f(plist, .5, 3), .02734375)
316 class Asserts(unittest.TestCase):
317 def should_assert(self, func, *args, **kwargs):
319 func(*args, **kwargs)
320 except AssertionError, e:
323 self.fail("assert failed with non-AssertionError: %s" % e)
324 self.fail("assert was not caught")
326 def should_not_assert(self, func, *args, **kwargs):
328 func(*args, **kwargs)
329 except AssertionError, e:
330 self.fail("assertion fired when it should not have: %s" % e)
332 self.fail("assertion (which shouldn't have failed) failed with non-AssertionError: %s" % e)
336 def test_assert(self):
337 f = assertutil._assert
338 self.should_assert(f)
339 self.should_assert(f, False)
340 self.should_not_assert(f, True)
342 m = self.should_assert(f, False, "message")
343 self.failUnlessEqual(m, "'message' <type 'str'>", m)
344 m = self.should_assert(f, False, "message1", othermsg=12)
345 self.failUnlessEqual("'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
346 m = self.should_assert(f, False, othermsg="message2")
347 self.failUnlessEqual("othermsg: 'message2' <type 'str'>", m)
349 def test_precondition(self):
350 f = assertutil.precondition
351 self.should_assert(f)
352 self.should_assert(f, False)
353 self.should_not_assert(f, True)
355 m = self.should_assert(f, False, "message")
356 self.failUnlessEqual("precondition: 'message' <type 'str'>", m)
357 m = self.should_assert(f, False, "message1", othermsg=12)
358 self.failUnlessEqual("precondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
359 m = self.should_assert(f, False, othermsg="message2")
360 self.failUnlessEqual("precondition: othermsg: 'message2' <type 'str'>", m)
362 def test_postcondition(self):
363 f = assertutil.postcondition
364 self.should_assert(f)
365 self.should_assert(f, False)
366 self.should_not_assert(f, True)
368 m = self.should_assert(f, False, "message")
369 self.failUnlessEqual("postcondition: 'message' <type 'str'>", m)
370 m = self.should_assert(f, False, "message1", othermsg=12)
371 self.failUnlessEqual("postcondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
372 m = self.should_assert(f, False, othermsg="message2")
373 self.failUnlessEqual("postcondition: othermsg: 'message2' <type 'str'>", m)
375 class FileUtil(ReallyEqualMixin, unittest.TestCase):
376 def mkdir(self, basedir, path, mode=0777):
377 fn = os.path.join(basedir, path)
378 fileutil.make_dirs(fn, mode)
380 def touch(self, basedir, path, mode=None, data="touch\n"):
381 fn = os.path.join(basedir, path)
388 def test_rm_dir(self):
389 basedir = "util/FileUtil/test_rm_dir"
390 fileutil.make_dirs(basedir)
391 # create it again to test idempotency
392 fileutil.make_dirs(basedir)
393 d = os.path.join(basedir, "doomed")
395 self.touch(d, "a/b/1.txt")
396 self.touch(d, "a/b/2.txt", 0444)
397 self.touch(d, "a/b/3.txt", 0)
399 self.touch(d, "a/c/1.txt")
400 self.touch(d, "a/c/2.txt", 0444)
401 self.touch(d, "a/c/3.txt", 0)
402 os.chmod(os.path.join(d, "a/c"), 0444)
404 self.touch(d, "a/d/1.txt")
405 self.touch(d, "a/d/2.txt", 0444)
406 self.touch(d, "a/d/3.txt", 0)
407 os.chmod(os.path.join(d, "a/d"), 0)
410 self.failIf(os.path.exists(d))
411 # remove it again to test idempotency
414 def test_remove_if_possible(self):
415 basedir = "util/FileUtil/test_remove_if_possible"
416 fileutil.make_dirs(basedir)
417 self.touch(basedir, "here")
418 fn = os.path.join(basedir, "here")
419 fileutil.remove_if_possible(fn)
420 self.failIf(os.path.exists(fn))
421 fileutil.remove_if_possible(fn) # should be idempotent
422 fileutil.rm_dir(basedir)
423 fileutil.remove_if_possible(fn) # should survive errors
425 def test_write_atomically(self):
426 basedir = "util/FileUtil/test_write_atomically"
427 fileutil.make_dirs(basedir)
428 fn = os.path.join(basedir, "here")
429 fileutil.write_atomically(fn, "one")
430 self.failUnlessEqual(fileutil.read(fn), "one")
431 fileutil.write_atomically(fn, "two", mode="") # non-binary
432 self.failUnlessEqual(fileutil.read(fn), "two")
434 def test_NamedTemporaryDirectory(self):
435 basedir = "util/FileUtil/test_NamedTemporaryDirectory"
436 fileutil.make_dirs(basedir)
437 td = fileutil.NamedTemporaryDirectory(dir=basedir)
439 self.failUnless(basedir in name)
440 self.failUnless(basedir in repr(td))
441 self.failUnless(os.path.isdir(name))
443 # it is conceivable that we need to force gc here, but I'm not sure
444 self.failIf(os.path.isdir(name))
446 def test_rename(self):
447 basedir = "util/FileUtil/test_rename"
448 fileutil.make_dirs(basedir)
449 self.touch(basedir, "here")
450 fn = os.path.join(basedir, "here")
451 fn2 = os.path.join(basedir, "there")
452 fileutil.rename(fn, fn2)
453 self.failIf(os.path.exists(fn))
454 self.failUnless(os.path.exists(fn2))
457 basedir = "util/FileUtil/test_du"
458 fileutil.make_dirs(basedir)
459 d = os.path.join(basedir, "space-consuming")
461 self.touch(d, "a/b/1.txt", data="a"*10)
462 self.touch(d, "a/b/2.txt", data="b"*11)
464 self.touch(d, "a/c/1.txt", data="c"*12)
465 self.touch(d, "a/c/2.txt", data="d"*13)
467 used = fileutil.du(basedir)
468 self.failUnlessEqual(10+11+12+13, used)
470 def test_abspath_expanduser_unicode(self):
471 self.failUnlessRaises(AssertionError, fileutil.abspath_expanduser_unicode, "bytestring")
473 saved_cwd = os.path.normpath(os.getcwdu())
474 abspath_cwd = fileutil.abspath_expanduser_unicode(u".")
475 self.failUnless(isinstance(saved_cwd, unicode), saved_cwd)
476 self.failUnless(isinstance(abspath_cwd, unicode), abspath_cwd)
477 if sys.platform == "win32":
478 self.failUnlessReallyEqual(abspath_cwd, fileutil.to_windows_long_path(saved_cwd))
480 self.failUnlessReallyEqual(abspath_cwd, saved_cwd)
482 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\?\\foo"), u"\\\\?\\foo")
483 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\.\\foo"), u"\\\\.\\foo")
484 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\server\\foo"), u"\\\\?\\UNC\\server\\foo")
485 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo"), u"\\\\?\\C:\\foo")
486 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo/bar"), u"\\\\?\\C:\\foo\\bar")
488 # adapted from <http://svn.python.org/view/python/branches/release26-maint/Lib/test/test_posixpath.py?view=markup&pathrev=78279#test_abspath>
490 foo = fileutil.abspath_expanduser_unicode(u"foo")
491 self.failUnless(foo.endswith(u"%sfoo" % (os.path.sep,)), foo)
493 foobar = fileutil.abspath_expanduser_unicode(u"bar", base=foo)
494 self.failUnless(foobar.endswith(u"%sfoo%sbar" % (os.path.sep, os.path.sep)), foobar)
496 if sys.platform == "win32":
497 # This is checking that a drive letter is added for a path without one.
498 baz = fileutil.abspath_expanduser_unicode(u"\\baz")
499 self.failUnless(baz.startswith(u"\\\\?\\"), baz)
500 self.failUnlessReallyEqual(baz[5 :], u":\\baz")
502 bar = fileutil.abspath_expanduser_unicode(u"\\bar", base=baz)
503 self.failUnless(bar.startswith(u"\\\\?\\"), bar)
504 self.failUnlessReallyEqual(bar[5 :], u":\\bar")
505 # not u":\\baz\\bar", because \bar is absolute on the current drive.
507 self.failUnlessReallyEqual(baz[4], bar[4]) # same drive
509 self.failIfIn(u"~", fileutil.abspath_expanduser_unicode(u"~"))
513 cwds.append(u'\xe7w\xf0'.encode(sys.getfilesystemencoding()
515 except UnicodeEncodeError:
516 pass # the cwd can't be encoded -- test with ascii cwd only
522 for upath in (u'', u'fuu', u'f\xf9\xf9', u'/fuu', u'U:\\', u'~'):
523 uabspath = fileutil.abspath_expanduser_unicode(upath)
524 self.failUnless(isinstance(uabspath, unicode), uabspath)
528 def test_create_long_path(self):
529 workdir = u"test_create_long_path"
530 fileutil.make_dirs(workdir)
531 long_path = fileutil.abspath_expanduser_unicode(os.path.join(workdir, u'x'*255))
533 fileutil.remove(long_path)
534 self.addCleanup(_cleanup)
536 fileutil.write(long_path, "test")
537 self.failUnless(os.path.exists(long_path))
538 self.failUnlessEqual(fileutil.read(long_path), "test")
540 self.failIf(os.path.exists(long_path))
542 def _test_windows_expanduser(self, userprofile=None, homedrive=None, homepath=None):
543 def call_windows_getenv(name):
544 if name == u"USERPROFILE": return userprofile
545 if name == u"HOMEDRIVE": return homedrive
546 if name == u"HOMEPATH": return homepath
547 self.fail("unexpected argument to call_windows_getenv")
548 self.patch(fileutil, 'windows_getenv', call_windows_getenv)
550 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
551 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~\\foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
552 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~/foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
553 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a"), u"a")
554 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a~"), u"a~")
555 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a\\~\\foo"), u"a\\~\\foo")
557 def test_windows_expanduser_xp(self):
558 return self._test_windows_expanduser(homedrive=u"C:", homepath=u"\\Documents and Settings\\\u0100")
560 def test_windows_expanduser_win7(self):
561 return self._test_windows_expanduser(userprofile=os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
563 def test_disk_stats(self):
564 avail = fileutil.get_available_space('.', 2**14)
566 raise unittest.SkipTest("This test will spuriously fail there is no disk space left.")
568 disk = fileutil.get_disk_stats('.', 2**13)
569 self.failUnless(disk['total'] > 0, disk['total'])
570 # we tolerate used==0 for a Travis-CI bug, see #2290
571 self.failUnless(disk['used'] >= 0, disk['used'])
572 self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
573 self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
574 self.failUnless(disk['avail'] > 0, disk['avail'])
576 def test_disk_stats_avail_nonnegative(self):
577 # This test will spuriously fail if you have more than 2^128
578 # bytes of available space on your filesystem.
579 disk = fileutil.get_disk_stats('.', 2**128)
580 self.failUnlessEqual(disk['avail'], 0)
582 class PollMixinTests(unittest.TestCase):
584 self.pm = pollmixin.PollMixin()
586 def test_PollMixin_True(self):
587 d = self.pm.poll(check_f=lambda : True,
591 def test_PollMixin_False_then_True(self):
592 i = iter([False, True])
593 d = self.pm.poll(check_f=i.next,
597 def test_timeout(self):
598 d = self.pm.poll(check_f=lambda: False,
602 self.fail("poll should have failed, not returned %s" % (res,))
604 f.trap(pollmixin.TimeoutError)
605 return None # success
606 d.addCallbacks(_suc, _err)
609 class DeferredUtilTests(unittest.TestCase, deferredutil.WaitForDelayedCallsMixin):
610 def test_gather_results(self):
611 d1 = defer.Deferred()
612 d2 = defer.Deferred()
613 res = deferredutil.gatherResults([d1, d2])
614 d1.errback(ValueError("BAD"))
616 self.fail("Should have errbacked, not resulted in %s" % (res,))
618 thef.trap(ValueError)
619 res.addCallbacks(_callb, _errb)
622 def test_success(self):
623 d1, d2 = defer.Deferred(), defer.Deferred()
626 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
627 dlss.addCallbacks(good.append, bad.append)
630 self.failUnlessEqual(good, [[1,2]])
631 self.failUnlessEqual(bad, [])
633 def test_failure(self):
634 d1, d2 = defer.Deferred(), defer.Deferred()
637 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
638 dlss.addCallbacks(good.append, bad.append)
639 d1.addErrback(lambda _ignore: None)
640 d2.addErrback(lambda _ignore: None)
642 d2.errback(ValueError())
643 self.failUnlessEqual(good, [])
644 self.failUnlessEqual(len(bad), 1)
646 self.failUnless(isinstance(f, Failure))
647 self.failUnless(f.check(ValueError))
649 def test_wait_for_delayed_calls(self):
651 This tests that 'wait_for_delayed_calls' does in fact wait for a
652 delayed call that is active when the test returns. If it didn't,
653 Trial would report an unclean reactor error for this test.
658 reactor.callLater(0.1, _trigger)
660 d = defer.succeed(None)
661 d.addBoth(self.wait_for_delayed_calls)
664 class HashUtilTests(unittest.TestCase):
666 def test_random_key(self):
667 k = hashutil.random_key()
668 self.failUnlessEqual(len(k), hashutil.KEYLEN)
670 def test_sha256d(self):
671 h1 = hashutil.tagged_hash("tag1", "value")
672 h2 = hashutil.tagged_hasher("tag1")
676 self.failUnlessEqual(h1, h2a)
677 self.failUnlessEqual(h2a, h2b)
679 def test_sha256d_truncated(self):
680 h1 = hashutil.tagged_hash("tag1", "value", 16)
681 h2 = hashutil.tagged_hasher("tag1", 16)
684 self.failUnlessEqual(len(h1), 16)
685 self.failUnlessEqual(len(h2), 16)
686 self.failUnlessEqual(h1, h2)
689 h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
690 h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
693 self.failUnlessEqual(h1, h2)
695 def test_hashers(self):
696 h1 = hashutil.block_hash("foo")
697 h2 = hashutil.block_hasher()
699 self.failUnlessEqual(h1, h2.digest())
701 h1 = hashutil.uri_extension_hash("foo")
702 h2 = hashutil.uri_extension_hasher()
704 self.failUnlessEqual(h1, h2.digest())
706 h1 = hashutil.plaintext_hash("foo")
707 h2 = hashutil.plaintext_hasher()
709 self.failUnlessEqual(h1, h2.digest())
711 h1 = hashutil.crypttext_hash("foo")
712 h2 = hashutil.crypttext_hasher()
714 self.failUnlessEqual(h1, h2.digest())
716 h1 = hashutil.crypttext_segment_hash("foo")
717 h2 = hashutil.crypttext_segment_hasher()
719 self.failUnlessEqual(h1, h2.digest())
721 h1 = hashutil.plaintext_segment_hash("foo")
722 h2 = hashutil.plaintext_segment_hasher()
724 self.failUnlessEqual(h1, h2.digest())
726 def test_timing_safe_compare(self):
727 self.failUnless(hashutil.timing_safe_compare("a", "a"))
728 self.failUnless(hashutil.timing_safe_compare("ab", "ab"))
729 self.failIf(hashutil.timing_safe_compare("a", "b"))
730 self.failIf(hashutil.timing_safe_compare("a", "aa"))
732 def _testknown(self, hashf, expected_a, *args):
734 got_a = base32.b2a(got)
735 self.failUnlessEqual(got_a, expected_a)
737 def test_known_answers(self):
738 # assert backwards compatibility
739 self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
740 self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
741 self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
742 self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
743 self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
744 self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
745 self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
746 self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
747 self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
748 self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
749 self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
750 self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
751 self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
752 self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
753 self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
754 self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
755 self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
756 self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
757 self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
758 self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
759 self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
760 self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
761 self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
764 class Abbreviate(unittest.TestCase):
766 a = abbreviate.abbreviate_time
767 self.failUnlessEqual(a(None), "unknown")
768 self.failUnlessEqual(a(0), "0 seconds")
769 self.failUnlessEqual(a(1), "1 second")
770 self.failUnlessEqual(a(2), "2 seconds")
771 self.failUnlessEqual(a(119), "119 seconds")
773 self.failUnlessEqual(a(2*MIN), "2 minutes")
774 self.failUnlessEqual(a(60*MIN), "60 minutes")
775 self.failUnlessEqual(a(179*MIN), "179 minutes")
777 self.failUnlessEqual(a(180*MIN), "3 hours")
778 self.failUnlessEqual(a(4*HOUR), "4 hours")
781 self.failUnlessEqual(a(2*DAY), "2 days")
782 self.failUnlessEqual(a(2*MONTH), "2 months")
784 self.failUnlessEqual(a(5*YEAR), "5 years")
786 def test_space(self):
787 tests_si = [(None, "unknown"),
794 (20*1000, "20.00 kB"),
795 (1024*1024, "1.05 MB"),
796 (1000*1000, "1.00 MB"),
797 (1000*1000*1000, "1.00 GB"),
798 (1000*1000*1000*1000, "1.00 TB"),
799 (1000*1000*1000*1000*1000, "1.00 PB"),
800 (1000*1000*1000*1000*1000*1000, "1.00 EB"),
801 (1234567890123456789, "1.23 EB"),
803 for (x, expected) in tests_si:
804 got = abbreviate.abbreviate_space(x, SI=True)
805 self.failUnlessEqual(got, expected)
807 tests_base1024 = [(None, "unknown"),
814 (20*1024, "20.00 kiB"),
815 (1000*1000, "976.56 kiB"),
816 (1024*1024, "1.00 MiB"),
817 (1024*1024*1024, "1.00 GiB"),
818 (1024*1024*1024*1024, "1.00 TiB"),
819 (1000*1000*1000*1000*1000, "909.49 TiB"),
820 (1024*1024*1024*1024*1024, "1.00 PiB"),
821 (1024*1024*1024*1024*1024*1024, "1.00 EiB"),
822 (1234567890123456789, "1.07 EiB"),
824 for (x, expected) in tests_base1024:
825 got = abbreviate.abbreviate_space(x, SI=False)
826 self.failUnlessEqual(got, expected)
828 self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
829 "(1.23 MB, 1.18 MiB)")
831 def test_parse_space(self):
832 p = abbreviate.parse_abbreviated_size
833 self.failUnlessEqual(p(""), None)
834 self.failUnlessEqual(p(None), None)
835 self.failUnlessEqual(p("123"), 123)
836 self.failUnlessEqual(p("123B"), 123)
837 self.failUnlessEqual(p("2K"), 2000)
838 self.failUnlessEqual(p("2kb"), 2000)
839 self.failUnlessEqual(p("2KiB"), 2048)
840 self.failUnlessEqual(p("10MB"), 10*1000*1000)
841 self.failUnlessEqual(p("10MiB"), 10*1024*1024)
842 self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
843 self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
844 self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
845 self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
846 self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
847 self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
848 self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
849 self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
851 e = self.failUnlessRaises(ValueError, p, "12 cubits")
852 self.failUnlessIn("12 cubits", str(e))
853 e = self.failUnlessRaises(ValueError, p, "1 BB")
854 self.failUnlessIn("1 BB", str(e))
855 e = self.failUnlessRaises(ValueError, p, "fhtagn")
856 self.failUnlessIn("fhtagn", str(e))
858 class Limiter(unittest.TestCase):
859 timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
861 def job(self, i, foo):
862 self.calls.append( (i, foo) )
863 self.simultaneous += 1
864 self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
867 self.simultaneous -= 1
868 d.callback("done %d" % i)
869 reactor.callLater(1.0, _done)
872 def bad_job(self, i, foo):
873 raise ValueError("bad_job %d" % i)
875 def test_limiter(self):
877 self.simultaneous = 0
878 self.peak_simultaneous = 0
879 l = limiter.ConcurrencyLimiter()
882 dl.append(l.add(self.job, i, foo=str(i)))
883 d = defer.DeferredList(dl, fireOnOneErrback=True)
885 self.failUnlessEqual(self.simultaneous, 0)
886 self.failUnless(self.peak_simultaneous <= 10)
887 self.failUnlessEqual(len(self.calls), 20)
889 self.failUnless( (i, str(i)) in self.calls)
893 def test_errors(self):
895 self.simultaneous = 0
896 self.peak_simultaneous = 0
897 l = limiter.ConcurrencyLimiter()
900 dl.append(l.add(self.job, i, foo=str(i)))
901 d2 = l.add(self.bad_job, 21, "21")
902 d = defer.DeferredList(dl, fireOnOneErrback=True)
905 for (success, result) in res:
906 self.failUnlessEqual(success, True)
907 results.append(result)
909 expected_results = ["done %d" % i for i in range(20)]
910 expected_results.sort()
911 self.failUnlessEqual(results, expected_results)
912 self.failUnless(self.peak_simultaneous <= 10)
913 self.failUnlessEqual(len(self.calls), 20)
915 self.failUnless( (i, str(i)) in self.calls)
917 self.fail("should have failed, not got %s" % (res,))
920 self.failUnless("bad_job 21" in str(f))
921 d2.addCallbacks(_good, _err)
923 d.addCallback(_most_done)
925 self.failUnlessEqual(self.simultaneous, 0)
926 self.failUnless(self.peak_simultaneous <= 10)
927 self.failUnlessEqual(len(self.calls), 20)
929 self.failUnless( (i, str(i)) in self.calls)
930 d.addCallback(_all_done)
933 class TimeFormat(unittest.TestCase):
934 def test_epoch(self):
935 return self._help_test_epoch()
937 def test_epoch_in_London(self):
938 # Europe/London is a particularly troublesome timezone. Nowadays, its
939 # offset from GMT is 0. But in 1970, its offset from GMT was 1.
940 # (Apparently in 1970 Britain had redefined standard time to be GMT+1
941 # and stayed in standard time all year round, whereas today
942 # Europe/London standard time is GMT and Europe/London Daylight
943 # Savings Time is GMT+1.) The current implementation of
944 # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
945 # Europe/London. (As soon as this unit test is done then I'll change
946 # that implementation to something that works even in this case...)
947 origtz = os.environ.get('TZ')
948 os.environ['TZ'] = "Europe/London"
949 if hasattr(time, 'tzset'):
952 return self._help_test_epoch()
957 os.environ['TZ'] = origtz
958 if hasattr(time, 'tzset'):
961 def _help_test_epoch(self):
962 origtzname = time.tzname
963 s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
964 self.failUnlessEqual(s, 1.0)
965 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
966 self.failUnlessEqual(s, 1.0)
967 s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
968 self.failUnlessEqual(s, 1.0)
970 self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
971 self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
972 "1970-01-01 00:00:01")
975 isostr = time_format.iso_utc(now)
976 timestamp = time_format.iso_utc_time_to_seconds(isostr)
977 self.failUnlessEqual(int(timestamp), int(now))
981 self.failUnlessEqual(time_format.iso_utc(t=my_time),
982 "1970-01-01_00:00:01")
983 e = self.failUnlessRaises(ValueError,
984 time_format.iso_utc_time_to_seconds,
985 "invalid timestring")
986 self.failUnless("not a complete ISO8601 timestamp" in str(e))
987 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
988 self.failUnlessEqual(s, 1.5)
990 # Look for daylight-savings-related errors.
991 thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
992 self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
993 self.failUnlessEqual(origtzname, time.tzname)
995 def test_iso_utc(self):
996 when = 1266760143.7841301
997 out = time_format.iso_utc_date(when)
998 self.failUnlessEqual(out, "2010-02-21")
999 out = time_format.iso_utc_date(t=lambda: when)
1000 self.failUnlessEqual(out, "2010-02-21")
1001 out = time_format.iso_utc(when)
1002 self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
1003 out = time_format.iso_utc(when, sep="-")
1004 self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
1006 def test_parse_duration(self):
1007 p = time_format.parse_duration
1009 self.failUnlessEqual(p("1 day"), DAY)
1010 self.failUnlessEqual(p("2 days"), 2*DAY)
1011 self.failUnlessEqual(p("3 months"), 3*31*DAY)
1012 self.failUnlessEqual(p("4 mo"), 4*31*DAY)
1013 self.failUnlessEqual(p("5 years"), 5*365*DAY)
1014 e = self.failUnlessRaises(ValueError, p, "123")
1015 self.failUnlessIn("no unit (like day, month, or year) in '123'",
1018 def test_parse_date(self):
1019 self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
1021 class CacheDir(unittest.TestCase):
1022 def test_basic(self):
1023 basedir = "test_util/CacheDir/test_basic"
1025 def _failIfExists(name):
1026 absfn = os.path.join(basedir, name)
1027 self.failIf(os.path.exists(absfn),
1028 "%s exists but it shouldn't" % absfn)
1030 def _failUnlessExists(name):
1031 absfn = os.path.join(basedir, name)
1032 self.failUnless(os.path.exists(absfn),
1033 "%s doesn't exist but it should" % absfn)
1035 cdm = cachedir.CacheDirectoryManager(basedir)
1036 a = cdm.get_file("a")
1037 b = cdm.get_file("b")
1038 c = cdm.get_file("c")
1039 f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
1040 f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
1041 f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
1043 _failUnlessExists("a")
1044 _failUnlessExists("b")
1045 _failUnlessExists("c")
1049 _failUnlessExists("a")
1050 _failUnlessExists("b")
1051 _failUnlessExists("c")
1054 # this file won't be deleted yet, because it isn't old enough
1056 _failUnlessExists("a")
1057 _failUnlessExists("b")
1058 _failUnlessExists("c")
1060 # we change the definition of "old" to make everything old
1065 _failUnlessExists("b")
1066 _failUnlessExists("c")
1074 _failUnlessExists("b")
1075 _failUnlessExists("c")
1077 b2 = cdm.get_file("b")
1081 _failUnlessExists("b")
1082 _failUnlessExists("c")
1087 def __init__(self, x):
1092 return "<%s %s>" % (self.__class__.__name__, self.x,)
1095 def __le__(self, other):
1096 return self.x <= other
1097 def __lt__(self, other):
1098 return self.x < other
1099 def __ge__(self, other):
1100 return self.x >= other
1101 def __gt__(self, other):
1102 return self.x > other
1103 def __ne__(self, other):
1104 return self.x != other
1105 def __eq__(self, other):
1106 return self.x == other
1108 class DictUtil(unittest.TestCase):
1109 def _help_test_empty_dict(self, klass):
1113 self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1114 self.failUnless(len(d1) == 0)
1115 self.failUnless(len(d2) == 0)
1117 def _help_test_nonempty_dict(self, klass):
1118 d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1119 d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1121 self.failUnless(d1 == d2)
1122 self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1123 self.failUnless(len(d2) == 3)
1125 def _help_test_eq_but_notis(self, klass):
1126 d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1131 d['b'] = EqButNotIs(3)
1136 d['b'] = EqButNotIs(3)
1142 d['a'] = EqButNotIs(3)
1147 fake3 = EqButNotIs(3)
1148 fake7 = EqButNotIs(7)
1152 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1153 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1154 # The real 7 should have been ejected by the d[3] = 8.
1155 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1156 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1157 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1162 fake3 = EqButNotIs(3)
1163 fake7 = EqButNotIs(7)
1166 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1167 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1168 # The real 7 should have been ejected by the d[3] = 8.
1169 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1170 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1171 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1175 self._help_test_eq_but_notis(dictutil.UtilDict)
1176 self._help_test_eq_but_notis(dictutil.NumDict)
1177 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1178 self._help_test_nonempty_dict(dictutil.UtilDict)
1179 self._help_test_nonempty_dict(dictutil.NumDict)
1180 self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1181 self._help_test_eq_but_notis(dictutil.UtilDict)
1182 self._help_test_eq_but_notis(dictutil.NumDict)
1183 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1185 def test_dict_of_sets(self):
1186 ds = dictutil.DictOfSets()
1191 self.failUnlessEqual(ds[1], set(["a"]))
1192 self.failUnlessEqual(ds[2], set(["b", "c"]))
1193 ds.discard(3, "d") # should not raise an exception
1195 self.failUnlessEqual(ds[2], set(["c"]))
1197 self.failIf(2 in ds)
1200 ds2 = dictutil.DictOfSets()
1205 self.failUnlessEqual(ds[1], set(["a"]))
1206 self.failUnlessEqual(ds[3], set(["f", "g"]))
1207 self.failUnlessEqual(ds[4], set(["h"]))
1209 def test_move(self):
1210 d1 = {1: "a", 2: "b"}
1211 d2 = {2: "c", 3: "d"}
1212 dictutil.move(1, d1, d2)
1213 self.failUnlessEqual(d1, {2: "b"})
1214 self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1216 d1 = {1: "a", 2: "b"}
1217 d2 = {2: "c", 3: "d"}
1218 dictutil.move(2, d1, d2)
1219 self.failUnlessEqual(d1, {1: "a"})
1220 self.failUnlessEqual(d2, {2: "b", 3: "d"})
1222 d1 = {1: "a", 2: "b"}
1223 d2 = {2: "c", 3: "d"}
1224 self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1226 def test_subtract(self):
1227 d1 = {1: "a", 2: "b"}
1228 d2 = {2: "c", 3: "d"}
1229 d3 = dictutil.subtract(d1, d2)
1230 self.failUnlessEqual(d3, {1: "a"})
1232 d1 = {1: "a", 2: "b"}
1234 d3 = dictutil.subtract(d1, d2)
1235 self.failUnlessEqual(d3, {1: "a"})
1237 def test_utildict(self):
1238 d = dictutil.UtilDict({1: "a", 2: "b"})
1241 self.failUnlessEqual(d, {2: "b"})
1244 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1246 d = dictutil.UtilDict({1: "b", 2: "a"})
1247 self.failUnlessEqual(d.items_sorted_by_value(),
1248 [(2, "a"), (1, "b")])
1249 self.failUnlessEqual(d.items_sorted_by_key(),
1250 [(1, "b"), (2, "a")])
1251 self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1252 self.failUnless(1 in d)
1254 d2 = dictutil.UtilDict({3: "c", 4: "d"})
1255 self.failUnless(d != d2)
1256 self.failUnless(d2 > d)
1257 self.failUnless(d2 >= d)
1258 self.failUnless(d <= d2)
1259 self.failUnless(d < d2)
1260 self.failUnlessEqual(d[1], "b")
1261 self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1264 self.failUnlessEqual(d, d3)
1265 self.failUnless(isinstance(d3, dictutil.UtilDict))
1267 d4 = d.fromkeys([3,4], "e")
1268 self.failUnlessEqual(d4, {3: "e", 4: "e"})
1270 self.failUnlessEqual(d.get(1), "b")
1271 self.failUnlessEqual(d.get(3), None)
1272 self.failUnlessEqual(d.get(3, "default"), "default")
1273 self.failUnlessEqual(sorted(list(d.items())),
1274 [(1, "b"), (2, "a")])
1275 self.failUnlessEqual(sorted(list(d.iteritems())),
1276 [(1, "b"), (2, "a")])
1277 self.failUnlessEqual(sorted(d.keys()), [1, 2])
1278 self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1279 x = d.setdefault(1, "new")
1280 self.failUnlessEqual(x, "b")
1281 self.failUnlessEqual(d[1], "b")
1282 x = d.setdefault(3, "new")
1283 self.failUnlessEqual(x, "new")
1284 self.failUnlessEqual(d[3], "new")
1288 self.failUnless(x in [(1, "b"), (2, "a")])
1290 self.failUnless(x in [(1, "b"), (2, "a")])
1291 self.failUnlessRaises(KeyError, d.popitem)
1293 def test_numdict(self):
1294 d = dictutil.NumDict({"a": 1, "b": 2})
1296 d.add_num("a", 10, 5)
1297 d.add_num("c", 20, 5)
1299 self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1301 d.subtract_num("a", 10)
1302 d.subtract_num("e", 10)
1303 d.subtract_num("f", 10, 15)
1304 self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1307 self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1309 d = dictutil.NumDict()
1313 self.failUnlessEqual(d, {"a": 2, "b": 6})
1317 self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1318 self.failUnlessEqual(d.items_sorted_by_key(),
1319 [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1320 self.failUnlessEqual(d.items_sorted_by_value(),
1321 [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1322 self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1324 d = dictutil.NumDict({"a": 1, "b": 2})
1325 self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1326 self.failUnless("a" in d)
1328 d2 = dictutil.NumDict({"c": 3, "d": 4})
1329 self.failUnless(d != d2)
1330 self.failUnless(d2 > d)
1331 self.failUnless(d2 >= d)
1332 self.failUnless(d <= d2)
1333 self.failUnless(d < d2)
1334 self.failUnlessEqual(d["a"], 1)
1335 self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1338 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1341 self.failUnlessEqual(d, d3)
1342 self.failUnless(isinstance(d3, dictutil.NumDict))
1344 d4 = d.fromkeys(["a","b"], 5)
1345 self.failUnlessEqual(d4, {"a": 5, "b": 5})
1347 self.failUnlessEqual(d.get("a"), 1)
1348 self.failUnlessEqual(d.get("c"), 0)
1349 self.failUnlessEqual(d.get("c", 5), 5)
1350 self.failUnlessEqual(sorted(list(d.items())),
1351 [("a", 1), ("b", 2)])
1352 self.failUnlessEqual(sorted(list(d.iteritems())),
1353 [("a", 1), ("b", 2)])
1354 self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1355 self.failUnlessEqual(sorted(d.values()), [1, 2])
1356 self.failUnless(d.has_key("a"))
1357 self.failIf(d.has_key("c"))
1359 x = d.setdefault("c", 3)
1360 self.failUnlessEqual(x, 3)
1361 self.failUnlessEqual(d["c"], 3)
1362 x = d.setdefault("c", 5)
1363 self.failUnlessEqual(x, 3)
1364 self.failUnlessEqual(d["c"], 3)
1368 self.failUnless(x in [("a", 1), ("b", 2)])
1370 self.failUnless(x in [("a", 1), ("b", 2)])
1371 self.failUnlessRaises(KeyError, d.popitem)
1374 d.update({"c": 4, "d": 5})
1375 self.failUnlessEqual(d, {"c": 4, "d": 5})
1377 def test_del_if_present(self):
1378 d = {1: "a", 2: "b"}
1379 dictutil.del_if_present(d, 1)
1380 dictutil.del_if_present(d, 3)
1381 self.failUnlessEqual(d, {2: "b"})
1383 def test_valueordereddict(self):
1384 d = dictutil.ValueOrderedDict()
1389 self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1390 self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1391 self.failUnlessEqual(d.values(), [1, 2, 3])
1392 self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1393 self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1396 self.failIf(d == {"a": 4})
1397 self.failUnless(d != {"a": 4})
1399 x = d.setdefault("d", 0)
1400 self.failUnlessEqual(x, 0)
1401 self.failUnlessEqual(d["d"], 0)
1402 x = d.setdefault("d", -1)
1403 self.failUnlessEqual(x, 0)
1404 self.failUnlessEqual(d["d"], 0)
1406 x = d.remove("e", "default", False)
1407 self.failUnlessEqual(x, "default")
1408 self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1409 x = d.remove("d", 5)
1410 self.failUnlessEqual(x, 0)
1412 x = d.__getitem__("c")
1413 self.failUnlessEqual(x, 1)
1414 x = d.__getitem__("e", "default", False)
1415 self.failUnlessEqual(x, "default")
1416 self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1418 self.failUnlessEqual(d.popitem(), ("c", 1))
1419 self.failUnlessEqual(d.popitem(), ("b", 2))
1420 self.failUnlessEqual(d.popitem(), ("a", 3))
1421 self.failUnlessRaises(KeyError, d.popitem)
1423 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1424 x = d.pop("d", "default", False)
1425 self.failUnlessEqual(x, "default")
1426 self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1428 self.failUnlessEqual(x, 2)
1429 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1431 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1432 x = d.pop_from_list(1) # pop the second item, b/2
1433 self.failUnlessEqual(x, "b")
1434 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1436 def test_auxdict(self):
1437 d = dictutil.AuxValueDict()
1438 # we put the serialized form in the auxdata
1439 d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1441 self.failUnlessEqual(d.keys(), ["key"])
1442 self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1443 self.failUnlessEqual(d.get_aux("key"), "serialized")
1444 def _get_missing(key):
1446 self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1447 self.failUnlessEqual(d.get("nonkey"), None)
1448 self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1449 self.failUnlessEqual(d.get_aux("nonkey"), None)
1450 self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1452 d["key"] = ("filecap2", "metadata2")
1453 self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1454 self.failUnlessEqual(d.get_aux("key"), None)
1456 d.set_with_aux("key2", "value2", "aux2")
1457 self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1459 self.failUnlessEqual(d.keys(), ["key"])
1460 self.failIf("key2" in d)
1461 self.failUnlessRaises(KeyError, _get_missing, "key2")
1462 self.failUnlessEqual(d.get("key2"), None)
1463 self.failUnlessEqual(d.get_aux("key2"), None)
1464 d["key2"] = "newvalue2"
1465 self.failUnlessEqual(d.get("key2"), "newvalue2")
1466 self.failUnlessEqual(d.get_aux("key2"), None)
1468 d = dictutil.AuxValueDict({1:2,3:4})
1469 self.failUnlessEqual(sorted(d.keys()), [1,3])
1470 self.failUnlessEqual(d[1], 2)
1471 self.failUnlessEqual(d.get_aux(1), None)
1473 d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1474 self.failUnlessEqual(sorted(d.keys()), [1,3])
1475 self.failUnlessEqual(d[1], 2)
1476 self.failUnlessEqual(d.get_aux(1), None)
1478 d = dictutil.AuxValueDict(one=1, two=2)
1479 self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1480 self.failUnlessEqual(d["one"], 1)
1481 self.failUnlessEqual(d.get_aux("one"), None)
1483 class Pipeline(unittest.TestCase):
1484 def pause(self, *args, **kwargs):
1485 d = defer.Deferred()
1486 self.calls.append( (d, args, kwargs) )
1489 def failUnlessCallsAre(self, expected):
1492 self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1493 for i,c in enumerate(self.calls):
1494 self.failUnlessEqual(c[1:], expected[i], str(i))
1496 def test_basic(self):
1499 p = pipeline.Pipeline(100)
1501 d = p.flush() # fires immediately
1502 d.addCallbacks(finished.append, log.err)
1503 self.failUnlessEqual(len(finished), 1)
1506 d = p.add(10, self.pause, "one")
1507 # the call should start right away, and our return Deferred should
1509 d.addCallbacks(finished.append, log.err)
1510 self.failUnlessEqual(len(finished), 1)
1511 self.failUnlessEqual(finished[0], None)
1512 self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1513 self.failUnlessEqual(p.gauge, 10)
1518 d = p.add(20, self.pause, "two", kw=2)
1519 # pipeline: [one, two]
1521 # the call and the Deferred should fire right away
1522 d.addCallbacks(finished.append, log.err)
1523 self.failUnlessEqual(len(finished), 1)
1524 self.failUnlessEqual(finished[0], None)
1525 self.failUnlessCallsAre([ ( ("one",) , {} ),
1526 ( ("two",) , {"kw": 2} ),
1528 self.failUnlessEqual(p.gauge, 30)
1530 self.calls[0][0].callback("one-result")
1532 self.failUnlessEqual(p.gauge, 20)
1535 d = p.add(90, self.pause, "three", "posarg1")
1536 # pipeline: [two, three]
1539 fd.addCallbacks(flushed.append, log.err)
1540 self.failUnlessEqual(flushed, [])
1542 # the call will be made right away, but the return Deferred will not,
1543 # because the pipeline is now full.
1544 d.addCallbacks(finished.append, log.err)
1545 self.failUnlessEqual(len(finished), 0)
1546 self.failUnlessCallsAre([ ( ("one",) , {} ),
1547 ( ("two",) , {"kw": 2} ),
1548 ( ("three", "posarg1"), {} ),
1550 self.failUnlessEqual(p.gauge, 110)
1552 self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1554 # retiring either call will unblock the pipeline, causing the #3
1556 self.calls[2][0].callback("three-result")
1559 self.failUnlessEqual(len(finished), 1)
1560 self.failUnlessEqual(finished[0], None)
1561 self.failUnlessEqual(flushed, [])
1563 # retiring call#2 will finally allow the flush() Deferred to fire
1564 self.calls[1][0].callback("two-result")
1565 self.failUnlessEqual(len(flushed), 1)
1567 def test_errors(self):
1569 p = pipeline.Pipeline(100)
1571 d1 = p.add(200, self.pause, "one")
1575 d1.addBoth(finished.append)
1576 self.failUnlessEqual(finished, [])
1579 d2.addBoth(flushed.append)
1580 self.failUnlessEqual(flushed, [])
1582 self.calls[0][0].errback(ValueError("oops"))
1584 self.failUnlessEqual(len(finished), 1)
1586 self.failUnless(isinstance(f, Failure))
1587 self.failUnless(f.check(pipeline.PipelineError))
1588 self.failUnlessIn("PipelineError", str(f.value))
1589 self.failUnlessIn("ValueError", str(f.value))
1591 self.failUnless("ValueError" in r, r)
1593 self.failUnless(f2.check(ValueError))
1595 self.failUnlessEqual(len(flushed), 1)
1597 self.failUnless(isinstance(f, Failure))
1598 self.failUnless(f.check(pipeline.PipelineError))
1600 self.failUnless(f2.check(ValueError))
1602 # now that the pipeline is in the failed state, any new calls will
1605 d3 = p.add(20, self.pause, "two")
1608 d3.addBoth(finished.append)
1609 self.failUnlessEqual(len(finished), 1)
1611 self.failUnless(isinstance(f, Failure))
1612 self.failUnless(f.check(pipeline.PipelineError))
1614 self.failUnless("ValueError" in r, r)
1616 self.failUnless(f2.check(ValueError))
1620 d4.addBoth(flushed.append)
1621 self.failUnlessEqual(len(flushed), 1)
1623 self.failUnless(isinstance(f, Failure))
1624 self.failUnless(f.check(pipeline.PipelineError))
1626 self.failUnless(f2.check(ValueError))
1628 def test_errors2(self):
1630 p = pipeline.Pipeline(100)
1632 d1 = p.add(10, self.pause, "one")
1633 d2 = p.add(20, self.pause, "two")
1634 d3 = p.add(30, self.pause, "three")
1637 # one call fails, then the second one succeeds: make sure
1638 # ExpandableDeferredList tolerates the second one
1641 d4.addBoth(flushed.append)
1642 self.failUnlessEqual(flushed, [])
1644 self.calls[0][0].errback(ValueError("oops"))
1645 self.failUnlessEqual(len(flushed), 1)
1647 self.failUnless(isinstance(f, Failure))
1648 self.failUnless(f.check(pipeline.PipelineError))
1650 self.failUnless(f2.check(ValueError))
1652 self.calls[1][0].callback("two-result")
1653 self.calls[2][0].errback(ValueError("three-error"))
1657 class SampleError(Exception):
1660 class Log(unittest.TestCase):
1662 if not hasattr(self, "flushLoggedErrors"):
1663 # without flushLoggedErrors, we can't get rid of the
1664 # twisted.log.err that tahoe_log records, so we can't keep this
1665 # test from [ERROR]ing
1666 raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1668 raise SampleError("simple sample")
1671 tahoe_log.err(format="intentional sample error",
1672 failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1673 self.flushLoggedErrors(SampleError)
1677 # this is a simple+inefficient form of util.spans.Spans . We compare the
1678 # behavior of this reference model against the real (efficient) form.
1680 def __init__(self, _span_or_start=None, length=None):
1682 if length is not None:
1683 for i in range(_span_or_start, _span_or_start+length):
1685 elif _span_or_start:
1686 for (start,length) in _span_or_start:
1687 self.add(start, length)
1689 def add(self, start, length):
1690 for i in range(start, start+length):
1694 def remove(self, start, length):
1695 for i in range(start, start+length):
1696 self._have.discard(i)
1700 return sorted(self._have)
1703 items = sorted(self._have)
1707 if prevstart is None:
1708 prevstart = prevend = i
1713 yield (prevstart, prevend-prevstart+1)
1714 prevstart = prevend = i
1715 if prevstart is not None:
1716 yield (prevstart, prevend-prevstart+1)
1718 def __nonzero__(self): # this gets us bool()
1722 return len(self._have)
1724 def __add__(self, other):
1725 s = self.__class__(self)
1726 for (start, length) in other:
1727 s.add(start, length)
1730 def __sub__(self, other):
1731 s = self.__class__(self)
1732 for (start, length) in other:
1733 s.remove(start, length)
1736 def __iadd__(self, other):
1737 for (start, length) in other:
1738 self.add(start, length)
1741 def __isub__(self, other):
1742 for (start, length) in other:
1743 self.remove(start, length)
1746 def __and__(self, other):
1747 s = self.__class__()
1748 for i in other.each():
1753 def __contains__(self, (start,length)):
1754 for i in range(start, start+length):
1755 if i not in self._have:
1759 class ByteSpans(unittest.TestCase):
1760 def test_basic(self):
1762 self.failUnlessEqual(list(s), [])
1764 self.failIf((0,1) in s)
1765 self.failUnlessEqual(s.len(), 0)
1767 s1 = Spans(3, 4) # 3,4,5,6
1770 s1 = Spans(3L, 4L) # 3,4,5,6
1776 s2.add(10,2) # 10,11
1778 self.failUnless((10,1) in s2)
1779 self.failIf((10,1) in s1)
1780 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1781 self.failUnlessEqual(s2.len(), 6)
1783 s2.add(15,2).add(20,2)
1784 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1785 self.failUnlessEqual(s2.len(), 10)
1787 s2.remove(4,3).remove(15,1)
1788 self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1789 self.failUnlessEqual(s2.len(), 6)
1791 s1 = SimpleSpans(3, 4) # 3 4 5 6
1792 s2 = SimpleSpans(5, 4) # 5 6 7 8
1794 self.failUnlessEqual(list(i.each()), [5, 6])
1796 def _check1(self, s):
1797 self.failUnlessEqual(list(s), [(3,4)])
1799 self.failUnlessEqual(s.len(), 4)
1800 self.failIf((0,1) in s)
1801 self.failUnless((3,4) in s)
1802 self.failUnless((3,1) in s)
1803 self.failUnless((5,2) in s)
1804 self.failUnless((6,1) in s)
1805 self.failIf((6,2) in s)
1806 self.failIf((7,1) in s)
1807 self.failUnlessEqual(list(s.each()), [3,4,5,6])
1809 def test_large(self):
1810 s = Spans(4, 2**65) # don't do this with a SimpleSpans
1811 self.failUnlessEqual(list(s), [(4, 2**65)])
1813 self.failUnlessEqual(s.len(), 2**65)
1814 self.failIf((0,1) in s)
1815 self.failUnless((4,2) in s)
1816 self.failUnless((2**65,2) in s)
1818 def test_math(self):
1819 s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1820 s2 = Spans(5, 3) # 5,6,7
1821 s3 = Spans(8, 4) # 8,9,10,11
1824 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1826 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1828 self.failUnlessEqual(list(s.each()), [5,6,7])
1830 self.failUnlessEqual(list(s.each()), [5,6,7])
1832 self.failUnlessEqual(list(s.each()), [5,6,7])
1834 self.failUnlessEqual(list(s.each()), [8,9])
1836 self.failUnlessEqual(list(s.each()), [8,9])
1838 self.failUnlessEqual(list(s.each()), [])
1840 self.failUnlessEqual(list(s.each()), [])
1842 self.failUnlessEqual(list(s.each()), [])
1844 self.failUnlessEqual(list(s.each()), [])
1847 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1849 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1851 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1855 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1858 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1861 self.failUnlessEqual(list(s.each()), [5,6,7])
1865 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1868 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1871 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1873 def test_random(self):
1874 # attempt to increase coverage of corner cases by comparing behavior
1875 # of a simple-but-slow model implementation against the
1876 # complex-but-fast actual implementation, in a large number of random
1880 s1 = S1(); s2 = S2()
1882 def _create(subseed):
1883 ns1 = S1(); ns2 = S2()
1885 what = _hash(subseed+str(i)).hexdigest()
1886 start = int(what[2:4], 16)
1887 length = max(1,int(what[5:6], 16))
1888 ns1.add(start, length); ns2.add(start, length)
1892 for i in range(1000):
1893 what = _hash(seed+str(i)).hexdigest()
1896 start = int(what[2:4], 16)
1897 length = max(1,int(what[5:6], 16))
1900 if subop in "01234":
1901 s1 = S1(); s2 = S2()
1902 elif subop in "5678":
1903 s1 = S1(start, length); s2 = S2(start, length)
1905 s1 = S1(s1); s2 = S2(s2)
1906 #print "s2 = %s" % s2.dump()
1908 #print "s2.add(%d,%d)" % (start, length)
1909 s1.add(start, length); s2.add(start, length)
1911 #print "s2.remove(%d,%d)" % (start, length)
1912 s1.remove(start, length); s2.remove(start, length)
1914 ns1, ns2 = _create(what[7:11])
1915 #print "s2 + %s" % ns2.dump()
1916 s1 = s1 + ns1; s2 = s2 + ns2
1918 ns1, ns2 = _create(what[7:11])
1919 #print "%s - %s" % (s2.dump(), ns2.dump())
1920 s1 = s1 - ns1; s2 = s2 - ns2
1922 ns1, ns2 = _create(what[7:11])
1923 #print "s2 += %s" % ns2.dump()
1924 s1 += ns1; s2 += ns2
1926 ns1, ns2 = _create(what[7:11])
1927 #print "%s -= %s" % (s2.dump(), ns2.dump())
1928 s1 -= ns1; s2 -= ns2
1930 ns1, ns2 = _create(what[7:11])
1931 #print "%s &= %s" % (s2.dump(), ns2.dump())
1932 s1 = s1 & ns1; s2 = s2 & ns2
1933 #print "s2 now %s" % s2.dump()
1934 self.failUnlessEqual(list(s1.each()), list(s2.each()))
1935 self.failUnlessEqual(s1.len(), s2.len())
1936 self.failUnlessEqual(bool(s1), bool(s2))
1937 self.failUnlessEqual(list(s1), list(s2))
1939 what = _hash(what[12:14]+str(j)).hexdigest()
1940 start = int(what[2:4], 16)
1941 length = max(1, int(what[5:6], 16))
1942 span = (start, length)
1943 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1949 # s.add(start,length) : returns s
1950 # s.remove(start,length)
1951 # s.each() -> list of byte offsets, mostly for testing
1952 # list(s) -> list of (start,length) tuples, one per span
1953 # (start,length) in s -> True if (start..start+length-1) are all members
1954 # NOT equivalent to x in list(s)
1955 # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
1956 # bool(s) (__nonzeron__)
1957 # s = s1+s2, s1-s2, +=s1, -=s1
1959 def test_overlap(self):
1964 self._test_overlap(a,b,c,d)
1966 def _test_overlap(self, a, b, c, d):
1967 s1 = set(range(a,a+b))
1968 s2 = set(range(c,c+d))
1970 #self._show_overlap(s1, "1")
1971 #self._show_overlap(s2, "2")
1972 o = overlap(a,b,c,d)
1973 expected = s1.intersection(s2)
1975 self.failUnlessEqual(o, None)
1978 so = set(range(start,start+length))
1979 #self._show(so, "o")
1980 self.failUnlessEqual(so, expected)
1982 def _show_overlap(self, s, c):
1986 for i in range(max(s)):
1993 def extend(s, start, length, fill):
1994 if len(s) >= start+length:
1996 assert len(fill) == 1
1997 return s + fill*(start+length-len(s))
1999 def replace(s, start, data):
2000 assert len(s) >= start+len(data)
2001 return s[:start] + data + s[start+len(data):]
2003 class SimpleDataSpans:
2004 def __init__(self, other=None):
2005 self.missing = "" # "1" where missing, "0" where found
2008 for (start, data) in other.get_chunks():
2009 self.add(start, data)
2011 def __nonzero__(self): # this gets us bool()
2014 return len(self.missing.replace("1", ""))
2016 return [i for (i,c) in enumerate(self.missing) if c == "0"]
2017 def _have(self, start, length):
2018 m = self.missing[start:start+length]
2019 if not m or len(m)<length or int(m):
2022 def get_chunks(self):
2023 for i in self._dump():
2024 yield (i, self.data[i])
2025 def get_spans(self):
2026 return SimpleSpans([(start,len(data))
2027 for (start,data) in self.get_chunks()])
2028 def get(self, start, length):
2029 if self._have(start, length):
2030 return self.data[start:start+length]
2032 def pop(self, start, length):
2033 data = self.get(start, length)
2035 self.remove(start, length)
2037 def remove(self, start, length):
2038 self.missing = replace(extend(self.missing, start, length, "1"),
2040 def add(self, start, data):
2041 self.missing = replace(extend(self.missing, start, len(data), "1"),
2042 start, "0"*len(data))
2043 self.data = replace(extend(self.data, start, len(data), " "),
2047 class StringSpans(unittest.TestCase):
2048 def do_basic(self, klass):
2050 self.failUnlessEqual(ds.len(), 0)
2051 self.failUnlessEqual(list(ds._dump()), [])
2052 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
2054 self.failUnlessEqual(ds.get(0, 4), None)
2055 self.failUnlessEqual(ds.pop(0, 4), None)
2059 self.failUnlessEqual(ds.len(), 4)
2060 self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
2061 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2063 self.failUnless((2,2) in s1)
2064 self.failUnlessEqual(ds.get(0, 4), None)
2065 self.failUnlessEqual(ds.pop(0, 4), None)
2066 self.failUnlessEqual(ds.get(4, 4), None)
2069 self.failUnlessEqual(ds2.len(), 4)
2070 self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2071 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2072 self.failUnlessEqual(ds2.get(0, 4), None)
2073 self.failUnlessEqual(ds2.pop(0, 4), None)
2074 self.failUnlessEqual(ds2.pop(2, 3), "fou")
2075 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2076 self.failUnlessEqual(ds2.get(2, 3), None)
2077 self.failUnlessEqual(ds2.get(5, 1), "r")
2078 self.failUnlessEqual(ds.get(2, 3), "fou")
2079 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2082 self.failUnlessEqual(ds.len(), 6)
2083 self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2084 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2085 self.failUnlessEqual(ds.get(0, 4), "23fo")
2086 self.failUnlessEqual(ds.pop(0, 4), "23fo")
2087 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2088 self.failUnlessEqual(ds.get(0, 4), None)
2089 self.failUnlessEqual(ds.pop(0, 4), None)
2094 self.failUnlessEqual(ds.get(2, 4), "fear")
2099 self.failUnlessEqual(ds.get(2L, 4L), "fear")
2102 def do_scan(self, klass):
2103 # do a test with gaps and spans of size 1 and 2
2104 # left=(1,11) * right=(1,11) * gapsize=(1,2)
2105 # 111, 112, 121, 122, 211, 212, 221, 222
2114 # 11 1 1 11 11 11 1 1 111
2115 # 0123456789012345678901234567
2116 # abcdefghijklmnopqrstuvwxyz-=
2117 pieces = [(1, "bc"),
2127 p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2128 S = "abcdefghijklmnopqrstuvwxyz-="
2129 # TODO: when adding data, add capital letters, to make sure we aren't
2130 # just leaving the old data in place
2134 for start, data in pieces:
2139 d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2143 for start in range(0, l):
2144 for end in range(start+1, l):
2145 # add [start-end) to the baseline
2146 which = "%d-%d" % (start, end-1)
2147 p_added = set(range(start, end))
2151 print dump(b), which
2152 add = klass(); add.add(start, S[start:end])
2154 b.add(start, S[start:end])
2157 # check that the new span is there
2158 d = b.get(start, end-start)
2159 self.failUnlessEqual(d, S[start:end], which)
2160 # check that all the original pieces are still there
2161 for t_start, t_data in pieces:
2163 self.failUnlessEqual(b.get(t_start, t_len),
2164 S[t_start:t_start+t_len],
2165 "%s %d+%d" % (which, t_start, t_len))
2166 # check that a lot of subspans are mostly correct
2167 for t_start in range(l):
2168 for t_len in range(1,4):
2169 d = b.get(t_start, t_len)
2171 which2 = "%s+(%d-%d)" % (which, t_start,
2173 self.failUnlessEqual(d, S[t_start:t_start+t_len],
2175 # check that removing a subspan gives the right value
2177 b2.remove(t_start, t_len)
2178 removed = set(range(t_start, t_start+t_len))
2180 exp = (((i in p_elements) or (i in p_added))
2181 and (i not in removed))
2182 which2 = "%s-(%d-%d)" % (which, t_start,
2184 self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2187 def test_test(self):
2188 self.do_basic(SimpleDataSpans)
2189 self.do_scan(SimpleDataSpans)
2191 def test_basic(self):
2192 self.do_basic(DataSpans)
2193 self.do_scan(DataSpans)
2195 def test_random(self):
2196 # attempt to increase coverage of corner cases by comparing behavior
2197 # of a simple-but-slow model implementation against the
2198 # complex-but-fast actual implementation, in a large number of random
2200 S1 = SimpleDataSpans
2202 s1 = S1(); s2 = S2()
2204 def _randstr(length, seed):
2207 while created < length:
2208 piece = _hash(seed + str(created)).hexdigest()
2209 pieces.append(piece)
2210 created += len(piece)
2211 return "".join(pieces)[:length]
2212 def _create(subseed):
2213 ns1 = S1(); ns2 = S2()
2215 what = _hash(subseed+str(i)).hexdigest()
2216 start = int(what[2:4], 16)
2217 length = max(1,int(what[5:6], 16))
2218 ns1.add(start, _randstr(length, what[7:9]));
2219 ns2.add(start, _randstr(length, what[7:9]))
2223 for i in range(1000):
2224 what = _hash(seed+str(i)).hexdigest()
2227 start = int(what[2:4], 16)
2228 length = max(1,int(what[5:6], 16))
2231 if subop in "0123456":
2232 s1 = S1(); s2 = S2()
2234 s1, s2 = _create(what[7:11])
2235 #print "s2 = %s" % list(s2._dump())
2236 elif op in "123456":
2237 #print "s2.add(%d,%d)" % (start, length)
2238 s1.add(start, _randstr(length, what[7:9]));
2239 s2.add(start, _randstr(length, what[7:9]))
2240 elif op in "789abc":
2241 #print "s2.remove(%d,%d)" % (start, length)
2242 s1.remove(start, length); s2.remove(start, length)
2244 #print "s2.pop(%d,%d)" % (start, length)
2245 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2246 self.failUnlessEqual(d1, d2)
2247 #print "s1 now %s" % list(s1._dump())
2248 #print "s2 now %s" % list(s2._dump())
2249 self.failUnlessEqual(s1.len(), s2.len())
2250 self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2251 for j in range(100):
2252 what = _hash(what[12:14]+str(j)).hexdigest()
2253 start = int(what[2:4], 16)
2254 length = max(1, int(what[5:6], 16))
2255 d1 = s1.get(start, length); d2 = s2.get(start, length)
2256 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))