← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Jelmer Vernooij
  • Date: 2012-08-23 15:04:34 UTC
  • mto: This revision was merged to the branch mainline in revision 6555.
  • Revision ID: jelmer@samba.org-20120823150434-qq2olqvr4k07kpu4
Rename termcolor to _termcolor.

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
51
51
 
52
52
"""
53
53
 
 
54
from __future__ import absolute_import
 
55
 
54
56
 
55
57
from cStringIO import StringIO
56
 
from itertools import izip, chain
 
58
from itertools import izip
57
59
import operator
58
60
import os
59
 
import sys
60
61
 
61
62
from bzrlib.lazy_import import lazy_import
62
63
lazy_import(globals(), """
 
64
import gzip
 
65
 
63
66
from bzrlib import (
64
 
    annotate,
65
67
    debug,
66
68
    diff,
67
69
    graph as _mod_graph,
68
70
    index as _mod_index,
69
 
    lru_cache,
70
71
    pack,
71
 
    progress,
 
72
    patiencediff,
 
73
    static_tuple,
72
74
    trace,
73
75
    tsort,
74
76
    tuned_gzip,
 
77
    ui,
75
78
    )
 
79
 
 
80
from bzrlib.repofmt import pack_repo
 
81
from bzrlib.i18n import gettext
76
82
""")
77
83
from bzrlib import (
 
84
    annotate,
78
85
    errors,
79
86
    osutils,
80
 
    patiencediff,
81
87
    )
82
88
from bzrlib.errors import (
83
 
    FileExists,
84
89
    NoSuchFile,
85
 
    KnitError,
86
90
    InvalidRevisionId,
87
91
    KnitCorrupt,
88
92
    KnitHeaderError,
89
93
    RevisionNotPresent,
90
 
    RevisionAlreadyPresent,
91
94
    SHA1KnitCorrupt,
92
95
    )
93
96
from bzrlib.osutils import (
94
97
    contains_whitespace,
95
 
    contains_linebreaks,
96
98
    sha_string,
97
99
    sha_strings,
98
100
    split_lines,
99
101
    )
100
102
from bzrlib.versionedfile import (
 
103
    _KeyRefs,
101
104
    AbsentContentFactory,
102
105
    adapter_registry,
103
106
    ConstantMapper,
104
107
    ContentFactory,
105
 
    ChunkedContentFactory,
106
108
    sort_groupcompress,
107
 
    VersionedFile,
108
 
    VersionedFiles,
 
109
    VersionedFilesWithFallbacks,
109
110
    )
110
111
 
111
112
 
410
411
class KnitContent(object):
411
412
    """Content of a knit version to which deltas can be applied.
412
413
 
413
 
    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,
414
415
    plus a flag saying if the final ending is really there or not, because that
415
416
    corresponds to the on-disk knit representation.
416
417
    """
664
665
 
665
666
        see parse_fulltext which this inverts.
666
667
        """
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
669
668
        return ['%s %s' % (o, t) for o, t in content._lines]
670
669
 
671
670
    def lower_line_delta(self, delta):
686
685
        content = knit._get_content(key)
687
686
        # adjust for the fact that serialised annotations are only key suffixes
688
687
        # for this factory.
689
 
        if type(key) == tuple:
 
688
        if type(key) is tuple:
690
689
            prefix = key[:-1]
691
690
            origins = content.annotate()
692
691
            result = []
758
757
 
759
758
    def annotate(self, knit, key):
760
759
        annotator = _KnitAnnotator(knit)
761
 
        return annotator.annotate(key)
 
760
        return annotator.annotate_flat(key)
762
761
 
763
762
 
764
763
 
805
804
        writer.begin()
806
805
        index = _KnitGraphIndex(graph_index, lambda:True, parents=parents,
807
806
            deltas=delta, add_callback=graph_index.add_nodes)
808
 
        access = _DirectPackAccess({})
 
807
        access = pack_repo._DirectPackAccess({})
809
808
        access.set_writer(writer, graph_index, (transport, 'newpack'))
810
809
        result = KnitVersionedFiles(index, access,
811
810
            max_delta_chain=max_delta_chain)
849
848
                in all_build_index_memos.itervalues()])
850
849
 
851
850
 
852
 
class KnitVersionedFiles(VersionedFiles):
 
851
class KnitVersionedFiles(VersionedFilesWithFallbacks):
853
852
    """Storage for many versioned files using knit compression.
854
853
 
855
854
    Backend storage is managed by indices and data objects.
882
881
            self._factory = KnitAnnotateFactory()
883
882
        else:
884
883
            self._factory = KnitPlainFactory()
885
 
        self._fallback_vfs = []
 
884
        self._immediate_fallback_vfs = []
886
885
        self._reload_func = reload_func
887
886
 
888
887
    def __repr__(self):
891
890
            self._index,
892
891
            self._access)
893
892
 
 
893
    def without_fallbacks(self):
 
894
        """Return a clone of this object without any fallbacks configured."""
 
895
        return KnitVersionedFiles(self._index, self._access,
 
896
            self._max_delta_chain, self._factory.annotated,
 
897
            self._reload_func)
 
898
 
894
899
    def add_fallback_versioned_files(self, a_versioned_files):
895
900
        """Add a source of texts for texts not present in this knit.
896
901
 
897
902
        :param a_versioned_files: A VersionedFiles object.
898
903
        """
899
 
        self._fallback_vfs.append(a_versioned_files)
 
904
        self._immediate_fallback_vfs.append(a_versioned_files)
900
905
 
901
906
    def add_lines(self, key, parents, lines, parent_texts=None,
902
907
        left_matching_blocks=None, nostore_sha=None, random_id=False,
909
914
            # indexes can't directly store that, so we give them
910
915
            # an empty tuple instead.
911
916
            parents = ()
 
917
        line_bytes = ''.join(lines)
912
918
        return self._add(key, lines, parents,
913
 
            parent_texts, left_matching_blocks, nostore_sha, random_id)
 
919
            parent_texts, left_matching_blocks, nostore_sha, random_id,
 
920
            line_bytes=line_bytes)
 
921
 
 
922
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
 
923
        """See VersionedFiles._add_text()."""
 
924
        self._index._check_write_ok()
 
925
        self._check_add(key, None, random_id, check_content=False)
 
926
        if text.__class__ is not str:
 
927
            raise errors.BzrBadParameterUnicode("text")
 
928
        if parents is None:
 
929
            # The caller might pass None if there is no graph data, but kndx
 
930
            # indexes can't directly store that, so we give them
 
931
            # an empty tuple instead.
 
932
            parents = ()
 
933
        return self._add(key, None, parents,
 
934
            None, None, nostore_sha, random_id,
 
935
            line_bytes=text)
914
936
 
915
937
    def _add(self, key, lines, parents, parent_texts,
916
 
        left_matching_blocks, nostore_sha, random_id):
 
938
        left_matching_blocks, nostore_sha, random_id,
 
939
        line_bytes):
917
940
        """Add a set of lines on top of version specified by parents.
918
941
 
919
942
        Any versions not present will be converted into ghosts.
 
943
 
 
944
        :param lines: A list of strings where each one is a single line (has a
 
945
            single newline at the end of the string) This is now optional
 
946
            (callers can pass None). It is left in its location for backwards
 
947
            compatibility. It should ''.join(lines) must == line_bytes
 
948
        :param line_bytes: A single string containing the content
 
949
 
 
950
        We pass both lines and line_bytes because different routes bring the
 
951
        values to this function. And for memory efficiency, we don't want to
 
952
        have to split/join on-demand.
