halo2_axiom/circuit/layouter.rs
1//! Implementations of common circuit layouters.
2
3use std::cmp;
4use std::collections::HashSet;
5use std::fmt;
6
7use ff::Field;
8
9pub use super::table_layouter::TableLayouter;
10use super::{AssignedCell, Cell, RegionIndex, Value};
11use crate::plonk::{Advice, Any, Assigned, Challenge, Column, Error, Fixed, Instance, Selector};
12
13/// Intermediate trait requirements for [`RegionLayouter`] when thread-safe regions are enabled.
14#[cfg(feature = "thread-safe-region")]
15pub trait SyncDeps: Send + Sync {}
16
17#[cfg(feature = "thread-safe-region")]
18impl<T: Send + Sync> SyncDeps for T {}
19
20/// Intermediate trait requirements for [`RegionLayouter`].
21#[cfg(not(feature = "thread-safe-region"))]
22pub trait SyncDeps {}
23
24#[cfg(not(feature = "thread-safe-region"))]
25impl<T> SyncDeps for T {}
26
27/// Helper trait for implementing a custom [`Layouter`].
28///
29/// This trait is used for implementing region assignments:
30///
31/// ```ignore
32/// impl<'a, F: Field, C: Chip<F>, CS: Assignment<F> + 'a> Layouter<C> for MyLayouter<'a, C, CS> {
33/// fn assign_region(
34/// &mut self,
35/// assignment: impl FnOnce(Region<'_, F, C>) -> Result<(), Error>,
36/// ) -> Result<(), Error> {
37/// let region_index = self.regions.len();
38/// self.regions.push(self.current_gate);
39///
40/// let mut region = MyRegion::new(self, region_index);
41/// {
42/// let region: &mut dyn RegionLayouter<F> = &mut region;
43/// assignment(region.into())?;
44/// }
45/// self.current_gate += region.row_count;
46///
47/// Ok(())
48/// }
49/// }
50/// ```
51///
52/// TODO: It would be great if we could constrain the columns in these types to be
53/// "logical" columns that are guaranteed to correspond to the chip (and have come from
54/// `Chip::Config`).
55///
56/// [`Layouter`]: super::Layouter
57pub trait RegionLayouter<F: Field>: fmt::Debug + SyncDeps {
58 /// Enables a selector at the given offset.
59 fn enable_selector<'v>(
60 &'v mut self,
61 annotation: &'v (dyn Fn() -> String + 'v),
62 selector: &Selector,
63 offset: usize,
64 ) -> Result<(), Error>;
65
66 /// Allows the circuit implementor to name/annotate a Column within a Region context.
67 ///
68 /// This is useful in order to improve the amount of information that `prover.verify()`
69 /// and `prover.assert_satisfied()` can provide.
70 fn name_column<'v>(
71 &'v mut self,
72 annotation: &'v (dyn Fn() -> String + 'v),
73 column: Column<Any>,
74 );
75
76 /// Assign an advice column value (witness)
77 fn assign_advice<'v>(
78 &mut self,
79 // annotation: &'v (dyn Fn() -> String + 'v),
80 column: Column<Advice>,
81 offset: usize,
82 to: Value<Assigned<F>>, // &'v mut (dyn FnMut() -> Value<Assigned<F>> + 'v),
83 ) -> AssignedCell<&'v Assigned<F>, F>;
84
85 /// Assigns a constant value to the column `advice` at `offset` within this region.
86 ///
87 /// The constant value will be assigned to a cell within one of the fixed columns
88 /// configured via `ConstraintSystem::enable_constant`.
89 ///
90 /// Returns the advice cell that has been equality-constrained to the constant.
91 fn assign_advice_from_constant<'v>(
92 &'v mut self,
93 annotation: &'v (dyn Fn() -> String + 'v),
94 column: Column<Advice>,
95 offset: usize,
96 constant: Assigned<F>,
97 ) -> Result<Cell, Error>;
98
99 /// Assign the value of the instance column's cell at absolute location
100 /// `row` to the column `advice` at `offset` within this region.
101 ///
102 /// Returns the advice cell that has been equality-constrained to the
103 /// instance cell, and its value if known.
104 fn assign_advice_from_instance<'v>(
105 &mut self,
106 annotation: &'v (dyn Fn() -> String + 'v),
107 instance: Column<Instance>,
108 row: usize,
109 advice: Column<Advice>,
110 offset: usize,
111 ) -> Result<(Cell, Value<F>), Error>;
112
113 /// Returns the value of the instance column's cell at absolute location `row`.
114 fn instance_value(&mut self, instance: Column<Instance>, row: usize)
115 -> Result<Value<F>, Error>;
116
117 /// Assign a fixed value
118 fn assign_fixed(
119 &mut self,
120 // annotation: &'v (dyn Fn() -> String + 'v),
121 column: Column<Fixed>,
122 offset: usize,
123 to: Assigned<F>,
124 ) -> Cell;
125
126 /// Constrains a cell to have a constant value.
127 ///
128 /// Returns an error if the cell is in a column where equality has not been enabled.
129 fn constrain_constant(&mut self, cell: Cell, constant: Assigned<F>) -> Result<(), Error>;
130
131 /// Constraint two cells to have the same value.
132 ///
133 /// Returns an error if either of the cells is not within the given permutation.
134 fn constrain_equal(&mut self, left: Cell, right: Cell);
135
136 /// Queries the value of the given challenge.
137 ///
138 /// Returns `Value::unknown()` if the current synthesis phase is before the challenge can be queried.
139 fn get_challenge(&self, challenge: Challenge) -> Value<F>;
140
141 /// Commit advice columns in current phase and squeeze challenges.
142 /// This can be called DURING synthesize.
143 fn next_phase(&mut self);
144}
145
146/// The shape of a region. For a region at a certain index, we track
147/// the set of columns it uses as well as the number of rows it uses.
148#[derive(Clone, Debug)]
149#[allow(dead_code)]
150pub struct RegionShape {
151 pub(super) region_index: RegionIndex,
152 pub(super) columns: HashSet<RegionColumn>,
153 pub(super) row_count: usize,
154}
155
156/// The virtual column involved in a region. This includes concrete columns,
157/// as well as selectors that are not concrete columns at this stage.
158#[derive(Eq, PartialEq, Copy, Clone, Debug, Hash)]
159pub enum RegionColumn {
160 /// Concrete column
161 Column(Column<Any>),
162 /// Virtual column representing a (boolean) selector
163 Selector(Selector),
164}
165
166impl From<Column<Any>> for RegionColumn {
167 fn from(column: Column<Any>) -> RegionColumn {
168 RegionColumn::Column(column)
169 }
170}
171
172impl From<Selector> for RegionColumn {
173 fn from(selector: Selector) -> RegionColumn {
174 RegionColumn::Selector(selector)
175 }
176}
177
178impl Ord for RegionColumn {
179 fn cmp(&self, other: &Self) -> cmp::Ordering {
180 match (self, other) {
181 (Self::Column(ref a), Self::Column(ref b)) => a.cmp(b),
182 (Self::Selector(ref a), Self::Selector(ref b)) => a.0.cmp(&b.0),
183 (Self::Column(_), Self::Selector(_)) => cmp::Ordering::Less,
184 (Self::Selector(_), Self::Column(_)) => cmp::Ordering::Greater,
185 }
186 }
187}
188
189impl PartialOrd for RegionColumn {
190 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
191 Some(self.cmp(other))
192 }
193}
194
195/*
196impl RegionShape {
197 /// Create a new `RegionShape` for a region at `region_index`.
198 pub fn new(region_index: RegionIndex) -> Self {
199 RegionShape {
200 region_index,
201 columns: HashSet::default(),
202 row_count: 0,
203 }
204 }
205
206 /// Get the `region_index` of a `RegionShape`.
207 pub fn region_index(&self) -> RegionIndex {
208 self.region_index
209 }
210
211 /// Get a reference to the set of `columns` used in a `RegionShape`.
212 pub fn columns(&self) -> &HashSet<RegionColumn> {
213 &self.columns
214 }
215
216 /// Get the `row_count` of a `RegionShape`.
217 pub fn row_count(&self) -> usize {
218 self.row_count
219 }
220}
221
222impl<F: Field> RegionLayouter<F> for RegionShape {
223 fn enable_selector<'v>(
224 &'v mut self,
225 _: &'v (dyn Fn() -> String + 'v),
226 selector: &Selector,
227 offset: usize,
228 ) -> Result<(), Error> {
229 // Track the selector's fixed column as part of the region's shape.
230 self.columns.insert((*selector).into());
231 self.row_count = cmp::max(self.row_count, offset + 1);
232 Ok(())
233 }
234
235 fn assign_advice<'v>(
236 &'v mut self,
237 //_: &'v (dyn Fn() -> String + 'v),
238 column: Column<Advice>,
239 offset: usize,
240 _to: Value<Assigned<F>>, // &'v mut (dyn FnMut() -> Value<Assigned<F>> + 'v),
241 ) -> Result<AssignedCell<&Assigned<F>, F>, Error> {
242 self.columns.insert(Column::<Any>::from(column).into());
243 self.row_count = cmp::max(self.row_count, offset + 1);
244
245 Ok(Cell {
246 region_index: self.region_index,
247 row_offset: offset,
248 column: column.into(),
249 });
250 todo!()
251 }
252
253 fn assign_advice_from_constant<'v>(
254 &'v mut self,
255 annotation: &'v (dyn Fn() -> String + 'v),
256 column: Column<Advice>,
257 offset: usize,
258 constant: Assigned<F>,
259 ) -> Result<Cell, Error> {
260 // The rest is identical to witnessing an advice cell.
261 self.assign_advice(column, offset, Value::known(constant))
262 }
263
264 fn assign_advice_from_instance<'v>(
265 &mut self,
266 _: &'v (dyn Fn() -> String + 'v),
267 _: Column<Instance>,
268 _: usize,
269 advice: Column<Advice>,
270 offset: usize,
271 ) -> Result<(Cell, Value<F>), Error> {
272 self.columns.insert(Column::<Any>::from(advice).into());
273 self.row_count = cmp::max(self.row_count, offset + 1);
274
275 Ok((
276 Cell {
277 region_index: self.region_index,
278 row_offset: offset,
279 column: advice.into(),
280 },
281 Value::unknown(),
282 ))
283 }
284
285 fn instance_value(
286 &mut self,
287 _instance: Column<Instance>,
288 _row: usize,
289 ) -> Result<Value<F>, Error> {
290 Ok(Value::unknown())
291 }
292
293 fn assign_fixed<'v>(
294 &'v mut self,
295 _: &'v (dyn Fn() -> String + 'v),
296 column: Column<Fixed>,
297 offset: usize,
298 _to: &'v mut (dyn FnMut() -> Value<Assigned<F>> + 'v),
299 ) -> Result<Cell, Error> {
300 self.columns.insert(Column::<Any>::from(column).into());
301 self.row_count = cmp::max(self.row_count, offset + 1);
302
303 Ok(Cell {
304 region_index: self.region_index,
305 row_offset: offset,
306 column: column.into(),
307 })
308 }
309
310 fn name_column<'v>(
311 &'v mut self,
312 _annotation: &'v (dyn Fn() -> String + 'v),
313 _column: Column<Any>,
314 ) {
315 // Do nothing
316 }
317
318 fn constrain_constant(&mut self, _cell: Cell, _constant: Assigned<F>) -> Result<(), Error> {
319 // Global constants don't affect the region shape.
320 Ok(())
321 }
322
323 fn constrain_equal(&mut self, _left: Cell, _right: Cell) -> Result<(), Error> {
324 // Equality constraints don't affect the region shape.
325 Ok(())
326 }
327
328 fn get_challenge(&self, _: Challenge) -> Value<F> {
329 Value::unknown()
330 }
331
332 fn next_phase(&mut self) -> Result<(), Error> {
333 // Region shapes don't care about phases.
334 Ok(())
335 }
336}
337*/