~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

add a clean target

Show diffs side-by-side

added added

removed removed

Lines of Context:
21
21
 
22
22
"""Weave - storage of related text file versions"""
23
23
 
 
24
# before intset (r923) 2000 versions in 41.5s
 
25
# with intset (r926) 2000 versions in 93s !!!
 
26
# better to just use plain sets.
 
27
 
 
28
# making _extract build and return a list, rather than being a generator
 
29
# takes 37.94s
 
30
 
 
31
# with python -O, r923 does 2000 versions in 36.87s
 
32
 
 
33
# with optimizations to avoid mutating lists - 35.75!  I guess copying
 
34
# all the elements every time costs more than the small manipulations.
 
35
# a surprisingly small change.
 
36
 
 
37
# r931, which avoids using a generator for extract, does 36.98s
 
38
 
 
39
# with memoized inclusions, takes 41.49s; not very good
 
40
 
 
41
# with slots, takes 37.35s; without takes 39.16, a bit surprising
 
42
 
 
43
# with the delta calculation mixed in with the add method, rather than
 
44
# separated, takes 36.78s
 
45
 
 
46
# with delta folded in and mutation of the list, 36.13s
 
47
 
 
48
# with all this and simplification of add code, 33s
 
49
 
 
50
 
 
51
 
 
52
 
 
53
 
 
54
# TODO: Perhaps have copy method for Weave instances?
24
55
 
25
56
# XXX: If we do weaves this way, will a merge still behave the same
26
57
# way if it's done in a different order?  That's a pretty desirable
27
58
# property.
28
59
 
29
60
# TODO: Nothing here so far assumes the lines are really \n newlines,
30
 
# rather than being split up in some other way.  We could accommodate
 
61
# rather than being split up in some other way.  We could accomodate
31
62
# binaries, perhaps by naively splitting on \n or perhaps using
32
63
# something like a rolling checksum.
33
64
 
43
74
 
44
75
# TODO: Parallel-extract that passes back each line along with a
45
76
# description of which revisions include it.  Nice for checking all
46
 
# shas or calculating stats in parallel.
 
77
# shas in parallel.
47
78
 
48
79
# TODO: Using a single _extract routine and then processing the output
49
80
# is probably inefficient.  It's simple enough that we can afford to
50
81
# have slight specializations for different ways its used: annotate,
51
82
# basis for add, get, etc.
52
83
 
53
 
# TODO: Probably the API should work only in names to hide the integer
54
 
# indexes from the user.
55
 
 
56
 
# TODO: Is there any potential performance win by having an add()
57
 
# variant that is passed a pre-cooked version of the single basis
58
 
# version?
59
 
 
60
 
# TODO: Reweave can possibly be made faster by remembering diffs
61
 
# where the basis and destination are unchanged.
62
 
 
63
 
# FIXME: Sometimes we will be given a parents list for a revision
64
 
# that includes some redundant parents (i.e. already a parent of 
65
 
# something in the list.)  We should eliminate them.  This can 
66
 
# be done fairly efficiently because the sequence numbers constrain
67
 
# the possible relationships.
68
 
 
69
 
# FIXME: the conflict markers should be *7* characters
70
 
 
71
 
from copy import copy
72
 
from cStringIO import StringIO
73
 
import os
 
84
# TODO: Perhaps the API should work only in names to hide the integer
 
85
# indexes from the user?
 
86
 
 
87
 
 
88
 
74
89
import sha
75
 
import time
76
 
 
77
 
from bzrlib.trace import mutter
78
 
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
79
 
        RevisionAlreadyPresent,
80
 
        RevisionNotPresent,
81
 
        WeaveRevisionAlreadyPresent,
82
 
        WeaveRevisionNotPresent,
83
 
        )
84
 
import bzrlib.errors as errors
85
 
from bzrlib.osutils import sha_strings
86
 
import bzrlib.patiencediff
87
 
from bzrlib.symbol_versioning import *
88
 
from bzrlib.tsort import topo_sort
89
 
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
90
 
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
91
 
 
92
 
 
93
 
class Weave(VersionedFile):
 
90
 
 
91
 
 
92
 
 
93
class WeaveError(Exception):
 
94
    """Exception in processing weave"""
 
95
 
 
96
 
 
97
class WeaveFormatError(WeaveError):
 
98
    """Weave invariant violated"""
 
99
    
 
100
 
 
101
class Weave(object):
94
102
    """weave - versioned text file storage.
95
103
    
96
104
    A Weave manages versions of line-based text files, keeping track
105
113
 
106
114
    * a nonnegative index number.
107
115
 
108
 
    * a version-id string.
 
116
    * a version-id string. (not implemented yet)
109
117
 
110
118
    Typically the index number will be valid only inside this weave and
111
119
    the version-id is used to reference it in the larger world.
173
181
 
174
182
    _name_map
175
183
        For each name, the version number.
176
 
 
177
 
    _weave_name
178
 
        Descriptive name of this weave; typically the filename if known.
179
 
        Set by read_weave.
180
184
    """
181
185
 
182
 
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
183
 
                 '_weave_name', '_matcher']
 
186
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map']
184
187
    
185
 
    def __init__(self, weave_name=None, access_mode='w', matcher=None):
186
 
        super(Weave, self).__init__(access_mode)
 
188
    def __init__(self):
187
189
        self._weave = []
188
190
        self._parents = []
189
191
        self._sha1s = []
190
192
        self._names = []
191
193
        self._name_map = {}
192
 
        self._weave_name = weave_name
193
 
        if matcher is None:
194
 
            self._matcher = bzrlib.patiencediff.PatienceSequenceMatcher
195
 
        else:
196
 
            self._matcher = matcher
197
 
 
198
 
    def __repr__(self):
199
 
        return "Weave(%r)" % self._weave_name
200
 
 
201
 
    def copy(self):
202
 
        """Return a deep copy of self.
203
 
        
204
 
        The copy can be modified without affecting the original weave."""
205
 
        other = Weave()
206
 
        other._weave = self._weave[:]
207
 
        other._parents = self._parents[:]
208
 
        other._sha1s = self._sha1s[:]
209
 
        other._names = self._names[:]
210
 
        other._name_map = self._name_map.copy()
211
 
        other._weave_name = self._weave_name
212
 
        return other
 
194
 
213
195
 
214
196
    def __eq__(self, other):
215
197
        if not isinstance(other, Weave):
217
199
        return self._parents == other._parents \
218
200
               and self._weave == other._weave \
219
201
               and self._sha1s == other._sha1s 
 
202
 
220
203
    
221
204
    def __ne__(self, other):
222
205
        return not self.__eq__(other)
223
206
 
224
 
    @deprecated_method(zero_eight)
225
 
    def idx_to_name(self, index):
226
 
        """Old public interface, the public interface is all names now."""
227
 
        return index
228
 
 
229
 
    def _idx_to_name(self, version):
230
 
        return self._names[version]
231
 
 
232
 
    @deprecated_method(zero_eight)
 
207
 
233
208
    def lookup(self, name):
234
 
        """Backwards compatibility thunk:
235
 
 
236
 
        Return name, as name is valid in the api now, and spew deprecation
237
 
        warnings everywhere.
238
 
        """
239
 
        return name
240
 
 
241
 
    def _lookup(self, name):
242
 
        """Convert symbolic version name to index."""
243
209
        try:
244
210
            return self._name_map[name]
245
211
        except KeyError:
246
 
            raise RevisionNotPresent(name, self._weave_name)
247
 
 
248
 
    @deprecated_method(zero_eight)
249
 
    def iter_names(self):
250
 
        """Deprecated convenience function, please see VersionedFile.names()."""
251
 
        return iter(self.names())
252
 
 
253
 
    @deprecated_method(zero_eight)
254
 
    def names(self):
255
 
        """See Weave.versions for the current api."""
256
 
        return self.versions()
257
 
 
258
 
    def versions(self):
259
 
        """See VersionedFile.versions."""
260
 
        return self._names[:]
261
 
 
262
 
    def has_version(self, version_id):
263
 
        """See VersionedFile.has_version."""
