~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/versionedfile.py

Latest bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2006, 2007, 2008 Canonical Ltd
 
1
# Copyright (C) 2005 by Canonical Ltd
2
2
#
3
3
# Authors:
4
4
#   Johan Rydberg <jrydberg@gnu.org>
7
7
# it under the terms of the GNU General Public License as published by
8
8
# the Free Software Foundation; either version 2 of the License, or
9
9
# (at your option) any later version.
10
 
#
 
10
 
11
11
# This program is distributed in the hope that it will be useful,
12
12
# but WITHOUT ANY WARRANTY; without even the implied warranty of
13
13
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
14
# GNU General Public License for more details.
15
 
#
 
15
 
16
16
# You should have received a copy of the GNU General Public License
17
17
# along with this program; if not, write to the Free Software
18
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
18
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
19
 
 
20
# Remaing to do is to figure out if get_graph should return a simple
 
21
# map, or a graph object of some kind.
 
22
 
19
23
 
20
24
"""Versioned text file storage api."""
21
25
 
22
 
from copy import copy
23
 
from cStringIO import StringIO
24
 
import os
25
 
import struct
26
 
from zlib import adler32
27
 
 
28
 
from bzrlib.lazy_import import lazy_import
29
 
lazy_import(globals(), """
30
 
import urllib
31
 
 
32
 
from bzrlib import (
33
 
    annotate,
34
 
    errors,
35
 
    graph as _mod_graph,
36
 
    groupcompress,
37
 
    index,
38
 
    knit,
39
 
    osutils,
40
 
    multiparent,
41
 
    tsort,
42
 
    revision,
43
 
    ui,
44
 
    )
45
 
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
46
 
from bzrlib.transport.memory import MemoryTransport
47
 
""")
 
26
 
 
27
from copy import deepcopy
 
28
from unittest import TestSuite
 
29
 
 
30
 
 
31
import bzrlib.errors as errors
48
32
from bzrlib.inter import InterObject
49
 
from bzrlib.registry import Registry
50
33
from bzrlib.symbol_versioning import *
51
 
from bzrlib.textmerge import TextMerge
52
 
from bzrlib import bencode
53
 
 
54
 
 
55
 
adapter_registry = Registry()
56
 
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
57
 
    'DeltaPlainToFullText')
58
 
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
59
 
    'FTPlainToFullText')
60
 
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
61
 
    'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
62
 
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
63
 
    'bzrlib.knit', 'DeltaAnnotatedToFullText')
64
 
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
65
 
    'bzrlib.knit', 'FTAnnotatedToUnannotated')
66
 
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
67
 
    'bzrlib.knit', 'FTAnnotatedToFullText')
68
 
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
69
 
#     'bzrlib.knit', 'FTAnnotatedToChunked')
70
 
 
71
 
 
72
 
class ContentFactory(object):
73
 
    """Abstract interface for insertion and retrieval from a VersionedFile.
74
 
 
75
 
    :ivar sha1: None, or the sha1 of the content fulltext.
76
 
    :ivar storage_kind: The native storage kind of this factory. One of
77
 
        'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
78
 
        'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
79
 
        'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
80
 
    :ivar key: The key of this content. Each key is a tuple with a single
81
 
        string in it.
82
 
    :ivar parents: A tuple of parent keys for self.key. If the object has
83
 
        no parent information, None (as opposed to () for an empty list of
84
 
        parents).
85
 
    """
86
 
 
87
 
    def __init__(self):
88
 
        """Create a ContentFactory."""
89
 
        self.sha1 = None
90
 
        self.storage_kind = None
91
 
        self.key = None
92
 
        self.parents = None
93
 
 
94
 
 
95
 
class ChunkedContentFactory(ContentFactory):
96
 
    """Static data content factory.
97
 
 
98
 
    This takes a 'chunked' list of strings. The only requirement on 'chunked' is
99
 
    that ''.join(lines) becomes a valid fulltext. A tuple of a single string
100
 
    satisfies this, as does a list of lines.
101
 
 
102
 
    :ivar sha1: None, or the sha1 of the content fulltext.
103
 
    :ivar storage_kind: The native storage kind of this factory. Always
104
 
        'chunked'
105
 
    :ivar key: The key of this content. Each key is a tuple with a single
106
 
        string in it.
107
 
    :ivar parents: A tuple of parent keys for self.key. If the object has
108
 
        no parent information, None (as opposed to () for an empty list of
109
 
        parents).
110
 
     """
111
 
 
112
 
    def __init__(self, key, parents, sha1, chunks):
113
 
        """Create a ContentFactory."""
114
 
        self.sha1 = sha1
115
 
        self.storage_kind = 'chunked'
116
 
        self.key = key
117
 
        self.parents = parents
118
 
        self._chunks = chunks
119
 
 
120
 
    def get_bytes_as(self, storage_kind):
121
 
        if storage_kind == 'chunked':
122
 
            return self._chunks
123
 
        elif storage_kind == 'fulltext':
124
 
            return ''.join(self._chunks)
125
 
        raise errors.UnavailableRepresentation(self.key, storage_kind,
126
 
            self.storage_kind)
127
 
 
128
 
 
129
 
class FulltextContentFactory(ContentFactory):
130
 
    """Static data content factory.
131
 
 
132
 
    This takes a fulltext when created and just returns that during
133
 
    get_bytes_as('fulltext').
134
 
 
135
 
    :ivar sha1: None, or the sha1 of the content fulltext.
136
 
    :ivar storage_kind: The native storage kind of this factory. Always
137
 
        'fulltext'.
138
 
    :ivar key: The key of this content. Each key is a tuple with a single
139
 
        string in it.
140
 
    :ivar parents: A tuple of parent keys for self.key. If the object has
141
 
        no parent information, None (as opposed to () for an empty list of
142
 
        parents).
143
 
     """
144
 
 
145
 
    def __init__(self, key, parents, sha1, text):
146
 
        """Create a ContentFactory."""
147
 
        self.sha1 = sha1
148
 
        self.storage_kind = 'fulltext'
149
 
        self.key = key
150
 
        self.parents = parents
151
 
        self._text = text
152
 
 
153
 
    def get_bytes_as(self, storage_kind):
154
 
        if storage_kind == self.storage_kind:
155
 
            return self._text
156
 
        elif storage_kind == 'chunked':
157
 
            return [self._text]
158
 
        raise errors.UnavailableRepresentation(self.key, storage_kind,
159
 
            self.storage_kind)
160
 
 
161
 
 
162
 
class AbsentContentFactory(ContentFactory):
163
 
    """A placeholder content factory for unavailable texts.
164
 
 
165
 
    :ivar sha1: None.
166
 
    :ivar storage_kind: 'absent'.
167
 
    :ivar key: The key of this content. Each key is a tuple with a single
168
 
        string in it.
169
 
    :ivar parents: None.
170
 
    """
171
 
 
172
 
    def __init__(self, key):
173
 
        """Create a ContentFactory."""
174
 
        self.sha1 = None
175
 
        self.storage_kind = 'absent'
176
 
        self.key = key
177
 
        self.parents = None
178
 
 
179
 
    def get_bytes_as(self, storage_kind):
180
 
        raise ValueError('A request was made for key: %s, but that'
181
 
                         ' content is not available, and the calling'
182
 
                         ' code does not handle if it is missing.'
183
 
                         % (self.key,))
184
 
 
185
 
 
186
 
class AdapterFactory(ContentFactory):
187
 
    """A content factory to adapt between key prefix's."""
188
 
 
189
 
    def __init__(self, key, parents, adapted):
190
 
        """Create an adapter factory instance."""
191
 
        self.key = key
192
 
        self.parents = parents
193
 
        self._adapted = adapted
194
 
 
195
 
    def __getattr__(self, attr):
196
 
        """Return a member from the adapted object."""
197
 
        if attr in ('key', 'parents'):
198
 
            return self.__dict__[attr]
199
 
        else:
200
 
            return getattr(self._adapted, attr)
201
 
 
202
 
 
203
 
def filter_absent(record_stream):
204
 
    """Adapt a record stream to remove absent records."""
205
 
    for record in record_stream:
206
 
        if record.storage_kind != 'absent':
207
 
            yield record
 
34
from bzrlib.transport.memory import MemoryTransport
 
35
from bzrlib.tsort import topo_sort
 
36
from bzrlib import ui
208
37
 
209
38
 
210
39
class VersionedFile(object):
211
40
    """Versioned text file storage.
212
 
 
 
41
    
213
42
    A versioned file manages versions of line-based text files,
214
43
    keeping track of the originating version for each line.
215
44
 
221
50
    Texts are identified by a version-id string.
222
51
    """
223
52
 
224
 
    @staticmethod
225
 
    def check_not_reserved_id(version_id):
226
 
        revision.check_not_reserved_id(version_id)
 
53
    def __init__(self, access_mode):
 
54
        self.finished = False
 
55
        self._access_mode = access_mode
227
56
 
228
57
    def copy_to(self, name, transport):
229
58
        """Copy this versioned file to name on transport."""
230
59
        raise NotImplementedError(self.copy_to)
231
 
 
232
 
    def get_record_stream(self, versions, ordering, include_delta_closure):
233
 
        """Get a stream of records for versions.
234
 
 
235
 
        :param versions: The versions to include. Each version is a tuple
236
 
            (version,).
237
 
        :param ordering: Either 'unordered' or 'topological'. A topologically
238
 
            sorted stream has compression parents strictly before their
239
 
            children.
240
 
        :param include_delta_closure: If True then the closure across any
241
 
            compression parents will be included (in the data content of the
242
 
            stream, not in the emitted records). This guarantees that
243
 
            'fulltext' can be used successfully on every record.
244
 
        :return: An iterator of ContentFactory objects, each of which is only
245
 
            valid until the iterator is advanced.
 
60
    
 
61
    @deprecated_method(zero_eight)
 
62
    def names(self):
 
63
        """Return a list of all the versions in this versioned file.
 
64
 
 
65
        Please use versionedfile.versions() now.
246
66
        """
247
 
        raise NotImplementedError(self.get_record_stream)
 
67
        return self.versions()
 
68
 
 
69
    def versions(self):
 
70
        """Return a unsorted list of versions."""
 
71
        raise NotImplementedError(self.versions)
 
72
 
 
73
    def has_ghost(self, version_id):
 
74
        """Returns whether version is present as a ghost."""
 
75
        raise NotImplementedError(self.has_ghost)
248
76
 
249
77
    def has_version(self, version_id):
250
78
        """Returns whether version is present."""
251
79
        raise NotImplementedError(self.has_version)
252
80
 
253
 
    def insert_record_stream(self, stream):
254
 
        """Insert a record stream into this versioned file.
255
 
 
256
 
        :param stream: A stream of records to insert.
257
 
        :return: None
258
 
        :seealso VersionedFile.get_record_stream:
259
 
        """
260
 
        raise NotImplementedError
261
 
 
262
 
    def add_lines(self, version_id, parents, lines, parent_texts=None,
263
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
264
 
        check_content=True):
 
81
    def add_lines(self, version_id, parents, lines):
265
82
        """Add a single text on top of the versioned file.
