← 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: 2009-06-18 20:25:52 UTC
  • mfrom: (4413.5.15 1.16-chk-direct)
  • Revision ID: pqm@pqm.ubuntu.com-20090618202552-xyl6tcvbxtm8bupf
(jam) Improve initial commit performance by creating a CHKMap in bulk,
        rather than via O(tree) map() calls.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
1
 
# Copyright (C) 2006-2010 Canonical Ltd
 
1
# Copyright (C) 2005, 2006, 2007, 2008 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
53
53
 
54
54
 
55
55
from cStringIO import StringIO
56
 
from itertools import izip
 
56
from itertools import izip, chain
57
57
import operator
58
58
import os
59
59
import sys
68
68
    index as _mod_index,
69
69
    lru_cache,
70
70
    pack,
71
 
    patiencediff,
72
71
    progress,
73
 
    static_tuple,
74
72
    trace,
75
73
    tsort,
76
74
    tuned_gzip,
77
 
    ui,
78
75
    )
79
76
""")
80
77
from bzrlib import (
81
78
    errors,
82
79
    osutils,
 
80
    patiencediff,
83
81
    )
84
82
from bzrlib.errors import (
85
83
    FileExists,
666
664
 
667
665
        see parse_fulltext which this inverts.
668
666
        """
 
667
        # TODO: jam 20070209 We only do the caching thing to make sure that
 
668
        #       the origin is a valid utf-8 line, eventually we could remove it
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) is tuple:
 
689
        if type(key) == 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_flat(key)
 
761
        return annotator.annotate(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)
913
912
        return self._add(key, lines, parents,
914
 
            parent_texts, left_matching_blocks, nostore_sha, random_id,
915
 
            line_bytes=line_bytes)
916
 
 
917
 
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
918
 
        """See VersionedFiles._add_text()."""
919
 
        self._index._check_write_ok()
920
 
        self._check_add(key, None, random_id, check_content=False)
921
 
        if text.__class__ is not str:
922
 
            raise errors.BzrBadParameterUnicode("text")
923
 
        if parents is None:
924
 
            # The caller might pass None if there is no graph data, but kndx
925
 
            # indexes can't directly store that, so we give them
926
 
            # an empty tuple instead.
927
 
            parents = ()
928
 
        return self._add(key, None, parents,
929
 
            None, None, nostore_sha, random_id,
930
 
            line_bytes=text)
 
913
            parent_texts, left_matching_blocks, nostore_sha, random_id)
931
914
 
932
915
    def _add(self, key, lines, parents, parent_texts,
933
 
        left_matching_blocks, nostore_sha, random_id,
934
 
        line_bytes):
 
916
        left_matching_blocks, nostore_sha, random_id):
935
917
        """Add a set of lines on top of version specified by parents.
936
918
 
937
919
        Any versions not present will be converted into ghosts.
938
 
 
939
 
        :param lines: A list of strings where each one is a single line (has a
940
 
            single newline at the end of the string) This is now optional
941
 
            (callers can pass None). It is left in its location for backwards
942
 
            compatibility. It should ''.join(lines) must == line_bytes
943
 
        :param line_bytes: A single string containing the content
944
 
 
945
 
        We pass both lines and line_bytes because different routes bring the
946
 
        values to this function. And for memory efficiency, we don't want to
947
 
        have to split/join on-demand.
948
920
        """
949
921
        # first thing, if the content is something we don't need to store, find
950
922
        # that out.
 
923
        line_bytes = ''.join(lines)
951
924
        digest = sha_string(line_bytes)
952
925
        if nostore_sha == digest:
953
926
            raise errors.ExistingContent
974
947
 
975
948
        text_length = len(line_bytes)
976
949
        options = []
977
 
        no_eol = False
978
 
        # Note: line_bytes is not modified to add a newline, that is tracked
979
 
        #       via the no_eol flag. 'lines' *is* modified, because that is the
980
 
        #       general values needed by the Content code.
981
 
        if line_bytes and line_bytes[-1] != '\n':
982
 
            options.append('no-eol')
983
 
            no_eol = True
984
 
            # Copy the existing list, or create a new one
985
 
            if lines is None:
986
 
                lines = osutils.split_lines(line_bytes)
987
 
            else:
 
950
        if lines:
 
951
            if lines[-1][-1] != '\n':
 
952
                # copy the contents of lines.
988
953
                lines = lines[:]
989
 
            # Replace the last line with one that ends in a final newline
