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