~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Aaron Bentley
  • Date: 2008-12-03 05:31:27 UTC
  • mto: This revision was merged to the branch mainline in revision 3893.
  • Revision ID: aaron@aaronbentley.com-20081203053127-vozu5rmsixaadw0v
Change ls-shelf to shelve --list

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?
55
24
 
56
25
# XXX: If we do weaves this way, will a merge still behave the same
57
26
# way if it's done in a different order?  That's a pretty desirable
58
27
# property.
59
28
 
60
29
# TODO: Nothing here so far assumes the lines are really \n newlines,
61
 
# rather than being split up in some other way.  We could accomodate
 
30
# rather than being split up in some other way.  We could accommodate
62
31
# binaries, perhaps by naively splitting on \n or perhaps using
63
32
# something like a rolling checksum.
64
33
 
74
43
 
75
44
# TODO: Parallel-extract that passes back each line along with a
76
45
# description of which revisions include it.  Nice for checking all
77
 
# shas in parallel.
 
46
# shas or calculating stats in parallel.
78
47
 
79
48
# TODO: Using a single _extract routine and then processing the output
80
49
# is probably inefficient.  It's simple enough that we can afford to
81
50
# have slight specializations for different ways its used: annotate,
82
51
# basis for add, get, etc.
83
52
 
84
 
# TODO: Perhaps the API should work only in names to hide the integer
85
 
# indexes from the user?
86
 
 
87
 
 
88
 
 
89
 
import sha
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):
 
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
 
74
import time
 
75
import warnings
 
76
 
 
77
from bzrlib.lazy_import import lazy_import
 
78
lazy_import(globals(), """
 
79
from bzrlib import tsort
 
80
""")
 
81
from bzrlib import (
 
82
    progress,
 
83
    )
 
84
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
 
85
        RevisionAlreadyPresent,
 
86
        RevisionNotPresent,
 
87
        UnavailableRepresentation,
 
88
        WeaveRevisionAlreadyPresent,
 
89
        WeaveRevisionNotPresent,
 
90
        )
 
91
import bzrlib.errors as errors
 
92
from bzrlib.osutils import dirname, sha, sha_strings, split_lines
 
93
import bzrlib.patiencediff
 
94
from bzrlib.revision import NULL_REVISION
 
95
from bzrlib.symbol_versioning import *
 
96
from bzrlib.trace import mutter
 
97
from bzrlib.versionedfile import (
 
98
    AbsentContentFactory,
 
99
    adapter_registry,
 
100
    ContentFactory,
 
101
    VersionedFile,
 
102
    )
 
103
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
 
104
 
 
105
 
 
106
class WeaveContentFactory(ContentFactory):
 
107
    """Content factory for streaming from weaves.
 
108
 
 
109
    :seealso ContentFactory:
 
110
    """
 
111
 
 
112
    def __init__(self, version, weave):
 
113
        """Create a WeaveContentFactory for version from weave."""
 
114
        ContentFactory.__init__(self)
 
115
        self.sha1 = weave.get_sha1s([version])[version]
 
116
        self.key = (version,)
 
117
        parents = weave.get_parent_map([version])[version]
 
118
        self.parents = tuple((parent,) for parent in parents)
 
119
        self.storage_kind = 'fulltext'
 
120
        self._weave = weave
 
121
 
 
122
    def get_bytes_as(self, storage_kind):
 
123
        if storage_kind == 'fulltext':
 
124
            return self._weave.get_text(self.key[-1])
 
125
        else:
 
126
            raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
 
127
 
 
128
 
 
129
class Weave(VersionedFile):
102
130
    """weave - versioned text file storage.
103
131
    
104
132
    A Weave manages versions of line-based text files, keeping track
113
141
 
114
142
    * a nonnegative index number.
115
143
 
116
 
    * a version-id string. (not implemented yet)
 
144
    * a version-id string.
117
145
 
118
146
    Typically the index number will be valid only inside this weave and
119
147
    the version-id is used to reference it in the larger world.
181
209
 
182
210
    _name_map
183
211
        For each name, the version number.
 
212
 
 
213
    _weave_name
 
214
        Descriptive name of this weave; typically the filename if known.
 
215
        Set by read_weave.
184
216
    """
185
217
 
186
 
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map']
187
 
    
188
 
    def __init__(self):
 
218
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
 
219
                 '_weave_name', '_matcher', '_allow_reserved']
 
220
 
 
221
    def __init__(self, weave_name=None, access_mode='w', matcher=None,
 
222
                 get_scope=None, allow_reserved=False):
 
223
        """Create a weave.
 
224
 
 
225
        :param get_scope: A callable that returns an opaque object to be used
 
226
            for detecting when this weave goes out of scope (should stop
 
227
            answering requests or allowing mutation).
 
228
        """
 
229
        super(Weave, self).__init__()
189
230
        self._weave = []
190
231
        self._parents = []
191
232
        self._sha1s = []
192
233
        self._names = []
193
234
        self._name_map = {}
194
 
 
 
235
        self._weave_name = weave_name
 
236
        if matcher is None:
 
237
            self._matcher = bzrlib.patiencediff.PatienceSequenceMatcher
 
238
        else:
 
239
            self._matcher = matcher
 
240
        if get_scope is None:
 
241
            get_scope = lambda:None
 
242
        self._get_scope = get_scope
 
243
        self._scope = get_scope()
 
244
        self._access_mode = access_mode
 
245
        self._allow_reserved = allow_reserved
 
246
 
 
247
    def __repr__(self):
 
248
        return "Weave(%r)" % self._weave_name
 
