← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Robert Collins
  • Date: 2009-03-26 23:16:06 UTC
  • mto: This revision was merged to the branch mainline in revision 4216.
  • Revision ID: robertc@robertcollins.net-20090326231606-rh98suac20x246pk
Review caught a bogus change to test_last_modified_revision_after_commit_link_unchanged_ric.

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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
"""Knit versionedfile implementation.
18
18
 
53
53
 
54
54
 
55
55
from cStringIO import StringIO
56
 
from itertools import izip
 
56
from itertools import izip, chain
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
    """
662
664
 
663
665
        see parse_fulltext which this inverts.
664
666
        """
 
667
        # TODO: jam 20070209 We only do the caching thing to make sure that
 
668
        #       the origin is a valid utf-8 line, eventually we could remove it
665
669
        return ['%s %s' % (o, t) for o, t in content._lines]
666
670
 
667
671
    def lower_line_delta(self, delta):
682
686
        content = knit._get_content(key)
683
687
        # adjust for the fact that serialised annotations are only key suffixes
684
688
        # for this factory.
685
 
        if type(key) is tuple:
 
689
        if type(key) == tuple:
686
690
            prefix = key[:-1]
687
691
            origins = content.annotate()
688
692
            result = []
754
758
 
755
759
    def annotate(self, knit, key):
756
760
        annotator = _KnitAnnotator(knit)
757
 
        return annotator.annotate_flat(key)
 
761
        return annotator.annotate(key)
758
762
 
759
763
 
760
764
 
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,
911
909
            # indexes can't directly store that, so we give them
912
910
            # an empty tuple instead.
913
911
            parents = ()
914
 
        line_bytes = ''.join(lines)
915
912
        return self._add(key, lines, parents,
916
 
            parent_texts, left_matching_blocks, nostore_sha, random_id,
917
 
            line_bytes=line_bytes)
918
 
 
919
 
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
920
 
        """See VersionedFiles._add_text()."""
921
 
        self._index._check_write_ok()
922
 
        self._check_add(key, None, random_id, check_content=False)
923
 
        if text.__class__ is not str:
924
 
            raise errors.BzrBadParameterUnicode("text")
925
 
        if parents is None:
926
 
            # The caller might pass None if there is no graph data, but kndx
927
 
            # indexes can't directly store that, so we give them
928
 
            # an empty tuple instead.
929
 
            parents = ()
930
 
        return self._add(key, None, parents,
931
 
            None, None, nostore_sha, random_id,
932
 
            line_bytes=text)
 
913
            parent_texts, left_matching_blocks, nostore_sha, random_id)
933
914
 
934
915
    def _add(self, key, lines, parents, parent_texts,
935
 
        left_matching_blocks, nostore_sha, random_id,
936
 
        line_bytes):
 
916
        left_matching_blocks, nostore_sha, random_id):
937
917
        """Add a set of lines on top of version specified by parents.
938
918
 
939
919
        Any versions not present will be converted into ghosts.
940
 
 
941
 
        :param lines: A list of strings where each one is a single line (has a
942
 
            single newline at the end of the string) This is now optional
943
 
            (callers can pass None). It is left in its location for backwards
944
 
            compatibility. It should ''.join(lines) must == line_bytes
945
 
        :param line_bytes: A single string containing the content
946
 
 
947
 
        We pass both lines and line_bytes because different routes bring the
948
 
        values to this function. And for memory efficiency, we don't want to
949
 
        have to split/join on-demand.
950
920
        """
951
921
        # first thing, if the content is something we don't need to store, find
952
922
        # that out.
 
923
        line_bytes = ''.join(lines)
953
924
        digest = sha_string(line_bytes)
954
925
        if nostore_sha == digest:
955
926
            raise errors.ExistingContent
976
947
 
977
948
        text_length = len(line_bytes)
978
949
        options = []
979
 
        no_eol = False
980
 
        # Note: line_bytes is not modified to add a newline, that is tracked
981
 
        #       via the no_eol flag. 'lines' *is* modified, because that is the
982
 
        #       general values needed by the Content code.
983
 
        if line_bytes and line_bytes[-1] != '\n':
984
 
            options.append('no-eol')
985
 
            no_eol = True
986
 
            # Copy the existing list, or create a new one
987
 
            if lines is None:
988
 
                lines = osutils.split_lines(line_bytes)
989
 
            else:
 
950
        if lines:
 
951
            if lines[-1][-1] != '\n':
 
952
                # copy the contents of lines.
990
953
                lines = lines[:]
991
 
            # Replace the last line with one that ends in a final newline
992
 
            lines[-1] = lines[-1] + '\n'
993
 
        if lines is None:
994
 
            lines = osutils.split_lines(line_bytes)
 
954
                options.append('no-eol')
 
955
                lines[-1] = lines[-1] + '\n'
 
956
                line_bytes += '\n'
995
957
 
996
 
        for element in key[:-1]:
997
 
            if type(element) is not str:
998
 
                raise TypeError("key contains non-strings: %r" % (key,))
999
 
        if key[-1] is None:
1000
 
            key = key[:-1] + ('sha1:' + digest,)
1001
 
        elif type(key[-1]) is not str:
 
958
        for element in key:
 
959
            if type(element) != str:
1002
960
                raise TypeError("key contains non-strings: %r" % (key,))
1003
961
        # Knit hunks are still last-element only
1004
962
        version_id = key[-1]
1005
963
        content = self._factory.make(lines, version_id)
1006
 
        if no_eol:
 
964
        if 'no-eol' in options:
1007
965
            # Hint to the content object that its text() call should strip the
1008
966
            # EOL.
1009
967
            content._should_strip_eol = True
1024
982
            if self._factory.__class__ is KnitPlainFactory:
1025
983
                # Use the already joined bytes saving iteration time in
1026
984
                # _record_to_data.
1027
 
                dense_lines = [line_bytes]
1028
 
                if no_eol:
1029
 
                    dense_lines.append('\n')
1030
985
                size, bytes = self._record_to_data(key, digest,
1031
 
                    lines, dense_lines)
 
986
                    lines, [line_bytes])
1032
987
            else:
1033
988
                # get mixed annotation + content and feed it into the
1034
989
                # serialiser.
1046
1001
        """See VersionedFiles.annotate."""
1047
1002
        return self._factory.annotate(self, key)
1048
1003
 
1049
 
    def get_annotator(self):
1050
 
        return _KnitAnnotator(self)
1051
 
 
1052
 
    def check(self, progress_bar=None, keys=None):
 
1004
    def check(self, progress_bar=None):
1053
1005
        """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
1006
        # This doesn't actually test extraction of everything, but that will
1062
1007
        # impact 'bzr check' substantially, and needs to be integrated with
1063
1008
        # care. However, it does check for the obvious problem of a delta with
1071
1016
                    raise errors.KnitCorrupt(self,
1072
1017
                        "Missing basis parent %s for %s" % (
1073
1018
                        compression_parent, key))
