← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: INADA Naoki
  • Date: 2011-05-18 06:27:34 UTC
  • mfrom: (5887 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5894.
  • Revision ID: songofacandy@gmail.com-20110518062734-1ilhll0rrqyyp8um
merge from lp:bzr and resolve conflicts.

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-2011 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
60
59
 
61
60
from bzrlib.lazy_import import lazy_import
62
61
lazy_import(globals(), """
 
62
import gzip
 
63
 
63
64
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,
70
69
    pack,
71
 
    progress,
 
70
    patiencediff,
 
71
    static_tuple,
72
72
    trace,
73
73
    tsort,
74
74
    tuned_gzip,
 
75
    ui,
75
76
    )
 
77
 
 
78
from bzrlib.repofmt import pack_repo
76
79
""")
77
80
from bzrlib import (
 
81
    annotate,
78
82
    errors,
79
83
    osutils,
80
 
    patiencediff,
81
84
    )
82
85
from bzrlib.errors import (
83
 
    FileExists,
84
86
    NoSuchFile,
85
 
    KnitError,
86
87
    InvalidRevisionId,
87
88
    KnitCorrupt,
88
89
    KnitHeaderError,
89
90
    RevisionNotPresent,
90
 
    RevisionAlreadyPresent,
91
91
    SHA1KnitCorrupt,
92
92
    )
93
93
from bzrlib.osutils import (
94
94
    contains_whitespace,
95
 
    contains_linebreaks,
96
95
    sha_string,
97
96
    sha_strings,
98
97
    split_lines,
99
98
    )
100
99
from bzrlib.versionedfile import (
 
100
    _KeyRefs,
101
101
    AbsentContentFactory,
102
102
    adapter_registry,
103
103
    ConstantMapper,
104
104
    ContentFactory,
105
 
    ChunkedContentFactory,
106
105
    sort_groupcompress,
107
 
    VersionedFile,
108
 
    VersionedFiles,
 
106
    VersionedFilesWithFallbacks,
109
107
    )
110
108
 
111
109
 
803
801
        writer.begin()
804
802
        index = _KnitGraphIndex(graph_index, lambda:True, parents=parents,
805
803
            deltas=delta, add_callback=graph_index.add_nodes)
806
 
        access = _DirectPackAccess({})
 
804
        access = pack_repo._DirectPackAccess({})
807
805
        access.set_writer(writer, graph_index, (transport, 'newpack'))
808
806
        result = KnitVersionedFiles(index, access,
809
807
            max_delta_chain=max_delta_chain)
847
845
                in all_build_index_memos.itervalues()])
848
846
 
849
847
 
850
 
class KnitVersionedFiles(VersionedFiles):
 
848
class KnitVersionedFiles(VersionedFilesWithFallbacks):
851
849
    """Storage for many versioned files using knit compression.
852
850
 
853
851
    Backend storage is managed by indices and data objects.
880
878
            self._factory = KnitAnnotateFactory()
881
879
        else:
882
880
            self._factory = KnitPlainFactory()
883
 
        self._fallback_vfs = []
 
881
        self._immediate_fallback_vfs = []
884
882
        self._reload_func = reload_func
885
883
 
886
884
    def __repr__(self):
889
887
            self._index,
890
888
            self._access)
891
889
 
 
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
 
892
896
    def add_fallback_versioned_files(self, a_versioned_files):
893
897
        """Add a source of texts for texts not present in this knit.
894
898
 
895
899
        :param a_versioned_files: A VersionedFiles object.
896
900
        """
897
 
        self._fallback_vfs.append(a_versioned_files)
 
901
        self._immediate_fallback_vfs.append(a_versioned_files)
898
902
 
899
903
    def add_lines(self, key, parents, lines, parent_texts=None,
900
904
        left_matching_blocks=None, nostore_sha=None, random_id=False,
1067
1071
                    raise errors.KnitCorrupt(self,
1068
1072
                        "Missing basis parent %s for %s" % (
1069
1073
                        compression_parent, key))
1070
 
        for fallback_vfs in self._fallback_vfs:
 
1074
        for fallback_vfs in self._immediate_fallback_vfs:
1071
1075
            fallback_vfs.check()
1072
1076
 
1073
1077
    def _check_add(self, key, lines, random_id, check_content):
1190
1194
        generator = _VFContentMapGenerator(self, [key])
1191
1195
        return generator._get_content(key)
1192
1196
 
1193
 
    def get_known_graph_ancestry(self, keys):
1194
 
        """Get a KnownGraph instance with the ancestry of keys."""
1195
 
        parent_map, missing_keys = self._index.find_ancestry(keys)
1196
 
        kg = _mod_graph.KnownGraph(parent_map)
1197
 
        return kg
1198
 
 
1199
1197
    def get_parent_map(self, keys):
1200
1198
        """Get a map of the graph parents of keys.
1201
1199
 
1216
1214
            and so on.
