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*/