920
953
        """
921
954
        # first thing, if the content is something we don't need to store, find
922
955
        # that out.
923
 
        line_bytes = ''.join(lines)
924
956
        digest = sha_string(line_bytes)
925
957
        if nostore_sha == digest:
926
958
            raise errors.ExistingContent
947
979
 
948
980
        text_length = len(line_bytes)
949
981
        options = []
950
 
        if lines:
951
 
            if lines[-1][-1] != '\n':
952
 
                # copy the contents of lines.
 
982
        no_eol = False
 
983
        # Note: line_bytes is not modified to add a newline, that is tracked
 
984
        #       via the no_eol flag. 'lines' *is* modified, because that is the
 
985
        #       general values needed by the Content code.
 
986
        if line_bytes and line_bytes[-1] != '\n':
 
987
            options.append('no-eol')
 
988
            no_eol = True
 
989
            # Copy the existing list, or create a new one
 
990
            if lines is None:
 
991
                lines = osutils.split_lines(line_bytes)
 
992
            else:
953
993
                lines = lines[:]
954
 
                options.append('no-eol')
955
 
                lines[-1] = lines[-1] + '\n'
956
 
                line_bytes += '\n'
 
994
            # Replace the last line with one that ends in a final newline
 
995
            lines[-1] = lines[-1] + '\n'
 
996
        if lines is None:
 
997
            lines = osutils.split_lines(line_bytes)
957
998
 
958
999
        for element in key[:-1]:
959
 
            if type(element) != str:
 
1000
            if type(element) is not str:
960
1001
                raise TypeError("key contains non-strings: %r" % (key,))
961
1002
        if key[-1] is None:
962
1003
            key = key[:-1] + ('sha1:' + digest,)
963
 
        elif type(key[-1]) != str:
 
1004
        elif type(key[-1]) is not str:
964
1005
                raise TypeError("key contains non-strings: %r" % (key,))
965
1006
        # Knit hunks are still last-element only
966
1007
        version_id = key[-1]
967
1008
        content = self._factory.make(lines, version_id)
968
 
        if 'no-eol' in options:
 
1009
        if no_eol:
969
1010
            # Hint to the content object that its text() call should strip the
970
1011
            # EOL.
971
1012
            content._should_strip_eol = True
986
1027
            if self._factory.__class__ is KnitPlainFactory:
987
1028
                # Use the already joined bytes saving iteration time in
988
1029
                # _record_to_data.
 
1030
                dense_lines = [line_bytes]
 
1031
                if no_eol:
 
1032
                    dense_lines.append('\n')
989
1033
                size, bytes = self._record_to_data(key, digest,
990
 
                    lines, [line_bytes])
 
1034
                    lines, dense_lines)
991
1035
            else:
992
1036
                # get mixed annotation + content and feed it into the
993
1037
                # serialiser.
1005
1049
        """See VersionedFiles.annotate."""
1006
1050
        return self._factory.annotate(self, key)
1007
1051
 
1008
 
    def check(self, progress_bar=None):
 
1052
    def get_annotator(self):
 
1053
        return _KnitAnnotator(self)
 
1054
 
 
1055
    def check(self, progress_bar=None, keys=None):
1009
1056
        """See VersionedFiles.check()."""
 
1057
        if keys is None:
 
1058
            return self._logical_check()
 
1059
        else:
 
1060
            # At the moment, check does not extra work over get_record_stream
 
1061
            return self.get_record_stream(keys, 'unordered', True)
 
1062
 
 
1063
    def _logical_check(self):
1010
1064
        # This doesn't actually test extraction of everything, but that will
1011
1065
        # impact 'bzr check' substantially, and needs to be integrated with
1012
1066
        # care. However, it does check for the obvious problem of a delta with
1020
1074
                    raise errors.KnitCorrupt(self,
1021
1075
                        "Missing basis parent %s for %s" % (
1022
1076
                        compression_parent, key))
1023
 
        for fallback_vfs in self._fallback_vfs:
 
1077
        for fallback_vfs in self._immediate_fallback_vfs:
1024
1078
            fallback_vfs.check()
1025
1079
 
1026
1080
    def _check_add(self, key, lines, random_id, check_content):
1104
1158
 
1105
1159
        A dict of key to (record_details, index_memo, next, parents) is
1106
1160
        returned.
1107
 
        method is the way referenced data should be applied.
1108
 
        index_memo is the handle to pass to the data access to actually get the
1109
 
            data
1110
 
        next is the build-parent of the version, or None for fulltexts.
1111
 
        parents is the version_ids of the parents of this version
1112
 
 
1113
 
        :param allow_missing: If True do not raise an error on a missing component,
1114
 
            just ignore it.
 
1161
 
 
1162
        * method is the way referenced data should be applied.
 
1163
        * index_memo is the handle to pass to the data access to actually get
 
1164
          the data
 
1165
        * next is the build-parent of the version, or None for fulltexts.
 
1166
        * parents is the version_ids of the parents of this version
 
1167
 
 
1168
        :param allow_missing: If True do not raise an error on a missing
 
1169
            component, just ignore it.
1115
1170
        """
1116
1171
        component_data = {}
1117
1172
        pending_components = keys
1163
1218
            and so on.
1164
1219
        """
1165
1220
        result = {}
1166
 
        sources = [self._index] + self._fallback_vfs
 
1221
        sources = [self._index] + self._immediate_fallback_vfs
1167
1222
        source_results = []
1168
1223
        missing = set(keys)
1169
1224
        for source in sources:
1179
1234
        """Produce a dictionary of knit records.
1180
1235
 
1181
1236
        :return: {key:(record, record_details, digest, next)}
1182
 
            record
1183
 
                data returned from read_records (a KnitContentobject)
1184
 
            record_details
1185
 
                opaque information to pass to parse_record
1186
 
            digest
1187
 
                SHA1 digest of the full text after all steps are done
1188
 
            next
1189
 
                build-parent of the version, i.e. the leftmost ancestor.
 
1237
 
 
1238
            * record: data returned from read_records (a KnitContentobject)
 
1239
            * record_details: opaque information to pass to parse_record
 
1240
            * digest: SHA1 digest of the full text after all steps are done
 
1241
            * next: build-parent of the version, i.e. the leftmost ancestor.
1190
1242
                Will be None if the record is not a delta.
 
1243
 
1191
1244
        :param keys: The keys to build a map for
1192
1245
        :param allow_missing: If some records are missing, rather than
1193
1246
            error, just return the data that could be generated.
1449
1502
                                                                non_local_keys,
1450
1503
                                                                positions):
1451
1504
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1452
 
                                                   global_map)
 
1505
                                                   global_map,
 
1506
                                                   ordering=ordering)
1453
1507
                for record in generator.get_record_stream():
1454
1508
                    yield record
1455
1509
        else:
1457
1511
                if source is parent_maps[0]:
1458
1512
                    # this KnitVersionedFiles
1459
1513
                    records = [(key, positions[key][1]) for key in keys]
1460
 
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
 
1514
                    for key, raw_data in self._read_records_iter_unchecked(records):
1461
1515
                        (record_details, index_memo, _) = positions[key]
1462
1516
                        yield KnitContentFactory(key, global_map[key],
1463
 
                            record_details, sha1, raw_data, self._factory.annotated, None)
 
1517
                            record_details, None, raw_data, self._factory.annotated, None)
1464
1518
                else:
1465
 
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
 
1519
                    vf = self._immediate_fallback_vfs[parent_maps.index(source) - 1]
1466
1520
                    for record in vf.get_record_stream(keys, ordering,
1467
1521
                        include_delta_closure):
1468
1522
                        yield record
1478
1532
            # record entry 2 is the 'digest'.
1479
1533
            result[key] = details[2]
1480
1534
        missing.difference_update(set(result))
1481
 
        for source in self._fallback_vfs:
 
1535
        for source in self._immediate_fallback_vfs:
1482
1536
            if not missing:
1483
1537
                break
1484
1538
            new_result = source.get_sha1s(missing)
1535
1589
        # key = basis_parent, value = index entry to add
1536
1590
        buffered_index_entries = {}
1537
1591
        for record in stream:
 
1592
            kind = record.storage_kind
 
1593
            if kind.startswith('knit-') and kind.endswith('-gz'):
 
1594
                # Check that the ID in the header of the raw knit bytes matches
 
1595
                # the record metadata.
 
1596
                raw_data = record._raw_record
 
1597
                df, rec = self._parse_record_header(record.key, raw_data)
 
1598
                df.close()
1538
1599
            buffered = False
1539
1600
            parents = record.parents
1540
1601
            if record.storage_kind in delta_types:
1548
1609
                raise RevisionNotPresent([record.key], self)
