wsb 0.275.7622

//! Three-way convergence: what to do when two machines have both been edited.
//!
//! This is not "copy A to B". Both sides are worked on, so the only honest
//! question is what each side has done SINCE the last state they agreed on:
//!
//! ```text
//! BASE = the last state both peers acknowledged
//! A    = this side now
//! B    = the peer now
//! ```
//!
//! and then:
//!
//! ```text
//! A changed, B did not   → send A
//! B changed, A did not   → take B
//! both changed, same     → converged, just agree on the new base
//! both changed, differ   → CONFLICT
//! ```
//!
//! # What is deliberately not used
//!
//! Modification times. A file's mtime says when a filesystem was written, not
//! which edit a person meant to keep — clocks disagree, editors preserve
//! mtimes, a checkout rewrites them wholesale, and a machine that was asleep
//! comes back with everything older than the machine that was not. Deciding a
//! conflict by "newest wins" silently destroys the work of whichever machine
//! has the slower clock, and the operator never learns it happened.
//!
//! Content hashes decide what changed. The baseline decides who changed it.

use std::collections::{BTreeMap, BTreeSet};
use std::path::Path;

use serde::{Deserialize, Serialize};

/// What a path is.
///
/// A file that became a directory, or a symlink that became a file, is not a
/// modification — it is a different kind of thing at the same name, and
/// applying one over the other without noticing is how a tree gets a file
/// where a link should be.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum EntryKind {
    File,
    /// Kept as its target text, never followed. A link pointing outside the
    /// tree is a link, not a copy of whatever it points at.
    Symlink,
}

/// One path's state, as both sides describe it to each other.
///
/// Everything here is content, never location and never time: two machines
/// keep the worktree in different directories and their clocks are their own.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Entry {
    pub kind: EntryKind,
    /// SHA-256 of the file's bytes, or of the symlink's target text.
    pub hash: String,
    pub size: u64,
    /// Whether the owner-execute bit is set. The one permission bit git itself
    /// tracks, and the one whose loss breaks a checkout.
    pub executable: bool,
}

impl Entry {
    /// Read one path, or `None` when it is not there.
    ///
    /// A path that is a directory is `None` too: directories are not members
    /// of the continuity set — they exist because files inside them do — so a
    /// name that is a directory here is, for this purpose, a name with no file
    /// at it.
    pub fn read(path: &Path) -> Result<Option<Self>, String> {
        let meta = match std::fs::symlink_metadata(path) {
            Ok(meta) => meta,
            Err(e) if e.kind() == std::io::ErrorKind::NotFound => return Ok(None),
            Err(e) => return Err(format!("cannot look at {}: {e}", path.display())),
        };

        if meta.is_symlink() {
            let target = std::fs::read_link(path)
                .map_err(|e| format!("cannot read the link {}: {e}", path.display()))?;
            let text = super::scan::to_slash(&target);
            // A link's identity is its target text. Hashed like content so a
            // link and a file holding the same text are still different by
            // kind, and two links compare by what they point at.
            return Ok(Some(Self {
                kind: EntryKind::Symlink,
                hash: hash_bytes(text.as_bytes()),
                size: text.len() as u64,
                executable: false,
            }));
        }
        if meta.is_dir() {
            return Ok(None);
        }

        let bytes = std::fs::read(path)
            .map_err(|e| format!("cannot read {}: {e}", path.display()))?;
        Ok(Some(Self {
            kind: EntryKind::File,
            hash: hash_bytes(&bytes),
            size: bytes.len() as u64,
            executable: is_executable(&meta),
        }))
    }

    /// Whether two entries are the same content in the same shape.
    pub fn same_as(&self, other: &Self) -> bool {
        self.kind == other.kind && self.hash == other.hash && self.executable == other.executable
    }
}

/// SHA-256, hex, lowercase. The one content identity this feature uses.
pub fn hash_bytes(bytes: &[u8]) -> String {
    use sha2::{Digest, Sha256};
    let mut hasher = Sha256::new();
    hasher.update(bytes);
    format!("{:x}", hasher.finalize())
}

#[cfg(unix)]
fn is_executable(meta: &std::fs::Metadata) -> bool {
    use std::os::unix::fs::PermissionsExt;
    meta.permissions().mode() & 0o100 != 0
}

/// Windows has no execute bit. Reported as false rather than guessed from an
/// extension: a `.exe` is not the same fact, and a value invented here would
/// travel to a machine where it IS a permission and change a file's mode.
#[cfg(windows)]
fn is_executable(_meta: &std::fs::Metadata) -> bool {
    false
}

