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