tsafe_core/

sync.rs

//! Three-way vault merge for concurrent edit reconciliation.
//!
//! `merge` takes a common ancestor and two diverged [`VaultFile`] snapshots and
//! produces a merged result.  Secret additions and deletions from both sides are
//! applied; conflicting edits (same key changed differently) resolve in favour of
//! the `theirs` side with a conflict marker in the merged entry's tags.

use std::collections::{HashMap, HashSet};

use crate::errors::SafeResult;
use crate::vault::{SecretEntry, VaultFile};

/// Result of a three-way merge between base, ours (local), and theirs (remote) vault files.
#[derive(Debug)]
pub struct MergeResult {
    /// The merged vault file — ready to write to disk.
    pub merged: VaultFile,
    /// Keys added from theirs (remote additions we didn't have).
    pub added_from_theirs: Vec<String>,
    /// Keys updated from theirs (we were stale, theirs was newer).
    pub updated_from_theirs: Vec<String>,
    /// Keys added from ours (local additions not on remote).
    pub added_from_ours: Vec<String>,
    /// Keys where both sides changed — resolved by last-write-wins.
    pub conflicts: Vec<String>,
    /// Keys deleted (removed from one or both sides).
    pub deleted: Vec<String>,
    /// True if nothing changed (ours == theirs at the key level).
    pub is_noop: bool,
    /// Explicit per-key merge outcomes in deterministic key order.
    pub decisions: Vec<MergeDecision>,
}

/// Explicit per-key outcome from the sync merge lifecycle.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MergeDecision {
    pub key: String,
    pub state: MergeState,
}

/// Merge lifecycle states for one key across base, ours, and theirs.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MergeState {
    Unchanged,
    AddedFromOurs,
    AddedFromTheirs,
    AddedConcurrentlyIdentical,
    UpdatedFromOurs,
    UpdatedFromTheirs,
    DeletedByOurs,
    DeletedByTheirs,
    DeletedByBoth,
    ConflictResolvedToOurs,
    ConflictResolvedToTheirs,
    DeleteConflictResolvedToOurs,
    DeleteConflictResolvedToTheirs,
}

#[derive(Debug, Clone)]
struct PlannedMergeDecision {
    state: MergeState,
    merged_entry: Option<SecretEntry>,
}

/// Compare two SecretEntry values by their encrypted representation.
/// Returns true if the ciphertext is identical (same encryption = same value + same nonce).
fn entry_eq(a: &SecretEntry, b: &SecretEntry) -> bool {
    a.nonce == b.nonce && a.ciphertext == b.ciphertext
}

