~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

- rules for using destructors

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2009 Canonical Ltd
2
 
#
 
1
#! /usr/bin/python
 
2
 
 
3
# Copyright (C) 2005 Canonical Ltd
 
4
 
3
5
# This program is free software; you can redistribute it and/or modify
4
6
# it under the terms of the GNU General Public License as published by
5
7
# the Free Software Foundation; either version 2 of the License, or
6
8
# (at your option) any later version.
7
 
#
 
9
 
8
10
# This program is distributed in the hope that it will be useful,
9
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
13
# GNU General Public License for more details.
12
 
#
 
14
 
13
15
# You should have received a copy of the GNU General Public License
14
16
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
18
 
17
19
# Author: Martin Pool <mbp@canonical.com>
18
20
 
25
27
# property.
26
28
 
27
29
# TODO: Nothing here so far assumes the lines are really \n newlines,
28
 
# rather than being split up in some other way.  We could accommodate
 
30
# rather than being split up in some other way.  We could accomodate
29
31
# binaries, perhaps by naively splitting on \n or perhaps using
30
32
# something like a rolling checksum.
31
33
 
59
61
# where the basis and destination are unchanged.
60
62
 
61
63
# FIXME: Sometimes we will be given a parents list for a revision
62
 
# that includes some redundant parents (i.e. already a parent of
63
 
# something in the list.)  We should eliminate them.  This can
 
64
# that includes some redundant parents (i.e. already a parent of 
 
65
# something in the list.)  We should eliminate them.  This can 
64
66
# be done fairly efficiently because the sequence numbers constrain
65
67
# the possible relationships.
66
68
 
67
 
# FIXME: the conflict markers should be *7* characters
68
 
 
69
 
from copy import copy
70
 
from cStringIO import StringIO
71
 
import os
72
 
import time
73
 
import warnings
74
 
 
75
 
from bzrlib.lazy_import import lazy_import
76
 
lazy_import(globals(), """
77
 
from bzrlib import tsort
78
 
""")
79
 
from bzrlib import (
80
 
    errors,
81
 
    osutils,
82
 
    progress,
83
 
    )
84
 
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
85
 
        RevisionAlreadyPresent,
86
 
        RevisionNotPresent,
87
 
        UnavailableRepresentation,
88
 
        WeaveRevisionAlreadyPresent,
89
 
        WeaveRevisionNotPresent,
90
 
        )
91
 
from bzrlib.osutils import dirname, sha, sha_strings, split_lines
92
 
import bzrlib.patiencediff
93
 
from bzrlib.revision import NULL_REVISION
94
 
from bzrlib.symbol_versioning import *
 
69
 
 
70
import sha
 
71
from difflib import SequenceMatcher
 
72
 
95
73
from bzrlib.trace import mutter
96
 
from bzrlib.versionedfile import (
97
 
    AbsentContentFactory,
98
 
    adapter_registry,
99
 
    ContentFactory,
100
 
    sort_groupcompress,
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
 
        elif storage_kind == 'chunked':
126
 
            return self._weave.get_lines(self.key[-1])
127
 
        else:
128
 
            raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
129
 
 
130
 
 
131
 
class Weave(VersionedFile):
 
74
 
 
75
 
 
76
class WeaveError(Exception):
 
77
    """Exception in processing weave"""
 
78
 
 
79
 
 
80
class WeaveFormatError(WeaveError):
 
81
    """Weave invariant violated"""
 
82
 
 
83
 
 
84
class WeaveParentMismatch(WeaveError):
 
85
    """Parents are mismatched between two revisions."""
 
86
    
 
87
 
 
88
class Weave(object):
132
89
    """weave - versioned text file storage.
133
 
 
 
90
    
134
91
    A Weave manages versions of line-based text files, keeping track
135
92
    of the originating version for each line.
136
93
 
182
139
 
183
140
    * It doesn't seem very useful to have an active insertion
184
141
      inside an inactive insertion, but it might happen.
185
 
 
 
142
      
186
143
    * Therefore, all instructions are always"considered"; that
187
144
      is passed onto and off the stack.  An outer inactive block
188
145
      doesn't disable an inner block.
218
175
    """
219
176
 
220
177
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
221
 
                 '_weave_name', '_matcher', '_allow_reserved']
222
 
 
223
 
    def __init__(self, weave_name=None, access_mode='w', matcher=None,
224
 
                 get_scope=None, allow_reserved=False):
225
 
        """Create a weave.
226
 
 
227
 
        :param get_scope: A callable that returns an opaque object to be used
228
 
            for detecting when this weave goes out of scope (should stop
229
 
            answering requests or allowing mutation).
230
 
        """
231
 
        super(Weave, self).__init__()
 
178
                 '_weave_name']
 
179
    
 
180
    def __init__(self, weave_name=None):
232
181
        self._weave = []
233
182
        self._parents = []
234
183
        self._sha1s = []
235
184
        self._names = []
236
185
        self._name_map = {}
237
186
        self._weave_name = weave_name
238
 
        if matcher is None:
239
 
            self._matcher = bzrlib.patiencediff.PatienceSequenceMatcher
240
 
        else:
241
 
            self._matcher = matcher
242
 
        if get_scope is None:
243
 
            get_scope = lambda:None
244
 
        self._get_scope = get_scope
245
 
        self._scope = get_scope()
246
 
        self._access_mode = access_mode
247
 
        self._allow_reserved = allow_reserved
248
 
 
249
 
    def __repr__(self):
250
 
        return "Weave(%r)" % self._weave_name
251
 
 
252
 
    def _check_write_ok(self):
253
 
        """Is the versioned file marked as 'finished' ? Raise if it is."""
254
 
        if self._get_scope() != self._scope:
255
 
            raise errors.OutSideTransaction()
256
 
        if self._access_mode != 'w':
257
 
            raise errors.ReadOnlyObjectDirtiedError(self)
 
187
 
258
188
 
259
189
    def copy(self):
260
190
        """Return a deep copy of self.
261
 
 
 
191
        
262
192
        The copy can be modified without affecting the original weave."""
263
193
        other = Weave()
264
194
        other._weave = self._weave[:]
274
204
            return False
275
205
        return self._parents == other._parents \
276
206
               and self._weave == other._weave \
277
 
               and self._sha1s == other._sha1s
 
207
               and self._sha1s == other._sha1s 
278
208
 
 
209
    
279
210
    def __ne__(self, other):
280
211
        return not self.__eq__(other)
281
212
 
282
 
    def _idx_to_name(self, version):
283
 
        return self._names[version]
284
 
 
285
 
    def _lookup(self, name):
 
213
 
 
214
    def maybe_lookup(self, name_or_index):
 
215
        """Convert possible symbolic name to index, or pass through indexes."""
 
216
        if isinstance(name_or_index, (int, long)):
 
217
            return name_or_index
 
218
        else:
 
219
            return self.lookup(name_or_index)
 
220
 
 
221
        
 
222
    def lookup(self, name):
286
223
        """Convert symbolic version name to index."""
287
 
        if not self._allow_reserved:
288
 
            self.check_not_reserved_id(name)
289
224
        try:
290
225
            return self._name_map[name]
291
226
        except KeyError:
292
 
            raise RevisionNotPresent(name, self._weave_name)
293
 
 
294
 
    def versions(self):
295
 
        """See VersionedFile.versions."""
296
 
        return self._names[:]
297
 
 
298
 
    def has_version(self, version_id):
299
 
        """See VersionedFile.has_version."""
300
 
        return (version_id in self._name_map)
301
 
 
302
 
    __contains__ = has_version
303
 
 
304
 
    def get_record_stream(self, versions, ordering, include_delta_closure):
