Re: Bizarre missing changes (git bug?)

[Roman Zippel <zippel@linux-m68k.org>]

Hi,

On Sat, 26 Jul 2008, Linus Torvalds wrote:

> > Is there a way to change that default?
> 
> Use an alias or something.

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

> To see why it's the default, do a few tests. In particular, try it with 
> gitk on the kernel. Try it on some fairly simple file that doesn't get a 
> lot of churn. Example:
> 
> 	gitk lib/vsprintf.c
> 
> vs
> 
> 	gitk --full-history lib/vsprintf.c
> 
> and if you don't _immediately_ see why --full-history isn't the default, 
> there's likely something wrong with you. One is useful. The other is not.
> 
> So we absolutely _have_ to simplify merges. There is no question about it.

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.)

> That said, we currently simplify merges the simple and stupid way, and 
> I've hinted several times on this mailing list that there is a better way 
> to do it (last time it was the discussion about "filter-branch".
> 
> In fact, if you google for 
> 
> 	filter-branch full-history
> 
> you'll find some of the discussion. In order to make --full-history useful 
> as a default, we'd need to do an after-the-fact merge cleanup (ie remove 
> lines of development that are later found to really be totally 
> uninteresting), but that is *hard*.

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