/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/versionedfile.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/versionedfile.py
1
 
# Copyright (C) 2006-2011 Canonical Ltd
 
1
# Copyright (C) 2006-2010 Canonical Ltd
 
2
#
 
3
# Authors:
 
4
#   Johan Rydberg <jrydberg@gnu.org>
2
5
#
3
6
# This program is free software; you can redistribute it and/or modify
4
7
# it under the terms of the GNU General Public License as published by
16
19
 
17
20
"""Versioned text file storage api."""
18
21
 
19
 
from __future__ import absolute_import
20
 
 
21
22
from copy import copy
22
 
import itertools
 
23
from cStringIO import StringIO
23
24
import os
24
25
import struct
25
26
from zlib import adler32
26
27
 
27
 
from ..lazy_import import lazy_import
 
28
from bzrlib.lazy_import import lazy_import
28
29
lazy_import(globals(), """
29
 
from breezy import (
 
30
import urllib
 
31
 
 
32
from bzrlib import (
30
33
    annotate,
31
 
    bencode,
32
34
    errors,
33
35
    graph as _mod_graph,
 
36
    groupcompress,
 
37
    index,
 
38
    knit,
34
39
    osutils,
35
40
    multiparent,
36
41
    tsort,
37
42
    revision,
38
 
    urlutils,
39
 
    )
40
 
from breezy.bzr import (
41
 
    groupcompress,
42
 
    index,
43
 
    knit,
44
 
    )
 
43
    ui,
 
44
    )
 
45
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
 
46
from bzrlib.transport.memory import MemoryTransport
45
47
""")
46
 
from ..registry import Registry
47
 
from ..sixish import (
48
 
    BytesIO,
49
 
    viewitems,
50
 
    viewvalues,
51
 
    zip,
52
 
    )
53
 
from ..textmerge import TextMerge
 
48
from bzrlib.registry import Registry
 
49
from bzrlib.symbol_versioning import *
 
50
from bzrlib.textmerge import TextMerge
 
51
from bzrlib import bencode
54
52
 
55
53
 
56
54
adapter_registry = Registry()
57
 
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'breezy.bzr.knit',
 
55
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
58
56
    'DeltaPlainToFullText')
59
 
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'breezy.bzr.knit',
 
57
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
60
58
    'FTPlainToFullText')
61
59
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
62
 
    'breezy.bzr.knit', 'DeltaAnnotatedToUnannotated')
 
60
    'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
63
61
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
64
 
    'breezy.bzr.knit', 'DeltaAnnotatedToFullText')
 
62
    'bzrlib.knit', 'DeltaAnnotatedToFullText')
65
63
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
66
 
    'breezy.bzr.knit', 'FTAnnotatedToUnannotated')
 
64
    'bzrlib.knit', 'FTAnnotatedToUnannotated')
67
65
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
68
 
    'breezy.bzr.knit', 'FTAnnotatedToFullText')
 
66
    'bzrlib.knit', 'FTAnnotatedToFullText')
69
67
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
70
 
#     'breezy.bzr.knit', 'FTAnnotatedToChunked')
 
68
#     'bzrlib.knit', 'FTAnnotatedToChunked')
71
69
 
72
70
 
73
71
class ContentFactory(object):
122
120
        if storage_kind == 'chunked':
123
121
            return self._chunks
124
122
        elif storage_kind == 'fulltext':
125
 
            return b''.join(self._chunks)
 
123
            return ''.join(self._chunks)
126
124
        raise errors.UnavailableRepresentation(self.key, storage_kind,
127
125
            self.storage_kind)
128
126
 
149
147
        self.storage_kind = 'fulltext'
150
148
        self.key = key
151
149
        self.parents = parents
152
 
        if not isinstance(text, bytes):
153
 
            raise TypeError(text)
154
150
        self._text = text
155
151
 
156
152
    def get_bytes_as(self, storage_kind):
210
206
            yield record
211
207
 
212
208
 
213
 
class _MPDiffGenerator(object):
214
 
    """Pull out the functionality for generating mp_diffs."""
215
 
 
216
 
    def __init__(self, vf, keys):
217
 
        self.vf = vf
218
 
        # This is the order the keys were requested in
219
 
        self.ordered_keys = tuple(keys)
220
 
        # keys + their parents, what we need to compute the diffs
221
 
        self.needed_keys = ()
222
 
        # Map from key: mp_diff
223
 
        self.diffs = {}
224
 
        # Map from key: parents_needed (may have ghosts)
225
 
        self.parent_map = {}
226
 
        # Parents that aren't present
227
 
        self.ghost_parents = ()
228
 
        # Map from parent_key => number of children for this text
229
 
        self.refcounts = {}
230
 
        # Content chunks that are cached while we still need them
231
 
        self.chunks = {}
232
 
 
233
 
    def _find_needed_keys(self):
234
 
        """Find the set of keys we need to request.
235
 
 
236
 
        This includes all the original keys passed in, and the non-ghost
237
 
        parents of those keys.
238
 
 
239
 
        :return: (needed_keys, refcounts)
240
 
            needed_keys is the set of all texts we need to extract
241
 
            refcounts is a dict of {key: num_children} letting us know when we
242
 
                no longer need to cache a given parent text
243
 
        """
