src/allmydata/test/test_util.py

   1
   2 def foo(): pass # keep the line number constant
   3
   4 import os, time, sys
   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
  11
  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
  19 class Base32(unittest.TestCase):
  20     def test_b2a_matches_Pythons(self):
  21         import base64
  22         y = "\x12\x34\x45\x67\x89\x0a\xbc\xde\xf0"
  23         x = base64.b32encode(y)
  24         while x and x[-1] == '=':
  25             x = x[:-1]
  26         x = x.lower()
  27         self.failUnlessEqual(base32.b2a(y), x)
  28     def test_b2a(self):
  29         self.failUnlessEqual(base32.b2a("\x12\x34"), "ci2a")
  30     def test_b2a_or_none(self):
  31         self.failUnlessEqual(base32.b2a_or_none(None), None)
  32         self.failUnlessEqual(base32.b2a_or_none("\x12\x34"), "ci2a")
  33     def test_a2b(self):
  34         self.failUnlessEqual(base32.a2b("ci2a"), "\x12\x34")
  35         self.failUnlessRaises(AssertionError, base32.a2b, "b0gus")
  36
  37 class IDLib(unittest.TestCase):
  38     def test_nodeid_b2a(self):
  39         self.failUnlessEqual(idlib.nodeid_b2a("\x00"*20), "a"*32)
  40
  41 class NoArgumentException(Exception):
  42     def __init__(self):
  43         pass
  44
  45 class HumanReadable(unittest.TestCase):
  46     def test_repr(self):
  47         hr = humanreadable.hr
  48         self.failUnlessEqual(hr(foo), "<foo() at test_util.py:2>")
  49         self.failUnlessEqual(hr(self.test_repr),
  50                              "<bound method HumanReadable.test_repr of <allmydata.test.test_util.HumanReadable testMethod=test_repr>>")
  51         self.failUnlessEqual(hr(1L), "1")
  52         self.failUnlessEqual(hr(10**40),
  53                              "100000000000000000...000000000000000000")
  54         self.failUnlessEqual(hr(self), "<allmydata.test.test_util.HumanReadable testMethod=test_repr>")
  55         self.failUnlessEqual(hr([1,2]), "[1, 2]")
  56         self.failUnlessEqual(hr({1:2}), "{1:2}")
  57         try:
  58             raise ValueError
  59         except Exception, e:
  60             self.failUnless(
  61                 hr(e) == "<ValueError: ()>" # python-2.4
  62                 or hr(e) == "ValueError()") # python-2.5
  63         try:
  64             raise ValueError("oops")
  65         except Exception, e:
  66             self.failUnless(
  67                 hr(e) == "<ValueError: 'oops'>" # python-2.4
  68                 or hr(e) == "ValueError('oops',)") # python-2.5
  69         try:
  70             raise NoArgumentException
  71         except Exception, e:
  72             self.failUnless(
  73                 hr(e) == "<NoArgumentException>" # python-2.4
  74                 or hr(e) == "NoArgumentException()") # python-2.5
  75
  76
  77 class MyList(list):
  78     pass
  79
  80 class Math(unittest.TestCase):
  81     def test_div_ceil(self):
  82         f = mathutil.div_ceil
  83         self.failUnlessEqual(f(0, 1), 0)
  84         self.failUnlessEqual(f(0, 2), 0)
  85         self.failUnlessEqual(f(0, 3), 0)
  86         self.failUnlessEqual(f(1, 3), 1)
  87         self.failUnlessEqual(f(2, 3), 1)
  88         self.failUnlessEqual(f(3, 3), 1)
  89         self.failUnlessEqual(f(4, 3), 2)
  90         self.failUnlessEqual(f(5, 3), 2)
  91         self.failUnlessEqual(f(6, 3), 2)
  92         self.failUnlessEqual(f(7, 3), 3)
  93
  94     def test_next_multiple(self):
  95         f = mathutil.next_multiple
  96         self.failUnlessEqual(f(5, 1), 5)
  97         self.failUnlessEqual(f(5, 2), 6)
  98         self.failUnlessEqual(f(5, 3), 6)
  99         self.failUnlessEqual(f(5, 4), 8)
 100         self.failUnlessEqual(f(5, 5), 5)
 101         self.failUnlessEqual(f(5, 6), 6)
 102         self.failUnlessEqual(f(32, 1), 32)
 103         self.failUnlessEqual(f(32, 2), 32)
 104         self.failUnlessEqual(f(32, 3), 33)
 105         self.failUnlessEqual(f(32, 4), 32)
 106         self.failUnlessEqual(f(32, 5), 35)
 107         self.failUnlessEqual(f(32, 6), 36)
 108         self.failUnlessEqual(f(32, 7), 35)
 109         self.failUnlessEqual(f(32, 8), 32)
 110         self.failUnlessEqual(f(32, 9), 36)
 111         self.failUnlessEqual(f(32, 10), 40)
 112         self.failUnlessEqual(f(32, 11), 33)
 113         self.failUnlessEqual(f(32, 12), 36)
 114         self.failUnlessEqual(f(32, 13), 39)
 115         self.failUnlessEqual(f(32, 14), 42)
 116         self.failUnlessEqual(f(32, 15), 45)
 117         self.failUnlessEqual(f(32, 16), 32)
 118         self.failUnlessEqual(f(32, 17), 34)
 119         self.failUnlessEqual(f(32, 18), 36)
 120         self.failUnlessEqual(f(32, 589), 589)
 121
 122     def test_pad_size(self):
 123         f = mathutil.pad_size
 124         self.failUnlessEqual(f(0, 4), 0)
 125         self.failUnlessEqual(f(1, 4), 3)
 126         self.failUnlessEqual(f(2, 4), 2)
 127         self.failUnlessEqual(f(3, 4), 1)
 128         self.failUnlessEqual(f(4, 4), 0)
 129         self.failUnlessEqual(f(5, 4), 3)
 130
 131     def test_is_power_of_k(self):
 132         f = mathutil.is_power_of_k
 133         for i in range(1, 100):
 134             if i in (1, 2, 4, 8, 16, 32, 64):
 135                 self.failUnless(f(i, 2), "but %d *is* a power of 2" % i)
 136             else:
 137                 self.failIf(f(i, 2), "but %d is *not* a power of 2" % i)
 138         for i in range(1, 100):
 139             if i in (1, 3, 9, 27, 81):
 140                 self.failUnless(f(i, 3), "but %d *is* a power of 3" % i)
 141             else:
 142                 self.failIf(f(i, 3), "but %d is *not* a power of 3" % i)
 143
 144     def test_next_power_of_k(self):
 145         f = mathutil.next_power_of_k
 146         self.failUnlessEqual(f(0,2), 1)
 147         self.failUnlessEqual(f(1,2), 1)
 148         self.failUnlessEqual(f(2,2), 2)
 149         self.failUnlessEqual(f(3,2), 4)
 150         self.failUnlessEqual(f(4,2), 4)
 151         for i in range(5, 8): self.failUnlessEqual(f(i,2), 8, "%d" % i)
 152         for i in range(9, 16): self.failUnlessEqual(f(i,2), 16, "%d" % i)
 153         for i in range(17, 32): self.failUnlessEqual(f(i,2), 32, "%d" % i)
 154         for i in range(33, 64): self.failUnlessEqual(f(i,2), 64, "%d" % i)
 155         for i in range(65, 100): self.failUnlessEqual(f(i,2), 128, "%d" % i)
 156
 157         self.failUnlessEqual(f(0,3), 1)
 158         self.failUnlessEqual(f(1,3), 1)
 159         self.failUnlessEqual(f(2,3), 3)
 160         self.failUnlessEqual(f(3,3), 3)
 161         for i in range(4, 9): self.failUnlessEqual(f(i,3), 9, "%d" % i)
 162         for i in range(10, 27): self.failUnlessEqual(f(i,3), 27, "%d" % i)
 163         for i in range(28, 81): self.failUnlessEqual(f(i,3), 81, "%d" % i)
 164         for i in range(82, 200): self.failUnlessEqual(f(i,3), 243, "%d" % i)
 165
 166     def test_ave(self):
 167         f = mathutil.ave
 168         self.failUnlessEqual(f([1,2,3]), 2)
 169         self.failUnlessEqual(f([0,0,0,4]), 1)
 170         self.failUnlessAlmostEqual(f([0.0, 1.0, 1.0]), .666666666666)
 171
 172     def test_round_sigfigs(self):
 173         f = mathutil.round_sigfigs
 174         self.failUnlessEqual(f(22.0/3, 4), 7.3330000000000002)
 175
 176 class Statistics(unittest.TestCase):
 177     def should_assert(self, msg, func, *args, **kwargs):
 178         try:
 179             func(*args, **kwargs)
 180             self.fail(msg)
 181         except AssertionError:
 182             pass
 183
 184     def failUnlessListEqual(self, a, b, msg = None):
 185         self.failUnlessEqual(len(a), len(b))
 186         for i in range(len(a)):
 187             self.failUnlessEqual(a[i], b[i], msg)
 188
 189     def failUnlessListAlmostEqual(self, a, b, places = 7, msg = None):
 190         self.failUnlessEqual(len(a), len(b))
 191         for i in range(len(a)):
 192             self.failUnlessAlmostEqual(a[i], b[i], places, msg)
 193
 194     def test_binomial_coeff(self):
 195         f = statistics.binomial_coeff
 196         self.failUnlessEqual(f(20, 0), 1)
 197         self.failUnlessEqual(f(20, 1), 20)
 198         self.failUnlessEqual(f(20, 2), 190)
 199         self.failUnlessEqual(f(20, 8), f(20, 12))
 200         self.should_assert("Should assert if n < k", f, 2, 3)
 201
 202     def test_binomial_distribution_pmf(self):
 203         f = statistics.binomial_distribution_pmf
 204
 205         pmf_comp = f(2, .1)
 206         pmf_stat = [0.81, 0.18, 0.01]
 207         self.failUnlessListAlmostEqual(pmf_comp, pmf_stat)
 208
 209         # Summing across a PMF should give the total probability 1
 210         self.failUnlessAlmostEqual(sum(pmf_comp), 1)
 211         self.should_assert("Should assert if not 0<=p<=1", f, 1, -1)
 212         self.should_assert("Should assert if n < 1", f, 0, .1)
 213
 214         out = StringIO()
 215         statistics.print_pmf(pmf_comp, out=out)
 216         lines = out.getvalue().splitlines()
 217         self.failUnlessEqual(lines[0], "i=0: 0.81")
 218         self.failUnlessEqual(lines[1], "i=1: 0.18")
 219         self.failUnlessEqual(lines[2], "i=2: 0.01")
 220
 221     def test_survival_pmf(self):
 222         f = statistics.survival_pmf
 223         # Cross-check binomial-distribution method against convolution
 224         # method.
 225         p_list = [.9999] * 100 + [.99] * 50 + [.8] * 20
 226         pmf1 = statistics.survival_pmf_via_conv(p_list)
 227         pmf2 = statistics.survival_pmf_via_bd(p_list)
 228         self.failUnlessListAlmostEqual(pmf1, pmf2)
 229         self.failUnlessTrue(statistics.valid_pmf(pmf1))
 230         self.should_assert("Should assert if p_i > 1", f, [1.1]);
 231         self.should_assert("Should assert if p_i < 0", f, [-.1]);
 232
 233     def test_repair_count_pmf(self):
 234         survival_pmf = statistics.binomial_distribution_pmf(5, .9)
 235         repair_pmf = statistics.repair_count_pmf(survival_pmf, 3)
 236         # repair_pmf[0] == sum(survival_pmf[0,1,2,5])
 237         # repair_pmf[1] == survival_pmf[4]
 238         # repair_pmf[2] = survival_pmf[3]
 239         self.failUnlessListAlmostEqual(repair_pmf,
 240                                        [0.00001 + 0.00045 + 0.0081 + 0.59049,
 241                                         .32805,
 242                                         .0729,
 243                                         0, 0, 0])
 244
 245     def test_repair_cost(self):
 246         survival_pmf = statistics.binomial_distribution_pmf(5, .9)
 247         bwcost = statistics.bandwidth_cost_function
 248         cost = statistics.mean_repair_cost(bwcost, 1000,
 249                                            survival_pmf, 3, ul_dl_ratio=1.0)
 250         self.failUnlessAlmostEqual(cost, 558.90)
 251         cost = statistics.mean_repair_cost(bwcost, 1000,
 252                                            survival_pmf, 3, ul_dl_ratio=8.0)
 253         self.failUnlessAlmostEqual(cost, 1664.55)
 254
 255         # I haven't manually checked the math beyond here -warner
 256         cost = statistics.eternal_repair_cost(bwcost, 1000,
 257                                               survival_pmf, 3,
 258                                               discount_rate=0, ul_dl_ratio=1.0)
 259         self.failUnlessAlmostEqual(cost, 65292.056074766246)
 260         cost = statistics.eternal_repair_cost(bwcost, 1000,
 261                                               survival_pmf, 3,
 262                                               discount_rate=0.05,
 263                                               ul_dl_ratio=1.0)
 264         self.failUnlessAlmostEqual(cost, 9133.6097158191551)
 265
 266     def test_convolve(self):
 267         f = statistics.convolve
 268         v1 = [ 1, 2, 3 ]
 269         v2 = [ 4, 5, 6 ]
 270         v3 = [ 7, 8 ]
 271         v1v2result = [ 4, 13, 28, 27, 18 ]
 272         # Convolution is commutative
 273         r1 = f(v1, v2)
 274         r2 = f(v2, v1)
 275         self.failUnlessListEqual(r1, r2, "Convolution should be commutative")
 276         self.failUnlessListEqual(r1, v1v2result, "Didn't match known result")
 277         # Convolution is associative
 278         r1 = f(f(v1, v2), v3)
 279         r2 = f(v1, f(v2, v3))
 280         self.failUnlessListEqual(r1, r2, "Convolution should be associative")
 281         # Convolution is distributive
 282         r1 = f(v3, [ a + b for a, b in zip(v1, v2) ])
 283         tmp1 = f(v3, v1)
 284         tmp2 = f(v3, v2)
 285         r2 = [ a + b for a, b in zip(tmp1, tmp2) ]
 286         self.failUnlessListEqual(r1, r2, "Convolution should be distributive")
 287         # Convolution is scalar multiplication associative
 288         tmp1 = f(v1, v2)
 289         r1 = [ a * 4 for a in tmp1 ]
 290         tmp2 = [ a * 4 for a in v1 ]
 291         r2 = f(tmp2, v2)
 292         self.failUnlessListEqual(r1, r2, "Convolution should be scalar multiplication associative")
 293
 294     def test_find_k(self):
 295         f = statistics.find_k
 296         g = statistics.pr_file_loss
 297         plist = [.9] * 10 + [.8] * 10 # N=20
 298         t = .0001
 299         k = f(plist, t)
 300         self.failUnlessEqual(k, 10)
 301         self.failUnless(g(plist, k) < t)
 302
 303     def test_pr_file_loss(self):
 304         f = statistics.pr_file_loss
 305         plist = [.5] * 10
 306         self.failUnlessEqual(f(plist, 3), .0546875)
 307
 308     def test_pr_backup_file_loss(self):
 309         f = statistics.pr_backup_file_loss
 310         plist = [.5] * 10
 311         self.failUnlessEqual(f(plist, .5, 3), .02734375)
 312
 313
 314 class Asserts(unittest.TestCase):
 315     def should_assert(self, func, *args, **kwargs):
 316         try:
 317             func(*args, **kwargs)
 318         except AssertionError, e:
 319             return str(e)
 320         except Exception, e:
 321             self.fail("assert failed with non-AssertionError: %s" % e)
 322         self.fail("assert was not caught")
 323
 324     def should_not_assert(self, func, *args, **kwargs):
 325         try:
 326             func(*args, **kwargs)
 327         except AssertionError, e:
 328             self.fail("assertion fired when it should not have: %s" % e)
 329         except Exception, e:
 330             self.fail("assertion (which shouldn't have failed) failed with non-AssertionError: %s" % e)
 331         return # we're happy
 332
 333
 334     def test_assert(self):
 335         f = assertutil._assert
 336         self.should_assert(f)
 337         self.should_assert(f, False)
 338         self.should_not_assert(f, True)
 339
 340         m = self.should_assert(f, False, "message")
 341         self.failUnlessEqual(m, "'message' <type 'str'>", m)
 342         m = self.should_assert(f, False, "message1", othermsg=12)
 343         self.failUnlessEqual("'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 344         m = self.should_assert(f, False, othermsg="message2")
 345         self.failUnlessEqual("othermsg: 'message2' <type 'str'>", m)
 346
 347     def test_precondition(self):
 348         f = assertutil.precondition
 349         self.should_assert(f)
 350         self.should_assert(f, False)
 351         self.should_not_assert(f, True)
 352
 353         m = self.should_assert(f, False, "message")
 354         self.failUnlessEqual("precondition: 'message' <type 'str'>", m)
 355         m = self.should_assert(f, False, "message1", othermsg=12)
 356         self.failUnlessEqual("precondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 357         m = self.should_assert(f, False, othermsg="message2")
 358         self.failUnlessEqual("precondition: othermsg: 'message2' <type 'str'>", m)
 359
 360     def test_postcondition(self):
 361         f = assertutil.postcondition
 362         self.should_assert(f)
 363         self.should_assert(f, False)
 364         self.should_not_assert(f, True)
 365
 366         m = self.should_assert(f, False, "message")
 367         self.failUnlessEqual("postcondition: 'message' <type 'str'>", m)
 368         m = self.should_assert(f, False, "message1", othermsg=12)
 369         self.failUnlessEqual("postcondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 370         m = self.should_assert(f, False, othermsg="message2")
 371         self.failUnlessEqual("postcondition: othermsg: 'message2' <type 'str'>", m)
 372
 373 class FileUtil(unittest.TestCase):
 374     def mkdir(self, basedir, path, mode=0777):
 375         fn = os.path.join(basedir, path)
 376         fileutil.make_dirs(fn, mode)
 377
 378     def touch(self, basedir, path, mode=None, data="touch\n"):
 379         fn = os.path.join(basedir, path)
 380         f = open(fn, "w")
 381         f.write(data)
 382         f.close()
 383         if mode is not None:
 384             os.chmod(fn, mode)
 385
 386     def test_rm_dir(self):
 387         basedir = "util/FileUtil/test_rm_dir"
 388         fileutil.make_dirs(basedir)
 389         # create it again to test idempotency
 390         fileutil.make_dirs(basedir)
 391         d = os.path.join(basedir, "doomed")
 392         self.mkdir(d, "a/b")
 393         self.touch(d, "a/b/1.txt")
 394         self.touch(d, "a/b/2.txt", 0444)
 395         self.touch(d, "a/b/3.txt", 0)
 396         self.mkdir(d, "a/c")
 397         self.touch(d, "a/c/1.txt")
 398         self.touch(d, "a/c/2.txt", 0444)
 399         self.touch(d, "a/c/3.txt", 0)
 400         os.chmod(os.path.join(d, "a/c"), 0444)
 401         self.mkdir(d, "a/d")
 402         self.touch(d, "a/d/1.txt")
 403         self.touch(d, "a/d/2.txt", 0444)
 404         self.touch(d, "a/d/3.txt", 0)
 405         os.chmod(os.path.join(d, "a/d"), 0)
 406
 407         fileutil.rm_dir(d)
 408         self.failIf(os.path.exists(d))
 409         # remove it again to test idempotency
 410         fileutil.rm_dir(d)
 411
 412     def test_remove_if_possible(self):
 413         basedir = "util/FileUtil/test_remove_if_possible"
 414         fileutil.make_dirs(basedir)
 415         self.touch(basedir, "here")
 416         fn = os.path.join(basedir, "here")
 417         fileutil.remove_if_possible(fn)
 418         self.failIf(os.path.exists(fn))
 419         fileutil.remove_if_possible(fn) # should be idempotent
 420         fileutil.rm_dir(basedir)
 421         fileutil.remove_if_possible(fn) # should survive errors
 422
 423     def test_write_atomically(self):
 424         basedir = "util/FileUtil/test_write_atomically"
 425         fileutil.make_dirs(basedir)
 426         fn = os.path.join(basedir, "here")
 427         fileutil.write_atomically(fn, "one")
 428         self.failUnlessEqual(fileutil.read(fn), "one")
 429         fileutil.write_atomically(fn, "two", mode="") # non-binary
 430         self.failUnlessEqual(fileutil.read(fn), "two")
 431
 432     def test_open_or_create(self):
 433         basedir = "util/FileUtil/test_open_or_create"
 434         fileutil.make_dirs(basedir)
 435         fn = os.path.join(basedir, "here")
 436         f = fileutil.open_or_create(fn)
 437         f.write("stuff.")
 438         f.close()
 439         f = fileutil.open_or_create(fn)
 440         f.seek(0, os.SEEK_END)
 441         f.write("more.")
 442         f.close()
 443         f = open(fn, "r")
 444         data = f.read()
 445         f.close()
 446         self.failUnlessEqual(data, "stuff.more.")
 447
 448     def test_NamedTemporaryDirectory(self):
 449         basedir = "util/FileUtil/test_NamedTemporaryDirectory"
 450         fileutil.make_dirs(basedir)
 451         td = fileutil.NamedTemporaryDirectory(dir=basedir)
 452         name = td.name
 453         self.failUnless(basedir in name)
 454         self.failUnless(basedir in repr(td))
 455         self.failUnless(os.path.isdir(name))
 456         del td
 457         # it is conceivable that we need to force gc here, but I'm not sure
 458         self.failIf(os.path.isdir(name))
 459
 460     def test_rename(self):
 461         basedir = "util/FileUtil/test_rename"
 462         fileutil.make_dirs(basedir)
 463         self.touch(basedir, "here")
 464         fn = os.path.join(basedir, "here")
 465         fn2 = os.path.join(basedir, "there")
 466         fileutil.rename(fn, fn2)
 467         self.failIf(os.path.exists(fn))
 468         self.failUnless(os.path.exists(fn2))
 469
 470     def test_du(self):
 471         basedir = "util/FileUtil/test_du"
 472         fileutil.make_dirs(basedir)
 473         d = os.path.join(basedir, "space-consuming")
 474         self.mkdir(d, "a/b")
 475         self.touch(d, "a/b/1.txt", data="a"*10)
 476         self.touch(d, "a/b/2.txt", data="b"*11)
 477         self.mkdir(d, "a/c")
 478         self.touch(d, "a/c/1.txt", data="c"*12)
 479         self.touch(d, "a/c/2.txt", data="d"*13)
 480
 481         used = fileutil.du(basedir)
 482         self.failUnlessEqual(10+11+12+13, used)
 483
 484     def test_abspath_expanduser_unicode(self):
 485         self.failUnlessRaises(AssertionError, fileutil.abspath_expanduser_unicode, "bytestring")
 486
 487         saved_cwd = os.path.normpath(os.getcwdu())
 488         abspath_cwd = fileutil.abspath_expanduser_unicode(u".")
 489         self.failUnless(isinstance(saved_cwd, unicode), saved_cwd)
 490         self.failUnless(isinstance(abspath_cwd, unicode), abspath_cwd)
 491         self.failUnlessEqual(abspath_cwd, saved_cwd)
 492
 493         # adapted from <http://svn.python.org/view/python/branches/release26-maint/Lib/test/test_posixpath.py?view=markup&pathrev=78279#test_abspath>
 494
 495         self.failUnlessIn(u"foo", fileutil.abspath_expanduser_unicode(u"foo"))
 496         self.failIfIn(u"~", fileutil.abspath_expanduser_unicode(u"~"))
 497
 498         cwds = ['cwd']
 499         try:
 500             cwds.append(u'\xe7w\xf0'.encode(sys.getfilesystemencoding()
 501                                             or 'ascii'))
 502         except UnicodeEncodeError:
 503             pass # the cwd can't be encoded -- test with ascii cwd only
 504
 505         for cwd in cwds:
 506             try:
 507                 os.mkdir(cwd)
 508                 os.chdir(cwd)
 509                 for upath in (u'', u'fuu', u'f\xf9\xf9', u'/fuu', u'U:\\', u'~'):
 510                     uabspath = fileutil.abspath_expanduser_unicode(upath)
 511                     self.failUnless(isinstance(uabspath, unicode), uabspath)
 512             finally:
 513                 os.chdir(saved_cwd)
 514
 515     def test_disk_stats(self):
 516         avail = fileutil.get_available_space('.', 2**14)
 517         if avail == 0:
 518             raise unittest.SkipTest("This test will spuriously fail there is no disk space left.")
 519
 520         disk = fileutil.get_disk_stats('.', 2**13)
 521         self.failUnless(disk['total'] > 0, disk['total'])
 522         self.failUnless(disk['used'] > 0, disk['used'])
 523         self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
 524         self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
 525         self.failUnless(disk['avail'] > 0, disk['avail'])
 526
 527     def test_disk_stats_avail_nonnegative(self):
 528         # This test will spuriously fail if you have more than 2^128
 529         # bytes of available space on your filesystem.
 530         disk = fileutil.get_disk_stats('.', 2**128)
 531         self.failUnlessEqual(disk['avail'], 0)
 532
 533 class PollMixinTests(unittest.TestCase):
 534     def setUp(self):
 535         self.pm = pollmixin.PollMixin()
 536
 537     def test_PollMixin_True(self):
 538         d = self.pm.poll(check_f=lambda : True,
 539                          pollinterval=0.1)
 540         return d
 541
 542     def test_PollMixin_False_then_True(self):
 543         i = iter([False, True])
 544         d = self.pm.poll(check_f=i.next,
 545                          pollinterval=0.1)
 546         return d
 547
 548     def test_timeout(self):
 549         d = self.pm.poll(check_f=lambda: False,
 550                          pollinterval=0.01,
 551                          timeout=1)
 552         def _suc(res):
 553             self.fail("poll should have failed, not returned %s" % (res,))
 554         def _err(f):
 555             f.trap(pollmixin.TimeoutError)
 556             return None # success
 557         d.addCallbacks(_suc, _err)
 558         return d
 559
 560 class DeferredUtilTests(unittest.TestCase):
 561     def test_gather_results(self):
 562         d1 = defer.Deferred()
 563         d2 = defer.Deferred()
 564         res = deferredutil.gatherResults([d1, d2])
 565         d1.errback(ValueError("BAD"))
 566         def _callb(res):
 567             self.fail("Should have errbacked, not resulted in %s" % (res,))
 568         def _errb(thef):
 569             thef.trap(ValueError)
 570         res.addCallbacks(_callb, _errb)
 571         return res
 572
 573     def test_success(self):
 574         d1, d2 = defer.Deferred(), defer.Deferred()
 575         good = []
 576         bad = []
 577         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 578         dlss.addCallbacks(good.append, bad.append)
 579         d1.callback(1)
 580         d2.callback(2)
 581         self.failUnlessEqual(good, [[1,2]])
 582         self.failUnlessEqual(bad, [])
 583
 584     def test_failure(self):
 585         d1, d2 = defer.Deferred(), defer.Deferred()
 586         good = []
 587         bad = []
 588         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 589         dlss.addCallbacks(good.append, bad.append)
 590         d1.addErrback(lambda _ignore: None)
 591         d2.addErrback(lambda _ignore: None)
 592         d1.callback(1)
 593         d2.errback(ValueError())
 594         self.failUnlessEqual(good, [])
 595         self.failUnlessEqual(len(bad), 1)
 596         f = bad[0]
 597         self.failUnless(isinstance(f, Failure))
 598         self.failUnless(f.check(ValueError))
 599
 600 class HashUtilTests(unittest.TestCase):
 601
 602     def test_random_key(self):
 603         k = hashutil.random_key()
 604         self.failUnlessEqual(len(k), hashutil.KEYLEN)
 605
 606     def test_sha256d(self):
 607         h1 = hashutil.tagged_hash("tag1", "value")
 608         h2 = hashutil.tagged_hasher("tag1")
 609         h2.update("value")
 610         h2a = h2.digest()
 611         h2b = h2.digest()
 612         self.failUnlessEqual(h1, h2a)
 613         self.failUnlessEqual(h2a, h2b)
 614
 615     def test_sha256d_truncated(self):
 616         h1 = hashutil.tagged_hash("tag1", "value", 16)
 617         h2 = hashutil.tagged_hasher("tag1", 16)
 618         h2.update("value")
 619         h2 = h2.digest()
 620         self.failUnlessEqual(len(h1), 16)
 621         self.failUnlessEqual(len(h2), 16)
 622         self.failUnlessEqual(h1, h2)
 623
 624     def test_chk(self):
 625         h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
 626         h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
 627         h2.update("data")
 628         h2 = h2.digest()
 629         self.failUnlessEqual(h1, h2)
 630
 631     def test_hashers(self):
 632         h1 = hashutil.block_hash("foo")
 633         h2 = hashutil.block_hasher()
 634         h2.update("foo")
 635         self.failUnlessEqual(h1, h2.digest())
 636
 637         h1 = hashutil.uri_extension_hash("foo")
 638         h2 = hashutil.uri_extension_hasher()
 639         h2.update("foo")
 640         self.failUnlessEqual(h1, h2.digest())
 641
 642         h1 = hashutil.plaintext_hash("foo")
 643         h2 = hashutil.plaintext_hasher()
 644         h2.update("foo")
 645         self.failUnlessEqual(h1, h2.digest())
 646
 647         h1 = hashutil.crypttext_hash("foo")
 648         h2 = hashutil.crypttext_hasher()
 649         h2.update("foo")
 650         self.failUnlessEqual(h1, h2.digest())
 651
 652         h1 = hashutil.crypttext_segment_hash("foo")
 653         h2 = hashutil.crypttext_segment_hasher()
 654         h2.update("foo")
 655         self.failUnlessEqual(h1, h2.digest())
 656
 657         h1 = hashutil.plaintext_segment_hash("foo")
 658         h2 = hashutil.plaintext_segment_hasher()
 659         h2.update("foo")
 660         self.failUnlessEqual(h1, h2.digest())
 661
 662     def test_constant_time_compare(self):
 663         self.failUnless(hashutil.constant_time_compare("a", "a"))
 664         self.failUnless(hashutil.constant_time_compare("ab", "ab"))
 665         self.failIf(hashutil.constant_time_compare("a", "b"))
 666         self.failIf(hashutil.constant_time_compare("a", "aa"))
 667
 668     def _testknown(self, hashf, expected_a, *args):
 669         got = hashf(*args)
 670         got_a = base32.b2a(got)
 671         self.failUnlessEqual(got_a, expected_a)
 672
 673     def test_known_answers(self):
 674         # assert backwards compatibility
 675         self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
 676         self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
 677         self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
 678         self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
 679         self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
 680         self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
 681         self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
 682         self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
 683         self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
 684         self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
 685         self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
 686         self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
 687         self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
 688         self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
 689         self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
 690         self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
 691         self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
 692         self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
 693         self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
 694         self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
 695         self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
 696         self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
 697         self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
 698
 699
 700 class Abbreviate(unittest.TestCase):
 701     def test_time(self):
 702         a = abbreviate.abbreviate_time
 703         self.failUnlessEqual(a(None), "unknown")
 704         self.failUnlessEqual(a(0), "0 seconds")
 705         self.failUnlessEqual(a(1), "1 second")
 706         self.failUnlessEqual(a(2), "2 seconds")
 707         self.failUnlessEqual(a(119), "119 seconds")
 708         MIN = 60
 709         self.failUnlessEqual(a(2*MIN), "2 minutes")
 710         self.failUnlessEqual(a(60*MIN), "60 minutes")
 711         self.failUnlessEqual(a(179*MIN), "179 minutes")
 712         HOUR = 60*MIN
 713         self.failUnlessEqual(a(180*MIN), "3 hours")
 714         self.failUnlessEqual(a(4*HOUR), "4 hours")
 715         DAY = 24*HOUR
 716         MONTH = 30*DAY
 717         self.failUnlessEqual(a(2*DAY), "2 days")
 718         self.failUnlessEqual(a(2*MONTH), "2 months")
 719         YEAR = 365*DAY
 720         self.failUnlessEqual(a(5*YEAR), "5 years")
 721
 722     def test_space(self):
 723         tests_si = [(None, "unknown"),
 724                     (0, "0 B"),
 725                     (1, "1 B"),
 726                     (999, "999 B"),
 727                     (1000, "1000 B"),
 728                     (1023, "1023 B"),
 729                     (1024, "1.02 kB"),
 730                     (20*1000, "20.00 kB"),
 731                     (1024*1024, "1.05 MB"),
 732                     (1000*1000, "1.00 MB"),
 733                     (1000*1000*1000, "1.00 GB"),
 734                     (1000*1000*1000*1000, "1.00 TB"),
 735                     (1000*1000*1000*1000*1000, "1.00 PB"),
 736                     (1234567890123456, "1.23 PB"),
 737                     ]
 738         for (x, expected) in tests_si:
 739             got = abbreviate.abbreviate_space(x, SI=True)
 740             self.failUnlessEqual(got, expected)
 741
 742         tests_base1024 = [(None, "unknown"),
 743                           (0, "0 B"),
 744                           (1, "1 B"),
 745                           (999, "999 B"),
 746                           (1000, "1000 B"),
 747                           (1023, "1023 B"),
 748                           (1024, "1.00 kiB"),
 749                           (20*1024, "20.00 kiB"),
 750                           (1000*1000, "976.56 kiB"),
 751                           (1024*1024, "1.00 MiB"),
 752                           (1024*1024*1024, "1.00 GiB"),
 753                           (1024*1024*1024*1024, "1.00 TiB"),
 754                           (1000*1000*1000*1000*1000, "909.49 TiB"),
 755                           (1024*1024*1024*1024*1024, "1.00 PiB"),
 756                           (1234567890123456, "1.10 PiB"),
 757                     ]
 758         for (x, expected) in tests_base1024:
 759             got = abbreviate.abbreviate_space(x, SI=False)
 760             self.failUnlessEqual(got, expected)
 761
 762         self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
 763                              "(1.23 MB, 1.18 MiB)")
 764
 765     def test_parse_space(self):
 766         p = abbreviate.parse_abbreviated_size
 767         self.failUnlessEqual(p(""), None)
 768         self.failUnlessEqual(p(None), None)
 769         self.failUnlessEqual(p("123"), 123)
 770         self.failUnlessEqual(p("123B"), 123)
 771         self.failUnlessEqual(p("2K"), 2000)
 772         self.failUnlessEqual(p("2kb"), 2000)
 773         self.failUnlessEqual(p("2KiB"), 2048)
 774         self.failUnlessEqual(p("10MB"), 10*1000*1000)
 775         self.failUnlessEqual(p("10MiB"), 10*1024*1024)
 776         self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
 777         self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
 778         self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
 779         self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
 780         self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
 781         self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
 782         self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
 783         self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
 784
 785         e = self.failUnlessRaises(ValueError, p, "12 cubits")
 786         self.failUnlessIn("12 cubits", str(e))
 787         e = self.failUnlessRaises(ValueError, p, "1 BB")
 788         self.failUnlessIn("1 BB", str(e))
 789         e = self.failUnlessRaises(ValueError, p, "fhtagn")
 790         self.failUnlessIn("fhtagn", str(e))
 791
 792 class Limiter(unittest.TestCase):
 793     timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
 794
 795     def job(self, i, foo):
 796         self.calls.append( (i, foo) )
 797         self.simultaneous += 1
 798         self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
 799         d = defer.Deferred()
 800         def _done():
 801             self.simultaneous -= 1
 802             d.callback("done %d" % i)
 803         reactor.callLater(1.0, _done)
 804         return d
 805
 806     def bad_job(self, i, foo):
 807         raise ValueError("bad_job %d" % i)
 808
 809     def test_limiter(self):
 810         self.calls = []
 811         self.simultaneous = 0
 812         self.peak_simultaneous = 0
 813         l = limiter.ConcurrencyLimiter()
 814         dl = []
 815         for i in range(20):
 816             dl.append(l.add(self.job, i, foo=str(i)))
 817         d = defer.DeferredList(dl, fireOnOneErrback=True)
 818         def _done(res):
 819             self.failUnlessEqual(self.simultaneous, 0)
 820             self.failUnless(self.peak_simultaneous <= 10)
 821             self.failUnlessEqual(len(self.calls), 20)
 822             for i in range(20):
 823                 self.failUnless( (i, str(i)) in self.calls)
 824         d.addCallback(_done)
 825         return d
 826
 827     def test_errors(self):
 828         self.calls = []
 829         self.simultaneous = 0
 830         self.peak_simultaneous = 0
 831         l = limiter.ConcurrencyLimiter()
 832         dl = []
 833         for i in range(20):
 834             dl.append(l.add(self.job, i, foo=str(i)))
 835         d2 = l.add(self.bad_job, 21, "21")
 836         d = defer.DeferredList(dl, fireOnOneErrback=True)
 837         def _most_done(res):
 838             results = []
 839             for (success, result) in res:
 840                 self.failUnlessEqual(success, True)
 841                 results.append(result)
 842             results.sort()
 843             expected_results = ["done %d" % i for i in range(20)]
 844             expected_results.sort()
 845             self.failUnlessEqual(results, expected_results)
 846             self.failUnless(self.peak_simultaneous <= 10)
 847             self.failUnlessEqual(len(self.calls), 20)
 848             for i in range(20):
 849                 self.failUnless( (i, str(i)) in self.calls)
 850             def _good(res):
 851                 self.fail("should have failed, not got %s" % (res,))
 852             def _err(f):
 853                 f.trap(ValueError)
 854                 self.failUnless("bad_job 21" in str(f))
 855             d2.addCallbacks(_good, _err)
 856             return d2
 857         d.addCallback(_most_done)
 858         def _all_done(res):
 859             self.failUnlessEqual(self.simultaneous, 0)
 860             self.failUnless(self.peak_simultaneous <= 10)
 861             self.failUnlessEqual(len(self.calls), 20)
 862             for i in range(20):
 863                 self.failUnless( (i, str(i)) in self.calls)
 864         d.addCallback(_all_done)
 865         return d
 866
 867 class TimeFormat(unittest.TestCase):
 868     def test_epoch(self):
 869         return self._help_test_epoch()
 870
 871     def test_epoch_in_London(self):
 872         # Europe/London is a particularly troublesome timezone.  Nowadays, its
 873         # offset from GMT is 0.  But in 1970, its offset from GMT was 1.
 874         # (Apparently in 1970 Britain had redefined standard time to be GMT+1
 875         # and stayed in standard time all year round, whereas today
 876         # Europe/London standard time is GMT and Europe/London Daylight
 877         # Savings Time is GMT+1.)  The current implementation of
 878         # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
 879         # Europe/London.  (As soon as this unit test is done then I'll change
 880         # that implementation to something that works even in this case...)
 881         origtz = os.environ.get('TZ')
 882         os.environ['TZ'] = "Europe/London"
 883         if hasattr(time, 'tzset'):
 884             time.tzset()
 885         try:
 886             return self._help_test_epoch()
 887         finally:
 888             if origtz is None:
 889                 del os.environ['TZ']
 890             else:
 891                 os.environ['TZ'] = origtz
 892             if hasattr(time, 'tzset'):
 893                 time.tzset()
 894
 895     def _help_test_epoch(self):
 896         origtzname = time.tzname
 897         s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
 898         self.failUnlessEqual(s, 1.0)
 899         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
 900         self.failUnlessEqual(s, 1.0)
 901         s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
 902         self.failUnlessEqual(s, 1.0)
 903
 904         self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
 905         self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
 906                              "1970-01-01 00:00:01")
 907
 908         now = time.time()
 909         isostr = time_format.iso_utc(now)
 910         timestamp = time_format.iso_utc_time_to_seconds(isostr)
 911         self.failUnlessEqual(int(timestamp), int(now))
 912
 913         def my_time():
 914             return 1.0
 915         self.failUnlessEqual(time_format.iso_utc(t=my_time),
 916                              "1970-01-01_00:00:01")
 917         e = self.failUnlessRaises(ValueError,
 918                                   time_format.iso_utc_time_to_seconds,
 919                                   "invalid timestring")
 920         self.failUnless("not a complete ISO8601 timestamp" in str(e))
 921         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
 922         self.failUnlessEqual(s, 1.5)
 923
 924         # Look for daylight-savings-related errors.
 925         thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
 926         self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
 927         self.failUnlessEqual(origtzname, time.tzname)
 928
 929     def test_iso_utc(self):
 930         when = 1266760143.7841301
 931         out = time_format.iso_utc_date(when)
 932         self.failUnlessEqual(out, "2010-02-21")
 933         out = time_format.iso_utc_date(t=lambda: when)
 934         self.failUnlessEqual(out, "2010-02-21")
 935         out = time_format.iso_utc(when)
 936         self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
 937         out = time_format.iso_utc(when, sep="-")
 938         self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
 939
 940     def test_parse_duration(self):
 941         p = time_format.parse_duration
 942         DAY = 24*60*60
 943         self.failUnlessEqual(p("1 day"), DAY)
 944         self.failUnlessEqual(p("2 days"), 2*DAY)
 945         self.failUnlessEqual(p("3 months"), 3*31*DAY)
 946         self.failUnlessEqual(p("4 mo"), 4*31*DAY)
 947         self.failUnlessEqual(p("5 years"), 5*365*DAY)
 948         e = self.failUnlessRaises(ValueError, p, "123")
 949         self.failUnlessIn("no unit (like day, month, or year) in '123'",
 950                           str(e))
 951
 952     def test_parse_date(self):
 953         self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
 954
 955 class CacheDir(unittest.TestCase):
 956     def test_basic(self):
 957         basedir = "test_util/CacheDir/test_basic"
 958
 959         def _failIfExists(name):
 960             absfn = os.path.join(basedir, name)
 961             self.failIf(os.path.exists(absfn),
 962                         "%s exists but it shouldn't" % absfn)
 963
 964         def _failUnlessExists(name):
 965             absfn = os.path.join(basedir, name)
 966             self.failUnless(os.path.exists(absfn),
 967                             "%s doesn't exist but it should" % absfn)
 968
 969         cdm = cachedir.CacheDirectoryManager(basedir)
 970         a = cdm.get_file("a")
 971         b = cdm.get_file("b")
 972         c = cdm.get_file("c")
 973         f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
 974         f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
 975         f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
 976
 977         _failUnlessExists("a")
 978         _failUnlessExists("b")
 979         _failUnlessExists("c")
 980
 981         cdm.check()
 982
 983         _failUnlessExists("a")
 984         _failUnlessExists("b")
 985         _failUnlessExists("c")
 986
 987         del a
 988         # this file won't be deleted yet, because it isn't old enough
 989         cdm.check()
 990         _failUnlessExists("a")
 991         _failUnlessExists("b")
 992         _failUnlessExists("c")
 993
 994         # we change the definition of "old" to make everything old
 995         cdm.old = -10
 996
 997         cdm.check()
 998         _failIfExists("a")
 999         _failUnlessExists("b")
1000         _failUnlessExists("c")
1001
1002         cdm.old = 60*60
1003
1004         del b
1005
1006         cdm.check()
1007         _failIfExists("a")
1008         _failUnlessExists("b")
1009         _failUnlessExists("c")
1010
1011         b2 = cdm.get_file("b")
1012
1013         cdm.check()
1014         _failIfExists("a")
1015         _failUnlessExists("b")
1016         _failUnlessExists("c")
1017         del b2
1018
1019 ctr = [0]
1020 class EqButNotIs:
1021     def __init__(self, x):
1022         self.x = x
1023         self.hash = ctr[0]
1024         ctr[0] += 1
1025     def __repr__(self):
1026         return "<%s %s>" % (self.__class__.__name__, self.x,)
1027     def __hash__(self):
1028         return self.hash
1029     def __le__(self, other):
1030         return self.x <= other
1031     def __lt__(self, other):
1032         return self.x < other
1033     def __ge__(self, other):
1034         return self.x >= other
1035     def __gt__(self, other):
1036         return self.x > other
1037     def __ne__(self, other):
1038         return self.x != other
1039     def __eq__(self, other):
1040         return self.x == other
1041
1042 class DictUtil(unittest.TestCase):
1043     def _help_test_empty_dict(self, klass):
1044         d1 = klass()
1045         d2 = klass({})
1046
1047         self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1048         self.failUnless(len(d1) == 0)
1049         self.failUnless(len(d2) == 0)
1050
1051     def _help_test_nonempty_dict(self, klass):
1052         d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1053         d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1054
1055         self.failUnless(d1 == d2)
1056         self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1057         self.failUnless(len(d2) == 3)
1058
1059     def _help_test_eq_but_notis(self, klass):
1060         d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1061         d.pop('b')
1062
1063         d.clear()
1064         d['a'] = 3
1065         d['b'] = EqButNotIs(3)
1066         d['c'] = 3
1067         d.pop('b')
1068
1069         d.clear()
1070         d['b'] = EqButNotIs(3)
1071         d['a'] = 3
1072         d['c'] = 3
1073         d.pop('b')
1074
1075         d.clear()
1076         d['a'] = EqButNotIs(3)
1077         d['c'] = 3
1078         d['a'] = 3
1079
1080         d.clear()
1081         fake3 = EqButNotIs(3)
1082         fake7 = EqButNotIs(7)
1083         d[fake3] = fake7
1084         d[3] = 7
1085         d[3] = 8
1086         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1087         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1088         # The real 7 should have been ejected by the d[3] = 8.
1089         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1090         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1091         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1092         d[fake3] = 8
1093
1094         d.clear()
1095         d[3] = 7
1096         fake3 = EqButNotIs(3)
1097         fake7 = EqButNotIs(7)
1098         d[fake3] = fake7
1099         d[3] = 8
1100         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1101         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1102         # The real 7 should have been ejected by the d[3] = 8.
1103         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1104         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1105         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1106         d[fake3] = 8
1107
1108     def test_all(self):
1109         self._help_test_eq_but_notis(dictutil.UtilDict)
1110         self._help_test_eq_but_notis(dictutil.NumDict)
1111         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1112         self._help_test_nonempty_dict(dictutil.UtilDict)
1113         self._help_test_nonempty_dict(dictutil.NumDict)
1114         self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1115         self._help_test_eq_but_notis(dictutil.UtilDict)
1116         self._help_test_eq_but_notis(dictutil.NumDict)
1117         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1118
1119     def test_dict_of_sets(self):
1120         ds = dictutil.DictOfSets()
1121         ds.add(1, "a")
1122         ds.add(2, "b")
1123         ds.add(2, "b")
1124         ds.add(2, "c")
1125         self.failUnlessEqual(ds[1], set(["a"]))
1126         self.failUnlessEqual(ds[2], set(["b", "c"]))
1127         ds.discard(3, "d") # should not raise an exception
1128         ds.discard(2, "b")
1129         self.failUnlessEqual(ds[2], set(["c"]))
1130         ds.discard(2, "c")
1131         self.failIf(2 in ds)
1132
1133         ds.add(3, "f")
1134         ds2 = dictutil.DictOfSets()
1135         ds2.add(3, "f")
1136         ds2.add(3, "g")
1137         ds2.add(4, "h")
1138         ds.update(ds2)
1139         self.failUnlessEqual(ds[1], set(["a"]))
1140         self.failUnlessEqual(ds[3], set(["f", "g"]))
1141         self.failUnlessEqual(ds[4], set(["h"]))
1142
1143     def test_move(self):
1144         d1 = {1: "a", 2: "b"}
1145         d2 = {2: "c", 3: "d"}
1146         dictutil.move(1, d1, d2)
1147         self.failUnlessEqual(d1, {2: "b"})
1148         self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1149
1150         d1 = {1: "a", 2: "b"}
1151         d2 = {2: "c", 3: "d"}
1152         dictutil.move(2, d1, d2)
1153         self.failUnlessEqual(d1, {1: "a"})
1154         self.failUnlessEqual(d2, {2: "b", 3: "d"})
1155
1156         d1 = {1: "a", 2: "b"}
1157         d2 = {2: "c", 3: "d"}
1158         self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1159
1160     def test_subtract(self):
1161         d1 = {1: "a", 2: "b"}
1162         d2 = {2: "c", 3: "d"}
1163         d3 = dictutil.subtract(d1, d2)
1164         self.failUnlessEqual(d3, {1: "a"})
1165
1166         d1 = {1: "a", 2: "b"}
1167         d2 = {2: "c"}
1168         d3 = dictutil.subtract(d1, d2)
1169         self.failUnlessEqual(d3, {1: "a"})
1170
1171     def test_utildict(self):
1172         d = dictutil.UtilDict({1: "a", 2: "b"})
1173         d.del_if_present(1)
1174         d.del_if_present(3)
1175         self.failUnlessEqual(d, {2: "b"})
1176         def eq(a, b):
1177             return a == b
1178         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1179
1180         d = dictutil.UtilDict({1: "b", 2: "a"})
1181         self.failUnlessEqual(d.items_sorted_by_value(),
1182                              [(2, "a"), (1, "b")])
1183         self.failUnlessEqual(d.items_sorted_by_key(),
1184                              [(1, "b"), (2, "a")])
1185         self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1186         self.failUnless(1 in d)
1187
1188         d2 = dictutil.UtilDict({3: "c", 4: "d"})
1189         self.failUnless(d != d2)
1190         self.failUnless(d2 > d)
1191         self.failUnless(d2 >= d)
1192         self.failUnless(d <= d2)
1193         self.failUnless(d < d2)
1194         self.failUnlessEqual(d[1], "b")
1195         self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1196
1197         d3 = d.copy()
1198         self.failUnlessEqual(d, d3)
1199         self.failUnless(isinstance(d3, dictutil.UtilDict))
1200
1201         d4 = d.fromkeys([3,4], "e")
1202         self.failUnlessEqual(d4, {3: "e", 4: "e"})
1203
1204         self.failUnlessEqual(d.get(1), "b")
1205         self.failUnlessEqual(d.get(3), None)
1206         self.failUnlessEqual(d.get(3, "default"), "default")
1207         self.failUnlessEqual(sorted(list(d.items())),
1208                              [(1, "b"), (2, "a")])
1209         self.failUnlessEqual(sorted(list(d.iteritems())),
1210                              [(1, "b"), (2, "a")])
1211         self.failUnlessEqual(sorted(d.keys()), [1, 2])
1212         self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1213         x = d.setdefault(1, "new")
1214         self.failUnlessEqual(x, "b")
1215         self.failUnlessEqual(d[1], "b")
1216         x = d.setdefault(3, "new")
1217         self.failUnlessEqual(x, "new")
1218         self.failUnlessEqual(d[3], "new")
1219         del d[3]
1220
1221         x = d.popitem()
1222         self.failUnless(x in [(1, "b"), (2, "a")])
1223         x = d.popitem()
1224         self.failUnless(x in [(1, "b"), (2, "a")])
1225         self.failUnlessRaises(KeyError, d.popitem)
1226
1227     def test_numdict(self):
1228         d = dictutil.NumDict({"a": 1, "b": 2})
1229
1230         d.add_num("a", 10, 5)
1231         d.add_num("c", 20, 5)
1232         d.add_num("d", 30)
1233         self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1234
1235         d.subtract_num("a", 10)
1236         d.subtract_num("e", 10)
1237         d.subtract_num("f", 10, 15)
1238         self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1239                                  "e": -10, "f": 5})
1240
1241         self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1242
1243         d = dictutil.NumDict()
1244         d.inc("a")
1245         d.inc("a")
1246         d.inc("b", 5)
1247         self.failUnlessEqual(d, {"a": 2, "b": 6})
1248         d.dec("a")
1249         d.dec("c")
1250         d.dec("d", 5)
1251         self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1252         self.failUnlessEqual(d.items_sorted_by_key(),
1253                              [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1254         self.failUnlessEqual(d.items_sorted_by_value(),
1255                              [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1256         self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1257
1258         d = dictutil.NumDict({"a": 1, "b": 2})
1259         self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1260         self.failUnless("a" in d)
1261
1262         d2 = dictutil.NumDict({"c": 3, "d": 4})
1263         self.failUnless(d != d2)
1264         self.failUnless(d2 > d)
1265         self.failUnless(d2 >= d)
1266         self.failUnless(d <= d2)
1267         self.failUnless(d < d2)
1268         self.failUnlessEqual(d["a"], 1)
1269         self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1270         def eq(a, b):
1271             return a == b
1272         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1273
1274         d3 = d.copy()
1275         self.failUnlessEqual(d, d3)
1276         self.failUnless(isinstance(d3, dictutil.NumDict))
1277
1278         d4 = d.fromkeys(["a","b"], 5)
1279         self.failUnlessEqual(d4, {"a": 5, "b": 5})
1280
1281         self.failUnlessEqual(d.get("a"), 1)
1282         self.failUnlessEqual(d.get("c"), 0)
1283         self.failUnlessEqual(d.get("c", 5), 5)
1284         self.failUnlessEqual(sorted(list(d.items())),
1285                              [("a", 1), ("b", 2)])
1286         self.failUnlessEqual(sorted(list(d.iteritems())),
1287                              [("a", 1), ("b", 2)])
1288         self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1289         self.failUnlessEqual(sorted(d.values()), [1, 2])
1290         self.failUnless(d.has_key("a"))
1291         self.failIf(d.has_key("c"))
1292
1293         x = d.setdefault("c", 3)
1294         self.failUnlessEqual(x, 3)
1295         self.failUnlessEqual(d["c"], 3)
1296         x = d.setdefault("c", 5)
1297         self.failUnlessEqual(x, 3)
1298         self.failUnlessEqual(d["c"], 3)
1299         del d["c"]
1300
1301         x = d.popitem()
1302         self.failUnless(x in [("a", 1), ("b", 2)])
1303         x = d.popitem()
1304         self.failUnless(x in [("a", 1), ("b", 2)])
1305         self.failUnlessRaises(KeyError, d.popitem)
1306
1307         d.update({"c": 3})
1308         d.update({"c": 4, "d": 5})
1309         self.failUnlessEqual(d, {"c": 4, "d": 5})
1310
1311     def test_del_if_present(self):
1312         d = {1: "a", 2: "b"}
1313         dictutil.del_if_present(d, 1)
1314         dictutil.del_if_present(d, 3)
1315         self.failUnlessEqual(d, {2: "b"})
1316
1317     def test_valueordereddict(self):
1318         d = dictutil.ValueOrderedDict()
1319         d["a"] = 3
1320         d["b"] = 2
1321         d["c"] = 1
1322
1323         self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1324         self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1325         self.failUnlessEqual(d.values(), [1, 2, 3])
1326         self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1327         self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1328         def eq(a, b):
1329             return a == b
1330         self.failIf(d == {"a": 4})
1331         self.failUnless(d != {"a": 4})
1332
1333         x = d.setdefault("d", 0)
1334         self.failUnlessEqual(x, 0)
1335         self.failUnlessEqual(d["d"], 0)
1336         x = d.setdefault("d", -1)
1337         self.failUnlessEqual(x, 0)
1338         self.failUnlessEqual(d["d"], 0)
1339
1340         x = d.remove("e", "default", False)
1341         self.failUnlessEqual(x, "default")
1342         self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1343         x = d.remove("d", 5)
1344         self.failUnlessEqual(x, 0)
1345
1346         x = d.__getitem__("c")
1347         self.failUnlessEqual(x, 1)
1348         x = d.__getitem__("e", "default", False)
1349         self.failUnlessEqual(x, "default")
1350         self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1351
1352         self.failUnlessEqual(d.popitem(), ("c", 1))
1353         self.failUnlessEqual(d.popitem(), ("b", 2))
1354         self.failUnlessEqual(d.popitem(), ("a", 3))
1355         self.failUnlessRaises(KeyError, d.popitem)
1356
1357         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1358         x = d.pop("d", "default", False)
1359         self.failUnlessEqual(x, "default")
1360         self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1361         x = d.pop("b")
1362         self.failUnlessEqual(x, 2)
1363         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1364
1365         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1366         x = d.pop_from_list(1) # pop the second item, b/2
1367         self.failUnlessEqual(x, "b")
1368         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1369
1370     def test_auxdict(self):
1371         d = dictutil.AuxValueDict()
1372         # we put the serialized form in the auxdata
1373         d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1374
1375         self.failUnlessEqual(d.keys(), ["key"])
1376         self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1377         self.failUnlessEqual(d.get_aux("key"), "serialized")
1378         def _get_missing(key):
1379             return d[key]
1380         self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1381         self.failUnlessEqual(d.get("nonkey"), None)
1382         self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1383         self.failUnlessEqual(d.get_aux("nonkey"), None)
1384         self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1385
1386         d["key"] = ("filecap2", "metadata2")
1387         self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1388         self.failUnlessEqual(d.get_aux("key"), None)
1389
1390         d.set_with_aux("key2", "value2", "aux2")
1391         self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1392         del d["key2"]
1393         self.failUnlessEqual(d.keys(), ["key"])
1394         self.failIf("key2" in d)
1395         self.failUnlessRaises(KeyError, _get_missing, "key2")
1396         self.failUnlessEqual(d.get("key2"), None)
1397         self.failUnlessEqual(d.get_aux("key2"), None)
1398         d["key2"] = "newvalue2"
1399         self.failUnlessEqual(d.get("key2"), "newvalue2")
1400         self.failUnlessEqual(d.get_aux("key2"), None)
1401
1402         d = dictutil.AuxValueDict({1:2,3:4})
1403         self.failUnlessEqual(sorted(d.keys()), [1,3])
1404         self.failUnlessEqual(d[1], 2)
1405         self.failUnlessEqual(d.get_aux(1), None)
1406
1407         d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1408         self.failUnlessEqual(sorted(d.keys()), [1,3])
1409         self.failUnlessEqual(d[1], 2)
1410         self.failUnlessEqual(d.get_aux(1), None)
1411
1412         d = dictutil.AuxValueDict(one=1, two=2)
1413         self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1414         self.failUnlessEqual(d["one"], 1)
1415         self.failUnlessEqual(d.get_aux("one"), None)
1416
1417 class Pipeline(unittest.TestCase):
1418     def pause(self, *args, **kwargs):
1419         d = defer.Deferred()
1420         self.calls.append( (d, args, kwargs) )
1421         return d
1422
1423     def failUnlessCallsAre(self, expected):
1424         #print self.calls
1425         #print expected
1426         self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1427         for i,c in enumerate(self.calls):
1428             self.failUnlessEqual(c[1:], expected[i], str(i))
1429
1430     def test_basic(self):
1431         self.calls = []
1432         finished = []
1433         p = pipeline.Pipeline(100)
1434
1435         d = p.flush() # fires immediately
1436         d.addCallbacks(finished.append, log.err)
1437         self.failUnlessEqual(len(finished), 1)
1438         finished = []
1439
1440         d = p.add(10, self.pause, "one")
1441         # the call should start right away, and our return Deferred should
1442         # fire right away
1443         d.addCallbacks(finished.append, log.err)
1444         self.failUnlessEqual(len(finished), 1)
1445         self.failUnlessEqual(finished[0], None)
1446         self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1447         self.failUnlessEqual(p.gauge, 10)
1448
1449         # pipeline: [one]
1450
1451         finished = []
1452         d = p.add(20, self.pause, "two", kw=2)
1453         # pipeline: [one, two]
1454
1455         # the call and the Deferred should fire right away
1456         d.addCallbacks(finished.append, log.err)
1457         self.failUnlessEqual(len(finished), 1)
1458         self.failUnlessEqual(finished[0], None)
1459         self.failUnlessCallsAre([ ( ("one",) , {} ),
1460                                   ( ("two",) , {"kw": 2} ),
1461                                   ])
1462         self.failUnlessEqual(p.gauge, 30)
1463
1464         self.calls[0][0].callback("one-result")
1465         # pipeline: [two]
1466         self.failUnlessEqual(p.gauge, 20)
1467
1468         finished = []
1469         d = p.add(90, self.pause, "three", "posarg1")
1470         # pipeline: [two, three]
1471         flushed = []
1472         fd = p.flush()
1473         fd.addCallbacks(flushed.append, log.err)
1474         self.failUnlessEqual(flushed, [])
1475
1476         # the call will be made right away, but the return Deferred will not,
1477         # because the pipeline is now full.
1478         d.addCallbacks(finished.append, log.err)
1479         self.failUnlessEqual(len(finished), 0)
1480         self.failUnlessCallsAre([ ( ("one",) , {} ),
1481                                   ( ("two",) , {"kw": 2} ),
1482                                   ( ("three", "posarg1"), {} ),
1483                                   ])
1484         self.failUnlessEqual(p.gauge, 110)
1485
1486         self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1487
1488         # retiring either call will unblock the pipeline, causing the #3
1489         # Deferred to fire
1490         self.calls[2][0].callback("three-result")
1491         # pipeline: [two]
1492
1493         self.failUnlessEqual(len(finished), 1)
1494         self.failUnlessEqual(finished[0], None)
1495         self.failUnlessEqual(flushed, [])
1496
1497         # retiring call#2 will finally allow the flush() Deferred to fire
1498         self.calls[1][0].callback("two-result")
1499         self.failUnlessEqual(len(flushed), 1)
1500
1501     def test_errors(self):
1502         self.calls = []
1503         p = pipeline.Pipeline(100)
1504
1505         d1 = p.add(200, self.pause, "one")
1506         d2 = p.flush()
1507
1508         finished = []
1509         d1.addBoth(finished.append)
1510         self.failUnlessEqual(finished, [])
1511
1512         flushed = []
1513         d2.addBoth(flushed.append)
1514         self.failUnlessEqual(flushed, [])
1515
1516         self.calls[0][0].errback(ValueError("oops"))
1517
1518         self.failUnlessEqual(len(finished), 1)
1519         f = finished[0]
1520         self.failUnless(isinstance(f, Failure))
1521         self.failUnless(f.check(pipeline.PipelineError))
1522         self.failUnlessIn("PipelineError", str(f.value))
1523         self.failUnlessIn("ValueError", str(f.value))
1524         r = repr(f.value)
1525         self.failUnless("ValueError" in r, r)
1526         f2 = f.value.error
1527         self.failUnless(f2.check(ValueError))
1528
1529         self.failUnlessEqual(len(flushed), 1)
1530         f = flushed[0]
1531         self.failUnless(isinstance(f, Failure))
1532         self.failUnless(f.check(pipeline.PipelineError))
1533         f2 = f.value.error
1534         self.failUnless(f2.check(ValueError))
1535
1536         # now that the pipeline is in the failed state, any new calls will
1537         # fail immediately
1538
1539         d3 = p.add(20, self.pause, "two")
1540
1541         finished = []
1542         d3.addBoth(finished.append)
1543         self.failUnlessEqual(len(finished), 1)
1544         f = finished[0]
1545         self.failUnless(isinstance(f, Failure))
1546         self.failUnless(f.check(pipeline.PipelineError))
1547         r = repr(f.value)
1548         self.failUnless("ValueError" in r, r)
1549         f2 = f.value.error
1550         self.failUnless(f2.check(ValueError))
1551
1552         d4 = p.flush()
1553         flushed = []
1554         d4.addBoth(flushed.append)
1555         self.failUnlessEqual(len(flushed), 1)
1556         f = flushed[0]
1557         self.failUnless(isinstance(f, Failure))
1558         self.failUnless(f.check(pipeline.PipelineError))
1559         f2 = f.value.error
1560         self.failUnless(f2.check(ValueError))
1561
1562     def test_errors2(self):
1563         self.calls = []
1564         p = pipeline.Pipeline(100)
1565
1566         d1 = p.add(10, self.pause, "one")
1567         d2 = p.add(20, self.pause, "two")
1568         d3 = p.add(30, self.pause, "three")
1569         d4 = p.flush()
1570
1571         # one call fails, then the second one succeeds: make sure
1572         # ExpandableDeferredList tolerates the second one
1573
1574         flushed = []
1575         d4.addBoth(flushed.append)
1576         self.failUnlessEqual(flushed, [])
1577
1578         self.calls[0][0].errback(ValueError("oops"))
1579         self.failUnlessEqual(len(flushed), 1)
1580         f = flushed[0]
1581         self.failUnless(isinstance(f, Failure))
1582         self.failUnless(f.check(pipeline.PipelineError))
1583         f2 = f.value.error
1584         self.failUnless(f2.check(ValueError))
1585
1586         self.calls[1][0].callback("two-result")
1587         self.calls[2][0].errback(ValueError("three-error"))
1588
1589         del d1,d2,d3,d4
1590
1591 class SampleError(Exception):
1592     pass
1593
1594 class Log(unittest.TestCase):
1595     def test_err(self):
1596         if not hasattr(self, "flushLoggedErrors"):
1597             # without flushLoggedErrors, we can't get rid of the
1598             # twisted.log.err that tahoe_log records, so we can't keep this
1599             # test from [ERROR]ing
1600             raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1601         try:
1602             raise SampleError("simple sample")
1603         except:
1604             f = Failure()
1605         tahoe_log.err(format="intentional sample error",
1606                       failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1607         self.flushLoggedErrors(SampleError)
1608
1609
1610 class SimpleSpans:
1611     # this is a simple+inefficient form of util.spans.Spans . We compare the
1612     # behavior of this reference model against the real (efficient) form.
1613
1614     def __init__(self, _span_or_start=None, length=None):
1615         self._have = set()
1616         if length is not None:
1617             for i in range(_span_or_start, _span_or_start+length):
1618                 self._have.add(i)
1619         elif _span_or_start:
1620             for (start,length) in _span_or_start:
1621                 self.add(start, length)
1622
1623     def add(self, start, length):
1624         for i in range(start, start+length):
1625             self._have.add(i)
1626         return self
1627
1628     def remove(self, start, length):
1629         for i in range(start, start+length):
1630             self._have.discard(i)
1631         return self
1632
1633     def each(self):
1634         return sorted(self._have)
1635
1636     def __iter__(self):
1637         items = sorted(self._have)
1638         prevstart = None
1639         prevend = None
1640         for i in items:
1641             if prevstart is None:
1642                 prevstart = prevend = i
1643                 continue
1644             if i == prevend+1:
1645                 prevend = i
1646                 continue
1647             yield (prevstart, prevend-prevstart+1)
1648             prevstart = prevend = i
1649         if prevstart is not None:
1650             yield (prevstart, prevend-prevstart+1)
1651
1652     def __nonzero__(self): # this gets us bool()
1653         return self.len()
1654
1655     def len(self):
1656         return len(self._have)
1657
1658     def __add__(self, other):
1659         s = self.__class__(self)
1660         for (start, length) in other:
1661             s.add(start, length)
1662         return s
1663
1664     def __sub__(self, other):
1665         s = self.__class__(self)
1666         for (start, length) in other:
1667             s.remove(start, length)
1668         return s
1669
1670     def __iadd__(self, other):
1671         for (start, length) in other:
1672             self.add(start, length)
1673         return self
1674
1675     def __isub__(self, other):
1676         for (start, length) in other:
1677             self.remove(start, length)
1678         return self
1679
1680     def __and__(self, other):
1681         s = self.__class__()
1682         for i in other.each():
1683             if i in self._have:
1684                 s.add(i, 1)
1685         return s
1686
1687     def __contains__(self, (start,length)):
1688         for i in range(start, start+length):
1689             if i not in self._have:
1690                 return False
1691         return True
1692
1693 class ByteSpans(unittest.TestCase):
1694     def test_basic(self):
1695         s = Spans()
1696         self.failUnlessEqual(list(s), [])
1697         self.failIf(s)
1698         self.failIf((0,1) in s)
1699         self.failUnlessEqual(s.len(), 0)
1700
1701         s1 = Spans(3, 4) # 3,4,5,6
1702         self._check1(s1)
1703
1704         s1 = Spans(3L, 4L) # 3,4,5,6
1705         self._check1(s1)
1706
1707         s2 = Spans(s1)
1708         self._check1(s2)
1709
1710         s2.add(10,2) # 10,11
1711         self._check1(s1)
1712         self.failUnless((10,1) in s2)
1713         self.failIf((10,1) in s1)
1714         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1715         self.failUnlessEqual(s2.len(), 6)
1716
1717         s2.add(15,2).add(20,2)
1718         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1719         self.failUnlessEqual(s2.len(), 10)
1720
1721         s2.remove(4,3).remove(15,1)
1722         self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1723         self.failUnlessEqual(s2.len(), 6)
1724
1725         s1 = SimpleSpans(3, 4) # 3 4 5 6
1726         s2 = SimpleSpans(5, 4) # 5 6 7 8
1727         i = s1 & s2
1728         self.failUnlessEqual(list(i.each()), [5, 6])
1729
1730     def _check1(self, s):
1731         self.failUnlessEqual(list(s), [(3,4)])
1732         self.failUnless(s)
1733         self.failUnlessEqual(s.len(), 4)
1734         self.failIf((0,1) in s)
1735         self.failUnless((3,4) in s)
1736         self.failUnless((3,1) in s)
1737         self.failUnless((5,2) in s)
1738         self.failUnless((6,1) in s)
1739         self.failIf((6,2) in s)
1740         self.failIf((7,1) in s)
1741         self.failUnlessEqual(list(s.each()), [3,4,5,6])
1742
1743     def test_large(self):
1744         s = Spans(4, 2**65) # don't do this with a SimpleSpans
1745         self.failUnlessEqual(list(s), [(4, 2**65)])
1746         self.failUnless(s)
1747         self.failUnlessEqual(s.len(), 2**65)
1748         self.failIf((0,1) in s)
1749         self.failUnless((4,2) in s)
1750         self.failUnless((2**65,2) in s)
1751
1752     def test_math(self):
1753         s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1754         s2 = Spans(5, 3) # 5,6,7
1755         s3 = Spans(8, 4) # 8,9,10,11
1756
1757         s = s1 - s2
1758         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1759         s = s1 - s3
1760         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1761         s = s2 - s3
1762         self.failUnlessEqual(list(s.each()), [5,6,7])
1763         s = s1 & s2
1764         self.failUnlessEqual(list(s.each()), [5,6,7])
1765         s = s2 & s1
1766         self.failUnlessEqual(list(s.each()), [5,6,7])
1767         s = s1 & s3
1768         self.failUnlessEqual(list(s.each()), [8,9])
1769         s = s3 & s1
1770         self.failUnlessEqual(list(s.each()), [8,9])
1771         s = s2 & s3
1772         self.failUnlessEqual(list(s.each()), [])
1773         s = s3 & s2
1774         self.failUnlessEqual(list(s.each()), [])
1775         s = Spans() & s3
1776         self.failUnlessEqual(list(s.each()), [])
1777         s = s3 & Spans()
1778         self.failUnlessEqual(list(s.each()), [])
1779
1780         s = s1 + s2
1781         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1782         s = s1 + s3
1783         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1784         s = s2 + s3
1785         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1786
1787         s = Spans(s1)
1788         s -= s2
1789         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1790         s = Spans(s1)
1791         s -= s3
1792         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1793         s = Spans(s2)
1794         s -= s3
1795         self.failUnlessEqual(list(s.each()), [5,6,7])
1796
1797         s = Spans(s1)
1798         s += s2
1799         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1800         s = Spans(s1)
1801         s += s3
1802         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1803         s = Spans(s2)
1804         s += s3
1805         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1806
1807     def test_random(self):
1808         # attempt to increase coverage of corner cases by comparing behavior
1809         # of a simple-but-slow model implementation against the
1810         # complex-but-fast actual implementation, in a large number of random
1811         # operations
1812         S1 = SimpleSpans
1813         S2 = Spans
1814         s1 = S1(); s2 = S2()
1815         seed = ""
1816         def _create(subseed):
1817             ns1 = S1(); ns2 = S2()
1818             for i in range(10):
1819                 what = _hash(subseed+str(i)).hexdigest()
1820                 start = int(what[2:4], 16)
1821                 length = max(1,int(what[5:6], 16))
1822                 ns1.add(start, length); ns2.add(start, length)
1823             return ns1, ns2
1824
1825         #print
1826         for i in range(1000):
1827             what = _hash(seed+str(i)).hexdigest()
1828             op = what[0]
1829             subop = what[1]
1830             start = int(what[2:4], 16)
1831             length = max(1,int(what[5:6], 16))
1832             #print what
1833             if op in "0":
1834                 if subop in "01234":
1835                     s1 = S1(); s2 = S2()
1836                 elif subop in "5678":
1837                     s1 = S1(start, length); s2 = S2(start, length)
1838                 else:
1839                     s1 = S1(s1); s2 = S2(s2)
1840                 #print "s2 = %s" % s2.dump()
1841             elif op in "123":
1842                 #print "s2.add(%d,%d)" % (start, length)
1843                 s1.add(start, length); s2.add(start, length)
1844             elif op in "456":
1845                 #print "s2.remove(%d,%d)" % (start, length)
1846                 s1.remove(start, length); s2.remove(start, length)
1847             elif op in "78":
1848                 ns1, ns2 = _create(what[7:11])
1849                 #print "s2 + %s" % ns2.dump()
1850                 s1 = s1 + ns1; s2 = s2 + ns2
1851             elif op in "9a":
1852                 ns1, ns2 = _create(what[7:11])
1853                 #print "%s - %s" % (s2.dump(), ns2.dump())
1854                 s1 = s1 - ns1; s2 = s2 - ns2
1855             elif op in "bc":
1856                 ns1, ns2 = _create(what[7:11])
1857                 #print "s2 += %s" % ns2.dump()
1858                 s1 += ns1; s2 += ns2
1859             elif op in "de":
1860                 ns1, ns2 = _create(what[7:11])
1861                 #print "%s -= %s" % (s2.dump(), ns2.dump())
1862                 s1 -= ns1; s2 -= ns2
1863             else:
1864                 ns1, ns2 = _create(what[7:11])
1865                 #print "%s &= %s" % (s2.dump(), ns2.dump())
1866                 s1 = s1 & ns1; s2 = s2 & ns2
1867             #print "s2 now %s" % s2.dump()
1868             self.failUnlessEqual(list(s1.each()), list(s2.each()))
1869             self.failUnlessEqual(s1.len(), s2.len())
1870             self.failUnlessEqual(bool(s1), bool(s2))
1871             self.failUnlessEqual(list(s1), list(s2))
1872             for j in range(10):
1873                 what = _hash(what[12:14]+str(j)).hexdigest()
1874                 start = int(what[2:4], 16)
1875                 length = max(1, int(what[5:6], 16))
1876                 span = (start, length)
1877                 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1878
1879
1880     # s()
1881     # s(start,length)
1882     # s(s0)
1883     # s.add(start,length) : returns s
1884     # s.remove(start,length)
1885     # s.each() -> list of byte offsets, mostly for testing
1886     # list(s) -> list of (start,length) tuples, one per span
1887     # (start,length) in s -> True if (start..start+length-1) are all members
1888     #  NOT equivalent to x in list(s)
1889     # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
1890     # bool(s)  (__nonzeron__)
1891     # s = s1+s2, s1-s2, +=s1, -=s1
1892
1893     def test_overlap(self):
1894         for a in range(20):
1895             for b in range(10):
1896                 for c in range(20):
1897                     for d in range(10):
1898                         self._test_overlap(a,b,c,d)
1899
1900     def _test_overlap(self, a, b, c, d):
1901         s1 = set(range(a,a+b))
1902         s2 = set(range(c,c+d))
1903         #print "---"
1904         #self._show_overlap(s1, "1")
1905         #self._show_overlap(s2, "2")
1906         o = overlap(a,b,c,d)
1907         expected = s1.intersection(s2)
1908         if not expected:
1909             self.failUnlessEqual(o, None)
1910         else:
1911             start,length = o
1912             so = set(range(start,start+length))
1913             #self._show(so, "o")
1914             self.failUnlessEqual(so, expected)
1915
1916     def _show_overlap(self, s, c):
1917         import sys
1918         out = sys.stdout
1919         if s:
1920             for i in range(max(s)):
1921                 if i in s:
1922                     out.write(c)
1923                 else:
1924                     out.write(" ")
1925         out.write("\n")
1926
1927 def extend(s, start, length, fill):
1928     if len(s) >= start+length:
1929         return s
1930     assert len(fill) == 1
1931     return s + fill*(start+length-len(s))
1932
1933 def replace(s, start, data):
1934     assert len(s) >= start+len(data)
1935     return s[:start] + data + s[start+len(data):]
1936
1937 class SimpleDataSpans:
1938     def __init__(self, other=None):
1939         self.missing = "" # "1" where missing, "0" where found
1940         self.data = ""
1941         if other:
1942             for (start, data) in other.get_chunks():
1943                 self.add(start, data)
1944
1945     def __nonzero__(self): # this gets us bool()
1946         return self.len()
1947     def len(self):
1948         return len(self.missing.replace("1", ""))
1949     def _dump(self):
1950         return [i for (i,c) in enumerate(self.missing) if c == "0"]
1951     def _have(self, start, length):
1952         m = self.missing[start:start+length]
1953         if not m or len(m)<length or int(m):
1954             return False
1955         return True
1956     def get_chunks(self):
1957         for i in self._dump():
1958             yield (i, self.data[i])
1959     def get_spans(self):
1960         return SimpleSpans([(start,len(data))
1961                             for (start,data) in self.get_chunks()])
1962     def get(self, start, length):
1963         if self._have(start, length):
1964             return self.data[start:start+length]
1965         return None
1966     def pop(self, start, length):
1967         data = self.get(start, length)
1968         if data:
1969             self.remove(start, length)
1970         return data
1971     def remove(self, start, length):
1972         self.missing = replace(extend(self.missing, start, length, "1"),
1973                                start, "1"*length)
1974     def add(self, start, data):
1975         self.missing = replace(extend(self.missing, start, len(data), "1"),
1976                                start, "0"*len(data))
1977         self.data = replace(extend(self.data, start, len(data), " "),
1978                             start, data)
1979
1980
1981 class StringSpans(unittest.TestCase):
1982     def do_basic(self, klass):
1983         ds = klass()
1984         self.failUnlessEqual(ds.len(), 0)
1985         self.failUnlessEqual(list(ds._dump()), [])
1986         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
1987         s = ds.get_spans()
1988         self.failUnlessEqual(ds.get(0, 4), None)
1989         self.failUnlessEqual(ds.pop(0, 4), None)
1990         ds.remove(0, 4)
1991
1992         ds.add(2, "four")
1993         self.failUnlessEqual(ds.len(), 4)
1994         self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
1995         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
1996         s = ds.get_spans()
1997         self.failUnless((2,2) in s)
1998         self.failUnlessEqual(ds.get(0, 4), None)
1999         self.failUnlessEqual(ds.pop(0, 4), None)
2000         self.failUnlessEqual(ds.get(4, 4), None)
2001
2002         ds2 = klass(ds)
2003         self.failUnlessEqual(ds2.len(), 4)
2004         self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2005         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2006         self.failUnlessEqual(ds2.get(0, 4), None)
2007         self.failUnlessEqual(ds2.pop(0, 4), None)
2008         self.failUnlessEqual(ds2.pop(2, 3), "fou")
2009         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2010         self.failUnlessEqual(ds2.get(2, 3), None)
2011         self.failUnlessEqual(ds2.get(5, 1), "r")
2012         self.failUnlessEqual(ds.get(2, 3), "fou")
2013         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2014
2015         ds.add(0, "23")
2016         self.failUnlessEqual(ds.len(), 6)
2017         self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2018         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2019         self.failUnlessEqual(ds.get(0, 4), "23fo")
2020         self.failUnlessEqual(ds.pop(0, 4), "23fo")
2021         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2022         self.failUnlessEqual(ds.get(0, 4), None)
2023         self.failUnlessEqual(ds.pop(0, 4), None)
2024
2025         ds = klass()
2026         ds.add(2, "four")
2027         ds.add(3, "ea")
2028         self.failUnlessEqual(ds.get(2, 4), "fear")
2029
2030         ds = klass()
2031         ds.add(2L, "four")
2032         ds.add(3L, "ea")
2033         self.failUnlessEqual(ds.get(2L, 4L), "fear")
2034
2035
2036     def do_scan(self, klass):
2037         # do a test with gaps and spans of size 1 and 2
2038         #  left=(1,11) * right=(1,11) * gapsize=(1,2)
2039         # 111, 112, 121, 122, 211, 212, 221, 222
2040         #    211
2041         #      121
2042         #         112
2043         #            212
2044         #               222
2045         #                   221
2046         #                      111
2047         #                        122
2048         #  11 1  1 11 11  11  1 1  111
2049         # 0123456789012345678901234567
2050         # abcdefghijklmnopqrstuvwxyz-=
2051         pieces = [(1, "bc"),
2052                   (4, "e"),
2053                   (7, "h"),
2054                   (9, "jk"),
2055                   (12, "mn"),
2056                   (16, "qr"),
2057                   (20, "u"),
2058                   (22, "w"),
2059                   (25, "z-="),
2060                   ]
2061         p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2062         S = "abcdefghijklmnopqrstuvwxyz-="
2063         # TODO: when adding data, add capital letters, to make sure we aren't
2064         # just leaving the old data in place
2065         l = len(S)
2066         def base():
2067             ds = klass()
2068             for start, data in pieces:
2069                 ds.add(start, data)
2070             return ds
2071         def dump(s):
2072             p = set(s._dump())
2073             d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2074             assert len(d) == l
2075             return d
2076         DEBUG = False
2077         for start in range(0, l):
2078             for end in range(start+1, l):
2079                 # add [start-end) to the baseline
2080                 which = "%d-%d" % (start, end-1)
2081                 p_added = set(range(start, end))
2082                 b = base()
2083                 if DEBUG:
2084                     print
2085                     print dump(b), which
2086                     add = klass(); add.add(start, S[start:end])
2087                     print dump(add)
2088                 b.add(start, S[start:end])
2089                 if DEBUG:
2090                     print dump(b)
2091                 # check that the new span is there
2092                 d = b.get(start, end-start)
2093                 self.failUnlessEqual(d, S[start:end], which)
2094                 # check that all the original pieces are still there
2095                 for t_start, t_data in pieces:
2096                     t_len = len(t_data)
2097                     self.failUnlessEqual(b.get(t_start, t_len),
2098                                          S[t_start:t_start+t_len],
2099                                          "%s %d+%d" % (which, t_start, t_len))
2100                 # check that a lot of subspans are mostly correct
2101                 for t_start in range(l):
2102                     for t_len in range(1,4):
2103                         d = b.get(t_start, t_len)
2104                         if d is not None:
2105                             which2 = "%s+(%d-%d)" % (which, t_start,
2106                                                      t_start+t_len-1)
2107                             self.failUnlessEqual(d, S[t_start:t_start+t_len],
2108                                                  which2)
2109                         # check that removing a subspan gives the right value
2110                         b2 = klass(b)
2111                         b2.remove(t_start, t_len)
2112                         removed = set(range(t_start, t_start+t_len))
2113                         for i in range(l):
2114                             exp = (((i in p_elements) or (i in p_added))
2115                                    and (i not in removed))
2116                             which2 = "%s-(%d-%d)" % (which, t_start,
2117                                                      t_start+t_len-1)
2118                             self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2119                                                  which2+" %d" % i)
2120
2121     def test_test(self):
2122         self.do_basic(SimpleDataSpans)
2123         self.do_scan(SimpleDataSpans)
2124
2125     def test_basic(self):
2126         self.do_basic(DataSpans)
2127         self.do_scan(DataSpans)
2128
2129     def test_random(self):
2130         # attempt to increase coverage of corner cases by comparing behavior
2131         # of a simple-but-slow model implementation against the
2132         # complex-but-fast actual implementation, in a large number of random
2133         # operations
2134         S1 = SimpleDataSpans
2135         S2 = DataSpans
2136         s1 = S1(); s2 = S2()
2137         seed = ""
2138         def _randstr(length, seed):
2139             created = 0
2140             pieces = []
2141             while created < length:
2142                 piece = _hash(seed + str(created)).hexdigest()
2143                 pieces.append(piece)
2144                 created += len(piece)
2145             return "".join(pieces)[:length]
2146         def _create(subseed):
2147             ns1 = S1(); ns2 = S2()
2148             for i in range(10):
2149                 what = _hash(subseed+str(i)).hexdigest()
2150                 start = int(what[2:4], 16)
2151                 length = max(1,int(what[5:6], 16))
2152                 ns1.add(start, _randstr(length, what[7:9]));
2153                 ns2.add(start, _randstr(length, what[7:9]))
2154             return ns1, ns2
2155
2156         #print
2157         for i in range(1000):
2158             what = _hash(seed+str(i)).hexdigest()
2159             op = what[0]
2160             subop = what[1]
2161             start = int(what[2:4], 16)
2162             length = max(1,int(what[5:6], 16))
2163             #print what
2164             if op in "0":
2165                 if subop in "0123456":
2166                     s1 = S1(); s2 = S2()
2167                 else:
2168                     s1, s2 = _create(what[7:11])
2169                 #print "s2 = %s" % list(s2._dump())
2170             elif op in "123456":
2171                 #print "s2.add(%d,%d)" % (start, length)
2172                 s1.add(start, _randstr(length, what[7:9]));
2173                 s2.add(start, _randstr(length, what[7:9]))
2174             elif op in "789abc":
2175                 #print "s2.remove(%d,%d)" % (start, length)
2176                 s1.remove(start, length); s2.remove(start, length)
2177             else:
2178                 #print "s2.pop(%d,%d)" % (start, length)
2179                 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2180                 self.failUnlessEqual(d1, d2)
2181             #print "s1 now %s" % list(s1._dump())
2182             #print "s2 now %s" % list(s2._dump())
2183             self.failUnlessEqual(s1.len(), s2.len())
2184             self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2185             for j in range(100):
2186                 what = _hash(what[12:14]+str(j)).hexdigest()
2187                 start = int(what[2:4], 16)
2188                 length = max(1, int(what[5:6], 16))
2189                 d1 = s1.get(start, length); d2 = s2.get(start, length)
2190                 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))