← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__static_tuple.py

Things are ~ working again.

Man this is getting messy, I may have to change my mind again.

I tried to export the StaticTuple type only through _static_tuple_pyx.pyx
by using a little bit of trickery. However, you end up with a circular
import issue, and also I forgot to track down one place where I needed
to rename '_static_tuple_c' => '_static_tuple_type_c'.

The idea was that _static_tuple_type.c would *only* define the type,
and not any extra info. This way the code could be compiled with either
cython or pyrex and still get the 'better' StaticTuple object.

It ended up, overall, just being a multi-hour mess trying to get the
dependencies sorted out. By using a .pxd file, at least the basic
circular import problem was sorted out.

However at this point, you *have* to import _static_tuple_pyx before
_static_tuple_type_c or you get a segfault, and you have to import the
latter if you want to get direct access to the class.

So at this point I feel like I either need to:
 1) Go back to the way it was, and get rid of the circular import
 2) Finish the rest of the steps, bring everything into Cython
    and say 'if you want the memory improvements, then you have
    to compile with cython.'

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__static_tuple.py
34
34
    ]
35
35
    suite = loader.suiteClass()
36
36
    if CompiledStaticTuple.available():
37
 
        from bzrlib import _static_tuple_c
38
 
        scenarios.append(('C', {'module': _static_tuple_c}))
 
37
        from bzrlib import _static_tuple_pyx
 
38
        scenarios.append(('C', {'module': _static_tuple_pyx}))
39
39
    else:
40
40
        # the compiled module isn't available, so we add a failing test
41
41
        class FailWithoutFeature(tests.TestCase):
50
50
 
51
51
    def _probe(self):
52
52
        try:
53
 
            import bzrlib._static_tuple_c
 
53
            import bzrlib._static_tuple_pyx
54
54
        except ImportError:
55
55
            return False
56
56
        return True
57
57
 
58
58
    def feature_name(self):
59
 
        return 'bzrlib._static_tuple_c'
 
59
        return 'bzrlib._static_tuple_pyx'
60
60
 
61
61
CompiledStaticTuple = _CompiledStaticTuple()
62
62
 
372
372
        if self.module is _static_tuple_py:
373
373
            return
374
374
        self.assertIsNot(None, self.module._C_API)
 
375
 
 
376
 
 
377
 
 
378
class TestStaticTupleInterned(tests.TestCase):
 
379
 
 
380
    _test_needs_features = [CompiledStaticTuple]
 
381
 
 
382
    def assertIn(self, obj, container):
 
383
        self.assertTrue(obj in container,
 
384
            '%s not found in %s' % (obj, container))
 
385
 
 
386
    def assertNotIn(self, obj, container):
 
387
        self.assertTrue(obj not in container,
 
388
            'We found %s in %s' % (obj, container))
 
389
 
 
390
    def assertFillState(self, used, fill, mask, obj):
 
391
        self.assertEqual((used, fill, mask), (obj.used, obj.fill, obj.mask))
 
392
 
 
393
    def assertRefcount(self, count, obj):
 
394
        """Assert that the refcount for obj is what we expect.
 
395
 
 
396
        Note that this automatically adjusts for the fact that calling
 
397
        assertRefcount actually creates a new pointer, as does calling
 
398
        sys.getrefcount. So pass the expected value *before* the call.
 
399
        """
 
400
        # I don't understand why it is count+3 here, but it seems to be
 
401
        # correct. If I check in the calling function, with:
 
402
        # self.assertEqual(count+1, sys.getrefcount(obj))
 
403
        # Then it works fine. Something about passing it to assertRefcount is
 
404
        # actually double-incrementing (and decrementing) the refcount
 
405
        self.assertEqual(count+3, sys.getrefcount(obj))
 
406
 
 
407
    def test_initial(self):
 
408
        obj = _module.StaticTupleInterner()
 
409
        self.assertEqual(0, len(obj))
 
