migratrom 0.2.0

Declarative, self-verifying database migrations (core engine).
Documentation
//! Dependency resolution for the migration DAG.
//!
//! [`plan_order`] validates the graph and returns the pending migrations in the
//! order they must run: by depth (parents before children), then by id.

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

use crate::error::{MigratromError, Result};
use crate::types::Migration;

/// Validate the migration graph and return the unapplied migrations in order.
///
/// Validation covers duplicate ids, root structure (exactly one root on an empty
/// history; no brand-new roots otherwise), missing parents, and cycles.
pub fn plan_order(migrations: &[Migration], applied_ids: &HashSet<i64>) -> Result<Vec<Migration>> {
    let mut by_id: HashMap<i64, &Migration> = HashMap::with_capacity(migrations.len());
    for m in migrations {
        if by_id.insert(m.id, m).is_some() {
            return Err(MigratromError::DuplicateMigrationId(m.id));
        }
    }

    let roots: Vec<&Migration> = migrations
        .iter()
        .filter(|m| m.parent_id.is_none())
        .collect();
    if applied_ids.is_empty() {
        if roots.is_empty() {
            return Err(MigratromError::MissingRoot);
        }
        if roots.len() > 1 {
            return Err(MigratromError::MultipleRoots(
                roots.iter().map(|r| r.id).collect(),
            ));
        }
    } else {
        let new_roots: Vec<i64> = roots
            .iter()
            .filter(|r| !applied_ids.contains(&r.id))
            .map(|r| r.id)
            .collect();
        if !new_roots.is_empty() {
            return Err(MigratromError::MultipleRoots(new_roots));
        }
    }

    for m in migrations {
        if let Some(parent) = m.parent_id {
            if !by_id.contains_key(&parent) && !applied_ids.contains(&parent) {
                return Err(MigratromError::MissingParent { id: m.id, parent });
            }
        }
    }

    // Depth, memoized, with a path set for cycle detection. Parents found only in
    // history act as depth-0 anchors for their in-batch children.
    let mut depth_cache: HashMap<i64, usize> = HashMap::new();
    for m in migrations {
        depth(m.id, &by_id, &mut depth_cache, &mut Vec::new())?;
    }

    let mut pending: Vec<Migration> = migrations
        .iter()
        .filter(|m| !applied_ids.contains(&m.id))
        .cloned()
        .collect();
    pending.sort_by(|a, b| {
        let da = depth_cache.get(&a.id).copied().unwrap_or(0);
        let db = depth_cache.get(&b.id).copied().unwrap_or(0);
        da.cmp(&db).then(a.id.cmp(&b.id))
    });
    Ok(pending)
}

fn depth(
    id: i64,
    by_id: &HashMap<i64, &Migration>,
    cache: &mut HashMap<i64, usize>,
    path: &mut Vec<i64>,
) -> Result<usize> {
    if let Some(&cached) = cache.get(&id) {
        return Ok(cached);
    }
    if path.contains(&id) {
        let mut cycle = path.clone();
        cycle.push(id);
        return Err(MigratromError::CycleDetected(cycle));
    }
    path.push(id);

    let computed = match by_id.get(&id) {
        // Parent-only-in-history: anchor children at depth 0.
        None => 0,
        Some(m) => match m.parent_id {
            None => 0,
            Some(parent) => depth(parent, by_id, cache, path)? + 1,
        },
    };

    path.pop();
    cache.insert(id, computed);
    Ok(computed)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn migration(id: i64, parent_id: Option<i64>) -> Migration {
        Migration::new(id, parent_id, Vec::new())
    }

    fn ids(ms: &[Migration]) -> Vec<i64> {
        ms.iter().map(|m| m.id).collect()
    }

    #[test]
    fn orders_parent_before_child() {
        let out = plan_order(
            &[migration(2, Some(1)), migration(1, None)],
            &HashSet::new(),
        )
        .unwrap();
        assert_eq!(ids(&out), vec![1, 2]);
    }

    #[test]
    fn ties_break_by_id() {
        let ms = [
            migration(3, Some(1)),
            migration(2, Some(1)),
            migration(1, None),
        ];
        let out = plan_order(&ms, &HashSet::new()).unwrap();
        assert_eq!(ids(&out), vec![1, 2, 3]);
    }

    #[test]
    fn excludes_already_applied() {
        let ms = [migration(1, None), migration(2, Some(1))];
        let applied = HashSet::from([1]);
        let out = plan_order(&ms, &applied).unwrap();
        assert_eq!(ids(&out), vec![2]);
    }

    #[test]
    fn duplicate_id_is_rejected() {
        let err =
            plan_order(&[migration(1, None), migration(1, None)], &HashSet::new()).unwrap_err();
        assert!(matches!(err, MigratromError::DuplicateMigrationId(1)));
    }

    #[test]
    fn empty_history_needs_exactly_one_root() {
        // A batch with no root migration is rejected before any parent check.
        assert!(matches!(
            plan_order(&[migration(2, Some(1))], &HashSet::new()),
            Err(MigratromError::MissingRoot)
        ));
        assert!(matches!(
            plan_order(&[migration(1, None), migration(2, None)], &HashSet::new()),
            Err(MigratromError::MultipleRoots(_))
        ));
    }

    #[test]
    fn missing_parent_is_rejected() {
        let err = plan_order(
            &[migration(1, None), migration(2, Some(9))],
            &HashSet::new(),
        )
        .unwrap_err();
        assert!(matches!(
            err,
            MigratromError::MissingParent { id: 2, parent: 9 }
        ));
    }

    #[test]
    fn cycle_is_detected() {
        // A valid root keeps the root check happy; 2 <-> 3 form the cycle.
        let ms = [
            migration(1, None),
            migration(2, Some(3)),
            migration(3, Some(2)),
        ];
        let err = plan_order(&ms, &HashSet::new()).unwrap_err();
        assert!(matches!(err, MigratromError::CycleDetected(_)));
    }
}