{"thread":{"id":"66326","subject":"[PATCH 0/2] connected: add incremental connectivity check","startedAt":"2026-09-14T09:47:59Z","lastAt":"2026-10-06T05:59:01Z","messageCount":13,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Kristofer Karlsson","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"552689","messageId":"pull.2211.git.1789379276.gitgitgadget@gmail.com","threadId":"66326","inReplyTo":null,"subject":"[PATCH 0/2] connected: add incremental connectivity check","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-09-14T09:47:54Z","receivedAt":"2026-09-14T09:47:59Z","isPatch":true,"body":"This series adds an incremental mode for the connectivity check, gated\nbehind transfer.connectivityCheck=incremental (no expected changes unless\nyou opt in).\n\nThe intent is to solve the problem of the connectivity check slowing down as\nthe number of reachable objects from the boundary grows.\n\nIt relates to the RFC I sent out earlier:\n\n[RFC] check_connected: toward incoming-proportional cost\nhttps://lore.kernel.org/git/CAL71e4Nf=-zCrfN7ghEVGq11irajJhtdxYZgKe0Ycux0qs1ZvQ@mail.gmail.com/\n\n\n\nDesign\n======\n\nThe verifier runs inside the same rev-list subprocess that check_connected()\nalready spawns, triggered by a new internal flag --verify-trees-incremental.\nAfter get_revision() collects the incoming commits, the verifier processes\nthem in topological order (ancestors before descendants).\n\nThe idea is to keep a set of trusted objects, shared across the incoming\ncommits, that grows over time. We visit the new/untrusted commit trees and\ndo a comparison walk over the trees of their parents. Entries discovered on\nthe trusted parent side are remembered as trusted, which lets later\nverification skip matching objects and avoid descending into unchanged\nsubtrees.\n\nMore algorithmic details are in\nDocumentation/technical/connectivity-check.adoc.\n\n\nBenchmarks\n==========\n\nI'll just mention a short summary here, to avoid repeating what's already in\nthe commit message. The incremental mode is faster than the full mode when\nthere are few commits to verify and when the active object tree is large. In\nthe happy case, the work tracks the changed paths and their comparison trees\nrather than the full reachable object closure, which substantially reduces\nthe dependence on total repository size. I've seen speedups up to around 20x\nfor the synthetic perf tests.\n\nRunning against a large real-world repo (3.4 GB boundary closure), the\nnumbers are more dramatic. All timings use rev-list directly with --not\nHEADN, isolating the tree verification cost from the boundary-finding cost:\n\ncommits full incr. speedup full RSS incr. RSS\n 1 1.9s 0.01s 190x 3.4 GB 14 MB\n 10 1.9s 0.04s 48x 3.4 GB 125 MB\n 100 1.9s 0.37s 5x 3.4 GB 1.1 GB\n\n\nThe full mode takes ~1.9s regardless of commit count because it is dominated\nby walking the boundary closure. Incremental scales with the number of\nincoming commits and the paths they touch. Memory follows the same pattern:\nincremental uses a fraction of the full mode's RSS for small pushes,\nconverging only when many commits are verified.\n\nThere are also regression cases in the synthetic fixtures. With long\nincoming histories, the extra parent-tree scans accumulate; in the synthetic\nfixture incremental is about 1.5x slower at 10000 commits. Per-commit\nchanges have less impact than expected: even when every directory is\ntouched, incremental remains competitive; bypassing the object cache for\ntree reads likely helps here.\n\nI cannot establish how common these regression cases are. In the cases I\nhave tested, however, the regression has remained modest; I have not been\nable to provoke a substantially larger slowdown. My feeling is that this is\nan acceptable tradeoff behind the opt-in config, since the target case\n(small pushes to large repos) sees the largest speedup, while the regression\nappears with long incoming histories.\n\nA safety net for this regression could be to dynamically disable the\nincremental mode if the number of incoming commits is too large, but this is\nleft out of the initial version to avoid overly speculative code.\n\nDeepening fetches currently fall back to the full check because the full\ncheck omits --not --all for deepening -- there is no existing-reference\nboundary at which the walk can stop. An incremental approach is possible\nhere too -- using the old shallow roots as the trusted boundary and walking\nthe deepened ancestry forward -- but that is a separate change and left for\nfuture work. Deepening is also less common than regular fetch and\nreceive-pack, where the speedup matters most.\n\n\nTest coverage\n=============\n\nMost correctness cases in t5412-connectivity-check.sh are run in both full\nand incremental modes to check semantic equivalence. Selected cases\nadditionally assert trace2 tree/blob counts for the incremental mode, to\nverify that unchanged portions of the object graph are actually skipped. It\ncovers:\n\n * Corruption detection: missing blobs, missing trees, type mismatches,\n malformed trees (unparseable, mid-tree corruption)\n * Tree optimization: trace2 assertions confirm unchanged subtrees are\n skipped, subtree moves, merge parent boundaries\n * Root commits (no parents -- verifies full tree closure)\n * Partial clones: missing promised blobs, missing promised trees,\n verification of local commits\n * Replacement objects (with and without GIT_NO_REPLACE_OBJECTS)\n * Shallow boundaries\n * Deepening fetches (falls back to full check)\n * Integration: real push, fetch, and clone\n\nMost tests call git rev-list directly with the appropriate flags;\nintegration tests exercise the full check_connected() path through push,\nfetch, and clone.\n\n\nAlternatives considered\n=======================\n\nMy first prototype ran the verifier in-process inside connected.c. This\nrequired a second rev-list subprocess just for boundary finding, _nofetch\nvariants of several object-reading functions to prevent lazy fetches in\npartial clones, explicit shallow-file plumbing, and careful avoidance of\ndie() in all code paths reachable from the verifier. The result worked but\nwas fragile and touched many files.\n\nMoving the verifier into the rev-list subprocess eliminated all of those\nproblems: in partial clones the existing --exclude-promisor-objects handling\nalready disables lazy fetching, die() is isolated by the process boundary,\nshallow and replacement semantics are established before the verifier runs,\nand error routing comes for free via stderr.\n\nSo while I liked the idea of being less reliant on checking within a\nsubprocess, making that work ended up being a lot more complex.\n\n\nNext steps\n==========\n\nThis series only addresses tree verification; the other significant cost is\nfinding the commit boundary, especially for repos with many refs. I already\nhave some prototypes for optimizing that too, and if this ends up landing,\nthat would be something I would start polishing up.\n\nThanks, Kristofer\n\nKristofer Karlsson (2):\n Documentation: describe connectivity checking\n connected: add incremental connectivity check via rev-list\n\n Documentation/config/transfer.adoc | 20 +\n Documentation/rev-list-options.adoc | 6 +\n .../technical/connectivity-check.adoc | 243 +++++++\n Makefile | 1 +\n builtin/rev-list.c | 18 +\n connected.c | 24 +\n meson.build | 1 +\n t/meson.build | 1 +\n ...enerate-repo-p5412-connectivity-check.perl | 44 ++\n t/perf/p5412-connectivity-check.sh | 92 +++\n t/t5412-connectivity-check.sh | 655 ++++++++++++++++++\n tree-verify.c | 306 ++++++++\n tree-verify.h | 15 +\n 13 files changed, 1426 insertions(+)\n create mode 100644 Documentation/technical/connectivity-check.adoc\n create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl\n create mode 100755 t/perf/p5412-connectivity-check.sh\n create mode 100755 t/t5412-connectivity-check.sh\n create mode 100644 tree-verify.c\n create mode 100644 tree-verify.h\n\n\nbase-commit: 47ce80527c56f462cb97db4ca8125342204d3783\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2211%2Fspkrka%2Ftree-diff-connectivity-v1-clean-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2211/spkrka/tree-diff-connectivity-v1-clean-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2211\n-- \ngitgitgadget\n"},{"id":"552690","messageId":"e55c5452db0b7cb683d4e2ad51cd8f44046c23bd.1789379276.git.gitgitgadget@gmail.com","threadId":"66326","inReplyTo":"pull.2211.git.1789379276.gitgitgadget@gmail.com","subject":"[PATCH 1/2] Documentation: describe connectivity checking","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-09-14T09:47:55Z","receivedAt":"2026-09-14T09:48:00Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nAdd Documentation/technical/connectivity-check.adoc describing\nthe connectivity invariant and the full connectivity check.\n\nSigned-off-by: Kristofer Karlsson \n---\n .../technical/connectivity-check.adoc | 109 ++++++++++++++++++\n 1 file changed, 109 insertions(+)\n create mode 100644 Documentation/technical/connectivity-check.adoc\n\ndiff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc\nnew file mode 100644\nindex 0000000000..d20bff6af6\n--- /dev/null\n+++ b/Documentation/technical/connectivity-check.adoc\n@@ -0,0 +1,109 @@\n+Connectivity checking\n+=====================\n+\n+After receiving new objects via fetch, push (receive-pack), clone,\n+or bundle, Git verifies that the new reference tips do not leave\n+the repository in a state where reachable objects are missing.\n+This verification is called the connectivity check.\n+\n+Connectivity invariant\n+----------------------\n+\n+A repository is connected when every object reachable from its\n+references is available locally (with exceptions noted below).\n+\n+The connectivity check maintains this invariant when references\n+are updated. It trusts the existing connected state and verifies\n+that the new reference tips do not introduce references to\n+unavailable objects. Verification is permitted to stop when it\n+reaches objects already reachable from trusted existing\n+references, since their closure is already connected. These\n+trusted references include local references and references from\n+alternate object stores.\n+\n+Without this check, a truncated or corrupted transfer could leave\n+a repository in a state where later history walks encounter\n+missing objects.\n+\n+Exceptions\n+~~~~~~~~~~\n+\n+Gitlink entries (submodule references) are excluded from\n+connectivity checking. Their target objects belong to a separate\n+repository.\n+\n+In partial clones, objects promised by a promisor remote are\n+accepted as connected without requiring local existence. The\n+check excludes promisor objects from traversal so that it does\n+not trigger on-demand fetches for them.\n+\n+Full connectivity check\n+-----------------------\n+\n+`check_connected()` (see `connected.c`) normally performs the\n+connectivity check using a `rev-list` subprocess, feeding the\n+new reference tips via stdin. A normal invocation is roughly:\n+\n+ git rev-list --objects --stdin --not --all --quiet\n+ --alternate-refs [--exclude-promisor-objects]\n+\n+When promisor remotes are configured, `check_connected()` first\n+attempts a fast path based on promisor packfiles. If it falls\n+back to the `rev-list` check, `--exclude-promisor-objects` is\n+added so that the traversal does not trigger on-demand fetches.\n+\n+Consider the following graph after a fetch, where all reference\n+tips point directly to commits. For simplicity, only local\n+references appear on the already-connected side; alternate refs\n+play the same role. N3 is a merge commit:\n+\n+ /-------------L2\n+ /\n+ C1---B1---C2---B2-----L1\n+ \\ \\\n+ N1 N3---T2\n+ \\ /\n+ N2-----------T1\n+\n+ L1, L2: local refs\n+ T1, T2: incoming tips (new refs)\n+ N1, N2, N3: incoming commits (N3 is a merge)\n+ B1, B2: boundary commits (already connected)\n+ C1, C2: already connected (but not boundary)\n+\n+The incoming set is the commits reachable from the incoming\n+tips but not from the already-connected side. Boundary commits\n+are the already-connected commits at the edge of that set. Here\n+B1 is an ancestor of B2, which happens when incoming branches\n+fork at different depths in the existing history.\n+\n+The check proceeds in three phases:\n+\n+1. Walk from the incoming tips (T1, T2) against the trusted\n+ refs (L1, L2) to find the incoming set ({N1, N2, N3, T1, T2}).\n+\n+2. Walk the trees of the boundary commits (B1, B2) and mark\n+ those objects uninteresting. These trees are already trusted\n+ because their commits are on the already-connected side.\n+\n+3. Walk the trees of each incoming commit and verify that every\n+ referenced object is connected, stopping at objects already\n+ marked uninteresting in phase 2.\n+\n+Deepening fetches\n+~~~~~~~~~~~~~~~~~\n+\n+For deepening fetches (where the shallow boundary moves), the\n+full check omits `--not --all`. There is no existing-reference\n+boundary at which the walk can stop. Instead, traversal follows\n+the effective shallow boundary supplied for the deepened\n+repository. The new content may be below the old shallow\n+boundary even when the tips themselves have not changed.\n+\n+Non-commit tips\n+~~~~~~~~~~~~~~~\n+\n+When a new reference points to a non-commit object, such as a\n+tag, tree, or blob, that object is not part of the commit walk.\n+These non-commit tips are handled by the subsequent object\n+traversal.\n-- \ngitgitgadget\n\n"},{"id":"552691","messageId":"ebe6c90cc58b9e1f64c9bec4a18e8cb3ce9be1b2.1789379276.git.gitgitgadget@gmail.com","threadId":"66326","inReplyTo":"pull.2211.git.1789379276.gitgitgadget@gmail.com","subject":"[PATCH 2/2] connected: add incremental connectivity check via rev-list","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-09-14T09:47:56Z","receivedAt":"2026-09-14T09:48:03Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nThe full connectivity check uses rev-list to find commits\nreachable from the incoming tips but not from the\nalready-connected side, then walks their object closure. Commit\ntraversal stops at the connectivity boundary, but trees and blobs\nreachable from that boundary still need to be walked so they can\nbe marked uninteresting, allocating a struct object for each one.\nOn repositories where the boundary commits have large trees, the\nconnectivity check for small incoming changes visits and tracks\nmore objects than needed.\n\nAdd an alternative connectivity check that verifies incoming\ncommits incrementally against their parents.\n\nThe verifier processes incoming commits with ancestors first and\ncompares each new tree against its trusted parent trees. Entries\nalready seen on the trusted side are skipped by OID, so unchanged\nsubtrees need not remain at the same path to be recognized.\nChanged subtrees are recursively compared against same-path parent\nsubtrees, and new subtrees without a comparison base are verified\nfrom scratch.\n\nSee Documentation/technical/connectivity-check.adoc for the trust\ninvariants and detailed algorithm.\n\nThe incremental check runs as an internal\n--verify-trees-incremental mode in rev-list. After the normal\nrevision walk identifies the incoming commits, the verifier\nconsumes them before the usual object traversal; any pending\nnon-commit tips are still handled by the existing traversal.\n\nPartial-clone semantics are preserved: objects promised by a\npromisor remote are accepted as connected, and on-demand fetching\nis prevented by excluding promisor objects from traversal. The\nnew mode is selected by transfer.connectivityCheck=incremental,\nwith full remaining the default. Deepening fetches fall back to\nthe full check because they do not have the normal\nexisting-reference boundary, and traversal instead follows the\neffective shallow boundary.\n\np5412 results (median of 3), scaling one dimension at a time.\nEach fixture is a repository with a flat tree of many\ndirectories containing 100 files each. The incoming set is a\nchain of commits on top of the existing history, with each\ncommit changing files in different directories round-robin.\nThe three axes vary the total repository tree size, the number\nof incoming commits, and the number of files changed per\nincoming commit.\n\nScaling tree size (10 incoming commits, 10 files/commit):\n\n files full incr. full/incr\n 5K 0.01s 0.01s 1.0x\n 50K 0.04s 0.01s 4.0x\n 200K 0.15s 0.01s 15.0x\n 800K 0.61s 0.03s 20.3x\n\nThe full mode must walk the trees of boundary commits, which\ngrows with overall tree size. Incremental still scans the\nroot trees, but avoids descending into unchanged subtrees,\nso it grows much more slowly with repository size.\n\nScaling incoming commit count (200K files, 10 files/commit):\n\n commits full incr. full/incr\n 1 0.14s 0.01s 14.0x\n 10 0.15s 0.01s 15.0x\n 100 0.19s 0.05s 3.8x\n 500 0.32s 0.27s 1.2x\n 3000 1.23s 1.52s 0.8x\n 5000 1.88s 2.43s 0.8x\n 10000 3.72s 5.36s 0.7x\n\nWith many commits the per-commit overhead of scanning both\nthe new and parent root trees accumulates and incremental\nbecomes slower. Breakeven is between 500 and 3000 commits\nand the ratio stabilizes near 0.7x for this fixture.\n\nScaling files per incoming commit (200K files, 10 commits):\n\n files/commit full incr. full/incr\n 1 0.14s 0.01s 14.0x\n 10 0.15s 0.01s 15.0x\n 100 0.16s 0.04s 4.0x\n 500 0.23s 0.14s 1.6x\n 1000 0.34s 0.28s 1.2x\n 2000 0.70s 0.63s 1.1x\n\nBreakeven is around 1000 files/commit. At 2000 files/commit\n(every directory touched), incremental remains slightly faster;\nbypassing the object cache for tree reads likely helps here.\n\nFor small repositories both modes are fast enough that the\ndifference is difficult to measure reliably.\n\nSelected peak RSS measurements from the same fixtures:\n\n case full incr. ratio\n 200K files, 10 commits 31 MB 12 MB 0.4x\n 800K files, 10 commits 110 MB 26 MB 0.2x\n 200K files, 5000 commits 155 MB 151 MB 1.0x\n\nIncremental uses substantially less memory when it can prune\nmost of the boundary tree walk. In the long-history case the\ntwo modes visit similar object sets and memory converges.\n\nThe regression cases in the CPU benchmarks are in wall-clock\ntime rather than memory, primarily from scanning some trees\nmore than once.\n\nSigned-off-by: Kristofer Karlsson \n---\n Documentation/config/transfer.adoc | 20 +\n Documentation/rev-list-options.adoc | 6 +\n .../technical/connectivity-check.adoc | 134 ++++\n Makefile | 1 +\n builtin/rev-list.c | 18 +\n connected.c | 24 +\n meson.build | 1 +\n t/meson.build | 1 +\n ...enerate-repo-p5412-connectivity-check.perl | 44 ++\n t/perf/p5412-connectivity-check.sh | 92 +++\n t/t5412-connectivity-check.sh | 655 ++++++++++++++++++\n tree-verify.c | 306 ++++++++\n tree-verify.h | 15 +\n 13 files changed, 1317 insertions(+)\n create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl\n create mode 100755 t/perf/p5412-connectivity-check.sh\n create mode 100755 t/t5412-connectivity-check.sh\n create mode 100644 tree-verify.c\n create mode 100644 tree-verify.h\n\ndiff --git a/Documentation/config/transfer.adoc b/Documentation/config/transfer.adoc\nindex f1ce50f4a6..b9939d3bde 100644\n--- a/Documentation/config/transfer.adoc\n+++ b/Documentation/config/transfer.adoc\n@@ -1,3 +1,23 @@\n+transfer.connectivityCheck::\n+\tChoose which algorithm to use for the connectivity check\n+\tperformed during object transfer operations such as\n+\tlinkgit:git-fetch[1] and linkgit:git-receive-pack[1].\n+\tThe connectivity check verifies that all objects reachable\n+\tfrom the incoming tips are available locally or, in a partial\n+\tclone, promised by a promisor remote.\n+\tThe variants are as follows:\n++\n+--\n+`full` (default);;\n+\tWalk the full object closure of the boundary commits.\n+`incremental`;;\n+\tVerify incoming commits by diffing their trees against parent\n+\ttrees, recursively descending only into entries that differ.\n+\tThe largest benefits occur when incoming commits change a\n+\tsmall fraction of a large tree closure.\n+\tFalls back to `full` for deepening fetches.\n+--\n+\n transfer.credentialsInUrl::\n \tA configured URL can contain plaintext credentials in the form\n \t`://:@/`. You may want\ndiff --git a/Documentation/rev-list-options.adoc b/Documentation/rev-list-options.adoc\nindex fd831f0ec6..7964b691c4 100644\n--- a/Documentation/rev-list-options.adoc\n+++ b/Documentation/rev-list-options.adoc\n@@ -1089,6 +1089,12 @@ we cannot get their Object ID though, an error will be raised.\n \tstronger than `--missing=allow-promisor` because it limits the\n \ttraversal, rather than just silencing errors about missing\n \tobjects.\n+\n+`--verify-trees-incremental`::\n+\t(For internal use only.) Verify tree connectivity\n+\tincrementally by comparing each commit's tree against its\n+\tparent trees. Used by `check_connected()` when\n+\t`transfer.connectivityCheck` is set to `incremental`.\n endif::git-rev-list[]\n \n `--no-walk[=(sorted|unsorted)]`::\ndiff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc\nindex d20bff6af6..0a8f370546 100644\n--- a/Documentation/technical/connectivity-check.adoc\n+++ b/Documentation/technical/connectivity-check.adoc\n@@ -107,3 +107,137 @@ When a new reference points to a non-commit object, such as a\n tag, tree, or blob, that object is not part of the commit walk.\n These non-commit tips are handled by the subsequent object\n traversal.\n+\n+Incremental connectivity check\n+------------------------------\n+\n+The incremental mode, selected by\n+`transfer.connectivityCheck=incremental`, avoids traversing the\n+full tree walk of the boundary commits. Instead, it verifies\n+each incoming commit's tree against the already-trusted trees of\n+its parents.\n+\n+Trust model\n+~~~~~~~~~~~\n+\n+A tree is trusted when its transitive object closure is known to\n+be connected. Trees reachable from commits on the\n+already-connected side of the boundary are therefore trusted.\n+\n+Incoming commits are processed with ancestors before descendants.\n+Once an incoming commit's tree has been verified, it is trusted\n+and can be used as a comparison base for later descendants.\n+\n+This gives an inductive correctness argument: every parent of the\n+commit currently being verified is either already connected or is\n+an earlier incoming commit whose tree has already been verified.\n+\n+Tree states\n+~~~~~~~~~~~\n+\n+The verifier tracks tree OIDs in three states:\n+\n+untrusted::\n+\tThe tree has not yet been established as connected. This\n+\tis the implicit state of an OID not present in the state\n+\tmap.\n+\n+trusted::\n+\tThe tree is known to have a connected transitive closure,\n+\tbut its direct entries have not yet been published into the\n+\tverifier's trusted object sets.\n+\n+expanded::\n+\tThe tree is trusted and its direct non-gitlink entries\n+\thave also been published into the trusted object sets.\n+\n+State transitions are monotonic: a tree may move from untrusted\n+to trusted to expanded, but never backwards. An untrusted tree\n+that is successfully verified goes directly to expanded.\n+\n+Blobs require only trusted/untrusted state: a blob becomes\n+trusted when it is found in a trusted tree or when its existence\n+and type have been verified directly.\n+\n+The trusted/expanded distinction is an optimization. An expanded\n+parent does not need to be reread merely to publish entries that\n+are already trusted, though it may still be read when same-path\n+subtree bases are needed for recursive comparison.\n+\n+Algorithm\n+~~~~~~~~~\n+\n+At a high level:\n+\n+ verify(commits):\n+ sort topologically (ancestors first)\n+ for each commit:\n+ mark parent root trees as trusted\n+ verify_tree(commit.tree, parent root trees)\n+\n+ verify_tree(tree, base_trees):\n+ if tree already trusted: return\n+ read tree, collect entries not already trusted\n+ for each available base tree:\n+ publish its entries as trusted\n+ record same-path subtrees as bases\n+ for each collected entry:\n+ if now trusted: skip\n+ if blob: verify blob connectivity and type\n+ if tree: verify_tree(entry, its recorded bases)\n+ mark tree as expanded\n+\n+The important ordering within `verify_tree` is that entries from\n+the new tree are collected before the base trees are scanned, but\n+are processed only afterwards. Trust learned from any base can\n+therefore eliminate work before recursive verification begins.\n+\n+Same-path parent subtrees are passed down as comparison bases\n+during recursive descent. If no comparison base is available,\n+the new subtree is verified from scratch.\n+\n+Worked example\n+~~~~~~~~~~~~~~\n+\n+Consider a commit that changes one file under `lib/` and moves an\n+unchanged subtree from `src/` to `dev/`:\n+\n+ Parent tree New tree\n+ +-- src/ (aaa) +-- dev/ (aaa)\n+ +-- lib/ (bbb) +-- lib/ (ccc)\n+ +-- foo.c (ddd) +-- foo.c (ddd)\n+ +-- bar.c (eee) +-- bar.c (fff)\n+\n+Scanning the parent makes `aaa` trusted even though it moved from\n+`src/` to `dev/`, so that subtree is skipped. The changed `ccc`\n+subtree is compared against its same-path parent `bbb`; scanning\n+`bbb` makes `ddd` and `eee` trusted, leaving only the new `fff`\n+blob to be checked.\n+\n+This illustrates two properties:\n+\n+* Trust is OID-based rather than path-based. An unchanged subtree\n+ is recognized after a move.\n+\n+* Same-path parent subtrees provide recursive comparison bases.\n+ These bases improve pruning efficiency but are not required for\n+ correctness; a new subtree can always be verified from scratch.\n+\n+Multiple parents\n+~~~~~~~~~~~~~~~~\n+\n+For a merge commit, root trees from all parents are comparison\n+bases. When several parents contain a same-path subtree, each\n+matching subtree is collected as a recursive comparison base.\n+\n+Entries published from any trusted parent become globally trusted,\n+so a matching tree or blob entry present in any parent can be\n+skipped while verifying the merge tree.\n+\n+Missing comparison bases\n+~~~~~~~~~~~~~~~~~~~~~~~~\n+\n+A promised base tree may not be locally available for comparison.\n+In that case the verifier skips that base and verifies the new\n+subtree without it. The missing comparison can reduce pruning but\n+does not affect correctness.\ndiff --git a/Makefile b/Makefile\nindex d4b775953d..aa5b4e2b84 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1357,6 +1357,7 @@ LIB_OBJS += trailer.o\n LIB_OBJS += transport-helper.o\n LIB_OBJS += transport.o\n LIB_OBJS += tree-diff.o\n+LIB_OBJS += tree-verify.o\n LIB_OBJS += tree-walk.o\n LIB_OBJS += tree.o\n LIB_OBJS += unpack-trees.o\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 6b596231ab..7741fdec9f 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -28,6 +28,7 @@\n #include \"commit-reach.h\"\n #include \"quote.h\"\n #include \"strbuf.h\"\n+#include \"tree-verify.h\"\n \n struct rev_list_info {\n \tstruct rev_info *revs;\n@@ -706,6 +707,7 @@ int cmd_rev_list(int argc,\n \tint bisect_find_all = 0;\n \tint use_bitmap_index = 0;\n \tint filter_provided_objects = 0;\n+\tint verify_trees_incremental = 0;\n \tconst char *show_progress = NULL;\n \tint ret = 0;\n \n@@ -748,6 +750,8 @@ int cmd_rev_list(int argc,\n \t\tif (!strcmp(arg, \"--exclude-promisor-objects\")) {\n \t\t\trepo->fetch_if_missing = 0;\n \t\t\trevs.exclude_promisor_objects = 1;\n+\t\t} else if (!strcmp(arg, \"--verify-trees-incremental\")) {\n+\t\t\tverify_trees_incremental = 1;\n \t\t} else if (skip_prefix(arg, \"--missing=\", &arg)) {\n \t\t\tparse_missing_action_value(repo, arg);\n \t\t} else if (!strcmp(arg, \"-z\")) {\n@@ -822,6 +826,8 @@ int cmd_rev_list(int argc,\n \n \t\tif (!strcmp(arg, \"--exclude-promisor-objects\"))\n \t\t\tcontinue; /* already handled above */\n+\t\tif (!strcmp(arg, \"--verify-trees-incremental\"))\n+\t\t\tcontinue; /* already handled above */\n \t\tif (skip_prefix(arg, \"--missing=\", &arg))\n \t\t\tcontinue; /* already handled above */\n \n@@ -935,6 +941,18 @@ int cmd_rev_list(int argc,\n \n \tprepare_maximal_independent(&revs);\n \n+\tif (verify_trees_incremental) {\n+\t\tstruct commit *commit;\n+\t\tstruct commit_list *new_commits = NULL;\n+\n+\t\twhile ((commit = get_revision(&revs)) != NULL)\n+\t\t\tcommit_list_insert(commit, &new_commits);\n+\n+\t\tverify_commits_incremental(repo, &new_commits,\n+\t\t\t\t\t revs.exclude_promisor_objects);\n+\t\tcommit_list_free(new_commits);\n+\t}\n+\n \tif (revs.tree_objects)\n \t\tmark_edges_uninteresting(&revs, show_edge, 0);\n \ndiff --git a/connected.c b/connected.c\nindex 929b9bd28d..e3dcd8e2b0 100644\n--- a/connected.c\n+++ b/connected.c\n@@ -1,6 +1,7 @@\n #define USE_THE_REPOSITORY_VARIABLE\n \n #include \"git-compat-util.h\"\n+#include \"config.h\"\n #include \"gettext.h\"\n #include \"hex.h\"\n #include \"odb.h\"\n@@ -67,6 +68,26 @@ static int check_connected_promisor(oid_iterate_fn fn,\n \treturn 1;\n }\n \n+static int incremental_check_applicable(struct check_connected_options *opt)\n+{\n+\tconst char *algorithm = NULL;\n+\n+\tif (repo_config_get_string_tmp(the_repository,\n+\t\t\t\t \"transfer.connectivitycheck\",\n+\t\t\t\t &algorithm))\n+\t\treturn 0;\n+\tif (!strcasecmp(algorithm, \"full\"))\n+\t\treturn 0;\n+\tif (strcasecmp(algorithm, \"incremental\"))\n+\t\tdie(_(\"unknown transfer.connectivityCheck algorithm '%s'\"),\n+\t\t algorithm);\n+\n+\tif (opt->is_deepening_fetch)\n+\t\treturn 0;\n+\n+\treturn 1;\n+}\n+\n /*\n * If we feed all the commits we want to verify to this command\n *\n@@ -133,6 +154,9 @@ int check_connected(oid_iterate_fn fn, void *cb_data,\n \tif (opt->progress)\n \t\tstrvec_pushf(&rev_list.args, \"--progress=%s\",\n \t\t\t _(\"Checking connectivity\"));\n+\tif (incremental_check_applicable(opt))\n+\t\tstrvec_push(&rev_list.args,\n+\t\t\t \"--verify-trees-incremental\");\n \n \trev_list.git_cmd = 1;\n \tif (opt->env)\ndiff --git a/meson.build b/meson.build\nindex 0a95d90d21..d94dedc26c 100644\n--- a/meson.build\n+++ b/meson.build\n@@ -562,6 +562,7 @@ libgit_sources = [\n 'transport-helper.c',\n 'transport.c',\n 'tree-diff.c',\n+ 'tree-verify.c',\n 'tree-walk.c',\n 'tree.c',\n 'unpack-trees.c',\ndiff --git a/t/meson.build b/t/meson.build\nindex 7f53cca7d1..19a8246c44 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -652,6 +652,7 @@ integration_tests = [\n 't5409-colorize-remote-messages.sh',\n 't5410-receive-pack.sh',\n 't5411-proc-receive-hook.sh',\n+ 't5412-connectivity-check.sh',\n 't5500-fetch-pack.sh',\n 't5501-fetch-push-alternates.sh',\n 't5502-quickfetch.sh',\ndiff --git a/t/perf/generate-repo-p5412-connectivity-check.perl b/t/perf/generate-repo-p5412-connectivity-check.perl\nnew file mode 100644\nindex 0000000000..9546996280\n--- /dev/null\n+++ b/t/perf/generate-repo-p5412-connectivity-check.perl\n@@ -0,0 +1,44 @@\n+#!/usr/bin/perl\n+#\n+# Generate a fast-import stream for p5412 connectivity check benchmarks.\n+#\n+# Usage: generate-repo-p5412-connectivity-check.perl\n+# [] []\n+#\n+# Creates one initial commit with dirs*files_per_dir files, then\n+# additional commits each modifying \n+# files in directories chosen round-robin from 1...\n+\n+use strict;\n+use warnings;\n+\n+my ($nd, $nf, $nc, $hot, $fpc) = @ARGV;\n+$hot = $nd if !$hot || $hot > $nd;\n+$fpc = 1 if !$fpc;\n+\n+sub data {\n+\tprintf \"data %d\\n%s\\n\", length($_[0]), $_[0];\n+}\n+\n+# Initial tree: one commit with nd*nf files.\n+printf \"commit refs/heads/main\\n\";\n+printf \"committer perf now\\n\";\n+data(\"initial\");\n+for my $d (1..$nd) {\n+\tfor my $f (1..$nf) {\n+\t\tprintf \"M 100644 inline d-%04d/f-%03d\\n\", $d, $f;\n+\t\tdata(sprintf \"%03d%03d\", $d, $f);\n+\t}\n+}\n+\n+# Subsequent commits (auto-chained by fast-import).\n+for my $i (1..$nc) {\n+\tprintf \"commit refs/heads/main\\n\";\n+\tprintf \"committer perf now\\n\";\n+\tdata(sprintf \"change-%03d\", $i);\n+\tfor my $j (0..$fpc-1) {\n+\t\tmy $d = (($i + $j) % $hot) + 1;\n+\t\tprintf \"M 100644 inline d-%04d/f-001\\n\", $d;\n+\t\tdata(sprintf \"c%d-%d\", $i, $j);\n+\t}\n+}\ndiff --git a/t/perf/p5412-connectivity-check.sh b/t/perf/p5412-connectivity-check.sh\nnew file mode 100755\nindex 0000000000..827643a847\n--- /dev/null\n+++ b/t/perf/p5412-connectivity-check.sh\n@@ -0,0 +1,92 @@\n+#!/bin/sh\n+\n+test_description='performance of connectivity check modes\n+\n+Compare the default and incremental rev-list connectivity modes\n+directly, avoiding pack transfer noise.\n+\n+Each repository has a flat tree of many directories with 100 files\n+in each. Three axes are scaled independently: tree size, commit\n+count, and files changed per commit.'\n+\n+. ./perf-lib.sh\n+\n+test_perf_fresh_repo\n+\n+generate=\"$TEST_DIRECTORY/perf/generate-repo-p5412-connectivity-check.perl\"\n+\n+# $1=dirs $2=files_per_dir $3=commits $4=hot_dirs (optional, default=all)\n+# $5=files_per_commit (optional, default=1)\n+test_perf_conn () {\n+\tlocal nd=\"$1\" nf=\"$2\" nc=\"$3\" hot=\"${4:-$1}\" fpc=\"${5:-1}\"\n+\tlocal total=$(($nd * $nf))\n+\tlocal name=\"repo-${nd}d-${nf}f-${nc}c-${hot}h-${fpc}fpc\"\n+\tlocal label=\"${total} files, ${nc} commits\"\n+\tif test \"$hot\" -lt \"$nd\"\n+\tthen\n+\t\tlabel=\"$label (${hot} hot dirs)\"\n+\tfi\n+\tif test \"$fpc\" -gt 1\n+\tthen\n+\t\tlabel=\"$label (${fpc} files/commit)\"\n+\tfi\n+\n+\ttest_expect_success \"setup $label\" '\n+\t\tif test -d '\"$name\"'\n+\t\tthen\n+\t\t\ttrue\n+\t\telse\n+\t\t\tgit init '\"$name\"' &&\n+\t\t\t\"$PERL_PATH\" '\"$generate\"' '\"$nd\"' '\"$nf\"' '\"$nc\"' '\"$hot\"' '\"$fpc\"' |\n+\t\t\tgit -C '\"$name\"' fast-import --date-format=now --quiet &&\n+\t\t\t(\n+\t\t\t\tcd '\"$name\"' &&\n+\t\t\t\tgit rev-parse main~'\"$nc\"' >../'\"${name}\"'_old &&\n+\t\t\t\tgit rev-parse main >../'\"${name}\"'_new &&\n+\t\t\t\tgit update-ref refs/heads/main \\\n+\t\t\t\t\t$(cat ../'\"${name}\"'_old) &&\n+\t\t\t\tgit repack -ad &&\n+\t\t\t\tgit config gc.auto 0\n+\t\t\t)\n+\t\tfi\n+\t'\n+\n+\ttest_perf \"$label (full)\" '\n+\t\tcat '\"${name}\"'_new |\n+\t\tgit -C '\"$name\"' rev-list \\\n+\t\t\t--objects --stdin --not --all --quiet \\\n+\t\t\t--exclude-promisor-objects\n+\t'\n+\n+\ttest_perf \"$label (incremental)\" '\n+\t\tcat '\"${name}\"'_new |\n+\t\tgit -C '\"$name\"' rev-list --verify-trees-incremental \\\n+\t\t\t--objects --stdin --not --all --quiet \\\n+\t\t\t--exclude-promisor-objects\n+\t'\n+}\n+\n+# Scaling tree size (10 commits, 10 files/commit).\n+test_perf_conn 50 100 10 50 10\n+test_perf_conn 500 100 10 500 10\n+test_perf_conn 2000 100 10 2000 10\n+test_perf_conn 8000 100 10 8000 10\n+\n+# Scaling commit count (200K files, 10 files/commit).\n+test_perf_conn 2000 100 1 2000 10\n+test_perf_conn 2000 100 10 2000 10\n+test_perf_conn 2000 100 100 2000 10\n+test_perf_conn 2000 100 500 2000 10\n+test_perf_conn 2000 100 3000 2000 10\n+test_perf_conn 2000 100 5000 2000 10\n+test_perf_conn 2000 100 10000 2000 10\n+\n+# Scaling files per commit (200K files, 10 commits).\n+test_perf_conn 2000 100 10 2000 1\n+test_perf_conn 2000 100 10 2000 10\n+test_perf_conn 2000 100 10 2000 100\n+test_perf_conn 2000 100 10 2000 500\n+test_perf_conn 2000 100 10 2000 1000\n+test_perf_conn 2000 100 10 2000 2000\n+\n+test_done\ndiff --git a/t/t5412-connectivity-check.sh b/t/t5412-connectivity-check.sh\nnew file mode 100755\nindex 0000000000..e276085e83\n--- /dev/null\n+++ b/t/t5412-connectivity-check.sh\n@@ -0,0 +1,655 @@\n+#!/bin/sh\n+\n+test_description='connectivity check (transfer.connectivityCheck)'\n+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main\n+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME\n+\n+. ./test-lib.sh\n+\n+test_oid_cache <<-\\EOF\n+missing sha1:0000000000000000000000000000000000000001\n+missing sha256:0000000000000000000000000000000000000000000000000000000000000001\n+EOF\n+\n+set_connectivity_check () {\n+\tgit -C \"$1\" config transfer.connectivityCheck \"$2\"\n+}\n+\n+# Run a connectivity check via rev-list directly. Uses $mode\n+# (set by the enclosing for-loop) to choose full or incremental.\n+check_connected () {\n+\tflags= &&\n+\tif test \"$mode\" = incremental\n+\tthen\n+\t\tflags=--verify-trees-incremental\n+\tfi &&\n+\tprintf '%s\\n' \"$@\" |\n+\tgit rev-list $flags \\\n+\t\t--objects --stdin --not --all --quiet \\\n+\t\t--exclude-promisor-objects\n+}\n+\n+# Run git with a temporary index, leaving the real index untouched.\n+tmpgit () {\n+\tGIT_INDEX_FILE=.git/tmp-idx git \"$@\"\n+}\n+\n+# Create a commit with one file changed, without modifying HEAD,\n+# index, or worktree. Prints the new commit OID on stdout.\n+# Usage: commit_with_change \n+commit_with_change () {\n+\tnew_blob=$(echo \"$3\" | git hash-object -w --stdin) &&\n+\ttmpgit read-tree \"$1\" &&\n+\ttmpgit update-index --replace \\\n+\t\t--cacheinfo \"100644,$new_blob,$2\" &&\n+\tnew_tree=$(tmpgit write-tree) &&\n+\trm -f .git/tmp-idx &&\n+\tgit commit-tree \"$new_tree\" -p \"$1\" -m \"modify $2\"\n+}\n+\n+# Check OIDs and optionally verify trace2 counts.\n+# Usage: check_connected_trace ...\n+# An empty string for or skips that assertion.\n+check_connected_trace () {\n+\ttrace_file=$1 trees=$2 blobs=$3 &&\n+\tshift 3 &&\n+\ttest_env GIT_TRACE2_EVENT=\"$(pwd)/$trace_file\" \\\n+\t\tcheck_connected \"$@\" &&\n+\tif test \"$mode\" != incremental\n+\tthen\n+\t\treturn\n+\tfi &&\n+\tif test -n \"$trees\"\n+\tthen\n+\t\ttest_trace2_data_singular connectivity trees_loaded \"$trees\" \\\n+\t\t\t<\"$trace_file\"\n+\tfi &&\n+\tif test -n \"$blobs\"\n+\tthen\n+\t\ttest_trace2_data_singular connectivity blobs_checked \"$blobs\" \\\n+\t\t\t<\"$trace_file\"\n+\tfi\n+}\n+\n+# Shared setup: a repo with several root-level files and nested dirs.\n+# The unchanged/ subtree (10 dirs x 10 files = 100 blobs, 11 trees)\n+# acts as a canary: any test asserting small tree/blob counts would\n+# fail dramatically if incremental accidentally walked into it.\n+\n+test_expect_success 'setup main repo' '\n+\tgit init main-repo &&\n+\t(\n+\t\tcd main-repo &&\n+\t\tfor i in $(test_seq 1 5)\n+\t\tdo\n+\t\t\techo \"file $i\" >\"file-$i.txt\" || return 1\n+\t\tdone &&\n+\t\tgit add file-*.txt &&\n+\t\tgit commit -m \"initial\" &&\n+\n+\t\tmkdir -p a/b/c &&\n+\t\techo deep >a/b/c/deep.txt &&\n+\t\techo other >a/other.txt &&\n+\t\tgit add a/b/c/deep.txt a/other.txt &&\n+\t\tgit commit -m \"add nested dirs\" &&\n+\n+\t\tfor i in $(test_seq 1 10)\n+\t\tdo\n+\t\t\td=\"unchanged/dir-$i\" &&\n+\t\t\tmkdir -p \"$d\" &&\n+\t\t\tfor j in $(test_seq 1 10)\n+\t\t\tdo\n+\t\t\t\techo \"$i $j\" >\"$d/file-$j.txt\" || return 1\n+\t\t\tdone\n+\t\tdone &&\n+\t\tgit add unchanged/ &&\n+\t\tgit commit -m \"add unchanged canary subtree\"\n+\t)\n+'\n+\n+test_expect_success 'setup replacement object repo' '\n+\tgit init replace-test &&\n+\t(\n+\t\tcd replace-test &&\n+\n+\t\ttest_commit --no-tag original file.txt &&\n+\t\toriginal=$(git rev-parse HEAD) &&\n+\t\torig_blob=$(git rev-parse HEAD:file.txt) &&\n+\n+\t\t# Orphan replacement commit with a different tree\n+\t\treplacement_tree=$(echo replaced | git hash-object -w --stdin |\n+\t\t\txargs -I{} git mktree <<-EOF\n+\t\t\t100644 blob {}\tfile.txt\n+\t\t\tEOF\n+\t\t) &&\n+\t\treplacement=$(git commit-tree -m \"replacement\" \\\n+\t\t\t\"$replacement_tree\") &&\n+\n+\t\tgit replace \"$original\" \"$replacement\" &&\n+\n+\t\t# Remove the original blob so only the replacement\n+\t\t# tree is complete.\n+\t\trm .git/objects/$(test_oid_to_path \"$orig_blob\") &&\n+\n+\t\t# Drop branch and HEAD so --not --all does not\n+\t\t# exclude the original commit.\n+\t\tgit update-ref -d refs/heads/main &&\n+\t\tgit update-ref -d HEAD &&\n+\n+\t\techo \"$original\" >.git/test-oid\n+\t)\n+'\n+\n+missing_oid=$(test_oid missing)\n+original_oid=$(cat replace-test/.git/test-oid)\n+\n+for mode in full incremental\n+do\n+\n+# Corruption detection: craft broken object graphs and verify detection.\n+# All tests use main-repo without modifying its refs or worktree.\n+\n+test_expect_success \"$mode: rejects commit with missing blob\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tbad_tree=$(printf \"100644 blob ${missing_oid}\\tfile.txt\\n\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tbad_commit=$(git commit-tree \"$bad_tree\" -p HEAD -m \"bad\") &&\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"missing blob object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: rejects commit with missing subtree\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tbad_tree=$(printf \"40000 tree ${missing_oid}\\tdir\\n\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tbad_commit=$(git commit-tree \"$bad_tree\" -p HEAD -m \"bad\") &&\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"bad tree object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies direct tree tip\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tbad_tree=$(printf \"100644 blob ${missing_oid}\\tfile.txt\\n\" |\n+\t\t\tgit mktree --missing) &&\n+\t\ttest_expect_code 128 check_connected \"$bad_tree\" 2>err &&\n+\t\ttest_grep \"missing blob object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies direct blob tip\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tblob_oid=$(echo \"hello\" | git hash-object -w --stdin) &&\n+\t\tcheck_connected \"$blob_oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: rejects missing direct blob tip\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$missing_oid\" 2>err\n+\t)\n+'\n+\n+test_expect_success PERL_TEST_HELPERS \\\n+\t\"$mode: rejects blob OID reused as tree entry\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\tblob_oid=$(git rev-parse HEAD:file-1.txt) &&\n+\t\tbin_oid=$(echo \"$blob_oid\" | hex2oct) &&\n+\n+\t\tbad_tree=$(printf \"40000 subdir\\0$bin_oid\" |\n+\t\t\tgit hash-object -t tree -w --stdin) &&\n+\t\tbad_commit=$(git commit-tree -p HEAD -m \"child\" \"$bad_tree\") &&\n+\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"not a tree\" err\n+\t)\n+'\n+\n+test_expect_success PERL_TEST_HELPERS \\\n+\t\"$mode: rejects tree OID reused as blob entry\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\ttree_oid=$(git rev-parse HEAD:a) &&\n+\t\tbin_oid=$(echo \"$tree_oid\" | hex2oct) &&\n+\n+\t\tbad_tree=$(printf \"100644 fakefile\\0$bin_oid\" |\n+\t\t\tgit hash-object -t tree -w --stdin) &&\n+\t\tbad_commit=$(git commit-tree -p HEAD -m \"child\" \"$bad_tree\") &&\n+\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"not a blob\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: checks multiple tips\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tc1=$(commit_with_change HEAD file-1.txt \"tip-a\") &&\n+\t\tc2=$(commit_with_change HEAD file-2.txt \"tip-b\") &&\n+\t\tgit tag -a -m \"tagged\" multi-tag \"$c1\" &&\n+\t\ttag_oid=$(git rev-parse multi-tag) &&\n+\t\tgit tag -d multi-tag &&\n+\t\tcheck_connected \"$c2\" \"$tag_oid\"\n+\t)\n+'\n+\n+# Tree-diff optimization: verify trace2 counts.\n+\n+test_expect_success \"$mode: handles root commit (no parents)\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tblob_oid=$(echo \"root-content\" | git hash-object -w --stdin) &&\n+\t\ttree_oid=$(printf \"100644 blob %s\\tfile.txt\\n\" \\\n+\t\t\t\"$blob_oid\" | git mktree) &&\n+\t\troot_oid=$(git commit-tree \"$tree_oid\" -m \"root\") &&\n+\n+\t\t# No parent trees, so the full tree is verified.\n+\t\t# 1 tree loaded (root), 1 blob checked.\n+\t\tcheck_connected_trace trace-root.txt 1 1 \"$root_oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles single file change\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\toid=$(commit_with_change HEAD file-1.txt \"changed\") &&\n+\n+\t\t# 2 trees loaded (new root + parent root), 1 blob checked.\n+\t\tcheck_connected_trace trace-flat.txt 2 1 \"$oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles nested change\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\toid=$(commit_with_change HEAD a/b/c/deep.txt \"deep-changed\") &&\n+\t\t# 4 new trees + 4 parent trees = 8 loaded, 1 blob checked.\n+\t\tcheck_connected_trace trace-nested.txt 8 1 \"$oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles change-then-revert\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tc1=$(commit_with_change HEAD file-1.txt \"revert-tmp\") &&\n+\t\tc2=$(commit_with_change \"$c1\" file-1.txt \"file 1\") &&\n+\t\tc3=$(commit_with_change \"$c2\" file-1.txt \"revert-final\") &&\n+\n+\t\t# c1: new root + parent root = 2 loads. c2: root matches\n+\t\t# HEAD (already trusted), skipped. c3: new root + parent\n+\t\t# already expanded = 1 load. Total: 3 trees, 2 blobs.\n+\t\tcheck_connected_trace trace-revert.txt 3 2 \"$c3\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles subtree moved to another path\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tmoved_tree=$(git ls-tree HEAD |\n+\t\t\tsed \"s/\ta$/\tmoved/\" |\n+\t\t\tgit mktree) &&\n+\t\tmoved=$(git commit-tree \"$moved_tree\" -p HEAD -m move) &&\n+\t\t# New root + parent root scanned, but the moved subtree\n+\t\t# (same OID) is trusted and not descended into.\n+\t\tcheck_connected_trace trace-move.txt 2 0 \"$moved\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles multi-parent merge\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tleft=$(commit_with_change HEAD file-1.txt left) &&\n+\t\tright=$(commit_with_change HEAD file-2.txt right) &&\n+\t\tgit update-ref refs/heads/left \"$left\" &&\n+\t\tgit update-ref refs/heads/right \"$right\" &&\n+\t\tleft_blob=$(git rev-parse \"$left:file-1.txt\") &&\n+\t\tright_blob=$(git rev-parse \"$right:file-2.txt\") &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --replace \\\n+\t\t\t--cacheinfo \"100644,$left_blob,file-1.txt\" &&\n+\t\ttmpgit update-index --replace \\\n+\t\t\t--cacheinfo \"100644,$right_blob,file-2.txt\" &&\n+\t\tmerge_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tmerge=$(git commit-tree \"$merge_tree\" \\\n+\t\t\t-p \"$left\" -p \"$right\" -m merge) &&\n+\t\t# Both parent root trees are scanned as bases, so\n+\t\t# blobs from each parent are trusted without ODB checks.\n+\t\tcheck_connected_trace trace-merge.txt 3 0 \"$merge\" &&\n+\t\tgit update-ref -d refs/heads/left &&\n+\t\tgit update-ref -d refs/heads/right\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles merge with incoming and boundary parents\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\t# parent1 is incoming (not a ref), HEAD is boundary.\n+\t\tparent1=$(commit_with_change HEAD file-1.txt merge-inc) &&\n+\t\tmerge=$(git commit-tree \\\n+\t\t\t\"$(git rev-parse \"$parent1^{tree}\")\" \\\n+\t\t\t-p \"$parent1\" -p HEAD -m merge-mixed) &&\n+\t\t# parent1 verified first (topo order): 2 trees, 1 blob.\n+\t\t# merge tree = parent1 tree (already trusted): 0 extra.\n+\t\tcheck_connected_trace trace-merge-inc.txt 2 1 \"$merge\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles gitlink entries (submodules)\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"160000,$missing_oid,my-submodule\" &&\n+\t\tgitlink_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tgitlink_commit=$(git commit-tree \"$gitlink_tree\" -p HEAD \\\n+\t\t\t-m \"add gitlink\") &&\n+\n+\t\t# Gitlink entries are skipped -- the missing submodule\n+\t\t# commit OID does not cause a failure.\n+\t\tcheck_connected_trace trace-gitlink.txt 2 0 \"$gitlink_commit\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles file-to-directory transition\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\t# Parent: \"foo\" is a blob at root.\n+\t\tblob_a=$(echo \"file-content\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_a,foo\" &&\n+\t\tparent_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tparent=$(git commit-tree \"$parent_tree\" -p HEAD \\\n+\t\t\t-m \"add foo as file\") &&\n+\n+\t\t# Child: \"foo\" becomes a directory (foo/bar.txt).\n+\t\tblob_b=$(echo \"dir-content\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree \"$parent\" &&\n+\t\ttmpgit update-index --remove foo &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_b,foo/bar.txt\" &&\n+\t\tchild_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tchild=$(git commit-tree \"$child_tree\" -p \"$parent\" \\\n+\t\t\t-m \"foo: file to directory\") &&\n+\t\tcheck_connected_trace trace-f2d.txt \"\" \"\" \"$child\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles directory-to-file transition\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\t# Parent: \"bar/baz.txt\" exists (bar is a directory).\n+\t\tblob_a=$(echo \"nested\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_a,bar/baz.txt\" &&\n+\t\tparent_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tparent=$(git commit-tree \"$parent_tree\" -p HEAD \\\n+\t\t\t-m \"add bar as directory\") &&\n+\n+\t\t# Child: \"bar\" becomes a plain file.\n+\t\tblob_b=$(echo \"flat\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree \"$parent\" &&\n+\t\ttmpgit update-index --remove bar/baz.txt &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_b,bar\" &&\n+\t\tchild_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tchild=$(git commit-tree \"$child_tree\" -p \"$parent\" \\\n+\t\t\t-m \"bar: directory to file\") &&\n+\t\tcheck_connected_trace trace-d2f.txt \"\" \"\" \"$child\"\n+\t)\n+'\n+\n+# Replacement objects.\n+\n+test_expect_success \"$mode: accepts with replacement objects\" '\n+\t(\n+\t\tcd replace-test &&\n+\t\tcheck_connected \"$original_oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: rejects without replacement objects\" '\n+\t(\n+\t\tcd replace-test &&\n+\t\tGIT_NO_REPLACE_OBJECTS=1 &&\n+\t\texport GIT_NO_REPLACE_OBJECTS &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$original_oid\" 2>err &&\n+\t\ttest_grep \"missing blob object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: accepts missing promised blob\" '\n+\ttest_when_finished \"rm -rf prom-src prom-server.git prom-client\" &&\n+\tgit init prom-src &&\n+\ttest_commit -C prom-src --no-tag base file.txt original &&\n+\ttest_commit -C prom-src --no-tag \"add file2\" file2.txt extra &&\n+\tgit clone --bare prom-src prom-server.git &&\n+\tgit -C prom-server.git config uploadpack.allowfilter true &&\n+\tgit -C prom-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --no-checkout --filter=blob:none \\\n+\t\t\"file://$(pwd)/prom-server.git\" prom-client &&\n+\t(\n+\t\tcd prom-client &&\n+\t\tpromised_blob=$(git rev-parse HEAD:file2.txt) &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_blob\" &&\n+\t\tnew_tree=$(printf \"100644 blob %s\\tnewname.txt\\n\" \\\n+\t\t\t\"$promised_blob\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tnew_commit=$(git commit-tree \"$new_tree\" \\\n+\t\t\t-p HEAD -m \"reuse promised blob\") &&\n+\t\tcheck_connected \"$new_commit\" &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_blob\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: accepts missing promised tree\" '\n+\ttest_when_finished \"rm -rf prom-tree-src prom-tree-server.git prom-tree-client\" &&\n+\tgit init prom-tree-src &&\n+\tmkdir -p prom-tree-src/a/b &&\n+\ttest_commit -C prom-tree-src --no-tag \"nested dirs\" a/b/file.txt deep &&\n+\tgit clone --bare prom-tree-src prom-tree-server.git &&\n+\tgit -C prom-tree-server.git config uploadpack.allowfilter true &&\n+\tgit -C prom-tree-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --no-checkout --filter=tree:1 \\\n+\t\t\"file://$(pwd)/prom-tree-server.git\" prom-tree-client &&\n+\t(\n+\t\tcd prom-tree-client &&\n+\t\tpromised_tree=$(git ls-tree HEAD -- a |\n+\t\t\tawk \"{print \\$3}\") &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_tree\" &&\n+\t\tnew_tree=$(printf \"40000 tree %s\\trenamed\\n\" \\\n+\t\t\t\"$promised_tree\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tnew_commit=$(git commit-tree \"$new_tree\" \\\n+\t\t\t-p HEAD -m \"reuse promised tree\") &&\n+\t\tcheck_connected \"$new_commit\" &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_tree\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies new subtree when parent subtree is promised\" '\n+\ttest_when_finished \"rm -rf prom-base-src prom-base-server.git prom-base-client\" &&\n+\tgit init prom-base-src &&\n+\tmkdir -p prom-base-src/a &&\n+\ttest_commit -C prom-base-src --no-tag \"base\" a/file.txt deep &&\n+\tgit clone --bare prom-base-src prom-base-server.git &&\n+\tgit -C prom-base-server.git config uploadpack.allowfilter true &&\n+\tgit -C prom-base-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --no-checkout --filter=tree:1 \\\n+\t\t\"file://$(pwd)/prom-base-server.git\" prom-base-client &&\n+\t(\n+\t\tcd prom-base-client &&\n+\t\tparent_subtree=$(git ls-tree HEAD -- a |\n+\t\t\tawk \"{print \\$3}\") &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$parent_subtree\" &&\n+\t\tnew_blob=$(echo \"local-content\" | git hash-object -w --stdin) &&\n+\t\tnew_subtree=$(printf \"100644 blob %s\\tfile.txt\\n\" \\\n+\t\t\t\"$new_blob\" | git mktree) &&\n+\t\tnew_root=$(printf \"40000 tree %s\\ta\\n\" \\\n+\t\t\t\"$new_subtree\" | git mktree) &&\n+\t\tnew_commit=$(git commit-tree \"$new_root\" \\\n+\t\t\t-p HEAD -m \"replace promised subtree\") &&\n+\t\tcheck_connected \"$new_commit\" &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$parent_subtree\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies local commit in partial clone\" '\n+\ttest_when_finished \"rm -rf pc-src pc-server.git pc-client\" &&\n+\tgit init pc-src &&\n+\ttest_commit -C pc-src --no-tag base file.txt &&\n+\tgit clone --bare pc-src pc-server.git &&\n+\tgit -C pc-server.git config uploadpack.allowfilter true &&\n+\tgit -C pc-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --filter=blob:none \\\n+\t\t\"file://$(pwd)/pc-server.git\" pc-client &&\n+\t(\n+\t\tcd pc-client &&\n+\t\tlocal_commit=$(commit_with_change HEAD file.txt local-content) &&\n+\t\tcheck_connected \"$local_commit\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: respects shallow boundary\" '\n+\ttest_when_finished \"rm -rf shallow-src shallow\" &&\n+\tgit init shallow-src &&\n+\ttest_commit -C shallow-src --no-tag base file content-1 &&\n+\tmkdir shallow-src/sub &&\n+\ttest_commit -C shallow-src --no-tag change sub/other content-2 &&\n+\tgit clone --depth=1 \"file://$(pwd)/shallow-src\" shallow &&\n+\t(\n+\t\tcd shallow &&\n+\t\ttip=$(git rev-parse HEAD) &&\n+\t\tgit for-each-ref --format=\"delete %(refname)\" |\n+\t\t\tgit update-ref --no-deref --stdin &&\n+\t\tcheck_connected \"$tip\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: deepening fetch succeeds\" '\n+\ttest_when_finished \"rm -rf deepen-src deepen-server.git deepen-client\" &&\n+\tgit init deepen-src &&\n+\ttest_commit -C deepen-src --no-tag c1 file.txt &&\n+\ttest_commit -C deepen-src --no-tag c2 file.txt &&\n+\ttest_commit -C deepen-src --no-tag c3 file.txt &&\n+\tgit clone --bare deepen-src deepen-server.git &&\n+\tgit clone --depth=1 \"file://$(pwd)/deepen-server.git\" deepen-client &&\n+\tset_connectivity_check deepen-client $mode &&\n+\ttest -f deepen-client/.git/shallow &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/deepen-trace.txt\" \\\n+\t\tgit -C deepen-client fetch --deepen=2 origin main &&\n+\t# Incremental falls back to full for deepening fetches,\n+\t# so the trees_loaded event should not appear.\n+\ttest_grep ! trees_loaded deepen-trace.txt\n+'\n+\n+test_expect_success \"$mode: malformed tree detected\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\techo abc >malformed-tree &&\n+\t\tmalformed_tree=$(git hash-object --literally -t tree -w \\\n+\t\t\tmalformed-tree) &&\n+\t\tmalformed_commit=$(git commit-tree \"$malformed_tree\" \\\n+\t\t\t-p HEAD -m malformed) &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$malformed_commit\" 2>err\n+\t)\n+'\n+\n+test_expect_success PERL_TEST_HELPERS \\\n+\t\"$mode: mid-tree corruption detected\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\t# Build a tree with one valid entry followed by garbage.\n+\t\tblob_oid=$(echo \"valid\" | git hash-object -w --stdin) &&\n+\t\tbin_oid=$(echo \"$blob_oid\" | hex2oct) &&\n+\t\tprintf \"100644 good\\0${bin_oid}GARBAGE\" >corrupt-mid-tree &&\n+\t\tcorrupt_tree=$(git hash-object --literally -t tree -w \\\n+\t\t\tcorrupt-mid-tree) &&\n+\t\tcorrupt_commit=$(git commit-tree \"$corrupt_tree\" \\\n+\t\t\t-p HEAD -m \"mid-tree corruption\") &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$corrupt_commit\" 2>err &&\n+\t\ttest_grep \"too-short tree object\" err\n+\t)\n+'\n+\n+done\n+\n+# Algorithm selection.\n+\n+test_expect_success 'invalid transfer.connectivityCheck is rejected' '\n+\ttest_when_finished \"rm -rf invalid-cfg-src invalid-cfg-dst\" &&\n+\tgit init invalid-cfg-src &&\n+\ttest_commit -C invalid-cfg-src --no-tag base file.txt &&\n+\tgit clone invalid-cfg-src invalid-cfg-dst &&\n+\ttest_commit -C invalid-cfg-src --no-tag update file.txt updated &&\n+\tgit -C invalid-cfg-dst config transfer.connectivityCheck bogus &&\n+\ttest_must_fail git -C invalid-cfg-dst fetch origin main 2>err &&\n+\ttest_grep \"unknown transfer.connectivityCheck\" err\n+'\n+\n+test_expect_success 'push uses incremental when configured' '\n+\ttest_when_finished \"rm -rf int-src int-dst.git\" &&\n+\tgit init int-src &&\n+\ttest_commit -C int-src --no-tag base file.txt &&\n+\tgit clone --bare int-src int-dst.git &&\n+\ttest_commit -C int-src --no-tag update file.txt updated &&\n+\tset_connectivity_check int-dst.git incremental &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/push-trace.txt\" \\\n+\t\tgit -C int-src push ../int-dst.git main &&\n+\ttest_trace2_data_singular connectivity trees_loaded 2 \\\n+\t\t kh_val(m, pos))\n+\t\tkh_val(m, pos) = state;\n+}\n+\n+struct work_item {\n+\tstruct name_entry entry;\n+\tstruct oid_array parent_trees;\n+};\n+\n+struct verify_state {\n+\tkh_oid_tree_t *trees;\n+\tstruct oidset trusted_blobs;\n+\tint trees_loaded;\n+\tint blobs_checked;\n+\tint exclude_promisor_objects;\n+};\n+\n+/*\n+ * Merge-walk the work list against one base tree entry, recording\n+ * same-path parent subtrees as recursive comparison bases.\n+ * Returns the updated work-list cursor.\n+ */\n+static size_t collect_subtree_bases(struct work_item *work, size_t nr_work,\n+\t\t\t\t size_t wi, const struct name_entry *entry)\n+{\n+\twhile (wi < nr_work) {\n+\t\tint cmp = base_name_compare(\n+\t\t\twork[wi].entry.path, work[wi].entry.pathlen,\n+\t\t\twork[wi].entry.mode,\n+\t\t\tentry->path, entry->pathlen,\n+\t\t\tentry->mode);\n+\t\tif (cmp > 0)\n+\t\t\tbreak;\n+\t\tif (cmp < 0) {\n+\t\t\twi++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (S_ISDIR(work[wi].entry.mode) &&\n+\t\t S_ISDIR(entry->mode))\n+\t\t\toid_array_append(&work[wi].parent_trees,\n+\t\t\t\t\t &entry->oid);\n+\t\treturn wi + 1;\n+\t}\n+\treturn wi;\n+}\n+\n+static void verify_blob(struct repository *repo,\n+\t\t\tconst struct object_id *oid,\n+\t\t\tstruct verify_state *vs)\n+{\n+\tint type;\n+\n+\tif (oidset_contains(&vs->trusted_blobs, oid))\n+\t\treturn;\n+\n+\tvs->blobs_checked++;\n+\ttype = odb_read_object_info(repo->objects, oid, NULL);\n+\tif (type == OBJ_BLOB) {\n+\t\toidset_insert(&vs->trusted_blobs, oid);\n+\t\treturn;\n+\t}\n+\tif (type >= 0)\n+\t\tdie(_(\"object %s is a %s, not a blob\"),\n+\t\t oid_to_hex(oid), type_name(type));\n+\tif (vs->exclude_promisor_objects &&\n+\t is_promisor_object(repo, oid))\n+\t\treturn;\n+\tdie(_(\"missing blob object '%s'\"), oid_to_hex(oid));\n+}\n+\n+static void *read_tree_object(struct object_database *odb,\n+\t\t\t const struct object_id *oid,\n+\t\t\t size_t *sizep)\n+{\n+\tenum object_type type;\n+\tvoid *buf = odb_read_object(odb, oid, &type, sizep);\n+\n+\tif (buf && type != OBJ_TREE) {\n+\t\tfree(buf);\n+\t\tdie(_(\"object %s is a %s, not a tree\"),\n+\t\t oid_to_hex(oid), type_name(type));\n+\t}\n+\treturn buf;\n+}\n+\n+static void verify_tree(struct repository *repo,\n+\t\t\tconst struct object_id *new_tree_oid,\n+\t\t\tconst struct oid_array *base_trees,\n+\t\t\tstruct verify_state *vs, int depth)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct work_item *work = NULL;\n+\tsize_t nr_work = 0, alloc_work = 0;\n+\tint need_subtree_bases = 0;\n+\tsize_t i, tree_size;\n+\tvoid *tree_buf;\n+\n+\tif (depth > repo->settings.max_allowed_tree_depth)\n+\t\tdie(_(\"exceeded maximum allowed tree depth\"));\n+\n+\tif (tree_map_get(vs->trees, new_tree_oid) >= TREE_TRUSTED)\n+\t\treturn;\n+\n+\ttree_buf = read_tree_object(repo->objects, new_tree_oid, &tree_size);\n+\tif (!tree_buf) {\n+\t\tif (vs->exclude_promisor_objects &&\n+\t\t is_promisor_object(repo, new_tree_oid))\n+\t\t\treturn;\n+\t\tdie(_(\"bad tree object %s\"),\n+\t\t oid_to_hex(new_tree_oid));\n+\t}\n+\n+\tvs->trees_loaded++;\n+\tinit_tree_desc(&desc, new_tree_oid, tree_buf, tree_size);\n+\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tif (S_ISGITLINK(entry.mode))\n+\t\t\tcontinue;\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tif (tree_map_get(vs->trees, &entry.oid) >= TREE_TRUSTED)\n+\t\t\t\tcontinue;\n+\t\t\tneed_subtree_bases = 1;\n+\t\t} else {\n+\t\t\tif (oidset_contains(&vs->trusted_blobs, &entry.oid))\n+\t\t\t\tcontinue;\n+\t\t}\n+\t\tALLOC_GROW(work, nr_work + 1, alloc_work);\n+\t\tmemset(&work[nr_work], 0, sizeof(work[nr_work]));\n+\t\twork[nr_work].entry = entry;\n+\t\tnr_work++;\n+\t}\n+\n+\tif (!nr_work) {\n+\t\tfree(tree_buf);\n+\t\tgoto done;\n+\t}\n+\n+\tfor (i = 0; base_trees && i < base_trees->nr; i++) {\n+\t\tconst struct object_id *base_oid = &base_trees->oid[i];\n+\t\tint expanded = tree_map_get(vs->trees, base_oid) >= TREE_EXPANDED;\n+\t\tstruct tree_desc base_desc;\n+\t\tstruct name_entry scan_entry;\n+\t\tsize_t wi = 0, base_size;\n+\t\tvoid *base_buf;\n+\n+\t\tif (expanded && !need_subtree_bases)\n+\t\t\tcontinue;\n+\n+\t\tbase_buf = read_tree_object(repo->objects, base_oid,\n+\t\t\t\t\t &base_size);\n+\t\tif (!base_buf) {\n+\t\t\tif (vs->exclude_promisor_objects &&\n+\t\t\t is_promisor_object(repo, base_oid))\n+\t\t\t\tcontinue;\n+\t\t\tdie(_(\"bad tree object %s\"),\n+\t\t\t oid_to_hex(base_oid));\n+\t\t}\n+\n+\t\tvs->trees_loaded++;\n+\t\tinit_tree_desc(&base_desc, base_oid, base_buf, base_size);\n+\n+\t\twhile (tree_entry(&base_desc, &scan_entry)) {\n+\t\t\tif (S_ISGITLINK(scan_entry.mode))\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (need_subtree_bases)\n+\t\t\t\twi = collect_subtree_bases(work, nr_work,\n+\t\t\t\t\t\t\t wi, &scan_entry);\n+\n+\t\t\tif (!expanded) {\n+\t\t\t\tif (S_ISDIR(scan_entry.mode))\n+\t\t\t\t\ttree_map_add(vs->trees,\n+\t\t\t\t\t\t &scan_entry.oid,\n+\t\t\t\t\t\t TREE_TRUSTED);\n+\t\t\t\telse\n+\t\t\t\t\toidset_insert(&vs->trusted_blobs,\n+\t\t\t\t\t\t &scan_entry.oid);\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!expanded)\n+\t\t\ttree_map_add(vs->trees, base_oid, TREE_EXPANDED);\n+\n+\t\tfree(base_buf);\n+\t}\n+\n+\tfor (i = 0; i < nr_work; i++) {\n+\t\tif (S_ISDIR(work[i].entry.mode))\n+\t\t\tverify_tree(repo, &work[i].entry.oid,\n+\t\t\t\t &work[i].parent_trees, vs,\n+\t\t\t\t depth + 1);\n+\t\telse\n+\t\t\tverify_blob(repo, &work[i].entry.oid, vs);\n+\t}\n+\n+\tfree(tree_buf);\n+\n+done:\n+\ttree_map_add(vs->trees, new_tree_oid, TREE_EXPANDED);\n+\tfor (i = 0; i < nr_work; i++)\n+\t\toid_array_clear(&work[i].parent_trees);\n+\tfree(work);\n+}\n+\n+static void verify_commit_tree(struct repository *repo,\n+\t\t\t struct commit *commit,\n+\t\t\t struct verify_state *vs)\n+{\n+\tstruct oid_array base_trees = OID_ARRAY_INIT;\n+\tstruct commit_list *p;\n+\n+\t/*\n+\t * Parent trees are trusted: boundary parents are already\n+\t * connected, and earlier incoming parents were verified\n+\t * first due to the topological processing order.\n+\t */\n+\tfor (p = commit->parents; p; p = p->next) {\n+\t\tconst struct object_id *tree_oid;\n+\t\tparse_commit_or_die(p->item);\n+\t\ttree_oid = get_commit_tree_oid(p->item);\n+\t\ttree_map_add(vs->trees, tree_oid, TREE_TRUSTED);\n+\t\toid_array_append(&base_trees, tree_oid);\n+\t}\n+\n+\tverify_tree(repo, get_commit_tree_oid(commit),\n+\t\t &base_trees, vs, 0);\n+\toid_array_clear(&base_trees);\n+}\n+\n+void verify_commits_incremental(struct repository *repo,\n+\t\t\t\tstruct commit_list **commits,\n+\t\t\t\tint exclude_promisor_objects)\n+{\n+\tstruct verify_state vs = { 0 };\n+\tstruct commit_list *iter;\n+\tunsigned nr_before;\n+\n+\tvs.trees = kh_init_oid_tree();\n+\tvs.exclude_promisor_objects = exclude_promisor_objects;\n+\n+\t/*\n+\t * Ancestors must be verified before descendants so that parent\n+\t * trees can be trusted without re-verification. Sort explicitly\n+\t * rather than relying on the caller's ordering.\n+\t *\n+\t * sort_in_topological_order() silently drops cycle members,\n+\t * so explicitly check if the size has changed.\n+\t */\n+\tnr_before = commit_list_count(*commits);\n+\tsort_in_topological_order(commits, REV_SORT_IN_GRAPH_ORDER);\n+\tif (commit_list_count(*commits) < nr_before)\n+\t\tdie(_(\"cycle detected in incoming commit graph\"));\n+\n+\t*commits = commit_list_reverse(*commits);\n+\n+\tfor (iter = *commits; iter; iter = iter->next)\n+\t\tverify_commit_tree(repo, iter->item, &vs);\n+\n+\tkh_destroy_oid_tree(vs.trees);\n+\toidset_clear(&vs.trusted_blobs);\n+\ttrace2_data_intmax(\"connectivity\", repo,\n+\t\t\t \"trees_loaded\", vs.trees_loaded);\n+\ttrace2_data_intmax(\"connectivity\", repo,\n+\t\t\t \"blobs_checked\", vs.blobs_checked);\n+}\ndiff --git a/tree-verify.h b/tree-verify.h\nnew file mode 100644\nindex 0000000000..6aadadff70\n--- /dev/null\n+++ b/tree-verify.h\n@@ -0,0 +1,15 @@\n+#ifndef TREE_VERIFY_H\n+#define TREE_VERIFY_H\n+\n+struct commit_list;\n+struct repository;\n+\n+/*\n+ * Verify trees of commits incrementally against their parents.\n+ * Dies on verification failure.\n+ */\n+void verify_commits_incremental(struct repository *repo,\n+\t\t\t\tstruct commit_list **commits,\n+\t\t\t\tint exclude_promisor_objects);\n+\n+#endif /* TREE_VERIFY_H */\n-- \ngitgitgadget\n"},{"id":"552711","messageId":"xmqqmrtj7tp2.fsf@gitster.g","threadId":"66326","inReplyTo":"pull.2211.git.1789379276.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/2] connected: add incremental connectivity check","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-09-14T15:12:41Z","receivedAt":"2026-09-14T15:12:44Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> This series adds an incremental mode for the connectivity check, gated\n> behind transfer.connectivityCheck=incremental (no expected changes unless\n> you opt in).\n>\n> The intent is to solve the problem of the connectivity check slowing down as\n> the number of reachable objects from the boundary grows.\n\nExciting benchmarks.\n"},{"id":"552712","messageId":"xmqqh5jr7t1h.fsf@gitster.g","threadId":"66326","inReplyTo":"ebe6c90cc58b9e1f64c9bec4a18e8cb3ce9be1b2.1789379276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/2] connected: add incremental connectivity check via rev-list","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-09-14T15:26:50Z","receivedAt":"2026-09-14T15:26:52Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" \nwrites:\n\n> +static void verify_blob(struct repository *repo,\n> +\t\t\tconst struct object_id *oid,\n> +\t\t\tstruct verify_state *vs)\n> +{\n> +\tint type;\n> +\n> +\tif (oidset_contains(&vs->trusted_blobs, oid))\n> +\t\treturn;\n> +\n> +\tvs->blobs_checked++;\n> +\ttype = odb_read_object_info(repo->objects, oid, NULL);\n> +\tif (type == OBJ_BLOB) {\n> +\t\toidset_insert(&vs->trusted_blobs, oid);\n> +\t\treturn;\n> +\t}\n> +\tif (type >= 0)\n> +\t\tdie(_(\"object %s is a %s, not a blob\"),\n> +\t\t oid_to_hex(oid), type_name(type));\n> +\tif (vs->exclude_promisor_objects &&\n> +\t is_promisor_object(repo, oid))\n> +\t\treturn;\n> +\tdie(_(\"missing blob object '%s'\"), oid_to_hex(oid));\n> +}\n\nI wonder if this is_promisor_object() call comes a bit too late, as\nwe earlier already have called odb_read_object_info() which may have\nfetched it lazily from the promisor remote? Or do we globally\ndisable promisor_remote_get_direct() call somehow without having to\npass OBJECT_INFO_SKIP_FETCH_OBJECT flag?\n\n> +static void verify_commit_tree(struct repository *repo,\n> +\t\t\t struct commit *commit,\n> +\t\t\t struct verify_state *vs)\n> +{\n> +\tstruct oid_array base_trees = OID_ARRAY_INIT;\n> +\tstruct commit_list *p;\n> +\n> +\t/*\n> +\t * Parent trees are trusted: boundary parents are already\n> +\t * connected, and earlier incoming parents were verified\n> +\t * first due to the topological processing order.\n> +\t */\n> +\tfor (p = commit->parents; p; p = p->next) {\n> +\t\tconst struct object_id *tree_oid;\n> +\t\tparse_commit_or_die(p->item);\n> +\t\ttree_oid = get_commit_tree_oid(p->item);\n> +\t\ttree_map_add(vs->trees, tree_oid, TREE_TRUSTED);\n> +\t\toid_array_append(&base_trees, tree_oid);\n> +\t}\n> +\n> +\tverify_tree(repo, get_commit_tree_oid(commit),\n> +\t\t &base_trees, vs, 0);\n> +\toid_array_clear(&base_trees);\n> +}\n\nDo we assume that we do not have to deal with repository corruption\nin any graceful way? I am just wondering what happens when\nget_commit_tree_oid() yields NULL after parse_commit_or_die() finds\np->item is a valid-looking commit object but the tree within it is\nnot, and we end up passing NULL to tree_map_add(), perhaps?\n\nThe same potential issue may exist in the get_commit_tree_oid() call\noutside the look at the end on the incoming commit's tree.\n"},{"id":"552723","messageId":"CAL71e4My+maYAtWbkoHXvsm=qhCmao7K_7mLV5wg1FyKTa3u8A@mail.gmail.com","threadId":"66326","inReplyTo":"xmqqh5jr7t1h.fsf@gitster.g","subject":"Re: [PATCH 2/2] connected: add incremental connectivity check via rev-list","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-09-14T17:46:05Z","receivedAt":"2026-09-14T17:46:19Z","isPatch":true,"body":"On Mon, 14 Sept 2026 at 17:26, Junio C Hamano wrote:\n>\n> \"Kristofer Karlsson via GitGitGadget\" \n> writes:\n>\n> I wonder if this is_promisor_object() call comes a bit too late, as\n> we earlier already have called odb_read_object_info() which may have\n> fetched it lazily from the promisor remote? Or do we globally\n> disable promisor_remote_get_direct() call somehow without having to\n> pass OBJECT_INFO_SKIP_FETCH_OBJECT flag?\n\nYes, I think it's safe due to the following mechanism:\n\n1. If promisors exist, the connectivity-check will invoke\n rev-list with --exclude-promisor-objects.\n2. rev-list in turn sets repo->fetch_if_missing = 0 on startup.\n3. Then the odb read goes down into do_oid_object_info_extended()\n which respects that flag.\n\nHowever, my paranoia kicked in so I re-ran my test for this,\nafter adding some temporary code inside\nverify_commits_incremental():\n\n repo->fetch_if_missing = 1;\n\nAnd fortunately, one of the tests failed as expected.\n\n Exactly 1 failure out of 62 tests: test 53\n \"incremental: verifies new subtree when parent subtree is\n promised\".\n\nAnd the relevant assertion is this one:\n\n test_must_fail env GIT_NO_LAZY_FETCH=1 \\\n git cat-file -e \"$parent_subtree\"\n\nwhich ensures that the object was never fetched.\n\nHowever, the test only catches this scenario for trees,\nnot blobs -- that's an oversight, I will add a matching\ntest for blobs too.\n\nI think the code technically works as-is, but I could also try\nto rewrite the code to stop depending on odb_read_object_info()\nand instead use odb_read_object_info_extended() which allows\nme to pass the flags. That gives us belts and suspenders, which\nmay be nicer here.\n\n> Do we assume that we do not have to deal with repository corruption\n> in any graceful way? I am just wondering what happens when\n> get_commit_tree_oid() yields NULL after parse_commit_or_die() finds\n> p->item is a valid-looking commit object but the tree within it is\n> not, and we end up passing NULL to tree_map_add(), perhaps?\n>\n> The same potential issue may exist in the get_commit_tree_oid() call\n> outside the look at the end on the incoming commit's tree.\n\nYou're right, this is an oversight.\nI think I incorrectly assumed that parse_commit_or_die()\nwould catch any malformed commit.\n\nI will add a NULL check and a die()-exit at the two call sites\nin verify_commit_tree()\n\n die(_(\"unable to load root tree for commit %s\"),\n oid_to_hex(&commit->object.oid));\n\nThanks for spotting these errors,\nKristofer\n"},{"id":"553462","messageId":"pull.2211.v2.git.1790600552.gitgitgadget@gmail.com","threadId":"66326","inReplyTo":"pull.2211.git.1789379276.gitgitgadget@gmail.com","subject":"[PATCH v2 0/2] connected: add incremental connectivity check","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-09-28T13:02:30Z","receivedAt":"2026-09-28T13:02:39Z","isPatch":true,"body":"This series adds an incremental mode for the connectivity check, gated\nbehind transfer.connectivityCheck=incremental (no expected changes unless\nyou opt in).\n\nThe intent is to solve the problem of the connectivity check slowing down as\nthe number of reachable objects from the boundary grows.\n\nIt relates to the RFC I sent out earlier:\n\n[RFC] check_connected: toward incoming-proportional cost\nhttps://lore.kernel.org/git/CAL71e4Nf=-zCrfN7ghEVGq11irajJhtdxYZgKe0Ycux0qs1ZvQ@mail.gmail.com/\n\n\n\nDesign\n======\n\nThe verifier runs inside the same rev-list subprocess that check_connected()\nalready spawns, triggered by a new internal flag --verify-trees-incremental.\nAfter get_revision() collects the incoming commits, the verifier processes\nthem in topological order (ancestors before descendants).\n\nThe idea is to keep a set of trusted objects, shared across the incoming\ncommits, that grows over time. We visit the new/untrusted commit trees and\ndo a comparison walk over the trees of their parents. Entries discovered on\nthe trusted parent side are remembered as trusted, which lets later\nverification skip matching objects and avoid descending into unchanged\nsubtrees.\n\nMore algorithmic details are in\nDocumentation/technical/connectivity-check.adoc.\n\n\nBenchmarks\n==========\n\nI'll just mention a short summary here, to avoid repeating what's already in\nthe commit message. The incremental mode is faster than the full mode when\nthere are few commits to verify and when the active object tree is large. In\nthe happy case, the work tracks the changed paths and their comparison trees\nrather than the full reachable object closure, which substantially reduces\nthe dependence on total repository size. I've seen speedups up to around 20x\nfor the synthetic perf tests.\n\nRunning against a large real-world repo (3.4 GB boundary closure), the\nnumbers are more dramatic. All timings use rev-list directly with --not\nHEADN, isolating the tree verification cost from the boundary-finding cost:\n\ncommits full incr. speedup full RSS incr. RSS\n 1 1.9s 0.01s 190x 3.4 GB 14 MB\n 10 1.9s 0.04s 48x 3.4 GB 125 MB\n 100 1.9s 0.37s 5x 3.4 GB 1.1 GB\n\n\nThe full mode takes ~1.9s regardless of commit count because it is dominated\nby walking the boundary closure. Incremental scales with the number of\nincoming commits and the paths they touch. Memory follows the same pattern:\nincremental uses a fraction of the full mode's RSS for small pushes,\nconverging only when many commits are verified.\n\nThere are also regression cases in the synthetic fixtures. With long\nincoming histories, the extra parent-tree scans accumulate; in the synthetic\nfixture incremental is about 1.5x slower at 10000 commits. Per-commit\nchanges have less impact than expected: even when every directory is\ntouched, incremental remains competitive; bypassing the object cache for\ntree reads likely helps here.\n\nI cannot establish how common these regression cases are. In the cases I\nhave tested, however, the regression has remained modest; I have not been\nable to provoke a substantially larger slowdown. My feeling is that this is\nan acceptable tradeoff behind the opt-in config, since the target case\n(small pushes to large repos) sees the largest speedup, while the regression\nappears with long incoming histories.\n\nA safety net for this regression could be to dynamically disable the\nincremental mode if the number of incoming commits is too large, but this is\nleft out of the initial version to avoid overly speculative code.\n\nDeepening fetches currently fall back to the full check because the full\ncheck omits --not --all for deepening -- there is no existing-reference\nboundary at which the walk can stop. An incremental approach is possible\nhere too -- using the old shallow roots as the trusted boundary and walking\nthe deepened ancestry forward -- but that is a separate change and left for\nfuture work. Deepening is also less common than regular fetch and\nreceive-pack, where the speedup matters most.\n\n\nTest coverage\n=============\n\nMost correctness cases in t5412-connectivity-check.sh are run in both full\nand incremental modes to check semantic equivalence. Selected cases\nadditionally assert trace2 tree/blob counts for the incremental mode, to\nverify that unchanged portions of the object graph are actually skipped. It\ncovers:\n\n * Corruption detection: missing blobs, missing trees, type mismatches,\n malformed trees (unparseable, mid-tree corruption)\n * Tree optimization: trace2 assertions confirm unchanged subtrees are\n skipped, subtree moves, merge parent boundaries\n * Root commits (no parents -- verifies full tree closure)\n * Partial clones: missing promised blobs, missing promised trees,\n verification of local commits\n * Replacement objects (with and without GIT_NO_REPLACE_OBJECTS)\n * Shallow boundaries\n * Deepening fetches (falls back to full check)\n * Integration: real push, fetch, and clone\n\nMost tests call git rev-list directly with the appropriate flags;\nintegration tests exercise the full check_connected() path through push,\nfetch, and clone.\n\n\nAlternatives considered\n=======================\n\nMy first prototype ran the verifier in-process inside connected.c. This\nrequired a second rev-list subprocess just for boundary finding, _nofetch\nvariants of several object-reading functions to prevent lazy fetches in\npartial clones, explicit shallow-file plumbing, and careful avoidance of\ndie() in all code paths reachable from the verifier. The result worked but\nwas fragile and touched many files.\n\nMoving the verifier into the rev-list subprocess eliminated all of those\nproblems: in partial clones the existing --exclude-promisor-objects handling\nalready disables lazy fetching, die() is isolated by the process boundary,\nshallow and replacement semantics are established before the verifier runs,\nand error routing comes for free via stderr.\n\nSo while I liked the idea of being less reliant on checking within a\nsubprocess, making that work ended up being a lot more complex.\n\n\nNext steps\n==========\n\nThis series only addresses tree verification; the other significant cost is\nfinding the commit boundary, especially for repos with many refs. I already\nhave some prototypes for optimizing that too, and if this ends up landing,\nthat would be something I would start polishing up.\n\n\nChanges since v1\n================\n\n * Guard against get_commit_tree_oid() returning NULL in\n verify_commit_tree(), dying with a clear message instead of a NULL\n dereference. (Thanks Junio for catching this)\n * Set fetch_if_missing = 0 in the rev-list early option parse when\n --verify-trees-incremental is seen, and add a BUG() assertion in\n verify_commits_incremental() to catch any future caller that forgets.\n This makes the lazy-fetch protection explicit rather than relying solely\n on --exclude-promisor-objects having set it earlier. (Thanks again to\n Junio)\n * Add a test that verifies promised blobs are not lazy-fetched during the\n incremental check.\n * Reuse the existing 3-argument type-mismatch format string to avoid adding\n new strings for localization.\n\nThanks, Kristofer\n\nKristofer Karlsson (2):\n Documentation: describe connectivity checking\n connected: add incremental connectivity check via rev-list\n\n Documentation/config/transfer.adoc | 20 +\n Documentation/rev-list-options.adoc | 6 +\n .../technical/connectivity-check.adoc | 243 +++++++\n Makefile | 1 +\n builtin/rev-list.c | 19 +\n connected.c | 24 +\n meson.build | 1 +\n t/meson.build | 1 +\n ...enerate-repo-p5412-connectivity-check.perl | 44 ++\n t/perf/p5412-connectivity-check.sh | 92 +++\n t/t5412-connectivity-check.sh | 680 ++++++++++++++++++\n tree-verify.c | 316 ++++++++\n tree-verify.h | 15 +\n 13 files changed, 1462 insertions(+)\n create mode 100644 Documentation/technical/connectivity-check.adoc\n create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl\n create mode 100755 t/perf/p5412-connectivity-check.sh\n create mode 100755 t/t5412-connectivity-check.sh\n create mode 100644 tree-verify.c\n create mode 100644 tree-verify.h\n\n\nbase-commit: 47ce80527c56f462cb97db4ca8125342204d3783\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2211%2Fspkrka%2Ftree-diff-connectivity-v1-clean-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2211/spkrka/tree-diff-connectivity-v1-clean-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2211\n\nRange-diff vs v1:\n\n 1: e55c5452db = 1: 97c11449ae Documentation: describe connectivity checking\n 2: ebe6c90cc5 ! 2: 6ad528f4bb connected: add incremental connectivity check via rev-list\n @@ builtin/rev-list.c: int cmd_rev_list(int argc,\n \t\t\trevs.exclude_promisor_objects = 1;\n +\t\t} else if (!strcmp(arg, \"--verify-trees-incremental\")) {\n +\t\t\tverify_trees_incremental = 1;\n ++\t\t\trepo->fetch_if_missing = 0;\n \t\t} else if (skip_prefix(arg, \"--missing=\", &arg)) {\n \t\t\tparse_missing_action_value(repo, arg);\n \t\t} else if (!strcmp(arg, \"-z\")) {\n @@ t/t5412-connectivity-check.sh (new)\n +\t)\n +'\n +\n ++test_expect_success \"$mode: does not lazy-fetch promised blob\" '\n ++\ttest_when_finished \"rm -rf nofetch-src nofetch-server.git nofetch-client\" &&\n ++\tgit init nofetch-src &&\n ++\ttest_commit -C nofetch-src --no-tag base file.txt content &&\n ++\tgit clone --bare nofetch-src nofetch-server.git &&\n ++\tgit -C nofetch-server.git config uploadpack.allowfilter true &&\n ++\tgit -C nofetch-server.git config uploadpack.allowanysha1inwant true &&\n ++\tgit clone --no-checkout --filter=blob:none \\\n ++\t\t\"file://$(pwd)/nofetch-server.git\" nofetch-client &&\n ++\t(\n ++\t\tcd nofetch-client &&\n ++\t\tpromised_blob=$(git rev-parse HEAD:file.txt) &&\n ++\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n ++\t\t\tgit cat-file -e \"$promised_blob\" &&\n ++\t\tnew_tree=$(printf \"100644 blob %s\\tfile.txt\\n\" \\\n ++\t\t\t\"$promised_blob\" |\n ++\t\t\tgit mktree --missing) &&\n ++\t\tnew_commit=$(git commit-tree \"$new_tree\" \\\n ++\t\t\t-m \"root commit with promised blob\") &&\n ++\t\tcheck_connected \"$new_commit\" &&\n ++\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n ++\t\t\tgit cat-file -e \"$promised_blob\"\n ++\t)\n ++'\n ++\n +test_expect_success \"$mode: accepts missing promised tree\" '\n +\ttest_when_finished \"rm -rf prom-tree-src prom-tree-server.git prom-tree-client\" &&\n +\tgit init prom-tree-src &&\n @@ tree-verify.c (new)\n +\t\treturn;\n +\t}\n +\tif (type >= 0)\n -+\t\tdie(_(\"object %s is a %s, not a blob\"),\n -+\t\t oid_to_hex(oid), type_name(type));\n ++\t\tdie(_(\"object %s is a %s, not a %s\"),\n ++\t\t oid_to_hex(oid), type_name(type), \"blob\");\n +\tif (vs->exclude_promisor_objects &&\n +\t is_promisor_object(repo, oid))\n +\t\treturn;\n @@ tree-verify.c (new)\n +\n +\tif (buf && type != OBJ_TREE) {\n +\t\tfree(buf);\n -+\t\tdie(_(\"object %s is a %s, not a tree\"),\n -+\t\t oid_to_hex(oid), type_name(type));\n ++\t\tdie(_(\"object %s is a %s, not a %s\"),\n ++\t\t oid_to_hex(oid), type_name(type), \"tree\");\n +\t}\n +\treturn buf;\n +}\n @@ tree-verify.c (new)\n +\t\tconst struct object_id *tree_oid;\n +\t\tparse_commit_or_die(p->item);\n +\t\ttree_oid = get_commit_tree_oid(p->item);\n ++\t\tif (!tree_oid)\n ++\t\t\tdie(_(\"unable to load root tree for commit %s\"),\n ++\t\t\t oid_to_hex(&p->item->object.oid));\n +\t\ttree_map_add(vs->trees, tree_oid, TREE_TRUSTED);\n +\t\toid_array_append(&base_trees, tree_oid);\n +\t}\n +\n ++\tif (!get_commit_tree_oid(commit))\n ++\t\tdie(_(\"unable to load root tree for commit %s\"),\n ++\t\t oid_to_hex(&commit->object.oid));\n +\tverify_tree(repo, get_commit_tree_oid(commit),\n +\t\t &base_trees, vs, 0);\n +\toid_array_clear(&base_trees);\n @@ tree-verify.c (new)\n +\tstruct commit_list *iter;\n +\tunsigned nr_before;\n +\n ++\tif (repo->fetch_if_missing)\n ++\t\tBUG(\"verify_commits_incremental must not be called \"\n ++\t\t \"with fetch_if_missing set\");\n ++\n +\tvs.trees = kh_init_oid_tree();\n +\tvs.exclude_promisor_objects = exclude_promisor_objects;\n +\n\n-- \ngitgitgadget\n"},{"id":"553463","messageId":"97c11449aeae924436ba22a00a2545254e988a58.1790600552.git.gitgitgadget@gmail.com","threadId":"66326","inReplyTo":"pull.2211.v2.git.1790600552.gitgitgadget@gmail.com","subject":"[PATCH v2 1/2] Documentation: describe connectivity checking","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-09-28T13:02:31Z","receivedAt":"2026-09-28T13:02:51Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nAdd Documentation/technical/connectivity-check.adoc describing\nthe connectivity invariant and the full connectivity check.\n\nSigned-off-by: Kristofer Karlsson \n---\n .../technical/connectivity-check.adoc | 109 ++++++++++++++++++\n 1 file changed, 109 insertions(+)\n create mode 100644 Documentation/technical/connectivity-check.adoc\n\ndiff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc\nnew file mode 100644\nindex 0000000000..d20bff6af6\n--- /dev/null\n+++ b/Documentation/technical/connectivity-check.adoc\n@@ -0,0 +1,109 @@\n+Connectivity checking\n+=====================\n+\n+After receiving new objects via fetch, push (receive-pack), clone,\n+or bundle, Git verifies that the new reference tips do not leave\n+the repository in a state where reachable objects are missing.\n+This verification is called the connectivity check.\n+\n+Connectivity invariant\n+----------------------\n+\n+A repository is connected when every object reachable from its\n+references is available locally (with exceptions noted below).\n+\n+The connectivity check maintains this invariant when references\n+are updated. It trusts the existing connected state and verifies\n+that the new reference tips do not introduce references to\n+unavailable objects. Verification is permitted to stop when it\n+reaches objects already reachable from trusted existing\n+references, since their closure is already connected. These\n+trusted references include local references and references from\n+alternate object stores.\n+\n+Without this check, a truncated or corrupted transfer could leave\n+a repository in a state where later history walks encounter\n+missing objects.\n+\n+Exceptions\n+~~~~~~~~~~\n+\n+Gitlink entries (submodule references) are excluded from\n+connectivity checking. Their target objects belong to a separate\n+repository.\n+\n+In partial clones, objects promised by a promisor remote are\n+accepted as connected without requiring local existence. The\n+check excludes promisor objects from traversal so that it does\n+not trigger on-demand fetches for them.\n+\n+Full connectivity check\n+-----------------------\n+\n+`check_connected()` (see `connected.c`) normally performs the\n+connectivity check using a `rev-list` subprocess, feeding the\n+new reference tips via stdin. A normal invocation is roughly:\n+\n+ git rev-list --objects --stdin --not --all --quiet\n+ --alternate-refs [--exclude-promisor-objects]\n+\n+When promisor remotes are configured, `check_connected()` first\n+attempts a fast path based on promisor packfiles. If it falls\n+back to the `rev-list` check, `--exclude-promisor-objects` is\n+added so that the traversal does not trigger on-demand fetches.\n+\n+Consider the following graph after a fetch, where all reference\n+tips point directly to commits. For simplicity, only local\n+references appear on the already-connected side; alternate refs\n+play the same role. N3 is a merge commit:\n+\n+ /-------------L2\n+ /\n+ C1---B1---C2---B2-----L1\n+ \\ \\\n+ N1 N3---T2\n+ \\ /\n+ N2-----------T1\n+\n+ L1, L2: local refs\n+ T1, T2: incoming tips (new refs)\n+ N1, N2, N3: incoming commits (N3 is a merge)\n+ B1, B2: boundary commits (already connected)\n+ C1, C2: already connected (but not boundary)\n+\n+The incoming set is the commits reachable from the incoming\n+tips but not from the already-connected side. Boundary commits\n+are the already-connected commits at the edge of that set. Here\n+B1 is an ancestor of B2, which happens when incoming branches\n+fork at different depths in the existing history.\n+\n+The check proceeds in three phases:\n+\n+1. Walk from the incoming tips (T1, T2) against the trusted\n+ refs (L1, L2) to find the incoming set ({N1, N2, N3, T1, T2}).\n+\n+2. Walk the trees of the boundary commits (B1, B2) and mark\n+ those objects uninteresting. These trees are already trusted\n+ because their commits are on the already-connected side.\n+\n+3. Walk the trees of each incoming commit and verify that every\n+ referenced object is connected, stopping at objects already\n+ marked uninteresting in phase 2.\n+\n+Deepening fetches\n+~~~~~~~~~~~~~~~~~\n+\n+For deepening fetches (where the shallow boundary moves), the\n+full check omits `--not --all`. There is no existing-reference\n+boundary at which the walk can stop. Instead, traversal follows\n+the effective shallow boundary supplied for the deepened\n+repository. The new content may be below the old shallow\n+boundary even when the tips themselves have not changed.\n+\n+Non-commit tips\n+~~~~~~~~~~~~~~~\n+\n+When a new reference points to a non-commit object, such as a\n+tag, tree, or blob, that object is not part of the commit walk.\n+These non-commit tips are handled by the subsequent object\n+traversal.\n-- \ngitgitgadget\n\n"},{"id":"553464","messageId":"6ad528f4bb42a960910eb4fe917a3766fa55d598.1790600552.git.gitgitgadget@gmail.com","threadId":"66326","inReplyTo":"pull.2211.v2.git.1790600552.gitgitgadget@gmail.com","subject":"[PATCH v2 2/2] connected: add incremental connectivity check via rev-list","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-09-28T13:02:32Z","receivedAt":"2026-09-28T13:02:54Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nThe full connectivity check uses rev-list to find commits\nreachable from the incoming tips but not from the\nalready-connected side, then walks their object closure. Commit\ntraversal stops at the connectivity boundary, but trees and blobs\nreachable from that boundary still need to be walked so they can\nbe marked uninteresting, allocating a struct object for each one.\nOn repositories where the boundary commits have large trees, the\nconnectivity check for small incoming changes visits and tracks\nmore objects than needed.\n\nAdd an alternative connectivity check that verifies incoming\ncommits incrementally against their parents.\n\nThe verifier processes incoming commits with ancestors first and\ncompares each new tree against its trusted parent trees. Entries\nalready seen on the trusted side are skipped by OID, so unchanged\nsubtrees need not remain at the same path to be recognized.\nChanged subtrees are recursively compared against same-path parent\nsubtrees, and new subtrees without a comparison base are verified\nfrom scratch.\n\nSee Documentation/technical/connectivity-check.adoc for the trust\ninvariants and detailed algorithm.\n\nThe incremental check runs as an internal\n--verify-trees-incremental mode in rev-list. After the normal\nrevision walk identifies the incoming commits, the verifier\nconsumes them before the usual object traversal; any pending\nnon-commit tips are still handled by the existing traversal.\n\nPartial-clone semantics are preserved: objects promised by a\npromisor remote are accepted as connected, and on-demand fetching\nis prevented by excluding promisor objects from traversal. The\nnew mode is selected by transfer.connectivityCheck=incremental,\nwith full remaining the default. Deepening fetches fall back to\nthe full check because they do not have the normal\nexisting-reference boundary, and traversal instead follows the\neffective shallow boundary.\n\np5412 results (median of 3), scaling one dimension at a time.\nEach fixture is a repository with a flat tree of many\ndirectories containing 100 files each. The incoming set is a\nchain of commits on top of the existing history, with each\ncommit changing files in different directories round-robin.\nThe three axes vary the total repository tree size, the number\nof incoming commits, and the number of files changed per\nincoming commit.\n\nScaling tree size (10 incoming commits, 10 files/commit):\n\n files full incr. full/incr\n 5K 0.01s 0.01s 1.0x\n 50K 0.04s 0.01s 4.0x\n 200K 0.15s 0.01s 15.0x\n 800K 0.61s 0.03s 20.3x\n\nThe full mode must walk the trees of boundary commits, which\ngrows with overall tree size. Incremental still scans the\nroot trees, but avoids descending into unchanged subtrees,\nso it grows much more slowly with repository size.\n\nScaling incoming commit count (200K files, 10 files/commit):\n\n commits full incr. full/incr\n 1 0.14s 0.01s 14.0x\n 10 0.15s 0.01s 15.0x\n 100 0.19s 0.05s 3.8x\n 500 0.32s 0.27s 1.2x\n 3000 1.23s 1.52s 0.8x\n 5000 1.88s 2.43s 0.8x\n 10000 3.72s 5.36s 0.7x\n\nWith many commits the per-commit overhead of scanning both\nthe new and parent root trees accumulates and incremental\nbecomes slower. Breakeven is between 500 and 3000 commits\nand the ratio stabilizes near 0.7x for this fixture.\n\nScaling files per incoming commit (200K files, 10 commits):\n\n files/commit full incr. full/incr\n 1 0.14s 0.01s 14.0x\n 10 0.15s 0.01s 15.0x\n 100 0.16s 0.04s 4.0x\n 500 0.23s 0.14s 1.6x\n 1000 0.34s 0.28s 1.2x\n 2000 0.70s 0.63s 1.1x\n\nBreakeven is around 1000 files/commit. At 2000 files/commit\n(every directory touched), incremental remains slightly faster;\nbypassing the object cache for tree reads likely helps here.\n\nFor small repositories both modes are fast enough that the\ndifference is difficult to measure reliably.\n\nSelected peak RSS measurements from the same fixtures:\n\n case full incr. ratio\n 200K files, 10 commits 31 MB 12 MB 0.4x\n 800K files, 10 commits 110 MB 26 MB 0.2x\n 200K files, 5000 commits 155 MB 151 MB 1.0x\n\nIncremental uses substantially less memory when it can prune\nmost of the boundary tree walk. In the long-history case the\ntwo modes visit similar object sets and memory converges.\n\nThe regression cases in the CPU benchmarks are in wall-clock\ntime rather than memory, primarily from scanning some trees\nmore than once.\n\nSigned-off-by: Kristofer Karlsson \n---\n Documentation/config/transfer.adoc | 20 +\n Documentation/rev-list-options.adoc | 6 +\n .../technical/connectivity-check.adoc | 134 ++++\n Makefile | 1 +\n builtin/rev-list.c | 19 +\n connected.c | 24 +\n meson.build | 1 +\n t/meson.build | 1 +\n ...enerate-repo-p5412-connectivity-check.perl | 44 ++\n t/perf/p5412-connectivity-check.sh | 92 +++\n t/t5412-connectivity-check.sh | 680 ++++++++++++++++++\n tree-verify.c | 316 ++++++++\n tree-verify.h | 15 +\n 13 files changed, 1353 insertions(+)\n create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl\n create mode 100755 t/perf/p5412-connectivity-check.sh\n create mode 100755 t/t5412-connectivity-check.sh\n create mode 100644 tree-verify.c\n create mode 100644 tree-verify.h\n\ndiff --git a/Documentation/config/transfer.adoc b/Documentation/config/transfer.adoc\nindex f1ce50f4a6..b9939d3bde 100644\n--- a/Documentation/config/transfer.adoc\n+++ b/Documentation/config/transfer.adoc\n@@ -1,3 +1,23 @@\n+transfer.connectivityCheck::\n+\tChoose which algorithm to use for the connectivity check\n+\tperformed during object transfer operations such as\n+\tlinkgit:git-fetch[1] and linkgit:git-receive-pack[1].\n+\tThe connectivity check verifies that all objects reachable\n+\tfrom the incoming tips are available locally or, in a partial\n+\tclone, promised by a promisor remote.\n+\tThe variants are as follows:\n++\n+--\n+`full` (default);;\n+\tWalk the full object closure of the boundary commits.\n+`incremental`;;\n+\tVerify incoming commits by diffing their trees against parent\n+\ttrees, recursively descending only into entries that differ.\n+\tThe largest benefits occur when incoming commits change a\n+\tsmall fraction of a large tree closure.\n+\tFalls back to `full` for deepening fetches.\n+--\n+\n transfer.credentialsInUrl::\n \tA configured URL can contain plaintext credentials in the form\n \t`://:@/`. You may want\ndiff --git a/Documentation/rev-list-options.adoc b/Documentation/rev-list-options.adoc\nindex fd831f0ec6..7964b691c4 100644\n--- a/Documentation/rev-list-options.adoc\n+++ b/Documentation/rev-list-options.adoc\n@@ -1089,6 +1089,12 @@ we cannot get their Object ID though, an error will be raised.\n \tstronger than `--missing=allow-promisor` because it limits the\n \ttraversal, rather than just silencing errors about missing\n \tobjects.\n+\n+`--verify-trees-incremental`::\n+\t(For internal use only.) Verify tree connectivity\n+\tincrementally by comparing each commit's tree against its\n+\tparent trees. Used by `check_connected()` when\n+\t`transfer.connectivityCheck` is set to `incremental`.\n endif::git-rev-list[]\n \n `--no-walk[=(sorted|unsorted)]`::\ndiff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc\nindex d20bff6af6..0a8f370546 100644\n--- a/Documentation/technical/connectivity-check.adoc\n+++ b/Documentation/technical/connectivity-check.adoc\n@@ -107,3 +107,137 @@ When a new reference points to a non-commit object, such as a\n tag, tree, or blob, that object is not part of the commit walk.\n These non-commit tips are handled by the subsequent object\n traversal.\n+\n+Incremental connectivity check\n+------------------------------\n+\n+The incremental mode, selected by\n+`transfer.connectivityCheck=incremental`, avoids traversing the\n+full tree walk of the boundary commits. Instead, it verifies\n+each incoming commit's tree against the already-trusted trees of\n+its parents.\n+\n+Trust model\n+~~~~~~~~~~~\n+\n+A tree is trusted when its transitive object closure is known to\n+be connected. Trees reachable from commits on the\n+already-connected side of the boundary are therefore trusted.\n+\n+Incoming commits are processed with ancestors before descendants.\n+Once an incoming commit's tree has been verified, it is trusted\n+and can be used as a comparison base for later descendants.\n+\n+This gives an inductive correctness argument: every parent of the\n+commit currently being verified is either already connected or is\n+an earlier incoming commit whose tree has already been verified.\n+\n+Tree states\n+~~~~~~~~~~~\n+\n+The verifier tracks tree OIDs in three states:\n+\n+untrusted::\n+\tThe tree has not yet been established as connected. This\n+\tis the implicit state of an OID not present in the state\n+\tmap.\n+\n+trusted::\n+\tThe tree is known to have a connected transitive closure,\n+\tbut its direct entries have not yet been published into the\n+\tverifier's trusted object sets.\n+\n+expanded::\n+\tThe tree is trusted and its direct non-gitlink entries\n+\thave also been published into the trusted object sets.\n+\n+State transitions are monotonic: a tree may move from untrusted\n+to trusted to expanded, but never backwards. An untrusted tree\n+that is successfully verified goes directly to expanded.\n+\n+Blobs require only trusted/untrusted state: a blob becomes\n+trusted when it is found in a trusted tree or when its existence\n+and type have been verified directly.\n+\n+The trusted/expanded distinction is an optimization. An expanded\n+parent does not need to be reread merely to publish entries that\n+are already trusted, though it may still be read when same-path\n+subtree bases are needed for recursive comparison.\n+\n+Algorithm\n+~~~~~~~~~\n+\n+At a high level:\n+\n+ verify(commits):\n+ sort topologically (ancestors first)\n+ for each commit:\n+ mark parent root trees as trusted\n+ verify_tree(commit.tree, parent root trees)\n+\n+ verify_tree(tree, base_trees):\n+ if tree already trusted: return\n+ read tree, collect entries not already trusted\n+ for each available base tree:\n+ publish its entries as trusted\n+ record same-path subtrees as bases\n+ for each collected entry:\n+ if now trusted: skip\n+ if blob: verify blob connectivity and type\n+ if tree: verify_tree(entry, its recorded bases)\n+ mark tree as expanded\n+\n+The important ordering within `verify_tree` is that entries from\n+the new tree are collected before the base trees are scanned, but\n+are processed only afterwards. Trust learned from any base can\n+therefore eliminate work before recursive verification begins.\n+\n+Same-path parent subtrees are passed down as comparison bases\n+during recursive descent. If no comparison base is available,\n+the new subtree is verified from scratch.\n+\n+Worked example\n+~~~~~~~~~~~~~~\n+\n+Consider a commit that changes one file under `lib/` and moves an\n+unchanged subtree from `src/` to `dev/`:\n+\n+ Parent tree New tree\n+ +-- src/ (aaa) +-- dev/ (aaa)\n+ +-- lib/ (bbb) +-- lib/ (ccc)\n+ +-- foo.c (ddd) +-- foo.c (ddd)\n+ +-- bar.c (eee) +-- bar.c (fff)\n+\n+Scanning the parent makes `aaa` trusted even though it moved from\n+`src/` to `dev/`, so that subtree is skipped. The changed `ccc`\n+subtree is compared against its same-path parent `bbb`; scanning\n+`bbb` makes `ddd` and `eee` trusted, leaving only the new `fff`\n+blob to be checked.\n+\n+This illustrates two properties:\n+\n+* Trust is OID-based rather than path-based. An unchanged subtree\n+ is recognized after a move.\n+\n+* Same-path parent subtrees provide recursive comparison bases.\n+ These bases improve pruning efficiency but are not required for\n+ correctness; a new subtree can always be verified from scratch.\n+\n+Multiple parents\n+~~~~~~~~~~~~~~~~\n+\n+For a merge commit, root trees from all parents are comparison\n+bases. When several parents contain a same-path subtree, each\n+matching subtree is collected as a recursive comparison base.\n+\n+Entries published from any trusted parent become globally trusted,\n+so a matching tree or blob entry present in any parent can be\n+skipped while verifying the merge tree.\n+\n+Missing comparison bases\n+~~~~~~~~~~~~~~~~~~~~~~~~\n+\n+A promised base tree may not be locally available for comparison.\n+In that case the verifier skips that base and verifies the new\n+subtree without it. The missing comparison can reduce pruning but\n+does not affect correctness.\ndiff --git a/Makefile b/Makefile\nindex d4b775953d..aa5b4e2b84 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1357,6 +1357,7 @@ LIB_OBJS += trailer.o\n LIB_OBJS += transport-helper.o\n LIB_OBJS += transport.o\n LIB_OBJS += tree-diff.o\n+LIB_OBJS += tree-verify.o\n LIB_OBJS += tree-walk.o\n LIB_OBJS += tree.o\n LIB_OBJS += unpack-trees.o\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 6b596231ab..beaec67d16 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -28,6 +28,7 @@\n #include \"commit-reach.h\"\n #include \"quote.h\"\n #include \"strbuf.h\"\n+#include \"tree-verify.h\"\n \n struct rev_list_info {\n \tstruct rev_info *revs;\n@@ -706,6 +707,7 @@ int cmd_rev_list(int argc,\n \tint bisect_find_all = 0;\n \tint use_bitmap_index = 0;\n \tint filter_provided_objects = 0;\n+\tint verify_trees_incremental = 0;\n \tconst char *show_progress = NULL;\n \tint ret = 0;\n \n@@ -748,6 +750,9 @@ int cmd_rev_list(int argc,\n \t\tif (!strcmp(arg, \"--exclude-promisor-objects\")) {\n \t\t\trepo->fetch_if_missing = 0;\n \t\t\trevs.exclude_promisor_objects = 1;\n+\t\t} else if (!strcmp(arg, \"--verify-trees-incremental\")) {\n+\t\t\tverify_trees_incremental = 1;\n+\t\t\trepo->fetch_if_missing = 0;\n \t\t} else if (skip_prefix(arg, \"--missing=\", &arg)) {\n \t\t\tparse_missing_action_value(repo, arg);\n \t\t} else if (!strcmp(arg, \"-z\")) {\n@@ -822,6 +827,8 @@ int cmd_rev_list(int argc,\n \n \t\tif (!strcmp(arg, \"--exclude-promisor-objects\"))\n \t\t\tcontinue; /* already handled above */\n+\t\tif (!strcmp(arg, \"--verify-trees-incremental\"))\n+\t\t\tcontinue; /* already handled above */\n \t\tif (skip_prefix(arg, \"--missing=\", &arg))\n \t\t\tcontinue; /* already handled above */\n \n@@ -935,6 +942,18 @@ int cmd_rev_list(int argc,\n \n \tprepare_maximal_independent(&revs);\n \n+\tif (verify_trees_incremental) {\n+\t\tstruct commit *commit;\n+\t\tstruct commit_list *new_commits = NULL;\n+\n+\t\twhile ((commit = get_revision(&revs)) != NULL)\n+\t\t\tcommit_list_insert(commit, &new_commits);\n+\n+\t\tverify_commits_incremental(repo, &new_commits,\n+\t\t\t\t\t revs.exclude_promisor_objects);\n+\t\tcommit_list_free(new_commits);\n+\t}\n+\n \tif (revs.tree_objects)\n \t\tmark_edges_uninteresting(&revs, show_edge, 0);\n \ndiff --git a/connected.c b/connected.c\nindex 929b9bd28d..e3dcd8e2b0 100644\n--- a/connected.c\n+++ b/connected.c\n@@ -1,6 +1,7 @@\n #define USE_THE_REPOSITORY_VARIABLE\n \n #include \"git-compat-util.h\"\n+#include \"config.h\"\n #include \"gettext.h\"\n #include \"hex.h\"\n #include \"odb.h\"\n@@ -67,6 +68,26 @@ static int check_connected_promisor(oid_iterate_fn fn,\n \treturn 1;\n }\n \n+static int incremental_check_applicable(struct check_connected_options *opt)\n+{\n+\tconst char *algorithm = NULL;\n+\n+\tif (repo_config_get_string_tmp(the_repository,\n+\t\t\t\t \"transfer.connectivitycheck\",\n+\t\t\t\t &algorithm))\n+\t\treturn 0;\n+\tif (!strcasecmp(algorithm, \"full\"))\n+\t\treturn 0;\n+\tif (strcasecmp(algorithm, \"incremental\"))\n+\t\tdie(_(\"unknown transfer.connectivityCheck algorithm '%s'\"),\n+\t\t algorithm);\n+\n+\tif (opt->is_deepening_fetch)\n+\t\treturn 0;\n+\n+\treturn 1;\n+}\n+\n /*\n * If we feed all the commits we want to verify to this command\n *\n@@ -133,6 +154,9 @@ int check_connected(oid_iterate_fn fn, void *cb_data,\n \tif (opt->progress)\n \t\tstrvec_pushf(&rev_list.args, \"--progress=%s\",\n \t\t\t _(\"Checking connectivity\"));\n+\tif (incremental_check_applicable(opt))\n+\t\tstrvec_push(&rev_list.args,\n+\t\t\t \"--verify-trees-incremental\");\n \n \trev_list.git_cmd = 1;\n \tif (opt->env)\ndiff --git a/meson.build b/meson.build\nindex 0a95d90d21..d94dedc26c 100644\n--- a/meson.build\n+++ b/meson.build\n@@ -562,6 +562,7 @@ libgit_sources = [\n 'transport-helper.c',\n 'transport.c',\n 'tree-diff.c',\n+ 'tree-verify.c',\n 'tree-walk.c',\n 'tree.c',\n 'unpack-trees.c',\ndiff --git a/t/meson.build b/t/meson.build\nindex 7f53cca7d1..19a8246c44 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -652,6 +652,7 @@ integration_tests = [\n 't5409-colorize-remote-messages.sh',\n 't5410-receive-pack.sh',\n 't5411-proc-receive-hook.sh',\n+ 't5412-connectivity-check.sh',\n 't5500-fetch-pack.sh',\n 't5501-fetch-push-alternates.sh',\n 't5502-quickfetch.sh',\ndiff --git a/t/perf/generate-repo-p5412-connectivity-check.perl b/t/perf/generate-repo-p5412-connectivity-check.perl\nnew file mode 100644\nindex 0000000000..9546996280\n--- /dev/null\n+++ b/t/perf/generate-repo-p5412-connectivity-check.perl\n@@ -0,0 +1,44 @@\n+#!/usr/bin/perl\n+#\n+# Generate a fast-import stream for p5412 connectivity check benchmarks.\n+#\n+# Usage: generate-repo-p5412-connectivity-check.perl\n+# [] []\n+#\n+# Creates one initial commit with dirs*files_per_dir files, then\n+# additional commits each modifying \n+# files in directories chosen round-robin from 1...\n+\n+use strict;\n+use warnings;\n+\n+my ($nd, $nf, $nc, $hot, $fpc) = @ARGV;\n+$hot = $nd if !$hot || $hot > $nd;\n+$fpc = 1 if !$fpc;\n+\n+sub data {\n+\tprintf \"data %d\\n%s\\n\", length($_[0]), $_[0];\n+}\n+\n+# Initial tree: one commit with nd*nf files.\n+printf \"commit refs/heads/main\\n\";\n+printf \"committer perf now\\n\";\n+data(\"initial\");\n+for my $d (1..$nd) {\n+\tfor my $f (1..$nf) {\n+\t\tprintf \"M 100644 inline d-%04d/f-%03d\\n\", $d, $f;\n+\t\tdata(sprintf \"%03d%03d\", $d, $f);\n+\t}\n+}\n+\n+# Subsequent commits (auto-chained by fast-import).\n+for my $i (1..$nc) {\n+\tprintf \"commit refs/heads/main\\n\";\n+\tprintf \"committer perf now\\n\";\n+\tdata(sprintf \"change-%03d\", $i);\n+\tfor my $j (0..$fpc-1) {\n+\t\tmy $d = (($i + $j) % $hot) + 1;\n+\t\tprintf \"M 100644 inline d-%04d/f-001\\n\", $d;\n+\t\tdata(sprintf \"c%d-%d\", $i, $j);\n+\t}\n+}\ndiff --git a/t/perf/p5412-connectivity-check.sh b/t/perf/p5412-connectivity-check.sh\nnew file mode 100755\nindex 0000000000..827643a847\n--- /dev/null\n+++ b/t/perf/p5412-connectivity-check.sh\n@@ -0,0 +1,92 @@\n+#!/bin/sh\n+\n+test_description='performance of connectivity check modes\n+\n+Compare the default and incremental rev-list connectivity modes\n+directly, avoiding pack transfer noise.\n+\n+Each repository has a flat tree of many directories with 100 files\n+in each. Three axes are scaled independently: tree size, commit\n+count, and files changed per commit.'\n+\n+. ./perf-lib.sh\n+\n+test_perf_fresh_repo\n+\n+generate=\"$TEST_DIRECTORY/perf/generate-repo-p5412-connectivity-check.perl\"\n+\n+# $1=dirs $2=files_per_dir $3=commits $4=hot_dirs (optional, default=all)\n+# $5=files_per_commit (optional, default=1)\n+test_perf_conn () {\n+\tlocal nd=\"$1\" nf=\"$2\" nc=\"$3\" hot=\"${4:-$1}\" fpc=\"${5:-1}\"\n+\tlocal total=$(($nd * $nf))\n+\tlocal name=\"repo-${nd}d-${nf}f-${nc}c-${hot}h-${fpc}fpc\"\n+\tlocal label=\"${total} files, ${nc} commits\"\n+\tif test \"$hot\" -lt \"$nd\"\n+\tthen\n+\t\tlabel=\"$label (${hot} hot dirs)\"\n+\tfi\n+\tif test \"$fpc\" -gt 1\n+\tthen\n+\t\tlabel=\"$label (${fpc} files/commit)\"\n+\tfi\n+\n+\ttest_expect_success \"setup $label\" '\n+\t\tif test -d '\"$name\"'\n+\t\tthen\n+\t\t\ttrue\n+\t\telse\n+\t\t\tgit init '\"$name\"' &&\n+\t\t\t\"$PERL_PATH\" '\"$generate\"' '\"$nd\"' '\"$nf\"' '\"$nc\"' '\"$hot\"' '\"$fpc\"' |\n+\t\t\tgit -C '\"$name\"' fast-import --date-format=now --quiet &&\n+\t\t\t(\n+\t\t\t\tcd '\"$name\"' &&\n+\t\t\t\tgit rev-parse main~'\"$nc\"' >../'\"${name}\"'_old &&\n+\t\t\t\tgit rev-parse main >../'\"${name}\"'_new &&\n+\t\t\t\tgit update-ref refs/heads/main \\\n+\t\t\t\t\t$(cat ../'\"${name}\"'_old) &&\n+\t\t\t\tgit repack -ad &&\n+\t\t\t\tgit config gc.auto 0\n+\t\t\t)\n+\t\tfi\n+\t'\n+\n+\ttest_perf \"$label (full)\" '\n+\t\tcat '\"${name}\"'_new |\n+\t\tgit -C '\"$name\"' rev-list \\\n+\t\t\t--objects --stdin --not --all --quiet \\\n+\t\t\t--exclude-promisor-objects\n+\t'\n+\n+\ttest_perf \"$label (incremental)\" '\n+\t\tcat '\"${name}\"'_new |\n+\t\tgit -C '\"$name\"' rev-list --verify-trees-incremental \\\n+\t\t\t--objects --stdin --not --all --quiet \\\n+\t\t\t--exclude-promisor-objects\n+\t'\n+}\n+\n+# Scaling tree size (10 commits, 10 files/commit).\n+test_perf_conn 50 100 10 50 10\n+test_perf_conn 500 100 10 500 10\n+test_perf_conn 2000 100 10 2000 10\n+test_perf_conn 8000 100 10 8000 10\n+\n+# Scaling commit count (200K files, 10 files/commit).\n+test_perf_conn 2000 100 1 2000 10\n+test_perf_conn 2000 100 10 2000 10\n+test_perf_conn 2000 100 100 2000 10\n+test_perf_conn 2000 100 500 2000 10\n+test_perf_conn 2000 100 3000 2000 10\n+test_perf_conn 2000 100 5000 2000 10\n+test_perf_conn 2000 100 10000 2000 10\n+\n+# Scaling files per commit (200K files, 10 commits).\n+test_perf_conn 2000 100 10 2000 1\n+test_perf_conn 2000 100 10 2000 10\n+test_perf_conn 2000 100 10 2000 100\n+test_perf_conn 2000 100 10 2000 500\n+test_perf_conn 2000 100 10 2000 1000\n+test_perf_conn 2000 100 10 2000 2000\n+\n+test_done\ndiff --git a/t/t5412-connectivity-check.sh b/t/t5412-connectivity-check.sh\nnew file mode 100755\nindex 0000000000..1c84cfe452\n--- /dev/null\n+++ b/t/t5412-connectivity-check.sh\n@@ -0,0 +1,680 @@\n+#!/bin/sh\n+\n+test_description='connectivity check (transfer.connectivityCheck)'\n+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main\n+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME\n+\n+. ./test-lib.sh\n+\n+test_oid_cache <<-\\EOF\n+missing sha1:0000000000000000000000000000000000000001\n+missing sha256:0000000000000000000000000000000000000000000000000000000000000001\n+EOF\n+\n+set_connectivity_check () {\n+\tgit -C \"$1\" config transfer.connectivityCheck \"$2\"\n+}\n+\n+# Run a connectivity check via rev-list directly. Uses $mode\n+# (set by the enclosing for-loop) to choose full or incremental.\n+check_connected () {\n+\tflags= &&\n+\tif test \"$mode\" = incremental\n+\tthen\n+\t\tflags=--verify-trees-incremental\n+\tfi &&\n+\tprintf '%s\\n' \"$@\" |\n+\tgit rev-list $flags \\\n+\t\t--objects --stdin --not --all --quiet \\\n+\t\t--exclude-promisor-objects\n+}\n+\n+# Run git with a temporary index, leaving the real index untouched.\n+tmpgit () {\n+\tGIT_INDEX_FILE=.git/tmp-idx git \"$@\"\n+}\n+\n+# Create a commit with one file changed, without modifying HEAD,\n+# index, or worktree. Prints the new commit OID on stdout.\n+# Usage: commit_with_change \n+commit_with_change () {\n+\tnew_blob=$(echo \"$3\" | git hash-object -w --stdin) &&\n+\ttmpgit read-tree \"$1\" &&\n+\ttmpgit update-index --replace \\\n+\t\t--cacheinfo \"100644,$new_blob,$2\" &&\n+\tnew_tree=$(tmpgit write-tree) &&\n+\trm -f .git/tmp-idx &&\n+\tgit commit-tree \"$new_tree\" -p \"$1\" -m \"modify $2\"\n+}\n+\n+# Check OIDs and optionally verify trace2 counts.\n+# Usage: check_connected_trace ...\n+# An empty string for or skips that assertion.\n+check_connected_trace () {\n+\ttrace_file=$1 trees=$2 blobs=$3 &&\n+\tshift 3 &&\n+\ttest_env GIT_TRACE2_EVENT=\"$(pwd)/$trace_file\" \\\n+\t\tcheck_connected \"$@\" &&\n+\tif test \"$mode\" != incremental\n+\tthen\n+\t\treturn\n+\tfi &&\n+\tif test -n \"$trees\"\n+\tthen\n+\t\ttest_trace2_data_singular connectivity trees_loaded \"$trees\" \\\n+\t\t\t<\"$trace_file\"\n+\tfi &&\n+\tif test -n \"$blobs\"\n+\tthen\n+\t\ttest_trace2_data_singular connectivity blobs_checked \"$blobs\" \\\n+\t\t\t<\"$trace_file\"\n+\tfi\n+}\n+\n+# Shared setup: a repo with several root-level files and nested dirs.\n+# The unchanged/ subtree (10 dirs x 10 files = 100 blobs, 11 trees)\n+# acts as a canary: any test asserting small tree/blob counts would\n+# fail dramatically if incremental accidentally walked into it.\n+\n+test_expect_success 'setup main repo' '\n+\tgit init main-repo &&\n+\t(\n+\t\tcd main-repo &&\n+\t\tfor i in $(test_seq 1 5)\n+\t\tdo\n+\t\t\techo \"file $i\" >\"file-$i.txt\" || return 1\n+\t\tdone &&\n+\t\tgit add file-*.txt &&\n+\t\tgit commit -m \"initial\" &&\n+\n+\t\tmkdir -p a/b/c &&\n+\t\techo deep >a/b/c/deep.txt &&\n+\t\techo other >a/other.txt &&\n+\t\tgit add a/b/c/deep.txt a/other.txt &&\n+\t\tgit commit -m \"add nested dirs\" &&\n+\n+\t\tfor i in $(test_seq 1 10)\n+\t\tdo\n+\t\t\td=\"unchanged/dir-$i\" &&\n+\t\t\tmkdir -p \"$d\" &&\n+\t\t\tfor j in $(test_seq 1 10)\n+\t\t\tdo\n+\t\t\t\techo \"$i $j\" >\"$d/file-$j.txt\" || return 1\n+\t\t\tdone\n+\t\tdone &&\n+\t\tgit add unchanged/ &&\n+\t\tgit commit -m \"add unchanged canary subtree\"\n+\t)\n+'\n+\n+test_expect_success 'setup replacement object repo' '\n+\tgit init replace-test &&\n+\t(\n+\t\tcd replace-test &&\n+\n+\t\ttest_commit --no-tag original file.txt &&\n+\t\toriginal=$(git rev-parse HEAD) &&\n+\t\torig_blob=$(git rev-parse HEAD:file.txt) &&\n+\n+\t\t# Orphan replacement commit with a different tree\n+\t\treplacement_tree=$(echo replaced | git hash-object -w --stdin |\n+\t\t\txargs -I{} git mktree <<-EOF\n+\t\t\t100644 blob {}\tfile.txt\n+\t\t\tEOF\n+\t\t) &&\n+\t\treplacement=$(git commit-tree -m \"replacement\" \\\n+\t\t\t\"$replacement_tree\") &&\n+\n+\t\tgit replace \"$original\" \"$replacement\" &&\n+\n+\t\t# Remove the original blob so only the replacement\n+\t\t# tree is complete.\n+\t\trm .git/objects/$(test_oid_to_path \"$orig_blob\") &&\n+\n+\t\t# Drop branch and HEAD so --not --all does not\n+\t\t# exclude the original commit.\n+\t\tgit update-ref -d refs/heads/main &&\n+\t\tgit update-ref -d HEAD &&\n+\n+\t\techo \"$original\" >.git/test-oid\n+\t)\n+'\n+\n+missing_oid=$(test_oid missing)\n+original_oid=$(cat replace-test/.git/test-oid)\n+\n+for mode in full incremental\n+do\n+\n+# Corruption detection: craft broken object graphs and verify detection.\n+# All tests use main-repo without modifying its refs or worktree.\n+\n+test_expect_success \"$mode: rejects commit with missing blob\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tbad_tree=$(printf \"100644 blob ${missing_oid}\\tfile.txt\\n\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tbad_commit=$(git commit-tree \"$bad_tree\" -p HEAD -m \"bad\") &&\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"missing blob object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: rejects commit with missing subtree\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tbad_tree=$(printf \"40000 tree ${missing_oid}\\tdir\\n\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tbad_commit=$(git commit-tree \"$bad_tree\" -p HEAD -m \"bad\") &&\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"bad tree object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies direct tree tip\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tbad_tree=$(printf \"100644 blob ${missing_oid}\\tfile.txt\\n\" |\n+\t\t\tgit mktree --missing) &&\n+\t\ttest_expect_code 128 check_connected \"$bad_tree\" 2>err &&\n+\t\ttest_grep \"missing blob object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies direct blob tip\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tblob_oid=$(echo \"hello\" | git hash-object -w --stdin) &&\n+\t\tcheck_connected \"$blob_oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: rejects missing direct blob tip\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$missing_oid\" 2>err\n+\t)\n+'\n+\n+test_expect_success PERL_TEST_HELPERS \\\n+\t\"$mode: rejects blob OID reused as tree entry\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\tblob_oid=$(git rev-parse HEAD:file-1.txt) &&\n+\t\tbin_oid=$(echo \"$blob_oid\" | hex2oct) &&\n+\n+\t\tbad_tree=$(printf \"40000 subdir\\0$bin_oid\" |\n+\t\t\tgit hash-object -t tree -w --stdin) &&\n+\t\tbad_commit=$(git commit-tree -p HEAD -m \"child\" \"$bad_tree\") &&\n+\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"not a tree\" err\n+\t)\n+'\n+\n+test_expect_success PERL_TEST_HELPERS \\\n+\t\"$mode: rejects tree OID reused as blob entry\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\ttree_oid=$(git rev-parse HEAD:a) &&\n+\t\tbin_oid=$(echo \"$tree_oid\" | hex2oct) &&\n+\n+\t\tbad_tree=$(printf \"100644 fakefile\\0$bin_oid\" |\n+\t\t\tgit hash-object -t tree -w --stdin) &&\n+\t\tbad_commit=$(git commit-tree -p HEAD -m \"child\" \"$bad_tree\") &&\n+\n+\t\ttest_expect_code 128 check_connected \"$bad_commit\" 2>err &&\n+\t\ttest_grep \"not a blob\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: checks multiple tips\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tc1=$(commit_with_change HEAD file-1.txt \"tip-a\") &&\n+\t\tc2=$(commit_with_change HEAD file-2.txt \"tip-b\") &&\n+\t\tgit tag -a -m \"tagged\" multi-tag \"$c1\" &&\n+\t\ttag_oid=$(git rev-parse multi-tag) &&\n+\t\tgit tag -d multi-tag &&\n+\t\tcheck_connected \"$c2\" \"$tag_oid\"\n+\t)\n+'\n+\n+# Tree-diff optimization: verify trace2 counts.\n+\n+test_expect_success \"$mode: handles root commit (no parents)\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tblob_oid=$(echo \"root-content\" | git hash-object -w --stdin) &&\n+\t\ttree_oid=$(printf \"100644 blob %s\\tfile.txt\\n\" \\\n+\t\t\t\"$blob_oid\" | git mktree) &&\n+\t\troot_oid=$(git commit-tree \"$tree_oid\" -m \"root\") &&\n+\n+\t\t# No parent trees, so the full tree is verified.\n+\t\t# 1 tree loaded (root), 1 blob checked.\n+\t\tcheck_connected_trace trace-root.txt 1 1 \"$root_oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles single file change\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\toid=$(commit_with_change HEAD file-1.txt \"changed\") &&\n+\n+\t\t# 2 trees loaded (new root + parent root), 1 blob checked.\n+\t\tcheck_connected_trace trace-flat.txt 2 1 \"$oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles nested change\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\toid=$(commit_with_change HEAD a/b/c/deep.txt \"deep-changed\") &&\n+\t\t# 4 new trees + 4 parent trees = 8 loaded, 1 blob checked.\n+\t\tcheck_connected_trace trace-nested.txt 8 1 \"$oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles change-then-revert\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tc1=$(commit_with_change HEAD file-1.txt \"revert-tmp\") &&\n+\t\tc2=$(commit_with_change \"$c1\" file-1.txt \"file 1\") &&\n+\t\tc3=$(commit_with_change \"$c2\" file-1.txt \"revert-final\") &&\n+\n+\t\t# c1: new root + parent root = 2 loads. c2: root matches\n+\t\t# HEAD (already trusted), skipped. c3: new root + parent\n+\t\t# already expanded = 1 load. Total: 3 trees, 2 blobs.\n+\t\tcheck_connected_trace trace-revert.txt 3 2 \"$c3\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles subtree moved to another path\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tmoved_tree=$(git ls-tree HEAD |\n+\t\t\tsed \"s/\ta$/\tmoved/\" |\n+\t\t\tgit mktree) &&\n+\t\tmoved=$(git commit-tree \"$moved_tree\" -p HEAD -m move) &&\n+\t\t# New root + parent root scanned, but the moved subtree\n+\t\t# (same OID) is trusted and not descended into.\n+\t\tcheck_connected_trace trace-move.txt 2 0 \"$moved\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles multi-parent merge\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\tleft=$(commit_with_change HEAD file-1.txt left) &&\n+\t\tright=$(commit_with_change HEAD file-2.txt right) &&\n+\t\tgit update-ref refs/heads/left \"$left\" &&\n+\t\tgit update-ref refs/heads/right \"$right\" &&\n+\t\tleft_blob=$(git rev-parse \"$left:file-1.txt\") &&\n+\t\tright_blob=$(git rev-parse \"$right:file-2.txt\") &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --replace \\\n+\t\t\t--cacheinfo \"100644,$left_blob,file-1.txt\" &&\n+\t\ttmpgit update-index --replace \\\n+\t\t\t--cacheinfo \"100644,$right_blob,file-2.txt\" &&\n+\t\tmerge_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tmerge=$(git commit-tree \"$merge_tree\" \\\n+\t\t\t-p \"$left\" -p \"$right\" -m merge) &&\n+\t\t# Both parent root trees are scanned as bases, so\n+\t\t# blobs from each parent are trusted without ODB checks.\n+\t\tcheck_connected_trace trace-merge.txt 3 0 \"$merge\" &&\n+\t\tgit update-ref -d refs/heads/left &&\n+\t\tgit update-ref -d refs/heads/right\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles merge with incoming and boundary parents\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\t# parent1 is incoming (not a ref), HEAD is boundary.\n+\t\tparent1=$(commit_with_change HEAD file-1.txt merge-inc) &&\n+\t\tmerge=$(git commit-tree \\\n+\t\t\t\"$(git rev-parse \"$parent1^{tree}\")\" \\\n+\t\t\t-p \"$parent1\" -p HEAD -m merge-mixed) &&\n+\t\t# parent1 verified first (topo order): 2 trees, 1 blob.\n+\t\t# merge tree = parent1 tree (already trusted): 0 extra.\n+\t\tcheck_connected_trace trace-merge-inc.txt 2 1 \"$merge\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles gitlink entries (submodules)\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"160000,$missing_oid,my-submodule\" &&\n+\t\tgitlink_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tgitlink_commit=$(git commit-tree \"$gitlink_tree\" -p HEAD \\\n+\t\t\t-m \"add gitlink\") &&\n+\n+\t\t# Gitlink entries are skipped -- the missing submodule\n+\t\t# commit OID does not cause a failure.\n+\t\tcheck_connected_trace trace-gitlink.txt 2 0 \"$gitlink_commit\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles file-to-directory transition\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\t# Parent: \"foo\" is a blob at root.\n+\t\tblob_a=$(echo \"file-content\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_a,foo\" &&\n+\t\tparent_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tparent=$(git commit-tree \"$parent_tree\" -p HEAD \\\n+\t\t\t-m \"add foo as file\") &&\n+\n+\t\t# Child: \"foo\" becomes a directory (foo/bar.txt).\n+\t\tblob_b=$(echo \"dir-content\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree \"$parent\" &&\n+\t\ttmpgit update-index --remove foo &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_b,foo/bar.txt\" &&\n+\t\tchild_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tchild=$(git commit-tree \"$child_tree\" -p \"$parent\" \\\n+\t\t\t-m \"foo: file to directory\") &&\n+\t\tcheck_connected_trace trace-f2d.txt \"\" \"\" \"$child\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: handles directory-to-file transition\" '\n+\t(\n+\t\tcd main-repo &&\n+\n+\t\t# Parent: \"bar/baz.txt\" exists (bar is a directory).\n+\t\tblob_a=$(echo \"nested\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree HEAD &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_a,bar/baz.txt\" &&\n+\t\tparent_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tparent=$(git commit-tree \"$parent_tree\" -p HEAD \\\n+\t\t\t-m \"add bar as directory\") &&\n+\n+\t\t# Child: \"bar\" becomes a plain file.\n+\t\tblob_b=$(echo \"flat\" | git hash-object -w --stdin) &&\n+\t\ttmpgit read-tree \"$parent\" &&\n+\t\ttmpgit update-index --remove bar/baz.txt &&\n+\t\ttmpgit update-index --add \\\n+\t\t\t--cacheinfo \"100644,$blob_b,bar\" &&\n+\t\tchild_tree=$(tmpgit write-tree) &&\n+\t\trm -f .git/tmp-idx &&\n+\t\tchild=$(git commit-tree \"$child_tree\" -p \"$parent\" \\\n+\t\t\t-m \"bar: directory to file\") &&\n+\t\tcheck_connected_trace trace-d2f.txt \"\" \"\" \"$child\"\n+\t)\n+'\n+\n+# Replacement objects.\n+\n+test_expect_success \"$mode: accepts with replacement objects\" '\n+\t(\n+\t\tcd replace-test &&\n+\t\tcheck_connected \"$original_oid\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: rejects without replacement objects\" '\n+\t(\n+\t\tcd replace-test &&\n+\t\tGIT_NO_REPLACE_OBJECTS=1 &&\n+\t\texport GIT_NO_REPLACE_OBJECTS &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$original_oid\" 2>err &&\n+\t\ttest_grep \"missing blob object\" err\n+\t)\n+'\n+\n+test_expect_success \"$mode: accepts missing promised blob\" '\n+\ttest_when_finished \"rm -rf prom-src prom-server.git prom-client\" &&\n+\tgit init prom-src &&\n+\ttest_commit -C prom-src --no-tag base file.txt original &&\n+\ttest_commit -C prom-src --no-tag \"add file2\" file2.txt extra &&\n+\tgit clone --bare prom-src prom-server.git &&\n+\tgit -C prom-server.git config uploadpack.allowfilter true &&\n+\tgit -C prom-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --no-checkout --filter=blob:none \\\n+\t\t\"file://$(pwd)/prom-server.git\" prom-client &&\n+\t(\n+\t\tcd prom-client &&\n+\t\tpromised_blob=$(git rev-parse HEAD:file2.txt) &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_blob\" &&\n+\t\tnew_tree=$(printf \"100644 blob %s\\tnewname.txt\\n\" \\\n+\t\t\t\"$promised_blob\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tnew_commit=$(git commit-tree \"$new_tree\" \\\n+\t\t\t-p HEAD -m \"reuse promised blob\") &&\n+\t\tcheck_connected \"$new_commit\" &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_blob\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: does not lazy-fetch promised blob\" '\n+\ttest_when_finished \"rm -rf nofetch-src nofetch-server.git nofetch-client\" &&\n+\tgit init nofetch-src &&\n+\ttest_commit -C nofetch-src --no-tag base file.txt content &&\n+\tgit clone --bare nofetch-src nofetch-server.git &&\n+\tgit -C nofetch-server.git config uploadpack.allowfilter true &&\n+\tgit -C nofetch-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --no-checkout --filter=blob:none \\\n+\t\t\"file://$(pwd)/nofetch-server.git\" nofetch-client &&\n+\t(\n+\t\tcd nofetch-client &&\n+\t\tpromised_blob=$(git rev-parse HEAD:file.txt) &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_blob\" &&\n+\t\tnew_tree=$(printf \"100644 blob %s\\tfile.txt\\n\" \\\n+\t\t\t\"$promised_blob\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tnew_commit=$(git commit-tree \"$new_tree\" \\\n+\t\t\t-m \"root commit with promised blob\") &&\n+\t\tcheck_connected \"$new_commit\" &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_blob\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: accepts missing promised tree\" '\n+\ttest_when_finished \"rm -rf prom-tree-src prom-tree-server.git prom-tree-client\" &&\n+\tgit init prom-tree-src &&\n+\tmkdir -p prom-tree-src/a/b &&\n+\ttest_commit -C prom-tree-src --no-tag \"nested dirs\" a/b/file.txt deep &&\n+\tgit clone --bare prom-tree-src prom-tree-server.git &&\n+\tgit -C prom-tree-server.git config uploadpack.allowfilter true &&\n+\tgit -C prom-tree-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --no-checkout --filter=tree:1 \\\n+\t\t\"file://$(pwd)/prom-tree-server.git\" prom-tree-client &&\n+\t(\n+\t\tcd prom-tree-client &&\n+\t\tpromised_tree=$(git ls-tree HEAD -- a |\n+\t\t\tawk \"{print \\$3}\") &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_tree\" &&\n+\t\tnew_tree=$(printf \"40000 tree %s\\trenamed\\n\" \\\n+\t\t\t\"$promised_tree\" |\n+\t\t\tgit mktree --missing) &&\n+\t\tnew_commit=$(git commit-tree \"$new_tree\" \\\n+\t\t\t-p HEAD -m \"reuse promised tree\") &&\n+\t\tcheck_connected \"$new_commit\" &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$promised_tree\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies new subtree when parent subtree is promised\" '\n+\ttest_when_finished \"rm -rf prom-base-src prom-base-server.git prom-base-client\" &&\n+\tgit init prom-base-src &&\n+\tmkdir -p prom-base-src/a &&\n+\ttest_commit -C prom-base-src --no-tag \"base\" a/file.txt deep &&\n+\tgit clone --bare prom-base-src prom-base-server.git &&\n+\tgit -C prom-base-server.git config uploadpack.allowfilter true &&\n+\tgit -C prom-base-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --no-checkout --filter=tree:1 \\\n+\t\t\"file://$(pwd)/prom-base-server.git\" prom-base-client &&\n+\t(\n+\t\tcd prom-base-client &&\n+\t\tparent_subtree=$(git ls-tree HEAD -- a |\n+\t\t\tawk \"{print \\$3}\") &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$parent_subtree\" &&\n+\t\tnew_blob=$(echo \"local-content\" | git hash-object -w --stdin) &&\n+\t\tnew_subtree=$(printf \"100644 blob %s\\tfile.txt\\n\" \\\n+\t\t\t\"$new_blob\" | git mktree) &&\n+\t\tnew_root=$(printf \"40000 tree %s\\ta\\n\" \\\n+\t\t\t\"$new_subtree\" | git mktree) &&\n+\t\tnew_commit=$(git commit-tree \"$new_root\" \\\n+\t\t\t-p HEAD -m \"replace promised subtree\") &&\n+\t\tcheck_connected \"$new_commit\" &&\n+\t\ttest_must_fail env GIT_NO_LAZY_FETCH=1 \\\n+\t\t\tgit cat-file -e \"$parent_subtree\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: verifies local commit in partial clone\" '\n+\ttest_when_finished \"rm -rf pc-src pc-server.git pc-client\" &&\n+\tgit init pc-src &&\n+\ttest_commit -C pc-src --no-tag base file.txt &&\n+\tgit clone --bare pc-src pc-server.git &&\n+\tgit -C pc-server.git config uploadpack.allowfilter true &&\n+\tgit -C pc-server.git config uploadpack.allowanysha1inwant true &&\n+\tgit clone --filter=blob:none \\\n+\t\t\"file://$(pwd)/pc-server.git\" pc-client &&\n+\t(\n+\t\tcd pc-client &&\n+\t\tlocal_commit=$(commit_with_change HEAD file.txt local-content) &&\n+\t\tcheck_connected \"$local_commit\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: respects shallow boundary\" '\n+\ttest_when_finished \"rm -rf shallow-src shallow\" &&\n+\tgit init shallow-src &&\n+\ttest_commit -C shallow-src --no-tag base file content-1 &&\n+\tmkdir shallow-src/sub &&\n+\ttest_commit -C shallow-src --no-tag change sub/other content-2 &&\n+\tgit clone --depth=1 \"file://$(pwd)/shallow-src\" shallow &&\n+\t(\n+\t\tcd shallow &&\n+\t\ttip=$(git rev-parse HEAD) &&\n+\t\tgit for-each-ref --format=\"delete %(refname)\" |\n+\t\t\tgit update-ref --no-deref --stdin &&\n+\t\tcheck_connected \"$tip\"\n+\t)\n+'\n+\n+test_expect_success \"$mode: deepening fetch succeeds\" '\n+\ttest_when_finished \"rm -rf deepen-src deepen-server.git deepen-client\" &&\n+\tgit init deepen-src &&\n+\ttest_commit -C deepen-src --no-tag c1 file.txt &&\n+\ttest_commit -C deepen-src --no-tag c2 file.txt &&\n+\ttest_commit -C deepen-src --no-tag c3 file.txt &&\n+\tgit clone --bare deepen-src deepen-server.git &&\n+\tgit clone --depth=1 \"file://$(pwd)/deepen-server.git\" deepen-client &&\n+\tset_connectivity_check deepen-client $mode &&\n+\ttest -f deepen-client/.git/shallow &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/deepen-trace.txt\" \\\n+\t\tgit -C deepen-client fetch --deepen=2 origin main &&\n+\t# Incremental falls back to full for deepening fetches,\n+\t# so the trees_loaded event should not appear.\n+\ttest_grep ! trees_loaded deepen-trace.txt\n+'\n+\n+test_expect_success \"$mode: malformed tree detected\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\techo abc >malformed-tree &&\n+\t\tmalformed_tree=$(git hash-object --literally -t tree -w \\\n+\t\t\tmalformed-tree) &&\n+\t\tmalformed_commit=$(git commit-tree \"$malformed_tree\" \\\n+\t\t\t-p HEAD -m malformed) &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$malformed_commit\" 2>err\n+\t)\n+'\n+\n+test_expect_success PERL_TEST_HELPERS \\\n+\t\"$mode: mid-tree corruption detected\" '\n+\t(\n+\t\tcd main-repo &&\n+\t\t# Build a tree with one valid entry followed by garbage.\n+\t\tblob_oid=$(echo \"valid\" | git hash-object -w --stdin) &&\n+\t\tbin_oid=$(echo \"$blob_oid\" | hex2oct) &&\n+\t\tprintf \"100644 good\\0${bin_oid}GARBAGE\" >corrupt-mid-tree &&\n+\t\tcorrupt_tree=$(git hash-object --literally -t tree -w \\\n+\t\t\tcorrupt-mid-tree) &&\n+\t\tcorrupt_commit=$(git commit-tree \"$corrupt_tree\" \\\n+\t\t\t-p HEAD -m \"mid-tree corruption\") &&\n+\t\ttest_expect_code 128 check_connected \\\n+\t\t\t\"$corrupt_commit\" 2>err &&\n+\t\ttest_grep \"too-short tree object\" err\n+\t)\n+'\n+\n+done\n+\n+# Algorithm selection.\n+\n+test_expect_success 'invalid transfer.connectivityCheck is rejected' '\n+\ttest_when_finished \"rm -rf invalid-cfg-src invalid-cfg-dst\" &&\n+\tgit init invalid-cfg-src &&\n+\ttest_commit -C invalid-cfg-src --no-tag base file.txt &&\n+\tgit clone invalid-cfg-src invalid-cfg-dst &&\n+\ttest_commit -C invalid-cfg-src --no-tag update file.txt updated &&\n+\tgit -C invalid-cfg-dst config transfer.connectivityCheck bogus &&\n+\ttest_must_fail git -C invalid-cfg-dst fetch origin main 2>err &&\n+\ttest_grep \"unknown transfer.connectivityCheck\" err\n+'\n+\n+test_expect_success 'push uses incremental when configured' '\n+\ttest_when_finished \"rm -rf int-src int-dst.git\" &&\n+\tgit init int-src &&\n+\ttest_commit -C int-src --no-tag base file.txt &&\n+\tgit clone --bare int-src int-dst.git &&\n+\ttest_commit -C int-src --no-tag update file.txt updated &&\n+\tset_connectivity_check int-dst.git incremental &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/push-trace.txt\" \\\n+\t\tgit -C int-src push ../int-dst.git main &&\n+\ttest_trace2_data_singular connectivity trees_loaded 2 \\\n+\t\t kh_val(m, pos))\n+\t\tkh_val(m, pos) = state;\n+}\n+\n+struct work_item {\n+\tstruct name_entry entry;\n+\tstruct oid_array parent_trees;\n+};\n+\n+struct verify_state {\n+\tkh_oid_tree_t *trees;\n+\tstruct oidset trusted_blobs;\n+\tint trees_loaded;\n+\tint blobs_checked;\n+\tint exclude_promisor_objects;\n+};\n+\n+/*\n+ * Merge-walk the work list against one base tree entry, recording\n+ * same-path parent subtrees as recursive comparison bases.\n+ * Returns the updated work-list cursor.\n+ */\n+static size_t collect_subtree_bases(struct work_item *work, size_t nr_work,\n+\t\t\t\t size_t wi, const struct name_entry *entry)\n+{\n+\twhile (wi < nr_work) {\n+\t\tint cmp = base_name_compare(\n+\t\t\twork[wi].entry.path, work[wi].entry.pathlen,\n+\t\t\twork[wi].entry.mode,\n+\t\t\tentry->path, entry->pathlen,\n+\t\t\tentry->mode);\n+\t\tif (cmp > 0)\n+\t\t\tbreak;\n+\t\tif (cmp < 0) {\n+\t\t\twi++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (S_ISDIR(work[wi].entry.mode) &&\n+\t\t S_ISDIR(entry->mode))\n+\t\t\toid_array_append(&work[wi].parent_trees,\n+\t\t\t\t\t &entry->oid);\n+\t\treturn wi + 1;\n+\t}\n+\treturn wi;\n+}\n+\n+static void verify_blob(struct repository *repo,\n+\t\t\tconst struct object_id *oid,\n+\t\t\tstruct verify_state *vs)\n+{\n+\tint type;\n+\n+\tif (oidset_contains(&vs->trusted_blobs, oid))\n+\t\treturn;\n+\n+\tvs->blobs_checked++;\n+\ttype = odb_read_object_info(repo->objects, oid, NULL);\n+\tif (type == OBJ_BLOB) {\n+\t\toidset_insert(&vs->trusted_blobs, oid);\n+\t\treturn;\n+\t}\n+\tif (type >= 0)\n+\t\tdie(_(\"object %s is a %s, not a %s\"),\n+\t\t oid_to_hex(oid), type_name(type), \"blob\");\n+\tif (vs->exclude_promisor_objects &&\n+\t is_promisor_object(repo, oid))\n+\t\treturn;\n+\tdie(_(\"missing blob object '%s'\"), oid_to_hex(oid));\n+}\n+\n+static void *read_tree_object(struct object_database *odb,\n+\t\t\t const struct object_id *oid,\n+\t\t\t size_t *sizep)\n+{\n+\tenum object_type type;\n+\tvoid *buf = odb_read_object(odb, oid, &type, sizep);\n+\n+\tif (buf && type != OBJ_TREE) {\n+\t\tfree(buf);\n+\t\tdie(_(\"object %s is a %s, not a %s\"),\n+\t\t oid_to_hex(oid), type_name(type), \"tree\");\n+\t}\n+\treturn buf;\n+}\n+\n+static void verify_tree(struct repository *repo,\n+\t\t\tconst struct object_id *new_tree_oid,\n+\t\t\tconst struct oid_array *base_trees,\n+\t\t\tstruct verify_state *vs, int depth)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct work_item *work = NULL;\n+\tsize_t nr_work = 0, alloc_work = 0;\n+\tint need_subtree_bases = 0;\n+\tsize_t i, tree_size;\n+\tvoid *tree_buf;\n+\n+\tif (depth > repo->settings.max_allowed_tree_depth)\n+\t\tdie(_(\"exceeded maximum allowed tree depth\"));\n+\n+\tif (tree_map_get(vs->trees, new_tree_oid) >= TREE_TRUSTED)\n+\t\treturn;\n+\n+\ttree_buf = read_tree_object(repo->objects, new_tree_oid, &tree_size);\n+\tif (!tree_buf) {\n+\t\tif (vs->exclude_promisor_objects &&\n+\t\t is_promisor_object(repo, new_tree_oid))\n+\t\t\treturn;\n+\t\tdie(_(\"bad tree object %s\"),\n+\t\t oid_to_hex(new_tree_oid));\n+\t}\n+\n+\tvs->trees_loaded++;\n+\tinit_tree_desc(&desc, new_tree_oid, tree_buf, tree_size);\n+\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tif (S_ISGITLINK(entry.mode))\n+\t\t\tcontinue;\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tif (tree_map_get(vs->trees, &entry.oid) >= TREE_TRUSTED)\n+\t\t\t\tcontinue;\n+\t\t\tneed_subtree_bases = 1;\n+\t\t} else {\n+\t\t\tif (oidset_contains(&vs->trusted_blobs, &entry.oid))\n+\t\t\t\tcontinue;\n+\t\t}\n+\t\tALLOC_GROW(work, nr_work + 1, alloc_work);\n+\t\tmemset(&work[nr_work], 0, sizeof(work[nr_work]));\n+\t\twork[nr_work].entry = entry;\n+\t\tnr_work++;\n+\t}\n+\n+\tif (!nr_work) {\n+\t\tfree(tree_buf);\n+\t\tgoto done;\n+\t}\n+\n+\tfor (i = 0; base_trees && i < base_trees->nr; i++) {\n+\t\tconst struct object_id *base_oid = &base_trees->oid[i];\n+\t\tint expanded = tree_map_get(vs->trees, base_oid) >= TREE_EXPANDED;\n+\t\tstruct tree_desc base_desc;\n+\t\tstruct name_entry scan_entry;\n+\t\tsize_t wi = 0, base_size;\n+\t\tvoid *base_buf;\n+\n+\t\tif (expanded && !need_subtree_bases)\n+\t\t\tcontinue;\n+\n+\t\tbase_buf = read_tree_object(repo->objects, base_oid,\n+\t\t\t\t\t &base_size);\n+\t\tif (!base_buf) {\n+\t\t\tif (vs->exclude_promisor_objects &&\n+\t\t\t is_promisor_object(repo, base_oid))\n+\t\t\t\tcontinue;\n+\t\t\tdie(_(\"bad tree object %s\"),\n+\t\t\t oid_to_hex(base_oid));\n+\t\t}\n+\n+\t\tvs->trees_loaded++;\n+\t\tinit_tree_desc(&base_desc, base_oid, base_buf, base_size);\n+\n+\t\twhile (tree_entry(&base_desc, &scan_entry)) {\n+\t\t\tif (S_ISGITLINK(scan_entry.mode))\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (need_subtree_bases)\n+\t\t\t\twi = collect_subtree_bases(work, nr_work,\n+\t\t\t\t\t\t\t wi, &scan_entry);\n+\n+\t\t\tif (!expanded) {\n+\t\t\t\tif (S_ISDIR(scan_entry.mode))\n+\t\t\t\t\ttree_map_add(vs->trees,\n+\t\t\t\t\t\t &scan_entry.oid,\n+\t\t\t\t\t\t TREE_TRUSTED);\n+\t\t\t\telse\n+\t\t\t\t\toidset_insert(&vs->trusted_blobs,\n+\t\t\t\t\t\t &scan_entry.oid);\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!expanded)\n+\t\t\ttree_map_add(vs->trees, base_oid, TREE_EXPANDED);\n+\n+\t\tfree(base_buf);\n+\t}\n+\n+\tfor (i = 0; i < nr_work; i++) {\n+\t\tif (S_ISDIR(work[i].entry.mode))\n+\t\t\tverify_tree(repo, &work[i].entry.oid,\n+\t\t\t\t &work[i].parent_trees, vs,\n+\t\t\t\t depth + 1);\n+\t\telse\n+\t\t\tverify_blob(repo, &work[i].entry.oid, vs);\n+\t}\n+\n+\tfree(tree_buf);\n+\n+done:\n+\ttree_map_add(vs->trees, new_tree_oid, TREE_EXPANDED);\n+\tfor (i = 0; i < nr_work; i++)\n+\t\toid_array_clear(&work[i].parent_trees);\n+\tfree(work);\n+}\n+\n+static void verify_commit_tree(struct repository *repo,\n+\t\t\t struct commit *commit,\n+\t\t\t struct verify_state *vs)\n+{\n+\tstruct oid_array base_trees = OID_ARRAY_INIT;\n+\tstruct commit_list *p;\n+\n+\t/*\n+\t * Parent trees are trusted: boundary parents are already\n+\t * connected, and earlier incoming parents were verified\n+\t * first due to the topological processing order.\n+\t */\n+\tfor (p = commit->parents; p; p = p->next) {\n+\t\tconst struct object_id *tree_oid;\n+\t\tparse_commit_or_die(p->item);\n+\t\ttree_oid = get_commit_tree_oid(p->item);\n+\t\tif (!tree_oid)\n+\t\t\tdie(_(\"unable to load root tree for commit %s\"),\n+\t\t\t oid_to_hex(&p->item->object.oid));\n+\t\ttree_map_add(vs->trees, tree_oid, TREE_TRUSTED);\n+\t\toid_array_append(&base_trees, tree_oid);\n+\t}\n+\n+\tif (!get_commit_tree_oid(commit))\n+\t\tdie(_(\"unable to load root tree for commit %s\"),\n+\t\t oid_to_hex(&commit->object.oid));\n+\tverify_tree(repo, get_commit_tree_oid(commit),\n+\t\t &base_trees, vs, 0);\n+\toid_array_clear(&base_trees);\n+}\n+\n+void verify_commits_incremental(struct repository *repo,\n+\t\t\t\tstruct commit_list **commits,\n+\t\t\t\tint exclude_promisor_objects)\n+{\n+\tstruct verify_state vs = { 0 };\n+\tstruct commit_list *iter;\n+\tunsigned nr_before;\n+\n+\tif (repo->fetch_if_missing)\n+\t\tBUG(\"verify_commits_incremental must not be called \"\n+\t\t \"with fetch_if_missing set\");\n+\n+\tvs.trees = kh_init_oid_tree();\n+\tvs.exclude_promisor_objects = exclude_promisor_objects;\n+\n+\t/*\n+\t * Ancestors must be verified before descendants so that parent\n+\t * trees can be trusted without re-verification. Sort explicitly\n+\t * rather than relying on the caller's ordering.\n+\t *\n+\t * sort_in_topological_order() silently drops cycle members,\n+\t * so explicitly check if the size has changed.\n+\t */\n+\tnr_before = commit_list_count(*commits);\n+\tsort_in_topological_order(commits, REV_SORT_IN_GRAPH_ORDER);\n+\tif (commit_list_count(*commits) < nr_before)\n+\t\tdie(_(\"cycle detected in incoming commit graph\"));\n+\n+\t*commits = commit_list_reverse(*commits);\n+\n+\tfor (iter = *commits; iter; iter = iter->next)\n+\t\tverify_commit_tree(repo, iter->item, &vs);\n+\n+\tkh_destroy_oid_tree(vs.trees);\n+\toidset_clear(&vs.trusted_blobs);\n+\ttrace2_data_intmax(\"connectivity\", repo,\n+\t\t\t \"trees_loaded\", vs.trees_loaded);\n+\ttrace2_data_intmax(\"connectivity\", repo,\n+\t\t\t \"blobs_checked\", vs.blobs_checked);\n+}\ndiff --git a/tree-verify.h b/tree-verify.h\nnew file mode 100644\nindex 0000000000..6aadadff70\n--- /dev/null\n+++ b/tree-verify.h\n@@ -0,0 +1,15 @@\n+#ifndef TREE_VERIFY_H\n+#define TREE_VERIFY_H\n+\n+struct commit_list;\n+struct repository;\n+\n+/*\n+ * Verify trees of commits incrementally against their parents.\n+ * Dies on verification failure.\n+ */\n+void verify_commits_incremental(struct repository *repo,\n+\t\t\t\tstruct commit_list **commits,\n+\t\t\t\tint exclude_promisor_objects);\n+\n+#endif /* TREE_VERIFY_H */\n-- \ngitgitgadget\n"},{"id":"554151","messageId":"asNY7SfEohsOSf0J@pks.im","threadId":"66326","inReplyTo":"97c11449aeae924436ba22a00a2545254e988a58.1790600552.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/2] Documentation: describe connectivity checking","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-10-05T07:59:41Z","receivedAt":"2026-10-05T07:59:52Z","isPatch":true,"body":"On Mon, Sep 28, 2026 at 01:02:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> diff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc\n> new file mode 100644\n> index 0000000000..d20bff6af6\n> --- /dev/null\n> +++ b/Documentation/technical/connectivity-check.adoc\n> @@ -0,0 +1,109 @@\n> +Connectivity checking\n> +=====================\n> +\n> +After receiving new objects via fetch, push (receive-pack), clone,\n> +or bundle, Git verifies that the new reference tips do not leave\n> +the repository in a state where reachable objects are missing.\n> +This verification is called the connectivity check.\n> +\n> +Connectivity invariant\n> +----------------------\n> +\n> +A repository is connected when every object reachable from its\n> +references is available locally (with exceptions noted below).\n\nRight. I think it would also be important to spell out the reverse of\nthis, which is that nothing can be assumed about objects that aren't\nreachable by any reference. So even if an object already exists in the\nobject database, it is not safe to assume that it is fully connected\nunless it is referenced.\n\n> +The connectivity check maintains this invariant when references\n> +are updated. It trusts the existing connected state and verifies\n\nNit: it's basically already implicit, but I'd clarify that \"existing\nconnected state\" is again just the connected state of objects reachable\nfrom reference tips. So maybe \"It trusts that all objects reachable from\nreferences are already fully connected and verifies...\"\n\n> +that the new reference tips do not introduce references to\n> +unavailable objects. Verification is permitted to stop when it\n> +reaches objects already reachable from trusted existing\n> +references, since their closure is already connected. These\n> +trusted references include local references and references from\n> +alternate object stores.\n> +\n> +Without this check, a truncated or corrupted transfer could leave\n> +a repository in a state where later history walks encounter\n> +missing objects.\n> +\n> +Exceptions\n> +~~~~~~~~~~\n> +\n> +Gitlink entries (submodule references) are excluded from\n> +connectivity checking. Their target objects belong to a separate\n> +repository.\n> +\n> +In partial clones, objects promised by a promisor remote are\n> +accepted as connected without requiring local existence. The\n> +check excludes promisor objects from traversal so that it does\n> +not trigger on-demand fetches for them.\n> +\n> +Full connectivity check\n> +-----------------------\n> +\n> +`check_connected()` (see `connected.c`) normally performs the\n\nI'm always a bit hesitant to directly refer to code in our docs. We\nshould either make this documentation part of \"connected.c\" directly, or\nwe should not refer to code. Otherwise, chances that this documentation\ngrows stale is very high.\n\n> +connectivity check using a `rev-list` subprocess, feeding the\n> +new reference tips via stdin. A normal invocation is roughly:\n> +\n> + git rev-list --objects --stdin --not --all --quiet\n> + --alternate-refs [--exclude-promisor-objects]\n> +\n> +When promisor remotes are configured, `check_connected()` first\n> +attempts a fast path based on promisor packfiles. If it falls\n> +back to the `rev-list` check, `--exclude-promisor-objects` is\n> +added so that the traversal does not trigger on-demand fetches.\n> +\n> +Consider the following graph after a fetch, where all reference\n> +tips point directly to commits. For simplicity, only local\n> +references appear on the already-connected side; alternate refs\n> +play the same role. N3 is a merge commit:\n> +\n> + /-------------L2\n> + /\n> + C1---B1---C2---B2-----L1\n> + \\ \\\n> + N1 N3---T2\n> + \\ /\n> + N2-----------T1\n> +\n> + L1, L2: local refs\n> + T1, T2: incoming tips (new refs)\n> + N1, N2, N3: incoming commits (N3 is a merge)\n> + B1, B2: boundary commits (already connected)\n> + C1, C2: already connected (but not boundary)\n> +\n> +The incoming set is the commits reachable from the incoming\n> +tips but not from the already-connected side. Boundary commits\n> +are the already-connected commits at the edge of that set. Here\n> +B1 is an ancestor of B2, which happens when incoming branches\n> +fork at different depths in the existing history.\n> +\n> +The check proceeds in three phases:\n> +\n> +1. Walk from the incoming tips (T1, T2) against the trusted\n> + refs (L1, L2) to find the incoming set ({N1, N2, N3, T1, T2}).\n> +\n> +2. Walk the trees of the boundary commits (B1, B2) and mark\n> + those objects uninteresting. These trees are already trusted\n> + because their commits are on the already-connected side.\n> +\n> +3. Walk the trees of each incoming commit and verify that every\n> + referenced object is connected, stopping at objects already\n> + marked uninteresting in phase 2.\n\nI feel like these phases here basically just explain how revision walks\nwork without adding any more details that are specifically relevant to\nthe connectivity check.\n\n> +Deepening fetches\n> +~~~~~~~~~~~~~~~~~\n> +\n> +For deepening fetches (where the shallow boundary moves), the\n> +full check omits `--not --all`. There is no existing-reference\n> +boundary at which the walk can stop. Instead, traversal follows\n> +the effective shallow boundary supplied for the deepened\n> +repository. The new content may be below the old shallow\n> +boundary even when the tips themselves have not changed.\n> +\n> +Non-commit tips\n> +~~~~~~~~~~~~~~~\n> +\n> +When a new reference points to a non-commit object, such as a\n> +tag, tree, or blob, that object is not part of the commit walk.\n> +These non-commit tips are handled by the subsequent object\n> +traversal.\n\nHuh, what subsequent object traversal? This part puzzles me a bit.\n\nPatrick\n"},{"id":"554152","messageId":"asNZD7AOC6QL9q1d@pks.im","threadId":"66326","inReplyTo":"6ad528f4bb42a960910eb4fe917a3766fa55d598.1790600552.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/2] connected: add incremental connectivity check via rev-list","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-10-05T08:00:15Z","receivedAt":"2026-10-05T08:00:20Z","isPatch":true,"body":"On Mon, Sep 28, 2026 at 01:02:32PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> From: Kristofer Karlsson \n> \n> The full connectivity check uses rev-list to find commits\n> reachable from the incoming tips but not from the\n> already-connected side, then walks their object closure. Commit\n> traversal stops at the connectivity boundary, but trees and blobs\n> reachable from that boundary still need to be walked so they can\n> be marked uninteresting, allocating a struct object for each one.\n> On repositories where the boundary commits have large trees, the\n> connectivity check for small incoming changes visits and tracks\n> more objects than needed.\n\nOkay. In the old world we basically mark evertyhing as uninteresting,\nincluding trees and blobs, ...\n\n> Add an alternative connectivity check that verifies incoming\n> commits incrementally against their parents.\n> \n> The verifier processes incoming commits with ancestors first and\n> compares each new tree against its trusted parent trees. Entries\n> already seen on the trusted side are skipped by OID, so unchanged\n> subtrees need not remain at the same path to be recognized.\n> Changed subtrees are recursively compared against same-path parent\n> subtrees, and new subtrees without a comparison base are verified\n> from scratch.\n\n... whereas in the new world you propose to skip marking trees/blobs as\nuninteresting. Instead, the idea is to compare the trees/blobs of the\nold tips directly with the trees/blobs of the new tips and only verify\nthose parts that have changed between the two?\n\nThis can of course cause us to verify significantly more objects in some\nscenarios. But it does have the consequence that we scale with the\nnumber of changes, not with the number of preexisting objects in the\nrepository. And that's something I'd really appreciate, because marking\nreachable objects as uninteresting is extremely expensive.\n\nOne thing I wonder though... does this help with the scenario where we\nhave tons of references or do we still end up passing \"--not --all\"? I\nhave seen many times that parsing the refs by itself is dominating the\ntime of the connectivity check quite significantly. So ideally, I'd like\nto have a solution that also catches this case. Your benchmarks do not\ncover that scenario though.\n\n> Incremental uses substantially less memory when it can prune\n> most of the boundary tree walk. In the long-history case the\n> two modes visit similar object sets and memory converges.\n> \n> The regression cases in the CPU benchmarks are in wall-clock\n> time rather than memory, primarily from scanning some trees\n> more than once.\n> \n> Signed-off-by: Kristofer Karlsson \n> ---\n> Documentation/config/transfer.adoc | 20 +\n> Documentation/rev-list-options.adoc | 6 +\n> .../technical/connectivity-check.adoc | 134 ++++\n> Makefile | 1 +\n> builtin/rev-list.c | 19 +\n> connected.c | 24 +\n> meson.build | 1 +\n> t/meson.build | 1 +\n> ...enerate-repo-p5412-connectivity-check.perl | 44 ++\n> t/perf/p5412-connectivity-check.sh | 92 +++\n> t/t5412-connectivity-check.sh | 680 ++++++++++++++++++\n> tree-verify.c | 316 ++++++++\n> tree-verify.h | 15 +\n> 13 files changed, 1353 insertions(+)\n> create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl\n> create mode 100755 t/perf/p5412-connectivity-check.sh\n> create mode 100755 t/t5412-connectivity-check.sh\n> create mode 100644 tree-verify.c\n> create mode 100644 tree-verify.h\n\nMay I suggest splitting up this patch in the following way?\n\n - One commit that introduces the new option, but for now only accepts\n \"full\" as the algorithm.\n\n - One commit that introduces the benchmark.\n\n - One commit that introduces the new flag for git-rev-list(1).\n\n - One commit that then introduces the new strategy.\n\nThat may make it a bit easier to focus on the actual change.\n\n> diff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc\n> index d20bff6af6..0a8f370546 100644\n> --- a/Documentation/technical/connectivity-check.adoc\n> +++ b/Documentation/technical/connectivity-check.adoc\n> @@ -107,3 +107,137 @@ When a new reference points to a non-commit object, such as a\n> tag, tree, or blob, that object is not part of the commit walk.\n> These non-commit tips are handled by the subsequent object\n> traversal.\n> +\n> +Incremental connectivity check\n> +------------------------------\n> +\n> +The incremental mode, selected by\n> +`transfer.connectivityCheck=incremental`, avoids traversing the\n> +full tree walk of the boundary commits. Instead, it verifies\n> +each incoming commit's tree against the already-trusted trees of\n> +its parents.\n\nCan we define \"parents\" here? Specifically, I wonder how you define\n\"parent\" in the case where you perform a force push or when creating a\nnew reference. Is it the parent of the first new commit? Is it the old\nstate of the ref, if it even exists?\n\n> +Trust model\n> +~~~~~~~~~~~\n> +\n> +A tree is trusted when its transitive object closure is known to\n> +be connected. Trees reachable from commits on the\n> +already-connected side of the boundary are therefore trusted.\n\nWhere the \"already-connected side of the boundary\" is anything reachable\nvia a reference.\n\n> +Incoming commits are processed with ancestors before descendants.\n> +Once an incoming commit's tree has been verified, it is trusted\n> +and can be used as a comparison base for later descendants.\n> +\n> +This gives an inductive correctness argument: every parent of the\n> +commit currently being verified is either already connected or is\n> +an earlier incoming commit whose tree has already been verified.\n\nRight. The big question to me still is how you identify\nalready-connected trees without having to read all references.\n\n> +Worked example\n\nWorked?\n\n[snip]\n> diff --git a/tree-verify.c b/tree-verify.c\n> new file mode 100644\n> index 0000000000..5c11c2251a\n> --- /dev/null\n> +++ b/tree-verify.c\n> @@ -0,0 +1,316 @@\n[snip]\n> +static void verify_commit_tree(struct repository *repo,\n> +\t\t\t struct commit *commit,\n> +\t\t\t struct verify_state *vs)\n> +{\n> +\tstruct oid_array base_trees = OID_ARRAY_INIT;\n> +\tstruct commit_list *p;\n> +\n> +\t/*\n> +\t * Parent trees are trusted: boundary parents are already\n> +\t * connected, and earlier incoming parents were verified\n> +\t * first due to the topological processing order.\n> +\t */\n\nI feel like I still miss where exactly you establish the trust boundary\nbetween preexisting fully-connected commits and new commits.\n\n> +\tfor (p = commit->parents; p; p = p->next) {\n> +\t\tconst struct object_id *tree_oid;\n> +\t\tparse_commit_or_die(p->item);\n> +\t\ttree_oid = get_commit_tree_oid(p->item);\n> +\t\tif (!tree_oid)\n> +\t\t\tdie(_(\"unable to load root tree for commit %s\"),\n> +\t\t\t oid_to_hex(&p->item->object.oid));\n> +\t\ttree_map_add(vs->trees, tree_oid, TREE_TRUSTED);\n> +\t\toid_array_append(&base_trees, tree_oid);\n> +\t}\n> +\n> +\tif (!get_commit_tree_oid(commit))\n> +\t\tdie(_(\"unable to load root tree for commit %s\"),\n> +\t\t oid_to_hex(&commit->object.oid));\n> +\tverify_tree(repo, get_commit_tree_oid(commit),\n> +\t\t &base_trees, vs, 0);\n> +\toid_array_clear(&base_trees);\n> +}\n> +\n> +void verify_commits_incremental(struct repository *repo,\n> +\t\t\t\tstruct commit_list **commits,\n> +\t\t\t\tint exclude_promisor_objects)\n> +{\n> +\tstruct verify_state vs = { 0 };\n> +\tstruct commit_list *iter;\n> +\tunsigned nr_before;\n> +\n> +\tif (repo->fetch_if_missing)\n> +\t\tBUG(\"verify_commits_incremental must not be called \"\n> +\t\t \"with fetch_if_missing set\");\n> +\n> +\tvs.trees = kh_init_oid_tree();\n> +\tvs.exclude_promisor_objects = exclude_promisor_objects;\n> +\n> +\t/*\n> +\t * Ancestors must be verified before descendants so that parent\n> +\t * trees can be trusted without re-verification. Sort explicitly\n> +\t * rather than relying on the caller's ordering.\n> +\t *\n> +\t * sort_in_topological_order() silently drops cycle members,\n> +\t * so explicitly check if the size has changed.\n> +\t */\n> +\tnr_before = commit_list_count(*commits);\n> +\tsort_in_topological_order(commits, REV_SORT_IN_GRAPH_ORDER);\n> +\tif (commit_list_count(*commits) < nr_before)\n> +\t\tdie(_(\"cycle detected in incoming commit graph\"));\n\nI don't think we should just die, should we? That may not interact well\nwith git-receive-pack(1) and others that expect a broken connectivity\ncheck to bubble up errors so that they can properly report those to the\nclient and clean up their local state.\n\n> +\t*commits = commit_list_reverse(*commits);\n> +\n> +\tfor (iter = *commits; iter; iter = iter->next)\n> +\t\tverify_commit_tree(repo, iter->item, &vs);\n\n> +\tkh_destroy_oid_tree(vs.trees);\n> +\toidset_clear(&vs.trusted_blobs);\n> +\ttrace2_data_intmax(\"connectivity\", repo,\n> +\t\t\t \"trees_loaded\", vs.trees_loaded);\n> +\ttrace2_data_intmax(\"connectivity\", repo,\n> +\t\t\t \"blobs_checked\", vs.blobs_checked);\n> +}\n\nPatrick\n"},{"id":"554214","messageId":"xmqqece4j6t4.fsf@gitster.g","threadId":"66326","inReplyTo":"asNY7SfEohsOSf0J@pks.im","subject":"Re: [PATCH v2 1/2] Documentation: describe connectivity checking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-10-05T19:17:27Z","receivedAt":"2026-10-05T19:17:27Z","isPatch":true,"body":"Patrick Steinhardt writes:\n\n>> +Full connectivity check\n>> +-----------------------\n>> +\n>> +`check_connected()` (see `connected.c`) normally performs the\n>\n> I'm always a bit hesitant to directly refer to code in our docs. We\n> should either make this documentation part of \"connected.c\" directly, or\n> we should not refer to code. Otherwise, chances that this documentation\n> grows stale is very high.\n\nThis is totally outside the topic of documentation updates, but it\nmakes me wonder if we should pay attention to connectivity roots\nother than refs (like index entries) that we use when we run fsck.\n\n"},{"id":"554237","messageId":"asSOJVUTS3BMq6kS@pks.im","threadId":"66326","inReplyTo":"xmqqece4j6t4.fsf@gitster.g","subject":"Re: [PATCH v2 1/2] Documentation: describe connectivity checking","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-10-06T05:59:01Z","receivedAt":"2026-10-06T05:59:01Z","isPatch":true,"body":"On Mon, Oct 05, 2026 at 12:17:27PM -0700, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n> \n> >> +Full connectivity check\n> >> +-----------------------\n> >> +\n> >> +`check_connected()` (see `connected.c`) normally performs the\n> >\n> > I'm always a bit hesitant to directly refer to code in our docs. We\n> > should either make this documentation part of \"connected.c\" directly, or\n> > we should not refer to code. Otherwise, chances that this documentation\n> > grows stale is very high.\n> \n> This is totally outside the topic of documentation updates, but it\n> makes me wonder if we should pay attention to connectivity roots\n> other than refs (like index entries) that we use when we run fsck.\n\nHmm, I'm not sure. I guess performance of the connectivity check is\ntypically an issue on the server side only, much less so on the client\nside. And the server would of course typically not even have an index\nentry at all. Same for reflogs, at least in many setups.\n\nI also wonder whether that'd really speed things up if we add more data\nsources. At GitLab we typically have the problem that we have too many\nconnectivity roots with refs alone, and that is making the whole check\npainfully slow in some repositories. So adding more connectivity roots\nto it would probably be counterproductive.\n\nPatrick\n\n"}]}