Skip to main content

query/promql/
native_compile.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Compiles a PromQL AST into a [`NativeTree`].
16//!
17//! This is the front half of the native evaluation model: it reads the parsed statement and writes
18//! down what it means as bound nodes. The native planner uses this compiler to build a tree for
19//! standalone execution. Its accepted expressions are described by the recursive rule below:
20//!
21//! ```text
22//! <expression>                                     one of, recursively:
23//!   <selector>                                     e.g. x, x offset -5m
24//!   <range function>(<matrix>)                     e.g. rate(x[5m]), rate(x[5m:1m] @ 1234)
25//!   quantile_over_time(<constant>, <matrix>)       e.g. quantile_over_time(0.9, x[5m])
26//!   predict_linear(<matrix>, <constant>)           e.g. predict_linear(x[5m], 300)
27//!   double_exponential_smoothing(<matrix>, <constant>, <constant>)
28//!                                                  e.g. double_exponential_smoothing(x[5m], .5, .1)
29//!   <math function>(<expression>[, <constant>]*)   e.g. abs(rate(x[5m])), clamp_min(x, 0)
30//!   <round or clamp>(<expression>, <scalar>+)      e.g. round(x, time() / 10), clamp(x, 0, time())
31//!   <histogram function>(<expression>)             e.g. histogram_count(x)
32//!   <sort>(<expression>[, <string>]*)              e.g. sort_desc(x), sort_by_label(x, "job")
33//!   absent(<expression>)                           e.g. absent(x{job="a"})
34//!   absent_over_time(<matrix>)                     e.g. absent_over_time(x{job="a"}[5m])
35//!   <histogram>(<constant>+, <expression>)         e.g. histogram_quantile(0.9, rate(x[5m]))
36//!   <label function>(<expression>, <string>*)       e.g. label_replace(x, "a", "$1", "b", "(.*)")
37//!   <expression> <operator> <scalar>               e.g. x * 100, x > bool time()
38//!   <scalar> <operator> <expression>               e.g. 1 / x, time() - timestamp(x)
39//!   <scalar> <operator> <scalar>                   e.g. time() - 60, time() > bool 1
40//!   time(), pi(), vector(<scalar>)                 e.g. vector(time()), pi() * x
41//!   <date function>()                              e.g. hour(), which is `hour(vector(time()))`
42//!   -<expression>                                  e.g. -x
43//!   <expression> <set operator> <expression>       e.g. x and on(job) y, x unless y
44//!   info(<expression>[, {<matchers>}])             e.g. info(rate(x[5m]), {version=~".+"})
45//!   <aggregator> [(by|without)(<labels>)] (<expression>)
46//!                                                  e.g. avg by(job)(rate(x[5m]) * 100)
47//!   <aggregator> (<expression>) [(by|without)(<labels>)]
48//!                                                  e.g. count (x) by(job)
49//!   quantile(<constant>, <expression>) [(by|without)(<labels>)]
50//!                                                  e.g. quantile(0.9, x) by(job)
51//!   <selector aggregator>(<constant>, <expression>) [(by|without)(<labels>)]
52//!                                                  e.g. topk(3, x) by(job), limit_ratio(0.5, x)
53//!   count_values(<string>, <expression>) [(by|without)(<labels>)]
54//!                                                  e.g. count_values("v", x)
55//!
56//! <matrix>    <selector>[<range>]<modifiers>       a range selector: raw samples
57//!           | <expression>[<range>:<step>]<modifiers>
58//!                                                  a subquery: <expression> evaluated on a grid;
59//!                                                  the step may be omitted as `[<range>:]`
60//! <scalar>    <constant> | time() | <scalar> <operator> <scalar>
61//! <modifiers>                                      nothing, `offset <duration>`, `@ <anchor>`, or
62//!                                                  both, in either order — e.g. `x[5m] @ 1234
63//!                                                  offset 1m`
64//! ```
65//!
66//! where `<set operator>` is `and`, `or` or `unless`, optionally with `on(...)` or `ignoring(...)`,
67//! `<aggregator>` is `sum`, `avg`, `count`, `min`, `max`, `group`, `stddev`, `stdvar` or
68//! `quantile`, `<selector aggregator>` is `topk`, `bottomk`, `limitk` or `limit_ratio`, the
69//! function names are [`range_signature`]'s and [`math_signature`]'s, and which side
70//! of the matrix a range function's constants go on is [`RangeSignature`]'s: before it for
71//! `quantile_over_time`, after it for `predict_linear` and `double_exponential_smoothing`. A math
72//! function's constants always follow its vector.
73//!
74//! Parentheses are transparent wherever they appear — `rate((x[5m]))` is `rate(x[5m])` — because
75//! they say how a statement was typed rather than what it asks for.
76//!
77//! A subquery's `<expression>` is any shape above, so a subquery nests inside a subquery on a grid
78//! of its own, as in `rate(rate(x[5m:1m])[10m:30s])`; a `<step>` left out means Prometheus's default
79//! evaluation interval, one minute. Its `offset` and its `@` anchor are its own, not the inner
80//! expression's, so `rate(x[5m:1m] @ end() offset 1m)` reads one fixed interval. A `<selector>`
81//! outside a `<matrix>` takes an `offset` and an optional `@` anchor; `x @ 100` selects at one
82//! fixed instant across the evaluation grid, as does `rate(x[5m] @ 100)` for its window.
83//!
84//! Those shapes become `Input` (raw samples) → `Instant` (the last sample within the statement's
85//! lookback), `Input` (raw samples) → `Window` (the range function over the statement's grid),
86//! `<expression>` → `Window` whose input is evaluated (the subquery, whose input grid is its own),
87//! `<expression>` → `Map` (a pointwise math, native histogram or label function over what its
88//! argument evaluates to) and, over
89//! any of those, `Binary` (an arithmetic or comparison operation between vectors or with a
90//! constant on one side), `Scalar` (that constant), `Set` (`and`, `or` or `unless` between two
91//! vectors), `Info` (the expression and an `Instant` of the info metric reporting sample times),
92//! `Aggregate` (one of the nine aggregators that
93//! fold a group's values into one value per grid point, optionally grouped) and `Vector` (an
94//! operation over the whole vector at each point: a sort, `absent`, a classic histogram function, a
95//! selecting aggregator or `count_values`). Everything else is a
96//! [`DataFusionError::NotImplemented`] that names what was found and quotes the shapes above,
97//! because rejecting a query the compiler does not understand is the only honest alternative to
98//! compiling it into something else.
99//!
100//! The compiler binds a subquery's child grid and `RangeWindow` independently of runtime execution:
101//! compilation describes the anchored interval, while runtime support determines how that bound
102//! plan is consumed.
103//!
104//! Two decisions keep the recursion from growing a branch per query. A constant argument — a
105//! quantile, a rounding step, a clamp bound — is folded out of the statement by [`constant_value`],
106//! so `quantile_over_time(1 - 0.1, x[5m])` binds the number it means rather than the expression it
107//! was written as. A math function is bound by [`math_op`] from a list of names, so
108//! `clamp_min(abs(rate(x[5m])), 0)` is two maps over one window because the arguments nest, not
109//! because the compiler knows the query. Arithmetic inside a fold is the kernel operation
110//! [`BinaryOp::kind`] names, so the number this compiler binds and the number the kernel computes
111//! cannot disagree about `%`, `^` or `atan2`.
112//!
113//! Two more are about what a node means rather than about which node to build. A binary operation
114//! keeps its operands in the order they were written, because most operators are not commutative:
115//! `1 / x` is not `x / 1`, and which side the constant is on is the only thing that tells them
116//! apart. `return_bool` is carried as its own field, so `x > 0` (which filters) and `x > bool 0`
117//! (which reports zero or one) are one node with one field changed. A negation then needs no node of
118//! its own: `-x` binds as the multiplication by `-1` that it is, which the multiplication kernel
119//! already computes.
120//!
121//! Vector matching is bound with each selector's own input, including the labels and cardinality
122//! written on a vector–vector operation. A scalar has no input of its own: it is bound next to the
123//! vector that gives it something to broadcast over, while a statement whose value is only a
124//! constant is bound by [`compile_statement`] as that constant on the statement's grid.
125//!
126//! An aggregate is bound as [`AggregateStage::Complete`], which is a claim about the whole execution
127//! rather than about the node: it says that every contribution to every group is in this execution's
128//! input. The caller has to keep that claim. One tree per partition does not: handing every
129//! partition the same `Complete` tree sums each partition's part and reports it as the group's
130//! whole, so a partitioned caller has to feed whole groups to one execution or split the aggregation
131//! into `Partial` and `Final` instead. What a `Complete` node guarantees here is only the arithmetic
132//! — that the values it folded are all the values it was given.
133//!
134//! The statement's grid, the selector's lookback, window, offset and anchor are the only numbers
135//! derived here; the legality of the tree is not checked here. [`NativeTree::try_new`] is the
136//! single authority on that, so a node added later cannot be legal in one place and illegal in
137//! another. What is refused before a tree exists is the scan's shape: no shape below can consume
138//! chunks of different series that interleave, so an `Interleaved` ordering is refused once, at the
139//! entry, and [`NativeNode::validate`] refuses the same ordering for a tree built some other way.
140
141use std::cell::RefCell;
142use std::sync::Arc;
143use std::time::Duration;
144
145use datafusion::error::{DataFusionError, Result};
146use datatypes::series::samples::{FieldSpec, SeriesSchema};
147use datatypes::series::time::{EvalGrid, GridSpec};
148use datatypes::series::{SeriesLabels, SeriesOrdering};
149use promql::extension_plan::FieldKind;
150use promql::histogram_eval::{HistogramFunction, NativeHistogramFunction};
151use promql::info::InfoSelector;
152use promql::map::MathOp;
153use promql::map_label::LabelRewrite;
154use promql::map_time::DateFunction;
155use promql::native::plan::{
156    AggregateKind, AggregateStage, BoundAggregate, BoundInput, BoundInstant, BoundMap, BoundScalar,
157    BoundSetOp, BoundVectorOp, BoundWindow, Grouping, InstantValue, MapOp, NativeExpr, NativeNode,
158    NativeTree, NativeType, ParameterizedOp,
159};
160use promql::range_eval::{RangeFunction, RangeWindow, subquery_grid};
161use promql::select::{LabelMatcher, MatchOp, SortOrder, absent_labels};
162use promql::vector_match::{
163    BinaryKind, BinaryMatching, BinaryOp, Cardinality, FillValues, MatchingLabels, SetOp,
164    binary_output_schema,
165};
166use promql_parser::label::{MatchOp as ParserMatchOp, Matcher, Matchers};
167use promql_parser::parser::token::TokenType;
168use promql_parser::parser::value::ValueType;
169use promql_parser::parser::{
170    AggregateExpr, AtModifier, BinModifier, BinaryExpr, Call, EvalStmt, Expr as PromExpr,
171    LabelModifier, MatrixSelector, NumberLiteral, Offset, StringLiteral, SubqueryExpr,
172    VectorMatchCardinality, VectorMatchFillValues, VectorSelector, token,
173};
174
175use crate::promql::label_values::signed_millis_since_epoch;
176
177#[derive(Clone, Copy, Debug, PartialEq, Eq)]
178pub enum SelectorTiming {
179    Instant { lookback_ms: i64 },
180    Window { range_ms: i64 },
181}
182
183#[derive(Clone, Debug)]
184pub struct SelectorRequirement {
185    pub metric: Option<String>,
186    pub matchers: Matchers,
187    pub offset_ms: i64,
188    pub at_ms: Option<i64>,
189    pub grid_start_ms: i64,
190    pub grid_end_ms: i64,
191    pub timing: SelectorTiming,
192}
193
194impl SelectorRequirement {
195    /// Returns `(start_ms, end_ms, include_start)` for the scan hull covering this selector.
196    ///
197    /// The upper endpoint is inclusive. The hull can include timestamps unused by a sparse
198    /// evaluation grid; `grid_end_ms` is its actual last point, not the statement's end. The lower
199    /// endpoint is inclusive only for a zero-lookback instant selector.
200    pub fn raw_scan_bounds(&self) -> Result<(i64, i64, bool)> {
201        let end = self
202            .at_ms
203            .unwrap_or(self.grid_end_ms)
204            .checked_sub(self.offset_ms)
205            .ok_or_else(|| DataFusionError::Plan("selector scan end overflows".into()))?;
206        let lower = self
207            .at_ms
208            .unwrap_or(self.grid_start_ms)
209            .checked_sub(self.offset_ms)
210            .ok_or_else(|| DataFusionError::Plan("selector scan start overflows".into()))?;
211        let (duration, inclusive) = match self.timing {
212            SelectorTiming::Instant { lookback_ms } => (lookback_ms, lookback_ms == 0),
213            SelectorTiming::Window { range_ms } => (range_ms, false),
214        };
215        let start = lower
216            .checked_sub(duration)
217            .ok_or_else(|| DataFusionError::Plan("selector scan start overflows".into()))?;
218        Ok((start, end, inclusive))
219    }
220}
221
222/// One compiled selector occurrence and the scan layout bound for it.
223#[derive(Clone, Debug)]
224pub struct CompiledInput {
225    /// Occurrence number assigned in compiler traversal order, starting at zero. The caller maps this
226    /// occurrence to the appropriate scan; different occurrences may map to a shared scan child.
227    pub source_index: usize,
228    pub requirement: SelectorRequirement,
229    pub schema: Arc<SeriesSchema>,
230    pub ordering: SeriesOrdering,
231}
232
233#[derive(Clone, Debug)]
234pub struct CompiledTree {
235    pub tree: NativeTree,
236    pub inputs: Arc<[CompiledInput]>,
237}
238
239/// The shapes this compiler accepts, quoted in every rejection.
240///
241/// It is one sentence of grammar rather than a list of examples, because it is what a refused query
242/// reads: the shapes have to be true of every query the compiler binds, and the examples only show
243/// them. The two matrix shapes and the recursion through them are stated first, because that
244/// recursion is what a reader is most likely to get wrong.
245const SUPPORTED: &str = "a selector — `x`, optionally with an `offset` — a range function over \
246                         a matrix, where a matrix is `<selector>[<range>]` as in `rate(x[5m])` or \
247                         `<expression>[<range>:<step>]` as in `rate(x[5m:1m])`, with the step \
248                         optionally omitted as `[<range>:]`, where the subquery's `<expression>` \
249                         is any shape here, so a subquery nests on a grid of its own as in \
250                         `rate(rate(x[5m:1m])[10m:30s])`, and where either matrix shape carries the \
251                         `offset` and `@` anchor written on it as in `rate(x[5m] @ 1234)`; a math \
252                         function over any of them (`abs(rate(x[5m]))`, `clamp_min(x, 0)`), with \
253                         `round` and the `clamp` functions also taking scalars \
254                         (`round(x, time() / 10)`), a native \
255                         histogram function over any of them (`histogram_count(x)`), a label \
256                         function over any of them \
257                         (`label_replace(x, \"a\", \"$1\", \"b\", \"(.*)\")`), a binary \
258                         operation between one of them and a scalar (`2 / (x + 1)`, \
259                         `x > bool time()`, `time() - timestamp(x)`), a scalar — a constant, \
260                         `time()` or a binary operation between scalars — \
261                         `vector(<scalar>)`, a date function without an argument (`hour()`), a \
262                         negation of one of them (`-x`), a set operation between two of them \
263                         (`x and on(job) y`, `x or y`, `x unless y`), `info` over any of them with \
264                         one info metric (`info(x, {version=~\".+\"})`), or one of the \
265                         aggregators that folds a group's values into one value per grid point — \
266                         `sum`, `avg`, `count`, `min`, `max`, `group`, `stddev`, `stdvar` and \
267                         `quantile(<constant>, <expression>)` — over any of them, optionally \
268                         grouped by `by` or `without` as in `avg by(job)(rate(x[5m]) * 100)`; \
269                         `topk`, `bottomk`, `limitk`, `limit_ratio` or `count_values` over any of \
270                         them, as in `topk(3, x) by(job)` and `count_values(\"v\", x)`; a \
271                         sort, `absent`, `absent_over_time` or `histogram_quantile` / \
272                         `histogram_fraction` over any of them (`sort_desc(x)`, \
273                         `absent(x{job=\"a\"})`, `absent_over_time(x{job=\"a\"}[5m])`, \
274                         `histogram_quantile(0.9, rate(x[5m]))`); a range function's own \
275                         constants sit where that function takes them, before \
276                         the matrix for `quantile_over_time(0.9, x[5m])` and after it for \
277                         `predict_linear(x[5m], 300)` and \
278                         `double_exponential_smoothing(x[5m], 0.5, 0.1)`";
279
280/// Compiles `stmt` into a tree that reads `input` and evaluates the statement's expression over it.
281///
282/// `input` is the raw series schema the caller bound from the table, and the caller has to apply the
283/// selector's matchers before binding it: `__field__`, `__schema__` and `__database__` select rows
284/// and fields the same way they do in the existing planner, and the AST cannot restate that
285/// afterwards. `input.fields` is therefore the post-`__field__` field set, not the table's; a caller
286/// that binds every field of the table instead compiles a different, wrong window, because
287/// `rate(x{__field__="a"}[5m])` over fields `[a, b]` would fold two fields where the planner folds
288/// one.
289///
290/// `ordering` is what the caller's scan guarantees, and the tree records it rather than assuming
291/// one. Only `Contiguous` and `KeyThenTime` are accepted: every shape this compiler accepts reads
292/// one series to its last chunk before the next, so an `Interleaved` declaration is refused at the
293/// entry, before any shape is built — the bare selector included, which returns before a window
294/// exists — and a shape added later inherits the refusal instead of restating it.
295/// [`NativeNode::validate`] refuses the same ordering in its `Instant` and `Window` branches, as a
296/// backstop for a tree built some other way.
297///
298/// This compatibility entry accepts exactly one selector. Call [`compile_selectors`] to retain
299/// each selector's requirement and binding when compiling more than one input.
300pub fn compile(
301    stmt: &EvalStmt,
302    input: Arc<SeriesSchema>,
303    ordering: SeriesOrdering,
304) -> Result<NativeTree> {
305    // This entry describes one float input: it has no way to be told that a field carries native
306    // histograms, so an aggregate whose state would depend on that is bound as the float aggregate it
307    // would be. A caller that does know - the planner, from the table's own fields - binds through
308    // [`compile_selectors`] and passes the kind with it.
309    let compiled = compile_selectors(
310        stmt,
311        &|_| Ok(Arc::clone(&input)),
312        ordering,
313        Some(FieldKind::Float),
314    )?;
315    if compiled.inputs.len() != 1 {
316        return Err(not_implemented(&format!(
317            "`compile` with {} selector inputs; use `compile_selectors` to bind each input",
318            compiled.inputs.len()
319        )));
320    }
321    Ok(compiled.tree)
322}
323
324fn data_free_value_field(stmt: &EvalStmt) -> Arc<str> {
325    fn visit(expr: &PromExpr, targets: &mut Vec<String>) {
326        match expr {
327            PromExpr::Aggregate(aggregate) => {
328                if aggregate.op.id() == token::T_COUNT_VALUES
329                    && let Some(param) = &aggregate.param
330                    && let PromExpr::StringLiteral(value) = unparen(param)
331                {
332                    targets.push(value.val.clone());
333                }
334                if let Some(modifier) = &aggregate.modifier {
335                    match modifier {
336                        LabelModifier::Include(labels) | LabelModifier::Exclude(labels) => {
337                            targets.extend(labels.labels.iter().cloned());
338                        }
339                    }
340                }
341                // An aggregate's parameter is an expression since `topk` and friends take one, and
342                // the grouping labels it binds are names the value field must not collide with:
343                // an aggregate refuses to group by the field it folds.
344                if let Some(param) = &aggregate.param {
345                    visit(param, targets);
346                }
347                visit(&aggregate.expr, targets);
348            }
349            PromExpr::Unary(unary) => visit(&unary.expr, targets),
350            PromExpr::Binary(binary) => {
351                if let Some(modifier) = &binary.modifier {
352                    if let Some(matching) = &modifier.matching {
353                        targets.extend(matching.labels().labels.iter().cloned());
354                    }
355                    match &modifier.card {
356                        VectorMatchCardinality::OneToMany(labels)
357                        | VectorMatchCardinality::ManyToOne(labels) => {
358                            targets.extend(labels.labels.iter().cloned());
359                        }
360                        _ => {}
361                    }
362                }
363                visit(&binary.lhs, targets);
364                visit(&binary.rhs, targets);
365            }
366            PromExpr::Paren(paren) => visit(&paren.expr, targets),
367            PromExpr::Subquery(subquery) => visit(&subquery.expr, targets),
368            PromExpr::Call(call) => call.args.args.iter().for_each(|arg| visit(arg, targets)),
369            _ => {}
370        }
371    }
372    let mut targets = Vec::new();
373    visit(&stmt.expr, &mut targets);
374    if !targets.iter().any(|name| name == VECTOR_FIELD) {
375        return Arc::from(VECTOR_FIELD);
376    }
377    (0usize..)
378        .map(|index| format!("native_value_{index}"))
379        .find(|candidate| !targets.iter().any(|name| name == candidate))
380        .map(Arc::from)
381        .expect("the value field candidate sequence is unbounded")
382}
383
384/// Compiles a statement that reads no data — a constant, `time()`, `vector(time())`, `hour()` —
385/// to a tree without inputs, on the statement's grid.
386///
387/// A statement that reads a selector is refused: its scan is the caller's to bind, through
388/// [`compile_selectors`].
389pub fn compile_statement(stmt: &EvalStmt) -> Result<NativeTree> {
390    let output_field = data_free_value_field(stmt);
391    let compiled = compile_selectors_with_value_field(
392        stmt,
393        &|_| {
394            Err(not_implemented(&format!(
395                "a selector in `{}`, which is compiled as a statement that reads no data",
396                stmt.expr
397            )))
398        },
399        SeriesOrdering::Contiguous,
400        output_field,
401        // A statement that reads no data has no source to take a kind from. An aggregate over it
402        // still binds: the walk only reads the source kind at an input node, and there is none.
403        None,
404    )?;
405    Ok(compiled.tree)
406}
407
408/// Compiles `stmt` with an explicit evaluation grid, instead of the one its bounds derive.
409///
410/// A subquery root's inner expression is evaluated on the subquery's child grid, while the
411/// statement's own bounds stay where `@ start()` and `@ end()` resolve against them.
412pub(crate) fn compile_statement_with_grid(
413    stmt: &EvalStmt,
414    grid: Arc<EvalGrid>,
415) -> Result<NativeTree> {
416    let output_field = data_free_value_field(stmt);
417    let compiled = compile_selectors_with_grid_and_value_field(
418        stmt,
419        &|_| {
420            Err(not_implemented(&format!(
421                "a selector in `{}`, which is compiled as a statement that reads no data",
422                stmt.expr
423            )))
424        },
425        SeriesOrdering::Contiguous,
426        output_field,
427        Some(grid),
428        None,
429    )?;
430    Ok(compiled.tree)
431}
432
433/// Compiles `stmt` into a tree and returns a binding record for each selector occurrence.
434///
435/// `bindings` is called once per selector with its requirements. The resulting source indices are
436/// occurrence numbers in compiler traversal order; the caller maps them to scan children.
437pub fn compile_selectors(
438    stmt: &EvalStmt,
439    bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
440    ordering: SeriesOrdering,
441    source_kind: Option<FieldKind>,
442) -> Result<CompiledTree> {
443    compile_selectors_with_value_field(
444        stmt,
445        bindings,
446        ordering,
447        Arc::from(VECTOR_FIELD),
448        source_kind,
449    )
450}
451
452/// Compiles `stmt` with an explicit evaluation grid. See [`compile_statement_with_grid`].
453pub(crate) fn compile_selectors_with_grid(
454    stmt: &EvalStmt,
455    bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
456    ordering: SeriesOrdering,
457    grid: Arc<EvalGrid>,
458    source_kind: Option<FieldKind>,
459) -> Result<CompiledTree> {
460    compile_selectors_with_grid_and_value_field(
461        stmt,
462        bindings,
463        ordering,
464        Arc::from(VECTOR_FIELD),
465        Some(grid),
466        source_kind,
467    )
468}
469
470fn compile_selectors_with_value_field(
471    stmt: &EvalStmt,
472    bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
473    ordering: SeriesOrdering,
474    value_field: Arc<str>,
475    source_kind: Option<FieldKind>,
476) -> Result<CompiledTree> {
477    compile_selectors_with_grid_and_value_field(
478        stmt,
479        bindings,
480        ordering,
481        value_field,
482        None,
483        source_kind,
484    )
485}
486
487fn compile_selectors_with_grid_and_value_field(
488    stmt: &EvalStmt,
489    bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
490    ordering: SeriesOrdering,
491    value_field: Arc<str>,
492    grid: Option<Arc<EvalGrid>>,
493    source_kind: Option<FieldKind>,
494) -> Result<CompiledTree> {
495    if ordering == SeriesOrdering::Interleaved {
496        return Err(not_implemented(
497            "raw samples whose series interleave, which this compiler cannot consume: a native \
498             evaluation reads one series to its last chunk before the next, so chunks of different \
499             series may not interleave",
500        ));
501    }
502    // A tree reports evaluated samples or a scalar on the statement's grid; a range vector or a
503    // string has no grid of its own.
504    if !matches!(
505        stmt.expr.value_type(),
506        ValueType::Vector | ValueType::Scalar
507    ) {
508        return Err(not_implemented(&format!(
509            "the expression `{}`, which is a {} where a tree reports evaluated samples or a \
510             scalar",
511            stmt.expr,
512            stmt.expr.value_type()
513        )));
514    }
515    let inputs = RefCell::new(Vec::new());
516    let context = Context {
517        stmt,
518        bindings,
519        ordering,
520        inputs: &inputs,
521        // The grid is derived only once the statement is a shape this compiler answers, so an
522        // unsupported statement reports the reason it has no tree rather than a grid complaint.
523        grid: match grid {
524            Some(grid) => grid,
525            None => statement_grid(stmt)?,
526        },
527        value_field,
528        source_kind,
529    };
530    let tree = NativeTree::try_new(compile_expr(&context, &stmt.expr)?)?;
531    let inputs = inputs.into_inner();
532    validate_inputs(tree.root(), &inputs)?;
533    Ok(CompiledTree {
534        tree,
535        inputs: inputs.into(),
536    })
537}
538
539fn validate_inputs(root: &NativeNode, inputs: &[CompiledInput]) -> Result<()> {
540    let bound = root.inputs();
541    if bound.len() == inputs.len()
542        && bound
543            .iter()
544            .zip(inputs)
545            .enumerate()
546            .all(|(index, (bound, input))| {
547                input.source_index == index
548                    && bound.source_index == input.source_index
549                    && bound.ordering == input.ordering
550                    && bound
551                        .output
552                        .samples()
553                        .is_some_and(|schema| Arc::ptr_eq(schema, &input.schema))
554            })
555    {
556        return Ok(());
557    }
558    Err(DataFusionError::Internal(
559        "a compiled tree's recorded inputs do not match its input nodes".into(),
560    ))
561}
562
563/// Shared statement, per-selector binding callback, occurrence records, ordering and current grid.
564///
565/// A subquery substitutes its own grid while reusing the statement-level bindings and input list.
566struct Context<'a> {
567    stmt: &'a EvalStmt,
568    bindings: &'a dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
569    ordering: SeriesOrdering,
570    inputs: &'a RefCell<Vec<CompiledInput>>,
571    grid: Arc<EvalGrid>,
572    value_field: Arc<str>,
573    /// The kind the statement's sources carry, when the caller knows it.
574    ///
575    /// A binding whose state depends on it is refused rather than bound from a guess when it is
576    /// unknown: `source_kind` is `None` only for a statement the caller could not describe, and a
577    /// tree with no source never needs it.
578    source_kind: Option<FieldKind>,
579}
580
581/// Compiles `expr` into the node it denotes, recursing into whatever it is made of.
582///
583/// One rule per kind of expression and nothing per query: a math function is compiled by compiling
584/// its argument, so a query nests as deeply as it was written. A kind this compiler has no node for
585/// is refused with what was found, which is why the rejection is useful without a coverage list.
586fn compile_expr(context: &Context, expr: &PromExpr) -> Result<NativeNode> {
587    // A constant is a value rather than a computation, so it binds as the number it folds to, by the
588    // same fold a call's parameters use: `x * (1 + 2)` carries `3` rather than an addition the tree
589    // would have to know how to run. The fold is checked first so that no shape below has to say
590    // what it does with a constant operand.
591    if let Some(value) = constant_value(expr) {
592        return Ok(scalar_node(context, value));
593    }
594    match expr {
595        // Parentheses group, so they change how a statement was typed rather than what it asks for:
596        // the expression inside them is the one that compiles.
597        PromExpr::Paren(paren) => compile_expr(context, &paren.expr),
598        PromExpr::Call(call) => compile_call(context, call),
599        PromExpr::VectorSelector(selector) => instant_selection(context, selector),
600        PromExpr::Unary(unary) => negate(context, &unary.expr),
601        PromExpr::Binary(binary) => binary_operation(context, binary),
602        PromExpr::Aggregate(aggregate) => aggregate_expr(context, aggregate),
603        found => Err(not_implemented(&format!("the expression `{found}`"))),
604    }
605}
606
607/// Binds `value` as a constant scalar on the grid of the expression being compiled.
608///
609/// The grid is the context's rather than the constant's own: a constant has no timestamps, so the
610/// only positions it can be broadcast over are the ones the expression it sits next to is evaluated
611/// at — the statement's grid, or a subquery's inside one. [`NativeTree::validate`] compares a binary
612/// operation's two grids by spec rather than by allocation.
613///
614/// Nothing here can fail: the grid is the one [`Context`] already carries, so a caller needs no `?`.
615fn scalar_node(context: &Context, value: f64) -> NativeNode {
616    NativeNode {
617        expr: NativeExpr::Scalar(BoundScalar { value }),
618        output: NativeType::Scalar(Arc::clone(&context.grid)),
619    }
620}
621
622/// Compiles a negation as the multiplication it is: `-x` is `-1 * x`.
623///
624/// The tree has no negate node and needs none: broadcasting a constant over the expression's value
625/// is the same arithmetic, and the multiplication kernel is the one that already computes it. A
626/// dedicated negate kernel would be an optimization of this node's work rather than a different
627/// meaning, so binding the multiplication does not bind anything the query did not ask for.
628fn negate(context: &Context, operand: &PromExpr) -> Result<NativeNode> {
629    // The constant goes on the left, where the minus was: `-x` subtracts nothing, but a reader of
630    // the tree should see the same order the query was written in.
631    Ok(broadcast(
632        scalar_node(context, -1.0),
633        compile_expr(context, operand)?,
634        BinaryOp::Mul,
635        false,
636    ))
637}
638
639/// Compiles a binary operation, preserving written operand order and vector matching modifiers.
640///
641/// A scalar carries no labels, so broadcasting it over a vector is unambiguous. Vector operands
642/// retain their own input bindings and matching, including a fill on either side.
643fn binary_operation(context: &Context, binary: &BinaryExpr) -> Result<NativeNode> {
644    if let Some(op) = set_op(&binary.op) {
645        return set_operation(context, binary, op);
646    }
647    let Some(op) = binary_op(&binary.op) else {
648        return Err(not_implemented(&format!(
649            "the binary operator `{}` in `{binary}`",
650            binary.op
651        )));
652    };
653    // Two vectors are matched by their labels, so the node carries the modifiers the query wrote and
654    // each operand is compiled from its own selector.
655    if binary.lhs.value_type() == ValueType::Vector && binary.rhs.value_type() == ValueType::Vector
656    {
657        let left = compile_expr(context, &binary.lhs)?;
658        let right = compile_expr(context, &binary.rhs)?;
659        return bind_vector_binary(binary, left, right, op);
660    }
661    // What is left has a constant on one side, and a modifier is refused rather than dropped. This
662    // is deliberately narrower than Prometheus, which drops an `on` or `ignoring` written on a
663    // scalar rather than refusing it; refusing is the conservative choice here, because the tree's
664    // matching has no field that could carry the modifier, so binding the operation would compute
665    // something the query did not ask for. A fill value is refused for the same reason: the tree's
666    // matching has no field for one, and dropping it would compute the operation without the fill
667    // the query asked for.
668    if refuses_modifier(binary.modifier.as_ref()) {
669        return Err(not_implemented(&format!(
670            "the vector matching in `{binary}`, which a constant operand has nothing to match: \
671             `on`, `ignoring`, `group_left` and `group_right` name labels of a vector, and a fill \
672             value fills in a match group that could miss"
673        )));
674    }
675    // A comparison of two scalars reports a value only when written with `bool`; Prometheus
676    // refuses to parse one without it. Binding it would produce a node that only fails when it is
677    // run, so it is refused here with what was found. Two constants never reach here: they folded.
678    if binary.lhs.value_type() == ValueType::Scalar
679        && binary.rhs.value_type() == ValueType::Scalar
680        && matches!(op.kind(), BinaryKind::Comparison(_))
681        && !binary.return_bool()
682    {
683        return Err(not_implemented(&format!(
684            "the binary operation `{binary}` between two scalars, which reports no value: a \
685             comparison of two scalars is written with `bool` to say whether it holds"
686        )));
687    }
688    // Both operands are compiled before the node is built, so `2 / (x + 1)` nests. The constant side
689    // is bound by [`compile_expr`]'s fold, which is what makes it a scalar node rather than an
690    // expression the tree would have to run.
691    Ok(broadcast(
692        compile_expr(context, &binary.lhs)?,
693        compile_expr(context, &binary.rhs)?,
694        op,
695        binary.return_bool(),
696    ))
697}
698
699/// Binds the same vector operation over compiled or already evaluated operands.
700fn bind_vector_binary(
701    binary: &BinaryExpr,
702    left: NativeNode,
703    right: NativeNode,
704    op: BinaryOp,
705) -> Result<NativeNode> {
706    let (Some(lhs), Some(rhs)) = (left.output.samples(), right.output.samples()) else {
707        return Err(DataFusionError::Internal(format!(
708            "the binary operation `{binary}` compiled a vector operand to something other than samples"
709        )));
710    };
711    let output = NativeType::Samples(binary_output_schema(lhs, rhs)?);
712    Ok(NativeNode {
713        expr: NativeExpr::Binary {
714            left: Box::new(left),
715            right: Box::new(right),
716            matching: vector_matching(binary, op)?,
717        },
718        output,
719    })
720}
721
722/// Uses the ordinary binary binder for two evaluated frame inputs.
723pub(crate) fn bind_evaluated_binary(
724    binary: &BinaryExpr,
725    left: NativeNode,
726    right: NativeNode,
727) -> Result<NativeTree> {
728    let op = binary_op(&binary.op).ok_or_else(|| {
729        not_implemented(&format!(
730            "the binary operator `{}` in `{binary}`",
731            binary.op
732        ))
733    })?;
734    NativeTree::try_new(bind_vector_binary(binary, left, right, op)?)
735}
736
737/// Compiles `and`, `or` or `unless` between two vectors, matched by the labels the query wrote.
738///
739/// The parser already refuses a scalar operand, `bool` and `group_left` / `group_right` on a set
740/// operator. It does not refuse a fill value, which Prometheus does ("filling in missing series not
741/// allowed for set operators"), so that is refused here along with any cardinality other than the
742/// many-to-many the parser assigns.
743fn set_operation(context: &Context, binary: &BinaryExpr, op: SetOp) -> Result<NativeNode> {
744    let modifier = binary.modifier.as_ref();
745    if modifier.is_some_and(|modifier| {
746        modifier.card != VectorMatchCardinality::ManyToMany
747            || modifier.fill_values != VectorMatchFillValues::default()
748    }) {
749        return Err(not_implemented(&format!(
750            "the modifiers in `{binary}`: a set operator matches many-to-many and takes no fill \
751             value"
752        )));
753    }
754    let labels = matching_labels(modifier);
755    let left = compile_expr(context, &binary.lhs)?;
756    let right = compile_expr(context, &binary.rhs)?;
757    let (Some(lhs), Some(rhs)) = (left.output.samples(), right.output.samples()) else {
758        return Err(DataFusionError::Internal(format!(
759            "the set operation `{binary}` compiled an operand to something other than samples: the \
760             parser only accepts a set operator between two vectors"
761        )));
762    };
763    // Prometheus has one value per sample, and the existing planner refuses a set operator over
764    // several fields, so per-field presence has no reference semantics to follow.
765    if lhs.fields.len() != 1 || rhs.fields.len() != 1 {
766        return Err(not_implemented(&format!(
767            "the set operation `{binary}` between vectors of {} and {} fields: a set operator is \
768             compiled over one field on each side",
769            lhs.fields.len(),
770            rhs.fields.len()
771        )));
772    }
773    // A set operation hands on the samples it keeps unchanged, so it reports the left side's fields
774    // on the grid both sides share.
775    let output = left.output.clone();
776    Ok(NativeNode {
777        expr: NativeExpr::Set {
778            left: Box::new(left),
779            right: Box::new(right),
780            op: BoundSetOp { op, labels },
781        },
782        output,
783    })
784}
785
786/// Wraps two compiled operands in the binary node that applies `op` to them.
787///
788/// The output is the vector side's own binding, because a scalar carries no fields: a broadcast keeps
789/// the vector's fields and the grid it is evaluated on, which is the statement's grid on both sides.
790/// Two scalars are possible as a nested operand — a pair that [`constant_value`] refuses to fold, such
791/// as a comparison between two constants — and the node reports the left one's grid, which is the
792/// statement's too. The operands keep the order they were written in, because a non-commutative
793/// operator means what that order says.
794fn broadcast(left: NativeNode, right: NativeNode, op: BinaryOp, return_bool: bool) -> NativeNode {
795    // `compile_expr` binds a constant to a scalar node and a selection or a function to a vector, so
796    // this is where the side the operation reports is decided.
797    let output = if matches!(left.output, NativeType::Scalar(_)) {
798        right.output.clone()
799    } else {
800        left.output.clone()
801    };
802    NativeNode {
803        expr: NativeExpr::Binary {
804            left: Box::new(left),
805            right: Box::new(right),
806            matching: scalar_matching(op, return_bool),
807        },
808        output,
809    }
810}
811
812/// The matching a vector-and-constant operation records.
813///
814/// Nothing is matched: a scalar carries no labels, so [`NativeTree::validate`] broadcasts it and
815/// reads neither `labels` nor `cardinality`. They carry the default a vector–vector operation of the
816/// same operator would have, which is also the only matching PromQL allows here — it rejects
817/// `on`, `ignoring`, `group_left` and `group_right` on a scalar–vector operation. `return_bool` is
818/// the one modifier that changes what this operation computes: `x > 0` filters the vector and
819/// `x > bool 0` reports zero or one for each of its values.
820fn scalar_matching(op: BinaryOp, return_bool: bool) -> BinaryMatching {
821    BinaryMatching {
822        op,
823        return_bool,
824        labels: MatchingLabels::Ignoring(Vec::new()),
825        cardinality: Cardinality::OneToOne,
826        // A fill value fills in a match group that could miss, which a broadcast over a constant never
827        // does: the constant exists at every grid point, so there is no missing side to fill.
828        fill: FillValues::default(),
829    }
830}
831
832/// The matching a vector–vector operation records.
833///
834/// Each part is read from the modifier the query wrote, and a modifier it did not write is the
835/// default PromQL applies: every label but `__name__` matches (`ignoring` nothing), and the
836/// cardinality is one-to-one. Fill fields retain the parser's left/right values, which name the
837/// sides as written: the kernel swaps them together with the operands under `group_right`.
838///
839/// `ManyToMany` is the cardinality of a set operator, which [`binary_operation`] compiles before
840/// asking for a matching, so reaching it means the two disagree; it is reported as a shape with no
841/// node rather than panicking on a path a query cannot take today.
842fn vector_matching(binary: &BinaryExpr, op: BinaryOp) -> Result<BinaryMatching> {
843    let modifier = binary.modifier.as_ref();
844    let labels = matching_labels(modifier);
845    let cardinality = match modifier.map(|modifier| &modifier.card) {
846        None | Some(VectorMatchCardinality::OneToOne) => Cardinality::OneToOne,
847        Some(VectorMatchCardinality::ManyToOne(labels)) => {
848            Cardinality::ManyToOne(label_names(&labels.labels))
849        }
850        Some(VectorMatchCardinality::OneToMany(labels)) => {
851            Cardinality::OneToMany(label_names(&labels.labels))
852        }
853        Some(VectorMatchCardinality::ManyToMany) => {
854            return Err(not_implemented(&format!(
855                "the many-to-many matching in `{binary}`, which is the cardinality of a set \
856                 operator: it combines two vectors' series, and this node is an arithmetic or \
857                 comparison operation over values"
858            )));
859        }
860    };
861    let fill = modifier.map_or_else(FillValues::default, |modifier| FillValues {
862        lhs: modifier.fill_values.lhs,
863        rhs: modifier.fill_values.rhs,
864    });
865    Ok(BinaryMatching {
866        op,
867        return_bool: binary.return_bool(),
868        labels,
869        cardinality,
870        fill,
871    })
872}
873
874/// The set operator a PromQL token denotes, or `None` when it is not one.
875fn set_op(op: &TokenType) -> Option<SetOp> {
876    match op.id() {
877        token::T_LAND => Some(SetOp::And),
878        token::T_LOR => Some(SetOp::Or),
879        token::T_LUNLESS => Some(SetOp::Unless),
880        _ => None,
881    }
882}
883
884/// The labels `on(...)` or `ignoring(...)` names; with neither, every label but `__name__`.
885fn matching_labels(modifier: Option<&BinModifier>) -> MatchingLabels {
886    match modifier.and_then(|modifier| modifier.matching.as_ref()) {
887        None => MatchingLabels::Ignoring(Vec::new()),
888        Some(LabelModifier::Include(labels)) => MatchingLabels::On(label_names(&labels.labels)),
889        Some(LabelModifier::Exclude(labels)) => {
890            MatchingLabels::Ignoring(label_names(&labels.labels))
891        }
892    }
893}
894
895fn label_names(labels: &[String]) -> Vec<Arc<str>> {
896    labels.iter().map(|name| Arc::from(name.as_str())).collect()
897}
898
899/// The binary operator a PromQL token denotes, or `None` when there is no node for it.
900///
901/// A comparison carries `return_bool` separately, so `x > 0` and `x > bool 0` use the same
902/// operator. The node the runtime executes and the constant fold both read the operator here.
903fn binary_op(op: &TokenType) -> Option<BinaryOp> {
904    match op.id() {
905        token::T_ADD => Some(BinaryOp::Add),
906        token::T_SUB => Some(BinaryOp::Sub),
907        token::T_MUL => Some(BinaryOp::Mul),
908        token::T_DIV => Some(BinaryOp::Div),
909        token::T_MOD => Some(BinaryOp::Mod),
910        token::T_POW => Some(BinaryOp::Pow),
911        token::T_ATAN2 => Some(BinaryOp::Atan2),
912        token::T_EQLC => Some(BinaryOp::Eq),
913        token::T_NEQ => Some(BinaryOp::Ne),
914        token::T_GTR => Some(BinaryOp::Gt),
915        token::T_LSS => Some(BinaryOp::Lt),
916        token::T_GTE => Some(BinaryOp::Ge),
917        token::T_LTE => Some(BinaryOp::Le),
918        _ => None,
919    }
920}
921
922/// Compiles an aggregation into an aggregate node over the expression it groups.
923///
924/// The aggregators that fold a group's values into one value per grid point bind to an aggregate
925/// node: `sum`, `avg`, `count`, `min`, `max`, `group`, `stddev`, `stdvar` and `quantile`. The
926/// runtime validates whether the resulting tree can execute.
927///
928/// The rest of the parser's aggregates are a different shape and bind as a vector operation
929/// ([`vector_aggregate`]) rather than as a kind that would compute something else: `topk`,
930/// `bottomk`, `limitk` and `limit_ratio` select some of the input's series, so they do not report
931/// one value per group per grid point, and `count_values` writes one output label per distinct value
932/// rather than folding a group's values at all.
933///
934/// The grouping is bound in the tree's own terms, because `by` and `without` are not each other's
935/// inverse: `by(job)` keeps `job` and drops every other label, while `without(instance)` keeps every
936/// label it does not name and drops `__name__` as well, so a list of the surviving labels could not
937/// say the same thing. A bare `sum(x)` groups by no label at all, which is Prometheus's reading of
938/// "no modifier": every label is dropped, `__name__` included, and every series of the input falls
939/// into one group.
940///
941/// The stage is [`AggregateStage::Complete`], which says that every contribution to each group is in
942/// this execution's input. The module documentation says what keeping that claim costs a caller.
943fn aggregate_expr(context: &Context, aggregate: &AggregateExpr) -> Result<NativeNode> {
944    let AggregateExpr {
945        op,
946        expr,
947        param,
948        modifier,
949    } = aggregate;
950    let kind = match op.id() {
951        token::T_SUM => AggregateKind::Sum,
952        token::T_AVG => AggregateKind::Avg,
953        token::T_COUNT => AggregateKind::Count,
954        token::T_MIN => AggregateKind::Min,
955        token::T_MAX => AggregateKind::Max,
956        token::T_GROUP => AggregateKind::Group,
957        token::T_STDDEV => AggregateKind::Stddev,
958        token::T_STDVAR => AggregateKind::Stdvar,
959        token::T_QUANTILE => {
960            // `quantile` is the only one of the nine with a parameter, and the parser always gives
961            // it one: a `quantile` with no quantile written is refused before the compiler sees it.
962            // The quantile is the call's first argument, so a parameter that is not a constant is
963            // refused under that name rather than answered from a number bound too early.
964            let param = param.as_ref().ok_or_else(|| {
965                not_implemented(&format!(
966                    "the aggregate `{op}` in `{aggregate}`, which takes its quantile as its first \
967                     argument"
968                ))
969            })?;
970            AggregateKind::Quantile {
971                quantile: constant_argument(&op.to_string(), param, 0)?,
972            }
973        }
974        // A ranking aggregate keeps some of the input's series, and `count_values` writes one
975        // output label per distinct value: neither folds a group into one value per grid point, so
976        // both read the whole vector in a `Vector` node instead.
977        token::T_TOPK
978        | token::T_BOTTOMK
979        | token::T_LIMITK
980        | token::T_LIMIT_RATIO
981        | token::T_COUNT_VALUES => {
982            return vector_aggregate(context, aggregate);
983        }
984        // The parser's `aggregate_op` rule lists exactly the fourteen names above, so this arm is
985        // an operator this compiler was not taught rather than one it means to fold.
986        _ => {
987            return Err(not_implemented(&format!(
988                "the aggregate `{op}` in `{aggregate}`"
989            )));
990        }
991    };
992    let input = compile_expr(context, expr)?;
993    // What the aggregate's state carries is what its direct input answers with, so the binding is
994    // decided here, from the input's own walk, rather than from the statement's sources: an
995    // operator between the two can change the kind (`sum(count_over_time(h[5m]))` folds a float
996    // built from histograms).
997    //
998    // A kind this walk cannot name is not a float by default: the state a `sum` or `avg` keeps over
999    // a histogram is a different layout, so binding one from a guess would compute the wrong thing
1000    // for a statement whose sources carry histograms. Such a shape keeps the existing plan (the
1001    // refusal is `NotImplemented`).
1002    //
1003    // With float sources - or with no source at all - an unnameable input is still a float, and the
1004    // aggregate binds the numeric state it always did. What makes that a proof rather than a default
1005    // is that a native histogram sample can only enter a tree from a source that carries one: every
1006    // operator here passes a histogram through, reduces it to a float, or declines the shape. A
1007    // shape whose samples this walk does not describe (`clamp`, `topk`, `vector()` of a scalar) can
1008    // therefore not be holding one.
1009    let field_kind = match input.output_field_kind(context.source_kind) {
1010        Some(kind) => kind,
1011        None if context.source_kind == Some(FieldKind::Histogram) => {
1012            return Err(not_implemented(&format!(
1013                "the aggregate `{op}` in `{aggregate}`, whose input's field kind this compile cannot \
1014                 name while its sources carry native histograms: the aggregate's state depends on \
1015                 whether the input carries floats or histograms"
1016            )));
1017        }
1018        None => FieldKind::Float,
1019    };
1020    // A complete aggregate folds each group's values and reports them on its input's grid, one value
1021    // per input field, so its layout is its input's.
1022    let output = input.output.clone();
1023    Ok(NativeNode {
1024        expr: NativeExpr::Aggregate {
1025            input: Box::new(input),
1026            op: BoundAggregate {
1027                kind,
1028                group: grouping(modifier.as_ref()),
1029                stage: AggregateStage::Complete,
1030                field_kind,
1031            },
1032        },
1033        output,
1034    })
1035}
1036
1037/// Binds `topk`, `bottomk`, `limitk`, `limit_ratio` or `count_values` as a vector operation over
1038/// the expression it aggregates.
1039///
1040/// The parser gives each of them its parameter: a number for the first four, folded to the constant
1041/// it means like a `quantile`, and a string for `count_values`, the label it writes the value to.
1042fn vector_aggregate(context: &Context, aggregate: &AggregateExpr) -> Result<NativeNode> {
1043    let AggregateExpr {
1044        op,
1045        expr,
1046        param,
1047        modifier,
1048    } = aggregate;
1049    let name = op.to_string();
1050    let param = param.as_ref().ok_or_else(|| {
1051        not_implemented(&format!(
1052            "the aggregate `{op}` in `{aggregate}`, which takes a parameter as its first argument"
1053        ))
1054    })?;
1055    let group = grouping(modifier.as_ref());
1056    if matches!(op.id(), token::T_TOPK | token::T_BOTTOMK) && constant_value(param).is_none() {
1057        let input = compile_expr(context, expr)?;
1058        let output = input.output.clone();
1059        let parameter = compile_expr(context, param)?;
1060        return Ok(NativeNode {
1061            expr: NativeExpr::ParameterizedTopK {
1062                input: Box::new(input),
1063                op: BoundVectorOp::TopK {
1064                    k: 0.0,
1065                    top: op.id() == token::T_TOPK,
1066                    group,
1067                },
1068                parameter: Box::new(parameter),
1069            },
1070            output,
1071        });
1072    }
1073    let bound = match op.id() {
1074        token::T_TOPK | token::T_BOTTOMK => BoundVectorOp::TopK {
1075            k: constant_argument(&name, param, 0)?,
1076            top: op.id() == token::T_TOPK,
1077            group,
1078        },
1079        token::T_LIMITK => BoundVectorOp::LimitK {
1080            k: constant_argument(&name, param, 0)?,
1081            group,
1082        },
1083        // `limit_ratio` keeps whole series by their label hash, so a grouping changes nothing.
1084        token::T_LIMIT_RATIO => BoundVectorOp::LimitRatio {
1085            ratio: constant_argument(&name, param, 0)?,
1086        },
1087        _ => {
1088            let PromExpr::StringLiteral(StringLiteral { val }) = unparen(param) else {
1089                return Err(not_implemented(&format!(
1090                    "the aggregate `{op}` in `{aggregate}`, whose label `{param}` is not a string \
1091                     literal"
1092                )));
1093            };
1094            BoundVectorOp::CountValues {
1095                label: Arc::from(val.as_str()),
1096                group,
1097            }
1098        }
1099    };
1100    vector_call(context, &name, bound, expr)
1101}
1102
1103/// How a `by` or `without` modifier identifies a group, in the tree's own terms.
1104///
1105/// The labels keep the order they were written in: a grouping is a set, and the tree records the
1106/// query rather than a key it derived from one.
1107fn grouping(modifier: Option<&LabelModifier>) -> Grouping {
1108    /// The written labels, as the tree stores them.
1109    fn labels(labels: &[String]) -> Arc<[Arc<str>]> {
1110        labels
1111            .iter()
1112            .map(|label| Arc::<str>::from(label.as_str()))
1113            .collect()
1114    }
1115    match modifier {
1116        // No modifier and `by()` ask for the same grouping: no label is kept, so every series of the
1117        // input falls into one group.
1118        None => Grouping::By(Arc::new([])),
1119        Some(LabelModifier::Include(by)) => Grouping::By(labels(&by.labels)),
1120        Some(LabelModifier::Exclude(without)) => Grouping::Without(labels(&without.labels)),
1121    }
1122}
1123
1124/// Compiles `timestamp`, projecting selected source times for a selector and evaluation times for
1125/// an already evaluated vector.
1126fn timestamp_call(context: &Context, args: &[Box<PromExpr>]) -> Result<NativeNode> {
1127    if args.len() != 1 {
1128        return Err(not_implemented("timestamp expects one argument"));
1129    }
1130    let argument = unparen(&args[0]);
1131    if argument.value_type() != ValueType::Vector {
1132        return Err(not_implemented("timestamp argument is not a vector"));
1133    }
1134    if let PromExpr::VectorSelector(selector) = argument {
1135        return instant_selection_of(context, selector, InstantValue::Timestamp);
1136    }
1137    let input = compile_expr(context, argument)?;
1138    let NativeType::Samples(schema) = &input.output else {
1139        return Err(not_implemented("timestamp argument is not a vector"));
1140    };
1141    if schema.fields.len() != 1 {
1142        return Err(not_implemented(
1143            "timestamp() over a multi-value input is not supported natively",
1144        ));
1145    }
1146    let output = input.output.clone();
1147    Ok(NativeNode {
1148        expr: NativeExpr::Timestamp {
1149            input: Box::new(input),
1150        },
1151        output,
1152    })
1153}
1154
1155/// Compiles `info(v[, {selector}])` as its base `v` and the instant selection of the info series it
1156/// reads.
1157///
1158/// The info series are selected the way Prometheus' `fetchInfoSeries` and `evalSeries` select
1159/// them: by the info metric's name and the data matchers, at the reference time the selectors of
1160/// `v` share ([`info_input`]), with the statement's lookback. Which of them a base series matches by
1161/// its identifying labels is the kernel's.
1162fn info_call(context: &Context, args: &[Box<PromExpr>]) -> Result<NativeNode> {
1163    let InfoInput { selector, kernel } = info_input(context.stmt, args)?;
1164    let base = compile_expr(context, &args[0])?;
1165    if base
1166        .output
1167        .samples()
1168        .is_none_or(|schema| schema.eval_grid.is_none())
1169    {
1170        return Err(DataFusionError::Internal(format!(
1171            "info's first argument `{}` compiled to something other than an evaluated vector: the \
1172             parser only accepts a vector there",
1173            args[0]
1174        )));
1175    }
1176    let info = instant_selection_of(context, &selector, InstantValue::InfoTimestamp)?;
1177    let fields = info
1178        .output
1179        .samples()
1180        .map_or(0, |schema| schema.fields.len());
1181    // Prometheus reads one sample per info series and point, and the existing planner has no
1182    // `info` to follow for several fields.
1183    if fields != 1 {
1184        return Err(not_implemented(&format!(
1185            "info over the info metric `{selector}` with {fields} fields: an info series is read as \
1186             one field"
1187        )));
1188    }
1189    let output = base.output.clone();
1190    Ok(NativeNode {
1191        expr: NativeExpr::Info {
1192            base: Box::new(base),
1193            info: Box::new(info),
1194            selector: kernel,
1195        },
1196        output,
1197    })
1198}
1199
1200/// The info series `info(v[, {selector}])` reads, as a selector, and the selector its kernel
1201/// combines by.
1202pub(crate) struct InfoInput {
1203    /// The info metric with the data matchers, at the reference time the selectors of `v` share.
1204    pub selector: VectorSelector,
1205    pub kernel: InfoSelector,
1206}
1207
1208/// Splits the arguments of `info` into the selector of its info series and the kernel's selector.
1209///
1210/// The compiler binds the selector as the call's last input and the planner prepares a scan for it
1211/// at the same position, so both read it here. One info metric is one table, so the name has to be
1212/// `target_info` (no name matcher) or one `__name__="..."`: a regular expression or a negative
1213/// matcher can select several tables. `__field__`, `__schema__` and `__database__` choose what a
1214/// selector reads rather than match a label, which Prometheus would read them as, so they are
1215/// refused too.
1216pub(crate) fn info_input(stmt: &EvalStmt, args: &[Box<PromExpr>]) -> Result<InfoInput> {
1217    let (base, labels) = match args {
1218        [base] => (base, None),
1219        [base, labels] => (base, Some(labels)),
1220        _ => {
1221            return Err(not_implemented(&format!(
1222                "a call to `info` with {} argument(s)",
1223                args.len()
1224            )));
1225        }
1226    };
1227    let matchers: &[Matcher] = match labels.map(|labels| labels.as_ref()) {
1228        None => &[],
1229        Some(PromExpr::VectorSelector(VectorSelector {
1230            name: None,
1231            matchers,
1232            offset: None,
1233            at: None,
1234        })) if matchers.or_matchers.is_empty() => &matchers.matchers,
1235        Some(other) => {
1236            return Err(not_implemented(&format!(
1237                "`info` whose second argument `{other}` is not one label selector without a name \
1238                 or modifiers"
1239            )));
1240        }
1241    };
1242    let (names, data): (Vec<&Matcher>, Vec<&Matcher>) = matchers
1243        .iter()
1244        .partition(|matcher| matcher.name == "__name__");
1245    let metric = match names.as_slice() {
1246        [] => "target_info".to_string(),
1247        [name] if name.op == ParserMatchOp::Equal => name.value.clone(),
1248        _ => {
1249            return Err(not_implemented(
1250                "`info` over the info metrics a regular expression, a negative matcher or several \
1251                 `__name__` matchers select, which can be several tables",
1252            ));
1253        }
1254    };
1255    if data.iter().any(|matcher| {
1256        matches!(
1257            matcher.name.as_str(),
1258            "__field__" | "__schema__" | "__database__"
1259        )
1260    }) {
1261        return Err(not_implemented(
1262            "`info` with a `__field__`, `__schema__` or `__database__` matcher, which selects \
1263             what is read rather than a data label",
1264        ));
1265    }
1266    let (at, offset_ms) = info_reference(stmt, base)?;
1267    let offset = match offset_ms {
1268        0 => None,
1269        ms if ms > 0 => Some(Offset::Pos(Duration::from_millis(ms.unsigned_abs()))),
1270        ms => Some(Offset::Neg(Duration::from_millis(ms.unsigned_abs()))),
1271    };
1272    let kernel = InfoSelector {
1273        name_matchers: names
1274            .iter()
1275            .map(|matcher| (match_op(&matcher.op), Arc::from(matcher.value.as_str())))
1276            .collect(),
1277        data_labels: data
1278            .iter()
1279            .map(|matcher| Arc::from(matcher.name.as_str()))
1280            .collect(),
1281        keep_unmatched: data.iter().all(|matcher| matcher.is_match("")),
1282    };
1283    Ok(InfoInput {
1284        selector: VectorSelector {
1285            name: Some(metric),
1286            matchers: Matchers::new(data.into_iter().cloned().collect()),
1287            offset,
1288            at,
1289        },
1290        kernel,
1291    })
1292}
1293
1294/// The `@` anchor and offset the info series are selected at: those of the first selector of
1295/// `expr` when every vector-producing path of it reaches a selector with the same effective
1296/// reference time, and none otherwise, as Prometheus `infoSeriesSelectTimestampAndOffset` decides.
1297///
1298/// A selector inside subqueries adds their offsets until one of them anchors it with `@`. A path
1299/// that produces a vector without a selector, such as `vector(1)`, is evaluated at the step itself,
1300/// so it leaves no shared reference.
1301fn info_reference(stmt: &EvalStmt, expr: &PromExpr) -> Result<(Option<AtModifier>, i64)> {
1302    #[derive(Default)]
1303    struct Walk {
1304        /// The first selector's anchor, its resolved time and its offset.
1305        first: Option<(Option<AtModifier>, Option<i64>, i64)>,
1306        uniform: bool,
1307        reference_free: bool,
1308    }
1309
1310    fn inspect<'a>(
1311        stmt: &EvalStmt,
1312        expr: &'a PromExpr,
1313        subqueries: &mut Vec<&'a SubqueryExpr>,
1314        walk: &mut Walk,
1315    ) -> Result<bool> {
1316        if !matches!(expr.value_type(), ValueType::Vector | ValueType::Matrix) {
1317            return Ok(false);
1318        }
1319        let selector = match expr {
1320            PromExpr::VectorSelector(selector) => Some(selector),
1321            PromExpr::MatrixSelector(MatrixSelector { vs, .. }) => Some(vs),
1322            _ => None,
1323        };
1324        if let Some(selector) = selector {
1325            let mut at = selector.at.clone();
1326            let mut offset = selector_offset_ms(&selector.offset)?;
1327            for subquery in subqueries.iter().rev() {
1328                if at.is_some() {
1329                    break;
1330                }
1331                offset = offset
1332                    .checked_add(selector_offset_ms(&subquery.offset)?)
1333                    .ok_or_else(|| DataFusionError::Plan("selector offset overflows".into()))?;
1334                at = subquery.at.clone();
1335            }
1336            let at_ms = selector_anchor_ms(&at, stmt)?;
1337            match &walk.first {
1338                None => walk.first = Some((at, at_ms, offset)),
1339                Some((_, first_at, first_offset)) => {
1340                    let same = match (first_at, at_ms) {
1341                        (None, None) => *first_offset == offset,
1342                        (Some(first_at), Some(at)) => {
1343                            i128::from(*first_at) - i128::from(*first_offset)
1344                                == i128::from(at) - i128::from(offset)
1345                        }
1346                        _ => false,
1347                    };
1348                    walk.uniform &= same;
1349                }
1350            }
1351            return Ok(true);
1352        }
1353        let children: Vec<&PromExpr> = match expr {
1354            PromExpr::Paren(paren) => vec![&paren.expr],
1355            PromExpr::Unary(unary) => vec![&unary.expr],
1356            PromExpr::Binary(binary) => vec![&binary.lhs, &binary.rhs],
1357            PromExpr::Aggregate(aggregate) => aggregate
1358                .param
1359                .iter()
1360                .chain([&aggregate.expr])
1361                .map(|child| child.as_ref())
1362                .collect(),
1363            // The second argument of a nested `info` is selector syntax, not a vector it evaluates.
1364            PromExpr::Call(call) if call.func.name == "info" => call
1365                .args
1366                .args
1367                .iter()
1368                .take(1)
1369                .map(|arg| arg.as_ref())
1370                .collect(),
1371            PromExpr::Call(call) => call.args.args.iter().map(|arg| arg.as_ref()).collect(),
1372            PromExpr::Subquery(subquery) => {
1373                subqueries.push(subquery);
1374                let found = inspect(stmt, &subquery.expr, subqueries, walk);
1375                subqueries.pop();
1376                let found = found?;
1377                walk.reference_free |= !found;
1378                return Ok(found);
1379            }
1380            other => {
1381                return Err(not_implemented(&format!(
1382                    "`info` over `{other}`, whose reference time is not derived here"
1383                )));
1384            }
1385        };
1386        let mut found = false;
1387        for child in children {
1388            found |= inspect(stmt, child, subqueries, walk)?;
1389        }
1390        walk.reference_free |= !found;
1391        Ok(found)
1392    }
1393
1394    let mut walk = Walk {
1395        uniform: true,
1396        ..Default::default()
1397    };
1398    inspect(stmt, expr, &mut Vec::new(), &mut walk)?;
1399    match walk.first {
1400        Some((at, _, offset)) if walk.uniform && !walk.reference_free => Ok((at, offset)),
1401        _ => Ok((None, 0)),
1402    }
1403}
1404
1405fn match_op(op: &ParserMatchOp) -> MatchOp {
1406    match op {
1407        ParserMatchOp::Equal => MatchOp::Equal,
1408        ParserMatchOp::NotEqual => MatchOp::NotEqual,
1409        ParserMatchOp::Re(_) => MatchOp::Regex,
1410        ParserMatchOp::NotRe(_) => MatchOp::NotRegex,
1411    }
1412}
1413
1414/// Compiles a range, pointwise, histogram or label function call.
1415///
1416/// The name lists are disjoint, and a range function is decided first because it binds its own
1417/// window rather than its argument's value. A name in neither list is refused here, which is where
1418/// the difference between "this compiler cannot fold this function" and "this name means nothing"
1419/// is still visible.
1420fn compile_call(context: &Context, call: &Call) -> Result<NativeNode> {
1421    if call.func.name == "timestamp" {
1422        return timestamp_call(context, &call.args.args);
1423    }
1424    if call.func.name == "info" {
1425        return info_call(context, &call.args.args);
1426    }
1427    // `absent_over_time` reads a matrix where `absent` reads a vector, so it cannot ride the vector
1428    // path below: the operation it binds is `absent`'s own, over a presence read of the window.
1429    if call.func.name == ABSENT_OVER_TIME {
1430        return absent_over_time_call(context, &call.args.args);
1431    }
1432    let Call { func, args } = call;
1433    if let Some(node) = scalar_call(context, func.name, &args.args)? {
1434        return Ok(node);
1435    }
1436    if let Some(signature) = range_signature(func.name) {
1437        return window_call(context, func.name, signature, &args.args);
1438    }
1439    if let Some(node) = parameterized_histogram_call(context, func.name, &args.args)? {
1440        return Ok(node);
1441    }
1442    if let Some((op, vector)) = vector_op(func.name, &args.args)? {
1443        return vector_call(context, func.name, op, vector);
1444    }
1445    if let Some(node) = scalar_function_call(context, func.name, &args.args)? {
1446        return Ok(node);
1447    }
1448    // The name is looked up before the call's arguments are read, so a name this compiler has no
1449    // kernel for is refused as such whichever arguments it was given, and the rejection names the
1450    // name rather than describing a vector it never wrote. `pi()` does not reach here: it is a
1451    // constant the statement itself decides, so it already folded in `compile_expr`.
1452    if let Some(node) = parameterized_call(context, func.name, &args.args)? {
1453        return Ok(node);
1454    }
1455    if let Some((op, vector)) = math_op(func.name, &args.args)? {
1456        return map_call(context, func.name, MapOp::Math(op), vector);
1457    }
1458    if let Some(function) = histogram_function(func.name) {
1459        let [vector] = args.args.as_slice() else {
1460            return Err(not_implemented(&format!(
1461                "a call to `{}` with {} argument(s), where it takes its vector",
1462                func.name,
1463                args.args.len()
1464            )));
1465        };
1466        return map_call(context, func.name, MapOp::Histogram(function), vector);
1467    }
1468    if let Some((rewrite, vector)) = label_rewrite(func.name, &args.args)? {
1469        return map_call(context, func.name, MapOp::Label(Arc::new(rewrite)), vector);
1470    }
1471    Err(not_implemented(&format!(
1472        "a call to `{}`, which has no native kernel",
1473        func.name
1474    )))
1475}
1476
1477/// Binds `time()`, `vector(s)` and a date function called without an argument, or
1478/// returns `None` when the call is none of them.
1479///
1480/// A date function without an argument is `f(vector(time()))` in Prometheus, but it reads the
1481/// evaluation timestamp truncated to whole seconds rather than the float `time()` reports, so it is
1482/// bound as the evaluation time's own date and then handed on as a vector.
1483fn scalar_call(
1484    context: &Context,
1485    name: &str,
1486    args: &[Box<PromExpr>],
1487) -> Result<Option<NativeNode>> {
1488    let grid = || Arc::clone(&context.grid);
1489    let eval_time = |date| NativeNode {
1490        expr: NativeExpr::EvalTime { date },
1491        output: NativeType::Scalar(grid()),
1492    };
1493    let node = match (name, args) {
1494        ("time", []) => eval_time(None),
1495        ("vector", [scalar]) => vector_of(
1496            compile_expr(context, scalar)?,
1497            &grid(),
1498            &context.value_field,
1499        ),
1500        ("scalar", [vector]) => {
1501            if vector.value_type() != ValueType::Vector {
1502                return Err(not_implemented("scalar() requires a vector argument"));
1503            }
1504            let input = compile_expr(context, vector)?;
1505            let NativeType::Samples(schema) = &input.output else {
1506                return Err(not_implemented("scalar() requires an evaluated vector"));
1507            };
1508            let Some(input_grid) = schema.eval_grid.clone() else {
1509                return Err(not_implemented("scalar() requires an evaluated vector"));
1510            };
1511            NativeNode {
1512                expr: NativeExpr::ScalarOf {
1513                    input: Box::new(input),
1514                },
1515                output: NativeType::Scalar(input_grid),
1516            }
1517        }
1518        (name, []) => match math_signature(name) {
1519            Some(MathSignature::Unary(MathOp::Date(date))) => {
1520                vector_of(eval_time(Some(date)), &grid(), &context.value_field)
1521            }
1522            _ => return Ok(None),
1523        },
1524        _ => return Ok(None),
1525    };
1526    Ok(Some(node))
1527}
1528
1529/// Binds `max_of(a, b)` or `min_of(a, b)`, whose arguments are both scalars, or returns `None` for
1530/// any other call.
1531///
1532/// Prometheus types both as `(scalar, scalar) -> scalar`, so what the call wrote is two scalar
1533/// expressions rather than a vector and its parameters: the first argument is the map's input and
1534/// the second is its one parameter, and the answer is a scalar on the grid they are evaluated on. A
1535/// constant argument is bound as the number it folds to ([`compile_expr`]); as the input, that
1536/// number is the one chunk the map materializes, so a call of two constants reads no input at all.
1537/// A vector argument is refused here: it is not a shape the kernel could compute, and a function of
1538/// two scalars has no vector form to fold.
1539fn scalar_function_call(
1540    context: &Context,
1541    name: &str,
1542    args: &[Box<PromExpr>],
1543) -> Result<Option<NativeNode>> {
1544    let op = match name {
1545        "max_of" => ParameterizedOp::MaxOf,
1546        "min_of" => ParameterizedOp::MinOf,
1547        _ => return Ok(None),
1548    };
1549    let [left, right] = args else {
1550        return Err(not_implemented(&format!(
1551            "a call to `{name}` with {} argument(s), where it takes two scalars",
1552            args.len()
1553        )));
1554    };
1555    for argument in [left, right] {
1556        if argument.value_type() != ValueType::Scalar {
1557            return Err(not_implemented(&format!(
1558                "a call to `{name}` whose argument `{argument}` is a {}, where the function takes \
1559                 scalars",
1560                argument.value_type()
1561            )));
1562        }
1563    }
1564    let input = compile_expr(context, left)?;
1565    let output_grid = match &input.output {
1566        NativeType::Scalar(grid) => Arc::clone(grid),
1567        // A scalar expression compiles to a scalar, so this is a backstop rather than a shape a
1568        // statement reaches.
1569        _ => {
1570            return Err(not_implemented(&format!(
1571                "a call to `{name}` whose argument `{left}` does not evaluate to a scalar"
1572            )));
1573        }
1574    };
1575    let parameter = compile_expr(context, right)?;
1576    match &parameter.output {
1577        NativeType::Scalar(grid) if grid.spec() == output_grid.spec() => {}
1578        NativeType::Scalar(_) => {
1579            return Err(not_implemented(&format!(
1580                "a call to `{name}` whose arguments are evaluated on grids that differ"
1581            )));
1582        }
1583        _ => {
1584            return Err(not_implemented(&format!(
1585                "a call to `{name}` whose argument `{right}` does not evaluate to a scalar"
1586            )));
1587        }
1588    }
1589    Ok(Some(NativeNode {
1590        expr: NativeExpr::ParameterizedMap {
1591            input: Box::new(input),
1592            op,
1593            parameters: vec![parameter],
1594        },
1595        output: NativeType::Scalar(output_grid),
1596    }))
1597}
1598
1599/// Binds `round`, `clamp`, `clamp_min` or `clamp_max` whose parameters are not all constants, or
1600/// returns `None` for any other call. Prometheus reads each parameter at every step, so each one is
1601/// bound as the scalar node it compiles to; with constant parameters the call is a [`MathOp`].
1602fn parameterized_call(
1603    context: &Context,
1604    name: &str,
1605    args: &[Box<PromExpr>],
1606) -> Result<Option<NativeNode>> {
1607    let op = match name {
1608        "round" => ParameterizedOp::Round,
1609        "clamp" => ParameterizedOp::Clamp,
1610        "clamp_min" => ParameterizedOp::ClampMin,
1611        "clamp_max" => ParameterizedOp::ClampMax,
1612        _ => return Ok(None),
1613    };
1614    let Some((vector, parameters)) = args.split_first() else {
1615        return Ok(None);
1616    };
1617    if parameters.len() != op.arity()
1618        || parameters
1619            .iter()
1620            .all(|parameter| constant_value(parameter).is_some())
1621    {
1622        return Ok(None);
1623    }
1624    if vector.value_type() != ValueType::Vector {
1625        return Err(not_implemented(&format!(
1626            "a call to `{name}` whose first argument is `{vector}`, which is a {}, where the \
1627             function takes a vector",
1628            vector.value_type()
1629        )));
1630    }
1631    let input = compile_expr(context, vector)?;
1632    let parameters = parameters
1633        .iter()
1634        .map(|parameter| compile_expr(context, parameter))
1635        .collect::<Result<Vec<_>>>()?;
1636    let output = input.output.clone();
1637    Ok(Some(NativeNode {
1638        expr: NativeExpr::ParameterizedMap {
1639            input: Box::new(input),
1640            op,
1641            parameters,
1642        },
1643        output,
1644    }))
1645}
1646
1647/// `vector(s)`: the scalar `input` as one series without labels, under one value field.
1648fn vector_of(input: NativeNode, grid: &Arc<EvalGrid>, value_field: &str) -> NativeNode {
1649    NativeNode {
1650        expr: NativeExpr::VectorOf {
1651            input: Box::new(input),
1652        },
1653        output: NativeType::Samples(Arc::new(SeriesSchema {
1654            fields: Arc::from([FieldSpec {
1655                name: Arc::from(value_field),
1656            }]),
1657            eval_grid: Some(Arc::clone(grid)),
1658        })),
1659    }
1660}
1661
1662/// The field `vector(s)` reports its value under: a scalar names no column, so it is the planner's
1663/// default value column.
1664const VECTOR_FIELD: &str = "value";
1665
1666/// Binds a range function over the matrix it is given, and the window that matrix opens.
1667///
1668/// Where the matrix sits is the signature's, not a convention: `quantile_over_time(0.9, x[5m])` writes
1669/// its constant before the matrix, while `predict_linear(x[5m], 300)` and
1670/// `double_exponential_smoothing(x[5m], 0.5, 0.1)` write theirs after it, and a function with no
1671/// constants at all reads the matrix first. [`RangeSignature::selector_index`] is that position, and
1672/// everything else the call wrote is a constant — which keeps the position it was written at, so a
1673/// rejection names the argument the query wrote rather than the constant's offset among the constants.
1674///
1675/// The matrix is either shape: a range selector, which reads raw samples, or a subquery, which
1676/// evaluates its own expression on a grid of its own.
1677fn window_call(
1678    context: &Context,
1679    name: &str,
1680    signature: RangeSignature,
1681    args: &[Box<PromExpr>],
1682) -> Result<NativeNode> {
1683    // The count is the signature's, so the rejection names what this function takes rather than
1684    // what one argument happens to be.
1685    let expected = signature.arity();
1686    if args.len() != expected {
1687        return Err(not_implemented(&format!(
1688            "a call to `{name}` with {} argument(s), where it takes {expected}: {}",
1689            args.len(),
1690            signature.arguments()
1691        )));
1692    }
1693    // The matrix sits where the signature says it does, and everything else is a constant. Reading it
1694    // by position rather than by "the last argument" is what lets `predict_linear(x[5m], 300)` and
1695    // `quantile_over_time(0.9, x[5m])` share one path.
1696    let selector_index = signature.selector_index();
1697    // The selector stays in its original argument position for signature binding, while either
1698    // matrix form can provide the samples folded by the range function.
1699    let argument = &args[selector_index];
1700    let function = signature.bind(name, args)?;
1701    match unparen(argument) {
1702        PromExpr::MatrixSelector(MatrixSelector { vs, range }) => {
1703            window_selection(context, function, vs, range)
1704        }
1705        PromExpr::Subquery(subquery) => subquery_window(context, name, function, subquery),
1706        other => Err(not_implemented(&format!(
1707            "a call to `{name}` whose matrix is `{other}`, where it has to be a range \
1708             selector like `x[5m]` or a subquery like `x[5m:1m]`"
1709        ))),
1710    }
1711}
1712
1713/// Wraps `op` over the value of `vector`, which is the first argument of a math, native histogram
1714/// or label function.
1715///
1716/// The output is the input's own type: a pointwise function moves no value to another grid point
1717/// and reports one value per field it was given, so the map's schema is the input's allocation
1718/// rather than a copy that merely agrees with it. [`NativeTree::validate`] does not require that
1719/// sharing: it compares the map's grid with its input's by [`EvalGrid::spec`] and its field count
1720/// with its input's, so a map that allocated an equal grid of its own would validate the same way.
1721/// The only comparison by identity is an input node's, whose output has to be the very binding it
1722/// was bound to.
1723fn map_call(context: &Context, name: &str, op: MapOp, vector: &PromExpr) -> Result<NativeNode> {
1724    // A map is pointwise over a vector, so the function's first argument has to be one. The parser
1725    // checks the same thing and the tree's validation checks the compiled input's type again, but
1726    // neither can name the argument the client wrote: this is the check that can.
1727    if vector.value_type() != ValueType::Vector {
1728        return Err(not_implemented(&format!(
1729            "a call to `{name}` whose first argument is `{vector}`, which is a {}, where the \
1730             function takes a vector",
1731            vector.value_type()
1732        )));
1733    }
1734    let input = compile_expr(context, vector)?;
1735    let output = input.output.clone();
1736    Ok(NativeNode {
1737        expr: NativeExpr::Map {
1738            input: Box::new(input),
1739            op: BoundMap {
1740                ops: Arc::from([op]),
1741            },
1742        },
1743        output,
1744    })
1745}
1746
1747/// Wraps the vector operation `op` over the value of `vector`, which keeps its type as a map does.
1748fn vector_call(
1749    context: &Context,
1750    name: &str,
1751    op: BoundVectorOp,
1752    vector: &PromExpr,
1753) -> Result<NativeNode> {
1754    if vector.value_type() != ValueType::Vector {
1755        return Err(not_implemented(&format!(
1756            "a call to `{name}` whose vector argument is `{vector}`, which is a {}, where the \
1757             function takes a vector",
1758            vector.value_type()
1759        )));
1760    }
1761    let input = compile_expr(context, vector)?;
1762    let output = input.output.clone();
1763    Ok(NativeNode {
1764        expr: NativeExpr::Vector {
1765            input: Box::new(input),
1766            op,
1767        },
1768        output,
1769    })
1770}
1771
1772/// Compiles a classic histogram call with at least one varying scalar argument.
1773fn parameterized_histogram_call(
1774    context: &Context,
1775    name: &str,
1776    arguments: &[Box<PromExpr>],
1777) -> Result<Option<NativeNode>> {
1778    if !matches!(name, "histogram_quantile" | "histogram_fraction") {
1779        return Ok(None);
1780    }
1781    let Some((vector, args)) = arguments.split_last() else {
1782        return Ok(None);
1783    };
1784    let expected = if name == "histogram_quantile" { 1 } else { 2 };
1785    if args.len() != expected || args.iter().all(|arg| constant_value(arg).is_some()) {
1786        return Ok(None);
1787    }
1788    if vector.value_type() != ValueType::Vector {
1789        return Err(not_implemented(&format!(
1790            "a call to `{name}` whose vector argument is `{vector}` is not a vector"
1791        )));
1792    }
1793    let function = if name == "histogram_quantile" {
1794        HistogramFunction::Quantile(
1795            args.first()
1796                .and_then(|arg| constant_value(arg))
1797                .unwrap_or(0.0),
1798        )
1799    } else {
1800        HistogramFunction::Fraction {
1801            lower: args
1802                .first()
1803                .and_then(|arg| constant_value(arg))
1804                .unwrap_or(0.0),
1805            upper: args
1806                .get(1)
1807                .and_then(|arg| constant_value(arg))
1808                .unwrap_or(0.0),
1809        }
1810    };
1811    let input = compile_expr(context, vector)?;
1812    let output = input.output.clone();
1813    let parameters = args
1814        .iter()
1815        .map(|arg| compile_expr(context, arg))
1816        .collect::<Result<Vec<_>>>()?;
1817    Ok(Some(NativeNode {
1818        expr: NativeExpr::ParameterizedHistogram {
1819            input: Box::new(input),
1820            op: BoundVectorOp::Histogram(function),
1821            parameters,
1822        },
1823        output,
1824    }))
1825}
1826
1827/// The PromQL name of `absent_over_time`, which is not a range function here: it reads a matrix but
1828/// answers with `absent`'s vector operation rather than with one value per series.
1829const ABSENT_OVER_TIME: &str = "absent_over_time";
1830
1831/// The range function `absent_over_time` folds a window with, to learn whether a series has a sample
1832/// in it.
1833///
1834/// `absent` answers at every point its input holds no series at, so the matrix has to become one
1835/// series per series holding a sample: a range function at all, rather than a value no series
1836/// states. Which range function is therefore a question of which points a window reports, and
1837/// `present_over_time` and `last_over_time` report the same ones — a window with at least one
1838/// sample. The name is what separates them: `present_over_time` drops the metric name, and a
1839/// selector written without one is discovered as one source per metric, so two metrics carrying the
1840/// same ordinary labels would arrive at the fold as one label set. The window refuses two values of
1841/// one label set at one point, because everything above it reads them as one series: the query
1842/// would fail where Prometheus answers with the empty vector. Keeping the name keeps those two
1843/// series apart, and `absent` reads presence alone, so the value this fold computes is not part of
1844/// the answer.
1845const PRESENCE_FOLD: RangeFunction = RangeFunction::LastOverTime;
1846
1847/// Binds `absent_over_time(m[d])` into `absent`'s own vector operation, over a presence read of the
1848/// window.
1849///
1850/// Both halves are `absent`'s: the labels come from the matrix selector's matchers exactly as
1851/// `absent` derives them from a vector selector's, and the operation tests whether its input holds
1852/// a series at each grid point. What differs is only where that input comes from — a matrix folds a
1853/// window rather than selecting an instant — which is why the call is bound here and not by
1854/// [`vector_call`]: `absent_over_time` reads a matrix, and nothing in it is a vector expression the
1855/// recursion could compile.
1856///
1857/// The existing plan answers this call per series with a UDF, which needs a metric name to read a
1858/// table from; a selector written without one names its metrics only by the labels that pick them,
1859/// which is exactly the shape `absent_over_time` is asked for when nothing matches.
1860fn absent_over_time_call(context: &Context, arguments: &[Box<PromExpr>]) -> Result<NativeNode> {
1861    let [matrix] = arguments else {
1862        return Err(not_implemented(&format!(
1863            "a call to `{ABSENT_OVER_TIME}` with {} argument(s), where it takes one matrix",
1864            arguments.len()
1865        )));
1866    };
1867    let labels = absent_labels_of(matrix)?;
1868    let input = match unparen(matrix) {
1869        PromExpr::MatrixSelector(MatrixSelector { vs, range }) => {
1870            window_selection(context, PRESENCE_FOLD, vs, range)?
1871        }
1872        PromExpr::Subquery(subquery) => {
1873            subquery_window(context, ABSENT_OVER_TIME, PRESENCE_FOLD, subquery)?
1874        }
1875        other => {
1876            return Err(not_implemented(&format!(
1877                "a call to `{ABSENT_OVER_TIME}` whose matrix is `{other}`, where it has to be a \
1878                 range selector like `x[5m]` or a subquery like `x[5m:1m]`"
1879            )));
1880        }
1881    };
1882    let output = input.output.clone();
1883    Ok(NativeNode {
1884        expr: NativeExpr::Vector {
1885            input: Box::new(input),
1886            op: BoundVectorOp::Absent { labels },
1887        },
1888        output,
1889    })
1890}
1891
1892/// The vector operation a sort, `absent` or a classic histogram function binds, and the vector it reads,
1893/// or `None` when `name` is none of them.
1894fn vector_op<'a>(
1895    name: &str,
1896    arguments: &'a [Box<PromExpr>],
1897) -> Result<Option<(BoundVectorOp, &'a PromExpr)>> {
1898    let order = match name {
1899        "sort" => Some(SortOrder::Asc),
1900        "sort_desc" => Some(SortOrder::Desc),
1901        "sort_by_label" | "sort_by_label_desc" => None,
1902        "histogram_quantile" | "histogram_fraction" => {
1903            let Some((vector, constants)) = arguments.split_last() else {
1904                return Err(not_implemented(&format!(
1905                    "a call to `{name}` with no argument"
1906                )));
1907            };
1908            let function = match constants {
1909                [quantile] if name == "histogram_quantile" => {
1910                    HistogramFunction::Quantile(constant_argument(name, quantile, 0)?)
1911                }
1912                [lower, upper] if name == "histogram_fraction" => HistogramFunction::Fraction {
1913                    lower: constant_argument(name, lower, 0)?,
1914                    upper: constant_argument(name, upper, 1)?,
1915                },
1916                _ => {
1917                    return Err(not_implemented(&format!(
1918                        "a call to `{name}` with {} argument(s)",
1919                        arguments.len()
1920                    )));
1921                }
1922            };
1923            return Ok(Some((BoundVectorOp::Histogram(function), vector)));
1924        }
1925        "absent" => {
1926            let [vector] = arguments else {
1927                return Err(not_implemented(&format!(
1928                    "a call to `absent` with {} argument(s)",
1929                    arguments.len()
1930                )));
1931            };
1932            let labels = absent_labels_of(vector)?;
1933            return Ok(Some((BoundVectorOp::Absent { labels }, vector)));
1934        }
1935        _ => return Ok(None),
1936    };
1937    let Some((vector, strings)) = arguments.split_first() else {
1938        return Err(not_implemented(&format!(
1939            "a call to `{name}` with no argument"
1940        )));
1941    };
1942    let order = match order {
1943        Some(order) if strings.is_empty() => order,
1944        Some(_) => {
1945            return Err(not_implemented(&format!(
1946                "a call to `{name}` with {} argument(s)",
1947                arguments.len()
1948            )));
1949        }
1950        None => {
1951            let labels = strings
1952                .iter()
1953                .map(|argument| match unparen(argument) {
1954                    PromExpr::StringLiteral(StringLiteral { val }) => Ok(Arc::from(val.as_str())),
1955                    other => Err(not_implemented(&format!(
1956                        "a call to `{name}` whose argument `{other}` is not a string literal"
1957                    ))),
1958                })
1959                .collect::<Result<Vec<_>>>()?;
1960            if name == "sort_by_label" {
1961                SortOrder::ByLabel(labels)
1962            } else {
1963                SortOrder::ByLabelDesc(labels)
1964            }
1965        }
1966    };
1967    Ok(Some((BoundVectorOp::Sort(order), vector)))
1968}
1969
1970/// The labels `absent(expr)` and `absent_over_time(m[d])` answer with, as Prometheus
1971/// `createLabelsForAbsentFunction` derives them: from the matchers of a vector or range selector,
1972/// and none for any other expression.
1973///
1974/// Both selectors carry the same matchers, and Prometheus derives the labels from them the same way
1975/// in either position, so the range selector of `absent_over_time` reads exactly as the vector
1976/// selector of `absent` does.
1977///
1978/// `__field__`, `__schema__` and `__database__` choose what is read rather than match a label, so
1979/// they are not labels of the answer, as in the existing planner.
1980fn absent_labels_of(expr: &PromExpr) -> Result<SeriesLabels> {
1981    let (selector, alternatives) = match unparen(expr) {
1982        PromExpr::VectorSelector(selector) => (&selector.matchers, &selector.matchers.or_matchers),
1983        PromExpr::MatrixSelector(MatrixSelector { vs, .. }) => {
1984            (&vs.matchers, &vs.matchers.or_matchers)
1985        }
1986        _ => return absent_labels(&[]),
1987    };
1988    if !alternatives.is_empty() {
1989        return Err(not_implemented(&format!(
1990            "`absent` or `absent_over_time` over `{expr}`, whose matchers are alternatives"
1991        )));
1992    }
1993    let matchers = selector
1994        .matchers
1995        .iter()
1996        .filter(|matcher| {
1997            !matches!(
1998                matcher.name.as_str(),
1999                "__field__" | "__schema__" | "__database__"
2000            )
2001        })
2002        .map(|matcher| LabelMatcher {
2003            name: Arc::from(matcher.name.as_str()),
2004            op: match_op(&matcher.op),
2005            value: Arc::from(matcher.value.as_str()),
2006            matches_empty: matcher.is_match(""),
2007        })
2008        .collect::<Vec<_>>();
2009    absent_labels(&matchers)
2010}
2011
2012/// Binds `function` over the range selector `vs[range]` into a window over the raw input.
2013///
2014/// Both shapes reach this: the range, the offset, the anchor, the grid and the output are the same
2015/// whichever function reads them, so a parameterised function only decides *what* folds the window,
2016/// never *which* window is folded.
2017fn window_selection(
2018    context: &Context,
2019    function: RangeFunction,
2020    vs: &VectorSelector,
2021    range: &Duration,
2022) -> Result<NativeNode> {
2023    // An `@` anchor is step-invariant: every step folds the same samples, which the window's
2024    // `anchor_ms` tells `RangeEvaluator` to replay over the grid.
2025    let range_ms = range_millis(range.as_millis())?;
2026    let offset_ms = selector_offset_ms(&vs.offset)?;
2027    let anchor_ms = selector_anchor_ms(&vs.at, context.stmt)?;
2028    // The grid is the last thing built: a query refused above, or a window that cannot exist,
2029    // never pays for a grid nothing would read.
2030    let output_grid = Arc::clone(&context.grid);
2031
2032    let (grid_start_ms, grid_end_ms) = grid_endpoints(&output_grid)?;
2033    let (source_index, schema) = bind_selector(
2034        context,
2035        SelectorRequirement {
2036            metric: vs.name.clone(),
2037            matchers: vs.matchers.clone(),
2038            offset_ms,
2039            at_ms: anchor_ms,
2040            grid_start_ms,
2041            grid_end_ms,
2042            timing: SelectorTiming::Window { range_ms },
2043        },
2044    )?;
2045    let output = NativeType::Samples(Arc::new(SeriesSchema {
2046        fields: Arc::clone(&schema.fields),
2047        eval_grid: Some(Arc::clone(&output_grid)),
2048    }));
2049    let raw = NativeType::Samples(Arc::clone(&schema));
2050
2051    Ok(NativeNode {
2052        expr: NativeExpr::Window {
2053            input: Box::new(NativeNode {
2054                expr: NativeExpr::Input(BoundInput {
2055                    output: raw.clone(),
2056                    source_index,
2057                    ordering: context.ordering,
2058                }),
2059                output: raw,
2060            }),
2061            op: BoundWindow {
2062                function,
2063                window: RangeWindow {
2064                    range_ms,
2065                    offset_ms,
2066                    anchor_ms,
2067                    modifier: None,
2068                },
2069                // The input is raw samples, so it has no grid of its own.
2070                input_grid: None,
2071                output_grid,
2072            },
2073        },
2074        output,
2075    })
2076}
2077
2078/// The step a subquery names when it names none, as in `x[5m:]`.
2079///
2080/// Prometheus falls back to the global evaluation interval, whose default is a minute, rather than to
2081/// the statement's own step. The existing planner folds the same default; the constant is restated
2082/// here because that one is private to the planner, and it is a Prometheus protocol constant rather
2083/// than a number either caller may choose.
2084const DEFAULT_SUBQUERY_STEP_MS: i64 = 60_000;
2085
2086/// The grid a subquery's inner expression is evaluated on, and the window that reads it.
2087///
2088/// Both halves of the native route need the same answer: the compiler binds the grid into the node,
2089/// where it tells the window which points its input was evaluated at, and the planner binds the tree
2090/// it compiles to the grid its rows carry. A second derivation would let the two disagree about the
2091/// default step or the conversion of the range, and a tree bound to a grid it was not compiled on
2092/// cannot be planned, so the numbers are derived here once.
2093pub(crate) struct SubqueryGrid {
2094    /// The interval the range function folds, and how far back from the anchor it reads.
2095    pub(crate) window: RangeWindow,
2096    /// The grid `subquery.expr` is evaluated on.
2097    pub(crate) grid: Arc<EvalGrid>,
2098}
2099
2100/// Derives the [`SubqueryGrid`] of `subquery`, whose outer statement is evaluated on `outer`.
2101///
2102/// The child grid is one point per `step` over the interval the subquery's window reads, which its
2103/// `@` anchor, offset and range decide; without an anchor it is the statement's own range. Every
2104/// number is converted checked, so a range or a step too large to name a millisecond is reported as
2105/// itself rather than wrapped into a different interval.
2106///
2107/// `None` when the anchored interval contains no step boundary, which names no evaluation point at
2108/// all. Declining is the caller's decision: the compiler reports the shape it cannot fold, while the
2109/// planner keeps the plan the existing path builds.
2110pub(crate) fn subquery_child_grid(
2111    stmt: &EvalStmt,
2112    outer: &EvalGrid,
2113    subquery: &SubqueryExpr,
2114) -> Result<Option<SubqueryGrid>> {
2115    // The anchor is resolved by the same function a range selector's is, so `start()`, `end()` and a
2116    // literal — including a negative one — mean the same thing in both shapes.
2117    let anchor_ms = selector_anchor_ms(&subquery.at, stmt)?;
2118    let range_ms = range_millis(subquery.range.as_millis())?;
2119    // A subquery step of zero names no evaluation point at all, so it is reported as its own value
2120    // rather than as an empty grid.
2121    let step_ms = match subquery.step {
2122        Some(step) => millis(step.as_millis()).ok_or_else(|| {
2123            DataFusionError::Plan(format!(
2124                "the subquery's step of {}ms is out of range",
2125                step.as_millis()
2126            ))
2127        })?,
2128        None => DEFAULT_SUBQUERY_STEP_MS,
2129    };
2130    if step_ms <= 0 {
2131        return Err(DataFusionError::Plan(format!(
2132            "the subquery's step is {step_ms}ms, and a step has to be longer than zero"
2133        )));
2134    }
2135    let offset_ms = selector_offset_ms(&subquery.offset)?;
2136    let window = RangeWindow {
2137        range_ms,
2138        offset_ms,
2139        anchor_ms,
2140        modifier: None,
2141    };
2142    let Some(spec) = subquery_grid(outer.spec(), window, step_ms)? else {
2143        return Ok(None);
2144    };
2145    // Keep subquery grids deferred: selector binding needs only their spec endpoints, not a
2146    // materialized timestamp vector proportional to the range.
2147    let grid = Arc::new(EvalGrid::try_deferred(spec).map_err(grid_error)?);
2148    Ok(Some(SubqueryGrid { window, grid }))
2149}
2150
2151/// Binds `function` over `subquery`, whose inner expression is evaluated on a grid of its own.
2152///
2153/// A range function folds a matrix, and PromQL writes a matrix two ways. A range selector reads raw
2154/// samples from the scan; a subquery builds one by evaluating an expression. That is why this node
2155/// declares `input_grid`: `rate(x[5m:1m])` samples `x` at one-minute steps over the five-minute
2156/// lookback, and the window folds those points rather than raw samples. The inner expression is
2157/// compiled against the subquery's grid for the same reason — a selector inside it has to land where
2158/// the window will read it.
2159///
2160/// An `@` anchor makes the subquery step-invariant: every output point reads the same interval,
2161/// `(anchor - offset - range, anchor - offset]`. The child grid is built for that interval, while
2162/// the output grid remains the statement's grid; the anchor, range and offset are bound together in
2163/// the window.
2164fn subquery_window(
2165    context: &Context,
2166    name: &str,
2167    function: RangeFunction,
2168    subquery: &SubqueryExpr,
2169) -> Result<NativeNode> {
2170    let SubqueryExpr { expr, .. } = subquery;
2171    // A subquery evaluates an expression and hands the window one value per grid point per field, so
2172    // the expression inside it has to be a vector: a scalar has no fields for the window to fold.
2173    if expr.value_type() != ValueType::Vector {
2174        return Err(not_implemented(&format!(
2175            "a call to `{name}` over the subquery `{subquery}`, whose expression is a {}, where a \
2176             subquery has to evaluate a vector",
2177            expr.value_type()
2178        )));
2179    }
2180    let Some(SubqueryGrid {
2181        window,
2182        grid: child_grid,
2183    }) = subquery_child_grid(context.stmt, &context.grid, subquery)?
2184    else {
2185        return Err(not_implemented(&format!(
2186            "the subquery `{subquery}`, which names no evaluation point in its anchored interval or \
2187             the statement's range"
2188        )));
2189    };
2190    let inner = compile_expr(
2191        &Context {
2192            stmt: context.stmt,
2193            bindings: context.bindings,
2194            inputs: context.inputs,
2195            ordering: context.ordering,
2196            grid: Arc::clone(&child_grid),
2197            value_field: Arc::clone(&context.value_field),
2198            source_kind: context.source_kind,
2199        },
2200        expr,
2201    )?;
2202
2203    let inner_schema = inner
2204        .output
2205        .samples()
2206        .ok_or_else(|| DataFusionError::Internal("subquery body did not produce samples".into()))?;
2207    let output = NativeType::Samples(Arc::new(SeriesSchema {
2208        fields: Arc::clone(&inner_schema.fields),
2209        eval_grid: Some(Arc::clone(&context.grid)),
2210    }));
2211
2212    Ok(NativeNode {
2213        expr: NativeExpr::Window {
2214            input: Box::new(inner),
2215            op: BoundWindow {
2216                function,
2217                window,
2218                // The one field that tells this window from a raw one: its input was evaluated on the
2219                // subquery's grid rather than read from the scan.
2220                input_grid: Some(child_grid),
2221                output_grid: Arc::clone(&context.grid),
2222            },
2223        },
2224        output,
2225    })
2226}
2227
2228/// Compiles a bare selector into an instant selection over the raw input.
2229///
2230/// The lookback, the offset and the grid are the whole of an instant selection: it reports the last
2231/// sample at or before each grid point, within the statement's lookback.
2232fn instant_selection(context: &Context, selector: &VectorSelector) -> Result<NativeNode> {
2233    instant_selection_of(context, selector, InstantValue::Sample)
2234}
2235
2236fn instant_selection_of(
2237    context: &Context,
2238    selector: &VectorSelector,
2239    value: InstantValue,
2240) -> Result<NativeNode> {
2241    let lookback_ms = lookback_millis(context.stmt.lookback_delta.as_millis())?;
2242    let offset_ms = selector_offset_ms(&selector.offset)?;
2243    let at_ms = selector_anchor_ms(&selector.at, context.stmt)?;
2244    let output_grid = Arc::clone(&context.grid);
2245    let (grid_start_ms, grid_end_ms) = grid_endpoints(&output_grid)?;
2246    let (source_index, schema) = bind_selector(
2247        context,
2248        SelectorRequirement {
2249            metric: selector.name.clone(),
2250            matchers: selector.matchers.clone(),
2251            offset_ms,
2252            at_ms,
2253            grid_start_ms,
2254            grid_end_ms,
2255            timing: SelectorTiming::Instant { lookback_ms },
2256        },
2257    )?;
2258    if value == InstantValue::Timestamp && schema.fields.len() != 1 {
2259        return Err(not_implemented(
2260            "timestamp() over a multi-value input is not supported natively",
2261        ));
2262    }
2263    let output = NativeType::Samples(Arc::new(SeriesSchema {
2264        fields: Arc::clone(&schema.fields),
2265        eval_grid: Some(Arc::clone(&output_grid)),
2266    }));
2267    let raw = NativeType::Samples(Arc::clone(&schema));
2268    Ok(NativeNode {
2269        expr: NativeExpr::Instant {
2270            input: Box::new(NativeNode {
2271                expr: NativeExpr::Input(BoundInput {
2272                    output: raw.clone(),
2273                    source_index,
2274                    ordering: context.ordering,
2275                }),
2276                output: raw,
2277            }),
2278            op: BoundInstant {
2279                lookback_ms,
2280                offset_ms,
2281                at_ms,
2282                value,
2283                output_grid,
2284            },
2285        },
2286        output,
2287    })
2288}
2289
2290fn bind_selector(
2291    context: &Context,
2292    requirement: SelectorRequirement,
2293) -> Result<(usize, Arc<SeriesSchema>)> {
2294    let schema = (context.bindings)(&requirement)?;
2295    let source_index = context.inputs.borrow().len();
2296    context.inputs.borrow_mut().push(CompiledInput {
2297        source_index,
2298        requirement,
2299        schema: Arc::clone(&schema),
2300        ordering: context.ordering,
2301    });
2302    Ok((source_index, schema))
2303}
2304
2305fn grid_endpoints(grid: &EvalGrid) -> Result<(i64, i64)> {
2306    let spec = grid.spec();
2307    let end = i128::from(spec.start_ms) + i128::from(spec.len - 1) * i128::from(spec.step_ms);
2308    let end = i64::try_from(end)
2309        .map_err(|_| DataFusionError::Internal("evaluation grid endpoint overflows".into()))?;
2310    Ok((spec.start_ms, end))
2311}
2312
2313/// The grid the statement is evaluated on: `(end - start) / step + 1` points, the last of which
2314/// does not pass `end`.
2315///
2316/// Visible to the planner because the binding a [`NativeTree`] is planned against has to name the
2317/// same grid the tree itself was compiled on, and [`compile`]'s callers therefore read it here
2318/// rather than deriving the grid a second time.
2319pub(crate) fn statement_grid(stmt: &EvalStmt) -> Result<Arc<EvalGrid>> {
2320    let start_ms = signed_millis_since_epoch(stmt.start)?;
2321    let end_ms = signed_millis_since_epoch(stmt.end)?;
2322    // The step is narrowed before [`GridSpec`] sees it, so an interval to which no millisecond
2323    // step corresponds is reported as its own value rather than as a step of zero.
2324    let step_ms = millis(stmt.interval.as_millis()).ok_or_else(|| {
2325        DataFusionError::Plan(format!(
2326            "the statement's evaluation step of {}ms is out of range",
2327            stmt.interval.as_millis()
2328        ))
2329    })?;
2330    // A positive step, ordered endpoints and an inclusive length that fits are the grid's contract,
2331    // so [`GridSpec`] owns them; re-deriving any of them here would be a second copy of it.
2332    let spec = GridSpec::try_from_range(start_ms, end_ms, step_ms).map_err(|error| {
2333        DataFusionError::Plan(format!(
2334            "the statement's grid of {start_ms}ms..{end_ms}ms at {step_ms}ms per step is invalid: \
2335             {error}"
2336        ))
2337    })?;
2338    Ok(Arc::new(EvalGrid::try_deferred(spec).map_err(grid_error)?))
2339}
2340
2341/// The window length of a range selector, which has to be longer than zero to select anything.
2342fn range_millis(range: u128) -> Result<i64> {
2343    let range_ms = millis(range).ok_or_else(|| {
2344        DataFusionError::Plan(format!(
2345            "the range selector's window of {range}ms is out of range"
2346        ))
2347    })?;
2348    if range_ms <= 0 {
2349        return Err(DataFusionError::Plan(format!(
2350            "the range selector's window is {range_ms}ms, and a window has to be longer than zero"
2351        )));
2352    }
2353    Ok(range_ms)
2354}
2355
2356/// The statement's lookback in milliseconds, which is how far back an instant selection reads.
2357fn lookback_millis(lookback: u128) -> Result<i64> {
2358    millis(lookback).ok_or_else(|| {
2359        DataFusionError::Plan(format!(
2360            "the statement's lookback of {lookback}ms is out of range"
2361        ))
2362    })
2363}
2364
2365/// The selector's `@` anchor in milliseconds since the Unix epoch, or `None` when it has none.
2366///
2367/// `start()` and `end()` stay symbolic in the AST, because only the statement knows which evaluation
2368/// range they name, so they are resolved against `stmt.start` and `stmt.end` here. The offset is not
2369/// folded in: [`RangeWindow`] keeps anchor and offset apart and ends the window at
2370/// `anchor_ms - offset_ms` at run time.
2371///
2372/// An anchor decouples the window's read range from the statement's: it reads
2373/// `(anchor_ms - offset_ms - range_ms, anchor_ms - offset_ms]`, which for an anchor like `@ 1234` can
2374/// lie entirely outside `[stmt.start - range_ms, stmt.end]`. Whoever binds the scan therefore has to
2375/// derive its range from the window's anchor, offset and range rather than from `stmt.start` and
2376/// `stmt.end`; a scan bound to the statement alone leaves such a window with no samples, and the
2377/// query silently returns empty instead of failing.
2378fn selector_anchor_ms(at: &Option<AtModifier>, stmt: &EvalStmt) -> Result<Option<i64>> {
2379    match at {
2380        None => Ok(None),
2381        Some(AtModifier::Start) => Ok(Some(signed_millis_since_epoch(stmt.start)?)),
2382        Some(AtModifier::End) => Ok(Some(signed_millis_since_epoch(stmt.end)?)),
2383        Some(AtModifier::At(time)) => Ok(Some(signed_millis_since_epoch(*time)?)),
2384    }
2385}
2386
2387/// The selector's offset in milliseconds; positive reads earlier samples.
2388fn selector_offset_ms(offset: &Option<Offset>) -> Result<i64> {
2389    let Some(offset) = offset else {
2390        return Ok(0);
2391    };
2392    let (magnitude, sign) = match offset {
2393        Offset::Pos(duration) => (duration.as_millis(), 1),
2394        Offset::Neg(duration) => (duration.as_millis(), -1),
2395    };
2396    millis(magnitude)
2397        .and_then(|magnitude| magnitude.checked_mul(sign))
2398        .ok_or_else(|| {
2399            DataFusionError::Plan(format!(
2400                "the selector's offset of {magnitude}ms is out of range"
2401            ))
2402        })
2403}
2404
2405/// A millisecond magnitude as an `i64`, or `None` when it does not fit.
2406fn millis(millis: u128) -> Option<i64> {
2407    i64::try_from(millis).ok()
2408}
2409
2410fn grid_error(error: datatypes::error::Error) -> DataFusionError {
2411    DataFusionError::Plan(format!("the statement's grid is invalid: {error}"))
2412}
2413
2414/// What a call to a range function has to be: where its range selector sits, how many constants it
2415/// reads, and how they bind.
2416///
2417/// The selector's position is a variant rather than a convention because PromQL does not put it in
2418/// one place: `quantile_over_time(0.9, x[5m])` writes its quantile before the selector, while
2419/// `predict_linear(x[5m], 300)` and `double_exponential_smoothing(x[5m], 0.5, 0.1)` write theirs
2420/// after it. A single "parameters come first" rule would read the selector as a constant in the
2421/// second group and reject an ordinary query, so each shape states its own layout.
2422#[derive(Clone, Copy)]
2423enum RangeSignature {
2424    /// A function that reads only its range selector, as in `rate(x[5m])`.
2425    Selector(RangeFunction),
2426    /// One constant, then the range selector, as in `quantile_over_time(0.9, x[5m])`.
2427    ConstantBeforeSelector(fn(f64) -> RangeFunction),
2428    /// The range selector, then one constant, as in `predict_linear(x[5m], 300)`.
2429    ConstantAfterSelector(fn(f64) -> RangeFunction),
2430    /// The range selector, then two constants, as in
2431    /// `double_exponential_smoothing(x[5m], 0.5, 0.1)`.
2432    TwoConstantsAfterSelector(fn(f64, f64) -> RangeFunction),
2433}
2434
2435impl RangeSignature {
2436    /// The position of the range selector among the call's arguments.
2437    fn selector_index(self) -> usize {
2438        match self {
2439            Self::Selector(_)
2440            | Self::ConstantAfterSelector(_)
2441            | Self::TwoConstantsAfterSelector(_) => 0,
2442            Self::ConstantBeforeSelector(_) => 1,
2443        }
2444    }
2445
2446    /// How many constants the function reads.
2447    fn constants(self) -> usize {
2448        match self {
2449            Self::Selector(_) => 0,
2450            Self::ConstantBeforeSelector(_) | Self::ConstantAfterSelector(_) => 1,
2451            Self::TwoConstantsAfterSelector(_) => 2,
2452        }
2453    }
2454
2455    /// How many arguments the call writes, its range selector counted in.
2456    fn arity(self) -> usize {
2457        self.constants() + 1
2458    }
2459
2460    /// What the call's arguments are, for the arity rejection to name them.
2461    fn arguments(self) -> &'static str {
2462        match self {
2463            Self::Selector(_) => "its range selector",
2464            Self::ConstantBeforeSelector(_) => "a number and its range selector",
2465            Self::ConstantAfterSelector(_) => "its range selector and a number",
2466            Self::TwoConstantsAfterSelector(_) => "its range selector and two numbers",
2467        }
2468    }
2469
2470    /// Binds the function from the call's arguments, which have already passed the arity check.
2471    fn bind(self, name: &str, args: &[Box<PromExpr>]) -> Result<RangeFunction> {
2472        Ok(match self {
2473            Self::Selector(function) => function,
2474            Self::ConstantBeforeSelector(bind) => bind(constant_argument(name, &args[0], 0)?),
2475            Self::ConstantAfterSelector(bind) => bind(constant_argument(name, &args[1], 1)?),
2476            Self::TwoConstantsAfterSelector(bind) => bind(
2477                constant_argument(name, &args[1], 1)?,
2478                constant_argument(name, &args[2], 2)?,
2479            ),
2480        })
2481    }
2482}
2483
2484/// The signature the PromQL name calls, or `None` when this compiler has no range kernel for it.
2485///
2486/// The map is explicit on purpose, as in [`range_function`]: a name that is not listed is rejected,
2487/// so supporting one more function is a decision made in one place rather than a consequence of a
2488/// name looking familiar. A parameterised function is named here rather than in the map, because
2489/// its name alone cannot produce the variant the tree binds.
2490fn range_signature(name: &str) -> Option<RangeSignature> {
2491    match name {
2492        "quantile_over_time" => Some(RangeSignature::ConstantBeforeSelector(
2493            RangeFunction::QuantileOverTime,
2494        )),
2495        // These two write their constants after the selector, which is the opposite order to
2496        // `quantile_over_time`.
2497        "predict_linear" => Some(RangeSignature::ConstantAfterSelector(
2498            RangeFunction::PredictLinear,
2499        )),
2500        "double_exponential_smoothing" => Some(RangeSignature::TwoConstantsAfterSelector(
2501            |smoothing, trend| RangeFunction::DoubleExponentialSmoothing { smoothing, trend },
2502        )),
2503        _ => range_function(name).map(RangeSignature::Selector),
2504    }
2505}
2506
2507/// What a call to a math function has to be: the constants it reads after its vector, and how to
2508/// bind them.
2509///
2510/// The shapes are separated by how many constants the function reads, because that is the only
2511/// thing the variants differ in: a name maps to one kernel, and the constants are bound from the
2512/// call. `round` is the one function whose constant may be left out, so it is its own shape: the
2513/// default is a decision about the function rather than about the constant.
2514#[derive(Clone, Copy)]
2515enum MathSignature {
2516    /// A function of its vector alone, as in `abs`.
2517    Unary(MathOp),
2518    /// A function of its vector and one constant, as in `clamp_min`.
2519    OneConstant(fn(f64) -> MathOp),
2520    /// A function of its vector and one constant it may be called without, as in `round`.
2521    DefaultedConstant {
2522        default: f64,
2523        bind: fn(f64) -> MathOp,
2524    },
2525    /// A function of its vector and two constants, as in `clamp`.
2526    TwoConstants(fn(f64, f64) -> MathOp),
2527}
2528
2529impl MathSignature {
2530    /// How many constants the function reads when every one of them is written.
2531    fn parameters(self) -> usize {
2532        match self {
2533            Self::Unary(_) => 0,
2534            Self::OneConstant(_) | Self::DefaultedConstant { .. } => 1,
2535            Self::TwoConstants(_) => 2,
2536        }
2537    }
2538
2539    /// How many constants the function has to be given.
2540    fn required(self) -> usize {
2541        match self {
2542            Self::DefaultedConstant { .. } => 0,
2543            _ => self.parameters(),
2544        }
2545    }
2546
2547    /// What the call's arguments are, for the arity rejection to name them.
2548    fn arguments(self) -> &'static str {
2549        match self {
2550            Self::Unary(_) => "its vector",
2551            Self::OneConstant(_) => "its vector and one constant",
2552            Self::DefaultedConstant { .. } => "its vector and one optional constant",
2553            Self::TwoConstants(_) => "its vector and two constants",
2554        }
2555    }
2556}
2557
2558/// The signature the PromQL name calls, or `None` when this compiler has no math kernel for it.
2559///
2560/// The map is explicit on purpose, as in [`range_function`]: a name that is not listed is refused
2561/// rather than treated as math because it looks mathematical, so adding one more function is a
2562/// decision made in one place. A name in this list is a promise that its kernel exists, which is why
2563/// arity is a property of the variant rather than of the caller.
2564fn math_signature(name: &str) -> Option<MathSignature> {
2565    match name {
2566        "abs" => Some(MathSignature::Unary(MathOp::Abs)),
2567        "ceil" => Some(MathSignature::Unary(MathOp::Ceil)),
2568        "floor" => Some(MathSignature::Unary(MathOp::Floor)),
2569        "sqrt" => Some(MathSignature::Unary(MathOp::Sqrt)),
2570        "exp" => Some(MathSignature::Unary(MathOp::Exp)),
2571        "ln" => Some(MathSignature::Unary(MathOp::Ln)),
2572        "log2" => Some(MathSignature::Unary(MathOp::Log2)),
2573        "log10" => Some(MathSignature::Unary(MathOp::Log10)),
2574        "sin" => Some(MathSignature::Unary(MathOp::Sin)),
2575        "cos" => Some(MathSignature::Unary(MathOp::Cos)),
2576        "tan" => Some(MathSignature::Unary(MathOp::Tan)),
2577        "asin" => Some(MathSignature::Unary(MathOp::Asin)),
2578        "acos" => Some(MathSignature::Unary(MathOp::Acos)),
2579        "atan" => Some(MathSignature::Unary(MathOp::Atan)),
2580        "sinh" => Some(MathSignature::Unary(MathOp::Sinh)),
2581        "cosh" => Some(MathSignature::Unary(MathOp::Cosh)),
2582        "tanh" => Some(MathSignature::Unary(MathOp::Tanh)),
2583        "asinh" => Some(MathSignature::Unary(MathOp::Asinh)),
2584        "acosh" => Some(MathSignature::Unary(MathOp::Acosh)),
2585        "atanh" => Some(MathSignature::Unary(MathOp::Atanh)),
2586        "deg" => Some(MathSignature::Unary(MathOp::Deg)),
2587        "rad" => Some(MathSignature::Unary(MathOp::Rad)),
2588        "sgn" => Some(MathSignature::Unary(MathOp::Sgn)),
2589        // A date function takes the vector its values are read from; without one it reads the
2590        // evaluation time, which has no input to map and is refused by `math_op`.
2591        "day_of_month" => Some(MathSignature::Unary(MathOp::Date(DateFunction::DayOfMonth))),
2592        "day_of_week" => Some(MathSignature::Unary(MathOp::Date(DateFunction::DayOfWeek))),
2593        "day_of_year" => Some(MathSignature::Unary(MathOp::Date(DateFunction::DayOfYear))),
2594        "days_in_month" => Some(MathSignature::Unary(MathOp::Date(
2595            DateFunction::DaysInMonth,
2596        ))),
2597        "hour" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Hour))),
2598        "minute" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Minute))),
2599        "month" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Month))),
2600        "year" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Year))),
2601        // `round`'s nearest defaults to one, so `round(x)` is `round(x, 1)` and its variant always
2602        // carries the number it rounds to.
2603        "round" => Some(MathSignature::DefaultedConstant {
2604            default: 1.0,
2605            bind: |nearest| MathOp::Round { nearest },
2606        }),
2607        "clamp" => Some(MathSignature::TwoConstants(|min, max| MathOp::Clamp {
2608            min,
2609            max,
2610        })),
2611        "clamp_min" => Some(MathSignature::OneConstant(|min| MathOp::ClampMin { min })),
2612        "clamp_max" => Some(MathSignature::OneConstant(|max| MathOp::ClampMax { max })),
2613        _ => None,
2614    }
2615}
2616
2617/// The pointwise kernel `name` denotes over its vector, and that vector, or `None` when this
2618/// compiler has no math kernel for that name.
2619///
2620/// A name that is not in [`math_signature`] is not math: the caller reports that it has no kernel
2621/// instead of compiling it into a kernel that would compute something else. `arguments` is the
2622/// call's whole argument list, because the vector is its first argument: the arity is the
2623/// signature's and counts the vector in, so a call with no argument at all is refused as a call
2624/// that wrote none rather than as a shape this compiler cannot bind. The arguments after the vector
2625/// are the call's constants, in the order they were written, and each is folded to the number it
2626/// means by [`constant_value`], because the tree binds a kernel's constants and has no field for an
2627/// expression.
2628fn math_op<'a>(
2629    name: &str,
2630    arguments: &'a [Box<PromExpr>],
2631) -> Result<Option<(MathOp, &'a PromExpr)>> {
2632    let Some(signature) = math_signature(name) else {
2633        return Ok(None);
2634    };
2635    // The vector is the function's first argument, so a call that wrote no argument at all is
2636    // refused by the same arity check as one that wrote too few constants.
2637    let Some((vector, parameters)) = arguments.split_first() else {
2638        return Err(arity_error(name, signature, 0));
2639    };
2640    let given = parameters.len() + 1;
2641    if given < signature.required() + 1 || given > signature.parameters() + 1 {
2642        return Err(arity_error(name, signature, given));
2643    }
2644    // The vector is the first argument, so the constants are read from the second onwards.
2645    let op = match signature {
2646        MathSignature::Unary(op) => op,
2647        MathSignature::OneConstant(bind) => bind(constant_argument(name, &parameters[0], 1)?),
2648        MathSignature::DefaultedConstant { default, bind } => bind(match parameters.first() {
2649            Some(parameter) => constant_argument(name, parameter, 1)?,
2650            None => default,
2651        }),
2652        MathSignature::TwoConstants(bind) => bind(
2653            constant_argument(name, &parameters[0], 1)?,
2654            constant_argument(name, &parameters[1], 2)?,
2655        ),
2656    };
2657    Ok(Some((op, vector)))
2658}
2659
2660/// The native histogram function `name` denotes, or `None` when it is not one.
2661///
2662/// These read only native histogram samples and drop the float ones, as Prometheus'
2663/// `simpleHistogramFunc` does; `histogram_quantile` and `histogram_fraction` also read classic
2664/// bucket series and are not listed.
2665fn histogram_function(name: &str) -> Option<NativeHistogramFunction> {
2666    match name {
2667        "histogram_count" => Some(NativeHistogramFunction::Count),
2668        "histogram_sum" => Some(NativeHistogramFunction::Sum),
2669        "histogram_avg" => Some(NativeHistogramFunction::Avg),
2670        "histogram_stddev" => Some(NativeHistogramFunction::StdDev),
2671        "histogram_stdvar" => Some(NativeHistogramFunction::StdVar),
2672        _ => None,
2673    }
2674}
2675
2676/// The label change `label_replace` or `label_join` makes, and the vector it is made to, or `None`
2677/// when `name` is neither.
2678///
2679/// The parser checks the argument types and counts; what is left to check is the arguments'
2680/// content, which [`LabelRewrite`] does as Prometheus does at evaluation, so an invalid regular
2681/// expression or an empty label name fails the statement here as it would there.
2682fn label_rewrite<'a>(
2683    name: &str,
2684    arguments: &'a [Box<PromExpr>],
2685) -> Result<Option<(LabelRewrite, &'a PromExpr)>> {
2686    if !matches!(name, "label_replace" | "label_join") {
2687        return Ok(None);
2688    }
2689    let Some((vector, strings)) = arguments.split_first() else {
2690        return Err(not_implemented(&format!(
2691            "a call to `{name}` with no argument"
2692        )));
2693    };
2694    let strings = strings
2695        .iter()
2696        .map(|argument| match unparen(argument) {
2697            PromExpr::StringLiteral(StringLiteral { val }) => Ok(val.as_str()),
2698            other => Err(not_implemented(&format!(
2699                "a call to `{name}` whose argument `{other}` is not a string literal"
2700            ))),
2701        })
2702        .collect::<Result<Vec<_>>>()?;
2703    let rewrite = match (name, strings.as_slice()) {
2704        ("label_replace", [dst, replacement, src, regex]) => {
2705            LabelRewrite::replace(dst, replacement, src, regex)?
2706        }
2707        ("label_join", [dst, separator, src @ ..]) => LabelRewrite::join(dst, separator, src)?,
2708        _ => {
2709            return Err(not_implemented(&format!(
2710                "a call to `{name}` with {} argument(s)",
2711                arguments.len()
2712            )));
2713        }
2714    };
2715    Ok(Some((rewrite, vector)))
2716}
2717
2718/// The rejection of a math call that wrote `given` arguments where `signature` takes another count.
2719///
2720/// The count is the signature's, so the message says what this function takes rather than what one
2721/// argument happens to be. The vector is counted in: it is the function's first argument, and a
2722/// reader counting the call's arguments should not have to add it themselves.
2723fn arity_error(name: &str, signature: MathSignature, given: usize) -> DataFusionError {
2724    not_implemented(&format!(
2725        "a call to `{name}` with {given} argument(s), where it takes {}",
2726        signature.arguments()
2727    ))
2728}
2729
2730/// The constant `argument` folds to, or a rejection naming the argument and where it was read.
2731///
2732/// A parameter is a constant of the statement: a quantile, a rounding step or a clamp bound is a
2733/// field of the tree, so a parameter whose value is only known at run time — `time()` being the real
2734/// case — has nowhere to go. It is refused rather than answered from the wrong number, and the
2735/// rejection names the expression, because that is what the query has to change.
2736///
2737/// `name` is whoever reads the argument: a call's function name, or an aggregator's, since
2738/// `quantile(0.9, x)` reads a constant too. The rejection therefore names that and the position
2739/// rather than calling everything a call, which would be false for an aggregate.
2740///
2741/// A quantile outside `[0, 1]` is not refused here: Prometheus binds it and the kernel reports
2742/// `-Infinity` below zero and `+Infinity` above one, so refusing it would be this compiler inventing
2743/// a rule the query engine does not have.
2744fn constant_argument(name: &str, argument: &PromExpr, position: usize) -> Result<f64> {
2745    constant_value(argument).ok_or_else(|| {
2746        not_implemented(&format!(
2747            "`{name}`, whose {} is `{argument}`, where it has to be a constant expression this \
2748             compiler folds to a number literal",
2749            argument_position(position)
2750        ))
2751    })
2752}
2753
2754/// How a rejection names the argument a parameter was read from.
2755///
2756/// The three positions are the ones a supported call can write: a math function's vector and the two
2757/// constants behind it, or a range function's selector and the constants on either side of it. Every
2758/// caller passes the literal position it read, so there is no fourth position to name and no default
2759/// to invent one for.
2760fn argument_position(position: usize) -> &'static str {
2761    const POSITIONS: [&str; 3] = ["first argument", "second argument", "third argument"];
2762    POSITIONS[position]
2763}
2764
2765/// Whether a binary operation carries a modifier this compiler refuses to bind.
2766///
2767/// A scalar carries no labels, so there is nothing to match or name, and the tree's matching has no
2768/// field for a fill value: binding the operation would compute it without the modifier the query
2769/// asked for. The fold and [`binary_operation`] share this test rather than restating it, because a
2770/// fold that computed a constant without reading its modifier would answer a query the dispatch
2771/// below refuses.
2772fn refuses_modifier(modifier: Option<&BinModifier>) -> bool {
2773    modifier.is_some_and(|modifier| {
2774        modifier.matching.is_some()
2775            || modifier.card != VectorMatchCardinality::OneToOne
2776            || modifier.fill_values != VectorMatchFillValues::default()
2777    })
2778}
2779
2780/// The number `expr` folds to, or `None` when its value is not the statement's to know.
2781///
2782/// Only what the statement itself decides is folded: a number literal, a group around one, a negated
2783/// one, `pi()`, and arithmetic whose two operands both fold. Any other call, a selector, a range
2784/// selector, an aggregate and a subquery are `None`, because their value comes from the data or from
2785/// the evaluation time, and a kernel's constant is a field of the tree rather than something bound
2786/// while it runs. Returning `None` rather than an error is what lets the caller report where the
2787/// expression was found, which is the useful half of the refusal.
2788///
2789/// `pi()` belongs on the folding side because the statement itself decides it: it is one number, not
2790/// a value read from the data. Folding it is what makes `pi() * x` the multiplication by
2791/// [`std::f64::consts::PI`] it means, `clamp_max(x, pi())` a kernel constant like `clamp_max(x, 3)`,
2792/// and `quantile(pi() / 4, x)` a parameter this compiler can bind. The number is the one the promql
2793/// crate's `map_pi` answers the previous route with — both are `std::f64::consts::PI` — so the two
2794/// routes cannot disagree about what `pi()` is.
2795///
2796/// Arithmetic uses the kernel operation named by [`BinaryOp::kind`], including
2797/// [`ArithmeticOp::calculate`]'s platform math behavior; defining `%`, `^` or `atan2` again here
2798/// would be a second answer for the two to disagree over. Set operators do not fold.
2799/// Visible to the planner, which asks whether a statement's value is a constant before binding it.
2800pub(crate) fn constant_value(expr: &PromExpr) -> Option<f64> {
2801    match expr {
2802        PromExpr::NumberLiteral(NumberLiteral { val }) => Some(*val),
2803        PromExpr::Paren(paren) => constant_value(&paren.expr),
2804        PromExpr::Unary(unary) => constant_value(&unary.expr).map(|value| -value),
2805        PromExpr::Binary(binary) => {
2806            // A modifier is read before the operands are folded: `x * (1 + fill(0) 2)` asks for a
2807            // fill, and folding the inner addition would answer `x * 3` with the fill gone. The
2808            // expression is left unfolded so the dispatch below refuses it with the reason it
2809            // writes, which is also why this is a `None` rather than an error here.
2810            if refuses_modifier(binary.modifier.as_ref()) {
2811                return None;
2812            }
2813            let left = constant_value(&binary.lhs)?;
2814            let right = constant_value(&binary.rhs)?;
2815            match binary_op(&binary.op)?.kind() {
2816                BinaryKind::Arithmetic(op) => Some(op.calculate(left, right)),
2817                // A comparison of two constants is the number it reports when it is written with
2818                // `bool`: Prometheus reads `1 > bool 2` as `0`, which is the kernel's own
2819                // comparison. Without `bool` there is no number to report -- `1 > 2` is a parse
2820                // error in Prometheus -- so it is left unfolded and the dispatch refuses it.
2821                BinaryKind::Comparison(op) => binary
2822                    .return_bool()
2823                    .then(|| f64::from(op.apply(left, right))),
2824            }
2825        }
2826        // A selector, a range selector, an aggregate and a subquery read data; `time()`,
2827        // `scalar(v)` and the rest of the calls read something this compiler cannot know before the
2828        // query runs. `pi()` is not one of them: it is the one call whose value the statement itself
2829        // fixes, so it folds here as a literal does.
2830        PromExpr::Call(call) if call.func.name == "pi" && call.args.args.is_empty() => {
2831            Some(std::f64::consts::PI)
2832        }
2833        _ => None,
2834    }
2835}
2836
2837/// The range function a PromQL name denotes, or `None` when this compiler has no kernel for it.
2838///
2839/// The map is explicit on purpose: a name that is not listed here is rejected, so supporting one
2840/// more function is a decision made in one place rather than a consequence of a name looking
2841/// familiar.
2842fn range_function(name: &str) -> Option<RangeFunction> {
2843    match name {
2844        "rate" => Some(RangeFunction::Rate),
2845        "increase" => Some(RangeFunction::Increase),
2846        "delta" => Some(RangeFunction::Delta),
2847        "irate" => Some(RangeFunction::Irate),
2848        "idelta" => Some(RangeFunction::Idelta),
2849        "avg_over_time" => Some(RangeFunction::AvgOverTime),
2850        "min_over_time" => Some(RangeFunction::MinOverTime),
2851        "max_over_time" => Some(RangeFunction::MaxOverTime),
2852        "sum_over_time" => Some(RangeFunction::SumOverTime),
2853        "count_over_time" => Some(RangeFunction::CountOverTime),
2854        "last_over_time" => Some(RangeFunction::LastOverTime),
2855        "present_over_time" => Some(RangeFunction::PresentOverTime),
2856        "stddev_over_time" => Some(RangeFunction::StddevOverTime),
2857        "stdvar_over_time" => Some(RangeFunction::StdvarOverTime),
2858        "resets" => Some(RangeFunction::Resets),
2859        "changes" => Some(RangeFunction::Changes),
2860        "deriv" => Some(RangeFunction::Deriv),
2861        // These functions are supported unconditionally by this native compiler.
2862        "first_over_time" => Some(RangeFunction::FirstOverTime),
2863        "mad_over_time" => Some(RangeFunction::MadOverTime),
2864        "ts_of_first_over_time" => Some(RangeFunction::TsOfFirstOverTime),
2865        "ts_of_last_over_time" => Some(RangeFunction::TsOfLastOverTime),
2866        "ts_of_min_over_time" => Some(RangeFunction::TsOfMinOverTime),
2867        "ts_of_max_over_time" => Some(RangeFunction::TsOfMaxOverTime),
2868        _ => None,
2869    }
2870}
2871
2872/// The expression a parenthesised one wraps, however many parentheses were written.
2873///
2874/// Parentheses group, so they say nothing about the expression inside them: `rate((x[5m]))` asks
2875/// for exactly what `rate(x[5m])` asks for. Refusing it would reject a statement on the way it was
2876/// typed rather than on what it means. A range selector is not an expression this compiler
2877/// compiles on its own, so the call that reads one looks through the grouping itself.
2878fn unparen(mut expr: &PromExpr) -> &PromExpr {
2879    while let PromExpr::Paren(paren) = expr {
2880        expr = &paren.expr;
2881    }
2882    expr
2883}
2884
2885/// A rejection of a shape outside [`SUPPORTED`].
2886fn not_implemented(found: &str) -> DataFusionError {
2887    DataFusionError::NotImplemented(format!(
2888        "the native PromQL compiler supports only {SUPPORTED} for now, but found {found}"
2889    ))
2890}
2891
2892#[cfg(test)]
2893mod tests;