/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: John Arbash Meinel
  • Date: 2009-02-25 20:23:04 UTC
  • mto: This revision was merged to the branch mainline in revision 4051.
  • Revision ID: john@arbash-meinel.com-20090225202304-j52lrdrx8aw101uh
Turn _split_by_prefix into a classmethod, and add direct tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
1
 
# Copyright (C) 2006-2010 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
59
import sys
69
69
    lru_cache,
70
70
    pack,
71
71
    progress,
72
 
    static_tuple,
73
72
    trace,
74
73
    tsort,
75
74
    tuned_gzip,
76
 
    ui,
77
75
    )
78
76
""")
79
77
from bzrlib import (
105
103
    ConstantMapper,
106
104
    ContentFactory,
107
105
    ChunkedContentFactory,
108
 
    sort_groupcompress,
109
106
    VersionedFile,
110
107
    VersionedFiles,
111
108
    )
301
298
            if self._network_bytes is None:
302
299
                self._create_network_bytes()
303
300
            return self._network_bytes
304
 
        if ('-ft-' in self.storage_kind and
305
 
            storage_kind in ('chunked', 'fulltext')):
306
 
            adapter_key = (self.storage_kind, 'fulltext')
307
 
            adapter_factory = adapter_registry.get(adapter_key)
308
 
            adapter = adapter_factory(None)
309
 
            bytes = adapter.get_bytes(self)
310
 
            if storage_kind == 'chunked':
311
 
                return [bytes]
312
 
            else:
313
 
                return bytes
314
301
        if self._knit is not None:
315
 
            # Not redundant with direct conversion above - that only handles
316
 
            # fulltext cases.
317
302
            if storage_kind == 'chunked':
318
303
                return self._knit.get_lines(self.key[0])
319
304
            elif storage_kind == 'fulltext':
666
651
 
667
652
        see parse_fulltext which this inverts.
668
653
        """
 
654
        # TODO: jam 20070209 We only do the caching thing to make sure that
 
655
        #       the origin is a valid utf-8 line, eventually we could remove it
669
656
        return ['%s %s' % (o, t) for o, t in content._lines]
670
657
 
671
658
    def lower_line_delta(self, delta):
686
673
        content = knit._get_content(key)
687
674
        # adjust for the fact that serialised annotations are only key suffixes
688
675
        # for this factory.
689
 
        if type(key) is tuple:
 
676
        if type(key) == tuple:
690
677
            prefix = key[:-1]
691
678
            origins = content.annotate()
692
679
            result = []
758
745
 
759
746
    def annotate(self, knit, key):
760
747
        annotator = _KnitAnnotator(knit)
761
 
        return annotator.annotate_flat(key)
 
748
        return annotator.annotate(key)
762
749
 
763
750
 
764
751
 
909
896
            # indexes can't directly store that, so we give them
910
897
            # an empty tuple instead.
911
898
            parents = ()
912
 
        line_bytes = ''.join(lines)
913
899
        return self._add(key, lines, parents,
914
 
            parent_texts, left_matching_blocks, nostore_sha, random_id,
915
 
            line_bytes=line_bytes)
916
 
 
917
 
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
918
 
        """See VersionedFiles._add_text()."""
919
 
        self._index._check_write_ok()
920
 
        self._check_add(key, None, random_id, check_content=False)
921
 
        if text.__class__ is not str:
922
 
            raise errors.BzrBadParameterUnicode("text")
923
 
        if parents is None:
924
 
            # The caller might pass None if there is no graph data, but kndx
925
 
            # indexes can't directly store that, so we give them
926
 
            # an empty tuple instead.
927
 
            parents = ()
928
 
        return self._add(key, None, parents,
929
 
            None, None, nostore_sha, random_id,
930
 
            line_bytes=text)
 
900
            parent_texts, left_matching_blocks, nostore_sha, random_id)
931
901
 
932
902
    def _add(self, key, lines, parents, parent_texts,
933
 
        left_matching_blocks, nostore_sha, random_id,
934
 
        line_bytes):
 
903
        left_matching_blocks, nostore_sha, random_id):
935
904
        """Add a set of lines on top of version specified by parents.
936
905
 
937
906
        Any versions not present will be converted into ghosts.
938
 
 
939
 
        :param lines: A list of strings where each one is a single line (has a
940
 
            single newline at the end of the string) This is now optional
941
 
            (callers can pass None). It is left in its location for backwards
942
 
            compatibility. It should ''.join(lines) must == line_bytes
943
 
        :param line_bytes: A single string containing the content
944
 
 
945
 
        We pass both lines and line_bytes because different routes bring the
946
 
        values to this function. And for memory efficiency, we don't want to
947
 
        have to split/join on-demand.
948
907
        """
949
908
        # first thing, if the content is something we don't need to store, find
950
909
        # that out.
 
910
        line_bytes = ''.join(lines)
951
911
        digest = sha_string(line_bytes)
952
912
        if nostore_sha == digest:
953
913
            raise errors.ExistingContent
974
934
 
975
935
        text_length = len(line_bytes)
976
936
        options = []
977
 
        no_eol = False
978
 
        # Note: line_bytes is not modified to add a newline, that is tracked
979
 
        #       via the no_eol flag. 'lines' *is* modified, because that is the
980
 
        #       general values needed by the Content code.
981
 
        if line_bytes and line_bytes[-1] != '\n':
982
 
            options.append('no-eol')
983
 
            no_eol = True
984
 
            # Copy the existing list, or create a new one
985
 
            if lines is None:
986
 
                lines = osutils.split_lines(line_bytes)
987
 
            else:
 
937
        if lines:
 
938
            if lines[-1][-1] != '\n':
 
939
                # copy the contents of lines.
988
940
                lines = lines[:]
989
 
            # Replace the last line with one that ends in a final newline
990
 
            lines[-1] = lines[-1] + '\n'
991
 
        if lines is None:
992
 
            lines = osutils.split_lines(line_bytes)
 
941
                options.append('no-eol')
 
942
                lines[-1] = lines[-1] + '\n'
 
943
                line_bytes += '\n'
993
944
 
994
 
        for element in key[:-1]:
995
 
            if type(element) is not str:
996
 
                raise TypeError("key contains non-strings: %r" % (key,))
997
 
        if key[-1] is None:
998
 
            key = key[:-1] + ('sha1:' + digest,)
999
 
        elif type(key[-1]) is not str:
 
945
        for element in key:
 
946
            if type(element) != str:
1000
947
                raise TypeError("key contains non-strings: %r" % (key,))
1001
948
        # Knit hunks are still last-element only
1002
949
        version_id = key[-1]
1003
950
        content = self._factory.make(lines, version_id)
1004
 
        if no_eol:
 
951
        if 'no-eol' in options:
1005
952
            # Hint to the content object that its text() call should strip the
1006
953
            # EOL.
1007
954
            content._should_strip_eol = True
1019
966
        else:
1020
967
            options.append('fulltext')
1021
968
            # isinstance is slower and we have no hierarchy.
1022
 
            if self._factory.__class__ is KnitPlainFactory:
 
969
            if self._factory.__class__ == KnitPlainFactory:
1023
970
                # Use the already joined bytes saving iteration time in
1024
971
                # _record_to_data.
1025
 
                dense_lines = [line_bytes]
1026
 
                if no_eol:
1027
 
                    dense_lines.append('\n')
1028
972
                size, bytes = self._record_to_data(key, digest,
1029
 
                    lines, dense_lines)
 
973
                    lines, [line_bytes])
1030
974
            else:
1031
975
                # get mixed annotation + content and feed it into the
1032
976
                # serialiser.
1044
988
        """See VersionedFiles.annotate."""
1045
989
        return self._factory.annotate(self, key)
1046
990
 
1047
 
    def get_annotator(self):
1048
 
        return _KnitAnnotator(self)
