{"thread":{"id":"65000","subject":"[PATCH 2/3] contrib/subtree: functionalize split traversal","startedAt":"2026-02-15T20:18:40Z","lastAt":"2026-02-15T20:18:43Z","messageCount":4,"participants":["Colin Stagner"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"536062","messageId":"20260215201748.889866-3-ask+git@howdoi.land","threadId":"65000","inReplyTo":"20260215201748.889866-1-ask+git@howdoi.land","subject":"[PATCH 2/3] contrib/subtree: functionalize split traversal","fromName":"Colin Stagner","fromEmail":"ask+git@howdoi.land","sentAt":"2026-02-15T20:17:44Z","receivedAt":"2026-02-15T20:18:40Z","isPatch":true,"sender":{"key":"ask+git@howdoi.land","avatar":null},"body":"`git subtree split` requires an ancestor-first history traversal.\nRefactor the existing rev-list traversal into its own function,\n`find_commits_to_split`.\n\nPass unrevs via stdin to avoid limits on the maximum length of\ncommand-line arguments. Also remove an unnecessary `eval`.\n\nSigned-off-by: Colin Stagner <ask+git@howdoi.land>\n---\n contrib/subtree/git-subtree.sh | 30 +++++++++++++++++++++++++++---\n 1 file changed, 27 insertions(+), 3 deletions(-)\n\ndiff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh\nindex 1cdf39a481..7a62ef7504 100755\n--- a/contrib/subtree/git-subtree.sh\n+++ b/contrib/subtree/git-subtree.sh\n@@ -516,6 +516,31 @@ find_existing_splits () {\n \tdone || exit $?\n }\n \n+# Usage: find_commits_to_split REV UNREVS [ARGS...]\n+#\n+# List each commit to split, with its parents.\n+#\n+# Specify the starting REV for the split, which is usually\n+# a branch tip. Populate UNREVS with the last --rejoin for\n+# this prefix, if any. Typically, `subtree split` ignores\n+# history prior to the last --rejoin... unless and if it\n+# becomes necessary to consider it. `find_existing_splits` is\n+# a convenient source of UNREVS.\n+#\n+# Remaining arguments are passed to rev-list.\n+#\n+# Outputs commits in ancestor-first order, one per line, with\n+# parent information. Outputs all parents before any child.\n+find_commits_to_split() {\n+\tassert test $# -ge 2\n+\trev=\"$1\"\n+\tunrevs=\"$2\"\n+\tshift 2\n+\n+\techo \"$unrevs\" |\n+\tgit rev-list --topo-order --reverse --parents --stdin \"$rev\" \"$@\"\n+}\n+\n # Usage: copy_commit REV TREE FLAGS_STR\n copy_commit () {\n \tassert test $# = 3\n@@ -1003,12 +1028,11 @@ cmd_split () {\n \t# We can't restrict rev-list to only $dir here, because some of our\n \t# parents have the $dir contents the root, and those won't match.\n \t# (and rev-list --follow doesn't seem to solve this)\n-\tgrl='git rev-list --topo-order --reverse --parents $rev $unrevs'\n-\trevmax=$(eval \"$grl\" | wc -l)\n+\trevmax=\"$(find_commits_to_split \"$rev\" \"$unrevs\" --count)\"\n \trevcount=0\n \tcreatecount=0\n \textracount=0\n-\teval \"$grl\" |\n+\tfind_commits_to_split \"$rev\" \"$unrevs\" |\n \twhile read rev parents\n \tdo\n \t\tif should_ignore_subtree_split_commit \"$rev\"\n-- \n2.43.0\n\n"},{"id":"536064","messageId":"20260215201748.889866-2-ask+git@howdoi.land","threadId":"65000","inReplyTo":"20260215201748.889866-1-ask+git@howdoi.land","subject":"[PATCH 1/3] contrib/subtree: reduce function side-effects","fromName":"Colin Stagner","fromEmail":"ask+git@howdoi.land","sentAt":"2026-02-15T20:17:43Z","receivedAt":"2026-02-15T20:18:40Z","isPatch":true,"sender":{"key":"ask+git@howdoi.land","avatar":null},"body":"`process_subtree_split_trailer()` communicates its return value\nto the caller by setting a variable (`sub`) that is also defined\nby the calling function. This is both unclear and encourages\nside-effects.\n\nInvoke this function in a sub-shell instead.\n\nSigned-off-by: Colin Stagner <ask+git@howdoi.land>\n---\n contrib/subtree/git-subtree.sh | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh\nindex 17106d1a72..1cdf39a481 100755\n--- a/contrib/subtree/git-subtree.sh\n+++ b/contrib/subtree/git-subtree.sh\n@@ -370,6 +370,10 @@ try_remove_previous () {\n }\n \n # Usage: process_subtree_split_trailer SPLIT_HASH MAIN_HASH [REPOSITORY]\n+#\n+# Parse SPLIT_HASH as a commit. If the commit is not found, fetches\n+# REPOSITORY and tries again. If found, prints full commit hash.\n+# Otherwise, dies.\n process_subtree_split_trailer () {\n \tassert test $# -ge 2\n \tassert test $# -le 3\n@@ -397,6 +401,7 @@ process_subtree_split_trailer () {\n \t\t\tdie \"$fail_msg\"\n \t\tfi\n \tfi\n+\techo \"${sub}\"\n }\n \n # Usage: find_latest_squash DIR [REPOSITORY]\n@@ -429,7 +434,7 @@ find_latest_squash () {\n \t\t\tmain=\"$b\"\n \t\t\t;;\n \t\tgit-subtree-split:)\n-\t\t\tprocess_subtree_split_trailer \"$b\" \"$sq\" \"$repository\"\n+\t\t\tsub=\"$(process_subtree_split_trailer \"$b\" \"$sq\" \"$repository\")\" || exit 1\n \t\t\t;;\n \t\tEND)\n \t\t\tif test -n \"$sub\"\n@@ -486,7 +491,7 @@ find_existing_splits () {\n \t\t\tmain=\"$b\"\n \t\t\t;;\n \t\tgit-subtree-split:)\n-\t\t\tprocess_subtree_split_trailer \"$b\" \"$sq\" \"$repository\"\n+\t\t\tsub=\"$(process_subtree_split_trailer \"$b\" \"$sq\" \"$repository\")\" || exit 1\n \t\t\t;;\n \t\tEND)\n \t\t\tdebug \"Main is: '$main'\"\n-- \n2.43.0\n\n"},{"id":"536063","messageId":"20260215201748.889866-1-ask+git@howdoi.land","threadId":"65000","inReplyTo":null,"subject":"[PATCH 0/3] contrib/subtree: reduce recursion during split","fromName":"Colin Stagner","fromEmail":"ask+git@howdoi.land","sentAt":"2026-02-15T20:17:42Z","receivedAt":"2026-02-15T20:18:42Z","isPatch":true,"sender":{"key":"ask+git@howdoi.land","avatar":null},"body":"* cs/subtree-split-recursion: when processing large history\n  graphs on Debian or Ubuntu, \"git subtree\" can die with a\n  \"recursion depth reached\" error. Reduce recursion.\n\nOn Debian's POSIX sh, shell recursion is artificially limited\nto 1000 calls. You can check if your sh has limited recursion\nwith:\n\n    #!/bin/sh\n    recurse() {\n        r=$(( r + 1 ))\n        test \"$r\" -le 1000 || { echo OK; exit; }\n        recurse\n    } && r=0 && recurse\n\nDepending on the history graph, subtree split can recurse deeply\nenough to encounter this limit. Rewrite the rejoin-deepening\nalgorithm to reduce recursive calls.\n\nColin Stagner (3):\n  contrib/subtree: reduce function side-effects\n  contrib/subtree: functionalize split traversal\n  contrib/subtree: reduce recursion during split\n\n contrib/subtree/git-subtree.sh | 95 +++++++++++++++++++++++++++++++---\n 1 file changed, 88 insertions(+), 7 deletions(-)\n\n\nbase-commit: 852829b3dd2fe4e7c7fc4d8badde644cf1b66c74\n-- \n2.43.0\n\n"},{"id":"536065","messageId":"20260215201748.889866-4-ask+git@howdoi.land","threadId":"65000","inReplyTo":"20260215201748.889866-1-ask+git@howdoi.land","subject":"[PATCH 3/3] contrib/subtree: reduce recursion during split","fromName":"Colin Stagner","fromEmail":"ask+git@howdoi.land","sentAt":"2026-02-15T20:17:45Z","receivedAt":"2026-02-15T20:18:43Z","isPatch":true,"sender":{"key":"ask+git@howdoi.land","avatar":null},"body":"On Debian-alikes, POSIX sh has a hardcoded recursion depth\nof 1000. This limit operates like bash's `$FUNCNEST` [1], but\nit does not actually respect `$FUNCNEST`. This is non-standard\nbehavior. On other distros, the sh recursion depth is limited\nonly by the available stack size.\n\nWith certain history graphs, subtree splits are recursive—with\none recursion per commit. Attempting to split complex repos that\nhave thousands of commits, like [2], may fail on these distros.\n\nReduce the amount of recursion required by eagerly discovering\nthe complete range of commits to process.\n\nThe recursion is a side-effect of the rejoin-finder in\n`find_existing_splits`. Rejoin mode, as in\n\n    git subtree split --rejoin -b hax main ...\n\nimproves the speed of later splits by merging the split history\nback into `main`. This gives the splitting algorithm a stopping\npoint. The rejoin maps one commit on `main` to one split commit\non `hax`. If we encounter this commit, we know that it maps to\n`hax`.\n\nBut this is only a single point in the history. Many splits\nrequire history from before the rejoin. See patch content for\nexamples.\n\nIf pre-rejoin history is required, `check_parents` recursively\ndiscovers each individual parent, with one recursion per commit.\nThe recursion deepens the entire tree, even if an older rejoin\nis available. This quickly overwhelms the Debian sh stack.\n\nInstead of recursively processing each commit, process *all* the\ncommits back to the next obvious starting point: i.e., either the\nnext-oldest --rejoin or the beginning of history. This is where the\nrecursion is likely to stop anyway.\n\nWhile this still requires recursion, it is *considerably* less\nrecursive.\n\n[1]: https://www.gnu.org/software/bash/manual/html_node/Bash-Variables.html#index-FUNCNEST\n\n[2]: https://github.com/christian-heusel/aur.git\n\nSigned-off-by: Colin Stagner <ask+git@howdoi.land>\n---\n contrib/subtree/git-subtree.sh | 56 ++++++++++++++++++++++++++++++++--\n 1 file changed, 54 insertions(+), 2 deletions(-)\n\ndiff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh\nindex 7a62ef7504..54d7151a50 100755\n--- a/contrib/subtree/git-subtree.sh\n+++ b/contrib/subtree/git-subtree.sh\n@@ -312,6 +312,46 @@ cache_miss () {\n }\n \n # Usage: check_parents [REVS...]\n+#\n+# During a split, check that every commit in REVS has already been\n+# processed via `process_split_commit`. If not, deepen the history\n+# until it is.\n+#\n+# Commits authored by `subtree split` have to be created in the\n+# same order as every other git commit: ancestor-first, with new\n+# commits building on old commits. The traversal order normally\n+# ensures this is the case, but it also excludes --rejoins commits\n+# by default.\n+#\n+# The --rejoin tells us, \"this mainline commit is equivalent to\n+# this split commit.\" The relationship is only known for that\n+# exact commit---and not before or after it. Frequently, commits\n+# prior to a rejoin are not needed... but, just as often, they\n+# are! Consider this history graph:\n+#\n+#              --D---\n+#             /      \\\n+#         A--B--C--R--X--Y    main\n+#                 /     /\n+#          a--b--c     /      split\n+#              \\      /\n+#               --e--/\n+#\n+# The main branch has commits A, B, and C. main is split into\n+# commits a, b, and c. The split history is rejoined at R.\n+#\n+# There are at least two cases where we might need the A-B-C\n+# history that is prior to R:\n+#\n+# 1. Commit D is based on history prior to R, but\n+#    it isn't merged into mainline until after R.\n+#\n+# 2. Commit e is based on old split history. It is merged\n+#    back into mainline with a subtree merge. Again, this\n+#    happens after R.\n+#\n+# check_parents detects these cases and deepens the history\n+# to the next available rejoin.\n check_parents () {\n \tmissed=$(cache_miss \"$@\") || exit $?\n \tlocal indent=$(($indent + 1))\n@@ -319,8 +359,20 @@ check_parents () {\n \tdo\n \t\tif ! test -r \"$cachedir/notree/$miss\"\n \t\tthen\n-\t\t\tdebug \"incorrect order: $miss\"\n-\t\t\tprocess_split_commit \"$miss\" \"\"\n+\t\t\tdebug \"found commit excluded by --rejoin: $miss. skipping to the next --rejoin...\"\n+\t\t\tunrevs=\"$(find_existing_splits \"$dir\" \"$miss\" \"$repository\")\" || exit 1\n+\n+\t\t\tfind_commits_to_split \"$miss\" \"$unrevs\" |\n+\t\t\twhile read -r rev parents\n+\t\t\tdo\n+\t\t\t\tprocess_split_commit \"$rev\" \"$parents\"\n+\t\t\tdone\n+\n+\t\t\tif ! test -r \"$cachedir/$miss\" &&\n+\t\t\t\t! test -r \"$cachedir/notree/$miss\"\n+\t\t\tthen\n+\t\t\t\tdie \"failed to deepen history at $miss\"\n+\t\t\tfi\n \t\tfi\n \tdone\n }\n-- \n2.43.0\n\n"}]}