← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Neil Martinsen-Burrell
  • Date: 2009-12-07 21:51:01 UTC
  • mto: This revision was merged to the branch mainline in revision 4910.
  • Revision ID: nmb@wartburg.edu-20091207215101-lv1fyi2blzer4h5j
tweaks based on JAMs review

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