305
 
        """Get a stream of records for versions.
306
 
 
307
 
        :param versions: The versions to include. Each version is a tuple
308
 
            (version,).
309
 
        :param ordering: Either 'unordered' or 'topological'. A topologically
310
 
            sorted stream has compression parents strictly before their
311
 
            children.
312
 
        :param include_delta_closure: If True then the closure across any
313
 
            compression parents will be included (in the opaque data).
314
 
        :return: An iterator of ContentFactory objects, each of which is only
315
 
            valid until the iterator is advanced.
316
 
        """
317
 
        versions = [version[-1] for version in versions]
318
 
        if ordering == 'topological':
319
 
            parents = self.get_parent_map(versions)
320
 
            new_versions = tsort.topo_sort(parents)
321
 
            new_versions.extend(set(versions).difference(set(parents)))
322
 
            versions = new_versions
323
 
        elif ordering == 'groupcompress':
324
 
            parents = self.get_parent_map(versions)
325
 
            new_versions = sort_groupcompress(parents)
326
 
            new_versions.extend(set(versions).difference(set(parents)))
327
 
            versions = new_versions
328
 
        for version in versions:
329
 
            if version in self:
330
 
                yield WeaveContentFactory(version, self)
331
 
            else:
332
 
                yield AbsentContentFactory((version,))
333
 
 
334
 
    def get_parent_map(self, version_ids):
335
 
        """See VersionedFile.get_parent_map."""
336
 
        result = {}
337
 
        for version_id in version_ids:
338
 
            if version_id == NULL_REVISION:
339
 
                parents = ()
340
 
            else:
341
 
                try:
342
 
                    parents = tuple(
343
 
                        map(self._idx_to_name,
344
 
                            self._parents[self._lookup(version_id)]))
345
 
                except RevisionNotPresent:
346
 
                    continue
347
 
            result[version_id] = parents
348
 
        return result
349
 
 
350
 
    def get_parents_with_ghosts(self, version_id):
351
 
        raise NotImplementedError(self.get_parents_with_ghosts)
352
 
 
353
 
    def insert_record_stream(self, stream):
354
 
        """Insert a record stream into this versioned file.
355
 
 
356
 
        :param stream: A stream of records to insert.
357
 
        :return: None
358
 
        :seealso VersionedFile.get_record_stream:
359
 
        """
360
 
        adapters = {}
361
 
        for record in stream:
362
 
            # Raise an error when a record is missing.
363
 
            if record.storage_kind == 'absent':
364
 
                raise RevisionNotPresent([record.key[0]], self)
365
 
            # adapt to non-tuple interface
366
 
            parents = [parent[0] for parent in record.parents]
367
 
            if (record.storage_kind == 'fulltext'
368
 
                or record.storage_kind == 'chunked'):
369
 
                self.add_lines(record.key[0], parents,
370
 
                    osutils.chunks_to_lines(record.get_bytes_as('chunked')))
371
 
            else:
372
 
                adapter_key = record.storage_kind, 'fulltext'
373
 
                try:
374
 
                    adapter = adapters[adapter_key]
375
 
                except KeyError:
376
 
                    adapter_factory = adapter_registry.get(adapter_key)
377
 
                    adapter = adapter_factory(self)
378
 
                    adapters[adapter_key] = adapter
379
 
                lines = split_lines(adapter.get_bytes(record))
380
 
                try:
381
 
                    self.add_lines(record.key[0], parents, lines)
382
 
                except RevisionAlreadyPresent:
383
 
                    pass
 
227
            raise WeaveError("name %r not present in weave %r" %
 
228
                             (name, self._weave_name))
 
229
 
 
230
 
 
231
    def iter_names(self):
 
232
        """Yield a list of all names in this weave."""
 
233
        return iter(self._names)
 
234
 
 
235
    def idx_to_name(self, version):
 
236
        return self._names[version]
 
237
 
384
238
 
385
239
    def _check_repeated_add(self, name, parents, text, sha1):
386
240
        """Check that a duplicated add is OK.
387
241
 
388
242
        If it is, return the (old) index; otherwise raise an exception.
389
243
        """
390
 
        idx = self._lookup(name)
391
 
        if sorted(self._parents[idx]) != sorted(parents) \
392
 
            or sha1 != self._sha1s[idx]:
393
 
            raise RevisionAlreadyPresent(name, self._weave_name)
 
244
        idx = self.lookup(name)
 
245
        if sorted(self._parents[idx]) != sorted(parents):
 
246
            raise WeaveError("name \"%s\" already present in weave "
 
247
                             "with different parents" % name)
 
248
        if sha1 != self._sha1s[idx]:
 
249
            raise WeaveError("name \"%s\" already present in weave "
 
250
                             "with different text" % name)            
394
251
        return idx
395
 
 
396
 
    def _add_lines(self, version_id, parents, lines, parent_texts,
397
 
       left_matching_blocks, nostore_sha, random_id, check_content):
398
 
        """See VersionedFile.add_lines."""
399
 
        idx = self._add(version_id, lines, map(self._lookup, parents),
400
 
            nostore_sha=nostore_sha)
401
 
        return sha_strings(lines), sum(map(len, lines)), idx
402
 
 
403
 
    def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
 
252
        
 
253
 
 
254
        
 
255
    def add(self, name, parents, text, sha1=None):
404
256
        """Add a single text on top of the weave.
405
 
 
 
257
  
406
258
        Returns the index number of the newly added version.
407
259
 
408
 
        version_id
 
260
        name
409
261
            Symbolic name for this version.
410
262
            (Typically the revision-id of the revision that added it.)
411
 
            If None, a name will be allocated based on the hash. (sha1:SHAHASH)
412
263
 
413
264
        parents
414
265
            List or set of direct parent version numbers.
415
 
 
416
 
        lines
 
266
            
 
267
        text
417
268
            Sequence of lines to be added in the new version.
418
269
 
419
 
        :param nostore_sha: See VersionedFile.add_lines.
 
270
        sha -- SHA-1 of the file, if known.  This is trusted to be
 
271
            correct if supplied.
420
272
        """
421
 
        self._check_lines_not_unicode(lines)
422
 
        self._check_lines_are_lines(lines)
423
 
        if not sha1:
424
 
            sha1 = sha_strings(lines)
425
 
        if sha1 == nostore_sha:
426
 
            raise errors.ExistingContent
427
 
        if version_id is None:
428
 
            version_id = "sha1:" + sha1
429
 
        if version_id in self._name_map:
430
 
            return self._check_repeated_add(version_id, parents, lines, sha1)
431
 
 
 
273
        from bzrlib.osutils import sha_strings
 
274
 
 
275
        assert isinstance(name, basestring)
 
276
        if sha1 is None:
 
277
            sha1 = sha_strings(text)
 
278
        if name in self._name_map:
 
279
            return self._check_repeated_add(name, parents, text, sha1)
 
280
 
 
281
        parents = map(self.maybe_lookup, parents)
432
282
        self._check_versions(parents)
433
 
        ## self._check_lines(lines)
 
283
        ## self._check_lines(text)
434
284
        new_version = len(self._parents)
435
285
 
 
286
 
436
287
        # if we abort after here the (in-memory) weave will be corrupt because only
437
288
        # some fields are updated
438
 
        # XXX: FIXME implement a succeed-or-fail of the rest of this routine.
439
 
        #      - Robert Collins 20060226
440
289
        self._parents.append(parents[:])
441
290
        self._sha1s.append(sha1)
442
 
        self._names.append(version_id)
443
 
        self._name_map[version_id] = new_version
444
 
 
445
 
 
 
291
        self._names.append(name)
 
292
        self._name_map[name] = new_version
 
293
 
 
294
            
446
295
        if not parents:
