Module v0 

Version 0.

This module defines representations of the hugr IR as plain data, designed to be as independent of implementation details of the compiler as feasible. It can be used by the core compiler, alternative implementations or tooling that does not need the power/complexity of the full compiler. We provide the following in-memory representations:

• Table: Efficient intermediate data structure to facilitate conversions.
• AST: Abstract syntax tree that uses direct references rather than table indices.

The table and AST format are interconvertible and can be serialised to a binary and text format, respectively:

• Binary: Binary serialisation format optimised for performance and size.
• Text: Human readable s-expression based text format.

Logical Format

The hugr IR is a hierarchical graph data structure. Nodes represent both instructions that manipulate runtime values and symbols which represent named language objects. Instructions have input and output ports and runtime values flow between ports when they are connected by a link.

Nodes are organised into regions and do not have any explicit ordering between them; any schedule that respects the data dependencies between nodes is valid. Previous designs included order-edges that could be added between nodes to further constrain the ordering; as long as this system is still used, order hint metadata can be used to encode the additional ordering constraints.

Regions come in three different kinds. Module regions form the top level of a module and can only contain symbols. Dataflow regions describe how data flows from the region’s source ports to the region’s target ports and are restricted to contain instructions. Controlflow regions are control flow graphs containing dataflow blocks, with control flow originating from the region’s source ports and ending in the region’s target ports.

Terms form a meta language that is used to describe types, parameters and metadata that are known statically. To allow types to be parameterized by statically known values, types and static values are treated uniformly as terms, enabling a restricted form of dependent typing. Terms are extensible declaratively via constructors. Constraints can be used to express more complex validation rules.

Remaining Mismatch with hugr-core

This data model was designed to encode as much of hugr-core as possible while also filling in conceptual gaps and providing a forward-compatible foundation for future development. However, there are still some mismatches with hugr-core that are not addressed by conversions in import/export:

• Some terms can not yet be represented in hugr-core although they should be. Importing such terms will result in an error that declares these terms as currently unsupported.
• In particular hugr-core (as of v0.22.3) only allows to define custom runtime types but can not represent custom term constructors for static types. Implementing support for static Terms in hugr-core will allow to use the term system for extensible metadata and constants. Once that is implemented, the hugr IR will have a unified extension mechanism.
• hugr-core uses a JSON encoding for metadata which is supported by hugr-model via the compat.meta_json metadata constructor. hugr-model further allows to declare custom metadata constructors so that metadata can be composed of terms. These are currently not supported in hugr-core beyond a few exceptions which are hard-coded into the import/export process.
• hugr-core uses JSON encoded constants. Similarly to metadata, hugr-model provides a compatibility mechanism via the compat.const_json constant constructor but also allows to declare custom constant constructors. Import/export has hard-coded support for a small fixed set of these for now.
• In hugr-core a constant is a Value, included in the hugr graph via a Const node. A LoadConst node connects to the Const node via a static edge. Values are separate from Terms in hugr-core and can not refer to local variables or to function nodes. In hugr-model the Const node is not needed: The core.load_const operation takes the constant’s description as a term argument. This enables hugr-model constants to depend on local variables and to refer to functions in the module (removing the need for a separate LoadFunc operation).
• Values in hugr-core have a single representation for every constant. The encoding of constants as terms in hugr-model can use different constructors for the same type of constant value. This can be useful for large constants by enabling efficient encodings. For example, a constant array of integers could have a constructor taking a byte string that consists of the integer values, which is significantly more economical than a generic representation of arrays that has a term for every element.
• The model does not have types with a copy bound as hugr-core does, and instead uses a more general form of type constraints (#1556). Similarly, the model does not have bounded naturals. We perform a conversion for compatibility where possible, but this does not fully cover all potential cases of bounds.
• hugr-model has support for passing closed regions as static parameters to operations, which allows for higher-order operations that require their function arguments to be statically known. We currently do not yet support converting this to hugr-core.
• In a model module, ports are connected when they share the same link. This differs from the type of port connectivity in the graph data structure used by hugr-core. However, hugr-core restricts connectivity so that in any group of connected ports there is at most one output port (for dataflow) or at most one input port (for control flow). In these cases, there is no mismatch.
• hugr-core only allows to define type aliases, but not aliases for other terms. The alias system is under-developed in both hugr-core and hugr-model and will need some considerable design and implementation work (or to be removed if deemed unnecessary). See #2558.

Re-exports

pub use bumpalo;

Modules

ast

Abstract syntax tree representation of hugr modules.

binary

Binary format based on capnproto.

scope

Utilities for working with scoped symbols, variables and links.

table

Table representation of hugr modules.

Structs

LinkName

The name of a link.

SymbolName

The name of a symbol.

VarName

The name of a variable.

Enums

Literal

A static literal value.

RegionKind

The kind of a region.

ScopeClosure

Type to indicate whether scopes are open or closed.

Visibility

Describes how a function or symbol should be acted upon by a linker

Constants

COMPAT_CONST_JSON

Constructor for JSON encoded constants.

COMPAT_META_JSON

Constructor for JSON encoded metadata.

CORE_ADT

Runtime algebraic data types.

CORE_BYTES_TYPE

Type of bytes literals.

CORE_CALL

Operation to call a statically known function.

CORE_CALL_INDIRECT

Operation to call a functiion known at runtime.

CORE_CONST

The type for runtime constants.

CORE_CONSTRAINT

The type of constraints.

CORE_CONST_ADT

Constants for runtime algebraic data types.

CORE_CTRL

Type of control flow regions.

CORE_ENTRYPOINT

Metadata to tag a node or region as the entrypoint of a module.

CORE_FLOAT_TYPE

Type of float literals.

CORE_FN

Core function types.

CORE_LIST_TYPE

The type for lists of static data.

CORE_LOAD_CONST

Operation to load a constant value.

CORE_MAKE_ADT

Operation to create a value of an algebraic data type.

CORE_META

The type of metadata.

CORE_META_DESCRIPTION

Constructor for documentation metadata.

CORE_NAT_TYPE

Type of natural number literals.

CORE_NON_LINEAR

The constraint for non-linear runtime data.

CORE_STATIC

The type of static types.

CORE_STR_TYPE

Type of string literals.

CORE_TITLE

Metadata constructor for symbol titles.

CORE_TUPLE_TYPE

The type for tuples of static data.

CORE_TYPE

The type of runtime types.

ORDER_HINT_INPUT_KEY

Metadata constructor for order hint keys on input nodes.

ORDER_HINT_KEY

Metadata constructor for order hint keys.

ORDER_HINT_ORDER

Metadata constructor for order hints.

ORDER_HINT_OUTPUT_KEY

Metadata constructor for order hint keys on output nodes.