nika_core/ast/analyzed/
ids.rs

1//! Interned identifiers for the Analyzed AST.
2//!
3//! These are u32 indices that reference into lookup tables,
4//! providing O(1) comparison and hashing while keeping string
5//! data deduplicated.
6
7use rustc_hash::FxHashMap;
8use std::fmt;
9
10/// Interned task identifier.
11///
12/// Tasks are identified by a u32 index into the workflow's task table.
13/// This enables O(1) comparison and efficient storage.
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
15pub struct TaskId(pub u32);
16
17impl TaskId {
18    /// Create a new task ID.
19    pub const fn new(index: u32) -> Self {
20        Self(index)
21    }
22
23    /// Get the raw index.
24    pub const fn index(self) -> u32 {
25        self.0
26    }
27}
28
29impl fmt::Display for TaskId {
30    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
31        write!(f, "task#{}", self.0)
32    }
33}
34
35/// Task name lookup table.
36///
37/// Bidirectional mapping between task names and TaskIds.
38/// Uses HashMap for O(1) name→id lookup.
39#[derive(Debug, Clone, Default)]
40pub struct TaskTable {
41    /// Task names indexed by TaskId.
42    names: Vec<String>,
43    /// Reverse lookup (name → TaskId) for O(1) lookup.
44    index: FxHashMap<String, TaskId>,
45}
46
47impl TaskTable {
48    /// Create a new empty task table.
49    pub fn new() -> Self {
50        Self::default()
51    }
52
53    /// Insert a task name, returning its ID.
54    ///
55    /// Does NOT check for duplicates - use `try_insert()` for safe insertion.
56    pub fn insert(&mut self, name: &str) -> TaskId {
57        let id = TaskId::new(self.names.len() as u32);
58        self.names.push(name.to_string());
59        self.index.insert(name.to_string(), id);
60        id
61    }
62
63    /// Try to insert a task name, returning None if duplicate.
64    ///
65    /// Returns `Some(TaskId)` on success, `None` if name already exists.
66    pub fn try_insert(&mut self, name: &str) -> Option<TaskId> {
67        if self.index.contains_key(name) {
68            None
69        } else {
70            Some(self.insert(name))
71        }
72    }
73
74    /// Check if a task name exists.
75    pub fn contains(&self, name: &str) -> bool {
76        self.index.contains_key(name)
77    }
78
79    /// Look up a task ID by name. O(1) operation.
80    pub fn get_id(&self, name: &str) -> Option<TaskId> {
81        self.index.get(name).copied()
82    }
83
84    /// Get a task name by ID.
85    pub fn get_name(&self, id: TaskId) -> Option<&str> {
86        self.names.get(id.0 as usize).map(|s| s.as_str())
87    }
88
89    /// Get the number of tasks.
90    pub fn len(&self) -> usize {
91        self.names.len()
92    }
93
94    /// Check if the table is empty.
95    pub fn is_empty(&self) -> bool {
96        self.names.is_empty()
97    }
98
99    /// Iterate over all (TaskId, name) pairs.
100    pub fn iter(&self) -> impl Iterator<Item = (TaskId, &str)> {
101        self.names
102            .iter()
103            .enumerate()
104            .map(|(i, name)| (TaskId::new(i as u32), name.as_str()))
105    }
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111
112    #[test]
113    fn test_task_id() {
114        let id = TaskId::new(42);
115        assert_eq!(id.index(), 42);
116        assert_eq!(format!("{}", id), "task#42");
117    }
118
119    #[test]
120    fn test_task_table() {
121        let mut table = TaskTable::new();
122        assert!(table.is_empty());
123
124        let id1 = table.insert("task1");
125        let id2 = table.insert("task2");
126
127        assert_eq!(id1.index(), 0);
128        assert_eq!(id2.index(), 1);
129
130        assert_eq!(table.get_id("task1"), Some(id1));
131        assert_eq!(table.get_id("task2"), Some(id2));
132        assert_eq!(table.get_id("unknown"), None);
133
134        assert_eq!(table.get_name(id1), Some("task1"));
135        assert_eq!(table.get_name(id2), Some("task2"));
136    }
137
138    #[test]
139    fn test_task_table_iter() {
140        let mut table = TaskTable::new();
141        table.insert("a");
142        table.insert("b");
143        table.insert("c");
144
145        let pairs: Vec<_> = table.iter().collect();
146        assert_eq!(pairs.len(), 3);
147        assert_eq!(pairs[0].1, "a");
148        assert_eq!(pairs[1].1, "b");
149        assert_eq!(pairs[2].1, "c");
150    }
151
152    #[test]
153    fn test_task_table_try_insert() {
154        let mut table = TaskTable::new();
155
156        // First insert succeeds
157        let id1 = table.try_insert("task1");
158        assert!(id1.is_some());
159        assert_eq!(id1.unwrap().index(), 0);
160
161        // Second different insert succeeds
162        let id2 = table.try_insert("task2");
163        assert!(id2.is_some());
164        assert_eq!(id2.unwrap().index(), 1);
165
166        // Duplicate insert fails
167        let id3 = table.try_insert("task1");
168        assert!(id3.is_none());
169
170        // Table still has only 2 entries
171        assert_eq!(table.len(), 2);
172    }
173
174    #[test]
175    fn test_task_table_contains() {
176        let mut table = TaskTable::new();
177        table.insert("existing");
178
179        assert!(table.contains("existing"));
180        assert!(!table.contains("missing"));
181    }
182
183    #[test]
184    fn test_task_table_o1_lookup() {
185        let mut table = TaskTable::new();
186        // Insert many tasks to verify O(1) behavior
187        for i in 0..1000 {
188            table.insert(&format!("task_{}", i));
189        }
190
191        // Lookup should be O(1) with HashMap
192        assert_eq!(table.get_id("task_500").map(|id| id.index()), Some(500));
193        assert_eq!(table.get_id("task_999").map(|id| id.index()), Some(999));
194        assert_eq!(table.get_id("nonexistent"), None);
195    }
196}
nika_core/ast/analyzed/ids.rs

nika_core/ast/analyzed/
ids.rs