266
83
 
267
84
        Must raise RevisionAlreadyPresent if the new version is
269
86
 
270
87
        Must raise RevisionNotPresent if any of the given parents are
271
88
        not present in file history.
272
 
 
273
 
        :param lines: A list of lines. Each line must be a bytestring. And all
274
 
            of them except the last must be terminated with \n and contain no
275
 
            other \n's. The last line may either contain no \n's or a single
276
 
            terminated \n. If the lines list does meet this constraint the add
277
 
            routine may error or may succeed - but you will be unable to read
278
 
            the data back accurately. (Checking the lines have been split
279
 
            correctly is expensive and extremely unlikely to catch bugs so it
280
 
            is not done at runtime unless check_content is True.)
281
 
        :param parent_texts: An optional dictionary containing the opaque
282
 
            representations of some or all of the parents of version_id to
283
 
            allow delta optimisations.  VERY IMPORTANT: the texts must be those
284
 
            returned by add_lines or data corruption can be caused.
285
 
        :param left_matching_blocks: a hint about which areas are common
286
 
            between the text and its left-hand-parent.  The format is
287
 
            the SequenceMatcher.get_matching_blocks format.
288
 
        :param nostore_sha: Raise ExistingContent and do not add the lines to
289
 
            the versioned file if the digest of the lines matches this.
290
 
        :param random_id: If True a random id has been selected rather than
291
 
            an id determined by some deterministic process such as a converter
292
 
            from a foreign VCS. When True the backend may choose not to check
293
 
            for uniqueness of the resulting key within the versioned file, so
294
 
            this should only be done when the result is expected to be unique
295
 
            anyway.
296
 
        :param check_content: If True, the lines supplied are verified to be
297
 
            bytestrings that are correctly formed lines.
298
 
        :return: The text sha1, the number of bytes in the text, and an opaque
299
 
                 representation of the inserted version which can be provided
300
 
                 back to future add_lines calls in the parent_texts dictionary.
301
89
        """
302
90
        self._check_write_ok()
303
 
        return self._add_lines(version_id, parents, lines, parent_texts,
304
 
            left_matching_blocks, nostore_sha, random_id, check_content)
 
91
        return self._add_lines(version_id, parents, lines)
305
92
 
306
 
    def _add_lines(self, version_id, parents, lines, parent_texts,
307
 
        left_matching_blocks, nostore_sha, random_id, check_content):
 
93
    def _add_lines(self, version_id, parents, lines):
308
94
        """Helper to do the class specific add_lines."""
309
95
        raise NotImplementedError(self.add_lines)
310
96
 
311
 
    def add_lines_with_ghosts(self, version_id, parents, lines,
312
 
        parent_texts=None, nostore_sha=None, random_id=False,
313
 
        check_content=True, left_matching_blocks=None):
314
 
        """Add lines to the versioned file, allowing ghosts to be present.
315
 
 
316
 
        This takes the same parameters as add_lines and returns the same.
317
 
        """
 
97
    def add_lines_with_ghosts(self, version_id, parents, lines):
 
98
        """Add lines to the versioned file, allowing ghosts to be present."""
318
99
        self._check_write_ok()
319
 
        return self._add_lines_with_ghosts(version_id, parents, lines,
320
 
            parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
 
100
        return self._add_lines_with_ghosts(version_id, parents, lines)
321
101
 
322
 
    def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
323
 
        nostore_sha, random_id, check_content, left_matching_blocks):
 
102
    def _add_lines_with_ghosts(self, version_id, parents, lines):
324
103
        """Helper to do class specific add_lines_with_ghosts."""
325
104
        raise NotImplementedError(self.add_lines_with_ghosts)
326
105
 
328
107
        """Check the versioned file for integrity."""
329
108
        raise NotImplementedError(self.check)
330
109
 
331
 
    def _check_lines_not_unicode(self, lines):
332
 
        """Check that lines being added to a versioned file are not unicode."""
333
 
        for line in lines:
334
 
            if line.__class__ is not str:
335
 
                raise errors.BzrBadParameterUnicode("lines")
336
 
 
337
 
    def _check_lines_are_lines(self, lines):
338
 
        """Check that the lines really are full lines without inline EOL."""
339
 
        for line in lines:
340
 
            if '\n' in line[:-1]:
341
 
                raise errors.BzrBadParameterContainsNewline("lines")
342
 
 
343
 
    def get_format_signature(self):
344
 
        """Get a text description of the data encoding in this file.
345
 
 
346
 
        :since: 0.90
347
 
        """
348
 
        raise NotImplementedError(self.get_format_signature)
349
 
 
350
 
    def make_mpdiffs(self, version_ids):
351
 
        """Create multiparent diffs for specified versions."""
352
 
        knit_versions = set()
353
 
        knit_versions.update(version_ids)
354
 
        parent_map = self.get_parent_map(version_ids)
355
 
        for version_id in version_ids:
356
 
            try:
357
 
                knit_versions.update(parent_map[version_id])
358
 
            except KeyError:
359
 
                raise errors.RevisionNotPresent(version_id, self)
360
 
        # We need to filter out ghosts, because we can't diff against them.
361
 
        knit_versions = set(self.get_parent_map(knit_versions).keys())
362
 
        lines = dict(zip(knit_versions,
363
 
            self._get_lf_split_line_list(knit_versions)))
364
 
        diffs = []
365
 
        for version_id in version_ids:
366
 
            target = lines[version_id]
367
 
            try:
368
 
                parents = [lines[p] for p in parent_map[version_id] if p in
369
 
                    knit_versions]
370
 
            except KeyError:
371
 
                # I don't know how this could ever trigger.
372
 
                # parent_map[version_id] was already triggered in the previous
373
 
                # for loop, and lines[p] has the 'if p in knit_versions' check,
374
 
                # so we again won't have a KeyError.
375
 
                raise errors.RevisionNotPresent(version_id, self)
376
 
            if len(parents) > 0:
377
 
                left_parent_blocks = self._extract_blocks(version_id,
378
 
                                                          parents[0], target)
379
 
            else:
380
 
                left_parent_blocks = None
381
 
            diffs.append(multiparent.MultiParent.from_lines(target, parents,
382
 
                         left_parent_blocks))
383
 
        return diffs
384
 
 
385
 
    def _extract_blocks(self, version_id, source, target):
386
 
        return None
387
 
 
388
 
    def add_mpdiffs(self, records):
389
 
        """Add mpdiffs to this VersionedFile.
390
 
 
391
 
        Records should be iterables of version, parents, expected_sha1,
392
 
        mpdiff. mpdiff should be a MultiParent instance.
393
 
        """
394
 
        # Does this need to call self._check_write_ok()? (IanC 20070919)
395
 
        vf_parents = {}
396
 
        mpvf = multiparent.MultiMemoryVersionedFile()
397
 
        versions = []
398
 
        for version, parent_ids, expected_sha1, mpdiff in records:
399
 
            versions.append(version)
400
 
            mpvf.add_diff(mpdiff, version, parent_ids)
401
 
        needed_parents = set()
402
 
        for version, parent_ids, expected_sha1, mpdiff in records:
403
 
            needed_parents.update(p for p in parent_ids
404
 
                                  if not mpvf.has_version(p))
405
 
        present_parents = set(self.get_parent_map(needed_parents).keys())
406
 
        for parent_id, lines in zip(present_parents,
407
 
                                 self._get_lf_split_line_list(present_parents)):
408
 
            mpvf.add_version(lines, parent_id, [])
409
 
        for (version, parent_ids, expected_sha1, mpdiff), lines in\
410
 
            zip(records, mpvf.get_line_list(versions)):
411
 
            if len(parent_ids) == 1:
412
 
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
413
 
                    mpvf.get_diff(parent_ids[0]).num_lines()))
414
 
            else:
415
 
                left_matching_blocks = None
416
 
            try:
417
 
                _, _, version_text = self.add_lines_with_ghosts(version,
418
 
                    parent_ids, lines, vf_parents,
419
 
                    left_matching_blocks=left_matching_blocks)
420
 
            except NotImplementedError:
421
 
                # The vf can't handle ghosts, so add lines normally, which will
422
 
                # (reasonably) fail if there are ghosts in the data.
423
 
                _, _, version_text = self.add_lines(version,
424
 
                    parent_ids, lines, vf_parents,
425
 
                    left_matching_blocks=left_matching_blocks)
426
 
            vf_parents[version] = version_text
427
 
        sha1s = self.get_sha1s(versions)
428
 
        for version, parent_ids, expected_sha1, mpdiff in records:
429
 
            if expected_sha1 != sha1s[version]:
430
 
                raise errors.VersionedFileInvalidChecksum(version)
431
 
 
 
110
    def _check_write_ok(self):
 
111
        """Is the versioned file marked as 'finished' ? Raise if it is."""
 
112
        if self.finished:
 
113
            raise errors.OutSideTransaction()
 
114
        if self._access_mode != 'w':
 
115
            raise errors.ReadOnlyObjectDirtiedError(self)
 
116
 
 
117
    def clear_cache(self):
 
118
        """Remove any data cached in the versioned file object."""
 
119
 
 
120
    def clone_text(self, new_version_id, old_version_id, parents):
 
121
        """Add an identical text to old_version_id as new_version_id.
 
122
 
 
123
        Must raise RevisionNotPresent if the old version or any of the
 
124
        parents are not present in file history.
 
125
 
 
126
        Must raise RevisionAlreadyPresent if the new version is
 
127
        already present in file history."""
 
128
        self._check_write_ok()
 
129
        return self._clone_text(new_version_id, old_version_id, parents)
 
130
 
 
131
    def _clone_text(self, new_version_id, old_version_id, parents):
 
132
        """Helper function to do the _clone_text work."""
 
133
        raise NotImplementedError(self.clone_text)
 
134
 
 
135
    def create_empty(self, name, transport, mode=None):
 
136
        """Create a new versioned file of this exact type.
 
137
 
 
138
        :param name: the file name
 
139
        :param transport: the transport
 
140
        :param mode: optional file mode.
 
141
        """
 
142
        raise NotImplementedError(self.create_empty)
 
143
 
 
144
    def fix_parents(self, version, new_parents):
 
145
        """Fix the parents list for version.
 
146
        
 
147
        This is done by appending a new version to the index
 
148
        with identical data except for the parents list.
 
149
        the parents list must be a superset of the current
 
150
        list.
 
151
        """
 
152
        self._check_write_ok()
 
153
        return self._fix_parents(version, new_parents)
 
154
 
 
155
    def _fix_parents(self, version, new_parents):
 
156
        """Helper for fix_parents."""
 
157
        raise NotImplementedError(self.fix_parents)
 
158
 
 
159
    def get_suffixes(self):
 
160
        """Return the file suffixes associated with this versioned file."""
 
161
        raise NotImplementedError(self.get_suffixes)
 
162
    
432
163
    def get_text(self, version_id):
433
164
        """Return version contents as a text string.
434
165
 
438
169
        return ''.join(self.get_lines(version_id))
439
170
    get_string = get_text
440
171
 
441
 
    def get_texts(self, version_ids):
