merge
Source: crates/lvcs-ws/src/merge/mod.rs.
/// The inputs of a bundle id (decision 57), in hash order: the
/// [`BundleId`] is the `HASH` of the canonical CBOR array of these four,
/// each a byte string, so it never depends on the changes that carry it.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub struct BundleInputs {
/// The workspace merged back.
pub workspace: WorkspaceId,
/// The merging participant.
pub merger: ParticipantKey,
/// The workspace's visible frontier when the merge started.
pub workspace_frontier: FrontierId,
/// The visible frontier of the workspace merged into, when the merge
/// started.
pub base_frontier: FrontierId,
}
/// Merge a workspace back (design §8, `ws.merge`).
///
/// It is a workspace event (`WorkspaceViewEvents::MergeRequest`), computed once, by the
/// merging peer's workspace actor, as one `WorkspaceMerged` bundle. Per
/// override, the claim's text at claim time is diffed against the override
/// and applied as fine-grained edits at the base's current anchors when the
/// base is unchanged inside the range, and merged three-way within the
/// range otherwise; only genuinely overlapping edits become a [`Conflict`].
/// Every change is a `BundleEdit` tagged with the bundle id; merge-back is
/// the only way a workspace's work reaches its base. Answered with exactly
/// one [`MergeResult`] for `req`.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MergeRequest {
/// The request its [`MergeResult`] answers.
pub req: RequestId,
/// The merging participant's origin: the author and time of every
/// change in the bundle.
pub origin: Origin,
/// The bundle id's inputs.
pub inputs: BundleInputs,
/// The workspace merged into: always the workspace's base, `main`, or
/// for a stacked workspace the one it stacks on, which absorbs the
/// bundle (`StackedBundle` in `crate::workspace`).
pub into: WorkspaceBase,
/// Block the merge until checks pass on a preview of the merged state
/// (design §8).
pub require_validated: bool,
/// Every Automerge actor the daemon can name, mapped to its participant
/// through its key store (each local participant's `AuthorId` on this
/// device, M2) or, for a remote author, its `ChangeSig` signer, which
/// the documents report (`DocOutput::Signers`, M3), for
/// [`Conflict::authors`].
pub authors: BTreeMap<AuthorId, ParticipantKey>,
/// Leave derived overrides out of the bundle (row 180): set with
/// the generator, whose next counted generation covers the merged
/// inputs, so the merging participant is offered one
/// `derived_superseded` per path left out.
pub leave_derived: bool,
}
/// One document a bundle changed, as its merge record lists it.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MergedDoc {
/// The document's heads in the base visible frontier the merge read,
/// so two records can be tested for concurrency: neither's base heads
/// contain the other's target heads (decision 65).
#[serde(with = "cbor::heads")]
pub base: Vec<ChangeHash>,
/// The document's heads with the bundle's changes: a peer's visible
/// frontier advances over the bundle only once the record and every
/// target head are present locally (decision 48).
#[serde(with = "cbor::heads")]
pub target: Vec<ChangeHash>,
/// The base ranges the bundle's range overrides changed, as their claim
/// anchors, cursor pairs anchored at the claim's heads, which `base`
/// descends from (decision 65). Two concurrent bundles whose ranges
/// overlap in a document open a conflict thread to both mergers
/// (`lvcs_doc::CheckOverlap`).
pub ranges: Vec<RangeAnchor>,
/// The bundle made a change here that has no range (decision 108): a
/// whole-document override's body or executable bit (its claim anchors
/// no cursor pair, so even a text change of it names none), a
/// workspace-local file's recreate, a binary body, or a removal. Overlap
/// detection treats a whole entry as overlapping every range of the
/// document, and every other whole entry. `ranges` is empty then: a
/// document's changes come from one whole-document or workspace-local
/// override, from a whiteout, or from range overrides, never from two
/// of them.
pub whole: bool,
}
/// A bundle's merge record, written to `.lvcs/registry` as a
/// `RecordBundle` holding its canonical CBOR encoding, and signed
/// (decisions 48 and 65).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MergeRecord {
/// The `HASH` of `inputs`.
pub bundle: BundleId,
/// The bundle id's inputs, among them the workspace id.
pub inputs: BundleInputs,
/// Every document the bundle changed, by address.
pub docs: BTreeMap<String, MergedDoc>,
}
/// A merge-back conflict (design §8).
///
/// It is an override's edits and the base's edits since the claim that
/// genuinely overlap, an override whose anchor was lost, or a whiteout of a
/// file the base changed since (decision 86). It opens a thread anchored on
/// `address` (`ThreadAnchor::Address`) and addressed (`ThreadOpen.to`) to
/// `authors` (design §9). The conflicts of one merge in one document share
/// that thread, since its id inputs (the anchor, the merger, the merge's
/// time) are the same; its `to` is the union of their authors. Conflicts
/// between two concurrent bundles (decision 65) are not these: they come
/// from merge records ([`MergedDoc::ranges`] and [`MergedDoc::whole`]).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Conflict {
/// The base document the override claimed from, or the whited-out
/// path.
pub address: String,
/// What conflicts: an override, or the path's whiteout (decision 86).
pub subject: ConflictSubject,
/// Why the conflict opened.
pub cause: ConflictCause,
/// The conflicting base range, in code points at the document's target
/// heads; `Collapsed { at }` when that range is empty, `at` the gap
/// where it is there (decision 92): always for an anchor-lost override,
/// whose text the base no longer holds a place for, and `Collapsed {
/// at: 0 }`, no range, when the base deleted the file (decision 100).
pub span: AnchorSpan,
/// The participants whose edits overlap, on the workspace's side and on
/// the base's side. The daemon maps each Automerge actor (`AuthorId`) to
/// its participant through its key store (M2) or the `ChangeSig` signer
/// the documents report (`DocOutput::Signers`, M3), as
/// [`MergeRequest::authors`]; an author it can't map is omitted.
pub authors: BTreeSet<ParticipantKey>,
/// The conflict thread, at `THREAD_ADDRESS`.
pub thread: ThreadId,
/// `span`'s lines in the document's text after the plan, named as the
/// thread names a range there (decisions 160, 165, and 197), one name
/// per conflict, never joined across conflicts; `None` for a
/// collapsed span, a document that holds no text after the plan, an
/// `AnchorLost` conflict, and a `Whiteout`.
pub lines: Option<LineName>,
}
/// What a [`Conflict`] is about (decision 86). Ordered: overrides by id,
/// then the whiteout.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub enum ConflictSubject {
/// One of the workspace's overrides of the document.
Override(OverrideId),
/// The workspace's whiteout of the path.
Whiteout,
}
/// Why a [`Conflict`] opened (decision 92).
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum ConflictCause {
/// The override's edits and the base's edits since the claim genuinely
/// overlap, and the base's text was kept: also an override whose body
/// or the base's is not text a merge needs, whose range doesn't fit
/// the base's text, or whose claim overlaps a smaller id's (M3).
Overlap,
/// The base deleted the override's whole range, or the whole file
/// (decision 100), so it has no anchor; it merged nothing.
AnchorLost,
/// The base changed the whited-out file since the whiteout, so the
/// file was kept.
Whiteout,
}
/// The answer to a [`MergeRequest`] (`WorkspaceOutput::Merged`).
///
/// It is sent once the changeset is closed (decision 94): every change of
/// the bundle is applied and rendered, its record written, and every
/// override and whiteout the merge read has left the index.
///
/// A refused merge-back (decision 88): `rejected` maps each base document
/// that refused a bundle change or a merge read to its first reason (and,
/// after a restart, each one the merge still waited on to `Failed`,
/// decision 93). When it is not empty, the merge is answered once every
/// read and change it routed is answered (at once after a restart), and no
/// merge record is written, no thread
/// opens, nothing leaves the index, and `ws.merge` answers an error;
/// `conflicts` is empty and `record` lists only the documents whose every
/// bundle change applied (none when a read was refused). M2 has no bundle
/// visibility gate (it arrives with sync in M3), so bundle changes applied
/// before the refusal stay visible in M2.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MergeResult {
/// The request answered.
pub req: RequestId,
/// The bundle's merge record: for a refused merge, only the documents
/// whose every bundle change applied.
pub record: MergeRecord,
/// The merge's conflicts, each with its thread; empty for a refused
/// merge.
pub conflicts: Vec<Conflict>,
/// Each base document that refused a bundle change or a read, with its
/// first reason; empty for a merge that applied.
pub rejected: BTreeMap<String, RejectReason>,
/// The path of each derived override the merge left out
/// ([`MergeRequest::leave_derived`], row 180), for which the merging
/// participant is offered one `derived_superseded`; empty without
/// `leave_derived` and for a refused merge.
pub left_derived: BTreeSet<String>,
}
/// Everything [`plan`] reads: the request, and every base document the
/// workspace's overrides and whiteouts touch, as the workspace actor holds
/// them when the merge starts.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MergeInput {
/// The merge request planned.
pub request: MergeRequest,
/// The workspace actor's next request id for a change it routes; the
/// plan numbers its `BundleEdit`s from it, in address order.
pub next_req: u64,
/// By base address (`OverrideClaim.base`, or a workspace-local file's
/// path).
pub docs: BTreeMap<String, BaseInput>,
}
/// One base document of a merge.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct BaseInput {
/// Its current heads, at which every change of the plan applies: for a
/// workspace-local file's path, those of the path's file document,
/// whose body is `Deleted` at its genesis heads or after a removal
/// (decision 98).
#[serde(with = "cbor::heads")]
pub heads: Vec<ChangeHash>,
/// Its current body there. A workspace-local file is recreated over a
/// `Deleted` body, and conflicts with any other: the base created the
/// file meanwhile (decision 98).
pub body: FileBody,
/// Its current executable bit there.
pub executable: bool,
/// The workspace whites the path out (decision 86).
pub whiteout: Option<WhiteoutInput>,
/// The workspace's overrides of it.
pub overrides: BTreeMap<OverrideId, OverrideInput>,
}
/// A whiteout of a merge (decision 86).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct WhiteoutInput {
/// The heads of the document that held the path in the base view when
/// it was whited out (the index's `WhiteoutEntry`): the merge deletes
/// the file only while [`BaseInput::heads`] equal them.
#[serde(with = "cbor::heads")]
pub heads: Vec<ChangeHash>,
/// Who a conflict on the whiteout names: the participant who placed it
/// and the base's editors beyond `heads` (`ReadAt` authors), mapped
/// through [`MergeRequest::authors`], unknown authors omitted.
pub authors: BTreeSet<ParticipantKey>,
}
/// One override of a merge.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct OverrideInput {
/// The override's claim.
pub claim: OverrideClaim,
/// The override's body at its init heads: what the base view held in
/// the claimed scope at claim time (read with `ReadAt`).
pub claimed: FileBody,
/// The override's executable bit at its init heads, the bit its init
/// change wrote (read with the same `ReadAt`, decision 85).
pub claimed_executable: bool,
/// The override's body now.
pub current: FileBody,
/// The override's executable bit now.
pub executable: bool,
/// The claim's range resolved at the base's `heads` (`None` for a
/// whole-document or workspace-local override).
pub span: Option<AnchorSpan>,
/// A derived save marked it derived (row 180): a whole-document or
/// workspace-local override that merge-back writes whole at its claim's
/// base heads, never merged three-way, or leaves out.
pub derived: bool,
/// Who a conflict on this override names: the claimant, the override's
/// editors since its init, and the base's editors inside the range since
/// the claim (`ReadAt` authors), mapped through
/// [`MergeRequest::authors`], unknown authors omitted.
pub authors: BTreeSet<ParticipantKey>,
}
/// What [`plan`] decided: the workspace actor routes the edits, then, from
/// their answers, completes and records the merge record, opens the
/// threads, and answers with a [`MergeResult`].
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MergePlan {
/// The bundle's changes per base document, in the order they apply,
/// each at that document's `BaseInput.heads`.
pub edits: BTreeMap<String, Vec<BundleEdit>>,
/// The merge record, its `target` heads empty: the workspace actor
/// fills each document's from the answer to its last `BundleEdit`.
pub record: MergeRecord,
/// The plan's conflicts: per document in address order, each
/// document's by span and then subject.
pub conflicts: Vec<Conflict>,
/// The thread each conflicting document's conflicts open, by thread id.
pub threads: BTreeMap<ThreadId, ThreadOpen>,
/// The path of each derived override left out
/// ([`MergeRequest::leave_derived`]).
pub left_derived: BTreeSet<String>,
}
/// Plan a merge-back (design §8): a pure function of `input`, so the
/// workspace actor's action can call it and replay gets the same plan.
///
/// It reads no clock and no RNG; the only time is `request.origin.time_ms`.
///
/// Per base document, in address order:
/// - A whiteout deletes the file (`Removed`, none when the body is already
/// `Deleted`) only when the base's `heads` equal the whiteout's (compared
/// as sets): the base is as the workspace saw it when it deleted the
/// file. Otherwise the base changed the file since, and the whiteout is a
/// conflict (`Whiteout`) that keeps the base, so a base edit the
/// workspace never saw is never deleted (decision 86). Either way it
/// hides the document's overrides, which merge nothing. Of concurrent
/// whiteouts of one path (M3), the input is the entry the index
/// resolves their key to; testing any one of them is safe, since the
/// base equals its heads only while its placer has seen every base edit.
/// - A range override is merged three-way within its span, the claimed
/// text the common ancestor: the override's diff from it and the base's
/// diff from it (the base's text inside the span now) are hunks of the
/// claimed text, each one splice of the shortest code point diff (a
/// maximal run of changes between unchanged code points). When the base
/// is unchanged inside the range its diff is empty, so the override's
/// diff applies as fine-grained edits at the span. Hunks of the two sides
/// genuinely overlap when their replaced ranges share a code point, an
/// insertion lies strictly inside the other side's replaced range, or
/// both are insertions at one gap; touching hunks don't (decision 95),
/// and an insertion at a replaced range's start or end lands before or
/// after the replacement. Overlapping hunks form a cluster; one whose two
/// versions are equal is already in the base, and any other is a
/// conflict (`Overlap`) that keeps main's text there, the base's
/// (decision 99), while the override's other hunks still apply. An
/// override whose text equals its claimed text merges nothing.
/// - A range override whose span is `Collapsed` (or `None`) lost its
/// anchor: a conflict (`AnchorLost`) that changes nothing in the base
/// (decision 95). So does every range override of a base whose body is
/// `Deleted`, whatever its span: the base deleted its whole range, and
/// the conflict has no range (decision 100). One whose bodies are not
/// text, whose base body is binary, or whose span doesn't fit the base's
/// text, is a conflict (`Overlap`) that merges nothing. Range overrides
/// merge in order of their span's start, equal starts by override id.
/// - A whole-document override of a present base is merged three-way over
/// the body: written when only the override changed it (`Text` splices of
/// the base's text, `Binary`, or `Removed`), merged as text when both
/// changed text, and a conflict (`Overlap`) that keeps the base
/// otherwise, or when a text must be written over a binary or deleted
/// base, whose `/content` is not an input. Its executable bit is merged
/// three-way against `claimed_executable` (decision 85): `Executable`
/// (the override's bit) is written only when the bit differs from both
/// the claim-time bit and the base's, and the file exists after the
/// merge, so a chmod the base made after the claim is kept.
/// - A workspace-local file is written when the base body is `Deleted`, at
/// its genesis heads or after history: `Recreate` with its text (an empty
/// text included, which still creates the file), or `Binary` (decision
/// 98). When the base body is not deleted (main created the file
/// meanwhile), it is a conflict (`Overlap`) that keeps the base, unless
/// both hold the same body. One the workspace deleted again merges
/// nothing. Its executable bit goes with its body: written when it
/// differs from the base's and the merge writes the body, or the base
/// already holds the same one.
/// - A derived override (row 180: `derived`, a whole-document or
/// workspace-local one, the only override of its document) is never
/// merged three-way and never conflicts. With `request.leave_derived`
/// it changes nothing, and when it would have written something its
/// path joins `left_derived`, since the next counted generation covers
/// the merged inputs. Otherwise, when its body
/// or bit changed since the claim and the base doesn't hold its body
/// already, its whole text (`Recreate`) or bytes (`Binary`), then a
/// changed bit, are written at the claim's `base_heads` (the base's
/// `heads` for a workspace-local file), each `BundleEdit` flagged
/// `derived` = `Mark`: a base change since the claim stays concurrent,
/// and the winner rule decides and tells the loser. Its record entry is
/// `whole`, with `base` = the document's `heads`.
/// - Concurrent claims that overlap (M3) give the text to the override
/// with the smaller id; the others conflict (`Overlap`).
///
/// A document's range splices, sorted and with touching splices joined, are
/// one `Text` change; an executable change follows. Every change is a
/// `BundleEdit` at the document's `heads` (a derived override's at its
/// claim's base heads), numbered from `next_req` in that
/// order. The record lists each changed document with `base` = its
/// `heads`, `target` empty, `ranges` = the claim anchors of its range
/// overrides that changed the base's text, and `whole` set when a
/// whole-document or workspace-local override or a whiteout changed it
/// (decision 108).
///
/// Each conflicting override, and a conflicting whiteout, is one
/// [`Conflict`]. Its `span` is the override's range at the target heads, or
/// for a whole-document override or a whiteout the whole target text;
/// `Collapsed { at }` when that range is empty (`at` its place at the
/// target heads: an anchor-lost override's gap, moved past the splices
/// before it), or `Collapsed { at: 0 }` when the target holds no text. A
/// document's conflicts, ordered by span (ranges by start and end, then
/// collapsed ones by `at`) and then subject, share one thread: anchored on
/// its address, `to` the union of their authors, opened by
/// `request.origin` with an `Ask` from `inputs.merger` listing each
/// conflict. Its id is `ThreadOpen::id`, and the bundle id is lvcs-doc's
/// `BundleId::of` over the four [`BundleInputs`], the one implementation,
/// which the registry checks a merge record's id with (decision 112).
#[must_use]
pub fn plan(input: MergeInput) -> MergePlan {
planner::plan(input)
}