/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

[merge] robertc's integration, updated tests to check for retcode=3

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2009 Canonical Ltd
2
 
#
 
1
#! /usr/bin/python
 
2
 
 
3
# Copyright (C) 2005 Canonical Ltd
 
4
 
3
5
# This program is free software; you can redistribute it and/or modify
4
6
# it under the terms of the GNU General Public License as published by
5
7
# the Free Software Foundation; either version 2 of the License, or
6
8
# (at your option) any later version.
7
 
#
 
9
 
8
10
# This program is distributed in the hope that it will be useful,
9
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
13
# GNU General Public License for more details.
12
 
#
 
14
 
13
15
# You should have received a copy of the GNU General Public License
14
16
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
18
 
17
19
# Author: Martin Pool <mbp@canonical.com>
18
20
 
 
21
 
19
22
"""Weave - storage of related text file versions"""
20
23
 
21
 
from __future__ import absolute_import
22
24
 
23
25
# XXX: If we do weaves this way, will a merge still behave the same
24
26
# way if it's done in a different order?  That's a pretty desirable
25
27
# property.
26
28
 
27
29
# TODO: Nothing here so far assumes the lines are really \n newlines,
28
 
# rather than being split up in some other way.  We could accommodate
 
30
# rather than being split up in some other way.  We could accomodate
29
31
# binaries, perhaps by naively splitting on \n or perhaps using
30
32
# something like a rolling checksum.
31
33
 
59
61
# where the basis and destination are unchanged.
60
62
 
61
63
# FIXME: Sometimes we will be given a parents list for a revision
62
 
# that includes some redundant parents (i.e. already a parent of
63
 
# something in the list.)  We should eliminate them.  This can
 
64
# that includes some redundant parents (i.e. already a parent of 
 
65
# something in the list.)  We should eliminate them.  This can 
64
66
# be done fairly efficiently because the sequence numbers constrain
65
67
# the possible relationships.
66
68
 
67
 
# FIXME: the conflict markers should be *7* characters
68
 
 
69
 
from copy import copy
70
 
import os
71
 
import patiencediff
72
 
 
73
 
from ..lazy_import import lazy_import
74
 
lazy_import(globals(), """
75
 
from breezy import tsort
76
 
""")
77
 
from .. import (
78
 
    errors,
79
 
    osutils,
80
 
    )
81
 
from ..errors import (
82
 
    RevisionAlreadyPresent,
83
 
    RevisionNotPresent,
84
 
    UnavailableRepresentation,
85
 
    )
86
 
from ..osutils import dirname, sha, sha_strings, split_lines
87
 
from ..revision import NULL_REVISION
88
 
from ..sixish import (
89
 
    BytesIO,
90
 
    )
91
 
from ..trace import mutter
92
 
from .versionedfile import (
93
 
    AbsentContentFactory,
94
 
    adapter_registry,
95
 
    ContentFactory,
96
 
    sort_groupcompress,
97
 
    VersionedFile,
98
 
    )
99
 
from .weavefile import _read_weave_v5, write_weave_v5
100
 
 
101
 
 
102
 
class WeaveError(errors.BzrError):
103
 
 
104
 
    _fmt = "Error in processing weave: %(msg)s"
105
 
 
106
 
    def __init__(self, msg=None):
107
 
        errors.BzrError.__init__(self)
108
 
        self.msg = msg
109
 
 
110
 
 
111
 
class WeaveRevisionAlreadyPresent(WeaveError):
112
 
 
113
 
    _fmt = "Revision {%(revision_id)s} already present in %(weave)s"
114
 
 
115
 
    def __init__(self, revision_id, weave):
116
 
 
117
 
        WeaveError.__init__(self)
118
 
        self.revision_id = revision_id
119
 
        self.weave = weave
120
 
 
121
 
 
122
 
class WeaveRevisionNotPresent(WeaveError):
123
 
 
124
 
    _fmt = "Revision {%(revision_id)s} not present in %(weave)s"
125
 
 
126
 
    def __init__(self, revision_id, weave):
127
 
        WeaveError.__init__(self)
128
 
        self.revision_id = revision_id
129
 
        self.weave = weave
130
 
 
131
 
 
132
 
class WeaveFormatError(WeaveError):
133
 
 
134
 
    _fmt = "Weave invariant violated: %(what)s"
135
 
 
136
 
    def __init__(self, what):
137
 
        WeaveError.__init__(self)
138
 
        self.what = what
139
 
 
140
 
 
141
 
class WeaveParentMismatch(WeaveError):
142
 
 
143
 
    _fmt = "Parents are mismatched between two revisions. %(msg)s"
144
 
 
145
 
 
146
 
class WeaveInvalidChecksum(WeaveError):
147
 
 
148
 
    _fmt = "Text did not match its checksum: %(msg)s"
149
 
 
150
 
 
151
 
class WeaveTextDiffers(WeaveError):
152
 
 
153
 
    _fmt = ("Weaves differ on text content. Revision:"
154
 
            " {%(revision_id)s}, %(weave_a)s, %(weave_b)s")
155
 
 
156
 
    def __init__(self, revision_id, weave_a, weave_b):
157
 
        WeaveError.__init__(self)
158
 
        self.revision_id = revision_id
159
 
        self.weave_a = weave_a
160
 
        self.weave_b = weave_b
161
 
 
162
 
 
163
 
class WeaveContentFactory(ContentFactory):
164
 
    """Content factory for streaming from weaves.
165
 
 
166
 
    :seealso ContentFactory:
167
 
    """
168
 
 
169
 
    def __init__(self, version, weave):
170
 
        """Create a WeaveContentFactory for version from weave."""
171
 
        ContentFactory.__init__(self)
172
 
        self.sha1 = weave.get_sha1s([version])[version]
173
 
        self.key = (version,)
174
 
        parents = weave.get_parent_map([version])[version]
175
 
        self.parents = tuple((parent,) for parent in parents)
176
 
        self.storage_kind = 'fulltext'
177
 
        self._weave = weave
178
 
 
179
 
    def get_bytes_as(self, storage_kind):
180
 
        if storage_kind == 'fulltext':
181
 
            return self._weave.get_text(self.key[-1])
182
 
        elif storage_kind in ('chunked', 'lines'):
183
 
            return self._weave.get_lines(self.key[-1])
184
 
        else:
185
 
            raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
186
 
 
187
 
    def iter_bytes_as(self, storage_kind):
188
 
        if storage_kind in ('chunked', 'lines'):
189
 
            return iter(self._weave.get_lines(self.key[-1]))
190
 
        else:
191
 
            raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
192
 
 
193
 
 
194
 
class Weave(VersionedFile):
 
69
 
 
70
import sha
 
71
from difflib import SequenceMatcher
 
72
 
 
73
from bzrlib.trace import mutter
 
74
from bzrlib.errors import WeaveError, WeaveFormatError, WeaveParentMismatch, \
 
75
        WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent
 
76
from bzrlib.tsort import topo_sort
 
77
 
 
78
 
 
79
class Weave(object):
195
80
    """weave - versioned text file storage.
196
 
 
 
81
    
197
82
    A Weave manages versions of line-based text files, keeping track
198
83
    of the originating version for each line.
199
84
 
245
130
 
246
131
    * It doesn't seem very useful to have an active insertion
247
132
      inside an inactive insertion, but it might happen.
248
 
 
 
133
      
249
134
    * Therefore, all instructions are always"considered"; that
250
135
      is passed onto and off the stack.  An outer inactive block
251
136
      doesn't disable an inner block.
281
166
    """
282
167
 
283
168
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
284
 
                 '_weave_name', '_matcher', '_allow_reserved']
285
 
 
286
 
    def __init__(self, weave_name=None, access_mode='w', matcher=None,
287
 
                 get_scope=None, allow_reserved=False):
288
 
        """Create a weave.
289
 
 
290
 
        :param get_scope: A callable that returns an opaque object to be used
291
 
            for detecting when this weave goes out of scope (should stop
292
 
            answering requests or allowing mutation).
293
 
        """
294
 
        super(Weave, self).__init__()
 
169
                 '_weave_name']
 
170
    
 
171
    def __init__(self, weave_name=None):
295
172
        self._weave = []
296
173
        self._parents = []
297
174
        self._sha1s = []
298
175
        self._names = []
299
176
        self._name_map = {}
