← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Ian Clatworthy
  • Date: 2009-07-23 00:24:30 UTC
  • mfrom: (4371.6.5 bzr.mv_after)
  • mto: This revision was merged to the branch mainline in revision 4561.
  • Revision ID: ian.clatworthy@canonical.com-20090723002430-70me272jpp3uss7i
(igc) Allow rename of items already removed from the inventory (Marius Kruger)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
1
 
# Copyright (C) 2006-2011 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
56
56
from itertools import izip
57
57
import operator
58
58
import os
 
59
import sys
59
60
 
60
61
from bzrlib.lazy_import import lazy_import
61
62
lazy_import(globals(), """
62
 
import gzip
63
 
 
64
63
from bzrlib import (
 
64
    annotate,
65
65
    debug,
66
66
    diff,
67
67
    graph as _mod_graph,
68
68
    index as _mod_index,
 
69
    lru_cache,
69
70
    pack,
70
 
    patiencediff,
71
 
    static_tuple,
 
71
    progress,
72
72
    trace,
73
73
    tsort,
74
74
    tuned_gzip,
75
 
    ui,
76
75
    )
77
 
 
78
 
from bzrlib.repofmt import pack_repo
79
76
""")
80
77
from bzrlib import (
81
 
    annotate,
82
78
    errors,
83
79
    osutils,
 
80
    patiencediff,
84
81
    )
85
82
from bzrlib.errors import (
 
83
    FileExists,
86
84
    NoSuchFile,
 
85
    KnitError,
87
86
    InvalidRevisionId,
88
87
    KnitCorrupt,
89
88
    KnitHeaderError,
90
89
    RevisionNotPresent,
 
90
    RevisionAlreadyPresent,
91
91
    SHA1KnitCorrupt,
92
92
    )
93
93
from bzrlib.osutils import (
94
94
    contains_whitespace,
 
95
    contains_linebreaks,
95
96
    sha_string,
96
97
    sha_strings,
97
98
    split_lines,
98
99
    )
99
100
from bzrlib.versionedfile import (
100
 
    _KeyRefs,
101
101
    AbsentContentFactory,
102
102
    adapter_registry,
103
103
    ConstantMapper,
104
104
    ContentFactory,
 
105
    ChunkedContentFactory,
105
106
    sort_groupcompress,
106
 
    VersionedFilesWithFallbacks,
 
107
    VersionedFile,
 
108
    VersionedFiles,
107
109
    )
108
110
 
109
111
 
408
410
class KnitContent(object):
409
411
    """Content of a knit version to which deltas can be applied.
410
412
 
411
 
    This is always stored in memory as a list of lines with \\n at the end,
 
413
    This is always stored in memory as a list of lines with \n at the end,
412
414
    plus a flag saying if the final ending is really there or not, because that
413
415
    corresponds to the on-disk knit representation.
414
416
    """
801
803
        writer.begin()
802
804
        index = _KnitGraphIndex(graph_index, lambda:True, parents=parents,
803
805
            deltas=delta, add_callback=graph_index.add_nodes)
804
 
        access = pack_repo._DirectPackAccess({})
 
806
        access = _DirectPackAccess({})
805
807
        access.set_writer(writer, graph_index, (transport, 'newpack'))
806
808
        result = KnitVersionedFiles(index, access,
807
809
            max_delta_chain=max_delta_chain)
845
847
                in all_build_index_memos.itervalues()])
846
848
 
847
849
 
848
 
class KnitVersionedFiles(VersionedFilesWithFallbacks):
 
