binius_m3/builder/
column.rs

1// Copyright 2025 Irreducible Inc.
2
3use std::{marker::PhantomData, sync::Arc};
4
5use binius_core::{oracle::ShiftVariant, polynomial::MultivariatePoly};
6use binius_field::{ExtensionField, TowerField};
7use binius_math::ArithCircuit;
8
9use super::{structured::StructuredDynSize, table::TableId, types::B128};
10
11/// An index of a column within a table.
12#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
13pub(crate) struct ColumnIndex(pub(crate) usize);
14
15/// An index of a column within a partition.
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub(crate) struct ColumnPartitionIndex(pub(crate) usize);
18
19/// A typed identifier for a column in a table.
20///
21/// The column has entries that are elements of `F`. In practice, the fields used will always be
22/// from the canonical tower (B1, B8, B16, B32, B64, B128). The second constant represents how many
23/// elements are packed vertically into a single logical row. For example, a column of type
24/// `Col<B1, 32>` will have 2^5 = 32 elements of `B1` packed into a single row.
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26pub struct Col<F: TowerField, const VALUES_PER_ROW: usize = 1> {
27	pub table_id: TableId,
28	pub(crate) table_index: ColumnIndex,
29	// Denormalized partition index so that we can use it to construct arithmetic expressions over
30	// the partition columns.
31	pub(crate) partition_index: ColumnPartitionIndex,
32	_marker: PhantomData<F>,
33}
34
35impl<F: TowerField, const VALUES_PER_ROW: usize> Col<F, VALUES_PER_ROW> {
36	/// Creates a new typed column handle.
37	///
38	/// This has limited visibility to ensure that only the [`TableBuilder`] can create them. This
39	/// ensures the type parameters are consistent with the column definition.
40	pub(super) fn new(id: ColumnId, partition_index: ColumnPartitionIndex) -> Self {
41		assert!(VALUES_PER_ROW.is_power_of_two());
42		Self {
43			table_id: id.table_id,
44			table_index: id.table_index,
45			partition_index,
46			_marker: PhantomData,
47		}
48	}
49
50	pub fn shape(&self) -> ColumnShape {
51		ColumnShape {
52			tower_height: F::TOWER_LEVEL,
53			log_values_per_row: VALUES_PER_ROW.ilog2() as usize,
54		}
55	}
56
57	pub fn id(&self) -> ColumnId {
58		ColumnId {
59			table_id: self.table_id,
60			table_index: self.table_index,
61		}
62	}
63}
64
65/// Upcast a column from a subfield to an extension field..
66pub fn upcast_col<F, FSub, const V: usize>(col: Col<FSub, V>) -> Col<F, V>
67where
68	FSub: TowerField,
69	F: TowerField + ExtensionField<FSub>,
70{
71	let Col {
72		table_id,
73		table_index,
74		partition_index,
75		_marker: _,
76	} = col;
77	// REVIEW: Maybe this should retain the info of the smallest tower level
78	Col {
79		table_id,
80		table_index,
81		partition_index,
82		_marker: PhantomData,
83	}
84}
85
86/// Complete description of a column within a table.
87#[derive(Debug)]
88pub struct ColumnInfo<F: TowerField = B128> {
89	pub id: ColumnId,
90	pub col: ColumnDef<F>,
91	pub name: String,
92	pub shape: ColumnShape,
93	/// Whether the column is constrained to be non-zero.
94	pub is_nonzero: bool,
95}
96
97/// The shape of each cell in a column.
98#[derive(Debug, Clone, Copy)]
99pub struct ColumnShape {
100	/// The tower height of the field elements.
101	pub tower_height: usize,
102	/// The binary logarithm of the number of elements packed vertically per event row.
103	pub log_values_per_row: usize,
104}
105
106impl ColumnShape {
107	/// Returns the binary logarithm of the number of bits each cell occupies.
108	pub fn log_cell_size(&self) -> usize {
109		self.tower_height + self.log_values_per_row
110	}
111}
112
113/// Unique identifier for a column within a constraint system.
114///
115/// IDs are assigned when columns are added to the constraint system and remain stable when more
116/// columns are added.
117#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
118pub struct ColumnId {
119	pub(crate) table_id: TableId,
120	pub(crate) table_index: ColumnIndex,
121}
122
123/// A definition of a column in a table.
124#[derive(Debug)]
125pub enum ColumnDef<F: TowerField = B128> {
126	Committed {
127		tower_level: usize,
128	},
129	Selected {
130		col: ColumnId,
131		index: usize,
132		index_bits: usize,
133	},
134	Projected {
135		col: ColumnId,
136		start_index: usize,
137		query_size: usize,
138		query_bits: usize,
139	},
140	ZeroPadded {
141		col: ColumnId,
142		n_pad_vars: usize,
143		start_index: usize,
144		nonzero_index: usize,
145	},
146	Shifted {
147		col: ColumnId,
148		offset: usize,
149		log_block_size: usize,
150		variant: ShiftVariant,
151	},
152	Packed {
153		col: ColumnId,
154		log_degree: usize,
155	},
156	Computed {
157		cols: Vec<ColumnId>,
158		expr: ArithCircuit<F>,
159	},
160	Constant {
161		poly: Arc<dyn MultivariatePoly<F>>,
162		data: Vec<F>,
163	},
164	StructuredDynSize(StructuredDynSize),
165	StructuredFixedSize {
166		expr: ArithCircuit<F>,
167	},
168	StaticExp {
169		bit_cols: Vec<ColumnId>,
170		base: F,
171		base_tower_level: usize,
172	},
173	DynamicExp {
174		bit_cols: Vec<ColumnId>,
175		base: ColumnId,
176		base_tower_level: usize,
177	},
178}
binius_m3/builder/column.rs

binius_m3/builder/
column.rs