447
296
            # special case; adding with no parents revision; can do
448
297
            # this more quickly by just appending unconditionally.
449
298
            # even more specially, if we're adding an empty text we
450
299
            # need do nothing at all.
451
 
            if lines:
 
300
            if text:
452
301
                self._weave.append(('{', new_version))
453
 
                self._weave.extend(lines)
 
302
                self._weave.extend(text)
454
303
                self._weave.append(('}', None))
 
304
        
455
305
            return new_version
456
306
 
457
307
        if len(parents) == 1:
459
309
            if sha1 == self._sha1s[pv]:
460
310
                # special case: same as the single parent
461
311
                return new_version
462
 
 
463
 
 
464
 
        ancestors = self._inclusions(parents)
 
312
            
 
313
 
 
314
        ancestors = self.inclusions(parents)
465
315
 
466
316
        l = self._weave
467
317
 
474
324
 
475
325
        # another small special case: a merge, producing the same text
476
326
        # as auto-merge
477
 
        if lines == basis_lines:
478
 
            return new_version
 
327
        if text == basis_lines:
 
328
            return new_version            
479
329
 
480
 
        # add a sentinel, because we can also match against the final line
 
330
        # add a sentinal, because we can also match against the final line
481
331
        basis_lineno.append(len(self._weave))
482
332
 
483
333
        # XXX: which line of the weave should we really consider
487
337
        #print 'basis_lines:', basis_lines
488
338
        #print 'new_lines:  ', lines
489
339
 
490
 
        s = self._matcher(None, basis_lines, lines)
 
340
        s = SequenceMatcher(None, basis_lines, text)
491
341
 
492
342
        # offset gives the number of lines that have been inserted
493
343
        # into the weave up to the current point; if the original edit instruction
500
350
            #print 'raw match', tag, i1, i2, j1, j2
501
351
            if tag == 'equal':
502
352
                continue
 
353
 
503
354
            i1 = basis_lineno[i1]
504
355
            i2 = basis_lineno[i2]
 
356
 
 
357
            assert 0 <= j1 <= j2 <= len(text)
 
358
 
 
359
            #print tag, i1, i2, j1, j2
 
360
 
505
361
            # the deletion and insertion are handled separately.
506
362
            # first delete the region.
507
363
            if i1 != i2:
514
370
                # i2; we want to insert after this region to make sure
515
371
                # we don't destroy ourselves
516
372
                i = i2 + offset
