~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

Update news and readme

- better explanation of dependencies

Show diffs side-by-side

added added

removed removed

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