249
 
 
250
    def _check_write_ok(self):
 
251
        """Is the versioned file marked as 'finished' ? Raise if it is."""
 
252
        if self._get_scope() != self._scope:
 
253
            raise errors.OutSideTransaction()
 
254
        if self._access_mode != 'w':
 
255
            raise errors.ReadOnlyObjectDirtiedError(self)
 
256
 
 
257
    def copy(self):
 
258
        """Return a deep copy of self.
 
259
        
 
260
        The copy can be modified without affecting the original weave."""
 
261
        other = Weave()
 
262
        other._weave = self._weave[:]
 
263
        other._parents = self._parents[:]
 
264
        other._sha1s = self._sha1s[:]
 
265
        other._names = self._names[:]
 
266
        other._name_map = self._name_map.copy()
 
267
        other._weave_name = self._weave_name
 
268
        return other
195
269
 
196
270
    def __eq__(self, other):
197
271
        if not isinstance(other, Weave):
199
273
        return self._parents == other._parents \
200
274
               and self._weave == other._weave \
201
275
               and self._sha1s == other._sha1s 
202
 
 
203
276
    
204
277
    def __ne__(self, other):
205
278
        return not self.__eq__(other)
206
279
 
 
280
    def _idx_to_name(self, version):
 
281
        return self._names[version]
207
282
 
208
 
    def lookup(self, name):
 
283
    def _lookup(self, name):
 
284
        """Convert symbolic version name to index."""
 
285
        if not self._allow_reserved:
 
286
            self.check_not_reserved_id(name)
209
287
        try:
210
288
            return self._name_map[name]
211
289
        except KeyError:
212
 
            raise WeaveError("name %s not present in weave" % name)
213
 
 
214
 
        
215
 
    def add(self, name, parents, text):
 
290
            raise RevisionNotPresent(name, self._weave_name)
 
291
 
 
292
    def versions(self):
 
293
        """See VersionedFile.versions."""
 
294
        return self._names[:]
 
295
 
 
296
    def has_version(self, version_id):
 
297
        """See VersionedFile.has_version."""
 
298
        return (version_id in self._name_map)
 
299
 
 
300
    __contains__ = has_version
 
301
 
 
302
    def get_record_stream(self, versions, ordering, include_delta_closure):
 
303
        """Get a stream of records for versions.
 
304
 
 
305
        :param versions: The versions to include. Each version is a tuple
 
306
            (version,).
 
307
        :param ordering: Either 'unordered' or 'topological'. A topologically
 
308
            sorted stream has compression parents strictly before their
 
309
            children.
 
310
        :param include_delta_closure: If True then the closure across any
 
311
            compression parents will be included (in the opaque data).
 
312
        :return: An iterator of ContentFactory objects, each of which is only
 
313
            valid until the iterator is advanced.
 
314
        """
 
315
        versions = [version[-1] for version in versions]
 
316
        if ordering == 'topological':
 
317
            parents = self.get_parent_map(versions)
 
318
            new_versions = tsort.topo_sort(parents)
 
319
            new_versions.extend(set(versions).difference(set(parents)))
 
320
            versions = new_versions
 
321
        for version in versions:
 
322
            if version in self:
 
323
                yield WeaveContentFactory(version, self)
 
324
            else:
 
325
                yield AbsentContentFactory((version,))
 
326
 
 
327
    def get_parent_map(self, version_ids):
 
328
        """See VersionedFile.get_parent_map."""
 
329
        result = {}
 
330
        for version_id in version_ids:
 
331
            if version_id == NULL_REVISION:
 
332
                parents = ()
 
333
            else:
 
334
                try:
 
335
                    parents = tuple(
 
336
                        map(self._idx_to_name,
 
337
                            self._parents[self._lookup(version_id)]))
 
338
                except RevisionNotPresent:
 
339
                    continue
 
340
            result[version_id] = parents
 
341
        return result
 
342
 
 
343
    def get_parents_with_ghosts(self, version_id):
 
344
        raise NotImplementedError(self.get_parents_with_ghosts)
 
345
 
 
346
    def insert_record_stream(self, stream):
 
347
        """Insert a record stream into this versioned file.
 
348
 
 
349
        :param stream: A stream of records to insert. 
 
350
        :return: None
 
351
        :seealso VersionedFile.get_record_stream:
 
352
        """
 
353
        adapters = {}
 
354
        for record in stream:
 
355
            # Raise an error when a record is missing.
 
356
            if record.storage_kind == 'absent':
 
357
                raise RevisionNotPresent([record.key[0]], self)
 
358
            # adapt to non-tuple interface
 
359
            parents = [parent[0] for parent in record.parents]
 
360
            if record.storage_kind == 'fulltext':
 
361
                self.add_lines(record.key[0], parents,
 
362
                    split_lines(record.get_bytes_as('fulltext')))
 
363
            else:
 
364
                adapter_key = record.storage_kind, 'fulltext'
 
365
                try:
 
366
                    adapter = adapters[adapter_key]
 
367
                except KeyError:
 
368
                    adapter_factory = adapter_registry.get(adapter_key)
 
369
                    adapter = adapter_factory(self)
 
370
                    adapters[adapter_key] = adapter
 
371
                lines = split_lines(adapter.get_bytes(
 
372
                    record, record.get_bytes_as(record.storage_kind)))
 
373
                try:
 
374
                    self.add_lines(record.key[0], parents, lines)
 
375
                except RevisionAlreadyPresent:
 
376
                    pass
 
377
 
 
378
    def _check_repeated_add(self, name, parents, text, sha1):
 
