Skip to main content

vortex_array/test_harness/trace/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Snapshot-friendly tracing harness for the optimizer and executor.
5//!
6//! # What this records
7//!
8//! [`trace_op`] runs a closure with a thread-local recorder installed. While the recorder is
9//! active, calls to the `trace_op!` macro inside the optimizer and executor push
10//! structured events into the recorder. The recorder produces a [`TraceDisplay`] that renders
11//! as a deterministic, hierarchical text trace suitable for `insta` snapshot assertions.
12//!
13//! Events cover:
14//!
15//! - **Optimization**: optimize/recursive-optimize entry, fixpoint loop iterations, applied
16//!   reduce rules, applied parent-reduce rules.
17//! - **Execution**: `execute_until` iterations, single-step entries, parent kernel attempts and
18//!   matches, slot transitions, builder start/append/finish, and the eventual canonical output.
19//!
20//! Despite the name `trace_op`, the harness is *not* a generic logging facility: it is closely
21//! coupled to the optimizer/executor state machines so that the resulting trace is stable enough
22//! to commit as a snapshot.
23//!
24//! # When to use it
25//!
26//! Use [`trace_op`] to write a regression test that asserts on the sequence of optimizer
27//! rewrites or executor steps an array goes through. Typical scenarios:
28//!
29//! - A reduce rule should fire exactly once on a specific input shape.
30//! - A parent kernel should be tried in a specific order and the first match should win.
31//! - The executor should walk into a slot, finish it, and pop back to the parent without
32//!   building a canonical intermediate.
33//! - A chunked array should drive the builder path rather than the stack path.
34//!
35//! Two resolutions are available:
36//!
37//! - [`TraceResolution::ExecutedOnly`] (default) — only events that actually fired (rule
38//!   rewrites that matched, kernels that succeeded, execution steps that ran). Optimizer
39//!   passes that produced no change are elided.
40//! - [`TraceResolution::Attempts`] — also records declined rule attempts, kernels that did
41//!   not match, and per-loop bookkeeping. Use this when ordering or fall-through matters.
42//!
43//! # Cost and scope
44//!
45//! - Capture is thread-local. Worker threads spawned inside `f` do not inherit the recorder.
46//! - Nested captures return an error so that unrelated traces never merge.
47//! - In release builds and CodSpeed benchmark builds, every `trace_op!` invocation is compiled
48//!   away by the macro's `cfg` gating; this module is then unused. See
49//!   `trace_op!` for the gating rules.
50//!
51//! # Example
52//!
53//! ```ignore
54//! use vortex_array::test_harness::trace::trace_op;
55//!
56//! let traced = trace_op(|| filter_array.optimize())?;
57//! assert!(traced.output.is::<Primitive>());
58//! insta::assert_snapshot!(traced.trace.to_string(), @r"
59//! optimize root=vortex.filter(i32, len=4) session=false
60//!   reduce TrivialFilterRule: vortex.filter(i32, len=4) -> vortex.primitive(i32, len=4)
61//!   done output=vortex.primitive(i32, len=4)
62//! ");
63//! ```
64
65use std::cell::Cell;
66use std::cell::RefCell;
67use std::fmt;
68use std::fmt::Debug;
69use std::fmt::Display;
70use std::sync::atomic::AtomicUsize;
71use std::sync::atomic::Ordering;
72
73use vortex_error::VortexExpect;
74use vortex_error::VortexResult;
75use vortex_error::vortex_err;
76
77use crate::ArrayRef;
78
79/// Controls how much rule and kernel resolution detail is captured.
80#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
81pub enum TraceResolution {
82    /// Record only the operations that actually executed.
83    #[default]
84    ExecutedOnly,
85    /// Also record rule and kernel attempts that matched but declined, or did not match.
86    Attempts,
87}
88
89/// Options for [`trace_op_with`].
90#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
91pub struct TraceOptions {
92    /// The amount of rule and kernel resolution detail to include.
93    pub resolution: TraceResolution,
94}
95
96/// The result of a traced operation.
97#[derive(Clone, Debug)]
98pub struct Traced<T> {
99    /// The value returned by the traced closure.
100    pub output: T,
101    /// A stable, snapshot-friendly rendering of optimizer and execution activity.
102    pub trace: TraceDisplay,
103}
104
105/// A stable, snapshot-friendly trace.
106#[derive(Clone, Debug, Default)]
107pub struct TraceDisplay {
108    options: TraceOptions,
109    events: Vec<TraceEvent>,
110}
111
112impl Display for TraceDisplay {
113    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
114        let hidden_events = self.hidden_events();
115        let mut optimize_depth = 0usize;
116        let mut wrote_event = false;
117
118        for (idx, event) in self.events.iter().enumerate() {
119            if hidden_events[idx] {
120                continue;
121            }
122
123            if event.closes_before(self.options.resolution) {
124                optimize_depth = optimize_depth.saturating_sub(1);
125            }
126
127            if event.is_hidden(self.options.resolution) {
128                continue;
129            }
130
131            if wrote_event {
132                writeln!(f)?;
133            } else {
134                wrote_event = true;
135            }
136
137            write_indent(
138                f,
139                optimize_depth + event.relative_indent(self.options.resolution, optimize_depth > 0),
140            )?;
141            event.fmt_line(f, self.options.resolution)?;
142
143            if event.opens_after(self.options.resolution) {
144                optimize_depth += 1;
145            }
146            if event.closes_after(self.options.resolution) {
147                optimize_depth = optimize_depth.saturating_sub(1);
148            }
149        }
150        Ok(())
151    }
152}
153
154impl TraceDisplay {
155    fn hidden_events(&self) -> Vec<bool> {
156        let mut hidden = vec![false; self.events.len()];
157        if self.options.resolution != TraceResolution::ExecutedOnly {
158            return hidden;
159        }
160
161        let mut optimize_stack = Vec::new();
162        for (idx, event) in self.events.iter().enumerate() {
163            match event {
164                TraceEvent::OptimizeStart { .. } => optimize_stack.push(idx),
165                TraceEvent::OptimizeDone { changed, .. } => {
166                    let Some(start) = optimize_stack.pop() else {
167                        continue;
168                    };
169                    if !changed {
170                        hidden[start..=idx].fill(true);
171                    }
172                }
173                _ => {}
174            }
175        }
176        hidden
177    }
178}
179
180fn write_indent(f: &mut fmt::Formatter<'_>, depth: usize) -> fmt::Result {
181    for _ in 0..depth {
182        f.write_str("  ")?;
183    }
184    Ok(())
185}
186
187/// Run `f` while capturing a trace of the optimizer and executor work it performs.
188///
189/// `f` typically invokes an operation that drives the executor or optimizer, such as
190/// [`ArrayOptimizer::optimize`][crate::optimizer::ArrayOptimizer::optimize] or
191/// [`ArrayRef::execute`][crate::ArrayRef::execute]. While `f` runs,
192/// the optimizer and executor emit structured events via the `trace_op!`
193/// macro into a thread-local recorder. When `f` returns, the recorder is finalized and
194/// returned alongside the closure's output as a [`Traced<T>`].
195///
196/// The default resolution ([`TraceResolution::ExecutedOnly`]) records the rule rewrites,
197/// parent kernels, execution steps, and builder activity that actually executed. Optimizer
198/// passes that produced no change are hidden from the rendered trace. Use [`trace_op_with`]
199/// with [`TraceResolution::Attempts`] when a test needs to assert on declined rule attempts,
200/// kernels that did not match, or other fall-through detail.
201///
202/// # Examples
203///
204/// ```ignore
205/// let traced = trace_op(|| filter_array.optimize())?;
206/// assert!(traced.output.is::<Primitive>());
207/// insta::assert_snapshot!(traced.trace.to_string(), @r"
208/// optimize root=vortex.filter(i32, len=4) session=false
209///   reduce TrivialFilterRule: vortex.filter(i32, len=4) -> vortex.primitive(i32, len=4)
210///   done output=vortex.primitive(i32, len=4)
211/// ");
212/// ```
213///
214/// # Errors
215///
216/// Returns whatever error `f` produces. Returns an error if a recorder is already active on
217/// the current thread — nested traces are not supported.
218pub fn trace_op<T>(f: impl FnOnce() -> VortexResult<T>) -> VortexResult<Traced<T>> {
219    trace_op_with(TraceOptions::default(), f)
220}
221
222/// Run `f` while capturing a trace using `options`.
223///
224/// See [`trace_op`] for the common case. Use this when you need to override the default
225/// [`TraceResolution`] to capture declined rules and unmatched kernels.
226///
227/// Trace capture is thread-local and intentionally does not propagate to worker threads. Nested
228/// trace captures return an error so tests do not accidentally merge unrelated traces.
229pub fn trace_op_with<T>(
230    options: TraceOptions,
231    f: impl FnOnce() -> VortexResult<T>,
232) -> VortexResult<Traced<T>> {
233    let interest = TraceInterest::from(options.resolution);
234    ACTIVE_TRACE.with(|active| {
235        let mut active = active.borrow_mut();
236        if active.is_some() {
237            return Err(vortex_err!("trace_op captures cannot be nested"));
238        }
239        *active = Some(TraceRecorder::new(options));
240        Ok(())
241    })?;
242    TRACE_INTEREST.with(|trace_interest| trace_interest.set(interest));
243    ACTIVE_TRACE_COUNT.fetch_add(1, Ordering::Relaxed);
244    if interest == TraceInterest::Attempts {
245        ATTEMPTS_TRACE_COUNT.fetch_add(1, Ordering::Relaxed);
246    }
247
248    let guard = ActiveTraceGuard { interest };
249    let output = f();
250    let recorder = ACTIVE_TRACE.with(|active| {
251        active
252            .borrow_mut()
253            .take()
254            .vortex_expect("trace recorder must be installed")
255    });
256    drop(guard);
257
258    output.map(|output| Traced {
259        output,
260        trace: recorder.finish(),
261    })
262}
263
264/// Returns true when the current thread has an active trace recorder.
265#[allow(clippy::inline_always)]
266#[inline(always)]
267pub(crate) fn is_active() -> bool {
268    if ACTIVE_TRACE_COUNT.load(Ordering::Relaxed) == 0 {
269        return false;
270    }
271    TRACE_INTEREST.with(|interest| interest.get().is_active())
272}
273
274#[allow(clippy::inline_always)]
275#[inline(always)]
276fn attempts_enabled() -> bool {
277    if ATTEMPTS_TRACE_COUNT.load(Ordering::Relaxed) == 0 {
278        return false;
279    }
280    TRACE_INTEREST.with(|interest| interest.get() == TraceInterest::Attempts)
281}
282
283#[derive(Clone, Copy, Debug)]
284enum TraceSource {
285    Static,
286    Session(usize),
287}
288
289impl Display for TraceSource {
290    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
291        match self {
292            TraceSource::Static => f.write_str("static"),
293            TraceSource::Session(idx) => write!(f, "session[{idx}]"),
294        }
295    }
296}
297
298#[derive(Clone, Copy, Debug)]
299enum AttemptOutcome {
300    Declined,
301    NoMatch,
302}
303
304impl Display for AttemptOutcome {
305    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
306        match self {
307            AttemptOutcome::Declined => f.write_str("declined"),
308            AttemptOutcome::NoMatch => f.write_str("no-match"),
309        }
310    }
311}
312
313#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
314enum TraceInterest {
315    #[default]
316    Off,
317    ExecutedOnly,
318    Attempts,
319}
320
321impl TraceInterest {
322    #[inline]
323    fn is_active(self) -> bool {
324        self != Self::Off
325    }
326}
327
328impl From<TraceResolution> for TraceInterest {
329    fn from(resolution: TraceResolution) -> Self {
330        match resolution {
331            TraceResolution::ExecutedOnly => Self::ExecutedOnly,
332            TraceResolution::Attempts => Self::Attempts,
333        }
334    }
335}
336
337/// Snapshot-friendly wrapper around [`ArrayRef`] that renders the encoding, dtype, and length
338/// using the canonical [`Display`] format (`vortex.primitive(i32, len=4)`).
339///
340/// Carries a clone of the [`ArrayRef`] instead of duplicating fields,
341/// so trace events stay small and share the same rendering as every other `{array}` print in
342/// the codebase.
343#[derive(Clone, Debug)]
344pub(crate) struct ArraySummary(ArrayRef);
345
346impl ArraySummary {
347    pub(crate) fn new(array: &ArrayRef) -> Self {
348        Self(array.clone())
349    }
350}
351
352impl Display for ArraySummary {
353    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
354        Display::fmt(&self.0, f)
355    }
356}
357
358pub(crate) fn record_optimize_start(root: &ArrayRef, session: bool) {
359    record(TraceEvent::OptimizeStart {
360        root: ArraySummary::new(root),
361        session,
362    });
363}
364
365pub(crate) fn record_optimize_loop_start(array: &ArrayRef) {
366    if !attempts_enabled() {
367        return;
368    }
369    record(TraceEvent::OptimizeLoopStart {
370        array: ArraySummary::new(array),
371    });
372}
373
374pub(crate) fn record_optimize_loop_end() {
375    if !attempts_enabled() {
376        return;
377    }
378    record(TraceEvent::OptimizeLoopEnd);
379}
380
381pub(crate) fn record_optimize_reduce_none(array: &ArrayRef) {
382    if !attempts_enabled() {
383        return;
384    }
385    record(TraceEvent::PhaseNone {
386        indent: 0,
387        phase: "reduce",
388        subject: "array",
389        array: ArraySummary::new(array),
390    });
391}
392
393pub(crate) fn record_optimize_parent_reduce_none(array: &ArrayRef) {
394    if !attempts_enabled() {
395        return;
396    }
397    record(TraceEvent::PhaseNone {
398        indent: 0,
399        phase: "reduce_parent",
400        subject: "array",
401        array: ArraySummary::new(array),
402    });
403}
404
405pub(crate) fn record_optimize_done(output: &ArrayRef, changed: bool) {
406    record(TraceEvent::OptimizeDone {
407        output: ArraySummary::new(output),
408        changed,
409    });
410}
411
412pub(crate) fn record_reduce_applied(array: &ArrayRef, rule: &dyn Debug, output: &ArrayRef) {
413    record(TraceEvent::ReduceApplied {
414        array: ArraySummary::new(array),
415        rule: compact_label(rule),
416        output: ArraySummary::new(output),
417    });
418}
419
420pub(crate) fn record_reduce_declined(array: &ArrayRef, rule: &dyn Debug) {
421    if !attempts_enabled() {
422        return;
423    }
424    record(TraceEvent::ReduceAttempt {
425        array: ArraySummary::new(array),
426        rule: compact_label(rule),
427        outcome: AttemptOutcome::Declined,
428    });
429}
430
431pub(crate) fn record_session_parent_reduce_applied(
432    parent: &ArrayRef,
433    child: &ArrayRef,
434    slot_idx: usize,
435    plugin_idx: usize,
436    output: &ArrayRef,
437) {
438    record_parent_reduce_applied(
439        parent,
440        child,
441        slot_idx,
442        TraceSource::Session(plugin_idx),
443        "reduce_parent_fn",
444        output,
445    );
446}
447
448pub(crate) fn record_session_parent_reduce_declined(
449    parent: &ArrayRef,
450    child: &ArrayRef,
451    slot_idx: usize,
452    plugin_idx: usize,
453) {
454    record_parent_reduce_attempt(
455        parent,
456        child,
457        slot_idx,
458        TraceSource::Session(plugin_idx),
459        "reduce_parent_fn",
460        AttemptOutcome::Declined,
461    );
462}
463
464pub(crate) fn record_static_parent_reduce_no_match(
465    parent: &ArrayRef,
466    child: &ArrayRef,
467    slot_idx: usize,
468    rule: &dyn Debug,
469) {
470    record_parent_reduce_attempt(
471        parent,
472        child,
473        slot_idx,
474        TraceSource::Static,
475        compact_label(rule),
476        AttemptOutcome::NoMatch,
477    );
478}
479
480pub(crate) fn record_static_parent_reduce_applied(
481    parent: &ArrayRef,
482    child: &ArrayRef,
483    slot_idx: usize,
484    rule: &dyn Debug,
485    output: &ArrayRef,
486) {
487    record_parent_reduce_applied(
488        parent,
489        child,
490        slot_idx,
491        TraceSource::Static,
492        compact_label(rule),
493        output,
494    );
495}
496
497pub(crate) fn record_static_parent_reduce_declined(
498    parent: &ArrayRef,
499    child: &ArrayRef,
500    slot_idx: usize,
501    rule: &dyn Debug,
502) {
503    record_parent_reduce_attempt(
504        parent,
505        child,
506        slot_idx,
507        TraceSource::Static,
508        compact_label(rule),
509        AttemptOutcome::Declined,
510    );
511}
512
513fn record_parent_reduce_attempt(
514    parent: &ArrayRef,
515    child: &ArrayRef,
516    slot_idx: usize,
517    source: TraceSource,
518    rule: impl Into<String>,
519    outcome: AttemptOutcome,
520) {
521    if !attempts_enabled() {
522        return;
523    }
524    record(TraceEvent::ParentReduceAttempt {
525        parent: ArraySummary::new(parent),
526        child: ArraySummary::new(child),
527        slot_idx,
528        source,
529        rule: rule.into(),
530        outcome,
531    });
532}
533
534fn record_parent_reduce_applied(
535    parent: &ArrayRef,
536    child: &ArrayRef,
537    slot_idx: usize,
538    source: TraceSource,
539    rule: impl Into<String>,
540    output: &ArrayRef,
541) {
542    record(TraceEvent::ParentReduceApplied {
543        parent: ArraySummary::new(parent),
544        child: ArraySummary::new(child),
545        slot_idx,
546        source,
547        rule: rule.into(),
548        output: ArraySummary::new(output),
549    });
550}
551
552pub(crate) fn record_execute_until_start<M>(root: &ArrayRef) {
553    record(TraceEvent::ExecuteUntilStart {
554        target: short_type_name::<M>(),
555        root: ArraySummary::new(root),
556    });
557}
558
559pub(crate) fn record_execute_until_iteration(
560    iteration: usize,
561    current: &ArrayRef,
562    stack_parent: Option<(&ArrayRef, usize)>,
563    builder_active: bool,
564) {
565    record(TraceEvent::ExecuteUntilIteration {
566        iteration,
567        current: ArraySummary::new(current),
568        stack_parent: stack_parent.map(|(array, slot_idx)| (ArraySummary::new(array), slot_idx)),
569        builder_active,
570    });
571}
572
573pub(crate) fn record_execute_until_done_check(target: bool, canonical: bool) {
574    if !attempts_enabled() {
575        return;
576    }
577    record(TraceEvent::ExecuteUntilDoneCheck { target, canonical });
578}
579
580pub(crate) fn record_execute_until_return(output: &ArrayRef) {
581    record(TraceEvent::ExecuteUntilReturn {
582        output: ArraySummary::new(output),
583    });
584}
585
586pub(crate) fn record_execute_until_pop_frame(slot_idx: usize, output: &ArrayRef) {
587    record(TraceEvent::ExecuteUntilPopFrame {
588        slot_idx,
589        output: ArraySummary::new(output),
590    });
591}
592
593pub(crate) fn record_session_execute_parent_applied(
594    phase: &'static str,
595    parent: &ArrayRef,
596    child: &ArrayRef,
597    slot_idx: usize,
598    plugin_idx: usize,
599    output: &ArrayRef,
600) {
601    record_execute_parent_applied(
602        phase,
603        parent,
604        child,
605        slot_idx,
606        TraceSource::Session(plugin_idx),
607        "execute_parent_fn",
608        output,
609    );
610}
611
612pub(crate) fn record_session_execute_parent_declined(
613    phase: &'static str,
614    parent: &ArrayRef,
615    child: &ArrayRef,
616    slot_idx: usize,
617    plugin_idx: usize,
618) {
619    record_execute_parent_attempt(
620        phase,
621        parent,
622        child,
623        slot_idx,
624        TraceSource::Session(plugin_idx),
625        "execute_parent_fn",
626        AttemptOutcome::Declined,
627    );
628}
629
630fn record_execute_parent_attempt(
631    phase: &'static str,
632    parent: &ArrayRef,
633    child: &ArrayRef,
634    slot_idx: usize,
635    source: TraceSource,
636    kernel: impl Into<String>,
637    outcome: AttemptOutcome,
638) {
639    if !attempts_enabled() {
640        return;
641    }
642    record(TraceEvent::ExecuteParentAttempt {
643        phase,
644        parent: ArraySummary::new(parent),
645        child: ArraySummary::new(child),
646        slot_idx,
647        source,
648        kernel: kernel.into(),
649        outcome,
650    });
651}
652
653fn record_execute_parent_applied(
654    phase: &'static str,
655    parent: &ArrayRef,
656    child: &ArrayRef,
657    slot_idx: usize,
658    source: TraceSource,
659    kernel: impl Into<String>,
660    output: &ArrayRef,
661) {
662    record(TraceEvent::ExecuteParentApplied {
663        phase,
664        parent: ArraySummary::new(parent),
665        child: ArraySummary::new(child),
666        slot_idx,
667        source,
668        kernel: kernel.into(),
669        output: ArraySummary::new(output),
670    });
671}
672
673pub(crate) fn record_execute_parent_none(phase: &'static str, current: &ArrayRef) {
674    if !attempts_enabled() {
675        return;
676    }
677    record(TraceEvent::PhaseNone {
678        indent: 2,
679        phase,
680        subject: "current",
681        array: ArraySummary::new(current),
682    });
683}
684
685pub(crate) fn record_execute_optimized(input: &ArrayRef, output: &ArrayRef) {
686    let changed = !ArrayRef::ptr_eq(input, output);
687    if !changed && !attempts_enabled() {
688        return;
689    }
690    record(TraceEvent::ExecuteOptimized {
691        input: ArraySummary::new(input),
692        output: ArraySummary::new(output),
693        changed,
694    });
695}
696
697pub(crate) fn record_execute_encoding(array: &ArrayRef) {
698    if !attempts_enabled() {
699        return;
700    }
701    record(TraceEvent::ExecuteEncoding {
702        array: ArraySummary::new(array),
703    });
704}
705
706pub(crate) fn record_execute_slot(slot_idx: usize, parent: &ArrayRef, child: &ArrayRef) {
707    record(TraceEvent::SlotTransition {
708        step: "ExecuteSlot",
709        slot_idx,
710        parent: ArraySummary::new(parent),
711        child: ArraySummary::new(child),
712    });
713}
714
715pub(crate) fn record_builder_start(array: &ArrayRef) {
716    record(TraceEvent::BuilderEvent {
717        action: "start",
718        subject: "array",
719        array: ArraySummary::new(array),
720    });
721}
722
723pub(crate) fn record_append_child(slot_idx: usize, parent: &ArrayRef, child: &ArrayRef) {
724    record(TraceEvent::SlotTransition {
725        step: "AppendChild",
726        slot_idx,
727        parent: ArraySummary::new(parent),
728        child: ArraySummary::new(child),
729    });
730}
731
732pub(crate) fn record_builder_append(child: &ArrayRef) {
733    record(TraceEvent::BuilderEvent {
734        action: "append",
735        subject: "child",
736        array: ArraySummary::new(child),
737    });
738}
739
740pub(crate) fn record_execute_done(array: &ArrayRef) {
741    record(TraceEvent::ExecuteDone {
742        array: ArraySummary::new(array),
743    });
744}
745
746pub(crate) fn record_builder_finish(output: &ArrayRef) {
747    record(TraceEvent::BuilderEvent {
748        action: "finish",
749        subject: "output",
750        array: ArraySummary::new(output),
751    });
752}
753
754pub(crate) fn record_single_step_start(array: &ArrayRef) {
755    record(TraceEvent::SingleStepStart {
756        array: ArraySummary::new(array),
757    });
758}
759
760pub(crate) fn record_single_step_phase_none(phase: &'static str, array: &ArrayRef) {
761    if !attempts_enabled() {
762        return;
763    }
764    record(TraceEvent::PhaseNone {
765        indent: 1,
766        phase,
767        subject: "array",
768        array: ArraySummary::new(array),
769    });
770}
771
772pub(crate) fn record_single_step_applied(phase: &'static str, input: &ArrayRef, output: &ArrayRef) {
773    record(TraceEvent::SingleStepApplied {
774        phase,
775        input: ArraySummary::new(input),
776        output: ArraySummary::new(output),
777    });
778}
779
780fn record(event: TraceEvent) {
781    ACTIVE_TRACE.with(|active| {
782        if let Some(recorder) = active.borrow_mut().as_mut() {
783            recorder.events.push(event);
784        }
785    });
786}
787
788fn compact_label(value: &dyn Debug) -> String {
789    let label = format!("{value:?}");
790    if let Some(label) = adapter_field(&label, "rule") {
791        return label.to_string();
792    }
793    if let Some(label) = adapter_field(&label, "kernel") {
794        return label.to_string();
795    }
796    label
797}
798
799fn adapter_field<'a>(label: &'a str, field: &str) -> Option<&'a str> {
800    let marker = format!("{field}: ");
801    let start = label.find(&marker)? + marker.len();
802    let rest = &label[start..];
803    let end = rest.rfind(" }")?;
804    Some(&rest[..end])
805}
806
807fn short_type_name<T>() -> String {
808    std::any::type_name::<T>()
809        .rsplit("::")
810        .next()
811        .vortex_expect("type names are never empty")
812        .to_string()
813}
814
815thread_local! {
816    static TRACE_INTEREST: Cell<TraceInterest> = const { Cell::new(TraceInterest::Off) };
817    static ACTIVE_TRACE: RefCell<Option<TraceRecorder>> = const { RefCell::new(None) };
818}
819
820static ACTIVE_TRACE_COUNT: AtomicUsize = AtomicUsize::new(0);
821static ATTEMPTS_TRACE_COUNT: AtomicUsize = AtomicUsize::new(0);
822
823struct ActiveTraceGuard {
824    interest: TraceInterest,
825}
826
827impl Drop for ActiveTraceGuard {
828    fn drop(&mut self) {
829        if self.interest == TraceInterest::Attempts {
830            ATTEMPTS_TRACE_COUNT.fetch_sub(1, Ordering::Relaxed);
831        }
832        ACTIVE_TRACE_COUNT.fetch_sub(1, Ordering::Relaxed);
833        TRACE_INTEREST.with(|interest| interest.set(TraceInterest::Off));
834        ACTIVE_TRACE.with(|active| {
835            active.borrow_mut().take();
836        });
837    }
838}
839
840#[derive(Debug)]
841struct TraceRecorder {
842    options: TraceOptions,
843    events: Vec<TraceEvent>,
844}
845
846impl TraceRecorder {
847    fn new(options: TraceOptions) -> Self {
848        Self {
849            options,
850            events: Vec::new(),
851        }
852    }
853
854    fn finish(self) -> TraceDisplay {
855        TraceDisplay {
856            options: self.options,
857            events: self.events,
858        }
859    }
860}
861
862#[derive(Clone, Debug)]
863enum TraceEvent {
864    OptimizeStart {
865        root: ArraySummary,
866        session: bool,
867    },
868    OptimizeLoopStart {
869        array: ArraySummary,
870    },
871    OptimizeLoopEnd,
872    OptimizeDone {
873        output: ArraySummary,
874        changed: bool,
875    },
876    ReduceAttempt {
877        array: ArraySummary,
878        rule: String,
879        outcome: AttemptOutcome,
880    },
881    ReduceApplied {
882        array: ArraySummary,
883        rule: String,
884        output: ArraySummary,
885    },
886    ParentReduceAttempt {
887        parent: ArraySummary,
888        child: ArraySummary,
889        slot_idx: usize,
890        source: TraceSource,
891        rule: String,
892        outcome: AttemptOutcome,
893    },
894    ParentReduceApplied {
895        parent: ArraySummary,
896        child: ArraySummary,
897        slot_idx: usize,
898        source: TraceSource,
899        rule: String,
900        output: ArraySummary,
901    },
902    ExecuteUntilStart {
903        target: String,
904        root: ArraySummary,
905    },
906    ExecuteUntilIteration {
907        iteration: usize,
908        current: ArraySummary,
909        stack_parent: Option<(ArraySummary, usize)>,
910        builder_active: bool,
911    },
912    ExecuteUntilDoneCheck {
913        target: bool,
914        canonical: bool,
915    },
916    ExecuteUntilReturn {
917        output: ArraySummary,
918    },
919    ExecuteUntilPopFrame {
920        slot_idx: usize,
921        output: ArraySummary,
922    },
923    ExecuteParentAttempt {
924        phase: &'static str,
925        parent: ArraySummary,
926        child: ArraySummary,
927        slot_idx: usize,
928        source: TraceSource,
929        kernel: String,
930        outcome: AttemptOutcome,
931    },
932    ExecuteParentApplied {
933        phase: &'static str,
934        parent: ArraySummary,
935        child: ArraySummary,
936        slot_idx: usize,
937        source: TraceSource,
938        kernel: String,
939        output: ArraySummary,
940    },
941    PhaseNone {
942        indent: usize,
943        phase: &'static str,
944        subject: &'static str,
945        array: ArraySummary,
946    },
947    ExecuteOptimized {
948        input: ArraySummary,
949        output: ArraySummary,
950        changed: bool,
951    },
952    ExecuteEncoding {
953        array: ArraySummary,
954    },
955    SlotTransition {
956        step: &'static str,
957        slot_idx: usize,
958        parent: ArraySummary,
959        child: ArraySummary,
960    },
961    BuilderEvent {
962        action: &'static str,
963        subject: &'static str,
964        array: ArraySummary,
965    },
966    ExecuteDone {
967        array: ArraySummary,
968    },
969    SingleStepStart {
970        array: ArraySummary,
971    },
972    SingleStepApplied {
973        phase: &'static str,
974        input: ArraySummary,
975        output: ArraySummary,
976    },
977}
978
979impl TraceEvent {
980    fn is_hidden(&self, resolution: TraceResolution) -> bool {
981        match resolution {
982            TraceResolution::Attempts => matches!(self, TraceEvent::OptimizeLoopEnd),
983            TraceResolution::ExecutedOnly => matches!(
984                self,
985                TraceEvent::OptimizeLoopStart { .. }
986                    | TraceEvent::OptimizeLoopEnd
987                    | TraceEvent::PhaseNone { .. }
988                    | TraceEvent::ExecuteUntilDoneCheck { .. }
989                    | TraceEvent::ExecuteEncoding { .. }
990                    | TraceEvent::ExecuteOptimized { changed: false, .. }
991                    | TraceEvent::ExecuteParentAttempt { .. }
992                    | TraceEvent::ReduceAttempt { .. }
993                    | TraceEvent::ParentReduceAttempt { .. }
994            ),
995        }
996    }
997
998    fn opens_after(&self, resolution: TraceResolution) -> bool {
999        match resolution {
1000            TraceResolution::Attempts => matches!(
1001                self,
1002                TraceEvent::OptimizeStart { .. } | TraceEvent::OptimizeLoopStart { .. }
1003            ),
1004            TraceResolution::ExecutedOnly => matches!(self, TraceEvent::OptimizeStart { .. }),
1005        }
1006    }
1007
1008    fn closes_before(&self, resolution: TraceResolution) -> bool {
1009        match resolution {
1010            TraceResolution::Attempts => matches!(self, TraceEvent::OptimizeLoopEnd),
1011            TraceResolution::ExecutedOnly => false,
1012        }
1013    }
1014
1015    fn closes_after(&self, _resolution: TraceResolution) -> bool {
1016        matches!(self, TraceEvent::OptimizeDone { .. })
1017    }
1018
1019    fn relative_indent(&self, _resolution: TraceResolution, in_optimize_scope: bool) -> usize {
1020        match self {
1021            TraceEvent::OptimizeStart { .. }
1022            | TraceEvent::OptimizeLoopStart { .. }
1023            | TraceEvent::OptimizeDone { .. } => 0,
1024            TraceEvent::ReduceAttempt { .. }
1025            | TraceEvent::ReduceApplied { .. }
1026            | TraceEvent::ParentReduceAttempt { .. }
1027            | TraceEvent::ParentReduceApplied { .. }
1028                if in_optimize_scope =>
1029            {
1030                0
1031            }
1032            TraceEvent::PhaseNone { indent, .. } => *indent,
1033            TraceEvent::ReduceAttempt { .. }
1034            | TraceEvent::ReduceApplied { .. }
1035            | TraceEvent::ParentReduceAttempt { .. }
1036            | TraceEvent::ParentReduceApplied { .. }
1037            | TraceEvent::ExecuteUntilDoneCheck { .. }
1038            | TraceEvent::ExecuteUntilPopFrame { .. }
1039            | TraceEvent::ExecuteParentAttempt { .. }
1040            | TraceEvent::ExecuteParentApplied { .. }
1041            | TraceEvent::ExecuteOptimized { .. }
1042            | TraceEvent::ExecuteEncoding { .. }
1043            | TraceEvent::SlotTransition { .. }
1044            | TraceEvent::BuilderEvent { .. }
1045            | TraceEvent::ExecuteDone { .. } => 2,
1046            TraceEvent::ExecuteUntilIteration { .. }
1047            | TraceEvent::ExecuteUntilReturn { .. }
1048            | TraceEvent::SingleStepApplied { .. } => 1,
1049            TraceEvent::OptimizeLoopEnd
1050            | TraceEvent::ExecuteUntilStart { .. }
1051            | TraceEvent::SingleStepStart { .. } => 0,
1052        }
1053    }
1054
1055    fn fmt_line(&self, f: &mut fmt::Formatter<'_>, resolution: TraceResolution) -> fmt::Result {
1056        match self {
1057            TraceEvent::OptimizeStart { root, session } => {
1058                write!(f, "optimize root={root} session={session}")
1059            }
1060            TraceEvent::OptimizeLoopStart { array } => {
1061                write!(f, "loop input={array}")
1062            }
1063            TraceEvent::OptimizeLoopEnd => Ok(()),
1064            TraceEvent::OptimizeDone { output, changed } => match resolution {
1065                TraceResolution::Attempts => write!(f, "done output={output} changed={changed}"),
1066                TraceResolution::ExecutedOnly => write!(f, "done output={output}"),
1067            },
1068            TraceEvent::ReduceAttempt {
1069                array,
1070                rule,
1071                outcome,
1072            } => write!(
1073                f,
1074                "reduce attempt array={array} source=static rule={rule} outcome={outcome}"
1075            ),
1076            TraceEvent::ReduceApplied {
1077                array,
1078                rule,
1079                output,
1080            } => match resolution {
1081                TraceResolution::Attempts => write!(
1082                    f,
1083                    "reduce applied array={array} source=static rule={rule} output={output}"
1084                ),
1085                TraceResolution::ExecutedOnly => {
1086                    write!(f, "reduce {rule}: {array} -> {output}")
1087                }
1088            },
1089            TraceEvent::ParentReduceAttempt {
1090                parent,
1091                child,
1092                slot_idx,
1093                source,
1094                rule,
1095                outcome,
1096            } => write!(
1097                f,
1098                "reduce_parent attempt slot={slot_idx} parent={parent} child={child} source={source} rule={rule} outcome={outcome}"
1099            ),
1100            TraceEvent::ParentReduceApplied {
1101                parent,
1102                child,
1103                slot_idx,
1104                source,
1105                rule,
1106                output,
1107            } => match resolution {
1108                TraceResolution::Attempts => write!(
1109                    f,
1110                    "reduce_parent applied slot={slot_idx} parent={parent} child={child} source={source} rule={rule} output={output}"
1111                ),
1112                TraceResolution::ExecutedOnly => write!(
1113                    f,
1114                    "reduce_parent {source}:{rule} slot={slot_idx} parent={parent} child={child} -> {output}"
1115                ),
1116            },
1117            TraceEvent::ExecuteUntilStart { target, root } => {
1118                write!(f, "execute_until target={target} root={root}")
1119            }
1120            TraceEvent::ExecuteUntilIteration {
1121                iteration,
1122                current,
1123                stack_parent,
1124                builder_active,
1125            } => {
1126                write!(f, "iter {iteration} current={current}")?;
1127                if let Some((parent, slot_idx)) = stack_parent {
1128                    write!(f, " stack_parent={parent} slot={slot_idx}")?;
1129                }
1130                write!(f, " builder_active={builder_active}")
1131            }
1132            TraceEvent::ExecuteUntilDoneCheck { target, canonical } => {
1133                write!(f, "done_check target={target} canonical={canonical}")
1134            }
1135            TraceEvent::ExecuteUntilReturn { output } => {
1136                write!(f, "return output={output}")
1137            }
1138            TraceEvent::ExecuteUntilPopFrame { slot_idx, output } => {
1139                write!(f, "pop_frame slot={slot_idx} output={output}")
1140            }
1141            TraceEvent::ExecuteParentAttempt {
1142                phase,
1143                parent,
1144                child,
1145                slot_idx,
1146                source,
1147                kernel,
1148                outcome,
1149            } => write!(
1150                f,
1151                "{phase} attempt slot={slot_idx} parent={parent} child={child} source={source} kernel={kernel} outcome={outcome}"
1152            ),
1153            TraceEvent::ExecuteParentApplied {
1154                phase,
1155                parent,
1156                child,
1157                slot_idx,
1158                source,
1159                kernel,
1160                output,
1161            } => match resolution {
1162                TraceResolution::Attempts => write!(
1163                    f,
1164                    "{phase} applied slot={slot_idx} parent={parent} child={child} source={source} kernel={kernel} output={output}"
1165                ),
1166                TraceResolution::ExecutedOnly => write!(
1167                    f,
1168                    "{phase} {source}:{kernel} slot={slot_idx} parent={parent} child={child} -> {output}"
1169                ),
1170            },
1171            TraceEvent::PhaseNone {
1172                phase,
1173                subject,
1174                array,
1175                ..
1176            } => {
1177                write!(f, "{phase} none {subject}={array}")
1178            }
1179            TraceEvent::ExecuteOptimized {
1180                input,
1181                output,
1182                changed,
1183            } => match resolution {
1184                TraceResolution::Attempts => write!(
1185                    f,
1186                    "optimize_ctx input={input} output={output} changed={changed}"
1187                ),
1188                TraceResolution::ExecutedOnly => write!(f, "optimize_ctx {input} -> {output}"),
1189            },
1190            TraceEvent::ExecuteEncoding { array } => {
1191                write!(f, "execute encoding={array}")
1192            }
1193            TraceEvent::SlotTransition {
1194                step,
1195                slot_idx,
1196                parent,
1197                child,
1198            } => write!(f, "{step} slot={slot_idx} parent={parent} child={child}"),
1199            TraceEvent::ExecuteDone { array } => {
1200                write!(f, "Done array={array}")
1201            }
1202            TraceEvent::BuilderEvent {
1203                action,
1204                subject,
1205                array,
1206            } => {
1207                write!(f, "builder {action} {subject}={array}")
1208            }
1209            TraceEvent::SingleStepStart { array } => {
1210                write!(f, "execute_step input={array}")
1211            }
1212            TraceEvent::SingleStepApplied {
1213                phase,
1214                input,
1215                output,
1216            } => match resolution {
1217                TraceResolution::Attempts => {
1218                    write!(f, "{phase} applied input={input} output={output}")
1219                }
1220                TraceResolution::ExecutedOnly => write!(f, "{phase} {input} -> {output}"),
1221            },
1222        }
1223    }
1224}
1225
1226#[cfg(test)]
1227mod tests;