src/allmydata/test/test_util.py

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