/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 bzr.dev

Show diffs side-by-side

added added

removed removed

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