Re: [PATCH v7 19/31] merge-recursive: add get_directory_renames()

[Elijah Newren <newren@gmail.com>]

On Fri, Feb 2, 2018 at 5:02 PM, Stefan Beller <sbeller@google.com> wrote:
> On Tue, Jan 30, 2018 at 3:25 PM, Elijah Newren <newren@gmail.com> wrote:

>> +       /* For
>
> comment style.

Fixed it and looked through the file for any other violations and
fixed the ones introduced in this series.  (The ones I added years ago
in other places of the file I just left.)

>> +        *    "a/b/c/d/foo.c" -> "a/b/something-else/d/foo.c"
>> +        * the "d/foo.c" part is the same, we just want to know that
>> +        *    "a/b/c" was renamed to "a/b/something-else"
>> +        * so, for this example, this function returns "a/b/c" in
>> +        * *old_dir and "a/b/something-else" in *new_dir.
>
> So we would not see multi-directory renames?
>
>     "a/b/c/d/foo.c" -> "a/b/something-else/e/foo.c"
>
> could be detected as
>
>     "a/b/{c/d/ => something-else/e}/foo.c"
>
> I assume this patch series is not bringing that to the table.
> (which is fine, I am just wondering)

I fully intended to support that, and believe the code does.  I
changed the comment as follows to try to make it clearer:

    /*
     * For
     *    "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c"
     * the "e/foo.c" part is the same, we just want to know that
     *    "a/b/c/d" was renamed to "a/b/some/thing/else"
     * so, for this example, this function returns "a/b/c/d" in
     * *old_dir and "a/b/some/thing/else" in *new_dir.
     *
     * Also, if the basename of the file changed, we don't care.  We
     * want to know which portion of the directory, if any, changed.
     */

Is that better?

>> +        *
>> +        * Also, if the basename of the file changed, we don't care.  We
>> +        * want to know which portion of the directory, if any, changed.
>> +        */
>> +       end_of_old = strrchr(old_path, '/');
>> +       end_of_new = strrchr(new_path, '/');
>> +
>> +       if (end_of_old == NULL || end_of_new == NULL)
>> +               return;
>
> return early as the files are in the top level, and apparently we do
> not support top level renaming?
>
> What about a commit like 81b50f3ce4 (Move 'builtin-*' into
> a 'builtin/' subdirectory, 2010-02-22) ?
>
> Well that specific commit left many files outside the new builtin dir,
> but conceptually we could see a directory rename of
>
>     /* => /src/*

We had some internal usecases for want to support a "rename" of the
toplevel directory into a subdirectory of itself.  However, attempting
to support that opened much too big a can of worms for me.  We'd open
up some big surprises somewhere.

In particular, note that not supporting a "rename" of the toplevel
directory is a special case of not supporting a "rename" of any
directory to a subdirectory below itself, which in turn is a very
special case of excluding partial directory renames.  I addressed this
in the cover letter of my original submission, as follows:

"""
Further, there's a basic question about when directory rename detection
should be applied at all.  I have a simple rule:

  3) If a given directory still exists on both sides of a merge, we do
     not consider it to have been renamed.

Rule 3 may sound obvious at first, but it will probably arise as a
question for some users -- what if someone "mostly" moved a directory but
still left some files around, or, equivalently (from the perspective of the
three-way merge that merge-recursive performs), fully renamed a directory
in one commmit and then recreated that directory in a later commit adding
some new files and then tried to merge?  See the big comment in section 4
of the new t6043 for further discussion of this rule.
"""

Patch 04/31 is the one that adds that big comment with further discussion.

Maybe there's a way to support toplevel renames, but I think it'd make
this series longer and more complicated...and may cause more edge
cases that confuse users.

>> +       while (*--end_of_new == *--end_of_old &&
>> +              end_of_old != old_path &&
>> +              end_of_new != new_path)
>> +               ; /* Do nothing; all in the while loop */
>
> We have to compare manually as we'd want to find
> the first non-equal and there doesn't seem to be a good
> library function for that.
>
> Assuming many repos are UTF8 (including in their paths),
> how does this work with display characters longer than one char?
> It should be fine as we cut at the slash?

Oh, UTF-8.  Ugh.
Can UTF-8 characters, other than '/', have a byte whose value matches
(unsigned char)('/')?  If so, then I'll need to figure out how to do
utf-8 character parsing.  Anyone have pointers?