/// Three-way merge of vault files at the per-key level.
///
/// Works entirely on the encrypted representation — no decryption required.
/// Compares `nonce + ciphertext` to detect changes. Uses `updated_at` as a
/// last-write-wins tiebreaker when both sides changed the same key.
///
/// `base` may have an empty secrets map (first sync / no common ancestor).
pub fn three_way_merge(
    base: &VaultFile,
    ours: &VaultFile,
    theirs: &VaultFile,
) -> SafeResult<MergeResult> {
    let mut merged_secrets: HashMap<String, SecretEntry> = HashMap::new();
    let mut added_from_theirs = Vec::new();
    let mut updated_from_theirs = Vec::new();
    let mut added_from_ours = Vec::new();
    let mut conflicts = Vec::new();
    let mut deleted = Vec::new();
    let mut decisions = Vec::new();

    // Collect all keys across all three versions.
    let all_keys: HashSet<&str> = base
        .secrets
        .keys()
        .chain(ours.secrets.keys())
        .chain(theirs.secrets.keys())
        .map(String::as_str)
        .collect();
    let mut all_keys: Vec<&str> = all_keys.into_iter().collect();
    all_keys.sort_unstable();

    for key in all_keys {
        let planned = plan_merge_decision(
            base.secrets.get(key),
            ours.secrets.get(key),
            theirs.secrets.get(key),
        )?;
        match planned.state {
            MergeState::AddedFromOurs => {
                added_from_ours.push(key.to_string());
            }
            MergeState::AddedFromTheirs => {
                added_from_theirs.push(key.to_string());
            }
            MergeState::UpdatedFromTheirs => {
                updated_from_theirs.push(key.to_string());
            }
            MergeState::DeletedByOurs | MergeState::DeletedByTheirs | MergeState::DeletedByBoth => {
                deleted.push(key.to_string());
            }
            MergeState::ConflictResolvedToOurs
            | MergeState::ConflictResolvedToTheirs
            | MergeState::DeleteConflictResolvedToOurs
            | MergeState::DeleteConflictResolvedToTheirs => {
                conflicts.push(key.to_string());
            }
            MergeState::Unchanged
            | MergeState::AddedConcurrentlyIdentical
            | MergeState::UpdatedFromOurs => {}
        }
        if let Some(entry) = planned.merged_entry {
            merged_secrets.insert(key.to_string(), entry);
        }
        decisions.push(MergeDecision {
            key: key.to_string(),
            state: planned.state,
        });
    }

    // Merge age_recipients as a union.
    let mut merged_recipients: Vec<String> = ours.age_recipients.clone();
    for r in &theirs.age_recipients {
        if !merged_recipients.contains(r) {
            merged_recipients.push(r.clone());
        }
    }

    let is_noop = decisions
        .iter()
        .all(|decision| decision.state == MergeState::Unchanged);

    let merged = VaultFile {
        schema: ours.schema.clone(),
        kdf: ours.kdf.clone(),
        cipher: ours.cipher.clone(),
        vault_challenge: ours.vault_challenge.clone(),
        created_at: ours.created_at,
        updated_at: std::cmp::max(ours.updated_at, theirs.updated_at),
        secrets: merged_secrets,
        age_recipients: merged_recipients,
        // wrapped_dek: if recipients changed, caller must re-wrap.
        // For now, keep ours (caller handles re-wrapping if needed).
        wrapped_dek: ours.wrapped_dek.clone(),
    };

    Ok(MergeResult {
        merged,
        added_from_theirs,
        updated_from_theirs,
        added_from_ours,
        conflicts,
        deleted,
        is_noop,
        decisions,
    })
}

