Project 4: Three-Way Merge Engine — Implement Git’s Core Merge Algorithm

A three-way merge tool that takes a base version, “ours” version, and “theirs” version of a file and produces either a merged result or conflict markers—exactly like Git does.

Quick Reference

Attribute Value
Difficulty Expert
Time Estimate 2-4 weeks
Main Programming Language C
Alternative Programming Languages Rust, Go, Python
Coolness Level Level 4: Hardcore Tech Flex
Business Potential 1. The “Resume Gold”
Prerequisites Projects 1-3 completed, dynamic programming, understanding of diff
Key Topics Longest Common Subsequence (LCS), The Diff Algorithm, Three-Way Merge Logic

1. Learning Objectives

By completing this project, you will:

  1. Implement a working version of: A three-way merge tool that takes a base version, “ours” version, and “theirs” version of a file and produces either a merged result or conflict markers—exactly like Git does..
  2. Explain the core Git workflow tradeoff this project is designed to surface.
  3. Design deterministic checks so results can be verified and reproduced.
  4. Document operational failure modes and safe recovery actions.

2. All Theory Needed (Per-Concept Breakdown)

Longest Common Subsequence (LCS)

Fundamentals This concept matters in this project because your implementation will fail or become non-deterministic without a precise model of Longest Common Subsequence (LCS). You should define what the concept controls, what invariants must hold, and which actions are safe versus destructive. Treat this concept as a production concern, not a tutorial checkbox.

Deep Dive into the concept When applying Longest Common Subsequence (LCS) in this project, reason in three passes: data shape, state transitions, and enforcement. First, identify which artifacts are authoritative (commit objects, refs, metadata, policy config, CI status, or scan findings). Second, map how those artifacts change when your tool runs. Third, define failure behavior explicitly. In Git tooling, silent partial success is dangerous: you need either complete success with evidence or an explicit failure state with remediation guidance. Also account for scale behavior. A workflow that works on a toy repo may fail on large history depth, concurrent updates, or mixed branch policies. Include trace logs for every irreversible action, and separate simulation mode from write mode. For interview readiness, be able to explain how this concept protects delivery speed while reducing operational risk.

How this fit on projects In this project, Longest Common Subsequence (LCS) is directly used in design decisions, implementation constraints, and verification criteria.

Definitions & key terms

  • Longest Common Subsequence (LCS) invariant: A condition that must remain true before and after every operation.
  • Safety boundary: The point where actions become destructive unless guarded.
  • Verification signal: Evidence proving the action behaved as expected.

Mental model diagram

Input state -> Validate invariant -> Apply change -> Verify output -> Record evidence

How it works

  1. Capture current state and constraints.
  2. Evaluate whether Longest Common Subsequence (LCS) preconditions are satisfied.
  3. Execute the minimal safe transition.
  4. Verify postconditions and publish an auditable result.

Failure modes: stale state, partial writes, race conditions, ambiguous output contracts.

Minimal concrete example

Plan -> dry-run -> execute -> verify -> rollback/forward-fix decision

Common misconceptions

  • Assuming local success implies team-safe behavior.
  • Treating policy violations as warnings instead of merge blockers.
  • Skipping deterministic verification because the output appears correct.

Check-your-understanding questions

  1. Which invariant is most likely to break first under concurrency?
  2. What output proves your tool handled an edge case correctly?
  3. Where should enforcement happen: local hook, CI, or protected branch gate?

Check-your-understanding answers

  1. The invariant tied to mutable refs or policy-dependent merge eligibility.
  2. A deterministic transcript showing both success and controlled failure behavior.
  3. Layered enforcement: fast local checks plus non-bypassable server-side gates.

Real-world applications

  • Change-management tooling for fast-moving teams.
  • Incident-safe release workflows with traceable rollback paths.
  • Compliance-ready source-control automation.

Where you’ll apply it This project and its immediate adjacent projects in this sprint.

References

  • https://git-scm.com/docs
  • https://dora.dev/capabilities/trunk-based-development/

Key insights Longest Common Subsequence (LCS) is only valuable when its invariants are encoded into tooling and checks.

Summary Mastering Longest Common Subsequence (LCS) here gives you transferable patterns for larger workflow systems.

Homework/Exercises to practice the concept

  1. Write one failing scenario and expected detection output.
  2. Define one invariant and one explicit violation test.

Solutions to the homework/exercises

  1. Use a stale branch or invalid metadata case and assert deterministic error reporting.
  2. Invariant: protected branch must not accept unchecked changes; violation test: bypass attempt should fail fast.

The Diff Algorithm

