use std::collections::{HashMap, HashSet};
use crate::error::{MigratromError, Result};
use crate::types::Migration;
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 });
}
}
}
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) {
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() {
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() {
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(_)));
}
}