517
 
                self._weave[i:i] = ([('{', new_version)]
518
 
                                    + lines[j1:j2]
 
373
                self._weave[i:i] = ([('{', new_version)] 
 
374
                                    + text[j1:j2] 
519
375
                                    + [('}', None)])
520
376
                offset += 2 + (j2 - j1)
 
377
 
521
378
        return new_version
522
379
 
523
 
    def _inclusions(self, versions):
 
380
    def add_identical(self, old_rev_id, new_rev_id, parents):
 
381
        """Add an identical text to old_rev_id as new_rev_id."""
 
382
        old_lines = self.get(self.lookup(old_rev_id))
 
383
        self.add(new_rev_id, parents, old_lines)
 
384
 
 
385
    def inclusions(self, versions):
524
386
        """Return set of all ancestors of given version(s)."""
525
 
        if not len(versions):
526
 
            return []
527
387
        i = set(versions)
528
388
        for v in xrange(max(versions), 0, -1):
529
389
            if v in i:
533
393
        ## except IndexError:
534
394
        ##     raise ValueError("version %d not present in weave" % v)
535
395
 
536
 
    def get_ancestry(self, version_ids, topo_sorted=True):
537
 
        """See VersionedFile.get_ancestry."""
538
 
        if isinstance(version_ids, basestring):
539
 
            version_ids = [version_ids]
540
 
        i = self._inclusions([self._lookup(v) for v in version_ids])
541
 
        return [self._idx_to_name(v) for v in i]
 
396
 
 
397
    def parents(self, version):
 
398
        return self._parents[version]
 
399
 
 
400
 
 
401
    def parent_names(self, version):
 
402
        """Return version names for parents of a version."""
 
403
        return map(self.idx_to_name, self._parents[self.lookup(version)])
 
404
 
 
405
 
 
406
    def minimal_parents(self, version):
 
407
        """Find the minimal set of parents for the version."""
 
408
        included = self._parents[version]
 
409
        if not included:
 
410
            return []
 
411
        
 
412
        li = list(included)
 
413
        li.sort(reverse=True)
 
414
 
 
415
        mininc = []
 
416
        gotit = set()
 
417
 
 
418
        for pv in li:
 
419
            if pv not in gotit:
 
420
                mininc.append(pv)
 
421
                gotit.update(self.inclusions(pv))
 
422
 
 
423
        assert mininc[0] >= 0
 
424
        assert mininc[-1] < version
 
425
        return mininc
 
426
 
 
427
 
542
428
 
543
429
    def _check_lines(self, text):
544
430
        if not isinstance(text, list):
548
434
            if not isinstance(l, basestring):
549
435
                raise ValueError("text line should be a string or unicode, not %s"
550
436
                                 % type(l))
551
 
 
 
437
        
552
438
 
553
439
 
554
440
    def _check_versions(self, indexes):
559
445
            except IndexError:
560
446
                raise IndexError("invalid version number %r" % i)
561
447
 
562
 
    def _compatible_parents(self, my_parents, other_parents):
563
 
        """During join check that other_parents are joinable with my_parents.
564
 
 
565
 
        Joinable is defined as 'is a subset of' - supersets may require
566
 
        regeneration of diffs, but subsets do not.
567
 
        """
568
 
        return len(other_parents.difference(my_parents)) == 0
569
 
 
570
 
    def annotate(self, version_id):
571
 
        """Return a list of (version-id, line) tuples for version_id.
 
448
    
 
449
    def annotate(self, name_or_index):
 
450
        return list(self.annotate_iter(name_or_index))
 
451
 
 
452
 
 
453
    def annotate_iter(self, name_or_index):
 
454
        """Yield list of (index-id, line) pairs for the specified version.
572
455
 
573
456
        The index indicates when the line originated in the weave."""
574
 
        incls = [self._lookup(version_id)]
575
 
        return [(self._idx_to_name(origin), text) for origin, lineno, text in
576
 
            self._extract(incls)]
577
 
 
578
 
    def iter_lines_added_or_present_in_versions(self, version_ids=None,
579
 
                                                pb=None):
580
 
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
581
 
        if version_ids is None:
582
 
            version_ids = self.versions()
583
 
        version_ids = set(version_ids)
584
 
        for lineno, inserted, deletes, line in self._walk_internal(version_ids):
585
 
            if inserted not in version_ids: continue
586
 
            if line[-1] != '\n':
587
 
                yield line + '\n', inserted
588
 
            else:
589
 
                yield line, inserted
590
 
 
591
 
    def _walk_internal(self, version_ids=None):
592
 
        """Helper method for weave actions."""
593
 
 
 
457
        incls = [self.maybe_lookup(name_or_index)]
 
458
        for origin, lineno, text in self._extract(incls):
 
459
            yield origin, text
 
460
 
 
461
 
 
462
    def _walk(self):
 
463
        """Walk the weave.
 
464
 
 
465
        Yields sequence of
 
466
        (lineno, insert, deletes, text)
 
467
        for each literal line.
 
468
        """
 
469
        
594
470
        istack = []
595
471
        dset = set()
596
472
 
597
473
        lineno = 0         # line of weave, 0-based
598
474
 
599
475
        for l in self._weave:
600
 
            if l.__class__ == tuple:
 
476
            if isinstance(l, tuple):
601
477
                c, v = l
602
478
                isactive = None
603
479
                if c == '{':
604
 
                    istack.append(self._names[v])
 
480
                    istack.append(v)
605
481
                elif c == '}':
606
482
                    istack.pop()
607
483
                elif c == '[':
608
 
                    dset.add(self._names[v])
 
484
                    assert v not in dset
 
485
                    dset.add(v)
609
486
                elif c == ']':
610
 
                    dset.remove(self._names[v])
611
 
                else:
612
 
                    raise WeaveFormatError('unexpected instruction %r' % v)
613
 
            else:
614
 
                yield lineno, istack[-1], frozenset(dset), l
 
487
                    dset.remove(v)
 
488
                else:
 
489
                    raise WeaveFormatError('unexpected instruction %r'
 
490
                                           % v)
 
491
            else:
 
492
                assert isinstance(l, basestring)
 
493
                assert istack
 
494
                yield lineno, istack[-1], dset, l
 
495
            lineno += 1
 
496
 
 
497
 
 
498
 
 
499
    def _extract(self, versions):
 
500
        """Yield annotation of lines in included set.
 
501
 
 
502
        Yields a sequence of tuples (origin, lineno, text), where
 
503
        origin is the origin version, lineno the index in the weave,
 
504
        and text the text of the line.
 
505
 
 
506
        The set typically but not necessarily corresponds to a version.
 
507
        """
 
508
        for i in versions:
 
509
            if not isinstance(i, int):
 
510
                raise ValueError(i)
 
511
            
 
512
        included = self.inclusions(versions)
 
513
 
 
514
        istack = []
 
515
        dset = set()
 
516
 
 
517
        lineno = 0         # line of weave, 0-based
 
518
 
 
519
        isactive = None
 
520
 
 
521
        result = []
 
522
 
 
523
        WFE = WeaveFormatError
 
524
 
 
525
        for l in self._weave:
 
526
            if isinstance(l, tuple):
 
527
                c, v = l
 
528
                isactive = None
 
529
                if c == '{':
 
530
                    assert v not in istack
 
531
                    istack.append(v)
 
532
                elif c == '}':
 
533
                    istack.pop()
 
534
                elif c == '[':
 
535
                    if v in included:
 
536
                        assert v not in dset
 
537
                        dset.add(v)
 
538
                else:
 
539
                    assert c == ']'
 
540
                    if v in included:
 
541
                        assert v in dset
 
542
                        dset.remove(v)
 
543
            else:
 
544
                assert isinstance(l, basestring)
 
545
                if isactive is None:
 
546
                    isactive = (not dset) and istack and (istack[-1] in included)
 
547
                if isactive:
 
548
                    result.append((istack[-1], lineno, l))
615
549
            lineno += 1
616
550
 
617
551
        if istack:
618
 
            raise WeaveFormatError("unclosed insertion blocks "
619
 
                    "at end of weave: %s" % istack)
 
552
            raise WFE("unclosed insertion blocks at end of weave",
 
553
                                   istack)
620
554
        if dset:
621
 
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
622
 
                                   % dset)
623
 
 
 
555
            raise WFE("unclosed deletion blocks at end of weave",
 
556
                                   dset)
 
557
 
 
558
        return result
 
559
    
 
560
 
 
561
 
 
562
    def get_iter(self, name_or_index):
 
563
        """Yield lines for the specified version."""
 
564
        incls = [self.maybe_lookup(name_or_index)]
 
565
        for origin, lineno, line in self._extract(incls):
 
566
            yield line
 
567
 
 
568
 
 
569
    def get_text(self, name_or_index):
 
570
        return ''.join(self.get_iter(name_or_index))
 
571
        assert isinstance(version, int)
 
572
 
 
573
 
 
574
    def get_lines(self, name_or_index):
 
575
        return list(self.get_iter(name_or_index))
 
576
 
 
577
 
 
578
    get = get_lines
 
579
 
 
580
 
 
581
    def mash_iter(self, included):
 
582
        """Return composed version of multiple included versions."""
 
583
        included = map(self.maybe_lookup, included)
 
584
        for origin, lineno, text in self._extract(included):
 
585
            yield text
 
586
 
 
587
 
 
588
    def dump(self, to_file):
 
589
        from pprint import pprint
 
590
        print >>to_file, "Weave._weave = ",
 
591
        pprint(self._weave, to_file)
 
592
        print >>to_file, "Weave._parents = ",
 
593
        pprint(self._parents, to_file)
 
594
 
 
595
 
 
596
 
 
597
    def numversions(self):
 
598
        l = len(self._parents)
 
599
        assert l == len(self._sha1s)
 
600
        return l
 
601
 
 
602
 
 
603
    def __len__(self):
 
604
        return self.numversions()
 
605
 
 
606
 
 
607
    def check(self, progress_bar=None):
 
608
        # check no circular inclusions
 
609
        for version in range(self.numversions()):
 
610
            inclusions = list(self._parents[version])
 
611
            if inclusions:
 
612
                inclusions.sort()
 
613
                if inclusions[-1] >= version:
 
614
                    raise WeaveFormatError("invalid included version %d for index %d"
 
615
                                           % (inclusions[-1], version))
 
616
 
 
617
        # try extracting all versions; this is a bit slow and parallel
 
618
        # extraction could be used
 
619
        nv = self.numversions()
 
620
        for version in range(nv):
 
621
            if progress_bar:
 
622
                progress_bar.update('checking text', version, nv)
 
623
            s = sha.new()
 
624
            for l in self.get_iter(version):
 
625
                s.update(l)
 
626
            hd = s.hexdigest()
 
627
            expected = self._sha1s[version]
 
628
            if hd != expected:
 
629
                raise WeaveError("mismatched sha1 for version %d; "
 
630
                                 "got %s, expected %s"
 
631
                                 % (version, hd, expected))
 
632
 
 
633
        # TODO: check insertions are properly nested, that there are
 
634
        # no lines outside of insertion blocks, that deletions are
 
635
        # properly paired, etc.
 
636
 
 
637
 
 
638
 
 
639
    def merge(self, merge_versions):
 
640
        """Automerge and mark conflicts between versions.
 
641
 
 
642
        This returns a sequence, each entry describing alternatives
 
643
        for a chunk of the file.  Each of the alternatives is given as
 
644
        a list of lines.
 
645
 
 
646
        If there is a chunk of the file where there's no diagreement,
 
647
        only one alternative is given.
 
648
        """
 
649
        # approach: find the included versions common to all the
 
650
        # merged versions
 
651
        raise NotImplementedError()
 
652
 
 
653
 
 
654
 
 
655
    def _delta(self, included, lines):
 
656
        """Return changes from basis to new revision.
 
657
 
 
658
        The old text for comparison is the union of included revisions.
 
659
 
 
660
        This is used in inserting a new text.
 
661
 
 
662
        Delta is returned as a sequence of
 
663
        (weave1, weave2, newlines).
 
664
 
 
665
        This indicates that weave1:weave2 of the old weave should be
 
666
        replaced by the sequence of lines in newlines.  Note that
 
667
        these line numbers are positions in the total weave and don't
 
668
        correspond to the lines in any extracted version, or even the
 
669
        extracted union of included versions.
 
670
 
 
671
        If line1=line2, this is a pure insert; if newlines=[] this is a
 
672
        pure delete.  (Similar to difflib.)
 
673
        """
 
674
        raise NotImplementedError()
 
675
 
 
676
            
624
677
    def plan_merge(self, ver_a, ver_b):
625
678
        """Return pseudo-annotation indicating how the two versions merge.
626
679
 
629
682
 
630
683
        Weave lines present in none of them are skipped entirely.
631
684
        """
632
 
        inc_a = set(self.get_ancestry([ver_a]))
633
 
        inc_b = set(self.get_ancestry([ver_b]))
 
685
        inc_a = self.inclusions([ver_a])
 
686
        inc_b = self.inclusions([ver_b])
634
687
        inc_c = inc_a & inc_b
635
688
 
636
 
        for lineno, insert, deleteset, line in self._walk_internal([ver_a, ver_b]):
 
689
        for lineno, insert, deleteset, line in self._walk():
637
690
            if deleteset & inc_c:
638
691
                # killed in parent; can't be in either a or b
639
692
                # not relevant to our work
665
718
                # not in either revision
666
719
                yield 'irrelevant', line
667
720
 
668
 
    def _extract(self, versions):
669
 
        """Yield annotation of lines in included set.
670
 
 
671
 
        Yields a sequence of tuples (origin, lineno, text), where
672
 
        origin is the origin version, lineno the index in the weave,
673
 
        and text the text of the line.
674
 
 
675
 
        The set typically but not necessarily corresponds to a version.
676
 
        """
677
 
        for i in versions:
678
 
            if not isinstance(i, int):
679
 
                raise ValueError(i)
680
 
 
681
 
        included = self._inclusions(versions)
682
 
 
683
 
        istack = []
684
 
        iset = set()
685
 
        dset = set()
686
 
 
687
 
        lineno = 0         # line of weave, 0-based
688
 
 
689
 
        isactive = None
690
 
 
691
 
        result = []
692
 
 
693
 
        WFE = WeaveFormatError
694
 
 
695
 
        # wow.
696
 
        #  449       0   4474.6820   2356.5590   bzrlib.weave:556(_extract)
697
 
        #  +285282   0   1676.8040   1676.8040   +<isinstance>
698
 
        # 1.6 seconds in 'isinstance'.
699
 
        # changing the first isinstance:
700
 
        #  449       0   2814.2660   1577.1760   bzrlib.weave:556(_extract)
701
 
        #  +140414   0    762.8050    762.8050   +<isinstance>
702
 
        # note that the inline time actually dropped (less function calls)
703
 
        # and total processing time was halved.
704
 
        # we're still spending ~1/4 of the method in isinstance though.
705
 
        # so lets hard code the acceptable string classes we expect:
706
 
        #  449       0   1202.9420    786.2930   bzrlib.weave:556(_extract)
707
 
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list'
708
 
        #                                          objects>
709
 
        # yay, down to ~1/4 the initial extract time, and our inline time
710
 
        # has shrunk again, with isinstance no longer dominating.
711
 
        # tweaking the stack inclusion test to use a set gives:
712
 
        #  449       0   1122.8030    713.0080   bzrlib.weave:556(_extract)
713
 
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list'
714
 
        #                                          objects>
715
 
        # - a 5% win, or possibly just noise. However with large istacks that
716
 
        # 'in' test could dominate, so I'm leaving this change in place -
717
 
        # when its fast enough to consider profiling big datasets we can review.
718
 
 
719
 
 
720
 
 
721
 
 
722
 
        for l in self._weave:
723
 
            if l.__class__ == tuple:
724
 
                c, v = l
725
 
                isactive = None
726
 
                if c == '{':
727
 
                    istack.append(v)
728
 
                    iset.add(v)
729
 
                elif c == '}':
730
 
                    iset.remove(istack.pop())
731
 
                elif c == '[':
732
 
                    if v in included:
733
 
                        dset.add(v)
734
 
                elif c == ']':
735
 
                    if v in included:
736
 
                        dset.remove(v)
 
721
        yield 'unchanged', ''           # terminator
 
722
 
 
723
 
 
724
 
 
725
    def weave_merge(self, plan):
 
726
        lines_a = []
 
727
        lines_b = []
 
728
        ch_a = ch_b = False
 
729
 
 
730
        for state, line in plan:
 
731
            if state == 'unchanged' or state == 'killed-both':
 
732
                # resync and flush queued conflicts changes if any
 
733
                if not lines_a and not lines_b:
 
734
                    pass
 
735
                elif ch_a and not ch_b:
 
736
                    # one-sided change:                    
 
737
                    for l in lines_a: yield l
 
738
                elif ch_b and not ch_a:
 
739
                    for l in lines_b: yield l
 
740
                elif lines_a == lines_b:
 
741
                    for l in lines_a: yield l
737
742
                else:
738
 
                    raise AssertionError()
 
743
                    yield '<<<<\n'
 
744
                    for l in lines_a: yield l
 
745
                    yield '====\n'
 
746
                    for l in lines_b: yield l
 
747
                    yield '>>>>\n'
 
748
 
 
749
                del lines_a[:]
 
750
                del lines_b[:]
 
751
                ch_a = ch_b = False
 
752
                
 
753
            if state == 'unchanged':
 
754
                if line:
 
755
                    yield line
 
756
            elif state == 'killed-a':
 
757
                ch_a = True
 
758
                lines_b.append(line)
 
759
            elif state == 'killed-b':
 
760
                ch_b = True
 
761
                lines_a.append(line)
 
762
            elif state == 'new-a':
 
763
                ch_a = True
 
764
                lines_a.append(line)
 
765
            elif state == 'new-b':
 
766
                ch_b = True
 
767
                lines_b.append(line)
739
768
            else:
740
 
                if isactive is None:
741
 
                    isactive = (not dset) and istack and (istack[-1] in included)
742
 
                if isactive:
743
 
                    result.append((istack[-1], lineno, l))
744
 
            lineno += 1
745
 
        if istack:
746
 
            raise WeaveFormatError("unclosed insertion blocks "
747
 
                    "at end of weave: %s" % istack)
748
 
        if dset:
749
 
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
750
 
                                   % dset)
751
 
        return result
752
 
 
753
 
    def _maybe_lookup(self, name_or_index):
754
 
        """Convert possible symbolic name to index, or pass through indexes.
755
 
 
756
 
        NOT FOR PUBLIC USE.
 
769
                assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
 
770
                                 'killed-both'), \
 
771
                       state
 
772
 
 
773
                
 
774
    def join(self, other):
 
775
        """Integrate versions from other into this weave.
 
776
 
 
777
        The resulting weave contains all the history of both weaves; 
 
778
        any version you could retrieve from either self or other can be 
 
779
        retrieved from self after this call.
 
780
 
 
781
        It is illegal for the two weaves to contain different values 
 
782
        or different parents for any version.  See also reweave().
757
783
        """
758
 
        if isinstance(name_or_index, (int, long)):
759
 
            return name_or_index
760
 
        else:
761
 
            return self._lookup(name_or_index)
762
 
 
763
 
    def get_lines(self, version_id):
764
 
        """See VersionedFile.get_lines()."""
765
 
        int_index = self._maybe_lookup(version_id)
766
 
        result = [line for (origin, lineno, line) in self._extract([int_index])]
767
 
        expected_sha1 = self._sha1s[int_index]
768
 
        measured_sha1 = sha_strings(result)
769
 
        if measured_sha1 != expected_sha1:
770
 
            raise errors.WeaveInvalidChecksum(
771
 
                    'file %s, revision %s, expected: %s, measured %s'
772
 
                    % (self._weave_name, version_id,
773
 
                       expected_sha1, measured_sha1))
774
 
        return result
775
 
 
776
 
    def get_sha1s(self, version_ids):
777
 
        """See VersionedFile.get_sha1s()."""
778
 
        result = {}
779
 
        for v in version_ids:
780
 
            result[v] = self._sha1s[self._lookup(v)]
781
 
        return result
782
 
 
783
 
    def num_versions(self):
784
 
        """How many versions are in this weave?"""
785
 
        l = len(self._parents)
786
 
        return l
787
 
 
788
 
    __len__ = num_versions
