Re: [PATCH v2] log: improve --follow following renames for non-linear history

[Junio C Hamano <gitster@pobox.com>]

Miklos Vajna <vmiklos@collabora.com> writes:

> situation when determining what path to follow for a specific commit
> with multiple previously visited children.
> ---

Missing sign-off; omitting sign-off to say that this is primarily
for requesting comments and not ready for application (often we see
RFC on the Subject line when this is done) is fine, though.

>> Can a "map" cut it?
>> 
>> If a history forked at commit A, with two children commit B and
>> commit C, and you started traversing the history from a much later
>> descendant M that merges these two lines of history (i.e., M^1
>> contains B, M^2 contains C, and A==B^1==C^1), while traversing down
>> from M to B you may find that you need to follow path1 and similarly
>> somewhere between M down to C the path you are following may be
>> path2.  And the traversal meets at A.  The slab records path1 for B
>> and path2 for C.  Wouldn't you need to be able to store both path1
>> and path2 for commit A?  What path do you need to pay attention to
>> when traversing past A to its ancestors?
>
> Indeed, I focused on merge commits and their parents and I did not 
> consider that slab[A] may be set to path1 when visiting one parent and 
> then slab[A] may be set to path2 when visiting an other parent -- even 
> if "A" itself is just a plain commit with no renames and is not a merge.

"A" in my example is a fork point.  One of A's children may arrive
at A following path1 while another child may come to A following
path2.  IOW, in the history below:

      B---X---o---M---o---Z
     /           /
    A---C---Y---o

 * A has the original path at "path0"; so do B and C.
 * X renames "path0" to "path1"
 * Y renames "path0" to "path2"
 * M merges path1 coming from upper and path2 from lower history
   and records the result at path "path".
 * Z has "path".

You run "git log --follow Z -- path".

My answer to my (rhetorical) question (Can a "map" cut it?) actually
was "we probably can", since our "rename following" code does not
handle cases where two paths in a parent is merged into a single
path in a child, or a single path in a parent is split to form
multiple paths in a child.

So the "what path are we following?" slab would need to keep track
of a single path.  From Z down to M, we follow "path".  "path1" is
followed from M to X and "path2" is followed from M to Y.  And from
X to A, and Y to A, we follow "path0".  IOW, I did not think we need
two paths recorded for one commit.

Are any of your test cases added by this patch behave differently
with this version (vs the "single path assigned to each commit"
version you had earlier)?  If so, then obviously there is some hole
in my above discussion.  

One case that _could_ break down is if a rename on one track (say,
at Y) is so huge that it is not recognised as a rename.  Then from Y
down to A we would probably try to track "path2" (because we fail to
notice that "path2" came from "path0") and declare that "path2"
appeared at Y from nowhere.  But even then, we shouldn't propagate
"path2" down to A, so A would get only "path0" which was what we
follow going from X down to A, I think.  Still no need for following
multiple paths at a fork point.

> +	/* Any recorded paths for this commit? If so, restore it */
> +	if (opt->diffopt.flags.follow_renames) {
> +		paths = get_follow_pathspec_at(opt, commit);
> +		if (!paths->nr) {
> +			const char *path = pathspec_single_path(&opt->diffopt.pathspec);
> +			if (path)
> +				string_list_insert(paths, path);

We do not need to worry about deduplicating, as string_list_insert()
will automatically takes care of that for us, which is nice.

> +		}
> +		set_pathspec_to_paths(&opt->diffopt.pathspec, paths);
> +		if (paths->nr > 1) {
> +			/* diff_check_follow_pathspec() doesn't handle multiple paths */
> +			saved_follow_renames = opt->diffopt.flags.follow_renames;
> +			opt->diffopt.flags.follow_renames = 0;
> +		}
> +	}

Eek. That's a subtle workaround to break the built-in safety to
ensure there is only one pathspec element while following.