379
        """Check that a duplicated add is OK.
 
380
 
 
381
        If it is, return the (old) index; otherwise raise an exception.
 
382
        """
 
383
        idx = self._lookup(name)
 
384
        if sorted(self._parents[idx]) != sorted(parents) \
 
385
            or sha1 != self._sha1s[idx]:
 
386
            raise RevisionAlreadyPresent(name, self._weave_name)
 
387
        return idx
 
388
 
 
389
    def _add_lines(self, version_id, parents, lines, parent_texts,
 
390
       left_matching_blocks, nostore_sha, random_id, check_content):
 
391
        """See VersionedFile.add_lines."""
 
392
        idx = self._add(version_id, lines, map(self._lookup, parents),
 
393
            nostore_sha=nostore_sha)
 
394
        return sha_strings(lines), sum(map(len, lines)), idx
 
395
 
 
396
    def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
216
397
        """Add a single text on top of the weave.
217
398
  
218
399
        Returns the index number of the newly added version.
219
400
 
220
 
        name
 
401
        version_id
221
402
            Symbolic name for this version.
222
403
            (Typically the revision-id of the revision that added it.)
223
404
 
224
405
        parents
225
406
            List or set of direct parent version numbers.
226
407
            
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
 
        
 
408
        lines
 
409
            Sequence of lines to be added in the new version.
 
410
 
 
411
        :param nostore_sha: See VersionedFile.add_lines.
 
412
        """
 
413
        self._check_lines_not_unicode(lines)
 
414
        self._check_lines_are_lines(lines)
 
415
        if not sha1:
 
416
            sha1 = sha_strings(lines)
 
417
        if sha1 == nostore_sha:
 
418
            raise errors.ExistingContent
 
419
        if version_id in self._name_map:
 
420
            return self._check_repeated_add(version_id, parents, lines, sha1)
 
421
 
234
422
        self._check_versions(parents)
235
 
        ## self._check_lines(text)
 
423
        ## self._check_lines(lines)
236
424
        new_version = len(self._parents)
237
425
 
238
 
        s = sha.new()
239
 
        map(s.update, text)
240
 
        sha1 = s.hexdigest()
241
 
        del s
242
 
 
243
426
        # if we abort after here the (in-memory) weave will be corrupt because only
244
427
        # some fields are updated
 
428
        # XXX: FIXME implement a succeed-or-fail of the rest of this routine.
 
429
        #      - Robert Collins 20060226
245
430
        self._parents.append(parents[:])
246
431
        self._sha1s.append(sha1)
247
 
        self._names.append(name)
248
 
        self._name_map[name] = new_version
 
432
        self._names.append(version_id)
 
433
        self._name_map[version_id] = new_version
249
434
 
250
435
            
251
436
        if not parents:
253
438
            # this more quickly by just appending unconditionally.
254
439
            # even more specially, if we're adding an empty text we
255
440
            # need do nothing at all.
256
 
            if text:
 
441
            if lines:
257
442
                self._weave.append(('{', new_version))
258
 
                self._weave.extend(text)
 
443
                self._weave.extend(lines)
259
444
                self._weave.append(('}', None))
260
 
        
261
445
            return new_version
262
446
 
263
447
        if len(parents) == 1:
267
451
                return new_version
268
452
            
269
453
 
270
 
        ancestors = self.inclusions(parents)
 
454
        ancestors = self._inclusions(parents)
271
455
 
272
456
        l = self._weave
273
457
 
280
464
 
281
465
        # another small special case: a merge, producing the same text
282
466
        # as auto-merge
283
 
        if text == basis_lines:
284
 
            return new_version            
 
467
        if lines == basis_lines:
 
468
            return new_version
285
469
 
286
 
        # add a sentinal, because we can also match against the final line
 
470
        # add a sentinel, because we can also match against the final line
287
471
        basis_lineno.append(len(self._weave))
288
472
 
289
473
        # XXX: which line of the weave should we really consider
293
477
        #print 'basis_lines:', basis_lines
294
478
        #print 'new_lines:  ', lines
295
479
 
296
 
        from difflib import SequenceMatcher
297
 
        s = SequenceMatcher(None, basis_lines, text)
 
480
        s = self._matcher(None, basis_lines, lines)
298
481
 
299
482
        # offset gives the number of lines that have been inserted
300
483
        # into the weave up to the current point; if the original edit instruction
307
490
            #print 'raw match', tag, i1, i2, j1, j2
308
491
            if tag == 'equal':
309
492
                continue
310
 
 
311
493
            i1 = basis_lineno[i1]
312
494
            i2 = basis_lineno[i2]
313
 
 
314
 
            assert 0 <= j1 <= j2 <= len(text)
315
 
 
316
 
            #print tag, i1, i2, j1, j2
317
 
 
318
495
            # the deletion and insertion are handled separately.
319
496
            # first delete the region.
320
497
            if i1 != i2:
328
505
                # we don't destroy ourselves
329
506
                i = i2 + offset
330
507
                self._weave[i:i] = ([('{', new_version)] 
331
 
                                    + text[j1:j2] 
 
508
                                    + lines[j1:j2] 
332
509
                                    + [('}', None)])
333
510
                offset += 2 + (j2 - j1)
334
 
 
335
511
        return new_version
336
512
 
337
 
 
338
 
    def inclusions(self, versions):
 
513
    def _inclusions(self, versions):
339
514
        """Return set of all ancestors of given version(s)."""
 
515
        if not len(versions):
 
516
            return []
340
517
        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:
357
 
            return []
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
 
 
 
