ainl-mission 0.1.0

//! Within-layer parallel groups via file-overlap greedy coloring (`touches_files`).

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

use ainl_contracts::{Feature, FeatureId};
use thiserror::Error;

/// Scheduler input error.
#[derive(Debug, Error, PartialEq, Eq)]
pub enum SchedulerError {
    #[error("max_parallelism must be >= 1")]
    InvalidMaxParallelism,
    #[error("empty feature layer")]
    EmptyLayer,
}

/// Returns true when two file path lists conflict (exact match or directory prefix overlap).
pub fn files_overlap(a: &[String], b: &[String]) -> bool {
    for pa in a {
        let pa = pa.trim();
        if pa.is_empty() {
            continue;
        }
        for pb in b {
            let pb = pb.trim();
            if pb.is_empty() {
                continue;
            }
            if pa == pb {
                return true;
            }
            if path_prefix_overlap(pa, pb) {
                return true;
            }
        }
    }
    false
}

fn path_prefix_overlap(a: &str, b: &str) -> bool {
    if a == b {
        return true;
    }
    let a_slash = a.ends_with('/');
    let b_slash = b.ends_with('/');
    if a.starts_with(b) {
        return b_slash || a.as_bytes().get(b.len()) == Some(&b'/');
    }
    if b.starts_with(a) {
        return a_slash || b.as_bytes().get(a.len()) == Some(&b'/');
    }
    false
}

/// Partition one topological layer into conflict-free parallel groups (greedy coloring).
///
/// Features within a group may run concurrently; groups must run sequentially in order.
/// Respects `max_parallelism` as an upper bound on group size (split oversized color classes).
pub fn partition_layer(
    layer: &[Feature],
    max_parallelism: usize,
) -> Result<Vec<Vec<FeatureId>>, SchedulerError> {
    if max_parallelism == 0 {
        return Err(SchedulerError::InvalidMaxParallelism);
    }
    if layer.is_empty() {
        return Err(SchedulerError::EmptyLayer);
    }

    let mut colors: HashMap<usize, Vec<usize>> = HashMap::new();
    let mut assigned: Vec<Option<usize>> = vec![None; layer.len()];

    for (i, fi) in layer.iter().enumerate() {
        let mut used_colors = HashSet::new();
        for (j, fj) in layer.iter().enumerate() {
            if i == j {
                continue;
            }
            if let Some(c) = assigned[j] {
                if files_overlap(&fi.touches_files, &fj.touches_files) {
                    used_colors.insert(c);
                }
            }
        }
        let mut color = 0usize;
        while used_colors.contains(&color) {
            color += 1;
        }
        assigned[i] = Some(color);
        colors.entry(color).or_default().push(i);
    }

    let mut color_keys: Vec<usize> = colors.keys().copied().collect();
    color_keys.sort_unstable();

    let mut groups = Vec::new();
    for color in color_keys {
        let indices = &colors[&color];
        let mut chunk: Vec<FeatureId> = indices
            .iter()
            .map(|&idx| layer[idx].feature_id.clone())
            .collect();
        chunk.sort_by(|a, b| a.as_str().cmp(b.as_str()));

        while !chunk.is_empty() {
            let take = chunk.len().min(max_parallelism);
            let (head, tail) = chunk.split_at(take);
            groups.push(head.to_vec());
            chunk = tail.to_vec();
        }
    }

    Ok(groups)
}

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

    fn feat(id: &str, files: &[&str]) -> Feature {
        Feature {
            feature_id: FeatureId(id.into()),
            description: id.into(),
            status: FeatureStatus::Pending,
            milestone: None,
            skill_name: None,
            touches_files: files.iter().map(|f| (*f).into()).collect(),
            preconditions: vec![],
            expected_behavior: vec![],
            verification_steps: vec![],
            fulfills: vec![],
            snapshot: None,
        }
    }

    #[test]
    fn exact_path_overlap() {
        assert!(files_overlap(&["src/a.rs".into()], &["src/a.rs".into()]));
    }

    #[test]
    fn prefix_overlap_directory() {
        assert!(files_overlap(&["src/".into()], &["src/lib.rs".into()]));
        assert!(files_overlap(&["src/lib.rs".into()], &["src/".into()]));
    }

    #[test]
    fn disjoint_paths_no_overlap() {
        assert!(!files_overlap(&["src/a.rs".into()], &["docs/b.md".into()]));
    }

    #[test]
    fn partition_non_overlapping_single_group() {
        let layer = vec![feat("a", &["src/a.rs"]), feat("b", &["src/b.rs"])];
        let groups = partition_layer(&layer, 4).unwrap();
        assert_eq!(groups.len(), 1);
        assert_eq!(groups[0].len(), 2);
    }

    #[test]
    fn partition_overlapping_separate_groups() {
        let layer = vec![
            feat("a", &["src/shared.rs"]),
            feat("b", &["src/shared.rs"]),
        ];
        let groups = partition_layer(&layer, 4).unwrap();
        assert_eq!(groups.len(), 2);
        assert_eq!(groups[0].len(), 1);
        assert_eq!(groups[1].len(), 1);
    }

    #[test]
    fn max_parallelism_splits_color_class() {
        let layer = (0..5)
            .map(|i| feat(&format!("f{i}"), &[&format!("disjoint/{i}.rs")]))
            .collect::<Vec<_>>();
        let groups = partition_layer(&layer, 2).unwrap();
        assert_eq!(groups.len(), 3);
        assert!(groups.iter().all(|g| g.len() <= 2));
    }
}