244
 
        # All the keys and their parents
245
 
        needed_keys = set(self.ordered_keys)
246
 
        parent_map = self.vf.get_parent_map(needed_keys)
247
 
        self.parent_map = parent_map
248
 
        # TODO: Should we be using a different construct here? I think this
249
 
        #       uses difference_update internally, and we expect the result to
250
 
        #       be tiny
251
 
        missing_keys = needed_keys.difference(parent_map)
252
 
        if missing_keys:
253
 
            raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
254
 
        # Parents that might be missing. They are allowed to be ghosts, but we
255
 
        # should check for them
256
 
        refcounts = {}
257
 
        setdefault = refcounts.setdefault
258
 
        just_parents = set()
259
 
        for child_key, parent_keys in viewitems(parent_map):
260
 
            if not parent_keys:
261
 
                # parent_keys may be None if a given VersionedFile claims to
262
 
                # not support graph operations.
263
 
                continue
264
 
            just_parents.update(parent_keys)
265
 
            needed_keys.update(parent_keys)
266
 
            for p in parent_keys:
267
 
                refcounts[p] = setdefault(p, 0) + 1
268
 
        just_parents.difference_update(parent_map)
269
 
        # Remove any parents that are actually ghosts from the needed set
270
 
        self.present_parents = set(self.vf.get_parent_map(just_parents))
271
 
        self.ghost_parents = just_parents.difference(self.present_parents)
272
 
        needed_keys.difference_update(self.ghost_parents)
273
 
        self.needed_keys = needed_keys
274
 
        self.refcounts = refcounts
275
 
        return needed_keys, refcounts
276
 
 
277
 
    def _compute_diff(self, key, parent_lines, lines):
278
 
        """Compute a single mp_diff, and store it in self._diffs"""
279
 
        if len(parent_lines) > 0:
280
 
            # XXX: _extract_blocks is not usefully defined anywhere...
281
 
            #      It was meant to extract the left-parent diff without
282
 
            #      having to recompute it for Knit content (pack-0.92,
283
 
            #      etc). That seems to have regressed somewhere
284
 
            left_parent_blocks = self.vf._extract_blocks(key,
285
 
                parent_lines[0], lines)
286
 
        else:
287
 
            left_parent_blocks = None
288
 
        diff = multiparent.MultiParent.from_lines(lines,
289
 
                    parent_lines, left_parent_blocks)
290
 
        self.diffs[key] = diff
291
 
 
292
 
    def _process_one_record(self, key, this_chunks):
293
 
        parent_keys = None
294
 
        if key in self.parent_map:
295
 
            # This record should be ready to diff, since we requested
296
 
            # content in 'topological' order
297
 
            parent_keys = self.parent_map.pop(key)
298
 
            # If a VersionedFile claims 'no-graph' support, then it may return
299
 
            # None for any parent request, so we replace it with an empty tuple
300
 
            if parent_keys is None:
301
 
                parent_keys = ()
302
 
            parent_lines = []
303
 
            for p in parent_keys:
304
 
                # Alternatively we could check p not in self.needed_keys, but
305
 
                # ghost_parents should be tiny versus huge
306
 
                if p in self.ghost_parents:
307
 
                    continue
308
 
                refcount = self.refcounts[p]
309
 
                if refcount == 1: # Last child reference
310
 
                    self.refcounts.pop(p)
311
 
                    parent_chunks = self.chunks.pop(p)
312
 
                else:
313
 
                    self.refcounts[p] = refcount - 1
314
 
                    parent_chunks = self.chunks[p]
315
 
                p_lines = osutils.chunks_to_lines(parent_chunks)
316
 
                # TODO: Should we cache the line form? We did the
317
 
                #       computation to get it, but storing it this way will
318
 
                #       be less memory efficient...
319
 
                parent_lines.append(p_lines)
320
 
                del p_lines
321
 
            lines = osutils.chunks_to_lines(this_chunks)
322
 
            # Since we needed the lines, we'll go ahead and cache them this way
323
 
            this_chunks = lines
324
 
            self._compute_diff(key, parent_lines, lines)
325
 
            del lines
326
 
        # Is this content required for any more children?
327
 
        if key in self.refcounts:
328
 
            self.chunks[key] = this_chunks
329
 
 
330
 
    def _extract_diffs(self):
331
 
        needed_keys, refcounts = self._find_needed_keys()
332
 
        for record in self.vf.get_record_stream(needed_keys,
333
 
                                                'topological', True):
334
 
            if record.storage_kind == 'absent':
335
 
                raise errors.RevisionNotPresent(record.key, self.vf)
336
 
            self._process_one_record(record.key,
337
 
                                     record.get_bytes_as('chunked'))
338
 
        
339
 
    def compute_diffs(self):
340
 
        self._extract_diffs()
341
 
        dpop = self.diffs.pop
342
 
        return [dpop(k) for k in self.ordered_keys]
