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