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_rename(self):
435 basedir = "util/FileUtil/test_rename"
436 fileutil.make_dirs(basedir)
437 self.touch(basedir, "here")
438 fn = os.path.join(basedir, "here")
439 fn2 = os.path.join(basedir, "there")
440 fileutil.rename(fn, fn2)
441 self.failIf(os.path.exists(fn))
442 self.failUnless(os.path.exists(fn2))
445 basedir = "util/FileUtil/test_du"
446 fileutil.make_dirs(basedir)
447 d = os.path.join(basedir, "space-consuming")
449 self.touch(d, "a/b/1.txt", data="a"*10)
450 self.touch(d, "a/b/2.txt", data="b"*11)
452 self.touch(d, "a/c/1.txt", data="c"*12)
453 self.touch(d, "a/c/2.txt", data="d"*13)
455 used = fileutil.du(basedir)
456 self.failUnlessEqual(10+11+12+13, used)
458 def test_abspath_expanduser_unicode(self):
459 self.failUnlessRaises(AssertionError, fileutil.abspath_expanduser_unicode, "bytestring")
461 saved_cwd = os.path.normpath(os.getcwdu())
462 abspath_cwd = fileutil.abspath_expanduser_unicode(u".")
463 self.failUnless(isinstance(saved_cwd, unicode), saved_cwd)
464 self.failUnless(isinstance(abspath_cwd, unicode), abspath_cwd)
465 if sys.platform == "win32":
466 self.failUnlessReallyEqual(abspath_cwd, fileutil.to_windows_long_path(saved_cwd))
468 self.failUnlessReallyEqual(abspath_cwd, saved_cwd)
470 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\?\\foo"), u"\\\\?\\foo")
471 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\.\\foo"), u"\\\\.\\foo")
472 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\server\\foo"), u"\\\\?\\UNC\\server\\foo")
473 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo"), u"\\\\?\\C:\\foo")
474 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo/bar"), u"\\\\?\\C:\\foo\\bar")
476 # adapted from <http://svn.python.org/view/python/branches/release26-maint/Lib/test/test_posixpath.py?view=markup&pathrev=78279#test_abspath>
478 foo = fileutil.abspath_expanduser_unicode(u"foo")
479 self.failUnless(foo.endswith(u"%sfoo" % (os.path.sep,)), foo)
481 foobar = fileutil.abspath_expanduser_unicode(u"bar", base=foo)
482 self.failUnless(foobar.endswith(u"%sfoo%sbar" % (os.path.sep, os.path.sep)), foobar)
484 if sys.platform == "win32":
485 # This is checking that a drive letter is added for a path without one.
486 baz = fileutil.abspath_expanduser_unicode(u"\\baz")
487 self.failUnless(baz.startswith(u"\\\\?\\"), baz)
488 self.failUnlessReallyEqual(baz[5 :], u":\\baz")
490 bar = fileutil.abspath_expanduser_unicode(u"\\bar", base=baz)
491 self.failUnless(bar.startswith(u"\\\\?\\"), bar)
492 self.failUnlessReallyEqual(bar[5 :], u":\\bar")
493 # not u":\\baz\\bar", because \bar is absolute on the current drive.
495 self.failUnlessReallyEqual(baz[4], bar[4]) # same drive
497 self.failIfIn(u"~", fileutil.abspath_expanduser_unicode(u"~"))
501 cwds.append(u'\xe7w\xf0'.encode(sys.getfilesystemencoding()
503 except UnicodeEncodeError:
504 pass # the cwd can't be encoded -- test with ascii cwd only
510 for upath in (u'', u'fuu', u'f\xf9\xf9', u'/fuu', u'U:\\', u'~'):
511 uabspath = fileutil.abspath_expanduser_unicode(upath)
512 self.failUnless(isinstance(uabspath, unicode), uabspath)
516 def test_create_long_path(self):
517 workdir = u"test_create_long_path"
518 fileutil.make_dirs(workdir)
519 long_path = fileutil.abspath_expanduser_unicode(os.path.join(workdir, u'x'*255))
521 fileutil.remove(long_path)
522 self.addCleanup(_cleanup)
524 fileutil.write(long_path, "test")
525 self.failUnless(os.path.exists(long_path))
526 self.failUnlessEqual(fileutil.read(long_path), "test")
528 self.failIf(os.path.exists(long_path))
530 def _test_windows_expanduser(self, userprofile=None, homedrive=None, homepath=None):
531 def call_windows_getenv(name):
532 if name == u"USERPROFILE": return userprofile
533 if name == u"HOMEDRIVE": return homedrive
534 if name == u"HOMEPATH": return homepath
535 self.fail("unexpected argument to call_windows_getenv")
536 self.patch(fileutil, 'windows_getenv', call_windows_getenv)
538 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
539 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~\\foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
540 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~/foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
541 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a"), u"a")
542 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a~"), u"a~")
543 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a\\~\\foo"), u"a\\~\\foo")
545 def test_windows_expanduser_xp(self):
546 return self._test_windows_expanduser(homedrive=u"C:", homepath=u"\\Documents and Settings\\\u0100")
548 def test_windows_expanduser_win7(self):
549 return self._test_windows_expanduser(userprofile=os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
551 def test_disk_stats(self):
552 avail = fileutil.get_available_space('.', 2**14)
554 raise unittest.SkipTest("This test will spuriously fail there is no disk space left.")
556 disk = fileutil.get_disk_stats('.', 2**13)
557 self.failUnless(disk['total'] > 0, disk['total'])
558 # we tolerate used==0 for a Travis-CI bug, see #2290
559 self.failUnless(disk['used'] >= 0, disk['used'])
560 self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
561 self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
562 self.failUnless(disk['avail'] > 0, disk['avail'])
564 def test_disk_stats_avail_nonnegative(self):
565 # This test will spuriously fail if you have more than 2^128
566 # bytes of available space on your filesystem.
567 disk = fileutil.get_disk_stats('.', 2**128)
568 self.failUnlessEqual(disk['avail'], 0)
570 class PollMixinTests(unittest.TestCase):
572 self.pm = pollmixin.PollMixin()
574 def test_PollMixin_True(self):
575 d = self.pm.poll(check_f=lambda : True,
579 def test_PollMixin_False_then_True(self):
580 i = iter([False, True])
581 d = self.pm.poll(check_f=i.next,
585 def test_timeout(self):
586 d = self.pm.poll(check_f=lambda: False,
590 self.fail("poll should have failed, not returned %s" % (res,))
592 f.trap(pollmixin.TimeoutError)
593 return None # success
594 d.addCallbacks(_suc, _err)
597 class DeferredUtilTests(unittest.TestCase, deferredutil.WaitForDelayedCallsMixin):
598 def test_gather_results(self):
599 d1 = defer.Deferred()
600 d2 = defer.Deferred()
601 res = deferredutil.gatherResults([d1, d2])
602 d1.errback(ValueError("BAD"))
604 self.fail("Should have errbacked, not resulted in %s" % (res,))
606 thef.trap(ValueError)
607 res.addCallbacks(_callb, _errb)
610 def test_success(self):
611 d1, d2 = defer.Deferred(), defer.Deferred()
614 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
615 dlss.addCallbacks(good.append, bad.append)
618 self.failUnlessEqual(good, [[1,2]])
619 self.failUnlessEqual(bad, [])
621 def test_failure(self):
622 d1, d2 = defer.Deferred(), defer.Deferred()
625 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
626 dlss.addCallbacks(good.append, bad.append)
627 d1.addErrback(lambda _ignore: None)
628 d2.addErrback(lambda _ignore: None)
630 d2.errback(ValueError())
631 self.failUnlessEqual(good, [])
632 self.failUnlessEqual(len(bad), 1)
634 self.failUnless(isinstance(f, Failure))
635 self.failUnless(f.check(ValueError))
637 def test_wait_for_delayed_calls(self):
639 This tests that 'wait_for_delayed_calls' does in fact wait for a
640 delayed call that is active when the test returns. If it didn't,
641 Trial would report an unclean reactor error for this test.
646 reactor.callLater(0.1, _trigger)
648 d = defer.succeed(None)
649 d.addBoth(self.wait_for_delayed_calls)
652 class HashUtilTests(unittest.TestCase):
654 def test_random_key(self):
655 k = hashutil.random_key()
656 self.failUnlessEqual(len(k), hashutil.KEYLEN)
658 def test_sha256d(self):
659 h1 = hashutil.tagged_hash("tag1", "value")
660 h2 = hashutil.tagged_hasher("tag1")
664 self.failUnlessEqual(h1, h2a)
665 self.failUnlessEqual(h2a, h2b)
667 def test_sha256d_truncated(self):
668 h1 = hashutil.tagged_hash("tag1", "value", 16)
669 h2 = hashutil.tagged_hasher("tag1", 16)
672 self.failUnlessEqual(len(h1), 16)
673 self.failUnlessEqual(len(h2), 16)
674 self.failUnlessEqual(h1, h2)
677 h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
678 h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
681 self.failUnlessEqual(h1, h2)
683 def test_hashers(self):
684 h1 = hashutil.block_hash("foo")
685 h2 = hashutil.block_hasher()
687 self.failUnlessEqual(h1, h2.digest())
689 h1 = hashutil.uri_extension_hash("foo")
690 h2 = hashutil.uri_extension_hasher()
692 self.failUnlessEqual(h1, h2.digest())
694 h1 = hashutil.plaintext_hash("foo")
695 h2 = hashutil.plaintext_hasher()
697 self.failUnlessEqual(h1, h2.digest())
699 h1 = hashutil.crypttext_hash("foo")
700 h2 = hashutil.crypttext_hasher()
702 self.failUnlessEqual(h1, h2.digest())
704 h1 = hashutil.crypttext_segment_hash("foo")
705 h2 = hashutil.crypttext_segment_hasher()
707 self.failUnlessEqual(h1, h2.digest())
709 h1 = hashutil.plaintext_segment_hash("foo")
710 h2 = hashutil.plaintext_segment_hasher()
712 self.failUnlessEqual(h1, h2.digest())
714 def test_timing_safe_compare(self):
715 self.failUnless(hashutil.timing_safe_compare("a", "a"))
716 self.failUnless(hashutil.timing_safe_compare("ab", "ab"))
717 self.failIf(hashutil.timing_safe_compare("a", "b"))
718 self.failIf(hashutil.timing_safe_compare("a", "aa"))
720 def _testknown(self, hashf, expected_a, *args):
722 got_a = base32.b2a(got)
723 self.failUnlessEqual(got_a, expected_a)
725 def test_known_answers(self):
726 # assert backwards compatibility
727 self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
728 self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
729 self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
730 self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
731 self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
732 self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
733 self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
734 self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
735 self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
736 self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
737 self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
738 self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
739 self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
740 self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
741 self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
742 self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
743 self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
744 self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
745 self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
746 self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
747 self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
748 self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
749 self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
752 class Abbreviate(unittest.TestCase):
754 a = abbreviate.abbreviate_time
755 self.failUnlessEqual(a(None), "unknown")
756 self.failUnlessEqual(a(0), "0 seconds")
757 self.failUnlessEqual(a(1), "1 second")
758 self.failUnlessEqual(a(2), "2 seconds")
759 self.failUnlessEqual(a(119), "119 seconds")
761 self.failUnlessEqual(a(2*MIN), "2 minutes")
762 self.failUnlessEqual(a(60*MIN), "60 minutes")
763 self.failUnlessEqual(a(179*MIN), "179 minutes")
765 self.failUnlessEqual(a(180*MIN), "3 hours")
766 self.failUnlessEqual(a(4*HOUR), "4 hours")
769 self.failUnlessEqual(a(2*DAY), "2 days")
770 self.failUnlessEqual(a(2*MONTH), "2 months")
772 self.failUnlessEqual(a(5*YEAR), "5 years")
774 def test_space(self):
775 tests_si = [(None, "unknown"),
782 (20*1000, "20.00 kB"),
783 (1024*1024, "1.05 MB"),
784 (1000*1000, "1.00 MB"),
785 (1000*1000*1000, "1.00 GB"),
786 (1000*1000*1000*1000, "1.00 TB"),
787 (1000*1000*1000*1000*1000, "1.00 PB"),
788 (1000*1000*1000*1000*1000*1000, "1.00 EB"),
789 (1234567890123456789, "1.23 EB"),
791 for (x, expected) in tests_si:
792 got = abbreviate.abbreviate_space(x, SI=True)
793 self.failUnlessEqual(got, expected)
795 tests_base1024 = [(None, "unknown"),
802 (20*1024, "20.00 kiB"),
803 (1000*1000, "976.56 kiB"),
804 (1024*1024, "1.00 MiB"),
805 (1024*1024*1024, "1.00 GiB"),
806 (1024*1024*1024*1024, "1.00 TiB"),
807 (1000*1000*1000*1000*1000, "909.49 TiB"),
808 (1024*1024*1024*1024*1024, "1.00 PiB"),
809 (1024*1024*1024*1024*1024*1024, "1.00 EiB"),
810 (1234567890123456789, "1.07 EiB"),
812 for (x, expected) in tests_base1024:
813 got = abbreviate.abbreviate_space(x, SI=False)
814 self.failUnlessEqual(got, expected)
816 self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
817 "(1.23 MB, 1.18 MiB)")
819 def test_parse_space(self):
820 p = abbreviate.parse_abbreviated_size
821 self.failUnlessEqual(p(""), None)
822 self.failUnlessEqual(p(None), None)
823 self.failUnlessEqual(p("123"), 123)
824 self.failUnlessEqual(p("123B"), 123)
825 self.failUnlessEqual(p("2K"), 2000)
826 self.failUnlessEqual(p("2kb"), 2000)
827 self.failUnlessEqual(p("2KiB"), 2048)
828 self.failUnlessEqual(p("10MB"), 10*1000*1000)
829 self.failUnlessEqual(p("10MiB"), 10*1024*1024)
830 self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
831 self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
832 self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
833 self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
834 self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
835 self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
836 self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
837 self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
839 e = self.failUnlessRaises(ValueError, p, "12 cubits")
840 self.failUnlessIn("12 cubits", str(e))
841 e = self.failUnlessRaises(ValueError, p, "1 BB")
842 self.failUnlessIn("1 BB", str(e))
843 e = self.failUnlessRaises(ValueError, p, "fhtagn")
844 self.failUnlessIn("fhtagn", str(e))
846 class Limiter(unittest.TestCase):
847 timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
849 def job(self, i, foo):
850 self.calls.append( (i, foo) )
851 self.simultaneous += 1
852 self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
855 self.simultaneous -= 1
856 d.callback("done %d" % i)
857 reactor.callLater(1.0, _done)
860 def bad_job(self, i, foo):
861 raise ValueError("bad_job %d" % i)
863 def test_limiter(self):
865 self.simultaneous = 0
866 self.peak_simultaneous = 0
867 l = limiter.ConcurrencyLimiter()
870 dl.append(l.add(self.job, i, foo=str(i)))
871 d = defer.DeferredList(dl, fireOnOneErrback=True)
873 self.failUnlessEqual(self.simultaneous, 0)
874 self.failUnless(self.peak_simultaneous <= 10)
875 self.failUnlessEqual(len(self.calls), 20)
877 self.failUnless( (i, str(i)) in self.calls)
881 def test_errors(self):
883 self.simultaneous = 0
884 self.peak_simultaneous = 0
885 l = limiter.ConcurrencyLimiter()
888 dl.append(l.add(self.job, i, foo=str(i)))
889 d2 = l.add(self.bad_job, 21, "21")
890 d = defer.DeferredList(dl, fireOnOneErrback=True)
893 for (success, result) in res:
894 self.failUnlessEqual(success, True)
895 results.append(result)
897 expected_results = ["done %d" % i for i in range(20)]
898 expected_results.sort()
899 self.failUnlessEqual(results, expected_results)
900 self.failUnless(self.peak_simultaneous <= 10)
901 self.failUnlessEqual(len(self.calls), 20)
903 self.failUnless( (i, str(i)) in self.calls)
905 self.fail("should have failed, not got %s" % (res,))
908 self.failUnless("bad_job 21" in str(f))
909 d2.addCallbacks(_good, _err)
911 d.addCallback(_most_done)
913 self.failUnlessEqual(self.simultaneous, 0)
914 self.failUnless(self.peak_simultaneous <= 10)
915 self.failUnlessEqual(len(self.calls), 20)
917 self.failUnless( (i, str(i)) in self.calls)
918 d.addCallback(_all_done)
921 class TimeFormat(unittest.TestCase):
922 def test_epoch(self):
923 return self._help_test_epoch()
925 def test_epoch_in_London(self):
926 # Europe/London is a particularly troublesome timezone. Nowadays, its
927 # offset from GMT is 0. But in 1970, its offset from GMT was 1.
928 # (Apparently in 1970 Britain had redefined standard time to be GMT+1
929 # and stayed in standard time all year round, whereas today
930 # Europe/London standard time is GMT and Europe/London Daylight
931 # Savings Time is GMT+1.) The current implementation of
932 # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
933 # Europe/London. (As soon as this unit test is done then I'll change
934 # that implementation to something that works even in this case...)
935 origtz = os.environ.get('TZ')
936 os.environ['TZ'] = "Europe/London"
937 if hasattr(time, 'tzset'):
940 return self._help_test_epoch()
945 os.environ['TZ'] = origtz
946 if hasattr(time, 'tzset'):
949 def _help_test_epoch(self):
950 origtzname = time.tzname
951 s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
952 self.failUnlessEqual(s, 1.0)
953 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
954 self.failUnlessEqual(s, 1.0)
955 s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
956 self.failUnlessEqual(s, 1.0)
958 self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
959 self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
960 "1970-01-01 00:00:01")
963 isostr = time_format.iso_utc(now)
964 timestamp = time_format.iso_utc_time_to_seconds(isostr)
965 self.failUnlessEqual(int(timestamp), int(now))
969 self.failUnlessEqual(time_format.iso_utc(t=my_time),
970 "1970-01-01_00:00:01")
971 e = self.failUnlessRaises(ValueError,
972 time_format.iso_utc_time_to_seconds,
973 "invalid timestring")
974 self.failUnless("not a complete ISO8601 timestamp" in str(e))
975 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
976 self.failUnlessEqual(s, 1.5)
978 # Look for daylight-savings-related errors.
979 thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
980 self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
981 self.failUnlessEqual(origtzname, time.tzname)
983 def test_iso_utc(self):
984 when = 1266760143.7841301
985 out = time_format.iso_utc_date(when)
986 self.failUnlessEqual(out, "2010-02-21")
987 out = time_format.iso_utc_date(t=lambda: when)
988 self.failUnlessEqual(out, "2010-02-21")
989 out = time_format.iso_utc(when)
990 self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
991 out = time_format.iso_utc(when, sep="-")
992 self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
994 def test_parse_duration(self):
995 p = time_format.parse_duration
997 self.failUnlessEqual(p("1 day"), DAY)
998 self.failUnlessEqual(p("2 days"), 2*DAY)
999 self.failUnlessEqual(p("3 months"), 3*31*DAY)
1000 self.failUnlessEqual(p("4 mo"), 4*31*DAY)
1001 self.failUnlessEqual(p("5 years"), 5*365*DAY)
1002 e = self.failUnlessRaises(ValueError, p, "123")
1003 self.failUnlessIn("no unit (like day, month, or year) in '123'",
1006 def test_parse_date(self):
1007 self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
1009 def test_format_time(self):
1010 self.failUnlessEqual(time_format.format_time(time.gmtime(0)), '1970-01-01 00:00:00')
1011 self.failUnlessEqual(time_format.format_time(time.gmtime(60)), '1970-01-01 00:01:00')
1012 self.failUnlessEqual(time_format.format_time(time.gmtime(60*60)), '1970-01-01 01:00:00')
1013 seconds_per_day = 60*60*24
1014 leap_years_1970_to_2014_inclusive = ((2012 - 1968) // 4)
1015 self.failUnlessEqual(time_format.format_time(time.gmtime(seconds_per_day*((2015 - 1970)*365+leap_years_1970_to_2014_inclusive))), '2015-01-01 00:00:00')
1017 def test_format_time_y2038(self):
1018 seconds_per_day = 60*60*24
1019 leap_years_1970_to_2047_inclusive = ((2044 - 1968) // 4)
1020 self.failUnlessEqual(time_format.format_time(time.gmtime(seconds_per_day*((2048 - 1970)*365+leap_years_1970_to_2047_inclusive))), '2048-01-01 00:00:00')
1022 test_format_time_y2038.todo = "This test is known to fail on systems with 32-bit time_t."
1024 def test_format_delta(self):
1026 time_5s_delta = 1389812728
1027 time_28m7s_delta = 1389814410
1028 time_1h_delta = 1389816323
1029 time_1d21h46m49s_delta = 1389977532
1031 self.failUnlessEqual(
1032 time_format.format_delta(time_1, time_1), '0s')
1034 self.failUnlessEqual(
1035 time_format.format_delta(time_1, time_5s_delta), '5s')
1036 self.failUnlessEqual(
1037 time_format.format_delta(time_1, time_28m7s_delta), '28m 7s')
1038 self.failUnlessEqual(
1039 time_format.format_delta(time_1, time_1h_delta), '1h 0m 0s')
1040 self.failUnlessEqual(
1041 time_format.format_delta(time_1, time_1d21h46m49s_delta), '1d 21h 46m 49s')
1043 self.failUnlessEqual(
1044 time_format.format_delta(time_1d21h46m49s_delta, time_1), '-')
1046 # time_1 with a decimal fraction will make the delta 1s less
1047 time_1decimal = 1389812723.383963
1049 self.failUnlessEqual(
1050 time_format.format_delta(time_1decimal, time_5s_delta), '4s')
1051 self.failUnlessEqual(
1052 time_format.format_delta(time_1decimal, time_28m7s_delta), '28m 6s')
1053 self.failUnlessEqual(
1054 time_format.format_delta(time_1decimal, time_1h_delta), '59m 59s')
1055 self.failUnlessEqual(
1056 time_format.format_delta(time_1decimal, time_1d21h46m49s_delta), '1d 21h 46m 48s')
1058 class CacheDir(unittest.TestCase):
1059 def test_basic(self):
1060 basedir = "test_util/CacheDir/test_basic"
1062 def _failIfExists(name):
1063 absfn = os.path.join(basedir, name)
1064 self.failIf(os.path.exists(absfn),
1065 "%s exists but it shouldn't" % absfn)
1067 def _failUnlessExists(name):
1068 absfn = os.path.join(basedir, name)
1069 self.failUnless(os.path.exists(absfn),
1070 "%s doesn't exist but it should" % absfn)
1072 cdm = cachedir.CacheDirectoryManager(basedir)
1073 a = cdm.get_file("a")
1074 b = cdm.get_file("b")
1075 c = cdm.get_file("c")
1076 f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
1077 f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
1078 f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
1080 _failUnlessExists("a")
1081 _failUnlessExists("b")
1082 _failUnlessExists("c")
1086 _failUnlessExists("a")
1087 _failUnlessExists("b")
1088 _failUnlessExists("c")
1091 # this file won't be deleted yet, because it isn't old enough
1093 _failUnlessExists("a")
1094 _failUnlessExists("b")
1095 _failUnlessExists("c")
1097 # we change the definition of "old" to make everything old
1102 _failUnlessExists("b")
1103 _failUnlessExists("c")
1111 _failUnlessExists("b")
1112 _failUnlessExists("c")
1114 b2 = cdm.get_file("b")
1118 _failUnlessExists("b")
1119 _failUnlessExists("c")
1124 def __init__(self, x):
1129 return "<%s %s>" % (self.__class__.__name__, self.x,)
1132 def __le__(self, other):
1133 return self.x <= other
1134 def __lt__(self, other):
1135 return self.x < other
1136 def __ge__(self, other):
1137 return self.x >= other
1138 def __gt__(self, other):
1139 return self.x > other
1140 def __ne__(self, other):
1141 return self.x != other
1142 def __eq__(self, other):
1143 return self.x == other
1145 class DictUtil(unittest.TestCase):
1146 def _help_test_empty_dict(self, klass):
1150 self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1151 self.failUnless(len(d1) == 0)
1152 self.failUnless(len(d2) == 0)
1154 def _help_test_nonempty_dict(self, klass):
1155 d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1156 d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1158 self.failUnless(d1 == d2)
1159 self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1160 self.failUnless(len(d2) == 3)
1162 def _help_test_eq_but_notis(self, klass):
1163 d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1168 d['b'] = EqButNotIs(3)
1173 d['b'] = EqButNotIs(3)
1179 d['a'] = EqButNotIs(3)
1184 fake3 = EqButNotIs(3)
1185 fake7 = EqButNotIs(7)
1189 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1190 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1191 # The real 7 should have been ejected by the d[3] = 8.
1192 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1193 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1194 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1199 fake3 = EqButNotIs(3)
1200 fake7 = EqButNotIs(7)
1203 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1204 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1205 # The real 7 should have been ejected by the d[3] = 8.
1206 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1207 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1208 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1212 self._help_test_eq_but_notis(dictutil.UtilDict)
1213 self._help_test_eq_but_notis(dictutil.NumDict)
1214 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1215 self._help_test_nonempty_dict(dictutil.UtilDict)
1216 self._help_test_nonempty_dict(dictutil.NumDict)
1217 self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1218 self._help_test_eq_but_notis(dictutil.UtilDict)
1219 self._help_test_eq_but_notis(dictutil.NumDict)
1220 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1222 def test_dict_of_sets(self):
1223 ds = dictutil.DictOfSets()
1228 self.failUnlessEqual(ds[1], set(["a"]))
1229 self.failUnlessEqual(ds[2], set(["b", "c"]))
1230 ds.discard(3, "d") # should not raise an exception
1232 self.failUnlessEqual(ds[2], set(["c"]))
1234 self.failIf(2 in ds)
1237 ds2 = dictutil.DictOfSets()
1242 self.failUnlessEqual(ds[1], set(["a"]))
1243 self.failUnlessEqual(ds[3], set(["f", "g"]))
1244 self.failUnlessEqual(ds[4], set(["h"]))
1246 def test_move(self):
1247 d1 = {1: "a", 2: "b"}
1248 d2 = {2: "c", 3: "d"}
1249 dictutil.move(1, d1, d2)
1250 self.failUnlessEqual(d1, {2: "b"})
1251 self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1253 d1 = {1: "a", 2: "b"}
1254 d2 = {2: "c", 3: "d"}
1255 dictutil.move(2, d1, d2)
1256 self.failUnlessEqual(d1, {1: "a"})
1257 self.failUnlessEqual(d2, {2: "b", 3: "d"})
1259 d1 = {1: "a", 2: "b"}
1260 d2 = {2: "c", 3: "d"}
1261 self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1263 def test_subtract(self):
1264 d1 = {1: "a", 2: "b"}
1265 d2 = {2: "c", 3: "d"}
1266 d3 = dictutil.subtract(d1, d2)
1267 self.failUnlessEqual(d3, {1: "a"})
1269 d1 = {1: "a", 2: "b"}
1271 d3 = dictutil.subtract(d1, d2)
1272 self.failUnlessEqual(d3, {1: "a"})
1274 def test_utildict(self):
1275 d = dictutil.UtilDict({1: "a", 2: "b"})
1278 self.failUnlessEqual(d, {2: "b"})
1281 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1283 d = dictutil.UtilDict({1: "b", 2: "a"})
1284 self.failUnlessEqual(d.items_sorted_by_value(),
1285 [(2, "a"), (1, "b")])
1286 self.failUnlessEqual(d.items_sorted_by_key(),
1287 [(1, "b"), (2, "a")])
1288 self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1289 self.failUnless(1 in d)
1291 d2 = dictutil.UtilDict({3: "c", 4: "d"})
1292 self.failUnless(d != d2)
1293 self.failUnless(d2 > d)
1294 self.failUnless(d2 >= d)
1295 self.failUnless(d <= d2)
1296 self.failUnless(d < d2)
1297 self.failUnlessEqual(d[1], "b")
1298 self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1301 self.failUnlessEqual(d, d3)
1302 self.failUnless(isinstance(d3, dictutil.UtilDict))
1304 d4 = d.fromkeys([3,4], "e")
1305 self.failUnlessEqual(d4, {3: "e", 4: "e"})
1307 self.failUnlessEqual(d.get(1), "b")
1308 self.failUnlessEqual(d.get(3), None)
1309 self.failUnlessEqual(d.get(3, "default"), "default")
1310 self.failUnlessEqual(sorted(list(d.items())),
1311 [(1, "b"), (2, "a")])
1312 self.failUnlessEqual(sorted(list(d.iteritems())),
1313 [(1, "b"), (2, "a")])
1314 self.failUnlessEqual(sorted(d.keys()), [1, 2])
1315 self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1316 x = d.setdefault(1, "new")
1317 self.failUnlessEqual(x, "b")
1318 self.failUnlessEqual(d[1], "b")
1319 x = d.setdefault(3, "new")
1320 self.failUnlessEqual(x, "new")
1321 self.failUnlessEqual(d[3], "new")
1325 self.failUnless(x in [(1, "b"), (2, "a")])
1327 self.failUnless(x in [(1, "b"), (2, "a")])
1328 self.failUnlessRaises(KeyError, d.popitem)
1330 def test_numdict(self):
1331 d = dictutil.NumDict({"a": 1, "b": 2})
1333 d.add_num("a", 10, 5)
1334 d.add_num("c", 20, 5)
1336 self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1338 d.subtract_num("a", 10)
1339 d.subtract_num("e", 10)
1340 d.subtract_num("f", 10, 15)
1341 self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1344 self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1346 d = dictutil.NumDict()
1350 self.failUnlessEqual(d, {"a": 2, "b": 6})
1354 self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1355 self.failUnlessEqual(d.items_sorted_by_key(),
1356 [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1357 self.failUnlessEqual(d.items_sorted_by_value(),
1358 [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1359 self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1361 d = dictutil.NumDict({"a": 1, "b": 2})
1362 self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1363 self.failUnless("a" in d)
1365 d2 = dictutil.NumDict({"c": 3, "d": 4})
1366 self.failUnless(d != d2)
1367 self.failUnless(d2 > d)
1368 self.failUnless(d2 >= d)
1369 self.failUnless(d <= d2)
1370 self.failUnless(d < d2)
1371 self.failUnlessEqual(d["a"], 1)
1372 self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1375 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1378 self.failUnlessEqual(d, d3)
1379 self.failUnless(isinstance(d3, dictutil.NumDict))
1381 d4 = d.fromkeys(["a","b"], 5)
1382 self.failUnlessEqual(d4, {"a": 5, "b": 5})
1384 self.failUnlessEqual(d.get("a"), 1)
1385 self.failUnlessEqual(d.get("c"), 0)
1386 self.failUnlessEqual(d.get("c", 5), 5)
1387 self.failUnlessEqual(sorted(list(d.items())),
1388 [("a", 1), ("b", 2)])
1389 self.failUnlessEqual(sorted(list(d.iteritems())),
1390 [("a", 1), ("b", 2)])
1391 self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1392 self.failUnlessEqual(sorted(d.values()), [1, 2])
1393 self.failUnless(d.has_key("a"))
1394 self.failIf(d.has_key("c"))
1396 x = d.setdefault("c", 3)
1397 self.failUnlessEqual(x, 3)
1398 self.failUnlessEqual(d["c"], 3)
1399 x = d.setdefault("c", 5)
1400 self.failUnlessEqual(x, 3)
1401 self.failUnlessEqual(d["c"], 3)
1405 self.failUnless(x in [("a", 1), ("b", 2)])
1407 self.failUnless(x in [("a", 1), ("b", 2)])
1408 self.failUnlessRaises(KeyError, d.popitem)
1411 d.update({"c": 4, "d": 5})
1412 self.failUnlessEqual(d, {"c": 4, "d": 5})
1414 def test_del_if_present(self):
1415 d = {1: "a", 2: "b"}
1416 dictutil.del_if_present(d, 1)
1417 dictutil.del_if_present(d, 3)
1418 self.failUnlessEqual(d, {2: "b"})
1420 def test_valueordereddict(self):
1421 d = dictutil.ValueOrderedDict()
1426 self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1427 self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1428 self.failUnlessEqual(d.values(), [1, 2, 3])
1429 self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1430 self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1433 self.failIf(d == {"a": 4})
1434 self.failUnless(d != {"a": 4})
1436 x = d.setdefault("d", 0)
1437 self.failUnlessEqual(x, 0)
1438 self.failUnlessEqual(d["d"], 0)
1439 x = d.setdefault("d", -1)
1440 self.failUnlessEqual(x, 0)
1441 self.failUnlessEqual(d["d"], 0)
1443 x = d.remove("e", "default", False)
1444 self.failUnlessEqual(x, "default")
1445 self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1446 x = d.remove("d", 5)
1447 self.failUnlessEqual(x, 0)
1449 x = d.__getitem__("c")
1450 self.failUnlessEqual(x, 1)
1451 x = d.__getitem__("e", "default", False)
1452 self.failUnlessEqual(x, "default")
1453 self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1455 self.failUnlessEqual(d.popitem(), ("c", 1))
1456 self.failUnlessEqual(d.popitem(), ("b", 2))
1457 self.failUnlessEqual(d.popitem(), ("a", 3))
1458 self.failUnlessRaises(KeyError, d.popitem)
1460 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1461 x = d.pop("d", "default", False)
1462 self.failUnlessEqual(x, "default")
1463 self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1465 self.failUnlessEqual(x, 2)
1466 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1468 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1469 x = d.pop_from_list(1) # pop the second item, b/2
1470 self.failUnlessEqual(x, "b")
1471 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1473 def test_auxdict(self):
1474 d = dictutil.AuxValueDict()
1475 # we put the serialized form in the auxdata
1476 d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1478 self.failUnlessEqual(d.keys(), ["key"])
1479 self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1480 self.failUnlessEqual(d.get_aux("key"), "serialized")
1481 def _get_missing(key):
1483 self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1484 self.failUnlessEqual(d.get("nonkey"), None)
1485 self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1486 self.failUnlessEqual(d.get_aux("nonkey"), None)
1487 self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1489 d["key"] = ("filecap2", "metadata2")
1490 self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1491 self.failUnlessEqual(d.get_aux("key"), None)
1493 d.set_with_aux("key2", "value2", "aux2")
1494 self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1496 self.failUnlessEqual(d.keys(), ["key"])
1497 self.failIf("key2" in d)
1498 self.failUnlessRaises(KeyError, _get_missing, "key2")
1499 self.failUnlessEqual(d.get("key2"), None)
1500 self.failUnlessEqual(d.get_aux("key2"), None)
1501 d["key2"] = "newvalue2"
1502 self.failUnlessEqual(d.get("key2"), "newvalue2")
1503 self.failUnlessEqual(d.get_aux("key2"), None)
1505 d = dictutil.AuxValueDict({1:2,3:4})
1506 self.failUnlessEqual(sorted(d.keys()), [1,3])
1507 self.failUnlessEqual(d[1], 2)
1508 self.failUnlessEqual(d.get_aux(1), None)
1510 d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1511 self.failUnlessEqual(sorted(d.keys()), [1,3])
1512 self.failUnlessEqual(d[1], 2)
1513 self.failUnlessEqual(d.get_aux(1), None)
1515 d = dictutil.AuxValueDict(one=1, two=2)
1516 self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1517 self.failUnlessEqual(d["one"], 1)
1518 self.failUnlessEqual(d.get_aux("one"), None)
1520 class Pipeline(unittest.TestCase):
1521 def pause(self, *args, **kwargs):
1522 d = defer.Deferred()
1523 self.calls.append( (d, args, kwargs) )
1526 def failUnlessCallsAre(self, expected):
1529 self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1530 for i,c in enumerate(self.calls):
1531 self.failUnlessEqual(c[1:], expected[i], str(i))
1533 def test_basic(self):
1536 p = pipeline.Pipeline(100)
1538 d = p.flush() # fires immediately
1539 d.addCallbacks(finished.append, log.err)
1540 self.failUnlessEqual(len(finished), 1)
1543 d = p.add(10, self.pause, "one")
1544 # the call should start right away, and our return Deferred should
1546 d.addCallbacks(finished.append, log.err)
1547 self.failUnlessEqual(len(finished), 1)
1548 self.failUnlessEqual(finished[0], None)
1549 self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1550 self.failUnlessEqual(p.gauge, 10)
1555 d = p.add(20, self.pause, "two", kw=2)
1556 # pipeline: [one, two]
1558 # the call and the Deferred should fire right away
1559 d.addCallbacks(finished.append, log.err)
1560 self.failUnlessEqual(len(finished), 1)
1561 self.failUnlessEqual(finished[0], None)
1562 self.failUnlessCallsAre([ ( ("one",) , {} ),
1563 ( ("two",) , {"kw": 2} ),
1565 self.failUnlessEqual(p.gauge, 30)
1567 self.calls[0][0].callback("one-result")
1569 self.failUnlessEqual(p.gauge, 20)
1572 d = p.add(90, self.pause, "three", "posarg1")
1573 # pipeline: [two, three]
1576 fd.addCallbacks(flushed.append, log.err)
1577 self.failUnlessEqual(flushed, [])
1579 # the call will be made right away, but the return Deferred will not,
1580 # because the pipeline is now full.
1581 d.addCallbacks(finished.append, log.err)
1582 self.failUnlessEqual(len(finished), 0)
1583 self.failUnlessCallsAre([ ( ("one",) , {} ),
1584 ( ("two",) , {"kw": 2} ),
1585 ( ("three", "posarg1"), {} ),
1587 self.failUnlessEqual(p.gauge, 110)
1589 self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1591 # retiring either call will unblock the pipeline, causing the #3
1593 self.calls[2][0].callback("three-result")
1596 self.failUnlessEqual(len(finished), 1)
1597 self.failUnlessEqual(finished[0], None)
1598 self.failUnlessEqual(flushed, [])
1600 # retiring call#2 will finally allow the flush() Deferred to fire
1601 self.calls[1][0].callback("two-result")
1602 self.failUnlessEqual(len(flushed), 1)
1604 def test_errors(self):
1606 p = pipeline.Pipeline(100)
1608 d1 = p.add(200, self.pause, "one")
1612 d1.addBoth(finished.append)
1613 self.failUnlessEqual(finished, [])
1616 d2.addBoth(flushed.append)
1617 self.failUnlessEqual(flushed, [])
1619 self.calls[0][0].errback(ValueError("oops"))
1621 self.failUnlessEqual(len(finished), 1)
1623 self.failUnless(isinstance(f, Failure))
1624 self.failUnless(f.check(pipeline.PipelineError))
1625 self.failUnlessIn("PipelineError", str(f.value))
1626 self.failUnlessIn("ValueError", str(f.value))
1628 self.failUnless("ValueError" in r, r)
1630 self.failUnless(f2.check(ValueError))
1632 self.failUnlessEqual(len(flushed), 1)
1634 self.failUnless(isinstance(f, Failure))
1635 self.failUnless(f.check(pipeline.PipelineError))
1637 self.failUnless(f2.check(ValueError))
1639 # now that the pipeline is in the failed state, any new calls will
1642 d3 = p.add(20, self.pause, "two")
1645 d3.addBoth(finished.append)
1646 self.failUnlessEqual(len(finished), 1)
1648 self.failUnless(isinstance(f, Failure))
1649 self.failUnless(f.check(pipeline.PipelineError))
1651 self.failUnless("ValueError" in r, r)
1653 self.failUnless(f2.check(ValueError))
1657 d4.addBoth(flushed.append)
1658 self.failUnlessEqual(len(flushed), 1)
1660 self.failUnless(isinstance(f, Failure))
1661 self.failUnless(f.check(pipeline.PipelineError))
1663 self.failUnless(f2.check(ValueError))
1665 def test_errors2(self):
1667 p = pipeline.Pipeline(100)
1669 d1 = p.add(10, self.pause, "one")
1670 d2 = p.add(20, self.pause, "two")
1671 d3 = p.add(30, self.pause, "three")
1674 # one call fails, then the second one succeeds: make sure
1675 # ExpandableDeferredList tolerates the second one
1678 d4.addBoth(flushed.append)
1679 self.failUnlessEqual(flushed, [])
1681 self.calls[0][0].errback(ValueError("oops"))
1682 self.failUnlessEqual(len(flushed), 1)
1684 self.failUnless(isinstance(f, Failure))
1685 self.failUnless(f.check(pipeline.PipelineError))
1687 self.failUnless(f2.check(ValueError))
1689 self.calls[1][0].callback("two-result")
1690 self.calls[2][0].errback(ValueError("three-error"))
1694 class SampleError(Exception):
1697 class Log(unittest.TestCase):
1699 if not hasattr(self, "flushLoggedErrors"):
1700 # without flushLoggedErrors, we can't get rid of the
1701 # twisted.log.err that tahoe_log records, so we can't keep this
1702 # test from [ERROR]ing
1703 raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1705 raise SampleError("simple sample")
1708 tahoe_log.err(format="intentional sample error",
1709 failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1710 self.flushLoggedErrors(SampleError)
1714 # this is a simple+inefficient form of util.spans.Spans . We compare the
1715 # behavior of this reference model against the real (efficient) form.
1717 def __init__(self, _span_or_start=None, length=None):
1719 if length is not None:
1720 for i in range(_span_or_start, _span_or_start+length):
1722 elif _span_or_start:
1723 for (start,length) in _span_or_start:
1724 self.add(start, length)
1726 def add(self, start, length):
1727 for i in range(start, start+length):
1731 def remove(self, start, length):
1732 for i in range(start, start+length):
1733 self._have.discard(i)
1737 return sorted(self._have)
1740 items = sorted(self._have)
1744 if prevstart is None:
1745 prevstart = prevend = i
1750 yield (prevstart, prevend-prevstart+1)
1751 prevstart = prevend = i
1752 if prevstart is not None:
1753 yield (prevstart, prevend-prevstart+1)
1755 def __nonzero__(self): # this gets us bool()
1759 return len(self._have)
1761 def __add__(self, other):
1762 s = self.__class__(self)
1763 for (start, length) in other:
1764 s.add(start, length)
1767 def __sub__(self, other):
1768 s = self.__class__(self)
1769 for (start, length) in other:
1770 s.remove(start, length)
1773 def __iadd__(self, other):
1774 for (start, length) in other:
1775 self.add(start, length)
1778 def __isub__(self, other):
1779 for (start, length) in other:
1780 self.remove(start, length)
1783 def __and__(self, other):
1784 s = self.__class__()
1785 for i in other.each():
1790 def __contains__(self, (start,length)):
1791 for i in range(start, start+length):
1792 if i not in self._have:
1796 class ByteSpans(unittest.TestCase):
1797 def test_basic(self):
1799 self.failUnlessEqual(list(s), [])
1801 self.failIf((0,1) in s)
1802 self.failUnlessEqual(s.len(), 0)
1804 s1 = Spans(3, 4) # 3,4,5,6
1807 s1 = Spans(3L, 4L) # 3,4,5,6
1813 s2.add(10,2) # 10,11
1815 self.failUnless((10,1) in s2)
1816 self.failIf((10,1) in s1)
1817 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1818 self.failUnlessEqual(s2.len(), 6)
1820 s2.add(15,2).add(20,2)
1821 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1822 self.failUnlessEqual(s2.len(), 10)
1824 s2.remove(4,3).remove(15,1)
1825 self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1826 self.failUnlessEqual(s2.len(), 6)
1828 s1 = SimpleSpans(3, 4) # 3 4 5 6
1829 s2 = SimpleSpans(5, 4) # 5 6 7 8
1831 self.failUnlessEqual(list(i.each()), [5, 6])
1833 def _check1(self, s):
1834 self.failUnlessEqual(list(s), [(3,4)])
1836 self.failUnlessEqual(s.len(), 4)
1837 self.failIf((0,1) in s)
1838 self.failUnless((3,4) in s)
1839 self.failUnless((3,1) in s)
1840 self.failUnless((5,2) in s)
1841 self.failUnless((6,1) in s)
1842 self.failIf((6,2) in s)
1843 self.failIf((7,1) in s)
1844 self.failUnlessEqual(list(s.each()), [3,4,5,6])
1846 def test_large(self):
1847 s = Spans(4, 2**65) # don't do this with a SimpleSpans
1848 self.failUnlessEqual(list(s), [(4, 2**65)])
1850 self.failUnlessEqual(s.len(), 2**65)
1851 self.failIf((0,1) in s)
1852 self.failUnless((4,2) in s)
1853 self.failUnless((2**65,2) in s)
1855 def test_math(self):
1856 s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1857 s2 = Spans(5, 3) # 5,6,7
1858 s3 = Spans(8, 4) # 8,9,10,11
1861 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1863 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1865 self.failUnlessEqual(list(s.each()), [5,6,7])
1867 self.failUnlessEqual(list(s.each()), [5,6,7])
1869 self.failUnlessEqual(list(s.each()), [5,6,7])
1871 self.failUnlessEqual(list(s.each()), [8,9])
1873 self.failUnlessEqual(list(s.each()), [8,9])
1875 self.failUnlessEqual(list(s.each()), [])
1877 self.failUnlessEqual(list(s.each()), [])
1879 self.failUnlessEqual(list(s.each()), [])
1881 self.failUnlessEqual(list(s.each()), [])
1884 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1886 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1888 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1892 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1895 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1898 self.failUnlessEqual(list(s.each()), [5,6,7])
1902 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1905 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1908 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1910 def test_random(self):
1911 # attempt to increase coverage of corner cases by comparing behavior
1912 # of a simple-but-slow model implementation against the
1913 # complex-but-fast actual implementation, in a large number of random
1917 s1 = S1(); s2 = S2()
1919 def _create(subseed):
1920 ns1 = S1(); ns2 = S2()
1922 what = _hash(subseed+str(i)).hexdigest()
1923 start = int(what[2:4], 16)
1924 length = max(1,int(what[5:6], 16))
1925 ns1.add(start, length); ns2.add(start, length)
1929 for i in range(1000):
1930 what = _hash(seed+str(i)).hexdigest()
1933 start = int(what[2:4], 16)
1934 length = max(1,int(what[5:6], 16))
1937 if subop in "01234":
1938 s1 = S1(); s2 = S2()
1939 elif subop in "5678":
1940 s1 = S1(start, length); s2 = S2(start, length)
1942 s1 = S1(s1); s2 = S2(s2)
1943 #print "s2 = %s" % s2.dump()
1945 #print "s2.add(%d,%d)" % (start, length)
1946 s1.add(start, length); s2.add(start, length)
1948 #print "s2.remove(%d,%d)" % (start, length)
1949 s1.remove(start, length); s2.remove(start, length)
1951 ns1, ns2 = _create(what[7:11])
1952 #print "s2 + %s" % ns2.dump()
1953 s1 = s1 + ns1; s2 = s2 + ns2
1955 ns1, ns2 = _create(what[7:11])
1956 #print "%s - %s" % (s2.dump(), ns2.dump())
1957 s1 = s1 - ns1; s2 = s2 - ns2
1959 ns1, ns2 = _create(what[7:11])
1960 #print "s2 += %s" % ns2.dump()
1961 s1 += ns1; s2 += ns2
1963 ns1, ns2 = _create(what[7:11])
1964 #print "%s -= %s" % (s2.dump(), ns2.dump())
1965 s1 -= ns1; s2 -= ns2
1967 ns1, ns2 = _create(what[7:11])
1968 #print "%s &= %s" % (s2.dump(), ns2.dump())
1969 s1 = s1 & ns1; s2 = s2 & ns2
1970 #print "s2 now %s" % s2.dump()
1971 self.failUnlessEqual(list(s1.each()), list(s2.each()))
1972 self.failUnlessEqual(s1.len(), s2.len())
1973 self.failUnlessEqual(bool(s1), bool(s2))
1974 self.failUnlessEqual(list(s1), list(s2))
1976 what = _hash(what[12:14]+str(j)).hexdigest()
1977 start = int(what[2:4], 16)
1978 length = max(1, int(what[5:6], 16))
1979 span = (start, length)
1980 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1986 # s.add(start,length) : returns s
1987 # s.remove(start,length)
1988 # s.each() -> list of byte offsets, mostly for testing
1989 # list(s) -> list of (start,length) tuples, one per span
1990 # (start,length) in s -> True if (start..start+length-1) are all members
1991 # NOT equivalent to x in list(s)
1992 # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
1993 # bool(s) (__nonzeron__)
1994 # s = s1+s2, s1-s2, +=s1, -=s1
1996 def test_overlap(self):
2001 self._test_overlap(a,b,c,d)
2003 def _test_overlap(self, a, b, c, d):
2004 s1 = set(range(a,a+b))
2005 s2 = set(range(c,c+d))
2007 #self._show_overlap(s1, "1")
2008 #self._show_overlap(s2, "2")
2009 o = overlap(a,b,c,d)
2010 expected = s1.intersection(s2)
2012 self.failUnlessEqual(o, None)
2015 so = set(range(start,start+length))
2016 #self._show(so, "o")
2017 self.failUnlessEqual(so, expected)
2019 def _show_overlap(self, s, c):
2023 for i in range(max(s)):
2030 def extend(s, start, length, fill):
2031 if len(s) >= start+length:
2033 assert len(fill) == 1
2034 return s + fill*(start+length-len(s))
2036 def replace(s, start, data):
2037 assert len(s) >= start+len(data)
2038 return s[:start] + data + s[start+len(data):]
2040 class SimpleDataSpans:
2041 def __init__(self, other=None):
2042 self.missing = "" # "1" where missing, "0" where found
2045 for (start, data) in other.get_chunks():
2046 self.add(start, data)
2048 def __nonzero__(self): # this gets us bool()
2051 return len(self.missing.replace("1", ""))
2053 return [i for (i,c) in enumerate(self.missing) if c == "0"]
2054 def _have(self, start, length):
2055 m = self.missing[start:start+length]
2056 if not m or len(m)<length or int(m):
2059 def get_chunks(self):
2060 for i in self._dump():
2061 yield (i, self.data[i])
2062 def get_spans(self):
2063 return SimpleSpans([(start,len(data))
2064 for (start,data) in self.get_chunks()])
2065 def get(self, start, length):
2066 if self._have(start, length):
2067 return self.data[start:start+length]
2069 def pop(self, start, length):
2070 data = self.get(start, length)
2072 self.remove(start, length)
2074 def remove(self, start, length):
2075 self.missing = replace(extend(self.missing, start, length, "1"),
2077 def add(self, start, data):
2078 self.missing = replace(extend(self.missing, start, len(data), "1"),
2079 start, "0"*len(data))
2080 self.data = replace(extend(self.data, start, len(data), " "),
2084 class StringSpans(unittest.TestCase):
2085 def do_basic(self, klass):
2087 self.failUnlessEqual(ds.len(), 0)
2088 self.failUnlessEqual(list(ds._dump()), [])
2089 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
2091 self.failUnlessEqual(ds.get(0, 4), None)
2092 self.failUnlessEqual(ds.pop(0, 4), None)
2096 self.failUnlessEqual(ds.len(), 4)
2097 self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
2098 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2100 self.failUnless((2,2) in s1)
2101 self.failUnlessEqual(ds.get(0, 4), None)
2102 self.failUnlessEqual(ds.pop(0, 4), None)
2103 self.failUnlessEqual(ds.get(4, 4), None)
2106 self.failUnlessEqual(ds2.len(), 4)
2107 self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2108 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2109 self.failUnlessEqual(ds2.get(0, 4), None)
2110 self.failUnlessEqual(ds2.pop(0, 4), None)
2111 self.failUnlessEqual(ds2.pop(2, 3), "fou")
2112 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2113 self.failUnlessEqual(ds2.get(2, 3), None)
2114 self.failUnlessEqual(ds2.get(5, 1), "r")
2115 self.failUnlessEqual(ds.get(2, 3), "fou")
2116 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2119 self.failUnlessEqual(ds.len(), 6)
2120 self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2121 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2122 self.failUnlessEqual(ds.get(0, 4), "23fo")
2123 self.failUnlessEqual(ds.pop(0, 4), "23fo")
2124 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2125 self.failUnlessEqual(ds.get(0, 4), None)
2126 self.failUnlessEqual(ds.pop(0, 4), None)
2131 self.failUnlessEqual(ds.get(2, 4), "fear")
2136 self.failUnlessEqual(ds.get(2L, 4L), "fear")
2139 def do_scan(self, klass):
2140 # do a test with gaps and spans of size 1 and 2
2141 # left=(1,11) * right=(1,11) * gapsize=(1,2)
2142 # 111, 112, 121, 122, 211, 212, 221, 222
2151 # 11 1 1 11 11 11 1 1 111
2152 # 0123456789012345678901234567
2153 # abcdefghijklmnopqrstuvwxyz-=
2154 pieces = [(1, "bc"),
2164 p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2165 S = "abcdefghijklmnopqrstuvwxyz-="
2166 # TODO: when adding data, add capital letters, to make sure we aren't
2167 # just leaving the old data in place
2171 for start, data in pieces:
2176 d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2180 for start in range(0, l):
2181 for end in range(start+1, l):
2182 # add [start-end) to the baseline
2183 which = "%d-%d" % (start, end-1)
2184 p_added = set(range(start, end))
2188 print dump(b), which
2189 add = klass(); add.add(start, S[start:end])
2191 b.add(start, S[start:end])
2194 # check that the new span is there
2195 d = b.get(start, end-start)
2196 self.failUnlessEqual(d, S[start:end], which)
2197 # check that all the original pieces are still there
2198 for t_start, t_data in pieces:
2200 self.failUnlessEqual(b.get(t_start, t_len),
2201 S[t_start:t_start+t_len],
2202 "%s %d+%d" % (which, t_start, t_len))
2203 # check that a lot of subspans are mostly correct
2204 for t_start in range(l):
2205 for t_len in range(1,4):
2206 d = b.get(t_start, t_len)
2208 which2 = "%s+(%d-%d)" % (which, t_start,
2210 self.failUnlessEqual(d, S[t_start:t_start+t_len],
2212 # check that removing a subspan gives the right value
2214 b2.remove(t_start, t_len)
2215 removed = set(range(t_start, t_start+t_len))
2217 exp = (((i in p_elements) or (i in p_added))
2218 and (i not in removed))
2219 which2 = "%s-(%d-%d)" % (which, t_start,
2221 self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2224 def test_test(self):
2225 self.do_basic(SimpleDataSpans)
2226 self.do_scan(SimpleDataSpans)
2228 def test_basic(self):
2229 self.do_basic(DataSpans)
2230 self.do_scan(DataSpans)
2232 def test_random(self):
2233 # attempt to increase coverage of corner cases by comparing behavior
2234 # of a simple-but-slow model implementation against the
2235 # complex-but-fast actual implementation, in a large number of random
2237 S1 = SimpleDataSpans
2239 s1 = S1(); s2 = S2()
2241 def _randstr(length, seed):
2244 while created < length:
2245 piece = _hash(seed + str(created)).hexdigest()
2246 pieces.append(piece)
2247 created += len(piece)
2248 return "".join(pieces)[:length]
2249 def _create(subseed):
2250 ns1 = S1(); ns2 = S2()
2252 what = _hash(subseed+str(i)).hexdigest()
2253 start = int(what[2:4], 16)
2254 length = max(1,int(what[5:6], 16))
2255 ns1.add(start, _randstr(length, what[7:9]));
2256 ns2.add(start, _randstr(length, what[7:9]))
2260 for i in range(1000):
2261 what = _hash(seed+str(i)).hexdigest()
2264 start = int(what[2:4], 16)
2265 length = max(1,int(what[5:6], 16))
2268 if subop in "0123456":
2269 s1 = S1(); s2 = S2()
2271 s1, s2 = _create(what[7:11])
2272 #print "s2 = %s" % list(s2._dump())
2273 elif op in "123456":
2274 #print "s2.add(%d,%d)" % (start, length)
2275 s1.add(start, _randstr(length, what[7:9]));
2276 s2.add(start, _randstr(length, what[7:9]))
2277 elif op in "789abc":
2278 #print "s2.remove(%d,%d)" % (start, length)
2279 s1.remove(start, length); s2.remove(start, length)
2281 #print "s2.pop(%d,%d)" % (start, length)
2282 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2283 self.failUnlessEqual(d1, d2)
2284 #print "s1 now %s" % list(s1._dump())
2285 #print "s2 now %s" % list(s2._dump())
2286 self.failUnlessEqual(s1.len(), s2.len())
2287 self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2288 for j in range(100):
2289 what = _hash(what[12:14]+str(j)).hexdigest()
2290 start = int(what[2:4], 16)
2291 length = max(1, int(what[5:6], 16))
2292 d1 = s1.get(start, length); d2 = s2.get(start, length)
2293 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))