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