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     def test_format_delta(self):
1025         time_1 = 1389812723
1026         time_5s_delta = 1389812728
1027         time_28m7s_delta = 1389814410
1028         time_1h_delta = 1389816323
1029         time_1d21h46m49s_delta = 1389977532
1030
1031         self.failUnlessEqual(
1032             time_format.format_delta(time_1, time_1), '0s')
1033
1034         self.failUnlessEqual(
1035             time_format.format_delta(time_1, time_5s_delta), '5s')
1036         self.failUnlessEqual(
1037             time_format.format_delta(time_1, time_28m7s_delta), '28m 7s')
1038         self.failUnlessEqual(
1039             time_format.format_delta(time_1, time_1h_delta), '1h 0m 0s')
1040         self.failUnlessEqual(
1041             time_format.format_delta(time_1, time_1d21h46m49s_delta), '1d 21h 46m 49s')
1042
1043         self.failUnlessEqual(
1044             time_format.format_delta(time_1d21h46m49s_delta, time_1), '-')
1045
1046         # time_1 with a decimal fraction will make the delta 1s less
1047         time_1decimal = 1389812723.383963
1048
1049         self.failUnlessEqual(
1050             time_format.format_delta(time_1decimal, time_5s_delta), '4s')
1051         self.failUnlessEqual(
1052             time_format.format_delta(time_1decimal, time_28m7s_delta), '28m 6s')
1053         self.failUnlessEqual(
1054             time_format.format_delta(time_1decimal, time_1h_delta), '59m 59s')
1055         self.failUnlessEqual(
1056             time_format.format_delta(time_1decimal, time_1d21h46m49s_delta), '1d 21h 46m 48s')
1057
1058 class CacheDir(unittest.TestCase):
1059     def test_basic(self):
1060         basedir = "test_util/CacheDir/test_basic"
1061
1062         def _failIfExists(name):
1063             absfn = os.path.join(basedir, name)
1064             self.failIf(os.path.exists(absfn),
1065                         "%s exists but it shouldn't" % absfn)
1066
1067         def _failUnlessExists(name):
1068             absfn = os.path.join(basedir, name)
1069             self.failUnless(os.path.exists(absfn),
1070                             "%s doesn't exist but it should" % absfn)
1071
1072         cdm = cachedir.CacheDirectoryManager(basedir)
1073         a = cdm.get_file("a")
1074         b = cdm.get_file("b")
1075         c = cdm.get_file("c")
1076         f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
1077         f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
1078         f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
1079
1080         _failUnlessExists("a")
1081         _failUnlessExists("b")
1082         _failUnlessExists("c")
1083
1084         cdm.check()
1085
1086         _failUnlessExists("a")
1087         _failUnlessExists("b")
1088         _failUnlessExists("c")
1089
1090         del a
1091         # this file won't be deleted yet, because it isn't old enough
1092         cdm.check()
1093         _failUnlessExists("a")
1094         _failUnlessExists("b")
1095         _failUnlessExists("c")
1096
1097         # we change the definition of "old" to make everything old
1098         cdm.old = -10
1099
1100         cdm.check()
1101         _failIfExists("a")
1102         _failUnlessExists("b")
1103         _failUnlessExists("c")
1104
1105         cdm.old = 60*60
1106
1107         del b
1108
1109         cdm.check()
1110         _failIfExists("a")
1111         _failUnlessExists("b")
1112         _failUnlessExists("c")
1113
1114         b2 = cdm.get_file("b")
1115
1116         cdm.check()
1117         _failIfExists("a")
1118         _failUnlessExists("b")
1119         _failUnlessExists("c")
1120         del b2
1121
1122 ctr = [0]
1123 class EqButNotIs:
1124     def __init__(self, x):
1125         self.x = x
1126         self.hash = ctr[0]
1127         ctr[0] += 1
1128     def __repr__(self):
1129         return "<%s %s>" % (self.__class__.__name__, self.x,)
1130     def __hash__(self):
1131         return self.hash
1132     def __le__(self, other):
1133         return self.x <= other
1134     def __lt__(self, other):
1135         return self.x < other
1136     def __ge__(self, other):
1137         return self.x >= other
1138     def __gt__(self, other):
1139         return self.x > other
1140     def __ne__(self, other):
1141         return self.x != other
1142     def __eq__(self, other):
1143         return self.x == other
1144
1145 class DictUtil(unittest.TestCase):
1146     def _help_test_empty_dict(self, klass):
1147         d1 = klass()
1148         d2 = klass({})
1149
1150         self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1151         self.failUnless(len(d1) == 0)
1152         self.failUnless(len(d2) == 0)
1153
1154     def _help_test_nonempty_dict(self, klass):
1155         d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1156         d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1157
1158         self.failUnless(d1 == d2)
1159         self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1160         self.failUnless(len(d2) == 3)
1161
1162     def _help_test_eq_but_notis(self, klass):
1163         d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1164         d.pop('b')
1165
1166         d.clear()
1167         d['a'] = 3
1168         d['b'] = EqButNotIs(3)
1169         d['c'] = 3
1170         d.pop('b')
1171
1172         d.clear()
1173         d['b'] = EqButNotIs(3)
1174         d['a'] = 3
1175         d['c'] = 3
1176         d.pop('b')
1177
1178         d.clear()
1179         d['a'] = EqButNotIs(3)
1180         d['c'] = 3
1181         d['a'] = 3
1182
1183         d.clear()
1184         fake3 = EqButNotIs(3)
1185         fake7 = EqButNotIs(7)
1186         d[fake3] = fake7
1187         d[3] = 7
1188         d[3] = 8
1189         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1190         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1191         # The real 7 should have been ejected by the d[3] = 8.
1192         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1193         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1194         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1195         d[fake3] = 8
1196
1197         d.clear()
1198         d[3] = 7
1199         fake3 = EqButNotIs(3)
1200         fake7 = EqButNotIs(7)
1201         d[fake3] = fake7
1202         d[3] = 8
1203         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1204         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1205         # The real 7 should have been ejected by the d[3] = 8.
1206         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1207         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1208         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1209         d[fake3] = 8
1210
1211     def test_all(self):
1212         self._help_test_eq_but_notis(dictutil.UtilDict)
1213         self._help_test_eq_but_notis(dictutil.NumDict)
1214         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1215         self._help_test_nonempty_dict(dictutil.UtilDict)
1216         self._help_test_nonempty_dict(dictutil.NumDict)
1217         self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1218         self._help_test_eq_but_notis(dictutil.UtilDict)
1219         self._help_test_eq_but_notis(dictutil.NumDict)
1220         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1221
1222     def test_dict_of_sets(self):
1223         ds = dictutil.DictOfSets()
1224         ds.add(1, "a")
1225         ds.add(2, "b")
1226         ds.add(2, "b")
1227         ds.add(2, "c")
1228         self.failUnlessEqual(ds[1], set(["a"]))
1229         self.failUnlessEqual(ds[2], set(["b", "c"]))
1230         ds.discard(3, "d") # should not raise an exception
1231         ds.discard(2, "b")
1232         self.failUnlessEqual(ds[2], set(["c"]))
1233         ds.discard(2, "c")
1234         self.failIf(2 in ds)
1235
1236         ds.add(3, "f")
1237         ds2 = dictutil.DictOfSets()
1238         ds2.add(3, "f")
1239         ds2.add(3, "g")
1240         ds2.add(4, "h")
1241         ds.update(ds2)
1242         self.failUnlessEqual(ds[1], set(["a"]))
1243         self.failUnlessEqual(ds[3], set(["f", "g"]))
1244         self.failUnlessEqual(ds[4], set(["h"]))
1245
1246     def test_move(self):
1247         d1 = {1: "a", 2: "b"}
1248         d2 = {2: "c", 3: "d"}
1249         dictutil.move(1, d1, d2)
1250         self.failUnlessEqual(d1, {2: "b"})
1251         self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1252
1253         d1 = {1: "a", 2: "b"}
1254         d2 = {2: "c", 3: "d"}
1255         dictutil.move(2, d1, d2)
1256         self.failUnlessEqual(d1, {1: "a"})
1257         self.failUnlessEqual(d2, {2: "b", 3: "d"})
1258
1259         d1 = {1: "a", 2: "b"}
1260         d2 = {2: "c", 3: "d"}
1261         self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1262
1263     def test_subtract(self):
1264         d1 = {1: "a", 2: "b"}
1265         d2 = {2: "c", 3: "d"}
1266         d3 = dictutil.subtract(d1, d2)
1267         self.failUnlessEqual(d3, {1: "a"})
1268
1269         d1 = {1: "a", 2: "b"}
1270         d2 = {2: "c"}
1271         d3 = dictutil.subtract(d1, d2)
1272         self.failUnlessEqual(d3, {1: "a"})
1273
1274     def test_utildict(self):
1275         d = dictutil.UtilDict({1: "a", 2: "b"})
1276         d.del_if_present(1)
1277         d.del_if_present(3)
1278         self.failUnlessEqual(d, {2: "b"})
1279         def eq(a, b):
1280             return a == b
1281         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1282
1283         d = dictutil.UtilDict({1: "b", 2: "a"})
1284         self.failUnlessEqual(d.items_sorted_by_value(),
1285                              [(2, "a"), (1, "b")])
1286         self.failUnlessEqual(d.items_sorted_by_key(),
1287                              [(1, "b"), (2, "a")])
1288         self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1289         self.failUnless(1 in d)
1290
1291         d2 = dictutil.UtilDict({3: "c", 4: "d"})
1292         self.failUnless(d != d2)
1293         self.failUnless(d2 > d)
1294         self.failUnless(d2 >= d)
1295         self.failUnless(d <= d2)
1296         self.failUnless(d < d2)
1297         self.failUnlessEqual(d[1], "b")
1298         self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1299
1300         d3 = d.copy()
1301         self.failUnlessEqual(d, d3)
1302         self.failUnless(isinstance(d3, dictutil.UtilDict))
1303
1304         d4 = d.fromkeys([3,4], "e")
1305         self.failUnlessEqual(d4, {3: "e", 4: "e"})
1306
1307         self.failUnlessEqual(d.get(1), "b")
1308         self.failUnlessEqual(d.get(3), None)
1309         self.failUnlessEqual(d.get(3, "default"), "default")
1310         self.failUnlessEqual(sorted(list(d.items())),
1311                              [(1, "b"), (2, "a")])
1312         self.failUnlessEqual(sorted(list(d.iteritems())),
1313                              [(1, "b"), (2, "a")])
1314         self.failUnlessEqual(sorted(d.keys()), [1, 2])
1315         self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1316         x = d.setdefault(1, "new")
1317         self.failUnlessEqual(x, "b")
1318         self.failUnlessEqual(d[1], "b")
1319         x = d.setdefault(3, "new")
1320         self.failUnlessEqual(x, "new")
1321         self.failUnlessEqual(d[3], "new")
1322         del d[3]
1323
1324         x = d.popitem()
1325         self.failUnless(x in [(1, "b"), (2, "a")])
1326         x = d.popitem()
1327         self.failUnless(x in [(1, "b"), (2, "a")])
1328         self.failUnlessRaises(KeyError, d.popitem)
1329
1330     def test_numdict(self):
1331         d = dictutil.NumDict({"a": 1, "b": 2})
1332
1333         d.add_num("a", 10, 5)
1334         d.add_num("c", 20, 5)
1335         d.add_num("d", 30)
1336         self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1337
1338         d.subtract_num("a", 10)
1339         d.subtract_num("e", 10)
1340         d.subtract_num("f", 10, 15)
1341         self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1342                                  "e": -10, "f": 5})
1343
1344         self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1345
1346         d = dictutil.NumDict()
1347         d.inc("a")
1348         d.inc("a")
1349         d.inc("b", 5)
1350         self.failUnlessEqual(d, {"a": 2, "b": 6})
1351         d.dec("a")
1352         d.dec("c")
1353         d.dec("d", 5)
1354         self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1355         self.failUnlessEqual(d.items_sorted_by_key(),
1356                              [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1357         self.failUnlessEqual(d.items_sorted_by_value(),
1358                              [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1359         self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1360
1361         d = dictutil.NumDict({"a": 1, "b": 2})
1362         self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1363         self.failUnless("a" in d)
1364
1365         d2 = dictutil.NumDict({"c": 3, "d": 4})
1366         self.failUnless(d != d2)
1367         self.failUnless(d2 > d)
1368         self.failUnless(d2 >= d)
1369         self.failUnless(d <= d2)
1370         self.failUnless(d < d2)
1371         self.failUnlessEqual(d["a"], 1)
1372         self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1373         def eq(a, b):
1374             return a == b
1375         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1376
1377         d3 = d.copy()
1378         self.failUnlessEqual(d, d3)
1379         self.failUnless(isinstance(d3, dictutil.NumDict))
1380
1381         d4 = d.fromkeys(["a","b"], 5)
1382         self.failUnlessEqual(d4, {"a": 5, "b": 5})
1383
1384         self.failUnlessEqual(d.get("a"), 1)
1385         self.failUnlessEqual(d.get("c"), 0)
1386         self.failUnlessEqual(d.get("c", 5), 5)
1387         self.failUnlessEqual(sorted(list(d.items())),
1388                              [("a", 1), ("b", 2)])
1389         self.failUnlessEqual(sorted(list(d.iteritems())),
1390                              [("a", 1), ("b", 2)])
1391         self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1392         self.failUnlessEqual(sorted(d.values()), [1, 2])
1393         self.failUnless(d.has_key("a"))
1394         self.failIf(d.has_key("c"))
1395
1396         x = d.setdefault("c", 3)
1397         self.failUnlessEqual(x, 3)
1398         self.failUnlessEqual(d["c"], 3)
1399         x = d.setdefault("c", 5)
1400         self.failUnlessEqual(x, 3)
1401         self.failUnlessEqual(d["c"], 3)
1402         del d["c"]
1403
1404         x = d.popitem()
1405         self.failUnless(x in [("a", 1), ("b", 2)])
1406         x = d.popitem()
1407         self.failUnless(x in [("a", 1), ("b", 2)])
1408         self.failUnlessRaises(KeyError, d.popitem)
1409
1410         d.update({"c": 3})
1411         d.update({"c": 4, "d": 5})
1412         self.failUnlessEqual(d, {"c": 4, "d": 5})
1413
1414     def test_del_if_present(self):
1415         d = {1: "a", 2: "b"}
1416         dictutil.del_if_present(d, 1)
1417         dictutil.del_if_present(d, 3)
1418         self.failUnlessEqual(d, {2: "b"})
1419
1420     def test_valueordereddict(self):
1421         d = dictutil.ValueOrderedDict()
1422         d["a"] = 3
1423         d["b"] = 2
1424         d["c"] = 1
1425
1426         self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1427         self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1428         self.failUnlessEqual(d.values(), [1, 2, 3])
1429         self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1430         self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1431         def eq(a, b):
1432             return a == b
1433         self.failIf(d == {"a": 4})
1434         self.failUnless(d != {"a": 4})
1435
1436         x = d.setdefault("d", 0)
1437         self.failUnlessEqual(x, 0)
1438         self.failUnlessEqual(d["d"], 0)
1439         x = d.setdefault("d", -1)
1440         self.failUnlessEqual(x, 0)
1441         self.failUnlessEqual(d["d"], 0)
1442
1443         x = d.remove("e", "default", False)
1444         self.failUnlessEqual(x, "default")
1445         self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1446         x = d.remove("d", 5)
1447         self.failUnlessEqual(x, 0)
1448
1449         x = d.__getitem__("c")
1450         self.failUnlessEqual(x, 1)
1451         x = d.__getitem__("e", "default", False)
1452         self.failUnlessEqual(x, "default")
1453         self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1454
1455         self.failUnlessEqual(d.popitem(), ("c", 1))
1456         self.failUnlessEqual(d.popitem(), ("b", 2))
1457         self.failUnlessEqual(d.popitem(), ("a", 3))
1458         self.failUnlessRaises(KeyError, d.popitem)
1459
1460         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1461         x = d.pop("d", "default", False)
1462         self.failUnlessEqual(x, "default")
1463         self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1464         x = d.pop("b")
1465         self.failUnlessEqual(x, 2)
1466         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1467
1468         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1469         x = d.pop_from_list(1) # pop the second item, b/2
1470         self.failUnlessEqual(x, "b")
1471         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1472
1473     def test_auxdict(self):
1474         d = dictutil.AuxValueDict()
1475         # we put the serialized form in the auxdata
1476         d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1477
1478         self.failUnlessEqual(d.keys(), ["key"])
1479         self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1480         self.failUnlessEqual(d.get_aux("key"), "serialized")
1481         def _get_missing(key):
1482             return d[key]
1483         self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1484         self.failUnlessEqual(d.get("nonkey"), None)
1485         self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1486         self.failUnlessEqual(d.get_aux("nonkey"), None)
1487         self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1488
1489         d["key"] = ("filecap2", "metadata2")
1490         self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1491         self.failUnlessEqual(d.get_aux("key"), None)
1492
1493         d.set_with_aux("key2", "value2", "aux2")
1494         self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1495         del d["key2"]
1496         self.failUnlessEqual(d.keys(), ["key"])
1497         self.failIf("key2" in d)
1498         self.failUnlessRaises(KeyError, _get_missing, "key2")
1499         self.failUnlessEqual(d.get("key2"), None)
1500         self.failUnlessEqual(d.get_aux("key2"), None)
1501         d["key2"] = "newvalue2"
1502         self.failUnlessEqual(d.get("key2"), "newvalue2")
1503         self.failUnlessEqual(d.get_aux("key2"), None)
1504
1505         d = dictutil.AuxValueDict({1:2,3:4})
1506         self.failUnlessEqual(sorted(d.keys()), [1,3])
1507         self.failUnlessEqual(d[1], 2)
1508         self.failUnlessEqual(d.get_aux(1), None)
1509
1510         d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1511         self.failUnlessEqual(sorted(d.keys()), [1,3])
1512         self.failUnlessEqual(d[1], 2)
1513         self.failUnlessEqual(d.get_aux(1), None)
1514
1515         d = dictutil.AuxValueDict(one=1, two=2)
1516         self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1517         self.failUnlessEqual(d["one"], 1)
1518         self.failUnlessEqual(d.get_aux("one"), None)
1519
1520 class Pipeline(unittest.TestCase):
1521     def pause(self, *args, **kwargs):
1522         d = defer.Deferred()
1523         self.calls.append( (d, args, kwargs) )
1524         return d
1525
1526     def failUnlessCallsAre(self, expected):
1527         #print self.calls
1528         #print expected
1529         self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1530         for i,c in enumerate(self.calls):
1531             self.failUnlessEqual(c[1:], expected[i], str(i))
1532
1533     def test_basic(self):
1534         self.calls = []
1535         finished = []
1536         p = pipeline.Pipeline(100)
1537
1538         d = p.flush() # fires immediately
1539         d.addCallbacks(finished.append, log.err)
1540         self.failUnlessEqual(len(finished), 1)
1541         finished = []
1542
1543         d = p.add(10, self.pause, "one")
1544         # the call should start right away, and our return Deferred should
1545         # fire right away
1546         d.addCallbacks(finished.append, log.err)
1547         self.failUnlessEqual(len(finished), 1)
1548         self.failUnlessEqual(finished[0], None)
1549         self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1550         self.failUnlessEqual(p.gauge, 10)
1551
1552         # pipeline: [one]
1553
1554         finished = []
1555         d = p.add(20, self.pause, "two", kw=2)
1556         # pipeline: [one, two]
1557
1558         # the call and the Deferred should fire right away
1559         d.addCallbacks(finished.append, log.err)
1560         self.failUnlessEqual(len(finished), 1)
1561         self.failUnlessEqual(finished[0], None)
1562         self.failUnlessCallsAre([ ( ("one",) , {} ),
1563                                   ( ("two",) , {"kw": 2} ),
1564                                   ])
1565         self.failUnlessEqual(p.gauge, 30)
1566
1567         self.calls[0][0].callback("one-result")
1568         # pipeline: [two]
1569         self.failUnlessEqual(p.gauge, 20)
1570
1571         finished = []
1572         d = p.add(90, self.pause, "three", "posarg1")
1573         # pipeline: [two, three]
1574         flushed = []
1575         fd = p.flush()
1576         fd.addCallbacks(flushed.append, log.err)
1577         self.failUnlessEqual(flushed, [])
1578
1579         # the call will be made right away, but the return Deferred will not,
1580         # because the pipeline is now full.
1581         d.addCallbacks(finished.append, log.err)
1582         self.failUnlessEqual(len(finished), 0)
1583         self.failUnlessCallsAre([ ( ("one",) , {} ),
1584                                   ( ("two",) , {"kw": 2} ),
1585                                   ( ("three", "posarg1"), {} ),
1586                                   ])
1587         self.failUnlessEqual(p.gauge, 110)
1588
1589         self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1590
1591         # retiring either call will unblock the pipeline, causing the #3
1592         # Deferred to fire
1593         self.calls[2][0].callback("three-result")
1594         # pipeline: [two]
1595
1596         self.failUnlessEqual(len(finished), 1)
1597         self.failUnlessEqual(finished[0], None)
1598         self.failUnlessEqual(flushed, [])
1599
1600         # retiring call#2 will finally allow the flush() Deferred to fire
1601         self.calls[1][0].callback("two-result")
1602         self.failUnlessEqual(len(flushed), 1)
1603
1604     def test_errors(self):
1605         self.calls = []
1606         p = pipeline.Pipeline(100)
1607
1608         d1 = p.add(200, self.pause, "one")
1609         d2 = p.flush()
1610
1611         finished = []
1612         d1.addBoth(finished.append)
1613         self.failUnlessEqual(finished, [])
1614
1615         flushed = []
1616         d2.addBoth(flushed.append)
1617         self.failUnlessEqual(flushed, [])
1618
1619         self.calls[0][0].errback(ValueError("oops"))
1620
1621         self.failUnlessEqual(len(finished), 1)
1622         f = finished[0]
1623         self.failUnless(isinstance(f, Failure))
1624         self.failUnless(f.check(pipeline.PipelineError))
1625         self.failUnlessIn("PipelineError", str(f.value))
1626         self.failUnlessIn("ValueError", str(f.value))
1627         r = repr(f.value)
1628         self.failUnless("ValueError" in r, r)
1629         f2 = f.value.error
1630         self.failUnless(f2.check(ValueError))
1631
1632         self.failUnlessEqual(len(flushed), 1)
1633         f = flushed[0]
1634         self.failUnless(isinstance(f, Failure))
1635         self.failUnless(f.check(pipeline.PipelineError))
1636         f2 = f.value.error
1637         self.failUnless(f2.check(ValueError))
1638
1639         # now that the pipeline is in the failed state, any new calls will
1640         # fail immediately
1641
1642         d3 = p.add(20, self.pause, "two")
1643
1644         finished = []
1645         d3.addBoth(finished.append)
1646         self.failUnlessEqual(len(finished), 1)
1647         f = finished[0]
1648         self.failUnless(isinstance(f, Failure))
1649         self.failUnless(f.check(pipeline.PipelineError))
1650         r = repr(f.value)
1651         self.failUnless("ValueError" in r, r)
1652         f2 = f.value.error
1653         self.failUnless(f2.check(ValueError))
1654
1655         d4 = p.flush()
1656         flushed = []
1657         d4.addBoth(flushed.append)
1658         self.failUnlessEqual(len(flushed), 1)
1659         f = flushed[0]
1660         self.failUnless(isinstance(f, Failure))
1661         self.failUnless(f.check(pipeline.PipelineError))
1662         f2 = f.value.error
1663         self.failUnless(f2.check(ValueError))
1664
1665     def test_errors2(self):
1666         self.calls = []
1667         p = pipeline.Pipeline(100)
1668
1669         d1 = p.add(10, self.pause, "one")
1670         d2 = p.add(20, self.pause, "two")
1671         d3 = p.add(30, self.pause, "three")
1672         d4 = p.flush()
1673
1674         # one call fails, then the second one succeeds: make sure
1675         # ExpandableDeferredList tolerates the second one
1676
1677         flushed = []
1678         d4.addBoth(flushed.append)
1679         self.failUnlessEqual(flushed, [])
1680
1681         self.calls[0][0].errback(ValueError("oops"))
1682         self.failUnlessEqual(len(flushed), 1)
1683         f = flushed[0]
1684         self.failUnless(isinstance(f, Failure))
1685         self.failUnless(f.check(pipeline.PipelineError))
1686         f2 = f.value.error
1687         self.failUnless(f2.check(ValueError))
1688
1689         self.calls[1][0].callback("two-result")
1690         self.calls[2][0].errback(ValueError("three-error"))
1691
1692         del d1,d2,d3,d4
1693
1694 class SampleError(Exception):
1695     pass
1696
1697 class Log(unittest.TestCase):
1698     def test_err(self):
1699         if not hasattr(self, "flushLoggedErrors"):
1700             # without flushLoggedErrors, we can't get rid of the
1701             # twisted.log.err that tahoe_log records, so we can't keep this
1702             # test from [ERROR]ing
1703             raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1704         try:
1705             raise SampleError("simple sample")
1706         except:
1707             f = Failure()
1708         tahoe_log.err(format="intentional sample error",
1709                       failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1710         self.flushLoggedErrors(SampleError)
1711
1712
1713 class SimpleSpans:
1714     # this is a simple+inefficient form of util.spans.Spans . We compare the
1715     # behavior of this reference model against the real (efficient) form.
1716
1717     def __init__(self, _span_or_start=None, length=None):
1718         self._have = set()
1719         if length is not None:
1720             for i in range(_span_or_start, _span_or_start+length):
1721                 self._have.add(i)
1722         elif _span_or_start:
1723             for (start,length) in _span_or_start:
1724                 self.add(start, length)
1725
1726     def add(self, start, length):
1727         for i in range(start, start+length):
1728             self._have.add(i)
1729         return self
1730
1731     def remove(self, start, length):
1732         for i in range(start, start+length):
1733             self._have.discard(i)
1734         return self
1735
1736     def each(self):
1737         return sorted(self._have)
1738
1739     def __iter__(self):
1740         items = sorted(self._have)
1741         prevstart = None
1742         prevend = None
1743         for i in items:
1744             if prevstart is None:
1745                 prevstart = prevend = i
1746                 continue
1747             if i == prevend+1:
1748                 prevend = i
1749                 continue
1750             yield (prevstart, prevend-prevstart+1)
1751             prevstart = prevend = i
1752         if prevstart is not None:
1753             yield (prevstart, prevend-prevstart+1)
1754
1755     def __nonzero__(self): # this gets us bool()
1756         return self.len()
1757
1758     def len(self):
1759         return len(self._have)
1760
1761     def __add__(self, other):
1762         s = self.__class__(self)
1763         for (start, length) in other:
1764             s.add(start, length)
1765         return s
1766
1767     def __sub__(self, other):
1768         s = self.__class__(self)
1769         for (start, length) in other:
1770             s.remove(start, length)
1771         return s
1772
1773     def __iadd__(self, other):
1774         for (start, length) in other:
1775             self.add(start, length)
1776         return self
1777
1778     def __isub__(self, other):
1779         for (start, length) in other:
1780             self.remove(start, length)
1781         return self
1782
1783     def __and__(self, other):
1784         s = self.__class__()
1785         for i in other.each():
1786             if i in self._have:
1787                 s.add(i, 1)
1788         return s
1789
1790     def __contains__(self, (start,length)):
1791         for i in range(start, start+length):
1792             if i not in self._have:
1793                 return False
1794         return True
1795
1796 class ByteSpans(unittest.TestCase):
1797     def test_basic(self):
1798         s = Spans()
1799         self.failUnlessEqual(list(s), [])
1800         self.failIf(s)
1801         self.failIf((0,1) in s)
1802         self.failUnlessEqual(s.len(), 0)
1803
1804         s1 = Spans(3, 4) # 3,4,5,6
1805         self._check1(s1)
1806
1807         s1 = Spans(3L, 4L) # 3,4,5,6
1808         self._check1(s1)
1809
1810         s2 = Spans(s1)
1811         self._check1(s2)
1812
1813         s2.add(10,2) # 10,11
1814         self._check1(s1)
1815         self.failUnless((10,1) in s2)
1816         self.failIf((10,1) in s1)
1817         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1818         self.failUnlessEqual(s2.len(), 6)
1819
1820         s2.add(15,2).add(20,2)
1821         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1822         self.failUnlessEqual(s2.len(), 10)
1823
1824         s2.remove(4,3).remove(15,1)
1825         self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1826         self.failUnlessEqual(s2.len(), 6)
1827
1828         s1 = SimpleSpans(3, 4) # 3 4 5 6
1829         s2 = SimpleSpans(5, 4) # 5 6 7 8
1830         i = s1 & s2
1831         self.failUnlessEqual(list(i.each()), [5, 6])
1832
1833     def _check1(self, s):
1834         self.failUnlessEqual(list(s), [(3,4)])
1835         self.failUnless(s)
1836         self.failUnlessEqual(s.len(), 4)
1837         self.failIf((0,1) in s)
1838         self.failUnless((3,4) in s)
1839         self.failUnless((3,1) in s)
1840         self.failUnless((5,2) in s)
1841         self.failUnless((6,1) in s)
1842         self.failIf((6,2) in s)
1843         self.failIf((7,1) in s)
1844         self.failUnlessEqual(list(s.each()), [3,4,5,6])
1845
1846     def test_large(self):
1847         s = Spans(4, 2**65) # don't do this with a SimpleSpans
1848         self.failUnlessEqual(list(s), [(4, 2**65)])
1849         self.failUnless(s)
1850         self.failUnlessEqual(s.len(), 2**65)
1851         self.failIf((0,1) in s)
1852         self.failUnless((4,2) in s)
1853         self.failUnless((2**65,2) in s)
1854
1855     def test_math(self):
1856         s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1857         s2 = Spans(5, 3) # 5,6,7
1858         s3 = Spans(8, 4) # 8,9,10,11
1859
1860         s = s1 - s2
1861         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1862         s = s1 - s3
1863         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1864         s = s2 - s3
1865         self.failUnlessEqual(list(s.each()), [5,6,7])
1866         s = s1 & s2
1867         self.failUnlessEqual(list(s.each()), [5,6,7])
1868         s = s2 & s1
1869         self.failUnlessEqual(list(s.each()), [5,6,7])
1870         s = s1 & s3
1871         self.failUnlessEqual(list(s.each()), [8,9])
1872         s = s3 & s1
1873         self.failUnlessEqual(list(s.each()), [8,9])
1874         s = s2 & s3
1875         self.failUnlessEqual(list(s.each()), [])
1876         s = s3 & s2
1877         self.failUnlessEqual(list(s.each()), [])
1878         s = Spans() & s3
1879         self.failUnlessEqual(list(s.each()), [])
1880         s = s3 & Spans()
1881         self.failUnlessEqual(list(s.each()), [])
1882
1883         s = s1 + s2
1884         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1885         s = s1 + s3
1886         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1887         s = s2 + s3
1888         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1889
1890         s = Spans(s1)
1891         s -= s2
1892         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1893         s = Spans(s1)
1894         s -= s3
1895         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1896         s = Spans(s2)
1897         s -= s3
1898         self.failUnlessEqual(list(s.each()), [5,6,7])
1899
1900         s = Spans(s1)
1901         s += s2
1902         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1903         s = Spans(s1)
1904         s += s3
1905         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1906         s = Spans(s2)
1907         s += s3
1908         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1909
1910     def test_random(self):
1911         # attempt to increase coverage of corner cases by comparing behavior
1912         # of a simple-but-slow model implementation against the
1913         # complex-but-fast actual implementation, in a large number of random
1914         # operations
1915         S1 = SimpleSpans
1916         S2 = Spans
1917         s1 = S1(); s2 = S2()
1918         seed = ""
1919         def _create(subseed):
1920             ns1 = S1(); ns2 = S2()
1921             for i in range(10):
1922                 what = _hash(subseed+str(i)).hexdigest()
1923                 start = int(what[2:4], 16)
1924                 length = max(1,int(what[5:6], 16))
1925                 ns1.add(start, length); ns2.add(start, length)
1926             return ns1, ns2
1927
1928         #print
1929         for i in range(1000):
1930             what = _hash(seed+str(i)).hexdigest()
1931             op = what[0]
1932             subop = what[1]
1933             start = int(what[2:4], 16)
1934             length = max(1,int(what[5:6], 16))
1935             #print what
1936             if op in "0":
1937                 if subop in "01234":
1938                     s1 = S1(); s2 = S2()
1939                 elif subop in "5678":
1940                     s1 = S1(start, length); s2 = S2(start, length)
1941                 else:
1942                     s1 = S1(s1); s2 = S2(s2)
1943                 #print "s2 = %s" % s2.dump()
1944             elif op in "123":
1945                 #print "s2.add(%d,%d)" % (start, length)
1946                 s1.add(start, length); s2.add(start, length)
1947             elif op in "456":
1948                 #print "s2.remove(%d,%d)" % (start, length)
1949                 s1.remove(start, length); s2.remove(start, length)
1950             elif op in "78":
1951                 ns1, ns2 = _create(what[7:11])
1952                 #print "s2 + %s" % ns2.dump()
1953                 s1 = s1 + ns1; s2 = s2 + ns2
1954             elif op in "9a":
1955                 ns1, ns2 = _create(what[7:11])
1956                 #print "%s - %s" % (s2.dump(), ns2.dump())
1957                 s1 = s1 - ns1; s2 = s2 - ns2
1958             elif op in "bc":
1959                 ns1, ns2 = _create(what[7:11])
1960                 #print "s2 += %s" % ns2.dump()
1961                 s1 += ns1; s2 += ns2
1962             elif op in "de":
1963                 ns1, ns2 = _create(what[7:11])
1964                 #print "%s -= %s" % (s2.dump(), ns2.dump())
1965                 s1 -= ns1; s2 -= ns2
1966             else:
1967                 ns1, ns2 = _create(what[7:11])
1968                 #print "%s &= %s" % (s2.dump(), ns2.dump())
1969                 s1 = s1 & ns1; s2 = s2 & ns2
1970             #print "s2 now %s" % s2.dump()
1971             self.failUnlessEqual(list(s1.each()), list(s2.each()))
1972             self.failUnlessEqual(s1.len(), s2.len())
1973             self.failUnlessEqual(bool(s1), bool(s2))
1974             self.failUnlessEqual(list(s1), list(s2))
1975             for j in range(10):
1976                 what = _hash(what[12:14]+str(j)).hexdigest()
1977                 start = int(what[2:4], 16)
1978                 length = max(1, int(what[5:6], 16))
1979                 span = (start, length)
1980                 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1981
1982
1983     # s()
1984     # s(start,length)
1985     # s(s0)
1986     # s.add(start,length) : returns s
1987     # s.remove(start,length)
1988     # s.each() -> list of byte offsets, mostly for testing
1989     # list(s) -> list of (start,length) tuples, one per span
1990     # (start,length) in s -> True if (start..start+length-1) are all members
1991     #  NOT equivalent to x in list(s)
1992     # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
1993     # bool(s)  (__nonzeron__)
1994     # s = s1+s2, s1-s2, +=s1, -=s1
1995
1996     def test_overlap(self):
1997         for a in range(20):
1998             for b in range(10):
1999                 for c in range(20):
2000                     for d in range(10):
2001                         self._test_overlap(a,b,c,d)
2002
2003     def _test_overlap(self, a, b, c, d):
2004         s1 = set(range(a,a+b))
2005         s2 = set(range(c,c+d))
2006         #print "---"
2007         #self._show_overlap(s1, "1")
2008         #self._show_overlap(s2, "2")
2009         o = overlap(a,b,c,d)
2010         expected = s1.intersection(s2)
2011         if not expected:
2012             self.failUnlessEqual(o, None)
2013         else:
2014             start,length = o
2015             so = set(range(start,start+length))
2016             #self._show(so, "o")
2017             self.failUnlessEqual(so, expected)
2018
2019     def _show_overlap(self, s, c):
2020         import sys
2021         out = sys.stdout
2022         if s:
2023             for i in range(max(s)):
2024                 if i in s:
2025                     out.write(c)
2026                 else:
2027                     out.write(" ")
2028         out.write("\n")
2029
2030 def extend(s, start, length, fill):
2031     if len(s) >= start+length:
2032         return s
2033     assert len(fill) == 1
2034     return s + fill*(start+length-len(s))
2035
2036 def replace(s, start, data):
2037     assert len(s) >= start+len(data)
2038     return s[:start] + data + s[start+len(data):]
2039
2040 class SimpleDataSpans:
2041     def __init__(self, other=None):
2042         self.missing = "" # "1" where missing, "0" where found
2043         self.data = ""
2044         if other:
2045             for (start, data) in other.get_chunks():
2046                 self.add(start, data)
2047
2048     def __nonzero__(self): # this gets us bool()
2049         return self.len()
2050     def len(self):
2051         return len(self.missing.replace("1", ""))
2052     def _dump(self):
2053         return [i for (i,c) in enumerate(self.missing) if c == "0"]
2054     def _have(self, start, length):
2055         m = self.missing[start:start+length]
2056         if not m or len(m)<length or int(m):
2057             return False
2058         return True
2059     def get_chunks(self):
2060         for i in self._dump():
2061             yield (i, self.data[i])
2062     def get_spans(self):
2063         return SimpleSpans([(start,len(data))
2064                             for (start,data) in self.get_chunks()])
2065     def get(self, start, length):
2066         if self._have(start, length):
2067             return self.data[start:start+length]
2068         return None
2069     def pop(self, start, length):
2070         data = self.get(start, length)
2071         if data:
2072             self.remove(start, length)
2073         return data
2074     def remove(self, start, length):
2075         self.missing = replace(extend(self.missing, start, length, "1"),
2076                                start, "1"*length)
2077     def add(self, start, data):
2078         self.missing = replace(extend(self.missing, start, len(data), "1"),
2079                                start, "0"*len(data))
2080         self.data = replace(extend(self.data, start, len(data), " "),
2081                             start, data)
2082
2083
2084 class StringSpans(unittest.TestCase):
2085     def do_basic(self, klass):
2086         ds = klass()
2087         self.failUnlessEqual(ds.len(), 0)
2088         self.failUnlessEqual(list(ds._dump()), [])
2089         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
2090         s1 = ds.get_spans()
2091         self.failUnlessEqual(ds.get(0, 4), None)
2092         self.failUnlessEqual(ds.pop(0, 4), None)
2093         ds.remove(0, 4)
2094
2095         ds.add(2, "four")
2096         self.failUnlessEqual(ds.len(), 4)
2097         self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
2098         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2099         s1 = ds.get_spans()
2100         self.failUnless((2,2) in s1)
2101         self.failUnlessEqual(ds.get(0, 4), None)
2102         self.failUnlessEqual(ds.pop(0, 4), None)
2103         self.failUnlessEqual(ds.get(4, 4), None)
2104
2105         ds2 = klass(ds)
2106         self.failUnlessEqual(ds2.len(), 4)
2107         self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2108         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2109         self.failUnlessEqual(ds2.get(0, 4), None)
2110         self.failUnlessEqual(ds2.pop(0, 4), None)
2111         self.failUnlessEqual(ds2.pop(2, 3), "fou")
2112         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2113         self.failUnlessEqual(ds2.get(2, 3), None)
2114         self.failUnlessEqual(ds2.get(5, 1), "r")
2115         self.failUnlessEqual(ds.get(2, 3), "fou")
2116         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2117
2118         ds.add(0, "23")
2119         self.failUnlessEqual(ds.len(), 6)
2120         self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2121         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2122         self.failUnlessEqual(ds.get(0, 4), "23fo")
2123         self.failUnlessEqual(ds.pop(0, 4), "23fo")
2124         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2125         self.failUnlessEqual(ds.get(0, 4), None)
2126         self.failUnlessEqual(ds.pop(0, 4), None)
2127
2128         ds = klass()
2129         ds.add(2, "four")
2130         ds.add(3, "ea")
2131         self.failUnlessEqual(ds.get(2, 4), "fear")
2132
2133         ds = klass()
2134         ds.add(2L, "four")
2135         ds.add(3L, "ea")
2136         self.failUnlessEqual(ds.get(2L, 4L), "fear")
2137
2138
2139     def do_scan(self, klass):
2140         # do a test with gaps and spans of size 1 and 2
2141         #  left=(1,11) * right=(1,11) * gapsize=(1,2)
2142         # 111, 112, 121, 122, 211, 212, 221, 222
2143         #    211
2144         #      121
2145         #         112
2146         #            212
2147         #               222
2148         #                   221
2149         #                      111
2150         #                        122
2151         #  11 1  1 11 11  11  1 1  111
2152         # 0123456789012345678901234567
2153         # abcdefghijklmnopqrstuvwxyz-=
2154         pieces = [(1, "bc"),
2155                   (4, "e"),
2156                   (7, "h"),
2157                   (9, "jk"),
2158                   (12, "mn"),
2159                   (16, "qr"),
2160                   (20, "u"),
2161                   (22, "w"),
2162                   (25, "z-="),
2163                   ]
2164         p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2165         S = "abcdefghijklmnopqrstuvwxyz-="
2166         # TODO: when adding data, add capital letters, to make sure we aren't
2167         # just leaving the old data in place
2168         l = len(S)
2169         def base():
2170             ds = klass()
2171             for start, data in pieces:
2172                 ds.add(start, data)
2173             return ds
2174         def dump(s):
2175             p = set(s._dump())
2176             d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2177             assert len(d) == l
2178             return d
2179         DEBUG = False
2180         for start in range(0, l):
2181             for end in range(start+1, l):
2182                 # add [start-end) to the baseline
2183                 which = "%d-%d" % (start, end-1)
2184                 p_added = set(range(start, end))
2185                 b = base()
2186                 if DEBUG:
2187                     print
2188                     print dump(b), which
2189                     add = klass(); add.add(start, S[start:end])
2190                     print dump(add)
2191                 b.add(start, S[start:end])
2192                 if DEBUG:
2193                     print dump(b)
2194                 # check that the new span is there
2195                 d = b.get(start, end-start)
2196                 self.failUnlessEqual(d, S[start:end], which)
2197                 # check that all the original pieces are still there
2198                 for t_start, t_data in pieces:
2199                     t_len = len(t_data)
2200                     self.failUnlessEqual(b.get(t_start, t_len),
2201                                          S[t_start:t_start+t_len],
2202                                          "%s %d+%d" % (which, t_start, t_len))
2203                 # check that a lot of subspans are mostly correct
2204                 for t_start in range(l):
2205                     for t_len in range(1,4):
2206                         d = b.get(t_start, t_len)
2207                         if d is not None:
2208                             which2 = "%s+(%d-%d)" % (which, t_start,
2209                                                      t_start+t_len-1)
2210                             self.failUnlessEqual(d, S[t_start:t_start+t_len],
2211                                                  which2)
2212                         # check that removing a subspan gives the right value
2213                         b2 = klass(b)
2214                         b2.remove(t_start, t_len)
2215                         removed = set(range(t_start, t_start+t_len))
2216                         for i in range(l):
2217                             exp = (((i in p_elements) or (i in p_added))
2218                                    and (i not in removed))
2219                             which2 = "%s-(%d-%d)" % (which, t_start,
2220                                                      t_start+t_len-1)
2221                             self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2222                                                  which2+" %d" % i)
2223
2224     def test_test(self):
2225         self.do_basic(SimpleDataSpans)
2226         self.do_scan(SimpleDataSpans)
2227
2228     def test_basic(self):
2229         self.do_basic(DataSpans)
2230         self.do_scan(DataSpans)
2231
2232     def test_random(self):
2233         # attempt to increase coverage of corner cases by comparing behavior
2234         # of a simple-but-slow model implementation against the
2235         # complex-but-fast actual implementation, in a large number of random
2236         # operations
2237         S1 = SimpleDataSpans
2238         S2 = DataSpans
2239         s1 = S1(); s2 = S2()
2240         seed = ""
2241         def _randstr(length, seed):
2242             created = 0
2243             pieces = []
2244             while created < length:
2245                 piece = _hash(seed + str(created)).hexdigest()
2246                 pieces.append(piece)
2247                 created += len(piece)
2248             return "".join(pieces)[:length]
2249         def _create(subseed):
2250             ns1 = S1(); ns2 = S2()
2251             for i in range(10):
2252                 what = _hash(subseed+str(i)).hexdigest()
2253                 start = int(what[2:4], 16)
2254                 length = max(1,int(what[5:6], 16))
2255                 ns1.add(start, _randstr(length, what[7:9]));
2256                 ns2.add(start, _randstr(length, what[7:9]))
2257             return ns1, ns2
2258
2259         #print
2260         for i in range(1000):
2261             what = _hash(seed+str(i)).hexdigest()
2262             op = what[0]
2263             subop = what[1]
2264             start = int(what[2:4], 16)
2265             length = max(1,int(what[5:6], 16))
2266             #print what
2267             if op in "0":
2268                 if subop in "0123456":
2269                     s1 = S1(); s2 = S2()
2270                 else:
2271                     s1, s2 = _create(what[7:11])
2272                 #print "s2 = %s" % list(s2._dump())
2273             elif op in "123456":
2274                 #print "s2.add(%d,%d)" % (start, length)
2275                 s1.add(start, _randstr(length, what[7:9]));
2276                 s2.add(start, _randstr(length, what[7:9]))
2277             elif op in "789abc":
2278                 #print "s2.remove(%d,%d)" % (start, length)
2279                 s1.remove(start, length); s2.remove(start, length)
2280             else:
2281                 #print "s2.pop(%d,%d)" % (start, length)
2282                 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2283                 self.failUnlessEqual(d1, d2)
2284             #print "s1 now %s" % list(s1._dump())
2285             #print "s2 now %s" % list(s2._dump())
2286             self.failUnlessEqual(s1.len(), s2.len())
2287             self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2288             for j in range(100):
2289                 what = _hash(what[12:14]+str(j)).hexdigest()
2290                 start = int(what[2:4], 16)
2291                 length = max(1, int(what[5:6], 16))
2292                 d1 = s1.get(start, length); d2 = s2.get(start, length)
2293                 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))