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         # we tolerate used==0 for a Travis-CI bug, see #2290
 523         self.failUnless(disk['used'] >= 0, disk['used'])
 524         self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
 525         self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
 526         self.failUnless(disk['avail'] > 0, disk['avail'])
 527
 528     def test_disk_stats_avail_nonnegative(self):
 529         # This test will spuriously fail if you have more than 2^128
 530         # bytes of available space on your filesystem.
 531         disk = fileutil.get_disk_stats('.', 2**128)
 532         self.failUnlessEqual(disk['avail'], 0)
 533
 534 class PollMixinTests(unittest.TestCase):
 535     def setUp(self):
 536         self.pm = pollmixin.PollMixin()
 537
 538     def test_PollMixin_True(self):
 539         d = self.pm.poll(check_f=lambda : True,
 540                          pollinterval=0.1)
 541         return d
 542
 543     def test_PollMixin_False_then_True(self):
 544         i = iter([False, True])
 545         d = self.pm.poll(check_f=i.next,
 546                          pollinterval=0.1)
 547         return d
 548
 549     def test_timeout(self):
 550         d = self.pm.poll(check_f=lambda: False,
 551                          pollinterval=0.01,
 552                          timeout=1)
 553         def _suc(res):
 554             self.fail("poll should have failed, not returned %s" % (res,))
 555         def _err(f):
 556             f.trap(pollmixin.TimeoutError)
 557             return None # success
 558         d.addCallbacks(_suc, _err)
 559         return d
 560
 561 class DeferredUtilTests(unittest.TestCase):
 562     def test_gather_results(self):
 563         d1 = defer.Deferred()
 564         d2 = defer.Deferred()
 565         res = deferredutil.gatherResults([d1, d2])
 566         d1.errback(ValueError("BAD"))
 567         def _callb(res):
 568             self.fail("Should have errbacked, not resulted in %s" % (res,))
 569         def _errb(thef):
 570             thef.trap(ValueError)
 571         res.addCallbacks(_callb, _errb)
 572         return res
 573
 574     def test_success(self):
 575         d1, d2 = defer.Deferred(), defer.Deferred()
 576         good = []
 577         bad = []
 578         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 579         dlss.addCallbacks(good.append, bad.append)
 580         d1.callback(1)
 581         d2.callback(2)
 582         self.failUnlessEqual(good, [[1,2]])
 583         self.failUnlessEqual(bad, [])
 584
 585     def test_failure(self):
 586         d1, d2 = defer.Deferred(), defer.Deferred()
 587         good = []
 588         bad = []
 589         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 590         dlss.addCallbacks(good.append, bad.append)
 591         d1.addErrback(lambda _ignore: None)
 592         d2.addErrback(lambda _ignore: None)
 593         d1.callback(1)
 594         d2.errback(ValueError())
 595         self.failUnlessEqual(good, [])
 596         self.failUnlessEqual(len(bad), 1)
 597         f = bad[0]
 598         self.failUnless(isinstance(f, Failure))
 599         self.failUnless(f.check(ValueError))
 600
 601 class HashUtilTests(unittest.TestCase):
 602
 603     def test_random_key(self):
 604         k = hashutil.random_key()
 605         self.failUnlessEqual(len(k), hashutil.KEYLEN)
 606
 607     def test_sha256d(self):
 608         h1 = hashutil.tagged_hash("tag1", "value")
 609         h2 = hashutil.tagged_hasher("tag1")
 610         h2.update("value")
 611         h2a = h2.digest()
 612         h2b = h2.digest()
 613         self.failUnlessEqual(h1, h2a)
 614         self.failUnlessEqual(h2a, h2b)
 615
 616     def test_sha256d_truncated(self):
 617         h1 = hashutil.tagged_hash("tag1", "value", 16)
 618         h2 = hashutil.tagged_hasher("tag1", 16)
 619         h2.update("value")
 620         h2 = h2.digest()
 621         self.failUnlessEqual(len(h1), 16)
 622         self.failUnlessEqual(len(h2), 16)
 623         self.failUnlessEqual(h1, h2)
 624
 625     def test_chk(self):
 626         h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
 627         h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
 628         h2.update("data")
 629         h2 = h2.digest()
 630         self.failUnlessEqual(h1, h2)
 631
 632     def test_hashers(self):
 633         h1 = hashutil.block_hash("foo")
 634         h2 = hashutil.block_hasher()
 635         h2.update("foo")
 636         self.failUnlessEqual(h1, h2.digest())
 637
 638         h1 = hashutil.uri_extension_hash("foo")
 639         h2 = hashutil.uri_extension_hasher()
 640         h2.update("foo")
 641         self.failUnlessEqual(h1, h2.digest())
 642
 643         h1 = hashutil.plaintext_hash("foo")
 644         h2 = hashutil.plaintext_hasher()
 645         h2.update("foo")
 646         self.failUnlessEqual(h1, h2.digest())
 647
 648         h1 = hashutil.crypttext_hash("foo")
 649         h2 = hashutil.crypttext_hasher()
 650         h2.update("foo")
 651         self.failUnlessEqual(h1, h2.digest())
 652
 653         h1 = hashutil.crypttext_segment_hash("foo")
 654         h2 = hashutil.crypttext_segment_hasher()
 655         h2.update("foo")
 656         self.failUnlessEqual(h1, h2.digest())
 657
 658         h1 = hashutil.plaintext_segment_hash("foo")
 659         h2 = hashutil.plaintext_segment_hasher()
 660         h2.update("foo")
 661         self.failUnlessEqual(h1, h2.digest())
 662
 663     def test_timing_safe_compare(self):
 664         self.failUnless(hashutil.timing_safe_compare("a", "a"))
 665         self.failUnless(hashutil.timing_safe_compare("ab", "ab"))
 666         self.failIf(hashutil.timing_safe_compare("a", "b"))
 667         self.failIf(hashutil.timing_safe_compare("a", "aa"))
 668
 669     def _testknown(self, hashf, expected_a, *args):
 670         got = hashf(*args)
 671         got_a = base32.b2a(got)
 672         self.failUnlessEqual(got_a, expected_a)
 673
 674     def test_known_answers(self):
 675         # assert backwards compatibility
 676         self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
 677         self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
 678         self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
 679         self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
 680         self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
 681         self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
 682         self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
 683         self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
 684         self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
 685         self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
 686         self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
 687         self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
 688         self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
 689         self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
 690         self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
 691         self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
 692         self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
 693         self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
 694         self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
 695         self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
 696         self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
 697         self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
 698         self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
 699
 700
 701 class Abbreviate(unittest.TestCase):
 702     def test_time(self):
 703         a = abbreviate.abbreviate_time
 704         self.failUnlessEqual(a(None), "unknown")
 705         self.failUnlessEqual(a(0), "0 seconds")
 706         self.failUnlessEqual(a(1), "1 second")
 707         self.failUnlessEqual(a(2), "2 seconds")
 708         self.failUnlessEqual(a(119), "119 seconds")
 709         MIN = 60
 710         self.failUnlessEqual(a(2*MIN), "2 minutes")
 711         self.failUnlessEqual(a(60*MIN), "60 minutes")
 712         self.failUnlessEqual(a(179*MIN), "179 minutes")
 713         HOUR = 60*MIN
 714         self.failUnlessEqual(a(180*MIN), "3 hours")
 715         self.failUnlessEqual(a(4*HOUR), "4 hours")
 716         DAY = 24*HOUR
 717         MONTH = 30*DAY
 718         self.failUnlessEqual(a(2*DAY), "2 days")
 719         self.failUnlessEqual(a(2*MONTH), "2 months")
 720         YEAR = 365*DAY
 721         self.failUnlessEqual(a(5*YEAR), "5 years")
 722
 723     def test_space(self):
 724         tests_si = [(None, "unknown"),
 725                     (0, "0 B"),
 726                     (1, "1 B"),
 727                     (999, "999 B"),
 728                     (1000, "1000 B"),
 729                     (1023, "1023 B"),
 730                     (1024, "1.02 kB"),
 731                     (20*1000, "20.00 kB"),
 732                     (1024*1024, "1.05 MB"),
 733                     (1000*1000, "1.00 MB"),
 734                     (1000*1000*1000, "1.00 GB"),
 735                     (1000*1000*1000*1000, "1.00 TB"),
 736                     (1000*1000*1000*1000*1000, "1.00 PB"),
 737                     (1000*1000*1000*1000*1000*1000, "1.00 EB"),
 738                     (1234567890123456789, "1.23 EB"),
 739                     ]
 740         for (x, expected) in tests_si:
 741             got = abbreviate.abbreviate_space(x, SI=True)
 742             self.failUnlessEqual(got, expected)
 743
 744         tests_base1024 = [(None, "unknown"),
 745                           (0, "0 B"),
 746                           (1, "1 B"),
 747                           (999, "999 B"),
 748                           (1000, "1000 B"),
 749                           (1023, "1023 B"),
 750                           (1024, "1.00 kiB"),
 751                           (20*1024, "20.00 kiB"),
 752                           (1000*1000, "976.56 kiB"),
 753                           (1024*1024, "1.00 MiB"),
 754                           (1024*1024*1024, "1.00 GiB"),
 755                           (1024*1024*1024*1024, "1.00 TiB"),
 756                           (1000*1000*1000*1000*1000, "909.49 TiB"),
 757                           (1024*1024*1024*1024*1024, "1.00 PiB"),
 758                           (1024*1024*1024*1024*1024*1024, "1.00 EiB"),
 759                           (1234567890123456789, "1.07 EiB"),
 760                     ]
 761         for (x, expected) in tests_base1024:
 762             got = abbreviate.abbreviate_space(x, SI=False)
 763             self.failUnlessEqual(got, expected)
 764
 765         self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
 766                              "(1.23 MB, 1.18 MiB)")
 767
 768     def test_parse_space(self):
 769         p = abbreviate.parse_abbreviated_size
 770         self.failUnlessEqual(p(""), None)
 771         self.failUnlessEqual(p(None), None)
 772         self.failUnlessEqual(p("123"), 123)
 773         self.failUnlessEqual(p("123B"), 123)
 774         self.failUnlessEqual(p("2K"), 2000)
 775         self.failUnlessEqual(p("2kb"), 2000)
 776         self.failUnlessEqual(p("2KiB"), 2048)
 777         self.failUnlessEqual(p("10MB"), 10*1000*1000)
 778         self.failUnlessEqual(p("10MiB"), 10*1024*1024)
 779         self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
 780         self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
 781         self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
 782         self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
 783         self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
 784         self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
 785         self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
 786         self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
 787
 788         e = self.failUnlessRaises(ValueError, p, "12 cubits")
 789         self.failUnlessIn("12 cubits", str(e))
 790         e = self.failUnlessRaises(ValueError, p, "1 BB")
 791         self.failUnlessIn("1 BB", str(e))
 792         e = self.failUnlessRaises(ValueError, p, "fhtagn")
 793         self.failUnlessIn("fhtagn", str(e))
 794
 795 class Limiter(unittest.TestCase):
 796     timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
 797
 798     def job(self, i, foo):
 799         self.calls.append( (i, foo) )
 800         self.simultaneous += 1
 801         self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
 802         d = defer.Deferred()
 803         def _done():
 804             self.simultaneous -= 1
 805             d.callback("done %d" % i)
 806         reactor.callLater(1.0, _done)
 807         return d
 808
 809     def bad_job(self, i, foo):
 810         raise ValueError("bad_job %d" % i)
 811
 812     def test_limiter(self):
 813         self.calls = []
 814         self.simultaneous = 0
 815         self.peak_simultaneous = 0
 816         l = limiter.ConcurrencyLimiter()
 817         dl = []
 818         for i in range(20):
 819             dl.append(l.add(self.job, i, foo=str(i)))
 820         d = defer.DeferredList(dl, fireOnOneErrback=True)
 821         def _done(res):
 822             self.failUnlessEqual(self.simultaneous, 0)
 823             self.failUnless(self.peak_simultaneous <= 10)
 824             self.failUnlessEqual(len(self.calls), 20)
 825             for i in range(20):
 826                 self.failUnless( (i, str(i)) in self.calls)
 827         d.addCallback(_done)
 828         return d
 829
 830     def test_errors(self):
 831         self.calls = []
 832         self.simultaneous = 0
 833         self.peak_simultaneous = 0
 834         l = limiter.ConcurrencyLimiter()
 835         dl = []
 836         for i in range(20):
 837             dl.append(l.add(self.job, i, foo=str(i)))
 838         d2 = l.add(self.bad_job, 21, "21")
 839         d = defer.DeferredList(dl, fireOnOneErrback=True)
 840         def _most_done(res):
 841             results = []
 842             for (success, result) in res:
 843                 self.failUnlessEqual(success, True)
 844                 results.append(result)
 845             results.sort()
 846             expected_results = ["done %d" % i for i in range(20)]
 847             expected_results.sort()
 848             self.failUnlessEqual(results, expected_results)
 849             self.failUnless(self.peak_simultaneous <= 10)
 850             self.failUnlessEqual(len(self.calls), 20)
 851             for i in range(20):
 852                 self.failUnless( (i, str(i)) in self.calls)
 853             def _good(res):
 854                 self.fail("should have failed, not got %s" % (res,))
 855             def _err(f):
 856                 f.trap(ValueError)
 857                 self.failUnless("bad_job 21" in str(f))
 858             d2.addCallbacks(_good, _err)
 859             return d2
 860         d.addCallback(_most_done)
 861         def _all_done(res):
 862             self.failUnlessEqual(self.simultaneous, 0)
 863             self.failUnless(self.peak_simultaneous <= 10)
 864             self.failUnlessEqual(len(self.calls), 20)
 865             for i in range(20):
 866                 self.failUnless( (i, str(i)) in self.calls)
 867         d.addCallback(_all_done)
 868         return d
 869
 870 class TimeFormat(unittest.TestCase):
 871     def test_epoch(self):
 872         return self._help_test_epoch()
 873
 874     def test_epoch_in_London(self):
 875         # Europe/London is a particularly troublesome timezone.  Nowadays, its
 876         # offset from GMT is 0.  But in 1970, its offset from GMT was 1.
 877         # (Apparently in 1970 Britain had redefined standard time to be GMT+1
 878         # and stayed in standard time all year round, whereas today
 879         # Europe/London standard time is GMT and Europe/London Daylight
 880         # Savings Time is GMT+1.)  The current implementation of
 881         # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
 882         # Europe/London.  (As soon as this unit test is done then I'll change
 883         # that implementation to something that works even in this case...)
 884         origtz = os.environ.get('TZ')
 885         os.environ['TZ'] = "Europe/London"
 886         if hasattr(time, 'tzset'):
 887             time.tzset()
 888         try:
 889             return self._help_test_epoch()
 890         finally:
 891             if origtz is None:
 892                 del os.environ['TZ']
 893             else:
 894                 os.environ['TZ'] = origtz
 895             if hasattr(time, 'tzset'):
 896                 time.tzset()
 897
 898     def _help_test_epoch(self):
 899         origtzname = time.tzname
 900         s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
 901         self.failUnlessEqual(s, 1.0)
 902         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
 903         self.failUnlessEqual(s, 1.0)
 904         s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
 905         self.failUnlessEqual(s, 1.0)
 906
 907         self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
 908         self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
 909                              "1970-01-01 00:00:01")
 910
 911         now = time.time()
 912         isostr = time_format.iso_utc(now)
 913         timestamp = time_format.iso_utc_time_to_seconds(isostr)
 914         self.failUnlessEqual(int(timestamp), int(now))
 915
 916         def my_time():
 917             return 1.0
 918         self.failUnlessEqual(time_format.iso_utc(t=my_time),
 919                              "1970-01-01_00:00:01")
 920         e = self.failUnlessRaises(ValueError,
 921                                   time_format.iso_utc_time_to_seconds,
 922                                   "invalid timestring")
 923         self.failUnless("not a complete ISO8601 timestamp" in str(e))
 924         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
 925         self.failUnlessEqual(s, 1.5)
 926
 927         # Look for daylight-savings-related errors.
 928         thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
 929         self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
 930         self.failUnlessEqual(origtzname, time.tzname)
 931
 932     def test_iso_utc(self):
 933         when = 1266760143.7841301
 934         out = time_format.iso_utc_date(when)
 935         self.failUnlessEqual(out, "2010-02-21")
 936         out = time_format.iso_utc_date(t=lambda: when)
 937         self.failUnlessEqual(out, "2010-02-21")
 938         out = time_format.iso_utc(when)
 939         self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
 940         out = time_format.iso_utc(when, sep="-")
 941         self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
 942
 943     def test_parse_duration(self):
 944         p = time_format.parse_duration
 945         DAY = 24*60*60
 946         self.failUnlessEqual(p("1 day"), DAY)
 947         self.failUnlessEqual(p("2 days"), 2*DAY)
 948         self.failUnlessEqual(p("3 months"), 3*31*DAY)
 949         self.failUnlessEqual(p("4 mo"), 4*31*DAY)
 950         self.failUnlessEqual(p("5 years"), 5*365*DAY)
 951         e = self.failUnlessRaises(ValueError, p, "123")
 952         self.failUnlessIn("no unit (like day, month, or year) in '123'",
 953                           str(e))
 954
 955     def test_parse_date(self):
 956         self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
 957
 958 class CacheDir(unittest.TestCase):
 959     def test_basic(self):
 960         basedir = "test_util/CacheDir/test_basic"
 961
 962         def _failIfExists(name):
 963             absfn = os.path.join(basedir, name)
 964             self.failIf(os.path.exists(absfn),
 965                         "%s exists but it shouldn't" % absfn)
 966
 967         def _failUnlessExists(name):
 968             absfn = os.path.join(basedir, name)
 969             self.failUnless(os.path.exists(absfn),
 970                             "%s doesn't exist but it should" % absfn)
 971
 972         cdm = cachedir.CacheDirectoryManager(basedir)
 973         a = cdm.get_file("a")
 974         b = cdm.get_file("b")
 975         c = cdm.get_file("c")
 976         f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
 977         f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
 978         f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
 979
 980         _failUnlessExists("a")
 981         _failUnlessExists("b")
 982         _failUnlessExists("c")
 983
 984         cdm.check()
 985
 986         _failUnlessExists("a")
 987         _failUnlessExists("b")
 988         _failUnlessExists("c")
 989
 990         del a
 991         # this file won't be deleted yet, because it isn't old enough
 992         cdm.check()
 993         _failUnlessExists("a")
 994         _failUnlessExists("b")
 995         _failUnlessExists("c")
 996
 997         # we change the definition of "old" to make everything old
 998         cdm.old = -10
 999
