regista 0.5.0

🎬 AI agent director — state-machine-driven pipeline for pi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

//! Grafo de dependencias entre historias.
//!
//! Permite detectar ciclos (dependencias circulares), calcular
//! el conteo de referencias inversas (cuántas historias desbloquea cada una),
//! y determinar si una historia bloqueada puede desbloquearse.

use crate::story::Story;
use std::collections::{HashMap, HashSet};

/// Grafo dirigido de dependencias: `bloqueador → bloqueados`.
///
/// Las aristas van del bloqueador a la historia bloqueada.
/// Ejemplo: si STORY-002 depende de STORY-001, hay arista 001→002.
#[derive(Debug, Clone, Default)]
pub struct DependencyGraph {
    /// Para cada historia, las historias que dependen de ella.
    forward: HashMap<String, Vec<String>>,
    /// Para cada historia, las historias de las que depende.
    reverse: HashMap<String, Vec<String>>,
}

impl DependencyGraph {
    /// Construye el grafo a partir de una lista de historias.
    pub fn from_stories(stories: &[Story]) -> Self {
        let mut graph = Self::default();

        for story in stories {
            // Asegurar que toda historia tenga entrada (aunque no tenga dependencias)
            graph.forward.entry(story.id.clone()).or_default();
            graph.reverse.entry(story.id.clone()).or_default();

            for blocker in &story.blockers {
                graph
                    .forward
                    .entry(blocker.clone())
                    .or_default()
                    .push(story.id.clone());
                graph
                    .reverse
                    .entry(story.id.clone())
                    .or_default()
                    .push(blocker.clone());
            }
        }

        graph
    }

    /// Cuántas historias bloquea directamente esta historia.
    pub fn blocks_count(&self, story_id: &str) -> usize {
        self.forward.get(story_id).map(|v| v.len()).unwrap_or(0)
    }

    /// IDs de historias bloqueadas por esta historia.
    #[allow(dead_code)]
    pub fn blocked_by_me(&self, story_id: &str) -> Vec<&str> {
        self.forward
            .get(story_id)
            .map(|v| v.iter().map(|s| s.as_str()).collect())
            .unwrap_or_default()
    }

    /// Detecta si existe un ciclo que incluya a `story_id`.
    ///
    /// Usa DFS con colores: 0 = no visitado, 1 = en pila, 2 = procesado.
    pub fn has_cycle_from(&self, story_id: &str) -> bool {
        let mut color: HashMap<&str, u8> = self.forward.keys().map(|k| (k.as_str(), 0u8)).collect();

        self.dfs_has_cycle(story_id, &mut color)
    }

    /// Detecta si existe ALGÚN ciclo en todo el grafo.
    #[allow(dead_code)]
    pub fn has_any_cycle(&self) -> bool {
        let mut color: HashMap<&str, u8> = self.forward.keys().map(|k| (k.as_str(), 0u8)).collect();

        for node in self.forward.keys() {
            if color.get(node.as_str()) == Some(&0) && self.dfs_has_cycle(node, &mut color) {
                return true;
            }
        }
        false
    }

    fn dfs_has_cycle(&self, node: &str, color: &mut HashMap<&str, u8>) -> bool {
        *color.get_mut(node).unwrap() = 1; // en pila

        if let Some(neighbors) = self.forward.get(node) {
            for neighbor in neighbors {
                let neighbor_color = *color.get(neighbor.as_str()).unwrap_or(&0);
                if neighbor_color == 1 {
                    return true; // ciclo detectado
                }
                if neighbor_color == 0 && self.dfs_has_cycle(neighbor, color) {
                    return true;
                }
            }
        }

        *color.get_mut(node).unwrap() = 2; // procesado
        false
    }

    /// Encuentra los IDs de todas las historias que forman parte de un ciclo.
    #[allow(dead_code)]
    pub fn find_cycle_members(&self) -> HashSet<String> {
        let mut color: HashMap<&str, u8> = self.forward.keys().map(|k| (k.as_str(), 0u8)).collect();

        let mut in_stack = HashSet::new();
        let mut cycle_members = HashSet::new();

        for node in self.forward.keys() {
            if color.get(node.as_str()) == Some(&0) {
                self.dfs_find_cycle(node, &mut color, &mut in_stack, &mut cycle_members);
            }
        }

        cycle_members
    }

    #[allow(dead_code)]
    fn dfs_find_cycle(
        &self,
        node: &str,
        color: &mut HashMap<&str, u8>,
        in_stack: &mut HashSet<String>,
        cycle_members: &mut HashSet<String>,
    ) {
        *color.get_mut(node).unwrap() = 1;
        in_stack.insert(node.to_string());

        if let Some(neighbors) = self.forward.get(node) {
            for neighbor in neighbors {
                let neighbor_color = *color.get(neighbor.as_str()).unwrap_or(&0);
                if neighbor_color == 1 {
                    // Encontramos un ciclo: marcamos todo lo que está en la pila
                    cycle_members.extend(in_stack.iter().cloned());
                } else if neighbor_color == 0 {
                    self.dfs_find_cycle(neighbor, color, in_stack, cycle_members);
                }
            }
        }

        in_stack.remove(node);
        *color.get_mut(node).unwrap() = 2;
    }
}

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

    fn story(id: &str, blockers: &[&str]) -> Story {
        Story {
            id: id.to_string(),
            path: format!("stories/{id}.md").into(),
            status: crate::state::Status::Blocked,
            epic: None,
            blockers: blockers.iter().map(|s| s.to_string()).collect(),
            last_rejection: None,
            raw_content: String::new(),
        }
    }

    #[test]
    fn no_cycle_linear_chain() {
        let stories = vec![
            story("STORY-001", &[]),
            story("STORY-002", &["STORY-001"]),
            story("STORY-003", &["STORY-002"]),
        ];
        let graph = DependencyGraph::from_stories(&stories);
        assert!(!graph.has_any_cycle());
        assert!(!graph.has_cycle_from("STORY-001"));
        assert!(!graph.has_cycle_from("STORY-003"));
    }

    #[test]
    fn cycle_two_nodes() {
        let stories = vec![
            story("STORY-001", &["STORY-002"]),
            story("STORY-002", &["STORY-001"]),
        ];
        let graph = DependencyGraph::from_stories(&stories);
        assert!(graph.has_any_cycle());
        assert!(graph.has_cycle_from("STORY-001"));
        assert!(graph.has_cycle_from("STORY-002"));
    }

    #[test]
    fn cycle_three_nodes() {
        let stories = vec![
            story("STORY-001", &["STORY-003"]),
            story("STORY-002", &["STORY-001"]),
            story("STORY-003", &["STORY-002"]),
        ];
        let graph = DependencyGraph::from_stories(&stories);
        assert!(graph.has_any_cycle());

        let members = graph.find_cycle_members();
        assert!(members.len() >= 3);
        assert!(members.contains("STORY-001"));
        assert!(members.contains("STORY-002"));
        assert!(members.contains("STORY-003"));
    }

    #[test]
    fn blocks_count_works() {
        let stories = vec![
            story("STORY-001", &[]),
            story("STORY-002", &["STORY-001"]),
            story("STORY-003", &["STORY-001"]),
        ];
        let graph = DependencyGraph::from_stories(&stories);
        assert_eq!(graph.blocks_count("STORY-001"), 2);
        assert_eq!(graph.blocks_count("STORY-002"), 0);
    }
}