Three-Way Merge

The fundamental data model requires three distinct document states: the Base (original common ancestor), Ours (local branch with first set of edits), and Theirs (remote branch with second set of edits). The engine computes two diffs—Base→Ours and Base→Theirs—and then walks both edit scripts simultaneously. A change is applied cleanly if only one branch modified a given region. The engine's core logic is to identify overlapping edits and either auto-resolve or flag them.

A conflict is declared when Ours and Theirs both modify the same logical region of the Base document. This is not merely line-based adjacency; sophisticated engines use clause-level hashing and semantic boundaries to define regions. Detection algorithms classify conflicts into types: textual (same lines changed), structural (same paragraph reordered), or semantic (same obligation altered differently). The engine must output a structured conflict marker—often using a standard like the Unified Diff Format with conflict brackets—to enable downstream resolution.

To minimize manual intervention, merge engines apply deterministic rules for non-conflicting changes. Common strategies include:

• Take-Ours/Theirs: For non-overlapping regions, apply the sole edit.
• Chronological Last-Write-Wins: Use timestamps if one edit is strictly newer.
• Whitespace Normalization: Ignore formatting-only changes to prevent spurious conflicts.
• Move Detection: Recognize when a clause was relocated in one branch and apply the move in the merge, rather than treating it as a delete+insert pair. These heuristics dramatically reduce the cognitive load on human reviewers.

Two concurrency models underpin modern merge engines. Operational Transformation (OT) transforms incoming operations against a history of applied ops to maintain consistency, suited for real-time editing. Conflict-Free Replicated Data Types (CRDTs) use mathematical structures (like RGA trees for text) that guarantee mergeability without a central server. For legal documents, CRDTs offer an advantage: the merge result is deterministic and provably correct regardless of operation order, ensuring an irrefutable audit trail of how a final contract version was synthesized.

Advanced engines transcend string comparison by performing a semantic merge. This involves converting each branch's text into vector embeddings and computing cosine similarity against the Base. If Ours and Theirs both alter the same clause but with semantically equivalent language (e.g., 'Term: 5 years' vs. 'Duration: 60 months'), the engine can auto-resolve. This requires integration with a Legal Embedding Model fine-tuned on contractual language to understand that 'Indemnify' and 'Hold Harmless' are functionally identical obligations.

The final output of a three-way merge is a patch file—a machine-readable script that, when applied to the Base, produces the merged document. This patch is often formatted as a Unified Diff or a JSON Patch (RFC 6902) for structured data. The engine must generate a patch that is minimal (no redundant operations) and idempotent (applying it twice yields the same result). This patch becomes the change provenance artifact, cryptographically signable to create a non-repudiable record of the reconciliation process.

A programmatic rule set that automatically reconciles overlapping or contradictory edits made by different parties to the same section of a document. In a three-way merge, when both branches modify the same line relative to the base ancestor, the algorithm must decide whether to accept one change, combine them, or flag for manual intervention. Common strategies include last-writer-wins, majority-vote, and semantic merge rules that parse the actual meaning of clauses rather than relying on raw text comparison.

A concurrency control algorithm that transforms editing operations to ensure eventual consistency across all replicas in a real-time collaborative document editing system. OT works by adjusting the positional parameters of insert and delete operations based on the effects of concurrently executed operations from other users. This is the foundational technology behind Google Docs and enables multiple lawyers to edit the same contract simultaneously without locking, with the system mathematically guaranteeing that all copies converge to an identical final state.

A distributed data structure designed so that concurrent, uncoordinated edits from multiple users can be merged mathematically without conflicts. Unlike Operational Transformation, CRDTs do not require a central server to coordinate transformations. Key types include:

• G-Counter: Grow-only counter for tracking edit counts
• RGA (Replicated Growable Array): For ordered text sequences
• LWW-Register: Last-writer-wins for single-value fields CRDTs power modern collaborative diff engines in tools like Notion and Figma, enabling offline editing with guaranteed mergeability.

An advanced differencing capability that identifies when a block of text has been relocated within a document, rather than treating it as a deletion in one place and an insertion in another. In a three-way merge, move detection prevents false conflicts: if Branch A moves a clause from Section 2 to Section 5, and Branch B edits that clause in its original location, a naive diff would report a delete-modify conflict. Move-aware algorithms recognize the relocation and apply Branch B's edits to the clause in its new position, preserving both changes.

An algorithm measuring the minimum-cost sequence of node insertions, deletions, and relabelings required to transform one hierarchical structure into another. Applied to legal documents, this treats the document as a tree (sections, subsections, clauses) rather than a flat text sequence. The Zhang-Shasha algorithm computes this distance in O(n⁴) time, enabling structural comparison of XML-based legal formats. This is critical for three-way merges of structured contracts where preserving the hierarchy is as important as preserving the text.

A technique that generates a unique, fixed-size cryptographic fingerprint for an individual clause to efficiently detect any modification to its content across document versions. Using algorithms like SHA-256 or locality-sensitive hashing, each clause is hashed independently. During a three-way merge, the system compares hashes from the base, Branch A, and Branch B to instantly identify which clauses are unchanged, modified, or unique to each branch. This dramatically accelerates merge performance by avoiding expensive text comparisons on unmodified content.