300
177
        self._weave_name = weave_name
301
 
        if matcher is None:
302
 
            self._matcher = patiencediff.PatienceSequenceMatcher
303
 
        else:
304
 
            self._matcher = matcher
305
 
        if get_scope is None:
306
 
            def get_scope():
307
 
                return None
308
 
        self._get_scope = get_scope
309
 
        self._scope = get_scope()
310
 
        self._access_mode = access_mode
311
 
        self._allow_reserved = allow_reserved
312
 
 
313
 
    def __repr__(self):
314
 
        return "Weave(%r)" % self._weave_name
315
 
 
316
 
    def _check_write_ok(self):
317
 
        """Is the versioned file marked as 'finished' ? Raise if it is."""
318
 
        if self._get_scope() != self._scope:
319
 
            raise errors.OutSideTransaction()
320
 
        if self._access_mode != 'w':
321
 
            raise errors.ReadOnlyObjectDirtiedError(self)
 
178
 
322
179
 
323
180
    def copy(self):
324
181
        """Return a deep copy of self.
325
 
 
 
182
        
326
183
        The copy can be modified without affecting the original weave."""
327
184
        other = Weave()
328
185
        other._weave = self._weave[:]
337
194
        if not isinstance(other, Weave):
338
195
            return False
339
196
        return self._parents == other._parents \
340
 
            and self._weave == other._weave \
341
 
            and self._sha1s == other._sha1s
 
197
               and self._weave == other._weave \
 
198
               and self._sha1s == other._sha1s 
342
199
 
 
200
    
343
201
    def __ne__(self, other):
344
202
        return not self.__eq__(other)
345
203
 
346
 
    def _idx_to_name(self, version):
347
 
        return self._names[version]
348
 
 
349
 
    def _lookup(self, name):
 
204
    def __contains__(self, name):
 
205
        return self._name_map.has_key(name)
 
206
 
 
207
    def maybe_lookup(self, name_or_index):
 
208
        """Convert possible symbolic name to index, or pass through indexes."""
 
209
        if isinstance(name_or_index, (int, long)):
 
210
            return name_or_index
 
211
        else:
 
212
            return self.lookup(name_or_index)
 
213
 
 
214
        
 
215
    def lookup(self, name):
350
216
        """Convert symbolic version name to index."""
351
 
        if not self._allow_reserved:
352
 
            self.check_not_reserved_id(name)
353
217
        try:
354
218
            return self._name_map[name]
355
219
        except KeyError:
356
 
            raise RevisionNotPresent(name, self._weave_name)
 
220
            raise WeaveRevisionNotPresent(name, self)
357
221
 
358
 
    def versions(self):
359
 
        """See VersionedFile.versions."""
 
222
    def names(self):
360
223
        return self._names[:]
361
224
 
362
 
    def has_version(self, version_id):
363
 
        """See VersionedFile.has_version."""
364
 
        return (version_id in self._name_map)
365
 
 
366
 
    __contains__ = has_version
367
 
 
368
 
    def get_record_stream(self, versions, ordering, include_delta_closure):
369
 
        """Get a stream of records for versions.
370
 
 
371
 
        :param versions: The versions to include. Each version is a tuple
372
 
            (version,).
373
 
        :param ordering: Either 'unordered' or 'topological'. A topologically
374
 
            sorted stream has compression parents strictly before their
375
 
            children.
376
 
        :param include_delta_closure: If True then the closure across any
377
 
            compression parents will be included (in the opaque data).
378
 
        :return: An iterator of ContentFactory objects, each of which is only
379
 
            valid until the iterator is advanced.
380
 
        """
381
 
        versions = [version[-1] for version in versions]
382
 
        if ordering == 'topological':
383
 
            parents = self.get_parent_map(versions)
384
 
            new_versions = tsort.topo_sort(parents)
385
 
            new_versions.extend(set(versions).difference(set(parents)))
386
 
            versions = new_versions
387
 
        elif ordering == 'groupcompress':
388
 
            parents = self.get_parent_map(versions)
389
 
            new_versions = sort_groupcompress(parents)
390
 
            new_versions.extend(set(versions).difference(set(parents)))
391
 
            versions = new_versions
392
 
        for version in versions:
393
 
            if version in self:
394
 
                yield WeaveContentFactory(version, self)
395
 
            else:
396
 
                yield AbsentContentFactory((version,))
397
 
 
398
 
    def get_parent_map(self, version_ids):
399
 
        """See VersionedFile.get_parent_map."""
400
 
        result = {}
401
 
        for version_id in version_ids:
402
 
            if version_id == NULL_REVISION:
403
 
                parents = ()
404
 
            else:
405
 
                try:
406
 
                    parents = tuple(
407
 
                        map(self._idx_to_name,
408
 
                            self._parents[self._lookup(version_id)]))
409
 
                except RevisionNotPresent:
410
 
                    continue
411
 
            result[version_id] = parents
412
 
        return result
413
 
 
414
 
    def get_parents_with_ghosts(self, version_id):
415
 
        raise NotImplementedError(self.get_parents_with_ghosts)
416
 
 
417
 
    def insert_record_stream(self, stream):
418
 
        """Insert a record stream into this versioned file.
419
 
 
420
 
        :param stream: A stream of records to insert.
421
 
        :return: None
422
 
        :seealso VersionedFile.get_record_stream:
423
 
        """
424
 
        adapters = {}
425
 
        for record in stream:
426
 
            # Raise an error when a record is missing.
427
 
            if record.storage_kind == 'absent':
428
 
                raise RevisionNotPresent([record.key[0]], self)
429
 
            # adapt to non-tuple interface
430
 
            parents = [parent[0] for parent in record.parents]
431
 
            if record.storage_kind in ('fulltext', 'chunked', 'lines'):
432
 
                self.add_lines(
433
 
                    record.key[0], parents,
434
 
                    record.get_bytes_as('lines'))
435
 
            else:
436
 
                adapter_key = record.storage_kind, 'lines'
437
 
                try:
438
 
                    adapter = adapters[adapter_key]
439
 
                except KeyError:
440
 
                    adapter_factory = adapter_registry.get(adapter_key)
441
 
                    adapter = adapter_factory(self)
442
 
                    adapters[adapter_key] = adapter
443
 
                lines = adapter.get_bytes(record, 'lines')
444
 
                try:
445
 
                    self.add_lines(record.key[0], parents, lines)
446
 
                except RevisionAlreadyPresent:
447
 
                    pass
 
225
    def iter_names(self):
 
226
        """Yield a list of all names in this weave."""
 
227
        return iter(self._names)
 
228
 
 
229
    def idx_to_name(self, version):
 
230
        return self._names[version]
448
231
 
449
232
    def _check_repeated_add(self, name, parents, text, sha1):
450
233
        """Check that a duplicated add is OK.
451
234
 
452
235
        If it is, return the (old) index; otherwise raise an exception.
453
236
        """
454
 
        idx = self._lookup(name)
 
237
        idx = self.lookup(name)
455
238
        if sorted(self._parents[idx]) != sorted(parents) \
456
 
                or sha1 != self._sha1s[idx]:
457
 
            raise RevisionAlreadyPresent(name, self._weave_name)
 
239
            or sha1 != self._sha1s[idx]:
 
240
            raise WeaveRevisionAlreadyPresent(name, self)
458
241
        return idx
459
 
 
460
 
    def _add_lines(self, version_id, parents, lines, parent_texts,
461
 
                   left_matching_blocks, nostore_sha, random_id,
462
 
                   check_content):
463
 
        """See VersionedFile.add_lines."""
464
 
        idx = self._add(version_id, lines, list(map(self._lookup, parents)),
465
 
                        nostore_sha=nostore_sha)
466
 
        return sha_strings(lines), sum(map(len, lines)), idx
467
 
 
468
 
    def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
 
242
        
 
243
    def add(self, name, parents, text, sha1=None):
469
244
        """Add a single text on top of the weave.
470
 
 
 
245
  
471
246
        Returns the index number of the newly added version.
472
247
 
473
 
        version_id
 
248
        name
474
249
            Symbolic name for this version.
475
250
            (Typically the revision-id of the revision that added it.)
476
 
            If None, a name will be allocated based on the hash. (sha1:SHAHASH)
477
251
 
478
252
        parents
479
253
            List or set of direct parent version numbers.
480
 
 
481
 
        lines
 
254
            
 
255
        text
482
256
            Sequence of lines to be added in the new version.
483
257
 
484
 
        :param nostore_sha: See VersionedFile.add_lines.
 
258
        sha -- SHA-1 of the file, if known.  This is trusted to be
 
259
            correct if supplied.
485
260
        """
