plotnik_lib/query/
mod.rs

1//! Query processing pipeline.
2//!
3//! Stages: parse → alt_kinds → symbol_table → recursion → shapes → [qis → build_graph].
4//! Each stage populates its own diagnostics. Use `is_valid()` to check
5//! if any stage produced errors.
6//!
7//! The `build_graph` stage is optional and constructs the transition graph
8//! for compilation to binary IR. QIS detection runs as part of this stage.
9
10mod dump;
11mod graph_qis;
12mod invariants;
13mod printer;
14pub use printer::QueryPrinter;
15
16pub mod alt_kinds;
17pub mod graph;
18mod graph_build;
19mod graph_dump;
20mod graph_optimize;
21pub mod infer;
22mod infer_dump;
23#[cfg(feature = "plotnik-langs")]
24pub mod link;
25pub mod recursion;
26pub mod shapes;
27pub mod symbol_table;
28
29pub use graph::{BuildEffect, BuildGraph, BuildMatcher, BuildNode, Fragment, NodeId, RefMarker};
30pub use graph_optimize::OptimizeStats;
31pub use infer::{
32    InferredMember, InferredTypeDef, TypeDescription, TypeInferenceResult, UnificationError,
33};
34pub use symbol_table::UNNAMED_DEF;
35
36#[cfg(test)]
37mod alt_kinds_tests;
38#[cfg(test)]
39mod graph_build_tests;
40#[cfg(test)]
41mod graph_master_test;
42#[cfg(test)]
43mod graph_qis_tests;
44#[cfg(test)]
45mod infer_tests;
46#[cfg(all(test, feature = "plotnik-langs"))]
47mod link_tests;
48#[cfg(test)]
49mod mod_tests;
50#[cfg(test)]
51mod printer_tests;
52#[cfg(test)]
53mod recursion_tests;
54#[cfg(test)]
55mod shapes_tests;
56#[cfg(test)]
57mod symbol_table_tests;
58
59use std::collections::{HashMap, HashSet};
60
61#[cfg(feature = "plotnik-langs")]
62use plotnik_langs::{NodeFieldId, NodeTypeId};
63
64use rowan::GreenNodeBuilder;
65
66use crate::Result;
67use crate::diagnostics::Diagnostics;
68use crate::parser::cst::SyntaxKind;
69use crate::parser::lexer::lex;
70use crate::parser::{ParseResult, Parser, Root, SyntaxNode, ast};
71
72const DEFAULT_EXEC_FUEL: u32 = 1_000_000;
73const DEFAULT_RECURSION_FUEL: u32 = 4096;
74
75use shapes::ShapeCardinality;
76use symbol_table::SymbolTable;
77
78/// A parsed and analyzed query.
79///
80/// Create with [`new`](Self::new), optionally configure fuel limits,
81/// then call [`exec`](Self::exec) to run analysis.
82///
83/// For compilation, call [`build_graph`](Self::build_graph) after `exec`.
84///
85/// Check [`is_valid`](Self::is_valid) or [`diagnostics`](Self::diagnostics)
86/// to determine if the query has syntax/semantic issues.
87/// Quantifier-Induced Scope trigger info.
88///
89/// When a quantified expression has ≥2 propagating captures, QIS creates
90/// an implicit object scope so captures stay coupled per-iteration.
91#[derive(Debug, Clone)]
92pub struct QisTrigger<'a> {
93    /// Capture names that propagate from this quantified expression.
94    pub captures: Vec<&'a str>,
95}
96
97#[derive(Debug)]
98pub struct Query<'a> {
99    source: &'a str,
100    ast: Root,
101    symbol_table: SymbolTable<'a>,
102    shape_cardinality_table: HashMap<ast::Expr, ShapeCardinality>,
103    #[cfg(feature = "plotnik-langs")]
104    node_type_ids: HashMap<&'a str, Option<NodeTypeId>>,
105    #[cfg(feature = "plotnik-langs")]
106    node_field_ids: HashMap<&'a str, Option<NodeFieldId>>,
107    exec_fuel: Option<u32>,
108    recursion_fuel: Option<u32>,
109    exec_fuel_consumed: u32,
110    parse_diagnostics: Diagnostics,
111    alt_kind_diagnostics: Diagnostics,
112    resolve_diagnostics: Diagnostics,
113    recursion_diagnostics: Diagnostics,
114    shapes_diagnostics: Diagnostics,
115    #[cfg(feature = "plotnik-langs")]
116    link_diagnostics: Diagnostics,
117    // Graph compilation fields
118    graph: BuildGraph<'a>,
119    dead_nodes: HashSet<NodeId>,
120    type_info: TypeInferenceResult<'a>,
121    /// QIS triggers: quantified expressions with ≥2 propagating captures.
122    qis_triggers: HashMap<ast::QuantifiedExpr, QisTrigger<'a>>,
123    /// Definitions with exactly 1 propagating capture: def name → capture name.
124    single_capture_defs: HashMap<&'a str, &'a str>,
125    /// Definitions with 2+ propagating captures (need struct wrapping at root).
126    multi_capture_defs: HashSet<&'a str>,
127    /// Current definition name during graph construction.
128    current_def_name: &'a str,
129    /// Counter for generating unique ref IDs during graph construction.
130    next_ref_id: u32,
131}
132
133fn empty_root() -> Root {
134    let mut builder = GreenNodeBuilder::new();
135    builder.start_node(SyntaxKind::Root.into());
136    builder.finish_node();
137    let green = builder.finish();
138    Root::cast(SyntaxNode::new_root(green)).expect("we just built a Root node")
139}
140
141impl<'a> Query<'a> {
142    /// Create a new query from source text.
143    ///
144    /// Call [`exec`](Self::exec) to run analysis passes.
145    pub fn new(source: &'a str) -> Self {
146        Self {
147            source,
148            ast: empty_root(),
149            symbol_table: SymbolTable::default(),
150            shape_cardinality_table: HashMap::new(),
151            #[cfg(feature = "plotnik-langs")]
152            node_type_ids: HashMap::new(),
153            #[cfg(feature = "plotnik-langs")]
154            node_field_ids: HashMap::new(),
155            exec_fuel: Some(DEFAULT_EXEC_FUEL),
156            recursion_fuel: Some(DEFAULT_RECURSION_FUEL),
157            exec_fuel_consumed: 0,
158            parse_diagnostics: Diagnostics::new(),
159            alt_kind_diagnostics: Diagnostics::new(),
160            resolve_diagnostics: Diagnostics::new(),
161            recursion_diagnostics: Diagnostics::new(),
162            shapes_diagnostics: Diagnostics::new(),
163            #[cfg(feature = "plotnik-langs")]
164            link_diagnostics: Diagnostics::new(),
165            graph: BuildGraph::default(),
166            dead_nodes: HashSet::new(),
167            type_info: TypeInferenceResult::default(),
168            qis_triggers: HashMap::new(),
169            single_capture_defs: HashMap::new(),
170            multi_capture_defs: HashSet::new(),
171            current_def_name: "",
172            next_ref_id: 0,
173        }
174    }
175
176    /// Set execution fuel limit. None = infinite.
177    ///
178    /// Execution fuel never replenishes. It protects against large inputs.
179    /// Returns error from [`exec`](Self::exec) when exhausted.
180    pub fn with_exec_fuel(mut self, limit: Option<u32>) -> Self {
181        self.exec_fuel = limit;
182        self
183    }
184
185    /// Set recursion depth limit. None = infinite.
186    ///
187    /// Recursion fuel restores when exiting recursion. It protects against
188    /// deeply nested input. Returns error from [`exec`](Self::exec) when exhausted.
189    pub fn with_recursion_fuel(mut self, limit: Option<u32>) -> Self {
190        self.recursion_fuel = limit;
191        self
192    }
193
194    /// Run all analysis passes.
195    ///
196    /// Returns `Err` if fuel limits are exceeded.
197    /// Syntax/semantic diagnostics are collected and accessible via [`diagnostics`](Self::diagnostics).
198    pub fn exec(mut self) -> Result<Self> {
199        self.try_parse()?;
200        self.validate_alt_kinds();
201        self.resolve_names();
202        self.validate_recursion();
203        self.infer_shapes();
204        Ok(self)
205    }
206
207    /// Build the transition graph for compilation.
208    ///
209    /// This is an optional step after `exec`. It detects QIS triggers,
210    /// constructs the graph, runs epsilon elimination, and infers types.
211    ///
212    /// Only runs if the query is valid (no errors from previous passes).
213    pub fn build_graph(mut self) -> Self {
214        if !self.is_valid() {
215            return self;
216        }
217        self.detect_capture_scopes();
218        self.construct_graph();
219        self.infer_types(); // Run before optimization to avoid merged effects
220        self.optimize_graph();
221        self
222    }
223
224    /// Build graph and return dump of graph before optimization (for debugging).
225    ///
226    /// If `root_kind` is provided, definitions are wrapped before dumping.
227    pub fn build_graph_with_pre_opt_dump(mut self, root_kind: Option<&'a str>) -> (Self, String) {
228        if !self.is_valid() {
229            return (self, String::new());
230        }
231        self.detect_capture_scopes();
232        self.construct_graph();
233        if let Some(root) = root_kind {
234            self.graph.wrap_definitions_with_root(root);
235        }
236        let pre_opt_dump = self.graph.dump();
237        self.infer_types();
238        self.optimize_graph();
239        (self, pre_opt_dump)
240    }
241
242    fn try_parse(&mut self) -> Result<()> {
243        let tokens = lex(self.source);
244        let parser = Parser::new(self.source, tokens)
245            .with_exec_fuel(self.exec_fuel)
246            .with_recursion_fuel(self.recursion_fuel);
247
248        let ParseResult {
249            root,
250            diagnostics,
251            exec_fuel_consumed,
252        } = parser.parse()?;
253        self.ast = root;
254        self.parse_diagnostics = diagnostics;
255        self.exec_fuel_consumed = exec_fuel_consumed;
256        Ok(())
257    }
258
259    pub(crate) fn as_cst(&self) -> &SyntaxNode {
260        self.ast.as_cst()
261    }
262
263    pub(crate) fn root(&self) -> &Root {
264        &self.ast
265    }
266
267    /// Access the constructed graph.
268    pub fn graph(&self) -> &BuildGraph<'a> {
269        &self.graph
270    }
271
272    /// Wrap definitions that don't already match the root node kind.
273    ///
274    /// Call this after `build_graph()` to allow queries like `(function_declaration)`
275    /// to work when the interpreter starts at tree root (e.g., `program`).
276    ///
277    /// The `root_kind` should be the language's root node kind (e.g., "program" for JS).
278    pub fn wrap_with_root(mut self, root_kind: &'a str) -> Self {
279        self.graph.wrap_definitions_with_root(root_kind);
280        // Re-run type inference and optimization on wrapped graph
281        self.infer_types();
282        self.optimize_graph();
283        self
284    }
285
286    /// Access the set of dead nodes (eliminated by optimization).
287    pub fn dead_nodes(&self) -> &HashSet<NodeId> {
288        &self.dead_nodes
289    }
290
291    /// Access the type inference result.
292    pub fn type_info(&self) -> &TypeInferenceResult<'a> {
293        &self.type_info
294    }
295
296    pub(crate) fn shape_cardinality(&self, node: &SyntaxNode) -> ShapeCardinality {
297        // Error nodes are invalid
298        if node.kind() == SyntaxKind::Error {
299            return ShapeCardinality::Invalid;
300        }
301
302        // Root: cardinality based on definition count
303        if let Some(root) = Root::cast(node.clone()) {
304            return if root.defs().count() > 1 {
305                ShapeCardinality::Many
306            } else {
307                ShapeCardinality::One
308            };
309        }
310
311        // Def: delegate to body's cardinality
312        if let Some(def) = ast::Def::cast(node.clone()) {
313            return def
314                .body()
315                .and_then(|b| self.shape_cardinality_table.get(&b).copied())
316                .unwrap_or(ShapeCardinality::Invalid);
317        }
318
319        // Branch: delegate to body's cardinality
320        if let Some(branch) = ast::Branch::cast(node.clone()) {
321            return branch
322                .body()
323                .and_then(|b| self.shape_cardinality_table.get(&b).copied())
324                .unwrap_or(ShapeCardinality::Invalid);
325        }
326
327        // Expr: direct lookup
328        ast::Expr::cast(node.clone())
329            .and_then(|e| self.shape_cardinality_table.get(&e).copied())
330            .unwrap_or(ShapeCardinality::One)
331    }
332
333    /// All diagnostics combined from all passes (unfiltered).
334    ///
335    /// Use this for debugging or when you need to see all diagnostics
336    /// including cascading errors.
337    pub fn diagnostics_raw(&self) -> Diagnostics {
338        let mut all = Diagnostics::new();
339        all.extend(self.parse_diagnostics.clone());
340        all.extend(self.alt_kind_diagnostics.clone());
341        all.extend(self.resolve_diagnostics.clone());
342        all.extend(self.recursion_diagnostics.clone());
343        all.extend(self.shapes_diagnostics.clone());
344        #[cfg(feature = "plotnik-langs")]
345        all.extend(self.link_diagnostics.clone());
346        all.extend(self.type_info.diagnostics.clone());
347        all
348    }
349
350    /// All diagnostics combined from all passes.
351    ///
352    /// Returns diagnostics with cascading errors suppressed.
353    /// For raw access, use [`diagnostics_raw`](Self::diagnostics_raw).
354    pub fn diagnostics(&self) -> Diagnostics {
355        self.diagnostics_raw()
356    }
357
358    /// Query is valid if there are no error-severity diagnostics (warnings are allowed).
359    #[cfg(feature = "plotnik-langs")]
360    pub fn is_valid(&self) -> bool {
361        !self.parse_diagnostics.has_errors()
362            && !self.alt_kind_diagnostics.has_errors()
363            && !self.resolve_diagnostics.has_errors()
364            && !self.recursion_diagnostics.has_errors()
365            && !self.shapes_diagnostics.has_errors()
366            && !self.link_diagnostics.has_errors()
367    }
368
369    /// Query is valid if there are no error-severity diagnostics (warnings are allowed).
370    #[cfg(not(feature = "plotnik-langs"))]
371    pub fn is_valid(&self) -> bool {
372        !self.parse_diagnostics.has_errors()
373            && !self.alt_kind_diagnostics.has_errors()
374            && !self.resolve_diagnostics.has_errors()
375            && !self.recursion_diagnostics.has_errors()
376            && !self.shapes_diagnostics.has_errors()
377    }
378
379    /// Check if graph compilation produced type errors.
380    pub fn has_type_errors(&self) -> bool {
381        self.type_info.has_errors()
382    }
383}
384
385impl<'a> TryFrom<&'a str> for Query<'a> {
386    type Error = crate::Error;
387
388    fn try_from(source: &'a str) -> Result<Self> {
389        Self::new(source).exec()
390    }
391}
392
393impl<'a> TryFrom<&'a String> for Query<'a> {
394    type Error = crate::Error;
395
396    fn try_from(source: &'a String) -> Result<Self> {
397        Self::new(source.as_str()).exec()
398    }
399}
plotnik_lib/query/mod.rs

plotnik_lib/query/
mod.rs