1000         cdm.check()
1001         _failIfExists("a")
1002         _failUnlessExists("b")
1003         _failUnlessExists("c")
1004
1005         cdm.old = 60*60
1006
1007         del b
1008
1009         cdm.check()
1010         _failIfExists("a")
1011         _failUnlessExists("b")
1012         _failUnlessExists("c")
1013
1014         b2 = cdm.get_file("b")
1015
1016         cdm.check()
1017         _failIfExists("a")
1018         _failUnlessExists("b")
1019         _failUnlessExists("c")
1020         del b2
1021
1022 ctr = [0]
1023 class EqButNotIs:
1024     def __init__(self, x):
1025         self.x = x
1026         self.hash = ctr[0]
1027         ctr[0] += 1
1028     def __repr__(self):
1029         return "<%s %s>" % (self.__class__.__name__, self.x,)
1030     def __hash__(self):
1031         return self.hash
1032     def __le__(self, other):
1033         return self.x <= other
1034     def __lt__(self, other):
1035         return self.x < other
1036     def __ge__(self, other):
1037         return self.x >= other
1038     def __gt__(self, other):
1039         return self.x > other
1040     def __ne__(self, other):
1041         return self.x != other
1042     def __eq__(self, other):
1043         return self.x == other
1044
1045 class DictUtil(unittest.TestCase):
1046     def _help_test_empty_dict(self, klass):
1047         d1 = klass()
1048         d2 = klass({})
1049
1050         self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1051         self.failUnless(len(d1) == 0)
1052         self.failUnless(len(d2) == 0)
1053
1054     def _help_test_nonempty_dict(self, klass):
1055         d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1056         d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1057
1058         self.failUnless(d1 == d2)
1059         self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1060         self.failUnless(len(d2) == 3)
1061
1062     def _help_test_eq_but_notis(self, klass):
1063         d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1064         d.pop('b')
1065
1066         d.clear()
1067         d['a'] = 3
1068         d['b'] = EqButNotIs(3)
1069         d['c'] = 3
1070         d.pop('b')
1071
1072         d.clear()
1073         d['b'] = EqButNotIs(3)
1074         d['a'] = 3
1075         d['c'] = 3
1076         d.pop('b')
1077
1078         d.clear()
1079         d['a'] = EqButNotIs(3)
1080         d['c'] = 3
1081         d['a'] = 3
1082
1083         d.clear()
1084         fake3 = EqButNotIs(3)
1085         fake7 = EqButNotIs(7)
1086         d[fake3] = fake7
1087         d[3] = 7
1088         d[3] = 8
1089         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1090         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1091         # The real 7 should have been ejected by the d[3] = 8.
1092         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1093         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1094         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1095         d[fake3] = 8
1096
1097         d.clear()
1098         d[3] = 7
1099         fake3 = EqButNotIs(3)
1100         fake7 = EqButNotIs(7)
1101         d[fake3] = fake7
1102         d[3] = 8
1103         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1104         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1105         # The real 7 should have been ejected by the d[3] = 8.
1106         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1107         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1108         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1109         d[fake3] = 8
1110
1111     def test_all(self):
1112         self._help_test_eq_but_notis(dictutil.UtilDict)
1113         self._help_test_eq_but_notis(dictutil.NumDict)
1114         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1115         self._help_test_nonempty_dict(dictutil.UtilDict)
1116         self._help_test_nonempty_dict(dictutil.NumDict)
1117         self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1118         self._help_test_eq_but_notis(dictutil.UtilDict)
1119         self._help_test_eq_but_notis(dictutil.NumDict)
1120         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1121
1122     def test_dict_of_sets(self):
1123         ds = dictutil.DictOfSets()
1124         ds.add(1, "a")
1125         ds.add(2, "b")
1126         ds.add(2, "b")
1127         ds.add(2, "c")
1128         self.failUnlessEqual(ds[1], set(["a"]))
1129         self.failUnlessEqual(ds[2], set(["b", "c"]))
1130         ds.discard(3, "d") # should not raise an exception
1131         ds.discard(2, "b")
1132         self.failUnlessEqual(ds[2], set(["c"]))
1133         ds.discard(2, "c")
1134         self.failIf(2 in ds)
1135
1136         ds.add(3, "f")
1137         ds2 = dictutil.DictOfSets()
1138         ds2.add(3, "f")
1139         ds2.add(3, "g")
1140         ds2.add(4, "h")
1141         ds.update(ds2)
1142         self.failUnlessEqual(ds[1], set(["a"]))
1143         self.failUnlessEqual(ds[3], set(["f", "g"]))
1144         self.failUnlessEqual(ds[4], set(["h"]))
1145
1146     def test_move(self):
1147         d1 = {1: "a", 2: "b"}
1148         d2 = {2: "c", 3: "d"}
1149         dictutil.move(1, d1, d2)
1150         self.failUnlessEqual(d1, {2: "b"})
1151         self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1152
1153         d1 = {1: "a", 2: "b"}
1154         d2 = {2: "c", 3: "d"}
1155         dictutil.move(2, d1, d2)
1156         self.failUnlessEqual(d1, {1: "a"})
1157         self.failUnlessEqual(d2, {2: "b", 3: "d"})
1158
1159         d1 = {1: "a", 2: "b"}
1160         d2 = {2: "c", 3: "d"}
1161         self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1162
1163     def test_subtract(self):
1164         d1 = {1: "a", 2: "b"}
1165         d2 = {2: "c", 3: "d"}
1166         d3 = dictutil.subtract(d1, d2)
1167         self.failUnlessEqual(d3, {1: "a"})
1168
1169         d1 = {1: "a", 2: "b"}
1170         d2 = {2: "c"}
1171         d3 = dictutil.subtract(d1, d2)
1172         self.failUnlessEqual(d3, {1: "a"})
1173
1174     def test_utildict(self):
1175         d = dictutil.UtilDict({1: "a", 2: "b"})
1176         d.del_if_present(1)
1177         d.del_if_present(3)
1178         self.failUnlessEqual(d, {2: "b"})
1179         def eq(a, b):
1180             return a == b
1181         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1182
1183         d = dictutil.UtilDict({1: "b", 2: "a"})
1184         self.failUnlessEqual(d.items_sorted_by_value(),
1185                              [(2, "a"), (1, "b")])
1186         self.failUnlessEqual(d.items_sorted_by_key(),
1187                              [(1, "b"), (2, "a")])
1188         self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1189         self.failUnless(1 in d)
1190
1191         d2 = dictutil.UtilDict({3: "c", 4: "d"})
1192         self.failUnless(d != d2)
1193         self.failUnless(d2 > d)
1194         self.failUnless(d2 >= d)
1195         self.failUnless(d <= d2)
1196         self.failUnless(d < d2)
1197         self.failUnlessEqual(d[1], "b")
1198         self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1199
1200         d3 = d.copy()
1201         self.failUnlessEqual(d, d3)
1202         self.failUnless(isinstance(d3, dictutil.UtilDict))
1203
1204         d4 = d.fromkeys([3,4], "e")
1205         self.failUnlessEqual(d4, {3: "e", 4: "e"})
1206
1207         self.failUnlessEqual(d.get(1), "b")
1208         self.failUnlessEqual(d.get(3), None)
1209         self.failUnlessEqual(d.get(3, "default"), "default")
1210         self.failUnlessEqual(sorted(list(d.items())),
1211                              [(1, "b"), (2, "a")])
1212         self.failUnlessEqual(sorted(list(d.iteritems())),
1213                              [(1, "b"), (2, "a")])
1214         self.failUnlessEqual(sorted(d.keys()), [1, 2])
1215         self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1216         x = d.setdefault(1, "new")
1217         self.failUnlessEqual(x, "b")
1218         self.failUnlessEqual(d[1], "b")
1219         x = d.setdefault(3, "new")
1220         self.failUnlessEqual(x, "new")
1221         self.failUnlessEqual(d[3], "new")
1222         del d[3]
1223
1224         x = d.popitem()
1225         self.failUnless(x in [(1, "b"), (2, "a")])
1226         x = d.popitem()
1227         self.failUnless(x in [(1, "b"), (2, "a")])
1228         self.failUnlessRaises(KeyError, d.popitem)
1229
1230     def test_numdict(self):
1231         d = dictutil.NumDict({"a": 1, "b": 2})
1232
1233         d.add_num("a", 10, 5)
1234         d.add_num("c", 20, 5)
1235         d.add_num("d", 30)
1236         self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1237
1238         d.subtract_num("a", 10)
1239         d.subtract_num("e", 10)
1240         d.subtract_num("f", 10, 15)
1241         self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1242                                  "e": -10, "f": 5})
1243
1244         self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1245
1246         d = dictutil.NumDict()
1247         d.inc("a")
1248         d.inc("a")
1249         d.inc("b", 5)
1250         self.failUnlessEqual(d, {"a": 2, "b": 6})
1251         d.dec("a")
1252         d.dec("c")
1253         d.dec("d", 5)
1254         self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1255         self.failUnlessEqual(d.items_sorted_by_key(),
1256                              [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1257         self.failUnlessEqual(d.items_sorted_by_value(),
1258                              [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1259         self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1260
1261         d = dictutil.NumDict({"a": 1, "b": 2})
1262         self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1263         self.failUnless("a" in d)
1264
1265         d2 = dictutil.NumDict({"c": 3, "d": 4})
1266         self.failUnless(d != d2)
1267         self.failUnless(d2 > d)
1268         self.failUnless(d2 >= d)
1269         self.failUnless(d <= d2)
1270         self.failUnless(d < d2)
1271         self.failUnlessEqual(d["a"], 1)
1272         self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1273         def eq(a, b):
1274             return a == b
1275         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1276
1277         d3 = d.copy()
1278         self.failUnlessEqual(d, d3)
1279         self.failUnless(isinstance(d3, dictutil.NumDict))
1280
1281         d4 = d.fromkeys(["a","b"], 5)
1282         self.failUnlessEqual(d4, {"a": 5, "b": 5})
1283
1284         self.failUnlessEqual(d.get("a"), 1)
1285         self.failUnlessEqual(d.get("c"), 0)
1286         self.failUnlessEqual(d.get("c", 5), 5)
1287         self.failUnlessEqual(sorted(list(d.items())),
1288                              [("a", 1), ("b", 2)])
1289         self.failUnlessEqual(sorted(list(d.iteritems())),
1290                              [("a", 1), ("b", 2)])
1291         self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1292         self.failUnlessEqual(sorted(d.values()), [1, 2])
1293         self.failUnless(d.has_key("a"))
1294         self.failIf(d.has_key("c"))
1295
1296         x = d.setdefault("c", 3)
1297         self.failUnlessEqual(x, 3)
1298         self.failUnlessEqual(d["c"], 3)
1299         x = d.setdefault("c", 5)
1300         self.failUnlessEqual(x, 3)
1301         self.failUnlessEqual(d["c"], 3)
1302         del d["c"]
1303
1304         x = d.popitem()
1305         self.failUnless(x in [("a", 1), ("b", 2)])
1306         x = d.popitem()
1307         self.failUnless(x in [("a", 1), ("b", 2)])
1308         self.failUnlessRaises(KeyError, d.popitem)
1309
1310         d.update({"c": 3})
1311         d.update({"c": 4, "d": 5})
1312         self.failUnlessEqual(d, {"c": 4, "d": 5})
1313
1314     def test_del_if_present(self):
1315         d = {1: "a", 2: "b"}
1316         dictutil.del_if_present(d, 1)
1317         dictutil.del_if_present(d, 3)
1318         self.failUnlessEqual(d, {2: "b"})
1319
1320     def test_valueordereddict(self):
1321         d = dictutil.ValueOrderedDict()
1322         d["a"] = 3
1323         d["b"] = 2
1324         d["c"] = 1
1325
1326         self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1327         self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1328         self.failUnlessEqual(d.values(), [1, 2, 3])
1329         self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1330         self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1331         def eq(a, b):
1332             return a == b
1333         self.failIf(d == {"a": 4})
1334         self.failUnless(d != {"a": 4})
1335
1336         x = d.setdefault("d", 0)
1337         self.failUnlessEqual(x, 0)
1338         self.failUnlessEqual(d["d"], 0)
1339         x = d.setdefault("d", -1)
1340         self.failUnlessEqual(x, 0)
1341         self.failUnlessEqual(d["d"], 0)
1342
1343         x = d.remove("e", "default", False)
1344         self.failUnlessEqual(x, "default")
1345         self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1346         x = d.remove("d", 5)
1347         self.failUnlessEqual(x, 0)
1348
1349         x = d.__getitem__("c")
1350         self.failUnlessEqual(x, 1)
1351         x = d.__getitem__("e", "default", False)
1352         self.failUnlessEqual(x, "default")
1353         self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1354
1355         self.failUnlessEqual(d.popitem(), ("c", 1))
1356         self.failUnlessEqual(d.popitem(), ("b", 2))
1357         self.failUnlessEqual(d.popitem(), ("a", 3))
1358         self.failUnlessRaises(KeyError, d.popitem)
1359
1360         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1361         x = d.pop("d", "default", False)
1362         self.failUnlessEqual(x, "default")
1363         self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1364         x = d.pop("b")
1365         self.failUnlessEqual(x, 2)
1366         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1367
1368         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1369         x = d.pop_from_list(1) # pop the second item, b/2
1370         self.failUnlessEqual(x, "b")
1371         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1372
1373     def test_auxdict(self):
1374         d = dictutil.AuxValueDict()
1375         # we put the serialized form in the auxdata
1376         d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1377
1378         self.failUnlessEqual(d.keys(), ["key"])
1379         self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1380         self.failUnlessEqual(d.get_aux("key"), "serialized")
1381         def _get_missing(key):
1382             return d[key]
1383         self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1384         self.failUnlessEqual(d.get("nonkey"), None)
1385         self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1386         self.failUnlessEqual(d.get_aux("nonkey"), None)
1387         self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1388
1389         d["key"] = ("filecap2", "metadata2")
1390         self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1391         self.failUnlessEqual(d.get_aux("key"), None)
1392
1393         d.set_with_aux("key2", "value2", "aux2")
1394         self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1395         del d["key2"]
1396         self.failUnlessEqual(d.keys(), ["key"])
1397         self.failIf("key2" in d)
1398         self.failUnlessRaises(KeyError, _get_missing, "key2")
1399         self.failUnlessEqual(d.get("key2"), None)
1400         self.failUnlessEqual(d.get_aux("key2"), None)
1401         d["key2"] = "newvalue2"
1402         self.failUnlessEqual(d.get("key2"), "newvalue2")
1403         self.failUnlessEqual(d.get_aux("key2"), None)
1404
1405         d = dictutil.AuxValueDict({1:2,3:4})
1406         self.failUnlessEqual(sorted(d.keys()), [1,3])
1407         self.failUnlessEqual(d[1], 2)
1408         self.failUnlessEqual(d.get_aux(1), None)
1409
1410         d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1411         self.failUnlessEqual(sorted(d.keys()), [1,3])
1412         self.failUnlessEqual(d[1], 2)
1413         self.failUnlessEqual(d.get_aux(1), None)
1414
1415         d = dictutil.AuxValueDict(one=1, two=2)
1416         self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1417         self.failUnlessEqual(d["one"], 1)
1418         self.failUnlessEqual(d.get_aux("one"), None)
1419
1420 class Pipeline(unittest.TestCase):
1421     def pause(self, *args, **kwargs):
1422         d = defer.Deferred()
1423         self.calls.append( (d, args, kwargs) )
1424         return d
1425
1426     def failUnlessCallsAre(self, expected):
1427         #print self.calls
1428         #print expected
1429         self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1430         for i,c in enumerate(self.calls):
1431             self.failUnlessEqual(c[1:], expected[i], str(i))
1432
1433     def test_basic(self):
1434         self.calls = []
1435         finished = []
1436         p = pipeline.Pipeline(100)
1437
1438         d = p.flush() # fires immediately
1439         d.addCallbacks(finished.append, log.err)
1440         self.failUnlessEqual(len(finished), 1)
1441         finished = []
1442
1443         d = p.add(10, self.pause, "one")
1444         # the call should start right away, and our return Deferred should
1445         # fire right away
1446         d.addCallbacks(finished.append, log.err)
1447         self.failUnlessEqual(len(finished), 1)
1448         self.failUnlessEqual(finished[0], None)
1449         self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1450         self.failUnlessEqual(p.gauge, 10)
1451
1452         # pipeline: [one]
1453
1454         finished = []
1455         d = p.add(20, self.pause, "two", kw=2)
1456         # pipeline: [one, two]
1457
1458         # the call and the Deferred should fire right away
1459         d.addCallbacks(finished.append, log.err)
1460         self.failUnlessEqual(len(finished), 1)
1461         self.failUnlessEqual(finished[0], None)
1462         self.failUnlessCallsAre([ ( ("one",) , {} ),
1463                                   ( ("two",) , {"kw": 2} ),
1464                                   ])
1465         self.failUnlessEqual(p.gauge, 30)
1466
1467         self.calls[0][0].callback("one-result")
1468         # pipeline: [two]
1469         self.failUnlessEqual(p.gauge, 20)
1470
1471         finished = []
1472         d = p.add(90, self.pause, "three", "posarg1")
1473         # pipeline: [two, three]
1474         flushed = []
1475         fd = p.flush()
1476         fd.addCallbacks(flushed.append, log.err)
1477         self.failUnlessEqual(flushed, [])
1478
1479         # the call will be made right away, but the return Deferred will not,
1480         # because the pipeline is now full.
1481         d.addCallbacks(finished.append, log.err)
1482         self.failUnlessEqual(len(finished), 0)
1483         self.failUnlessCallsAre([ ( ("one",) , {} ),
1484                                   ( ("two",) , {"kw": 2} ),
1485                                   ( ("three", "posarg1"), {} ),
1486                                   ])
1487         self.failUnlessEqual(p.gauge, 110)
1488
1489         self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1490
1491         # retiring either call will unblock the pipeline, causing the #3
1492         # Deferred to fire
1493         self.calls[2][0].callback("three-result")
1494         # pipeline: [two]
1495
1496         self.failUnlessEqual(len(finished), 1)
1497         self.failUnlessEqual(finished[0], None)
1498         self.failUnlessEqual(flushed, [])
1499
1500         # retiring call#2 will finally allow the flush() Deferred to fire
1501         self.calls[1][0].callback("two-result")
1502         self.failUnlessEqual(len(flushed), 1)
1503
1504     def test_errors(self):
1505         self.calls = []
1506         p = pipeline.Pipeline(100)
1507
1508         d1 = p.add(200, self.pause, "one")
1509         d2 = p.flush()
1510
1511         finished = []
1512         d1.addBoth(finished.append)
1513         self.failUnlessEqual(finished, [])
1514
1515         flushed = []
1516         d2.addBoth(flushed.append)
1517         self.failUnlessEqual(flushed, [])
1518
1519         self.calls[0][0].errback(ValueError("oops"))
1520
1521         self.failUnlessEqual(len(finished), 1)
1522         f = finished[0]
1523         self.failUnless(isinstance(f, Failure))
1524         self.failUnless(f.check(pipeline.PipelineError))
1525         self.failUnlessIn("PipelineError", str(f.value))
1526         self.failUnlessIn("ValueError", str(f.value))
1527         r = repr(f.value)
1528         self.failUnless("ValueError" in r, r)
1529         f2 = f.value.error
1530         self.failUnless(f2.check(ValueError))
1531
1532         self.failUnlessEqual(len(flushed), 1)
1533         f = flushed[0]
1534         self.failUnless(isinstance(f, Failure))
1535         self.failUnless(f.check(pipeline.PipelineError))
1536         f2 = f.value.error
1537         self.failUnless(f2.check(ValueError))
1538
1539         # now that the pipeline is in the failed state, any new calls will
1540         # fail immediately
1541
1542         d3 = p.add(20, self.pause, "two")
1543
1544         finished = []
1545         d3.addBoth(finished.append)
1546         self.failUnlessEqual(len(finished), 1)
1547         f = finished[0]
1548         self.failUnless(isinstance(f, Failure))
1549         self.failUnless(f.check(pipeline.PipelineError))
1550         r = repr(f.value)
1551         self.failUnless("ValueError" in r, r)
1552         f2 = f.value.error
1553         self.failUnless(f2.check(ValueError))
1554
1555         d4 = p.flush()
1556         flushed = []
1557         d4.addBoth(flushed.append)
1558         self.failUnlessEqual(len(flushed), 1)
1559         f = flushed[0]
1560         self.failUnless(isinstance(f, Failure))
1561         self.failUnless(f.check(pipeline.PipelineError))
1562         f2 = f.value.error
1563         self.failUnless(f2.check(ValueError))
1564
1565     def test_errors2(self):
1566         self.calls = []
1567         p = pipeline.Pipeline(100)
1568
1569         d1 = p.add(10, self.pause, "one")
1570         d2 = p.add(20, self.pause, "two")
1571         d3 = p.add(30, self.pause, "three")
1572         d4 = p.flush()
1573
1574         # one call fails, then the second one succeeds: make sure
1575         # ExpandableDeferredList tolerates the second one
1576
1577         flushed = []
1578         d4.addBoth(flushed.append)
1579         self.failUnlessEqual(flushed, [])
1580
1581         self.calls[0][0].errback(ValueError("oops"))
1582         self.failUnlessEqual(len(flushed), 1)
1583         f = flushed[0]
1584         self.failUnless(isinstance(f, Failure))
1585         self.failUnless(f.check(pipeline.PipelineError))
1586         f2 = f.value.error
1587         self.failUnless(f2.check(ValueError))
1588
1589         self.calls[1][0].callback("two-result")
1590         self.calls[2][0].errback(ValueError("three-error"))
1591
1592         del d1,d2,d3,d4
1593
1594 class SampleError(Exception):
1595     pass
1596
1597 class Log(unittest.TestCase):
1598     def test_err(self):
1599         if not hasattr(self, "flushLoggedErrors"):
1600             # without flushLoggedErrors, we can't get rid of the
1601             # twisted.log.err that tahoe_log records, so we can't keep this
1602             # test from [ERROR]ing
1603             raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1604         try:
1605             raise SampleError("simple sample")
1606         except:
1607             f = Failure()
1608         tahoe_log.err(format="intentional sample error",
1609                       failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1610         self.flushLoggedErrors(SampleError)
1611
1612
1613 class SimpleSpans:
1614     # this is a simple+inefficient form of util.spans.Spans . We compare the
1615     # behavior of this reference model against the real (efficient) form.
1616
1617     def __init__(self, _span_or_start=None, length=None):
1618         self._have = set()
1619         if length is not None:
1620             for i in range(_span_or_start, _span_or_start+length):
1621                 self._have.add(i)
1622         elif _span_or_start:
1623             for (start,length) in _span_or_start:
1624                 self.add(start, length)
1625
1626     def add(self, start, length):
1627         for i in range(start, start+length):
1628             self._have.add(i)
1629         return self
1630
1631     def remove(self, start, length):
1632         for i in range(start, start+length):
1633             self._have.discard(i)
1634         return self
1635
1636     def each(self):
1637         return sorted(self._have)
1638
1639     def __iter__(self):
1640         items = sorted(self._have)
1641         prevstart = None
1642         prevend = None
1643         for i in items:
1644             if prevstart is None:
1645                 prevstart = prevend = i
1646                 continue
1647             if i == prevend+1:
1648                 prevend = i
1649                 continue
1650             yield (prevstart, prevend-prevstart+1)
1651             prevstart = prevend = i
1652         if prevstart is not None:
1653             yield (prevstart, prevend-prevstart+1)
1654
1655     def __nonzero__(self): # this gets us bool()
1656         return self.len()
1657
1658     def len(self):
1659         return len(self._have)
1660
1661     def __add__(self, other):
1662         s = self.__class__(self)
1663         for (start, length) in other:
1664             s.add(start, length)
1665         return s
1666
1667     def __sub__(self, other):
1668         s = self.__class__(self)
1669         for (start, length) in other:
1670             s.remove(start, length)
1671         return s
1672
1673     def __iadd__(self, other):
1674         for (start, length) in other:
1675             self.add(start, length)
1676         return self
1677
1678     def __isub__(self, other):
1679         for (start, length) in other:
1680             self.remove(start, length)
1681         return self
1682
1683     def __and__(self, other):
1684         s = self.__class__()
1685         for i in other.each():
1686             if i in self._have:
1687                 s.add(i, 1)
1688         return s
1689
1690     def __contains__(self, (start,length)):
1691         for i in range(start, start+length):
1692             if i not in self._have:
1693                 return False
1694         return True
1695
1696 class ByteSpans(unittest.TestCase):
1697     def test_basic(self):
1698         s = Spans()
1699         self.failUnlessEqual(list(s), [])
1700         self.failIf(s)
1701         self.failIf((0,1) in s)
1702         self.failUnlessEqual(s.len(), 0)
1703
1704         s1 = Spans(3, 4) # 3,4,5,6
1705         self._check1(s1)
1706
1707         s1 = Spans(3L, 4L) # 3,4,5,6
1708         self._check1(s1)
1709
1710         s2 = Spans(s1)
1711         self._check1(s2)
1712
1713         s2.add(10,2) # 10,11
1714         self._check1(s1)
1715         self.failUnless((10,1) in s2)
1716         self.failIf((10,1) in s1)
1717         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1718         self.failUnlessEqual(s2.len(), 6)
1719
1720         s2.add(15,2).add(20,2)
1721         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1722         self.failUnlessEqual(s2.len(), 10)
1723
1724         s2.remove(4,3).remove(15,1)
1725         self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1726         self.failUnlessEqual(s2.len(), 6)
1727
1728         s1 = SimpleSpans(3, 4) # 3 4 5 6
1729         s2 = SimpleSpans(5, 4) # 5 6 7 8
1730         i = s1 & s2
1731         self.failUnlessEqual(list(i.each()), [5, 6])
1732
1733     def _check1(self, s):
1734         self.failUnlessEqual(list(s), [(3,4)])
1735         self.failUnless(s)
1736         self.failUnlessEqual(s.len(), 4)
1737         self.failIf((0,1) in s)
1738         self.failUnless((3,4) in s)
1739         self.failUnless((3,1) in s)
1740         self.failUnless((5,2) in s)
1741         self.failUnless((6,1) in s)
1742         self.failIf((6,2) in s)
1743         self.failIf((7,1) in s)
1744         self.failUnlessEqual(list(s.each()), [3,4,5,6])
1745
1746     def test_large(self):
1747         s = Spans(4, 2**65) # don't do this with a SimpleSpans
1748         self.failUnlessEqual(list(s), [(4, 2**65)])
1749         self.failUnless(s)
1750         self.failUnlessEqual(s.len(), 2**65)
1751         self.failIf((0,1) in s)
1752         self.failUnless((4,2) in s)
1753         self.failUnless((2**65,2) in s)
1754
1755     def test_math(self):
1756         s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1757         s2 = Spans(5, 3) # 5,6,7
1758         s3 = Spans(8, 4) # 8,9,10,11
1759
1760         s = s1 - s2
1761         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1762         s = s1 - s3
1763         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1764         s = s2 - s3
1765         self.failUnlessEqual(list(s.each()), [5,6,7])
1766         s = s1 & s2
1767         self.failUnlessEqual(list(s.each()), [5,6,7])
1768         s = s2 & s1
1769         self.failUnlessEqual(list(s.each()), [5,6,7])
1770         s = s1 & s3
1771         self.failUnlessEqual(list(s.each()), [8,9])
1772         s = s3 & s1
1773         self.failUnlessEqual(list(s.each()), [8,9])
1774         s = s2 & s3
1775         self.failUnlessEqual(list(s.each()), [])
1776         s = s3 & s2
1777         self.failUnlessEqual(list(s.each()), [])
1778         s = Spans() & s3
1779         self.failUnlessEqual(list(s.each()), [])
1780         s = s3 & Spans()
1781         self.failUnlessEqual(list(s.each()), [])
1782
1783         s = s1 + s2
1784         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1785         s = s1 + s3
1786         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1787         s = s2 + s3
1788         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1789
1790         s = Spans(s1)
1791         s -= s2
1792         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1793         s = Spans(s1)
1794         s -= s3
1795         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1796         s = Spans(s2)
1797         s -= s3
1798         self.failUnlessEqual(list(s.each()), [5,6,7])
1799
1800         s = Spans(s1)
1801         s += s2
1802         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1803         s = Spans(s1)
1804         s += s3
1805         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1806         s = Spans(s2)
1807         s += s3
1808         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1809
1810     def test_random(self):
1811         # attempt to increase coverage of corner cases by comparing behavior
1812         # of a simple-but-slow model implementation against the
1813         # complex-but-fast actual implementation, in a large number of random
1814         # operations
1815         S1 = SimpleSpans
1816         S2 = Spans
1817         s1 = S1(); s2 = S2()
1818         seed = ""
1819         def _create(subseed):
1820             ns1 = S1(); ns2 = S2()
1821             for i in range(10):
1822                 what = _hash(subseed+str(i)).hexdigest()
1823                 start = int(what[2:4], 16)
1824                 length = max(1,int(what[5:6], 16))
1825                 ns1.add(start, length); ns2.add(start, length)
1826             return ns1, ns2
1827
1828         #print
1829         for i in range(1000):
1830             what = _hash(seed+str(i)).hexdigest()
1831             op = what[0]
1832             subop = what[1]
1833             start = int(what[2:4], 16)
1834             length = max(1,int(what[5:6], 16))
1835             #print what
1836             if op in "0":
1837                 if subop in "01234":
1838                     s1 = S1(); s2 = S2()
1839                 elif subop in "5678":
1840                     s1 = S1(start, length); s2 = S2(start, length)
1841                 else:
1842                     s1 = S1(s1); s2 = S2(s2)
1843                 #print "s2 = %s" % s2.dump()
1844             elif op in "123":
1845                 #print "s2.add(%d,%d)" % (start, length)
1846                 s1.add(start, length); s2.add(start, length)
1847             elif op in "456":
1848                 #print "s2.remove(%d,%d)" % (start, length)
1849                 s1.remove(start, length); s2.remove(start, length)
1850             elif op in "78":
1851                 ns1, ns2 = _create(what[7:11])
1852                 #print "s2 + %s" % ns2.dump()
1853                 s1 = s1 + ns1; s2 = s2 + ns2
1854             elif op in "9a":
1855                 ns1, ns2 = _create(what[7:11])
1856                 #print "%s - %s" % (s2.dump(), ns2.dump())
1857                 s1 = s1 - ns1; s2 = s2 - ns2
1858             elif op in "bc":
1859                 ns1, ns2 = _create(what[7:11])
1860                 #print "s2 += %s" % ns2.dump()
1861                 s1 += ns1; s2 += ns2
1862             elif op in "de":
1863                 ns1, ns2 = _create(what[7:11])
1864                 #print "%s -= %s" % (s2.dump(), ns2.dump())
1865                 s1 -= ns1; s2 -= ns2
1866             else:
1867                 ns1, ns2 = _create(what[7:11])
1868                 #print "%s &= %s" % (s2.dump(), ns2.dump())
1869                 s1 = s1 & ns1; s2 = s2 & ns2
1870             #print "s2 now %s" % s2.dump()
1871             self.failUnlessEqual(list(s1.each()), list(s2.each()))
1872             self.failUnlessEqual(s1.len(), s2.len())
1873             self.failUnlessEqual(bool(s1), bool(s2))
1874             self.failUnlessEqual(list(s1), list(s2))
1875             for j in range(10):
1876                 what = _hash(what[12:14]+str(j)).hexdigest()
1877                 start = int(what[2:4], 16)
1878                 length = max(1, int(what[5:6], 16))
1879                 span = (start, length)
1880                 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1881
1882
1883     # s()
1884     # s(start,length)
1885     # s(s0)
1886     # s.add(start,length) : returns s
1887     # s.remove(start,length)
1888     # s.each() -> list of byte offsets, mostly for testing
1889     # list(s) -> list of (start,length) tuples, one per span
1890     # (start,length) in s -> True if (start..start+length-1) are all members
1891     #  NOT equivalent to x in list(s)
1892     # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
1893     # bool(s)  (__nonzeron__)
1894     # s = s1+s2, s1-s2, +=s1, -=s1
1895
1896     def test_overlap(self):
1897         for a in range(20):
1898             for b in range(10):
1899                 for c in range(20):
1900                     for d in range(10):
1901                         self._test_overlap(a,b,c,d)
1902
1903     def _test_overlap(self, a, b, c, d):
1904         s1 = set(range(a,a+b))
1905         s2 = set(range(c,c+d))
1906         #print "---"
1907         #self._show_overlap(s1, "1")
1908         #self._show_overlap(s2, "2")
1909         o = overlap(a,b,c,d)
1910         expected = s1.intersection(s2)
1911         if not expected:
1912             self.failUnlessEqual(o, None)
1913         else:
1914             start,length = o
1915             so = set(range(start,start+length))
1916             #self._show(so, "o")
1917             self.failUnlessEqual(so, expected)
1918
1919     def _show_overlap(self, s, c):
1920         import sys
1921         out = sys.stdout
1922         if s:
1923             for i in range(max(s)):
1924                 if i in s:
1925                     out.write(c)
1926                 else:
1927                     out.write(" ")
1928         out.write("\n")
1929
1930 def extend(s, start, length, fill):
1931     if len(s) >= start+length:
1932         return s
1933     assert len(fill) == 1
1934     return s + fill*(start+length-len(s))
1935
1936 def replace(s, start, data):
1937     assert len(s) >= start+len(data)
1938     return s[:start] + data + s[start+len(data):]
1939
1940 class SimpleDataSpans:
1941     def __init__(self, other=None):
1942         self.missing = "" # "1" where missing, "0" where found
1943         self.data = ""
1944         if other:
1945             for (start, data) in other.get_chunks():
1946                 self.add(start, data)
1947
1948     def __nonzero__(self): # this gets us bool()
1949         return self.len()
1950     def len(self):
1951         return len(self.missing.replace("1", ""))
1952     def _dump(self):
1953         return [i for (i,c) in enumerate(self.missing) if c == "0"]
1954     def _have(self, start, length):
1955         m = self.missing[start:start+length]
1956         if not m or len(m)<length or int(m):
1957             return False
1958         return True
1959     def get_chunks(self):
1960         for i in self._dump():
1961             yield (i, self.data[i])
1962     def get_spans(self):
1963         return SimpleSpans([(start,len(data))
1964                             for (start,data) in self.get_chunks()])
1965     def get(self, start, length):
1966         if self._have(start, length):
1967             return self.data[start:start+length]
1968         return None
1969     def pop(self, start, length):
1970         data = self.get(start, length)
1971         if data:
1972             self.remove(start, length)
1973         return data
1974     def remove(self, start, length):
1975         self.missing = replace(extend(self.missing, start, length, "1"),
1976                                start, "1"*length)
1977     def add(self, start, data):
1978         self.missing = replace(extend(self.missing, start, len(data), "1"),
1979                                start, "0"*len(data))
1980         self.data = replace(extend(self.data, start, len(data), " "),
1981                             start, data)
1982
1983
1984 class StringSpans(unittest.TestCase):
1985     def do_basic(self, klass):
1986         ds = klass()
1987         self.failUnlessEqual(ds.len(), 0)
1988         self.failUnlessEqual(list(ds._dump()), [])
1989         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
1990         s1 = ds.get_spans()
1991         self.failUnlessEqual(ds.get(0, 4), None)
1992         self.failUnlessEqual(ds.pop(0, 4), None)
1993         ds.remove(0, 4)
1994
1995         ds.add(2, "four")
1996         self.failUnlessEqual(ds.len(), 4)
1997         self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
1998         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
1999         s1 = ds.get_spans()
2000         self.failUnless((2,2) in s1)
2001         self.failUnlessEqual(ds.get(0, 4), None)
2002         self.failUnlessEqual(ds.pop(0, 4), None)
2003         self.failUnlessEqual(ds.get(4, 4), None)
2004
2005         ds2 = klass(ds)
2006         self.failUnlessEqual(ds2.len(), 4)
2007         self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2008         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2009         self.failUnlessEqual(ds2.get(0, 4), None)
2010         self.failUnlessEqual(ds2.pop(0, 4), None)
2011         self.failUnlessEqual(ds2.pop(2, 3), "fou")
2012         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2013         self.failUnlessEqual(ds2.get(2, 3), None)
2014         self.failUnlessEqual(ds2.get(5, 1), "r")
2015         self.failUnlessEqual(ds.get(2, 3), "fou")
2016         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2017
2018         ds.add(0, "23")
2019         self.failUnlessEqual(ds.len(), 6)
2020         self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2021         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2022         self.failUnlessEqual(ds.get(0, 4), "23fo")
2023         self.failUnlessEqual(ds.pop(0, 4), "23fo")
2024         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2025         self.failUnlessEqual(ds.get(0, 4), None)
2026         self.failUnlessEqual(ds.pop(0, 4), None)
2027
2028         ds = klass()
2029         ds.add(2, "four")
2030         ds.add(3, "ea")
2031         self.failUnlessEqual(ds.get(2, 4), "fear")
2032
2033         ds = klass()
2034         ds.add(2L, "four")
2035         ds.add(3L, "ea")
2036         self.failUnlessEqual(ds.get(2L, 4L), "fear")
2037
2038
2039     def do_scan(self, klass):
2040         # do a test with gaps and spans of size 1 and 2
2041         #  left=(1,11) * right=(1,11) * gapsize=(1,2)
2042         # 111, 112, 121, 122, 211, 212, 221, 222
2043         #    211
2044         #      121
2045         #         112
2046         #            212
2047         #               222
2048         #                   221
2049         #                      111
2050         #                        122
2051         #  11 1  1 11 11  11  1 1  111
2052         # 0123456789012345678901234567
2053         # abcdefghijklmnopqrstuvwxyz-=
2054         pieces = [(1, "bc"),
2055                   (4, "e"),
2056                   (7, "h"),
2057                   (9, "jk"),
2058                   (12, "mn"),
2059                   (16, "qr"),
2060                   (20, "u"),
2061                   (22, "w"),
2062                   (25, "z-="),
2063                   ]
2064         p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2065         S = "abcdefghijklmnopqrstuvwxyz-="
2066         # TODO: when adding data, add capital letters, to make sure we aren't
2067         # just leaving the old data in place
2068         l = len(S)
2069         def base():
2070             ds = klass()
2071             for start, data in pieces:
2072                 ds.add(start, data)
2073             return ds
2074         def dump(s):
2075             p = set(s._dump())
2076             d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2077             assert len(d) == l
2078             return d
2079         DEBUG = False
2080         for start in range(0, l):
2081             for end in range(start+1, l):
2082                 # add [start-end) to the baseline
2083                 which = "%d-%d" % (start, end-1)
2084                 p_added = set(range(start, end))
2085                 b = base()
2086                 if DEBUG:
2087                     print
2088                     print dump(b), which
2089                     add = klass(); add.add(start, S[start:end])
2090                     print dump(add)
2091                 b.add(start, S[start:end])
2092                 if DEBUG:
2093                     print dump(b)
2094                 # check that the new span is there
2095                 d = b.get(start, end-start)
2096                 self.failUnlessEqual(d, S[start:end], which)
2097                 # check that all the original pieces are still there
2098                 for t_start, t_data in pieces:
2099                     t_len = len(t_data)
2100                     self.failUnlessEqual(b.get(t_start, t_len),
2101                                          S[t_start:t_start+t_len],
2102                                          "%s %d+%d" % (which, t_start, t_len))
2103                 # check that a lot of subspans are mostly correct
2104                 for t_start in range(l):
2105                     for t_len in range(1,4):
2106                         d = b.get(t_start, t_len)
2107                         if d is not None:
2108                             which2 = "%s+(%d-%d)" % (which, t_start,
2109                                                      t_start+t_len-1)
2110                             self.failUnlessEqual(d, S[t_start:t_start+t_len],
2111                                                  which2)
2112                         # check that removing a subspan gives the right value
2113                         b2 = klass(b)
2114                         b2.remove(t_start, t_len)
2115                         removed = set(range(t_start, t_start+t_len))
2116                         for i in range(l):
2117                             exp = (((i in p_elements) or (i in p_added))
2118                                    and (i not in removed))
2119                             which2 = "%s-(%d-%d)" % (which, t_start,
2120                                                      t_start+t_len-1)
2121                             self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2122                                                  which2+" %d" % i)
2123
2124     def test_test(self):
2125         self.do_basic(SimpleDataSpans)
2126         self.do_scan(SimpleDataSpans)
2127
2128     def test_basic(self):
2129         self.do_basic(DataSpans)
2130         self.do_scan(DataSpans)
2131
2132     def test_random(self):
2133         # attempt to increase coverage of corner cases by comparing behavior
2134         # of a simple-but-slow model implementation against the
2135         # complex-but-fast actual implementation, in a large number of random
2136         # operations
2137         S1 = SimpleDataSpans
2138         S2 = DataSpans
2139         s1 = S1(); s2 = S2()
2140         seed = ""
2141         def _randstr(length, seed):
2142             created = 0
2143             pieces = []
2144             while created < length:
2145                 piece = _hash(seed + str(created)).hexdigest()
2146                 pieces.append(piece)
2147                 created += len(piece)
2148             return "".join(pieces)[:length]
2149         def _create(subseed):
2150             ns1 = S1(); ns2 = S2()
2151             for i in range(10):
2152                 what = _hash(subseed+str(i)).hexdigest()
2153                 start = int(what[2:4], 16)
2154                 length = max(1,int(what[5:6], 16))
2155                 ns1.add(start, _randstr(length, what[7:9]));
2156                 ns2.add(start, _randstr(length, what[7:9]))
2157             return ns1, ns2
2158
2159         #print
2160         for i in range(1000):
2161             what = _hash(seed+str(i)).hexdigest()
2162             op = what[0]
2163             subop = what[1]
2164             start = int(what[2:4], 16)
2165             length = max(1,int(what[5:6], 16))
2166             #print what
2167             if op in "0":
2168                 if subop in "0123456":
2169                     s1 = S1(); s2 = S2()
2170                 else:
2171                     s1, s2 = _create(what[7:11])
2172                 #print "s2 = %s" % list(s2._dump())
2173             elif op in "123456":
2174                 #print "s2.add(%d,%d)" % (start, length)
2175                 s1.add(start, _randstr(length, what[7:9]));
2176                 s2.add(start, _randstr(length, what[7:9]))
2177             elif op in "789abc":
2178                 #print "s2.remove(%d,%d)" % (start, length)
2179                 s1.remove(start, length); s2.remove(start, length)
2180             else:
2181                 #print "s2.pop(%d,%d)" % (start, length)
2182                 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2183                 self.failUnlessEqual(d1, d2)
2184             #print "s1 now %s" % list(s1._dump())
2185             #print "s2 now %s" % list(s2._dump())
2186             self.failUnlessEqual(s1.len(), s2.len())
2187             self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2188             for j in range(100):
2189                 what = _hash(what[12:14]+str(j)).hexdigest()
2190                 start = int(what[2:4], 16)
2191                 length = max(1, int(what[5:6], 16))
2192                 d1 = s1.get(start, length); d2 = s2.get(start, length)
2193                 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))