486
 
        self._check_lines_not_unicode(lines)
487
 
        self._check_lines_are_lines(lines)
488
 
        if not sha1:
489
 
            sha1 = sha_strings(lines)
490
 
        if sha1 == nostore_sha:
491
 
            raise errors.ExistingContent
492
 
        if version_id is None:
493
 
            version_id = b"sha1:" + sha1
494
 
        if version_id in self._name_map:
495
 
            return self._check_repeated_add(version_id, parents, lines, sha1)
496
 
 
 
261
        from bzrlib.osutils import sha_strings
 
262
 
 
263
        assert isinstance(name, basestring)
 
264
        if sha1 is None:
 
265
            sha1 = sha_strings(text)
 
266
        if name in self._name_map:
 
267
            return self._check_repeated_add(name, parents, text, sha1)
 
268
 
 
269
        parents = map(self.maybe_lookup, parents)
497
270
        self._check_versions(parents)
 
271
        ## self._check_lines(text)
498
272
        new_version = len(self._parents)
499
273
 
500
 
        # if we abort after here the (in-memory) weave will be corrupt because
501
 
        # only some fields are updated
502
 
        # XXX: FIXME implement a succeed-or-fail of the rest of this routine.
503
 
        #      - Robert Collins 20060226
 
274
 
 
275
        # if we abort after here the (in-memory) weave will be corrupt because only
 
276
        # some fields are updated
504
277
        self._parents.append(parents[:])
505
278
        self._sha1s.append(sha1)
506
 
        self._names.append(version_id)
507
 
        self._name_map[version_id] = new_version
 
279
        self._names.append(name)
 
280
        self._name_map[name] = new_version
508
281
 
 
282
            
509
283
        if not parents:
510
284
            # special case; adding with no parents revision; can do
511
285
            # this more quickly by just appending unconditionally.
512
286
            # even more specially, if we're adding an empty text we
513
287
            # need do nothing at all.
514
 
            if lines:
515
 
                self._weave.append((b'{', new_version))
516
 
                self._weave.extend(lines)
517
 
                self._weave.append((b'}', None))
 
288
            if text:
 
289
                self._weave.append(('{', new_version))
 
290
                self._weave.extend(text)
 
291
                self._weave.append(('}', None))
 
292
        
518
293
            return new_version
519
294
 
520
295
        if len(parents) == 1:
522
297
            if sha1 == self._sha1s[pv]:
523
298
                # special case: same as the single parent
524
299
                return new_version
 
300
            
525
301
 
526
 
        ancestors = self._inclusions(parents)
 
302
        ancestors = self.inclusions(parents)
527
303
 
528
304
        l = self._weave
529
305
 
536
312
 
537
313
        # another small special case: a merge, producing the same text
538
314
        # as auto-merge
539
 
        if lines == basis_lines:
540
 
            return new_version
 
315
        if text == basis_lines:
 
316
            return new_version            
541
317
 
542
 
        # add a sentinel, because we can also match against the final line
 
318
        # add a sentinal, because we can also match against the final line
543
319
        basis_lineno.append(len(self._weave))
544
320
 
545
321
        # XXX: which line of the weave should we really consider
546
322
        # matches the end of the file?  the current code says it's the
547
323
        # last line of the weave?
548
324
 
549
 
        # print 'basis_lines:', basis_lines
550
 
        # print 'new_lines:  ', lines
 
325
        #print 'basis_lines:', basis_lines
 
326
        #print 'new_lines:  ', lines
551
327
 
552
 
        s = self._matcher(None, basis_lines, lines)
 
328
        s = SequenceMatcher(None, basis_lines, text)
553
329
 
554
330
        # offset gives the number of lines that have been inserted
555
 
        # into the weave up to the current point; if the original edit
556
 
        # instruction says to change line A then we actually change (A+offset)
 
331
        # into the weave up to the current point; if the original edit instruction
 
332
        # says to change line A then we actually change (A+offset)
557
333
        offset = 0
558
334
 
559
335
        for tag, i1, i2, j1, j2 in s.get_opcodes():
560
 
            # i1,i2 are given in offsets within basis_lines; we need to map
561
 
            # them back to offsets within the entire weave print 'raw match',
562
 
            # tag, i1, i2, j1, j2
 
336
            # i1,i2 are given in offsets within basis_lines; we need to map them
 
337
            # back to offsets within the entire weave
 
338
            #print 'raw match', tag, i1, i2, j1, j2
563
339
            if tag == 'equal':
564
340
                continue
 
341
 
565
342
            i1 = basis_lineno[i1]
566
343
            i2 = basis_lineno[i2]
 
344
 
 
345
            assert 0 <= j1 <= j2 <= len(text)
 
346
 
 
347
            #print tag, i1, i2, j1, j2
 
348
 
567
349
            # the deletion and insertion are handled separately.
568
350
            # first delete the region.
569
351
            if i1 != i2:
570
 
                self._weave.insert(i1 + offset, (b'[', new_version))
571
 
                self._weave.insert(i2 + offset + 1, (b']', new_version))
 
352
                self._weave.insert(i1+offset, ('[', new_version))
 
353
                self._weave.insert(i2+offset+1, (']', new_version))
572
354
                offset += 2
573
355
 
574
356
            if j1 != j2:
576
358
                # i2; we want to insert after this region to make sure
577
359
                # we don't destroy ourselves
578
360
                i = i2 + offset
579
 
                self._weave[i:i] = ([(b'{', new_version)] +
580
 
                                    lines[j1:j2] +
581
 
                                    [(b'}', None)])
 
361
                self._weave[i:i] = ([('{', new_version)] 
 
362
                                    + text[j1:j2] 
 
363
                                    + [('}', None)])
582
364
                offset += 2 + (j2 - j1)
 
365
 
583
366
        return new_version
584
367
 
585
 
    def _inclusions(self, versions):
 
368
    def add_identical(self, old_rev_id, new_rev_id, parents):
 
369
        """Add an identical text to old_rev_id as new_rev_id."""
 
370
        old_lines = self.get(self.lookup(old_rev_id))
 
371
        self.add(new_rev_id, parents, old_lines)
 
372
 
 
373
    def inclusions(self, versions):
586
374
        """Return set of all ancestors of given version(s)."""
587
 
        if not len(versions):
588
 
            return []
589
375
        i = set(versions)
590
 
        for v in range(max(versions), 0, -1):
 
376
        for v in xrange(max(versions), 0, -1):
591
377
            if v in i:
592
378
                # include all its parents
593
379
                i.update(self._parents[v])
594
380
        return i
595
 
 
596
 
    def get_ancestry(self, version_ids, topo_sorted=True):
597
 
        """See VersionedFile.get_ancestry."""
598
 
        if isinstance(version_ids, bytes):
599
 
            version_ids = [version_ids]
600
 
        i = self._inclusions([self._lookup(v) for v in version_ids])
601
 
        return [self._idx_to_name(v) for v in i]
 
381
        ## except IndexError:
 
382
        ##     raise ValueError("version %d not present in weave" % v)
 
383
 
 
384
 
 
385
    def parents(self, version):
 
386
        return self._parents[version]
 
387
 
 
388
 
 
389
    def parent_names(self, version):
 
390
        """Return version names for parents of a version."""
 
391
        return map(self.idx_to_name, self._parents[self.lookup(version)])
 
392
 
 
393
 
 
394
    def minimal_parents(self, version):
 
395
        """Find the minimal set of parents for the version."""
 
396
        included = self._parents[version]
 
397
        if not included:
 
398
            return []
 
399
        
 
400
        li = list(included)
 
401
        li.sort(reverse=True)
 
402
 
 
403
        mininc = []
 
404
        gotit = set()
 
405
 
 
406
        for pv in li:
 
407
            if pv not in gotit:
 
408
                mininc.append(pv)
 
409
                gotit.update(self.inclusions(pv))
 
410
 
 
411
        assert mininc[0] >= 0
 
412
        assert mininc[-1] < version
 
413
        return mininc
 