343
 
 
344
 
 
345
209
class VersionedFile(object):
346
210
    """Versioned text file storage.
347
211
 
466
330
    def _check_lines_not_unicode(self, lines):
467
331
        """Check that lines being added to a versioned file are not unicode."""
468
332
        for line in lines:
469
 
            if not isinstance(line, bytes):
 
333
            if line.__class__ is not str:
470
334
                raise errors.BzrBadParameterUnicode("lines")
471
335
 
472
336
    def _check_lines_are_lines(self, lines):
473
337
        """Check that the lines really are full lines without inline EOL."""
474
338
        for line in lines:
475
 
            if b'\n' in line[:-1]:
 
339
            if '\n' in line[:-1]:
476
340
                raise errors.BzrBadParameterContainsNewline("lines")
477
341
 
478
342
    def get_format_signature(self):
484
348
 
485
349
    def make_mpdiffs(self, version_ids):
486
350
        """Create multiparent diffs for specified versions."""
487
 
        # XXX: Can't use _MPDiffGenerator just yet. This is because version_ids
488
 
        #      is a list of strings, not keys. And while self.get_record_stream
489
 
        #      is supported, it takes *keys*, while self.get_parent_map() takes
490
 
        #      strings... *sigh*
491
351
        knit_versions = set()
492
352
        knit_versions.update(version_ids)
493
353
        parent_map = self.get_parent_map(version_ids)
497
357
            except KeyError:
498
358
                raise errors.RevisionNotPresent(version_id, self)
499
359
        # We need to filter out ghosts, because we can't diff against them.
500
 
        knit_versions = set(self.get_parent_map(knit_versions))
 
360
        knit_versions = set(self.get_parent_map(knit_versions).keys())
501
361
        lines = dict(zip(knit_versions,
502
362
            self._get_lf_split_line_list(knit_versions)))
503
363
        diffs = []
541
401
        for version, parent_ids, expected_sha1, mpdiff in records:
542
402
            needed_parents.update(p for p in parent_ids
543
403
                                  if not mpvf.has_version(p))
544
 
        present_parents = set(self.get_parent_map(needed_parents))
 
404
        present_parents = set(self.get_parent_map(needed_parents).keys())
545
405
        for parent_id, lines in zip(present_parents,
546
 
                self._get_lf_split_line_list(present_parents)):
 
406
                                 self._get_lf_split_line_list(present_parents)):
547
407
            mpvf.add_version(lines, parent_id, [])
548
 
        for (version, parent_ids, expected_sha1, mpdiff), lines in zip(
549
 
                records, mpvf.get_line_list(versions)):
 
408
        for (version, parent_ids, expected_sha1, mpdiff), lines in\
 
409
            zip(records, mpvf.get_line_list(versions)):
550
410
            if len(parent_ids) == 1:
551
411
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
552
412
                    mpvf.get_diff(parent_ids[0]).num_lines()))
574
434
        Raises RevisionNotPresent if version is not present in
575
435
        file history.
576
436
        """
577
 
        return b''.join(self.get_lines(version_id))
 
437
        return ''.join(self.get_lines(version_id))
578
438
    get_string = get_text
579
439
 
580
440
    def get_texts(self, version_ids):
583
443
        Raises RevisionNotPresent if version is not present in
584
444
        file history.
585
445
        """
586
 
        return [b''.join(self.get_lines(v)) for v in version_ids]
 
446
        return [''.join(self.get_lines(v)) for v in version_ids]
587
447
 
588
448
    def get_lines(self, version_id):
589
449
        """Return version contents as a sequence of lines.
594
454
        raise NotImplementedError(self.get_lines)
595
455
 
596
456
    def _get_lf_split_line_list(self, version_ids):
597
 
        return [BytesIO(t).readlines() for t in self.get_texts(version_ids)]
 
457
        return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
598
458
 
599
459
    def get_ancestry(self, version_ids, topo_sorted=True):
600
460
        """Return a list of all ancestors of given version(s). This
605
465
 
606
466
        Must raise RevisionNotPresent if any of the given versions are
607
467
        not present in file history."""
 
468
        if isinstance(version_ids, basestring):
 
469
            version_ids = [version_ids]
608
470
        raise NotImplementedError(self.get_ancestry)
609
471
 
610
472
    def get_ancestry_with_ghosts(self, version_ids):
671
533
        """
672
534
        raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
673
535
 
674
 
    def plan_merge(self, ver_a, ver_b, base=None):
 
536
    def plan_merge(self, ver_a, ver_b):
675
537
        """Return pseudo-annotation indicating how the two versions merge.
676
538
 
677
539
        This is computed between versions a and b and their common
793
655
    def map(self, key):
794
656
        """Map key to an underlying storage identifier.
795
657
 
796
 
        :param key: A key tuple e.g. (b'file-id', b'revision-id').
 
658
        :param key: A key tuple e.g. ('file-id', 'revision-id').
797
659
        :return: An underlying storage identifier, specific to the partitioning
798
660
            mechanism.
799
661
        """
830
692
 
831
693
    def map(self, key):
