entropy-auth 2026.7.31

//! SCIM 2.0 filter-expression parser + evaluator (RFC 7644 §3.4.2.2).
//!
//! A provisioning client filters a collection with expressions like
//! `userName eq "bjensen"` or `title pr and (emails.type eq "work")`. This is
//! the pure, transport-free core: [`parse_filter`] turns the query string into
//! a [`Filter`] AST, and [`Filter::matches`] evaluates it against a resource
//! represented as the crate's [`JsonValue`]. The server maps its rows into
//! `JsonValue` and reuses this for the `?filter=` query on `GET /scim/v2/*`.
//!
//! # Supported grammar (a practical subset)
//!
//! * attribute operators — `eq ne co sw ew gt ge lt le` and the unary `pr`
//!   (present);
//! * logical `and` / `or` / `not`, grouping with `( )`;
//! * dotted attribute paths (`name.familyName`) resolved case-insensitively
//!   (SCIM attribute names are case-insensitive).
//!
//! Operator keywords are case-insensitive. String comparisons are
//! case-insensitive (the SCIM default for non-`caseExact` attributes);
//! numbers and booleans compare exactly. `valuePath` sub-filters
//! (`attr[...]`) are not parsed (documented limitation).

use core::fmt;

use crate::json::JsonValue;

/// A comparison operator (RFC 7644 §3.4.2.2).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum CompareOp {
    /// `eq` — equal.
    Eq,
    /// `ne` — not equal.
    Ne,
    /// `co` — contains.
    Co,
    /// `sw` — starts with.
    Sw,
    /// `ew` — ends with.
    Ew,
    /// `gt` — greater than.
    Gt,
    /// `ge` — greater than or equal.
    Ge,
    /// `lt` — less than.
    Lt,
    /// `le` — less than or equal.
    Le,
}

/// A comparison literal.
#[derive(Debug, Clone, PartialEq)]
pub enum FilterValue {
    /// A quoted string.
    Str(String),
    /// `true` / `false`.
    Bool(bool),
    /// A JSON number.
    Num(f64),
    /// `null`.
    Null,
}

/// A parsed SCIM filter expression.
#[derive(Debug, Clone, PartialEq)]
pub enum Filter {
    /// `attrPath pr` — the attribute is present (and non-null).
    Present(String),
    /// `attrPath op value`.
    Compare(String, CompareOp, FilterValue),
    /// `expr and expr`.
    And(Box<Filter>, Box<Filter>),
    /// `expr or expr`.
    Or(Box<Filter>, Box<Filter>),
    /// `not ( expr )`.
    Not(Box<Filter>),
}

/// A filter parse failure.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ScimFilterError {
    message: &'static str,
}

impl ScimFilterError {
    /// The (non-secret) diagnostic message.
    #[must_use]
    pub fn message(&self) -> &str {
        self.message
    }
}

impl fmt::Display for ScimFilterError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "invalid SCIM filter: {}", self.message)
    }
}

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

fn err(message: &'static str) -> ScimFilterError {
    ScimFilterError { message }
}

// ---------------------------------------------------------------------------
// Tokenizer
// ---------------------------------------------------------------------------

#[derive(Debug, Clone, PartialEq)]
enum Token {
    Ident(String),
    Str(String),
    LParen,
    RParen,
}

fn tokenize(input: &str) -> Result<Vec<Token>, ScimFilterError> {
    let mut tokens = Vec::new();
    let chars: Vec<char> = input.chars().collect();
    let mut i = 0;
    while i < chars.len() {
        let c = chars[i];
        if c.is_whitespace() {
            i += 1;
        } else if c == '(' {
            tokens.push(Token::LParen);
            i += 1;
        } else if c == ')' {
            tokens.push(Token::RParen);
            i += 1;
        } else if c == '"' {
            // Quoted string with `\"` and `\\` escapes.
            let mut s = String::new();
            i += 1;
            loop {
                let Some(&ch) = chars.get(i) else {
                    return Err(err("unterminated string"));
                };
                match ch {
                    '"' => {
                        i += 1;
                        break;
                    }
                    '\\' => {
                        let Some(&next) = chars.get(i + 1) else {
                            return Err(err("dangling escape"));
                        };
                        s.push(next);
                        i += 2;
                    }
                    _ => {
                        s.push(ch);
                        i += 1;
                    }
                }
            }
            tokens.push(Token::Str(s));
        } else {
            // A bare word: attribute path, operator, keyword, number, or
            // literal (true/false/null). Terminated by whitespace or paren.
            let start = i;
            while i < chars.len() && !chars[i].is_whitespace() && chars[i] != '(' && chars[i] != ')'
            {
                i += 1;
            }
            let word: String = chars[start..i].iter().collect();
            tokens.push(Token::Ident(word));
        }
    }
    Ok(tokens)
}

