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