oxedyne/fe2o3/fe2o3_file/src/walk.rs
33.3 KiB, 106 runs
created by r1870400018:70645, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | //! A directory walk that honours nested ignore files, over any listing source. |
| 2 | //! |
| 3 | //! The walk is a pull-based state machine, [`Walk`], with no I/O of its own. The caller asks |
| 4 | //! [`Walk::next`] what to do and answers each request: a [`Step::List`] with [`Walk::listed`], a |
| 5 | //! [`Step::Read`] with [`Walk::read`]. That keeps every await point in the caller, so a browser |
| 6 | //! engine listing the origin-private file system or a File System Access handle drives the same |
| 7 | //! walk as a disk source, awaiting its own listings between steps and yielding to its event loop |
| 8 | //! whenever it likes: |
| 9 | //! |
| 10 | //! ```ignore |
| 11 | //! let mut walk = Walk::new(20_000); |
| 12 | //! loop { |
| 13 | //! match res!(walk.next()) { |
| 14 | //! Step::List(dir) => res!(walk.listed(list_dir(&dir).await)), |
| 15 | //! Step::Read(path) => res!(walk.read(read_file(&path).await)), |
| 16 | //! Step::Entry(entry) => found.push(entry), |
| 17 | //! Step::Stopped(rep) => { report = Some(rep); break; } |
| 18 | //! Step::Done => break, |
| 19 | //! } |
| 20 | //! } |
| 21 | //! ``` |
| 22 | //! |
| 23 | //! A synchronous source implements [`WalkSource`] and hands itself to [`Walk::run`]; [`Disk`] is |
| 24 | //! that source over `std::fs`. |
| 25 | //! |
| 26 | //! The rules are git's. Each directory's `.gitignore` and `.oreignore` (by default) speak for |
| 27 | //! paths beneath that directory, relative to it; a deeper file outranks a shallower one, a later |
| 28 | //! name in the list outranks an earlier one in the same directory, and within one file the last |
| 29 | //! matching pattern decides, so `!` re-includes. An ignored directory is never listed, which is |
| 30 | //! both git's rule that nothing inside it can be re-included and the point of the walk: the cost |
| 31 | //! of `.ore/` or `node_modules/` is one entry, not every entry beneath. Beneath every file lie |
| 32 | //! built-in defaults ([`WALK_DEFAULTS`]), which a repository's own `!node_modules/` overrides. |
| 33 | //! |
| 34 | //! Two more layers sit where git puts them. A directory holding a `.git` directory has its |
| 35 | //! `.git/info/exclude` read first and laid at that directory beneath its own ignore files, so it |
| 36 | //! ranks below every in-tree file of the repository. A `.git` file (a linked worktree or a |
| 37 | //! submodule) points outside the tree and is not followed. Global excludes, git's |
| 38 | //! `core.excludesFile`, are given with [`Walk::with_excludes`] and lie just above the defaults; on |
| 39 | //! a native target [`git_global_excludes`] finds and reads them. A browser cannot see the user's |
| 40 | //! git configuration, so a walk there has no global layer unless the caller supplies one. |
| 41 | //! |
| 42 | //! [`Walk::beneath`] starts the walk at a directory inside the root while keeping entry paths |
| 43 | //! relative to the root, reading the ignore files of every directory above the start without |
| 44 | //! listing any of them. [`Walk::rules`] hands back every file the walk read as [`Rules`], which |
| 45 | //! answers for any path the same way the walk did, and names the file that decided. |
| 46 | //! |
| 47 | //! Every listed entry, kept or ignored, spends one unit of the entry budget. When it runs out the |
| 48 | //! walk ends with a [`WalkBudget`] saying how far it got, so a caller can tell a search that found |
| 49 | //! nothing from one that stopped early. |
| 50 | //! |
| 51 | //! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\ |
| 52 | //! Anthropic Claude |
| 53 | |
| 54 | use crate::glob::IgnoreFile; |
| 55 | use crate::limits::Limits; |
| 56 | |
| 57 | use oxedyne_fe2o3_core::prelude::*; |
| 58 | |
| 59 | use std::{ |
| 60 | collections::VecDeque, |
| 61 | fs, |
| 62 | io::{ |
| 63 | self, |
| 64 | Read, |
| 65 | }, |
| 66 | path::{ |
| 67 | Path, |
| 68 | PathBuf, |
| 69 | }, |
| 70 | }; |
| 71 | |
| 72 | |
| 73 | // Directories no walk wants by default: version-control stores, tool state, Syncthing's history and |
| 74 | // dependency or build output. Laid beneath every ignore file, so a repository can re-include one. |
| 75 | pub const WALK_DEFAULTS: &[&str] = &[ |
| 76 | ".git/", // git |
| 77 | ".hg/", // Mercurial |
| 78 | ".svn/", // Subversion |
| 79 | ".ore/", // Ore |
| 80 | ".claude/", // agent state, including whole worktree copies |
| 81 | ".stversions/", // Syncthing's old versions |
| 82 | "node_modules/", // npm dependencies |
| 83 | "target/", // cargo build output |
| 84 | ]; |
| 85 | |
| 86 | // The ignore files read in each directory, lowest priority first. |
| 87 | pub const IGNORE_NAMES: &[&str] = &[ |
| 88 | ".gitignore", |
| 89 | ".oreignore", |
| 90 | ]; |
| 91 | |
| 92 | pub const REPO_MARKS: &[&str] = &[".git", ".ore"]; // what a repository's top holds |
| 93 | pub const REPO_EXCLUDE: &str = ".git/info/exclude"; // a repository's own excludes, below its files |
| 94 | pub const EXCLUDES_NAME: &str = "core.excludesFile"; // how Rules::why names the global excludes |
| 95 | |
| 96 | /// One name from a directory listing, as the caller's source gives it. |
| 97 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 98 | pub struct Listed { |
| 99 | pub name: Vec<u8>, // one component, no slash |
| 100 | pub is_dir: bool, |
| 101 | } |
| 102 | |
| 103 | impl Listed { |
| 104 | pub fn new<N: Into<Vec<u8>>>(name: N, is_dir: bool) -> Self { |
| 105 | Self { name: name.into(), is_dir } |
| 106 | } |
| 107 | } |
| 108 | |
| 109 | /// One entry the walk kept. |
| 110 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 111 | pub struct WalkEntry { |
| 112 | pub path: Vec<u8>, // relative to the walk's root, components joined by `/` |
| 113 | pub is_dir: bool, |
| 114 | } |
| 115 | |
| 116 | /// How far a walk got before its entry budget ran out. |
| 117 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 118 | pub struct WalkBudget { |
| 119 | pub budget: usize, // the entries allowed |
| 120 | pub kept: usize, // entries yielded |
| 121 | pub ignored: usize, // entries listed but ignored |
| 122 | pub unlisted: usize, // kept directories never listed |
| 123 | pub at: Vec<u8>, // the directory being listed when it ran out |
| 124 | } |
| 125 | |
| 126 | /// What the caller is to do next. |
| 127 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 128 | pub enum Step { |
| 129 | List(Vec<u8>), // list this directory, then call `listed` |
| 130 | Read(Vec<u8>), // read this ignore file, then call `read` |
| 131 | Entry(WalkEntry), // a kept file or directory |
| 132 | Stopped(WalkBudget), // the budget ran out; the walk is over |
| 133 | Done, // everything not ignored has been yielded |
| 134 | } |
| 135 | |
| 136 | /// How [`Walk::run`] ended. |
| 137 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 138 | pub enum WalkEnd { |
| 139 | Complete, |
| 140 | Budget(WalkBudget), |
| 141 | Halted, // the visitor asked to stop |
| 142 | } |
| 143 | |
| 144 | /// A synchronous listing source for [`Walk::run`]. |
| 145 | pub trait WalkSource { |
| 146 | /// Lists one directory, given relative to the walk's root (empty for the root itself). |
| 147 | fn list(&mut self, dir: &[u8]) -> Outcome<Vec<Listed>>; |
| 148 | /// Reads one ignore file; `None` when it has gone or cannot be read. |
| 149 | fn read(&mut self, path: &[u8]) -> Outcome<Option<Vec<u8>>>; |
| 150 | } |
| 151 | |
| 152 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] |
| 153 | enum Want { |
| 154 | Nothing, |
| 155 | Listing, |
| 156 | File, |
| 157 | } |
| 158 | |
| 159 | // One ignore file, scoped to the directory it sits in, chained to the one that ranks below it. |
| 160 | #[derive(Clone, Debug)] |
| 161 | struct Layer { |
| 162 | base: Vec<u8>, // the directory it speaks for |
| 163 | path: Vec<u8>, // the file itself, relative to the root |
| 164 | rank: usize, // its order among one directory's files, lowest first |
| 165 | file: IgnoreFile, |
| 166 | below: Option<usize>, |
| 167 | } |
| 168 | |
| 169 | // An ignore file still to be read. |
| 170 | #[derive(Clone, Debug)] |
| 171 | struct Owed { |
| 172 | path: Vec<u8>, |
| 173 | rank: usize, |
| 174 | } |
| 175 | |
| 176 | /// An ignore-aware depth-first walk. See the module documentation. |
| 177 | #[derive(Debug)] |
| 178 | pub struct Walk { |
| 179 | defaults: IgnoreFile, |
| 180 | excludes: IgnoreFile, // global excludes, just above the defaults |
| 181 | names: Vec<Vec<u8>>, |
| 182 | layers: Vec<Layer>, // arena of every ignore file read |
| 183 | pending: Vec<(Vec<u8>, Option<usize>)>, // directories to list, with their top layer |
| 184 | climb: VecDeque<Vec<u8>>, // root down to the start, not yet opened |
| 185 | start_ign: bool, // the start or a directory above it is ignored |
| 186 | dir: Vec<u8>, // the directory whose listing is being worked |
| 187 | top: Option<usize>, // its top layer |
| 188 | entries: VecDeque<Listed>, // its listing, not yet judged |
| 189 | reads: VecDeque<Owed>, // its ignore files, not yet read |
| 190 | children: Vec<Vec<u8>>, // its kept subdirectories |
| 191 | want: Want, |
| 192 | budget: usize, |
| 193 | kept: usize, |
| 194 | ignored: usize, |
| 195 | over: bool, |
| 196 | } |
| 197 | |
| 198 | impl Walk { |
| 199 | |
| 200 | /// A walk from the root, reading [`IGNORE_NAMES`] above [`WALK_DEFAULTS`], allowed `budget` |
| 201 | /// listed entries. |
| 202 | pub fn new(budget: usize) -> Self { |
| 203 | let defaults = IgnoreFile::parse(WALK_DEFAULTS.join("\n").as_bytes()); |
| 204 | Self { |
| 205 | defaults, |
| 206 | excludes: IgnoreFile::default(), |
| 207 | names: IGNORE_NAMES.iter().map(|n| n.as_bytes().to_vec()).collect(), |
| 208 | layers: Vec::new(), |
| 209 | pending: vec![(Vec::new(), None)], |
| 210 | climb: VecDeque::new(), |
| 211 | start_ign: false, |
| 212 | dir: Vec::new(), |
| 213 | top: None, |
| 214 | entries: VecDeque::new(), |
| 215 | reads: VecDeque::new(), |
| 216 | children: Vec::new(), |
| 217 | want: Want::Nothing, |
| 218 | budget, |
| 219 | kept: 0, |
| 220 | ignored: 0, |
| 221 | over: false, |
| 222 | } |
| 223 | } |
| 224 | |
| 225 | /// Replaces the built-in defaults, e.g. with an empty [`IgnoreFile`] to walk everything. |
| 226 | pub fn with_defaults(mut self, defaults: IgnoreFile) -> Self { |
| 227 | self.defaults = defaults; |
| 228 | self |
| 229 | } |
| 230 | |
| 231 | /// Replaces the names of the ignore files read in each directory, lowest priority first. |
| 232 | pub fn with_ignore_names<N: AsRef<[u8]>>(mut self, names: &[N]) -> Self { |
| 233 | self.names = names.iter().map(|n| n.as_ref().to_vec()).collect(); |
| 234 | self |
| 235 | } |
| 236 | |
| 237 | /// Lays a global excludes file, as git's `core.excludesFile`, below every file in the tree |
| 238 | /// and above the defaults. See [`git_global_excludes`]. |
| 239 | pub fn with_excludes<B: AsRef<[u8]>>(mut self, bytes: B) -> Self { |
| 240 | self.excludes = IgnoreFile::parse(bytes.as_ref()); |
| 241 | self |
| 242 | } |
| 243 | |
| 244 | /// Starts the walk at `start`, a directory relative to the root, keeping entry paths relative |
| 245 | /// to the root. |
| 246 | /// |
| 247 | /// Before `start` is listed, the walk asks to read [`REPO_EXCLUDE`] and every ignore file in |
| 248 | /// each directory above it, the root first, without listing them; a source answers `None` |
| 249 | /// for a file that is not there. If `start` or a directory above it is ignored, the walk ends |
| 250 | /// with [`Step::Done`] having yielded nothing, and [`Walk::start_ignored`] says so. |
| 251 | pub fn beneath<P: AsRef<[u8]>>(mut self, start: P) -> Self { |
| 252 | let mut start = start.as_ref(); |
| 253 | while start.first() == Some(&b'/') { |
| 254 | start = &start[1..]; |
| 255 | } |
| 256 | while start.last() == Some(&b'/') { |
| 257 | start = &start[..start.len() - 1]; |
| 258 | } |
| 259 | if start.is_empty() { |
| 260 | return self; |
| 261 | } |
| 262 | self.pending.clear(); |
| 263 | self.climb.push_back(Vec::new()); |
| 264 | for (i, b) in start.iter().enumerate() { |
| 265 | if *b == b'/' { |
| 266 | self.climb.push_back(start[..i].to_vec()); |
| 267 | } |
| 268 | } |
| 269 | self.climb.push_back(start.to_vec()); |
| 270 | self |
| 271 | } |
| 272 | |
| 273 | /// Did the walk end because its start, or a directory above it, is ignored? |
| 274 | pub fn start_ignored(&self) -> bool { |
| 275 | self.start_ign |
| 276 | } |
| 277 | |
| 278 | /// The rules the walk has read so far, to ask about paths it did not list. |
| 279 | pub fn rules(&self) -> Rules { |
| 280 | Rules { |
| 281 | defaults: self.defaults.clone(), |
| 282 | excludes: self.excludes.clone(), |
| 283 | files: self.layers.iter().map(|l| RuleFile { |
| 284 | base: l.base.clone(), |
| 285 | path: l.path.clone(), |
| 286 | rank: l.rank, |
| 287 | file: l.file.clone(), |
| 288 | }).collect(), |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | pub fn next(&mut self) -> Outcome<Step> { |
| 293 | match self.want { |
| 294 | Want::Nothing => (), |
| 295 | Want::Listing => return Err(err!( |
| 296 | "Walk::next called while the listing of '{}' is still owed.", |
| 297 | String::from_utf8_lossy(&self.dir); Order)), |
| 298 | Want::File => return Err(err!( |
| 299 | "Walk::next called while the ignore file '{}' is still owed.", |
| 300 | String::from_utf8_lossy(self.reads.front().map(|o| o.path.as_slice()).unwrap_or(b"")); Order)), |
| 301 | } |
| 302 | loop { |
| 303 | if self.over { |
| 304 | return Ok(Step::Done); |
| 305 | } |
| 306 | if let Some(owed) = self.reads.front() { |
| 307 | self.want = Want::File; |
| 308 | return Ok(Step::Read(owed.path.clone())); |
| 309 | } |
| 310 | // Climbing to the start: open the next directory down, unless it is ignored. |
| 311 | let dir = match self.climb.pop_front() { |
| 312 | Some(dir) => dir, |
| 313 | None => break, |
| 314 | }; |
| 315 | if !dir.is_empty() && self.is_ignored(&dir, true) { |
| 316 | self.start_ign = true; |
| 317 | self.over = true; |
| 318 | return Ok(Step::Done); |
| 319 | } |
| 320 | if self.climb.is_empty() { |
| 321 | self.pending.push((dir, self.top)); // the start itself, listed as usual |
| 322 | } else { |
| 323 | // Blind reads: the directory is never listed, so a source answers None for a gap. |
| 324 | self.dir = dir; |
| 325 | self.reads.push_back(Owed { path: Self::join(&self.dir, REPO_EXCLUDE.as_bytes()), rank: 0 }); |
| 326 | for (i, name) in self.names.iter().enumerate() { |
| 327 | self.reads.push_back(Owed { path: Self::join(&self.dir, name), rank: i + 1 }); |
| 328 | } |
| 329 | } |
| 330 | } |
| 331 | while let Some(item) = self.entries.pop_front() { |
| 332 | if self.kept + self.ignored >= self.budget { |
| 333 | self.over = true; |
| 334 | let unlisted = self.pending.len() |
| 335 | + self.children.len() |
| 336 | + if item.is_dir { 1 } else { 0 } |
| 337 | + self.entries.iter().filter(|e| e.is_dir).count(); |
| 338 | return Ok(Step::Stopped(WalkBudget { |
| 339 | budget: self.budget, |
| 340 | kept: self.kept, |
| 341 | ignored: self.ignored, |
| 342 | unlisted, |
| 343 | at: self.dir.clone(), |
| 344 | })); |
| 345 | } |
| 346 | let path = Self::join(&self.dir, &item.name); |
| 347 | if self.is_ignored(&path, item.is_dir) { |
| 348 | self.ignored += 1; |
| 349 | continue; |
| 350 | } |
| 351 | self.kept += 1; |
| 352 | if item.is_dir { |
| 353 | self.children.push(path.clone()); |
| 354 | } |
| 355 | return Ok(Step::Entry(WalkEntry { path, is_dir: item.is_dir })); |
| 356 | } |
| 357 | // Listing done: its subdirectories go on the stack so the first is listed next. |
| 358 | let top = self.top; |
| 359 | for child in self.children.drain(..).rev() { |
| 360 | self.pending.push((child, top)); |
| 361 | } |
| 362 | match self.pending.pop() { |
| 363 | Some((dir, top)) => { |
| 364 | self.dir = dir; |
| 365 | self.top = top; |
| 366 | self.want = Want::Listing; |
| 367 | Ok(Step::List(self.dir.clone())) |
| 368 | } |
| 369 | None => { |
| 370 | self.over = true; |
| 371 | Ok(Step::Done) |
| 372 | } |
| 373 | } |
| 374 | } |
| 375 | |
| 376 | /// Answers a [`Step::List`] with the directory's entries, in the order to walk them. |
| 377 | pub fn listed(&mut self, entries: Vec<Listed>) -> Outcome<()> { |
| 378 | if self.want != Want::Listing { |
| 379 | return Err(err!("Walk::listed called when no listing was asked for."; Order)); |
| 380 | } |
| 381 | self.want = Want::Nothing; |
| 382 | // A repository's own excludes rank below its ignore files, so they are laid first. |
| 383 | if entries.iter().any(|e| e.is_dir && e.name == b".git") { |
| 384 | self.reads.push_back(Owed { path: Self::join(&self.dir, REPO_EXCLUDE.as_bytes()), rank: 0 }); |
| 385 | } |
| 386 | for (i, name) in self.names.iter().enumerate() { |
| 387 | if entries.iter().any(|e| !e.is_dir && &e.name == name) { |
| 388 | self.reads.push_back(Owed { path: Self::join(&self.dir, name), rank: i + 1 }); |
| 389 | } |
| 390 | } |
| 391 | self.entries = entries.into(); |
| 392 | Ok(()) |
| 393 | } |
| 394 | |
| 395 | /// Answers a [`Step::Read`] with the ignore file's bytes, or `None` if it could not be read. |
| 396 | pub fn read(&mut self, bytes: Option<Vec<u8>>) -> Outcome<()> { |
| 397 | if self.want != Want::File { |
| 398 | return Err(err!("Walk::read called when no ignore file was asked for."; Order)); |
| 399 | } |
| 400 | self.want = Want::Nothing; |
| 401 | let owed = match self.reads.pop_front() { |
| 402 | Some(owed) => owed, |
| 403 | None => return Err(err!("Walk::read found no owed ignore file to record."; Bug)), |
| 404 | }; |
| 405 | if let Some(bytes) = bytes { |
| 406 | let file = IgnoreFile::parse(&bytes); |
| 407 | if !file.is_empty() { |
| 408 | self.layers.push(Layer { |
| 409 | base: self.dir.clone(), |
| 410 | path: owed.path, |
| 411 | rank: owed.rank, |
| 412 | file, |
| 413 | below: self.top, |
| 414 | }); |
| 415 | self.top = Some(self.layers.len() - 1); |
| 416 | } |
| 417 | } |
| 418 | Ok(()) |
| 419 | } |
| 420 | |
| 421 | /// Drives the walk to its end over a synchronous source, handing each kept entry to `visit`, |
| 422 | /// which returns `false` to stop. |
| 423 | pub fn run<S, F>(mut self, src: &mut S, mut visit: F) -> Outcome<WalkEnd> |
| 424 | where |
| 425 | S: WalkSource, |
| 426 | F: FnMut(WalkEntry) -> Outcome<bool>, |
| 427 | { |
| 428 | loop { |
| 429 | match res!(self.next()) { |
| 430 | Step::List(dir) => res!(self.listed(res!(src.list(&dir)))), |
| 431 | Step::Read(path) => res!(self.read(res!(src.read(&path)))), |
| 432 | Step::Entry(entry) => if !res!(visit(entry)) { return Ok(WalkEnd::Halted); }, |
| 433 | Step::Stopped(rep) => return Ok(WalkEnd::Budget(rep)), |
| 434 | Step::Done => return Ok(WalkEnd::Complete), |
| 435 | } |
| 436 | } |
| 437 | } |
| 438 | |
| 439 | // The deepest ignore file that speaks decides; the defaults speak last. |
| 440 | fn is_ignored(&self, path: &[u8], is_dir: bool) -> bool { |
| 441 | let mut at = self.top; |
| 442 | while let Some(i) = at { |
| 443 | let layer = &self.layers[i]; |
| 444 | let rel = if layer.base.is_empty() { path } else { &path[layer.base.len() + 1..] }; |
| 445 | if let Some(ignored) = layer.file.decides(rel, is_dir) { |
| 446 | return ignored; |
| 447 | } |
| 448 | at = layer.below; |
| 449 | } |
| 450 | if let Some(ignored) = self.excludes.decides(path, is_dir) { |
| 451 | return ignored; |
| 452 | } |
| 453 | self.defaults.ignores(path, is_dir) |
| 454 | } |
| 455 | |
| 456 | fn join(dir: &[u8], name: &[u8]) -> Vec<u8> { |
| 457 | if dir.is_empty() { |
| 458 | return name.to_vec(); |
| 459 | } |
| 460 | let mut path = Vec::with_capacity(dir.len() + 1 + name.len()); |
| 461 | path.extend_from_slice(dir); |
| 462 | path.push(b'/'); |
| 463 | path.extend_from_slice(name); |
| 464 | path |
| 465 | } |
| 466 | } |
| 467 | |
| 468 | |
| 469 | #[derive(Clone, Debug)] |
| 470 | struct RuleFile { |
| 471 | base: Vec<u8>, |
| 472 | path: Vec<u8>, |
| 473 | rank: usize, |
| 474 | file: IgnoreFile, |
| 475 | } |
| 476 | |
| 477 | /// Every ignore file a walk read, with its defaults and global excludes, as one matcher. |
| 478 | /// |
| 479 | /// It answers for any path beneath the walk's root as the walk would have, so a caller can judge |
| 480 | /// a path it learns of later -- one another device sent, say -- without walking again. A |
| 481 | /// directory the walk never listed contributes nothing, so its own ignore files go unheard. |
| 482 | #[derive(Clone, Debug, Default)] |
| 483 | pub struct Rules { |
| 484 | defaults: IgnoreFile, |
| 485 | excludes: IgnoreFile, |
| 486 | files: Vec<RuleFile>, |
| 487 | } |
| 488 | |
| 489 | // Which layer decided. |
| 490 | enum Origin<'a> { |
| 491 | File(&'a [u8]), |
| 492 | Excludes, |
| 493 | Defaults, |
| 494 | } |
| 495 | |
| 496 | impl Rules { |
| 497 | |
| 498 | /// Is the path ignored, by its own rules or because a directory above it is? Nothing inside |
| 499 | /// an ignored directory can be re-included, as in git. |
| 500 | pub fn ignored(&self, path: &[u8], is_dir: bool) -> bool { |
| 501 | self.top_ignored(path, is_dir).is_some() |
| 502 | } |
| 503 | |
| 504 | /// The path of the ignore file that ignores `path` or the directory above it that is |
| 505 | /// ignored, e.g. `sub/.gitignore`: empty for the built-in defaults, [`EXCLUDES_NAME`] for the |
| 506 | /// global excludes, `None` when the path is not ignored. |
| 507 | pub fn why(&self, path: &[u8], is_dir: bool) -> Option<Vec<u8>> { |
| 508 | let top = match self.top_ignored(path, is_dir) { |
| 509 | Some(top) => top, |
| 510 | None => return None, |
| 511 | }; |
| 512 | let top_dir = if top.len() == path.len() { is_dir } else { true }; |
| 513 | match self.decide(&top, top_dir) { |
| 514 | Some((true, Origin::File(p))) => Some(p.to_vec()), |
| 515 | Some((true, Origin::Excludes)) => Some(EXCLUDES_NAME.as_bytes().to_vec()), |
| 516 | Some((true, Origin::Defaults)) => Some(Vec::new()), |
| 517 | _ => None, |
| 518 | } |
| 519 | } |
| 520 | |
| 521 | /// The shortest ignored path among `path` and the directories above it. |
| 522 | pub fn top_ignored(&self, path: &[u8], is_dir: bool) -> Option<Vec<u8>> { |
| 523 | for (i, b) in path.iter().enumerate() { |
| 524 | if *b == b'/' && i > 0 && Self::says_ignored(&self.decide(&path[..i], true)) { |
| 525 | return Some(path[..i].to_vec()); |
| 526 | } |
| 527 | } |
| 528 | if !path.is_empty() && Self::says_ignored(&self.decide(path, is_dir)) { |
| 529 | return Some(path.to_vec()); |
| 530 | } |
| 531 | None |
| 532 | } |
| 533 | |
| 534 | /// Adds the files of another walk's rules not already held, by file path, so walks of |
| 535 | /// several starts under one root answer as one. The defaults and excludes of `self` stand. |
| 536 | pub fn absorb(&mut self, other: Rules) { |
| 537 | for f in other.files { |
| 538 | if !self.files.iter().any(|g| g.path == f.path) { |
| 539 | self.files.push(f); |
| 540 | } |
| 541 | } |
| 542 | } |
| 543 | |
| 544 | fn says_ignored(d: &Option<(bool, Origin)>) -> bool { |
| 545 | matches!(d, Some((true, _))) |
| 546 | } |
| 547 | |
| 548 | // The deepest file that speaks decides, and in one directory the later file; then the global |
| 549 | // excludes, then the defaults. The same order as the walk's chain of layers. |
| 550 | fn decide(&self, path: &[u8], is_dir: bool) -> Option<(bool, Origin<'_>)> { |
| 551 | let mut best: Option<(&RuleFile, bool)> = None; |
| 552 | for f in &self.files { |
| 553 | let rel = if f.base.is_empty() { |
| 554 | path |
| 555 | } else if path.len() > f.base.len() |
| 556 | && path.starts_with(&f.base) |
| 557 | && path[f.base.len()] == b'/' |
| 558 | { |
| 559 | &path[f.base.len() + 1..] |
| 560 | } else { |
| 561 | continue; |
| 562 | }; |
| 563 | if let Some((b, _)) = best { |
| 564 | if (f.base.len(), f.rank) < (b.base.len(), b.rank) { |
| 565 | continue; |
| 566 | } |
| 567 | } |
| 568 | if let Some(ignored) = f.file.decides(rel, is_dir) { |
| 569 | best = Some((f, ignored)); |
| 570 | } |
| 571 | } |
| 572 | if let Some((f, ignored)) = best { |
| 573 | return Some((ignored, Origin::File(&f.path))); |
| 574 | } |
| 575 | if let Some(ignored) = self.excludes.decides(path, is_dir) { |
| 576 | return Some((ignored, Origin::Excludes)); |
| 577 | } |
| 578 | self.defaults.decides(path, is_dir).map(|ignored| (ignored, Origin::Defaults)) |
| 579 | } |
| 580 | } |
| 581 | |
| 582 | |
| 583 | /// Finds and reads git's global excludes for this user, as git does. |
| 584 | /// |
| 585 | /// `core.excludesFile` is taken from `$GIT_CONFIG_GLOBAL` when set, else from |
| 586 | /// `$XDG_CONFIG_HOME/git/config` and then `~/.gitconfig`, the later winning; unset, the file is |
| 587 | /// `$XDG_CONFIG_HOME/git/ignore` (`~/.config/git/ignore`). A leading `~/` is expanded and |
| 588 | /// `include` directives are not followed. `None` when there is no such file, or when it, or a |
| 589 | /// config file, is not a regular file or is over [`Limits::ignore_file_bytes`]. |
| 590 | #[cfg(not(target_arch = "wasm32"))] |
| 591 | pub fn git_global_excludes() -> Outcome<Option<Vec<u8>>> { |
| 592 | git_global_excludes_with(&Limits::default()) |
| 593 | } |
| 594 | |
| 595 | #[cfg(not(target_arch = "wasm32"))] |
| 596 | pub fn git_global_excludes_with(lim: &Limits) -> Outcome<Option<Vec<u8>>> { |
| 597 | let var = |k: &str| std::env::var_os(k).filter(|v| !v.is_empty()).map(PathBuf::from); |
| 598 | let home = var("HOME"); |
| 599 | let xdg = match var("XDG_CONFIG_HOME") { |
| 600 | Some(x) => Some(x), |
| 601 | None => home.as_ref().map(|h| h.join(".config")), |
| 602 | }; |
| 603 | let configs: Vec<PathBuf> = match var("GIT_CONFIG_GLOBAL") { |
| 604 | Some(g) => vec![g], |
| 605 | None => { |
| 606 | let mut v = Vec::new(); |
| 607 | if let Some(x) = &xdg { |
| 608 | v.push(x.join("git").join("config")); |
| 609 | } |
| 610 | if let Some(h) = &home { |
| 611 | v.push(h.join(".gitconfig")); |
| 612 | } |
| 613 | v |
| 614 | } |
| 615 | }; |
| 616 | let mut named: Option<Vec<u8>> = None; |
| 617 | for config in &configs { |
| 618 | if let Some(bytes) = res!(read_tolerant(config, lim.ignore_file_bytes)) { |
| 619 | if let Some(v) = git_config_excludes(&bytes) { |
| 620 | named = Some(v); |
| 621 | } |
| 622 | } |
| 623 | } |
| 624 | let file = match named { |
| 625 | Some(v) if v.starts_with(b"~/") => match &home { |
| 626 | Some(h) => h.join(Disk::from_bytes(&v[2..])), |
| 627 | None => return Err(err!( |
| 628 | "core.excludesFile '{}' starts with ~/ but HOME is not set.", |
| 629 | String::from_utf8_lossy(&v); Missing, Configuration)), |
| 630 | }, |
| 631 | Some(v) => Disk::from_bytes(&v), |
| 632 | None => match &xdg { |
| 633 | Some(x) => x.join("git").join("ignore"), |
| 634 | None => return Ok(None), |
| 635 | }, |
| 636 | }; |
| 637 | read_tolerant(&file, lim.ignore_file_bytes) |
| 638 | } |
| 639 | |
| 640 | /// The value of `core.excludesFile` in one git config file, if set; the last setting wins. |
| 641 | /// |
| 642 | /// Section and key names match without regard to case, a quoted value is unquoted, a backslash |
| 643 | /// escapes the next byte, and `#` or `;` outside quotes begins a comment. |
| 644 | pub fn git_config_excludes(config: &[u8]) -> Option<Vec<u8>> { |
| 645 | let mut in_core = false; |
| 646 | let mut found = None; |
| 647 | for raw in config.split(|b| *b == b'\n') { |
| 648 | let mut line = trim(raw); |
| 649 | if line.first() == Some(&b'[') { |
| 650 | let end = match line.iter().position(|b| *b == b']') { |
| 651 | Some(end) => end, |
| 652 | None => continue, |
| 653 | }; |
| 654 | in_core = trim(&line[1..end]).eq_ignore_ascii_case(b"core"); |
| 655 | line = trim(&line[end + 1..]); // a key may follow the header on its line |
| 656 | } |
| 657 | if !in_core || line.is_empty() || line[0] == b'#' || line[0] == b';' { |
| 658 | continue; |
| 659 | } |
| 660 | let eq = match line.iter().position(|b| *b == b'=') { |
| 661 | Some(eq) => eq, |
| 662 | None => continue, |
| 663 | }; |
| 664 | if !trim(&line[..eq]).eq_ignore_ascii_case(b"excludesfile") { |
| 665 | continue; |
| 666 | } |
| 667 | let mut val = Vec::new(); |
| 668 | let mut quoted = false; |
| 669 | let mut bytes = trim(&line[eq + 1..]).iter(); |
| 670 | while let Some(b) = bytes.next() { |
| 671 | match *b { |
| 672 | b'"' => quoted = !quoted, |
| 673 | b'\\' => if let Some(n) = bytes.next() { val.push(*n); }, |
| 674 | b'#' | b';' if !quoted => break, |
| 675 | other => val.push(other), |
| 676 | } |
| 677 | } |
| 678 | let val = trim(&val); |
| 679 | found = if val.is_empty() { None } else { Some(val.to_vec()) }; |
| 680 | } |
| 681 | found |
| 682 | } |
| 683 | |
| 684 | fn trim(b: &[u8]) -> &[u8] { |
| 685 | let start = match b.iter().position(|c| !c.is_ascii_whitespace()) { |
| 686 | Some(i) => i, |
| 687 | None => return &b[b.len()..], |
| 688 | }; |
| 689 | let end = match b.iter().rposition(|c| !c.is_ascii_whitespace()) { |
| 690 | Some(i) => i + 1, |
| 691 | None => b.len(), |
| 692 | }; |
| 693 | &b[start..end] |
| 694 | } |
| 695 | |
| 696 | // The user's own files, named by path, so a link is followed as git follows it. |
| 697 | #[cfg(not(target_arch = "wasm32"))] |
| 698 | fn read_tolerant(path: &Path, cap: u64) -> Outcome<Option<Vec<u8>>> { |
| 699 | match read_pattern_file(path, true, cap) { |
| 700 | Ok(bytes) => Ok(bytes), |
| 701 | Err(e) if Disk::tolerable(&e) => Ok(None), |
| 702 | Err(e) => Err(err!(Error::from(e), |
| 703 | "While reading git's global excludes from {:?}.", path; IO, File)), |
| 704 | } |
| 705 | } |
| 706 | |
| 707 | /// The nearest directory at or above `dir` holding one of [`REPO_MARKS`], `None` outside any. |
| 708 | /// |
| 709 | /// A walk of a directory inside a repository roots at this one and starts [`Walk::beneath`] the |
| 710 | /// directory, so the ignore files above it speak, as they do for git and ripgrep. |
| 711 | #[cfg(not(target_arch = "wasm32"))] |
| 712 | pub fn repo_top(dir: &std::path::Path) -> Option<PathBuf> { |
| 713 | dir.ancestors() |
| 714 | .find(|d| REPO_MARKS.iter().any(|m| d.join(m).exists())) |
| 715 | .map(|d| d.to_path_buf()) |
| 716 | } |
| 717 | |
| 718 | |
| 719 | /// A [`WalkSource`] over `std::fs`, rooted at a directory. |
| 720 | /// |
| 721 | /// Symbolic links are listed as files and never followed, an ignore file among them. A directory |
| 722 | /// that vanishes or cannot be read mid-walk lists as empty rather than ending the walk, and is kept |
| 723 | /// in [`Disk::unread`], so a caller never takes its absent entries as gone; the root itself must be |
| 724 | /// readable. An ignore file over [`Limits::ignore_file_bytes`] is skipped. |
| 725 | #[derive(Clone, Debug)] |
| 726 | pub struct Disk { |
| 727 | root: PathBuf, |
| 728 | cap: u64, // the most an ignore file may hold |
| 729 | unread: Vec<Vec<u8>>, // directories listed in part or not at all, relative to the root |
| 730 | } |
| 731 | |
| 732 | impl Disk { |
| 733 | |
| 734 | pub fn new<P: Into<PathBuf>>(root: P) -> Self { |
| 735 | Self { root: root.into(), cap: Limits::default().ignore_file_bytes, unread: Vec::new() } |
| 736 | } |
| 737 | |
| 738 | /// The directories, relative to the root, whose listing failed in whole or in part. |
| 739 | pub fn unread(&self) -> &[Vec<u8>] { |
| 740 | &self.unread |
| 741 | } |
| 742 | |
| 743 | pub fn limited(mut self, lim: &Limits) -> Self { |
| 744 | self.cap = lim.ignore_file_bytes; |
| 745 | self |
| 746 | } |
| 747 | |
| 748 | fn path(&self, rel: &[u8]) -> PathBuf { |
| 749 | if rel.is_empty() { |
| 750 | return self.root.clone(); |
| 751 | } |
| 752 | self.root.join(Self::from_bytes(rel)) |
| 753 | } |
| 754 | |
| 755 | #[cfg(unix)] |
| 756 | fn from_bytes(b: &[u8]) -> PathBuf { |
| 757 | use std::os::unix::ffi::OsStrExt; |
| 758 | PathBuf::from(std::ffi::OsStr::from_bytes(b)) |
| 759 | } |
| 760 | |
| 761 | #[cfg(not(unix))] |
| 762 | fn from_bytes(b: &[u8]) -> PathBuf { |
| 763 | PathBuf::from(String::from_utf8_lossy(b).into_owned()) |
| 764 | } |
| 765 | |
| 766 | #[cfg(unix)] |
| 767 | fn to_bytes(s: &std::ffi::OsStr) -> Vec<u8> { |
| 768 | use std::os::unix::ffi::OsStrExt; |
| 769 | s.as_bytes().to_vec() |
| 770 | } |
| 771 | |
| 772 | #[cfg(not(unix))] |
| 773 | fn to_bytes(s: &std::ffi::OsStr) -> Vec<u8> { |
| 774 | s.to_string_lossy().into_owned().into_bytes() |
| 775 | } |
| 776 | |
| 777 | // A blind read above a walk's start may meet a `.git` file where a directory was expected, |
| 778 | // or a directory named like an ignore file. |
| 779 | fn tolerable(e: &io::Error) -> bool { |
| 780 | matches!(e.kind(), |
| 781 | io::ErrorKind::NotFound |
| 782 | | io::ErrorKind::PermissionDenied |
| 783 | | io::ErrorKind::NotADirectory |
| 784 | | io::ErrorKind::IsADirectory) |
| 785 | } |
| 786 | } |
| 787 | |
| 788 | impl WalkSource for Disk { |
| 789 | |
| 790 | fn list(&mut self, dir: &[u8]) -> Outcome<Vec<Listed>> { |
| 791 | let path = self.path(dir); |
| 792 | let iter = match fs::read_dir(&path) { |
| 793 | Ok(iter) => iter, |
| 794 | Err(e) if !dir.is_empty() && Self::tolerable(&e) => { |
| 795 | self.unread.push(dir.to_vec()); |
| 796 | return Ok(Vec::new()); |
| 797 | }, |
| 798 | Err(e) => return Err(err!(Error::from(e), "While listing {:?} for a walk.", path; IO, File)), |
| 799 | }; |
| 800 | let mut out = Vec::new(); |
| 801 | for entry in iter { |
| 802 | let entry = match entry { |
| 803 | Ok(entry) => entry, |
| 804 | Err(e) if Self::tolerable(&e) => { self.unread.push(dir.to_vec()); continue; }, |
| 805 | Err(e) => return Err(err!(Error::from(e), "While listing {:?} for a walk.", path; IO, File)), |
| 806 | }; |
| 807 | let is_dir = match entry.file_type() { |
| 808 | Ok(t) => t.is_dir(), |
| 809 | Err(e) if Self::tolerable(&e) => { self.unread.push(dir.to_vec()); continue; }, |
| 810 | Err(e) => return Err(err!(Error::from(e), "While typing an entry of {:?} for a walk.", path; IO, File)), |
| 811 | }; |
| 812 | out.push(Listed { name: Self::to_bytes(&entry.file_name()), is_dir }); |
| 813 | } |
| 814 | // Name order, so a walk is the same on every run and every platform. |
| 815 | out.sort_by(|a, b| a.name.cmp(&b.name)); |
| 816 | Ok(out) |
| 817 | } |
| 818 | |
| 819 | fn read(&mut self, path: &[u8]) -> Outcome<Option<Vec<u8>>> { |
| 820 | let path = self.path(path); |
| 821 | // A link in the tree may point anywhere, a device or a file outside the root; git does not |
| 822 | // follow an in-tree ignore file that is a link either. |
| 823 | match read_pattern_file(&path, false, self.cap) { |
| 824 | Ok(bytes) => Ok(bytes), |
| 825 | Err(e) if Self::tolerable(&e) => Ok(None), |
| 826 | Err(e) => Err(err!(Error::from(e), "While reading ignore file {:?}.", path; IO, File)), |
| 827 | } |
| 828 | } |
| 829 | } |
| 830 | |
| 831 | /// The bytes of a pattern file, or `None` when it is not a regular file or holds more than `cap` |
| 832 | /// bytes, which git also skips with a warning. A link is followed only when `follow`. |
| 833 | fn read_pattern_file(path: &Path, follow: bool, cap: u64) -> io::Result<Option<Vec<u8>>> { |
| 834 | let seen = match follow { |
| 835 | true => fs::metadata(path), |
| 836 | false => fs::symlink_metadata(path), |
| 837 | }; |
| 838 | let seen = match seen { |
| 839 | Ok(m) => m, |
| 840 | Err(e) => return Err(e), |
| 841 | }; |
| 842 | // Checked before the open, which would wait forever on a FIFO. |
| 843 | if !seen.is_file() { |
| 844 | return Ok(None); |
| 845 | } |
| 846 | let file = match fs::File::open(path) { |
| 847 | Ok(f) => f, |
| 848 | Err(e) => return Err(e), |
| 849 | }; |
| 850 | let held = match file.metadata() { |
| 851 | Ok(m) => m, |
| 852 | Err(e) => return Err(e), |
| 853 | }; |
| 854 | // The file opened is the file looked at, not one swapped in between. |
| 855 | #[cfg(unix)] |
| 856 | { |
| 857 | use std::os::unix::fs::MetadataExt; |
| 858 | if held.dev() != seen.dev() || held.ino() != seen.ino() { |
| 859 | return Ok(None); |
| 860 | } |
| 861 | } |
| 862 | if !held.is_file() { |
| 863 | return Ok(None); |
| 864 | } |
| 865 | if held.len() > cap { |
| 866 | warn!("The pattern file {:?} is over {} bytes, so it is skipped.", path, cap); |
| 867 | return Ok(None); |
| 868 | } |
| 869 | let mut out = Vec::new(); |
| 870 | match file.take(cap + 1).read_to_end(&mut out) { |
| 871 | Ok(_) => {}, |
| 872 | Err(e) => return Err(e), |
| 873 | } |
| 874 | // It grew after it was measured. |
| 875 | if out.len() as u64 > cap { |
| 876 | warn!("The pattern file {:?} is over {} bytes, so it is skipped.", path, cap); |
| 877 | return Ok(None); |
| 878 | } |
| 879 | Ok(Some(out)) |
| 880 | } |