Re: [PATCH v5 10/14] diff-lib: handle index diffs with sparse dirs

>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> While comparing an index to a tree, we may see a sparse directory entry.
> In this case, we should compare that portion of the tree to the tree
> represented by that entry. This could include a new tree which needs to
> be expanded to a full list of added files. It could also include an
> existing tree, in which case all of the changes inside are important to
> describe, including the modifications, additions, and deletions. Note
> that the case where the tree has a path and the index does not remains
> identical to before: the lack of a cache entry is the same with a sparse
> index.
>
> In the case where a tree is modified, we need to expand the tree
> recursively, and start comparing each contained entry as either an
> addition, deletion, or modification. This causes an interesting
> recursion that did not exist before.

> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  diff-lib.c | 188 +++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 188 insertions(+)
>
> diff --git a/diff-lib.c b/diff-lib.c
> index b73cc1859a49..ba4c683d4bc4 100644
> --- a/diff-lib.c
> +++ b/diff-lib.c
> @@ -314,6 +314,48 @@ static int get_stat_data(const struct cache_entry *ce,
>         return 0;
>  }
>
> +struct show_new_tree_context {
> +       struct rev_info *revs;
> +       unsigned added:1;
> +};
> +
> +static int show_new_file_from_tree(const struct object_id *oid,
> +                                  struct strbuf *base, const char *path,
> +                                  unsigned int mode, void *context)
> +{
> +       struct show_new_tree_context *ctx = context;
> +       struct cache_entry *new_file = make_transient_cache_entry(mode, oid, path, /* stage */ 0);
> +
> +       diff_index_show_file(ctx->revs, ctx->added ? "+" : "-", new_file, oid, !is_null_oid(oid), mode, 0);
> +       discard_cache_entry(new_file);
> +       return 0;
> +}
> +
> +static void show_directory(struct rev_info *revs,
> +                          const struct cache_entry *new_dir,
> +                          int added)
> +{
> +       /*
> +        * new_dir is a sparse directory entry, so we want to collect all
> +        * of the new files within the tree. This requires recursively
> +        * expanding the trees.
> +        */
> +       struct show_new_tree_context ctx = { revs, added };
> +       struct repository *r = revs->repo;
> +       struct strbuf base = STRBUF_INIT;
> +       struct pathspec ps;
> +       struct tree *tree = lookup_tree(r, &new_dir->oid);
> +
> +       memset(&ps, 0, sizeof(ps));
> +       ps.recursive = 1;
> +       ps.has_wildcard = 1;
> +       ps.max_depth = -1;
> +
> +       strbuf_add(&base, new_dir->name, new_dir->ce_namelen);
> +       read_tree_at(r, tree, &base, &ps,
> +                       show_new_file_from_tree, &ctx);
> +}
> +
>  static void show_new_file(struct rev_info *revs,
>                           const struct cache_entry *new_file,
>                           int cached, int match_missing)
> @@ -322,6 +364,11 @@ static void show_new_file(struct rev_info *revs,
>         unsigned int mode;
>         unsigned dirty_submodule = 0;
>
> +       if (new_file && S_ISSPARSEDIR(new_file->ce_mode)) {
> +               show_directory(revs, new_file, /*added */ 1);
> +               return;
> +       }
> +
>         /*
>          * New file in the index: it might actually be different in
>          * the working tree.
> @@ -333,6 +380,136 @@ static void show_new_file(struct rev_info *revs,
>         diff_index_show_file(revs, "+", new_file, oid, !is_null_oid(oid), mode, dirty_submodule);
>  }
>
> +static int show_modified(struct rev_info *revs,
> +                        const struct cache_entry *old_entry,
> +                        const struct cache_entry *new_entry,
> +                        int report_missing,
> +                        int cached, int match_missing);
> +
> +static int compare_within_sparse_dir(int n, unsigned long mask,
> +                                    unsigned long dirmask, struct name_entry *entry,
> +                                    struct traverse_info *info)
> +{
> +       struct rev_info *revs = info->data;
> +       struct object_id *oid0 = &entry[0].oid;
> +       struct object_id *oid1 = &entry[1].oid;
> +
> +       if (oideq(oid0, oid1))
> +               return mask;
> +
> +       /* Directory/file conflicts are handled earlier. */
> +       if (S_ISDIR(entry[0].mode) && S_ISDIR(entry[1].mode)) {
> +               struct tree_desc t[2];
> +               void *buf[2];
> +               struct traverse_info info_r = { NULL, };
> +
> +               info_r.name = xstrfmt("%s%s", info->traverse_path, entry[0].path);
> +               info_r.namelen = strlen(info_r.name);
> +               info_r.traverse_path = xstrfmt("%s/", info_r.name);
> +               info_r.fn = compare_within_sparse_dir;
> +               info_r.prev = info;
> +               info_r.mode = entry[0].mode;
> +               info_r.pathlen = entry[0].pathlen;
> +               info_r.df_conflicts = 0;
> +               info_r.data = revs;
> +
> +               buf[0] = fill_tree_descriptor(revs->repo, &t[0], oid0);
> +               buf[1] = fill_tree_descriptor(revs->repo, &t[1], oid1);
> +
> +               traverse_trees(NULL, 2, t, &info_r);
> +
> +               free((char *)info_r.name);
> +               free((char *)info_r.traverse_path);
> +               free(buf[0]);
> +               free(buf[1]);
> +       } else {
> +               char *old_path = NULL, *new_path = NULL;
> +               struct cache_entry *old_entry = NULL, *new_entry = NULL;
> +
> +               if (entry[0].path) {
> +                       old_path = xstrfmt("%s%s", info->traverse_path, entry[0].path);
> +                       old_entry = make_transient_cache_entry(
> +                                       entry[0].mode, &entry[0].oid,
> +                                       old_path, /* stage */ 0);
> +                       old_entry->ce_flags |= CE_SKIP_WORKTREE;
> +               }
> +               if (entry[1].path) {
> +                       new_path = xstrfmt("%s%s", info->traverse_path, entry[1].path);
> +                       new_entry = make_transient_cache_entry(
> +                                       entry[1].mode, &entry[1].oid,
> +                                       new_path, /* stage */ 0);
> +                       new_entry->ce_flags |= CE_SKIP_WORKTREE;
> +               }
> +
> +               if (entry[0].path && entry[1].path)
> +                       show_modified(revs, old_entry, new_entry, 0, 1, 0);
> +               else if (entry[0].path)
> +                       diff_index_show_file(revs, revs->prefix,
> +                                            old_entry, &entry[0].oid,
> +                                            0, entry[0].mode, 0);
> +               else if (entry[1].path)
> +                       show_new_file(revs, new_entry, 1, 0);
> +
> +               discard_cache_entry(old_entry);
> +               discard_cache_entry(new_entry);
> +               free(old_path);
> +               free(new_path);
> +       }
> +
> +       return mask;
> +}
> +
> +static void show_modified_sparse_directory(struct rev_info *revs,
> +                        const struct cache_entry *old_entry,
> +                        const struct cache_entry *new_entry,
> +                        int report_missing,
> +                        int cached, int match_missing)
> +{
> +       struct tree_desc t[2];
> +       void *buf[2];
> +       struct traverse_info info = { NULL };
> +       struct strbuf name = STRBUF_INIT;
> +       struct strbuf parent_path = STRBUF_INIT;
> +       char *last_dir_sep;
> +
> +       if (oideq(&old_entry->oid, &new_entry->oid))
> +               return;
> +
> +       info.fn = compare_within_sparse_dir;
> +       info.prev = &info;
> +
> +       strbuf_add(&name, new_entry->name, new_entry->ce_namelen - 1);
> +       info.name = name.buf;
> +       info.namelen = name.len;
> +
> +       strbuf_add(&parent_path, new_entry->name, new_entry->ce_namelen - 1);
> +       if ((last_dir_sep = find_last_dir_sep(parent_path.buf)) > parent_path.buf)
> +               strbuf_setlen(&parent_path, (last_dir_sep - parent_path.buf) - 1);
> +       else
> +               strbuf_setlen(&parent_path, 0);
> +
> +       info.pathlen = parent_path.len;
> +
> +       if (parent_path.len)
> +               info.traverse_path = parent_path.buf;
> +       else
> +               info.traverse_path = "";
> +
> +       info.mode = new_entry->ce_mode;
> +       info.df_conflicts = 0;
> +       info.data = revs;
> +
> +       buf[0] = fill_tree_descriptor(revs->repo, &t[0], &old_entry->oid);
> +       buf[1] = fill_tree_descriptor(revs->repo, &t[1], &new_entry->oid);
> +
> +       traverse_trees(NULL, 2, t, &info);
> +
> +       free(buf[0]);
> +       free(buf[1]);
> +       strbuf_release(&name);
> +       strbuf_release(&parent_path);
> +}
> +
>  static int show_modified(struct rev_info *revs,
>                          const struct cache_entry *old_entry,
>                          const struct cache_entry *new_entry,
> @@ -343,6 +520,17 @@ static int show_modified(struct rev_info *revs,
>         const struct object_id *oid;
>         unsigned dirty_submodule = 0;
>
> +       /*
> +        * If both are sparse directory entries, then expand the
> +        * modifications to the file level.
> +        */
> +       if (old_entry && new_entry &&
> +           S_ISSPARSEDIR(old_entry->ce_mode) &&
> +           S_ISSPARSEDIR(new_entry->ce_mode)) {
> +               show_modified_sparse_directory(revs, old_entry, new_entry, report_missing, cached, match_missing);
> +               return 0;
> +       }
> +
>         if (get_stat_data(new_entry, &oid, &mode, cached, match_missing,
>                           &dirty_submodule, &revs->diffopt) < 0) {
>                 if (report_missing)
> --
> gitgitgadget
>