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