A function to get the shortest path between two revisions?

[Arne Babenhauserheide]

Hi, 

Does Mercurial already offer a function to get the shortest path between two 
revisions? 

With that it would be possible to write a damn slow but correct merger for 
files in which the order of the line doesn't matter. 

Basic idea: Merge rev1 into rev2 by walking the shortest path of changesets 
between the two revisions. 

# Definitions

rev1.lines() = all lines in the file to merge in rev1 
# rev1.lines() is a shortcut for 
# "read all lines from the file in the manifest of rev1". 

rev1.rev() = revision number of rev1

path = [all revisions in the shortest path between rev1 and rev2]
# path has to be ordered so that iterating over it 
# gives the revs in the order we'd have to go to reach 
# rev2 when we begin with rev1, including rev1 and rev2

add_line(line, rev) # appends a line to file the in the given revision
# keeping the annotation intact. 

# Functions

def removed_in_path(line, path): 
	"""Check if the given line was actively removed in the path"""
	line_removed = False
	i = path[0]
	for j in path[1:]: 
		# only check "forward revisions"
		if j.rev() > i.rev() and line in i.lines() and not line in j.lines()
			line_removed = True
		i = j.copy()
	return line_removed


def walking_merge(rev1, rev2, path): 

	# Merge additions from rev1 into rev2
	for line in rev1.lines(): 
		if line in rev2.lines: 
			continue # no need to act
		elif line_removed(line, path): 
			continue # the line was actively removed, so we don't add it
		else: 
			add_line(line, rev2)

	# merge removals from rev1 into rev2
	for line in rev2.lines(): 
		if line in rev1.lines(): 
			continue
		elif line_removed(line, path.reversed()): 
			# if the line was actively removed in the path 
			# from rev2 to rev1, remove it in rev2
			remove_line(line, rev2)


"actively removed" means: A changeset removed the line. 


Firstoff: Is there a "get shortest path" functions? 

Second: What do you think about the merge idea? 


Best wishes, 
Arne
-- 
-- My stuff: http://draketo.de - stories, songs, poems, programs and stuff :)
-- Infinite Hands: http://infinite-hands.draketo.de - singing a part of the 
history of free software.
-- Ein Würfel System: http://1w6.org - einfach saubere (Rollenspiel-) Regeln.

-- PGP/GnuPG: http://draketo.de/inhalt/ich/pubkey.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
Url : http://selenic.com/pipermail/mercurial/attachments/20081211/3ebf392e/attachment.pgp