amql_selector/

matcher.rs

//! Match parsed selector ASTs against structured node data.

use crate::selector::{Combinator, CompoundSelector, SelectorAst};
use crate::types::{AttrName, TagName};
use rustc_hash::FxHashMap;
use serde_json::Value as JsonValue;

/// A matchable node — works for both annotations and code elements.
pub trait Matchable {
    /// The element's tag name (e.g. "function", "controller").
    fn tag(&self) -> &TagName;
    /// Key-value attributes on this node.
    fn attrs(&self) -> &FxHashMap<AttrName, JsonValue>;
    /// Parent node, if any, for combinator matching.
    fn parent(&self) -> Option<&dyn Matchable>;
}

/// Test if a single node matches a compound selector (tag + attributes).
pub fn matches_compound(node: &dyn Matchable, compound: &CompoundSelector) -> bool {
    if let Some(ref tag) = compound.tag {
        if *node.tag() != **tag {
            return false;
        }
    }

    for pred in &compound.attrs {
        if !matches_attr_predicate(node, pred) {
            return false;
        }
    }

    true
}

/// Filter an array of flat nodes by a selector AST.
/// Returns indices into the input slice for matched nodes.
#[must_use]
pub fn filter_by_selector(nodes: &[&dyn Matchable], selector: &SelectorAst) -> Vec<usize> {
    if selector.compounds.is_empty() {
        return vec![];
    }

    if selector.compounds.len() == 1 {
        return nodes
            .iter()
            .enumerate()
            .filter(|(_, n)| matches_compound(**n, &selector.compounds[0]))
            .map(|(i, _)| i)
            .collect();
    }

    // Multi-compound: the last compound is the target
    let target = &selector.compounds[selector.compounds.len() - 1];
    nodes
        .iter()
        .enumerate()
        .filter(|(_, node)| {
            if !matches_compound(**node, target) {
                return false;
            }
            verify_chain(
                **node,
                &selector.compounds,
                selector.compounds.len() as isize - 2,
            )
        })
        .map(|(i, _)| i)
        .collect()
}

/// Filter nodes using parent indices for combinator matching.
/// `parent_indices[i]` is the index of node i's parent in `nodes`, or `None`.
#[must_use]
pub fn filter_by_selector_indexed(
    nodes: &[&dyn Matchable],
    parent_indices: &[Option<usize>],
    selector: &SelectorAst,
) -> Vec<usize> {
    if selector.compounds.is_empty() {
        return vec![];
    }

    if selector.compounds.len() == 1 {
        return nodes
            .iter()
            .enumerate()
            .filter(|(_, n)| matches_compound(**n, &selector.compounds[0]))
            .map(|(i, _)| i)
            .collect();
    }

    let target = &selector.compounds[selector.compounds.len() - 1];
    nodes
        .iter()
        .enumerate()
        .filter(|(i, node)| {
            if !matches_compound(**node, target) {
                return false;
            }
            verify_chain_indexed(
                nodes,
                parent_indices,
                *i,
                &selector.compounds,
                selector.compounds.len() as isize - 2,
            )
        })
        .map(|(i, _)| i)
        .collect()
}

fn verify_chain_indexed(
    nodes: &[&dyn Matchable],
    parent_indices: &[Option<usize>],
    node_idx: usize,
    compounds: &[CompoundSelector],
    index: isize,
) -> bool {
    if index < 0 {
        return true;
    }
    let idx = index as usize;
    let compound = &compounds[idx];
    let combinator = compounds
        .get(idx + 1)
        .and_then(|c| c.combinator)
        .unwrap_or(Combinator::Descendant);

    match combinator {
        Combinator::Child => match parent_indices[node_idx] {
            Some(parent_idx) => {
                if !matches_compound(nodes[parent_idx], compound) {
                    return false;
                }
                verify_chain_indexed(nodes, parent_indices, parent_idx, compounds, index - 1)
            }
            None => false,
        },
        Combinator::Descendant => {
            let mut current = parent_indices[node_idx];
            let mut depth = 0;
            while let Some(ancestor_idx) = current {
                depth += 1;
                // Defensive: stop if depth exceeds node count (cycle in parent_indices)
                if depth > nodes.len() {
                    return false;
                }
                if matches_compound(nodes[ancestor_idx], compound)
                    && verify_chain_indexed(
                        nodes,
                        parent_indices,
                        ancestor_idx,
                        compounds,
                        index - 1,
                    )
                {
                    return true;
                }
                current = parent_indices[ancestor_idx];
            }
            false
        }
        Combinator::AdjacentSibling | Combinator::GeneralSibling => false,
    }
}

/// Maximum ancestor depth before bailing out (defensive against cyclic parent refs).
const MAX_ANCESTOR_DEPTH: usize = 1024;

