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