[PATCH v4] subtree: fix split processing with multiple subtrees present

From: Zach FettersMoore <zach.fetters@apollographql.com>

When there are multiple subtrees present in a repository and they are all using 'git subtree split', the 'split' command can take a significant (and constantly growing) amount of time to run even when using the '--rejoin' flag. This is due to the fact that when processing commits to determine the last known split to start from when looking for changes, if there has been a split/merge done from another subtree there will be 2 split commits, one mainline and one subtree, for the second subtree that are part of the processing. The non-mainline subtree split commit will cause the processing to always need to search the entire history of the given subtree as part of its processing even though those commits are totally irrelevant to the current subtree split being run.

In the diagram below, 'M' represents the mainline repo branch, 'A' represents one subtree, and 'B' represents another. M3 and B1 represent a split commit for subtree B that was created from commit M4. M2 and A1 represent a split commit made from subtree A that was also created based on changes back to and including M4. M1 represents new changes to the repo, in this scenario if you try to run a 'git subtree split --rejoin' for subtree B, commits M1, M2, and A1, will be included in the processing of changes for the new split commit since the last split/rejoin for subtree B was at M3. The issue is that by having A1 included in this processing the command ends up needing to processing every commit down tree A even though none of that is needed or relevant to the current command and result.

M1
 |	  \	  \
M2	   |	   |
 |     	  A1	   |
M3	   |	   |
 |	   |	  B1
M4	   |	   |

So this commit makes a change to the processing of commits for the split command in order to ignore non-mainline commits from other subtrees such as A1 in the diagram by adding a new function 'should_ignore_subtree_commit' which is called during 'process_split_commit'. This allows the split/rejoin processing to still function as expected but removes all of the unnecessary processing that takes place currently which greatly inflates the processing time.

Added a test to validate that the proposed fix solves the issue.

The test accomplishes this by checking the output of the split command to ensure the output from the progress of 'process_split_commit' function that represents the 'extracount' of commits processed does not increment.

This was tested against the original functionality to show the test failed, and then with this fix to show the test passes.

This illustrated that when using multiple subtrees, A and B, when doing a split on subtree B, the processing does not traverse the entire history of subtree A which is unnecessary and would cause the 'extracount' of processed commits to climb based on the number of commits in the history of subtree A.

Signed-off-by: Zach FettersMoore <zach.fetters@apollographql.com>
---
    subtree: fix split processing with multiple subtrees present
    
    When there are multiple subtrees in a repo and git subtree split
    --rejoin is being used for the subtrees, the processing of commits for a
    new split can take a significant (and constantly growing) amount of time
    because the split commits from other subtrees cause the processing to
    have to scan the entire history of the other subtree(s). This patch
    filters out the other subtree split commits that are unnecessary for the
    split commit processing.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1587%2FBobaFetters%2Fzf%2Fmulti-subtree-processing-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1587/BobaFetters/zf/multi-subtree-processing-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/1587

Range-diff vs v3:

 1:  43175154a82 < -:  ----------- subtree: fix split processing with multiple subtrees present
 2:  d6811daf7cf < -:  ----------- subtree: changing location of commit ignore processing
 3:  eff8bfcc042 ! 1:  353152910eb subtree: adding test to validate fix
     @@ Metadata
      Author: Zach FettersMoore <zach.fetters@apollographql.com>
      
       ## Commit message ##
     -    subtree: adding test to validate fix
     +    subtree: fix split processing with multiple subtrees present
      
     -    Adding a test to validate that the proposed fix
     +    When there are multiple subtrees present in a repository and they are
     +    all using 'git subtree split', the 'split' command can take a
     +    significant (and constantly growing) amount of time to run even when
     +    using the '--rejoin' flag. This is due to the fact that when processing
     +    commits to determine the last known split to start from when looking
     +    for changes, if there has been a split/merge done from another subtree
     +    there will be 2 split commits, one mainline and one subtree, for the
     +    second subtree that are part of the processing. The non-mainline
     +    subtree split commit will cause the processing to always need to search
     +    the entire history of the given subtree as part of its processing even
     +    though those commits are totally irrelevant to the current subtree
     +    split being run.
     +
     +    In the diagram below, 'M' represents the mainline repo branch, 'A'
     +    represents one subtree, and 'B' represents another. M3 and B1 represent
     +    a split commit for subtree B that was created from commit M4. M2 and A1
     +    represent a split commit made from subtree A that was also created
     +    based on changes back to and including M4. M1 represents new changes to
     +    the repo, in this scenario if you try to run a 'git subtree split
     +    --rejoin' for subtree B, commits M1, M2, and A1, will be included in
     +    the processing of changes for the new split commit since the last
     +    split/rejoin for subtree B was at M3. The issue is that by having A1
     +    included in this processing the command ends up needing to processing
     +    every commit down tree A even though none of that is needed or relevant
     +    to the current command and result.
     +
     +    M1
     +     |        \       \
     +    M2         |       |
     +     |        A1       |
     +    M3         |       |
     +     |         |      B1
     +    M4         |       |
     +
     +    So this commit makes a change to the processing of commits for the split
     +    command in order to ignore non-mainline commits from other subtrees such
     +    as A1 in the diagram by adding a new function
     +    'should_ignore_subtree_commit' which is called during
     +    'process_split_commit'. This allows the split/rejoin processing to still
     +    function as expected but removes all of the unnecessary processing that
     +    takes place currently which greatly inflates the processing time.
     +
     +    Added a test to validate that the proposed fix
          solves the issue.
      
          The test accomplishes this by checking the output
     @@ Commit message
      
          Signed-off-by: Zach FettersMoore <zach.fetters@apollographql.com>
      
     + ## contrib/subtree/git-subtree.sh ##
     +@@ contrib/subtree/git-subtree.sh: ensure_valid_ref_format () {
     + 		die "fatal: '$1' does not look like a ref"
     + }
     + 
     ++# Usage: check if a commit from another subtree should be
     ++# ignored from processing for splits
     ++should_ignore_subtree_split_commit () {
     ++  if test -n "$(git log -1 --grep="git-subtree-dir:" $1)"
     ++  then
     ++    if test -z "$(git log -1 --grep="git-subtree-mainline:" $1)" &&
     ++			test -z "$(git log -1 --grep="git-subtree-dir: $arg_prefix$" $1)"
     ++    then
     ++      return 0
     ++    fi
     ++  fi
     ++  return 1
     ++}
     ++
     + # Usage: process_split_commit REV PARENTS
     + process_split_commit () {
     + 	assert test $# = 2
     +@@ contrib/subtree/git-subtree.sh: cmd_split () {
     + 	eval "$grl" |
     + 	while read rev parents
     + 	do
     +-		process_split_commit "$rev" "$parents"
     ++		if should_ignore_subtree_split_commit "$rev"
     ++		then
     ++			continue
     ++		fi
     ++		parsedParents=''
     ++		for parent in $parents
     ++		do
     ++			should_ignore_subtree_split_commit "$parent"
     ++			if test $? -eq 1
     ++			then
     ++				parsedParents+="$parent "
     ++			fi
     ++		done
     ++		process_split_commit "$rev" "$parsedParents"
     + 	done || exit $?
     + 
     + 	latest_new=$(cache_get latest_new) || exit $?
     +
       ## contrib/subtree/t/t7900-subtree.sh ##
      @@ contrib/subtree/t/t7900-subtree.sh: test_expect_success 'split sub dir/ with --rejoin' '
       	)
     @@ contrib/subtree/t/t7900-subtree.sh: test_expect_success 'split sub dir/ with --r
      +	) &&
      +	(
      +		cd "$test_count" &&
     -+		test "$(git subtree split --prefix=subBDir --squash --rejoin -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" = ""
     ++		test "$(git subtree split --prefix=subBDir --squash --rejoin \
     ++		 -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" = ""
      +	)
      +'
      +

 contrib/subtree/git-subtree.sh     | 29 ++++++++++++++++++++-
 contrib/subtree/t/t7900-subtree.sh | 42 ++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+), 1 deletion(-)