850
class KnitVersionedFiles(VersionedFiles):
849
851
    """Storage for many versioned files using knit compression.
850
852
 
851
853
    Backend storage is managed by indices and data objects.
878
880
            self._factory = KnitAnnotateFactory()
879
881
        else:
880
882
            self._factory = KnitPlainFactory()
881
 
        self._immediate_fallback_vfs = []
 
883
        self._fallback_vfs = []
882
884
        self._reload_func = reload_func
883
885
 
884
886
    def __repr__(self):
887
889
            self._index,
888
890
            self._access)
889
891
 
890
 
    def without_fallbacks(self):
891
 
        """Return a clone of this object without any fallbacks configured."""
892
 
        return KnitVersionedFiles(self._index, self._access,
893
 
            self._max_delta_chain, self._factory.annotated,
894
 
            self._reload_func)
895
 
 
896
892
    def add_fallback_versioned_files(self, a_versioned_files):
897
893
        """Add a source of texts for texts not present in this knit.
898
894
 
899
895
        :param a_versioned_files: A VersionedFiles object.
900
896
        """
901
 
        self._immediate_fallback_vfs.append(a_versioned_files)
 
897
        self._fallback_vfs.append(a_versioned_files)
902
898
 
903
899
    def add_lines(self, key, parents, lines, parent_texts=None,
904
900
        left_matching_blocks=None, nostore_sha=None, random_id=False,
1049
1045
    def get_annotator(self):
1050
1046
        return _KnitAnnotator(self)
1051
1047
 
1052
 
    def check(self, progress_bar=None, keys=None):
 
1048
    def check(self, progress_bar=None):
1053
1049
        """See VersionedFiles.check()."""
1054
 
        if keys is None:
1055
 
            return self._logical_check()
1056
 
        else:
1057
 
            # At the moment, check does not extra work over get_record_stream
1058
 
            return self.get_record_stream(keys, 'unordered', True)
1059
 
 
1060
 
    def _logical_check(self):
1061
1050
        # This doesn't actually test extraction of everything, but that will
1062
1051
        # impact 'bzr check' substantially, and needs to be integrated with
1063
1052
        # care. However, it does check for the obvious problem of a delta with
1071
1060
                    raise errors.KnitCorrupt(self,
1072
1061
                        "Missing basis parent %s for %s" % (
1073
1062
                        compression_parent, key))
1074
 
        for fallback_vfs in self._immediate_fallback_vfs:
 
1063
        for fallback_vfs in self._fallback_vfs:
1075
1064
            fallback_vfs.check()
1076
1065
 
1077
1066
    def _check_add(self, key, lines, random_id, check_content):
1155
1144
 
1156
1145
        A dict of key to (record_details, index_memo, next, parents) is
1157
1146
        returned.
1158
 
 
1159
 
        * method is the way referenced data should be applied.
1160
 
        * index_memo is the handle to pass to the data access to actually get
1161
 
          the data
1162
 
        * next is the build-parent of the version, or None for fulltexts.
1163
 
        * parents is the version_ids of the parents of this version
1164
 
 
1165
 
        :param allow_missing: If True do not raise an error on a missing
1166
 
            component, just ignore it.
 
1147
        method is the way referenced data should be applied.
 
1148
        index_memo is the handle to pass to the data access to actually get the
 
1149
            data
 
1150
        next is the build-parent of the version, or None for fulltexts.
 
1151
        parents is the version_ids of the parents of this version
 
1152
 
 
1153
        :param allow_missing: If True do not raise an error on a missing component,
 
1154
            just ignore it.
1167
1155
        """
1168
1156
        component_data = {}
1169
1157
        pending_components = keys
1215
1203
            and so on.
1216
1204
        """
1217
1205
        result = {}
1218
 
        sources = [self._index] + self._immediate_fallback_vfs
 
1206
        sources = [self._index] + self._fallback_vfs
1219
1207
        source_results = []
1220
1208
        missing = set(keys)
1221
1209
        for source in sources:
1231
1219
        """Produce a dictionary of knit records.
1232
1220
 
1233
1221
        :return: {key:(record, record_details, digest, next)}
1234
 
 
1235
 
            * record: data returned from read_records (a KnitContentobject)
1236
 
            * record_details: opaque information to pass to parse_record
1237
 
            * digest: SHA1 digest of the full text after all steps are done
1238
 
            * next: build-parent of the version, i.e. the leftmost ancestor.
 
