halo2_proofs/circuit/
layouter.rs

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

halo2_proofs/circuit/
layouter.rs
