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.
136pub(crate) fn 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
147/// Whether the expression removes atoms by negation, which fixes the
148/// universe later conjunction operands must read.
149pub(crate) fn excludes(expr: &PhysicalExpr) -> bool {
150    match expr {
151        PhysicalExpr::Not(_) => true,
152        PhysicalExpr::And(left, right) | PhysicalExpr::Or(left, right) => {
153            excludes(left) || excludes(right)
154        }
155        PhysicalExpr::Logical(logical) => logical_excludes(logical),
156        _ => false,
157    }
158}
159
160pub(crate) fn logical_excludes(expr: &Expr) -> bool {
161    match expr {
162        Expr::Not(_) => true,
163        Expr::And(left, right) | Expr::Or(left, right) => {
164            logical_excludes(left) || logical_excludes(right)
165        }
166        _ => false,
167    }
168}
169
170pub(crate) fn logical_atom_local(expr: &Expr) -> bool {
171    match expr {
172        Expr::All
173        | Expr::None
174        | Expr::Comparison { .. }
175        | Expr::Membership { .. }
176        | Expr::Group(_)
177        | Expr::Atom { .. } => true,
178        Expr::And(left, right) | Expr::Or(left, right) => {
179            logical_atom_local(left) && logical_atom_local(right)
180        }
181        Expr::Not(target) => logical_atom_local(target),
182        _ => false,
183    }
184}
185
186/// Returns a small relative execution-cost class for plan ordering.
187///
188/// Compound expressions rank with the dearest atom-level membership.
189///
190/// Runtime and space are `O(1)`.
191#[inline]
192fn cost(expr: &PhysicalExpr) -> u8 {
193    match expr {
194        PhysicalExpr::None | PhysicalExpr::All => 0,
195        // A residue-level column is decided once per residue and returned as
196        // runs; an atom-level column compares every atom, so it runs second.
197        PhysicalExpr::ResolvedMembership { column, .. } => {
198            if matches!(
199                column,
200                Column::AlternateLocation | Column::LabelAtomName | Column::AuthAtomName
201            ) {
202                2
203            } else {
204                1
205            }
206        }
207        PhysicalExpr::And(_, _) | PhysicalExpr::Or(_, _) | PhysicalExpr::Not(_) => 2,
208        PhysicalExpr::Logical(Expr::Geometric(_)) => 5,
209        PhysicalExpr::Logical(_) => 3,
210    }
211}
212
213/// Returns whether `column` can be lowered to dictionary symbol membership.
214///
215/// Explicit identifier-policy restrictions are preserved. Elements are not
216/// text: a file may write iron as `FE` and a query as `Fe`, so they are
217/// compared as elements rather than through the symbol dictionary.
218fn symbol_column(column: Column, policy: &AnalysisPolicy) -> bool {
219    if policy.identifiers == molframe_core::contract::Namespace::Explicit
220        && matches!(
221            column,
222            Column::Chain | Column::ResidueName | Column::AtomName
223        )
224    {
225        return false;
226    }
227
228    matches!(
229        crate::predicate::resolved_column(column, policy),
230        Column::LabelChain
231            | Column::AuthChain
232            | Column::LabelResidueName
233            | Column::AuthResidueName
234            | Column::LabelAtomName
235            | Column::AuthAtomName
236            | Column::AlternateLocation
237            | Column::Entity
238            | Column::SegmentId
239            | Column::InsertionCode
240    )
241}
242
243/// Resolves membership patterns against the structure symbol dictionary.
244///
245/// Plain literal patterns use direct dictionary lookup and therefore avoid a
246/// complete dictionary scan. Only true glob/escape patterns are compiled and
247/// scanned across dictionary entries.
248fn resolve_symbols(structure: &Structure, values: &[Box<str>]) -> BTreeSet<SymbolId> {
249    let dictionary = &structure.data().dictionary;
250    let mut symbols = BTreeSet::new();
251    let mut patterns = Vec::new();
252
253    for value in values {
254        if is_plain_literal(value) {
255            if let Some(symbol) = dictionary.get(value) {
256                symbols.insert(symbol);
257            }
258        } else {
259            patterns.push(Glob::new(value));
260        }
261    }
262
263    if patterns.is_empty() {
264        return symbols;
265    }
266
267    for (symbol, text) in dictionary.iter() {
268        if patterns.iter().any(|pattern| pattern.matches(text)) {
269            symbols.insert(symbol);
270        }
271    }
272
273    symbols
274}
275
276/// Returns whether `pattern` has no glob or escape metacharacters.
277///
278/// Such patterns are semantically exact literals and can be resolved through a
279/// direct dictionary lookup.
280#[inline]
281fn is_plain_literal(pattern: &str) -> bool {
282    !pattern
283        .bytes()
284        .any(|byte| matches!(byte, b'*' | b'?' | b'[' | b'\\'))
285}
286
287#[cfg(test)]
288#[path = "plan_tests.rs"]
289mod tests;
molframe_query/execution/plan.rs

molframe_query/execution/
plan.rs
