git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2 15/20] merge-ort: step 3 of tree writing -- handling subdirectories as we go

From
Elijah Newren <newren@gmail.com>
Date
Nov 12, 2020, 22:30 UTC
Message-ID
<CABPp-BFwn5+S_swrtZEq6DmZx6kbB0xO_d=ZJkqs4H6FG1vo1Q@mail.gmail.com>
In-Reply-To
<20201112201524.3438029-1-jonathantanmy@google.com>
On Thu, Nov 12, 2020 at 12:15 PM Jonathan Tan <jonathantanmy@google.com> wrote:
Show 29 quoted lines
>
> 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"?

No, it's a simple cache of strlen(info->last_directory), so I don't have to recompute that length multiple times. Perhaps I should add a comment to that effect.

Show 22 quoted lines
> >  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.

Checking ci->filemask is likely an out-of-bounds memory read if ci->merged.clean is true. (ci may point to something that was allocated with the size of a merge_info or a conflict_info.) Perhaps I could extend the comment to say that conflicted directories, i.e. paths that are unclean with ci->filemask == 0 can be skipped because they were already handled.

Show 14 quoted lines
> > +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.
Yes, precisely.
Show 5 quoted lines
> 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).

Good news: Interned strings already are stored as the keys of our primary data structure -- the strmap known as opt->priv->paths. All relative paths from the root of the repository that are relevant to the merge at all -- both for files and directories -- are interned by collect_merge_info() inside that "paths" strmap.

I guess I should note that it eventually gets _slightly_ more complicated. Due to renames and directory renames, I might need to remove a path from opt->priv->paths. In such a case there will be an auxiliary string_list named "paths_to_free" that stores the interned strings which are no longer part of opt->priv->paths.

Show 32 quoted lines
> > +     /*
> > +      * 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.
Oops, that code has been heavily refactored since that comment.
Something like this would be more up-to-date:
    /*
     * The next entry will be within new_directory_name.  Since at this
     * point we know that new_directory_name is within a different
     * directory than info->last_directory, we have all entries for
     * info->last_directory in info->versions and we need to create a
     * tree object for them.
     */
Show 16 quoted lines
> > +     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?

Yes, it is possible that all files within the directory become empty as a result of merging[1], and in such cases this line of logic will trigger (note that record_entry_for_tree(), which is what adds more items to info->versions, returns early if ci->merged.is_null). We do not want to write out an empty tree for the directory or record the tree's hash for its parent directory, we simply want to omit it entirely. Omitting it entirely is handled by the line "dir_info->is_null = 1".

[1] The simplest example is when one side doesn't touch anything within a directory but the other side deletes the whole directory. Files can also disappear in a merge for other reasons, such as being deleted on both sides, or being renamed. If _all_ files within the directory are removed by the merge logic, the directory has no entries.

