src/allmydata/test/test_util.py

   1
   2 def foo(): pass # keep the line number constant
   3
   4 import os, time
   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
  11 from allmydata.util import base32, idlib, humanreadable, mathutil, hashutil
  12 from allmydata.util import assertutil, fileutil, deferredutil, abbreviate
  13 from allmydata.util import limiter, time_format, pollmixin, cachedir
  14 from allmydata.util import statistics, dictutil, pipeline
  15 from allmydata.util import log as tahoe_log
  16
  17 class Base32(unittest.TestCase):
  18     def test_b2a_matches_Pythons(self):
  19         import base64
  20         y = "\x12\x34\x45\x67\x89\x0a\xbc\xde\xf0"
  21         x = base64.b32encode(y)
  22         while x and x[-1] == '=':
  23             x = x[:-1]
  24         x = x.lower()
  25         self.failUnlessEqual(base32.b2a(y), x)
  26     def test_b2a(self):
  27         self.failUnlessEqual(base32.b2a("\x12\x34"), "ci2a")
  28     def test_b2a_or_none(self):
  29         self.failUnlessEqual(base32.b2a_or_none(None), None)
  30         self.failUnlessEqual(base32.b2a_or_none("\x12\x34"), "ci2a")
  31     def test_a2b(self):
  32         self.failUnlessEqual(base32.a2b("ci2a"), "\x12\x34")
  33         self.failUnlessRaises(AssertionError, base32.a2b, "b0gus")
  34
  35 class IDLib(unittest.TestCase):
  36     def test_nodeid_b2a(self):
  37         self.failUnlessEqual(idlib.nodeid_b2a("\x00"*20), "a"*32)
  38
  39 class NoArgumentException(Exception):
  40     def __init__(self):
  41         pass
  42
  43 class HumanReadable(unittest.TestCase):
  44     def test_repr(self):
  45         hr = humanreadable.hr
  46         self.failUnlessEqual(hr(foo), "<foo() at test_util.py:2>")
  47         self.failUnlessEqual(hr(self.test_repr),
  48                              "<bound method HumanReadable.test_repr of <allmydata.test.test_util.HumanReadable testMethod=test_repr>>")
  49         self.failUnlessEqual(hr(1L), "1")
  50         self.failUnlessEqual(hr(10**40),
  51                              "100000000000000000...000000000000000000")
  52         self.failUnlessEqual(hr(self), "<allmydata.test.test_util.HumanReadable testMethod=test_repr>")
  53         self.failUnlessEqual(hr([1,2]), "[1, 2]")
  54         self.failUnlessEqual(hr({1:2}), "{1:2}")
  55         try:
  56             raise ValueError
  57         except Exception, e:
  58             self.failUnless(
  59                 hr(e) == "<ValueError: ()>" # python-2.4
  60                 or hr(e) == "ValueError()") # python-2.5
  61         try:
  62             raise ValueError("oops")
  63         except Exception, e:
  64             self.failUnless(
  65                 hr(e) == "<ValueError: 'oops'>" # python-2.4
  66                 or hr(e) == "ValueError('oops',)") # python-2.5
  67         try:
  68             raise NoArgumentException
  69         except Exception, e:
  70             self.failUnless(
  71                 hr(e) == "<NoArgumentException>" # python-2.4
  72                 or hr(e) == "NoArgumentException()") # python-2.5
  73
  74
  75 class MyList(list):
  76     pass
  77
  78 class Math(unittest.TestCase):
  79     def test_div_ceil(self):
  80         f = mathutil.div_ceil
  81         self.failUnlessEqual(f(0, 1), 0)
  82         self.failUnlessEqual(f(0, 2), 0)
  83         self.failUnlessEqual(f(0, 3), 0)
  84         self.failUnlessEqual(f(1, 3), 1)
  85         self.failUnlessEqual(f(2, 3), 1)
  86         self.failUnlessEqual(f(3, 3), 1)
  87         self.failUnlessEqual(f(4, 3), 2)
  88         self.failUnlessEqual(f(5, 3), 2)
  89         self.failUnlessEqual(f(6, 3), 2)
  90         self.failUnlessEqual(f(7, 3), 3)
  91
  92     def test_next_multiple(self):
  93         f = mathutil.next_multiple
  94         self.failUnlessEqual(f(5, 1), 5)
  95         self.failUnlessEqual(f(5, 2), 6)
  96         self.failUnlessEqual(f(5, 3), 6)
  97         self.failUnlessEqual(f(5, 4), 8)
  98         self.failUnlessEqual(f(5, 5), 5)
  99         self.failUnlessEqual(f(5, 6), 6)
 100         self.failUnlessEqual(f(32, 1), 32)
 101         self.failUnlessEqual(f(32, 2), 32)
 102         self.failUnlessEqual(f(32, 3), 33)
 103         self.failUnlessEqual(f(32, 4), 32)
 104         self.failUnlessEqual(f(32, 5), 35)
 105         self.failUnlessEqual(f(32, 6), 36)
 106         self.failUnlessEqual(f(32, 7), 35)
 107         self.failUnlessEqual(f(32, 8), 32)
 108         self.failUnlessEqual(f(32, 9), 36)
 109         self.failUnlessEqual(f(32, 10), 40)
 110         self.failUnlessEqual(f(32, 11), 33)
 111         self.failUnlessEqual(f(32, 12), 36)
 112         self.failUnlessEqual(f(32, 13), 39)
 113         self.failUnlessEqual(f(32, 14), 42)
 114         self.failUnlessEqual(f(32, 15), 45)
 115         self.failUnlessEqual(f(32, 16), 32)
 116         self.failUnlessEqual(f(32, 17), 34)
 117         self.failUnlessEqual(f(32, 18), 36)
 118         self.failUnlessEqual(f(32, 589), 589)
 119
 120     def test_pad_size(self):
 121         f = mathutil.pad_size
 122         self.failUnlessEqual(f(0, 4), 0)
 123         self.failUnlessEqual(f(1, 4), 3)
 124         self.failUnlessEqual(f(2, 4), 2)
 125         self.failUnlessEqual(f(3, 4), 1)
 126         self.failUnlessEqual(f(4, 4), 0)
 127         self.failUnlessEqual(f(5, 4), 3)
 128
 129     def test_is_power_of_k(self):
 130         f = mathutil.is_power_of_k
 131         for i in range(1, 100):
 132             if i in (1, 2, 4, 8, 16, 32, 64):
 133                 self.failUnless(f(i, 2), "but %d *is* a power of 2" % i)
 134             else:
 135                 self.failIf(f(i, 2), "but %d is *not* a power of 2" % i)
 136         for i in range(1, 100):
 137             if i in (1, 3, 9, 27, 81):
 138                 self.failUnless(f(i, 3), "but %d *is* a power of 3" % i)
 139             else:
 140                 self.failIf(f(i, 3), "but %d is *not* a power of 3" % i)
 141
 142     def test_next_power_of_k(self):
 143         f = mathutil.next_power_of_k
 144         self.failUnlessEqual(f(0,2), 1)
 145         self.failUnlessEqual(f(1,2), 1)
 146         self.failUnlessEqual(f(2,2), 2)
 147         self.failUnlessEqual(f(3,2), 4)
 148         self.failUnlessEqual(f(4,2), 4)
 149         for i in range(5, 8): self.failUnlessEqual(f(i,2), 8, "%d" % i)
 150         for i in range(9, 16): self.failUnlessEqual(f(i,2), 16, "%d" % i)
 151         for i in range(17, 32): self.failUnlessEqual(f(i,2), 32, "%d" % i)
 152         for i in range(33, 64): self.failUnlessEqual(f(i,2), 64, "%d" % i)
 153         for i in range(65, 100): self.failUnlessEqual(f(i,2), 128, "%d" % i)
 154
 155         self.failUnlessEqual(f(0,3), 1)
 156         self.failUnlessEqual(f(1,3), 1)
 157         self.failUnlessEqual(f(2,3), 3)
 158         self.failUnlessEqual(f(3,3), 3)
 159         for i in range(4, 9): self.failUnlessEqual(f(i,3), 9, "%d" % i)
 160         for i in range(10, 27): self.failUnlessEqual(f(i,3), 27, "%d" % i)
 161         for i in range(28, 81): self.failUnlessEqual(f(i,3), 81, "%d" % i)
 162         for i in range(82, 200): self.failUnlessEqual(f(i,3), 243, "%d" % i)
 163
 164     def test_ave(self):
 165         f = mathutil.ave
 166         self.failUnlessEqual(f([1,2,3]), 2)
 167         self.failUnlessEqual(f([0,0,0,4]), 1)
 168         self.failUnlessAlmostEqual(f([0.0, 1.0, 1.0]), .666666666666)
 169
 170     def test_round_sigfigs(self):
 171         f = mathutil.round_sigfigs
 172         self.failUnlessEqual(f(22.0/3, 4), 7.3330000000000002)
 173
 174 class Statistics(unittest.TestCase):
 175     def should_assert(self, msg, func, *args, **kwargs):
 176         try:
 177             func(*args, **kwargs)
 178             self.fail(msg)
 179         except AssertionError, e:
 180             pass
 181
 182     def failUnlessListEqual(self, a, b, msg = None):
 183         self.failUnlessEqual(len(a), len(b))
 184         for i in range(len(a)):
 185             self.failUnlessEqual(a[i], b[i], msg)
 186
 187     def failUnlessListAlmostEqual(self, a, b, places = 7, msg = None):
 188         self.failUnlessEqual(len(a), len(b))
 189         for i in range(len(a)):
 190             self.failUnlessAlmostEqual(a[i], b[i], places, msg)
 191
 192     def test_binomial_coeff(self):
 193         f = statistics.binomial_coeff
 194         self.failUnlessEqual(f(20, 0), 1)
 195         self.failUnlessEqual(f(20, 1), 20)
 196         self.failUnlessEqual(f(20, 2), 190)
 197         self.failUnlessEqual(f(20, 8), f(20, 12))
 198         self.should_assert("Should assert if n < k", f, 2, 3)
 199
 200     def test_binomial_distribution_pmf(self):
 201         f = statistics.binomial_distribution_pmf
 202
 203         pmf_comp = f(2, .1)
 204         pmf_stat = [0.81, 0.18, 0.01]
 205         self.failUnlessListAlmostEqual(pmf_comp, pmf_stat)
 206
 207         # Summing across a PMF should give the total probability 1
 208         self.failUnlessAlmostEqual(sum(pmf_comp), 1)
 209         self.should_assert("Should assert if not 0<=p<=1", f, 1, -1)
 210         self.should_assert("Should assert if n < 1", f, 0, .1)
 211
 212         out = StringIO()
 213         statistics.print_pmf(pmf_comp, out=out)
 214         lines = out.getvalue().splitlines()
 215         self.failUnlessEqual(lines[0], "i=0: 0.81")
 216         self.failUnlessEqual(lines[1], "i=1: 0.18")
 217         self.failUnlessEqual(lines[2], "i=2: 0.01")
 218
 219     def test_survival_pmf(self):
 220         f = statistics.survival_pmf
 221         # Cross-check binomial-distribution method against convolution
 222         # method.
 223         p_list = [.9999] * 100 + [.99] * 50 + [.8] * 20
 224         pmf1 = statistics.survival_pmf_via_conv(p_list)
 225         pmf2 = statistics.survival_pmf_via_bd(p_list)
 226         self.failUnlessListAlmostEqual(pmf1, pmf2)
 227         self.failUnlessTrue(statistics.valid_pmf(pmf1))
 228         self.should_assert("Should assert if p_i > 1", f, [1.1]);
 229         self.should_assert("Should assert if p_i < 0", f, [-.1]);
 230
 231     def test_repair_count_pmf(self):
 232         survival_pmf = statistics.binomial_distribution_pmf(5, .9)
 233         repair_pmf = statistics.repair_count_pmf(survival_pmf, 3)
 234         # repair_pmf[0] == sum(survival_pmf[0,1,2,5])
 235         # repair_pmf[1] == survival_pmf[4]
 236         # repair_pmf[2] = survival_pmf[3]
 237         self.failUnlessListAlmostEqual(repair_pmf,
 238                                        [0.00001 + 0.00045 + 0.0081 + 0.59049,
 239                                         .32805,
 240                                         .0729,
 241                                         0, 0, 0])
 242
 243     def test_repair_cost(self):
 244         survival_pmf = statistics.binomial_distribution_pmf(5, .9)
 245         bwcost = statistics.bandwidth_cost_function
 246         cost = statistics.mean_repair_cost(bwcost, 1000,
 247                                            survival_pmf, 3, ul_dl_ratio=1.0)
 248         self.failUnlessAlmostEqual(cost, 558.90)
 249         cost = statistics.mean_repair_cost(bwcost, 1000,
 250                                            survival_pmf, 3, ul_dl_ratio=8.0)
 251         self.failUnlessAlmostEqual(cost, 1664.55)
 252
 253         # I haven't manually checked the math beyond here -warner
 254         cost = statistics.eternal_repair_cost(bwcost, 1000,
 255                                               survival_pmf, 3,
 256                                               discount_rate=0, ul_dl_ratio=1.0)
 257         self.failUnlessAlmostEqual(cost, 65292.056074766246)
 258         cost = statistics.eternal_repair_cost(bwcost, 1000,
 259                                               survival_pmf, 3,
 260                                               discount_rate=0.05,
 261                                               ul_dl_ratio=1.0)
 262         self.failUnlessAlmostEqual(cost, 9133.6097158191551)
 263
 264     def test_convolve(self):
 265         f = statistics.convolve
 266         v1 = [ 1, 2, 3 ]
 267         v2 = [ 4, 5, 6 ]
 268         v3 = [ 7, 8 ]
 269         v1v2result = [ 4, 13, 28, 27, 18 ]
 270         # Convolution is commutative
 271         r1 = f(v1, v2)
 272         r2 = f(v2, v1)
 273         self.failUnlessListEqual(r1, r2, "Convolution should be commutative")
 274         self.failUnlessListEqual(r1, v1v2result, "Didn't match known result")
 275         # Convolution is associative
 276         r1 = f(f(v1, v2), v3)
 277         r2 = f(v1, f(v2, v3))
 278         self.failUnlessListEqual(r1, r2, "Convolution should be associative")
 279         # Convolution is distributive
 280         r1 = f(v3, [ a + b for a, b in zip(v1, v2) ])
 281         tmp1 = f(v3, v1)
 282         tmp2 = f(v3, v2)
 283         r2 = [ a + b for a, b in zip(tmp1, tmp2) ]
 284         self.failUnlessListEqual(r1, r2, "Convolution should be distributive")
 285         # Convolution is scalar multiplication associative
 286         tmp1 = f(v1, v2)
 287         r1 = [ a * 4 for a in tmp1 ]
 288         tmp2 = [ a * 4 for a in v1 ]
 289         r2 = f(tmp2, v2)
 290         self.failUnlessListEqual(r1, r2, "Convolution should be scalar multiplication associative")
 291
 292     def test_find_k(self):
 293         f = statistics.find_k
 294         g = statistics.pr_file_loss
 295         plist = [.9] * 10 + [.8] * 10 # N=20
 296         t = .0001
 297         k = f(plist, t)
 298         self.failUnlessEqual(k, 10)
 299         self.failUnless(g(plist, k) < t)
 300
 301     def test_pr_file_loss(self):
 302         f = statistics.pr_file_loss
 303         plist = [.5] * 10
 304         self.failUnlessEqual(f(plist, 3), .0546875)
 305
 306     def test_pr_backup_file_loss(self):
 307         f = statistics.pr_backup_file_loss
 308         plist = [.5] * 10
 309         self.failUnlessEqual(f(plist, .5, 3), .02734375)
 310
 311
 312 class Asserts(unittest.TestCase):
 313     def should_assert(self, func, *args, **kwargs):
 314         try:
 315             func(*args, **kwargs)
 316         except AssertionError, e:
 317             return str(e)
 318         except Exception, e:
 319             self.fail("assert failed with non-AssertionError: %s" % e)
 320         self.fail("assert was not caught")
 321
 322     def should_not_assert(self, func, *args, **kwargs):
 323         if "re" in kwargs:
 324             regexp = kwargs["re"]
 325             del kwargs["re"]
 326         try:
 327             func(*args, **kwargs)
 328         except AssertionError, e:
 329             self.fail("assertion fired when it should not have: %s" % e)
 330         except Exception, e:
 331             self.fail("assertion (which shouldn't have failed) failed with non-AssertionError: %s" % e)
 332         return # we're happy
 333
 334
 335     def test_assert(self):
 336         f = assertutil._assert
 337         self.should_assert(f)
 338         self.should_assert(f, False)
 339         self.should_not_assert(f, True)
 340
 341         m = self.should_assert(f, False, "message")
 342         self.failUnlessEqual(m, "'message' <type 'str'>", m)
 343         m = self.should_assert(f, False, "message1", othermsg=12)
 344         self.failUnlessEqual("'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 345         m = self.should_assert(f, False, othermsg="message2")
 346         self.failUnlessEqual("othermsg: 'message2' <type 'str'>", m)
 347
 348     def test_precondition(self):
 349         f = assertutil.precondition
 350         self.should_assert(f)
 351         self.should_assert(f, False)
 352         self.should_not_assert(f, True)
 353
 354         m = self.should_assert(f, False, "message")
 355         self.failUnlessEqual("precondition: 'message' <type 'str'>", m)
 356         m = self.should_assert(f, False, "message1", othermsg=12)
 357         self.failUnlessEqual("precondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 358         m = self.should_assert(f, False, othermsg="message2")
 359         self.failUnlessEqual("precondition: othermsg: 'message2' <type 'str'>", m)
 360
 361     def test_postcondition(self):
 362         f = assertutil.postcondition
 363         self.should_assert(f)
 364         self.should_assert(f, False)
 365         self.should_not_assert(f, True)
 366
 367         m = self.should_assert(f, False, "message")
 368         self.failUnlessEqual("postcondition: 'message' <type 'str'>", m)
 369         m = self.should_assert(f, False, "message1", othermsg=12)
 370         self.failUnlessEqual("postcondition: 'message1' <type 'str'>, othermsg: 12 <type 'int'>", m)
 371         m = self.should_assert(f, False, othermsg="message2")
 372         self.failUnlessEqual("postcondition: othermsg: 'message2' <type 'str'>", m)
 373
 374 class FileUtil(unittest.TestCase):
 375     def mkdir(self, basedir, path, mode=0777):
 376         fn = os.path.join(basedir, path)
 377         fileutil.make_dirs(fn, mode)
 378
 379     def touch(self, basedir, path, mode=None, data="touch\n"):
 380         fn = os.path.join(basedir, path)
 381         f = open(fn, "w")
 382         f.write(data)
 383         f.close()
 384         if mode is not None:
 385             os.chmod(fn, mode)
 386
 387     def test_rm_dir(self):
 388         basedir = "util/FileUtil/test_rm_dir"
 389         fileutil.make_dirs(basedir)
 390         # create it again to test idempotency
 391         fileutil.make_dirs(basedir)
 392         d = os.path.join(basedir, "doomed")
 393         self.mkdir(d, "a/b")
 394         self.touch(d, "a/b/1.txt")
 395         self.touch(d, "a/b/2.txt", 0444)
 396         self.touch(d, "a/b/3.txt", 0)
 397         self.mkdir(d, "a/c")
 398         self.touch(d, "a/c/1.txt")
 399         self.touch(d, "a/c/2.txt", 0444)
 400         self.touch(d, "a/c/3.txt", 0)
 401         os.chmod(os.path.join(d, "a/c"), 0444)
 402         self.mkdir(d, "a/d")
 403         self.touch(d, "a/d/1.txt")
 404         self.touch(d, "a/d/2.txt", 0444)
 405         self.touch(d, "a/d/3.txt", 0)
 406         os.chmod(os.path.join(d, "a/d"), 0)
 407
 408         fileutil.rm_dir(d)
 409         self.failIf(os.path.exists(d))
 410         # remove it again to test idempotency
 411         fileutil.rm_dir(d)
 412
 413     def test_remove_if_possible(self):
 414         basedir = "util/FileUtil/test_remove_if_possible"
 415         fileutil.make_dirs(basedir)
 416         self.touch(basedir, "here")
 417         fn = os.path.join(basedir, "here")
 418         fileutil.remove_if_possible(fn)
 419         self.failIf(os.path.exists(fn))
 420         fileutil.remove_if_possible(fn) # should be idempotent
 421         fileutil.rm_dir(basedir)
 422         fileutil.remove_if_possible(fn) # should survive errors
 423
 424     def test_open_or_create(self):
 425         basedir = "util/FileUtil/test_open_or_create"
 426         fileutil.make_dirs(basedir)
 427         fn = os.path.join(basedir, "here")
 428         f = fileutil.open_or_create(fn)
 429         f.write("stuff.")
 430         f.close()
 431         f = fileutil.open_or_create(fn)
 432         f.seek(0, 2)
 433         f.write("more.")
 434         f.close()
 435         f = open(fn, "r")
 436         data = f.read()
 437         f.close()
 438         self.failUnlessEqual(data, "stuff.more.")
 439
 440     def test_NamedTemporaryDirectory(self):
 441         basedir = "util/FileUtil/test_NamedTemporaryDirectory"
 442         fileutil.make_dirs(basedir)
 443         td = fileutil.NamedTemporaryDirectory(dir=basedir)
 444         name = td.name
 445         self.failUnless(basedir in name)
 446         self.failUnless(basedir in repr(td))
 447         self.failUnless(os.path.isdir(name))
 448         del td
 449         # it is conceivable that we need to force gc here, but I'm not sure
 450         self.failIf(os.path.isdir(name))
 451
 452     def test_rename(self):
 453         basedir = "util/FileUtil/test_rename"
 454         fileutil.make_dirs(basedir)
 455         self.touch(basedir, "here")
 456         fn = os.path.join(basedir, "here")
 457         fn2 = os.path.join(basedir, "there")
 458         fileutil.rename(fn, fn2)
 459         self.failIf(os.path.exists(fn))
 460         self.failUnless(os.path.exists(fn2))
 461
 462     def test_du(self):
 463         basedir = "util/FileUtil/test_du"
 464         fileutil.make_dirs(basedir)
 465         d = os.path.join(basedir, "space-consuming")
 466         self.mkdir(d, "a/b")
 467         self.touch(d, "a/b/1.txt", data="a"*10)
 468         self.touch(d, "a/b/2.txt", data="b"*11)
 469         self.mkdir(d, "a/c")
 470         self.touch(d, "a/c/1.txt", data="c"*12)
 471         self.touch(d, "a/c/2.txt", data="d"*13)
 472
 473         used = fileutil.du(basedir)
 474         self.failUnlessEqual(10+11+12+13, used)
 475
 476 class PollMixinTests(unittest.TestCase):
 477     def setUp(self):
 478         self.pm = pollmixin.PollMixin()
 479
 480     def test_PollMixin_True(self):
 481         d = self.pm.poll(check_f=lambda : True,
 482                          pollinterval=0.1)
 483         return d
 484
 485     def test_PollMixin_False_then_True(self):
 486         i = iter([False, True])
 487         d = self.pm.poll(check_f=i.next,
 488                          pollinterval=0.1)
 489         return d
 490
 491     def test_timeout(self):
 492         d = self.pm.poll(check_f=lambda: False,
 493                          pollinterval=0.01,
 494                          timeout=1)
 495         def _suc(res):
 496             self.fail("poll should have failed, not returned %s" % (res,))
 497         def _err(f):
 498             f.trap(pollmixin.TimeoutError)
 499             return None # success
 500         d.addCallbacks(_suc, _err)
 501         return d
 502
 503 class DeferredUtilTests(unittest.TestCase):
 504     def test_gather_results(self):
 505         d1 = defer.Deferred()
 506         d2 = defer.Deferred()
 507         res = deferredutil.gatherResults([d1, d2])
 508         d1.errback(ValueError("BAD"))
 509         def _callb(res):
 510             self.fail("Should have errbacked, not resulted in %s" % (res,))
 511         def _errb(thef):
 512             thef.trap(ValueError)
 513         res.addCallbacks(_callb, _errb)
 514         return res
 515
 516     def test_success(self):
 517         d1, d2 = defer.Deferred(), defer.Deferred()
 518         good = []
 519         bad = []
 520         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 521         dlss.addCallbacks(good.append, bad.append)
 522         d1.callback(1)
 523         d2.callback(2)
 524         self.failUnlessEqual(good, [[1,2]])
 525         self.failUnlessEqual(bad, [])
 526
 527     def test_failure(self):
 528         d1, d2 = defer.Deferred(), defer.Deferred()
 529         good = []
 530         bad = []
 531         dlss = deferredutil.DeferredListShouldSucceed([d1,d2])
 532         dlss.addCallbacks(good.append, bad.append)
 533         d1.addErrback(lambda _ignore: None)
 534         d2.addErrback(lambda _ignore: None)
 535         d1.callback(1)
 536         d2.errback(ValueError())
 537         self.failUnlessEqual(good, [])
 538         self.failUnlessEqual(len(bad), 1)
 539         f = bad[0]
 540         self.failUnless(isinstance(f, Failure))
 541         self.failUnless(f.check(ValueError))
 542
 543 class HashUtilTests(unittest.TestCase):
 544
 545     def test_random_key(self):
 546         k = hashutil.random_key()
 547         self.failUnlessEqual(len(k), hashutil.KEYLEN)
 548
 549     def test_sha256d(self):
 550         h1 = hashutil.tagged_hash("tag1", "value")
 551         h2 = hashutil.tagged_hasher("tag1")
 552         h2.update("value")
 553         h2a = h2.digest()
 554         h2b = h2.digest()
 555         self.failUnlessEqual(h1, h2a)
 556         self.failUnlessEqual(h2a, h2b)
 557
 558     def test_sha256d_truncated(self):
 559         h1 = hashutil.tagged_hash("tag1", "value", 16)
 560         h2 = hashutil.tagged_hasher("tag1", 16)
 561         h2.update("value")
 562         h2 = h2.digest()
 563         self.failUnlessEqual(len(h1), 16)
 564         self.failUnlessEqual(len(h2), 16)
 565         self.failUnlessEqual(h1, h2)
 566
 567     def test_chk(self):
 568         h1 = hashutil.convergence_hash(3, 10, 1000, "data", "secret")
 569         h2 = hashutil.convergence_hasher(3, 10, 1000, "secret")
 570         h2.update("data")
 571         h2 = h2.digest()
 572         self.failUnlessEqual(h1, h2)
 573
 574     def test_hashers(self):
 575         h1 = hashutil.block_hash("foo")
 576         h2 = hashutil.block_hasher()
 577         h2.update("foo")
 578         self.failUnlessEqual(h1, h2.digest())
 579
 580         h1 = hashutil.uri_extension_hash("foo")
 581         h2 = hashutil.uri_extension_hasher()
 582         h2.update("foo")
 583         self.failUnlessEqual(h1, h2.digest())
 584
 585         h1 = hashutil.plaintext_hash("foo")
 586         h2 = hashutil.plaintext_hasher()
 587         h2.update("foo")
 588         self.failUnlessEqual(h1, h2.digest())
 589
 590         h1 = hashutil.crypttext_hash("foo")
 591         h2 = hashutil.crypttext_hasher()
 592         h2.update("foo")
 593         self.failUnlessEqual(h1, h2.digest())
 594
 595         h1 = hashutil.crypttext_segment_hash("foo")
 596         h2 = hashutil.crypttext_segment_hasher()
 597         h2.update("foo")
 598         self.failUnlessEqual(h1, h2.digest())
 599
 600         h1 = hashutil.plaintext_segment_hash("foo")
 601         h2 = hashutil.plaintext_segment_hasher()
 602         h2.update("foo")
 603         self.failUnlessEqual(h1, h2.digest())
 604
 605     def test_constant_time_compare(self):
 606         self.failUnless(hashutil.constant_time_compare("a", "a"))
 607         self.failUnless(hashutil.constant_time_compare("ab", "ab"))
 608         self.failIf(hashutil.constant_time_compare("a", "b"))
 609         self.failIf(hashutil.constant_time_compare("a", "aa"))
 610
 611     def _testknown(self, hashf, expected_a, *args):
 612         got = hashf(*args)
 613         got_a = base32.b2a(got)
 614         self.failUnlessEqual(got_a, expected_a)
 615
 616     def test_known_answers(self):
 617         # assert backwards compatibility
 618         self._testknown(hashutil.storage_index_hash, "qb5igbhcc5esa6lwqorsy7e6am", "")
 619         self._testknown(hashutil.block_hash, "msjr5bh4evuh7fa3zw7uovixfbvlnstr5b65mrerwfnvjxig2jvq", "")
 620         self._testknown(hashutil.uri_extension_hash, "wthsu45q7zewac2mnivoaa4ulh5xvbzdmsbuyztq2a5fzxdrnkka", "")
 621         self._testknown(hashutil.plaintext_hash, "5lz5hwz3qj3af7n6e3arblw7xzutvnd3p3fjsngqjcb7utf3x3da", "")
 622         self._testknown(hashutil.crypttext_hash, "itdj6e4njtkoiavlrmxkvpreosscssklunhwtvxn6ggho4rkqwga", "")
 623         self._testknown(hashutil.crypttext_segment_hash, "aovy5aa7jej6ym5ikgwyoi4pxawnoj3wtaludjz7e2nb5xijb7aa", "")
 624         self._testknown(hashutil.plaintext_segment_hash, "4fdgf6qruaisyukhqcmoth4t3li6bkolbxvjy4awwcpprdtva7za", "")
 625         self._testknown(hashutil.convergence_hash, "3mo6ni7xweplycin6nowynw2we", 3, 10, 100, "", "converge")
 626         self._testknown(hashutil.my_renewal_secret_hash, "ujhr5k5f7ypkp67jkpx6jl4p47pyta7hu5m527cpcgvkafsefm6q", "")
 627         self._testknown(hashutil.my_cancel_secret_hash, "rjwzmafe2duixvqy6h47f5wfrokdziry6zhx4smew4cj6iocsfaa", "")
 628         self._testknown(hashutil.file_renewal_secret_hash, "hzshk2kf33gzbd5n3a6eszkf6q6o6kixmnag25pniusyaulqjnia", "", "si")
 629         self._testknown(hashutil.file_cancel_secret_hash, "bfciwvr6w7wcavsngxzxsxxaszj72dej54n4tu2idzp6b74g255q", "", "si")
 630         self._testknown(hashutil.bucket_renewal_secret_hash, "e7imrzgzaoashsncacvy3oysdd2m5yvtooo4gmj4mjlopsazmvuq", "", "\x00"*20)
 631         self._testknown(hashutil.bucket_cancel_secret_hash, "dvdujeyxeirj6uux6g7xcf4lvesk632aulwkzjar7srildvtqwma", "", "\x00"*20)
 632         self._testknown(hashutil.hmac, "c54ypfi6pevb3nvo6ba42jtglpkry2kbdopqsi7dgrm4r7tw5sra", "tag", "")
 633         self._testknown(hashutil.mutable_rwcap_key_hash, "6rvn2iqrghii5n4jbbwwqqsnqu", "iv", "wk")
 634         self._testknown(hashutil.ssk_writekey_hash, "ykpgmdbpgbb6yqz5oluw2q26ye", "")
 635         self._testknown(hashutil.ssk_write_enabler_master_hash, "izbfbfkoait4dummruol3gy2bnixrrrslgye6ycmkuyujnenzpia", "")
 636         self._testknown(hashutil.ssk_write_enabler_hash, "fuu2dvx7g6gqu5x22vfhtyed7p4pd47y5hgxbqzgrlyvxoev62tq", "wk", "\x00"*20)
 637         self._testknown(hashutil.ssk_pubkey_fingerprint_hash, "3opzw4hhm2sgncjx224qmt5ipqgagn7h5zivnfzqycvgqgmgz35q", "")
 638         self._testknown(hashutil.ssk_readkey_hash, "vugid4as6qbqgeq2xczvvcedai", "")
 639         self._testknown(hashutil.ssk_readkey_data_hash, "73wsaldnvdzqaf7v4pzbr2ae5a", "iv", "rk")
 640         self._testknown(hashutil.ssk_storage_index_hash, "j7icz6kigb6hxrej3tv4z7ayym", "")
 641
 642
 643 class Abbreviate(unittest.TestCase):
 644     def test_time(self):
 645         a = abbreviate.abbreviate_time
 646         self.failUnlessEqual(a(None), "unknown")
 647         self.failUnlessEqual(a(0), "0 seconds")
 648         self.failUnlessEqual(a(1), "1 second")
 649         self.failUnlessEqual(a(2), "2 seconds")
 650         self.failUnlessEqual(a(119), "119 seconds")
 651         MIN = 60
 652         self.failUnlessEqual(a(2*MIN), "2 minutes")
 653         self.failUnlessEqual(a(60*MIN), "60 minutes")
 654         self.failUnlessEqual(a(179*MIN), "179 minutes")
 655         HOUR = 60*MIN
 656         self.failUnlessEqual(a(180*MIN), "3 hours")
 657         self.failUnlessEqual(a(4*HOUR), "4 hours")
 658         DAY = 24*HOUR
 659         MONTH = 30*DAY
 660         self.failUnlessEqual(a(2*DAY), "2 days")
 661         self.failUnlessEqual(a(2*MONTH), "2 months")
 662         YEAR = 365*DAY
 663         self.failUnlessEqual(a(5*YEAR), "5 years")
 664
 665     def test_space(self):
 666         tests_si = [(None, "unknown"),
 667                     (0, "0 B"),
 668                     (1, "1 B"),
 669                     (999, "999 B"),
 670                     (1000, "1000 B"),
 671                     (1023, "1023 B"),
 672                     (1024, "1.02 kB"),
 673                     (20*1000, "20.00 kB"),
 674                     (1024*1024, "1.05 MB"),
 675                     (1000*1000, "1.00 MB"),
 676                     (1000*1000*1000, "1.00 GB"),
 677                     (1000*1000*1000*1000, "1.00 TB"),
 678                     (1000*1000*1000*1000*1000, "1.00 PB"),
 679                     (1234567890123456, "1.23 PB"),
 680                     ]
 681         for (x, expected) in tests_si:
 682             got = abbreviate.abbreviate_space(x, SI=True)
 683             self.failUnlessEqual(got, expected)
 684
 685         tests_base1024 = [(None, "unknown"),
 686                           (0, "0 B"),
 687                           (1, "1 B"),
 688                           (999, "999 B"),
 689                           (1000, "1000 B"),
 690                           (1023, "1023 B"),
 691                           (1024, "1.00 kiB"),
 692                           (20*1024, "20.00 kiB"),
 693                           (1000*1000, "976.56 kiB"),
 694                           (1024*1024, "1.00 MiB"),
 695                           (1024*1024*1024, "1.00 GiB"),
 696                           (1024*1024*1024*1024, "1.00 TiB"),
 697                           (1000*1000*1000*1000*1000, "909.49 TiB"),
 698                           (1024*1024*1024*1024*1024, "1.00 PiB"),
 699                           (1234567890123456, "1.10 PiB"),
 700                     ]
 701         for (x, expected) in tests_base1024:
 702             got = abbreviate.abbreviate_space(x, SI=False)
 703             self.failUnlessEqual(got, expected)
 704
 705         self.failUnlessEqual(abbreviate.abbreviate_space_both(1234567),
 706                              "(1.23 MB, 1.18 MiB)")
 707
 708     def test_parse_space(self):
 709         p = abbreviate.parse_abbreviated_size
 710         self.failUnlessEqual(p(""), None)
 711         self.failUnlessEqual(p(None), None)
 712         self.failUnlessEqual(p("123"), 123)
 713         self.failUnlessEqual(p("123B"), 123)
 714         self.failUnlessEqual(p("2K"), 2000)
 715         self.failUnlessEqual(p("2kb"), 2000)
 716         self.failUnlessEqual(p("2KiB"), 2048)
 717         self.failUnlessEqual(p("10MB"), 10*1000*1000)
 718         self.failUnlessEqual(p("10MiB"), 10*1024*1024)
 719         self.failUnlessEqual(p("5G"), 5*1000*1000*1000)
 720         self.failUnlessEqual(p("4GiB"), 4*1024*1024*1024)
 721         e = self.failUnlessRaises(ValueError, p, "12 cubits")
 722         self.failUnless("12 cubits" in str(e))
 723
 724 class Limiter(unittest.TestCase):
 725     timeout = 480 # This takes longer than 240 seconds on Francois's arm box.
 726
 727     def job(self, i, foo):
 728         self.calls.append( (i, foo) )
 729         self.simultaneous += 1
 730         self.peak_simultaneous = max(self.simultaneous, self.peak_simultaneous)
 731         d = defer.Deferred()
 732         def _done():
 733             self.simultaneous -= 1
 734             d.callback("done %d" % i)
 735         reactor.callLater(1.0, _done)
 736         return d
 737
 738     def bad_job(self, i, foo):
 739         raise ValueError("bad_job %d" % i)
 740
 741     def test_limiter(self):
 742         self.calls = []
 743         self.simultaneous = 0
 744         self.peak_simultaneous = 0
 745         l = limiter.ConcurrencyLimiter()
 746         dl = []
 747         for i in range(20):
 748             dl.append(l.add(self.job, i, foo=str(i)))
 749         d = defer.DeferredList(dl, fireOnOneErrback=True)
 750         def _done(res):
 751             self.failUnlessEqual(self.simultaneous, 0)
 752             self.failUnless(self.peak_simultaneous <= 10)
 753             self.failUnlessEqual(len(self.calls), 20)
 754             for i in range(20):
 755                 self.failUnless( (i, str(i)) in self.calls)
 756         d.addCallback(_done)
 757         return d
 758
 759     def test_errors(self):
 760         self.calls = []
 761         self.simultaneous = 0
 762         self.peak_simultaneous = 0
 763         l = limiter.ConcurrencyLimiter()
 764         dl = []
 765         for i in range(20):
 766             dl.append(l.add(self.job, i, foo=str(i)))
 767         d2 = l.add(self.bad_job, 21, "21")
 768         d = defer.DeferredList(dl, fireOnOneErrback=True)
 769         def _most_done(res):
 770             results = []
 771             for (success, result) in res:
 772                 self.failUnlessEqual(success, True)
 773                 results.append(result)
 774             results.sort()
 775             expected_results = ["done %d" % i for i in range(20)]
 776             expected_results.sort()
 777             self.failUnlessEqual(results, expected_results)
 778             self.failUnless(self.peak_simultaneous <= 10)
 779             self.failUnlessEqual(len(self.calls), 20)
 780             for i in range(20):
 781                 self.failUnless( (i, str(i)) in self.calls)
 782             def _good(res):
 783                 self.fail("should have failed, not got %s" % (res,))
 784             def _err(f):
 785                 f.trap(ValueError)
 786                 self.failUnless("bad_job 21" in str(f))
 787             d2.addCallbacks(_good, _err)
 788             return d2
 789         d.addCallback(_most_done)
 790         def _all_done(res):
 791             self.failUnlessEqual(self.simultaneous, 0)
 792             self.failUnless(self.peak_simultaneous <= 10)
 793             self.failUnlessEqual(len(self.calls), 20)
 794             for i in range(20):
 795                 self.failUnless( (i, str(i)) in self.calls)
 796         d.addCallback(_all_done)
 797         return d
 798
 799 class TimeFormat(unittest.TestCase):
 800     def test_epoch(self):
 801         return self._help_test_epoch()
 802
 803     def test_epoch_in_London(self):
 804         # Europe/London is a particularly troublesome timezone.  Nowadays, its
 805         # offset from GMT is 0.  But in 1970, its offset from GMT was 1.
 806         # (Apparently in 1970 Britain had redefined standard time to be GMT+1
 807         # and stayed in standard time all year round, whereas today
 808         # Europe/London standard time is GMT and Europe/London Daylight
 809         # Savings Time is GMT+1.)  The current implementation of
 810         # time_format.iso_utc_time_to_localseconds() breaks if the timezone is
 811         # Europe/London.  (As soon as this unit test is done then I'll change
 812         # that implementation to something that works even in this case...)
 813         origtz = os.environ.get('TZ')
 814         os.environ['TZ'] = "Europe/London"
 815         if hasattr(time, 'tzset'):
 816             time.tzset()
 817         try:
 818             return self._help_test_epoch()
 819         finally:
 820             if origtz is None:
 821                 del os.environ['TZ']
 822             else:
 823                 os.environ['TZ'] = origtz
 824             if hasattr(time, 'tzset'):
 825                 time.tzset()
 826
 827     def _help_test_epoch(self):
 828         origtzname = time.tzname
 829         s = time_format.iso_utc_time_to_seconds("1970-01-01T00:00:01")
 830         self.failUnlessEqual(s, 1.0)
 831         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01")
 832         self.failUnlessEqual(s, 1.0)
 833         s = time_format.iso_utc_time_to_seconds("1970-01-01 00:00:01")
 834         self.failUnlessEqual(s, 1.0)
 835
 836         self.failUnlessEqual(time_format.iso_utc(1.0), "1970-01-01_00:00:01")
 837         self.failUnlessEqual(time_format.iso_utc(1.0, sep=" "),
 838                              "1970-01-01 00:00:01")
 839
 840         now = time.time()
 841         isostr = time_format.iso_utc(now)
 842         timestamp = time_format.iso_utc_time_to_seconds(isostr)
 843         self.failUnlessEqual(int(timestamp), int(now))
 844
 845         def my_time():
 846             return 1.0
 847         self.failUnlessEqual(time_format.iso_utc(t=my_time),
 848                              "1970-01-01_00:00:01")
 849         e = self.failUnlessRaises(ValueError,
 850                                   time_format.iso_utc_time_to_seconds,
 851                                   "invalid timestring")
 852         self.failUnless("not a complete ISO8601 timestamp" in str(e))
 853         s = time_format.iso_utc_time_to_seconds("1970-01-01_00:00:01.500")
 854         self.failUnlessEqual(s, 1.5)
 855
 856         # Look for daylight-savings-related errors.
 857         thatmomentinmarch = time_format.iso_utc_time_to_seconds("2009-03-20 21:49:02.226536")
 858         self.failUnlessEqual(thatmomentinmarch, 1237585742.226536)
 859         self.failUnlessEqual(origtzname, time.tzname)
 860
 861 class CacheDir(unittest.TestCase):
 862     def test_basic(self):
 863         basedir = "test_util/CacheDir/test_basic"
 864
 865         def _failIfExists(name):
 866             absfn = os.path.join(basedir, name)
 867             self.failIf(os.path.exists(absfn),
 868                         "%s exists but it shouldn't" % absfn)
 869
 870         def _failUnlessExists(name):
 871             absfn = os.path.join(basedir, name)
 872             self.failUnless(os.path.exists(absfn),
 873                             "%s doesn't exist but it should" % absfn)
 874
 875         cdm = cachedir.CacheDirectoryManager(basedir)
 876         a = cdm.get_file("a")
 877         b = cdm.get_file("b")
 878         c = cdm.get_file("c")
 879         f = open(a.get_filename(), "wb"); f.write("hi"); f.close(); del f
 880         f = open(b.get_filename(), "wb"); f.write("hi"); f.close(); del f
 881         f = open(c.get_filename(), "wb"); f.write("hi"); f.close(); del f
 882
 883         _failUnlessExists("a")
 884         _failUnlessExists("b")
 885         _failUnlessExists("c")
 886
 887         cdm.check()
 888
 889         _failUnlessExists("a")
 890         _failUnlessExists("b")
 891         _failUnlessExists("c")
 892
 893         del a
 894         # this file won't be deleted yet, because it isn't old enough
 895         cdm.check()
 896         _failUnlessExists("a")
 897         _failUnlessExists("b")
 898         _failUnlessExists("c")
 899
 900         # we change the definition of "old" to make everything old
 901         cdm.old = -10
 902
 903         cdm.check()
 904         _failIfExists("a")
 905         _failUnlessExists("b")
 906         _failUnlessExists("c")
 907
 908         cdm.old = 60*60
 909
 910         del b
 911
 912         cdm.check()
 913         _failIfExists("a")
 914         _failUnlessExists("b")
 915         _failUnlessExists("c")
 916
 917         b2 = cdm.get_file("b")
 918
 919         cdm.check()
 920         _failIfExists("a")
 921         _failUnlessExists("b")
 922         _failUnlessExists("c")
 923
 924 ctr = [0]
 925 class EqButNotIs:
 926     def __init__(self, x):
 927         self.x = x
 928         self.hash = ctr[0]
 929         ctr[0] += 1
 930     def __repr__(self):
 931         return "<%s %s>" % (self.__class__.__name__, self.x,)
 932     def __hash__(self):
 933         return self.hash
 934     def __le__(self, other):
 935         return self.x <= other
 936     def __lt__(self, other):
 937         return self.x < other
 938     def __ge__(self, other):
 939         return self.x >= other
 940     def __gt__(self, other):
 941         return self.x > other
 942     def __ne__(self, other):
 943         return self.x != other
 944     def __eq__(self, other):
 945         return self.x == other
 946
 947 class DictUtil(unittest.TestCase):
 948     def _help_test_empty_dict(self, klass):
 949         d1 = klass()
 950         d2 = klass({})
 951
 952         self.failUnless(d1 == d2, "d1: %r, d2: %r" % (d1, d2,))
 953         self.failUnless(len(d1) == 0)
 954         self.failUnless(len(d2) == 0)
 955
 956     def _help_test_nonempty_dict(self, klass):
 957         d1 = klass({'a': 1, 'b': "eggs", 3: "spam",})
 958         d2 = klass({'a': 1, 'b': "eggs", 3: "spam",})
 959
 960         self.failUnless(d1 == d2)
 961         self.failUnless(len(d1) == 3, "%s, %s" % (len(d1), d1,))
 962         self.failUnless(len(d2) == 3)
 963
 964     def _help_test_eq_but_notis(self, klass):
 965         d = klass({'a': 3, 'b': EqButNotIs(3), 'c': 3})
 966         d.pop('b')
 967
 968         d.clear()
 969         d['a'] = 3
 970         d['b'] = EqButNotIs(3)
 971         d['c'] = 3
 972         d.pop('b')
 973
 974         d.clear()
 975         d['b'] = EqButNotIs(3)
 976         d['a'] = 3
 977         d['c'] = 3
 978         d.pop('b')
 979
 980         d.clear()
 981         d['a'] = EqButNotIs(3)
 982         d['c'] = 3
 983         d['a'] = 3
 984
 985         d.clear()
 986         fake3 = EqButNotIs(3)
 987         fake7 = EqButNotIs(7)
 988         d[fake3] = fake7
 989         d[3] = 7
 990         d[3] = 8
 991         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
 992         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
 993         # The real 7 should have been ejected by the d[3] = 8.
 994         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
 995         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
 996         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
 997         d[fake3] = 8
 998
 999         d.clear()
1000         d[3] = 7
1001         fake3 = EqButNotIs(3)
1002         fake7 = EqButNotIs(7)
1003         d[fake3] = fake7
1004         d[3] = 8
1005         self.failUnless(filter(lambda x: x is 8,  d.itervalues()))
1006         self.failUnless(filter(lambda x: x is fake7,  d.itervalues()))
1007         # The real 7 should have been ejected by the d[3] = 8.
1008         self.failUnless(not filter(lambda x: x is 7,  d.itervalues()))
1009         self.failUnless(filter(lambda x: x is fake3,  d.iterkeys()))
1010         self.failUnless(filter(lambda x: x is 3,  d.iterkeys()))
1011         d[fake3] = 8
1012
1013     def test_all(self):
1014         self._help_test_eq_but_notis(dictutil.UtilDict)
1015         self._help_test_eq_but_notis(dictutil.NumDict)
1016         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1017         self._help_test_nonempty_dict(dictutil.UtilDict)
1018         self._help_test_nonempty_dict(dictutil.NumDict)
1019         self._help_test_nonempty_dict(dictutil.ValueOrderedDict)
1020         self._help_test_eq_but_notis(dictutil.UtilDict)
1021         self._help_test_eq_but_notis(dictutil.NumDict)
1022         self._help_test_eq_but_notis(dictutil.ValueOrderedDict)
1023
1024     def test_dict_of_sets(self):
1025         ds = dictutil.DictOfSets()
1026         ds.add(1, "a")
1027         ds.add(2, "b")
1028         ds.add(2, "b")
1029         ds.add(2, "c")
1030         self.failUnlessEqual(ds[1], set(["a"]))
1031         self.failUnlessEqual(ds[2], set(["b", "c"]))
1032         ds.discard(3, "d") # should not raise an exception
1033         ds.discard(2, "b")
1034         self.failUnlessEqual(ds[2], set(["c"]))
1035         ds.discard(2, "c")
1036         self.failIf(2 in ds)
1037
1038         ds.union(1, ["a", "e"])
1039         ds.union(3, ["f"])
1040         self.failUnlessEqual(ds[1], set(["a","e"]))
1041         self.failUnlessEqual(ds[3], set(["f"]))
1042         ds2 = dictutil.DictOfSets()
1043         ds2.add(3, "f")
1044         ds2.add(3, "g")
1045         ds2.add(4, "h")
1046         ds.update(ds2)
1047         self.failUnlessEqual(ds[1], set(["a","e"]))
1048         self.failUnlessEqual(ds[3], set(["f", "g"]))
1049         self.failUnlessEqual(ds[4], set(["h"]))
1050
1051     def test_move(self):
1052         d1 = {1: "a", 2: "b"}
1053         d2 = {2: "c", 3: "d"}
1054         dictutil.move(1, d1, d2)
1055         self.failUnlessEqual(d1, {2: "b"})
1056         self.failUnlessEqual(d2, {1: "a", 2: "c", 3: "d"})
1057
1058         d1 = {1: "a", 2: "b"}
1059         d2 = {2: "c", 3: "d"}
1060         dictutil.move(2, d1, d2)
1061         self.failUnlessEqual(d1, {1: "a"})
1062         self.failUnlessEqual(d2, {2: "b", 3: "d"})
1063
1064         d1 = {1: "a", 2: "b"}
1065         d2 = {2: "c", 3: "d"}
1066         self.failUnlessRaises(KeyError, dictutil.move, 5, d1, d2, strict=True)
1067
1068     def test_subtract(self):
1069         d1 = {1: "a", 2: "b"}
1070         d2 = {2: "c", 3: "d"}
1071         d3 = dictutil.subtract(d1, d2)
1072         self.failUnlessEqual(d3, {1: "a"})
1073
1074         d1 = {1: "a", 2: "b"}
1075         d2 = {2: "c"}
1076         d3 = dictutil.subtract(d1, d2)
1077         self.failUnlessEqual(d3, {1: "a"})
1078
1079     def test_utildict(self):
1080         d = dictutil.UtilDict({1: "a", 2: "b"})
1081         d.del_if_present(1)
1082         d.del_if_present(3)
1083         self.failUnlessEqual(d, {2: "b"})
1084         def eq(a, b):
1085             return a == b
1086         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1087
1088         d = dictutil.UtilDict({1: "b", 2: "a"})
1089         self.failUnlessEqual(d.items_sorted_by_value(),
1090                              [(2, "a"), (1, "b")])
1091         self.failUnlessEqual(d.items_sorted_by_key(),
1092                              [(1, "b"), (2, "a")])
1093         self.failUnlessEqual(repr(d), "{1: 'b', 2: 'a'}")
1094         self.failUnless(1 in d)
1095
1096         d2 = dictutil.UtilDict({3: "c", 4: "d"})
1097         self.failUnless(d != d2)
1098         self.failUnless(d2 > d)
1099         self.failUnless(d2 >= d)
1100         self.failUnless(d <= d2)
1101         self.failUnless(d < d2)
1102         self.failUnlessEqual(d[1], "b")
1103         self.failUnlessEqual(sorted(list([k for k in d])), [1,2])
1104
1105         d3 = d.copy()
1106         self.failUnlessEqual(d, d3)
1107         self.failUnless(isinstance(d3, dictutil.UtilDict))
1108
1109         d4 = d.fromkeys([3,4], "e")
1110         self.failUnlessEqual(d4, {3: "e", 4: "e"})
1111
1112         self.failUnlessEqual(d.get(1), "b")
1113         self.failUnlessEqual(d.get(3), None)
1114         self.failUnlessEqual(d.get(3, "default"), "default")
1115         self.failUnlessEqual(sorted(list(d.items())),
1116                              [(1, "b"), (2, "a")])
1117         self.failUnlessEqual(sorted(list(d.iteritems())),
1118                              [(1, "b"), (2, "a")])
1119         self.failUnlessEqual(sorted(d.keys()), [1, 2])
1120         self.failUnlessEqual(sorted(d.values()), ["a", "b"])
1121         x = d.setdefault(1, "new")
1122         self.failUnlessEqual(x, "b")
1123         self.failUnlessEqual(d[1], "b")
1124         x = d.setdefault(3, "new")
1125         self.failUnlessEqual(x, "new")
1126         self.failUnlessEqual(d[3], "new")
1127         del d[3]
1128
1129         x = d.popitem()
1130         self.failUnless(x in [(1, "b"), (2, "a")])
1131         x = d.popitem()
1132         self.failUnless(x in [(1, "b"), (2, "a")])
1133         self.failUnlessRaises(KeyError, d.popitem)
1134
1135     def test_numdict(self):
1136         d = dictutil.NumDict({"a": 1, "b": 2})
1137
1138         d.add_num("a", 10, 5)
1139         d.add_num("c", 20, 5)
1140         d.add_num("d", 30)
1141         self.failUnlessEqual(d, {"a": 11, "b": 2, "c": 25, "d": 30})
1142
1143         d.subtract_num("a", 10)
1144         d.subtract_num("e", 10)
1145         d.subtract_num("f", 10, 15)
1146         self.failUnlessEqual(d, {"a": 1, "b": 2, "c": 25, "d": 30,
1147                                  "e": -10, "f": 5})
1148
1149         self.failUnlessEqual(d.sum(), sum([1, 2, 25, 30, -10, 5]))
1150
1151         d = dictutil.NumDict()
1152         d.inc("a")
1153         d.inc("a")
1154         d.inc("b", 5)
1155         self.failUnlessEqual(d, {"a": 2, "b": 6})
1156         d.dec("a")
1157         d.dec("c")
1158         d.dec("d", 5)
1159         self.failUnlessEqual(d, {"a": 1, "b": 6, "c": -1, "d": 4})
1160         self.failUnlessEqual(d.items_sorted_by_key(),
1161                              [("a", 1), ("b", 6), ("c", -1), ("d", 4)])
1162         self.failUnlessEqual(d.items_sorted_by_value(),
1163                              [("c", -1), ("a", 1), ("d", 4), ("b", 6)])
1164         self.failUnlessEqual(d.item_with_largest_value(), ("b", 6))
1165
1166         d = dictutil.NumDict({"a": 1, "b": 2})
1167         self.failUnlessEqual(repr(d), "{'a': 1, 'b': 2}")
1168         self.failUnless("a" in d)
1169
1170         d2 = dictutil.NumDict({"c": 3, "d": 4})
1171         self.failUnless(d != d2)
1172         self.failUnless(d2 > d)
1173         self.failUnless(d2 >= d)
1174         self.failUnless(d <= d2)
1175         self.failUnless(d < d2)
1176         self.failUnlessEqual(d["a"], 1)
1177         self.failUnlessEqual(sorted(list([k for k in d])), ["a","b"])
1178         def eq(a, b):
1179             return a == b
1180         self.failUnlessRaises(TypeError, eq, d, "not a dict")
1181
1182         d3 = d.copy()
1183         self.failUnlessEqual(d, d3)
1184         self.failUnless(isinstance(d3, dictutil.NumDict))
1185
1186         d4 = d.fromkeys(["a","b"], 5)
1187         self.failUnlessEqual(d4, {"a": 5, "b": 5})
1188
1189         self.failUnlessEqual(d.get("a"), 1)
1190         self.failUnlessEqual(d.get("c"), 0)
1191         self.failUnlessEqual(d.get("c", 5), 5)
1192         self.failUnlessEqual(sorted(list(d.items())),
1193                              [("a", 1), ("b", 2)])
1194         self.failUnlessEqual(sorted(list(d.iteritems())),
1195                              [("a", 1), ("b", 2)])
1196         self.failUnlessEqual(sorted(d.keys()), ["a", "b"])
1197         self.failUnlessEqual(sorted(d.values()), [1, 2])
1198         self.failUnless(d.has_key("a"))
1199         self.failIf(d.has_key("c"))
1200
1201         x = d.setdefault("c", 3)
1202         self.failUnlessEqual(x, 3)
1203         self.failUnlessEqual(d["c"], 3)
1204         x = d.setdefault("c", 5)
1205         self.failUnlessEqual(x, 3)
1206         self.failUnlessEqual(d["c"], 3)
1207         del d["c"]
1208
1209         x = d.popitem()
1210         self.failUnless(x in [("a", 1), ("b", 2)])
1211         x = d.popitem()
1212         self.failUnless(x in [("a", 1), ("b", 2)])
1213         self.failUnlessRaises(KeyError, d.popitem)
1214
1215         d.update({"c": 3})
1216         d.update({"c": 4, "d": 5})
1217         self.failUnlessEqual(d, {"c": 4, "d": 5})
1218
1219     def test_del_if_present(self):
1220         d = {1: "a", 2: "b"}
1221         dictutil.del_if_present(d, 1)
1222         dictutil.del_if_present(d, 3)
1223         self.failUnlessEqual(d, {2: "b"})
1224
1225     def test_valueordereddict(self):
1226         d = dictutil.ValueOrderedDict()
1227         d["a"] = 3
1228         d["b"] = 2
1229         d["c"] = 1
1230
1231         self.failUnlessEqual(d, {"a": 3, "b": 2, "c": 1})
1232         self.failUnlessEqual(d.items(), [("c", 1), ("b", 2), ("a", 3)])
1233         self.failUnlessEqual(d.values(), [1, 2, 3])
1234         self.failUnlessEqual(d.keys(), ["c", "b", "a"])
1235         self.failUnlessEqual(repr(d), "<ValueOrderedDict {c: 1, b: 2, a: 3}>")
1236         def eq(a, b):
1237             return a == b
1238         self.failIf(d == {"a": 4})
1239         self.failUnless(d != {"a": 4})
1240
1241         x = d.setdefault("d", 0)
1242         self.failUnlessEqual(x, 0)
1243         self.failUnlessEqual(d["d"], 0)
1244         x = d.setdefault("d", -1)
1245         self.failUnlessEqual(x, 0)
1246         self.failUnlessEqual(d["d"], 0)
1247
1248         x = d.remove("e", "default", False)
1249         self.failUnlessEqual(x, "default")
1250         self.failUnlessRaises(KeyError, d.remove, "e", "default", True)
1251         x = d.remove("d", 5)
1252         self.failUnlessEqual(x, 0)
1253
1254         x = d.__getitem__("c")
1255         self.failUnlessEqual(x, 1)
1256         x = d.__getitem__("e", "default", False)
1257         self.failUnlessEqual(x, "default")
1258         self.failUnlessRaises(KeyError, d.__getitem__, "e", "default", True)
1259
1260         self.failUnlessEqual(d.popitem(), ("c", 1))
1261         self.failUnlessEqual(d.popitem(), ("b", 2))
1262         self.failUnlessEqual(d.popitem(), ("a", 3))
1263         self.failUnlessRaises(KeyError, d.popitem)
1264
1265         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1266         x = d.pop("d", "default", False)
1267         self.failUnlessEqual(x, "default")
1268         self.failUnlessRaises(KeyError, d.pop, "d", "default", True)
1269         x = d.pop("b")
1270         self.failUnlessEqual(x, 2)
1271         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1272
1273         d = dictutil.ValueOrderedDict({"a": 3, "b": 2, "c": 1})
1274         x = d.pop_from_list(1) # pop the second item, b/2
1275         self.failUnlessEqual(x, "b")
1276         self.failUnlessEqual(d.items(), [("c", 1), ("a", 3)])
1277
1278     def test_auxdict(self):
1279         d = dictutil.AuxValueDict()
1280         # we put the serialized form in the auxdata
1281         d.set_with_aux("key", ("filecap", "metadata"), "serialized")
1282
1283         self.failUnlessEqual(d.keys(), ["key"])
1284         self.failUnlessEqual(d["key"], ("filecap", "metadata"))
1285         self.failUnlessEqual(d.get_aux("key"), "serialized")
1286         def _get_missing(key):
1287             return d[key]
1288         self.failUnlessRaises(KeyError, _get_missing, "nonkey")
1289         self.failUnlessEqual(d.get("nonkey"), None)
1290         self.failUnlessEqual(d.get("nonkey", "nonvalue"), "nonvalue")
1291         self.failUnlessEqual(d.get_aux("nonkey"), None)
1292         self.failUnlessEqual(d.get_aux("nonkey", "nonvalue"), "nonvalue")
1293
1294         d["key"] = ("filecap2", "metadata2")
1295         self.failUnlessEqual(d["key"], ("filecap2", "metadata2"))
1296         self.failUnlessEqual(d.get_aux("key"), None)
1297
1298         d.set_with_aux("key2", "value2", "aux2")
1299         self.failUnlessEqual(sorted(d.keys()), ["key", "key2"])
1300         del d["key2"]
1301         self.failUnlessEqual(d.keys(), ["key"])
1302         self.failIf("key2" in d)
1303         self.failUnlessRaises(KeyError, _get_missing, "key2")
1304         self.failUnlessEqual(d.get("key2"), None)
1305         self.failUnlessEqual(d.get_aux("key2"), None)
1306         d["key2"] = "newvalue2"
1307         self.failUnlessEqual(d.get("key2"), "newvalue2")
1308         self.failUnlessEqual(d.get_aux("key2"), None)
1309
1310         d = dictutil.AuxValueDict({1:2,3:4})
1311         self.failUnlessEqual(sorted(d.keys()), [1,3])
1312         self.failUnlessEqual(d[1], 2)
1313         self.failUnlessEqual(d.get_aux(1), None)
1314
1315         d = dictutil.AuxValueDict([ (1,2), (3,4) ])
1316         self.failUnlessEqual(sorted(d.keys()), [1,3])
1317         self.failUnlessEqual(d[1], 2)
1318         self.failUnlessEqual(d.get_aux(1), None)
1319
1320         d = dictutil.AuxValueDict(one=1, two=2)
1321         self.failUnlessEqual(sorted(d.keys()), ["one","two"])
1322         self.failUnlessEqual(d["one"], 1)
1323         self.failUnlessEqual(d.get_aux("one"), None)
1324
1325 class Pipeline(unittest.TestCase):
1326     def pause(self, *args, **kwargs):
1327         d = defer.Deferred()
1328         self.calls.append( (d, args, kwargs) )
1329         return d
1330
1331     def failUnlessCallsAre(self, expected):
1332         #print self.calls
1333         #print expected
1334         self.failUnlessEqual(len(self.calls), len(expected), self.calls)
1335         for i,c in enumerate(self.calls):
1336             self.failUnlessEqual(c[1:], expected[i], str(i))
1337
1338     def test_basic(self):
1339         self.calls = []
1340         finished = []
1341         p = pipeline.Pipeline(100)
1342
1343         d = p.flush() # fires immediately
1344         d.addCallbacks(finished.append, log.err)
1345         self.failUnlessEqual(len(finished), 1)
1346         finished = []
1347
1348         d = p.add(10, self.pause, "one")
1349         # the call should start right away, and our return Deferred should
1350         # fire right away
1351         d.addCallbacks(finished.append, log.err)
1352         self.failUnlessEqual(len(finished), 1)
1353         self.failUnlessEqual(finished[0], None)
1354         self.failUnlessCallsAre([ ( ("one",) , {} ) ])
1355         self.failUnlessEqual(p.gauge, 10)
1356
1357         # pipeline: [one]
1358
1359         finished = []
1360         d = p.add(20, self.pause, "two", kw=2)
1361         # pipeline: [one, two]
1362
1363         # the call and the Deferred should fire right away
1364         d.addCallbacks(finished.append, log.err)
1365         self.failUnlessEqual(len(finished), 1)
1366         self.failUnlessEqual(finished[0], None)
1367         self.failUnlessCallsAre([ ( ("one",) , {} ),
1368                                   ( ("two",) , {"kw": 2} ),
1369                                   ])
1370         self.failUnlessEqual(p.gauge, 30)
1371
1372         self.calls[0][0].callback("one-result")
1373         # pipeline: [two]
1374         self.failUnlessEqual(p.gauge, 20)
1375
1376         finished = []
1377         d = p.add(90, self.pause, "three", "posarg1")
1378         # pipeline: [two, three]
1379         flushed = []
1380         fd = p.flush()
1381         fd.addCallbacks(flushed.append, log.err)
1382         self.failUnlessEqual(flushed, [])
1383
1384         # the call will be made right away, but the return Deferred will not,
1385         # because the pipeline is now full.
1386         d.addCallbacks(finished.append, log.err)
1387         self.failUnlessEqual(len(finished), 0)
1388         self.failUnlessCallsAre([ ( ("one",) , {} ),
1389                                   ( ("two",) , {"kw": 2} ),
1390                                   ( ("three", "posarg1"), {} ),
1391                                   ])
1392         self.failUnlessEqual(p.gauge, 110)
1393
1394         self.failUnlessRaises(pipeline.SingleFileError, p.add, 10, self.pause)
1395
1396         # retiring either call will unblock the pipeline, causing the #3
1397         # Deferred to fire
1398         self.calls[2][0].callback("three-result")
1399         # pipeline: [two]
1400
1401         self.failUnlessEqual(len(finished), 1)
1402         self.failUnlessEqual(finished[0], None)
1403         self.failUnlessEqual(flushed, [])
1404
1405         # retiring call#2 will finally allow the flush() Deferred to fire
1406         self.calls[1][0].callback("two-result")
1407         self.failUnlessEqual(len(flushed), 1)
1408
1409     def test_errors(self):
1410         self.calls = []
1411         p = pipeline.Pipeline(100)
1412
1413         d1 = p.add(200, self.pause, "one")
1414         d2 = p.flush()
1415
1416         finished = []
1417         d1.addBoth(finished.append)
1418         self.failUnlessEqual(finished, [])
1419
1420         flushed = []
1421         d2.addBoth(flushed.append)
1422         self.failUnlessEqual(flushed, [])
1423
1424         self.calls[0][0].errback(ValueError("oops"))
1425
1426         self.failUnlessEqual(len(finished), 1)
1427         f = finished[0]
1428         self.failUnless(isinstance(f, Failure))
1429         self.failUnless(f.check(pipeline.PipelineError))
1430         self.failUnlessIn("PipelineError", str(f.value))
1431         self.failUnlessIn("ValueError", str(f.value))
1432         r = repr(f.value)
1433         self.failUnless("ValueError" in r, r)
1434         f2 = f.value.error
1435         self.failUnless(f2.check(ValueError))
1436
1437         self.failUnlessEqual(len(flushed), 1)
1438         f = flushed[0]
1439         self.failUnless(isinstance(f, Failure))
1440         self.failUnless(f.check(pipeline.PipelineError))
1441         f2 = f.value.error
1442         self.failUnless(f2.check(ValueError))
1443
1444         # now that the pipeline is in the failed state, any new calls will
1445         # fail immediately
1446
1447         d3 = p.add(20, self.pause, "two")
1448
1449         finished = []
1450         d3.addBoth(finished.append)
1451         self.failUnlessEqual(len(finished), 1)
1452         f = finished[0]
1453         self.failUnless(isinstance(f, Failure))
1454         self.failUnless(f.check(pipeline.PipelineError))
1455         r = repr(f.value)
1456         self.failUnless("ValueError" in r, r)
1457         f2 = f.value.error
1458         self.failUnless(f2.check(ValueError))
1459
1460         d4 = p.flush()
1461         flushed = []
1462         d4.addBoth(flushed.append)
1463         self.failUnlessEqual(len(flushed), 1)
1464         f = flushed[0]
1465         self.failUnless(isinstance(f, Failure))
1466         self.failUnless(f.check(pipeline.PipelineError))
1467         f2 = f.value.error
1468         self.failUnless(f2.check(ValueError))
1469
1470     def test_errors2(self):
1471         self.calls = []
1472         p = pipeline.Pipeline(100)
1473
1474         d1 = p.add(10, self.pause, "one")
1475         d2 = p.add(20, self.pause, "two")
1476         d3 = p.add(30, self.pause, "three")
1477         d4 = p.flush()
1478
1479         # one call fails, then the second one succeeds: make sure
1480         # ExpandableDeferredList tolerates the second one
1481
1482         flushed = []
1483         d4.addBoth(flushed.append)
1484         self.failUnlessEqual(flushed, [])
1485
1486         self.calls[0][0].errback(ValueError("oops"))
1487         self.failUnlessEqual(len(flushed), 1)
1488         f = flushed[0]
1489         self.failUnless(isinstance(f, Failure))
1490         self.failUnless(f.check(pipeline.PipelineError))
1491         f2 = f.value.error
1492         self.failUnless(f2.check(ValueError))
1493
1494         self.calls[1][0].callback("two-result")
1495         self.calls[2][0].errback(ValueError("three-error"))
1496
1497 class SampleError(Exception):
1498     pass
1499
1500 class Log(unittest.TestCase):
1501     def test_err(self):
1502         if not hasattr(self, "flushLoggedErrors"):
1503             # without flushLoggedErrors, we can't get rid of the
1504             # twisted.log.err that tahoe_log records, so we can't keep this
1505             # test from [ERROR]ing
1506             raise unittest.SkipTest("needs flushLoggedErrors from Twisted-2.5.0")
1507         try:
1508             raise SampleError("simple sample")
1509         except:
1510             f = Failure()
1511         tahoe_log.err(format="intentional sample error",
1512                       failure=f, level=tahoe_log.OPERATIONAL, umid="wO9UoQ")
1513         self.flushLoggedErrors(SampleError)