Privacy-first password manager with built-in email aliasing. Fully encrypted and self-hostable.
//! Last-write-wins merge of the canonical vault (manifests and data buckets), one manifest at a time, rows in and
//! rows out. Both sides arrive in canonical form and the output is the merged canonical form.
use std::collections::{BTreeSet, HashMap, HashSet};
use serde::{Deserialize, Serialize};
use crate::common::error::VaultResult;
use crate::common::timestamp::updated_at;
use crate::vault_model::{id_key, TableConfig, SYNCABLE_TABLES};
use crate::vault_codec::{bucket_categories, ensure_readable_schema_version, identity_part, is_bucketed_table, tables_for_category, CodecRecord, DataBucket, Manifest};
mod item_deletes;
#[cfg(test)]
mod tests;
/// How the rows of a merge were decided. The base is the server's side, the incoming side the local vault.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct MergeStats {
/// Rows both sides hold where the base row stood.
pub base_kept: u32,
/// Rows both sides hold where the newer incoming row replaced the base row.
pub incoming_won: u32,
/// Rows only the base holds.
pub base_only: u32,
/// Rows only the incoming side holds.
pub incoming_only: u32,
}
impl MergeStats {
/// Add another manifest's counters to these, for a whole-vault total.
pub fn add(&mut self, other: &MergeStats) {
self.base_kept += other.base_kept;
self.incoming_won += other.incoming_won;
self.base_only += other.base_only;
self.incoming_only += other.incoming_only;
}
}
/// Input of the canonical merge: the server side is the base (kept on ties), the local side the incoming set.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct CanonicalMergeInput {
pub server_manifests: Vec<Manifest>,
pub server_buckets: Vec<DataBucket>,
#[serde(default)]
pub contentless_server_manifest_ids: Vec<String>,
pub local_manifests: Vec<Manifest>,
pub local_buckets: Vec<DataBucket>,
pub schema_columns: HashMap<String, Vec<String>>,
}
/// One manifest's merged result.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct CanonicalManifestMerge {
pub manifest_id: String,
pub manifest: Manifest,
pub buckets: Vec<DataBucket>,
pub stats: MergeStats,
}
/// Output of the canonical merge.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct CanonicalMergeOutput {
pub manifests: Vec<CanonicalManifestMerge>,
pub dropped_local_manifest_ids: Vec<String>,
}
/// Merge the local canonical vault onto the server canonical vault (the base), per manifest.
pub fn merge_canonical(input: CanonicalMergeInput) -> VaultResult<CanonicalMergeOutput> {
let CanonicalMergeInput { server_manifests, server_buckets, contentless_server_manifest_ids, local_manifests, local_buckets, schema_columns } = input;
for manifest in &server_manifests {
ensure_readable_schema_version(manifest.schema_version, &format!("server manifest {}", manifest.manifest_id))?;
}
for bucket in &server_buckets {
ensure_readable_schema_version(bucket.schema_version, &format!("\"{}\" server bucket of manifest {}", bucket.category, bucket.manifest_id))?;
}
let mut local_by_id: HashMap<String, Manifest> = local_manifests.into_iter().map(|m| (id_key(&m.manifest_id), m)).collect();
let mut local_buckets_by_id = group_buckets(local_buckets);
let mut server_buckets_by_id = group_buckets(server_buckets);
let mut manifests: Vec<CanonicalManifestMerge> = Vec::new();
for server_manifest in server_manifests {
let key = id_key(&server_manifest.manifest_id);
let local = local_by_id.remove(&key);
let local_buckets = local_buckets_by_id.remove(&key).unwrap_or_default();
let server_buckets = server_buckets_by_id.remove(&key).unwrap_or_default();
manifests.push(merge_manifest_pair(server_manifest, server_buckets, local, local_buckets, &schema_columns));
}
// A contentless server manifest has no base; the local counterpart passes through whole.
for manifest_id in contentless_server_manifest_ids {
let key = id_key(&manifest_id);
if let Some(local) = local_by_id.remove(&key) {
manifests.push(pass_through(local, local_buckets_by_id.remove(&key).unwrap_or_default()));
}
}
let mut dropped_local_manifest_ids: Vec<String> = local_by_id.into_values().map(|m| m.manifest_id).collect();
dropped_local_manifest_ids.sort();
Ok(CanonicalMergeOutput { manifests, dropped_local_manifest_ids })
}
/// Group buckets by their manifest id (lowercased).
fn group_buckets(buckets: Vec<DataBucket>) -> HashMap<String, Vec<DataBucket>> {
let mut grouped: HashMap<String, Vec<DataBucket>> = HashMap::new();
for bucket in buckets {
grouped.entry(id_key(&bucket.manifest_id)).or_default().push(bucket);
}
grouped
}
/// Merge one manifest: LWW over the flattened table view of both sides, then split the bucketed tables back out. The
/// merged `Manifest` is the server one with only its tables replaced.
fn merge_manifest_pair(server: Manifest, server_buckets: Vec<DataBucket>, local: Option<Manifest>, local_buckets: Vec<DataBucket>, schema_columns: &HashMap<String, Vec<String>>) -> CanonicalManifestMerge {
let manifest_id = server.manifest_id.clone();
let mut stats = MergeStats::default();
// A bucket of a category this build does not know cannot be flattened without losing its category: the server's
// ride through as-is and the local ones are dropped, exactly as the base-wins rule treats every unknown table.
let server_bucket_extras: HashMap<String, HashMap<String, serde_json::Value>> = server_buckets.iter().map(|bucket| (bucket.category.clone(), bucket.extra.clone())).collect();
let (server_bucket_tables, unknown_server_buckets) = split_known_buckets(server_buckets);
let (local_bucket_tables, _) = split_known_buckets(local_buckets);
let mut base_tables = server.tables.clone();
base_tables.extend(server_bucket_tables);
let mut incoming_tables = local.map(|m| m.tables).unwrap_or_default();
incoming_tables.extend(local_bucket_tables);
item_deletes::resolve_item_deletes(&mut base_tables, &mut incoming_tables);
let table_names: BTreeSet<String> = base_tables.keys().chain(incoming_tables.keys()).cloned().collect();
let mut merged: HashMap<String, Vec<CodecRecord>> = HashMap::new();
for name in table_names {
let base_entry = base_tables.remove(&name);
let base_carried_table = base_entry.is_some();
let base_rows = base_entry.unwrap_or_default();
let incoming_rows = incoming_tables.remove(&name).unwrap_or_default();
let merged_rows = match SYNCABLE_TABLES.iter().find(|t| t.name == name) {
Some(config) => merge_rows(config, base_rows, incoming_rows, schema_columns, &mut stats),
// Not a syncable table (a skip table, or one from a newer writer): the base wins as-is.
None => base_rows,
};
// A table the base carried stays in the output even when it merged to nothing, so the manifest keeps the base's shape.
if base_carried_table || !merged_rows.is_empty() {
merged.insert(name, merged_rows);
}
}
// A delete that won can leave the other side's children under a tombstoned item, and a union of concurrently
// added multi-value rows can leave two rows at the same ValueIndex: repair and normalize like any canonicalized manifest.
crate::vault_codec::integrity::repair(&mut merged);
crate::vault_codec::normalize::normalize_row_shapes(&mut merged);
// One bucket per category: the merged rows of the tables this build buckets, plus the server's tables of that
// category it does not know; a merged bucket keeps the server's extra top-level keys.
let mut buckets: Vec<DataBucket> = Vec::new();
for category in bucket_categories() {
let mut bucket_tables: HashMap<String, Vec<CodecRecord>> = HashMap::new();
for table in tables_for_category(category) {
if let Some(rows) = merged.remove(table) {
bucket_tables.insert(table.to_string(), rows);
}
}
for unknown in unknown_server_buckets.iter().filter(|bucket| bucket.category == category) {
bucket_tables.extend(unknown.tables.clone());
}
if !bucket_tables.is_empty() {
let extra = server_bucket_extras.get(category).cloned().unwrap_or_default();
buckets.push(DataBucket { extra, ..DataBucket::new(manifest_id.clone(), category.to_string(), bucket_tables) });
}
}
buckets.extend(unknown_server_buckets.into_iter().filter(|bucket| !bucket_categories().contains(&bucket.category.as_str())));
let manifest = Manifest { tables: merged, ..server };
CanonicalManifestMerge { manifest_id, manifest, buckets, stats }
}
/// Split buckets into the flattened rows of the tables this build buckets itself, and leftover buckets holding every
/// other table (a newer writer's), kept under their served category.
fn split_known_buckets(buckets: Vec<DataBucket>) -> (HashMap<String, Vec<CodecRecord>>, Vec<DataBucket>) {
let mut tables: HashMap<String, Vec<CodecRecord>> = HashMap::new();
let mut unknown: Vec<DataBucket> = Vec::new();
for bucket in buckets {
let mut unknown_tables: HashMap<String, Vec<CodecRecord>> = HashMap::new();
for (name, rows) in bucket.tables {
if is_bucketed_table(&name) {
tables.entry(name).or_default().extend(rows);
} else {
unknown_tables.insert(name, rows);
}
}
if !unknown_tables.is_empty() {
unknown.push(DataBucket::new(bucket.manifest_id, bucket.category, unknown_tables));
}
}
(tables, unknown)
}
/// A contentless server manifest's local counterpart passes through whole: every row is an incoming-only row.
fn pass_through(local: Manifest, local_buckets: Vec<DataBucket>) -> CanonicalManifestMerge {
let row_count = |tables: &HashMap<String, Vec<CodecRecord>>| tables.values().map(|rows| rows.len() as u32).sum::<u32>();
let stats = MergeStats { incoming_only: row_count(&local.tables) + local_buckets.iter().map(|b| row_count(&b.tables)).sum::<u32>(), ..MergeStats::default() };
CanonicalManifestMerge { manifest_id: local.manifest_id.clone(), manifest: local, buckets: local_buckets, stats }
}
/// LWW one table, rows out: base rows in order (replaced where the incoming row is strictly newer), then
/// incoming-only rows in first-occurrence order.
fn merge_rows(config: &TableConfig, base_rows: Vec<CodecRecord>, incoming_rows: Vec<CodecRecord>, schema_columns: &HashMap<String, Vec<String>>, stats: &mut MergeStats) -> Vec<CodecRecord> {
let identity_columns = config.identity_columns();
// Rows arrive in wire shape, so a canonical key may rely on stripped derived ids.
let match_columns: &[&str] = if config.canonical_key_columns.is_empty() { &identity_columns } else { config.canonical_key_columns };
let known_columns: Option<HashSet<&str>> = schema_columns.get(config.name).map(|cols| cols.iter().map(String::as_str).collect());
// Winner per match key among incoming rows; on duplicates the latest UpdatedAt wins.
let mut incoming_map: HashMap<String, &CodecRecord> = HashMap::new();
for record in &incoming_rows {
let key = get_key(record, match_columns);
match incoming_map.get(&key) {
Some(existing) if updated_at(record) <= updated_at(existing) => {}
_ => {
incoming_map.insert(key, record);
}
}
}
let mut merged: Vec<CodecRecord> = Vec::with_capacity(base_rows.len());
for base_record in base_rows {
let key = get_key(&base_record, match_columns);
match incoming_map.remove(&key) {
Some(incoming) => {
let (incoming_ts, base_ts) = (updated_at(incoming), updated_at(&base_record));
match (incoming_ts, base_ts) {
(Some(i_ts), Some(b_ts)) if i_ts > b_ts => {
stats.incoming_won += 1;
merged.push(overlay_winner(incoming.clone(), &base_record, &identity_columns, known_columns.as_ref()));
}
_ => {
stats.base_kept += 1;
merged.push(base_record);
}
}
}
None => {
stats.base_only += 1;
merged.push(base_record);
}
}
}
for record in &incoming_rows {
if let Some(winner) = incoming_map.remove(&get_key(record, match_columns)) {
stats.incoming_only += 1;
merged.push(winner.clone());
}
}
merged
}
/// The winning incoming row, with the base's identity columns and the columns this build's schema does not know.
fn overlay_winner(mut winner: CodecRecord, base: &CodecRecord, identity_columns: &[&str], known_columns: Option<&HashSet<&str>>) -> CodecRecord {
for (column, value) in base {
let base_wins = identity_columns.contains(&column.as_str()) || known_columns.is_some_and(|known| !known.contains(column.as_str()));
if base_wins {
winner.insert(column.clone(), value.clone());
}
}
winner
}
/// Stable string key over `columns`, ids compared case-insensitively. Unlike `vault_codec::row_identity`, a column the
/// record does not carry contributes an empty part, so a row missing one still matches its counterpart.
fn get_key(record: &CodecRecord, columns: &[&str]) -> String {
let parts: Vec<String> = columns.iter().map(|column| record.get(*column).filter(|v| !v.is_null()).map(identity_part).unwrap_or_default()).collect();
parts.join("\u{1f}")
}