264
 
        return self._name_map.has_key(version_id)
265
 
 
266
 
    __contains__ = has_version
267
 
 
268
 
    def get_delta(self, version_id):
269
 
        """See VersionedFile.get_delta."""
270
 
        return self.get_deltas([version_id])[version_id]
271
 
 
272
 
    def get_deltas(self, version_ids):
273
 
        """See VersionedFile.get_deltas."""
274
 
        version_ids = self.get_ancestry(version_ids)
275
 
        for version_id in version_ids:
276
 
            if not self.has_version(version_id):
277
 
                raise RevisionNotPresent(version_id, self)
278
 
        # try extracting all versions; parallel extraction is used
279
 
        nv = self.num_versions()
280
 
        sha1s = {}
281
 
        deltas = {}
282
 
        texts = {}
283
 
        inclusions = {}
284
 
        noeols = {}
285
 
        last_parent_lines = {}
286
 
        parents = {}
287
 
        parent_inclusions = {}
288
 
        parent_linenums = {}
289
 
        parent_noeols = {}
290
 
        current_hunks = {}
291
 
        diff_hunks = {}
292
 
        # its simplest to generate a full set of prepared variables.
293
 
        for i in range(nv):
294
 
            name = self._names[i]
295
 
            sha1s[name] = self.get_sha1(name)
296
 
            parents_list = self.get_parents(name)
297
 
            try:
298
 
                parent = parents_list[0]
299
 
                parents[name] = parent
300
 
                parent_inclusions[name] = inclusions[parent]
301
 
            except IndexError:
302
 
                parents[name] = None
303
 
                parent_inclusions[name] = set()
304
 
            # we want to emit start, finish, replacement_length, replacement_lines tuples.
305
 
            diff_hunks[name] = []
306
 
            current_hunks[name] = [0, 0, 0, []] # #start, finish, repl_length, repl_tuples
307
 
            parent_linenums[name] = 0
308
 
            noeols[name] = False
309
 
            parent_noeols[name] = False
310
 
            last_parent_lines[name] = None
311
 
            new_inc = set([name])
312
 
            for p in self._parents[i]:
313
 
                new_inc.update(inclusions[self._idx_to_name(p)])
314
 
            # debug only, known good so far.
315
 
            #assert set(new_inc) == set(self.get_ancestry(name)), \
316
 
            #    'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))
317
 
            inclusions[name] = new_inc
318
 
 
319
 
        nlines = len(self._weave)
320
 
 
321
 
        for lineno, inserted, deletes, line in self._walk_internal():
322
 
            # a line is active in a version if:
323
 
            # insert is in the versions inclusions
324
 
            # and
325
 
            # deleteset & the versions inclusions is an empty set.
326
 
            # so - if we have a included by mapping - version is included by
327
 
            # children, we get a list of children to examine for deletes affect
328
 
            # ing them, which is less than the entire set of children.
329
 
            for version_id in version_ids:  
330
 
                # The active inclusion must be an ancestor,
331
 
                # and no ancestors must have deleted this line,
332
 
                # because we don't support resurrection.
333
 
                parent_inclusion = parent_inclusions[version_id]
334
 
                inclusion = inclusions[version_id]
335
 
                parent_active = inserted in parent_inclusion and not (deletes & parent_inclusion)
336
 
                version_active = inserted in inclusion and not (deletes & inclusion)
337
 
                if not parent_active and not version_active:
338
 
                    # unrelated line of ancestry
339
 
                    continue
340
 
                elif parent_active and version_active:
341
 
                    # shared line
342
 
                    parent_linenum = parent_linenums[version_id]
343
 
                    if current_hunks[version_id] != [parent_linenum, parent_linenum, 0, []]:
344
 
                        diff_hunks[version_id].append(tuple(current_hunks[version_id]))
345
 
                    parent_linenum += 1
346
 
                    current_hunks[version_id] = [parent_linenum, parent_linenum, 0, []]
347
 
                    parent_linenums[version_id] = parent_linenum
348
 
                    try:
349
 
                        if line[-1] != '\n':
350
 
                            noeols[version_id] = True
351
 
                    except IndexError:
352
 
                        pass
353
 
                elif parent_active and not version_active:
354
 
                    # deleted line
355
 
                    current_hunks[version_id][1] += 1
356
 
                    parent_linenums[version_id] += 1
357
 
                    last_parent_lines[version_id] = line
358
 
                elif not parent_active and version_active:
359
 
                    # replacement line
360
 
                    # noeol only occurs at the end of a file because we 
361
 
                    # diff linewise. We want to show noeol changes as a
362
 
                    # empty diff unless the actual eol-less content changed.
363
 
                    theline = line
364
 
                    try:
365
 
                        if last_parent_lines[version_id][-1] != '\n':
366
 
                            parent_noeols[version_id] = True
367
 
                    except (TypeError, IndexError):
368
 
                        pass
369
 
                    try:
370
 
                        if theline[-1] != '\n':
371
 
                            noeols[version_id] = True
372
 
                    except IndexError:
373
 
                        pass
374
 
                    new_line = False
375
 
                    parent_should_go = False
376
 
 
377
 
                    if parent_noeols[version_id] == noeols[version_id]:
378
 
                        # no noeol toggle, so trust the weaves statement
379
 
                        # that this line is changed.
380
 
                        new_line = True
381
 
                        if parent_noeols[version_id]:
382
 
                            theline = theline + '\n'
383
 
                    elif parent_noeols[version_id]:
384
 
                        # parent has no eol, we do:
385
 
                        # our line is new, report as such..
386
 
                        new_line = True
387
 
                    elif noeols[version_id]:
388
 
                        # append a eol so that it looks like
389
 
                        # a normalised delta
390
 
                        theline = theline + '\n'
391
 
                        if parents[version_id] is not None:
392
 
                        #if last_parent_lines[version_id] is not None:
393
 
                            parent_should_go = True
394
 
                        if last_parent_lines[version_id] != theline:
395
 
                            # but changed anyway
396
 
                            new_line = True
397
 
                            #parent_should_go = False
398
 
                    if new_line:
399
 
                        current_hunks[version_id][2] += 1
400
 
                        current_hunks[version_id][3].append((inserted, theline))
401
 
                    if parent_should_go:
402
 
                        # last hunk last parent line is not eaten
403
 
                        current_hunks[version_id][1] -= 1
404
 
                    if current_hunks[version_id][1] < 0:
405
 
                        current_hunks[version_id][1] = 0
406
 
                        # import pdb;pdb.set_trace()
407
 
                    # assert current_hunks[version_id][1] >= 0
408
 
 
409
 
        # flush last hunk
410
 
        for i in range(nv):
411
 
            version = self._idx_to_name(i)
412
 
            if current_hunks[version] != [0, 0, 0, []]:
413
 
                diff_hunks[version].append(tuple(current_hunks[version]))
414
 
        result = {}
415
 
        for version_id in version_ids:
416
 
            result[version_id] = (
417
 
                                  parents[version_id],
418
 
                                  sha1s[version_id],
419
 
                                  noeols[version_id],
420
 
                                  diff_hunks[version_id],
421
 
                                  )
422
 
        return result
423
 
 
424
 
    def get_parents(self, version_id):
425
 
        """See VersionedFile.get_parent."""
426
 
        return map(self._idx_to_name, self._parents[self._lookup(version_id)])
427
 
 
428
 
    def _check_repeated_add(self, name, parents, text, sha1):
429
 
        """Check that a duplicated add is OK.
430
 
 
431
 
        If it is, return the (old) index; otherwise raise an exception.
432
 
        """
433
 
        idx = self._lookup(name)
434
 
        if sorted(self._parents[idx]) != sorted(parents) \
435
 
            or sha1 != self._sha1s[idx]:
436
 
            raise RevisionAlreadyPresent(name, self._weave_name)
437
 
        return idx
438
 
 
439
 
    @deprecated_method(zero_eight)
440
 
    def add_identical(self, old_rev_id, new_rev_id, parents):
441
 
        """Please use Weave.clone_text now."""
442
 
        return self.clone_text(new_rev_id, old_rev_id, parents)
