/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: Robert Collins
  • Date: 2010-05-06 11:08:10 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506110810-h3j07fh5gmw54s25
Cleaner matcher matching revised unlocking protocol.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
1
 
# Copyright (C) 2005, 2006, 2007, 2008 Canonical Ltd
 
1
# Copyright (C) 2006-2010 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
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,
 
76
    ui,
75
77
    )
76
78
""")
77
79
from bzrlib import (
664
666
 
665
667
        see parse_fulltext which this inverts.
666
668
        """
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
669
        return ['%s %s' % (o, t) for o, t in content._lines]
670
670
 
671
671
    def lower_line_delta(self, delta):
686
686
        content = knit._get_content(key)
687
687
        # adjust for the fact that serialised annotations are only key suffixes
688
688
        # for this factory.
689
 
        if type(key) == tuple:
 
689
        if type(key) is tuple:
690
690
            prefix = key[:-1]
691
691
            origins = content.annotate()
692
692
            result = []
758
758
 
759
759
    def annotate(self, knit, key):
760
760
        annotator = _KnitAnnotator(knit)
761
 
        return annotator.annotate(key)
 
761
        return annotator.annotate_flat(key)
762
762
 
763
763
 
764
764
 
909
909
            # indexes can't directly store that, so we give them
910
910
            # an empty tuple instead.
911
911
            parents = ()
 
912
        line_bytes = ''.join(lines)
912
913
        return self._add(key, lines, parents,
913
 
            parent_texts, left_matching_blocks, nostore_sha, random_id)
 
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)
914
931
 
915
932
    def _add(self, key, lines, parents, parent_texts,
916
 
        left_matching_blocks, nostore_sha, random_id):
 
933
        left_matching_blocks, nostore_sha, random_id,
 
934
        line_bytes):
917
935
        """Add a set of lines on top of version specified by parents.
918
936
 
919
937
        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.
920
948
        """
921
949
        # first thing, if the content is something we don't need to store, find
922
950
        # that out.
923
 
        line_bytes = ''.join(lines)
924
951
        digest = sha_string(line_bytes)
925
952
        if nostore_sha == digest:
926
953
            raise errors.ExistingContent
947
974
 
948
975
        text_length = len(line_bytes)
949
976
        options = []
950
 
        if lines:
951
 
            if lines[-1][-1] != '\n':
952
 
                # copy the contents of lines.
 
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:
953
988
                lines = lines[:]
954
 
                options.append('no-eol')
955
 
                lines[-1] = lines[-1] + '\n'
956
 
                line_bytes += '\n'
 
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)
957
993
 
958
994
        for element in key[:-1]:
959
 
            if type(element) != str:
 
995
            if type(element) is not str:
960
996
                raise TypeError("key contains non-strings: %r" % (key,))
961
997
        if key[-1] is None:
962
998
            key = key[:-1] + ('sha1:' + digest,)
963
 
        elif type(key[-1]) != str:
 
999
        elif type(key[-1]) is not str:
964
1000
                raise TypeError("key contains non-strings: %r" % (key,))
965
1001
        # Knit hunks are still last-element only
966
1002
        version_id = key[-1]
967
1003
        content = self._factory.make(lines, version_id)
968
 
        if 'no-eol' in options:
 
1004
        if no_eol:
969
1005
            # Hint to the content object that its text() call should strip the
970
1006
            # EOL.
971
1007
            content._should_strip_eol = True
986
1022
            if self._factory.__class__ is KnitPlainFactory:
987
1023
                # Use the already joined bytes saving iteration time in
988
1024
                # _record_to_data.
 
1025
                dense_lines = [line_bytes]
 
1026
                if no_eol:
 
1027
                    dense_lines.append('\n')
989
1028
                size, bytes = self._record_to_data(key, digest,
990
 
                    lines, [line_bytes])
 
1029
                    lines, dense_lines)
991
1030
            else:
992
1031
                # get mixed annotation + content and feed it into the
993
1032
                # serialiser.
1005
1044
        """See VersionedFiles.annotate."""
1006
1045
        return self._factory.annotate(self, key)
1007
1046
 
1008
 
    def check(self, progress_bar=None):
 
1047
    def get_annotator(self):
 
1048
        return _KnitAnnotator(self)
 
1049
 
 
1050
    def check(self, progress_bar=None, keys=None):
