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