414
 
 
415
 
 
416
 
 
417
    def _check_lines(self, text):
 
418
        if not isinstance(text, list):
 
419
            raise ValueError("text should be a list, not %s" % type(text))
 
420
 
 
421
        for l in text:
 
422
            if not isinstance(l, basestring):
 
423
                raise ValueError("text line should be a string or unicode, not %s"
 
424
                                 % type(l))
 
425
        
 
426
 
602
427
 
603
428
    def _check_versions(self, indexes):
604
429
        """Check everything in the sequence of indexes is valid"""
608
433
            except IndexError:
609
434
                raise IndexError("invalid version number %r" % i)
610
435
 
611
 
    def _compatible_parents(self, my_parents, other_parents):
612
 
        """During join check that other_parents are joinable with my_parents.
613
 
 
614
 
        Joinable is defined as 'is a subset of' - supersets may require
615
 
        regeneration of diffs, but subsets do not.
616
 
        """
617
 
        return len(other_parents.difference(my_parents)) == 0
618
 
 
619
 
    def annotate(self, version_id):
620
 
        """Return a list of (version-id, line) tuples for version_id.
 
436
    
 
437
    def annotate(self, name_or_index):
 
438
        return list(self.annotate_iter(name_or_index))
 
439
 
 
440
 
 
441
    def annotate_iter(self, name_or_index):
 
442
        """Yield list of (index-id, line) pairs for the specified version.
621
443
 
622
444
        The index indicates when the line originated in the weave."""
623
 
        incls = [self._lookup(version_id)]
624
 
        return [(self._idx_to_name(origin), text) for origin, lineno, text in
625
 
                self._extract(incls)]
626
 
 
627
 
    def iter_lines_added_or_present_in_versions(self, version_ids=None,
628
 
                                                pb=None):
629
 
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
630
 
        if version_ids is None:
631
 
            version_ids = self.versions()
632
 
        version_ids = set(version_ids)
633
 
        for lineno, inserted, deletes, line in self._walk_internal(
634
 
                version_ids):
635
 
            if inserted not in version_ids:
636
 
                continue
637
 
            if not line.endswith(b'\n'):
638
 
                yield line + b'\n', inserted
639
 
            else:
640
 
                yield line, inserted
641
 
 
642
 
    def _walk_internal(self, version_ids=None):
643
 
        """Helper method for weave actions."""
644
 
 
 
445
        incls = [self.maybe_lookup(name_or_index)]
 
446
        for origin, lineno, text in self._extract(incls):
 
447
            yield origin, text
 
448
 
 
449
    def _walk(self):
 
450
        """Walk the weave.
 
451
 
 
452
        Yields sequence of
 
453
        (lineno, insert, deletes, text)
 
454
        for each literal line.
 
455
        """
 
456
        
645
457
        istack = []
646
458
        dset = set()
647
459
 
648
460
        lineno = 0         # line of weave, 0-based
649
461
 
650
462
        for l in self._weave:
651
 
            if l.__class__ == tuple:
 
463
            if isinstance(l, tuple):
652
464
                c, v = l
653
 
                if c == b'{':
654
 
                    istack.append(self._names[v])
655
 
                elif c == b'}':
 
465
                isactive = None
 
466
                if c == '{':
 
467
                    istack.append(v)
 
468
                elif c == '}':
656
469
                    istack.pop()
657
 
                elif c == b'[':
658
 
                    dset.add(self._names[v])
659
 
                elif c == b']':
660
 
                    dset.remove(self._names[v])
 
470
                elif c == '[':
 
471
                    assert v not in dset
 
472
                    dset.add(v)
 
473
                elif c == ']':
 
474
                    dset.remove(v)
661
475
                else:
662
476
                    raise WeaveFormatError('unexpected instruction %r' % v)
663
477
            else:
664
 
                yield lineno, istack[-1], frozenset(dset), l
665
 
            lineno += 1
666
 
 
 
478
                assert isinstance(l, basestring)
 
479
                assert istack
 
480
                yield lineno, istack[-1], dset, l
 
481
            lineno += 1
 
482
 
 
483
 
 
484
 
 
485
    def _extract(self, versions):
 
486
        """Yield annotation of lines in included set.
 
487
 
 
488
        Yields a sequence of tuples (origin, lineno, text), where
 
489
        origin is the origin version, lineno the index in the weave,
 
490
        and text the text of the line.
 
491
 
 
492
        The set typically but not necessarily corresponds to a version.
 
493
        """
 
494
        for i in versions:
 
495
            if not isinstance(i, int):
 
496
                raise ValueError(i)
 
497
            
 
498
        included = self.inclusions(versions)
 
499
 
 
500
        istack = []
 
501
        dset = set()
 
502
 
 
503
        lineno = 0         # line of weave, 0-based
 
504
 
 
505
        isactive = None
 
506
 
 
507
        result = []
 
508
 
 
509
        WFE = WeaveFormatError
 
510
 
 
511
        for l in self._weave:
 
512
            if isinstance(l, tuple):
 
513
                c, v = l
 
514
                isactive = None
 
515
                if c == '{':
 
516
                    assert v not in istack
 
517
                    istack.append(v)
 
518
                elif c == '}':
 
519
                    istack.pop()
 
520
                elif c == '[':
 
521
                    if v in included:
 
522
                        assert v not in dset
 
523
                        dset.add(v)
 
524
                else:
 
525
                    assert c == ']'
 
526
                    if v in included:
 
527
                        assert v in dset
 
528
                        dset.remove(v)
 
529
            else:
 
530
                assert isinstance(l, basestring)
 
531
                if isactive is None:
 
532
                    isactive = (not dset) and istack and (istack[-1] in included)
 
533
                if isactive:
 
534
                    result.append((istack[-1], lineno, l))
 
535
            lineno += 1
667
536
        if istack:
668
537
            raise WeaveFormatError("unclosed insertion blocks "
669
 
                                   "at end of weave: %s" % istack)
 
538
                    "at end of weave: %s" % istack)
670
539
        if dset:
671
 
            raise WeaveFormatError(
672
 
                "unclosed deletion blocks at end of weave: %s" % dset)
673
 
 
 
540
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
 
541
                                   % dset)
 
542
        return result
 
543
 
 
544
 
 
545
    def get_iter(self, name_or_index):
 
546
        """Yield lines for the specified version."""
 
547
        incls = [self.maybe_lookup(name_or_index)]
 
548
        for origin, lineno, line in self._extract(incls):
 
549
            yield line
 
550
 
 
551
 
 
552
    def get_text(self, name_or_index):
 
553
        return ''.join(self.get_iter(name_or_index))
 
554
        assert isinstance(version, int)
 
555
 
 
556
 
 
557
    def get_lines(self, name_or_index):
 
558
        return list(self.get_iter(name_or_index))
 
559
 
 
560
 
 
561
    get = get_lines
 
562
 
 
563
 
 
564
    def mash_iter(self, included):
 
565
        """Return composed version of multiple included versions."""
 
566
        included = map(self.maybe_lookup, included)
 
567
        for origin, lineno, text in self._extract(included):
 
568
            yield text
 
569
 
 
570
 
 
571
    def dump(self, to_file):
 
572
        from pprint import pprint
 
573
        print >>to_file, "Weave._weave = ",
 
574
        pprint(self._weave, to_file)
 
575
        print >>to_file, "Weave._parents = ",
 
576
        pprint(self._parents, to_file)
 
577
 
 
578
 
 
579
 
 
580
    def numversions(self):
 
581
        l = len(self._parents)
 
582
        assert l == len(self._sha1s)
 
583
        return l
 
584
 
 
585
 
 
586
    def __len__(self):
 
587
        return self.numversions()
 
588
 
 
589
 
 
590
    def check(self, progress_bar=None):
 
591
        # check no circular inclusions
 
592
        for version in range(self.numversions()):
 
593
            inclusions = list(self._parents[version])
 
594
            if inclusions:
 
595
                inclusions.sort()
 
596
                if inclusions[-1] >= version:
 
597
                    raise WeaveFormatError("invalid included version %d for index %d"
 
598
                                           % (inclusions[-1], version))
 
599
 
 
600
        # try extracting all versions; this is a bit slow and parallel
 
601
        # extraction could be used
 
602
        nv = self.numversions()
 
603
        for version in range(nv):
 
604
            if progress_bar:
 
605
                progress_bar.update('checking text', version, nv)
 
606
            s = sha.new()
 
607
            for l in self.get_iter(version):
 
608
                s.update(l)
 
609
            hd = s.hexdigest()
 
610
            expected = self._sha1s[version]
 
611
            if hd != expected:
 
612
                raise WeaveError("mismatched sha1 for version %d; "
 
613
                                 "got %s, expected %s"
 
614
                                 % (version, hd, expected))
 
615
 
 
616
        # TODO: check insertions are properly nested, that there are
 
617
        # no lines outside of insertion blocks, that deletions are
 
618
        # properly paired, etc.
 
619
 
 
620
 
 
621
 
 
622
    def merge(self, merge_versions):
 
623
        """Automerge and mark conflicts between versions.
 
