← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Aaron Bentley
  • Date: 2005-10-27 23:14:48 UTC
  • mfrom: (1185.16.130)
  • mto: (1185.25.1)
  • mto: This revision was merged to the branch mainline in revision 1491.
  • Revision ID: abentley@panoramicfeedback.com-20051027231448-ba0ae9cde819edc9
Merge from mainline

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