442
 
        """Return the texts of listed versions as a list of strings.
443
 
 
444
 
        Raises RevisionNotPresent if version is not present in
445
 
        file history.
446
 
        """
447
 
        return [''.join(self.get_lines(v)) for v in version_ids]
448
 
 
449
172
    def get_lines(self, version_id):
450
173
        """Return version contents as a sequence of lines.
451
174
 
454
177
        """
455
178
        raise NotImplementedError(self.get_lines)
456
179
 
457
 
    def _get_lf_split_line_list(self, version_ids):
458
 
        return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
459
 
 
460
 
    def get_ancestry(self, version_ids, topo_sorted=True):
 
180
    def get_ancestry(self, version_ids):
461
181
        """Return a list of all ancestors of given version(s). This
462
182
        will not include the null revision.
463
183
 
464
 
        This list will not be topologically sorted if topo_sorted=False is
465
 
        passed.
466
 
 
467
184
        Must raise RevisionNotPresent if any of the given versions are
468
185
        not present in file history."""
469
186
        if isinstance(version_ids, basestring):
470
187
            version_ids = [version_ids]
471
188
        raise NotImplementedError(self.get_ancestry)
472
 
 
 
189
        
473
190
    def get_ancestry_with_ghosts(self, version_ids):
474
191
        """Return a list of all ancestors of given version(s). This
475
192
        will not include the null revision.
476
193
 
477
194
        Must raise RevisionNotPresent if any of the given versions are
478
195
        not present in file history.
479
 
 
 
196
        
480
197
        Ghosts that are known about will be included in ancestry list,
481
198
        but are not explicitly marked.
482
199
        """
483
200
        raise NotImplementedError(self.get_ancestry_with_ghosts)
484
 
 
485
 
    def get_parent_map(self, version_ids):
486
 
        """Get a map of the parents of version_ids.
487
 
 
488
 
        :param version_ids: The version ids to look up parents for.
489
 
        :return: A mapping from version id to parents.
490
 
        """
491
 
        raise NotImplementedError(self.get_parent_map)
 
201
        
 
202
    def get_graph(self):
 
203
        """Return a graph for the entire versioned file.
 
204
        
 
205
        Ghosts are not listed or referenced in the graph.
 
206
        """
 
207
        result = {}
 
208
        for version in self.versions():
 
209
            result[version] = self.get_parents(version)
 
210
        return result
 
211
 
 
212
    def get_graph_with_ghosts(self):
 
213
        """Return a graph for the entire versioned file.
 
214
        
 
215
        Ghosts are referenced in parents list but are not
 
216
        explicitly listed.
 
217
        """
 
218
        raise NotImplementedError(self.get_graph_with_ghosts)
 
219
 
 
220
    @deprecated_method(zero_eight)
 
221
    def parent_names(self, version):
 
222
        """Return version names for parents of a version.
 
223
        
 
224
        See get_parents for the current api.
 
225
        """
 
226
        return self.get_parents(version)
 
227
 
 
228
    def get_parents(self, version_id):
 
229
        """Return version names for parents of a version.
 
230
 
 
231
        Must raise RevisionNotPresent if version is not present in
 
232
        file history.
 
233
        """
 
234
        raise NotImplementedError(self.get_parents)
492
235
 
493
236
    def get_parents_with_ghosts(self, version_id):
494
237
        """Return version names for parents of version_id.
499
242
        Ghosts that are known about will be included in the parent list,
500
243
        but are not explicitly marked.
501
244
        """
502
 
        try:
503
 
            return list(self.get_parent_map([version_id])[version_id])
504
 
        except KeyError:
505
 
            raise errors.RevisionNotPresent(version_id, self)
 
245
        raise NotImplementedError(self.get_parents_with_ghosts)
 
246
 
 
247
    def annotate_iter(self, version_id):
 
248
        """Yield list of (version-id, line) pairs for the specified
 
249
        version.
 
250
 
 
251
        Must raise RevisionNotPresent if any of the given versions are
 
252
        not present in file history.
 
253
        """
 
254
        raise NotImplementedError(self.annotate_iter)
506
255
 
507
256
    def annotate(self, version_id):
508
 
        """Return a list of (version-id, line) tuples for version_id.
509
 
 
510
 
        :raise RevisionNotPresent: If the given version is
511
 
        not present in file history.
 
257
        return list(self.annotate_iter(version_id))
 
258
 
 
259
    def join(self, other, pb=None, msg=None, version_ids=None,
 
260
             ignore_missing=False):
 
261
        """Integrate versions from other into this versioned file.
 
262
 
 
263
        If version_ids is None all versions from other should be
 
264
        incorporated into this versioned file.
 
265
 
 
266
        Must raise RevisionNotPresent if any of the specified versions
 
267
        are not present in the other files history unless ignore_missing
 
268
        is supplied when they are silently skipped.
512
269
        """
513
 
        raise NotImplementedError(self.annotate)
 
270
        self._check_write_ok()
 
271
        return InterVersionedFile.get(other, self).join(
 
272
            pb,
 
273
            msg,
 
274
            version_ids,
 
275
            ignore_missing)
514
276
 
515
 
    def iter_lines_added_or_present_in_versions(self, version_ids=None,
516
 
                                                pb=None):
 
277
    def iter_lines_added_or_present_in_versions(self, version_ids=None):
517
278
        """Iterate over the lines in the versioned file from version_ids.
518
279
 
519
 
        This may return lines from other versions. Each item the returned
520
 
        iterator yields is a tuple of a line and a text version that that line
521
 
        is present in (not introduced in).
522
 
 
523
 
        Ordering of results is in whatever order is most suitable for the
524
 
        underlying storage format.
525
 
 
526
 
        If a progress bar is supplied, it may be used to indicate progress.
527
 
        The caller is responsible for cleaning up progress bars (because this
528
 
        is an iterator).
 
280
        This may return lines from other versions, and does not return the
 
281
        specific version marker at this point. The api may be changed
 
282
        during development to include the version that the versioned file
 
283
        thinks is relevant, but given that such hints are just guesses,
 
284
        its better not to have it if we dont need it.
529
285
 
530
286
        NOTES: Lines are normalised: they will all have \n terminators.
531
287
               Lines are returned in arbitrary order.
532
 
 
533
 
        :return: An iterator over (line, version_id).
534
288
        """
535
289
        raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
536
290
 
 
291
    def transaction_finished(self):
 
292
        """The transaction that this file was opened in has finished.
 
293
 
 
294
        This records self.finished = True and should cause all mutating
 
295
        operations to error.
 
296
        """
 
297
        self.finished = True
 
298
 
 
299
    @deprecated_method(zero_eight)
 
300
    def walk(self, version_ids=None):
 
301
        """Walk the versioned file as a weave-like structure, for
 
302
        versions relative to version_ids.  Yields sequence of (lineno,
 
303
        insert, deletes, text) for each relevant line.
 
304
 
 
305
        Must raise RevisionNotPresent if any of the specified versions
 
306
        are not present in the file history.
 
307
 
 
308
        :param version_ids: the version_ids to walk with respect to. If not
 
309
                            supplied the entire weave-like structure is walked.
 
310
 
 
311
        walk is deprecated in favour of iter_lines_added_or_present_in_versions
 
312
        """
 
313
        raise NotImplementedError(self.walk)
 
314
 
 
315
    @deprecated_method(zero_eight)
 
316
    def iter_names(self):
 
317
        """Walk the names list."""
 
318
        return iter(self.versions())
 
319
 
537
320
    def plan_merge(self, ver_a, ver_b):
538
321
        """Return pseudo-annotation indicating how the two versions merge.
539
322
 
541
324
        base.
542
325
 
543
326
        Weave lines present in none of them are skipped entirely.
544
 
 
545
 
        Legend:
546
 
        killed-base Dead in base revision
547
 
        killed-both Killed in each revision
548
 
        killed-a    Killed in a
549
 
        killed-b    Killed in b
550
 
        unchanged   Alive in both a and b (possibly created in both)
551
 
        new-a       Created in a
552
 
        new-b       Created in b
553
 
        ghost-a     Killed in a, unborn in b
554
 
        ghost-b     Killed in b, unborn in a
555
 
        irrelevant  Not in either revision
556
 
        """
557
 
        raise NotImplementedError(VersionedFile.plan_merge)
558
 
 
559
 
    def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
560
 
                    b_marker=TextMerge.B_MARKER):
561
 
        return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
562
 
 
563
 
 
564
 
class RecordingVersionedFilesDecorator(object):
565
 
    """A minimal versioned files that records calls made on it.
566
 
 
567
 
    Only enough methods have been added to support tests using it to date.
568
 
 
569
 
    :ivar calls: A list of the calls made; can be reset at any time by
570
 
        assigning [] to it.
571
 
    """
572
 
 
573
 
    def __init__(self, backing_vf):
574
 
        """Create a RecordingVersionedFilesDecorator decorating backing_vf.
575
 
 
576
 
        :param backing_vf: The versioned file to answer all methods.
577
 
        """
578
 
        self._backing_vf = backing_vf
579
 
        self.calls = []
580
 
 
581
 
    def add_lines(self, key, parents, lines, parent_texts=None,
582
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
583
 
        check_content=True):
584
 
        self.calls.append(("add_lines", key, parents, lines, parent_texts,
585
 
            left_matching_blocks, nostore_sha, random_id, check_content))
586
 
        return self._backing_vf.add_lines(key, parents, lines, parent_texts,
587
 
            left_matching_blocks, nostore_sha, random_id, check_content)
588
 
 
589
 
    def check(self):
590
 
        self._backing_vf.check()
591
 
 
592
 
    def get_parent_map(self, keys):
593
 
        self.calls.append(("get_parent_map", copy(keys)))
594
 
        return self._backing_vf.get_parent_map(keys)
595
 
 
596
 
    def get_record_stream(self, keys, sort_order, include_delta_closure):
597
 
        self.calls.append(("get_record_stream", list(keys), sort_order,
598
 
            include_delta_closure))
599
 
        return self._backing_vf.get_record_stream(keys, sort_order,
600
 
            include_delta_closure)
601
 
 
602
 
    def get_sha1s(self, keys):
603
 
        self.calls.append(("get_sha1s", copy(keys)))
604
 
        return self._backing_vf.get_sha1s(keys)
605
 
 
606
 
    def iter_lines_added_or_present_in_keys(self, keys, pb=None):
607
 
        self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
608
 
        return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
609
 
 
610
 
    def keys(self):
611
 
        self.calls.append(("keys",))
612
 
        return self._backing_vf.keys()
613
 
 
614
 
 
615
 
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
616
 
    """A VF that records calls, and returns keys in specific order.
617
 
 
618
 
    :ivar calls: A list of the calls made; can be reset at any time by
619
 
        assigning [] to it.
620
 
    """
621
 
 
622
 
    def __init__(self, backing_vf, key_priority):
623
 
        """Create a RecordingVersionedFilesDecorator decorating backing_vf.
624
 
 
625
 
        :param backing_vf: The versioned file to answer all methods.
626
 
        :param key_priority: A dictionary defining what order keys should be
627
 
            returned from an 'unordered' get_record_stream request.
628
 
            Keys with lower priority are returned first, keys not present in
