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