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