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