1049
 
 
1050
 
    def check(self, progress_bar=None, keys=None):
 
991
    def check(self, progress_bar=None):
1051
992
        """See VersionedFiles.check()."""
1052
 
        if keys is None:
1053
 
            return self._logical_check()
1054
 
        else:
1055
 
            # At the moment, check does not extra work over get_record_stream
1056
 
            return self.get_record_stream(keys, 'unordered', True)
1057
 
 
1058
 
    def _logical_check(self):
1059
993
        # This doesn't actually test extraction of everything, but that will
1060
994
        # impact 'bzr check' substantially, and needs to be integrated with
1061
995
        # care. However, it does check for the obvious problem of a delta with
1075
1009
    def _check_add(self, key, lines, random_id, check_content):
1076
1010
        """check that version_id and lines are safe to add."""
1077
1011
        version_id = key[-1]
1078
 
        if version_id is not None:
1079
 
            if contains_whitespace(version_id):
1080
 
                raise InvalidRevisionId(version_id, self)
1081
 
            self.check_not_reserved_id(version_id)
 
1012
        if contains_whitespace(version_id):
 
1013
            raise InvalidRevisionId(version_id, self)
 
1014
        self.check_not_reserved_id(version_id)
1082
1015
        # TODO: If random_id==False and the key is already present, we should
1083
1016
        # probably check that the existing content is identical to what is
1084
1017
        # being inserted, and otherwise raise an exception.  This would make
1192
1125
        generator = _VFContentMapGenerator(self, [key])
1193
1126
        return generator._get_content(key)
1194
1127
 
1195
 
    def get_known_graph_ancestry(self, keys):
1196
 
        """Get a KnownGraph instance with the ancestry of keys."""
1197
 
        parent_map, missing_keys = self._index.find_ancestry(keys)
1198
 
        for fallback in self._fallback_vfs:
1199
 
            if not missing_keys:
1200
 
                break
1201
 
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1202
 
                                                missing_keys)
1203
 
            parent_map.update(f_parent_map)
1204
 
            missing_keys = f_missing_keys
1205
 
        kg = _mod_graph.KnownGraph(parent_map)
1206
 
        return kg
1207
 
 
1208
1128
    def get_parent_map(self, keys):
1209
1129
        """Get a map of the graph parents of keys.
1210
1130
 
1336
1256
                prefix_order.append(prefix)
1337
1257
        return split_by_prefix, prefix_order
1338
1258
 
1339
 
    def _group_keys_for_io(self, keys, non_local_keys, positions,
1340
 
                           _min_buffer_size=_STREAM_MIN_BUFFER_SIZE):
 
1259
    def _group_keys_for_io(self, keys, non_local_keys, positions):
1341
1260
        """For the given keys, group them into 'best-sized' requests.
1342
1261
 
1343
1262
        The idea is to avoid making 1 request per file, but to never try to
1345
1264
        possible, we should try to group requests to the same pack file
1346
1265
        together.
1347
1266
 
1348
 
        :return: list of (keys, non_local) tuples that indicate what keys
1349
 
            should be fetched next.
 
1267
        :return: yield (keys, non_local) tuples that indicate what keys should
 
1268
            be fetched next.
1350
1269
        """
1351
1270
        # TODO: Ideally we would group on 2 factors. We want to extract texts
1352
1271
        #       from the same pack file together, and we want to extract all
1368
1287
            cur_size += this_size
1369
1288
            cur_keys.extend(keys)
1370
1289
            cur_non_local.update(non_local)
1371
 
            if cur_size > _min_buffer_size:
 
1290
            if cur_size > _STREAM_MIN_BUFFER_SIZE:
1372
1291
                result.append((cur_keys, cur_non_local))
1373
1292
                sizes.append(cur_size)
1374
1293
                cur_keys = []
1377
1296
        if cur_keys:
1378
1297
            result.append((cur_keys, cur_non_local))
1379
1298
            sizes.append(cur_size)
 
1299
        trace.mutter('Collapsed %d keys into %d requests w/ %d file_ids'
 
1300
                     ' w/ sizes: %s', total_keys, len(result),
 
1301
                     len(prefix_split_keys), sizes)
1380
1302
        return result
1381
1303
 
1382
1304
    def get_record_stream(self, keys, ordering, include_delta_closure):
1396
1318
        if not keys:
1397
1319
            return
1398
1320
        if not self._index.has_graph:
1399
 
            # Cannot sort when no graph has been stored.
 
1321
            # Cannot topological order when no graph has been stored.
1400
1322
            ordering = 'unordered'
1401
1323
 
1402
1324
        remaining_keys = keys
1458
1380
                    needed_from_fallback.add(key)
1459
1381
        # Double index lookups here : need a unified api ?
1460
1382
        global_map, parent_maps = self._get_parent_map_with_sources(keys)
1461
 
        if ordering in ('topological', 'groupcompress'):
1462
 
            if ordering == 'topological':
1463
 
                # Global topological sort
1464
 
                present_keys = tsort.topo_sort(global_map)
1465
 
            else:
1466
 
                present_keys = sort_groupcompress(global_map)
 
1383
        if ordering == 'topological':
 
1384
            # Global topological sort
 
1385
            present_keys = tsort.topo_sort(global_map)
1467
1386
            # Now group by source:
1468
1387
            source_keys = []
1469
1388
            current_source = None
1479
1398
        else:
1480
1399
            if ordering != 'unordered':
1481
1400
                raise AssertionError('valid values for ordering are:'
1482
 
                    ' "unordered", "groupcompress" or "topological" not: %r'
 
1401
                    ' "unordered" or "topological" not: %r'
1483
1402
                    % (ordering,))
1484
1403
            # Just group by source; remote sources first.
1485
1404
            present_keys = []
1511
1430
                                                                non_local_keys,
1512
1431
                                                                positions):
1513
1432
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1514
 
                                                   global_map,
1515
 
                                                   ordering=ordering)
 
1433
                                                   global_map)
1516
1434
                for record in generator.get_record_stream():
1517
1435
                    yield record
1518
1436
        else:
1520
1438
                if source is parent_maps[0]:
1521
1439
                    # this KnitVersionedFiles
1522
1440
                    records = [(key, positions[key][1]) for key in keys]
1523
 
                    for key, raw_data in self._read_records_iter_unchecked(records):
 
1441
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
1524
1442
                        (record_details, index_memo, _) = positions[key]
1525
1443
                        yield KnitContentFactory(key, global_map[key],
1526
 
                            record_details, None, raw_data, self._factory.annotated, None)
 
1444
                            record_details, sha1, raw_data, self._factory.annotated, None)
1527
1445
                else:
1528
1446
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1529
1447
                    for record in vf.get_record_stream(keys, ordering,
1598
1516
        # key = basis_parent, value = index entry to add
1599
1517
        buffered_index_entries = {}
1600
1518
        for record in stream:
1601
 
            kind = record.storage_kind
1602
 
            if kind.startswith('knit-') and kind.endswith('-gz'):
1603
 
                # Check that the ID in the header of the raw knit bytes matches
1604
 
                # the record metadata.
1605
 
                raw_data = record._raw_record
1606
 
                df, rec = self._parse_record_header(record.key, raw_data)
1607
 
                df.close()
1608
 
            buffered = False
1609
1519
            parents = record.parents
1610
1520
            if record.storage_kind in delta_types:
1611
1521
                # TODO: eventually the record itself should track
1657
1567
                access_memo = self._access.add_raw_records(
1658
1568
                    [(record.key, len(bytes))], bytes)[0]
1659
1569
                index_entry = (record.key, options, access_memo, parents)
 
1570
                buffered = False
1660
1571
                if 'fulltext' not in options:
1661
1572
                    # Not a fulltext, so we need to make sure the compression
1662
1573
                    # parent will also be present.
1684
1595
                # KnitVersionedFiles doesn't permit deltas (_max_delta_chain ==
1685
1596
                # 0) or because it depends on a base only present in the
1686
1597
                # fallback kvfs.
1687
 
                self._access.flush()
1688
1598
                try:
1689
1599
                    # Try getting a fulltext directly from the record.
1690
1600
                    bytes = record.get_bytes_as('fulltext')
1698
1608
                except errors.RevisionAlreadyPresent:
1699
1609
                    pass
1700
1610
            # Add any records whose basis parent is now available.
1701
 
            if not buffered:
1702
 
                added_keys = [record.key]
1703
 
                while added_keys:
1704
 
                    key = added_keys.pop(0)
1705
 
                    if key in buffered_index_entries:
1706
 
                        index_entries = buffered_index_entries[key]
1707
 
                        self._index.add_records(index_entries)
1708
 
                        added_keys.extend(
1709
 
                            [index_entry[0] for index_entry in index_entries])
1710
 
                        del buffered_index_entries[key]
 
1611
            added_keys = [record.key]
 
1612
            while added_keys:
 
1613
                key = added_keys.pop(0)
 
1614
                if key in buffered_index_entries:
 
1615
                    index_entries = buffered_index_entries[key]
 
1616
                    self._index.add_records(index_entries)
 
1617
                    added_keys.extend(
 
1618
                        [index_entry[0] for index_entry in index_entries])
 
1619
                    del buffered_index_entries[key]
1711
1620
        if buffered_index_entries:
1712
1621
            # There were index entries buffered at the end of the stream,
1713
1622
            # So these need to be added (if the index supports holding such
1714
1623
            # entries for later insertion)
1715
 
            all_entries = []
1716
1624
            for key in buffered_index_entries:
1717
1625
                index_entries = buffered_index_entries[key]
1718
 
                all_entries.extend(index_entries)
1719
 
            self._index.add_records(
1720
 
                all_entries, missing_compression_parents=True)
 
1626
                self._index.add_records(index_entries,
 
1627
                    missing_compression_parents=True)
1721
1628
 
1722
1629
    def get_missing_compression_parent_keys(self):
1723
1630
        """Return an iterable of keys of missing compression parents.