1009
1051
        """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):
1010
1059
        # This doesn't actually test extraction of everything, but that will
1011
1060
        # impact 'bzr check' substantially, and needs to be integrated with
1012
1061
        # care. However, it does check for the obvious problem of a delta with
1143
1192
        generator = _VFContentMapGenerator(self, [key])
1144
1193
        return generator._get_content(key)
1145
1194
 
 
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
 
1146
1208
    def get_parent_map(self, keys):
1147
1209
        """Get a map of the graph parents of keys.
1148
1210
 
1449
1511
                                                                non_local_keys,
1450
1512
                                                                positions):
1451
1513
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1452
 
                                                   global_map)
 
1514
                                                   global_map,
 
1515
                                                   ordering=ordering)
1453
1516
                for record in generator.get_record_stream():
1454
1517
                    yield record
1455
1518
        else:
1457
1520
                if source is parent_maps[0]:
1458
1521
                    # this KnitVersionedFiles
1459
1522
                    records = [(key, positions[key][1]) for key in keys]
1460
 
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
 
1523
                    for key, raw_data in self._read_records_iter_unchecked(records):
1461
1524
                        (record_details, index_memo, _) = positions[key]
1462
1525
                        yield KnitContentFactory(key, global_map[key],
1463
 
                            record_details, sha1, raw_data, self._factory.annotated, None)
 
1526
                            record_details, None, raw_data, self._factory.annotated, None)
1464
1527
                else:
1465
1528
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1466
1529
                    for record in vf.get_record_stream(keys, ordering,
1535
1598
        # key = basis_parent, value = index entry to add
1536
1599
        buffered_index_entries = {}
1537
1600
        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()
1538
1608
            buffered = False
1539
1609
            parents = record.parents
1540
1610
            if record.storage_kind in delta_types:
1642
1712
            # There were index entries buffered at the end of the stream,
1643
1713
            # So these need to be added (if the index supports holding such
1644
1714
            # entries for later insertion)
 
1715
            all_entries = []
1645
1716
            for key in buffered_index_entries:
1646
1717
                index_entries = buffered_index_entries[key]
1647
 
                self._index.add_records(index_entries,
1648
 
                    missing_compression_parents=True)
 
1718
                all_entries.extend(index_entries)
 
1719
            self._index.add_records(
 
1720
                all_entries, missing_compression_parents=True)
1649
1721
 
1650
1722
    def get_missing_compression_parent_keys(self):
1651
1723
        """Return an iterable of keys of missing compression parents.
1684
1756
        :return: An iterator over (line, key).
1685
1757
        """
1686
1758
        if pb is None:
1687
 
            pb = progress.DummyProgress()
 
1759
            pb = ui.ui_factory.nested_progress_bar()
1688
1760
        keys = set(keys)
1689
1761
        total = len(keys)
1690
1762
        done = False
1920
1992
            function spends less time resizing the final string.
1921
1993
        :return: (len, a StringIO instance with the raw data ready to read.)
1922
1994
        """
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))
 
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))
1935
2002
        if lines and lines[-1][-1] != '\n':
1936
2003
            raise ValueError('corrupt lines value %r' % lines)
1937
 
        compressed_bytes = tuned_gzip.bytes_to_gzip(bytes)
 
2004
        compressed_bytes = tuned_gzip.chunks_to_gzip(chunks)
1938
2005
        return len(compressed_bytes), compressed_bytes
1939
2006
 
1940
2007
    def _split_header(self, line):
1958
2025
class _ContentMapGenerator(object):
1959
2026
    """Generate texts or expose raw deltas for a set of texts."""
1960
2027
 
 
2028
    def __init__(self, ordering='unordered'):
 
2029
        self._ordering = ordering
 
2030
 
1961
2031
    def _get_content(self, key):
1962
2032
        """Get the content object for key."""
1963
2033
        # Note that _get_content is only called when the _ContentMapGenerator
1997
2067
            # Loop over fallback repositories asking them for texts - ignore
1998
2068
            # any missing from a particular fallback.
1999
2069
            for record in source.get_record_stream(missing_keys,
2000
 
                'unordered', True):
 
2070
                self._ordering, True):
2001
2071
                if record.storage_kind == 'absent':
2002
2072
                    # Not in thie particular stream, may be in one of the
2003
2073
                    # other fallback vfs objects.
2135
2205
    """Content map generator reading from a VersionedFiles object."""
2136
2206
 
2137
2207
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2138
 
        global_map=None, raw_record_map=None):
 
2208
        global_map=None, raw_record_map=None, ordering='unordered'):
2139
2209
        """Create a _ContentMapGenerator.
2140
2210
 
2141
2211
        :param versioned_files: The versioned files that the texts are being
2149
2219
        :param raw_record_map: A unparsed raw record map to use for answering
2150
2220
            contents.
2151
2221
        """
 
2222
        _ContentMapGenerator.__init__(self, ordering=ordering)
2152
2223
        # The vf to source data from
2153
2224
        self.vf = versioned_files
2154
2225
        # The keys desired
2298
2369
    FLAGS is a comma separated list of flags about the record. Values include
2299
2370
        no-eol, line-delta, fulltext.
2300
2371
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2301
 
        that the the compressed data starts at.
 
2372
        that the compressed data starts at.
2302
2373
    LENGTH is the ascii representation of the length of the data file.
2303
2374
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2304
2375
        REVISION_ID.
2375
2446
                    line = "\n%s %s %s %s %s :" % (
2376
2447
                        key[-1], ','.join(options), pos, size,
2377
2448
                        self._dictionary_compress(parents))
2378
 
                    if type(line) != str:
 
2449
                    if type(line) is not str:
2379
2450
                        raise AssertionError(
2380
2451
                            'data must be utf8 was %s' % type(line))
2381
2452
                    lines.append(line)
2513
2584
        except KeyError:
2514
2585
            raise RevisionNotPresent(key, self)
2515
2586
 
 
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
 
2516
2614
    def get_parent_map(self, keys):
2517
2615
        """Get a map of the parents of keys.
2518
2616
 
2570
2668
        result = set()
2571
2669
        # Identify all key prefixes.
2572
2670
        # XXX: A bit hacky, needs polish.
2573
 
        if type(self._mapper) == ConstantMapper:
 
2671
        if type(self._mapper) is ConstantMapper:
2574
2672
            prefixes = [()]
2575
2673
        else:
2576
2674
            relpaths = set()
2608
2706
                    del self._history
2609
2707
                except NoSuchFile:
2610
2708
                    self._kndx_cache[prefix] = ({}, [])
2611
 
                    if type(self._mapper) == ConstantMapper:
 
2709
                    if type(self._mapper) is ConstantMapper:
2612
2710
                        # preserve behaviour for revisions.kndx etc.
2613
2711
                        self._init_index(path)
2614
2712
                    del self._cache
2690
2788
 
2691
2789
class _KeyRefs(object):
2692
2790
 
2693
 
    def __init__(self):
 
2791
    def __init__(self, track_new_keys=False):
2694
2792
        # dict mapping 'key' to 'set of keys referring to that key'
2695
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()
2696
2805
 
2697
2806
    def add_references(self, key, refs):
2698
2807
        # Record the new references
2705
2814
        # Discard references satisfied by the new key
2706
2815
        self.add_key(key)
2707
2816
 
 
2817
    def get_new_keys(self):
 
2818
        return self.new_keys
 
2819
    
2708
2820
    def get_unsatisfied_refs(self):
2709
2821
        return self.refs.iterkeys()
2710
2822
 
2711
 
    def add_key(self, key):
 
2823
    def _satisfy_refs_for_key(self, key):
2712
2824
        try:
2713
2825
            del self.refs[key]
2714
2826
        except KeyError:
2715
2827
            # No keys depended on this key.  That's ok.
2716
2828
            pass
2717
2829
 
2718
 
    def add_keys(self, keys):
 
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):
2719
2837
        for key in keys:
2720
 
            self.add_key(key)
 
2838
            self._satisfy_refs_for_key(key)
2721
2839
 
2722
2840
    def get_referrers(self):
2723
2841
        result = set()
2828
2946
        if not random_id:
2829
2947
            present_nodes = self._get_entries(keys)
2830
2948
            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]
2831
2953
                if (value[0] != keys[key][0][0] or
2832
 
                    node_refs[:1] != keys[key][1][:1]):
 
2954
                    parents != passed_parents):
 
2955
                    node_refs = static_tuple.as_tuples(node_refs)
2833
2956
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2834
 
                        ": %s %s" % ((value, node_refs), keys[key]))
 