832
694
        """See KeyMapper.map()."""
833
 
        return urlutils.quote(self._map(key))
 
695
        return urllib.quote(self._map(key))
834
696
 
835
697
    def unmap(self, partition_id):
836
698
        """See KeyMapper.unmap()."""
837
 
        return self._unmap(urlutils.unquote(partition_id))
 
699
        return self._unmap(urllib.unquote(partition_id))
838
700
 
839
701
 
840
702
class PrefixMapper(URLEscapeMapper):
845
707
 
846
708
    def _map(self, key):
847
709
        """See KeyMapper.map()."""
848
 
        return key[0].decode('utf-8')
 
710
        return key[0]
849
711
 
850
712
    def _unmap(self, partition_id):
851
713
        """See KeyMapper.unmap()."""
852
 
        return (partition_id.encode('utf-8'),)
 
714
        return (partition_id,)
853
715
 
854
716
 
855
717
class HashPrefixMapper(URLEscapeMapper):
861
723
    def _map(self, key):
862
724
        """See KeyMapper.map()."""
863
725
        prefix = self._escape(key[0])
864
 
        return "%02x/%s" % (adler32(prefix) & 0xff, prefix.decode('utf-8'))
 
726
        return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
865
727
 
866
728
    def _escape(self, prefix):
867
729
        """No escaping needed here."""
869
731
 
870
732
    def _unmap(self, partition_id):
871
733
        """See KeyMapper.unmap()."""
872
 
        return (self._unescape(osutils.basename(partition_id)).encode('utf-8'),)
 
734
        return (self._unescape(osutils.basename(partition_id)),)
873
735
 
874
736
    def _unescape(self, basename):
875
737
        """No unescaping needed for HashPrefixMapper."""
882
744
    This mapper is for use with a transport based backend.
883
745
    """
884
746
 
885
 
    _safe = bytearray(b"abcdefghijklmnopqrstuvwxyz0123456789-_@,.")
 
747
    _safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
886
748
 
887
749
    def _escape(self, prefix):
888
750
        """Turn a key element into a filesystem safe string.
889
751
 
890
 
        This is similar to a plain urlutils.quote, except
 
752
        This is similar to a plain urllib.quote, except
891
753
        it uses specific safe characters, so that it doesn't
892
754
        have to translate a lot of valid file ids.
893
755
        """
894
756
        # @ does not get escaped. This is because it is a valid
895
757
        # filesystem character we use all the time, and it looks
896
758
        # a lot better than seeing %40 all the time.
897
 
        r = [(c in self._safe) and chr(c) or ('%%%02x' % c)
898
 
                for c in bytearray(prefix)]
899
 
        return ''.join(r).encode('ascii')
 
759
        r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
 
760
             for c in prefix]
 
761
        return ''.join(r)
900
762
 
901
763
    def _unescape(self, basename):
902
764
        """Escaped names are easily unescaped by urlutils."""
903
 
        return urlutils.unquote(basename)
 
765
        return urllib.unquote(basename)
904
766
 
905
767
 
906
768
def make_versioned_files_factory(versioned_file_factory, mapper):
912
774
    """
913
775
    def factory(transport):
914
776
        return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
915
 
            lambda: True)
 
777
            lambda:True)
916
778
    return factory
917
779
 
918
780
 
927
789
 
928
790
    The keyspace is expressed via simple tuples. Any instance of VersionedFiles
929
791
    may have a different length key-size, but that size will be constant for
930
 
    all texts added to or retrieved from it. For instance, breezy uses
 
792
    all texts added to or retrieved from it. For instance, bzrlib uses
931
793
    instances with a key-size of 2 for storing user files in a repository, with
932
794
    the first element the fileid, and the second the version of that file.
933
795
 
934
796
    The use of tuples allows a single code base to support several different
935
797
    uses with only the mapping logic changing from instance to instance.
936
 
 
937
 
    :ivar _immediate_fallback_vfs: For subclasses that support stacking,
938
 
        this is a list of other VersionedFiles immediately underneath this
939
 
        one.  They may in turn each have further fallbacks.
940
798
    """
941
799
 
942
800
    def add_lines(self, key, parents, lines, parent_texts=None,
978
836
        """
979
837
        raise NotImplementedError(self.add_lines)
980
838
 
 
839
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
 
840
        """Add a text to the store.
 
841
 
 
842
        This is a private function for use by CommitBuilder.
 
843
 
 
844
        :param key: The key tuple of the text to add. If the last element is
 
845
            None, a CHK string will be generated during the addition.
 
846
        :param parents: The parents key tuples of the text to add.
 
847
        :param text: A string containing the text to be committed.
 
848
        :param nostore_sha: Raise ExistingContent and do not add the lines to
 
849
            the versioned file if the digest of the lines matches this.
 
850
        :param random_id: If True a random id has been selected rather than
 
851
            an id determined by some deterministic process such as a converter
 
852
            from a foreign VCS. When True the backend may choose not to check
 
853
            for uniqueness of the resulting key within the versioned file, so
 
854
            this should only be done when the result is expected to be unique
 
855
            anyway.
 
856
        :param check_content: If True, the lines supplied are verified to be
 
857
            bytestrings that are correctly formed lines.
 
858
        :return: The text sha1, the number of bytes in the text, and an opaque
 
859
                 representation of the inserted version which can be provided
 
860
                 back to future _add_text calls in the parent_texts dictionary.
 
861
        """
 