1752
1659
         * If a requested key did not change any lines (or didn't have any
1753
1660
           lines), it may not be mentioned at all in the result.
1754
1661
 
1755
 
        :param pb: Progress bar supplied by caller.
1756
1662
        :return: An iterator over (line, key).
1757
1663
        """
1758
1664
        if pb is None:
1759
 
            pb = ui.ui_factory.nested_progress_bar()
 
1665
            pb = progress.DummyProgress()
1760
1666
        keys = set(keys)
1761
1667
        total = len(keys)
1762
1668
        done = False
1772
1678
                        key_records.append((key, details[0]))
1773
1679
                records_iter = enumerate(self._read_records_iter(key_records))
1774
1680
                for (key_idx, (key, data, sha_value)) in records_iter:
1775
 
                    pb.update('Walking content', key_idx, total)
 
1681
                    pb.update('Walking content.', key_idx, total)
1776
1682
                    compression_parent = build_details[key][1]
1777
1683
                    if compression_parent is None:
1778
1684
                        # fulltext
1808
1714
                source_keys.add(key)
1809
1715
                yield line, key
1810
1716
            keys.difference_update(source_keys)
1811
 
        pb.update('Walking content', total, total)
 
1717
        pb.update('Walking content.', total, total)
1812
1718
 
1813
1719
    def _make_line_delta(self, delta_seq, new_content):
1814
1720
        """Generate a line delta from delta_seq and new_content."""
1992
1898
            function spends less time resizing the final string.
1993
1899
        :return: (len, a StringIO instance with the raw data ready to read.)
1994
1900
        """
1995
 
        chunks = ["version %s %d %s\n" % (key[-1], len(lines), digest)]
1996
 
        chunks.extend(dense_lines or lines)
1997
 
        chunks.append("end %s\n" % key[-1])
1998
 
        for chunk in chunks:
1999
 
            if type(chunk) is not str:
2000
 
                raise AssertionError(
2001
 
                    'data must be plain bytes was %s' % type(chunk))
 
1901
        # Note: using a string copy here increases memory pressure with e.g.
 
1902
        # ISO's, but it is about 3 seconds faster on a 1.2Ghz intel machine
 
1903
        # when doing the initial commit of a mozilla tree. RBC 20070921
 
1904
        bytes = ''.join(chain(
 
1905
            ["version %s %d %s\n" % (key[-1],
 
1906
                                     len(lines),
 
1907
                                     digest)],
 
1908
            dense_lines or lines,
 
1909
            ["end %s\n" % key[-1]]))
 
1910
        if type(bytes) != str:
 
1911
            raise AssertionError(
 
1912
                'data must be plain bytes was %s' % type(bytes))
2002
1913
        if lines and lines[-1][-1] != '\n':
2003
1914
            raise ValueError('corrupt lines value %r' % lines)
2004
 
        compressed_bytes = tuned_gzip.chunks_to_gzip(chunks)
 
1915
        compressed_bytes = tuned_gzip.bytes_to_gzip(bytes)
2005
1916
        return len(compressed_bytes), compressed_bytes
2006
1917
 
2007
1918
    def _split_header(self, line):
2025
1936
class _ContentMapGenerator(object):
2026
1937
    """Generate texts or expose raw deltas for a set of texts."""
2027
1938
 
2028
 
    def __init__(self, ordering='unordered'):
2029
 
        self._ordering = ordering
2030
 
 
2031
1939
    def _get_content(self, key):
2032
1940
        """Get the content object for key."""
2033
1941
        # Note that _get_content is only called when the _ContentMapGenerator
2067
1975
            # Loop over fallback repositories asking them for texts - ignore
2068
1976
            # any missing from a particular fallback.
2069
1977
            for record in source.get_record_stream(missing_keys,
2070
 
                self._ordering, True):
 
1978
                'unordered', True):
2071
1979
                if record.storage_kind == 'absent':
2072
1980
                    # Not in thie particular stream, may be in one of the
2073
1981
                    # other fallback vfs objects.
2075
1983
                missing_keys.remove(record.key)
2076
1984
                yield record
2077
1985
 
2078
 
        if self._raw_record_map is None:
2079
 
            raise AssertionError('_raw_record_map should have been filled')
 
1986
        self._raw_record_map = self.vf._get_record_map_unparsed(self.keys,
 
1987
            allow_missing=True)
2080
1988
        first = True
2081
1989
        for key in self.keys:
2082
1990
            if key in self.nonlocal_keys:
2205
2113
    """Content map generator reading from a VersionedFiles object."""
2206
2114
 
2207
2115
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2208
 
        global_map=None, raw_record_map=None, ordering='unordered'):
 
2116
        global_map=None, raw_record_map=None):
2209
2117
        """Create a _ContentMapGenerator.
2210
2118
 
2211
2119
        :param versioned_files: The versioned files that the texts are being
2219
2127
        :param raw_record_map: A unparsed raw record map to use for answering
2220
2128
            contents.
2221
2129
        """
2222
 
        _ContentMapGenerator.__init__(self, ordering=ordering)
2223
2130
        # The vf to source data from
2224
2131
        self.vf = versioned_files
2225
2132
        # The keys desired
2369
2276
    FLAGS is a comma separated list of flags about the record. Values include
2370
2277
        no-eol, line-delta, fulltext.
2371
2278
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2372
 
        that the compressed data starts at.
 
2279
        that the the compressed data starts at.
2373
2280
    LENGTH is the ascii representation of the length of the data file.
2374
2281
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2375
2282
        REVISION_ID.
2446
2353
                    line = "\n%s %s %s %s %s :" % (
2447
2354
                        key[-1], ','.join(options), pos, size,
2448
2355
                        self._dictionary_compress(parents))
