kimchi_msm/
columns.rs

1use std::collections::HashMap;
2
3use folding::expressions::FoldingColumnTrait;
4use kimchi::circuits::expr::{CacheId, FormattedOutput};
5
6/// Describe a generic indexed variable X_{i}.
7#[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)]
8pub enum Column<T> {
9    /// Columns related to the relation encoded in the circuit
10    Relation(T),
11    /// Columns related to dynamic selectors to indicate gate type
12    DynamicSelector(usize),
13    /// Constant column that is /always/ fixed for a given circuit.
14    FixedSelector(usize),
15    // Columns related to the lookup protocol
16    /// Partial sums. This corresponds to the `h_i`.
17    /// It is first indexed by the table ID, and after that internal index.
18    LookupPartialSum((u32, usize)),
19    /// Multiplicities, indexed. This corresponds to the `m_i`. First
20    /// indexed by table ID, then internal index.
21    LookupMultiplicity((u32, usize)),
22    /// The lookup aggregation, i.e. `phi`
23    LookupAggregation,
24    /// The fixed tables. The parameter is considered to the indexed table.
25    LookupFixedTable(u32),
26}
27
28impl Column<usize> {
29    /// Adds offset if the column is `Relation`. Fails otherwise.
30    pub fn add_rel_offset(self, offset: usize) -> Column<usize> {
31        let Column::Relation(i) = self else {
32            todo!("add_rel_offset is only implemented for the relation columns")
33        };
34        Column::Relation(offset + i)
35    }
36}
37
38impl FormattedOutput for Column<usize> {
39    fn latex(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
40        match self {
41            Column::Relation(i) => format!("x_{{{i}}}"),
42            Column::FixedSelector(i) => format!("fs_{{{i}}}"),
43            Column::DynamicSelector(i) => format!("ds_{{{i}}}"),
44            Column::LookupPartialSum((table_id, i)) => format!("h_{{{table_id}, {i}}}"),
45            Column::LookupMultiplicity((table_id, i)) => format!("m_{{{table_id}, {i}}}"),
46            Column::LookupFixedTable(i) => format!("t_{{{i}}}"),
47            Column::LookupAggregation => String::from("φ"),
48        }
49    }
50
51    fn text(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
52        match self {
53            Column::Relation(i) => format!("x[{i}]"),
54            Column::FixedSelector(i) => format!("fs[{i}]"),
55            Column::DynamicSelector(i) => format!("ds[{i}]"),
56            Column::LookupPartialSum((table_id, i)) => format!("h[{table_id}, {i}]"),
57            Column::LookupMultiplicity((table_id, i)) => format!("m[{table_id}, {i}]"),
58            Column::LookupFixedTable(i) => format!("t[{i}]"),
59            Column::LookupAggregation => String::from("φ"),
60        }
61    }
62
63    fn ocaml(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
64        // FIXME
65        unimplemented!("Not used at the moment")
66    }
67
68    fn is_alpha(&self) -> bool {
69        // FIXME
70        unimplemented!("Not used at the moment")
71    }
72}
73
74/// A datatype expressing a generalized column, but with potentially
75/// more convenient interface than a bare column.
76pub trait ColumnIndexer<T>: core::fmt::Debug + Copy + Eq + Ord {
77    /// Total number of columns in this index.
78    const N_COL: usize;
79
80    /// Flatten the column "alias" into the integer-like column.
81    fn to_column(self) -> Column<T>;
82}
83
84// Implementation to be compatible with folding if we use generic column
85// constraints
86impl<T: Copy> FoldingColumnTrait for Column<T> {
87    fn is_witness(&self) -> bool {
88        match self {
89            // Witness
90            Column::Relation(_) => true,
91            Column::DynamicSelector(_) => true,
92            // FIXME: check if we want to treat lookups differently
93            Column::LookupPartialSum(_) => true,
94            Column::LookupMultiplicity(_) => true,
95            Column::LookupAggregation => true,
96            // Not witness/public values
97            Column::FixedSelector(_) => false,
98            Column::LookupFixedTable(_) => false,
99        }
100    }
101}
kimchi_msm/columns.rs

kimchi_msm/
columns.rs
