← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Andrew Bennetts
  • Date: 2010-10-13 00:26:41 UTC
  • mto: This revision was merged to the branch mainline in revision 5498.
  • Revision ID: andrew.bennetts@canonical.com-20101013002641-9tlh9k89mlj1666m
Keep docs-plain working.

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) 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
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
71
    patiencediff,
 
72
    progress,
71
73
    static_tuple,
72
74
    trace,
73
75
    tsort,
74
76
    tuned_gzip,
75
77
    ui,
76
78
    )
77
 
 
78
 
from bzrlib.repofmt import pack_repo
79
79
""")
80
80
from bzrlib import (
81
 
    annotate,
82
81
    errors,
83
82
    osutils,
84
83
    )
85
84
from bzrlib.errors import (
 
85
    FileExists,
86
86
    NoSuchFile,
 
87
    KnitError,
87
88
    InvalidRevisionId,
88
89
    KnitCorrupt,
89
90
    KnitHeaderError,
90
91
    RevisionNotPresent,
 
92
    RevisionAlreadyPresent,
91
93
    SHA1KnitCorrupt,
92
94
    )
93
95
from bzrlib.osutils import (
94
96
    contains_whitespace,
 
97
    contains_linebreaks,
95
98
    sha_string,
96
99
    sha_strings,
97
100
    split_lines,
98
101
    )
99
102
from bzrlib.versionedfile import (
100
 
    _KeyRefs,
101
103
    AbsentContentFactory,
102
104
    adapter_registry,
103
105
    ConstantMapper,
104
106
    ContentFactory,
 
107
    ChunkedContentFactory,
105
108
    sort_groupcompress,
106
 
    VersionedFilesWithFallbacks,
 
109
    VersionedFile,
 
110
    VersionedFiles,
107
111
    )
108
112
 
109
113
 
408
412
class KnitContent(object):
409
413
    """Content of a knit version to which deltas can be applied.
410
414
 
411
 
    This is always stored in memory as a list of lines with \\n at the end,
 
415
    This is always stored in memory as a list of lines with \n at the end,
412
416
    plus a flag saying if the final ending is really there or not, because that
413
417
    corresponds to the on-disk knit representation.
414
418
    """
801
805
        writer.begin()
802
806
        index = _KnitGraphIndex(graph_index, lambda:True, parents=parents,
803
807
            deltas=delta, add_callback=graph_index.add_nodes)
804
 
        access = pack_repo._DirectPackAccess({})
 
808
        access = _DirectPackAccess({})
805
809
        access.set_writer(writer, graph_index, (transport, 'newpack'))
806
810
        result = KnitVersionedFiles(index, access,
807
811
            max_delta_chain=max_delta_chain)
845
849
                in all_build_index_memos.itervalues()])
846
850
 
847
851
 
848
 
class KnitVersionedFiles(VersionedFilesWithFallbacks):
 
852
class KnitVersionedFiles(VersionedFiles):
849
853
    """Storage for many versioned files using knit compression.
850
854
 
851
855
    Backend storage is managed by indices and data objects.
878
882
            self._factory = KnitAnnotateFactory()
879
883
        else:
880
884
            self._factory = KnitPlainFactory()
881
 
        self._immediate_fallback_vfs = []
 
885
        self._fallback_vfs = []
882
886
        self._reload_func = reload_func
883
887
 
884
888
    def __repr__(self):
887
891
            self._index,
888
892
            self._access)
889
893
 
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
894
    def add_fallback_versioned_files(self, a_versioned_files):
897
895
        """Add a source of texts for texts not present in this knit.
898
896
 
899
897
        :param a_versioned_files: A VersionedFiles object.
900
898
        """
901
 
        self._immediate_fallback_vfs.append(a_versioned_files)
 
899
        self._fallback_vfs.append(a_versioned_files)
902
900
 
