← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-01-14 00:01:32 UTC
  • mfrom: (4957.1.1 jam-integration)
  • Revision ID: pqm@pqm.ubuntu.com-20100114000132-3p3rabnonjw3gzqb
(jam) Merge bzr.stable, bringing in bug fixes #175839, #504390

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
53
53
 
54
54
 
55
55
from cStringIO import StringIO
56
 
from itertools import izip, chain
 
56
from itertools import izip
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,
72
73
    trace,
73
74
    tsort,
74
75
    tuned_gzip,
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
 
909
908
            # indexes can't directly store that, so we give them
910
909
            # an empty tuple instead.
911
910
            parents = ()
 
911
        line_bytes = ''.join(lines)
912
912
        return self._add(key, lines, parents,
913
 
            parent_texts, left_matching_blocks, nostore_sha, random_id)
 
913
            parent_texts, left_matching_blocks, nostore_sha, random_id,
 
914
            line_bytes=line_bytes)
 
915
 
 
916
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
 
917
        """See VersionedFiles._add_text()."""
 
918
        self._index._check_write_ok()
 
919
        self._check_add(key, None, random_id, check_content=False)
 
920
        if text.__class__ is not str:
 
921
            raise errors.BzrBadParameterUnicode("text")
 
922
        if parents is None:
 
923
            # The caller might pass None if there is no graph data, but kndx
 
924
            # indexes can't directly store that, so we give them
 
925
            # an empty tuple instead.
 
926
            parents = ()
 
927
        return self._add(key, None, parents,
 
928
            None, None, nostore_sha, random_id,
 
929
            line_bytes=text)
914
930
 
915
931
    def _add(self, key, lines, parents, parent_texts,
916
 
        left_matching_blocks, nostore_sha, random_id):
 
932
        left_matching_blocks, nostore_sha, random_id,
 
933
        line_bytes):
917
934
        """Add a set of lines on top of version specified by parents.
918
935
 
919
936
        Any versions not present will be converted into ghosts.
 
937
 
 
938
        :param lines: A list of strings where each one is a single line (has a
 
939
            single newline at the end of the string) This is now optional
 
940
            (callers can pass None). It is left in its location for backwards
 
941
            compatibility. It should ''.join(lines) must == line_bytes
 
942
        :param line_bytes: A single string containing the content
 
943
 
 
944
        We pass both lines and line_bytes because different routes bring the
 
945
        values to this function. And for memory efficiency, we don't want to
 
946
        have to split/join on-demand.
920
947
        """
921
948
        # first thing, if the content is something we don't need to store, find
922
949
        # that out.
923
 
        line_bytes = ''.join(lines)
924
950
        digest = sha_string(line_bytes)
925
951
        if nostore_sha == digest:
926
952
            raise errors.ExistingContent
947
973
 
948
974
        text_length = len(line_bytes)
949
975
        options = []
950
 
        if lines:
951
 
            if lines[-1][-1] != '\n':
952
 
                # copy the contents of lines.
 
976
        no_eol = False
 
977
        # Note: line_bytes is not modified to add a newline, that is tracked
 
978
        #       via the no_eol flag. 'lines' *is* modified, because that is the
 
979
        #       general values needed by the Content code.
 
980
        if line_bytes and line_bytes[-1] != '\n':
 
981
            options.append('no-eol')
 
982
            no_eol = True
 
983
            # Copy the existing list, or create a new one
 
984
            if lines is None:
 
985
                lines = osutils.split_lines(line_bytes)
 
986
            else:
953
987
                lines = lines[:]
954
 
                options.append('no-eol')
955
 
                lines[-1] = lines[-1] + '\n'
956
 
                line_bytes += '\n'
 
988
            # Replace the last line with one that ends in a final newline
 
989
            lines[-1] = lines[-1] + '\n'
 
990
        if lines is None:
 
991
            lines = osutils.split_lines(line_bytes)
957
992
 
958
993
        for element in key[:-1]:
959
 
            if type(element) != str:
 
994
            if type(element) is not str:
960
995
                raise TypeError("key contains non-strings: %r" % (key,))
961
996
        if key[-1] is None:
962
997
            key = key[:-1] + ('sha1:' + digest,)
963
 
        elif type(key[-1]) != str:
 
998
        elif type(key[-1]) is not str:
964
999
                raise TypeError("key contains non-strings: %r" % (key,))
965
1000
        # Knit hunks are still last-element only
966
1001
        version_id = key[-1]
967
1002
        content = self._factory.make(lines, version_id)
968
 
        if 'no-eol' in options:
 
1003
        if no_eol:
969
1004
            # Hint to the content object that its text() call should strip the
970
1005
            # EOL.
971
1006
            content._should_strip_eol = True
986
1021
            if self._factory.__class__ is KnitPlainFactory:
987
1022
                # Use the already joined bytes saving iteration time in
988
1023
                # _record_to_data.
 
1024
                dense_lines = [line_bytes]
 
1025
                if no_eol:
 
1026
                    dense_lines.append('\n')
989
1027
                size, bytes = self._record_to_data(key, digest,
990
 
                    lines, [line_bytes])
 
1028
                    lines, dense_lines)
991
1029
            else:
992
1030
                # get mixed annotation + content and feed it into the
993
1031
                # serialiser.
1005
1043
        """See VersionedFiles.annotate."""
1006
1044
        return self._factory.annotate(self, key)
1007
1045
 
1008
 
    def check(self, progress_bar=None):
 
1046
    def get_annotator(self):
 
1047
        return _KnitAnnotator(self)
 
1048
 
 
1049
    def check(self, progress_bar=None, keys=None):
1009
1050
        """See VersionedFiles.check()."""
 
1051
        if keys is None:
 
1052
            return self._logical_check()
 
1053
        else:
 
1054
            # At the moment, check does not extra work over get_record_stream
 
1055
            return self.get_record_stream(keys, 'unordered', True)
 
1056
 
 
1057
    def _logical_check(self):
1010
1058
        # This doesn't actually test extraction of everything, but that will
1011
1059
        # impact 'bzr check' substantially, and needs to be integrated with
1012
1060
        # care. However, it does check for the obvious problem of a delta with
1143
1191
        generator = _VFContentMapGenerator(self, [key])
1144
1192
        return generator._get_content(key)