862
        # The default implementation just thunks over to .add_lines(),
 
863
        # inefficient, but it works.
 
864
        return self.add_lines(key, parents, osutils.split_lines(text),
 
865
                              nostore_sha=nostore_sha,
 
866
                              random_id=random_id,
 
867
                              check_content=True)
 
868
 
981
869
    def add_mpdiffs(self, records):
982
870
        """Add mpdiffs to this VersionedFile.
983
871
 
1003
891
                continue
1004
892
            mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
1005
893
                record.key, [])
1006
 
        for (key, parent_keys, expected_sha1, mpdiff), lines in zip(
1007
 
                records, mpvf.get_line_list(versions)):
 
894
        for (key, parent_keys, expected_sha1, mpdiff), lines in\
 
895
            zip(records, mpvf.get_line_list(versions)):
1008
896
            if len(parent_keys) == 1:
1009
897
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
1010
898
                    mpvf.get_diff(parent_keys[0]).num_lines()))
1051
939
    def _check_lines_not_unicode(self, lines):
1052
940
        """Check that lines being added to a versioned file are not unicode."""
1053
941
        for line in lines:
1054
 
            if line.__class__ is not bytes:
 
942
            if line.__class__ is not str:
1055
943
                raise errors.BzrBadParameterUnicode("lines")
1056
944
 
1057
945
    def _check_lines_are_lines(self, lines):
1058
946
        """Check that the lines really are full lines without inline EOL."""
1059
947
        for line in lines:
1060
 
            if b'\n' in line[:-1]:
 
948
            if '\n' in line[:-1]:
1061
949
                raise errors.BzrBadParameterContainsNewline("lines")
1062
950
 
1063
951
    def get_known_graph_ancestry(self, keys):
1068
956
        while pending:
1069
957
            this_parent_map = self.get_parent_map(pending)
1070
958
            parent_map.update(this_parent_map)
1071
 
            pending = set(itertools.chain.from_iterable(
1072
 
                viewvalues(this_parent_map)))
1073
 
            pending.difference_update(parent_map)
 
959
            pending = set()
 
960
            map(pending.update, this_parent_map.itervalues())
 
961
            pending = pending.difference(parent_map)
1074
962
        kg = _mod_graph.KnownGraph(parent_map)
1075
963
        return kg
1076
964
 
1107
995
        """
1108
996
        raise NotImplementedError(self.get_sha1s)
1109
997
 
1110
 
    __contains__ = index._has_key_from_parent_map
 
998
    has_key = index._has_key_from_parent_map
1111
999
 
1112
1000
    def get_missing_compression_parent_keys(self):
1113
1001
        """Return an iterable of keys of missing compression parents.
1159
1047
 
1160
1048
    def make_mpdiffs(self, keys):
1161
1049
        """Create multiparent diffs for specified keys."""
1162
 
        generator = _MPDiffGenerator(self, keys)
1163
 
        return generator.compute_diffs()
1164
 
 
1165
 
    def get_annotator(self):
1166
 
        return annotate.Annotator(self)
 
1050
        keys_order = tuple(keys)
 
1051
        keys = frozenset(keys)
 
1052
        knit_keys = set(keys)
 
1053
        parent_map = self.get_parent_map(keys)
 
1054
        for parent_keys in parent_map.itervalues():
 
1055
            if parent_keys:
 
1056
                knit_keys.update(parent_keys)
 
1057
        missing_keys = keys - set(parent_map)
 
1058
        if missing_keys:
 
1059
            raise errors.RevisionNotPresent(list(missing_keys)[0], self)
 
1060
        # We need to filter out ghosts, because we can't diff against them.
 
1061
        maybe_ghosts = knit_keys - keys
 
1062
        ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
 
1063
        knit_keys.difference_update(ghosts)
 
1064
        lines = {}
 
1065
        chunks_to_lines = osutils.chunks_to_lines
 
1066
        for record in self.get_record_stream(knit_keys, 'topological', True):
 
1067
            lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
 
1068
            # line_block_dict = {}
 
1069
            # for parent, blocks in record.extract_line_blocks():
 
1070
            #   line_blocks[parent] = blocks
 
1071
            # line_blocks[record.key] = line_block_dict
 
1072
        diffs = []
 
1073
        for key in keys_order:
 
1074
            target = lines[key]
 
1075
            parents = parent_map[key] or []
 
1076
            # Note that filtering knit_keys can lead to a parent difference
 
1077
            # between the creation and the application of the mpdiff.
 
1078
            parent_lines = [lines[p] for p in parents if p in knit_keys]
 
1079
            if len(parent_lines) > 0:
 
1080
                left_parent_blocks = self._extract_blocks(key, parent_lines[0],
 
1081
                    target)
 
1082
            else:
 
1083
                left_parent_blocks = None
 
1084
            diffs.append(multiparent.MultiParent.from_lines(target,
 
1085
                parent_lines, left_parent_blocks))
 
1086
        return diffs
1167
1087
 
1168
1088
    missing_keys = index._missing_keys_from_parent_map
1169
1089
 
1170
1090
    def _extract_blocks(self, version_id, source, target):
1171
1091
        return None
1172
1092
 
1173
 
    def _transitive_fallbacks(self):
1174
 
        """Return the whole stack of fallback versionedfiles.