1074
 
        for fallback_vfs in self._immediate_fallback_vfs:
 
1019
        for fallback_vfs in self._fallback_vfs:
1075
1020
            fallback_vfs.check()
1076
1021
 
1077
1022
    def _check_add(self, key, lines, random_id, check_content):
1078
1023
        """check that version_id and lines are safe to add."""
1079
1024
        version_id = key[-1]
1080
 
        if version_id is not None:
1081
 
            if contains_whitespace(version_id):
1082
 
                raise InvalidRevisionId(version_id, self)
1083
 
            self.check_not_reserved_id(version_id)
 
1025
        if contains_whitespace(version_id):
 
1026
            raise InvalidRevisionId(version_id, self)
 
1027
        self.check_not_reserved_id(version_id)
1084
1028
        # TODO: If random_id==False and the key is already present, we should
1085
1029
        # probably check that the existing content is identical to what is
1086
1030
        # being inserted, and otherwise raise an exception.  This would make
1155
1099
 
1156
1100
        A dict of key to (record_details, index_memo, next, parents) is
1157
1101
        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.
 
1102
        method is the way referenced data should be applied.
 
1103
        index_memo is the handle to pass to the data access to actually get the
 
1104
            data
 
1105
        next is the build-parent of the version, or None for fulltexts.
 
1106
        parents is the version_ids of the parents of this version
 
1107
 
 
1108
        :param allow_missing: If True do not raise an error on a missing component,
 
1109
            just ignore it.
1167
1110
        """
1168
1111
        component_data = {}
1169
1112
        pending_components = keys
1215
1158
            and so on.
1216
1159
        """
1217
1160
        result = {}
1218
 
        sources = [self._index] + self._immediate_fallback_vfs
 
1161
        sources = [self._index] + self._fallback_vfs
1219
1162
        source_results = []
1220
1163
        missing = set(keys)
1221
1164
        for source in sources:
1231
1174
        """Produce a dictionary of knit records.
1232
1175
 
1233
1176
        :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.
 
1177
            record
 
1178
                data returned from read_records (a KnitContentobject)
 
1179
            record_details
 
1180
                opaque information to pass to parse_record
 
1181
            digest
 
1182
                SHA1 digest of the full text after all steps are done
 
1183
            next
 
1184
                build-parent of the version, i.e. the leftmost ancestor.
1239
1185
                Will be None if the record is not a delta.
1240
 
 
1241
1186
        :param keys: The keys to build a map for
1242
1187
        :param allow_missing: If some records are missing, rather than
1243
1188
            error, just return the data that could be generated.
1499
1444
                                                                non_local_keys,
1500
1445
                                                                positions):
1501
1446
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1502
 
                                                   global_map,
1503
 
                                                   ordering=ordering)
 
1447
                                                   global_map)
1504
1448
                for record in generator.get_record_stream():
1505
1449
                    yield record
1506
1450
        else:
1508
1452
                if source is parent_maps[0]:
1509
1453
                    # this KnitVersionedFiles
1510
1454
                    records = [(key, positions[key][1]) for key in keys]
1511
 
                    for key, raw_data in self._read_records_iter_unchecked(records):
 
1455
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
1512
1456
                        (record_details, index_memo, _) = positions[key]
1513
1457
                        yield KnitContentFactory(key, global_map[key],
1514
 
                            record_details, None, raw_data, self._factory.annotated, None)
 
1458
                            record_details, sha1, raw_data, self._factory.annotated, None)
1515
1459
                else:
1516
 
                    vf = self._immediate_fallback_vfs[parent_maps.index(source) - 1]
 
1460
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1517
1461
                    for record in vf.get_record_stream(keys, ordering,
1518
1462
                        include_delta_closure):
1519
1463
                        yield record
1529
1473
            # record entry 2 is the 'digest'.
1530
1474
            result[key] = details[2]
1531
1475
        missing.difference_update(set(result))
1532
 
        for source in self._immediate_fallback_vfs:
 
1476
        for source in self._fallback_vfs:
1533
1477
            if not missing:
1534
1478
                break
1535
1479
            new_result = source.get_sha1s(missing)
1586
1530
        # key = basis_parent, value = index entry to add
1587
1531
        buffered_index_entries = {}
1588
1532
        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
1533
            buffered = False
1597
1534
            parents = record.parents
1598
1535
            if record.storage_kind in delta_types:
1606
1543
                raise RevisionNotPresent([record.key], self)
1607
1544
            elif ((record.storage_kind in knit_types)
1608
1545
                  and (compression_parent is None
1609
 
                       or not self._immediate_fallback_vfs
 
1546
                       or not self._fallback_vfs
1610
1547
                       or self._index.has_key(compression_parent)
1611
1548
                       or not self.has_key(compression_parent))):
1612
1549
                # we can insert the knit record literally if either it has no
1672
1609
                # KnitVersionedFiles doesn't permit deltas (_max_delta_chain ==
1673
1610
                # 0) or because it depends on a base only present in the
1674
1611
                # fallback kvfs.
1675
 
                self._access.flush()
1676
1612
                try:
1677
1613
                    # Try getting a fulltext directly from the record.
1678
1614
                    bytes = record.get_bytes_as('fulltext')
1700
1636
            # There were index entries buffered at the end of the stream,
1701
1637
            # So these need to be added (if the index supports holding such
1702
1638
            # entries for later insertion)
1703
 
            all_entries = []
1704
1639
            for key in buffered_index_entries:
1705
1640
                index_entries = buffered_index_entries[key]
1706
 
                all_entries.extend(index_entries)
1707
 
            self._index.add_records(
1708
 
                all_entries, missing_compression_parents=True)
 
1641
                self._index.add_records(index_entries,
 
1642
                    missing_compression_parents=True)
1709
1643
 
1710
1644
    def get_missing_compression_parent_keys(self):
1711
1645
        """Return an iterable of keys of missing compression parents.
1744
1678
        :return: An iterator over (line, key).
1745
1679
        """
1746
1680
        if pb is None:
1747
 
            pb = ui.ui_factory.nested_progress_bar()
 
1681
            pb = progress.DummyProgress()
1748
1682
        keys = set(keys)
1749
1683
        total = len(keys)
1750
1684
        done = False
1784
1718
        # vfs, and hope to find them there.  Note that if the keys are found
1785
1719
        # but had no changes or no content, the fallback may not return
1786
1720
        # anything.
1787
 
        if keys and not self._immediate_fallback_vfs:
 
1721
        if keys and not self._fallback_vfs:
1788
1722
            # XXX: strictly the second parameter is meant to be the file id
1789
1723
            # but it's not easily accessible here.
1790
1724
            raise RevisionNotPresent(keys, repr(self))
1791
 
        for source in self._immediate_fallback_vfs:
 
1725
        for source in self._fallback_vfs:
1792
1726
            if not keys:
1793
1727
                break
1794
1728
            source_keys = set()
1867
1801
        :return: the header and the decompressor stream.
1868
1802
                 as (stream, header_record)
1869
1803
        """
