mktree: support more flexible usage

The goal of this series is to make 'git mktree' a much more flexible and powerful tool for constructing arbitrary trees in memory without the use of an index or worktree. The main additions are:

* Using an optional "base tree" to add or replace entries in an existing tree rather than creating a new one from scratch.
* Building off of this, having entries with mode "0" indicate "remove this entry, if it exists, from the tree"
* Handling tree entries inside of subtrees (e.g., folder1/my-file.txt)

It also introduces some quality-of-life updates:

* Using the same input parsing as 'update-index' to allow a wider variety of tree entry formats.
* Adding deduplication of input entries & more thorough validation of inputs (with an option to disable both - plus input sorting - if desired with '--literally').

The implementation change underpinning the new features is completely revamping how the tree is constructed in memory. Instead of writing a single tree object into a strbuf and hashing it into the object database, we construct an in-core sparse index and write out the root tree, as well as any new subtrees, using the cache tree infrastructure.

The series is organized as follows:

* Commits 1-3 contain miscellaneous small renames/refactors to make the code more readable & prepare for larger refactoring later.
* Commits 4-7 generalize the input parsing performed by 'read_index_info()' in 'update-index' and update 'mktree' to use it.
* Commit 8 adds the '--literally' option to 'mktree'. Practically, this option allows tests that currently use 'mktree' to generate corrupt trees to continue functioning after we strengthen input validations.
* Commits 9 & 10 add input path validation & entry deduplication, respectively.
* Commit 11 replaces the strbuf-to-object tree creation with construction of an in-core index & writing out the cache tree.
* Commits 12-14 add the ability to add tree entries to an existing "base" tree. Takes 3 commits to do it because it requires a bit of finesse around directory/file deduplication and iterating over a tree with 'read_tree()' with a parallel iteration over the input tree entries.
* Commit 15 allows for deeper paths in the input.
* Commit 16 adds handling for mode '0' as "removal" entries.

I also plan to add a '--strict' option that runs 'fsck' checks on the new tree(s) before writing to the object database (similar to 'mkttag --strict'), but this series is pretty long as it is and that part can easily be separated out into its own series.

Thanks!

* Victoria

Victoria Dye (16):
mktree: use OPT_BOOL
mktree: rename treeent to tree_entry
mktree: use non-static tree_entry array
update-index: generalize 'read_index_info' index-info.c: identify empty input lines in read_index_info index-info.c: parse object type in provided in read_index_info
mktree: use read_index_info to read stdin lines
mktree: add a --literally option
mktree: validate paths more carefully
mktree: overwrite duplicate entries
mktree: create tree using an in-core index
mktree: use iterator struct to add tree entries to index
mktree: add directory-file conflict hashmap
mktree: optionally add to an existing tree
mktree: allow deeper paths in input
mktree: remove entries when mode is 0

 Documentation/git-mktree.txt       |  42 +-
 Makefile                           |   1 +
 builtin/mktree.c                   | 595 +++++++++++++++++++++++------
 builtin/update-index.c             | 119 ++----
 index-info.c                       | 104 +++++
 index-info.h                       |  14 +
 t/t1010-mktree.sh                  | 354 ++++++++++++++++-
 t/t1014-read-tree-confusing.sh     |   6 +-
 t/t1450-fsck.sh                    |   4 +-
 t/t1601-index-bogus.sh             |   2 +-
 t/t1700-split-index.sh             |   6 +-
 t/t2107-update-index-basic.sh      |  32 ++
 t/t7008-filter-branch-null-sha1.sh |   6 +-
 t/t7417-submodule-path-url.sh      |   2 +-
 t/t7450-bad-git-dotfiles.sh        |   8 +-
 15 files changed, 1055 insertions(+), 240 deletions(-)
 create mode 100644 index-info.c
 create mode 100644 index-info.h

base-commit: 8d94cfb54504f2ec9edc7ca3eb5c29a3dd3675ae
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1746%2Fvdye%2Fvdye%2Fmktree-recursive-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1746/vdye/vdye/mktree-recursive-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1746

gitgitgadget

From: Victoria Dye <[email protected]>

Replace 'OPT_SET_INT' with 'OPT_BOOL' for the options '--missing' and '--batch'. The use of 'OPT_SET_INT' in these options is identical to 'OPT_BOOL', but 'OPT_BOOL' provides slightly simpler syntax.

---
 builtin/mktree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index 9a22d4e2773..8b19d440747 100644
@@ -162,8 +162,8 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 
 	const struct option option[] = {
 		OPT_BOOL('z', NULL, &nul_term_line, N_("input is NUL terminated")),
-		OPT_SET_INT( 0 , "missing", &allow_missing, N_("allow missing objects"), 1),
-		OPT_SET_INT( 0 , "batch", &is_batch_mode, N_("allow creation of more than one tree"), 1),
+		OPT_BOOL(0, "missing", &allow_missing, N_("allow missing objects")),
+		OPT_BOOL(0, "batch", &is_batch_mode, N_("allow creation of more than one tree")),
 		OPT_END()
 	};
 

gitgitgadget

From: Victoria Dye <[email protected]>

Rename the type for better readability, clearly specifying "entry" (instead of the "ent" abbreviation) and separating "tree" from "entry".

---
 builtin/mktree.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

index 8b19d440747..c02feb06aff 100644
@@ -12,7 +12,7 @@
 #include "parse-options.h"
 #include "object-store-ll.h"
 
-static struct treeent {
+static struct tree_entry {
 	unsigned mode;
 	struct object_id oid;
 	int len;

@@ -22,7 +22,7 @@ static int alloc, used;
 
 static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
 {
-	struct treeent *ent;
+	struct tree_entry *ent;
 	size_t len = strlen(path);
 	if (strchr(path, '/'))
 		die("path %s contains slash", path);

@@ -38,8 +38,8 @@ static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
 
 static int ent_compare(const void *a_, const void *b_)
 {
-	struct treeent *a = *(struct treeent **)a_;
-	struct treeent *b = *(struct treeent **)b_;
+	struct tree_entry *a = *(struct tree_entry **)a_;
+	struct tree_entry *b = *(struct tree_entry **)b_;
 	return base_name_compare(a->name, a->len, a->mode,
 				 b->name, b->len, b->mode);
 }

@@ -56,7 +56,7 @@ static void write_tree(struct object_id *oid)
 
 	strbuf_init(&buf, size);
 	for (i = 0; i < used; i++) {
-		struct treeent *ent = entries[i];
+		struct tree_entry *ent = entries[i];
 		strbuf_addf(&buf, "%o %s%c", ent->mode, ent->name, '\0');
 		strbuf_add(&buf, ent->oid.hash, the_hash_algo->rawsz);
 	}

gitgitgadget

From: Victoria Dye <[email protected]>

Replace the static 'struct tree_entry **entries' with a non-static 'struct tree_entry_array' instance. In later commits, we'll want to be able to create additional 'struct tree_entry_array' instances utilizing common functionality (create, push, clear, free). To avoid code duplication, create the 'struct tree_entry_array' type and add functions that perform those basic operations.

---
 builtin/mktree.c | 67 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 47 insertions(+), 20 deletions(-)

index c02feb06aff..15bd908702a 100644
@@ -12,15 +12,39 @@
 #include "parse-options.h"
 #include "object-store-ll.h"
 
-static struct tree_entry {
+struct tree_entry {
 	unsigned mode;
 	struct object_id oid;
 	int len;
 	char name[FLEX_ARRAY];
-} **entries;
-static int alloc, used;
+};
+
+struct tree_entry_array {
+	size_t nr, alloc;
+	struct tree_entry **entries;
+};
 
-static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
+static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entry *ent)
+{
+	ALLOC_GROW(arr->entries, arr->nr + 1, arr->alloc);
+	arr->entries[arr->nr++] = ent;
+}
+
+static void clear_tree_entry_array(struct tree_entry_array *arr)
+{
+	for (size_t i = 0; i < arr->nr; i++)
+		FREE_AND_NULL(arr->entries[i]);
+	arr->nr = 0;
+}
+
+static void release_tree_entry_array(struct tree_entry_array *arr)
+{
+	FREE_AND_NULL(arr->entries);
+	arr->nr = arr->alloc = 0;
+}
+
+static void append_to_tree(unsigned mode, struct object_id *oid, const char *path,
+			   struct tree_entry_array *arr)
 {
 	struct tree_entry *ent;
 	size_t len = strlen(path);

@@ -32,8 +56,8 @@ static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
 	ent->len = len;
 	oidcpy(&ent->oid, oid);
 
-	ALLOC_GROW(entries, used + 1, alloc);
-	entries[used++] = ent;
+	/* Append the update */
+	tree_entry_array_push(arr, ent);
 }
 
 static int ent_compare(const void *a_, const void *b_)

@@ -44,19 +68,18 @@ static int ent_compare(const void *a_, const void *b_)
 				 b->name, b->len, b->mode);
 }
 
-static void write_tree(struct object_id *oid)
+static void write_tree(struct tree_entry_array *arr, struct object_id *oid)
 {
 	struct strbuf buf;
-	size_t size;
-	int i;
+	size_t size = 0;
 
-	QSORT(entries, used, ent_compare);
-	for (size = i = 0; i < used; i++)
-		size += 32 + entries[i]->len;
+	QSORT(arr->entries, arr->nr, ent_compare);
+	for (size_t i = 0; i < arr->nr; i++)
+		size += 32 + arr->entries[i]->len;
 
 	strbuf_init(&buf, size);
-	for (i = 0; i < used; i++) {
-		struct tree_entry *ent = entries[i];
+	for (size_t i = 0; i < arr->nr; i++) {
+		struct tree_entry *ent = arr->entries[i];
 		strbuf_addf(&buf, "%o %s%c", ent->mode, ent->name, '\0');
 		strbuf_add(&buf, ent->oid.hash, the_hash_algo->rawsz);
 	}

@@ -70,7 +93,8 @@ static const char *mktree_usage[] = {
 	NULL
 };
 
-static void mktree_line(char *buf, int nul_term_line, int allow_missing)
+static void mktree_line(char *buf, int nul_term_line, int allow_missing,
+			struct tree_entry_array *arr)
 {
 	char *ptr, *ntr;
 	const char *p;

@@ -146,7 +170,7 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)
 		}
 	}
 
-	append_to_tree(mode, &oid, path);
+	append_to_tree(mode, &oid, path, arr);
 	free(to_free);
 }
 

@@ -158,6 +182,7 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 	int allow_missing = 0;
 	int is_batch_mode = 0;
 	int got_eof = 0;
+	struct tree_entry_array arr = { 0 };
 	strbuf_getline_fn getline_fn;
 
 	const struct option option[] = {

@@ -182,9 +207,9 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 					break;
 				die("input format error: (blank line only valid in batch mode)");
 			}
-			mktree_line(sb.buf, nul_term_line, allow_missing);
+			mktree_line(sb.buf, nul_term_line, allow_missing, &arr);
 		}
-		if (is_batch_mode && got_eof && used < 1) {
+		if (is_batch_mode && got_eof && arr.nr < 1) {
 			/*
 			 * Execution gets here if the last tree entry is terminated with a
 			 * new-line.  The final new-line has been made optional to be

@@ -192,12 +217,14 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 			 */
 			; /* skip creating an empty tree */
 		} else {
-			write_tree(&oid);
+			write_tree(&arr, &oid);
 			puts(oid_to_hex(&oid));
 			fflush(stdout);
 		}
-		used=0; /* reset tree entry buffer for re-use in batch mode */
+		clear_tree_entry_array(&arr); /* reset tree entry buffer for re-use in batch mode */
 	}
+
+	release_tree_entry_array(&arr);
 	strbuf_release(&sb);
 	return 0;
 }

gitgitgadget

From: Victoria Dye <[email protected]>

Move 'read_index_info()' into a new header 'index-info.h' and generalize the function to call a provided callback for each parsed line. Update 'update-index.c' to use this generalized 'read_index_info()', adding the callback 'apply_index_info()' to verify the parsed line and update the index according to its contents.

The input parsing done by 'read_index_info()' is similar to, but more flexible than, the parsing done in 'mktree' by 'mktree_line()' (handling not only 'git ls-tree' output but also the outputs of 'git apply --index-info' and 'git ls-files --stage' outputs). To make 'mktree' more flexible, a later patch will replace mktree's custom parsing with 'read_index_info()'.

---
 Makefile                      |   1 +
 builtin/update-index.c        | 116 ++++++++--------------------------
 index-info.c                  |  91 ++++++++++++++++++++++++++
 index-info.h                  |  11 ++++
 t/t2107-update-index-basic.sh |  27 ++++++++
 5 files changed, 155 insertions(+), 91 deletions(-)
 create mode 100644 index-info.c
 create mode 100644 index-info.h

index 2f5f16847ae..db9604e59c3 100644
@@ -1037,6 +1037,7 @@ LIB_OBJS += hex.o
 LIB_OBJS += hex-ll.o
 LIB_OBJS += hook.o
 LIB_OBJS += ident.o
+LIB_OBJS += index-info.o
 LIB_OBJS += json-writer.o
 LIB_OBJS += kwset.o
 LIB_OBJS += levenshtein.o

new file mode 100644
index 00000000000..d650498325a
@@ -0,0 +1,11 @@
+#ifndef INDEX_INFO_H
+#define INDEX_INFO_H
+
+#include "hash.h"
+
+typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);
+
+/* Iterate over parsed index info from stdin */
+int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata);
+
+#endif /* INDEX_INFO_H */

index cc72ead79f3..29696ade0d0 100755
@@ -142,4 +142,31 @@ test_expect_success '--index-version' '
 	test_must_be_empty actual
 '
 
+test_expect_success '--index-info fails on malformed input' '
+	# empty line
+	echo "" |
+	test_must_fail git update-index --index-info 2>err &&
+	grep "malformed input line" err &&
+
+	# bad whitespace
+	printf "100644 $EMPTY_BLOB A" |
+	test_must_fail git update-index --index-info 2>err &&
+	grep "malformed input line" err &&
+
+	# invalid stage value
+	printf "100644 $EMPTY_BLOB 5\tA" |
+	test_must_fail git update-index --index-info 2>err &&
+	grep "malformed input line" err &&
+
+	# invalid OID length
+	printf "100755 abc123\tA" |
+	test_must_fail git update-index --index-info 2>err &&
+	grep "malformed input line" err &&
+
+	# bad quoting
+	printf "100644 $EMPTY_BLOB\t\"A" |
+	test_must_fail git update-index --index-info 2>err &&
+	grep "bad quoting of path name" err
+'
+
 test_done

gitgitgadget

From: Victoria Dye <[email protected]>

If the object type (e.g. "blob", "tree") is identified on a stdin line read by 'read_index_info()' (i.e. on lines formatted like the output of 'git ls-tree'), parse it into an 'enum object_type' and provide it to the 'read_index_info()' callback as an argument. If the type is not provided, pass 'OBJ_NONE' instead. If the object type is invalid, return an error.

The goal of this change is to allow for more thorough validation of the provided object type (e.g. against the provided mode) in 'mktree' once 'mktree_line' is replaced with 'read_index_info()'. Note, though, that this change also strengthens the validation done by 'update-index', since invalid type names now trigger an error.

---
 builtin/update-index.c        |  3 ++-
 index-info.c                  | 16 ++++++++++++----
 index-info.h                  |  3 ++-
 t/t2107-update-index-basic.sh |  5 +++++
 4 files changed, 21 insertions(+), 6 deletions(-)

index b1b334807f8..8882433b644 100644
@@ -510,7 +510,8 @@ static void update_one(const char *path)
 	report("add '%s'", path);
 }
 