1145
1193
 
 
1194
    def get_known_graph_ancestry(self, keys):
 
1195
        """Get a KnownGraph instance with the ancestry of keys."""
 
1196
        parent_map, missing_keys = self._index.find_ancestry(keys)
 
1197
        for fallback in self._fallback_vfs:
 
1198
            if not missing_keys:
 
1199
                break
 
1200
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
 
1201
                                                missing_keys)
 
1202
            parent_map.update(f_parent_map)
 
1203
            missing_keys = f_missing_keys
 
1204
        kg = _mod_graph.KnownGraph(parent_map)
 
1205
        return kg
 
1206
 
1146
1207
    def get_parent_map(self, keys):
1147
1208
        """Get a map of the graph parents of keys.
1148
1209
 
1449
1510
                                                                non_local_keys,
1450
1511
                                                                positions):
1451
1512
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1452
 
                                                   global_map)
 
1513
                                                   global_map,
 
1514
                                                   ordering=ordering)
1453
1515
                for record in generator.get_record_stream():
1454
1516
                    yield record
1455
1517
        else:
1457
1519
                if source is parent_maps[0]:
1458
1520
                    # this KnitVersionedFiles
1459
1521
                    records = [(key, positions[key][1]) for key in keys]
1460
 
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
 
1522
                    for key, raw_data in self._read_records_iter_unchecked(records):
1461
1523
                        (record_details, index_memo, _) = positions[key]
1462
1524
                        yield KnitContentFactory(key, global_map[key],
1463
 
                            record_details, sha1, raw_data, self._factory.annotated, None)
 
1525
                            record_details, None, raw_data, self._factory.annotated, None)
1464
1526
                else:
1465
1527
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1466
1528
                    for record in vf.get_record_stream(keys, ordering,
1535
1597
        # key = basis_parent, value = index entry to add
1536
1598
        buffered_index_entries = {}
1537
1599
        for record in stream:
 
1600
            kind = record.storage_kind
 
1601
            if kind.startswith('knit-') and kind.endswith('-gz'):
 
1602
                # Check that the ID in the header of the raw knit bytes matches
 
1603
                # the record metadata.
 
1604
                raw_data = record._raw_record
 
1605
                df, rec = self._parse_record_header(record.key, raw_data)
 
1606
                df.close()
1538
1607
            buffered = False
1539
1608
            parents = record.parents
1540
1609
            if record.storage_kind in delta_types:
1642
1711
            # There were index entries buffered at the end of the stream,
1643
1712
            # So these need to be added (if the index supports holding such
1644
1713
            # entries for later insertion)
 
1714
            all_entries = []
1645
1715
            for key in buffered_index_entries:
1646
1716
                index_entries = buffered_index_entries[key]
1647
 
                self._index.add_records(index_entries,
1648
 
                    missing_compression_parents=True)
 
1717
                all_entries.extend(index_entries)
 
1718
            self._index.add_records(
 
1719
                all_entries, missing_compression_parents=True)
1649
1720
 
1650
1721
    def get_missing_compression_parent_keys(self):
1651
1722
        """Return an iterable of keys of missing compression parents.
1920
1991
            function spends less time resizing the final string.
1921
1992
        :return: (len, a StringIO instance with the raw data ready to read.)
1922
1993
        """
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))
 
1994
        chunks = ["version %s %d %s\n" % (key[-1], len(lines), digest)]
 
1995
        chunks.extend(dense_lines or lines)
 
1996
        chunks.append("end %s\n" % key[-1])
 
1997
        for chunk in chunks:
 
1998
            if type(chunk) is not str:
 
1999
                raise AssertionError(
 
2000
                    'data must be plain bytes was %s' % type(chunk))
1935
2001
        if lines and lines[-1][-1] != '\n':
1936
2002
            raise ValueError('corrupt lines value %r' % lines)
1937
 
        compressed_bytes = tuned_gzip.bytes_to_gzip(bytes)
 
2003
        compressed_bytes = tuned_gzip.chunks_to_gzip(chunks)
1938
2004
        return len(compressed_bytes), compressed_bytes
1939
2005
 
1940
2006
    def _split_header(self, line):
1958
2024
class _ContentMapGenerator(object):
1959
2025
    """Generate texts or expose raw deltas for a set of texts."""
1960
2026
 
 
2027
    def __init__(self, ordering='unordered'):
 
2028
        self._ordering = ordering
 
2029
 
1961
2030
    def _get_content(self, key):
1962
2031
        """Get the content object for key."""
1963
2032
        # Note that _get_content is only called when the _ContentMapGenerator
1997
2066
            # Loop over fallback repositories asking them for texts - ignore
1998
2067
            # any missing from a particular fallback.
1999
2068
            for record in source.get_record_stream(missing_keys,
2000
 
                'unordered', True):
 
2069
                self._ordering, True):
2001
2070
                if record.storage_kind == 'absent':
2002
2071
                    # Not in thie particular stream, may be in one of the
2003
2072
                    # other fallback vfs objects.
2005
2074
                missing_keys.remove(record.key)
2006
2075
                yield record
2007
2076
 
2008
 
        self._raw_record_map = self.vf._get_record_map_unparsed(self.keys,
2009
 
            allow_missing=True)
 
2077
        if self._raw_record_map is None:
 
2078
            raise AssertionError('_raw_record_map should have been filled')
2010
2079
        first = True
2011
2080
        for key in self.keys:
2012
2081
            if key in self.nonlocal_keys:
2135
2204
    """Content map generator reading from a VersionedFiles object."""
2136
2205
 
2137
2206
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2138
 
        global_map=None, raw_record_map=None):
 
2207
        global_map=None, raw_record_map=None, ordering='unordered'):
2139
2208
        """Create a _ContentMapGenerator.
2140
2209
 
2141
2210
        :param versioned_files: The versioned files that the texts are being
2149
2218
        :param raw_record_map: A unparsed raw record map to use for answering
2150
2219
            contents.