Fundamentals This concept matters in this project because your implementation will fail or become non-deterministic without a precise model of The Diff Algorithm. You should define what the concept controls, what invariants must hold, and which actions are safe versus destructive. Treat this concept as a production concern, not a tutorial checkbox.

Deep Dive into the concept When applying The Diff Algorithm in this project, reason in three passes: data shape, state transitions, and enforcement. First, identify which artifacts are authoritative (commit objects, refs, metadata, policy config, CI status, or scan findings). Second, map how those artifacts change when your tool runs. Third, define failure behavior explicitly. In Git tooling, silent partial success is dangerous: you need either complete success with evidence or an explicit failure state with remediation guidance. Also account for scale behavior. A workflow that works on a toy repo may fail on large history depth, concurrent updates, or mixed branch policies. Include trace logs for every irreversible action, and separate simulation mode from write mode. For interview readiness, be able to explain how this concept protects delivery speed while reducing operational risk.

How this fit on projects In this project, The Diff Algorithm is directly used in design decisions, implementation constraints, and verification criteria.

Definitions & key terms

  • The Diff Algorithm invariant: A condition that must remain true before and after every operation.
  • Safety boundary: The point where actions become destructive unless guarded.
  • Verification signal: Evidence proving the action behaved as expected.

Mental model diagram

Input state -> Validate invariant -> Apply change -> Verify output -> Record evidence

How it works

  1. Capture current state and constraints.
  2. Evaluate whether The Diff Algorithm preconditions are satisfied.
  3. Execute the minimal safe transition.
  4. Verify postconditions and publish an auditable result.

Failure modes: stale state, partial writes, race conditions, ambiguous output contracts.

Minimal concrete example

Plan -> dry-run -> execute -> verify -> rollback/forward-fix decision

Common misconceptions

  • Assuming local success implies team-safe behavior.
  • Treating policy violations as warnings instead of merge blockers.
  • Skipping deterministic verification because the output appears correct.

Check-your-understanding questions

  1. Which invariant is most likely to break first under concurrency?
  2. What output proves your tool handled an edge case correctly?
  3. Where should enforcement happen: local hook, CI, or protected branch gate?

Check-your-understanding answers

  1. The invariant tied to mutable refs or policy-dependent merge eligibility.
  2. A deterministic transcript showing both success and controlled failure behavior.
  3. Layered enforcement: fast local checks plus non-bypassable server-side gates.

Real-world applications

  • Change-management tooling for fast-moving teams.
  • Incident-safe release workflows with traceable rollback paths.
  • Compliance-ready source-control automation.

Where you’ll apply it This project and its immediate adjacent projects in this sprint.

References

  • https://git-scm.com/docs
  • https://dora.dev/capabilities/trunk-based-development/

Key insights The Diff Algorithm is only valuable when its invariants are encoded into tooling and checks.

Summary Mastering The Diff Algorithm here gives you transferable patterns for larger workflow systems.

Homework/Exercises to practice the concept

  1. Write one failing scenario and expected detection output.
  2. Define one invariant and one explicit violation test.

Solutions to the homework/exercises

  1. Use a stale branch or invalid metadata case and assert deterministic error reporting.
  2. Invariant: protected branch must not accept unchecked changes; violation test: bypass attempt should fail fast.

Three-Way Merge Logic

Fundamentals This concept matters in this project because your implementation will fail or become non-deterministic without a precise model of Three-Way Merge Logic. You should define what the concept controls, what invariants must hold, and which actions are safe versus destructive. Treat this concept as a production concern, not a tutorial checkbox.

Deep Dive into the concept When applying Three-Way Merge Logic in this project, reason in three passes: data shape, state transitions, and enforcement. First, identify which artifacts are authoritative (commit objects, refs, metadata, policy config, CI status, or scan findings). Second, map how those artifacts change when your tool runs. Third, define failure behavior explicitly. In Git tooling, silent partial success is dangerous: you need either complete success with evidence or an explicit failure state with remediation guidance. Also account for scale behavior. A workflow that works on a toy repo may fail on large history depth, concurrent updates, or mixed branch policies. Include trace logs for every irreversible action, and separate simulation mode from write mode. For interview readiness, be able to explain how this concept protects delivery speed while reducing operational risk.

How this fit on projects In this project, Three-Way Merge Logic is directly used in design decisions, implementation constraints, and verification criteria.

Definitions & key terms

  • Three-Way Merge Logic invariant: A condition that must remain true before and after every operation.
  • Safety boundary: The point where actions become destructive unless guarded.
  • Verification signal: Evidence proving the action behaved as expected.

Mental model diagram