Show 44 quoted lines
>
> > +     /*
> > +      * 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.
Interesting, I'll take a look into it.
Show 38 quoted lines
>
> > +     /*
> > +      * 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.

Yeah, write_completed_directory() would be better. And just to reiterate on the offset == info->versions.nr thing, we do not want to write a tree if it turns out that the merged result of all files within the directory is to delete them all.

Show 30 quoted lines
> 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).

I'm not sure how the BEGIN_TREE/END_TREE entries would look, but I'll investigate.

Previous: Jonathan TanNext: Elijah Newren
Message 24 of 83 in “fundamentals of merge-ort implementation”
  1. 00/20 fundamentals of merge-ort implementationElijah Newren, Nov 2, 2020
  2. 10/20 merge-ort: avoid recursing into identical treesElijah Newren, Nov 2, 2020
  3. Derrick StoleeNov 11, 2020
  4. 08/20 merge-ort: compute a few more useful fields for collect_merge_infoElijah Newren, Nov 2, 2020
  5. Jonathan TanNov 6, 2020
  6. Elijah NewrenNov 6, 2020
  7. Jonathan TanNov 9, 2020
  8. Elijah NewrenNov 9, 2020
  9. 11/20 merge-ort: add a preliminary simple process_entries() implementationElijah Newren, Nov 2, 2020
  10. Jonathan TanNov 11, 2020
  11. Elijah NewrenNov 12, 2020
  12. 09/20 merge-ort: record stage and auxiliary info for every pathElijah Newren, Nov 2, 2020
  13. Jonathan TanNov 6, 2020
  14. Elijah NewrenNov 7, 2020
  15. Jonathan TanNov 9, 2020
  16. Elijah NewrenNov 9, 2020
  17. Derrick StoleeNov 11, 2020
  18. Elijah NewrenNov 11, 2020
  19. Elijah NewrenNov 11, 2020
  20. Derrick StoleeNov 12, 2020
  21. Derrick StoleeNov 12, 2020
  22. 15/20 merge-ort: step 3 of tree writing -- handling subdirectories as we goElijah Newren, Nov 2, 2020
  23. Jonathan TanNov 12, 2020
  24. Elijah NewrenNov 12, 2020
  25. Elijah NewrenNov 24, 2020
  26. Jonathan TanNov 25, 2020
  27. Elijah NewrenNov 26, 2020
  28. Jonathan TanNov 30, 2020
  29. 17/20 merge-ort: add implementation of checkout()Elijah Newren, Nov 2, 2020
  30. 18/20 tree: enable cmp_cache_name_compare() to be used elsewhereElijah Newren, Nov 2, 2020
  31. 14/20 merge-ort: step 2 of tree writing -- function to create tree objectElijah Newren, Nov 2, 2020
  32. Jonathan TanNov 11, 2020
  33. Elijah NewrenNov 11, 2020
  34. 19/20 merge-ort: add implementation of record_unmerged_index_entries()Elijah Newren, Nov 2, 2020
  35. 20/20 merge-ort: free data structures in merge_finalize()Elijah Newren, Nov 2, 2020
  36. 16/20 merge-ort: basic outline for merge_switch_to_result()Elijah Newren, Nov 2, 2020
  37. 12/20 merge-ort: have process_entries operate in a defined orderElijah Newren, Nov 2, 2020
  38. Derrick StoleeNov 11, 2020
  39. Elijah NewrenNov 11, 2020
  40. 13/20 merge-ort: step 1 of tree writing -- record basenames, modes, and oidsElijah Newren, Nov 2, 2020
  41. Jonathan TanNov 11, 2020
  42. Elijah NewrenNov 11, 2020
  43. Jonathan TanNov 12, 2020
  44. 07/20 merge-ort: avoid repeating fill_tree_descriptor() on the same treeElijah Newren, Nov 2, 2020
  45. Derrick StoleeNov 11, 2020
  46. Elijah NewrenNov 11, 2020
  47. Eric SunshineNov 11, 2020
  48. 05/20 merge-ort: add an err() function similar to one from merge-recursiveElijah Newren, Nov 2, 2020
  49. Derrick StoleeNov 11, 2020
  50. Elijah NewrenNov 11, 2020
  51. Derrick StoleeNov 11, 2020
  52. 01/20 merge-ort: setup basic internal data structuresElijah Newren, Nov 2, 2020
  53. Jonathan TanNov 6, 2020
  54. Elijah NewrenNov 6, 2020
  55. Jonathan TanNov 9, 2020
  56. 02/20 merge-ort: add some high-level algorithm structureElijah Newren, Nov 2, 2020
  57. 03/20 merge-ort: port merge_start() from merge-recursiveElijah Newren, Nov 2, 2020
  58. Derrick StoleeNov 11, 2020
  59. Elijah NewrenNov 11, 2020
  60. 04/20 merge-ort: use histogram diffElijah Newren, Nov 2, 2020
  61. Derrick StoleeNov 11, 2020
  62. Elijah NewrenNov 11, 2020
  63. Derrick StoleeNov 11, 2020
  64. Elijah NewrenNov 11, 2020
  65. 06/20 merge-ort: implement a very basic collect_merge_info()Elijah Newren, Nov 2, 2020
  66. Jonathan TanNov 6, 2020
  67. Elijah NewrenNov 6, 2020
  68. Jonathan TanNov 9, 2020
  69. Derrick StoleeNov 11, 2020
  70. Elijah NewrenNov 11, 2020
  71. Derrick StoleeNov 3, 2020
  72. Elijah NewrenNov 3, 2020
  73. Elijah NewrenNov 7, 2020
  74. Derrick StoleeNov 7, 2020
  75. Elijah NewrenNov 7, 2020
  76. Derrick StoleeNov 9, 2020
  77. Elijah NewrenNov 9, 2020
  78. Derrick StoleeNov 9, 2020
  79. Elijah NewrenNov 9, 2020
  80. Derrick StoleeNov 11, 2020
  81. Elijah NewrenNov 11, 2020
  82. Derrick StoleeNov 11, 2020
  83. Elijah NewrenNov 11, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.