629
 
            the map get an implicit priority of 0, and are returned in
630
 
            lexicographical order.
631
 
        """
632
 
        RecordingVersionedFilesDecorator.__init__(self, backing_vf)
633
 
        self._key_priority = key_priority
634
 
 
635
 
    def get_record_stream(self, keys, sort_order, include_delta_closure):
636
 
        self.calls.append(("get_record_stream", list(keys), sort_order,
637
 
            include_delta_closure))
638
 
        if sort_order == 'unordered':
639
 
            def sort_key(key):
640
 
                return (self._key_priority.get(key, 0), key)
641
 
            # Use a defined order by asking for the keys one-by-one from the
642
 
            # backing_vf
643
 
            for key in sorted(keys, key=sort_key):
644
 
                for record in self._backing_vf.get_record_stream([key],
645
 
                                'unordered', include_delta_closure):
646
 
                    yield record
647
 
        else:
648
 
            for record in self._backing_vf.get_record_stream(keys, sort_order,
649
 
                            include_delta_closure):
650
 
                yield record
651
 
 
652
 
 
653
 
class KeyMapper(object):
654
 
    """KeyMappers map between keys and underlying partitioned storage."""
655
 
 
656
 
    def map(self, key):
657
 
        """Map key to an underlying storage identifier.
658
 
 
659
 
        :param key: A key tuple e.g. ('file-id', 'revision-id').
660
 
        :return: An underlying storage identifier, specific to the partitioning
661
 
            mechanism.
662
 
        """
663
 
        raise NotImplementedError(self.map)
664
 
 
665
 
    def unmap(self, partition_id):
666
 
        """Map a partitioned storage id back to a key prefix.
667
 
 
668
 
        :param partition_id: The underlying partition id.
669
 
        :return: As much of a key (or prefix) as is derivable from the partition
670
 
            id.
671
 
        """
672
 
        raise NotImplementedError(self.unmap)
673
 
 
674
 
 
675
 
class ConstantMapper(KeyMapper):
676
 
    """A key mapper that maps to a constant result."""
677
 
 
678
 
    def __init__(self, result):
679
 
        """Create a ConstantMapper which will return result for all maps."""
680
 
        self._result = result
681
 
 
682
 
    def map(self, key):
683
 
        """See KeyMapper.map()."""
684
 
        return self._result
685
 
 
686
 
 
687
 
class URLEscapeMapper(KeyMapper):
688
 
    """Base class for use with transport backed storage.
689
 
 
690
 
    This provides a map and unmap wrapper that respectively url escape and
691
 
    unescape their outputs and inputs.
692
 
    """
693
 
 
694
 
    def map(self, key):
695
 
        """See KeyMapper.map()."""
696
 
        return urllib.quote(self._map(key))
697
 
 
698
 
    def unmap(self, partition_id):
699
 
        """See KeyMapper.unmap()."""
700
 
        return self._unmap(urllib.unquote(partition_id))
701
 
 
702
 
 
703
 
class PrefixMapper(URLEscapeMapper):
704
 
    """A key mapper that extracts the first component of a key.
705
 
 
706
 
    This mapper is for use with a transport based backend.
707
 
    """
708
 
 
709
 
    def _map(self, key):
710
 
        """See KeyMapper.map()."""
711
 
        return key[0]
712
 
 
713
 
    def _unmap(self, partition_id):
714
 
        """See KeyMapper.unmap()."""
715
 
        return (partition_id,)
716
 
 
717
 
 
718
 
class HashPrefixMapper(URLEscapeMapper):
719
 
    """A key mapper that combines the first component of a key with a hash.
720
 
 
721
 
    This mapper is for use with a transport based backend.
722
 
    """
723
 
 
724
 
    def _map(self, key):
725
 
        """See KeyMapper.map()."""
726
 
        prefix = self._escape(key[0])
727
 
        return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
728
 
 
729
 
    def _escape(self, prefix):
730
 
        """No escaping needed here."""
731
 
        return prefix
732
 
 
733
 
    def _unmap(self, partition_id):
734
 
        """See KeyMapper.unmap()."""
735
 
        return (self._unescape(osutils.basename(partition_id)),)
736
 
 
737
 
    def _unescape(self, basename):
738
 
        """No unescaping needed for HashPrefixMapper."""
739
 
        return basename
740
 
 
741
 
 
742
 
class HashEscapedPrefixMapper(HashPrefixMapper):
743
 
    """Combines the escaped first component of a key with a hash.
744
 
 
745
 
    This mapper is for use with a transport based backend.
746
 
    """
747
 
 
748
 
    _safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
749
 
 
750
 
    def _escape(self, prefix):
751
 
        """Turn a key element into a filesystem safe string.
752
 
 
753
 
        This is similar to a plain urllib.quote, except
754
 
        it uses specific safe characters, so that it doesn't
755
 
        have to translate a lot of valid file ids.
756
 
        """
757
 
        # @ does not get escaped. This is because it is a valid
758
 
        # filesystem character we use all the time, and it looks
759
 
        # a lot better than seeing %40 all the time.
760
 
        r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
761
 
             for c in prefix]
762
 
        return ''.join(r)
763
 
 
764
 
    def _unescape(self, basename):
765
 
        """Escaped names are easily unescaped by urlutils."""
766
 
        return urllib.unquote(basename)
767
 
 
768
 
 
769
 
def make_versioned_files_factory(versioned_file_factory, mapper):
770
 
    """Create a ThunkedVersionedFiles factory.
771
 
 
772
 
    This will create a callable which when called creates a
773
 
    ThunkedVersionedFiles on a transport, using mapper to access individual
774
 
    versioned files, and versioned_file_factory to create each individual file.
775
 
    """
776
 
    def factory(transport):
777
 
        return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
778
 
            lambda:True)
779
 
    return factory
780
 
 
781
 
 
782
 
class VersionedFiles(object):
783
 
    """Storage for many versioned files.
784
 
 
785
 
    This object allows a single keyspace for accessing the history graph and
786
 
    contents of named bytestrings.
787
 
 
788
 
    Currently no implementation allows the graph of different key prefixes to
789
 
    intersect, but the API does allow such implementations in the future.
790
 
 
791
 
    The keyspace is expressed via simple tuples. Any instance of VersionedFiles
792
 
    may have a different length key-size, but that size will be constant for
793
 
    all texts added to or retrieved from it. For instance, bzrlib uses
794
 
    instances with a key-size of 2 for storing user files in a repository, with
795
 
    the first element the fileid, and the second the version of that file.
796
 
 
797
 
    The use of tuples allows a single code base to support several different
798
 
    uses with only the mapping logic changing from instance to instance.
799
 
    """
800
 
 
801
 
    def add_lines(self, key, parents, lines, parent_texts=None,
802
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
803
 
        check_content=True):
804
 
        """Add a text to the store.
805
 
 
806
 
        :param key: The key tuple of the text to add. If the last element is
807
 
            None, a CHK string will be generated during the addition.
808
 
        :param parents: The parents key tuples of the text to add.
809
 
        :param lines: A list of lines. Each line must be a bytestring. And all
810
 
            of them except the last must be terminated with \n and contain no
811
 
            other \n's. The last line may either contain no \n's or a single
812
 
            terminating \n. If the lines list does meet this constraint the add
813
 
            routine may error or may succeed - but you will be unable to read
814
 
            the data back accurately. (Checking the lines have been split
815
 
            correctly is expensive and extremely unlikely to catch bugs so it
816
 
            is not done at runtime unless check_content is True.)
817
 
        :param parent_texts: An optional dictionary containing the opaque
818
 
            representations of some or all of the parents of version_id to
819
 
            allow delta optimisations.  VERY IMPORTANT: the texts must be those
820
 
            returned by add_lines or data corruption can be caused.
821
 
        :param left_matching_blocks: a hint about which areas are common
822
 
            between the text and its left-hand-parent.  The format is
823
 
            the SequenceMatcher.get_matching_blocks format.
824
 
        :param nostore_sha: Raise ExistingContent and do not add the lines to
825
 
            the versioned file if the digest of the lines matches this.
826
 
        :param random_id: If True a random id has been selected rather than
827
 
            an id determined by some deterministic process such as a converter
828
 
            from a foreign VCS. When True the backend may choose not to check
829
 
            for uniqueness of the resulting key within the versioned file, so
830
 
            this should only be done when the result is expected to be unique
831
 
            anyway.
832
 
        :param check_content: If True, the lines supplied are verified to be
833
 
            bytestrings that are correctly formed lines.
834
 
        :return: The text sha1, the number of bytes in the text, and an opaque
835
 
                 representation of the inserted version which can be provided
836
 
                 back to future add_lines calls in the parent_texts dictionary.
837
 
        """
838
 
        raise NotImplementedError(self.add_lines)
839
 
 
840
 
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
841
 
        """Add a text to the store.
842
 
 
843
 
        This is a private function for use by CommitBuilder.
844
 
 
845
 
        :param key: The key tuple of the text to add. If the last element is
846
 
            None, a CHK string will be generated during the addition.
847
 
        :param parents: The parents key tuples of the text to add.
848
 
        :param text: A string containing the text to be committed.
849
 
        :param nostore_sha: Raise ExistingContent and do not add the lines to
850
 
            the versioned file if the digest of the lines matches this.
851
 
        :param random_id: If True a random id has been selected rather than
852
 
            an id determined by some deterministic process such as a converter
853
 
            from a foreign VCS. When True the backend may choose not to check
854
 
            for uniqueness of the resulting key within the versioned file, so
855
 
            this should only be done when the result is expected to be unique
856
 
            anyway.
857
 
        :param check_content: If True, the lines supplied are verified to be
858
 
            bytestrings that are correctly formed lines.
859
 
        :return: The text sha1, the number of bytes in the text, and an opaque
860
 
                 representation of the inserted version which can be provided
861
 
                 back to future _add_text calls in the parent_texts dictionary.
862
 
        """
863
 
        # The default implementation just thunks over to .add_lines(),
864
 
        # inefficient, but it works.
865
 
        return self.add_lines(key, parents, osutils.split_lines(text),
866
 
                              nostore_sha=nostore_sha,
867
 
                              random_id=random_id,
868
 
                              check_content=True)
869
 
 
870
 
    def add_mpdiffs(self, records):
871
 
        """Add mpdiffs to this VersionedFile.
872
 
 
873
 
        Records should be iterables of version, parents, expected_sha1,
874
 
        mpdiff. mpdiff should be a MultiParent instance.