2449
 
                    if type(line) is not str:
 
2356
                    if type(line) != str:
2450
2357
                        raise AssertionError(
2451
2358
                            'data must be utf8 was %s' % type(line))
2452
2359
                    lines.append(line)
2584
2491
        except KeyError:
2585
2492
            raise RevisionNotPresent(key, self)
2586
2493
 
2587
 
    def find_ancestry(self, keys):
2588
 
        """See CombinedGraphIndex.find_ancestry()"""
2589
 
        prefixes = set(key[:-1] for key in keys)
2590
 
        self._load_prefixes(prefixes)
2591
 
        result = {}
2592
 
        parent_map = {}
2593
 
        missing_keys = set()
2594
 
        pending_keys = list(keys)
2595
 
        # This assumes that keys will not reference parents in a different
2596
 
        # prefix, which is accurate so far.
2597
 
        while pending_keys:
2598
 
            key = pending_keys.pop()
2599
 
            if key in parent_map:
2600
 
                continue
2601
 
            prefix = key[:-1]
2602
 
            try:
2603
 
                suffix_parents = self._kndx_cache[prefix][0][key[-1]][4]
2604
 
            except KeyError:
2605
 
                missing_keys.add(key)
2606
 
            else:
2607
 
                parent_keys = tuple([prefix + (suffix,)
2608
 
                                     for suffix in suffix_parents])
2609
 
                parent_map[key] = parent_keys
2610
 
                pending_keys.extend([p for p in parent_keys
2611
 
                                        if p not in parent_map])
2612
 
        return parent_map, missing_keys
2613
 
 
2614
2494
    def get_parent_map(self, keys):
2615
2495
        """Get a map of the parents of keys.
2616
2496
 
2668
2548
        result = set()
2669
2549
        # Identify all key prefixes.
2670
2550
        # XXX: A bit hacky, needs polish.
2671
 
        if type(self._mapper) is ConstantMapper:
 
2551
        if type(self._mapper) == ConstantMapper:
2672
2552
            prefixes = [()]
2673
2553
        else:
2674
2554
            relpaths = set()
2706
2586
                    del self._history
2707
2587
                except NoSuchFile:
2708
2588
                    self._kndx_cache[prefix] = ({}, [])
2709
 
                    if type(self._mapper) is ConstantMapper:
 
2589
                    if type(self._mapper) == ConstantMapper:
2710
2590
                        # preserve behaviour for revisions.kndx etc.
2711
2591
                        self._init_index(path)
2712
2592
                    del self._cache
2786
2666
        return key[:-1], key[-1]
2787
2667
 
2788
2668
 
2789
 
class _KeyRefs(object):
2790
 
 
2791
 
    def __init__(self, track_new_keys=False):
2792
 
        # dict mapping 'key' to 'set of keys referring to that key'
2793
 
        self.refs = {}
2794
 
        if track_new_keys:
2795
 
            # set remembering all new keys
2796
 
            self.new_keys = set()
2797
 
        else:
2798
 
            self.new_keys = None
2799
 
 
2800
 
    def clear(self):
2801
 
        if self.refs:
2802
 
            self.refs.clear()
2803
 
        if self.new_keys:
2804
 
            self.new_keys.clear()
2805
 
 
2806
 
    def add_references(self, key, refs):
2807
 
        # Record the new references
2808
 
        for referenced in refs:
2809
 
            try:
2810
 
                needed_by = self.refs[referenced]
2811
 
            except KeyError:
2812
 
                needed_by = self.refs[referenced] = set()
2813
 
            needed_by.add(key)
2814
 
        # Discard references satisfied by the new key
2815
 
        self.add_key(key)
2816
 
 
2817
 
    def get_new_keys(self):
2818
 
        return self.new_keys
2819
 
    
2820
 
    def get_unsatisfied_refs(self):
2821
 
        return self.refs.iterkeys()
2822
 
 
2823
 
    def _satisfy_refs_for_key(self, key):
2824
 
        try:
2825
 
            del self.refs[key]
2826
 
        except KeyError:
2827
 
            # No keys depended on this key.  That's ok.
2828
 
            pass
2829
 
 
2830
 
    def add_key(self, key):
2831
 
        # satisfy refs for key, and remember that we've seen this key.
2832
 
        self._satisfy_refs_for_key(key)
2833
 
        if self.new_keys is not None:
2834
 
            self.new_keys.add(key)
2835
 
 
2836
 
    def satisfy_refs_for_keys(self, keys):
2837
 
        for key in keys:
2838
 
            self._satisfy_refs_for_key(key)
2839
 
 
2840
 
    def get_referrers(self):
2841
 
        result = set()
2842
 
        for referrers in self.refs.itervalues():
2843
 
            result.update(referrers)
2844
 
        return result
2845
 
 
2846
 
 
2847
2669
class _KnitGraphIndex(object):
2848
2670
    """A KnitVersionedFiles index layered on GraphIndex."""
2849
2671
 
2850
2672
    def __init__(self, graph_index, is_locked, deltas=False, parents=True,
2851
 
        add_callback=None, track_external_parent_refs=False):
 
2673
        add_callback=None):
2852
2674
        """Construct a KnitGraphIndex on a graph_index.
2853
2675
 
2854
2676
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
2862
2684
            [(node, value, node_refs), ...]
2863
2685
        :param is_locked: A callback, returns True if the index is locked and
2864
2686
            thus usable.
2865
 
        :param track_external_parent_refs: If True, record all external parent
2866
 
            references parents from added records.  These can be retrieved
2867
 
            later by calling get_missing_parents().
2868
2687
        """
2869
2688
        self._add_callback = add_callback
2870
2689
        self._graph_index = graph_index
2878
2697
        self.has_graph = parents
2879
2698
        self._is_locked = is_locked
2880
2699
        self._missing_compression_parents = set()
2881
 
        if track_external_parent_refs:
2882
 
            self._key_dependencies = _KeyRefs()
2883
 
        else:
2884
 
            self._key_dependencies = None
2885
2700
 
2886
2701
    def __repr__(self):
2887
2702
        return "%s(%r)" % (self.__class__.__name__, self._graph_index)
2911
2726
 
2912
2727
        keys = {}
2913
2728
        compression_parents = set()
2914
 
        key_dependencies = self._key_dependencies
2915
2729
        for (key, options, access_memo, parents) in records:
2916
2730
            if self._parents:
2917
2731
                parents = tuple(parents)
2918
 
                if key_dependencies is not None:
2919
 
                    key_dependencies.add_references(key, parents)
2920
2732
            index, pos, size = access_memo
2921
2733
            if 'no-eol' in options:
2922
2734
                value = 'N'
2946
2758
        if not random_id:
2947
2759
            present_nodes = self._get_entries(keys)
2948
2760
            for (index, key, value, node_refs) in present_nodes:
2949
 
                parents = node_refs[:1]
2950
 
                # Sometimes these are passed as a list rather than a tuple
2951
 
                passed = static_tuple.as_tuples(keys[key])
2952
 
                passed_parents = passed[1][:1]
2953
2761
                if (value[0] != keys[key][0][0] or
2954
 
                    parents != passed_parents):
2955
 
                    node_refs = static_tuple.as_tuples(node_refs)
 
2762
                    node_refs[:1] != keys[key][1][:1]):
2956
2763
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2957
 
                        ": %s %s" % ((value, node_refs), passed))
 
2764
                        ": %s %s" % ((value, node_refs), keys[key]))
2958
2765
                del keys[key]
2959
2766
        result = []
2960
2767
        if self._parents:
2989
2796
            new_missing = graph_index.external_references(ref_list_num=1)
2990
2797
            new_missing.difference_update(self.get_parent_map(new_missing))
2991
2798
            self._missing_compression_parents.update(new_missing)
2992
 
        if self._key_dependencies is not None:
2993
 
            # Add parent refs from graph_index (and discard parent refs that
2994
 
            # the graph_index has).
2995
 
            for node in graph_index.iter_all_entries():
2996
 
                self._key_dependencies.add_references(node[1], node[3][0])
2997
2799
 
2998
2800
    def get_missing_compression_parents(self):
2999
2801
        """Return the keys of missing compression parents.
