src/allmydata/test/test_util.py

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