990
 
            lines[-1] = lines[-1] + '\n'
991
 
        if lines is None:
992
 
            lines = osutils.split_lines(line_bytes)
 
954
                options.append('no-eol')
 
955
                lines[-1] = lines[-1] + '\n'
 
956
                line_bytes += '\n'
993
957
 
994
958
        for element in key[:-1]:
995
 
            if type(element) is not str:
 
959
            if type(element) != str:
996
960
                raise TypeError("key contains non-strings: %r" % (key,))
997
961
        if key[-1] is None:
998
962
            key = key[:-1] + ('sha1:' + digest,)
999
 
        elif type(key[-1]) is not str:
 
963
        elif type(key[-1]) != str:
1000
964
                raise TypeError("key contains non-strings: %r" % (key,))
1001
965
        # Knit hunks are still last-element only
1002
966
        version_id = key[-1]
1003
967
        content = self._factory.make(lines, version_id)
1004
 
        if no_eol:
 
968
        if 'no-eol' in options:
1005
969
            # Hint to the content object that its text() call should strip the
1006
970
            # EOL.
1007
971
            content._should_strip_eol = True
1022
986
            if self._factory.__class__ is KnitPlainFactory:
1023
987
                # Use the already joined bytes saving iteration time in
1024
988
                # _record_to_data.
1025
 
                dense_lines = [line_bytes]
1026
 
                if no_eol:
1027
 
                    dense_lines.append('\n')
1028
989
                size, bytes = self._record_to_data(key, digest,
1029
 
                    lines, dense_lines)
 
990
                    lines, [line_bytes])
1030
991
            else:
1031
992
                # get mixed annotation + content and feed it into the
1032
993
                # serialiser.
1044
1005
        """See VersionedFiles.annotate."""
1045
1006
        return self._factory.annotate(self, key)
1046
1007
 
1047
 
    def get_annotator(self):
1048
 
        return _KnitAnnotator(self)
1049
 
 
1050
 
    def check(self, progress_bar=None, keys=None):
 
1008
    def check(self, progress_bar=None):
1051
1009
        """See VersionedFiles.check()."""
1052
 
        if keys is None:
1053
 
            return self._logical_check()
1054
 
        else:
1055
 
            # At the moment, check does not extra work over get_record_stream
1056
 
            return self.get_record_stream(keys, 'unordered', True)
1057
 
 
1058
 
    def _logical_check(self):
1059
1010
        # This doesn't actually test extraction of everything, but that will
1060
1011
        # impact 'bzr check' substantially, and needs to be integrated with
1061
1012
        # care. However, it does check for the obvious problem of a delta with
1192
1143
        generator = _VFContentMapGenerator(self, [key])
1193
1144
        return generator._get_content(key)
1194
1145
 
1195
 
    def get_known_graph_ancestry(self, keys):
1196
 
        """Get a KnownGraph instance with the ancestry of keys."""
1197
 
        parent_map, missing_keys = self._index.find_ancestry(keys)
1198
 
        for fallback in self._fallback_vfs:
1199
 
            if not missing_keys:
1200
 
                break
1201
 
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1202
 
                                                missing_keys)
1203
 
            parent_map.update(f_parent_map)
1204
 
            missing_keys = f_missing_keys
1205
 
        kg = _mod_graph.KnownGraph(parent_map)
1206
 
        return kg
1207
 
 
1208
1146
    def get_parent_map(self, keys):
