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))
444 def test_rename_no_overwrite(self):
445 workdir = fileutil.abspath_expanduser_unicode(u"test_rename_no_overwrite")
446 fileutil.make_dirs(workdir)
448 source_path = os.path.join(workdir, "source")
449 dest_path = os.path.join(workdir, "dest")
451 # when neither file exists
452 self.failUnlessRaises(OSError, fileutil.rename_no_overwrite, source_path, dest_path)
454 # when only dest exists
455 fileutil.write(dest_path, "dest")
456 self.failUnlessRaises(OSError, fileutil.rename_no_overwrite, source_path, dest_path)
457 self.failUnlessEqual(fileutil.read(dest_path), "dest")
460 fileutil.write(source_path, "source")
461 self.failUnlessRaises(OSError, fileutil.rename_no_overwrite, source_path, dest_path)
462 self.failUnlessEqual(fileutil.read(source_path), "source")
463 self.failUnlessEqual(fileutil.read(dest_path), "dest")
465 # when only source exists
467 fileutil.rename_no_overwrite(source_path, dest_path)
468 self.failUnlessEqual(fileutil.read(dest_path), "source")
469 self.failIf(os.path.exists(source_path))
471 def test_replace_file(self):
472 workdir = fileutil.abspath_expanduser_unicode(u"test_replace_file")
473 fileutil.make_dirs(workdir)
475 backup_path = os.path.join(workdir, "backup")
476 replaced_path = os.path.join(workdir, "replaced")
477 replacement_path = os.path.join(workdir, "replacement")
479 # when none of the files exist
480 self.failUnlessRaises(fileutil.ConflictError, fileutil.replace_file, replaced_path, replacement_path, backup_path)
482 # when only replaced exists
483 fileutil.write(replaced_path, "foo")
484 self.failUnlessRaises(fileutil.ConflictError, fileutil.replace_file, replaced_path, replacement_path, backup_path)
485 self.failUnlessEqual(fileutil.read(replaced_path), "foo")
487 # when both replaced and replacement exist, but not backup
488 fileutil.write(replacement_path, "bar")
489 fileutil.replace_file(replaced_path, replacement_path, backup_path)
490 self.failUnlessEqual(fileutil.read(backup_path), "foo")
491 self.failUnlessEqual(fileutil.read(replaced_path), "bar")
492 self.failIf(os.path.exists(replacement_path))
494 # when only replacement exists
495 os.remove(backup_path)
496 os.remove(replaced_path)
497 fileutil.write(replacement_path, "bar")
498 fileutil.replace_file(replaced_path, replacement_path, backup_path)
499 self.failUnlessEqual(fileutil.read(replaced_path), "bar")
500 self.failIf(os.path.exists(replacement_path))
501 self.failIf(os.path.exists(backup_path))
503 # when replaced, replacement and backup all exist
504 fileutil.write(replaced_path, "foo")
505 fileutil.write(replacement_path, "bar")
506 fileutil.write(backup_path, "bak")
507 fileutil.replace_file(replaced_path, replacement_path, backup_path)
508 self.failUnlessEqual(fileutil.read(backup_path), "foo")
509 self.failUnlessEqual(fileutil.read(replaced_path), "bar")
510 self.failIf(os.path.exists(replacement_path))
513 basedir = "util/FileUtil/test_du"
514 fileutil.make_dirs(basedir)
515 d = os.path.join(basedir, "space-consuming")
517 self.touch(d, "a/b/1.txt", data="a"*10)
518 self.touch(d, "a/b/2.txt", data="b"*11)
520 self.touch(d, "a/c/1.txt", data="c"*12)
521 self.touch(d, "a/c/2.txt", data="d"*13)
523 used = fileutil.du(basedir)
524 self.failUnlessEqual(10+11+12+13, used)
526 def test_abspath_expanduser_unicode(self):
527 self.failUnlessRaises(AssertionError, fileutil.abspath_expanduser_unicode, "bytestring")
529 saved_cwd = os.path.normpath(os.getcwdu())
530 abspath_cwd = fileutil.abspath_expanduser_unicode(u".")
531 self.failUnless(isinstance(saved_cwd, unicode), saved_cwd)
532 self.failUnless(isinstance(abspath_cwd, unicode), abspath_cwd)
533 if sys.platform == "win32":
534 self.failUnlessReallyEqual(abspath_cwd, fileutil.to_windows_long_path(saved_cwd))
536 self.failUnlessReallyEqual(abspath_cwd, saved_cwd)
538 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\?\\foo"), u"\\\\?\\foo")
539 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\.\\foo"), u"\\\\.\\foo")
540 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\server\\foo"), u"\\\\?\\UNC\\server\\foo")
541 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo"), u"\\\\?\\C:\\foo")
542 self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo/bar"), u"\\\\?\\C:\\foo\\bar")
544 # adapted from <http://svn.python.org/view/python/branches/release26-maint/Lib/test/test_posixpath.py?view=markup&pathrev=78279#test_abspath>
546 foo = fileutil.abspath_expanduser_unicode(u"foo")
547 self.failUnless(foo.endswith(u"%sfoo" % (os.path.sep,)), foo)
549 foobar = fileutil.abspath_expanduser_unicode(u"bar", base=foo)
550 self.failUnless(foobar.endswith(u"%sfoo%sbar" % (os.path.sep, os.path.sep)), foobar)
552 if sys.platform == "win32":
553 # This is checking that a drive letter is added for a path without one.
554 baz = fileutil.abspath_expanduser_unicode(u"\\baz")
555 self.failUnless(baz.startswith(u"\\\\?\\"), baz)
556 self.failUnlessReallyEqual(baz[5 :], u":\\baz")
558 bar = fileutil.abspath_expanduser_unicode(u"\\bar", base=baz)
559 self.failUnless(bar.startswith(u"\\\\?\\"), bar)
560 self.failUnlessReallyEqual(bar[5 :], u":\\bar")
561 # not u":\\baz\\bar", because \bar is absolute on the current drive.
563 self.failUnlessReallyEqual(baz[4], bar[4]) # same drive
565 self.failIfIn(u"~", fileutil.abspath_expanduser_unicode(u"~"))
569 cwds.append(u'\xe7w\xf0'.encode(sys.getfilesystemencoding()
571 except UnicodeEncodeError:
572 pass # the cwd can't be encoded -- test with ascii cwd only
578 for upath in (u'', u'fuu', u'f\xf9\xf9', u'/fuu', u'U:\\', u'~'):
579 uabspath = fileutil.abspath_expanduser_unicode(upath)
580 self.failUnless(isinstance(uabspath, unicode), uabspath)
584 def test_create_long_path(self):
585 workdir = u"test_create_long_path"
586 fileutil.make_dirs(workdir)
587 long_path = fileutil.abspath_expanduser_unicode(os.path.join(workdir, u'x'*255))
589 fileutil.remove(long_path)
590 self.addCleanup(_cleanup)
592 fileutil.write(long_path, "test")
593 self.failUnless(os.path.exists(long_path))
594 self.failUnlessEqual(fileutil.read(long_path), "test")
596 self.failIf(os.path.exists(long_path))
598 def _test_windows_expanduser(self, userprofile=None, homedrive=None, homepath=None):
599 def call_windows_getenv(name):
600 if name == u"USERPROFILE": return userprofile
601 if name == u"HOMEDRIVE": return homedrive
602 if name == u"HOMEPATH": return homepath
603 self.fail("unexpected argument to call_windows_getenv")
604 self.patch(fileutil, 'windows_getenv', call_windows_getenv)
606 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
607 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~\\foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
608 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~/foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
609 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a"), u"a")
610 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a~"), u"a~")
611 self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a\\~\\foo"), u"a\\~\\foo")
613 def test_windows_expanduser_xp(self):
614 return self._test_windows_expanduser(homedrive=u"C:", homepath=u"\\Documents and Settings\\\u0100")
616 def test_windows_expanduser_win7(self):
617 return self._test_windows_expanduser(userprofile=os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
619 def test_disk_stats(self):
620 avail = fileutil.get_available_space('.', 2**14)
622 raise unittest.SkipTest("This test will spuriously fail there is no disk space left.")
624 disk = fileutil.get_disk_stats('.', 2**13)
625 self.failUnless(disk['total'] > 0, disk['total'])
626 # we tolerate used==0 for a Travis-CI bug, see #2290
627 self.failUnless(disk['used'] >= 0, disk['used'])
628 self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
629 self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
630 self.failUnless(disk['avail'] > 0, disk['avail'])
632 def test_disk_stats_avail_nonnegative(self):
633 # This test will spuriously fail if you have more than 2^128
634 # bytes of available space on your filesystem.
635 disk = fileutil.get_disk_stats('.', 2**128)
636 self.failUnlessEqual(disk['avail'], 0)
638 def test_get_pathinfo(self):
639 basedir = "util/FileUtil/test_get_pathinfo"
640 fileutil.make_dirs(basedir)
643 self.mkdir(basedir, "a")
644 dirinfo = fileutil.get_pathinfo(basedir)
645 self.failUnlessTrue(dirinfo.isdir)
646 self.failUnlessTrue(dirinfo.exists)
647 self.failUnlessFalse(dirinfo.isfile)
648 self.failUnlessFalse(dirinfo.islink)
650 # create a file under the directory
651 f = os.path.join(basedir, "a", "1.txt")
652 self.touch(basedir, "a/1.txt", data="a"*10)
653 fileinfo = fileutil.get_pathinfo(f)
654 self.failUnlessTrue(fileinfo.isfile)
655 self.failUnlessTrue(fileinfo.exists)
656 self.failUnlessFalse(fileinfo.isdir)
657 self.failUnlessFalse(fileinfo.islink)
658 self.failUnlessEqual(fileinfo.size, 10)
660 # create a symlink under the directory a pointing to 1.txt
661 slname = os.path.join(basedir, "a", "linkto1.txt")
662 os.symlink(f, slname)
663 symlinkinfo = fileutil.get_pathinfo(slname)
664 self.failUnlessTrue(symlinkinfo.islink)
665 self.failUnlessTrue(symlinkinfo.exists)
666 self.failUnlessFalse(symlinkinfo.isfile)
667 self.failUnlessFalse(symlinkinfo.isdir)
669 # path at which nothing exists
670 dnename = os.path.join(basedir, "a", "doesnotexist")
672 dneinfo = fileutil.get_pathinfo(dnename, now=now)
673 self.failUnlessFalse(dneinfo.exists)
674 self.failUnlessFalse(dneinfo.isfile)
675 self.failUnlessFalse(dneinfo.isdir)
676 self.failUnlessFalse(dneinfo.islink)
677 self.failUnlessEqual(dneinfo.size, None)
678 self.failUnlessEqual(dneinfo.mtime, now)
679 self.failUnlessEqual(dneinfo.ctime, now)
682 class PollMixinTests(unittest.TestCase):
684 self.pm = pollmixin.PollMixin()
686 def test_PollMixin_True(self):
687 d = self.pm.poll(check_f=lambda : True,
691 def test_PollMixin_False_then_True(self):
692 i = iter([False, True])
693 d = self.pm.poll(check_f=i.next,
697 def test_timeout(self):
698 d = self.pm.poll(check_f=lambda: False,
702 self.fail("poll should have failed, not returned %s" % (res,))
704 f.trap(pollmixin.TimeoutError)
705 return None # success
706 d.addCallbacks(_suc, _err)
709 class DeferredUtilTests(unittest.TestCase, deferredutil.WaitForDelayedCallsMixin):
710 def test_gather_results(self):
711 d1 = defer.Deferred()
712 d2 = defer.Deferred()
713 res = deferredutil.gatherResults([d1, d2])
714 d1.errback(ValueError("BAD"))
716 self.fail("Should have errbacked, not resulted in %s" % (res,))
718 thef.trap(ValueError)
719 res.addCallbacks(_callb, _errb)
722 def test_success(self):
723 d1, d2 = defer.Deferred(), defer.Deferred()
726 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
727 dlss.addCallbacks(good.append, bad.append)
730 self.failUnlessEqual(good, [[1,2]])
731 self.failUnlessEqual(bad, [])
733 def test_failure(self):
734 d1, d2 = defer.Deferred(), defer.Deferred()
737 dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
738 dlss.addCallbacks(good.append, bad.append)
739 d1.addErrback(lambda _ignore: None)
740 d2.addErrback(lambda _ignore: None)
742 d2.errback(ValueError())
743 self.failUnlessEqual(good, [])
744 self.failUnlessEqual(len(bad), 1)
746 self.failUnless(isinstance(f, Failure))
747 self.failUnless(f.check(ValueError))
749 def test_wait_for_delayed_calls(self):
751 This tests that 'wait_for_delayed_calls' does in fact wait for a
752 delayed call that is active when the test returns. If it didn't,
753 Trial would report an unclean reactor error for this test.
758 reactor.callLater(0.1, _trigger)
760 d = defer.succeed(None)
761 d.addBoth(self.wait_for_delayed_calls)
764 class HashUtilTests(unittest.TestCase):
766 def test_random_key(self):
767 k = hashutil.random_key()
768 self.failUnlessEqual(len(k), hashutil.KEYLEN)
770 def test_sha256d(self):
771 h1 = hashutil.tagged_hash("tag1", "value")
772 h2 = hashutil.tagged_hasher("tag1")
776 self.failUnlessEqual(h1, h2a)
777 self.failUnlessEqual(h2a, h2b)
779 def test_sha256d_truncated(self):
780 h1 = hashutil.tagged_hash("tag1", "value", 16)
781 h2 = hashutil.tagged_hasher("tag1", 16)
784 self.failUnlessEqual(len(h1), 16)
785 self.failUnlessEqual(len(h2), 16)
786 self.failUnlessEqual(h1, h2)
789 h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
790 h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
793 self.failUnlessEqual(h1, h2)
795 def test_hashers(self):
796 h1 = hashutil.block_hash("foo")
797 h2 = hashutil.block_hasher()
799 self.failUnlessEqual(h1, h2.digest())
801 h1 = hashutil.uri_extension_hash("foo")
802 h2 = hashutil.uri_extension_hasher()
804 self.failUnlessEqual(h1, h2.digest())
806 h1 = hashutil.plaintext_hash("foo")
807 h2 = hashutil.plaintext_hasher()
809 self.failUnlessEqual(h1, h2.digest())
811 h1 = hashutil.crypttext_hash("foo")
812 h2 = hashutil.crypttext_hasher()
814 self.failUnlessEqual(h1, h2.digest())
816 h1 = hashutil.crypttext_segment_hash("foo")
817 h2 = hashutil.crypttext_segment_hasher()
819 self.failUnlessEqual(h1, h2.digest())
821 h1 = hashutil.plaintext_segment_hash("foo")
822 h2 = hashutil.plaintext_segment_hasher()
824 self.failUnlessEqual(h1, h2.digest())
826 def test_timing_safe_compare(self):
827 self.failUnless(hashutil.timing_safe_compare("a", "a"))
828 self.failUnless(hashutil.timing_safe_compare("ab", "ab"))
829 self.failIf(hashutil.timing_safe_compare("a", "b"))
830 self.failIf(hashutil.timing_safe_compare("a", "aa"))
832 def _testknown(self, hashf, expected_a, *args):
834 got_a = base32.b2a(got)
835 self.failUnlessEqual(got_a, expected_a)
837 def test_known_answers(self):
838 # assert backwards compatibility
839 self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
840 self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
841 self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
842 self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
843 self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
844 self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
845 self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
846 self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
847 self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
848 self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
849 self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
850 self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
851 self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
852 self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
853 self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
854 self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
855 self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
856 self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
857 self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
858 self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
859 self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
860 self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
861 self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
864 class Abbreviate(unittest.TestCase):
866 a = abbreviate.abbreviate_time
867 self.failUnlessEqual(a(None), "unknown")
868 self.failUnlessEqual(a(0), "0 seconds")
869 self.failUnlessEqual(a(1), "1 second")
870 self.failUnlessEqual(a(2), "2 seconds")
871 self.failUnlessEqual(a(119), "119 seconds")
873 self.failUnlessEqual(a(2*MIN), "2 minutes")
874 self.failUnlessEqual(a(60*MIN), "60 minutes")
875 self.failUnlessEqual(a(179*MIN), "179 minutes")
877 self.failUnlessEqual(a(180*MIN), "3 hours")
878 self.failUnlessEqual(a(4*HOUR), "4 hours")
881 self.failUnlessEqual(a(2*DAY), "2 days")
882 self.failUnlessEqual(a(2*MONTH), "2 months")
884 self.failUnlessEqual(a(5*YEAR), "5 years")
886 def test_space(self):
887 tests_si = [(None, "unknown"),
894 (20*1000, "20.00 kB"),
895 (1024*1024, "1.05 MB"),
896 (1000*1000, "1.00 MB"),
897 (1000*1000*1000, "1.00 GB"),
898 (1000*1000*1000*1000, "1.00 TB"),
899 (1000*1000*1000*1000*1000, "1.00 PB"),
900 (1000*1000*1000*1000*1000*1000, "1.00 EB"),
901 (1234567890123456789, "1.23 EB"),
903 for (x, expected) in tests_si:
904 got = abbreviate.abbreviate_space(x, SI=True)
905 self.failUnlessEqual(got, expected)
907 tests_base1024 = [(None, "unknown"),
914 (20*1024, "20.00 kiB"),
915 (1000*1000, "976.56 kiB"),
916 (1024*1024, "1.00 MiB"),
917 (1024*1024*1024, "1.00 GiB"),
918 (1024*1024*1024*1024, "1.00 TiB"),
919 (1000*1000*1000*1000*1000, "909.49 TiB"),
920 (1024*1024*1024*1024*1024, "1.00 PiB"),
921 (1024*1024*1024*1024*1024*1024, "1.00 EiB"),
922 (1234567890123456789, "1.07 EiB"),
924 for (x, expected) in tests_base1024:
925 got = abbreviate.abbreviate_space(x, SI=False)
926 self.failUnlessEqual(got, expected)
928 self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
929 "(1.23 MB, 1.18 MiB)")
931 def test_parse_space(self):
932 p = abbreviate.parse_abbreviated_size
933 self.failUnlessEqual(p(""), None)
934 self.failUnlessEqual(p(None), None)
935 self.failUnlessEqual(p("123"), 123)
936 self.failUnlessEqual(p("123B"), 123)
937 self.failUnlessEqual(p("2K"), 2000)
938 self.failUnlessEqual(p("2kb"), 2000)
939 self.failUnlessEqual(p("2KiB"), 2048)
940 self.failUnlessEqual(p("10MB"), 10*1000*1000)
941 self.failUnlessEqual(p("10MiB"), 10*1024*1024)
942 self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
943 self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
944 self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
945 self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
946 self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
947 self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
948 self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
949 self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
951 e = self.failUnlessRaises(ValueError, p, "12 cubits")
952 self.failUnlessIn("12 cubits", str(e))
953 e = self.failUnlessRaises(ValueError, p, "1 BB")
954 self.failUnlessIn("1 BB", str(e))
955 e = self.failUnlessRaises(ValueError, p, "fhtagn")
956 self.failUnlessIn("fhtagn", str(e))
958 class Limiter(unittest.TestCase):
959 timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
961 def job(self, i, foo):
962 self.calls.append( (i, foo) )
963 self.simultaneous += 1
964 self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
967 self.simultaneous -= 1
968 d.callback("done %d" % i)
969 reactor.callLater(1.0, _done)
972 def bad_job(self, i, foo):
973 raise ValueError("bad_job %d" % i)
975 def test_limiter(self):
977 self.simultaneous = 0
978 self.peak_simultaneous = 0
979 l = limiter.ConcurrencyLimiter()
982 dl.append(l.add(self.job, i, foo=str(i)))
983 d = defer.DeferredList(dl, fireOnOneErrback=True)
985 self.failUnlessEqual(self.simultaneous, 0)
986 self.failUnless(self.peak_simultaneous <= 10)
987 self.failUnlessEqual(len(self.calls), 20)
989 self.failUnless( (i, str(i)) in self.calls)
993 def test_errors(self):
995 self.simultaneous = 0
996 self.peak_simultaneous = 0
997 l = limiter.ConcurrencyLimiter()
1000 dl.append(l.add(self.job, i, foo=str(i)))
1001 d2 = l.add(self.bad_job, 21, "21")
1002 d = defer.DeferredList(dl, fireOnOneErrback=True)
1003 def _most_done(res):
1005 for (success, result) in res:
1006 self.failUnlessEqual(success, True)
1007 results.append(result)
1009 expected_results = ["done %d" % i for i in range(20)]
1010 expected_results.sort()
1011 self.failUnlessEqual(results, expected_results)
1012 self.failUnless(self.peak_simultaneous <= 10)
1013 self.failUnlessEqual(len(self.calls), 20)
1015 self.failUnless( (i, str(i)) in self.calls)
1017 self.fail("should have failed, not got %s" % (res,))
1020 self.failUnless("bad_job 21" in str(f))
1021 d2.addCallbacks(_good, _err)
1023 d.addCallback(_most_done)
1025 self.failUnlessEqual(self.simultaneous, 0)
1026 self.failUnless(self.peak_simultaneous <= 10)
1027 self.failUnlessEqual(len(self.calls), 20)
1029 self.failUnless( (i, str(i)) in self.calls)
1030 d.addCallback(_all_done)
1033 class TimeFormat(unittest.TestCase):
1034 def test_epoch(self):
1035 return self._help_test_epoch()
1037 def test_epoch_in_London(self):
1038 # Europe/London is a particularly troublesome timezone. Nowadays, its
1039 # offset from GMT is 0. But in 1970, its offset from GMT was 1.
1040 # (Apparently in 1970 Britain had redefined standard time to be GMT+1
1041 # and stayed in standard time all year round, whereas today
1042 # Europe/London standard time is GMT and Europe/London Daylight
1043 # Savings Time is GMT+1.) The current implementation of
1044 # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
1045 # Europe/London. (As soon as this unit test is done then I'll change
1046 # that implementation to something that works even in this case...)
1047 origtz = os.environ.get('TZ')
1048 os.environ['TZ'] = "Europe/London"
1049 if hasattr(time, 'tzset'):
1052 return self._help_test_epoch()
1055 del os.environ['TZ']
1057 os.environ['TZ'] = origtz
1058 if hasattr(time, 'tzset'):
1061 def _help_test_epoch(self):
1062 origtzname = time.tzname
1063 s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
1064 self.failUnlessEqual(s, 1.0)
1065 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
1066 self.failUnlessEqual(s, 1.0)
1067 s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
1068 self.failUnlessEqual(s, 1.0)
1070 self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
1071 self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
1072 "1970-01-01 00:00:01")
1075 isostr = time_format.iso_utc(now)
1076 timestamp = time_format.iso_utc_time_to_seconds(isostr)
1077 self.failUnlessEqual(int(timestamp), int(now))
1081 self.failUnlessEqual(time_format.iso_utc(t=my_time),
1082 "1970-01-01_00:00:01")
1083 e = self.failUnlessRaises(ValueError,
1084 time_format.iso_utc_time_to_seconds,
1085 "invalid timestring")
1086 self.failUnless("not a complete ISO8601 timestamp" in str(e))
1087 s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
1088 self.failUnlessEqual(s, 1.5)
1090 # Look for daylight-savings-related errors.
1091 thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
1092 self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
1093 self.failUnlessEqual(origtzname, time.tzname)
1095 def test_iso_utc(self):
1096 when = 1266760143.7841301
1097 out = time_format.iso_utc_date(when)
1098 self.failUnlessEqual(out, "2010-02-21")
1099 out = time_format.iso_utc_date(t=lambda: when)
1100 self.failUnlessEqual(out, "2010-02-21")
1101 out = time_format.iso_utc(when)
1102 self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
1103 out = time_format.iso_utc(when, sep="-")
1104 self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
1106 def test_parse_duration(self):
1107 p = time_format.parse_duration
1109 self.failUnlessEqual(p("1 day"), DAY)
1110 self.failUnlessEqual(p("2 days"), 2*DAY)
1111 self.failUnlessEqual(p("3 months"), 3*31*DAY)
1112 self.failUnlessEqual(p("4 mo"), 4*31*DAY)
1113 self.failUnlessEqual(p("5 years"), 5*365*DAY)
1114 e = self.failUnlessRaises(ValueError, p, "123")
1115 self.failUnlessIn("no unit (like day, month, or year) in '123'",
1118 def test_parse_date(self):
1119 self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
1121 class CacheDir(unittest.TestCase):
1122 def test_basic(self):
1123 basedir = "test_util/CacheDir/test_basic"
1125 def _failIfExists(name):
1126 absfn = os.path.join(basedir, name)
1127 self.failIf(os.path.exists(absfn),
1128 "%s exists but it shouldn't" % absfn)
1130 def _failUnlessExists(name):
1131 absfn = os.path.join(basedir, name)
1132 self.failUnless(os.path.exists(absfn),
1133 "%s doesn't exist but it should" % absfn)
1135 cdm = cachedir.CacheDirectoryManager(basedir)
1136 a = cdm.get_file("a")
1137 b = cdm.get_file("b")
1138 c = cdm.get_file("c")
1139 f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
1140 f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
1141 f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
1143 _failUnlessExists("a")
1144 _failUnlessExists("b")
1145 _failUnlessExists("c")
1149 _failUnlessExists("a")
1150 _failUnlessExists("b")
1151 _failUnlessExists("c")
1154 # this file won't be deleted yet, because it isn't old enough
1156 _failUnlessExists("a")
1157 _failUnlessExists("b")
1158 _failUnlessExists("c")
1160 # we change the definition of "old" to make everything old
1165 _failUnlessExists("b")
1166 _failUnlessExists("c")
1174 _failUnlessExists("b")
1175 _failUnlessExists("c")
1177 b2 = cdm.get_file("b")
1181 _failUnlessExists("b")
1182 _failUnlessExists("c")
1187 def __init__(self, x):
1192 return "<%s %s>" % (self.__class__.__name__, self.x,)
1195 def __le__(self, other):
1196 return self.x <= other
1197 def __lt__(self, other):
1198 return self.x < other
1199 def __ge__(self, other):
1200 return self.x >= other
1201 def __gt__(self, other):
1202 return self.x > other
1203 def __ne__(self, other):
1204 return self.x != other
1205 def __eq__(self, other):
1206 return self.x == other
1208 class DictUtil(unittest.TestCase):
1209 def _help_test_empty_dict(self, klass):
1213 self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1214 self.failUnless(len(d1) == 0)
1215 self.failUnless(len(d2) == 0)
1217 def _help_test_nonempty_dict(self, klass):
1218 d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1219 d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1221 self.failUnless(d1 == d2)
1222 self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1223 self.failUnless(len(d2) == 3)
1225 def _help_test_eq_but_notis(self, klass):
1226 d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1231 d['b'] = EqButNotIs(3)
1236 d['b'] = EqButNotIs(3)
1242 d['a'] = EqButNotIs(3)
1247 fake3 = EqButNotIs(3)
1248 fake7 = EqButNotIs(7)
1252 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1253 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1254 # The real 7 should have been ejected by the d[3] = 8.
1255 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1256 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1257 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1262 fake3 = EqButNotIs(3)
1263 fake7 = EqButNotIs(7)
1266 self.failUnless(filter(lambda x: x is 8, d.itervalues()))
1267 self.failUnless(filter(lambda x: x is fake7, d.itervalues()))
1268 # The real 7 should have been ejected by the d[3] = 8.
1269 self.failUnless(not filter(lambda x: x is 7, d.itervalues()))
1270 self.failUnless(filter(lambda x: x is fake3, d.iterkeys()))
1271 self.failUnless(filter(lambda x: x is 3, d.iterkeys()))
1275 self._help_test_eq_but_notis(dictutil.UtilDict)
1276 self._help_test_eq_but_notis(dictutil.NumDict)
1277 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1278 self._help_test_nonempty_dict(dictutil.UtilDict)
1279 self._help_test_nonempty_dict(dictutil.NumDict)
1280 self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1281 self._help_test_eq_but_notis(dictutil.UtilDict)
1282 self._help_test_eq_but_notis(dictutil.NumDict)
1283 self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1285 def test_dict_of_sets(self):
1286 ds = dictutil.DictOfSets()
1291 self.failUnlessEqual(ds[1], set(["a"]))
1292 self.failUnlessEqual(ds[2], set(["b", "c"]))
1293 ds.discard(3, "d") # should not raise an exception
1295 self.failUnlessEqual(ds[2], set(["c"]))
1297 self.failIf(2 in ds)
1300 ds2 = dictutil.DictOfSets()
1305 self.failUnlessEqual(ds[1], set(["a"]))
1306 self.failUnlessEqual(ds[3], set(["f", "g"]))
1307 self.failUnlessEqual(ds[4], set(["h"]))
1309 def test_move(self):
1310 d1 = {1: "a", 2: "b"}
1311 d2 = {2: "c", 3: "d"}
1312 dictutil.move(1, d1, d2)
1313 self.failUnlessEqual(d1, {2: "b"})
1314 self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1316 d1 = {1: "a", 2: "b"}
1317 d2 = {2: "c", 3: "d"}
1318 dictutil.move(2, d1, d2)
1319 self.failUnlessEqual(d1, {1: "a"})
1320 self.failUnlessEqual(d2, {2: "b", 3: "d"})
1322 d1 = {1: "a", 2: "b"}
1323 d2 = {2: "c", 3: "d"}
1324 self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1326 def test_subtract(self):
1327 d1 = {1: "a", 2: "b"}
1328 d2 = {2: "c", 3: "d"}
1329 d3 = dictutil.subtract(d1, d2)
1330 self.failUnlessEqual(d3, {1: "a"})
1332 d1 = {1: "a", 2: "b"}
1334 d3 = dictutil.subtract(d1, d2)
1335 self.failUnlessEqual(d3, {1: "a"})
1337 def test_utildict(self):
1338 d = dictutil.UtilDict({1: "a", 2: "b"})
1341 self.failUnlessEqual(d, {2: "b"})
1344 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1346 d = dictutil.UtilDict({1: "b", 2: "a"})
1347 self.failUnlessEqual(d.items_sorted_by_value(),
1348 [(2, "a"), (1, "b")])
1349 self.failUnlessEqual(d.items_sorted_by_key(),
1350 [(1, "b"), (2, "a")])
1351 self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1352 self.failUnless(1 in d)
1354 d2 = dictutil.UtilDict({3: "c", 4: "d"})
1355 self.failUnless(d != d2)
1356 self.failUnless(d2 > d)
1357 self.failUnless(d2 >= d)
1358 self.failUnless(d <= d2)
1359 self.failUnless(d < d2)
1360 self.failUnlessEqual(d[1], "b")
1361 self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1364 self.failUnlessEqual(d, d3)
1365 self.failUnless(isinstance(d3, dictutil.UtilDict))
1367 d4 = d.fromkeys([3,4], "e")
1368 self.failUnlessEqual(d4, {3: "e", 4: "e"})
1370 self.failUnlessEqual(d.get(1), "b")
1371 self.failUnlessEqual(d.get(3), None)
1372 self.failUnlessEqual(d.get(3, "default"), "default")
1373 self.failUnlessEqual(sorted(list(d.items())),
1374 [(1, "b"), (2, "a")])
1375 self.failUnlessEqual(sorted(list(d.iteritems())),
1376 [(1, "b"), (2, "a")])
1377 self.failUnlessEqual(sorted(d.keys()), [1, 2])
1378 self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1379 x = d.setdefault(1, "new")
1380 self.failUnlessEqual(x, "b")
1381 self.failUnlessEqual(d[1], "b")
1382 x = d.setdefault(3, "new")
1383 self.failUnlessEqual(x, "new")
1384 self.failUnlessEqual(d[3], "new")
1388 self.failUnless(x in [(1, "b"), (2, "a")])
1390 self.failUnless(x in [(1, "b"), (2, "a")])
1391 self.failUnlessRaises(KeyError, d.popitem)
1393 def test_numdict(self):
1394 d = dictutil.NumDict({"a": 1, "b": 2})
1396 d.add_num("a", 10, 5)
1397 d.add_num("c", 20, 5)
1399 self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1401 d.subtract_num("a", 10)
1402 d.subtract_num("e", 10)
1403 d.subtract_num("f", 10, 15)
1404 self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1407 self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1409 d = dictutil.NumDict()
1413 self.failUnlessEqual(d, {"a": 2, "b": 6})
1417 self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1418 self.failUnlessEqual(d.items_sorted_by_key(),
1419 [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1420 self.failUnlessEqual(d.items_sorted_by_value(),
1421 [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1422 self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1424 d = dictutil.NumDict({"a": 1, "b": 2})
1425 self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1426 self.failUnless("a" in d)
1428 d2 = dictutil.NumDict({"c": 3, "d": 4})
1429 self.failUnless(d != d2)
1430 self.failUnless(d2 > d)
1431 self.failUnless(d2 >= d)
1432 self.failUnless(d <= d2)
1433 self.failUnless(d < d2)
1434 self.failUnlessEqual(d["a"], 1)
1435 self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1438 self.failUnlessRaises(TypeError, eq, d, "not a dict")
1441 self.failUnlessEqual(d, d3)
1442 self.failUnless(isinstance(d3, dictutil.NumDict))
1444 d4 = d.fromkeys(["a","b"], 5)
1445 self.failUnlessEqual(d4, {"a": 5, "b": 5})
1447 self.failUnlessEqual(d.get("a"), 1)
1448 self.failUnlessEqual(d.get("c"), 0)
1449 self.failUnlessEqual(d.get("c", 5), 5)
1450 self.failUnlessEqual(sorted(list(d.items())),
1451 [("a", 1), ("b", 2)])
1452 self.failUnlessEqual(sorted(list(d.iteritems())),
1453 [("a", 1), ("b", 2)])
1454 self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1455 self.failUnlessEqual(sorted(d.values()), [1, 2])
1456 self.failUnless(d.has_key("a"))
1457 self.failIf(d.has_key("c"))
1459 x = d.setdefault("c", 3)
1460 self.failUnlessEqual(x, 3)
1461 self.failUnlessEqual(d["c"], 3)
1462 x = d.setdefault("c", 5)
1463 self.failUnlessEqual(x, 3)
1464 self.failUnlessEqual(d["c"], 3)
1468 self.failUnless(x in [("a", 1), ("b", 2)])
1470 self.failUnless(x in [("a", 1), ("b", 2)])
1471 self.failUnlessRaises(KeyError, d.popitem)
1474 d.update({"c": 4, "d": 5})
1475 self.failUnlessEqual(d, {"c": 4, "d": 5})
1477 def test_del_if_present(self):
1478 d = {1: "a", 2: "b"}
1479 dictutil.del_if_present(d, 1)
1480 dictutil.del_if_present(d, 3)
1481 self.failUnlessEqual(d, {2: "b"})
1483 def test_valueordereddict(self):
1484 d = dictutil.ValueOrderedDict()
1489 self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1490 self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1491 self.failUnlessEqual(d.values(), [1, 2, 3])
1492 self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1493 self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1496 self.failIf(d == {"a": 4})
1497 self.failUnless(d != {"a": 4})
1499 x = d.setdefault("d", 0)
1500 self.failUnlessEqual(x, 0)
1501 self.failUnlessEqual(d["d"], 0)
1502 x = d.setdefault("d", -1)
1503 self.failUnlessEqual(x, 0)
1504 self.failUnlessEqual(d["d"], 0)
1506 x = d.remove("e", "default", False)
1507 self.failUnlessEqual(x, "default")
1508 self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1509 x = d.remove("d", 5)
1510 self.failUnlessEqual(x, 0)
1512 x = d.__getitem__("c")
1513 self.failUnlessEqual(x, 1)
1514 x = d.__getitem__("e", "default", False)
1515 self.failUnlessEqual(x, "default")
1516 self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1518 self.failUnlessEqual(d.popitem(), ("c", 1))
1519 self.failUnlessEqual(d.popitem(), ("b", 2))
1520 self.failUnlessEqual(d.popitem(), ("a", 3))
1521 self.failUnlessRaises(KeyError, d.popitem)
1523 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1524 x = d.pop("d", "default", False)
1525 self.failUnlessEqual(x, "default")
1526 self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1528 self.failUnlessEqual(x, 2)
1529 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1531 d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1532 x = d.pop_from_list(1) # pop the second item, b/2
1533 self.failUnlessEqual(x, "b")
1534 self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1536 def test_auxdict(self):
1537 d = dictutil.AuxValueDict()
1538 # we put the serialized form in the auxdata
1539 d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1541 self.failUnlessEqual(d.keys(), ["key"])
1542 self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1543 self.failUnlessEqual(d.get_aux("key"), "serialized")
1544 def _get_missing(key):
1546 self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1547 self.failUnlessEqual(d.get("nonkey"), None)
1548 self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1549 self.failUnlessEqual(d.get_aux("nonkey"), None)
1550 self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1552 d["key"] = ("filecap2", "metadata2")
1553 self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1554 self.failUnlessEqual(d.get_aux("key"), None)
1556 d.set_with_aux("key2", "value2", "aux2")
1557 self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1559 self.failUnlessEqual(d.keys(), ["key"])
1560 self.failIf("key2" in d)
1561 self.failUnlessRaises(KeyError, _get_missing, "key2")
1562 self.failUnlessEqual(d.get("key2"), None)
1563 self.failUnlessEqual(d.get_aux("key2"), None)
1564 d["key2"] = "newvalue2"
1565 self.failUnlessEqual(d.get("key2"), "newvalue2")
1566 self.failUnlessEqual(d.get_aux("key2"), None)
1568 d = dictutil.AuxValueDict({1:2,3:4})
1569 self.failUnlessEqual(sorted(d.keys()), [1,3])
1570 self.failUnlessEqual(d[1], 2)
1571 self.failUnlessEqual(d.get_aux(1), None)
1573 d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1574 self.failUnlessEqual(sorted(d.keys()), [1,3])
1575 self.failUnlessEqual(d[1], 2)
1576 self.failUnlessEqual(d.get_aux(1), None)
1578 d = dictutil.AuxValueDict(one=1, two=2)
1579 self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1580 self.failUnlessEqual(d["one"], 1)
1581 self.failUnlessEqual(d.get_aux("one"), None)
1583 class Pipeline(unittest.TestCase):
1584 def pause(self, *args, **kwargs):
1585 d = defer.Deferred()
1586 self.calls.append( (d, args, kwargs) )
1589 def failUnlessCallsAre(self, expected):
1592 self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1593 for i,c in enumerate(self.calls):
1594 self.failUnlessEqual(c[1:], expected[i], str(i))
1596 def test_basic(self):
1599 p = pipeline.Pipeline(100)
1601 d = p.flush() # fires immediately
1602 d.addCallbacks(finished.append, log.err)
1603 self.failUnlessEqual(len(finished), 1)
1606 d = p.add(10, self.pause, "one")
1607 # the call should start right away, and our return Deferred should
1609 d.addCallbacks(finished.append, log.err)
1610 self.failUnlessEqual(len(finished), 1)
1611 self.failUnlessEqual(finished[0], None)
1612 self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1613 self.failUnlessEqual(p.gauge, 10)
1618 d = p.add(20, self.pause, "two", kw=2)
1619 # pipeline: [one, two]
1621 # the call and the Deferred should fire right away
1622 d.addCallbacks(finished.append, log.err)
1623 self.failUnlessEqual(len(finished), 1)
1624 self.failUnlessEqual(finished[0], None)
1625 self.failUnlessCallsAre([ ( ("one",) , {} ),
1626 ( ("two",) , {"kw": 2} ),
1628 self.failUnlessEqual(p.gauge, 30)
1630 self.calls[0][0].callback("one-result")
1632 self.failUnlessEqual(p.gauge, 20)
1635 d = p.add(90, self.pause, "three", "posarg1")
1636 # pipeline: [two, three]
1639 fd.addCallbacks(flushed.append, log.err)
1640 self.failUnlessEqual(flushed, [])
1642 # the call will be made right away, but the return Deferred will not,
1643 # because the pipeline is now full.
1644 d.addCallbacks(finished.append, log.err)
1645 self.failUnlessEqual(len(finished), 0)
1646 self.failUnlessCallsAre([ ( ("one",) , {} ),
1647 ( ("two",) , {"kw": 2} ),
1648 ( ("three", "posarg1"), {} ),
1650 self.failUnlessEqual(p.gauge, 110)
1652 self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1654 # retiring either call will unblock the pipeline, causing the #3
1656 self.calls[2][0].callback("three-result")
1659 self.failUnlessEqual(len(finished), 1)
1660 self.failUnlessEqual(finished[0], None)
1661 self.failUnlessEqual(flushed, [])
1663 # retiring call#2 will finally allow the flush() Deferred to fire
1664 self.calls[1][0].callback("two-result")
1665 self.failUnlessEqual(len(flushed), 1)
1667 def test_errors(self):
1669 p = pipeline.Pipeline(100)
1671 d1 = p.add(200, self.pause, "one")
1675 d1.addBoth(finished.append)
1676 self.failUnlessEqual(finished, [])
1679 d2.addBoth(flushed.append)
1680 self.failUnlessEqual(flushed, [])
1682 self.calls[0][0].errback(ValueError("oops"))
1684 self.failUnlessEqual(len(finished), 1)
1686 self.failUnless(isinstance(f, Failure))
1687 self.failUnless(f.check(pipeline.PipelineError))
1688 self.failUnlessIn("PipelineError", str(f.value))
1689 self.failUnlessIn("ValueError", str(f.value))
1691 self.failUnless("ValueError" in r, r)
1693 self.failUnless(f2.check(ValueError))
1695 self.failUnlessEqual(len(flushed), 1)
1697 self.failUnless(isinstance(f, Failure))
1698 self.failUnless(f.check(pipeline.PipelineError))
1700 self.failUnless(f2.check(ValueError))
1702 # now that the pipeline is in the failed state, any new calls will
1705 d3 = p.add(20, self.pause, "two")
1708 d3.addBoth(finished.append)
1709 self.failUnlessEqual(len(finished), 1)
1711 self.failUnless(isinstance(f, Failure))
1712 self.failUnless(f.check(pipeline.PipelineError))
1714 self.failUnless("ValueError" in r, r)
1716 self.failUnless(f2.check(ValueError))
1720 d4.addBoth(flushed.append)
1721 self.failUnlessEqual(len(flushed), 1)
1723 self.failUnless(isinstance(f, Failure))
1724 self.failUnless(f.check(pipeline.PipelineError))
1726 self.failUnless(f2.check(ValueError))
1728 def test_errors2(self):
1730 p = pipeline.Pipeline(100)
1732 d1 = p.add(10, self.pause, "one")
1733 d2 = p.add(20, self.pause, "two")
1734 d3 = p.add(30, self.pause, "three")
1737 # one call fails, then the second one succeeds: make sure
1738 # ExpandableDeferredList tolerates the second one
1741 d4.addBoth(flushed.append)
1742 self.failUnlessEqual(flushed, [])
1744 self.calls[0][0].errback(ValueError("oops"))
1745 self.failUnlessEqual(len(flushed), 1)
1747 self.failUnless(isinstance(f, Failure))
1748 self.failUnless(f.check(pipeline.PipelineError))
1750 self.failUnless(f2.check(ValueError))
1752 self.calls[1][0].callback("two-result")
1753 self.calls[2][0].errback(ValueError("three-error"))
1757 class SampleError(Exception):
1760 class Log(unittest.TestCase):
1762 if not hasattr(self, "flushLoggedErrors"):
1763 # without flushLoggedErrors, we can't get rid of the
1764 # twisted.log.err that tahoe_log records, so we can't keep this
1765 # test from [ERROR]ing
1766 raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1768 raise SampleError("simple sample")
1771 tahoe_log.err(format="intentional sample error",
1772 failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1773 self.flushLoggedErrors(SampleError)
1777 # this is a simple+inefficient form of util.spans.Spans . We compare the
1778 # behavior of this reference model against the real (efficient) form.
1780 def __init__(self, _span_or_start=None, length=None):
1782 if length is not None:
1783 for i in range(_span_or_start, _span_or_start+length):
1785 elif _span_or_start:
1786 for (start,length) in _span_or_start:
1787 self.add(start, length)
1789 def add(self, start, length):
1790 for i in range(start, start+length):
1794 def remove(self, start, length):
1795 for i in range(start, start+length):
1796 self._have.discard(i)
1800 return sorted(self._have)
1803 items = sorted(self._have)
1807 if prevstart is None:
1808 prevstart = prevend = i
1813 yield (prevstart, prevend-prevstart+1)
1814 prevstart = prevend = i
1815 if prevstart is not None:
1816 yield (prevstart, prevend-prevstart+1)
1818 def __nonzero__(self): # this gets us bool()
1822 return len(self._have)
1824 def __add__(self, other):
1825 s = self.__class__(self)
1826 for (start, length) in other:
1827 s.add(start, length)
1830 def __sub__(self, other):
1831 s = self.__class__(self)
1832 for (start, length) in other:
1833 s.remove(start, length)
1836 def __iadd__(self, other):
1837 for (start, length) in other:
1838 self.add(start, length)
1841 def __isub__(self, other):
1842 for (start, length) in other:
1843 self.remove(start, length)
1846 def __and__(self, other):
1847 s = self.__class__()
1848 for i in other.each():
1853 def __contains__(self, (start,length)):
1854 for i in range(start, start+length):
1855 if i not in self._have:
1859 class ByteSpans(unittest.TestCase):
1860 def test_basic(self):
1862 self.failUnlessEqual(list(s), [])
1864 self.failIf((0,1) in s)
1865 self.failUnlessEqual(s.len(), 0)
1867 s1 = Spans(3, 4) # 3,4,5,6
1870 s1 = Spans(3L, 4L) # 3,4,5,6
1876 s2.add(10,2) # 10,11
1878 self.failUnless((10,1) in s2)
1879 self.failIf((10,1) in s1)
1880 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1881 self.failUnlessEqual(s2.len(), 6)
1883 s2.add(15,2).add(20,2)
1884 self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1885 self.failUnlessEqual(s2.len(), 10)
1887 s2.remove(4,3).remove(15,1)
1888 self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1889 self.failUnlessEqual(s2.len(), 6)
1891 s1 = SimpleSpans(3, 4) # 3 4 5 6
1892 s2 = SimpleSpans(5, 4) # 5 6 7 8
1894 self.failUnlessEqual(list(i.each()), [5, 6])
1896 def _check1(self, s):
1897 self.failUnlessEqual(list(s), [(3,4)])
1899 self.failUnlessEqual(s.len(), 4)
1900 self.failIf((0,1) in s)
1901 self.failUnless((3,4) in s)
1902 self.failUnless((3,1) in s)
1903 self.failUnless((5,2) in s)
1904 self.failUnless((6,1) in s)
1905 self.failIf((6,2) in s)
1906 self.failIf((7,1) in s)
1907 self.failUnlessEqual(list(s.each()), [3,4,5,6])
1909 def test_large(self):
1910 s = Spans(4, 2**65) # don't do this with a SimpleSpans
1911 self.failUnlessEqual(list(s), [(4, 2**65)])
1913 self.failUnlessEqual(s.len(), 2**65)
1914 self.failIf((0,1) in s)
1915 self.failUnless((4,2) in s)
1916 self.failUnless((2**65,2) in s)
1918 def test_math(self):
1919 s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1920 s2 = Spans(5, 3) # 5,6,7
1921 s3 = Spans(8, 4) # 8,9,10,11
1924 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1926 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1928 self.failUnlessEqual(list(s.each()), [5,6,7])
1930 self.failUnlessEqual(list(s.each()), [5,6,7])
1932 self.failUnlessEqual(list(s.each()), [5,6,7])
1934 self.failUnlessEqual(list(s.each()), [8,9])
1936 self.failUnlessEqual(list(s.each()), [8,9])
1938 self.failUnlessEqual(list(s.each()), [])
1940 self.failUnlessEqual(list(s.each()), [])
1942 self.failUnlessEqual(list(s.each()), [])
1944 self.failUnlessEqual(list(s.each()), [])
1947 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1949 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1951 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1955 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1958 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1961 self.failUnlessEqual(list(s.each()), [5,6,7])
1965 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1968 self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1971 self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1973 def test_random(self):
1974 # attempt to increase coverage of corner cases by comparing behavior
1975 # of a simple-but-slow model implementation against the
1976 # complex-but-fast actual implementation, in a large number of random
1980 s1 = S1(); s2 = S2()
1982 def _create(subseed):
1983 ns1 = S1(); ns2 = S2()
1985 what = _hash(subseed+str(i)).hexdigest()
1986 start = int(what[2:4], 16)
1987 length = max(1,int(what[5:6], 16))
1988 ns1.add(start, length); ns2.add(start, length)
1992 for i in range(1000):
1993 what = _hash(seed+str(i)).hexdigest()
1996 start = int(what[2:4], 16)
1997 length = max(1,int(what[5:6], 16))
2000 if subop in "01234":
2001 s1 = S1(); s2 = S2()
2002 elif subop in "5678":
2003 s1 = S1(start, length); s2 = S2(start, length)
2005 s1 = S1(s1); s2 = S2(s2)
2006 #print "s2 = %s" % s2.dump()
2008 #print "s2.add(%d,%d)" % (start, length)
2009 s1.add(start, length); s2.add(start, length)
2011 #print "s2.remove(%d,%d)" % (start, length)
2012 s1.remove(start, length); s2.remove(start, length)
2014 ns1, ns2 = _create(what[7:11])
2015 #print "s2 + %s" % ns2.dump()
2016 s1 = s1 + ns1; s2 = s2 + ns2
2018 ns1, ns2 = _create(what[7:11])
2019 #print "%s - %s" % (s2.dump(), ns2.dump())
2020 s1 = s1 - ns1; s2 = s2 - ns2
2022 ns1, ns2 = _create(what[7:11])
2023 #print "s2 += %s" % ns2.dump()
2024 s1 += ns1; s2 += ns2
2026 ns1, ns2 = _create(what[7:11])
2027 #print "%s -= %s" % (s2.dump(), ns2.dump())
2028 s1 -= ns1; s2 -= ns2
2030 ns1, ns2 = _create(what[7:11])
2031 #print "%s &= %s" % (s2.dump(), ns2.dump())
2032 s1 = s1 & ns1; s2 = s2 & ns2
2033 #print "s2 now %s" % s2.dump()
2034 self.failUnlessEqual(list(s1.each()), list(s2.each()))
2035 self.failUnlessEqual(s1.len(), s2.len())
2036 self.failUnlessEqual(bool(s1), bool(s2))
2037 self.failUnlessEqual(list(s1), list(s2))
2039 what = _hash(what[12:14]+str(j)).hexdigest()
2040 start = int(what[2:4], 16)
2041 length = max(1, int(what[5:6], 16))
2042 span = (start, length)
2043 self.failUnlessEqual(bool(span in s1), bool(span in s2))
2049 # s.add(start,length) : returns s
2050 # s.remove(start,length)
2051 # s.each() -> list of byte offsets, mostly for testing
2052 # list(s) -> list of (start,length) tuples, one per span
2053 # (start,length) in s -> True if (start..start+length-1) are all members
2054 # NOT equivalent to x in list(s)
2055 # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
2056 # bool(s) (__nonzeron__)
2057 # s = s1+s2, s1-s2, +=s1, -=s1
2059 def test_overlap(self):
2064 self._test_overlap(a,b,c,d)
2066 def _test_overlap(self, a, b, c, d):
2067 s1 = set(range(a,a+b))
2068 s2 = set(range(c,c+d))
2070 #self._show_overlap(s1, "1")
2071 #self._show_overlap(s2, "2")
2072 o = overlap(a,b,c,d)
2073 expected = s1.intersection(s2)
2075 self.failUnlessEqual(o, None)
2078 so = set(range(start,start+length))
2079 #self._show(so, "o")
2080 self.failUnlessEqual(so, expected)
2082 def _show_overlap(self, s, c):
2086 for i in range(max(s)):
2093 def extend(s, start, length, fill):
2094 if len(s) >= start+length:
2096 assert len(fill) == 1
2097 return s + fill*(start+length-len(s))
2099 def replace(s, start, data):
2100 assert len(s) >= start+len(data)
2101 return s[:start] + data + s[start+len(data):]
2103 class SimpleDataSpans:
2104 def __init__(self, other=None):
2105 self.missing = "" # "1" where missing, "0" where found
2108 for (start, data) in other.get_chunks():
2109 self.add(start, data)
2111 def __nonzero__(self): # this gets us bool()
2114 return len(self.missing.replace("1", ""))
2116 return [i for (i,c) in enumerate(self.missing) if c == "0"]
2117 def _have(self, start, length):
2118 m = self.missing[start:start+length]
2119 if not m or len(m)<length or int(m):
2122 def get_chunks(self):
2123 for i in self._dump():
2124 yield (i, self.data[i])
2125 def get_spans(self):
2126 return SimpleSpans([(start,len(data))
2127 for (start,data) in self.get_chunks()])
2128 def get(self, start, length):
2129 if self._have(start, length):
2130 return self.data[start:start+length]
2132 def pop(self, start, length):
2133 data = self.get(start, length)
2135 self.remove(start, length)
2137 def remove(self, start, length):
2138 self.missing = replace(extend(self.missing, start, length, "1"),
2140 def add(self, start, data):
2141 self.missing = replace(extend(self.missing, start, len(data), "1"),
2142 start, "0"*len(data))
2143 self.data = replace(extend(self.data, start, len(data), " "),
2147 class StringSpans(unittest.TestCase):
2148 def do_basic(self, klass):
2150 self.failUnlessEqual(ds.len(), 0)
2151 self.failUnlessEqual(list(ds._dump()), [])
2152 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
2154 self.failUnlessEqual(ds.get(0, 4), None)
2155 self.failUnlessEqual(ds.pop(0, 4), None)
2159 self.failUnlessEqual(ds.len(), 4)
2160 self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
2161 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2163 self.failUnless((2,2) in s1)
2164 self.failUnlessEqual(ds.get(0, 4), None)
2165 self.failUnlessEqual(ds.pop(0, 4), None)
2166 self.failUnlessEqual(ds.get(4, 4), None)
2169 self.failUnlessEqual(ds2.len(), 4)
2170 self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2171 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2172 self.failUnlessEqual(ds2.get(0, 4), None)
2173 self.failUnlessEqual(ds2.pop(0, 4), None)
2174 self.failUnlessEqual(ds2.pop(2, 3), "fou")
2175 self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2176 self.failUnlessEqual(ds2.get(2, 3), None)
2177 self.failUnlessEqual(ds2.get(5, 1), "r")
2178 self.failUnlessEqual(ds.get(2, 3), "fou")
2179 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2182 self.failUnlessEqual(ds.len(), 6)
2183 self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2184 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2185 self.failUnlessEqual(ds.get(0, 4), "23fo")
2186 self.failUnlessEqual(ds.pop(0, 4), "23fo")
2187 self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2188 self.failUnlessEqual(ds.get(0, 4), None)
2189 self.failUnlessEqual(ds.pop(0, 4), None)
2194 self.failUnlessEqual(ds.get(2, 4), "fear")
2199 self.failUnlessEqual(ds.get(2L, 4L), "fear")
2202 def do_scan(self, klass):
2203 # do a test with gaps and spans of size 1 and 2
2204 # left=(1,11) * right=(1,11) * gapsize=(1,2)
2205 # 111, 112, 121, 122, 211, 212, 221, 222
2214 # 11 1 1 11 11 11 1 1 111
2215 # 0123456789012345678901234567
2216 # abcdefghijklmnopqrstuvwxyz-=
2217 pieces = [(1, "bc"),
2227 p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2228 S = "abcdefghijklmnopqrstuvwxyz-="
2229 # TODO: when adding data, add capital letters, to make sure we aren't
2230 # just leaving the old data in place
2234 for start, data in pieces:
2239 d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2243 for start in range(0, l):
2244 for end in range(start+1, l):
2245 # add [start-end) to the baseline
2246 which = "%d-%d" % (start, end-1)
2247 p_added = set(range(start, end))
2251 print dump(b), which
2252 add = klass(); add.add(start, S[start:end])
2254 b.add(start, S[start:end])
2257 # check that the new span is there
2258 d = b.get(start, end-start)
2259 self.failUnlessEqual(d, S[start:end], which)
2260 # check that all the original pieces are still there
2261 for t_start, t_data in pieces:
2263 self.failUnlessEqual(b.get(t_start, t_len),
2264 S[t_start:t_start+t_len],
2265 "%s %d+%d" % (which, t_start, t_len))
2266 # check that a lot of subspans are mostly correct
2267 for t_start in range(l):
2268 for t_len in range(1,4):
2269 d = b.get(t_start, t_len)
2271 which2 = "%s+(%d-%d)" % (which, t_start,
2273 self.failUnlessEqual(d, S[t_start:t_start+t_len],
2275 # check that removing a subspan gives the right value
2277 b2.remove(t_start, t_len)
2278 removed = set(range(t_start, t_start+t_len))
2280 exp = (((i in p_elements) or (i in p_added))
2281 and (i not in removed))
2282 which2 = "%s-(%d-%d)" % (which, t_start,
2284 self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2287 def test_test(self):
2288 self.do_basic(SimpleDataSpans)
2289 self.do_scan(SimpleDataSpans)
2291 def test_basic(self):
2292 self.do_basic(DataSpans)
2293 self.do_scan(DataSpans)
2295 def test_random(self):
2296 # attempt to increase coverage of corner cases by comparing behavior
2297 # of a simple-but-slow model implementation against the
2298 # complex-but-fast actual implementation, in a large number of random
2300 S1 = SimpleDataSpans
2302 s1 = S1(); s2 = S2()
2304 def _randstr(length, seed):
2307 while created < length:
2308 piece = _hash(seed + str(created)).hexdigest()
2309 pieces.append(piece)
2310 created += len(piece)
2311 return "".join(pieces)[:length]
2312 def _create(subseed):
2313 ns1 = S1(); ns2 = S2()
2315 what = _hash(subseed+str(i)).hexdigest()
2316 start = int(what[2:4], 16)
2317 length = max(1,int(what[5:6], 16))
2318 ns1.add(start, _randstr(length, what[7:9]));
2319 ns2.add(start, _randstr(length, what[7:9]))
2323 for i in range(1000):
2324 what = _hash(seed+str(i)).hexdigest()
2327 start = int(what[2:4], 16)
2328 length = max(1,int(what[5:6], 16))
2331 if subop in "0123456":
2332 s1 = S1(); s2 = S2()
2334 s1, s2 = _create(what[7:11])
2335 #print "s2 = %s" % list(s2._dump())
2336 elif op in "123456":
2337 #print "s2.add(%d,%d)" % (start, length)
2338 s1.add(start, _randstr(length, what[7:9]));
2339 s2.add(start, _randstr(length, what[7:9]))
2340 elif op in "789abc":
2341 #print "s2.remove(%d,%d)" % (start, length)
2342 s1.remove(start, length); s2.remove(start, length)
2344 #print "s2.pop(%d,%d)" % (start, length)
2345 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2346 self.failUnlessEqual(d1, d2)
2347 #print "s1 now %s" % list(s1._dump())
2348 #print "s2 now %s" % list(s2._dump())
2349 self.failUnlessEqual(s1.len(), s2.len())
2350 self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2351 for j in range(100):
2352 what = _hash(what[12:14]+str(j)).hexdigest()
2353 start = int(what[2:4], 16)
2354 length = max(1, int(what[5:6], 16))
2355 d1 = s1.get(start, length); d2 = s2.get(start, length)
2356 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))