1222
            record
 
1223
                data returned from read_records (a KnitContentobject)
 
1224
            record_details
 
1225
                opaque information to pass to parse_record
 
1226
            digest
 
1227
                SHA1 digest of the full text after all steps are done
 
1228
            next
 
1229
                build-parent of the version, i.e. the leftmost ancestor.
1239
1230
                Will be None if the record is not a delta.
1240
 
 
1241
1231
        :param keys: The keys to build a map for
1242
1232
        :param allow_missing: If some records are missing, rather than
1243
1233
            error, just return the data that could be generated.
1499
1489
                                                                non_local_keys,
1500
1490
                                                                positions):
1501
1491
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1502
 
                                                   global_map,
1503
 
                                                   ordering=ordering)
 
1492
                                                   global_map)
1504
1493
                for record in generator.get_record_stream():
1505
1494
                    yield record
1506
1495
        else:
1508
1497
                if source is parent_maps[0]:
1509
1498
                    # this KnitVersionedFiles
1510
1499
                    records = [(key, positions[key][1]) for key in keys]
1511
 
                    for key, raw_data in self._read_records_iter_unchecked(records):
 
1500
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
1512
1501
                        (record_details, index_memo, _) = positions[key]
1513
1502
                        yield KnitContentFactory(key, global_map[key],
1514
 
                            record_details, None, raw_data, self._factory.annotated, None)
 
1503
                            record_details, sha1, raw_data, self._factory.annotated, None)
1515
1504
                else:
1516
 
                    vf = self._immediate_fallback_vfs[parent_maps.index(source) - 1]
 
1505
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1517
1506
                    for record in vf.get_record_stream(keys, ordering,
1518
1507
                        include_delta_closure):
1519
1508
                        yield record
1529
1518
            # record entry 2 is the 'digest'.
1530
1519
            result[key] = details[2]
1531
1520
        missing.difference_update(set(result))
1532
 
        for source in self._immediate_fallback_vfs:
 
1521
        for source in self._fallback_vfs:
1533
1522
            if not missing:
1534
1523
                break
1535
1524
            new_result = source.get_sha1s(missing)
1586
1575
        # key = basis_parent, value = index entry to add
1587
1576
        buffered_index_entries = {}
1588
1577
        for record in stream:
1589
 
            kind = record.storage_kind
1590
 
            if kind.startswith('knit-') and kind.endswith('-gz'):
1591
 
                # Check that the ID in the header of the raw knit bytes matches
1592
 
                # the record metadata.
1593
 
                raw_data = record._raw_record
1594
 
                df, rec = self._parse_record_header(record.key, raw_data)
1595
 
                df.close()
1596
1578
            buffered = False
1597
1579
            parents = record.parents
1598
1580
            if record.storage_kind in delta_types:
1606
1588
                raise RevisionNotPresent([record.key], self)
1607
1589
            elif ((record.storage_kind in knit_types)
1608
1590
                  and (compression_parent is None
1609
 
                       or not self._immediate_fallback_vfs
 
1591
                       or not self._fallback_vfs
1610
1592
                       or self._index.has_key(compression_parent)
1611
1593
                       or not self.has_key(compression_parent))):
1612
1594
                # we can insert the knit record literally if either it has no
1700
1682
            # There were index entries buffered at the end of the stream,
1701
1683
            # So these need to be added (if the index supports holding such
1702
1684
            # entries for later insertion)
1703
 
            all_entries = []
1704
1685
            for key in buffered_index_entries:
1705
1686
                index_entries = buffered_index_entries[key]
1706
 
                all_entries.extend(index_entries)
1707
 
            self._index.add_records(
1708
 
                all_entries, missing_compression_parents=True)
 
1687
                self._index.add_records(index_entries,
 
1688
                    missing_compression_parents=True)
1709
1689
 
1710
1690
    def get_missing_compression_parent_keys(self):