789
 
 
790
 
    def check(self, progress_bar=None):
791
 
        # TODO evaluate performance hit of using string sets in this routine.
792
 
        # TODO: check no circular inclusions
793
 
        # TODO: create a nested progress bar
794
 
        for version in range(self.num_versions()):
795
 
            inclusions = list(self._parents[version])
796
 
            if inclusions:
797
 
                inclusions.sort()
798
 
                if inclusions[-1] >= version:
799
 
                    raise WeaveFormatError("invalid included version %d for index %d"
800
 
                                           % (inclusions[-1], version))
801
 
 
802
 
        # try extracting all versions; parallel extraction is used
803
 
        nv = self.num_versions()
804
 
        sha1s = {}
805
 
        texts = {}
806
 
        inclusions = {}
807
 
        for i in range(nv):
808
 
            # For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
809
 
            # The problem is that set membership is much more expensive
810
 
            name = self._idx_to_name(i)
811
 
            sha1s[name] = sha()
812
 
            texts[name] = []
813
 
            new_inc = set([name])
814
 
            for p in self._parents[i]:
815
 
                new_inc.update(inclusions[self._idx_to_name(p)])
816
 
 
817
 
            if set(new_inc) != set(self.get_ancestry(name)):
818
 
                raise AssertionError(
819
 
                    'failed %s != %s'
820
 
                    % (set(new_inc), set(self.get_ancestry(name))))
821
 
            inclusions[name] = new_inc
822
 
 
823
 
        nlines = len(self._weave)
824
 
 
825
 
        update_text = 'checking weave'
826
 
        if self._weave_name:
827
 
            short_name = os.path.basename(self._weave_name)
828
 
            update_text = 'checking %s' % (short_name,)
829
 
            update_text = update_text[:25]
830
 
 
831
 
        for lineno, insert, deleteset, line in self._walk_internal():
832
 
            if progress_bar:
833
 
                progress_bar.update(update_text, lineno, nlines)
834
 
 
835
 
            for name, name_inclusions in inclusions.items():
836
 
                # The active inclusion must be an ancestor,
837
 
                # and no ancestors must have deleted this line,
838
 
                # because we don't support resurrection.
839
 
                if (insert in name_inclusions) and not (deleteset & name_inclusions):
840
 
                    sha1s[name].update(line)
841
 
 
842
 
        for i in range(nv):
843
 
            version = self._idx_to_name(i)
844
 
            hd = sha1s[version].hexdigest()
845
 
            expected = self._sha1s[i]
846
 
            if hd != expected:
847
 
                raise errors.WeaveInvalidChecksum(
848
 
                        "mismatched sha1 for version %s: "
849
 
                        "got %s, expected %s"
850
 
                        % (version, hd, expected))
851
 
 
852
 
        # TODO: check insertions are properly nested, that there are
853
 
        # no lines outside of insertion blocks, that deletions are
854
 
        # properly paired, etc.
 
784
        if other.numversions() == 0:
 
785
            return          # nothing to update, easy
 
786
        # two loops so that we do not change ourselves before verifying it
 
787
        # will be ok
 
788
        # work through in index order to make sure we get all dependencies
 
789
        for other_idx, name in enumerate(other._names):
 
790
            if self._check_version_consistent(other, other_idx, name):
 
791
                continue
 
792
        for other_idx, name in enumerate(other._names):
 
793
            # TODO: If all the parents of the other version are already 
 
794
            # present then we can avoid some work by just taking the delta
 
795
            # and adjusting the offsets.
 
796
            new_parents = self._imported_parents(other, other_idx)
 
797
            lines = other.get_lines(other_idx)
 
798
            sha1 = other._sha1s[other_idx]
 
799
            self.add(name, new_parents, lines, sha1)
 
800
 
855
801
 
856
802
    def _imported_parents(self, other, other_idx):
857
803
        """Return list of parents in self corresponding to indexes in other."""
858
804
        new_parents = []
859
805
        for parent_idx in other._parents[other_idx]:
860
806
            parent_name = other._names[parent_idx]
861
 
            if parent_name not in self._name_map:
 
807
            if parent_name not in self._names:
862
808
                # should not be possible