-static int apply_index_info(unsigned int mode, struct object_id *oid, int stage,
+static int apply_index_info(unsigned int mode, struct object_id *oid,
+			    enum object_type obj_type UNUSED, int stage,
 			    const char *path_name, void *cbdata UNUSED)
 {
 	if (!verify_path(path_name, mode)) {

index 735cbf1f476..5d61e61e28f 100644
@@ -18,6 +18,7 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
 		char *ptr, *tab;
 		char *path_name;
 		struct object_id oid;
+		enum object_type obj_type = OBJ_NONE;
 		unsigned int mode;
 		unsigned long ul;
 		int stage;

@@ -56,18 +57,17 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
 
 		if (tab[-2] == ' ' && '0' <= tab[-1] && tab[-1] <= '3') {
 			stage = tab[-1] - '0';
-			ptr = tab + 1; /* point at the head of path */
+			path_name = tab + 1; /* point at the head of path */
 			tab = tab - 2; /* point at tail of sha1 */
 		} else {
 			stage = 0;
-			ptr = tab + 1; /* point at the head of path */
+			path_name = tab + 1; /* point at the head of path */
 		}
 
 		if (get_oid_hex(tab - hexsz, &oid) ||
 			tab[-(hexsz + 1)] != ' ')
 			goto bad_line;
 
-		path_name = ptr;
 		if (!nul_term_line && path_name[0] == '"') {
 			strbuf_reset(&uq);
 			if (unquote_c_style(&uq, path_name, NULL)) {

@@ -77,7 +77,15 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
 			path_name = uq.buf;
 		}
 
-		ret = fn(mode, &oid, stage, path_name, cbdata);
+		/* Get the type, if provided */
+		if (tab - hexsz - 1 > ptr + 1) {
+			if (*(tab - hexsz - 1) != ' ')
+				goto bad_line;
+			*(tab - hexsz - 1) = '\0';
+			obj_type = type_from_string(ptr + 1);
+		}
+
+		ret = fn(mode, &oid, obj_type, stage, path_name, cbdata);
 		if (ret) {
 			ret = -1;
 			break;

index 1884972021d..767cf304213 100644
@@ -2,8 +2,9 @@
 #define INDEX_INFO_H
 
 #include "hash.h"
+#include "object.h"
 
-typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);
+typedef int (*each_index_info_fn)(unsigned int, struct object_id *, enum object_type, int, const char *, void *);
 
 #define INDEX_INFO_EMPTY_LINE 1
 

index 29696ade0d0..9c19d24cd4a 100755
@@ -153,6 +153,11 @@ test_expect_success '--index-info fails on malformed input' '
 	test_must_fail git update-index --index-info 2>err &&
 	grep "malformed input line" err &&
 
+	# invalid type
+	printf "100644 bad $EMPTY_BLOB\tA" |
+	test_must_fail git update-index --index-info 2>err &&
+	grep "invalid object type" err &&
+
 	# invalid stage value
 	printf "100644 $EMPTY_BLOB 5\tA" |
 	test_must_fail git update-index --index-info 2>err &&

gitgitgadget

From: Victoria Dye <[email protected]>

Update 'read_index_info()' to return INDEX_INFO_EMPTY_LINE (value 1), rather than the default error code (value -1) when the function encounters an empty line in stdin. This grants the caller the flexibility to handle such scenarios differently than a typical error. In the case of 'update-index', we'll still exit with a "malformed input line" error. However, when 'read_index_info()' is used to process the input to 'mktree' in a later patch, the empty line return value will signal a new tree in --batch mode.

---
 builtin/update-index.c | 4 +++-
 index-info.c           | 5 +++++
 index-info.h           | 2 ++
 3 files changed, 10 insertions(+), 1 deletion(-)

index 77df380cb54..b1b334807f8 100644
@@ -788,7 +788,9 @@ static enum parse_opt_result stdin_cacheinfo_callback(
 		return error("option '%s' must be the last argument", opt->long_name);
 	allow_add = allow_replace = allow_remove = 1;
 	ret = read_index_info(*nul_term_line, apply_index_info, NULL);
-	if (ret)
+	if (ret == INDEX_INFO_EMPTY_LINE)
+		return error("malformed input line ''");
+	else if (ret < 0)
 		return -1;
 
 	return 0;

index 0b68e34c361..735cbf1f476 100644
@@ -22,6 +22,11 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
 		unsigned long ul;
 		int stage;
 
+		if (!buf.len) {
+			ret = INDEX_INFO_EMPTY_LINE;
+			break;
+		}
+
 		/* This reads lines formatted in one of three formats:
 		 *
 		 * (1) mode         SP sha1          TAB path

index d650498325a..1884972021d 100644
@@ -5,6 +5,8 @@
 
 typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);
 
+#define INDEX_INFO_EMPTY_LINE 1
+
 /* Iterate over parsed index info from stdin */
 int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata);
 

gitgitgadget

From: Victoria Dye <[email protected]>

Replace the custom input parsing of 'mktree' with 'read_index_info()', which handles not only the 'ls-tree' output format it already handles but also the other formats compatible with 'update-index'. This lends some consistency across the commands (avoiding the need for two similar implementations for input parsing) and adds flexibility to mktree.

Update 'Documentation/git-mktree.txt' to reflect the more permissive input format.

---
 Documentation/git-mktree.txt |  17 +++--
 builtin/mktree.c             | 139 ++++++++++++-----------------------
 t/t1010-mktree.sh            |  66 +++++++++++++++++
 3 files changed, 125 insertions(+), 97 deletions(-)

index 383f09dd333..507682ed23e 100644
@@ -3,7 +3,7 @@ git-mktree(1)
 
 NAME
 ----
-git-mktree - Build a tree-object from ls-tree formatted text
+git-mktree - Build a tree-object from formatted tree entries
 
 
 SYNOPSIS

@@ -13,15 +13,13 @@ SYNOPSIS
 
 DESCRIPTION
 -----------
-Reads standard input in non-recursive `ls-tree` output format, and creates
-a tree object.  The order of the tree entries is normalized by mktree so
-pre-sorting the input is not required.  The object name of the tree object
-built is written to the standard output.
+Reads entry information from stdin and creates a tree object from those entries.
+The object name of the tree object built is written to the standard output.
 
 OPTIONS
 -------
 -z::
-	Read the NUL-terminated `ls-tree -z` output instead.
+	Input lines are separated with NUL rather than LF.
 
 --missing::
 	Allow missing objects.  The default behaviour (without this option)

@@ -35,6 +33,13 @@ OPTIONS
 	optional.  Note - if the `-z` option is used, lines are terminated
 	with NUL.
 
+INPUT FORMAT
+------------
+Tree entries may be specified in any of the formats compatible with the
+`--index-info` option to linkgit:git-update-index[1]. The order of the tree
+entries is normalized by `mktree` so pre-sorting the input by path is not
+required.
+
 GIT
 ---
 Part of the linkgit:git[1] suite

gitgitgadget

From: Victoria Dye <[email protected]>

Add the '--literally' option to 'git mktree' to allow constructing a tree with invalid contents. For now, the only change this represents compared to the normal 'git mktree' behavior is no longer sorting the inputs; in later commits, deduplicaton and path validation will be added to the command and '--literally' will skip those as well.

Certain tests use 'git mktree' to intentionally generate corrupt trees. Update these tests to use '--literally' so that they continue functioning properly when additional input cleanup & validation is added to the base command. Note that, because 'mktree --literally' does not sort entries, some of the tests are updated to provide their inputs in tree order; otherwise, the test would fail with an "incorrect order" error instead of the error the test expects.

---
 Documentation/git-mktree.txt       |  9 ++++++-
 builtin/mktree.c                   | 36 +++++++++++++++++++++++----
 t/t1010-mktree.sh                  | 40 ++++++++++++++++++++++++++++++
 t/t1014-read-tree-confusing.sh     |  6 ++---
 t/t1450-fsck.sh                    |  4 +--
 t/t1601-index-bogus.sh             |  2 +-
 t/t1700-split-index.sh             |  6 ++---
 t/t7008-filter-branch-null-sha1.sh |  6 ++---
 t/t7417-submodule-path-url.sh      |  2 +-
 t/t7450-bad-git-dotfiles.sh        |  8 +++---
 10 files changed, 96 insertions(+), 23 deletions(-)

index 507682ed23e..fb07e40cef0 100644
@@ -9,7 +9,7 @@ git-mktree - Build a tree-object from formatted tree entries
 SYNOPSIS
 --------
 [verse]
-'git mktree' [-z] [--missing] [--batch]
+'git mktree' [-z] [--missing] [--literally] [--batch]
 
 DESCRIPTION
 -----------

@@ -27,6 +27,13 @@ OPTIONS
 	object.  This option has no effect on the treatment of gitlink entries
 	(aka "submodules") which are always allowed to be missing.
 
+--literally::
+	Create the tree from the tree entries provided to stdin in the order
+	they are provided without performing additional sorting, deduplication,
+	or path validation on them. This option is primarily useful for creating
+	invalid tree objects to use in tests of how Git deals with various forms
+	of tree corruption.
+
 --batch::
 	Allow building of more than one tree object before exiting.  Each
 	tree is separated by a single blank line. The final newline is

index 5530257252d..48019448c1f 100644
@@ -45,11 +45,11 @@ static void release_tree_entry_array(struct tree_entry_array *arr)
 }
 
 static void append_to_tree(unsigned mode, struct object_id *oid, const char *path,
-			   struct tree_entry_array *arr)
+			   struct tree_entry_array *arr, int literally)
 {
 	struct tree_entry *ent;
 	size_t len = strlen(path);
-	if (strchr(path, '/'))
+	if (!literally && strchr(path, '/'))
 		die("path %s contains slash", path);
 
 	FLEX_ALLOC_MEM(ent, name, path, len);

@@ -89,14 +89,35 @@ static void write_tree(struct tree_entry_array *arr, struct object_id *oid)
 	strbuf_release(&buf);
 }
 
+static void write_tree_literally(struct tree_entry_array *arr,
+				 struct object_id *oid)
+{
+	struct strbuf buf;
+	size_t size = 0;
+
+	for (size_t i = 0; i < arr->nr; i++)
+		size += 32 + arr->entries[i]->len;
+
+	strbuf_init(&buf, size);
+	for (size_t i = 0; i < arr->nr; i++) {
+		struct tree_entry *ent = arr->entries[i];
+		strbuf_addf(&buf, "%o %s%c", ent->mode, ent->name, '\0');
+		strbuf_add(&buf, ent->oid.hash, the_hash_algo->rawsz);
+	}
+
+	write_object_file(buf.buf, buf.len, OBJ_TREE, oid);
+	strbuf_release(&buf);
+}
+
 static const char *mktree_usage[] = {
-	"git mktree [-z] [--missing] [--batch]",
+	"git mktree [-z] [--missing] [--literally] [--batch]",
 	NULL
 };
 
 struct mktree_line_data {
 	struct tree_entry_array *arr;
 	int allow_missing;
+	int literally;
 };
 
 static int mktree_line(unsigned int mode, struct object_id *oid,

@@ -136,7 +157,7 @@ static int mktree_line(unsigned int mode, struct object_id *oid,
 		    path, oid_to_hex(oid), type_name(parsed_obj_type), type_name(mode_type));
 	}
 
-	append_to_tree(mode, oid, path, data->arr);
+	append_to_tree(mode, oid, path, data->arr, data->literally);
 	return 0;
 }
 

@@ -152,6 +173,8 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 	const struct option option[] = {
 		OPT_BOOL('z', NULL, &nul_term_line, N_("input is NUL terminated")),
 		OPT_BOOL(0, "missing", &mktree_line_data.allow_missing, N_("allow missing objects")),
+		OPT_BOOL(0, "literally", &mktree_line_data.literally,
+			 N_("do not sort, deduplicate, or validate paths of tree entries")),
 		OPT_BOOL(0, "batch", &is_batch_mode, N_("allow creation of more than one tree")),
 		OPT_END()
 	};

@@ -175,7 +198,10 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 			 */
 			; /* skip creating an empty tree */
 		} else {
-			write_tree(&arr, &oid);
+			if (mktree_line_data.literally)
+				write_tree_literally(&arr, &oid);
+			else
+				write_tree(&arr, &oid);
 			puts(oid_to_hex(&oid));
 			fflush(stdout);
 		}

index 9b2ab0c97ad..e0687cb529f 100755
@@ -133,4 +133,44 @@ test_expect_success 'mktree fails on mode mismatch' '
 	grep "object $tree_oid is a tree but specified type was (blob)" err
 '
 
+test_expect_success '--literally can create invalid trees' '
+	tree_oid="$(cat tree)" &&
+	blob_oid="$(git rev-parse ${tree_oid}:one)" &&
+
+	# duplicate entries
+	{
+		printf "040000 tree $tree_oid\tmy-tree\n" &&
+		printf "100644 blob $blob_oid\ttest-file\n" &&
+		printf "100755 blob $blob_oid\ttest-file\n"
+	} | git mktree --literally >tree.bad &&
+	git cat-file tree $(cat tree.bad) >top.bad &&
+	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
+	grep "contains duplicate file entries" err &&
+
+	# disallowed path
+	{
+		printf "100644 blob $blob_oid\t.git\n"
+	} | git mktree --literally >tree.bad &&
+	git cat-file tree $(cat tree.bad) >top.bad &&
+	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
+	grep "contains ${SQ}.git${SQ}" err &&
+
+	# nested entry
+	{
+		printf "100644 blob $blob_oid\tdeeper/my-file\n"
+	} | git mktree --literally >tree.bad &&
+	git cat-file tree $(cat tree.bad) >top.bad &&
+	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
+	grep "contains full pathnames" err &&
+
+	# bad entry ordering
+	{
+		printf "100644 blob $blob_oid\tB\n" &&
+		printf "040000 tree $tree_oid\tA\n"
+	} | git mktree --literally >tree.bad &&
+	git cat-file tree $(cat tree.bad) >top.bad &&
+	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
+	grep "not properly sorted" err
+'
+
 test_done

index 8ea8d36818b..762eb789704 100755
@@ -30,13 +30,13 @@ while read path pretty; do
 	esac
 	test_expect_success "reject $pretty at end of path" '
 		printf "100644 blob %s\t%s" "$blob" "$path" >tree &&
-		bogus=$(git mktree <tree) &&
+		bogus=$(git mktree --literally <tree) &&
 		test_must_fail git read-tree $bogus
 	'
 
 	test_expect_success "reject $pretty as subtree" '
 		printf "040000 tree %s\t%s" "$tree" "$path" >tree &&
-		bogus=$(git mktree <tree) &&
+		bogus=$(git mktree --literally <tree) &&
 		test_must_fail git read-tree $bogus
 	'
 done <<-EOF

@@ -58,7 +58,7 @@ test_expect_success 'utf-8 paths allowed with core.protectHFS off' '
 	test_when_finished "git read-tree HEAD" &&
 	test_config core.protectHFS false &&
 	printf "100644 blob %s\t%s" "$blob" ".gi${u200c}t" >tree &&
-	ok=$(git mktree <tree) &&
+	ok=$(git mktree --literally <tree) &&
 	git read-tree $ok
 '
 

index 8a456b1142d..532d2770e88 100755
@@ -316,7 +316,7 @@ check_duplicate_names () {
 			*)  printf "100644 blob %s\t%s\n" $blob "$name" ;;
 			esac
 		done >badtree &&
-		badtree=$(git mktree <badtree) &&
+		badtree=$(git mktree --literally <badtree) &&
 		test_must_fail git fsck 2>out &&
 		test_grep "$badtree" out &&
 		test_grep "error in tree .*contains duplicate file entries" out

@@ -614,7 +614,7 @@ while read name path pretty; do
 			tree=$(git rev-parse HEAD^{tree}) &&
 			value=$(eval "echo \$$type") &&
 			printf "$mode $type %s\t%s" "$value" "$path" >bad &&
-			bad_tree=$(git mktree <bad) &&
+			bad_tree=$(git mktree --literally <bad) &&
 			git fsck 2>out &&
 			test_grep "warning.*tree $bad_tree" out
 		)'

index 4171f1e1410..54e8ae038b7 100755
@@ -4,7 +4,7 @@ test_description='test handling of bogus index entries'
 . ./test-lib.sh
 
 test_expect_success 'create tree with null sha1' '
-	tree=$(printf "160000 commit $ZERO_OID\\tbroken\\n" | git mktree)
+	tree=$(printf "160000 commit $ZERO_OID\\tbroken\\n" | git mktree --literally)
 '
 
 test_expect_success 'read-tree refuses to read null sha1' '

index ac4a5b2734c..97b58aa3cca 100755
@@ -478,12 +478,12 @@ test_expect_success 'writing split index with null sha1 does not write cache tre
 	git config splitIndex.maxPercentChange 0 &&
 	git commit -m "commit" &&
 	{
-		git ls-tree HEAD &&
-		printf "160000 commit $ZERO_OID\\tbroken\\n"
+		printf "160000 commit $ZERO_OID\\tbroken\\n" &&
+		git ls-tree HEAD
 	} >broken-tree &&
 	echo "add broken entry" >msg &&
 
-	tree=$(git mktree <broken-tree) &&
+	tree=$(git mktree --literally <broken-tree) &&
 	test_tick &&
 	commit=$(git commit-tree $tree -p HEAD <msg) &&
 	git update-ref HEAD "$commit" &&

index 93fbc92b8db..a1b4c295c01 100755
@@ -12,12 +12,12 @@ test_expect_success 'setup: base commits' '
 
 test_expect_success 'setup: a commit with a bogus null sha1 in the tree' '
 	{
-		git ls-tree HEAD &&
-		printf "160000 commit $ZERO_OID\\tbroken\\n"
+		printf "160000 commit $ZERO_OID\\tbroken\\n" &&
+		git ls-tree HEAD
 	} >broken-tree &&
 	echo "add broken entry" >msg &&
 
-	tree=$(git mktree <broken-tree) &&
+	tree=$(git mktree --literally <broken-tree) &&
 	test_tick &&
 	commit=$(git commit-tree $tree -p HEAD <msg) &&
 	git update-ref HEAD "$commit"

index dbbb3853dc0..5d3c98e99a7 100755
@@ -42,7 +42,7 @@ test_expect_success MINGW 'submodule paths disallows trailing spaces' '
 	tree=$(git -C super write-tree) &&
 	git -C super ls-tree $tree >tree &&
 	sed "s/sub/sub /" <tree >tree.new &&
-	tree=$(git -C super mktree <tree.new) &&
+	tree=$(git -C super mktree --literally <tree.new) &&
 	commit=$(echo with space | git -C super commit-tree $tree) &&
 	git -C super update-ref refs/heads/main $commit &&
 

index 4a9c22c9e2b..de2d45d2244 100755
@@ -203,11 +203,11 @@ check_dotx_symlink () {
 			content=$(git hash-object -w ../.gitmodules) &&
 			target=$(printf "$tricky" | git hash-object -w --stdin) &&
 			{
-				printf "100644 blob $content\t$tricky\n" &&
-				printf "120000 blob $target\t$path\n"
+				printf "120000 blob $target\t$path\n" &&
+				printf "100644 blob $content\t$tricky\n"
 			} >bad-tree
 		) &&
-		tree=$(git -C $dir mktree <$dir/bad-tree)
+		tree=$(git -C $dir mktree --literally <$dir/bad-tree)
 	'
 
 	test_expect_success "fsck detects symlinked $name ($type)" '

@@ -261,7 +261,7 @@ test_expect_success 'fsck detects non-blob .gitmodules' '
 		cp ../.gitmodules subdir/file &&
 		git add subdir/file &&
 		git commit -m ok &&
-		git ls-tree HEAD | sed s/subdir/.gitmodules/ | git mktree &&
+		git ls-tree HEAD | sed s/subdir/.gitmodules/ | git mktree --literally &&
 
 		test_must_fail git fsck 2>output &&
 		test_grep gitmodulesBlob output

gitgitgadget

From: Victoria Dye <[email protected]>

Use 'verify_path' to validate the paths provided as tree entries, ensuring we do not create entries with paths not allowed in trees (e.g., .git). Also, remove trailing slashes on directories before validating, allowing users to provide 'folder-name/' as the path for a tree object entry.

---
 builtin/mktree.c  | 20 +++++++++++++++++---
 t/t1010-mktree.sh | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+), 3 deletions(-)

index 48019448c1f..29e9dc6ce69 100644
@@ -8,6 +8,7 @@
 #include "hex.h"
 #include "index-info.h"
 #include "quote.h"
+#include "read-cache-ll.h"
 #include "strbuf.h"
 #include "tree.h"
 #include "parse-options.h"

