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