Show More
@@ -1,481 +1,482 b'' | |||||
1 | // utils module |
|
1 | // utils module | |
2 | // |
|
2 | // | |
3 | // Copyright 2019 Raphaël Gomès <rgomes@octobus.net> |
|
3 | // Copyright 2019 Raphaël Gomès <rgomes@octobus.net> | |
4 | // |
|
4 | // | |
5 | // This software may be used and distributed according to the terms of the |
|
5 | // This software may be used and distributed according to the terms of the | |
6 | // GNU General Public License version 2 or any later version. |
|
6 | // GNU General Public License version 2 or any later version. | |
7 |
|
7 | |||
8 | //! Contains useful functions, traits, structs, etc. for use in core. |
|
8 | //! Contains useful functions, traits, structs, etc. for use in core. | |
9 |
|
9 | |||
10 | use crate::errors::{HgError, IoErrorContext}; |
|
10 | use crate::errors::{HgError, IoErrorContext}; | |
11 | use crate::utils::hg_path::HgPath; |
|
11 | use crate::utils::hg_path::HgPath; | |
12 | use im_rc::ordmap::DiffItem; |
|
12 | use im_rc::ordmap::DiffItem; | |
13 | use im_rc::ordmap::OrdMap; |
|
13 | use im_rc::ordmap::OrdMap; | |
14 | use std::cell::Cell; |
|
14 | use std::cell::Cell; | |
15 | use std::fmt; |
|
15 | use std::fmt; | |
16 | use std::{io::Write, ops::Deref}; |
|
16 | use std::{io::Write, ops::Deref}; | |
17 |
|
17 | |||
18 | pub mod files; |
|
18 | pub mod files; | |
19 | pub mod hg_path; |
|
19 | pub mod hg_path; | |
20 | pub mod path_auditor; |
|
20 | pub mod path_auditor; | |
21 |
|
21 | |||
22 | /// Useful until rust/issues/56345 is stable |
|
22 | /// Useful until rust/issues/56345 is stable | |
23 | /// |
|
23 | /// | |
24 | /// # Examples |
|
24 | /// # Examples | |
25 | /// |
|
25 | /// | |
26 | /// ``` |
|
26 | /// ``` | |
27 | /// use crate::hg::utils::find_slice_in_slice; |
|
27 | /// use crate::hg::utils::find_slice_in_slice; | |
28 | /// |
|
28 | /// | |
29 | /// let haystack = b"This is the haystack".to_vec(); |
|
29 | /// let haystack = b"This is the haystack".to_vec(); | |
30 | /// assert_eq!(find_slice_in_slice(&haystack, b"the"), Some(8)); |
|
30 | /// assert_eq!(find_slice_in_slice(&haystack, b"the"), Some(8)); | |
31 | /// assert_eq!(find_slice_in_slice(&haystack, b"not here"), None); |
|
31 | /// assert_eq!(find_slice_in_slice(&haystack, b"not here"), None); | |
32 | /// ``` |
|
32 | /// ``` | |
33 | pub fn find_slice_in_slice<T>(slice: &[T], needle: &[T]) -> Option<usize> |
|
33 | pub fn find_slice_in_slice<T>(slice: &[T], needle: &[T]) -> Option<usize> | |
34 | where |
|
34 | where | |
35 | for<'a> &'a [T]: PartialEq, |
|
35 | for<'a> &'a [T]: PartialEq, | |
36 | { |
|
36 | { | |
37 | slice |
|
37 | slice | |
38 | .windows(needle.len()) |
|
38 | .windows(needle.len()) | |
39 | .position(|window| window == needle) |
|
39 | .position(|window| window == needle) | |
40 | } |
|
40 | } | |
41 |
|
41 | |||
42 | /// Replaces the `from` slice with the `to` slice inside the `buf` slice. |
|
42 | /// Replaces the `from` slice with the `to` slice inside the `buf` slice. | |
43 | /// |
|
43 | /// | |
44 | /// # Examples |
|
44 | /// # Examples | |
45 | /// |
|
45 | /// | |
46 | /// ``` |
|
46 | /// ``` | |
47 | /// use crate::hg::utils::replace_slice; |
|
47 | /// use crate::hg::utils::replace_slice; | |
48 | /// let mut line = b"I hate writing tests!".to_vec(); |
|
48 | /// let mut line = b"I hate writing tests!".to_vec(); | |
49 | /// replace_slice(&mut line, b"hate", b"love"); |
|
49 | /// replace_slice(&mut line, b"hate", b"love"); | |
50 | /// assert_eq!( |
|
50 | /// assert_eq!( | |
51 | /// line, |
|
51 | /// line, | |
52 | /// b"I love writing tests!".to_vec() |
|
52 | /// b"I love writing tests!".to_vec() | |
53 | /// ); |
|
53 | /// ); | |
54 | /// ``` |
|
54 | /// ``` | |
55 | pub fn replace_slice<T>(buf: &mut [T], from: &[T], to: &[T]) |
|
55 | pub fn replace_slice<T>(buf: &mut [T], from: &[T], to: &[T]) | |
56 | where |
|
56 | where | |
57 | T: Clone + PartialEq, |
|
57 | T: Clone + PartialEq, | |
58 | { |
|
58 | { | |
59 | if buf.len() < from.len() || from.len() != to.len() { |
|
59 | if buf.len() < from.len() || from.len() != to.len() { | |
60 | return; |
|
60 | return; | |
61 | } |
|
61 | } | |
62 | for i in 0..=buf.len() - from.len() { |
|
62 | for i in 0..=buf.len() - from.len() { | |
63 | if buf[i..].starts_with(from) { |
|
63 | if buf[i..].starts_with(from) { | |
64 | buf[i..(i + from.len())].clone_from_slice(to); |
|
64 | buf[i..(i + from.len())].clone_from_slice(to); | |
65 | } |
|
65 | } | |
66 | } |
|
66 | } | |
67 | } |
|
67 | } | |
68 |
|
68 | |||
69 | pub trait SliceExt { |
|
69 | pub trait SliceExt { | |
70 | fn trim_end(&self) -> &Self; |
|
70 | fn trim_end(&self) -> &Self; | |
71 | fn trim_start(&self) -> &Self; |
|
71 | fn trim_start(&self) -> &Self; | |
72 | fn trim_end_matches(&self, f: impl FnMut(u8) -> bool) -> &Self; |
|
72 | fn trim_end_matches(&self, f: impl FnMut(u8) -> bool) -> &Self; | |
73 | fn trim_start_matches(&self, f: impl FnMut(u8) -> bool) -> &Self; |
|
73 | fn trim_start_matches(&self, f: impl FnMut(u8) -> bool) -> &Self; | |
74 | fn trim(&self) -> &Self; |
|
74 | fn trim(&self) -> &Self; | |
75 | fn drop_prefix(&self, needle: &Self) -> Option<&Self>; |
|
75 | fn drop_prefix(&self, needle: &Self) -> Option<&Self>; | |
76 | fn split_2(&self, separator: u8) -> Option<(&[u8], &[u8])>; |
|
76 | fn split_2(&self, separator: u8) -> Option<(&[u8], &[u8])>; | |
77 | fn split_2_by_slice(&self, separator: &[u8]) -> Option<(&[u8], &[u8])>; |
|
77 | fn split_2_by_slice(&self, separator: &[u8]) -> Option<(&[u8], &[u8])>; | |
78 | } |
|
78 | } | |
79 |
|
79 | |||
80 | impl SliceExt for [u8] { |
|
80 | impl SliceExt for [u8] { | |
81 | fn trim_end(&self) -> &[u8] { |
|
81 | fn trim_end(&self) -> &[u8] { | |
82 | self.trim_end_matches(|byte| byte.is_ascii_whitespace()) |
|
82 | self.trim_end_matches(|byte| byte.is_ascii_whitespace()) | |
83 | } |
|
83 | } | |
84 |
|
84 | |||
85 | fn trim_start(&self) -> &[u8] { |
|
85 | fn trim_start(&self) -> &[u8] { | |
86 | self.trim_start_matches(|byte| byte.is_ascii_whitespace()) |
|
86 | self.trim_start_matches(|byte| byte.is_ascii_whitespace()) | |
87 | } |
|
87 | } | |
88 |
|
88 | |||
89 | fn trim_end_matches(&self, mut f: impl FnMut(u8) -> bool) -> &Self { |
|
89 | fn trim_end_matches(&self, mut f: impl FnMut(u8) -> bool) -> &Self { | |
90 | if let Some(last) = self.iter().rposition(|&byte| !f(byte)) { |
|
90 | if let Some(last) = self.iter().rposition(|&byte| !f(byte)) { | |
91 | &self[..=last] |
|
91 | &self[..=last] | |
92 | } else { |
|
92 | } else { | |
93 | &[] |
|
93 | &[] | |
94 | } |
|
94 | } | |
95 | } |
|
95 | } | |
96 |
|
96 | |||
97 | fn trim_start_matches(&self, mut f: impl FnMut(u8) -> bool) -> &Self { |
|
97 | fn trim_start_matches(&self, mut f: impl FnMut(u8) -> bool) -> &Self { | |
98 | if let Some(first) = self.iter().position(|&byte| !f(byte)) { |
|
98 | if let Some(first) = self.iter().position(|&byte| !f(byte)) { | |
99 | &self[first..] |
|
99 | &self[first..] | |
100 | } else { |
|
100 | } else { | |
101 | &[] |
|
101 | &[] | |
102 | } |
|
102 | } | |
103 | } |
|
103 | } | |
104 |
|
104 | |||
105 | /// ``` |
|
105 | /// ``` | |
106 | /// use hg::utils::SliceExt; |
|
106 | /// use hg::utils::SliceExt; | |
107 | /// assert_eq!( |
|
107 | /// assert_eq!( | |
108 | /// b" to trim ".trim(), |
|
108 | /// b" to trim ".trim(), | |
109 | /// b"to trim" |
|
109 | /// b"to trim" | |
110 | /// ); |
|
110 | /// ); | |
111 | /// assert_eq!( |
|
111 | /// assert_eq!( | |
112 | /// b"to trim ".trim(), |
|
112 | /// b"to trim ".trim(), | |
113 | /// b"to trim" |
|
113 | /// b"to trim" | |
114 | /// ); |
|
114 | /// ); | |
115 | /// assert_eq!( |
|
115 | /// assert_eq!( | |
116 | /// b" to trim".trim(), |
|
116 | /// b" to trim".trim(), | |
117 | /// b"to trim" |
|
117 | /// b"to trim" | |
118 | /// ); |
|
118 | /// ); | |
119 | /// ``` |
|
119 | /// ``` | |
120 | fn trim(&self) -> &[u8] { |
|
120 | fn trim(&self) -> &[u8] { | |
121 | self.trim_start().trim_end() |
|
121 | self.trim_start().trim_end() | |
122 | } |
|
122 | } | |
123 |
|
123 | |||
124 | fn drop_prefix(&self, needle: &Self) -> Option<&Self> { |
|
124 | fn drop_prefix(&self, needle: &Self) -> Option<&Self> { | |
125 | if self.starts_with(needle) { |
|
125 | if self.starts_with(needle) { | |
126 | Some(&self[needle.len()..]) |
|
126 | Some(&self[needle.len()..]) | |
127 | } else { |
|
127 | } else { | |
128 | None |
|
128 | None | |
129 | } |
|
129 | } | |
130 | } |
|
130 | } | |
131 |
|
131 | |||
132 | fn split_2(&self, separator: u8) -> Option<(&[u8], &[u8])> { |
|
132 | fn split_2(&self, separator: u8) -> Option<(&[u8], &[u8])> { | |
133 | let mut iter = self.splitn(2, |&byte| byte == separator); |
|
133 | let mut iter = self.splitn(2, |&byte| byte == separator); | |
134 | let a = iter.next()?; |
|
134 | let a = iter.next()?; | |
135 | let b = iter.next()?; |
|
135 | let b = iter.next()?; | |
136 | Some((a, b)) |
|
136 | Some((a, b)) | |
137 | } |
|
137 | } | |
138 |
|
138 | |||
139 | fn split_2_by_slice(&self, separator: &[u8]) -> Option<(&[u8], &[u8])> { |
|
139 | fn split_2_by_slice(&self, separator: &[u8]) -> Option<(&[u8], &[u8])> { | |
140 | if let Some(pos) = find_slice_in_slice(self, separator) { |
|
140 | if let Some(pos) = find_slice_in_slice(self, separator) { | |
141 | Some((&self[..pos], &self[pos + separator.len()..])) |
|
141 | Some((&self[..pos], &self[pos + separator.len()..])) | |
142 | } else { |
|
142 | } else { | |
143 | None |
|
143 | None | |
144 | } |
|
144 | } | |
145 | } |
|
145 | } | |
146 | } |
|
146 | } | |
147 |
|
147 | |||
148 | pub trait Escaped { |
|
148 | pub trait Escaped { | |
149 | /// Return bytes escaped for display to the user |
|
149 | /// Return bytes escaped for display to the user | |
150 | fn escaped_bytes(&self) -> Vec<u8>; |
|
150 | fn escaped_bytes(&self) -> Vec<u8>; | |
151 | } |
|
151 | } | |
152 |
|
152 | |||
153 | impl Escaped for u8 { |
|
153 | impl Escaped for u8 { | |
154 | fn escaped_bytes(&self) -> Vec<u8> { |
|
154 | fn escaped_bytes(&self) -> Vec<u8> { | |
155 | let mut acc = vec![]; |
|
155 | let mut acc = vec![]; | |
156 | match self { |
|
156 | match self { | |
157 | c @ b'\'' | c @ b'\\' => { |
|
157 | c @ b'\'' | c @ b'\\' => { | |
158 | acc.push(b'\\'); |
|
158 | acc.push(b'\\'); | |
159 | acc.push(*c); |
|
159 | acc.push(*c); | |
160 | } |
|
160 | } | |
161 | b'\t' => { |
|
161 | b'\t' => { | |
162 | acc.extend(br"\\t"); |
|
162 | acc.extend(br"\\t"); | |
163 | } |
|
163 | } | |
164 | b'\n' => { |
|
164 | b'\n' => { | |
165 | acc.extend(br"\\n"); |
|
165 | acc.extend(br"\\n"); | |
166 | } |
|
166 | } | |
167 | b'\r' => { |
|
167 | b'\r' => { | |
168 | acc.extend(br"\\r"); |
|
168 | acc.extend(br"\\r"); | |
169 | } |
|
169 | } | |
170 | c if (*c < b' ' || *c >= 127) => { |
|
170 | c if (*c < b' ' || *c >= 127) => { | |
171 | write!(acc, "\\x{:x}", self).unwrap(); |
|
171 | write!(acc, "\\x{:x}", self).unwrap(); | |
172 | } |
|
172 | } | |
173 | c => { |
|
173 | c => { | |
174 | acc.push(*c); |
|
174 | acc.push(*c); | |
175 | } |
|
175 | } | |
176 | } |
|
176 | } | |
177 | acc |
|
177 | acc | |
178 | } |
|
178 | } | |
179 | } |
|
179 | } | |
180 |
|
180 | |||
181 | impl<'a, T: Escaped> Escaped for &'a [T] { |
|
181 | impl<'a, T: Escaped> Escaped for &'a [T] { | |
182 | fn escaped_bytes(&self) -> Vec<u8> { |
|
182 | fn escaped_bytes(&self) -> Vec<u8> { | |
183 | self.iter().flat_map(Escaped::escaped_bytes).collect() |
|
183 | self.iter().flat_map(Escaped::escaped_bytes).collect() | |
184 | } |
|
184 | } | |
185 | } |
|
185 | } | |
186 |
|
186 | |||
187 | impl<T: Escaped> Escaped for Vec<T> { |
|
187 | impl<T: Escaped> Escaped for Vec<T> { | |
188 | fn escaped_bytes(&self) -> Vec<u8> { |
|
188 | fn escaped_bytes(&self) -> Vec<u8> { | |
189 | self.deref().escaped_bytes() |
|
189 | self.deref().escaped_bytes() | |
190 | } |
|
190 | } | |
191 | } |
|
191 | } | |
192 |
|
192 | |||
193 | impl<'a> Escaped for &'a HgPath { |
|
193 | impl<'a> Escaped for &'a HgPath { | |
194 | fn escaped_bytes(&self) -> Vec<u8> { |
|
194 | fn escaped_bytes(&self) -> Vec<u8> { | |
195 | self.as_bytes().escaped_bytes() |
|
195 | self.as_bytes().escaped_bytes() | |
196 | } |
|
196 | } | |
197 | } |
|
197 | } | |
198 |
|
198 | |||
199 | #[cfg(unix)] |
|
199 | #[cfg(unix)] | |
200 | pub fn shell_quote(value: &[u8]) -> Vec<u8> { |
|
200 | pub fn shell_quote(value: &[u8]) -> Vec<u8> { | |
201 | // TODO: Use the `matches!` macro when we require Rust 1.42+ |
|
201 | if value.iter().all(|&byte| { | |
202 | if value.iter().all(|&byte| match byte { |
|
202 | matches!( | |
203 | b'a'..=b'z' |
|
203 | byte, | |
204 |
|
|
204 | b'a'..=b'z' | |
205 |
| b' |
|
205 | | b'A'..=b'Z' | |
206 | | b'.' |
|
206 | | b'0'..=b'9' | |
207 |
| b' |
|
207 | | b'.' | |
208 |
| b' |
|
208 | | b'_' | |
209 |
| b' |
|
209 | | b'/' | |
210 |
| b' |
|
210 | | b'+' | |
211 | _ => false, |
|
211 | | b'-' | |
|
212 | ) | |||
212 | }) { |
|
213 | }) { | |
213 | value.to_owned() |
|
214 | value.to_owned() | |
214 | } else { |
|
215 | } else { | |
215 | let mut quoted = Vec::with_capacity(value.len() + 2); |
|
216 | let mut quoted = Vec::with_capacity(value.len() + 2); | |
216 | quoted.push(b'\''); |
|
217 | quoted.push(b'\''); | |
217 | for &byte in value { |
|
218 | for &byte in value { | |
218 | if byte == b'\'' { |
|
219 | if byte == b'\'' { | |
219 | quoted.push(b'\\'); |
|
220 | quoted.push(b'\\'); | |
220 | } |
|
221 | } | |
221 | quoted.push(byte); |
|
222 | quoted.push(byte); | |
222 | } |
|
223 | } | |
223 | quoted.push(b'\''); |
|
224 | quoted.push(b'\''); | |
224 | quoted |
|
225 | quoted | |
225 | } |
|
226 | } | |
226 | } |
|
227 | } | |
227 |
|
228 | |||
228 | pub fn current_dir() -> Result<std::path::PathBuf, HgError> { |
|
229 | pub fn current_dir() -> Result<std::path::PathBuf, HgError> { | |
229 | std::env::current_dir().map_err(|error| HgError::IoError { |
|
230 | std::env::current_dir().map_err(|error| HgError::IoError { | |
230 | error, |
|
231 | error, | |
231 | context: IoErrorContext::CurrentDir, |
|
232 | context: IoErrorContext::CurrentDir, | |
232 | }) |
|
233 | }) | |
233 | } |
|
234 | } | |
234 |
|
235 | |||
235 | pub fn current_exe() -> Result<std::path::PathBuf, HgError> { |
|
236 | pub fn current_exe() -> Result<std::path::PathBuf, HgError> { | |
236 | std::env::current_exe().map_err(|error| HgError::IoError { |
|
237 | std::env::current_exe().map_err(|error| HgError::IoError { | |
237 | error, |
|
238 | error, | |
238 | context: IoErrorContext::CurrentExe, |
|
239 | context: IoErrorContext::CurrentExe, | |
239 | }) |
|
240 | }) | |
240 | } |
|
241 | } | |
241 |
|
242 | |||
242 | /// Expand `$FOO` and `${FOO}` environment variables in the given byte string |
|
243 | /// Expand `$FOO` and `${FOO}` environment variables in the given byte string | |
243 | pub fn expand_vars(s: &[u8]) -> std::borrow::Cow<[u8]> { |
|
244 | pub fn expand_vars(s: &[u8]) -> std::borrow::Cow<[u8]> { | |
244 | lazy_static::lazy_static! { |
|
245 | lazy_static::lazy_static! { | |
245 | /// https://github.com/python/cpython/blob/3.9/Lib/posixpath.py#L301 |
|
246 | /// https://github.com/python/cpython/blob/3.9/Lib/posixpath.py#L301 | |
246 | /// The `x` makes whitespace ignored. |
|
247 | /// The `x` makes whitespace ignored. | |
247 | /// `-u` disables the Unicode flag, which makes `\w` like Python with the ASCII flag. |
|
248 | /// `-u` disables the Unicode flag, which makes `\w` like Python with the ASCII flag. | |
248 | static ref VAR_RE: regex::bytes::Regex = |
|
249 | static ref VAR_RE: regex::bytes::Regex = | |
249 | regex::bytes::Regex::new(r"(?x-u) |
|
250 | regex::bytes::Regex::new(r"(?x-u) | |
250 | \$ |
|
251 | \$ | |
251 | (?: |
|
252 | (?: | |
252 | (\w+) |
|
253 | (\w+) | |
253 | | |
|
254 | | | |
254 | \{ |
|
255 | \{ | |
255 | ([^}]*) |
|
256 | ([^}]*) | |
256 | \} |
|
257 | \} | |
257 | ) |
|
258 | ) | |
258 | ").unwrap(); |
|
259 | ").unwrap(); | |
259 | } |
|
260 | } | |
260 | VAR_RE.replace_all(s, |captures: ®ex::bytes::Captures| { |
|
261 | VAR_RE.replace_all(s, |captures: ®ex::bytes::Captures| { | |
261 | let var_name = files::get_os_str_from_bytes( |
|
262 | let var_name = files::get_os_str_from_bytes( | |
262 | captures |
|
263 | captures | |
263 | .get(1) |
|
264 | .get(1) | |
264 | .or_else(|| captures.get(2)) |
|
265 | .or_else(|| captures.get(2)) | |
265 | .expect("either side of `|` must participate in match") |
|
266 | .expect("either side of `|` must participate in match") | |
266 | .as_bytes(), |
|
267 | .as_bytes(), | |
267 | ); |
|
268 | ); | |
268 | std::env::var_os(var_name) |
|
269 | std::env::var_os(var_name) | |
269 | .map(files::get_bytes_from_os_str) |
|
270 | .map(files::get_bytes_from_os_str) | |
270 | .unwrap_or_else(|| { |
|
271 | .unwrap_or_else(|| { | |
271 | // Referencing an environment variable that does not exist. |
|
272 | // Referencing an environment variable that does not exist. | |
272 | // Leave the $FOO reference as-is. |
|
273 | // Leave the $FOO reference as-is. | |
273 | captures[0].to_owned() |
|
274 | captures[0].to_owned() | |
274 | }) |
|
275 | }) | |
275 | }) |
|
276 | }) | |
276 | } |
|
277 | } | |
277 |
|
278 | |||
278 | #[test] |
|
279 | #[test] | |
279 | fn test_expand_vars() { |
|
280 | fn test_expand_vars() { | |
280 | // Modifying process-global state in a test isn’t great, |
|
281 | // Modifying process-global state in a test isn’t great, | |
281 | // but hopefully this won’t collide with anything. |
|
282 | // but hopefully this won’t collide with anything. | |
282 | std::env::set_var("TEST_EXPAND_VAR", "1"); |
|
283 | std::env::set_var("TEST_EXPAND_VAR", "1"); | |
283 | assert_eq!( |
|
284 | assert_eq!( | |
284 | expand_vars(b"before/$TEST_EXPAND_VAR/after"), |
|
285 | expand_vars(b"before/$TEST_EXPAND_VAR/after"), | |
285 | &b"before/1/after"[..] |
|
286 | &b"before/1/after"[..] | |
286 | ); |
|
287 | ); | |
287 | assert_eq!( |
|
288 | assert_eq!( | |
288 | expand_vars(b"before${TEST_EXPAND_VAR}${TEST_EXPAND_VAR}${TEST_EXPAND_VAR}after"), |
|
289 | expand_vars(b"before${TEST_EXPAND_VAR}${TEST_EXPAND_VAR}${TEST_EXPAND_VAR}after"), | |
289 | &b"before111after"[..] |
|
290 | &b"before111after"[..] | |
290 | ); |
|
291 | ); | |
291 | let s = b"before $SOME_LONG_NAME_THAT_WE_ASSUME_IS_NOT_AN_ACTUAL_ENV_VAR after"; |
|
292 | let s = b"before $SOME_LONG_NAME_THAT_WE_ASSUME_IS_NOT_AN_ACTUAL_ENV_VAR after"; | |
292 | assert_eq!(expand_vars(s), &s[..]); |
|
293 | assert_eq!(expand_vars(s), &s[..]); | |
293 | } |
|
294 | } | |
294 |
|
295 | |||
295 | pub(crate) enum MergeResult<V> { |
|
296 | pub(crate) enum MergeResult<V> { | |
296 | UseLeftValue, |
|
297 | UseLeftValue, | |
297 | UseRightValue, |
|
298 | UseRightValue, | |
298 | UseNewValue(V), |
|
299 | UseNewValue(V), | |
299 | } |
|
300 | } | |
300 |
|
301 | |||
301 | /// Return the union of the two given maps, |
|
302 | /// Return the union of the two given maps, | |
302 | /// calling `merge(key, left_value, right_value)` to resolve keys that exist in |
|
303 | /// calling `merge(key, left_value, right_value)` to resolve keys that exist in | |
303 | /// both. |
|
304 | /// both. | |
304 | /// |
|
305 | /// | |
305 | /// CC https://github.com/bodil/im-rs/issues/166 |
|
306 | /// CC https://github.com/bodil/im-rs/issues/166 | |
306 | pub(crate) fn ordmap_union_with_merge<K, V>( |
|
307 | pub(crate) fn ordmap_union_with_merge<K, V>( | |
307 | left: OrdMap<K, V>, |
|
308 | left: OrdMap<K, V>, | |
308 | right: OrdMap<K, V>, |
|
309 | right: OrdMap<K, V>, | |
309 | mut merge: impl FnMut(&K, &V, &V) -> MergeResult<V>, |
|
310 | mut merge: impl FnMut(&K, &V, &V) -> MergeResult<V>, | |
310 | ) -> OrdMap<K, V> |
|
311 | ) -> OrdMap<K, V> | |
311 | where |
|
312 | where | |
312 | K: Clone + Ord, |
|
313 | K: Clone + Ord, | |
313 | V: Clone + PartialEq, |
|
314 | V: Clone + PartialEq, | |
314 | { |
|
315 | { | |
315 | if left.ptr_eq(&right) { |
|
316 | if left.ptr_eq(&right) { | |
316 | // One of the two maps is an unmodified clone of the other |
|
317 | // One of the two maps is an unmodified clone of the other | |
317 | left |
|
318 | left | |
318 | } else if left.len() / 2 > right.len() { |
|
319 | } else if left.len() / 2 > right.len() { | |
319 | // When two maps have different sizes, |
|
320 | // When two maps have different sizes, | |
320 | // their size difference is a lower bound on |
|
321 | // their size difference is a lower bound on | |
321 | // how many keys of the larger map are not also in the smaller map. |
|
322 | // how many keys of the larger map are not also in the smaller map. | |
322 | // This in turn is a lower bound on the number of differences in |
|
323 | // This in turn is a lower bound on the number of differences in | |
323 | // `OrdMap::diff` and the "amount of work" that would be done |
|
324 | // `OrdMap::diff` and the "amount of work" that would be done | |
324 | // by `ordmap_union_with_merge_by_diff`. |
|
325 | // by `ordmap_union_with_merge_by_diff`. | |
325 | // |
|
326 | // | |
326 | // Here `left` is more than twice the size of `right`, |
|
327 | // Here `left` is more than twice the size of `right`, | |
327 | // so the number of differences is more than the total size of |
|
328 | // so the number of differences is more than the total size of | |
328 | // `right`. Therefore an algorithm based on iterating `right` |
|
329 | // `right`. Therefore an algorithm based on iterating `right` | |
329 | // is more efficient. |
|
330 | // is more efficient. | |
330 | // |
|
331 | // | |
331 | // This helps a lot when a tiny (or empty) map is merged |
|
332 | // This helps a lot when a tiny (or empty) map is merged | |
332 | // with a large one. |
|
333 | // with a large one. | |
333 | ordmap_union_with_merge_by_iter(left, right, merge) |
|
334 | ordmap_union_with_merge_by_iter(left, right, merge) | |
334 | } else if left.len() < right.len() / 2 { |
|
335 | } else if left.len() < right.len() / 2 { | |
335 | // Same as above but with `left` and `right` swapped |
|
336 | // Same as above but with `left` and `right` swapped | |
336 | ordmap_union_with_merge_by_iter(right, left, |key, a, b| { |
|
337 | ordmap_union_with_merge_by_iter(right, left, |key, a, b| { | |
337 | // Also swapped in `merge` arguments: |
|
338 | // Also swapped in `merge` arguments: | |
338 | match merge(key, b, a) { |
|
339 | match merge(key, b, a) { | |
339 | MergeResult::UseNewValue(v) => MergeResult::UseNewValue(v), |
|
340 | MergeResult::UseNewValue(v) => MergeResult::UseNewValue(v), | |
340 | // … and swap back in `merge` result: |
|
341 | // … and swap back in `merge` result: | |
341 | MergeResult::UseLeftValue => MergeResult::UseRightValue, |
|
342 | MergeResult::UseLeftValue => MergeResult::UseRightValue, | |
342 | MergeResult::UseRightValue => MergeResult::UseLeftValue, |
|
343 | MergeResult::UseRightValue => MergeResult::UseLeftValue, | |
343 | } |
|
344 | } | |
344 | }) |
|
345 | }) | |
345 | } else { |
|
346 | } else { | |
346 | // For maps of similar size, use the algorithm based on `OrdMap::diff` |
|
347 | // For maps of similar size, use the algorithm based on `OrdMap::diff` | |
347 | ordmap_union_with_merge_by_diff(left, right, merge) |
|
348 | ordmap_union_with_merge_by_diff(left, right, merge) | |
348 | } |
|
349 | } | |
349 | } |
|
350 | } | |
350 |
|
351 | |||
351 | /// Efficient if `right` is much smaller than `left` |
|
352 | /// Efficient if `right` is much smaller than `left` | |
352 | fn ordmap_union_with_merge_by_iter<K, V>( |
|
353 | fn ordmap_union_with_merge_by_iter<K, V>( | |
353 | mut left: OrdMap<K, V>, |
|
354 | mut left: OrdMap<K, V>, | |
354 | right: OrdMap<K, V>, |
|
355 | right: OrdMap<K, V>, | |
355 | mut merge: impl FnMut(&K, &V, &V) -> MergeResult<V>, |
|
356 | mut merge: impl FnMut(&K, &V, &V) -> MergeResult<V>, | |
356 | ) -> OrdMap<K, V> |
|
357 | ) -> OrdMap<K, V> | |
357 | where |
|
358 | where | |
358 | K: Clone + Ord, |
|
359 | K: Clone + Ord, | |
359 | V: Clone, |
|
360 | V: Clone, | |
360 | { |
|
361 | { | |
361 | for (key, right_value) in right { |
|
362 | for (key, right_value) in right { | |
362 | match left.get(&key) { |
|
363 | match left.get(&key) { | |
363 | None => { |
|
364 | None => { | |
364 | left.insert(key, right_value); |
|
365 | left.insert(key, right_value); | |
365 | } |
|
366 | } | |
366 | Some(left_value) => match merge(&key, left_value, &right_value) { |
|
367 | Some(left_value) => match merge(&key, left_value, &right_value) { | |
367 | MergeResult::UseLeftValue => {} |
|
368 | MergeResult::UseLeftValue => {} | |
368 | MergeResult::UseRightValue => { |
|
369 | MergeResult::UseRightValue => { | |
369 | left.insert(key, right_value); |
|
370 | left.insert(key, right_value); | |
370 | } |
|
371 | } | |
371 | MergeResult::UseNewValue(new_value) => { |
|
372 | MergeResult::UseNewValue(new_value) => { | |
372 | left.insert(key, new_value); |
|
373 | left.insert(key, new_value); | |
373 | } |
|
374 | } | |
374 | }, |
|
375 | }, | |
375 | } |
|
376 | } | |
376 | } |
|
377 | } | |
377 | left |
|
378 | left | |
378 | } |
|
379 | } | |
379 |
|
380 | |||
380 | /// Fallback when both maps are of similar size |
|
381 | /// Fallback when both maps are of similar size | |
381 | fn ordmap_union_with_merge_by_diff<K, V>( |
|
382 | fn ordmap_union_with_merge_by_diff<K, V>( | |
382 | mut left: OrdMap<K, V>, |
|
383 | mut left: OrdMap<K, V>, | |
383 | mut right: OrdMap<K, V>, |
|
384 | mut right: OrdMap<K, V>, | |
384 | mut merge: impl FnMut(&K, &V, &V) -> MergeResult<V>, |
|
385 | mut merge: impl FnMut(&K, &V, &V) -> MergeResult<V>, | |
385 | ) -> OrdMap<K, V> |
|
386 | ) -> OrdMap<K, V> | |
386 | where |
|
387 | where | |
387 | K: Clone + Ord, |
|
388 | K: Clone + Ord, | |
388 | V: Clone + PartialEq, |
|
389 | V: Clone + PartialEq, | |
389 | { |
|
390 | { | |
390 | // (key, value) pairs that would need to be inserted in either map |
|
391 | // (key, value) pairs that would need to be inserted in either map | |
391 | // in order to turn it into the union. |
|
392 | // in order to turn it into the union. | |
392 | // |
|
393 | // | |
393 | // TODO: if/when https://github.com/bodil/im-rs/pull/168 is accepted, |
|
394 | // TODO: if/when https://github.com/bodil/im-rs/pull/168 is accepted, | |
394 | // change these from `Vec<(K, V)>` to `Vec<(&K, Cow<V>)>` |
|
395 | // change these from `Vec<(K, V)>` to `Vec<(&K, Cow<V>)>` | |
395 | // with `left_updates` only borrowing from `right` and `right_updates` from |
|
396 | // with `left_updates` only borrowing from `right` and `right_updates` from | |
396 | // `left`, and with `Cow::Owned` used for `MergeResult::UseNewValue`. |
|
397 | // `left`, and with `Cow::Owned` used for `MergeResult::UseNewValue`. | |
397 | // |
|
398 | // | |
398 | // This would allow moving all `.clone()` calls to after we’ve decided |
|
399 | // This would allow moving all `.clone()` calls to after we’ve decided | |
399 | // which of `right_updates` or `left_updates` to use |
|
400 | // which of `right_updates` or `left_updates` to use | |
400 | // (value ones becoming `Cow::into_owned`), |
|
401 | // (value ones becoming `Cow::into_owned`), | |
401 | // and avoid making clones we don’t end up using. |
|
402 | // and avoid making clones we don’t end up using. | |
402 | let mut left_updates = Vec::new(); |
|
403 | let mut left_updates = Vec::new(); | |
403 | let mut right_updates = Vec::new(); |
|
404 | let mut right_updates = Vec::new(); | |
404 |
|
405 | |||
405 | for difference in left.diff(&right) { |
|
406 | for difference in left.diff(&right) { | |
406 | match difference { |
|
407 | match difference { | |
407 | DiffItem::Add(key, value) => { |
|
408 | DiffItem::Add(key, value) => { | |
408 | left_updates.push((key.clone(), value.clone())) |
|
409 | left_updates.push((key.clone(), value.clone())) | |
409 | } |
|
410 | } | |
410 | DiffItem::Remove(key, value) => { |
|
411 | DiffItem::Remove(key, value) => { | |
411 | right_updates.push((key.clone(), value.clone())) |
|
412 | right_updates.push((key.clone(), value.clone())) | |
412 | } |
|
413 | } | |
413 | DiffItem::Update { |
|
414 | DiffItem::Update { | |
414 | old: (key, left_value), |
|
415 | old: (key, left_value), | |
415 | new: (_, right_value), |
|
416 | new: (_, right_value), | |
416 | } => match merge(key, left_value, right_value) { |
|
417 | } => match merge(key, left_value, right_value) { | |
417 | MergeResult::UseLeftValue => { |
|
418 | MergeResult::UseLeftValue => { | |
418 | right_updates.push((key.clone(), left_value.clone())) |
|
419 | right_updates.push((key.clone(), left_value.clone())) | |
419 | } |
|
420 | } | |
420 | MergeResult::UseRightValue => { |
|
421 | MergeResult::UseRightValue => { | |
421 | left_updates.push((key.clone(), right_value.clone())) |
|
422 | left_updates.push((key.clone(), right_value.clone())) | |
422 | } |
|
423 | } | |
423 | MergeResult::UseNewValue(new_value) => { |
|
424 | MergeResult::UseNewValue(new_value) => { | |
424 | left_updates.push((key.clone(), new_value.clone())); |
|
425 | left_updates.push((key.clone(), new_value.clone())); | |
425 | right_updates.push((key.clone(), new_value)) |
|
426 | right_updates.push((key.clone(), new_value)) | |
426 | } |
|
427 | } | |
427 | }, |
|
428 | }, | |
428 | } |
|
429 | } | |
429 | } |
|
430 | } | |
430 | if left_updates.len() < right_updates.len() { |
|
431 | if left_updates.len() < right_updates.len() { | |
431 | for (key, value) in left_updates { |
|
432 | for (key, value) in left_updates { | |
432 | left.insert(key, value); |
|
433 | left.insert(key, value); | |
433 | } |
|
434 | } | |
434 | left |
|
435 | left | |
435 | } else { |
|
436 | } else { | |
436 | for (key, value) in right_updates { |
|
437 | for (key, value) in right_updates { | |
437 | right.insert(key, value); |
|
438 | right.insert(key, value); | |
438 | } |
|
439 | } | |
439 | right |
|
440 | right | |
440 | } |
|
441 | } | |
441 | } |
|
442 | } | |
442 |
|
443 | |||
443 | /// Join items of the iterable with the given separator, similar to Python’s |
|
444 | /// Join items of the iterable with the given separator, similar to Python’s | |
444 | /// `separator.join(iter)`. |
|
445 | /// `separator.join(iter)`. | |
445 | /// |
|
446 | /// | |
446 | /// Formatting the return value consumes the iterator. |
|
447 | /// Formatting the return value consumes the iterator. | |
447 | /// Formatting it again will produce an empty string. |
|
448 | /// Formatting it again will produce an empty string. | |
448 | pub fn join_display( |
|
449 | pub fn join_display( | |
449 | iter: impl IntoIterator<Item = impl fmt::Display>, |
|
450 | iter: impl IntoIterator<Item = impl fmt::Display>, | |
450 | separator: impl fmt::Display, |
|
451 | separator: impl fmt::Display, | |
451 | ) -> impl fmt::Display { |
|
452 | ) -> impl fmt::Display { | |
452 | JoinDisplay { |
|
453 | JoinDisplay { | |
453 | iter: Cell::new(Some(iter.into_iter())), |
|
454 | iter: Cell::new(Some(iter.into_iter())), | |
454 | separator, |
|
455 | separator, | |
455 | } |
|
456 | } | |
456 | } |
|
457 | } | |
457 |
|
458 | |||
458 | struct JoinDisplay<I, S> { |
|
459 | struct JoinDisplay<I, S> { | |
459 | iter: Cell<Option<I>>, |
|
460 | iter: Cell<Option<I>>, | |
460 | separator: S, |
|
461 | separator: S, | |
461 | } |
|
462 | } | |
462 |
|
463 | |||
463 | impl<I, T, S> fmt::Display for JoinDisplay<I, S> |
|
464 | impl<I, T, S> fmt::Display for JoinDisplay<I, S> | |
464 | where |
|
465 | where | |
465 | I: Iterator<Item = T>, |
|
466 | I: Iterator<Item = T>, | |
466 | T: fmt::Display, |
|
467 | T: fmt::Display, | |
467 | S: fmt::Display, |
|
468 | S: fmt::Display, | |
468 | { |
|
469 | { | |
469 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
|
470 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
470 | if let Some(mut iter) = self.iter.take() { |
|
471 | if let Some(mut iter) = self.iter.take() { | |
471 | if let Some(first) = iter.next() { |
|
472 | if let Some(first) = iter.next() { | |
472 | first.fmt(f)?; |
|
473 | first.fmt(f)?; | |
473 | } |
|
474 | } | |
474 | for value in iter { |
|
475 | for value in iter { | |
475 | self.separator.fmt(f)?; |
|
476 | self.separator.fmt(f)?; | |
476 | value.fmt(f)?; |
|
477 | value.fmt(f)?; | |
477 | } |
|
478 | } | |
478 | } |
|
479 | } | |
479 | Ok(()) |
|
480 | Ok(()) | |
480 | } |
|
481 | } | |
481 | } |
|
482 | } |
General Comments 0
You need to be logged in to leave comments.
Login now