443
 
 
444
 
    def _add_lines(self, version_id, parents, lines, parent_texts):
445
 
        """See VersionedFile.add_lines."""
446
 
        return self._add(version_id, lines, map(self._lookup, parents))
447
 
 
448
 
    @deprecated_method(zero_eight)
449
 
    def add(self, name, parents, text, sha1=None):
450
 
        """See VersionedFile.add_lines for the non deprecated api."""
451
 
        return self._add(name, text, map(self._maybe_lookup, parents), sha1)
452
 
 
453
 
    def _add(self, version_id, lines, parents, sha1=None):
 
212
            raise WeaveError("name %s not present in weave" % name)
 
213
 
 
214
        
 
215
    def add(self, name, parents, text):
454
216
        """Add a single text on top of the weave.
455
217
  
456
218
        Returns the index number of the newly added version.
457
219
 
458
 
        version_id
 
220
        name
459
221
            Symbolic name for this version.
460
222
            (Typically the revision-id of the revision that added it.)
461
223
 
462
224
        parents
463
225
            List or set of direct parent version numbers.
464
226
            
465
 
        lines
466
 
            Sequence of lines to be added in the new version.
467
 
        """
468
 
 
469
 
        assert isinstance(version_id, basestring)
470
 
        self._check_lines_not_unicode(lines)
471
 
        self._check_lines_are_lines(lines)
472
 
        if not sha1:
473
 
            sha1 = sha_strings(lines)
474
 
        if version_id in self._name_map:
475
 
            return self._check_repeated_add(version_id, parents, lines, sha1)
476
 
 
 
227
        text
 
228
            Sequence of lines to be added in the new version."""
 
229
 
 
230
        assert isinstance(name, basestring)
 
231
        if name in self._name_map:
 
232
            raise WeaveError("name %r already present in weave" % name)
 
233
        
477
234
        self._check_versions(parents)
478
 
        ## self._check_lines(lines)
 
235
        ## self._check_lines(text)
479
236
        new_version = len(self._parents)
480
237
 
 
238
        s = sha.new()
 
239
        map(s.update, text)
 
240
        sha1 = s.hexdigest()
 
241
        del s
 
242
 
481
243
        # if we abort after here the (in-memory) weave will be corrupt because only
482
244
        # some fields are updated
483
 
        # XXX: FIXME implement a succeed-or-fail of the rest of this routine.
484
 
        #      - Robert Collins 20060226
485
245
        self._parents.append(parents[:])
486
246
        self._sha1s.append(sha1)
487
 
        self._names.append(version_id)
488
 
        self._name_map[version_id] = new_version
 
247
        self._names.append(name)
 
248
        self._name_map[name] = new_version
489
249
 
490
250
            
491
251
        if not parents:
493
253
            # this more quickly by just appending unconditionally.
494
254
            # even more specially, if we're adding an empty text we
495
255
            # need do nothing at all.
496
 
            if lines:
 
256
            if text:
497
257
                self._weave.append(('{', new_version))
498
 
                self._weave.extend(lines)
 
258
                self._weave.extend(text)
499
259
                self._weave.append(('}', None))
 
260
        
500
261
            return new_version
501
262
 
502
263
        if len(parents) == 1:
506
267
                return new_version
507
268
            
508
269
 
509
 
        ancestors = self._inclusions(parents)
 
270
        ancestors = self.inclusions(parents)
510
271
 
511
272
        l = self._weave
512
273
 
519
280
 
520
281
        # another small special case: a merge, producing the same text
521
282
        # as auto-merge
522
 
        if lines == basis_lines:
 
283
        if text == basis_lines:
523
284
            return new_version            
524
285
 
525
 
        # add a sentinel, because we can also match against the final line
 
286
        # add a sentinal, because we can also match against the final line
526
287
        basis_lineno.append(len(self._weave))
527
288
 
528
289
        # XXX: which line of the weave should we really consider
532
293
        #print 'basis_lines:', basis_lines
533
294
        #print 'new_lines:  ', lines
534
295
 
535
 
        s = self._matcher(None, basis_lines, lines)
 
296
        from difflib import SequenceMatcher
 
297
        s = SequenceMatcher(None, basis_lines, text)
536
298
 
537
299
        # offset gives the number of lines that have been inserted
538
300
        # into the weave up to the current point; if the original edit instruction
549
311
            i1 = basis_lineno[i1]
550
312
            i2 = basis_lineno[i2]
551
313
 
552
 
            assert 0 <= j1 <= j2 <= len(lines)
 
314
            assert 0 <= j1 <= j2 <= len(text)
553
315
 
554
316
            #print tag, i1, i2, j1, j2
555
317
 
566
328
                # we don't destroy ourselves
567
329
                i = i2 + offset
568
330
                self._weave[i:i] = ([('{', new_version)] 
569
 
                                    + lines[j1:j2] 
 
331
                                    + text[j1:j2] 
570
332
                                    + [('}', None)])
571
333
                offset += 2 + (j2 - j1)
 
334
 
572
335
        return new_version
573
336
 
574
 
    def _clone_text(self, new_version_id, old_version_id, parents):
575
 
        """See VersionedFile.clone_text."""
576
 
        old_lines = self.get_text(old_version_id)
577
 
        self.add_lines(new_version_id, parents, old_lines)
578
337
 
579
 
    def _inclusions(self, versions):
 
338
    def inclusions(self, versions):
580
339
        """Return set of all ancestors of given version(s)."""
581
 
        if not len(versions):
582
 
            return []
583
340
        i = set(versions)
584
 
        for v in xrange(max(versions), 0, -1):
585
 
            if v in i:
586
 
                # include all its parents
587
 
                i.update(self._parents[v])
588
 
        return i
589
 
        ## except IndexError:
590
 
        ##     raise ValueError("version %d not present in weave" % v)
591
 
 
592
 
    @deprecated_method(zero_eight)
593
 
    def inclusions(self, version_ids):
594
 
        """Deprecated - see VersionedFile.get_ancestry for the replacement."""
595
 
        if not version_ids:
 
341
        v = max(versions)
 
342
        try:
 
343
            while v >= 0:
 
344
                if v in i:
 
345
                    # include all its parents
 
346
                    i.update(self._parents[v])
 
347
                v -= 1
 
348
            return i
 
349
        except IndexError:
 
350
            raise ValueError("version %d not present in weave" % v)
 
351
 
 
352
 
 
353
    def minimal_parents(self, version):
 
354
        """Find the minimal set of parents for the version."""
 
355
        included = self._parents[version]
 
356
        if not included:
596
357
            return []
597
 
        if isinstance(version_ids[0], int):
598
 
            return [self._idx_to_name(v) for v in self._inclusions(version_ids)]
599
 
        else:
600
 
            return self.get_ancestry(version_ids)
601
 
 
602
 
    def get_ancestry(self, version_ids):
603
 
        """See VersionedFile.get_ancestry."""
604
 
        if isinstance(version_ids, basestring):
605
 
            version_ids = [version_ids]
606
 
        i = self._inclusions([self._lookup(v) for v in version_ids])
607
 
        return [self._idx_to_name(v) for v in i]
 
358
        
 
359
        li = list(included)
 
360
        li.sort(reverse=True)
 
361
 
 
362
        mininc = []
 
363
        gotit = set()
 
364
 
 
365
        for pv in li:
 
366
            if pv not in gotit:
 
367
                mininc.append(pv)
 
368
                gotit.update(self.inclusions(pv))
 
369
 
 
370
        assert mininc[0] >= 0
 
371
        assert mininc[-1] < version
 
372
        return mininc
 
373
 
 
374
 
608
375
 
609
376
    def _check_lines(self, text):
610
377
        if not isinstance(text, list):
625
392
            except IndexError:
626
393
                raise IndexError("invalid version number %r" % i)
627
394
 
628
 
    def _compatible_parents(self, my_parents, other_parents):
629
 
        """During join check that other_parents are joinable with my_parents.
630
 
 
631
 
        Joinable is defined as 'is a subset of' - supersets may require 
632
 
        regeneration of diffs, but subsets do not.