fn verify_chain(node: &dyn Matchable, compounds: &[CompoundSelector], index: isize) -> bool {
    if index < 0 {
        return true;
    }
    let idx = index as usize;
    let compound = &compounds[idx];
    let combinator = compounds
        .get(idx + 1)
        .and_then(|c| c.combinator)
        .unwrap_or(Combinator::Descendant);

    match combinator {
        Combinator::Child => {
            // Direct parent must match
            match node.parent() {
                Some(parent) => {
                    if !matches_compound(parent, compound) {
                        return false;
                    }
                    verify_chain(parent, compounds, index - 1)
                }
                None => false,
            }
        }
        Combinator::Descendant => {
            // Any ancestor must match; backtrack if chain fails at a higher compound
            let mut ancestor = node.parent();
            let mut depth = 0;
            while let Some(anc) = ancestor {
                depth += 1;
                // Defensive: stop if depth exceeds limit (cycle in parent refs)
                if depth > MAX_ANCESTOR_DEPTH {
                    return false;
                }
                if matches_compound(anc, compound) && verify_chain(anc, compounds, index - 1) {
                    return true;
                }
                ancestor = anc.parent();
            }
            false
        }
        // Sibling combinators are rejected at parse time; this arm is defensive.
        Combinator::AdjacentSibling | Combinator::GeneralSibling => false,
    }
}

