Skip to content

merge: a changed span over the diff-table budget (~1023 lines) silently drops the other branch's change inside it — Merged, not Conflict #517

Closed

Description

@fisherever

Environment

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-A and 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)

  1. 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: true diagnostic on the merge result) instead of a silent take-one-side.
  2. Raise/expose MAXIMUM_DIFF_CELLS per file-size class, since a merge is offline and the exact LCS only needs the changed span, not the whole file.
  3. 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

  1. Aaron-Ben commented on Nov 2, 2026

    @Aaron-Ben

    I reproduced this on layerfs_v2_0_0 (0b8ae8af5; macOS arm64, native machine, debug build). The code involved is byte-identical on main (35d36575c) and at the reported ad78914: compare/text.rs, merge/text.rs, merge/decide.rs and the store-service history/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 from main:

    • a: lines 200 and 1300 (span ≈ 1100)
    • b: line 600 (it has its own Commit; checked with commit list)
    • a2: lines 200 and 900 (control, span ≈ 700)
    Commands
    export LAYERFS_HOME=~/lfs-517/home
    mkdir -p src && for i in $(seq 1 2000); do echo "line$i"; done > src/span_a.txt
    layerfs store create r517
    layerfs project init r517/p ./src
    for b in a b a2; do layerfs branch fork r517/p $b main; done
    sed -e 's/^line200$/line200-by-A/' -e 's/^line1300$/line1300-by-A/' src/span_a.txt | layerfs file write r517/p a /span_a.txt -m A
    sed -e 's/^line600$/line600-by-B/' src/span_a.txt | layerfs file write r517/p b /span_a.txt -m B
    sed -e 's/^line200$/line200-by-A/' -e 's/^line900$/line900-by-A/' src/span_a.txt | layerfs file write r517/p a2 /span_a.txt -m A2
    layerfs commit list r517/p b
    layerfs branch merge r517/p large a b
    layerfs branch merge r517/p small a2 b

    Results

    $ layerfs branch merge r517/p large a b      # exit 125
    {"code":"Conflict","message":"a + b conflict in 1 file(s); nothing was created",
     "detail":{..., "conflicts":[{"path":"/span_a.txt","kind":"content","blocks":1,"hunksOmitted":true,"hunks":[]}], ...}}
    
    $ layerfs branch merge r517/p small a2 b     # exit 0
    {"kind":"Merged","fast_forward":false, ...}
    line 200: line200-by-A   line 600: line600-by-B   line 900: line900-by-A
    

    Why

    • diff_lines (core/crates/layerfs-content/src/compare/text.rs): base → a keeps the common prefix/suffix; the middle is lines 200–1300 (1101 lines), and 1102² = 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". Calling merge3 directly on these inputs gives one hunk starting at line 200 (1101 lines per side), with both sides' changes inside the markers.
    • A merge that is not clean is refused and creates nothing (engine/crates/layerfs-store-service/src/history/branch.rs, the !merged.clean() branch).

    The only path that answers Merged without 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 particular fastForward) and commit list of span-test-b? If span-test-b had no Commit of its own, the merge fast-forwards to span-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.

  2. PoisonGodv commented on Nov 2, 2026

    @PoisonGodv

    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-content calling merge::merge3 directly, Linux x86_64, Rust 1.85.1). Base is line1..line2000 plus a trailing newline. A edits lines 200 and 1300, B edits line 600.

    • merge3 returns 1 hunk at output line 200 with 1101 ours / 1101 theirs lines.
    • The ours side holds both of A's edits and not B's. The theirs side holds B's edit. So nothing is dropped; the merge is refused.
    • The merged text also contains all three edits (it is the conflict-marked text).
    • Control: A editing lines 200 and 900 (701-line middle, exact table) merges cleanly with all three edits.
    • git merge-file base ours theirs on 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_diff on 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 changes line_diff, match_lines (so fs.blame for files of at most 2000 lines) and merge3 output, but only for inputs that hit the coarse fallback today.

    Two questions that change the design:

    1. Are you fine with the change living in diff_lines (so diff and blame benefit too), or do you want it confined to merge?
    2. Anchors (not minimal, but no extra bound) or an exact linear-space Myers (needs an explicit work budget)?

    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.

  3. Aaron-Ben commented on Nov 2, 2026

    @Aaron-Ben

    Thanks @PoisonGodv. The git merge-file check 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:

    1. Where: 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.
    2. Which: anchors, with one more bound. Myers would need a work budget too, and a minimal edit script does not help 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 1000 a lines vs 1000 b lines, each closed by a unique line; Rust 1.85.1, macOS arm64, test profile, one exploratory run each):
    variant time
    today, the largest single table (1023 × 1023) ~8–9 ms
    anchors, one table per gap that fits 2.0 s
    anchors, all gaps sharing one MAXIMUM_DIFF_CELLS budget 30 ms

    The 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):

    • the repro merges cleanly, and an overlap at line 1300 becomes a 1-line hunk;
    • in a 300-case random test, every input that does not reach the last arm (228) gives byte-identical output to the current code; the other 72 always rebuild both sides and never match fewer lines;
    • the layerfs-content tests, 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.

  4. PoisonGodv commented on Nov 2, 2026

    @PoisonGodv

    Thanks @Aaron-Ben. The shared MAXIMUM_DIFF_CELLS budget 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.rs calls match_lines when both versions are complete, i.e. at most 2000 lines, so comparisonCoarse stays false there). On the same 2000-line file, calling match_lines(base, new) at 35d36575c:

    • edits at lines 200 and 1300: 1101 unmatched lines, of which 1099 were not edited;
    • edits at lines 200 and 900: 2 unmatched lines, none unedited.

    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 existing sdk_blame_coarse cases 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.

  5. Aaron-Ben commented on Nov 2, 2026

    @Aaron-Ben

    Thanks @PoisonGodv, the blame data point is useful. I'll mention it in the PR description and add an fs.blame regression test.

    I ran your two inputs on the prototype (shared budget), with git merge-file as a reference:

    input layerfs git
    3000 lines from 4 repeated values, no unique line; A edits 200 and 2500, B edits 1300 1 conflict hunk, no edit lost clean
    the same with a unique line every 1100 lines clean, same text as git clean
    A moves line 500 below 1500 and edits 200 and 1300; B edits 900 clean, same text as git clean
    A duplicates line 700 below 1600 and edits 200 and 1300; B edits 1000 clean, same text as git clean
    as above, but B edits line 700 itself clean, same text as git clean

    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

  6. Aaron-Ben commented on Nov 2, 2026

    @Aaron-Ben

    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_0 at 0b8ae8af5, with the regression tests). I'll open a PR once you pick a direction and a target branch.

  7. PoisonGodv commented on Nov 2, 2026

    @PoisonGodv

    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_CELLS budget 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!

  8. Aaron-Ben commented on Nov 5, 2026

    @Aaron-Ben

    Opened as a draft: #564 , targeting layerfs_v2_0_0 and rebased on its current tip (d43047413). It now includes the fs.blame regression test and the blame note. I'll keep it a draft until a maintainer confirms the direction.

  9. added theissue type on Nov 5, 2026
  10. added this to the LayerFS v2.0.0 milestone on Nov 5, 2026
  11. Mola-maker commented on Nov 8, 2026

    @Mola-maker
    Member

    Resolved by merged PR #564.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions