← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-23 20:20:39 UTC
  • mto: This revision was merged to the branch mainline in revision 4522.
  • Revision ID: john@arbash-meinel.com-20090623202039-kr6mxu576z5vc4y5
Initial implementation of a Pyrex annotator.

Drops the time down to 8.6s down from 9.7s.
This implementation is basically just a copy of the python one, so I'm
a bit surprised to see that much of a win already.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
1
 
# Copyright (C) 2006-2010 Canonical Ltd
 
1
# Copyright (C) 2005, 2006, 2007, 2008 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
69
69
    lru_cache,
70
70
    pack,
71
71
    progress,
72
 
    static_tuple,
73
72
    trace,
74
73
    tsort,
75
74
    tuned_gzip,
76
 
    ui,
77
75
    )
78
76
""")
79
77
from bzrlib import (
1044
1042
        """See VersionedFiles.annotate."""
1045
1043
        return self._factory.annotate(self, key)
1046
1044
 
1047
 
    def get_annotator(self):
1048
 
        return _KnitAnnotator(self)
1049
 
 
1050
 
    def check(self, progress_bar=None, keys=None):
 
1045
    def check(self, progress_bar=None):
1051
1046
        """See VersionedFiles.check()."""
1052
 
        if keys is None:
1053
 
            return self._logical_check()
1054
 
        else:
1055
 
            # At the moment, check does not extra work over get_record_stream
1056
 
            return self.get_record_stream(keys, 'unordered', True)
1057
 
 
1058
 
    def _logical_check(self):
1059
1047
        # This doesn't actually test extraction of everything, but that will
1060
1048
        # impact 'bzr check' substantially, and needs to be integrated with
1061
1049
        # care. However, it does check for the obvious problem of a delta with
1192
1180
        generator = _VFContentMapGenerator(self, [key])
1193
1181
        return generator._get_content(key)
1194
1182
 
1195
 
    def get_known_graph_ancestry(self, keys):
1196
 
        """Get a KnownGraph instance with the ancestry of keys."""
1197
 
        parent_map, missing_keys = self._index.find_ancestry(keys)
1198
 
        for fallback in self._fallback_vfs:
1199
 
            if not missing_keys:
1200
 
                break
1201
 
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1202
 
                                                missing_keys)
1203
 
            parent_map.update(f_parent_map)
1204
 
            missing_keys = f_missing_keys
1205
 
        kg = _mod_graph.KnownGraph(parent_map)
1206
 
        return kg
1207
 
 
1208
1183
    def get_parent_map(self, keys):
1209
1184
        """Get a map of the graph parents of keys.
1210
1185
 
1511
1486
                                                                non_local_keys,
1512
1487
                                                                positions):
1513
1488
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1514
 
                                                   global_map,
1515
 
                                                   ordering=ordering)
 
1489
                                                   global_map)
1516
1490
                for record in generator.get_record_stream():
1517
1491
                    yield record
1518
1492
        else:
1520
1494
                if source is parent_maps[0]:
1521
1495
                    # this KnitVersionedFiles
1522
1496
                    records = [(key, positions[key][1]) for key in keys]
1523
 
                    for key, raw_data in self._read_records_iter_unchecked(records):
 
1497
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
1524
1498
                        (record_details, index_memo, _) = positions[key]
1525
1499
                        yield KnitContentFactory(key, global_map[key],
1526
 
                            record_details, None, raw_data, self._factory.annotated, None)
 
1500
                            record_details, sha1, raw_data, self._factory.annotated, None)
1527
1501
                else:
1528
1502
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1529
1503
                    for record in vf.get_record_stream(keys, ordering,
1598
1572
        # key = basis_parent, value = index entry to add
1599
1573
        buffered_index_entries = {}
1600
1574
        for record in stream:
1601
 
            kind = record.storage_kind
1602
 
            if kind.startswith('knit-') and kind.endswith('-gz'):
1603
 
                # Check that the ID in the header of the raw knit bytes matches
1604
 
                # the record metadata.
1605
 
                raw_data = record._raw_record
1606
 
                df, rec = self._parse_record_header(record.key, raw_data)
1607
 
                df.close()
1608
1575
            buffered = False
1609
1576
            parents = record.parents
1610
1577
            if record.storage_kind in delta_types:
1712
1679
            # There were index entries buffered at the end of the stream,
1713
1680
            # So these need to be added (if the index supports holding such
1714
1681
            # entries for later insertion)
1715
 
            all_entries = []
1716
1682
            for key in buffered_index_entries:
1717
1683
                index_entries = buffered_index_entries[key]
1718
 
                all_entries.extend(index_entries)
1719
 
            self._index.add_records(
1720
 
                all_entries, missing_compression_parents=True)
 
1684
                self._index.add_records(index_entries,
 
1685
                    missing_compression_parents=True)
1721
1686
 
1722
1687
    def get_missing_compression_parent_keys(self):
1723
1688
        """Return an iterable of keys of missing compression parents.
1756
1721
        :return: An iterator over (line, key).
1757
1722
        """
1758
1723
        if pb is None:
1759
 
            pb = ui.ui_factory.nested_progress_bar()
 
1724
            pb = progress.DummyProgress()
1760
1725
        keys = set(keys)
1761
1726
        total = len(keys)
1762
1727
        done = False
2025
1990
class _ContentMapGenerator(object):
2026
1991
    """Generate texts or expose raw deltas for a set of texts."""
2027
1992
 
2028
 
    def __init__(self, ordering='unordered'):
2029
 
        self._ordering = ordering
2030
 
 
2031
1993
    def _get_content(self, key):
2032
1994
        """Get the content object for key."""
2033
1995
        # Note that _get_content is only called when the _ContentMapGenerator
2067
2029
            # Loop over fallback repositories asking them for texts - ignore
2068
2030
            # any missing from a particular fallback.
2069
2031
            for record in source.get_record_stream(missing_keys,
2070
 
                self._ordering, True):
 
2032
                'unordered', True):
2071
2033
                if record.storage_kind == 'absent':
2072
2034
                    # Not in thie particular stream, may be in one of the
2073
2035
                    # other fallback vfs objects.
2205
2167
    """Content map generator reading from a VersionedFiles object."""
2206
2168
 
2207
2169
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2208
 
        global_map=None, raw_record_map=None, ordering='unordered'):
 
2170
        global_map=None, raw_record_map=None):
2209
2171
        """Create a _ContentMapGenerator.
2210
2172
 
2211
2173
        :param versioned_files: The versioned files that the texts are being
2219
2181
        :param raw_record_map: A unparsed raw record map to use for answering
2220
2182
            contents.
2221
2183
        """
2222
 
        _ContentMapGenerator.__init__(self, ordering=ordering)
2223
2184
        # The vf to source data from
2224
2185
        self.vf = versioned_files
2225
2186
        # The keys desired
2369
2330
    FLAGS is a comma separated list of flags about the record. Values include
2370
2331
        no-eol, line-delta, fulltext.
2371
2332
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2372
 
        that the compressed data starts at.
 
2333
        that the the compressed data starts at.
2373
2334
    LENGTH is the ascii representation of the length of the data file.
2374
2335
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2375
2336
        REVISION_ID.
2584
2545
        except KeyError:
2585
2546
            raise RevisionNotPresent(key, self)
2586
2547
 
2587
 
    def find_ancestry(self, keys):
2588
 
        """See CombinedGraphIndex.find_ancestry()"""
2589
 
        prefixes = set(key[:-1] for key in keys)
2590
 
        self._load_prefixes(prefixes)
2591
 
        result = {}
2592
 
        parent_map = {}
2593
 
        missing_keys = set()
2594
 
        pending_keys = list(keys)
2595
 
        # This assumes that keys will not reference parents in a different
2596
 
        # prefix, which is accurate so far.
2597
 
        while pending_keys:
2598
 
            key = pending_keys.pop()
2599
 
            if key in parent_map:
2600
 
                continue
2601
 
            prefix = key[:-1]
2602
 
            try:
2603
 
                suffix_parents = self._kndx_cache[prefix][0][key[-1]][4]
2604
 
            except KeyError:
2605
 
                missing_keys.add(key)
2606
 
            else:
2607
 
                parent_keys = tuple([prefix + (suffix,)
2608
 
                                     for suffix in suffix_parents])
2609
 
                parent_map[key] = parent_keys