Input state -> Validate invariant -> Apply change -> Verify output -> Record evidence

How it works

  1. Capture current state and constraints.
  2. Evaluate whether Three-Way Merge Logic preconditions are satisfied.
  3. Execute the minimal safe transition.
  4. Verify postconditions and publish an auditable result.

Failure modes: stale state, partial writes, race conditions, ambiguous output contracts.

Minimal concrete example

Plan -> dry-run -> execute -> verify -> rollback/forward-fix decision

Common misconceptions

  • Assuming local success implies team-safe behavior.
  • Treating policy violations as warnings instead of merge blockers.
  • Skipping deterministic verification because the output appears correct.

Check-your-understanding questions

  1. Which invariant is most likely to break first under concurrency?
  2. What output proves your tool handled an edge case correctly?
  3. Where should enforcement happen: local hook, CI, or protected branch gate?

Check-your-understanding answers

  1. The invariant tied to mutable refs or policy-dependent merge eligibility.
  2. A deterministic transcript showing both success and controlled failure behavior.
  3. Layered enforcement: fast local checks plus non-bypassable server-side gates.

Real-world applications

  • Change-management tooling for fast-moving teams.
  • Incident-safe release workflows with traceable rollback paths.
  • Compliance-ready source-control automation.

Where you’ll apply it This project and its immediate adjacent projects in this sprint.

References

  • https://git-scm.com/docs
  • https://dora.dev/capabilities/trunk-based-development/

Key insights Three-Way Merge Logic is only valuable when its invariants are encoded into tooling and checks.

Summary Mastering Three-Way Merge Logic here gives you transferable patterns for larger workflow systems.

Homework/Exercises to practice the concept

  1. Write one failing scenario and expected detection output.
  2. Define one invariant and one explicit violation test.

Solutions to the homework/exercises

  1. Use a stale branch or invalid metadata case and assert deterministic error reporting.
  2. Invariant: protected branch must not accept unchecked changes; violation test: bypass attempt should fail fast.

3. Project Specification

3.1 What You Will Build

A three-way merge tool that takes a base version, “ours” version, and “theirs” version of a file and produces either a merged result or conflict markers—exactly like Git does.

3.2 Functional Requirements

  1. Scope control: Deliver a deterministic and testable implementation.
  2. Correctness: Preserve Git invariants and policy constraints.

3.3 Non-Functional Requirements

  • Performance: Deterministic execution with documented runtime behavior on representative history sizes.
  • Reliability: Repeated runs on the same input produce identical outputs.
  • Usability: Clear CLI or report output for both success and failure cases.

3.4 Example Usage / Output

You’ll have a merge tool that can combine file versions exactly like Git:

Example Output:

$ ./merge3 base.txt ours.txt theirs.txt

=== Three-Way Merge ===

Base version:
1: Hello World
2: This is a test
3: Goodbye

Ours version (changes on our branch):
1: Hello World
2: This is a test
3: This is our change
4: Goodbye

Theirs version (changes on their branch):
1: Hello World
2: Their modification here
3: This is a test
4: Goodbye

=== Diff Analysis ===
Line 2: THEIRS modified (base→theirs differs, base=ours)
Line 3: OURS added (ours has extra line)

=== Merge Result (no conflicts!) ===
1: Hello World
2: Their modification here
3: This is a test
4: This is our change
5: Goodbye

$ ./merge3 base.txt ours.txt theirs.txt --conflict-case

=== CONFLICT DETECTED ===

Both modified line 2:
  Base:   "This is a test"
  Ours:   "Our version of line 2"
  Theirs: "Their version of line 2"

Merged output with conflict markers:
1: Hello World
<<<<<<< OURS
2: Our version of line 2
=======
2: Their version of line 2
>>>>>>> THEIRS
3: Goodbye

3.5 Data Formats / Schemas / Protocols

Describe input repository assumptions, output report shape, and any policy/config schema consumed by the tool.

3.6 Edge Cases

  • Empty repository or shallow clone state.
  • Detached HEAD or rewritten history during execution.
  • Invalid metadata/policy configuration.

3.7 Real World Outcome

You’ll have a merge tool that can combine file versions exactly like Git:

Example Output:

$ ./merge3 base.txt ours.txt theirs.txt

=== Three-Way Merge ===

Base version:
1: Hello World
2: This is a test
3: Goodbye

Ours version (changes on our branch):
1: Hello World
2: This is a test
3: This is our change
4: Goodbye

Theirs version (changes on their branch):
1: Hello World
2: Their modification here
3: This is a test
4: Goodbye

=== Diff Analysis ===
Line 2: THEIRS modified (base→theirs differs, base=ours)
Line 3: OURS added (ours has extra line)

