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