410
        st = StaticTuple('foo', 'bar')
 
411
        self.assertFillState(0, 0, 0x3ff, obj)
 
412
 
 
413
    def test__lookup(self):
 
414
        # The tuple hash function is rather good at entropy. For all integers
 
415
        # 0=>1023, hash((i,)) & 1023 maps to a unique output, and hash((i,j))
 
416
        # maps to all 1024 fields evenly.
 
417
        # However, hash((c,d))& 1023 for characters has an uneven distribution
 
418
        # of collisions, for example:
 
419
        #  ('a', 'a'), ('f', '4'), ('p', 'r'), ('q', '1'), ('F', 'T'),
 
420
        #  ('Q', 'Q'), ('V', 'd'), ('7', 'C')
 
421
        # all collide @ 643
 
422
        obj = _module.StaticTupleInterner()
 
423
        offset, val = obj._test_lookup(StaticTuple('a', 'a'))
 
424
        self.assertEqual(643, offset)
 
425
        self.assertEqual('<null>', val)
 
426
        offset, val = obj._test_lookup(StaticTuple('f', '4'))
 
427
        self.assertEqual(643, offset)
 
428
        self.assertEqual('<null>', val)
 
429
        offset, val = obj._test_lookup(StaticTuple('p', 'r'))
 
430
        self.assertEqual(643, offset)
 
431
        self.assertEqual('<null>', val)
 
432
 
 
433
    def test_get_set_del_with_collisions(self):
 
434
        obj = _module.StaticTupleInterner()
 
435
        k1 = StaticTuple('a', 'a')
 
436
        k2 = StaticTuple('f', '4') # collides
 
437
        k3 = StaticTuple('p', 'r')
 
438
        k4 = StaticTuple('q', '1')
 
439
        self.assertEqual((643, '<null>'), obj._test_lookup(k1))
 
440
        self.assertEqual((643, '<null>'), obj._test_lookup(k2))
 
441
        self.assertEqual((643, '<null>'), obj._test_lookup(k3))
 
442
        self.assertEqual((643, '<null>'), obj._test_lookup(k4))
 
443
        obj.add(k1)
 
444
        self.assertIn(k1, obj)
 
445
        self.assertNotIn(k2, obj)
 
446
        self.assertNotIn(k3, obj)
 
447
        self.assertNotIn(k4, obj)
 
448
        self.assertEqual((643, k1), obj._test_lookup(k1))
 
449
        self.assertEqual((787, '<null>'), obj._test_lookup(k2))
 
450
        self.assertEqual((787, '<null>'), obj._test_lookup(k3))
 
451
        self.assertEqual((787, '<null>'), obj._test_lookup(k4))
 
452
        self.assertIs(k1, obj[k1])
 
453
        obj.add(k2)
 
454
        self.assertIs(k2, obj[k2])
 
455
        self.assertEqual((643, k1), obj._test_lookup(k1))
 
456
        self.assertEqual((787, k2), obj._test_lookup(k2))
 
457
        self.assertEqual((660, '<null>'), obj._test_lookup(k3))
 
458
        # Even though k4 collides for the first couple of iterations, the hash
 
459
        # perturbation uses the full width hash (not just the masked value), so
 
460
        # it now diverges
 
461
        self.assertEqual((180, '<null>'), obj._test_lookup(k4))
 
462
        self.assertEqual((643, k1), obj._test_lookup(('a', 'a')))
 
463
        self.assertEqual((787, k2), obj._test_lookup(('f', '4')))
 
464
        self.assertEqual((660, '<null>'), obj._test_lookup(('p', 'r')))
 
465
        self.assertEqual((180, '<null>'), obj._test_lookup(('q', '1')))
 
466
        obj.add(k3)
 
467
        self.assertIs(k3, obj[k3])
 
468
        self.assertIn(k1, obj)
 
469
        self.assertIn(k2, obj)
 
470
        self.assertIn(k3, obj)
 