3003
2805
        """
3004
2806
        return frozenset(self._missing_compression_parents)
3005
2807
 
3006
 
    def get_missing_parents(self):
3007
 
        """Return the keys of missing parents."""
3008
 
        # If updating this, you should also update
3009
 
        # groupcompress._GCGraphIndex.get_missing_parents
3010
 
        # We may have false positives, so filter those out.
3011
 
        self._key_dependencies.satisfy_refs_for_keys(
3012
 
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
3013
 
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
3014
 
 
3015
2808
    def _check_read(self):
3016
2809
        """raise if reads are not permitted."""
3017
2810
        if not self._is_locked():
3125
2918
            options.append('no-eol')
3126
2919
        return options
3127
2920
 
3128
 
    def find_ancestry(self, keys):
3129
 
        """See CombinedGraphIndex.find_ancestry()"""
3130
 
        return self._graph_index.find_ancestry(keys, 0)
3131
 
 
3132
2921
    def get_parent_map(self, keys):
3133
2922
        """Get a map of the parents of keys.
3134
2923
 
3221
3010
            opaque index memo. For _KnitKeyAccess the memo is (key, pos,
3222
3011
            length), where the key is the record key.
3223
3012
        """
3224
 
        if type(raw_data) is not str:
 
3013
        if type(raw_data) != str:
3225
3014
            raise AssertionError(
3226
3015
                'data must be plain bytes was %s' % type(raw_data))
3227
3016
        result = []
3244
3033
            result.append((key, base, size))
3245
3034
        return result
3246
3035
 
3247
 
    def flush(self):
3248
 
        """Flush pending writes on this access object.
3249
 
        
3250
 
        For .knit files this is a no-op.
3251
 
        """
3252
 
        pass
3253
 
 
3254
3036
    def get_raw_records(self, memos_for_retrieval):
3255
3037
        """Get the raw bytes for a records.
3256
3038
 
3281
3063
class _DirectPackAccess(object):
3282
3064
    """Access to data in one or more packs with less translation."""
3283
3065
 
3284
 
    def __init__(self, index_to_packs, reload_func=None, flush_func=None):
 
3066
    def __init__(self, index_to_packs, reload_func=None):
3285
3067
        """Create a _DirectPackAccess object.
3286
3068
 
3287
3069
        :param index_to_packs: A dict mapping index objects to the transport
3294
3076
        self._write_index = None
3295
3077
        self._indices = index_to_packs
3296
3078
        self._reload_func = reload_func
3297
 
        self._flush_func = flush_func
3298
3079
 
3299
3080
    def add_raw_records(self, key_sizes, raw_data):
3300
3081
        """Add raw knit bytes to a storage area.
3310
3091
            length), where the index field is the write_index object supplied
3311
3092
            to the PackAccess object.
3312
3093
        """
3313
 
        if type(raw_data) is not str:
 
3094
        if type(raw_data) != str:
3314
3095
            raise AssertionError(
3315
3096
                'data must be plain bytes was %s' % type(raw_data))
3316
3097
        result = []
3322
3103
            result.append((self._write_index, p_offset, p_length))
3323
3104
        return result
3324
3105
 
3325
 
    def flush(self):
3326
 
        """Flush pending writes on this access object.
3327
 
 
3328
 
        This will flush any buffered writes to a NewPack.
3329
 
        """
3330
 
        if self._flush_func is not None:
3331
 
            self._flush_func()
3332
 
            
3333
3106
    def get_raw_records(self, memos_for_retrieval):
3334
3107
        """Get the raw bytes for a records.
3335
3108
 
3429
3202
    recommended.
3430
3203
    """
3431
3204
    annotator = _KnitAnnotator(knit)
3432
 
    return iter(annotator.annotate_flat(revision_id))
3433
 
 
3434
 
 
3435
 
class _KnitAnnotator(annotate.Annotator):
 
3205
    return iter(annotator.annotate(revision_id))
 
3206
 
 
3207
 
 
3208
class _KnitAnnotator(object):
3436
3209
    """Build up the annotations for a text."""
3437
3210
 
3438
 
    def __init__(self, vf):
3439
 
        annotate.Annotator.__init__(self, vf)
3440
 
 
3441
 
        # TODO: handle Nodes which cannot be extracted
3442
 
        # self._ghosts = set()
3443
 
 
3444
 
        # Map from (key, parent_key) => matching_blocks, should be 'use once'
3445
 
        self._matching_blocks = {}
3446
 
 
3447
 
        # KnitContent objects
3448
 
        self._content_objects = {}
3449
 
        # The number of children that depend on this fulltext content object
3450
 
        self._num_compression_children = {}
3451
 
        # Delta records that need their compression parent before they can be
3452
 
        # expanded
3453
 
        self._pending_deltas = {}
3454
 
        # Fulltext records that are waiting for their parents fulltexts before
3455
 
        # they can be yielded for annotation
3456
 
        self._pending_annotation = {}
 
3211
    def __init__(self, knit):
 
3212
        self._knit = knit
 
3213
 
 
3214
        # Content objects, differs from fulltexts because of how final newlines
 
3215
        # are treated by knits. the content objects here will always have a
 
3216
        # final newline
 
3217
        self._fulltext_contents = {}
 
3218
 
 
3219
        # Annotated lines of specific revisions
 
3220
        self._annotated_lines = {}
 
3221
 
 
3222
        # Track the raw data for nodes that we could not process yet.
 
3223
        # This maps the revision_id of the base to a list of children that will
 
3224
        # annotated from it.
 
3225
        self._pending_children = {}
 
3226
 
 
3227
        # Nodes which cannot be extracted
 
3228
        self._ghosts = set()
 
3229
 
 
3230
        # Track how many children this node has, so we know if we need to keep
 
3231
        # it
 
3232
        self._annotate_children = {}
 
3233
        self._compression_children = {}
3457
3234
 
3458
3235
        self._all_build_details = {}
 
3236
        # The children => parent revision_id graph
 
3237
        self._revision_id_graph = {}
 
3238
 
 
3239
        self._heads_provider = None
 
3240
 
 
3241
        self._nodes_to_keep_annotations = set()
 
3242
        self._generations_until_keep = 100
 
3243
 
 
3244
    def set_generations_until_keep(self, value):
 
3245
        """Set the number of generations before caching a node.
 
3246
 
 
3247
        Setting this to -1 will cache every merge node, setting this higher
 
3248
        will cache fewer nodes.
 
3249
        """
 
3250
        self._generations_until_keep = value
 
3251
 
 
3252
    def _add_fulltext_content(self, revision_id, content_obj):
 
3253
        self._fulltext_contents[revision_id] = content_obj
 
3254
        # TODO: jam 20080305 It might be good to check the sha1digest here
 
3255
        return content_obj.text()
 
3256
 
 
3257
    def _check_parents(self, child, nodes_to_annotate):
 
3258
        """Check if all parents have been processed.
 
3259
 
 
3260
        :param child: A tuple of (rev_id, parents, raw_content)
 
3261
        :param nodes_to_annotate: If child is ready, add it to
 
3262
            nodes_to_annotate, otherwise put it back in self._pending_children
 