1549
1610
            elif ((record.storage_kind in knit_types)
1550
1611
                  and (compression_parent is None
1551
 
                       or not self._fallback_vfs
 
1612
                       or not self._immediate_fallback_vfs
1552
1613
                       or self._index.has_key(compression_parent)
1553
1614
                       or not self.has_key(compression_parent))):
1554
1615
                # we can insert the knit record literally if either it has no
1642
1703
            # There were index entries buffered at the end of the stream,
1643
1704
            # So these need to be added (if the index supports holding such
1644
1705
            # entries for later insertion)
 
1706
            all_entries = []
1645
1707
            for key in buffered_index_entries:
1646
1708
                index_entries = buffered_index_entries[key]
1647
 
                self._index.add_records(index_entries,
1648
 
                    missing_compression_parents=True)
 
1709
                all_entries.extend(index_entries)
 
1710
            self._index.add_records(
 
1711
                all_entries, missing_compression_parents=True)
1649
1712
 
1650
1713
    def get_missing_compression_parent_keys(self):
1651
1714
        """Return an iterable of keys of missing compression parents.
1684
1747
        :return: An iterator over (line, key).
1685
1748
        """
1686
1749
        if pb is None:
1687
 
            pb = progress.DummyProgress()
 
1750
            pb = ui.ui_factory.nested_progress_bar()
1688
1751
        keys = set(keys)
1689
1752
        total = len(keys)
1690
1753
        done = False
1700
1763
                        key_records.append((key, details[0]))
1701
1764
                records_iter = enumerate(self._read_records_iter(key_records))
1702
1765
                for (key_idx, (key, data, sha_value)) in records_iter:
1703
 
                    pb.update('Walking content', key_idx, total)
 
1766
                    pb.update(gettext('Walking content'), key_idx, total)
1704
1767
                    compression_parent = build_details[key][1]
1705
1768
                    if compression_parent is None:
1706
1769
                        # fulltext
1724
1787
        # vfs, and hope to find them there.  Note that if the keys are found
1725
1788
        # but had no changes or no content, the fallback may not return
1726
1789
        # anything.
1727
 
        if keys and not self._fallback_vfs:
 
1790
        if keys and not self._immediate_fallback_vfs:
1728
1791
            # XXX: strictly the second parameter is meant to be the file id
1729
1792
            # but it's not easily accessible here.
1730
1793
            raise RevisionNotPresent(keys, repr(self))
1731
 
        for source in self._fallback_vfs:
 
1794
        for source in self._immediate_fallback_vfs:
1732
1795
            if not keys:
1733
1796
                break
1734
1797
            source_keys = set()
1736
1799
                source_keys.add(key)
1737
1800
                yield line, key
1738
1801
            keys.difference_update(source_keys)
1739
 
        pb.update('Walking content', total, total)
 
1802
        pb.update(gettext('Walking content'), total, total)
1740
1803
 
1741
1804
    def _make_line_delta(self, delta_seq, new_content):
1742
1805
        """Generate a line delta from delta_seq and new_content."""
1807
1870
        :return: the header and the decompressor stream.
1808
1871
                 as (stream, header_record)
1809
1872
        """
1810
 
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
1873
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
1811
1874
        try:
1812
1875
            # Current serialise
1813
1876
            rec = self._check_header(key, df.readline())
1822
1885
        # 4168 calls in 2880 217 internal
1823
1886
        # 4168 calls to _parse_record_header in 2121
1824
1887
        # 4168 calls to readlines in 330
1825
 
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(data))
 
1888
        df = gzip.GzipFile(mode='rb', fileobj=StringIO(data))
1826
1889
        try:
1827
1890
            record_contents = df.readlines()
1828
1891
        except Exception, e:
1850
1913
        The result will be returned in whatever is the fastest to read.
1851
1914
        Not by the order requested. Also, multiple requests for the same
1852
1915
        record will only yield 1 response.
 
1916
 
1853
1917
        :param records: A list of (key, access_memo) entries
1854
1918
        :return: Yields (key, contents, digest) in the order
1855
1919
                 read, not the order requested
1913
1977
        :param key: The key of the record. Currently keys are always serialised
1914
1978
            using just the trailing component.
1915
1979
        :param dense_lines: The bytes of lines but in a denser form. For
1916
 
            instance, if lines is a list of 1000 bytestrings each ending in \n,
1917
 
            dense_lines may be a list with one line in it, containing all the
1918
 
            1000's lines and their \n's. Using dense_lines if it is already
1919
 
            known is a win because the string join to create bytes in this
1920
 
            function spends less time resizing the final string.
 
1980
            instance, if lines is a list of 1000 bytestrings each ending in
 
1981
            \\n, dense_lines may be a list with one line in it, containing all
 
1982
            the 1000's lines and their \\n's. Using dense_lines if it is
 
1983
            already known is a win because the string join to create bytes in
 
1984
            this function spends less time resizing the final string.
1921
1985
        :return: (len, a StringIO instance with the raw data ready to read.)
1922
1986
        """
1923
 
        # Note: using a string copy here increases memory pressure with e.g.
1924
 
        # ISO's, but it is about 3 seconds faster on a 1.2Ghz intel machine
1925
 
        # when doing the initial commit of a mozilla tree. RBC 20070921
1926
 
        bytes = ''.join(chain(
1927
 
            ["version %s %d %s\n" % (key[-1],
1928
 
                                     len(lines),
1929
 
                                     digest)],
1930
 
            dense_lines or lines,
1931
 
            ["end %s\n" % key[-1]]))
1932
 
        if type(bytes) != str:
1933
 
            raise AssertionError(
1934
 
                'data must be plain bytes was %s' % type(bytes))
 
1987
        chunks = ["version %s %d %s\n" % (key[-1], len(lines), digest)]
 
1988
        chunks.extend(dense_lines or lines)
 
1989
        chunks.append("end %s\n" % key[-1])
 
1990
        for chunk in chunks:
 
1991
            if type(chunk) is not str:
 
1992
                raise AssertionError(
 
1993
                    'data must be plain bytes was %s' % type(chunk))
1935
1994
        if lines and lines[-1][-1] != '\n':
1936
1995
            raise ValueError('corrupt lines value %r' % lines)
1937
 
        compressed_bytes = tuned_gzip.bytes_to_gzip(bytes)
 
1996
        compressed_bytes = tuned_gzip.chunks_to_gzip(chunks)
1938
1997
        return len(compressed_bytes), compressed_bytes
1939
1998
 
1940
1999
    def _split_header(self, line):
1948
2007
        """See VersionedFiles.keys."""
1949
2008
        if 'evil' in debug.debug_flags:
1950
2009
            trace.mutter_callsite(2, "keys scales with size of history")
1951
 
        sources = [self._index] + self._fallback_vfs
 
2010
        sources = [self._index] + self._immediate_fallback_vfs
1952
2011
        result = set()
1953
2012
        for source in sources:
1954
2013
            result.update(source.keys())
1958
2017
class _ContentMapGenerator(object):
1959
2018
    """Generate texts or expose raw deltas for a set of texts."""
1960
2019
 
 
2020
    def __init__(self, ordering='unordered'):
 
2021
        self._ordering = ordering
 
2022
 
1961
2023
    def _get_content(self, key):
1962
2024
        """Get the content object for key."""
1963
2025
        # Note that _get_content is only called when the _ContentMapGenerator
1991
2053
 
1992
2054
        missing_keys = set(nonlocal_keys)
1993
2055
        # Read from remote versioned file instances and provide to our caller.
1994
 
        for source in self.vf._fallback_vfs:
 
2056
        for source in self.vf._immediate_fallback_vfs:
1995
2057
            if not missing_keys:
1996
2058
                break
1997
2059
            # Loop over fallback repositories asking them for texts - ignore
1998
2060
            # any missing from a particular fallback.
1999
2061
            for record in source.get_record_stream(missing_keys,
2000
 
                'unordered', True):
 
2062
                self._ordering, True):
2001
2063
                if record.storage_kind == 'absent':
2002
2064
                    # Not in thie particular stream, may be in one of the
2003
2065
                    # other fallback vfs objects.
2005
2067
                missing_keys.remove(record.key)
2006
2068
                yield record
2007
2069
 
2008
 
        self._raw_record_map = self.vf._get_record_map_unparsed(self.keys,
2009
 
            allow_missing=True)
 
