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
  19 class Base32(unittest.TestCase):
  20     def test_b2a_matches_Pythons(self):
  21         import base64
  22         y = "\x12\x34\x45\x67\x89\x0a\xbc\xde\xf0"
  23         x = base64.b32encode(y)
  24         while x and x[-1] == '=':
  25             x = x[:-1]
  26         x = x.lower()
  27         self.failUnlessEqual(base32.b2a(y), x)
  28     def test_b2a(self):
  29         self.failUnlessEqual(base32.b2a("\x12\x34"), "ci2a")
  30     def test_b2a_or_none(self):
  31         self.failUnlessEqual(base32.b2a_or_none(None), None)
  32         self.failUnlessEqual(base32.b2a_or_none("\x12\x34"), "ci2a")
  33     def test_a2b(self):
  34         self.failUnlessEqual(base32.a2b("ci2a"), "\x12\x34")
  35         self.failUnlessRaises(AssertionError, base32.a2b, "b0gus")
  36
  37 class IDLib(unittest.TestCase):
  38     def test_nodeid_b2a(self):
  39         self.failUnlessEqual(idlib.nodeid_b2a("\x00"*20), "a"*32)
  40
  41 class NoArgumentException(Exception):
  42     def __init__(self):
  43         pass
  44
  45 class HumanReadable(unittest.TestCase):
  46     def test_repr(self):
  47         hr = humanreadable.hr
  48         self.failUnlessEqual(hr(foo), "<foo() at test_util.py:2>")
  49         self.failUnlessEqual(hr(self.test_repr),
  50                              "<bound method HumanReadable.test_repr of <allmydata.test.test_util.HumanReadable testMethod=test_repr>>")
  51         self.failUnlessEqual(hr(1L), "1")
  52         self.failUnlessEqual(hr(10**40),
  53                              "100000000000000000...000000000000000000")
  54         self.failUnlessEqual(hr(self), "<allmydata.test.test_util.HumanReadable testMethod=test_repr>")
  55         self.failUnlessEqual(hr([1,2]), "[1, 2]")
  56         self.failUnlessEqual(hr({1:2}), "{1:2}")
  57         try:
  58             raise ValueError
  59         except Exception, e:
  60             self.failUnless(
  61                 hr(e) == "<ValueError: ()>" # python-2.4
  62                 or hr(e) == "ValueError()") # python-2.5
  63         try:
  64             raise ValueError("oops")
  65         except Exception, e:
  66             self.failUnless(
  67                 hr(e) == "<ValueError: 'oops'>" # python-2.4
  68                 or hr(e) == "ValueError('oops',)") # python-2.5
  69         try:
  70             raise NoArgumentException
  71         except Exception, e:
  72             self.failUnless(
  73                 hr(e) == "<NoArgumentException>" # python-2.4
  74                 or hr(e) == "NoArgumentException()") # python-2.5
  75
  76
  77 class MyList(list):
  78     pass
  79
  80 class Math(unittest.TestCase):
  81     def test_div_ceil(self):
  82         f = mathutil.div_ceil
  83         self.failUnlessEqual(f(0, 1), 0)
  84         self.failUnlessEqual(f(0, 2), 0)
  85         self.failUnlessEqual(f(0, 3), 0)
  86         self.failUnlessEqual(f(1, 3), 1)
  87         self.failUnlessEqual(f(2, 3), 1)
  88         self.failUnlessEqual(f(3, 3), 1)
  89         self.failUnlessEqual(f(4, 3), 2)
  90         self.failUnlessEqual(f(5, 3), 2)
  91         self.failUnlessEqual(f(6, 3), 2)
  92         self.failUnlessEqual(f(7, 3), 3)
  93
  94     def test_next_multiple(self):
  95         f = mathutil.next_multiple
  96         self.failUnlessEqual(f(5, 1), 5)
  97         self.failUnlessEqual(f(5, 2), 6)
  98         self.failUnlessEqual(f(5, 3), 6)
  99         self.failUnlessEqual(f(5, 4), 8)
 100         self.failUnlessEqual(f(5, 5), 5)
 101         self.failUnlessEqual(f(5, 6), 6)
 102         self.failUnlessEqual(f(32, 1), 32)
 103         self.failUnlessEqual(f(32, 2), 32)
 104         self.failUnlessEqual(f(32, 3), 33)
 105         self.failUnlessEqual(f(32, 4), 32)
 106         self.failUnlessEqual(f(32, 5), 35)
 107         self.failUnlessEqual(f(32, 6), 36)
 108         self.failUnlessEqual(f(32, 7), 35)
 109         self.failUnlessEqual(f(32, 8), 32)
 110         self.failUnlessEqual(f(32, 9), 36)
 111         self.failUnlessEqual(f(32, 10), 40)
 112         self.failUnlessEqual(f(32, 11), 33)
 113         self.failUnlessEqual(f(32, 12), 36)
 114         self.failUnlessEqual(f(32, 13), 39)
 115         self.failUnlessEqual(f(32, 14), 42)
 116         self.failUnlessEqual(f(32, 15), 45)
 117         self.failUnlessEqual(f(32, 16), 32)
 118         self.failUnlessEqual(f(32, 17), 34)
 119         self.failUnlessEqual(f(32, 18), 36)
 120         self.failUnlessEqual(f(32, 589), 589)
 121
 122     def test_pad_size(self):
 123         f = mathutil.pad_size
 124         self.failUnlessEqual(f(0, 4), 0)
 125         self.failUnlessEqual(f(1, 4), 3)
 126         self.failUnlessEqual(f(2, 4), 2)
 127         self.failUnlessEqual(f(3, 4), 1)
 128         self.failUnlessEqual(f(4, 4), 0)
 129         self.failUnlessEqual(f(5, 4), 3)
 130
 131     def test_is_power_of_k(self):
 132         f = mathutil.is_power_of_k
 133         for i in range(1, 100):
 134             if i in (1, 2, 4, 8, 16, 32, 64):
 135                 self.failUnless(f(i, 2), "but %d *is* a power of 2" % i)
 136             else:
 137                 self.failIf(f(i, 2), "but %d is *not* a power of 2" % i)
 138         for i in range(1, 100):
 139             if i in (1, 3, 9, 27, 81):
 140                 self.failUnless(f(i, 3), "but %d *is* a power of 3" % i)
 141             else:
 142                 self.failIf(f(i, 3), "but %d is *not* a power of 3" % i)
 143
 144     def test_next_power_of_k(self):
 145         f = mathutil.next_power_of_k
 146         self.failUnlessEqual(f(0,2), 1)
 147         self.failUnlessEqual(f(1,2), 1)
 148         self.failUnlessEqual(f(2,2), 2)
 149         self.failUnlessEqual(f(3,2), 4)
 150         self.failUnlessEqual(f(4,2), 4)
 151         for i in range(5, 8): self.failUnlessEqual(f(i,2), 8, "%d" % i)
 152         for i in range(9, 16): self.failUnlessEqual(f(i,2), 16, "%d" % i)
 153         for i in range(17, 32): self.failUnlessEqual(f(i,2), 32, "%d" % i)
 154         for i in range(33, 64): self.failUnlessEqual(f(i,2), 64, "%d" % i)
 155         for i in range(65, 100): self.failUnlessEqual(f(i,2), 128, "%d" % i)
 156
 157         self.failUnlessEqual(f(0,3), 1)
 158         self.failUnlessEqual(f(1,3), 1)
 159         self.failUnlessEqual(f(2,3), 3)
 160         self.failUnlessEqual(f(3,3), 3)
 161         for i in range(4, 9): self.failUnlessEqual(f(i,3), 9, "%d" % i)
 162         for i in range(10, 27): self.failUnlessEqual(f(i,3), 27, "%d" % i)
 163         for i in range(28, 81): self.failUnlessEqual(f(i,3), 81, "%d" % i)
 164         for i in range(82, 200): self.failUnlessEqual(f(i,3), 243, "%d" % i)
 165
 166     def test_ave(self):
 167         f = mathutil.ave
 168         self.failUnlessEqual(f([1,2,3]), 2)
 169         self.failUnlessEqual(f([0,0,0,4]), 1)
 170         self.failUnlessAlmostEqual(f([0.0, 1.0, 1.0]), .666666666666)
 171
 172     def test_round_sigfigs(self):
 173         f = mathutil.round_sigfigs
 174         self.failUnlessEqual(f(22.0/3, 4), 7.3330000000000002)
 175
 176 class Statistics(unittest.TestCase):
 177     def should_assert(self, msg, func, *args, **kwargs):
 178         try:
 179             func(*args, **kwargs)
 180             self.fail(msg)
 181         except AssertionError:
 182             pass
 183
 184     def failUnlessListEqual(self, a, b, msg = None):
 185         self.failUnlessEqual(len(a), len(b))
 186         for i in range(len(a)):
 187             self.failUnlessEqual(a[i], b[i], msg)
 188
 189     def failUnlessListAlmostEqual(self, a, b, places = 7, msg = None):
 190         self.failUnlessEqual(len(a), len(b))
 191         for i in range(len(a)):
 192             self.failUnlessAlmostEqual(a[i], b[i], places, msg)
 193
 194     def test_binomial_coeff(self):
 195         f = statistics.binomial_coeff
 196         self.failUnlessEqual(f(20, 0), 1)
 197         self.failUnlessEqual(f(20, 1), 20)
 198         self.failUnlessEqual(f(20, 2), 190)
 199         self.failUnlessEqual(f(20, 8), f(20, 12))
 200         self.should_assert("Should assert if n < k", f, 2, 3)
 201
 202     def test_binomial_distribution_pmf(self):
 203         f = statistics.binomial_distribution_pmf
 204
 205         pmf_comp = f(2, .1)
 206         pmf_stat = [0.81, 0.18, 0.01]
 207         self.failUnlessListAlmostEqual(pmf_comp, pmf_stat)
 208
 209         # Summing across a PMF should give the total probability 1
 210         self.failUnlessAlmostEqual(sum(pmf_comp), 1)
 211         self.should_assert("Should assert if not 0<=p<=1", f, 1, -1)
 212         self.should_assert("Should assert if n < 1", f, 0, .1)
 213
 214         out = StringIO()
 215         statistics.print_pmf(pmf_comp, out=out)
 216         lines = out.getvalue().splitlines()
 217         self.failUnlessEqual(lines[0], "i=0: 0.81")
 218         self.failUnlessEqual(lines[1], "i=1: 0.18")
 219         self.failUnlessEqual(lines[2], "i=2: 0.01")
 220
 221     def test_survival_pmf(self):
 222         f = statistics.survival_pmf
 223         # Cross-check binomial-distribution method against convolution
 224         # method.
 225         p_list = [.9999] * 100 + [.99] * 50 + [.8] * 20
 226         pmf1 = statistics.survival_pmf_via_conv(p_list)
 227         pmf2 = statistics.survival_pmf_via_bd(p_list)
 228         self.failUnlessListAlmostEqual(pmf1, pmf2)
 229         self.failUnlessTrue(statistics.valid_pmf(pmf1))
 230         self.should_assert("Should assert if p_i > 1", f, [1.1]);
 231         self.should_assert("Should assert if p_i < 0", f, [-.1]);
 232
 233     def test_repair_count_pmf(self):
 234         survival_pmf = statistics.binomial_distribution_pmf(5, .9)
 235         repair_pmf = statistics.repair_count_pmf(survival_pmf, 3)
 236         # repair_pmf[0] == sum(survival_pmf[0,1,2,5])
 237         # repair_pmf[1] == survival_pmf[4]
 238         # repair_pmf[2] = survival_pmf[3]
 239         self.failUnlessListAlmostEqual(repair_pmf,
 240                                        [0.00001 + 0.00045 + 0.0081 + 0.59049,
 241                                         .32805,
 242                                         .0729,
 243                                         0, 0, 0])
 244
 245     def test_repair_cost(self):
 246         survival_pmf = statistics.binomial_distribution_pmf(5, .9)
 247         bwcost = statistics.bandwidth_cost_function
 248         cost = statistics.mean_repair_cost(bwcost, 1000,
 249                                            survival_pmf, 3, ul_dl_ratio=1.0)
 250         self.failUnlessAlmostEqual(cost, 558.90)
 251         cost = statistics.mean_repair_cost(bwcost, 1000,
 252                                            survival_pmf, 3, ul_dl_ratio=8.0)
 253         self.failUnlessAlmostEqual(cost, 1664.55)
 254
 255         # I haven't manually checked the math beyond here -warner
 256         cost = statistics.eternal_repair_cost(bwcost, 1000,
 257                                               survival_pmf, 3,
 258                                               discount_rate=0, ul_dl_ratio=1.0)
 259         self.failUnlessAlmostEqual(cost, 65292.056074766246)
 260         cost = statistics.eternal_repair_cost(bwcost, 1000,
 261                                               survival_pmf, 3,
 262                                               discount_rate=0.05,
 263                                               ul_dl_ratio=1.0)
 264         self.failUnlessAlmostEqual(cost, 9133.6097158191551)
 265
 266     def test_convolve(self):
 267         f = statistics.convolve
 268         v1 = [ 1, 2, 3 ]
 269         v2 = [ 4, 5, 6 ]
 270         v3 = [ 7, 8 ]
 271         v1v2result = [ 4, 13, 28, 27, 18 ]
 272         # Convolution is commutative
 273         r1 = f(v1, v2)
 274         r2 = f(v2, v1)
 275         self.failUnlessListEqual(r1, r2, "Convolution should be commutative")
 276         self.failUnlessListEqual(r1, v1v2result, "Didn't match known result")
 277         # Convolution is associative
 278         r1 = f(f(v1, v2), v3)
 279         r2 = f(v1, f(v2, v3))
 280         self.failUnlessListEqual(r1, r2, "Convolution should be associative")
 281         # Convolution is distributive
 282         r1 = f(v3, [ a + b for a, b in zip(v1, v2) ])
 283         tmp1 = f(v3, v1)
 284         tmp2 = f(v3, v2)
 285         r2 = [ a + b for a, b in zip(tmp1, tmp2) ]
 286         self.failUnlessListEqual(r1, r2, "Convolution should be distributive")
 287         # Convolution is scalar multiplication associative
 288         tmp1 = f(v1, v2)
 289         r1 = [ a * 4 for a in tmp1 ]
 290         tmp2 = [ a * 4 for a in v1 ]
 291         r2 = f(tmp2, v2)
 292         self.failUnlessListEqual(r1, r2, "Convolution should be scalar multiplication associative")
 293
 294     def test_find_k(self):
 295         f = statistics.find_k
 296         g = statistics.pr_file_loss
 297         plist = [.9] * 10 + [.8] * 10 # N=20
 298         t = .0001
 299         k = f(plist, t)
 300         self.failUnlessEqual(k, 10)
 301         self.failUnless(g(plist, k) < t)
 302
 303     def test_pr_file_loss(self):
 304         f = statistics.pr_file_loss
 305         plist = [.5] * 10
 306         self.failUnlessEqual(f(plist, 3), .0546875)
 307
 308     def test_pr_backup_file_loss(self):
 309         f = statistics.pr_backup_file_loss
 310         plist = [.5] * 10
 311         self.failUnlessEqual(f(plist, .5, 3), .02734375)
 312
 313
 314 class Asserts(unittest.TestCase):
 315     def should_assert(self, func, *args, **kwargs):
 316         try:
 317             func(*args, **kwargs)
 318         except AssertionError, e:
 319             return str(e)
 320         except Exception, e:
 321             self.fail("assert failed with non-AssertionError: %s" % e)
 322         self.fail("assert was not caught")
 323
 324     def should_not_assert(self, func, *args, **kwargs):
 325         try:
 326             func(*args, **kwargs)
 327         except AssertionError, e:
 328             self.fail("assertion fired when it should not have: %s" % e)
 329         except Exception, e:
 330             self.fail("assertion (which shouldn't have failed) failed with non-AssertionError: %s" % e)
 331         return # we're happy
 332
 333
 334     def test_assert(self):
 335         f = assertutil._assert
 336         self.should_assert(f)
 337         self.should_assert(f, False)
 338         self.should_not_assert(f, True)
 339
 340         m = self.should_assert(f, False, "message")
 341         self.failUnlessEqual(m, "'message' <type 'str'>", m)
 342         m = self.should_assert(f, False, "message1", othermsg=12)
 343         self.failUnlessEqual("'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 344         m = self.should_assert(f, False, othermsg="message2")
 345         self.failUnlessEqual("othermsg: 'message2' <type 'str'>", m)
 346
 347     def test_precondition(self):
 348         f = assertutil.precondition
 349         self.should_assert(f)
 350         self.should_assert(f, False)
 351         self.should_not_assert(f, True)
 352
 353         m = self.should_assert(f, False, "message")
 354         self.failUnlessEqual("precondition: 'message' <type 'str'>", m)
 355         m = self.should_assert(f, False, "message1", othermsg=12)
 356         self.failUnlessEqual("precondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 357         m = self.should_assert(f, False, othermsg="message2")
 358         self.failUnlessEqual("precondition: othermsg: 'message2' <type 'str'>", m)
 359
 360     def test_postcondition(self):
 361         f = assertutil.postcondition
 362         self.should_assert(f)
 363         self.should_assert(f, False)
 364         self.should_not_assert(f, True)
 365
 366         m = self.should_assert(f, False, "message")
 367         self.failUnlessEqual("postcondition: 'message' <type 'str'>", m)
 368         m = self.should_assert(f, False, "message1", othermsg=12)
 369         self.failUnlessEqual("postcondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 370         m = self.should_assert(f, False, othermsg="message2")
 371         self.failUnlessEqual("postcondition: othermsg: 'message2' <type 'str'>", m)
 372
 373 class FileUtil(unittest.TestCase):
 374     def mkdir(self, basedir, path, mode=0777):
 375         fn = os.path.join(basedir, path)
 376         fileutil.make_dirs(fn, mode)
 377
 378     def touch(self, basedir, path, mode=None, data="touch\n"):
 379         fn = os.path.join(basedir, path)
 380         f = open(fn, "w")
 381         f.write(data)
 382         f.close()
 383         if mode is not None:
 384             os.chmod(fn, mode)
 385
 386     def test_rm_dir(self):
 387         basedir = "util/FileUtil/test_rm_dir"
 388         fileutil.make_dirs(basedir)
 389         # create it again to test idempotency
 390         fileutil.make_dirs(basedir)
 391         d = os.path.join(basedir, "doomed")
 392         self.mkdir(d, "a/b")
 393         self.touch(d, "a/b/1.txt")
 394         self.touch(d, "a/b/2.txt", 0444)
 395         self.touch(d, "a/b/3.txt", 0)
 396         self.mkdir(d, "a/c")
 397         self.touch(d, "a/c/1.txt")
 398         self.touch(d, "a/c/2.txt", 0444)
 399         self.touch(d, "a/c/3.txt", 0)
 400         os.chmod(os.path.join(d, "a/c"), 0444)
 401         self.mkdir(d, "a/d")
 402         self.touch(d, "a/d/1.txt")
 403         self.touch(d, "a/d/2.txt", 0444)
 404         self.touch(d, "a/d/3.txt", 0)
 405         os.chmod(os.path.join(d, "a/d"), 0)
 406
 407         fileutil.rm_dir(d)
 408         self.failIf(os.path.exists(d))
 409         # remove it again to test idempotency
 410         fileutil.rm_dir(d)
 411
 412     def test_remove_if_possible(self):
 413         basedir = "util/FileUtil/test_remove_if_possible"
 414         fileutil.make_dirs(basedir)
 415         self.touch(basedir, "here")
 416         fn = os.path.join(basedir, "here")
 417         fileutil.remove_if_possible(fn)
 418         self.failIf(os.path.exists(fn))
 419         fileutil.remove_if_possible(fn) # should be idempotent
 420         fileutil.rm_dir(basedir)
 421         fileutil.remove_if_possible(fn) # should survive errors
 422
 423     def test_write_atomically(self):
 424         basedir = "util/FileUtil/test_write_atomically"
 425         fileutil.make_dirs(basedir)
 426         fn = os.path.join(basedir, "here")
 427         fileutil.write_atomically(fn, "one")
 428         self.failUnlessEqual(fileutil.read(fn), "one")
 429         fileutil.write_atomically(fn, "two", mode="") # non-binary
 430         self.failUnlessEqual(fileutil.read(fn), "two")
 431
 432     def test_open_or_create(self):
 433         basedir = "util/FileUtil/test_open_or_create"
 434         fileutil.make_dirs(basedir)
 435         fn = os.path.join(basedir, "here")
 436         f = fileutil.open_or_create(fn)
 437         f.write("stuff.")
 438         f.close()
 439         f = fileutil.open_or_create(fn)
 440         f.seek(0, os.SEEK_END)
 441         f.write("more.")
 442         f.close()
 443         f = open(fn, "r")
 444         data = f.read()
 445         f.close()
 446         self.failUnlessEqual(data, "stuff.more.")
 447
 448     def test_NamedTemporaryDirectory(self):
 449         basedir = "util/FileUtil/test_NamedTemporaryDirectory"
 450         fileutil.make_dirs(basedir)
 451         td = fileutil.NamedTemporaryDirectory(dir=basedir)
 452         name = td.name
 453         self.failUnless(basedir in name)
 454         self.failUnless(basedir in repr(td))
 455         self.failUnless(os.path.isdir(name))
 456         del td
 457         # it is conceivable that we need to force gc here, but I'm not sure
 458         self.failIf(os.path.isdir(name))
 459
 460     def test_rename(self):
 461         basedir = "util/FileUtil/test_rename"
 462         fileutil.make_dirs(basedir)
 463         self.touch(basedir, "here")
 464         fn = os.path.join(basedir, "here")
 465         fn2 = os.path.join(basedir, "there")
 466         fileutil.rename(fn, fn2)
 467         self.failIf(os.path.exists(fn))
 468         self.failUnless(os.path.exists(fn2))
 469
 470     def test_du(self):
 471         basedir = "util/FileUtil/test_du"
 472         fileutil.make_dirs(basedir)
 473         d = os.path.join(basedir, "space-consuming")
 474         self.mkdir(d, "a/b")
 475         self.touch(d, "a/b/1.txt", data="a"*10)
 476         self.touch(d, "a/b/2.txt", data="b"*11)
 477         self.mkdir(d, "a/c")
 478         self.touch(d, "a/c/1.txt", data="c"*12)
 479         self.touch(d, "a/c/2.txt", data="d"*13)
 480
 481         used = fileutil.du(basedir)
 482         self.failUnlessEqual(10+11+12+13, used)
 483
 484     def test_abspath_expanduser_unicode(self):
 485         self.failUnlessRaises(AssertionError, fileutil.abspath_expanduser_unicode, "bytestring")
 486
 487         saved_cwd = os.path.normpath(os.getcwdu())
 488         abspath_cwd = fileutil.abspath_expanduser_unicode(u".")
 489         self.failUnless(isinstance(saved_cwd, unicode), saved_cwd)
 490         self.failUnless(isinstance(abspath_cwd, unicode), abspath_cwd)
 491         self.failUnlessEqual(abspath_cwd, saved_cwd)
 492
 493         # adapted from <http://svn.python.org/view/python/branches/release26-maint/Lib/test/test_posixpath.py?view=markup&pathrev=78279#test_abspath>
 494
 495         self.failUnlessIn(u"foo", fileutil.abspath_expanduser_unicode(u"foo"))
 496         self.failIfIn(u"~", fileutil.abspath_expanduser_unicode(u"~"))
 497
 498         cwds = ['cwd']
 499         try:
 500             cwds.append(u'\xe7w\xf0'.encode(sys.getfilesystemencoding()
 501                                             or 'ascii'))
 502         except UnicodeEncodeError:
 503             pass # the cwd can't be encoded -- test with ascii cwd only
 504
 505         for cwd in cwds:
 506             try:
 507                 os.mkdir(cwd)
 508                 os.chdir(cwd)
 509                 for upath in (u'', u'fuu', u'f\xf9\xf9', u'/fuu', u'U:\\', u'~'):
 510                     uabspath = fileutil.abspath_expanduser_unicode(upath)
 511                     self.failUnless(isinstance(uabspath, unicode), uabspath)
 512             finally:
 513                 os.chdir(saved_cwd)
 514
 515     def test_disk_stats(self):
 516         avail = fileutil.get_available_space('.', 2**14)
 517         if avail == 0:
 518             raise unittest.SkipTest("This test will spuriously fail there is no disk space left.")
 519
 520         disk = fileutil.get_disk_stats('.', 2**13)
 521         self.failUnless(disk['total'] > 0, disk['total'])
 522         # we tolerate used==0 for a Travis-CI bug, see #2290
 523         self.failUnless(disk['used'] >= 0, disk['used'])
 524         self.failUnless(disk['free_for_root'] > 0, disk['free_for_root'])
 525         self.failUnless(disk['free_for_nonroot'] > 0, disk['free_for_nonroot'])
 526         self.failUnless(disk['avail'] > 0, disk['avail'])
 527
 528     def test_disk_stats_avail_nonnegative(self):
 529         # This test will spuriously fail if you have more than 2^128
 530         # bytes of available space on your filesystem.
 531         disk = fileutil.get_disk_stats('.', 2**128)
 532         self.failUnlessEqual(disk['avail'], 0)
 533
 534 class PollMixinTests(unittest.TestCase):
 535     def setUp(self):
 536         self.pm = pollmixin.PollMixin()
 537
 538     def test_PollMixin_True(self):
 539         d = self.pm.poll(check_f=lambda : True,
 540                          pollinterval=0.1)
 541         return d
 542
 543     def test_PollMixin_False_then_True(self):
 544         i = iter([False, True])
 545         d = self.pm.poll(check_f=i.next,
 546                          pollinterval=0.1)
 547         return d
 548
 549     def test_timeout(self):
 550         d = self.pm.poll(check_f=lambda: False,
 551                          pollinterval=0.01,
 552                          timeout=1)
 553         def _suc(res):
 554             self.fail("poll should have failed, not returned %s" % (res,))
 555         def _err(f):
 556             f.trap(pollmixin.TimeoutError)
 557             return None # success
 558         d.addCallbacks(_suc, _err)
 559         return d
 560
 561 class DeferredUtilTests(unittest.TestCase):
 562     def test_gather_results(self):
 563         d1 = defer.Deferred()
 564         d2 = defer.Deferred()
 565         res = deferredutil.gatherResults([d1, d2])
 566         d1.errback(ValueError("BAD"))
 567         def _callb(res):
 568             self.fail("Should have errbacked, not resulted in %s" % (res,))
 569         def _errb(thef):
 570             thef.trap(ValueError)
 571         res.addCallbacks(_callb, _errb)
 572         return res
 573
 574     def test_success(self):
 575         d1, d2 = defer.Deferred(), defer.Deferred()
 576         good = []
 577         bad = []
 578         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 579         dlss.addCallbacks(good.append, bad.append)
 580         d1.callback(1)
 581         d2.callback(2)
 582         self.failUnlessEqual(good, [[1,2]])
 583         self.failUnlessEqual(bad, [])
 584
 585     def test_failure(self):
 586         d1, d2 = defer.Deferred(), defer.Deferred()
 587         good = []
 588         bad = []
 589         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 590         dlss.addCallbacks(good.append, bad.append)
 591         d1.addErrback(lambda _ignore: None)
 592         d2.addErrback(lambda _ignore: None)
 593         d1.callback(1)
 594         d2.errback(ValueError())
 595         self.failUnlessEqual(good, [])
 596         self.failUnlessEqual(len(bad), 1)
 597         f = bad[0]
 598         self.failUnless(isinstance(f, Failure))
 599         self.failUnless(f.check(ValueError))
 600
 601 class HashUtilTests(unittest.TestCase):
 602
 603     def test_random_key(self):
 604         k = hashutil.random_key()
 605         self.failUnlessEqual(len(k), hashutil.KEYLEN)
 606
 607     def test_sha256d(self):
 608         h1 = hashutil.tagged_hash("tag1", "value")
 609         h2 = hashutil.tagged_hasher("tag1")
 610         h2.update("value")
 611         h2a = h2.digest()
 612         h2b = h2.digest()
 613         self.failUnlessEqual(h1, h2a)
 614         self.failUnlessEqual(h2a, h2b)
 615
 616     def test_sha256d_truncated(self):
 617         h1 = hashutil.tagged_hash("tag1", "value", 16)
 618         h2 = hashutil.tagged_hasher("tag1", 16)
 619         h2.update("value")
 620         h2 = h2.digest()
 621         self.failUnlessEqual(len(h1), 16)
 622         self.failUnlessEqual(len(h2), 16)
 623         self.failUnlessEqual(h1, h2)
 624
 625     def test_chk(self):
 626         h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
 627         h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
 628         h2.update("data")
 629         h2 = h2.digest()
 630         self.failUnlessEqual(h1, h2)
 631
 632     def test_hashers(self):
 633         h1 = hashutil.block_hash("foo")
 634         h2 = hashutil.block_hasher()
 635         h2.update("foo")
 636         self.failUnlessEqual(h1, h2.digest())
 637
 638         h1 = hashutil.uri_extension_hash("foo")
 639         h2 = hashutil.uri_extension_hasher()
 640         h2.update("foo")
 641         self.failUnlessEqual(h1, h2.digest())
 642
 643         h1 = hashutil.plaintext_hash("foo")
 644         h2 = hashutil.plaintext_hasher()
 645         h2.update("foo")
 646         self.failUnlessEqual(h1, h2.digest())
 647
 648         h1 = hashutil.crypttext_hash("foo")
 649         h2 = hashutil.crypttext_hasher()
 650         h2.update("foo")
 651         self.failUnlessEqual(h1, h2.digest())
 652
 653         h1 = hashutil.crypttext_segment_hash("foo")
 654         h2 = hashutil.crypttext_segment_hasher()
 655         h2.update("foo")
 656         self.failUnlessEqual(h1, h2.digest())
 657
 658         h1 = hashutil.plaintext_segment_hash("foo")
 659         h2 = hashutil.plaintext_segment_hasher()
 660         h2.update("foo")
 661         self.failUnlessEqual(h1, h2.digest())
 662
 663     def test_timing_safe_compare(self):
 664         self.failUnless(hashutil.timing_safe_compare("a", "a"))
 665         self.failUnless(hashutil.timing_safe_compare("ab", "ab"))
 666         self.failIf(hashutil.timing_safe_compare("a", "b"))
 667         self.failIf(hashutil.timing_safe_compare("a", "aa"))
 668
 669     def _testknown(self, hashf, expected_a, *args):
 670         got = hashf(*args)
 671         got_a = base32.b2a(got)
 672         self.failUnlessEqual(got_a, expected_a)
 673
 674     def test_known_answers(self):
 675         # assert backwards compatibility
 676         self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
 677         self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
 678         self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
 679         self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
 680         self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
 681         self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
 682         self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
 683         self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
 684         self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
 685         self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
 686         self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
 687         self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
 688         self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
 689         self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
 690         self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
 691         self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
 692         self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
 693         self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
 694         self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
 695         self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
 696         self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
 697         self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
 698         self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
 699
 700
 701 class Abbreviate(unittest.TestCase):
 702     def test_time(self):
 703         a = abbreviate.abbreviate_time
 704         self.failUnlessEqual(a(None), "unknown")
 705         self.failUnlessEqual(a(0), "0 seconds")
 706         self.failUnlessEqual(a(1), "1 second")
 707         self.failUnlessEqual(a(2), "2 seconds")
 708         self.failUnlessEqual(a(119), "119 seconds")
 709         MIN = 60
 710         self.failUnlessEqual(a(2*MIN), "2 minutes")
 711         self.failUnlessEqual(a(60*MIN), "60 minutes")
 712         self.failUnlessEqual(a(179*MIN), "179 minutes")
 713         HOUR = 60*MIN
 714         self.failUnlessEqual(a(180*MIN), "3 hours")
 715         self.failUnlessEqual(a(4*HOUR), "4 hours")
 716         DAY = 24*HOUR
 717         MONTH = 30*DAY
 718         self.failUnlessEqual(a(2*DAY), "2 days")
 719         self.failUnlessEqual(a(2*MONTH), "2 months")
 720         YEAR = 365*DAY
 721         self.failUnlessEqual(a(5*YEAR), "5 years")
 722
 723     def test_space(self):
 724         tests_si = [(None, "unknown"),
 725                     (0, "0 B"),
 726                     (1, "1 B"),
 727                     (999, "999 B"),
 728                     (1000, "1000 B"),
 729                     (1023, "1023 B"),
 730                     (1024, "1.02 kB"),
 731                     (20*1000, "20.00 kB"),
 732                     (1024*1024, "1.05 MB"),
 733                     (1000*1000, "1.00 MB"),
 734                     (1000*1000*1000, "1.00 GB"),
 735                     (1000*1000*1000*1000, "1.00 TB"),
 736                     (1000*1000*1000*1000*1000, "1.00 PB"),
 737                     (1000*1000*1000*1000*1000*1000, "1.00 EB"),
 738                     (1234567890123456789, "1.23 EB"),
 739                     ]
 740         for (x, expected) in tests_si:
 741             got = abbreviate.abbreviate_space(x, SI=True)
 742             self.failUnlessEqual(got, expected)
 743
 744         tests_base1024 = [(None, "unknown"),
 745                           (0, "0 B"),
 746                           (1, "1 B"),
 747                           (999, "999 B"),
 748                           (1000, "1000 B"),
 749                           (1023, "1023 B"),
 750                           (1024, "1.00 kiB"),
 751                           (20*1024, "20.00 kiB"),
 752                           (1000*1000, "976.56 kiB"),
 753                           (1024*1024, "1.00 MiB"),
 754                           (1024*1024*1024, "1.00 GiB"),
 755                           (1024*1024*1024*1024, "1.00 TiB"),
 756                           (1000*1000*1000*1000*1000, "909.49 TiB"),
 757                           (1024*1024*1024*1024*1024, "1.00 PiB"),
 758                           (1024*1024*1024*1024*1024*1024, "1.00 EiB"),
 759                           (1234567890123456789, "1.07 EiB"),
 760                     ]
 761         for (x, expected) in tests_base1024:
 762             got = abbreviate.abbreviate_space(x, SI=False)
 763             self.failUnlessEqual(got, expected)
 764
 765         self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
 766                              "(1.23 MB, 1.18 MiB)")
 767
 768     def test_parse_space(self):
 769         p = abbreviate.parse_abbreviated_size
 770         self.failUnlessEqual(p(""), None)
 771         self.failUnlessEqual(p(None), None)
 772         self.failUnlessEqual(p("123"), 123)
 773         self.failUnlessEqual(p("123B"), 123)
 774         self.failUnlessEqual(p("2K"), 2000)
 775         self.failUnlessEqual(p("2kb"), 2000)
 776         self.failUnlessEqual(p("2KiB"), 2048)
 777         self.failUnlessEqual(p("10MB"), 10*1000*1000)
 778         self.failUnlessEqual(p("10MiB"), 10*1024*1024)
 779         self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
 780         self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
 781         self.failUnlessEqual(p("3TB"), 3*1000*1000*1000*1000)
 782         self.failUnlessEqual(p("3TiB"), 3*1024*1024*1024*1024)
 783         self.failUnlessEqual(p("6PB"), 6*1000*1000*1000*1000*1000)
 784         self.failUnlessEqual(p("6PiB"), 6*1024*1024*1024*1024*1024)
 785         self.failUnlessEqual(p("9EB"), 9*1000*1000*1000*1000*1000*1000)
 786         self.failUnlessEqual(p("9EiB"), 9*1024*1024*1024*1024*1024*1024)
 787
 788         e = self.failUnlessRaises(ValueError, p, "12 cubits")
 789         self.failUnlessIn("12 cubits", str(e))
 790         e = self.failUnlessRaises(ValueError, p, "1 BB")
 791         self.failUnlessIn("1 BB", str(e))
 792         e = self.failUnlessRaises(ValueError, p, "fhtagn")
 793         self.failUnlessIn("fhtagn", str(e))
 794
 795 class Limiter(unittest.TestCase):
 796     timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
 797
 798     def job(self, i, foo):
 799         self.calls.append( (i, foo) )
 800         self.simultaneous += 1
 801         self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
 802         d = defer.Deferred()
 803         def _done():
 804             self.simultaneous -= 1
 805             d.callback("done %d" % i)
 806         reactor.callLater(1.0, _done)
 807         return d
 808
 809     def bad_job(self, i, foo):
 810         raise ValueError("bad_job %d" % i)
 811
 812     def test_limiter(self):
 813         self.calls = []
 814         self.simultaneous = 0
 815         self.peak_simultaneous = 0
 816         l = limiter.ConcurrencyLimiter()
 817         dl = []
 818         for i in range(20):
 819             dl.append(l.add(self.job, i, foo=str(i)))
 820         d = defer.DeferredList(dl, fireOnOneErrback=True)
 821         def _done(res):
 822             self.failUnlessEqual(self.simultaneous, 0)
 823             self.failUnless(self.peak_simultaneous <= 10)
 824             self.failUnlessEqual(len(self.calls), 20)
 825             for i in range(20):
 826                 self.failUnless( (i, str(i)) in self.calls)
 827         d.addCallback(_done)
 828         return d
 829
 830     def test_errors(self):
 831         self.calls = []
 832         self.simultaneous = 0
 833         self.peak_simultaneous = 0
 834         l = limiter.ConcurrencyLimiter()
 835         dl = []
 836         for i in range(20):
 837             dl.append(l.add(self.job, i, foo=str(i)))
 838         d2 = l.add(self.bad_job, 21, "21")
 839         d = defer.DeferredList(dl, fireOnOneErrback=True)
 840         def _most_done(res):
 841             results = []
 842             for (success, result) in res:
 843                 self.failUnlessEqual(success, True)
 844                 results.append(result)
 845             results.sort()
 846             expected_results = ["done %d" % i for i in range(20)]
 847             expected_results.sort()
 848             self.failUnlessEqual(results, expected_results)
 849             self.failUnless(self.peak_simultaneous <= 10)
 850             self.failUnlessEqual(len(self.calls), 20)
 851             for i in range(20):
 852                 self.failUnless( (i, str(i)) in self.calls)
 853             def _good(res):
 854                 self.fail("should have failed, not got %s" % (res,))
 855             def _err(f):
 856                 f.trap(ValueError)
 857                 self.failUnless("bad_job 21" in str(f))
 858             d2.addCallbacks(_good, _err)
 859             return d2
 860         d.addCallback(_most_done)
 861         def _all_done(res):
 862             self.failUnlessEqual(self.simultaneous, 0)
 863             self.failUnless(self.peak_simultaneous <= 10)
 864             self.failUnlessEqual(len(self.calls), 20)
 865             for i in range(20):
 866                 self.failUnless( (i, str(i)) in self.calls)
 867         d.addCallback(_all_done)
 868         return d
 869
 870 class TimeFormat(unittest.TestCase):
 871     def test_epoch(self):
 872         return self._help_test_epoch()
 873
 874     def test_epoch_in_London(self):
 875         # Europe/London is a particularly troublesome timezone.  Nowadays, its
 876         # offset from GMT is 0.  But in 1970, its offset from GMT was 1.
 877         # (Apparently in 1970 Britain had redefined standard time to be GMT+1
 878         # and stayed in standard time all year round, whereas today
 879         # Europe/London standard time is GMT and Europe/London Daylight
 880         # Savings Time is GMT+1.)  The current implementation of
 881         # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
 882         # Europe/London.  (As soon as this unit test is done then I'll change
 883         # that implementation to something that works even in this case...)
 884         origtz = os.environ.get('TZ')
 885         os.environ['TZ'] = "Europe/London"
 886         if hasattr(time, 'tzset'):
 887             time.tzset()
 888         try:
 889             return self._help_test_epoch()
 890         finally:
 891             if origtz is None:
 892                 del os.environ['TZ']
 893             else:
 894                 os.environ['TZ'] = origtz
 895             if hasattr(time, 'tzset'):
 896                 time.tzset()
 897
 898     def _help_test_epoch(self):
 899         origtzname = time.tzname
 900         s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
 901         self.failUnlessEqual(s, 1.0)
 902         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
 903         self.failUnlessEqual(s, 1.0)
 904         s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
 905         self.failUnlessEqual(s, 1.0)
 906
 907         self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
 908         self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
 909                              "1970-01-01 00:00:01")
 910
 911         now = time.time()
 912         isostr = time_format.iso_utc(now)
 913         timestamp = time_format.iso_utc_time_to_seconds(isostr)
 914         self.failUnlessEqual(int(timestamp), int(now))
 915
 916         def my_time():
 917             return 1.0
 918         self.failUnlessEqual(time_format.iso_utc(t=my_time),
 919                              "1970-01-01_00:00:01")
 920         e = self.failUnlessRaises(ValueError,
 921                                   time_format.iso_utc_time_to_seconds,
 922                                   "invalid timestring")
 923         self.failUnless("not a complete ISO8601 timestamp" in str(e))
 924         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
 925         self.failUnlessEqual(s, 1.5)
 926
 927         # Look for daylight-savings-related errors.
 928         thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
 929         self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
 930         self.failUnlessEqual(origtzname, time.tzname)
 931
 932     def test_iso_utc(self):
 933         when = 1266760143.7841301
 934         out = time_format.iso_utc_date(when)
 935         self.failUnlessEqual(out, "2010-02-21")
 936         out = time_format.iso_utc_date(t=lambda: when)
 937         self.failUnlessEqual(out, "2010-02-21")
 938         out = time_format.iso_utc(when)
 939         self.failUnlessEqual(out, "2010-02-21_13:49:03.784130")
 940         out = time_format.iso_utc(when, sep="-")
 941         self.failUnlessEqual(out, "2010-02-21-13:49:03.784130")
 942
 943     def test_parse_duration(self):
 944         p = time_format.parse_duration
 945         DAY = 24*60*60
 946         self.failUnlessEqual(p("1 day"), DAY)
 947         self.failUnlessEqual(p("2 days"), 2*DAY)
 948         self.failUnlessEqual(p("3 months"), 3*31*DAY)
 949         self.failUnlessEqual(p("4 mo"), 4*31*DAY)
 950         self.failUnlessEqual(p("5 years"), 5*365*DAY)
 951         e = self.failUnlessRaises(ValueError, p, "123")
 952         self.failUnlessIn("no unit (like day, month, or year) in '123'",
 953                           str(e))
 954
 955     def test_parse_date(self):
 956         self.failUnlessEqual(time_format.parse_date("2010-02-21"), 1266710400)
 957
 958     def test_format_delta(self):
 959         time_1 = 1389812723
 960         time_5s_delta = 1389812728
 961         time_28m7s_delta = 1389814410
 962         time_1h_delta = 1389816323
 963         time_1d21h46m49s_delta = 1389977532
 964         TIME_FORMAT = "%H:%M:%S %d-%b-%Y"
 965         time_1_isostr = time.strftime(TIME_FORMAT, time.localtime(time_1))
 966
 967         self.failUnlessEqual(
 968             time_format.format_delta(time_1, time_5s_delta),
 969             (time_1_isostr, '5s'))
 970         self.failUnlessEqual(
 971             time_format.format_delta(time_1, time_28m7s_delta),
 972             (time_1_isostr, '28m7s'))
 973         self.failUnlessEqual(
 974             time_format.format_delta(time_1, time_1h_delta),
 975             (time_1_isostr, '1h0m0s'))
 976         self.failUnlessEqual(
 977             time_format.format_delta(time_1, time_1d21h46m49s_delta),
 978             (time_1_isostr, '1d21h46m49s'))
 979
 980         # time_1 with a decimal fraction will make the delta 1s less
 981         time_1decimal = 1389812723.383963
 982
 983         self.failUnlessEqual(
 984             time_format.format_delta(time_1decimal, time_5s_delta),
 985             (time_1_isostr, '4s'))
 986         self.failUnlessEqual(
 987             time_format.format_delta(time_1decimal, time_28m7s_delta),
 988             (time_1_isostr, '28m6s'))
 989         self.failUnlessEqual(
 990             time_format.format_delta(time_1decimal, time_1h_delta),
 991             (time_1_isostr, '59m59s'))
 992         self.failUnlessEqual(
 993             time_format.format_delta(time_1decimal, time_1d21h46m49s_delta),
 994             (time_1_isostr, '1d21h46m48s'))
 995
 996 class CacheDir(unittest.TestCase):
 997     def test_basic(self):
 998         basedir = "test_util/CacheDir/test_basic"
 999
1000         def _failIfExists(name):
1001             absfn = os.path.join(basedir, name)
1002             self.failIf(os.path.exists(absfn),
1003                         "%s exists but it shouldn't" % absfn)
1004
1005         def _failUnlessExists(name):
1006             absfn = os.path.join(basedir, name)
1007             self.failUnless(os.path.exists(absfn),
1008                             "%s doesn't exist but it should" % absfn)
1009
1010         cdm = cachedir.CacheDirectoryManager(basedir)
1011         a = cdm.get_file("a")
1012         b = cdm.get_file("b")
1013         c = cdm.get_file("c")
1014         f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
1015         f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
1016         f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
1017
1018         _failUnlessExists("a")
1019         _failUnlessExists("b")
1020         _failUnlessExists("c")
1021
1022         cdm.check()
1023
1024         _failUnlessExists("a")
1025         _failUnlessExists("b")
1026         _failUnlessExists("c")
1027
1028         del a
1029         # this file won't be deleted yet, because it isn't old enough
1030         cdm.check()
1031         _failUnlessExists("a")
1032         _failUnlessExists("b")
1033         _failUnlessExists("c")
1034
1035         # we change the definition of "old" to make everything old
1036         cdm.old = -10
1037
1038         cdm.check()
1039         _failIfExists("a")
1040         _failUnlessExists("b")
1041         _failUnlessExists("c")
1042
1043         cdm.old = 60*60
1044
1045         del b
1046
1047         cdm.check()
1048         _failIfExists("a")
1049         _failUnlessExists("b")
1050         _failUnlessExists("c")
1051
1052         b2 = cdm.get_file("b")
1053
1054         cdm.check()
1055         _failIfExists("a")
1056         _failUnlessExists("b")
1057         _failUnlessExists("c")
1058         del b2
1059
1060 ctr = [0]
1061 class EqButNotIs:
1062     def __init__(self, x):
1063         self.x = x
1064         self.hash = ctr[0]
1065         ctr[0] += 1
1066     def __repr__(self):
1067         return "<%s %s>" % (self.__class__.__name__, self.x,)
1068     def __hash__(self):
1069         return self.hash
1070     def __le__(self, other):
1071         return self.x <= other
1072     def __lt__(self, other):
1073         return self.x < other
1074     def __ge__(self, other):
1075         return self.x >= other
1076     def __gt__(self, other):
1077         return self.x > other
1078     def __ne__(self, other):
1079         return self.x != other
1080     def __eq__(self, other):
1081         return self.x == other
1082
1083 class DictUtil(unittest.TestCase):
1084     def _help_test_empty_dict(self, klass):
1085         d1 = klass()
1086         d2 = klass({})
1087
1088         self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
1089         self.failUnless(len(d1) == 0)
1090         self.failUnless(len(d2) == 0)
1091
1092     def _help_test_nonempty_dict(self, klass):
1093         d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1094         d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
1095
1096         self.failUnless(d1 == d2)
1097         self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
1098         self.failUnless(len(d2) == 3)
1099
1100     def _help_test_eq_but_notis(self, klass):
1101         d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
1102         d.pop('b')
1103
1104         d.clear()
1105         d['a'] = 3
1106         d['b'] = EqButNotIs(3)
1107         d['c'] = 3
1108         d.pop('b')
1109
1110         d.clear()
1111         d['b'] = EqButNotIs(3)
1112         d['a'] = 3
1113         d['c'] = 3
1114         d.pop('b')
1115
1116         d.clear()
1117         d['a'] = EqButNotIs(3)
1118         d['c'] = 3
1119         d['a'] = 3
1120
1121         d.clear()
1122         fake3 = EqButNotIs(3)
1123         fake7 = EqButNotIs(7)
1124         d[fake3] = fake7
1125         d[3] = 7
1126         d[3] = 8
1127         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1128         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1129         # The real 7 should have been ejected by the d[3] = 8.
1130         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1131         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1132         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1133         d[fake3] = 8
1134
1135         d.clear()
1136         d[3] = 7
1137         fake3 = EqButNotIs(3)
1138         fake7 = EqButNotIs(7)
1139         d[fake3] = fake7
1140         d[3] = 8
1141         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1142         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1143         # The real 7 should have been ejected by the d[3] = 8.
1144         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1145         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1146         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1147         d[fake3] = 8
1148
1149     def test_all(self):
1150         self._help_test_eq_but_notis(dictutil.UtilDict)
1151         self._help_test_eq_but_notis(dictutil.NumDict)
1152         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1153         self._help_test_nonempty_dict(dictutil.UtilDict)
1154         self._help_test_nonempty_dict(dictutil.NumDict)
1155         self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1156         self._help_test_eq_but_notis(dictutil.UtilDict)
1157         self._help_test_eq_but_notis(dictutil.NumDict)
1158         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1159
1160     def test_dict_of_sets(self):
1161         ds = dictutil.DictOfSets()
1162         ds.add(1, "a")
1163         ds.add(2, "b")
1164         ds.add(2, "b")
1165         ds.add(2, "c")
1166         self.failUnlessEqual(ds[1], set(["a"]))
1167         self.failUnlessEqual(ds[2], set(["b", "c"]))
1168         ds.discard(3, "d") # should not raise an exception
1169         ds.discard(2, "b")
1170         self.failUnlessEqual(ds[2], set(["c"]))
1171         ds.discard(2, "c")
1172         self.failIf(2 in ds)
1173
1174         ds.add(3, "f")
1175         ds2 = dictutil.DictOfSets()
1176         ds2.add(3, "f")
1177         ds2.add(3, "g")
1178         ds2.add(4, "h")
1179         ds.update(ds2)
1180         self.failUnlessEqual(ds[1], set(["a"]))
1181         self.failUnlessEqual(ds[3], set(["f", "g"]))
1182         self.failUnlessEqual(ds[4], set(["h"]))
1183
1184     def test_move(self):
1185         d1 = {1: "a", 2: "b"}
1186         d2 = {2: "c", 3: "d"}
1187         dictutil.move(1, d1, d2)
1188         self.failUnlessEqual(d1, {2: "b"})
1189         self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1190
1191         d1 = {1: "a", 2: "b"}
1192         d2 = {2: "c", 3: "d"}
1193         dictutil.move(2, d1, d2)
1194         self.failUnlessEqual(d1, {1: "a"})
1195         self.failUnlessEqual(d2, {2: "b", 3: "d"})
1196
1197         d1 = {1: "a", 2: "b"}
1198         d2 = {2: "c", 3: "d"}
1199         self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1200
1201     def test_subtract(self):
1202         d1 = {1: "a", 2: "b"}
1203         d2 = {2: "c", 3: "d"}
1204         d3 = dictutil.subtract(d1, d2)
1205         self.failUnlessEqual(d3, {1: "a"})
1206
1207         d1 = {1: "a", 2: "b"}
1208         d2 = {2: "c"}
1209         d3 = dictutil.subtract(d1, d2)
1210         self.failUnlessEqual(d3, {1: "a"})
1211
1212     def test_utildict(self):
1213         d = dictutil.UtilDict({1: "a", 2: "b"})
1214         d.del_if_present(1)
1215         d.del_if_present(3)
1216         self.failUnlessEqual(d, {2: "b"})
1217         def eq(a, b):
1218             return a == b
1219         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1220
1221         d = dictutil.UtilDict({1: "b", 2: "a"})
1222         self.failUnlessEqual(d.items_sorted_by_value(),
1223                              [(2, "a"), (1, "b")])
1224         self.failUnlessEqual(d.items_sorted_by_key(),
1225                              [(1, "b"), (2, "a")])
1226         self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1227         self.failUnless(1 in d)
1228
1229         d2 = dictutil.UtilDict({3: "c", 4: "d"})
1230         self.failUnless(d != d2)
1231         self.failUnless(d2 > d)
1232         self.failUnless(d2 >= d)
1233         self.failUnless(d <= d2)
1234         self.failUnless(d < d2)
1235         self.failUnlessEqual(d[1], "b")
1236         self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1237
1238         d3 = d.copy()
1239         self.failUnlessEqual(d, d3)
1240         self.failUnless(isinstance(d3, dictutil.UtilDict))
1241
1242         d4 = d.fromkeys([3,4], "e")
1243         self.failUnlessEqual(d4, {3: "e", 4: "e"})
1244
1245         self.failUnlessEqual(d.get(1), "b")
1246         self.failUnlessEqual(d.get(3), None)
1247         self.failUnlessEqual(d.get(3, "default"), "default")
1248         self.failUnlessEqual(sorted(list(d.items())),
1249                              [(1, "b"), (2, "a")])
1250         self.failUnlessEqual(sorted(list(d.iteritems())),
1251                              [(1, "b"), (2, "a")])
1252         self.failUnlessEqual(sorted(d.keys()), [1, 2])
1253         self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1254         x = d.setdefault(1, "new")
1255         self.failUnlessEqual(x, "b")
1256         self.failUnlessEqual(d[1], "b")
1257         x = d.setdefault(3, "new")
1258         self.failUnlessEqual(x, "new")
1259         self.failUnlessEqual(d[3], "new")
1260         del d[3]
1261
1262         x = d.popitem()
1263         self.failUnless(x in [(1, "b"), (2, "a")])
1264         x = d.popitem()
1265         self.failUnless(x in [(1, "b"), (2, "a")])
1266         self.failUnlessRaises(KeyError, d.popitem)
1267
1268     def test_numdict(self):
1269         d = dictutil.NumDict({"a": 1, "b": 2})
1270
1271         d.add_num("a", 10, 5)
1272         d.add_num("c", 20, 5)
1273         d.add_num("d", 30)
1274         self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1275
1276         d.subtract_num("a", 10)
1277         d.subtract_num("e", 10)
1278         d.subtract_num("f", 10, 15)
1279         self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1280                                  "e": -10, "f": 5})
1281
1282         self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1283
1284         d = dictutil.NumDict()
1285         d.inc("a")
1286         d.inc("a")
1287         d.inc("b", 5)
1288         self.failUnlessEqual(d, {"a": 2, "b": 6})
1289         d.dec("a")
1290         d.dec("c")
1291         d.dec("d", 5)
1292         self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1293         self.failUnlessEqual(d.items_sorted_by_key(),
1294                              [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1295         self.failUnlessEqual(d.items_sorted_by_value(),
1296                              [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1297         self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1298
1299         d = dictutil.NumDict({"a": 1, "b": 2})
1300         self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1301         self.failUnless("a" in d)
1302
1303         d2 = dictutil.NumDict({"c": 3, "d": 4})
1304         self.failUnless(d != d2)
1305         self.failUnless(d2 > d)
1306         self.failUnless(d2 >= d)
1307         self.failUnless(d <= d2)
1308         self.failUnless(d < d2)
1309         self.failUnlessEqual(d["a"], 1)
1310         self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1311         def eq(a, b):
1312             return a == b
1313         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1314
1315         d3 = d.copy()
1316         self.failUnlessEqual(d, d3)
1317         self.failUnless(isinstance(d3, dictutil.NumDict))
1318
1319         d4 = d.fromkeys(["a","b"], 5)
1320         self.failUnlessEqual(d4, {"a": 5, "b": 5})
1321
1322         self.failUnlessEqual(d.get("a"), 1)
1323         self.failUnlessEqual(d.get("c"), 0)
1324         self.failUnlessEqual(d.get("c", 5), 5)
1325         self.failUnlessEqual(sorted(list(d.items())),
1326                              [("a", 1), ("b", 2)])
1327         self.failUnlessEqual(sorted(list(d.iteritems())),
1328                              [("a", 1), ("b", 2)])
1329         self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1330         self.failUnlessEqual(sorted(d.values()), [1, 2])
1331         self.failUnless(d.has_key("a"))
1332         self.failIf(d.has_key("c"))
1333
1334         x = d.setdefault("c", 3)
1335         self.failUnlessEqual(x, 3)
1336         self.failUnlessEqual(d["c"], 3)
1337         x = d.setdefault("c", 5)
1338         self.failUnlessEqual(x, 3)
1339         self.failUnlessEqual(d["c"], 3)
1340         del d["c"]
1341
1342         x = d.popitem()
1343         self.failUnless(x in [("a", 1), ("b", 2)])
1344         x = d.popitem()
1345         self.failUnless(x in [("a", 1), ("b", 2)])
1346         self.failUnlessRaises(KeyError, d.popitem)
1347
1348         d.update({"c": 3})
1349         d.update({"c": 4, "d": 5})
1350         self.failUnlessEqual(d, {"c": 4, "d": 5})
1351
1352     def test_del_if_present(self):
1353         d = {1: "a", 2: "b"}
1354         dictutil.del_if_present(d, 1)
1355         dictutil.del_if_present(d, 3)
1356         self.failUnlessEqual(d, {2: "b"})
1357
1358     def test_valueordereddict(self):
1359         d = dictutil.ValueOrderedDict()
1360         d["a"] = 3
1361         d["b"] = 2
1362         d["c"] = 1
1363
1364         self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1365         self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1366         self.failUnlessEqual(d.values(), [1, 2, 3])
1367         self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1368         self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1369         def eq(a, b):
1370             return a == b
1371         self.failIf(d == {"a": 4})
1372         self.failUnless(d != {"a": 4})
1373
1374         x = d.setdefault("d", 0)
1375         self.failUnlessEqual(x, 0)
1376         self.failUnlessEqual(d["d"], 0)
1377         x = d.setdefault("d", -1)
1378         self.failUnlessEqual(x, 0)
1379         self.failUnlessEqual(d["d"], 0)
1380
1381         x = d.remove("e", "default", False)
1382         self.failUnlessEqual(x, "default")
1383         self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1384         x = d.remove("d", 5)
1385         self.failUnlessEqual(x, 0)
1386
1387         x = d.__getitem__("c")
1388         self.failUnlessEqual(x, 1)
1389         x = d.__getitem__("e", "default", False)
1390         self.failUnlessEqual(x, "default")
1391         self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1392
1393         self.failUnlessEqual(d.popitem(), ("c", 1))
1394         self.failUnlessEqual(d.popitem(), ("b", 2))
1395         self.failUnlessEqual(d.popitem(), ("a", 3))
1396         self.failUnlessRaises(KeyError, d.popitem)
1397
1398         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1399         x = d.pop("d", "default", False)
1400         self.failUnlessEqual(x, "default")
1401         self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1402         x = d.pop("b")
1403         self.failUnlessEqual(x, 2)
1404         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1405
1406         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1407         x = d.pop_from_list(1) # pop the second item, b/2
1408         self.failUnlessEqual(x, "b")
1409         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1410
1411     def test_auxdict(self):
1412         d = dictutil.AuxValueDict()
1413         # we put the serialized form in the auxdata
1414         d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1415
1416         self.failUnlessEqual(d.keys(), ["key"])
1417         self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1418         self.failUnlessEqual(d.get_aux("key"), "serialized")
1419         def _get_missing(key):
1420             return d[key]
1421         self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1422         self.failUnlessEqual(d.get("nonkey"), None)
1423         self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1424         self.failUnlessEqual(d.get_aux("nonkey"), None)
1425         self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1426
1427         d["key"] = ("filecap2", "metadata2")
1428         self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1429         self.failUnlessEqual(d.get_aux("key"), None)
1430
1431         d.set_with_aux("key2", "value2", "aux2")
1432         self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1433         del d["key2"]
1434         self.failUnlessEqual(d.keys(), ["key"])
1435         self.failIf("key2" in d)
1436         self.failUnlessRaises(KeyError, _get_missing, "key2")
1437         self.failUnlessEqual(d.get("key2"), None)
1438         self.failUnlessEqual(d.get_aux("key2"), None)
1439         d["key2"] = "newvalue2"
1440         self.failUnlessEqual(d.get("key2"), "newvalue2")
1441         self.failUnlessEqual(d.get_aux("key2"), None)
1442
1443         d = dictutil.AuxValueDict({1:2,3:4})
1444         self.failUnlessEqual(sorted(d.keys()), [1,3])
1445         self.failUnlessEqual(d[1], 2)
1446         self.failUnlessEqual(d.get_aux(1), None)
1447
1448         d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1449         self.failUnlessEqual(sorted(d.keys()), [1,3])
1450         self.failUnlessEqual(d[1], 2)
1451         self.failUnlessEqual(d.get_aux(1), None)
1452
1453         d = dictutil.AuxValueDict(one=1, two=2)
1454         self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1455         self.failUnlessEqual(d["one"], 1)
1456         self.failUnlessEqual(d.get_aux("one"), None)
1457
1458 class Pipeline(unittest.TestCase):
1459     def pause(self, *args, **kwargs):
1460         d = defer.Deferred()
1461         self.calls.append( (d, args, kwargs) )
1462         return d
1463
1464     def failUnlessCallsAre(self, expected):
1465         #print self.calls
1466         #print expected
1467         self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1468         for i,c in enumerate(self.calls):
1469             self.failUnlessEqual(c[1:], expected[i], str(i))
1470
1471     def test_basic(self):
1472         self.calls = []
1473         finished = []
1474         p = pipeline.Pipeline(100)
1475
1476         d = p.flush() # fires immediately
1477         d.addCallbacks(finished.append, log.err)
1478         self.failUnlessEqual(len(finished), 1)
1479         finished = []
1480
1481         d = p.add(10, self.pause, "one")
1482         # the call should start right away, and our return Deferred should
1483         # fire right away
1484         d.addCallbacks(finished.append, log.err)
1485         self.failUnlessEqual(len(finished), 1)
1486         self.failUnlessEqual(finished[0], None)
1487         self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1488         self.failUnlessEqual(p.gauge, 10)
1489
1490         # pipeline: [one]
1491
1492         finished = []
1493         d = p.add(20, self.pause, "two", kw=2)
1494         # pipeline: [one, two]
1495
1496         # the call and the Deferred should fire right away
1497         d.addCallbacks(finished.append, log.err)
1498         self.failUnlessEqual(len(finished), 1)
1499         self.failUnlessEqual(finished[0], None)
1500         self.failUnlessCallsAre([ ( ("one",) , {} ),
1501                                   ( ("two",) , {"kw": 2} ),
1502                                   ])
1503         self.failUnlessEqual(p.gauge, 30)
1504
1505         self.calls[0][0].callback("one-result")
1506         # pipeline: [two]
1507         self.failUnlessEqual(p.gauge, 20)
1508
1509         finished = []
1510         d = p.add(90, self.pause, "three", "posarg1")
1511         # pipeline: [two, three]
1512         flushed = []
1513         fd = p.flush()
1514         fd.addCallbacks(flushed.append, log.err)
1515         self.failUnlessEqual(flushed, [])
1516
1517         # the call will be made right away, but the return Deferred will not,
1518         # because the pipeline is now full.
1519         d.addCallbacks(finished.append, log.err)
1520         self.failUnlessEqual(len(finished), 0)
1521         self.failUnlessCallsAre([ ( ("one",) , {} ),
1522                                   ( ("two",) , {"kw": 2} ),
1523                                   ( ("three", "posarg1"), {} ),
1524                                   ])
1525         self.failUnlessEqual(p.gauge, 110)
1526
1527         self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1528
1529         # retiring either call will unblock the pipeline, causing the #3
1530         # Deferred to fire
1531         self.calls[2][0].callback("three-result")
1532         # pipeline: [two]
1533
1534         self.failUnlessEqual(len(finished), 1)
1535         self.failUnlessEqual(finished[0], None)
1536         self.failUnlessEqual(flushed, [])
1537
1538         # retiring call#2 will finally allow the flush() Deferred to fire
1539         self.calls[1][0].callback("two-result")
1540         self.failUnlessEqual(len(flushed), 1)
1541
1542     def test_errors(self):
1543         self.calls = []
1544         p = pipeline.Pipeline(100)
1545
1546         d1 = p.add(200, self.pause, "one")
1547         d2 = p.flush()
1548
1549         finished = []
1550         d1.addBoth(finished.append)
1551         self.failUnlessEqual(finished, [])
1552
1553         flushed = []
1554         d2.addBoth(flushed.append)
1555         self.failUnlessEqual(flushed, [])
1556
1557         self.calls[0][0].errback(ValueError("oops"))
1558
1559         self.failUnlessEqual(len(finished), 1)
1560         f = finished[0]
1561         self.failUnless(isinstance(f, Failure))
1562         self.failUnless(f.check(pipeline.PipelineError))
1563         self.failUnlessIn("PipelineError", str(f.value))
1564         self.failUnlessIn("ValueError", str(f.value))
1565         r = repr(f.value)
1566         self.failUnless("ValueError" in r, r)
1567         f2 = f.value.error
1568         self.failUnless(f2.check(ValueError))
1569
1570         self.failUnlessEqual(len(flushed), 1)
1571         f = flushed[0]
1572         self.failUnless(isinstance(f, Failure))
1573         self.failUnless(f.check(pipeline.PipelineError))
1574         f2 = f.value.error
1575         self.failUnless(f2.check(ValueError))
1576
1577         # now that the pipeline is in the failed state, any new calls will
1578         # fail immediately
1579
1580         d3 = p.add(20, self.pause, "two")
1581
1582         finished = []
1583         d3.addBoth(finished.append)
1584         self.failUnlessEqual(len(finished), 1)
1585         f = finished[0]
1586         self.failUnless(isinstance(f, Failure))
1587         self.failUnless(f.check(pipeline.PipelineError))
1588         r = repr(f.value)
1589         self.failUnless("ValueError" in r, r)
1590         f2 = f.value.error
1591         self.failUnless(f2.check(ValueError))
1592
1593         d4 = p.flush()
1594         flushed = []
1595         d4.addBoth(flushed.append)
1596         self.failUnlessEqual(len(flushed), 1)
1597         f = flushed[0]
1598         self.failUnless(isinstance(f, Failure))
1599         self.failUnless(f.check(pipeline.PipelineError))
1600         f2 = f.value.error
1601         self.failUnless(f2.check(ValueError))
1602
1603     def test_errors2(self):
1604         self.calls = []
1605         p = pipeline.Pipeline(100)
1606
1607         d1 = p.add(10, self.pause, "one")
1608         d2 = p.add(20, self.pause, "two")
1609         d3 = p.add(30, self.pause, "three")
1610         d4 = p.flush()
1611
1612         # one call fails, then the second one succeeds: make sure
1613         # ExpandableDeferredList tolerates the second one
1614
1615         flushed = []
1616         d4.addBoth(flushed.append)
1617         self.failUnlessEqual(flushed, [])
1618
1619         self.calls[0][0].errback(ValueError("oops"))
1620         self.failUnlessEqual(len(flushed), 1)
1621         f = flushed[0]
1622         self.failUnless(isinstance(f, Failure))
1623         self.failUnless(f.check(pipeline.PipelineError))
1624         f2 = f.value.error
1625         self.failUnless(f2.check(ValueError))
1626
1627         self.calls[1][0].callback("two-result")
1628         self.calls[2][0].errback(ValueError("three-error"))
1629
1630         del d1,d2,d3,d4
1631
1632 class SampleError(Exception):
1633     pass
1634
1635 class Log(unittest.TestCase):
1636     def test_err(self):
1637         if not hasattr(self, "flushLoggedErrors"):
1638             # without flushLoggedErrors, we can't get rid of the
1639             # twisted.log.err that tahoe_log records, so we can't keep this
1640             # test from [ERROR]ing
1641             raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1642         try:
1643             raise SampleError("simple sample")
1644         except:
1645             f = Failure()
1646         tahoe_log.err(format="intentional sample error",
1647                       failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1648         self.flushLoggedErrors(SampleError)
1649
1650
1651 class SimpleSpans:
1652     # this is a simple+inefficient form of util.spans.Spans . We compare the
1653     # behavior of this reference model against the real (efficient) form.
1654
1655     def __init__(self, _span_or_start=None, length=None):
1656         self._have = set()
1657         if length is not None:
1658             for i in range(_span_or_start, _span_or_start+length):
1659                 self._have.add(i)
1660         elif _span_or_start:
1661             for (start,length) in _span_or_start:
1662                 self.add(start, length)
1663
1664     def add(self, start, length):
1665         for i in range(start, start+length):
1666             self._have.add(i)
1667         return self
1668
1669     def remove(self, start, length):
1670         for i in range(start, start+length):
1671             self._have.discard(i)
1672         return self
1673
1674     def each(self):
1675         return sorted(self._have)
1676
1677     def __iter__(self):
1678         items = sorted(self._have)
1679         prevstart = None
1680         prevend = None
1681         for i in items:
1682             if prevstart is None:
1683                 prevstart = prevend = i
1684                 continue
1685             if i == prevend+1:
1686                 prevend = i
1687                 continue
1688             yield (prevstart, prevend-prevstart+1)
1689             prevstart = prevend = i
1690         if prevstart is not None:
1691             yield (prevstart, prevend-prevstart+1)
1692
1693     def __nonzero__(self): # this gets us bool()
1694         return self.len()
1695
1696     def len(self):
1697         return len(self._have)
1698
1699     def __add__(self, other):
1700         s = self.__class__(self)
1701         for (start, length) in other:
1702             s.add(start, length)
1703         return s
1704
1705     def __sub__(self, other):
1706         s = self.__class__(self)
1707         for (start, length) in other:
1708             s.remove(start, length)
1709         return s
1710
1711     def __iadd__(self, other):
1712         for (start, length) in other:
1713             self.add(start, length)
1714         return self
1715
1716     def __isub__(self, other):
1717         for (start, length) in other:
1718             self.remove(start, length)
1719         return self
1720
1721     def __and__(self, other):
1722         s = self.__class__()
1723         for i in other.each():
1724             if i in self._have:
1725                 s.add(i, 1)
1726         return s
1727
1728     def __contains__(self, (start,length)):
1729         for i in range(start, start+length):
1730             if i not in self._have:
1731                 return False
1732         return True
1733
1734 class ByteSpans(unittest.TestCase):
1735     def test_basic(self):
1736         s = Spans()
1737         self.failUnlessEqual(list(s), [])
1738         self.failIf(s)
1739         self.failIf((0,1) in s)
1740         self.failUnlessEqual(s.len(), 0)
1741
1742         s1 = Spans(3, 4) # 3,4,5,6
1743         self._check1(s1)
1744
1745         s1 = Spans(3L, 4L) # 3,4,5,6
1746         self._check1(s1)
1747
1748         s2 = Spans(s1)
1749         self._check1(s2)
1750
1751         s2.add(10,2) # 10,11
1752         self._check1(s1)
1753         self.failUnless((10,1) in s2)
1754         self.failIf((10,1) in s1)
1755         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11])
1756         self.failUnlessEqual(s2.len(), 6)
1757
1758         s2.add(15,2).add(20,2)
1759         self.failUnlessEqual(list(s2.each()), [3,4,5,6,10,11,15,16,20,21])
1760         self.failUnlessEqual(s2.len(), 10)
1761
1762         s2.remove(4,3).remove(15,1)
1763         self.failUnlessEqual(list(s2.each()), [3,10,11,16,20,21])
1764         self.failUnlessEqual(s2.len(), 6)
1765
1766         s1 = SimpleSpans(3, 4) # 3 4 5 6
1767         s2 = SimpleSpans(5, 4) # 5 6 7 8
1768         i = s1 & s2
1769         self.failUnlessEqual(list(i.each()), [5, 6])
1770
1771     def _check1(self, s):
1772         self.failUnlessEqual(list(s), [(3,4)])
1773         self.failUnless(s)
1774         self.failUnlessEqual(s.len(), 4)
1775         self.failIf((0,1) in s)
1776         self.failUnless((3,4) in s)
1777         self.failUnless((3,1) in s)
1778         self.failUnless((5,2) in s)
1779         self.failUnless((6,1) in s)
1780         self.failIf((6,2) in s)
1781         self.failIf((7,1) in s)
1782         self.failUnlessEqual(list(s.each()), [3,4,5,6])
1783
1784     def test_large(self):
1785         s = Spans(4, 2**65) # don't do this with a SimpleSpans
1786         self.failUnlessEqual(list(s), [(4, 2**65)])
1787         self.failUnless(s)
1788         self.failUnlessEqual(s.len(), 2**65)
1789         self.failIf((0,1) in s)
1790         self.failUnless((4,2) in s)
1791         self.failUnless((2**65,2) in s)
1792
1793     def test_math(self):
1794         s1 = Spans(0, 10) # 0,1,2,3,4,5,6,7,8,9
1795         s2 = Spans(5, 3) # 5,6,7
1796         s3 = Spans(8, 4) # 8,9,10,11
1797
1798         s = s1 - s2
1799         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1800         s = s1 - s3
1801         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1802         s = s2 - s3
1803         self.failUnlessEqual(list(s.each()), [5,6,7])
1804         s = s1 & s2
1805         self.failUnlessEqual(list(s.each()), [5,6,7])
1806         s = s2 & s1
1807         self.failUnlessEqual(list(s.each()), [5,6,7])
1808         s = s1 & s3
1809         self.failUnlessEqual(list(s.each()), [8,9])
1810         s = s3 & s1
1811         self.failUnlessEqual(list(s.each()), [8,9])
1812         s = s2 & s3
1813         self.failUnlessEqual(list(s.each()), [])
1814         s = s3 & s2
1815         self.failUnlessEqual(list(s.each()), [])
1816         s = Spans() & s3
1817         self.failUnlessEqual(list(s.each()), [])
1818         s = s3 & Spans()
1819         self.failUnlessEqual(list(s.each()), [])
1820
1821         s = s1 + s2
1822         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1823         s = s1 + s3
1824         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1825         s = s2 + s3
1826         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1827
1828         s = Spans(s1)
1829         s -= s2
1830         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,8,9])
1831         s = Spans(s1)
1832         s -= s3
1833         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7])
1834         s = Spans(s2)
1835         s -= s3
1836         self.failUnlessEqual(list(s.each()), [5,6,7])
1837
1838         s = Spans(s1)
1839         s += s2
1840         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9])
1841         s = Spans(s1)
1842         s += s3
1843         self.failUnlessEqual(list(s.each()), [0,1,2,3,4,5,6,7,8,9,10,11])
1844         s = Spans(s2)
1845         s += s3
1846         self.failUnlessEqual(list(s.each()), [5,6,7,8,9,10,11])
1847
1848     def test_random(self):
1849         # attempt to increase coverage of corner cases by comparing behavior
1850         # of a simple-but-slow model implementation against the
1851         # complex-but-fast actual implementation, in a large number of random
1852         # operations
1853         S1 = SimpleSpans
1854         S2 = Spans
1855         s1 = S1(); s2 = S2()
1856         seed = ""
1857         def _create(subseed):
1858             ns1 = S1(); ns2 = S2()
1859             for i in range(10):
1860                 what = _hash(subseed+str(i)).hexdigest()
1861                 start = int(what[2:4], 16)
1862                 length = max(1,int(what[5:6], 16))
1863                 ns1.add(start, length); ns2.add(start, length)
1864             return ns1, ns2
1865
1866         #print
1867         for i in range(1000):
1868             what = _hash(seed+str(i)).hexdigest()
1869             op = what[0]
1870             subop = what[1]
1871             start = int(what[2:4], 16)
1872             length = max(1,int(what[5:6], 16))
1873             #print what
1874             if op in "0":
1875                 if subop in "01234":
1876                     s1 = S1(); s2 = S2()
1877                 elif subop in "5678":
1878                     s1 = S1(start, length); s2 = S2(start, length)
1879                 else:
1880                     s1 = S1(s1); s2 = S2(s2)
1881                 #print "s2 = %s" % s2.dump()
1882             elif op in "123":
1883                 #print "s2.add(%d,%d)" % (start, length)
1884                 s1.add(start, length); s2.add(start, length)
1885             elif op in "456":
1886                 #print "s2.remove(%d,%d)" % (start, length)
1887                 s1.remove(start, length); s2.remove(start, length)
1888             elif op in "78":
1889                 ns1, ns2 = _create(what[7:11])
1890                 #print "s2 + %s" % ns2.dump()
1891                 s1 = s1 + ns1; s2 = s2 + ns2
1892             elif op in "9a":
1893                 ns1, ns2 = _create(what[7:11])
1894                 #print "%s - %s" % (s2.dump(), ns2.dump())
1895                 s1 = s1 - ns1; s2 = s2 - ns2
1896             elif op in "bc":
1897                 ns1, ns2 = _create(what[7:11])
1898                 #print "s2 += %s" % ns2.dump()
1899                 s1 += ns1; s2 += ns2
1900             elif op in "de":
1901                 ns1, ns2 = _create(what[7:11])
1902                 #print "%s -= %s" % (s2.dump(), ns2.dump())
1903                 s1 -= ns1; s2 -= ns2
1904             else:
1905                 ns1, ns2 = _create(what[7:11])
1906                 #print "%s &= %s" % (s2.dump(), ns2.dump())
1907                 s1 = s1 & ns1; s2 = s2 & ns2
1908             #print "s2 now %s" % s2.dump()
1909             self.failUnlessEqual(list(s1.each()), list(s2.each()))
1910             self.failUnlessEqual(s1.len(), s2.len())
1911             self.failUnlessEqual(bool(s1), bool(s2))
1912             self.failUnlessEqual(list(s1), list(s2))
1913             for j in range(10):
1914                 what = _hash(what[12:14]+str(j)).hexdigest()
1915                 start = int(what[2:4], 16)
1916                 length = max(1, int(what[5:6], 16))
1917                 span = (start, length)
1918                 self.failUnlessEqual(bool(span in s1), bool(span in s2))
1919
1920
1921     # s()
1922     # s(start,length)
1923     # s(s0)
1924     # s.add(start,length) : returns s
1925     # s.remove(start,length)
1926     # s.each() -> list of byte offsets, mostly for testing
1927     # list(s) -> list of (start,length) tuples, one per span
1928     # (start,length) in s -> True if (start..start+length-1) are all members
1929     #  NOT equivalent to x in list(s)
1930     # s.len() -> number of bytes, for testing, bool(), and accounting/limiting
1931     # bool(s)  (__nonzeron__)
1932     # s = s1+s2, s1-s2, +=s1, -=s1
1933
1934     def test_overlap(self):
1935         for a in range(20):
1936             for b in range(10):
1937                 for c in range(20):
1938                     for d in range(10):
1939                         self._test_overlap(a,b,c,d)
1940
1941     def _test_overlap(self, a, b, c, d):
1942         s1 = set(range(a,a+b))
1943         s2 = set(range(c,c+d))
1944         #print "---"
1945         #self._show_overlap(s1, "1")
1946         #self._show_overlap(s2, "2")
1947         o = overlap(a,b,c,d)
1948         expected = s1.intersection(s2)
1949         if not expected:
1950             self.failUnlessEqual(o, None)
1951         else:
1952             start,length = o
1953             so = set(range(start,start+length))
1954             #self._show(so, "o")
1955             self.failUnlessEqual(so, expected)
1956
1957     def _show_overlap(self, s, c):
1958         import sys
1959         out = sys.stdout
1960         if s:
1961             for i in range(max(s)):
1962                 if i in s:
1963                     out.write(c)
1964                 else:
1965                     out.write(" ")
1966         out.write("\n")
1967
1968 def extend(s, start, length, fill):
1969     if len(s) >= start+length:
1970         return s
1971     assert len(fill) == 1
1972     return s + fill*(start+length-len(s))
1973
1974 def replace(s, start, data):
1975     assert len(s) >= start+len(data)
1976     return s[:start] + data + s[start+len(data):]
1977
1978 class SimpleDataSpans:
1979     def __init__(self, other=None):
1980         self.missing = "" # "1" where missing, "0" where found
1981         self.data = ""
1982         if other:
1983             for (start, data) in other.get_chunks():
1984                 self.add(start, data)
1985
1986     def __nonzero__(self): # this gets us bool()
1987         return self.len()
1988     def len(self):
1989         return len(self.missing.replace("1", ""))
1990     def _dump(self):
1991         return [i for (i,c) in enumerate(self.missing) if c == "0"]
1992     def _have(self, start, length):
1993         m = self.missing[start:start+length]
1994         if not m or len(m)<length or int(m):
1995             return False
1996         return True
1997     def get_chunks(self):
1998         for i in self._dump():
1999             yield (i, self.data[i])
2000     def get_spans(self):
2001         return SimpleSpans([(start,len(data))
2002                             for (start,data) in self.get_chunks()])
2003     def get(self, start, length):
2004         if self._have(start, length):
2005             return self.data[start:start+length]
2006         return None
2007     def pop(self, start, length):
2008         data = self.get(start, length)
2009         if data:
2010             self.remove(start, length)
2011         return data
2012     def remove(self, start, length):
2013         self.missing = replace(extend(self.missing, start, length, "1"),
2014                                start, "1"*length)
2015     def add(self, start, data):
2016         self.missing = replace(extend(self.missing, start, len(data), "1"),
2017                                start, "0"*len(data))
2018         self.data = replace(extend(self.data, start, len(data), " "),
2019                             start, data)
2020
2021
2022 class StringSpans(unittest.TestCase):
2023     def do_basic(self, klass):
2024         ds = klass()
2025         self.failUnlessEqual(ds.len(), 0)
2026         self.failUnlessEqual(list(ds._dump()), [])
2027         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 0)
2028         s1 = ds.get_spans()
2029         self.failUnlessEqual(ds.get(0, 4), None)
2030         self.failUnlessEqual(ds.pop(0, 4), None)
2031         ds.remove(0, 4)
2032
2033         ds.add(2, "four")
2034         self.failUnlessEqual(ds.len(), 4)
2035         self.failUnlessEqual(list(ds._dump()), [2,3,4,5])
2036         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2037         s1 = ds.get_spans()
2038         self.failUnless((2,2) in s1)
2039         self.failUnlessEqual(ds.get(0, 4), None)
2040         self.failUnlessEqual(ds.pop(0, 4), None)
2041         self.failUnlessEqual(ds.get(4, 4), None)
2042
2043         ds2 = klass(ds)
2044         self.failUnlessEqual(ds2.len(), 4)
2045         self.failUnlessEqual(list(ds2._dump()), [2,3,4,5])
2046         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 4)
2047         self.failUnlessEqual(ds2.get(0, 4), None)
2048         self.failUnlessEqual(ds2.pop(0, 4), None)
2049         self.failUnlessEqual(ds2.pop(2, 3), "fou")
2050         self.failUnlessEqual(sum([len(d) for (s,d) in ds2.get_chunks()]), 1)
2051         self.failUnlessEqual(ds2.get(2, 3), None)
2052         self.failUnlessEqual(ds2.get(5, 1), "r")
2053         self.failUnlessEqual(ds.get(2, 3), "fou")
2054         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 4)
2055
2056         ds.add(0, "23")
2057         self.failUnlessEqual(ds.len(), 6)
2058         self.failUnlessEqual(list(ds._dump()), [0,1,2,3,4,5])
2059         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 6)
2060         self.failUnlessEqual(ds.get(0, 4), "23fo")
2061         self.failUnlessEqual(ds.pop(0, 4), "23fo")
2062         self.failUnlessEqual(sum([len(d) for (s,d) in ds.get_chunks()]), 2)
2063         self.failUnlessEqual(ds.get(0, 4), None)
2064         self.failUnlessEqual(ds.pop(0, 4), None)
2065
2066         ds = klass()
2067         ds.add(2, "four")
2068         ds.add(3, "ea")
2069         self.failUnlessEqual(ds.get(2, 4), "fear")
2070
2071         ds = klass()
2072         ds.add(2L, "four")
2073         ds.add(3L, "ea")
2074         self.failUnlessEqual(ds.get(2L, 4L), "fear")
2075
2076
2077     def do_scan(self, klass):
2078         # do a test with gaps and spans of size 1 and 2
2079         #  left=(1,11) * right=(1,11) * gapsize=(1,2)
2080         # 111, 112, 121, 122, 211, 212, 221, 222
2081         #    211
2082         #      121
2083         #         112
2084         #            212
2085         #               222
2086         #                   221
2087         #                      111
2088         #                        122
2089         #  11 1  1 11 11  11  1 1  111
2090         # 0123456789012345678901234567
2091         # abcdefghijklmnopqrstuvwxyz-=
2092         pieces = [(1, "bc"),
2093                   (4, "e"),
2094                   (7, "h"),
2095                   (9, "jk"),
2096                   (12, "mn"),
2097                   (16, "qr"),
2098                   (20, "u"),
2099                   (22, "w"),
2100                   (25, "z-="),
2101                   ]
2102         p_elements = set([1,2,4,7,9,10,12,13,16,17,20,22,25,26,27])
2103         S = "abcdefghijklmnopqrstuvwxyz-="
2104         # TODO: when adding data, add capital letters, to make sure we aren't
2105         # just leaving the old data in place
2106         l = len(S)
2107         def base():
2108             ds = klass()
2109             for start, data in pieces:
2110                 ds.add(start, data)
2111             return ds
2112         def dump(s):
2113             p = set(s._dump())
2114             d = "".join([((i not in p) and " " or S[i]) for i in range(l)])
2115             assert len(d) == l
2116             return d
2117         DEBUG = False
2118         for start in range(0, l):
2119             for end in range(start+1, l):
2120                 # add [start-end) to the baseline
2121                 which = "%d-%d" % (start, end-1)
2122                 p_added = set(range(start, end))
2123                 b = base()
2124                 if DEBUG:
2125                     print
2126                     print dump(b), which
2127                     add = klass(); add.add(start, S[start:end])
2128                     print dump(add)
2129                 b.add(start, S[start:end])
2130                 if DEBUG:
2131                     print dump(b)
2132                 # check that the new span is there
2133                 d = b.get(start, end-start)
2134                 self.failUnlessEqual(d, S[start:end], which)
2135                 # check that all the original pieces are still there
2136                 for t_start, t_data in pieces:
2137                     t_len = len(t_data)
2138                     self.failUnlessEqual(b.get(t_start, t_len),
2139                                          S[t_start:t_start+t_len],
2140                                          "%s %d+%d" % (which, t_start, t_len))
2141                 # check that a lot of subspans are mostly correct
2142                 for t_start in range(l):
2143                     for t_len in range(1,4):
2144                         d = b.get(t_start, t_len)
2145                         if d is not None:
2146                             which2 = "%s+(%d-%d)" % (which, t_start,
2147                                                      t_start+t_len-1)
2148                             self.failUnlessEqual(d, S[t_start:t_start+t_len],
2149                                                  which2)
2150                         # check that removing a subspan gives the right value
2151                         b2 = klass(b)
2152                         b2.remove(t_start, t_len)
2153                         removed = set(range(t_start, t_start+t_len))
2154                         for i in range(l):
2155                             exp = (((i in p_elements) or (i in p_added))
2156                                    and (i not in removed))
2157                             which2 = "%s-(%d-%d)" % (which, t_start,
2158                                                      t_start+t_len-1)
2159                             self.failUnlessEqual(bool(b2.get(i, 1)), exp,
2160                                                  which2+" %d" % i)
2161
2162     def test_test(self):
2163         self.do_basic(SimpleDataSpans)
2164         self.do_scan(SimpleDataSpans)
2165
2166     def test_basic(self):
2167         self.do_basic(DataSpans)
2168         self.do_scan(DataSpans)
2169
2170     def test_random(self):
2171         # attempt to increase coverage of corner cases by comparing behavior
2172         # of a simple-but-slow model implementation against the
2173         # complex-but-fast actual implementation, in a large number of random
2174         # operations
2175         S1 = SimpleDataSpans
2176         S2 = DataSpans
2177         s1 = S1(); s2 = S2()
2178         seed = ""
2179         def _randstr(length, seed):
2180             created = 0
2181             pieces = []
2182             while created < length:
2183                 piece = _hash(seed + str(created)).hexdigest()
2184                 pieces.append(piece)
2185                 created += len(piece)
2186             return "".join(pieces)[:length]
2187         def _create(subseed):
2188             ns1 = S1(); ns2 = S2()
2189             for i in range(10):
2190                 what = _hash(subseed+str(i)).hexdigest()
2191                 start = int(what[2:4], 16)
2192                 length = max(1,int(what[5:6], 16))
2193                 ns1.add(start, _randstr(length, what[7:9]));
2194                 ns2.add(start, _randstr(length, what[7:9]))
2195             return ns1, ns2
2196
2197         #print
2198         for i in range(1000):
2199             what = _hash(seed+str(i)).hexdigest()
2200             op = what[0]
2201             subop = what[1]
2202             start = int(what[2:4], 16)
2203             length = max(1,int(what[5:6], 16))
2204             #print what
2205             if op in "0":
2206                 if subop in "0123456":
2207                     s1 = S1(); s2 = S2()
2208                 else:
2209                     s1, s2 = _create(what[7:11])
2210                 #print "s2 = %s" % list(s2._dump())
2211             elif op in "123456":
2212                 #print "s2.add(%d,%d)" % (start, length)
2213                 s1.add(start, _randstr(length, what[7:9]));
2214                 s2.add(start, _randstr(length, what[7:9]))
2215             elif op in "789abc":
2216                 #print "s2.remove(%d,%d)" % (start, length)
2217                 s1.remove(start, length); s2.remove(start, length)
2218             else:
2219                 #print "s2.pop(%d,%d)" % (start, length)
2220                 d1 = s1.pop(start, length); d2 = s2.pop(start, length)
2221                 self.failUnlessEqual(d1, d2)
2222             #print "s1 now %s" % list(s1._dump())
2223             #print "s2 now %s" % list(s2._dump())
2224             self.failUnlessEqual(s1.len(), s2.len())
2225             self.failUnlessEqual(list(s1._dump()), list(s2._dump()))
2226             for j in range(100):
2227                 what = _hash(what[12:14]+str(j)).hexdigest()
2228                 start = int(what[2:4], 16)
2229                 length = max(1, int(what[5:6], 16))
2230                 d1 = s1.get(start, length); d2 = s2.get(start, length)
2231                 self.failUnlessEqual(d1, d2, "%d+%d" % (start, length))