624
 
 
625
        This returns a sequence, each entry describing alternatives
 
626
        for a chunk of the file.  Each of the alternatives is given as
 
627
        a list of lines.
 
628
 
 
629
        If there is a chunk of the file where there's no diagreement,
 
630
        only one alternative is given.
 
631
        """
 
632
        # approach: find the included versions common to all the
 
633
        # merged versions
 
634
        raise NotImplementedError()
 
635
 
 
636
 
 
637
 
 
638
    def _delta(self, included, lines):
 
639
        """Return changes from basis to new revision.
 
640
 
 
641
        The old text for comparison is the union of included revisions.
 
642
 
 
643
        This is used in inserting a new text.
 
644
 
 
645
        Delta is returned as a sequence of
 
646
        (weave1, weave2, newlines).
 
647
 
 
648
        This indicates that weave1:weave2 of the old weave should be
 
649
        replaced by the sequence of lines in newlines.  Note that
 
650
        these line numbers are positions in the total weave and don't
 
651
        correspond to the lines in any extracted version, or even the
 
652
        extracted union of included versions.
 
653
 
 
654
        If line1=line2, this is a pure insert; if newlines=[] this is a
 
655
        pure delete.  (Similar to difflib.)
 
656
        """
 
657
        raise NotImplementedError()
 
658
 
 
659
            
674
660
    def plan_merge(self, ver_a, ver_b):
675
661
        """Return pseudo-annotation indicating how the two versions merge.
676
662
 
679
665
 
680
666
        Weave lines present in none of them are skipped entirely.
681
667
        """
682
 
        inc_a = set(self.get_ancestry([ver_a]))
683
 
        inc_b = set(self.get_ancestry([ver_b]))
 
668
        inc_a = self.inclusions([ver_a])
 
669
        inc_b = self.inclusions([ver_b])
684
670
        inc_c = inc_a & inc_b
685
671
 
686
 
        for lineno, insert, deleteset, line in self._walk_internal(
687
 
                [ver_a, ver_b]):
 
672
        for lineno, insert, deleteset, line in self._walk():
688
673
            if deleteset & inc_c:
689
674
                # killed in parent; can't be in either a or b
690
675
                # not relevant to our work
716
701
                # not in either revision
717
702
                yield 'irrelevant', line
718
703
 
719
 
    def _extract(self, versions):
720
 
        """Yield annotation of lines in included set.
721
 
 
722
 
        Yields a sequence of tuples (origin, lineno, text), where
723
 
        origin is the origin version, lineno the index in the weave,
724
 
        and text the text of the line.
725
 
 
726
 
        The set typically but not necessarily corresponds to a version.
727
 
        """
728
 
        for i in versions:
729
 
            if not isinstance(i, int):
730
 
                raise ValueError(i)
731
 
 
732
 
        included = self._inclusions(versions)
733
 
 
734
 
        istack = []
735
 
        iset = set()
736
 
        dset = set()
737
 
 
738
 
        lineno = 0         # line of weave, 0-based
739
 
 
740
 
        isactive = None
741
 
 
742
 
        result = []
743
 
 
744
 
        # wow.
745
 
        #  449       0   4474.6820   2356.5590   breezy.weave:556(_extract)
746
 
        #  +285282   0   1676.8040   1676.8040   +<isinstance>
747
 
        # 1.6 seconds in 'isinstance'.
748
 
        # changing the first isinstance:
749
 
        #  449       0   2814.2660   1577.1760   breezy.weave:556(_extract)
750
 
        #  +140414   0    762.8050    762.8050   +<isinstance>
751
 
        # note that the inline time actually dropped (less function calls)
752
 
        # and total processing time was halved.
753
 
        # we're still spending ~1/4 of the method in isinstance though.
754
 
        # so lets hard code the acceptable string classes we expect:
755
 
        #  449       0   1202.9420    786.2930   breezy.weave:556(_extract)
756
 
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list'
757
 
        #                                          objects>
758
 
        # yay, down to ~1/4 the initial extract time, and our inline time
759
 
        # has shrunk again, with isinstance no longer dominating.
760
 
        # tweaking the stack inclusion test to use a set gives:
761
 
        #  449       0   1122.8030    713.0080   breezy.weave:556(_extract)
762
 
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list'
763
 
        #                                          objects>
764
 
        # - a 5% win, or possibly just noise. However with large istacks that
765
 
        # 'in' test could dominate, so I'm leaving this change in place - when
766
 
        # its fast enough to consider profiling big datasets we can review.
767
 
 
768
 
        for l in self._weave:
769
 
            if l.__class__ == tuple:
770
 
                c, v = l
771
 
                isactive = None
772
 
                if c == b'{':
773
 
                    istack.append(v)
774
 
                    iset.add(v)
775
 
                elif c == b'}':
776
 
                    iset.remove(istack.pop())
777
 
                elif c == b'[':
778
 
                    if v in included:
779
 
                        dset.add(v)
780
 
                elif c == b']':
781
 
                    if v in included:
782
 
                        dset.remove(v)
 
704
        yield 'unchanged', ''           # terminator
 
705
 
 
706
 
 
707
 
 
708
    def weave_merge(self, plan):
 
709
        lines_a = []
 
710
        lines_b = []
 
711
        ch_a = ch_b = False
 
712
 
 
713
        for state, line in plan:
 
714
            if state == 'unchanged' or state == 'killed-both':
 
715
                # resync and flush queued conflicts changes if any
 
716
                if not lines_a and not lines_b:
 
717
                    pass
 
718
                elif ch_a and not ch_b:
 
719
                    # one-sided change:                    
 
720
                    for l in lines_a: yield l
 
721
                elif ch_b and not ch_a:
 
722
                    for l in lines_b: yield l
 
723
                elif lines_a == lines_b:
 
724
                    for l in lines_a: yield l
783
725
                else:
784
 
                    raise AssertionError()
 
726
                    yield '<<<<<<<\n'
 
727
                    for l in lines_a: yield l
 
728
                    yield '=======\n'
 
729
                    for l in lines_b: yield l
 
730
                    yield '>>>>>>>\n'
 
731
 
 
732
                del lines_a[:]
 
733
                del lines_b[:]
 
734
                ch_a = ch_b = False
 
735
                
 
736
            if state == 'unchanged':
 
737
                if line:
 
738
                    yield line
 
739
            elif state == 'killed-a':
 
740
                ch_a = True
 
741
                lines_b.append(line)
 
742
            elif state == 'killed-b':
 
743
                ch_b = True
 
744
                lines_a.append(line)
 
745
            elif state == 'new-a':
 
746
                ch_a = True
 
747
                lines_a.append(line)
 
748
            elif state == 'new-b':
 
749
                ch_b = True
 
750
                lines_b.append(line)
785
751
            else:
786
 
                if isactive is None:
787
 
                    isactive = (not dset) and istack and (
788
 
                        istack[-1] in included)
789
 
                if isactive:
790
 
                    result.append((istack[-1], lineno, l))
791
 
            lineno += 1
792
 
        if istack:
793
 
            raise WeaveFormatError("unclosed insertion blocks "
794
 
                                   "at end of weave: %s" % istack)
795
 
        if dset:
796
 
            raise WeaveFormatError(
797
 
                "unclosed deletion blocks at end of weave: %s" % dset)
798
 
        return result
799
 
 
800
 
    def _maybe_lookup(self, name_or_index):
801
 
        """Convert possible symbolic name to index, or pass through indexes.
802
 
 
803
 
        NOT FOR PUBLIC USE.
 
752
                assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
 