=== Merge Result (no conflicts!) ===
1: Hello World
2: Their modification here
3: This is a test
4: This is our change
5: Goodbye

$ ./merge3 base.txt ours.txt theirs.txt --conflict-case

=== CONFLICT DETECTED ===

Both modified line 2:
  Base:   "This is a test"
  Ours:   "Our version of line 2"
  Theirs: "Their version of line 2"

Merged output with conflict markers:
1: Hello World
<<<<<<< OURS
2: Our version of line 2
=======
2: Their version of line 2
>>>>>>> THEIRS
3: Goodbye

4. Solution Architecture

4.1 High-Level Design

Inputs -> Validation -> Core Engine -> Output Formatter -> Verification Report

4.2 Key Components

Component Responsibility Key Decisions
Input loader Discover commits/refs/config inputs Deterministic ordering and clear failure messages
Core engine Compute project-specific logic Separate read-only simulation from mutating actions
Reporter Produce user-facing output and evidence Include machine-readable and human-readable forms

4.4 Data Structures (No Full Code)

ProjectState { refs, commits, policy, findings, metrics }
Result { status, evidence, warnings, next_actions }

4.4 Algorithm Overview

  1. Collect state from repository and configuration.
  2. Evaluate invariants and policy preconditions.
  3. Execute core transformation or analysis logic.
  4. Verify postconditions and emit deterministic report.

Complexity Analysis:

  • Time: O(history + affected scope)
  • Space: O(active graph window + report size)

5. Implementation Guide

5.1 Development Environment Setup

Use the environment defined in the main guide. Pin tool versions and fixture data to keep outputs reproducible.

5.2 Project Structure

project-root/
├── fixtures/
├── src/
├── tests/
├── docs/
└── README.md

5.3 The Core Question You’re Answering

“How does Git know when changes can be automatically merged and when they conflict?”

Before you write any code, sit with this question. The key insight is the BASE version—Git doesn’t just compare two files, it compares both to their common ancestor. If only one side changed a line, that change can be applied automatically.

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Longest Common Subsequence (LCS)
    • What’s the difference between LCS and longest common substring?
    • How does dynamic programming solve LCS in O(mn) time?
    • How does LCS relate to computing diffs?
    • Book Reference: “The Algorithm Design Manual” Ch. 8 — Skiena
  2. The Diff Algorithm
    • How does Myers’ diff algorithm work?
    • What’s an edit script?
    • How do you go from LCS to a list of insertions/deletions?
    • Paper: “An O(ND) Difference Algorithm — Eugene Myers
  3. Three-Way Merge Logic
    • What are the four possible states of a line (unchanged, ours-only, theirs-only, both)?
    • When is a change non-conflicting?
    • What’s the format of Git’s conflict markers?
    • Book Reference: “Pro Git” Ch. 3.2 — Chacon

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. Diff Representation
    • How will you represent a diff? As edit operations? As hunks?
    • How do you handle lines that moved (not just added/deleted)?
    • Should you diff by lines or by characters within lines?
  2. Merge Algorithm
    • How do you align the three versions?
    • What if ours and theirs made the same change?
    • What if ours deleted a line that theirs modified?
  3. Conflict Handling
    • How do you represent the conflict region?
    • Should you include context lines?
    • How do you handle nested conflicts?

5.6 Thinking Exercise

Trace a Merge Manually

Set up a conflict scenario:

git init merge-test && cd merge-test
echo -e "line1\nline2\nline3" > file.txt
git add . && git commit -m "Base"
git checkout -b feature
echo -e "line1\nfeature-line2\nline3" > file.txt
git commit -am "Feature change"
git checkout main
echo -e "line1\nmain-line2\nline3" > file.txt
git commit -am "Main change"
git merge feature  # Will conflict!
cat file.txt  # See conflict markers

Questions while tracing:

  • Draw out base, ours, theirs for line 2
  • Why did Git detect a conflict?
  • What if only one branch had changed line 2?
  • Look at .git/MERGE_HEAD — what’s stored there?

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “Explain the three-way merge algorithm. What is the ‘base’ and why is it important?”
  2. “What’s the time complexity of computing a diff between two files?”
  3. “Why might git merge succeed when manual file comparison would suggest a conflict?”
  4. “What merge strategies does Git support, and when would you use each?”
  5. “How would you resolve a merge conflict where both sides made the same change?”

5.8 Hints in Layers

Hint 1: Starting Point Implement diff first. The simplest approach: compute LCS, then derive insertions/deletions from what’s NOT in the LCS.