@@ -49,10 +50,23 @@ static void append_to_tree(unsigned mode, struct object_id *oid, const char *pat
 {
 	struct tree_entry *ent;
 	size_t len = strlen(path);
-	if (!literally && strchr(path, '/'))
-		die("path %s contains slash", path);
 
-	FLEX_ALLOC_MEM(ent, name, path, len);
+	if (literally) {
+		FLEX_ALLOC_MEM(ent, name, path, len);
+	} else {
+		/* Normalize and validate entry path */
+		if (S_ISDIR(mode)) {
+			while(len > 0 && is_dir_sep(path[len - 1]))
+				len--;
+		}
+		FLEX_ALLOC_MEM(ent, name, path, len);
+
+		if (!verify_path(ent->name, mode))
+			die(_("invalid path '%s'"), path);
+		if (strchr(ent->name, '/'))
+			die("path %s contains slash", path);
+	}
+
 	ent->mode = mode;
 	ent->len = len;
 	oidcpy(&ent->oid, oid);

index e0687cb529f..e0263cb2bf8 100755
@@ -173,4 +173,37 @@ test_expect_success '--literally can create invalid trees' '
 	grep "not properly sorted" err
 '
 
+test_expect_success 'mktree validates path' '
+	tree_oid="$(cat tree)" &&
+	blob_oid="$(git rev-parse $tree_oid:a/one)" &&
+	head_oid="$(git rev-parse HEAD)" &&
+
+	# Valid: tree with or without trailing slash, blob without trailing slash
+	{
+		printf "040000 tree $tree_oid\tfolder1/\n" &&
+		printf "040000 tree $tree_oid\tfolder2\n" &&
+		printf "100644 blob $blob_oid\tfile.txt\n"
+	} | git mktree >actual &&
+
+	# Invalid: blob with trailing slash
+	printf "100644 blob $blob_oid\ttest/" |
+	test_must_fail git mktree 2>err &&
+	grep "invalid path ${SQ}test/${SQ}" err &&
+
+	# Invalid: dotdot
+	printf "040000 tree $tree_oid\t../" |
+	test_must_fail git mktree 2>err &&
+	grep "invalid path ${SQ}../${SQ}" err &&
+
+	# Invalid: dot
+	printf "040000 tree $tree_oid\t." |
+	test_must_fail git mktree 2>err &&
+	grep "invalid path ${SQ}.${SQ}" err &&
+
+	# Invalid: .git
+	printf "040000 tree $tree_oid\t.git/" |
+	test_must_fail git mktree 2>err &&
+	grep "invalid path ${SQ}.git/${SQ}" err
+'
+
 test_done

gitgitgadget

From: Victoria Dye <[email protected]>

If multiple tree entries with the same name are provided as input to 'mktree', only write the last one to the tree. Entries are considered duplicates if they have identical names (*not* considering mode); if a blob and a tree with the same name are provided, only the last one will be written to the tree. A tree with duplicate entries is invalid (per 'git fsck'), so that condition should be avoided wherever possible.

---
 Documentation/git-mktree.txt |  8 ++++---
 builtin/mktree.c             | 45 ++++++++++++++++++++++++++++++++----
 t/t1010-mktree.sh            | 36 +++++++++++++++++++++++++++--
 3 files changed, 80 insertions(+), 9 deletions(-)

index fb07e40cef0..afbc846d077 100644
@@ -43,9 +43,11 @@ OPTIONS
 INPUT FORMAT
 ------------
 Tree entries may be specified in any of the formats compatible with the
-`--index-info` option to linkgit:git-update-index[1]. The order of the tree
-entries is normalized by `mktree` so pre-sorting the input by path is not
-required.
+`--index-info` option to linkgit:git-update-index[1].
+
+The order of the tree entries is normalized by `mktree` so pre-sorting the input
+by path is not required. Multiple entries provided with the same path are
+deduplicated, with only the last one specified added to the tree.
 
 GIT
 ---

index e0263cb2bf8..956692347f0 100755
@@ -6,11 +6,16 @@ TEST_PASSES_SANITIZE_LEAK=true
 . ./test-lib.sh
 
 test_expect_success setup '
-	for d in a a- a0
+	for d in folder folder- folder0
 	do
 		mkdir "$d" && echo "$d/one" >"$d/one" &&
 		git add "$d" || return 1
 	done &&
+	for f in before folder.txt later
+	do
+		echo "$f" >"$f" &&
+		git add "$f" || return 1
+	done &&
 	echo zero >one &&
 	git update-index --add --info-only one &&
 	git write-tree --missing-ok >tree.missing &&

@@ -175,7 +180,7 @@ test_expect_success '--literally can create invalid trees' '
 
 test_expect_success 'mktree validates path' '
 	tree_oid="$(cat tree)" &&
-	blob_oid="$(git rev-parse $tree_oid:a/one)" &&
+	blob_oid="$(git rev-parse $tree_oid:folder.txt)" &&
 	head_oid="$(git rev-parse HEAD)" &&
 
 	# Valid: tree with or without trailing slash, blob without trailing slash

@@ -206,4 +211,31 @@ test_expect_success 'mktree validates path' '
 	grep "invalid path ${SQ}.git/${SQ}" err
 '
 
+test_expect_success 'mktree with duplicate entries' '
+	tree_oid=$(cat tree) &&
+	folder_oid=$(git rev-parse ${tree_oid}:folder) &&
+	before_oid=$(git rev-parse ${tree_oid}:before) &&
+	head_oid=$(git rev-parse HEAD) &&
+
+	{
+		printf "100755 blob $before_oid\ttest\n" &&
+		printf "040000 tree $folder_oid\ttest-\n" &&
+		printf "160000 commit $head_oid\ttest.txt\n" &&
+		printf "040000 tree $folder_oid\ttest\n" &&
+		printf "100644 blob $before_oid\ttest0\n" &&
+		printf "160000 commit $head_oid\ttest-\n"
+	} >top.dup &&
+	git mktree <top.dup >tree.actual &&
+
+	{
+		printf "160000 commit $head_oid\ttest-\n" &&
+		printf "160000 commit $head_oid\ttest.txt\n" &&
+		printf "040000 tree $folder_oid\ttest\n" &&
+		printf "100644 blob $before_oid\ttest0\n"
+	} >expect &&
+	git ls-tree $(cat tree.actual) >actual &&
+
+	test_cmp expect actual
+'
+
 test_done

gitgitgadget

From: Victoria Dye <[email protected]>

Rather than manually write out the contents of a tree object file, construct an in-memory sparse index from the provided tree entries and create the tree by writing out its corresponding cache tree.

This patch does not change the behavior of the 'mktree' command. However, constructing the tree this way will substantially simplify future extensions to the command's functionality, including handling deeper-than-toplevel tree entries and applying the provided entries to an existing tree.

---
 builtin/mktree.c | 74 +++++++++++++++++++++++++++++++++++-------------
 1 file changed, 55 insertions(+), 19 deletions(-)

index e9e2134136f..12f68187221 100644
@@ -4,6 +4,7 @@
  * Copyright (c) Junio C Hamano, 2006, 2009
  */
 #include "builtin.h"
+#include "cache-tree.h"
 #include "gettext.h"
 #include "hex.h"
 #include "index-info.h"

@@ -24,6 +25,11 @@ struct tree_entry {
 	char name[FLEX_ARRAY];
 };
 
+static inline size_t df_path_len(size_t pathlen, unsigned int mode)
+{
+	return S_ISDIR(mode) ? pathlen - 1 : pathlen;
+}
+
 struct tree_entry_array {
 	size_t nr, alloc;
 	struct tree_entry **entries;

@@ -57,17 +63,25 @@ static void append_to_tree(unsigned mode, struct object_id *oid, const char *pat
 	if (literally) {
 		FLEX_ALLOC_MEM(ent, name, path, len);
 	} else {
+		size_t len_to_copy = len;
+
 		/* Normalize and validate entry path */
 		if (S_ISDIR(mode)) {
-			while(len > 0 && is_dir_sep(path[len - 1]))
-				len--;
+			while(len_to_copy > 0 && is_dir_sep(path[len_to_copy - 1]))
+				len_to_copy--;
+			len = len_to_copy + 1; /* add space for trailing slash */
 		}
-		FLEX_ALLOC_MEM(ent, name, path, len);
+		ent = xcalloc(1, st_add3(sizeof(struct tree_entry), len, 1));
+		memcpy(ent->name, path, len_to_copy);
 
 		if (!verify_path(ent->name, mode))
 			die(_("invalid path '%s'"), path);
 		if (strchr(ent->name, '/'))
 			die("path %s contains slash", path);
+
+		/* Add trailing slash to dir */
+		if (S_ISDIR(mode))
+			ent->name[len - 1] = '/';
 	}
 
 	ent->mode = mode;

@@ -86,11 +100,14 @@ static int ent_compare(const void *a_, const void *b_, void *ctx)
 	struct tree_entry *b = *(struct tree_entry **)b_;
 	int ignore_mode = *((int *)ctx);
 
-	if (ignore_mode)
-		cmp = name_compare(a->name, a->len, b->name, b->len);
-	else
-		cmp = base_name_compare(a->name, a->len, a->mode,
-					b->name, b->len, b->mode);
+	size_t a_len = a->len, b_len = b->len;
+
+	if (ignore_mode) {
+		a_len = df_path_len(a_len, a->mode);
+		b_len = df_path_len(b_len, b->mode);
+	}
+
+	cmp = name_compare(a->name, a_len, b->name, b_len);
 	return cmp ? cmp : b->order - a->order;
 }
 

@@ -106,8 +123,8 @@ static void sort_and_dedup_tree_entry_array(struct tree_entry_array *arr)
 	for (size_t i = 0; i < count; i++) {
 		struct tree_entry *curr = arr->entries[i];
 		if (prev &&
-		    !name_compare(prev->name, prev->len,
-				  curr->name, curr->len)) {
+		    !name_compare(prev->name, df_path_len(prev->len, prev->mode),
+				  curr->name, df_path_len(curr->len, curr->mode))) {
 			FREE_AND_NULL(curr);
 		} else {
 			arr->entries[arr->nr++] = curr;

@@ -120,24 +137,43 @@ static void sort_and_dedup_tree_entry_array(struct tree_entry_array *arr)
 	QSORT_S(arr->entries, arr->nr, ent_compare, &ignore_mode);
 }
 
+static int add_tree_entry_to_index(struct index_state *istate,
+				   struct tree_entry *ent)
+{
+	struct cache_entry *ce;
+	struct strbuf ce_name = STRBUF_INIT;
+	strbuf_add(&ce_name, ent->name, ent->len);
+
+	ce = make_cache_entry(istate, ent->mode, &ent->oid, ent->name, 0, 0);
+	if (!ce)
+		return error(_("make_cache_entry failed for path '%s'"), ent->name);
+
+	add_index_entry(istate, ce, ADD_CACHE_JUST_APPEND);
+	strbuf_release(&ce_name);
+	return 0;
+}
+
 static void write_tree(struct tree_entry_array *arr, struct object_id *oid)
 {
-	struct strbuf buf;
-	size_t size = 0;
+	struct index_state istate = INDEX_STATE_INIT(the_repository);
+	istate.sparse_index = 1;
 
 	sort_and_dedup_tree_entry_array(arr);
-	for (size_t i = 0; i < arr->nr; i++)
-		size += 32 + arr->entries[i]->len;
 
-	strbuf_init(&buf, size);
+	/* Construct an in-memory index from the provided entries */
 	for (size_t i = 0; i < arr->nr; i++) {
 		struct tree_entry *ent = arr->entries[i];
-		strbuf_addf(&buf, "%o %s%c", ent->mode, ent->name, '\0');
-		strbuf_add(&buf, ent->oid.hash, the_hash_algo->rawsz);
+
+		if (add_tree_entry_to_index(&istate, ent))
+			die(_("failed to add tree entry '%s'"), ent->name);
 	}
 
-	write_object_file(buf.buf, buf.len, OBJ_TREE, oid);
-	strbuf_release(&buf);
+	/* Write out new tree */
+	if (cache_tree_update(&istate, WRITE_TREE_SILENT | WRITE_TREE_MISSING_OK))
+		die(_("failed to write tree"));
+	oidcpy(oid, &istate.cache_tree->oid);
+
+	release_index(&istate);
 }
 
 static void write_tree_literally(struct tree_entry_array *arr,

gitgitgadget

From: Victoria Dye <[email protected]>

Create 'struct tree_entry_iterator' to manage iteration through a 'struct tree_entry_array'. Using an iterator allows for conditional iteration; this functionality will be necessary in later commits when performing parallel iteration through multiple sets of tree entries.

---
 builtin/mktree.c | 40 +++++++++++++++++++++++++++++++++++++---
 1 file changed, 37 insertions(+), 3 deletions(-)

index 12f68187221..bee359e9978 100644
@@ -137,6 +137,38 @@ static void sort_and_dedup_tree_entry_array(struct tree_entry_array *arr)
 	QSORT_S(arr->entries, arr->nr, ent_compare, &ignore_mode);
 }
 
+struct tree_entry_iterator {
+	struct tree_entry *current;
+
+	/* private */
+	struct {
+		struct tree_entry_array *arr;
+		size_t idx;
+	} priv;
+};
+
+static void init_tree_entry_iterator(struct tree_entry_iterator *iter,
+				     struct tree_entry_array *arr)
+{
+	iter->priv.arr = arr;
+	iter->priv.idx = 0;
+	iter->current = 0 < arr->nr ? arr->entries[0] : NULL;
+}
+
+/*
+ * Advance the tree entry iterator to the next entry in the array. If no entries
+ * remain, 'current' is set to NULL. Returns the previous 'current' value of the
+ * iterator.
+ */
+static struct tree_entry *advance_tree_entry_iterator(struct tree_entry_iterator *iter)
+{
+	struct tree_entry *prev = iter->current;
+	iter->current = (iter->priv.idx + 1) < iter->priv.arr->nr
+			? iter->priv.arr->entries[++iter->priv.idx]
+			: NULL;
+	return prev;
+}
+
 static int add_tree_entry_to_index(struct index_state *istate,
 				   struct tree_entry *ent)
 {

@@ -155,15 +187,17 @@ static int add_tree_entry_to_index(struct index_state *istate,
 
 static void write_tree(struct tree_entry_array *arr, struct object_id *oid)
 {
+	struct tree_entry_iterator iter = { NULL };
+	struct tree_entry *ent;
 	struct index_state istate = INDEX_STATE_INIT(the_repository);
 	istate.sparse_index = 1;
 
 	sort_and_dedup_tree_entry_array(arr);
 
-	/* Construct an in-memory index from the provided entries */
-	for (size_t i = 0; i < arr->nr; i++) {
-		struct tree_entry *ent = arr->entries[i];
+	init_tree_entry_iterator(&iter, arr);
 
+	/* Construct an in-memory index from the provided entries & base tree */
+	while ((ent = advance_tree_entry_iterator(&iter))) {
 		if (add_tree_entry_to_index(&istate, ent))
 			die(_("failed to add tree entry '%s'"), ent->name);
 	}

gitgitgadget

From: Victoria Dye <[email protected]>

Create a hashmap member of a 'struct tree_entry_array' that contains all of the (de-duplicated) provided tree entries, indexed by the hash of their path with *no* trailing slash. This hashmap will be used in a later commit to avoid adding a file to an existing tree that has the same path as a directory, or vice versa.

---
 builtin/mktree.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

index bee359e9978..09b3c5c6244 100644
@@ -16,6 +16,8 @@
 #include "object-store-ll.h"
 
 struct tree_entry {
+	struct hashmap_entry ent;
+
 	/* Internal */
 	size_t order;
 

@@ -33,8 +35,33 @@ static inline size_t df_path_len(size_t pathlen, unsigned int mode)
 struct tree_entry_array {
 	size_t nr, alloc;
 	struct tree_entry **entries;
+
+	struct hashmap df_name_hash;
 };
 
+static int df_name_hash_cmp(const void *cmp_data UNUSED,
+			    const struct hashmap_entry *eptr,
+			    const struct hashmap_entry *entry_or_key,
+			    const void *keydata UNUSED)
+{
+	const struct tree_entry *e1, *e2;
+	size_t e1_len, e2_len;
+
+	e1 = container_of(eptr, const struct tree_entry, ent);
+	e2 = container_of(entry_or_key, const struct tree_entry, ent);
+
+	e1_len = df_path_len(e1->len, e1->mode);
+	e2_len = df_path_len(e2->len, e2->mode);
+
+	return e1_len != e2_len ||
+	       name_compare(e1->name, e1_len, e2->name, e2_len);
+}
+
+static void init_tree_entry_array(struct tree_entry_array *arr)
+{
+	hashmap_init(&arr->df_name_hash, df_name_hash_cmp, NULL, 0);
+}
+
 static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entry *ent)
 {
 	ALLOC_GROW(arr->entries, arr->nr + 1, arr->alloc);

@@ -43,6 +70,7 @@ static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entr
 
 static void clear_tree_entry_array(struct tree_entry_array *arr)
 {
+	hashmap_clear(&arr->df_name_hash);
 	for (size_t i = 0; i < arr->nr; i++)
 		FREE_AND_NULL(arr->entries[i]);
 	arr->nr = 0;

@@ -50,6 +78,7 @@ static void clear_tree_entry_array(struct tree_entry_array *arr)
 
 static void release_tree_entry_array(struct tree_entry_array *arr)
 {
+	hashmap_clear(&arr->df_name_hash);
 	FREE_AND_NULL(arr->entries);
 	arr->nr = arr->alloc = 0;
 }

@@ -135,6 +164,14 @@ static void sort_and_dedup_tree_entry_array(struct tree_entry_array *arr)
 	/* Sort again to order the entries for tree insertion */
 	ignore_mode = 0;
 	QSORT_S(arr->entries, arr->nr, ent_compare, &ignore_mode);
+
+	/* Finally, initialize the directory-file conflict hash map */
+	for (size_t i = 0; i < count; i++) {
+		struct tree_entry *curr = arr->entries[i];
+		hashmap_entry_init(&curr->ent,
+				   memhash(curr->name, df_path_len(curr->len, curr->mode)));
+		hashmap_put(&arr->df_name_hash, &curr->ent);
+	}
 }
 
 struct tree_entry_iterator {

@@ -302,6 +339,8 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 
 	ac = parse_options(ac, av, prefix, option, mktree_usage, 0);
 
+	init_tree_entry_array(&arr);
+
 	do {
 		ret = read_index_info(nul_term_line, mktree_line, &mktree_line_data);
 		if (ret < 0)

gitgitgadget

From: Victoria Dye <[email protected]>

Allow users to specify a single "tree-ish" value as a positional argument. If provided, the contents of the given tree serve as the basis for the new tree (or trees, in --batch mode) created by 'mktree', on top of which all of the stdin-provided tree entries are applied.

At a high level, the entries are "applied" to a base tree by iterating through the base tree using 'read_tree' in parallel with iterating through the sorted & deduplicated stdin entries via their iterator. That is, for each call to the 'build_index_from_tree callback of 'read_tree':

* If the iterator entry precedes the base tree entry, add it to the in-core index, increment the iterator, and repeat.
* If the iterator entry has the same name as the base tree entry, add the iterator entry to the index, increment the iterator, and return from the callback to continue the 'read_tree' iteration.
* If the iterator entry follows the base tree entry, first check 'df_name_hash' to ensure we won't be adding an entry with the same name later (with a different mode). If there's no directory/file conflict, add the base tree entry to the index. In either case, return from the callback to continue the 'read_tree' iteration.

Finally, once 'read_tree' is complete, add the remaining entries in the iterator to the index and write out the index as a tree.

---
 Documentation/git-mktree.txt |   7 +-
 builtin/mktree.c             | 134 ++++++++++++++++++++++++++++++-----
 t/t1010-mktree.sh            |  36 ++++++++++
 3 files changed, 157 insertions(+), 20 deletions(-)

index afbc846d077..99abd3c31a6 100644
@@ -9,7 +9,7 @@ git-mktree - Build a tree-object from formatted tree entries
 SYNOPSIS
 --------
 [verse]
-'git mktree' [-z] [--missing] [--literally] [--batch]
+'git mktree' [-z] [--missing] [--literally] [--batch] [--] [<tree-ish>]
 
 DESCRIPTION
 -----------

@@ -40,6 +40,11 @@ OPTIONS
 	optional.  Note - if the `-z` option is used, lines are terminated
 	with NUL.
 
+<tree-ish>::
+	If provided, the tree entries provided in stdin are added to this tree
+	rather than a new empty one, replacing existing entries with identical
+	names. Not compatible with `--literally`.
+
 INPUT FORMAT
 ------------
 Tree entries may be specified in any of the formats compatible with the

index 956692347f0..ea5a011405e 100755
@@ -238,4 +238,40 @@ test_expect_success 'mktree with duplicate entries' '
 	test_cmp expect actual
 '
 
+test_expect_success 'mktree with base tree' '
+	tree_oid=$(cat tree) &&
+	folder_oid=$(git rev-parse ${tree_oid}:folder) &&
+	before_oid=$(git rev-parse ${tree_oid}:before) &&
+	head_oid=$(git rev-parse HEAD) &&
+
+	{
+		printf "040000 tree $folder_oid\ttest\n" &&
+		printf "100644 blob $before_oid\ttest.txt\n" &&
+		printf "040000 tree $folder_oid\ttest-\n" &&
+		printf "160000 commit $head_oid\ttest0\n"
+	} >top.base &&
+	git mktree <top.base >tree.base &&
+
+	{
+		printf "100755 blob $before_oid\tz\n" &&
+		printf "160000 commit $head_oid\ttest.xyz\n" &&
+		printf "040000 tree $folder_oid\ta\n" &&
+		printf "100644 blob $before_oid\ttest\n"
+	} >top.append &&
+	git mktree $(cat tree.base) <top.append >tree.actual &&
+
+	{
+		printf "040000 tree $folder_oid\ta\n" &&
+		printf "100644 blob $before_oid\ttest\n" &&
+		printf "040000 tree $folder_oid\ttest-\n" &&
+		printf "100644 blob $before_oid\ttest.txt\n" &&
+		printf "160000 commit $head_oid\ttest.xyz\n" &&
+		printf "160000 commit $head_oid\ttest0\n" &&
+		printf "100755 blob $before_oid\tz\n"
+	} >expect &&
+	git ls-tree $(cat tree.actual) >actual &&
+
+	test_cmp expect actual
+'
+
 test_done

gitgitgadget

From: Victoria Dye <[email protected]>

Update 'git mktree' to handle entries nested inside of directories (e.g. 'path/to/a/file.txt'). This functionality requires a series of changes:

* In 'sort_and_dedup_tree_entry_array()', remove entries inside of directories that come after them in input order.
* Also in 'sort_and_dedup_tree_entry_array()', mark directories that contain entries that come after them in input order (e.g., 'folder/' followed by 'folder/file.txt') as "need to expand".
* In 'add_tree_entry_to_index()', if a tree entry is marked as "need to expand", recurse into it with 'read_tree_at()' & 'build_index_from_tree'.
* In 'build_index_from_tree()', if a user-specified tree entry is contained within the current iterated entry, return 'READ_TREE_RECURSIVE' to recurse into the iterated tree.

---
 Documentation/git-mktree.txt |   5 ++
 builtin/mktree.c             | 101 ++++++++++++++++++++++++++++++---
 t/t1010-mktree.sh            | 107 +++++++++++++++++++++++++++++++++--
 3 files changed, 200 insertions(+), 13 deletions(-)

index 99abd3c31a6..db90fdcdc8f 100644
@@ -50,6 +50,11 @@ INPUT FORMAT
 Tree entries may be specified in any of the formats compatible with the
 `--index-info` option to linkgit:git-update-index[1].
 
+Entries may use full pathnames containing directory separators to specify
+entries nested within one or more directories. These entries are inserted into
+the appropriate tree in the base tree-ish if one exists. Otherwise, empty parent
+trees are created to contain the entries.
+
 The order of the tree entries is normalized by `mktree` so pre-sorting the input
 by path is not required. Multiple entries provided with the same path are
 deduplicated, with only the last one specified added to the tree.

gitgitgadget

From: Victoria Dye <[email protected]>

If tree entries are specified with a mode with value '0', remove them from the tree instead of adding/updating them. If the mode is '0', both the provided type string (if specified) and the object ID of the entry are ignored.

Note that entries with mode '0' are added to the 'struct tree_ent_array' with a trailing slash so that it's always treated like a directory. This is a bit of a hack to ensure that the removal supercedes any preceding entries with matching names, as well as any nested inside a directory matching its name.

---
 Documentation/git-mktree.txt |  4 +++
 builtin/mktree.c             | 64 ++++++++++++++++++++----------------
 t/t1010-mktree.sh            | 38 +++++++++++++++++++++
 3 files changed, 77 insertions(+), 29 deletions(-)

index db90fdcdc8f..a660438c67f 100644
@@ -55,6 +55,10 @@ entries nested within one or more directories. These entries are inserted into
 the appropriate tree in the base tree-ish if one exists. Otherwise, empty parent
 trees are created to contain the entries.
 
+An entry with a mode of "0" will remove an entry of the same name from the base
+tree-ish. If no tree-ish argument is given, or the entry does not exist in that
+tree, the entry is ignored.
+
 The order of the tree entries is normalized by `mktree` so pre-sorting the input
 by path is not required. Multiple entries provided with the same path are
 deduplicated, with only the last one specified added to the tree.

index 1d6365141fc..7cb88e32d4f 100755
@@ -373,4 +373,42 @@ test_expect_success 'mktree fails on directory-file conflict' '
 	grep "You have both folder/one and folder/one/deeper/deep" err
 '
 
+test_expect_success 'mktree with remove entries' '
+	tree_oid="$(cat tree)" &&
+	blob_oid="$(git rev-parse $tree_oid:folder.txt)" &&
+
+	{
+		printf "100644 blob $blob_oid\ttest/deeper/deep.txt\n" &&
+		printf "100644 blob $blob_oid\ttest.txt\n" &&
+		printf "100644 blob $blob_oid\texample\n" &&
+		printf "100644 blob $blob_oid\texample.a/file\n" &&
+		printf "100644 blob $blob_oid\texample.txt\n" &&
+		printf "040000 tree $tree_oid\tfolder\n" &&
+		printf "0 $ZERO_OID\tfolder\n" &&
+		printf "0 $ZERO_OID\tmissing\n"
+	} | git mktree >tree.base &&
+
+	{
+		printf "0 $ZERO_OID\texample.txt\n" &&
+		printf "0 $ZERO_OID\ttest/deeper\n"
+	} | git mktree $(cat tree.base) >tree.actual &&
+
+	{
+		printf "100644 blob $blob_oid\texample\n" &&
+		printf "100644 blob $blob_oid\texample.a/file\n" &&
+		printf "100644 blob $blob_oid\ttest.txt\n"
+	} >expect &&
+	git ls-tree -r $(cat tree.actual) >actual &&
+
+	test_cmp expect actual
+'
+
+test_expect_success 'type and oid not checked if entry mode is 0' '
+	# type and oid do not match
+	printf "0 commit $EMPTY_TREE\tfolder.txt\n" |
+	git mktree >tree.actual &&
+
+	test "$(cat tree.actual)" = $EMPTY_TREE
+'
+
 test_done

gitgitgadget

"git apply --index-info"?

That is a blast from the past. It no longer exists since 7a988699 (apply: get rid of --index-info in favor of --build-fake-ancestor, 2007-09-17).

As to the scriptability, supporting "ls-files -s" and "ls-tree -r" output as our input do help, but the third one is not natively emitted and it is very unlikely that there are third-party tools that give output in that format. After all these years, I suspect that it is sufficient to say

"update-index --index-info" and "mktree" both read information necessary to eventually build trees, but having two separate parsers is a maintenance burden, so we are massaging the code from the former to be reusable.

without mentioning where the old third format comes from.

Interesting. We could even introduce "# commented input" but that is a different story ;-).

I also wonder if we can flip it around and teach read_index_info() to (1) silently accept and do a callback when it recognises the input line is one of the supported formats, and (2) send any unrecognised line, not just an empty one, with "unrecognised" status code. That way, the caller can handle more than single kind of "special input line" more easily, perhaps?

Thanks.

My recollection is, when we do not know what to expect, we tend to use OBJ_ANY rather than OBJ_NONE as convention to signal that fact (e.g., object-name.c:peel_to_type()).

As long as the code path this series touches is internally consistent, using OBJ_NONE may not hurt but once they need to start interacting with existing code paths that use OBJ_ANY for that purpose, we may need to adjust one to match the other.

Nice.

Yay.

Nice.

		if (!data->allow_missing && !S_ISGITLINK(mode))
			die("...");

	if (S_ISGITILNK(mode)) {
		... anything goes ...
	} else if (oid_object_info_extended(...) < 0 &&
		   !data->allow_missing) {
        	... not found ...
	} else if (parsed_obj_type != mode_type) {
        	... found something different from what we expected ...
	}

Hmph, the end state of the the series as a whole may be good, but the above makes me wonder if we broke bisectability with the previous step 07/16 where we introduced type checks without touching any existing tests?

Makes sense.

Sensible.

Is that a good idea for a plumbing like this command? We would silently accept these after silently stripping the trailing slash?

040000 tree 82a33d5150d9316378ef1955a49f2a5bf21aaeb2 templates/
100644 blob 1f89ffab4c32bc02b5d955851401628a5b9a540e thread-utils.c/

The former _might_ count as "usability improvement", but if we are doing the same for the latter we might be going a bit too lenient.

Let's see what really happens in the code.

Thanks for getting rid of more global state, I really appreciate this.

Here is a way to do so, which I alluded to earlier. The original text is too specific to "update-index" in that it talked about "stuffing them into the index", which does not apply in the context of "mktree".

And then it made me realize that "ls-files -s" output has the stage information, which of course is needed for "update-index" to be able to recreate the index state from a textual dump, but "mktree" should reject if given a higher stage entry.

It seems that the code after applying all these 16 patches does not diagnose it as an error if you feed a non-zero stage. The callback starts like so.

static int mktree_line(unsigned int mode, struct object_id *oid,
enum object_type obj_type, int stage UNUSED, const char *path, void *cbdata)
{

I _think_ it should be made an error if the input has non-zero stage, which would be a sign that it was taken from "ls-files -s" (or even "ls-files -u"), out of which "git write-tree" will REFUSE to create a tree object. "mktree" should behave the same way, no?

In any case, here is the documentation split/refactor.

 Documentation/git-mktree.txt         |  4 +++-
 Documentation/git-update-index.txt   | 14 +-------------
 Documentation/index-info-formats.txt | 13 +++++++++++++
 3 files changed, 17 insertions(+), 14 deletions(-)

index a660438c67..fefaa83d29 100644
@@ -48,7 +48,9 @@ OPTIONS
 INPUT FORMAT
 ------------
 Tree entries may be specified in any of the formats compatible with the
-`--index-info` option to linkgit:git-update-index[1].
+`--index-info` option to linkgit:git-update-index[1].  That is:
+
+include::index-info-formats.txt[]
 
 Entries may use full pathnames containing directory separators to specify
 entries nested within one or more directories. These entries are inserted into

index 7128aed540..2287a5d4be 100644
@@ -280,19 +280,7 @@ USING --INDEX-INFO
 multiple entry definitions from the standard input, and designed
 specifically for scripts.  It can take inputs of three formats:
 
-    . mode SP type SP sha1          TAB path
-+
-This format is to stuff `git ls-tree` output into the index.
-
-    . mode         SP sha1 SP stage TAB path
-+
-This format is to put higher order stages into the
-index file and matches 'git ls-files --stage' output.
-
-    . mode         SP sha1          TAB path
-+
-This format is no longer produced by any Git command, but is
-and will continue to be supported by `update-index --index-info`.
+include::index-info-formats.txt[]
 
 To place a higher stage entry to the index, the path should
 first be removed by feeding a mode=0 entry for the path, and

new file mode 100644
index 0000000000..037ebd2432
@@ -0,0 +1,13 @@
+    . mode SP type SP sha1          TAB path
++
+This format is to use `git ls-tree` output.
+
+    . mode         SP sha1 SP stage TAB path
++
+This format allows higher order stages to appear and
+matches 'git ls-files --stage' output.
+
+    . mode         SP sha1          TAB path
++
+This format is no longer produced by any Git command, but is
+and will continue to be supported.

'git mktree' already does some cleaning of the inputs by sorting the entries, presumably so that a valid tree is created rather than one with ordering errors. Deduplication is also a cleanup of user inputs to ensure a valid tree is created, so to me it's a consistent extension to existing behavior. Conversely, rejecting the inputs and failing would be introducing an error scenario where none existed previously, which to me would be a bigger deviation.

One potential way to get the kind of functionality you're looking for, though, might be to combine something like '--literally' and a '--strict' that validates the tree before writing. Like I mentioned in the cover letter [1], I do plan to submit a follow-up series with '--strict' (it's just that this series is already pretty long and it would add 4-ish more patches).

[1] https://lore.kernel.org/git/[email protected]/

Practically, there are a couple of reasons that led me to wanting this behavior. One is that it allows using data structures with more rigid integrity checks (like the index & cache tree). The other is that, once the ability to add nested entries is introduced, the concept of a "duplicate" gets fuzzier and blocking them entirely could lead to inconsistencies and/or limited flexibility. If, for example a user wants to create a tree with a directory 'folder1/' with OID '0123456789012345678901234567890123456789', but update a blob 'folder1/file1' in it to OID '0987654321098765432109876543210987654321', the latter is technically a "duplicate" but rejecting it would avoid being able to create the tree without first expanding 'folder1/'with something like 'ls-tree', replacing the appropriate entry, then calling 'mktree'.

The trailing slashes are only ignored on tree entries (with mode 040000), so the latter case would not be allowed (and triggers a 'die()' as it would today).

Ah, sorry about that, thanks for catching it.

It might be a bit niche, but 'git ls-files -s --sparse' does print directories with a trailing slash, and in a format that is otherwise accepted by the command after switching to 'read_index_info' for input parsing.

OK.

Presumably the same way how you remove entries with "update-index --index-info"? I.e. mode=0 entry in the input would serve as a signal to remove the path?

That works for me. I'm not attached to the naming convention I used and your justification for changing it in [1] is reasonable.

[1] https://lore.kernel.org/git/ZmltDQ5SlVvrEDGP@tanuki/

I do see how it's confusing. I was attempting to mimic the various array/stack "pop" methods throughout the codebase (which return the "popped" value while moving the stack pointer), but that doesn't really work here with an iterator.

The only real benefit of this was that it simplified a loop somewhere later on, but not by a ton. I'll drop the 'tree_entry *' return value from the method and access 'iter->current' directly where it's needed.

The idea of the iterator is to have callers only ever reference the 'current' value to avoid needing to deal with the array & current index directly; I find that it majorly simplifies the parallel iteration through the base tree and entry array in [2]. IOW, in a language with support for it, 'idx' would be private & 'current' would be public. So I would like to keep the 'current' value as the publicly-accessible way of interacting with the iterator (although, as mentioned above, I'm happy to drop it from the 'advance' method return value).

[2] https://lore.kernel.org/git/df0c50dfea3cb77e0070246efdf7a3f070b2ad97.1718130288.git.gitgitgadget@gmail.com/

To me, the positional '<tree-ish>' is more intuitive; it's reminiscent of 'read-tree' (but with '--empty' being the default, since there's no equivalent to the existing index to overwrite). I consider 'read-tree' relevant in this case because the updated 'mktree' allows a users to create trees like:

$ git read-tree <tree-ish>
$ git update-index <entries
$ git write-tree

without the intermediate on-disk index. Conversely, there isn't really an equivalent option to base the name on ('--base' is a bit overloaded, as it typically refers to a merge/diff base), and I'd like to avoid adding more potentially-confusing names to the overall Git UX if I can help it (even if this is a plumbing command).

However, looking at other command documentation, I should at least drop '[--]' from the usage string. While that is a separator used to signify "end of options" using 'parse_options()', it's typically only included in the usage string to separate different sets of positional arguments (e.g. revisions from pathspecs).

In patch 16 [1], entries with mode "0" are removed from the tree (similar to 'update-index').

[1] https://lore.kernel.org/git/a90d6d0c943283e9e7bd181cd6e9bb6d4572aaeb.1718130288.git.gitgitgadget@gmail.com/

This is an interesting idea. The simplest way to do this would probably to have 'bad_line' stop printing the "malformed input line" error and instead return INDEX_INFO_UNRECOGNIZED_LINE, and pass in a strbuf so that the "malformed" line is available to the caller.

That seems simple enough, so I'll include it in V2; I can always revert back to INDEX_INFO_EMPTY_LINE if the generalized approach doesn't work out for some reason.

The goal of this series is to make 'git mktree' a much more flexible and powerful tool for constructing arbitrary trees in memory without the use of an index or worktree. The main additions are:

* Using an optional "base tree" to add or replace entries in an existing tree rather than creating a new one from scratch.
* Building off of this, having entries with mode "0" indicate "remove this entry, if it exists, from the tree"
* Handling tree entries inside of subtrees (e.g., folder1/my-file.txt)

It also introduces some quality-of-life updates:

* Using the same input parsing as 'update-index' to allow a wider variety of tree entry formats.
* Adding deduplication of input entries & more thorough validation of inputs (with an option to disable both - plus input sorting - if desired with '--literally').

The implementation change underpinning the new features is completely revamping how the tree is constructed in memory. Instead of writing a single tree object into a strbuf and hashing it into the object database, we construct an in-core sparse index and write out the root tree, as well as any new subtrees, using the cache tree infrastructure.

The series is organized as follows:

* Commits 1-3 contain miscellaneous small renames/refactors to make the code more readable & prepare for larger refactoring later.
* Commits 4-7 generalize the input parsing performed by 'read_index_info()' in 'update-index' and update 'mktree' to use it.
* Commit 8 removes the check on object existence & type from submodule entries.
* Commit 9 adds the '--literally' option to 'mktree'. Practically, this option allows tests that currently use 'mktree' to generate corrupt trees to continue functioning after we strengthen input validations.
* Commits 10 & 11 add input path validation & entry deduplication, respectively.
* Commit 12 replaces the strbuf-to-object tree creation with construction of an in-core index & writing out the cache tree.
* Commits 13-15 add the ability to add tree entries to an existing "base" tree. Takes 3 commits to do it because it requires a bit of finesse around directory/file deduplication and iterating over a tree with 'read_tree()' with a parallel iteration over the input tree entries.
* Commit 16 allows for deeper paths in the input.
* Commit 17 adds handling for mode '0' as "removal" entries.

I also plan to add a '--strict' option that runs 'fsck' checks on the new tree(s) before writing to the object database (similar to 'mkttag --strict'), but this series is pretty long as it is and that part can easily be separated out into its own series.

Changes since V1
================

* Renamed 'tree_entry_array' & 'tree_entry_iterator' functions to 'tree_entry_array' & 'tree_entry_iterator', respectively.
* Removed the return value from 'tree_entry_iterator_advance'.
* Added call to 'tree_entry_array_clear' in 'tree_entry_array_release', updated both methods to optionally free tree entries based on a 'free_entries' arg.
* Updated 'read_index_info()':
* Replaced INDEX_INFO_EMPTY_LINE with INDEX_INFO_UNRECOGNIZED_LINE which is returned when any "malformed" line is found, setting an input strbuf to the line contents for the caller to deal with.
* Updated default object type value (when no type info is specified) to

     'OBJ_ANY' from 'OBJ_NONE'.

* Updated 'mktree' to 'die()' on malformed line with "input format error", rather than 'error()' with "malformed input line", to avoid unnecessarily changing the error message.
* Removed check for object existence & type when the entry type is a submodule, rearranged checks for readability.
* Replaced use of 'grep' with 'test_grep' in new/updated tests.
* Wrapped lines in documentation updates to 76 characters.
* Applied documentation refactor patch in [1].
* Dropped '[--]' from the 'mktree' usage string.

[1] https://lore.kernel.org/git/[email protected]/

Thanks!

* Victoria

Victoria Dye (17):
mktree: use OPT_BOOL
mktree: rename treeent to tree_entry
mktree: use non-static tree_entry array
update-index: generalize 'read_index_info' index-info.c: return unrecognized lines to caller index-info.c: parse object type in provided in read_index_info
mktree: use read_index_info to read stdin lines mktree.c: do not fail on mismatched submodule type
mktree: add a --literally option
mktree: validate paths more carefully
mktree: overwrite duplicate entries
mktree: create tree using an in-core index
mktree: use iterator struct to add tree entries to index
mktree: add directory-file conflict hashmap
mktree: optionally add to an existing tree
mktree: allow deeper paths in input
mktree: remove entries when mode is 0

 Documentation/git-mktree.txt         |  50 ++-
 Documentation/git-update-index.txt   |  16 +-
 Documentation/index-info-formats.txt |  13 +
 Makefile                             |   1 +
 builtin/mktree.c                     | 592 ++++++++++++++++++++++-----
 builtin/update-index.c               | 135 ++----
 index-info.c                         | 100 +++++
 index-info.h                         |  15 +
 t/t1010-mktree.sh                    | 350 +++++++++++++++-
 t/t1014-read-tree-confusing.sh       |   6 +-
 t/t1450-fsck.sh                      |   4 +-
 t/t1601-index-bogus.sh               |   2 +-
 t/t1700-split-index.sh               |   6 +-
 t/t2107-update-index-basic.sh        |  32 ++
 t/t7008-filter-branch-null-sha1.sh   |   6 +-
 t/t7417-submodule-path-url.sh        |   2 +-
 t/t7450-bad-git-dotfiles.sh          |   8 +-
 17 files changed, 1088 insertions(+), 250 deletions(-)
 create mode 100644 Documentation/index-info-formats.txt
 create mode 100644 index-info.c
 create mode 100644 index-info.h

base-commit: 8d94cfb54504f2ec9edc7ca3eb5c29a3dd3675ae
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1746%2Fvdye%2Fvdye%2Fmktree-recursive-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1746/vdye/vdye/mktree-recursive-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1746

Range-diff vs v1:

  1:  074dc98acc7 =  1:  074dc98acc7 mktree: use OPT_BOOL
  2:  4558f35e7bf =  2:  4558f35e7bf mktree: rename treeent to tree_entry
  3:  5ade145352f !  3:  d0d5523a32b mktree: use non-static tree_entry array
     @@ builtin/mktree.c
      +	size_t nr, alloc;
      +	struct tree_entry **entries;
      +};
     - 
     --static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
     ++
      +static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entry *ent)
      +{
      +	ALLOC_GROW(arr->entries, arr->nr + 1, arr->alloc);
      +	arr->entries[arr->nr++] = ent;
      +}
      +
     -+static void clear_tree_entry_array(struct tree_entry_array *arr)
     ++static void tree_entry_array_clear(struct tree_entry_array *arr, int free_entries)
      +{
     -+	for (size_t i = 0; i < arr->nr; i++)
     -+		FREE_AND_NULL(arr->entries[i]);
     ++	if (free_entries) {
     ++		for (size_t i = 0; i < arr->nr; i++)
     ++			FREE_AND_NULL(arr->entries[i]);
     ++	}
      +	arr->nr = 0;
      +}
     -+
     -+static void release_tree_entry_array(struct tree_entry_array *arr)
     + 
     +-static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
     ++static void tree_entry_array_release(struct tree_entry_array *arr, int free_entries)
      +{
     ++	tree_entry_array_clear(arr, free_entries);
      +	FREE_AND_NULL(arr->entries);
     -+	arr->nr = arr->alloc = 0;
     ++	arr->alloc = 0;
      +}
      +
      +static void append_to_tree(unsigned mode, struct object_id *oid, const char *path,
     @@ builtin/mktree.c: static void append_to_tree(unsigned mode, struct object_id *oi
       
      -	ALLOC_GROW(entries, used + 1, alloc);
      -	entries[used++] = ent;
     -+	/* Append the update */
      +	tree_entry_array_push(arr, ent);
       }
       
     @@ builtin/mktree.c: int cmd_mktree(int ac, const char **av, const char *prefix)
       			fflush(stdout);
       		}
      -		used=0; /* reset tree entry buffer for re-use in batch mode */
     -+		clear_tree_entry_array(&arr); /* reset tree entry buffer for re-use in batch mode */
     ++		tree_entry_array_clear(&arr, 1); /* reset tree entry buffer for re-use in batch mode */
       	}
      +
     -+	release_tree_entry_array(&arr);
     ++	tree_entry_array_release(&arr, 1);
       	strbuf_release(&sb);
       	return 0;
       }
  4:  9d0689e9c28 !  4:  f5473764236 update-index: generalize 'read_index_info'
     @@ Commit message
          callback 'apply_index_info()' to verify the parsed line and update the index
          according to its contents.
      
     -    The input parsing done by 'read_index_info()' is similar to, but more
     -    flexible than, the parsing done in 'mktree' by 'mktree_line()' (handling not
     -    only 'git ls-tree' output but also the outputs of 'git apply --index-info'
     -    and 'git ls-files --stage' outputs). To make 'mktree' more flexible, a later
     -    patch will replace mktree's custom parsing with 'read_index_info()'.
     +    Switching to using a callback to validate the parsed entry in 'update-index'
     +    results in a slight change to the error message indicating a file could not
     +    be removed from the index. The original implementation uses the raw, quoted
     +    pathname in the error message, whereas the callback (without access to the
     +    raw pathname) uses the unquoted value. However, this change makes the failed
     +    removal message consistent with all other error messages in the function,
     +    and that consistency is likely more beneficial than not to a user.
      
     +    The motivation for this change is to consolidate the already-similar input
     +    parsing logic in 'git update-index' and 'git mktree', avoiding code
     +    duplication and the associated maintenance burden. The input formats
     +    accepted by 'update-index' are a superset of those accepted by 'mktree', so
     +    in a later commit we can replace the input parsing of the latter with
     +    'read_index_info()' without breaking existing usage.
     +
     +    Co-authored-by: Junio C Hamano <[email protected]>
          Signed-off-by: Victoria Dye <[email protected]>
      
     + ## Documentation/git-update-index.txt ##
     +@@ Documentation/git-update-index.txt: USING --INDEX-INFO
     + 
     + `--index-info` is a more powerful mechanism that lets you feed
     + multiple entry definitions from the standard input, and designed
     +-specifically for scripts.  It can take inputs of three formats:
     ++specifically for scripts.  It can take inputs in the following formats:
     + 
     +-    . mode SP type SP sha1          TAB path
     +-+
     +-This format is to stuff `git ls-tree` output into the index.
     +-
     +-    . mode         SP sha1 SP stage TAB path
     +-+
     +-This format is to put higher order stages into the
     +-index file and matches 'git ls-files --stage' output.
     +-
     +-    . mode         SP sha1          TAB path
     +-+
     +-This format is no longer produced by any Git command, but is
     +-and will continue to be supported by `update-index --index-info`.
     ++include::index-info-formats.txt[]
     + 
     + To place a higher stage entry to the index, the path should
     + first be removed by feeding a mode=0 entry for the path, and
     +
     + ## Documentation/index-info-formats.txt (new) ##
     +@@
     ++    . mode SP type SP sha1          TAB path
     +++
     ++This format is to use `git ls-tree` output.
     ++
     ++    . mode         SP sha1 SP stage TAB path
     +++
     ++This format allows higher order stages to appear and
     ++matches 'git ls-files --stage' output.
     ++
     ++    . mode         SP sha1          TAB path
     +++
     ++This format is no longer produced by any Git command, but is
     ++and will continue to be supported.
     +
       ## Makefile ##
      @@ Makefile: LIB_OBJS += hex.o
       LIB_OBJS += hex-ll.o
     @@ builtin/update-index.c: static void update_one(const char *path)
       
       static const char * const update_index_usage[] = {
      @@ builtin/update-index.c: static enum parse_opt_result stdin_cacheinfo_callback(
     + 	struct parse_opt_ctx_t *ctx, const struct option *opt,
       	const char *arg, int unset)
       {
     - 	int *nul_term_line = opt->value;
     -+	int ret;
     +-	int *nul_term_line = opt->value;
     ++	int ret = 0;
       
       	BUG_ON_OPT_NEG(unset);
       	BUG_ON_OPT_ARG(arg);
     -@@ builtin/update-index.c: static enum parse_opt_result stdin_cacheinfo_callback(
     - 	if (ctx->argc != 1)
     - 		return error("option '%s' must be the last argument", opt->long_name);
     - 	allow_add = allow_replace = allow_remove = 1;
     + 
     +-	if (ctx->argc != 1)
     +-		return error("option '%s' must be the last argument", opt->long_name);
     +-	allow_add = allow_replace = allow_remove = 1;
      -	read_index_info(*nul_term_line);
     -+	ret = read_index_info(*nul_term_line, apply_index_info, NULL);
     -+	if (ret)
     -+		return -1;
     +-	return 0;
     ++	if (ctx->argc != 1) {
     ++		ret = error("option '%s' must be the last argument", opt->long_name);
     ++	} else {
     ++		int *nul_term_line = opt->value;
      +
     - 	return 0;
     ++		allow_add = allow_replace = allow_remove = 1;
     ++		ret = read_index_info(*nul_term_line, apply_index_info, NULL);
     ++		if (ret)
     ++			ret = -1;
     ++	}
     ++
     ++	return ret;
       }
       
     + static enum parse_opt_result stdin_callback(
      
       ## index-info.c (new) ##
      @@
     @@ index-info.c (new)
      +		continue;
      +
      +	bad_line:
     -+		ret = error("malformed input line '%s'", buf.buf);
     -+		break;
     ++		die("malformed input line '%s'", buf.buf);
      +	}
      +	strbuf_release(&buf);
      +	strbuf_release(&uq);
     @@ t/t2107-update-index-basic.sh: test_expect_success '--index-version' '
      +	# empty line
      +	echo "" |
      +	test_must_fail git update-index --index-info 2>err &&
     -+	grep "malformed input line" err &&
     ++	test_grep "malformed input line" err &&
      +
      +	# bad whitespace
      +	printf "100644 $EMPTY_BLOB A" |
      +	test_must_fail git update-index --index-info 2>err &&
     -+	grep "malformed input line" err &&
     ++	test_grep "malformed input line" err &&
      +
      +	# invalid stage value
      +	printf "100644 $EMPTY_BLOB 5\tA" |
      +	test_must_fail git update-index --index-info 2>err &&
     -+	grep "malformed input line" err &&
     ++	test_grep "malformed input line" err &&
      +
      +	# invalid OID length
      +	printf "100755 abc123\tA" |
      +	test_must_fail git update-index --index-info 2>err &&
     -+	grep "malformed input line" err &&
     ++	test_grep "malformed input line" err &&
      +
      +	# bad quoting
      +	printf "100644 $EMPTY_BLOB\t\"A" |
      +	test_must_fail git update-index --index-info 2>err &&
     -+	grep "bad quoting of path name" err
     ++	test_grep "bad quoting of path name" err
      +'
      +
       test_done

5: 7e3bcc16e23 ! 5: 4f4d54c8d07 index-info.c: identify empty input lines in read_index_info
@@ Metadata
Author: Victoria Dye <[email protected]>

## Commit message ##
- index-info.c: identify empty input lines in read_index_info
+ index-info.c: return unrecognized lines to caller

- Update 'read_index_info()' to return INDEX_INFO_EMPTY_LINE (value 1), rather
- than the default error code (value -1) when the function encounters an empty
- line in stdin. This grants the caller the flexibility to handle such
- scenarios differently than a typical error. In the case of 'update-index',
- we'll still exit with a "malformed input line" error. However, when
- 'read_index_info()' is used to process the input to 'mktree' in a later
- patch, the empty line return value will signal a new tree in --batch mode.
+ Update 'read_index_info()' to return INDEX_INFO_UNRECOGNIZED_LINE (value 1),
+ rather than die()-ing when the function encounters a line that cannot be
+ parsed according to one of the accepted formats. This grants the caller the
+ flexibility to fall back on custom handling for such lines rather than a
+ returning a catch-all error. In the case of 'update-index', we'll still exit
+ with a "malformed input line" error. However, when 'read_index_info()' is
+ used to process the input to 'mktree' in a later patch, an empty line return
+ value will signal a new tree in --batch mode.

## builtin/update-index.c ##
@@ builtin/update-index.c: static enum parse_opt_result stdin_cacheinfo_callback(
- return error("option '%s' must be the last argument", opt->long_name);
- allow_add = allow_replace = allow_remove = 1;
- ret = read_index_info(*nul_term_line, apply_index_info, NULL);
-- if (ret)
-+ if (ret == INDEX_INFO_EMPTY_LINE)
-+ return error("malformed input line ''");
-+ else if (ret < 0)
- return -1;
-
- return 0;
+ ret = error("option '%s' must be the last argument", opt->long_name);
+ } else {
+ int *nul_term_line = opt->value;
++ struct strbuf line = STRBUF_INIT;
+
+ allow_add = allow_replace = allow_remove = 1;
+- ret = read_index_info(*nul_term_line, apply_index_info, NULL);
+- if (ret)
++ ret = read_index_info(*nul_term_line, apply_index_info, NULL, &line);
++
++ if (ret == INDEX_INFO_UNRECOGNIZED_LINE)
++ ret = error("malformed input line '%s'", line.buf);
++ else if (ret)
+ ret = -1;
++ strbuf_release(&line);
+ }
+
+ return ret;

## index-info.c ##
+@@
+ #include "strbuf.h"
+ #include "quote.h"
+
+-int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata) ++int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
++ struct strbuf *line)
+ {
+ const int hexsz = the_hash_algo->hexsz;
+- struct strbuf buf = STRBUF_INIT;
+ struct strbuf uq = STRBUF_INIT;
+ strbuf_getline_fn getline_fn;
+ int ret = 0;
+
+ getline_fn = nul_term_line ? strbuf_getline_nul : strbuf_getline_lf;
+- while (getline_fn(&buf, stdin) != EOF) {
++ while (getline_fn(line, stdin) != EOF) {
+ char *ptr, *tab;
+ char *path_name;
+ struct object_id oid;
+@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
+ * index file and matches "git ls-files --stage" output.
+ */
+ errno = 0;
+- ul = strtoul(buf.buf, &ptr, 8);
+- if (ptr == buf.buf || *ptr != ' '
++ ul = strtoul(line->buf, &ptr, 8);
++ if (ptr == line->buf || *ptr != ' '
+ || errno || (unsigned int) ul != ul)
+ goto bad_line;
+ mode = ul;
@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
- unsigned long ul;
- int stage;
+ continue;

-+ if (!buf.len) {
-+ ret = INDEX_INFO_EMPTY_LINE;
-+ break;
-+ }
-+
- /* This reads lines formatted in one of three formats:
- *
- * (1) mode SP sha1 TAB path
+ bad_line:
+- die("malformed input line '%s'", buf.buf);
++ ret = INDEX_INFO_UNRECOGNIZED_LINE;
++ break;
+ }
+- strbuf_release(&buf);
+ strbuf_release(&uq);
++ if (!ret)
++ strbuf_reset(line);
+
+ return ret;
+ }

## index-info.h ##
@@

typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);

-+#define INDEX_INFO_EMPTY_LINE 1
++#define INDEX_INFO_UNRECOGNIZED_LINE 1
+
/* Iterate over parsed index info from stdin */
- int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata); +-int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata); ++int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
++ struct strbuf *line);

+ #endif /* INDEX_INFO_H */
6: f56eee0b48d ! 6: 472efcaf1dd index-info.c: parse object type in provided in read_index_info

     @@ Commit message
          by 'read_index_info()' (i.e. on lines formatted like the output of 'git
          ls-tree'), parse it into an 'enum object_type' and provide it to the
          'read_index_info()' callback as an argument. If the type is not provided,
     -    pass 'OBJ_NONE' instead. If the object type is invalid, return an error.
     +    pass 'OBJ_ANY' instead. If the object type is invalid, return an error.
      
          The goal of this change is to allow for more thorough validation of the
          provided object type (e.g. against the provided mode) in 'mktree' once
     @@ builtin/update-index.c: static void update_one(const char *path)
       	if (!verify_path(path_name, mode)) {
      
       ## index-info.c ##
     -@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
     +@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
       		char *ptr, *tab;
       		char *path_name;
       		struct object_id oid;
     -+		enum object_type obj_type = OBJ_NONE;
     ++		enum object_type obj_type = OBJ_ANY;
       		unsigned int mode;
       		unsigned long ul;
       		int stage;
     -@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
     +@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
       
       		if (tab[-2] == ' ' && '0' <= tab[-1] && tab[-1] <= '3') {
       			stage = tab[-1] - '0';
     @@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void
       		if (!nul_term_line && path_name[0] == '"') {
       			strbuf_reset(&uq);
       			if (unquote_c_style(&uq, path_name, NULL)) {
     -@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
     +@@ index-info.c: int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
       			path_name = uq.buf;
       		}
       
     @@ index-info.h
      -typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);
      +typedef int (*each_index_info_fn)(unsigned int, struct object_id *, enum object_type, int, const char *, void *);
       
     - #define INDEX_INFO_EMPTY_LINE 1
     + #define INDEX_INFO_UNRECOGNIZED_LINE 1
       
      
       ## t/t2107-update-index-basic.sh ##
      @@ t/t2107-update-index-basic.sh: test_expect_success '--index-info fails on malformed input' '
       	test_must_fail git update-index --index-info 2>err &&
     - 	grep "malformed input line" err &&
     + 	test_grep "malformed input line" err &&
       
      +	# invalid type
      +	printf "100644 bad $EMPTY_BLOB\tA" |
      +	test_must_fail git update-index --index-info 2>err &&
     -+	grep "invalid object type" err &&
     ++	test_grep "invalid object type" err &&
      +
       	# invalid stage value
       	printf "100644 $EMPTY_BLOB 5\tA" |
  7:  8d1e1eaa70b !  7:  9dc8e16a7fc mktree: use read_index_info to read stdin lines
     @@ Commit message
          across the commands (avoiding the need for two similar implementations for
          input parsing) and adds flexibility to mktree.
      
     +    It should be noted that, while the error messages are largely preserved in
     +    the refactor, one does change: "fatal: invalid quoting" is now "error: bad
     +    quoting of path name".
     +
          Update 'Documentation/git-mktree.txt' to reflect the more permissive input
     -    format.
     +    format, as well as make a note about rejecting stage values higher than 0.
      
     +    Helped-by: Junio C Hamano <[email protected]>
          Signed-off-by: Victoria Dye <[email protected]>
      
       ## Documentation/git-mktree.txt ##
     @@ Documentation/git-mktree.txt: SYNOPSIS
      -a tree object.  The order of the tree entries is normalized by mktree so
      -pre-sorting the input is not required.  The object name of the tree object
      -built is written to the standard output.
     -+Reads entry information from stdin and creates a tree object from those entries.
     -+The object name of the tree object built is written to the standard output.
     ++Reads entry information from stdin and creates a tree object from those
     ++entries. The object name of the tree object built is written to the standard
     ++output.
       
       OPTIONS
       -------
     @@ Documentation/git-mktree.txt: OPTIONS
      +INPUT FORMAT
      +------------
      +Tree entries may be specified in any of the formats compatible with the
     -+`--index-info` option to linkgit:git-update-index[1]. The order of the tree
     -+entries is normalized by `mktree` so pre-sorting the input by path is not
     -+required.
     ++`--index-info` option to linkgit:git-update-index[1]:
     ++
     ++include::index-info-formats.txt[]
     ++
     ++Note that if the `stage` of a tree entry is given, the value must be 0.
     ++Higher stages represent conflicted files in an index; this information
     ++cannot be represented in a tree object. The command will fail without
     ++writing the tree if a higher order stage is specified for any entry.
     ++
     ++The order of the tree entries is normalized by `mktree` so pre-sorting the
     ++input by path is not required.
      +
       GIT
       ---
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
      +};
      +
      +static int mktree_line(unsigned int mode, struct object_id *oid,
     -+		       enum object_type obj_type, int stage UNUSED,
     ++		       enum object_type obj_type, int stage,
      +		       const char *path, void *cbdata)
       {
      -	char *ptr, *ntr;
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
      -			die("invalid quoting");
      -		path = to_free = strbuf_detach(&p_uq, NULL);
      -	}
     -+	if (obj_type && mode_type != obj_type)
     -+		die("object type (%s) doesn't match mode type (%s)",
     -+		    type_name(obj_type), type_name(mode_type));
     ++	if (stage)
     ++		die(_("path '%s' is unmerged"), path);
       
      -	/*
      -	 * Object type is redundantly derivable three ways.
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
      -		die("entry '%s' object type (%s) doesn't match mode type (%s)",
      -			path, ptr, type_name(mode_type));
      -	}
     ++	if (obj_type != OBJ_ANY && mode_type != obj_type)
     ++		die("object type (%s) doesn't match mode type (%s)",
     ++		    type_name(obj_type), type_name(mode_type));
     ++
      +	oi.typep = &parsed_obj_type;
       
      -	/* Check the type of object identified by oid without fetching objects */
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
       				     OBJECT_INFO_QUICK |
       				     OBJECT_INFO_SKIP_FETCH_OBJECT) < 0)
      -		obj_type = -1;
     -+		parsed_obj_type = -1;
     - 
     +-
      -	if (obj_type < 0) {
      -		if (allow_missing) {
      -			; /* no problem - missing objects are presumed to be of the right type */
     -+	if (parsed_obj_type < 0) {
     -+		if (data->allow_missing || S_ISGITLINK(mode)) {
     -+			; /* no problem - missing objects & submodules are presumed to be of the right type */
     - 		} else {
     +-		} else {
      -			die("entry '%s' object %s is unavailable", path, oid_to_hex(&oid));
      -		}
      -	} else {
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
      -			 */
      -			die("entry '%s' object %s is a %s but specified type was (%s)",
      -				path, oid_to_hex(&oid), type_name(obj_type), type_name(mode_type));
     +-		}
     ++		parsed_obj_type = -1;
     ++
     ++	if (parsed_obj_type < 0) {
     ++		/*
     ++		 * There are two conditions where the object being missing
     ++		 * is acceptable:
     ++		 *
     ++		 * - We're explicitly allowing it with --missing.
     ++		 * - The object is a submodule, which we wouldn't expect to
     ++		 *   be in this repo anyway.
     ++		 *
     ++		 * If neither condition is met, die().
     ++		 */
     ++		if (!data->allow_missing && !S_ISGITLINK(mode))
      +			die("entry '%s' object %s is unavailable", path, oid_to_hex(oid));
     - 		}
     ++
      +	} else if (parsed_obj_type != mode_type) {
      +		/*
      +		 * The object exists but is of the wrong type.
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
       	struct tree_entry_array arr = { 0 };
      -	strbuf_getline_fn getline_fn;
      +	struct mktree_line_data mktree_line_data = { .arr = &arr };
     ++	struct strbuf line = STRBUF_INIT;
      +	int ret;
       
       	const struct option option[] = {
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
      -				break;
      -			}
      -			if (sb.buf[0] == '\0') {
     --				/* empty lines denote tree boundaries in batch mode */
     --				if (is_batch_mode)
     --					break;
     --				die("input format error: (blank line only valid in batch mode)");
     --			}
     --			mktree_line(sb.buf, nul_term_line, allow_missing, &arr);
     --		}
     --		if (is_batch_mode && got_eof && arr.nr < 1) {
      +
      +	do {
     -+		ret = read_index_info(nul_term_line, mktree_line, &mktree_line_data);
     ++		ret = read_index_info(nul_term_line, mktree_line, &mktree_line_data, &line);
      +		if (ret < 0)
      +			break;
      +
     -+		/* empty lines denote tree boundaries in batch mode */
     -+		if (ret > 0 && !is_batch_mode)
     -+			die("input format error: (blank line only valid in batch mode)");
     ++		if (ret == INDEX_INFO_UNRECOGNIZED_LINE) {
     ++			if (line.len)
     ++				die("input format error: %s", line.buf);
     ++			else if (!is_batch_mode)
     + 				/* empty lines denote tree boundaries in batch mode */
     +-				if (is_batch_mode)
     +-					break;
     + 				die("input format error: (blank line only valid in batch mode)");
     +-			}
     +-			mktree_line(sb.buf, nul_term_line, allow_missing, &arr);
     + 		}
     +-		if (is_batch_mode && got_eof && arr.nr < 1) {
      +
      +		if (is_batch_mode && !ret && arr.nr < 1) {
       			/*
     @@ builtin/mktree.c: static const char *mktree_usage[] = {
      @@ builtin/mktree.c: int cmd_mktree(int ac, const char **av, const char *prefix)
       			fflush(stdout);
       		}
     - 		clear_tree_entry_array(&arr); /* reset tree entry buffer for re-use in batch mode */
     + 		tree_entry_array_clear(&arr, 1); /* reset tree entry buffer for re-use in batch mode */
      -	}
      +	} while (ret > 0);
       
     - 	release_tree_entry_array(&arr);
     ++	strbuf_release(&line);
     + 	tree_entry_array_release(&arr, 1);
      -	strbuf_release(&sb);
      -	return 0;
      +	return !!ret;
     @@ t/t1010-mktree.sh: test_expect_success 'ls-tree output in wrong order given to m
      +	tree_oid="$(cat tree)" &&
      +	printf "160000 commit $tree_oid\tA" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "object $tree_oid is a tree but specified type was (commit)" err
     ++	test_grep "object $tree_oid is a tree but specified type was (commit)" err
      +'
      +
       test_expect_success 'mktree refuses to read ls-tree -r output (1)' '
     @@ t/t1010-mktree.sh: test_expect_success 'mktree refuses to read ls-tree -r output
      +	# empty line without --batch
      +	echo "" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "blank line only valid in batch mode" err &&
     ++	test_grep "blank line only valid in batch mode" err &&
      +
      +	# bad whitespace
      +	printf "100644 blob $EMPTY_BLOB A" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "malformed input line" err &&
     ++	test_grep "input format error" err &&
      +
      +	# invalid type
      +	printf "100644 bad $EMPTY_BLOB\tA" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "invalid object type" err &&
     ++	test_grep "invalid object type" err &&
      +
      +	# invalid OID length
      +	printf "100755 blob abc123\tA" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "malformed input line" err &&
     ++	test_grep "input format error" err &&
      +
      +	# bad quoting
      +	printf "100644 blob $EMPTY_BLOB\t\"A" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "bad quoting of path name" err
     ++	test_grep "bad quoting of path name" err
      +'
      +
      +test_expect_success 'mktree fails on mode mismatch' '
     @@ t/t1010-mktree.sh: test_expect_success 'mktree refuses to read ls-tree -r output
      +	# mode-type mismatch
      +	printf "100644 tree $tree_oid\tA" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "object type (tree) doesn${SQ}t match mode type (blob)" err &&
     ++	test_grep "object type (tree) doesn${SQ}t match mode type (blob)" err &&
      +
      +	# mode-object mismatch (no --missing)
      +	printf "100644 $tree_oid\tA" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "object $tree_oid is a tree but specified type was (blob)" err
     ++	test_grep "object $tree_oid is a tree but specified type was (blob)" err
      +'
      +
       test_done
  -:  ----------- >  8:  8a3264afd0c mktree.c: do not fail on mismatched submodule type
  8:  b497dc90687 !  9:  e640a385b3d mktree: add a --literally option
     @@ Documentation/git-mktree.txt: OPTIONS
       
      +--literally::
      +	Create the tree from the tree entries provided to stdin in the order
     -+	they are provided without performing additional sorting, deduplication,
     -+	or path validation on them. This option is primarily useful for creating
     -+	invalid tree objects to use in tests of how Git deals with various forms
     -+	of tree corruption.
     ++	they are provided without performing additional sorting,
     ++	deduplication, or path validation on them. This option is primarily
     ++	useful for creating invalid tree objects to use in tests of how Git
     ++	deals with various forms of tree corruption.
      +
       --batch::
       	Allow building of more than one tree object before exiting.  Each
       	tree is separated by a single blank line. The final newline is
      
       ## builtin/mktree.c ##
     -@@ builtin/mktree.c: static void release_tree_entry_array(struct tree_entry_array *arr)
     +@@ builtin/mktree.c: static void tree_entry_array_release(struct tree_entry_array *arr, int free_entr
       }
       
       static void append_to_tree(unsigned mode, struct object_id *oid, const char *path,
     @@ builtin/mktree.c: static void write_tree(struct tree_entry_array *arr, struct ob
       
       static int mktree_line(unsigned int mode, struct object_id *oid,
      @@ builtin/mktree.c: static int mktree_line(unsigned int mode, struct object_id *oid,
     - 		    path, oid_to_hex(oid), type_name(parsed_obj_type), type_name(mode_type));
     + 		}
       	}
       
      -	append_to_tree(mode, oid, path, data->arr);
     @@ builtin/mktree.c: int cmd_mktree(int ac, const char **av, const char *prefix)
      
       ## t/t1010-mktree.sh ##
      @@ t/t1010-mktree.sh: test_expect_success 'mktree fails on mode mismatch' '
     - 	grep "object $tree_oid is a tree but specified type was (blob)" err
     + 	test_grep "object $tree_oid is a tree but specified type was (blob)" err
       '
       
      +test_expect_success '--literally can create invalid trees' '
     @@ t/t1010-mktree.sh: test_expect_success 'mktree fails on mode mismatch' '
      +	} | git mktree --literally >tree.bad &&
      +	git cat-file tree $(cat tree.bad) >top.bad &&
      +	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
     -+	grep "contains duplicate file entries" err &&
     ++	test_grep "contains duplicate file entries" err &&
      +
      +	# disallowed path
      +	{
     @@ t/t1010-mktree.sh: test_expect_success 'mktree fails on mode mismatch' '
      +	} | git mktree --literally >tree.bad &&
      +	git cat-file tree $(cat tree.bad) >top.bad &&
      +	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
     -+	grep "contains ${SQ}.git${SQ}" err &&
     ++	test_grep "contains ${SQ}.git${SQ}" err &&
      +
      +	# nested entry
      +	{
     @@ t/t1010-mktree.sh: test_expect_success 'mktree fails on mode mismatch' '
      +	} | git mktree --literally >tree.bad &&
      +	git cat-file tree $(cat tree.bad) >top.bad &&
      +	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
     -+	grep "contains full pathnames" err &&
     ++	test_grep "contains full pathnames" err &&
      +
      +	# bad entry ordering
      +	{
     @@ t/t1010-mktree.sh: test_expect_success 'mktree fails on mode mismatch' '
      +	} | git mktree --literally >tree.bad &&
      +	git cat-file tree $(cat tree.bad) >top.bad &&
      +	test_must_fail git hash-object --stdin -t tree <top.bad 2>err &&
     -+	grep "not properly sorted" err
     ++	test_grep "not properly sorted" err
      +'
      +
       test_done
  9:  4f9f77e693c ! 10:  2eb207064f8 mktree: validate paths more carefully
     @@ builtin/mktree.c: static void append_to_tree(unsigned mode, struct object_id *oi
      
       ## t/t1010-mktree.sh ##
      @@ t/t1010-mktree.sh: test_expect_success '--literally can create invalid trees' '
     - 	grep "not properly sorted" err
     + 	test_grep "not properly sorted" err
       '
       
      +test_expect_success 'mktree validates path' '
     @@ t/t1010-mktree.sh: test_expect_success '--literally can create invalid trees' '
      +	# Invalid: blob with trailing slash
      +	printf "100644 blob $blob_oid\ttest/" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "invalid path ${SQ}test/${SQ}" err &&
     ++	test_grep "invalid path ${SQ}test/${SQ}" err &&
      +
      +	# Invalid: dotdot
      +	printf "040000 tree $tree_oid\t../" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "invalid path ${SQ}../${SQ}" err &&
     ++	test_grep "invalid path ${SQ}../${SQ}" err &&
      +
      +	# Invalid: dot
      +	printf "040000 tree $tree_oid\t." |
      +	test_must_fail git mktree 2>err &&
     -+	grep "invalid path ${SQ}.${SQ}" err &&
     ++	test_grep "invalid path ${SQ}.${SQ}" err &&
      +
      +	# Invalid: .git
      +	printf "040000 tree $tree_oid\t.git/" |
      +	test_must_fail git mktree 2>err &&
     -+	grep "invalid path ${SQ}.git/${SQ}" err
     ++	test_grep "invalid path ${SQ}.git/${SQ}" err
      +'
      +
       test_done

10: b59a4ad8ab4 ! 11: fb555658057 mktree: overwrite duplicate entries
@@ Commit message

## Documentation/git-mktree.txt ##
-@@ Documentation/git-mktree.txt: OPTIONS
- INPUT FORMAT
- ------------
- Tree entries may be specified in any of the formats compatible with the ----index-info option to linkgit:git-update-index[1]. The order of the tree --entries is normalized by mktree so pre-sorting the input by path is not --required.
-+--index-info option to linkgit:git-update-index[1].
-+
-+The order of the tree entries is normalized by mktree so pre-sorting the input -+by path is not required. Multiple entries provided with the same path are -+deduplicated, with only the last one specified added to the tree.
+@@ Documentation/git-mktree.txt: cannot be represented in a tree object. The command will fail without
+ writing the tree if a higher order stage is specified for any entry.
+
+ The order of the tree entries is normalized by mktree so pre-sorting the
+-input by path is not required.
++input by path is not required. Multiple entries provided with the same path
++are deduplicated, with only the last one specified added to the tree.

GIT
---
@@ builtin/mktree.c
struct object_id oid;
int len;
@@ builtin/mktree.c: static void append_to_tree(unsigned mode, struct object_id *oid, const char *pat
+ ent->len = len;
oidcpy(&ent->oid, oid);

- /* Append the update */
+ ent->order = arr->nr;
tree_entry_array_push(arr, ent);
}
@@ t/t1010-mktree.sh: test_expect_success '--literally can create invalid trees' '

# Valid: tree with or without trailing slash, blob without trailing slash
@@ t/t1010-mktree.sh: test_expect_success 'mktree validates path' '
- grep "invalid path ${SQ}.git/${SQ}" err
+ test_grep "invalid path ${SQ}.git/${SQ}" err
'

+test_expect_success 'mktree with duplicate entries' '

 11:  130413f2404 = 12:  2333775ba5b mktree: create tree using an in-core index
 12:  94d6615d634 ! 13:  56f28efff54 mktree: use iterator struct to add tree entries to index
     @@ builtin/mktree.c: static void sort_and_dedup_tree_entry_array(struct tree_entry_
      +	} priv;
      +};
      +
     -+static void init_tree_entry_iterator(struct tree_entry_iterator *iter,
     ++static void tree_entry_iterator_init(struct tree_entry_iterator *iter,
      +				     struct tree_entry_array *arr)
      +{
      +	iter->priv.arr = arr;
     @@ builtin/mktree.c: static void sort_and_dedup_tree_entry_array(struct tree_entry_
      +}
      +
      +/*
     -+ * Advance the tree entry iterator to the next entry in the array. If no entries
     -+ * remain, 'current' is set to NULL. Returns the previous 'current' value of the
     -+ * iterator.
     ++ * Advance the tree entry iterator to the next entry in the array. If no
     ++ * entries remain, 'current' is set to NULL.
      + */
     -+static struct tree_entry *advance_tree_entry_iterator(struct tree_entry_iterator *iter)
     ++static void tree_entry_iterator_advance(struct tree_entry_iterator *iter)
      +{
     -+	struct tree_entry *prev = iter->current;
      +	iter->current = (iter->priv.idx + 1) < iter->priv.arr->nr
      +			? iter->priv.arr->entries[++iter->priv.idx]
      +			: NULL;
     -+	return prev;
      +}
      +
       static int add_tree_entry_to_index(struct index_state *istate,
     @@ builtin/mktree.c: static int add_tree_entry_to_index(struct index_state *istate,
       static void write_tree(struct tree_entry_array *arr, struct object_id *oid)
       {
      +	struct tree_entry_iterator iter = { NULL };
     -+	struct tree_entry *ent;
       	struct index_state istate = INDEX_STATE_INIT(the_repository);
       	istate.sparse_index = 1;
       
     @@ builtin/mktree.c: static int add_tree_entry_to_index(struct index_state *istate,
      -	/* Construct an in-memory index from the provided entries */
      -	for (size_t i = 0; i < arr->nr; i++) {
      -		struct tree_entry *ent = arr->entries[i];
     -+	init_tree_entry_iterator(&iter, arr);
     - 
     ++	tree_entry_iterator_init(&iter, arr);
     ++
      +	/* Construct an in-memory index from the provided entries & base tree */
     -+	while ((ent = advance_tree_entry_iterator(&iter))) {
     ++	while (iter.current) {
     ++		struct tree_entry *ent = iter.current;
     ++		tree_entry_iterator_advance(&iter);
     + 
       		if (add_tree_entry_to_index(&istate, ent))
       			die(_("failed to add tree entry '%s'"), ent->name);
     - 	}

13: 68acdd3c5ee ! 14: 6f6d78ae7ac mktree: add directory-file conflict hashmap
@@ builtin/mktree.c: static inline size_t df_path_len(size_t pathlen, unsigned int
+ name_compare(e1->name, e1_len, e2->name, e2_len);
+}
+
-+static void init_tree_entry_array(struct tree_entry_array *arr)
++static void tree_entry_array_init(struct tree_entry_array *arr)
+{
+ hashmap_init(&arr->df_name_hash, df_name_hash_cmp, NULL, 0);
+}
@@ builtin/mktree.c: static inline size_t df_path_len(size_t pathlen, unsigned int
static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entry *ent) {
ALLOC_GROW(arr->entries, arr->nr + 1, arr->alloc);
-@@ builtin/mktree.c: static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entr -
- static void clear_tree_entry_array(struct tree_entry_array *arr)
- {
-+ hashmap_clear(&arr->df_name_hash);
- for (size_t i = 0; i < arr->nr; i++)
- FREE_AND_NULL(arr->entries[i]);
+@@ builtin/mktree.c: static void tree_entry_array_clear(struct tree_entry_array *arr, int free_entrie
+ FREE_AND_NULL(arr->entries[i]);
+ }
arr->nr = 0;
-@@ builtin/mktree.c: static void clear_tree_entry_array(struct tree_entry_array *arr) -
- static void release_tree_entry_array(struct tree_entry_array *arr)
- {
+ hashmap_clear(&arr->df_name_hash);
- FREE_AND_NULL(arr->entries);
- arr->nr = arr->alloc = 0;
}
+
+ static void tree_entry_array_release(struct tree_entry_array *arr, int free_entries) @@ builtin/mktree.c: static void sort_and_dedup_tree_entry_array(struct tree_entry_array *arr) /* Sort again to order the entries for tree insertion */
ignore_mode = 0;
@@ builtin/mktree.c: int cmd_mktree(int ac, const char **av, const char *prefix)

ac = parse_options(ac, av, prefix, option, mktree_usage, 0);

-+ init_tree_entry_array(&arr);
++ tree_entry_array_init(&arr);
+
do {
- ret = read_index_info(nul_term_line, mktree_line, &mktree_line_data);
+ ret = read_index_info(nul_term_line, mktree_line, &mktree_line_data, &line);
if (ret < 0)
14: df0c50dfea3 ! 15: 4b88f84b933 mktree: optionally add to an existing tree

     @@ Documentation/git-mktree.txt: git-mktree - Build a tree-object from formatted tr
       --------
       [verse]
      -'git mktree' [-z] [--missing] [--literally] [--batch]
     -+'git mktree' [-z] [--missing] [--literally] [--batch] [--] [<tree-ish>]
     ++'git mktree' [-z] [--missing] [--literally] [--batch] [<tree-ish>]
       
       DESCRIPTION
       -----------
     @@ Documentation/git-mktree.txt: OPTIONS
       	with NUL.
       
      +<tree-ish>::
     -+	If provided, the tree entries provided in stdin are added to this tree
     -+	rather than a new empty one, replacing existing entries with identical
     -+	names. Not compatible with `--literally`.
     ++	If provided, the tree entries provided in stdin are added to this
     ++	tree rather than a new empty one, replacing existing entries with
     ++	identical names. Not compatible with `--literally`.
      +
       INPUT FORMAT
       ------------
     @@ builtin/mktree.c
       #include "object-store-ll.h"
       
       struct tree_entry {
     -@@ builtin/mktree.c: static struct tree_entry *advance_tree_entry_iterator(struct tree_entry_iterator
     - 	return prev;
     +@@ builtin/mktree.c: static void tree_entry_iterator_advance(struct tree_entry_iterator *iter)
     + 			: NULL;
       }
       
      -static int add_tree_entry_to_index(struct index_state *istate,
     @@ builtin/mktree.c: static struct tree_entry *advance_tree_entry_iterator(struct t
      +				 unsigned mode, void *context)
       {
      -	struct tree_entry_iterator iter = { NULL };
     +-	struct index_state istate = INDEX_STATE_INIT(the_repository);
     +-	istate.sparse_index = 1;
      +	int result;
      +	struct tree_entry *base_tree_ent;
      +	struct build_index_data *cbdata = context;
     @@ builtin/mktree.c: static struct tree_entry *advance_tree_entry_iterator(struct t
      +		int cmp = name_compare(ent->name, ent->len,
      +				       base_tree_ent->name, base_tree_ent->len);
      +		if (!cmp || cmp < 0) {
     -+			advance_tree_entry_iterator(&cbdata->iter);
     ++			tree_entry_iterator_advance(&cbdata->iter);
      +
      +			if (add_tree_entry_to_index(cbdata, ent) < 0) {
      +				result = error(_("failed to add tree entry '%s'"), ent->name);
     @@ builtin/mktree.c: static struct tree_entry *advance_tree_entry_iterator(struct t
      +		       struct object_id *oid)
      +{
      +	struct build_index_data cbdata = { 0 };
     - 	struct tree_entry *ent;
     --	struct index_state istate = INDEX_STATE_INIT(the_repository);
     --	istate.sparse_index = 1;
      +	struct pathspec ps = { 0 };
       
       	sort_and_dedup_tree_entry_array(arr);
       
     --	init_tree_entry_iterator(&iter, arr);
     +-	tree_entry_iterator_init(&iter, arr);
      +	index_state_init(&cbdata.istate, the_repository);
      +	cbdata.istate.sparse_index = 1;
     -+	init_tree_entry_iterator(&cbdata.iter, arr);
     ++	tree_entry_iterator_init(&cbdata.iter, arr);
      +	cbdata.df_name_hash = &arr->df_name_hash;
       
       	/* Construct an in-memory index from the provided entries & base tree */
     --	while ((ent = advance_tree_entry_iterator(&iter))) {
     --		if (add_tree_entry_to_index(&istate, ent))
     +-	while (iter.current) {
     +-		struct tree_entry *ent = iter.current;
     +-		tree_entry_iterator_advance(&iter);
      +	if (base_tree &&
      +	    read_tree(the_repository, base_tree, &ps, build_index_from_tree, &cbdata) < 0)
      +		die(_("failed to create tree"));
      +
     -+	while ((ent = advance_tree_entry_iterator(&cbdata.iter))) {
     ++	while (cbdata.iter.current) {
     ++		struct tree_entry *ent = cbdata.iter.current;
     ++		tree_entry_iterator_advance(&cbdata.iter);
     + 
     +-		if (add_tree_entry_to_index(&istate, ent))
      +		if (add_tree_entry_to_index(&cbdata, ent))
       			die(_("failed to add tree entry '%s'"), ent->name);
       	}
     @@ builtin/mktree.c: static void write_tree_literally(struct tree_entry_array *arr,
       
       static const char *mktree_usage[] = {
      -	"git mktree [-z] [--missing] [--literally] [--batch]",
     -+	"git mktree [-z] [--missing] [--literally] [--batch] [--] [<tree-ish>]",
     ++	"git mktree [-z] [--missing] [--literally] [--batch] [<tree-ish>]",
       	NULL
       };
       
      @@ builtin/mktree.c: int cmd_mktree(int ac, const char **av, const char *prefix)
     - 	int is_batch_mode = 0;
       	struct tree_entry_array arr = { 0 };
       	struct mktree_line_data mktree_line_data = { .arr = &arr };
     + 	struct strbuf line = STRBUF_INIT;
      +	struct tree *base_tree = NULL;
       	int ret;
       
     @@ builtin/mktree.c: int cmd_mktree(int ac, const char **av, const char *prefix)
      +			die(_("not a tree object: %s"), oid_to_hex(&base_tree_oid));
      +	}
       
     - 	init_tree_entry_array(&arr);
     + 	tree_entry_array_init(&arr);
       
      @@ builtin/mktree.c: int cmd_mktree(int ac, const char **av, const char *prefix)
       			if (mktree_line_data.literally)

15: 058354f45f7 ! 16: 46756c4e314 mktree: allow deeper paths in input
@@ Commit message

## Documentation/git-mktree.txt ##
-@@ Documentation/git-mktree.txt: INPUT FORMAT
- Tree entries may be specified in any of the formats compatible with the
- --index-info option to linkgit:git-update-index[1].
+@@ Documentation/git-mktree.txt: Higher stages represent conflicted files in an index; this information
+ cannot be represented in a tree object. The command will fail without
+ writing the tree if a higher order stage is specified for any entry.

+Entries may use full pathnames containing directory separators to specify
-+entries nested within one or more directories. These entries are inserted into -+the appropriate tree in the base tree-ish if one exists. Otherwise, empty parent -+trees are created to contain the entries.
++entries nested within one or more directories. These entries are inserted ++into the appropriate tree in the base tree-ish if one exists. Otherwise, ++empty parent trees are created to contain the entries.
+
- The order of the tree entries is normalized by mktree so pre-sorting the input
- by path is not required. Multiple entries provided with the same path are
- deduplicated, with only the last one specified added to the tree.
+ The order of the tree entries is normalized by mktree so pre-sorting the
+ input by path is not required. Multiple entries provided with the same path
+ are deduplicated, with only the last one specified added to the tree.

## builtin/mktree.c ##
@@ builtin/mktree.c: struct tree_entry {
@@ builtin/mktree.c: static void tree_entry_array_push(struct tree_entry_array *arr
+ return arr->entries[--arr->nr];
+}
+
- static void clear_tree_entry_array(struct tree_entry_array *arr)
+ static void tree_entry_array_clear(struct tree_entry_array *arr, int free_entries) {
- hashmap_clear(&arr->df_name_hash);
+ if (free_entries) {
@@ builtin/mktree.c: static void append_to_tree(unsigned mode, struct object_id *oid, const char *pat

if (!verify_path(ent->name, mode))
@@ builtin/mktree.c: static void sort_and_dedup_tree_entry_array(struct tree_entry_
+ }
+ }
+
-+ release_tree_entry_array(&parent_dir_ents);
++ tree_entry_array_release(&parent_dir_ents, 0);
+ }
+
/* Finally, initialize the directory-file conflict hash map */
@@ builtin/mktree.c: static int build_index_from_tree(const struct object_id *oid,
+ cmp = name_compare(ent->name, ent->len,
+ base_tree_ent->name, base_tree_ent->len);
if (!cmp || cmp < 0) {
- advance_tree_entry_iterator(&cbdata->iter);
+ tree_entry_iterator_advance(&cbdata->iter);

@@ builtin/mktree.c: static int build_index_from_tree(const struct object_id *oid,
goto cleanup_and_return;
@@ builtin/mktree.c: static int build_index_from_tree(const struct object_id *oid,

## t/t1010-mktree.sh ##
@@ t/t1010-mktree.sh: test_expect_success 'mktree with invalid submodule OIDs' '
- grep "object $tree_oid is a tree but specified type was (commit)" err
+ done
'

-test_expect_success 'mktree refuses to read ls-tree -r output (1)' '
@@ t/t1010-mktree.sh: test_expect_success 'mktree with base tree' '
+ printf "100644 blob $blob_oid\ttest/deeper\n"
+ } |
+ test_must_fail git mktree 2>err &&
-+ grep "You have both test and test/deeper" err &&
++ test_grep "You have both test and test/deeper" err &&
+
+ {
+ printf "100644 blob $blob_oid\tfolder/one/deeper/deep\n"
+ } |
+ test_must_fail git mktree $tree_oid 2>err &&
-+ grep "You have both folder/one and folder/one/deeper/deep" err
++ test_grep "You have both folder/one and folder/one/deeper/deep" err
+'
+
test_done
16: a90d6d0c943 ! 17: d392c440b8a mktree: remove entries when mode is 0

     @@ Commit message
          Signed-off-by: Victoria Dye <[email protected]>
      
       ## Documentation/git-mktree.txt ##
     -@@ Documentation/git-mktree.txt: entries nested within one or more directories. These entries are inserted into
     - the appropriate tree in the base tree-ish if one exists. Otherwise, empty parent
     - trees are created to contain the entries.
     +@@ Documentation/git-mktree.txt: entries nested within one or more directories. These entries are inserted
     + into the appropriate tree in the base tree-ish if one exists. Otherwise,
     + empty parent trees are created to contain the entries.
       
     -+An entry with a mode of "0" will remove an entry of the same name from the base
     -+tree-ish. If no tree-ish argument is given, or the entry does not exist in that
     -+tree, the entry is ignored.
     ++An entry with a mode of "0" will remove an entry of the same name from the
     ++base tree-ish. If no tree-ish argument is given, or the entry does not exist
     ++in that tree, the entry is ignored.
      +
     - The order of the tree entries is normalized by `mktree` so pre-sorting the input
     - by path is not required. Multiple entries provided with the same path are
     - deduplicated, with only the last one specified added to the tree.
     + The order of the tree entries is normalized by `mktree` so pre-sorting the
     + input by path is not required. Multiple entries provided with the same path
     + are deduplicated, with only the last one specified added to the tree.
      
       ## builtin/mktree.c ##
      @@ builtin/mktree.c: struct tree_entry {
     @@ builtin/mktree.c: static int build_index_from_tree(const struct object_id *oid,
       		int ret = 0;
       		struct pathspec ps = { 0 };
      @@ builtin/mktree.c: static int mktree_line(unsigned int mode, struct object_id *oid,
     - 		       const char *path, void *cbdata)
     - {
     - 	struct mktree_line_data *data = cbdata;
     --	enum object_type mode_type = object_type(mode);
     --	struct object_info oi = OBJECT_INFO_INIT;
     --	enum object_type parsed_obj_type;
     - 
     --	if (obj_type && mode_type != obj_type)
     --		die("object type (%s) doesn't match mode type (%s)",
     --		    type_name(obj_type), type_name(mode_type));
     -+	if (mode) {
     -+		struct object_info oi = OBJECT_INFO_INIT;
     -+		enum object_type parsed_obj_type;
     -+		enum object_type mode_type = object_type(mode);
     - 
     --	oi.typep = &parsed_obj_type;
     -+		if (obj_type && mode_type != obj_type)
     -+			die("object type (%s) doesn't match mode type (%s)",
     -+			    type_name(obj_type), type_name(mode_type));
     + 	if (stage)
     + 		die(_("path '%s' is unmerged"), path);
       
     --	if (oid_object_info_extended(the_repository, oid, &oi,
     --				     OBJECT_INFO_LOOKUP_REPLACE |
     --				     OBJECT_INFO_QUICK |
     --				     OBJECT_INFO_SKIP_FETCH_OBJECT) < 0)
     --		parsed_obj_type = -1;
     -+		oi.typep = &parsed_obj_type;
     - 
     --	if (parsed_obj_type < 0) {
     --		if (data->allow_missing || S_ISGITLINK(mode)) {
     --			; /* no problem - missing objects & submodules are presumed to be of the right type */
     --		} else {
     --			die("entry '%s' object %s is unavailable", path, oid_to_hex(oid));
     -+		if (oid_object_info_extended(the_repository, oid, &oi,
     -+					     OBJECT_INFO_LOOKUP_REPLACE |
     -+					     OBJECT_INFO_QUICK |
     -+					     OBJECT_INFO_SKIP_FETCH_OBJECT) < 0)
     -+			parsed_obj_type = -1;
     ++	/* OID ignored for zero-mode entries; append unconditionally */
     ++	if (!mode)
     ++		goto append_entry;
      +
     -+		if (parsed_obj_type < 0) {
     -+			if (data->allow_missing || S_ISGITLINK(mode)) {
     -+				; /* no problem - missing objects & submodules are presumed to be of the right type */
     -+			} else {
     -+				die("entry '%s' object %s is unavailable", path, oid_to_hex(oid));
     -+			}
     -+		} else if (parsed_obj_type != mode_type) {
     -+			/*
     -+			* The object exists but is of the wrong type.
     -+			* This is a problem regardless of allow_missing
     -+			* because the new tree entry will never be correct.
     -+			*/
     -+			die("entry '%s' object %s is a %s but specified type was (%s)",
     -+			path, oid_to_hex(oid), type_name(parsed_obj_type), type_name(mode_type));
     + 	if (obj_type != OBJ_ANY && mode_type != obj_type)
     + 		die("object type (%s) doesn't match mode type (%s)",
     + 		    type_name(obj_type), type_name(mode_type));
     +@@ builtin/mktree.c: static int mktree_line(unsigned int mode, struct object_id *oid,
       		}
     --	} else if (parsed_obj_type != mode_type) {
     --		/*
     --		 * The object exists but is of the wrong type.
     --		 * This is a problem regardless of allow_missing
     --		 * because the new tree entry will never be correct.
     --		 */
     --		die("entry '%s' object %s is a %s but specified type was (%s)",
     --		    path, oid_to_hex(oid), type_name(parsed_obj_type), type_name(mode_type));
       	}
       
     ++append_entry:
       	append_to_tree(mode, oid, path, data->arr, data->literally);
     + 	return 0;
     + }
      
       ## t/t1010-mktree.sh ##
      @@ t/t1010-mktree.sh: test_expect_success 'mktree fails on directory-file conflict' '
     - 	grep "You have both folder/one and folder/one/deeper/deep" err
     + 	test_grep "You have both folder/one and folder/one/deeper/deep" err
       '
       
      +test_expect_success 'mktree with remove entries' '

gitgitgadget

From: Victoria Dye <[email protected]>

Replace 'OPT_SET_INT' with 'OPT_BOOL' for the options '--missing' and '--batch'. The use of 'OPT_SET_INT' in these options is identical to 'OPT_BOOL', but 'OPT_BOOL' provides slightly simpler syntax.

---
 builtin/mktree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index 9a22d4e2773..8b19d440747 100644
@@ -162,8 +162,8 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 
 	const struct option option[] = {
 		OPT_BOOL('z', NULL, &nul_term_line, N_("input is NUL terminated")),
-		OPT_SET_INT( 0 , "missing", &allow_missing, N_("allow missing objects"), 1),
-		OPT_SET_INT( 0 , "batch", &is_batch_mode, N_("allow creation of more than one tree"), 1),
+		OPT_BOOL(0, "missing", &allow_missing, N_("allow missing objects")),
+		OPT_BOOL(0, "batch", &is_batch_mode, N_("allow creation of more than one tree")),
 		OPT_END()
 	};
 

gitgitgadget

From: Victoria Dye <[email protected]>

Rename the type for better readability, clearly specifying "entry" (instead of the "ent" abbreviation) and separating "tree" from "entry".

---
 builtin/mktree.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

index 8b19d440747..c02feb06aff 100644
@@ -12,7 +12,7 @@
 #include "parse-options.h"
 #include "object-store-ll.h"
 
-static struct treeent {
+static struct tree_entry {
 	unsigned mode;
 	struct object_id oid;
 	int len;

@@ -22,7 +22,7 @@ static int alloc, used;
 
 static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
 {
-	struct treeent *ent;
+	struct tree_entry *ent;
 	size_t len = strlen(path);
 	if (strchr(path, '/'))
 		die("path %s contains slash", path);

@@ -38,8 +38,8 @@ static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
 
 static int ent_compare(const void *a_, const void *b_)
 {
-	struct treeent *a = *(struct treeent **)a_;
-	struct treeent *b = *(struct treeent **)b_;
+	struct tree_entry *a = *(struct tree_entry **)a_;
+	struct tree_entry *b = *(struct tree_entry **)b_;
 	return base_name_compare(a->name, a->len, a->mode,
 				 b->name, b->len, b->mode);
 }

@@ -56,7 +56,7 @@ static void write_tree(struct object_id *oid)
 
 	strbuf_init(&buf, size);
 	for (i = 0; i < used; i++) {
-		struct treeent *ent = entries[i];
+		struct tree_entry *ent = entries[i];
 		strbuf_addf(&buf, "%o %s%c", ent->mode, ent->name, '\0');
 		strbuf_add(&buf, ent->oid.hash, the_hash_algo->rawsz);
 	}

gitgitgadget

From: Victoria Dye <[email protected]>

Replace the static 'struct tree_entry **entries' with a non-static 'struct tree_entry_array' instance. In later commits, we'll want to be able to create additional 'struct tree_entry_array' instances utilizing common functionality (create, push, clear, free). To avoid code duplication, create the 'struct tree_entry_array' type and add functions that perform those basic operations.

---
 builtin/mktree.c | 69 ++++++++++++++++++++++++++++++++++--------------
 1 file changed, 49 insertions(+), 20 deletions(-)

index c02feb06aff..a96ea10bf95 100644
@@ -12,15 +12,42 @@
 #include "parse-options.h"
 #include "object-store-ll.h"
 
-static struct tree_entry {
+struct tree_entry {
 	unsigned mode;
 	struct object_id oid;
 	int len;
 	char name[FLEX_ARRAY];
-} **entries;
-static int alloc, used;
+};
+
+struct tree_entry_array {
+	size_t nr, alloc;
+	struct tree_entry **entries;
+};
+
+static void tree_entry_array_push(struct tree_entry_array *arr, struct tree_entry *ent)
+{
+	ALLOC_GROW(arr->entries, arr->nr + 1, arr->alloc);
+	arr->entries[arr->nr++] = ent;
+}
+
+static void tree_entry_array_clear(struct tree_entry_array *arr, int free_entries)
+{
+	if (free_entries) {
+		for (size_t i = 0; i < arr->nr; i++)
+			FREE_AND_NULL(arr->entries[i]);
+	}
+	arr->nr = 0;
+}
 
-static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
+static void tree_entry_array_release(struct tree_entry_array *arr, int free_entries)
+{
+	tree_entry_array_clear(arr, free_entries);
+	FREE_AND_NULL(arr->entries);
+	arr->alloc = 0;
+}
+
+static void append_to_tree(unsigned mode, struct object_id *oid, const char *path,
+			   struct tree_entry_array *arr)
 {
 	struct tree_entry *ent;
 	size_t len = strlen(path);

@@ -32,8 +59,7 @@ static void append_to_tree(unsigned mode, struct object_id *oid, char *path)
 	ent->len = len;
 	oidcpy(&ent->oid, oid);
 
-	ALLOC_GROW(entries, used + 1, alloc);
-	entries[used++] = ent;
+	tree_entry_array_push(arr, ent);
 }
 
 static int ent_compare(const void *a_, const void *b_)

@@ -44,19 +70,18 @@ static int ent_compare(const void *a_, const void *b_)
 				 b->name, b->len, b->mode);
 }
 
-static void write_tree(struct object_id *oid)
+static void write_tree(struct tree_entry_array *arr, struct object_id *oid)
 {
 	struct strbuf buf;
-	size_t size;
-	int i;
+	size_t size = 0;
 
-	QSORT(entries, used, ent_compare);
-	for (size = i = 0; i < used; i++)
-		size += 32 + entries[i]->len;
+	QSORT(arr->entries, arr->nr, ent_compare);
+	for (size_t i = 0; i < arr->nr; i++)
+		size += 32 + arr->entries[i]->len;
 
 	strbuf_init(&buf, size);
-	for (i = 0; i < used; i++) {
-		struct tree_entry *ent = entries[i];
+	for (size_t i = 0; i < arr->nr; i++) {
+		struct tree_entry *ent = arr->entries[i];
 		strbuf_addf(&buf, "%o %s%c", ent->mode, ent->name, '\0');
 		strbuf_add(&buf, ent->oid.hash, the_hash_algo->rawsz);
 	}

@@ -70,7 +95,8 @@ static const char *mktree_usage[] = {
 	NULL
 };
 
-static void mktree_line(char *buf, int nul_term_line, int allow_missing)
+static void mktree_line(char *buf, int nul_term_line, int allow_missing,
+			struct tree_entry_array *arr)
 {
 	char *ptr, *ntr;
 	const char *p;

@@ -146,7 +172,7 @@ static void mktree_line(char *buf, int nul_term_line, int allow_missing)
 		}
 	}
 
-	append_to_tree(mode, &oid, path);
+	append_to_tree(mode, &oid, path, arr);
 	free(to_free);
 }
 

@@ -158,6 +184,7 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 	int allow_missing = 0;
 	int is_batch_mode = 0;
 	int got_eof = 0;
+	struct tree_entry_array arr = { 0 };
 	strbuf_getline_fn getline_fn;
 
 	const struct option option[] = {

@@ -182,9 +209,9 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 					break;
 				die("input format error: (blank line only valid in batch mode)");
 			}
-			mktree_line(sb.buf, nul_term_line, allow_missing);
+			mktree_line(sb.buf, nul_term_line, allow_missing, &arr);
 		}
-		if (is_batch_mode && got_eof && used < 1) {
+		if (is_batch_mode && got_eof && arr.nr < 1) {
 			/*
 			 * Execution gets here if the last tree entry is terminated with a
 			 * new-line.  The final new-line has been made optional to be

@@ -192,12 +219,14 @@ int cmd_mktree(int ac, const char **av, const char *prefix)
 			 */
 			; /* skip creating an empty tree */
 		} else {
-			write_tree(&oid);
+			write_tree(&arr, &oid);
 			puts(oid_to_hex(&oid));
 			fflush(stdout);
 		}
-		used=0; /* reset tree entry buffer for re-use in batch mode */
+		tree_entry_array_clear(&arr, 1); /* reset tree entry buffer for re-use in batch mode */
 	}
+
+	tree_entry_array_release(&arr, 1);
 	strbuf_release(&sb);
 	return 0;
 }

gitgitgadget

From: Victoria Dye <[email protected]>

Move 'read_index_info()' into a new header 'index-info.h' and generalize the function to call a provided callback for each parsed line. Update 'update-index.c' to use this generalized 'read_index_info()', adding the callback 'apply_index_info()' to verify the parsed line and update the index according to its contents.

Switching to using a callback to validate the parsed entry in 'update-index' results in a slight change to the error message indicating a file could not be removed from the index. The original implementation uses the raw, quoted pathname in the error message, whereas the callback (without access to the raw pathname) uses the unquoted value. However, this change makes the failed removal message consistent with all other error messages in the function, and that consistency is likely more beneficial than not to a user.

The motivation for this change is to consolidate the already-similar input parsing logic in 'git update-index' and 'git mktree', avoiding code duplication and the associated maintenance burden. The input formats accepted by 'update-index' are a superset of those accepted by 'mktree', so in a later commit we can replace the input parsing of the latter with 'read_index_info()' without breaking existing usage.

---
 Documentation/git-update-index.txt   |  16 +---
 Documentation/index-info-formats.txt |  13 +++
 Makefile                             |   1 +
 builtin/update-index.c               | 129 +++++++--------------------
 index-info.c                         |  90 +++++++++++++++++++
 index-info.h                         |  11 +++
 t/t2107-update-index-basic.sh        |  27 ++++++
 7 files changed, 177 insertions(+), 110 deletions(-)
 create mode 100644 Documentation/index-info-formats.txt
 create mode 100644 index-info.c
 create mode 100644 index-info.h

index 7128aed5405..e52aecb845d 100644
@@ -278,21 +278,9 @@ USING --INDEX-INFO
 
 `--index-info` is a more powerful mechanism that lets you feed
 multiple entry definitions from the standard input, and designed
-specifically for scripts.  It can take inputs of three formats:
+specifically for scripts.  It can take inputs in the following formats:
 
-    . mode SP type SP sha1          TAB path
-+
-This format is to stuff `git ls-tree` output into the index.
-
-    . mode         SP sha1 SP stage TAB path
-+
-This format is to put higher order stages into the
-index file and matches 'git ls-files --stage' output.
-
-    . mode         SP sha1          TAB path
-+
-This format is no longer produced by any Git command, but is
-and will continue to be supported by `update-index --index-info`.
+include::index-info-formats.txt[]
 
 To place a higher stage entry to the index, the path should
 first be removed by feeding a mode=0 entry for the path, and

new file mode 100644
index 00000000000..037ebd24321
@@ -0,0 +1,13 @@
+    . mode SP type SP sha1          TAB path
++
+This format is to use `git ls-tree` output.
+
+    . mode         SP sha1 SP stage TAB path
++
+This format allows higher order stages to appear and
+matches 'git ls-files --stage' output.
+
+    . mode         SP sha1          TAB path
++
+This format is no longer produced by any Git command, but is
+and will continue to be supported.

index 2f5f16847ae..db9604e59c3 100644
@@ -1037,6 +1037,7 @@ LIB_OBJS += hex.o
 LIB_OBJS += hex-ll.o
 LIB_OBJS += hook.o
 LIB_OBJS += ident.o
+LIB_OBJS += index-info.o
 LIB_OBJS += json-writer.o
 LIB_OBJS += kwset.o
 LIB_OBJS += levenshtein.o

new file mode 100644
index 00000000000..d650498325a
@@ -0,0 +1,11 @@
+#ifndef INDEX_INFO_H
+#define INDEX_INFO_H
+
+#include "hash.h"
+
+typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);
+
+/* Iterate over parsed index info from stdin */
+int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata);
+
+#endif /* INDEX_INFO_H */

index cc72ead79f3..794a5b1a184 100755
@@ -142,4 +142,31 @@ test_expect_success '--index-version' '
 	test_must_be_empty actual
 '
 
+test_expect_success '--index-info fails on malformed input' '
+	# empty line
+	echo "" |
+	test_must_fail git update-index --index-info 2>err &&
+	test_grep "malformed input line" err &&
+
+	# bad whitespace
+	printf "100644 $EMPTY_BLOB A" |
+	test_must_fail git update-index --index-info 2>err &&
+	test_grep "malformed input line" err &&
+
+	# invalid stage value
+	printf "100644 $EMPTY_BLOB 5\tA" |
+	test_must_fail git update-index --index-info 2>err &&
+	test_grep "malformed input line" err &&
+
+	# invalid OID length
+	printf "100755 abc123\tA" |
+	test_must_fail git update-index --index-info 2>err &&
+	test_grep "malformed input line" err &&
+
+	# bad quoting
+	printf "100644 $EMPTY_BLOB\t\"A" |
+	test_must_fail git update-index --index-info 2>err &&
+	test_grep "bad quoting of path name" err
+'
+
 test_done

gitgitgadget

From: Victoria Dye <[email protected]>

Update 'read_index_info()' to return INDEX_INFO_UNRECOGNIZED_LINE (value 1), rather than die()-ing when the function encounters a line that cannot be parsed according to one of the accepted formats. This grants the caller the flexibility to fall back on custom handling for such lines rather than a returning a catch-all error. In the case of 'update-index', we'll still exit with a "malformed input line" error. However, when 'read_index_info()' is used to process the input to 'mktree' in a later patch, an empty line return value will signal a new tree in --batch mode.

---
 builtin/update-index.c |  9 +++++++--
 index-info.c           | 16 +++++++++-------
 index-info.h           |  5 ++++-
 3 files changed, 20 insertions(+), 10 deletions(-)

index fddf59b54c1..8d0b40a6fd6 100644
@@ -787,11 +787,16 @@ static enum parse_opt_result stdin_cacheinfo_callback(
 		ret = error("option '%s' must be the last argument", opt->long_name);
 	} else {
 		int *nul_term_line = opt->value;
+		struct strbuf line = STRBUF_INIT;
 
 		allow_add = allow_replace = allow_remove = 1;
-		ret = read_index_info(*nul_term_line, apply_index_info, NULL);
-		if (ret)
+		ret = read_index_info(*nul_term_line, apply_index_info, NULL, &line);
+
+		if (ret == INDEX_INFO_UNRECOGNIZED_LINE)
+			ret = error("malformed input line '%s'", line.buf);
+		else if (ret)
 			ret = -1;
+		strbuf_release(&line);
 	}
 
 	return ret;

index 8ccaac5487b..7a02f66426a 100644
@@ -5,16 +5,16 @@
 #include "strbuf.h"
 #include "quote.h"
 
-int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
+int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
+		    struct strbuf *line)
 {
 	const int hexsz = the_hash_algo->hexsz;
-	struct strbuf buf = STRBUF_INIT;
 	struct strbuf uq = STRBUF_INIT;
 	strbuf_getline_fn getline_fn;
 	int ret = 0;
 
 	getline_fn = nul_term_line ? strbuf_getline_nul : strbuf_getline_lf;
-	while (getline_fn(&buf, stdin) != EOF) {
+	while (getline_fn(line, stdin) != EOF) {
 		char *ptr, *tab;
 		char *path_name;
 		struct object_id oid;

@@ -39,8 +39,8 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
 		 * index file and matches "git ls-files --stage" output.
 		 */
 		errno = 0;
-		ul = strtoul(buf.buf, &ptr, 8);
-		if (ptr == buf.buf || *ptr != ' '
+		ul = strtoul(line->buf, &ptr, 8);
+		if (ptr == line->buf || *ptr != ' '
 		    || errno || (unsigned int) ul != ul)
 			goto bad_line;
 		mode = ul;

@@ -81,10 +81,12 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata)
 		continue;
 
 	bad_line:
-		die("malformed input line '%s'", buf.buf);
+		ret = INDEX_INFO_UNRECOGNIZED_LINE;
+		break;
 	}
-	strbuf_release(&buf);
 	strbuf_release(&uq);
+	if (!ret)
+		strbuf_reset(line);
 
 	return ret;
 }

index d650498325a..9258011462d 100644
@@ -5,7 +5,10 @@
 
 typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);
 
+#define INDEX_INFO_UNRECOGNIZED_LINE 1
+
 /* Iterate over parsed index info from stdin */
-int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata);
+int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
+		    struct strbuf *line);
 
 #endif /* INDEX_INFO_H */

gitgitgadget

From: Victoria Dye <[email protected]>

If the object type (e.g. "blob", "tree") is identified on a stdin line read by 'read_index_info()' (i.e. on lines formatted like the output of 'git ls-tree'), parse it into an 'enum object_type' and provide it to the 'read_index_info()' callback as an argument. If the type is not provided, pass 'OBJ_ANY' instead. If the object type is invalid, return an error.

The goal of this change is to allow for more thorough validation of the provided object type (e.g. against the provided mode) in 'mktree' once 'mktree_line' is replaced with 'read_index_info()'. Note, though, that this change also strengthens the validation done by 'update-index', since invalid type names now trigger an error.

---
 builtin/update-index.c        |  3 ++-
 index-info.c                  | 16 ++++++++++++----
 index-info.h                  |  3 ++-
 t/t2107-update-index-basic.sh |  5 +++++
 4 files changed, 21 insertions(+), 6 deletions(-)

index 8d0b40a6fd6..42a274f9ce4 100644
@@ -510,7 +510,8 @@ static void update_one(const char *path)
 	report("add '%s'", path);
 }
 
-static int apply_index_info(unsigned int mode, struct object_id *oid, int stage,
+static int apply_index_info(unsigned int mode, struct object_id *oid,
+			    enum object_type obj_type UNUSED, int stage,
 			    const char *path_name, void *cbdata UNUSED)
 {
 	if (!verify_path(path_name, mode)) {

index 7a02f66426a..9c986cd9093 100644
@@ -18,6 +18,7 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
 		char *ptr, *tab;
 		char *path_name;
 		struct object_id oid;
+		enum object_type obj_type = OBJ_ANY;
 		unsigned int mode;
 		unsigned long ul;
 		int stage;

@@ -51,18 +52,17 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
 
 		if (tab[-2] == ' ' && '0' <= tab[-1] && tab[-1] <= '3') {
 			stage = tab[-1] - '0';
-			ptr = tab + 1; /* point at the head of path */
+			path_name = tab + 1; /* point at the head of path */
 			tab = tab - 2; /* point at tail of sha1 */
 		} else {
 			stage = 0;
-			ptr = tab + 1; /* point at the head of path */
+			path_name = tab + 1; /* point at the head of path */
 		}
 
 		if (get_oid_hex(tab - hexsz, &oid) ||
 			tab[-(hexsz + 1)] != ' ')
 			goto bad_line;
 
-		path_name = ptr;
 		if (!nul_term_line && path_name[0] == '"') {
 			strbuf_reset(&uq);
 			if (unquote_c_style(&uq, path_name, NULL)) {

@@ -72,7 +72,15 @@ int read_index_info(int nul_term_line, each_index_info_fn fn, void *cbdata,
 			path_name = uq.buf;
 		}
 
-		ret = fn(mode, &oid, stage, path_name, cbdata);
+		/* Get the type, if provided */
+		if (tab - hexsz - 1 > ptr + 1) {
+			if (*(tab - hexsz - 1) != ' ')
+				goto bad_line;
+			*(tab - hexsz - 1) = '\0';
+			obj_type = type_from_string(ptr + 1);
+		}
+
+		ret = fn(mode, &oid, obj_type, stage, path_name, cbdata);
 		if (ret) {
 			ret = -1;
 			break;

index 9258011462d..adea453b197 100644
@@ -2,8 +2,9 @@
 #define INDEX_INFO_H
 
 #include "hash.h"
+#include "object.h"
 
-typedef int (*each_index_info_fn)(unsigned int, struct object_id *, int, const char *, void *);
+typedef int (*each_index_info_fn)(unsigned int, struct object_id *, enum object_type, int, const char *, void *);
 
 #define INDEX_INFO_UNRECOGNIZED_LINE 1
 

index 794a5b1a184..9e0e77bbf9e 100755
@@ -153,6 +153,11 @@ test_expect_success '--index-info fails on malformed input' '
 	test_must_fail git update-index --index-info 2>err &&
 	test_grep "malformed input line" err &&
 
+	# invalid type
+	printf "100644 bad $EMPTY_BLOB\tA" |
+	test_must_fail git update-index --index-info 2>err &&
+	test_grep "invalid object type" err &&
+
 	# invalid stage value
 	printf "100644 $EMPTY_BLOB 5\tA" |
 	test_must_fail git update-index --index-info 2>err &&

gitgitgadget

From: Victoria Dye <[email protected]>

Replace the custom input parsing of 'mktree' with 'read_index_info()', which handles not only the 'ls-tree' output format it already handles but also the other formats compatible with 'update-index'. This lends some consistency across the commands (avoiding the need for two similar implementations for input parsing) and adds flexibility to mktree.

It should be noted that, while the error messages are largely preserved in the refactor, one does change: "fatal: invalid quoting" is now "error: bad quoting of path name".

Update 'Documentation/git-mktree.txt' to reflect the more permissive input format, as well as make a note about rejecting stage values higher than 0.

---
 Documentation/git-mktree.txt |  26 ++++--
 builtin/mktree.c             | 156 +++++++++++++++--------------------
 t/t1010-mktree.sh            |  66 +++++++++++++++
 3 files changed, 151 insertions(+), 97 deletions(-)

index 383f09dd333..c187403c6bd 100644
@@ -3,7 +3,7 @@ git-mktree(1)
 
 NAME
 ----
-git-mktree - Build a tree-object from ls-tree formatted text
+git-mktree - Build a tree-object from formatted tree entries
 
 
 SYNOPSIS

@@ -13,15 +13,14 @@ SYNOPSIS
 
 DESCRIPTION
 -----------
-Reads standard input in non-recursive `ls-tree` output format, and creates
-a tree object.  The order of the tree entries is normalized by mktree so
-pre-sorting the input is not required.  The object name of the tree object
-built is written to the standard output.
+Reads entry information from stdin and creates a tree object from those
+entries. The object name of the tree object built is written to the standard
+output.
 
 OPTIONS
 -------
 -z::
-	Read the NUL-terminated `ls-tree -z` output instead.
+	Input lines are separated with NUL rather than LF.
 
 --missing::
 	Allow missing objects.  The default behaviour (without this option)

@@ -35,6 +34,21 @@ OPTIONS
 	optional.  Note - if the `-z` option is used, lines are terminated
 	with NUL.
 
+INPUT FORMAT
+------------
+Tree entries may be specified in any of the formats compatible with the
+`--index-info` option to linkgit:git-update-index[1]:
+
+include::index-info-formats.txt[]
+
+Note that if the `stage` of a tree entry is given, the value must be 0.
+Higher stages represent conflicted files in an index; this information
+cannot be represented in a tree object. The command will fail without
+writing the tree if a higher order stage is specified for any entry.
+
+The order of the tree entries is normalized by `mktree` so pre-sorting the
+input by path is not required.
+
 GIT
 ---
 Part of the linkgit:git[1] suite

gitgitgadget

From: Victoria Dye <[email protected]>

Adjust the 'git mktree' tree entry intake logic to no longer fail if an OID specified with a S_IFGITLINK mode exists in the current repository's object database with a different type.

While this scenario likely represents a mistake by the user, submodule OIDs are not validated as part of object writes or in 'git fsck'. In other commands, any object info would be ignored if such an OID was found in the current repository with a different type.

Since this check is not needed to avoid creation of a corrupt tree, let's remove it and make 'git mktree' less opinionated as a result.

---
 builtin/mktree.c  | 58 ++++++++++++++++++++++-------------------------
 t/t1010-mktree.sh | 18 ++++++---------
 2 files changed, 34 insertions(+), 42 deletions(-)

index 03a9899bc11..f509ed1a81f 100644
@@ -107,8 +107,6 @@ static int mktree_line(unsigned int mode, struct object_id *oid,
 {
 	struct mktree_line_data *data = cbdata;
 	enum object_type mode_type = object_type(mode);
-	struct object_info oi = OBJECT_INFO_INIT;
-	enum object_type parsed_obj_type;
 
 	if (stage)
 		die(_("path '%s' is unmerged"), path);

@@ -117,36 +115,34 @@ static int mktree_line(unsigned int mode, struct object_id *oid,
 		die("object type (%s) doesn't match mode type (%s)",
 		    type_name(obj_type), type_name(mode_type));
 
-	oi.typep = &parsed_obj_type;
-
-	if (oid_object_info_extended(the_repository, oid, &oi,
-				     OBJECT_INFO_LOOKUP_REPLACE |
+	if (!S_ISGITLINK(mode)) {
+		struct object_info oi = OBJECT_INFO_INIT;
+		enum object_type parsed_obj_type;
+		unsigned int flags = OBJECT_INFO_LOOKUP_REPLACE |
 				     OBJECT_INFO_QUICK |
-				     OBJECT_INFO_SKIP_FETCH_OBJECT) < 0)
-		parsed_obj_type = -1;
-
-	if (parsed_obj_type < 0) {
-		/*
-		 * There are two conditions where the object being missing
-		 * is acceptable:
-		 *
-		 * - We're explicitly allowing it with --missing.
-		 * - The object is a submodule, which we wouldn't expect to
-		 *   be in this repo anyway.
-		 *
-		 * If neither condition is met, die().
-		 */
-		if (!data->allow_missing && !S_ISGITLINK(mode))
-			die("entry '%s' object %s is unavailable", path, oid_to_hex(oid));
-
-	} else if (parsed_obj_type != mode_type) {
-		/*
-		 * The object exists but is of the wrong type.
-		 * This is a problem regardless of allow_missing
-		 * because the new tree entry will never be correct.
-		 */
-		die("entry '%s' object %s is a %s but specified type was (%s)",
-		    path, oid_to_hex(oid), type_name(parsed_obj_type), type_name(mode_type));
+				     OBJECT_INFO_SKIP_FETCH_OBJECT;
+
+		oi.typep = &parsed_obj_type;
+
+		if (oid_object_info_extended(the_repository, oid, &oi, flags) < 0) {
+			/*
+			 * If the object is missing and we aren't explicitly
+			 * allowing missing objects, die(). Otherwise, continue
+			 * without error.
+			 */
+			if (!data->allow_missing)
+				die("entry '%s' object %s is unavailable", path,
+				    oid_to_hex(oid));
+		} else if (parsed_obj_type != mode_type) {
+			/*
+			 * The object exists but is of the wrong type.
+			 * This is a problem regardless of allow_missing
+			 * because the new tree entry will never be correct.
+			 */
+			die("entry '%s' object %s is a %s but specified type was (%s)",
+			    path, oid_to_hex(oid), type_name(parsed_obj_type),
+			    type_name(mode_type));
+		}
 	}
 
 	append_to_tree(mode, oid, path, data->arr);