875
 
        """
876
 
        vf_parents = {}
877
 
        mpvf = multiparent.MultiMemoryVersionedFile()
878
 
        versions = []
879
 
        for version, parent_ids, expected_sha1, mpdiff in records:
880
 
            versions.append(version)
881
 
            mpvf.add_diff(mpdiff, version, parent_ids)
882
 
        needed_parents = set()
883
 
        for version, parent_ids, expected_sha1, mpdiff in records:
884
 
            needed_parents.update(p for p in parent_ids
885
 
                                  if not mpvf.has_version(p))
886
 
        # It seems likely that adding all the present parents as fulltexts can
887
 
        # easily exhaust memory.
888
 
        chunks_to_lines = osutils.chunks_to_lines
889
 
        for record in self.get_record_stream(needed_parents, 'unordered',
890
 
            True):
891
 
            if record.storage_kind == 'absent':
892
 
                continue
893
 
            mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
894
 
                record.key, [])
895
 
        for (key, parent_keys, expected_sha1, mpdiff), lines in\
896
 
            zip(records, mpvf.get_line_list(versions)):
897
 
            if len(parent_keys) == 1:
898
 
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
899
 
                    mpvf.get_diff(parent_keys[0]).num_lines()))
900
 
            else:
901
 
                left_matching_blocks = None
902
 
            version_sha1, _, version_text = self.add_lines(key,
903
 
                parent_keys, lines, vf_parents,
904
 
                left_matching_blocks=left_matching_blocks)
905
 
            if version_sha1 != expected_sha1:
906
 
                raise errors.VersionedFileInvalidChecksum(version)
907
 
            vf_parents[key] = version_text
908
 
 
909
 
    def annotate(self, key):
910
 
        """Return a list of (version-key, line) tuples for the text of key.
911
 
 
912
 
        :raise RevisionNotPresent: If the key is not present.
913
 
        """
914
 
        raise NotImplementedError(self.annotate)
915
 
 
916
 
    def check(self, progress_bar=None):
917
 
        """Check this object for integrity.
918
 
        
919
 
        :param progress_bar: A progress bar to output as the check progresses.
920
 
        :param keys: Specific keys within the VersionedFiles to check. When
921
 
            this parameter is not None, check() becomes a generator as per
922
 
            get_record_stream. The difference to get_record_stream is that
923
 
            more or deeper checks will be performed.
924
 
        :return: None, or if keys was supplied a generator as per
925
 
            get_record_stream.
926
 
        """
927
 
        raise NotImplementedError(self.check)
928
 
 
929
 
    @staticmethod
930
 
    def check_not_reserved_id(version_id):
931
 
        revision.check_not_reserved_id(version_id)
932
 
 
933
 
    def clear_cache(self):
934
 
        """Clear whatever caches this VersionedFile holds.
935
 
 
936
 
        This is generally called after an operation has been performed, when we
937
 
        don't expect to be using this versioned file again soon.
938
 
        """
939
 
 
940
 
    def _check_lines_not_unicode(self, lines):
941
 
        """Check that lines being added to a versioned file are not unicode."""
942
 
        for line in lines:
943
 
            if line.__class__ is not str:
944
 
                raise errors.BzrBadParameterUnicode("lines")
945
 
 
946
 
    def _check_lines_are_lines(self, lines):
947
 
        """Check that the lines really are full lines without inline EOL."""
948
 
        for line in lines:
949
 
            if '\n' in line[:-1]:
950
 
                raise errors.BzrBadParameterContainsNewline("lines")
951
 
 
952
 
    def get_known_graph_ancestry(self, keys):
953
 
        """Get a KnownGraph instance with the ancestry of keys."""
954
 
        # most basic implementation is a loop around get_parent_map
955
 
        pending = set(keys)
956
 
        parent_map = {}
957
 
        while pending:
958
 
            this_parent_map = self.get_parent_map(pending)
959
 
            parent_map.update(this_parent_map)
960
 
            pending = set()
961
 
            map(pending.update, this_parent_map.itervalues())
962
 
            pending = pending.difference(parent_map)
963
 
        kg = _mod_graph.KnownGraph(parent_map)
964
 
        return kg
965
 
 
966
 
    def get_parent_map(self, keys):
967
 
        """Get a map of the parents of keys.
968
 
 
969
 
        :param keys: The keys to look up parents for.
970
 
        :return: A mapping from keys to parents. Absent keys are absent from
971
 
            the mapping.
972
 
        """
973
 
        raise NotImplementedError(self.get_parent_map)
974
 
 
975
 
    def get_record_stream(self, keys, ordering, include_delta_closure):
976
 
        """Get a stream of records for keys.
977
 
 
978
 
        :param keys: The keys to include.
979
 
        :param ordering: Either 'unordered' or 'topological'. A topologically
980
 
            sorted stream has compression parents strictly before their
981
 
            children.
982
 
        :param include_delta_closure: If True then the closure across any
983
 
            compression parents will be included (in the opaque data).
984
 
        :return: An iterator of ContentFactory objects, each of which is only
985
 
            valid until the iterator is advanced.
986
 
        """
987
 
        raise NotImplementedError(self.get_record_stream)
988
 
 
989
 
    def get_sha1s(self, keys):
990
 
        """Get the sha1's of the texts for the given keys.
991
 
 
992
 
        :param keys: The names of the keys to lookup
993
 
        :return: a dict from key to sha1 digest. Keys of texts which are not
994
 
            present in the store are not present in the returned
995
 
            dictionary.
996
 
        """
997
 
        raise NotImplementedError(self.get_sha1s)
998
 
 
999
 
    has_key = index._has_key_from_parent_map
1000
 
 
1001
 
    def get_missing_compression_parent_keys(self):
1002
 
        """Return an iterable of keys of missing compression parents.
1003
 
 
1004
 
        Check this after calling insert_record_stream to find out if there are
1005
 
        any missing compression parents.  If there are, the records that
1006
 
        depend on them are not able to be inserted safely. The precise
1007
 
        behaviour depends on the concrete VersionedFiles class in use.
1008
 
 
1009
 
        Classes that do not support this will raise NotImplementedError.
1010
 
        """
1011
 
        raise NotImplementedError(self.get_missing_compression_parent_keys)
1012
 
 
1013
 
    def insert_record_stream(self, stream):
1014
 
        """Insert a record stream into this container.
1015
 
 
1016
 
        :param stream: A stream of records to insert.
1017
 
        :return: None
1018
 
        :seealso VersionedFile.get_record_stream:
1019
 
        """
1020
 
        raise NotImplementedError
1021
 
 
1022
 
    def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1023
 
        """Iterate over the lines in the versioned files from keys.
1024
 
 
1025
 
        This may return lines from other keys. Each item the returned
1026
 
        iterator yields is a tuple of a line and a text version that that line
1027
 
        is present in (not introduced in).
1028
 
 
1029
 
        Ordering of results is in whatever order is most suitable for the
1030
 
        underlying storage format.
1031
 
 
1032
 
        If a progress bar is supplied, it may be used to indicate progress.
1033
 
        The caller is responsible for cleaning up progress bars (because this
1034
 
        is an iterator).
1035
 
 
1036
 
        NOTES:
1037
 
         * Lines are normalised by the underlying store: they will all have \n
1038
 
           terminators.
1039
 
         * Lines are returned in arbitrary order.
1040
 
 
1041
 
        :return: An iterator over (line, key).
1042
 
        """
1043
 
        raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
1044
 
 
1045
 
    def keys(self):
1046
 
        """Return a iterable of the keys for all the contained texts."""
1047
 
        raise NotImplementedError(self.keys)
1048
 
 
1049
 
    def make_mpdiffs(self, keys):
1050
 
        """Create multiparent diffs for specified keys."""
1051
 
        keys_order = tuple(keys)
1052
 
        keys = frozenset(keys)
1053
 
        knit_keys = set(keys)
1054
 
        parent_map = self.get_parent_map(keys)
1055
 
        for parent_keys in parent_map.itervalues():
1056
 
            if parent_keys:
1057
 
                knit_keys.update(parent_keys)
1058
 
        missing_keys = keys - set(parent_map)
1059
 
        if missing_keys:
1060
 
            raise errors.RevisionNotPresent(list(missing_keys)[0], self)
1061
 
        # We need to filter out ghosts, because we can't diff against them.
1062
 
        maybe_ghosts = knit_keys - keys
1063
 
        ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
1064
 
        knit_keys.difference_update(ghosts)
1065
 
        lines = {}
1066
 
        chunks_to_lines = osutils.chunks_to_lines
1067
 
        for record in self.get_record_stream(knit_keys, 'topological', True):
1068
 
            lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1069
 
            # line_block_dict = {}
1070
 
            # for parent, blocks in record.extract_line_blocks():
1071
 
            #   line_blocks[parent] = blocks
1072
 
            # line_blocks[record.key] = line_block_dict
1073
 
        diffs = []
1074
 
        for key in keys_order:
1075
 
            target = lines[key]
1076
 
            parents = parent_map[key] or []
1077
 
            # Note that filtering knit_keys can lead to a parent difference
1078
 
            # between the creation and the application of the mpdiff.
1079
 
            parent_lines = [lines[p] for p in parents if p in knit_keys]
1080
 
            if len(parent_lines) > 0:
1081
 
                left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1082
 
                    target)
1083
 
            else:
1084
 
                left_parent_blocks = None
1085
 
            diffs.append(multiparent.MultiParent.from_lines(target,
1086
 
                parent_lines, left_parent_blocks))
1087
 
        return diffs
1088
 
 
1089
 
    missing_keys = index._missing_keys_from_parent_map
1090
 
 
1091
 
    def _extract_blocks(self, version_id, source, target):
1092
 
        return None
1093
 
 
1094
 
 
1095
 
class ThunkedVersionedFiles(VersionedFiles):
1096
 
    """Storage for many versioned files thunked onto a 'VersionedFile' class.
1097
 
 
1098
 
    This object allows a single keyspace for accessing the history graph and
1099
 
    contents of named bytestrings.
1100
 
 
1101
 
    Currently no implementation allows the graph of different key prefixes to
1102
 
    intersect, but the API does allow such implementations in the future.
1103
 
    """
1104
 
 
1105
 
    def __init__(self, transport, file_factory, mapper, is_locked):
1106
 
        """Create a ThunkedVersionedFiles."""
1107
 
        self._transport = transport
1108
 
        self._file_factory = file_factory
1109
 
        self._mapper = mapper
1110
 
        self._is_locked = is_locked
1111
 
 
1112
 
    def add_lines(self, key, parents, lines, parent_texts=None,
1113
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
1114
 
        check_content=True):
1115
 
        """See VersionedFiles.add_lines()."""
1116
 
        path = self._mapper.map(key)
1117
 
        version_id = key[-1]
1118
 
        parents = [parent[-1] for parent in parents]
1119
 
        vf = self._get_vf(path)
1120
 
        try:
1121
 
            try:
1122
 
                return vf.add_lines_with_ghosts(version_id, parents, lines,
1123
 
                    parent_texts=parent_texts,
1124
 
                    left_matching_blocks=left_matching_blocks,
1125
 
                    nostore_sha=nostore_sha, random_id=random_id,
1126
 
                    check_content=check_content)
1127
 
            except NotImplementedError:
1128
 
                return vf.add_lines(version_id, parents, lines,
1129
 
                    parent_texts=parent_texts,
1130
 
                    left_matching_blocks=left_matching_blocks,
1131
 
                    nostore_sha=nostore_sha, random_id=random_id,
1132
 
                    check_content=check_content)
1133
 
        except errors.NoSuchFile:
1134
 
            # parent directory may be missing, try again.
1135
 
            self._transport.mkdir(osutils.dirname(path))
1136
 
            try:
1137
 
                return vf.add_lines_with_ghosts(version_id, parents, lines,
1138
 
                    parent_texts=parent_texts,
1139
 
                    left_matching_blocks=left_matching_blocks,
1140
 
                    nostore_sha=nostore_sha, random_id=random_id,
1141
 
                    check_content=check_content)
1142
 
            except NotImplementedError:
1143
 
                return vf.add_lines(version_id, parents, lines,
1144
 
                    parent_texts=parent_texts,
1145
 
                    left_matching_blocks=left_matching_blocks,
1146
 
                    nostore_sha=nostore_sha, random_id=random_id,
1147
 
                    check_content=check_content)
1148
 
 
1149
 
    def annotate(self, key):
1150
 
        """Return a list of (version-key, line) tuples for the text of key.