3263
        """
 
3264
        for parent_id in child[1]:
 
3265
            if (parent_id not in self._annotated_lines):
 
3266
                # This parent is present, but another parent is missing
 
3267
                self._pending_children.setdefault(parent_id,
 
3268
                                                  []).append(child)
 
3269
                break
 
3270
        else:
 
3271
            # This one is ready to be processed
 
3272
            nodes_to_annotate.append(child)
 
3273
 
 
3274
    def _add_annotation(self, revision_id, fulltext, parent_ids,
 
3275
                        left_matching_blocks=None):
 
3276
        """Add an annotation entry.
 
3277
 
 
3278
        All parents should already have been annotated.
 
3279
        :return: A list of children that now have their parents satisfied.
 
3280
        """
 
3281
        a = self._annotated_lines
 
3282
        annotated_parent_lines = [a[p] for p in parent_ids]
 
3283
        annotated_lines = list(annotate.reannotate(annotated_parent_lines,
 
3284
            fulltext, revision_id, left_matching_blocks,
 
3285
            heads_provider=self._get_heads_provider()))
 
3286
        self._annotated_lines[revision_id] = annotated_lines
 
3287
        for p in parent_ids:
 
3288
            ann_children = self._annotate_children[p]
 
3289
            ann_children.remove(revision_id)
 
3290
            if (not ann_children
 
3291
                and p not in self._nodes_to_keep_annotations):
 
3292
                del self._annotated_lines[p]
 
3293
                del self._all_build_details[p]
 
3294
                if p in self._fulltext_contents:
 
3295
                    del self._fulltext_contents[p]
 
3296
        # Now that we've added this one, see if there are any pending
 
3297
        # deltas to be done, certainly this parent is finished
 
3298
        nodes_to_annotate = []
 
3299
        for child in self._pending_children.pop(revision_id, []):
 
3300
            self._check_parents(child, nodes_to_annotate)
 
3301
        return nodes_to_annotate
3459
3302
 
3460
3303
    def _get_build_graph(self, key):
3461
3304
        """Get the graphs for building texts and annotations.
3466
3309
        fulltext.)
3467
3310
 
3468
3311
        :return: A list of (key, index_memo) records, suitable for
3469
 
            passing to read_records_iter to start reading in the raw data from
 
3312
            passing to read_records_iter to start reading in the raw data fro/
3470
3313
            the pack file.
3471
3314
        """
 
3315
        if key in self._annotated_lines:
 
3316
            # Nothing to do
 
3317
            return []
3472
3318
        pending = set([key])
3473
3319
        records = []
3474
 
        ann_keys = set()
3475
 
        self._num_needed_children[key] = 1
 
3320
        generation = 0
 
3321
        kept_generation = 0
3476
3322
        while pending:
3477
3323
            # get all pending nodes
 
3324
            generation += 1
3478
3325
            this_iteration = pending
3479
 
            build_details = self._vf._index.get_build_details(this_iteration)
 
3326
            build_details = self._knit._index.get_build_details(this_iteration)
3480
3327
            self._all_build_details.update(build_details)
3481
 
            # new_nodes = self._vf._index._get_entries(this_iteration)
 
3328
            # new_nodes = self._knit._index._get_entries(this_iteration)
3482
3329
            pending = set()
3483
3330
            for key, details in build_details.iteritems():
3484
 
                (index_memo, compression_parent, parent_keys,
 
3331
                (index_memo, compression_parent, parents,
3485
3332
                 record_details) = details
3486
 
                self._parent_map[key] = parent_keys
3487
 
                self._heads_provider = None
 
3333
                self._revision_id_graph[key] = parents
3488
3334
                records.append((key, index_memo))
3489
3335
                # Do we actually need to check _annotated_lines?
3490
 
                pending.update([p for p in parent_keys
3491
 
                                   if p not in self._all_build_details])
3492
 
                if parent_keys:
3493
 
                    for parent_key in parent_keys:
3494
 
                        if parent_key in self._num_needed_children:
3495
 
                            self._num_needed_children[parent_key] += 1
3496
 
                        else:
3497
 
                            self._num_needed_children[parent_key] = 1
 
3336
                pending.update(p for p in parents
 
3337
                                 if p not in self._all_build_details)
3498
3338
                if compression_parent:
3499
 
                    if compression_parent in self._num_compression_children:
3500
 
                        self._num_compression_children[compression_parent] += 1
3501
 
                    else:
3502
 
                        self._num_compression_children[compression_parent] = 1
 
3339
                    self._compression_children.setdefault(compression_parent,
 
3340
                        []).append(key)
 
3341
                if parents:
 
3342
                    for parent in parents:
 
3343
                        self._annotate_children.setdefault(parent,
 
3344
                            []).append(key)
 
3345
                    num_gens = generation - kept_generation
 
3346
                    if ((num_gens >= self._generations_until_keep)
 
3347
                        and len(parents) > 1):
 
3348
                        kept_generation = generation
 
3349
                        self._nodes_to_keep_annotations.add(key)
3503
3350
 
3504
3351
            missing_versions = this_iteration.difference(build_details.keys())
3505
 
            if missing_versions:
3506
 
                for key in missing_versions:
3507
 
                    if key in self._parent_map and key in self._text_cache:
3508
 
                        # We already have this text ready, we just need to
3509
 
                        # yield it later so we get it annotated
3510
 
                        ann_keys.add(key)
3511
 
                        parent_keys = self._parent_map[key]
3512
 
                        for parent_key in parent_keys:
3513
 
                            if parent_key in self._num_needed_children:
3514
 
                                self._num_needed_children[parent_key] += 1
3515
 
                            else:
3516
 
                                self._num_needed_children[parent_key] = 1
3517
 
                        pending.update([p for p in parent_keys
3518
 
                                           if p not in self._all_build_details])
3519
 
                    else:
3520
 
                        raise errors.RevisionNotPresent(key, self._vf)
 
3352
            self._ghosts.update(missing_versions)
 
3353
            for missing_version in missing_versions:
 
3354
                # add a key, no parents
 
3355
                self._revision_id_graph[missing_version] = ()
 
3356
                pending.discard(missing_version) # don't look for it
 
3357
        if self._ghosts.intersection(self._compression_children):
 
3358
            raise KnitCorrupt(
 
3359
                "We cannot have nodes which have a ghost compression parent:\n"
 
3360
                "ghosts: %r\n"
 
3361
                "compression children: %r"
 
3362
                % (self._ghosts, self._compression_children))
 
3363
        # Cleanout anything that depends on a ghost so that we don't wait for
 
3364
        # the ghost to show up
 
3365
        for node in self._ghosts:
 
3366
            if node in self._annotate_children:
 
3367
                # We won't be building this node
 
3368
                del self._annotate_children[node]
3521
3369
        # Generally we will want to read the records in reverse order, because
3522
3370
        # we find the parent nodes after the children
3523
3371
        records.reverse()
3524
 
        return records, ann_keys
3525
 
 
3526
 
    def _get_needed_texts(self, key, pb=None):
3527
 
        # if True or len(self._vf._fallback_vfs) > 0:
3528
 
        if len(self._vf._fallback_vfs) > 0:
3529
 
            # If we have fallbacks, go to the generic path
3530
 
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
3531
 
                yield v
3532
 
            return
3533
 
        while True:
3534
 
            try:
3535
 
                records, ann_keys = self._get_build_graph(key)
3536
 
                for idx, (sub_key, text, num_lines) in enumerate(
3537
 
                                                self._extract_texts(records)):
3538
 
                    if pb is not None:
3539
 
                        pb.update('annotating', idx, len(records))
3540
 
                    yield sub_key, text, num_lines
3541
 
                for sub_key in ann_keys:
3542
 
                    text = self._text_cache[sub_key]
3543
 
                    num_lines = len(text) # bad assumption
3544
 
                    yield sub_key, text, num_lines
3545
 
                return
3546
 
            except errors.RetryWithNewPacks, e:
3547
 
                self._vf._access.reload_or_raise(e)
3548
 
                # The cached build_details are no longer valid
3549
 
                self._all_build_details.clear()
3550
 
 
3551
 
    def _cache_delta_blocks(self, key, compression_parent, delta, lines):
3552
 
        parent_lines = self._text_cache[compression_parent]
3553
 
        blocks = list(KnitContent.get_line_delta_blocks(delta, parent_lines, lines))
3554
 
        self._matching_blocks[(key, compression_parent)] = blocks
3555
 
 
3556
 
    def _expand_record(self, key, parent_keys, compression_parent, record,
3557
 
                       record_details):
3558
 
        delta = None
3559
 
        if compression_parent:
3560
 
            if compression_parent not in self._content_objects:
3561
 
                # Waiting for the parent
3562
 
                self._pending_deltas.setdefault(compression_parent, []).append(
3563
 
                    (key, parent_keys, record, record_details))
3564
 
                return None
3565
 
            # We have the basis parent, so expand the delta
3566
 
            num = self._num_compression_children[compression_parent]
3567
 
            num -= 1
3568
 
            if num == 0:
3569
 
                base_content = self._content_objects.pop(compression_parent)
3570
 
                self._num_compression_children.pop(compression_parent)
3571
 
            else:
3572
 
                self._num_compression_children[compression_parent] = num
3573
 
                base_content = self._content_objects[compression_parent]
3574
 
            # It is tempting to want to copy_base_content=False for the last
3575
 
            # child object. However, whenever noeol=False,
3576
 
            # self._text_cache[parent_key] is content._lines. So mutating it
3577
 
            # gives very bad results.
3578
 
            # The alternative is to copy the lines into text cache, but then we
3579
 
            # are copying anyway, so just do it here.
3580
 
            content, delta = self._vf._factory.parse_record(
3581
 
                key, record, record_details, base_content,
3582
 
                copy_base_content=True)
3583
 
        else:
3584
 
            # Fulltext record
3585
 
            content, _ = self._vf._factory.parse_record(
3586
 
                key, record, record_details, None)
3587
 
        if self._num_compression_children.get(key, 0) > 0:
3588
 
            self._content_objects[key] = content
3589
 
        lines = content.text()
3590
 
        self._text_cache[key] = lines
3591
 
        if delta is not None:
3592
 
            self._cache_delta_blocks(key, compression_parent, delta, lines)
3593
 
        return lines
3594
 
 
3595
 
    def _get_parent_annotations_and_matches(self, key, text, parent_key):
3596
 
        """Get the list of annotations for the parent, and the matching lines.
