use crate::error::{ParseError, line_col};
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum FileRulePattern {
Literal(String),
Star,
StarStar,
Question,
CharClass {
negated: bool,
ranges: Vec<(char, char)>,
},
Alternation(Vec<FileRulePattern>),
Variable(String),
Sequence(Vec<FileRulePattern>),
}
impl FileRulePattern {
pub fn parse(input: &str) -> Result<FileRulePattern, ParseError> {
let mut parser = GlobParser {
input,
pos: 0,
source: input,
};
let atoms = parser.parse_sequence()?;
if parser.pos != input.len() {
return Err(parser.error_at(parser.pos, "unexpected trailing characters in pattern"));
}
Ok(collapse(atoms))
}
pub fn literal(s: impl Into<String>) -> FileRulePattern {
FileRulePattern::Literal(s.into())
}
pub fn is_meta(&self) -> bool {
match self {
FileRulePattern::Literal(_) => false,
FileRulePattern::Variable(_) => false,
FileRulePattern::Star
| FileRulePattern::StarStar
| FileRulePattern::Question
| FileRulePattern::CharClass { .. } => true,
FileRulePattern::Alternation(_) => true,
FileRulePattern::Sequence(seq) => seq.iter().any(|a| a.is_meta()),
}
}
pub fn is_alternation(&self) -> bool {
matches!(self, FileRulePattern::Alternation(_))
}
pub fn render(&self) -> String {
let mut out = String::new();
self.write_to(&mut out);
out
}
fn write_to(&self, out: &mut String) {
match self {
FileRulePattern::Literal(s) => {
for c in s.chars() {
escape_literal(c, out);
}
}
FileRulePattern::Star => out.push('*'),
FileRulePattern::StarStar => out.push_str("**"),
FileRulePattern::Question => out.push('?'),
FileRulePattern::CharClass { negated, ranges } => {
out.push('[');
if *negated {
out.push('^');
}
for (lo, hi) in ranges {
if lo == hi {
escape_class_char(*lo, out);
} else {
escape_class_char(*lo, out);
out.push('-');
escape_class_char(*hi, out);
}
}
out.push(']');
}
FileRulePattern::Alternation(alts) => {
out.push('{');
for (i, alt) in alts.iter().enumerate() {
if i > 0 {
out.push(',');
}
alt.write_to(out);
}
out.push('}');
}
FileRulePattern::Variable(name) => {
out.push_str("@{");
out.push_str(name);
out.push('}');
}
FileRulePattern::Sequence(seq) => {
for s in seq {
s.write_to(out);
}
}
}
}
}
impl std::fmt::Display for FileRulePattern {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.render())
}
}
fn escape_literal(c: char, out: &mut String) {
match c {
'*' | '?' | '[' | ']' | '{' | '}' | '\\' | ',' | '^' => {
out.push('\\');
out.push(c);
}
c if c.is_control() => {
let mut buf = [0u8; 4];
let bytes = c.encode_utf8(&mut buf).as_bytes();
for &b in bytes {
out.push_str(&format!("\\{:03o}", b));
}
}
c => out.push(c),
}
}
fn escape_class_char(c: char, out: &mut String) {
match c {
']' | '\\' | '^' | '-' => {
out.push('\\');
out.push(c);
}
c => out.push(c),
}
}
fn collapse(seq: Vec<FileRulePattern>) -> FileRulePattern {
match seq.len() {
0 => FileRulePattern::Literal(String::new()),
1 => seq.into_iter().next().unwrap(),
_ => FileRulePattern::Sequence(seq),
}
}
struct GlobParser<'a> {
input: &'a str,
pos: usize,
source: &'a str,
}
impl<'a> GlobParser<'a> {
fn peek(&self) -> Option<char> {
self.input[self.pos..].chars().next()
}
fn bump(&mut self) -> Option<char> {
let c = self.peek()?;
self.pos += c.len_utf8();
Some(c)
}
fn error_at(&self, pos: usize, msg: impl Into<String>) -> ParseError {
let (line, col) = line_col(self.source, pos);
let context = self
.source
.lines()
.nth(line.saturating_sub(1))
.unwrap_or("")
.to_string();
ParseError {
line,
col,
message: msg.into(),
context,
}
}
fn parse_sequence(&mut self) -> Result<Vec<FileRulePattern>, ParseError> {
let mut atoms = Vec::new();
loop {
let c = match self.peek() {
None => break,
Some(c) => c,
};
match c {
'}' | ',' => break, _ => {}
}
match c {
'*' => {
self.bump();
if self.peek() == Some('*') {
self.bump();
atoms.push(FileRulePattern::StarStar);
} else {
atoms.push(FileRulePattern::Star);
}
}
'?' => {
self.bump();
atoms.push(FileRulePattern::Question);
}
'[' => {
self.bump();
let cls = self.parse_char_class()?;
atoms.push(cls);
}
'{' => {
self.bump();
let alts = self.parse_alternation()?;
atoms.push(alts);
}
'@' => {
if self.input[self.pos..].starts_with("@{") {
self.bump();
self.bump();
let name = self.parse_variable_name()?;
atoms.push(FileRulePattern::Variable(name));
} else {
self.bump();
atoms.push(FileRulePattern::Literal("@".to_string()));
}
}
'\\' => {
self.bump();
let esc = self.parse_escape()?;
atoms.push(FileRulePattern::Literal(esc));
}
_ => {
let mut lit = String::new();
while let Some(c) = self.peek() {
if matches!(c, '*' | '?' | '[' | '{' | '}' | '@' | '\\' | ',') {
break;
}
lit.push(c);
self.bump();
}
if lit.is_empty() {
let c = self.bump().unwrap();
lit.push(c);
}
atoms.push(FileRulePattern::Literal(lit));
}
}
}
Ok(atoms)
}
fn parse_char_class(&mut self) -> Result<FileRulePattern, ParseError> {
let negated = if self.peek() == Some('^') {
self.bump();
true
} else {
false
};
let mut ranges: Vec<(char, char)> = Vec::new();
loop {
match self.peek() {
None => {
return Err(self.error_at(self.pos, "unterminated character class `[...]`"));
}
Some(']') => {
self.bump();
break;
}
Some('\\') => {
self.bump();
let c = self.parse_escape_char()?;
ranges.push((c, c));
}
Some(c) => {
self.bump();
if self.peek() == Some('-')
&& self.input[self.pos..].chars().nth(1) != Some(']')
{
self.bump();
match self.peek() {
Some('\\') => {
self.bump();
let hi = self.parse_escape_char()?;
ranges.push((c, hi));
}
Some(hi) => {
self.bump();
ranges.push((c, hi));
}
None => {
return Err(
self.error_at(self.pos, "unterminated character class `[...]`")
);
}
}
} else {
ranges.push((c, c));
}
}
}
}
Ok(FileRulePattern::CharClass { negated, ranges })
}
fn parse_alternation(&mut self) -> Result<FileRulePattern, ParseError> {
let mut alts = Vec::new();
loop {
let inner = self.parse_sequence()?;
alts.push(collapse(inner));
match self.peek() {
Some(',') => {
self.bump();
}
Some('}') => {
self.bump();
break;
}
_ => {
return Err(self.error_at(self.pos, "unterminated alternation `{...}`"));
}
}
}
Ok(FileRulePattern::Alternation(alts))
}
fn parse_variable_name(&mut self) -> Result<String, ParseError> {
let mut name = String::new();
loop {
match self.peek() {
Some('}') => {
self.bump();
break;
}
Some(c) if c.is_alphanumeric() || c == '_' => {
name.push(c);
self.bump();
}
None => {
return Err(self.error_at(self.pos, "unterminated variable `@{...}`"));
}
Some(_) => {
return Err(self.error_at(
self.pos,
"invalid character in variable name (expected alphanumeric or `_`)",
));
}
}
}
if name.is_empty() {
return Err(self.error_at(self.pos, "empty variable name `@{}`"));
}
Ok(name)
}
fn parse_escape(&mut self) -> Result<String, ParseError> {
let c = self.parse_escape_char()?;
Ok(c.to_string())
}
fn parse_escape_char(&mut self) -> Result<char, ParseError> {
match self.bump() {
None => Err(self.error_at(self.pos, "trailing backslash in pattern")),
Some(c) if c.is_ascii_digit() => {
let mut val = c.to_digit(8).unwrap();
for _ in 0..2 {
match self.peek() {
Some(d) if d.is_ascii_digit() && d.is_digit(8) => {
let d = self.bump().unwrap();
val = val * 8 + d.to_digit(8).unwrap();
}
_ => break,
}
}
if val > 0x10FFFF {
return Err(self.error_at(self.pos, "octal escape out of range"));
}
let decoded = char::from_u32(val).ok_or_else(|| {
self.error_at(self.pos, "octal escape is not a valid character")
})?;
Ok(decoded)
}
Some(c) => Ok(c),
}
}
}
#[cfg(test)]
mod tests {
use super::FileRulePattern as P;
fn parse(s: &str) -> P {
P::parse(s).unwrap()
}
#[test]
fn plain_literal() {
let p = parse("/etc/passwd");
assert!(!p.is_meta());
assert_eq!(p.to_string(), "/etc/passwd");
}
#[test]
fn star_is_single_level() {
let p = parse("/tmp/*");
assert!(p.is_meta());
assert_eq!(p.to_string(), "/tmp/*");
}
#[test]
fn starstar_crosses_dirs() {
let p = parse("/dir/**");
assert_eq!(p.to_string(), "/dir/**");
}
#[test]
fn question_mark() {
let p = parse("/a?b");
assert_eq!(p.to_string(), "/a?b");
}
#[test]
fn char_class() {
let p = parse("/x/[a-z0-9]");
assert!(matches!(
p,
P::Sequence(ref s) if matches!(s.last(), Some(P::CharClass { negated: false, .. }))
));
assert_eq!(p.to_string(), "/x/[a-z0-9]");
}
#[test]
fn negated_char_class() {
let p = parse("[^/]");
assert!(matches!(p, P::CharClass { negated: true, .. }));
assert_eq!(p.to_string(), "[^/]");
}
#[test]
fn alternation_round_trip() {
let p = parse("/dir{,1,2}/**");
assert_eq!(p.to_string(), "/dir{,1,2}/**");
}
#[test]
fn empty_alternation_preserved() {
let p = parse("{foo,}");
assert!(matches!(p, P::Alternation(ref a) if a.len() == 2));
assert_eq!(p.to_string(), "{foo,}");
}
#[test]
fn nested_alternation() {
let p = parse("{a,{b,c},d}");
assert_eq!(p.to_string(), "{a,{b,c},d}");
}
#[test]
fn variable_kept_unespanded() {
let p = parse("@{HOME}/**");
assert!(matches!(
p,
P::Sequence(ref s)
if matches!(s.first(), Some(P::Variable(n)) if n == "HOME")
));
assert_eq!(p.to_string(), "@{HOME}/**");
}
#[test]
fn escaped_star_is_literal() {
let p = parse("/a/\\*");
assert_eq!(p.to_string(), "/a/\\*");
let again = parse(&p.to_string());
assert_eq!(p, again);
}
#[test]
fn escaped_comma_is_literal() {
let p = parse("/a\\,b");
assert_eq!(p.to_string(), "/a\\,b");
}
#[test]
fn octal_escape() {
let p = parse("/\\001");
assert!(
matches!(p, P::Sequence(ref s) if s.iter().any(|x| matches!(x, P::Literal(l) if l.starts_with('\u{1}'))))
);
assert_eq!(p.to_string(), "/\\001");
}
#[test]
fn round_trip_is_identity() {
let cases = [
"/etc/passwd",
"/etc/**",
"/home/*/bin/*",
"/opt/{a,b,c}/**",
"/dev/[a-z]*",
"/x/[^/]*",
"/a?b*c",
"@{PROC}/**",
"/tmp/\\*",
"/tmp/{foo,bar,baz}",
"/usr/bin/**",
];
for c in cases {
let p = parse(c);
let rendered = p.to_string();
assert_eq!(
p,
parse(&rendered),
"round trip failed for {c:?} -> {rendered:?}"
);
}
}
#[test]
fn starstar_plus_star() {
let p = parse("/x/***");
assert_eq!(p.to_string(), "/x/***");
}
#[test]
fn unterminated_class_errors() {
let e = P::parse("/x/[abc").unwrap_err();
assert!(e.message.contains("unterminated"));
assert!(e.line >= 1);
}
#[test]
fn unterminated_alternation_errors() {
let e = P::parse("/x/{a,b").unwrap_err();
assert!(e.message.contains("unterminated"));
}
#[test]
fn unterminated_variable_errors() {
let e = P::parse("/x/@{HOME").unwrap_err();
assert!(e.message.contains("unterminated"));
}
#[test]
fn trailing_backslash_errors() {
let e = P::parse("/x/\\").unwrap_err();
assert!(e.message.contains("backslash"));
}
}