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