tenant.openagents/omega

1use std::collections::HashMap;
2use std::hash::Hash;
3
4/// Computes the minimum detail level needed for each item so that no two items
5/// share the same description. Items whose descriptions are unique at level 0
6/// stay at 0; items that collide get their detail level incremented until either
7/// the collision is resolved or increasing the level no longer changes the
8/// description (preventing infinite loops for truly identical items).
9///
10/// The `get_description` closure must return a sequence that eventually reaches
11/// a "fixed point" where increasing `detail` no longer changes the output. If
12/// an item reaches its fixed point, it is assumed it will no longer change and
13/// will no longer be checked for collisions.
14pub fn compute_disambiguation_details<T, D>(
15    items: &[T],
16    get_description: impl Fn(&T, usize) -> D,
17) -> Vec<usize>
18where
19    D: Eq + Hash + Clone,
20{
21    let mut details = vec![0usize; items.len()];
22    let mut descriptions: HashMap<D, Vec<usize>> = HashMap::default();
23    let mut current_descriptions: Vec<D> =
24        items.iter().map(|item| get_description(item, 0)).collect();
25
26    loop {
27        let mut any_collisions = false;
28
29        for (index, (item, &detail)) in items.iter().zip(&details).enumerate() {
30            if detail > 0 {
31                let new_description = get_description(item, detail);
32                if new_description == current_descriptions[index] {
33                    continue;
34                }
35                current_descriptions[index] = new_description;
36            }
37            descriptions
38                .entry(current_descriptions[index].clone())
39                .or_insert_with(Vec::new)
40                .push(index);
41        }
42
43        for (_, indices) in descriptions.drain() {
44            if indices.len() > 1 {
45                any_collisions = true;
46                for index in indices {
47                    details[index] += 1;
48                }
49            }
50        }
51
52        if !any_collisions {
53            break;
54        }
55    }
56
57    details
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_no_conflicts() {
66        let items = vec!["alpha", "beta", "gamma"];
67        let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
68        assert_eq!(details, vec![0, 0, 0]);
69    }
70
71    #[test]
72    fn test_simple_two_way_conflict() {
73        // Two items with the same base name but different parents.
74        let items = vec![("src/foo.rs", "foo.rs"), ("lib/foo.rs", "foo.rs")];
75        let details = compute_disambiguation_details(&items, |item, detail| match detail {
76            0 => item.1.to_string(),
77            _ => item.0.to_string(),
78        });
79        assert_eq!(details, vec![1, 1]);
80    }
81
82    #[test]
83    fn test_three_way_conflict() {
84        let items = vec![
85            ("foo.rs", "a/foo.rs"),
86            ("foo.rs", "b/foo.rs"),
87            ("foo.rs", "c/foo.rs"),
88        ];
89        let details = compute_disambiguation_details(&items, |item, detail| match detail {
90            0 => item.0.to_string(),
91            _ => item.1.to_string(),
92        });
93        assert_eq!(details, vec![1, 1, 1]);
94    }
95
96    #[test]
97    fn test_deeper_conflict() {
98        // At detail 0, all three show "file.rs".
99        // At detail 1, items 0 and 1 both show "src/file.rs", item 2 shows "lib/file.rs".
100        // At detail 2, item 0 shows "a/src/file.rs", item 1 shows "b/src/file.rs".
101        let items = vec![
102            vec!["file.rs", "src/file.rs", "a/src/file.rs"],
103            vec!["file.rs", "src/file.rs", "b/src/file.rs"],
104            vec!["file.rs", "lib/file.rs", "x/lib/file.rs"],
105        ];
106        let details = compute_disambiguation_details(&items, |item, detail| {
107            let clamped = detail.min(item.len() - 1);
108            item[clamped].to_string()
109        });
110        assert_eq!(details, vec![2, 2, 1]);
111    }
112
113    #[test]
114    fn test_mixed_conflicting_and_unique() {
115        let items = vec![
116            ("src/foo.rs", "foo.rs"),
117            ("lib/foo.rs", "foo.rs"),
118            ("src/bar.rs", "bar.rs"),
119        ];
120        let details = compute_disambiguation_details(&items, |item, detail| match detail {
121            0 => item.1.to_string(),
122            _ => item.0.to_string(),
123        });
124        assert_eq!(details, vec![1, 1, 0]);
125    }
126
127    #[test]
128    fn test_identical_items_terminates() {
129        // All items return the same description at every detail level.
130        // The algorithm must terminate rather than looping forever.
131        let items = vec!["same", "same", "same"];
132        let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
133        // After bumping to 1, the description doesn't change from level 0,
134        // so the items are skipped and the loop terminates.
135        assert_eq!(details, vec![1, 1, 1]);
136    }
137
138    #[test]
139    fn test_single_item() {
140        let items = vec!["only"];
141        let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
142        assert_eq!(details, vec![0]);
143    }
144
145    #[test]
146    fn test_empty_input() {
147        let items: Vec<&str> = vec![];
148        let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
149        let expected: Vec<usize> = vec![];
150        assert_eq!(details, expected);
151    }
152
153    #[test]
154    fn test_duplicate_paths_from_multiple_groups() {
155        use std::path::Path;
156
157        // Simulates the sidebar scenario: a path like /Users/rtfeldman/code/zed
158        // appears in two project groups (e.g. "zed" alone and "zed, roc").
159        // After deduplication, only unique paths should be disambiguated.
160        //
161        // Paths:
162        //   /Users/rtfeldman/code/worktrees/zed/focal-arrow/zed  (group 1)
163        //   /Users/rtfeldman/code/zed                             (group 2)
164        //   /Users/rtfeldman/code/zed                             (group 3, same path as group 2)
165        //   /Users/rtfeldman/code/roc                             (group 3)
166        //
167        // A naive flat_map collects duplicates. The duplicate /code/zed entries
168        // collide with each other and drive the detail to the full path.
169        // The fix is to deduplicate before disambiguating.
170
171        fn path_suffix(path: &Path, detail: usize) -> String {
172            let mut components: Vec<_> = path
173                .components()
174                .rev()
175                .filter_map(|c| match c {
176                    std::path::Component::Normal(s) => Some(s.to_string_lossy()),
177                    _ => None,
178                })
179                .take(detail + 1)
180                .collect();
181            components.reverse();
182            components.join("/")
183        }
184
185        let all_paths: Vec<&Path> = vec![
186            Path::new("/Users/rtfeldman/code/worktrees/zed/focal-arrow/zed"),
187            Path::new("/Users/rtfeldman/code/zed"),
188            Path::new("/Users/rtfeldman/code/roc"),
189        ];
190
191        let details =
192            compute_disambiguation_details(&all_paths, |path, detail| path_suffix(path, detail));
193
194        // focal-arrow/zed and code/zed both end in "zed", so they need detail 1.
195        // "roc" is unique at detail 0.
196        assert_eq!(details, vec![1, 1, 0]);
197
198        assert_eq!(path_suffix(all_paths[0], details[0]), "focal-arrow/zed");
199        assert_eq!(path_suffix(all_paths[1], details[1]), "code/zed");
200        assert_eq!(path_suffix(all_paths[2], details[2]), "roc");
201    }
202}
203