1711
1691
        """Return an iterable of keys of missing compression parents.
1744
1724
        :return: An iterator over (line, key).
1745
1725
        """
1746
1726
        if pb is None:
1747
 
            pb = ui.ui_factory.nested_progress_bar()
 
1727
            pb = progress.DummyProgress()
1748
1728
        keys = set(keys)
1749
1729
        total = len(keys)
1750
1730
        done = False
1784
1764
        # vfs, and hope to find them there.  Note that if the keys are found
1785
1765
        # but had no changes or no content, the fallback may not return
1786
1766
        # anything.
1787
 
        if keys and not self._immediate_fallback_vfs:
 
1767
        if keys and not self._fallback_vfs:
1788
1768
            # XXX: strictly the second parameter is meant to be the file id
1789
1769
            # but it's not easily accessible here.
1790
1770
            raise RevisionNotPresent(keys, repr(self))
1791
 
        for source in self._immediate_fallback_vfs:
 
1771
        for source in self._fallback_vfs:
1792
1772
            if not keys:
1793
1773
                break
1794
1774
            source_keys = set()
1867
1847
        :return: the header and the decompressor stream.
1868
1848
                 as (stream, header_record)
1869
1849
        """
1870
 
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
1850
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
1871
1851
        try:
1872
1852
            # Current serialise
1873
1853
            rec = self._check_header(key, df.readline())
1882
1862
        # 4168 calls in 2880 217 internal
1883
1863
        # 4168 calls to _parse_record_header in 2121
1884
1864
        # 4168 calls to readlines in 330
1885
 
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(data))
 
1865
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(data))
1886
1866
        try:
1887
1867
            record_contents = df.readlines()
1888
1868
        except Exception, e:
1910
1890
        The result will be returned in whatever is the fastest to read.
1911
1891
        Not by the order requested. Also, multiple requests for the same
1912
1892
        record will only yield 1 response.
1913
 
 
1914
1893
        :param records: A list of (key, access_memo) entries
1915
1894
        :return: Yields (key, contents, digest) in the order
1916
1895
                 read, not the order requested
1974
1953
        :param key: The key of the record. Currently keys are always serialised
1975
1954
            using just the trailing component.
1976
1955
        :param dense_lines: The bytes of lines but in a denser form. For
1977
 
            instance, if lines is a list of 1000 bytestrings each ending in
1978
 
            \\n, dense_lines may be a list with one line in it, containing all
1979
 
            the 1000's lines and their \\n's. Using dense_lines if it is
1980
 
            already known is a win because the string join to create bytes in
1981
 
            this function spends less time resizing the final string.
 
1956
            instance, if lines is a list of 1000 bytestrings each ending in \n,
 
1957
            dense_lines may be a list with one line in it, containing all the
 
1958
            1000's lines and their \n's. Using dense_lines if it is already
 
1959
            known is a win because the string join to create bytes in this
 
1960
            function spends less time resizing the final string.
1982
1961
        :return: (len, a StringIO instance with the raw data ready to read.)
1983
1962
        """
1984
1963
        chunks = ["version %s %d %s\n" % (key[-1], len(lines), digest)]
2004
1983
        """See VersionedFiles.keys."""
2005
1984
        if 'evil' in debug.debug_flags:
2006
1985
            trace.mutter_callsite(2, "keys scales with size of history")
2007
 
        sources = [self._index] + self._immediate_fallback_vfs
 
1986
        sources = [self._index] + self._fallback_vfs
2008
1987
        result = set()
2009
1988
        for source in sources:
2010
1989
            result.update(source.keys())
2014
1993
class _ContentMapGenerator(object):
2015
1994
    """Generate texts or expose raw deltas for a set of texts."""
2016
1995
 
2017
 
    def __init__(self, ordering='unordered'):
2018
 
        self._ordering = ordering
2019
 
 
2020
1996
    def _get_content(self, key):
2021
1997
        """Get the content object for key."""
2022
1998
        # Note that _get_content is only called when the _ContentMapGenerator
