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_rename_no_overwrite(self):
 445         workdir = fileutil.abspath_expanduser_unicode(u"test_rename_no_overwrite")
 446         fileutil.make_dirs(workdir)
 447
 448         source_path = os.path.join(workdir, "source")
 449         dest_path   = os.path.join(workdir, "dest")
 450
 451         # when neither file exists
 452         self.failUnlessRaises(OSError, fileutil.rename_no_overwrite, source_path, dest_path)
 453
 454         # when only dest exists
 455         fileutil.write(dest_path,   "dest")
 456         self.failUnlessRaises(OSError, fileutil.rename_no_overwrite, source_path, dest_path)
 457         self.failUnlessEqual(fileutil.read(dest_path),   "dest")
 458
 459         # when both exist
 460         fileutil.write(source_path, "source")
 461         self.failUnlessRaises(OSError, fileutil.rename_no_overwrite, source_path, dest_path)
 462         self.failUnlessEqual(fileutil.read(source_path), "source")
 463         self.failUnlessEqual(fileutil.read(dest_path),   "dest")
 464
 465         # when only source exists
 466         os.remove(dest_path)
 467         fileutil.rename_no_overwrite(source_path, dest_path)
 468         self.failUnlessEqual(fileutil.read(dest_path), "source")
 469         self.failIf(os.path.exists(source_path))
 470
 471     def test_replace_file(self):
 472         workdir = fileutil.abspath_expanduser_unicode(u"test_replace_file")
 473         fileutil.make_dirs(workdir)
 474
 475         backup_path      = os.path.join(workdir, "backup")
 476         replaced_path    = os.path.join(workdir, "replaced")
 477         replacement_path = os.path.join(workdir, "replacement")
 478
 479         # when none of the files exist
 480         self.failUnlessRaises(fileutil.ConflictError, fileutil.replace_file, replaced_path, replacement_path, backup_path)
 481
 482         # when only replaced exists
 483         fileutil.write(replaced_path,    "foo")
 484         self.failUnlessRaises(fileutil.ConflictError, fileutil.replace_file, replaced_path, replacement_path, backup_path)
 485         self.failUnlessEqual(fileutil.read(replaced_path), "foo")
 486
 487         # when both replaced and replacement exist, but not backup
 488         fileutil.write(replacement_path, "bar")
 489         fileutil.replace_file(replaced_path, replacement_path, backup_path)
 490         self.failUnlessEqual(fileutil.read(backup_path),   "foo")
 491         self.failUnlessEqual(fileutil.read(replaced_path), "bar")
 492         self.failIf(os.path.exists(replacement_path))
 493
 494         # when only replacement exists
 495         os.remove(backup_path)
 496         os.remove(replaced_path)
 497         fileutil.write(replacement_path, "bar")
 498         fileutil.replace_file(replaced_path, replacement_path, backup_path)
 499         self.failUnlessEqual(fileutil.read(replaced_path), "bar")
 500         self.failIf(os.path.exists(replacement_path))
 501         self.failIf(os.path.exists(backup_path))
 502
 503         # when replaced, replacement and backup all exist
 504         fileutil.write(replaced_path,    "foo")
 505         fileutil.write(replacement_path, "bar")
 506         fileutil.write(backup_path,      "bak")
 507         fileutil.replace_file(replaced_path, replacement_path, backup_path)
 508         self.failUnlessEqual(fileutil.read(backup_path),   "foo")
 509         self.failUnlessEqual(fileutil.read(replaced_path), "bar")
 510         self.failIf(os.path.exists(replacement_path))
 511
 512     def test_du(self):
 513         basedir = "util/FileUtil/test_du"
 514         fileutil.make_dirs(basedir)
 515         d = os.path.join(basedir, "space-consuming")
 516         self.mkdir(d, "a/b")
 517         self.touch(d, "a/b/1.txt", data="a"*10)
 518         self.touch(d, "a/b/2.txt", data="b"*11)
 519         self.mkdir(d, "a/c")
 520         self.touch(d, "a/c/1.txt", data="c"*12)
 521         self.touch(d, "a/c/2.txt", data="d"*13)
 522
 523         used = fileutil.du(basedir)
 524         self.failUnlessEqual(10+11+12+13, used)
 525
 526     def test_abspath_expanduser_unicode(self):
 527         self.failUnlessRaises(AssertionError, fileutil.abspath_expanduser_unicode, "bytestring")
 528
 529         saved_cwd = os.path.normpath(os.getcwdu())
 530         abspath_cwd = fileutil.abspath_expanduser_unicode(u".")
 531         self.failUnless(isinstance(saved_cwd, unicode), saved_cwd)
 532         self.failUnless(isinstance(abspath_cwd, unicode), abspath_cwd)
 533         if sys.platform == "win32":
 534             self.failUnlessReallyEqual(abspath_cwd, fileutil.to_windows_long_path(saved_cwd))
 535         else:
 536             self.failUnlessReallyEqual(abspath_cwd, saved_cwd)
 537
 538         self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\?\\foo"), u"\\\\?\\foo")
 539         self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\.\\foo"), u"\\\\.\\foo")
 540         self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"\\\\server\\foo"), u"\\\\?\\UNC\\server\\foo")
 541         self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo"), u"\\\\?\\C:\\foo")
 542         self.failUnlessReallyEqual(fileutil.to_windows_long_path(u"C:\\foo/bar"), u"\\\\?\\C:\\foo\\bar")
 543
 544         # adapted from <http://svn.python.org/view/python/branches/release26-maint/Lib/test/test_posixpath.py?view=markup&pathrev=78279#test_abspath>
 545
 546         foo = fileutil.abspath_expanduser_unicode(u"foo")
 547         self.failUnless(foo.endswith(u"%sfoo" % (os.path.sep,)), foo)
 548
 549         foobar = fileutil.abspath_expanduser_unicode(u"bar", base=foo)
 550         self.failUnless(foobar.endswith(u"%sfoo%sbar" % (os.path.sep, os.path.sep)), foobar)
 551
 552         if sys.platform == "win32":
 553             # This is checking that a drive letter is added for a path without one.
 554             baz = fileutil.abspath_expanduser_unicode(u"\\baz")
 555             self.failUnless(baz.startswith(u"\\\\?\\"), baz)
 556             self.failUnlessReallyEqual(baz[5 :], u":\\baz")
 557
 558             bar = fileutil.abspath_expanduser_unicode(u"\\bar", base=baz)
 559             self.failUnless(bar.startswith(u"\\\\?\\"), bar)
 560             self.failUnlessReallyEqual(bar[5 :], u":\\bar")
 561             # not u":\\baz\\bar", because \bar is absolute on the current drive.
 562
 563             self.failUnlessReallyEqual(baz[4], bar[4])  # same drive
 564
 565         self.failIfIn(u"~", fileutil.abspath_expanduser_unicode(u"~"))
 566
 567         cwds = ['cwd']
 568         try:
 569             cwds.append(u'\xe7w\xf0'.encode(sys.getfilesystemencoding()
 570                                             or 'ascii'))
 571         except UnicodeEncodeError:
 572             pass # the cwd can't be encoded -- test with ascii cwd only
 573
 574         for cwd in cwds:
 575             try:
 576                 os.mkdir(cwd)
 577                 os.chdir(cwd)
 578                 for upath in (u'', u'fuu', u'f\xf9\xf9', u'/fuu', u'U:\\', u'~'):
 579                     uabspath = fileutil.abspath_expanduser_unicode(upath)
 580                     self.failUnless(isinstance(uabspath, unicode), uabspath)
 581             finally:
 582                 os.chdir(saved_cwd)
 583
 584     def test_create_long_path(self):
 585         workdir = u"test_create_long_path"
 586         fileutil.make_dirs(workdir)
 587         long_path = fileutil.abspath_expanduser_unicode(os.path.join(workdir, u'x'*255))
 588         def _cleanup():
 589             fileutil.remove(long_path)
 590         self.addCleanup(_cleanup)
 591
 592         fileutil.write(long_path, "test")
 593         self.failUnless(os.path.exists(long_path))
 594         self.failUnlessEqual(fileutil.read(long_path), "test")
 595         _cleanup()
 596         self.failIf(os.path.exists(long_path))
 597
 598     def _test_windows_expanduser(self, userprofile=None, homedrive=None, homepath=None):
 599         def call_windows_getenv(name):
 600             if name == u"USERPROFILE": return userprofile
 601             if name == u"HOMEDRIVE":   return homedrive
 602             if name == u"HOMEPATH":    return homepath
 603             self.fail("unexpected argument to call_windows_getenv")
 604         self.patch(fileutil, 'windows_getenv', call_windows_getenv)
 605
 606         self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
 607         self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~\\foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
 608         self.failUnlessReallyEqual(fileutil.windows_expanduser(u"~/foo"), os.path.join(u"C:", u"\\Documents and Settings\\\u0100", u"foo"))
 609         self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a"), u"a")
 610         self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a~"), u"a~")
 611         self.failUnlessReallyEqual(fileutil.windows_expanduser(u"a\\~\\foo"), u"a\\~\\foo")
 612
 613     def test_windows_expanduser_xp(self):
 614         return self._test_windows_expanduser(homedrive=u"C:", homepath=u"\\Documents and Settings\\\u0100")
 615
 616     def test_windows_expanduser_win7(self):
 617         return self._test_windows_expanduser(userprofile=os.path.join(u"C:", u"\\Documents and Settings\\\u0100"))
 618
 619     def test_disk_stats(self):
 620         avail = fileutil.get_available_space('.', 2**14)
 621         if avail == 0:
 622             raise unittest.SkipTest("This test will spuriously fail there is no disk space left.")
 623
 624         disk = fileutil.get_disk_stats('.', 2**13)
 625         self.failUnless(disk['total'] > 0, disk['total'])
 626         # we tolerate used==0 for a Travis-CI bug, see #2290
 627         self.failUnless(disk['used'] >= 0, disk['used'])
 628         self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
 629         self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
 630         self.failUnless(disk['avail'] > 0, disk['avail'])
 631
 632     def test_disk_stats_avail_nonnegative(self):
 633         # This test will spuriously fail if you have more than 2^128
 634         # bytes of available space on your filesystem.
 635         disk = fileutil.get_disk_stats('.', 2**128)
 636         self.failUnlessEqual(disk['avail'], 0)
 637
 638     def test_get_pathinfo(self):
 639         basedir = "util/FileUtil/test_get_pathinfo"
 640         fileutil.make_dirs(basedir)
 641
 642         # create a directory
 643         self.mkdir(basedir, "a")
 644         dirinfo = fileutil.get_pathinfo(basedir)
 645         self.failUnlessTrue(dirinfo.isdir)
 646         self.failUnlessTrue(dirinfo.exists)
 647         self.failUnlessFalse(dirinfo.isfile)
 648         self.failUnlessFalse(dirinfo.islink)
 649
 650         # create a file under the directory
 651         f = os.path.join(basedir, "a", "1.txt")
 652         self.touch(basedir, "a/1.txt", data="a"*10)
 653         fileinfo = fileutil.get_pathinfo(f)
 654         self.failUnlessTrue(fileinfo.isfile)
 655         self.failUnlessTrue(fileinfo.exists)
 656         self.failUnlessFalse(fileinfo.isdir)
 657         self.failUnlessFalse(fileinfo.islink)
 658         self.failUnlessEqual(fileinfo.size, 10)
 659
 660         # create a symlink under the directory a pointing to 1.txt
 661         slname = os.path.join(basedir, "a", "linkto1.txt")
 662         os.symlink(f, slname)
 663         symlinkinfo = fileutil.get_pathinfo(slname)
 664         self.failUnlessTrue(symlinkinfo.islink)
 665         self.failUnlessTrue(symlinkinfo.exists)
 666         self.failUnlessFalse(symlinkinfo.isfile)
 667         self.failUnlessFalse(symlinkinfo.isdir)
 668
 669         # path at which nothing exists
 670         dnename = os.path.join(basedir, "a", "doesnotexist")
 671         now = time.time()
 672         dneinfo = fileutil.get_pathinfo(dnename, now=now)
 673         self.failUnlessFalse(dneinfo.exists)
 674         self.failUnlessFalse(dneinfo.isfile)
 675         self.failUnlessFalse(dneinfo.isdir)
 676         self.failUnlessFalse(dneinfo.islink)
 677         self.failUnlessEqual(dneinfo.size, None)
 678         self.failUnlessEqual(dneinfo.mtime, now)
 679         self.failUnlessEqual(dneinfo.ctime, now)
 680
 681
 682 class PollMixinTests(unittest.TestCase):
 683     def setUp(self):
 684         self.pm = pollmixin.PollMixin()
 685
 686     def test_PollMixin_True(self):
 687         d = self.pm.poll(check_f=lambda : True,
 688                          pollinterval=0.1)
 689         return d
 690
 691     def test_PollMixin_False_then_True(self):
 692         i = iter([False, True])
 693         d = self.pm.poll(check_f=i.next,
 694                          pollinterval=0.1)
 695         return d
 696
 697     def test_timeout(self):
 698         d = self.pm.poll(check_f=lambda: False,
 699                          pollinterval=0.01,
 700                          timeout=1)
 701         def _suc(res):
 702             self.fail("poll should have failed, not returned %s" % (res,))
 703         def _err(f):
 704             f.trap(pollmixin.TimeoutError)
 705             return None # success
 706         d.addCallbacks(_suc, _err)
 707         return d
 708
 709 class DeferredUtilTests(unittest.TestCase, deferredutil.WaitForDelayedCallsMixin):
 710     def test_gather_results(self):
 711         d1 = defer.Deferred()
 712         d2 = defer.Deferred()
 713         res = deferredutil.gatherResults([d1, d2])
 714         d1.errback(ValueError("BAD"))
 715         def _callb(res):
 716             self.fail("Should have errbacked, not resulted in %s" % (res,))
 717         def _errb(thef):
 718             thef.trap(ValueError)
 719         res.addCallbacks(_callb, _errb)
 720         return res
 721
 722     def test_success(self):
 723         d1, d2 = defer.Deferred(), defer.Deferred()
 724         good = []
 725         bad = []
 726         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 727         dlss.addCallbacks(good.append, bad.append)
 728         d1.callback(1)
 729         d2.callback(2)
 730         self.failUnlessEqual(good, [[1,2]])
 731         self.failUnlessEqual(bad, [])
 732
 733     def test_failure(self):
 734         d1, d2 = defer.Deferred(), defer.Deferred()
 735         good = []
 736         bad = []
 737         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 738         dlss.addCallbacks(good.append, bad.append)
 739         d1.addErrback(lambda _ignore: None)
 740         d2.addErrback(lambda _ignore: None)
 741         d1.callback(1)
 742         d2.errback(ValueError())
 743         self.failUnlessEqual(good, [])
 744         self.failUnlessEqual(len(bad), 1)
 745         f = bad[0]
 746         self.failUnless(isinstance(f, Failure))
 747         self.failUnless(f.check(ValueError))
 748
 749     def test_wait_for_delayed_calls(self):
 750         """
 751         This tests that 'wait_for_delayed_calls' does in fact wait for a
 752         delayed call that is active when the test returns. If it didn't,
 753         Trial would report an unclean reactor error for this test.
 754         """
 755         def _trigger():
 756             #print "trigger"
 757             pass
 758         reactor.callLater(0.1, _trigger)
 759
 760         d = defer.succeed(None)
 761         d.addBoth(self.wait_for_delayed_calls)
 762         return d
 763
 764 class HashUtilTests(unittest.TestCase):
 765
 766     def test_random_key(self):
 767         k = hashutil.random_key()
 768         self.failUnlessEqual(len(k), hashutil.KEYLEN)
 769
 770     def test_sha256d(self):
 771         h1 = hashutil.tagged_hash("tag1", "value")
 772         h2 = hashutil.tagged_hasher("tag1")
 773         h2.update("value")
 774         h2a = h2.digest()
 775         h2b = h2.digest()
 776         self.failUnlessEqual(h1, h2a)
 777         self.failUnlessEqual(h2a, h2b)
 778
 779     def test_sha256d_truncated(self):
 780         h1 = hashutil.tagged_hash("tag1", "value", 16)
 781         h2 = hashutil.tagged_hasher("tag1", 16)
 782         h2.update("value")
 783         h2 = h2.digest()
 784         self.failUnlessEqual(len(h1), 16)
 785         self.failUnlessEqual(len(h2), 16)
 786         self.failUnlessEqual(h1, h2)
 787
 788     def test_chk(self):
 789         h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
 790         h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
 791         h2.update("data")
 792         h2 = h2.digest()
 793         self.failUnlessEqual(h1, h2)
 794
 795     def test_hashers(self):
 796         h1 = hashutil.block_hash("foo")
 797         h2 = hashutil.block_hasher()
 798         h2.update("foo")
 799         self.failUnlessEqual(h1, h2.digest())
 800
 801         h1 = hashutil.uri_extension_hash("foo")
 802         h2 = hashutil.uri_extension_hasher()
 803         h2.update("foo")
 804         self.failUnlessEqual(h1, h2.digest())
 805
 806         h1 = hashutil.plaintext_hash("foo")
 807         h2 = hashutil.plaintext_hasher()
 808         h2.update("foo")
 809         self.failUnlessEqual(h1, h2.digest())
 810
 811         h1 = hashutil.crypttext_hash("foo")
 812         h2 = hashutil.crypttext_hasher()
 813         h2.update("foo")
 814         self.failUnlessEqual(h1, h2.digest())
 815
 816         h1 = hashutil.crypttext_segment_hash("foo")
 817         h2 = hashutil.crypttext_segment_hasher()
 818         h2.update("foo")
 819         self.failUnlessEqual(h1, h2.digest())
 820
 821         h1 = hashutil.plaintext_segment_hash("foo")
 822         h2 = hashutil.plaintext_segment_hasher()
 823         h2.update("foo")
 824         self.failUnlessEqual(h1, h2.digest())
 825
 826     def test_timing_safe_compare(self):
 827         self.failUnless(hashutil.timing_safe_compare("a", "a"))
 828         self.failUnless(hashutil.timing_safe_compare("ab", "ab"))
 829         self.failIf(hashutil.timing_safe_compare("a", "b"))
 830         self.failIf(hashutil.timing_safe_compare("a", "aa"))
 831
 832     def _testknown(self, hashf, expected_a, *args):
 833         got = hashf(*args)
 834         got_a = base32.b2a(got)
 835         self.failUnlessEqual(got_a, expected_a)
 836
 837     def test_known_answers(self):
 838         # assert backwards compatibility
 839         self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
 840         self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
 841         self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
 842         self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
 843         self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
 844         self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
 845         self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
 846         self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
 847         self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
 848         self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
 849         self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
 850         self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
 851         self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
 852         self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
 853         self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
 854         self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
 855         self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
 856         self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
 857         self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
 858         self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
 859         self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
 860         self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
 861         self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
 862
 863
 864 class Abbreviate(unittest.TestCase):
 865     def test_time(self):
 866         a = abbreviate.abbreviate_time
 867         self.failUnlessEqual(a(None), "unknown")
 868         self.failUnlessEqual(a(0), "0 seconds")
 869         self.failUnlessEqual(a(1), "1 second")
 870         self.failUnlessEqual(a(2), "2 seconds")
 871         self.failUnlessEqual(a(119), "119 seconds")
 872         MIN = 60
 873         self.failUnlessEqual(a(2*MIN), "2 minutes")
 874         self.failUnlessEqual(a(60*MIN), "60 minutes")
 875         self.failUnlessEqual(a(179*MIN), "179 minutes")
 876         HOUR = 60*MIN
 877         self.failUnlessEqual(a(180*MIN), "3 hours")
 878         self.failUnlessEqual(a(4*HOUR), "4 hours")
 879         DAY = 24*HOUR
 880         MONTH = 30*DAY
 881         self.failUnlessEqual(a(2*DAY), "2 days")
 882         self.failUnlessEqual(a(2*MONTH), "2 months")
 883         YEAR = 365*DAY
 884         self.failUnlessEqual(a(5*YEAR), "5 years")
 885
 886     def test_space(self):
 887         tests_si = [(None, "unknown"),
 888                     (0, "0 B"),
 889                     (1, "1 B"),
 890                     (999, "999 B"),
 891                     (1000, "1000 B"),
 892                     (1023, "1023 B"),
 893                     (1024, "1.02 kB"),
 894                     (20*1000, "20.00 kB"),
 895                     (1024*1024, "1.05 MB"),
 896                     (1000*1000, "1.00 MB"),
 897                     (1000*1000*1000, "1.00 GB"),
 898                     (1000*1000*1000*1000, "1.00 TB"),
 899                     (1000*1000*1000*1000*1000, "1.00 PB"),
 900                     (1000*1000*1000*1000*1000*1000, "1.00 EB"),
 901                     (1234567890123456789, "1.23 EB"),
 902                     ]
 903         for (x, expected) in tests_si:
 904             got = abbreviate.abbreviate_space(x, SI=True)
 905             self.failUnlessEqual(got, expected)
 906
 907         tests_base1024 = [(None, "unknown"),
 908                           (0, "0 B"),
 909                           (1, "1 B"),
 910                           (999, "999 B"),
 911                           (1000, "1000 B"),
 912                           (1023, "1023 B"),
 913                           (1024, "1.00 kiB"),
 914                           (20*1024, "20.00 kiB"),
 915                           (1000*1000, "976.56 kiB"),
 916                           (1024*1024, "1.00 MiB"),
 917                           (1024*1024*1024, "1.00 GiB"),
 918                           (1024*1024*1024*1024, "1.00 TiB"),
 919                           (1000*1000*1000*1000*1000, "909.49 TiB"),
 920                           (1024*1024*1024*1024*1024, "1.00 PiB"),
 921                           (1024*1024*1024*1024*1024*1024, "1.00 EiB"),
 922                           (1234567890123456789, "1.07 EiB"),
 923                     ]
 924         for (x, expected) in tests_base1024:
 925             got = abbreviate.abbreviate_space(x, SI=False)
 926             self.failUnlessEqual(got, expected)
 927
 928         self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
 929                              "(1.23 MB, 1.18 MiB)")
 930
 931     def test_parse_space(self):
 932         p = abbreviate.parse_abbreviated_size
 933         self.failUnlessEqual(p(""), None)
 934         self.failUnlessEqual(p(None), None)
 935         self.failUnlessEqual(p("123"), 123)
 936         self.failUnlessEqual(p("123B"), 123)
 937         self.failUnlessEqual(p("2K"), 2000)
 938         self.failUnlessEqual(p("2kb"), 2000)
 939         self.failUnlessEqual(p("2KiB"), 2048)
 940         self.failUnlessEqual(p("10MB"), 10*1000*1000)
 941         self.failUnlessEqual(p("10MiB"), 10*1024*1024)
 942         self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
 943         self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
 944         self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
 945         self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
 946         self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
 947         self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
 948         self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
 949         self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
 950
 951         e = self.failUnlessRaises(ValueError, p, "12 cubits")
 952         self.failUnlessIn("12 cubits", str(e))
 953         e = self.failUnlessRaises(ValueError, p, "1 BB")
 954         self.failUnlessIn("1 BB", str(e))
 955         e = self.failUnlessRaises(ValueError, p, "fhtagn")
 956         self.failUnlessIn("fhtagn", str(e))
 957
 958 class Limiter(unittest.TestCase):
 959     timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
 960
 961     def job(self, i, foo):
 962         self.calls.append( (i, foo) )
 963         self.simultaneous += 1
 964         self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
 965         d = defer.Deferred()
 966         def _done():
 967             self.simultaneous -= 1
 968             d.callback("done %d" % i)
 969         reactor.callLater(1.0, _done)
 970         return d
 971
 972     def bad_job(self, i, foo):
 973         raise ValueError("bad_job %d" % i)
 974
 975     def test_limiter(self):
 976         self.calls = []
 977         self.simultaneous = 0
 978         self.peak_simultaneous = 0
 979         l = limiter.ConcurrencyLimiter()
 980         dl = []
 981         for i in range(20):
 982             dl.append(l.add(self.job, i, foo=str(i)))
 983         d = defer.DeferredList(dl, fireOnOneErrback=True)
 984         def _done(res):
 985             self.failUnlessEqual(self.simultaneous, 0)
 986             self.failUnless(self.peak_simultaneous <= 10)
 987             self.failUnlessEqual(len(self.calls), 20)
 988             for i in range(20):
 989                 self.failUnless( (i, str(i)) in self.calls)
 990         d.addCallback(_done)
 991         return d
 992
 993     def test_errors(self):
 994         self.calls = []
 995         self.simultaneous = 0
 996         self.peak_simultaneous = 0
 997         l = limiter.ConcurrencyLimiter()
 998         dl = []
 999         for i in range(20):
