Building Lit: A Journey Through Distributed Systems

class LitObject(ABC):
    """Base class for all Lit objects."""
    
    def compute_hash(self) -> str:
        """
        Objects are hashed with a header: <type> <size>\0<content>
        The same content always produces the same hash.
        """
        data = self.serialize()
        header = f"{self.type} {len(data)}\0".encode()
        self._hash = hashlib.sha1(header + data).hexdigest()
        return self._hash

class Blob(LitObject):
    """Raw file content, no metadata."""
    
    def __init__(self, data: bytes = None):
        self.data = data or b''

class Tree(LitObject):
    """Directory structure: list of (mode, name, hash) entries."""
    
    def __init__(self):
        self.entries: List[TreeEntry] = []

class Commit(LitObject):
    """Snapshot in time with parent links."""
    
    def __init__(self):
        self.tree: str = ''           # Root tree hash
        self.parents: List[str] = []  # Parent commit hashes
        self.message: str = ''
        self.author_time: int = 0     # Timestamp

class Commit(LitObject):
    def __init__(self):
        self.parents: List[str] = []  # Links to parent commits

        A ← B ← C ← D ← G (main, merge commit)
             \         ↗
              E ← F ──┘ (feature)

def find_merge_base(self, commit1: str, commit2: str) -> Optional[str]:
    """
    Find the best common ancestor using BFS.
    This is the merge base, essential for three-way merge.
    """
    if commit1 == commit2:
        return commit1
    
    ancestors1 = self._get_all_ancestors(commit1)
    ancestors2 = self._get_all_ancestors(commit2)
    
    common = ancestors1 & ancestors2
    
    if not common:
        return None  # Unrelated histories
    
    # Find the closest common ancestor
    return self._find_closest(commit1, commit2, common)

def clone(self, source_url: str, dest_path: str) -> Repository:
    """
    Clone creates a complete, independent replica.
    No coordination with source required after clone completes.
    """
    # Copy ALL objects: complete history
    for obj_file in source_objects.rglob('*'):
        copy_object(obj_file, dest_repo)
    
    # Copy refs as remote-tracking branches
    for branch in source_branches:
        # refs/heads/main → refs/remotes/origin/main
        create_remote_tracking_ref(branch, dest_repo)
    
    # Set up remote for future sync
    dest_repo.add_remote('origin', source_url)

def fetch(self, remote: str = 'origin'):
    """
    Download new objects WITHOUT modifying local branches.
    Updates refs/remotes/<remote>/* only.
    """
    url = self.get_remote_url(remote)
    
    # Transfer only missing objects
    for obj_hash in get_remote_objects(url):
        if not self.repo.object_exists(obj_hash):
            download_and_store(obj_hash)
    
    # Update remote-tracking refs
    for branch, commit in get_remote_refs(url):
        self.update_ref(f'refs/remotes/{remote}/{branch}', commit)

def push(self, remote: str, branch: str):
    """
    Upload commits to remote.
    Fails if it would lose commits (non-fast-forward).
    """
    local_hash = self.get_branch_hash(branch)
    remote_hash = self.get_remote_branch_hash(remote, branch)
    
    # Safety check: ensure we're not losing history
    if remote_hash and not self.is_ancestor(remote_hash, local_hash):
        raise Exception(
            "Non-fast-forward push rejected. "
            "Pull and merge first."
        )
    
    # Transfer missing objects
    missing = self.find_missing_objects(local_hash, remote_hash)
    for obj_hash in missing:
        upload_object(obj_hash)
    
    # Update remote ref
    update_remote_ref(remote, branch, local_hash)

def merge(self, branch_name: str) -> MergeResult:
    """
    Merge is the consistency mechanism.
    After merge, both branches reflect all changes.
    """
    theirs = self.resolve_ref(branch_name)
    ours = self.repo.refs.resolve_head()
    base = self.find_merge_base(ours, theirs)
    
    # If we're already up-to-date
    if base == theirs:
        return MergeResult(message="Already up to date")
    
    # Fast-forward if possible
    if base == ours:
        return self.fast_forward(theirs)
    
    # Three-way merge required
    return self.three_way_merge(base, ours, theirs)

def three_way_merge_file(self, base: bytes, ours: bytes, theirs: bytes) -> Tuple[bytes, bool]:
    """
    Merge a single file using three-way merge.
    Returns (merged_content, had_conflicts).
    """
    # Case 1: Same in both, no conflict
    if ours == theirs:
        return ours, False
    
    # Case 2: Only we changed it
    if base == theirs:
        return ours, False
    
    # Case 3: Only they changed it
    if base == ours:
        return theirs, False
    
    # Case 4: Both changed, need line-by-line merge
    return self._merge_lines(base, ours, theirs)

