levi_core/

rank.rs

//! Ranking for `levi next` (spec §Ranking).
//!
//! Eligible = open on this checkout ∧ every blocker closed on this checkout ∧
//! no live claim by someone else. Order: priority (P0 first) → transitive
//! unblock count (closing this frees the most open work) → age (oldest
//! first) → task id. Deterministic and explainable.

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

use chrono::{DateTime, Utc};

use crate::entities::Priority;
use crate::materialize::World;
use crate::resolve::{ResolvedStatus, Status};

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Identity {
    pub dev: String,
    pub machine: String,
    pub worktree: String,
}

#[derive(Debug, Clone)]
pub struct RankedTask {
    pub task_id: String,
    pub priority: Priority,
    pub unblocks: usize,
    pub created: String,
    pub reason: String,
}

/// Rank all eligible tasks, best first. `statuses` must contain a resolved
/// status for every task in `world`.
pub fn rank_next(
    world: &World,
    statuses: &BTreeMap<String, ResolvedStatus>,
    now: DateTime<Utc>,
    me: &Identity,
) -> Vec<RankedTask> {
    let is_open = |id: &str| {
        statuses
            .get(id)
            .map(|r| r.status == Status::Open)
            .unwrap_or(false)
    };

    // blocker -> directly blocked open tasks
    let mut blocks: HashMap<&str, Vec<&str>> = HashMap::new();
    // blocked -> blockers
    let mut blocked_by: HashMap<&str, Vec<&str>> = HashMap::new();
    for dep in world.deps.values() {
        // Deps referencing deleted tasks are ignored.
        if !world.tasks.contains_key(&*dep.blocker_task_id)
            || !world.tasks.contains_key(&*dep.blocked_task_id)
        {
            continue;
        }
        blocks
            .entry(&dep.blocker_task_id)
            .or_default()
            .push(&dep.blocked_task_id);
        blocked_by
            .entry(&dep.blocked_task_id)
            .or_default()
            .push(&dep.blocker_task_id);
    }

    let mut candidates: Vec<RankedTask> = Vec::new();
    let mut eligible_count = 0usize;
    for (id, task) in &world.tasks {
        if !is_open(id) {
            continue;
        }
        let all_blockers_closed = blocked_by
            .get(id.as_str())
            .map(|bs| bs.iter().all(|b| !is_open(b)))
            .unwrap_or(true);
        if !all_blockers_closed {
            continue;
        }
        if let Some(claim) = world.live_claim(id, now) {
            let mine =
                claim.dev == me.dev && claim.machine == me.machine && claim.worktree == me.worktree;
            if !mine {
                continue;
            }
        }
        eligible_count += 1;
        candidates.push(RankedTask {
            task_id: id.clone(),
            priority: task.priority,
            unblocks: transitive_unblocks(id, &blocks, &is_open),
            created: task.created.clone(),
            reason: String::new(),
        });
    }

    candidates.sort_by(|a, b| {
        (
            a.priority.rank(),
            std::cmp::Reverse(a.unblocks),
            a.created.as_str(),
            a.task_id.as_str(),
        )
            .cmp(&(
                b.priority.rank(),
                std::cmp::Reverse(b.unblocks),
                b.created.as_str(),
                b.task_id.as_str(),
            ))
    });

    for (i, c) in candidates.iter_mut().enumerate() {
        let mut parts = vec![c.priority.label().to_string()];
        if c.unblocks > 0 {
            parts.push(format!(
                "unblocks {} open task{}",
                c.unblocks,
                if c.unblocks == 1 { "" } else { "s" }
            ));
        }
        parts.push(if i == 0 {
            format!("ranked 1st of {eligible_count} eligible")
        } else {
            format!("ranked {} of {eligible_count} eligible", ordinal(i + 1))
        });
        c.reason = parts.join("; ");
    }
    candidates
}

/// Count open tasks transitively blocked by `id` (cycle-safe).
fn transitive_unblocks(
    id: &str,
    blocks: &HashMap<&str, Vec<&str>>,
    is_open: &impl Fn(&str) -> bool,
) -> usize {
    let mut seen: HashSet<&str> = HashSet::new();
    let mut stack: Vec<&str> = blocks.get(id).cloned().unwrap_or_default();
    let mut count = 0;
    while let Some(next) = stack.pop() {
        if next == id || !seen.insert(next) {
            continue;
        }
        if is_open(next) {
            count += 1;
        }
        if let Some(more) = blocks.get(next) {
            stack.extend(more);
        }
    }
    count
}

