← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-09-01 08:02:42 UTC
  • mfrom: (5390.3.3 faster-revert-593560)
  • Revision ID: pqm@pqm.ubuntu.com-20100901080242-esg62ody4frwmy66
(spiv) Avoid repeatedly calling self.target.all_file_ids() in
 InterTree.iter_changes. (Andrew Bennetts)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
1
 
# Copyright (C) 2005, 2006, 2007, 2008 Canonical Ltd
 
1
# Copyright (C) 2006-2010 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
68
68
    index as _mod_index,
69
69
    lru_cache,
70
70
    pack,
 
71
    patiencediff,
71
72
    progress,
 
73
    static_tuple,
72
74
    trace,
73
75
    tsort,
74
76
    tuned_gzip,
 
77
    ui,
75
78
    )
76
79
""")
77
80
from bzrlib import (
78
81
    errors,
79
82
    osutils,
80
 
    patiencediff,
81
83
    )
82
84
from bzrlib.errors import (
83
85
    FileExists,
1045
1047
    def get_annotator(self):
1046
1048
        return _KnitAnnotator(self)
1047
1049
 
1048
 
    def check(self, progress_bar=None):
 
1050
    def check(self, progress_bar=None, keys=None):
1049
1051
        """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):
1050
1059
        # This doesn't actually test extraction of everything, but that will
1051
1060
        # impact 'bzr check' substantially, and needs to be integrated with
1052
1061
        # care. However, it does check for the obvious problem of a delta with
1183
1192
        generator = _VFContentMapGenerator(self, [key])
1184
1193
        return generator._get_content(key)
1185
1194
 
 
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
 
1186
1208
    def get_parent_map(self, keys):
1187
1209
        """Get a map of the graph parents of keys.
1188
1210
 
1489
1511
                                                                non_local_keys,
1490
1512
                                                                positions):
1491
1513
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1492
 
                                                   global_map)
 
1514
                                                   global_map,
 
1515
                                                   ordering=ordering)
1493
1516
                for record in generator.get_record_stream():
1494
1517
                    yield record
1495
1518
        else:
1497
1520
                if source is parent_maps[0]:
1498
1521
                    # this KnitVersionedFiles
1499
1522
                    records = [(key, positions[key][1]) for key in keys]
1500
 
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
 
1523
                    for key, raw_data in self._read_records_iter_unchecked(records):
1501
1524
                        (record_details, index_memo, _) = positions[key]
1502
1525
                        yield KnitContentFactory(key, global_map[key],
1503
 
                            record_details, sha1, raw_data, self._factory.annotated, None)
 
1526
                            record_details, None, raw_data, self._factory.annotated, None)
1504
1527
                else:
1505
1528
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1506
1529
                    for record in vf.get_record_stream(keys, ordering,
1575
1598
        # key = basis_parent, value = index entry to add
1576
1599
        buffered_index_entries = {}
1577
1600
        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()
1578
1608
            buffered = False
1579
1609
            parents = record.parents
1580
1610
            if record.storage_kind in delta_types:
1682
1712
            # There were index entries buffered at the end of the stream,
1683
1713
            # So these need to be added (if the index supports holding such
1684
1714
            # entries for later insertion)
 
1715
            all_entries = []
1685
1716
            for key in buffered_index_entries:
1686
1717
                index_entries = buffered_index_entries[key]
1687
 
                self._index.add_records(index_entries,
1688
 
                    missing_compression_parents=True)
 
1718
                all_entries.extend(index_entries)
 
1719
            self._index.add_records(
 
1720
                all_entries, missing_compression_parents=True)
1689
1721
 
1690
1722
    def get_missing_compression_parent_keys(self):
1691
1723
        """Return an iterable of keys of missing compression parents.
1724
1756
        :return: An iterator over (line, key).
1725
1757
        """
1726
1758
        if pb is None:
1727
 
            pb = progress.DummyProgress()
 
1759
            pb = ui.ui_factory.nested_progress_bar()
1728
1760
        keys = set(keys)
1729
1761
        total = len(keys)
1730
1762
        done = False
1993
2025
class _ContentMapGenerator(object):
1994
2026
    """Generate texts or expose raw deltas for a set of texts."""
1995
2027
 
 
2028
    def __init__(self, ordering='unordered'):
 
2029
        self._ordering = ordering
 
2030
 
1996
2031
    def _get_content(self, key):
1997
2032
        """Get the content object for key."""
1998
2033
        # Note that _get_content is only called when the _ContentMapGenerator
2032
2067
            # Loop over fallback repositories asking them for texts - ignore
2033
2068
            # any missing from a particular fallback.
2034
2069
            for record in source.get_record_stream(missing_keys,
2035
 
                'unordered', True):
 
2070
                self._ordering, True):
2036
2071
                if record.storage_kind == 'absent':
2037
2072
                    # Not in thie particular stream, may be in one of the
2038
2073
                    # other fallback vfs objects.
2170
2205
    """Content map generator reading from a VersionedFiles object."""
2171
2206
 
2172
2207
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2173
 
        global_map=None, raw_record_map=None):
 
2208
        global_map=None, raw_record_map=None, ordering='unordered'):
2174
2209
        """Create a _ContentMapGenerator.