1870
 
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
1804
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
1871
1805
        try:
1872
1806
            # Current serialise
1873
1807
            rec = self._check_header(key, df.readline())
1882
1816
        # 4168 calls in 2880 217 internal
1883
1817
        # 4168 calls to _parse_record_header in 2121
1884
1818
        # 4168 calls to readlines in 330
1885
 
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(data))
 
1819
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(data))
1886
1820
        try:
1887
1821
            record_contents = df.readlines()
1888
1822
        except Exception, e:
1910
1844
        The result will be returned in whatever is the fastest to read.
1911
1845
        Not by the order requested. Also, multiple requests for the same
1912
1846
        record will only yield 1 response.
1913
 
 
1914
1847
        :param records: A list of (key, access_memo) entries
1915
1848
        :return: Yields (key, contents, digest) in the order
1916
1849
                 read, not the order requested
1974
1907
        :param key: The key of the record. Currently keys are always serialised
1975
1908
            using just the trailing component.
1976
1909
        :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.
 
1910
            instance, if lines is a list of 1000 bytestrings each ending in \n,
 
1911
            dense_lines may be a list with one line in it, containing all the
 
1912
            1000's lines and their \n's. Using dense_lines if it is already
 
1913
            known is a win because the string join to create bytes in this
 
1914
            function spends less time resizing the final string.
1982
1915
        :return: (len, a StringIO instance with the raw data ready to read.)
1983
1916
        """
1984
 
        chunks = ["version %s %d %s\n" % (key[-1], len(lines), digest)]
1985
 
        chunks.extend(dense_lines or lines)
1986
 
        chunks.append("end %s\n" % key[-1])
1987
 
        for chunk in chunks:
1988
 
            if type(chunk) is not str:
1989
 
                raise AssertionError(
1990
 
                    'data must be plain bytes was %s' % type(chunk))
 
1917
        # Note: using a string copy here increases memory pressure with e.g.
 
1918
        # ISO's, but it is about 3 seconds faster on a 1.2Ghz intel machine
 
1919
        # when doing the initial commit of a mozilla tree. RBC 20070921
 
1920
        bytes = ''.join(chain(
 
1921
            ["version %s %d %s\n" % (key[-1],
 
1922
                                     len(lines),
 
1923
                                     digest)],
 
1924
            dense_lines or lines,
 
1925
            ["end %s\n" % key[-1]]))
 
1926
        if type(bytes) != str:
 
1927
            raise AssertionError(
 
1928
                'data must be plain bytes was %s' % type(bytes))
1991
1929
        if lines and lines[-1][-1] != '\n':
1992
1930
            raise ValueError('corrupt lines value %r' % lines)
1993
 
        compressed_bytes = tuned_gzip.chunks_to_gzip(chunks)
 
1931
        compressed_bytes = tuned_gzip.bytes_to_gzip(bytes)
1994
1932
        return len(compressed_bytes), compressed_bytes
1995
1933
 
1996
1934
    def _split_header(self, line):
2004
1942
        """See VersionedFiles.keys."""
2005
1943
        if 'evil' in debug.debug_flags:
2006
1944
            trace.mutter_callsite(2, "keys scales with size of history")
2007
 
        sources = [self._index] + self._immediate_fallback_vfs
 
1945
        sources = [self._index] + self._fallback_vfs
2008
1946
        result = set()
2009
1947
        for source in sources:
2010
1948
            result.update(source.keys())
2014
1952
class _ContentMapGenerator(object):
2015
1953
    """Generate texts or expose raw deltas for a set of texts."""
2016
1954
 
2017
 
    def __init__(self, ordering='unordered'):
2018
 
        self._ordering = ordering
2019
 
 
2020
1955
    def _get_content(self, key):
2021
1956
        """Get the content object for key."""
2022
1957
        # Note that _get_content is only called when the _ContentMapGenerator
2050
1985
 
2051
1986
        missing_keys = set(nonlocal_keys)
2052
1987
        # Read from remote versioned file instances and provide to our caller.
2053
 
        for source in self.vf._immediate_fallback_vfs:
 
1988
        for source in self.vf._fallback_vfs:
2054
1989
            if not missing_keys:
2055
1990
                break
2056
1991
            # Loop over fallback repositories asking them for texts - ignore
2057
1992
            # any missing from a particular fallback.
2058
1993
            for record in source.get_record_stream(missing_keys,
2059
 
                self._ordering, True):
 
1994
                'unordered', True):
2060
1995
                if record.storage_kind == 'absent':
2061
1996
                    # Not in thie particular stream, may be in one of the
2062
1997
                    # other fallback vfs objects.
2064
1999
                missing_keys.remove(record.key)
2065
2000
                yield record
2066
2001
 
2067
 
        if self._raw_record_map is None:
2068
 
            raise AssertionError('_raw_record_map should have been filled')
 
2002
        self._raw_record_map = self.vf._get_record_map_unparsed(self.keys,
 
2003
            allow_missing=True)
2069
2004
        first = True
2070
2005
        for key in self.keys:
2071
2006
            if key in self.nonlocal_keys:
2194
2129
    """Content map generator reading from a VersionedFiles object."""
2195
2130
 
2196
2131
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2197
 
        global_map=None, raw_record_map=None, ordering='unordered'):
 
2132
        global_map=None, raw_record_map=None):
2198
2133
        """Create a _ContentMapGenerator.
2199
2134
 
2200
2135
        :param versioned_files: The versioned files that the texts are being
2208
2143
        :param raw_record_map: A unparsed raw record map to use for answering
2209
2144
            contents.
2210
2145
        """
2211
 
        _ContentMapGenerator.__init__(self, ordering=ordering)
2212
2146
        # The vf to source data from
2213
2147
        self.vf = versioned_files
2214
2148
        # The keys desired
2358
2292
    FLAGS is a comma separated list of flags about the record. Values include
2359
2293
        no-eol, line-delta, fulltext.
2360
2294
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2361
 
        that the compressed data starts at.
 
2295
        that the the compressed data starts at.
2362
2296
    LENGTH is the ascii representation of the length of the data file.
2363
2297
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2364
2298
        REVISION_ID.
2435
2369
                    line = "\n%s %s %s %s %s :" % (
2436
2370
                        key[-1], ','.join(options), pos, size,
2437
2371
                        self._dictionary_compress(parents))
2438
 
                    if type(line) is not str:
 
2372
                    if type(line) != str:
2439
2373
                        raise AssertionError(
2440
2374
                            'data must be utf8 was %s' % type(line))
2441
2375
                    lines.append(line)
2573
2507
        except KeyError:
2574
2508
            raise RevisionNotPresent(key, self)
2575
2509
 
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
2510
    def get_parent_map(self, keys):
2604
2511
        """Get a map of the parents of keys.
2605
2512
 
2657
2564
        result = set()
2658
2565
        # Identify all key prefixes.
2659
2566
        # XXX: A bit hacky, needs polish.