2050
2026
 
2051
2027
        missing_keys = set(nonlocal_keys)
2052
2028
        # Read from remote versioned file instances and provide to our caller.
2053
 
        for source in self.vf._immediate_fallback_vfs:
 
2029
        for source in self.vf._fallback_vfs:
2054
2030
            if not missing_keys:
2055
2031
                break
2056
2032
            # Loop over fallback repositories asking them for texts - ignore
2057
2033
            # any missing from a particular fallback.
2058
2034
            for record in source.get_record_stream(missing_keys,
2059
 
                self._ordering, True):
 
2035
                'unordered', True):
2060
2036
                if record.storage_kind == 'absent':
2061
2037
                    # Not in thie particular stream, may be in one of the
2062
2038
                    # other fallback vfs objects.
2194
2170
    """Content map generator reading from a VersionedFiles object."""
2195
2171
 
2196
2172
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2197
 
        global_map=None, raw_record_map=None, ordering='unordered'):
 
2173
        global_map=None, raw_record_map=None):
2198
2174
        """Create a _ContentMapGenerator.
2199
2175
 
2200
2176
        :param versioned_files: The versioned files that the texts are being
2208
2184
        :param raw_record_map: A unparsed raw record map to use for answering
2209
2185
            contents.
2210
2186
        """
2211
 
        _ContentMapGenerator.__init__(self, ordering=ordering)
2212
2187
        # The vf to source data from
2213
2188
        self.vf = versioned_files
2214
2189
        # The keys desired
2358
2333
    FLAGS is a comma separated list of flags about the record. Values include
2359
2334
        no-eol, line-delta, fulltext.
2360
2335
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2361
 
        that the compressed data starts at.
 
2336
        that the the compressed data starts at.
2362
2337
    LENGTH is the ascii representation of the length of the data file.
2363
2338
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2364
2339
        REVISION_ID.
2573
2548
        except KeyError:
2574
2549
            raise RevisionNotPresent(key, self)
2575
2550
 
2576
 
    def find_ancestry(self, keys):
2577
 
        """See CombinedGraphIndex.find_ancestry()"""
2578
 
        prefixes = set(key[:-1] for key in keys)
2579
 
        self._load_prefixes(prefixes)
2580
 
        result = {}
2581
 
        parent_map = {}
2582
 
        missing_keys = set()
2583
 
        pending_keys = list(keys)
2584
 
        # This assumes that keys will not reference parents in a different
2585
 
        # prefix, which is accurate so far.
2586
 
        while pending_keys:
2587
 
            key = pending_keys.pop()
2588
 
            if key in parent_map:
2589
 
                continue
2590
 
            prefix = key[:-1]
2591
 
            try:
2592
 
                suffix_parents = self._kndx_cache[prefix][0][key[-1]][4]
2593
 
            except KeyError:
2594
 
                missing_keys.add(key)
2595
 
            else:
2596
 
                parent_keys = tuple([prefix + (suffix,)
2597
 
                                     for suffix in suffix_parents])
2598
 
                parent_map[key] = parent_keys
2599
 
                pending_keys.extend([p for p in parent_keys
2600
 
                                        if p not in parent_map])
2601
 
        return parent_map, missing_keys
2602
 
 
2603
2551
    def get_parent_map(self, keys):
