rust-filepatterns: match exact `rootglob`s with a `HashSet`, not in the regex

This optimization yields some very interesting results in `rootglob`-heavy
repositories.

I build a test repository of the following structure:

```
root
    /<uuid>/build/empty_file
    ... repeat for 4000 entries
```

and a `.hgignore` containing the corresponding 4000 `rootglob` entries pointing
to all `build/` folders.

Rust+c `hg status` goes from 350ms down to 110ms.

Differential Revision: https://phab.mercurial-scm.org/D8491

rust/hg-core/src/filepatterns.rs

@@ -1,665 +1,660 b''
 // filepatterns.rs
 //
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Handling of Mercurial-specific patterns.
 
 use crate::{
     utils::{
         files::{canonical_path, get_bytes_from_path, get_path_from_bytes},
         hg_path::{path_to_hg_path_buf, HgPathBuf, HgPathError},
         SliceExt,
     },
     FastHashMap, PatternError,
 };
 use lazy_static::lazy_static;
 use regex::bytes::{NoExpand, Regex};
 use std::fs::File;
 use std::io::Read;
 use std::ops::Deref;
 use std::path::{Path, PathBuf};
 use std::vec::Vec;
 
 lazy_static! {
     static ref RE_ESCAPE: Vec<Vec<u8>> = {
         let mut v: Vec<Vec<u8>> = (0..=255).map(|byte| vec![byte]).collect();
         let to_escape = b"()[]{}?*+-|^$\\.&~# \t\n\r\x0b\x0c";
         for byte in to_escape {
             v[*byte as usize].insert(0, b'\\');
         }
         v
     };
 }
 
 /// These are matched in order
 const GLOB_REPLACEMENTS: &[(&[u8], &[u8])] =
     &[(b"*/", b"(?:.*/)?"), (b"*", b".*"), (b"", b"[^/]*")];
 
 /// Appended to the regexp of globs
 const GLOB_SUFFIX: &[u8; 7] = b"(?:/|$)";
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 pub enum PatternSyntax {
     /// A regular expression
     Regexp,
     /// Glob that matches at the front of the path
     RootGlob,
     /// Glob that matches at any suffix of the path (still anchored at
     /// slashes)
     Glob,
     /// a path relative to repository root, which is matched recursively
     Path,
     /// A path relative to cwd
     RelPath,
     /// an unrooted glob (*.rs matches Rust files in all dirs)
     RelGlob,
     /// A regexp that needn't match the start of a name
     RelRegexp,
     /// A path relative to repository root, which is matched non-recursively
     /// (will not match subdirectories)
     RootFiles,
     /// A file of patterns to read and include
     Include,
     /// A file of patterns to match against files under the same directory
     SubInclude,
 }
 
 /// Transforms a glob pattern into a regex
 fn glob_to_re(pat: &[u8]) -> Vec<u8> {
     let mut input = pat;
     let mut res: Vec<u8> = vec![];
     let mut group_depth = 0;
 
     while let Some((c, rest)) = input.split_first() {
         input = rest;
 
         match c {
             b'*' => {
                 for (source, repl) in GLOB_REPLACEMENTS {
                     if let Some(rest) = input.drop_prefix(source) {
                         input = rest;
                         res.extend(*repl);
                         break;
                     }
                 }
             }
             b'?' => res.extend(b"."),
             b'[' => {
                 match input.iter().skip(1).position(|b| *b == b']') {
                     None => res.extend(b"\\["),
                     Some(end) => {
                         // Account for the one we skipped
                         let end = end + 1;
 
                         res.extend(b"[");
 
                         for (i, b) in input[..end].iter().enumerate() {
                             if *b == b'!' && i == 0 {
                                 res.extend(b"^")
                             } else if *b == b'^' && i == 0 {
                                 res.extend(b"\\^")
                             } else if *b == b'\\' {
                                 res.extend(b"\\\\")
                             } else {
                                 res.push(*b)
                             }
                         }
                         res.extend(b"]");
                         input = &input[end + 1..];
                     }
                 }
             }
             b'{' => {
                 group_depth += 1;
                 res.extend(b"(?:")
             }
             b'}' if group_depth > 0 => {
                 group_depth -= 1;
                 res.extend(b")");
             }
             b',' if group_depth > 0 => res.extend(b"|"),
             b'\\' => {
                 let c = {
                     if let Some((c, rest)) = input.split_first() {
                         input = rest;
                         c
                     } else {
                         c
                     }
                 };
                 res.extend(&RE_ESCAPE[*c as usize])
             }
             _ => res.extend(&RE_ESCAPE[*c as usize]),
         }
     }
     res
 }
 
 fn escape_pattern(pattern: &[u8]) -> Vec<u8> {
     pattern
         .iter()
         .flat_map(|c| RE_ESCAPE[*c as usize].clone())
         .collect()
 }
 
 pub fn parse_pattern_syntax(
     kind: &[u8],
 ) -> Result<PatternSyntax, PatternError> {
     match kind {
         b"re:" => Ok(PatternSyntax::Regexp),
         b"path:" => Ok(PatternSyntax::Path),
         b"relpath:" => Ok(PatternSyntax::RelPath),
         b"rootfilesin:" => Ok(PatternSyntax::RootFiles),
         b"relglob:" => Ok(PatternSyntax::RelGlob),
         b"relre:" => Ok(PatternSyntax::RelRegexp),
         b"glob:" => Ok(PatternSyntax::Glob),
         b"rootglob:" => Ok(PatternSyntax::RootGlob),
         b"include:" => Ok(PatternSyntax::Include),
         b"subinclude:" => Ok(PatternSyntax::SubInclude),
         _ => Err(PatternError::UnsupportedSyntax(
             String::from_utf8_lossy(kind).to_string(),
         )),
     }
 }
 
 /// Builds the regex that corresponds to the given pattern.
 /// If within a `syntax: regexp` context, returns the pattern,
 /// otherwise, returns the corresponding regex.
 fn _build_single_regex(entry: &IgnorePattern) -> Vec<u8> {
     let IgnorePattern {
         syntax, pattern, ..
     } = entry;
     if pattern.is_empty() {
         return vec![];
     }
     match syntax {
         // The `regex` crate adds `.*` to the start and end of expressions
         // if there are no anchors, so add them.
         PatternSyntax::Regexp => [b"^", &pattern[..], b"$"].concat(),
         PatternSyntax::RelRegexp => {
             // The `regex` crate accepts `**` while `re2` and Python's `re`
             // do not. Checking for `*` correctly triggers the same error all
             // engines.
             if pattern[0] == b'^' || pattern[0] == b'*' {
                 return pattern.to_owned();
             }
             [&b".*"[..], pattern].concat()
         }
         PatternSyntax::Path | PatternSyntax::RelPath => {
             if pattern == b"." {
                 return vec![];
             }
             [escape_pattern(pattern).as_slice(), b"(?:/|$)"].concat()
         }
         PatternSyntax::RootFiles => {
             let mut res = if pattern == b"." {
                 vec![b'^']
             } else {
                 // Pattern is a directory name.
                 [b"^", escape_pattern(pattern).as_slice(), b"/"].concat()
             };
 
             // Anything after the pattern must be a non-directory.
             res.extend(b"[^/]+$");
             res.push(b'$');
             res
         }
         PatternSyntax::RelGlob => {
             let glob_re = glob_to_re(pattern);
             if let Some(rest) = glob_re.drop_prefix(b"[^/]*") {
                 [b".*", rest, GLOB_SUFFIX].concat()
             } else {
                 [b"(?:.*/)?", glob_re.as_slice(), GLOB_SUFFIX].concat()
             }
         }
         PatternSyntax::Glob | PatternSyntax::RootGlob => {
             [b"^", glob_to_re(pattern).as_slice(), GLOB_SUFFIX].concat()
         }
         PatternSyntax::Include | PatternSyntax::SubInclude => unreachable!(),
     }
 }
 
 const GLOB_SPECIAL_CHARACTERS: [u8; 7] =
     [b'*', b'?', b'[', b']', b'{', b'}', b'\\'];
 
 /// TODO support other platforms
 #[cfg(unix)]
 pub fn normalize_path_bytes(bytes: &[u8]) -> Vec<u8> {
     if bytes.is_empty() {
         return b".".to_vec();
     }
     let sep = b'/';
 
     let mut initial_slashes = bytes.iter().take_while(|b| **b == sep).count();
     if initial_slashes > 2 {
         // POSIX allows one or two initial slashes, but treats three or more
         // as single slash.
         initial_slashes = 1;
     }
     let components = bytes
         .split(|b| *b == sep)
         .filter(|c| !(c.is_empty() || c == b"."))
         .fold(vec![], |mut acc, component| {
             if component != b".."
                 || (initial_slashes == 0 && acc.is_empty())
                 || (!acc.is_empty() && acc[acc.len() - 1] == b"..")
             {
                 acc.push(component)
             } else if !acc.is_empty() {
                 acc.pop();
             }
             acc
         });
     let mut new_bytes = components.join(&sep);
 
     if initial_slashes > 0 {
         let mut buf: Vec<_> = (0..initial_slashes).map(|_| sep).collect();
         buf.extend(new_bytes);
         new_bytes = buf;
     }
     if new_bytes.is_empty() {
         b".".to_vec()
     } else {
         new_bytes
     }
 }
 
 /// Wrapper function to `_build_single_regex` that short-circuits 'exact' globs
 /// that don't need to be transformed into a regex.
 pub fn build_single_regex(
     entry: &IgnorePattern,
-) -> Result<Vec<u8>, PatternError> {
+) -> Result<Option<Vec<u8>>, PatternError> {
     let IgnorePattern {
         pattern, syntax, ..
     } = entry;
     let pattern = match syntax {
         PatternSyntax::RootGlob
         | PatternSyntax::Path
         | PatternSyntax::RelGlob
         | PatternSyntax::RootFiles => normalize_path_bytes(&pattern),
         PatternSyntax::Include | PatternSyntax::SubInclude => {
             return Err(PatternError::NonRegexPattern(entry.clone()))
         }
         _ => pattern.to_owned(),
     };
     if *syntax == PatternSyntax::RootGlob
         && !pattern.iter().any(|b| GLOB_SPECIAL_CHARACTERS.contains(b))
     {
-        // The `regex` crate adds `.*` to the start and end of expressions
-        // if there are no anchors, so add the start anchor.
-        let mut escaped = vec![b'^'];
-        escaped.extend(escape_pattern(&pattern));
-        escaped.extend(GLOB_SUFFIX);
-        Ok(escaped)
+        Ok(None)
     } else {
         let mut entry = entry.clone();
         entry.pattern = pattern;
-        Ok(_build_single_regex(&entry))
+        Ok(Some(_build_single_regex(&entry)))
     }
 }
 
 lazy_static! {
     static ref SYNTAXES: FastHashMap<&'static [u8], &'static [u8]> = {
         let mut m = FastHashMap::default();
 
         m.insert(b"re".as_ref(), b"relre:".as_ref());
         m.insert(b"regexp".as_ref(), b"relre:".as_ref());
         m.insert(b"glob".as_ref(), b"relglob:".as_ref());
         m.insert(b"rootglob".as_ref(), b"rootglob:".as_ref());
         m.insert(b"include".as_ref(), b"include:".as_ref());
         m.insert(b"subinclude".as_ref(), b"subinclude:".as_ref());
         m
     };
 }
 
 #[derive(Debug)]
 pub enum PatternFileWarning {
     /// (file path, syntax bytes)
     InvalidSyntax(PathBuf, Vec<u8>),
     /// File path
     NoSuchFile(PathBuf),
 }
 
 pub fn parse_pattern_file_contents<P: AsRef<Path>>(
     lines: &[u8],
     file_path: P,
     warn: bool,
 ) -> Result<(Vec<IgnorePattern>, Vec<PatternFileWarning>), PatternError> {
     let comment_regex = Regex::new(r"((?:^|[^\\])(?:\\\\)*)#.*").unwrap();
     let comment_escape_regex = Regex::new(r"\\#").unwrap();
     let mut inputs: Vec<IgnorePattern> = vec![];
     let mut warnings: Vec<PatternFileWarning> = vec![];
 
     let mut current_syntax = b"relre:".as_ref();
 
     for (line_number, mut line) in lines.split(|c| *c == b'\n').enumerate() {
         let line_number = line_number + 1;
 
         let line_buf;
         if line.contains(&b'#') {
             if let Some(cap) = comment_regex.captures(line) {
                 line = &line[..cap.get(1).unwrap().end()]
             }
             line_buf = comment_escape_regex.replace_all(line, NoExpand(b"#"));
             line = &line_buf;
         }
 
         let mut line = line.trim_end();
 
         if line.is_empty() {
             continue;
         }
 
         if let Some(syntax) = line.drop_prefix(b"syntax:") {
             let syntax = syntax.trim();
 
             if let Some(rel_syntax) = SYNTAXES.get(syntax) {
                 current_syntax = rel_syntax;
             } else if warn {
                 warnings.push(PatternFileWarning::InvalidSyntax(
                     file_path.as_ref().to_owned(),
                     syntax.to_owned(),
                 ));
             }
             continue;
         }
 
         let mut line_syntax: &[u8] = &current_syntax;
 
         for (s, rels) in SYNTAXES.iter() {
             if let Some(rest) = line.drop_prefix(rels) {
                 line_syntax = rels;
                 line = rest;
                 break;
             }
             if let Some(rest) = line.drop_prefix(&[s, &b":"[..]].concat()) {
                 line_syntax = rels;
                 line = rest;
                 break;
             }
         }
 
         inputs.push(IgnorePattern::new(
             parse_pattern_syntax(&line_syntax).map_err(|e| match e {
                 PatternError::UnsupportedSyntax(syntax) => {
                     PatternError::UnsupportedSyntaxInFile(
                         syntax,
                         file_path.as_ref().to_string_lossy().into(),
                         line_number,
                     )
                 }
                 _ => e,
             })?,
             &line,
             &file_path,
         ));
     }
     Ok((inputs, warnings))
 }
 
 pub fn read_pattern_file<P: AsRef<Path>>(
     file_path: P,
     warn: bool,
 ) -> Result<(Vec<IgnorePattern>, Vec<PatternFileWarning>), PatternError> {
     let mut f = match File::open(file_path.as_ref()) {
         Ok(f) => Ok(f),
         Err(e) => match e.kind() {
             std::io::ErrorKind::NotFound => {
                 return Ok((
                     vec![],
                     vec![PatternFileWarning::NoSuchFile(
                         file_path.as_ref().to_owned(),
                     )],
                 ))
             }
             _ => Err(e),
         },
     }?;
     let mut contents = Vec::new();
 
     f.read_to_end(&mut contents)?;
 
     Ok(parse_pattern_file_contents(&contents, file_path, warn)?)
 }
 
 /// Represents an entry in an "ignore" file.
 #[derive(Debug, Eq, PartialEq, Clone)]
 pub struct IgnorePattern {
     pub syntax: PatternSyntax,
     pub pattern: Vec<u8>,
     pub source: PathBuf,
 }
 
 impl IgnorePattern {
     pub fn new(
         syntax: PatternSyntax,
         pattern: &[u8],
         source: impl AsRef<Path>,
     ) -> Self {
         Self {
             syntax,
             pattern: pattern.to_owned(),
             source: source.as_ref().to_owned(),
         }
     }
 }
 
 pub type PatternResult<T> = Result<T, PatternError>;
 
 /// Wrapper for `read_pattern_file` that also recursively expands `include:`
 /// patterns.
 ///
 /// `subinclude:` is not treated as a special pattern here: unraveling them
 /// needs to occur in the "ignore" phase.
 pub fn get_patterns_from_file(
     pattern_file: impl AsRef<Path>,
     root_dir: impl AsRef<Path>,
 ) -> PatternResult<(Vec<IgnorePattern>, Vec<PatternFileWarning>)> {
     let (patterns, mut warnings) = read_pattern_file(&pattern_file, true)?;
     let patterns = patterns
         .into_iter()
         .flat_map(|entry| -> PatternResult<_> {
             let IgnorePattern {
                 syntax,
                 pattern,
                 source: _,
             } = &entry;
             Ok(match syntax {
                 PatternSyntax::Include => {
                     let inner_include =
                         root_dir.as_ref().join(get_path_from_bytes(&pattern));
                     let (inner_pats, inner_warnings) = get_patterns_from_file(
                         &inner_include,
                         root_dir.as_ref(),
                     )?;
                     warnings.extend(inner_warnings);
                     inner_pats
                 }
                 _ => vec![entry],
             })
         })
         .flatten()
         .collect();
 
     Ok((patterns, warnings))
 }
 
 /// Holds all the information needed to handle a `subinclude:` pattern.
 pub struct SubInclude {
     /// Will be used for repository (hg) paths that start with this prefix.
     /// It is relative to the current working directory, so comparing against
     /// repository paths is painless.
     pub prefix: HgPathBuf,
     /// The file itself, containing the patterns
     pub path: PathBuf,
     /// Folder in the filesystem where this it applies
     pub root: PathBuf,
 }
 
 impl SubInclude {
     pub fn new(
         root_dir: impl AsRef<Path>,
         pattern: &[u8],
         source: impl AsRef<Path>,
     ) -> Result<SubInclude, HgPathError> {
         let normalized_source =
             normalize_path_bytes(&get_bytes_from_path(source));
 
         let source_root = get_path_from_bytes(&normalized_source);
         let source_root = source_root.parent().unwrap_or(source_root.deref());
 
         let path = source_root.join(get_path_from_bytes(pattern));
         let new_root = path.parent().unwrap_or(path.deref());
 
         let prefix = canonical_path(&root_dir, &root_dir, new_root)?;
 
         Ok(Self {
             prefix: path_to_hg_path_buf(prefix).and_then(|mut p| {
                 if !p.is_empty() {
                     p.push(b'/');
                 }
                 Ok(p)
             })?,
             path: path.to_owned(),
             root: new_root.to_owned(),
         })
     }
 }
 
 /// Separate and pre-process subincludes from other patterns for the "ignore"
 /// phase.
 pub fn filter_subincludes(
     ignore_patterns: &[IgnorePattern],
     root_dir: impl AsRef<Path>,
 ) -> Result<(Vec<SubInclude>, Vec<&IgnorePattern>), HgPathError> {
     let mut subincludes = vec![];
     let mut others = vec![];
 
     for ignore_pattern in ignore_patterns.iter() {
         let IgnorePattern {
             syntax,
             pattern,
             source,
         } = ignore_pattern;
         if *syntax == PatternSyntax::SubInclude {
             subincludes.push(SubInclude::new(&root_dir, pattern, &source)?);
         } else {
             others.push(ignore_pattern)
         }
     }
     Ok((subincludes, others))
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use pretty_assertions::assert_eq;
 
     #[test]
     fn escape_pattern_test() {
         let untouched =
             br#"!"%',/0123456789:;<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ_`abcdefghijklmnopqrstuvwxyz"#;
         assert_eq!(escape_pattern(untouched), untouched.to_vec());
         // All escape codes
         assert_eq!(
             escape_pattern(br#"()[]{}?*+-|^$\\.&~# \t\n\r\v\f"#),
             br#"\(\)\[\]\{\}\?\*\+\-\|\^\$\\\\\.\&\~\#\ \\t\\n\\r\\v\\f"#
                 .to_vec()
         );
     }
 
     #[test]
     fn glob_test() {
         assert_eq!(glob_to_re(br#"?"#), br#"."#);
         assert_eq!(glob_to_re(br#"*"#), br#"[^/]*"#);
         assert_eq!(glob_to_re(br#"**"#), br#".*"#);
         assert_eq!(glob_to_re(br#"**/a"#), br#"(?:.*/)?a"#);
         assert_eq!(glob_to_re(br#"a/**/b"#), br#"a/(?:.*/)?b"#);
         assert_eq!(glob_to_re(br#"[a*?!^][^b][!c]"#), br#"[a*?!^][\^b][^c]"#);
         assert_eq!(glob_to_re(br#"{a,b}"#), br#"(?:a|b)"#);
         assert_eq!(glob_to_re(br#".\*\?"#), br#"\.\*\?"#);
     }
 
     #[test]
     fn test_parse_pattern_file_contents() {
         let lines = b"syntax: glob\n*.elc";
 
         assert_eq!(
             parse_pattern_file_contents(lines, Path::new("file_path"), false)
                 .unwrap()
                 .0,
             vec![IgnorePattern::new(
                 PatternSyntax::RelGlob,
                 b"*.elc",
                 Path::new("file_path")
             )],
         );
 
         let lines = b"syntax: include\nsyntax: glob";
 
         assert_eq!(
             parse_pattern_file_contents(lines, Path::new("file_path"), false)
                 .unwrap()
                 .0,
             vec![]
         );
         let lines = b"glob:**.o";
         assert_eq!(
             parse_pattern_file_contents(lines, Path::new("file_path"), false)
                 .unwrap()
                 .0,
             vec![IgnorePattern::new(
                 PatternSyntax::RelGlob,
                 b"**.o",
                 Path::new("file_path")
             )]
         );
     }
 
     #[test]
     fn test_build_single_regex() {
         assert_eq!(
             build_single_regex(&IgnorePattern::new(
                 PatternSyntax::RelGlob,
                 b"rust/target/",
                 Path::new("")
             ))
             .unwrap(),
-            br"(?:.*/)?rust/target(?:/|$)".to_vec(),
+            Some(br"(?:.*/)?rust/target(?:/|$)".to_vec()),
         );
     }
 
     #[test]
     fn test_build_single_regex_shortcut() {
         assert_eq!(
             build_single_regex(&IgnorePattern::new(
                 PatternSyntax::RootGlob,
                 b"",
                 Path::new("")
             ))
             .unwrap(),
-            br"^\.(?:/|$)".to_vec(),
+            None,
         );
         assert_eq!(
             build_single_regex(&IgnorePattern::new(
                 PatternSyntax::RootGlob,
                 b"whatever",
                 Path::new("")
             ))
             .unwrap(),
-            br"^whatever(?:/|$)".to_vec(),
+            None,
         );
         assert_eq!(
             build_single_regex(&IgnorePattern::new(
                 PatternSyntax::RootGlob,
                 b"*.o",
                 Path::new("")
             ))
             .unwrap(),
-            br"^[^/]*\.o(?:/|$)".to_vec(),
+            Some(br"^[^/]*\.o(?:/|$)".to_vec()),
         );
     }
 }

rust/hg-core/src/matchers.rs

@@ -1,930 +1,948 b''
 // matchers.rs
 //
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Structs and types for matching files and directories.
 
 #[cfg(feature = "with-re2")]
 use crate::re2::Re2;
 use crate::{
     dirstate::dirs_multiset::DirsChildrenMultiset,
     filepatterns::{
         build_single_regex, filter_subincludes, get_patterns_from_file,
         PatternFileWarning, PatternResult, SubInclude,
     },
     utils::{
         files::find_dirs,
         hg_path::{HgPath, HgPathBuf},
         Escaped,
     },
     DirsMultiset, DirstateMapError, FastHashMap, IgnorePattern, PatternError,
     PatternSyntax,
 };
 
+use crate::filepatterns::normalize_path_bytes;
 use std::borrow::ToOwned;
 use std::collections::HashSet;
 use std::fmt::{Display, Error, Formatter};
 use std::iter::FromIterator;
 use std::ops::Deref;
 use std::path::{Path, PathBuf};
 
 use micro_timer::timed;
 
 #[derive(Debug, PartialEq)]
 pub enum VisitChildrenSet<'a> {
     /// Don't visit anything
     Empty,
     /// Only visit this directory
     This,
     /// Visit this directory and these subdirectories
     /// TODO Should we implement a `NonEmptyHashSet`?
     Set(HashSet<&'a HgPath>),
     /// Visit this directory and all subdirectories
     Recursive,
 }
 
 pub trait Matcher {
     /// Explicitly listed files
     fn file_set(&self) -> Option<&HashSet<&HgPath>>;
     /// Returns whether `filename` is in `file_set`
     fn exact_match(&self, filename: impl AsRef<HgPath>) -> bool;
     /// Returns whether `filename` is matched by this matcher
     fn matches(&self, filename: impl AsRef<HgPath>) -> bool;
     /// Decides whether a directory should be visited based on whether it
     /// has potential matches in it or one of its subdirectories, and
     /// potentially lists which subdirectories of that directory should be
     /// visited. This is based on the match's primary, included, and excluded
     /// patterns.
     ///
     /// # Example
     ///
     /// Assume matchers `['path:foo/bar', 'rootfilesin:qux']`, we would
     /// return the following values (assuming the implementation of
     /// visit_children_set is capable of recognizing this; some implementations
     /// are not).
     ///
     /// ```text
     /// ```ignore
     /// '' -> {'foo', 'qux'}
     /// 'baz' -> set()
     /// 'foo' -> {'bar'}
     /// // Ideally this would be `Recursive`, but since the prefix nature of
     /// // matchers is applied to the entire matcher, we have to downgrade this
     /// // to `This` due to the (yet to be implemented in Rust) non-prefix
     /// // `RootFilesIn'-kind matcher being mixed in.
     /// 'foo/bar' -> 'this'
     /// 'qux' -> 'this'
     /// ```
     /// # Important
     ///
     /// Most matchers do not know if they're representing files or
     /// directories. They see `['path:dir/f']` and don't know whether `f` is a
     /// file or a directory, so `visit_children_set('dir')` for most matchers
     /// will return `HashSet{ HgPath { "f" } }`, but if the matcher knows it's
     /// a file (like the yet to be implemented in Rust `ExactMatcher` does),
     /// it may return `VisitChildrenSet::This`.
     /// Do not rely on the return being a `HashSet` indicating that there are
     /// no files in this dir to investigate (or equivalently that if there are
     /// files to investigate in 'dir' that it will always return
     /// `VisitChildrenSet::This`).
     fn visit_children_set(
         &self,
         directory: impl AsRef<HgPath>,
     ) -> VisitChildrenSet;
     /// Matcher will match everything and `files_set()` will be empty:
     /// optimization might be possible.
     fn matches_everything(&self) -> bool;
     /// Matcher will match exactly the files in `files_set()`: optimization
     /// might be possible.
     fn is_exact(&self) -> bool;
 }
 
 /// Matches everything.
 ///```
 /// use hg::{ matchers::{Matcher, AlwaysMatcher}, utils::hg_path::HgPath };
 ///
 /// let matcher = AlwaysMatcher;
 ///
 /// assert_eq!(matcher.matches(HgPath::new(b"whatever")), true);
 /// assert_eq!(matcher.matches(HgPath::new(b"b.txt")), true);
 /// assert_eq!(matcher.matches(HgPath::new(b"main.c")), true);
 /// assert_eq!(matcher.matches(HgPath::new(br"re:.*\.c$")), true);
 /// ```
 #[derive(Debug)]
 pub struct AlwaysMatcher;
 
 impl Matcher for AlwaysMatcher {
     fn file_set(&self) -> Option<&HashSet<&HgPath>> {
         None
     }
     fn exact_match(&self, _filename: impl AsRef<HgPath>) -> bool {
         false
     }
     fn matches(&self, _filename: impl AsRef<HgPath>) -> bool {
         true
     }
     fn visit_children_set(
         &self,
         _directory: impl AsRef<HgPath>,
     ) -> VisitChildrenSet {
         VisitChildrenSet::Recursive
     }
     fn matches_everything(&self) -> bool {
         true
     }
     fn is_exact(&self) -> bool {
         false
     }
 }
 
 /// Matches the input files exactly. They are interpreted as paths, not
 /// patterns.
 ///
 ///```
 /// use hg::{ matchers::{Matcher, FileMatcher}, utils::hg_path::HgPath };
 ///
 /// let files = [HgPath::new(b"a.txt"), HgPath::new(br"re:.*\.c$")];
 /// let matcher = FileMatcher::new(&files).unwrap();
 ///
 /// assert_eq!(matcher.matches(HgPath::new(b"a.txt")), true);
 /// assert_eq!(matcher.matches(HgPath::new(b"b.txt")), false);
 /// assert_eq!(matcher.matches(HgPath::new(b"main.c")), false);
 /// assert_eq!(matcher.matches(HgPath::new(br"re:.*\.c$")), true);
 /// ```
 #[derive(Debug)]
 pub struct FileMatcher<'a> {
     files: HashSet<&'a HgPath>,
     dirs: DirsMultiset,
 }
 
 impl<'a> FileMatcher<'a> {
     pub fn new(
         files: &'a [impl AsRef<HgPath>],
     ) -> Result<Self, DirstateMapError> {
         Ok(Self {
             files: HashSet::from_iter(files.iter().map(|f| f.as_ref())),
             dirs: DirsMultiset::from_manifest(files)?,
         })
     }
     fn inner_matches(&self, filename: impl AsRef<HgPath>) -> bool {
         self.files.contains(filename.as_ref())
     }
 }
 
 impl<'a> Matcher for FileMatcher<'a> {
     fn file_set(&self) -> Option<&HashSet<&HgPath>> {
         Some(&self.files)
     }
     fn exact_match(&self, filename: impl AsRef<HgPath>) -> bool {
         self.inner_matches(filename)
     }
     fn matches(&self, filename: impl AsRef<HgPath>) -> bool {
         self.inner_matches(filename)
     }
     fn visit_children_set(
         &self,
         directory: impl AsRef<HgPath>,
     ) -> VisitChildrenSet {
         if self.files.is_empty() || !self.dirs.contains(&directory) {
             return VisitChildrenSet::Empty;
         }
         let dirs_as_set = self.dirs.iter().map(|k| k.deref()).collect();
 
         let mut candidates: HashSet<&HgPath> =
             self.files.union(&dirs_as_set).map(|k| *k).collect();
         candidates.remove(HgPath::new(b""));
 
         if !directory.as_ref().is_empty() {
             let directory = [directory.as_ref().as_bytes(), b"/"].concat();
             candidates = candidates
                 .iter()
                 .filter_map(|c| {
                     if c.as_bytes().starts_with(&directory) {
                         Some(HgPath::new(&c.as_bytes()[directory.len()..]))
                     } else {
                         None
                     }
                 })
                 .collect();
         }
 
         // `self.dirs` includes all of the directories, recursively, so if
         // we're attempting to match 'foo/bar/baz.txt', it'll have '', 'foo',
         // 'foo/bar' in it. Thus we can safely ignore a candidate that has a
         // '/' in it, indicating it's for a subdir-of-a-subdir; the immediate
         // subdir will be in there without a slash.
         VisitChildrenSet::Set(
             candidates
                 .iter()
                 .filter_map(|c| {
                     if c.bytes().all(|b| *b != b'/') {
                         Some(*c)
                     } else {
                         None
                     }
                 })
                 .collect(),
         )
     }
     fn matches_everything(&self) -> bool {
         false
     }
     fn is_exact(&self) -> bool {
         true
     }
 }
 
 /// Matches files that are included in the ignore rules.
 #[cfg_attr(
     feature = "with-re2",
     doc = r##"
 ```
 use hg::{
     matchers::{IncludeMatcher, Matcher},
     IgnorePattern,
     PatternSyntax,
     utils::hg_path::HgPath
 };
 use std::path::Path;
 ///
 let ignore_patterns =
 vec![IgnorePattern::new(PatternSyntax::RootGlob, b"this*", Path::new(""))];
 let (matcher, _) = IncludeMatcher::new(ignore_patterns, "").unwrap();
 ///
 assert_eq!(matcher.matches(HgPath::new(b"testing")), false);
 assert_eq!(matcher.matches(HgPath::new(b"this should work")), true);
 assert_eq!(matcher.matches(HgPath::new(b"this also")), true);
 assert_eq!(matcher.matches(HgPath::new(b"but not this")), false);
 ```
 "##
 )]
 pub struct IncludeMatcher<'a> {
     patterns: Vec<u8>,
     match_fn: Box<dyn for<'r> Fn(&'r HgPath) -> bool + 'a + Sync>,
     /// Whether all the patterns match a prefix (i.e. recursively)
     prefix: bool,
     roots: HashSet<HgPathBuf>,
     dirs: HashSet<HgPathBuf>,
     parents: HashSet<HgPathBuf>,
 }
 
 impl<'a> Matcher for IncludeMatcher<'a> {
     fn file_set(&self) -> Option<&HashSet<&HgPath>> {
         None
     }
 
     fn exact_match(&self, _filename: impl AsRef<HgPath>) -> bool {
         false
     }
 
     fn matches(&self, filename: impl AsRef<HgPath>) -> bool {
         (self.match_fn)(filename.as_ref())
     }
 
     fn visit_children_set(
         &self,
         directory: impl AsRef<HgPath>,
     ) -> VisitChildrenSet {
         let dir = directory.as_ref();
         if self.prefix && self.roots.contains(dir) {
             return VisitChildrenSet::Recursive;
         }
         if self.roots.contains(HgPath::new(b""))
             || self.roots.contains(dir)
             || self.dirs.contains(dir)
             || find_dirs(dir).any(|parent_dir| self.roots.contains(parent_dir))
         {
             return VisitChildrenSet::This;
         }
 
         if self.parents.contains(directory.as_ref()) {
             let multiset = self.get_all_parents_children();
             if let Some(children) = multiset.get(dir) {
                 return VisitChildrenSet::Set(children.to_owned());
             }
         }
         VisitChildrenSet::Empty
     }
 
     fn matches_everything(&self) -> bool {
         false
     }
 
     fn is_exact(&self) -> bool {
         false
     }
 }
 
 #[cfg(feature = "with-re2")]
 /// Returns a function that matches an `HgPath` against the given regex
 /// pattern.
 ///
 /// This can fail when the pattern is invalid or not supported by the
 /// underlying engine `Re2`, for instance anything with back-references.
 #[timed]
 fn re_matcher(
     pattern: &[u8],
 ) -> PatternResult<impl Fn(&HgPath) -> bool + Sync> {
     let regex = Re2::new(pattern);
     let regex = regex.map_err(|e| PatternError::UnsupportedSyntax(e))?;
     Ok(move |path: &HgPath| regex.is_match(path.as_bytes()))
 }
 
 #[cfg(not(feature = "with-re2"))]
 /// Returns a function that matches an `HgPath` against the given regex
 /// pattern.
 ///
 /// This can fail when the pattern is invalid or not supported by the
 /// underlying engine (the `regex` crate), for instance anything with
 /// back-references.
 #[timed]
 fn re_matcher(
     pattern: &[u8],
 ) -> PatternResult<impl Fn(&HgPath) -> bool + Sync> {
     use std::io::Write;
 
     let mut escaped_bytes = vec![];
     for byte in pattern {
         if *byte > 127 {
             write!(escaped_bytes, "\\x{:x}", *byte).unwrap();
         } else {
             escaped_bytes.push(*byte);
         }
     }
 
     // Avoid the cost of UTF8 checking
     //
     // # Safety
     // This is safe because we escaped all non-ASCII bytes.
     let pattern_string = unsafe { String::from_utf8_unchecked(escaped_bytes) };
     let re = regex::bytes::RegexBuilder::new(&pattern_string)
         .unicode(false)
         .build()
         .map_err(|e| PatternError::UnsupportedSyntax(e.to_string()))?;
 
     Ok(move |path: &HgPath| re.is_match(path.as_bytes()))
 }
 
 /// Returns the regex pattern and a function that matches an `HgPath` against
 /// said regex formed by the given ignore patterns.
 fn build_regex_match<'a>(
     ignore_patterns: &'a [&'a IgnorePattern],
 ) -> PatternResult<(Vec<u8>, Box<dyn Fn(&HgPath) -> bool + Sync>)> {
-    let regexps: Result<Vec<_>, PatternError> = ignore_patterns
-        .into_iter()
-        .map(|k| build_single_regex(*k))
-        .collect();
-    let regexps = regexps?;
+    let mut regexps = vec![];
+    let mut exact_set = HashSet::new();
+
+    for pattern in ignore_patterns {
+        if let Some(re) = build_single_regex(pattern)? {
+            regexps.push(re);
+        } else {
+            let exact = normalize_path_bytes(&pattern.pattern);
+            exact_set.insert(HgPathBuf::from_bytes(&exact));
+        }
+    }
+
     let full_regex = regexps.join(&b'|');
 
-    let matcher = re_matcher(&full_regex)?;
-    let func = Box::new(move |filename: &HgPath| matcher(filename));
+    // An empty pattern would cause the regex engine to incorrectly match the
+    // (empty) root directory
+    let func = if !(regexps.is_empty()) {
+        let matcher = re_matcher(&full_regex)?;
+        let func = move |filename: &HgPath| {
+            exact_set.contains(filename) || matcher(filename)
+        };
+        Box::new(func) as Box<dyn Fn(&HgPath) -> bool + Sync>
+    } else {
+        let func = move |filename: &HgPath| exact_set.contains(filename);
+        Box::new(func) as Box<dyn Fn(&HgPath) -> bool + Sync>
+    };
 
     Ok((full_regex, func))
 }
 
 /// Returns roots and directories corresponding to each pattern.
 ///
 /// This calculates the roots and directories exactly matching the patterns and
 /// returns a tuple of (roots, dirs). It does not return other directories
 /// which may also need to be considered, like the parent directories.
 fn roots_and_dirs(
     ignore_patterns: &[IgnorePattern],
 ) -> (Vec<HgPathBuf>, Vec<HgPathBuf>) {
     let mut roots = Vec::new();
     let mut dirs = Vec::new();
 
     for ignore_pattern in ignore_patterns {
         let IgnorePattern {
             syntax, pattern, ..
         } = ignore_pattern;
         match syntax {
             PatternSyntax::RootGlob | PatternSyntax::Glob => {
                 let mut root = vec![];
 
                 for p in pattern.split(|c| *c == b'/') {
                     if p.iter().any(|c| match *c {
                         b'[' | b'{' | b'*' | b'?' => true,
                         _ => false,
                     }) {
                         break;
                     }
                     root.push(HgPathBuf::from_bytes(p));
                 }
                 let buf =
                     root.iter().fold(HgPathBuf::new(), |acc, r| acc.join(r));
                 roots.push(buf);
             }
             PatternSyntax::Path | PatternSyntax::RelPath => {
                 let pat = HgPath::new(if pattern == b"." {
                     &[] as &[u8]
                 } else {
                     pattern
                 });
                 roots.push(pat.to_owned());
             }
             PatternSyntax::RootFiles => {
                 let pat = if pattern == b"." {
                     &[] as &[u8]
                 } else {
                     pattern
                 };
                 dirs.push(HgPathBuf::from_bytes(pat));
             }
             _ => {
                 roots.push(HgPathBuf::new());
             }
         }
     }
     (roots, dirs)
 }
 
 /// Paths extracted from patterns
 #[derive(Debug, PartialEq)]
 struct RootsDirsAndParents {
     /// Directories to match recursively
     pub roots: HashSet<HgPathBuf>,
     /// Directories to match non-recursively
     pub dirs: HashSet<HgPathBuf>,
     /// Implicitly required directories to go to items in either roots or dirs
     pub parents: HashSet<HgPathBuf>,
 }
 
 /// Extract roots, dirs and parents from patterns.
 fn roots_dirs_and_parents(
     ignore_patterns: &[IgnorePattern],
 ) -> PatternResult<RootsDirsAndParents> {
     let (roots, dirs) = roots_and_dirs(ignore_patterns);
 
     let mut parents = HashSet::new();
 
     parents.extend(
         DirsMultiset::from_manifest(&dirs)
             .map_err(|e| match e {
                 DirstateMapError::InvalidPath(e) => e,
                 _ => unreachable!(),
             })?
             .iter()
             .map(|k| k.to_owned()),
     );
     parents.extend(
         DirsMultiset::from_manifest(&roots)
             .map_err(|e| match e {
                 DirstateMapError::InvalidPath(e) => e,
                 _ => unreachable!(),
             })?
             .iter()
             .map(|k| k.to_owned()),
     );
 
     Ok(RootsDirsAndParents {
         roots: HashSet::from_iter(roots),
         dirs: HashSet::from_iter(dirs),
         parents,
     })
 }
 
 /// Returns a function that checks whether a given file (in the general sense)
 /// should be matched.
 fn build_match<'a, 'b>(
     ignore_patterns: &'a [IgnorePattern],
     root_dir: impl AsRef<Path>,
 ) -> PatternResult<(
     Vec<u8>,
     Box<dyn Fn(&HgPath) -> bool + 'b + Sync>,
     Vec<PatternFileWarning>,
 )> {
     let mut match_funcs: Vec<Box<dyn Fn(&HgPath) -> bool + Sync>> = vec![];
     // For debugging and printing
     let mut patterns = vec![];
     let mut all_warnings = vec![];
 
     let (subincludes, ignore_patterns) =
         filter_subincludes(ignore_patterns, root_dir)?;
 
     if !subincludes.is_empty() {
         // Build prefix-based matcher functions for subincludes
         let mut submatchers = FastHashMap::default();
         let mut prefixes = vec![];
 
         for SubInclude { prefix, root, path } in subincludes.into_iter() {
             let (match_fn, warnings) =
                 get_ignore_function(vec![path.to_path_buf()], root)?;
             all_warnings.extend(warnings);
             prefixes.push(prefix.to_owned());
             submatchers.insert(prefix.to_owned(), match_fn);
         }
 
         let match_subinclude = move |filename: &HgPath| {
             for prefix in prefixes.iter() {
                 if let Some(rel) = filename.relative_to(prefix) {
                     if (submatchers.get(prefix).unwrap())(rel) {
                         return true;
                     }
                 }
             }
             false
         };
 
         match_funcs.push(Box::new(match_subinclude));
     }
 
     if !ignore_patterns.is_empty() {
         // Either do dumb matching if all patterns are rootfiles, or match
         // with a regex.
         if ignore_patterns
             .iter()
             .all(|k| k.syntax == PatternSyntax::RootFiles)
         {
             let dirs: HashSet<_> = ignore_patterns
                 .iter()
                 .map(|k| k.pattern.to_owned())
                 .collect();
             let mut dirs_vec: Vec<_> = dirs.iter().cloned().collect();
 
             let match_func = move |path: &HgPath| -> bool {
                 let path = path.as_bytes();
                 let i = path.iter().rfind(|a| **a == b'/');
                 let dir = if let Some(i) = i {
                     &path[..*i as usize]
                 } else {
                     b"."
                 };
                 dirs.contains(dir.deref())
             };
             match_funcs.push(Box::new(match_func));
 
             patterns.extend(b"rootfilesin: ");
             dirs_vec.sort();
             patterns.extend(dirs_vec.escaped_bytes());
         } else {
             let (new_re, match_func) = build_regex_match(&ignore_patterns)?;
             patterns = new_re;
             match_funcs.push(match_func)
         }
     }
 
     Ok(if match_funcs.len() == 1 {
         (patterns, match_funcs.remove(0), all_warnings)
     } else {
         (
             patterns,
             Box::new(move |f: &HgPath| -> bool {
                 match_funcs.iter().any(|match_func| match_func(f))
             }),
             all_warnings,
         )
     })
 }
 
 /// Parses all "ignore" files with their recursive includes and returns a
 /// function that checks whether a given file (in the general sense) should be
 /// ignored.
 pub fn get_ignore_function<'a>(
     all_pattern_files: Vec<PathBuf>,
     root_dir: impl AsRef<Path>,
 ) -> PatternResult<(
     Box<dyn for<'r> Fn(&'r HgPath) -> bool + Sync + 'a>,
     Vec<PatternFileWarning>,
 )> {
     let mut all_patterns = vec![];
     let mut all_warnings = vec![];
 
     for pattern_file in all_pattern_files.into_iter() {
         let (patterns, warnings) =
             get_patterns_from_file(pattern_file, &root_dir)?;
 
         all_patterns.extend(patterns.to_owned());
         all_warnings.extend(warnings);
     }
     let (matcher, warnings) = IncludeMatcher::new(all_patterns, root_dir)?;
     all_warnings.extend(warnings);
     Ok((
         Box::new(move |path: &HgPath| matcher.matches(path)),
         all_warnings,
     ))
 }
 
 impl<'a> IncludeMatcher<'a> {
     pub fn new(
         ignore_patterns: Vec<IgnorePattern>,
         root_dir: impl AsRef<Path>,
     ) -> PatternResult<(Self, Vec<PatternFileWarning>)> {
         let (patterns, match_fn, warnings) =
             build_match(&ignore_patterns, root_dir)?;
         let RootsDirsAndParents {
             roots,
             dirs,
             parents,
         } = roots_dirs_and_parents(&ignore_patterns)?;
 
         let prefix = ignore_patterns.iter().any(|k| match k.syntax {
             PatternSyntax::Path | PatternSyntax::RelPath => true,
             _ => false,
         });
 
         Ok((
             Self {
                 patterns,
                 match_fn,
                 prefix,
                 roots,
                 dirs,
                 parents,
             },
             warnings,
         ))
     }
 
     fn get_all_parents_children(&self) -> DirsChildrenMultiset {
         // TODO cache
         let thing = self
             .dirs
             .iter()
             .chain(self.roots.iter())
             .chain(self.parents.iter());
         DirsChildrenMultiset::new(thing, Some(&self.parents))
     }
 }
 
 impl<'a> Display for IncludeMatcher<'a> {
     fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         write!(
             f,
             "IncludeMatcher(includes='{}')",
             String::from_utf8_lossy(&self.patterns.escaped_bytes())
         )
     }
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use pretty_assertions::assert_eq;
     use std::path::Path;
 
     #[test]
     fn test_roots_and_dirs() {
         let pats = vec![
             IgnorePattern::new(PatternSyntax::Glob, b"g/h/*", Path::new("")),
             IgnorePattern::new(PatternSyntax::Glob, b"g/h", Path::new("")),
             IgnorePattern::new(PatternSyntax::Glob, b"g*", Path::new("")),
         ];
         let (roots, dirs) = roots_and_dirs(&pats);
 
         assert_eq!(
             roots,
             vec!(
                 HgPathBuf::from_bytes(b"g/h"),
                 HgPathBuf::from_bytes(b"g/h"),
                 HgPathBuf::new()
             ),
         );
         assert_eq!(dirs, vec!());
     }
 
     #[test]
     fn test_roots_dirs_and_parents() {
         let pats = vec![
             IgnorePattern::new(PatternSyntax::Glob, b"g/h/*", Path::new("")),
             IgnorePattern::new(PatternSyntax::Glob, b"g/h", Path::new("")),
             IgnorePattern::new(PatternSyntax::Glob, b"g*", Path::new("")),
         ];
 
         let mut roots = HashSet::new();
         roots.insert(HgPathBuf::from_bytes(b"g/h"));
         roots.insert(HgPathBuf::new());
 
         let dirs = HashSet::new();
 
         let mut parents = HashSet::new();
         parents.insert(HgPathBuf::new());
         parents.insert(HgPathBuf::from_bytes(b"g"));
 
         assert_eq!(
             roots_dirs_and_parents(&pats).unwrap(),
             RootsDirsAndParents {
                 roots,
                 dirs,
                 parents
             }
         );
     }
 
     #[test]
     fn test_filematcher_visit_children_set() {
         // Visitchildrenset
         let files = vec![HgPath::new(b"dir/subdir/foo.txt")];
         let matcher = FileMatcher::new(&files).unwrap();
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"dir"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"")),
             VisitChildrenSet::Set(set)
         );
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"subdir"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir")),
             VisitChildrenSet::Set(set)
         );
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"foo.txt"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir")),
             VisitChildrenSet::Set(set)
         );
 
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir/x")),
             VisitChildrenSet::Empty
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir/foo.txt")),
             VisitChildrenSet::Empty
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"folder")),
             VisitChildrenSet::Empty
         );
     }
 
     #[test]
     fn test_filematcher_visit_children_set_files_and_dirs() {
         let files = vec![
             HgPath::new(b"rootfile.txt"),
             HgPath::new(b"a/file1.txt"),
             HgPath::new(b"a/b/file2.txt"),
             // No file in a/b/c
             HgPath::new(b"a/b/c/d/file4.txt"),
         ];
         let matcher = FileMatcher::new(&files).unwrap();
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"a"));
         set.insert(HgPath::new(b"rootfile.txt"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"")),
             VisitChildrenSet::Set(set)
         );
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"b"));
         set.insert(HgPath::new(b"file1.txt"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"a")),
             VisitChildrenSet::Set(set)
         );
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"c"));
         set.insert(HgPath::new(b"file2.txt"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"a/b")),
             VisitChildrenSet::Set(set)
         );
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"d"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"a/b/c")),
             VisitChildrenSet::Set(set)
         );
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"file4.txt"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"a/b/c/d")),
             VisitChildrenSet::Set(set)
         );
 
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"a/b/c/d/e")),
             VisitChildrenSet::Empty
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"folder")),
             VisitChildrenSet::Empty
         );
     }
 
     #[cfg(feature = "with-re2")]
     #[test]
     fn test_includematcher() {
         // VisitchildrensetPrefix
         let (matcher, _) = IncludeMatcher::new(
             vec![IgnorePattern::new(
                 PatternSyntax::RelPath,
                 b"dir/subdir",
                 Path::new(""),
             )],
             "",
         )
         .unwrap();
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"dir"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"")),
             VisitChildrenSet::Set(set)
         );
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"subdir"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir")),
             VisitChildrenSet::Set(set)
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir")),
             VisitChildrenSet::Recursive
         );
         // OPT: This should probably be 'all' if its parent is?
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir/x")),
             VisitChildrenSet::This
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"folder")),
             VisitChildrenSet::Empty
         );
 
         // VisitchildrensetRootfilesin
         let (matcher, _) = IncludeMatcher::new(
             vec![IgnorePattern::new(
                 PatternSyntax::RootFiles,
                 b"dir/subdir",
                 Path::new(""),
             )],
             "",
         )
         .unwrap();
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"dir"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"")),
             VisitChildrenSet::Set(set)
         );
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"subdir"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir")),
             VisitChildrenSet::Set(set)
         );
 
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir")),
             VisitChildrenSet::This
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir/x")),
             VisitChildrenSet::Empty
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"folder")),
             VisitChildrenSet::Empty
         );
 
         // VisitchildrensetGlob
         let (matcher, _) = IncludeMatcher::new(
             vec![IgnorePattern::new(
                 PatternSyntax::Glob,
                 b"dir/z*",
                 Path::new(""),
             )],
             "",
         )
         .unwrap();
 
         let mut set = HashSet::new();
         set.insert(HgPath::new(b"dir"));
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"")),
             VisitChildrenSet::Set(set)
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"folder")),
             VisitChildrenSet::Empty
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir")),
             VisitChildrenSet::This
         );
         // OPT: these should probably be set().
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir")),
             VisitChildrenSet::This
         );
         assert_eq!(
             matcher.visit_children_set(HgPath::new(b"dir/subdir/x")),
             VisitChildrenSet::This
         );
     }
 }