hugr_model/v0/ast/
mod.rs

1//! Abstract syntax tree representation of hugr modules.
2//!
3//! This module defines the abstract syntax tree for hugr graphs. The AST types
4//! implement [`Display`] and [`FromStr`] for pretty printing into and parsing
5//! from the s-expression based hugr text form. This is useful for debugging and
6//! writing hugr modules by hand. For a more performant serialization format, see
7//! [binary] instead.
8//!
9//! The data types in this module logically mirror those of the [table]
10//! representation, but are encoded differently. Instead of using ids, the AST
11//! data structure is recursive and uses names for symbols, variables and links.
12//! [`Term`]s, [`Node`]s and [`Region`]s can be referred to individually in this
13//! form, whereas the table form requires them to be seen in the context of a
14//! module. An AST module can be translated into a table module via [`Module::resolve`].
15//! This representation makes different efficiency tradeoffs than the table
16//! form by using standard heap based data structures instead of a bump
17//! allocated arena. This is slower but considerably more ergonomic.
18//!
19//! [binary]: crate::v0::binary
20//! [table]: crate::v0::table
21//! [`Display`]: std::fmt::Display
22//! [`FromStr`]: std::str::FromStr
23use std::sync::Arc;
24
25use bumpalo::Bump;
26
27use super::table::{self};
28use super::{LinkName, Literal, RegionKind, SymbolName, VarName, Visibility};
29
30mod parse;
31mod print;
32#[cfg(feature = "pyo3")]
33mod python;
34mod resolve;
35mod view;
36
37pub use parse::ParseError;
38pub use resolve::ResolveError;
39
40/// A package in the hugr AST.
41///
42/// See [`table::Package`] for the table representation.
43///
44/// [`table::Package`]: crate::v0::table::Package
45#[derive(Debug, Clone, PartialEq, Eq)]
46pub struct Package {
47    /// The sequence of modules in the package.
48    pub modules: Vec<Module>,
49}
50
51impl Package {
52    /// Try to convert this package into the table representation by
53    /// independently resolving its modules via [`Module::resolve`].
54    pub fn resolve<'a>(
55        &'a self,
56        bump: &'a Bump,
57    ) -> Result<table::Package<'a>, resolve::ResolveError> {
58        let modules = self
59            .modules
60            .iter()
61            .map(|module| module.resolve(bump))
62            .collect::<Result<_, _>>()?;
63        Ok(table::Package { modules })
64    }
65}
66
67/// A module in the hugr AST.
68///
69/// See [`table::Module`] for the table representation.
70///
71/// [`table::Module`]: crate::v0::table::Module
72#[derive(Debug, Clone, PartialEq, Eq)]
73pub struct Module {
74    /// The root region of the module.
75    ///
76    /// This must be a region of kind [`RegionKind::Module`].
77    pub root: Region,
78}
79
80impl Module {
81    /// Try to convert this module into the table representation.
82    ///
83    /// This conversion resolves the names of variables, symbols and links
84    /// according to their scoping rules described in the [`scope`] module.
85    /// Whenever a symbol is used but not defined in scope, an import node will
86    /// be inserted into the module region and all references to that symbol will
87    /// refer to the import node. This gives the opportunity to link the missing symbols.
88    ///
89    /// [`scope`]: crate::v0::scope
90    pub fn resolve<'a>(
91        &'a self,
92        bump: &'a Bump,
93    ) -> Result<table::Module<'a>, resolve::ResolveError> {
94        let mut ctx = resolve::Context::new(bump);
95        ctx.resolve_module(self)?;
96        Ok(ctx.finish())
97    }
98}
99
100/// A node in the hugr AST.
101///
102/// See [`table::Node`] for the table representation.
103///
104/// [`table::Node`]: crate::v0::table::Node
105#[derive(Debug, Clone, PartialEq, Eq, Default)]
106pub struct Node {
107    /// The operation that the node performs.
108    pub operation: Operation,
109
110    /// The names of the links connected to the input ports of the node.
111    pub inputs: Box<[LinkName]>,
112
113    /// The names of the links connected to the output ports of the node.
114    pub outputs: Box<[LinkName]>,
115
116    /// The regions in the node.
117    pub regions: Box<[Region]>,
118
119    /// Metadata attached to the node.
120    pub meta: Box<[Term]>,
121
122    /// The input/output signature of the node.
123    pub signature: Option<Term>,
124}
125
126/// The operation of a [`Node`] in the hugr AST.
127///
128/// See [`table::Operation`] for the table representation.
129///
130/// [`table::Operation`]: crate::v0::table::Operation
131#[derive(Debug, Clone, PartialEq, Eq, Default)]
132pub enum Operation {
133    /// Invalid operation to be used as a placeholder.
134    #[default]
135    Invalid,
136    /// Data flow graphs.
137    Dfg,
138    /// Control flow graphs.
139    Cfg,
140    /// Basic blocks in a control flow graph.
141    Block,
142    /// Function definitions.
143    DefineFunc(Box<Symbol>),
144    /// Function declarations.
145    DeclareFunc(Box<Symbol>),
146    /// Custom operations.
147    Custom(Term),
148    /// Alias definitions.
149    DefineAlias(Box<Symbol>, Term),
150    /// Alias declarations.
151    DeclareAlias(Box<Symbol>),
152    /// Tail controlled loops.
153    TailLoop,
154    /// Conditional operations.
155    Conditional,
156    /// Constructor declarations.
157    DeclareConstructor(Box<Symbol>),
158    /// Operation declarations.
159    DeclareOperation(Box<Symbol>),
160    /// Symbol imports.
161    Import(SymbolName),
162}
163
164impl Operation {
165    /// The name of the symbol introduced by this operation, if any.
166    #[must_use]
167    pub fn symbol_name(&self) -> Option<&SymbolName> {
168        if let Operation::Import(symbol_name) = self {
169            Some(symbol_name)
170        } else {
171            Some(&self.symbol()?.name)
172        }
173    }
174
175    /// The symbol declared or defined by this operation, if any.
176    #[must_use]
177    pub fn symbol(&self) -> Option<&Symbol> {
178        match self {
179            Operation::DefineFunc(symbol)
180            | Operation::DeclareFunc(symbol)
181            | Operation::DefineAlias(symbol, _)
182            | Operation::DeclareAlias(symbol)
183            | Operation::DeclareConstructor(symbol)
184            | Operation::DeclareOperation(symbol) => Some(symbol),
185            _ => None,
186        }
187    }
188}
189
190/// A symbol declaration in the hugr AST.
191///
192/// See [`table::Symbol`] for the table representation.
193///
194/// [`table::Symbol`]: crate::v0::table::Symbol
195#[derive(Debug, Clone, PartialEq, Eq)]
196pub struct Symbol {
197    /// The visibility of the symbol.
198    pub visibility: Option<Visibility>,
199    /// The name of the symbol.
200    pub name: SymbolName,
201    /// The parameters of the symbol.
202    pub params: Box<[Param]>,
203    /// Constraints that the symbol imposes on the parameters.j
204    pub constraints: Box<[Term]>,
205    /// The type of the terms produced when the symbol is applied.
206    pub signature: Term,
207}
208
209/// A parameter of a [`Symbol`] in the hugr AST.
210///
211/// See [`table::Param`] for the table representation.
212///
213/// [`table::Param`]: crate::v0::table::Param
214#[derive(Debug, Clone, PartialEq, Eq)]
215pub struct Param {
216    /// The name of the parameter.
217    pub name: VarName,
218    /// The type of the parameter.
219    pub r#type: Term,
220}
221
222/// A region in the hugr AST.
223///
224/// See [`table::Region`] for the table representation.
225///
226/// [`table::Region`]: crate::v0::table::Region
227#[derive(Debug, Clone, PartialEq, Eq, Default)]
228pub struct Region {
229    /// The kind of the region. See [`RegionKind`] for details.
230    pub kind: RegionKind,
231    /// The names of the links connected to the source ports of the region.
232    pub sources: Box<[LinkName]>,
233    /// The names of the links connected to the target ports of the region.
234    pub targets: Box<[LinkName]>,
235    /// The nodes in the region. The order of the nodes is not significant.
236    pub children: Box<[Node]>,
237    /// The metadata attached to the region.
238    pub meta: Box<[Term]>,
239    /// The source/target signature of the region.
240    pub signature: Option<Term>,
241}
242
243/// A term in the hugr AST.
244///
245/// To facilitate sharing where possible, terms in the AST use reference
246/// counting. This makes it cheap to clone and share terms.
247///
248/// See [`table::Term`] for the table representation.
249///
250/// [`table::Term`]: crate::v0::table::Term
251#[derive(Debug, Clone, PartialEq, Eq, Default)]
252pub enum Term {
253    /// Standin for any term.
254    #[default]
255    Wildcard,
256    /// Local variable, identified by its name.
257    Var(VarName),
258    /// Symbol application.
259    Apply(SymbolName, Arc<[Term]>),
260    /// List of static data.
261    List(Arc<[SeqPart]>),
262    /// Static literal value.
263    Literal(Literal),
264    /// Tuple of static data.
265    Tuple(Arc<[SeqPart]>),
266    /// Function constant.
267    Func(Arc<Region>),
268}
269
270impl From<Literal> for Term {
271    fn from(value: Literal) -> Self {
272        Self::Literal(value)
273    }
274}
275
276/// A part of a tuple/list [`Term`] in the hugr AST.
277///
278/// See [`table::SeqPart`] for the table representation.
279///
280/// [`table::SeqPart`]: crate::v0::table::SeqPart
281#[derive(Debug, Clone, PartialEq, Eq)]
282pub enum SeqPart {
283    /// An individual item in the sequence.
284    Item(Term),
285    /// A sequence to be spliced into this sequence.
286    Splice(Term),
287}
hugr_model/v0/ast/mod.rs

hugr_model/v0/ast/
mod.rs
