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):
543 def call_windows_getenv(name):
544 if name == u"HOMEDRIVE": return u"C:"
545 if name == u"HOMEPATH": return u"\\Documents and Settings\\\u0100"
546 self.fail("unexpected argument to call_windows_getenv")
547 self.patch(fileutil, 'windows_getenv', call_windows_getenv)
549 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
550 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~\\foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
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"a"), u"a")
553 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a~"), u"a~")
554 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a\\~\\foo"), u"a\\~\\foo")
556 def test_disk_stats(self):
557 avail = fileutil.get_available_space('.', 2**14)
559 raise unittest.SkipTest("This test will spuriously fail there is no disk space left.")
561 disk = fileutil.get_disk_stats('.', 2**13)
562 self.failUnless(disk['total'] > 0, disk['total'])
563 # we tolerate used==0 for a Travis-CI bug, see #2290
564 self.failUnless(disk['used'] >= 0, disk['used'])
565 self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
566 self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
567 self.failUnless(disk['avail'] > 0, disk['avail'])
569 def test_disk_stats_avail_nonnegative(self):
570 # This test will spuriously fail if you have more than 2^128
571 # bytes of available space on your filesystem.
572 disk = fileutil.get_disk_stats('.', 2**128)
573 self.failUnlessEqual(disk['avail'], 0)
575 class PollMixinTests(unittest.TestCase):
577 self.pm = pollmixin.PollMixin()
579 def test_PollMixin_True(self):
580 d = self.pm.poll(check_f=lambda : True,
584 def test_PollMixin_False_then_True(self):
585 i = iter([False, True])
586 d = self.pm.poll(check_f=i.next,
590 def test_timeout(self):
591 d = self.pm.poll(check_f=lambda: False,
595 self.fail("poll should have failed, not returned %s" % (res,))
597 f.trap(pollmixin.TimeoutError)
598 return None # success
599 d.addCallbacks(_suc, _err)
602 class DeferredUtilTests(unittest.TestCase, deferredutil.WaitForDelayedCallsMixin):
603 def test_gather_results(self):
604 d1 = defer.Deferred()
605 d2 = defer.Deferred()
606 res = deferredutil.gatherResults([d1, d2])
607 d1.errback(ValueError("BAD"))
609 self.fail("Should have errbacked, not resulted in %s" % (res,))
611 thef.trap(ValueError)
612 res.addCallbacks(_callb, _errb)
615 def test_success(self):
616 d1, d2 = defer.Deferred(), defer.Deferred()
619 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
620 dlss.addCallbacks(good.append, bad.append)
623 self.failUnlessEqual(good, [[1,2]])
624 self.failUnlessEqual(bad, [])
626 def test_failure(self):
627 d1, d2 = defer.Deferred(), defer.Deferred()
630 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
631 dlss.addCallbacks(good.append, bad.append)
632 d1.addErrback(lambda _ignore: None)
633 d2.addErrback(lambda _ignore: None)
635 d2.errback(ValueError())
636 self.failUnlessEqual(good, [])
637 self.failUnlessEqual(len(bad), 1)
639 self.failUnless(isinstance(f, Failure))
640 self.failUnless(f.check(ValueError))
642 def test_wait_for_delayed_calls(self):
644 This tests that 'wait_for_delayed_calls' does in fact wait for a
645 delayed call that is active when the test returns. If it didn't,
646 Trial would report an unclean reactor error for this test.
651 reactor.callLater(0.1, _trigger)
653 d = defer.succeed(None)
654 d.addBoth(self.wait_for_delayed_calls)
657 class HashUtilTests(unittest.TestCase):
659 def test_random_key(self):
660 k = hashutil.random_key()
661 self.failUnlessEqual(len(k), hashutil.KEYLEN)
663 def test_sha256d(self):
664 h1 = hashutil.tagged_hash("tag1", "value")
665 h2 = hashutil.tagged_hasher("tag1")
669 self.failUnlessEqual(h1, h2a)
670 self.failUnlessEqual(h2a, h2b)
672 def test_sha256d_truncated(self):
673 h1 = hashutil.tagged_hash("tag1", "value", 16)
674 h2 = hashutil.tagged_hasher("tag1", 16)
677 self.failUnlessEqual(len(h1), 16)
678 self.failUnlessEqual(len(h2), 16)
679 self.failUnlessEqual(h1, h2)
682 h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
683 h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
686 self.failUnlessEqual(h1, h2)
688 def test_hashers(self):
689 h1 = hashutil.block_hash("foo")
690 h2 = hashutil.block_hasher()
692 self.failUnlessEqual(h1, h2.digest())
694 h1 = hashutil.uri_extension_hash("foo")
695 h2 = hashutil.uri_extension_hasher()
697 self.failUnlessEqual(h1, h2.digest())
699 h1 = hashutil.plaintext_hash("foo")
700 h2 = hashutil.plaintext_hasher()
702 self.failUnlessEqual(h1, h2.digest())
704 h1 = hashutil.crypttext_hash("foo")
705 h2 = hashutil.crypttext_hasher()
707 self.failUnlessEqual(h1, h2.digest())
709 h1 = hashutil.crypttext_segment_hash("foo")
710 h2 = hashutil.crypttext_segment_hasher()
712 self.failUnlessEqual(h1, h2.digest())
714 h1 = hashutil.plaintext_segment_hash("foo")
715 h2 = hashutil.plaintext_segment_hasher()
717 self.failUnlessEqual(h1, h2.digest())
719 def test_timing_safe_compare(self):
720 self.failUnless(hashutil.timing_safe_compare("a", "a"))
721 self.failUnless(hashutil.timing_safe_compare("ab", "ab"))
722 self.failIf(hashutil.timing_safe_compare("a", "b"))
723 self.failIf(hashutil.timing_safe_compare("a", "aa"))
725 def _testknown(self, hashf, expected_a, *args):
727 got_a = base32.b2a(got)
728 self.failUnlessEqual(got_a, expected_a)
730 def test_known_answers(self):
731 # assert backwards compatibility
732 self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
733 self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
734 self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
735 self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
736 self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
737 self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
738 self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
739 self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
740 self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
741 self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
742 self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
743 self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
744 self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
745 self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
746 self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
747 self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
748 self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
749 self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
750 self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
751 self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
752 self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
753 self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
754 self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
757 class Abbreviate(unittest.TestCase):
759 a = abbreviate.abbreviate_time
760 self.failUnlessEqual(a(None), "unknown")
761 self.failUnlessEqual(a(0), "0 seconds")
762 self.failUnlessEqual(a(1), "1 second")
763 self.failUnlessEqual(a(2), "2 seconds")
764 self.failUnlessEqual(a(119), "119 seconds")
766 self.failUnlessEqual(a(2*MIN), "2 minutes")
767 self.failUnlessEqual(a(60*MIN), "60 minutes")
768 self.failUnlessEqual(a(179*MIN), "179 minutes")
770 self.failUnlessEqual(a(180*MIN), "3 hours")
771 self.failUnlessEqual(a(4*HOUR), "4 hours")
774 self.failUnlessEqual(a(2*DAY), "2 days")
775 self.failUnlessEqual(a(2*MONTH), "2 months")
777 self.failUnlessEqual(a(5*YEAR), "5 years")
779 def test_space(self):
780 tests_si = [(None, "unknown"),
787 (20*1000, "20.00 kB"),
788 (1024*1024, "1.05 MB"),
789 (1000*1000, "1.00 MB"),
790 (1000*1000*1000, "1.00 GB"),
791 (1000*1000*1000*1000, "1.00 TB"),
792 (1000*1000*1000*1000*1000, "1.00 PB"),
793 (1000*1000*1000*1000*1000*1000, "1.00 EB"),
794 (1234567890123456789, "1.23 EB"),
796 for (x, expected) in tests_si:
797 got = abbreviate.abbreviate_space(x, SI=True)
798 self.failUnlessEqual(got, expected)
800 tests_base1024 = [(None, "unknown"),
807 (20*1024, "20.00 kiB"),
808 (1000*1000, "976.56 kiB"),
809 (1024*1024, "1.00 MiB"),
810 (1024*1024*1024, "1.00 GiB"),
811 (1024*1024*1024*1024, "1.00 TiB"),
812 (1000*1000*1000*1000*1000, "909.49 TiB"),
813 (1024*1024*1024*1024*1024, "1.00 PiB"),
814 (1024*1024*1024*1024*1024*1024, "1.00 EiB"),
815 (1234567890123456789, "1.07 EiB"),
817 for (x, expected) in tests_base1024:
818 got = abbreviate.abbreviate_space(x, SI=False)
819 self.failUnlessEqual(got, expected)
821 self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
822 "(1.23 MB, 1.18 MiB)")
824 def test_parse_space(self):
825 p = abbreviate.parse_abbreviated_size
826 self.failUnlessEqual(p(""), None)
827 self.failUnlessEqual(p(None), None)
828 self.failUnlessEqual(p("123"), 123)
829 self.failUnlessEqual(p("123B"), 123)
830 self.failUnlessEqual(p("2K"), 2000)
831 self.failUnlessEqual(p("2kb"), 2000)
832 self.failUnlessEqual(p("2KiB"), 2048)
833 self.failUnlessEqual(p("10MB"), 10*1000*1000)
834 self.failUnlessEqual(p("10MiB"), 10*1024*1024)
835 self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
836 self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
837 self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
838 self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
839 self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
840 self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
841 self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
842 self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
844 e = self.failUnlessRaises(ValueError, p, "12 cubits")
845 self.failUnlessIn("12 cubits", str(e))
846 e = self.failUnlessRaises(ValueError, p, "1 BB")
847 self.failUnlessIn("1 BB", str(e))
848 e = self.failUnlessRaises(ValueError, p, "fhtagn")
849 self.failUnlessIn("fhtagn", str(e))
851 class Limiter(unittest.TestCase):
852 timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
854 def job(self, i, foo):
855 self.calls.append( (i, foo) )
856 self.simultaneous += 1
857 self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
860 self.simultaneous -= 1
861 d.callback("done %d" % i)
862 reactor.callLater(1.0, _done)
865 def bad_job(self, i, foo):
866 raise ValueError("bad_job %d" % i)
868 def test_limiter(self):
870 self.simultaneous = 0
871 self.peak_simultaneous = 0
872 l = limiter.ConcurrencyLimiter()
875 dl.append(l.add(self.job, i, foo=str(i)))
876 d = defer.DeferredList(dl, fireOnOneErrback=True)
878 self.failUnlessEqual(self.simultaneous, 0)
879 self.failUnless(self.peak_simultaneous <= 10)
880 self.failUnlessEqual(len(self.calls), 20)
882 self.failUnless( (i, str(i)) in self.calls)
886 def test_errors(self):
888 self.simultaneous = 0
889 self.peak_simultaneous = 0
890 l = limiter.ConcurrencyLimiter()
893 dl.append(l.add(self.job, i, foo=str(i)))
894 d2 = l.add(self.bad_job, 21, "21")
895 d = defer.DeferredList(dl, fireOnOneErrback=True)
898 for (success, result) in res:
899 self.failUnlessEqual(success, True)
900 results.append(result)
902 expected_results = ["done %d" % i for i in range(20)]
903 expected_results.sort()
904 self.failUnlessEqual(results, expected_results)
905 self.failUnless(self.peak_simultaneous <= 10)
906 self.failUnlessEqual(len(self.calls), 20)
908 self.failUnless( (i, str(i)) in self.calls)
910 self.fail("should have failed, not got %s" % (res,))
913 self.failUnless("bad_job 21" in str(f))
914 d2.addCallbacks(_good, _err)
916 d.addCallback(_most_done)
918 self.failUnlessEqual(self.simultaneous, 0)
919 self.failUnless(self.peak_simultaneous <= 10)
920 self.failUnlessEqual(len(self.calls), 20)
922 self.failUnless( (i, str(i)) in self.calls)
923 d.addCallback(_all_done)
926 class TimeFormat(unittest.TestCase):
927 def test_epoch(self):
928 return self._help_test_epoch()
930 def test_epoch_in_London(self):
931 # Europe/London is a particularly troublesome timezone. Nowadays, its
932 # offset from GMT is 0. But in 1970, its offset from GMT was 1.
933 # (Apparently in 1970 Britain had redefined standard time to be GMT+1
934 # and stayed in standard time all year round, whereas today
935 # Europe/London standard time is GMT and Europe/London Daylight
936 # Savings Time is GMT+1.) The current implementation of
937 # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
938 # Europe/London. (As soon as this unit test is done then I'll change
939 # that implementation to something that works even in this case...)
940 origtz = os.environ.get('TZ')
941 os.environ['TZ'] = "Europe/London"
942 if hasattr(time, 'tzset'):
945 return self._help_test_epoch()
950 os.environ['TZ'] = origtz
951 if hasattr(time, 'tzset'):
954 def _help_test_epoch(self):
955 origtzname = time.tzname
956 s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
957 self.failUnlessEqual(s, 1.0)
958 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
959 self.failUnlessEqual(s, 1.0)
960 s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
961 self.failUnlessEqual(s, 1.0)
963 self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
964 self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
965 "1970-01-01 00:00:01")
968 isostr = time_format.iso_utc(now)
969 timestamp = time_format.iso_utc_time_to_seconds(isostr)
970 self.failUnlessEqual(int(timestamp), int(now))
974 self.failUnlessEqual(time_format.iso_utc(t=my_time),
975 "1970-01-01_00:00:01")
976 e = self.failUnlessRaises(ValueError,
977 time_format.iso_utc_time_to_seconds,
978 "invalid timestring")
979 self.failUnless("not a complete ISO8601 timestamp" in str(e))
980 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
981 self.failUnlessEqual(s, 1.5)
983 # Look for daylight-savings-related errors.
984 thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
985 self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
986 self.failUnlessEqual(origtzname, time.tzname)
988 def test_iso_utc(self):
989 when = 1266760143.7841301
990 out = time_format.iso_utc_date(when)
991 self.failUnlessEqual(out, "2010-02-21")
992 out = time_format.iso_utc_date(t=lambda: when)
993 self.failUnlessEqual(out, "2010-02-21")
994 out = time_format.iso_utc(when)
995 self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
996 out = time_format.iso_utc(when, sep="-")
997 self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
999 def test_parse_duration(self):
1000 p = time_format.parse_duration
1002 self.failUnlessEqual(p("1 day"), DAY)
1003 self.failUnlessEqual(p("2 days"), 2*DAY)
1004 self.failUnlessEqual(p("3 months"), 3*31*DAY)
1005 self.failUnlessEqual(p("4 mo"), 4*31*DAY)
1006 self.failUnlessEqual(p("5 years"), 5*365*DAY)
1007 e = self.failUnlessRaises(ValueError, p, "123")
1008 self.failUnlessIn("no unit (like day, month, or year) in '123'",
1011 def test_parse_date(self):
1012 self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
1014 class CacheDir(unittest.TestCase):
1015 def test_basic(self):
1016 basedir = "test_util/CacheDir/test_basic"
1018 def _failIfExists(name):
1019 absfn = os.path.join(basedir, name)
1020 self.failIf(os.path.exists(absfn),
1021 "%s exists but it shouldn't" % absfn)
1023 def _failUnlessExists(name):
1024 absfn = os.path.join(basedir, name)
1025 self.failUnless(os.path.exists(absfn),
1026 "%s doesn't exist but it should" % absfn)
1028 cdm = cachedir.CacheDirectoryManager(basedir)
1029 a = cdm.get_file("a")
1030 b = cdm.get_file("b")
1031 c = cdm.get_file("c")
1032 f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
1033 f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
1034 f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
1036 _failUnlessExists("a")
1037 _failUnlessExists("b")
1038 _failUnlessExists("c")
1042 _failUnlessExists("a")
1043 _failUnlessExists("b")
1044 _failUnlessExists("c")
1047 # this file won't be deleted yet, because it isn't old enough
1049 _failUnlessExists("a")
1050 _failUnlessExists("b")
1051 _failUnlessExists("c")
1053 # we change the definition of "old" to make everything old
1058 _failUnlessExists("b")
1059 _failUnlessExists("c")
1067 _failUnlessExists("b")
1068 _failUnlessExists("c")
1070 b2 = cdm.get_file("b")
1074 _failUnlessExists("b")
1075 _failUnlessExists("c")
1080 def __init__(self, x):
1085 return "<%s %s>" % (self.__class__.__name__, self.x,)
1088 def __le__(self, other):
1089 return self.x <= other
1090 def __lt__(self, other):
1091 return self.x < other
1092 def __ge__(self, other):
1093 return self.x >= other
1094 def __gt__(self, other):
1095 return self.x > other
1096 def __ne__(self, other):
1097 return self.x != other
1098 def __eq__(self, other):
1099 return self.x == other
1101 class DictUtil(unittest.TestCase):
1102 def _help_test_empty_dict(self, klass):
1106 self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1107 self.failUnless(len(d1) == 0)
1108 self.failUnless(len(d2) == 0)
1110 def _help_test_nonempty_dict(self, klass):
1111 d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1112 d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1114 self.failUnless(d1 == d2)
1115 self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1116 self.failUnless(len(d2) == 3)
1118 def _help_test_eq_but_notis(self, klass):
1119 d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1124 d['b'] = EqButNotIs(3)
1129 d['b'] = EqButNotIs(3)
1135 d['a'] = EqButNotIs(3)
1140 fake3 = EqButNotIs(3)
1141 fake7 = EqButNotIs(7)
1145 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1146 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1147 # The real 7 should have been ejected by the d[3] = 8.
1148 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1149 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1150 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1155 fake3 = EqButNotIs(3)
1156 fake7 = EqButNotIs(7)
1159 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1160 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1161 # The real 7 should have been ejected by the d[3] = 8.
1162 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1163 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1164 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1168 self._help_test_eq_but_notis(dictutil.UtilDict)
1169 self._help_test_eq_but_notis(dictutil.NumDict)
1170 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1171 self._help_test_nonempty_dict(dictutil.UtilDict)
1172 self._help_test_nonempty_dict(dictutil.NumDict)
1173 self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1174 self._help_test_eq_but_notis(dictutil.UtilDict)
1175 self._help_test_eq_but_notis(dictutil.NumDict)
1176 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1178 def test_dict_of_sets(self):
1179 ds = dictutil.DictOfSets()
1184 self.failUnlessEqual(ds[1], set(["a"]))
1185 self.failUnlessEqual(ds[2], set(["b", "c"]))
1186 ds.discard(3, "d") # should not raise an exception
1188 self.failUnlessEqual(ds[2], set(["c"]))
1190 self.failIf(2 in ds)
1193 ds2 = dictutil.DictOfSets()
1198 self.failUnlessEqual(ds[1], set(["a"]))
1199 self.failUnlessEqual(ds[3], set(["f", "g"]))
1200 self.failUnlessEqual(ds[4], set(["h"]))
1202 def test_move(self):
1203 d1 = {1: "a", 2: "b"}
1204 d2 = {2: "c", 3: "d"}
1205 dictutil.move(1, d1, d2)
1206 self.failUnlessEqual(d1, {2: "b"})
1207 self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1209 d1 = {1: "a", 2: "b"}
1210 d2 = {2: "c", 3: "d"}
1211 dictutil.move(2, d1, d2)
1212 self.failUnlessEqual(d1, {1: "a"})
1213 self.failUnlessEqual(d2, {2: "b", 3: "d"})
1215 d1 = {1: "a", 2: "b"}
1216 d2 = {2: "c", 3: "d"}
1217 self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1219 def test_subtract(self):
1220 d1 = {1: "a", 2: "b"}
1221 d2 = {2: "c", 3: "d"}
1222 d3 = dictutil.subtract(d1, d2)
1223 self.failUnlessEqual(d3, {1: "a"})
1225 d1 = {1: "a", 2: "b"}
1227 d3 = dictutil.subtract(d1, d2)
1228 self.failUnlessEqual(d3, {1: "a"})
1230 def test_utildict(self):
1231 d = dictutil.UtilDict({1: "a", 2: "b"})
1234 self.failUnlessEqual(d, {2: "b"})
1237 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1239 d = dictutil.UtilDict({1: "b", 2: "a"})
1240 self.failUnlessEqual(d.items_sorted_by_value(),
1241 [(2, "a"), (1, "b")])
1242 self.failUnlessEqual(d.items_sorted_by_key(),
1243 [(1, "b"), (2, "a")])
1244 self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1245 self.failUnless(1 in d)
1247 d2 = dictutil.UtilDict({3: "c", 4: "d"})
1248 self.failUnless(d != d2)
1249 self.failUnless(d2 > d)
1250 self.failUnless(d2 >= d)
1251 self.failUnless(d <= d2)
1252 self.failUnless(d < d2)
1253 self.failUnlessEqual(d[1], "b")
1254 self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1257 self.failUnlessEqual(d, d3)
1258 self.failUnless(isinstance(d3, dictutil.UtilDict))
1260 d4 = d.fromkeys([3,4], "e")
1261 self.failUnlessEqual(d4, {3: "e", 4: "e"})
1263 self.failUnlessEqual(d.get(1), "b")
1264 self.failUnlessEqual(d.get(3), None)
1265 self.failUnlessEqual(d.get(3, "default"), "default")
1266 self.failUnlessEqual(sorted(list(d.items())),
1267 [(1, "b"), (2, "a")])
1268 self.failUnlessEqual(sorted(list(d.iteritems())),
1269 [(1, "b"), (2, "a")])
1270 self.failUnlessEqual(sorted(d.keys()), [1, 2])
1271 self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1272 x = d.setdefault(1, "new")
1273 self.failUnlessEqual(x, "b")
1274 self.failUnlessEqual(d[1], "b")
1275 x = d.setdefault(3, "new")
1276 self.failUnlessEqual(x, "new")
1277 self.failUnlessEqual(d[3], "new")
1281 self.failUnless(x in [(1, "b"), (2, "a")])
1283 self.failUnless(x in [(1, "b"), (2, "a")])
1284 self.failUnlessRaises(KeyError, d.popitem)
1286 def test_numdict(self):
1287 d = dictutil.NumDict({"a": 1, "b": 2})
1289 d.add_num("a", 10, 5)
1290 d.add_num("c", 20, 5)
1292 self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1294 d.subtract_num("a", 10)
1295 d.subtract_num("e", 10)
1296 d.subtract_num("f", 10, 15)
1297 self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1300 self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1302 d = dictutil.NumDict()
1306 self.failUnlessEqual(d, {"a": 2, "b": 6})
1310 self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1311 self.failUnlessEqual(d.items_sorted_by_key(),
1312 [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1313 self.failUnlessEqual(d.items_sorted_by_value(),
1314 [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1315 self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1317 d = dictutil.NumDict({"a": 1, "b": 2})
1318 self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1319 self.failUnless("a" in d)
1321 d2 = dictutil.NumDict({"c": 3, "d": 4})
1322 self.failUnless(d != d2)
1323 self.failUnless(d2 > d)
1324 self.failUnless(d2 >= d)
1325 self.failUnless(d <= d2)
1326 self.failUnless(d < d2)
1327 self.failUnlessEqual(d["a"], 1)
1328 self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1331 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1334 self.failUnlessEqual(d, d3)
1335 self.failUnless(isinstance(d3, dictutil.NumDict))
1337 d4 = d.fromkeys(["a","b"], 5)
1338 self.failUnlessEqual(d4, {"a": 5, "b": 5})
1340 self.failUnlessEqual(d.get("a"), 1)
1341 self.failUnlessEqual(d.get("c"), 0)
1342 self.failUnlessEqual(d.get("c", 5), 5)
1343 self.failUnlessEqual(sorted(list(d.items())),
1344 [("a", 1), ("b", 2)])
1345 self.failUnlessEqual(sorted(list(d.iteritems())),
1346 [("a", 1), ("b", 2)])
1347 self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1348 self.failUnlessEqual(sorted(d.values()), [1, 2])
1349 self.failUnless(d.has_key("a"))
1350 self.failIf(d.has_key("c"))
1352 x = d.setdefault("c", 3)
1353 self.failUnlessEqual(x, 3)
1354 self.failUnlessEqual(d["c"], 3)
1355 x = d.setdefault("c", 5)
1356 self.failUnlessEqual(x, 3)
1357 self.failUnlessEqual(d["c"], 3)
1361 self.failUnless(x in [("a", 1), ("b", 2)])
1363 self.failUnless(x in [("a", 1), ("b", 2)])
1364 self.failUnlessRaises(KeyError, d.popitem)
1367 d.update({"c": 4, "d": 5})
1368 self.failUnlessEqual(d, {"c": 4, "d": 5})
1370 def test_del_if_present(self):
1371 d = {1: "a", 2: "b"}
1372 dictutil.del_if_present(d, 1)
1373 dictutil.del_if_present(d, 3)
1374 self.failUnlessEqual(d, {2: "b"})
1376 def test_valueordereddict(self):
1377 d = dictutil.ValueOrderedDict()
1382 self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1383 self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1384 self.failUnlessEqual(d.values(), [1, 2, 3])
1385 self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1386 self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1389 self.failIf(d == {"a": 4})
1390 self.failUnless(d != {"a": 4})
1392 x = d.setdefault("d", 0)
1393 self.failUnlessEqual(x, 0)
1394 self.failUnlessEqual(d["d"], 0)
1395 x = d.setdefault("d", -1)
1396 self.failUnlessEqual(x, 0)
1397 self.failUnlessEqual(d["d"], 0)
1399 x = d.remove("e", "default", False)
1400 self.failUnlessEqual(x, "default")
1401 self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1402 x = d.remove("d", 5)
1403 self.failUnlessEqual(x, 0)
1405 x = d.__getitem__("c")
1406 self.failUnlessEqual(x, 1)
1407 x = d.__getitem__("e", "default", False)
1408 self.failUnlessEqual(x, "default")
1409 self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1411 self.failUnlessEqual(d.popitem(), ("c", 1))
1412 self.failUnlessEqual(d.popitem(), ("b", 2))
1413 self.failUnlessEqual(d.popitem(), ("a", 3))
1414 self.failUnlessRaises(KeyError, d.popitem)
1416 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1417 x = d.pop("d", "default", False)
1418 self.failUnlessEqual(x, "default")
1419 self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1421 self.failUnlessEqual(x, 2)
1422 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1424 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1425 x = d.pop_from_list(1) # pop the second item, b/2
1426 self.failUnlessEqual(x, "b")
1427 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1429 def test_auxdict(self):
1430 d = dictutil.AuxValueDict()
1431 # we put the serialized form in the auxdata
1432 d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1434 self.failUnlessEqual(d.keys(), ["key"])
1435 self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1436 self.failUnlessEqual(d.get_aux("key"), "serialized")
1437 def _get_missing(key):
1439 self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1440 self.failUnlessEqual(d.get("nonkey"), None)
1441 self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1442 self.failUnlessEqual(d.get_aux("nonkey"), None)
1443 self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1445 d["key"] = ("filecap2", "metadata2")
1446 self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1447 self.failUnlessEqual(d.get_aux("key"), None)
1449 d.set_with_aux("key2", "value2", "aux2")
1450 self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1452 self.failUnlessEqual(d.keys(), ["key"])
1453 self.failIf("key2" in d)
1454 self.failUnlessRaises(KeyError, _get_missing, "key2")
1455 self.failUnlessEqual(d.get("key2"), None)
1456 self.failUnlessEqual(d.get_aux("key2"), None)
1457 d["key2"] = "newvalue2"
1458 self.failUnlessEqual(d.get("key2"), "newvalue2")
1459 self.failUnlessEqual(d.get_aux("key2"), None)
1461 d = dictutil.AuxValueDict({1:2,3:4})
1462 self.failUnlessEqual(sorted(d.keys()), [1,3])
1463 self.failUnlessEqual(d[1], 2)
1464 self.failUnlessEqual(d.get_aux(1), None)
1466 d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1467 self.failUnlessEqual(sorted(d.keys()), [1,3])
1468 self.failUnlessEqual(d[1], 2)
1469 self.failUnlessEqual(d.get_aux(1), None)
1471 d = dictutil.AuxValueDict(one=1, two=2)
1472 self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1473 self.failUnlessEqual(d["one"], 1)
1474 self.failUnlessEqual(d.get_aux("one"), None)
1476 class Pipeline(unittest.TestCase):
1477 def pause(self, *args, **kwargs):
1478 d = defer.Deferred()
1479 self.calls.append( (d, args, kwargs) )
1482 def failUnlessCallsAre(self, expected):
1485 self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1486 for i,c in enumerate(self.calls):
1487 self.failUnlessEqual(c[1:], expected[i], str(i))
1489 def test_basic(self):
1492 p = pipeline.Pipeline(100)
1494 d = p.flush() # fires immediately
1495 d.addCallbacks(finished.append, log.err)
1496 self.failUnlessEqual(len(finished), 1)
1499 d = p.add(10, self.pause, "one")
1500 # the call should start right away, and our return Deferred should
1502 d.addCallbacks(finished.append, log.err)
1503 self.failUnlessEqual(len(finished), 1)
1504 self.failUnlessEqual(finished[0], None)
1505 self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1506 self.failUnlessEqual(p.gauge, 10)
1511 d = p.add(20, self.pause, "two", kw=2)
1512 # pipeline: [one, two]
1514 # the call and the Deferred should fire right away
1515 d.addCallbacks(finished.append, log.err)
1516 self.failUnlessEqual(len(finished), 1)
1517 self.failUnlessEqual(finished[0], None)
1518 self.failUnlessCallsAre([ ( ("one",) , {} ),
1519 ( ("two",) , {"kw": 2} ),
1521 self.failUnlessEqual(p.gauge, 30)
1523 self.calls[0][0].callback("one-result")
1525 self.failUnlessEqual(p.gauge, 20)
1528 d = p.add(90, self.pause, "three", "posarg1")
1529 # pipeline: [two, three]
1532 fd.addCallbacks(flushed.append, log.err)
1533 self.failUnlessEqual(flushed, [])
1535 # the call will be made right away, but the return Deferred will not,
1536 # because the pipeline is now full.
1537 d.addCallbacks(finished.append, log.err)
1538 self.failUnlessEqual(len(finished), 0)
1539 self.failUnlessCallsAre([ ( ("one",) , {} ),
1540 ( ("two",) , {"kw": 2} ),
1541 ( ("three", "posarg1"), {} ),
1543 self.failUnlessEqual(p.gauge, 110)
1545 self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1547 # retiring either call will unblock the pipeline, causing the #3
1549 self.calls[2][0].callback("three-result")
1552 self.failUnlessEqual(len(finished), 1)
1553 self.failUnlessEqual(finished[0], None)
1554 self.failUnlessEqual(flushed, [])
1556 # retiring call#2 will finally allow the flush() Deferred to fire
1557 self.calls[1][0].callback("two-result")
1558 self.failUnlessEqual(len(flushed), 1)
1560 def test_errors(self):
1562 p = pipeline.Pipeline(100)
1564 d1 = p.add(200, self.pause, "one")
1568 d1.addBoth(finished.append)
1569 self.failUnlessEqual(finished, [])
1572 d2.addBoth(flushed.append)
1573 self.failUnlessEqual(flushed, [])
1575 self.calls[0][0].errback(ValueError("oops"))
1577 self.failUnlessEqual(len(finished), 1)
1579 self.failUnless(isinstance(f, Failure))
1580 self.failUnless(f.check(pipeline.PipelineError))
1581 self.failUnlessIn("PipelineError", str(f.value))
1582 self.failUnlessIn("ValueError", str(f.value))
1584 self.failUnless("ValueError" in r, r)
1586 self.failUnless(f2.check(ValueError))
1588 self.failUnlessEqual(len(flushed), 1)
1590 self.failUnless(isinstance(f, Failure))
1591 self.failUnless(f.check(pipeline.PipelineError))
1593 self.failUnless(f2.check(ValueError))
1595 # now that the pipeline is in the failed state, any new calls will
1598 d3 = p.add(20, self.pause, "two")
1601 d3.addBoth(finished.append)
1602 self.failUnlessEqual(len(finished), 1)
1604 self.failUnless(isinstance(f, Failure))
1605 self.failUnless(f.check(pipeline.PipelineError))
1607 self.failUnless("ValueError" in r, r)
1609 self.failUnless(f2.check(ValueError))
1613 d4.addBoth(flushed.append)
1614 self.failUnlessEqual(len(flushed), 1)
1616 self.failUnless(isinstance(f, Failure))
1617 self.failUnless(f.check(pipeline.PipelineError))
1619 self.failUnless(f2.check(ValueError))
1621 def test_errors2(self):
1623 p = pipeline.Pipeline(100)
1625 d1 = p.add(10, self.pause, "one")
1626 d2 = p.add(20, self.pause, "two")
1627 d3 = p.add(30, self.pause, "three")
1630 # one call fails, then the second one succeeds: make sure
1631 # ExpandableDeferredList tolerates the second one
1634 d4.addBoth(flushed.append)
1635 self.failUnlessEqual(flushed, [])
1637 self.calls[0][0].errback(ValueError("oops"))
1638 self.failUnlessEqual(len(flushed), 1)
1640 self.failUnless(isinstance(f, Failure))
1641 self.failUnless(f.check(pipeline.PipelineError))
1643 self.failUnless(f2.check(ValueError))
1645 self.calls[1][0].callback("two-result")
1646 self.calls[2][0].errback(ValueError("three-error"))
1650 class SampleError(Exception):
1653 class Log(unittest.TestCase):
1655 if not hasattr(self, "flushLoggedErrors"):
1656 # without flushLoggedErrors, we can't get rid of the
1657 # twisted.log.err that tahoe_log records, so we can't keep this
1658 # test from [ERROR]ing
1659 raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1661 raise SampleError("simple sample")
1664 tahoe_log.err(format="intentional sample error",
1665 failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1666 self.flushLoggedErrors(SampleError)
1670 # this is a simple+inefficient form of util.spans.Spans . We compare the
1671 # behavior of this reference model against the real (efficient) form.
1673 def __init__(self, _span_or_start=None, length=None):
1675 if length is not None:
1676 for i in range(_span_or_start, _span_or_start+length):
1678 elif _span_or_start:
1679 for (start,length) in _span_or_start:
1680 self.add(start, length)
1682 def add(self, start, length):
1683 for i in range(start, start+length):
1687 def remove(self, start, length):
1688 for i in range(start, start+length):
1689 self._have.discard(i)
1693 return sorted(self._have)
1696 items = sorted(self._have)
1700 if prevstart is None:
1701 prevstart = prevend = i
1706 yield (prevstart, prevend-prevstart+1)
1707 prevstart = prevend = i
1708 if prevstart is not None:
1709 yield (prevstart, prevend-prevstart+1)
1711 def __nonzero__(self): # this gets us bool()
1715 return len(self._have)
1717 def __add__(self, other):
1718 s = self.__class__(self)
1719 for (start, length) in other:
1720 s.add(start, length)
1723 def __sub__(self, other):
1724 s = self.__class__(self)
1725 for (start, length) in other:
1726 s.remove(start, length)
1729 def __iadd__(self, other):
1730 for (start, length) in other:
1731 self.add(start, length)
1734 def __isub__(self, other):
1735 for (start, length) in other:
1736 self.remove(start, length)
1739 def __and__(self, other):
1740 s = self.__class__()
1741 for i in other.each():
1746 def __contains__(self, (start,length)):
1747 for i in range(start, start+length):
1748 if i not in self._have:
1752 class ByteSpans(unittest.TestCase):
1753 def test_basic(self):
1755 self.failUnlessEqual(list(s), [])
1757 self.failIf((0,1) in s)
1758 self.failUnlessEqual(s.len(), 0)
1760 s1 = Spans(3, 4) # 3,4,5,6
1763 s1 = Spans(3L, 4L) # 3,4,5,6
1769 s2.add(10,2) # 10,11
1771 self.failUnless((10,1) in s2)
1772 self.failIf((10,1) in s1)
1773 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1774 self.failUnlessEqual(s2.len(), 6)
1776 s2.add(15,2).add(20,2)
1777 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1778 self.failUnlessEqual(s2.len(), 10)
1780 s2.remove(4,3).remove(15,1)
1781 self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1782 self.failUnlessEqual(s2.len(), 6)
1784 s1 = SimpleSpans(3, 4) # 3 4 5 6
1785 s2 = SimpleSpans(5, 4) # 5 6 7 8
1787 self.failUnlessEqual(list(i.each()), [5, 6])
1789 def _check1(self, s):
1790 self.failUnlessEqual(list(s), [(3,4)])
1792 self.failUnlessEqual(s.len(), 4)
1793 self.failIf((0,1) in s)
1794 self.failUnless((3,4) in s)
1795 self.failUnless((3,1) in s)
1796 self.failUnless((5,2) in s)
1797 self.failUnless((6,1) in s)
1798 self.failIf((6,2) in s)
1799 self.failIf((7,1) in s)
1800 self.failUnlessEqual(list(s.each()), [3,4,5,6])
1802 def test_large(self):
1803 s = Spans(4, 2**65) # don't do this with a SimpleSpans
1804 self.failUnlessEqual(list(s), [(4, 2**65)])
1806 self.failUnlessEqual(s.len(), 2**65)
1807 self.failIf((0,1) in s)
1808 self.failUnless((4,2) in s)
1809 self.failUnless((2**65,2) in s)
1811 def test_math(self):
1812 s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1813 s2 = Spans(5, 3) # 5,6,7
1814 s3 = Spans(8, 4) # 8,9,10,11
1817 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1819 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1821 self.failUnlessEqual(list(s.each()), [5,6,7])
1823 self.failUnlessEqual(list(s.each()), [5,6,7])
1825 self.failUnlessEqual(list(s.each()), [5,6,7])
1827 self.failUnlessEqual(list(s.each()), [8,9])
1829 self.failUnlessEqual(list(s.each()), [8,9])
1831 self.failUnlessEqual(list(s.each()), [])
1833 self.failUnlessEqual(list(s.each()), [])
1835 self.failUnlessEqual(list(s.each()), [])
1837 self.failUnlessEqual(list(s.each()), [])
1840 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1842 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1844 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1848 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1851 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1854 self.failUnlessEqual(list(s.each()), [5,6,7])
1858 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1861 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1864 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1866 def test_random(self):
1867 # attempt to increase coverage of corner cases by comparing behavior
1868 # of a simple-but-slow model implementation against the
1869 # complex-but-fast actual implementation, in a large number of random
1873 s1 = S1(); s2 = S2()
1875 def _create(subseed):
1876 ns1 = S1(); ns2 = S2()
1878 what = _hash(subseed+str(i)).hexdigest()
1879 start = int(what[2:4], 16)
1880 length = max(1,int(what[5:6], 16))
1881 ns1.add(start, length); ns2.add(start, length)
1885 for i in range(1000):
1886 what = _hash(seed+str(i)).hexdigest()
1889 start = int(what[2:4], 16)
1890 length = max(1,int(what[5:6], 16))
1893 if subop in "01234":
1894 s1 = S1(); s2 = S2()
1895 elif subop in "5678":
1896 s1 = S1(start, length); s2 = S2(start, length)
1898 s1 = S1(s1); s2 = S2(s2)
1899 #print "s2 = %s" % s2.dump()
1901 #print "s2.add(%d,%d)" % (start, length)
1902 s1.add(start, length); s2.add(start, length)
1904 #print "s2.remove(%d,%d)" % (start, length)
1905 s1.remove(start, length); s2.remove(start, length)
1907 ns1, ns2 = _create(what[7:11])
1908 #print "s2 + %s" % ns2.dump()
1909 s1 = s1 + ns1; s2 = s2 + ns2
1911 ns1, ns2 = _create(what[7:11])
1912 #print "%s - %s" % (s2.dump(), ns2.dump())
1913 s1 = s1 - ns1; s2 = s2 - ns2
1915 ns1, ns2 = _create(what[7:11])
1916 #print "s2 += %s" % ns2.dump()
1917 s1 += ns1; s2 += ns2
1919 ns1, ns2 = _create(what[7:11])
1920 #print "%s -= %s" % (s2.dump(), ns2.dump())
1921 s1 -= ns1; s2 -= ns2
1923 ns1, ns2 = _create(what[7:11])
1924 #print "%s &= %s" % (s2.dump(), ns2.dump())
1925 s1 = s1 & ns1; s2 = s2 & ns2
1926 #print "s2 now %s" % s2.dump()
1927 self.failUnlessEqual(list(s1.each()), list(s2.each()))
1928 self.failUnlessEqual(s1.len(), s2.len())
1929 self.failUnlessEqual(bool(s1), bool(s2))
1930 self.failUnlessEqual(list(s1), list(s2))
1932 what = _hash(what[12:14]+str(j)).hexdigest()
1933 start = int(what[2:4], 16)
1934 length = max(1, int(what[5:6], 16))
1935 span = (start, length)
1936 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1942 # s.add(start,length) : returns s
1943 # s.remove(start,length)
1944 # s.each() -> list of byte offsets, mostly for testing
1945 # list(s) -> list of (start,length) tuples, one per span
1946 # (start,length) in s -> True if (start..start+length-1) are all members
1947 # NOT equivalent to x in list(s)
1948 # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
1949 # bool(s) (__nonzeron__)
1950 # s = s1+s2, s1-s2, +=s1, -=s1
1952 def test_overlap(self):
1957 self._test_overlap(a,b,c,d)
1959 def _test_overlap(self, a, b, c, d):
1960 s1 = set(range(a,a+b))
1961 s2 = set(range(c,c+d))
1963 #self._show_overlap(s1, "1")
1964 #self._show_overlap(s2, "2")
1965 o = overlap(a,b,c,d)
1966 expected = s1.intersection(s2)
1968 self.failUnlessEqual(o, None)
1971 so = set(range(start,start+length))
1972 #self._show(so, "o")
1973 self.failUnlessEqual(so, expected)
1975 def _show_overlap(self, s, c):
1979 for i in range(max(s)):
1986 def extend(s, start, length, fill):
1987 if len(s) >= start+length:
1989 assert len(fill) == 1
1990 return s + fill*(start+length-len(s))
1992 def replace(s, start, data):
1993 assert len(s) >= start+len(data)
1994 return s[:start] + data + s[start+len(data):]
1996 class SimpleDataSpans:
1997 def __init__(self, other=None):
1998 self.missing = "" # "1" where missing, "0" where found
2001 for (start, data) in other.get_chunks():
2002 self.add(start, data)
2004 def __nonzero__(self): # this gets us bool()
2007 return len(self.missing.replace("1", ""))
2009 return [i for (i,c) in enumerate(self.missing) if c == "0"]
2010 def _have(self, start, length):
2011 m = self.missing[start:start+length]
2012 if not m or len(m)<length or int(m):
2015 def get_chunks(self):
2016 for i in self._dump():
2017 yield (i, self.data[i])
2018 def get_spans(self):
2019 return SimpleSpans([(start,len(data))
2020 for (start,data) in self.get_chunks()])
2021 def get(self, start, length):
2022 if self._have(start, length):
2023 return self.data[start:start+length]
2025 def pop(self, start, length):
2026 data = self.get(start, length)
2028 self.remove(start, length)
2030 def remove(self, start, length):
2031 self.missing = replace(extend(self.missing, start, length, "1"),
2033 def add(self, start, data):
2034 self.missing = replace(extend(self.missing, start, len(data), "1"),
2035 start, "0"*len(data))
2036 self.data = replace(extend(self.data, start, len(data), " "),
2040 class StringSpans(unittest.TestCase):
2041 def do_basic(self, klass):
2043 self.failUnlessEqual(ds.len(), 0)
2044 self.failUnlessEqual(list(ds._dump()), [])
2045 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
2047 self.failUnlessEqual(ds.get(0, 4), None)
2048 self.failUnlessEqual(ds.pop(0, 4), None)
2052 self.failUnlessEqual(ds.len(), 4)
2053 self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
2054 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2056 self.failUnless((2,2) in s1)
2057 self.failUnlessEqual(ds.get(0, 4), None)
2058 self.failUnlessEqual(ds.pop(0, 4), None)
2059 self.failUnlessEqual(ds.get(4, 4), None)
2062 self.failUnlessEqual(ds2.len(), 4)
2063 self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2064 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2065 self.failUnlessEqual(ds2.get(0, 4), None)
2066 self.failUnlessEqual(ds2.pop(0, 4), None)
2067 self.failUnlessEqual(ds2.pop(2, 3), "fou")
2068 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2069 self.failUnlessEqual(ds2.get(2, 3), None)
2070 self.failUnlessEqual(ds2.get(5, 1), "r")
2071 self.failUnlessEqual(ds.get(2, 3), "fou")
2072 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2075 self.failUnlessEqual(ds.len(), 6)
2076 self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2077 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2078 self.failUnlessEqual(ds.get(0, 4), "23fo")
2079 self.failUnlessEqual(ds.pop(0, 4), "23fo")
2080 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2081 self.failUnlessEqual(ds.get(0, 4), None)
2082 self.failUnlessEqual(ds.pop(0, 4), None)
2087 self.failUnlessEqual(ds.get(2, 4), "fear")
2092 self.failUnlessEqual(ds.get(2L, 4L), "fear")
2095 def do_scan(self, klass):
2096 # do a test with gaps and spans of size 1 and 2
2097 # left=(1,11) * right=(1,11) * gapsize=(1,2)
2098 # 111, 112, 121, 122, 211, 212, 221, 222
2107 # 11 1 1 11 11 11 1 1 111
2108 # 0123456789012345678901234567
2109 # abcdefghijklmnopqrstuvwxyz-=
2110 pieces = [(1, "bc"),
2120 p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2121 S = "abcdefghijklmnopqrstuvwxyz-="
2122 # TODO: when adding data, add capital letters, to make sure we aren't
2123 # just leaving the old data in place
2127 for start, data in pieces:
2132 d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2136 for start in range(0, l):
2137 for end in range(start+1, l):
2138 # add [start-end) to the baseline
2139 which = "%d-%d" % (start, end-1)
2140 p_added = set(range(start, end))
2144 print dump(b), which
2145 add = klass(); add.add(start, S[start:end])
2147 b.add(start, S[start:end])
2150 # check that the new span is there
2151 d = b.get(start, end-start)
2152 self.failUnlessEqual(d, S[start:end], which)
2153 # check that all the original pieces are still there
2154 for t_start, t_data in pieces:
2156 self.failUnlessEqual(b.get(t_start, t_len),
2157 S[t_start:t_start+t_len],
2158 "%s %d+%d" % (which, t_start, t_len))
2159 # check that a lot of subspans are mostly correct
2160 for t_start in range(l):
2161 for t_len in range(1,4):
2162 d = b.get(t_start, t_len)
2164 which2 = "%s+(%d-%d)" % (which, t_start,
2166 self.failUnlessEqual(d, S[t_start:t_start+t_len],
2168 # check that removing a subspan gives the right value
2170 b2.remove(t_start, t_len)
2171 removed = set(range(t_start, t_start+t_len))
2173 exp = (((i in p_elements) or (i in p_added))
2174 and (i not in removed))
2175 which2 = "%s-(%d-%d)" % (which, t_start,
2177 self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2180 def test_test(self):
2181 self.do_basic(SimpleDataSpans)
2182 self.do_scan(SimpleDataSpans)
2184 def test_basic(self):
2185 self.do_basic(DataSpans)
2186 self.do_scan(DataSpans)
2188 def test_random(self):
2189 # attempt to increase coverage of corner cases by comparing behavior
2190 # of a simple-but-slow model implementation against the
2191 # complex-but-fast actual implementation, in a large number of random
2193 S1 = SimpleDataSpans
2195 s1 = S1(); s2 = S2()
2197 def _randstr(length, seed):
2200 while created < length:
2201 piece = _hash(seed + str(created)).hexdigest()
2202 pieces.append(piece)
2203 created += len(piece)
2204 return "".join(pieces)[:length]
2205 def _create(subseed):
2206 ns1 = S1(); ns2 = S2()
2208 what = _hash(subseed+str(i)).hexdigest()
2209 start = int(what[2:4], 16)
2210 length = max(1,int(what[5:6], 16))
2211 ns1.add(start, _randstr(length, what[7:9]));
2212 ns2.add(start, _randstr(length, what[7:9]))
2216 for i in range(1000):
2217 what = _hash(seed+str(i)).hexdigest()
2220 start = int(what[2:4], 16)
2221 length = max(1,int(what[5:6], 16))
2224 if subop in "0123456":
2225 s1 = S1(); s2 = S2()
2227 s1, s2 = _create(what[7:11])
2228 #print "s2 = %s" % list(s2._dump())
2229 elif op in "123456":
2230 #print "s2.add(%d,%d)" % (start, length)
2231 s1.add(start, _randstr(length, what[7:9]));
2232 s2.add(start, _randstr(length, what[7:9]))
2233 elif op in "789abc":
2234 #print "s2.remove(%d,%d)" % (start, length)
2235 s1.remove(start, length); s2.remove(start, length)
2237 #print "s2.pop(%d,%d)" % (start, length)
2238 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2239 self.failUnlessEqual(d1, d2)
2240 #print "s1 now %s" % list(s1._dump())
2241 #print "s2 now %s" % list(s2._dump())
2242 self.failUnlessEqual(s1.len(), s2.len())
2243 self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2244 for j in range(100):
2245 what = _hash(what[12:14]+str(j)).hexdigest()
2246 start = int(what[2:4], 16)
2247 length = max(1, int(what[5:6], 16))
2248 d1 = s1.get(start, length); d2 = s2.get(start, length)
2249 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))