2610
 
                pending_keys.extend([p for p in parent_keys
2611
 
                                        if p not in parent_map])
2612
 
        return parent_map, missing_keys
2613
 
 
2614
2548
    def get_parent_map(self, keys):
2615
2549
        """Get a map of the parents of keys.
2616
2550
 
2788
2722
 
2789
2723
class _KeyRefs(object):
2790
2724
 
2791
 
    def __init__(self, track_new_keys=False):
 
2725
    def __init__(self):
2792
2726
        # dict mapping 'key' to 'set of keys referring to that key'
2793
2727
        self.refs = {}
2794
 
        if track_new_keys:
2795
 
            # set remembering all new keys
2796
 
            self.new_keys = set()
2797
 
        else:
2798
 
            self.new_keys = None
2799
 
 
2800
 
    def clear(self):
2801
 
        if self.refs:
2802
 
            self.refs.clear()
2803
 
        if self.new_keys:
2804
 
            self.new_keys.clear()
2805
2728
 
2806
2729
    def add_references(self, key, refs):
2807
2730
        # Record the new references
2814
2737
        # Discard references satisfied by the new key
2815
2738
        self.add_key(key)
2816
2739
 
2817
 
    def get_new_keys(self):
2818
 
        return self.new_keys
2819
 
    
2820
2740
    def get_unsatisfied_refs(self):
2821
2741
        return self.refs.iterkeys()
2822
2742
 
2823
 
    def _satisfy_refs_for_key(self, key):
 
2743
    def add_key(self, key):
2824
2744
        try:
2825
2745
            del self.refs[key]
2826
2746
        except KeyError:
2827
2747
            # No keys depended on this key.  That's ok.
2828
2748
            pass
2829
2749
 
2830
 
    def add_key(self, key):
2831
 
        # satisfy refs for key, and remember that we've seen this key.
2832
 
        self._satisfy_refs_for_key(key)
2833
 
        if self.new_keys is not None:
2834
 
            self.new_keys.add(key)
2835
 
 
2836
 
    def satisfy_refs_for_keys(self, keys):
 
2750
    def add_keys(self, keys):
2837
2751
        for key in keys:
2838
 
            self._satisfy_refs_for_key(key)
 
2752
            self.add_key(key)
2839
2753
 
2840
2754
    def get_referrers(self):
2841
2755
        result = set()
2946
2860
        if not random_id:
2947
2861
            present_nodes = self._get_entries(keys)
2948
2862
            for (index, key, value, node_refs) in present_nodes:
2949
 
                parents = node_refs[:1]
2950
 
                # Sometimes these are passed as a list rather than a tuple
2951
 
                passed = static_tuple.as_tuples(keys[key])
2952
 
                passed_parents = passed[1][:1]
2953
2863
                if (value[0] != keys[key][0][0] or
2954
 
                    parents != passed_parents):
2955
 
                    node_refs = static_tuple.as_tuples(node_refs)
 
2864
                    node_refs[:1] != keys[key][1][:1]):
2956
2865
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2957
 
                        ": %s %s" % ((value, node_refs), passed))
 
2866
                        ": %s %s" % ((value, node_refs), keys[key]))
2958
2867
                del keys[key]
2959
2868
        result = []
2960
2869
        if self._parents:
3008
2917
        # If updating this, you should also update
3009
2918
        # groupcompress._GCGraphIndex.get_missing_parents
3010
2919
        # We may have false positives, so filter those out.
3011
 
        self._key_dependencies.satisfy_refs_for_keys(
 
2920
        self._key_dependencies.add_keys(
3012
2921
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
3013
2922
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
3014
2923
 
3125
3034
            options.append('no-eol')
3126
3035
        return options
3127
3036
 
3128
 
    def find_ancestry(self, keys):
3129
 
        """See CombinedGraphIndex.find_ancestry()"""
3130
 
        return self._graph_index.find_ancestry(keys, 0)
3131
 
 
3132
3037
    def get_parent_map(self, keys):
3133
3038
        """Get a map of the parents of keys.
3134
3039
 