2070
        if self._raw_record_map is None:
 
2071
            raise AssertionError('_raw_record_map should have been filled')
2010
2072
        first = True
2011
2073
        for key in self.keys:
2012
2074
            if key in self.nonlocal_keys:
2135
2197
    """Content map generator reading from a VersionedFiles object."""
2136
2198
 
2137
2199
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2138
 
        global_map=None, raw_record_map=None):
 
2200
        global_map=None, raw_record_map=None, ordering='unordered'):
2139
2201
        """Create a _ContentMapGenerator.
2140
2202
 
2141
2203
        :param versioned_files: The versioned files that the texts are being
2149
2211
        :param raw_record_map: A unparsed raw record map to use for answering
2150
2212
            contents.
2151
2213
        """
 
2214
        _ContentMapGenerator.__init__(self, ordering=ordering)
2152
2215
        # The vf to source data from
2153
2216
        self.vf = versioned_files
2154
2217
        # The keys desired
2298
2361
    FLAGS is a comma separated list of flags about the record. Values include
2299
2362
        no-eol, line-delta, fulltext.
2300
2363
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2301
 
        that the the compressed data starts at.
 
2364
        that the compressed data starts at.
2302
2365
    LENGTH is the ascii representation of the length of the data file.
2303
2366
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2304
2367
        REVISION_ID.
2375
2438
                    line = "\n%s %s %s %s %s :" % (
2376
2439
                        key[-1], ','.join(options), pos, size,
2377
2440
                        self._dictionary_compress(parents))
2378
 
                    if type(line) != str:
 
2441
                    if type(line) is not str:
2379
2442
                        raise AssertionError(
2380
2443
                            'data must be utf8 was %s' % type(line))
2381
2444
                    lines.append(line)
2513
2576
        except KeyError:
2514
2577
            raise RevisionNotPresent(key, self)
2515
2578
 
 
2579
    def find_ancestry(self, keys):
 
2580
        """See CombinedGraphIndex.find_ancestry()"""
 
2581
        prefixes = set(key[:-1] for key in keys)
 
2582
        self._load_prefixes(prefixes)
 
2583
        result = {}
 
2584
        parent_map = {}
 
2585
        missing_keys = set()
 
2586
        pending_keys = list(keys)
 
2587
        # This assumes that keys will not reference parents in a different
 
2588
        # prefix, which is accurate so far.
 
2589
        while pending_keys:
 
2590
            key = pending_keys.pop()
 
2591
            if key in parent_map:
 
2592
                continue
 
2593
            prefix = key[:-1]
 
2594
            try:
 
2595
                suffix_parents = self._kndx_cache[prefix][0][key[-1]][4]
 
2596
            except KeyError:
 
2597
                missing_keys.add(key)
 
2598
            else:
 
2599
                parent_keys = tuple([prefix + (suffix,)
 
2600
                                     for suffix in suffix_parents])
 
2601
                parent_map[key] = parent_keys
 
2602
                pending_keys.extend([p for p in parent_keys
 
2603
                                        if p not in parent_map])
 
2604
        return parent_map, missing_keys
 
2605
 
2516
2606
    def get_parent_map(self, keys):
2517
2607
        """Get a map of the parents of keys.
2518
2608
 
2570
2660
        result = set()
2571
2661
        # Identify all key prefixes.
2572
2662
        # XXX: A bit hacky, needs polish.
2573
 
        if type(self._mapper) == ConstantMapper:
 
2663
        if type(self._mapper) is ConstantMapper:
2574
2664
            prefixes = [()]
2575
2665
        else:
2576
2666
            relpaths = set()
2608
2698
                    del self._history
2609
2699
                except NoSuchFile:
2610
2700
                    self._kndx_cache[prefix] = ({}, [])
2611
 
                    if type(self._mapper) == ConstantMapper:
 
2701
                    if type(self._mapper) is ConstantMapper:
2612
2702
                        # preserve behaviour for revisions.kndx etc.
2613
2703
                        self._init_index(path)
2614
2704
                    del self._cache
2688
2778
        return key[:-1], key[-1]
2689
2779
 
2690
2780
 
2691
 
class _KeyRefs(object):
2692
 
 
2693
 
    def __init__(self):
2694
 
        # dict mapping 'key' to 'set of keys referring to that key'
2695
 
        self.refs = {}
2696
 
 
2697
 
    def add_references(self, key, refs):
2698
 
        # Record the new references
2699
 
        for referenced in refs:
2700
 
            try:
2701
 
                needed_by = self.refs[referenced]
2702
 
            except KeyError:
2703
 
                needed_by = self.refs[referenced] = set()
2704
 
            needed_by.add(key)
2705
 
        # Discard references satisfied by the new key
2706
 
        self.add_key(key)
2707
 
 
2708
 
    def get_unsatisfied_refs(self):
2709
 
        return self.refs.iterkeys()
2710
 
 
2711
 
    def add_key(self, key):
2712
 
        try:
2713
 
            del self.refs[key]
2714
 
        except KeyError:
2715
 
            # No keys depended on this key.  That's ok.
2716
 
            pass
2717
 
 
2718
 
    def add_keys(self, keys):
2719
 
        for key in keys:
2720
 
            self.add_key(key)
2721
 
 
2722
 
    def get_referrers(self):
2723
 
        result = set()
2724
 
        for referrers in self.refs.itervalues():
2725
 
            result.update(referrers)
2726
 
        return result
2727
 
 
2728
 
 
2729
2781
class _KnitGraphIndex(object):
2730
2782
    """A KnitVersionedFiles index layered on GraphIndex."""
2731
2783
 
2828
2880
        if not random_id:
2829
2881
            present_nodes = self._get_entries(keys)
2830
2882
            for (index, key, value, node_refs) in present_nodes:
 
2883
                parents = node_refs[:1]
 
2884
                # Sometimes these are passed as a list rather than a tuple
 
2885
                passed = static_tuple.as_tuples(keys[key])
 
2886
                passed_parents = passed[1][:1]
2831
2887
                if (value[0] != keys[key][0][0] or
2832
 
                    node_refs[:1] != keys[key][1][:1]):
 
2888
                    parents != passed_parents):
 
2889
                    node_refs = static_tuple.as_tuples(node_refs)
2833
2890
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2834
 
                        ": %s %s" % ((value, node_refs), keys[key]))
 
2891
                        ": %s %s" % ((value, node_refs), passed))
2835
2892
                del keys[key]
2836
2893
        result = []
2837
2894
        if self._parents:
2885
2942
        # If updating this, you should also update
2886
2943
        # groupcompress._GCGraphIndex.get_missing_parents
2887
2944
        # We may have false positives, so filter those out.
2888
 
        self._key_dependencies.add_keys(
 
2945
        self._key_dependencies.satisfy_refs_for_keys(
2889
2946
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2890
2947
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
2891
2948
 
3002
3059
            options.append('no-eol')
3003
3060
        return options
3004
3061
 
 
3062
    def find_ancestry(self, keys):
 
3063
        """See CombinedGraphIndex.find_ancestry()"""
 
3064
        return self._graph_index.find_ancestry(keys, 0)
 
3065
 
3005
3066
    def get_parent_map(self, keys):
3006
3067
        """Get a map of the parents of keys.
3007
3068
 
3094
3155
            opaque index memo. For _KnitKeyAccess the memo is (key, pos,
3095
3156
            length), where the key is the record key.
3096
3157
        """
3097
 
        if type(raw_data) != str:
 
3158
        if type(raw_data) is not str:
3098
3159
            raise AssertionError(
3099
3160
                'data must be plain bytes was %s' % type(raw_data))
3100
3161
        result = []
3151
3212
                yield data
3152
3213
 
3153
3214
 
3154
 
class _DirectPackAccess(object):
3155
 
    """Access to data in one or more packs with less translation."""
3156
 
 
3157
 
    def __init__(self, index_to_packs, reload_func=None, flush_func=None):
3158
 
        """Create a _DirectPackAccess object.
3159
 
 
3160
 
        :param index_to_packs: A dict mapping index objects to the transport
3161
 
            and file names for obtaining data.
3162
 
        :param reload_func: A function to call if we determine that the pack
3163
 
            files have moved and we need to reload our caches. See
