rune/workspace/
glob.rs

Help
1#[cfg(test)]
2mod tests;
3
4use std::fmt;
5use std::fs;
6use std::io;
7use std::mem;
8use std::path::{Path, PathBuf};
9
10use crate as rune;
11use crate::alloc::prelude::*;
12use crate::alloc::{self, Box, Vec, VecDeque};
13
14use relative_path::RelativePath;
15
16/// Errors raised during glob expansion.
17#[derive(Debug)]
18pub enum GlobError {
19    Io(io::Error),
20    Alloc(alloc::Error),
21}
22
23impl From<io::Error> for GlobError {
24    fn from(error: io::Error) -> Self {
25        Self::Io(error)
26    }
27}
28
29impl From<alloc::Error> for GlobError {
30    fn from(error: alloc::Error) -> Self {
31        Self::Alloc(error)
32    }
33}
34
35impl fmt::Display for GlobError {
36    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37        match self {
38            GlobError::Io(error) => error.fmt(f),
39            GlobError::Alloc(error) => error.fmt(f),
40        }
41    }
42}
43
44impl core::error::Error for GlobError {
45    fn source(&self) -> Option<&(dyn core::error::Error + 'static)> {
46        match self {
47            GlobError::Io(error) => Some(error),
48            _ => None,
49        }
50    }
51}
52
53/// A compiled glob expression.
54pub struct Glob<'a> {
55    root: &'a Path,
56    components: Vec<Component<'a>>,
57}
58
59impl<'a> Glob<'a> {
60    /// Construct a new glob pattern.
61    pub fn new<R, P>(root: &'a R, pattern: &'a P) -> alloc::Result<Self>
62    where
63        R: ?Sized + AsRef<Path>,
64        P: ?Sized + AsRef<RelativePath>,
65    {
66        let components = compile_pattern(pattern)?;
67
68        Ok(Self {
69            root: root.as_ref(),
70            components,
71        })
72    }
73
74    /// Construct a new matcher.
75    pub(crate) fn matcher(&self) -> alloc::Result<Matcher<'_>> {
76        Ok(Matcher {
77            queue: [(self.root.to_path_buf(), self.components.as_ref())]
78                .into_iter()
79                .try_collect()?,
80        })
81    }
82}
83
84impl<'a> Matcher<'a> {
85    /// Perform an expansion in the filesystem.
86    fn expand_filesystem<M>(
87        &mut self,
88        path: &Path,
89        rest: &'a [Component<'a>],
90        mut m: M,
91    ) -> Result<(), GlobError>
92    where
93        M: FnMut(&str) -> alloc::Result<bool>,
94    {
95        let io_path = if path.as_os_str().is_empty() {
96            Path::new(std::path::Component::CurDir.as_os_str())
97        } else {
98            path
99        };
100
101        match fs::metadata(io_path) {
102            Ok(m) => {
103                if !m.is_dir() {
104                    return Ok(());
105                }
106            }
107            Err(e) if e.kind() == io::ErrorKind::NotFound => {
108                return Ok(());
109            }
110            Err(e) => return Err(e.into()),
111        }
112
113        for e in fs::read_dir(io_path)? {
114            let e = e?;
115            let file_name = e.file_name();
116            let c = file_name.to_string_lossy();
117
118            if !m(c.as_ref())? {
119                continue;
120            }
121
122            let mut new = path.to_path_buf();
123            new.push(file_name);
124            self.queue.try_push_back((new, rest))?;
125        }
126
127        Ok(())
128    }
129
130    /// Perform star star expansion.
131    fn walk(&mut self, path: &Path, rest: &'a [Component<'a>]) -> Result<(), GlobError> {
132        self.queue.try_push_back((path.to_path_buf(), rest))?;
133
134        let mut queue = VecDeque::new();
135        queue.try_push_back(path.to_path_buf())?;
136
137        while let Some(path) = queue.pop_front() {
138            let io_path = if path.as_os_str().is_empty() {
139                Path::new(std::path::Component::CurDir.as_os_str())
140            } else {
141                path.as_path()
142            };
143
144            match fs::metadata(io_path) {
145                Ok(m) => {
146                    if !m.is_dir() {
147                        return Ok(());
148                    }
149                }
150                Err(e) if e.kind() == io::ErrorKind::NotFound => {
151                    continue;
152                }
153                Err(e) => return Err(e.into()),
154            }
155
156            for e in fs::read_dir(io_path)? {
157                let next = e?.path();
158                self.queue.try_push_back((next.clone(), rest))?;
159                queue.try_push_back(next)?;
160            }
161        }
162
163        Ok(())
164    }
165}
166
167pub(crate) struct Matcher<'a> {
168    queue: VecDeque<(PathBuf, &'a [Component<'a>])>,
169}
170
171impl Iterator for Matcher<'_> {
172    type Item = Result<PathBuf, GlobError>;
173
174    fn next(&mut self) -> Option<Self::Item> {
175        'outer: loop {
176            let (mut path, mut components) = self.queue.pop_front()?;
177
178            while let [first, rest @ ..] = components {
179                match first {
180                    Component::ParentDir => {
181                        path = path.join(std::path::Component::ParentDir);
182                    }
183                    Component::Normal(normal) => {
184                        path = path.join(normal);
185                    }
186                    Component::Fragment(fragment) => {
187                        if let Err(e) =
188                            self.expand_filesystem(&path, rest, |name| fragment.is_match(name))
189                        {
190                            return Some(Err(e));
191                        }
192
193                        continue 'outer;
194                    }
195                    Component::StarStar => {
196                        if let Err(e) = self.walk(&path, rest) {
197                            return Some(Err(e));
198                        }
199
200                        continue 'outer;
201                    }
202                }
203
204                components = rest;
205            }
206
207            return Some(Ok(path));
208        }
209    }
210}
211
212#[derive(Debug, TryClone)]
213enum Component<'a> {
214    /// Parent directory.
215    ParentDir,
216    /// A normal component.
217    Normal(#[try_clone(copy)] &'a str),
218    /// Normal component, compiled into a fragment.
219    Fragment(Fragment<'a>),
220    /// `**` component, which keeps expanding.
221    StarStar,
222}
223
224fn compile_pattern<P>(pattern: &P) -> alloc::Result<Vec<Component<'_>>>
225where
226    P: ?Sized + AsRef<RelativePath>,
227{
228    let pattern = pattern.as_ref();
229
230    let mut output = Vec::new();
231
232    for c in pattern.components() {
233        output.try_push(match c {
234            relative_path::Component::CurDir => continue,
235            relative_path::Component::ParentDir => Component::ParentDir,
236            relative_path::Component::Normal("**") => Component::StarStar,
237            relative_path::Component::Normal(normal) => {
238                let fragment = Fragment::parse(normal)?;
239
240                if let Some(normal) = fragment.as_literal() {
241                    Component::Normal(normal)
242                } else {
243                    Component::Fragment(fragment)
244                }
245            }
246        })?;
247    }
248
249    Ok(output)
250}
251
252#[derive(Debug, TryClone, Clone, Copy)]
253#[try_clone(copy)]
254enum Part<'a> {
255    Star,
256    Literal(&'a str),
257}
258
259/// A match fragment.
260#[derive(Debug, TryClone)]
261pub(crate) struct Fragment<'a> {
262    parts: Box<[Part<'a>]>,
263}
264
265impl<'a> Fragment<'a> {
266    pub(crate) fn parse(string: &'a str) -> alloc::Result<Fragment<'a>> {
267        let mut literal = true;
268        let mut parts = Vec::new();
269        let mut start = None;
270
271        for (n, c) in string.char_indices() {
272            match c {
273                '*' => {
274                    if let Some(s) = start.take() {
275                        parts.try_push(Part::Literal(&string[s..n]))?;
276                    }
277
278                    if mem::take(&mut literal) {
279                        parts.try_push(Part::Star)?;
280                    }
281                }
282                _ => {
283                    if start.is_none() {
284                        start = Some(n);
285                    }
286
287                    literal = true;
288                }
289            }
290        }
291
292        if let Some(s) = start {
293            parts.try_push(Part::Literal(&string[s..]))?;
294        }
295
296        Ok(Fragment {
297            parts: parts.try_into()?,
298        })
299    }
300
301    /// Test if the given string matches the current fragment.
302    pub(crate) fn is_match(&self, string: &str) -> alloc::Result<bool> {
303        let mut backtrack = VecDeque::new();
304        backtrack.try_push_back((self.parts.as_ref(), string))?;
305
306        while let Some((mut parts, mut string)) = backtrack.pop_front() {
307            while let Some(part) = parts.first() {
308                match part {
309                    Part::Star => {
310                        // Peek the next literal component. If we have a
311                        // trailing wildcard (which this constitutes) then it
312                        // is by definition a match.
313                        let Some(Part::Literal(peek)) = parts.get(1) else {
314                            return Ok(true);
315                        };
316
317                        let Some(peek) = peek.chars().next() else {
318                            return Ok(true);
319                        };
320
321                        while let Some(c) = string.chars().next() {
322                            if c == peek {
323                                backtrack.try_push_front((
324                                    parts,
325                                    string.get(c.len_utf8()..).unwrap_or_default(),
326                                ))?;
327                                break;
328                            }
329
330                            string = string.get(c.len_utf8()..).unwrap_or_default();
331                        }
332                    }
333                    Part::Literal(literal) => {
334                        // The literal component must be an exact prefix of the
335                        // current string.
336                        let Some(remainder) = string.strip_prefix(literal) else {
337                            return Ok(false);
338                        };
339
340                        string = remainder;
341                    }
342                }
343
344                parts = parts.get(1..).unwrap_or_default();
345            }
346
347            if string.is_empty() {
348                return Ok(true);
349            }
350        }
351
352        Ok(false)
353    }
354
355    /// Treat the fragment as a single normal component.
356    fn as_literal(&self) -> Option<&'a str> {
357        if let [Part::Literal(one)] = self.parts.as_ref() {
358            Some(one)
359        } else {
360            None
361        }
362    }
363}
rune/workspace/glob.rs

rune/workspace/
glob.rs