fn ordinal(n: usize) -> String {
    let suffix = match (n % 10, n % 100) {
        (1, 11) | (2, 12) | (3, 13) => "th",
        (1, _) => "st",
        (2, _) => "nd",
        (3, _) => "rd",
        _ => "th",
    };
    format!("{n}{suffix}")
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::entities::*;
    use crate::ids::{PrefixError, resolve_prefix, short_id};
    use crate::resolve::Resolution;

    fn me() -> Identity {
        Identity {
            dev: "me@x".into(),
            machine: "m1".into(),
            worktree: "/w1".into(),
        }
    }

    fn now() -> DateTime<Utc> {
        "2026-07-18T12:00:00Z".parse().unwrap()
    }

    fn world_with(tasks: &[(&str, Priority, &str)]) -> (World, BTreeMap<String, ResolvedStatus>) {
        let mut w = World::default();
        let mut statuses = BTreeMap::new();
        for (id, priority, created_at) in tasks {
            w.tasks.insert(
                id.to_string(),
                Task {
                    id: (*id).into(),
                    project_id: "p".into(),
                    title: format!("task {id}"),
                    body: String::new(),
                    priority: *priority,
                    labels: vec![],
                    created_by_dev: "d".into(),
                    created_by_machine: "m".into(),
                    created: created_at.to_string(),
                },
            );
            statuses.insert(
                id.to_string(),
                ResolvedStatus {
                    status: Status::Open,
                    resolution: Resolution::Exact,
                },
            );
        }
        (w, statuses)
    }

    fn dep(w: &mut World, blocker: &str, blocked: &str) {
        let id = dependency_id(blocker, blocked);
        w.deps.insert(
            id.clone(),
            Dependency {
                id: id.into(),
                project_id: "p".into(),
                blocker_task_id: blocker.into(),
                blocked_task_id: blocked.into(),
            },
        );
    }

    fn close(statuses: &mut BTreeMap<String, ResolvedStatus>, id: &str) {
        statuses.insert(
            id.to_string(),
            ResolvedStatus {
                status: Status::Closed,
                resolution: Resolution::Exact,
            },
        );
    }

    fn claim(w: &mut World, task: &str, dev: &str, machine: &str, worktree: &str, at: &str) {
        w.claims.insert(
            task.to_string(),
            Claim {
                id: task.into(),
                project_id: "p".into(),
                task_id: task.into(),
                dev: dev.into(),
                machine: machine.into(),
                worktree: worktree.into(),
                created: at.into(),
                ttl_secs: 86400,
            },
        );
    }

    #[test]
    fn priority_beats_unblock_count() {
        let (mut w, statuses) = world_with(&[
            ("aaaa", Priority::P1, "2026-07-01T00:00:00Z"),
            ("bbbb", Priority::P0, "2026-07-02T00:00:00Z"),
            ("cccc", Priority::P2, "2026-07-03T00:00:00Z"),
            ("dddd", Priority::P2, "2026-07-04T00:00:00Z"),
        ]);
        // aaaa unblocks two tasks; bbbb unblocks none but is P0.
        dep(&mut w, "aaaa", "cccc");
        dep(&mut w, "aaaa", "dddd");
        let ranked = rank_next(&w, &statuses, now(), &me());
        assert_eq!(ranked[0].task_id, "bbbb");
        assert_eq!(ranked[1].task_id, "aaaa");
        assert!(ranked[0].reason.starts_with("P0"));
    }

    #[test]
    fn unblock_count_beats_age() {
        let (mut w, statuses) = world_with(&[
            ("aaaa", Priority::P2, "2026-07-01T00:00:00Z"), // older
            ("bbbb", Priority::P2, "2026-07-02T00:00:00Z"), // newer but unblocks
            ("cccc", Priority::P2, "2026-07-03T00:00:00Z"),
        ]);
        dep(&mut w, "bbbb", "cccc");
        let ranked = rank_next(&w, &statuses, now(), &me());
        assert_eq!(ranked[0].task_id, "bbbb");
        assert!(ranked[0].reason.contains("unblocks 1 open task"));
    }

    #[test]
    fn transitive_unblocks_counts_chain_and_survives_cycles() {
        let (mut w, mut statuses) = world_with(&[
            ("aaaa", Priority::P2, "2026-07-01T00:00:00Z"),
            ("bbbb", Priority::P2, "2026-07-02T00:00:00Z"),
            ("cccc", Priority::P2, "2026-07-03T00:00:00Z"),
            ("dddd", Priority::P2, "2026-07-04T00:00:00Z"),
        ]);
        // aaaa -> bbbb -> cccc, and a cycle cccc -> aaaa; dddd closed.
        dep(&mut w, "aaaa", "bbbb");
        dep(&mut w, "bbbb", "cccc");
        dep(&mut w, "cccc", "aaaa");
        dep(&mut w, "aaaa", "dddd");
        close(&mut statuses, "dddd");
        let ranked = rank_next(&w, &statuses, now(), &me());
        // Everything is blocked by an open blocker except… aaaa is blocked by
        // cccc (open), bbbb by aaaa (open), cccc by bbbb (open): cycle makes
        // all ineligible. Break it: close cccc.
        assert!(ranked.is_empty());
        close(&mut statuses, "cccc");
        let ranked = rank_next(&w, &statuses, now(), &me());
        assert_eq!(ranked[0].task_id, "aaaa");
        // aaaa unblocks bbbb (open) transitively; cccc and dddd are closed.
        assert_eq!(ranked[0].unblocks, 1);
    }

    #[test]
    fn blocked_task_ineligible_until_blocker_closed() {
        let (mut w, mut statuses) = world_with(&[
            ("aaaa", Priority::P2, "2026-07-01T00:00:00Z"),
            ("bbbb", Priority::P0, "2026-07-02T00:00:00Z"),
        ]);
        dep(&mut w, "aaaa", "bbbb");
        let ranked = rank_next(&w, &statuses, now(), &me());
        assert_eq!(
            ranked
                .iter()
                .map(|r| r.task_id.as_str())
                .collect::<Vec<_>>(),
            ["aaaa"]
        );
        close(&mut statuses, "aaaa");
        let ranked = rank_next(&w, &statuses, now(), &me());
        assert_eq!(ranked[0].task_id, "bbbb");
    }

    #[test]
    fn foreign_live_claim_excludes_but_own_or_expired_does_not() {
        let (mut w, statuses) = world_with(&[
            ("aaaa", Priority::P2, "2026-07-01T00:00:00Z"),
            ("bbbb", Priority::P2, "2026-07-02T00:00:00Z"),
            ("cccc", Priority::P2, "2026-07-03T00:00:00Z"),
        ]);
        claim(
            &mut w,
            "aaaa",
            "other@x",
            "m2",
            "/w2",
            "2026-07-18T11:00:00Z",
        ); // foreign, live
        claim(&mut w, "bbbb", "me@x", "m1", "/w1", "2026-07-18T11:00:00Z"); // mine
        claim(
            &mut w,
            "cccc",
            "other@x",
            "m2",
            "/w2",
            "2026-07-01T00:00:00Z",
        ); // expired
        let ranked: Vec<_> = rank_next(&w, &statuses, now(), &me())
            .into_iter()
            .map(|r| r.task_id)
            .collect();
        assert_eq!(ranked, ["bbbb", "cccc"]);
    }

    #[test]
    fn short_ids_and_prefix_resolution() {
        let (w, _) = world_with(&[
            ("3f2a99aabbcc", Priority::P2, "2026-07-01T00:00:00Z"),
            ("3f2b00ddeeff", Priority::P2, "2026-07-02T00:00:00Z"),
        ]);
        assert_eq!(short_id(&w, "3f2a99aabbcc"), "lv-3f2a");
        assert_eq!(resolve_prefix(&w, "lv-3f2a").unwrap(), "3f2a99aabbcc");
        assert_eq!(resolve_prefix(&w, "3f2b").unwrap(), "3f2b00ddeeff");
        assert!(matches!(
            resolve_prefix(&w, "3f2"),
            Err(PrefixError::Ambiguous(..))
        ));
        assert!(matches!(
            resolve_prefix(&w, "9999"),
            Err(PrefixError::NotFound(..))
        ));
    }

    #[test]
    fn short_id_lengthens_on_collision() {
        let (w, _) = world_with(&[
            ("3f2a99aabbcc", Priority::P2, "2026-07-01T00:00:00Z"),
            ("3f2a99ffeedd", Priority::P2, "2026-07-02T00:00:00Z"),
        ]);
        assert_eq!(short_id(&w, "3f2a99aabbcc"), "lv-3f2a99aa");
    }
}