hugr_core/
import.rs

1//! Importing HUGR graphs from their `hugr-model` representation.
2//!
3//! **Warning**: This module is still under development and is expected to change.
4//! It is included in the library to allow for early experimentation, and for
5//! the core and model to converge incrementally.
6use std::sync::Arc;
7
8use crate::{
9    Direction, Hugr, HugrView, Node, Port,
10    extension::{
11        ExtensionId, ExtensionRegistry, SignatureError, resolution::ExtensionResolutionError,
12    },
13    hugr::{HugrMut, NodeMetadata},
14    ops::{
15        AliasDecl, AliasDefn, CFG, Call, CallIndirect, Case, Conditional, Const, DFG,
16        DataflowBlock, ExitBlock, FuncDecl, FuncDefn, Input, LoadConstant, LoadFunction, OpType,
17        OpaqueOp, Output, Tag, TailLoop, Value,
18        constant::{CustomConst, CustomSerialized, OpaqueValue},
19    },
20    package::Package,
21    std_extensions::{
22        arithmetic::{float_types::ConstF64, int_types::ConstInt},
23        collections::array::ArrayValue,
24    },
25    types::{
26        CustomType, FuncTypeBase, MaybeRV, PolyFuncType, PolyFuncTypeBase, RowVariable, Signature,
27        Term, Type, TypeArg, TypeBase, TypeBound, TypeEnum, TypeName, TypeRow,
28        type_param::{SeqPart, TypeParam},
29        type_row::TypeRowBase,
30    },
31};
32use fxhash::FxHashMap;
33use hugr_model::v0::table;
34use hugr_model::v0::{self as model};
35use itertools::{Either, Itertools};
36use smol_str::{SmolStr, ToSmolStr};
37use thiserror::Error;
38
39fn gen_str(generator: &Option<String>) -> String {
40    match generator {
41        Some(g) => format!(" generated by {g}"),
42        None => String::new(),
43    }
44}
45
46/// An error that can occur during import.
47#[derive(Debug, Clone, Error)]
48#[error("failed to import hugr{}", gen_str(&self.generator))]
49pub struct ImportError {
50    #[source]
51    inner: ImportErrorInner,
52    generator: Option<String>,
53}
54
55#[derive(Debug, Clone, Error)]
56enum ImportErrorInner {
57    /// The model contains a feature that is not supported by the importer yet.
58    /// Errors of this kind are expected to be removed as the model format and
59    /// the core HUGR representation converge.
60    #[error("currently unsupported: {0}")]
61    Unsupported(String),
62
63    /// The model contains implicit information that has not yet been inferred.
64    /// This includes wildcards and application of functions with implicit parameters.
65    #[error("uninferred implicit: {0}")]
66    Uninferred(String),
67
68    /// The model is not well-formed.
69    #[error("{0}")]
70    Invalid(String),
71
72    /// An error with additional context.
73    #[error("import failed in context: {1}")]
74    Context(#[source] Box<ImportErrorInner>, String),
75
76    /// A signature mismatch was detected during import.
77    #[error("signature error")]
78    Signature(#[from] SignatureError),
79
80    /// An error relating to the loaded extension registry.
81    #[error("extension error")]
82    Extension(#[from] ExtensionError),
83
84    /// Incorrect order hints.
85    #[error("incorrect order hint")]
86    OrderHint(#[from] OrderHintError),
87
88    /// Extension resolution.
89    #[error("extension resolution error")]
90    ExtensionResolution(#[from] ExtensionResolutionError),
91}
92
93#[derive(Debug, Clone, Error)]
94enum ExtensionError {
95    /// An extension is missing.
96    #[error("Importing the hugr requires extension {missing_ext}, which was not found in the registry. The available extensions are: [{}]",
97            available.iter().map(std::string::ToString::to_string).collect::<Vec<_>>().join(", "))]
98    Missing {
99        /// The missing extension.
100        missing_ext: ExtensionId,
101        /// The available extensions in the registry.
102        available: Vec<ExtensionId>,
103    },
104
105    /// An extension type is missing.
106    #[error(
107        "Importing the hugr requires extension {ext} to have a type named {name}, but it was not found."
108    )]
109    MissingType {
110        /// The extension that is missing the type.
111        ext: ExtensionId,
112        /// The name of the missing type.
113        name: TypeName,
114    },
115}
116
117/// Import error caused by incorrect order hints.
118#[derive(Debug, Clone, Error)]
119enum OrderHintError {
120    /// Duplicate order hint key in the same region.
121    #[error("duplicate order hint key {0}")]
122    DuplicateKey(table::RegionId, u64),
123    /// Order hint including a key not defined in the region.
124    #[error("order hint with unknown key {0}")]
125    UnknownKey(u64),
126    /// Order hint involving a node with no order port.
127    #[error("order hint on node with no order port: {0}")]
128    NoOrderPort(table::NodeId),
129}
130
131/// Helper macro to create an `ImportErrorInner::Unsupported` error with a formatted message.
132macro_rules! error_unsupported {
133    ($($e:expr),*) => { ImportErrorInner::Unsupported(format!($($e),*)) }
134}
135
136/// Helper macro to create an `ImportErrorInner::Uninferred` error with a formatted message.
137macro_rules! error_uninferred {
138    ($($e:expr),*) => { ImportErrorInner::Uninferred(format!($($e),*)) }
139}
140
141/// Helper macro to create an `ImportErrorInner::Invalid` error with a formatted message.
142macro_rules! error_invalid {
143    ($($e:expr),*) => { ImportErrorInner::Invalid(format!($($e),*)) }
144}
145
146/// Helper macro to create an `ImportErrorInner::Context` error with a formatted message.
147macro_rules! error_context {
148    ($err:expr, $($e:expr),*) => {
149        {
150            ImportErrorInner::Context(Box::new($err), format!($($e),*))
151        }
152    }
153}
154
155/// Import a [`Package`] from its model representation.
156pub fn import_package(
157    package: &table::Package,
158    extensions: &ExtensionRegistry,
159) -> Result<Package, ImportError> {
160    let modules = package
161        .modules
162        .iter()
163        .map(|module| import_hugr(module, extensions))
164        .collect::<Result<Vec<_>, _>>()?;
165
166    // This does not panic since the import already requires a module root.
167    let package = Package::new(modules);
168    Ok(package)
169}
170
171/// Get the name of the generator from the metadata of the module.
172/// If no generator is found, `None` is returned.
173fn get_generator(ctx: &Context<'_>) -> Option<String> {
174    ctx.module
175        .get_region(ctx.module.root)
176        .map(|r| r.meta.iter())
177        .into_iter()
178        .flatten()
179        .find_map(|meta| {
180            let (name, json_val) = ctx.decode_json_meta(*meta).ok()??;
181
182            (name == crate::envelope::GENERATOR_KEY)
183                .then_some(crate::envelope::format_generator(&json_val))
184        })
185}
186
187/// Import a [`Hugr`] module from its model representation.
188pub fn import_hugr(
189    module: &table::Module,
190    extensions: &ExtensionRegistry,
191) -> Result<Hugr, ImportError> {
192    // TODO: Module should know about the number of edges, so that we can use a vector here.
193    // For now we use a hashmap, which will be slower.
194    let mut ctx = Context {
195        module,
196        hugr: Hugr::new(),
197        link_ports: FxHashMap::default(),
198        static_edges: Vec::new(),
199        extensions,
200        nodes: FxHashMap::default(),
201        local_vars: FxHashMap::default(),
202        custom_name_cache: FxHashMap::default(),
203        region_scope: table::RegionId::default(),
204    };
205
206    let import_steps: [fn(&mut Context) -> _; 3] = [
207        |ctx| ctx.import_root(),
208        |ctx| ctx.link_ports(),
209        |ctx| ctx.link_static_ports(),
210    ];
211
212    for step in import_steps {
213        if let Err(e) = step(&mut ctx) {
214            return Err(ImportError {
215                inner: e,
216                generator: get_generator(&ctx),
217            });
218        }
219    }
220    ctx.hugr
221        .resolve_extension_defs(extensions)
222        .map_err(|e| ImportError {
223            inner: ImportErrorInner::ExtensionResolution(e),
224            generator: get_generator(&ctx),
225        })?;
226    Ok(ctx.hugr)
227}
228
229struct Context<'a> {
230    /// The module being imported.
231    module: &'a table::Module<'a>,
232
233    /// The HUGR graph being constructed.
234    hugr: Hugr,
235
236    /// The ports that are part of each link. This is used to connect the ports at the end of the
237    /// import process.
238    link_ports: FxHashMap<(table::RegionId, table::LinkIndex), Vec<(Node, Port)>>,
239
240    /// Pairs of nodes that should be connected by a static edge.
241    /// These are collected during the import process and connected at the end.
242    static_edges: Vec<(table::NodeId, table::NodeId)>,
243
244    /// The ambient extension registry to use for importing.
245    extensions: &'a ExtensionRegistry,
246
247    /// A map from `NodeId` to the imported `Node`.
248    nodes: FxHashMap<table::NodeId, Node>,
249
250    local_vars: FxHashMap<table::VarId, LocalVar>,
251
252    custom_name_cache: FxHashMap<&'a str, (ExtensionId, SmolStr)>,
253
254    region_scope: table::RegionId,
255}
256
257impl<'a> Context<'a> {
258    /// Get the signature of the node with the given `NodeId`.
259    fn get_node_signature(&mut self, node: table::NodeId) -> Result<Signature, ImportErrorInner> {
260        let node_data = self.get_node(node)?;
261        let signature = node_data
262            .signature
263            .ok_or_else(|| error_uninferred!("node signature"))?;
264        self.import_func_type(signature)
265    }
266
267    /// Get the node with the given `NodeId`, or return an error if it does not exist.
268    #[inline]
269    fn get_node(&self, node_id: table::NodeId) -> Result<&'a table::Node<'a>, ImportErrorInner> {
270        self.module
271            .get_node(node_id)
272            .ok_or_else(|| error_invalid!("unknown node {}", node_id))
273    }
274
275    /// Get the term with the given `TermId`, or return an error if it does not exist.
276    #[inline]
277    fn get_term(&self, term_id: table::TermId) -> Result<&'a table::Term<'a>, ImportErrorInner> {
278        self.module
279            .get_term(term_id)
280            .ok_or_else(|| error_invalid!("unknown term {}", term_id))
281    }
282
283    /// Get the region with the given `RegionId`, or return an error if it does not exist.
284    #[inline]
285    fn get_region(
286        &self,
287        region_id: table::RegionId,
288    ) -> Result<&'a table::Region<'a>, ImportErrorInner> {
289        self.module
290            .get_region(region_id)
291            .ok_or_else(|| error_invalid!("unknown region {}", region_id))
292    }
293
294    fn make_node(
295        &mut self,
296        node_id: table::NodeId,
297        op: OpType,
298        parent: Node,
299    ) -> Result<Node, ImportErrorInner> {
300        let node = self.hugr.add_node_with_parent(parent, op);
301        self.nodes.insert(node_id, node);
302
303        let node_data = self.get_node(node_id)?;
304        self.record_links(node, Direction::Incoming, node_data.inputs);
305        self.record_links(node, Direction::Outgoing, node_data.outputs);
306
307        for meta_item in node_data.meta {
308            self.import_node_metadata(node, *meta_item)
309                .map_err(|err| error_context!(err, "node metadata"))?;
310        }
311
312        Ok(node)
313    }
314
315    fn import_node_metadata(
316        &mut self,
317        node: Node,
318        meta_item: table::TermId,
319    ) -> Result<(), ImportErrorInner> {
320        // Import the JSON metadata
321        if let Some((name, json_value)) = self.decode_json_meta(meta_item)? {
322            self.hugr.set_metadata(node, name, json_value);
323        }
324
325        // Set the entrypoint
326        if let Some([]) = self.match_symbol(meta_item, model::CORE_ENTRYPOINT)? {
327            self.hugr.set_entrypoint(node);
328        }
329
330        Ok(())
331    }
332
333    fn decode_json_meta(
334        &self,
335        meta_item: table::TermId,
336    ) -> Result<Option<(SmolStr, serde_json::Value)>, ImportErrorInner> {
337        Ok(
338            if let Some([name_arg, json_arg]) =
339                self.match_symbol(meta_item, model::COMPAT_META_JSON)?
340            {
341                let table::Term::Literal(model::Literal::Str(name)) = self.get_term(name_arg)?
342                else {
343                    return Err(error_invalid!(
344                        "`{}` expects a string literal as its first argument",
345                        model::COMPAT_META_JSON
346                    ));
347                };
348
349                let table::Term::Literal(model::Literal::Str(json_str)) =
350                    self.get_term(json_arg)?
351                else {
352                    return Err(error_invalid!(
353                        "`{}` expects a string literal as its second argument",
354                        model::COMPAT_CONST_JSON
355                    ));
356                };
357
358                let json_value: NodeMetadata = serde_json::from_str(json_str).map_err(|_| {
359                    error_invalid!(
360                        "failed to parse JSON string for `{}` metadata",
361                        model::COMPAT_CONST_JSON
362                    )
363                })?;
364                Some((name.to_owned(), json_value))
365            } else {
366                None
367            },
368        )
369    }
370
371    /// Associate links with the ports of the given node in the given direction.
372    fn record_links(&mut self, node: Node, direction: Direction, links: &'a [table::LinkIndex]) {
373        let optype = self.hugr.get_optype(node);
374        // NOTE: `OpType::port_count` copies the signature, which significantly slows down the import.
375        debug_assert!(links.len() <= optype.port_count(direction));
376
377        for (link, port) in links.iter().zip(self.hugr.node_ports(node, direction)) {
378            self.link_ports
379                .entry((self.region_scope, *link))
380                .or_default()
381                .push((node, port));
382        }
383    }
384
385    /// Link up the ports in the hugr graph, according to the connectivity information that
386    /// has been gathered in the `link_ports` map.
387    fn link_ports(&mut self) -> Result<(), ImportErrorInner> {
388        // For each edge, we group the ports by their direction. We reuse the `inputs` and
389        // `outputs` vectors to avoid unnecessary allocations.
390        let mut inputs = Vec::new();
391        let mut outputs = Vec::new();
392
393        for (link_id, link_ports) in std::mem::take(&mut self.link_ports) {
394            // Skip the edge if it doesn't have any ports.
395            if link_ports.is_empty() {
396                continue;
397            }
398
399            for (node, port) in link_ports {
400                match port.as_directed() {
401                    Either::Left(input) => inputs.push((node, input)),
402                    Either::Right(output) => outputs.push((node, output)),
403                }
404            }
405
406            match (inputs.as_slice(), outputs.as_slice()) {
407                ([], []) => {
408                    unreachable!();
409                }
410                (_, [output]) => {
411                    for (node, port) in &inputs {
412                        self.hugr.connect(output.0, output.1, *node, *port);
413                    }
414                }
415                ([input], _) => {
416                    for (node, port) in &outputs {
417                        self.hugr.connect(*node, *port, input.0, input.1);
418                    }
419                }
420                _ => {
421                    return Err(error_unsupported!(
422                        "link {:?} would require hyperedge",
423                        link_id
424                    ));
425                }
426            }
427
428            inputs.clear();
429            outputs.clear();
430        }
431
432        Ok(())
433    }
434
435    fn link_static_ports(&mut self) -> Result<(), ImportErrorInner> {
436        for (src_id, dst_id) in std::mem::take(&mut self.static_edges) {
437            // None of these lookups should fail given how we constructed `static_edges`.
438            let src = self.nodes[&src_id];
439            let dst = self.nodes[&dst_id];
440            let src_port = self.hugr.get_optype(src).static_output_port().unwrap();
441            let dst_port = self.hugr.get_optype(dst).static_input_port().unwrap();
442            self.hugr.connect(src, src_port, dst, dst_port);
443        }
444
445        Ok(())
446    }
447
448    fn get_symbol_name(&self, node_id: table::NodeId) -> Result<&'a str, ImportErrorInner> {
449        let node_data = self.get_node(node_id)?;
450        let name = node_data
451            .operation
452            .symbol()
453            .ok_or_else(|| error_invalid!("node {} is expected to be a symbol", node_id))?;
454        Ok(name)
455    }
456
457    fn get_func_signature(
458        &mut self,
459        func_node: table::NodeId,
460    ) -> Result<PolyFuncType, ImportErrorInner> {
461        let symbol = match self.get_node(func_node)?.operation {
462            table::Operation::DefineFunc(symbol) => symbol,
463            table::Operation::DeclareFunc(symbol) => symbol,
464            _ => {
465                return Err(error_invalid!(
466                    "node {} is expected to be a function declaration or definition",
467                    func_node
468                ));
469            }
470        };
471
472        self.import_poly_func_type(func_node, *symbol, |_, signature| Ok(signature))
473    }
474
475    /// Import the root region of the module.
476    fn import_root(&mut self) -> Result<(), ImportErrorInner> {
477        self.region_scope = self.module.root;
478        let region_data = self.get_region(self.module.root)?;
479
480        for node in region_data.children {
481            self.import_node(*node, self.hugr.module_root())?;
482        }
483
484        for meta_item in region_data.meta {
485            self.import_node_metadata(self.hugr.module_root(), *meta_item)?;
486        }
487
488        Ok(())
489    }
490
491    fn import_node(
492        &mut self,
493        node_id: table::NodeId,
494        parent: Node,
495    ) -> Result<Option<Node>, ImportErrorInner> {
496        let node_data = self.get_node(node_id)?;
497
498        let result = match node_data.operation {
499            table::Operation::Invalid => {
500                return Err(error_invalid!("tried to import an `invalid` operation"));
501            }
502
503            table::Operation::Dfg => Some(
504                self.import_node_dfg(node_id, parent, node_data)
505                    .map_err(|err| error_context!(err, "`dfg` node with id {}", node_id))?,
506            ),
507
508            table::Operation::Cfg => Some(
509                self.import_node_cfg(node_id, parent, node_data)
510                    .map_err(|err| error_context!(err, "`cfg` node with id {}", node_id))?,
511            ),
512
513            table::Operation::Block => Some(
514                self.import_node_block(node_id, parent)
515                    .map_err(|err| error_context!(err, "`block` node with id {}", node_id))?,
516            ),
517
518            table::Operation::DefineFunc(symbol) => Some(
519                self.import_node_define_func(node_id, symbol, node_data, parent)
520                    .map_err(|err| error_context!(err, "`define-func` node with id {}", node_id))?,
521            ),
522
523            table::Operation::DeclareFunc(symbol) => Some(
524                self.import_node_declare_func(node_id, symbol, parent)
525                    .map_err(|err| {
526                        error_context!(err, "`declare-func` node with id {}", node_id)
527                    })?,
528            ),
529
530            table::Operation::TailLoop => Some(
531                self.import_tail_loop(node_id, parent)
532                    .map_err(|err| error_context!(err, "`tail-loop` node with id {}", node_id))?,
533            ),
534
535            table::Operation::Conditional => Some(
536                self.import_conditional(node_id, parent)
537                    .map_err(|err| error_context!(err, "`cond` node with id {}", node_id))?,
538            ),
539
540            table::Operation::Custom(operation) => Some(
541                self.import_node_custom(node_id, operation, node_data, parent)
542                    .map_err(|err| error_context!(err, "custom node with id {}", node_id))?,
543            ),
544
545            table::Operation::DefineAlias(symbol, value) => Some(
546                self.import_node_define_alias(node_id, symbol, value, parent)
547                    .map_err(|err| {
548                        error_context!(err, "`define-alias` node with id {}", node_id)
549                    })?,
550            ),
551
552            table::Operation::DeclareAlias(symbol) => Some(
553                self.import_node_declare_alias(node_id, symbol, parent)
554                    .map_err(|err| {
555                        error_context!(err, "`declare-alias` node with id {}", node_id)
556                    })?,
557            ),
558
559            table::Operation::Import { .. } => None,
560
561            table::Operation::DeclareConstructor { .. } => None,
562            table::Operation::DeclareOperation { .. } => None,
563        };
564
565        Ok(result)
566    }
567
568    fn import_node_dfg(
569        &mut self,
570        node_id: table::NodeId,
571        parent: Node,
572        node_data: &'a table::Node<'a>,
573    ) -> Result<Node, ImportErrorInner> {
574        let signature = self
575            .get_node_signature(node_id)
576            .map_err(|err| error_context!(err, "node signature"))?;
577
578        let optype = OpType::DFG(DFG { signature });
579        let node = self.make_node(node_id, optype, parent)?;
580
581        let [region] = node_data.regions else {
582            return Err(error_invalid!("dfg region expects a single region"));
583        };
584
585        self.import_dfg_region(*region, node)?;
586        Ok(node)
587    }
588
589    fn import_node_cfg(
590        &mut self,
591        node_id: table::NodeId,
592        parent: Node,
593        node_data: &'a table::Node<'a>,
594    ) -> Result<Node, ImportErrorInner> {
595        let signature = self
596            .get_node_signature(node_id)
597            .map_err(|err| error_context!(err, "node signature"))?;
598
599        let optype = OpType::CFG(CFG { signature });
600        let node = self.make_node(node_id, optype, parent)?;
601
602        let [region] = node_data.regions else {
603            return Err(error_invalid!("cfg nodes expect a single region"));
604        };
605
606        self.import_cfg_region(*region, node)?;
607        Ok(node)
608    }
609
610    fn import_dfg_region(
611        &mut self,
612        region: table::RegionId,
613        node: Node,
614    ) -> Result<(), ImportErrorInner> {
615        let region_data = self.get_region(region)?;
616
617        let prev_region = self.region_scope;
618        if region_data.scope.is_some() {
619            self.region_scope = region;
620        }
621
622        if region_data.kind != model::RegionKind::DataFlow {
623            return Err(error_invalid!("expected dfg region"));
624        }
625
626        let signature = self
627            .import_func_type(
628                region_data
629                    .signature
630                    .ok_or_else(|| error_uninferred!("region signature"))?,
631            )
632            .map_err(|err| error_context!(err, "signature of dfg region with id {}", region))?;
633
634        // Create the input and output nodes
635        let input = self.hugr.add_node_with_parent(
636            node,
637            OpType::Input(Input {
638                types: signature.input,
639            }),
640        );
641        let output = self.hugr.add_node_with_parent(
642            node,
643            OpType::Output(Output {
644                types: signature.output,
645            }),
646        );
647
648        // Make sure that the ports of the input/output nodes are connected correctly
649        self.record_links(input, Direction::Outgoing, region_data.sources);
650        self.record_links(output, Direction::Incoming, region_data.targets);
651
652        for child in region_data.children {
653            self.import_node(*child, node)?;
654        }
655
656        self.create_order_edges(region, input, output)?;
657
658        for meta_item in region_data.meta {
659            self.import_node_metadata(node, *meta_item)?;
660        }
661
662        self.region_scope = prev_region;
663
664        Ok(())
665    }
666
667    /// Create order edges between nodes of a dataflow region based on order hint metadata.
668    ///
669    /// This method assumes that the nodes for the children of the region have already been imported.
670    fn create_order_edges(
671        &mut self,
672        region_id: table::RegionId,
673        input: Node,
674        output: Node,
675    ) -> Result<(), ImportErrorInner> {
676        let region_data = self.get_region(region_id)?;
677        debug_assert_eq!(region_data.kind, model::RegionKind::DataFlow);
678
679        // Collect order hint keys
680        // PERFORMANCE: It might be worthwhile to reuse the map to avoid allocations.
681        let mut order_keys = FxHashMap::<u64, Node>::default();
682
683        for child_id in region_data.children {
684            let child_data = self.get_node(*child_id)?;
685
686            for meta_id in child_data.meta {
687                let Some([key]) = self.match_symbol(*meta_id, model::ORDER_HINT_KEY)? else {
688                    continue;
689                };
690
691                let table::Term::Literal(model::Literal::Nat(key)) = self.get_term(key)? else {
692                    continue;
693                };
694
695                // NOTE: The lookups here are expected to succeed since we only
696                // process the order metadata after we have imported the nodes.
697                let child_node = self.nodes[child_id];
698                let child_optype = self.hugr.get_optype(child_node);
699
700                // Check that the node has order ports.
701                // NOTE: This assumes that a node has an input order port iff it has an output one.
702                if child_optype.other_output_port().is_none() {
703                    return Err(OrderHintError::NoOrderPort(*child_id).into());
704                }
705
706                if order_keys.insert(*key, child_node).is_some() {
707                    return Err(OrderHintError::DuplicateKey(region_id, *key).into());
708                }
709            }
710        }
711
712        // Collect the order hint keys for the input and output nodes
713        for meta_id in region_data.meta {
714            if let Some([key]) = self.match_symbol(*meta_id, model::ORDER_HINT_INPUT_KEY)? {
715                let table::Term::Literal(model::Literal::Nat(key)) = self.get_term(key)? else {
716                    continue;
717                };
718
719                if order_keys.insert(*key, input).is_some() {
720                    return Err(OrderHintError::DuplicateKey(region_id, *key).into());
721                }
722            }
723
724            if let Some([key]) = self.match_symbol(*meta_id, model::ORDER_HINT_OUTPUT_KEY)? {
725                let table::Term::Literal(model::Literal::Nat(key)) = self.get_term(key)? else {
726                    continue;
727                };
728
729                if order_keys.insert(*key, output).is_some() {
730                    return Err(OrderHintError::DuplicateKey(region_id, *key).into());
731                }
732            }
733        }
734
735        // Insert order edges
736        for meta_id in region_data.meta {
737            let Some([a, b]) = self.match_symbol(*meta_id, model::ORDER_HINT_ORDER)? else {
738                continue;
739            };
740
741            let table::Term::Literal(model::Literal::Nat(a)) = self.get_term(a)? else {
742                continue;
743            };
744
745            let table::Term::Literal(model::Literal::Nat(b)) = self.get_term(b)? else {
746                continue;
747            };
748
749            let a = order_keys.get(a).ok_or(OrderHintError::UnknownKey(*a))?;
750            let b = order_keys.get(b).ok_or(OrderHintError::UnknownKey(*b))?;
751
752            // NOTE: The unwrap here must succeed:
753            // - For all ordinary nodes we checked that they have an order port.
754            // - Input and output nodes always have an order port.
755            let a_port = self.hugr.get_optype(*a).other_output_port().unwrap();
756            let b_port = self.hugr.get_optype(*b).other_input_port().unwrap();
757
758            self.hugr.connect(*a, a_port, *b, b_port);
759        }
760
761        Ok(())
762    }
763
764    fn import_adt_and_rest(
765        &mut self,
766        list: table::TermId,
767    ) -> Result<(Vec<TypeRow>, TypeRow), ImportErrorInner> {
768        let items = self.import_closed_list(list)?;
769
770        let Some((first, rest)) = items.split_first() else {
771            return Err(error_invalid!("expected list to have at least one element"));
772        };
773
774        let sum_rows: Vec<_> = {
775            let [variants] = self.expect_symbol(*first, model::CORE_ADT)?;
776            self.import_type_rows(variants)?
777        };
778
779        let rest = rest
780            .iter()
781            .map(|term| self.import_type(*term))
782            .collect::<Result<Vec<_>, _>>()?
783            .into();
784
785        Ok((sum_rows, rest))
786    }
787
788    fn import_tail_loop(
789        &mut self,
790        node_id: table::NodeId,
791        parent: Node,
792    ) -> Result<Node, ImportErrorInner> {
793        let node_data = self.get_node(node_id)?;
794        debug_assert_eq!(node_data.operation, table::Operation::TailLoop);
795
796        let [region] = node_data.regions else {
797            return Err(error_invalid!(
798                "loop node {} expects a single region",
799                node_id
800            ));
801        };
802
803        let region_data = self.get_region(*region)?;
804
805        let (just_inputs, just_outputs, rest) = (|| {
806            let [_, region_outputs] = self.get_func_type(
807                region_data
808                    .signature
809                    .ok_or_else(|| error_uninferred!("region signature"))?,
810            )?;
811            let (sum_rows, rest) = self.import_adt_and_rest(region_outputs)?;
812
813            if sum_rows.len() != 2 {
814                return Err(error_invalid!(
815                    "loop nodes expect their first target to be an ADT with two variants"
816                ));
817            }
818
819            let mut sum_rows = sum_rows.into_iter();
820            let just_inputs = sum_rows.next().unwrap();
821            let just_outputs = sum_rows.next().unwrap();
822
823            Ok((just_inputs, just_outputs, rest))
824        })()
825        .map_err(|err| error_context!(err, "region signature"))?;
826
827        let optype = OpType::TailLoop(TailLoop {
828            just_inputs,
829            just_outputs,
830            rest,
831        });
832
833        let node = self.make_node(node_id, optype, parent)?;
834
835        self.import_dfg_region(*region, node)?;
836        Ok(node)
837    }
838
839    fn import_conditional(
840        &mut self,
841        node_id: table::NodeId,
842        parent: Node,
843    ) -> Result<Node, ImportErrorInner> {
844        let node_data = self.get_node(node_id)?;
845        debug_assert_eq!(node_data.operation, table::Operation::Conditional);
846
847        let (sum_rows, other_inputs, outputs) = (|| {
848            let [inputs, outputs] = self.get_func_type(
849                node_data
850                    .signature
851                    .ok_or_else(|| error_uninferred!("node signature"))?,
852            )?;
853            let (sum_rows, other_inputs) = self.import_adt_and_rest(inputs)?;
854            let outputs = self.import_type_row(outputs)?;
855
856            Ok((sum_rows, other_inputs, outputs))
857        })()
858        .map_err(|err| error_context!(err, "node signature"))?;
859
860        let optype = OpType::Conditional(Conditional {
861            sum_rows,
862            other_inputs,
863            outputs,
864        });
865
866        let node = self.make_node(node_id, optype, parent)?;
867
868        for region in node_data.regions {
869            let region_data = self.get_region(*region)?;
870            let signature = self.import_func_type(
871                region_data
872                    .signature
873                    .ok_or_else(|| error_uninferred!("region signature"))?,
874            )?;
875
876            let case_node = self
877                .hugr
878                .add_node_with_parent(node, OpType::Case(Case { signature }));
879
880            self.import_dfg_region(*region, case_node)?;
881        }
882
883        Ok(node)
884    }
885
886    fn import_cfg_region(
887        &mut self,
888        region: table::RegionId,
889        node: Node,
890    ) -> Result<(), ImportErrorInner> {
891        let region_data = self.get_region(region)?;
892
893        if region_data.kind != model::RegionKind::ControlFlow {
894            return Err(error_invalid!("expected cfg region"));
895        }
896
897        let prev_region = self.region_scope;
898        if region_data.scope.is_some() {
899            self.region_scope = region;
900        }
901
902        let region_target_types = (|| {
903            let [_, region_targets] = self.get_ctrl_type(
904                region_data
905                    .signature
906                    .ok_or_else(|| error_uninferred!("region signature"))?,
907            )?;
908
909            self.import_closed_list(region_targets)
910        })()
911        .map_err(|err| error_context!(err, "signature of cfg region with id {}", region))?;
912
913        // Identify the entry node of the control flow region by looking for
914        // a block whose input is linked to the sole source port of the CFG region.
915        let entry_node = 'find_entry: {
916            let [entry_link] = region_data.sources else {
917                return Err(error_invalid!("cfg region expects a single source"));
918            };
919
920            for child in region_data.children {
921                let child_data = self.get_node(*child)?;
922                let is_entry = child_data.inputs.iter().any(|link| link == entry_link);
923
924                if is_entry {
925                    break 'find_entry *child;
926                }
927            }
928
929            // TODO: We should allow for the case in which control flows
930            // directly from the source to the target of the region. This is
931            // currently not allowed in hugr core directly, but may be simulated
932            // by constructing an empty entry block.
933            return Err(error_invalid!("cfg region without entry node"));
934        };
935
936        // The entry node in core control flow regions is identified by being
937        // the first child node of the CFG node. We therefore import the entry node first.
938        self.import_node(entry_node, node)?;
939
940        // Create the exit node for the control flow region. This always needs
941        // to be second in the node list.
942        {
943            let cfg_outputs = {
944                let [target_types] = region_target_types.as_slice() else {
945                    return Err(error_invalid!("cfg region expects a single target"));
946                };
947
948                self.import_type_row(*target_types)?
949            };
950
951            let exit = self
952                .hugr
953                .add_node_with_parent(node, OpType::ExitBlock(ExitBlock { cfg_outputs }));
954            self.record_links(exit, Direction::Incoming, region_data.targets);
955        }
956
957        // Finally we import all other nodes.
958        for child in region_data.children {
959            if *child != entry_node {
960                self.import_node(*child, node)?;
961            }
962        }
963
964        for meta_item in region_data.meta {
965            self.import_node_metadata(node, *meta_item)
966                .map_err(|err| error_context!(err, "node metadata"))?;
967        }
968
969        self.region_scope = prev_region;
970
971        Ok(())
972    }
973
974    fn import_node_block(
975        &mut self,
976        node_id: table::NodeId,
977        parent: Node,
978    ) -> Result<Node, ImportErrorInner> {
979        let node_data = self.get_node(node_id)?;
980        debug_assert_eq!(node_data.operation, table::Operation::Block);
981
982        let [region] = node_data.regions else {
983            return Err(error_invalid!("basic block expects a single region"));
984        };
985        let region_data = self.get_region(*region)?;
986        let [inputs, outputs] = self.get_func_type(
987            region_data
988                .signature
989                .ok_or_else(|| error_uninferred!("region signature"))?,
990        )?;
991        let inputs = self.import_type_row(inputs)?;
992        let (sum_rows, other_outputs) = self.import_adt_and_rest(outputs)?;
993
994        let optype = OpType::DataflowBlock(DataflowBlock {
995            inputs,
996            other_outputs,
997            sum_rows,
998        });
999        let node = self.make_node(node_id, optype, parent)?;
1000
1001        self.import_dfg_region(*region, node).map_err(|err| {
1002            error_context!(err, "block body defined by region with id {}", *region)
1003        })?;
1004        Ok(node)
1005    }
1006
1007    fn import_node_define_func(
1008        &mut self,
1009        node_id: table::NodeId,
1010        symbol: &'a table::Symbol<'a>,
1011        node_data: &'a table::Node<'a>,
1012        parent: Node,
1013    ) -> Result<Node, ImportErrorInner> {
1014        let visibility = symbol.visibility.clone().ok_or(ImportErrorInner::Invalid(
1015            "No visibility for FuncDefn".to_string(),
1016        ))?;
1017        self.import_poly_func_type(node_id, *symbol, |ctx, signature| {
1018            let func_name = ctx.import_title_metadata(node_id)?.unwrap_or(symbol.name);
1019
1020            let optype =
1021                OpType::FuncDefn(FuncDefn::new_vis(func_name, signature, visibility.into()));
1022
1023            let node = ctx.make_node(node_id, optype, parent)?;
1024
1025            let [region] = node_data.regions else {
1026                return Err(error_invalid!(
1027                    "function definition nodes expect a single region"
1028                ));
1029            };
1030
1031            ctx.import_dfg_region(*region, node).map_err(|err| {
1032                error_context!(err, "function body defined by region with id {}", *region)
1033            })?;
1034
1035            Ok(node)
1036        })
1037    }
1038
1039    fn import_node_declare_func(
1040        &mut self,
1041        node_id: table::NodeId,
1042        symbol: &'a table::Symbol<'a>,
1043        parent: Node,
1044    ) -> Result<Node, ImportErrorInner> {
1045        let visibility = symbol.visibility.clone().ok_or(ImportErrorInner::Invalid(
1046            "No visibility for FuncDecl".to_string(),
1047        ))?;
1048        self.import_poly_func_type(node_id, *symbol, |ctx, signature| {
1049            let func_name = ctx.import_title_metadata(node_id)?.unwrap_or(symbol.name);
1050
1051            let optype =
1052                OpType::FuncDecl(FuncDecl::new_vis(func_name, signature, visibility.into()));
1053            let node = ctx.make_node(node_id, optype, parent)?;
1054            Ok(node)
1055        })
1056    }
1057
1058    fn import_node_custom(
1059        &mut self,
1060        node_id: table::NodeId,
1061        operation: table::TermId,
1062        node_data: &'a table::Node<'a>,
1063        parent: Node,
1064    ) -> Result<Node, ImportErrorInner> {
1065        if let Some([inputs, outputs]) = self.match_symbol(operation, model::CORE_CALL_INDIRECT)? {
1066            let inputs = self.import_type_row(inputs)?;
1067            let outputs = self.import_type_row(outputs)?;
1068            let signature = Signature::new(inputs, outputs);
1069            let optype = OpType::CallIndirect(CallIndirect { signature });
1070            let node = self.make_node(node_id, optype, parent)?;
1071            return Ok(node);
1072        }
1073
1074        if let Some([_, _, func]) = self.match_symbol(operation, model::CORE_CALL)? {
1075            let table::Term::Apply(symbol, args) = self.get_term(func)? else {
1076                return Err(error_invalid!(
1077                    "expected a symbol application to be passed to `{}`",
1078                    model::CORE_CALL
1079                ));
1080            };
1081
1082            let func_sig = self.get_func_signature(*symbol)?;
1083
1084            let type_args = args
1085                .iter()
1086                .map(|term| self.import_term(*term))
1087                .collect::<Result<Vec<TypeArg>, _>>()?;
1088
1089            self.static_edges.push((*symbol, node_id));
1090            let optype = OpType::Call(
1091                Call::try_new(func_sig, type_args).map_err(ImportErrorInner::Signature)?,
1092            );
1093
1094            let node = self.make_node(node_id, optype, parent)?;
1095            return Ok(node);
1096        }
1097
1098        if let Some([_, value]) = self.match_symbol(operation, model::CORE_LOAD_CONST)? {
1099            // If the constant refers directly to a function, import this as the `LoadFunc` operation.
1100            if let table::Term::Apply(symbol, args) = self.get_term(value)? {
1101                let func_node_data = self.get_node(*symbol)?;
1102
1103                if let table::Operation::DefineFunc(_) | table::Operation::DeclareFunc(_) =
1104                    func_node_data.operation
1105                {
1106                    let func_sig = self.get_func_signature(*symbol)?;
1107                    let type_args = args
1108                        .iter()
1109                        .map(|term| self.import_term(*term))
1110                        .collect::<Result<Vec<TypeArg>, _>>()?;
1111
1112                    self.static_edges.push((*symbol, node_id));
1113
1114                    let optype = OpType::LoadFunction(
1115                        LoadFunction::try_new(func_sig, type_args)
1116                            .map_err(ImportErrorInner::Signature)?,
1117                    );
1118
1119                    let node = self.make_node(node_id, optype, parent)?;
1120                    return Ok(node);
1121                }
1122            }
1123
1124            // Otherwise use const nodes
1125            let signature = node_data
1126                .signature
1127                .ok_or_else(|| error_uninferred!("node signature"))?;
1128            let [_, outputs] = self.get_func_type(signature)?;
1129            let outputs = self.import_closed_list(outputs)?;
1130            let output = outputs.first().ok_or_else(|| {
1131                error_invalid!("`{}` expects a single output", model::CORE_LOAD_CONST)
1132            })?;
1133            let datatype = self.import_type(*output)?;
1134
1135            let imported_value = self.import_value(value, *output)?;
1136
1137            let load_const_node = self.make_node(
1138                node_id,
1139                OpType::LoadConstant(LoadConstant {
1140                    datatype: datatype.clone(),
1141                }),
1142                parent,
1143            )?;
1144
1145            let const_node = self
1146                .hugr
1147                .add_node_with_parent(parent, OpType::Const(Const::new(imported_value)));
1148
1149            self.hugr.connect(const_node, 0, load_const_node, 0);
1150
1151            return Ok(load_const_node);
1152        }
1153
1154        if let Some([_, _, tag]) = self.match_symbol(operation, model::CORE_MAKE_ADT)? {
1155            let table::Term::Literal(model::Literal::Nat(tag)) = self.get_term(tag)? else {
1156                return Err(error_invalid!(
1157                    "`{}` expects a nat literal tag",
1158                    model::CORE_MAKE_ADT
1159                ));
1160            };
1161
1162            let signature = node_data
1163                .signature
1164                .ok_or_else(|| error_uninferred!("node signature"))?;
1165            let [_, outputs] = self.get_func_type(signature)?;
1166            let (variants, _) = self.import_adt_and_rest(outputs)?;
1167            let node = self.make_node(
1168                node_id,
1169                OpType::Tag(Tag {
1170                    variants,
1171                    tag: *tag as usize,
1172                }),
1173                parent,
1174            )?;
1175            return Ok(node);
1176        }
1177
1178        let table::Term::Apply(node, params) = self.get_term(operation)? else {
1179            return Err(error_invalid!(
1180                "custom operations expect a symbol application referencing an operation"
1181            ));
1182        };
1183        let name = self.get_symbol_name(*node)?;
1184        let args = params
1185            .iter()
1186            .map(|param| self.import_term(*param))
1187            .collect::<Result<Vec<_>, _>>()?;
1188        let (extension, name) = self.import_custom_name(name)?;
1189        let signature = self.get_node_signature(node_id)?;
1190
1191        // TODO: Currently we do not have the description or any other metadata for
1192        // the custom op. This will improve with declarative extensions being able
1193        // to declare operations as a node, in which case the description will be attached
1194        // to that node as metadata.
1195
1196        let optype = OpType::OpaqueOp(OpaqueOp::new(extension, name, args, signature));
1197        self.make_node(node_id, optype, parent)
1198    }
1199
1200    fn import_node_define_alias(
1201        &mut self,
1202        node_id: table::NodeId,
1203        symbol: &'a table::Symbol<'a>,
1204        value: table::TermId,
1205        parent: Node,
1206    ) -> Result<Node, ImportErrorInner> {
1207        if !symbol.params.is_empty() {
1208            return Err(error_unsupported!(
1209                "parameters or constraints in alias definition"
1210            ));
1211        }
1212
1213        let optype = OpType::AliasDefn(AliasDefn {
1214            name: symbol.name.to_smolstr(),
1215            definition: self.import_type(value)?,
1216        });
1217
1218        let node = self.make_node(node_id, optype, parent)?;
1219        Ok(node)
1220    }
1221
1222    fn import_node_declare_alias(
1223        &mut self,
1224        node_id: table::NodeId,
1225        symbol: &'a table::Symbol<'a>,
1226        parent: Node,
1227    ) -> Result<Node, ImportErrorInner> {
1228        if !symbol.params.is_empty() {
1229            return Err(error_unsupported!(
1230                "parameters or constraints in alias declaration"
1231            ));
1232        }
1233
1234        let optype = OpType::AliasDecl(AliasDecl {
1235            name: symbol.name.to_smolstr(),
1236            bound: TypeBound::Copyable,
1237        });
1238
1239        let node = self.make_node(node_id, optype, parent)?;
1240        Ok(node)
1241    }
1242
1243    fn import_poly_func_type<RV: MaybeRV, T>(
1244        &mut self,
1245        node: table::NodeId,
1246        symbol: table::Symbol<'a>,
1247        in_scope: impl FnOnce(&mut Self, PolyFuncTypeBase<RV>) -> Result<T, ImportErrorInner>,
1248    ) -> Result<T, ImportErrorInner> {
1249        (|| {
1250            let mut imported_params = Vec::with_capacity(symbol.params.len());
1251
1252            for (index, param) in symbol.params.iter().enumerate() {
1253                self.local_vars
1254                    .insert(table::VarId(node, index as _), LocalVar::new(param.r#type));
1255            }
1256
1257            for constraint in symbol.constraints {
1258                if let Some([term]) = self.match_symbol(*constraint, model::CORE_NON_LINEAR)? {
1259                    let table::Term::Var(var) = self.get_term(term)? else {
1260                        return Err(error_unsupported!(
1261                            "constraint on term that is not a variable"
1262                        ));
1263                    };
1264
1265                    self.local_vars
1266                        .get_mut(var)
1267                        .ok_or_else(|| error_invalid!("unknown variable {}", var))?
1268                        .bound = TypeBound::Copyable;
1269                } else {
1270                    return Err(error_unsupported!("constraint other than copy or discard"));
1271                }
1272            }
1273
1274            for (index, param) in symbol.params.iter().enumerate() {
1275                // NOTE: `PolyFuncType` only has explicit type parameters at present.
1276                let bound = self.local_vars[&table::VarId(node, index as _)].bound;
1277                imported_params.push(
1278                    self.import_term_with_bound(param.r#type, bound)
1279                        .map_err(|err| error_context!(err, "type of parameter `{}`", param.name))?,
1280                );
1281            }
1282
1283            let body = self.import_func_type::<RV>(symbol.signature)?;
1284            in_scope(self, PolyFuncTypeBase::new(imported_params, body))
1285        })()
1286        .map_err(|err| error_context!(err, "symbol `{}` defined by node {}", symbol.name, node))
1287    }
1288
1289    /// Import a [`Term`] from a term that represents a static type or value.
1290    fn import_term(&mut self, term_id: table::TermId) -> Result<Term, ImportErrorInner> {
1291        self.import_term_with_bound(term_id, TypeBound::Linear)
1292    }
1293
1294    fn import_term_with_bound(
1295        &mut self,
1296        term_id: table::TermId,
1297        bound: TypeBound,
1298    ) -> Result<Term, ImportErrorInner> {
1299        (|| {
1300            if let Some([]) = self.match_symbol(term_id, model::CORE_STR_TYPE)? {
1301                return Ok(Term::StringType);
1302            }
1303
1304            if let Some([]) = self.match_symbol(term_id, model::CORE_NAT_TYPE)? {
1305                return Ok(Term::max_nat_type());
1306            }
1307
1308            if let Some([]) = self.match_symbol(term_id, model::CORE_BYTES_TYPE)? {
1309                return Ok(Term::BytesType);
1310            }
1311
1312            if let Some([]) = self.match_symbol(term_id, model::CORE_FLOAT_TYPE)? {
1313                return Ok(Term::FloatType);
1314            }
1315
1316            if let Some([]) = self.match_symbol(term_id, model::CORE_TYPE)? {
1317                return Ok(TypeParam::RuntimeType(bound));
1318            }
1319
1320            if let Some([]) = self.match_symbol(term_id, model::CORE_CONSTRAINT)? {
1321                return Err(error_unsupported!("`{}`", model::CORE_CONSTRAINT));
1322            }
1323
1324            if let Some([]) = self.match_symbol(term_id, model::CORE_STATIC)? {
1325                return Ok(Term::StaticType);
1326            }
1327
1328            if let Some([ty]) = self.match_symbol(term_id, model::CORE_CONST)? {
1329                let ty = self
1330                    .import_type(ty)
1331                    .map_err(|err| error_context!(err, "type of a constant"))?;
1332                return Ok(TypeParam::new_const(ty));
1333            }
1334
1335            if let Some([item_type]) = self.match_symbol(term_id, model::CORE_LIST_TYPE)? {
1336                // At present `hugr-model` has no way to express that the item
1337                // type of a list must be copyable. Therefore we import it as `Any`.
1338                let item_type = self
1339                    .import_term(item_type)
1340                    .map_err(|err| error_context!(err, "item type of list type"))?;
1341                return Ok(TypeParam::new_list_type(item_type));
1342            }
1343
1344            if let Some([item_types]) = self.match_symbol(term_id, model::CORE_TUPLE_TYPE)? {
1345                // At present `hugr-model` has no way to express that the item
1346                // types of a tuple must be copyable. Therefore we import it as `Any`.
1347                let item_types = self
1348                    .import_term(item_types)
1349                    .map_err(|err| error_context!(err, "item types of tuple type"))?;
1350                return Ok(TypeParam::new_tuple_type(item_types));
1351            }
1352
1353            match self.get_term(term_id)? {
1354                table::Term::Wildcard => Err(error_uninferred!("wildcard")),
1355
1356                table::Term::Var(var) => {
1357                    let var_info = self
1358                        .local_vars
1359                        .get(var)
1360                        .ok_or_else(|| error_invalid!("unknown variable {}", var))?;
1361                    let decl = self.import_term_with_bound(var_info.r#type, var_info.bound)?;
1362                    Ok(Term::new_var_use(var.1 as _, decl))
1363                }
1364
1365                table::Term::List(parts) => {
1366                    // PERFORMANCE: Can we do this without the additional allocation?
1367                    let parts: Vec<_> = parts
1368                        .iter()
1369                        .map(|part| self.import_seq_part(part))
1370                        .collect::<Result<_, _>>()
1371                        .map_err(|err| error_context!(err, "list parts"))?;
1372                    Ok(TypeArg::new_list_from_parts(parts))
1373                }
1374
1375                table::Term::Tuple(parts) => {
1376                    // PERFORMANCE: Can we do this without the additional allocation?
1377                    let parts: Vec<_> = parts
1378                        .iter()
1379                        .map(|part| self.import_seq_part(part))
1380                        .try_collect()
1381                        .map_err(|err| error_context!(err, "tuple parts"))?;
1382                    Ok(TypeArg::new_tuple_from_parts(parts))
1383                }
1384
1385                table::Term::Literal(model::Literal::Str(value)) => {
1386                    Ok(Term::String(value.to_string()))
1387                }
1388
1389                table::Term::Literal(model::Literal::Nat(value)) => Ok(Term::BoundedNat(*value)),
1390
1391                table::Term::Literal(model::Literal::Bytes(value)) => {
1392                    Ok(Term::Bytes(value.clone()))
1393                }
1394                table::Term::Literal(model::Literal::Float(value)) => Ok(Term::Float(*value)),
1395                table::Term::Func { .. } => Err(error_unsupported!("function constant")),
1396
1397                table::Term::Apply { .. } => {
1398                    let ty: Type = self.import_type(term_id)?;
1399                    Ok(ty.into())
1400                }
1401            }
1402        })()
1403        .map_err(|err| error_context!(err, "term {}", term_id))
1404    }
1405
1406    fn import_seq_part(
1407        &mut self,
1408        seq_part: &'a table::SeqPart,
1409    ) -> Result<SeqPart<TypeArg>, ImportErrorInner> {
1410        Ok(match seq_part {
1411            table::SeqPart::Item(term_id) => SeqPart::Item(self.import_term(*term_id)?),
1412            table::SeqPart::Splice(term_id) => SeqPart::Splice(self.import_term(*term_id)?),
1413        })
1414    }
1415
1416    /// Import a `Type` from a term that represents a runtime type.
1417    fn import_type<RV: MaybeRV>(
1418        &mut self,
1419        term_id: table::TermId,
1420    ) -> Result<TypeBase<RV>, ImportErrorInner> {
1421        (|| {
1422            if let Some([_, _]) = self.match_symbol(term_id, model::CORE_FN)? {
1423                let func_type = self.import_func_type::<RowVariable>(term_id)?;
1424                return Ok(TypeBase::new_function(func_type));
1425            }
1426
1427            if let Some([variants]) = self.match_symbol(term_id, model::CORE_ADT)? {
1428                let variants = (|| {
1429                    self.import_closed_list(variants)?
1430                        .iter()
1431                        .map(|variant| self.import_type_row::<RowVariable>(*variant))
1432                        .collect::<Result<Vec<_>, _>>()
1433                })()
1434                .map_err(|err| error_context!(err, "adt variants"))?;
1435
1436                return Ok(TypeBase::new_sum(variants));
1437            }
1438
1439            match self.get_term(term_id)? {
1440                table::Term::Wildcard => Err(error_uninferred!("wildcard")),
1441
1442                table::Term::Apply(symbol, args) => {
1443                    let name = self.get_symbol_name(*symbol)?;
1444
1445                    let args = args
1446                        .iter()
1447                        .map(|arg| self.import_term(*arg))
1448                        .collect::<Result<Vec<_>, _>>()
1449                        .map_err(|err| {
1450                            error_context!(err, "type argument of custom type `{}`", name)
1451                        })?;
1452
1453                    let (extension, id) = self.import_custom_name(name)?;
1454
1455                    let extension_ref =
1456                        self.extensions
1457                            .get(&extension)
1458                            .ok_or_else(|| ExtensionError::Missing {
1459                                missing_ext: extension.clone(),
1460                                available: self.extensions.ids().cloned().collect(),
1461                            })?;
1462
1463                    let ext_type =
1464                        extension_ref
1465                            .get_type(&id)
1466                            .ok_or_else(|| ExtensionError::MissingType {
1467                                ext: extension.clone(),
1468                                name: id.clone(),
1469                            })?;
1470
1471                    let bound = ext_type.bound(&args);
1472
1473                    Ok(TypeBase::new_extension(CustomType::new(
1474                        id,
1475                        args,
1476                        extension,
1477                        bound,
1478                        &Arc::downgrade(extension_ref),
1479                    )))
1480                }
1481
1482                table::Term::Var(var @ table::VarId(_, index)) => {
1483                    let local_var = self
1484                        .local_vars
1485                        .get(var)
1486                        .ok_or(error_invalid!("unknown var {}", var))?;
1487                    Ok(TypeBase::new_var_use(*index as _, local_var.bound))
1488                }
1489
1490                // The following terms are not runtime types, but the core `Type` only contains runtime types.
1491                // We therefore report a type error here.
1492                table::Term::List { .. }
1493                | table::Term::Tuple { .. }
1494                | table::Term::Literal(_)
1495                | table::Term::Func { .. } => Err(error_invalid!("expected a runtime type")),
1496            }
1497        })()
1498        .map_err(|err| error_context!(err, "term {} as `Type`", term_id))
1499    }
1500
1501    fn get_func_type(
1502        &mut self,
1503        term_id: table::TermId,
1504    ) -> Result<[table::TermId; 2], ImportErrorInner> {
1505        self.match_symbol(term_id, model::CORE_FN)?
1506            .ok_or(error_invalid!("expected a function type"))
1507    }
1508
1509    fn get_ctrl_type(
1510        &mut self,
1511        term_id: table::TermId,
1512    ) -> Result<[table::TermId; 2], ImportErrorInner> {
1513        self.match_symbol(term_id, model::CORE_CTRL)?
1514            .ok_or(error_invalid!("expected a control type"))
1515    }
1516
1517    fn import_func_type<RV: MaybeRV>(
1518        &mut self,
1519        term_id: table::TermId,
1520    ) -> Result<FuncTypeBase<RV>, ImportErrorInner> {
1521        (|| {
1522            let [inputs, outputs] = self.get_func_type(term_id)?;
1523            let inputs = self
1524                .import_type_row(inputs)
1525                .map_err(|err| error_context!(err, "function inputs"))?;
1526            let outputs = self
1527                .import_type_row(outputs)
1528                .map_err(|err| error_context!(err, "function outputs"))?;
1529            Ok(FuncTypeBase::new(inputs, outputs))
1530        })()
1531        .map_err(|err| error_context!(err, "function type"))
1532    }
1533
1534    fn import_closed_list(
1535        &mut self,
1536        term_id: table::TermId,
1537    ) -> Result<Vec<table::TermId>, ImportErrorInner> {
1538        fn import_into(
1539            ctx: &mut Context,
1540            term_id: table::TermId,
1541            types: &mut Vec<table::TermId>,
1542        ) -> Result<(), ImportErrorInner> {
1543            match ctx.get_term(term_id)? {
1544                table::Term::List(parts) => {
1545                    types.reserve(parts.len());
1546
1547                    for part in *parts {
1548                        match part {
1549                            table::SeqPart::Item(term_id) => {
1550                                types.push(*term_id);
1551                            }
1552                            table::SeqPart::Splice(term_id) => {
1553                                import_into(ctx, *term_id, types)?;
1554                            }
1555                        }
1556                    }
1557                }
1558                _ => return Err(error_invalid!("expected a closed list")),
1559            }
1560
1561            Ok(())
1562        }
1563
1564        let mut types = Vec::new();
1565        import_into(self, term_id, &mut types)?;
1566        Ok(types)
1567    }
1568
1569    fn import_closed_tuple(
1570        &mut self,
1571        term_id: table::TermId,
1572    ) -> Result<Vec<table::TermId>, ImportErrorInner> {
1573        fn import_into(
1574            ctx: &mut Context,
1575            term_id: table::TermId,
1576            types: &mut Vec<table::TermId>,
1577        ) -> Result<(), ImportErrorInner> {
1578            match ctx.get_term(term_id)? {
1579                table::Term::Tuple(parts) => {
1580                    types.reserve(parts.len());
1581
1582                    for part in *parts {
1583                        match part {
1584                            table::SeqPart::Item(term_id) => {
1585                                types.push(*term_id);
1586                            }
1587                            table::SeqPart::Splice(term_id) => {
1588                                import_into(ctx, *term_id, types)?;
1589                            }
1590                        }
1591                    }
1592                }
1593                _ => return Err(error_invalid!("expected a closed tuple")),
1594            }
1595
1596            Ok(())
1597        }
1598
1599        let mut types = Vec::new();
1600        import_into(self, term_id, &mut types)?;
1601        Ok(types)
1602    }
1603
1604    fn import_type_rows<RV: MaybeRV>(
1605        &mut self,
1606        term_id: table::TermId,
1607    ) -> Result<Vec<TypeRowBase<RV>>, ImportErrorInner> {
1608        self.import_closed_list(term_id)?
1609            .into_iter()
1610            .map(|term_id| self.import_type_row::<RV>(term_id))
1611            .collect()
1612    }
1613
1614    fn import_type_row<RV: MaybeRV>(
1615        &mut self,
1616        term_id: table::TermId,
1617    ) -> Result<TypeRowBase<RV>, ImportErrorInner> {
1618        fn import_into<RV: MaybeRV>(
1619            ctx: &mut Context,
1620            term_id: table::TermId,
1621            types: &mut Vec<TypeBase<RV>>,
1622        ) -> Result<(), ImportErrorInner> {
1623            match ctx.get_term(term_id)? {
1624                table::Term::List(parts) => {
1625                    types.reserve(parts.len());
1626
1627                    for item in *parts {
1628                        match item {
1629                            table::SeqPart::Item(term_id) => {
1630                                types.push(ctx.import_type::<RV>(*term_id)?);
1631                            }
1632                            table::SeqPart::Splice(term_id) => {
1633                                import_into(ctx, *term_id, types)?;
1634                            }
1635                        }
1636                    }
1637                }
1638                table::Term::Var(table::VarId(_, index)) => {
1639                    let var = RV::try_from_rv(RowVariable(*index as _, TypeBound::Linear))
1640                        .map_err(|_| error_invalid!("expected a closed list"))?;
1641                    types.push(TypeBase::new(TypeEnum::RowVar(var)));
1642                }
1643                _ => return Err(error_invalid!("expected a list")),
1644            }
1645
1646            Ok(())
1647        }
1648
1649        let mut types = Vec::new();
1650        import_into(self, term_id, &mut types)?;
1651        Ok(types.into())
1652    }
1653
1654    fn import_custom_name(
1655        &mut self,
1656        symbol: &'a str,
1657    ) -> Result<(ExtensionId, SmolStr), ImportErrorInner> {
1658        use std::collections::hash_map::Entry;
1659        match self.custom_name_cache.entry(symbol) {
1660            Entry::Occupied(occupied_entry) => Ok(occupied_entry.get().clone()),
1661            Entry::Vacant(vacant_entry) => {
1662                let qualified_name = ExtensionId::new(symbol)
1663                    .map_err(|_| error_invalid!("`{}` is not a valid symbol name", symbol))?;
1664
1665                let (extension, id) = qualified_name
1666                    .split_last()
1667                    .ok_or_else(|| error_invalid!("`{}` is not a valid symbol name", symbol))?;
1668
1669                vacant_entry.insert((extension.clone(), id.clone()));
1670                Ok((extension, id))
1671            }
1672        }
1673    }
1674
1675    fn import_value(
1676        &mut self,
1677        term_id: table::TermId,
1678        type_id: table::TermId,
1679    ) -> Result<Value, ImportErrorInner> {
1680        let term_data = self.get_term(term_id)?;
1681
1682        // NOTE: We have special cased arrays, integers, and floats for now.
1683        // TODO: Allow arbitrary extension values to be imported from terms.
1684
1685        if let Some([runtime_type, json]) = self.match_symbol(term_id, model::COMPAT_CONST_JSON)? {
1686            let table::Term::Literal(model::Literal::Str(json)) = self.get_term(json)? else {
1687                return Err(error_invalid!(
1688                    "`{}` expects a string literal",
1689                    model::COMPAT_CONST_JSON
1690                ));
1691            };
1692
1693            // We attempt to deserialize as the custom const directly.
1694            // This might fail due to the custom const struct not being included when
1695            // this code was compiled; in that case, we fall back to the serialized form.
1696            let value: Option<Box<dyn CustomConst>> = serde_json::from_str(json).ok();
1697
1698            if let Some(value) = value {
1699                let opaque_value = OpaqueValue::from(value);
1700                return Ok(Value::Extension { e: opaque_value });
1701            } else {
1702                let runtime_type = self.import_type(runtime_type)?;
1703                let value: serde_json::Value = serde_json::from_str(json).map_err(|_| {
1704                    error_invalid!(
1705                        "unable to parse JSON string for `{}`",
1706                        model::COMPAT_CONST_JSON
1707                    )
1708                })?;
1709                let custom_const = CustomSerialized::new(runtime_type, value);
1710                let opaque_value = OpaqueValue::new(custom_const);
1711                return Ok(Value::Extension { e: opaque_value });
1712            }
1713        }
1714
1715        if let Some([_, element_type_term, contents]) =
1716            self.match_symbol(term_id, ArrayValue::CTR_NAME)?
1717        {
1718            let element_type = self.import_type(element_type_term)?;
1719            let contents = self.import_closed_list(contents)?;
1720            let contents = contents
1721                .iter()
1722                .map(|item| self.import_value(*item, element_type_term))
1723                .collect::<Result<Vec<_>, _>>()?;
1724            return Ok(ArrayValue::new(element_type, contents).into());
1725        }
1726
1727        if let Some([bitwidth, value]) = self.match_symbol(term_id, ConstInt::CTR_NAME)? {
1728            let bitwidth = {
1729                let table::Term::Literal(model::Literal::Nat(bitwidth)) =
1730                    self.get_term(bitwidth)?
1731                else {
1732                    return Err(error_invalid!(
1733                        "`{}` expects a nat literal in its `bitwidth` argument",
1734                        ConstInt::CTR_NAME
1735                    ));
1736                };
1737                if *bitwidth > 6 {
1738                    return Err(error_invalid!(
1739                        "`{}` expects the bitwidth to be at most 6, got {}",
1740                        ConstInt::CTR_NAME,
1741                        bitwidth
1742                    ));
1743                }
1744                *bitwidth as u8
1745            };
1746
1747            let value = {
1748                let table::Term::Literal(model::Literal::Nat(value)) = self.get_term(value)? else {
1749                    return Err(error_invalid!(
1750                        "`{}` expects a nat literal value",
1751                        ConstInt::CTR_NAME
1752                    ));
1753                };
1754                *value
1755            };
1756
1757            return Ok(ConstInt::new_u(bitwidth, value)
1758                .map_err(|_| error_invalid!("failed to create int constant"))?
1759                .into());
1760        }
1761
1762        if let Some([value]) = self.match_symbol(term_id, ConstF64::CTR_NAME)? {
1763            let table::Term::Literal(model::Literal::Float(value)) = self.get_term(value)? else {
1764                return Err(error_invalid!(
1765                    "`{}` expects a float literal value",
1766                    ConstF64::CTR_NAME
1767                ));
1768            };
1769
1770            return Ok(ConstF64::new(value.into_inner()).into());
1771        }
1772
1773        if let Some([_, _, tag, values]) = self.match_symbol(term_id, model::CORE_CONST_ADT)? {
1774            let [variants] = self.expect_symbol(type_id, model::CORE_ADT)?;
1775            let values = self.import_closed_tuple(values)?;
1776            let variants = self.import_closed_list(variants)?;
1777
1778            let table::Term::Literal(model::Literal::Nat(tag)) = self.get_term(tag)? else {
1779                return Err(error_invalid!(
1780                    "`{}` expects a nat literal tag",
1781                    model::CORE_ADT
1782                ));
1783            };
1784
1785            let variant = variants.get(*tag as usize).ok_or(error_invalid!(
1786                "the tag of a `{}` must be a valid index into the list of variants",
1787                model::CORE_CONST_ADT
1788            ))?;
1789
1790            let variant = self.import_closed_list(*variant)?;
1791
1792            let items = values
1793                .iter()
1794                .zip(variant.iter())
1795                .map(|(value, typ)| self.import_value(*value, *typ))
1796                .collect::<Result<Vec<_>, _>>()?;
1797
1798            let typ = {
1799                // TODO: Import as a `SumType` directly and avoid the copy.
1800                let typ: Type = self.import_type(type_id)?;
1801                match typ.as_type_enum() {
1802                    TypeEnum::Sum(sum) => sum.clone(),
1803                    _ => unreachable!(),
1804                }
1805            };
1806
1807            return Ok(Value::sum(*tag as _, items, typ).unwrap());
1808        }
1809
1810        match term_data {
1811            table::Term::Wildcard => Err(error_uninferred!("wildcard")),
1812            table::Term::Var(_) => Err(error_unsupported!("constant value containing a variable")),
1813
1814            table::Term::Apply(symbol, _) => {
1815                let symbol_name = self.get_symbol_name(*symbol)?;
1816                Err(error_unsupported!(
1817                    "unknown custom constant value `{}`",
1818                    symbol_name
1819                ))
1820                // TODO: This should ultimately include the following cases:
1821                // - function definitions
1822                // - custom constructors for values
1823            }
1824
1825            table::Term::List { .. } | table::Term::Tuple(_) | table::Term::Literal(_) => {
1826                Err(error_invalid!("expected constant"))
1827            }
1828
1829            table::Term::Func { .. } => Err(error_unsupported!("constant function value")),
1830        }
1831    }
1832
1833    fn match_symbol<const N: usize>(
1834        &self,
1835        term_id: table::TermId,
1836        name: &str,
1837    ) -> Result<Option<[table::TermId; N]>, ImportErrorInner> {
1838        let term = self.get_term(term_id)?;
1839
1840        // TODO: Follow alias chains?
1841
1842        let table::Term::Apply(symbol, args) = term else {
1843            return Ok(None);
1844        };
1845
1846        if name != self.get_symbol_name(*symbol)? {
1847            return Ok(None);
1848        }
1849
1850        // We allow the match even if the symbol is applied to fewer arguments
1851        // than parameters. In that case, the arguments are padded with wildcards
1852        // at the beginning.
1853        if args.len() > N {
1854            return Ok(None);
1855        }
1856
1857        let result = std::array::from_fn(|i| {
1858            (i + args.len())
1859                .checked_sub(N)
1860                .map(|i| args[i])
1861                .unwrap_or_default()
1862        });
1863
1864        Ok(Some(result))
1865    }
1866
1867    fn expect_symbol<const N: usize>(
1868        &self,
1869        term_id: table::TermId,
1870        name: &str,
1871    ) -> Result<[table::TermId; N], ImportErrorInner> {
1872        self.match_symbol(term_id, name)?.ok_or(error_invalid!(
1873            "expected symbol `{}` with arity {}",
1874            name,
1875            N
1876        ))
1877    }
1878
1879    /// Searches for `core.title` metadata on the given node.
1880    fn import_title_metadata(
1881        &self,
1882        node_id: table::NodeId,
1883    ) -> Result<Option<&'a str>, ImportErrorInner> {
1884        let node_data = self.get_node(node_id)?;
1885        for meta in node_data.meta {
1886            let Some([name]) = self.match_symbol(*meta, model::CORE_TITLE)? else {
1887                continue;
1888            };
1889
1890            let table::Term::Literal(model::Literal::Str(name)) = self.get_term(name)? else {
1891                return Err(error_invalid!(
1892                    "`{}` metadata expected a string literal as argument",
1893                    model::CORE_TITLE
1894                ));
1895            };
1896
1897            return Ok(Some(name.as_str()));
1898        }
1899
1900        Ok(None)
1901    }
1902}
1903
1904/// Information about a local variable.
1905#[derive(Debug, Clone, Copy)]
1906struct LocalVar {
1907    /// The type of the variable.
1908    r#type: table::TermId,
1909    /// The type bound of the variable.
1910    bound: TypeBound,
1911}
1912
1913impl LocalVar {
1914    pub fn new(r#type: table::TermId) -> Self {
1915        Self {
1916            r#type,
1917            bound: TypeBound::Linear,
1918        }
1919    }
1920}