3164
 
            bzrlib.repo_fmt.pack_repo.AggregateIndex for more details.
3165
 
        """
3166
 
        self._container_writer = None
3167
 
        self._write_index = None
3168
 
        self._indices = index_to_packs
3169
 
        self._reload_func = reload_func
3170
 
        self._flush_func = flush_func
3171
 
 
3172
 
    def add_raw_records(self, key_sizes, raw_data):
3173
 
        """Add raw knit bytes to a storage area.
3174
 
 
3175
 
        The data is spooled to the container writer in one bytes-record per
3176
 
        raw data item.
3177
 
 
3178
 
        :param sizes: An iterable of tuples containing the key and size of each
3179
 
            raw data segment.
3180
 
        :param raw_data: A bytestring containing the data.
3181
 
        :return: A list of memos to retrieve the record later. Each memo is an
3182
 
            opaque index memo. For _DirectPackAccess the memo is (index, pos,
3183
 
            length), where the index field is the write_index object supplied
3184
 
            to the PackAccess object.
3185
 
        """
3186
 
        if type(raw_data) != str:
3187
 
            raise AssertionError(
3188
 
                'data must be plain bytes was %s' % type(raw_data))
3189
 
        result = []
3190
 
        offset = 0
3191
 
        for key, size in key_sizes:
3192
 
            p_offset, p_length = self._container_writer.add_bytes_record(
3193
 
                raw_data[offset:offset+size], [])
3194
 
            offset += size
3195
 
            result.append((self._write_index, p_offset, p_length))
3196
 
        return result
3197
 
 
3198
 
    def flush(self):
3199
 
        """Flush pending writes on this access object.
3200
 
 
3201
 
        This will flush any buffered writes to a NewPack.
3202
 
        """
3203
 
        if self._flush_func is not None:
3204
 
            self._flush_func()
3205
 
            
3206
 
    def get_raw_records(self, memos_for_retrieval):
3207
 
        """Get the raw bytes for a records.
3208
 
 
3209
 
        :param memos_for_retrieval: An iterable containing the (index, pos,
3210
 
            length) memo for retrieving the bytes. The Pack access method
3211
 
            looks up the pack to use for a given record in its index_to_pack
3212
 
            map.
3213
 
        :return: An iterator over the bytes of the records.
3214
 
        """
3215
 
        # first pass, group into same-index requests
3216
 
        request_lists = []
3217
 
        current_index = None
3218
 
        for (index, offset, length) in memos_for_retrieval:
3219
 
            if current_index == index:
3220
 
                current_list.append((offset, length))
3221
 
            else:
3222
 
                if current_index is not None:
3223
 
                    request_lists.append((current_index, current_list))
3224
 
                current_index = index
3225
 
                current_list = [(offset, length)]
3226
 
        # handle the last entry
3227
 
        if current_index is not None:
3228
 
            request_lists.append((current_index, current_list))
3229
 
        for index, offsets in request_lists:
3230
 
            try:
3231
 
                transport, path = self._indices[index]
3232
 
            except KeyError:
3233
 
                # A KeyError here indicates that someone has triggered an index
3234
 
                # reload, and this index has gone missing, we need to start
3235
 
                # over.
3236
 
                if self._reload_func is None:
3237
 
                    # If we don't have a _reload_func there is nothing that can
3238
 
                    # be done
3239
 
                    raise
3240
 
                raise errors.RetryWithNewPacks(index,
3241
 
                                               reload_occurred=True,
3242
 
                                               exc_info=sys.exc_info())
3243
 
            try:
3244
 
                reader = pack.make_readv_reader(transport, path, offsets)
3245
 
                for names, read_func in reader.iter_records():
3246
 
                    yield read_func(None)
3247
 
            except errors.NoSuchFile:
3248
 
                # A NoSuchFile error indicates that a pack file has gone
3249
 
                # missing on disk, we need to trigger a reload, and start over.
3250
 
                if self._reload_func is None:
3251
 
                    raise
3252
 
                raise errors.RetryWithNewPacks(transport.abspath(path),
3253
 
                                               reload_occurred=False,
3254
 
                                               exc_info=sys.exc_info())
3255
 
 
3256
 
    def set_writer(self, writer, index, transport_packname):
3257
 
        """Set a writer to use for adding data."""
3258
 
        if index is not None:
3259
 
            self._indices[index] = transport_packname
3260
 
        self._container_writer = writer
3261
 
        self._write_index = index
3262
 
 
3263
 
    def reload_or_raise(self, retry_exc):
3264
 
        """Try calling the reload function, or re-raise the original exception.
3265
 
 
3266
 
        This should be called after _DirectPackAccess raises a
3267
 
        RetryWithNewPacks exception. This function will handle the common logic
3268
 
        of determining when the error is fatal versus being temporary.
3269
 
        It will also make sure that the original exception is raised, rather
3270
 
        than the RetryWithNewPacks exception.
3271
 
 
3272
 
        If this function returns, then the calling function should retry
3273
 
        whatever operation was being performed. Otherwise an exception will
3274
 
        be raised.
3275
 
 
3276
 
        :param retry_exc: A RetryWithNewPacks exception.
3277
 
        """
3278
 
        is_error = False
3279
 
        if self._reload_func is None:
3280
 
            is_error = True
3281
 
        elif not self._reload_func():
3282
 
            # The reload claimed that nothing changed
3283
 
            if not retry_exc.reload_occurred:
3284
 
                # If there wasn't an earlier reload, then we really were
3285
 
                # expecting to find changes. We didn't find them, so this is a
3286
 
                # hard error
3287
 
                is_error = True
3288
 
        if is_error:
3289
 
            exc_class, exc_value, exc_traceback = retry_exc.exc_info
3290
 
            raise exc_class, exc_value, exc_traceback
3291
 
 
3292
 
 
3293
 
# Deprecated, use PatienceSequenceMatcher instead
3294
 
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
3295
 
 
3296
 
 
3297
3215
def annotate_knit(knit, revision_id):
3298
3216
    """Annotate a knit with no cached annotations.
3299
3217
 
3302
3220
    recommended.
3303
3221
    """
3304
3222
    annotator = _KnitAnnotator(knit)
3305
 
    return iter(annotator.annotate(revision_id))
3306
 
 
3307
 
 
3308
 
class _KnitAnnotator(object):
 
3223
    return iter(annotator.annotate_flat(revision_id))
 
3224
 
 
3225
 
 
3226
class _KnitAnnotator(annotate.Annotator):
3309
3227
    """Build up the annotations for a text."""
3310
3228
 
3311
 
    def __init__(self, knit):
3312
 
        self._knit = knit
3313
 
 
3314
 
        # Content objects, differs from fulltexts because of how final newlines
3315
 
        # are treated by knits. the content objects here will always have a
3316
 
        # final newline
3317
 
        self._fulltext_contents = {}
3318
 
 
3319
 
        # Annotated lines of specific revisions
3320
 
        self._annotated_lines = {}
3321
 
 
3322
 
        # Track the raw data for nodes that we could not process yet.
3323
 
        # This maps the revision_id of the base to a list of children that will
3324
 
        # annotated from it.
3325
 
        self._pending_children = {}
3326
 
 
3327
 
        # Nodes which cannot be extracted
3328
 
        self._ghosts = set()
3329
 
 
3330
 
        # Track how many children this node has, so we know if we need to keep
3331
 
        # it
3332
 
        self._annotate_children = {}
3333
 
        self._compression_children = {}
 
3229
    def __init__(self, vf):
 
3230
        annotate.Annotator.__init__(self, vf)
 
3231
 
 
3232
        # TODO: handle Nodes which cannot be extracted
 
3233
        # self._ghosts = set()
 
3234
 
 
3235
        # Map from (key, parent_key) => matching_blocks, should be 'use once'
 
3236
        self._matching_blocks = {}
 
3237
 
 
3238
        # KnitContent objects
 
3239
        self._content_objects = {}
 
3240
        # The number of children that depend on this fulltext content object
 
3241
        self._num_compression_children = {}
 
3242
        # Delta records that need their compression parent before they can be
 
3243
        # expanded
 
3244
        self._pending_deltas = {}
 
3245
        # Fulltext records that are waiting for their parents fulltexts before
 
3246
        # they can be yielded for annotation
 
3247
        self._pending_annotation = {}
3334
3248
 
3335
3249
        self._all_build_details = {}
3336
 
        # The children => parent revision_id graph
3337
 
        self._revision_id_graph = {}
3338
 
 
3339
 
        self._heads_provider = None
3340
 
 
3341
 
        self._nodes_to_keep_annotations = set()
3342
 
        self._generations_until_keep = 100
3343
 
 
3344
 
    def set_generations_until_keep(self, value):
3345
 
        """Set the number of generations before caching a node.
