← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

Update news and readme

- better explanation of dependencies

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/weave.py
71
71
from difflib import SequenceMatcher
72
72
 
73
73
from bzrlib.trace import mutter
74
 
from bzrlib.errors import WeaveError, WeaveFormatError, WeaveParentMismatch, \
75
 
        WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent
76
 
from bzrlib.tsort import topo_sort
77
 
 
 
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
    
78
87
 
79
88
class Weave(object):
80
89
    """weave - versioned text file storage.
176
185
        self._name_map = {}
177
186
        self._weave_name = weave_name
178
187
 
179
 
    def __repr__(self):
180
 
        return "Weave(%r)" % self._weave_name
181
 
 
182
188
 
183
189
    def copy(self):
184
190
        """Return a deep copy of self.
204
210
    def __ne__(self, other):
205
211
        return not self.__eq__(other)
206
212
 
207
 
    def __contains__(self, name):
208
 
        return self._name_map.has_key(name)
209
213
 
210
214
    def maybe_lookup(self, name_or_index):
211
215
        """Convert possible symbolic name to index, or pass through indexes."""
220
224
        try:
221
225
            return self._name_map[name]
222
226
        except KeyError:
223
 
            raise WeaveRevisionNotPresent(name, self)
 
227
            raise WeaveError("name %r not present in weave %r" %
 
228
                             (name, self._weave_name))
224
229
 
225
 
    def names(self):
226
 
        return self._names[:]
227
230
 
228
231
    def iter_names(self):
229
232
        """Yield a list of all names in this weave."""
232
235
    def idx_to_name(self, version):
233
236
        return self._names[version]
234
237
 
 
238
 
235
239
    def _check_repeated_add(self, name, parents, text, sha1):
236
240
        """Check that a duplicated add is OK.
237
241
 
238
242
        If it is, return the (old) index; otherwise raise an exception.
239
243
        """
240
244
        idx = self.lookup(name)
241
 
        if sorted(self._parents[idx]) != sorted(parents) \
242
 
            or sha1 != self._sha1s[idx]:
243
 
            raise WeaveRevisionAlreadyPresent(name, self)
 
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)            
244
251
        return idx
245
252
        
 
253
 
 
254
        
246
255
    def add(self, name, parents, text, sha1=None):
247
256
        """Add a single text on top of the weave.
248
257
  
449
458
        for origin, lineno, text in self._extract(incls):
450
459
            yield origin, text
451
460
 
 
461
 
452
462
    def _walk(self):
453
463
        """Walk the weave.
454
464
 
476
486
                elif c == ']':
477
487
                    dset.remove(v)
478
488
                else:
479
 
                    raise WeaveFormatError('unexpected instruction %r' % v)
 
489
                    raise WeaveFormatError('unexpected instruction %r'
 
490
                                           % v)
480
491
            else:
481
492
                assert isinstance(l, basestring)
482
493
                assert istack
536
547
                if isactive:
537
548
                    result.append((istack[-1], lineno, l))
538
549
            lineno += 1
 
550
 
539
551
        if istack:
540
 
            raise WeaveFormatError("unclosed insertion blocks "
541
 
                    "at end of weave: %s" % istack)
 
552
            raise WFE("unclosed insertion blocks at end of weave",
 
553
                                   istack)
542
554
        if dset:
543
 
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
544
 
                                   % dset)
 
555
            raise WFE("unclosed deletion blocks at end of weave",
 
556
                                   dset)
 
557
 
545
558
        return result
 
559
    
546
560
 
547
561
 
548
562
    def get_iter(self, name_or_index):
621
635
        # properly paired, etc.
622
636
 
623
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
 
624
655
    def _delta(self, included, lines):
625
656
        """Return changes from basis to new revision.
626
657
 
709
740
                elif lines_a == lines_b:
710
741
                    for l in lines_a: yield l
711
742
                else:
712
 
                    yield '<<<<<<<\n'
 
743
                    yield '<<<<\n'
713
744
                    for l in lines_a: yield l
714
 
                    yield '=======\n'
 
745
                    yield '====\n'
715
746
                    for l in lines_b: yield l
716
 
                    yield '>>>>>>>\n'
 
747
                    yield '>>>>\n'
717
748
 
718
749
                del lines_a[:]
719
750
                del lines_b[:]
839
870
    # map from version name -> all parent names
840
871
    combined_parents = _reweave_parent_graphs(wa, wb)
841
872
    mutter("combined parents: %r", combined_parents)
842
 
    order = topo_sort(combined_parents.iteritems())
 
873
    order = _make_reweave_order(wa._names, wb._names, combined_parents)
843
874
    mutter("order to reweave: %r", order)
844
875
    for name in order:
845
876
        if name in wa._name_map:
864
895
    return combined
865
896
 
866
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
 
867
932
def weave_toc(w):
868
933
    """Show the weave's table-of-contents"""
869
934
    print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')