sourcemap/
utils.rs

1use std::borrow::Cow;
2use std::iter;
3
4fn split_path(path: &str) -> Vec<&str> {
5    let mut last_idx = 0;
6    let mut rv = vec![];
7    for (idx, _) in path.match_indices(&['/', '\\'][..]) {
8        rv.push(&path[last_idx..idx]);
9        last_idx = idx;
10    }
11    if last_idx < path.len() {
12        rv.push(&path[last_idx..]);
13    }
14    rv
15}
16
17fn is_abs_path(s: &str) -> bool {
18    if s.starts_with('/') {
19        return true;
20    } else if s.len() > 3 {
21        let b = s.as_bytes();
22        if b[1] == b':'
23            && (b[2] == b'/' || b[2] == b'\\')
24            && ((b[0] >= b'a' && b[0] <= b'z') || (b[0] >= b'A' && b[0] <= b'Z'))
25        {
26            return true;
27        }
28    }
29    false
30}
31
32fn find_common_prefix_of_sorted_vec<'a>(items: &'a [Cow<'a, [&'a str]>]) -> Option<&'a [&'a str]> {
33    if items.is_empty() {
34        return None;
35    }
36
37    let shortest = &items[0];
38    let mut max_idx = None;
39    for seq in items.iter() {
40        let mut seq_max_idx = None;
41        for (idx, &comp) in shortest.iter().enumerate() {
42            if seq.get(idx) != Some(&comp) {
43                break;
44            }
45            seq_max_idx = Some(idx);
46        }
47        if max_idx.is_none() || seq_max_idx < max_idx {
48            max_idx = seq_max_idx;
49        }
50    }
51
52    if let Some(max_idx) = max_idx {
53        Some(&shortest[..=max_idx])
54    } else {
55        None
56    }
57}
58
59pub fn find_common_prefix<'a, I: Iterator<Item = &'a str>>(iter: I) -> Option<String> {
60    let mut items: Vec<Cow<'_, [&str]>> = iter
61        .filter(|x| is_abs_path(x))
62        .map(|x| Cow::Owned(split_path(x)))
63        .collect();
64    items.sort_by_key(|x| x.len());
65
66    if let Some(slice) = find_common_prefix_of_sorted_vec(&items) {
67        let rv = slice.join("");
68        if !rv.is_empty() && &rv != "/" {
69            return Some(rv);
70        }
71    }
72
73    None
74}
75
76/// Helper function to calculate the path from a base file to a target file.
77///
78/// This is intended to caculate the path from a minified JavaScript file
79/// to a sourcemap if they are both on the same server.
80///
81/// Example:
82///
83/// ```
84/// # use sourcemap::make_relative_path;
85/// assert_eq!(&make_relative_path(
86///     "/foo/bar/baz.js", "/foo/baz.map"), "../baz.map");
87/// ```
88pub fn make_relative_path(base: &str, target: &str) -> String {
89    let target_path: Vec<_> = target
90        .split(&['/', '\\'][..])
91        .filter(|x| !x.is_empty())
92        .collect();
93    let mut base_path: Vec<_> = base
94        .split(&['/', '\\'][..])
95        .filter(|x| !x.is_empty())
96        .collect();
97    base_path.pop();
98
99    let mut items = vec![
100        Cow::Borrowed(target_path.as_slice()),
101        Cow::Borrowed(base_path.as_slice()),
102    ];
103    items.sort_by_key(|x| x.len());
104
105    let prefix = find_common_prefix_of_sorted_vec(&items)
106        .map(|x| x.len())
107        .unwrap_or(0);
108    let mut rel_list: Vec<_> = iter::repeat_n("../", base_path.len() - prefix).collect();
109    rel_list.extend_from_slice(&target_path[prefix..]);
110    if rel_list.is_empty() {
111        ".".into()
112    } else {
113        rel_list.join("")
114    }
115}
116
117pub fn greatest_lower_bound<'a, T, K: Ord, F: Fn(&'a T) -> K>(
118    slice: &'a [T],
119    key: &K,
120    map: F,
121) -> Option<(usize, &'a T)> {
122    let mut idx = match slice.binary_search_by_key(key, &map) {
123        Ok(index) => index,
124        Err(index) => {
125            // If there is no match, then we know for certain that the index is where we should
126            // insert a new token, and that the token directly before is the greatest lower bound.
127            return slice.get(index.checked_sub(1)?).map(|res| (index, res));
128        }
129    };
130
131    // If we get an exact match, then we need to continue looking at previous tokens to see if
132    // they also match. We use a linear search because the number of exact matches is generally
133    // very small, and almost certainly smaller than the number of tokens before the index.
134    for i in (0..idx).rev() {
135        if map(&slice[i]) == *key {
136            idx = i;
137        } else {
138            break;
139        }
140    }
141    slice.get(idx).map(|res| (idx, res))
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn test_is_abs_path() {
150        assert!(is_abs_path("C:\\foo.txt"));
151        assert!(is_abs_path("d:/foo.txt"));
152        assert!(!is_abs_path("foo.txt"));
153        assert!(is_abs_path("/foo.txt"));
154        assert!(is_abs_path("/"));
155    }
156
157    #[test]
158    fn test_split_path() {
159        assert_eq!(split_path("/foo/bar/baz"), &["", "/foo", "/bar", "/baz"]);
160    }
161
162    #[test]
163    fn test_find_common_prefix() {
164        let rv = find_common_prefix(vec!["/foo/bar/baz", "/foo/bar/baz/blah"].into_iter());
165        assert_eq!(rv, Some("/foo/bar/baz".into()));
166
167        let rv = find_common_prefix(vec!["/foo/bar/baz", "/foo/bar/baz/blah", "/meh"].into_iter());
168        assert_eq!(rv, None);
169
170        let rv = find_common_prefix(vec!["/foo/bar/baz", "/foo/bar/baz/blah", "/foo"].into_iter());
171        assert_eq!(rv, Some("/foo".into()));
172
173        let rv = find_common_prefix(vec!["/foo/bar/baz", "/foo/bar/baz/blah", "foo"].into_iter());
174        assert_eq!(rv, Some("/foo/bar/baz".into()));
175
176        let rv = find_common_prefix(
177            vec!["/foo/bar/baz", "/foo/bar/baz/blah", "/blah", "foo"].into_iter(),
178        );
179        assert_eq!(rv, None);
180
181        let rv = find_common_prefix(
182            vec!["/foo/bar/baz", "/foo/bar/baz/blah", "/blah", "foo"].into_iter(),
183        );
184        assert_eq!(rv, None);
185    }
186
187    #[test]
188    fn test_make_relative_path() {
189        assert_eq!(
190            &make_relative_path("/foo/bar/baz.js", "/foo/bar/baz.map"),
191            "baz.map"
192        );
193        assert_eq!(
194            &make_relative_path("/foo/bar/.", "/foo/bar/baz.map"),
195            "baz.map"
196        );
197        assert_eq!(
198            &make_relative_path("/foo/bar/baz.js", "/foo/baz.map"),
199            "../baz.map"
200        );
201        assert_eq!(&make_relative_path("foo.txt", "foo.js"), "foo.js");
202        assert_eq!(&make_relative_path("blah/foo.txt", "foo.js"), "../foo.js");
203    }
204
205    #[test]
206    fn test_greatest_lower_bound() {
207        let cmp = |&(i, _id)| i;
208
209        let haystack = vec![(1, 1)];
210        assert_eq!(greatest_lower_bound(&haystack, &1, cmp).unwrap().1, &(1, 1));
211        assert_eq!(greatest_lower_bound(&haystack, &2, cmp).unwrap().1, &(1, 1));
212        assert_eq!(greatest_lower_bound(&haystack, &0, cmp), None);
213
214        let haystack = vec![(1, 1), (1, 2)];
215        assert_eq!(greatest_lower_bound(&haystack, &1, cmp).unwrap().1, &(1, 1));
216        assert_eq!(greatest_lower_bound(&haystack, &2, cmp).unwrap().1, &(1, 2));
217        assert_eq!(greatest_lower_bound(&haystack, &0, cmp), None);
218
219        let haystack = vec![(1, 1), (1, 2), (1, 3)];
220        assert_eq!(greatest_lower_bound(&haystack, &1, cmp).unwrap().1, &(1, 1));
221        assert_eq!(greatest_lower_bound(&haystack, &2, cmp).unwrap().1, &(1, 3));
222        assert_eq!(greatest_lower_bound(&haystack, &0, cmp), None);
223
224        let haystack = vec![(1, 1), (1, 2), (1, 3), (1, 4)];
225        assert_eq!(greatest_lower_bound(&haystack, &1, cmp).unwrap().1, &(1, 1));
226        assert_eq!(greatest_lower_bound(&haystack, &2, cmp).unwrap().1, &(1, 4));
227        assert_eq!(greatest_lower_bound(&haystack, &0, cmp), None);
228
229        let haystack = vec![(1, 1), (1, 2), (1, 3), (1, 4), (1, 5)];
230        assert_eq!(greatest_lower_bound(&haystack, &1, cmp).unwrap().1, &(1, 1));
231        assert_eq!(greatest_lower_bound(&haystack, &2, cmp).unwrap().1, &(1, 5));
232        assert_eq!(greatest_lower_bound(&haystack, &0, cmp), None);
233    }
234}
sourcemap/utils.rs

sourcemap/
utils.rs