1209
1147
        """Get a map of the graph parents of keys.
1210
1148
 
1511
1449
                                                                non_local_keys,
1512
1450
                                                                positions):
1513
1451
                generator = _VFContentMapGenerator(self, keys, non_local_keys,
1514
 
                                                   global_map,
1515
 
                                                   ordering=ordering)
 
1452
                                                   global_map)
1516
1453
                for record in generator.get_record_stream():
1517
1454
                    yield record
1518
1455
        else:
1520
1457
                if source is parent_maps[0]:
1521
1458
                    # this KnitVersionedFiles
1522
1459
                    records = [(key, positions[key][1]) for key in keys]
1523
 
                    for key, raw_data in self._read_records_iter_unchecked(records):
 
1460
                    for key, raw_data, sha1 in self._read_records_iter_raw(records):
1524
1461
                        (record_details, index_memo, _) = positions[key]
1525
1462
                        yield KnitContentFactory(key, global_map[key],
1526
 
                            record_details, None, raw_data, self._factory.annotated, None)
 
1463
                            record_details, sha1, raw_data, self._factory.annotated, None)
1527
1464
                else:
1528
1465
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
1529
1466
                    for record in vf.get_record_stream(keys, ordering,
1598
1535
        # key = basis_parent, value = index entry to add
1599
1536
        buffered_index_entries = {}
1600
1537
        for record in stream:
1601
 
            kind = record.storage_kind
1602
 
            if kind.startswith('knit-') and kind.endswith('-gz'):
1603
 
                # Check that the ID in the header of the raw knit bytes matches
1604
 
                # the record metadata.
1605
 
                raw_data = record._raw_record
1606
 
                df, rec = self._parse_record_header(record.key, raw_data)
1607
 
                df.close()
1608
1538
            buffered = False
1609
1539
            parents = record.parents
1610
1540
            if record.storage_kind in delta_types:
1712
1642
            # There were index entries buffered at the end of the stream,
1713
1643
            # So these need to be added (if the index supports holding such
1714
1644
            # entries for later insertion)
1715
 
            all_entries = []
1716
1645
            for key in buffered_index_entries:
1717
1646
                index_entries = buffered_index_entries[key]
1718
 
                all_entries.extend(index_entries)
1719
 
            self._index.add_records(
1720
 
                all_entries, missing_compression_parents=True)
 
1647
                self._index.add_records(index_entries,
 
1648
                    missing_compression_parents=True)
1721
1649
 
1722
1650
    def get_missing_compression_parent_keys(self):
1723
1651
        """Return an iterable of keys of missing compression parents.
1756
1684
        :return: An iterator over (line, key).
1757
1685
        """
1758
1686
        if pb is None:
1759
 
            pb = ui.ui_factory.nested_progress_bar()
 
1687
            pb = progress.DummyProgress()
1760
1688
        keys = set(keys)
1761
1689
        total = len(keys)
1762
1690
        done = False
1992
1920
            function spends less time resizing the final string.
1993
1921
        :return: (len, a StringIO instance with the raw data ready to read.)
1994
1922
        """
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))
 
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))
2002
1935
        if lines and lines[-1][-1] != '\n':
2003
1936
            raise ValueError('corrupt lines value %r' % lines)
2004
 
        compressed_bytes = tuned_gzip.chunks_to_gzip(chunks)
 
1937
        compressed_bytes = tuned_gzip.bytes_to_gzip(bytes)
2005
1938
        return len(compressed_bytes), compressed_bytes
2006
1939
 
2007
1940
    def _split_header(self, line):
2025
1958
class _ContentMapGenerator(object):
2026
1959
    """Generate texts or expose raw deltas for a set of texts."""
2027
1960
 
2028
 
    def __init__(self, ordering='unordered'):
2029
 
        self._ordering = ordering
2030
 
 
2031
1961
    def _get_content(self, key):
2032
1962
        """Get the content object for key."""
2033
1963
        # Note that _get_content is only called when the _ContentMapGenerator
2067
1997
            # Loop over fallback repositories asking them for texts - ignore
2068
1998
            # any missing from a particular fallback.
2069
1999
            for record in source.get_record_stream(missing_keys,
2070
 
                self._ordering, True):
 
2000
                'unordered', True):
2071
2001
                if record.storage_kind == 'absent':
2072
2002
                    # Not in thie particular stream, may be in one of the
2073
2003
                    # other fallback vfs objects.
2205
2135
    """Content map generator reading from a VersionedFiles object."""
2206
2136
 
2207
2137
    def __init__(self, versioned_files, keys, nonlocal_keys=None,
2208
 
        global_map=None, raw_record_map=None, ordering='unordered'):
 
2138
        global_map=None, raw_record_map=None):
2209
2139
        """Create a _ContentMapGenerator.
2210
2140
 
2211
2141
        :param versioned_files: The versioned files that the texts are being
2219
2149
        :param raw_record_map: A unparsed raw record map to use for answering
2220
2150
            contents.
2221
2151
        """
2222
 
        _ContentMapGenerator.__init__(self, ordering=ordering)
2223
2152
        # The vf to source data from
2224
2153
        self.vf = versioned_files
2225
2154
        # The keys desired
2369
2298
    FLAGS is a comma separated list of flags about the record. Values include
2370
2299
        no-eol, line-delta, fulltext.
2371
2300
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
2372
 
        that the compressed data starts at.
 
2301
        that the the compressed data starts at.
2373
2302
    LENGTH is the ascii representation of the length of the data file.