Hint 2: LCS Algorithm Use dynamic programming. Build a table where lcs[i][j] = length of LCS of first i lines of A and first j lines of B. Backtrack to find the actual sequence.

Hint 3: Three-Way Logic Compute diff(base, ours) and diff(base, theirs). For each line region, categorize: unchanged, ours-only, theirs-only, or conflict.

Hint 4: Conflict Markers Git’s format:

<<<<<<< HEAD
our content
=======
their content
>>>>>>> branch-name

5.9 Books That Will Help

Topic Book Chapter
LCS algorithm “The Algorithm Design Manual” by Skiena Ch. 8
Diff algorithm “An O(ND) Difference Algorithm” by Myers Paper
Merge internals “Version Control with Git” by Loeliger Ch. 9

5.10 Implementation Phases

Phase 1: Foundation (1-2 sessions)

  • Define fixtures, expected outputs, and invariant checks.
  • Build read-only analysis path.

Phase 2: Core Functionality (2-4 sessions)

  • Implement project-specific core logic and deterministic reporting.
  • Add policy and edge-case handling.

Phase 3: Polish and Edge Cases (1-2 sessions)

  • Add failure demos, performance notes, and usability improvements.
  • Finalize docs and validation transcripts.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Execution mode direct write vs dry-run+write dry-run+write Safer and easier to debug
Output contract free text vs structured+text structured+text Better automation and readability
Enforcement location local only vs local+CI local+CI Prevents bypass in shared branches

6. Testing Strategy

6.1 Test Categories

  • Unit tests for parsing and policy logic.
  • Integration tests on fixture repositories.
  • Edge-case tests for stale refs, malformed metadata, and large histories.

6.2 Critical Test Cases

  1. Deterministic golden-path scenario.
  2. Policy violation hard-fail scenario.
  3. Recovery path after partial or conflicting state.

6.3 Test Data

Use fixed repository fixtures with known commit graphs and expected outputs stored under version control.

7. Common Pitfalls & Debugging

Problem 1: “Output looks correct but history or metadata is inconsistent”

  • Why: Validation happens after mutation, not before.
  • Fix: Add a preflight invariant check and a post-write verification step.
  • Quick test: Run the same command twice on the same fixture and verify identical results.

Problem 2: “Tool works on small repo but times out on larger history”

  • Why: Full traversal is performed where selective traversal is possible.
  • Fix: Cache intermediate graph lookups and scope analysis to affected commits/paths.
  • Quick test: Compare runtime on small and large fixtures with a clear budget target.

Problem 3: “Policy check can be bypassed by local-only behavior”

  • Why: Enforcement is advisory, not server-authoritative.
  • Fix: Mirror critical checks in CI and protected branch rules.
  • Quick test: Attempt merge with failing policy in CI and confirm hard block.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add richer error messages with remediation hints.
  • Add fixture generation helpers for repeatable demos.

8.2 Intermediate Extensions

  • Add performance instrumentation and budget assertions.
  • Add policy configuration profiles by repository type.

8.3 Advanced Extensions

  • Add distributed execution support for large repositories.
  • Add signed evidence exports for compliance workflows.

9. Real-World Connections

9.1 Industry Applications

  • Internal developer portals.
  • Enterprise repository governance systems.
  • Release safety and incident diagnostics tooling.
  • Git core: https://git-scm.com/
  • GitHub CLI: https://github.com/cli/cli
  • pre-commit framework: https://pre-commit.com/

9.3 Interview Relevance

This project prepares you for architecture and debugging interviews that focus on merge policy, CI gates, and workflow reliability tradeoffs.

10. Resources

10.1 Essential Reading

  • Pro Git (Internals and Workflows chapters)
  • Software Engineering at Google (Version control and build chapters)
  • Accelerate (delivery performance practices)

10.2 Video Resources

  • Git internals talks from Git Merge conference archives.
  • DORA and delivery metrics conference sessions.

10.3 Tools and Documentation

  • https://git-scm.com/docs
  • https://docs.github.com/
  • https://dora.dev/

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain the primary invariant this project enforces.
  • I can explain one failure mode and one safe recovery path.

11.2 Implementation

  • Functional requirements are met on deterministic fixtures.
  • Critical edge cases are tested and documented.

11.3 Growth

  • I can describe tradeoffs in an interview setting.
  • I documented what I would change in a production version.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Deterministic golden-path output exists.
  • One failure scenario is handled with clear output.
  • Core workflow objective is demonstrably met.

Full Completion:

  • Minimum criteria plus policy validation, structured reporting, and edge-case coverage.

Excellence:

  • Full completion plus measurable performance budget and production-hardening notes.