def _merge_lines(self, base: bytes, ours: bytes, theirs: bytes) -> Tuple[bytes, bool]:
    """Line-by-line merge with conflict detection."""
    
    base_lines = base.decode().splitlines(keepends=True)
    ours_lines = ours.decode().splitlines(keepends=True)
    theirs_lines = theirs.decode().splitlines(keepends=True)
    
    result = []
    has_conflicts = False
    
    for base_line, our_line, their_line in align_lines(base_lines, ours_lines, theirs_lines):
        if our_line == their_line:
            result.append(our_line)
        elif base_line == their_line:
            result.append(our_line)  # We changed it
        elif base_line == our_line:
            result.append(their_line)  # They changed it
        else:
            # Both changed differently: CONFLICT
            has_conflicts = True
            result.extend([
                "<<<<<<< HEAD\n",
                our_line,
                "=======\n",
                their_line,
                ">>>>>>> theirs\n"
            ])
    
    return ''.join(result).encode(), has_conflicts

# If DevA and DevB both merge the same branches...
devA: merge(feature, main)  # → produces commit X
devB: merge(feature, main)  # → produces commit X'

# X and X' will have:
# Same tree (same file contents)
# Same parents (same history links)
# Different hashes (different timestamps/authors)

# Commutativity demonstration:
merge(A, B)  # Same content as...
merge(B, A)  # this (different commit hash, same tree)

# Idempotency demonstration:
merge(feature)
merge(feature)  # Second merge is a no-op

class StashManager:
    def push(self, message: str = None) -> StashEntry:
        """Save working directory and index state."""
        
        # Capture current state as trees
        index_tree = self._build_tree_from_index()
        work_tree = self._build_tree_from_working_dir()
        
        entry = StashEntry(
            message=message or f"WIP on {branch}",
            branch=self.get_current_branch(),
            commit=self.repo.refs.resolve_head(),
            index_tree=index_tree,
            work_tree=work_tree,
            timestamp=int(time.time())
        )
        
        # Save to stash stack
        self._push_to_stack(entry)
        
        # Reset working directory
        self._reset_to_head()
        
        return entry

def rebase(self, upstream: str):
    """Replay commits on a new base."""
    
    onto = self.resolve_ref(upstream)
    head = self.repo.refs.resolve_head()
    base = self.find_merge_base(onto, head)
    
    # Get commits to replay (base..HEAD)
    commits = self.get_commits_between(base, head)
    
    # Move HEAD to the new base
    self.reset_hard(onto)
    
    # Replay each commit
    for commit_hash in commits:
        original = self.repo.read_object(commit_hash)
        
        # Apply changes from this commit
        changes = self.get_commit_changes(commit_hash)
        self.apply_changes(changes)
        
        # Create new commit with same message
        new_hash = self.create_commit(
            message=original.message,
            author=original.author
        )

        A ← B ← C (main)
             \
              D ← E (feature)

        A ← B ← C (main)
                 \
                  D' ← E' (feature)

┌─────────────────────────────────────────────────────────────┐
│                        CLI Layer                             │
│    init │ add │ commit │ branch │ merge │ fetch │ push      │
└────────────────────────────┬────────────────────────────────┘
                             │
┌────────────────────────────▼────────────────────────────────┐
│                    Operations Layer                          │
│        DiffEngine │ MergeEngine │ StashManager               │
└────────────────────────────┬────────────────────────────────┘
                             │
┌────────────────────────────▼────────────────────────────────┐
│                       Core Layer                             │
│    Repository │ Objects │ Index │ Refs │ RemoteManager      │
└────────────────────────────┬────────────────────────────────┘
                             │
┌────────────────────────────▼────────────────────────────────┐
│                     Storage Layer                            │
│              .lit/ directory (filesystem)                    │
└─────────────────────────────────────────────────────────────┘

.lit/
├── objects/           # Content-addressable object database
│   ├── ab/           # Sharded by first 2 hex chars
│   │   └── cdef...   # Compressed object data
│   └── ...
├── refs/
│   ├── heads/        # Local branches
│   │   └── main      # → commit hash
│   ├── tags/         # Tags
│   └── remotes/      # Remote-tracking branches
│       └── origin/
│           └── main
├── HEAD              # Current branch reference
├── index             # Staging area (binary format)
└── config            # Repository configuration