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