518
        for v in xrange(max(versions), 0, -1):
 
519
            if v in i:
 
520
                # include all its parents
 
521
                i.update(self._parents[v])
 
522
        return i
 
523
        ## except IndexError:
 
524
        ##     raise ValueError("version %d not present in weave" % v)
 
525
 
 
526
    def get_ancestry(self, version_ids, topo_sorted=True):
 
527
        """See VersionedFile.get_ancestry."""
 
528
        if isinstance(version_ids, basestring):
 
529
            version_ids = [version_ids]
 
530
        i = self._inclusions([self._lookup(v) for v in version_ids])
 
531
        return [self._idx_to_name(v) for v in i]
375
532
 
376
533
    def _check_lines(self, text):
377
534
        if not isinstance(text, list):
392
549
            except IndexError:
393
550
                raise IndexError("invalid version number %r" % i)
394
551
 
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.
 
552
    def _compatible_parents(self, my_parents, other_parents):
 
553
        """During join check that other_parents are joinable with my_parents.
 
554
 
 
555
        Joinable is defined as 'is a subset of' - supersets may require 
 
556
        regeneration of diffs, but subsets do not.
 
557
        """
 
558
        return len(other_parents.difference(my_parents)) == 0
 
559
 
 
560
    def annotate(self, version_id):
 
561
        """Return a list of (version-id, line) tuples for version_id.
402
562
 
403
563
        The index indicates when the line originated in the weave."""
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
 
        """
 
564
        incls = [self._lookup(version_id)]
 
565
        return [(self._idx_to_name(origin), text) for origin, lineno, text in
 
566
            self._extract(incls)]
 
567
 
 
568
    def iter_lines_added_or_present_in_versions(self, version_ids=None,
 
569
                                                pb=None):
 
570
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
 
571
        if version_ids is None:
 
572
            version_ids = self.versions()
 
573
        version_ids = set(version_ids)
 
574
        for lineno, inserted, deletes, line in self._walk_internal(version_ids):
 
575
            # if inserted not in version_ids then it was inserted before the
 
576
            # versions we care about, but because weaves cannot represent ghosts
 
577
            # properly, we do not filter down to that
 
578
            # if inserted not in version_ids: continue
 
579
            if line[-1] != '\n':
 
580
                yield line + '\n', inserted
 
581
            else:
 
582
                yield line, inserted
 
583
 
 
584
    def _walk_internal(self, version_ids=None):
 
585
        """Helper method for weave actions."""
415
586
        
416
587
        istack = []
417
588
        dset = set()
419
590
        lineno = 0         # line of weave, 0-based
420
591
 
421
592
        for l in self._weave:
422
 
            if isinstance(l, tuple):
 
593
            if l.__class__ == tuple:
423
594
                c, v = l
424
595
                isactive = None
425
596
                if c == '{':
426
 
                    istack.append(v)
 
597
                    istack.append(self._names[v])
427
598
                elif c == '}':
428
599
                    istack.pop()
429
600
                elif c == '[':
430
 
                    assert v not in dset
431
 
                    dset.add(v)
 
601
                    dset.add(self._names[v])
432
602
                elif c == ']':
433
 
                    dset.remove(v)
434
 
                else:
435
 
                    raise WeaveFormatError('unexpected instruction %r'
436
 
                                           % v)
437
 
            else:
438
 
                assert isinstance(l, basestring)
439
 
                assert istack
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))
 
603
                    dset.remove(self._names[v])
 
604
                else:
 
605
                    raise WeaveFormatError('unexpected instruction %r' % v)
 
606
            else:
 
607
                yield lineno, istack[-1], frozenset(dset), l
491
608
            lineno += 1
492
609
 
493
610
        if istack:
494
 
            raise WFE("unclosed insertion blocks at end of weave",
495
 
                                   istack)
 
611
            raise WeaveFormatError("unclosed insertion blocks "
 
612
                    "at end of weave: %s" % istack)
496
613
        if dset:
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
 
            
 
614
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
 
615
                                   % dset)
 
616
 
610
617
    def plan_merge(self, ver_a, ver_b):
611
618
        """Return pseudo-annotation indicating how the two versions merge.
612
619
 
615
622
 
616
623
        Weave lines present in none of them are skipped entirely.
617
624
        """
618
 
        inc_a = self.inclusions([ver_a])
619
 
        inc_b = self.inclusions([ver_b])
 
625
        inc_a = set(self.get_ancestry([ver_a]))
 
626
        inc_b = set(self.get_ancestry([ver_b]))
620
627
        inc_c = inc_a & inc_b
621
628
 
622
 
        for lineno, insert, deleteset, line in self._walk():
 
629
        for lineno, insert, deleteset, line in self._walk_internal([ver_a, ver_b]):
623
630
            if deleteset & inc_c:
624
631
                # killed in parent; can't be in either a or b
625
632
                # not relevant to our work
651
658
                # not in either revision
652
659
                yield 'irrelevant', line
653
660
 
654
 
        yield 'unchanged', ''           # terminator
655
 
 
656
 
 
657
 
 
658
 
    def weave_merge(self, plan):
659
 
        lines_a = []
660
 
        lines_b = []
661
 
        ch_a = ch_b = False
662
 
 
663
 
        for state, line in plan:
664
 
            if state == 'unchanged' or state == 'killed-both':
665
 
                # resync and flush queued conflicts changes if any
666
 
                if not lines_a and not lines_b:
667
 
                    pass
668
 
                elif ch_a and not ch_b:
669
 
                    # one-sided change:                    
670
 
                    for l in lines_a: yield l
671
 
                elif ch_b and not ch_a:
672
 
                    for l in lines_b: yield l
673
 
                elif lines_a == lines_b:
674
 
                    for l in lines_a: yield l
 
661
    def _extract(self, versions):
 
662
        """Yield annotation of lines in included set.
 
