~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

Nathaniel McCallums patch for urandom friendliness on aix.

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