2151
2220
        """
 
2221
        _ContentMapGenerator.__init__(self, ordering=ordering)
2152
2222
        # The vf to source data from
2153
2223
        self.vf = versioned_files
2154
2224
        # The keys desired
2298
2368
    FLAGS is a comma separated list of flags about the record. Values include
2299
2369
        no-eol, line-delta, fulltext.
2300
2370
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2301
 
        that the the compressed data starts at.
 
2371
        that the compressed data starts at.
2302
2372
    LENGTH is the ascii representation of the length of the data file.
2303
2373
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2304
2374
        REVISION_ID.
2375
2445
                    line = "\n%s %s %s %s %s :" % (
2376
2446
                        key[-1], ','.join(options), pos, size,
2377
2447
                        self._dictionary_compress(parents))
2378
 
                    if type(line) != str:
 
2448
                    if type(line) is not str:
2379
2449
                        raise AssertionError(
2380
2450
                            'data must be utf8 was %s' % type(line))
2381
2451
                    lines.append(line)
2513
2583
        except KeyError:
2514
2584
            raise RevisionNotPresent(key, self)
2515
2585
 
 
2586
    def find_ancestry(self, keys):
 
2587
        """See CombinedGraphIndex.find_ancestry()"""
 
2588
        prefixes = set(key[:-1] for key in keys)
 
2589
        self._load_prefixes(prefixes)
 
2590
        result = {}
 
2591
        parent_map = {}
 
2592
        missing_keys = set()
 
2593
        pending_keys = list(keys)
 
2594
        # This assumes that keys will not reference parents in a different
 
2595
        # prefix, which is accurate so far.
 
2596
        while pending_keys:
 
2597
            key = pending_keys.pop()
 
2598
            if key in parent_map:
 
2599
                continue
 
2600
            prefix = key[:-1]
 
2601
            try:
 
2602
                suffix_parents = self._kndx_cache[prefix][0][key[-1]][4]
 
2603
            except KeyError:
 
2604
                missing_keys.add(key)
 
2605
            else:
 
2606
                parent_keys = tuple([prefix + (suffix,)
 
2607
                                     for suffix in suffix_parents])
 
2608
                parent_map[key] = parent_keys
 
2609
                pending_keys.extend([p for p in parent_keys
 
2610
                                        if p not in parent_map])
 
2611
        return parent_map, missing_keys
 
2612
 
2516
2613
    def get_parent_map(self, keys):
2517
2614
        """Get a map of the parents of keys.
2518
2615
 
2570
2667
        result = set()
2571
2668
        # Identify all key prefixes.
2572
2669
        # XXX: A bit hacky, needs polish.
2573
 
        if type(self._mapper) == ConstantMapper:
 
2670
        if type(self._mapper) is ConstantMapper:
2574
2671
            prefixes = [()]
2575
2672
        else:
2576
2673
            relpaths = set()
2608
2705
                    del self._history
2609
2706
                except NoSuchFile:
2610
2707
                    self._kndx_cache[prefix] = ({}, [])
2611
 
                    if type(self._mapper) == ConstantMapper:
 
2708
                    if type(self._mapper) is ConstantMapper:
2612
2709
                        # preserve behaviour for revisions.kndx etc.
2613
2710
                        self._init_index(path)
2614
2711
                    del self._cache
2688
2785
        return key[:-1], key[-1]
2689
2786
 
2690
2787
 
 
2788
class _KeyRefs(object):
 
2789
 
 
2790
    def __init__(self, track_new_keys=False):
 
2791
        # dict mapping 'key' to 'set of keys referring to that key'
 
2792
        self.refs = {}
 
2793
        if track_new_keys:
 
2794
            # set remembering all new keys
 
2795
            self.new_keys = set()
 
2796
        else:
 
2797
            self.new_keys = None
 
2798
 
 
2799
    def clear(self):
 
2800
        if self.refs:
 
2801
            self.refs.clear()
 
2802
        if self.new_keys:
 
2803
            self.new_keys.clear()
 
2804
 
 
2805
    def add_references(self, key, refs):
 
2806
        # Record the new references
 
2807
        for referenced in refs:
 
2808
            try:
 
2809
                needed_by = self.refs[referenced]
 
2810
            except KeyError:
 
2811
                needed_by = self.refs[referenced] = set()
 
2812
            needed_by.add(key)
 
2813
        # Discard references satisfied by the new key
 
2814
        self.add_key(key)
 
2815
 
 
2816
    def get_new_keys(self):
 
2817
        return self.new_keys
 
2818
    
 
2819
    def get_unsatisfied_refs(self):
 
2820
        return self.refs.iterkeys()
 
2821
 
 
2822
    def _satisfy_refs_for_key(self, key):
 
2823
        try:
 
2824
            del self.refs[key]
 
2825
        except KeyError:
 
2826
            # No keys depended on this key.  That's ok.
 
2827
            pass
 
2828
 
 
2829
    def add_key(self, key):
 
2830
        # satisfy refs for key, and remember that we've seen this key.
 
2831
        self._satisfy_refs_for_key(key)
 
2832
        if self.new_keys is not None:
 
2833
            self.new_keys.add(key)
 
2834
 
 
2835
    def satisfy_refs_for_keys(self, keys):
 
2836
        for key in keys:
 
2837
            self._satisfy_refs_for_key(key)
 
2838
 
 
2839
    def get_referrers(self):
 
2840
        result = set()
 
2841
        for referrers in self.refs.itervalues():
 
2842
            result.update(referrers)
 
2843
        return result
 
2844
 
 
2845
 
2691
2846
class _KnitGraphIndex(object):
2692
2847
    """A KnitVersionedFiles index layered on GraphIndex."""
2693
2848
 
2694
2849
    def __init__(self, graph_index, is_locked, deltas=False, parents=True,
2695
 
        add_callback=None):
 
2850
        add_callback=None, track_external_parent_refs=False):
2696
2851
        """Construct a KnitGraphIndex on a graph_index.
2697
2852
 
2698
2853
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
2706
2861
            [(node, value, node_refs), ...]
2707
2862
        :param is_locked: A callback, returns True if the index is locked and
2708
2863
            thus usable.
 
2864
        :param track_external_parent_refs: If True, record all external parent
 
2865
            references parents from added records.  These can be retrieved
 
2866
            later by calling get_missing_parents().
2709
2867
        """
2710
2868
        self._add_callback = add_callback
2711
2869
        self._graph_index = graph_index
2719
2877
        self.has_graph = parents
2720
2878
        self._is_locked = is_locked
2721
2879
        self._missing_compression_parents = set()
 
2880
        if track_external_parent_refs:
 
2881
            self._key_dependencies = _KeyRefs()
 