2175
2210
 
2176
2211
        :param versioned_files: The versioned files that the texts are being
2184
2219
        :param raw_record_map: A unparsed raw record map to use for answering
2185
2220
            contents.
2186
2221
        """
 
2222
        _ContentMapGenerator.__init__(self, ordering=ordering)
2187
2223
        # The vf to source data from
2188
2224
        self.vf = versioned_files
2189
2225
        # The keys desired
2333
2369
    FLAGS is a comma separated list of flags about the record. Values include
2334
2370
        no-eol, line-delta, fulltext.
2335
2371
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2336
 
        that the the compressed data starts at.
 
2372
        that the compressed data starts at.
2337
2373
    LENGTH is the ascii representation of the length of the data file.
2338
2374
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2339
2375
        REVISION_ID.
2548
2584
        except KeyError:
2549
2585
            raise RevisionNotPresent(key, self)
2550
2586
 
 
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
 
2551
2614
    def get_parent_map(self, keys):
2552
2615
        """Get a map of the parents of keys.
2553
2616
 
2725
2788
 
2726
2789
class _KeyRefs(object):
2727
2790
 
2728
 
    def __init__(self):
 
2791
    def __init__(self, track_new_keys=False):
2729
2792
        # dict mapping 'key' to 'set of keys referring to that key'
2730
2793
        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()
2731
2805
 
2732
2806
    def add_references(self, key, refs):
2733
2807
        # Record the new references
2740
2814
        # Discard references satisfied by the new key
2741
2815
        self.add_key(key)
2742
2816
 
 
2817
    def get_new_keys(self):
 
2818
        return self.new_keys
 
2819
    
2743
2820
    def get_unsatisfied_refs(self):
2744
2821
        return self.refs.iterkeys()
2745
2822
 
2746
 
    def add_key(self, key):
 
2823
    def _satisfy_refs_for_key(self, key):
2747
2824
        try:
2748
2825
            del self.refs[key]
2749
2826
        except KeyError:
2750
2827
            # No keys depended on this key.  That's ok.
2751
2828
            pass
2752
2829
 
2753
 
    def add_keys(self, keys):
 
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):
2754
2837
        for key in keys:
2755
 
            self.add_key(key)
 
2838
            self._satisfy_refs_for_key(key)
2756
2839
 
2757
2840
    def get_referrers(self):
2758
2841
        result = set()
2863
2946
        if not random_id:
2864
2947
            present_nodes = self._get_entries(keys)
2865
2948
            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]
2866
2953
                if (value[0] != keys[key][0][0] or
2867
 
                    node_refs[:1] != keys[key][1][:1]):
 
2954
                    parents != passed_parents):
 
2955
                    node_refs = static_tuple.as_tuples(node_refs)
2868
2956
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2869
 
                        ": %s %s" % ((value, node_refs), keys[key]))
 
2957
                        ": %s %s" % ((value, node_refs), passed))
2870
2958
                del keys[key]
2871
2959
        result = []
2872
2960
        if self._parents:
2920
3008
        # If updating this, you should also update
2921
3009
        # groupcompress._GCGraphIndex.get_missing_parents
2922
3010
        # We may have false positives, so filter those out.
2923
 
        self._key_dependencies.add_keys(
 
3011
        self._key_dependencies.satisfy_refs_for_keys(
2924
3012
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2925
3013
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
2926
3014
 
3037
3125
            options.append('no-eol')
3038
3126
        return options
3039
3127
 
 
3128
    def find_ancestry(self, keys):
 
3129
        """See CombinedGraphIndex.find_ancestry()"""
 
3130
        return self._graph_index.find_ancestry(keys, 0)
 
3131
 
3040
3132
    def get_parent_map(self, keys):
3041
3133
        """Get a map of the parents of keys.
3042
3134
 
3325
3417
            raise exc_class, exc_value, exc_traceback
3326
3418
 
3327
3419
 
3328
 
# Deprecated, use PatienceSequenceMatcher instead
3329
 
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
3330
 
 
3331
 
 
3332
3420
def annotate_knit(knit, revision_id):
3333
3421
    """Annotate a knit with no cached annotations.
3334
3422
 
3616
3704
                    to_process.extend(self._process_pending(key))
3617
3705
 
3618
3706
try:
3619
 
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
3620
 
except ImportError:
 
3707
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
 
3708
except ImportError, e:
 
3709
    osutils.failed_to_load_extension(e)
3621
3710
    from bzrlib._knit_load_data_py import _load_data_py as _load_data