weavatrix_scan/
walker.rs

1use crate::walk_builder::{EntryFilter, EntrySorter};
2use crate::walk_platform::{
3    DirectoryIdentity, FileSystemId, PlatformDirectoryInfo, directory_info,
4};
5pub use crate::walk_types::{
6    ErrorPolicy, RootSymlinkPolicy, WalkEntry, WalkError, WalkOperation, WalkOptions,
7    WalkSkipReason,
8};
9use std::collections::{HashSet, VecDeque};
10use std::fs::{self, FileType};
11use std::io;
12use std::path::{Path, PathBuf};
13use std::sync::Arc;
14
15#[derive(Debug)]
16pub(crate) struct PendingDirectory {
17    pub(crate) path: PathBuf,
18    pub(crate) depth: usize,
19    pub(crate) identity: Option<DirectoryIdentity>,
20    pub(crate) post_entry: Option<WalkEntry>,
21}
22
23// Keeping ReadDir inline avoids one heap allocation per directory on the hot
24// traversal path; the stack is depth-bounded and buffered at max_open.
25#[allow(clippy::large_enum_variant)]
26pub(crate) enum DirectoryEntries {
27    Open(fs::ReadDir),
28    Buffered(VecDeque<io::Result<fs::DirEntry>>),
29}
30
31impl DirectoryEntries {
32    #[allow(clippy::inline_always)]
33    #[inline(always)]
34    pub(crate) fn next(&mut self) -> Option<io::Result<fs::DirEntry>> {
35        match self {
36            Self::Open(entries) => entries.next(),
37            Self::Buffered(entries) => entries.pop_front(),
38        }
39    }
40
41    #[allow(clippy::inline_always)]
42    #[inline(always)]
43    pub(crate) const fn is_open(&self) -> bool {
44        matches!(self, Self::Open(_))
45    }
46}
47
48pub(crate) struct DirectoryFrame {
49    pub(crate) path: PathBuf,
50    pub(crate) depth: usize,
51    pub(crate) entries: DirectoryEntries,
52    pub(crate) identity: Option<DirectoryIdentity>,
53    pub(crate) post_entry: Option<WalkEntry>,
54}
55
56/// Iterative depth-first filesystem walker.
57///
58/// Paths remain native `PathBuf` values; no lossy UTF-8 conversion occurs.
59/// Open directory handles are bounded by `WalkOptions::max_open`; when a deep
60/// tree reaches the limit, the oldest remaining directory entries are buffered
61/// and its handle is closed.
62#[allow(clippy::struct_excessive_bools)]
63pub struct Walker {
64    pub(crate) root: Arc<PathBuf>,
65    pub(crate) root_components: usize,
66    pub(crate) root_file_type: Option<FileType>,
67    pub(crate) root_bytes: Option<u64>,
68    pub(crate) root_version: Option<crate::FileVersion>,
69    pub(crate) root_file_system: Option<FileSystemId>,
70    pub(crate) root_directory_info: Option<PlatformDirectoryInfo>,
71    pub(crate) options: WalkOptions,
72    pub(crate) frames: Vec<DirectoryFrame>,
73    pub(crate) open_handles: usize,
74    pub(crate) yield_root: bool,
75    pub(crate) pending_directory: Option<PendingDirectory>,
76    pub(crate) skip_pending_directory: bool,
77    pub(crate) active_directories: HashSet<DirectoryIdentity>,
78    pub(crate) finished: bool,
79    pub(crate) sorter: Option<EntrySorter>,
80    pub(crate) filter: Option<EntryFilter>,
81    pub(crate) skip_stdout: Option<crate::FileIdentity>,
82    pub(crate) contents_first: bool,
83    pub(crate) deferred_entry: Option<WalkEntry>,
84    pub(crate) plain_entries: bool,
85}
86
87impl Walker {
88    /// Creates a walker with the default traversal policy.
89    ///
90    /// # Errors
91    ///
92    /// Returns an error when the root cannot be resolved or inspected.
93    pub fn new(root: impl AsRef<Path>) -> Result<Self, WalkError> {
94        Self::with_options(root, WalkOptions::default())
95    }
96
97    /// Creates a walker with an explicit traversal policy.
98    ///
99    /// # Errors
100    ///
101    /// Returns an error when the root cannot be resolved or inspected.
102    pub fn with_options(root: impl AsRef<Path>, options: WalkOptions) -> Result<Self, WalkError> {
103        Self::with_behavior(root, options, None, None, None, false)
104    }
105
106    pub(crate) fn with_behavior(
107        root: impl AsRef<Path>,
108        options: WalkOptions,
109        sorter: Option<EntrySorter>,
110        filter: Option<EntryFilter>,
111        skip_stdout: Option<crate::FileIdentity>,
112        contents_first: bool,
113    ) -> Result<Self, WalkError> {
114        let requested = root.as_ref();
115        let options = options.normalized();
116        if options.root_symlink_policy == RootSymlinkPolicy::Reject {
117            let metadata = fs::symlink_metadata(requested).map_err(|source| {
118                WalkError::new(requested, 0, WalkOperation::ReadMetadata, source)
119            })?;
120            if metadata.file_type().is_symlink() {
121                return Err(WalkError::new(
122                    requested,
123                    0,
124                    WalkOperation::ReadMetadata,
125                    io::Error::new(
126                        io::ErrorKind::InvalidInput,
127                        "root symlink rejected by policy",
128                    ),
129                ));
130            }
131        }
132        let canonical = if options.follow_links || options.same_file_system {
133            requested.canonicalize().map_err(|source| {
134                WalkError::new(requested, 0, WalkOperation::Canonicalize, source)
135            })?
136        } else if requested.is_absolute() {
137            requested.to_path_buf()
138        } else {
139            std::env::current_dir()
140                .map_err(|source| {
141                    WalkError::new(requested, 0, WalkOperation::Canonicalize, source)
142                })?
143                .join(requested)
144        };
145        let metadata = fs::metadata(&canonical)
146            .map_err(|source| WalkError::new(&canonical, 0, WalkOperation::ReadMetadata, source))?;
147        let root_directory_info =
148            if metadata.is_dir() && (options.follow_links || options.same_file_system) {
149                Some(directory_info(&canonical, &metadata).map_err(|source| {
150                    WalkError::new(&canonical, 0, WalkOperation::ReadMetadata, source)
151                })?)
152            } else {
153                None
154            };
155        let root_file_system = if options.same_file_system {
156            root_directory_info.map(|info| info.file_system)
157        } else {
158            None
159        };
160        let (root_bytes, root_version) = if options.collect_metadata && metadata.is_file() {
161            (
162                Some(metadata.len()),
163                Some(crate::file_version::from_metadata(&metadata)),
164            )
165        } else {
166            (None, None)
167        };
168        let plain_entries = !options.follow_links
169            && !options.same_file_system
170            && !options.collect_metadata
171            && options.max_depth.is_none()
172            && options.min_depth == 0
173            && filter.is_none()
174            && skip_stdout.is_none()
175            && !contents_first;
176        let root = Arc::new(canonical.clone());
177        Ok(Self {
178            root: Arc::clone(&root),
179            root_components: canonical.components().count(),
180            root_file_type: Some(metadata.file_type()),
181            root_bytes,
182            root_version,
183            root_file_system,
184            root_directory_info,
185            options,
186            frames: Vec::new(),
187            open_handles: 0,
188            yield_root: true,
189            pending_directory: None,
190            skip_pending_directory: false,
191            active_directories: HashSet::new(),
192            finished: false,
193            sorter,
194            filter,
195            skip_stdout,
196            contents_first,
197            deferred_entry: None,
198            plain_entries,
199        })
200    }
201
202    pub(crate) fn from_known_directory(
203        root: &Arc<PathBuf>,
204        directory: PathBuf,
205        depth: usize,
206        options: WalkOptions,
207        root_file_system: Option<FileSystemId>,
208    ) -> Self {
209        Self::from_known_directory_with_ancestry(
210            root,
211            directory,
212            depth,
213            options,
214            root_file_system,
215            None,
216            HashSet::new(),
217        )
218    }
219
220    pub(crate) fn from_known_directory_with_ancestry(
221        root: &Arc<PathBuf>,
222        directory: PathBuf,
223        depth: usize,
224        options: WalkOptions,
225        root_file_system: Option<FileSystemId>,
226        directory_identity: Option<DirectoryIdentity>,
227        active_directories: HashSet<DirectoryIdentity>,
228    ) -> Self {
229        let options = options.normalized();
230        let root_components = root.components().count();
231        let plain_entries = !options.follow_links
232            && !options.same_file_system
233            && !options.collect_metadata
234            && options.max_depth.is_none()
235            && options.min_depth == 0;
236        Self {
237            root: Arc::clone(root),
238            root_components,
239            root_file_type: None,
240            root_bytes: None,
241            root_version: None,
242            root_file_system,
243            root_directory_info: None,
244            options,
245            frames: Vec::new(),
246            open_handles: 0,
247            yield_root: false,
248            pending_directory: Some(PendingDirectory {
249                path: directory,
250                depth,
251                identity: directory_identity,
252                post_entry: None,
253            }),
254            skip_pending_directory: false,
255            active_directories,
256            finished: false,
257            sorter: None,
258            filter: None,
259            skip_stdout: None,
260            contents_first: false,
261            deferred_entry: None,
262            plain_entries,
263        }
264    }
265
266    #[must_use]
267    pub fn root(&self) -> &Path {
268        self.root.as_path()
269    }
270
271    #[must_use]
272    pub const fn options(&self) -> &WalkOptions {
273        &self.options
274    }
275
276    /// Prevents descent into the directory returned by the previous `next`.
277    pub fn skip_current_dir(&mut self) {
278        if self.pending_directory.is_some() {
279            self.skip_pending_directory = true;
280        }
281    }
282
283    pub(crate) fn schedule_pending_directory(&mut self) -> Option<WalkError> {
284        let pending = self.pending_directory.take()?;
285        if self.skip_pending_directory {
286            self.skip_pending_directory = false;
287            return None;
288        }
289        if self.open_handles >= self.options.max_open {
290            self.buffer_oldest_open_directory();
291        }
292        match fs::read_dir(&pending.path) {
293            Ok(entries) => {
294                if let Some(identity) = pending.identity {
295                    self.active_directories.insert(identity);
296                }
297                let (entries, opened) = match self.sorter.as_ref() {
298                    None => (DirectoryEntries::Open(entries), true),
299                    Some(sorter) => {
300                        let mut entries = entries.collect::<Vec<_>>();
301                        entries.sort_by(|left, right| match (left, right) {
302                            (Ok(left), Ok(right)) => sorter(left, right),
303                            (Err(_), Ok(_)) => std::cmp::Ordering::Less,
304                            (Ok(_), Err(_)) => std::cmp::Ordering::Greater,
305                            (Err(_), Err(_)) => std::cmp::Ordering::Equal,
306                        });
307                        (DirectoryEntries::Buffered(entries.into()), false)
308                    }
309                };
310                self.frames.push(DirectoryFrame {
311                    path: pending.path,
312                    depth: pending.depth,
313                    entries,
314                    identity: pending.identity,
315                    post_entry: pending.post_entry,
316                });
317                self.open_handles += usize::from(opened);
318                None
319            }
320            Err(source) => {
321                self.deferred_entry = pending.post_entry;
322                Some(WalkError::new(
323                    pending.path,
324                    pending.depth,
325                    WalkOperation::ReadDirectory,
326                    source,
327                ))
328            }
329        }
330    }
331
332    fn buffer_oldest_open_directory(&mut self) {
333        let Some(index) = self.frames.iter().position(|frame| frame.entries.is_open()) else {
334            return;
335        };
336        let placeholder = DirectoryEntries::Buffered(VecDeque::new());
337        let entries = std::mem::replace(&mut self.frames[index].entries, placeholder);
338        if let DirectoryEntries::Open(entries) = entries {
339            self.frames[index].entries = DirectoryEntries::Buffered(entries.collect());
340            self.open_handles -= 1;
341        }
342    }
343}
weavatrix_scan/walker.rs

weavatrix_scan/
walker.rs