// ---------------------------------------------------------------------------
// Parser (recursive descent; precedence: not > and > or)
// ---------------------------------------------------------------------------

/// Maximum parenthesis/`not` nesting depth. The parser recurses per nesting
/// level, so an untrusted `?filter=` with thousands of nested `(` would
/// otherwise overflow the stack and abort the process. Real SCIM filters nest
/// far below this.
const MAX_FILTER_DEPTH: usize = 32;

/// Maximum total AST nodes. Paren depth alone does NOT bound a long *flat*
/// chain (`x pr or x pr or …`): that builds a left-nested `Or(Or(…))` whose
/// depth equals the term count, which [`Filter::matches`] and the recursive
/// `Drop` then walk — a stack overflow (uncatchable process abort) for a large
/// enough chain. Bounding the node count bounds that recursion regardless of
/// how the depth is reached. Set well above any real filter.
const MAX_FILTER_NODES: usize = 512;

struct Parser {
    tokens: Vec<Token>,
    pos: usize,
    depth: usize,
    nodes: usize,
}

impl Parser {
    fn peek(&self) -> Option<&Token> {
        self.tokens.get(self.pos)
    }

    fn next(&mut self) -> Option<Token> {
        let t = self.tokens.get(self.pos).cloned();
        if t.is_some() {
            self.pos += 1;
        }
        t
    }

    /// Count one AST node, rejecting a filter whose total node count would let
    /// its (left-nested) depth overflow the stack in `matches`/`Drop`.
    fn bump(&mut self) -> Result<(), ScimFilterError> {
        self.nodes += 1;
        if self.nodes > MAX_FILTER_NODES {
            return Err(err("filter too large"));
        }
        Ok(())
    }

    /// A word-token matching `kw` case-insensitively (keywords/operators).
    fn peek_keyword(&self, kw: &str) -> bool {
        matches!(self.peek(), Some(Token::Ident(w)) if w.eq_ignore_ascii_case(kw))
    }

