Rewriting boundary parents when path-limiting

Rewriting boundary parents when path-limiting

[Paul Mackerras]

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.

Re: Rewriting boundary parents when path-limiting

[Linus Torvalds]

On Sat, 16 Feb 2008, Paul Mackerras wrote:
>
> 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.

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

Re: Rewriting boundary parents when path-limiting

[Paul Mackerras]

Linus Torvalds writes:

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

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.