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    ///
86    /// Symbols may be versioned either at their import/declaration/definition
87    /// site or at their use site. Unversioned references will be resolved to
88    /// the latest declared version if one is available.
89    ///
90    /// Whenever a symbol is used but not defined in scope, an import node will
91    /// be inserted into the module region and all references to that symbol will
92    /// refer to the import node. This gives the opportunity to link the missing symbols.
93    ///
94    /// [`scope`]: crate::v0::scope
95    pub fn resolve<'a>(
96        &'a self,
97        bump: &'a Bump,
98    ) -> Result<table::Module<'a>, resolve::ResolveError> {
99        let mut ctx = resolve::Context::new(bump);
100        ctx.resolve_module(self)?;
101        Ok(ctx.finish())
102    }
103}
104
105/// A node in the hugr AST.
106///
107/// See [`table::Node`] for the table representation.
108///
109/// [`table::Node`]: crate::v0::table::Node
110#[derive(Debug, Clone, PartialEq, Eq, Default)]
111pub struct Node {
112    /// The operation that the node performs.
113    pub operation: Operation,
114
115    /// The names of the links connected to the input ports of the node.
116    pub inputs: Box<[LinkName]>,
117
118    /// The names of the links connected to the output ports of the node.
119    pub outputs: Box<[LinkName]>,
120
121    /// The regions in the node.
122    pub regions: Box<[Region]>,
123
124    /// Metadata attached to the node.
125    pub meta: Box<[Term]>,
126
127    /// The input/output signature of the node.
128    pub signature: Option<Term>,
129}
130
131/// The operation of a [`Node`] in the hugr AST.
132///
133/// See [`table::Operation`] for the table representation.
134///
135/// [`table::Operation`]: crate::v0::table::Operation
136#[derive(Debug, Clone, PartialEq, Eq, Default)]
137pub enum Operation {
138    /// Invalid operation to be used as a placeholder.
139    #[default]
140    Invalid,
141    /// Data flow graphs.
142    Dfg,
143    /// Control flow graphs.
144    Cfg,
145    /// Basic blocks in a control flow graph.
146    Block,
147    /// Function definitions.
148    DefineFunc(Box<Symbol>),
149    /// Function declarations.
150    DeclareFunc(Box<Symbol>),
151    /// Custom operations.
152    Custom(Term),
153    /// Alias definitions.
154    DefineAlias(Box<Symbol>, Term),
155    /// Alias declarations.
156    DeclareAlias(Box<Symbol>),
157    /// Tail controlled loops.
158    TailLoop,
159    /// Conditional operations.
160    Conditional,
161    /// Constructor declarations.
162    DeclareConstructor(Box<Symbol>),
163    /// Operation declarations.
164    DeclareOperation(Box<Symbol>),
165    /// Symbol imports.
166    Import(SymbolIdent),
167}
168
169impl Operation {
170    /// The name of the symbol introduced by this operation, if any.
171    #[must_use]
172    pub fn symbol_name(&self) -> Option<&SymbolName> {
173        if let Operation::Import(symbol_ident) = self {
174            Some(&symbol_ident.name)
175        } else {
176            Some(&self.symbol()?.name)
177        }
178    }
179
180    /// The name and version of the symbol introduced by this operation, if any.
181    #[must_use]
182    pub fn symbol_binding(&self) -> Option<(&SymbolName, Option<&semver::Version>)> {
183        match self {
184            Operation::Import(symbol_ident) => {
185                Some((&symbol_ident.name, symbol_ident.version.as_ref()))
186            }
187            _ => self
188                .symbol()
189                .map(|symbol| (&symbol.name, symbol.version.as_ref())),
190        }
191    }
192
193    /// The symbol declared or defined by this operation, if any.
194    #[must_use]
195    pub fn symbol(&self) -> Option<&Symbol> {
196        match self {
197            Operation::DefineFunc(symbol)
198            | Operation::DeclareFunc(symbol)
199            | Operation::DefineAlias(symbol, _)
200            | Operation::DeclareAlias(symbol)
201            | Operation::DeclareConstructor(symbol)
202            | Operation::DeclareOperation(symbol) => Some(symbol),
203            _ => None,
204        }
205    }
206}
207
208/// An identifier for a possibly versioned symbol in the hugr AST.
209#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
210pub struct SymbolIdent {
211    /// The symbol name.
212    pub name: SymbolName,
213    /// The extension version associated with the symbol use, if specified.
214    pub version: Option<semver::Version>,
215}
216
217/// A symbol declaration in the hugr AST.
218///
219/// See [`table::Symbol`] for the table representation.
220///
221/// [`table::Symbol`]: crate::v0::table::Symbol
222#[derive(Debug, Clone, PartialEq, Eq)]
223pub struct Symbol {
224    /// The visibility of the symbol.
225    pub visibility: Option<Visibility>,
226    /// The name of the symbol.
227    pub name: SymbolName,
228    /// The extension version associated with this symbol declaration, if any.
229    pub version: Option<semver::Version>,
230    /// The parameters of the symbol.
231    pub params: Box<[Param]>,
232    /// Constraints that the symbol imposes on the parameters.j
233    pub constraints: Box<[Term]>,
234    /// The type of the terms produced when the symbol is applied.
235    pub signature: Term,
236}
237
238/// A parameter of a [`Symbol`] in the hugr AST.
239///
240/// See [`table::Param`] for the table representation.
241///
242/// [`table::Param`]: crate::v0::table::Param
243#[derive(Debug, Clone, PartialEq, Eq)]
244pub struct Param {
245    /// The name of the parameter.
246    pub name: VarName,
247    /// The type of the parameter.
248    pub r#type: Term,
249}
250
251/// A region in the hugr AST.
252///
253/// See [`table::Region`] for the table representation.
254///
255/// [`table::Region`]: crate::v0::table::Region
256#[derive(Debug, Clone, PartialEq, Eq, Default)]
257pub struct Region {
258    /// The kind of the region. See [`RegionKind`] for details.
259    pub kind: RegionKind,
260    /// The names of the links connected to the source ports of the region.
261    pub sources: Box<[LinkName]>,
262    /// The names of the links connected to the target ports of the region.
263    pub targets: Box<[LinkName]>,
264    /// The nodes in the region. The order of the nodes is not significant.
265    pub children: Box<[Node]>,
266    /// The metadata attached to the region.
267    pub meta: Box<[Term]>,
268    /// The source/target signature of the region.
269    pub signature: Option<Term>,
270}
271
272/// A term in the hugr AST.
273///
274/// To facilitate sharing where possible, terms in the AST use reference
275/// counting. This makes it cheap to clone and share terms.
276///
277/// See [`table::Term`] for the table representation.
278///
279/// [`table::Term`]: crate::v0::table::Term
280#[derive(Debug, Clone, PartialEq, Eq, Default)]
281pub enum Term {
282    /// Standin for any term.
283    #[default]
284    Wildcard,
285    /// Local variable, identified by its name.
286    Var(VarName),
287    /// Symbol application.
288    Apply(SymbolIdent, Arc<[Term]>),
289    /// List of static data.
290    List(Arc<[SeqPart]>),
291    /// Static literal value.
292    Literal(Literal),
293    /// Tuple of static data.
294    Tuple(Arc<[SeqPart]>),
295    /// Function constant.
296    Func(Arc<Region>),
297}
298
299impl From<Literal> for Term {
300    fn from(value: Literal) -> Self {
301        Self::Literal(value)
302    }
303}
304
305/// A part of a tuple/list [`Term`] in the hugr AST.
306///
307/// See [`table::SeqPart`] for the table representation.
308///
309/// [`table::SeqPart`]: crate::v0::table::SeqPart
310#[derive(Debug, Clone, PartialEq, Eq)]
311pub enum SeqPart {
312    /// An individual item in the sequence.
313    Item(Term),
314    /// A sequence to be spliced into this sequence.
315    Splice(Term),
316}
hugr_model/v0/ast/mod.rs

hugr_model/v0/ast/
mod.rs
