71
69
from copy import copy
72
70
from cStringIO import StringIO
78
from bzrlib.trace import mutter
75
from bzrlib.lazy_import import lazy_import
76
lazy_import(globals(), """
77
from bzrlib import tsort
79
84
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
80
85
RevisionAlreadyPresent,
81
86
RevisionNotPresent,
87
UnavailableRepresentation,
82
88
WeaveRevisionAlreadyPresent,
83
89
WeaveRevisionNotPresent,
85
import bzrlib.errors as errors
86
from bzrlib.osutils import sha_strings
91
from bzrlib.osutils import dirname, sha, sha_strings, split_lines
87
92
import bzrlib.patiencediff
88
from bzrlib.symbol_versioning import (deprecated_method,
92
from bzrlib.tsort import topo_sort
93
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
93
from bzrlib.revision import NULL_REVISION
94
from bzrlib.symbol_versioning import *
95
from bzrlib.trace import mutter
96
from bzrlib.versionedfile import (
94
103
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
106
class WeaveContentFactory(ContentFactory):
107
"""Content factory for streaming from weaves.
109
:seealso ContentFactory:
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'
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])
128
raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
97
131
class Weave(VersionedFile):
98
132
"""weave - versioned text file storage.
100
134
A Weave manages versions of line-based text files, keeping track
101
135
of the originating version for each line.
221
275
return self._parents == other._parents \
222
276
and self._weave == other._weave \
223
and self._sha1s == other._sha1s
277
and self._sha1s == other._sha1s
225
279
def __ne__(self, other):
226
280
return not self.__eq__(other)
228
@deprecated_method(zero_eight)
229
def idx_to_name(self, index):
230
"""Old public interface, the public interface is all names now."""
233
282
def _idx_to_name(self, version):
234
283
return self._names[version]
236
@deprecated_method(zero_eight)
237
def lookup(self, name):
238
"""Backwards compatibility thunk:
240
Return name, as name is valid in the api now, and spew deprecation
245
285
def _lookup(self, name):
246
286
"""Convert symbolic version name to index."""
287
if not self._allow_reserved:
288
self.check_not_reserved_id(name)
248
290
return self._name_map[name]
250
292
raise RevisionNotPresent(name, self._weave_name)
252
@deprecated_method(zero_eight)
253
def iter_names(self):
254
"""Deprecated convenience function, please see VersionedFile.names()."""
255
return iter(self.names())
257
@deprecated_method(zero_eight)
259
"""See Weave.versions for the current api."""
260
return self.versions()
262
294
def versions(self):
263
295
"""See VersionedFile.versions."""
264
296
return self._names[:]
266
298
def has_version(self, version_id):
267
299
"""See VersionedFile.has_version."""
268
return self._name_map.has_key(version_id)
300
return (version_id in self._name_map)
270
302
__contains__ = has_version
272
def get_delta(self, version_id):
273
"""See VersionedFile.get_delta."""
274
return self.get_deltas([version_id])[version_id]
276
def get_deltas(self, version_ids):
277
"""See VersionedFile.get_deltas."""
278
version_ids = self.get_ancestry(version_ids)
304
def get_record_stream(self, versions, ordering, include_delta_closure):
305
"""Get a stream of records for versions.
307
:param versions: The versions to include. Each version is a tuple
309
:param ordering: Either 'unordered' or 'topological'. A topologically
310
sorted stream has compression parents strictly before their
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.
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:
330
yield WeaveContentFactory(version, self)
332
yield AbsentContentFactory((version,))
334
def get_parent_map(self, version_ids):
335
"""See VersionedFile.get_parent_map."""
279
337
for version_id in version_ids:
280
if not self.has_version(version_id):
281
raise RevisionNotPresent(version_id, self)
282
# try extracting all versions; parallel extraction is used
283
nv = self.num_versions()
289
last_parent_lines = {}
291
parent_inclusions = {}
296
# its simplest to generate a full set of prepared variables.
298
name = self._names[i]
299
sha1s[name] = self.get_sha1(name)
300
parents_list = self.get_parents(name)
302
parent = parents_list[0]
303
parents[name] = parent
304
parent_inclusions[name] = inclusions[parent]
307
parent_inclusions[name] = set()
308
# we want to emit start, finish, replacement_length, replacement_lines tuples.
309
diff_hunks[name] = []
310
current_hunks[name] = [0, 0, 0, []] # #start, finish, repl_length, repl_tuples
311
parent_linenums[name] = 0
313
parent_noeols[name] = False
314
last_parent_lines[name] = None
315
new_inc = set([name])
316
for p in self._parents[i]:
317
new_inc.update(inclusions[self._idx_to_name(p)])
318
# debug only, known good so far.
319
#assert set(new_inc) == set(self.get_ancestry(name)), \
320
# 'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))
321
inclusions[name] = new_inc
323
nlines = len(self._weave)
325
for lineno, inserted, deletes, line in self._walk_internal():
326
# a line is active in a version if:
327
# insert is in the versions inclusions
329
# deleteset & the versions inclusions is an empty set.
330
# so - if we have a included by mapping - version is included by
331
# children, we get a list of children to examine for deletes affect
332
# ing them, which is less than the entire set of children.
333
for version_id in version_ids:
334
# The active inclusion must be an ancestor,
335
# and no ancestors must have deleted this line,
336
# because we don't support resurrection.
337
parent_inclusion = parent_inclusions[version_id]
338
inclusion = inclusions[version_id]
339
parent_active = inserted in parent_inclusion and not (deletes & parent_inclusion)
340
version_active = inserted in inclusion and not (deletes & inclusion)
341
if not parent_active and not version_active:
342
# unrelated line of ancestry
338
if version_id == NULL_REVISION:
343
map(self._idx_to_name,
344
self._parents[self._lookup(version_id)]))
345
except RevisionNotPresent:
344
elif parent_active and version_active:
346
parent_linenum = parent_linenums[version_id]
347
if current_hunks[version_id] != [parent_linenum, parent_linenum, 0, []]:
348
diff_hunks[version_id].append(tuple(current_hunks[version_id]))
350
current_hunks[version_id] = [parent_linenum, parent_linenum, 0, []]
351
parent_linenums[version_id] = parent_linenum
354
noeols[version_id] = True
357
elif parent_active and not version_active:
359
current_hunks[version_id][1] += 1
360
parent_linenums[version_id] += 1
361
last_parent_lines[version_id] = line
362
elif not parent_active and version_active:
364
# noeol only occurs at the end of a file because we
365
# diff linewise. We want to show noeol changes as a
366
# empty diff unless the actual eol-less content changed.
369
if last_parent_lines[version_id][-1] != '\n':
370
parent_noeols[version_id] = True
371
except (TypeError, IndexError):
374
if theline[-1] != '\n':
375
noeols[version_id] = True
379
parent_should_go = False
381
if parent_noeols[version_id] == noeols[version_id]:
382
# no noeol toggle, so trust the weaves statement
383
# that this line is changed.
385
if parent_noeols[version_id]:
386
theline = theline + '\n'
387
elif parent_noeols[version_id]:
388
# parent has no eol, we do:
389
# our line is new, report as such..
391
elif noeols[version_id]:
392
# append a eol so that it looks like
394
theline = theline + '\n'
395
if parents[version_id] is not None:
396
#if last_parent_lines[version_id] is not None:
397
parent_should_go = True
398
if last_parent_lines[version_id] != theline:
401
#parent_should_go = False
403
current_hunks[version_id][2] += 1
404
current_hunks[version_id][3].append((inserted, theline))
406
# last hunk last parent line is not eaten
407
current_hunks[version_id][1] -= 1
408
if current_hunks[version_id][1] < 0:
409
current_hunks[version_id][1] = 0
410
# import pdb;pdb.set_trace()
411
# assert current_hunks[version_id][1] >= 0
415
version = self._idx_to_name(i)
416
if current_hunks[version] != [0, 0, 0, []]:
417
diff_hunks[version].append(tuple(current_hunks[version]))
419
for version_id in version_ids:
420
result[version_id] = (
424
diff_hunks[version_id],
347
result[version_id] = parents
428
def get_parents(self, version_id):
429
"""See VersionedFile.get_parent."""
430
return map(self._idx_to_name, self._parents[self._lookup(version_id)])
350
def get_parents_with_ghosts(self, version_id):
351
raise NotImplementedError(self.get_parents_with_ghosts)
353
def insert_record_stream(self, stream):
354
"""Insert a record stream into this versioned file.
356
:param stream: A stream of records to insert.
358
:seealso VersionedFile.get_record_stream:
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')))
372
adapter_key = record.storage_kind, 'fulltext'
374
adapter = adapters[adapter_key]
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))
381
self.add_lines(record.key[0], parents, lines)
382
except RevisionAlreadyPresent:
432
385
def _check_repeated_add(self, name, parents, text, sha1):
433
386
"""Check that a duplicated add is OK.
440
393
raise RevisionAlreadyPresent(name, self._weave_name)
443
@deprecated_method(zero_eight)
444
def add_identical(self, old_rev_id, new_rev_id, parents):
445
"""Please use Weave.clone_text now."""
446
return self.clone_text(new_rev_id, old_rev_id, parents)
448
def _add_lines(self, version_id, parents, lines, parent_texts):
396
def _add_lines(self, version_id, parents, lines, parent_texts,
397
left_matching_blocks, nostore_sha, random_id, check_content):
449
398
"""See VersionedFile.add_lines."""
450
return self._add(version_id, lines, map(self._lookup, parents))
452
@deprecated_method(zero_eight)
453
def add(self, name, parents, text, sha1=None):
454
"""See VersionedFile.add_lines for the non deprecated api."""
455
return self._add(name, text, map(self._maybe_lookup, parents), sha1)
457
def _add(self, version_id, lines, parents, sha1=None):
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
403
def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
458
404
"""Add a single text on top of the weave.
460
406
Returns the index number of the newly added version.
463
409
Symbolic name for this version.
464
410
(Typically the revision-id of the revision that added it.)
411
If None, a name will be allocated based on the hash. (sha1:SHAHASH)
467
414
List or set of direct parent version numbers.
470
417
Sequence of lines to be added in the new version.
419
:param nostore_sha: See VersionedFile.add_lines.
473
assert isinstance(version_id, basestring)
474
421
self._check_lines_not_unicode(lines)
475
422
self._check_lines_are_lines(lines)
477
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
478
429
if version_id in self._name_map:
479
430
return self._check_repeated_add(version_id, parents, lines, sha1)
632
562
def _compatible_parents(self, my_parents, other_parents):
633
563
"""During join check that other_parents are joinable with my_parents.
635
Joinable is defined as 'is a subset of' - supersets may require
565
Joinable is defined as 'is a subset of' - supersets may require
636
566
regeneration of diffs, but subsets do not.
638
568
return len(other_parents.difference(my_parents)) == 0
640
570
def annotate(self, version_id):
641
if isinstance(version_id, int):
642
warnings.warn('Weave.annotate(int) is deprecated. Please use version names'
643
' in all circumstances as of 0.8',
648
for origin, lineno, text in self._extract([version_id]):
649
result.append((origin, text))
652
return super(Weave, self).annotate(version_id)
654
def annotate_iter(self, version_id):
655
"""Yield list of (version-id, line) pairs for the specified version.
571
"""Return a list of (version-id, line) tuples for version_id.
657
573
The index indicates when the line originated in the weave."""
658
574
incls = [self._lookup(version_id)]
659
for origin, lineno, text in self._extract(incls):
660
yield self._idx_to_name(origin), text
662
@deprecated_method(zero_eight)
664
"""_walk has become visit, a supported api."""
665
return self._walk_internal()
667
def iter_lines_added_or_present_in_versions(self, version_ids=None):
575
return [(self._idx_to_name(origin), text) for origin, lineno, text in
576
self._extract(incls)]
578
def iter_lines_added_or_present_in_versions(self, version_ids=None,
668
580
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
669
581
if version_ids is None:
670
582
version_ids = self.versions()
671
583
version_ids = set(version_ids)
672
584
for lineno, inserted, deletes, line in self._walk_internal(version_ids):
673
# if inserted not in version_ids then it was inserted before the
674
# versions we care about, but because weaves cannot represent ghosts
675
# properly, we do not filter down to that
676
# if inserted not in version_ids: continue
585
if inserted not in version_ids: continue
677
586
if line[-1] != '\n':
587
yield line + '\n', inserted
682
#@deprecated_method(zero_eight)
683
def walk(self, version_ids=None):
684
"""See VersionedFile.walk."""
685
return self._walk_internal(version_ids)
687
591
def _walk_internal(self, version_ids=None):
688
592
"""Helper method for weave actions."""
980
853
# no lines outside of insertion blocks, that deletions are
981
854
# properly paired, etc.
983
def _join(self, other, pb, msg, version_ids, ignore_missing):
984
"""Worker routine for join()."""
985
if not other.versions():
986
return # nothing to update, easy
989
# versions is never none, InterWeave checks this.
992
# two loops so that we do not change ourselves before verifying it
994
# work through in index order to make sure we get all dependencies
997
# get the selected versions only that are in other.versions.
998
version_ids = set(other.versions()).intersection(set(version_ids))
999
# pull in the referenced graph.
1000
version_ids = other.get_ancestry(version_ids)
1001
pending_graph = [(version, other.get_parents(version)) for
1002
version in version_ids]
1003
for name in topo_sort(pending_graph):
1004
other_idx = other._name_map[name]
1005
# returns True if we have it, False if we need it.
1006
if not self._check_version_consistent(other, other_idx, name):
1007
names_to_join.append((other_idx, name))
1016
for other_idx, name in names_to_join:
1017
# TODO: If all the parents of the other version are already
1018
# present then we can avoid some work by just taking the delta
1019
# and adjusting the offsets.
1020
new_parents = self._imported_parents(other, other_idx)
1021
sha1 = other._sha1s[other_idx]
1026
pb.update(msg, merged, len(names_to_join))
1028
lines = other.get_lines(other_idx)
1029
self._add(name, lines, new_parents, sha1)
1031
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
1032
merged, processed, self._weave_name, time.time()-time0))
1034
856
def _imported_parents(self, other, other_idx):
1035
857
"""Return list of parents in self corresponding to indexes in other."""
1036
858
new_parents = []
1143
956
sio = StringIO()
1144
957
write_weave_v5(self, sio)
1146
self._transport.put(self._weave_name + WeaveFile.WEAVE_SUFFIX,
959
bytes = sio.getvalue()
960
path = self._weave_name + WeaveFile.WEAVE_SUFFIX
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)
1151
968
def get_suffixes():
1152
969
"""See VersionedFile.get_suffixes()."""
1153
970
return [WeaveFile.WEAVE_SUFFIX]
1155
def join(self, other, pb=None, msg=None, version_ids=None,
1156
ignore_missing=False):
1157
"""Join other into self and save."""
1158
super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
972
def insert_record_stream(self, stream):
973
super(WeaveFile, self).insert_record_stream(stream)
1162
@deprecated_function(zero_eight)
1163
def reweave(wa, wb, pb=None, msg=None):
1164
"""reweaving is deprecation, please just use weave.join()."""
1165
_reweave(wa, wb, pb, msg)
1167
977
def _reweave(wa, wb, pb=None, msg=None):
1168
978
"""Combine two weaves and return the result.
1170
This works even if a revision R has different parents in
980
This works even if a revision R has different parents in
1171
981
wa and wb. In the resulting weave all the parents are given.
1173
This is done by just building up a new weave, maintaining ordering
983
This is done by just building up a new weave, maintaining ordering
1174
984
of the versions in the two inputs. More efficient approaches
1175
might be possible but it should only be necessary to do
1176
this operation rarely, when a new previously ghost version is
985
might be possible but it should only be necessary to do
986
this operation rarely, when a new previously ghost version is
1179
989
:param pb: An optional progress bar, indicating how far done we are
1223
1034
p = combined.setdefault(name, set())
1224
1035
p.update(map(weave._idx_to_name, weave._parents[idx]))
1225
1036
return combined
1229
"""Show the weave's table-of-contents"""
1230
print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
1231
for i in (6, 50, 10, 10):
1234
for i in range(w.num_versions()):
1237
parent_str = ' '.join(map(str, w._parents[i]))
1238
print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
1242
def weave_stats(weave_file, pb):
1243
from bzrlib.weavefile import read_weave
1245
wf = file(weave_file, 'rb')
1247
# FIXME: doesn't work on pipes
1248
weave_size = wf.tell()
1252
for i in range(vers):
1253
pb.update('checking sizes', i, vers)
1254
for origin, lineno, line in w._extract([i]):
1259
print 'versions %9d' % vers
1260
print 'weave file %9d bytes' % weave_size
1261
print 'total contents %9d bytes' % total
1262
print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
1265
print 'average size %9d bytes' % avg
1266
print 'relative size %9.2fx' % (float(weave_size) / float(avg))
1270
print """bzr weave tool
1272
Experimental tool for weave algorithm.
1275
weave init WEAVEFILE
1276
Create an empty weave file
1277
weave get WEAVEFILE VERSION
1278
Write out specified version.
1279
weave check WEAVEFILE
1280
Check consistency of all versions.
1282
Display table of contents.
1283
weave add WEAVEFILE NAME [BASE...] < NEWTEXT
1284
Add NEWTEXT, with specified parent versions.
1285
weave annotate WEAVEFILE VERSION
1286
Display origin of each line.
1287
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
1288
Auto-merge two versions and display conflicts.
1289
weave diff WEAVEFILE VERSION1 VERSION2
1290
Show differences between two versions.
1294
% weave init foo.weave
1296
% weave add foo.weave ver0 < foo.txt
1299
(create updated version)
1301
% weave get foo.weave 0 | diff -u - foo.txt
1302
% weave add foo.weave ver1 0 < foo.txt
1305
% weave get foo.weave 0 > foo.txt (create forked version)
1307
% weave add foo.weave ver2 0 < foo.txt
1310
% weave merge foo.weave 1 2 > foo.txt (merge them)
1311
% vi foo.txt (resolve conflicts)
1312
% weave add foo.weave merged 1 2 < foo.txt (commit merged version)
1324
# in case we're run directly from the subdirectory
1325
sys.path.append('..')
1327
from bzrlib.weavefile import write_weave, read_weave
1328
from bzrlib.progress import ProgressBar
1343
return read_weave(file(argv[2], 'rb'))
1349
# at the moment, based on everything in the file
1351
parents = map(int, argv[4:])
1352
lines = sys.stdin.readlines()
1353
ver = w.add(name, parents, lines)
1354
write_weave(w, file(argv[2], 'wb'))
1355
print 'added version %r %d' % (name, ver)
1358
if os.path.exists(fn):
1359
raise IOError("file exists")
1361
write_weave(w, file(fn, 'wb'))
1362
elif cmd == 'get': # get one version
1364
sys.stdout.writelines(w.get_iter(int(argv[3])))
1369
v1, v2 = map(int, argv[3:5])
1372
diff_gen = bzrlib.patiencediff.unified_diff(lines1, lines2,
1373
'%s version %d' % (fn, v1),
1374
'%s version %d' % (fn, v2))
1375
sys.stdout.writelines(diff_gen)
1377
elif cmd == 'annotate':
1379
# newline is added to all lines regardless; too hard to get
1380
# reasonable formatting otherwise
1382
for origin, text in w.annotate(int(argv[3])):
1383
text = text.rstrip('\r\n')
1385
print ' | %s' % (text)
1387
print '%5d | %s' % (origin, text)
1393
elif cmd == 'stats':
1394
weave_stats(argv[2], ProgressBar())
1396
elif cmd == 'check':
1401
print '%d versions ok' % w.num_versions()
1403
elif cmd == 'inclusions':
1405
print ' '.join(map(str, w.inclusions([int(argv[3])])))
1407
elif cmd == 'parents':
1409
print ' '.join(map(str, w._parents[int(argv[3])]))
1411
elif cmd == 'plan-merge':
1412
# replaced by 'bzr weave-plan-merge'
1414
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
1416
print '%14s | %s' % (state, line),
1417
elif cmd == 'merge':
1418
# replaced by 'bzr weave-merge-text'
1420
p = w.plan_merge(int(argv[3]), int(argv[4]))
1421
sys.stdout.writelines(w.weave_merge(p))
1423
raise ValueError('unknown command %r' % cmd)
1426
if __name__ == '__main__':
1428
sys.exit(main(sys.argv))
1431
class InterWeave(InterVersionedFile):
1432
"""Optimised code paths for weave to weave operations."""
1434
_matching_file_from_factory = staticmethod(WeaveFile)
1435
_matching_file_to_factory = staticmethod(WeaveFile)
1438
def is_compatible(source, target):
1439
"""Be compatible with weaves."""
1441
return (isinstance(source, Weave) and
1442
isinstance(target, Weave))
1443
except AttributeError:
1446
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1447
"""See InterVersionedFile.join."""
1448
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1449
if self.target.versions() == [] and version_ids is None:
1450
self.target._copy_weave_content(self.source)
1453
self.target._join(self.source, pb, msg, version_ids, ignore_missing)
1454
except errors.WeaveParentMismatch:
1455
self.target._reweave(self.source, pb, msg)
1458
InterVersionedFile.register_optimiser(InterWeave)
added
removed
bzrlib/weave.py