fn plan_merge_decision(
    base: Option<&SecretEntry>,
    ours: Option<&SecretEntry>,
    theirs: Option<&SecretEntry>,
) -> SafeResult<PlannedMergeDecision> {
    match (base, ours, theirs) {
        // Not in base — only in ours → keep ours (local addition).
        (None, Some(o), None) => Ok(PlannedMergeDecision {
            state: MergeState::AddedFromOurs,
            merged_entry: Some(o.clone()),
        }),

        // Not in base — only in theirs → take theirs (remote addition).
        (None, None, Some(t)) => Ok(PlannedMergeDecision {
            state: MergeState::AddedFromTheirs,
            merged_entry: Some(t.clone()),
        }),

        // Not in base — in both → simultaneous add.
        (None, Some(o), Some(t)) => {
            if entry_eq(o, t) {
                Ok(PlannedMergeDecision {
                    state: MergeState::AddedConcurrentlyIdentical,
                    merged_entry: Some(o.clone()),
                })
            } else if t.updated_at >= o.updated_at {
                Ok(PlannedMergeDecision {
                    state: MergeState::ConflictResolvedToTheirs,
                    merged_entry: Some(t.clone()),
                })
            } else {
                Ok(PlannedMergeDecision {
                    state: MergeState::ConflictResolvedToOurs,
                    merged_entry: Some(o.clone()),
                })
            }
        }

        // In base, not in ours, not in theirs → both deleted.
        (Some(_), None, None) => Ok(PlannedMergeDecision {
            state: MergeState::DeletedByBoth,
            merged_entry: None,
        }),

        // In base, deleted in ours, unchanged in theirs → deleted.
        (Some(b), None, Some(t)) => {
            if entry_eq(b, t) {
                Ok(PlannedMergeDecision {
                    state: MergeState::DeletedByOurs,
                    merged_entry: None,
                })
            } else {
                Ok(PlannedMergeDecision {
                    state: MergeState::DeleteConflictResolvedToTheirs,
                    merged_entry: Some(t.clone()),
                })
            }
        }

        // In base, unchanged in ours, deleted in theirs → deleted.
        (Some(b), Some(o), None) => {
            if entry_eq(b, o) {
                Ok(PlannedMergeDecision {
                    state: MergeState::DeletedByTheirs,
                    merged_entry: None,
                })
            } else {
                Ok(PlannedMergeDecision {
                    state: MergeState::DeleteConflictResolvedToOurs,
                    merged_entry: Some(o.clone()),
                })
            }
        }

        // In base, in both — check for changes.
        (Some(b), Some(o), Some(t)) => {
            let ours_changed = !entry_eq(b, o);
            let theirs_changed = !entry_eq(b, t);

            match (ours_changed, theirs_changed) {
                (false, false) => Ok(PlannedMergeDecision {
                    state: MergeState::Unchanged,
                    merged_entry: Some(o.clone()),
                }),
                (true, false) => Ok(PlannedMergeDecision {
                    state: MergeState::UpdatedFromOurs,
                    merged_entry: Some(o.clone()),
                }),
                (false, true) => Ok(PlannedMergeDecision {
                    state: MergeState::UpdatedFromTheirs,
                    merged_entry: Some(t.clone()),
                }),
                (true, true) => {
                    if entry_eq(o, t) {
                        Ok(PlannedMergeDecision {
                            state: MergeState::UpdatedFromOurs,
                            merged_entry: Some(o.clone()),
                        })
                    } else if t.updated_at >= o.updated_at {
                        Ok(PlannedMergeDecision {
                            state: MergeState::ConflictResolvedToTheirs,
                            merged_entry: Some(t.clone()),
                        })
                    } else {
                        Ok(PlannedMergeDecision {
                            state: MergeState::ConflictResolvedToOurs,
                            merged_entry: Some(o.clone()),
                        })
                    }
                }
            }
        }

        // Not in any — impossible since we iterate all_keys (invariant violation).
        (None, None, None) => Err(crate::errors::SafeError::InvalidVault {
            reason: "merge invariant violated: key absent from all three vaults".into(),
        }),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::vault::{KdfParams, VaultChallenge};
    use chrono::{Duration, Utc};
    use std::collections::HashMap;

    fn empty_vault() -> VaultFile {
        VaultFile {
            schema: "tsafe/vault/v1".into(),
            kdf: KdfParams {
                algorithm: "argon2id".into(),
                m_cost: 65536,
                t_cost: 3,
                p_cost: 4,
                salt: "AAAA".into(),
            },
            cipher: "xchacha20poly1305".into(),
            vault_challenge: VaultChallenge {
                nonce: "AAAA".into(),
                ciphertext: "AAAA".into(),
            },
            created_at: Utc::now(),
            updated_at: Utc::now(),
            secrets: HashMap::new(),
            age_recipients: Vec::new(),
            wrapped_dek: None,
        }
    }

    fn make_entry(nonce: &str, ct: &str, age_days: i64) -> SecretEntry {
        let now = Utc::now();
        SecretEntry {
            nonce: nonce.into(),
            ciphertext: ct.into(),
            created_at: now - Duration::days(age_days + 1),
            updated_at: now - Duration::days(age_days),
            tags: HashMap::new(),
            history: Vec::new(),
        }
    }

    #[test]
    fn merge_no_changes_is_noop() {
        let base = empty_vault();
        let ours = base.clone();
        let theirs = base.clone();
        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert!(result.is_noop);
        assert!(result.conflicts.is_empty());
    }

    #[test]
    fn merge_disjoint_additions() {
        let base = empty_vault();
        let mut ours = base.clone();
        ours.secrets
            .insert("KEY_A".into(), make_entry("n1", "ct1", 0));
        let mut theirs = base.clone();
        theirs
            .secrets
            .insert("KEY_B".into(), make_entry("n2", "ct2", 0));

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert!(!result.is_noop);
        assert!(result.merged.secrets.contains_key("KEY_A"));
        assert!(result.merged.secrets.contains_key("KEY_B"));
        assert_eq!(result.added_from_ours, vec!["KEY_A"]);
        assert_eq!(result.added_from_theirs, vec!["KEY_B"]);
        assert!(result.conflicts.is_empty());
        assert_eq!(
            result.decisions,
            vec![
                MergeDecision {
                    key: "KEY_A".into(),
                    state: MergeState::AddedFromOurs,
                },
                MergeDecision {
                    key: "KEY_B".into(),
                    state: MergeState::AddedFromTheirs,
                },
            ]
        );
    }

    #[test]
    fn merge_ours_deletes_theirs_unchanged() {
        let mut base = empty_vault();
        base.secrets
            .insert("DEL".into(), make_entry("n1", "ct1", 5));
        let mut ours = base.clone();
        ours.secrets.remove("DEL");
        let theirs = base.clone(); // unchanged

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert!(!result.merged.secrets.contains_key("DEL"));
        assert_eq!(result.deleted, vec!["DEL"]);
    }

    #[test]
    fn merge_both_edit_same_key_lww() {
        let mut base = empty_vault();
        base.secrets
            .insert("SHARED".into(), make_entry("n0", "ct0", 10));

        let mut ours = base.clone();
        ours.secrets
            .insert("SHARED".into(), make_entry("n1", "ct1", 2)); // 2 days ago

        let mut theirs = base.clone();
        theirs
            .secrets
            .insert("SHARED".into(), make_entry("n2", "ct2", 0)); // today (newer)

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert_eq!(result.conflicts, vec!["SHARED"]);
        // Theirs wins (more recent updated_at).
        assert_eq!(result.merged.secrets["SHARED"].ciphertext, "ct2");
    }

    #[test]
    fn merge_both_edit_same_value_no_conflict() {
        let mut base = empty_vault();
        base.secrets
            .insert("SAME".into(), make_entry("n0", "ct0", 5));

        let mut ours = base.clone();
        ours.secrets
            .insert("SAME".into(), make_entry("n1", "ct1", 0));

        let mut theirs = base.clone();
        theirs
            .secrets
            .insert("SAME".into(), make_entry("n1", "ct1", 0)); // identical edit

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert!(result.conflicts.is_empty());
    }

    #[test]
    fn merge_only_theirs_changed() {
        let mut base = empty_vault();
        base.secrets.insert("K".into(), make_entry("n0", "ct0", 5));
        let ours = base.clone();
        let mut theirs = base.clone();
        theirs
            .secrets
            .insert("K".into(), make_entry("n1", "ct1", 0));

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert_eq!(result.updated_from_theirs, vec!["K"]);
        assert_eq!(result.merged.secrets["K"].ciphertext, "ct1");
    }

    #[test]
    fn merge_recipients_union() {
        let mut base = empty_vault();
        base.age_recipients = vec!["age1aaa".into()];

        let mut ours = base.clone();
        ours.age_recipients.push("age1bbb".into());

        let mut theirs = base.clone();
        theirs.age_recipients.push("age1ccc".into());

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert!(result
            .merged
            .age_recipients
            .contains(&"age1aaa".to_string()));
        assert!(result
            .merged
            .age_recipients
            .contains(&"age1bbb".to_string()));
        assert!(result
            .merged
            .age_recipients
            .contains(&"age1ccc".to_string()));
    }

    #[test]
    fn merge_delete_vs_edit_conflict_prefers_live_value() {
        let mut base = empty_vault();
        base.secrets
            .insert("KEY".into(), make_entry("n0", "ct0", 5));

        // Ours deletes it.
        let mut ours = base.clone();
        ours.secrets.remove("KEY");

        // Theirs edits it (changed ciphertext).
        let mut theirs = base.clone();
        theirs
            .secrets
            .insert("KEY".into(), make_entry("n1", "ct1", 0));

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        // Should prefer the live value over deletion.
        assert!(result.merged.secrets.contains_key("KEY"));
        assert!(result.conflicts.contains(&"KEY".to_string()));
        assert_eq!(
            result.decisions,
            vec![MergeDecision {
                key: "KEY".into(),
                state: MergeState::DeleteConflictResolvedToTheirs,
            }]
        );
    }

    #[test]
    fn merge_both_delete_records_deleted_by_both() {
        let mut base = empty_vault();
        base.secrets
            .insert("GONE".into(), make_entry("n0", "ct0", 5));

        let mut ours = base.clone();
        ours.secrets.remove("GONE");

        let mut theirs = base.clone();
        theirs.secrets.remove("GONE");

        let result = three_way_merge(&base, &ours, &theirs).unwrap();
        assert_eq!(result.deleted, vec!["GONE"]);
        assert_eq!(
            result.decisions,
            vec![MergeDecision {
                key: "GONE".into(),
                state: MergeState::DeletedByBoth,
            }]
        );
    }
}