633
 
        """
634
 
        return len(other_parents.difference(my_parents)) == 0
635
 
 
636
 
    def annotate(self, version_id):
637
 
        if isinstance(version_id, int):
638
 
            warn('Weave.annotate(int) is deprecated. Please use version names'
639
 
                 ' in all circumstances as of 0.8',
640
 
                 DeprecationWarning,
641
 
                 stacklevel=2
642
 
                 )
643
 
            result = []
644
 
            for origin, lineno, text in self._extract([version_id]):
645
 
                result.append((origin, text))
646
 
            return result
647
 
        else:
648
 
            return super(Weave, self).annotate(version_id)
649
395
    
650
 
    def annotate_iter(self, version_id):
651
 
        """Yield list of (version-id, line) pairs for the specified version.
 
396
    def annotate(self, index):
 
397
        return list(self.annotate_iter(index))
 
398
 
 
399
 
 
400
    def annotate_iter(self, version):
 
401
        """Yield list of (index-id, line) pairs for the specified version.
652
402
 
653
403
        The index indicates when the line originated in the weave."""
654
 
        incls = [self._lookup(version_id)]
655
 
        for origin, lineno, text in self._extract(incls):
656
 
            yield self._idx_to_name(origin), text
657
 
 
658
 
    @deprecated_method(zero_eight)
 
404
        for origin, lineno, text in self._extract([version]):
 
405
            yield origin, text
 
406
 
 
407
 
659
408
    def _walk(self):
660
 
        """_walk has become visit, a supported api."""
661
 
        return self._walk_internal()
662
 
 
663
 
    def iter_lines_added_or_present_in_versions(self, version_ids=None):
664
 
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
665
 
        if version_ids is None:
666
 
            version_ids = self.versions()
667
 
        version_ids = set(version_ids)
668
 
        for lineno, inserted, deletes, line in self._walk_internal(version_ids):
669
 
            # if inserted not in version_ids then it was inserted before the
670
 
            # versions we care about, but because weaves cannot represent ghosts
671
 
            # properly, we do not filter down to that
672
 
            # if inserted not in version_ids: continue
673
 
            if line[-1] != '\n':
674
 
                yield line + '\n'
675
 
            else:
676
 
                yield line
677
 
 
678
 
    #@deprecated_method(zero_eight)
679
 
    def walk(self, version_ids=None):
680
 
        """See VersionedFile.walk."""
681
 
        return self._walk_internal(version_ids)
682
 
 
683
 
    def _walk_internal(self, version_ids=None):
684
 
        """Helper method for weave actions."""
 
409
        """Walk the weave.
 
410
 
 
411
        Yields sequence of
 
412
        (lineno, insert, deletes, text)
 
413
        for each literal line.
 
414
        """
685
415
        
686
416
        istack = []
687
417
        dset = set()
689
419
        lineno = 0         # line of weave, 0-based
690
420
 
691
421
        for l in self._weave:
692
 
            if l.__class__ == tuple:
 
422
            if isinstance(l, tuple):
693
423
                c, v = l
694
424
                isactive = None
695
425
                if c == '{':
696
 
                    istack.append(self._names[v])
 
426
                    istack.append(v)
697
427
                elif c == '}':
698
428
                    istack.pop()
699
429
                elif c == '[':
700
 
                    assert self._names[v] not in dset
701
 
                    dset.add(self._names[v])
 
430
                    assert v not in dset
 
431
                    dset.add(v)
702
432
                elif c == ']':
703
 
                    dset.remove(self._names[v])
 
433
                    dset.remove(v)
704
434
                else:
705
 
                    raise WeaveFormatError('unexpected instruction %r' % v)
 
435
                    raise WeaveFormatError('unexpected instruction %r'
 
436
                                           % v)
706
437
            else:
707
 
                assert l.__class__ in (str, unicode)
 
438
                assert isinstance(l, basestring)
708
439
                assert istack
709
 
                yield lineno, istack[-1], frozenset(dset), l
 
440
                yield lineno, istack[-1], dset, l
710
441
            lineno += 1
711
442
 
712
 
        if istack:
713
 
            raise WeaveFormatError("unclosed insertion blocks "
714
 
                    "at end of weave: %s" % istack)
715
 
        if dset:
716
 
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
717
 
                                   % dset)
718
 
 
719
 
    def plan_merge(self, ver_a, ver_b):
720
 
        """Return pseudo-annotation indicating how the two versions merge.
721
 
 
722
 
        This is computed between versions a and b and their common
723
 
        base.
724
 
 
725
 
        Weave lines present in none of them are skipped entirely.
726
 
        """
727
 
        inc_a = set(self.get_ancestry([ver_a]))
728
 
        inc_b = set(self.get_ancestry([ver_b]))
729
 
        inc_c = inc_a & inc_b
730
 
 
731
 
        for lineno, insert, deleteset, line in\
732
 
            self.walk([ver_a, ver_b]):
733
 
            if deleteset & inc_c:
734
 
                # killed in parent; can't be in either a or b
735
 
                # not relevant to our work
736
 
                yield 'killed-base', line
737
 
            elif insert in inc_c:
738
 
                # was inserted in base
739
 
                killed_a = bool(deleteset & inc_a)
740
 
                killed_b = bool(deleteset & inc_b)
741
 
                if killed_a and killed_b:
742
 
                    yield 'killed-both', line
743
 
                elif killed_a:
744
 
                    yield 'killed-a', line
745
 
                elif killed_b:
746
 
                    yield 'killed-b', line
747
 
                else:
748
 
                    yield 'unchanged', line
749
 
            elif insert in inc_a:
750
 
                if deleteset & inc_a:
751
 
                    yield 'ghost-a', line
752
 
                else:
753
 
                    # new in A; not in B
754
 
                    yield 'new-a', line
755
 
            elif insert in inc_b:
756
 
                if deleteset & inc_b:
757
 
                    yield 'ghost-b', line
758
 
                else:
759
 
                    yield 'new-b', line
760
 
            else:
761
 
                # not in either revision
762
 
                yield 'irrelevant', line
763
 
 
764
 
        yield 'unchanged', ''           # terminator
 
443
 
765
444
 
766
445
    def _extract(self, versions):
767
446
        """Yield annotation of lines in included set.
772
451
 
773
452
        The set typically but not necessarily corresponds to a version.
774
453
        """
775
 
        for i in versions:
776
 
            if not isinstance(i, int):
777
 
                raise ValueError(i)
778
 
            
779
 
        included = self._inclusions(versions)
 
454
        included = self.inclusions(versions)
780
455
 
781
456
        istack = []
782
 
        iset = set()
783
457
        dset = set()
784
458
 
785
459
        lineno = 0         # line of weave, 0-based
790
464
 
791
465
        WFE = WeaveFormatError
792
466
 
793
 
        # wow. 
794
 
        #  449       0   4474.6820   2356.5590   bzrlib.weave:556(_extract)
795
 
        #  +285282   0   1676.8040   1676.8040   +<isinstance>
796
 
        # 1.6 seconds in 'isinstance'.
797
 
        # changing the first isinstance:
798
 
        #  449       0   2814.2660   1577.1760   bzrlib.weave:556(_extract)
799
 
        #  +140414   0    762.8050    762.8050   +<isinstance>
800
 
        # note that the inline time actually dropped (less function calls)
801
 
        # and total processing time was halved.
802
 
        # we're still spending ~1/4 of the method in isinstance though.
803
 
        # so lets hard code the acceptable string classes we expect:
804
 
        #  449       0   1202.9420    786.2930   bzrlib.weave:556(_extract)
805
 
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list' 
806
 
        #                                          objects>
807
 
        # yay, down to ~1/4 the initial extract time, and our inline time
808
 
        # has shrunk again, with isinstance no longer dominating.
809
 
        # tweaking the stack inclusion test to use a set gives:
810
 
        #  449       0   1122.8030    713.0080   bzrlib.weave:556(_extract)
811
 
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list' 
812
 
        #                                          objects>
813
 
        # - a 5% win, or possibly just noise. However with large istacks that