2882
        else:
 
2883
            self._key_dependencies = None
2722
2884
 
2723
2885
    def __repr__(self):
2724
2886
        return "%s(%r)" % (self.__class__.__name__, self._graph_index)
2748
2910
 
2749
2911
        keys = {}
2750
2912
        compression_parents = set()
 
2913
        key_dependencies = self._key_dependencies
2751
2914
        for (key, options, access_memo, parents) in records:
2752
2915
            if self._parents:
2753
2916
                parents = tuple(parents)
 
2917
                if key_dependencies is not None:
 
2918
                    key_dependencies.add_references(key, parents)
2754
2919
            index, pos, size = access_memo
2755
2920
            if 'no-eol' in options:
2756
2921
                value = 'N'
2780
2945
        if not random_id:
2781
2946
            present_nodes = self._get_entries(keys)
2782
2947
            for (index, key, value, node_refs) in present_nodes:
 
2948
                parents = node_refs[:1]
 
2949
                # Sometimes these are passed as a list rather than a tuple
 
2950
                passed = static_tuple.as_tuples(keys[key])
 
2951
                passed_parents = passed[1][:1]
2783
2952
                if (value[0] != keys[key][0][0] or
2784
 
                    node_refs[:1] != keys[key][1][:1]):
 
2953
                    parents != passed_parents):
 
2954
                    node_refs = static_tuple.as_tuples(node_refs)
2785
2955
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2786
 
                        ": %s %s" % ((value, node_refs), keys[key]))
 
2956
                        ": %s %s" % ((value, node_refs), passed))
2787
2957
                del keys[key]
2788
2958
        result = []
2789
2959
        if self._parents:
2818
2988
            new_missing = graph_index.external_references(ref_list_num=1)
2819
2989
            new_missing.difference_update(self.get_parent_map(new_missing))
2820
2990
            self._missing_compression_parents.update(new_missing)
 
2991
        if self._key_dependencies is not None:
 
2992
            # Add parent refs from graph_index (and discard parent refs that
 
2993
            # the graph_index has).
 
2994
            for node in graph_index.iter_all_entries():
 
2995
                self._key_dependencies.add_references(node[1], node[3][0])
2821
2996
 
2822
2997
    def get_missing_compression_parents(self):
2823
2998
        """Return the keys of missing compression parents.
2827
3002
        """
2828
3003
        return frozenset(self._missing_compression_parents)
2829
3004
 
 
3005
    def get_missing_parents(self):
 
3006
        """Return the keys of missing parents."""
 
3007
        # If updating this, you should also update
 
3008
        # groupcompress._GCGraphIndex.get_missing_parents
 
3009
        # We may have false positives, so filter those out.
 
3010
        self._key_dependencies.satisfy_refs_for_keys(
 
3011
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
 
3012
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
 
3013
 
2830
3014
    def _check_read(self):
2831
3015
        """raise if reads are not permitted."""
2832
3016
        if not self._is_locked():
2940
3124
            options.append('no-eol')
2941
3125
        return options
2942
3126
 
 
3127
    def find_ancestry(self, keys):
 
3128
        """See CombinedGraphIndex.find_ancestry()"""
 
3129
        return self._graph_index.find_ancestry(keys, 0)
 
3130
 
2943
3131
    def get_parent_map(self, keys):
2944
3132
        """Get a map of the parents of keys.
2945
3133
 
3032
3220
            opaque index memo. For _KnitKeyAccess the memo is (key, pos,
3033
3221
            length), where the key is the record key.
3034
3222
        """
3035
 
        if type(raw_data) != str:
 
3223
        if type(raw_data) is not str:
3036
3224
            raise AssertionError(
3037
3225
                'data must be plain bytes was %s' % type(raw_data))
3038
3226
        result = []
3121
3309
            length), where the index field is the write_index object supplied
3122
3310
            to the PackAccess object.
3123
3311
        """
3124
 
        if type(raw_data) != str:
 
3312
        if type(raw_data) is not str:
3125
3313
            raise AssertionError(
3126
3314
                'data must be plain bytes was %s' % type(raw_data))
3127
3315
        result = []
3240
3428
    recommended.
3241
3429
    """
3242
3430
    annotator = _KnitAnnotator(knit)
3243
 
    return iter(annotator.annotate(revision_id))
3244
 
 
3245
 
 
3246
 
class _KnitAnnotator(object):
 
3431
    return iter(annotator.annotate_flat(revision_id))
 
3432
 
 
3433
 
 
3434
class _KnitAnnotator(annotate.Annotator):
3247
3435
    """Build up the annotations for a text."""
3248
3436
 
3249
 
    def __init__(self, knit):
3250
 
        self._knit = knit
3251
 
 
3252
 
        # Content objects, differs from fulltexts because of how final newlines
3253
 
        # are treated by knits. the content objects here will always have a
3254
 
        # final newline
3255
 
        self._fulltext_contents = {}
3256
 
 
3257
 
        # Annotated lines of specific revisions
3258
 
        self._annotated_lines = {}
3259
 
 
3260
 
        # Track the raw data for nodes that we could not process yet.
3261
 
        # This maps the revision_id of the base to a list of children that will
3262
 
        # annotated from it.
3263
 
        self._pending_children = {}
3264
 
 
3265
 
        # Nodes which cannot be extracted
3266
 
        self._ghosts = set()
3267
 
 
3268
 
        # Track how many children this node has, so we know if we need to keep
3269
 
        # it
3270
 
        self._annotate_children = {}
3271
 
        self._compression_children = {}
 
3437
    def __init__(self, vf):
 
3438
        annotate.Annotator.__init__(self, vf)
 
3439
 
 
3440
        # TODO: handle Nodes which cannot be extracted
 
3441
        # self._ghosts = set()
 
3442
 
 
3443
        # Map from (key, parent_key) => matching_blocks, should be 'use once'
 
3444
        self._matching_blocks = {}
 
3445
 
 
3446
        # KnitContent objects
 
3447
        self._content_objects = {}
 
3448
        # The number of children that depend on this fulltext content object
 
3449
        self._num_compression_children = {}
 
3450
        # Delta records that need their compression parent before they can be
 
3451
        # expanded
 
3452
        self._pending_deltas = {}
 
3453
        # Fulltext records that are waiting for their parents fulltexts before
 
