69
71
from copy import copy
70
72
from cStringIO import StringIO
73
from bzrlib.lazy_import import lazy_import
74
lazy_import(globals(), """
75
from bzrlib import tsort
78
from bzrlib.trace import mutter
81
79
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
82
80
RevisionAlreadyPresent,
83
81
RevisionNotPresent,
84
UnavailableRepresentation,
82
WeaveRevisionAlreadyPresent,
83
WeaveRevisionNotPresent,
86
from bzrlib.osutils import dirname, sha, sha_strings, split_lines
85
import bzrlib.errors as errors
86
from bzrlib.osutils import sha_strings
87
87
import bzrlib.patiencediff
88
from bzrlib.revision import NULL_REVISION
89
from bzrlib.symbol_versioning import *
90
from bzrlib.trace import mutter
91
from bzrlib.versionedfile import (
88
from bzrlib.symbol_versioning import (deprecated_method,
92
from bzrlib.tsort import topo_sort
93
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
98
94
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
101
class WeaveContentFactory(ContentFactory):
102
"""Content factory for streaming from weaves.
104
:seealso ContentFactory:
107
def __init__(self, version, weave):
108
"""Create a WeaveContentFactory for version from weave."""
109
ContentFactory.__init__(self)
110
self.sha1 = weave.get_sha1s([version])[version]
111
self.key = (version,)
112
parents = weave.get_parent_map([version])[version]
113
self.parents = tuple((parent,) for parent in parents)
114
self.storage_kind = 'fulltext'
117
def get_bytes_as(self, storage_kind):
118
if storage_kind == 'fulltext':
119
return self._weave.get_text(self.key[-1])
120
elif storage_kind == 'chunked':
121
return self._weave.get_lines(self.key[-1])
123
raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
126
97
class Weave(VersionedFile):
127
98
"""weave - versioned text file storage.
129
100
A Weave manages versions of line-based text files, keeping track
130
101
of the originating version for each line.
270
221
return self._parents == other._parents \
271
222
and self._weave == other._weave \
272
and self._sha1s == other._sha1s
223
and self._sha1s == other._sha1s
274
225
def __ne__(self, other):
275
226
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."""
277
233
def _idx_to_name(self, version):
278
234
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
280
245
def _lookup(self, name):
281
246
"""Convert symbolic version name to index."""
282
if not self._allow_reserved:
283
self.check_not_reserved_id(name)
285
248
return self._name_map[name]
287
250
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()
289
262
def versions(self):
290
263
"""See VersionedFile.versions."""
291
264
return self._names[:]
293
266
def has_version(self, version_id):
294
267
"""See VersionedFile.has_version."""
295
return (version_id in self._name_map)
268
return self._name_map.has_key(version_id)
297
270
__contains__ = has_version
299
def get_record_stream(self, versions, ordering, include_delta_closure):
300
"""Get a stream of records for versions.
302
:param versions: The versions to include. Each version is a tuple
304
:param ordering: Either 'unordered' or 'topological'. A topologically
305
sorted stream has compression parents strictly before their
307
:param include_delta_closure: If True then the closure across any
308
compression parents will be included (in the opaque data).
309
:return: An iterator of ContentFactory objects, each of which is only
310
valid until the iterator is advanced.
312
versions = [version[-1] for version in versions]
313
if ordering == 'topological':
314
parents = self.get_parent_map(versions)
315
new_versions = tsort.topo_sort(parents)
316
new_versions.extend(set(versions).difference(set(parents)))
317
versions = new_versions
318
elif ordering == 'groupcompress':
319
parents = self.get_parent_map(versions)
320
new_versions = sort_groupcompress(parents)
321
new_versions.extend(set(versions).difference(set(parents)))
322
versions = new_versions
323
for version in versions:
325
yield WeaveContentFactory(version, self)
327
yield AbsentContentFactory((version,))
329
def get_parent_map(self, version_ids):
330
"""See VersionedFile.get_parent_map."""
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)
332
279
for version_id in version_ids:
333
if version_id == NULL_REVISION:
338
map(self._idx_to_name,
339
self._parents[self._lookup(version_id)]))
340
except RevisionNotPresent:
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
342
result[version_id] = parents
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],
345
def get_parents_with_ghosts(self, version_id):
346
raise NotImplementedError(self.get_parents_with_ghosts)
348
def insert_record_stream(self, stream):
349
"""Insert a record stream into this versioned file.
351
:param stream: A stream of records to insert.
353
:seealso VersionedFile.get_record_stream:
356
for record in stream:
357
# Raise an error when a record is missing.
358
if record.storage_kind == 'absent':
359
raise RevisionNotPresent([record.key[0]], self)
360
# adapt to non-tuple interface
361
parents = [parent[0] for parent in record.parents]
362
if (record.storage_kind == 'fulltext'
363
or record.storage_kind == 'chunked'):
364
self.add_lines(record.key[0], parents,
365
osutils.chunks_to_lines(record.get_bytes_as('chunked')))
367
adapter_key = record.storage_kind, 'fulltext'
369
adapter = adapters[adapter_key]
371
adapter_factory = adapter_registry.get(adapter_key)
372
adapter = adapter_factory(self)
373
adapters[adapter_key] = adapter
374
lines = split_lines(adapter.get_bytes(record))
376
self.add_lines(record.key[0], parents, lines)
377
except RevisionAlreadyPresent:
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)])
380
432
def _check_repeated_add(self, name, parents, text, sha1):
381
433
"""Check that a duplicated add is OK.
388
440
raise RevisionAlreadyPresent(name, self._weave_name)
391
def _add_lines(self, version_id, parents, lines, parent_texts,
392
left_matching_blocks, nostore_sha, random_id, check_content):
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):
393
449
"""See VersionedFile.add_lines."""
394
idx = self._add(version_id, lines, map(self._lookup, parents),
395
nostore_sha=nostore_sha)
396
return sha_strings(lines), sum(map(len, lines)), idx
398
def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
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
458
"""Add a single text on top of the weave.
401
460
Returns the index number of the newly added version.
404
463
Symbolic name for this version.
405
464
(Typically the revision-id of the revision that added it.)
406
If None, a name will be allocated based on the hash. (sha1:SHAHASH)
409
467
List or set of direct parent version numbers.
412
470
Sequence of lines to be added in the new version.
414
:param nostore_sha: See VersionedFile.add_lines.
473
assert isinstance(version_id, basestring)
416
474
self._check_lines_not_unicode(lines)
417
475
self._check_lines_are_lines(lines)
419
477
sha1 = sha_strings(lines)
420
if sha1 == nostore_sha:
421
raise errors.ExistingContent
422
if version_id is None:
423
version_id = "sha1:" + sha1
424
478
if version_id in self._name_map:
425
479
return self._check_repeated_add(version_id, parents, lines, sha1)
557
632
def _compatible_parents(self, my_parents, other_parents):
558
633
"""During join check that other_parents are joinable with my_parents.
560
Joinable is defined as 'is a subset of' - supersets may require
635
Joinable is defined as 'is a subset of' - supersets may require
561
636
regeneration of diffs, but subsets do not.
563
638
return len(other_parents.difference(my_parents)) == 0
565
640
def annotate(self, version_id):
566
"""Return a list of (version-id, line) tuples for 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.
568
657
The index indicates when the line originated in the weave."""
569
658
incls = [self._lookup(version_id)]
570
return [(self._idx_to_name(origin), text) for origin, lineno, text in
571
self._extract(incls)]
573
def iter_lines_added_or_present_in_versions(self, version_ids=None,
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
668
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
576
669
if version_ids is None:
577
670
version_ids = self.versions()
578
671
version_ids = set(version_ids)
579
672
for lineno, inserted, deletes, line in self._walk_internal(version_ids):
580
if inserted not in version_ids: continue
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
581
677
if line[-1] != '\n':
582
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)
586
687
def _walk_internal(self, version_ids=None):
587
688
"""Helper method for weave actions."""
848
980
# no lines outside of insertion blocks, that deletions are
849
981
# 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))
851
1034
def _imported_parents(self, other, other_idx):
852
1035
"""Return list of parents in self corresponding to indexes in other."""
853
1036
new_parents = []
951
1143
sio = StringIO()
952
1144
write_weave_v5(self, sio)
954
bytes = sio.getvalue()
955
path = self._weave_name + WeaveFile.WEAVE_SUFFIX
957
self._transport.put_bytes(path, bytes, self._filemode)
958
except errors.NoSuchFile:
959
self._transport.mkdir(dirname(path))
960
self._transport.put_bytes(path, bytes, self._filemode)
1146
self._transport.put(self._weave_name + WeaveFile.WEAVE_SUFFIX,
963
1151
def get_suffixes():
964
1152
"""See VersionedFile.get_suffixes()."""
965
1153
return [WeaveFile.WEAVE_SUFFIX]
967
def insert_record_stream(self, stream):
968
super(WeaveFile, self).insert_record_stream(stream)
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)
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)
972
1167
def _reweave(wa, wb, pb=None, msg=None):
973
1168
"""Combine two weaves and return the result.
975
This works even if a revision R has different parents in
1170
This works even if a revision R has different parents in
976
1171
wa and wb. In the resulting weave all the parents are given.
978
This is done by just building up a new weave, maintaining ordering
1173
This is done by just building up a new weave, maintaining ordering
979
1174
of the versions in the two inputs. More efficient approaches
980
might be possible but it should only be necessary to do
981
this operation rarely, when a new previously ghost version is
1175
might be possible but it should only be necessary to do
1176
this operation rarely, when a new previously ghost version is
984
1179
:param pb: An optional progress bar, indicating how far done we are
1029
1223
p = combined.setdefault(name, set())
1030
1224
p.update(map(weave._idx_to_name, weave._parents[idx]))
1031
1225
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