814
 
        # 'in' test could dominate, so I'm leaving this change in place -
815
 
        # when its fast enough to consider profiling big datasets we can review.
816
 
 
817
 
              
818
 
             
819
 
 
820
467
        for l in self._weave:
821
 
            if l.__class__ == tuple:
 
468
            if isinstance(l, tuple):
822
469
                c, v = l
823
470
                isactive = None
824
471
                if c == '{':
825
 
                    assert v not in iset
 
472
                    assert v not in istack
826
473
                    istack.append(v)
827
 
                    iset.add(v)
828
474
                elif c == '}':
829
 
                    iset.remove(istack.pop())
 
475
                    istack.pop()
830
476
                elif c == '[':
831
477
                    if v in included:
832
478
                        assert v not in dset
837
483
                        assert v in dset
838
484
                        dset.remove(v)
839
485
            else:
840
 
                assert l.__class__ in (str, unicode)
 
486
                assert isinstance(l, basestring)
841
487
                if isactive is None:
842
488
                    isactive = (not dset) and istack and (istack[-1] in included)
843
489
                if isactive:
844
490
                    result.append((istack[-1], lineno, l))
845
491
            lineno += 1
 
492
 
846
493
        if istack:
847
 
            raise WeaveFormatError("unclosed insertion blocks "
848
 
                    "at end of weave: %s" % istack)
 
494
            raise WFE("unclosed insertion blocks at end of weave",
 
495
                                   istack)
849
496
        if dset:
850
 
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
851
 
                                   % dset)
852
 
        return result
853
 
 
854
 
    @deprecated_method(zero_eight)
855
 
    def get_iter(self, name_or_index):
856
 
        """Deprecated, please do not use. Lookups are not not needed.
857
 
        
858
 
        Please use get_lines now.
859
 
        """
860
 
        return iter(self.get_lines(self._maybe_lookup(name_or_index)))
861
 
 
862
 
    @deprecated_method(zero_eight)
863
 
    def maybe_lookup(self, name_or_index):
864
 
        """Deprecated, please do not use. Lookups are not not needed."""
865
 
        return self._maybe_lookup(name_or_index)
866
 
 
867
 
    def _maybe_lookup(self, name_or_index):
868
 
        """Convert possible symbolic name to index, or pass through indexes.
869
 
        
870
 
        NOT FOR PUBLIC USE.
871
 
        """
872
 
        if isinstance(name_or_index, (int, long)):
873
 
            return name_or_index
874
 
        else:
875
 
            return self._lookup(name_or_index)
876
 
 
877
 
    @deprecated_method(zero_eight)
878
 
    def get(self, version_id):
879
 
        """Please use either Weave.get_text or Weave.get_lines as desired."""
880
 
        return self.get_lines(version_id)
881
 
 
882
 
    def get_lines(self, version_id):
883
 
        """See VersionedFile.get_lines()."""
884
 
        int_index = self._maybe_lookup(version_id)
885
 
        result = [line for (origin, lineno, line) in self._extract([int_index])]
886
 
        expected_sha1 = self._sha1s[int_index]
887
 
        measured_sha1 = sha_strings(result)
888
 
        if measured_sha1 != expected_sha1:
889
 
            raise errors.WeaveInvalidChecksum(
890
 
                    'file %s, revision %s, expected: %s, measured %s' 
891
 
                    % (self._weave_name, version_id,
892
 
                       expected_sha1, measured_sha1))
893
 
        return result
894
 
 
895
 
    def get_sha1(self, version_id):
896
 
        """See VersionedFile.get_sha1()."""
897
 
        return self._sha1s[self._lookup(version_id)]
898
 
 
899
 
    @deprecated_method(zero_eight)
 
497
            raise WFE("unclosed deletion blocks at end of weave",
 
498
                                   dset)
 
499
 
 
500
        return result
 
501
    
 
502
 
 
503
 
 
504
    def get_iter(self, version):
 
505
        """Yield lines for the specified version."""
 
506
        for origin, lineno, line in self._extract([version]):
 
507
            yield line
 
508
 
 
509
 
 
510
    def get(self, index):
 
511
        return list(self.get_iter(index))
 
512
 
 
513
 
 
514
    def mash_iter(self, included):
 
515
        """Return composed version of multiple included versions."""
 
516
        for origin, lineno, text in self._extract(included):
 
517
            yield text
 
518
 
 
519
 
 
520
    def dump(self, to_file):
 
521
        from pprint import pprint
 
522
        print >>to_file, "Weave._weave = ",
 
523
        pprint(self._weave, to_file)
 
524
        print >>to_file, "Weave._parents = ",
 
525
        pprint(self._parents, to_file)
 
526
 
 
527
 
 
528
 
900
529
    def numversions(self):
901
 
        """How many versions are in this weave?
902
 
 
903
 
        Deprecated in favour of num_versions.
904
 
        """
905
 
        return self.num_versions()
906
 
 
907
 
    def num_versions(self):
908
 
        """How many versions are in this weave?"""
909
530
        l = len(self._parents)
910
531
        assert l == len(self._sha1s)
911
532
        return l
912
533
 
913
 
    __len__ = num_versions
 
534
 
 
535
    def __len__(self):
 
536
        return self.numversions()
 
537
 
914
538
 
915
539
    def check(self, progress_bar=None):
916
 
        # TODO evaluate performance hit of using string sets in this routine.
917
 
        # TODO: check no circular inclusions
918
 
        # TODO: create a nested progress bar
919
 
        for version in range(self.num_versions()):
 
540
        # check no circular inclusions
 
541
        for version in range(self.numversions()):
920
542
            inclusions = list(self._parents[version])
921
543
            if inclusions:
922
544
                inclusions.sort()
924
546
                    raise WeaveFormatError("invalid included version %d for index %d"
925
547
                                           % (inclusions[-1], version))
926
548
 
927
 
        # try extracting all versions; parallel extraction is used
928
 
        nv = self.num_versions()
929
 
        sha1s = {}
930
 
        texts = {}
931
 
        inclusions = {}
932
 
        for i in range(nv):
933
 
            # For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
934
 
            # The problem is that set membership is much more expensive
935
 
            name = self._idx_to_name(i)
936
 
            sha1s[name] = sha.new()
937
 
            texts[name] = []
938
 
            new_inc = set([name])
939
 
            for p in self._parents[i]:
940
 
                new_inc.update(inclusions[self._idx_to_name(p)])
941
 
 
942
 
            assert set(new_inc) == set(self.get_ancestry(name)), \
943
 
                'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))
944
 
            inclusions[name] = new_inc
945
 
 
946
 
        nlines = len(self._weave)
947
 
 
948
 
        update_text = 'checking weave'
949
 
        if self._weave_name:
950
 
            short_name = os.path.basename(self._weave_name)
951
 
            update_text = 'checking %s' % (short_name,)
952
 
            update_text = update_text[:25]
953
 
 
954
 
        for lineno, insert, deleteset, line in self._walk_internal():
 
549
        # try extracting all versions; this is a bit slow and parallel
 
550
        # extraction could be used
 
551
        nv = self.numversions()
 
552
        for version in range(nv):
955
553
            if progress_bar:
956
 
                progress_bar.update(update_text, lineno, nlines)
957
 
 
958
 
            for name, name_inclusions in inclusions.items():
959
 
                # The active inclusion must be an ancestor,
960
 
                # and no ancestors must have deleted this line,
961
 
                # because we don't support resurrection.
962
 
                if (insert in name_inclusions) and not (deleteset & name_inclusions):
963
 
                    sha1s[name].update(line)
964
 
 
965
 
        for i in range(nv):
966
 
            version = self._idx_to_name(i)
967
 
            hd = sha1s[version].hexdigest()
968
 
            expected = self._sha1s[i]
 
554
                progress_bar.update('checking text', version, nv)
 
555
            s = sha.new()
 
556
            for l in self.get_iter(version):
 
557
                s.update(l)
 
558
            hd = s.hexdigest()
 
559
            expected = self._sha1s[version]
969
560
            if hd != expected:
970
 
                raise errors.WeaveInvalidChecksum(
971
 
                        "mismatched sha1 for version %s: "
972
 
                        "got %s, expected %s"
973
 
                        % (version, hd, expected))
 
561
                raise WeaveError("mismatched sha1 for version %d; "
 
562
                                 "got %s, expected %s"
 
563
                                 % (version, hd, expected))
974
564
 
975
565
        # TODO: check insertions are properly nested, that there are
976
566
        # no lines outside of insertion blocks, that deletions are
977
567
        # properly paired, etc.
978
568
 
979
 
    def _join(self, other, pb, msg, version_ids, ignore_missing):
980
 
        """Worker routine for join()."""
981
 
        if not other.versions():
982
 
            return          # nothing to update, easy
983
 
 
984
 
        if not version_ids:
985
 
            # versions is never none, InterWeave checks this.
986
 
            return 0
987
 
 
988
 
        # two loops so that we do not change ourselves before verifying it
989
 
        # will be ok
990
 
        # work through in index order to make sure we get all dependencies
991
 
        names_to_join = []
992
 
        processed = 0
993
 
        # get the selected versions only that are in other.versions.
994
 
        version_ids = set(other.versions()).intersection(set(version_ids))
995
 
        # pull in the referenced graph.
996
 
        version_ids = other.get_ancestry(version_ids)
997
 
        pending_graph = [(version, other.get_parents(version)) for
998
 
                         version in version_ids]
999
 
        for name in topo_sort(pending_graph):
1000
 
            other_idx = other._name_map[name]
1001
 
            # returns True if we have it, False if we need it.
1002
 
            if not self._check_version_consistent(other, other_idx, name):
1003
 
                names_to_join.append((other_idx, name))
1004
 
            processed += 1
1005
 
 
1006
 
 
1007
 
        if pb and not msg:
1008
 
            msg = 'weave join'
1009
 
 
1010
 
        merged = 0
1011
 
        time0 = time.time()
1012
 
        for other_idx, name in names_to_join:
1013
 
            # TODO: If all the parents of the other version are already
1014
 
            # present then we can avoid some work by just taking the delta
1015
 
            # and adjusting the offsets.
1016
 
            new_parents = self._imported_parents(other, other_idx)
1017
 
            sha1 = other._sha1s[other_idx]
1018
 
 
1019
 
            merged += 1
1020
 
 
1021
 
            if pb:
1022
 
                pb.update(msg, merged, len(names_to_join))
1023
 
           
1024
 
            lines = other.get_lines(other_idx)
1025
 
            self._add(name, lines, new_parents, sha1)
1026
 
 
1027
 
        mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
1028
 
                merged, processed, self._weave_name, time.time()-time0))
1029
 
 
1030
 
    def _imported_parents(self, other, other_idx):
1031
 
        """Return list of parents in self corresponding to indexes in other."""
1032
 
        new_parents = []
1033
 
        for parent_idx in other._parents[other_idx]:
1034
 
            parent_name = other._names[parent_idx]
1035
 
            if parent_name not in self._name_map:
1036
 
                # should not be possible
1037
 
                raise WeaveError("missing parent {%s} of {%s} in %r" 
1038
 
                                 % (parent_name, other._name_map[other_idx], self))
1039
 
            new_parents.append(self._name_map[parent_name])
1040
 
        return new_parents
1041
 
 
1042
 
    def _check_version_consistent(self, other, other_idx, name):
1043
 
        """Check if a version in consistent in this and other.
1044
 
 
1045
 
        To be consistent it must have:
1046
 
 
1047
 
         * the same text
1048
 
         * the same direct parents (by name, not index, and disregarding
1049
 
           order)
1050
 
        
1051
 
        If present & correct return True;
1052
 
        if not present in self return False; 
1053
 
        if inconsistent raise error."""
1054
 
        this_idx = self._name_map.get(name, -1)
1055
 
        if this_idx != -1:
1056
 
            if self._sha1s[this_idx] != other._sha1s[other_idx]:
1057
 
                raise errors.WeaveTextDiffers(name, self, other)
1058
 
            self_parents = self._parents[this_idx]
1059
 
            other_parents = other._parents[other_idx]
1060
 
            n1 = set([self._names[i] for i in self_parents])
1061
 
            n2 = set([other._names[i] for i in other_parents])
1062
 
            if not self._compatible_parents(n1, n2):
1063
 
                raise WeaveParentMismatch("inconsistent parents "
1064
 
                    "for version {%s}: %s vs %s" % (name, n1, n2))
1065
 
            else:
1066
 
                return True         # ok!
1067
 
        else:
1068
 
            return False
1069
 
 
1070
 
    @deprecated_method(zero_eight)
1071
 
    def reweave(self, other, pb=None, msg=None):
1072
 
        """reweave has been superseded by plain use of join."""
1073
 
        return self.join(other, pb, msg)
1074
 
 
1075
 
    def _reweave(self, other, pb, msg):
1076
 
        """Reweave self with other - internal helper for join().
1077
 
 
1078
 
        :param other: The other weave to merge
1079
 
        :param pb: An optional progress bar, indicating how far done we are
1080
 
        :param msg: An optional message for the progress
1081
 
        """
1082
 
        new_weave = _reweave(self, other, pb=pb, msg=msg)
1083
 
        self._copy_weave_content(new_weave)
1084
 
 
1085
 
    def _copy_weave_content(self, otherweave):
1086
 
        """adsorb the content from otherweave."""
1087
 
        for attr in self.__slots__:
1088
 
            if attr != '_weave_name':
1089
 
                setattr(self, attr, copy(getattr(otherweave, attr)))
1090
 
 
1091
 
 
1092
 
class WeaveFile(Weave):
1093
 
    """A WeaveFile represents a Weave on disk and writes on change."""
1094
 
 
1095
 
    WEAVE_SUFFIX = '.weave'
1096
 
    
1097
 
    def __init__(self, name, transport, filemode=None, create=False, access_mode='w'):
1098
 
        """Create a WeaveFile.
1099
 
        
1100
 
        :param create: If not True, only open an existing knit.
1101
 
        """
1102
 
        super(WeaveFile, self).__init__(name, access_mode)
1103
 
        self._transport = transport
1104
 
        self._filemode = filemode
1105
 
        try:
1106
 
            _read_weave_v5(self._transport.get(name + WeaveFile.WEAVE_SUFFIX), self)
1107
 
        except errors.NoSuchFile:
1108
 
            if not create:
1109
 
                raise
1110
 
            # new file, save it
1111
 
            self._save()
1112
 
 
1113
 
    def _add_lines(self, version_id, parents, lines, parent_texts):
1114
 
        """Add a version and save the weave."""
1115
 
        result = super(WeaveFile, self)._add_lines(version_id, parents, lines,
1116
 
                                                   parent_texts)
1117
 
        self._save()
1118
 
        return result
1119
 
 
1120
 
    def _clone_text(self, new_version_id, old_version_id, parents):
1121
 
        """See VersionedFile.clone_text."""
1122
 
        super(WeaveFile, self)._clone_text(new_version_id, old_version_id, parents)
1123
 
        self._save
1124
 
 
1125
 
    def copy_to(self, name, transport):
1126
 
        """See VersionedFile.copy_to()."""
1127
 
        # as we are all in memory always, just serialise to the new place.
1128
 
        sio = StringIO()
1129
 
        write_weave_v5(self, sio)
1130
 
        sio.seek(0)
