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

hugr_model/v0/ast/
mod.rs