3597
 
 
3598
 
        :param text: The opaque value given by _get_needed_texts
3599
 
        :param parent_key: The key for the parent text
3600
 
        :return: (parent_annotations, matching_blocks)
3601
 
            parent_annotations is a list as long as the number of lines in
3602
 
                parent
3603
 
            matching_blocks is a list of (parent_idx, text_idx, len) tuples
3604
 
                indicating which lines match between the two texts
3605
 
        """
3606
 
        block_key = (key, parent_key)
3607
 
        if block_key in self._matching_blocks:
3608
 
            blocks = self._matching_blocks.pop(block_key)
3609
 
            parent_annotations = self._annotations_cache[parent_key]
3610
 
            return parent_annotations, blocks
3611
 
        return annotate.Annotator._get_parent_annotations_and_matches(self,
3612
 
            key, text, parent_key)
3613
 
 
3614
 
    def _process_pending(self, key):
3615
 
        """The content for 'key' was just processed.
3616
 
 
3617
 
        Determine if there is any more pending work to be processed.
3618
 
        """
3619
 
        to_return = []
3620
 
        if key in self._pending_deltas:
3621
 
            compression_parent = key
3622
 
            children = self._pending_deltas.pop(key)
3623
 
            for child_key, parent_keys, record, record_details in children:
3624
 
                lines = self._expand_record(child_key, parent_keys,
3625
 
                                            compression_parent,
3626
 
                                            record, record_details)
3627
 
                if self._check_ready_for_annotations(child_key, parent_keys):
3628
 
                    to_return.append(child_key)
3629
 
        # Also check any children that are waiting for this parent to be
3630
 
        # annotation ready
3631
 
        if key in self._pending_annotation:
3632
 
            children = self._pending_annotation.pop(key)
3633
 
            to_return.extend([c for c, p_keys in children
3634
 
                              if self._check_ready_for_annotations(c, p_keys)])
3635
 
        return to_return
3636
 
 
3637
 
    def _check_ready_for_annotations(self, key, parent_keys):
3638
 
        """return true if this text is ready to be yielded.
3639
 
 
3640
 
        Otherwise, this will return False, and queue the text into
3641
 
        self._pending_annotation