663
 
 
664
        Yields a sequence of tuples (origin, lineno, text), where
 
665
        origin is the origin version, lineno the index in the weave,
 
666
        and text the text of the line.
 
667
 
 
668
        The set typically but not necessarily corresponds to a version.
 
669
        """
 
670
        for i in versions:
 
671
            if not isinstance(i, int):
 
672
                raise ValueError(i)
 
673
            
 
674
        included = self._inclusions(versions)
 
675
 
 
676
        istack = []
 
677
        iset = set()
 
678
        dset = set()
 
679
 
 
680
        lineno = 0         # line of weave, 0-based
 
681
 
 
682
        isactive = None
 
683
 
 
684
        result = []
 
685
 
 
686
        WFE = WeaveFormatError
 
687
 
 
688
        # wow. 
 
689
        #  449       0   4474.6820   2356.5590   bzrlib.weave:556(_extract)
 
690
        #  +285282   0   1676.8040   1676.8040   +<isinstance>
 
691
        # 1.6 seconds in 'isinstance'.
 
692
        # changing the first isinstance:
 
693
        #  449       0   2814.2660   1577.1760   bzrlib.weave:556(_extract)
 
694
        #  +140414   0    762.8050    762.8050   +<isinstance>
 
695
        # note that the inline time actually dropped (less function calls)
 
696
        # and total processing time was halved.
 
697
        # we're still spending ~1/4 of the method in isinstance though.
 
698
        # so lets hard code the acceptable string classes we expect:
 
699
        #  449       0   1202.9420    786.2930   bzrlib.weave:556(_extract)
 
700
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list' 
 
701
        #                                          objects>
 
702
        # yay, down to ~1/4 the initial extract time, and our inline time
 
703
        # has shrunk again, with isinstance no longer dominating.
 
704
        # tweaking the stack inclusion test to use a set gives:
 
705
        #  449       0   1122.8030    713.0080   bzrlib.weave:556(_extract)
 
706
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list' 
 
707
        #                                          objects>
 
708
        # - a 5% win, or possibly just noise. However with large istacks that
 
709
        # 'in' test could dominate, so I'm leaving this change in place -
 
710
        # when its fast enough to consider profiling big datasets we can review.
 
711
 
 
712
              
 
713
             
 
714
 
 
715
        for l in self._weave:
 
716
            if l.__class__ == tuple:
 
717
                c, v = l
 
718
                isactive = None
 
719
                if c == '{':
 
720
                    istack.append(v)
 
721
                    iset.add(v)
 
722
                elif c == '}':
 
723
                    iset.remove(istack.pop())
 
724
                elif c == '[':
 
725
                    if v in included:
 
726
                        dset.add(v)
 
727
                elif c == ']':
 
728
                    if v in included:
 
729
                        dset.remove(v)
675
730
                else:
676
 
                    yield '<<<<\n'
677
 
                    for l in lines_a: yield l
678
 
                    yield '====\n'
679
 
                    for l in lines_b: yield l
680
 
                    yield '>>>>\n'
681
 
 
682
 
                del lines_a[:]
683
 
                del lines_b[:]
684
 
                ch_a = ch_b = False
685
 
                
686
 
            if state == 'unchanged':
687
 
                if line:
688
 
                    yield line
689
 
            elif state == 'killed-a':
690
 
                ch_a = True
691
 
                lines_b.append(line)
692
 
            elif state == 'killed-b':
693
 
                ch_b = True
694
 
                lines_a.append(line)
695
 
            elif state == 'new-a':
696
 
                ch_a = True
697
 
                lines_a.append(line)
698
 
            elif state == 'new-b':
699
 
                ch_b = True
700
 
                lines_b.append(line)
701
 
            else:
702
 
                assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
703
 
                                 'killed-both'), \
704
 
                       state
705
 
 
706
 
                
707
 
 
708
 
 
709
 
 
 
731
                    raise AssertionError()
 
732
            else:
 
733
                if isactive is None:
 
734
                    isactive = (not dset) and istack and (istack[-1] in included)
 
735
                if isactive:
 
736
                    result.append((istack[-1], lineno, l))
 
737
            lineno += 1
 
738
        if istack:
 
739
            raise WeaveFormatError("unclosed insertion blocks "
 
740
                    "at end of weave: %s" % istack)
 
741
        if dset:
 
742
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
 
743
                                   % dset)
 
744
        return result
 
745
 
 
746
    def _maybe_lookup(self, name_or_index):
 
747
        """Convert possible symbolic name to index, or pass through indexes.
 
748
        
 
749
        NOT FOR PUBLIC USE.
 
