Re: Bizarre missing changes (git bug?)

Hi,

On Sat, 26 Jul 2008, Linus Torvalds wrote:

This doesn't help with the graphical front ends and they only use what git gives them.

Well, I don't want that much history. Let's take a different example. Look at kernel/sched_rt.c with git-log, --full-history shows an extra commit of a patch which was committed and merged twice, but there is no information how this other patch was merged. If you have giggle installed, you'll see that commit as a loose end.

(I have git version 1.5.6.2 installed in case it matters.)

I played a little with it in the ruby script below, which produces a complete connected graph of all content nodes and which have been merged into the head, e.g. for sched_rt.c it produces that extra commit merge. The script basically eliminates all empty merges. As input to the script I used "git log --parents --name-only --full-history kernel/sched_rt.c | grep -e ^commit -e ^kernel", which seems to produce the same amount of commits as "gitk --full-history ...".

The main function is to check, whether one parent of a commit is an ancestor of another parent, so that this path can be eliminated. I tried it with other paths and too simple implementations quickly lead to exponential behaviour. :) It probably also shouldn't be recursive, I had to increase the stack limit, otherwise I got stack exceptions. Otherwise it seems to work fine, it wasn't that hard :-)

The ruby syntax shouldn't be too hard too read, the nonobvious thing is maybe that '$' marks global variables.

bye, Roman

#! /usr/bin/ruby

$parent = Hash.new $content = Hash.new $result = Hash.new

commit = nil
head = nil
while l = $stdin.gets
	a = l.split(" ")
	if a[0] == "commit"
		commit = a[1]
		head = commit unless head
		$parent[commit] = a[2..-1]
	else
		$content[commit] = true
	end
end

$parent_check = Hash.new $parent_cache = Hash.new

def commit_has_parent?(commit, commit2)
	if $parent_check[commit]
		print "parent loop for #{commit} (#{commit2})?\n"
		p $parent_check
		return false
	end
	return $parent_cache[commit] if $parent_cache.has_key?(commit)
	$parent_check[commit] = true
	res = false
	if $content[commit] > $content[commit2]
		$parent[commit].each do |parent|
			if parent == commit2 || commit_has_parent?(parent, commit2)
				res = true
				break;
			end
		end
	end
	$parent_cache[commit] = res
	$parent_check.delete(commit)
	$parent_cache.clear if $parent_check.empty?
	return res
end

def check_commit(commit)
	return $result[commit] if $result.has_key? commit
	a = Array.new
	$parent[commit].each do |parent|
		parent = check_commit(parent)
		if parent
			a.each_index do |i|
				if a[i] == parent || commit_has_parent?(a[i], parent)
					parent = nil
					break
				elsif commit_has_parent?(parent, a[i])
					a[i] = parent
					parent = nil
					break
				end
			end
		end
		a.push(parent) if parent
	end
	$parent[commit] = a
	$content[commit] = true if a.size > 1
	if $content[commit]
		$result[commit] = commit
		max = 1
		a.each do |parent|
			max = $content[parent] + 1 if max <= $content[parent]
		end
		$content[commit] = max
	else
		$result[commit] = a[0]
	end
	return $result[commit]
end

check_commit(head) #p $result #p $parent

p $content.keys.size
$content.each_key do |commit|
	p [ commit, $parent[commit] ]
	commit = $parent[commit][0]
end