Skip to main content

vortex_array/
executor.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Iterative array execution.
5//!
6//! The single-step [`Executable`] implementation for [`ArrayRef`] optimizes the array with the
7//! context's session, then tries `execute_parent`, then `execute` once. The matcher-driven
8//! [`ArrayRef::execute_until`] loop interprets [`ExecutionStep::ExecuteSlot`],
9//! [`ExecutionStep::AppendChild`], and [`ExecutionStep::Done`] using an explicit stack plus an
10//! optional builder, so encodings can advance without recursive descent.
11//!
12//! See <https://docs.vortex.dev/developer-guide/internals/execution> for the full execution
13//! narrative, diagrams, and walkthroughs.
14
15use std::any::TypeId;
16use std::env::VarError;
17use std::fmt;
18use std::fmt::Display;
19use std::sync::Arc;
20use std::sync::LazyLock;
21use std::sync::OnceLock;
22#[cfg(debug_assertions)]
23use std::sync::atomic::AtomicUsize;
24#[cfg(debug_assertions)]
25use std::sync::atomic::Ordering;
26
27use vortex_error::VortexExpect;
28use vortex_error::VortexResult;
29use vortex_error::vortex_bail;
30use vortex_error::vortex_ensure_eq;
31use vortex_error::vortex_panic;
32use vortex_session::VortexSession;
33
34use crate::AnyCanonical;
35use crate::ArrayRef;
36use crate::IntoArray;
37use crate::aggregate_fn::session::AggregateFnSessionExt;
38use crate::aggregate_fn::session::AggregateKernels;
39use crate::array::ArrayId;
40use crate::builders::ArrayBuilder;
41use crate::builders::builder_with_capacity_in;
42use crate::dtype::DType;
43use crate::matcher::Matcher;
44use crate::memory::BufferAllocatorRef;
45use crate::memory::MemorySessionExt;
46use crate::optimizer::ArrayOptimizer;
47use crate::optimizer::Optimizer;
48use crate::optimizer::kernels::ArrayKernels;
49use crate::optimizer::kernels::ArrayKernelsExt;
50use crate::optimizer::kernels::ParentExecutionKernels;
51use crate::optimizer::kernels::execute_parent_key;
52use crate::optimizer::kernels::execute_parent_marker_key;
53use crate::stats::ArrayStats;
54use crate::trace_op;
55
56/// Returns the maximum number of iterations to attempt when executing an array before giving up and returning
57/// an error, can be by the `VORTEX_MAX_ITERATIONS` env variables, otherwise defaults to 2^22.
58pub(crate) fn max_iterations() -> usize {
59    static MAX_ITERATIONS: LazyLock<usize> = LazyLock::new(|| {
60        match std::env::var("VORTEX_MAX_ITERATIONS") {
61            Ok(val) => val.parse::<usize>().unwrap_or_else(|e| {
62                vortex_panic!("VORTEX_MAX_ITERATIONS is not a valid usize: {e}")
63            }),
64            Err(VarError::NotPresent) => 2 << 21, // 2 ^ 22
65            Err(VarError::NotUnicode(_)) => {
66                vortex_panic!("VORTEX_MAX_ITERATIONS is not a valid unicode string")
67            }
68        }
69    });
70    *MAX_ITERATIONS
71}
72
73/// Marker trait for types that an [`ArrayRef`] can be executed into.
74///
75/// Implementors must provide an implementation of `execute` that takes
76/// an [`ArrayRef`] and an [`ExecutionCtx`], and produces an instance of the
77/// implementor type.
78///
79/// Users should use the `Array::execute` or `Array::execute_as` methods
80pub trait Executable: Sized {
81    fn execute(array: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Self>;
82}
83
84#[expect(clippy::same_name_method)]
85impl ArrayRef {
86    /// Execute this array to produce an instance of `E`.
87    ///
88    /// See the [`Executable`] implementation for details on how this execution is performed.
89    pub fn execute<E: Executable>(self, ctx: &mut ExecutionCtx) -> VortexResult<E> {
90        E::execute(self, ctx)
91    }
92
93    /// Execute this array, labeling the execution step with a name for tracing.
94    pub fn execute_as<E: Executable>(
95        self,
96        _name: &'static str,
97        ctx: &mut ExecutionCtx,
98    ) -> VortexResult<E> {
99        E::execute(self, ctx)
100    }
101
102    /// Iteratively execute this array until the [`Matcher`] matches, using an explicit work
103    /// stack plus an optional builder for `AppendChild`.
104    ///
105    /// Note: the returned array may not match `M`. If execution converges to a canonical form
106    /// that does not match `M`, the canonical array is returned since no further execution
107    /// progress is possible.
108    ///
109    /// For safety, this errors once execution reaches a configurable maximum number of
110    /// iterations (default `2^22`, override with `VORTEX_MAX_ITERATIONS`).
111    ///
112    /// # Loop state
113    ///
114    /// - `current_array: ArrayRef` -- the array currently in focus.
115    /// - `current_builder: Option<Box<dyn ArrayBuilder>>` -- active only for builder-mode
116    ///   execution. `AppendChild` appends detached children here. `Done` finishes the builder
117    ///   and turns it back into the next `current_array`.
118    /// - `stack: Vec<StackFrame>` -- suspended parents from `ExecuteSlot`, including the
119    ///   detached slot index, its [`DonePredicate`], and the parent builder that was active
120    ///   before focus moved into the child.
121    ///
122    /// Example after `ExecuteSlot(1, pred)` has focused slot 1 of a parent:
123    ///
124    /// ```text
125    ///   stack[top].parent_array:
126    ///     RunEnd                          <-- suspended parent
127    ///     +-- slot 0: ends
128    ///     +-- slot 1: _  (detached)
129    ///
130    ///   current_array:
131    ///     DictEncoding                    <-- focused child
132    ///     +-- slot 0: codes
133    ///     +-- slot 1: dictionary
134    ///
135    ///   current_builder:
136    ///     None
137    /// ```
138    ///
139    /// Each loop iteration works like this:
140    ///
141    /// ```text
142    /// loop:
143    ///   Step 1: done(current_array)?
144    ///     - root activation   -> return current_array
145    ///     - ExecuteSlot frame -> pop, reattach child, resume parent
146    ///
147    ///   Step 2: current_builder active?
148    ///     - yes -> skip Step 2a / 2b
149    ///     - no  -> try parent kernels
150    ///
151    ///   Step 2a: if stack.top exists:
152    ///               parent = stack.top.parent_array
153    ///               child = current_array
154    ///               kernels[(parent.encoding_id(), child.encoding_id())]
155    ///                 .try_execute_parent(child, parent, stack.top.slot_idx)
156    ///
157    ///   Step 2b: if current_array's encoding has any registered kernel,
158    ///            for child in current_array.children():
159    ///               parent = current_array
160    ///               kernels[(parent.encoding_id(), child.encoding_id())]
161    ///                 .try_execute_parent(child, parent, child.slot_idx)
162    ///
163    ///   Step 3: match current_array.execute()
164    ///     ExecuteSlot(i, pred) -> push parent on stack, focus child `i`
165    ///     AppendChild(i)       -> detach child `i`, append it into current_builder,
166    ///                             keep parent as current_array
167    ///     Done                 -> finish current_builder if present, else use returned array
168    /// ```
169    ///
170    /// Step 2b first checks whether `current_array`'s encoding owns any execute-parent kernel at
171    /// all (a marker entry in the same kernel snapshot), so a pure compression encoding does not
172    /// probe the registry once for each of its children. Step 2a probes only one pair, so a
173    /// marker check there cannot remove a probe.
174    ///
175    /// Step 2a and Step 2b are skipped while `current_builder` is active. `AppendChild`
176    /// partially consumes `current_array`: some slots already live in the builder, so a
177    /// parent rewrite would observe inconsistent state and could discard accumulated builder
178    /// data.
179    #[allow(clippy::cognitive_complexity)]
180    pub fn execute_until<M: Matcher + 'static>(
181        self,
182        ctx: &mut ExecutionCtx,
183    ) -> VortexResult<ArrayRef> {
184        // One optimizer serves the whole execution, so a shared node that one step rewrote is
185        // reused when a later step reaches it. The session is cloned so the optimizer does not
186        // borrow `ctx`.
187        let session = ctx.session().clone();
188        let session_kernels = session.kernels();
189        let session_kernels: &ArrayKernels = &session_kernels;
190        let mut optimizer = Optimizer::new(Some(session_kernels));
191
192        // Each node is optimized when execution reaches it: the root here, with the nodes below it
193        // that were never optimized, and a child when execution focuses it.
194        let mut current_array = optimizer.optimize_array(&self)?;
195        let mut current_builder: Option<Box<dyn ArrayBuilder>> = None;
196        let mut stack: Vec<StackFrame> = Vec::new();
197        let execute_parent_kernels = Arc::clone(&ctx.execute_parent_kernels);
198        let kernels = execute_parent_kernels.as_ref();
199        let max_iterations = max_iterations();
200
201        trace_op!(record_execute_until_start::<M>(&current_array));
202
203        for _iteration in 0..max_iterations {
204            trace_op!(record_execute_until_iteration(
205                _iteration,
206                &current_array,
207                stack
208                    .last()
209                    .map(|frame| (&frame.parent_array, frame.slot_idx)),
210                current_builder.is_some(),
211            ));
212
213            let (done_target, done_canonical) = match stack.last() {
214                None => root_done_check::<M>(&current_array),
215                Some(frame) => (
216                    (frame.done)(&current_array),
217                    AnyCanonical::matches(&current_array),
218                ),
219            };
220            trace_op!(record_execute_until_done_check(done_target, done_canonical));
221
222            if done_target || done_canonical {
223                match stack.pop() {
224                    None => {
225                        debug_assert!(
226                            current_builder.is_none(),
227                            "root activation should not retain a builder"
228                        );
229                        // Kernels build their results with lazy constructors too, such as a
230                        // filtered validity, so optimize whatever execution produced. This is
231                        // free when the array is already marked as optimized.
232                        current_array = optimizer.optimize_array(&current_array)?;
233                        trace_op!(record_execute_until_return(&current_array));
234                        return Ok(current_array);
235                    }
236                    Some(frame) => {
237                        let _slot_idx = frame.slot_idx;
238                        (current_array, current_builder) = pop_frame(frame, current_array)?;
239                        trace_op!(record_execute_until_pop_frame(_slot_idx, &current_array));
240                        continue;
241                    }
242                }
243            }
244
245            // Step 2a: execute_parent against the suspended parent from ExecuteSlot.
246            //
247            // When executing a child for ExecuteSlot, try execute_parent against
248            // the suspended parent on the stack. This lets kernels like RunEnd's
249            // FilterKernel fire before the child is forced to canonical.
250            //
251            // Skip when a builder is active: the current array has been partially
252            // consumed by AppendChild (some slots are already in the builder), so
253            // a parent rewrite would see inconsistent state and the builder data
254            // would be lost when we restore frame.parent_builder.
255            if current_builder.is_none()
256                && let Some(frame) = stack.last()
257                && let Some(result) = {
258                    execute_parent_for_child(
259                        "stack_execute_parent",
260                        &frame.parent_array,
261                        &current_array,
262                        frame.slot_idx,
263                        kernels,
264                        ctx,
265                    )?
266                }
267            {
268                let frame = stack.pop().vortex_expect("just peeked");
269                let optimized = optimizer.optimize_array(&result)?;
270                trace_op!(record_execute_optimized(&result, &optimized));
271                current_array = optimized;
272                current_builder = frame.parent_builder;
273                continue;
274            }
275            if current_builder.is_none() && stack.last().is_some() {
276                trace_op!(record_execute_parent_none(
277                    "stack_execute_parent",
278                    &current_array,
279                ));
280            }
281
282            // Step 2b: execute_parent against current_array's own children.
283            if current_builder.is_none()
284                && has_execute_parent_kernels(kernels, &current_array)
285                && let Some(rewritten) = try_execute_parent(&current_array, kernels, ctx)?
286            {
287                let optimized = optimizer.optimize_array(&rewritten)?;
288                trace_op!(record_execute_optimized(&rewritten, &optimized));
289                current_array = optimized;
290                continue;
291            }
292            if current_builder.is_none() {
293                trace_op!(record_execute_parent_none(
294                    "child_execute_parent",
295                    &current_array,
296                ));
297            }
298
299            let expected_len = current_array.len();
300            // Only the debug postcondition compares dtypes, so skip the clone otherwise.
301            let expected_dtype = cfg!(debug_assertions).then(|| current_array.dtype().clone());
302            // Share the existing stats handle instead of cloning the set; uninitialised stats stay lazy.
303            let stats = current_array.statistics().share_existing();
304            let encoding_id = current_array.encoding_id();
305            trace_op!(record_execute_encoding(&current_array));
306            let result = current_array.execute_encoding_unchecked(ctx)?;
307            let (array, step) = result.into_parts();
308            match step {
309                ExecutionStep::ExecuteSlot(i, done) => {
310                    let (parent, child) = unsafe { array.take_slot_unchecked(i) }?;
311
312                    trace_op!(record_execute_slot(i, &parent, &child));
313                    stack.push(StackFrame {
314                        parent_array: parent,
315                        parent_builder: current_builder.take(),
316                        slot_idx: i,
317                        done,
318                        original_dtype: child.dtype().clone(),
319                        original_len: child.len(),
320                    });
321                    current_array = optimizer.optimize_array(&child)?;
322                    current_builder = None;
323                }
324                ExecutionStep::AppendChild(i) => {
325                    if current_builder.is_none() {
326                        trace_op!(record_builder_start(&array));
327                        current_builder = Some(builder_with_capacity_in(
328                            array.dtype(),
329                            array.len(),
330                            ctx.allocator(),
331                        ));
332                    }
333                    let (parent, child) = unsafe { array.take_slot_unchecked(i) }?;
334
335                    trace_op!(record_append_child(i, &parent, &child));
336                    trace_op!(record_builder_append(&child));
337
338                    // TODO(joe)[7674]: replace with a builder kernel registry so we don't
339                    // need to go through the VTable append_to_builder indirection.
340                    child.append_to_builder(
341                        current_builder
342                            .as_deref_mut()
343                            .vortex_expect("builder must exist"),
344                        ctx,
345                    )?;
346                    current_array = parent;
347                }
348                ExecutionStep::Done => {
349                    let had_builder = current_builder.is_some();
350                    trace_op!(record_execute_done(&array));
351                    (current_array, current_builder) = finalize_done(
352                        array,
353                        current_builder,
354                        expected_len,
355                        expected_dtype,
356                        stats,
357                        encoding_id,
358                    )?;
359                    if had_builder {
360                        trace_op!(record_builder_finish(&current_array));
361                    }
362                    // Kernels build their results with lazy constructors, such as a cast that only
363                    // changes nullability. Reduce them before execute-parent kernels see them.
364                    current_array = optimizer.optimize_array(&current_array)?;
365                }
366            }
367        }
368
369        vortex_bail!(
370            "Exceeded maximum execution iterations ({}) while executing array",
371            max_iterations,
372        )
373    }
374}
375
376struct StackFrame {
377    parent_array: ArrayRef,
378    parent_builder: Option<Box<dyn ArrayBuilder>>,
379    slot_idx: usize,
380    done: DonePredicate,
381    original_dtype: DType,
382    original_len: usize,
383}
384
385/// Execution context for batch CPU compute.
386#[derive(Debug, Clone)]
387pub struct ExecutionCtx {
388    session: VortexSession,
389    // OnceLock avoids cloning the session allocator when a context does not allocate.
390    allocator: OnceLock<BufferAllocatorRef>,
391    execute_parent_kernels: Arc<ParentExecutionKernels>,
392    // OnceLock avoids snapshotting the aggregate kernels when a context does not aggregate.
393    aggregate_kernels: OnceLock<AggregateKernels>,
394    #[cfg(debug_assertions)]
395    id: usize,
396    #[cfg(debug_assertions)]
397    ops: Vec<String>,
398}
399
400impl ExecutionCtx {
401    /// Create a new execution context with the given session.
402    ///
403    /// This captures a snapshot of the session's execute-parent kernel registry. Kernels
404    /// registered after this context is created are not visible to it; create a new
405    /// [`ExecutionCtx`] after registration to use newly registered kernels.
406    pub fn new(session: VortexSession) -> Self {
407        let execute_parent_kernels = session.kernels().execute_parent_snapshot();
408        Self {
409            session,
410            allocator: OnceLock::new(),
411            execute_parent_kernels,
412            aggregate_kernels: OnceLock::new(),
413            #[cfg(debug_assertions)]
414            id: {
415                static EXEC_CTX_ID: AtomicUsize = AtomicUsize::new(0);
416                EXEC_CTX_ID.fetch_add(1, Ordering::Relaxed)
417            },
418            #[cfg(debug_assertions)]
419            ops: Vec::new(),
420        }
421    }
422
423    /// Get the session associated with this execution context.
424    pub fn session(&self) -> &VortexSession {
425        &self.session
426    }
427
428    /// Get the allocator for this execution context.
429    pub fn allocator(&self) -> &BufferAllocatorRef {
430        self.allocator.get_or_init(|| self.session.allocator())
431    }
432
433    /// Get the aggregate kernels for this execution context.
434    ///
435    /// The session's aggregate kernel registries are snapshotted on first use. Kernels registered
436    /// after that are not visible to this context.
437    pub(crate) fn aggregate_kernels(&self) -> &AggregateKernels {
438        self.aggregate_kernels
439            .get_or_init(|| self.session.aggregate_fns().kernels_snapshot())
440    }
441
442    /// Set the allocator for this execution context.
443    pub fn with_allocator(mut self, allocator: BufferAllocatorRef) -> Self {
444        self.allocator = OnceLock::from(allocator);
445        self
446    }
447
448    /// Log an execution step at the current depth.
449    ///
450    /// Steps are accumulated and dumped as a single trace on Drop at DEBUG level.
451    /// Individual steps are also logged at TRACE level for real-time following.
452    ///
453    /// Use the [`format_args!`] macro to create the `msg` argument.
454    pub fn log(&mut self, msg: fmt::Arguments<'_>) {
455        #[cfg(debug_assertions)]
456        if tracing::enabled!(tracing::Level::TRACE) {
457            let formatted = format!(" - {msg}");
458            tracing::trace!("exec[{}]: {formatted}", self.id);
459            self.ops.push(formatted);
460        }
461        let _ = msg;
462    }
463}
464
465impl Display for ExecutionCtx {
466    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
467        #[cfg(debug_assertions)]
468        return write!(f, "exec[{}]", self.id);
469        #[cfg(not(debug_assertions))]
470        write!(f, "exec")
471    }
472}
473
474#[cfg(debug_assertions)]
475impl Drop for ExecutionCtx {
476    fn drop(&mut self) {
477        if !self.ops.is_empty() && tracing::enabled!(tracing::Level::DEBUG) {
478            // Unlike itertools `.format()` (panics in 0.14 on second format)
479            struct FmtOps<'a>(&'a [String]);
480            impl Display for FmtOps<'_> {
481                fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
482                    for (i, op) in self.0.iter().enumerate() {
483                        if i > 0 {
484                            f.write_str("\n")?;
485                        }
486                        f.write_str(op)?;
487                    }
488                    Ok(())
489                }
490            }
491            tracing::debug!("exec[{}] trace:\n{}", self.id, FmtOps(&self.ops));
492        }
493    }
494}
495
496/// Single-step execution: takes one step toward canonical form.
497///
498/// Steps through optimize, execute_parent, then execute. For `ExecuteSlot`,
499/// only a single child execution step is performed — the child is executed once and put back,
500/// making this a lightweight, bounded operation.
501///
502/// **However**, if `execute_step` returns [`ExecutionStep::AppendChild`], this implementation
503/// drives the *entire* array to completion via [`execute_into_builder`] in a single call.
504/// This can do substantially more work than a normal step because it creates a builder and
505/// fully decodes the array into that builder before returning. Callers should be aware that a
506/// single `.execute::<ArrayRef>(ctx)` call may perform O(n_children * decode_cost) work when
507/// `AppendChild` is returned.
508impl Executable for ArrayRef {
509    fn execute(array: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Self> {
510        trace_op!(record_single_step_start(&array));
511
512        if array.is::<AnyCanonical>() {
513            trace_op!(record_single_step_applied("canonical", &array, &array));
514            return Ok(array);
515        }
516        trace_op!(record_single_step_phase_none("canonical", &array));
517
518        let optimized = array.optimize_ctx(ctx.session())?;
519        if !ArrayRef::ptr_eq(&optimized, &array) {
520            optimized.statistics().inherit_from(array.statistics());
521            trace_op!(record_single_step_applied("optimize", &array, &optimized));
522            return Ok(optimized);
523        }
524        trace_op!(record_single_step_phase_none("optimize", &array));
525
526        let execute_parent_kernels = Arc::clone(&ctx.execute_parent_kernels);
527        let kernels = execute_parent_kernels.as_ref();
528        let has_parent_kernels = has_execute_parent_kernels(kernels, &array);
529
530        for (slot_idx, slot) in array.slots().iter().enumerate() {
531            let Some(child) = slot else { continue };
532            if has_parent_kernels
533                && let Some(executed_parent) = execute_parent_for_child(
534                    "single_step_execute_parent",
535                    &array,
536                    child,
537                    slot_idx,
538                    kernels,
539                    ctx,
540                )?
541            {
542                executed_parent
543                    .statistics()
544                    .inherit_from(array.statistics());
545                trace_op!(record_single_step_applied(
546                    "execute_parent",
547                    &array,
548                    &executed_parent,
549                ));
550                return Ok(executed_parent);
551            }
552        }
553        trace_op!(record_single_step_phase_none("execute_parent", &array));
554        trace_op!(record_execute_encoding(&array));
555
556        let result = array.execute_encoding(ctx)?;
557        let (array, step) = result.into_parts();
558        match step {
559            ExecutionStep::Done => {
560                trace_op!(record_execute_done(&array));
561                Ok(array)
562            }
563            ExecutionStep::ExecuteSlot(i, _) => {
564                let child = array.slots()[i].clone().vortex_expect("valid slot index");
565                let executed_child = child.execute::<ArrayRef>(ctx)?;
566                // SAFETY: execution of a child slot produces a logically equivalent array in a
567                // different physical representation, preserving parent values and statistics.
568                unsafe { array.with_slot(i, executed_child) }
569            }
570            ExecutionStep::AppendChild(_) => {
571                // Single-step: build the entire parent via the builder path.
572                trace_op!(record_builder_start(&array));
573                let builder = builder_with_capacity_in(array.dtype(), array.len(), ctx.allocator());
574                let mut builder = execute_into_builder(array, builder, ctx)?;
575                let output = builder.finish();
576                trace_op!(record_builder_finish(&output));
577                Ok(output)
578            }
579        }
580    }
581}
582
583/// Execute `array` into the given `builder`.
584///
585/// This uses the encoding's [`crate::array::VTable::append_to_builder`] implementation. Most
586/// encodings use the default path of `execute::<Canonical>` followed by re-dispatching
587/// `append_to_builder` on the canonical array, while encodings like `Chunked` can override that to
588/// append child-by-child without materializing the entire parent.
589///
590/// The builder must have a [`DType`] that is a nullability-superset of `array.dtype()`.
591pub fn execute_into_builder(
592    array: ArrayRef,
593    mut builder: Box<dyn ArrayBuilder>,
594    ctx: &mut ExecutionCtx,
595) -> VortexResult<Box<dyn ArrayBuilder>> {
596    array.append_to_builder(builder.as_mut(), ctx)?;
597    Ok(builder)
598}
599
600/// Returns `(matches M, is canonical)`, scanning once when `M` is [`AnyCanonical`].
601#[inline]
602fn root_done_check<M: Matcher + 'static>(array: &ArrayRef) -> (bool, bool) {
603    if TypeId::of::<M>() == TypeId::of::<AnyCanonical>() {
604        let canonical = AnyCanonical::matches(array);
605        return (canonical, canonical);
606    }
607    (M::matches(array), AnyCanonical::matches(array))
608}
609
610/// Pop a stack frame, restoring the parent with the finished child in its slot.
611fn pop_frame(
612    frame: StackFrame,
613    child: ArrayRef,
614) -> VortexResult<(ArrayRef, Option<Box<dyn ArrayBuilder>>)> {
615    debug_assert_eq!(
616        child.dtype(),
617        &frame.original_dtype,
618        "child dtype changed during execution"
619    );
620    debug_assert_eq!(
621        child.len(),
622        frame.original_len,
623        "child len changed during execution"
624    );
625    let parent_array = unsafe { frame.parent_array.put_slot_unchecked(frame.slot_idx, child) }?;
626    Ok((parent_array, frame.parent_builder))
627}
628
629fn finalize_done(
630    result: ArrayRef,
631    mut builder: Option<Box<dyn ArrayBuilder>>,
632    expected_len: usize,
633    expected_dtype: Option<DType>,
634    stats: ArrayStats,
635    encoding_id: ArrayId,
636) -> VortexResult<(ArrayRef, Option<Box<dyn ArrayBuilder>>)> {
637    let output = if let Some(mut builder) = builder.take() {
638        builder.finish()
639    } else {
640        result
641    };
642
643    if cfg!(debug_assertions) {
644        vortex_ensure_eq!(
645            output.len(),
646            expected_len,
647            "Result length mismatch for {:?}",
648            encoding_id
649        );
650        if let Some(expected_dtype) = expected_dtype {
651            vortex_ensure_eq!(
652                output.dtype(),
653                &expected_dtype,
654                "Executed canonical dtype mismatch for {:?}",
655                encoding_id
656            );
657        }
658    }
659
660    output.statistics().transfer_from(&stats);
661    Ok((output, None))
662}
663
664fn execute_parent_for_child(
665    phase: &'static str,
666    parent: &ArrayRef,
667    child: &ArrayRef,
668    slot_idx: usize,
669    kernels: &ParentExecutionKernels,
670    ctx: &mut ExecutionCtx,
671) -> VortexResult<Option<ArrayRef>> {
672    let key = execute_parent_key(parent.encoding_id(), child.encoding_id());
673    if let Some(plugins) = kernels.get(&key) {
674        #[allow(clippy::unused_enumerate_index)]
675        for (_plugin_idx, plugin) in plugins.as_ref().iter().enumerate() {
676            if let Some(result) = plugin.execute_parent(child, parent, slot_idx, ctx)? {
677                if cfg!(debug_assertions) {
678                    vortex_ensure_eq!(
679                        result.len(),
680                        parent.len(),
681                        "Executed parent canonical length mismatch"
682                    );
683                    vortex_ensure_eq!(
684                        result.dtype(),
685                        parent.dtype(),
686                        "Executed parent canonical dtype mismatch"
687                    );
688                }
689                log_parent_rewrite(ctx, phase, slot_idx, parent, child, &result);
690                trace_op!(record_session_execute_parent_applied(
691                    phase,
692                    parent,
693                    child,
694                    slot_idx,
695                    _plugin_idx,
696                    &result,
697                ));
698                return Ok(Some(result));
699            }
700            trace_op!(record_session_execute_parent_declined(
701                phase,
702                parent,
703                child,
704                slot_idx,
705                _plugin_idx,
706            ));
707        }
708    }
709
710    Ok(None)
711}
712
713/// Log a parent rewrite to the execution log.
714fn log_parent_rewrite(
715    ctx: &mut ExecutionCtx,
716    phase: &'static str,
717    slot_idx: usize,
718    parent: &ArrayRef,
719    child: &ArrayRef,
720    output: &ArrayRef,
721) {
722    ctx.log(format_args!(
723        "{phase}: slot[{slot_idx}]({}) rewrote {parent} -> {output}",
724        child.encoding_id(),
725    ));
726}
727
728/// Whether any execute-parent kernel is registered with `parent`'s encoding as the parent.
729#[inline]
730fn has_execute_parent_kernels(kernels: &ParentExecutionKernels, parent: &ArrayRef) -> bool {
731    kernels.contains_key(&execute_parent_marker_key(parent.encoding_id()))
732}
733
734/// Try execute_parent on each occupied slot of the array.
735fn try_execute_parent(
736    array: &ArrayRef,
737    kernels: &ParentExecutionKernels,
738    ctx: &mut ExecutionCtx,
739) -> VortexResult<Option<ArrayRef>> {
740    for (slot_idx, slot) in array.slots().iter().enumerate() {
741        let Some(child) = slot else { continue };
742        if let Some(executed_parent) =
743            execute_parent_for_child("child_execute_parent", array, child, slot_idx, kernels, ctx)?
744        {
745            executed_parent
746                .statistics()
747                .inherit_from(array.statistics());
748            return Ok(Some(executed_parent));
749        }
750    }
751    Ok(None)
752}
753
754/// A predicate that determines when an array has reached a desired form during execution.
755pub type DonePredicate = fn(&ArrayRef) -> bool;
756
757/// Scheduler step indicator returned alongside an array in [`ExecutionResult`].
758///
759/// Instead of recursively executing children, encodings return an `ExecutionStep` that tells the
760/// scheduler what to do next. This enables the scheduler to manage execution iteratively using
761/// an explicit work stack plus an optional builder.
762///
763/// # Semantics
764///
765/// Each variant describes a different execution strategy with distinct cost profiles:
766///
767/// - [`Done`](ExecutionStep::Done): The current activation has finished its work. If no builder
768///   is active, the returned array is the result. If a builder is active, the scheduler ignores
769///   the placeholder array and finishes the builder instead. The scheduler may continue
770///   executing if the target form (e.g. canonical) has not yet been reached.
771///
772/// - [`ExecuteSlot`](ExecutionStep::ExecuteSlot): The encoding needs one of its children
773///   decoded before it can make further progress. The scheduler detaches that child, pushes
774///   the parent onto the explicit stack, executes the child until the [`DonePredicate`]
775///   matches, puts it back, and re-enters the parent. This is a cooperative yield: the
776///   encoding does a bounded amount of work per step while the loop tracks the parent-child
777///   relationship explicitly.
778///
779/// - [`AppendChild`](ExecutionStep::AppendChild): The encoding needs one child executed to
780///   canonical form and then appended into a builder owned by the current activation. The
781///   scheduler detaches that child, lazily creates `current_builder` if needed, appends the
782///   child into it, and keeps the parent as `current_array` for the next iteration. While the
783///   builder is active, parent-kernel rewrites are skipped because the parent is partially
784///   consumed. **Important:** in the single-step executor ([`Executable`] for [`ArrayRef`]),
785///   returning `AppendChild` still causes the executor to drive the *entire* array to
786///   completion via [`execute_into_builder`] in one call — this can do significantly more
787///   work than a single `ExecuteSlot` step.
788pub enum ExecutionStep {
789    /// Request that the scheduler execute the slot at the given index, using the provided
790    /// [`DonePredicate`] to determine when the slot is "done", then replace the slot in this
791    /// array and re-enter execution.
792    ///
793    /// Use [`ExecutionResult::execute_slot`] instead of constructing this variant directly.
794    ExecuteSlot(usize, DonePredicate),
795
796    /// Detach the slot at the given index, append that child into the current activation's
797    /// canonical builder, and keep the returned parent as `current_array`.
798    ///
799    /// `Done` finalizes that builder and turns it into the result of the activation.
800    ///
801    /// **Note:** In the single-step executor ([`Executable`] for [`ArrayRef`]), this variant
802    /// drives the entire parent to completion in one call via [`execute_into_builder`], which
803    /// may perform substantially more work than a single `ExecuteSlot` step.
804    AppendChild(usize),
805
806    /// Execution is complete. If no builder is active, the array in the accompanying
807    /// [`ExecutionResult`] is the result. Otherwise, the scheduler finalizes the active
808    /// builder and uses that finished array instead.
809    ///
810    /// The scheduler will continue executing if it has not yet reached the target form.
811    Done,
812}
813
814impl fmt::Debug for ExecutionStep {
815    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
816        match self {
817            ExecutionStep::ExecuteSlot(idx, _) => f.debug_tuple("ExecuteSlot").field(idx).finish(),
818            ExecutionStep::AppendChild(idx) => f.debug_tuple("AppendChild").field(idx).finish(),
819            ExecutionStep::Done => write!(f, "Done"),
820        }
821    }
822}
823
824/// The result of a single execution step on an array encoding.
825///
826/// Combines an [`ArrayRef`] with an [`ExecutionStep`] to tell the scheduler both what to do next
827/// and what array to work with.
828pub struct ExecutionResult {
829    array: ArrayRef,
830    step: ExecutionStep,
831}
832
833impl ExecutionResult {
834    /// Signal that execution is complete with the given result array.
835    pub fn done(result: impl IntoArray) -> Self {
836        Self {
837            array: result.into_array(),
838            step: ExecutionStep::Done,
839        }
840    }
841
842    /// Request execution of slot at `slot_idx` until it matches the given [`Matcher`].
843    ///
844    /// The provided array is the (possibly modified) parent that still needs its slot executed.
845    pub fn execute_slot<M: Matcher>(array: impl IntoArray, slot_idx: usize) -> Self {
846        let array = array.into_array();
847        Self {
848            array,
849            step: ExecutionStep::ExecuteSlot(slot_idx, M::matches),
850        }
851    }
852
853    /// Like [`execute_slot`](Self::execute_slot), but with a [`DonePredicate`] chosen at runtime.
854    pub(crate) fn execute_slot_until(
855        array: ArrayRef,
856        slot_idx: usize,
857        done: DonePredicate,
858    ) -> Self {
859        Self {
860            array,
861            step: ExecutionStep::ExecuteSlot(slot_idx, done),
862        }
863    }
864
865    /// Request that the child slot at `slot_idx` be detached, appended into the current
866    /// activation's canonical builder, and leave the returned parent as the next
867    /// `current_array`.
868    pub fn append_child(array: impl IntoArray, slot_idx: usize) -> Self {
869        let array = array.into_array();
870        Self {
871            array,
872            step: ExecutionStep::AppendChild(slot_idx),
873        }
874    }
875
876    /// Returns a reference to the array.
877    pub fn array(&self) -> &ArrayRef {
878        &self.array
879    }
880
881    /// Returns a reference to the step.
882    pub fn step(&self) -> &ExecutionStep {
883        &self.step
884    }
885
886    /// Decompose into parts.
887    pub fn into_parts(self) -> (ArrayRef, ExecutionStep) {
888        (self.array, self.step)
889    }
890}
891
892impl fmt::Debug for ExecutionResult {
893    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
894        f.debug_struct("ExecutionResult")
895            .field("array", &self.array)
896            .field("step", &self.step)
897            .finish()
898    }
899}
900
901/// Require that a child array matches `$M`. If the child already matches, returns the same
902/// array unchanged. Otherwise, early-returns an [`ExecutionResult`] requesting execution of
903/// child `$idx` until it matches `$M`.
904///
905/// ```ignore
906/// let array = require_child!(array, array.codes(), 0 => Primitive);
907/// let array = require_child!(array, array.values(), 1 => AnyCanonical);
908/// ```
909#[macro_export]
910macro_rules! require_child {
911    ($parent:expr, $child:expr, $idx:expr => $M:ty) => {{
912        if !$child.is::<$M>() {
913            return Ok($crate::ExecutionResult::execute_slot::<$M>(
914                $parent.clone(),
915                $idx,
916            ));
917        }
918        $parent
919    }};
920}
921
922/// The scalar function counterpart of [`require_child!`]: require that input `$idx` of `$args`
923/// matches `$M`. If it does not, early-returns a
924/// [`ScalarFnExecutionResult`](crate::scalar_fn::ScalarFnExecutionResult) asking the executor to
925/// execute that input until it matches, so the function is stepped again with the executed input.
926///
927/// ```ignore
928/// require_input!(args, 0 => AnyColumnar);
929/// ```
930#[macro_export]
931macro_rules! require_input {
932    ($args:expr, $idx:expr => $M:ty) => {
933        if !$args.input_matches($idx, <$M as $crate::matcher::Matcher>::matches)? {
934            return Ok($crate::scalar_fn::ScalarFnExecutionResult::execute_input::<
935                $M,
936            >($idx));
937        }
938    };
939}
940
941/// Like [`require_child!`], but for optional children. If the child is `None`, this is a no-op.
942/// If the child is `Some` but does not match `$M`, early-returns an [`ExecutionResult`] requesting
943/// execution of child `$idx`.
944///
945/// Unlike `require_child!`, this is a statement macro (no value produced) and does not clone
946/// `$parent` - it is moved into the early-return path.
947///
948/// ```ignore
949/// require_opt_child!(array, array.patches().map(|p| p.indices()), 1 => Primitive);
950/// ```
951#[macro_export]
952macro_rules! require_opt_child {
953    ($parent:expr, $child_opt:expr, $idx:expr => $M:ty) => {
954        if $child_opt.is_some_and(|child| !child.is::<$M>()) {
955            return Ok($crate::ExecutionResult::execute_slot::<$M>($parent, $idx));
956        }
957    };
958}
959
960/// Require that patch slots (indices, values, and optionally chunk_offsets) are `Primitive`.
961/// If no patches are present (slots are `None`), this is a no-op.
962///
963/// Like [`require_opt_child!`], `$parent` is moved (not cloned) into the early-return path.
964///
965/// ```ignore
966/// require_patches!(
967///     array,
968///     MySlots::PATCH_INDICES,
969///     MySlots::PATCH_VALUES,
970///     MySlots::PATCH_CHUNK_OFFSETS
971/// );
972/// ```
973#[macro_export]
974macro_rules! require_patches {
975    ($parent:expr, $indices_slot:expr, $values_slot:expr, $chunk_offsets_slot:expr) => {
976        $crate::require_opt_child!(
977            $parent,
978            $parent.slots()[$indices_slot].as_ref(),
979            $indices_slot => $crate::arrays::Primitive
980        );
981        $crate::require_opt_child!(
982            $parent,
983            $parent.slots()[$values_slot].as_ref(),
984            $values_slot => $crate::arrays::Primitive
985        );
986        $crate::require_opt_child!(
987            $parent,
988            $parent.slots()[$chunk_offsets_slot].as_ref(),
989            $chunk_offsets_slot => $crate::arrays::Primitive
990        );
991    };
992}
993
994/// Require that the validity slot is a [`Bool`](crate::arrays::Bool) array. If validity is not
995/// array-backed (e.g. `NonNullable` or `AllValid`), this is a no-op. If it is array-backed but
996/// not `Bool`, early-returns an [`ExecutionResult`] requesting execution of the validity slot.
997///
998/// Like [`require_opt_child!`], `$parent` is moved (not cloned) into the early-return path.
999///
1000/// ```ignore
1001/// require_validity!(array, MySlots::VALIDITY);
1002/// ```
1003#[macro_export]
1004macro_rules! require_validity {
1005    ($parent:expr, $idx:expr) => {
1006        $crate::require_opt_child!(
1007            $parent,
1008            $parent.slots()[$idx].as_ref(),
1009            $idx => $crate::arrays::Bool
1010        );
1011    };
1012}
1013
1014/// Extension trait for creating an execution context from a session.
1015pub trait VortexSessionExecute {
1016    /// Create a new execution context from this session.
1017    fn create_execution_ctx(&self) -> ExecutionCtx;
1018}
1019
1020impl VortexSessionExecute for VortexSession {
1021    fn create_execution_ctx(&self) -> ExecutionCtx {
1022        ExecutionCtx::new(self.clone())
1023    }
1024}
1025
1026#[cfg(test)]
1027mod tests {
1028    use static_assertions::assert_impl_all;
1029    use vortex_session::SessionExt;
1030    use vortex_session::VortexSession;
1031
1032    use super::*;
1033    use crate::VTable as _;
1034    use crate::VortexSessionExecute;
1035    use crate::arrays::Bool;
1036    use crate::arrays::BoolArray;
1037    use crate::arrays::Primitive;
1038    use crate::memory::BufferAllocatorRef;
1039    use crate::memory::MemorySession;
1040    use crate::memory::MemorySessionExt;
1041    use crate::optimizer::kernels::ExecuteParentFn;
1042    use crate::optimizer::kernels::KernelSession;
1043    use crate::optimizer::kernels::execute_parent_key;
1044
1045    assert_impl_all!(ExecutionCtx: Send, Sync);
1046
1047    fn noop_execute_parent(
1048        _child: &ArrayRef,
1049        _parent: &ArrayRef,
1050        _child_idx: usize,
1051        _ctx: &mut ExecutionCtx,
1052    ) -> VortexResult<Option<ArrayRef>> {
1053        Ok(None)
1054    }
1055
1056    #[test]
1057    fn execution_ctx_snapshots_execute_parent_kernels_at_creation() {
1058        let session = VortexSession::empty().with_some(KernelSession::empty());
1059        let key = execute_parent_key(Bool.id(), Primitive.id());
1060
1061        let before_registration = session.create_execution_ctx();
1062        assert!(
1063            !before_registration
1064                .execute_parent_kernels
1065                .contains_key(&key)
1066        );
1067
1068        let kernels = session.kernels();
1069        kernels.register_execute_parent(
1070            Bool.id(),
1071            Primitive.id(),
1072            &[noop_execute_parent as ExecuteParentFn],
1073        );
1074
1075        assert!(
1076            !before_registration
1077                .execute_parent_kernels
1078                .contains_key(&key)
1079        );
1080
1081        let after_registration = session.create_execution_ctx();
1082        assert!(after_registration.execute_parent_kernels.contains_key(&key));
1083    }
1084
1085    #[test]
1086    fn execution_ctx_snapshot_marks_parents_with_kernels() {
1087        let session = VortexSession::empty().with_some(KernelSession::empty());
1088        let bool_array = BoolArray::from_iter([true, false]).into_array();
1089        let primitive = vortex_buffer::buffer![1i32, 2].into_array();
1090
1091        let before = session.create_execution_ctx();
1092        assert!(!has_execute_parent_kernels(
1093            &before.execute_parent_kernels,
1094            &bool_array
1095        ));
1096
1097        session.kernels().register_execute_parent(
1098            Bool.id(),
1099            Primitive.id(),
1100            &[noop_execute_parent as ExecuteParentFn],
1101        );
1102
1103        let after = session.create_execution_ctx();
1104        assert!(has_execute_parent_kernels(
1105            &after.execute_parent_kernels,
1106            &bool_array
1107        ));
1108        assert!(!has_execute_parent_kernels(
1109            &after.execute_parent_kernels,
1110            &primitive
1111        ));
1112    }
1113
1114    #[test]
1115    fn execution_ctx_allocator_override() {
1116        let first = BufferAllocatorRef::new(vortex_buffer::StaticBufferAllocator);
1117        let second = BufferAllocatorRef::new(vortex_buffer::StaticBufferAllocator);
1118        let third = BufferAllocatorRef::new(vortex_buffer::StaticBufferAllocator);
1119        let session = VortexSession::empty()
1120            .with::<MemorySession>()
1121            .with_allocator(first.clone());
1122        let ctx = session.create_execution_ctx();
1123
1124        session
1125            .get_mut::<MemorySession>()
1126            .set_allocator(third.clone());
1127
1128        assert!(session.allocator().ptr_eq(&third));
1129        assert!(ctx.allocator().ptr_eq(&third));
1130
1131        let ctx = ctx.with_allocator(second.clone());
1132        session.get_mut::<MemorySession>().set_allocator(first);
1133
1134        assert!(ctx.allocator().ptr_eq(&second));
1135    }
1136}