750
        """
 
751
        if isinstance(name_or_index, (int, long)):
 
752
            return name_or_index
 
753
        else:
 
754
            return self._lookup(name_or_index)
 
755
 
 
756
    def get_lines(self, version_id):
 
757
        """See VersionedFile.get_lines()."""
 
758
        int_index = self._maybe_lookup(version_id)
 
759
        result = [line for (origin, lineno, line) in self._extract([int_index])]
 
760
        expected_sha1 = self._sha1s[int_index]
 
761
        measured_sha1 = sha_strings(result)
 
762
        if measured_sha1 != expected_sha1:
 
763
            raise errors.WeaveInvalidChecksum(
 
764
                    'file %s, revision %s, expected: %s, measured %s' 
 
765
                    % (self._weave_name, version_id,
 
766
                       expected_sha1, measured_sha1))
 
767
        return result
 
768
 
 
769
    def get_sha1s(self, version_ids):
 
770
        """See VersionedFile.get_sha1s()."""
 
771
        result = {}
 
772
        for v in version_ids:
 
773
            result[v] = self._sha1s[self._lookup(v)]
 
774
        return result
 
775
 
 
776
    def num_versions(self):
 
777
        """How many versions are in this weave?"""
 
778
        l = len(self._parents)
 
779
        return l
 
780
 
 
781
    __len__ = num_versions
 
782
 
 
783
    def check(self, progress_bar=None):
 
784
        # TODO evaluate performance hit of using string sets in this routine.
 
785
        # TODO: check no circular inclusions
 
786
        # TODO: create a nested progress bar
 
787
        for version in range(self.num_versions()):
 
788
            inclusions = list(self._parents[version])
 
789
            if inclusions:
 
790
                inclusions.sort()
 
791
                if inclusions[-1] >= version:
 
792
                    raise WeaveFormatError("invalid included version %d for index %d"
 
793
                                           % (inclusions[-1], version))
 
794
 
 
795
        # try extracting all versions; parallel extraction is used
 
796
        nv = self.num_versions()
 
797
        sha1s = {}
 
798
        texts = {}
 
799
        inclusions = {}
 
800
        for i in range(nv):
 
801
            # For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
 
802
            # The problem is that set membership is much more expensive
 
803
            name = self._idx_to_name(i)
 
804
            sha1s[name] = sha()
 
805
            texts[name] = []
 
806
            new_inc = set([name])
 
807
            for p in self._parents[i]:
 
808
                new_inc.update(inclusions[self._idx_to_name(p)])
 
809
 
 
810
            if set(new_inc) != set(self.get_ancestry(name)):
 
811
                raise AssertionError(
 
812
                    'failed %s != %s' 
 
813
                    % (set(new_inc), set(self.get_ancestry(name))))
 
814
            inclusions[name] = new_inc
 
815
 
 
816
        nlines = len(self._weave)
 
817
 
 
818
        update_text = 'checking weave'
 
819
        if self._weave_name:
 
820
            short_name = os.path.basename(self._weave_name)
 
821
            update_text = 'checking %s' % (short_name,)
 
822
            update_text = update_text[:25]
 
823
 
 
824
        for lineno, insert, deleteset, line in self._walk_internal():
 
825
            if progress_bar:
 
826
                progress_bar.update(update_text, lineno, nlines)
 
827
 
 
828
            for name, name_inclusions in inclusions.items():
 
829
                # The active inclusion must be an ancestor,
 
830
                # and no ancestors must have deleted this line,
 
831
                # because we don't support resurrection.
 
832
                if (insert in name_inclusions) and not (deleteset & name_inclusions):
 
833
                    sha1s[name].update(line)
 
834
 
 
835
        for i in range(nv):
 
836
            version = self._idx_to_name(i)
 
837
            hd = sha1s[version].hexdigest()
 
838
            expected = self._sha1s[i]
 
839
            if hd != expected:
 
840
                raise errors.WeaveInvalidChecksum(
 
841
                        "mismatched sha1 for version %s: "
 
842
                        "got %s, expected %s"
 
843
                        % (version, hd, expected))
 
844
 
 
845
        # TODO: check insertions are properly nested, that there are
 
846
        # no lines outside of insertion blocks, that deletions are
 
847
        # properly paired, etc.
 
848
 
 
849
    def _imported_parents(self, other, other_idx):
 
850
        """Return list of parents in self corresponding to indexes in other."""
 
851
        new_parents = []
 
852
        for parent_idx in other._parents[other_idx]:
 
853
            parent_name = other._names[parent_idx]
 
854
            if parent_name not in self._name_map:
 
855
                # should not be possible
 
856
                raise WeaveError("missing parent {%s} of {%s} in %r" 
 
857
                                 % (parent_name, other._name_map[other_idx], self))
 
858
            new_parents.append(self._name_map[parent_name])
 
859
        return new_parents
 
860
 
 
861
    def _check_version_consistent(self, other, other_idx, name):
 
862
        """Check if a version in consistent in this and other.
 
863
 
 
864
        To be consistent it must have:
 
865
 
 
866
         * the same text
 
867
         * the same direct parents (by name, not index, and disregarding
 
868
           order)
 
869
        
 
870
        If present & correct return True;
 
871
        if not present in self return False; 
 
872
        if inconsistent raise error."""
 
873
        this_idx = self._name_map.get(name, -1)
 
874
        if this_idx != -1:
 
875
            if self._sha1s[this_idx] != other._sha1s[other_idx]:
 
876
                raise errors.WeaveTextDiffers(name, self, other)
 
877
            self_parents = self._parents[this_idx]
 
878
            other_parents = other._parents[other_idx]
 
879
            n1 = set([self._names[i] for i in self_parents])
 
880
            n2 = set([other._names[i] for i in other_parents])
 
881
            if not self._compatible_parents(n1, n2):
 
882
                raise WeaveParentMismatch("inconsistent parents "
 
883
                    "for version {%s}: %s vs %s" % (name, n1, n2))
 
884
            else:
 
885
                return True         # ok!
 
886
        else:
 
887
            return False
 
888
 
 
889
    def _reweave(self, other, pb, msg):
 
890
        """Reweave self with other - internal helper for join().
 
