Summary

Add a primitive to merge a commit (transaction) from one branch onto another branch. The
mechanism is:

1. Read the transaction that produced the source branch's commit.
2. Apply that transaction as a new commit on the target branch.
3. Graft the source branch's base into the target branch's base_paths so the target
   resolves the merged data files in place in the source's storage.

Today branches are cheap shallow clones, but there is no way to move a commit between
branches — no merge, cherry-pick, or fast-forward operation exists. This is the missing
primitive needed for branch rebasing and for fast-forwarding main to a branch.

Motivation

Lance branches are created by shallow clone: a branch's manifest references the parent's data
files through base_paths instead of copying them (see Background). But branches are currently a
one-way fork — once two branches diverge, there is no built-in way to bring a commit from one
into the other.

Features that need this:

• Rebase a branch onto an updated parent (re-apply branch work on top of newer commits).
• Fast-forward / promote a branch's tip into main.

Both reduce to the same operation: take a transaction from branch X and replay it onto branch Y,
keeping the data-file references intact.

Background: how branch data references work today

Two existing fields make cross-branch data references possible:

• Manifest.base_paths: HashMap<u32, BasePath> — a table of external base locations. A
  BasePath { id, name, is_dataset_root, path } records a full URI (e.g. another dataset/branch
  root). (rust/lance-table/src/format/manifest.rs)
• DataFile.base_id: Option<u32> — each data file in a fragment is resolved relative to the
  BasePath named by its base_id, or relative to the current dataset root when base_id is
  None. (rust/lance-table/src/format/fragment.rs)

Manifest::shallow_clone already performs base grafting, but for a whole manifest: it inserts
the source as a BasePath (is_dataset_root = true) and stamps every fragment's base_id to
point at it. That is exactly why a branch can be opened standalone and still read the parent's
data.

Separately, every commit records a transaction_file (_transactions/<id>.txn) capturing the
Operation (Append / Delete / Update / …) and the new fragments it introduced. It is readable
via read_transaction_file (rust/lance/src/io/commit.rs).

This feature generalizes shallow_clone's base grafting from "the whole manifest" to "a single
transaction's fragments," replayed onto an existing target branch.

Proposed mechanism

merge(source_branch, target_branch):
  1. txn      = read the source branch's transaction(s) since the fork point
  2. regraft  = for every new DataFile the operation introduces:
                  ensure the target manifest can resolve it ->
                    add a BasePath for the source's root into target.base_paths
                    (allocate a fresh base_id), and set that fragment's base_id to it.
                  (files that already carried a base_id inherited from the source's own
                   bases: copy those BasePath entries into the target, remapping ids.)
  3. apply    = commit the regrafted operation onto the target branch via the normal
                commit path (divergence handled by existing optimistic conflict resolution)

The result: the target branch's new tip references the merged data files physically located in
the source branch's storage, resolved through the grafted base_paths.

Visual — how a merge references data files

flowchart LR
    subgraph S["Source branch A — storage"]
      direction TB
      TA["tip manifest A<br/><b>transaction = Append(frag → D2)</b>"]
      D2[("D2.lance<br/>(new data file)")]
      TA -->|"base_id = None<br/>(local to A)"| D2
    end

    subgraph T0["Target branch B — before merge"]
      direction TB
      MB0["tip manifest B"]
    end

    subgraph T1["Target branch B — after merge"]
      direction TB
      MB1["new tip manifest B+1<br/>base_paths[9] = A-root<br/>frag(D2, <b>base_id = 9</b>)"]
    end

    TA ==>|"1. read transaction"| MB1
    MB0 -->|"3. apply commit"| MB1
    MB1 -. "2. graft A as base · resolves D2 in place" .-> D2

    style D2 fill:#e8f5e9,stroke:#43a047
    style MB1 fill:#e3f2fd,stroke:#1e88e5

Visual — the three steps in sequence

sequenceDiagram
    autonumber
    participant Src as Source branch A
    participant Eng as Merge engine
    participant Tgt as Target branch B

    Eng->>Src: read tip transaction (_transactions/*.txn)
    Src-->>Eng: Operation = Append(frag → D2)
    Note over Eng: rewrite fragment refs:<br/>add BasePath(A-root) to B.base_paths,<br/>set merged frag base_id → A-root
    Eng->>Tgt: commit regrafted Operation (normal commit path)
    Tgt-->>Eng: new tip B+1 (references D2 in A's storage)

API sketch (illustrative, not final)

// Cherry-pick the source branch's tip transaction onto the target branch.
dataset.merge_branch(
    source: BranchRef,        // e.g. "tree/feature" or "branch@version"
    options: MergeOptions {   // squash range, conflict policy, copy-vs-reference, ...
        ..Default::default()
    },
) -> Result<Dataset>;        // returns the target branch advanced by one commit

Special cases fall out of the same primitive:

• Fast-forward: the target has not diverged from the fork point → apply with no replay.
• Rebase: re-apply a branch's commits onto a new base — see below.

Modeling rebase on top of merge

A rebase of a branch feature onto an updated base (e.g. the latest main) is just the merge
primitive applied in a loop, followed by a branch-pointer swap:

1. Branch the new base — create a fresh branch R from the tip of the base. R starts as a
   shallow clone of that tip.
2. Replay the commits — for each commit feature accumulated since its old fork point, run
   the merge above to apply it onto R.
3. Repoint the name — point the branch name feature at R, and discard the old physical
   branch. feature now sits on top of the new base with its work replayed.

gitGraph
   commit id: "m1"
   commit id: "m2"
   branch feature
   checkout feature
   commit id: "f1"
   commit id: "f2"
   checkout main
   commit id: "m3"
   branch R
   checkout R
   commit id: "f1'"
   commit id: "f2'"

feature forked from main at m2, then the two diverged — main advanced to m3 while
feature added f1, f2. The rebase creates the temp branch R from main's tip (m3) and
replays f1, f2 onto it as f1', f2' (steps 1–2). Finally the name feature is repointed from
its old line to R (step 3), and the old physical branch is reclaimed by GC.

Step 3 is the catch. Today a branch's physical path is derived from its name (feature lives
at tree/feature), so the name cannot be moved onto R without physically relocating data. That
is exactly the format limitation raised in #7185, whose proposal — UUID-based physical
branch directories (tree/<uuid>) with a branch_name → uuid mapping in branch metadata — is
the prerequisite that turns "repoint feature to R" into a cheap metadata update. With that
indirection the rebase is simply: create R under a new UUID, replay onto it, then swap the
feature → uuid mapping; the old UUID directory becomes unreferenced and is reclaimed by GC.