1//! Scoring engine for the `next` command.
2//!
3//! Scores ready tasks (open, no open blockers) using priority, effort,
4//! and the transitive downstream impact through the blocker graph.
5
6use std::collections::{HashMap, HashSet, VecDeque};
7
8/// Scoring mode for ranking tasks.
9#[derive(Debug, Clone, Copy, PartialEq, Eq)]
10pub enum Mode {
11 /// Critical path: downstream impact dominates, effort is dampened.
12 ///
13 /// `score = (downstream + 1.0) × priority_weight / effort_weight^0.25`
14 Impact,
15
16 /// Effort-weighted: effort dominates, downstream is dampened.
17 ///
18 /// `score = (downstream × 0.25 + 1.0) × priority_weight / effort_weight²`
19 Effort,
20}
21
22/// A lightweight snapshot of a task for scoring purposes.
23#[derive(Debug, Clone)]
24pub struct TaskNode {
25 pub id: String,
26 pub priority: i32,
27 pub effort: i32,
28}
29
30/// Scored result for a single task.
31#[derive(Debug, Clone)]
32pub struct ScoredTask {
33 pub id: String,
34 pub title: String,
35 pub priority: i32,
36 pub effort: i32,
37 pub score: f64,
38 pub downstream_score: f64,
39 pub priority_weight: f64,
40 pub effort_weight: f64,
41 /// Total number of open tasks transitively blocked by this one.
42 pub total_unblocked: usize,
43 /// Number of tasks directly blocked by this one.
44 pub direct_unblocked: usize,
45}
46
47/// Convert DB priority (1=high, 2=medium, 3=low) to a scoring weight
48/// where higher priority = higher weight.
49fn priority_weight(p: i32) -> f64 {
50 match p {
51 1 => 3.0,
52 2 => 2.0,
53 3 => 1.0,
54 _ => 2.0,
55 }
56}
57
58/// Convert DB effort (1=low, 2=medium, 3=high) to a scoring weight.
59fn effort_weight(e: i32) -> f64 {
60 match e {
61 1 => 1.0,
62 2 => 2.0,
63 3 => 3.0,
64 _ => 2.0,
65 }
66}
67
68/// Compute the transitive downstream score and count for a given task.
69///
70/// Walks the `blocks` adjacency list (task → set of tasks it blocks)
71/// starting from `start`, summing priority weights of all reachable nodes.
72/// Uses a visited set to handle any residual cycles defensively.
73fn downstream(
74 start: &str,
75 blocks: &HashMap<String, HashSet<String>>,
76 nodes: &HashMap<String, TaskNode>,
77) -> (f64, usize, usize) {
78 let mut score = 0.0;
79 let mut total = 0usize;
80 let mut direct = 0usize;
81
82 let mut visited = HashSet::new();
83 let mut queue = VecDeque::new();
84 visited.insert(start.to_string());
85
86 if let Some(dependents) = blocks.get(start) {
87 for dep in dependents {
88 if visited.insert(dep.clone()) {
89 queue.push_back(dep.clone());
90 direct += 1;
91 }
92 }
93 }
94
95 while let Some(current) = queue.pop_front() {
96 total += 1;
97 if let Some(node) = nodes.get(¤t) {
98 score += priority_weight(node.priority);
99 }
100 if let Some(dependents) = blocks.get(¤t) {
101 for dep in dependents {
102 if visited.insert(dep.clone()) {
103 queue.push_back(dep.clone());
104 }
105 }
106 }
107 }
108
109 (score, total, direct)
110}
111
112/// Score and rank ready tasks.
113///
114/// # Arguments
115/// * `open_tasks` — all open tasks (id, title, priority, effort)
116/// * `blocker_edges` — `(task_id, blocker_id)` pairs among open tasks
117/// * `exclude` — task IDs to exclude from candidates (still counted in
118/// downstream scores). Used to filter parent tasks that have open subtasks.
119/// * `mode` — scoring strategy
120/// * `limit` — maximum number of results to return
121pub fn rank(
122 open_tasks: &[(String, String, i32, i32)],
123 blocker_edges: &[(String, String)],
124 exclude: &HashSet<String>,
125 mode: Mode,
126 limit: usize,
127) -> Vec<ScoredTask> {
128 // Build node map.
129 let mut nodes: HashMap<String, TaskNode> = HashMap::new();
130 let mut titles: HashMap<String, String> = HashMap::new();
131 for (id, title, priority, effort) in open_tasks {
132 nodes.insert(
133 id.clone(),
134 TaskNode {
135 id: id.clone(),
136 priority: *priority,
137 effort: *effort,
138 },
139 );
140 titles.insert(id.clone(), title.clone());
141 }
142
143 // Build adjacency lists.
144 // blocked_by: task_id → set of blocker_ids (who blocks this task)
145 // blocks: blocker_id → set of task_ids (who this task blocks)
146 let mut blocked_by: HashMap<String, HashSet<String>> = HashMap::new();
147 let mut blocks: HashMap<String, HashSet<String>> = HashMap::new();
148
149 for (task_id, blocker_id) in blocker_edges {
150 // Only include edges where both ends are open tasks.
151 if nodes.contains_key(task_id) && nodes.contains_key(blocker_id) {
152 blocked_by
153 .entry(task_id.clone())
154 .or_default()
155 .insert(blocker_id.clone());
156 blocks
157 .entry(blocker_id.clone())
158 .or_default()
159 .insert(task_id.clone());
160 }
161 }
162
163 // Find ready tasks: open tasks with no open blockers, excluding
164 // parent tasks that still have open subtasks.
165 let ready: Vec<&TaskNode> = nodes
166 .values()
167 .filter(|n| !blocked_by.contains_key(&n.id) && !exclude.contains(&n.id))
168 .collect();
169
170 // Score each ready task.
171 let mut scored: Vec<ScoredTask> = ready
172 .iter()
173 .map(|node| {
174 let (ds, total_unblocked, direct_unblocked) = downstream(&node.id, &blocks, &nodes);
175 let pw = priority_weight(node.priority);
176 let ew = effort_weight(node.effort);
177
178 let score = match mode {
179 Mode::Impact => (ds + 1.0) * pw / ew.powf(0.25),
180 Mode::Effort => (ds * 0.25 + 1.0) * pw / (ew * ew),
181 };
182
183 ScoredTask {
184 id: node.id.clone(),
185 title: titles.get(&node.id).cloned().unwrap_or_default(),
186 priority: node.priority,
187 effort: node.effort,
188 score,
189 downstream_score: ds,
190 priority_weight: pw,
191 effort_weight: ew,
192 total_unblocked,
193 direct_unblocked,
194 }
195 })
196 .collect();
197
198 // Sort descending by score, then by id for stability.
199 scored.sort_by(|a, b| {
200 b.score
201 .partial_cmp(&a.score)
202 .unwrap_or(std::cmp::Ordering::Equal)
203 .then_with(|| a.id.cmp(&b.id))
204 });
205
206 scored.truncate(limit);
207 scored
208}
209
210#[cfg(test)]
211mod tests {
212 use super::*;
213
214 fn task(id: &str, title: &str, pri: i32, eff: i32) -> (String, String, i32, i32) {
215 (id.to_string(), title.to_string(), pri, eff)
216 }
217
218 fn edge(task_id: &str, blocker_id: &str) -> (String, String) {
219 (task_id.to_string(), blocker_id.to_string())
220 }
221
222 #[test]
223 fn single_task_no_deps() {
224 let tasks = vec![task("a", "Alpha", 1, 1)];
225 let result = rank(&tasks, &[], &HashSet::new(), Mode::Impact, 5);
226
227 assert_eq!(result.len(), 1);
228 assert_eq!(result[0].id, "a");
229 // (0 + 1.0) * 3.0 / 1.0^0.25 = 3.0
230 assert!((result[0].score - 3.0).abs() < f64::EPSILON);
231 assert_eq!(result[0].total_unblocked, 0);
232 assert_eq!(result[0].direct_unblocked, 0);
233 }
234
235 #[test]
236 fn blocker_scores_higher_than_leaf() {
237 // A blocks B. Both are ready-eligible but only A has no blockers.
238 // A is ready (blocks B), B is blocked.
239 let tasks = vec![task("a", "Blocker", 2, 2), task("b", "Blocked", 1, 1)];
240 let edges = vec![edge("b", "a")];
241 let result = rank(&tasks, &edges, &HashSet::new(), Mode::Impact, 5);
242
243 // Only A is ready.
244 assert_eq!(result.len(), 1);
245 assert_eq!(result[0].id, "a");
246 // downstream of A = priority_weight(B) = 3.0
247 // score = (3.0 + 1.0) * 2.0 / 2.0^0.25 = 8.0 / 1.1892 ≈ 6.727
248 let expected = (3.0 + 1.0) * 2.0 / 2.0_f64.powf(0.25);
249 assert!((result[0].score - expected).abs() < 1e-10);
250 assert_eq!(result[0].total_unblocked, 1);
251 assert_eq!(result[0].direct_unblocked, 1);
252 }
253
254 #[test]
255 fn transitive_downstream_counted() {
256 // A blocks B, B blocks C. Only A is ready.
257 let tasks = vec![
258 task("a", "Root", 2, 2),
259 task("b", "Mid", 2, 2),
260 task("c", "Leaf", 1, 1),
261 ];
262 let edges = vec![edge("b", "a"), edge("c", "b")];
263 let result = rank(&tasks, &edges, &HashSet::new(), Mode::Impact, 5);
264
265 assert_eq!(result.len(), 1);
266 assert_eq!(result[0].id, "a");
267 // downstream = pw(b) + pw(c) = 2.0 + 3.0 = 5.0
268 // score = (5.0 + 1.0) * 2.0 / 2.0^0.25
269 let expected = (5.0 + 1.0) * 2.0 / 2.0_f64.powf(0.25);
270 assert!((result[0].score - expected).abs() < 1e-10);
271 assert_eq!(result[0].total_unblocked, 2);
272 assert_eq!(result[0].direct_unblocked, 1);
273 }
274
275 #[test]
276 fn diamond_graph_no_double_counting() {
277 // A and B both block C. A and B are ready.
278 let tasks = vec![
279 task("a", "Left", 1, 1),
280 task("b", "Right", 2, 2),
281 task("c", "Sink", 1, 1),
282 ];
283 let edges = vec![edge("c", "a"), edge("c", "b")];
284 let result = rank(&tasks, &edges, &HashSet::new(), Mode::Impact, 5);
285
286 assert_eq!(result.len(), 2);
287 // Both A and B see C as downstream.
288 // A: downstream = pw(c) = 3.0, score = (3+1)*3/1^0.25 = 12.0
289 // B: downstream = pw(c) = 3.0, score = (3+1)*2/2^0.25
290 assert_eq!(result[0].id, "a");
291 assert!((result[0].score - 12.0).abs() < f64::EPSILON);
292 let expected_b = (3.0 + 1.0) * 2.0 / 2.0_f64.powf(0.25);
293 assert_eq!(result[1].id, "b");
294 assert!((result[1].score - expected_b).abs() < 1e-10);
295 }
296
297 #[test]
298 fn effort_mode_dampens_downstream() {
299 // A blocks B. A is ready.
300 let tasks = vec![
301 task("a", "Blocker", 1, 3), // high pri, high effort
302 task("b", "Blocked", 1, 1),
303 ];
304 let edges = vec![edge("b", "a")];
305
306 let impact = rank(&tasks, &edges, &HashSet::new(), Mode::Impact, 5);
307 let effort = rank(&tasks, &edges, &HashSet::new(), Mode::Effort, 5);
308
309 // Impact: (3.0 + 1.0) * 3.0 / 3.0^0.25
310 let expected_impact = (3.0 + 1.0) * 3.0 / 3.0_f64.powf(0.25);
311 assert!((impact[0].score - expected_impact).abs() < 1e-10);
312 // Effort: (3.0 * 0.25 + 1.0) * 3.0 / 9.0 = 1.75 * 3.0 / 9.0 ≈ 0.583
313 assert!((effort[0].score - (1.75 * 3.0 / 9.0)).abs() < f64::EPSILON);
314 }
315
316 #[test]
317 fn effort_mode_prefers_low_effort() {
318 // Two standalone tasks: A is high-effort, B is low-effort. Same priority.
319 let tasks = vec![task("a", "Heavy", 2, 3), task("b", "Light", 2, 1)];
320 let result = rank(&tasks, &[], &HashSet::new(), Mode::Effort, 5);
321
322 assert_eq!(result.len(), 2);
323 // B should rank higher (low effort).
324 assert_eq!(result[0].id, "b");
325 assert_eq!(result[1].id, "a");
326 }
327
328 #[test]
329 fn limit_truncates() {
330 let tasks = vec![
331 task("a", "A", 1, 1),
332 task("b", "B", 2, 2),
333 task("c", "C", 3, 3),
334 ];
335 let result = rank(&tasks, &[], &HashSet::new(), Mode::Impact, 2);
336 assert_eq!(result.len(), 2);
337 }
338
339 #[test]
340 fn empty_input() {
341 let result = rank(&[], &[], &HashSet::new(), Mode::Impact, 5);
342 assert!(result.is_empty());
343 }
344
345 #[test]
346 fn stable_sort_by_id() {
347 // Two tasks with identical scores should sort by id.
348 let tasks = vec![task("b", "Second", 2, 2), task("a", "First", 2, 2)];
349 let result = rank(&tasks, &[], &HashSet::new(), Mode::Impact, 5);
350 assert_eq!(result[0].id, "a");
351 assert_eq!(result[1].id, "b");
352 }
353
354 #[test]
355 fn excluded_tasks_not_candidates() {
356 // A and B are both standalone ready tasks, but A is excluded
357 // (simulating a parent with open subtasks).
358 let tasks = vec![task("a", "Parent", 1, 1), task("b", "Leaf", 2, 2)];
359 let exclude: HashSet<String> = ["a".to_string()].into();
360 let result = rank(&tasks, &[], &exclude, Mode::Impact, 5);
361
362 assert_eq!(result.len(), 1);
363 assert_eq!(result[0].id, "b");
364 }
365
366 #[test]
367 fn excluded_task_still_counted_in_downstream() {
368 // A blocks B (the excluded parent). B blocks C.
369 // A is ready. B is excluded but its downstream weight should still
370 // flow through the graph — A should see both B and C downstream.
371 let tasks = vec![
372 task("a", "Root", 2, 2),
373 task("b", "Parent", 1, 1),
374 task("c", "Leaf", 2, 2),
375 ];
376 let edges = vec![edge("b", "a"), edge("c", "b")];
377 let exclude: HashSet<String> = ["b".to_string()].into();
378 let result = rank(&tasks, &edges, &exclude, Mode::Impact, 5);
379
380 // Only A is ready (B is blocked and also excluded, C is blocked).
381 assert_eq!(result.len(), 1);
382 assert_eq!(result[0].id, "a");
383 // Downstream still includes B and C.
384 assert_eq!(result[0].total_unblocked, 2);
385 }
386
387 #[test]
388 fn impact_prefers_priority_over_effort_for_standalone() {
389 // Regression: high-pri/high-eff must rank above medium-pri/low-eff
390 // in impact mode. Previously effort canceled priority entirely.
391 let tasks = vec![
392 task("a", "HighPriHighEff", 1, 3),
393 task("b", "MedPriLowEff", 2, 1),
394 ];
395 let result = rank(&tasks, &[], &HashSet::new(), Mode::Impact, 5);
396 assert_eq!(result[0].id, "a");
397 }
398
399 #[test]
400 fn parent_with_all_children_closed_remains_candidate() {
401 // A standalone task that would be in the open_tasks list but NOT
402 // in the exclude set (because all its children are closed, the
403 // caller wouldn't put it there). Verify it's still a candidate.
404 let tasks = vec![task("a", "Parent done kids", 1, 1)];
405 let result = rank(&tasks, &[], &HashSet::new(), Mode::Impact, 5);
406
407 assert_eq!(result.len(), 1);
408 assert_eq!(result[0].id, "a");
409 }
410}