1000             dl.append(l.add(self.job, i, foo=str(i)))
1001         d2 = l.add(self.bad_job, 21, "21")
1002         d = defer.DeferredList(dl, fireOnOneErrback=True)
1003         def _most_done(res):
1004             results = []
1005             for (success, result) in res:
1006                 self.failUnlessEqual(success, True)
1007                 results.append(result)
1008             results.sort()
1009             expected_results = ["done %d" % i for i in range(20)]
1010             expected_results.sort()
1011             self.failUnlessEqual(results, expected_results)
1012             self.failUnless(self.peak_simultaneous <= 10)
1013             self.failUnlessEqual(len(self.calls), 20)
1014             for i in range(20):
1015                 self.failUnless( (i, str(i)) in self.calls)
1016             def _good(res):
1017                 self.fail("should have failed, not got %s" % (res,))
1018             def _err(f):
1019                 f.trap(ValueError)
1020                 self.failUnless("bad_job 21" in str(f))
1021             d2.addCallbacks(_good, _err)
1022             return d2
1023         d.addCallback(_most_done)
1024         def _all_done(res):
1025             self.failUnlessEqual(self.simultaneous, 0)
1026             self.failUnless(self.peak_simultaneous <= 10)
1027             self.failUnlessEqual(len(self.calls), 20)
1028             for i in range(20):
1029                 self.failUnless( (i, str(i)) in self.calls)
1030         d.addCallback(_all_done)
1031         return d
1032
1033 class TimeFormat(unittest.TestCase, TimezoneMixin):
1034     def test_epoch(self):
1035         return self._help_test_epoch()
1036
1037     def test_epoch_in_London(self):
1038         # Europe/London is a particularly troublesome timezone.  Nowadays, its
1039         # offset from GMT is 0.  But in 1970, its offset from GMT was 1.
1040         # (Apparently in 1970 Britain had redefined standard time to be GMT+1
1041         # and stayed in standard time all year round, whereas today
1042         # Europe/London standard time is GMT and Europe/London Daylight
1043         # Savings Time is GMT+1.)  The current implementation of
1044         # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
1045         # Europe/London.  (As soon as this unit test is done then I'll change
1046         # that implementation to something that works even in this case...)
1047         self.setTimezone("Europe/London")
1048         return self._help_test_epoch()
1049
1050     def _help_test_epoch(self):
1051         origtzname = time.tzname
1052         s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
1053         self.failUnlessEqual(s, 1.0)
1054         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
1055         self.failUnlessEqual(s, 1.0)
1056         s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
1057         self.failUnlessEqual(s, 1.0)
1058
1059         self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
1060         self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
1061                              "1970-01-01 00:00:01")
1062
1063         now = time.time()
1064         isostr = time_format.iso_utc(now)
1065         timestamp = time_format.iso_utc_time_to_seconds(isostr)
1066         self.failUnlessEqual(int(timestamp), int(now))
1067
1068         def my_time():
1069             return 1.0
1070         self.failUnlessEqual(time_format.iso_utc(t=my_time),
1071                              "1970-01-01_00:00:01")
1072         e = self.failUnlessRaises(ValueError,
1073                                   time_format.iso_utc_time_to_seconds,
1074                                   "invalid timestring")
1075         self.failUnless("not a complete ISO8601 timestamp" in str(e))
1076         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
1077         self.failUnlessEqual(s, 1.5)
1078
1079         # Look for daylight-savings-related errors.
1080         thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
1081         self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
1082         self.failUnlessEqual(origtzname, time.tzname)
1083
1084     def test_iso_utc(self):
1085         when = 1266760143.7841301
1086         out = time_format.iso_utc_date(when)
1087         self.failUnlessEqual(out, "2010-02-21")
1088         out = time_format.iso_utc_date(t=lambda: when)
1089         self.failUnlessEqual(out, "2010-02-21")
1090         out = time_format.iso_utc(when)
1091         self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
1092         out = time_format.iso_utc(when, sep="-")
1093         self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
1094
1095     def test_parse_duration(self):
1096         p = time_format.parse_duration
1097         DAY = 24*60*60
1098         self.failUnlessEqual(p("1 day"), DAY)
1099         self.failUnlessEqual(p("2 days"), 2*DAY)
1100         self.failUnlessEqual(p("3 months"), 3*31*DAY)
1101         self.failUnlessEqual(p("4 mo"), 4*31*DAY)
1102         self.failUnlessEqual(p("5 years"), 5*365*DAY)
1103         e = self.failUnlessRaises(ValueError, p, "123")
1104         self.failUnlessIn("no unit (like day, month, or year) in '123'",
1105                           str(e))
1106
1107     def test_parse_date(self):
1108         self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
1109
1110     def test_format_time(self):
1111         self.failUnlessEqual(time_format.format_time(time.gmtime(0)), '1970-01-01 00:00:00')
1112         self.failUnlessEqual(time_format.format_time(time.gmtime(60)), '1970-01-01 00:01:00')
1113         self.failUnlessEqual(time_format.format_time(time.gmtime(60*60)), '1970-01-01 01:00:00')
1114         seconds_per_day = 60*60*24
1115         leap_years_1970_to_2014_inclusive = ((2012 - 1968) // 4)
1116         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')
1117
1118     def test_format_time_y2038(self):
1119         seconds_per_day = 60*60*24
1120         leap_years_1970_to_2047_inclusive = ((2044 - 1968) // 4)
1121         try:
1122             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')
1123         except unittest.FailTest:
1124             raise unittest.SkipTest("Note: this system cannot handle dates after 2037.")
1125
1126     def test_format_delta(self):
1127         time_1 = 1389812723
1128         time_5s_delta = 1389812728
1129         time_28m7s_delta = 1389814410
1130         time_1h_delta = 1389816323
1131         time_1d21h46m49s_delta = 1389977532
1132
1133         self.failUnlessEqual(
1134             time_format.format_delta(time_1, time_1), '0s')
1135
1136         self.failUnlessEqual(
1137             time_format.format_delta(time_1, time_5s_delta), '5s')
1138         self.failUnlessEqual(
1139             time_format.format_delta(time_1, time_28m7s_delta), '28m 7s')
1140         self.failUnlessEqual(
1141             time_format.format_delta(time_1, time_1h_delta), '1h 0m 0s')
1142         self.failUnlessEqual(
1143             time_format.format_delta(time_1, time_1d21h46m49s_delta), '1d 21h 46m 49s')
1144
1145         self.failUnlessEqual(
1146             time_format.format_delta(time_1d21h46m49s_delta, time_1), '-')
1147
1148         # time_1 with a decimal fraction will make the delta 1s less
1149         time_1decimal = 1389812723.383963
1150
1151         self.failUnlessEqual(
1152             time_format.format_delta(time_1decimal, time_5s_delta), '4s')
1153         self.failUnlessEqual(
1154             time_format.format_delta(time_1decimal, time_28m7s_delta), '28m 6s')
1155         self.failUnlessEqual(
1156             time_format.format_delta(time_1decimal, time_1h_delta), '59m 59s')
1157         self.failUnlessEqual(
1158             time_format.format_delta(time_1decimal, time_1d21h46m49s_delta), '1d 21h 46m 48s')
1159
1160 class CacheDir(unittest.TestCase):
1161     def test_basic(self):
1162         basedir = "test_util/CacheDir/test_basic"
1163
1164         def _failIfExists(name):
1165             absfn = os.path.join(basedir, name)
1166             self.failIf(os.path.exists(absfn),
1167                         "%s exists but it shouldn't" % absfn)
1168
1169         def _failUnlessExists(name):
1170             absfn = os.path.join(basedir, name)
1171             self.failUnless(os.path.exists(absfn),
1172                             "%s doesn't exist but it should" % absfn)
1173
1174         cdm = cachedir.CacheDirectoryManager(basedir)
1175         a = cdm.get_file("a")
1176         b = cdm.get_file("b")
1177         c = cdm.get_file("c")
1178         f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
1179         f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
1180         f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
1181
1182         _failUnlessExists("a")
1183         _failUnlessExists("b")
1184         _failUnlessExists("c")
1185
1186         cdm.check()
1187
1188         _failUnlessExists("a")
1189         _failUnlessExists("b")
1190         _failUnlessExists("c")
1191
1192         del a
1193         # this file won't be deleted yet, because it isn't old enough
1194         cdm.check()
1195         _failUnlessExists("a")
1196         _failUnlessExists("b")
1197         _failUnlessExists("c")
1198
1199         # we change the definition of "old" to make everything old
1200         cdm.old = -10
1201
1202         cdm.check()
1203         _failIfExists("a")
1204         _failUnlessExists("b")
1205         _failUnlessExists("c")
1206
1207         cdm.old = 60*60
1208
1209         del b
1210
1211         cdm.check()
1212         _failIfExists("a")
1213         _failUnlessExists("b")
1214         _failUnlessExists("c")
1215
1216         b2 = cdm.get_file("b")
1217
1218         cdm.check()
1219         _failIfExists("a")
1220         _failUnlessExists("b")
1221         _failUnlessExists("c")
1222         del b2
1223
1224 ctr = [0]
1225 class EqButNotIs:
1226     def __init__(self, x):
1227         self.x = x
1228         self.hash = ctr[0]
1229         ctr[0] += 1
1230     def __repr__(self):
1231         return "<%s %s>" % (self.__class__.__name__, self.x,)
1232     def __hash__(self):
1233         return self.hash
1234     def __le__(self, other):
1235         return self.x <= other
1236     def __lt__(self, other):
1237         return self.x < other
1238     def __ge__(self, other):
1239         return self.x >= other
1240     def __gt__(self, other):
1241         return self.x > other
1242     def __ne__(self, other):
1243         return self.x != other
1244     def __eq__(self, other):
1245         return self.x == other
1246
1247 class DictUtil(unittest.TestCase):
1248     def _help_test_empty_dict(self, klass):
1249         d1 = klass()
1250         d2 = klass({})
1251
1252         self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1253         self.failUnless(len(d1) == 0)
1254         self.failUnless(len(d2) == 0)
1255
1256     def _help_test_nonempty_dict(self, klass):
1257         d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1258         d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1259
1260         self.failUnless(d1 == d2)
1261         self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1262         self.failUnless(len(d2) == 3)
1263
1264     def _help_test_eq_but_notis(self, klass):
1265         d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1266         d.pop('b')
1267
1268         d.clear()
1269         d['a'] = 3
1270         d['b'] = EqButNotIs(3)
1271         d['c'] = 3
1272         d.pop('b')
1273
1274         d.clear()
1275         d['b'] = EqButNotIs(3)
1276         d['a'] = 3
1277         d['c'] = 3
1278         d.pop('b')
1279
1280         d.clear()
1281         d['a'] = EqButNotIs(3)
1282         d['c'] = 3
1283         d['a'] = 3
1284
1285         d.clear()
1286         fake3 = EqButNotIs(3)
1287         fake7 = EqButNotIs(7)
1288         d[fake3] = fake7
1289         d[3] = 7
1290         d[3] = 8
1291         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1292         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1293         # The real 7 should have been ejected by the d[3] = 8.
1294         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1295         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1296         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1297         d[fake3] = 8
1298
1299         d.clear()
1300         d[3] = 7
1301         fake3 = EqButNotIs(3)
1302         fake7 = EqButNotIs(7)
1303         d[fake3] = fake7
1304         d[3] = 8
1305         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1306         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1307         # The real 7 should have been ejected by the d[3] = 8.
1308         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1309         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1310         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1311         d[fake3] = 8
1312
1313     def test_all(self):
1314         self._help_test_eq_but_notis(dictutil.UtilDict)
1315         self._help_test_eq_but_notis(dictutil.NumDict)
1316         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1317         self._help_test_nonempty_dict(dictutil.UtilDict)
1318         self._help_test_nonempty_dict(dictutil.NumDict)
1319         self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1320         self._help_test_eq_but_notis(dictutil.UtilDict)
1321         self._help_test_eq_but_notis(dictutil.NumDict)
1322         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1323
1324     def test_dict_of_sets(self):
1325         ds = dictutil.DictOfSets()
1326         ds.add(1, "a")
1327         ds.add(2, "b")
1328         ds.add(2, "b")
1329         ds.add(2, "c")
1330         self.failUnlessEqual(ds[1], set(["a"]))
1331         self.failUnlessEqual(ds[2], set(["b", "c"]))
1332         ds.discard(3, "d") # should not raise an exception
1333         ds.discard(2, "b")
1334         self.failUnlessEqual(ds[2], set(["c"]))
1335         ds.discard(2, "c")
1336         self.failIf(2 in ds)
1337
1338         ds.add(3, "f")
1339         ds2 = dictutil.DictOfSets()
1340         ds2.add(3, "f")
1341         ds2.add(3, "g")
1342         ds2.add(4, "h")
1343         ds.update(ds2)
1344         self.failUnlessEqual(ds[1], set(["a"]))
1345         self.failUnlessEqual(ds[3], set(["f", "g"]))
1346         self.failUnlessEqual(ds[4], set(["h"]))
1347
1348     def test_move(self):
1349         d1 = {1: "a", 2: "b"}
1350         d2 = {2: "c", 3: "d"}
1351         dictutil.move(1, d1, d2)
1352         self.failUnlessEqual(d1, {2: "b"})
1353         self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1354
1355         d1 = {1: "a", 2: "b"}
1356         d2 = {2: "c", 3: "d"}
1357         dictutil.move(2, d1, d2)
1358         self.failUnlessEqual(d1, {1: "a"})
1359         self.failUnlessEqual(d2, {2: "b", 3: "d"})
1360
1361         d1 = {1: "a", 2: "b"}
1362         d2 = {2: "c", 3: "d"}
1363         self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1364
1365     def test_subtract(self):
1366         d1 = {1: "a", 2: "b"}
1367         d2 = {2: "c", 3: "d"}
1368         d3 = dictutil.subtract(d1, d2)
1369         self.failUnlessEqual(d3, {1: "a"})
1370
1371         d1 = {1: "a", 2: "b"}
1372         d2 = {2: "c"}
1373         d3 = dictutil.subtract(d1, d2)
1374         self.failUnlessEqual(d3, {1: "a"})
1375
1376     def test_utildict(self):
1377         d = dictutil.UtilDict({1: "a", 2: "b"})
1378         d.del_if_present(1)
1379         d.del_if_present(3)
1380         self.failUnlessEqual(d, {2: "b"})
1381         def eq(a, b):
1382             return a == b
1383         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1384
1385         d = dictutil.UtilDict({1: "b", 2: "a"})
1386         self.failUnlessEqual(d.items_sorted_by_value(),
1387                              [(2, "a"), (1, "b")])
1388         self.failUnlessEqual(d.items_sorted_by_key(),
1389                              [(1, "b"), (2, "a")])
1390         self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1391         self.failUnless(1 in d)
1392
1393         d2 = dictutil.UtilDict({3: "c", 4: "d"})
1394         self.failUnless(d != d2)
1395         self.failUnless(d2 > d)
1396         self.failUnless(d2 >= d)
1397         self.failUnless(d <= d2)
1398         self.failUnless(d < d2)
1399         self.failUnlessEqual(d[1], "b")
1400         self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1401
1402         d3 = d.copy()
1403         self.failUnlessEqual(d, d3)
1404         self.failUnless(isinstance(d3, dictutil.UtilDict))
1405
1406         d4 = d.fromkeys([3,4], "e")
1407         self.failUnlessEqual(d4, {3: "e", 4: "e"})
1408
1409         self.failUnlessEqual(d.get(1), "b")
1410         self.failUnlessEqual(d.get(3), None)
1411         self.failUnlessEqual(d.get(3, "default"), "default")
1412         self.failUnlessEqual(sorted(list(d.items())),
1413                              [(1, "b"), (2, "a")])
1414         self.failUnlessEqual(sorted(list(d.iteritems())),
1415                              [(1, "b"), (2, "a")])
1416         self.failUnlessEqual(sorted(d.keys()), [1, 2])
1417         self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1418         x = d.setdefault(1, "new")
1419         self.failUnlessEqual(x, "b")
1420         self.failUnlessEqual(d[1], "b")
1421         x = d.setdefault(3, "new")
1422         self.failUnlessEqual(x, "new")
1423         self.failUnlessEqual(d[3], "new")
1424         del d[3]
1425
1426         x = d.popitem()
1427         self.failUnless(x in [(1, "b"), (2, "a")])
1428         x = d.popitem()
1429         self.failUnless(x in [(1, "b"), (2, "a")])
1430         self.failUnlessRaises(KeyError, d.popitem)
1431
1432     def test_numdict(self):
1433         d = dictutil.NumDict({"a": 1, "b": 2})
1434
1435         d.add_num("a", 10, 5)
1436         d.add_num("c", 20, 5)
1437         d.add_num("d", 30)
1438         self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1439
1440         d.subtract_num("a", 10)
1441         d.subtract_num("e", 10)
1442         d.subtract_num("f", 10, 15)
1443         self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1444                                  "e": -10, "f": 5})
1445
1446         self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1447
1448         d = dictutil.NumDict()
1449         d.inc("a")
1450         d.inc("a")
1451         d.inc("b", 5)
1452         self.failUnlessEqual(d, {"a": 2, "b": 6})
1453         d.dec("a")
1454         d.dec("c")
1455         d.dec("d", 5)
1456         self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1457         self.failUnlessEqual(d.items_sorted_by_key(),
1458                              [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1459         self.failUnlessEqual(d.items_sorted_by_value(),
1460                              [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1461         self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1462
1463         d = dictutil.NumDict({"a": 1, "b": 2})
1464         self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1465         self.failUnless("a" in d)
1466
1467         d2 = dictutil.NumDict({"c": 3, "d": 4})
1468         self.failUnless(d != d2)
1469         self.failUnless(d2 > d)
1470         self.failUnless(d2 >= d)
1471         self.failUnless(d <= d2)
1472         self.failUnless(d < d2)
1473         self.failUnlessEqual(d["a"], 1)
1474         self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1475         def eq(a, b):
1476             return a == b
1477         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1478
1479         d3 = d.copy()
1480         self.failUnlessEqual(d, d3)
1481         self.failUnless(isinstance(d3, dictutil.NumDict))
1482
1483         d4 = d.fromkeys(["a","b"], 5)
1484         self.failUnlessEqual(d4, {"a": 5, "b": 5})
1485
1486         self.failUnlessEqual(d.get("a"), 1)
1487         self.failUnlessEqual(d.get("c"), 0)
1488         self.failUnlessEqual(d.get("c", 5), 5)
1489         self.failUnlessEqual(sorted(list(d.items())),
1490                              [("a", 1), ("b", 2)])
1491         self.failUnlessEqual(sorted(list(d.iteritems())),
1492                              [("a", 1), ("b", 2)])
1493         self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1494         self.failUnlessEqual(sorted(d.values()), [1, 2])
1495         self.failUnless(d.has_key("a"))
1496         self.failIf(d.has_key("c"))
1497
1498         x = d.setdefault("c", 3)
1499         self.failUnlessEqual(x, 3)
1500         self.failUnlessEqual(d["c"], 3)
1501         x = d.setdefault("c", 5)
1502         self.failUnlessEqual(x, 3)
1503         self.failUnlessEqual(d["c"], 3)
1504         del d["c"]
1505
1506         x = d.popitem()
1507         self.failUnless(x in [("a", 1), ("b", 2)])
1508         x = d.popitem()
1509         self.failUnless(x in [("a", 1), ("b", 2)])
1510         self.failUnlessRaises(KeyError, d.popitem)
1511
1512         d.update({"c": 3})
1513         d.update({"c": 4, "d": 5})
1514         self.failUnlessEqual(d, {"c": 4, "d": 5})
1515
1516     def test_del_if_present(self):
1517         d = {1: "a", 2: "b"}
1518         dictutil.del_if_present(d, 1)
1519         dictutil.del_if_present(d, 3)
1520         self.failUnlessEqual(d, {2: "b"})
1521
1522     def test_valueordereddict(self):
1523         d = dictutil.ValueOrderedDict()
1524         d["a"] = 3
1525         d["b"] = 2
1526         d["c"] = 1
1527
1528         self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1529         self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1530         self.failUnlessEqual(d.values(), [1, 2, 3])
1531         self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1532         self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1533         def eq(a, b):
1534             return a == b
1535         self.failIf(d == {"a": 4})
1536         self.failUnless(d != {"a": 4})
1537
1538         x = d.setdefault("d", 0)
1539         self.failUnlessEqual(x, 0)
1540         self.failUnlessEqual(d["d"], 0)
1541         x = d.setdefault("d", -1)
1542         self.failUnlessEqual(x, 0)
1543         self.failUnlessEqual(d["d"], 0)
1544
1545         x = d.remove("e", "default", False)
1546         self.failUnlessEqual(x, "default")
1547         self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1548         x = d.remove("d", 5)
1549         self.failUnlessEqual(x, 0)
1550
1551         x = d.__getitem__("c")
1552         self.failUnlessEqual(x, 1)
1553         x = d.__getitem__("e", "default", False)
1554         self.failUnlessEqual(x, "default")
1555         self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1556
1557         self.failUnlessEqual(d.popitem(), ("c", 1))
1558         self.failUnlessEqual(d.popitem(), ("b", 2))
1559         self.failUnlessEqual(d.popitem(), ("a", 3))
1560         self.failUnlessRaises(KeyError, d.popitem)
1561
1562         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1563         x = d.pop("d", "default", False)
1564         self.failUnlessEqual(x, "default")
1565         self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1566         x = d.pop("b")
1567         self.failUnlessEqual(x, 2)
1568         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1569
1570         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1571         x = d.pop_from_list(1) # pop the second item, b/2
1572         self.failUnlessEqual(x, "b")
1573         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1574
1575     def test_auxdict(self):
1576         d = dictutil.AuxValueDict()
1577         # we put the serialized form in the auxdata
1578         d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1579
1580         self.failUnlessEqual(d.keys(), ["key"])
1581         self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1582         self.failUnlessEqual(d.get_aux("key"), "serialized")
1583         def _get_missing(key):
1584             return d[key]
1585         self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1586         self.failUnlessEqual(d.get("nonkey"), None)
1587         self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1588         self.failUnlessEqual(d.get_aux("nonkey"), None)
1589         self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1590
1591         d["key"] = ("filecap2", "metadata2")
1592         self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1593         self.failUnlessEqual(d.get_aux("key"), None)
1594
1595         d.set_with_aux("key2", "value2", "aux2")
1596         self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1597         del d["key2"]
1598         self.failUnlessEqual(d.keys(), ["key"])
1599         self.failIf("key2" in d)
1600         self.failUnlessRaises(KeyError, _get_missing, "key2")
1601         self.failUnlessEqual(d.get("key2"), None)
1602         self.failUnlessEqual(d.get_aux("key2"), None)
1603         d["key2"] = "newvalue2"
1604         self.failUnlessEqual(d.get("key2"), "newvalue2")
1605         self.failUnlessEqual(d.get_aux("key2"), None)
1606
1607         d = dictutil.AuxValueDict({1:2,3:4})
1608         self.failUnlessEqual(sorted(d.keys()), [1,3])
1609         self.failUnlessEqual(d[1], 2)
1610         self.failUnlessEqual(d.get_aux(1), None)
1611
1612         d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1613         self.failUnlessEqual(sorted(d.keys()), [1,3])
1614         self.failUnlessEqual(d[1], 2)
1615         self.failUnlessEqual(d.get_aux(1), None)
1616
1617         d = dictutil.AuxValueDict(one=1, two=2)
1618         self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1619         self.failUnlessEqual(d["one"], 1)
1620         self.failUnlessEqual(d.get_aux("one"), None)
1621
1622 class Pipeline(unittest.TestCase):
1623     def pause(self, *args, **kwargs):
1624         d = defer.Deferred()
1625         self.calls.append( (d, args, kwargs) )
1626         return d
1627
1628     def failUnlessCallsAre(self, expected):
1629         #print self.calls
1630         #print expected
1631         self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1632         for i,c in enumerate(self.calls):
1633             self.failUnlessEqual(c[1:], expected[i], str(i))
1634
1635     def test_basic(self):
1636         self.calls = []
1637         finished = []
1638         p = pipeline.Pipeline(100)
1639
1640         d = p.flush() # fires immediately
1641         d.addCallbacks(finished.append, log.err)
1642         self.failUnlessEqual(len(finished), 1)
1643         finished = []
1644
1645         d = p.add(10, self.pause, "one")
1646         # the call should start right away, and our return Deferred should
1647         # fire right away
1648         d.addCallbacks(finished.append, log.err)
1649         self.failUnlessEqual(len(finished), 1)
1650         self.failUnlessEqual(finished[0], None)
1651         self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1652         self.failUnlessEqual(p.gauge, 10)
1653
1654         # pipeline: [one]
1655
1656         finished = []
1657         d = p.add(20, self.pause, "two", kw=2)
1658         # pipeline: [one, two]
1659
1660         # the call and the Deferred should fire right away
1661         d.addCallbacks(finished.append, log.err)
1662         self.failUnlessEqual(len(finished), 1)
1663         self.failUnlessEqual(finished[0], None)
1664         self.failUnlessCallsAre([ ( ("one",) , {} ),
1665                                   ( ("two",) , {"kw": 2} ),
1666                                   ])
1667         self.failUnlessEqual(p.gauge, 30)
1668
1669         self.calls[0][0].callback("one-result")
1670         # pipeline: [two]
1671         self.failUnlessEqual(p.gauge, 20)
1672
1673         finished = []
1674         d = p.add(90, self.pause, "three", "posarg1")
1675         # pipeline: [two, three]
1676         flushed = []
1677         fd = p.flush()
1678         fd.addCallbacks(flushed.append, log.err)
1679         self.failUnlessEqual(flushed, [])
1680
1681         # the call will be made right away, but the return Deferred will not,
1682         # because the pipeline is now full.
1683         d.addCallbacks(finished.append, log.err)
1684         self.failUnlessEqual(len(finished), 0)
1685         self.failUnlessCallsAre([ ( ("one",) , {} ),
1686                                   ( ("two",) , {"kw": 2} ),
1687                                   ( ("three", "posarg1"), {} ),
1688                                   ])
1689         self.failUnlessEqual(p.gauge, 110)
1690
1691         self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1692
1693         # retiring either call will unblock the pipeline, causing the #3
1694         # Deferred to fire
1695         self.calls[2][0].callback("three-result")
1696         # pipeline: [two]
1697
1698         self.failUnlessEqual(len(finished), 1)
1699         self.failUnlessEqual(finished[0], None)
1700         self.failUnlessEqual(flushed, [])
1701
1702         # retiring call#2 will finally allow the flush() Deferred to fire
1703         self.calls[1][0].callback("two-result")
1704         self.failUnlessEqual(len(flushed), 1)
1705
1706     def test_errors(self):
1707         self.calls = []
1708         p = pipeline.Pipeline(100)
1709
1710         d1 = p.add(200, self.pause, "one")
1711         d2 = p.flush()
1712
1713         finished = []
1714         d1.addBoth(finished.append)
1715         self.failUnlessEqual(finished, [])
1716
1717         flushed = []
1718         d2.addBoth(flushed.append)
1719         self.failUnlessEqual(flushed, [])
1720
1721         self.calls[0][0].errback(ValueError("oops"))
1722
1723         self.failUnlessEqual(len(finished), 1)
1724         f = finished[0]
1725         self.failUnless(isinstance(f, Failure))
1726         self.failUnless(f.check(pipeline.PipelineError))
1727         self.failUnlessIn("PipelineError", str(f.value))
1728         self.failUnlessIn("ValueError", str(f.value))
1729         r = repr(f.value)
1730         self.failUnless("ValueError" in r, r)
1731         f2 = f.value.error
1732         self.failUnless(f2.check(ValueError))
1733
1734         self.failUnlessEqual(len(flushed), 1)
1735         f = flushed[0]
1736         self.failUnless(isinstance(f, Failure))
1737         self.failUnless(f.check(pipeline.PipelineError))
1738         f2 = f.value.error
1739         self.failUnless(f2.check(ValueError))
1740
1741         # now that the pipeline is in the failed state, any new calls will
1742         # fail immediately
1743
1744         d3 = p.add(20, self.pause, "two")
1745
1746         finished = []
1747         d3.addBoth(finished.append)
1748         self.failUnlessEqual(len(finished), 1)
1749         f = finished[0]
1750         self.failUnless(isinstance(f, Failure))
1751         self.failUnless(f.check(pipeline.PipelineError))
1752         r = repr(f.value)
1753         self.failUnless("ValueError" in r, r)
1754         f2 = f.value.error
1755         self.failUnless(f2.check(ValueError))
1756
1757         d4 = p.flush()
1758         flushed = []
1759         d4.addBoth(flushed.append)
1760         self.failUnlessEqual(len(flushed), 1)
1761         f = flushed[0]
1762         self.failUnless(isinstance(f, Failure))
1763         self.failUnless(f.check(pipeline.PipelineError))
1764         f2 = f.value.error
1765         self.failUnless(f2.check(ValueError))
1766
1767     def test_errors2(self):
1768         self.calls = []
1769         p = pipeline.Pipeline(100)
1770
1771         d1 = p.add(10, self.pause, "one")
1772         d2 = p.add(20, self.pause, "two")
1773         d3 = p.add(30, self.pause, "three")
1774         d4 = p.flush()
1775
1776         # one call fails, then the second one succeeds: make sure
1777         # ExpandableDeferredList tolerates the second one
1778
1779         flushed = []
1780         d4.addBoth(flushed.append)
1781         self.failUnlessEqual(flushed, [])
1782
1783         self.calls[0][0].errback(ValueError("oops"))
1784         self.failUnlessEqual(len(flushed), 1)
1785         f = flushed[0]
1786         self.failUnless(isinstance(f, Failure))
1787         self.failUnless(f.check(pipeline.PipelineError))
1788         f2 = f.value.error
1789         self.failUnless(f2.check(ValueError))
1790
1791         self.calls[1][0].callback("two-result")
1792         self.calls[2][0].errback(ValueError("three-error"))
1793
1794         del d1,d2,d3,d4
1795
1796 class SampleError(Exception):
1797     pass
1798
1799 class Log(unittest.TestCase):
1800     def test_err(self):
1801         if not hasattr(self, "flushLoggedErrors"):
1802             # without flushLoggedErrors, we can't get rid of the
1803             # twisted.log.err that tahoe_log records, so we can't keep this
1804             # test from [ERROR]ing
1805             raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1806         try:
1807             raise SampleError("simple sample")
1808         except:
1809             f = Failure()
1810         tahoe_log.err(format="intentional sample error",
1811                       failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1812         self.flushLoggedErrors(SampleError)
1813
1814
1815 class SimpleSpans:
1816     # this is a simple+inefficient form of util.spans.Spans . We compare the
1817     # behavior of this reference model against the real (efficient) form.
1818
1819     def __init__(self, _span_or_start=None, length=None):
1820         self._have = set()
1821         if length is not None:
1822             for i in range(_span_or_start, _span_or_start+length):
1823                 self._have.add(i)
1824         elif _span_or_start:
1825             for (start,length) in _span_or_start:
1826                 self.add(start, length)
1827
1828     def add(self, start, length):
1829         for i in range(start, start+length):
1830             self._have.add(i)
1831         return self
1832
1833     def remove(self, start, length):
1834         for i in range(start, start+length):
1835             self._have.discard(i)
1836         return self
1837
1838     def each(self):
1839         return sorted(self._have)
1840
1841     def __iter__(self):
1842         items = sorted(self._have)
1843         prevstart = None
1844         prevend = None
1845         for i in items:
1846             if prevstart is None:
1847                 prevstart = prevend = i
1848                 continue
1849             if i == prevend+1:
1850                 prevend = i
1851                 continue
1852             yield (prevstart, prevend-prevstart+1)
1853             prevstart = prevend = i
1854         if prevstart is not None:
1855             yield (prevstart, prevend-prevstart+1)
1856
1857     def __nonzero__(self): # this gets us bool()
1858         return self.len()
1859
1860     def len(self):
1861         return len(self._have)
1862
1863     def __add__(self, other):
1864         s = self.__class__(self)
1865         for (start, length) in other:
1866             s.add(start, length)
1867         return s
1868
1869     def __sub__(self, other):
1870         s = self.__class__(self)
1871         for (start, length) in other:
1872             s.remove(start, length)
1873         return s
1874
1875     def __iadd__(self, other):
1876         for (start, length) in other:
1877             self.add(start, length)
1878         return self
1879
1880     def __isub__(self, other):
1881         for (start, length) in other:
1882             self.remove(start, length)
1883         return self
1884
1885     def __and__(self, other):
1886         s = self.__class__()
1887         for i in other.each():
1888             if i in self._have:
1889                 s.add(i, 1)
1890         return s
1891
1892     def __contains__(self, (start,length)):
1893         for i in range(start, start+length):
1894             if i not in self._have:
1895                 return False
1896         return True
1897
1898 class ByteSpans(unittest.TestCase):
1899     def test_basic(self):
1900         s = Spans()
1901         self.failUnlessEqual(list(s), [])
1902         self.failIf(s)
1903         self.failIf((0,1) in s)
1904         self.failUnlessEqual(s.len(), 0)
1905
1906         s1 = Spans(3, 4) # 3,4,5,6
1907         self._check1(s1)
1908
1909         s1 = Spans(3L, 4L) # 3,4,5,6
1910         self._check1(s1)
1911
1912         s2 = Spans(s1)
1913         self._check1(s2)
1914
1915         s2.add(10,2) # 10,11
1916         self._check1(s1)
1917         self.failUnless((10,1) in s2)
1918         self.failIf((10,1) in s1)
1919         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1920         self.failUnlessEqual(s2.len(), 6)
1921
1922         s2.add(15,2).add(20,2)
1923         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1924         self.failUnlessEqual(s2.len(), 10)
1925
1926         s2.remove(4,3).remove(15,1)
1927         self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1928         self.failUnlessEqual(s2.len(), 6)
1929
1930         s1 = SimpleSpans(3, 4) # 3 4 5 6
1931         s2 = SimpleSpans(5, 4) # 5 6 7 8
1932         i = s1 & s2
1933         self.failUnlessEqual(list(i.each()), [5, 6])
1934
1935     def _check1(self, s):
1936         self.failUnlessEqual(list(s), [(3,4)])
1937         self.failUnless(s)
1938         self.failUnlessEqual(s.len(), 4)
1939         self.failIf((0,1) in s)
1940         self.failUnless((3,4) in s)
1941         self.failUnless((3,1) in s)
1942         self.failUnless((5,2) in s)
1943         self.failUnless((6,1) in s)
1944         self.failIf((6,2) in s)
1945         self.failIf((7,1) in s)
1946         self.failUnlessEqual(list(s.each()), [3,4,5,6])
1947
1948     def test_large(self):
1949         s = Spans(4, 2**65) # don't do this with a SimpleSpans
1950         self.failUnlessEqual(list(s), [(4, 2**65)])
1951         self.failUnless(s)
1952         self.failUnlessEqual(s.len(), 2**65)
1953         self.failIf((0,1) in s)
1954         self.failUnless((4,2) in s)
1955         self.failUnless((2**65,2) in s)
1956
1957     def test_math(self):
1958         s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1959         s2 = Spans(5, 3) # 5,6,7
1960         s3 = Spans(8, 4) # 8,9,10,11
1961
1962         s = s1 - s2
1963         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1964         s = s1 - s3
1965         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1966         s = s2 - s3
1967         self.failUnlessEqual(list(s.each()), [5,6,7])
1968         s = s1 & s2
1969         self.failUnlessEqual(list(s.each()), [5,6,7])
1970         s = s2 & s1
1971         self.failUnlessEqual(list(s.each()), [5,6,7])
1972         s = s1 & s3
1973         self.failUnlessEqual(list(s.each()), [8,9])
1974         s = s3 & s1
1975         self.failUnlessEqual(list(s.each()), [8,9])
1976         s = s2 & s3
1977         self.failUnlessEqual(list(s.each()), [])
1978         s = s3 & s2
1979         self.failUnlessEqual(list(s.each()), [])
1980         s = Spans() & s3
1981         self.failUnlessEqual(list(s.each()), [])
1982         s = s3 & Spans()
1983         self.failUnlessEqual(list(s.each()), [])
1984
1985         s = s1 + s2
1986         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1987         s = s1 + s3
1988         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1989         s = s2 + s3
1990         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1991
1992         s = Spans(s1)
1993         s -= s2
1994         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1995         s = Spans(s1)
1996         s -= s3
1997         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1998         s = Spans(s2)
1999         s -= s3
2000         self.failUnlessEqual(list(s.each()), [5,6,7])
2001
2002         s = Spans(s1)
2003         s += s2
2004         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
2005         s = Spans(s1)
2006         s += s3
2007         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
2008         s = Spans(s2)
2009         s += s3
2010         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
2011
2012     def test_random(self):
2013         # attempt to increase coverage of corner cases by comparing behavior
2014         # of a simple-but-slow model implementation against the
2015         # complex-but-fast actual implementation, in a large number of random
2016         # operations
2017         S1 = SimpleSpans
2018         S2 = Spans
2019         s1 = S1(); s2 = S2()
2020         seed = ""
2021         def _create(subseed):
2022             ns1 = S1(); ns2 = S2()
2023             for i in range(10):
2024                 what = _hash(subseed+str(i)).hexdigest()
2025                 start = int(what[2:4], 16)
2026                 length = max(1,int(what[5:6], 16))
2027                 ns1.add(start, length); ns2.add(start, length)
2028             return ns1, ns2
2029
2030         #print
2031         for i in range(1000):
2032             what = _hash(seed+str(i)).hexdigest()
2033             op = what[0]
2034             subop = what[1]
2035             start = int(what[2:4], 16)
2036             length = max(1,int(what[5:6], 16))
2037             #print what
2038             if op in "0":
2039                 if subop in "01234":
2040                     s1 = S1(); s2 = S2()
2041                 elif subop in "5678":
2042                     s1 = S1(start, length); s2 = S2(start, length)
2043                 else:
2044                     s1 = S1(s1); s2 = S2(s2)
2045                 #print "s2 = %s" % s2.dump()
2046             elif op in "123":
2047                 #print "s2.add(%d,%d)" % (start, length)
2048                 s1.add(start, length); s2.add(start, length)
2049             elif op in "456":
2050                 #print "s2.remove(%d,%d)" % (start, length)
2051                 s1.remove(start, length); s2.remove(start, length)
2052             elif op in "78":
2053                 ns1, ns2 = _create(what[7:11])
2054                 #print "s2 + %s" % ns2.dump()
2055                 s1 = s1 + ns1; s2 = s2 + ns2
2056             elif op in "9a":
2057                 ns1, ns2 = _create(what[7:11])
2058                 #print "%s - %s" % (s2.dump(), ns2.dump())
2059                 s1 = s1 - ns1; s2 = s2 - ns2
2060             elif op in "bc":
2061                 ns1, ns2 = _create(what[7:11])
2062                 #print "s2 += %s" % ns2.dump()
2063                 s1 += ns1; s2 += ns2
2064             elif op in "de":
2065                 ns1, ns2 = _create(what[7:11])
2066                 #print "%s -= %s" % (s2.dump(), ns2.dump())
2067                 s1 -= ns1; s2 -= ns2
2068             else:
2069                 ns1, ns2 = _create(what[7:11])
2070                 #print "%s &= %s" % (s2.dump(), ns2.dump())
2071                 s1 = s1 & ns1; s2 = s2 & ns2
2072             #print "s2 now %s" % s2.dump()
2073             self.failUnlessEqual(list(s1.each()), list(s2.each()))
2074             self.failUnlessEqual(s1.len(), s2.len())
2075             self.failUnlessEqual(bool(s1), bool(s2))
2076             self.failUnlessEqual(list(s1), list(s2))
2077             for j in range(10):
2078                 what = _hash(what[12:14]+str(j)).hexdigest()
2079                 start = int(what[2:4], 16)
2080                 length = max(1, int(what[5:6], 16))
2081                 span = (start, length)
2082                 self.failUnlessEqual(bool(span in s1), bool(span in s2))
2083
2084
2085     # s()
2086     # s(start,length)
2087     # s(s0)
2088     # s.add(start,length) : returns s
2089     # s.remove(start,length)
2090     # s.each() -> list of byte offsets, mostly for testing
2091     # list(s) -> list of (start,length) tuples, one per span
2092     # (start,length) in s -> True if (start..start+length-1) are all members
2093     #  NOT equivalent to x in list(s)
2094     # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
2095     # bool(s)  (__nonzeron__)
2096     # s = s1+s2, s1-s2, +=s1, -=s1
2097
2098     def test_overlap(self):
2099         for a in range(20):
2100             for b in range(10):
2101                 for c in range(20):
2102                     for d in range(10):
2103                         self._test_overlap(a,b,c,d)
2104
2105     def _test_overlap(self, a, b, c, d):
2106         s1 = set(range(a,a+b))
2107         s2 = set(range(c,c+d))
2108         #print "---"
2109         #self._show_overlap(s1, "1")
2110         #self._show_overlap(s2, "2")
2111         o = overlap(a,b,c,d)
2112         expected = s1.intersection(s2)
2113         if not expected:
2114             self.failUnlessEqual(o, None)
2115         else:
2116             start,length = o
2117             so = set(range(start,start+length))
2118             #self._show(so, "o")
2119             self.failUnlessEqual(so, expected)
2120
2121     def _show_overlap(self, s, c):
2122         import sys
2123         out = sys.stdout
2124         if s:
2125             for i in range(max(s)):
2126                 if i in s:
2127                     out.write(c)
2128                 else:
2129                     out.write(" ")
2130         out.write("\n")
2131
2132 def extend(s, start, length, fill):
2133     if len(s) >= start+length:
2134         return s
2135     assert len(fill) == 1
2136     return s + fill*(start+length-len(s))
2137
2138 def replace(s, start, data):
2139     assert len(s) >= start+len(data)
2140     return s[:start] + data + s[start+len(data):]
2141
2142 class SimpleDataSpans:
2143     def __init__(self, other=None):
2144         self.missing = "" # "1" where missing, "0" where found
2145         self.data = ""
2146         if other:
2147             for (start, data) in other.get_chunks():
2148                 self.add(start, data)
2149
2150     def __nonzero__(self): # this gets us bool()
2151         return self.len()
2152     def len(self):
2153         return len(self.missing.replace("1", ""))
2154     def _dump(self):
2155         return [i for (i,c) in enumerate(self.missing) if c == "0"]
2156     def _have(self, start, length):
2157         m = self.missing[start:start+length]
2158         if not m or len(m)<length or int(m):
2159             return False
2160         return True
2161     def get_chunks(self):
2162         for i in self._dump():
2163             yield (i, self.data[i])
2164     def get_spans(self):
2165         return SimpleSpans([(start,len(data))
2166                             for (start,data) in self.get_chunks()])
2167     def get(self, start, length):
2168         if self._have(start, length):
2169             return self.data[start:start+length]
2170         return None
2171     def pop(self, start, length):
2172         data = self.get(start, length)
2173         if data:
2174             self.remove(start, length)
2175         return data
2176     def remove(self, start, length):
2177         self.missing = replace(extend(self.missing, start, length, "1"),
2178                                start, "1"*length)
2179     def add(self, start, data):
2180         self.missing = replace(extend(self.missing, start, len(data), "1"),
2181                                start, "0"*len(data))
2182         self.data = replace(extend(self.data, start, len(data), " "),
2183                             start, data)
2184
2185
2186 class StringSpans(unittest.TestCase):
2187     def do_basic(self, klass):
2188         ds = klass()
2189         self.failUnlessEqual(ds.len(), 0)
2190         self.failUnlessEqual(list(ds._dump()), [])
2191         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
2192         s1 = ds.get_spans()
2193         self.failUnlessEqual(ds.get(0, 4), None)
2194         self.failUnlessEqual(ds.pop(0, 4), None)
2195         ds.remove(0, 4)
2196
2197         ds.add(2, "four")
2198         self.failUnlessEqual(ds.len(), 4)
2199         self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
2200         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2201         s1 = ds.get_spans()
2202         self.failUnless((2,2) in s1)
2203         self.failUnlessEqual(ds.get(0, 4), None)
2204         self.failUnlessEqual(ds.pop(0, 4), None)
2205         self.failUnlessEqual(ds.get(4, 4), None)
2206
2207         ds2 = klass(ds)
2208         self.failUnlessEqual(ds2.len(), 4)
2209         self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2210         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2211         self.failUnlessEqual(ds2.get(0, 4), None)
2212         self.failUnlessEqual(ds2.pop(0, 4), None)
2213         self.failUnlessEqual(ds2.pop(2, 3), "fou")
2214         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2215         self.failUnlessEqual(ds2.get(2, 3), None)
2216         self.failUnlessEqual(ds2.get(5, 1), "r")
2217         self.failUnlessEqual(ds.get(2, 3), "fou")
2218         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2219
2220         ds.add(0, "23")
2221         self.failUnlessEqual(ds.len(), 6)
2222         self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2223         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2224         self.failUnlessEqual(ds.get(0, 4), "23fo")
2225         self.failUnlessEqual(ds.pop(0, 4), "23fo")
2226         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2227         self.failUnlessEqual(ds.get(0, 4), None)
2228         self.failUnlessEqual(ds.pop(0, 4), None)
2229
2230         ds = klass()
2231         ds.add(2, "four")
2232         ds.add(3, "ea")
2233         self.failUnlessEqual(ds.get(2, 4), "fear")
2234
2235         ds = klass()
2236         ds.add(2L, "four")
2237         ds.add(3L, "ea")
2238         self.failUnlessEqual(ds.get(2L, 4L), "fear")
2239
2240
2241     def do_scan(self, klass):
2242         # do a test with gaps and spans of size 1 and 2
2243         #  left=(1,11) * right=(1,11) * gapsize=(1,2)
2244         # 111, 112, 121, 122, 211, 212, 221, 222
2245         #    211
2246         #      121
2247         #         112
2248         #            212
2249         #               222
2250         #                   221
2251         #                      111
2252         #                        122
2253         #  11 1  1 11 11  11  1 1  111
2254         # 0123456789012345678901234567
2255         # abcdefghijklmnopqrstuvwxyz-=
2256         pieces = [(1, "bc"),
2257                   (4, "e"),
2258                   (7, "h"),
2259                   (9, "jk"),
2260                   (12, "mn"),
2261                   (16, "qr"),
2262                   (20, "u"),
2263                   (22, "w"),
2264                   (25, "z-="),
2265                   ]
2266         p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2267         S = "abcdefghijklmnopqrstuvwxyz-="
2268         # TODO: when adding data, add capital letters, to make sure we aren't
2269         # just leaving the old data in place
2270         l = len(S)
2271         def base():
2272             ds = klass()
2273             for start, data in pieces:
2274                 ds.add(start, data)
2275             return ds
2276         def dump(s):
2277             p = set(s._dump())
2278             d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2279             assert len(d) == l
2280             return d
2281         DEBUG = False
2282         for start in range(0, l):
2283             for end in range(start+1, l):
2284                 # add [start-end) to the baseline
2285                 which = "%d-%d" % (start, end-1)
2286                 p_added = set(range(start, end))
2287                 b = base()
2288                 if DEBUG:
2289                     print
2290                     print dump(b), which
2291                     add = klass(); add.add(start, S[start:end])
2292                     print dump(add)
2293                 b.add(start, S[start:end])
2294                 if DEBUG:
2295                     print dump(b)
2296                 # check that the new span is there
2297                 d = b.get(start, end-start)
2298                 self.failUnlessEqual(d, S[start:end], which)
2299                 # check that all the original pieces are still there
2300                 for t_start, t_data in pieces:
2301                     t_len = len(t_data)
2302                     self.failUnlessEqual(b.get(t_start, t_len),
2303                                          S[t_start:t_start+t_len],
2304                                          "%s %d+%d" % (which, t_start, t_len))
2305                 # check that a lot of subspans are mostly correct
2306                 for t_start in range(l):
2307                     for t_len in range(1,4):
2308                         d = b.get(t_start, t_len)
2309                         if d is not None:
2310                             which2 = "%s+(%d-%d)" % (which, t_start,
2311                                                      t_start+t_len-1)
2312                             self.failUnlessEqual(d, S[t_start:t_start+t_len],
2313                                                  which2)
2314                         # check that removing a subspan gives the right value
2315                         b2 = klass(b)
2316                         b2.remove(t_start, t_len)
2317                         removed = set(range(t_start, t_start+t_len))
2318                         for i in range(l):
2319                             exp = (((i in p_elements) or (i in p_added))
2320                                    and (i not in removed))
2321                             which2 = "%s-(%d-%d)" % (which, t_start,
2322                                                      t_start+t_len-1)
2323                             self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2324                                                  which2+" %d" % i)
2325
2326     def test_test(self):
2327         self.do_basic(SimpleDataSpans)
2328         self.do_scan(SimpleDataSpans)
2329
2330     def test_basic(self):
2331         self.do_basic(DataSpans)
2332         self.do_scan(DataSpans)
2333
2334     def test_random(self):
2335         # attempt to increase coverage of corner cases by comparing behavior
2336         # of a simple-but-slow model implementation against the
2337         # complex-but-fast actual implementation, in a large number of random
2338         # operations
2339         S1 = SimpleDataSpans
2340         S2 = DataSpans
2341         s1 = S1(); s2 = S2()
2342         seed = ""
2343         def _randstr(length, seed):
2344             created = 0
2345             pieces = []
2346             while created < length:
2347                 piece = _hash(seed + str(created)).hexdigest()
2348                 pieces.append(piece)
2349                 created += len(piece)
2350             return "".join(pieces)[:length]
2351         def _create(subseed):
2352             ns1 = S1(); ns2 = S2()
2353             for i in range(10):
2354                 what = _hash(subseed+str(i)).hexdigest()
2355                 start = int(what[2:4], 16)
2356                 length = max(1,int(what[5:6], 16))
2357                 ns1.add(start, _randstr(length, what[7:9]));
2358                 ns2.add(start, _randstr(length, what[7:9]))
2359             return ns1, ns2
2360
2361         #print
2362         for i in range(1000):
2363             what = _hash(seed+str(i)).hexdigest()
2364             op = what[0]
2365             subop = what[1]
2366             start = int(what[2:4], 16)
2367             length = max(1,int(what[5:6], 16))
2368             #print what
2369             if op in "0":
2370                 if subop in "0123456":
2371                     s1 = S1(); s2 = S2()
2372                 else:
2373                     s1, s2 = _create(what[7:11])
2374                 #print "s2 = %s" % list(s2._dump())
2375             elif op in "123456":
2376                 #print "s2.add(%d,%d)" % (start, length)
2377                 s1.add(start, _randstr(length, what[7:9]));
2378                 s2.add(start, _randstr(length, what[7:9]))
2379             elif op in "789abc":
2380                 #print "s2.remove(%d,%d)" % (start, length)
2381                 s1.remove(start, length); s2.remove(start, length)
2382             else:
2383                 #print "s2.pop(%d,%d)" % (start, length)
2384                 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2385                 self.failUnlessEqual(d1, d2)
2386             #print "s1 now %s" % list(s1._dump())
2387             #print "s2 now %s" % list(s2._dump())
2388             self.failUnlessEqual(s1.len(), s2.len())
2389             self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2390             for j in range(100):
2391                 what = _hash(what[12:14]+str(j)).hexdigest()
2392                 start = int(what[2:4], 16)
2393                 length = max(1, int(what[5:6], 16))
2394                 d1 = s1.get(start, length); d2 = s2.get(start, length)
2395                 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))