3346
 
 
3347
 
        Setting this to -1 will cache every merge node, setting this higher
3348
 
        will cache fewer nodes.
3349
 
        """
3350
 
        self._generations_until_keep = value
3351
 
 
3352
 
    def _add_fulltext_content(self, revision_id, content_obj):
3353
 
        self._fulltext_contents[revision_id] = content_obj
3354
 
        # TODO: jam 20080305 It might be good to check the sha1digest here
3355
 
        return content_obj.text()
3356
 
 
3357
 
    def _check_parents(self, child, nodes_to_annotate):
3358
 
        """Check if all parents have been processed.
3359
 
 
3360
 
        :param child: A tuple of (rev_id, parents, raw_content)
3361
 
        :param nodes_to_annotate: If child is ready, add it to
3362
 
            nodes_to_annotate, otherwise put it back in self._pending_children
3363
 
        """
3364
 
        for parent_id in child[1]:
3365
 
            if (parent_id not in self._annotated_lines):
3366
 
                # This parent is present, but another parent is missing
3367
 
                self._pending_children.setdefault(parent_id,
3368
 
                                                  []).append(child)
3369
 
                break
3370
 
        else:
3371
 
            # This one is ready to be processed
3372
 
            nodes_to_annotate.append(child)
3373
 
 
3374
 
    def _add_annotation(self, revision_id, fulltext, parent_ids,
3375
 
                        left_matching_blocks=None):
3376
 
        """Add an annotation entry.
3377
 
 
3378
 
        All parents should already have been annotated.
3379
 
        :return: A list of children that now have their parents satisfied.
3380
 
        """
3381
 
        a = self._annotated_lines
3382
 
        annotated_parent_lines = [a[p] for p in parent_ids]
3383
 
        annotated_lines = list(annotate.reannotate(annotated_parent_lines,
3384
 
            fulltext, revision_id, left_matching_blocks,
3385
 
            heads_provider=self._get_heads_provider()))
3386
 
        self._annotated_lines[revision_id] = annotated_lines
3387
 
        for p in parent_ids:
3388
 
            ann_children = self._annotate_children[p]
3389
 
            ann_children.remove(revision_id)
3390
 
            if (not ann_children
3391
 
                and p not in self._nodes_to_keep_annotations):
3392
 
                del self._annotated_lines[p]
3393
 
                del self._all_build_details[p]
3394
 
                if p in self._fulltext_contents:
3395
 
                    del self._fulltext_contents[p]
3396
 
        # Now that we've added this one, see if there are any pending
3397
 
        # deltas to be done, certainly this parent is finished
3398
 
        nodes_to_annotate = []
3399
 
        for child in self._pending_children.pop(revision_id, []):
3400
 
            self._check_parents(child, nodes_to_annotate)
3401
 
        return nodes_to_annotate
3402
3250
 
3403
3251
    def _get_build_graph(self, key):
3404
3252
        """Get the graphs for building texts and annotations.
3412
3260
            passing to read_records_iter to start reading in the raw data from
3413
3261
            the pack file.
3414
3262
        """
3415
 
        if key in self._annotated_lines:
3416
 
            # Nothing to do
3417
 
            return []
3418
3263
        pending = set([key])
3419
3264
        records = []
3420
 
        generation = 0
3421
 
        kept_generation = 0
 
3265
        ann_keys = set()
 
3266
        self._num_needed_children[key] = 1
3422
3267
        while pending:
3423
3268
            # get all pending nodes
3424
 
            generation += 1
3425
3269
            this_iteration = pending
3426
 
            build_details = self._knit._index.get_build_details(this_iteration)
 
3270
            build_details = self._vf._index.get_build_details(this_iteration)
3427
3271
            self._all_build_details.update(build_details)
3428
 
            # new_nodes = self._knit._index._get_entries(this_iteration)
 
3272
            # new_nodes = self._vf._index._get_entries(this_iteration)
3429
3273
            pending = set()
3430
3274
            for key, details in build_details.iteritems():
3431
 
                (index_memo, compression_parent, parents,
 
3275
                (index_memo, compression_parent, parent_keys,
3432
3276
                 record_details) = details
3433
 
                self._revision_id_graph[key] = parents
 
3277
                self._parent_map[key] = parent_keys
 
3278
                self._heads_provider = None
3434
3279
                records.append((key, index_memo))
3435
3280
                # Do we actually need to check _annotated_lines?
3436
 
                pending.update(p for p in parents
3437
 
                                 if p not in self._all_build_details)
 
3281
                pending.update([p for p in parent_keys
 
3282
                                   if p not in self._all_build_details])
 
3283
                if parent_keys:
 
3284
                    for parent_key in parent_keys:
 
3285
                        if parent_key in self._num_needed_children:
 
3286
                            self._num_needed_children[parent_key] += 1
 
3287
                        else:
 
3288
                            self._num_needed_children[parent_key] = 1
3438
3289
                if compression_parent:
3439
 
                    self._compression_children.setdefault(compression_parent,
3440
 
                        []).append(key)
3441
 
                if parents:
3442
 
                    for parent in parents:
3443
 
                        self._annotate_children.setdefault(parent,
3444
 
                            []).append(key)
3445
 
                    num_gens = generation - kept_generation
3446
 
                    if ((num_gens >= self._generations_until_keep)
3447
 
                        and len(parents) > 1):
3448
 
                        kept_generation = generation
3449
 
                        self._nodes_to_keep_annotations.add(key)
 
3290
                    if compression_parent in self._num_compression_children:
 
3291
                        self._num_compression_children[compression_parent] += 1
 
3292
                    else:
 
3293
                        self._num_compression_children[compression_parent] = 1
3450
3294
 
3451
3295
            missing_versions = this_iteration.difference(build_details.keys())
3452
 
            self._ghosts.update(missing_versions)
3453
 
            for missing_version in missing_versions:
3454
 
                # add a key, no parents
3455
 
                self._revision_id_graph[missing_version] = ()
3456
 
                pending.discard(missing_version) # don't look for it
3457
 
        if self._ghosts.intersection(self._compression_children):
3458
 
            raise KnitCorrupt(
3459
 
                "We cannot have nodes which have a ghost compression parent:\n"
3460
 
                "ghosts: %r\n"
3461
 
                "compression children: %r"
3462
 
                % (self._ghosts, self._compression_children))
3463
 
        # Cleanout anything that depends on a ghost so that we don't wait for
3464
 
        # the ghost to show up
3465
 
        for node in self._ghosts:
3466
 
            if node in self._annotate_children:
3467
 
                # We won't be building this node
3468
 
                del self._annotate_children[node]
 
3296
            if missing_versions:
 
3297
                for key in missing_versions:
 
3298
                    if key in self._parent_map and key in self._text_cache:
 
3299
                        # We already have this text ready, we just need to
 
3300
                        # yield it later so we get it annotated
 
3301
                        ann_keys.add(key)
 
3302
                        parent_keys = self._parent_map[key]
 
3303
                        for parent_key in parent_keys:
 
3304
                            if parent_key in self._num_needed_children:
 
3305
                                self._num_needed_children[parent_key] += 1
 
3306
                            else:
 
3307
                                self._num_needed_children[parent_key] = 1
 
3308
                        pending.update([p for p in parent_keys
 
3309
                                           if p not in self._all_build_details])
 
3310
                    else:
 
3311
                        raise errors.RevisionNotPresent(key, self._vf)
3469
3312
        # Generally we will want to read the records in reverse order, because
3470
3313
        # we find the parent nodes after the children
3471
3314
        records.reverse()
3472
 
        return records
3473
 
 
3474
 
    def _annotate_records(self, records):
3475
 
        """Build the annotations for the listed records."""
 
3315
        return records, ann_keys
 
3316
 
 
3317
    def _get_needed_texts(self, key, pb=None):
 
3318
        # if True or len(self._vf._immediate_fallback_vfs) > 0:
 
3319
        if len(self._vf._immediate_fallback_vfs) > 0:
 
3320
            # If we have fallbacks, go to the generic path
 
3321
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
 
3322
                yield v
 
3323
            return
 
3324
        while True:
 
3325
            try:
 
3326
                records, ann_keys = self._get_build_graph(key)
 
3327
                for idx, (sub_key, text, num_lines) in enumerate(
 
3328
                                                self._extract_texts(records)):
 
3329
                    if pb is not None:
 
3330
                        pb.update(gettext('annotating'), idx, len(records))
 
3331
                    yield sub_key, text, num_lines
 
3332
                for sub_key in ann_keys:
 
3333
                    text = self._text_cache[sub_key]
 
3334
                    num_lines = len(text) # bad assumption
 
3335
                    yield sub_key, text, num_lines
 
3336
                return
 
3337
            except errors.RetryWithNewPacks, e:
 
3338
                self._vf._access.reload_or_raise(e)
 
3339
                # The cached build_details are no longer valid
 
3340
                self._all_build_details.clear()
 
3341
 
 
3342
    def _cache_delta_blocks(self, key, compression_parent, delta, lines):
 
3343
        parent_lines = self._text_cache[compression_parent]
 
3344
        blocks = list(KnitContent.get_line_delta_blocks(delta, parent_lines, lines))
 
3345
        self._matching_blocks[(key, compression_parent)] = blocks
 
3346
 
 
3347
    def _expand_record(self, key, parent_keys, compression_parent, record,
 
3348
                       record_details):
 
3349
        delta = None
 
3350
        if compression_parent:
 
3351
            if compression_parent not in self._content_objects:
 
3352
                # Waiting for the parent
 
3353
                self._pending_deltas.setdefault(compression_parent, []).append(
 
3354
                    (key, parent_keys, record, record_details))
 
3355
                return None
 
3356
            # We have the basis parent, so expand the delta
 
3357
            num = self._num_compression_children[compression_parent]
 
3358
            num -= 1
 
3359
            if num == 0:
 
3360
                base_content = self._content_objects.pop(compression_parent)
 
3361
                self._num_compression_children.pop(compression_parent)
 
3362
            else:
 
3363
                self._num_compression_children[compression_parent] = num
 
3364
                base_content = self._content_objects[compression_parent]
 
3365
            # It is tempting to want to copy_base_content=False for the last
 
3366
            # child object. However, whenever noeol=False,
 
3367
            # self._text_cache[parent_key] is content._lines. So mutating it
 
3368
            # gives very bad results.
 
3369
            # The alternative is to copy the lines into text cache, but then we
 
3370
            # are copying anyway, so just do it here.
 
3371
            content, delta = self._vf._factory.parse_record(
 
3372
                key, record, record_details, base_content,
 
3373
                copy_base_content=True)
 
3374
        else:
 
3375
            # Fulltext record
 
3376
            content, _ = self._vf._factory.parse_record(
 
3377
                key, record, record_details, None)
 
3378
        if self._num_compression_children.get(key, 0) > 0:
 
3379
            self._content_objects[key] = content
 
3380
        lines = content.text()
 
3381
        self._text_cache[key] = lines
 
3382
        if delta is not None:
 
3383
            self._cache_delta_blocks(key, compression_parent, delta, lines)
 
3384
        return lines
 
3385
 
 
3386
    def _get_parent_annotations_and_matches(self, key, text, parent_key):
 
3387
        """Get the list of annotations for the parent, and the matching lines.
 