1151
 
 
1152
 
        :raise RevisionNotPresent: If the key is not present.
1153
 
        """
1154
 
        prefix = key[:-1]
1155
 
        path = self._mapper.map(prefix)
1156
 
        vf = self._get_vf(path)
1157
 
        origins = vf.annotate(key[-1])
1158
 
        result = []
1159
 
        for origin, line in origins:
1160
 
            result.append((prefix + (origin,), line))
1161
 
        return result
1162
 
 
1163
 
    def get_annotator(self):
1164
 
        return annotate.Annotator(self)
1165
 
 
1166
 
    def check(self, progress_bar=None, keys=None):
1167
 
        """See VersionedFiles.check()."""
1168
 
        # XXX: This is over-enthusiastic but as we only thunk for Weaves today
1169
 
        # this is tolerable. Ideally we'd pass keys down to check() and 
1170
 
        # have the older VersiondFile interface updated too.
1171
 
        for prefix, vf in self._iter_all_components():
1172
 
            vf.check()
1173
 
        if keys is not None:
1174
 
            return self.get_record_stream(keys, 'unordered', True)
1175
 
 
1176
 
    def get_parent_map(self, keys):
1177
 
        """Get a map of the parents of keys.
1178
 
 
1179
 
        :param keys: The keys to look up parents for.
1180
 
        :return: A mapping from keys to parents. Absent keys are absent from
1181
 
            the mapping.
1182
 
        """
1183
 
        prefixes = self._partition_keys(keys)
1184
 
        result = {}
1185
 
        for prefix, suffixes in prefixes.items():
1186
 
            path = self._mapper.map(prefix)
1187
 
            vf = self._get_vf(path)
1188
 
            parent_map = vf.get_parent_map(suffixes)
1189
 
            for key, parents in parent_map.items():
1190
 
                result[prefix + (key,)] = tuple(
1191
 
                    prefix + (parent,) for parent in parents)
1192
 
        return result
1193
 
 
1194
 
    def _get_vf(self, path):
1195
 
        if not self._is_locked():
1196
 
            raise errors.ObjectNotLocked(self)
1197
 
        return self._file_factory(path, self._transport, create=True,
1198
 
            get_scope=lambda:None)
1199
 
 
1200
 
    def _partition_keys(self, keys):
1201
 
        """Turn keys into a dict of prefix:suffix_list."""
1202
 
        result = {}
1203
 
        for key in keys:
1204
 
            prefix_keys = result.setdefault(key[:-1], [])
1205
 
            prefix_keys.append(key[-1])
1206
 
        return result
1207
 
 
1208
 
    def _get_all_prefixes(self):
1209
 
        # Identify all key prefixes.
1210
 
        # XXX: A bit hacky, needs polish.
1211
 
        if type(self._mapper) == ConstantMapper:
1212
 
            paths = [self._mapper.map(())]
1213
 
            prefixes = [()]
1214
 
        else:
1215
 
            relpaths = set()
1216
 
            for quoted_relpath in self._transport.iter_files_recursive():
1217
 
                path, ext = os.path.splitext(quoted_relpath)
1218
 
                relpaths.add(path)
1219
 
            paths = list(relpaths)
1220
 
            prefixes = [self._mapper.unmap(path) for path in paths]
1221
 
        return zip(paths, prefixes)
1222
 
 
1223
 
    def get_record_stream(self, keys, ordering, include_delta_closure):
1224
 
        """See VersionedFiles.get_record_stream()."""
1225
 
        # Ordering will be taken care of by each partitioned store; group keys
1226
 
        # by partition.
1227
 
        keys = sorted(keys)
1228
 
        for prefix, suffixes, vf in self._iter_keys_vf(keys):
1229
 
            suffixes = [(suffix,) for suffix in suffixes]
1230
 
            for record in vf.get_record_stream(suffixes, ordering,
1231
 
                include_delta_closure):
1232
 
                if record.parents is not None:
1233
 
                    record.parents = tuple(
1234
 
                        prefix + parent for parent in record.parents)
1235
 
                record.key = prefix + record.key
1236
 
                yield record
1237
 
 
1238
 
    def _iter_keys_vf(self, keys):
1239
 
        prefixes = self._partition_keys(keys)
1240
 
        sha1s = {}
1241
 
        for prefix, suffixes in prefixes.items():
1242
 
            path = self._mapper.map(prefix)
1243
 
            vf = self._get_vf(path)
1244
 
            yield prefix, suffixes, vf
1245
 
 
1246
 
    def get_sha1s(self, keys):
1247
 
        """See VersionedFiles.get_sha1s()."""
1248
 
        sha1s = {}
1249
 
        for prefix,suffixes, vf in self._iter_keys_vf(keys):
1250
 
            vf_sha1s = vf.get_sha1s(suffixes)
1251
 
            for suffix, sha1 in vf_sha1s.iteritems():
1252
 
                sha1s[prefix + (suffix,)] = sha1
1253
 
        return sha1s
1254
 
 
1255
 
    def insert_record_stream(self, stream):
1256
 
        """Insert a record stream into this container.
1257
 
 
1258
 
        :param stream: A stream of records to insert.
1259
 
        :return: None
1260
 
        :seealso VersionedFile.get_record_stream:
1261
 
        """
1262
 
        for record in stream:
1263
 
            prefix = record.key[:-1]
1264
 
            key = record.key[-1:]
1265
 
            if record.parents is not None:
1266
 
                parents = [parent[-1:] for parent in record.parents]
1267
 
            else:
1268
 
                parents = None
1269
 
            thunk_record = AdapterFactory(key, parents, record)
1270
 
            path = self._mapper.map(prefix)
1271
 
            # Note that this parses the file many times; we can do better but
1272
 
            # as this only impacts weaves in terms of performance, it is
1273
 
            # tolerable.
1274
 
            vf = self._get_vf(path)
1275
 
            vf.insert_record_stream([thunk_record])
1276
 
 
1277
 
    def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1278
 
        """Iterate over the lines in the versioned files from keys.
1279
 
 
1280
 
        This may return lines from other keys. Each item the returned
1281
 
        iterator yields is a tuple of a line and a text version that that line
1282
 
        is present in (not introduced in).
1283
 
 
1284
 
        Ordering of results is in whatever order is most suitable for the
1285
 
        underlying storage format.
1286
 
 
1287
 
        If a progress bar is supplied, it may be used to indicate progress.
1288
 
        The caller is responsible for cleaning up progress bars (because this
1289
 
        is an iterator).
1290
 
 
1291
 
        NOTES:
1292
 
         * Lines are normalised by the underlying store: they will all have \n
1293
 
           terminators.
1294
 
         * Lines are returned in arbitrary order.
1295
 
 
1296
 
        :return: An iterator over (line, key).
1297
 
        """
1298
 
        for prefix, suffixes, vf in self._iter_keys_vf(keys):
1299
 
            for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1300
 
                yield line, prefix + (version,)
1301
 
 
1302
 
    def _iter_all_components(self):
1303
 
        for path, prefix in self._get_all_prefixes():
1304
 
            yield prefix, self._get_vf(path)
1305
 
 
1306
 
    def keys(self):
1307
 
        """See VersionedFiles.keys()."""
1308
 
        result = set()
1309
 
        for prefix, vf in self._iter_all_components():
1310
 
            for suffix in vf.versions():
1311
 
                result.add(prefix + (suffix,))
1312
 
        return result
1313
 
 
1314
 
 
1315
 
class _PlanMergeVersionedFile(VersionedFiles):
1316
 
    """A VersionedFile for uncommitted and committed texts.
1317
 
 
1318
 
    It is intended to allow merges to be planned with working tree texts.
1319
 
    It implements only the small part of the VersionedFiles interface used by
1320
 
    PlanMerge.  It falls back to multiple versionedfiles for data not stored in
1321
 
    _PlanMergeVersionedFile itself.
1322
 
 
1323
 
    :ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1324
 
        queried for missing texts.
1325
 
    """
1326
 
 
1327
 
    def __init__(self, file_id):
1328
 
        """Create a _PlanMergeVersionedFile.
1329
 
 
1330
 
        :param file_id: Used with _PlanMerge code which is not yet fully
1331
 
            tuple-keyspace aware.
1332
 
        """
1333
 
        self._file_id = file_id
1334
 
        # fallback locations
1335
 
        self.fallback_versionedfiles = []
1336
 
        # Parents for locally held keys.
1337
 
        self._parents = {}
1338
 
        # line data for locally held keys.
1339
 
        self._lines = {}
1340
 
        # key lookup providers
1341
 
        self._providers = [DictParentsProvider(self._parents)]
1342
 
 
1343
 
    def plan_merge(self, ver_a, ver_b, base=None):
1344
 
        """See VersionedFile.plan_merge"""
1345
 
        from bzrlib.merge import _PlanMerge
1346
 
        if base is None:
1347
 
            return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1348
 
        old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1349
 
        new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1350
 
        return _PlanMerge._subtract_plans(old_plan, new_plan)
1351
 
 
1352
 
    def plan_lca_merge(self, ver_a, ver_b, base=None):
1353
 
        from bzrlib.merge import _PlanLCAMerge
1354
 
        graph = Graph(self)
1355
 
        new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1356
 
        if base is None:
1357
 
            return new_plan
1358
 
        old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1359
 
        return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1360
 
 
1361
 
    def add_lines(self, key, parents, lines):
1362
 
        """See VersionedFiles.add_lines
1363
 
 
1364
 
        Lines are added locally, not to fallback versionedfiles.  Also, ghosts
1365
 
        are permitted.  Only reserved ids are permitted.