1217
1215
        """
1218
1216
        result = {}
1219
 
        sources = [self._index] + self._fallback_vfs
 
1217
        sources = [self._index] + self._immediate_fallback_vfs
1220
1218
        source_results = []
1221
1219
        missing = set(keys)
1222
1220
        for source in sources:
1511
1509
                if source is parent_maps[0]:
1512
1510
                    # this KnitVersionedFiles
1513
1511
                    records = [(key, positions[key][1]) for key in keys]
1514
 
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
 
1512
                    for key, raw_data in self._read_records_iter_unchecked(records):
1515
1513
                        (record_details, index_memo, _) = positions[key]
1516
1514
                        yield KnitContentFactory(key, global_map[key],
1517
 
                            record_details, sha1, raw_data, self._factory.annotated, None)
 
1515
                            record_details, None, raw_data, self._factory.annotated, None)
1518
1516
                else:
1519
 
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
 
1517
                    vf = self._immediate_fallback_vfs[parent_maps.index(source) - 1]
1520
1518
                    for record in vf.get_record_stream(keys, ordering,
1521
1519
                        include_delta_closure):
1522
1520
                        yield record
1532
1530
            # record entry 2 is the 'digest'.
1533
1531
            result[key] = details[2]
1534
1532
        missing.difference_update(set(result))
1535
 
        for source in self._fallback_vfs:
 
1533
        for source in self._immediate_fallback_vfs:
1536
1534
            if not missing:
1537
1535
                break
1538
1536
            new_result = source.get_sha1s(missing)
1589
1587
        # key = basis_parent, value = index entry to add
1590
1588
        buffered_index_entries = {}
1591
1589
        for record in stream:
 
1590
            kind = record.storage_kind
 
1591
            if kind.startswith('knit-') and kind.endswith('-gz'):
 
1592
                # Check that the ID in the header of the raw knit bytes matches
 
1593
                # the record metadata.
 
1594
                raw_data = record._raw_record
 
1595
                df, rec = self._parse_record_header(record.key, raw_data)
 
1596
                df.close()
1592
1597
            buffered = False
1593
1598
            parents = record.parents
1594
1599
            if record.storage_kind in delta_types:
1602
1607
                raise RevisionNotPresent([record.key], self)
1603
1608
            elif ((record.storage_kind in knit_types)
1604
1609
                  and (compression_parent is None
1605
 
                       or not self._fallback_vfs
 
1610
                       or not self._immediate_fallback_vfs
1606
1611
                       or self._index.has_key(compression_parent)
1607
1612
                       or not self.has_key(compression_parent))):
1608
1613
                # we can insert the knit record literally if either it has no
1696
1701
            # There were index entries buffered at the end of the stream,
1697
1702
            # So these need to be added (if the index supports holding such
1698
1703
            # entries for later insertion)
 
1704
            all_entries = []
1699
1705
            for key in buffered_index_entries:
1700
1706
                index_entries = buffered_index_entries[key]
1701
 
                self._index.add_records(index_entries,
1702
 
                    missing_compression_parents=True)
 
1707
                all_entries.extend(index_entries)
 
1708
            self._index.add_records(
 
1709
                all_entries, missing_compression_parents=True)
1703
1710
 
1704
1711
    def get_missing_compression_parent_keys(self):
1705
1712
        """Return an iterable of keys of missing compression parents.
1738
1745
        :return: An iterator over (line, key).
1739
1746
        """
1740
1747
        if pb is None:
1741
 
            pb = progress.DummyProgress()
 
1748
            pb = ui.ui_factory.nested_progress_bar()
1742
1749
        keys = set(keys)
1743
1750
        total = len(keys)
1744
1751
        done = False
1778
1785
        # vfs, and hope to find them there.  Note that if the keys are found
1779
1786
        # but had no changes or no content, the fallback may not return
1780
1787
        # anything.
1781
 
        if keys and not self._fallback_vfs:
 
1788
        if keys and not self._immediate_fallback_vfs:
1782
1789
            # XXX: strictly the second parameter is meant to be the file id
1783
1790
            # but it's not easily accessible here.
1784
1791
            raise RevisionNotPresent(keys, repr(self))
1785
 
        for source in self._fallback_vfs:
 
1792
        for source in self._immediate_fallback_vfs:
1786
1793
            if not keys:
1787
1794
                break
1788
1795
            source_keys = set()
1861
1868
        :return: the header and the decompressor stream.
1862
1869
                 as (stream, header_record)
1863
1870
        """
1864
 
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
1871
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
1865
1872
        try:
1866
1873
            # Current serialise
1867
1874
            rec = self._check_header(key, df.readline())
1876
1883
        # 4168 calls in 2880 217 internal
1877
1884
        # 4168 calls to _parse_record_header in 2121
1878
1885
        # 4168 calls to readlines in 330
1879
 
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(data))
 
1886
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(data))
1880
1887
        try:
1881
1888
            record_contents = df.readlines()
1882
1889
        except Exception, e:
1997
2004
        """See VersionedFiles.keys."""