2374
2303
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
2375
2304
        REVISION_ID.
2446
2375
                    line = "\n%s %s %s %s %s :" % (
2447
2376
                        key[-1], ','.join(options), pos, size,
2448
2377
                        self._dictionary_compress(parents))
2449
 
                    if type(line) is not str:
 
2378
                    if type(line) != str:
2450
2379
                        raise AssertionError(
2451
2380
                            'data must be utf8 was %s' % type(line))
2452
2381
                    lines.append(line)
2584
2513
        except KeyError:
2585
2514
            raise RevisionNotPresent(key, self)
2586
2515
 
2587
 
    def find_ancestry(self, keys):
2588
 
        """See CombinedGraphIndex.find_ancestry()"""
2589
 
        prefixes = set(key[:-1] for key in keys)
2590
 
        self._load_prefixes(prefixes)
2591
 
        result = {}
2592
 
        parent_map = {}
2593
 
        missing_keys = set()
2594
 
        pending_keys = list(keys)
2595
 
        # This assumes that keys will not reference parents in a different
2596
 
        # prefix, which is accurate so far.
2597
 
        while pending_keys:
2598
 
            key = pending_keys.pop()
2599
 
            if key in parent_map:
2600
 
                continue
2601
 
            prefix = key[:-1]
2602
 
            try:
2603
 
                suffix_parents = self._kndx_cache[prefix][0][key[-1]][4]
2604
 
            except KeyError:
2605
 
                missing_keys.add(key)
2606
 
            else:
2607
 
                parent_keys = tuple([prefix + (suffix,)
2608
 
                                     for suffix in suffix_parents])
2609
 
                parent_map[key] = parent_keys
2610
 
                pending_keys.extend([p for p in parent_keys
2611
 
                                        if p not in parent_map])
2612
 
        return parent_map, missing_keys
2613
 
 
2614
2516
    def get_parent_map(self, keys):
2615
2517
        """Get a map of the parents of keys.
2616
2518
 
2668
2570
        result = set()
2669
2571
        # Identify all key prefixes.
2670
2572
        # XXX: A bit hacky, needs polish.
2671
 
        if type(self._mapper) is ConstantMapper:
 
2573
        if type(self._mapper) == ConstantMapper:
2672
2574
            prefixes = [()]
2673
2575
        else:
2674
2576
            relpaths = set()
2706
2608
                    del self._history
2707
2609
                except NoSuchFile:
2708
2610
                    self._kndx_cache[prefix] = ({}, [])
2709
 
                    if type(self._mapper) is ConstantMapper:
 
2611
                    if type(self._mapper) == ConstantMapper:
2710
2612
                        # preserve behaviour for revisions.kndx etc.
2711
2613
                        self._init_index(path)
2712
2614
                    del self._cache
2788
2690
 
2789
2691
class _KeyRefs(object):
2790
2692
 
2791
 
    def __init__(self, track_new_keys=False):
 
2693
    def __init__(self):
2792
2694
        # dict mapping 'key' to 'set of keys referring to that key'
2793
2695
        self.refs = {}
2794
 
        if track_new_keys:
2795
 
            # set remembering all new keys
2796
 
            self.new_keys = set()
2797
 
        else:
2798
 
            self.new_keys = None
2799
 
 
2800
 
    def clear(self):
2801
 
        if self.refs:
2802
 
            self.refs.clear()
2803
 
        if self.new_keys:
2804
 
            self.new_keys.clear()
2805
2696
 
2806
2697
    def add_references(self, key, refs):
2807
2698
        # Record the new references
2814
2705
        # Discard references satisfied by the new key
2815
2706
        self.add_key(key)
2816
2707
 
2817
 
    def get_new_keys(self):
2818
 
        return self.new_keys
2819
 
    
2820
2708
    def get_unsatisfied_refs(self):
2821
2709
        return self.refs.iterkeys()
2822
2710
 
2823
 
    def _satisfy_refs_for_key(self, key):
 
2711
    def add_key(self, key):
2824
2712
        try:
2825
2713
            del self.refs[key]
2826
2714
        except KeyError:
2827
2715
            # No keys depended on this key.  That's ok.
2828
2716
            pass
2829
2717
 
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):
 
2718
    def add_keys(self, keys):
2837
2719
        for key in keys:
2838
 
            self._satisfy_refs_for_key(key)
 
2720
            self.add_key(key)
2839
2721
 
2840
2722
    def get_referrers(self):
2841
2723
        result = set()
2946
2828
        if not random_id:
2947
2829
            present_nodes = self._get_entries(keys)
2948
2830
            for (index, key, value, node_refs) in present_nodes:
2949
 
                parents = node_refs[:1]
2950
 
                # Sometimes these are passed as a list rather than a tuple
2951
 
                passed = static_tuple.as_tuples(keys[key])
2952
 
                passed_parents = passed[1][:1]
2953
2831
                if (value[0] != keys[key][0][0] or
2954
 
                    parents != passed_parents):
2955
 
                    node_refs = static_tuple.as_tuples(node_refs)
 
2832
                    node_refs[:1] != keys[key][1][:1]):
2956
2833
                    raise KnitCorrupt(self, "inconsistent details in add_records"
2957
 
                        ": %s %s" % ((value, node_refs), passed))
 
2834
                        ": %s %s" % ((value, node_refs), keys[key]))
2958
2835
                del keys[key]
2959
2836
        result = []
2960
2837
        if self._parents:
3008
2885
        # If updating this, you should also update
3009
2886
        # groupcompress._GCGraphIndex.get_missing_parents
3010
2887
        # We may have false positives, so filter those out.
3011
 
        self._key_dependencies.satisfy_refs_for_keys(
 
2888
        self._key_dependencies.add_keys(
3012
2889
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
3013
2890
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
3014
2891
 
3125
3002
            options.append('no-eol')
3126
3003
        return options
3127
3004
 
3128
 
    def find_ancestry(self, keys):
3129
 
        """See CombinedGraphIndex.find_ancestry()"""
3130
 
        return self._graph_index.find_ancestry(keys, 0)
3131
 
 
3132
3005
    def get_parent_map(self, keys):
3133
3006
        """Get a map of the parents of keys.
