src/allmydata/test/test_util.py

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