halo2_proofs/dev/
graph.rs

1use ff::Field;
2use tabbycat::{AttrList, Edge, GraphBuilder, GraphType, Identity, StmtList};
3
4use crate::{
5    circuit::Value,
6    plonk::{
7        Advice, Any, Assigned, Assignment, Circuit, Column, ConstraintSystem, Error, Fixed,
8        FloorPlanner, Instance, Selector,
9    },
10};
11
12pub mod layout;
13
14/// Builds a dot graph string representing the given circuit.
15///
16/// The graph is built from calls to [`Layouter::namespace`] both within the circuit, and
17/// inside the gadgets and chips that it uses.
18///
19/// [`Layouter::namespace`]: crate::circuit::Layouter#method.namespace
20pub fn circuit_dot_graph<F: Field, ConcreteCircuit: Circuit<F>>(
21    circuit: &ConcreteCircuit,
22) -> String {
23    // Collect the graph details.
24    let mut cs = ConstraintSystem::default();
25    let config = ConcreteCircuit::configure(&mut cs);
26    let mut graph = Graph::default();
27    ConcreteCircuit::FloorPlanner::synthesize(&mut graph, circuit, config, cs.constants).unwrap();
28
29    // Construct the node labels. We need to store these, because tabbycat operates on
30    // string references, and we need those references to live long enough.
31    let node_labels: Vec<_> = graph
32        .nodes
33        .into_iter()
34        .map(|(name, gadget_name)| {
35            if let Some(gadget_name) = gadget_name {
36                format!("[{}] {}", gadget_name, name)
37            } else {
38                name
39            }
40        })
41        .collect();
42
43    // Construct the dot graph statements.
44    let mut stmts = StmtList::new();
45    for (id, label) in node_labels.iter().enumerate() {
46        stmts = stmts.add_node(
47            id.into(),
48            None,
49            Some(AttrList::new().add_pair(tabbycat::attributes::label(label))),
50        );
51    }
52    for (parent, child) in graph.edges {
53        stmts =
54            stmts.add_edge(Edge::head_node(parent.into(), None).arrow_to_node(child.into(), None))
55    }
56
57    // Build the graph!
58    GraphBuilder::default()
59        .graph_type(GraphType::DiGraph)
60        .strict(false)
61        .id(Identity::id("circuit").unwrap())
62        .stmts(stmts)
63        .build()
64        .unwrap()
65        .to_string()
66}
67
68#[derive(Default)]
69struct Graph {
70    /// Graph nodes in the namespace, structured as `(name, gadget_name)`.
71    nodes: Vec<(String, Option<String>)>,
72
73    /// Directed edges in the graph, as pairs of indices into `nodes`.
74    edges: Vec<(usize, usize)>,
75
76    /// The current namespace, as indices into `nodes`.
77    current_namespace: Vec<usize>,
78}
79
80impl<F: Field> Assignment<F> for Graph {
81    fn enter_region<NR, N>(&mut self, _: N)
82    where
83        NR: Into<String>,
84        N: FnOnce() -> NR,
85    {
86        // Do nothing; we don't care about regions in this context.
87    }
88
89    fn exit_region(&mut self) {
90        // Do nothing; we don't care about regions in this context.
91    }
92
93    fn enable_selector<A, AR>(&mut self, _: A, _: &Selector, _: usize) -> Result<(), Error>
94    where
95        A: FnOnce() -> AR,
96        AR: Into<String>,
97    {
98        // Do nothing; we don't care about cells in this context.
99        Ok(())
100    }
101
102    fn query_instance(&self, _: Column<Instance>, _: usize) -> Result<Value<F>, Error> {
103        Ok(Value::unknown())
104    }
105
106    fn assign_advice<V, VR, A, AR>(
107        &mut self,
108        _: A,
109        _: Column<Advice>,
110        _: usize,
111        _: V,
112    ) -> Result<(), Error>
113    where
114        V: FnOnce() -> Value<VR>,
115        VR: Into<Assigned<F>>,
116        A: FnOnce() -> AR,
117        AR: Into<String>,
118    {
119        // Do nothing; we don't care about cells in this context.
120        Ok(())
121    }
122
123    fn assign_fixed<V, VR, A, AR>(
124        &mut self,
125        _: A,
126        _: Column<Fixed>,
127        _: usize,
128        _: V,
129    ) -> Result<(), Error>
130    where
131        V: FnOnce() -> Value<VR>,
132        VR: Into<Assigned<F>>,
133        A: FnOnce() -> AR,
134        AR: Into<String>,
135    {
136        // Do nothing; we don't care about cells in this context.
137        Ok(())
138    }
139
140    fn copy(
141        &mut self,
142        _: Column<Any>,
143        _: usize,
144        _: Column<Any>,
145        _: usize,
146    ) -> Result<(), crate::plonk::Error> {
147        // Do nothing; we don't care about permutations in this context.
148        Ok(())
149    }
150
151    fn fill_from_row(
152        &mut self,
153        _: Column<Fixed>,
154        _: usize,
155        _: Value<Assigned<F>>,
156    ) -> Result<(), Error> {
157        Ok(())
158    }
159
160    fn push_namespace<NR, N>(&mut self, name_fn: N)
161    where
162        NR: Into<String>,
163        N: FnOnce() -> NR,
164    {
165        // Store the new node.
166        let new_node = self.nodes.len();
167        self.nodes.push((name_fn().into(), None));
168
169        // Create an edge from the parent, if any.
170        if let Some(parent) = self.current_namespace.last() {
171            self.edges.push((*parent, new_node));
172        }
173
174        // Push the new namespace.
175        self.current_namespace.push(new_node);
176    }
177
178    fn pop_namespace(&mut self, gadget_name: Option<String>) {
179        // Store the gadget name that was extracted, if any.
180        let node = self
181            .current_namespace
182            .last()
183            .expect("pop_namespace should never be called on the root");
184        self.nodes[*node].1 = gadget_name;
185
186        // Pop the namespace.
187        self.current_namespace.pop();
188    }
189}
halo2_proofs/dev/graph.rs

halo2_proofs/dev/
graph.rs