3134
3007
 
3221
3094
            opaque index memo. For _KnitKeyAccess the memo is (key, pos,
3222
3095
            length), where the key is the record key.
3223
3096
        """
3224
 
        if type(raw_data) is not str:
 
3097
        if type(raw_data) != str:
3225
3098
            raise AssertionError(
3226
3099
                'data must be plain bytes was %s' % type(raw_data))
3227
3100
        result = []
3310
3183
            length), where the index field is the write_index object supplied
3311
3184
            to the PackAccess object.
3312
3185
        """
3313
 
        if type(raw_data) is not str:
 
3186
        if type(raw_data) != str:
3314
3187
            raise AssertionError(
3315
3188
                'data must be plain bytes was %s' % type(raw_data))
3316
3189
        result = []
3417
3290
            raise exc_class, exc_value, exc_traceback
3418
3291
 
3419
3292
 
 
3293
# Deprecated, use PatienceSequenceMatcher instead
 
3294
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
 
3295
 
 
3296
 
3420
3297
def annotate_knit(knit, revision_id):
3421
3298
    """Annotate a knit with no cached annotations.
3422
3299
 
3425
3302
    recommended.
3426
3303
    """
3427
3304
    annotator = _KnitAnnotator(knit)
3428
 
    return iter(annotator.annotate_flat(revision_id))
3429
 
 
3430
 
 
3431
 
class _KnitAnnotator(annotate.Annotator):
 
3305
    return iter(annotator.annotate(revision_id))
 
3306
 
 
3307
 
 
3308
class _KnitAnnotator(object):
3432
3309
    """Build up the annotations for a text."""
3433
3310
 
3434
 
    def __init__(self, vf):
3435
 
        annotate.Annotator.__init__(self, vf)
3436
 
 
3437
 
        # TODO: handle Nodes which cannot be extracted
3438
 
        # self._ghosts = set()
3439
 
 
3440
 
        # Map from (key, parent_key) => matching_blocks, should be 'use once'
3441
 
        self._matching_blocks = {}
3442
 
 
3443
 
        # KnitContent objects
3444
 
        self._content_objects = {}
3445
 
        # The number of children that depend on this fulltext content object
3446
 
        self._num_compression_children = {}
3447
 
        # Delta records that need their compression parent before they can be
3448
 
        # expanded
3449
 
        self._pending_deltas = {}
3450
 
        # Fulltext records that are waiting for their parents fulltexts before
3451
 
        # they can be yielded for annotation
3452
 
        self._pending_annotation = {}
 
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 = {}
3453
3334
 
3454
3335
        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
3455
3402
 
3456
3403
    def _get_build_graph(self, key):
