swc_sourcemap/
utils.rs

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

swc_sourcemap/
utils.rs