903
901
    def add_lines(self, key, parents, lines, parent_texts=None,
904
902
        left_matching_blocks=None, nostore_sha=None, random_id=False,
1071
1069
                    raise errors.KnitCorrupt(self,
1072
1070
                        "Missing basis parent %s for %s" % (
1073
1071
                        compression_parent, key))
1074
 
        for fallback_vfs in self._immediate_fallback_vfs:
 
1072
        for fallback_vfs in self._fallback_vfs:
1075
1073
            fallback_vfs.check()
1076
1074
 
1077
1075
    def _check_add(self, key, lines, random_id, check_content):
1155
1153
 
1156
1154
        A dict of key to (record_details, index_memo, next, parents) is
1157
1155
        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.
 
1156
        method is the way referenced data should be applied.
 
1157
        index_memo is the handle to pass to the data access to actually get the
 
1158
            data
 
1159
        next is the build-parent of the version, or None for fulltexts.
 
1160
        parents is the version_ids of the parents of this version
 
1161
 
 
1162
        :param allow_missing: If True do not raise an error on a missing component,
 
1163
            just ignore it.
1167
1164
        """
1168
1165
        component_data = {}
1169
1166
        pending_components = keys
1195
1192
        generator = _VFContentMapGenerator(self, [key])
1196
1193
        return generator._get_content(key)
1197
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
 
1198
1208
    def get_parent_map(self, keys):
1199
1209
        """Get a map of the graph parents of keys.
1200
1210
 
1215
1225
            and so on.
1216
1226
        """
1217
1227
        result = {}
1218
 
        sources = [self._index] + self._immediate_fallback_vfs
 
1228
        sources = [self._index] + self._fallback_vfs
1219
1229
        source_results = []
1220
1230
        missing = set(keys)
1221
1231
        for source in sources:
1231
1241
        """Produce a dictionary of knit records.
1232
1242
 
1233
1243
        :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.
 
1244
            record
 
1245
                data returned from read_records (a KnitContentobject)
 
1246
            record_details
 
1247
                opaque information to pass to parse_record
 
1248
            digest
 
1249
                SHA1 digest of the full text after all steps are done
 
1250
            next
 
1251
                build-parent of the version, i.e. the leftmost ancestor.
1239
1252
                Will be None if the record is not a delta.
1240
 
 
1241
1253
        :param keys: The keys to build a map for
1242
1254
        :param allow_missing: If some records are missing, rather than
1243
1255
            error, just return the data that could be generated.
1513
1525
                        yield KnitContentFactory(key, global_map[key],
1514
1526
                            record_details, None, raw_data, self._factory.annotated, None)
1515
1527
                else:
1516
 
                    vf = self._immediate_fallback_vfs[parent_maps.index(source) - 1]
 
1528
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1517
1529
                    for record in vf.get_record_stream(keys, ordering,
1518
1530
                        include_delta_closure):
1519
1531
                        yield record
1529
1541
            # record entry 2 is the 'digest'.
1530
1542
            result[key] = details[2]
1531
1543
        missing.difference_update(set(result))
1532
 
        for source in self._immediate_fallback_vfs:
 
1544
        for source in self._fallback_vfs:
1533
1545
            if not missing:
1534
1546
                break
1535
1547
            new_result = source.get_sha1s(missing)
1606
1618
                raise RevisionNotPresent([record.key], self)
1607
1619
            elif ((record.storage_kind in knit_types)
1608
1620
                  and (compression_parent is None
1609
 
                       or not self._immediate_fallback_vfs
 
1621
                       or not self._fallback_vfs
1610
1622
                       or self._index.has_key(compression_parent)
1611
1623
                       or not self.has_key(compression_parent))):
1612
1624
                # we can insert the knit record literally if either it has no
1784
1796
        # vfs, and hope to find them there.  Note that if the keys are found
1785
1797
        # but had no changes or no content, the fallback may not return
1786
1798
        # anything.
1787
 
        if keys and not self._immediate_fallback_vfs:
 
1799
        if keys and not self._fallback_vfs:
1788
1800
            # XXX: strictly the second parameter is meant to be the file id
1789
1801
            # but it's not easily accessible here.
1790
1802
            raise RevisionNotPresent(keys, repr(self))
1791
 
        for source in self._immediate_fallback_vfs:
 
1803
        for source in self._fallback_vfs:
1792
1804
            if not keys:
1793
1805
                break
1794
1806
            source_keys = set()
1867
1879
        :return: the header and the decompressor stream.
1868
1880
                 as (stream, header_record)
1869
1881
        """
1870
 
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
1882
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
1871
1883
        try:
1872
1884
            # Current serialise
1873
1885
            rec = self._check_header(key, df.readline())
1882
1894
        # 4168 calls in 2880 217 internal
1883
1895
        # 4168 calls to _parse_record_header in 2121
1884
1896
        # 4168 calls to readlines in 330
1885
 
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(data))
 
1897
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(data))
1886
1898
        try:
1887
1899
            record_contents = df.readlines()
1888
1900
        except Exception, e:
1910
1922
        The result will be returned in whatever is the fastest to read.
1911
1923
        Not by the order requested. Also, multiple requests for the same
1912
1924
        record will only yield 1 response.
1913
 
 
1914
1925
        :param records: A list of (key, access_memo) entries
1915
1926
        :return: Yields (key, contents, digest) in the order
1916
1927
                 read, not the order requested
1974
1985
        :param key: The key of the record. Currently keys are always serialised
1975
1986
            using just the trailing component.
1976
1987
        :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.
 
1988
            instance, if lines is a list of 1000 bytestrings each ending in \n,
 
1989
            dense_lines may be a list with one line in it, containing all the
 
1990
            1000's lines and their \n's. Using dense_lines if it is already
 
1991
            known is a win because the string join to create bytes in this
 
1992
            function spends less time resizing the final string.
1982
1993
        :return: (len, a StringIO instance with the raw data ready to read.)
1983
1994
        """
1984
1995
        chunks = ["version %s %d %s\n" % (key[-1], len(lines), digest)]
2004
2015
        """See VersionedFiles.keys."""
2005
2016
        if 'evil' in debug.debug_flags:
2006
2017
            trace.mutter_callsite(2, "keys scales with size of history")
2007
 
        sources = [self._index] + self._immediate_fallback_vfs
 
2018
        sources = [self._index] + self._fallback_vfs
2008
2019
        result = set()
2009
2020
        for source in sources:
2010
2021
            result.update(source.keys())
2050
2061
 
2051
2062
        missing_keys = set(nonlocal_keys)
2052
2063
        # Read from remote versioned file instances and provide to our caller.
2053
 
        for source in self.vf._immediate_fallback_vfs:
 
2064
        for source in self.vf._fallback_vfs:
2054
2065
            if not missing_keys:
2055
2066
                break
2056
2067
            # Loop over fallback repositories asking them for texts - ignore
2775
2786
        return key[:-1], key[-1]
2776
2787
 
2777
2788
 
 
2789
class _KeyRefs(object):
 
2790
 
 
2791
    def __init__(self, track_new_keys=False):
 
2792
        # dict mapping 'key' to 'set of keys referring to that key'
 
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()
 
2805
 
 
2806
    def add_references(self, key, refs):
 
2807
        # Record the new references
 
2808
        for referenced in refs:
 
2809
            try:
 
2810
                needed_by = self.refs[referenced]
 
2811
            except KeyError:
 
2812
                needed_by = self.refs[referenced] = set()
 
2813
            needed_by.add(key)
 
2814
        # Discard references satisfied by the new key
 
2815
        self.add_key(key)
 
2816
 
 
2817
    def get_new_keys(self):
 
2818
        return self.new_keys
 
2819
    
 
2820
    def get_unsatisfied_refs(self):
 
2821
        return self.refs.iterkeys()
 
2822
 
 
2823
    def _satisfy_refs_for_key(self, key):
 
2824
        try:
 
2825
            del self.refs[key]
 
2826
        except KeyError:
 
2827
            # No keys depended on this key.  That's ok.
 
2828
            pass
 
2829
 
 
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):
 
2837
        for key in keys:
 
2838
            self._satisfy_refs_for_key(key)
 
2839
 
 
2840
    def get_referrers(self):
 
2841
        result = set()
 
2842
        for referrers in self.refs.itervalues():
 
2843
            result.update(referrers)
 
2844
        return result
 
2845
 
 
2846
 
2778
2847
class _KnitGraphIndex(object):
2779
2848
    """A KnitVersionedFiles index layered on GraphIndex."""
2780
2849
 
3451
3520
        return records, ann_keys
3452
3521
 
3453
3522
    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:
 
3523
        # if True or len(self._vf._fallback_vfs) > 0:
 
3524
        if len(self._vf._fallback_vfs) > 0:
3456
3525
            # If we have fallbacks, go to the generic path
3457
3526
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
3458
3527
                yield v