3388
 
 
3389
        :param text: The opaque value given by _get_needed_texts
 
3390
        :param parent_key: The key for the parent text
 
3391
        :return: (parent_annotations, matching_blocks)
 
3392
            parent_annotations is a list as long as the number of lines in
 
3393
                parent
 
3394
            matching_blocks is a list of (parent_idx, text_idx, len) tuples
 
3395
                indicating which lines match between the two texts
 
3396
        """
 
3397
        block_key = (key, parent_key)
 
3398
        if block_key in self._matching_blocks:
 
3399
            blocks = self._matching_blocks.pop(block_key)
 
3400
            parent_annotations = self._annotations_cache[parent_key]
 
3401
            return parent_annotations, blocks
 
3402
        return annotate.Annotator._get_parent_annotations_and_matches(self,
 
3403
            key, text, parent_key)
 
3404
 
 
3405
    def _process_pending(self, key):
 
3406
        """The content for 'key' was just processed.
 
3407
 
 
3408
        Determine if there is any more pending work to be processed.
 
3409
        """
 
3410
        to_return = []
 
3411
        if key in self._pending_deltas:
 
3412
            compression_parent = key
 
3413
            children = self._pending_deltas.pop(key)
 
3414
            for child_key, parent_keys, record, record_details in children:
 
3415
                lines = self._expand_record(child_key, parent_keys,
 
3416
                                            compression_parent,
 
3417
                                            record, record_details)
 
3418
                if self._check_ready_for_annotations(child_key, parent_keys):
 
3419
                    to_return.append(child_key)
 
3420
        # Also check any children that are waiting for this parent to be
 
3421
        # annotation ready
 
3422
        if key in self._pending_annotation:
 
3423
            children = self._pending_annotation.pop(key)
 
3424
            to_return.extend([c for c, p_keys in children
 
3425
                              if self._check_ready_for_annotations(c, p_keys)])
 
3426
        return to_return
 
3427
 
 
3428
    def _check_ready_for_annotations(self, key, parent_keys):
 
3429
        """return true if this text is ready to be yielded.
 
3430
 
 
3431
        Otherwise, this will return False, and queue the text into
 
3432
        self._pending_annotation
 
