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