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}