753
                                 'killed-both'), \
 
754
                       state
 
755
 
 
756
                
 
757
    def join(self, other):
 
758
        """Integrate versions from other into this weave.
 
759
 
 
760
        The resulting weave contains all the history of both weaves; 
 
761
        any version you could retrieve from either self or other can be 
 
762
        retrieved from self after this call.
 
763
 
 
764
        It is illegal for the two weaves to contain different values 
 
765
        or different parents for any version.  See also reweave().
804
766
        """
805
 
        # GZ 2017-04-01: This used to check for long as well, but I don't think
806
 
        # there are python implementations with sys.maxsize > sys.maxint
807
 
        if isinstance(name_or_index, int):
808
 
            return name_or_index
809
 
        else:
810
 
            return self._lookup(name_or_index)
811
 
 
812
 
    def get_lines(self, version_id):
813
 
        """See VersionedFile.get_lines()."""
814
 
        int_index = self._maybe_lookup(version_id)
815
 
        result = [line for (origin, lineno, line)
816
 
                  in self._extract([int_index])]
817
 
        expected_sha1 = self._sha1s[int_index]
818
 
        measured_sha1 = sha_strings(result)
819
 
        if measured_sha1 != expected_sha1:
820
 
            raise WeaveInvalidChecksum(
821
 
                'file %s, revision %s, expected: %s, measured %s'
822
 
                % (self._weave_name, version_id,
823
 
                   expected_sha1, measured_sha1))
824
 
        return result
825
 
 
826
 
    def get_sha1s(self, version_ids):
827
 
        """See VersionedFile.get_sha1s()."""
828
 
        result = {}
829
 
        for v in version_ids:
830
 
            result[v] = self._sha1s[self._lookup(v)]
831
 
        return result
832
 
 
833
 
    def num_versions(self):
834
 
        """How many versions are in this weave?"""
835
 
        return len(self._parents)
836
 
 
837
 
    __len__ = num_versions
838
 
 
839
 
    def check(self, progress_bar=None):
840
 
        # TODO evaluate performance hit of using string sets in this routine.
841
 
        # TODO: check no circular inclusions
842
 
        # TODO: create a nested progress bar
843
 
        for version in range(self.num_versions()):
844
 
            inclusions = list(self._parents[version])
845
 
            if inclusions:
846
 
                inclusions.sort()
847
 
                if inclusions[-1] >= version:
848
 
                    raise WeaveFormatError(
849
 
                        "invalid included version %d for index %d"
850
 
                        % (inclusions[-1], version))
851
 
 
852
 
        # try extracting all versions; parallel extraction is used
853
 
        nv = self.num_versions()
854
 
        sha1s = {}
855
 
        texts = {}
856
 
        inclusions = {}
857
 
        for i in range(nv):
858
 
            # For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
859
 
            # The problem is that set membership is much more expensive
860
 
            name = self._idx_to_name(i)
861
 
            sha1s[name] = sha()
862
 
            texts[name] = []
863
 
            new_inc = {name}
864
 
            for p in self._parents[i]:
865
 
                new_inc.update(inclusions[self._idx_to_name(p)])
866
 
 
867
 
            if set(new_inc) != set(self.get_ancestry(name)):
868
 
                raise AssertionError(
869
 
                    'failed %s != %s'
870
 
                    % (set(new_inc), set(self.get_ancestry(name))))
871
 
            inclusions[name] = new_inc
872
 
 
873
 
        nlines = len(self._weave)
874
 
 
875
 
        update_text = 'checking weave'
876
 
        if self._weave_name:
877
 
            short_name = os.path.basename(self._weave_name)
878
 
            update_text = 'checking %s' % (short_name,)
879
 
            update_text = update_text[:25]
880
 
 
881
 
        for lineno, insert, deleteset, line in self._walk_internal():
882
 
            if progress_bar:
883
 
                progress_bar.update(update_text, lineno, nlines)
884
 
 
885
 
            for name, name_inclusions in inclusions.items():
886
 
                # The active inclusion must be an ancestor,
887
 
                # and no ancestors must have deleted this line,
888
 
                # because we don't support resurrection.
889
 
                if ((insert in name_inclusions) and
890
 
                        not (deleteset & name_inclusions)):
891
 
                    sha1s[name].update(line)
892
 
 
893
 
        for i in range(nv):
894
 
            version = self._idx_to_name(i)
895
 
            hd = sha1s[version].hexdigest().encode()
896
 
            expected = self._sha1s[i]
897
 
            if hd != expected:
898
 
                raise WeaveInvalidChecksum(
899
 
                    "mismatched sha1 for version %s: "
900
 
                    "got %s, expected %s"
901
 
                    % (version, hd, expected))
902
 
 
903
 
        # TODO: check insertions are properly nested, that there are
904
 
        # no lines outside of insertion blocks, that deletions are
905
 
        # properly paired, etc.
 
767
        if other.numversions() == 0:
 
768
            return          # nothing to update, easy
 
769
        # two loops so that we do not change ourselves before verifying it
 
770
        # will be ok
 
771
        # work through in index order to make sure we get all dependencies
 
772
        for other_idx, name in enumerate(other._names):
 
773
            if self._check_version_consistent(other, other_idx, name):
 
774
                continue
 
775
        for other_idx, name in enumerate(other._names):
 
776
            # TODO: If all the parents of the other version are already 
 
777
            # present then we can avoid some work by just taking the delta
 
778
            # and adjusting the offsets.
 
779
            new_parents = self._imported_parents(other, other_idx)
 
780
            lines = other.get_lines(other_idx)
 
781
            sha1 = other._sha1s[other_idx]
 
782
            self.add(name, new_parents, lines, sha1)
 
783
 
906
784
 
907
785
    def _imported_parents(self, other, other_idx):
908
786
        """Return list of parents in self corresponding to indexes in other."""
909
787
        new_parents = []
910
788
        for parent_idx in other._parents[other_idx]:
911
789
            parent_name = other._names[parent_idx]
912
 
            if parent_name not in self._name_map:
 
790
            if parent_name not in self._names:
913
791
                # should not be possible