2604
2552
        """Get a map of the parents of keys.
2605
2553
 
2775
2723
        return key[:-1], key[-1]
2776
2724
 
2777
2725
 
 
2726
class _KeyRefs(object):
 
2727
 
 
2728
    def __init__(self):
 
2729
        # dict mapping 'key' to 'set of keys referring to that key'
 
2730
        self.refs = {}
 
2731
 
 
2732
    def add_references(self, key, refs):
 
2733
        # Record the new references
 
2734
        for referenced in refs:
 
2735
            try:
 
2736
                needed_by = self.refs[referenced]
 
2737
            except KeyError:
 
2738
                needed_by = self.refs[referenced] = set()
 
2739
            needed_by.add(key)
 
2740
        # Discard references satisfied by the new key
 
2741
        self.add_key(key)
 
2742
 
 
2743
    def get_unsatisfied_refs(self):
 
2744
        return self.refs.iterkeys()
 
2745
 
 
2746
    def add_key(self, key):
 
2747
        try:
 
2748
            del self.refs[key]
 
2749
        except KeyError:
 
2750
            # No keys depended on this key.  That's ok.
 
2751
            pass
 
2752
 
 
2753
    def add_keys(self, keys):
 
2754
        for key in keys:
 
2755
            self.add_key(key)
 
2756
 
 
2757
    def get_referrers(self):
 
2758
        result = set()
 
2759
        for referrers in self.refs.itervalues():
 
2760
            result.update(referrers)
 
2761
        return result
 
2762
 
 
2763
 
2778
2764
class _KnitGraphIndex(object):
2779
2765
    """A KnitVersionedFiles index layered on GraphIndex."""
2780
2766
 
2877
2863
        if not random_id:
2878
2864
            present_nodes = self._get_entries(keys)
2879
2865
            for (index, key, value, node_refs) in present_nodes:
2880
 
                parents = node_refs[:1]
2881
 
                # Sometimes these are passed as a list rather than a tuple
2882
 
                passed = static_tuple.as_tuples(keys[key])
2883
 
                passed_parents = passed[1][:1]
2884
2866
                if (value[0] != keys[key][0][0] or
2885
 
                    parents != passed_parents):
2886
 
                    node_refs = static_tuple.as_tuples(node_refs)
 
2867
                    node_refs[:1] != keys[key][1][:1]):
2887
2868
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2888
 
                        ": %s %s" % ((value, node_refs), passed))
 
2869
                        ": %s %s" % ((value, node_refs), keys[key]))
2889
2870
                del keys[key]
2890
2871
        result = []
2891
2872
        if self._parents:
2939
2920
        # If updating this, you should also update
2940
2921
        # groupcompress._GCGraphIndex.get_missing_parents
2941
2922
        # We may have false positives, so filter those out.
2942
 
        self._key_dependencies.satisfy_refs_for_keys(
 
2923
        self._key_dependencies.add_keys(
2943
2924
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2944
2925
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
2945
2926
 
3056
3037
            options.append('no-eol')
3057
3038
        return options
3058
3039
 
3059
 
    def find_ancestry(self, keys):
3060
 
        """See CombinedGraphIndex.find_ancestry()"""
3061
 
        return self._graph_index.find_ancestry(keys, 0)
3062
 
 
3063
3040
    def get_parent_map(self, keys):
3064
3041
        """Get a map of the parents of keys.
3065
3042
 
3348
3325
            raise exc_class, exc_value, exc_traceback
3349
3326
 
3350
3327
 
 
3328
# Deprecated, use PatienceSequenceMatcher instead
 
3329
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
 
3330
 
 
3331
 
3351
3332
def annotate_knit(knit, revision_id):
3352
3333
    """Annotate a knit with no cached annotations.
3353
3334
 
3451
3432
        return records, ann_keys
3452
3433
 
3453
3434
    def _get_needed_texts(self, key, pb=None):
3454
 
        # if True or len(self._vf._immediate_fallback_vfs) > 0:
3455
 
        if len(self._vf._immediate_fallback_vfs) > 0:
 
3435
        # if True or len(self._vf._fallback_vfs) > 0:
 
3436
        if len(self._vf._fallback_vfs) > 0:
3456
3437
            # If we have fallbacks, go to the generic path
3457
3438
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
3458
3439
                yield v
3635
3616
                    to_process.extend(self._process_pending(key))
3636
3617
 
3637
3618
try:
3638
 
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
3639
 
except ImportError, e:
3640
 
    osutils.failed_to_load_extension(e)
 
3619
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
 
3620
except ImportError:
3641
3621
    from bzrlib._knit_load_data_py import _load_data_py as _load_data