thread_ast_engine/match_tree/strictness.rs
1// SPDX-FileCopyrightText: 2022 Herrington Darkholme <2883231+HerringtonDarkholme@users.noreply.github.com>
2// SPDX-FileCopyrightText: 2025 Knitli Inc. <knitli@knit.li>
3// SPDX-FileContributor: Adam Poulemanos <adam@knit.li>
4//
5// SPDX-License-Identifier: AGPL-3.0-or-later AND MIT
6
7//! # Pattern Matching Strictness Implementation
8//!
9//! Implements the logic for different levels of pattern matching strictness,
10//! controlling how precisely patterns must match AST structure.
11//!
12//! ## Strictness Levels
13//!
14//! - **CST (Concrete Syntax Tree)** - Exact matching including all punctuation
15//! - **Smart** - Ignores unnamed tokens but matches all named nodes
16//! - **AST (Abstract Syntax Tree)** - Matches only named/structural nodes
17//! - **Relaxed** - AST matching while ignoring comments
18//! - **Signature** - Matches structure only, ignoring text content
19//!
20//! ## Core Types
21//!
22//! - [`MatchOneNode`] - Result of comparing a single pattern node to a candidate
23//! - [`MatchStrictness`] - Enum defining strictness levels (re-exported)
24//!
25//! ## Usage
26//!
27//! This module is primarily used internally by the pattern matching engine.
28//! Users typically interact with strictness through pattern configuration:
29//!
30//! ```rust,ignore
31//! let pattern = Pattern::new("function $NAME() {}", language)
32//! .with_strictness(MatchStrictness::Relaxed);
33//! ```
34//!
35//! The strictness level determines:
36//! - Which nodes in the AST are considered for matching
37//! - Whether whitespace and punctuation must match exactly
38//! - How comments are handled during matching
39//! - Whether text content is compared or just structure
40
41use crate::Doc;
42pub use crate::matcher::MatchStrictness;
43use crate::matcher::{PatternNode, kind_utils};
44use crate::meta_var::MetaVariable;
45use crate::node::Node;
46use std::iter::Peekable;
47use std::str::FromStr;
48
49/// Result of comparing a single pattern node against a candidate AST node.
50///
51/// Represents the different outcomes when the matching algorithm compares
52/// one element of a pattern against one AST node, taking into account
53/// the current strictness level.
54#[derive(Debug, Clone)]
55pub enum MatchOneNode {
56 /// Both pattern and candidate node match - continue with next elements
57 MatchedBoth,
58 /// Skip both pattern and candidate (e.g., both are unnamed tokens in AST mode)
59 SkipBoth,
60 /// Skip the pattern element (e.g., unnamed token in pattern during AST matching)
61 SkipGoal,
62 /// Skip the candidate node (e.g., unnamed token in candidate during AST matching)
63 SkipCandidate,
64 /// No match possible - pattern fails
65 NoMatch,
66}
67
68fn skip_comment_or_unnamed(n: &Node<impl Doc>) -> bool {
69 if !n.is_named() {
70 return true;
71 }
72 let kind = n.kind();
73 kind.contains("comment")
74}
75
76impl MatchStrictness {
77 pub(crate) fn match_terminal(
78 self,
79 is_named: bool,
80 text: &str,
81 goal_kind: u16,
82 candidate: &Node<impl Doc>,
83 ) -> MatchOneNode {
84 let cand_kind = candidate.kind_id();
85 let is_kind_matched = kind_utils::are_kinds_matching(goal_kind, cand_kind);
86 // work around ast-grep/ast-grep#1419 and tree-sitter/tree-sitter-typescript#306
87 // tree-sitter-typescript has wrong span of unnamed node so text would not match
88 // just compare kind for unnamed node
89 if is_kind_matched && (!is_named || text == candidate.text()) {
90 return MatchOneNode::MatchedBoth;
91 }
92 let (skip_goal, skip_candidate) = match self {
93 Self::Cst => (false, false),
94 Self::Smart => (false, !candidate.is_named()),
95 Self::Ast => (!is_named, !candidate.is_named()),
96 Self::Relaxed => (!is_named, skip_comment_or_unnamed(candidate)),
97 Self::Signature => {
98 if is_kind_matched {
99 return MatchOneNode::MatchedBoth;
100 }
101 (!is_named, skip_comment_or_unnamed(candidate))
102 }
103 };
104 match (skip_goal, skip_candidate) {
105 (true, true) => MatchOneNode::SkipBoth,
106 (true, false) => MatchOneNode::SkipGoal,
107 (false, true) => MatchOneNode::SkipCandidate,
108 (false, false) => MatchOneNode::NoMatch,
109 }
110 }
111
112 // TODO: this is a method for working around trailing nodes after pattern is matched
113 pub(crate) fn should_skip_trailing<D: Doc>(self, candidate: &Node<D>) -> bool {
114 match self {
115 Self::Cst | Self::Ast => false,
116 Self::Smart => true,
117 Self::Relaxed | Self::Signature => skip_comment_or_unnamed(candidate),
118 }
119 }
120
121 pub(crate) fn should_skip_goal<'p>(
122 self,
123 goal_children: &mut Peekable<impl Iterator<Item = &'p PatternNode>>,
124 ) -> bool {
125 while let Some(pattern) = goal_children.peek() {
126 let skipped = match self {
127 Self::Cst => false,
128 Self::Smart => match pattern {
129 PatternNode::MetaVar { meta_var } => match meta_var {
130 MetaVariable::Multiple | MetaVariable::MultiCapture(_) => true,
131 MetaVariable::Dropped(_) | MetaVariable::Capture(..) => false,
132 },
133 PatternNode::Terminal { .. } | PatternNode::Internal { .. } => false,
134 },
135 Self::Ast | Self::Relaxed | Self::Signature => match pattern {
136 PatternNode::MetaVar { meta_var } => match meta_var {
137 MetaVariable::Multiple | MetaVariable::MultiCapture(_) => true,
138 MetaVariable::Dropped(named) | MetaVariable::Capture(_, named) => !named,
139 },
140 PatternNode::Terminal { is_named, .. } => !is_named,
141 PatternNode::Internal { .. } => false,
142 },
143 };
144 if !skipped {
145 return false;
146 }
147 goal_children.next();
148 }
149 true
150 }
151}
152
153impl FromStr for MatchStrictness {
154 type Err = &'static str;
155 fn from_str(s: &str) -> Result<Self, Self::Err> {
156 match s {
157 "cst" => Ok(Self::Cst),
158 "smart" => Ok(Self::Smart),
159 "ast" => Ok(Self::Ast),
160 "relaxed" => Ok(Self::Relaxed),
161 "signature" => Ok(Self::Signature),
162 _ => Err("invalid strictness, valid options are: cst, smart, ast, relaxed, signature"),
163 }
164 }
165}