Merge Algorithm

Horizon Epoch uses a three-way merge algorithm similar to Git, extended for structured data with field-level conflict detection.

Overview

Three-way merge compares:

Base - The common ancestor (merge base)
Ours - The target branch (where we’re merging into)
Theirs - The source branch (what we’re merging)

Visual Overview

                    ┌─────────────────────────────────────────────────────────┐
                    │                  THREE-WAY MERGE                         │
                    └─────────────────────────────────────────────────────────┘

    Source Branch                      Target Branch
    (feature)                          (main)
         │                                  │
         ▼                                  ▼
    ┌─────────┐                        ┌─────────┐
    │Commit E │                        │Commit G │
    │ users:  │                        │ users:  │
    │ Alice→  │                        │ Alice→  │
    │ Smith   │                        │ alice@  │
    └────┬────┘                        │ company │
         │                             └────┬────┘
         │                                  │
         │      ┌──────────────────┐        │
         └──────►    MERGE BASE    ◄────────┘
                │    Commit B      │
                │    users:        │
                │    Alice         │
                │    alice@example │
                └────────┬─────────┘
                         │
                         ▼
                ┌────────────────────┐
                │  MERGE RESULT      │
                │  users:            │
                │  Alice Smith       │  ← from source (name changed)
                │  alice@company.com │  ← from target (email changed)
                └────────────────────┘

Finding the Merge Base

Commit Graph

        C---D---E  (feature)
       /
  A---B---F---G    (main)

The merge base for merging feature into main is commit B - the most recent common ancestor.

Algorithm

def find_merge_base(source_commit, target_commit):
    """Find the lowest common ancestor in the commit DAG."""
    source_ancestors = get_all_ancestors(source_commit)

    # BFS from target to find first intersection
    queue = [target_commit]
    while queue:
        commit = queue.pop(0)
        if commit in source_ancestors:
            return commit
        queue.extend(commit.parents)

    return None  # No common ancestor (shouldn't happen)

Content Hash Optimization

Before performing record-level comparison, Horizon Epoch uses content hashes for quick diff detection:

def should_merge_table(base_version, source_version, target_version):
    """Use content hashes to skip unchanged tables."""
    base_hash = base_version.content_hash
    source_hash = source_version.content_hash
    target_hash = target_version.content_hash

    if source_hash == target_hash:
        # Both branches have identical data - no merge needed
        return MergeAction.SKIP

    if source_hash == base_hash:
        # Only target changed - keep target (fast-forward)
        return MergeAction.KEEP_TARGET

    if target_hash == base_hash:
        # Only source changed - take source
        return MergeAction.TAKE_SOURCE

    # Both changed differently - full record merge required
    return MergeAction.RECORD_LEVEL_MERGE

Three-Way Merge Process

Step 1: Compute Changes

For each table, compute:

Changes from base to ours (ours_changes)
Changes from base to theirs (theirs_changes)

def compute_changes(base_state, current_state):
    changes = {}

    for record in current_state:
        base_record = base_state.get(record.key)

        if base_record is None:
            changes[record.key] = Change(type=INSERT, record=record)
        elif base_record != record:
            changes[record.key] = Change(type=UPDATE,
                                         base=base_record,
                                         current=record)

    for key in base_state:
        if key not in current_state:
            changes[key] = Change(type=DELETE, base=base_state[key])

    return changes

Step 2: Classify Changes

For each changed record:

Ours	Theirs	Result
No change	Changed	Accept theirs
Changed	No change	Keep ours
Same change	Same change	Keep either (identical)
Different changes	Different changes	CONFLICT
Deleted	Changed	CONFLICT
Changed	Deleted	CONFLICT
Deleted	Deleted	Keep deleted

Step 3: Apply Non-Conflicting Changes

def apply_changes(base, ours_changes, theirs_changes):
    result = base.copy()
    conflicts = []

    for key in set(ours_changes.keys()) | set(theirs_changes.keys()):
        ours = ours_changes.get(key)
        theirs = theirs_changes.get(key)

        if ours is None:
            # Only theirs changed
            result.apply(theirs)
        elif theirs is None:
            # Only ours changed - already in result
            pass
        elif ours == theirs:
            # Same change - already in result
            pass
        else:
            # Potential conflict - check field level
            conflict = check_field_conflict(key, ours, theirs)
            if conflict:
                conflicts.append(conflict)
            else:
                result.apply(merge_changes(ours, theirs))

    return result, conflicts

Field-Level Conflict Detection

Unlike file-based version control, Horizon Epoch detects conflicts at the field level. This is one of the most powerful features - it allows more changes to merge automatically.

How Field-Level Merge Works

┌─────────────────────────────────────────────────────────────────────────────┐
│                    FIELD-LEVEL MERGE ALGORITHM                               │
└─────────────────────────────────────────────────────────────────────────────┘

For each field in a record where both branches made changes:

┌──────────────────┬──────────────────┬──────────────────┬────────────────────┐
│   Ancestor (A)   │   Source (S)     │   Target (T)     │   Result           │
├──────────────────┼──────────────────┼──────────────────┼────────────────────┤
│   value_a        │   value_a        │   value_a        │   value_a (same)   │
│   value_a        │   value_s        │   value_a        │   value_s (source) │
│   value_a        │   value_a        │   value_t        │   value_t (target) │
│   value_a        │   value_s        │   value_s        │   value_s (same)   │
│   value_a        │   value_s        │   value_t        │   ⚠️ CONFLICT      │
│   NULL           │   value_s        │   NULL           │   value_s (added)  │
│   NULL           │   NULL           │   value_t        │   value_t (added)  │
│   NULL           │   value_s        │   value_t        │   ⚠️ CONFLICT      │
│   value_a        │   NULL           │   value_a        │   NULL (deleted)   │
│   value_a        │   value_a        │   NULL           │   NULL (deleted)   │
│   value_a        │   NULL           │   value_t        │   ⚠️ CONFLICT      │
└──────────────────┴──────────────────┴──────────────────┴────────────────────┘

Implementation

def field_level_merge(ancestor, source, target, strategy):
    """
    Merge two records field-by-field using three-way merge.
    Returns merged record or conflict information.
    """
    result = {}
    conflicting_fields = []

    # Get all fields across all three versions
    all_fields = set(ancestor.keys()) | set(source.keys()) | set(target.keys())

    for field in all_fields:
        ancestor_val = ancestor.get(field)
        source_val = source.get(field)
        target_val = target.get(field)

        # Case 1: Same in both source and target → no conflict
        if source_val == target_val:
            result[field] = source_val
            continue

        # Case 2: Only source changed from ancestor
        if ancestor_val == target_val and ancestor_val != source_val:
            result[field] = source_val
            continue

        # Case 3: Only target changed from ancestor
        if ancestor_val == source_val and ancestor_val != target_val:
            result[field] = target_val
            continue

        # Case 4: Field added in source only
        if ancestor_val is None and target_val is None and source_val is not None:
            result[field] = source_val
            continue

        # Case 5: Field added in target only
        if ancestor_val is None and source_val is None and target_val is not None:
            result[field] = target_val
            continue

        # Case 6: CONFLICT - both changed differently
        conflicting_fields.append(FieldConflict(
            field_name=field,
            ancestor_value=ancestor_val,
            source_value=source_val,
            target_value=target_val
        ))

    if conflicting_fields:
        return MergeRecordResult.Conflict(
            merged_fields=result,
            conflicting_fields=conflicting_fields
        )

    return MergeRecordResult.Resolved(result)

Example: Successful Auto-Merge

Base record:

{"id": 1, "name": "Alice", "email": "alice@example.com", "status": "active"}

Ours (main):

{"id": 1, "name": "Alice", "email": "alice@company.com", "status": "active"}

Theirs (feature):

{"id": 1, "name": "Alice Smith", "email": "alice@example.com", "status": "inactive"}

Field-by-Field Analysis

┌─────────┬───────────────┬───────────────┬───────────────┬────────────────────┐
│ Field   │ Base          │ Ours (main)   │ Theirs (feat) │ Result             │
├─────────┼───────────────┼───────────────┼───────────────┼────────────────────┤
│ id      │ 1             │ 1             │ 1             │ 1 (unchanged)      │
│ name    │ Alice         │ Alice         │ Alice Smith   │ Alice Smith ✓      │
│         │               │ (unchanged)   │ (changed)     │ (take theirs)      │
│ email   │ alice@example │ alice@company │ alice@example │ alice@company ✓    │
│         │               │ (changed)     │ (unchanged)   │ (keep ours)        │
│ status  │ active        │ active        │ inactive      │ inactive ✓         │
│         │               │ (unchanged)   │ (changed)     │ (take theirs)      │
└─────────┴───────────────┴───────────────┴───────────────┴────────────────────┘

Result (auto-merged):

{"id": 1, "name": "Alice Smith", "email": "alice@company.com", "status": "inactive"}

Example: Field-Level Conflict

If both branches changed the same field to different values:

┌─────────┬───────────────┬────────────────────┬────────────────────┬──────────┐
│ Field   │ Base          │ Ours (main)        │ Theirs (feature)   │ Result   │
├─────────┼───────────────┼────────────────────┼────────────────────┼──────────┤
│ email   │ alice@example │ alice@company.com  │ a.smith@example    │ CONFLICT │
│         │               │ (changed)          │ (changed)          │ ⚠️       │
└─────────┴───────────────┴────────────────────┴────────────────────┴──────────┘

Conflict Types

Horizon Epoch distinguishes several conflict types:

#![allow(unused)]
fn main() {
pub enum RecordConflictType {
    /// Both sides modified the same record differently
    ModifyModify,

    /// Source deleted, target modified
    DeleteModify,

    /// Source modified, target deleted
    ModifyDelete,

    /// Both sides added a record with the same primary key
    AddAdd,

    /// Other edge cases
    Other,
}
}

Each type may require different resolution strategies.

Merge Strategies

Horizon Epoch supports four merge strategies, each suited for different workflows:

