Repository navigation
Description
Environment
- LayerFS 1.1.0, checkout
ad78914(theMAXIMUM_DIFF_CELLSfallback is unchanged on currentmainafter D8 · Refactor core/ into core, engine and api layers #463) - macOS Darwin 25.6.0 arm64, Docker Desktop 29.9.2, worker route
- Project: a 2000-line text file, two branches forked from main
Summary
When one side's changed-region span in a file exceeds the diff-table budget (MAXIMUM_DIFF_CELLS = 1 << 20 in core/crates/layerfs-content/src/compare/text.rs), the bounded diff fallback changes merge semantics silently: a second branch's small change inside that span is merged away with {"kind":"Merged"} and no conflict — a silent loss, not a conflict.
Git (ort) merges the same inputs cleanly with all three changes present. So LayerFS's merge is not git-equivalent precisely in the case where a file is large and one side touched it in two distant places.
Repro
A 2000-line file (line1 … line2000). Three branches:
span-test-a(from main): changes line 200 →line200-by-Aand line 1300 →line1300-by-A(span ≈ 1100 > 1023, so(span+1)² > 1<<20)span-test-b(from main): changes line 600 →line600-by-B(inside A's span)span-test-c(from main): changes line 600 →line600-by-C(control: A′ changes 200 and 900, span ≈ 700 < 1023)
$ layerfs branch merge span-test-a span-test-b span-large
{"kind":"Merged", ...} # no Conflict, no truncation flags
$ layerfs fs read span-large /span_a.txt
line 200: line200-by-A ✅
line 600: line600 ❌ B's change is GONE (silently)
line 1300: line1300-by-A ✅
$ layerfs branch merge span-test-a span-test-c span-small # control, span 700
{"kind":"Merged"} → 200/600/900 all present ✅ git-equivalent
Git on the same inputs merges all three changes cleanly.
Root cause
diff_lines (compare/text.rs) uses an exact LCS table while cells(x.len(), y.len()) <= MAXIMUM_DIFF_CELLS; a larger input keeps the common prefix/suffix and diffs the middle with the bounded path. When one side's first-to-last changed line spans more than ~1023 lines, the bounded diff of that side vs base yields no unchanged anchor line inside the span, so in merge3Lines the other side's small change falls inside one changed chunk on the losing side's diff — taken as "changed on one side", which discards the other side's change without a marker block.
The affected line does not even appear in the merge diagnostics (conflicts, lww, units), and conflictsTruncated/unitsTruncated are false — the reply genuinely contains no hint of the loss.
Impact
- Multi-agent workflows that split a large file by region (e.g. two agents editing distant functions of one 1400–2500 line file) silently lose one side's work on merge.
- This is worse than a spurious conflict:
{"kind":"Merged"}invites the supervisor to publish, and the loss is invisible until runtime behavior breaks.
Suggested directions (any of)
- When the bounded fallback was used for a merge input and the two sides both changed the file, treat the span as conflict-prone: emit a conflict (or a
diffFallback: truediagnostic on the merge result) instead of a silent take-one-side. - Raise/expose
MAXIMUM_DIFF_CELLSper file-size class, since a merge is offline and the exact LCS only needs the changed span, not the whole file. - Document the 1023-line span boundary in
agent.md's merge section, next to the existing diagnostics-bounds paragraph.
Verification standard
- For any two branches with non-overlapping single-line edits, the merge either contains both edits or reports a conflict — never
{"kind":"Merged"}with one edit missing, regardless of file size or edit span.
Activity
Aaron-Ben commentedon Nov 2, 2026
I reproduced this on
layerfs_v2_0_0(0b8ae8af5; macOS arm64,nativemachine, debug build). The code involved is byte-identical onmain(35d36575c) and at the reportedad78914:compare/text.rs,merge/text.rs,merge/decide.rsand the store-servicehistory/branch.rs. On this build the large-span case is a Conflict, not a silent loss, but it is still a false conflict that git merges cleanly.Setup (as in the report): a 2000-line
/span_a.txt(line1…line2000); Branches forked frommain:a: lines 200 and 1300 (span ≈ 1100)b: line 600 (it has its own Commit; checked withcommit list)a2: lines 200 and 900 (control, span ≈ 700)Commands
Results
Why
diff_lines(core/crates/layerfs-content/src/compare/text.rs): base →akeeps the common prefix/suffix; the middle is lines 200–1300 (1101 lines), and1102² = 1,214,404 > MAXIMUM_DIFF_CELLS (1 << 20), so the whole middle is reported as one removed-then-added block. No base line in 200–1300 is matched on both sides.merge3(merge/text.rs) then sees one chunk where ours ≠ base, theirs ≠ base and ours ≠ theirs, which is a conflict block, not "take one side". Callingmerge3directly on these inputs gives one hunk starting at line 200 (1101 lines per side), with both sides' changes inside the markers.engine/crates/layerfs-store-service/src/history/branch.rs, the!merged.clean()branch).The only path that answers
Mergedwithout a text merge is the fast-forward one (one side is an ancestor of the other). @fisherever, could you share the full merge reply (in particularfastForward) andcommit listofspan-test-b? Ifspan-test-bhad no Commit of its own, the merge fast-forwards tospan-test-a, which matches what you saw.If that holds, a closer title would be: merge: a changed span over ~1023 lines gives a false conflict where git merges cleanly.
Related: the conflict reply omits this hunk (
hunksOmitted: true) because the 1101-line block does not fit the reply window, so the caller learns "1 block" but not where.Possible fix, if wanted: keep the exact table for inputs that fit it, and replace only the "whole middle as one block" fallback with a bounded-memory line diff (linear-space Myers, or unique-line anchors first). Every output that is exact today stays the same; inputs past a work bound would still conflict, never drop a change.
PoisonGodv commentedon Nov 2, 2026
I can confirm Aaron-Ben's reading at
35d36575c: the result is a false conflict, not a silent loss. I did not observe the "Merged, B's change gone" outcome.Check (unit test in
layerfs-contentcallingmerge::merge3directly, Linux x86_64, Rust 1.85.1). Base isline1..line2000plus a trailing newline. A edits lines 200 and 1300, B edits line 600.merge3returns 1 hunk at output line 200 with 1101 ours / 1101 theirs lines.textalso contains all three edits (it is the conflict-marked text).git merge-file base ours theirson the same three files exits 0 with all three edits and no markers.The threshold matches the cause in
diff_lines(compare/text.rs): 1024² = 1<<20, so a trimmed middle of 1023 lines per side still gets the exact table and 1101 does not.Proposal. Keep the first early return, the prefix/suffix trim and the "middle fits the table" arm exactly as they are, and change only the last arm, which today emits one Removed block plus one Added block. For a middle that still exceeds the bound: find lines that occur exactly once on each side, take the longest increasing subsequence of them as anchors, run the existing
table_diffon each gap between anchors where it fits, and keep the current block only for a gap that still does not fit. No new dependency, no file-size cap, no new constant. On the repro the 1099 interior lines are all anchors, so the only gaps are lines 200 and 1300, and the merge is clean. A real overlap (both sides edit line 600) shrinks to a 1-line hunk instead of 1101.What it would not fix: a span with no unique shared lines (long repeated runs) is still one block, and files over the text byte bound are still reported as Binary in
merge/decide.rs. It also changesline_diff,match_lines(sofs.blamefor files of at most 2000 lines) andmerge3output, but only for inputs that hit the coarse fallback today.Two questions that change the design:
diff_lines(so diff and blame benefit too), or do you want it confined to merge?I'm happy to implement it once you say which way, with the repro as a regression test. I will not open a PR before that.
Aaron-Ben commentedon Nov 2, 2026
Thanks @PoisonGodv. The
git merge-filecheck is a useful addition, and your reading of the code matches mine.On your two questions, my view as a data point for the owner:
diff_lines. Inputs that fit the table today keep byte-identical output, so only inputs that hit the coarse fallback change, and blame and file diffs get the same improvement as merge.merge3, whose result depends on the anchors rather than the edit count. But anchors are not free of bounds either: each gap's table is bounded, while the gaps together are not. On a ~1 MiB input (512 gaps of 1000alines vs 1000blines, each closed by a unique line; Rust 1.85.1, macOS arm64, test profile, one exploratory run each):MAXIMUM_DIFF_CELLSbudgetThe in-lane merge step also text-merges files up to
MAXIMUM_TEXT_BYTES(core/docs/architecture/81-compare-and-merge.md), so this matters there. A shared budget keeps the worst case at one table plus O(n log n) for the anchors, with no new constant. A gap past the budget stays a block, so the result is a conflict, never a lost change.I have this as a one-file prototype (
compare/text.rs, +56 production lines):layerfs-contenttests, Clippy and rustfmt pass.Once the owner picks a direction, I'm happy to open it as a PR with the repro as a regression test, or to hand it to @PoisonGodv if they'd rather take it. I won't open anything before that.
PoisonGodv commentedon Nov 2, 2026
Thanks @Aaron-Ben. The shared
MAXIMUM_DIFF_CELLSbudget is the better design: my sketch only bounded each gap's table, so with many gaps the total was not bounded. I'll leave the implementation to you.One data point on the blame side, since it is the other caller of the coarse arm (
read/blame.rscallsmatch_lineswhen both versions arecomplete, i.e. at most 2000 lines, socomparisonCoarsestays false there). On the same 2000-line file, callingmatch_lines(base, new)at35d36575c:Blame treats an unmatched line as written by the newer version, so today a two-line edit 1100 lines apart reassigns about 1100 untouched lines to that commit. With anchors those 1099 lines should map and keep their owner. That would be a user-visible blame change, so it is worth a line in the PR description and a regression test through
fs.blame; the existingsdk_blame_coarsecases use 2005 lines and take the byte path, so they do not cover it.Two inputs your random test may not hit: many repeated lines with few unique ones (the span has no anchors, so it must stay a block and still lose no edit), and a unique line moved or duplicated on one side while another distant edit exists.
I'm glad for you to open the PR once the owner picks a direction. I'll stay out of
compare/text.rs, and can add the blame regression test on top of yours if that's useful.Aaron-Ben commentedon Nov 2, 2026
Thanks @PoisonGodv, the blame data point is useful. I'll mention it in the PR description and add an
fs.blameregression test.I ran your two inputs on the prototype (shared budget), with
git merge-fileas a reference:So a span with no anchors stays a block, as expected: a false conflict, never a lost edit. On the blame side,
match_lines(base, new)for the 200/1300 edit leaves 2 of 2000 old lines unmatched instead of 1101.These cases will go into the regression tests. Thanks for the offer on the blame test; I’ll include the blame test in the PR as well
fix(content): match unique lines when a diff middle exceeds its table (…
Aaron-Ben commentedon Nov 2, 2026
The change is on a branch if it helps the decision: https://github.com/Aaron-Ben/layerfs/tree/fix/517-diff-anchors (one commit on
layerfs_v2_0_0at0b8ae8af5, with the regression tests). I'll open a PR once you pick a direction and a target branch.PoisonGodv commentedon Nov 2, 2026
Thanks @Aaron-Ben — the prototype results look great, and the two edge cases behaving exactly as designed (a no-anchor span stays a block: false conflict, never a lost edit) is what I hoped to see. The 1101 → 2 unmatched-lines drop on the blame side is a nice bonus.
Direction: the shared
MAXIMUM_DIFF_CELLSbudget is the right call — it's the only variant that bounds total cost across many gaps, and your results show it gives up nothing on correctness. I don't think we need to wait on more design discussion.Target branch:
layerfs_v2_0_0, please. It's where active work is landing right now (#528, #531), and your branch is already based on its current tip (0b8ae8af), so there's nothing to rebase.Please go ahead and open the PR, with the blame regression test and the blame note in the description as you proposed. If a maintainer prefers a different direction or base, it's easy to adjust on the PR. Thanks for running with this!
fix(content): match unique lines when a diff middle exceeds its table (…
Aaron-Ben commentedon Nov 5, 2026
Opened as a draft: #564 , targeting
layerfs_v2_0_0and rebased on its current tip (d43047413). It now includes thefs.blameregression test and the blame note. I'll keep it a draft until a maintainer confirms the direction.fix(content): match unique lines when a diff middle exceeds its table (…
Mola-maker commentedon Nov 8, 2026
Resolved by merged PR #564.
fix(content): align store-service line_alignment::exact with the #517 …