molframe_query/execution/
plan.rs

1//! Storage-independent logical plans and structure-bound physical plans.
2
3use crate::ast::{Column, Expr};
4use crate::glob::Glob;
5use molframe_core::contract::AnalysisPolicy;
6use molframe_core::diagnostic::{Code, Diagnostic};
7use molframe_core::structure::Structure;
8use molframe_core::symbol::SymbolId;
9use std::collections::BTreeSet;
10
11/// An immutable storage-independent selection plan.
12#[derive(Clone, Debug, PartialEq)]
13pub struct LogicalPlan(pub(crate) Expr);
14
15/// A selection plan bound to one structure dictionary and policy.
16///
17/// Glob patterns have become stable symbol sets and constant branches have
18/// been removed. Reuse this value for repeated frames sharing the topology.
19#[derive(Clone, Debug)]
20pub struct PhysicalQuery {
21    pub(crate) expr: PhysicalExpr,
22    pub(crate) warnings: Vec<Diagnostic>,
23}
24
25#[derive(Clone, Debug)]
26pub(crate) enum PhysicalExpr {
27    All,
28    None,
29    And(Box<Self>, Box<Self>),
30    Or(Box<Self>, Box<Self>),
31    Not(Box<Self>),
32    ResolvedMembership {
33        column: Column,
34        symbols: BTreeSet<SymbolId>,
35    },
36    Logical(Expr),
37}
38
39/// Binds an expression directly without first cloning it into `LogicalPlan`.
40///
41/// This path allows `Query::plan` to eliminate one complete AST clone while
42/// retaining exactly the same physical-plan representation.
43pub(crate) fn bind_expr(
44    expr: &Expr,
45    structure: &Structure,
46    policy: &AnalysisPolicy,
47    mut warnings: Vec<Diagnostic>,
48) -> PhysicalQuery {
49    let expr = lower(expr, structure, policy, &mut warnings);
50
51    warnings.sort_by_key(Diagnostic::code);
52
53    PhysicalQuery { expr, warnings }
54}
55
56/// Lowers one logical expression into a structure-bound physical expression.
57///
58/// Constant branches are folded and supported symbol memberships are resolved
59/// against the structure dictionary exactly once.
60fn lower(
61    expr: &Expr,
62    structure: &Structure,
63    policy: &AnalysisPolicy,
64    warnings: &mut Vec<Diagnostic>,
65) -> PhysicalExpr {
66    match expr {
67        Expr::All => PhysicalExpr::All,
68        Expr::None => PhysicalExpr::None,
69        Expr::And(left, right) => conjunction(
70            lower(left, structure, policy, warnings),
71            lower(right, structure, policy, warnings),
72        ),
73        Expr::Or(left, right) => disjunction(
74            lower(left, structure, policy, warnings),
75            lower(right, structure, policy, warnings),
76        ),
77        Expr::Not(target) => match lower(target, structure, policy, warnings) {
78            PhysicalExpr::All => PhysicalExpr::None,
79            PhysicalExpr::None => PhysicalExpr::All,
80            target => PhysicalExpr::Not(Box::new(target)),
81        },
82        Expr::Membership { column, values }
83            if symbol_column(*column, policy)
84                && !(matches!(column, Column::AlternateLocation)
85                    && values
86                        .iter()
87                        .any(|value| value.eq_ignore_ascii_case("none"))) =>
88        {
89            let column = crate::predicate::resolved_column(*column, policy);
90            let symbols = resolve_symbols(structure, values);
91
92            if symbols.is_empty() {
93                warnings.push(Diagnostic::new(Code::W4003));
94                PhysicalExpr::None
95            } else {
96                PhysicalExpr::ResolvedMembership { column, symbols }
97            }
98        }
99        other => PhysicalExpr::Logical(other.clone()),
100    }
101}
102
103/// Folds and cost-orders one binary conjunction.
104///
105/// The right operand is evaluated inside the left operand's result, so operands
106/// are exchanged only when the right-hand side has strictly lower estimated
107/// cost *and* both read nothing but the atom they test. Exchanging an operand
108/// that reads its surroundings (`within`, `byres`, `bonded`, ...) would change
109/// what it sees and therefore the answer: `within 4 of X and not X` selects the
110/// shell around `X`, while its mirror would test `X` against a universe that
111/// already excludes it.
112fn conjunction(left: PhysicalExpr, right: PhysicalExpr) -> PhysicalExpr {
113    match (left, right) {
114        (PhysicalExpr::None, _) | (_, PhysicalExpr::None) => PhysicalExpr::None,
115        (PhysicalExpr::All, right) => right,
116        (left, PhysicalExpr::All) => left,
117        (left, right) if cost(&right) < cost(&left) && atom_local(&left) && atom_local(&right) => {
118            PhysicalExpr::And(Box::new(right), Box::new(left))
119        }
120        (left, right) => PhysicalExpr::And(Box::new(left), Box::new(right)),
121    }
122}
123
124/// Constant-folds one binary disjunction.
125fn disjunction(left: PhysicalExpr, right: PhysicalExpr) -> PhysicalExpr {
126    match (left, right) {
127        (PhysicalExpr::All, _) | (_, PhysicalExpr::All) => PhysicalExpr::All,
128        (PhysicalExpr::None, right) => right,
129        (left, PhysicalExpr::None) => left,
130        (left, right) => PhysicalExpr::Or(Box::new(left), Box::new(right)),
131    }
132}
133
134/// Whether the expression's answer for one atom is independent of the universe
135/// it is evaluated in, so its position in a conjunction cannot change results.
136fn atom_local(expr: &PhysicalExpr) -> bool {
137    match expr {
138        PhysicalExpr::All | PhysicalExpr::None | PhysicalExpr::ResolvedMembership { .. } => true,
139        PhysicalExpr::And(left, right) | PhysicalExpr::Or(left, right) => {
140            atom_local(left) && atom_local(right)
141        }
142        PhysicalExpr::Not(target) => atom_local(target),
143        PhysicalExpr::Logical(logical) => logical_atom_local(logical),
144    }
145}
146
147fn logical_atom_local(expr: &Expr) -> bool {
148    match expr {
149        Expr::All
150        | Expr::None
151        | Expr::Comparison { .. }
152        | Expr::Membership { .. }
153        | Expr::Group(_)
154        | Expr::Atom { .. } => true,
155        Expr::And(left, right) | Expr::Or(left, right) => {
156            logical_atom_local(left) && logical_atom_local(right)
157        }
158        Expr::Not(target) => logical_atom_local(target),
159        _ => false,
160    }
161}
162
163/// Returns a small relative execution-cost class for plan ordering.
164///
165/// Runtime and space are `O(1)`.
166#[inline]
167fn cost(expr: &PhysicalExpr) -> u8 {
168    match expr {
169        PhysicalExpr::None | PhysicalExpr::All => 0,
170        PhysicalExpr::ResolvedMembership { .. } => 1,
171        PhysicalExpr::And(_, _) | PhysicalExpr::Or(_, _) | PhysicalExpr::Not(_) => 2,
172        PhysicalExpr::Logical(Expr::Geometric(_)) => 5,
173        PhysicalExpr::Logical(_) => 3,
174    }
175}
176
177/// Returns whether `column` can be lowered to dictionary symbol membership.
178///
179/// Explicit identifier-policy restrictions are preserved. Elements are not
180/// text: a file may write iron as `FE` and a query as `Fe`, so they are
181/// compared as elements rather than through the symbol dictionary.
182fn symbol_column(column: Column, policy: &AnalysisPolicy) -> bool {
183    if policy.identifiers == molframe_core::contract::Namespace::Explicit
184        && matches!(
185            column,
186            Column::Chain | Column::ResidueName | Column::AtomName
187        )
188    {
189        return false;
190    }
191
192    matches!(
193        crate::predicate::resolved_column(column, policy),
194        Column::LabelChain
195            | Column::AuthChain
196            | Column::LabelResidueName
197            | Column::AuthResidueName
198            | Column::LabelAtomName
199            | Column::AuthAtomName
200            | Column::AlternateLocation
201            | Column::Entity
202            | Column::SegmentId
203            | Column::InsertionCode
204    )
205}
206
207/// Resolves membership patterns against the structure symbol dictionary.
208///
209/// Plain literal patterns use direct dictionary lookup and therefore avoid a
210/// complete dictionary scan. Only true glob/escape patterns are compiled and
211/// scanned across dictionary entries.
212fn resolve_symbols(structure: &Structure, values: &[Box<str>]) -> BTreeSet<SymbolId> {
213    let dictionary = &structure.data().dictionary;
214    let mut symbols = BTreeSet::new();
215    let mut patterns = Vec::new();
216
217    for value in values {
218        if is_plain_literal(value) {
219            if let Some(symbol) = dictionary.get(value) {
220                symbols.insert(symbol);
221            }
222        } else {
223            patterns.push(Glob::new(value));
224        }
225    }
226
227    if patterns.is_empty() {
228        return symbols;
229    }
230
231    for (symbol, text) in dictionary.iter() {
232        if patterns.iter().any(|pattern| pattern.matches(text)) {
233            symbols.insert(symbol);
234        }
235    }
236
237    symbols
238}
239
240/// Returns whether `pattern` has no glob or escape metacharacters.
241///
242/// Such patterns are semantically exact literals and can be resolved through a
243/// direct dictionary lookup.
244#[inline]
245fn is_plain_literal(pattern: &str) -> bool {
246    !pattern
247        .bytes()
248        .any(|byte| matches!(byte, b'*' | b'?' | b'[' | b'\\'))
249}
250
251#[cfg(test)]
252#[path = "plan_tests.rs"]
253mod tests;
molframe_query/execution/plan.rs

molframe_query/execution/
plan.rs
