Rewriting boundary parents when path-limiting

When using both path and commit limiting, git log --parents --boundary rewrites the parents that are actually in the graph but doesn't rewrite the parents on the boundary, that is, the boundary parents may be commits that don't modify any of the specified paths. I'm wondering if there is a way to get the boundary parents rewritten too.

The reason is this. One of the nice things about the dev branch of gitk is that updating the graph is really quick, because the git log that gitk does when updating excludes all the commits that gitk has already seen, using commit limiting.

Without path limiting, that works nicely, and the boundary of the new set consists of commits that are already in the graph, so gitk can join the new graph into the old. But if path limiting is being used, the boundary commits of the new set aren't necessarily commits that are already in the graph, so gitk can't (at present) join the new graph to the old properly.

Here's an example: suppose the repository looks like this:

HEAD ->	c	modifies file x
	|
	b	modifies file y
	|
	a	modifies file x

Suppose you run "gitk -- x", so gitk will display:

	c
	|
	a

Then suppose commit c gets amended, and still modifies file x, so the HEAD is now commit c', whose parent is b. Then if you do "Update" in gitk (or press F5), gitk will do

	git log HEAD ^c -- x

and it will get one entry, which is c', with b listed as its parent. So then gitk ends up displaying:

	c'
	|
	b

	c
	|
	a

because it doesn't realize that the parent of c' in the path-limited graph should be a.

So can anyone suggest a good way for gitk to know that the parent of c' should be a in this situation?

Paul.

On Sat, 16 Feb 2008, Paul Mackerras wrote:

Hmm. Right now we never rewrite uninteresting parents. The reason is rather simple: we simply haven't followed the chain down uninteresting commits!

Changing that is pretty hard. The thing is, we do the commit range limiting mostly separately from the commit parent simplification: one happens while actually walking the commits, the other one happens after-the-fact when you do the "simplify_commit()" thing.

In addition to that problem (which is likely solvable: we do actually do a lot of the groundwork for the later simplification stage during the first stage, so we might be able to just move more of that logic up), we actually explicitly do *not* simplify uninteresting commits, ie we have:

        if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
                /* Even if a merge with an uninteresting
                 * side branch brought the entire change
                 * we are interested in, we do not want
                 * to lose the other branches of this
                 * merge, so we just keep going.
                 */
                pp = &parent->next;
                continue;
        }

in there, where the comment says it all: we literally *avoid* simplifying uninteresting parents, and if the commit itself is uninteresting, we go even further, and don't even compare the trees at all! (See the big comment in revision.c: add_parents_to_list, and note how it checks for the UNINTERESTING bit and returns early without even calling try_to_simplify_commit() for such a commit).

So right now, not only is the code not really organized for what you ask, it actually explicitly tries to avoid doing what you ask.

That said, I'm not sure either of these problems are really impossible (or even hard) issues to avoid.

We could simply move the "try_to_simplify_commit()" call up, and remove some of the code that explicitly avoids simplifying negative commits. But the logic on when to stop even traversing the list is fundamentally pretty hard, and that might require splitting up UNINTERESTING into two separate bits: a "fairly uninteresting" bit (which means that it is negative) and a "_really_ uninteresting bit" (which means that not only was it negtive, but it also changed the tree, so the parents of this commit are *really* not interesting any more, even after simplification).

Then the "can we stop traversing the tree" code would have to look at the "really uninteresting" bit rather than just the regular uninteresting one.

Quite frankly, I suspect it's not worth it, and maybe you just shouldn't do that optimization and limit the commits in other ways instead (ie you might try to limit them *numerically* instead of by using negative commits, and do one first run with the number of commits limited to <n>, and then if that wasn't enough to re-connect the trees, you do the whole thing)

		Linus

Linus Torvalds writes:

OK.  I have fixed the problem in gitk by making it do:

    git rev-list --first-parent --max-count=1 $id -- paths...

for each id that it gets while updating that is a boundary commit, if we are doing path limiting and the id is one that isn't in the graph. If what we get back is a commit that is already in the graph, then we use it instead. That seems to do what I want.

Currently gitk executes that git rev-list synchronously, but if that causes noticeable pauses, it could be done asynchronously instead.

Paul.