┌─────────────────────────────────────────────────────────────────────────────┐
│                         MERGE STRATEGIES                                     │
└─────────────────────────────────────────────────────────────────────────────┘

┌─────────────────┬────────────────────────────────────────────────────────────┐
│ Strategy        │ Behavior                                                    │
├─────────────────┼────────────────────────────────────────────────────────────┤
│ ThreeWay        │ Standard 3-way merge, reports conflicts for resolution     │
│ (default)       │ Use when: You want to review and manually resolve conflicts│
├─────────────────┼────────────────────────────────────────────────────────────┤
│ AcceptSource    │ Auto-resolve conflicts by taking source branch values      │
│ (--strategy     │ Use when: Source branch should "win" (e.g., hotfixes)      │
│  theirs)        │                                                            │
├─────────────────┼────────────────────────────────────────────────────────────┤
│ AcceptTarget    │ Auto-resolve conflicts by keeping target branch values     │
│ (--strategy     │ Use when: Target branch should "win" (preserve main)       │
│  ours)          │                                                            │
├─────────────────┼────────────────────────────────────────────────────────────┤
│ FailOnConflict  │ Abort immediately if any conflict is detected              │
│ (--fail-on-     │ Use when: CI/CD pipelines, automated processes             │
│  conflict)      │                                                            │
└─────────────────┴────────────────────────────────────────────────────────────┘

Default Strategy (ThreeWay)

Field-level three-way merge with conflict detection. Non-conflicting changes merge automatically; conflicts are reported for manual resolution.

epoch merge feature/branch

Accept Source (Theirs) Strategy

On conflicts, automatically choose the source branch (the branch being merged in):

epoch merge feature/branch --strategy theirs

Use cases:

Hotfix branches that must override any conflicting changes
Feature branches developed by domain experts
Emergency deployments

Accept Target (Ours) Strategy

On conflicts, automatically keep the target branch values (the branch you’re merging into):

epoch merge feature/branch --strategy ours

Use cases:

Integrating experimental branches where existing data should be preserved
Rebasing feature branches onto main
Pulling updates while preserving local modifications

Fail on Conflict Strategy

Fail immediately if any conflict is detected. Useful for automated pipelines.

epoch merge feature/branch --fail-on-conflict

Use cases:

CI/CD pipelines where conflicts indicate process failures
Automated data sync jobs
Pre-merge validation checks

Strategy Comparison

Scenario	ThreeWay	AcceptSource	AcceptTarget	FailOnConflict
Non-conflicting changes	✓ Merge	✓ Merge	✓ Merge	✓ Merge
Same field, different values	⚠️ Report	Take source	Keep target	❌ Abort
Delete vs modify	⚠️ Report	Delete	Keep modified	❌ Abort
Both add same key	⚠️ Report	Take source	Keep target	❌ Abort

Conflict Resolution

Interactive Resolution

epoch conflicts resolve --interactive

Walks through each conflict:

Conflict in users.email (record id=1):
  BASE:   alice@example.com
  OURS:   alice@company.com
  THEIRS: alice.smith@example.com

Choose:
  [o] Keep ours
  [t] Keep theirs
  [b] Keep base
  [c] Custom value
>

Programmatic Resolution

conflicts = client.get_conflicts()

for conflict in conflicts:
    for field in conflict.fields:
        # Custom resolution logic
        if field.name == "email":
            # Business rule: prefer company domain
            if "@company.com" in field.ours_value:
                resolution = field.ours_value
            else:
                resolution = field.theirs_value

            client.resolve_conflict(
                table=conflict.table_name,
                record_id=conflict.record_id,
                field=field.name,
                value=resolution
            )

client.merge_continue()

Schema Merge

Schema changes are also merged:

Compatible Changes

These merge automatically:

Adding a column (either branch)
Adding an index
Changing a default value (non-conflicting)

Conflicting Changes

These require resolution:

Same column changed to different types
Same column renamed differently
Conflicting constraints

Schema conflict in users:
  Column 'status':
    OURS:   VARCHAR(20)
    THEIRS: INTEGER

Choose resolution:
  [o] Keep VARCHAR(20)
  [t] Change to INTEGER
  [c] Custom type
>

Merge Commits

After successful merge, a merge commit is created:

Commit: ghi789
Parents: abc123 (main), def456 (feature)
Message: Merge feature/branch into main

Changes:
  users: 5 records merged, 2 conflicts resolved

Performance

Complexity

Finding merge base: O(commit history depth)
Computing changes: O(changed records)
Conflict detection: O(changed records)

Optimization

Change tracking - Only examine records marked as changed
Parallel comparison - Compare multiple tables concurrently
Early termination - Stop at first conflict if not auto-resolving

Best Practices

Merge frequently - Smaller merges have fewer conflicts
Keep branches focused - One feature per branch reduces conflicts
Communicate on shared data - Coordinate changes to same records
Test after merge - Verify data integrity post-merge
Document conflict resolution - Include context in merge commit

Keyboard shortcuts

Horizon Epoch Documentation