← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Robert Collins
  • Date: 2005-10-17 11:56:54 UTC
  • mfrom: (1185.16.59)
  • Revision ID: robertc@robertcollins.net-20051017115654-662239e1587524a8
merge from martin.

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.
201
210
    def __ne__(self, other):
202
211
        return not self.__eq__(other)
203
212
 
204
 
    def __contains__(self, name):
205
 
        return self._name_map.has_key(name)
206
213
 
207
214
    def maybe_lookup(self, name_or_index):
208
215
        """Convert possible symbolic name to index, or pass through indexes."""
217
224
        try:
218
225
            return self._name_map[name]
219
226
        except KeyError:
220
 
            raise WeaveRevisionNotPresent(name, self)
 
227
            raise WeaveError("name %r not present in weave %r" %
 
228
                             (name, self._weave_name))
221
229
 
222
 
    def names(self):
223
 
        return self._names[:]
224
230
 
225
231
    def iter_names(self):
226
232
        """Yield a list of all names in this weave."""
229
235
    def idx_to_name(self, version):
230
236
        return self._names[version]
231
237
 
 
238
 
232
239
    def _check_repeated_add(self, name, parents, text, sha1):
233
240
        """Check that a duplicated add is OK.
234
241
 
235
242
        If it is, return the (old) index; otherwise raise an exception.
236
243
        """
237
244
        idx = self.lookup(name)
238
 
        if sorted(self._parents[idx]) != sorted(parents) \
239
 
            or sha1 != self._sha1s[idx]:
240
 
            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)            
241
251
        return idx
242
252
        
 
253
 
 
254
        
243
255
    def add(self, name, parents, text, sha1=None):
244
256
        """Add a single text on top of the weave.
245
257
  
446
458
        for origin, lineno, text in self._extract(incls):
447
459
            yield origin, text
448
460
 
 
461
 
449
462
    def _walk(self):
450
463
        """Walk the weave.
451
464
 
473
486
                elif c == ']':
474
487
                    dset.remove(v)
475
488
                else:
476
 
                    raise WeaveFormatError('unexpected instruction %r' % v)
 
489
                    raise WeaveFormatError('unexpected instruction %r'
 
490
                                           % v)
477
491
            else:
478
492
                assert isinstance(l, basestring)
479
493
                assert istack
533
547
                if isactive:
534
548
                    result.append((istack[-1], lineno, l))
535
549
            lineno += 1
 
550
 
536
551
        if istack:
537
 
            raise WeaveFormatError("unclosed insertion blocks "
538
 
                    "at end of weave: %s" % istack)
 
552
            raise WFE("unclosed insertion blocks at end of weave",
 
553
                                   istack)
539
554
        if dset:
540
 
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
541
 
                                   % dset)
 
555
            raise WFE("unclosed deletion blocks at end of weave",
 
556
                                   dset)
 
557
 
542
558
        return result
 
559
    
543
560
 
544
561
 
545
562
    def get_iter(self, name_or_index):
723
740
                elif lines_a == lines_b:
724
741
                    for l in lines_a: yield l
725
742
                else:
726
 
                    yield '<<<<<<<\n'
 
743
                    yield '<<<<\n'
727
744
                    for l in lines_a: yield l
728
 
                    yield '=======\n'
 
745
                    yield '====\n'
729
746
                    for l in lines_b: yield l
730
 
                    yield '>>>>>>>\n'
 
747
                    yield '>>>>\n'
731
748
 
732
749
                del lines_a[:]
733
750
                del lines_b[:]
853
870
    # map from version name -> all parent names
854
871
    combined_parents = _reweave_parent_graphs(wa, wb)
855
872
    mutter("combined parents: %r", combined_parents)
856
 
    order = topo_sort(combined_parents.iteritems())
 
873
    order = _make_reweave_order(wa._names, wb._names, combined_parents)
857
874
    mutter("order to reweave: %r", order)
858
875
    for name in order:
859
876
        if name in wa._name_map:
878
895
    return combined
879
896
 
880
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
 
881
932
def weave_toc(w):
882
933
    """Show the weave's table-of-contents"""
883
934
    print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')