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