v2, 20 partsmerge-ort: avoid recursing into identical trees

> +	/*
> +	 * If mbase, side1, and side2 all match, we can resolve early.  Even
> +	 * if these are trees, there will be no renames or anything
> +	 * underneath.
> +	 */
> +	if (side1_matches_mbase && side2_matches_mbase) {

> +		/* mbase, side1, & side2 all match; use mbase as resolution */
> +		setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
> +				names, names+0, mbase_null, 0,
> +				filemask, dirmask, 1);
> +		return mask;
> +	}
> +

> +	/*
> +	 * Note: We only label files with df_conflict, not directories.
> +	 * Since directories stay where they are, and files move out of the
> +	 * way to make room for a directory, we don't care if there was a
> +	 * directory/file conflict for a parent directory of the current path.
> +	 */
> +	unsigned df_conflict = (filemask != 0) && (dirmask != 0);

> @@ -161,6 +179,13 @@ static int collect_merge_info_callback(int n,
>  		newinfo.name = p->path;
>  		newinfo.namelen = p->pathlen;
>  		newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
> +		/*
> +		 * If we did care about parent directories having a D/F
> +		 * conflict, then we'd include
> +		 *    newinfo.df_conflicts |= (mask & ~dirmask);
> +		 * here.  But we don't.  (See comment near setting of local
> +		 * df_conflict variable near the beginning of this function).
> +		 */

>
> > +     /*
> > +      * Note: We only label files with df_conflict, not directories.
> > +      * Since directories stay where they are, and files move out of the
> > +      * way to make room for a directory, we don't care if there was a
> > +      * directory/file conflict for a parent directory of the current path.
> > +      */
> > +     unsigned df_conflict = (filemask != 0) && (dirmask != 0);
>
> Suppose you have:
>
>  [ours]
>   foo/
>     bar/
>       baz
>     quux
>  [theirs]
>   foo
>
> By "we only label files with df_conflict, not directories", are you
> referring to not labelling "foo/" in [ours], or to "bar/", "baz", and
> "quux" (so, the files and directories within a directory)? At first I
> thought you were referring to the former, but perhaps you are referring
> to the latter.

>
> > @@ -161,6 +179,13 @@ static int collect_merge_info_callback(int n,
> >               newinfo.name = p->path;
> >               newinfo.namelen = p->pathlen;
> >               newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
> > +             /*
> > +              * If we did care about parent directories having a D/F
> > +              * conflict, then we'd include
> > +              *    newinfo.df_conflicts |= (mask & ~dirmask);
> > +              * here.  But we don't.  (See comment near setting of local
> > +              * df_conflict variable near the beginning of this function).
> > +              */
>
> I'm not sure how "mask" and "dirmask" contains information about parent
> directories. "mask" represents the available entries, and "dirmask"
> represents which of them are directories, as far as I know. So we can
> notice when something is missing, but I don't see how this distinguishes
> between the case that something is missing because it was in a parent
> directory that got deleted, vs something is missing because it itself
> got deleted.

> On Fri, Nov 6, 2020 at 2:52 PM Jonathan Tan <jonathantanmy@google.com> wrote:
> >
> > > +     /*
> > > +      * Note: We only label files with df_conflict, not directories.
> > > +      * Since directories stay where they are, and files move out of the
> > > +      * way to make room for a directory, we don't care if there was a
> > > +      * directory/file conflict for a parent directory of the current path.
> > > +      */
> > > +     unsigned df_conflict = (filemask != 0) && (dirmask != 0);
> >
> > Suppose you have:
> >
> >  [ours]
> >   foo/
> >     bar/
> >       baz
> >     quux
> >  [theirs]
> >   foo
> >
> > By "we only label files with df_conflict, not directories", are you
> > referring to not labelling "foo/" in [ours], or to "bar/", "baz", and
> > "quux" (so, the files and directories within a directory)? At first I
> > thought you were referring to the former, but perhaps you are referring
> > to the latter.
> 
> The former.  I was drawing a distinction between how this code
> operates, and how unpack_trees() operates, which probably only matters
> to those familiar with unpack_trees() or who have been reading through
> it recently.

> unpack_trees() will note when there is a directory/file
> conflict, and propagates that information to all subtrees, with every
> path specially checking for the o->df_conflict_entry and then handling
> it specially (e.g. keeping higher order stages instead of using an
> aggressive or trivial resolutions).

> However, leaving both a file and
> a directory at the same path, while allowed in the index, makes for
> ugliness and difficulty for users to resolve.   Plus it isn't allowed
> in the working tree anyway.  We decided a while ago that it'd be
> better to represent these conflicts differently[1], [2].
> 
> Also, at the time you are unpacking or traversing trees, you only know
> if one side had a directory where the other side had a file.  You
> don't know if the final merge result will actually have a
> directory/file conflict.  If the file existed in both the base version
> and unmodified on one side, for example, then the file will be removed
> as part of the merge.  It is similarly possible that the entire
> directory of files all need to be deleted or are all renamed
> elsewhere.  So, you have to keep track of a df_conflict bit, but you
> can't act on it until you've processed several other things first.
> 
> Since I already know I'm not going to move a whole directory of files
> out of the way so that a file can be placed in the working tree
> instead of that whole directory, the directory doesn't need to be
> tweaked.  I'm not going to propagate any information about a
> directory/file conflict at some path down to all subpaths of the
> directory.  I only track it for the file that immediately conflicts,
> and then only take action on it after resolving all the paths under
> the corresponding directory to see if the directory/file conflict
> remains.
> 
> [1] https://lore.kernel.org/git/xmqqbmabcuhf.fsf@gitster-ct.c.googlers.com/
> and the thread surrounding it
> [2] https://lore.kernel.org/git/f27f12e8e50e56c010c29caa00296475d4de205b.1603731704.git.gitgitgadget@gmail.com/,
> which is now commit ef52778708 ("merge tests: expect improved
> directory/file conflict handling in ort", 2020-10-26)

> > > @@ -161,6 +179,13 @@ static int collect_merge_info_callback(int n,
> > >               newinfo.name = p->path;
> > >               newinfo.namelen = p->pathlen;
> > >               newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
> > > +             /*
> > > +              * If we did care about parent directories having a D/F
> > > +              * conflict, then we'd include
> > > +              *    newinfo.df_conflicts |= (mask & ~dirmask);
> > > +              * here.  But we don't.  (See comment near setting of local
> > > +              * df_conflict variable near the beginning of this function).
> > > +              */
> >
> > I'm not sure how "mask" and "dirmask" contains information about parent
> > directories. "mask" represents the available entries, and "dirmask"
> > represents which of them are directories, as far as I know. So we can
> > notice when something is missing, but I don't see how this distinguishes
> > between the case that something is missing because it was in a parent
> > directory that got deleted, vs something is missing because it itself
> > got deleted.
> 
> Yeah, this is more comparisons to unpack_trees.  This code is about to
> set up a recursive call into subdirectories.  newinfo is set based on
> the mask and dirmask of the current entry, and then subdirectories can
> consult newinfo.df_conflicts to see if that path is within a directory
> that was involved in a directory/file conflict.  For example:
> 
> Tree in base version:
>     foo/
>         bar
>     stuff.txt
> Tree on side 1: (adds foo/baz)
>     foo/
>         bar
>         baz
>     stuff.txt
> Tree on side 2: (deletes foo/, adds new file foo)
>    foo
>    stuff.txt
> 
> When processing 'foo', we have mask=7, dirmask = 3.  So, here
> unpack_trees() would have set newinfo.df_conflicts = (mask & ~dirmask)
> = 4.  Then when we process foo/bar or foo/baz, we have mask=2,
> dirmask=0, which looks like there are no directory/file conflicts.
> However, we can note that these paths are under a directory involved
> in a directory/file conflict via info.df_conflicts whose value is 4.
> unpack_trees() cared about paths under a directory that was involved
> in a directory/file conflict, and someone familiar with that code
> might ask why I don't also track the same information.  The answer is
> that I don't track it, even though I thought about it, because it's
> useless overhead since I'm going to leave the directory alone and move
> the file out of the way.
> 
> Does that make sense?

>
> > On Fri, Nov 6, 2020 at 2:52 PM Jonathan Tan <jonathantanmy@google.com> wrote:
> > >
> > > > +     /*
> > > > +      * Note: We only label files with df_conflict, not directories.
> > > > +      * Since directories stay where they are, and files move out of the
> > > > +      * way to make room for a directory, we don't care if there was a
> > > > +      * directory/file conflict for a parent directory of the current path.
> > > > +      */
> > > > +     unsigned df_conflict = (filemask != 0) && (dirmask != 0);
> > >
> > > Suppose you have:
> > >
> > >  [ours]
> > >   foo/
> > >     bar/
> > >       baz
> > >     quux
> > >  [theirs]
> > >   foo
> > >
> > > By "we only label files with df_conflict, not directories", are you
> > > referring to not labelling "foo/" in [ours], or to "bar/", "baz", and
> > > "quux" (so, the files and directories within a directory)? At first I
> > > thought you were referring to the former, but perhaps you are referring
> > > to the latter.
> >
> > The former.  I was drawing a distinction between how this code
> > operates, and how unpack_trees() operates, which probably only matters
> > to those familiar with unpack_trees() or who have been reading through
> > it recently.
>
> Just for clarification: do you mean "the latter"? (The "not" in my
> question might be confusing.)

> To be more illustrative in what I meant, at first I thought that you
> were NOT labelling "foo/" in [ours], hence:
>
>  [ours]
>   foo/  <- unlabeled
>  [theirs]
>   foo   <- labeled
>
> In this way, in a sense, you are indeed labelling only the file, not the
> directory.
>
> But instead what you seem to be doing is this:
>
>  [ours]
>   foo/     <- labeled
>     bar/   <- unlabeled
>       baz  <- unlabeled
>     quux   <- unlabeled
>  [theirs]
>   foo      <- labeled
>
> which is what I meant by NOT labelling "bar/", "baz", and "quux".

> > unpack_trees() will note when there is a directory/file
> > conflict, and propagates that information to all subtrees, with every
> > path specially checking for the o->df_conflict_entry and then handling
> > it specially (e.g. keeping higher order stages instead of using an
> > aggressive or trivial resolutions).
>
> And here it seems like you're describing that unpack_trees() would label
> it in this way:
>
>  [ours]
>   foo/     <- labeled
>     bar/   <- labeled
>       baz  <- labeled
>     quux   <- labeled
>  [theirs]
>   foo      <- labeled
>
> (and you're emphasizing by contrast that merge-ort is NOT doing this).

> > However, leaving both a file and
> > a directory at the same path, while allowed in the index, makes for
> > ugliness and difficulty for users to resolve.   Plus it isn't allowed
> > in the working tree anyway.  We decided a while ago that it'd be
> > better to represent these conflicts differently[1], [2].
> >
> > Also, at the time you are unpacking or traversing trees, you only know
> > if one side had a directory where the other side had a file.  You
> > don't know if the final merge result will actually have a
> > directory/file conflict.  If the file existed in both the base version
> > and unmodified on one side, for example, then the file will be removed
> > as part of the merge.  It is similarly possible that the entire
> > directory of files all need to be deleted or are all renamed
> > elsewhere.  So, you have to keep track of a df_conflict bit, but you
> > can't act on it until you've processed several other things first.
> >
> > Since I already know I'm not going to move a whole directory of files
> > out of the way so that a file can be placed in the working tree
> > instead of that whole directory, the directory doesn't need to be
> > tweaked.  I'm not going to propagate any information about a
> > directory/file conflict at some path down to all subpaths of the
> > directory.  I only track it for the file that immediately conflicts,
> > and then only take action on it after resolving all the paths under
> > the corresponding directory to see if the directory/file conflict
> > remains.
> >
> > [1] https://lore.kernel.org/git/xmqqbmabcuhf.fsf@gitster-ct.c.googlers.com/
> > and the thread surrounding it
> > [2] https://lore.kernel.org/git/f27f12e8e50e56c010c29caa00296475d4de205b.1603731704.git.gitgitgadget@gmail.com/,
> > which is now commit ef52778708 ("merge tests: expect improved
> > directory/file conflict handling in ort", 2020-10-26)
>
> Makes sense.
>
> > > > @@ -161,6 +179,13 @@ static int collect_merge_info_callback(int n,
> > > >               newinfo.name = p->path;
> > > >               newinfo.namelen = p->pathlen;
> > > >               newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
> > > > +             /*
> > > > +              * If we did care about parent directories having a D/F
> > > > +              * conflict, then we'd include
> > > > +              *    newinfo.df_conflicts |= (mask & ~dirmask);
> > > > +              * here.  But we don't.  (See comment near setting of local
> > > > +              * df_conflict variable near the beginning of this function).
> > > > +              */
> > >
> > > I'm not sure how "mask" and "dirmask" contains information about parent
> > > directories. "mask" represents the available entries, and "dirmask"
> > > represents which of them are directories, as far as I know. So we can
> > > notice when something is missing, but I don't see how this distinguishes
> > > between the case that something is missing because it was in a parent
> > > directory that got deleted, vs something is missing because it itself
> > > got deleted.
> >
> > Yeah, this is more comparisons to unpack_trees.  This code is about to
> > set up a recursive call into subdirectories.  newinfo is set based on
> > the mask and dirmask of the current entry, and then subdirectories can
> > consult newinfo.df_conflicts to see if that path is within a directory
> > that was involved in a directory/file conflict.  For example:
> >
> > Tree in base version:
> >     foo/
> >         bar
> >     stuff.txt
> > Tree on side 1: (adds foo/baz)
> >     foo/
> >         bar
> >         baz
> >     stuff.txt
> > Tree on side 2: (deletes foo/, adds new file foo)
> >    foo
> >    stuff.txt
> >
> > When processing 'foo', we have mask=7, dirmask = 3.  So, here
> > unpack_trees() would have set newinfo.df_conflicts = (mask & ~dirmask)
> > = 4.  Then when we process foo/bar or foo/baz, we have mask=2,
> > dirmask=0, which looks like there are no directory/file conflicts.
> > However, we can note that these paths are under a directory involved
> > in a directory/file conflict via info.df_conflicts whose value is 4.
> > unpack_trees() cared about paths under a directory that was involved
> > in a directory/file conflict, and someone familiar with that code
> > might ask why I don't also track the same information.  The answer is
> > that I don't track it, even though I thought about it, because it's
> > useless overhead since I'm going to leave the directory alone and move
> > the file out of the way.
> >
> > Does that make sense?
>
> Ah...yes, that makes sense. I think I didn't notice the "newinfo", so I
> didn't realize that we were setting the info of our children based on
> ourselves. Perhaps I would have noticed it sooner if the comment had
> read "If this file/directory cared about its parent directory (the
> current directory) having a D/F conflict, then we'd propagate the masks
> in this way:" instead of "If we did care about parent directories having
> a D/F conflict", but perhaps the point is already obvious enough.

> +/* Per entry merge function */
> +static void process_entry(struct merge_options *opt,
> +			  const char *path,
> +			  struct conflict_info *ci)
> +{
> +	assert(!ci->merged.clean);
> +	assert(ci->filemask >= 0 && ci->filemask <= 7);

> +
> +	if (ci->filemask == 0) {
> +		/*
> +		 * This is a placeholder for directories that were recursed
> +		 * into; nothing to do in this case.
> +		 */
> +		return;
> +	}
> +
> +	if (ci->df_conflict) {
> +		die("Not yet implemented.");
> +	}
> +
> +	/*
> +	 * NOTE: Below there is a long switch-like if-elseif-elseif... block
> +	 *       which the code goes through even for the df_conflict cases
> +	 *       above.  Well, it will once we don't die-not-implemented above.
> +	 */
> +	if (ci->match_mask) {
> +		ci->merged.clean = 1;

> +			ci->merged.result.mode = ci->stages[side].mode;
> +			oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
> +
> +			assert(othermask == 2 || othermask == 4);
> +			assert(ci->merged.is_null == !ci->merged.result.mode);
> +		}
> +	} else if (ci->filemask >= 6 &&
> +		   (S_IFMT & ci->stages[1].mode) !=
> +		   (S_IFMT & ci->stages[2].mode)) {
> +		/*
> +		 * Two different items from (file/submodule/symlink)
> +		 */
> +		die("Not yet implemented.");

> +	} else if (ci->filemask >= 6) {
> +		/*
> +		 * TODO: Needs a two-way or three-way content merge, but we're
> +		 * just being lazy and copying the version from HEAD and
> +		 * leaving it as conflicted.
> +		 */
> +		ci->merged.clean = 0;
> +		ci->merged.result.mode = ci->stages[1].mode;
> +		oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);

> +	} else if (ci->filemask == 3 || ci->filemask == 5) {
> +		/* Modify/delete */
> +		die("Not yet implemented.");
> +	} else if (ci->filemask == 2 || ci->filemask == 4) {
> +		/* Added on one side */
> +		int side = (ci->filemask == 4) ? 2 : 1;
> +		ci->merged.result.mode = ci->stages[side].mode;
> +		oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
> +		ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
> +	} else if (ci->filemask == 1) {
> +		/* Deleted on both sides */
> +		ci->merged.is_null = 1;
> +		ci->merged.result.mode = 0;
> +		oidcpy(&ci->merged.result.oid, &null_oid);
> +		ci->merged.clean = !ci->path_conflict;
> +	}

> +
> +	/*
> +	 * If still unmerged, record it separately.  This allows us to later
> +	 * iterate over just unmerged entries when updating the index instead
> +	 * of iterating over all entries.
> +	 */
> +	if (!ci->merged.clean)
> +		strmap_put(&opt->priv->unmerged, path, ci);
> +}
> +
>  static void process_entries(struct merge_options *opt,
>  			    struct object_id *result_oid)
>  {
> -	die("Not yet implemented.");
> +	struct hashmap_iter iter;
> +	struct strmap_entry *e;
> +
> +	if (strmap_empty(&opt->priv->paths)) {
> +		oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
> +		return;
> +	}
> +
> +	strmap_for_each_entry(&opt->priv->paths, &iter, e) {
> +		/*
> +		 * WARNING: If ci->merged.clean is true, then ci does not
> +		 * actually point to a conflict_info but a struct merge_info.
> +		 */
> +		struct conflict_info *ci = e->value;
> +
> +		if (!ci->merged.clean)
> +			process_entry(opt, e->key, e->value);
> +	}
> +
> +	die("Tree creation not yet implemented");

>
> Okay...let me review patches 11-15. (Patches 16-20 deal with checkout
> and might be better reviewed by someone who is already familiar with how
> the existing merge performs checkout. If no one reviews it, I might come
> back to it if I have time.)

> > +/* Per entry merge function */
> > +static void process_entry(struct merge_options *opt,
> > +                       const char *path,
> > +                       struct conflict_info *ci)
> > +{
> > +     assert(!ci->merged.clean);
> > +     assert(ci->filemask >= 0 && ci->filemask <= 7);
>
> I see below that this function doesn't handle ci->match_mask == 7 (and
> it doesn't need to because, I believe, there is a function in one of the
> earlier patches that optimizes the case wherein all 3 match with each
> other). Maybe add an assert here for that too.
>
> > +
> > +     if (ci->filemask == 0) {
> > +             /*
> > +              * This is a placeholder for directories that were recursed
> > +              * into; nothing to do in this case.
> > +              */
> > +             return;
> > +     }
> > +
> > +     if (ci->df_conflict) {
> > +             die("Not yet implemented.");
> > +     }
> > +
> > +     /*
> > +      * NOTE: Below there is a long switch-like if-elseif-elseif... block
> > +      *       which the code goes through even for the df_conflict cases
> > +      *       above.  Well, it will once we don't die-not-implemented above.
> > +      */
> > +     if (ci->match_mask) {
> > +             ci->merged.clean = 1;
>
> OK, looks straightforward so far. It's a clean merge if 2 match. (As I
> said earlier, at this point in the code, it is not possible for 3 to
> match.)
>
> > +             if (ci->match_mask == 6) {
> > +                     /* stages[1] == stages[2] */
> > +                     ci->merged.result.mode = ci->stages[1].mode;
> > +                     oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
>
> If OURS and THEIRS match, use one of them arbitrarily (because they are
> the same anyway). OK.
>
> > +             } else {
> > +                     /* determine the mask of the side that didn't match */
> > +                     unsigned int othermask = 7 & ~ci->match_mask;
> > +                     int side = (othermask == 4) ? 2 : 1;
>
> BASE matches with either OURS or THEIRS, so use the side that doesn't
> match. OK.
>
> > +
> > +                     ci->merged.is_null = (ci->filemask == ci->match_mask);
>
> This works (if the non-matching bit in filemask is set, the file exists;
> the comparison will be false and therefore is_null is false - and
> correctly false because the file exists), but seems unnecessarily
> clever. Couldn't you just check nullness of the OID (or through the
> mode, like the line below it) and set it here?
>
> Admittedly, the way you wrote it also verifies that filemask is what we
> expect. I don't think it is important to verify it, but if you think it
> is important, I think it is this verification that should go in the
> assert statement.

> > +                     ci->merged.result.mode = ci->stages[side].mode;
> > +                     oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
> > +
> > +                     assert(othermask == 2 || othermask == 4);
> > +                     assert(ci->merged.is_null == !ci->merged.result.mode);
> > +             }
> > +     } else if (ci->filemask >= 6 &&
> > +                (S_IFMT & ci->stages[1].mode) !=
> > +                (S_IFMT & ci->stages[2].mode)) {
> > +             /*
> > +              * Two different items from (file/submodule/symlink)
> > +              */
> > +             die("Not yet implemented.");
>
> There are no matches, and OURS and THEIRS have different types. OK.
>
> > +     } else if (ci->filemask >= 6) {
> > +             /*
> > +              * TODO: Needs a two-way or three-way content merge, but we're
> > +              * just being lazy and copying the version from HEAD and
> > +              * leaving it as conflicted.
> > +              */
> > +             ci->merged.clean = 0;
> > +             ci->merged.result.mode = ci->stages[1].mode;
> > +             oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
>
> OK.
>
> > +     } else if (ci->filemask == 3 || ci->filemask == 5) {
> > +             /* Modify/delete */
> > +             die("Not yet implemented.");
> > +     } else if (ci->filemask == 2 || ci->filemask == 4) {
> > +             /* Added on one side */
> > +             int side = (ci->filemask == 4) ? 2 : 1;
> > +             ci->merged.result.mode = ci->stages[side].mode;
> > +             oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
> > +             ci->merged.clean = !ci->df_conflict && !ci->path_conflict;
> > +     } else if (ci->filemask == 1) {
> > +             /* Deleted on both sides */
> > +             ci->merged.is_null = 1;
> > +             ci->merged.result.mode = 0;
> > +             oidcpy(&ci->merged.result.oid, &null_oid);
> > +             ci->merged.clean = !ci->path_conflict;
> > +     }
>
> The rest is OK.
>
> > +
> > +     /*
> > +      * If still unmerged, record it separately.  This allows us to later
> > +      * iterate over just unmerged entries when updating the index instead
> > +      * of iterating over all entries.
> > +      */
> > +     if (!ci->merged.clean)
> > +             strmap_put(&opt->priv->unmerged, path, ci);
> > +}
> > +
> >  static void process_entries(struct merge_options *opt,
> >                           struct object_id *result_oid)
> >  {
> > -     die("Not yet implemented.");
> > +     struct hashmap_iter iter;
> > +     struct strmap_entry *e;
> > +
> > +     if (strmap_empty(&opt->priv->paths)) {
> > +             oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
> > +             return;
> > +     }
> > +
> > +     strmap_for_each_entry(&opt->priv->paths, &iter, e) {
> > +             /*
> > +              * WARNING: If ci->merged.clean is true, then ci does not
> > +              * actually point to a conflict_info but a struct merge_info.
> > +              */
> > +             struct conflict_info *ci = e->value;
> > +
> > +             if (!ci->merged.clean)
> > +                     process_entry(opt, e->key, e->value);
> > +     }
> > +
> > +     die("Tree creation not yet implemented");
>
> The rest looks straightforward.

> +static void setup_path_info(struct merge_options *opt,
> +			    struct string_list_item *result,
> +			    const char *current_dir_name,
> +			    int current_dir_name_len,
> +			    char *fullpath, /* we'll take over ownership */
> +			    struct name_entry *names,
> +			    struct name_entry *merged_version,
> +			    unsigned is_null,     /* boolean */
> +			    unsigned df_conflict, /* boolean */

> +			    unsigned filemask,
> +			    unsigned dirmask,
> +			    int resolved          /* boolean */)
> +{
> +	struct conflict_info *path_info;
> +
> +	assert(!is_null || resolved);
> +	assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
> +	assert(resolved == (merged_version != NULL));
> +
> +	path_info = xcalloc(1, resolved ? sizeof(struct merged_info) :
> +					  sizeof(struct conflict_info));
> +	path_info->merged.directory_name = current_dir_name;
> +	path_info->merged.basename_offset = current_dir_name_len;
> +	path_info->merged.clean = !!resolved;
> +	if (resolved) {
> +		path_info->merged.result.mode = merged_version->mode;
> +		oidcpy(&path_info->merged.result.oid, &merged_version->oid);
> +		path_info->merged.is_null = !!is_null;
> +	} else {
> +		int i;
> +
> +		for (i = 0; i < 3; i++) {
> +			path_info->pathnames[i] = fullpath;
> +			path_info->stages[i].mode = names[i].mode;
> +			oidcpy(&path_info->stages[i].oid, &names[i].oid);
> +		}
> +		path_info->filemask = filemask;
> +		path_info->dirmask = dirmask;
> +		path_info->df_conflict = !!df_conflict;
> +	}
> +	strmap_put(&opt->priv->paths, fullpath, path_info);

> +	result->string = fullpath;
> +	result->util = path_info;
> +}
> +
>  static int collect_merge_info_callback(int n,
>  				       unsigned long mask,
>  				       unsigned long dirmask,
> @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
>  	 */
>  	struct merge_options *opt = info->data;
>  	struct merge_options_internal *opti = opt->priv;
> -	struct conflict_info *ci;
> +	struct string_list_item pi;  /* Path Info */
> +	struct conflict_info *ci; /* pi.util when there's a conflict */

>
> > +static void setup_path_info(struct merge_options *opt,
> > +                         struct string_list_item *result,
> > +                         const char *current_dir_name,
> > +                         int current_dir_name_len,
> > +                         char *fullpath, /* we'll take over ownership */
> > +                         struct name_entry *names,
> > +                         struct name_entry *merged_version,
> > +                         unsigned is_null,     /* boolean */
> > +                         unsigned df_conflict, /* boolean */
>
> Booleans could be int, I think?

> > +                         unsigned filemask,
> > +                         unsigned dirmask,
> > +                         int resolved          /* boolean */)
> > +{
> > +     struct conflict_info *path_info;
> > +
> > +     assert(!is_null || resolved);
> > +     assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
> > +     assert(resolved == (merged_version != NULL));
> > +
> > +     path_info = xcalloc(1, resolved ? sizeof(struct merged_info) :
> > +                                       sizeof(struct conflict_info));
> > +     path_info->merged.directory_name = current_dir_name;
> > +     path_info->merged.basename_offset = current_dir_name_len;
> > +     path_info->merged.clean = !!resolved;
> > +     if (resolved) {
> > +             path_info->merged.result.mode = merged_version->mode;
> > +             oidcpy(&path_info->merged.result.oid, &merged_version->oid);
> > +             path_info->merged.is_null = !!is_null;
> > +     } else {
> > +             int i;
> > +
> > +             for (i = 0; i < 3; i++) {
> > +                     path_info->pathnames[i] = fullpath;
> > +                     path_info->stages[i].mode = names[i].mode;
> > +                     oidcpy(&path_info->stages[i].oid, &names[i].oid);
> > +             }
> > +             path_info->filemask = filemask;
> > +             path_info->dirmask = dirmask;
> > +             path_info->df_conflict = !!df_conflict;
> > +     }
> > +     strmap_put(&opt->priv->paths, fullpath, path_info);
>
> So these are placed in paths but not unmerged. I'm starting to wonder if
> struct merge_options_internal should be called merge_options_state or
> something, and each field having documentation about when they're used
> (or better yet, have functions like collect_merge_info() return their
> calculations in return values (which may be "out" parameters) instead of
> in this struct).

> > +     result->string = fullpath;
> > +     result->util = path_info;
> > +}
> > +
> >  static int collect_merge_info_callback(int n,
> >                                      unsigned long mask,
> >                                      unsigned long dirmask,
> > @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
> >        */
> >       struct merge_options *opt = info->data;
> >       struct merge_options_internal *opti = opt->priv;
> > -     struct conflict_info *ci;
> > +     struct string_list_item pi;  /* Path Info */
> > +     struct conflict_info *ci; /* pi.util when there's a conflict */
>
> Looking ahead to patch 10, this seems more like "pi.util unless we know
> for sure that there's no conflict".

> > So these are placed in paths but not unmerged. I'm starting to wonder if
> > struct merge_options_internal should be called merge_options_state or
> > something, and each field having documentation about when they're used
> > (or better yet, have functions like collect_merge_info() return their
> > calculations in return values (which may be "out" parameters) instead of
> > in this struct).
> 
> Right, unmerged is only those paths that remain unmerged after all
> steps.  record_unmerged_index_entries() could simply walk over all
> entries in paths and pick out the ones that were unmerged, but
> process_entries() has to walk over all paths, determine whether they
> can be merged, and determine what to record for the resulting tree for
> each path.  So, having it stash away the unmerged stuff is a simple
> optimization.
> 
> Renaming to merge_options_state or even just merge_state would be fine
> -- but any renaming done here will also affect merge-recursive.[ch].
> See the definition of merge_options in merge-recursive.  (For history,
> merge-recursive.h stuffed state into merge_options, which risked funny
> misusage patterns and made the API unnecessarily complex...and made it
> suggest that alternative algorithms needed to have the same state.
> So, the state was moved to a merge_options_internal struct.  That's
> not to say we can't rename, but it does need to be done in
> merge-recursive as well.)

> As for having collect_merge_info() return their calculations in return
> values, would that just end with me returning a struct
> merge_options_internal?  Or did you want each return value added to
> the function signature?  Each return value in the function signature
> makes sense right now for this super-simplified initial 20 patches,
> but what about when this data structure gains all kind of
> rename-related state that is collected, updated, and passed between
> these areas?  I'd have a huge number of "out" and "in" fields to every
> function.  Eventually, merge_options_internal (or whatever it might be
> renamed to) expands to the following, where I have to first define an
> extra enum and two extra structs so that you know the definitions of
> new types that show up in merge_options_internal:

> > > +     result->string = fullpath;
> > > +     result->util = path_info;
> > > +}
> > > +
> > >  static int collect_merge_info_callback(int n,
> > >                                      unsigned long mask,
> > >                                      unsigned long dirmask,
> > > @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
> > >        */
> > >       struct merge_options *opt = info->data;
> > >       struct merge_options_internal *opti = opt->priv;
> > > -     struct conflict_info *ci;
> > > +     struct string_list_item pi;  /* Path Info */
> > > +     struct conflict_info *ci; /* pi.util when there's a conflict */
> >
> > Looking ahead to patch 10, this seems more like "pi.util unless we know
> > for sure that there's no conflict".
> 
> That's too long for the line to remain at 80 characters; it's 16
> characters over the limit.  ;-)

>
> > > So these are placed in paths but not unmerged. I'm starting to wonder if
> > > struct merge_options_internal should be called merge_options_state or
> > > something, and each field having documentation about when they're used
> > > (or better yet, have functions like collect_merge_info() return their
> > > calculations in return values (which may be "out" parameters) instead of
> > > in this struct).
> >
> > Right, unmerged is only those paths that remain unmerged after all
> > steps.  record_unmerged_index_entries() could simply walk over all
> > entries in paths and pick out the ones that were unmerged, but
> > process_entries() has to walk over all paths, determine whether they
> > can be merged, and determine what to record for the resulting tree for
> > each path.  So, having it stash away the unmerged stuff is a simple
> > optimization.
> >
> > Renaming to merge_options_state or even just merge_state would be fine
> > -- but any renaming done here will also affect merge-recursive.[ch].
> > See the definition of merge_options in merge-recursive.  (For history,
> > merge-recursive.h stuffed state into merge_options, which risked funny
> > misusage patterns and made the API unnecessarily complex...and made it
> > suggest that alternative algorithms needed to have the same state.
> > So, the state was moved to a merge_options_internal struct.  That's
> > not to say we can't rename, but it does need to be done in
> > merge-recursive as well.)
>
> Ah, I see.
>
> > As for having collect_merge_info() return their calculations in return
> > values, would that just end with me returning a struct
> > merge_options_internal?  Or did you want each return value added to
> > the function signature?  Each return value in the function signature
> > makes sense right now for this super-simplified initial 20 patches,
> > but what about when this data structure gains all kind of
> > rename-related state that is collected, updated, and passed between
> > these areas?  I'd have a huge number of "out" and "in" fields to every
> > function.  Eventually, merge_options_internal (or whatever it might be
> > renamed to) expands to the following, where I have to first define an
> > extra enum and two extra structs so that you know the definitions of
> > new types that show up in merge_options_internal:
>
> [snip enums and structs]
>
> Good point. I should have realized that there would be much more to
> track.
>
> > > > +     result->string = fullpath;
> > > > +     result->util = path_info;
> > > > +}
> > > > +
> > > >  static int collect_merge_info_callback(int n,
> > > >                                      unsigned long mask,
> > > >                                      unsigned long dirmask,
> > > > @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
> > > >        */
> > > >       struct merge_options *opt = info->data;
> > > >       struct merge_options_internal *opti = opt->priv;
> > > > -     struct conflict_info *ci;
> > > > +     struct string_list_item pi;  /* Path Info */
> > > > +     struct conflict_info *ci; /* pi.util when there's a conflict */
> > >
> > > Looking ahead to patch 10, this seems more like "pi.util unless we know
> > > for sure that there's no conflict".
> >
> > That's too long for the line to remain at 80 characters; it's 16
> > characters over the limit.  ;-)
>
> Well, you could move the description onto its own line :-)

> +static void setup_path_info(struct merge_options *opt,
> +			    struct string_list_item *result,
> +			    const char *current_dir_name,
> +			    int current_dir_name_len,
> +			    char *fullpath, /* we'll take over ownership */
> +			    struct name_entry *names,
> +			    struct name_entry *merged_version,
> +			    unsigned is_null,     /* boolean */
> +			    unsigned df_conflict, /* boolean */
> +			    unsigned filemask,
> +			    unsigned dirmask,
> +			    int resolved          /* boolean */)
> +{
> +	struct conflict_info *path_info;

> +	path_info->merged.directory_name = current_dir_name;
> +	path_info->merged.basename_offset = current_dir_name_len;
> +	path_info->merged.clean = !!resolved;
> +	if (resolved) {
> +		path_info->merged.result.mode = merged_version->mode;
> +		oidcpy(&path_info->merged.result.oid, &merged_version->oid);
> +		path_info->merged.is_null = !!is_null;
> +	} else {
> +		int i;
> +
> +		for (i = 0; i < 3; i++) {
> +			path_info->pathnames[i] = fullpath;
> +			path_info->stages[i].mode = names[i].mode;
> +			oidcpy(&path_info->stages[i].oid, &names[i].oid);
> +		}
> +		path_info->filemask = filemask;
> +		path_info->dirmask = dirmask;
> +		path_info->df_conflict = !!df_conflict;
> +	}
> +	strmap_put(&opt->priv->paths, fullpath, path_info);
> +	result->string = fullpath;
> +	result->util = path_info;

> @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
>  	 */
>  	struct merge_options *opt = info->data;
>  	struct merge_options_internal *opti = opt->priv;
> -	struct conflict_info *ci;
> +	struct string_list_item pi;  /* Path Info */
> +	struct conflict_info *ci; /* pi.util when there's a conflict */

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > +static void setup_path_info(struct merge_options *opt,
> > +                         struct string_list_item *result,
> > +                         const char *current_dir_name,
> > +                         int current_dir_name_len,
> > +                         char *fullpath, /* we'll take over ownership */
> > +                         struct name_entry *names,
> > +                         struct name_entry *merged_version,
> > +                         unsigned is_null,     /* boolean */
> > +                         unsigned df_conflict, /* boolean */
> > +                         unsigned filemask,
> > +                         unsigned dirmask,
> > +                         int resolved          /* boolean */)
> > +{
> > +     struct conflict_info *path_info;
>
> In addition to my concerns below about 'conflict_info' versus
> 'merged_info', I was doubly confused that 'result' in the parameter
> list is given a variable named 'pi' for "path info" and result->util
> eventually is equal to this path_info. What if we renamed 'result'
> to 'pi' for "path info" here, then operated on 'pi->util' in this
> method?

>
> > +     path_info = xcalloc(1, resolved ? sizeof(struct merged_info) :
> > +                                       sizeof(struct conflict_info));
>
> Hm. I'm happy to have a `struct merged_info *` pointing to a
> `struct conflict_info`, but the opposite seems very dangerous.

> I imagine that in a large repo we will need many of these structs,
> but very few of them will actually need to be conflicts, so using
> 'struct conflict_info' always will lead to memory bloat. But in
> that case, would we not be better off with an array instead of a
> scattering of data across the heap?

> Perhaps 'struct conflict_info' shouldn't contain a 'struct merged_info'
> and instead be just the "extra" data. Then we could have a contiguous
> array of 'struct merged_info' values for most of the paths, but heap
> pointers for 'struct conflict_info' as necessary.
>
> It's also true that I haven't fully formed a mental model for how these
> are used in your algorithm, so I'll keep reading.

> > +     path_info->merged.directory_name = current_dir_name;
> > +     path_info->merged.basename_offset = current_dir_name_len;
> > +     path_info->merged.clean = !!resolved;
> > +     if (resolved) {
> > +             path_info->merged.result.mode = merged_version->mode;
> > +             oidcpy(&path_info->merged.result.oid, &merged_version->oid);
> > +             path_info->merged.is_null = !!is_null;
> > +     } else {
> > +             int i;
> > +
> > +             for (i = 0; i < 3; i++) {
> > +                     path_info->pathnames[i] = fullpath;
> > +                     path_info->stages[i].mode = names[i].mode;
> > +                     oidcpy(&path_info->stages[i].oid, &names[i].oid);
> > +             }
> > +             path_info->filemask = filemask;
> > +             path_info->dirmask = dirmask;
> > +             path_info->df_conflict = !!df_conflict;
> > +     }
> > +     strmap_put(&opt->priv->paths, fullpath, path_info);
> > +     result->string = fullpath;
> > +     result->util = path_info;
>
> This is set in all cases, so should we use it everywhere? Naturally,
> there might be a cost to the extra pointer indirection, so maybe we
> create a 'struct conflict_info *util' to operate on during this
> method, but set 'result->util = util' right after allocating so we
> know how it should behave?

> > @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
> >        */
> >       struct merge_options *opt = info->data;
> >       struct merge_options_internal *opti = opt->priv;
> > -     struct conflict_info *ci;
> > +     struct string_list_item pi;  /* Path Info */
> > +     struct conflict_info *ci; /* pi.util when there's a conflict */

> ...
>
> > +     setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
> > +                     names, NULL, 0, df_conflict, filemask, dirmask, 0);
> > +     ci = pi.util;
>
> Here is the use of 'pi' that I was talking about earlier.

>
> On Wed, Nov 11, 2020 at 7:26 AM Derrick Stolee <stolee@gmail.com> wrote:
> >
> > On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > > +static void setup_path_info(struct merge_options *opt,
> > > +                         struct string_list_item *result,
> > > +                         const char *current_dir_name,
> > > +                         int current_dir_name_len,
> > > +                         char *fullpath, /* we'll take over ownership */
> > > +                         struct name_entry *names,
> > > +                         struct name_entry *merged_version,
> > > +                         unsigned is_null,     /* boolean */
> > > +                         unsigned df_conflict, /* boolean */
> > > +                         unsigned filemask,
> > > +                         unsigned dirmask,
> > > +                         int resolved          /* boolean */)
> > > +{
> > > +     struct conflict_info *path_info;
> >
> > In addition to my concerns below about 'conflict_info' versus
> > 'merged_info', I was doubly confused that 'result' in the parameter
> > list is given a variable named 'pi' for "path info" and result->util
> > eventually is equal to this path_info. What if we renamed 'result'
> > to 'pi' for "path info" here, then operated on 'pi->util' in this
> > method?
>
> result->util (or pi->util if you rename) is void *, making it hard to
> operate on; you'd have to typecast at every usage.  Since it is used a
> *lot*, it makes sense to have a typed pointer, and then just set
> result->util to a copy of that value at the end.  That is what
> path_info is for.
>
> >
> > > +     path_info = xcalloc(1, resolved ? sizeof(struct merged_info) :
> > > +                                       sizeof(struct conflict_info));
> >
> > Hm. I'm happy to have a `struct merged_info *` pointing to a
> > `struct conflict_info`, but the opposite seems very dangerous.
>
> Yeah, this is perhaps the scariest bit, and if it were a side data
> structure rather than the fundamental main one that was central to the
> algorithm, then safety would trump performance concerns.  But since it
> is the main data structure and likely the biggest (once you count the
> various copies for each relevant path), then it might be worth the
> extra care needed to shave off the extra memory.  Maybe we can still
> tweak things to get some safety back without killing performance so
> let me consider each of your suggestions/questions.
>
> If I define it as a merged_info*, the compiler will only let me modify
> fields within the merged_info portion of the struct.  Should I
> typecast every line that touches the bits in the resolved==0 path
> where I need to set fields within the conflict_info portion?
> Alternatively, would a code flow like the following make you happier?
>
>     struct conflict_info *ci = NULL;
>     struct merge_info *mi = xcalloc(...);
>     result->util = mi;
>     /* Operate on mi */
>     ...
>     if (resolved)
>       return;
>    ci = mi;
>    /* Operate on ci */
>    ...
>
> In either case, the returned item has potentially different sizes, so
> the caller will still have to take care so I'm not sure how much extra
> this structure within setup_path_info() buys us.
>
> > Perhaps we should always use sizeof(struct conflict_info)?
>
> We could do that; it'd certainly waste memory as I expect many entries
> to be unmodified (on one or both sides of history).  But I'd way
> rather go this route than splitting or re-arranging this data
> structure.
>
> > We can use path_info->merged.clean to detect whether the rest of
> > the data is worth looking at. (Or, in your case, whether or not
> > it is allocated.)
>
> ci->merged.clean is used to determine whether to look at the rest of
> the data, yes -- and that's an enforced assumption throughout the code
> (as alluded to by the comment in the merge_options_internal data
> structure that "paths" maps pathanemes to merge_info and conflict_info
> types).  However, that is not quite the same as using the clean bit to
> determine if more data is allocated; something can be allocated as a
> conflict_info rather than a merged_info due to both sides making
> modifying the same path, but then a threeway content merge comes back
> clean and ci->merged.clean is updated from 0 to 1.  The extra data
> remains allocated, but nothing in the algorithm ever needs to use
> anything outside the merged bits for that path again.  (Actually, let
> me state that more forcefully: nothing is *allowed* to look outside
> the merged bits for that path once the clean bit is updated to 1).
>
> > I imagine that in a large repo we will need many of these structs,
> > but very few of them will actually need to be conflicts, so using
> > 'struct conflict_info' always will lead to memory bloat. But in
> > that case, would we not be better off with an array instead of a
> > scattering of data across the heap?
>
> Not sure what you're trying to solve here.  Putting them in an array
> would mean copying every single one of them every time the array is
> resized.  It would also make insertion or deletion very expensive.
> And it'd prevent O(1) lookup.  It'd be a horrible data structure all
> around.  Maybe you're assuming you know exactly how many entries you
> need and what they are before the merge algorithm starts?  I don't.
> In fact, I can't even give a good magnitude approximation of how many
> it'll be before a merge starts.  (Even if you assume it's a case where
> you have an index loaded and that index is related to the merge being
> done, the number can be and often is much smaller than the number of
> entries in the index.  And just to cover the extremes, in unusual
> cases the number might be much larger than the number of index entries
> if the merge base and side being merged in has far more paths).
>
> This was the whole point of the strmap API[1] I recently added --
> provide a hashmap specialized for the case where the key is a string.
> That way I get fast lookup, and relatively fast resize as the hash
> only contains pointers to the values, not a copy of the values.
>
> Is your concern that allocating many small structs is more expensive
> than allocating a huge block of them?  If so, yes that matters, but
> see the mem_pool related patches of the strmap API[1].
>
> [1] https://lore.kernel.org/git/pull.835.v5.git.git.1604622298.gitgitgadget@gmail.com/

> > Perhaps 'struct conflict_info' shouldn't contain a 'struct merged_info'
> > and instead be just the "extra" data. Then we could have a contiguous
> > array of 'struct merged_info' values for most of the paths, but heap
> > pointers for 'struct conflict_info' as necessary.
> >
> > It's also true that I haven't fully formed a mental model for how these
> > are used in your algorithm, so I'll keep reading.
>
> I don't understand how contiguous arrays are practical or desirable
> (I'm close to saying they're not possible, but one could employ some
> extremes to get them, as mentioned above).
>
> I could possibly have two strmaps; one mapping paths to a merge_info,
> and another (with fewer entries) mapping paths to a conflict_info.
> Seems like a royal pain, and would make for some pretty ugly code (I
> have other places that had to use two strmaps and I've hated it every
> time -- but those were cases of strmaps that were used much, much less
> than the "paths" one).  Might also slightly hurt perf
>
> > > +     path_info->merged.directory_name = current_dir_name;
> > > +     path_info->merged.basename_offset = current_dir_name_len;
> > > +     path_info->merged.clean = !!resolved;
> > > +     if (resolved) {
> > > +             path_info->merged.result.mode = merged_version->mode;
> > > +             oidcpy(&path_info->merged.result.oid, &merged_version->oid);
> > > +             path_info->merged.is_null = !!is_null;
> > > +     } else {
> > > +             int i;
> > > +
> > > +             for (i = 0; i < 3; i++) {
> > > +                     path_info->pathnames[i] = fullpath;
> > > +                     path_info->stages[i].mode = names[i].mode;
> > > +                     oidcpy(&path_info->stages[i].oid, &names[i].oid);
> > > +             }
> > > +             path_info->filemask = filemask;
> > > +             path_info->dirmask = dirmask;
> > > +             path_info->df_conflict = !!df_conflict;
> > > +     }
> > > +     strmap_put(&opt->priv->paths, fullpath, path_info);
> > > +     result->string = fullpath;
> > > +     result->util = path_info;
> >
> > This is set in all cases, so should we use it everywhere? Naturally,
> > there might be a cost to the extra pointer indirection, so maybe we
> > create a 'struct conflict_info *util' to operate on during this
> > method, but set 'result->util = util' right after allocating so we
> > know how it should behave?
>
> result->util is void*, so it's not just an extra pointer indirection,
> it's also the need to cast it to the appropriate type every time you
> want to use it.  It's easier to have that done via another copy of the
> pointer with the correct type, which is the reason for path_info.  So,
> essentially, I did use util everywhere, it's just that I spelled it as
> "path_info".  If I had named "path_info" "util" as you suggest,
> wouldn't everyone be annoyed that I used a lame name that didn't name
> the variable's purpose?
>
> Perhaps I should just add a comment saying that path_util is a typed
> alias/copy of result->util when I define it?
>
> > > @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
> > >        */
> > >       struct merge_options *opt = info->data;
> > >       struct merge_options_internal *opti = opt->priv;
> > > -     struct conflict_info *ci;
> > > +     struct string_list_item pi;  /* Path Info */
> > > +     struct conflict_info *ci; /* pi.util when there's a conflict */
>
> Perhaps here I should mention that ci is just a typed copy of pi.util
> (since pi.util is a void*).
>
> > ...
> >
> > > +     setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
> > > +                     names, NULL, 0, df_conflict, filemask, dirmask, 0);
> > > +     ci = pi.util;
> >
> > Here is the use of 'pi' that I was talking about earlier.
>
> ...although, to be fair, I don't actually have all that many uses of
> ci (at least not anymore) in this function.  So maybe typecasting
> pi.util each of the three-or-so times it is used isn't so bad?

> On Wed, Nov 11, 2020 at 10:16 AM Elijah Newren <newren@gmail.com> wrote:
>> This was the whole point of the strmap API[1] I recently added --
>> provide a hashmap specialized for the case where the key is a string.
>> That way I get fast lookup, and relatively fast resize as the hash
>> only contains pointers to the values, not a copy of the values.
>>
>> Is your concern that allocating many small structs is more expensive
>> than allocating a huge block of them?  If so, yes that matters, but
>> see the mem_pool related patches of the strmap API[1].
>>
>> [1] https://lore.kernel.org/git/pull.835.v5.git.git.1604622298.gitgitgadget@gmail.com/
> 
> 
> I just re-read what I wrote, here and below...and I need to apologize.
> I tend to write, edit, revise, and repeat while composing emails and
> the end result of my emails doesn't tend to reflect the path to get
> there; I looped through that cycle more times than most on this email.
> But, even worse, I added in a sentence or two that just shouldn't be
> included regardless.  I think in particular this one sounds extremely
> aggressive and dismissive which was not at all my intent.
> 
> I find your reviews to be very helpful, and I don't want to discourage
> them.  Hopefully my comments didn't come across anywhere near as
> strongly as they did to me on a second reading, but if they did, I'm
> sorry.

> On Wed, Nov 11, 2020 at 7:26 AM Derrick Stolee <stolee@gmail.com> wrote:
>>
>> On 11/2/2020 3:43 PM, Elijah Newren wrote:
>>> +static void setup_path_info(struct merge_options *opt,
>>> +                         struct string_list_item *result,
>>> +                         const char *current_dir_name,
>>> +                         int current_dir_name_len,
>>> +                         char *fullpath, /* we'll take over ownership */
>>> +                         struct name_entry *names,
>>> +                         struct name_entry *merged_version,
>>> +                         unsigned is_null,     /* boolean */
>>> +                         unsigned df_conflict, /* boolean */
>>> +                         unsigned filemask,
>>> +                         unsigned dirmask,
>>> +                         int resolved          /* boolean */)
>>> +{
>>> +     struct conflict_info *path_info;
>>
>> In addition to my concerns below about 'conflict_info' versus
>> 'merged_info', I was doubly confused that 'result' in the parameter
>> list is given a variable named 'pi' for "path info" and result->util
>> eventually is equal to this path_info. What if we renamed 'result'
>> to 'pi' for "path info" here, then operated on 'pi->util' in this
>> method?
> 
> result->util (or pi->util if you rename) is void *, making it hard to
> operate on; you'd have to typecast at every usage.  Since it is used a
> *lot*, it makes sense to have a typed pointer, and then just set
> result->util to a copy of that value at the end.  That is what
> path_info is for.

>>
>>> +     path_info = xcalloc(1, resolved ? sizeof(struct merged_info) :
>>> +                                       sizeof(struct conflict_info));
>>
>> Hm. I'm happy to have a `struct merged_info *` pointing to a
>> `struct conflict_info`, but the opposite seems very dangerous.
> 
> Yeah, this is perhaps the scariest bit, and if it were a side data
> structure rather than the fundamental main one that was central to the
> algorithm, then safety would trump performance concerns.  But since it
> is the main data structure and likely the biggest (once you count the
> various copies for each relevant path), then it might be worth the
> extra care needed to shave off the extra memory.  Maybe we can still
> tweak things to get some safety back without killing performance so
> let me consider each of your suggestions/questions.
> 
> If I define it as a merged_info*, the compiler will only let me modify
> fields within the merged_info portion of the struct.  Should I
> typecast every line that touches the bits in the resolved==0 path
> where I need to set fields within the conflict_info portion?
> Alternatively, would a code flow like the following make you happier?
> 
>     struct conflict_info *ci = NULL;
>     struct merge_info *mi = xcalloc(...);
>     result->util = mi;
>     /* Operate on mi */
>     ...
>     if (resolved)
>       return;
>    ci = mi;
>    /* Operate on ci */
>    ...
> 
> In either case, the returned item has potentially different sizes, so
> the caller will still have to take care so I'm not sure how much extra
> this structure within setup_path_info() buys us.

>> Perhaps we should always use sizeof(struct conflict_info)?
> 
> We could do that; it'd certainly waste memory as I expect many entries
> to be unmodified (on one or both sides of history).  But I'd way
> rather go this route than splitting or re-arranging this data
> structure.

>> We can use path_info->merged.clean to detect whether the rest of
>> the data is worth looking at. (Or, in your case, whether or not
>> it is allocated.)
> 
> ci->merged.clean is used to determine whether to look at the rest of
> the data, yes -- and that's an enforced assumption throughout the code
> (as alluded to by the comment in the merge_options_internal data
> structure that "paths" maps pathanemes to merge_info and conflict_info
> types).  However, that is not quite the same as using the clean bit to
> determine if more data is allocated; something can be allocated as a
> conflict_info rather than a merged_info due to both sides making
> modifying the same path, but then a threeway content merge comes back
> clean and ci->merged.clean is updated from 0 to 1.  The extra data
> remains allocated, but nothing in the algorithm ever needs to use
> anything outside the merged bits for that path again.  (Actually, let
> me state that more forcefully: nothing is *allowed* to look outside
> the merged bits for that path once the clean bit is updated to 1).

>> I imagine that in a large repo we will need many of these structs,
>> but very few of them will actually need to be conflicts, so using
>> 'struct conflict_info' always will lead to memory bloat. But in
>> that case, would we not be better off with an array instead of a
>> scattering of data across the heap?
> 
> Not sure what you're trying to solve here.  Putting them in an array
> would mean copying every single one of them every time the array is
> resized.  It would also make insertion or deletion very expensive.
> And it'd prevent O(1) lookup.  It'd be a horrible data structure all
> around.  Maybe you're assuming you know exactly how many entries you
> need and what they are before the merge algorithm starts?  I don't.
> In fact, I can't even give a good magnitude approximation of how many
> it'll be before a merge starts.  (Even if you assume it's a case where
> you have an index loaded and that index is related to the merge being
> done, the number can be and often is much smaller than the number of
> entries in the index.  And just to cover the extremes, in unusual
> cases the number might be much larger than the number of index entries
> if the merge base and side being merged in has far more paths).

> This was the whole point of the strmap API[1] I recently added --
> provide a hashmap specialized for the case where the key is a string.
> That way I get fast lookup, and relatively fast resize as the hash
> only contains pointers to the values, not a copy of the values.
> 
> Is your concern that allocating many small structs is more expensive
> than allocating a huge block of them?  If so, yes that matters, but
> see the mem_pool related patches of the strmap API[1].
> 
> [1] https://lore.kernel.org/git/pull.835.v5.git.git.1604622298.gitgitgadget@gmail.com/

>> Perhaps 'struct conflict_info' shouldn't contain a 'struct merged_info'
>> and instead be just the "extra" data. Then we could have a contiguous
>> array of 'struct merged_info' values for most of the paths, but heap
>> pointers for 'struct conflict_info' as necessary.
>>
>> It's also true that I haven't fully formed a mental model for how these
>> are used in your algorithm, so I'll keep reading.
> 
> I don't understand how contiguous arrays are practical or desirable
> (I'm close to saying they're not possible, but one could employ some
> extremes to get them, as mentioned above).
> 
> I could possibly have two strmaps; one mapping paths to a merge_info,
> and another (with fewer entries) mapping paths to a conflict_info.
> Seems like a royal pain, and would make for some pretty ugly code (I
> have other places that had to use two strmaps and I've hated it every
> time -- but those were cases of strmaps that were used much, much less
> than the "paths" one).  Might also slightly hurt perf

>>> +     path_info->merged.directory_name = current_dir_name;
>>> +     path_info->merged.basename_offset = current_dir_name_len;
>>> +     path_info->merged.clean = !!resolved;
>>> +     if (resolved) {
>>> +             path_info->merged.result.mode = merged_version->mode;
>>> +             oidcpy(&path_info->merged.result.oid, &merged_version->oid);
>>> +             path_info->merged.is_null = !!is_null;
>>> +     } else {
>>> +             int i;
>>> +
>>> +             for (i = 0; i < 3; i++) {
>>> +                     path_info->pathnames[i] = fullpath;
>>> +                     path_info->stages[i].mode = names[i].mode;
>>> +                     oidcpy(&path_info->stages[i].oid, &names[i].oid);
>>> +             }
>>> +             path_info->filemask = filemask;
>>> +             path_info->dirmask = dirmask;
>>> +             path_info->df_conflict = !!df_conflict;
>>> +     }
>>> +     strmap_put(&opt->priv->paths, fullpath, path_info);
>>> +     result->string = fullpath;
>>> +     result->util = path_info;
>>
>> This is set in all cases, so should we use it everywhere? Naturally,
>> there might be a cost to the extra pointer indirection, so maybe we
>> create a 'struct conflict_info *util' to operate on during this
>> method, but set 'result->util = util' right after allocating so we
>> know how it should behave?
> 
> result->util is void*, so it's not just an extra pointer indirection,
> it's also the need to cast it to the appropriate type every time you
> want to use it.  It's easier to have that done via another copy of the
> pointer with the correct type, which is the reason for path_info.  So,
> essentially, I did use util everywhere, it's just that I spelled it as
> "path_info".  If I had named "path_info" "util" as you suggest,
> wouldn't everyone be annoyed that I used a lame name that didn't name
> the variable's purpose?
> 
> Perhaps I should just add a comment saying that path_util is a typed
> alias/copy of result->util when I define it?

>>> @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
>>>        */
>>>       struct merge_options *opt = info->data;
>>>       struct merge_options_internal *opti = opt->priv;
>>> -     struct conflict_info *ci;
>>> +     struct string_list_item pi;  /* Path Info */
>>> +     struct conflict_info *ci; /* pi.util when there's a conflict */
> 
> Perhaps here I should mention that ci is just a typed copy of pi.util
> (since pi.util is a void*).
> 
>> ...
>>
>>> +     setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
>>> +                     names, NULL, 0, df_conflict, filemask, dirmask, 0);
>>> +     ci = pi.util;
>>
>> Here is the use of 'pi' that I was talking about earlier.
> 
> ...although, to be fair, I don't actually have all that many uses of
> ci (at least not anymore) in this function.  So maybe typecasting
> pi.util each of the three-or-so times it is used isn't so bad?

> @@ -353,6 +353,9 @@ static int string_list_df_name_compare(const char *one, const char *two)
>  
>  struct directory_versions {
>  	struct string_list versions;
> +	struct string_list offsets;

>  static void write_tree(struct object_id *result_oid,
> @@ -409,12 +412,100 @@ static void record_entry_for_tree(struct directory_versions *dir_metadata,
>  		/* nothing to record */
>  		return;
>  
> +	/*
> +	 * Note: write_completed_directories() already added
> +	 * entries for directories to dir_metadata->versions,
> +	 * so no need to handle ci->filemask == 0 again.
> +	 */
> +	if (!ci->merged.clean && !ci->filemask)
> +		return;
> +
>  	basename = path + ci->merged.basename_offset;
>  	assert(strchr(basename, '/') == NULL);
>  	string_list_append(&dir_metadata->versions,
>  			   basename)->util = &ci->merged.result;
>  }

> +static void write_completed_directories(struct merge_options *opt,
> +					const char *new_directory_name,
> +					struct directory_versions *info)
> +{
> +	const char *prev_dir;
> +	struct merged_info *dir_info = NULL;
> +	unsigned int offset;
> +	int wrote_a_new_tree = 0;
> +
> +	if (new_directory_name == info->last_directory)
> +		return;

> +	/*
> +	 * If we are just starting (last_directory is NULL), or last_directory
> +	 * is a prefix of the current directory, then we can just update
> +	 * last_directory and record the offset where we started this directory.
> +	 */
> +	if (info->last_directory == NULL ||
> +	    !strncmp(new_directory_name, info->last_directory,
> +		     info->last_directory_len)) {

> +		uintptr_t offset = info->versions.nr;
> +
> +		info->last_directory = new_directory_name;
> +		info->last_directory_len = strlen(info->last_directory);
> +		string_list_append(&info->offsets,
> +				   info->last_directory)->util = (void*)offset;
> +		return;
> +	}

> +	/*
> +	 * At this point, ne (next entry) is within a different directory
> +	 * than the last entry, so we need to create a tree object for all
> +	 * the entries in info->versions that are under info->last_directory.
> +	 */

> +	dir_info = strmap_get(&opt->priv->paths, info->last_directory);
> +	assert(dir_info);
> +	offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;
> +	if (offset == info->versions.nr) {
> +		dir_info->is_null = 1;
> +	} else {
> +		dir_info->result.mode = S_IFDIR;
> +		write_tree(&dir_info->result.oid, &info->versions, offset);
> +		wrote_a_new_tree = 1;
> +	}

> +	/*
> +	 * We've now used several entries from info->versions and one entry
> +	 * from info->offsets, so we get rid of those values.
> +	 */
> +	info->offsets.nr--;
> +	info->versions.nr = offset;

> +	/*
> +	 * Now we've got an OID for last_directory in dir_info.  We need to
> +	 * add it to info->versions for it to be part of the computation of
> +	 * its parent directories' OID.  But first, we have to find out what
> +	 * its' parent name was and whether that matches the previous
> +	 * info->offsets or we need to set up a new one.
> +	 */
> +	prev_dir = info->offsets.nr == 0 ? NULL :
> +		   info->offsets.items[info->offsets.nr-1].string;
> +	if (new_directory_name != prev_dir) {
> +		uintptr_t c = info->versions.nr;
> +		string_list_append(&info->offsets,
> +				   new_directory_name)->util = (void*)c;
> +	}

> +	/*
> +	 * Okay, finally record OID for last_directory in info->versions,
> +	 * and update last_directory.
> +	 */
> +	if (wrote_a_new_tree) {
> +		const char *dir_name = strrchr(info->last_directory, '/');
> +		dir_name = dir_name ? dir_name+1 : info->last_directory;
> +		string_list_append(&info->versions, dir_name)->util = dir_info;
> +	}
> +	info->last_directory = new_directory_name;
> +	info->last_directory_len = strlen(info->last_directory);
> +}

> @@ -541,22 +635,27 @@ static void process_entries(struct merge_options *opt,
>  		 */
>  		struct conflict_info *ci = entry->util;
>  
> +		write_completed_directories(opt, ci->merged.directory_name,
> +					    &dir_metadata);
>  		if (ci->merged.clean)
>  			record_entry_for_tree(&dir_metadata, path, ci);
>  		else
>  			process_entry(opt, path, ci, &dir_metadata);
>  	}

> -	/*
> -	 * TODO: We can't actually write a tree yet, because dir_metadata just
> -	 * contains all basenames of all files throughout the tree with their
> -	 * mode and hash.  Not only is that a nonsensical tree, it will have
> -	 * lots of duplicates for paths such as "Makefile" or ".gitignore".
> -	 */
> -	die("Not yet implemented; need to process subtrees separately");
> +	if (dir_metadata.offsets.nr != 1 ||
> +	    (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
> +		printf("dir_metadata.offsets.nr = %d (should be 1)\n",
> +		       dir_metadata.offsets.nr);
> +		printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
> +		       (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
> +		fflush(stdout);
> +		BUG("dir_metadata accounting completely off; shouldn't happen");
> +	}

>
> Firstly, from [1]:
>
> > Thanks for the reviews!  I was hoping to see some comments on patch
> > 15, as it's possibly the gnarliest.  It's a relatively straightforward
> > algorithm, just lots of bookkeeping.
>
> I was planning to send this out yesterday, but couldn't finish it. :-P
> Indeed, a lot of things to think about.
>
> [1] https://lore.kernel.org/git/CABPp-BFgQX6Ash03x7z+RfE3ytbw3x0DzDSBrGddgMr_soODoA@mail.gmail.com/
>
> [snip commit message]
>
> Thanks for the thorough explanation.
>
> > @@ -353,6 +353,9 @@ static int string_list_df_name_compare(const char *one, const char *two)
> >
> >  struct directory_versions {
> >       struct string_list versions;
> > +     struct string_list offsets;
>
> Looking below (and at the explanation in the commit message), this is a
> mapping from full paths to integers casted to the pointer type.
>
> > +     const char *last_directory;
> > +     unsigned last_directory_len;
>
> Is this just the last entry in "versions"?

> >  static void write_tree(struct object_id *result_oid,
> > @@ -409,12 +412,100 @@ static void record_entry_for_tree(struct directory_versions *dir_metadata,
> >               /* nothing to record */
> >               return;
> >
> > +     /*
> > +      * Note: write_completed_directories() already added
> > +      * entries for directories to dir_metadata->versions,
> > +      * so no need to handle ci->filemask == 0 again.
> > +      */
> > +     if (!ci->merged.clean && !ci->filemask)
> > +             return;
> > +
> >       basename = path + ci->merged.basename_offset;
> >       assert(strchr(basename, '/') == NULL);
> >       string_list_append(&dir_metadata->versions,
> >                          basename)->util = &ci->merged.result;
> >  }
>
> Conceptually, I can see how the algorithm below inserts directories, but
> I don't understand the significance of "!ci->merged.clean" in the change
> above.

> > +static void write_completed_directories(struct merge_options *opt,
> > +                                     const char *new_directory_name,
> > +                                     struct directory_versions *info)
> > +{
> > +     const char *prev_dir;
> > +     struct merged_info *dir_info = NULL;
> > +     unsigned int offset;
> > +     int wrote_a_new_tree = 0;
> > +
> > +     if (new_directory_name == info->last_directory)
> > +             return;
>
> Pointer equality is OK here presumably because of the string interning
> of directory names.

> I'm starting to think that it might be too difficult to keep track of
> where strings are interned. Maybe there should be a data structure
> containing all interned strings, and make the path a struct or something
> like that (to clearly indicate that the string inside comes from the
> interned string data structure).

> > +     /*
> > +      * If we are just starting (last_directory is NULL), or last_directory
> > +      * is a prefix of the current directory, then we can just update
> > +      * last_directory and record the offset where we started this directory.
> > +      */
> > +     if (info->last_directory == NULL ||
> > +         !strncmp(new_directory_name, info->last_directory,
> > +                  info->last_directory_len)) {
>
> Git has starts_with() for prefix checking. (May not be as optimized as
> this one, though.)
>
> > +             uintptr_t offset = info->versions.nr;
> > +
> > +             info->last_directory = new_directory_name;
> > +             info->last_directory_len = strlen(info->last_directory);
> > +             string_list_append(&info->offsets,
> > +                                info->last_directory)->util = (void*)offset;
> > +             return;
> > +     }
>
> Due to the way this is sorted, there might be a jump of 2 or more
> directories. (The commit message also provides such an example - from ""
> to "src/moduleB", without going through "src".)
>
> > +     /*
> > +      * At this point, ne (next entry) is within a different directory
> > +      * than the last entry, so we need to create a tree object for all
> > +      * the entries in info->versions that are under info->last_directory.
> > +      */
>
> There's no "ne" below.

> > +     dir_info = strmap_get(&opt->priv->paths, info->last_directory);
> > +     assert(dir_info);
> > +     offset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;
> > +     if (offset == info->versions.nr) {
> > +             dir_info->is_null = 1;
> > +     } else {
> > +             dir_info->result.mode = S_IFDIR;
> > +             write_tree(&dir_info->result.oid, &info->versions, offset);
> > +             wrote_a_new_tree = 1;
> > +     }
>
> I was trying to figure out the cases in which offset would be
> info->versions.nr - if such a case existed, and if yes, would it be
> incorrect to skip creating such a tree because presumably this offset
> exists in info->offsets for a reason. Do you know in which situation
> offset would equal info->versions.nr?

>
> > +     /*
> > +      * We've now used several entries from info->versions and one entry
> > +      * from info->offsets, so we get rid of those values.
> > +      */
> > +     info->offsets.nr--;
> > +     info->versions.nr = offset;
>
> OK.
>
> > +     /*
> > +      * Now we've got an OID for last_directory in dir_info.  We need to
> > +      * add it to info->versions for it to be part of the computation of
> > +      * its parent directories' OID.  But first, we have to find out what
> > +      * its' parent name was and whether that matches the previous
> > +      * info->offsets or we need to set up a new one.
> > +      */
> > +     prev_dir = info->offsets.nr == 0 ? NULL :
> > +                info->offsets.items[info->offsets.nr-1].string;
> > +     if (new_directory_name != prev_dir) {
> > +             uintptr_t c = info->versions.nr;
> > +             string_list_append(&info->offsets,
> > +                                new_directory_name)->util = (void*)c;
> > +     }
>
> Because of the possible jump of 2 or more directories that I mentioned
> earlier, there may be gaps in the offsets. So it makes sense that we
> sometimes need to insert an intermediate one.
>
> I wonder if the code would be clearer if we had explicit "begin tree"
> and "end tree" steps just like in list-objects-filter.c (LOFS_BEGIN_TREE
> and LOFS_END_TREE). Here we have "end tree" (because of the way the
> entries were sorted) but not "begin tree". If we had "begin tree", we
> probably would be able to create the necessary offsets in a loop at that
> stage, and the reasoning about the contents of the offsets would not be
> so complicated.
>
> If we really only want one side (i.e. you don't want to introduce a
> synthetic entry just to mark the end or the beginning), then my personal
> experience is that having the "begin" side is easier to understand, as
> the state is more natural and easier to reason about. (Unlike here,
> where there could be gaps in the offsets and the reader has to
> understand that the gaps will be filled just in time.) But that may just
> be my own experience.

>
> > +     /*
> > +      * Okay, finally record OID for last_directory in info->versions,
> > +      * and update last_directory.
> > +      */
> > +     if (wrote_a_new_tree) {
> > +             const char *dir_name = strrchr(info->last_directory, '/');
> > +             dir_name = dir_name ? dir_name+1 : info->last_directory;
> > +             string_list_append(&info->versions, dir_name)->util = dir_info;
> > +     }
> > +     info->last_directory = new_directory_name;
> > +     info->last_directory_len = strlen(info->last_directory);
> > +}
>
> OK - several entries in info->versions were deleted earlier (through
> info->versions.nr = offset), and we add one here to represent the tree
> containing all those deleted versions.
>
> > @@ -541,22 +635,27 @@ static void process_entries(struct merge_options *opt,
> >                */
> >               struct conflict_info *ci = entry->util;
> >
> > +             write_completed_directories(opt, ci->merged.directory_name,
> > +                                         &dir_metadata);
> >               if (ci->merged.clean)
> >                       record_entry_for_tree(&dir_metadata, path, ci);
> >               else
> >                       process_entry(opt, path, ci, &dir_metadata);
> >       }
>
> Trying to make sense of this: we pass in the directory name of the
> current entry so that if the last directory is *not* a prefix of the
> current directory (so we either went up a directory or went sideways),
> then we write a tree (unless offset == info->versions.nr, which as I
> stated above, I still don't fully understand - I thought we would always
> have to write a tree). So maybe the name of the function should be
> "write_completed_directory" (and document it as "write a tree if
> ???"), since we write at most one.

> In this kind of algorithm (where intermediate accumulated results are
> being written), there needs to be a last write after the loop that
> writes whatever's left in the accumulation buffer. I do see it below
> ("write_tree"), so that's good.
>
> > -     /*
> > -      * TODO: We can't actually write a tree yet, because dir_metadata just
> > -      * contains all basenames of all files throughout the tree with their
> > -      * mode and hash.  Not only is that a nonsensical tree, it will have
> > -      * lots of duplicates for paths such as "Makefile" or ".gitignore".
> > -      */
> > -     die("Not yet implemented; need to process subtrees separately");
> > +     if (dir_metadata.offsets.nr != 1 ||
> > +         (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
> > +             printf("dir_metadata.offsets.nr = %d (should be 1)\n",
> > +                    dir_metadata.offsets.nr);
> > +             printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
> > +                    (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
> > +             fflush(stdout);
> > +             BUG("dir_metadata accounting completely off; shouldn't happen");
> > +     }
>
> Sanity check, OK.
>
> [snip rest]
>
> In summary, I think that the code would be easier to understand (for
> everyone) if there were both BEGIN_TREE and END_TREE entries. And for me
> personally, once the offset == info->versions.nr part is clarified
> (perhaps there is something obvious that I'm missing).

>
> On Thu, Nov 12, 2020 at 12:15 PM Jonathan Tan <jonathantanmy@google.com> wrote:
> >
> > > +     /*
> > > +      * Now we've got an OID for last_directory in dir_info.  We need to
> > > +      * add it to info->versions for it to be part of the computation of
> > > +      * its parent directories' OID.  But first, we have to find out what
> > > +      * its' parent name was and whether that matches the previous
> > > +      * info->offsets or we need to set up a new one.
> > > +      */
> > > +     prev_dir = info->offsets.nr == 0 ? NULL :
> > > +                info->offsets.items[info->offsets.nr-1].string;
> > > +     if (new_directory_name != prev_dir) {
> > > +             uintptr_t c = info->versions.nr;
> > > +             string_list_append(&info->offsets,
> > > +                                new_directory_name)->util = (void*)c;
> > > +     }
> >
> > Because of the possible jump of 2 or more directories that I mentioned
> > earlier, there may be gaps in the offsets. So it makes sense that we
> > sometimes need to insert an intermediate one.
> >
> > I wonder if the code would be clearer if we had explicit "begin tree"
> > and "end tree" steps just like in list-objects-filter.c (LOFS_BEGIN_TREE
> > and LOFS_END_TREE). Here we have "end tree" (because of the way the
> > entries were sorted) but not "begin tree". If we had "begin tree", we
> > probably would be able to create the necessary offsets in a loop at that
> > stage, and the reasoning about the contents of the offsets would not be
> > so complicated.
> >
> > If we really only want one side (i.e. you don't want to introduce a
> > synthetic entry just to mark the end or the beginning), then my personal
> > experience is that having the "begin" side is easier to understand, as
> > the state is more natural and easier to reason about. (Unlike here,
> > where there could be gaps in the offsets and the reader has to
> > understand that the gaps will be filled just in time.) But that may just
> > be my own experience.
>
> Interesting, I'll take a look into it.
>

>
> > For now, I'll keep the code as-is, but add more comments to both the
> > data structure and the code.  If I've missed something about how I
> > could make use of your BEGIN_TREE idea, let me know and I'll look at
> > it again.
>
> In collect_merge_info_callback(), you call setup_path_info() to add to
> opt->priv->paths, then call traverse_trees() (which recursively calls
> collect_merge_info_callback()). I was thinking that in addition to doing
> that, you could call setup_path_info() a second time, but teach it to
> add a synthetic path (maybe have a special bit in struct conflict_info
> or something like that) that indicates "this is the end of the tree".
> Subsequent code can notice that bit and not do the normal processing,
> but instead do end-of-tree processing.

> On Tue, Nov 24, 2020 at 6:07 PM Jonathan Tan <jonathantanmy@google.com> wrote:
> >
> > > For now, I'll keep the code as-is, but add more comments to both the
> > > data structure and the code.  If I've missed something about how I
> > > could make use of your BEGIN_TREE idea, let me know and I'll look at
> > > it again.
> >
> > In collect_merge_info_callback(), you call setup_path_info() to add to
> > opt->priv->paths, then call traverse_trees() (which recursively calls
> > collect_merge_info_callback()). I was thinking that in addition to doing
> > that, you could call setup_path_info() a second time, but teach it to
> > add a synthetic path (maybe have a special bit in struct conflict_info
> > or something like that) that indicates "this is the end of the tree".
> > Subsequent code can notice that bit and not do the normal processing,
> > but instead do end-of-tree processing.
> 
> So, I realized that I already had end-of-tree markers -- the
> directories themselves.  But due to some other weirdness in how I had
> built up the processing, the existence of those markers was both
> obscured, and deliberately side-stepped.  So, I did a little
> restructuring so we can use these as actual end-of-tree markers more
> directly.

> > Having said that, maybe it will turn out that your additional comments
> > in v3 will be clearer, and we wouldn't need the synthetic entry.
> 
> Hopefully it's clearer now, but the entries aren't synthetic.  My big
> opt->priv->paths strmap with all full relative paths contained all
> files _and_ directories already, and now I just use the directory
> markers more directly.  Hopefully the extra comments help too.

> +static void write_tree(struct object_id *result_oid,
> +		       struct string_list *versions,
> +		       unsigned int offset)
> +{
> +	size_t maxlen = 0;
> +	unsigned int nr = versions->nr - offset;
> +	struct strbuf buf = STRBUF_INIT;
> +	struct string_list relevant_entries = STRING_LIST_INIT_NODUP;
> +	int i;
> +
> +	/*
> +	 * We want to sort the last (versions->nr-offset) entries in versions.
> +	 * Do so by abusing the string_list API a bit: make another string_list
> +	 * that contains just those entries and then sort them.
> +	 *
> +	 * We won't use relevant_entries again and will let it just pop off the
> +	 * stack, so there won't be allocation worries or anything.
> +	 */
> +	relevant_entries.items = versions->items + offset;
> +	relevant_entries.nr = versions->nr - offset;
> +	string_list_sort(&relevant_entries);
> +
> +	/* Pre-allocate some space in buf */
> +	for (i = 0; i < nr; i++) {
> +		maxlen += strlen(versions->items[offset+i].string) + 34;

>
> > +static void write_tree(struct object_id *result_oid,
> > +                    struct string_list *versions,
> > +                    unsigned int offset)
> > +{
> > +     size_t maxlen = 0;
> > +     unsigned int nr = versions->nr - offset;
> > +     struct strbuf buf = STRBUF_INIT;
> > +     struct string_list relevant_entries = STRING_LIST_INIT_NODUP;
> > +     int i;
> > +
> > +     /*
> > +      * We want to sort the last (versions->nr-offset) entries in versions.
> > +      * Do so by abusing the string_list API a bit: make another string_list
> > +      * that contains just those entries and then sort them.
> > +      *
> > +      * We won't use relevant_entries again and will let it just pop off the
> > +      * stack, so there won't be allocation worries or anything.
> > +      */
> > +     relevant_entries.items = versions->items + offset;
> > +     relevant_entries.nr = versions->nr - offset;
> > +     string_list_sort(&relevant_entries);
> > +
> > +     /* Pre-allocate some space in buf */
> > +     for (i = 0; i < nr; i++) {
> > +             maxlen += strlen(versions->items[offset+i].string) + 34;
>
> Probably should include the_hash_algo->rawsz instead of hardcoding 34.

> We want to handle paths below a directory before needing to handle the
> directory itself.  Also, we want to handle the directory immediately
> after the paths below it, so we can't use simple lexicographic ordering
> from strcmp (which would insert foo.txt between foo and foo/file.c).
> Copy string_list_df_name_compare() from merge-recursive.c, and set up a
> string list of paths sorted by that function so that we can iterate in
> the desired order.

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > We want to handle paths below a directory before needing to handle the
> > directory itself.  Also, we want to handle the directory immediately
> > after the paths below it, so we can't use simple lexicographic ordering
> > from strcmp (which would insert foo.txt between foo and foo/file.c).
> > Copy string_list_df_name_compare() from merge-recursive.c, and set up a
> > string list of paths sorted by that function so that we can iterate in
> > the desired order.
>
> This is at least the second time we've copied something from
> merge-recursive.c. Should we be starting a merge-utils.[c|h] to group
> these together under a common implementation?

> > +     /* Put every entry from paths into plist, then sort */
> >       strmap_for_each_entry(&opt->priv->paths, &iter, e) {
> > +             string_list_append(&plist, e->key)->util = e->value;
> > +     }
>
> nit: are braces required here?

> @@ -442,6 +464,7 @@ static void process_entries(struct merge_options *opt,
>  	struct strmap_entry *e;
>  	struct string_list plist = STRING_LIST_INIT_NODUP;
>  	struct string_list_item *entry;
> +	struct directory_versions dir_metadata;
>  
>  	if (strmap_empty(&opt->priv->paths)) {
>  		oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
> @@ -458,6 +481,9 @@ static void process_entries(struct merge_options *opt,
>  	plist.cmp = string_list_df_name_compare;
>  	string_list_sort(&plist);
>  
> +	/* other setup */
> +	string_list_init(&dir_metadata.versions, 0);
> +

>
> > +struct directory_versions {
> > +     struct string_list versions;
>
> Maybe comment that this is an unordered list of basenames to <whatever
> the type of ci->merged.result is>.

>
> > @@ -442,6 +464,7 @@ static void process_entries(struct merge_options *opt,
> >       struct strmap_entry *e;
> >       struct string_list plist = STRING_LIST_INIT_NODUP;
> >       struct string_list_item *entry;
> > +     struct directory_versions dir_metadata;
> >
> >       if (strmap_empty(&opt->priv->paths)) {
> >               oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
> > @@ -458,6 +481,9 @@ static void process_entries(struct merge_options *opt,
> >       plist.cmp = string_list_df_name_compare;
> >       string_list_sort(&plist);
> >
> > +     /* other setup */
> > +     string_list_init(&dir_metadata.versions, 0);
> > +
>
> Might be clearer to just initialize dir_metadata as {
> STRING_LIST_INIT_NODUP }.

> On Wed, Nov 11, 2020 at 12:01 PM Jonathan Tan <jonathantanmy@google.com> wrote:
> >
> > > +struct directory_versions {
> > > +     struct string_list versions;
> >
> > Maybe comment that this is an unordered list of basenames to <whatever
> > the type of ci->merged.result is>.
> 
> There actually is an order, and it's important.  It's reverse
> lexicographic order of full pathnames (the ordering comes from the
> fact that process_entries() iterates paths in that order).  The
> reasons for that ordering are (1) all the basenames within a directory
> are adjacent so that I can write out a tree for a directory as soon as
> it is done, and (2) paths within a directory are listed before the
> directory itself so that I get the necessary info for subtrees before
> trying to write out their parent trees.
> 
> It's not until later patches that I take advantage of this ordering
> (and when I do I have a very long commit message to describe it all),
> but I can add a comment that this is a list of basenames to
> merge_info.

> @@ -99,6 +99,15 @@ static int collect_merge_info_callback(int n,
>  	unsigned mbase_null = !(mask & 1);
>  	unsigned side1_null = !(mask & 2);
>  	unsigned side2_null = !(mask & 4);
> +	unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
> +					names[0].mode == names[1].mode &&
> +					oideq(&names[0].oid, &names[1].oid));
> +	unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
> +					names[0].mode == names[2].mode &&
> +					oideq(&names[0].oid, &names[2].oid));
> +	unsigned sides_match = (!side1_null && !side2_null &&
> +				names[1].mode == names[2].mode &&
> +				oideq(&names[1].oid, &names[2].oid));

> +			if (i == 1 && side1_matches_mbase)
> +				t[1] = t[0];
> +			else if (i == 2 && side2_matches_mbase)
> +				t[2] = t[0];
> +			else if (i == 2 && sides_match)
> +				t[2] = t[1];

> +			else {
> +				const struct object_id *oid = NULL;
> +				if (dirmask & 1)
> +					oid = &names[i].oid;
> +				buf[i] = fill_tree_descriptor(opt->repo,
> +							      t + i, oid);
> +			}

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > @@ -99,6 +99,15 @@ static int collect_merge_info_callback(int n,
> >       unsigned mbase_null = !(mask & 1);
> >       unsigned side1_null = !(mask & 2);
> >       unsigned side2_null = !(mask & 4);
> > +     unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
> > +                                     names[0].mode == names[1].mode &&
> > +                                     oideq(&names[0].oid, &names[1].oid));
> > +     unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
> > +                                     names[0].mode == names[2].mode &&
> > +                                     oideq(&names[0].oid, &names[2].oid));
> > +     unsigned sides_match = (!side1_null && !side2_null &&
> > +                             names[1].mode == names[2].mode &&
> > +                             oideq(&names[1].oid, &names[2].oid));
>
> If the *_null values were in an array, instead, then all of these
> lines could be grouped as a macro:
>
>         unsigned null_oid[3] = {
>                 !(mask & 1),
>                 !(mask & 2),
>                 !(mask & 4)
>         };
>
>         #define trivial_merge(i,j) (!null_oid[i] && !null_oid[j] && \
>                                     names[i].mode == names[j].mode && \
>                                     oideq(&names[i].oid, &names[j].oid))
>
>         unsigned side1_matches_mbase = trivial_merge(0, 1);
>         unsigned side2_matches_mbase = trivial_merge(0, 2);
>         unsigned sides_match = trivial_merge(1, 2);

> I briefly considered making these last three an array, as well,
> except the loop below doesn't use 'i' in a symmetrical way:
>
> > +                     if (i == 1 && side1_matches_mbase)
> > +                             t[1] = t[0];
> > +                     else if (i == 2 && side2_matches_mbase)
> > +                             t[2] = t[0];
> > +                     else if (i == 2 && sides_match)
> > +                             t[2] = t[1];
>
> Since the 'i == 2' case has two possible options, it wouldn't be
> possible to just have 'side_matches[i]' here.
>
> > +                     else {
> > +                             const struct object_id *oid = NULL;
> > +                             if (dirmask & 1)
> > +                                     oid = &names[i].oid;
> > +                             buf[i] = fill_tree_descriptor(opt->repo,
> > +                                                           t + i, oid);
> > +                     }
>
> I do appreciate the reduced recursion here!

> On Wed, Nov 11, 2020 at 6:51 AM Derrick Stolee <stolee@gmail.com> wrote:
> > If the *_null values were in an array, instead, then all of these
> > lines could be grouped as a macro:
> >
> >         unsigned null_oid[3] = {
> >                 !(mask & 1),
> >                 !(mask & 2),
> >                 !(mask & 4)
> >         };
>
> Hmm, I like it.  I think I'll rename trivial_merge() to
> non_null_match() (trivial merge suggests it can immediately be
> resolved which is not necessarily true if rename detection is on), but
> otherwise I'll use this.

> Various places in merge-recursive used an err() function when it hit
> some kind of unrecoverable error.  That code was from the reusable bits
> of merge-recursive.c that we liked, such as merge_3way, writing object
> files to the object store, reading blobs from the object store, etc.  So
> create a similar function to allow us to port that code over, and use it
> for when we detect problems returned from collect_merge_info()'s
> traverse_trees() call, which we will be adding next.
> 
> Signed-off-by: Elijah Newren <newren@gmail.com>
> ---
>  merge-ort.c | 27 ++++++++++++++++++++++++++-
>  1 file changed, 26 insertions(+), 1 deletion(-)
> 
> diff --git a/merge-ort.c b/merge-ort.c
> index df97a54773..537da9f6df 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -61,11 +61,28 @@ struct conflict_info {
>  	unsigned match_mask:3;
>  };
>  
> +static int err(struct merge_options *opt, const char *err, ...)
> +{
> +	va_list params;
> +	struct strbuf sb = STRBUF_INIT;
> +
> +	strbuf_addstr(&sb, "error: ");
> +	va_start(params, err);
> +	strbuf_vaddf(&sb, err, params);
> +	va_end(params);
> +
> +	error("%s", sb.buf);
> +	strbuf_release(&sb);
> +
> +	return -1;
> +}
> +

>  static int collect_merge_info(struct merge_options *opt,
>  			      struct tree *merge_base,
>  			      struct tree *side1,
>  			      struct tree *side2)
>  {
> +	/* TODO: Implement this using traverse_trees() */
>  	die("Not yet implemented.");
>  }

> > +static int err(struct merge_options *opt, const char *err, ...)
> > +{
> > +     va_list params;
> > +     struct strbuf sb = STRBUF_INIT;
> > +
> > +     strbuf_addstr(&sb, "error: ");
> > +     va_start(params, err);
> > +     strbuf_vaddf(&sb, err, params);
> > +     va_end(params);
> > +
> > +     error("%s", sb.buf);
> > +     strbuf_release(&sb);
> > +
> > +     return -1;
> > +}
> > +
>
> This seems simple enough to have a duplicate copy lying
> around. Do you anticipate that all common code will live
> in the same file eventually? Or will these two static err()
> method always be duplicated?

> Aside: I wonder if these errors could be logged using trace2
> primitives, to assist diagnosing problems with merges. CC'ing
> Jeff Hostetler if he has an opinion.
>
> >  static int collect_merge_info(struct merge_options *opt,
> >                             struct tree *merge_base,
> >                             struct tree *side1,
> >                             struct tree *side2)
> >  {
> > +     /* TODO: Implement this using traverse_trees() */
> >       die("Not yet implemented.");
> >  }
>
> This comment looks to be applied to the wrong patch.

> On Wed, Nov 11, 2020 at 5:58 AM Derrick Stolee <stolee@gmail.com> wrote:
>> This seems simple enough to have a duplicate copy lying
>> around. Do you anticipate that all common code will live
>> in the same file eventually? Or will these two static err()
>> method always be duplicated?
> 
> I anticipate that merge-recursive.[ch] will be deleted.
> 
> merge-ort was what I wanted to modify merge-recursive.[ch] to be, but
> Junio suggested doing it as a different merge backend since it had
> invasive changes, so that we could have an easy way to try it out and
> fallback to the known good algorithm until we had sufficient comfort
> with the new algorithm to switch over to it.

> merged_info contains all relevant information for a non-conflicted
> entry.  conflict_info contains a merged_info, plus any additional
> information about a conflict such as the higher orders stages involved
> and the names of the paths those came from (handy once renames get
> involved).  If an entry remains conflicted, the merged_info portion of a
> conflict_info will later be filled with whatever version of the file
> should be placed in the working directory (e.g. an as-merged-as-possible
> variation that contains conflict markers).

> diff --git a/merge-ort.c b/merge-ort.c
> index b487901d3e..9d5ea0930d 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -17,6 +17,46 @@
>  #include "cache.h"
>  #include "merge-ort.h"
>  
> +#include "strmap.h"
> +
> +struct merge_options_internal {
> +	struct strmap paths;    /* maps path -> (merged|conflict)_info */
> +	struct strmap unmerged; /* maps path -> conflict_info */
> +	const char *current_dir_name;
> +	int call_depth;
> +};

> +struct merged_info {
> +	struct version_info result;
> +	unsigned is_null:1;
> +	unsigned clean:1;
> +	size_t basename_offset;
> +	 /*
> +	  * Containing directory name.  Note that we assume directory_name is
> +	  * constructed such that
> +	  *    strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
> +	  * i.e. string equality is equivalent to pointer equality.  For this
> +	  * to hold, we have to be careful setting directory_name.
> +	  */
> +	const char *directory_name;
> +};

> > merged_info contains all relevant information for a non-conflicted
> > entry.  conflict_info contains a merged_info, plus any additional
> > information about a conflict such as the higher orders stages involved
> > and the names of the paths those came from (handy once renames get
> > involved).  If an entry remains conflicted, the merged_info portion of a
> > conflict_info will later be filled with whatever version of the file
> > should be placed in the working directory (e.g. an as-merged-as-possible
> > variation that contains conflict markers).
>
> I think that this information should be in the .c file.

> > diff --git a/merge-ort.c b/merge-ort.c
> > index b487901d3e..9d5ea0930d 100644
> > --- a/merge-ort.c
> > +++ b/merge-ort.c
> > @@ -17,6 +17,46 @@
> >  #include "cache.h"
> >  #include "merge-ort.h"
> >
> > +#include "strmap.h"
> > +
> > +struct merge_options_internal {
> > +     struct strmap paths;    /* maps path -> (merged|conflict)_info */
> > +     struct strmap unmerged; /* maps path -> conflict_info */
> > +     const char *current_dir_name;
> > +     int call_depth;
> > +};
>
> Maybe document if the path is from the root of the directory or just the
> filename as it appears in a tree object?

> Also, looking ahead, I see that current_dir_name is used as a temporary
> variable in the recursive calls to collect_merge_info_callback(). I
> would prefer if current_dir_name went in the cbdata to that function
> instead, but if that's not possible, maybe document here that
> current_dir_name is only used in collect_merge_info_callback(), and
> temporarily at that.

> > +struct version_info {
> > +     struct object_id oid;
> > +     unsigned short mode;
> > +};
>
> OK.
>
> > +struct merged_info {
> > +     struct version_info result;
> > +     unsigned is_null:1;
> > +     unsigned clean:1;
> > +     size_t basename_offset;
> > +      /*
> > +       * Containing directory name.  Note that we assume directory_name is
> > +       * constructed such that
> > +       *    strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
> > +       * i.e. string equality is equivalent to pointer equality.  For this
> > +       * to hold, we have to be careful setting directory_name.
> > +       */
> > +     const char *directory_name;
> > +};
>
> I'm not sure how most of the fields in this struct are to be used, but
> perhaps that will be clearer once I read the subsequent code.
>
> > +struct conflict_info {
> > +     struct merged_info merged;
> > +     struct version_info stages[3];
> > +     const char *pathnames[3];
>
> Why would these be different across stages? (Rename detection?)

>
> > +     unsigned df_conflict:1;
>
> OK.
>
> > +     unsigned path_conflict:1;
>
> This doesn't seem to be assigned anywhere in this patch set?

> > +     unsigned filemask:3;
> > +     unsigned dirmask:3;
>
> I wonder if this needs to be documented that the least significant bit
> corresponds to stages[0], and so forth.

> > +     unsigned match_mask:3;
>
> I think this can be derived by just looking at the stages array? Maybe
> document as:
>
>   Optimization to track which stages match. Either 0 or at least 2 bits
>   are set; if at least 2 bits are set, their corresponding stages match.

> > There seems to be 2 ways of referring to something that we couldn't
> > merge - "conflicted" (or "having a conflict") and "unmerged". Should we
> > stick to one of them?
> 
> Uhm...perhaps, but it feels like I'm going to miss some while looking
> over it.  Also, there are some semantic differences at play.  Since
> the whole algorithm is divided around multiple stages --
> collect_merge_info(), detect_and_process_renames(), process_entries(),
> as of a given early stage we might just know that we couldn't merge it
> *yet*.  For example, both sides modified the entry, or one side
> modified and the other side is missing ("did they delete it or rename
> it?").  After rename detection and three-way content merge, something
> that had not been automatically mergeable as of an earlier step might
> end up being so.  But we need names for stuff in the interim state.
> But it's also possible for us to know at an early state that thing are
> definitely going to be a conflict regardless of what later stages do
> (e.g. both sides rename a path, but rename it differently).

> > Also, looking ahead, I see that current_dir_name is used as a temporary
> > variable in the recursive calls to collect_merge_info_callback(). I
> > would prefer if current_dir_name went in the cbdata to that function
> > instead, but if that's not possible, maybe document here that
> > current_dir_name is only used in collect_merge_info_callback(), and
> > temporarily at that.
> 
> Yeah, not possible.  collect_merge_info_callback() has to be of
> traverse_callback_t type (from tree-walk.h), which provides no extra
> parameters for extra callback data.  I can add a documentation
> comment.

> > I wonder if this needs to be documented that the least significant bit
> > corresponds to stages[0], and so forth.
> 
> Maybe I should just put a comment to look at tree-walk.h?  The struct
> traverse_info has a "fn" member with a big comment above it describing
> mask & dirmask; filemask is just mask & ~dirmask.

> The weirdest part here is that merge-ort and merge-recursive use the
> same struct merge_options, even though merge_options has a number of
> fields that are oddly specific to merge-recursive's internal
> implementation and don't even make sense with merge-ort's high-level
> design (e.g. buffer_output, which merge-ort has to always do).  I reused
> the same data structure because:
>   * most the fields made sense to both merge algorithms
>   * making a new struct would have required making new enums or somehow
>     externalizing them, and that was getting messy.
>   * it simplifies converting the existing callers by not having to
>     have different code paths for merge_options setup.

> I also marked detect_renames as ignored.  We can revisit that later, but
> in short: merge-recursive allowed turning off rename detection because
> it was sometimes glacially slow.  When you speed something up by a few
> orders of magnitude, it's worth revisiting whether that justification is
> still relevant.  Besides, if folks find it's still too slow, perhaps
> they have a better scaling case than I could find and maybe it turns up
> some more optimizations we can add.  If it still is needed as an option,
> it is easy to add later.

>  static void merge_start(struct merge_options *opt, struct merge_result *result)
>  {
> -	die("Not yet implemented.");
> +	/* Sanity checks on opt */
> +	assert(opt->repo);
> +
> +	assert(opt->branch1 && opt->branch2);
> +
> +	assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
> +	       opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
> +	assert(opt->rename_limit >= -1);
> +	assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
> +	assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
> +
> +	assert(opt->xdl_opts >= 0);
> +	assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
> +	       opt->recursive_variant <= MERGE_VARIANT_THEIRS);
> +
> +	/*
> +	 * detect_renames, verbosity, buffer_output, and obuf are ignored
> +	 * fields that were used by "recursive" rather than "ort" -- but
> +	 * sanity check them anyway.
> +	 */
> +	assert(opt->detect_renames >= -1 &&
> +	       opt->detect_renames <= DIFF_DETECT_COPY);
> +	assert(opt->verbosity >= 0 && opt->verbosity <= 5);
> +	assert(opt->buffer_output <= 2);
> +	assert(opt->obuf.len == 0);
> +
> +	assert(opt->priv == NULL);
> +
> +	/* Initialization of opt->priv, our internal merge data */
> +	opt->priv = xcalloc(1, sizeof(*opt->priv));

> +	/*
> +	 * Although we initialize opt->priv->paths with strdup_strings=0,
> +	 * that's just to avoid making yet another copy of an allocated
> +	 * string.  Putting the entry into paths means we are taking
> +	 * ownership, so we will later free it.
> +	 *
> +	 * In contrast, unmerged just has a subset of keys from paths, so
> +	 * we don't want to free those (it'd be a duplicate free).
> +	 */
> +	strmap_init_with_options(&opt->priv->paths, NULL, 0);
> +	strmap_init_with_options(&opt->priv->unmerged, NULL, 0);
>  }

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > The weirdest part here is that merge-ort and merge-recursive use the
> > same struct merge_options, even though merge_options has a number of
> > fields that are oddly specific to merge-recursive's internal
> > implementation and don't even make sense with merge-ort's high-level
> > design (e.g. buffer_output, which merge-ort has to always do).  I reused
> > the same data structure because:
> >   * most the fields made sense to both merge algorithms
> >   * making a new struct would have required making new enums or somehow
> >     externalizing them, and that was getting messy.
> >   * it simplifies converting the existing callers by not having to
> >     have different code paths for merge_options setup.
>
> I think this is appropriate. The other option would be to split the
> struct into "common options" and "specific options" but that starts
> to get messy if we add yet another merge strategy that changes what
> should be "common". Hopefully we can group options within the struct
> merge_options definition to assist with this?

> For now, the assertions are a good approach.
>
> > I also marked detect_renames as ignored.  We can revisit that later, but
> > in short: merge-recursive allowed turning off rename detection because
> > it was sometimes glacially slow.  When you speed something up by a few
> > orders of magnitude, it's worth revisiting whether that justification is
> > still relevant.  Besides, if folks find it's still too slow, perhaps
> > they have a better scaling case than I could find and maybe it turns up
> > some more optimizations we can add.  If it still is needed as an option,
> > it is easy to add later.
>
> As long as it is easy to add later, I don't see much of a problem. Usually
> adding a knob to disable a feature is necessary to mitigate risk, and here
> we can simply adjust config to use the non-ort algorithm if we notice a data
> shape where rename detection makes the algorithm slow/unusable.

> >  static void merge_start(struct merge_options *opt, struct merge_result *result)
> >  {
> > -     die("Not yet implemented.");
> > +     /* Sanity checks on opt */
> > +     assert(opt->repo);
> > +
> > +     assert(opt->branch1 && opt->branch2);
> > +
> > +     assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
> > +            opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
> > +     assert(opt->rename_limit >= -1);
> > +     assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
> > +     assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
> > +
> > +     assert(opt->xdl_opts >= 0);
> > +     assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
> > +            opt->recursive_variant <= MERGE_VARIANT_THEIRS);
> > +
> > +     /*
> > +      * detect_renames, verbosity, buffer_output, and obuf are ignored
> > +      * fields that were used by "recursive" rather than "ort" -- but
> > +      * sanity check them anyway.
> > +      */
> > +     assert(opt->detect_renames >= -1 &&
> > +            opt->detect_renames <= DIFF_DETECT_COPY);
> > +     assert(opt->verbosity >= 0 && opt->verbosity <= 5);
> > +     assert(opt->buffer_output <= 2);
> > +     assert(opt->obuf.len == 0);
> > +
> > +     assert(opt->priv == NULL);
> > +
> > +     /* Initialization of opt->priv, our internal merge data */
> > +     opt->priv = xcalloc(1, sizeof(*opt->priv));
>
> nit: I would insert an empty line between this code and the
> multi-line comment below.
>
> > +     /*
> > +      * Although we initialize opt->priv->paths with strdup_strings=0,
> > +      * that's just to avoid making yet another copy of an allocated
> > +      * string.  Putting the entry into paths means we are taking
> > +      * ownership, so we will later free it.
> > +      *
> > +      * In contrast, unmerged just has a subset of keys from paths, so
> > +      * we don't want to free those (it'd be a duplicate free).
> > +      */
> > +     strmap_init_with_options(&opt->priv->paths, NULL, 0);
> > +     strmap_init_with_options(&opt->priv->unmerged, NULL, 0);
> >  }
>
> This approach looks fine to me.
>
> Thanks,
> -Stolee

> I have some ideas for using a histogram diff to improve content merges,
> which fundamentally relies on the idea of a histogram.  Since the diffs
> are never displayed to the user but just used internally for merging,
> the typical user preference shouldn't matter anyway, and I want to make
> sure that all my testing works with this algorithm.
> 
> Granted, I don't yet know if those ideas will pan out and I haven't even
> tried any of them out yet, but it's easy to change the diff algorithm in
> the future if needed or wanted.  For now, just set it to histogram.

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > I have some ideas for using a histogram diff to improve content merges,
> > which fundamentally relies on the idea of a histogram.  Since the diffs
> > are never displayed to the user but just used internally for merging,
> > the typical user preference shouldn't matter anyway, and I want to make
> > sure that all my testing works with this algorithm.
> >
> > Granted, I don't yet know if those ideas will pan out and I haven't even
> > tried any of them out yet, but it's easy to change the diff algorithm in
> > the future if needed or wanted.  For now, just set it to histogram.
>
> If you are not making use of the histogram yet, then could you set this
> patch aside until you _do_ use it? Or are there performance implications
> that are also a side benefit?

> On Wed, Nov 11, 2020 at 5:54 AM Derrick Stolee <stolee@gmail.com> wrote:
>>
>> On 11/2/2020 3:43 PM, Elijah Newren wrote:
>>> I have some ideas for using a histogram diff to improve content merges,
>>> which fundamentally relies on the idea of a histogram.  Since the diffs
>>> are never displayed to the user but just used internally for merging,
>>> the typical user preference shouldn't matter anyway, and I want to make
>>> sure that all my testing works with this algorithm.
>>>
>>> Granted, I don't yet know if those ideas will pan out and I haven't even
>>> tried any of them out yet, but it's easy to change the diff algorithm in
>>> the future if needed or wanted.  For now, just set it to histogram.
>>
>> If you are not making use of the histogram yet, then could you set this
>> patch aside until you _do_ use it? Or are there performance implications
>> that are also a side benefit?
> 
> Long story...

>
> On 11/11/2020 11:47 AM, Elijah Newren wrote:
> > On Wed, Nov 11, 2020 at 5:54 AM Derrick Stolee <stolee@gmail.com> wrote:
> >>
> >> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> >>> I have some ideas for using a histogram diff to improve content merges,
> >>> which fundamentally relies on the idea of a histogram.  Since the diffs
> >>> are never displayed to the user but just used internally for merging,
> >>> the typical user preference shouldn't matter anyway, and I want to make
> >>> sure that all my testing works with this algorithm.
> >>>
> >>> Granted, I don't yet know if those ideas will pan out and I haven't even
> >>> tried any of them out yet, but it's easy to change the diff algorithm in
> >>> the future if needed or wanted.  For now, just set it to histogram.
> >>
> >> If you are not making use of the histogram yet, then could you set this
> >> patch aside until you _do_ use it? Or are there performance implications
> >> that are also a side benefit?
> >
> > Long story...
>
> ...
>
> > Does that help?
>
> In summary, you have some concrete reasons to prefer the histogram
> diff other than just "I have some ideas that might pan out later" so
> this code change is a good one but could be better justified in the
> commit message. Does that sound correct?

> diff --git a/merge-ort.c b/merge-ort.c
> index 537da9f6df..626eb9713e 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -77,13 +77,130 @@ static int err(struct merge_options *opt, const char *err, ...)
>  	return -1;
>  }
>  
> +static int collect_merge_info_callback(int n,
> +				       unsigned long mask,
> +				       unsigned long dirmask,
> +				       struct name_entry *names,
> +				       struct traverse_info *info)
> +{

> +	/*
> +	 * A bunch of sanity checks verifying that traverse_trees() calls
> +	 * us the way I expect.  Could just remove these at some point,
> +	 * though maybe they are helpful to future code readers.
> +	 */
> +	assert(mbase_null == is_null_oid(&names[0].oid));
> +	assert(side1_null == is_null_oid(&names[1].oid));
> +	assert(side2_null == is_null_oid(&names[2].oid));
> +	assert(!mbase_null || !side1_null || !side2_null);
> +	assert(mask > 0 && mask < 8);

> +	/*
> +	 * TODO: record information about the path other than all zeros,
> +	 * so we can resolve later in process_entries.
> +	 */
> +	ci = xcalloc(1, sizeof(struct conflict_info));
> +	strmap_put(&opti->paths, fullpath, ci);

>  static int collect_merge_info(struct merge_options *opt,
>  			      struct tree *merge_base,
>  			      struct tree *side1,
>  			      struct tree *side2)
>  {
> -	/* TODO: Implement this using traverse_trees() */
> -	die("Not yet implemented.");
> +	int ret;
> +	struct tree_desc t[3];
> +	struct traverse_info info;
> +	char *toplevel_dir_placeholder = "";
> +
> +	opt->priv->current_dir_name = toplevel_dir_placeholder;
> +	setup_traverse_info(&info, toplevel_dir_placeholder);

>
> > diff --git a/merge-ort.c b/merge-ort.c
> > index 537da9f6df..626eb9713e 100644
> > --- a/merge-ort.c
> > +++ b/merge-ort.c
> > @@ -77,13 +77,130 @@ static int err(struct merge_options *opt, const char *err, ...)
> >       return -1;
> >  }
> >
> > +static int collect_merge_info_callback(int n,
> > +                                    unsigned long mask,
> > +                                    unsigned long dirmask,
> > +                                    struct name_entry *names,
> > +                                    struct traverse_info *info)
> > +{
>
> [snip]
>
> > +     unsigned mbase_null = !(mask & 1);
> > +     unsigned side1_null = !(mask & 2);
> > +     unsigned side2_null = !(mask & 4);
>
> Should these be "int"?

> > +     /*
> > +      * A bunch of sanity checks verifying that traverse_trees() calls
> > +      * us the way I expect.  Could just remove these at some point,
> > +      * though maybe they are helpful to future code readers.
> > +      */
> > +     assert(mbase_null == is_null_oid(&names[0].oid));
> > +     assert(side1_null == is_null_oid(&names[1].oid));
> > +     assert(side2_null == is_null_oid(&names[2].oid));
> > +     assert(!mbase_null || !side1_null || !side2_null);
> > +     assert(mask > 0 && mask < 8);
>
> These were helpful to me.
>
> > +     /* Other invariant checks, mostly for documentation purposes. */
> > +     assert(mask == (dirmask | filemask));
>
> But not this - filemask was computed in this function, so I need not
> look elsewhere to see that this is correct.
>
> > +     /*
> > +      * TODO: record information about the path other than all zeros,
> > +      * so we can resolve later in process_entries.
> > +      */
> > +     ci = xcalloc(1, sizeof(struct conflict_info));
> > +     strmap_put(&opti->paths, fullpath, ci);
>
> OK - so each entry is a full-size conflict_info to store all relevant
> information. Presumably some of these will be converted later into what
> is effectively a struct merged_info (so, the extra struct conflict_info
> fields are unused but memory is still occupied).
>
> I do see that in patch 10, there is an optimization that directly
> allocates the smaller struct merged_info when it is known at this point
> that there is no conflict.

> [snip rest of function]
>
> >  static int collect_merge_info(struct merge_options *opt,
> >                             struct tree *merge_base,
> >                             struct tree *side1,
> >                             struct tree *side2)
> >  {
> > -     /* TODO: Implement this using traverse_trees() */
> > -     die("Not yet implemented.");
> > +     int ret;
> > +     struct tree_desc t[3];
> > +     struct traverse_info info;
> > +     char *toplevel_dir_placeholder = "";
> > +
> > +     opt->priv->current_dir_name = toplevel_dir_placeholder;
> > +     setup_traverse_info(&info, toplevel_dir_placeholder);
>
> I thought that this was written like this (instead of inlining the 2
> double-quotes) to ensure that the string-equality-is-pointer-equality
> characteristic holds, but I see that that characteristic is for
> directory_name in struct merged_info, not current_dir_name in struct
> merge_options_internal. Any reason for not inlining ""?

> > > +     unsigned mbase_null = !(mask & 1);
> > > +     unsigned side1_null = !(mask & 2);
> > > +     unsigned side2_null = !(mask & 4);
> >
> > Should these be "int"?
> 
> Does the type matter, particularly since "boolean" isn't available?

> > I thought that this was written like this (instead of inlining the 2
> > double-quotes) to ensure that the string-equality-is-pointer-equality
> > characteristic holds, but I see that that characteristic is for
> > directory_name in struct merged_info, not current_dir_name in struct
> > merge_options_internal. Any reason for not inlining ""?
> 
> You're really digging in; I love it.  From setup_path_info(), the
> directory_name is set from the current_dir_name:
>         path_info->merged.directory_name = current_dir_name;
> (and if you follow where the current_dir_name parameter gets its value
> from, you find that it came indirectly from
> opt->priv->current_dir_name), so current_dir_name must meet all the
> requirements on merge_info's directory_name field.
> 
> Perhaps there's still some kind of additional simplification possible
> here, but directory rename detection is an area that has to take some
> special care around this requirement.  I simplified the code a little
> bit in this area as I was trying to break off a good first 20 patches
> to submit, but even if we can simplify it more, the structure is just
> going to come back later.

> +		const char *original_dir_name;
> +		int i, ret;
> +
> +		ci->match_mask &= filemask;
> +		newinfo = *info;
> +		newinfo.prev = info;
> +		newinfo.name = p->path;
> +		newinfo.namelen = p->pathlen;
> +		newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
> +
> +		for (i = 0; i < 3; i++, dirmask >>= 1) {

> +			const struct object_id *oid = NULL;
> +			if (dirmask & 1)
> +				oid = &names[i].oid;
> +			buf[i] = fill_tree_descriptor(opt->repo, t + i, oid);
> +		}

>  static int collect_merge_info(struct merge_options *opt,
>  			      struct tree *merge_base,
>  			      struct tree *side1,
>  			      struct tree *side2)
>  {
> -	/* TODO: Implement this using traverse_trees() */
> -	die("Not yet implemented.");
> +	int ret;
> +	struct tree_desc t[3];
> +	struct traverse_info info;
> +	char *toplevel_dir_placeholder = "";

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > +     /* +1 in both of the following lines to include the NUL byte */
> > +     fullpath = xmalloc(len+1);
> > +     make_traverse_path(fullpath, len+1, info, p->path, p->pathlen);
>
> nit: s/len+1/len + 1/g
>
> > +             void *buf[3] = {NULL,};
>
> This "{NULL,}" seems odd to me. I suppose there is a reason why it
> isn't "{ NULL, NULL, NULL }"?

> > +             const char *original_dir_name;
> > +             int i, ret;
> > +
> > +             ci->match_mask &= filemask;
> > +             newinfo = *info;
> > +             newinfo.prev = info;
> > +             newinfo.name = p->path;
> > +             newinfo.namelen = p->pathlen;
> > +             newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
> > +
> > +             for (i = 0; i < 3; i++, dirmask >>= 1) {
>
> This multi-action iterator borders on "too clever". It seems like
> placing "dirmask >>= 1;" or "dirmask = dirmask >> 1;" at the end
> of the block would be equivalent and less jarring to a reader.
>
> I was thinking it doesn't really matter, except that dirmask is not
> in the initializer or sentinel of the for(), so having it here does
> not immediately make sense.
>
> (This has been too much writing for such an inconsequential line
> of code. Sorry.)

> > +                     const struct object_id *oid = NULL;
> > +                     if (dirmask & 1)
> > +                             oid = &names[i].oid;
> > +                     buf[i] = fill_tree_descriptor(opt->repo, t + i, oid);
> > +             }
>
>
> >  static int collect_merge_info(struct merge_options *opt,
> >                             struct tree *merge_base,
> >                             struct tree *side1,
> >                             struct tree *side2)
> >  {
> > -     /* TODO: Implement this using traverse_trees() */
> > -     die("Not yet implemented.");
> > +     int ret;
> > +     struct tree_desc t[3];
> > +     struct traverse_info info;
> > +     char *toplevel_dir_placeholder = "";
>
> It seems like this should be "const char *"
>
> > +     init_tree_desc(t+0, merge_base->buffer, merge_base->size);
> > +     init_tree_desc(t+1, side1->buffer, side1->size);
> > +     init_tree_desc(t+2, side2->buffer, side2->size);
>
> More space issues: s/t+/t + /g

> This series depends on a merge of en/strmap (after updating to v3) and
> en/merge-ort-api-null-impl.
> 
> As promised, here's the update of the series due to the strmap
> updates...and two other tiny updates.

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > This series depends on a merge of en/strmap (after updating to v3) and
> > en/merge-ort-api-null-impl.
> >
> > As promised, here's the update of the series due to the strmap
> > updates...and two other tiny updates.
>
> Hi Elijah,
>
> I'm sorry that I've been unavailable to read and review your series
> on this topic. I'm very excited about the opportunities here, and I
> wanted to take your topic and merge it with our microsoft/git fork
> so I could test the performance in a Scalar-enabled monorepo. My
> branch is available in my fork [1]
>
> [1] https://github.com/derrickstolee/git/tree/merge-ort-vfs
>
> However, I'm unable to discover how to trigger your ort strategy,
> even for a simple rebase. Perhaps you could supply a recommended
> command for testing?
>
> Thanks,
> -Stolee

>
> On Tue, Nov 3, 2020 at 6:50 AM Derrick Stolee <stolee@gmail.com> wrote:
> >
> > On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > > This series depends on a merge of en/strmap (after updating to v3) and
> > > en/merge-ort-api-null-impl.
> > >
> > > As promised, here's the update of the series due to the strmap
> > > updates...and two other tiny updates.
> >
> > Hi Elijah,
> >
> > I'm sorry that I've been unavailable to read and review your series
> > on this topic. I'm very excited about the opportunities here, and I
> > wanted to take your topic and merge it with our microsoft/git fork
> > so I could test the performance in a Scalar-enabled monorepo. My
> > branch is available in my fork [1]
> >
> > [1] https://github.com/derrickstolee/git/tree/merge-ort-vfs
> >
> > However, I'm unable to discover how to trigger your ort strategy,
> > even for a simple rebase. Perhaps you could supply a recommended
> > command for testing?
> >
> > Thanks,
> > -Stolee
>
> If you want to test performance, you shouldn't test this particular
> submission, you should test the end result which exists as the 'ort'
> branch of my repo.  It actually passes all the tests rather than just
> trivial cherry-picks and rebases, and has lots (and lots) of
> performance work that hasn't even begun at the point of the
> 'ort-basics' branch.  (However, it also contains some unrelated memory
> cleanup in revision.c, chdir-notify.c, and a number of other places
> because I was annoyed that a rebase wouldn't run valgrind-free and
> made it harder to spot my memory leaks.  And the day I went hunting
> those memory "leaks", I went and grabbed some unrelated memory leaks
> too.  If it causes you merge conflicts, let me know and I'll try to
> create a branch for you that hash the minimal changes outside of
> merge-ort*.[ch] and diffcore*.[ch])
>
> All that said, for testing either branch you just need to first set
> pull.twohead=ort in your git config (see
> https://lore.kernel.org/git/61217a83bd7ff0ce9016eb4df9ded4fdf29a506c.1604360734.git.gitgitgadget@gmail.com/),
> or, if running regression tests, set GIT_TEST_MERGE_ALGORITHM=ort.

> Hi Derrick,
> 
> On Tue, Nov 3, 2020 at 8:36 AM Elijah Newren <newren@gmail.com> wrote:
>> All that said, for testing either branch you just need to first set
>> pull.twohead=ort in your git config (see
>> https://lore.kernel.org/git/61217a83bd7ff0ce9016eb4df9ded4fdf29a506c.1604360734.git.gitgitgadget@gmail.com/),
>> or, if running regression tests, set GIT_TEST_MERGE_ALGORITHM=ort.
> 
> I probably also should have mentioned that merge-ort does not (yet?)
> heed merge.renames configuration setting; it always detects renames.
> I know you run with merge.renames=false, so you won't quite get an
> apples-to-apples comparison.  However, part of my point was I wanted
> to make renames fast enough that they could be left turned on, even
> for the large scale repos, so I'm very interested in your experience.
> If you need an escape hatch, though, just put a "return 1" at the top
> of detect_and_process_renames() to turn it off.
> 
> Oh, and I went through and re-merged all the merge commits in the
> linux kernel and found a bug in merge-ort while doing that (causing it
> to die, not to merge badly).  I'm kind of surprised that none of my
> testcases triggered that failure earlier; if you're testing it out,
> you might want to update to get the fix (commit 067e5c1a38,
> "merge-ort: fix bug with cached_target_names not being initialized in
> redos", 2020-11-06).

>
> On 11/7/20 1:06 AM, Elijah Newren wrote:
> > Hi Derrick,
> >
> > On Tue, Nov 3, 2020 at 8:36 AM Elijah Newren <newren@gmail.com> wrote:
> >> All that said, for testing either branch you just need to first set
> >> pull.twohead=ort in your git config (see
> >> https://lore.kernel.org/git/61217a83bd7ff0ce9016eb4df9ded4fdf29a506c.1604360734.git.gitgitgadget@gmail.com/),
> >> or, if running regression tests, set GIT_TEST_MERGE_ALGORITHM=ort.
> >
> > I probably also should have mentioned that merge-ort does not (yet?)
> > heed merge.renames configuration setting; it always detects renames.
> > I know you run with merge.renames=false, so you won't quite get an
> > apples-to-apples comparison.  However, part of my point was I wanted
> > to make renames fast enough that they could be left turned on, even
> > for the large scale repos, so I'm very interested in your experience.
> > If you need an escape hatch, though, just put a "return 1" at the top
> > of detect_and_process_renames() to turn it off.
> >
> > Oh, and I went through and re-merged all the merge commits in the
> > linux kernel and found a bug in merge-ort while doing that (causing it
> > to die, not to merge badly).  I'm kind of surprised that none of my
> > testcases triggered that failure earlier; if you're testing it out,
> > you might want to update to get the fix (commit 067e5c1a38,
> > "merge-ort: fix bug with cached_target_names not being initialized in
> > redos", 2020-11-06).
>
> I did manage to do some testing to see what happens with
> a large repo under a small sparse-checkout. And using
> trace2, I was able to see that your code is being exercised.
> Unfortunately, I didn't see any performance improvement, and
> that is likely due to needing to expand the index entirely
> when checking out the merge commit.
>
> Is there a command to construct a merge commit without
> actually checking it out? That would reduce the time spent
> expanding the index, which would allow your algorithm to
> really show its benefits!

> On Sat, Nov 7, 2020 at 7:02 AM Derrick Stolee <stolee@gmail.com> wrote:
>>
>> On 11/7/20 1:06 AM, Elijah Newren wrote:
>>> Hi Derrick,
>>>
>>> On Tue, Nov 3, 2020 at 8:36 AM Elijah Newren <newren@gmail.com> wrote:
>>>> All that said, for testing either branch you just need to first set
>>>> pull.twohead=ort in your git config (see
>>>> https://lore.kernel.org/git/61217a83bd7ff0ce9016eb4df9ded4fdf29a506c.1604360734.git.gitgitgadget@gmail.com/),
>>>> or, if running regression tests, set GIT_TEST_MERGE_ALGORITHM=ort.
>>>
>>> I probably also should have mentioned that merge-ort does not (yet?)
>>> heed merge.renames configuration setting; it always detects renames.
>>> I know you run with merge.renames=false, so you won't quite get an
>>> apples-to-apples comparison.  However, part of my point was I wanted
>>> to make renames fast enough that they could be left turned on, even
>>> for the large scale repos, so I'm very interested in your experience.
>>> If you need an escape hatch, though, just put a "return 1" at the top
>>> of detect_and_process_renames() to turn it off.
>>>
>>> Oh, and I went through and re-merged all the merge commits in the
>>> linux kernel and found a bug in merge-ort while doing that (causing it
>>> to die, not to merge badly).  I'm kind of surprised that none of my
>>> testcases triggered that failure earlier; if you're testing it out,
>>> you might want to update to get the fix (commit 067e5c1a38,
>>> "merge-ort: fix bug with cached_target_names not being initialized in
>>> redos", 2020-11-06).
>>
>> I did manage to do some testing to see what happens with
>> a large repo under a small sparse-checkout. And using
>> trace2, I was able to see that your code is being exercised.
>> Unfortunately, I didn't see any performance improvement, and
>> that is likely due to needing to expand the index entirely
>> when checking out the merge commit.
>>
>> Is there a command to construct a merge commit without
>> actually checking it out? That would reduce the time spent
>> expanding the index, which would allow your algorithm to
>> really show its benefits!
> 
> Wow, very interesting.  I am working on a --remerge-diff option for
> log, which implies -p and is similar to -c or --cc in that it makes
> merge commits show a diff, but which in particular remerges the two
> parent commits complete with conflict markers and such and then diffs
> the merge commit against that intermediate remerge.  That's a case
> that constructs a merge commit without ever touching the index (or
> working tree)...but there's no equivalent comparison point for
> merge-recursive.  So, it doesn't provide something to compare against
> (and while the code can be used I don't actually have a --remerge-diff
> option yet -- it just hardcodes the behavior on if wanted or not), so
> I'm not sure if you'd be interested in it.  If you are, let me know
> though, and I'll send details.
> 
> However, I'm really surprised here, because merge-recursive always
> reads and writes the index too (the index is the basis for its whole
> algorithm).  In fact, merge-recursive always reads the index at least
> *twice* (it unconditionally discards and re-reads the index), so you
> must have some kind of specialized tweaking of merge-recursive if it
> somehow avoids a full index read/write.  In order to do an
> apples-to-apples comparison, we'd need to make those same tweaks to
> merge-ort, but I don't have a clue what kind of tweaks you've made
> here.  So, some investigation points:
> 
> *1*. Could you give me the accumulated times from the trace2_regions
> so we can verify where the time is spent?  The 'summarize-perf' script
> at the toplevel of the repo in my ort branch might be helpful for
> this; just prefix any git command with that script and it accumulates
> the trace2 region times and prints them out.  For example, I could run
> 'summarize-perf git merge --no-edit B^0' or 'summarize-perf test-tool
> fast-rebase --onto HEAD ca76bea9 myfeature'.  Here's an example:
> 
> === BEGIN OUTPUT ===
> $ /home/newren/floss/git/summarize-perf test-tool fast-rebase --onto
> HEAD 4703d9119972bf586d2cca76ec6438f819ffa30e hwmon-updates
> Rebasing fd8bdb23b91876ac1e624337bb88dc1dcc21d67e...
> Done.
> Accumulated times:
>     0.031 : <unmeasured> ( 3.2%)
>     0.837 : 35 : label:incore_nonrecursive
>        0.003 : <unmeasured> ( 0.4%)
>        0.476 : 41 : ..label:collect_merge_info
>           0.001 : <unmeasured> ( 0.2%)
>           0.475 : 41 : ....label:traverse_trees
>        0.298 : 41 : ..label:renames
>           0.015 : <unmeasured> ( 5.1%)
>           0.280 : 41 : ....label:regular renames
>              0.036 : <unmeasured> (12.7%)
>              0.244 : 6 : ......label:diffcore_rename
>                 0.001 : <unmeasured> ( 0.4%)
>                 0.078 : 6 : ........label:dir rename setup
>                 0.055 : 6 : ........label:basename matches
>                 0.051 : 6 : ........label:exact renames
>                 0.031 : 6 : ........label:write back to queue
>                 0.017 : 6 : ........label:setup
>                 0.009 : 6 : ........label:cull basename
>                 0.003 : 6 : ........label:cull exact
>           0.002 : 35 : ....label:directory renames
>           0.001 : 35 : ....label:process renames
>        0.052 : 35 : ..label:process_entries
>           0.001 : <unmeasured> ( 1.7%)
>           0.033 : 35 : ....label:processing
>           0.017 : 35 : ....label:process_entries setup
>              0.001 : <unmeasured> ( 5.8%)
>              0.008 : 35 : ......label:plist copy
>              0.008 : 35 : ......label:plist sort
>              0.000 : 35 : ......label:plist grow
>           0.001 : 35 : ....label:finalize
>        0.005 : 35 : ..label:merge_start
>           0.001 : <unmeasured> (18.8%)
>           0.004 : 34 : ....label:reset_maps
>           0.000 : 35 : ....label:sanity checks
>           0.000 : 1 : ....label:allocate/init
>        0.003 : 6 : ..label:reset_maps
>     0.035 : 1 : label:do_write_index
> /home/newren/floss/linux-stable/.git/index.lock
>     0.034 : 1 : label:checkout
>        0.034 : <unmeasured> (99.9%)
>        0.000 : 1 : ..label:Filtering content
>     0.009 : 1 : label:do_read_index .git/index
>     0.000 : 1 : label:write_auto_merge
>     0.000 : 1 : label:record_unmerged
> Estimated measurement overhead (.010 ms/region-measure * 679):
> 0.006790000000000001
> Timing including forking:  0.960 (0.013 additional seconds)
> === END OUTPUT ===
> This was a run that took just under 1s (and was a hot-cache case; I
> had just done the same rebase before to warm the caches), and the
> combination of index/working tree bits (everything at and after
> do_write_index in the output) was 0.035+0.034+0.009+0+0=0.078 seconds,
> corresponding to just over 8.1% of overall time.  I'm curious where
> that lands for your repository testcase; if the larger time ends up
> somewhere under the indented label:incore_nonrecursive region, then
> it's due to something other than index reading/updating/writing.
> 
> *2*. If it really is due to index reading/updating/writing, then index
> handling in merge-ort is confined to two functions: checkout() and
> record_unmerged_index_entries().  Both functions aren't too long, and
> neither one calls into any other function within merge-ort.c.
> (Further, checkout() is a near copy of code from merge_working_tree()
> in builtin/checkout.c, or at least a copy of that function from a year
> or so ago.)  As such, it's possible you can go in and make whatever
> special tweaks you have for partial index reading/writing to those
> functions.
> 
> I'm curious to hear back more on this.

> > *1*. Could you give me the accumulated times from the trace2_regions
> > so we can verify where the time is spent?  The 'summarize-perf' script
> > at the toplevel of the repo in my ort branch might be helpful for
> > this; just prefix any git command with that script and it accumulates
> > the trace2 region times and prints them out.  For example, I could run
> > 'summarize-perf git merge --no-edit B^0' or 'summarize-perf test-tool
> > fast-rebase --onto HEAD ca76bea9 myfeature'.  Here's an example:
> >
> > === BEGIN OUTPUT ===
> > $ /home/newren/floss/git/summarize-perf test-tool fast-rebase --onto
> > HEAD 4703d9119972bf586d2cca76ec6438f819ffa30e hwmon-updates
> > Rebasing fd8bdb23b91876ac1e624337bb88dc1dcc21d67e...
> > Done.
> > Accumulated times:
> >     0.031 : <unmeasured> ( 3.2%)
> >     0.837 : 35 : label:incore_nonrecursive
> >        0.003 : <unmeasured> ( 0.4%)
> >        0.476 : 41 : ..label:collect_merge_info
> >           0.001 : <unmeasured> ( 0.2%)
> >           0.475 : 41 : ....label:traverse_trees
> >        0.298 : 41 : ..label:renames
> >           0.015 : <unmeasured> ( 5.1%)
> >           0.280 : 41 : ....label:regular renames
> >              0.036 : <unmeasured> (12.7%)
> >              0.244 : 6 : ......label:diffcore_rename
> >                 0.001 : <unmeasured> ( 0.4%)
> >                 0.078 : 6 : ........label:dir rename setup
> >                 0.055 : 6 : ........label:basename matches
> >                 0.051 : 6 : ........label:exact renames
> >                 0.031 : 6 : ........label:write back to queue
> >                 0.017 : 6 : ........label:setup
> >                 0.009 : 6 : ........label:cull basename
> >                 0.003 : 6 : ........label:cull exact
> >           0.002 : 35 : ....label:directory renames
> >           0.001 : 35 : ....label:process renames
> >        0.052 : 35 : ..label:process_entries
> >           0.001 : <unmeasured> ( 1.7%)
> >           0.033 : 35 : ....label:processing
> >           0.017 : 35 : ....label:process_entries setup
> >              0.001 : <unmeasured> ( 5.8%)
> >              0.008 : 35 : ......label:plist copy
> >              0.008 : 35 : ......label:plist sort
> >              0.000 : 35 : ......label:plist grow
> >           0.001 : 35 : ....label:finalize
> >        0.005 : 35 : ..label:merge_start
> >           0.001 : <unmeasured> (18.8%)
> >           0.004 : 34 : ....label:reset_maps
> >           0.000 : 35 : ....label:sanity checks
> >           0.000 : 1 : ....label:allocate/init
> >        0.003 : 6 : ..label:reset_maps
> >     0.035 : 1 : label:do_write_index
> > /home/newren/floss/linux-stable/.git/index.lock
> >     0.034 : 1 : label:checkout
> >        0.034 : <unmeasured> (99.9%)
> >        0.000 : 1 : ..label:Filtering content
> >     0.009 : 1 : label:do_read_index .git/index
> >     0.000 : 1 : label:write_auto_merge
> >     0.000 : 1 : label:record_unmerged
> > Estimated measurement overhead (.010 ms/region-measure * 679):
> > 0.006790000000000001
> > Timing including forking:  0.960 (0.013 additional seconds)
> > === END OUTPUT ===
> > This was a run that took just under 1s (and was a hot-cache case; I
> > had just done the same rebase before to warm the caches), and the
> > combination of index/working tree bits (everything at and after
> > do_write_index in the output) was 0.035+0.034+0.009+0+0=0.078 seconds,
> > corresponding to just over 8.1% of overall time.  I'm curious where
> > that lands for your repository testcase; if the larger time ends up
> > somewhere under the indented label:incore_nonrecursive region, then
> > it's due to something other than index reading/updating/writing.
> >
> > *2*. If it really is due to index reading/updating/writing, then index
> > handling in merge-ort is confined to two functions: checkout() and
> > record_unmerged_index_entries().  Both functions aren't too long, and
> > neither one calls into any other function within merge-ort.c.
> > (Further, checkout() is a near copy of code from merge_working_tree()
> > in builtin/checkout.c, or at least a copy of that function from a year
> > or so ago.)  As such, it's possible you can go in and make whatever
> > special tweaks you have for partial index reading/writing to those
> > functions.
> >
> > I'm curious to hear back more on this.
>
> I don't have a lot of time to dig into this right now, but here are
> the stats for my rebases and merges with and without your option.

> The first thing I notice for each is that there is a significant
> amount of "unmeasured" time at the beginning of each, and that
> could possibly be improved separately.
>
> First, try a rebase forward and backward.
>
> $ /_git/git/summarize-perf git rebase --onto to from test
> Successfully rebased and updated refs/heads/test.
> Accumulated times:
>     8.511 : <unmeasured> (74.9%)

>     1.331 : 1 : ......label:unpack_trees
>        0.200 : <unmeasured> (15.1%)
>        0.580 : 1 : ........label:traverse_trees
>        0.403 : 1 : ........label:clear_ce_flags/0x00000000_0x02000000
>        0.126 : 1 : ........label:check_updates
>           0.126 : <unmeasured> (100.0%)
>           0.000 : 1 : ..........label:Filtering content
>        0.021 : 1 : ........label:clear_ce_flags/0x00080000_0x42000000
>        0.000 : 1 : ........label:fully_valid
>     1.059 : 1 : ......label:do_write_index /_git/office/src/.git/index.lock
>        0.930 : <unmeasured> (87.9%)
>        0.128 : 1 : ........label:write/extension/cache_tree
>     0.455 : 2 : ......label:fully_valid
>     0.001 : 1 : ......label:traverse_trees
>     0.000 : 1 : ......label:check_updates
> Estimated measurement overhead (.010 ms/region-measure * 41): 0.00041000000000000005
> Timing including forking: 11.382 (0.026 additional seconds)
>
> $ /_git/git/summarize-perf git rebase --onto from to test
> Successfully rebased and updated refs/heads/test.
> Accumulated times:
>     8.556 : <unmeasured> (75.2%)
>     1.315 : 1 : ......label:unpack_trees
>        0.197 : <unmeasured> (15.0%)
>        0.580 : 1 : ........label:traverse_trees
>        0.391 : 1 : ........label:clear_ce_flags/0x00000000_0x02000000
>        0.126 : 1 : ........label:check_updates
>           0.126 : <unmeasured> (100.0%)
>           0.000 : 1 : ..........label:Filtering content
>        0.021 : 1 : ........label:clear_ce_flags/0x00080000_0x42000000
>        0.000 : 1 : ........label:fully_valid
>     1.071 : 1 : ......label:do_write_index /_git/office/src/.git/index.lock
>        0.942 : <unmeasured> (88.0%)
>        0.129 : 1 : ........label:write/extension/cache_tree
>     0.431 : 2 : ......label:fully_valid
>     0.001 : 1 : ......label:traverse_trees
>     0.000 : 1 : ......label:check_updates
> Estimated measurement overhead (.010 ms/region-measure * 41): 0.00041000000000000005
> Timing including forking: 11.399 (0.026 additional seconds)

> Then do the same with the ort strategy.
>
> $ /_git/git/summarize-perf git -c pull.twohead=ort rebase --onto to from test
> Successfully rebased and updated refs/heads/test.
> Accumulated times:
>     8.350 : <unmeasured> (73.2%)
>     1.403 : 1 : ....label:checkout
>        0.000 : <unmeasured> ( 0.0%)
>        1.403 : 1 : ......label:unpack_trees
>           0.312 : <unmeasured> (22.3%)
>           0.539 : 1 : ........label:traverse_trees
>           0.401 : 1 : ........label:clear_ce_flags/0x00000000_0x02000000
>           0.128 : 1 : ........label:check_updates
>              0.128 : <unmeasured> (100.0%)
>              0.000 : 1 : ..........label:Filtering content
>           0.021 : 1 : ........label:clear_ce_flags/0x00080000_0x42000000
>           0.000 : 1 : ........label:fully_valid
>     1.081 : 1 : ....label:do_write_index /_git/office/src/.git/index.lock
>        0.951 : <unmeasured> (88.1%)
>        0.129 : 1 : ......label:write/extension/cache_tree
>     0.432 : 2 : ....label:fully_valid
>     0.143 : 1 : ....label:do_read_index .git/index
>        0.019 : <unmeasured> (13.1%)
>        0.125 : 1 : label:read/extension/cache_tree
>     0.004 : 1 : ....label:incore_nonrecursive
>        0.001 : <unmeasured> (25.8%)
>        0.002 : 1 : ......label:process_entries
>           0.000 : <unmeasured> ( 2.6%)
>           0.001 : 1 : ........label:finalize
>           0.001 : 1 : ........label:process_entries setup
>              0.000 : <unmeasured> ( 6.7%)
>              0.001 : 1 : ..........label:plist sort
>              0.000 : 1 : ..........label:plist copy
>              0.000 : 1 : ..........label:plist grow
>           0.000 : 1 : ........label:processing
>        0.001 : 1 : ......label:collect_merge_info
>           0.000 : <unmeasured> (35.3%)
>           0.001 : 1 : ........label:traverse_trees
>        0.000 : 1 : ......label:merge_start
>           0.000 : <unmeasured> (42.3%)
>           0.000 : 1 : ........label:allocate/init
>           0.000 : 1 : ........label:sanity checks
>        0.000 : 1 : ......label:renames
>     0.001 : 1 : ....label:traverse_trees
>     0.000 : 1 : ....label:write_auto_merge
>     0.000 : 1 : ....label:check_updates
>     0.000 : 1 : ....label:record_unmerged
> Estimated measurement overhead (.010 ms/region-measure * 56): 0.0005600000000000001
> Timing including forking: 11.442 (0.027 additional seconds)

> $ /_git/git/summarize-perf git -c pull.twohead=ort rebase --onto from to test
> Successfully rebased and updated refs/heads/test.
> Accumulated times:
>     8.337 : <unmeasured> (73.2%)
>     1.395 : 1 : ....label:checkout
>        0.000 : <unmeasured> ( 0.0%)
>        1.395 : 1 : ......label:unpack_trees
>           0.309 : <unmeasured> (22.1%)
>           0.537 : 1 : ........label:traverse_trees
>           0.403 : 1 : ........label:clear_ce_flags/0x00000000_0x02000000
>           0.124 : 1 : ........label:check_updates
>              0.124 : <unmeasured> (100.0%)
>              0.000 : 1 : ..........label:Filtering content
>           0.021 : 1 : ........label:clear_ce_flags/0x00080000_0x42000000
>           0.000 : 1 : ........label:fully_valid
>     1.084 : 1 : ....label:do_write_index /_git/office/src/.git/index.lock
>        0.955 : <unmeasured> (88.1%)
>        0.129 : 1 : ......label:write/extension/cache_tree
>     0.436 : 2 : ....label:fully_valid
>     0.137 : 1 : ....label:do_read_index .git/index
>        0.013 : <unmeasured> ( 9.3%)
>        0.125 : 1 : label:read/extension/cache_tree
>     0.004 : 1 : ....label:incore_nonrecursive
>        0.001 : <unmeasured> (24.5%)
>        0.002 : 1 : ......label:process_entries
>           0.000 : <unmeasured> ( 2.5%)
>           0.001 : 1 : ........label:finalize
>           0.001 : 1 : ........label:process_entries setup
>              0.000 : <unmeasured> ( 6.5%)
>              0.001 : 1 : ..........label:plist sort
>              0.000 : 1 : ..........label:plist copy
>              0.000 : 1 : ..........label:plist grow
>           0.000 : 1 : ........label:processing
>        0.001 : 1 : ......label:collect_merge_info
>           0.000 : <unmeasured> (26.5%)
>           0.001 : 1 : ........label:traverse_trees
>        0.000 : 1 : ......label:merge_start
>           0.000 : <unmeasured> (43.1%)
>           0.000 : 1 : ........label:allocate/init
>           0.000 : 1 : ........label:sanity checks
>        0.000 : 1 : ......label:renames
>     0.001 : 1 : ....label:traverse_trees
>     0.000 : 1 : ....label:write_auto_merge
>     0.000 : 1 : ....label:check_updates
>     0.000 : 1 : ....label:record_unmerged
> Estimated measurement overhead (.010 ms/region-measure * 56): 0.0005600000000000001
> Timing including forking: 11.418 (0.024 additional seconds)

> $ git reset --hard test2 && /_git/git/summarize-perf git merge test -m test
> Merge made by the 'recursive' strategy.
> Accumulated times:
>     2.647 : <unmeasured> (48.6%)
>     1.384 : 1 : ..label:unpack_trees
>        0.267 : <unmeasured> (19.3%)
>        0.582 : 1 : ....label:traverse_trees
>        0.391 : 1 : ....label:clear_ce_flags/0x00000000_0x02000000
>        0.124 : 1 : ....label:check_updates
>           0.124 : <unmeasured> (100.0%)
>           0.000 : 1 : ......label:Filtering content
>        0.021 : 1 : ....label:clear_ce_flags/0x00080000_0x42000000
>        0.000 : 1 : ....label:fully_valid
>     1.060 : 1 : ..label:do_write_index /_git/office/src/.git/index.lock
>        0.931 : <unmeasured> (87.9%)
>        0.128 : 1 : ....label:write/extension/cache_tree
>     0.226 : 1 : ..label:fully_valid
>     0.134 : 1 : ..label:do_read_index .git/index
>        0.008 : <unmeasured> ( 5.8%)
>        0.126 : 1 : label:read/extension/cache_tree
>     0.001 : 1 : ..label:traverse_trees
>     0.000 : 1 : ..label:check_updates
>     0.000 : 1 : ..label:setup
>     0.000 : 1 : ..label:write back to queue
> Estimated measurement overhead (.010 ms/region-measure * 20): 0.0002
> Timing including forking:  5.466 (0.015 additional seconds)

> $ git reset --hard test2 && /_git/git/summarize-perf git -c pull.twohead=ort merge test -m test
> Merge made by the 'ort' strategy.
> Accumulated times:
>     2.531 : <unmeasured> (49.1%)
>     1.328 : 1 : ..label:checkout
>        0.000 : <unmeasured> ( 0.0%)
>        1.328 : 1 : ....label:unpack_trees
>           0.228 : <unmeasured> (17.2%)
>           0.566 : 1 : ......label:traverse_trees
>           0.388 : 1 : ......label:clear_ce_flags/0x00000000_0x02000000
>           0.125 : 1 : ......label:check_updates
>              0.125 : <unmeasured> (100.0%)
>              0.000 : 1 : ........label:Filtering content
>           0.021 : 1 : ......label:clear_ce_flags/0x00080000_0x42000000
>           0.000 : 1 : ......label:fully_valid
>     1.067 : 1 : ..label:do_write_index /_git/office/src/.git/index.lock
>        0.938 : <unmeasured> (87.9%)
>        0.129 : 1 : ....label:write/extension/cache_tree
>     0.230 : 1 : ..label:fully_valid
>     0.002 : 1 : ..label:incore_recursive
>        0.001 : <unmeasured> (22.3%)
>        0.001 : 1 : ....label:collect_merge_info
>           0.001 : <unmeasured> (60.2%)
>           0.000 : 1 : ......label:traverse_trees
>        0.001 : 1 : ....label:process_entries
>           0.000 : <unmeasured> ( 2.8%)
>           0.001 : 1 : ......label:finalize
>           0.000 : 1 : ......label:process_entries setup
>              0.000 : <unmeasured> ( 6.9%)
>              0.000 : 1 : ........label:plist sort
>              0.000 : 1 : ........label:plist copy
>              0.000 : 1 : ........label:plist grow
>           0.000 : 1 : ......label:processing
>        0.000 : 1 : ....label:merge_start
>           0.000 : <unmeasured> (50.0%)
>           0.000 : 1 : ......label:allocate/init
>           0.000 : 1 : ......label:sanity checks
>        0.000 : 1 : ....label:renames
>     0.001 : 1 : ..label:traverse_trees
>     0.000 : 1 : ..label:write_auto_merge
>     0.000 : 1 : ..label:check_updates
>     0.000 : 1 : ..label:setup
>     0.000 : 1 : ..label:display messages
>     0.000 : 1 : ..label:write back to queue
>     0.000 : 1 : ..label:record_unmerged
> Estimated measurement overhead (.010 ms/region-measure * 36): 0.00036
> Timing including forking:  5.174 (0.015 additional seconds)

> happening...
> 
> First, a few years ago, Ben said that merges in the Microsoft repos
> took about an hour[1]:
> "For the repro that I have been using this drops the merge time from ~1 hour to
> ~5 minutes and the unmerged entries goes down from ~40,000 to 1."
> The change he made to drop it that far was to turn off rename detection.
> 
> [1] https://lore.kernel.org/git/20180426205202.23056-1-benpeart@microsoft.com/
> 
> Keep that in mind, especially since your times are actually
> significantly less than 5 minutes...

>> $ /_git/git/summarize-perf git rebase --onto to from test
>> Successfully rebased and updated refs/heads/test.
>> Accumulated times:
>>     8.511 : <unmeasured> (74.9%)
> 
> Wild guess: This is setup_git_directory() loading your ~3 million entry index.

> .004s on label:incore_nonrecursive -- that's the actual merge
> operation.  This was a trivial rebase, and the merging took just 4
> milliseconds.  But the overall run took 11.442 seconds because working
> with 3M+ entries in the index just takes forever, and my code didn't
> touch any on-disk formats, certainly not the index format.
> 
> _All_ of my optimization work was on the merging piece, not the stuff
> outside.  But for what you're testing here, it appears to be
> irrelevant compared to the overhead.

>> And here are timings for a simple merge. Two files at root were changed in the
>> commits I made, but there are also some larger changes from the commit history.
>> These should all be seen as "this tree updated in one of the two, so take that
>> tree".
> 
> Ahah!  That's a microsoft-specific optimization you guys made in the
> recursive strategy, yes? 

> It does NOT exist in upstream git.  It's
> also one that is nearly incompatible with rename detection; it turns
> out you can only do that optimization in the face of rename detection
> if you do a HUGE amount of specialized work and tracking in order to
> determine when it's safe _despite_ needing to detect renames. 

> I
> thought that optimization was totally incompatible with rename
> detection for a long time; I tried it a couple times while working on
> ort and watched it break all kinds of rename tests...but I eventually
> discovered some tricks involving a lot of work to be able to run that
> optimization.

> So, you aren't comparing upstream "recursive" to "ort", you're
> comparing a tweaked version of recursive, and one that is incompatible
> with how recursive's rename detection work.  In fact, just to be clear
> in case you go looking, I suspect that this tweak is to be found
> within unpack_trees.c (which recursive relies on heavily).
> 
> Further, you've set it up so there are only a few files changed after
> unpack_trees returns.
> 
> In total, you have: (1) turned off rename detection (most my
> optimizations are for improving this factor, meaning I can't show an
> advantage), (2) you took advantage of no rename detection to implement
> trivial-tree merges (thus killing the main second advantage my
> algorithm has), and (3) you are looking at a case with a tiny number
> of changes for the merge algorithm to process (thus killing a third
> optimization that removes quadratic performance).  Those are my three
> big optimizations, and you've made them all irrelevant.  In fact,
> you're in an area I would have been worried that ort would do _worse_
> than recursive.  I track an awful lot of things and there is overhead
> in checking and filling all that information in; if there are only a
> few entries to merge, then all that information was a waste to collect
> and ort might be slower than recursive.  But then again, that should
> be a case where both algorithms are "nearly instantaneous" (or would
> be if it weren't for your 3M+ index entry repo causing run_builtin()'s
> call to setup_git_directory() in git.c to take a huge amount of time
> before the builtin is even called.)

> 5 seconds.  I do have to hand it to Ben and anyone else involved,
> though.  From 1 hour down to 5 seconds is pretty good, even if it was
> done by hacks (turning off rename detection, and then implementing
> trivial-tree merging that would have broken rename detection).  I
> suspect that whoever did that work might have found the unconditional
> discarding and re-reading of the index and fixed it as well?

> Heh, yeah 0.002 seconds for ..label:incore_recursive.  Only 2
> milliseconds to create the actual merge tree.  That does suggest you
> might have fun with 'git log -p --remerge-diff'; if you can redo
> merges in 2 milliseconds, showing them in git log output is very
> reasonable.  :-)

> Could we have some fun, though?  What if you have some merge or rebase
> involving lots of changes, and you turn rename detection back on, and
> you disable that trivial-tree resolution optimization that breaks
> recursive's rename detection handling...and then compare recursive and
> ort?  (It might be easiest to just compare upstream recursive rather
> than the one with all the microsoft changes to make sure you undid
> whatever trivial tree handling work exists.)

> For example, my testcase in the linux kernel was finding a series of a
> few dozen patches I could rebase back to an older version, but
> tweaking the "older" version by renaming drivers/ -> pilots/ (with
> about 26K files under that directory, that meant about 26K renames).
> So, I got to see rebasing of dozens of real changes across a massive
> rename boundary -- and the massive rename boundary also guaranteed
> there were lots of entries for the merge algorithm to deal with.
> 
> In the end, though, 4 milliseconds for the rebase and 2 milliseconds
> for the merge, with the rest all being overhead of interfacing to the
> index and working tree actually seems pretty good to me.  I'm just
> curious if we can check how things work for more involved cases.

>
> On 11/9/20 12:13 PM, Elijah Newren wrote:> Actually, this was pretty enlightening.  I think I know about what's
> > happening...
> >
> > First, a few years ago, Ben said that merges in the Microsoft repos
> > took about an hour[1]:
> > "For the repro that I have been using this drops the merge time from ~1 hour to
> > ~5 minutes and the unmerged entries goes down from ~40,000 to 1."
> > The change he made to drop it that far was to turn off rename detection.
> >
> > [1] https://lore.kernel.org/git/20180426205202.23056-1-benpeart@microsoft.com/
> >
> > Keep that in mind, especially since your times are actually
> > significantly less than 5 minutes...
>
> Yes, the other thing to keep in mind is that this is
> a Scalar repo with the default cone-mode sparse-checkout
> of only the files at root. For this repo, that means that
> there are only ~10 files actually present.
>
> I wanted to remove any working directory updates/checks
> from the performance check as possible.

> >> $ /_git/git/summarize-perf git rebase --onto to from test
> >> Successfully rebased and updated refs/heads/test.
> >> Accumulated times:
> >>     8.511 : <unmeasured> (74.9%)
> >
> > Wild guess: This is setup_git_directory() loading your ~3 million entry index.
>
> I think there is also some commit walking happening, but
> it shouldn't be too much. 'from' and 'to' are not very
> far away.

> > Did you include two runs of recursive and two runs of ort just to show
> > that the timings were stable and thus there wasn't warm or cold disk
> > cache issues affecting things?  If so, good plan.  (If there was
> > another reason, let me know; I missed it.)
>
> For the rebase, I did "--onto to from test" and "--onto from to test"
> to show both directions of the rebase. The merge I did twice for the
> cache issues ;)

> > .004s on label:incore_nonrecursive -- that's the actual merge
> > operation.  This was a trivial rebase, and the merging took just 4
> > milliseconds.  But the overall run took 11.442 seconds because working
> > with 3M+ entries in the index just takes forever, and my code didn't
> > touch any on-disk formats, certainly not the index format.
> >
> > _All_ of my optimization work was on the merging piece, not the stuff
> > outside.  But for what you're testing here, it appears to be
> > irrelevant compared to the overhead.
>
> OK, so since we already disable rename detection through config,
> the machinery that you are changing is already fast with the old
> algorithm in these trivial cases.
>
> To actually show any benefits, we would need to disable rename
> detection or use a larger change.

> >> And here are timings for a simple merge. Two files at root were changed in the
> >> commits I made, but there are also some larger changes from the commit history.
> >> These should all be seen as "this tree updated in one of the two, so take that
> >> tree".
> >
> > Ahah!  That's a microsoft-specific optimization you guys made in the
> > recursive strategy, yes?
>
> I'm not aware of any logic we have that's different from core Git.
> The config we use [1] includes "merge.stat = false" and "merge.renames
> = false" but otherwise seems to be using stock Git.
>
> [1] https://github.com/microsoft/scalar/blob/1d7938d2df6921f7a3b4f3f1cce56a00929adc40/Scalar.Common/Maintenance/ConfigStep.cs#L100-L127
>
> I'm CC'ing Jeff Hostetler to see if he knows anything about a custom
> merge algorithm in microsoft/git.

> > It does NOT exist in upstream git.  It's
> > also one that is nearly incompatible with rename detection; it turns
> > out you can only do that optimization in the face of rename detection
> > if you do a HUGE amount of specialized work and tracking in order to
> > determine when it's safe _despite_ needing to detect renames.
>
> Perhaps merge.renames=false is enough to trigger this logic already?

> > I
> > thought that optimization was totally incompatible with rename
> > detection for a long time; I tried it a couple times while working on
> > ort and watched it break all kinds of rename tests...but I eventually
> > discovered some tricks involving a lot of work to be able to run that
> > optimization.
>
> I will try to keep this in mind.
>
> > So, you aren't comparing upstream "recursive" to "ort", you're
> > comparing a tweaked version of recursive, and one that is incompatible
> > with how recursive's rename detection work.  In fact, just to be clear
> > in case you go looking, I suspect that this tweak is to be found
> > within unpack_trees.c (which recursive relies on heavily).
> >
> > Further, you've set it up so there are only a few files changed after
> > unpack_trees returns.
> >
> > In total, you have: (1) turned off rename detection (most my
> > optimizations are for improving this factor, meaning I can't show an
> > advantage), (2) you took advantage of no rename detection to implement
> > trivial-tree merges (thus killing the main second advantage my
> > algorithm has), and (3) you are looking at a case with a tiny number
> > of changes for the merge algorithm to process (thus killing a third
> > optimization that removes quadratic performance).  Those are my three
> > big optimizations, and you've made them all irrelevant.  In fact,
> > you're in an area I would have been worried that ort would do _worse_
> > than recursive.  I track an awful lot of things and there is overhead
> > in checking and filling all that information in; if there are only a
> > few entries to merge, then all that information was a waste to collect
> > and ort might be slower than recursive.  But then again, that should
> > be a case where both algorithms are "nearly instantaneous" (or would
> > be if it weren't for your 3M+ index entry repo causing run_builtin()'s
> > call to setup_git_directory() in git.c to take a huge amount of time
> > before the builtin is even called.)
>
> Thanks for your time isolating this case. I appreciate knowing exactly
> which portions of the merge algorithm are being touched and which are
> not.
> > 5 seconds.  I do have to hand it to Ben and anyone else involved,
> > though.  From 1 hour down to 5 seconds is pretty good, even if it was
> > done by hacks (turning off rename detection, and then implementing
> > trivial-tree merging that would have broken rename detection).  I
> > suspect that whoever did that work might have found the unconditional
> > discarding and re-reading of the index and fixed it as well?
>
> As you can probably tell from my general confusion, I had nothing
> to do with it. ;)
>
> > Heh, yeah 0.002 seconds for ..label:incore_recursive.  Only 2
> > milliseconds to create the actual merge tree.  That does suggest you
> > might have fun with 'git log -p --remerge-diff'; if you can redo
> > merges in 2 milliseconds, showing them in git log output is very
> > reasonable.  :-)
>
> Yeah, 'git merge-tree' is very fast for these cases, so I assumed
> that something else was going on for that command.

> > Could we have some fun, though?  What if you have some merge or rebase
> > involving lots of changes, and you turn rename detection back on, and
> > you disable that trivial-tree resolution optimization that breaks
> > recursive's rename detection handling...and then compare recursive and
> > ort?  (It might be easiest to just compare upstream recursive rather
> > than the one with all the microsoft changes to make sure you undid
> > whatever trivial tree handling work exists.)
>
> I can try these kinds of cases, but it won't be today. I'm on kid duty
> today, and answering emails in between running around with them.

> > For example, my testcase in the linux kernel was finding a series of a
> > few dozen patches I could rebase back to an older version, but
> > tweaking the "older" version by renaming drivers/ -> pilots/ (with
> > about 26K files under that directory, that meant about 26K renames).
> > So, I got to see rebasing of dozens of real changes across a massive
> > rename boundary -- and the massive rename boundary also guaranteed
> > there were lots of entries for the merge algorithm to deal with.
> >
> > In the end, though, 4 milliseconds for the rebase and 2 milliseconds
> > for the merge, with the rest all being overhead of interfacing to the
> > index and working tree actually seems pretty good to me.  I'm just
> > curious if we can check how things work for more involved cases.
>
> I'm definitely interested in identifying how your algorithm improves
> over the previous cases, and perhaps re-enabling rename detection for
> merges is enough of a benefit to justify the new one.
>
> Eventually, I hope to actually engage with your patches in the form
> of review. Just trying to build a mental model for what's going on
> first.

> Elijah Newren (20):
>   merge-ort: setup basic internal data structures
>   merge-ort: add some high-level algorithm structure
>   merge-ort: port merge_start() from merge-recursive
>   merge-ort: use histogram diff
>   merge-ort: add an err() function similar to one from merge-recursive
>   merge-ort: implement a very basic collect_merge_info()
>   merge-ort: avoid repeating fill_tree_descriptor() on the same tree
>   merge-ort: compute a few more useful fields for collect_merge_info
>   merge-ort: record stage and auxiliary info for every path
>   merge-ort: avoid recursing into identical trees
>   merge-ort: add a preliminary simple process_entries() implementation
>   merge-ort: have process_entries operate in a defined order

>   merge-ort: step 1 of tree writing -- record basenames, modes, and oids
>   merge-ort: step 2 of tree writing -- function to create tree object
>   merge-ort: step 3 of tree writing -- handling subdirectories as we go
>   merge-ort: basic outline for merge_switch_to_result()
>   merge-ort: add implementation of checkout()
>   tree: enable cmp_cache_name_compare() to be used elsewhere
>   merge-ort: add implementation of record_unmerged_index_entries()
>   merge-ort: free data structures in merge_finalize()

>
> On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > Elijah Newren (20):
> >   merge-ort: setup basic internal data structures
> >   merge-ort: add some high-level algorithm structure
> >   merge-ort: port merge_start() from merge-recursive
> >   merge-ort: use histogram diff
> >   merge-ort: add an err() function similar to one from merge-recursive
> >   merge-ort: implement a very basic collect_merge_info()
> >   merge-ort: avoid repeating fill_tree_descriptor() on the same tree
> >   merge-ort: compute a few more useful fields for collect_merge_info
> >   merge-ort: record stage and auxiliary info for every path
> >   merge-ort: avoid recursing into identical trees
> >   merge-ort: add a preliminary simple process_entries() implementation
> >   merge-ort: have process_entries operate in a defined order
>
> I got this far before my attention to detail really started slipping.
>
> >   merge-ort: step 1 of tree writing -- record basenames, modes, and oids
> >   merge-ort: step 2 of tree writing -- function to create tree object
> >   merge-ort: step 3 of tree writing -- handling subdirectories as we go
> >   merge-ort: basic outline for merge_switch_to_result()
> >   merge-ort: add implementation of checkout()
> >   tree: enable cmp_cache_name_compare() to be used elsewhere
> >   merge-ort: add implementation of record_unmerged_index_entries()
> >   merge-ort: free data structures in merge_finalize()
>
> I'll try to take another pass on these commits tomorrow.
>
> For the series as a whole I'd love to see at least one test that
> demonstrates that this code does something, if even only for a very
> narrow case.
>
> There's a lot of code being moved here, and it would be nice to have
> even a very simple test case that can check that we didn't leave any
> important die("not implemented") calls lying around or worse accessing
> an uninitialized pointer or something.

> On Wed, Nov 11, 2020 at 9:09 AM Derrick Stolee <stolee@gmail.com> wrote:
>> For the series as a whole I'd love to see at least one test that
>> demonstrates that this code does something, if even only for a very
>> narrow case.
>>
>> There's a lot of code being moved here, and it would be nice to have
>> even a very simple test case that can check that we didn't leave any
>> important die("not implemented") calls lying around or worse accessing
>> an uninitialized pointer or something.
> 
> We absolutely left several die("not implemented") calls lying around.
> The series was long enough at 20 patches; reviewers lose steam at 10
> (at least both you and Jonathan have), so maybe I should have left
> even more in there as an attempt to split up this series more.
> 
> However, if you run the testsuite with GIT_TEST_MERGE_ALGORITHM=ort,
> then this series drops the number of failures in the testsuite from
> around 2200, down to 1500.  So, there's about 700 testcases for you.

>
> On 11/11/2020 1:35 PM, Elijah Newren wrote:
> > On Wed, Nov 11, 2020 at 9:09 AM Derrick Stolee <stolee@gmail.com> wrote:
> >> For the series as a whole I'd love to see at least one test that
> >> demonstrates that this code does something, if even only for a very
> >> narrow case.
> >>
> >> There's a lot of code being moved here, and it would be nice to have
> >> even a very simple test case that can check that we didn't leave any
> >> important die("not implemented") calls lying around or worse accessing
> >> an uninitialized pointer or something.
> >
> > We absolutely left several die("not implemented") calls lying around.
> > The series was long enough at 20 patches; reviewers lose steam at 10
> > (at least both you and Jonathan have), so maybe I should have left
> > even more in there as an attempt to split up this series more.
> >
> > However, if you run the testsuite with GIT_TEST_MERGE_ALGORITHM=ort,
> > then this series drops the number of failures in the testsuite from
> > around 2200, down to 1500.  So, there's about 700 testcases for you.
>
> Sorry that I'm jumping in to the series-of-series in the middle, so
> I am unfamiliar with the previous progress and testing strategy. This