2660
 
        if type(self._mapper) is ConstantMapper:
 
2567
        if type(self._mapper) == ConstantMapper:
2661
2568
            prefixes = [()]
2662
2569
        else:
2663
2570
            relpaths = set()
2695
2602
                    del self._history
2696
2603
                except NoSuchFile:
2697
2604
                    self._kndx_cache[prefix] = ({}, [])
2698
 
                    if type(self._mapper) is ConstantMapper:
 
2605
                    if type(self._mapper) == ConstantMapper:
2699
2606
                        # preserve behaviour for revisions.kndx etc.
2700
2607
                        self._init_index(path)
2701
2608
                    del self._cache
2779
2686
    """A KnitVersionedFiles index layered on GraphIndex."""
2780
2687
 
2781
2688
    def __init__(self, graph_index, is_locked, deltas=False, parents=True,
2782
 
        add_callback=None, track_external_parent_refs=False):
 
2689
        add_callback=None):
2783
2690
        """Construct a KnitGraphIndex on a graph_index.
2784
2691
 
2785
2692
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
2793
2700
            [(node, value, node_refs), ...]
2794
2701
        :param is_locked: A callback, returns True if the index is locked and
2795
2702
            thus usable.
2796
 
        :param track_external_parent_refs: If True, record all external parent
2797
 
            references parents from added records.  These can be retrieved
2798
 
            later by calling get_missing_parents().
2799
2703
        """
2800
2704
        self._add_callback = add_callback
2801
2705
        self._graph_index = graph_index
2809
2713
        self.has_graph = parents
2810
2714
        self._is_locked = is_locked
2811
2715
        self._missing_compression_parents = set()
2812
 
        if track_external_parent_refs:
2813
 
            self._key_dependencies = _KeyRefs()
2814
 
        else:
2815
 
            self._key_dependencies = None
2816
2716
 
2817
2717
    def __repr__(self):
2818
2718
        return "%s(%r)" % (self.__class__.__name__, self._graph_index)
2842
2742
 
2843
2743
        keys = {}
2844
2744
        compression_parents = set()
2845
 
        key_dependencies = self._key_dependencies
2846
2745
        for (key, options, access_memo, parents) in records:
2847
2746
            if self._parents:
2848
2747
                parents = tuple(parents)
2849
 
                if key_dependencies is not None:
2850
 
                    key_dependencies.add_references(key, parents)
2851
2748
            index, pos, size = access_memo
2852
2749
            if 'no-eol' in options:
2853
2750
                value = 'N'
2877
2774
        if not random_id:
2878
2775
            present_nodes = self._get_entries(keys)
2879
2776
            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
2777
                if (value[0] != keys[key][0][0] or
2885
 
                    parents != passed_parents):
2886
 
                    node_refs = static_tuple.as_tuples(node_refs)
 
2778
                    node_refs[:1] != keys[key][1][:1]):
2887
2779
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2888
 
                        ": %s %s" % ((value, node_refs), passed))
 
2780
                        ": %s %s" % ((value, node_refs), keys[key]))
2889
2781
                del keys[key]
2890
2782
        result = []
2891
2783
        if self._parents:
2920
2812
            new_missing = graph_index.external_references(ref_list_num=1)
2921
2813
            new_missing.difference_update(self.get_parent_map(new_missing))
2922
2814
            self._missing_compression_parents.update(new_missing)
2923
 
        if self._key_dependencies is not None:
2924
 
            # Add parent refs from graph_index (and discard parent refs that
2925
 
            # the graph_index has).
2926
 
            for node in graph_index.iter_all_entries():
2927
 
                self._key_dependencies.add_references(node[1], node[3][0])
2928
2815
 
2929
2816
    def get_missing_compression_parents(self):
2930
2817
        """Return the keys of missing compression parents.
2934
2821
        """
2935
2822
        return frozenset(self._missing_compression_parents)
2936
2823
 
2937
 
    def get_missing_parents(self):
2938
 
        """Return the keys of missing parents."""
2939
 
        # If updating this, you should also update
2940
 
        # groupcompress._GCGraphIndex.get_missing_parents
2941
 
        # We may have false positives, so filter those out.
