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
use std::collections::HashMap;
use std::hash::Hash;
/// Computes the minimum detail level needed for each item so that no two items
/// share the same description. Items whose descriptions are unique at level 0
/// stay at 0; items that collide get their detail level incremented until either
/// the collision is resolved or increasing the level no longer changes the
/// description (preventing infinite loops for truly identical items).
///
/// The `get_description` closure must return a sequence that eventually reaches
/// a "fixed point" where increasing `detail` no longer changes the output. If
/// an item reaches its fixed point, it is assumed it will no longer change and
/// will no longer be checked for collisions.
pub fn compute_disambiguation_details<T, D>(
items: &[T],
get_description: impl Fn(&T, usize) -> D,
) -> Vec<usize>
where
D: Eq + Hash + Clone,
{
let mut details = vec![0usize; items.len()];
let mut descriptions: HashMap<D, Vec<usize>> = HashMap::default();
let mut current_descriptions: Vec<D> =
items.iter().map(|item| get_description(item, 0)).collect();
loop {
let mut any_collisions = false;
for (index, (item, &detail)) in items.iter().zip(&details).enumerate() {
if detail > 0 {
let new_description = get_description(item, detail);
if new_description == current_descriptions[index] {
continue;
}
current_descriptions[index] = new_description;
}
descriptions
.entry(current_descriptions[index].clone())
.or_insert_with(Vec::new)
.push(index);
}
for (_, indices) in descriptions.drain() {
if indices.len() > 1 {
any_collisions = true;
for index in indices {
details[index] += 1;
}
}
}
if !any_collisions {
break;
}
}
details
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_no_conflicts() {
let items = vec!["alpha", "beta", "gamma"];
let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
assert_eq!(details, vec![0, 0, 0]);
}
#[test]
fn test_simple_two_way_conflict() {
// Two items with the same base name but different parents.
let items = vec![("src/foo.rs", "foo.rs"), ("lib/foo.rs", "foo.rs")];
let details = compute_disambiguation_details(&items, |item, detail| match detail {
0 => item.1.to_string(),
_ => item.0.to_string(),
});
assert_eq!(details, vec![1, 1]);
}
#[test]
fn test_three_way_conflict() {
let items = vec![
("foo.rs", "a/foo.rs"),
("foo.rs", "b/foo.rs"),
("foo.rs", "c/foo.rs"),
];
let details = compute_disambiguation_details(&items, |item, detail| match detail {
0 => item.0.to_string(),
_ => item.1.to_string(),
});
assert_eq!(details, vec![1, 1, 1]);
}
#[test]
fn test_deeper_conflict() {
// At detail 0, all three show "file.rs".
// At detail 1, items 0 and 1 both show "src/file.rs", item 2 shows "lib/file.rs".
// At detail 2, item 0 shows "a/src/file.rs", item 1 shows "b/src/file.rs".
let items = vec![
vec!["file.rs", "src/file.rs", "a/src/file.rs"],
vec!["file.rs", "src/file.rs", "b/src/file.rs"],
vec!["file.rs", "lib/file.rs", "x/lib/file.rs"],
];
let details = compute_disambiguation_details(&items, |item, detail| {
let clamped = detail.min(item.len() - 1);
item[clamped].to_string()
});
assert_eq!(details, vec![2, 2, 1]);
}
#[test]
fn test_mixed_conflicting_and_unique() {
let items = vec![
("src/foo.rs", "foo.rs"),
("lib/foo.rs", "foo.rs"),
("src/bar.rs", "bar.rs"),
];
let details = compute_disambiguation_details(&items, |item, detail| match detail {
0 => item.1.to_string(),
_ => item.0.to_string(),
});
assert_eq!(details, vec![1, 1, 0]);
}
#[test]
fn test_identical_items_terminates() {
// All items return the same description at every detail level.
// The algorithm must terminate rather than looping forever.
let items = vec!["same", "same", "same"];
let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
// After bumping to 1, the description doesn't change from level 0,
// so the items are skipped and the loop terminates.
assert_eq!(details, vec![1, 1, 1]);
}
#[test]
fn test_single_item() {
let items = vec!["only"];
let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
assert_eq!(details, vec![0]);
}
#[test]
fn test_empty_input() {
let items: Vec<&str> = vec![];
let details = compute_disambiguation_details(&items, |item, _detail| item.to_string());
let expected: Vec<usize> = vec![];
assert_eq!(details, expected);
}
#[test]
fn test_duplicate_paths_from_multiple_groups() {
use std::path::Path;
// Simulates the sidebar scenario: a path like /Users/rtfeldman/code/zed
// appears in two project groups (e.g. "zed" alone and "zed, roc").
// After deduplication, only unique paths should be disambiguated.
//
// Paths:
// /Users/rtfeldman/code/worktrees/zed/focal-arrow/zed (group 1)
// /Users/rtfeldman/code/zed (group 2)
// /Users/rtfeldman/code/zed (group 3, same path as group 2)
// /Users/rtfeldman/code/roc (group 3)
//
// A naive flat_map collects duplicates. The duplicate /code/zed entries
// collide with each other and drive the detail to the full path.
// The fix is to deduplicate before disambiguating.
fn path_suffix(path: &Path, detail: usize) -> String {
let mut components: Vec<_> = path
.components()
.rev()
.filter_map(|c| match c {
std::path::Component::Normal(s) => Some(s.to_string_lossy()),
_ => None,
})
.take(detail + 1)
.collect();
components.reverse();
components.join("/")
}
let all_paths: Vec<&Path> = vec![
Path::new("/Users/rtfeldman/code/worktrees/zed/focal-arrow/zed"),
Path::new("/Users/rtfeldman/code/zed"),
Path::new("/Users/rtfeldman/code/roc"),
];
let details =
compute_disambiguation_details(&all_paths, |path, detail| path_suffix(path, detail));
// focal-arrow/zed and code/zed both end in "zed", so they need detail 1.
// "roc" is unique at detail 0.
assert_eq!(details, vec![1, 1, 0]);
assert_eq!(path_suffix(all_paths[0], details[0]), "focal-arrow/zed");
assert_eq!(path_suffix(all_paths[1], details[1]), "code/zed");
assert_eq!(path_suffix(all_paths[2], details[2]), "roc");
}
}