Table of Contents
I needed a file system ignore library for a utility I was writing. This is similar to Git’s .gitignore, but the files containing the rules can have different names, and ignore rules may be defined programmatically.
I was using burntsushi’s ignore crate, which in turn uses globset by the same author. In a directory hierarchy, I was first collecting all .ignore files, then trying to decide which files are ignored. Ripgrep’s from parameter led me to believe this.
However, it looks like it has a bug that doesn’t consider the source directory of the ignore file. Git has different semantics when a/.gitignore and a/b/.gitignore have a line mydir/. In the second case, Git doesn’t ignore a/mydir/, but Ripgrep seems to consider all elements from all files as if they are from the root directory.
In practice, most people may be using ignore files in their root directory, but there are valid use cases (like moving around directories with ignore patterns in them) that are affected by such behavior.
I decided to tackle this. Ripgrep’s globset seems nice and fast, so it was better to base the solution on top of that. My basic use case is walking a directory hierarchy. There are solutions to this like walkdir or jwalk, but they use ripgrep’s gitignore; hence, they have the same bug.
I usually begin by setting up data structures to understand the problem. This allows me to understand the domain formally.
First, what are we trying to accomplish? Basically, we want to decide if a path should be ignored (a) in the results and (b) in the directory traversal. The gitignore specification not only allows ignores, but also has a way to add paths to a whitelist to unignore. Hence, deciding whether to ignore a path is like:
let include = |path| {
if whitelist_globs.match(path) {
true
} else if ignore_globs.match(path) {
false
} else {
true }
}
We also need to decide whether to traverse a directory:
let traverse = |path| {
if path.is_dir() && !include(path) { false } else { true }
}
We have the following possible MatchResults between the ignore rules and a path:
pub enum MatchResult {
NoMatch,
Ignore,
Whitelist,
}
We need a comparison function to get a MatchResult. One side of the comparison is path, and the other is a set of GlobSets from the globset crate. We’ll have two globsets: one for ignores and the other for whitelists.
pub struct IgnoreRules {
root: PathBuf,
patterns: Arc<Vec<Pattern<Glob>>>,
whitelist_set: Arc<GlobSet>,
ignore_set: Arc<GlobSet>,
}
The data types for the sets are Arc<GlobSet>, as I planned to make the traversal concurrent for each directory. However, as only one thread will be modifying the rules (one .gitignore or .ignore file per directory), I felt no need to wrap the sets with Mutex.
We also keep track of each pattern separately. patterns is a Pattern vector that contains all globs individually. One reason is to rebuild the GlobSet as we traverse directories: since we cannot add any more rules to the sets once they have been built, we keep the patterns separately to add them to the sets of the child directories.
Another reason is to keep track of the source, as this can be used for debugging or reporting, similar to git check-ignore.
root is the point where this traversal began.
Patterns are defined in a generic way to be instantiated with globs, strings, regexes, or any other type.
pub struct Pattern<T> {
pattern: T,
original: String,
source: Source,
effect: PatternEffect,
relativity: PatternRelativity,
path_kind: PathKind,
}
The rationale for this generic approach is that the patterns need some kind of transformation. They can be read from files as strings, then compiled into globs or regexes.
flowchart LR
String-->Ok(Glob)-->Glob-->Regex
The source field shows where this pattern was retrieved. It’s an enum with two possible values for the time being:
enum Source {
File { path: PathBuf, line: usize },
Global,
}
The gitignore specification says:
An optional prefix “!” which negates the pattern; any matching file excluded by a previous pattern will become included again.
We use the effect field to tag the pattern as either an Ignore or a Whitelist pattern.
pub enum PatternEffect {
Ignore,
Whitelist,
}
The spec also makes a distinction between files and directories:
If there is a separator at the end of the pattern then the pattern will only match directories, otherwise the pattern can match both files and directories.
So we use path_kind to reflect this distinction:
pub enum PathKind {
Any,
Directory,
}
Some patterns can be relative to the directory they are found in:
If there is a separator at the beginning or middle (or both) of the pattern, then the pattern is relative to the directory level of the particular .gitignore file itself. Otherwise the pattern may also match at any level below the .gitignore level.
And we show this with the relativity field:
pub enum PatternRelativity {
Anywhere,
RelativeTo { directory: String },
}
Note that we are converting from the specification to Rust types. In the future, these enums can be extended to cover cases where these patterns are used in other places, or we can merge some of them to reduce complexity. Currently, this level of abstraction seems adequate.
To convert Pattern<String> to Pattern<Glob> (or Pattern<Result<Glob, Error>>), or any other type, we can use a map function similar to Option::map:
fn map<U, F>(self, f: F) -> Pattern<U>
where
F: FnOnce(T) -> U,
{
let pat = Pattern::<U> {
pattern: f(self.pattern),
original: self.original,
source: self.source,
effect: self.effect,
relativity: self.relativity,
path_kind: self.path_kind,
};
pat
}
map will make it easy to convert between various types of patterns.
Now, we change the perspective to a higher level. Let’s begin by writing a file tree walker.
pub fn walk_serial(
given: IgnoreRules,
dir: &Path,
walk_options: &WalkOptions,
sender: &Sender<WalkerResult<PathMetadata>>,
) -> WalkerResult<()> { todo!() }
This function uses the given IgnoreRules and returns files and directories via the channel. PathMetadata is just a bundle of PathBuf and its Metadata.
pub struct PathMetadata {
path: PathBuf,
metadata: Metadata,
}
WalkOptions will contain various options about this traversal. Currently, it only has ignore_filename and include_dirs, which set whether only files are sent through the channel, or if directories should be included too.
pub struct WalkOptions<'a> {
ignore_filename: Option<&'a str>,
include_dirs: bool,
}
Initially, IgnoreRules contains only the files that should be ignored (or whitelisted) globally. When a directory contains a .gitignore file (or any file name that was set in WalkOptions), it checks for new ignore rules and sends all files through the channel. If a directory is not ignored, it then calls walk_serial recursively with it.
The final lines of the function are as follows:
for child_dir in child_dirs {
walk_serial(dir_with_ignores.clone(), &child_dir, walk_options, sender)?;
}
As it calls itself as a final operation after collecting and sending all child files, this is an example of tail recursion.
The output is sent through a channel because our final goal is to make all this concurrent. Each new directory will create a new thread, and all files will be collected from the channel. At this point, we are creating a serial version of the walker with identical data structures to test it easily.
One gotcha using the channels in the serial version is that the channel size must be enough to contain all file names. Effectively, this means it will be crossbeam_channel::unbounded for walk_serial. We will (ab)use the channel’s Sender<PathMetadata> as a Vec<PathMetadata> in no parallel mode. In parallel settings, using unbounded channels is not recommended; if the consumers of the channel don’t work as quickly, you may fill up the memory, especially for longer-running processes.
walk_serial will basically do four things:
- List all the elements in the given directory.
- Check if there is a new ignore file and update the rules if necessary.
- Filter the elements by ignore rules and send them to the channel.
- Run
walk_serialrecursively for child directories if they are not ignored.
Read the directory
The first is done using read_dir of Path. It returns a set of elements. Then the list is processed, and elements’ metadata is retrieved. This requires a bit of error handling: read_dir may return an Error, each element in the result can be an Error, and getting metadata may also result in an Error.
let elements = dir
.read_dir()
.map_err(|e| anyhow!("Error reading directory: {:?}, {:?}", dir, e))?;
let mut child_dirs = Vec::<PathBuf>::new();
let mut child_paths = Vec::<PathMetadata>::new();
for entry in elements {
match entry {
Err(err) => sender.send(Err(WalkerError::from(anyhow!(
"Error reading entry in dir {:?} {:?}",
dir,
err
))))?,
Ok(entry) => match entry.metadata() {
Err(err) => sender.send(Err(WalkerError::from(anyhow!(
"Error getting metadata {:?} {}",
entry,
err
))))?,
Ok(md) => {
child_paths.push(PathMetadata {
path: entry.path(),
metadata: md.clone(),
});
if md.is_dir() {
child_dirs.push(entry.path());
}
}
},
}
}
Note that we collect PathMetadata objects in the child_paths vector. If there happens to be an error while retrieving, it’s sent to the caller to ignore or to report to the user.
I usually handle errors first in match expressions because they are usually more straightforward.
Check if there are new ignore rules
After reading all the files in the directory, it checks if there actually is an ignore filename in given and that a file exists with that name in the list we just created. If there is no such file, we can use given rules to decide the ignored elements.
If there is a file that may change the ignore rules, it reads it and updates patterns. Then, if there are new ignore or whitelist rules, the respective globsets are recreated. It checks whether we have new rules because compiling globs is possibly an expensive operation.
Filtering directory elements
Filtering files and directories from the list checks two globsets. If an element matches a whitelist rule, it’s included in the results without checking if it also matches ignore rules. Hence, whitelisting has a priority. Otherwise, it checks the ignore rules, and if they don’t match, the element is included in the results.
If there are directories matching the ignore rules, they are not traversed, and any possible whitelisting rule that was specified within that directory is not taken into consideration.
Listing child directories
We saw how walk_serial calls itself for child directories above. After sending all results to the channel, it calls itself for the child directories and repeats.
Converting patterns from String to Glob
The interesting part about ignoring files is that we should modify patterns into globs to add to a GlobSet. We cannot add the patterns directly to a GlobSet because some of the rules make them context dependent. We parsed the patterns to get PatternRelativity and PathKind, and these also affect how we add the patterns to a GlobSet.
The heart of the conversion is a function that receives a String, filters it, and transforms it to a list of Pattern<Glob>s.
fn content_to_patterns(
ignore_root: &Path,
source: Option<&Path>,
contents: &str,
) -> Vec<Pattern<WalkerResult<Glob>>> {
As we also need to report the line number for patterns, we use enumerate on the iterator:
let patterns: Vec<Pattern<WalkerResult<Glob>>> = content
.lines()
.enumerate()
// A line starting with # serves as a comment. Put a backslash ("\") in front of the first hash for patterns that begin with a hash.
.filter(|(_, line)| !(line.trim().is_empty() || line.starts_with("#")))
The filter line is used to check for blank and comment lines. Then we trim the trailing space unless the pattern ends with \.
.map(|(i, line)| {
if !line.ends_with("\\ ") {
(i, line.trim_end())
} else {
(i, line)
}
})
The function receives the source file name as a parameter. We create the Source using it and the line number:
.map(|(i, line)| {
(
line,
match source {
Some(p) => Source::File {
path: p
.strip_prefix(ignore_root)
.expect("path must be within ignore_root")
.to_path_buf(),
line: (i + 1).into(),
},
None => Source::Global,
},
)
})
Then we build the pattern object, update the pattern to add it before the globset, and build the globs. Building the glob may cause errors if it’s not well-formed. They are handled as well.
.map(|(line, source)| build_pattern(source, line))
.map(transform_pattern_for_glob)
.map(|pc| pc.map(|s| Glob::new(&s).map_err(WalkerError::from)))
Two functions are left that may need attention. One is build_pattern that converts a pattern line to a Pattern<String> object. The other is the transform_pattern_for_glob function that modifies Pattern<String> before building the glob.
After writing walk_serial, we’ll use all the machinery to write a parallel version of it.
Parsing pattern strings for pattern objects
We create pattern objects from pattern strings following the spec. There are three basic rules that we will follow:
- If the pattern starts with
!, it’s a whitelist rule. - If the pattern ends with
/, it matches only to directories. - If the pattern contains a non-final
/, it’s relative to the directory.
We’ll also check whether the line starts with / and remove that to prevent double-slashes // in patterns. The resulting pattern in the object won’t contain any of the artifacts that change its semantics, and we’ll add them when building the globsets.
Let’s start by checking whether the line starts with !.
let begin_exclamation = original.starts_with("!");
let line = if begin_exclamation || original.starts_with("\\!") {
original[1..].to_owned()
} else {
original.to_owned()
};
Checking the presence of / at the beginning, at the end, and in intermediate positions is also straightforward:
let end_slash = line.ends_with("/");
let line = if end_slash {
&line[..line.len() - 1]
} else {
line
};
let begin_slash = line.starts_with("/");
let non_final_slash = if line.len() > 0 {
line[..line.len() - 1].chars().find(|c| *c == '/').is_some()
} else {
false
};
We check the non-final slash separately from the beginning slash because we’ll remove the initial slash if it exists.
let line = if begin_slash { &line[1..] } else { line };
Although there is almost 1-1 correspondence between the boolean conditions and the enums, I create enums in separate statements for self-documenting code.
let effect = if begin_exclamation {
PatternEffect::Whitelist
} else {
PatternEffect::Ignore
};
let path_kind = if end_slash {
PathKind::Directory
} else {
PathKind::Any
};
let relativity = if non_final_slash {
PatternRelativity::RelativeTo {
directory: current_dir.to_owned(),
}
} else {
PatternRelativity::Anywhere
};
After building these attributes of the pattern and stripping the pattern from the initial and final /, and other semantic-changing elements, we build a pattern:
let pattern = Pattern::<String> {
pattern: line.to_owned(),
original: original.to_owned(),
source,
effect,
relativity,
path_kind,
};
Transforming a pattern string to a suitable glob
Now, another transformation is needed to convert Pattern<String> to Pattern<Glob>. In this case, we’ll need to recreate the pattern based on the rules.
The transformation considers relativity and path_kind to generate a glob that can be added to a GlobSet. Note that the function returns not a compiled Pattern<Glob>, but a Pattern<String>, because after this transformation, building the glob requires Glob::new.
fn transform_pattern_for_glob(pattern: Pattern<String>) -> Pattern<String> {
let anything_anywhere = |p| format!("**/{p}");
let anything_relative = |p, directory| format!("{directory}/**/{p}");
let directory_anywhere = |p| format!("**{p}/");
let directory_relative = |p, directory| format!("{directory}/**/{p}/");
let transformed_pattern = match (&pattern.path_kind, &pattern.relativity) {
(PathKind::Any, PatternRelativity::Anywhere) => anything_anywhere(pattern.pattern),
(PathKind::Any, PatternRelativity::RelativeTo { directory }) => {
anything_relative(pattern.pattern, directory)
}
(PathKind::Directory, PatternRelativity::Anywhere) => directory_anywhere(pattern.pattern),
(PathKind::Directory, PatternRelativity::RelativeTo { directory }) => {
directory_relative(pattern.pattern, directory)
}
};
Pattern {
pattern: transformed_pattern,
..pattern
}
}
I could merge the closures into the match and lower the number of lines, but adding the closures increased self-documentation. Instead of multiple if/else branches, I tend to use match with tuples to have a clearer picture. The corresponding if/else code without closures would be like:
let transformed_pattern = if pattern.path_kind == PathKind::Any {
if pattern.relativity == PatternRelativity::Anywhere {
format!("**/{p}")
} else if ...
}
...
And in my opinion, this latter format is more error-prone and less readable.
Combining it all together
At this point, we can revisit content_to_patterns again:
1 fn content_to_patterns(
2 ignore_root: &Path,
3 source: Option<&Path>,
4 content: &str,
5 ) -> Vec<Pattern<Result<Glob>>> {
6 watch!(source);
7 let patterns: Vec<Pattern<Result<Glob>>> = content
8 .lines()
9 .enumerate()
10 ...
11 .map(|(line, source)| build_pattern(source, line))
12 .map(transform_pattern_for_glob)
13 .map(|pc| pc.map(|s|
14 Glob::new(&s).map_err(Error::from)))
15 .collect();
16
17 patterns
18 }
19
The last step in the transformation is creating the Glob object, as in the highlighted lines above. It runs Pattern<String>.map with Glob::new to get a Pattern<Result<Glob>>. Error and Result are custom types defined within the crate using the thiserror crate.
After we have a vector of Pattern<Result<Glob>>, we report the errors in clear_glob_errors to get Vec<Pattern<Glob>> from this vector. The function is defined as:
1 fn clear_glob_errors(
2 sender: &Sender<Result<PathMetadata>>,
3 new_patterns: Vec<Pattern<Result<Glob>>>,
4 ) -> Vec<Pattern<Glob>> {
5 let new_glob_patterns: Vec<Pattern<Glob>> = new_patterns
6 .into_iter()
7 .filter_map(|p| match p.transpose() {
8 Ok(p) => Some(p),
9 Err(e) => {
10 sender
11 .send(Err(Error::from(anyhow!("Error in glob pattern: {:?}", e))))
12 .expect("Error in channel");
13 None
14 }
15 })
16 .collect();
17 new_glob_patterns
18 }
The sender is the same channel that we use to send the results. This communication channel is used to report only the errors, not PathMetadata; hence, when we encounter an Err(e) in new_patterns, it’s reported to the same channel that the results are expected. Handling the errors first seems like a common theme here as well.
This is also one of the reasons walk_serial receives a channel instead of a vector. Our usual use case is traversing all the directories in parallel, and without channel-based communication in the serial version, we would need to duplicate this function.
At this point, I completed the walk_serial functionality. I wrote tests. I’m using the test-case crate for writing many tests encompassing different use cases. I’m omitting them here for brevity.
Writing a Parallel Walker
Converting walk_serial to a parallel one is quite trivial. As we already used channels in the serial version, we have all the components of a parallel walker. For the sake of simplicity, I won’t use a thread pool and instead spawn a new thread for each task. One question is what’s the unit task that we’ll use to create tasks.
jwalk uses directories as points to spawn new tasks. That’s a sensible approach, and I’ll use this as well. This means a single directory will be processed by a single thread, even if it contains one million files, and 10 directories will be processed by 10 threads even if each contains one file. In practice, I think we can assume directories are natural chunks for this problem.
The interface for the parallel walker is identical to the serial version. This is to replace one with the other when the need arises.1
Update: I decided to change the walk_serial interface to use Vec instead of Sender for simplicity.
The only difference is in the final loop. walk_serial calls itself recursively at the end, while walk_parallel calls itself in separate threads.
pub fn walk_parallel(
given: IgnoreRules,
dir: &Path,
walk_options: WalkOptions,
sender: Sender<Result<PathMetadata>>,
) -> Result<()> {
....
crossbeam::scope(|s| {
for child_dir in child_dirs {
let dwi = dir_with_ignores.clone();
let walk_options = walk_options.clone();
let sender = sender.clone();
s.spawn(move |_| walk_parallel(dwi, &child_dir.path, walk_options, sender));
}
})
.expect("Error in crossbeam scope in walk_parallel");
Ok(())
}
Code
The code is soon to be released, and I’ll add a link to it. You can check my GitHub profile if I forget.