863
 
                raise WeaveError("missing parent {%s} of {%s} in %r"
 
809
                raise WeaveError("missing parent {%s} of {%s} in %r" 
864
810
                                 % (parent_name, other._name_map[other_idx], self))
865
811
            new_parents.append(self._name_map[parent_name])
866
812
        return new_parents
873
819
         * the same text
874
820
         * the same direct parents (by name, not index, and disregarding
875
821
           order)
876
 
 
 
822
        
877
823
        If present & correct return True;
878
 
        if not present in self return False;
 
824
        if not present in self return False; 
879
825
        if inconsistent raise error."""
880
826
        this_idx = self._name_map.get(name, -1)
881
827
        if this_idx != -1:
882
828
            if self._sha1s[this_idx] != other._sha1s[other_idx]:
883
 
                raise errors.WeaveTextDiffers(name, self, other)
 
829
                raise WeaveError("inconsistent texts for version {%s} "
 
830
                                 "when joining weaves"
 
831
                                 % (name))
884
832
            self_parents = self._parents[this_idx]
885
833
            other_parents = other._parents[other_idx]
886
 
            n1 = set([self._names[i] for i in self_parents])
887
 
            n2 = set([other._names[i] for i in other_parents])
888
 
            if not self._compatible_parents(n1, n2):
 
834
            n1 = [self._names[i] for i in self_parents]
 
835
            n2 = [other._names[i] for i in other_parents]
 
836
            n1.sort()
 
837
            n2.sort()
 
838
            if n1 != n2:
889
839
                raise WeaveParentMismatch("inconsistent parents "
890
840
                    "for version {%s}: %s vs %s" % (name, n1, n2))
891
841
            else:
893
843
        else:
894
844
            return False
895
845
 
896
 
    def _reweave(self, other, pb, msg):
897
 
        """Reweave self with other - internal helper for join().
898
 
 
899
 
        :param other: The other weave to merge
900
 
        :param pb: An optional progress bar, indicating how far done we are
901
 
        :param msg: An optional message for the progress
902
 
        """
903
 
        new_weave = _reweave(self, other, pb=pb, msg=msg)
904
 
        self._copy_weave_content(new_weave)
905
 
 
906
 
    def _copy_weave_content(self, otherweave):
907
 
        """adsorb the content from otherweave."""
 
846
    def reweave(self, other):
 
847
        """Reweave self with other."""
 
848
        new_weave = reweave(self, other)
908
849
        for attr in self.__slots__:
909
 
            if attr != '_weave_name':
910
 
                setattr(self, attr, copy(getattr(otherweave, attr)))
911
 
 
912
 
 
913
 
class WeaveFile(Weave):
914
 
    """A WeaveFile represents a Weave on disk and writes on change."""
915
 
 
916
 
    WEAVE_SUFFIX = '.weave'
917
 
 
918
 
    def __init__(self, name, transport, filemode=None, create=False, access_mode='w', get_scope=None):
919
 
        """Create a WeaveFile.
920
 
 
921
 
        :param create: If not True, only open an existing knit.
922
 
        """
923
 
        super(WeaveFile, self).__init__(name, access_mode, get_scope=get_scope,
924
 
            allow_reserved=False)
925
 
        self._transport = transport
926
 
        self._filemode = filemode
927
 
        try:
928
 
            _read_weave_v5(self._transport.get(name + WeaveFile.WEAVE_SUFFIX), self)
929
 
        except errors.NoSuchFile:
930
 
            if not create:
931
 
                raise
932
 
            # new file, save it
933
 
            self._save()
934
 
 
935
 
    def _add_lines(self, version_id, parents, lines, parent_texts,
936
 
        left_matching_blocks, nostore_sha, random_id, check_content):
937
 
        """Add a version and save the weave."""
938
 
        self.check_not_reserved_id(version_id)
939
 
        result = super(WeaveFile, self)._add_lines(version_id, parents, lines,
940
 
            parent_texts, left_matching_blocks, nostore_sha, random_id,
941
 
            check_content)
942
 
        self._save()
943
 
        return result
944
 
 
945
 
    def copy_to(self, name, transport):
946
 
        """See VersionedFile.copy_to()."""
947
 
        # as we are all in memory always, just serialise to the new place.
948
 
        sio = StringIO()
949
 
        write_weave_v5(self, sio)
950
 
        sio.seek(0)
951
 
        transport.put_file(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
952
 
 
953
 
    def _save(self):
954
 
        """Save the weave."""
955
 
        self._check_write_ok()
956
 
        sio = StringIO()
957
 
        write_weave_v5(self, sio)
958
 
        sio.seek(0)
959
 
        bytes = sio.getvalue()
960
 
        path = self._weave_name + WeaveFile.WEAVE_SUFFIX
961
 
        try:
962
 
            self._transport.put_bytes(path, bytes, self._filemode)
963
 
        except errors.NoSuchFile:
964
 
            self._transport.mkdir(dirname(path))
965
 
            self._transport.put_bytes(path, bytes, self._filemode)
966
 
 
967
 
    @staticmethod
968
 
    def get_suffixes():
969
 
        """See VersionedFile.get_suffixes()."""
970
 
        return [WeaveFile.WEAVE_SUFFIX]
971
 
 
972
 
    def insert_record_stream(self, stream):
973
 
        super(WeaveFile, self).insert_record_stream(stream)
974
 
        self._save()
975
 
 
976
 
 
977
 
def _reweave(wa, wb, pb=None, msg=None):
 
850
            setattr(self, attr, getattr(new_weave, attr))
 
851
 
 
852
 
 
853
def reweave(wa, wb):
978
854
    """Combine two weaves and return the result.
979
855
 
980
 
    This works even if a revision R has different parents in
 
856
    This works even if a revision R has different parents in 
981
857
    wa and wb.  In the resulting weave all the parents are given.
982
858
 
983
 
    This is done by just building up a new weave, maintaining ordering
 
859
    This is done by just building up a new weave, maintaining ordering 
984
860
    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
 
861
    might be possible but it should only be necessary to do 
 
862
    this operation rarely, when a new previously ghost version is 
987
863
    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
864
    """
992
865
    wr = Weave()
993
866
    ia = ib = 0
994
 
    queue_a = range(wa.num_versions())
995
 
    queue_b = range(wb.num_versions())
 
867
    queue_a = range(wa.numversions())
 
868
    queue_b = range(wb.numversions())
996
869
    # first determine combined parents of all versions
997
870
    # map from version name -> all parent names
998
871
    combined_parents = _reweave_parent_graphs(wa, wb)
999
872
    mutter("combined parents: %r", combined_parents)
1000
 
    order = tsort.topo_sort(combined_parents.iteritems())
 
873
    order = _make_reweave_order(wa._names, wb._names, combined_parents)
1001
874
    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))
 
875
    for name in order:
1009
876
        if name in wa._name_map:
1010
877
            lines = wa.get_lines(name)
1011
878
            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)
 
879
                assert lines == wb.get_lines(name)
1021
880
        else:
1022
881
            lines = wb.get_lines(name)
1023
 
        wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
 
882
        wr.add(name, combined_parents[name], lines)
1024
883
    return wr
1025
884
 
1026
885
 
1027
886
def _reweave_parent_graphs(wa, wb):
1028
887
    """Return combined parent ancestry for two weaves.
1029
 
 
 
888
    
1030
889
    Returned as a list of (version_name, set(parent_names))"""
1031
890
    combined = {}
1032
891
    for weave in [wa, wb]:
1033
892
        for idx, name in enumerate(weave._names):
1034
893
            p = combined.setdefault(name, set())
1035
 
            p.update(map(weave._idx_to_name, weave._parents[idx]))
 
894
            p.update(map(weave.idx_to_name, weave._parents[idx]))
1036
895
    return combined
 
896
 
 
897
 
 
898
def _make_reweave_order(wa_order, wb_order, combined_parents):
 
899
    """Return an order to reweave versions respecting parents."""
 
900
    done = set()
 
901
    result = []
 
902
    ia = ib = 0
 
903
    next_a = next_b = None
 
904
    len_a = len(wa_order)
 
905
    len_b = len(wb_order)
 
906
    while ia < len(wa_order) or ib < len(wb_order):
 
907
        if ia < len_a:
 
908
            next_a = wa_order[ia]
 
909
            if next_a in done:
 
910
                ia += 1
 
911
                continue
 
912
            if combined_parents[next_a].issubset(done):
 
913
                ia += 1
 
914
                result.append(next_a)
 
915
                done.add(next_a)
 
916
                continue
 
917
        if ib < len_b:
 
918
            next_b = wb_order[ib]
 
919
            if next_b in done:
 
920
                ib += 1
 
921
                continue
 
922
            elif combined_parents[next_b].issubset(done):
 
923
                ib += 1
 
924
                result.append(next_b)
 
925
                done.add(next_b)
 
926
                continue
 
927
        raise WeaveError("don't know how to reweave at {%s} and {%s}"
 
928
                         % (next_a, next_b))
 
929
    return result
 
930
 
 
931
 
 
932
def weave_toc(w):
 
933
    """Show the weave's table-of-contents"""
 
934
    print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
 
935
    for i in (6, 50, 10, 10):
 
936
        print '-' * i,
 
937
    print
 
938
    for i in range(w.numversions()):
 
939
        sha1 = w._sha1s[i]
 
940
        name = w._names[i]
 
941
        parent_str = ' '.join(map(str, w._parents[i]))
 
942
        print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
 
943
 
 
944
 
 
945
 
 
946
def weave_stats(weave_file, pb):
 
947
    from bzrlib.weavefile import read_weave
 
948
 
 
949
    wf = file(weave_file, 'rb')
 
950
    w = read_weave(wf)
 
951
    # FIXME: doesn't work on pipes
 
952
    weave_size = wf.tell()
 
953
 
 
954
    total = 0
 
955
    vers = len(w)
 
956
    for i in range(vers):
 
957
        pb.update('checking sizes', i, vers)
 
958
        for origin, lineno, line in w._extract([i]):
 
959
            total += len(line)
 
960
 
 
961
    pb.clear()
 
962
 
 
963
    print 'versions          %9d' % vers
 
964
    print 'weave file        %9d bytes' % weave_size
 
965
    print 'total contents    %9d bytes' % total
 
966
    print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
 
967
    if vers:
 
968
        avg = total/vers
 
969
        print 'average size      %9d bytes' % avg
 
970
        print 'relative size     %9.2fx' % (float(weave_size) / float(avg))
 
971
 
 
972
 
 
973
def usage():
 
974
    print """bzr weave tool
 
975
 
 
976
Experimental tool for weave algorithm.
 
977
 
 
978
usage:
 
979
    weave init WEAVEFILE
 
980
        Create an empty weave file
 
981
    weave get WEAVEFILE VERSION
 
982
        Write out specified version.
 
983
    weave check WEAVEFILE
 
984
        Check consistency of all versions.
 
985
    weave toc WEAVEFILE
 
986
        Display table of contents.
 
987
    weave add WEAVEFILE NAME [BASE...] < NEWTEXT
 
988
        Add NEWTEXT, with specified parent versions.
 
989
    weave annotate WEAVEFILE VERSION
 
990
        Display origin of each line.
 
991
    weave mash WEAVEFILE VERSION...
 
992
        Display composite of all selected versions.
 
993
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
 
994
        Auto-merge two versions and display conflicts.
 
995
    weave diff WEAVEFILE VERSION1 VERSION2 
 
996
        Show differences between two versions.
 
997
 
 
998
example:
 
999
 
 
1000
    % weave init foo.weave
 
1001
    % vi foo.txt
 
1002
    % weave add foo.weave ver0 < foo.txt
 
1003
    added version 0
 
1004
 
 
1005
    (create updated version)
 
1006
    % vi foo.txt
 
1007
    % weave get foo.weave 0 | diff -u - foo.txt
 
1008
    % weave add foo.weave ver1 0 < foo.txt
 
1009
    added version 1
 
1010
 
 
1011
    % weave get foo.weave 0 > foo.txt       (create forked version)
 
1012
    % vi foo.txt
 
1013
    % weave add foo.weave ver2 0 < foo.txt
 
1014
    added version 2
 
1015
 
 
1016
    % weave merge foo.weave 1 2 > foo.txt   (merge them)
 
1017
    % vi foo.txt                            (resolve conflicts)
 
1018
    % weave add foo.weave merged 1 2 < foo.txt     (commit merged version)     
 
1019
    
 
1020
"""
 
1021
    
 
1022
 
 
1023
 
 
1024
def main(argv):
 
1025
    import sys
 
1026
    import os
 
1027
    try:
 
1028
        import bzrlib
 
1029
    except ImportError:
 
1030
        # in case we're run directly from the subdirectory
 
1031
        sys.path.append('..')
 
1032
        import bzrlib
 
1033
    from bzrlib.weavefile import write_weave, read_weave
 
1034
    from bzrlib.progress import ProgressBar
 
1035
 
 
1036
    try:
 
1037
        import psyco
 
1038
        psyco.full()
 
1039
    except ImportError:
 
1040
        pass
 
1041
 
 
1042
    if len(argv) < 2:
 
1043
        usage()
 
1044
        return 0
 
1045
 
 
1046
    cmd = argv[1]
 
1047
 
 
1048
    def readit():
 
1049
        return read_weave(file(argv[2], 'rb'))
 
1050
    
 
1051
    if cmd == 'help':
 
1052
        usage()
 
1053
    elif cmd == 'add':
 
1054
        w = readit()
 
1055
        # at the moment, based on everything in the file
 
1056
        name = argv[3]
 
1057
        parents = map(int, argv[4:])
 
1058
        lines = sys.stdin.readlines()
 
1059
        ver = w.add(name, parents, lines)
 
1060
        write_weave(w, file(argv[2], 'wb'))
 
1061
        print 'added version %r %d' % (name, ver)
 
1062
    elif cmd == 'init':
 
1063
        fn = argv[2]
 
1064
        if os.path.exists(fn):
 
1065
            raise IOError("file exists")
 
1066
        w = Weave()
 
1067
        write_weave(w, file(fn, 'wb'))
 
1068
    elif cmd == 'get': # get one version
 
1069
        w = readit()
 
1070
        sys.stdout.writelines(w.get_iter(int(argv[3])))
 
1071
        
 
1072
    elif cmd == 'mash': # get composite
 
1073
        w = readit()
 
1074
        sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
 
1075
 
 
1076
    elif cmd == 'diff':
 
1077
        from difflib import unified_diff
 
1078
        w = readit()
 
1079
        fn = argv[2]
 
1080
        v1, v2 = map(int, argv[3:5])
 
1081
        lines1 = w.get(v1)
 
1082
        lines2 = w.get(v2)
 
1083
        diff_gen = unified_diff(lines1, lines2,
 
1084
                                '%s version %d' % (fn, v1),
 
1085
                                '%s version %d' % (fn, v2))
 
1086
        sys.stdout.writelines(diff_gen)
 
1087
            
 
1088
    elif cmd == 'annotate':
 
1089
        w = readit()
 
1090
        # newline is added to all lines regardless; too hard to get
 
1091
        # reasonable formatting otherwise
 
1092
        lasto = None
 
1093
        for origin, text in w.annotate(int(argv[3])):
 
1094
            text = text.rstrip('\r\n')
 
1095
            if origin == lasto:
 
1096
                print '      | %s' % (text)
 
1097
            else:
 
1098
                print '%5d | %s' % (origin, text)
 
1099
                lasto = origin
 
1100
                
 
1101
    elif cmd == 'toc':
 
1102
        weave_toc(readit())
 
1103
 
 
1104
    elif cmd == 'stats':
 
1105
        weave_stats(argv[2], ProgressBar())
 
1106
        
 
1107
    elif cmd == 'check':
 
1108
        w = readit()
 
1109
        pb = ProgressBar()
 
1110
        w.check(pb)
 
1111
        pb.clear()
 
1112
        print '%d versions ok' % w.numversions()
 
1113
 
 
1114
    elif cmd == 'inclusions':
 
1115
        w = readit()
 
1116
        print ' '.join(map(str, w.inclusions([int(argv[3])])))
 
1117
 
 
1118
    elif cmd == 'parents':
 
1119
        w = readit()
 
1120
        print ' '.join(map(str, w._parents[int(argv[3])]))
 
1121
 
 
1122
    elif cmd == 'plan-merge':
 
1123
        w = readit()
 
1124
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
 
1125
            if line:
 
1126
                print '%14s | %s' % (state, line),
 
1127
 
 
1128
    elif cmd == 'merge':
 
1129
        w = readit()
 
1130
        p = w.plan_merge(int(argv[3]), int(argv[4]))
 
1131
        sys.stdout.writelines(w.weave_merge(p))
 
1132
            
 
1133
    elif cmd == 'mash-merge':
 
1134
        if len(argv) != 5:
 
1135
            usage()
 
1136
            return 1
 
1137
 
 
1138
        w = readit()
 
1139
        v1, v2 = map(int, argv[3:5])
 
1140
 
 
1141
        basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
 
1142
 
 
1143
        base_lines = list(w.mash_iter(basis))
 
1144
        a_lines = list(w.get(v1))
 
1145
        b_lines = list(w.get(v2))
 
1146
 
 
1147
        from bzrlib.merge3 import Merge3
 
1148
        m3 = Merge3(base_lines, a_lines, b_lines)
 
1149
 
 
1150
        name_a = 'version %d' % v1
 
1151
        name_b = 'version %d' % v2
 
1152
        sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
 
1153
    else:
 
1154
        raise ValueError('unknown command %r' % cmd)
 
1155
    
 
1156
 
 
1157
 
 
1158
def profile_main(argv): 
 
1159
    import tempfile, hotshot, hotshot.stats
 
1160
 
 
1161
    prof_f = tempfile.NamedTemporaryFile()
 
1162
 
 
1163
    prof = hotshot.Profile(prof_f.name)
 
1164
 
 
1165
    ret = prof.runcall(main, argv)
 
1166
    prof.close()
 
1167
 
 
1168
    stats = hotshot.stats.load(prof_f.name)
 
1169
    #stats.strip_dirs()
 
1170
    stats.sort_stats('cumulative')
 
1171
    ## XXX: Might like to write to stderr or the trace file instead but
 
1172
    ## print_stats seems hardcoded to stdout
 
1173
    stats.print_stats(20)
 
1174
            
 
1175
    return ret
 
1176
 
 
1177
 
 
1178
if __name__ == '__main__':
 
1179
    import sys
 
1180
    if '--profile' in sys.argv:
 
1181
        args = sys.argv[:]
 
1182
        args.remove('--profile')
 
1183
        sys.exit(profile_main(args))
 
1184
    else:
 
1185
        sys.exit(main(sys.argv))
 
1186