891
 
 
892
        :param other: The other weave to merge
 
893
        :param pb: An optional progress bar, indicating how far done we are
 
894
        :param msg: An optional message for the progress
 
895
        """
 
896
        new_weave = _reweave(self, other, pb=pb, msg=msg)
 
897
        self._copy_weave_content(new_weave)
 
898
 
 
899
    def _copy_weave_content(self, otherweave):
 
900
        """adsorb the content from otherweave."""
 
901
        for attr in self.__slots__:
 
902
            if attr != '_weave_name':
 
903
                setattr(self, attr, copy(getattr(otherweave, attr)))
 
904
 
 
905
 
 
906
class WeaveFile(Weave):
 
907
    """A WeaveFile represents a Weave on disk and writes on change."""
 
908
 
 
909
    WEAVE_SUFFIX = '.weave'
 
910
    
 
911
    def __init__(self, name, transport, filemode=None, create=False, access_mode='w', get_scope=None):
 
912
        """Create a WeaveFile.
 
913
        
 
914
        :param create: If not True, only open an existing knit.
 
915
        """
 
916
        super(WeaveFile, self).__init__(name, access_mode, get_scope=get_scope,
 
917
            allow_reserved=False)
 
918
        self._transport = transport
 
919
        self._filemode = filemode
 
920
        try:
 
921
            _read_weave_v5(self._transport.get(name + WeaveFile.WEAVE_SUFFIX), self)
 
922
        except errors.NoSuchFile:
 
923
            if not create:
 
924
                raise
 
925
            # new file, save it
 
926
            self._save()
 
927
 
 
928
    def _add_lines(self, version_id, parents, lines, parent_texts,
 
929
        left_matching_blocks, nostore_sha, random_id, check_content):
 
930
        """Add a version and save the weave."""
 
931
        self.check_not_reserved_id(version_id)
 
932
        result = super(WeaveFile, self)._add_lines(version_id, parents, lines,
 
933
            parent_texts, left_matching_blocks, nostore_sha, random_id,
 
934
            check_content)
 
935
        self._save()
 
936
        return result
 
937
 
 
938
    def copy_to(self, name, transport):
 
939
        """See VersionedFile.copy_to()."""
 
940
        # as we are all in memory always, just serialise to the new place.
 
941
        sio = StringIO()
 
942
        write_weave_v5(self, sio)
 
943
        sio.seek(0)
 
944
        transport.put_file(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
 
945
 
 
946
    def _save(self):
 
947
        """Save the weave."""
 
948
        self._check_write_ok()
 
949
        sio = StringIO()
 
950
        write_weave_v5(self, sio)
 
951
        sio.seek(0)
 
952
        bytes = sio.getvalue()
 
953
        path = self._weave_name + WeaveFile.WEAVE_SUFFIX
 
954
        try:
 
955
            self._transport.put_bytes(path, bytes, self._filemode)
 
956
        except errors.NoSuchFile:
 
957
            self._transport.mkdir(dirname(path))
 
958
            self._transport.put_bytes(path, bytes, self._filemode)
 
959
 
 
960
    @staticmethod
 
961
    def get_suffixes():
 
962
        """See VersionedFile.get_suffixes()."""
 
963
        return [WeaveFile.WEAVE_SUFFIX]
 
964
 
 
965
    def insert_record_stream(self, stream):
 
966
        super(WeaveFile, self).insert_record_stream(stream)
 
967
        self._save()
 
968
 
 
969
    @deprecated_method(one_five)
 
970
    def join(self, other, pb=None, msg=None, version_ids=None,
 
971
             ignore_missing=False):
 
972
        """Join other into self and save."""
 
973
        super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
 
974
        self._save()
 
975
 
 
976
 
 
977
def _reweave(wa, wb, pb=None, msg=None):
 
978
    """Combine two weaves and return the result.
 
979
 
 
980
    This works even if a revision R has different parents in 
 
981
    wa and wb.  In the resulting weave all the parents are given.
 
982
 
 
983
    This is done by just building up a new weave, maintaining ordering 
 
984
    of the versions in the two inputs.  More efficient approaches
 
985
    might be possible but it should only be necessary to do 
 
986
    this operation rarely, when a new previously ghost version is 
 
987
    inserted.
 
988
 
 
989
    :param pb: An optional progress bar, indicating how far done we are
 
990
    :param msg: An optional message for the progress
 
991
    """
 
992
    wr = Weave()
 
993
    ia = ib = 0
 
994
    queue_a = range(wa.num_versions())
 
995
    queue_b = range(wb.num_versions())
 
996
    # first determine combined parents of all versions
 
997
    # map from version name -> all parent names
 
998
    combined_parents = _reweave_parent_graphs(wa, wb)
 
999
    mutter("combined parents: %r", combined_parents)
 
1000
    order = tsort.topo_sort(combined_parents.iteritems())
 
1001
    mutter("order to reweave: %r", order)
 
1002
 
 
1003
    if pb and not msg:
 
1004
        msg = 'reweave'
 
1005
 
 
1006
    for idx, name in enumerate(order):
 
1007
        if pb:
 
1008
            pb.update(msg, idx, len(order))
 
1009
        if name in wa._name_map:
 
1010
            lines = wa.get_lines(name)
 
1011
            if name in wb._name_map:
 
1012
                lines_b = wb.get_lines(name)
 
1013
                if lines != lines_b:
 
1014
                    mutter('Weaves differ on content. rev_id {%s}', name)
 
1015
                    mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
 
1016
                    import difflib
 
1017
                    lines = list(difflib.unified_diff(lines, lines_b,
 
1018
                            wa._weave_name, wb._weave_name))
 
1019
                    mutter('lines:\n%s', ''.join(lines))
 
1020
                    raise errors.WeaveTextDiffers(name, wa, wb)
 
1021
        else:
 
1022
            lines = wb.get_lines(name)
 
1023
        wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
 
1024
    return wr
 
1025
 
 
1026
def _reweave_parent_graphs(wa, wb):
 
1027
    """Return combined parent ancestry for two weaves.
 
