src/allmydata/test/test_util.py

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