1131
 
        transport.put(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
1132
 
 
1133
 
    def create_empty(self, name, transport, filemode=None):
1134
 
        return WeaveFile(name, transport, filemode, create=True)
1135
 
 
1136
 
    def _save(self):
1137
 
        """Save the weave."""
1138
 
        self._check_write_ok()
1139
 
        sio = StringIO()
1140
 
        write_weave_v5(self, sio)
1141
 
        sio.seek(0)
1142
 
        self._transport.put(self._weave_name + WeaveFile.WEAVE_SUFFIX,
1143
 
                            sio,
1144
 
                            self._filemode)
1145
 
 
1146
 
    @staticmethod
1147
 
    def get_suffixes():
1148
 
        """See VersionedFile.get_suffixes()."""
1149
 
        return [WeaveFile.WEAVE_SUFFIX]
1150
 
 
1151
 
    def join(self, other, pb=None, msg=None, version_ids=None,
1152
 
             ignore_missing=False):
1153
 
        """Join other into self and save."""
1154
 
        super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
1155
 
        self._save()
1156
 
 
1157
 
 
1158
 
@deprecated_function(zero_eight)
1159
 
def reweave(wa, wb, pb=None, msg=None):
1160
 
    """reweaving is deprecation, please just use weave.join()."""
1161
 
    _reweave(wa, wb, pb, msg)
1162
 
 
1163
 
def _reweave(wa, wb, pb=None, msg=None):
1164
 
    """Combine two weaves and return the result.
1165
 
 
1166
 
    This works even if a revision R has different parents in 
1167
 
    wa and wb.  In the resulting weave all the parents are given.
1168
 
 
1169
 
    This is done by just building up a new weave, maintaining ordering 
1170
 
    of the versions in the two inputs.  More efficient approaches
1171
 
    might be possible but it should only be necessary to do 
1172
 
    this operation rarely, when a new previously ghost version is 
1173
 
    inserted.
1174
 
 
1175
 
    :param pb: An optional progress bar, indicating how far done we are
1176
 
    :param msg: An optional message for the progress
1177
 
    """
1178
 
    wr = Weave()
1179
 
    ia = ib = 0
1180
 
    queue_a = range(wa.num_versions())
1181
 
    queue_b = range(wb.num_versions())
1182
 
    # first determine combined parents of all versions
1183
 
    # map from version name -> all parent names
1184
 
    combined_parents = _reweave_parent_graphs(wa, wb)
1185
 
    mutter("combined parents: %r", combined_parents)
1186
 
    order = topo_sort(combined_parents.iteritems())
1187
 
    mutter("order to reweave: %r", order)
1188
 
 
1189
 
    if pb and not msg:
1190
 
        msg = 'reweave'
1191
 
 
1192
 
    for idx, name in enumerate(order):
1193
 
        if pb:
1194
 
            pb.update(msg, idx, len(order))
1195
 
        if name in wa._name_map:
1196
 
            lines = wa.get_lines(name)
1197
 
            if name in wb._name_map:
1198
 
                lines_b = wb.get_lines(name)
1199
 
                if lines != lines_b:
1200
 
                    mutter('Weaves differ on content. rev_id {%s}', name)
1201
 
                    mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
1202
 
                    import difflib
1203
 
                    lines = list(difflib.unified_diff(lines, lines_b,
1204
 
                            wa._weave_name, wb._weave_name))
1205
 
                    mutter('lines:\n%s', ''.join(lines))
1206
 
                    raise errors.WeaveTextDiffers(name, wa, wb)
1207
 
        else:
1208
 
            lines = wb.get_lines(name)
1209
 
        wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
1210
 
    return wr
1211
 
 
1212
 
def _reweave_parent_graphs(wa, wb):
1213
 
    """Return combined parent ancestry for two weaves.
1214
 
    
1215
 
    Returned as a list of (version_name, set(parent_names))"""
1216
 
    combined = {}
1217
 
    for weave in [wa, wb]:
1218
 
        for idx, name in enumerate(weave._names):
1219
 
            p = combined.setdefault(name, set())
1220
 
            p.update(map(weave._idx_to_name, weave._parents[idx]))
1221
 
    return combined
 
569
 
 
570
 
 
571
    def merge(self, merge_versions):
 
572
        """Automerge and mark conflicts between versions.
 
573
 
 
574
        This returns a sequence, each entry describing alternatives
 
575
        for a chunk of the file.  Each of the alternatives is given as
 
576
        a list of lines.
 
577
 
 
578
        If there is a chunk of the file where there's no diagreement,
 
579
        only one alternative is given.
 
580
        """
 
581
 
 
582
        # approach: find the included versions common to all the
 
583
        # merged versions
 
584
        raise NotImplementedError()
 
585
 
 
586
 
 
587
 
 
588
    def _delta(self, included, lines):
 
589
        """Return changes from basis to new revision.
 
590
 
 
591
        The old text for comparison is the union of included revisions.
 
592
 
 
593
        This is used in inserting a new text.
 
594
 
 
595
        Delta is returned as a sequence of
 
596
        (weave1, weave2, newlines).
 
597
 
 
598
        This indicates that weave1:weave2 of the old weave should be
 
599
        replaced by the sequence of lines in newlines.  Note that
 
600
        these line numbers are positions in the total weave and don't
 
601
        correspond to the lines in any extracted version, or even the
 
602
        extracted union of included versions.
 
603
 
 
604
        If line1=line2, this is a pure insert; if newlines=[] this is a
 
605
        pure delete.  (Similar to difflib.)
 
606
        """
 
607
 
 
608
 
 
609
            
 
610
    def plan_merge(self, ver_a, ver_b):
 
611
        """Return pseudo-annotation indicating how the two versions merge.
 
612
 
 
613
        This is computed between versions a and b and their common
 
614
        base.
 
615
 
 
616
        Weave lines present in none of them are skipped entirely.
 
617
        """
 
618
        inc_a = self.inclusions([ver_a])
 
619
        inc_b = self.inclusions([ver_b])
 
620
        inc_c = inc_a & inc_b
 
621
 
 
622
        for lineno, insert, deleteset, line in self._walk():
 
623
            if deleteset & inc_c:
 
624
                # killed in parent; can't be in either a or b
 
625
                # not relevant to our work
 
626
                yield 'killed-base', line
 
627
            elif insert in inc_c:
 
628
                # was inserted in base
 
629
                killed_a = bool(deleteset & inc_a)
 
630
                killed_b = bool(deleteset & inc_b)
 
631
                if killed_a and killed_b:
 
632
                    yield 'killed-both', line
 
633
                elif killed_a:
 
634
                    yield 'killed-a', line
 
635
                elif killed_b:
 
636
                    yield 'killed-b', line
 
637
                else:
 
638
                    yield 'unchanged', line
 
639
            elif insert in inc_a:
 
640
                if deleteset & inc_a:
 
641
                    yield 'ghost-a', line
 
642
                else:
 
643
                    # new in A; not in B
 
644
                    yield 'new-a', line
 
645
            elif insert in inc_b:
 
646
                if deleteset & inc_b:
 
647
                    yield 'ghost-b', line
 
648
                else:
 
649
                    yield 'new-b', line
 
650
            else:
 
651
                # not in either revision
 
652
                yield 'irrelevant', line
 
653
 
 
654
        yield 'unchanged', ''           # terminator
 
655
 
 
656
 
 
657
 
 
658
    def weave_merge(self, plan):
 
659
        lines_a = []
 
660
        lines_b = []
 
661
        ch_a = ch_b = False
 
662
 
 
663
        for state, line in plan:
 
664
            if state == 'unchanged' or state == 'killed-both':
 
665
                # resync and flush queued conflicts changes if any
 
666
                if not lines_a and not lines_b:
 
667
                    pass
 
668
                elif ch_a and not ch_b:
 
669
                    # one-sided change:                    
 
670
                    for l in lines_a: yield l
 
671
                elif ch_b and not ch_a:
 
672
                    for l in lines_b: yield l
 
673
                elif lines_a == lines_b:
 
674
                    for l in lines_a: yield l
 
675
                else:
 
676
                    yield '<<<<\n'
 
677
                    for l in lines_a: yield l
 
678
                    yield '====\n'
 
679
                    for l in lines_b: yield l
 
680
                    yield '>>>>\n'
 
681
 
 
682
                del lines_a[:]
 
683
                del lines_b[:]
 
684
                ch_a = ch_b = False
 
685
                
 
686
            if state == 'unchanged':
 
687
                if line:
 
688
                    yield line
 
689
            elif state == 'killed-a':
 
690
                ch_a = True
 
691
                lines_b.append(line)
 
692
            elif state == 'killed-b':
 
693
                ch_b = True
 
694
                lines_a.append(line)
 
695
            elif state == 'new-a':
 
696
                ch_a = True
 
697
                lines_a.append(line)
 
698
            elif state == 'new-b':
 
699
                ch_b = True
 
700
                lines_b.append(line)
 
701
            else:
 
702
                assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
 
703
                                 'killed-both'), \
 