3471
3376
        """
3472
3377
        pending = set([key])
3473
3378
        records = []
3474
 
        ann_keys = set()
 
3379
        generation = 0
 
3380
        kept_generation = 0
3475
3381
        self._num_needed_children[key] = 1
3476
3382
        while pending:
3477
3383
            # get all pending nodes
 
3384
            generation += 1
3478
3385
            this_iteration = pending
3479
3386
            build_details = self._vf._index.get_build_details(this_iteration)
3480
3387
            self._all_build_details.update(build_details)
3487
3394
                self._heads_provider = None
3488
3395
                records.append((key, index_memo))
3489
3396
                # Do we actually need to check _annotated_lines?
3490
 
                pending.update([p for p in parent_keys
3491
 
                                   if p not in self._all_build_details])
 
3397
                pending.update(p for p in parent_keys
 
3398
                                 if p not in self._all_build_details)
3492
3399
                if parent_keys:
3493
3400
                    for parent_key in parent_keys:
3494
3401
                        if parent_key in self._num_needed_children:
3503
3410
 
3504
3411
            missing_versions = this_iteration.difference(build_details.keys())
3505
3412
            if missing_versions:
3506
 
                for key in missing_versions:
3507
 
                    if key in self._parent_map and key in self._text_cache:
3508
 
                        # We already have this text ready, we just need to
3509
 
                        # yield it later so we get it annotated
3510
 
                        ann_keys.add(key)
3511
 
                        parent_keys = self._parent_map[key]
3512
 
                        for parent_key in parent_keys:
3513
 
                            if parent_key in self._num_needed_children:
3514
 
                                self._num_needed_children[parent_key] += 1
3515
 
                            else:
3516
 
                                self._num_needed_children[parent_key] = 1
3517
 
                        pending.update([p for p in parent_keys
3518
 
                                           if p not in self._all_build_details])
3519
 
                    else:
3520
 
                        raise errors.RevisionNotPresent(key, self._vf)
 
3413
                raise ValueError('i dont handle ghosts')
3521
3414
        # Generally we will want to read the records in reverse order, because
3522
3415
        # we find the parent nodes after the children
3523
3416
        records.reverse()
3524
 
        return records, ann_keys
 
3417
        return records
3525
3418
 
3526
3419
    def _get_needed_texts(self, key, pb=None):
3527
3420
        # if True or len(self._vf._fallback_vfs) > 0:
3532
3425
            return
3533
3426
        while True:
3534
3427
            try:
3535
 
                records, ann_keys = self._get_build_graph(key)
3536
 
                for idx, (sub_key, text, num_lines) in enumerate(
 
3428
                records = self._get_build_graph(key)
 
3429
                for idx, (key, text, num_lines) in enumerate(
3537
3430
                                                self._extract_texts(records)):
3538
3431
                    if pb is not None:
3539
3432
                        pb.update('annotating', idx, len(records))
3540
 
                    yield sub_key, text, num_lines
3541
 
                for sub_key in ann_keys:
3542
 
                    text = self._text_cache[sub_key]
3543
 
                    num_lines = len(text) # bad assumption
3544
 
                    yield sub_key, text, num_lines
 
3433
                    yield key, text, num_lines
3545
3434
                return
3546
3435
            except errors.RetryWithNewPacks, e:
3547
3436
                self._vf._access.reload_or_raise(e)
3624
3513
                lines = self._expand_record(child_key, parent_keys,
3625
3514
                                            compression_parent,
3626
3515
                                            record, record_details)
 
3516
                assert lines is not None
3627
3517
                if self._check_ready_for_annotations(child_key, parent_keys):
3628
3518
                    to_return.append(child_key)
3629
3519
        # Also check any children that are waiting for this parent to be
3686
3576
            # ghosts?
3687
3577
            details = self._all_build_details[key]
3688
3578
            (_, compression_parent, parent_keys, record_details) = details
 
3579
            assert parent_keys == self._parent_map[key]
3689
3580
            lines = self._expand_record(key, parent_keys, compression_parent,
3690
3581
                                        record, record_details)
3691
3582
            if lines is None:
3708
3599
                    to_process.extend(self._process_pending(key))
3709
3600
 
3710
3601
try:
3711
 
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
3712
 
except ImportError, e:
3713
 
    osutils.failed_to_load_extension(e)
 
3602
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
 
3603
except ImportError:
3714
3604
    from bzrlib._knit_load_data_py import _load_data_py as _load_data