3457
3404
        """Get the graphs for building texts and annotations.
3465
3412
            passing to read_records_iter to start reading in the raw data from
3466
3413
            the pack file.
3467
3414
        """
 
3415
        if key in self._annotated_lines:
 
3416
            # Nothing to do
 
3417
            return []
3468
3418
        pending = set([key])
3469
3419
        records = []
3470
 
        ann_keys = set()
3471
 
        self._num_needed_children[key] = 1
 
3420
        generation = 0
 
3421
        kept_generation = 0
3472
3422
        while pending:
3473
3423
            # get all pending nodes
 
3424
            generation += 1
3474
3425
            this_iteration = pending
3475
 
            build_details = self._vf._index.get_build_details(this_iteration)
 
3426
            build_details = self._knit._index.get_build_details(this_iteration)
3476
3427
            self._all_build_details.update(build_details)
3477
 
            # new_nodes = self._vf._index._get_entries(this_iteration)
 
3428
            # new_nodes = self._knit._index._get_entries(this_iteration)
3478
3429
            pending = set()
3479
3430
            for key, details in build_details.iteritems():
3480
 
                (index_memo, compression_parent, parent_keys,
 
3431
                (index_memo, compression_parent, parents,
3481
3432
                 record_details) = details
3482
 
                self._parent_map[key] = parent_keys
3483
 
                self._heads_provider = None
 
3433
                self._revision_id_graph[key] = parents
3484
3434
                records.append((key, index_memo))
3485
3435
                # Do we actually need to check _annotated_lines?
3486
 
                pending.update([p for p in parent_keys
3487
 
                                   if p not in self._all_build_details])
3488
 
                if parent_keys:
3489
 
                    for parent_key in parent_keys:
3490
 
                        if parent_key in self._num_needed_children:
3491
 
                            self._num_needed_children[parent_key] += 1
3492
 
                        else:
3493
 
                            self._num_needed_children[parent_key] = 1
 
3436
                pending.update(p for p in parents
 
3437
                                 if p not in self._all_build_details)
3494
3438
                if compression_parent:
3495
 
                    if compression_parent in self._num_compression_children:
3496
 
                        self._num_compression_children[compression_parent] += 1
3497
 
                    else:
3498
 
                        self._num_compression_children[compression_parent] = 1
 
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
3450
 
3500
3451
            missing_versions = this_iteration.difference(build_details.keys())
3501
 
            if missing_versions:
3502
 
                for key in missing_versions:
3503
 
                    if key in self._parent_map and key in self._text_cache:
3504
 
                        # We already have this text ready, we just need to
3505
 
                        # yield it later so we get it annotated
3506
 
                        ann_keys.add(key)
3507
 
                        parent_keys = self._parent_map[key]
3508
 
                        for parent_key in parent_keys:
3509
 
                            if parent_key in self._num_needed_children:
3510
 
                                self._num_needed_children[parent_key] += 1
3511
 
                            else:
3512
 
                                self._num_needed_children[parent_key] = 1
3513
 
                        pending.update([p for p in parent_keys
3514
 
                                           if p not in self._all_build_details])
3515
 
                    else:
3516
 
                        raise errors.RevisionNotPresent(key, self._vf)
 
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]
3517
3469
        # Generally we will want to read the records in reverse order, because
3518
3470
        # we find the parent nodes after the children
3519
3471
        records.reverse()
3520
 
        return records, ann_keys
3521
 
 
3522
 
    def _get_needed_texts(self, key, pb=None):
3523
 
        # if True or len(self._vf._fallback_vfs) > 0:
3524
 
        if len(self._vf._fallback_vfs) > 0:
3525
 
            # If we have fallbacks, go to the generic path
3526
 
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
3527
 
                yield v
3528
 
            return
3529
 
        while True:
3530
 
            try:
3531
 
                records, ann_keys = self._get_build_graph(key)
3532
 
                for idx, (sub_key, text, num_lines) in enumerate(
3533
 
                                                self._extract_texts(records)):
3534
 
                    if pb is not None:
3535
 
                        pb.update('annotating', idx, len(records))
3536
 
                    yield sub_key, text, num_lines
3537
 
                for sub_key in ann_keys:
3538
 
                    text = self._text_cache[sub_key]
3539
 
                    num_lines = len(text) # bad assumption
3540
 
                    yield sub_key, text, num_lines
3541
 
                return
3542
 
            except errors.RetryWithNewPacks, e:
3543
 
                self._vf._access.reload_or_raise(e)
