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