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