3433
        """
 
3434
        for parent_key in parent_keys:
 
3435
            if parent_key not in self._annotations_cache:
 
3436
                # still waiting on at least one parent text, so queue it up
 
3437
                # Note that if there are multiple parents, we need to wait
 
3438
                # for all of them.
 
3439
                self._pending_annotation.setdefault(parent_key,
 
3440
                    []).append((key, parent_keys))
 
3441
                return False
 
3442
        return True
 
3443
 
 
3444
    def _extract_texts(self, records):
 
3445
        """Extract the various texts needed based on records"""
3476
3446
        # We iterate in the order read, rather than a strict order requested
3477
3447
        # However, process what we can, and put off to the side things that
3478
3448
        # still need parents, cleaning them up when those parents are
3479
3449
        # processed.
3480
 
        for (rev_id, record,
3481
 
             digest) in self._knit._read_records_iter(records):
3482
 
            if rev_id in self._annotated_lines:
 
3450
        # Basic data flow:
 
3451
        #   1) As 'records' are read, see if we can expand these records into
 
3452
        #      Content objects (and thus lines)
 
3453
        #   2) If a given line-delta is waiting on its compression parent, it
 
3454
        #      gets queued up into self._pending_deltas, otherwise we expand
 
3455
        #      it, and put it into self._text_cache and self._content_objects
 
3456
        #   3) If we expanded the text, we will then check to see if all
 
3457
        #      parents have also been processed. If so, this text gets yielded,
 
3458
        #      else this record gets set aside into pending_annotation
 
3459
        #   4) Further, if we expanded the text in (2), we will then check to
 
3460
        #      see if there are any children in self._pending_deltas waiting to
 
3461
        #      also be processed. If so, we go back to (2) for those
 
3462
        #   5) Further again, if we yielded the text, we can then check if that
 
3463
        #      'unlocks' any of the texts in pending_annotations, which should
 
3464
        #      then get yielded as well
 
3465
        # Note that both steps 4 and 5 are 'recursive' in that unlocking one
 
3466
        # compression child could unlock yet another, and yielding a fulltext
 
3467
        # will also 'unlock' the children that are waiting on that annotation.
 
3468
        # (Though also, unlocking 1 parent's fulltext, does not unlock a child
 
3469
        # if other parents are also waiting.)
 
3470
        # We want to yield content before expanding child content objects, so
 
3471
        # that we know when we can re-use the content lines, and the annotation
 
3472
        # code can know when it can stop caching fulltexts, as well.
 
3473
 
 
3474
        # Children that are missing their compression parent
 
3475
        pending_deltas = {}
 
3476
        for (key, record, digest) in self._vf._read_records_iter(records):
 
3477
            # ghosts?
 
3478
            details = self._all_build_details[key]
 
3479
            (_, compression_parent, parent_keys, record_details) = details
 
3480
            lines = self._expand_record(key, parent_keys, compression_parent,
 
3481
                                        record, record_details)
 
3482
            if lines is None:
 
3483
                # Pending delta should be queued up
3483
3484
                continue
3484
 
            parent_ids = self._revision_id_graph[rev_id]
3485
 
            parent_ids = [p for p in parent_ids if p not in self._ghosts]
3486
 
            details = self._all_build_details[rev_id]
3487
 
            (index_memo, compression_parent, parents,
3488
 
             record_details) = details
3489
 
            nodes_to_annotate = []
3490
 
            # TODO: Remove the punning between compression parents, and
3491
 
            #       parent_ids, we should be able to do this without assuming
3492
 
            #       the build order
3493
 
            if len(parent_ids) == 0:
3494
 
                # There are no parents for this node, so just add it
3495
 
                # TODO: This probably needs to be decoupled
3496
 
                fulltext_content, delta = self._knit._factory.parse_record(
3497
 
                    rev_id, record, record_details, None)
3498
 
                fulltext = self._add_fulltext_content(rev_id, fulltext_content)
3499
 
                nodes_to_annotate.extend(self._add_annotation(rev_id, fulltext,
3500
 
                    parent_ids, left_matching_blocks=None))
3501
 
            else:
3502
 
                child = (rev_id, parent_ids, record)
3503
 
                # Check if all the parents are present
3504
 
                self._check_parents(child, nodes_to_annotate)
3505
 
            while nodes_to_annotate:
3506
 
                # Should we use a queue here instead of a stack?
3507
 
                (rev_id, parent_ids, record) = nodes_to_annotate.pop()
3508
 
                (index_memo, compression_parent, parents,
3509
 
                 record_details) = self._all_build_details[rev_id]
3510
 
                blocks = None
3511
 
                if compression_parent is not None:
3512
 
                    comp_children = self._compression_children[compression_parent]
3513
 
                    if rev_id not in comp_children:
3514
 
                        raise AssertionError("%r not in compression children %r"
3515
 
                            % (rev_id, comp_children))
3516
 
                    # If there is only 1 child, it is safe to reuse this
3517
 
                    # content
3518
 
                    reuse_content = (len(comp_children) == 1
3519
 
                        and compression_parent not in
3520
 
                            self._nodes_to_keep_annotations)
3521
 
                    if reuse_content:
3522
 
                        # Remove it from the cache since it will be changing
3523
 
                        parent_fulltext_content = self._fulltext_contents.pop(compression_parent)
3524
 
                        # Make sure to copy the fulltext since it might be
3525
 
                        # modified
3526
 
                        parent_fulltext = list(parent_fulltext_content.text())
3527
 
                    else:
3528
 
                        parent_fulltext_content = self._fulltext_contents[compression_parent]
3529
 
                        parent_fulltext = parent_fulltext_content.text()
3530
 
                    comp_children.remove(rev_id)
3531
 
                    fulltext_content, delta = self._knit._factory.parse_record(
3532
 
                        rev_id, record, record_details,
3533
 
                        parent_fulltext_content,
3534
 
                        copy_base_content=(not reuse_content))
3535
 
                    fulltext = self._add_fulltext_content(rev_id,
3536
 
                                                          fulltext_content)
3537
 
                    if compression_parent == parent_ids[0]:
3538
 
                        # the compression_parent is the left parent, so we can
3539
 
                        # re-use the delta
3540
 
                        blocks = KnitContent.get_line_delta_blocks(delta,
3541
 
                                parent_fulltext, fulltext)
3542
 
                else:
3543
 
                    fulltext_content = self._knit._factory.parse_fulltext(
3544
 
                        record, rev_id)
3545
 
                    fulltext = self._add_fulltext_content(rev_id,
3546
 
                        fulltext_content)
3547
 
                nodes_to_annotate.extend(
3548
 
                    self._add_annotation(rev_id, fulltext, parent_ids,
3549
 
                                     left_matching_blocks=blocks))
3550
 
 
3551
 
    def _get_heads_provider(self):
3552
 
        """Create a heads provider for resolving ancestry issues."""
3553
 
        if self._heads_provider is not None:
3554
 
            return self._heads_provider
3555
 
        self._heads_provider = _mod_graph.KnownGraph(self._revision_id_graph)
3556
 
        return self._heads_provider
3557
 
 
3558
 
    def annotate(self, key):
3559
 
        """Return the annotated fulltext at the given key.
3560
 
 
3561
 
        :param key: The key to annotate.
3562
 
        """
3563
 
        if len(self._knit._fallback_vfs) > 0:
3564
 
            # stacked knits can't use the fast path at present.
3565
 
            return self._simple_annotate(key)
3566
 
        while True:
3567
 
            try:
3568
 
                records = self._get_build_graph(key)
3569
 
                if key in self._ghosts:
3570
 
                    raise errors.RevisionNotPresent(key, self._knit)
3571
 
                self._annotate_records(records)
3572
 
                return self._annotated_lines[key]
3573
 
            except errors.RetryWithNewPacks, e:
3574
 
                self._knit._access.reload_or_raise(e)
3575
 
                # The cached build_details are no longer valid
3576
 
                self._all_build_details.clear()
3577
 
 
3578
 
    def _simple_annotate(self, key):
3579
 
        """Return annotated fulltext, rediffing from the full texts.
3580
 
 
3581
 
        This is slow but makes no assumptions about the repository
3582
 
        being able to produce line deltas.
3583
 
        """
3584
 
        # TODO: this code generates a parent maps of present ancestors; it
3585
 
        #       could be split out into a separate method
3586
 
        #       -- mbp and robertc 20080704
3587
 
        graph = _mod_graph.Graph(self._knit)
3588
 
        parent_map = dict((k, v) for k, v in graph.iter_ancestry([key])
3589
 
                          if v is not None)
3590
 
        if not parent_map:
3591
 
            raise errors.RevisionNotPresent(key, self)
3592
 
        keys = parent_map.keys()
3593
 
        heads_provider = _mod_graph.KnownGraph(parent_map)
3594
 
        parent_cache = {}
3595
 
        reannotate = annotate.reannotate
3596
 
        for record in self._knit.get_record_stream(keys, 'topological', True):
3597
 
            key = record.key
3598
 
            fulltext = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
3599
 
            parents = parent_map[key]
3600
 
            if parents is not None:
3601
 
                parent_lines = [parent_cache[parent] for parent in parent_map[key]]
3602
 
            else:
3603
 
                parent_lines = []
3604
 
            parent_cache[key] = list(
3605
 
                reannotate(parent_lines, fulltext, key, None, heads_provider))
3606
 
        try:
3607
 
            return parent_cache[key]
3608
 
        except KeyError, e:
3609
 
            raise errors.RevisionNotPresent(key, self._knit)
3610
 
 
 
3485
            # At this point, we may be able to yield this content, if all
 
3486
            # parents are also finished
 
3487
            yield_this_text = self._check_ready_for_annotations(key,
 
3488
                                                                parent_keys)
 
3489
            if yield_this_text:
 
3490
                # All parents present
 
3491
                yield key, lines, len(lines)
 
3492
            to_process = self._process_pending(key)
 
3493
            while to_process:
 
3494
                this_process = to_process
 
3495
                to_process = []
 
3496
                for key in this_process:
 
3497
                    lines = self._text_cache[key]
 
3498
                    yield key, lines, len(lines)
 
3499
                    to_process.extend(self._process_pending(key))
3611
3500
 
3612
3501
try:
3613
 
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
3614
 
except ImportError:
 
3502
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
 
3503
except ImportError, e:
 
3504
    osutils.failed_to_load_extension(e)
3615
3505
    from bzrlib._knit_load_data_py import _load_data_py as _load_data