471
        self.assertNotIn(k4, obj)
 
472
 
 
473
        del obj[k1]
 
474
        self.assertEqual((643, '<dummy>'), obj._test_lookup(k1))
 
475
        self.assertEqual((787, k2), obj._test_lookup(k2))
 
476
        self.assertEqual((660, k3), obj._test_lookup(k3))
 
477
        self.assertEqual((643, '<dummy>'), obj._test_lookup(k4))
 
478
        self.assertNotIn(k1, obj)
 
479
        self.assertIn(k2, obj)
 
480
        self.assertIn(k3, obj)
 
481
        self.assertNotIn(k4, obj)
 
482
 
 
483
    def test_add(self):
 
484
        obj = _module.StaticTupleInterner()
 
485
        self.assertFillState(0, 0, 0x3ff, obj)
 
486
        k1 = StaticTuple('foo')
 
487
        self.assertRefcount(1, k1)
 
488
        self.assertIs(k1, obj.add(k1))
 
489
        self.assertFillState(1, 1, 0x3ff, obj)
 
490
        self.assertRefcount(2, k1)
 
491
        ktest = obj[k1]
 
492
        self.assertRefcount(3, k1)
 
493
        self.assertIs(k1, ktest)
 
494
        del ktest
 
495
        self.assertRefcount(2, k1)
 
496
        k2 = StaticTuple('foo')
 
497
        self.assertRefcount(1, k2)
 
498
        self.assertIsNot(k1, k2)
 
499
        # doesn't add anything, so the counters shouldn't be adjusted
 
500
        self.assertIs(k1, obj.add(k2))
 
501
        self.assertFillState(1, 1, 0x3ff, obj)
 
502
        self.assertRefcount(2, k1) # not changed
 
503
        self.assertRefcount(1, k2) # not incremented
 
504
        self.assertIs(k1, obj[k1])
 
505
        self.assertIs(k1, obj[k2])
 
506
        self.assertRefcount(2, k1)
 
507
        self.assertRefcount(1, k2)
 
508
        # Deleting an entry should remove the fill, but not the used
 
509
        del obj[k1]
 
510
        self.assertFillState(0, 1, 0x3ff, obj)
 
511
        self.assertRefcount(1, k1)
 
512
        k3 = StaticTuple('bar')
 
513
        self.assertRefcount(1, k3)
 
514
        self.assertIs(k3, obj.add(k3))
 
515
        self.assertFillState(1, 2, 0x3ff, obj)
 
516
        self.assertRefcount(2, k3)
 
517
        self.assertIs(k2, obj.add(k2))
 
518
        self.assertFillState(2, 2, 0x3ff, obj)
 
519
        self.assertRefcount(1, k1)
 
520
        self.assertRefcount(2, k2)
 
521
        self.assertRefcount(2, k3)
 
522
 
 
523
    def test_discard(self):
 
524
        obj = _module.StaticTupleInterner()
 
525
        k1 = StaticTuple('foo')
 
526
        k2 = StaticTuple('foo')
 
527
        k3 = StaticTuple('bar')
 
528
        self.assertRefcount(1, k1)
 
529
        self.assertRefcount(1, k2)
 
530
        self.assertRefcount(1, k3)
 
531
        obj.add(k1)
 
532
        self.assertRefcount(2, k1)
 
533
        self.assertEqual(0, obj.discard(k3))
 
534
        self.assertRefcount(1, k3)
 
535
        obj.add(k3)
 
536
        self.assertRefcount(2, k3)
 
537
        self.assertEqual(1, obj.discard(k3))
 
538
        self.assertRefcount(1, k3)
 
539
 
 
540
    def test__delitem__(self):
 
541
        obj = _module.StaticTupleInterner()
 
542
        k1 = StaticTuple('foo')
 
543
        k2 = StaticTuple('foo')
 
544
        k3 = StaticTuple('bar')
 
545
        self.assertRefcount(1, k1)
 