    fn parse_or(&mut self) -> Result<Filter, ScimFilterError> {
        let mut left = self.parse_and()?;
        while self.peek_keyword("or") {
            self.pos += 1;
            let right = self.parse_and()?;
            self.bump()?;
            left = Filter::Or(Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    fn parse_and(&mut self) -> Result<Filter, ScimFilterError> {
        let mut left = self.parse_unary()?;
        while self.peek_keyword("and") {
            self.pos += 1;
            let right = self.parse_unary()?;
            self.bump()?;
            left = Filter::And(Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    fn parse_unary(&mut self) -> Result<Filter, ScimFilterError> {
        if self.peek_keyword("not") {
            self.pos += 1;
            if !matches!(self.next(), Some(Token::LParen)) {
                return Err(err("expected '(' after not"));
            }
            let inner = self.parse_group()?;
            if !matches!(self.next(), Some(Token::RParen)) {
                return Err(err("expected ')'"));
            }
            self.bump()?;
            return Ok(Filter::Not(Box::new(inner)));
        }
        if matches!(self.peek(), Some(Token::LParen)) {
            self.pos += 1;
            let inner = self.parse_group()?;
            if !matches!(self.next(), Some(Token::RParen)) {
                return Err(err("expected ')'"));
            }
            return Ok(inner);
        }
        self.parse_attr_expr()
    }

    /// Parse a parenthesised sub-expression, tracking nesting depth so a crafted
    /// filter cannot recurse the parser into a stack overflow.
    fn parse_group(&mut self) -> Result<Filter, ScimFilterError> {
        self.depth += 1;
        if self.depth > MAX_FILTER_DEPTH {
            return Err(err("filter nesting too deep"));
        }
        let inner = self.parse_or()?;
        self.depth -= 1;
        Ok(inner)
    }

    fn parse_attr_expr(&mut self) -> Result<Filter, ScimFilterError> {
        let Some(Token::Ident(attr)) = self.next() else {
            return Err(err("expected attribute path"));
        };
        let Some(Token::Ident(op)) = self.next() else {
            return Err(err("expected operator"));
        };
        if op.eq_ignore_ascii_case("pr") {
            self.bump()?;
            return Ok(Filter::Present(attr));
        }
        let cmp = match op.to_ascii_lowercase().as_str() {
            "eq" => CompareOp::Eq,
            "ne" => CompareOp::Ne,
            "co" => CompareOp::Co,
            "sw" => CompareOp::Sw,
            "ew" => CompareOp::Ew,
            "gt" => CompareOp::Gt,
            "ge" => CompareOp::Ge,
            "lt" => CompareOp::Lt,
            "le" => CompareOp::Le,
            _ => return Err(err("unknown operator")),
        };
        let value = match self.next() {
            Some(Token::Str(s)) => FilterValue::Str(s),
            Some(Token::Ident(w)) => literal_from_word(&w),
            _ => return Err(err("expected comparison value")),
        };
        self.bump()?;
        Ok(Filter::Compare(attr, cmp, value))
    }
}

/// Interpret a bare word after an operator as a `true`/`false`/`null` literal
/// or a number (an unquoted bareword otherwise is treated as a string).
fn literal_from_word(w: &str) -> FilterValue {
    match w {
        "true" => FilterValue::Bool(true),
        "false" => FilterValue::Bool(false),
        "null" => FilterValue::Null,
        _ => w
            .parse::<f64>()
            .map_or_else(|_| FilterValue::Str(w.to_string()), FilterValue::Num),
    }
}

/// Parse a SCIM filter expression into a [`Filter`].
///
/// # Errors
///
/// Returns [`ScimFilterError`] on any syntax error (unbalanced parens,
/// missing operator/value, unterminated string, …).
pub fn parse_filter(input: &str) -> Result<Filter, ScimFilterError> {
    let tokens = tokenize(input)?;
    if tokens.is_empty() {
        return Err(err("empty filter"));
    }
    let mut parser = Parser {
        tokens,
        pos: 0,
        depth: 0,
        nodes: 0,
    };
    let filter = parser.parse_or()?;
    if parser.pos != parser.tokens.len() {
        return Err(err("trailing tokens"));
    }
    Ok(filter)
}

// ---------------------------------------------------------------------------
// Evaluation
// ---------------------------------------------------------------------------

impl Filter {
    /// Evaluate this filter against a resource (`resource` is the SCIM object
    /// as a [`JsonValue`]).
    #[must_use]
    pub fn matches(&self, resource: &JsonValue) -> bool {
        match self {
            Filter::Present(path) => resolve_path(resource, path).iter().any(|v| !v.is_null()),
            Filter::Compare(path, op, value) => {
                let resolved = resolve_path(resource, path);
                if resolved.is_empty() {
                    // RFC 7644 §3.4.2.2: `ne` against an ABSENT attribute is a
                    // match — the resource does not have that value. Treating
                    // an unresolved path as `false` for every operator made an
                    // absent attribute report as "equal to" every value.
                    return matches!(op, CompareOp::Ne);
                }
                // A multi-valued attribute matches if ANY of its values does.
                resolved.iter().any(|v| compare(v, *op, value))
            }
            Filter::And(a, b) => a.matches(resource) && b.matches(resource),
            Filter::Or(a, b) => a.matches(resource) || b.matches(resource),
            Filter::Not(inner) => !inner.matches(resource),
        }
    }
}

/// Resolve a dotted attribute path against an object, case-insensitively.
fn resolve_path<'a>(resource: &'a JsonValue, path: &str) -> Vec<&'a JsonValue> {
    let mut current: Vec<&JsonValue> = vec![resource];
    for segment in path.split('.') {
        let mut next: Vec<&JsonValue> = Vec::new();
        for node in current {
            match node {
                // A dotted path through a MULTI-VALUED attribute (`emails.value`,
                // `emails.type` — the shape RFC 7643 defines for emails, phone
                // numbers, ims, photos, entitlements and roles) previously
                // resolved to None, because every intermediate segment had to be
                // an object. Every such filter silently matched nothing.
                JsonValue::Array(items) => {
                    for item in items {
                        if let Some(obj) = item.as_object() {
                            if let Some((_, v)) =
                                obj.iter().find(|(k, _)| k.eq_ignore_ascii_case(segment))
                            {
                                next.push(v);
                            }
                        }
                    }
                }
                other => {
                    if let Some(obj) = other.as_object() {
                        if let Some((_, v)) =
                            obj.iter().find(|(k, _)| k.eq_ignore_ascii_case(segment))
                        {
                            next.push(v);
                        }
                    }
                }
            }
        }
        if next.is_empty() {
            return Vec::new();
        }
        current = next;
    }
    // A terminal array (`emails eq …` with no sub-attribute) matches if any
    // element does.
    current
        .into_iter()
        .flat_map(|v| match v {
            JsonValue::Array(items) => items.iter().collect::<Vec<_>>(),
            other => vec![other],
        })
        .collect()
}

/// Compare a resolved resource value against a filter literal under `op`.
fn compare(actual: &JsonValue, op: CompareOp, expected: &FilterValue) -> bool {
    // String comparisons (case-insensitive, the SCIM default).
    if let (Some(a), FilterValue::Str(e)) = (actual.as_str(), expected) {
        let (al, el) = (a.to_lowercase(), e.to_lowercase());
        return match op {
            CompareOp::Eq => al == el,
            CompareOp::Ne => al != el,
            CompareOp::Co => al.contains(&el),
            CompareOp::Sw => al.starts_with(&el),
            CompareOp::Ew => al.ends_with(&el),
            CompareOp::Gt => al > el,
            CompareOp::Ge => al >= el,
            CompareOp::Lt => al < el,
            CompareOp::Le => al <= el,
        };
    }
    // Numeric comparisons.
    if let (Some(a), FilterValue::Num(e)) = (actual.as_f64(), expected) {
        return match op {
            CompareOp::Eq => (a - e).abs() < f64::EPSILON,
            CompareOp::Ne => (a - e).abs() >= f64::EPSILON,
            CompareOp::Gt => a > *e,
            CompareOp::Ge => a >= *e,
            CompareOp::Lt => a < *e,
            CompareOp::Le => a <= *e,
            // co/sw/ew are string-only.
            CompareOp::Co | CompareOp::Sw | CompareOp::Ew => false,
        };
    }
    // Boolean eq/ne.
    if let (Some(a), FilterValue::Bool(e)) = (actual.as_bool(), expected) {
        return match op {
            CompareOp::Eq => a == *e,
            CompareOp::Ne => a != *e,
            _ => false,
        };
    }
    // null eq/ne.
    if let FilterValue::Null = expected {
        return match op {
            CompareOp::Eq => actual.is_null(),
            CompareOp::Ne => !actual.is_null(),
            _ => false,
        };
    }
    false
}

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

    fn user() -> JsonValue {
        JsonValue::parse(
            r#"{"userName":"BJensen","active":true,"name":{"familyName":"Jensen"},"age":30}"#,
        )
        .unwrap()
    }

    fn m(filter: &str) -> bool {
        parse_filter(filter).unwrap().matches(&user())
    }

    #[test]
    fn eq_is_case_insensitive() {
        assert!(m(r#"userName eq "bjensen""#));
        assert!(m(r#"userName eq "BJENSEN""#));
        assert!(!m(r#"userName eq "other""#));
    }

    #[test]
    fn present_contains_starts_ends() {
        assert!(m("userName pr"));
        assert!(!m("nickName pr"));
        assert!(m(r#"userName co "jen""#));
        assert!(m(r#"userName sw "bj""#));
        assert!(m(r#"userName ew "sen""#));
    }

    #[test]
    fn dotted_path_and_bool_and_number() {
        assert!(m(r#"name.familyName eq "jensen""#));
        assert!(m("active eq true"));
        assert!(!m("active eq false"));
        assert!(m("age gt 20"));
        assert!(m("age le 30"));
        assert!(!m("age gt 30"));
    }

    #[test]
    fn logical_and_or_not_grouping() {
        assert!(m(r#"userName eq "bjensen" and active eq true"#));
        assert!(!m(r#"userName eq "nope" and active eq true"#));
        assert!(m(r#"userName eq "nope" or active eq true"#));
        assert!(m(r#"not (userName eq "nope")"#));
        assert!(m(
            r#"(userName eq "bjensen" or userName eq "x") and active eq true"#
        ));
    }

    #[test]
    fn precedence_or_binds_loosest() {
        // a and b or c  ==  (a and b) or c
        assert!(
            parse_filter(r#"userName eq "nope" and active eq true or age eq 30"#)
                .unwrap()
                .matches(&user())
        );
    }

    #[test]
    fn rejects_malformed() {
        assert!(parse_filter("").is_err());
        assert!(parse_filter("userName").is_err());
        assert!(parse_filter("userName eq").is_err());
        assert!(parse_filter(r#"(userName eq "x""#).is_err());
        assert!(parse_filter(r#"userName zz "x""#).is_err());
    }

    #[test]
    fn rejects_over_long_flat_chain() {
        // A long flat or-chain builds a left-nested AST whose depth equals the
        // term count; matches()/Drop would recurse that deep. The node cap must
        // reject it rather than let it overflow the stack.
        let chain = "userName pr or ".repeat(MAX_FILTER_NODES + 10) + "userName pr";
        assert!(parse_filter(&chain).is_err());
        // A modest chain still parses + evaluates.
        let ok = "userName pr or active eq true or age gt 10";
        assert!(parse_filter(ok).is_ok());
    }

    #[test]
    fn rejects_over_deep_nesting() {
        // Deeply nested parens must be rejected, not recursed into a stack
        // overflow. Depth beyond the cap fails before matching close-parens.
        let deep = format!("{}userName pr", "(".repeat(MAX_FILTER_DEPTH + 5));
        assert!(parse_filter(&deep).is_err());
        // A modest, legitimately-nested filter still parses.
        let ok = format!("{}userName pr{}", "(".repeat(4), ")".repeat(4));
        assert!(parse_filter(&ok).is_ok());
    }

    #[test]
    fn multi_valued_paths_resolve() {
        // RFC 7643's canonical multi-valued shape. Every dotted path through it
        // previously resolved to nothing, so these filters matched no resource.
        let user = JsonValue::parse(
            r#"{"userName":"bj","emails":[{"value":"a@x.com","type":"work"},
                {"value":"b@y.com","type":"home"}]}"#,
        )
        .unwrap();

        assert!(
            parse_filter(r#"emails.value eq "b@y.com""#)
                .unwrap()
                .matches(&user)
        );
        assert!(
            parse_filter(r#"emails.type eq "work""#)
                .unwrap()
                .matches(&user)
        );
        assert!(
            !parse_filter(r#"emails.value eq "nope@z.com""#)
                .unwrap()
                .matches(&user)
        );
        assert!(parse_filter("emails.value pr").unwrap().matches(&user));
    }

    #[test]
    fn ne_against_an_absent_attribute_matches() {
        // An absent attribute is not equal to anything; reporting `false` for
        // `ne` made it read as EQUAL to every value.
        let user = JsonValue::parse(r#"{"userName":"bj"}"#).unwrap();
        assert!(parse_filter(r#"nickName ne "bob""#).unwrap().matches(&user));
        assert!(!parse_filter(r#"nickName eq "bob""#).unwrap().matches(&user));
        // A present, differing value still matches `ne`.
        assert!(
            parse_filter(r#"userName ne "other""#)
                .unwrap()
                .matches(&user)
        );
        assert!(!parse_filter(r#"userName ne "bj""#).unwrap().matches(&user));
    }
}