3454
        # they can be yielded for annotation
 
3455
        self._pending_annotation = {}
3272
3456
 
3273
3457
        self._all_build_details = {}
3274
 
        # The children => parent revision_id graph
3275
 
        self._revision_id_graph = {}
3276
 
 
3277
 
        self._heads_provider = None
3278
 
 
3279
 
        self._nodes_to_keep_annotations = set()
3280
 
        self._generations_until_keep = 100
3281
 
 
3282
 
    def set_generations_until_keep(self, value):
3283
 
        """Set the number of generations before caching a node.
3284
 
 
3285
 
        Setting this to -1 will cache every merge node, setting this higher
3286
 
        will cache fewer nodes.
3287
 
        """
3288
 
        self._generations_until_keep = value
3289
 
 
3290
 
    def _add_fulltext_content(self, revision_id, content_obj):
3291
 
        self._fulltext_contents[revision_id] = content_obj
3292
 
        # TODO: jam 20080305 It might be good to check the sha1digest here
3293
 
        return content_obj.text()
3294
 
 
3295
 
    def _check_parents(self, child, nodes_to_annotate):
3296
 
        """Check if all parents have been processed.
3297
 
 
3298
 
        :param child: A tuple of (rev_id, parents, raw_content)
3299
 
        :param nodes_to_annotate: If child is ready, add it to
3300
 
            nodes_to_annotate, otherwise put it back in self._pending_children
3301
 
        """
3302
 
        for parent_id in child[1]:
3303
 
            if (parent_id not in self._annotated_lines):
3304
 
                # This parent is present, but another parent is missing
3305
 
                self._pending_children.setdefault(parent_id,
3306
 
                                                  []).append(child)
3307
 
                break
3308
 
        else:
3309
 
            # This one is ready to be processed
3310
 
            nodes_to_annotate.append(child)
3311
 
 
3312
 
    def _add_annotation(self, revision_id, fulltext, parent_ids,
3313
 
                        left_matching_blocks=None):
3314
 
        """Add an annotation entry.
3315
 
 
3316
 
        All parents should already have been annotated.
3317
 
        :return: A list of children that now have their parents satisfied.
3318
 
        """
3319
 
        a = self._annotated_lines
3320
 
        annotated_parent_lines = [a[p] for p in parent_ids]
3321
 
        annotated_lines = list(annotate.reannotate(annotated_parent_lines,
3322
 
            fulltext, revision_id, left_matching_blocks,
3323
 
            heads_provider=self._get_heads_provider()))
3324
 
        self._annotated_lines[revision_id] = annotated_lines
3325
 
        for p in parent_ids:
3326
 
            ann_children = self._annotate_children[p]
3327
 
            ann_children.remove(revision_id)
3328
 
            if (not ann_children
3329
 
                and p not in self._nodes_to_keep_annotations):
3330
 
                del self._annotated_lines[p]
3331
 
                del self._all_build_details[p]
3332
 
                if p in self._fulltext_contents:
3333
 
                    del self._fulltext_contents[p]
3334
 
        # Now that we've added this one, see if there are any pending
3335
 
        # deltas to be done, certainly this parent is finished
3336
 
        nodes_to_annotate = []
3337
 
        for child in self._pending_children.pop(revision_id, []):
3338
 
            self._check_parents(child, nodes_to_annotate)
3339
 
        return nodes_to_annotate
3340
3458
 
3341
3459
    def _get_build_graph(self, key):
3342
3460
        """Get the graphs for building texts and annotations.
3347
3465
        fulltext.)
3348
3466
 
3349
3467
        :return: A list of (key, index_memo) records, suitable for
3350
 
            passing to read_records_iter to start reading in the raw data fro/
 
3468
            passing to read_records_iter to start reading in the raw data from
3351
3469
            the pack file.
3352
3470
        """
3353
 
        if key in self._annotated_lines:
3354
 
            # Nothing to do
3355
 
            return []
3356
3471
        pending = set([key])
3357
3472
        records = []
3358
 
        generation = 0
3359
 
        kept_generation = 0
 
3473
        ann_keys = set()
 
3474
        self._num_needed_children[key] = 1
3360
3475
        while pending:
3361
3476
            # get all pending nodes
3362
 
            generation += 1
3363
3477
            this_iteration = pending
3364
 
            build_details = self._knit._index.get_build_details(this_iteration)
 
3478
            build_details = self._vf._index.get_build_details(this_iteration)
3365
3479
            self._all_build_details.update(build_details)
3366
 
            # new_nodes = self._knit._index._get_entries(this_iteration)
 
3480
            # new_nodes = self._vf._index._get_entries(this_iteration)
3367
3481
            pending = set()
3368
3482
            for key, details in build_details.iteritems():