1998
2005
        if 'evil' in debug.debug_flags:
1999
2006
            trace.mutter_callsite(2, "keys scales with size of history")
2000
 
        sources = [self._index] + self._fallback_vfs
 
2007
        sources = [self._index] + self._immediate_fallback_vfs
2001
2008
        result = set()
2002
2009
        for source in sources:
2003
2010
            result.update(source.keys())
2043
2050
 
2044
2051
        missing_keys = set(nonlocal_keys)
2045
2052
        # Read from remote versioned file instances and provide to our caller.
2046
 
        for source in self.vf._fallback_vfs:
 
2053
        for source in self.vf._immediate_fallback_vfs:
2047
2054
            if not missing_keys:
2048
2055
                break
2049
2056
            # Loop over fallback repositories asking them for texts - ignore
2351
2358
    FLAGS is a comma separated list of flags about the record. Values include
2352
2359
        no-eol, line-delta, fulltext.
2353
2360
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2354
 
        that the the compressed data starts at.
 
2361
        that the compressed data starts at.
2355
2362
    LENGTH is the ascii representation of the length of the data file.
2356
2363
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2357
2364
        REVISION_ID.
2768
2775
        return key[:-1], key[-1]
2769
2776
 
2770
2777
 
2771
 
class _KeyRefs(object):
2772
 
 
2773
 
    def __init__(self):
2774
 
        # dict mapping 'key' to 'set of keys referring to that key'
2775
 
        self.refs = {}
2776
 
 
2777
 
    def add_references(self, key, refs):
2778
 
        # Record the new references
2779
 
        for referenced in refs:
2780
 
            try:
2781
 
                needed_by = self.refs[referenced]
2782
 
            except KeyError:
2783
 
                needed_by = self.refs[referenced] = set()
2784
 
            needed_by.add(key)
2785
 
        # Discard references satisfied by the new key
2786
 
        self.add_key(key)
2787
 
 
2788
 
    def get_unsatisfied_refs(self):
2789
 
        return self.refs.iterkeys()
2790
 
 
2791
 
    def add_key(self, key):
2792
 
        try:
2793
 
            del self.refs[key]
2794
 
        except KeyError:
2795
 
            # No keys depended on this key.  That's ok.
2796
 
            pass
2797
 
 
2798
 
    def add_keys(self, keys):
2799
 
        for key in keys:
2800
 
            self.add_key(key)
2801
 
 
2802
 
    def get_referrers(self):
2803
 
        result = set()
2804
 
        for referrers in self.refs.itervalues():
2805
 
            result.update(referrers)
2806
 
        return result
2807
 
 
2808
 
 
2809
2778
class _KnitGraphIndex(object):
2810
2779
    """A KnitVersionedFiles index layered on GraphIndex."""
2811
2780
 
2908
2877
        if not random_id:
2909
2878
            present_nodes = self._get_entries(keys)
2910
2879
            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]
2911
2884
                if (value[0] != keys[key][0][0] or
2912
 
                    node_refs[:1] != keys[key][1][:1]):
 
2885
                    parents != passed_parents):
 
2886
                    node_refs = static_tuple.as_tuples(node_refs)
2913
2887
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2914
 
                        ": %s %s" % ((value, node_refs), keys[key]))
 
2888
                        ": %s %s" % ((value, node_refs), passed))
2915
2889
                del keys[key]
2916
2890
        result = []
2917
2891
        if self._parents:
2965
2939
        # If updating this, you should also update
2966
2940
        # groupcompress._GCGraphIndex.get_missing_parents
2967
2941
        # We may have false positives, so filter those out.
2968
 
        self._key_dependencies.add_keys(
 
2942
        self._key_dependencies.satisfy_refs_for_keys(
2969
2943
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2970
2944
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
2971
2945
 
3374
3348
            raise exc_class, exc_value, exc_traceback
3375
3349
 
3376
3350
 
3377
 
# Deprecated, use PatienceSequenceMatcher instead
3378
 
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
3379
 
 
3380
 
 
3381
3351
def annotate_knit(knit, revision_id):
3382
3352
    """Annotate a knit with no cached annotations.
3383
3353
 
3481
3451
        return records, ann_keys
3482
3452
 
3483
3453
    def _get_needed_texts(self, key, pb=None):
3484
 
        # if True or len(self._vf._fallback_vfs) > 0:
3485
 
        if len(self._vf._fallback_vfs) > 0:
 
3454
        # if True or len(self._vf._immediate_fallback_vfs) > 0:
 
3455
        if len(self._vf._immediate_fallback_vfs) > 0:
3486
3456
            # If we have fallbacks, go to the generic path
3487
3457
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
3488
3458
                yield v
3666
3636
 
3667
3637
try:
3668
3638
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
3669
 
except ImportError:
 
3639
except ImportError, e:
 
3640
    osutils.failed_to_load_extension(e)
3670
3641
    from bzrlib._knit_load_data_py import _load_data_py as _load_data