fn matches_attr_predicate(node: &dyn Matchable, pred: &amql_predicates::AttrPredicate) -> bool {
    let value = node.attrs().get(pred.name.as_str());

    // Bare attribute: [async] → just check existence and truthiness
    if pred.op.is_none() {
        return match value {
            None => false,
            Some(JsonValue::Null) => false,
            Some(JsonValue::Bool(false)) => false,
            Some(_) => true,
        };
    }

    // With operator: delegate to amql-predicates
    let node_str = value.map(crate::json_value_to_string).unwrap_or_default();

    match &pred.value {
        Some(pv) => amql_predicates::eval_op_typed(pred.op.unwrap(), &node_str, pv),
        None => amql_predicates::eval_op(pred.op.unwrap(), &node_str, ""),
    }
}

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

    /// Simple test node implementation.
    struct TestNode {
        tag: TagName,
        attrs: FxHashMap<AttrName, JsonValue>,
        parent: Option<Box<TestNode>>,
    }

    impl TestNode {
        fn new(tag: &str, attrs: FxHashMap<AttrName, JsonValue>) -> Self {
            Self {
                tag: TagName::from(tag),
                attrs,
                parent: None,
            }
        }

        fn with_parent(mut self, parent: TestNode) -> Self {
            self.parent = Some(Box::new(parent));
            self
        }
    }

    impl Matchable for TestNode {
        fn tag(&self) -> &TagName {
            &self.tag
        }
        fn attrs(&self) -> &FxHashMap<AttrName, JsonValue> {
            &self.attrs
        }
        fn parent(&self) -> Option<&dyn Matchable> {
            self.parent.as_ref().map(|p| p.as_ref() as &dyn Matchable)
        }
    }

    fn attrs(pairs: &[(&str, JsonValue)]) -> FxHashMap<AttrName, JsonValue> {
        pairs
            .iter()
            .map(|(k, v)| (AttrName::from(*k), v.clone()))
            .collect()
    }

    #[test]
    fn matches_and_rejects_by_tag() {
        // Arrange
        let matching = TestNode::new("controller", FxHashMap::default());
        let wrong = TestNode::new("function", FxHashMap::default());
        let selector = parse_selector("controller").unwrap();
        let compound = &selector.compounds[0];

        // Act
        let hit = matches_compound(&matching, compound);
        let miss = matches_compound(&wrong, compound);

        // Assert
        assert!(hit, "node with correct tag should match");
        assert!(!miss, "node with wrong tag should not match");
    }

    #[test]
    fn matches_and_rejects_attributes() {
        // Arrange
        let present = TestNode::new("function", attrs(&[("async", JsonValue::Bool(true))]));
        let absent = TestNode::new("function", FxHashMap::default());
        let post = TestNode::new(
            "controller",
            attrs(&[("method", JsonValue::String("POST".to_string()))]),
        );
        let get = TestNode::new(
            "controller",
            attrs(&[("method", JsonValue::String("GET".to_string()))]),
        );
        let handle = TestNode::new(
            "function",
            attrs(&[("name", JsonValue::String("handleClick".to_string()))]),
        );
        let create = TestNode::new(
            "function",
            attrs(&[("name", JsonValue::String("createUser".to_string()))]),
        );

        let sel_presence = parse_selector("function[async]").unwrap();
        let sel_value = parse_selector(r#"controller[method="POST"]"#).unwrap();
        let sel_starts = parse_selector(r#"[name^="handle"]"#).unwrap();
        let sel_contains = parse_selector(r#"[name*="User"]"#).unwrap();

        // Act
        let presence_hit = matches_compound(&present, &sel_presence.compounds[0]);
        let presence_miss = matches_compound(&absent, &sel_presence.compounds[0]);
        let value_hit = matches_compound(&post, &sel_value.compounds[0]);
        let value_miss = matches_compound(&get, &sel_value.compounds[0]);
        let starts_hit = matches_compound(&handle, &sel_starts.compounds[0]);
        let contains_hit = matches_compound(&create, &sel_contains.compounds[0]);

        // Assert
        assert!(presence_hit, "attribute present should match");
        assert!(!presence_miss, "missing attribute should not match");
        assert!(value_hit, "exact attribute value should match");
        assert!(!value_miss, "wrong attribute value should not match");
        assert!(starts_hit, "starts-with operator should match");
        assert!(contains_hit, "contains operator should match");
    }

    #[test]
    fn filters_by_selector() {
        // Arrange
        let n1 = TestNode::new(
            "controller",
            attrs(&[("method", JsonValue::String("POST".to_string()))]),
        );
        let n2 = TestNode::new("react-hook", FxHashMap::default());
        let n3 = TestNode::new(
            "controller",
            attrs(&[("method", JsonValue::String("GET".to_string()))]),
        );
        let n4 = TestNode::new(
            "controller",
            attrs(&[("owner", JsonValue::String("@backend".to_string()))]),
        );
        let n5 = TestNode::new(
            "react-hook",
            attrs(&[("owner", JsonValue::String("@frontend".to_string()))]),
        );
        let n6 = TestNode::new("function", FxHashMap::default());

        let parent = TestNode::new(
            "class",
            attrs(&[("name", JsonValue::String("UserService".to_string()))]),
        );
        let child =
            TestNode::new("method", attrs(&[("async", JsonValue::Bool(true))])).with_parent(parent);
        let orphan = TestNode::new("method", attrs(&[("async", JsonValue::Bool(true))]));

        let sel_tag = parse_selector("controller").unwrap();
        let sel_tag_attr = parse_selector(r#"controller[method="POST"]"#).unwrap();
        let sel_attr_only = parse_selector(r#"[owner="@backend"]"#).unwrap();
        let sel_child = parse_selector("class > method[async]").unwrap();

        // Act
        let by_tag: Vec<&dyn Matchable> = vec![&n1, &n2, &n3];
        let tag_indices = filter_by_selector(&by_tag, &sel_tag);

        let by_tag_attr: Vec<&dyn Matchable> = vec![&n1, &n3];
        let tag_attr_indices = filter_by_selector(&by_tag_attr, &sel_tag_attr);

        let by_attr: Vec<&dyn Matchable> = vec![&n4, &n5, &n6];
        let attr_indices = filter_by_selector(&by_attr, &sel_attr_only);

        let by_child: Vec<&dyn Matchable> = vec![&child, &orphan];
        let child_indices = filter_by_selector(&by_child, &sel_child);

        // Assert
        assert_eq!(tag_indices, vec![0, 2], "should filter by tag");
        assert_eq!(
            tag_attr_indices,
            vec![0],
            "should filter by tag + attribute"
        );
        assert_eq!(
            attr_indices,
            vec![0],
            "should filter by attribute-only selector"
        );
        assert_eq!(
            child_indices,
            vec![0],
            "child combinator should match only parented node"
        );
    }

    #[test]
    fn descendant_backtracks_past_first_match() {
        // Arrange: outer[name="a"] > inner > inner > method
        // Selector: outer[name="a"] inner method
        // The first `inner` ancestor of `method` matches `inner`,
        // but its parent is also `inner` (not `outer`).
        // The matcher must backtrack to the second `inner` whose parent IS `outer`.
        let outer = TestNode::new("outer", attrs(&[("name", JsonValue::String("a".into()))]));
        let mid = TestNode::new("inner", FxHashMap::default()).with_parent(outer);
        let inner = TestNode::new("inner", FxHashMap::default()).with_parent(mid);
        let leaf = TestNode::new("method", FxHashMap::default()).with_parent(inner);

        let sel = parse_selector(r#"outer[name="a"] inner method"#).unwrap();

        // Act
        let nodes: Vec<&dyn Matchable> = vec![&leaf];
        let result = filter_by_selector(&nodes, &sel);

        // Assert
        assert_eq!(
            result,
            vec![0],
            "descendant matcher should backtrack past first matching ancestor"
        );
    }

    #[test]
    fn descendant_backtracks_indexed() {
        // Arrange: same tree as above but using filter_by_selector_indexed
        // outer[name="a"] > inner(0) > inner(1) > method(2)
        // Nodes indexed: 0=outer, 1=mid_inner, 2=inner, 3=method
        let outer = TestNode::new("outer", attrs(&[("name", JsonValue::String("a".into()))]));
        let mid = TestNode::new("inner", FxHashMap::default());
        let inner = TestNode::new("inner", FxHashMap::default());
        let leaf = TestNode::new("method", FxHashMap::default());

        let nodes: Vec<&dyn Matchable> = vec![&outer, &mid, &inner, &leaf];
        let parent_indices: Vec<Option<usize>> = vec![None, Some(0), Some(1), Some(2)];

        let sel = parse_selector(r#"outer[name="a"] inner method"#).unwrap();

        // Act
        let result = filter_by_selector_indexed(&nodes, &parent_indices, &sel);

        // Assert
        assert_eq!(
            result,
            vec![3],
            "indexed descendant matcher should backtrack past first matching ancestor"
        );
    }
}