2942
 
        self._key_dependencies.satisfy_refs_for_keys(
2943
 
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2944
 
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
2945
 
 
2946
2824
    def _check_read(self):
2947
2825
        """raise if reads are not permitted."""
2948
2826
        if not self._is_locked():
3056
2934
            options.append('no-eol')
3057
2935
        return options
3058
2936
 
3059
 
    def find_ancestry(self, keys):
3060
 
        """See CombinedGraphIndex.find_ancestry()"""
3061
 
        return self._graph_index.find_ancestry(keys, 0)
3062
 
 
3063
2937
    def get_parent_map(self, keys):
3064
2938
        """Get a map of the parents of keys.
3065
2939
 
3152
3026
            opaque index memo. For _KnitKeyAccess the memo is (key, pos,
3153
3027
            length), where the key is the record key.
3154
3028
        """
3155
 
        if type(raw_data) is not str:
 
3029
        if type(raw_data) != str:
3156
3030
            raise AssertionError(
3157
3031
                'data must be plain bytes was %s' % type(raw_data))
3158
3032
        result = []
3175
3049
            result.append((key, base, size))
3176
3050
        return result
3177
3051
 
3178
 
    def flush(self):
3179
 
        """Flush pending writes on this access object.
3180
 
        
3181
 
        For .knit files this is a no-op.
3182
 
        """
3183
 
        pass
3184
 
 
3185
3052
    def get_raw_records(self, memos_for_retrieval):
3186
3053
        """Get the raw bytes for a records.
3187
3054
 
3212
3079
class _DirectPackAccess(object):
3213
3080
    """Access to data in one or more packs with less translation."""
3214
3081
 
3215
 
    def __init__(self, index_to_packs, reload_func=None, flush_func=None):
 
3082
    def __init__(self, index_to_packs, reload_func=None):
3216
3083
        """Create a _DirectPackAccess object.
3217
3084
 
3218
3085
        :param index_to_packs: A dict mapping index objects to the transport
3225
3092
        self._write_index = None
3226
3093
        self._indices = index_to_packs
3227
3094
        self._reload_func = reload_func
3228
 
        self._flush_func = flush_func
3229
3095
 
3230
3096
    def add_raw_records(self, key_sizes, raw_data):
3231
3097
        """Add raw knit bytes to a storage area.
3241
3107
            length), where the index field is the write_index object supplied
3242
3108
            to the PackAccess object.
3243
3109
        """
3244
 
        if type(raw_data) is not str:
 
3110
        if type(raw_data) != str:
3245
3111
            raise AssertionError(
3246
3112
                'data must be plain bytes was %s' % type(raw_data))
3247
3113
        result = []
3253
3119
            result.append((self._write_index, p_offset, p_length))
3254
3120
        return result
3255
3121
 
3256
 
    def flush(self):
3257
 
        """Flush pending writes on this access object.
3258
 
 
3259
 
        This will flush any buffered writes to a NewPack.
3260
 
        """
3261
 
        if self._flush_func is not None:
3262
 
            self._flush_func()
3263
 
            
3264
3122
    def get_raw_records(self, memos_for_retrieval):
3265
3123
        """Get the raw bytes for a records.
3266
3124
 
3348
3206
            raise exc_class, exc_value, exc_traceback
3349
3207
 
3350
3208
 
 
3209
# Deprecated, use PatienceSequenceMatcher instead
 
3210
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
 
3211
 
 
3212
 
3351
3213
def annotate_knit(knit, revision_id):
3352
3214
    """Annotate a knit with no cached annotations.
3353
3215
 
3356
3218
    recommended.
3357
3219
    """
3358
3220
    annotator = _KnitAnnotator(knit)
3359
 
    return iter(annotator.annotate_flat(revision_id))
3360
 
 
3361
 
 
3362
 
class _KnitAnnotator(annotate.Annotator):
 
3221
    return iter(annotator.annotate(revision_id))
 
3222
 
 
3223
 
 
3224
class _KnitAnnotator(object):
3363
3225
    """Build up the annotations for a text."""
3364
3226
 
3365
 
    def __init__(self, vf):
3366
 
        annotate.Annotator.__init__(self, vf)
3367
 
 
3368
 
        # TODO: handle Nodes which cannot be extracted
3369
 
        # self._ghosts = set()
3370
 
 
3371
 
        # Map from (key, parent_key) => matching_blocks, should be 'use once'
3372
 
        self._matching_blocks = {}
3373
 
 
3374
 
        # KnitContent objects
3375
 
        self._content_objects = {}
3376
 
        # The number of children that depend on this fulltext content object
3377
 
        self._num_compression_children = {}
3378
 
        # Delta records that need their compression parent before they can be
3379
 
        # expanded
3380
 
        self._pending_deltas = {}
3381
 
        # Fulltext records that are waiting for their parents fulltexts before
3382
 
        # they can be yielded for annotation
3383
 
        self._pending_annotation = {}
 
3227
    def __init__(self, knit):
 
3228
        self._knit = knit
 
3229
 
 
3230
        # Content objects, differs from fulltexts because of how final newlines
 
3231
        # are treated by knits. the content objects here will always have a
 
3232
        # final newline
 
3233
        self._fulltext_contents = {}
 
3234
 
 
3235
        # Annotated lines of specific revisions
 
3236
        self._annotated_lines = {}
 
3237
 
 
3238
        # Track the raw data for nodes that we could not process yet.
 
3239
        # This maps the revision_id of the base to a list of children that will
 
3240
        # annotated from it.
 
3241
        self._pending_children = {}
 
3242
 
 
3243
        # Nodes which cannot be extracted
 
3244
        self._ghosts = set()
 
3245
 
 
3246
        # Track how many children this node has, so we know if we need to keep
 
3247
        # it
 
3248
        self._annotate_children = {}
 
3249
        self._compression_children = {}
3384
3250
 
3385
3251
        self._all_build_details = {}
 
3252
        # The children => parent revision_id graph
 
3253
        self._revision_id_graph = {}
 
3254
 
 
3255
        self._heads_provider = None
 
3256
 
 
3257
        self._nodes_to_keep_annotations = set()
 
3258
        self._generations_until_keep = 100
 
3259
 
 
3260
    def set_generations_until_keep(self, value):
 
3261
        """Set the number of generations before caching a node.
 
3262
 
 
3263
        Setting this to -1 will cache every merge node, setting this higher
 
3264
        will cache fewer nodes.
 
3265
        """
 
3266
        self._generations_until_keep = value
 
3267
 
 
3268
    def _add_fulltext_content(self, revision_id, content_obj):
 
3269
        self._fulltext_contents[revision_id] = content_obj
 
3270
        # TODO: jam 20080305 It might be good to check the sha1digest here
 
3271
        return content_obj.text()
 
3272
 
 
3273
    def _check_parents(self, child, nodes_to_annotate):
 
3274
        """Check if all parents have been processed.
 
3275
 
 
3276
        :param child: A tuple of (rev_id, parents, raw_content)
 
3277
        :param nodes_to_annotate: If child is ready, add it to
 
3278
            nodes_to_annotate, otherwise put it back in self._pending_children
 
3279
        """
 
3280
        for parent_id in child[1]:
 
3281
            if (parent_id not in self._annotated_lines):
 
3282
                # This parent is present, but another parent is missing
 
3283
                self._pending_children.setdefault(parent_id,
 
3284
                                                  []).append(child)
 
3285
                break
 
3286
        else:
 
3287
            # This one is ready to be processed
 
3288
            nodes_to_annotate.append(child)
 
3289
 
 
3290
    def _add_annotation(self, revision_id, fulltext, parent_ids,
 
3291
                        left_matching_blocks=None):
 
3292
        """Add an annotation entry.
 
3293
 
 
3294
        All parents should already have been annotated.
 
3295
        :return: A list of children that now have their parents satisfied.
 
3296
        """
 
3297
        a = self._annotated_lines
 
3298
        annotated_parent_lines = [a[p] for p in parent_ids]
 
3299
        annotated_lines = list(annotate.reannotate(annotated_parent_lines,
 
3300
            fulltext, revision_id, left_matching_blocks,
 
3301
            heads_provider=self._get_heads_provider()))
 
3302
        self._annotated_lines[revision_id] = annotated_lines
 
3303
        for p in parent_ids:
 
3304
            ann_children = self._annotate_children[p]
 
3305
            ann_children.remove(revision_id)
 
3306
            if (not ann_children
 
3307
                and p not in self._nodes_to_keep_annotations):
 
3308
                del self._annotated_lines[p]
 
3309
                del self._all_build_details[p]
 
3310
                if p in self._fulltext_contents:
 
3311
                    del self._fulltext_contents[p]
 
3312
        # Now that we've added this one, see if there are any pending
 
3313
        # deltas to be done, certainly this parent is finished
 
3314
        nodes_to_annotate = []
 
3315
        for child in self._pending_children.pop(revision_id, []):
 
3316
            self._check_parents(child, nodes_to_annotate)
 
3317
        return nodes_to_annotate
3386
3318
 
3387
3319
    def _get_build_graph(self, key):
3388
3320
        """Get the graphs for building texts and annotations.
3393
3325
        fulltext.)
3394
3326
 
3395
3327
        :return: A list of (key, index_memo) records, suitable for
3396
 
            passing to read_records_iter to start reading in the raw data from
 
3328
            passing to read_records_iter to start reading in the raw data fro/
3397
3329
            the pack file.
