crates/gunnar-policy/src/pattern.rs
//! Reference-name patterns.
//!
//! One matcher, used by the ref-name gate and by branch protection alike (one
//! implementation). Two matchers is how `refs/heads/*` comes to mean one thing
//! in the allowlist and another in the protection rule, and nobody notices
//! until a protected branch is force-pushed.
//!
//! The syntax is git's `refspec`-flavoured glob, over **bytes**, because
//! reference names are bytes:
//!
//! | token | matches |
//! |---|---|
//! | `*` | any run of bytes, **not crossing `/`** |
//! | `**` | any run of bytes, including `/` |
//! | `?` | exactly one byte, not `/` |
//! | anything else | itself, literally |
//!
//! `refs/heads/*` therefore matches `refs/heads/main` but **not**
//! `refs/heads/feat/login`; `refs/heads/**` matches both. That distinction is the
//! whole reason `**` exists here, and it is pinned by a test in both directions.
//! A `**` may also absorb the `/` that follows it, so `refs/heads/**/fix` matches
//! `refs/heads/fix`.
use crate::error::{Error, Result};
/// A compiled reference-name pattern.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RefPattern(String);
impl RefPattern {
/// Compile `pattern`, refusing what could never be a reference name.
pub fn new(pattern: impl Into<String>) -> Result<Self> {
let pattern = pattern.into();
if pattern.is_empty() {
return Err(Error::BadPattern {
pattern,
reason: "empty",
});
}
if pattern.contains('\\') {
return Err(Error::BadPattern {
pattern,
reason: "backslash is not a reference-name character and is not an escape here",
});
}
if pattern.contains("***") {
return Err(Error::BadPattern {
pattern,
reason: "`***` is not a token; use `**`",
});
}
Ok(RefPattern(pattern))
}
/// The pattern as written.
pub fn as_str(&self) -> &str {
&self.0
}
/// Does `name` match?
pub fn matches(&self, name: &[u8]) -> bool {
glob(self.0.as_bytes(), name)
}
/// Does this reference match?
///
/// A `&str` rather than a validated newtype: `gunnar_store::FullName` went
/// with `RefStore`, and `GitOps` names references with `String`. Matching
/// never depended on the name being valid — a glob over bytes is a glob
/// over bytes — so nothing that was being relied on is lost here.
pub fn matches_ref(&self, name: &str) -> bool {
self.matches(name.as_bytes())
}
}
impl std::fmt::Display for RefPattern {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.0)
}
}
impl serde::Serialize for RefPattern {
fn serialize<S: serde::Serializer>(&self, ser: S) -> std::result::Result<S::Ok, S::Error> {
ser.serialize_str(&self.0)
}
}
impl<'de> serde::Deserialize<'de> for RefPattern {
fn deserialize<D: serde::Deserializer<'de>>(de: D) -> std::result::Result<Self, D::Error> {
let raw = String::deserialize(de)?;
RefPattern::new(raw).map_err(serde::de::Error::custom)
}
}
/// Backtracking glob over bytes.
///
/// Patterns are a handful of bytes long, so the recursion is bounded by the
/// pattern and cheap; there is no reason to hand-roll a state machine for it.
fn glob(pattern: &[u8], text: &[u8]) -> bool {
match pattern.first() {
None => text.is_empty(),
Some(b'*') if pattern.get(1) == Some(&b'*') => {
let rest = &pattern[2..];
// `a/**/b` must match `a/b`, so `**` is allowed to absorb the
// separator that follows it.
if let Some(after_slash) = rest.strip_prefix(b"/") {
if glob(after_slash, text) {
return true;
}
}
if glob(rest, text) {
return true;
}
(0..text.len()).any(|i| glob(rest, &text[i + 1..]))
}
Some(b'*') => {
let rest = &pattern[1..];
if glob(rest, text) {
return true;
}
for (i, &byte) in text.iter().enumerate() {
if byte == b'/' {
return false;
}
if glob(rest, &text[i + 1..]) {
return true;
}
}
false
}
Some(b'?') => match text.first() {
Some(&byte) if byte != b'/' => glob(&pattern[1..], &text[1..]),
_ => false,
},
Some(&literal) => match text.first() {
Some(&byte) if byte == literal => glob(&pattern[1..], &text[1..]),
_ => false,
},
}
}
/// Does any pattern in `patterns` match `name`?
pub fn any_matches(patterns: &[RefPattern], name: &str) -> bool {
patterns.iter().any(|p| p.matches_ref(name))
}
/// The first pattern in `patterns` that matches `name`.
pub fn first_match<'a>(patterns: &'a [RefPattern], name: &str) -> Option<&'a RefPattern> {
patterns.iter().find(|p| p.matches_ref(name))
}
#[cfg(test)]
mod tests {
use super::*;
fn m(pattern: &str, name: &str) -> bool {
RefPattern::new(pattern).unwrap().matches(name.as_bytes())
}
#[test]
fn star_does_not_cross_a_slash_but_doublestar_does() {
// The whole point of having both tokens. If these two ever agree, one of
// them has stopped working and every `refs/heads/*` protection rule has
// silently changed meaning.
assert!(m("refs/heads/*", "refs/heads/main"));
assert!(!m("refs/heads/*", "refs/heads/feat/login"));
assert!(m("refs/heads/**", "refs/heads/main"));
assert!(m("refs/heads/**", "refs/heads/feat/login"));
}
#[test]
fn literals_anchor_at_both_ends() {
assert!(m("refs/heads/main", "refs/heads/main"));
assert!(!m("refs/heads/main", "refs/heads/maintenance"));
assert!(!m("refs/heads/main", "xrefs/heads/main"));
assert!(!m("heads/main", "refs/heads/main"));
}
#[test]
fn prefix_and_suffix_stars() {
assert!(m("refs/heads/tmp-*", "refs/heads/tmp-thing"));
assert!(!m("refs/heads/tmp-*", "refs/heads/temp-thing"));
assert!(m("refs/tags/*-rc*", "refs/tags/v1-rc2"));
}
#[test]
fn doublestar_absorbs_the_following_slash() {
assert!(m("refs/heads/**/fix", "refs/heads/fix"));
assert!(m("refs/heads/**/fix", "refs/heads/a/b/fix"));
assert!(!m("refs/heads/**/fix", "refs/heads/fixx"));
}
#[test]
fn question_mark_is_one_byte_and_not_a_slash() {
assert!(m("refs/heads/v?", "refs/heads/v1"));
assert!(!m("refs/heads/v?", "refs/heads/v12"));
assert!(!m("refs/heads/a?b", "refs/heads/a/b"));
}
#[test]
fn malformed_patterns_are_refused_rather_than_silently_matching_nothing() {
assert!(RefPattern::new("").is_err());
assert!(RefPattern::new("refs/heads/a\\b").is_err());
assert!(RefPattern::new("refs/***").is_err());
}
#[test]
fn matching_is_over_bytes_not_utf8() {
let pattern = RefPattern::new("refs/heads/*").unwrap();
assert!(pattern.matches(b"refs/heads/\xff\xfe"));
}
}