1175
 
 
1176
 
        This VersionedFiles may have a list of fallbacks, but it doesn't
1177
 
        necessarily know about the whole stack going down, and it can't know
1178
 
        at open time because they may change after the objects are opened.
1179
 
        """
1180
 
        all_fallbacks = []
1181
 
        for a_vfs in self._immediate_fallback_vfs:
1182
 
            all_fallbacks.append(a_vfs)
1183
 
            all_fallbacks.extend(a_vfs._transitive_fallbacks())
1184
 
        return all_fallbacks
1185
 
 
1186
1093
 
1187
1094
class ThunkedVersionedFiles(VersionedFiles):
1188
1095
    """Storage for many versioned files thunked onto a 'VersionedFile' class.
1252
1159
            result.append((prefix + (origin,), line))
1253
1160
        return result
1254
1161
 
 
1162
    def get_annotator(self):
 
1163
        return annotate.Annotator(self)
 
1164
 
1255
1165
    def check(self, progress_bar=None, keys=None):
1256
1166
        """See VersionedFiles.check()."""
1257
1167
        # XXX: This is over-enthusiastic but as we only thunk for Weaves today
1271
1181
        """
1272
1182
        prefixes = self._partition_keys(keys)
1273
1183
        result = {}
1274
 
        for prefix, suffixes in viewitems(prefixes):
 
1184
        for prefix, suffixes in prefixes.items():
1275
1185
            path = self._mapper.map(prefix)
1276
1186
            vf = self._get_vf(path)
1277
1187
            parent_map = vf.get_parent_map(suffixes)
1278
 
            for key, parents in viewitems(parent_map):
 
1188
            for key, parents in parent_map.items():
1279
1189
                result[prefix + (key,)] = tuple(
1280
1190
                    prefix + (parent,) for parent in parents)
1281
1191
        return result
1294
1204
            prefix_keys.append(key[-1])
1295
1205
        return result
1296
1206
 
1297
 
    def _iter_all_prefixes(self):
 
1207
    def _get_all_prefixes(self):
1298
1208
        # Identify all key prefixes.
1299
1209
        # XXX: A bit hacky, needs polish.
1300
 
        if isinstance(self._mapper, ConstantMapper):
 
1210
        if type(self._mapper) == ConstantMapper:
1301
1211
            paths = [self._mapper.map(())]
1302
1212
            prefixes = [()]
1303
1213
        else:
1327
1237
    def _iter_keys_vf(self, keys):
1328
1238
        prefixes = self._partition_keys(keys)
1329
1239
        sha1s = {}
1330
 
        for prefix, suffixes in viewitems(prefixes):
 
1240
        for prefix, suffixes in prefixes.items():
1331
1241
            path = self._mapper.map(prefix)
1332
1242
            vf = self._get_vf(path)
1333
1243
            yield prefix, suffixes, vf
1335
1245
    def get_sha1s(self, keys):
1336
1246
        """See VersionedFiles.get_sha1s()."""
1337
1247
        sha1s = {}
1338
 
        for prefix, suffixes, vf in self._iter_keys_vf(keys):
 
1248
        for prefix,suffixes, vf in self._iter_keys_vf(keys):
1339
1249
            vf_sha1s = vf.get_sha1s(suffixes)
1340
 
            for suffix, sha1 in viewitems(vf_sha1s):
 
1250
            for suffix, sha1 in vf_sha1s.iteritems():
1341
1251
                sha1s[prefix + (suffix,)] = sha1
1342
1252
        return sha1s
1343
1253
 
1389
1299
                yield line, prefix + (version,)
1390
1300
 
1391
1301
    def _iter_all_components(self):
1392
 
        for path, prefix in self._iter_all_prefixes():
 
1302
        for path, prefix in self._get_all_prefixes():
1393
1303
            yield prefix, self._get_vf(path)
1394
1304
 
1395
1305
    def keys(self):
1401
1311
        return result
1402
1312
 
1403
1313
 
1404
 
class VersionedFilesWithFallbacks(VersionedFiles):
1405
 
 
1406
 
    def without_fallbacks(self):
1407
 
        """Return a clone of this object without any fallbacks configured."""
1408
 
        raise NotImplementedError(self.without_fallbacks)
1409
 
 
1410
 
    def add_fallback_versioned_files(self, a_versioned_files):
1411
 
        """Add a source of texts for texts not present in this knit.
1412
 
 
1413
 
        :param a_versioned_files: A VersionedFiles object.