3398
3330
        """
 
3331
        if key in self._annotated_lines:
 
3332
            # Nothing to do
 
3333
            return []
3399
3334
        pending = set([key])
3400
3335
        records = []
3401
 
        ann_keys = set()
3402
 
        self._num_needed_children[key] = 1
 
3336
        generation = 0
 
3337
        kept_generation = 0
3403
3338
        while pending:
3404
3339
            # get all pending nodes
 
3340
            generation += 1
3405
3341
            this_iteration = pending
3406
 
            build_details = self._vf._index.get_build_details(this_iteration)
 
3342
            build_details = self._knit._index.get_build_details(this_iteration)
3407
3343
            self._all_build_details.update(build_details)
3408
 
            # new_nodes = self._vf._index._get_entries(this_iteration)
 
3344
            # new_nodes = self._knit._index._get_entries(this_iteration)
3409
3345
            pending = set()
3410
3346
            for key, details in build_details.iteritems():
3411
 
                (index_memo, compression_parent, parent_keys,
 
3347
                (index_memo, compression_parent, parents,
3412
3348
                 record_details) = details
3413
 
                self._parent_map[key] = parent_keys
3414
 
                self._heads_provider = None
 
3349
                self._revision_id_graph[key] = parents
3415
3350
                records.append((key, index_memo))
3416
3351
                # Do we actually need to check _annotated_lines?
3417
 
                pending.update([p for p in parent_keys
3418
 
                                   if p not in self._all_build_details])
3419
 
                if parent_keys:
3420
 
                    for parent_key in parent_keys:
3421
 
                        if parent_key in self._num_needed_children:
3422
 
                            self._num_needed_children[parent_key] += 1
3423
 
                        else:
3424
 
                            self._num_needed_children[parent_key] = 1
 
3352
                pending.update(p for p in parents
 
3353
                                 if p not in self._all_build_details)
3425
3354
                if compression_parent:
3426
 
                    if compression_parent in self._num_compression_children:
3427
 
                        self._num_compression_children[compression_parent] += 1
3428
 
                    else:
3429
 
                        self._num_compression_children[compression_parent] = 1
 
3355
                    self._compression_children.setdefault(compression_parent,
 
3356
                        []).append(key)
 
3357
                if parents:
 
3358
                    for parent in parents:
 
3359
                        self._annotate_children.setdefault(parent,
 
3360
                            []).append(key)
 
3361
                    num_gens = generation - kept_generation
 
3362
                    if ((num_gens >= self._generations_until_keep)
 
3363
                        and len(parents) > 1):
 
3364
                        kept_generation = generation
 
3365
                        self._nodes_to_keep_annotations.add(key)
3430
3366
 
3431
3367
            missing_versions = this_iteration.difference(build_details.keys())
3432
 
            if missing_versions:
3433
 
                for key in missing_versions:
3434
 
                    if key in self._parent_map and key in self._text_cache:
3435
 
                        # We already have this text ready, we just need to
3436
 
                        # yield it later so we get it annotated
3437
 
                        ann_keys.add(key)
3438
 
                        parent_keys = self._parent_map[key]
3439
 
                        for parent_key in parent_keys:
3440
 
                            if parent_key in self._num_needed_children:
3441
 
                                self._num_needed_children[parent_key] += 1
3442
 
                            else:
3443
 
                                self._num_needed_children[parent_key] = 1
3444
 
                        pending.update([p for p in parent_keys
3445
 
                                           if p not in self._all_build_details])
3446
 
                    else:
3447
 
                        raise errors.RevisionNotPresent(key, self._vf)
 
3368
            self._ghosts.update(missing_versions)
 
3369
            for missing_version in missing_versions:
 
3370
                # add a key, no parents
 
3371
                self._revision_id_graph[missing_version] = ()
 
3372
                pending.discard(missing_version) # don't look for it
 
3373
        if self._ghosts.intersection(self._compression_children):
 
3374
            raise KnitCorrupt(
 
3375
                "We cannot have nodes which have a ghost compression parent:\n"
 
3376
                "ghosts: %r\n"
 
3377
                "compression children: %r"
 
3378
                % (self._ghosts, self._compression_children))
 
3379
        # Cleanout anything that depends on a ghost so that we don't wait for
 
3380
        # the ghost to show up
 
3381
        for node in self._ghosts:
 
3382
            if node in self._annotate_children:
 
3383
                # We won't be building this node
 
3384
                del self._annotate_children[node]
3448
3385
        # Generally we will want to read the records in reverse order, because
3449
3386
        # we find the parent nodes after the children
3450
3387
        records.reverse()
3451
 
        return records, ann_keys
3452
 
 
3453
 
    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:
3456
 
            # If we have fallbacks, go to the generic path
3457
 
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
3458
 
                yield v
3459
 
            return
3460
 
        while True:
3461
 
            try:
3462
 
                records, ann_keys = self._get_build_graph(key)
3463
 
                for idx, (sub_key, text, num_lines) in enumerate(
3464
 
                                                self._extract_texts(records)):
3465
 
                    if pb is not None:
3466
 
                        pb.update('annotating', idx, len(records))
3467
 
                    yield sub_key, text, num_lines
3468
 
                for sub_key in ann_keys:
3469
 
                    text = self._text_cache[sub_key]
3470
 
                    num_lines = len(text) # bad assumption
3471
 
                    yield sub_key, text, num_lines
3472
 
                return
3473
 
            except errors.RetryWithNewPacks, e:
3474
 
                self._vf._access.reload_or_raise(e)
3475
 
                # The cached build_details are no longer valid
3476
 
                self._all_build_details.clear()
3477
 
 
3478
 
    def _cache_delta_blocks(self, key, compression_parent, delta, lines):
3479
 
        parent_lines = self._text_cache[compression_parent]
3480
 
        blocks = list(KnitContent.get_line_delta_blocks(delta, parent_lines, lines))
3481
 
        self._matching_blocks[(key, compression_parent)] = blocks
3482
 
 
3483
 
    def _expand_record(self, key, parent_keys, compression_parent, record,
3484
 
                       record_details):
3485
 
        delta = None
3486
 
        if compression_parent:
3487
 
            if compression_parent not in self._content_objects:
3488
 
                # Waiting for the parent
3489
 
                self._pending_deltas.setdefault(compression_parent, []).append(
3490
 
                    (key, parent_keys, record, record_details))
3491
 
                return None
3492
 
            # We have the basis parent, so expand the delta
3493
 
            num = self._num_compression_children[compression_parent]
3494
 
            num -= 1
3495
 
            if num == 0:
3496
 
                base_content = self._content_objects.pop(compression_parent)
3497
 
                self._num_compression_children.pop(compression_parent)
3498
 
            else:
3499
 
                self._num_compression_children[compression_parent] = num
3500
 
                base_content = self._content_objects[compression_parent]
3501
 
            # It is tempting to want to copy_base_content=False for the last
3502
 
            # child object. However, whenever noeol=False,
3503
 
            # self._text_cache[parent_key] is content._lines. So mutating it
3504
 
            # gives very bad results.
3505
 
            # The alternative is to copy the lines into text cache, but then we
3506
 
            # are copying anyway, so just do it here.
3507
 
            content, delta = self._vf._factory.parse_record(
3508
 
                key, record, record_details, base_content,
3509
 
                copy_base_content=True)
3510
 
        else:
3511
 
            # Fulltext record
3512
 
            content, _ = self._vf._factory.parse_record(
3513
 
                key, record, record_details, None)
3514
 
        if self._num_compression_children.get(key, 0) > 0:
3515
 
            self._content_objects[key] = content
3516
 
        lines = content.text()
3517
 
        self._text_cache[key] = lines
3518
 
        if delta is not None:
3519
 
            self._cache_delta_blocks(key, compression_parent, delta, lines)
3520
 
        return lines
3521
 
 
3522
 
    def _get_parent_annotations_and_matches(self, key, text, parent_key):
3523
 
        """Get the list of annotations for the parent, and the matching lines.