/// The last state both sides agreed on, per path.
///
/// Absent from the map means "neither side had this path when we last agreed",
/// which is what makes a file created on one side an addition rather than a
/// conflict with nothing.
pub type Baseline = BTreeMap<String, Entry>;

/// What one side must do to converge, for one path.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(tag = "action", rename_all = "snake_case")]
pub enum Action {
    /// This side's content is the one to keep; the peer takes it.
    Send { path: String, entry: Entry },
    /// The peer's content is the one to keep; this side takes it.
    Receive { path: String, entry: Entry },
    /// The path is gone on this side and untouched on the peer's: it goes
    /// there too.
    SendDeletion { path: String },
    /// Gone on the peer's side and untouched here: it goes here too.
    ReceiveDeletion { path: String },
    /// Both sides changed the same base differently. Nothing moves.
    Conflict {
        path: String,
        /// What each side has now. `None` means the path is deleted there.
        here: Option<Entry>,
        there: Option<Entry>,
        /// What they agreed on last, when they ever did.
        base: Option<Entry>,
    },
    /// Both sides made the same change. Nothing to move; the baseline moves.
    Agree { path: String, entry: Option<Entry> },
}

impl Action {
    pub fn path(&self) -> &str {
        match self {
            Self::Send { path, .. }
            | Self::Receive { path, .. }
            | Self::SendDeletion { path }
            | Self::ReceiveDeletion { path }
            | Self::Conflict { path, .. }
            | Self::Agree { path, .. } => path,
        }
    }

    /// The one-word name of what this action does, for a log or a record.
    pub fn kind(&self) -> &'static str {
        match self {
            Self::Send { .. } => "send",
            Self::Receive { .. } => "receive",
            Self::SendDeletion { .. } => "send_deletion",
            Self::ReceiveDeletion { .. } => "receive_deletion",
            Self::Conflict { .. } => "conflict",
            Self::Agree { .. } => "agree",
        }
    }

    pub fn is_conflict(&self) -> bool {
        matches!(self, Self::Conflict { .. })
    }

    /// Whether anything has to move for this action.
    pub fn moves_data(&self) -> bool {
        matches!(
            self,
            Self::Send { .. }
                | Self::Receive { .. }
                | Self::SendDeletion { .. }
                | Self::ReceiveDeletion { .. }
        )
    }

    /// Whether this action brings something ONTO this machine.
    ///
    /// The direction is what decides who the automatic policy belongs to.
    /// `auto` means "changes arriving here are applied without asking me", and
    /// it is a statement one machine makes about its own tree — never about
    /// the peer's. Whether this machine's changes are applied THERE is the
    /// peer's own decision, made by the peer's own pass with the peer's own
    /// mode.
    ///
    /// So continuity is asked about incoming actions only. An outgoing
    /// difference nobody decided about waits for the other machine, however
    /// this one is set.
    pub fn arrives_here(&self) -> bool {
        matches!(self, Self::Receive { .. } | Self::ReceiveDeletion { .. })
    }

    /// Whether this action would put something on the PEER.
    pub fn leaves_here(&self) -> bool {
        matches!(self, Self::Send { .. } | Self::SendDeletion { .. })
    }
}

/// Whether one action may cross, given how this machine is set and whether a
/// person has spoken about that path.
///
/// The one place the direction rule lives, so the coordinator and every
/// surface that explains it cannot disagree.
///
/// `auto` is a statement a machine makes about its OWN working tree — "what
/// arrives here is applied without asking me" — and never about the peer's.
/// Whether this machine's changes are applied THERE is the peer's decision,
/// made by the peer's own pass with the peer's own mode. Two machines can
/// therefore differ, and changes travel automatically in one direction only.
///
/// A DECISION crosses either way: `take` and `keep` are a person on this
/// machine saying which side wins, and that is consent for the direction they
/// chose.
pub fn crosses(action: &Action, continuity: crate::peer::model::Continuity, decided: bool) -> bool {
    // Two machines that already hold the same bytes have agreed whatever the
    // mode; nothing moves and the baseline may advance to say so.
    if matches!(action, Action::Agree { .. }) {
        return true;
    }
    if !continuity.carries_decided() {
        // Off or paused: a decision taken before a pause is not consent to act
        // during it.
        return false;
    }
    if decided {
        return true;
    }
    action.arrives_here() && continuity.takes_undecided()
}

/// Everything one repository must do to converge.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct Convergence {
    pub actions: Vec<Action>,
}

impl Convergence {
    pub fn conflicts(&self) -> impl Iterator<Item = &Action> {
        self.actions.iter().filter(|action| action.is_conflict())
    }

