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