miden_air/lookup/debug/trace/
builder.rs

1//! `DebugTraceBuilder` — the `LookupBuilder` adapter that updates
2//! [`super::DebugTraceState`] per row of a concrete main trace.
3//!
4//! Pure implementation detail: instantiation happens inside
5//! `super::run_trace_walk`. The builder, column, group, and batch handles all collapse
6//! their associated types to `Felt` / `QuadFelt`.
7
8use alloc::{format, string::ToString};
9
10use miden_core::field::{PrimeCharacteristicRing, QuadFelt};
11use miden_crypto::stark::air::RowWindow;
12
13use super::{
14    super::super::{
15        BoundaryBuilder, Challenges, Deg, LookupBatch, LookupBuilder, LookupColumn, LookupGroup,
16        LookupMessage,
17    },
18    DebugTraceState, MutualExclusionViolation, PushRecord,
19};
20use crate::Felt;
21
22// BUILDER
23// ================================================================================================
24
25/// Real-trace `LookupBuilder` that updates [`super::DebugTraceState`] per row.
26pub struct DebugTraceBuilder<'a> {
27    main: RowWindow<'a, Felt>,
28    periodic_values: &'a [Felt],
29    challenges: &'a Challenges<QuadFelt>,
30    state: &'a mut DebugTraceState,
31    row_idx: usize,
32    column_idx: usize,
33}
34
35impl<'a> DebugTraceBuilder<'a> {
36    pub fn new(
37        main: RowWindow<'a, Felt>,
38        periodic_values: &'a [Felt],
39        challenges: &'a Challenges<QuadFelt>,
40        state: &'a mut DebugTraceState,
41        row_idx: usize,
42    ) -> Self {
43        Self {
44            main,
45            periodic_values,
46            challenges,
47            state,
48            row_idx,
49            column_idx: 0,
50        }
51    }
52}
53
54impl<'a> LookupBuilder for DebugTraceBuilder<'a> {
55    type F = Felt;
56    type Expr = Felt;
57    type Var = Felt;
58
59    type EF = QuadFelt;
60    type ExprEF = QuadFelt;
61    type VarEF = QuadFelt;
62
63    type PeriodicVar = Felt;
64
65    type MainWindow = RowWindow<'a, Felt>;
66
67    type Column<'c>
68        = DebugTraceColumn<'c>
69    where
70        Self: 'c;
71
72    fn main(&self) -> Self::MainWindow {
73        self.main
74    }
75
76    fn periodic_values(&self) -> &[Self::PeriodicVar] {
77        self.periodic_values
78    }
79
80    fn next_column<'c, R>(
81        &'c mut self,
82        f: impl FnOnce(&mut Self::Column<'c>) -> R,
83        _deg: Deg,
84    ) -> R {
85        let mut col = DebugTraceColumn {
86            challenges: self.challenges,
87            state: &mut *self.state,
88            row_idx: self.row_idx,
89            column_idx: self.column_idx,
90            next_group_idx: 0,
91        };
92        let result = f(&mut col);
93        self.column_idx += 1;
94        result
95    }
96}
97
98// COLUMN
99// ================================================================================================
100
101pub struct DebugTraceColumn<'c> {
102    challenges: &'c Challenges<QuadFelt>,
103    state: &'c mut DebugTraceState,
104    row_idx: usize,
105    column_idx: usize,
106    next_group_idx: usize,
107}
108
109impl<'c> DebugTraceColumn<'c> {
110    /// Common path shared by `group` and `group_with_cached_encoding`. Opens a group,
111    /// drives the caller's closure, folds the group's `(V_g, U_g)` into the column's
112    /// running `(V_col, U_col)`, and (for cached-encoding groups) records any mutex
113    /// violation.
114    fn open_group<'g>(
115        &'g mut self,
116        is_cached_encoding: bool,
117        f: impl FnOnce(&mut DebugTraceGroup<'g>),
118    ) {
119        let group_idx = self.next_group_idx;
120        let column_idx = self.column_idx;
121        let row_idx = self.row_idx;
122
123        let mut group = DebugTraceGroup {
124            challenges: self.challenges,
125            state: &mut *self.state,
126            u: QuadFelt::ONE,
127            v: QuadFelt::ZERO,
128            row_idx,
129            column_idx,
130            group_idx,
131            check_mutex: is_cached_encoding,
132            active_flag_count: 0,
133        };
134        f(&mut group);
135
136        if group.check_mutex && group.active_flag_count > 1 {
137            group.state.mutex_violations.push(MutualExclusionViolation {
138                row: row_idx,
139                column_idx,
140                group_idx,
141                active_flags: group.active_flag_count,
142            });
143        }
144        // Fold `(V_g, U_g)` into `(V_col, U_col)`:  (V, U) ← (V·U_g + V_g·U, U·U_g)
145        let (v_col, u_col) = group.state.column_folds[column_idx];
146        group.state.column_folds[column_idx] = (v_col * group.u + group.v * u_col, u_col * group.u);
147
148        self.next_group_idx += 1;
149    }
150}
151
152impl<'c> LookupColumn for DebugTraceColumn<'c> {
153    type Expr = Felt;
154    type ExprEF = QuadFelt;
155
156    type Group<'g>
157        = DebugTraceGroup<'g>
158    where
159        Self: 'g;
160
161    fn group<'g>(
162        &'g mut self,
163        _name: &'static str,
164        f: impl FnOnce(&mut Self::Group<'g>),
165        _deg: Deg,
166    ) {
167        self.open_group(false, f);
168    }
169
170    fn group_with_cached_encoding<'g>(
171        &'g mut self,
172        _name: &'static str,
173        canonical: impl FnOnce(&mut Self::Group<'g>),
174        _encoded: impl FnOnce(&mut Self::Group<'g>),
175        _deg: Deg,
176    ) {
177        // Run only the canonical closure: both closures must describe the same
178        // interaction set by contract (`DebugStructureBuilder` verifies their folds
179        // agree on sampled rows), and running both here would double-count balance
180        // multiplicities.
181        self.open_group(true, canonical);
182    }
183}
184
185// GROUP
186// ================================================================================================
187
188pub struct DebugTraceGroup<'g> {
189    challenges: &'g Challenges<QuadFelt>,
190    state: &'g mut DebugTraceState,
191    u: QuadFelt,
192    v: QuadFelt,
193    row_idx: usize,
194    column_idx: usize,
195    group_idx: usize,
196    /// `true` for `group_with_cached_encoding` — triggers the mutex check at group close.
197    check_mutex: bool,
198    active_flag_count: usize,
199}
200
201impl<'g> DebugTraceGroup<'g> {
202    /// Count active flags for mutex checks. Only meaningful when `check_mutex == true`,
203    /// but cheap enough to run unconditionally.
204    fn track_mutex(&mut self, flag: Felt) {
205        if self.check_mutex && flag != Felt::ZERO {
206            self.active_flag_count += 1;
207        }
208    }
209
210    /// Push one `(multiplicity, denom)` into both the balance map and the push log,
211    /// with the group's current `(row, col, group)` source coordinates.
212    fn record(&mut self, msg_repr: alloc::string::String, denom: QuadFelt, multiplicity: Felt) {
213        *self.state.balances.entry(denom).or_insert(Felt::ZERO) += multiplicity;
214        self.state.push_log.push(PushRecord {
215            row: self.row_idx,
216            column_idx: self.column_idx,
217            group_idx: self.group_idx,
218            msg_repr,
219            denom,
220            multiplicity,
221        });
222    }
223}
224
225impl<'g> LookupGroup for DebugTraceGroup<'g> {
226    type Expr = Felt;
227    type ExprEF = QuadFelt;
228
229    type Batch<'b>
230        = DebugTraceBatch<'b>
231    where
232        Self: 'b;
233
234    fn insert<M>(
235        &mut self,
236        _name: &'static str,
237        flag: Felt,
238        multiplicity: Felt,
239        msg: impl FnOnce() -> M,
240        _deg: Deg,
241    ) where
242        M: LookupMessage<Felt, QuadFelt>,
243    {
244        self.track_mutex(flag);
245        if flag == Felt::ZERO {
246            return;
247        }
248        let built = msg();
249        let v_msg = built.encode(self.challenges);
250        self.record(format!("{built:?}"), v_msg, multiplicity);
251        self.u += (v_msg - QuadFelt::ONE) * flag;
252        self.v += flag * multiplicity;
253    }
254
255    fn batch<'b>(
256        &'b mut self,
257        _name: &'static str,
258        flag: Felt,
259        build: impl FnOnce(&mut Self::Batch<'b>),
260        _deg: Deg,
261    ) {
262        self.track_mutex(flag);
263        let active = flag != Felt::ZERO;
264        let (n, d) = {
265            let mut batch = DebugTraceBatch {
266                challenges: self.challenges,
267                state: &mut *self.state,
268                active,
269                n: QuadFelt::ZERO,
270                d: QuadFelt::ONE,
271                row_idx: self.row_idx,
272                column_idx: self.column_idx,
273                group_idx: self.group_idx,
274            };
275            build(&mut batch);
276            (batch.n, batch.d)
277        };
278        self.u += (d - QuadFelt::ONE) * flag;
279        self.v += n * flag;
280    }
281
282    fn beta_powers(&self) -> &[QuadFelt] {
283        &self.challenges.beta_powers[..]
284    }
285
286    fn bus_prefix(&self, bus_id: usize) -> QuadFelt {
287        self.challenges.bus_prefix[bus_id]
288    }
289
290    fn insert_encoded(
291        &mut self,
292        _name: &'static str,
293        flag: Felt,
294        multiplicity: Felt,
295        encoded: impl FnOnce() -> QuadFelt,
296        _deg: Deg,
297    ) {
298        self.track_mutex(flag);
299        if flag == Felt::ZERO {
300            return;
301        }
302        let v_msg = encoded();
303        self.record("<encoded>".to_string(), v_msg, multiplicity);
304        self.u += (v_msg - QuadFelt::ONE) * flag;
305        self.v += flag * multiplicity;
306    }
307}
308
309// BATCH
310// ================================================================================================
311
312pub struct DebugTraceBatch<'b> {
313    challenges: &'b Challenges<QuadFelt>,
314    state: &'b mut DebugTraceState,
315    /// `false` if the outer group's flag was zero — batch-level short-circuit for balance
316    /// accumulation. `(N, D)` still tracks normally so the outer group's `(V_g, U_g)` fold
317    /// stays correct.
318    active: bool,
319    n: QuadFelt,
320    d: QuadFelt,
321    /// Source coordinates inherited from the enclosing group for push-log records.
322    row_idx: usize,
323    column_idx: usize,
324    group_idx: usize,
325}
326
327impl<'b> DebugTraceBatch<'b> {
328    fn record(&mut self, msg_repr: alloc::string::String, denom: QuadFelt, multiplicity: Felt) {
329        *self.state.balances.entry(denom).or_insert(Felt::ZERO) += multiplicity;
330        self.state.push_log.push(PushRecord {
331            row: self.row_idx,
332            column_idx: self.column_idx,
333            group_idx: self.group_idx,
334            msg_repr,
335            denom,
336            multiplicity,
337        });
338    }
339}
340
341impl<'b> LookupBatch for DebugTraceBatch<'b> {
342    type Expr = Felt;
343    type ExprEF = QuadFelt;
344
345    fn insert<M>(&mut self, _name: &'static str, multiplicity: Felt, msg: M, _deg: Deg)
346    where
347        M: LookupMessage<Felt, QuadFelt>,
348    {
349        let v_msg = msg.encode(self.challenges);
350        if self.active {
351            self.record(format!("{msg:?}"), v_msg, multiplicity);
352        }
353        let d_prev = self.d;
354        self.n = self.n * v_msg + d_prev * multiplicity;
355        self.d *= v_msg;
356    }
357
358    fn insert_encoded(
359        &mut self,
360        _name: &'static str,
361        multiplicity: Felt,
362        encoded: impl FnOnce() -> QuadFelt,
363        _deg: Deg,
364    ) {
365        let v_msg = encoded();
366        if self.active {
367            self.record("<encoded>".to_string(), v_msg, multiplicity);
368        }
369        let d_prev = self.d;
370        self.n = self.n * v_msg + d_prev * multiplicity;
371        self.d *= v_msg;
372    }
373}
374
375// BOUNDARY EMITTER
376// ================================================================================================
377
378/// `BoundaryBuilder` impl that writes once-per-proof emissions into the same
379/// [`DebugTraceState`] as the per-row `DebugTraceBuilder`. Emissions are tagged with
380/// `row: usize::MAX` and `msg_repr` prefixed `[boundary:<name>]` so they're visible
381/// in the report as originating outside the trace.
382pub struct DebugBoundaryEmitter<'a> {
383    pub(super) challenges: &'a Challenges<QuadFelt>,
384    pub(super) state: &'a mut DebugTraceState,
385    pub(super) public_values: &'a [Felt],
386    pub(super) var_len_public_inputs: &'a [&'a [Felt]],
387}
388
389impl<'a> BoundaryBuilder for DebugBoundaryEmitter<'a> {
390    type F = Felt;
391    type EF = QuadFelt;
392
393    fn public_values(&self) -> &[Felt] {
394        self.public_values
395    }
396
397    fn var_len_public_inputs(&self) -> &[&[Felt]] {
398        self.var_len_public_inputs
399    }
400
401    fn insert<M>(&mut self, name: &'static str, multiplicity: Felt, msg: M)
402    where
403        M: LookupMessage<Felt, QuadFelt>,
404    {
405        let denom = msg.encode(self.challenges);
406        *self.state.balances.entry(denom).or_insert(Felt::ZERO) += multiplicity;
407        self.state.push_log.push(PushRecord {
408            row: usize::MAX,
409            column_idx: usize::MAX,
410            group_idx: usize::MAX,
411            msg_repr: format!("[boundary:{name}] {msg:?}"),
412            denom,
413            multiplicity,
414        });
415    }
416}
miden_air/lookup/debug/trace/builder.rs

miden_air/lookup/debug/trace/
builder.rs
