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 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 name of the symbol.
198    pub name: SymbolName,
199    /// The parameters of the symbol.
200    pub params: Box<[Param]>,
201    /// Constraints that the symbol imposes on the parameters.j
202    pub constraints: Box<[Term]>,
203    /// The type of the terms produced when the symbol is applied.
204    pub signature: Term,
205}
206
207/// A parameter of a [`Symbol`] in the hugr AST.
208///
209/// See [`table::Param`] for the table representation.
210///
211/// [`table::Param`]: crate::v0::table::Param
212#[derive(Debug, Clone, PartialEq, Eq)]
213pub struct Param {
214    /// The name of the parameter.
215    pub name: VarName,
216    /// The type of the parameter.
217    pub r#type: Term,
218}
219
220/// A region in the hugr AST.
221///
222/// See [`table::Region`] for the table representation.
223///
224/// [`table::Region`]: crate::v0::table::Region
225#[derive(Debug, Clone, PartialEq, Eq, Default)]
226pub struct Region {
227    /// The kind of the region. See [`RegionKind`] for details.
228    pub kind: RegionKind,
229    /// The names of the links connected to the source ports of the region.
230    pub sources: Box<[LinkName]>,
231    /// The names of the links connected to the target ports of the region.
232    pub targets: Box<[LinkName]>,
233    /// The nodes in the region. The order of the nodes is not significant.
234    pub children: Box<[Node]>,
235    /// The metadata attached to the region.
236    pub meta: Box<[Term]>,
237    /// The source/target signature of the region.
238    pub signature: Option<Term>,
239}
240
241/// A term in the hugr AST.
242///
243/// To facilitate sharing where possible, terms in the AST use reference
244/// counting. This makes it cheap to clone and share terms.
245///
246/// See [`table::Term`] for the table representation.
247///
248/// [`table::Term`]: crate::v0::table::Term
249#[derive(Debug, Clone, PartialEq, Eq, Default)]
250pub enum Term {
251    /// Standin for any term.
252    #[default]
253    Wildcard,
254    /// Local variable, identified by its name.
255    Var(VarName),
256    /// Symbol application.
257    Apply(SymbolName, Arc<[Term]>),
258    /// List of static data.
259    List(Arc<[SeqPart]>),
260    /// Static literal value.
261    Literal(Literal),
262    /// Tuple of static data.
263    Tuple(Arc<[SeqPart]>),
264    /// Function constant.
265    Func(Arc<Region>),
266}
267
268impl From<Literal> for Term {
269    fn from(value: Literal) -> Self {
270        Self::Literal(value)
271    }
272}
273
274/// A part of a tuple/list [`Term`] in the hugr AST.
275///
276/// See [`table::SeqPart`] for the table representation.
277///
278/// [`table::SeqPart`]: crate::v0::table::SeqPart
279#[derive(Debug, Clone, PartialEq, Eq)]
280pub enum SeqPart {
281    /// An individual item in the sequence.
282    Item(Term),
283    /// A sequence to be spliced into this sequence.
284    Splice(Term),
285}
hugr_model/v0/ast/mod.rs

hugr_model/v0/ast/
mod.rs