3544
 
                # The cached build_details are no longer valid
3545
 
                self._all_build_details.clear()
3546
 
 
3547
 
    def _cache_delta_blocks(self, key, compression_parent, delta, lines):
3548
 
        parent_lines = self._text_cache[compression_parent]
3549
 
        blocks = list(KnitContent.get_line_delta_blocks(delta, parent_lines, lines))
3550
 
        self._matching_blocks[(key, compression_parent)] = blocks
3551
 
 
3552
 
    def _expand_record(self, key, parent_keys, compression_parent, record,
3553
 
                       record_details):
3554
 
        delta = None
3555
 
        if compression_parent:
3556
 
            if compression_parent not in self._content_objects:
3557
 
                # Waiting for the parent
3558
 
                self._pending_deltas.setdefault(compression_parent, []).append(
3559
 
                    (key, parent_keys, record, record_details))
3560
 
                return None
3561
 
            # We have the basis parent, so expand the delta
3562
 
            num = self._num_compression_children[compression_parent]
3563
 
            num -= 1
3564
 
            if num == 0:
3565
 
                base_content = self._content_objects.pop(compression_parent)
3566
 
                self._num_compression_children.pop(compression_parent)
3567
 
            else:
3568
 
                self._num_compression_children[compression_parent] = num
3569
 
                base_content = self._content_objects[compression_parent]
3570
 
            # It is tempting to want to copy_base_content=False for the last
3571
 
            # child object. However, whenever noeol=False,
3572
 
            # self._text_cache[parent_key] is content._lines. So mutating it
3573
 
            # gives very bad results.
3574
 
            # The alternative is to copy the lines into text cache, but then we
3575
 
            # are copying anyway, so just do it here.
3576
 
            content, delta = self._vf._factory.parse_record(
3577
 
                key, record, record_details, base_content,
3578
 
                copy_base_content=True)
3579
 
        else:
3580
 
            # Fulltext record
3581
 
            content, _ = self._vf._factory.parse_record(
3582
 
                key, record, record_details, None)
3583
 
        if self._num_compression_children.get(key, 0) > 0:
3584
 
            self._content_objects[key] = content
3585
 
        lines = content.text()
3586
 
        self._text_cache[key] = lines
3587
 
        if delta is not None:
3588
 
            self._cache_delta_blocks(key, compression_parent, delta, lines)
3589
 
        return lines
3590
 
 
3591
 
    def _get_parent_annotations_and_matches(self, key, text, parent_key):
3592
 
        """Get the list of annotations for the parent, and the matching lines.
3593
 
 
3594
 
        :param text: The opaque value given by _get_needed_texts
3595
 
        :param parent_key: The key for the parent text
3596
 
        :return: (parent_annotations, matching_blocks)
3597
 
            parent_annotations is a list as long as the number of lines in
3598
 
                parent
3599
 
            matching_blocks is a list of (parent_idx, text_idx, len) tuples
3600
 
                indicating which lines match between the two texts
3601
 
        """
3602
 
        block_key = (key, parent_key)
3603
 
        if block_key in self._matching_blocks:
3604
 
            blocks = self._matching_blocks.pop(block_key)
3605
 
            parent_annotations = self._annotations_cache[parent_key]
3606
 
            return parent_annotations, blocks
3607
 
        return annotate.Annotator._get_parent_annotations_and_matches(self,
3608
 
            key, text, parent_key)
3609
 
 
3610
 
    def _process_pending(self, key):
3611
 
        """The content for 'key' was just processed.
3612
 
 
3613
 
        Determine if there is any more pending work to be processed.
3614
 
        """
3615
 
        to_return = []
3616
 
        if key in self._pending_deltas:
3617
 
            compression_parent = key
3618
 
            children = self._pending_deltas.pop(key)
3619
 
            for child_key, parent_keys, record, record_details in children:
3620
 
                lines = self._expand_record(child_key, parent_keys,
3621
 
                                            compression_parent,
3622
 
                                            record, record_details)
3623
 
                if self._check_ready_for_annotations(child_key, parent_keys):
3624
 
                    to_return.append(child_key)
3625
 
        # Also check any children that are waiting for this parent to be
3626
 
        # annotation ready
3627
 
        if key in self._pending_annotation:
3628
 
            children = self._pending_annotation.pop(key)
3629
 
            to_return.extend([c for c, p_keys in children
3630
 
                              if self._check_ready_for_annotations(c, p_keys)])
