1use std::{
2 hash::{Hash, Hasher},
3 path::{Path, PathBuf},
4 sync::Arc,
5};
6
7use crate::paths::SanitizedPath;
8use itertools::Itertools;
9use serde::{Deserialize, Serialize};
10
11/// A list of absolute paths, with an associated display order.
12///
13/// Two `PathList` values are considered equal if they contain the same paths,
14/// regardless of the order in which those paths were originally provided.
15///
16/// The paths can be retrieved in the original order using `ordered_paths()`.
17#[derive(Default, Debug, Clone)]
18pub struct PathList {
19 /// The paths, in lexicographic order.
20 paths: Arc<[PathBuf]>,
21 /// The order in which the paths were provided.
22 ///
23 /// See `ordered_paths()` for a way to get the paths in the original order.
24 order: Arc<[usize]>,
25}
26
27impl PartialEq for PathList {
28 fn eq(&self, other: &Self) -> bool {
29 self.paths == other.paths
30 }
31}
32
33impl Eq for PathList {}
34
35impl Hash for PathList {
36 fn hash<H: Hasher>(&self, state: &mut H) {
37 self.paths.hash(state);
38 }
39}
40
41#[derive(Debug, Clone, Serialize, Deserialize)]
42pub struct SerializedPathList {
43 pub paths: String,
44 pub order: String,
45}
46
47impl PathList {
48 pub fn new<P: AsRef<Path>>(paths: &[P]) -> Self {
49 let mut indexed_paths: Vec<(usize, PathBuf)> = paths
50 .iter()
51 .enumerate()
52 .map(|(ix, path)| (ix, SanitizedPath::new(path).into()))
53 .collect();
54 indexed_paths.sort_by(|(_, a), (_, b)| a.cmp(b));
55 let order = indexed_paths.iter().map(|e| e.0).collect::<Vec<_>>().into();
56 let paths = indexed_paths
57 .into_iter()
58 .map(|e| e.1)
59 .collect::<Vec<_>>()
60 .into();
61 Self { order, paths }
62 }
63
64 pub fn is_empty(&self) -> bool {
65 self.paths.is_empty()
66 }
67
68 /// Returns a new `PathList` with the given path removed.
69 pub fn without_path(&self, path_to_remove: &Path) -> PathList {
70 let paths: Vec<PathBuf> = self
71 .ordered_paths()
72 .filter(|p| p.as_path() != path_to_remove)
73 .cloned()
74 .collect();
75 PathList::new(&paths)
76 }
77
78 /// Get the paths in lexicographic order.
79 pub fn paths(&self) -> &[PathBuf] {
80 self.paths.as_ref()
81 }
82
83 /// Get the paths in the lexicographic order.
84 pub fn paths_owned(&self) -> Arc<[PathBuf]> {
85 self.paths.clone()
86 }
87
88 /// Get the order in which the paths were provided.
89 pub fn order(&self) -> &[usize] {
90 self.order.as_ref()
91 }
92
93 /// Get the paths in the original order.
94 pub fn ordered_paths(&self) -> impl Iterator<Item = &PathBuf> {
95 self.order
96 .iter()
97 .zip(self.paths.iter())
98 .sorted_by_key(|(i, _)| **i)
99 .map(|(_, path)| path)
100 }
101
102 pub fn is_lexicographically_ordered(&self) -> bool {
103 self.order.iter().enumerate().all(|(i, &j)| i == j)
104 }
105
106 pub fn deserialize(serialized: &SerializedPathList) -> Self {
107 let mut paths: Vec<PathBuf> = if serialized.paths.is_empty() {
108 Vec::new()
109 } else {
110 serialized.paths.split('\n').map(PathBuf::from).collect()
111 };
112
113 let mut order: Vec<usize> = serialized
114 .order
115 .split(',')
116 .filter_map(|s| s.parse().ok())
117 .collect();
118
119 if !paths.is_sorted() || order.len() != paths.len() {
120 order = (0..paths.len()).collect();
121 paths.sort();
122 }
123
124 Self {
125 paths: paths.into(),
126 order: order.into(),
127 }
128 }
129
130 pub fn serialize(&self) -> SerializedPathList {
131 use std::fmt::Write as _;
132
133 let mut paths = String::new();
134 for path in self.paths.iter() {
135 if !paths.is_empty() {
136 paths.push('\n');
137 }
138 paths.push_str(&path.to_string_lossy());
139 }
140
141 let mut order = String::new();
142 for ix in self.order.iter() {
143 if !order.is_empty() {
144 order.push(',');
145 }
146 write!(&mut order, "{}", *ix).unwrap();
147 }
148 SerializedPathList { paths, order }
149 }
150}
151
152#[cfg(test)]
153mod tests {
154 use super::*;
155
156 #[test]
157 fn test_path_list() {
158 let list1 = PathList::new(&["a/d", "a/c"]);
159 let list2 = PathList::new(&["a/c", "a/d"]);
160
161 assert_eq!(list1.paths(), list2.paths(), "paths differ");
162 assert_eq!(list1.order(), &[1, 0], "list1 order incorrect");
163 assert_eq!(list2.order(), &[0, 1], "list2 order incorrect");
164
165 // Same paths in different order are equal (order is display-only).
166 assert_eq!(
167 list1, list2,
168 "same paths with different order should be equal"
169 );
170
171 let list1_deserialized = PathList::deserialize(&list1.serialize());
172 assert_eq!(list1_deserialized, list1, "list1 deserialization failed");
173
174 let list2_deserialized = PathList::deserialize(&list2.serialize());
175 assert_eq!(list2_deserialized, list2, "list2 deserialization failed");
176
177 assert_eq!(
178 list1.ordered_paths().collect_array().unwrap(),
179 [&PathBuf::from("a/d"), &PathBuf::from("a/c")],
180 "list1 ordered paths incorrect"
181 );
182 assert_eq!(
183 list2.ordered_paths().collect_array().unwrap(),
184 [&PathBuf::from("a/c"), &PathBuf::from("a/d")],
185 "list2 ordered paths incorrect"
186 );
187 }
188
189 #[test]
190 fn test_path_list_ordering() {
191 let list = PathList::new(&["b", "a", "c"]);
192 assert_eq!(
193 list.paths(),
194 &[PathBuf::from("a"), PathBuf::from("b"), PathBuf::from("c")]
195 );
196 assert_eq!(list.order(), &[1, 0, 2]);
197 assert!(!list.is_lexicographically_ordered());
198
199 let serialized = list.serialize();
200 let deserialized = PathList::deserialize(&serialized);
201 assert_eq!(deserialized, list);
202
203 assert_eq!(
204 deserialized.ordered_paths().collect_array().unwrap(),
205 [
206 &PathBuf::from("b"),
207 &PathBuf::from("a"),
208 &PathBuf::from("c")
209 ]
210 );
211
212 let list = PathList::new(&["b", "c", "a"]);
213 assert_eq!(
214 list.paths(),
215 &[PathBuf::from("a"), PathBuf::from("b"), PathBuf::from("c")]
216 );
217 assert_eq!(list.order(), &[2, 0, 1]);
218 assert!(!list.is_lexicographically_ordered());
219
220 let serialized = list.serialize();
221 let deserialized = PathList::deserialize(&serialized);
222 assert_eq!(deserialized, list);
223
224 assert_eq!(
225 deserialized.ordered_paths().collect_array().unwrap(),
226 [
227 &PathBuf::from("b"),
228 &PathBuf::from("c"),
229 &PathBuf::from("a"),
230 ]
231 );
232 }
233}