vfsi_sync/
traversal.rs

1//! Incremental, no-follow traversal shared by application adapters.
2use crate::{DirEntry, ReadDirOptions, TraversalCompletion, VfError, VfResult, WalkOptions};
3use std::path::Path;
4
5/// Callback decision. Pruning never reads the directory's contents.
6#[derive(Debug, Clone, Copy, PartialEq, Eq)]
7pub enum WalkControl {
8    Continue,
9    SkipSubtree,
10    Stop,
11}
12/// Enter/Leave surround a directory, including a pruned directory.
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub enum WalkEventKind {
15    Enter,
16    Entry,
17    Leave,
18}
19/// Root is depth zero. Symlinks are Entry events and are never followed.
20#[derive(Debug, Clone)]
21pub struct WalkEvent {
22    pub kind: WalkEventKind,
23    pub entry: DirEntry,
24    pub depth: usize,
25}
26
27/// Adapter hook; application callers should use their client's method.
28/// Each directory is bounded before sorting; only the active frontier is kept.
29/// Limits charge fetched entries (including the root), even if later pruned.
30#[doc(hidden)]
31pub fn walk_events(
32    root: DirEntry,
33    options: WalkOptions,
34    sort_by_name: bool,
35    mut read_dir: impl FnMut(&Path, ReadDirOptions) -> VfResult<Vec<DirEntry>>,
36    mut callback: impl FnMut(&WalkEvent) -> VfResult<WalkControl>,
37) -> VfResult<TraversalCompletion> {
38    let mut count = 1usize;
39    let mut bytes = root.path().as_os_str().len();
40    if count > options.entry_limit() || bytes > options.path_byte_limit() {
41        return Err(VfError::client(0, libc::EFBIG as u32));
42    }
43    let kind = if root.metadata().is_dir() {
44        WalkEventKind::Enter
45    } else {
46        WalkEventKind::Entry
47    };
48    let mut pending = vec![WalkEvent {
49        kind,
50        entry: root,
51        depth: 0,
52    }];
53    while let Some(event) = pending.pop() {
54        match callback(&event)? {
55            WalkControl::Stop => return Ok(TraversalCompletion::Stopped),
56            decision if event.kind == WalkEventKind::Enter => {
57                pending.push(WalkEvent {
58                    kind: WalkEventKind::Leave,
59                    ..event.clone()
60                });
61                if decision == WalkControl::SkipSubtree {
62                    continue;
63                }
64                if event.depth >= options.depth_limit() && options.truncates_at_depth_limit() {
65                    continue;
66                }
67                let remaining = ReadDirOptions::new()
68                    .max_entries(options.entry_limit().saturating_sub(count))
69                    .max_path_bytes(options.path_byte_limit().saturating_sub(bytes));
70                let mut entries = read_dir(event.entry.path(), remaining)?;
71                for entry in &entries {
72                    count = count
73                        .checked_add(1)
74                        .ok_or_else(|| VfError::client(0, libc::EFBIG as u32))?;
75                    bytes = bytes
76                        .checked_add(entry.path().as_os_str().len())
77                        .ok_or_else(|| VfError::client(0, libc::EFBIG as u32))?;
78                    if count > options.entry_limit()
79                        || bytes > options.path_byte_limit()
80                        || event.depth >= options.depth_limit()
81                    {
82                        return Err(VfError::client(0, libc::EFBIG as u32)
83                            .with_context("walk_events", entry.path()));
84                    }
85                }
86                if sort_by_name {
87                    entries.sort_by(|a, b| a.file_name().cmp(&b.file_name()));
88                }
89                for entry in entries.into_iter().rev() {
90                    let kind = if entry.metadata().is_dir() {
91                        WalkEventKind::Enter
92                    } else {
93                        WalkEventKind::Entry
94                    };
95                    pending.push(WalkEvent {
96                        kind,
97                        entry,
98                        depth: event.depth + 1,
99                    });
100                }
101            }
102            _ => {}
103        }
104    }
105    Ok(TraversalCompletion::Complete)
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111    use crate::{AttrMask, VfAttrs, VfFile, VfType};
112    fn entry(path: &str, dir: bool) -> DirEntry {
113        DirEntry::new(
114            path.into(),
115            crate::metadata_from_attrs(VfAttrs {
116                file: VfFile::from_path(path),
117                masks: AttrMask::MODE,
118                ftype: if dir {
119                    VfType::Directory
120                } else {
121                    VfType::Regular
122                },
123                ..Default::default()
124            }),
125        )
126    }
127    #[test]
128    fn prune_prevents_io_and_events_have_depth_first_order() {
129        let mut events = Vec::new();
130        walk_events(
131            entry("/", true),
132            WalkOptions::default(),
133            true,
134            |path, _| {
135                assert_eq!(path, Path::new("/"), "pruned directory must not be read");
136                Ok(vec![entry("/z", false), entry("/a", true)])
137            },
138            |event| {
139                events.push((event.kind, event.entry.path().to_path_buf(), event.depth));
140                Ok(if event.entry.path() == Path::new("/a") {
141                    WalkControl::SkipSubtree
142                } else {
143                    WalkControl::Continue
144                })
145            },
146        )
147        .unwrap();
148        assert_eq!(
149            events
150                .iter()
151                .map(|e| (e.0, e.1.as_path(), e.2))
152                .collect::<Vec<_>>(),
153            vec![
154                (WalkEventKind::Enter, Path::new("/"), 0),
155                (WalkEventKind::Enter, Path::new("/a"), 1),
156                (WalkEventKind::Leave, Path::new("/a"), 1),
157                (WalkEventKind::Entry, Path::new("/z"), 1),
158                (WalkEventKind::Leave, Path::new("/"), 0)
159            ]
160        );
161    }
162    #[test]
163    fn stop_error_and_limits_do_not_read_descendants() {
164        assert_eq!(
165            walk_events(
166                entry("/", true),
167                WalkOptions::default(),
168                false,
169                |_, _| panic!("stopped"),
170                |_| Ok(WalkControl::Stop)
171            )
172            .unwrap(),
173            TraversalCompletion::Stopped
174        );
175        assert!(
176            walk_events(
177                entry("/", true),
178                WalkOptions::default(),
179                false,
180                |_, _| panic!("callback failed"),
181                |_| Err(VfError::client(0, libc::EIO as u32))
182            )
183            .is_err()
184        );
185        for options in [
186            WalkOptions::new().max_entries(1),
187            WalkOptions::new().max_path_bytes(1),
188            WalkOptions::new().max_depth(0),
189        ] {
190            assert_eq!(
191                walk_events(
192                    entry("/", true),
193                    options,
194                    false,
195                    |path, _| {
196                        assert_eq!(path, Path::new("/"));
197                        Ok(vec![entry("/a", true)])
198                    },
199                    |_| Ok(WalkControl::Continue)
200                )
201                .unwrap_err()
202                .err_no(),
203                libc::EFBIG as u32
204            );
205        }
206    }
207}
vfsi_sync/traversal.rs

vfsi_sync/
traversal.rs
