{"thread":{"id":"54533","subject":"[PATCH 00/20] fundamentals of merge-ort implementation","startedAt":"2020-10-30T03:42:39Z","lastAt":"2020-10-30T03:58:14Z","messageCount":22,"participants":["Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":20},"messages":[{"id":"408694","messageId":"20201030034131.1479968-1-newren@gmail.com","threadId":"54533","inReplyTo":null,"subject":"[PATCH 00/20] fundamentals of merge-ort implementation","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:11Z","receivedAt":"2020-10-30T03:42:39Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on a merge of en/strmap and\nen/merge-ort-api-null-impl.\n\nThe goal of this series is to show the new design and structure behind\nmerge-ort, particularly the bits that are completely different to how\nmerge-recursive operates. There are still multiple important codepaths\nthat die with a \"Not yet implemented\" message, so the new merge\nalgorithm is still not very usable (however, it can handle very trivial\nrebases or cherry-picks at the end of the series).\n\nAt a high level, merge-ort avoids unpack_trees() and the index, instead\nusing traverse_trees() and its own data structure. After it is done\nprocessing each path, it writes a tree. Only after it has created a new\ntree will it touch the working copy or the index. It does so by using a\nsimple checkout-like step to switch from head to the newly created tree.\nIf there are unmerged entries, it touches up the index after the\ncheckout-like step to record those higher order stages.\n\nIn the series:\n * Patch 1 adds some basic data structures.\n * Patch 2 documents the high-level steps.\n * Patches 3-5 are some simple setup.\n * Patches 6-10 collect data from the traverse_trees() operation.\n * Patches 11-15 process the individual paths and create a tree.\n * Patches 16-19 handle checkout-and-then-write-higher-order-stages.\n * Patch 20 frees data from the merge_options_internal data structure\n\nElijah Newren (20):\n merge-ort: setup basic internal data structures\n merge-ort: add some high-level algorithm structure\n merge-ort: port merge_start() from merge-recursive\n merge-ort: use histogram diff\n merge-ort: add an err() function similar to one from merge-recursive\n merge-ort: implement a very basic collect_merge_info()\n merge-ort: avoid repeating fill_tree_descriptor() on the same tree\n merge-ort: compute a few more useful fields for collect_merge_info\n merge-ort: record stage and auxiliary info for every path\n merge-ort: avoid recursing into identical trees\n merge-ort: add a preliminary simple process_entries() implementation\n merge-ort: have process_entries operate in a defined order\n merge-ort: step 1 of tree writing -- record basenames, modes, and oids\n merge-ort: step 2 of tree writing -- function to create tree object\n merge-ort: step 3 of tree writing -- handling subdirectories as we go\n merge-ort: basic outline for merge_switch_to_result()\n merge-ort: add implementation of checkout()\n tree: enable cmp_cache_name_compare() to be used elsewhere\n merge-ort: add implementation of record_unmerged_index_entries()\n merge-ort: free data structures in merge_finalize()\n\n merge-ort.c | 922 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n tree.c | 2 +-\n tree.h | 2 +\n 3 files changed, 922 insertions(+), 4 deletions(-)\n\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408695","messageId":"20201030034131.1479968-8-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 07/20] merge-ort: avoid repeating fill_tree_descriptor() on the same tree","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:18Z","receivedAt":"2020-10-30T03:42:39Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Three-way merges, by their nature, are going to often have two or more\ntrees match at a given subdirectory. We can avoid calling\nfill_tree_descriptor() on the same tree by checking when these trees\nmatch. Noting when various oids match will also be useful in other\ncalculations and optimizations as well.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 26 ++++++++++++++++++++++----\n 1 file changed, 22 insertions(+), 4 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex d652f1f062..7083388a47 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -99,6 +99,15 @@ static int collect_merge_info_callback(int n,\n \tunsigned mbase_null = !(mask & 1);\n \tunsigned side1_null = !(mask & 2);\n \tunsigned side2_null = !(mask & 4);\n+\tunsigned side1_matches_mbase = (!side1_null && !mbase_null &&\n+\t\t\t\t\tnames[0].mode == names[1].mode &&\n+\t\t\t\t\toideq(&names[0].oid, &names[1].oid));\n+\tunsigned side2_matches_mbase = (!side2_null && !mbase_null &&\n+\t\t\t\t\tnames[0].mode == names[2].mode &&\n+\t\t\t\t\toideq(&names[0].oid, &names[2].oid));\n+\tunsigned sides_match = (!side1_null && !side2_null &&\n+\t\t\t\tnames[1].mode == names[2].mode &&\n+\t\t\t\toideq(&names[1].oid, &names[2].oid));\n \n \t/* n = 3 is a fundamental assumption. */\n \tif (n != 3)\n@@ -154,10 +163,19 @@ static int collect_merge_info_callback(int n,\n \t\tnewinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);\n \n \t\tfor (i = 0; i < 3; i++, dirmask >>= 1) {\n-\t\t\tconst struct object_id *oid = NULL;\n-\t\t\tif (dirmask & 1)\n-\t\t\t\toid = &names[i].oid;\n-\t\t\tbuf[i] = fill_tree_descriptor(opt->repo, t + i, oid);\n+\t\t\tif (i == 1 && side1_matches_mbase)\n+\t\t\t\tt[1] = t[0];\n+\t\t\telse if (i == 2 && side2_matches_mbase)\n+\t\t\t\tt[2] = t[0];\n+\t\t\telse if (i == 2 && sides_match)\n+\t\t\t\tt[2] = t[1];\n+\t\t\telse {\n+\t\t\t\tconst struct object_id *oid = NULL;\n+\t\t\t\tif (dirmask & 1)\n+\t\t\t\t\toid = &names[i].oid;\n+\t\t\t\tbuf[i] = fill_tree_descriptor(opt->repo,\n+\t\t\t\t\t\t\t t + i, oid);\n+\t\t\t}\n \t\t}\n \n \t\toriginal_dir_name = opti->current_dir_name;\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408696","messageId":"20201030034131.1479968-5-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 04/20] merge-ort: use histogram diff","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:15Z","receivedAt":"2020-10-30T03:42:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"I have some ideas for using a histogram diff to improve content merges,\nwhich fundamentally relies on the idea of a histogram. Since the diffs\nare never displayed to the user but just used internally for merging,\nthe typical user preference shouldn't matter anyway, and I want to make\nsure that all my testing works with this algorithm.\n\nGranted, I don't yet know if those ideas will pan out and I haven't even\ntried any of them out yet, but it's easy to change the diff algorithm in\nthe future if needed or wanted. For now, just set it to histogram.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 4 ++++\n 1 file changed, 4 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex bee9507319..e629d7b62c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -21,6 +21,7 @@\n #include \"diffcore.h\"\n #include \"strmap.h\"\n #include \"tree.h\"\n+#include \"xdiff-interface.h\"\n \n struct merge_options_internal {\n \tstruct strmap paths; /* maps path -> (merged|conflict)_info */\n@@ -137,6 +138,9 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \n \tassert(opt->priv == NULL);\n \n+\t/* Default to histogram diff. Actually, just hardcode it...for now. */\n+\topt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);\n+\n \t/* Initialization of opt->priv, our internal merge data */\n \topt->priv = xcalloc(1, sizeof(*opt->priv));\n \t/*\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408697","messageId":"20201030034131.1479968-2-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 01/20] merge-ort: setup basic internal data structures","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:12Z","receivedAt":"2020-10-30T03:42:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Set up some basic internal data structures. The only carry-over from\nmerge-recursive.c is call_depth, though needed_rename_limit will be\nadded later.\n\nThe central piece of data will definitely be the strmap \"paths\", which\nwill map every relevant pathname under consideration to either a\nmerged_info or a conflict_info. (\"unmerged\" is a strmap that is a\nsubset of \"paths\".)\n\nmerged_info contains all relevant information for a non-conflicted\nentry. conflict_info contains a merged_info, plus any additional\ninformation about a conflict such as the higher orders stages involved\nand the names of the paths those came from (handy once renames get\ninvolved). If an entry remains conflicted, the merged_info portion of a\nconflict_info will later be filled with whatever version of the file\nshould be placed in the working directory (e.g. an as-merged-as-possible\nvariation that contains conflict markers).\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 40 ++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 40 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b487901d3e..9d5ea0930d 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,6 +17,46 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"strmap.h\"\n+\n+struct merge_options_internal {\n+\tstruct strmap paths; /* maps path -> (merged|conflict)_info */\n+\tstruct strmap unmerged; /* maps path -> conflict_info */\n+\tconst char *current_dir_name;\n+\tint call_depth;\n+};\n+\n+struct version_info {\n+\tstruct object_id oid;\n+\tunsigned short mode;\n+};\n+\n+struct merged_info {\n+\tstruct version_info result;\n+\tunsigned is_null:1;\n+\tunsigned clean:1;\n+\tsize_t basename_offset;\n+\t /*\n+\t * Containing directory name. Note that we assume directory_name is\n+\t * constructed such that\n+\t * strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,\n+\t * i.e. string equality is equivalent to pointer equality. For this\n+\t * to hold, we have to be careful setting directory_name.\n+\t */\n+\tconst char *directory_name;\n+};\n+\n+struct conflict_info {\n+\tstruct merged_info merged;\n+\tstruct version_info stages[3];\n+\tconst char *pathnames[3];\n+\tunsigned df_conflict:1;\n+\tunsigned path_conflict:1;\n+\tunsigned filemask:3;\n+\tunsigned dirmask:3;\n+\tunsigned match_mask:3;\n+};\n+\n void merge_switch_to_result(struct merge_options *opt,\n \t\t\t struct tree *head,\n \t\t\t struct merge_result *result,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408698","messageId":"20201030034131.1479968-3-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 02/20] merge-ort: add some high-level algorithm structure","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:13Z","receivedAt":"2020-10-30T03:42:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"merge_ort_nonrecursive_internal() will be used by both\nmerge_inmemory_nonrecursive() and merge_inmemory_recursive(); let's\nfocus on it for now. It involves some setup -- merge_start() --\nfollowed by the following chain of functions:\n\n collect_merge_info()\n This function will populate merge_options_internal's paths field,\n via a call to traverse_trees() and a new callback that will be added\n later.\n\n detect_and_process_renames()\n This function will detect renames, and then adjust entries in paths\n to move conflict stages from old pathnames into those for new\n pathnames, so that the next step doesn't have to think about renames\n and just can do three-way content merging and such.\n\n process_entries()\n This function determines how to take the various stages (versions of\n a file from the three different sides) and merge them, and whether\n to mark the result as conflicted or cleanly merged. It also writes\n out these merged file versions as it goes to create a tree.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 66 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 9d5ea0930d..b53cd80104 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -18,6 +18,7 @@\n #include \"merge-ort.h\"\n \n #include \"strmap.h\"\n+#include \"tree.h\"\n \n struct merge_options_internal {\n \tstruct strmap paths; /* maps path -> (merged|conflict)_info */\n@@ -57,6 +58,37 @@ struct conflict_info {\n \tunsigned match_mask:3;\n };\n \n+static int collect_merge_info(struct merge_options *opt,\n+\t\t\t struct tree *merge_base,\n+\t\t\t struct tree *side1,\n+\t\t\t struct tree *side2)\n+{\n+\tdie(\"Not yet implemented.\");\n+}\n+\n+static int detect_and_process_renames(struct merge_options *opt,\n+\t\t\t\t struct tree *merge_base,\n+\t\t\t\t struct tree *side1,\n+\t\t\t\t struct tree *side2)\n+{\n+\tint clean = 1;\n+\n+\t/*\n+\t * Rename detection works by detecting file similarity. Here we use\n+\t * a really easy-to-implement scheme: files are similar IFF they have\n+\t * the same filename. Therefore, by this scheme, there are no renames.\n+\t *\n+\t * TODO: Actually implement a real rename detection scheme.\n+\t */\n+\treturn clean;\n+}\n+\n+static void process_entries(struct merge_options *opt,\n+\t\t\t struct object_id *result_oid)\n+{\n+\tdie(\"Not yet implemented.\");\n+}\n+\n void merge_switch_to_result(struct merge_options *opt,\n \t\t\t struct tree *head,\n \t\t\t struct merge_result *result,\n@@ -73,13 +105,46 @@ void merge_finalize(struct merge_options *opt,\n \tdie(\"Not yet implemented\");\n }\n \n+static void merge_start(struct merge_options *opt, struct merge_result *result)\n+{\n+\tdie(\"Not yet implemented.\");\n+}\n+\n+/*\n+ * Originally from merge_trees_internal(); heavily adapted, though.\n+ */\n+static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n+\t\t\t\t\t struct tree *merge_base,\n+\t\t\t\t\t struct tree *side1,\n+\t\t\t\t\t struct tree *side2,\n+\t\t\t\t\t struct merge_result *result)\n+{\n+\tstruct object_id working_tree_oid;\n+\n+\tcollect_merge_info(opt, merge_base, side1, side2);\n+\tresult->clean = detect_and_process_renames(opt, merge_base,\n+\t\t\t\t\t\t side1, side2);\n+\tprocess_entries(opt, &working_tree_oid);\n+\n+\t/* Set return values */\n+\tresult->tree = parse_tree_indirect(&working_tree_oid);\n+\t/* existence of unmerged entries implies unclean */\n+\tresult->clean &= strmap_empty(&opt->priv->unmerged);\n+\tif (!opt->priv->call_depth) {\n+\t\tresult->priv = opt->priv;\n+\t\topt->priv = NULL;\n+\t}\n+}\n+\n void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n \t\t\t struct tree *side2,\n \t\t\t struct merge_result *result)\n {\n-\tdie(\"Not yet implemented\");\n+\tassert(opt->ancestor != NULL);\n+\tmerge_start(opt, result);\n+\tmerge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);\n }\n \n void merge_incore_recursive(struct merge_options *opt,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408699","messageId":"20201030034131.1479968-7-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 06/20] merge-ort: implement a very basic collect_merge_info()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:17Z","receivedAt":"2020-10-30T03:42:44Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This does not actually collect any necessary info other than the\npathnames involved, since it just allocates an all-zero conflict_info\nand stuffs that into paths. However, it invokes the traverse_trees()\nmachinery to walk over all the paths and sets up the basic\ninfrastructure we need.\n\nI have left out a few obvious optimizations to try to make this patch as\nshort and obvious as possible. A subsequent patch will add some of\nthose back in with some more useful data fields before we introduce a\npatch that actually sets up the conflict_info fields.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 121 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 119 insertions(+), 2 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex ffea7ac8ea..d652f1f062 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -77,13 +77,130 @@ static int err(struct merge_options *opt, const char *err, ...)\n \treturn -1;\n }\n \n+static int collect_merge_info_callback(int n,\n+\t\t\t\t unsigned long mask,\n+\t\t\t\t unsigned long dirmask,\n+\t\t\t\t struct name_entry *names,\n+\t\t\t\t struct traverse_info *info)\n+{\n+\t/*\n+\t * n is 3. Always.\n+\t * common ancestor (mbase) has mask 1, and stored in index 0 of names\n+\t * head of side 1 (side1) has mask 2, and stored in index 1 of names\n+\t * head of side 2 (side2) has mask 4, and stored in index 2 of names\n+\t */\n+\tstruct merge_options *opt = info->data;\n+\tstruct merge_options_internal *opti = opt->priv;\n+\tstruct conflict_info *ci;\n+\tstruct name_entry *p;\n+\tsize_t len;\n+\tchar *fullpath;\n+\tunsigned filemask = mask & ~dirmask;\n+\tunsigned mbase_null = !(mask & 1);\n+\tunsigned side1_null = !(mask & 2);\n+\tunsigned side2_null = !(mask & 4);\n+\n+\t/* n = 3 is a fundamental assumption. */\n+\tif (n != 3)\n+\t\tBUG(\"Called collect_merge_info_callback wrong\");\n+\n+\t/*\n+\t * A bunch of sanity checks verifying that traverse_trees() calls\n+\t * us the way I expect. Could just remove these at some point,\n+\t * though maybe they are helpful to future code readers.\n+\t */\n+\tassert(mbase_null == is_null_oid(&names[0].oid));\n+\tassert(side1_null == is_null_oid(&names[1].oid));\n+\tassert(side2_null == is_null_oid(&names[2].oid));\n+\tassert(!mbase_null || !side1_null || !side2_null);\n+\tassert(mask > 0 && mask < 8);\n+\n+\t/* Other invariant checks, mostly for documentation purposes. */\n+\tassert(mask == (dirmask | filemask));\n+\n+\t/*\n+\t * Get the name of the relevant filepath, which we'll pass to\n+\t * setup_path_info() for tracking.\n+\t */\n+\tp = names;\n+\twhile (!p->mode)\n+\t\tp++;\n+\tlen = traverse_path_len(info, p->pathlen);\n+\n+\t/* +1 in both of the following lines to include the NUL byte */\n+\tfullpath = xmalloc(len+1);\n+\tmake_traverse_path(fullpath, len+1, info, p->path, p->pathlen);\n+\n+\t/*\n+\t * TODO: record information about the path other than all zeros,\n+\t * so we can resolve later in process_entries.\n+\t */\n+\tci = xcalloc(1, sizeof(struct conflict_info));\n+\tstrmap_put(&opti->paths, fullpath, ci);\n+\n+\t/* If dirmask, recurse into subdirectories */\n+\tif (dirmask) {\n+\t\tstruct traverse_info newinfo;\n+\t\tstruct tree_desc t[3];\n+\t\tvoid *buf[3] = {NULL,};\n+\t\tconst char *original_dir_name;\n+\t\tint i, ret;\n+\n+\t\tci->match_mask &= filemask;\n+\t\tnewinfo = *info;\n+\t\tnewinfo.prev = info;\n+\t\tnewinfo.name = p->path;\n+\t\tnewinfo.namelen = p->pathlen;\n+\t\tnewinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);\n+\n+\t\tfor (i = 0; i < 3; i++, dirmask >>= 1) {\n+\t\t\tconst struct object_id *oid = NULL;\n+\t\t\tif (dirmask & 1)\n+\t\t\t\toid = &names[i].oid;\n+\t\t\tbuf[i] = fill_tree_descriptor(opt->repo, t + i, oid);\n+\t\t}\n+\n+\t\toriginal_dir_name = opti->current_dir_name;\n+\t\topti->current_dir_name = fullpath;\n+\t\tret = traverse_trees(NULL, 3, t, &newinfo);\n+\t\topti->current_dir_name = original_dir_name;\n+\n+\t\tfor (i = 0; i < 3; i++)\n+\t\t\tfree(buf[i]);\n+\n+\t\tif (ret < 0)\n+\t\t\treturn -1;\n+\t}\n+\n+\treturn mask;\n+}\n+\n static int collect_merge_info(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n \t\t\t struct tree *side2)\n {\n-\t/* TODO: Implement this using traverse_trees() */\n-\tdie(\"Not yet implemented.\");\n+\tint ret;\n+\tstruct tree_desc t[3];\n+\tstruct traverse_info info;\n+\tchar *toplevel_dir_placeholder = \"\";\n+\n+\topt->priv->current_dir_name = toplevel_dir_placeholder;\n+\tsetup_traverse_info(&info, toplevel_dir_placeholder);\n+\tinfo.fn = collect_merge_info_callback;\n+\tinfo.data = opt;\n+\tinfo.show_all_errors = 1;\n+\n+\tparse_tree(merge_base);\n+\tparse_tree(side1);\n+\tparse_tree(side2);\n+\tinit_tree_desc(t+0, merge_base->buffer, merge_base->size);\n+\tinit_tree_desc(t+1, side1->buffer, side1->size);\n+\tinit_tree_desc(t+2, side2->buffer, side2->size);\n+\n+\tret = traverse_trees(NULL, 3, t, &info);\n+\n+\treturn ret;\n }\n \n static int detect_and_process_renames(struct merge_options *opt,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408700","messageId":"20201030034131.1479968-14-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 13/20] merge-ort: step 1 of tree writing -- record basenames, modes, and oids","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:24Z","receivedAt":"2020-10-30T03:42:44Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"As a step towards transforming the processed path->conflict_info entries\ninto an actual tree object, start recording basenames, modes, and oids\nin a dir_metadata structure. Subsequent commits will make use of this\nto actually write a tree.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 35 ++++++++++++++++++++++++++++++++---\n 1 file changed, 32 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 31c16edd3d..17159df5db 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -351,10 +351,31 @@ static int string_list_df_name_compare(const char *one, const char *two)\n \treturn onelen - twolen;\n }\n \n+struct directory_versions {\n+\tstruct string_list versions;\n+};\n+\n+static void record_entry_for_tree(struct directory_versions *dir_metadata,\n+\t\t\t\t const char *path,\n+\t\t\t\t struct conflict_info *ci)\n+{\n+\tconst char *basename;\n+\n+\tif (ci->merged.is_null)\n+\t\t/* nothing to record */\n+\t\treturn;\n+\n+\tbasename = path + ci->merged.basename_offset;\n+\tassert(strchr(basename, '/') == NULL);\n+\tstring_list_append(&dir_metadata->versions,\n+\t\t\t basename)->util = &ci->merged.result;\n+}\n+\n /* Per entry merge function */\n static void process_entry(struct merge_options *opt,\n \t\t\t const char *path,\n-\t\t\t struct conflict_info *ci)\n+\t\t\t struct conflict_info *ci,\n+\t\t\t struct directory_versions *dir_metadata)\n {\n \tassert(!ci->merged.clean);\n \tassert(ci->filemask >= 0 && ci->filemask <= 7);\n@@ -434,6 +455,7 @@ static void process_entry(struct merge_options *opt,\n \t */\n \tif (!ci->merged.clean)\n \t\tstrmap_put(&opt->priv->unmerged, path, ci);\n+\trecord_entry_for_tree(dir_metadata, path, ci);\n }\n \n static void process_entries(struct merge_options *opt,\n@@ -443,6 +465,7 @@ static void process_entries(struct merge_options *opt,\n \tstruct strmap_entry *e;\n \tstruct string_list plist = STRING_LIST_INIT_NODUP;\n \tstruct string_list_item *entry;\n+\tstruct directory_versions dir_metadata;\n \n \tif (strmap_empty(&opt->priv->paths)) {\n \t\toidcpy(result_oid, opt->repo->hash_algo->empty_tree);\n@@ -459,6 +482,9 @@ static void process_entries(struct merge_options *opt,\n \tplist.cmp = string_list_df_name_compare;\n \tstring_list_sort(&plist);\n \n+\t/* other setup */\n+\tstring_list_init(&dir_metadata.versions, 0);\n+\n \t/*\n \t * Iterate over the items in reverse order, so we can handle paths\n \t * below a directory before needing to handle the directory itself.\n@@ -471,11 +497,14 @@ static void process_entries(struct merge_options *opt,\n \t\t */\n \t\tstruct conflict_info *ci = entry->util;\n \n-\t\tif (!ci->merged.clean)\n-\t\t\tprocess_entry(opt, path, ci);\n+\t\tif (ci->merged.clean)\n+\t\t\trecord_entry_for_tree(&dir_metadata, path, ci);\n+\t\telse\n+\t\t\tprocess_entry(opt, path, ci, &dir_metadata);\n \t}\n \n \tstring_list_clear(&plist, 0);\n+\tstring_list_clear(&dir_metadata.versions, 0);\n \tdie(\"Tree creation not yet implemented\");\n }\n \n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408701","messageId":"20201030034131.1479968-12-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 11/20] merge-ort: add a preliminary simple process_entries() implementation","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:22Z","receivedAt":"2020-10-30T03:42:44Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Add a process_entries() implementation that just loops over the paths\nand processes each one individually with an auxiliary process_entry()\ncall. Add a basic process_entry() as well, which handles several cases\nbut leaves a few of the more involved ones with die-not-implemented\nmessages. Also, although process_entries() is supposed to create a\ntree, it does not yet have code to do so -- except in the special case\nof merging completely empty trees.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 105 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 2a402e18ed..f4bf1baf78 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -324,10 +324,114 @@ static int detect_and_process_renames(struct merge_options *opt,\n \treturn clean;\n }\n \n+/* Per entry merge function */\n+static void process_entry(struct merge_options *opt,\n+\t\t\t const char *path,\n+\t\t\t struct conflict_info *ci)\n+{\n+\tassert(!ci->merged.clean);\n+\tassert(ci->filemask >= 0 && ci->filemask <= 7);\n+\n+\tif (ci->filemask == 0) {\n+\t\t/*\n+\t\t * This is a placeholder for directories that were recursed\n+\t\t * into; nothing to do in this case.\n+\t\t */\n+\t\treturn;\n+\t}\n+\n+\tif (ci->df_conflict) {\n+\t\tdie(\"Not yet implemented.\");\n+\t}\n+\n+\t/*\n+\t * NOTE: Below there is a long switch-like if-elseif-elseif... block\n+\t * which the code goes through even for the df_conflict cases\n+\t * above. Well, it will once we don't die-not-implemented above.\n+\t */\n+\tif (ci->match_mask) {\n+\t\tci->merged.clean = 1;\n+\t\tif (ci->match_mask == 6) {\n+\t\t\t/* stages[1] == stages[2] */\n+\t\t\tci->merged.result.mode = ci->stages[1].mode;\n+\t\t\toidcpy(&ci->merged.result.oid, &ci->stages[1].oid);\n+\t\t} else {\n+\t\t\t/* determine the mask of the side that didn't match */\n+\t\t\tunsigned int othermask = 7 & ~ci->match_mask;\n+\t\t\tint side = (othermask == 4) ? 2 : 1;\n+\n+\t\t\tci->merged.is_null = (ci->filemask == ci->match_mask);\n+\t\t\tci->merged.result.mode = ci->stages[side].mode;\n+\t\t\toidcpy(&ci->merged.result.oid, &ci->stages[side].oid);\n+\n+\t\t\tassert(othermask == 2 || othermask == 4);\n+\t\t\tassert(ci->merged.is_null == !ci->merged.result.mode);\n+\t\t}\n+\t} else if (ci->filemask >= 6 &&\n+\t\t (S_IFMT & ci->stages[1].mode) !=\n+\t\t (S_IFMT & ci->stages[2].mode)) {\n+\t\t/*\n+\t\t * Two different items from (file/submodule/symlink)\n+\t\t */\n+\t\tdie(\"Not yet implemented.\");\n+\t} else if (ci->filemask >= 6) {\n+\t\t/*\n+\t\t * TODO: Needs a two-way or three-way content merge, but we're\n+\t\t * just being lazy and copying the version from HEAD and\n+\t\t * leaving it as conflicted.\n+\t\t */\n+\t\tci->merged.clean = 0;\n+\t\tci->merged.result.mode = ci->stages[1].mode;\n+\t\toidcpy(&ci->merged.result.oid, &ci->stages[1].oid);\n+\t} else if (ci->filemask == 3 || ci->filemask == 5) {\n+\t\t/* Modify/delete */\n+\t\tdie(\"Not yet implemented.\");\n+\t} else if (ci->filemask == 2 || ci->filemask == 4) {\n+\t\t/* Added on one side */\n+\t\tint side = (ci->filemask == 4) ? 2 : 1;\n+\t\tci->merged.result.mode = ci->stages[side].mode;\n+\t\toidcpy(&ci->merged.result.oid, &ci->stages[side].oid);\n+\t\tci->merged.clean = !ci->df_conflict && !ci->path_conflict;\n+\t} else if (ci->filemask == 1) {\n+\t\t/* Deleted on both sides */\n+\t\tci->merged.is_null = 1;\n+\t\tci->merged.result.mode = 0;\n+\t\toidcpy(&ci->merged.result.oid, &null_oid);\n+\t\tci->merged.clean = !ci->path_conflict;\n+\t}\n+\n+\t/*\n+\t * If still unmerged, record it separately. This allows us to later\n+\t * iterate over just unmerged entries when updating the index instead\n+\t * of iterating over all entries.\n+\t */\n+\tif (!ci->merged.clean)\n+\t\tstrmap_put(&opt->priv->unmerged, path, ci);\n+}\n+\n static void process_entries(struct merge_options *opt,\n \t\t\t struct object_id *result_oid)\n {\n-\tdie(\"Not yet implemented.\");\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *e;\n+\n+\tif (strmap_empty(&opt->priv->paths)) {\n+\t\toidcpy(result_oid, opt->repo->hash_algo->empty_tree);\n+\t\treturn;\n+\t}\n+\n+\tstrmap_for_each_entry(&opt->priv->paths, &iter, e) {\n+\t\t/*\n+\t\t * WARNING: If ci->merged.clean is true, then ci does not\n+\t\t * actually point to a conflict_info but a struct merge_info.\n+\t\t */\n+\t\tstruct conflict_info *ci = e->value;\n+\n+\t\tif (!ci->merged.clean)\n+\t\t\tprocess_entry(opt, e->key, e->value);\n+\t}\n+\n+\tdie(\"Tree creation not yet implemented\");\n }\n \n void merge_switch_to_result(struct merge_options *opt,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408702","messageId":"20201030034131.1479968-13-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 12/20] merge-ort: have process_entries operate in a defined order","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:23Z","receivedAt":"2020-10-30T03:42:47Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"We want to handle paths below a directory before needing to handle the\ndirectory itself. Also, we want to handle the directory immediately\nafter the paths below it, so we can't use simple lexicographic ordering\nfrom strcmp (which would insert foo.txt between foo and foo/file.c).\nCopy string_list_df_name_compare() from merge-recursive.c, and set up a\nstring list of paths sorted by that function so that we can iterate in\nthe desired order.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 47 insertions(+), 2 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex f4bf1baf78..31c16edd3d 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -324,6 +324,33 @@ static int detect_and_process_renames(struct merge_options *opt,\n \treturn clean;\n }\n \n+static int string_list_df_name_compare(const char *one, const char *two)\n+{\n+\tint onelen = strlen(one);\n+\tint twolen = strlen(two);\n+\t/*\n+\t * Here we only care that entries for D/F conflicts are\n+\t * adjacent, in particular with the file of the D/F conflict\n+\t * appearing before files below the corresponding directory.\n+\t * The order of the rest of the list is irrelevant for us.\n+\t *\n+\t * To achieve this, we sort with df_name_compare and provide\n+\t * the mode S_IFDIR so that D/F conflicts will sort correctly.\n+\t * We use the mode S_IFDIR for everything else for simplicity,\n+\t * since in other cases any changes in their order due to\n+\t * sorting cause no problems for us.\n+\t */\n+\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n+\t\t\t\t two, twolen, S_IFDIR);\n+\t/*\n+\t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n+\t * that 'foo' comes before 'foo/bar'.\n+\t */\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn onelen - twolen;\n+}\n+\n /* Per entry merge function */\n static void process_entry(struct merge_options *opt,\n \t\t\t const char *path,\n@@ -414,23 +441,41 @@ static void process_entries(struct merge_options *opt,\n {\n \tstruct hashmap_iter iter;\n \tstruct strmap_entry *e;\n+\tstruct string_list plist = STRING_LIST_INIT_NODUP;\n+\tstruct string_list_item *entry;\n \n \tif (strmap_empty(&opt->priv->paths)) {\n \t\toidcpy(result_oid, opt->repo->hash_algo->empty_tree);\n \t\treturn;\n \t}\n \n+\t/* Hack to pre-allocate plist to the desired size */\n+\tALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);\n+\n+\t/* Put every entry from paths into plist, then sort */\n \tstrmap_for_each_entry(&opt->priv->paths, &iter, e) {\n+\t\tstring_list_append(&plist, e->key)->util = e->value;\n+\t}\n+\tplist.cmp = string_list_df_name_compare;\n+\tstring_list_sort(&plist);\n+\n+\t/*\n+\t * Iterate over the items in reverse order, so we can handle paths\n+\t * below a directory before needing to handle the directory itself.\n+\t */\n+\tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n+\t\tchar *path = entry->string;\n \t\t/*\n \t\t * WARNING: If ci->merged.clean is true, then ci does not\n \t\t * actually point to a conflict_info but a struct merge_info.\n \t\t */\n-\t\tstruct conflict_info *ci = e->value;\n+\t\tstruct conflict_info *ci = entry->util;\n \n \t\tif (!ci->merged.clean)\n-\t\t\tprocess_entry(opt, e->key, e->value);\n+\t\t\tprocess_entry(opt, path, ci);\n \t}\n \n+\tstring_list_clear(&plist, 0);\n \tdie(\"Tree creation not yet implemented\");\n }\n \n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408703","messageId":"20201030034131.1479968-11-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 10/20] merge-ort: avoid recursing into identical trees","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:21Z","receivedAt":"2020-10-30T03:42:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"When all three trees have the same oid, there is no need to recurse into\nthese trees to find that all files within them happen to match. We can\njust record any one of the trees as the resolution of merging that\nparticular path.\n\nImmediately resolving trees for other types of trivial tree merges (such\nas one side matches the merge base, or the two sides match each other)\nwould prevent us from detecting renames for some paths, and thus prevent\nus from doing three-way content merges for those paths whose renames we\ndid not detect.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 14 ++++++++++++++\n 1 file changed, 14 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 60e2b78e2d..2a402e18ed 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -202,6 +202,20 @@ static int collect_merge_info_callback(int n,\n \tfullpath = xmalloc(len+1);\n \tmake_traverse_path(fullpath, len+1, info, p->path, p->pathlen);\n \n+\t/*\n+\t * If mbase, side1, and side2 all match, we can resolve early. Even\n+\t * if these are trees, there will be no renames or anything\n+\t * underneath.\n+\t */\n+\tif (side1_matches_mbase && side2_matches_mbase) {\n+\t\t/* mbase, side1, & side2 all match; use mbase as resolution */\n+\t\tsetup_path_info(opt, &pi, dirname, info->pathlen, fullpath,\n+\t\t\t\tnames, names+0, mbase_null, 0,\n+\t\t\t\tfilemask, dirmask, 1);\n+\t\tstrmap_put(&opti->paths, pi.string, pi.util);\n+\t\treturn mask;\n+\t}\n+\n \t/*\n \t * Record information about the path so we can resolve later in\n \t * process_entries.\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408704","messageId":"20201030034131.1479968-15-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 14/20] merge-ort: step 2 of tree writing -- function to create tree object","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:25Z","receivedAt":"2020-10-30T03:42:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Create a new function, write_tree(), which will take a list of\nbasenames, modes, and oids for a single directory and create a tree\nobject in the object-store. We do not yet have just basenames, modes,\nand oids for just a single directory (we have a mixture of entries from\nall directory levels in the hierarchy) so we still die() before the\ncurrent call to write_tree(), but the next patch will rectify that.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 53 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 17159df5db..ad34800705 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -19,6 +19,7 @@\n \n #include \"diff.h\"\n #include \"diffcore.h\"\n+#include \"object-store.h\"\n #include \"strmap.h\"\n #include \"tree.h\"\n #include \"xdiff-interface.h\"\n@@ -355,6 +356,50 @@ struct directory_versions {\n \tstruct string_list versions;\n };\n \n+static void write_tree(struct object_id *result_oid,\n+\t\t struct string_list *versions,\n+\t\t unsigned int offset)\n+{\n+\tsize_t maxlen = 0;\n+\tunsigned int nr = versions->nr - offset;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tstruct string_list relevant_entries = STRING_LIST_INIT_NODUP;\n+\tint i;\n+\n+\t/*\n+\t * We want to sort the last (versions->nr-offset) entries in versions.\n+\t * Do so by abusing the string_list API a bit: make another string_list\n+\t * that contains just those entries and then sort them.\n+\t *\n+\t * We won't use relevant_entries again and will let it just pop off the\n+\t * stack, so there won't be allocation worries or anything.\n+\t */\n+\trelevant_entries.items = versions->items + offset;\n+\trelevant_entries.nr = versions->nr - offset;\n+\tstring_list_sort(&relevant_entries);\n+\n+\t/* Pre-allocate some space in buf */\n+\tfor (i = 0; i < nr; i++) {\n+\t\tmaxlen += strlen(versions->items[offset+i].string) + 34;\n+\t}\n+\tstrbuf_reset(&buf);\n+\tstrbuf_grow(&buf, maxlen);\n+\n+\t/* Write each entry out to buf */\n+\tfor (i = 0; i < nr; i++) {\n+\t\tstruct merged_info *mi = versions->items[offset+i].util;\n+\t\tstruct version_info *ri = &mi->result;\n+\t\tstrbuf_addf(&buf, \"%o %s%c\",\n+\t\t\t ri->mode,\n+\t\t\t versions->items[offset+i].string, '\\0');\n+\t\tstrbuf_add(&buf, ri->oid.hash, the_hash_algo->rawsz);\n+\t}\n+\n+\t/* Write this object file out, and record in result_oid */\n+\twrite_object_file(buf.buf, buf.len, tree_type, result_oid);\n+\tstrbuf_release(&buf);\n+}\n+\n static void record_entry_for_tree(struct directory_versions *dir_metadata,\n \t\t\t\t const char *path,\n \t\t\t\t struct conflict_info *ci)\n@@ -503,9 +548,16 @@ static void process_entries(struct merge_options *opt,\n \t\t\tprocess_entry(opt, path, ci, &dir_metadata);\n \t}\n \n+\t/*\n+\t * TODO: We can't actually write a tree yet, because dir_metadata just\n+\t * contains all basenames of all files throughout the tree with their\n+\t * mode and hash. Not only is that a nonsensical tree, it will have\n+\t * lots of duplicates for paths such as \"Makefile\" or \".gitignore\".\n+\t */\n+\tdie(\"Not yet implemented; need to process subtrees separately\");\n+\twrite_tree(result_oid, &dir_metadata.versions, 0);\n \tstring_list_clear(&plist, 0);\n \tstring_list_clear(&dir_metadata.versions, 0);\n-\tdie(\"Tree creation not yet implemented\");\n }\n \n void merge_switch_to_result(struct merge_options *opt,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408705","messageId":"20201030034131.1479968-16-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 15/20] merge-ort: step 3 of tree writing -- handling subdirectories as we go","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:26Z","receivedAt":"2020-10-30T03:42:51Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Our order for processing of entries means that if we have a tree of\nfiles that looks like\n Makefile\n src/moduleA/foo.c\n src/moduleA/bar.c\n src/moduleB/baz.c\n src/moduleB/umm.c\n tokens.txt\n\nThen we will process paths in the order of the leftmost column below. I\nhave added two additional columns that help explain the algorithm that\nfollows; the 2nd column is there to remind us we have oid & mode info we\nare tracking for each of these paths (which differs between the paths\nwhich I'm not representing well here), and the third column annotates\nthe parent directory of the entry:\n tokens.txt \"\"\n src/moduleB/umm.c src/moduleB\n src/moduleB/baz.c src/moduleB\n src/moduleB src\n src/moduleA/foo.c src/moduleA\n src/moduleA/bar.c src/moduleA\n src/moduleA src\n src \"\"\n Makefile \"\"\n\nWhen the parent directory changes, if it's a subdirectory of the previous\nparent directory (e.g. \"\" -> src/moduleB) then we can just keep appending.\nIf the parent directory differs from the previous parent directory and is\nnot a subdirectory, then we should process that directory.\n\nSo, for example, when we get to this point:\n tokens.txt \"\"\n src/moduleB/umm.c src/moduleB\n src/moduleB/baz.c src/moduleB\n\nand note that the next entry (src/moduleB) has a different parent than\nthe last one that isn't a subdirectory, we should write out a tree for it\n 100644 blob umm.c\n 100644 blob baz.c\n\nthen pop all the entries under that directory while recording the new\nhash for that directory, leaving us with\n tokens.txt \"\"\n src/moduleB src\n\nThis process repeats until at the end we get to\n tokens.txt \"\"\n src \"\"\n Makefile \"\"\n\nand then we can write out the toplevel tree. Since we potentially have\nentries in our string_list corresponding to multiple different toplevel\ndirectories, e.g. a slightly different repository might have:\n whizbang.txt \"\"\n tokens.txt \"\"\n src/moduleD src\n src/moduleC src\n src/moduleB src\n src/moduleA/foo.c src/moduleA\n src/moduleA/bar.c src/moduleA\n\nWhen src/moduleA is popped off, we need to know that the \"last\ndirectory\" reverts back to src, and how many entries in our string_list\nare associated with that parent directory. So I use an auxiliary\noffsets string_list which would have (parent_directory,offset)\ninformation of the form\n \"\" 0\n src 2\n src/moduleA 5\n\nWhenever I write out a tree for a subdirectory, I set versions.nr to\nthe final offset value and then decrement offsets.nr...and then add\nan entry to versions with a hash for the new directory.\n\nThe idea is relatively simple, there's just a lot of accounting to\nimplement this.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 106 insertions(+), 7 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex ad34800705..ac58fa6f04 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -354,6 +354,9 @@ static int string_list_df_name_compare(const char *one, const char *two)\n \n struct directory_versions {\n \tstruct string_list versions;\n+\tstruct string_list offsets;\n+\tconst char *last_directory;\n+\tunsigned last_directory_len;\n };\n \n static void write_tree(struct object_id *result_oid,\n@@ -410,12 +413,100 @@ static void record_entry_for_tree(struct directory_versions *dir_metadata,\n \t\t/* nothing to record */\n \t\treturn;\n \n+\t/*\n+\t * Note: write_completed_directories() already added\n+\t * entries for directories to dir_metadata->versions,\n+\t * so no need to handle ci->filemask == 0 again.\n+\t */\n+\tif (!ci->merged.clean && !ci->filemask)\n+\t\treturn;\n+\n \tbasename = path + ci->merged.basename_offset;\n \tassert(strchr(basename, '/') == NULL);\n \tstring_list_append(&dir_metadata->versions,\n \t\t\t basename)->util = &ci->merged.result;\n }\n \n+static void write_completed_directories(struct merge_options *opt,\n+\t\t\t\t\tconst char *new_directory_name,\n+\t\t\t\t\tstruct directory_versions *info)\n+{\n+\tconst char *prev_dir;\n+\tstruct merged_info *dir_info = NULL;\n+\tunsigned int offset;\n+\tint wrote_a_new_tree = 0;\n+\n+\tif (new_directory_name == info->last_directory)\n+\t\treturn;\n+\n+\t/*\n+\t * If we are just starting (last_directory is NULL), or last_directory\n+\t * is a prefix of the current directory, then we can just update\n+\t * last_directory and record the offset where we started this directory.\n+\t */\n+\tif (info->last_directory == NULL ||\n+\t !strncmp(new_directory_name, info->last_directory,\n+\t\t info->last_directory_len)) {\n+\t\tuintptr_t offset = info->versions.nr;\n+\n+\t\tinfo->last_directory = new_directory_name;\n+\t\tinfo->last_directory_len = strlen(info->last_directory);\n+\t\tstring_list_append(&info->offsets,\n+\t\t\t\t info->last_directory)->util = (void*)offset;\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * At this point, ne (next entry) is within a different directory\n+\t * than the last entry, so we need to create a tree object for all\n+\t * the entires in info->versions that are under info->last_directory.\n+\t */\n+\tdir_info = strmap_get(&opt->priv->paths, info->last_directory);\n+\tassert(dir_info);\n+\toffset = (uintptr_t)info->offsets.items[info->offsets.nr-1].util;\n+\tif (offset == info->versions.nr) {\n+\t\tdir_info->is_null = 1;\n+\t} else {\n+\t\tdir_info->result.mode = S_IFDIR;\n+\t\twrite_tree(&dir_info->result.oid, &info->versions, offset);\n+\t\twrote_a_new_tree = 1;\n+\t}\n+\n+\t/*\n+\t * We've now used several entries from info->versions and one entry\n+\t * from info->offsets, so we get rid of those values.\n+\t */\n+\tinfo->offsets.nr--;\n+\tinfo->versions.nr = offset;\n+\n+\t/*\n+\t * Now we've got an OID for last_directory in dir_info. We need to\n+\t * add it to info->versions for it to be part of the computation of\n+\t * its parent directories' OID. But first, we have to find out what\n+\t * its' parent name was and whether that matches the previous\n+\t * info->offsets or we need to set up a new one.\n+\t */\n+\tprev_dir = info->offsets.nr == 0 ? NULL :\n+\t\t info->offsets.items[info->offsets.nr-1].string;\n+\tif (new_directory_name != prev_dir) {\n+\t\tuintptr_t c = info->versions.nr;\n+\t\tstring_list_append(&info->offsets,\n+\t\t\t\t new_directory_name)->util = (void*)c;\n+\t}\n+\n+\t/*\n+\t * Okay, finally record OID for last_directory in info->versions,\n+\t * and update last_directory.\n+\t */\n+\tif (wrote_a_new_tree) {\n+\t\tconst char *dir_name = strrchr(info->last_directory, '/');\n+\t\tdir_name = dir_name ? dir_name+1 : info->last_directory;\n+\t\tstring_list_append(&info->versions, dir_name)->util = dir_info;\n+\t}\n+\tinfo->last_directory = new_directory_name;\n+\tinfo->last_directory_len = strlen(info->last_directory);\n+}\n+\n /* Per entry merge function */\n static void process_entry(struct merge_options *opt,\n \t\t\t const char *path,\n@@ -529,6 +620,9 @@ static void process_entries(struct merge_options *opt,\n \n \t/* other setup */\n \tstring_list_init(&dir_metadata.versions, 0);\n+\tstring_list_init(&dir_metadata.offsets, 0);\n+\tdir_metadata.last_directory = NULL;\n+\tdir_metadata.last_directory_len = 0;\n \n \t/*\n \t * Iterate over the items in reverse order, so we can handle paths\n@@ -542,22 +636,27 @@ static void process_entries(struct merge_options *opt,\n \t\t */\n \t\tstruct conflict_info *ci = entry->util;\n \n+\t\twrite_completed_directories(opt, ci->merged.directory_name,\n+\t\t\t\t\t &dir_metadata);\n \t\tif (ci->merged.clean)\n \t\t\trecord_entry_for_tree(&dir_metadata, path, ci);\n \t\telse\n \t\t\tprocess_entry(opt, path, ci, &dir_metadata);\n \t}\n \n-\t/*\n-\t * TODO: We can't actually write a tree yet, because dir_metadata just\n-\t * contains all basenames of all files throughout the tree with their\n-\t * mode and hash. Not only is that a nonsensical tree, it will have\n-\t * lots of duplicates for paths such as \"Makefile\" or \".gitignore\".\n-\t */\n-\tdie(\"Not yet implemented; need to process subtrees separately\");\n+\tif (dir_metadata.offsets.nr != 1 ||\n+\t (uintptr_t)dir_metadata.offsets.items[0].util != 0) {\n+\t\tprintf(\"dir_metadata.offsets.nr = %d (should be 1)\\n\",\n+\t\t dir_metadata.offsets.nr);\n+\t\tprintf(\"dir_metadata.offsets.items[0].util = %u (should be 0)\\n\",\n+\t\t (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);\n+\t\tfflush(stdout);\n+\t\tBUG(\"dir_metadata accounting completely off; shouldn't happen\");\n+\t}\n \twrite_tree(result_oid, &dir_metadata.versions, 0);\n \tstring_list_clear(&plist, 0);\n \tstring_list_clear(&dir_metadata.versions, 0);\n+\tstring_list_clear(&dir_metadata.offsets, 0);\n }\n \n void merge_switch_to_result(struct merge_options *opt,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408707","messageId":"20201030034131.1479968-21-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 20/20] merge-ort: free data structures in merge_finalize()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:31Z","receivedAt":"2020-10-30T03:42:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Signed-off-by: Elijah Newren \n---\n merge-ort.c | 24 +++++++++++++++++++++++-\n 1 file changed, 23 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 0b091c86eb..9cd1845c37 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -840,7 +840,29 @@ void merge_switch_to_result(struct merge_options *opt,\n void merge_finalize(struct merge_options *opt,\n \t\t struct merge_result *result)\n {\n-\tdie(\"Not yet implemented\");\n+\tstruct merge_options_internal *opti = result->priv;\n+\n+\tassert(opt->priv == NULL);\n+\n+\t/*\n+\t * We marked opti->paths with strdup_strings = 0, so that we\n+\t * wouldn't have to make another copy of the fullpath created by\n+\t * make_traverse_path from setup_path_info(). But, now that we've\n+\t * used it and have no other references to these strings, it is time\n+\t * to deallocate them, which we do by just setting strdup_string = 1\n+\t * before the strmaps are cleared.\n+\t */\n+\topti->paths.strdup_strings = 1;\n+\tstrmap_clear(&opti->paths, 1);\n+\n+\t/*\n+\t * All strings and util fields in opti->unmerged are a subset\n+\t * of those in opti->paths. We don't want to deallocate\n+\t * anything twice, so we don't set strdup_strings and we pass 0 for\n+\t * free_util.\n+\t */\n+\tstrmap_clear(&opti->unmerged, 0);\n+\tFREE_AND_NULL(opti);\n }\n \n static void merge_start(struct merge_options *opt, struct merge_result *result)\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408706","messageId":"20201030034131.1479968-20-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 19/20] merge-ort: add implementation of record_unmerged_index_entries()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:30Z","receivedAt":"2020-10-30T03:42:54Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"After checkout(), the working tree has the appropriate contents, and the\nindex matches the working copy. That means that all unmodified and\ncleanly merged files have correct index entries, but unmerged entries\nneed to be updated.\n\nWe do this by looping over the unmerged entries, marking the existing\nindex entry for the path with CE_REMOVE, adding new higher order staged\nfor the path at the end of the index (ignoring normal index sort order),\nand then at the end of the loop removing the CE_REMOVED-marked cache\nentries and sorting the index.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 86 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 4da671d647..0b091c86eb 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,6 +17,7 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"cache-tree.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"dir.h\"\n@@ -714,10 +715,94 @@ static int record_unmerged_index_entries(struct merge_options *opt,\n \t\t\t\t\t struct strmap *paths,\n \t\t\t\t\t struct strmap *unmerged)\n {\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *e;\n+\tint errs = 0;\n+\tint original_cache_nr;\n+\n \tif (strmap_empty(unmerged))\n \t\treturn 0;\n \n-\tdie(\"Not yet implemented.\");\n+\toriginal_cache_nr = index->cache_nr;\n+\n+\t/* Put every entry from paths into plist, then sort */\n+\tstrmap_for_each_entry(unmerged, &iter, e) {\n+\t\tconst char *path = e->key;\n+\t\tstruct conflict_info *ci = e->value;\n+\t\tint pos;\n+\t\tstruct cache_entry *ce;\n+\t\tint i;\n+\n+\t\t/*\n+\t\t * The index will already have a stage=0 entry for this path,\n+\t\t * because we created an as-merged-as-possible version of the\n+\t\t * file and checkout() moved the working copy and index over\n+\t\t * to that version.\n+\t\t *\n+\t\t * However, previous iterations through this loop will have\n+\t\t * added unstaged entries to the end of the cache which\n+\t\t * ignore the standard alphabetical ordering of cache\n+\t\t * entries and break invariants needed for index_name_pos()\n+\t\t * to work. However, we know the entry we want is before\n+\t\t * those appended cache entries, so do a temporary swap on\n+\t\t * cache_nr to only look through entries of interest.\n+\t\t */\n+\t\tSWAP(index->cache_nr, original_cache_nr);\n+\t\tpos = index_name_pos(index, path, strlen(path));\n+\t\tSWAP(index->cache_nr, original_cache_nr);\n+\t\tif (pos < 0) {\n+\t\t\tif (ci->filemask == 1)\n+\t\t\t\tcache_tree_invalidate_path(index, path);\n+\t\t\telse\n+\t\t\t\tBUG(\"Unmerged %s but nothing in basic working tree or index; this shouldn't happen\", path);\n+\t\t} else {\n+\t\t\tce = index->cache[pos];\n+\n+\t\t\t/*\n+\t\t\t * Clean paths with CE_SKIP_WORKTREE set will not be\n+\t\t\t * written to the working tree by the unpack_trees()\n+\t\t\t * call in checkout(). Our unmerged entries would\n+\t\t\t * have appeared clean to that code since we ignored\n+\t\t\t * the higher order stages. Thus, we need override\n+\t\t\t * the CE_SKIP_WORKTREE bit and manually write those\n+\t\t\t * files to the working disk here.\n+\t\t\t *\n+\t\t\t * TODO: Implement this CE_SKIP_WORKTREE fixup.\n+\t\t\t */\n+\n+\t\t\t/*\n+\t\t\t * Mark this cache entry for removal and instead add\n+\t\t\t * new stage>0 entries corresponding to the\n+\t\t\t * conflicts. If there are many unmerged entries, we\n+\t\t\t * want to avoid memmove'ing O(NM) entries by\n+\t\t\t * inserting the new entries one at a time. So,\n+\t\t\t * instead, we just add the new cache entries to the\n+\t\t\t * end (ignoring normal index requirements on sort\n+\t\t\t * order) and sort the index once we're all done.\n+\t\t\t */\n+\t\t\tce->ce_flags |= CE_REMOVE;\n+\t\t}\n+\n+\t\tfor (i = 0; i < 3; i++) {\n+\t\t\tstruct version_info *vi;\n+\t\t\tif (!(ci->filemask & (1ul << i)))\n+\t\t\t\tcontinue;\n+\t\t\tvi = &ci->stages[i];\n+\t\t\tce = make_cache_entry(index, vi->mode, &vi->oid,\n+\t\t\t\t\t path, i+1, 0);\n+\t\t\tadd_index_entry(index, ce, ADD_CACHE_JUST_APPEND);\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * Remove the unused cache entries (and invalidate the relevant\n+\t * cache-trees), then sort the index entries to get the unmerged\n+\t * entries we added to the end into their right locations.\n+\t */\n+\tremove_marked_cache_entries(index, 1);\n+\tQSORT(index->cache, index->cache_nr, cmp_cache_name_compare);\n+\n+\treturn errs;\n }\n \n void merge_switch_to_result(struct merge_options *opt,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408708","messageId":"20201030034131.1479968-19-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 18/20] tree: enable cmp_cache_name_compare() to be used elsewhere","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:29Z","receivedAt":"2020-10-30T03:42:55Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Signed-off-by: Elijah Newren \n---\n tree.c | 2 +-\n tree.h | 2 ++\n 2 files changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/tree.c b/tree.c\nindex e76517f6b1..a52479812c 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -144,7 +144,7 @@ int read_tree_recursive(struct repository *r,\n \treturn ret;\n }\n \n-static int cmp_cache_name_compare(const void *a_, const void *b_)\n+int cmp_cache_name_compare(const void *a_, const void *b_)\n {\n \tconst struct cache_entry *ce1, *ce2;\n \ndiff --git a/tree.h b/tree.h\nindex 9383745073..3eb0484cbf 100644\n--- a/tree.h\n+++ b/tree.h\n@@ -28,6 +28,8 @@ void free_tree_buffer(struct tree *tree);\n /* Parses and returns the tree in the given ent, chasing tags and commits. */\n struct tree *parse_tree_indirect(const struct object_id *oid);\n \n+int cmp_cache_name_compare(const void *a_, const void *b_);\n+\n #define READ_TREE_RECURSIVE 1\n typedef int (*read_tree_fn_t)(const struct object_id *, struct strbuf *, const char *, unsigned int, int, void *);\n \n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408709","messageId":"20201030034131.1479968-18-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 17/20] merge-ort: add implementation of checkout()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:28Z","receivedAt":"2020-10-30T03:42:56Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Since merge-ort creates a tree for its output, when there are no\nconflicts, updating the working tree and index is as simple as using the\nunpack_trees() machinery with a twoway_merge (i.e. doing the equivalent\nof a \"checkout\" operation).\n\nIf there were conflicts in the merge, then since the tree we created\nincluded all the conflict markers, then using the unpack_trees machinery\nin this manner will still update the working tree correctly. Further,\nall index entries corresponding to cleanly merged files will also be\nupdated correctly by this procedure. Index entries corresponding to\nunmerged entries will appear as though the user had run \"git add -u\"\nafter the merge to accept all files as-is with conflict markers.\n\nThus, after running unpack_trees(), there needs to be a separate step\nfor updating the entries in the index corresponding to unmerged files.\nThis will be the job for the function record_unmerged_index_entries(),\nwhich will be implemented in a subsequent commit.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 45 ++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 44 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex a5b97adfc4..4da671d647 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -19,9 +19,11 @@\n \n #include \"diff.h\"\n #include \"diffcore.h\"\n+#include \"dir.h\"\n #include \"object-store.h\"\n #include \"strmap.h\"\n #include \"tree.h\"\n+#include \"unpack-trees.h\"\n #include \"xdiff-interface.h\"\n \n struct merge_options_internal {\n@@ -663,7 +665,48 @@ static int checkout(struct merge_options *opt,\n \t\t struct tree *prev,\n \t\t struct tree *next)\n {\n-\tdie(\"Not yet implemented.\");\n+\t/* Switch the index/working copy from old to new */\n+\tint ret;\n+\tstruct tree_desc trees[2];\n+\tstruct unpack_trees_options unpack_opts;\n+\n+\tmemset(&unpack_opts, 0, sizeof(unpack_opts));\n+\tunpack_opts.head_idx = -1;\n+\tunpack_opts.src_index = opt->repo->index;\n+\tunpack_opts.dst_index = opt->repo->index;\n+\n+\tsetup_unpack_trees_porcelain(&unpack_opts, \"merge\");\n+\n+\t/*\n+\t * NOTE: if this were just \"git checkout\" code, we would probably\n+\t * read or refresh the cache and check for an unmerged index, but\n+\t * builtin/merge.c or sequencer.c really needs to read the index\n+\t * and check for unmerged entries before starting merging for a\n+\t * good user experience (no sense waiting for merges/rebases before\n+\t * erroring out), so there's no reason to duplicate that work here.\n+\t */\n+\n+\t/* 2-way merge to the new branch */\n+\tunpack_opts.update = 1;\n+\tunpack_opts.merge = 1;\n+\tunpack_opts.quiet = 0; /* FIXME: sequencer might want quiet? */\n+\tunpack_opts.verbose_update = (opt->verbosity > 2);\n+\tunpack_opts.fn = twoway_merge;\n+\tif (1/* FIXME: opts->overwrite_ignore*/) {\n+\t\tunpack_opts.dir = xcalloc(1, sizeof(*unpack_opts.dir));\n+\t\tunpack_opts.dir->flags |= DIR_SHOW_IGNORED;\n+\t\tsetup_standard_excludes(unpack_opts.dir);\n+\t}\n+\tparse_tree(prev);\n+\tinit_tree_desc(&trees[0], prev->buffer, prev->size);\n+\tparse_tree(next);\n+\tinit_tree_desc(&trees[1], next->buffer, next->size);\n+\n+\tret = unpack_trees(2, trees, &unpack_opts);\n+\tclear_unpack_trees_porcelain(&unpack_opts);\n+\tdir_clear(unpack_opts.dir);\n+\tFREE_AND_NULL(unpack_opts.dir);\n+\treturn ret;\n }\n \n static int record_unmerged_index_entries(struct merge_options *opt,\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408710","messageId":"20201030034131.1479968-17-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 16/20] merge-ort: basic outline for merge_switch_to_result()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:27Z","receivedAt":"2020-10-30T03:42:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This adds a basic implementation for merge_switch_to_result(), though\njust in terms of a few new empty functions that will be defined in\nsubsequent commits.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 42 +++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 41 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex ac58fa6f04..a5b97adfc4 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -659,13 +659,53 @@ static void process_entries(struct merge_options *opt,\n \tstring_list_clear(&dir_metadata.offsets, 0);\n }\n \n+static int checkout(struct merge_options *opt,\n+\t\t struct tree *prev,\n+\t\t struct tree *next)\n+{\n+\tdie(\"Not yet implemented.\");\n+}\n+\n+static int record_unmerged_index_entries(struct merge_options *opt,\n+\t\t\t\t\t struct index_state *index,\n+\t\t\t\t\t struct strmap *paths,\n+\t\t\t\t\t struct strmap *unmerged)\n+{\n+\tif (strmap_empty(unmerged))\n+\t\treturn 0;\n+\n+\tdie(\"Not yet implemented.\");\n+}\n+\n void merge_switch_to_result(struct merge_options *opt,\n \t\t\t struct tree *head,\n \t\t\t struct merge_result *result,\n \t\t\t int update_worktree_and_index,\n \t\t\t int display_update_msgs)\n {\n-\tdie(\"Not yet implemented\");\n+\tassert(opt->priv == NULL);\n+\tif (result->clean >= 0 && update_worktree_and_index) {\n+\t\tstruct merge_options_internal *opti = result->priv;\n+\n+\t\tif (checkout(opt, head, result->tree)) {\n+\t\t\t/* failure to function */\n+\t\t\tresult->clean = -1;\n+\t\t\treturn;\n+\t\t}\n+\n+\t\tif (record_unmerged_index_entries(opt, opt->repo->index,\n+\t\t\t\t\t\t &opti->paths,\n+\t\t\t\t\t\t &opti->unmerged)) {\n+\t\t\t/* failure to function */\n+\t\t\tresult->clean = -1;\n+\t\t\treturn;\n+\t\t}\n+\t}\n+\n+\tif (display_update_msgs) {\n+\t\t/* TODO: print out CONFLICT and other informational messages. */\n+\t}\n+\n \tmerge_finalize(opt, result);\n }\n \n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408711","messageId":"20201030034131.1479968-6-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 05/20] merge-ort: add an err() function similar to one from merge-recursive","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:16Z","receivedAt":"2020-10-30T03:42:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Various places in merge-recursive used an err() function when it hit\nsome kind of unrecoverable error. That code was from the reusable bits\nof merge-recursive.c that we liked, such as merge_3way, writing object\nfiles to the object store, reading blobs from the object store, etc. So\ncreate a similar function to allow us to port that code over, and use it\nfor when we detect problems returned from collect_merge_info()'s\ntraverse_trees() call, which we will be adding next.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 27 ++++++++++++++++++++++++++-\n 1 file changed, 26 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex e629d7b62c..ffea7ac8ea 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -61,11 +61,28 @@ struct conflict_info {\n \tunsigned match_mask:3;\n };\n \n+static int err(struct merge_options *opt, const char *err, ...)\n+{\n+\tva_list params;\n+\tstruct strbuf sb = STRBUF_INIT;\n+\n+\tstrbuf_addstr(&sb, \"error: \");\n+\tva_start(params, err);\n+\tstrbuf_vaddf(&sb, err, params);\n+\tva_end(params);\n+\n+\terror(\"%s\", sb.buf);\n+\tstrbuf_release(&sb);\n+\n+\treturn -1;\n+}\n+\n static int collect_merge_info(struct merge_options *opt,\n \t\t\t struct tree *merge_base,\n \t\t\t struct tree *side1,\n \t\t\t struct tree *side2)\n {\n+\t/* TODO: Implement this using traverse_trees() */\n \tdie(\"Not yet implemented.\");\n }\n \n@@ -167,7 +184,15 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n {\n \tstruct object_id working_tree_oid;\n \n-\tcollect_merge_info(opt, merge_base, side1, side2);\n+\tif (collect_merge_info(opt, merge_base, side1, side2) != 0) {\n+\t\terr(opt, _(\"collecting merge info failed for trees %s, %s, %s\"),\n+\t\t oid_to_hex(&merge_base->object.oid),\n+\t\t oid_to_hex(&side1->object.oid),\n+\t\t oid_to_hex(&side2->object.oid));\n+\t\tresult->clean = -1;\n+\t\treturn;\n+\t}\n+\n \tresult->clean = detect_and_process_renames(opt, merge_base,\n \t\t\t\t\t\t side1, side2);\n \tprocess_entries(opt, &working_tree_oid);\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408712","messageId":"20201030034131.1479968-10-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 09/20] merge-ort: record stage and auxiliary info for every path","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:20Z","receivedAt":"2020-10-30T03:43:00Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Create a helper function, setup_path_info(), which can be used to record\nall the information we want in a merged_info or conflict_info. While\nthere is currently only one caller of this new function, and some of its\nparticular parameters are fixed, future callers of this function will be\nadded later.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 54 insertions(+), 7 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 86d9b87cb9..60e2b78e2d 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -77,6 +77,50 @@ static int err(struct merge_options *opt, const char *err, ...)\n \treturn -1;\n }\n \n+static void setup_path_info(struct merge_options *opt,\n+\t\t\t struct string_list_item *result,\n+\t\t\t const char *current_dir_name,\n+\t\t\t int current_dir_name_len,\n+\t\t\t char *fullpath, /* we'll take over ownership */\n+\t\t\t struct name_entry *names,\n+\t\t\t struct name_entry *merged_version,\n+\t\t\t unsigned is_null, /* boolean */\n+\t\t\t unsigned df_conflict, /* boolean */\n+\t\t\t unsigned filemask,\n+\t\t\t unsigned dirmask,\n+\t\t\t int resolved /* boolean */)\n+{\n+\tstruct conflict_info *path_info;\n+\n+\tassert(!is_null || resolved);\n+\tassert(!df_conflict || !resolved); /* df_conflict implies !resolved */\n+\tassert(resolved == (merged_version != NULL));\n+\n+\tpath_info = xcalloc(1, resolved ? sizeof(struct merged_info) :\n+\t\t\t\t\t sizeof(struct conflict_info));\n+\tpath_info->merged.directory_name = current_dir_name;\n+\tpath_info->merged.basename_offset = current_dir_name_len;\n+\tpath_info->merged.clean = !!resolved;\n+\tif (resolved) {\n+\t\tpath_info->merged.result.mode = merged_version->mode;\n+\t\toidcpy(&path_info->merged.result.oid, &merged_version->oid);\n+\t\tpath_info->merged.is_null = !!is_null;\n+\t} else {\n+\t\tint i;\n+\n+\t\tfor (i = 0; i < 3; i++) {\n+\t\t\tpath_info->pathnames[i] = fullpath;\n+\t\t\tpath_info->stages[i].mode = names[i].mode;\n+\t\t\toidcpy(&path_info->stages[i].oid, &names[i].oid);\n+\t\t}\n+\t\tpath_info->filemask = filemask;\n+\t\tpath_info->dirmask = dirmask;\n+\t\tpath_info->df_conflict = !!df_conflict;\n+\t}\n+\tresult->string = fullpath;\n+\tresult->util = path_info;\n+}\n+\n static int collect_merge_info_callback(int n,\n \t\t\t\t unsigned long mask,\n \t\t\t\t unsigned long dirmask,\n@@ -91,10 +135,12 @@ static int collect_merge_info_callback(int n,\n \t */\n \tstruct merge_options *opt = info->data;\n \tstruct merge_options_internal *opti = opt->priv;\n-\tstruct conflict_info *ci;\n+\tstruct string_list_item pi; /* Path Info */\n+\tstruct conflict_info *ci; /* pi.util when there's a conflict */\n \tstruct name_entry *p;\n \tsize_t len;\n \tchar *fullpath;\n+\tconst char *dirname = opti->current_dir_name;\n \tunsigned filemask = mask & ~dirmask;\n \tunsigned match_mask = 0; /* will be updated below */\n \tunsigned mbase_null = !(mask & 1);\n@@ -157,13 +203,14 @@ static int collect_merge_info_callback(int n,\n \tmake_traverse_path(fullpath, len+1, info, p->path, p->pathlen);\n \n \t/*\n-\t * TODO: record information about the path other than all zeros,\n-\t * so we can resolve later in process_entries.\n+\t * Record information about the path so we can resolve later in\n+\t * process_entries.\n \t */\n-\tci = xcalloc(1, sizeof(struct conflict_info));\n-\tci->df_conflict = df_conflict;\n+\tsetup_path_info(opt, &pi, dirname, info->pathlen, fullpath,\n+\t\t\tnames, NULL, 0, df_conflict, filemask, dirmask, 0);\n+\tci = pi.util;\n \tci->match_mask = match_mask;\n-\tstrmap_put(&opti->paths, fullpath, ci);\n+\tstrmap_put(&opti->paths, pi.string, pi.util);\n \n \t/* If dirmask, recurse into subdirectories */\n \tif (dirmask) {\n@@ -204,7 +251,7 @@ static int collect_merge_info_callback(int n,\n \t\t}\n \n \t\toriginal_dir_name = opti->current_dir_name;\n-\t\topti->current_dir_name = fullpath;\n+\t\topti->current_dir_name = pi.string;\n \t\tret = traverse_trees(NULL, 3, t, &newinfo);\n \t\topti->current_dir_name = original_dir_name;\n \n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408713","messageId":"20201030034131.1479968-4-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 03/20] merge-ort: port merge_start() from merge-recursive","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:14Z","receivedAt":"2020-10-30T03:43:01Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"merge_start() basically does a bunch of sanity checks, then allocates\nand initializes opt->priv -- a struct merge_options_internal.\n\nMost the sanity checks are usable as-is. The allocation/intialization\nis a bit different since merge-ort has a very different\nmerge_options_internal than merge-recursive, but the idea is the same.\n\nThe weirdest part here is that merge-ort and merge-recursive use the\nsame struct merge_options, even though merge_options has a number of\nfields that are oddly specific to merge-recursive's internal\nimplementation and don't even make sense with merge-ort's high-level\ndesign (e.g. buffer_output, which merge-ort has to always do). I reused\nthe same data structure because:\n * most the fields made sense to both merge algorithms\n * making a new struct would have required making new enums or somehow\n externalizing them, and that was getting messy.\n * it simplifies converting the existing callers by not having to\n have different code paths for merge_options setup.\n\nI also marked detect_renames as ignored. We can revisit that later, but\nin short: merge-recursive allowed turning off rename detection because\nit was sometimes glacially slow. When you speed something up by a few\norders of magnitude, it's worth revisiting whether that justification is\nstill relevant. Besides, if folks find it's still too slow, perhaps\nthey have a better scaling case than I could find and maybe it turns up\nsome more optimizations we can add. If it still is needed as an option,\nit is easy to add later.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 44 +++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 43 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b53cd80104..bee9507319 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -17,6 +17,8 @@\n #include \"cache.h\"\n #include \"merge-ort.h\"\n \n+#include \"diff.h\"\n+#include \"diffcore.h\"\n #include \"strmap.h\"\n #include \"tree.h\"\n \n@@ -107,7 +109,47 @@ void merge_finalize(struct merge_options *opt,\n \n static void merge_start(struct merge_options *opt, struct merge_result *result)\n {\n-\tdie(\"Not yet implemented.\");\n+\t/* Sanity checks on opt */\n+\tassert(opt->repo);\n+\n+\tassert(opt->branch1 && opt->branch2);\n+\n+\tassert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&\n+\t opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);\n+\tassert(opt->rename_limit >= -1);\n+\tassert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);\n+\tassert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);\n+\n+\tassert(opt->xdl_opts >= 0);\n+\tassert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&\n+\t opt->recursive_variant <= MERGE_VARIANT_THEIRS);\n+\n+\t/*\n+\t * detect_renames, verbosity, buffer_output, and obuf are ignored\n+\t * fields that were used by \"recursive\" rather than \"ort\" -- but\n+\t * sanity check them anyway.\n+\t */\n+\tassert(opt->detect_renames >= -1 &&\n+\t opt->detect_renames <= DIFF_DETECT_COPY);\n+\tassert(opt->verbosity >= 0 && opt->verbosity <= 5);\n+\tassert(opt->buffer_output <= 2);\n+\tassert(opt->obuf.len == 0);\n+\n+\tassert(opt->priv == NULL);\n+\n+\t/* Initialization of opt->priv, our internal merge data */\n+\topt->priv = xcalloc(1, sizeof(*opt->priv));\n+\t/*\n+\t * Although we initialize opt->priv->paths with strdup_strings=0,\n+\t * that's just to avoid making yet another copy of an allocated\n+\t * string. Putting the entry into paths means we are taking\n+\t * ownership, so we will later free it.\n+\t *\n+\t * In contrast, unmerged just has a subset of keys from paths, so\n+\t * we don't want to free those (it'd be a duplicate free).\n+\t */\n+\tstrmap_ocd_init(&opt->priv->paths, NULL, 0);\n+\tstrmap_ocd_init(&opt->priv->unmerged, NULL, 0);\n }\n \n /*\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408714","messageId":"20201030034131.1479968-9-newren@gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"[PATCH 08/20] merge-ort: compute a few more useful fields for collect_merge_info","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:41:19Z","receivedAt":"2020-10-30T03:43:02Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Signed-off-by: Elijah Newren \n---\n merge-ort.c | 25 +++++++++++++++++++++++++\n 1 file changed, 25 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 7083388a47..86d9b87cb9 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -96,6 +96,7 @@ static int collect_merge_info_callback(int n,\n \tsize_t len;\n \tchar *fullpath;\n \tunsigned filemask = mask & ~dirmask;\n+\tunsigned match_mask = 0; /* will be updated below */\n \tunsigned mbase_null = !(mask & 1);\n \tunsigned side1_null = !(mask & 2);\n \tunsigned side2_null = !(mask & 4);\n@@ -108,6 +109,13 @@ static int collect_merge_info_callback(int n,\n \tunsigned sides_match = (!side1_null && !side2_null &&\n \t\t\t\tnames[1].mode == names[2].mode &&\n \t\t\t\toideq(&names[1].oid, &names[2].oid));\n+\t/*\n+\t * Note: We only label files with df_conflict, not directories.\n+\t * Since directories stay where they are, and files move out of the\n+\t * way to make room for a directory, we don't care if there was a\n+\t * directory/file conflict for a parent directory of the current path.\n+\t */\n+\tunsigned df_conflict = (filemask != 0) && (dirmask != 0);\n \n \t/* n = 3 is a fundamental assumption. */\n \tif (n != 3)\n@@ -127,6 +135,14 @@ static int collect_merge_info_callback(int n,\n \t/* Other invariant checks, mostly for documentation purposes. */\n \tassert(mask == (dirmask | filemask));\n \n+\t/* Determine match_mask */\n+\tif (side1_matches_mbase)\n+\t\tmatch_mask = (side2_matches_mbase ? 7 : 3);\n+\telse if (side2_matches_mbase)\n+\t\tmatch_mask = 5;\n+\telse if (sides_match)\n+\t\tmatch_mask = 6;\n+\n \t/*\n \t * Get the name of the relevant filepath, which we'll pass to\n \t * setup_path_info() for tracking.\n@@ -145,6 +161,8 @@ static int collect_merge_info_callback(int n,\n \t * so we can resolve later in process_entries.\n \t */\n \tci = xcalloc(1, sizeof(struct conflict_info));\n+\tci->df_conflict = df_conflict;\n+\tci->match_mask = match_mask;\n \tstrmap_put(&opti->paths, fullpath, ci);\n \n \t/* If dirmask, recurse into subdirectories */\n@@ -161,6 +179,13 @@ static int collect_merge_info_callback(int n,\n \t\tnewinfo.name = p->path;\n \t\tnewinfo.namelen = p->pathlen;\n \t\tnewinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);\n+\t\t/*\n+\t\t * If we did care about parent directories having a D/F\n+\t\t * conflict, then we'd include\n+\t\t * newinfo.df_conflicts |= (mask & ~dirmask);\n+\t\t * here. But we don't. (See comment near setting of local\n+\t\t * df_conflict variable near the beginning of this function).\n+\t\t */\n \n \t\tfor (i = 0; i < 3; i++, dirmask >>= 1) {\n \t\t\tif (i == 1 && side1_matches_mbase)\n-- \n2.29.1.56.ga287c268e6.dirty\n\n"},{"id":"408716","messageId":"CABPp-BHKGkx04neULtYUyfiU+z-X7_rxQqriSEjxZjU1oXokOA@mail.gmail.com","threadId":"54533","inReplyTo":"20201030034131.1479968-1-newren@gmail.com","subject":"Re: [PATCH 00/20] fundamentals of merge-ort implementation","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-10-30T03:58:01Z","receivedAt":"2020-10-30T03:58:14Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Oct 29, 2020 at 8:41 PM Elijah Newren wrote:\n>\n> ...\n> The goal of this series is to show the new design and structure behind\n> merge-ort, particularly the bits that are completely different to how\n> merge-recursive operates....\n>\n> At a high level, merge-ort avoids unpack_trees() and the index, instead\n> using traverse_trees() and its own data structure. After it is done\n> processing each path, it writes a tree. Only after it has created a new\n> tree will it touch the working copy or the index. It does so by using a\n> simple checkout-like step to switch from head to the newly created tree.\n> If there are unmerged entries, it touches up the index after the\n> checkout-like step to record those higher order stages.\n\nWhile I didn't think anyone needed to be cc'ed on the whole series,\nbut I made some promises at Git Merge 2020 to give some heads up:\n\n* Brian: Patches 13-15 create tree objects, joining other places in\nthe code such as fast-import, mktree, cache-tree, and notes that write\ntree objects. You mentioned something about consolidating these for\nsha256 handling.\n* Edward: You wanted a heads up when I started submitting the ort\nmerge backend. Here it is. It doesn't change any on-disk data\nstructures now or later, though, so I'm not sure libgit2 really is\naffected.\n* Peff: This isn't a Git Merge 2020 thing, but here's a series that\nstarts depending on strmap. I'm happy to update and rebase if needed,\nbut opinions on strmap to prevent us from any API poisoning and such\nwould be great. :-)\n\nElijah\n\n> In the series:\n> * Patch 1 adds some basic data structures.\n> * Patch 2 documents the high-level steps.\n> * Patches 3-5 are some simple setup.\n> * Patches 6-10 collect data from the traverse_trees() operation.\n> * Patches 11-15 process the individual paths and create a tree.\n> * Patches 16-19 handle checkout-and-then-write-higher-order-stages.\n> * Patch 20 frees data from the merge_options_internal data structure\n>\n> Elijah Newren (20):\n> merge-ort: setup basic internal data structures\n> merge-ort: add some high-level algorithm structure\n> merge-ort: port merge_start() from merge-recursive\n> merge-ort: use histogram diff\n> merge-ort: add an err() function similar to one from merge-recursive\n> merge-ort: implement a very basic collect_merge_info()\n> merge-ort: avoid repeating fill_tree_descriptor() on the same tree\n> merge-ort: compute a few more useful fields for collect_merge_info\n> merge-ort: record stage and auxiliary info for every path\n> merge-ort: avoid recursing into identical trees\n> merge-ort: add a preliminary simple process_entries() implementation\n> merge-ort: have process_entries operate in a defined order\n> merge-ort: step 1 of tree writing -- record basenames, modes, and oids\n> merge-ort: step 2 of tree writing -- function to create tree object\n> merge-ort: step 3 of tree writing -- handling subdirectories as we go\n> merge-ort: basic outline for merge_switch_to_result()\n> merge-ort: add implementation of checkout()\n> tree: enable cmp_cache_name_compare() to be used elsewhere\n> merge-ort: add implementation of record_unmerged_index_entries()\n> merge-ort: free data structures in merge_finalize()\n>\n> merge-ort.c | 922 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n> tree.c | 2 +-\n> tree.h | 2 +\n> 3 files changed, 922 insertions(+), 4 deletions(-)\n>\n> --\n> 2.29.1.56.ga287c268e6.dirty\n"}]}