litnik 0.2.1

An embedded Lit and FileCheck runner for compiler test suites.
Documentation
use std::collections::HashSet;
use std::ops::Deref;

#[derive(Debug, Clone, PartialEq, Eq)]
enum Token {
    End,
    Or,
    And,
    Not,
    LParen,
    RParen,
    Match(String),
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct Error(String);

impl Error {
    fn parse(message: impl Into<String>) -> Self {
        Self(message.into())
    }

    fn in_expression(self, expression: &str) -> Self {
        Self(format!("{}\nin expression: {:?}", self.0, expression))
    }
}

impl Deref for Error {
    type Target = str;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(&self.0)
    }
}

impl std::error::Error for Error {}

struct Lexer<'a> {
    text: &'a str,
    pos: usize,
}

impl<'a> Lexer<'a> {
    fn new(expr: &'a str) -> Self {
        Self { text: expr, pos: 0 }
    }

    fn remaining(&self) -> &'a str {
        &self.text[self.pos..]
    }

    fn next_token(&mut self) -> Result<Token, Error> {
        self.skip_ws();

        let rest = self.remaining();
        if rest.is_empty() {
            return Ok(Token::End);
        }

        if rest.starts_with("&&") {
            self.pos += 2;
            return Ok(Token::And);
        }
        if rest.starts_with("||") {
            self.pos += 2;
            return Ok(Token::Or);
        }
        if rest.starts_with("!") {
            self.pos += 1;
            return Ok(Token::Not);
        }
        if rest.starts_with("(") {
            self.pos += 1;
            return Ok(Token::LParen);
        }
        if rest.starts_with(")") {
            self.pos += 1;
            return Ok(Token::RParen);
        }

        let start = self.pos;
        let mut idx = self.pos;

        loop {
            let tail = &self.text[idx..];
            if let Some(regex) = tail.strip_prefix("{{") {
                let Some(end) = regex.find("}}") else {
                    break;
                };
                if end == 0 {
                    break;
                }
                idx += 2 + end + 2;
                continue;
            }

            let identifier_len = tail
                .bytes()
                .take_while(|byte| {
                    matches!(
                        byte,
                        b'-' | b'+' | b'=' | b'.' | b'_'
                            | b'a'..=b'z'
                            | b'A'..=b'Z'
                            | b'0'..=b'9'
                    )
                })
                .count();
            if identifier_len == 0 {
                break;
            }
            idx += identifier_len;
        }

        if idx == start {
            return Err(Error::parse(format!("couldn't parse text: {:?}", rest)));
        }
        self.pos = idx;
        Ok(Token::Match(self.text[start..idx].to_string()))
    }

    fn skip_ws(&mut self) {
        while self.pos < self.text.len() {
            let mut chars = self.text[self.pos..].chars();
            let Some(ch) = chars.next() else {
                break;
            };
            if ch.is_whitespace() {
                self.pos += ch.len_utf8();
                continue;
            }
            break;
        }
    }
}

pub(crate) fn evaluate(expr: &str, variables: &HashSet<String>) -> Result<bool, Error> {
    let mut vars = variables.clone();
    vars.insert("true".into());
    let mut parser = Parser::new(expr).map_err(|error| error.in_expression(expr))?;
    parser
        .parse_all(&vars)
        .map_err(|error| error.in_expression(expr))
}

struct Parser<'a> {
    lexer: Lexer<'a>,
    token: Token,
}

impl<'a> Parser<'a> {
    fn new(expr: &'a str) -> Result<Self, Error> {
        let mut lexer = Lexer::new(expr);
        let first = lexer.next_token()?;
        Ok(Self {
            lexer,
            token: first,
        })
    }

    fn consume(&mut self, expected: &Token) -> Result<bool, Error> {
        if &self.token == expected {
            self.token = self.lexer.next_token()?;
            Ok(true)
        } else {
            Ok(false)
        }
    }

    fn expect(&mut self, expected: &Token) -> Result<(), Error> {
        if self.consume(expected)? {
            Ok(())
        } else {
            Err(Error::parse(format!(
                "expected: {}\nhave: {}",
                quote(expected),
                quote(&self.token)
            )))
        }
    }