3642
 
        """
3643
 
        for parent_key in parent_keys:
3644
 
            if parent_key not in self._annotations_cache:
3645
 
                # still waiting on at least one parent text, so queue it up
3646
 
                # Note that if there are multiple parents, we need to wait
3647
 
                # for all of them.
3648
 
                self._pending_annotation.setdefault(parent_key,
3649
 
                    []).append((key, parent_keys))
3650
 
                return False
3651
 
        return True
3652
 
 
3653
 
    def _extract_texts(self, records):
3654
 
        """Extract the various texts needed based on records"""
 
3372
        return records
 
3373
 
 
3374
    def _annotate_records(self, records):
 
3375
        """Build the annotations for the listed records."""
3655
3376
        # We iterate in the order read, rather than a strict order requested
3656
3377
        # However, process what we can, and put off to the side things that
3657
3378
        # still need parents, cleaning them up when those parents are
3658
3379
        # processed.
3659
 
        # Basic data flow:
3660
 
        #   1) As 'records' are read, see if we can expand these records into
3661
 
        #      Content objects (and thus lines)
3662
 
        #   2) If a given line-delta is waiting on its compression parent, it
3663
 
        #      gets queued up into self._pending_deltas, otherwise we expand
3664
 
        #      it, and put it into self._text_cache and self._content_objects
3665
 
        #   3) If we expanded the text, we will then check to see if all
3666
 
        #      parents have also been processed. If so, this text gets yielded,
3667
 
        #      else this record gets set aside into pending_annotation
3668
 
        #   4) Further, if we expanded the text in (2), we will then check to
3669
 
        #      see if there are any children in self._pending_deltas waiting to
3670
 
        #      also be processed. If so, we go back to (2) for those
3671
 
        #   5) Further again, if we yielded the text, we can then check if that
3672
 
        #      'unlocks' any of the texts in pending_annotations, which should
3673
 
        #      then get yielded as well
3674
 
        # Note that both steps 4 and 5 are 'recursive' in that unlocking one
3675
 
        # compression child could unlock yet another, and yielding a fulltext
3676
 
        # will also 'unlock' the children that are waiting on that annotation.
3677
 
        # (Though also, unlocking 1 parent's fulltext, does not unlock a child
3678
 
        # if other parents are also waiting.)
3679
 
        # We want to yield content before expanding child content objects, so
3680
 
        # that we know when we can re-use the content lines, and the annotation
3681
 
        # code can know when it can stop caching fulltexts, as well.
3682
 
 
3683
 
        # Children that are missing their compression parent
3684
 
        pending_deltas = {}
3685
 
        for (key, record, digest) in self._vf._read_records_iter(records):
3686
 
            # ghosts?
3687
 
            details = self._all_build_details[key]
3688
 
            (_, compression_parent, parent_keys, record_details) = details
3689
 
            lines = self._expand_record(key, parent_keys, compression_parent,
3690
 
                                        record, record_details)
3691
 
            if lines is None:
3692
 
                # Pending delta should be queued up
 
3380
        for (rev_id, record,
 
3381
             digest) in self._knit._read_records_iter(records):
 
3382
            if rev_id in self._annotated_lines:
3693
3383
                continue
3694
 
            # At this point, we may be able to yield this content, if all
3695
 
            # parents are also finished
3696
 
            yield_this_text = self._check_ready_for_annotations(key,
3697
 
                                                                parent_keys)
3698
 
            if yield_this_text:
3699
 
                # All parents present
3700
 
                yield key, lines, len(lines)
3701
 
            to_process = self._process_pending(key)
3702
 
            while to_process:
3703
 
                this_process = to_process
3704
 
                to_process = []
3705
 
                for key in this_process:
3706
 
                    lines = self._text_cache[key]
3707
 
                    yield key, lines, len(lines)
3708
 
                    to_process.extend(self._process_pending(key))
 
3384
            parent_ids = self._revision_id_graph[rev_id]
 
3385
            parent_ids = [p for p in parent_ids if p not in self._ghosts]
 
3386
            details = self._all_build_details[rev_id]
 
3387
            (index_memo, compression_parent, parents,
 
3388
             record_details) = details
 
3389
            nodes_to_annotate = []
 
3390
            # TODO: Remove the punning between compression parents, and
 
3391
            #       parent_ids, we should be able to do this without assuming
 
3392
            #       the build order
 
3393
            if len(parent_ids) == 0:
 
3394
                # There are no parents for this node, so just add it
 
3395
                # TODO: This probably needs to be decoupled
 
3396
                fulltext_content, delta = self._knit._factory.parse_record(
 
3397
                    rev_id, record, record_details, None)
 
3398
                fulltext = self._add_fulltext_content(rev_id, fulltext_content)
 
3399
                nodes_to_annotate.extend(self._add_annotation(rev_id, fulltext,
 
3400
                    parent_ids, left_matching_blocks=None))
 
3401
            else:
 
3402
                child = (rev_id, parent_ids, record)
 
3403
                # Check if all the parents are present
 
3404
                self._check_parents(child, nodes_to_annotate)
 
3405
            while nodes_to_annotate:
 
3406
                # Should we use a queue here instead of a stack?
 
3407
                (rev_id, parent_ids, record) = nodes_to_annotate.pop()
 
3408
                (index_memo, compression_parent, parents,
 
3409
                 record_details) = self._all_build_details[rev_id]
 
3410
                blocks = None
 
3411
                if compression_parent is not None:
 
3412
                    comp_children = self._compression_children[compression_parent]
 
3413
                    if rev_id not in comp_children:
 
3414
                        raise AssertionError("%r not in compression children %r"
 
3415
                            % (rev_id, comp_children))
 
3416
                    # If there is only 1 child, it is safe to reuse this
 
3417
                    # content
 
3418
                    reuse_content = (len(comp_children) == 1
 
3419
                        and compression_parent not in
 
3420
                            self._nodes_to_keep_annotations)
 
3421
                    if reuse_content:
 
3422
                        # Remove it from the cache since it will be changing
 
3423
                        parent_fulltext_content = self._fulltext_contents.pop(compression_parent)
 
3424
                        # Make sure to copy the fulltext since it might be
 
3425
                        # modified
 
3426
                        parent_fulltext = list(parent_fulltext_content.text())
 
3427
                    else:
 
3428
                        parent_fulltext_content = self._fulltext_contents[compression_parent]
 
3429
                        parent_fulltext = parent_fulltext_content.text()
 
3430
                    comp_children.remove(rev_id)
 
3431
                    fulltext_content, delta = self._knit._factory.parse_record(
 
3432
                        rev_id, record, record_details,
 
3433
                        parent_fulltext_content,
 
3434
                        copy_base_content=(not reuse_content))
 
3435
                    fulltext = self._add_fulltext_content(rev_id,
 
3436
                                                          fulltext_content)
 
3437
                    if compression_parent == parent_ids[0]:
 
3438
                        # the compression_parent is the left parent, so we can
 
3439
                        # re-use the delta
 
3440
                        blocks = KnitContent.get_line_delta_blocks(delta,
 
3441
                                parent_fulltext, fulltext)
 
3442
                else:
 
3443
                    fulltext_content = self._knit._factory.parse_fulltext(
 
3444
                        record, rev_id)
 
3445
                    fulltext = self._add_fulltext_content(rev_id,
 
3446
                        fulltext_content)
 
3447
                nodes_to_annotate.extend(
 
3448
                    self._add_annotation(rev_id, fulltext, parent_ids,
 
3449
                                     left_matching_blocks=blocks))
 
3450
 
 
3451
    def _get_heads_provider(self):
 
3452
        """Create a heads provider for resolving ancestry issues."""
 
3453
        if self._heads_provider is not None:
 
3454
            return self._heads_provider
 
3455
        parent_provider = _mod_graph.DictParentsProvider(
 
3456
            self._revision_id_graph)
 
3457
        graph_obj = _mod_graph.Graph(parent_provider)
 
3458
        head_cache = _mod_graph.FrozenHeadsCache(graph_obj)
 
3459
        self._heads_provider = head_cache
 
3460
        return head_cache
 
3461
 
 
3462
    def annotate(self, key):
 
3463
        """Return the annotated fulltext at the given key.
 
3464
 
 
3465
        :param key: The key to annotate.
 
3466
        """
 
3467
        if len(self._knit._fallback_vfs) > 0:
 
3468
            # stacked knits can't use the fast path at present.
 
3469
            return self._simple_annotate(key)
 
3470
        while True:
 
3471
            try:
 
3472
                records = self._get_build_graph(key)
 
3473
                if key in self._ghosts:
 
3474
                    raise errors.RevisionNotPresent(key, self._knit)
 
3475
                self._annotate_records(records)
 
3476
                return self._annotated_lines[key]
 
3477
            except errors.RetryWithNewPacks, e:
 
3478
                self._knit._access.reload_or_raise(e)
 
3479
                # The cached build_details are no longer valid
 
3480
                self._all_build_details.clear()
 
3481
 
 
3482
    def _simple_annotate(self, key):
 
3483
        """Return annotated fulltext, rediffing from the full texts.
 
3484
 
 
3485
        This is slow but makes no assumptions about the repository
 
3486
        being able to produce line deltas.
 
3487
        """
 
3488
        # TODO: this code generates a parent maps of present ancestors; it
 
3489
        # could be split out into a separate method, and probably should use
 
3490
        # iter_ancestry instead. -- mbp and robertc 20080704
 
3491
        graph = _mod_graph.Graph(self._knit)
 
3492
        head_cache = _mod_graph.FrozenHeadsCache(graph)
 
3493
        search = graph._make_breadth_first_searcher([key])
 
3494
        keys = set()
 
3495
        while True:
 
3496
            try:
 
3497
                present, ghosts = search.next_with_ghosts()
 
3498
            except StopIteration:
 
3499
                break
 
3500
            keys.update(present)
 
3501
        parent_map = self._knit.get_parent_map(keys)
 
3502
        parent_cache = {}
 
3503
        reannotate = annotate.reannotate
 
3504
        for record in self._knit.get_record_stream(keys, 'topological', True):
 
3505
            key = record.key
 
3506
            fulltext = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
 
3507
            parents = parent_map[key]
 
3508
            if parents is not None:
 
3509
                parent_lines = [parent_cache[parent] for parent in parent_map[key]]
 
3510
            else:
 
3511
                parent_lines = []
 
3512
            parent_cache[key] = list(
 
3513
                reannotate(parent_lines, fulltext, key, None, head_cache))
 
3514
        try:
 
3515
            return parent_cache[key]
 
3516
        except KeyError, e:
 
3517
            raise errors.RevisionNotPresent(key, self._knit)
 
3518
 
3709
3519
 
3710
3520
try:
3711
 
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
3712
 
except ImportError, e:
3713
 
    osutils.failed_to_load_extension(e)
 
3521
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
 
3522
except ImportError:
3714
3523
    from bzrlib._knit_load_data_py import _load_data_py as _load_data