3631
 
        return to_return
3632
 
 
3633
 
    def _check_ready_for_annotations(self, key, parent_keys):
3634
 
        """return true if this text is ready to be yielded.
3635
 
 
3636
 
        Otherwise, this will return False, and queue the text into
3637
 
        self._pending_annotation
3638
 
        """
3639
 
        for parent_key in parent_keys:
3640
 
            if parent_key not in self._annotations_cache:
3641
 
                # still waiting on at least one parent text, so queue it up
3642
 
                # Note that if there are multiple parents, we need to wait
3643
 
                # for all of them.
3644
 
                self._pending_annotation.setdefault(parent_key,
3645
 
                    []).append((key, parent_keys))
3646
 
                return False
3647
 
        return True
3648
 
 
3649
 
    def _extract_texts(self, records):
3650
 
        """Extract the various texts needed based on records"""
 
3472
        return records
 
3473
 
 
3474
    def _annotate_records(self, records):
 
3475
        """Build the annotations for the listed records."""
3651
3476
        # We iterate in the order read, rather than a strict order requested
3652
3477
        # However, process what we can, and put off to the side things that
3653
3478
        # still need parents, cleaning them up when those parents are
3654
3479
        # processed.
3655
 
        # Basic data flow:
3656
 
        #   1) As 'records' are read, see if we can expand these records into
3657
 
        #      Content objects (and thus lines)
3658
 
        #   2) If a given line-delta is waiting on its compression parent, it
3659
 
        #      gets queued up into self._pending_deltas, otherwise we expand
3660
 
        #      it, and put it into self._text_cache and self._content_objects
3661
 
        #   3) If we expanded the text, we will then check to see if all
3662
 
        #      parents have also been processed. If so, this text gets yielded,
3663
 
        #      else this record gets set aside into pending_annotation
3664
 
        #   4) Further, if we expanded the text in (2), we will then check to
3665
 
        #      see if there are any children in self._pending_deltas waiting to
3666
 
        #      also be processed. If so, we go back to (2) for those
3667
 
        #   5) Further again, if we yielded the text, we can then check if that
3668
 
        #      'unlocks' any of the texts in pending_annotations, which should
3669
 
        #      then get yielded as well
3670
 
        # Note that both steps 4 and 5 are 'recursive' in that unlocking one
3671
 
        # compression child could unlock yet another, and yielding a fulltext
3672
 
        # will also 'unlock' the children that are waiting on that annotation.
3673
 
        # (Though also, unlocking 1 parent's fulltext, does not unlock a child
3674
 
        # if other parents are also waiting.)
3675
 
        # We want to yield content before expanding child content objects, so
3676
 
        # that we know when we can re-use the content lines, and the annotation
3677
 
        # code can know when it can stop caching fulltexts, as well.
3678
 
 
3679
 
        # Children that are missing their compression parent
3680
 
        pending_deltas = {}
3681
 
        for (key, record, digest) in self._vf._read_records_iter(records):
3682
 
            # ghosts?
3683
 
            details = self._all_build_details[key]
3684
 
            (_, compression_parent, parent_keys, record_details) = details
3685
 
            lines = self._expand_record(key, parent_keys, compression_parent,
3686
 
                                        record, record_details)
3687
 
            if lines is None:
3688
 
                # Pending delta should be queued up
 
3480
        for (rev_id, record,
 
3481
             digest) in self._knit._read_records_iter(records):
 
3482
            if rev_id in self._annotated_lines:
3689
3483
                continue
3690
 
            # At this point, we may be able to yield this content, if all
3691
 
            # parents are also finished
3692
 
            yield_this_text = self._check_ready_for_annotations(key,
3693
 
                                                                parent_keys)
3694
 
            if yield_this_text:
3695
 
                # All parents present
3696
 
                yield key, lines, len(lines)
3697
 
            to_process = self._process_pending(key)
3698
 
            while to_process:
3699
 
                this_process = to_process
3700
 
                to_process = []
3701
 
                for key in this_process:
3702
 
                    lines = self._text_cache[key]
3703
 
                    yield key, lines, len(lines)
3704
 
                    to_process.extend(self._process_pending(key))
 
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
 
3705
3611
 
3706
3612
try:
3707
 
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
3708
 
except ImportError, e:
3709
 
    osutils.failed_to_load_extension(e)
 
3613
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
 
3614
except ImportError:
3710
3615
    from bzrlib._knit_load_data_py import _load_data_py as _load_data