>> +       /*
>> +        * We've found the first non-matching character in the directory
>> +        * paths.  That means the current directory we were comparing
>> +        * represents the rename.  Move end_of_old and end_of_new back
>> +        * to the full directory name.
>> +        */
>> +       if (*end_of_old == '/')
>> +               end_of_old++;
>> +       if (*end_of_old != '/')
>> +               end_of_new++;
>> +       end_of_old = strchr(end_of_old, '/');
>> +       end_of_new = strchr(end_of_new, '/');
>> +
>> +       /*
>> +        * It may have been the case that old_path and new_path were the same
>> +        * directory all along.  Don't claim a rename if they're the same.
>> +        */
>> +       old_len = end_of_old - old_path;
>> +       new_len = end_of_new - new_path;
>> +
>> +       if (old_len != new_len || strncmp(old_path, new_path, old_len)) {
>
> How often are we going to see this string-is-equal case?
> Would it make sense to do that first in the function?

We don't have old_len at that point, and old_len != strlen(old_path).
In particular, this is for comparing directories, and old_path and
new_path both stored file paths.
In particular, I think the most common case is someone renaming e.g.
   a/b/file.c -> a/b/newfile.c
The filenames are different, but the directory name is not.  Trying to
compare at the beginning of the function would thus give us the wrong
information.

So the check really needs to be done at this point of the function.

>> +       dir_renames = malloc(sizeof(struct hashmap));
>
> xmalloc

Thanks; I also looked for any other malloc uses I introduced, but it
looks like you caught both of them.  I'll fix them up.

>
>> +       dir_rename_init(dir_renames);
>> +       for (i = 0; i < pairs->nr; ++i) {
>> +               struct string_list_item *item;
>> +               int *count;
>> +               struct diff_filepair *pair = pairs->queue[i];
>> +               char *old_dir, *new_dir;
>> +
>> +               /* File not part of directory rename if it wasn't renamed */
>> +               if (pair->status != 'R')
>> +                       continue;
>> +
>> +               get_renamed_dir_portion(pair->one->path, pair->two->path,
>> +                                       &old_dir,        &new_dir);
>> +               if (!old_dir)
>> +                       /* Directory didn't change at all; ignore this one. */
>> +                       continue;
>
>
> So the first loop is about counting the number of files in each directory
> that are renamed and the later while loop is about mapping them?

Close; would adding the following comment at the top of the function help?

    /*
     * Typically, we think of a directory rename as all files from a
     * certain directory being moved to a target directory.  However,
     * what if someone first moved two files from the original
     * directory in one commit, and then renamed the directory
     * somewhere else in a later commit?  At merge time, we just know
     * that files from the original directory went to two different
     * places, and that the bulk of them ended up in the same place.
     * We want each directory rename to follow the bulk of the files
     * from that directory.  This function exists to find where the
     * bulk of the files went.
     *
     * The first loop below simply iterates through the list of
     * renames, adding up all the rename source->target locations with
     * a count.
     *
     * The second loop compares the count for each renamed directory
     * and declares the "winning" target location.
     */

Is there any part that remains unclear with that comment?  (Also, is
that comment too long?)

>> +               /* Strings were xstrndup'ed before inserting into string-list,
>> +                * so ask string_list to remove the entries for us.
>> +                */
>
> comment style.

Thanks.

>> +               entry->possible_new_dirs.strdup_strings = 1;
>
> Why do we need to set strdup_strings here (so late in the
> game, we are about to clear it?) Could we set it earlier?
>
> Or rather have the string list duplicate the strings instead of
> get_renamed_dir_portion ?

We didn't strdup the original string (a file path) as-is, we
strndup'ed a subset of the original string (just the relevant portion
of the directory).  Since we already had to allocate a special string
for that, making the string list duplicate the strings would have
caused an extra unnecessary allocation and required us to free the
memory allocated by get_renamed_dir_portion manually.  So, we do need
this here.

Does this comment make it clearer?:

        /*
         * The relevant directory sub-portion of the original full
         * filepaths were xstrndup'ed before inserting into
         * possible_new_dirs, and instead of manually iterating the
         * list and free'ing each, just lie and tell
         * possible_new_dirs that it did the strdup'ing so that it
         * will free them for us.
         */
        entry->possible_new_dirs.strdup_strings = 1;
        string_list_clear(&entry->possible_new_dirs, 1);