704
                       state
 
705
 
 
706
                
 
707
 
 
708
 
 
709
 
1222
710
 
1223
711
 
1224
712
def weave_toc(w):
1227
715
    for i in (6, 50, 10, 10):
1228
716
        print '-' * i,
1229
717
    print
1230
 
    for i in range(w.num_versions()):
 
718
    for i in range(w.numversions()):
1231
719
        sha1 = w._sha1s[i]
1232
720
        name = w._names[i]
1233
721
        parent_str = ' '.join(map(str, w._parents[i]))
1235
723
 
1236
724
 
1237
725
 
1238
 
def weave_stats(weave_file, pb):
 
726
def weave_stats(weave_file):
 
727
    from bzrlib.progress import ProgressBar
1239
728
    from bzrlib.weavefile import read_weave
1240
729
 
 
730
    pb = ProgressBar()
 
731
 
1241
732
    wf = file(weave_file, 'rb')
1242
 
    w = read_weave(wf, WeaveVersionedFile)
 
733
    w = read_weave(wf)
1243
734
    # FIXME: doesn't work on pipes
1244
735
    weave_size = wf.tell()
1245
736
 
1247
738
    vers = len(w)
1248
739
    for i in range(vers):
1249
740
        pb.update('checking sizes', i, vers)
1250
 
        for origin, lineno, line in w._extract([i]):
 
741
        for line in w.get_iter(i):
1251
742
            total += len(line)
1252
743
 
1253
744
    pb.clear()
1280
771
        Add NEWTEXT, with specified parent versions.
1281
772
    weave annotate WEAVEFILE VERSION
1282
773
        Display origin of each line.
 
774
    weave mash WEAVEFILE VERSION...
 
775
        Display composite of all selected versions.
1283
776
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
1284
777
        Auto-merge two versions and display conflicts.
1285
 
    weave diff WEAVEFILE VERSION1 VERSION2 
1286
 
        Show differences between two versions.
1287
778
 
1288
779
example:
1289
780
 
1314
805
def main(argv):
1315
806
    import sys
1316
807
    import os
1317
 
    try:
1318
 
        import bzrlib
1319
 
    except ImportError:
1320
 
        # in case we're run directly from the subdirectory
1321
 
        sys.path.append('..')
1322
 
        import bzrlib
1323
 
    from bzrlib.weavefile import write_weave, read_weave
 
808
    from weavefile import write_weave, read_weave
1324
809
    from bzrlib.progress import ProgressBar
1325
810
 
1326
811
    try:
1359
844
        w = readit()
1360
845
        sys.stdout.writelines(w.get_iter(int(argv[3])))
1361
846
        
1362
 
    elif cmd == 'diff':
 
847
    elif cmd == 'mash': # get composite
1363
848
        w = readit()
1364
 
        fn = argv[2]
1365
 
        v1, v2 = map(int, argv[3:5])
1366
 
        lines1 = w.get(v1)
1367
 
        lines2 = w.get(v2)
1368
 
        diff_gen = bzrlib.patiencediff.unified_diff(lines1, lines2,
1369
 
                                '%s version %d' % (fn, v1),
1370
 
                                '%s version %d' % (fn, v2))
1371
 
        sys.stdout.writelines(diff_gen)
1372
 
            
 
849
        sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
 
850
 
1373
851
    elif cmd == 'annotate':
1374
852
        w = readit()
1375
853
        # newline is added to all lines regardless; too hard to get
1387
865
        weave_toc(readit())
1388
866
 
1389
867
    elif cmd == 'stats':
1390
 
        weave_stats(argv[2], ProgressBar())
 
868
        weave_stats(argv[2])
1391
869
        
1392
870
    elif cmd == 'check':
1393
871
        w = readit()
1394
872
        pb = ProgressBar()
1395
873
        w.check(pb)
1396
874
        pb.clear()
1397
 
        print '%d versions ok' % w.num_versions()
 
875
        print '%d versions ok' % w.numversions()
1398
876
 
1399
877
    elif cmd == 'inclusions':
1400
878
        w = readit()
1405
883
        print ' '.join(map(str, w._parents[int(argv[3])]))
1406
884
 
1407
885
    elif cmd == 'plan-merge':
1408
 
        # replaced by 'bzr weave-plan-merge'
1409
886
        w = readit()
1410
887
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
1411
888
            if line:
1412
889
                print '%14s | %s' % (state, line),
 
890
 
1413
891
    elif cmd == 'merge':
1414
 
        # replaced by 'bzr weave-merge-text'
1415
892
        w = readit()
1416
893
        p = w.plan_merge(int(argv[3]), int(argv[4]))
1417
894
        sys.stdout.writelines(w.weave_merge(p))
 
895
            
 
896
    elif cmd == 'mash-merge':
 
897
        if len(argv) != 5:
 
898
            usage()
 
899
            return 1
 
900
 
 
901
        w = readit()
 
902
        v1, v2 = map(int, argv[3:5])
 
903
 
 
904
        basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
 
905
 
 
906
        base_lines = list(w.mash_iter(basis))
 
907
        a_lines = list(w.get(v1))
 
908
        b_lines = list(w.get(v2))
 
909
 
 
910
        from bzrlib.merge3 import Merge3
 
911
        m3 = Merge3(base_lines, a_lines, b_lines)
 
912
 
 
913
        name_a = 'version %d' % v1
 
914
        name_b = 'version %d' % v2
 
915
        sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
1418
916
    else:
1419
917
        raise ValueError('unknown command %r' % cmd)
1420
918
    
1421
919
 
1422
920
 
1423
 
def profile_main(argv):
 
921
def profile_main(argv): 
1424
922
    import tempfile, hotshot, hotshot.stats
1425
923
 
1426
924
    prof_f = tempfile.NamedTemporaryFile()
1440
938
    return ret
1441
939
 
1442
940
 
1443
 
def lsprofile_main(argv): 
1444
 
    from bzrlib.lsprof import profile
1445
 
    ret,stats = profile(main, argv)
1446
 
    stats.sort()
1447
 
    stats.pprint()
1448
 
    return ret
1449
 
 
1450
 
 
1451
941
if __name__ == '__main__':
1452
942
    import sys
1453
943
    if '--profile' in sys.argv:
1454
944
        args = sys.argv[:]
1455
945
        args.remove('--profile')
1456
946
        sys.exit(profile_main(args))
1457
 
    elif '--lsprof' in sys.argv:
1458
 
        args = sys.argv[:]
1459
 
        args.remove('--lsprof')
1460
 
        sys.exit(lsprofile_main(args))
1461
947
    else:
1462
948
        sys.exit(main(sys.argv))
1463
949
 
1464
 
 
1465
 
class InterWeave(InterVersionedFile):
1466
 
    """Optimised code paths for weave to weave operations."""
1467
 
    
1468
 
    _matching_file_from_factory = staticmethod(WeaveFile)
1469
 
    _matching_file_to_factory = staticmethod(WeaveFile)
1470
 
    
1471
 
    @staticmethod
1472
 
    def is_compatible(source, target):
1473
 
        """Be compatible with weaves."""
1474
 
        try:
1475
 
            return (isinstance(source, Weave) and
1476
 
                    isinstance(target, Weave))
1477
 
        except AttributeError:
1478
 
            return False
1479
 
 
1480
 
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1481
 
        """See InterVersionedFile.join."""
1482
 
        version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1483
 
        if self.target.versions() == [] and version_ids is None:
1484
 
            self.target._copy_weave_content(self.source)
1485
 
            return
1486
 
        try:
1487
 
            self.target._join(self.source, pb, msg, version_ids, ignore_missing)
1488
 
        except errors.WeaveParentMismatch:
1489
 
            self.target._reweave(self.source, pb, msg)
1490
 
 
1491
 
 
1492
 
InterVersionedFile.register_optimiser(InterWeave)