« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 1558.4.1
- compare with another revision
- compare with revision 1728.1.1
- download diff
- download tarball
- view history from revision 1558.4.1
- Committer: Aaron Bentley
- Date: 2006-03-09 14:33:08 UTC
- mfrom: (1602 +trunk)
- mto: (1534.10.1 Transactional Tree Transforms) (1551.6.4 Aaron's mergeable stuff) (1634.1.1 integration) (1558.8.2 bzr.progress)
- mto: This revision was merged to the branch mainline in revision 1604.
- Revision ID: abentley@panoramicfeedback.com-20060309143308-9ef11e32a83c4fed
Merge from mainline
- files added:
- bzrlib/inter.py
- bzrlib/store/revision
- bzrlib/store/versioned
- bzrlib/tests/interversionedfile_implementations
- bzrlib/tests/revisionstore_implementations
- files removed:
- bzrlib/tests/test_reweave.py
- files renamed:
- bzrlib/store/weave.py => bzrlib/store/versioned/__init__.py
- files modified:
- BRANCH.TODO
added
removed
bzrlib/weave.py
67
67
# the possible relationships.
68
68
69
69
70
from copy import copy
71
from cStringIO import StringIO
72
from difflib import SequenceMatcher
70
73
import os
71
74
import sha
72
from difflib import SequenceMatcher
75
import time
73
76
74
77
from bzrlib.trace import mutter
75
78
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
76
WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent)
79
RevisionAlreadyPresent,
80
RevisionNotPresent,
81
WeaveRevisionAlreadyPresent,
82
WeaveRevisionNotPresent,
83
)
77
84
import bzrlib.errors as errors
85
from bzrlib.osutils import sha_strings
86
from bzrlib.symbol_versioning import *
78
87
from bzrlib.tsort import topo_sort
79
80
81
class Weave(object):
88
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
89
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
90
91
92
class Weave(VersionedFile):
82
93
"""weave - versioned text file storage.
83
94
84
95
A Weave manages versions of line-based text files, keeping track
170
181
__slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
171
182
'_weave_name']
172
183
173
def __init__(self, weave_name=None):
184
def __init__(self, weave_name=None, access_mode='w'):
185
super(Weave, self).__init__(access_mode)
174
186
self._weave = []
175
187
self._parents = []
176
188
self._sha1s = []
181
193
def __repr__(self):
182
194
return "Weave(%r)" % self._weave_name
183
195
184
185
196
def copy(self):
186
197
"""Return a deep copy of self.
187
198
201
212
return self._parents == other._parents \
202
213
and self._weave == other._weave \
203
214
and self._sha1s == other._sha1s
204
205
215
206
216
def __ne__(self, other):
207
217
return not self.__eq__(other)
208
218
209
def __contains__(self, name):
210
return self._name_map.has_key(name)
211
212
def maybe_lookup(self, name_or_index):
213
"""Convert possible symbolic name to index, or pass through indexes."""
214
if isinstance(name_or_index, (int, long)):
215
return name_or_index
216
else:
217
return self.lookup(name_or_index)
218
219
219
@deprecated_method(zero_eight)
220
def idx_to_name(self, index):
221
"""Old public interface, the public interface is all names now."""
222
return index
223
224
def _idx_to_name(self, version):
225
return self._names[version]
226
227
@deprecated_method(zero_eight)
220
228
def lookup(self, name):
229
"""Backwards compatability thunk:
230
231
Return name, as name is valid in the api now, and spew deprecation
232
warnings everywhere.
233
"""
234
return name
235
236
def _lookup(self, name):
221
237
"""Convert symbolic version name to index."""
222
238
try:
223
239
return self._name_map[name]
224
240
except KeyError:
225
raise WeaveRevisionNotPresent(name, self)
226
241
raise RevisionNotPresent(name, self._weave_name)
242
243
@deprecated_method(zero_eight)
244
def iter_names(self):
245
"""Deprecated convenience function, please see VersionedFile.names()."""
246
return iter(self.names())
247
248
@deprecated_method(zero_eight)
227
249
def names(self):
250
"""See Weave.versions for the current api."""
251
return self.versions()
252
253
def versions(self):
254
"""See VersionedFile.versions."""
228
255
return self._names[:]
229
256
230
def iter_names(self):
231
"""Yield a list of all names in this weave."""
232
return iter(self._names)
233
234
def idx_to_name(self, version):
235
return self._names[version]
257
def has_version(self, version_id):
258
"""See VersionedFile.has_version."""
259
return self._name_map.has_key(version_id)
260
261
__contains__ = has_version
262
263
def get_parents(self, version_id):
264
"""See VersionedFile.get_parent."""
265
return map(self._idx_to_name, self._parents[self._lookup(version_id)])
236
266
237
267
def _check_repeated_add(self, name, parents, text, sha1):
238
268
"""Check that a duplicated add is OK.
239
269
240
270
If it is, return the (old) index; otherwise raise an exception.
241
271
"""
242
idx = self.lookup(name)
272
idx = self._lookup(name)
243
273
if sorted(self._parents[idx]) != sorted(parents) \
244
274
or sha1 != self._sha1s[idx]:
245
raise WeaveRevisionAlreadyPresent(name, self)
275
raise RevisionAlreadyPresent(name, self._weave_name)
246
276
return idx
247
277
278
@deprecated_method(zero_eight)
279
def add_identical(self, old_rev_id, new_rev_id, parents):
280
"""Please use Weave.clone_text now."""
281
return self.clone_text(new_rev_id, old_rev_id, parents)
282
283
def _add_lines(self, version_id, parents, lines):
284
"""See VersionedFile.add_lines."""
285
return self._add(version_id, lines, map(self._lookup, parents))
286
287
@deprecated_method(zero_eight)
248
288
def add(self, name, parents, text, sha1=None):
289
"""See VersionedFile.add_lines for the non deprecated api."""
290
return self._add(name, text, map(self._maybe_lookup, parents), sha1)
291
292
def _add(self, version_id, lines, parents, sha1=None):
249
293
"""Add a single text on top of the weave.
250
294
251
295
Returns the index number of the newly added version.
252
296
253
name
297
version_id
254
298
Symbolic name for this version.
255
299
(Typically the revision-id of the revision that added it.)
256
300
257
301
parents
258
302
List or set of direct parent version numbers.
259
303
260
text
304
lines
261
305
Sequence of lines to be added in the new version.
262
263
sha -- SHA-1 of the file, if known. This is trusted to be
264
correct if supplied.
265
306
"""
266
from bzrlib.osutils import sha_strings
267
268
assert isinstance(name, basestring)
269
if sha1 is None:
270
sha1 = sha_strings(text)
271
if name in self._name_map:
272
return self._check_repeated_add(name, parents, text, sha1)
273
274
parents = map(self.maybe_lookup, parents)
307
308
assert isinstance(version_id, basestring)
309
if not sha1:
310
sha1 = sha_strings(lines)
311
if version_id in self._name_map:
312
return self._check_repeated_add(version_id, parents, lines, sha1)
313
275
314
self._check_versions(parents)
276
## self._check_lines(text)
315
## self._check_lines(lines)
277
316
new_version = len(self._parents)
278
317
279
280
318
# if we abort after here the (in-memory) weave will be corrupt because only
281
319
# some fields are updated
282
320
# XXX: FIXME implement a succeed-or-fail of the rest of this routine.
283
321
# - Robert Collins 20060226
284
322
self._parents.append(parents[:])
285
323
self._sha1s.append(sha1)
286
self._names.append(name)
287
self._name_map[name] = new_version
324
self._names.append(version_id)
325
self._name_map[version_id] = new_version
288
326
289
327
290
328
if not parents:
292
330
# this more quickly by just appending unconditionally.
293
331
# even more specially, if we're adding an empty text we
294
332
# need do nothing at all.
295
if text:
333
if lines:
296
334
self._weave.append(('{', new_version))
297
self._weave.extend(text)
335
self._weave.extend(lines)
298
336
self._weave.append(('}', None))
299
300
337
return new_version
301
338
302
339
if len(parents) == 1:
306
343
return new_version
307
344
308
345
309
ancestors = self.inclusions(parents)
346
ancestors = self._inclusions(parents)
310
347
311
348
l = self._weave
312
349
319
356
320
357
# another small special case: a merge, producing the same text
321
358
# as auto-merge
322
if text == basis_lines:
323
return new_version
359
if lines == basis_lines:
360
return new_version
324
361
325
362
# add a sentinal, because we can also match against the final line
326
363
basis_lineno.append(len(self._weave))
332
369
#print 'basis_lines:', basis_lines
333
370
#print 'new_lines: ', lines
334
371
335
s = SequenceMatcher(None, basis_lines, text)
372
s = SequenceMatcher(None, basis_lines, lines)
336
373
337
374
# offset gives the number of lines that have been inserted
338
375
# into the weave up to the current point; if the original edit instruction
349
386
i1 = basis_lineno[i1]
350
387
i2 = basis_lineno[i2]
351
388
352
assert 0 <= j1 <= j2 <= len(text)
389
assert 0 <= j1 <= j2 <= len(lines)
353
390
354
391
#print tag, i1, i2, j1, j2
355
392
366
403
# we don't destroy ourselves
367
404
i = i2 + offset
368
405
self._weave[i:i] = ([('{', new_version)]
369
+ text[j1:j2]
406
+ lines[j1:j2]
370
407
+ [('}', None)])
371
408
offset += 2 + (j2 - j1)
372
373
409
return new_version
374
410
375
def add_identical(self, old_rev_id, new_rev_id, parents):
376
"""Add an identical text to old_rev_id as new_rev_id."""
377
old_lines = self.get(self.lookup(old_rev_id))
378
self.add(new_rev_id, parents, old_lines)
411
def _clone_text(self, new_version_id, old_version_id, parents):
412
"""See VersionedFile.clone_text."""
413
old_lines = self.get_text(old_version_id)
414
self.add_lines(new_version_id, parents, old_lines)
379
415
380
def inclusions(self, versions):
416
def _inclusions(self, versions):
381
417
"""Return set of all ancestors of given version(s)."""
418
if not len(versions):
419
return []
382
420
i = set(versions)
383
421
for v in xrange(max(versions), 0, -1):
384
422
if v in i:
388
426
## except IndexError:
389
427
## raise ValueError("version %d not present in weave" % v)
390
428
391
392
def parents(self, version):
393
return self._parents[version]
394
395
396
def parent_names(self, version):
397
"""Return version names for parents of a version."""
398
return map(self.idx_to_name, self._parents[self.lookup(version)])
399
400
401
def minimal_parents(self, version):
402
"""Find the minimal set of parents for the version."""
403
included = self._parents[version]
404
if not included:
429
@deprecated_method(zero_eight)
430
def inclusions(self, version_ids):
431
"""Deprecated - see VersionedFile.get_ancestry for the replacement."""
432
if not version_ids:
405
433
return []
406
407
li = list(included)
408
li.sort(reverse=True)
409
410
mininc = []
411
gotit = set()
412
413
for pv in li:
414
if pv not in gotit:
415
mininc.append(pv)
416
gotit.update(self.inclusions(pv))
417
418
assert mininc[0] >= 0
419
assert mininc[-1] < version
420
return mininc
421
422
434
if isinstance(version_ids[0], int):
435
return [self._idx_to_name(v) for v in self._inclusions(version_ids)]
436
else:
437
return self.get_ancestry(version_ids)
438
439
def get_ancestry(self, version_ids):
440
"""See VersionedFile.get_ancestry."""
441
if isinstance(version_ids, basestring):
442
version_ids = [version_ids]
443
i = self._inclusions([self._lookup(v) for v in version_ids])
444
return [self._idx_to_name(v) for v in i]
423
445
424
446
def _check_lines(self, text):
425
447
if not isinstance(text, list):
440
462
except IndexError:
441
463
raise IndexError("invalid version number %r" % i)
442
464
465
def _compatible_parents(self, my_parents, other_parents):
466
"""During join check that other_parents are joinable with my_parents.
467
468
Joinable is defined as 'is a subset of' - supersets may require
469
regeneration of diffs, but subsets do not.
470
"""
471
return len(other_parents.difference(my_parents)) == 0
472
473
def annotate(self, version_id):
474
if isinstance(version_id, int):
475
warn('Weave.annotate(int) is deprecated. Please use version names'
476
' in all circumstances as of 0.8',
477
DeprecationWarning,
478
stacklevel=2
479
)
480
result = []
481
for origin, lineno, text in self._extract([version_id]):
482
result.append((origin, text))
483
return result
484
else:
485
return super(Weave, self).annotate(version_id)
443
486
444
def annotate(self, name_or_index):
445
return list(self.annotate_iter(name_or_index))
446
447
448
def annotate_iter(self, name_or_index):
449
"""Yield list of (index-id, line) pairs for the specified version.
487
def annotate_iter(self, version_id):
488
"""Yield list of (version-id, line) pairs for the specified version.
450
489
451
490
The index indicates when the line originated in the weave."""
452
incls = [self.maybe_lookup(name_or_index)]
491
incls = [self._lookup(version_id)]
453
492
for origin, lineno, text in self._extract(incls):
454
yield origin, text
493
yield self._idx_to_name(origin), text
455
494
495
@deprecated_method(zero_eight)
456
496
def _walk(self):
457
"""Walk the weave.
458
459
Yields sequence of
460
(lineno, insert, deletes, text)
461
for each literal line.
462
"""
497
"""_walk has become visit, a supported api."""
498
return self._walk_internal()
499
500
def iter_lines_added_or_present_in_versions(self, version_ids=None):
501
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
502
if version_ids is None:
503
version_ids = self.versions()
504
version_ids = set(version_ids)
505
for lineno, inserted, deletes, line in self._walk_internal(version_ids):
506
# if inserted not in version_ids then it was inserted before the
507
# versions we care about, but because weaves cannot represent ghosts
508
# properly, we do not filter down to that
509
# if inserted not in version_ids: continue
510
if line[-1] != '\n':
511
yield line + '\n'
512
else:
513
yield line
514
515
#@deprecated_method(zero_eight)
516
def walk(self, version_ids=None):
517
"""See VersionedFile.walk."""
518
return self._walk_internal(version_ids)
519
520
def _walk_internal(self, version_ids=None):
521
"""Helper method for weave actions."""
463
522
464
523
istack = []
465
524
dset = set()
471
530
c, v = l
472
531
isactive = None
473
532
if c == '{':
474
istack.append(v)
533
istack.append(self._idx_to_name(v))
475
534
elif c == '}':
476
535
istack.pop()
477
536
elif c == '[':
478
assert v not in dset
479
dset.add(v)
537
assert self._idx_to_name(v) not in dset
538
dset.add(self._idx_to_name(v))
480
539
elif c == ']':
481
dset.remove(v)
540
dset.remove(self._idx_to_name(v))
482
541
else:
483
542
raise WeaveFormatError('unexpected instruction %r' % v)
484
543
else:
485
544
assert isinstance(l, basestring)
486
545
assert istack
487
yield lineno, istack[-1], dset, l
546
yield lineno, istack[-1], dset.copy(), l
488
547
lineno += 1
489
548
490
549
if istack:
507
566
if not isinstance(i, int):
508
567
raise ValueError(i)
509
568
510
included = self.inclusions(versions)
569
included = self._inclusions(versions)
511
570
512
571
istack = []
513
572
dset = set()
553
612
% dset)
554
613
return result
555
614
556
615
@deprecated_method(zero_eight)
557
616
def get_iter(self, name_or_index):
617
"""Deprecated, please do not use. Lookups are not not needed.
618
619
Please use get_lines now.
620
"""
621
return self._get_iter(self._maybe_lookup(name_or_index))
622
623
@deprecated_method(zero_eight)
624
def maybe_lookup(self, name_or_index):
625
"""Deprecated, please do not use. Lookups are not not needed."""
626
return self._maybe_lookup(name_or_index)
627
628
def _maybe_lookup(self, name_or_index):
629
"""Convert possible symbolic name to index, or pass through indexes.
630
631
NOT FOR PUBLIC USE.
632
"""
633
if isinstance(name_or_index, (int, long)):
634
return name_or_index
635
else:
636
return self._lookup(name_or_index)
637
638
def _get_iter(self, version_id):
558
639
"""Yield lines for the specified version."""
559
incls = [self.maybe_lookup(name_or_index)]
640
incls = [self._maybe_lookup(version_id)]
560
641
if len(incls) == 1:
561
642
index = incls[0]
562
643
cur_sha = sha.new()
576
657
% (self._weave_name, self._names[index],
577
658
expected_sha1, measured_sha1))
578
659
579
580
def get_text(self, name_or_index):
581
return ''.join(self.get_iter(name_or_index))
582
assert isinstance(version, int)
583
584
585
def get_lines(self, name_or_index):
586
return list(self.get_iter(name_or_index))
587
588
589
get = get_lines
590
660
@deprecated_method(zero_eight)
661
def get(self, version_id):
662
"""Please use either Weave.get_text or Weave.get_lines as desired."""
663
return self.get_lines(version_id)
664
665
def get_lines(self, version_id):
666
"""See VersionedFile.get_lines()."""
667
return list(self._get_iter(version_id))
591
668
592
669
def get_sha1(self, name):
593
670
"""Get the stored sha1 sum for the given revision.
594
671
595
672
:param name: The name of the version to lookup
596
673
"""
597
return self._sha1s[self.lookup(name)]
598
599
def mash_iter(self, included):
600
"""Return composed version of multiple included versions."""
601
included = map(self.maybe_lookup, included)
602
for origin, lineno, text in self._extract(included):
603
yield text
604
605
606
def dump(self, to_file):
607
from pprint import pprint
608
print >>to_file, "Weave._weave = ",
609
pprint(self._weave, to_file)
610
print >>to_file, "Weave._parents = ",
611
pprint(self._parents, to_file)
612
613
614
674
return self._sha1s[self._lookup(name)]
675
676
@deprecated_method(zero_eight)
615
677
def numversions(self):
678
"""How many versions are in this weave?
679
680
Deprecated in favour of num_versions.
681
"""
682
return self.num_versions()
683
684
def num_versions(self):
685
"""How many versions are in this weave?"""
616
686
l = len(self._parents)
617
687
assert l == len(self._sha1s)
618
688
return l
619
689
620
621
def __len__(self):
622
return self.numversions()
690
__len__ = num_versions
623
691
624
692
def check(self, progress_bar=None):
693
# TODO evaluate performance hit of using string sets in this routine.
625
694
# check no circular inclusions
626
for version in range(self.numversions()):
695
for version in range(self.num_versions()):
627
696
inclusions = list(self._parents[version])
628
697
if inclusions:
629
698
inclusions.sort()
632
701
% (inclusions[-1], version))
633
702
634
703
# try extracting all versions; parallel extraction is used
635
nv = self.numversions()
636
sha1s = [sha.new() for i in range(nv)]
637
texts = [[] for i in range(nv)]
638
inclusions = []
704
nv = self.num_versions()
705
sha1s = {}
706
texts = {}
707
inclusions = {}
639
708
for i in range(nv):
640
709
# For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
641
710
# The problem is that set membership is much more expensive
642
new_inc = set([i])
711
name = self._idx_to_name(i)
712
sha1s[name] = sha.new()
713
texts[name] = []
714
new_inc = set([name])
643
715
for p in self._parents[i]:
644
new_inc.update(inclusions[p])
716
new_inc.update(inclusions[self._idx_to_name(p)])
645
717
646
#assert set(new_inc) == self.inclusions([i]), 'failed %s != %s' % (new_inc, self.inclusions([i]))
647
inclusions.append(new_inc)
718
assert set(new_inc) == set(self.get_ancestry(name)), \
719
'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))
720
inclusions[name] = new_inc
648
721
649
722
nlines = len(self._weave)
650
723
654
727
update_text = 'checking %s' % (short_name,)
655
728
update_text = update_text[:25]
656
729
657
for lineno, insert, deleteset, line in self._walk():
730
for lineno, insert, deleteset, line in self._walk_internal():
658
731
if progress_bar:
659
732
progress_bar.update(update_text, lineno, nlines)
660
733
661
for j, j_inc in enumerate(inclusions):
734
for name, name_inclusions in inclusions.items():
662
735
# The active inclusion must be an ancestor,
663
736
# and no ancestors must have deleted this line,
664
737
# because we don't support resurrection.
665
if (insert in j_inc) and not (deleteset & j_inc):
666
sha1s[j].update(line)
738
if (insert in name_inclusions) and not (deleteset & name_inclusions):
739
sha1s[name].update(line)
667
740
668
for version in range(nv):
741
for i in range(nv):
742
version = self._idx_to_name(i)
669
743
hd = sha1s[version].hexdigest()
670
expected = self._sha1s[version]
744
expected = self._sha1s[i]
671
745
if hd != expected:
672
746
raise errors.WeaveInvalidChecksum(
673
747
"mismatched sha1 for version %s: "
674
748
"got %s, expected %s"
675
% (self._names[version], hd, expected))
749
% (version, hd, expected))
676
750
677
751
# TODO: check insertions are properly nested, that there are
678
752
# no lines outside of insertion blocks, that deletions are
679
753
# properly paired, etc.
680
754
681
def _delta(self, included, lines):
682
"""Return changes from basis to new revision.
683
684
The old text for comparison is the union of included revisions.
685
686
This is used in inserting a new text.
687
688
Delta is returned as a sequence of
689
(weave1, weave2, newlines).
690
691
This indicates that weave1:weave2 of the old weave should be
692
replaced by the sequence of lines in newlines. Note that
693
these line numbers are positions in the total weave and don't
694
correspond to the lines in any extracted version, or even the
695
extracted union of included versions.
696
697
If line1=line2, this is a pure insert; if newlines=[] this is a
698
pure delete. (Similar to difflib.)
699
"""
700
raise NotImplementedError()
701
702
703
def plan_merge(self, ver_a, ver_b):
704
"""Return pseudo-annotation indicating how the two versions merge.
705
706
This is computed between versions a and b and their common
707
base.
708
709
Weave lines present in none of them are skipped entirely.
710
"""
711
inc_a = self.inclusions([ver_a])
712
inc_b = self.inclusions([ver_b])
713
inc_c = inc_a & inc_b
714
715
for lineno, insert, deleteset, line in self._walk():
716
if deleteset & inc_c:
717
# killed in parent; can't be in either a or b
718
# not relevant to our work
719
yield 'killed-base', line
720
elif insert in inc_c:
721
# was inserted in base
722
killed_a = bool(deleteset & inc_a)
723
killed_b = bool(deleteset & inc_b)
724
if killed_a and killed_b:
725
yield 'killed-both', line
726
elif killed_a:
727
yield 'killed-a', line
728
elif killed_b:
729
yield 'killed-b', line
730
else:
731
yield 'unchanged', line
732
elif insert in inc_a:
733
if deleteset & inc_a:
734
yield 'ghost-a', line
735
else:
736
# new in A; not in B
737
yield 'new-a', line
738
elif insert in inc_b:
739
if deleteset & inc_b:
740
yield 'ghost-b', line
741
else:
742
yield 'new-b', line
743
else:
744
# not in either revision
745
yield 'irrelevant', line
746
747
yield 'unchanged', '' # terminator
748
749
750
751
def weave_merge(self, plan, a_marker='<<<<<<< \n', b_marker='>>>>>>> \n'):
752
lines_a = []
753
lines_b = []
754
ch_a = ch_b = False
755
# TODO: Return a structured form of the conflicts (e.g. 2-tuples for
756
# conflicted regions), rather than just inserting the markers.
757
#
758
# TODO: Show some version information (e.g. author, date) on
759
# conflicted regions.
760
for state, line in plan:
761
if state == 'unchanged' or state == 'killed-both':
762
# resync and flush queued conflicts changes if any
763
if not lines_a and not lines_b:
764
pass
765
elif ch_a and not ch_b:
766
# one-sided change:
767
for l in lines_a: yield l
768
elif ch_b and not ch_a:
769
for l in lines_b: yield l
770
elif lines_a == lines_b:
771
for l in lines_a: yield l
772
else:
773
yield a_marker
774
for l in lines_a: yield l
775
yield '=======\n'
776
for l in lines_b: yield l
777
yield b_marker
778
779
del lines_a[:]
780
del lines_b[:]
781
ch_a = ch_b = False
782
783
if state == 'unchanged':
784
if line:
785
yield line
786
elif state == 'killed-a':
787
ch_a = True
788
lines_b.append(line)
789
elif state == 'killed-b':
790
ch_b = True
791
lines_a.append(line)
792
elif state == 'new-a':
793
ch_a = True
794
lines_a.append(line)
795
elif state == 'new-b':
796
ch_b = True
797
lines_b.append(line)
798
else:
799
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
800
'killed-both'), \
801
state
802
803
804
def join(self, other, pb=None, msg=None):
805
import sys, time
806
"""Integrate versions from other into this weave.
807
808
The resulting weave contains all the history of both weaves;
809
any version you could retrieve from either self or other can be
810
retrieved from self after this call.
811
812
It is illegal for the two weaves to contain different values
813
or different parents for any version. See also reweave().
814
815
:param other: The other weave to pull into this one
816
:param pb: An optional progress bar
817
:param msg: An optional message to display for progress
818
"""
819
if other.numversions() == 0:
755
def _join(self, other, pb, msg, version_ids, ignore_missing):
756
"""Worker routine for join()."""
757
if not other.versions():
820
758
return # nothing to update, easy
759
760
if version_ids:
761
for version_id in version_ids:
762
if not other.has_version(version_id) and not ignore_missing:
763
raise RevisionNotPresent(version_id, self._weave_name)
764
else:
765
version_ids = other.versions()
766
821
767
# two loops so that we do not change ourselves before verifying it
822
768
# will be ok
823
769
# work through in index order to make sure we get all dependencies
824
770
names_to_join = []
825
771
processed = 0
826
for other_idx, name in enumerate(other._names):
772
# get the selected versions only that are in other.versions.
773
version_ids = set(other.versions()).intersection(set(version_ids))
774
# pull in the referenced graph.
775
version_ids = other.get_ancestry(version_ids)
776
pending_graph = [(version, other.get_parents(version)) for
777
version in version_ids]
778
for name in topo_sort(pending_graph):
779
other_idx = other._name_map[name]
827
780
self._check_version_consistent(other, other_idx, name)
828
781
sha1 = other._sha1s[other_idx]
829
782
830
783
processed += 1
831
784
832
785
if name in self._name_map:
833
idx = self.lookup(name)
834
n1 = set(map(other.idx_to_name, other._parents[other_idx]))
835
n2 = set(map(self.idx_to_name, self._parents[idx]))
786
idx = self._lookup(name)
787
n1 = set(map(other._idx_to_name, other._parents[other_idx]))
788
n2 = set(map(self._idx_to_name, self._parents[idx]))
836
789
if sha1 == self._sha1s[idx] and n1 == n2:
837
790
continue
838
791
842
795
msg = 'weave join'
843
796
844
797
merged = 0
845
time0 = time.time( )
798
time0 = time.time()
846
799
for other_idx, name in names_to_join:
847
800
# TODO: If all the parents of the other version are already
848
801
# present then we can avoid some work by just taking the delta
856
809
pb.update(msg, merged, len(names_to_join))
857
810
858
811
lines = other.get_lines(other_idx)
859
self.add(name, new_parents, lines, sha1)
812
self._add(name, lines, new_parents, sha1)
860
813
861
814
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
862
merged, processed, self._weave_name, time.time( )-time0))
815
merged, processed, self._weave_name, time.time()-time0))
863
816
864
817
def _imported_parents(self, other, other_idx):
865
818
"""Return list of parents in self corresponding to indexes in other."""
888
841
this_idx = self._name_map.get(name, -1)
889
842
if this_idx != -1:
890
843
if self._sha1s[this_idx] != other._sha1s[other_idx]:
891
raise WeaveError("inconsistent texts for version {%s} "
892
"when joining weaves"
893
% (name))
844
raise errors.WeaveTextDiffers(name, self, other)
894
845
self_parents = self._parents[this_idx]
895
846
other_parents = other._parents[other_idx]
896
847
n1 = set([self._names[i] for i in self_parents])
897
848
n2 = set([other._names[i] for i in other_parents])
898
if n1 != n2:
849
if not self._compatible_parents(n1, n2):
899
850
raise WeaveParentMismatch("inconsistent parents "
900
851
"for version {%s}: %s vs %s" % (name, n1, n2))
901
852
else:
903
854
else:
904
855
return False
905
856
857
@deprecated_method(zero_eight)
906
858
def reweave(self, other, pb=None, msg=None):
907
"""Reweave self with other.
859
"""reweave has been superceded by plain use of join."""
860
return self.join(other, pb, msg)
861
862
def _reweave(self, other, pb, msg):
863
"""Reweave self with other - internal helper for join().
908
864
909
865
:param other: The other weave to merge
910
866
:param pb: An optional progress bar, indicating how far done we are
911
867
:param msg: An optional message for the progress
912
868
"""
913
new_weave = reweave(self, other, pb=pb, msg=msg)
869
new_weave = _reweave(self, other, pb=pb, msg=msg)
870
self._copy_weave_content(new_weave)
871
872
def _copy_weave_content(self, otherweave):
873
"""adsorb the content from otherweave."""
914
874
for attr in self.__slots__:
915
setattr(self, attr, getattr(new_weave, attr))
916
917
875
if attr != '_weave_name':
876
setattr(self, attr, copy(getattr(otherweave, attr)))
877
878
879
class WeaveFile(Weave):
880
"""A WeaveFile represents a Weave on disk and writes on change."""
881
882
WEAVE_SUFFIX = '.weave'
883
884
def __init__(self, name, transport, filemode=None, create=False, access_mode='w'):
885
"""Create a WeaveFile.
886
887
:param create: If not True, only open an existing knit.
888
"""
889
super(WeaveFile, self).__init__(name, access_mode)
890
self._transport = transport
891
self._filemode = filemode
892
try:
893
_read_weave_v5(self._transport.get(name + WeaveFile.WEAVE_SUFFIX), self)
894
except errors.NoSuchFile:
895
if not create:
896
raise
897
# new file, save it
898
self._save()
899
900
def _add_lines(self, version_id, parents, lines):
901
"""Add a version and save the weave."""
902
super(WeaveFile, self)._add_lines(version_id, parents, lines)
903
self._save()
904
905
def _clone_text(self, new_version_id, old_version_id, parents):
906
"""See VersionedFile.clone_text."""
907
super(WeaveFile, self)._clone_text(new_version_id, old_version_id, parents)
908
self._save
909
910
def copy_to(self, name, transport):
911
"""See VersionedFile.copy_to()."""
912
# as we are all in memory always, just serialise to the new place.
913
sio = StringIO()
914
write_weave_v5(self, sio)
915
sio.seek(0)
916
transport.put(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
917
918
def create_empty(self, name, transport, filemode=None):
919
return WeaveFile(name, transport, filemode, create=True)
920
921
def _save(self):
922
"""Save the weave."""
923
self._check_write_ok()
924
sio = StringIO()
925
write_weave_v5(self, sio)
926
sio.seek(0)
927
self._transport.put(self._weave_name + WeaveFile.WEAVE_SUFFIX,
928
sio,
929
self._filemode)
930
931
@staticmethod
932
def get_suffixes():
933
"""See VersionedFile.get_suffixes()."""
934
return [WeaveFile.WEAVE_SUFFIX]
935
936
def join(self, other, pb=None, msg=None, version_ids=None,
937
ignore_missing=False):
938
"""Join other into self and save."""
939
super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
940
self._save()
941
942
943
@deprecated_function(zero_eight)
918
944
def reweave(wa, wb, pb=None, msg=None):
945
"""reweaving is deprecation, please just use weave.join()."""
946
_reweave(wa, wb, pb, msg)
947
948
def _reweave(wa, wb, pb=None, msg=None):
919
949
"""Combine two weaves and return the result.
920
950
921
951
This works even if a revision R has different parents in
932
962
"""
933
963
wr = Weave()
934
964
ia = ib = 0
935
queue_a = range(wa.numversions())
936
queue_b = range(wb.numversions())
965
queue_a = range(wa.num_versions())
966
queue_b = range(wb.num_versions())
937
967
# first determine combined parents of all versions
938
968
# map from version name -> all parent names
939
969
combined_parents = _reweave_parent_graphs(wa, wb)
961
991
raise errors.WeaveTextDiffers(name, wa, wb)
962
992
else:
963
993
lines = wb.get_lines(name)
964
wr.add(name, combined_parents[name], lines)
994
wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
965
995
return wr
966
996
967
968
997
def _reweave_parent_graphs(wa, wb):
969
998
"""Return combined parent ancestry for two weaves.
970
999
973
1002
for weave in [wa, wb]:
974
1003
for idx, name in enumerate(weave._names):
975
1004
p = combined.setdefault(name, set())
976
p.update(map(weave.idx_to_name, weave._parents[idx]))
1005
p.update(map(weave._idx_to_name, weave._parents[idx]))
977
1006
return combined
978
1007
979
1008
983
1012
for i in (6, 50, 10, 10):
984
1013
print '-' * i,
985
1014
print
986
for i in range(w.numversions()):
1015
for i in range(w.num_versions()):
987
1016
sha1 = w._sha1s[i]
988
1017
name = w._names[i]
989
1018
parent_str = ' '.join(map(str, w._parents[i]))
995
1024
from bzrlib.weavefile import read_weave
996
1025
997
1026
wf = file(weave_file, 'rb')
998
w = read_weave(wf)
1027
w = read_weave(wf, WeaveVersionedFile)
999
1028
# FIXME: doesn't work on pipes
1000
1029
weave_size = wf.tell()
1001
1030
1036
1065
Add NEWTEXT, with specified parent versions.
1037
1066
weave annotate WEAVEFILE VERSION
1038
1067
Display origin of each line.
1039
weave mash WEAVEFILE VERSION...
1040
Display composite of all selected versions.
1041
1068
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
1042
1069
Auto-merge two versions and display conflicts.
1043
1070
weave diff WEAVEFILE VERSION1 VERSION2
1117
1144
w = readit()
1118
1145
sys.stdout.writelines(w.get_iter(int(argv[3])))
1119
1146
1120
elif cmd == 'mash': # get composite
1121
w = readit()
1122
sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
1123
1124
1147
elif cmd == 'diff':
1125
1148
from difflib import unified_diff
1126
1149
w = readit()
1157
1180
pb = ProgressBar()
1158
1181
w.check(pb)
1159
1182
pb.clear()
1160
print '%d versions ok' % w.numversions()
1183
print '%d versions ok' % w.num_versions()
1161
1184
1162
1185
elif cmd == 'inclusions':
1163
1186
w = readit()
1178
1201
p = w.plan_merge(int(argv[3]), int(argv[4]))
1179
1202
sys.stdout.writelines(w.weave_merge(p))
1180
1203
1181
elif cmd == 'mash-merge':
1182
if len(argv) != 5:
1183
usage()
1184
return 1
1185
1186
w = readit()
1187
v1, v2 = map(int, argv[3:5])
1188
1189
basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
1190
1191
base_lines = list(w.mash_iter(basis))
1192
a_lines = list(w.get(v1))
1193
b_lines = list(w.get(v2))
1194
1195
from bzrlib.merge3 import Merge3
1196
m3 = Merge3(base_lines, a_lines, b_lines)
1197
1198
name_a = 'version %d' % v1
1199
name_b = 'version %d' % v2
1200
sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
1201
1204
else:
1202
1205
raise ValueError('unknown command %r' % cmd)
1203
1206
1244
1247
else:
1245
1248
sys.exit(main(sys.argv))
1246
1249
1250
1251
class InterWeave(InterVersionedFile):
1252
"""Optimised code paths for weave to weave operations."""
1253
1254
_matching_file_factory = staticmethod(WeaveFile)
1255
1256
@staticmethod
1257
def is_compatible(source, target):
1258
"""Be compatible with weaves."""
1259
try:
1260
return (isinstance(source, Weave) and
1261
isinstance(target, Weave))
1262
except AttributeError:
1263
return False
1264
1265
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1266
"""See InterVersionedFile.join."""
1267
if self.target.versions() == []:
1268
# optimised copy
1269
self.target._copy_weave_content(self.source)
1270
return
1271
try:
1272
self.target._join(self.source, pb, msg, version_ids, ignore_missing)
1273
except errors.WeaveParentMismatch:
1274
self.target._reweave(self.source, pb, msg)
1275
1276
1277
InterVersionedFile.register_optimiser(InterWeave)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1