diff --git a/rust/hg-core/src/lib.rs b/rust/hg-core/src/lib.rs
--- a/rust/hg-core/src/lib.rs
+++ b/rust/hg-core/src/lib.rs
@@ -126,6 +126,9 @@
     /// Needed a pattern that can be turned into a regex but got one that can't
     /// This should only happen through programmer error.
     NonRegexPattern(IgnorePattern),
+    /// This is temporary, see `re2/mod.rs`.
+    /// This will cause a fallback to Python.
+    Re2NotInstalled,
 }
 
 impl ToString for PatternError {
@@ -148,6 +151,10 @@
             PatternError::NonRegexPattern(pattern) => {
                 format!("'{:?}' cannot be turned into a regex", pattern)
             }
+            PatternError::Re2NotInstalled => {
+                "Re2 is not installed, cannot use regex functionality."
+                    .to_string()
+            }
         }
     }
 }
diff --git a/rust/hg-core/src/matchers.rs b/rust/hg-core/src/matchers.rs
--- a/rust/hg-core/src/matchers.rs
+++ b/rust/hg-core/src/matchers.rs
@@ -7,7 +7,12 @@
 
 //! Structs and types for matching files and directories.
 
-use crate::{utils::hg_path::HgPath, DirsMultiset, DirstateMapError};
+#[cfg(feature = "with-re2")]
+use crate::re2::Re2;
+use crate::{
+    filepatterns::PatternResult, utils::hg_path::HgPath, DirsMultiset,
+    DirstateMapError, PatternError,
+};
 use std::collections::HashSet;
 use std::iter::FromIterator;
 use std::ops::Deref;
@@ -215,6 +220,28 @@
         true
     }
 }
+
+const MAX_RE_SIZE: usize = 20000;
+
+#[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.
+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"))]
+fn re_matcher(_: &[u8]) -> PatternResult<Box<dyn Fn(&HgPath) -> bool + Sync>> {
+    Err(PatternError::Re2NotInstalled)
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;