1414
 
        """
1415
 
        raise NotImplementedError(self.add_fallback_versioned_files)
1416
 
 
1417
 
    def get_known_graph_ancestry(self, keys):
1418
 
        """Get a KnownGraph instance with the ancestry of keys."""
1419
 
        parent_map, missing_keys = self._index.find_ancestry(keys)
1420
 
        for fallback in self._transitive_fallbacks():
1421
 
            if not missing_keys:
1422
 
                break
1423
 
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1424
 
                                                missing_keys)
1425
 
            parent_map.update(f_parent_map)
1426
 
            missing_keys = f_missing_keys
1427
 
        kg = _mod_graph.KnownGraph(parent_map)
1428
 
        return kg
1429
 
 
1430
 
 
1431
1314
class _PlanMergeVersionedFile(VersionedFiles):
1432
1315
    """A VersionedFile for uncommitted and committed texts.
1433
1316
 
1454
1337
        # line data for locally held keys.
1455
1338
        self._lines = {}
1456
1339
        # key lookup providers
1457
 
        self._providers = [_mod_graph.DictParentsProvider(self._parents)]
 
1340
        self._providers = [DictParentsProvider(self._parents)]
1458
1341
 
1459
1342
    def plan_merge(self, ver_a, ver_b, base=None):
1460
1343
        """See VersionedFile.plan_merge"""
1461
 
        from ..merge import _PlanMerge
 
1344
        from bzrlib.merge import _PlanMerge
1462
1345
        if base is None:
1463
1346
            return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1464
1347
        old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1466
1349
        return _PlanMerge._subtract_plans(old_plan, new_plan)
1467
1350
 
1468
1351
    def plan_lca_merge(self, ver_a, ver_b, base=None):
1469
 
        from ..merge import _PlanLCAMerge
1470
 
        graph = _mod_graph.Graph(self)
 
1352
        from bzrlib.merge import _PlanLCAMerge
 
1353
        graph = Graph(self)
1471
1354
        new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1472
1355
        if base is None:
1473
1356
            return new_plan
1480
1363
        Lines are added locally, not to fallback versionedfiles.  Also, ghosts
1481
1364
        are permitted.  Only reserved ids are permitted.
1482
1365
        """
1483
 
        if not isinstance(key, tuple):
 
1366
        if type(key) is not tuple:
1484
1367
            raise TypeError(key)
1485
1368
        if not revision.is_reserved_id(key[-1]):
1486
1369
            raise ValueError('Only reserved ids may be used')
1525
1408
            result[revision.NULL_REVISION] = ()
1526
1409
        self._providers = self._providers[:1] + self.fallback_versionedfiles
1527
1410
        result.update(
1528
 
            _mod_graph.StackedParentsProvider(
1529
 
                self._providers).get_parent_map(keys))
1530
 
        for key, parents in viewitems(result):
 
1411
            StackedParentsProvider(self._providers).get_parent_map(keys))
 
1412
        for key, parents in result.iteritems():
1531
1413
            if parents == ():
1532
1414
                result[key] = (revision.NULL_REVISION,)
1533
1415
        return result
1706
1588
 
1707
1589
    def get_parent_map(self, keys):
1708
1590
        """See VersionedFiles.get_parent_map."""
1709
 
        parent_view = viewitems(self._get_parent_map(k for (k,) in keys))
1710
 
        return dict(((k,), tuple((p,) for p in v)) for k, v in parent_view)
 
1591
        return dict([((k,), tuple([(p,) for p in v]))
 
1592
            for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1711
1593
 
1712
1594
    def get_sha1s(self, keys):
1713
1595
        """See VersionedFiles.get_sha1s."""
1742
1624
                yield (l, key)
1743
1625
 
1744
1626
 
1745
 
class NoDupeAddLinesDecorator(object):
1746
 
    """Decorator for a VersionedFiles that skips doing an add_lines if the key
1747
 
    is already present.
1748
 
    """
1749
 
 
1750
 
    def __init__(self, store):
1751
 
        self._store = store
1752
 
 
1753
 
    def add_lines(self, key, parents, lines, parent_texts=None,
1754
 
            left_matching_blocks=None, nostore_sha=None, random_id=False,
1755
 
            check_content=True):
1756
 
        """See VersionedFiles.add_lines.
1757
 
        
1758
 
        This implementation may return None as the third element of the return
1759
 
        value when the original store wouldn't.
1760
 
        """
1761
 
        if nostore_sha:
1762
 
            raise NotImplementedError(
1763
 
                "NoDupeAddLinesDecorator.add_lines does not implement the "
1764
 
                "nostore_sha behaviour.")
1765
 
        if key[-1] is None:
1766
 
            sha1 = osutils.sha_strings(lines)
1767
 
            key = (b"sha1:" + sha1,)
1768
 
        else:
1769
 
            sha1 = None
1770
 
        if key in self._store.get_parent_map([key]):
1771
 
            # This key has already been inserted, so don't do it again.
1772
 
            if sha1 is None:
1773
 
                sha1 = osutils.sha_strings(lines)
1774
 
            return sha1, sum(map(len, lines)), None
1775
 
        return self._store.add_lines(key, parents, lines,
1776
 
                parent_texts=parent_texts,
1777
 
                left_matching_blocks=left_matching_blocks,
1778
 
                nostore_sha=nostore_sha, random_id=random_id,
1779
 
                check_content=check_content)
1780
 
 
1781
 
    def __getattr__(self, name):
1782
 
        return getattr(self._store, name)
1783
 
 
1784
 
 
1785
1627
def network_bytes_to_kind_and_offset(network_bytes):
1786
1628
    """Strip of a record kind from the front of network_bytes.