3524
 
 
3525
 
        :param text: The opaque value given by _get_needed_texts
3526
 
        :param parent_key: The key for the parent text
3527
 
        :return: (parent_annotations, matching_blocks)
3528
 
            parent_annotations is a list as long as the number of lines in
3529
 
                parent
3530
 
            matching_blocks is a list of (parent_idx, text_idx, len) tuples
3531
 
                indicating which lines match between the two texts
3532
 
        """
3533
 
        block_key = (key, parent_key)
3534
 
        if block_key in self._matching_blocks:
3535
 
            blocks = self._matching_blocks.pop(block_key)
3536
 
            parent_annotations = self._annotations_cache[parent_key]
3537
 
            return parent_annotations, blocks
3538
 
        return annotate.Annotator._get_parent_annotations_and_matches(self,
3539
 
            key, text, parent_key)
3540
 
 
3541
 
    def _process_pending(self, key):
3542
 
        """The content for 'key' was just processed.
3543
 
 
3544
 
        Determine if there is any more pending work to be processed.
3545
 
        """
3546
 
        to_return = []
3547
 
        if key in self._pending_deltas:
3548
 
            compression_parent = key
3549
 
            children = self._pending_deltas.pop(key)
3550
 
            for child_key, parent_keys, record, record_details in children:
3551
 
                lines = self._expand_record(child_key, parent_keys,
3552
 
                                            compression_parent,
3553
 
                                            record, record_details)
3554
 
                if self._check_ready_for_annotations(child_key, parent_keys):
3555
 
                    to_return.append(child_key)
3556
 
        # Also check any children that are waiting for this parent to be
3557
 
        # annotation ready
3558
 
        if key in self._pending_annotation:
3559
 
            children = self._pending_annotation.pop(key)
3560
 
            to_return.extend([c for c, p_keys in children
3561
 
                              if self._check_ready_for_annotations(c, p_keys)])
3562
 
        return to_return
3563
 
 
3564
 
    def _check_ready_for_annotations(self, key, parent_keys):
3565
 
        """return true if this text is ready to be yielded.
3566
 
 
3567
 
        Otherwise, this will return False, and queue the text into
3568
 
        self._pending_annotation