1028
    
 
1029
    Returned as a list of (version_name, set(parent_names))"""
 
1030
    combined = {}
 
1031
    for weave in [wa, wb]:
 
1032
        for idx, name in enumerate(weave._names):
 
1033
            p = combined.setdefault(name, set())
 
1034
            p.update(map(weave._idx_to_name, weave._parents[idx]))
 
1035
    return combined
710
1036
 
711
1037
 
712
1038
def weave_toc(w):
715
1041
    for i in (6, 50, 10, 10):
716
1042
        print '-' * i,
717
1043
    print
718
 
    for i in range(w.numversions()):
 
1044
    for i in range(w.num_versions()):
719
1045
        sha1 = w._sha1s[i]
720
1046
        name = w._names[i]
721
1047
        parent_str = ' '.join(map(str, w._parents[i]))
723
1049
 
724
1050
 
725
1051
 
726
 
def weave_stats(weave_file):
727
 
    from bzrlib.progress import ProgressBar
 
1052
def weave_stats(weave_file, pb):
728
1053
    from bzrlib.weavefile import read_weave
729
1054
 
730
 
    pb = ProgressBar()
731
 
 
732
1055
    wf = file(weave_file, 'rb')
733
1056
    w = read_weave(wf)
734
1057
    # FIXME: doesn't work on pipes
738
1061
    vers = len(w)
739
1062
    for i in range(vers):
740
1063
        pb.update('checking sizes', i, vers)
741
 
        for line in w.get_iter(i):
 
1064
        for origin, lineno, line in w._extract([i]):
742
1065
            total += len(line)
743
1066
 
744
1067
    pb.clear()
771
1094
        Add NEWTEXT, with specified parent versions.
772
1095
    weave annotate WEAVEFILE VERSION
773
1096
        Display origin of each line.
774
 
    weave mash WEAVEFILE VERSION...
775
 
        Display composite of all selected versions.
776
1097
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
777
1098
        Auto-merge two versions and display conflicts.
 
1099
    weave diff WEAVEFILE VERSION1 VERSION2 
 
1100
        Show differences between two versions.
778
1101
 
779
1102
example:
780
1103
 
805
1128
def main(argv):
806
1129
    import sys
807
1130
    import os
808
 
    from weavefile import write_weave, read_weave
 
1131
    try:
 
1132
        import bzrlib
 
1133
    except ImportError:
 
1134
        # in case we're run directly from the subdirectory
 
1135
        sys.path.append('..')
 
1136
        import bzrlib
 
1137
    from bzrlib.weavefile import write_weave, read_weave
809
1138
    from bzrlib.progress import ProgressBar
810
1139
 
811
1140
    try:
844
1173
        w = readit()
845
1174
        sys.stdout.writelines(w.get_iter(int(argv[3])))
846
1175
        
847
 
    elif cmd == 'mash': # get composite
 
1176
    elif cmd == 'diff':
848
1177
        w = readit()
849
 
        sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
850
 
 
 
1178
        fn = argv[2]
 
1179
        v1, v2 = map(int, argv[3:5])
 
1180
        lines1 = w.get(v1)
 
1181
        lines2 = w.get(v2)
 
1182
        diff_gen = bzrlib.patiencediff.unified_diff(lines1, lines2,
 
1183
                                '%s version %d' % (fn, v1),
 
1184
                                '%s version %d' % (fn, v2))
 
1185
        sys.stdout.writelines(diff_gen)
 
1186
            
851
1187
    elif cmd == 'annotate':
852
1188
        w = readit()
853
1189
        # newline is added to all lines regardless; too hard to get
865
1201
        weave_toc(readit())
866
1202
 
867
1203
    elif cmd == 'stats':
868
 
        weave_stats(argv[2])
 
1204
        weave_stats(argv[2], ProgressBar())
869
1205
        
870
1206
    elif cmd == 'check':
871
1207
        w = readit()
872
1208
        pb = ProgressBar()
873
1209
        w.check(pb)
874
1210
        pb.clear()
875
 
        print '%d versions ok' % w.numversions()
 
1211
        print '%d versions ok' % w.num_versions()
876
1212
 
877
1213
    elif cmd == 'inclusions':
878
1214
        w = readit()
883
1219
        print ' '.join(map(str, w._parents[int(argv[3])]))
884
1220
 
885
1221
    elif cmd == 'plan-merge':
 
1222
        # replaced by 'bzr weave-plan-merge'
886
1223
        w = readit()
887
1224
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
888
1225
            if line:
889
1226
                print '%14s | %s' % (state, line),
890
 
 
891
1227
    elif cmd == 'merge':
 
1228
        # replaced by 'bzr weave-merge-text'
892
1229
        w = readit()
893
1230
        p = w.plan_merge(int(argv[3]), int(argv[4]))
894
1231
        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))
916
1232
    else:
917
1233
        raise ValueError('unknown command %r' % cmd)
918
1234
    
919
1235
 
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
 
 
941
1236
if __name__ == '__main__':
942
1237
    import sys
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
 
 
 
1238
    sys.exit(main(sys.argv))