1787
1629
 
1788
1630
    :param network_bytes: The bytes of a record.
1789
1631
    :return: A tuple (storage_kind, offset_of_remaining_bytes)
1790
1632
    """
1791
 
    line_end = network_bytes.find(b'\n')
1792
 
    storage_kind = network_bytes[:line_end].decode('ascii')
 
1633
    line_end = network_bytes.find('\n')
 
1634
    storage_kind = network_bytes[:line_end]
1793
1635
    return storage_kind, line_end + 1
1794
1636
 
1795
1637
 
1831
1673
    meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1832
1674
    record_meta = bytes[line_end+4:line_end+4+meta_len]
1833
1675
    key, parents = bencode.bdecode_as_tuple(record_meta)
1834
 
    if parents == b'nil':
 
1676
    if parents == 'nil':
1835
1677
        parents = None
1836
1678
    fulltext = bytes[line_end+4+meta_len:]
1837
1679
    return [FulltextContentFactory(key, parents, None, fulltext)]
1843
1685
 
1844
1686
def record_to_fulltext_bytes(record):
1845
1687
    if record.parents is None:
1846
 
        parents = b'nil'
 
1688
        parents = 'nil'
1847
1689
    else:
1848
1690
        parents = record.parents
1849
1691
    record_meta = bencode.bencode((record.key, parents))
1850
1692
    record_content = record.get_bytes_as('fulltext')
1851
 
    return b"fulltext\n%s%s%s" % (
 
1693
    return "fulltext\n%s%s%s" % (
1852
1694
        _length_prefix(record_meta), record_meta, record_content)
1853
1695
 
1854
1696
 
1863
1705
    # gc-optimal ordering is approximately reverse topological,
1864
1706
    # properly grouped by file-id.
1865
1707
    per_prefix_map = {}
1866
 
    for item in viewitems(parent_map):
 
1708
    for item in parent_map.iteritems():
1867
1709
        key = item[0]
1868
 
        if isinstance(key, bytes) or len(key) == 1:
1869
 
            prefix = b''
 
1710
        if isinstance(key, str) or len(key) == 1:
 
1711
            prefix = ''
1870
1712
        else:
1871
1713
            prefix = key[0]
1872
1714
        try:
1878
1720
    for prefix in sorted(per_prefix_map):
1879
1721
        present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1880
1722
    return present_keys
1881
 
 
1882
 
 
1883
 
class _KeyRefs(object):
1884
 
 
1885
 
    def __init__(self, track_new_keys=False):
1886
 
        # dict mapping 'key' to 'set of keys referring to that key'
1887
 
        self.refs = {}
1888
 
        if track_new_keys:
1889
 
            # set remembering all new keys
1890
 
            self.new_keys = set()
1891
 
        else:
1892
 
            self.new_keys = None
1893
 
 
1894
 
    def clear(self):
1895
 
        if self.refs:
1896
 
            self.refs.clear()
1897
 
        if self.new_keys:
1898
 
            self.new_keys.clear()
1899
 
 
1900
 
    def add_references(self, key, refs):
1901
 
        # Record the new references
1902
 
        for referenced in refs:
1903
 
            try:
1904
 
                needed_by = self.refs[referenced]
1905
 
            except KeyError:
1906
 
                needed_by = self.refs[referenced] = set()
1907
 
            needed_by.add(key)
1908
 
        # Discard references satisfied by the new key
1909
 
        self.add_key(key)
1910
 
 
1911
 
    def get_new_keys(self):
1912
 
        return self.new_keys
1913
 
 
1914
 
    def get_unsatisfied_refs(self):
1915
 
        return self.refs.keys()
1916
 
 
1917
 
    def _satisfy_refs_for_key(self, key):
1918
 
        try:
1919
 
            del self.refs[key]
1920
 
        except KeyError:
1921
 
            # No keys depended on this key.  That's ok.
1922
 
            pass
1923
 
 
1924
 
    def add_key(self, key):
1925
 
        # satisfy refs for key, and remember that we've seen this key.
1926
 
        self._satisfy_refs_for_key(key)
1927
 
        if self.new_keys is not None:
1928
 
            self.new_keys.add(key)
1929
 
 
1930
 
    def satisfy_refs_for_keys(self, keys):
1931
 
        for key in keys:
1932
 
            self._satisfy_refs_for_key(key)
1933
 
 
1934
 
    def get_referrers(self):
1935
 
        return set(itertools.chain.from_iterable(viewvalues(self.refs)))
1936
 
 
1937
 
 
1938