Git Mailing List Archive on lore.kernel.org
 help / color / Atom feed
From: "Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: jonathantanmy@google.com, dstolee@microsoft.com,
	"Elijah Newren" <newren@gmail.com>,
	"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
	"Elijah Newren" <newren@gmail.com>
Subject: [PATCH v3 00/20] fundamentals of merge-ort implementation
Date: Sun, 13 Dec 2020 08:04:07 +0000
Message-ID: <pull.923.v3.git.git.1607846667.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.923.v2.git.git.1607114890.gitgitgadget@gmail.com>

This is actually v5 of this series, and is being sent due to review comments
from a different series, namely en/merge-ort-3[1].

I have rerolls of en/merge-ort-2 and en/merge-ort-3 already prepared, but
since gitgitgadget will not allow me to send a series dependent on a
not-published-by-Junio series, I cannot yet send them. You will need to
temporarily drop them, and I'll resend after you publish the updated version
of this series. I do not like this solution, and I was tempted to just push
the updates into en/merge-ort-3, but since this series was still hanging in
'seen' awaiting feedback and a lot of the suggestions were for things from
this series, I decided to go this route anyway...

[1]
https://lore.kernel.org/git/CABPp-BHa0zehQd-axmb4bF6fR4PTWwGu9uLjOzgTW8_Gu12iZA@mail.gmail.com/

Changes since v4:

 * Improved documentation of filemask and dirmask
 * Improved documentation of merge_result.clean
 * Added new enum merge_side and documentation with it to try to make the
   code a bit more self-documenting.

Elijah Newren (20):
  merge-ort: setup basic internal data structures
  merge-ort: add some high-level algorithm structure
  merge-ort: port merge_start() from merge-recursive
  merge-ort: use histogram diff
  merge-ort: add an err() function similar to one from merge-recursive
  merge-ort: implement a very basic collect_merge_info()
  merge-ort: avoid repeating fill_tree_descriptor() on the same tree
  merge-ort: compute a few more useful fields for collect_merge_info
  merge-ort: record stage and auxiliary info for every path
  merge-ort: avoid recursing into identical trees
  merge-ort: add a preliminary simple process_entries() implementation
  merge-ort: have process_entries operate in a defined order
  merge-ort: step 1 of tree writing -- record basenames, modes, and oids
  merge-ort: step 2 of tree writing -- function to create tree object
  merge-ort: step 3 of tree writing -- handling subdirectories as we go
  merge-ort: basic outline for merge_switch_to_result()
  merge-ort: add implementation of checkout()
  tree: enable cmp_cache_name_compare() to be used elsewhere
  merge-ort: add implementation of record_conflicted_index_entries()
  merge-ort: free data structures in merge_finalize()

 merge-ort.c | 1248 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 merge-ort.h |    9 +-
 tree.c      |    2 +-
 tree.h      |    2 +
 4 files changed, 1256 insertions(+), 5 deletions(-)


base-commit: 3cf59784d42c4152a0b3de7bb7a75d0071e5f878
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-923%2Fnewren%2Fort-basics-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-923/newren/ort-basics-v3
Pull-Request: https://github.com/git/git/pull/923

