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