intent_engine/
plan_validation.rs

1//! Pure validation functions for plan execution.
2//!
3//! Shared between SQLite `PlanExecutor` and Neo4j `Neo4jPlanExecutor`.
4//! All functions are stateless — no database access.
5
6use crate::error::{IntentError, Result};
7use crate::plan::{FlatTask, TaskStatus};
8use std::collections::{HashMap, HashSet};
9
10/// Validate that all dependency references exist within the plan.
11pub fn validate_dependencies(flat_tasks: &[FlatTask]) -> Result<()> {
12    let task_names: HashSet<&str> = flat_tasks
13        .iter()
14        .filter_map(|t| t.name.as_deref())
15        .collect();
16
17    for task in flat_tasks {
18        for dep_name in &task.depends_on {
19            if !task_names.contains(dep_name.as_str()) {
20                let task_name = task.name.as_deref().unwrap_or("<unknown>");
21                return Err(IntentError::InvalidInput(format!(
22                    "Task '{}' depends on '{}', but '{}' is not in the plan",
23                    task_name, dep_name, dep_name
24                )));
25            }
26        }
27    }
28
29    Ok(())
30}
31
32/// Validate that at most one task in the batch has status='doing'.
33pub fn validate_batch_single_doing(flat_tasks: &[FlatTask]) -> Result<()> {
34    let doing_tasks: Vec<&FlatTask> = flat_tasks
35        .iter()
36        .filter(|task| matches!(task.status, Some(TaskStatus::Doing)))
37        .collect();
38
39    if doing_tasks.len() > 1 {
40        let names: Vec<&str> = doing_tasks
41            .iter()
42            .map(|t| t.name.as_deref().unwrap_or("<unknown>"))
43            .collect();
44        return Err(IntentError::InvalidInput(format!(
45            "Batch single doing constraint violated: only one task per batch can have status='doing'. Found: {}",
46            names.join(", ")
47        )));
48    }
49
50    Ok(())
51}
52
53/// Detect circular dependencies using Tarjan's SCC algorithm.
54pub fn detect_circular_dependencies(flat_tasks: &[FlatTask]) -> Result<()> {
55    if flat_tasks.is_empty() {
56        return Ok(());
57    }
58
59    let name_to_idx: HashMap<&str, usize> = flat_tasks
60        .iter()
61        .enumerate()
62        .filter_map(|(i, t)| t.name.as_ref().map(|n| (n.as_str(), i)))
63        .collect();
64
65    // Build adjacency list
66    let mut graph: Vec<Vec<usize>> = vec![Vec::new(); flat_tasks.len()];
67    for (idx, task) in flat_tasks.iter().enumerate() {
68        for dep_name in &task.depends_on {
69            if let Some(dep_idx) = name_to_idx.get(dep_name.as_str()) {
70                graph[idx].push(*dep_idx);
71            }
72        }
73    }
74
75    // Check self-loops first
76    for task in flat_tasks {
77        if let Some(name) = &task.name {
78            if task.depends_on.contains(name) {
79                return Err(IntentError::InvalidInput(format!(
80                    "Circular dependency detected: task '{}' depends on itself",
81                    name
82                )));
83            }
84        }
85    }
86
87    // Tarjan's SCC
88    let sccs = tarjan_scc(&graph);
89    for scc in sccs {
90        if scc.len() > 1 {
91            let cycle_names: Vec<&str> = scc
92                .iter()
93                .map(|&idx| flat_tasks[idx].name.as_deref().unwrap_or("<unknown>"))
94                .collect();
95            return Err(IntentError::InvalidInput(format!(
96                "Circular dependency detected: {}",
97                cycle_names.join(" → ")
98            )));
99        }
100    }
101
102    Ok(())
103}
104
105/// Tarjan's algorithm for finding strongly connected components.
106///
107/// Returns a list of SCCs, where each SCC is a list of node indices.
108/// A cycle exists if any SCC has more than one node.
109pub fn tarjan_scc(graph: &[Vec<usize>]) -> Vec<Vec<usize>> {
110    let n = graph.len();
111    let mut index_counter = 0;
112    let mut stack = Vec::new();
113    let mut on_stack = vec![false; n];
114    let mut index = vec![usize::MAX; n];
115    let mut lowlink = vec![0; n];
116    let mut result = Vec::new();
117
118    #[allow(clippy::too_many_arguments)]
119    fn strongconnect(
120        v: usize,
121        graph: &[Vec<usize>],
122        index_counter: &mut usize,
123        stack: &mut Vec<usize>,
124        on_stack: &mut Vec<bool>,
125        index: &mut Vec<usize>,
126        lowlink: &mut Vec<usize>,
127        result: &mut Vec<Vec<usize>>,
128    ) {
129        index[v] = *index_counter;
130        lowlink[v] = *index_counter;
131        *index_counter += 1;
132        stack.push(v);
133        on_stack[v] = true;
134
135        for &w in &graph[v] {
136            if index[w] == usize::MAX {
137                strongconnect(
138                    w,
139                    graph,
140                    index_counter,
141                    stack,
142                    on_stack,
143                    index,
144                    lowlink,
145                    result,
146                );
147                lowlink[v] = lowlink[v].min(lowlink[w]);
148            } else if on_stack[w] {
149                lowlink[v] = lowlink[v].min(index[w]);
150            }
151        }
152
153        if lowlink[v] == index[v] {
154            let mut component = Vec::new();
155            loop {
156                let w = stack.pop().unwrap();
157                on_stack[w] = false;
158                component.push(w);
159                if w == v {
160                    break;
161                }
162            }
163            result.push(component);
164        }
165    }
166
167    for v in 0..n {
168        if index[v] == usize::MAX {
169            strongconnect(
170                v,
171                graph,
172                &mut index_counter,
173                &mut stack,
174                &mut on_stack,
175                &mut index,
176                &mut lowlink,
177                &mut result,
178            );
179        }
180    }
181
182    result
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188
189    #[test]
190    fn test_validate_batch_single_doing_ok() {
191        let tasks = vec![
192            FlatTask {
193                name: Some("A".to_string()),
194                status: Some(TaskStatus::Doing),
195                ..Default::default()
196            },
197            FlatTask {
198                name: Some("B".to_string()),
199                status: Some(TaskStatus::Todo),
200                ..Default::default()
201            },
202        ];
203        assert!(validate_batch_single_doing(&tasks).is_ok());
204    }
205
206    #[test]
207    fn test_validate_batch_single_doing_violation() {
208        let tasks = vec![
209            FlatTask {
210                name: Some("A".to_string()),
211                status: Some(TaskStatus::Doing),
212                ..Default::default()
213            },
214            FlatTask {
215                name: Some("B".to_string()),
216                status: Some(TaskStatus::Doing),
217                ..Default::default()
218            },
219        ];
220        assert!(validate_batch_single_doing(&tasks).is_err());
221    }
222
223    #[test]
224    fn test_validate_batch_single_doing_zero() {
225        let tasks = vec![FlatTask {
226            name: Some("A".to_string()),
227            status: Some(TaskStatus::Todo),
228            ..Default::default()
229        }];
230        assert!(validate_batch_single_doing(&tasks).is_ok());
231    }
232
233    #[test]
234    fn test_validate_dependencies_ok() {
235        let tasks = vec![
236            FlatTask {
237                name: Some("A".to_string()),
238                depends_on: vec!["B".to_string()],
239                ..Default::default()
240            },
241            FlatTask {
242                name: Some("B".to_string()),
243                ..Default::default()
244            },
245        ];
246        assert!(validate_dependencies(&tasks).is_ok());
247    }
248
249    #[test]
250    fn test_validate_dependencies_missing() {
251        let tasks = vec![FlatTask {
252            name: Some("A".to_string()),
253            depends_on: vec!["NonExistent".to_string()],
254            ..Default::default()
255        }];
256        let err = validate_dependencies(&tasks).unwrap_err();
257        assert!(err.to_string().contains("NonExistent"));
258    }
259
260    #[test]
261    fn test_validate_dependencies_empty() {
262        assert!(validate_dependencies(&[]).is_ok());
263    }
264
265    #[test]
266    fn test_detect_circular_no_cycle() {
267        let tasks = vec![
268            FlatTask {
269                name: Some("A".to_string()),
270                depends_on: vec!["B".to_string()],
271                ..Default::default()
272            },
273            FlatTask {
274                name: Some("B".to_string()),
275                ..Default::default()
276            },
277        ];
278        assert!(detect_circular_dependencies(&tasks).is_ok());
279    }
280
281    #[test]
282    fn test_detect_circular_self_loop() {
283        let tasks = vec![FlatTask {
284            name: Some("A".to_string()),
285            depends_on: vec!["A".to_string()],
286            ..Default::default()
287        }];
288        let err = detect_circular_dependencies(&tasks).unwrap_err();
289        assert!(err.to_string().contains("depends on itself"));
290    }
291
292    #[test]
293    fn test_detect_circular_two_node_cycle() {
294        let tasks = vec![
295            FlatTask {
296                name: Some("A".to_string()),
297                depends_on: vec!["B".to_string()],
298                ..Default::default()
299            },
300            FlatTask {
301                name: Some("B".to_string()),
302                depends_on: vec!["A".to_string()],
303                ..Default::default()
304            },
305        ];
306        assert!(detect_circular_dependencies(&tasks).is_err());
307    }
308
309    #[test]
310    fn test_detect_circular_three_node_cycle() {
311        let tasks = vec![
312            FlatTask {
313                name: Some("A".to_string()),
314                depends_on: vec!["B".to_string()],
315                ..Default::default()
316            },
317            FlatTask {
318                name: Some("B".to_string()),
319                depends_on: vec!["C".to_string()],
320                ..Default::default()
321            },
322            FlatTask {
323                name: Some("C".to_string()),
324                depends_on: vec!["A".to_string()],
325                ..Default::default()
326            },
327        ];
328        assert!(detect_circular_dependencies(&tasks).is_err());
329    }
330
331    #[test]
332    fn test_detect_circular_empty() {
333        assert!(detect_circular_dependencies(&[]).is_ok());
334    }
335
336    #[test]
337    fn test_tarjan_scc_no_cycle() {
338        let graph = vec![vec![1], vec![]]; // A → B
339        let sccs = tarjan_scc(&graph);
340        assert!(sccs.iter().all(|scc| scc.len() == 1));
341    }
342
343    #[test]
344    fn test_tarjan_scc_with_cycle() {
345        let graph = vec![vec![1], vec![0]]; // A → B → A
346        let sccs = tarjan_scc(&graph);
347        assert!(sccs.iter().any(|scc| scc.len() > 1));
348    }
349
350    #[test]
351    fn test_tarjan_scc_empty() {
352        let graph: Vec<Vec<usize>> = vec![];
353        let sccs = tarjan_scc(&graph);
354        assert!(sccs.is_empty());
355    }
356
357    #[test]
358    fn test_tarjan_scc_disconnected() {
359        let graph = vec![vec![], vec![]]; // A, B (no edges)
360        let sccs = tarjan_scc(&graph);
361        assert_eq!(sccs.len(), 2);
362        assert!(sccs.iter().all(|scc| scc.len() == 1));
363    }
364}
intent_engine/plan_validation.rs

intent_engine/
plan_validation.rs