Range-diff vs v2:

  1:  2568ec92c6d !  1:  518dde86966 merge-ort: setup basic internal data structures
     @@ merge-ort.c
      +	unsigned df_conflict:1;
      +
      +	/*
     -+	 * For filemask and dirmask, see tree-walk.h's struct traverse_info,
     -+	 * particularly the documentation above the "fn" member.  Note that
     -+	 * filemask = mask & ~dirmask from that documentation.
     ++	 * For filemask and dirmask, the ith bit corresponds to whether the
     ++	 * ith entry is a file (filemask) or a directory (dirmask).  Thus,
     ++	 * filemask & dirmask is always zero, and filemask | dirmask is at
     ++	 * most 7 but can be less when a path does not appear as either a
     ++	 * file or a directory on at least one side of history.
     ++	 *
     ++	 * Note that these masks are related to enum merge_side, as the ith
     ++	 * entry corresponds to side i.
     ++	 *
     ++	 * These values come from a traverse_trees() call; more info may be
     ++	 * found looking at tree-walk.h's struct traverse_info,
     ++	 * particularly the documentation above the "fn" member (note that
     ++	 * filemask = mask & ~dirmask from that documentation).
      +	 */
      +	unsigned filemask:3;
      +	unsigned dirmask:3;
  2:  b658536f59d =  2:  5827ec7f3eb merge-ort: add some high-level algorithm structure
  3:  acb40f5c165 =  3:  8295591ee13 merge-ort: port merge_start() from merge-recursive
  4:  22fecf6ccd1 =  4:  38b4f9cf78c merge-ort: use histogram diff
  5:  6c4c0c15b3d !  5:  95143bebf09 merge-ort: add an err() function similar to one from merge-recursive
     @@ Commit message
          for when we detect problems returned from collect_merge_info()'s
          traverse_trees() call, which we will be adding next.
      
     +    While we are at it, also add more documentation for the "clean" field
     +    from struct merge_result, particularly since the name suggests a boolean
     +    but it is not quite one and this is our first non-boolean usage.
     +
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## merge-ort.c ##
     @@ merge-ort.c: static void merge_ort_nonrecursive_internal(struct merge_options *o
       	result->clean = detect_and_process_renames(opt, merge_base,
       						   side1, side2);
       	process_entries(opt, &working_tree_oid);
     +
     + ## merge-ort.h ##
     +@@ merge-ort.h: struct commit;
     + struct tree;
     + 
     + struct merge_result {
     +-	/* Whether the merge is clean */
     ++	/*
     ++	 * Whether the merge is clean; possible values:
     ++	 *    1: clean
     ++	 *    0: not clean (merge conflicts)
     ++	 *   <0: operation aborted prematurely.  (object database
     ++	 *       unreadable, disk full, etc.)  Worktree may be left in an
     ++	 *       inconsistent state if operation failed near the end.
     ++	 */
     + 	int clean;
     + 
     + 	/*
  6:  27268ef8a3c !  6:  242f6462ebb merge-ort: implement a very basic collect_merge_info()
     @@ Commit message
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## merge-ort.c ##
     +@@
     + #include "tree.h"
     + #include "xdiff-interface.h"
     + 
     ++/*
     ++ * We have many arrays of size 3.  Whenever we have such an array, the
     ++ * indices refer to one of the sides of the three-way merge.  This is so
     ++ * pervasive that the constants 0, 1, and 2 are used in many places in the
     ++ * code (especially in arithmetic operations to find the other side's index
     ++ * or to compute a relevant mask), but sometimes these enum names are used
     ++ * to aid code clarity.
     ++ *
     ++ * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
     ++ * referred to there is one of these three sides.
     ++ */
     ++enum merge_side {
     ++	MERGE_BASE = 0,
     ++	MERGE_SIDE1 = 1,
     ++	MERGE_SIDE2 = 2
     ++};
     ++
     + struct merge_options_internal {
     + 	/*
     + 	 * paths: primary data structure in all of merge ort.
      @@ merge-ort.c: static int err(struct merge_options *opt, const char *err, ...)
       	return -1;
       }
     @@ merge-ort.c: static int err(struct merge_options *opt, const char *err, ...)
      +		newinfo.namelen = p->pathlen;
      +		newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
      +
     -+		for (i = 0; i < 3; i++) {
     ++		for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
      +			const struct object_id *oid = NULL;
      +			if (dirmask & 1)
      +				oid = &names[i].oid;
     @@ merge-ort.c: static int err(struct merge_options *opt, const char *err, ...)
      +		ret = traverse_trees(NULL, 3, t, &newinfo);
      +		opti->current_dir_name = original_dir_name;
      +
     -+		for (i = 0; i < 3; i++)
     ++		for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
      +			free(buf[i]);
      +
      +		if (ret < 0)
  7:  c6e5621c210 !  7:  c18bdc1b052 merge-ort: avoid repeating fill_tree_descriptor() on the same tree
     @@ merge-ort.c: static int collect_merge_info_callback(int n,
      @@ merge-ort.c: static int collect_merge_info_callback(int n,
       		newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
       
     - 		for (i = 0; i < 3; i++) {
     + 		for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
      -			const struct object_id *oid = NULL;
      -			if (dirmask & 1)
      -				oid = &names[i].oid;
  8:  93fd69fa3c6 !  8:  be5708dc628 merge-ort: compute a few more useful fields for collect_merge_info
     @@ merge-ort.c: static int collect_merge_info_callback(int n,
      +		 * the beginning of this function).
      +		 */
       
     - 		for (i = 0; i < 3; i++) {
     + 		for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
       			if (i == 1 && side1_matches_mbase)
  9:  decff4b3754 !  9:  be4bdfac876 merge-ort: record stage and auxiliary info for every path
     @@ merge-ort.c: static int err(struct merge_options *opt, const char *err, ...)
      +		struct conflict_info *ci;
      +
      +		ASSIGN_AND_VERIFY_CI(ci, mi);
     -+		for (i = 0; i < 3; i++) {
     ++		for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
      +			ci->pathnames[i] = fullpath;
      +			ci->stages[i].mode = names[i].mode;
      +			oidcpy(&ci->stages[i].oid, &names[i].oid);
 10:  86c661fe1ee = 10:  6fdf85c8f1a merge-ort: avoid recursing into identical trees
 11:  aa3b13ffd87 = 11:  8b001ae643a merge-ort: add a preliminary simple process_entries() implementation
 12:  b54306fd0e6 = 12:  260b12290fb merge-ort: have process_entries operate in a defined order
 13:  8ee8561d7a3 = 13:  092e77bbb15 merge-ort: step 1 of tree writing -- record basenames, modes, and oids
 14:  6ff56824c33 = 14:  b5d9ba10f8c merge-ort: step 2 of tree writing -- function to create tree object
 15:  da4fe900496 = 15:  81374cbf205 merge-ort: step 3 of tree writing -- handling subdirectories as we go
 16:  8e90d211c5d = 16:  3198efe3188 merge-ort: basic outline for merge_switch_to_result()
 17:  61fada146cf ! 17:  119f40c77f8 merge-ort: add implementation of checkout()
     @@ merge-ort.c
      +#include "unpack-trees.h"
       #include "xdiff-interface.h"
       
     - struct merge_options_internal {
     + /*
      @@ merge-ort.c: static int checkout(struct merge_options *opt,
       		    struct tree *prev,
       		    struct tree *next)
 18:  f5a13a0b084 = 18:  b4c400051ad tree: enable cmp_cache_name_compare() to be used elsewhere
 19:  4efac38116d ! 19:  ee831c8cece merge-ort: add implementation of record_conflicted_index_entries()
     @@ merge-ort.c: static int record_conflicted_index_entries(struct merge_options *op
      +			ce->ce_flags |= CE_REMOVE;
      +		}
      +
     -+		for (i = 0; i < 3; i++) {
     ++		for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
      +			struct version_info *vi;
      +			if (!(ci->filemask & (1ul << i)))
      +				continue;
 20:  fbeb527d671 = 20:  55451a79eec merge-ort: free data structures in merge_finalize()

-- 
gitgitgadget

  parent reply index

Thread overview: 70+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-11-29  7:43 [PATCH " Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 01/20] merge-ort: setup basic internal data structures Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 02/20] merge-ort: add some high-level algorithm structure Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 03/20] merge-ort: port merge_start() from merge-recursive Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 04/20] merge-ort: use histogram diff Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 05/20] merge-ort: add an err() function similar to one from merge-recursive Elijah Newren via GitGitGadget
2020-11-29 10:23   ` Ævar Arnfjörð Bjarmason
2020-11-30 16:56     ` Elijah Newren
2020-11-29 10:26   ` Ævar Arnfjörð Bjarmason
2020-11-29  7:43 ` [PATCH 06/20] merge-ort: implement a very basic collect_merge_info() Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 07/20] merge-ort: avoid repeating fill_tree_descriptor() on the same tree Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 08/20] merge-ort: compute a few more useful fields for collect_merge_info Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 09/20] merge-ort: record stage and auxiliary info for every path Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 10/20] merge-ort: avoid recursing into identical trees Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 11/20] merge-ort: add a preliminary simple process_entries() implementation Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 12/20] merge-ort: have process_entries operate in a defined order Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 13/20] merge-ort: step 1 of tree writing -- record basenames, modes, and oids Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 14/20] merge-ort: step 2 of tree writing -- function to create tree object Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 15/20] merge-ort: step 3 of tree writing -- handling subdirectories as we go Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 16/20] merge-ort: basic outline for merge_switch_to_result() Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 17/20] merge-ort: add implementation of checkout() Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 18/20] tree: enable cmp_cache_name_compare() to be used elsewhere Elijah Newren via GitGitGadget
2020-11-29  7:43 ` [PATCH 19/20] merge-ort: add implementation of record_conflicted_index_entries() Elijah Newren via GitGitGadget
2020-11-29 10:20   ` Ævar Arnfjörð Bjarmason
2020-11-29  7:43 ` [PATCH 20/20] merge-ort: free data structures in merge_finalize() Elijah Newren via GitGitGadget
2020-11-29  7:47 ` [PATCH 00/20] fundamentals of merge-ort implementation Elijah Newren
2020-12-04 20:47 ` [PATCH v2 " Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 01/20] merge-ort: setup basic internal data structures Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 02/20] merge-ort: add some high-level algorithm structure Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 03/20] merge-ort: port merge_start() from merge-recursive Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 04/20] merge-ort: use histogram diff Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 05/20] merge-ort: add an err() function similar to one from merge-recursive Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 06/20] merge-ort: implement a very basic collect_merge_info() Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 07/20] merge-ort: avoid repeating fill_tree_descriptor() on the same tree Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 08/20] merge-ort: compute a few more useful fields for collect_merge_info Elijah Newren via GitGitGadget
2020-12-04 20:47   ` [PATCH v2 09/20] merge-ort: record stage and auxiliary info for every path Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 10/20] merge-ort: avoid recursing into identical trees Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 11/20] merge-ort: add a preliminary simple process_entries() implementation Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 12/20] merge-ort: have process_entries operate in a defined order Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 13/20] merge-ort: step 1 of tree writing -- record basenames, modes, and oids Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 14/20] merge-ort: step 2 of tree writing -- function to create tree object Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 15/20] merge-ort: step 3 of tree writing -- handling subdirectories as we go Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 16/20] merge-ort: basic outline for merge_switch_to_result() Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 17/20] merge-ort: add implementation of checkout() Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 18/20] tree: enable cmp_cache_name_compare() to be used elsewhere Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 19/20] merge-ort: add implementation of record_conflicted_index_entries() Elijah Newren via GitGitGadget
2020-12-04 20:48   ` [PATCH v2 20/20] merge-ort: free data structures in merge_finalize() Elijah Newren via GitGitGadget
2020-12-13  8:04   ` Elijah Newren via GitGitGadget [this message]
2020-12-13  8:04     ` [PATCH v3 01/20] merge-ort: setup basic internal data structures Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 02/20] merge-ort: add some high-level algorithm structure Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 03/20] merge-ort: port merge_start() from merge-recursive Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 04/20] merge-ort: use histogram diff Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 05/20] merge-ort: add an err() function similar to one from merge-recursive Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 06/20] merge-ort: implement a very basic collect_merge_info() Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 07/20] merge-ort: avoid repeating fill_tree_descriptor() on the same tree Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 08/20] merge-ort: compute a few more useful fields for collect_merge_info Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 09/20] merge-ort: record stage and auxiliary info for every path Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 10/20] merge-ort: avoid recursing into identical trees Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 11/20] merge-ort: add a preliminary simple process_entries() implementation Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 12/20] merge-ort: have process_entries operate in a defined order Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 13/20] merge-ort: step 1 of tree writing -- record basenames, modes, and oids Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 14/20] merge-ort: step 2 of tree writing -- function to create tree object Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 15/20] merge-ort: step 3 of tree writing -- handling subdirectories as we go Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 16/20] merge-ort: basic outline for merge_switch_to_result() Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 17/20] merge-ort: add implementation of checkout() Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 18/20] tree: enable cmp_cache_name_compare() to be used elsewhere Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 19/20] merge-ort: add implementation of record_conflicted_index_entries() Elijah Newren via GitGitGadget
2020-12-13  8:04     ` [PATCH v3 20/20] merge-ort: free data structures in merge_finalize() Elijah Newren via GitGitGadget
2020-12-14 14:24     ` [PATCH v3 00/20] fundamentals of merge-ort implementation Felipe Contreras
2020-12-14 16:24       ` Elijah Newren

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=pull.923.v3.git.git.1607846667.gitgitgadget@gmail.com \
    --to=gitgitgadget@gmail.com \
    --cc=avarab@gmail.com \
    --cc=dstolee@microsoft.com \
    --cc=git@vger.kernel.org \
    --cc=jonathantanmy@google.com \
    --cc=newren@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Git Mailing List Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/git/0 git/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 git git/ https://lore.kernel.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.git


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git