3369
 
                (index_memo, compression_parent, parents,
 
3483
                (index_memo, compression_parent, parent_keys,
3370
3484
                 record_details) = details
3371
 
                self._revision_id_graph[key] = parents
 
3485
                self._parent_map[key] = parent_keys
 
3486
                self._heads_provider = None
3372
3487
                records.append((key, index_memo))
3373
3488
                # Do we actually need to check _annotated_lines?
3374
 
                pending.update(p for p in parents
3375
 
                                 if p not in self._all_build_details)
 
3489
                pending.update([p for p in parent_keys
 
3490
                                   if p not in self._all_build_details])
 
3491
                if parent_keys:
 
3492
                    for parent_key in parent_keys:
 
3493
                        if parent_key in self._num_needed_children:
 
3494
                            self._num_needed_children[parent_key] += 1
 
3495
                        else:
 
3496
                            self._num_needed_children[parent_key] = 1
3376
3497
                if compression_parent:
3377
 
                    self._compression_children.setdefault(compression_parent,
3378
 
                        []).append(key)
3379
 
                if parents:
3380
 
                    for parent in parents:
3381
 
                        self._annotate_children.setdefault(parent,
3382
 
                            []).append(key)
3383
 
                    num_gens = generation - kept_generation
3384
 
                    if ((num_gens >= self._generations_until_keep)
3385
 
                        and len(parents) > 1):
3386
 
                        kept_generation = generation
3387
 
                        self._nodes_to_keep_annotations.add(key)
 
3498
                    if compression_parent in self._num_compression_children:
 
3499
                        self._num_compression_children[compression_parent] += 1
 
3500
                    else:
 
3501
                        self._num_compression_children[compression_parent] = 1
3388
3502
 
3389
3503
            missing_versions = this_iteration.difference(build_details.keys())
3390
 
            self._ghosts.update(missing_versions)
3391
 
            for missing_version in missing_versions:
3392
 
                # add a key, no parents
3393
 
                self._revision_id_graph[missing_version] = ()
3394
 
                pending.discard(missing_version) # don't look for it
3395
 
        if self._ghosts.intersection(self._compression_children):
3396
 
            raise KnitCorrupt(
3397
 
                "We cannot have nodes which have a ghost compression parent:\n"
3398
 
                "ghosts: %r\n"
3399
 
                "compression children: %r"
3400
 
                % (self._ghosts, self._compression_children))
3401
 
        # Cleanout anything that depends on a ghost so that we don't wait for
3402
 
        # the ghost to show up
3403
 
        for node in self._ghosts:
3404
 
            if node in self._annotate_children:
3405
 
                # We won't be building this node
3406
 
                del self._annotate_children[node]
 
3504
            if missing_versions:
 
3505
                for key in missing_versions:
 
3506
                    if key in self._parent_map and key in self._text_cache:
 
3507
                        # We already have this text ready, we just need to
 
3508
                        # yield it later so we get it annotated
 
3509
                        ann_keys.add(key)
 
3510
                        parent_keys = self._parent_map[key]
 
3511
                        for parent_key in parent_keys:
 
3512
                            if parent_key in self._num_needed_children:
 
3513
                                self._num_needed_children[parent_key] += 1
 
3514
                            else:
 
3515
                                self._num_needed_children[parent_key] = 1
 
3516
                        pending.update([p for p in parent_keys
 
3517
                                           if p not in self._all_build_details])
 
3518
                    else:
 
3519
                        raise errors.RevisionNotPresent(key, self._vf)
3407
3520
        # Generally we will want to read the records in reverse order, because
3408
3521
        # we find the parent nodes after the children
3409
3522
        records.reverse()
3410
 
        return records
3411
 
 
3412
 
    def _annotate_records(self, records):
3413
 
        """Build the annotations for the listed records."""
 
3523
        return records, ann_keys
 
3524
 
 
3525
    def _get_needed_texts(self, key, pb=None):
 
3526
        # if True or len(self._vf._fallback_vfs) > 0:
 
3527
        if len(self._vf._fallback_vfs) > 0:
 
3528
            # If we have fallbacks, go to the generic path
 
3529
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
 
3530
                yield v
 
3531
            return
 
3532
        while True:
 
3533
            try:
 
3534
                records, ann_keys = self._get_build_graph(key)
 
3535
                for idx, (sub_key, text, num_lines) in enumerate(
 
3536
                                                self._extract_texts(records)):
 
3537
                    if pb is not None:
 
3538
                        pb.update('annotating', idx, len(records))
 
3539
                    yield sub_key, text, num_lines
 
3540
                for sub_key in ann_keys:
 
3541
                    text = self._text_cache[sub_key]
 
3542
                    num_lines = len(text) # bad assumption
 
3543
                    yield sub_key, text, num_lines
 
3544
                return
 
3545
            except errors.RetryWithNewPacks, e:
 
3546
                self._vf._access.reload_or_raise(e)
 
3547
                # The cached build_details are no longer valid
 
3548
                self._all_build_details.clear()
 
3549
 
 
3550
    def _cache_delta_blocks(self, key, compression_parent, delta, lines):
 
3551
        parent_lines = self._text_cache[compression_parent]
 
3552
        blocks = list(KnitContent.get_line_delta_blocks(delta, parent_lines, lines))
 
3553
        self._matching_blocks[(key, compression_parent)] = blocks
 
3554
 
 
3555
    def _expand_record(self, key, parent_keys, compression_parent, record,
 
3556
                       record_details):
 
3557
        delta = None
 
3558
        if compression_parent:
 
3559
            if compression_parent not in self._content_objects:
 
3560
                # Waiting for the parent
 
3561
                self._pending_deltas.setdefault(compression_parent, []).append(
 
3562
                    (key, parent_keys, record, record_details))
 
3563
                return None
 
3564
            # We have the basis parent, so expand the delta
 
3565
            num = self._num_compression_children[compression_parent]
 
3566
            num -= 1
 
3567
            if num == 0:
 
3568
                base_content = self._content_objects.pop(compression_parent)
 
3569
                self._num_compression_children.pop(compression_parent)
 
3570
            else:
 
3571
                self._num_compression_children[compression_parent] = num
 
3572
                base_content = self._content_objects[compression_parent]
 
3573
            # It is tempting to want to copy_base_content=False for the last
 
3574
            # child object. However, whenever noeol=False,
 
3575
            # self._text_cache[parent_key] is content._lines. So mutating it
 
3576
            # gives very bad results.
 
3577
            # The alternative is to copy the lines into text cache, but then we
 
3578
            # are copying anyway, so just do it here.
 
3579
            content, delta = self._vf._factory.parse_record(
 
3580
                key, record, record_details, base_content,
 
3581
                copy_base_content=True)
 
3582
        else:
 
3583
            # Fulltext record
 
3584
            content, _ = self._vf._factory.parse_record(
 
3585
                key, record, record_details, None)
 
3586
        if self._num_compression_children.get(key, 0) > 0:
 
3587
            self._content_objects[key] = content
 
3588
        lines = content.text()
 
3589
        self._text_cache[key] = lines
 
3590
        if delta is not None:
 
3591
            self._cache_delta_blocks(key, compression_parent, delta, lines)
 
3592
        return lines
 
3593
 
 
3594
    def _get_parent_annotations_and_matches(self, key, text, parent_key):
 
3595
        """Get the list of annotations for the parent, and the matching lines.
 
3596
 
 
3597
        :param text: The opaque value given by _get_needed_texts
 
3598
        :param parent_key: The key for the parent text
 
3599
        :return: (parent_annotations, matching_blocks)
 
3600
            parent_annotations is a list as long as the number of lines in
 
3601
                parent
 
3602
            matching_blocks is a list of (parent_idx, text_idx, len) tuples
 
3603
                indicating which lines match between the two texts
 
3604
        """
 
3605
        block_key = (key, parent_key)
 
3606
        if block_key in self._matching_blocks:
 
3607
            blocks = self._matching_blocks.pop(block_key)
 
3608
            parent_annotations = self._annotations_cache[parent_key]
 
3609
            return parent_annotations, blocks
 
3610
        return annotate.Annotator._get_parent_annotations_and_matches(self,
 
3611
            key, text, parent_key)
 
3612
 
 
3613
    def _process_pending(self, key):
 
3614
        """The content for 'key' was just processed.
 
3615
 
 
3616
        Determine if there is any more pending work to be processed.
 
3617
        """
 
3618
        to_return = []
 
3619
        if key in self._pending_deltas:
 
3620
            compression_parent = key
 
3621
            children = self._pending_deltas.pop(key)
 
3622
            for child_key, parent_keys, record, record_details in children:
 
3623
                lines = self._expand_record(child_key, parent_keys,
 
3624
                                            compression_parent,
 
3625
                                            record, record_details)
 
3626
                if self._check_ready_for_annotations(child_key, parent_keys):
 
3627
                    to_return.append(child_key)
 
3628
        # Also check any children that are waiting for this parent to be
 
3629
        # annotation ready
 
3630
        if key in self._pending_annotation:
 
3631
            children = self._pending_annotation.pop(key)
 
3632
            to_return.extend([c for c, p_keys in children
 
3633
                              if self._check_ready_for_annotations(c, p_keys)])
 
3634
        return to_return
 
3635
 
 
3636
    def _check_ready_for_annotations(self, key, parent_keys):
 
3637
        """return true if this text is ready to be yielded.
 
3638
 
 
3639
        Otherwise, this will return False, and queue the text into
 
3640
        self._pending_annotation
 
3641
        """
 
3642
        for parent_key in parent_keys:
 
3643
            if parent_key not in self._annotations_cache:
 
3644
                # still waiting on at least one parent text, so queue it up
 
3645
                # Note that if there are multiple parents, we need to wait
 
3646
                # for all of them.
 
3647
                self._pending_annotation.setdefault(parent_key,
 
3648
                    []).append((key, parent_keys))
 
3649
                return False
 
3650
        return True
 
3651
 
 
3652
    def _extract_texts(self, records):
 
3653
        """Extract the various texts needed based on records"""
3414
3654
        # We iterate in the order read, rather than a strict order requested
3415
3655
        # However, process what we can, and put off to the side things that
3416
3656
        # still need parents, cleaning them up when those parents are
3417
3657
        # processed.
3418
 
        for (rev_id, record,
3419
 
             digest) in self._knit._read_records_iter(records):
3420
 
            if rev_id in self._annotated_lines:
 
3658
        # Basic data flow:
 
3659
        #   1) As 'records' are read, see if we can expand these records into
 
3660
        #      Content objects (and thus lines)
 
3661
        #   2) If a given line-delta is waiting on its compression parent, it
 
3662
        #      gets queued up into self._pending_deltas, otherwise we expand
 
3663
        #      it, and put it into self._text_cache and self._content_objects
 
3664
        #   3) If we expanded the text, we will then check to see if all
 
3665
        #      parents have also been processed. If so, this text gets yielded,
 
3666
        #      else this record gets set aside into pending_annotation
 
3667
        #   4) Further, if we expanded the text in (2), we will then check to
 
3668
        #      see if there are any children in self._pending_deltas waiting to
 
3669
        #      also be processed. If so, we go back to (2) for those
 
3670
        #   5) Further again, if we yielded the text, we can then check if that
 
3671
        #      'unlocks' any of the texts in pending_annotations, which should
 
3672
        #      then get yielded as well
 
3673
        # Note that both steps 4 and 5 are 'recursive' in that unlocking one
 
3674
        # compression child could unlock yet another, and yielding a fulltext
 
3675
        # will also 'unlock' the children that are waiting on that annotation.
 
3676
        # (Though also, unlocking 1 parent's fulltext, does not unlock a child
 
3677
        # if other parents are also waiting.)
 
3678
        # We want to yield content before expanding child content objects, so
 
3679
        # that we know when we can re-use the content lines, and the annotation
 
3680
        # code can know when it can stop caching fulltexts, as well.
 
3681
 
 
3682
        # Children that are missing their compression parent
 
3683
        pending_deltas = {}
 
3684
        for (key, record, digest) in self._vf._read_records_iter(records):
 
3685
            # ghosts?
 
3686
            details = self._all_build_details[key]
 
3687
            (_, compression_parent, parent_keys, record_details) = details
 
3688
            lines = self._expand_record(key, parent_keys, compression_parent,
 
3689
                                        record, record_details)
 
3690
            if lines is None:
 
3691
                # Pending delta should be queued up
3421
3692
                continue
3422
 
            parent_ids = self._revision_id_graph[rev_id]
3423
 
            parent_ids = [p for p in parent_ids if p not in self._ghosts]
3424
 
            details = self._all_build_details[rev_id]
3425
 
            (index_memo, compression_parent, parents,
3426
 
             record_details) = details
3427
 
            nodes_to_annotate = []
3428
 
            # TODO: Remove the punning between compression parents, and
3429
 
            #       parent_ids, we should be able to do this without assuming
3430
 
            #       the build order
3431
 
            if len(parent_ids) == 0:
3432
 
                # There are no parents for this node, so just add it
3433
 
                # TODO: This probably needs to be decoupled
3434
 
                fulltext_content, delta = self._knit._factory.parse_record(
3435
 
                    rev_id, record, record_details, None)
3436
 
                fulltext = self._add_fulltext_content(rev_id, fulltext_content)
3437
 
                nodes_to_annotate.extend(self._add_annotation(rev_id, fulltext,
3438
 
                    parent_ids, left_matching_blocks=None))
3439
 
            else:
3440
 
                child = (rev_id, parent_ids, record)
3441
 
                # Check if all the parents are present
3442
 
                self._check_parents(child, nodes_to_annotate)
3443
 
            while nodes_to_annotate:
3444
 
                # Should we use a queue here instead of a stack?
3445
 
                (rev_id, parent_ids, record) = nodes_to_annotate.pop()
3446
 
                (index_memo, compression_parent, parents,
3447
 
                 record_details) = self._all_build_details[rev_id]
3448
 
                blocks = None
3449
 
                if compression_parent is not None:
3450
 
                    comp_children = self._compression_children[compression_parent]
3451
 
                    if rev_id not in comp_children:
3452
 
                        raise AssertionError("%r not in compression children %r"
3453
 
                            % (rev_id, comp_children))
3454
 
                    # If there is only 1 child, it is safe to reuse this
3455
 
                    # content
3456
 
                    reuse_content = (len(comp_children) == 1
3457
 
                        and compression_parent not in
3458
 
                            self._nodes_to_keep_annotations)
3459
 
                    if reuse_content:
3460
 
                        # Remove it from the cache since it will be changing
3461
 
                        parent_fulltext_content = self._fulltext_contents.pop(compression_parent)
3462
 
                        # Make sure to copy the fulltext since it might be
3463
 
                        # modified
3464
 
                        parent_fulltext = list(parent_fulltext_content.text())
3465
 
                    else:
3466
 
                        parent_fulltext_content = self._fulltext_contents[compression_parent]
3467
 
                        parent_fulltext = parent_fulltext_content.text()
3468
 
                    comp_children.remove(rev_id)
3469
 
                    fulltext_content, delta = self._knit._factory.parse_record(
3470
 
                        rev_id, record, record_details,
3471
 
                        parent_fulltext_content,
3472
 
                        copy_base_content=(not reuse_content))
3473
 
                    fulltext = self._add_fulltext_content(rev_id,
3474
 
                                                          fulltext_content)
3475
 
                    if compression_parent == parent_ids[0]:
3476
 
                        # the compression_parent is the left parent, so we can
3477
 
                        # re-use the delta
3478
 
                        blocks = KnitContent.get_line_delta_blocks(delta,
3479
 
                                parent_fulltext, fulltext)
3480
 
                else:
3481
 
                    fulltext_content = self._knit._factory.parse_fulltext(
3482
 
                        record, rev_id)
3483
 
                    fulltext = self._add_fulltext_content(rev_id,
3484
 
                        fulltext_content)
3485
 
                nodes_to_annotate.extend(
3486
 
                    self._add_annotation(rev_id, fulltext, parent_ids,
3487
 
                                     left_matching_blocks=blocks))
3488
 
 
3489
 
    def _get_heads_provider(self):
3490
 
        """Create a heads provider for resolving ancestry issues."""
3491
 
        if self._heads_provider is not None:
3492
 
            return self._heads_provider
3493
 
        parent_provider = _mod_graph.DictParentsProvider(
3494
 
            self._revision_id_graph)
3495
 
        graph_obj = _mod_graph.Graph(parent_provider)
3496
 
        head_cache = _mod_graph.FrozenHeadsCache(graph_obj)
3497
 
        self._heads_provider = head_cache
3498
 
        return head_cache
3499
 
 
3500
 
    def annotate(self, key):
3501
 
        """Return the annotated fulltext at the given key.
3502
 
 
3503
 
        :param key: The key to annotate.
3504
 
        """
3505
 
        if len(self._knit._fallback_vfs) > 0:
3506
 
            # stacked knits can't use the fast path at present.
3507
 
            return self._simple_annotate(key)
3508
 
        while True:
3509
 
            try:
3510
 
                records = self._get_build_graph(key)
3511
 
                if key in self._ghosts:
3512
 
                    raise errors.RevisionNotPresent(key, self._knit)
3513
 
                self._annotate_records(records)
3514
 
                return self._annotated_lines[key]
3515
 
            except errors.RetryWithNewPacks, e:
3516
 
                self._knit._access.reload_or_raise(e)
3517
 
                # The cached build_details are no longer valid
3518
 
                self._all_build_details.clear()
3519
 
 
3520
 
    def _simple_annotate(self, key):
3521
 
        """Return annotated fulltext, rediffing from the full texts.
3522
 
 
3523
 
        This is slow but makes no assumptions about the repository
3524
 
        being able to produce line deltas.
3525
 
        """
3526
 
        # TODO: this code generates a parent maps of present ancestors; it
3527
 
        # could be split out into a separate method, and probably should use
3528
 
        # iter_ancestry instead. -- mbp and robertc 20080704
3529
 
        graph = _mod_graph.Graph(self._knit)
3530
 
        head_cache = _mod_graph.FrozenHeadsCache(graph)
3531
 
        search = graph._make_breadth_first_searcher([key])
3532
 
        keys = set()
3533
 
        while True:
3534
 
            try:
3535
 
                present, ghosts = search.next_with_ghosts()
3536
 
            except StopIteration:
3537
 
                break
3538
 
            keys.update(present)
3539
 
        parent_map = self._knit.get_parent_map(keys)
3540
 
        parent_cache = {}
3541
 
        reannotate = annotate.reannotate
3542
 
        for record in self._knit.get_record_stream(keys, 'topological', True):
3543
 
            key = record.key
3544
 
            fulltext = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
3545
 
            parents = parent_map[key]
3546
 
            if parents is not None:
3547
 
                parent_lines = [parent_cache[parent] for parent in parent_map[key]]
3548
 
            else:
3549
 
                parent_lines = []
3550
 
            parent_cache[key] = list(
3551
 
                reannotate(parent_lines, fulltext, key, None, head_cache))
3552
 
        try:
3553
 
            return parent_cache[key]
3554
 
        except KeyError, e:
3555
 
            raise errors.RevisionNotPresent(key, self._knit)
3556
 
 
 
3693
            # At this point, we may be able to yield this content, if all
 
3694
            # parents are also finished
 
3695
            yield_this_text = self._check_ready_for_annotations(key,
 
3696
                                                                parent_keys)
 
3697
            if yield_this_text:
 
3698
                # All parents present
 
3699
                yield key, lines, len(lines)
 
3700
            to_process = self._process_pending(key)
 
3701
            while to_process:
 
3702
                this_process = to_process
 
3703
                to_process = []
 
3704
                for key in this_process:
 
3705
                    lines = self._text_cache[key]
 
3706
                    yield key, lines, len(lines)
 
3707
                    to_process.extend(self._process_pending(key))
3557
3708
 
3558
3709
try:
3559
 
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
3560
 
except ImportError:
 
3710
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
 
3711
except ImportError, e:
 
3712
    osutils.failed_to_load_extension(e)
3561
3713
    from bzrlib._knit_load_data_py import _load_data_py as _load_data