914
 
                raise WeaveError("missing parent {%s} of {%s} in %r"
 
792
                raise WeaveError("missing parent {%s} of {%s} in %r" 
915
793
                                 % (parent_name, other._name_map[other_idx], self))
916
794
            new_parents.append(self._name_map[parent_name])
917
795
        return new_parents
924
802
         * the same text
925
803
         * the same direct parents (by name, not index, and disregarding
926
804
           order)
927
 
 
 
805
        
928
806
        If present & correct return True;
929
 
        if not present in self return False;
 
807
        if not present in self return False; 
930
808
        if inconsistent raise error."""
931
809
        this_idx = self._name_map.get(name, -1)
932
810
        if this_idx != -1:
933
811
            if self._sha1s[this_idx] != other._sha1s[other_idx]:
934
 
                raise WeaveTextDiffers(name, self, other)
 
812
                raise WeaveError("inconsistent texts for version {%s} "
 
813
                                 "when joining weaves"
 
814
                                 % (name))
935
815
            self_parents = self._parents[this_idx]
936
816
            other_parents = other._parents[other_idx]
937
 
            n1 = {self._names[i] for i in self_parents}
938
 
            n2 = {other._names[i] for i in other_parents}
939
 
            if not self._compatible_parents(n1, n2):
940
 
                raise WeaveParentMismatch(
941
 
                    "inconsistent parents "
 
817
            n1 = [self._names[i] for i in self_parents]
 
818
            n2 = [other._names[i] for i in other_parents]
 
819
            n1.sort()
 
820
            n2.sort()
 
821
            if n1 != n2:
 
822
                raise WeaveParentMismatch("inconsistent parents "
942
823
                    "for version {%s}: %s vs %s" % (name, n1, n2))
943
824
            else:
944
825
                return True         # ok!
945
826
        else:
946
827
            return False
947
828
 
948
 
    def _reweave(self, other, pb, msg):
949
 
        """Reweave self with other - internal helper for join().
950
 
 
951
 
        :param other: The other weave to merge
952
 
        :param pb: An optional progress bar, indicating how far done we are
953
 
        :param msg: An optional message for the progress
954
 
        """
955
 
        new_weave = _reweave(self, other, pb=pb, msg=msg)
956
 
        self._copy_weave_content(new_weave)
957
 
 
958
 
    def _copy_weave_content(self, otherweave):
959
 
        """adsorb the content from otherweave."""
 
829
    def reweave(self, other):
 
830
        """Reweave self with other."""
 
831
        new_weave = reweave(self, other)
960
832
        for attr in self.__slots__:
961
 
            if attr != '_weave_name':
962
 
                setattr(self, attr, copy(getattr(otherweave, attr)))
963
 
 
964
 
 
965
 
class WeaveFile(Weave):
966
 
    """A WeaveFile represents a Weave on disk and writes on change."""
967
 
 
968
 
    WEAVE_SUFFIX = '.weave'
969
 
 
970
 
    def __init__(self, name, transport, filemode=None, create=False,
971
 
                 access_mode='w', get_scope=None):
972
 
        """Create a WeaveFile.
973
 
 
974
 
        :param create: If not True, only open an existing knit.
975
 
        """
976
 
        super(WeaveFile, self).__init__(name, access_mode, get_scope=get_scope,
977
 
                                        allow_reserved=False)
978
 
        self._transport = transport
979
 
        self._filemode = filemode
980
 
        try:
981
 
            f = self._transport.get(name + WeaveFile.WEAVE_SUFFIX)
982
 
            _read_weave_v5(BytesIO(f.read()), self)
983
 
        except errors.NoSuchFile:
984
 
            if not create:
985
 
                raise
986
 
            # new file, save it
987
 
            self._save()
988
 
 
989
 
    def _add_lines(self, version_id, parents, lines, parent_texts,
990
 
                   left_matching_blocks, nostore_sha, random_id,
991
 
                   check_content):
992
 
        """Add a version and save the weave."""
993
 
        self.check_not_reserved_id(version_id)
994
 
        result = super(WeaveFile, self)._add_lines(
995
 
            version_id, parents, lines, parent_texts, left_matching_blocks,
996
 
            nostore_sha, random_id, check_content)
997
 
        self._save()
998
 
        return result
999
 
 
1000
 
    def copy_to(self, name, transport):
1001
 
        """See VersionedFile.copy_to()."""
1002
 
        # as we are all in memory always, just serialise to the new place.
1003
 
        sio = BytesIO()
1004
 
        write_weave_v5(self, sio)
1005
 
        sio.seek(0)
1006
 
        transport.put_file(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
1007
 
 
1008
 
    def _save(self):
1009
 
        """Save the weave."""
1010
 
        self._check_write_ok()
1011
 
        sio = BytesIO()
1012
 
        write_weave_v5(self, sio)
1013
 
        sio.seek(0)
1014
 
        bytes = sio.getvalue()
1015
 
        path = self._weave_name + WeaveFile.WEAVE_SUFFIX
1016
 
        try:
1017
 
            self._transport.put_bytes(path, bytes, self._filemode)
1018
 
        except errors.NoSuchFile:
1019
 
            self._transport.mkdir(dirname(path))
1020
 
            self._transport.put_bytes(path, bytes, self._filemode)
1021
 
 
1022
 
    @staticmethod
1023
 
    def get_suffixes():
1024
 
        """See VersionedFile.get_suffixes()."""
1025
 
        return [WeaveFile.WEAVE_SUFFIX]
1026
 
 
1027
 
    def insert_record_stream(self, stream):
1028
 
        super(WeaveFile, self).insert_record_stream(stream)
1029
 
        self._save()
1030
 
 
1031
 
 
1032
 
def _reweave(wa, wb, pb=None, msg=None):
 
833
            setattr(self, attr, getattr(new_weave, attr))
 
834
 
 
835
 
 
836
def reweave(wa, wb):
1033
837
    """Combine two weaves and return the result.
1034
838
 
1035
 
    This works even if a revision R has different parents in
 
839
    This works even if a revision R has different parents in 
1036
840
    wa and wb.  In the resulting weave all the parents are given.
1037
841
 
1038
 
    This is done by just building up a new weave, maintaining ordering
 
842
    This is done by just building up a new weave, maintaining ordering 
1039
843
    of the versions in the two inputs.  More efficient approaches
1040
 
    might be possible but it should only be necessary to do
1041
 
    this operation rarely, when a new previously ghost version is
 
844
    might be possible but it should only be necessary to do 
 
845
    this operation rarely, when a new previously ghost version is 
1042
846
    inserted.
1043
 
 
1044
 
    :param pb: An optional progress bar, indicating how far done we are
1045
 
    :param msg: An optional message for the progress
1046
847
    """
1047
848
    wr = Weave()
 
849
    ia = ib = 0
 
850
    queue_a = range(wa.numversions())
 
851
    queue_b = range(wb.numversions())
1048
852
    # first determine combined parents of all versions
1049
853
    # map from version name -> all parent names
1050
854
    combined_parents = _reweave_parent_graphs(wa, wb)
1051
855
    mutter("combined parents: %r", combined_parents)
1052
 
    order = tsort.topo_sort(combined_parents.items())
 
856
    order = topo_sort(combined_parents.iteritems())
1053
857
    mutter("order to reweave: %r", order)
1054
 
 
1055
 
    if pb and not msg:
1056
 
        msg = 'reweave'
1057
 
 
1058
 
    for idx, name in enumerate(order):
1059
 
        if pb:
1060
 
            pb.update(msg, idx, len(order))
 
858
    for name in order:
1061
859
        if name in wa._name_map:
1062
860
            lines = wa.get_lines(name)
1063
861
            if name in wb._name_map:
1064
 
                lines_b = wb.get_lines(name)
1065
 
                if lines != lines_b:
1066
 
                    mutter('Weaves differ on content. rev_id {%s}', name)
1067
 
                    mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
1068
 
                    import difflib
1069
 
                    lines = list(difflib.unified_diff(lines, lines_b,
1070
 
                                                      wa._weave_name, wb._weave_name))
1071
 
                    mutter('lines:\n%s', ''.join(lines))
1072
 
                    raise WeaveTextDiffers(name, wa, wb)
 
862
                assert lines == wb.get_lines(name)
1073
863
        else:
1074
864
            lines = wb.get_lines(name)
1075
 
        wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
 
865
        wr.add(name, combined_parents[name], lines)
1076
866
    return wr
1077
867
 
1078
868
 
1079
869
def _reweave_parent_graphs(wa, wb):
1080
870
    """Return combined parent ancestry for two weaves.
1081
 
 
 
871
    
1082
872
    Returned as a list of (version_name, set(parent_names))"""
1083
873
    combined = {}
1084
874
    for weave in [wa, wb]:
1085
875
        for idx, name in enumerate(weave._names):
1086
876
            p = combined.setdefault(name, set())
1087
 
            p.update(map(weave._idx_to_name, weave._parents[idx]))
 
877
            p.update(map(weave.idx_to_name, weave._parents[idx]))
1088
878
    return combined
 
879
 
 
880
 
 
881
def weave_toc(w):
 
882
    """Show the weave's table-of-contents"""
 
883
    print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
 
884
    for i in (6, 50, 10, 10):
 
885
        print '-' * i,
 
886
    print
 
887
    for i in range(w.numversions()):
 
888
        sha1 = w._sha1s[i]
 
889
        name = w._names[i]
 
890
        parent_str = ' '.join(map(str, w._parents[i]))
 
891
        print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
 
892
 
 
893
 
 
894
 
 
895
def weave_stats(weave_file, pb):
 
896
    from bzrlib.weavefile import read_weave
 
897
 
 
898
    wf = file(weave_file, 'rb')
 
899
    w = read_weave(wf)
 
900
    # FIXME: doesn't work on pipes
 
901
    weave_size = wf.tell()
 
902
 
 
903
    total = 0
 
904
    vers = len(w)
 
905
    for i in range(vers):
 
906
        pb.update('checking sizes', i, vers)
 
907
        for origin, lineno, line in w._extract([i]):
 
908
            total += len(line)
 
909
 
 
910
    pb.clear()
 
911
 
 
912
    print 'versions          %9d' % vers
 
913
    print 'weave file        %9d bytes' % weave_size
 
914
    print 'total contents    %9d bytes' % total
 
915
    print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
 
916
    if vers:
 
917
        avg = total/vers
 
918
        print 'average size      %9d bytes' % avg
 
919
        print 'relative size     %9.2fx' % (float(weave_size) / float(avg))
 
920
 
 
921
 
 
922
def usage():
 
923
    print """bzr weave tool
 
924
 
 
925
Experimental tool for weave algorithm.
 
926
 
 
927
usage:
 
928
    weave init WEAVEFILE
 
929
        Create an empty weave file
 
930
    weave get WEAVEFILE VERSION
 
931
        Write out specified version.
 
932
    weave check WEAVEFILE
 
933
        Check consistency of all versions.
 
934
    weave toc WEAVEFILE
 
935
        Display table of contents.
 
936
    weave add WEAVEFILE NAME [BASE...] < NEWTEXT
 
937
        Add NEWTEXT, with specified parent versions.
 
938
    weave annotate WEAVEFILE VERSION
 
939
        Display origin of each line.
 
940
    weave mash WEAVEFILE VERSION...
 
941
        Display composite of all selected versions.
 
942
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
 
943
        Auto-merge two versions and display conflicts.
 
944
    weave diff WEAVEFILE VERSION1 VERSION2 
 
945
        Show differences between two versions.
 
946
 
 
947
example:
 
948
 
 
949
    % weave init foo.weave
 
950
    % vi foo.txt
 
951
    % weave add foo.weave ver0 < foo.txt
 
952
    added version 0
 
953
 
 
954
    (create updated version)
 
955
    % vi foo.txt
 
956
    % weave get foo.weave 0 | diff -u - foo.txt
 
957
    % weave add foo.weave ver1 0 < foo.txt
 
958
    added version 1
 
959
 
 
960
    % weave get foo.weave 0 > foo.txt       (create forked version)
 
961
    % vi foo.txt
 
962
    % weave add foo.weave ver2 0 < foo.txt
 
963
    added version 2
 
964
 
 
965
    % weave merge foo.weave 1 2 > foo.txt   (merge them)
 
966
    % vi foo.txt                            (resolve conflicts)
 
967
    % weave add foo.weave merged 1 2 < foo.txt     (commit merged version)     
 
968
    
 
969
"""
 
970
    
 
971
 
 
972
 
 
973
def main(argv):
 
974
    import sys
 
975
    import os
 
976
    try:
 
977
        import bzrlib
 
978
    except ImportError:
 
979
        # in case we're run directly from the subdirectory
 
980
        sys.path.append('..')
 
981
        import bzrlib
 
982
    from bzrlib.weavefile import write_weave, read_weave
 
983
    from bzrlib.progress import ProgressBar
 
984
 
 
985
    try:
 
986
        import psyco
 
987
        psyco.full()
 
988
    except ImportError:
 
989
        pass
 
990
 
 
991
    if len(argv) < 2:
 
992
        usage()
 
993
        return 0
 
994
 
 
995
    cmd = argv[1]
 
996
 
 
997
    def readit():
 
998
        return read_weave(file(argv[2], 'rb'))
 
999
    
 
1000
    if cmd == 'help':
 
1001
        usage()
 
1002
    elif cmd == 'add':
 
1003
        w = readit()
 
1004
        # at the moment, based on everything in the file
 
1005
        name = argv[3]
 
1006
        parents = map(int, argv[4:])
 
1007
        lines = sys.stdin.readlines()
 
1008
        ver = w.add(name, parents, lines)
 
1009
        write_weave(w, file(argv[2], 'wb'))
 
1010
        print 'added version %r %d' % (name, ver)
 
1011
    elif cmd == 'init':
 
1012
        fn = argv[2]
 
1013
        if os.path.exists(fn):
 
1014
            raise IOError("file exists")
 
1015
        w = Weave()
 
1016
        write_weave(w, file(fn, 'wb'))
 
1017
    elif cmd == 'get': # get one version
 
1018
        w = readit()
 
1019
        sys.stdout.writelines(w.get_iter(int(argv[3])))
 
1020
        
 
1021
    elif cmd == 'mash': # get composite
 
1022
        w = readit()
 
1023
        sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
 
1024
 
 
1025
    elif cmd == 'diff':
 
1026
        from difflib import unified_diff
 
1027
        w = readit()
 
1028
        fn = argv[2]
 
1029
        v1, v2 = map(int, argv[3:5])
 
1030
        lines1 = w.get(v1)
 
1031
        lines2 = w.get(v2)
 
1032
        diff_gen = unified_diff(lines1, lines2,
 
1033
                                '%s version %d' % (fn, v1),
 
1034
                                '%s version %d' % (fn, v2))
 
1035
        sys.stdout.writelines(diff_gen)
 
1036
            
 
1037
    elif cmd == 'annotate':
 
1038
        w = readit()
 
1039
        # newline is added to all lines regardless; too hard to get
 
1040
        # reasonable formatting otherwise
 
1041
        lasto = None
 
1042
        for origin, text in w.annotate(int(argv[3])):
 
1043
            text = text.rstrip('\r\n')
 
1044
            if origin == lasto:
 
1045
                print '      | %s' % (text)
 
1046
            else:
 
1047
                print '%5d | %s' % (origin, text)
 
1048
                lasto = origin
 
1049
                
 
1050
    elif cmd == 'toc':
 
1051
        weave_toc(readit())
 
1052
 
 
1053
    elif cmd == 'stats':
 
1054
        weave_stats(argv[2], ProgressBar())
 
1055
        
 
1056
    elif cmd == 'check':
 
1057
        w = readit()
 
1058
        pb = ProgressBar()
 
1059
        w.check(pb)
 
1060
        pb.clear()
 
1061
        print '%d versions ok' % w.numversions()
 
1062
 
 
1063
    elif cmd == 'inclusions':
 
1064
        w = readit()
 
1065
        print ' '.join(map(str, w.inclusions([int(argv[3])])))
 
1066
 
 
1067
    elif cmd == 'parents':
 
1068
        w = readit()
 
1069
        print ' '.join(map(str, w._parents[int(argv[3])]))
 
1070
 
 
1071
    elif cmd == 'plan-merge':
 
1072
        w = readit()
 
1073
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
 
1074
            if line:
 
1075
                print '%14s | %s' % (state, line),
 
1076
 
 
1077
    elif cmd == 'merge':
 
1078
        w = readit()
 
1079
        p = w.plan_merge(int(argv[3]), int(argv[4]))
 
1080
        sys.stdout.writelines(w.weave_merge(p))
 
1081
            
 
1082
    elif cmd == 'mash-merge':
 
1083
        if len(argv) != 5:
 
1084
            usage()
 
1085
            return 1
 
1086
 
 
1087
        w = readit()
 
1088
        v1, v2 = map(int, argv[3:5])
 
1089
 
 
1090
        basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
 
1091
 
 
1092
        base_lines = list(w.mash_iter(basis))
 
1093
        a_lines = list(w.get(v1))
 
1094
        b_lines = list(w.get(v2))
 
1095
 
 
1096
        from bzrlib.merge3 import Merge3
 
1097
        m3 = Merge3(base_lines, a_lines, b_lines)
 
1098
 
 
1099
        name_a = 'version %d' % v1
 
1100
        name_b = 'version %d' % v2
 
1101
        sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
 
1102
    else:
 
1103
        raise ValueError('unknown command %r' % cmd)
 
1104
    
 
1105
 
 
1106
 
 
1107
def profile_main(argv): 
 
1108
    import tempfile, hotshot, hotshot.stats
 
1109
 
 
1110
    prof_f = tempfile.NamedTemporaryFile()
 
1111
 
 
1112
    prof = hotshot.Profile(prof_f.name)
 
1113
 
 
1114
    ret = prof.runcall(main, argv)
 
1115
    prof.close()
 
1116
 
 
1117
    stats = hotshot.stats.load(prof_f.name)
 
1118
    #stats.strip_dirs()
 
1119
    stats.sort_stats('cumulative')
 
1120
    ## XXX: Might like to write to stderr or the trace file instead but
 
1121
    ## print_stats seems hardcoded to stdout
 
1122
    stats.print_stats(20)
 
1123
            
 
1124
    return ret
 
1125
 
 
1126
 
 
1127
if __name__ == '__main__':
 
1128
    import sys
 
1129
    if '--profile' in sys.argv:
 
1130
        args = sys.argv[:]
 
1131
        args.remove('--profile')
 
1132
        sys.exit(profile_main(args))
 
1133
    else:
 
1134
        sys.exit(main(sys.argv))
 
1135