1366
 
        """
1367
 
        if type(key) is not tuple:
1368
 
            raise TypeError(key)
1369
 
        if not revision.is_reserved_id(key[-1]):
1370
 
            raise ValueError('Only reserved ids may be used')
1371
 
        if parents is None:
1372
 
            raise ValueError('Parents may not be None')
1373
 
        if lines is None:
1374
 
            raise ValueError('Lines may not be None')
1375
 
        self._parents[key] = tuple(parents)
1376
 
        self._lines[key] = lines
1377
 
 
1378
 
    def get_record_stream(self, keys, ordering, include_delta_closure):
1379
 
        pending = set(keys)
1380
 
        for key in keys:
1381
 
            if key in self._lines:
1382
 
                lines = self._lines[key]
1383
 
                parents = self._parents[key]
1384
 
                pending.remove(key)
1385
 
                yield ChunkedContentFactory(key, parents, None, lines)
1386
 
        for versionedfile in self.fallback_versionedfiles:
1387
 
            for record in versionedfile.get_record_stream(
1388
 
                pending, 'unordered', True):
1389
 
                if record.storage_kind == 'absent':
1390
 
                    continue
1391
 
                else:
1392
 
                    pending.remove(record.key)
1393
 
                    yield record
1394
 
            if not pending:
1395
 
                return
1396
 
        # report absent entries
1397
 
        for key in pending:
1398
 
            yield AbsentContentFactory(key)
1399
 
 
1400
 
    def get_parent_map(self, keys):
1401
 
        """See VersionedFiles.get_parent_map"""
1402
 
        # We create a new provider because a fallback may have been added.
1403
 
        # If we make fallbacks private we can update a stack list and avoid
1404
 
        # object creation thrashing.
1405
 
        keys = set(keys)
1406
 
        result = {}
1407
 
        if revision.NULL_REVISION in keys:
1408
 
            keys.remove(revision.NULL_REVISION)
1409
 
            result[revision.NULL_REVISION] = ()
1410
 
        self._providers = self._providers[:1] + self.fallback_versionedfiles
1411
 
        result.update(
1412
 
            StackedParentsProvider(self._providers).get_parent_map(keys))
1413
 
        for key, parents in result.iteritems():
1414
 
            if parents == ():
1415
 
                result[key] = (revision.NULL_REVISION,)
1416
 
        return result
1417
 
 
1418
 
 
1419
 
class PlanWeaveMerge(TextMerge):
1420
 
    """Weave merge that takes a plan as its input.
1421
 
 
1422
 
    This exists so that VersionedFile.plan_merge is implementable.
1423
 
    Most callers will want to use WeaveMerge instead.
1424
 
    """
1425
 
 
1426
 
    def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1427
 
                 b_marker=TextMerge.B_MARKER):
1428
 
        TextMerge.__init__(self, a_marker, b_marker)
1429
 
        self.plan = list(plan)
1430
 
 
1431
 
    def _merge_struct(self):
 
327
        """
 
328
        inc_a = set(self.get_ancestry([ver_a]))
 
329
        inc_b = set(self.get_ancestry([ver_b]))
 
330
        inc_c = inc_a & inc_b
 
331
 
 
332
        for lineno, insert, deleteset, line in self.walk([ver_a, ver_b]):
 
333
            if deleteset & inc_c:
 
334
                # killed in parent; can't be in either a or b
 
335
                # not relevant to our work
 
336
                yield 'killed-base', line
 
337
            elif insert in inc_c:
 
338
                # was inserted in base
 
339
                killed_a = bool(deleteset & inc_a)
 
340
                killed_b = bool(deleteset & inc_b)
 
341
                if killed_a and killed_b:
 
342
                    yield 'killed-both', line
 
343
                elif killed_a:
 
344
                    yield 'killed-a', line
 
345
                elif killed_b:
 
346
                    yield 'killed-b', line
 
347
                else:
 
348
                    yield 'unchanged', line
 
349
            elif insert in inc_a:
 
350
                if deleteset & inc_a:
 
351
                    yield 'ghost-a', line
 
352
                else:
 
353
                    # new in A; not in B
 
354
                    yield 'new-a', line
 
355
            elif insert in inc_b:
 
356
                if deleteset & inc_b:
 
357
                    yield 'ghost-b', line
 
358
                else:
 
359
                    yield 'new-b', line
 
360
            else:
 
361
                # not in either revision
 
362
                yield 'irrelevant', line
 
363
 
 
364
        yield 'unchanged', ''           # terminator
 
365
 
 
366
    def weave_merge(self, plan, a_marker='<<<<<<< \n', b_marker='>>>>>>> \n'):
1432
367
        lines_a = []
1433
368
        lines_b = []
1434
369
        ch_a = ch_b = False
1435
 
 
1436
 
        def outstanding_struct():
1437
 
            if not lines_a and not lines_b:
1438
 
                return
1439
 
            elif ch_a and not ch_b:
1440
 
                # one-sided change:
1441
 
                yield(lines_a,)
1442
 
            elif ch_b and not ch_a:
1443
 
                yield (lines_b,)
1444
 
            elif lines_a == lines_b:
1445
 
                yield(lines_a,)
1446
 
            else:
1447
 
                yield (lines_a, lines_b)
1448
 
 
1449
 
        # We previously considered either 'unchanged' or 'killed-both' lines
1450
 
        # to be possible places to resynchronize.  However, assuming agreement
1451
 
        # on killed-both lines may be too aggressive. -- mbp 20060324
1452
 
        for state, line in self.plan:
1453
 
            if state == 'unchanged':
 
370
        # TODO: Return a structured form of the conflicts (e.g. 2-tuples for
 
371
        # conflicted regions), rather than just inserting the markers.
 
372
        # 
 
373
        # TODO: Show some version information (e.g. author, date) on 
 
374
        # conflicted regions.
 
375
        for state, line in plan:
 
376
            if state == 'unchanged' or state == 'killed-both':
1454
377
                # resync and flush queued conflicts changes if any
1455
 
                for struct in outstanding_struct():
1456
 
                    yield struct
1457
 
                lines_a = []
1458
 
                lines_b = []
 
378
                if not lines_a and not lines_b:
 
379
                    pass
 
380
                elif ch_a and not ch_b:
 
381
                    # one-sided change:                    
 
382
                    for l in lines_a: yield l
 
383
                elif ch_b and not ch_a:
 
384
                    for l in lines_b: yield l
 
385
                elif lines_a == lines_b:
 
386
                    for l in lines_a: yield l
 
387
                else:
 
388
                    yield a_marker
 
389
                    for l in lines_a: yield l
 
390
                    yield '=======\n'
 
391
                    for l in lines_b: yield l
 
392
                    yield b_marker
 
393
 
 
394
                del lines_a[:]
 
395
                del lines_b[:]
1459
396
                ch_a = ch_b = False
1460
 
 
 
397
                
1461
398
            if state == 'unchanged':
1462
399
                if line:
1463
 
                    yield ([line],)
 
400
                    yield line
1464
401
            elif state == 'killed-a':
1465
402
                ch_a = True
1466
403
                lines_b.append(line)
1473
410
            elif state == 'new-b':
1474
411
                ch_b = True
1475
412
                lines_b.append(line)
1476
 
            elif state == 'conflicted-a':
1477
 
                ch_b = ch_a = True
1478
 
                lines_a.append(line)
1479
 
            elif state == 'conflicted-b':
1480
 
                ch_b = ch_a = True
1481
 
                lines_b.append(line)
1482
 
            elif state == 'killed-both':
1483
 
                # This counts as a change, even though there is no associated
1484
 
                # line
1485
 
                ch_b = ch_a = True
1486
 
            else:
1487
 
                if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1488
 
                        'killed-base'):
1489
 
                    raise AssertionError(state)
1490
 
        for struct in outstanding_struct():
1491
 
            yield struct
1492
 
 
1493
 
    def base_from_plan(self):
1494
 
        """Construct a BASE file from the plan text."""
1495
 
        base_lines = []
1496
 
        for state, line in self.plan:
1497
 
            if state in ('killed-a', 'killed-b', 'killed-both', 'unchanged'):
1498
 
                # If unchanged, then this line is straight from base. If a or b
1499
 
                # or both killed the line, then it *used* to be in base.
1500
 
                base_lines.append(line)
1501
 
            else:
1502
 
                if state not in ('killed-base', 'irrelevant',
1503
 
                                 'ghost-a', 'ghost-b',
1504
 
                                 'new-a', 'new-b',
1505
 
                                 'conflicted-a', 'conflicted-b'):
1506
 
                    # killed-base, irrelevant means it doesn't apply
1507
 
                    # ghost-a/ghost-b are harder to say for sure, but they
1508
 
                    # aren't in the 'inc_c' which means they aren't in the
1509
 
                    # shared base of a & b. So we don't include them.  And
1510
 
                    # obviously if the line is newly inserted, it isn't in base
1511
 
 
1512
 
                    # If 'conflicted-a' or b, then it is new vs one base, but
1513
 
                    # old versus another base. However, if we make it present
1514
 
                    # in the base, it will be deleted from the target, and it
1515
 
                    # seems better to get a line doubled in the merge result,
1516
 
                    # rather than have it deleted entirely.
1517
 
                    # Example, each node is the 'text' at that point:
1518
 
                    #           MN
1519
 
                    #          /   \
1520
 
                    #        MaN   MbN
1521
 
                    #         |  X  |
1522
 
                    #        MabN MbaN
1523
 
                    #          \   /
1524
 
                    #           ???
1525
 
                    # There was a criss-cross conflict merge. Both sides
1526
 
                    # include the other, but put themselves first.
1527
 
                    # Weave marks this as a 'clean' merge, picking OTHER over
1528
 
                    # THIS. (Though the details depend on order inserted into
1529
 
                    # weave, etc.)
1530
 
                    # LCA generates a plan:
1531
 
                    # [('unchanged', M),
1532
 
                    #  ('conflicted-b', b),
1533
 
                    #  ('unchanged', a),
1534
 
                    #  ('conflicted-a', b),
1535
 
                    #  ('unchanged', N)]
1536
 
                    # If you mark 'conflicted-*' as part of BASE, then a 3-way
1537
 
                    # merge tool will cleanly generate "MaN" (as BASE vs THIS
1538
 
                    # removes one 'b', and BASE vs OTHER removes the other)
1539
 
                    # If you include neither, 3-way creates a clean "MbabN" as
1540
 
                    # THIS adds one 'b', and OTHER does too.
1541
 
                    # It seems that having the line 2 times is better than
1542
 
                    # having it omitted. (Easier to manually delete than notice
1543
 
                    # it needs to be added.)
1544
 
                    raise AssertionError('Unknown state: %s' % (state,))
1545
 
        return base_lines
1546
 
 
1547
 
 
1548
 
class WeaveMerge(PlanWeaveMerge):
1549
 
    """Weave merge that takes a VersionedFile and two versions as its input."""