2957
                        ": %s %s" % ((value, node_refs), passed))
2835
2958
                del keys[key]
2836
2959
        result = []
2837
2960
        if self._parents:
2885
3008
        # If updating this, you should also update
2886
3009
        # groupcompress._GCGraphIndex.get_missing_parents
2887
3010
        # We may have false positives, so filter those out.
2888
 
        self._key_dependencies.add_keys(
 
3011
        self._key_dependencies.satisfy_refs_for_keys(
2889
3012
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2890
3013
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
2891
3014
 
3002
3125
            options.append('no-eol')
3003
3126
        return options
3004
3127
 
 
3128
    def find_ancestry(self, keys):
 
3129
        """See CombinedGraphIndex.find_ancestry()"""
 
3130
        return self._graph_index.find_ancestry(keys, 0)
 
3131
 
3005
3132
    def get_parent_map(self, keys):
3006
3133
        """Get a map of the parents of keys.
3007
3134
 
3094
3221
            opaque index memo. For _KnitKeyAccess the memo is (key, pos,
3095
3222
            length), where the key is the record key.
3096
3223
        """
3097
 
        if type(raw_data) != str:
 
3224
        if type(raw_data) is not str:
3098
3225
            raise AssertionError(
3099
3226
                'data must be plain bytes was %s' % type(raw_data))
3100
3227
        result = []
3183
3310
            length), where the index field is the write_index object supplied
3184
3311
            to the PackAccess object.
3185
3312
        """
3186
 
        if type(raw_data) != str:
 
3313
        if type(raw_data) is not str:
3187
3314
            raise AssertionError(
3188
3315
                'data must be plain bytes was %s' % type(raw_data))
3189
3316
        result = []
3302
3429
    recommended.
3303
3430
    """
3304
3431
    annotator = _KnitAnnotator(knit)
3305
 
    return iter(annotator.annotate(revision_id))
3306
 
 
3307
 
 
3308
 
class _KnitAnnotator(object):
 
3432
    return iter(annotator.annotate_flat(revision_id))
 
3433
 
 
3434
 
 
3435
class _KnitAnnotator(annotate.Annotator):
3309
3436
    """Build up the annotations for a text."""
3310
3437
 
3311
 
    def __init__(self, knit):
3312
 
        self._knit = knit
3313
 
 
3314
 
        # Content objects, differs from fulltexts because of how final newlines
3315
 
        # are treated by knits. the content objects here will always have a
3316
 
        # final newline
3317
 
        self._fulltext_contents = {}
3318
 
 
3319
 
        # Annotated lines of specific revisions
3320
 
        self._annotated_lines = {}
3321
 
 
3322
 
        # Track the raw data for nodes that we could not process yet.
3323
 
        # This maps the revision_id of the base to a list of children that will
3324
 
        # annotated from it.
3325
 
        self._pending_children = {}
3326
 
 
3327
 
        # Nodes which cannot be extracted
3328
 
        self._ghosts = set()
3329
 
 
3330
 
        # Track how many children this node has, so we know if we need to keep
3331
 
        # it
3332
 
        self._annotate_children = {}
3333
 
        self._compression_children = {}
 
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 = {}
3334
3457
 
3335
3458
        self._all_build_details = {}
3336
 
        # The children => parent revision_id graph
3337
 
        self._revision_id_graph = {}
3338
 
 
3339
 
        self._heads_provider = None
3340
 
 
3341
 
        self._nodes_to_keep_annotations = set()
3342
 
        self._generations_until_keep = 100
3343
 
 
3344
 
    def set_generations_until_keep(self, value):
3345
 
        """Set the number of generations before caching a node.
3346
 
 
3347
 
        Setting this to -1 will cache every merge node, setting this higher
3348
 
        will cache fewer nodes.
3349
 
        """
3350
 
        self._generations_until_keep = value
3351
 
 
3352
 
    def _add_fulltext_content(self, revision_id, content_obj):
3353
 
        self._fulltext_contents[revision_id] = content_obj
3354
 
        # TODO: jam 20080305 It might be good to check the sha1digest here
3355
 
        return content_obj.text()
3356
 
 
3357
 
    def _check_parents(self, child, nodes_to_annotate):
3358
 
        """Check if all parents have been processed.
3359
 
 
3360
 
        :param child: A tuple of (rev_id, parents, raw_content)
3361
 
        :param nodes_to_annotate: If child is ready, add it to
3362
 
            nodes_to_annotate, otherwise put it back in self._pending_children
3363
 
        """
3364
 
        for parent_id in child[1]:
3365
 
            if (parent_id not in self._annotated_lines):
3366
 
                # This parent is present, but another parent is missing
3367
 
                self._pending_children.setdefault(parent_id,
3368
 
                                                  []).append(child)
3369
 
                break
3370
 
        else:
3371
 
            # This one is ready to be processed
3372
 
            nodes_to_annotate.append(child)
3373
 
 
3374
 
    def _add_annotation(self, revision_id, fulltext, parent_ids,
3375
 
                        left_matching_blocks=None):
3376
 
        """Add an annotation entry.
3377
 
 
3378
 
        All parents should already have been annotated.
3379
 
        :return: A list of children that now have their parents satisfied.
3380
 
        """
3381
 
        a = self._annotated_lines
3382
 
        annotated_parent_lines = [a[p] for p in parent_ids]
3383
 
        annotated_lines = list(annotate.reannotate(annotated_parent_lines,
3384
 
            fulltext, revision_id, left_matching_blocks,
3385
 
            heads_provider=self._get_heads_provider()))
3386
 
        self._annotated_lines[revision_id] = annotated_lines
3387
 
        for p in parent_ids:
3388
 
            ann_children = self._annotate_children[p]
3389
 
            ann_children.remove(revision_id)
3390
 
            if (not ann_children
3391
 
                and p not in self._nodes_to_keep_annotations):
3392
 
                del self._annotated_lines[p]
3393
 
                del self._all_build_details[p]
3394
 
                if p in self._fulltext_contents:
3395
 
                    del self._fulltext_contents[p]
3396
 
        # Now that we've added this one, see if there are any pending
3397
 
        # deltas to be done, certainly this parent is finished
3398
 
        nodes_to_annotate = []
3399
 
        for child in self._pending_children.pop(revision_id, []):
3400
 
            self._check_parents(child, nodes_to_annotate)
3401
 
        return nodes_to_annotate
3402
3459
 
3403
3460
    def _get_build_graph(self, key):
3404
3461
        """Get the graphs for building texts and annotations.
3412
3469
            passing to read_records_iter to start reading in the raw data from
3413
3470
            the pack file.
3414
3471
        """
3415
 
        if key in self._annotated_lines:
3416
 
            # Nothing to do
3417
 
            return []
3418
3472
        pending = set([key])
3419
3473
        records = []
3420
 
        generation = 0
3421
 
        kept_generation = 0
 
3474
        ann_keys = set()
 
3475
        self._num_needed_children[key] = 1
3422
3476
        while pending:
3423
3477
            # get all pending nodes
3424
 
            generation += 1
3425
3478
            this_iteration = pending
3426
 
            build_details = self._knit._index.get_build_details(this_iteration)
 
3479
            build_details = self._vf._index.get_build_details(this_iteration)
3427
3480
            self._all_build_details.update(build_details)
3428
 
            # new_nodes = self._knit._index._get_entries(this_iteration)
 
3481
            # new_nodes = self._vf._index._get_entries(this_iteration)
3429
3482
            pending = set()
3430
3483
            for key, details in build_details.iteritems():
3431
 
                (index_memo, compression_parent, parents,
 
3484
                (index_memo, compression_parent, parent_keys,
3432
3485
                 record_details) = details
3433
 
                self._revision_id_graph[key] = parents
 
3486
                self._parent_map[key] = parent_keys
 
3487
                self._heads_provider = None
3434
3488
                records.append((key, index_memo))
3435
3489
                # Do we actually need to check _annotated_lines?
3436
 
                pending.update(p for p in parents
3437
 
                                 if p not in self._all_build_details)
 
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
3438
3498
                if compression_parent:
3439
 
                    self._compression_children.setdefault(compression_parent,
3440
 
                        []).append(key)
3441
 
                if parents:
3442
 
                    for parent in parents:
3443
 
                        self._annotate_children.setdefault(parent,
3444
 
                            []).append(key)
3445
 
                    num_gens = generation - kept_generation
3446
 
                    if ((num_gens >= self._generations_until_keep)
3447
 
                        and len(parents) > 1):
3448
 
                        kept_generation = generation
3449
 
                        self._nodes_to_keep_annotations.add(key)
 
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
3450
3503
 
3451
3504
            missing_versions = this_iteration.difference(build_details.keys())
3452
 
            self._ghosts.update(missing_versions)
3453
 
            for missing_version in missing_versions:
3454
 
                # add a key, no parents
3455
 
                self._revision_id_graph[missing_version] = ()
3456
 
                pending.discard(missing_version) # don't look for it
3457
 
        if self._ghosts.intersection(self._compression_children):
3458
 
            raise KnitCorrupt(
3459
 
                "We cannot have nodes which have a ghost compression parent:\n"
3460
 
                "ghosts: %r\n"
3461
 
                "compression children: %r"
3462
 
                % (self._ghosts, self._compression_children))
3463
 
        # Cleanout anything that depends on a ghost so that we don't wait for
3464
 
        # the ghost to show up
3465
 
        for node in self._ghosts:
3466
 
            if node in self._annotate_children:
3467
 
                # We won't be building this node
3468
 
                del self._annotate_children[node]
 
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)
3469
3521
        # Generally we will want to read the records in reverse order, because
3470
3522
        # we find the parent nodes after the children
3471
3523
        records.reverse()
3472
 
        return records
3473
 
 
3474
 
    def _annotate_records(self, records):
3475
 
        """Build the annotations for the listed records."""
 
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"""
3476
3655
        # We iterate in the order read, rather than a strict order requested
3477
3656
        # However, process what we can, and put off to the side things that
3478
3657
        # still need parents, cleaning them up when those parents are
3479
3658
        # processed.
3480
 
        for (rev_id, record,
3481
 
             digest) in self._knit._read_records_iter(records):
3482
 
            if rev_id in self._annotated_lines:
 
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
3483
3693
                continue
3484
 
            parent_ids = self._revision_id_graph[rev_id]
3485
 
            parent_ids = [p for p in parent_ids if p not in self._ghosts]
3486
 
            details = self._all_build_details[rev_id]
3487
 
            (index_memo, compression_parent, parents,
3488
 
             record_details) = details
3489
 
            nodes_to_annotate = []
3490
 
            # TODO: Remove the punning between compression parents, and
3491
 
            #       parent_ids, we should be able to do this without assuming
3492
 
            #       the build order
3493
 
            if len(parent_ids) == 0:
3494
 
                # There are no parents for this node, so just add it
3495
 
                # TODO: This probably needs to be decoupled
3496
 
                fulltext_content, delta = self._knit._factory.parse_record(
3497
 
                    rev_id, record, record_details, None)
3498
 
                fulltext = self._add_fulltext_content(rev_id, fulltext_content)
3499
 
                nodes_to_annotate.extend(self._add_annotation(rev_id, fulltext,
3500
 
                    parent_ids, left_matching_blocks=None))
3501
 
            else:
3502
 
                child = (rev_id, parent_ids, record)
3503
 
                # Check if all the parents are present
3504
 
                self._check_parents(child, nodes_to_annotate)
3505
 
            while nodes_to_annotate:
3506
 
                # Should we use a queue here instead of a stack?
3507
 
                (rev_id, parent_ids, record) = nodes_to_annotate.pop()
3508
 
                (index_memo, compression_parent, parents,
3509
 
                 record_details) = self._all_build_details[rev_id]
3510
 
                blocks = None
3511
 
                if compression_parent is not None:
3512
 
                    comp_children = self._compression_children[compression_parent]
3513
 
                    if rev_id not in comp_children:
3514
 
                        raise AssertionError("%r not in compression children %r"
3515
 
                            % (rev_id, comp_children))
3516
 
                    # If there is only 1 child, it is safe to reuse this
3517
 
                    # content
3518
 
                    reuse_content = (len(comp_children) == 1
3519
 
                        and compression_parent not in
3520
 
                            self._nodes_to_keep_annotations)
3521
 
                    if reuse_content:
3522
 
                        # Remove it from the cache since it will be changing
3523
 
                        parent_fulltext_content = self._fulltext_contents.pop(compression_parent)
3524
 
                        # Make sure to copy the fulltext since it might be
3525
 
                        # modified
3526
 
                        parent_fulltext = list(parent_fulltext_content.text())
3527
 
                    else:
3528
 
                        parent_fulltext_content = self._fulltext_contents[compression_parent]
3529
 
                        parent_fulltext = parent_fulltext_content.text()
3530
 
                    comp_children.remove(rev_id)
3531
 
                    fulltext_content, delta = self._knit._factory.parse_record(
3532
 
                        rev_id, record, record_details,
3533
 
                        parent_fulltext_content,
3534
 
                        copy_base_content=(not reuse_content))
3535
 
                    fulltext = self._add_fulltext_content(rev_id,
3536
 
                                                          fulltext_content)
3537
 
                    if compression_parent == parent_ids[0]:
3538
 
                        # the compression_parent is the left parent, so we can
3539
 
                        # re-use the delta
3540
 
                        blocks = KnitContent.get_line_delta_blocks(delta,
3541
 
                                parent_fulltext, fulltext)
3542
 
                else:
3543
 
                    fulltext_content = self._knit._factory.parse_fulltext(
3544
 
                        record, rev_id)
3545
 
                    fulltext = self._add_fulltext_content(rev_id,
3546
 
                        fulltext_content)
3547
 
                nodes_to_annotate.extend(
3548
 
                    self._add_annotation(rev_id, fulltext, parent_ids,
3549
 
                                     left_matching_blocks=blocks))
3550
 
 
3551
 
    def _get_heads_provider(self):
3552
 
        """Create a heads provider for resolving ancestry issues."""
3553
 
        if self._heads_provider is not None:
3554
 
            return self._heads_provider
3555
 
        self._heads_provider = _mod_graph.KnownGraph(self._revision_id_graph)
3556
 
        return self._heads_provider
3557
 
 
3558
 
    def annotate(self, key):
3559
 
        """Return the annotated fulltext at the given key.
3560
 
 
3561
 
        :param key: The key to annotate.
3562
 
        """
3563
 
        if len(self._knit._fallback_vfs) > 0:
3564
 
            # stacked knits can't use the fast path at present.
3565
 
            return self._simple_annotate(key)
3566
 
        while True:
3567
 
            try:
3568
 
                records = self._get_build_graph(key)
3569
 
                if key in self._ghosts:
3570
 
                    raise errors.RevisionNotPresent(key, self._knit)
3571
 
                self._annotate_records(records)
3572
 
                return self._annotated_lines[key]
3573
 
            except errors.RetryWithNewPacks, e:
3574
 
                self._knit._access.reload_or_raise(e)
3575
 
                # The cached build_details are no longer valid
3576
 
                self._all_build_details.clear()
3577
 
 
3578
 
    def _simple_annotate(self, key):
3579
 
        """Return annotated fulltext, rediffing from the full texts.
3580
 
 
3581
 
        This is slow but makes no assumptions about the repository
3582
 
        being able to produce line deltas.
3583
 
        """
3584
 
        # TODO: this code generates a parent maps of present ancestors; it
3585
 
        #       could be split out into a separate method
3586
 
        #       -- mbp and robertc 20080704
3587
 
        graph = _mod_graph.Graph(self._knit)
3588
 
        parent_map = dict((k, v) for k, v in graph.iter_ancestry([key])
3589
 
                          if v is not None)
3590
 
        if not parent_map:
3591
 
            raise errors.RevisionNotPresent(key, self)
3592
 
        keys = parent_map.keys()
3593
 
        heads_provider = _mod_graph.KnownGraph(parent_map)
3594
 
        parent_cache = {}
3595
 
        reannotate = annotate.reannotate
3596
 
        for record in self._knit.get_record_stream(keys, 'topological', True):
3597
 
            key = record.key
3598
 
            fulltext = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
3599
 
            parents = parent_map[key]
3600
 
            if parents is not None:
3601
 
                parent_lines = [parent_cache[parent] for parent in parent_map[key]]
3602
 
            else:
3603
 
                parent_lines = []
3604
 
            parent_cache[key] = list(
3605
 
                reannotate(parent_lines, fulltext, key, None, heads_provider))
3606
 
        try:
3607
 
            return parent_cache[key]
3608
 
        except KeyError, e:
3609
 
            raise errors.RevisionNotPresent(key, self._knit)
3610
 
 
 
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))
3611
3709
 
3612
3710
try:
3613
 
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
3614
 
except ImportError:
 
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)
3615
3714
    from bzrlib._knit_load_data_py import _load_data_py as _load_data