    pub fn pending(&self) -> usize {
        self.actions.iter().filter(|a| a.moves_data()).count()
    }

    /// Whether both sides already hold the same tree.
    ///
    /// Note what this does NOT mean: an empty action list is not the same as
    /// "synced", because a baseline that was never verified produces no
    /// actions either. The coordinator promotes to `Synced` only after a scan
    /// on both sides produced this against a baseline both acknowledged.
    pub fn is_converged(&self) -> bool {
        !self.actions.iter().any(|action| action.moves_data() || action.is_conflict())
    }
}

/// Decide what each side must do, from the two current sets and the baseline.
///
/// Pure: no filesystem, no network, no clock. Every rule this feature makes a
/// promise about is decided here, which is why it can be tested exhaustively
/// without either machine existing.
pub fn plan(here: &BTreeMap<String, Entry>, there: &BTreeMap<String, Entry>, base: &Baseline) -> Convergence {
    let paths: BTreeSet<&String> = here.keys().chain(there.keys()).chain(base.keys()).collect();
    let mut actions = Vec::new();

    for path in paths {
        let mine = here.get(path);
        let theirs = there.get(path);
        let based = base.get(path);

        let changed_here = !same(mine, based);
        let changed_there = !same(theirs, based);

        let action = match (changed_here, changed_there) {
            // Neither side moved: nothing to do and nothing to agree.
            (false, false) => continue,

            // One side moved. The other is still at the base, so taking the
            // change cannot lose anything: what it would overwrite is exactly
            // what both sides last agreed on.
            (true, false) => match mine {
                Some(entry) => Action::Send {
                    path: path.clone(),
                    entry: entry.clone(),
                },
                None => Action::SendDeletion { path: path.clone() },
            },
            (false, true) => match theirs {
                Some(entry) => Action::Receive {
                    path: path.clone(),
                    entry: entry.clone(),
                },
                None => Action::ReceiveDeletion { path: path.clone() },
            },

            // Both moved. Identical outcomes converge; anything else is a
            // conflict — including one side deleting what the other edited,
            // which is the case where "the deletion wins" would destroy work
            // nobody reviewed.
            (true, true) => {
                if same(mine, theirs) {
                    Action::Agree {
                        path: path.clone(),
                        entry: mine.cloned(),
                    }
                } else {
                    Action::Conflict {
                        path: path.clone(),
                        here: mine.cloned(),
                        there: theirs.cloned(),
                        base: based.cloned(),
                    }
                }
            }
        };
        actions.push(action);
    }

    Convergence { actions }
}

/// Whether two optional entries are the same thing, absence included.
fn same(left: Option<&Entry>, right: Option<&Entry>) -> bool {
    match (left, right) {
        (None, None) => true,
        (Some(a), Some(b)) => a.same_as(b),
        _ => false,
    }
}

/// The baseline after a convergence has been applied and verified.
///
/// Only the actions that actually landed move the baseline. A conflict leaves
/// its path at the base it had — that is what makes the conflict survive a
/// restart and what keeps both original versions recoverable — and a path that
/// failed to apply is simply not in `applied`.
///
/// `Agree` is the exception, and it has to be: it is not a transfer, so it
/// can never be in `applied`, and it is the one action that says the two
/// machines ALREADY hold the same thing. Leaving it out left a path in the
/// baseline that neither machine had any more — a phantom both sides
/// recomputed as agreement forever, while their baselines differed by that
/// one entry. Since every request carries a baseline digest, the two then
/// refused each other's transfers permanently: nothing moved, both read as
/// "checking", and no edit made afterwards could ever cross. Agreement
/// observed by both sides, from the same two scans, moves both baselines the
/// same way without anything having to travel.
pub fn advance(base: &Baseline, convergence: &Convergence, applied: &BTreeSet<String>) -> Baseline {
    let mut next = base.clone();
    for action in &convergence.actions {
        if action.is_conflict() {
            continue;
        }
        // Everything that MOVES has to have moved. Agreement did not move.
        if action.moves_data() && !applied.contains(action.path()) {
            continue;
        }
        match action {
            Action::Send { path, entry } | Action::Receive { path, entry } => {
                next.insert(path.clone(), entry.clone());
            }
            Action::SendDeletion { path } | Action::ReceiveDeletion { path } => {
                next.remove(path);
            }
            Action::Agree { path, entry } => match entry {
                Some(entry) => {
                    next.insert(path.clone(), entry.clone());
                }
                None => {
                    next.remove(path);
                }
            },
            Action::Conflict { .. } => unreachable!("conflicts are skipped above"),
        }
    }
    next
}

#[cfg(test)]
#[path = "converge_tests.rs"]
mod tests;