3569
 
        """
3570
 
        for parent_key in parent_keys:
3571
 
            if parent_key not in self._annotations_cache:
3572
 
                # still waiting on at least one parent text, so queue it up
3573
 
                # Note that if there are multiple parents, we need to wait
3574
 
                # for all of them.
3575
 
                self._pending_annotation.setdefault(parent_key,
3576
 
                    []).append((key, parent_keys))
3577
 
                return False
3578
 
        return True
3579
 
 
3580
 
    def _extract_texts(self, records):
3581
 
        """Extract the various texts needed based on records"""
 
3388
        return records
 
3389
 
 
3390
    def _annotate_records(self, records):
 
3391
        """Build the annotations for the listed records."""
3582
3392
        # We iterate in the order read, rather than a strict order requested
3583
3393
        # However, process what we can, and put off to the side things that
3584
3394
        # still need parents, cleaning them up when those parents are
3585
3395
        # processed.
3586
 
        # Basic data flow:
3587
 
        #   1) As 'records' are read, see if we can expand these records into
3588
 
        #      Content objects (and thus lines)
3589
 
        #   2) If a given line-delta is waiting on its compression parent, it
3590
 
        #      gets queued up into self._pending_deltas, otherwise we expand
3591
 
        #      it, and put it into self._text_cache and self._content_objects
3592
 
        #   3) If we expanded the text, we will then check to see if all
3593
 
        #      parents have also been processed. If so, this text gets yielded,
3594
 
        #      else this record gets set aside into pending_annotation
3595
 
        #   4) Further, if we expanded the text in (2), we will then check to
3596
 
        #      see if there are any children in self._pending_deltas waiting to
3597
 
        #      also be processed. If so, we go back to (2) for those
3598
 
        #   5) Further again, if we yielded the text, we can then check if that
3599
 
        #      'unlocks' any of the texts in pending_annotations, which should
3600
 
        #      then get yielded as well
3601
 
        # Note that both steps 4 and 5 are 'recursive' in that unlocking one
3602
 
        # compression child could unlock yet another, and yielding a fulltext
3603
 
        # will also 'unlock' the children that are waiting on that annotation.
3604
 
        # (Though also, unlocking 1 parent's fulltext, does not unlock a child
3605
 
        # if other parents are also waiting.)
3606
 
        # We want to yield content before expanding child content objects, so
3607
 
        # that we know when we can re-use the content lines, and the annotation
3608
 
        # code can know when it can stop caching fulltexts, as well.
3609
 
 
3610
 
        # Children that are missing their compression parent
3611
 
        pending_deltas = {}
3612
 
        for (key, record, digest) in self._vf._read_records_iter(records):
3613
 
            # ghosts?
3614
 
            details = self._all_build_details[key]
3615
 
            (_, compression_parent, parent_keys, record_details) = details
3616
 
            lines = self._expand_record(key, parent_keys, compression_parent,
3617
 
                                        record, record_details)
3618
 
            if lines is None:
3619
 
                # Pending delta should be queued up
 
3396
        for (rev_id, record,
 
3397
             digest) in self._knit._read_records_iter(records):
 
3398
            if rev_id in self._annotated_lines:
3620
3399
                continue
3621
 
            # At this point, we may be able to yield this content, if all
3622
 
            # parents are also finished
3623
 
            yield_this_text = self._check_ready_for_annotations(key,
3624
 
                                                                parent_keys)
3625
 
            if yield_this_text:
3626
 
                # All parents present
3627
 
                yield key, lines, len(lines)
3628
 
            to_process = self._process_pending(key)
3629
 
            while to_process:
3630
 
                this_process = to_process
3631
 
                to_process = []
3632
 
                for key in this_process:
3633
 
                    lines = self._text_cache[key]
3634
 
                    yield key, lines, len(lines)
3635
 
                    to_process.extend(self._process_pending(key))
 
3400
            parent_ids = self._revision_id_graph[rev_id]
 
3401
            parent_ids = [p for p in parent_ids if p not in self._ghosts]
 
3402
            details = self._all_build_details[rev_id]
 
3403
            (index_memo, compression_parent, parents,
 
3404
             record_details) = details
 
3405
            nodes_to_annotate = []
 
3406
            # TODO: Remove the punning between compression parents, and
 
3407
            #       parent_ids, we should be able to do this without assuming
 
3408
            #       the build order
 
3409
            if len(parent_ids) == 0:
 
3410
                # There are no parents for this node, so just add it
 
3411
                # TODO: This probably needs to be decoupled
 
3412
                fulltext_content, delta = self._knit._factory.parse_record(
 
3413
                    rev_id, record, record_details, None)
 
3414
                fulltext = self._add_fulltext_content(rev_id, fulltext_content)
 
3415
                nodes_to_annotate.extend(self._add_annotation(rev_id, fulltext,
 
3416
                    parent_ids, left_matching_blocks=None))
 
3417
            else:
 
3418
                child = (rev_id, parent_ids, record)
 
3419
                # Check if all the parents are present
 
3420
                self._check_parents(child, nodes_to_annotate)
 
3421
            while nodes_to_annotate:
 
3422
                # Should we use a queue here instead of a stack?
 
3423
                (rev_id, parent_ids, record) = nodes_to_annotate.pop()
 
3424
                (index_memo, compression_parent, parents,
 
3425
                 record_details) = self._all_build_details[rev_id]
 
3426
                blocks = None
 
3427
                if compression_parent is not None:
 
3428
                    comp_children = self._compression_children[compression_parent]
 
3429
                    if rev_id not in comp_children:
 
3430
                        raise AssertionError("%r not in compression children %r"
 
3431
                            % (rev_id, comp_children))
 
3432
                    # If there is only 1 child, it is safe to reuse this
 
3433
                    # content
 
3434
                    reuse_content = (len(comp_children) == 1
 
3435
                        and compression_parent not in
 
3436
                            self._nodes_to_keep_annotations)
 
3437
                    if reuse_content:
 
3438
                        # Remove it from the cache since it will be changing
 
3439
                        parent_fulltext_content = self._fulltext_contents.pop(compression_parent)
 
3440
                        # Make sure to copy the fulltext since it might be
 
3441
                        # modified
 
3442
                        parent_fulltext = list(parent_fulltext_content.text())
 
3443
                    else:
 
3444
                        parent_fulltext_content = self._fulltext_contents[compression_parent]
 
3445
                        parent_fulltext = parent_fulltext_content.text()
 
3446
                    comp_children.remove(rev_id)
 
3447
                    fulltext_content, delta = self._knit._factory.parse_record(
 
3448
                        rev_id, record, record_details,
 
3449
                        parent_fulltext_content,
 
3450
                        copy_base_content=(not reuse_content))
 
3451
                    fulltext = self._add_fulltext_content(rev_id,
 
3452
                                                          fulltext_content)
 
3453
                    if compression_parent == parent_ids[0]:
 
3454
                        # the compression_parent is the left parent, so we can
 
3455
                        # re-use the delta
 
3456
                        blocks = KnitContent.get_line_delta_blocks(delta,
 
3457
                                parent_fulltext, fulltext)
 
3458
                else:
 
3459
                    fulltext_content = self._knit._factory.parse_fulltext(
 
3460
                        record, rev_id)
 
3461
                    fulltext = self._add_fulltext_content(rev_id,
 
3462
                        fulltext_content)
 
3463
                nodes_to_annotate.extend(
 
3464
                    self._add_annotation(rev_id, fulltext, parent_ids,
 
3465
                                     left_matching_blocks=blocks))
 
3466
 
 
3467
    def _get_heads_provider(self):
 
3468
        """Create a heads provider for resolving ancestry issues."""
 
3469
        if self._heads_provider is not None:
 
3470
            return self._heads_provider
 
3471
        parent_provider = _mod_graph.DictParentsProvider(
 
3472
            self._revision_id_graph)
 
3473
        graph_obj = _mod_graph.Graph(parent_provider)
 
3474
        head_cache = _mod_graph.FrozenHeadsCache(graph_obj)
 
3475
        self._heads_provider = head_cache
 
3476
        return head_cache
 
3477
 
 
3478
    def annotate(self, key):
 
3479
        """Return the annotated fulltext at the given key.
 
3480
 
 
3481
        :param key: The key to annotate.
 
3482
        """
 
3483
        if len(self._knit._fallback_vfs) > 0:
 
3484
            # stacked knits can't use the fast path at present.
 
3485
            return self._simple_annotate(key)
 
3486
        while True:
 
3487
            try:
 
3488
                records = self._get_build_graph(key)
 
3489
                if key in self._ghosts:
 
3490
                    raise errors.RevisionNotPresent(key, self._knit)
 
3491
                self._annotate_records(records)
 
3492
                return self._annotated_lines[key]
 
3493
            except errors.RetryWithNewPacks, e:
 
3494
                self._knit._access.reload_or_raise(e)
 
3495
                # The cached build_details are no longer valid
 
3496
                self._all_build_details.clear()
 
3497
 
 
3498
    def _simple_annotate(self, key):
 
3499
        """Return annotated fulltext, rediffing from the full texts.
 
3500
 
 
3501
        This is slow but makes no assumptions about the repository
 
3502
        being able to produce line deltas.
 
3503
        """
 
3504
        # TODO: this code generates a parent maps of present ancestors; it
 
3505
        # could be split out into a separate method, and probably should use
 
3506
        # iter_ancestry instead. -- mbp and robertc 20080704
 
3507
        graph = _mod_graph.Graph(self._knit)
 
3508
        head_cache = _mod_graph.FrozenHeadsCache(graph)
 
3509
        search = graph._make_breadth_first_searcher([key])
 
3510
        keys = set()
 
3511
        while True:
 
3512
            try:
 
3513
                present, ghosts = search.next_with_ghosts()
 
3514
            except StopIteration:
 
3515
                break
 
3516
            keys.update(present)
 
3517
        parent_map = self._knit.get_parent_map(keys)
 
3518
        parent_cache = {}
 
3519
        reannotate = annotate.reannotate
 
3520
        for record in self._knit.get_record_stream(keys, 'topological', True):
 
3521
            key = record.key
 
3522
            fulltext = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
 
3523
            parents = parent_map[key]
 
3524
            if parents is not None:
 
3525
                parent_lines = [parent_cache[parent] for parent in parent_map[key]]
 
3526
            else:
 
3527
                parent_lines = []
 
3528
            parent_cache[key] = list(
 
3529
                reannotate(parent_lines, fulltext, key, None, head_cache))
 
3530
        try:
 
3531
            return parent_cache[key]
 
3532
        except KeyError, e:
 
3533
            raise errors.RevisionNotPresent(key, self._knit)
 
3534
 
3636
3535
 
3637
3536
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)
 
3537
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
 
3538
except ImportError:
3641
3539
    from bzrlib._knit_load_data_py import _load_data_py as _load_data