sp1_stark/lookup/
debug.rs

1use p3_baby_bear::BabyBear;
2use p3_field::{AbstractField, Field, PrimeField32, PrimeField64};
3use p3_matrix::Matrix;
4use std::collections::BTreeMap;
5
6use super::InteractionKind;
7use crate::{
8    air::{InteractionScope, MachineAir},
9    MachineChip, StarkGenericConfig, StarkMachine, StarkProvingKey, Val,
10};
11
12/// The data for an interaction.
13#[derive(Debug)]
14pub struct InteractionData<F: Field> {
15    /// The chip name.
16    pub chip_name: String,
17    /// The kind of interaction.
18    pub kind: InteractionKind,
19    /// The row of the interaction.
20    pub row: usize,
21    /// The interaction number.
22    pub interaction_number: usize,
23    /// Whether the interaction is a send.
24    pub is_send: bool,
25    /// The multiplicity of the interaction.
26    pub multiplicity: F,
27}
28
29/// Converts a vector of field elements to a string.
30#[allow(clippy::needless_pass_by_value)]
31#[must_use]
32pub fn vec_to_string<F: Field>(vec: Vec<F>) -> String {
33    let mut result = String::from("(");
34    for (i, value) in vec.iter().enumerate() {
35        if i != 0 {
36            result.push_str(", ");
37        }
38        result.push_str(&value.to_string());
39    }
40    result.push(')');
41    result
42}
43
44/// Display field elements as signed integers on the range `[-modulus/2, modulus/2]`.
45///
46/// This presentation is useful when debugging interactions as it makes it clear which interactions
47/// are `send` and which are `receive`.
48fn field_to_int<F: PrimeField32>(x: F) -> i32 {
49    let modulus = BabyBear::ORDER_U64;
50    let val = x.as_canonical_u64();
51    if val > modulus / 2 {
52        val as i32 - modulus as i32
53    } else {
54        val as i32
55    }
56}
57
58/// Debugs the interactions of a chip.
59#[allow(clippy::type_complexity)]
60#[allow(clippy::needless_pass_by_value)]
61pub fn debug_interactions<SC: StarkGenericConfig, A: MachineAir<Val<SC>>>(
62    chip: &MachineChip<SC, A>,
63    pkey: &StarkProvingKey<SC>,
64    record: &A::Record,
65    interaction_kinds: Vec<InteractionKind>,
66    scope: InteractionScope,
67) -> (BTreeMap<String, Vec<InteractionData<Val<SC>>>>, BTreeMap<String, Val<SC>>) {
68    let mut key_to_vec_data = BTreeMap::new();
69    let mut key_to_count = BTreeMap::new();
70
71    let trace = chip.generate_trace(record, &mut A::Record::default());
72    let mut pre_traces = pkey.traces.clone();
73    let mut preprocessed_trace =
74        pkey.chip_ordering.get(&chip.name()).map(|&index| pre_traces.get_mut(index).unwrap());
75    let mut main = trace.clone();
76    let height = trace.clone().height();
77
78    let sends = chip.sends().iter().filter(|s| s.scope == scope).collect::<Vec<_>>();
79    let receives = chip.receives().iter().filter(|r| r.scope == scope).collect::<Vec<_>>();
80
81    let nb_send_interactions = sends.len();
82    for row in 0..height {
83        for (m, interaction) in sends.iter().chain(receives.iter()).enumerate() {
84            if !interaction_kinds.contains(&interaction.kind) {
85                continue;
86            }
87            let mut empty = vec![];
88            let preprocessed_row = preprocessed_trace
89                .as_mut()
90                .map(|t| t.row_mut(row))
91                .or_else(|| Some(&mut empty))
92                .unwrap();
93            let is_send = m < nb_send_interactions;
94            let multiplicity_eval: Val<SC> =
95                interaction.multiplicity.apply(preprocessed_row, main.row_mut(row));
96
97            if !multiplicity_eval.is_zero() {
98                let mut values = vec![];
99                for value in &interaction.values {
100                    let expr: Val<SC> = value.apply(preprocessed_row, main.row_mut(row));
101                    values.push(expr);
102                }
103                let key = format!(
104                    "{} {} {}",
105                    &interaction.scope.to_string(),
106                    &interaction.kind.to_string(),
107                    vec_to_string(values)
108                );
109                key_to_vec_data.entry(key.clone()).or_insert_with(Vec::new).push(InteractionData {
110                    chip_name: chip.name(),
111                    kind: interaction.kind,
112                    row,
113                    interaction_number: m,
114                    is_send,
115                    multiplicity: multiplicity_eval,
116                });
117                let current = key_to_count.entry(key.clone()).or_insert(Val::<SC>::zero());
118                if is_send {
119                    *current += multiplicity_eval;
120                } else {
121                    *current -= multiplicity_eval;
122                }
123            }
124        }
125    }
126
127    (key_to_vec_data, key_to_count)
128}
129
130/// Calculate the number of times we send and receive each event of the given interaction type,
131/// and print out the ones for which the set of sends and receives don't match.
132#[allow(clippy::needless_pass_by_value)]
133pub fn debug_interactions_with_all_chips<SC, A>(
134    machine: &StarkMachine<SC, A>,
135    pkey: &StarkProvingKey<SC>,
136    shards: &[A::Record],
137    interaction_kinds: Vec<InteractionKind>,
138    scope: InteractionScope,
139) -> bool
140where
141    SC: StarkGenericConfig,
142    SC::Val: PrimeField32,
143    A: MachineAir<SC::Val>,
144{
145    if scope == InteractionScope::Local {
146        assert!(shards.len() == 1);
147    }
148
149    let mut final_map = BTreeMap::new();
150    let mut total = SC::Val::zero();
151
152    let chips = machine.chips();
153    for chip in chips.iter() {
154        let mut total_events = 0;
155        for shard in shards {
156            if !chip.included(shard) {
157                continue;
158            }
159            eprintln!("{}", chip.name());
160            let (_, count) =
161                debug_interactions::<SC, A>(chip, pkey, shard, interaction_kinds.clone(), scope);
162            total_events += count.len();
163            for (key, value) in count.iter() {
164                let entry =
165                    final_map.entry(key.clone()).or_insert((SC::Val::zero(), BTreeMap::new()));
166                entry.0 += *value;
167                total += *value;
168                *entry.1.entry(chip.name()).or_insert(SC::Val::zero()) += *value;
169            }
170        }
171        tracing::info!("{} chip has {} distinct events", chip.name(), total_events);
172    }
173
174    tracing::info!("Final counts below.");
175    tracing::info!("==================");
176
177    let mut any_nonzero = false;
178    for (key, (value, chip_values)) in final_map.clone() {
179        if !Val::<SC>::is_zero(&value) {
180            tracing::info!(
181                "Interaction key: {} Send-Receive Discrepancy: {}",
182                key,
183                field_to_int(value)
184            );
185            any_nonzero = true;
186            for (chip, chip_value) in chip_values {
187                tracing::info!(
188                    " {} chip's send-receive discrepancy for this key is {}",
189                    chip,
190                    field_to_int(chip_value)
191                );
192            }
193        }
194    }
195
196    tracing::info!("==================");
197    if !any_nonzero {
198        tracing::info!("All chips have the same number of sends and receives.");
199    } else {
200        tracing::info!("Positive values mean sent more than received.");
201        tracing::info!("Negative values mean received more than sent.");
202        if total != SC::Val::zero() {
203            tracing::info!("Total send-receive discrepancy: {}", field_to_int(total));
204            if field_to_int(total) > 0 {
205                tracing::info!("you're sending more than you are receiving");
206            } else {
207                tracing::info!("you're receiving more than you are sending");
208            }
209        } else {
210            tracing::info!(
211                "the total number of sends and receives match, but the keys don't match"
212            );
213            tracing::info!("check the arguments");
214        }
215    }
216
217    !any_nonzero
218}
sp1_stark/lookup/debug.rs

sp1_stark/lookup/
debug.rs