1550
 
 
1551
 
    def __init__(self, versionedfile, ver_a, ver_b,
1552
 
        a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1553
 
        plan = versionedfile.plan_merge(ver_a, ver_b)
1554
 
        PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1555
 
 
1556
 
 
1557
 
class VirtualVersionedFiles(VersionedFiles):
1558
 
    """Dummy implementation for VersionedFiles that uses other functions for
1559
 
    obtaining fulltexts and parent maps.
1560
 
 
1561
 
    This is always on the bottom of the stack and uses string keys
1562
 
    (rather than tuples) internally.
1563
 
    """
1564
 
 
1565
 
    def __init__(self, get_parent_map, get_lines):
1566
 
        """Create a VirtualVersionedFiles.
1567
 
 
1568
 
        :param get_parent_map: Same signature as Repository.get_parent_map.
1569
 
        :param get_lines: Should return lines for specified key or None if
1570
 
                          not available.
1571
 
        """
1572
 
        super(VirtualVersionedFiles, self).__init__()
1573
 
        self._get_parent_map = get_parent_map
1574
 
        self._get_lines = get_lines
1575
 
 
1576
 
    def check(self, progressbar=None):
1577
 
        """See VersionedFiles.check.
1578
 
 
1579
 
        :note: Always returns True for VirtualVersionedFiles.
1580
 
        """
1581
 
        return True
1582
 
 
1583
 
    def add_mpdiffs(self, records):
1584
 
        """See VersionedFiles.mpdiffs.
1585
 
 
1586
 
        :note: Not implemented for VirtualVersionedFiles.
1587
 
        """
1588
 
        raise NotImplementedError(self.add_mpdiffs)
1589
 
 
1590
 
    def get_parent_map(self, keys):
1591
 
        """See VersionedFiles.get_parent_map."""
1592
 
        return dict([((k,), tuple([(p,) for p in v]))
1593
 
            for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1594
 
 
1595
 
    def get_sha1s(self, keys):
1596
 
        """See VersionedFiles.get_sha1s."""
1597
 
        ret = {}
1598
 
        for (k,) in keys:
1599
 
            lines = self._get_lines(k)
1600
 
            if lines is not None:
1601
 
                if not isinstance(lines, list):
1602
 
                    raise AssertionError
1603
 
                ret[(k,)] = osutils.sha_strings(lines)
1604
 
        return ret
1605
 
 
1606
 
    def get_record_stream(self, keys, ordering, include_delta_closure):
1607
 
        """See VersionedFiles.get_record_stream."""
1608
 
        for (k,) in list(keys):
1609
 
            lines = self._get_lines(k)
1610
 
            if lines is not None:
1611
 
                if not isinstance(lines, list):
1612
 
                    raise AssertionError
1613
 
                yield ChunkedContentFactory((k,), None,
1614
 
                        sha1=osutils.sha_strings(lines),
1615
 
                        chunks=lines)
1616
 
            else:
1617
 
                yield AbsentContentFactory((k,))
1618
 
 
1619
 
    def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1620
 
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
1621
 
        for i, (key,) in enumerate(keys):
1622
 
            if pb is not None:
1623
 
                pb.update("Finding changed lines", i, len(keys))
1624
 
            for l in self._get_lines(key):
1625
 
                yield (l, key)
1626
 
 
1627
 
 
1628
 
def network_bytes_to_kind_and_offset(network_bytes):
1629
 
    """Strip of a record kind from the front of network_bytes.
1630
 
 
1631
 
    :param network_bytes: The bytes of a record.
1632
 
    :return: A tuple (storage_kind, offset_of_remaining_bytes)
1633
 
    """
1634
 
    line_end = network_bytes.find('\n')
1635
 
    storage_kind = network_bytes[:line_end]
1636
 
    return storage_kind, line_end + 1
1637
 
 
1638
 
 
1639
 
class NetworkRecordStream(object):
1640
 
    """A record_stream which reconstitures a serialised stream."""
1641
 
 
1642
 
    def __init__(self, bytes_iterator):
1643
 
        """Create a NetworkRecordStream.
1644
 
 
1645
 
        :param bytes_iterator: An iterator of bytes. Each item in this
1646
 
            iterator should have been obtained from a record_streams'
1647
 
            record.get_bytes_as(record.storage_kind) call.
1648
 
        """
1649
 
        self._bytes_iterator = bytes_iterator
1650
 
        self._kind_factory = {
1651
 
            'fulltext': fulltext_network_to_record,
1652
 
            'groupcompress-block': groupcompress.network_block_to_records,
1653
 
            'knit-ft-gz': knit.knit_network_to_record,
1654
 
            'knit-delta-gz': knit.knit_network_to_record,
1655
 
            'knit-annotated-ft-gz': knit.knit_network_to_record,
1656
 
            'knit-annotated-delta-gz': knit.knit_network_to_record,
1657
 
            'knit-delta-closure': knit.knit_delta_closure_to_records,
1658
 
            }
1659
 
 
1660
 
    def read(self):
1661
 
        """Read the stream.
1662
 
 
1663
 
        :return: An iterator as per VersionedFiles.get_record_stream().
1664
 
        """
1665
 
        for bytes in self._bytes_iterator:
1666
 
            storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1667
 
            for record in self._kind_factory[storage_kind](
1668
 
                storage_kind, bytes, line_end):
1669
 
                yield record
1670
 
 
1671
 
 
1672
 
def fulltext_network_to_record(kind, bytes, line_end):
1673
 
    """Convert a network fulltext record to record."""
1674
 
    meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1675
 
    record_meta = bytes[line_end+4:line_end+4+meta_len]
1676
 
    key, parents = bencode.bdecode_as_tuple(record_meta)
1677
 
    if parents == 'nil':
1678
 
        parents = None
1679
 
    fulltext = bytes[line_end+4+meta_len:]
1680
 
    return [FulltextContentFactory(key, parents, None, fulltext)]
1681
 
 
1682
 
 
1683
 
def _length_prefix(bytes):
1684
 
    return struct.pack('!L', len(bytes))
1685
 
 
1686
 
 
1687
 
def record_to_fulltext_bytes(record):
1688
 
    if record.parents is None:
1689
 
        parents = 'nil'
1690
 
    else:
1691
 
        parents = record.parents
1692
 
    record_meta = bencode.bencode((record.key, parents))
1693
 
    record_content = record.get_bytes_as('fulltext')
1694
 
    return "fulltext\n%s%s%s" % (
1695
 
        _length_prefix(record_meta), record_meta, record_content)
1696
 
 
1697
 
 
1698
 
def sort_groupcompress(parent_map):
1699
 
    """Sort and group the keys in parent_map into groupcompress order.
1700
 
 
1701
 
    groupcompress is defined (currently) as reverse-topological order, grouped
1702
 
    by the key prefix.
1703
 
 
1704
 
    :return: A sorted-list of keys
1705
 
    """
1706
 
    # gc-optimal ordering is approximately reverse topological,
1707
 
    # properly grouped by file-id.
1708
 
    per_prefix_map = {}
1709
 
    for item in parent_map.iteritems():
1710
 
        key = item[0]
1711
 
        if isinstance(key, str) or len(key) == 1:
1712
 
            prefix = ''
 
413
            else:
 
414
                assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
 
415
                                 'killed-both'), \
 
416
                       state
 
417
 
 
418
 
 
419
class InterVersionedFile(InterObject):
 
420
    """This class represents operations taking place between two versionedfiles..
 
421
 
 
422
    Its instances have methods like join, and contain
 
423
    references to the source and target versionedfiles these operations can be 
 
424
    carried out on.
 
425
 
 
426
    Often we will provide convenience methods on 'versionedfile' which carry out
 
427
    operations with another versionedfile - they will always forward to
 
428
    InterVersionedFile.get(other).method_name(parameters).
 
429
    """
 
430
 
 
431
    _optimisers = set()
 
432
    """The available optimised InterVersionedFile types."""
 
433
 
 
434
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
 
435
        """Integrate versions from self.source into self.target.
 
436
 
 
437
        If version_ids is None all versions from source should be
 
438
        incorporated into this versioned file.
 
439
 
 
440
        Must raise RevisionNotPresent if any of the specified versions
 
441
        are not present in the other files history unless ignore_missing is 
 
442
        supplied when they are silently skipped.
 
443
        """
 
444
        # the default join: 
 
445
        # - if the target is empty, just add all the versions from 
 
446
        #   source to target, otherwise:
 
447
        # - make a temporary versioned file of type target
 
448
        # - insert the source content into it one at a time
 
449
        # - join them
 
450
        if not self.target.versions():
 
451
            target = self.target
1713
452
        else:
1714
 
            prefix = key[0]
 
453
            # Make a new target-format versioned file. 
 
454
            temp_source = self.target.create_empty("temp", MemoryTransport())
 
455
            target = temp_source
 
456
        graph = self.source.get_graph()
 
457
        order = topo_sort(graph.items())
 
458
        pb = ui.ui_factory.nested_progress_bar()
1715
459
        try:
1716
 
            per_prefix_map[prefix].append(item)
1717
 
        except KeyError:
1718
 
            per_prefix_map[prefix] = [item]
1719
 
 
1720
 
    present_keys = []
1721
 
    for prefix in sorted(per_prefix_map):
1722
 
        present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1723
 
    return present_keys
 
460
            for index, version in enumerate(order):
 
461
                pb.update('Converting versioned data', index, len(order))
 
462
                target.add_lines(version,
 
463
                                 self.source.get_parents(version),
 
464
                                 self.source.get_lines(version))
 
465
            
 
466
            # this should hit the native code path for target
 
467
            if target is not self.target:
 
468
                return self.target.join(temp_source,
 
469
                                        pb,
 
470
                                        msg,
 
471
                                        version_ids,
 
472
                                        ignore_missing)
 
473
        finally:
 
474
            pb.finished()
 
475
 
 
476
 
 
477
class InterVersionedFileTestProviderAdapter(object):
 
478
    """A tool to generate a suite testing multiple inter versioned-file classes.
 
479
 
 
480
    This is done by copying the test once for each interversionedfile provider
 
481
    and injecting the transport_server, transport_readonly_server,
 
482
    versionedfile_factory and versionedfile_factory_to classes into each copy.
 
483
    Each copy is also given a new id() to make it easy to identify.
 
484
    """
 
485
 
 
486
    def __init__(self, transport_server, transport_readonly_server, formats):
 
487
        self._transport_server = transport_server
 
488
        self._transport_readonly_server = transport_readonly_server
 
489
        self._formats = formats
 
490
    
 
491
    def adapt(self, test):
 
492
        result = TestSuite()
 
493
        for (interversionedfile_class,
 
494
             versionedfile_factory,
 
495
             versionedfile_factory_to) in self._formats:
 
496
            new_test = deepcopy(test)
 
497
            new_test.transport_server = self._transport_server
 
498
            new_test.transport_readonly_server = self._transport_readonly_server
 
499
            new_test.interversionedfile_class = interversionedfile_class
 
500
            new_test.versionedfile_factory = versionedfile_factory
 
501
            new_test.versionedfile_factory_to = versionedfile_factory_to
 
502
            def make_new_test_id():
 
503
                new_id = "%s(%s)" % (new_test.id(), interversionedfile_class.__name__)
 
504
                return lambda: new_id
 
505
            new_test.id = make_new_test_id()
 
506
            result.addTest(new_test)
 
507
        return result
 
508
 
 
509
    @staticmethod
 
510
    def default_test_list():
 
511
        """Generate the default list of interversionedfile permutations to test."""
 
512
        from bzrlib.weave import WeaveFile
 
513
        from bzrlib.knit import KnitVersionedFile
 
514
        result = []
 
515
        # test the fallback InterVersionedFile from weave to annotated knits
 
516
        result.append((InterVersionedFile, 
 
517
                       WeaveFile,
 
518
                       KnitVersionedFile))
 
519
        for optimiser in InterVersionedFile._optimisers:
 
520
            result.append((optimiser,
 
521
                           optimiser._matching_file_factory,
 
522
                           optimiser._matching_file_factory
 
523
                           ))
 
524
        # if there are specific combinations we want to use, we can add them 
 
525
        # here.
 
526
        return result