546
        self.assertRefcount(1, k2)
 
547
        self.assertRefcount(1, k3)
 
548
        obj.add(k1)
 
549
        self.assertRefcount(2, k1)
 
550
        self.assertRaises(KeyError, obj.__delitem__, k3)
 
551
        self.assertRefcount(1, k3)
 
552
        obj.add(k3)
 
553
        self.assertRefcount(2, k3)
 
554
        del obj[k3]
 
555
        self.assertRefcount(1, k3)
 
556
 
 
557
    def test__resize(self):
 
558
        obj = _module.StaticTupleInterner()
 
559
        k1 = StaticTuple('foo')
 
560
        k2 = StaticTuple('bar')
 
561
        k3 = StaticTuple('baz')
 
562
        obj.add(k1)
 
563
        obj.add(k2)
 
564
        obj.add(k3)
 
565
        del obj[k2]
 
566
        self.assertFillState(2, 3, 0x3ff, obj)
 
567
        self.assertEqual(1024, obj._resize(500))
 
568
        # Doesn't change the size, but does change the content
 
569
        self.assertFillState(2, 2, 0x3ff, obj)
 
570
        obj.add(k2)
 
571
        del obj[k3]
 
572
        self.assertFillState(2, 3, 0x3ff, obj)
 
573
        self.assertEqual(4096, obj._resize(4095))
 
574
        self.assertFillState(2, 2, 0xfff, obj)
 
575
        self.assertIn(k1, obj)
 
576
        self.assertIn(k2, obj)
 
577
        self.assertNotIn(k3, obj)
 
578
        obj.add(k2)
 
579
        self.assertIn(k2, obj)
 
580
        del obj[k2]
 
581
        self.assertEqual((591, '<dummy>'), obj._test_lookup(k2))
 
582
        self.assertFillState(1, 2, 0xfff, obj)
 
583
        self.assertEqual(2048, obj._resize(1024))
 
584
        self.assertFillState(1, 1, 0x7ff, obj)
 
585
        self.assertEqual((591, '<null>'), obj._test_lookup(k2))
 
586
 
 
587
    def test_add_and_remove_lots_of_items(self):
 
588
        obj = _module.StaticTupleInterner()
 
589
        chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890'
 
590
        for i in chars:
 
591
            for j in chars:
 
592
                k = StaticTuple(i, j)
 
593
                obj.add(k)
 
594
        num = len(chars)*len(chars)
 
595
        self.assertFillState(num, num, 0x1fff, obj)
 
596
        # Now delete all of the entries and it should shrink again
 
597
        for i in chars:
 
598
            for j in chars:
 
599
                k = StaticTuple(i, j)
 
600
                obj.discard(k)
 
601
        # It should be back to 1024 wide mask, though there may still be some
 
602
        # dummy values in there
 
603
        self.assertFillState(0, obj.fill, 0x3ff, obj)
 
604
        # but there should be fewer than 1/5th dummy entries
 
605
        self.assertTrue(obj.fill < 1024 / 5)
 
606
 
 
607
    def test__iter__(self):
 
608
        obj = _module.StaticTupleInterner()
 
609
        k1 = StaticTuple('1')
 
610
        k2 = StaticTuple('1', '2')
 
611
        k3 = StaticTuple('3', '4')
 
612
        obj.add(k1)
 
613
        obj.add(k2)
 
614
        obj.add(k3)
 
615
        all = set()
 
616
        for key in obj:
 
617
            all.add(key)
 
618
        self.assertEqual(sorted([k1, k2, k3]), sorted(all))
 
619
        iterator = iter(obj)
 
620
        iterator.next()
 
621
        obj.add(StaticTuple('foo'))
 
622
        # Set changed size
 
623
        self.assertRaises(RuntimeError, iterator.next)
 
624
        # And even removing an item still causes it to fail
 
625
        del obj[k2]
 
626
        self.assertRaises(RuntimeError, iterator.next)