    fn parse_all(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
        let value = self.parse_or(variables)?;
        self.expect(&Token::End)?;
        Ok(value)
    }

    fn parse_or(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
        let mut left = self.parse_and(variables)?;
        while let Token::Or = self.token {
            self.consume(&Token::Or)?;
            let right = self.parse_and(variables)?;
            left = left || right;
        }
        Ok(left)
    }

    fn parse_and(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
        let mut left = self.parse_not(variables)?;
        while let Token::And = self.token {
            self.consume(&Token::And)?;
            let right = self.parse_not(variables)?;
            left = left && right;
        }
        Ok(left)
    }

    fn parse_not(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
        if self.consume(&Token::Not)? {
            return Ok(!self.parse_not(variables)?);
        }

        if self.consume(&Token::LParen)? {
            let value = self.parse_or(variables)?;
            self.expect(&Token::RParen)?;
            return Ok(value);
        }

        match &self.token {
            Token::Match(_) => {
                let token = self.token.clone();
                self.token = self.lexer.next_token()?;
                let Token::Match(raw) = token else {
                    unreachable!()
                };
                matches_expr(&raw, variables)
            }
            Token::End => Err(Error::parse(
                "expected: '!', '(', '{{', or identifier\nhave: <end of expression>",
            )),
            Token::And | Token::Or | Token::RParen | Token::LParen | Token::Not => {
                Err(Error::parse(format!(
                    "expected: '!', '(', '{{', or identifier\nhave: {}",
                    quote(&self.token)
                )))
            }
        }
    }
}

fn matches_expr(expr: &str, features: &HashSet<String>) -> Result<bool, Error> {
    let mut parts = Vec::new();
    let re =
        regex::Regex::new(r"\{\{.+?\}\}").expect("the braced regular-expression matcher is valid");
    let mut last = 0usize;
    for mat in re.find_iter(expr) {
        let start = mat.start();
        let end = mat.end();
        if start > last {
            parts.push(regex::escape(&expr[last..start]));
        }
        parts.push(format!("(?:{})", &expr[start + 2..end - 2]));
        last = end;
    }
    if last < expr.len() {
        parts.push(regex::escape(&expr[last..]));
    }

    let pattern = format!(r"\A(?:{})\z", parts.join(""));
    let re = regex::Regex::new(&pattern).map_err(|error| {
        Error::parse(format!(
            "invalid regular expression in match {:?}: {error}",
            expr
        ))
    })?;
    Ok(features.iter().any(|feature| re.is_match(feature)))
}

fn quote(t: &Token) -> String {
    match t {
        Token::End => "<end of expression>".into(),
        Token::Or => "||".into(),
        Token::And => "&&".into(),
        Token::Not => "!".into(),
        Token::LParen => "(".into(),
        Token::RParen => ")".into(),
        Token::Match(v) => format!("{:?}", v),
    }
}

#[cfg(test)]
mod tests {
    use super::evaluate;

    fn make(features: &[&str]) -> std::collections::HashSet<String> {
        features.iter().map(|v| v.to_string()).collect()
    }

    #[test]
    fn operator_precedence() {
        let features = make(&["true", "linux", "target=x86_64-unknown-linux-gnu"]);
        assert!(evaluate("true || false", &features).unwrap());
        assert!(!evaluate("false && false", &features).unwrap());
        assert!(evaluate(
            "linux && (target={{aarch64-.+}} || target={{x86_64-.+}})",
            &features
        )
        .unwrap());
    }

    #[test]
    fn regex_matching() {
        let features = make(&["linux", "target=x86_64-unknown-linux-gnu"]);
        assert!(evaluate("target={{x86_64-.+}}", &features).unwrap());
    }

    #[test]
    fn parse_error_report() {
        let err = evaluate("|| true", &make(&[])).unwrap_err();
        assert!(err.contains("expected: '!', '(', '{', or identifier"));
        assert!(err.contains("have:"));
    }
}