hyperlight_component_util/
etypes.rs

1/*
2Copyright 2025 The Hyperlight Authors.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8    http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15 */
16
17/// Elaborated component model types
18///
19/// This has the basic type definitions for the elaborated types. They
20/// correspond roughly to the "Elaborated Types" section in the
21/// specification.
22use crate::structure::*;
23
24#[derive(Debug, Clone, PartialEq, Copy)]
25pub struct Name<'a> {
26    pub name: &'a str,
27}
28
29#[derive(Debug, Clone, PartialEq, Copy)]
30pub enum IntWidth {
31    I8,
32    I16,
33    I32,
34    I64,
35}
36impl IntWidth {
37    pub fn width(self) -> u8 {
38        match self {
39            IntWidth::I8 => 8,
40            IntWidth::I16 => 16,
41            IntWidth::I32 => 32,
42            IntWidth::I64 => 64,
43        }
44    }
45}
46
47#[derive(Debug, Clone, PartialEq, Copy)]
48pub enum FloatWidth {
49    F32,
50    F64,
51}
52impl FloatWidth {
53    pub fn width(self) -> u8 {
54        match self {
55            FloatWidth::F32 => 32,
56            FloatWidth::F64 => 64,
57        }
58    }
59}
60
61/// recordfield_e in the specification
62#[derive(Debug, Clone)]
63pub struct RecordField<'a> {
64    pub name: Name<'a>,
65    pub ty: Value<'a>,
66}
67
68/// variantcase_e in the specification
69#[derive(Debug, Clone)]
70pub struct VariantCase<'a> {
71    pub name: Name<'a>,
72    pub ty: Option<Value<'a>>,
73    pub refines: Option<u32>,
74}
75
76/// valtype_e in the specification
77#[derive(Debug, Clone)]
78pub enum Value<'a> {
79    Bool,
80    S(IntWidth),
81    U(IntWidth),
82    F(FloatWidth),
83    Char,
84    String,
85    List(Box<Value<'a>>),
86    FixList(Box<Value<'a>>, u32),
87    Record(Vec<RecordField<'a>>),
88    Tuple(Vec<Value<'a>>),
89    Flags(Vec<Name<'a>>),
90    Variant(Vec<VariantCase<'a>>),
91    Enum(Vec<Name<'a>>),
92    Option(Box<Value<'a>>),
93    Result(Box<Option<Value<'a>>>, Box<Option<Value<'a>>>),
94    Own(Handleable),
95    Borrow(Handleable),
96    /// This records that a type variable was once here, and is used
97    /// to enforce export namedness checks.
98    Var(Option<Tyvar>, Box<Value<'a>>),
99}
100
101/// Global resource identifier
102#[derive(Debug, Clone, Copy, PartialEq)]
103pub struct ResourceId {
104    pub(super) id: u32,
105}
106
107/// To make certain substitutions easier, free type variables are
108/// divided into Universal and Existential variables.  Each is
109/// represented by a pair of indices: the first index is an index into
110/// [`Ctx::parents()`], specifying parent context has the variable
111/// definition in it, and the second is an index into that context's
112/// [`Ctx::uvars`] or [`Ctx::evars`].
113#[derive(Debug, Clone)]
114pub enum FreeTyvar {
115    U(u32, u32),
116    E(u32, u32),
117}
118
119/// We explicitly distinguish between bound type variables, which are
120/// can only only present on types that are themselves inside a
121/// [`QualifiedInstance`] or [`Component`], and free type variables
122/// that are used while constructing or deconstructing such a type in
123/// a [`Ctx`].
124#[derive(Debug, Clone)]
125pub enum Tyvar {
126    /// A bound type variable as a de Bruijn index (0 is the innermost
127    /// binder)
128    Bound(u32),
129    /// A free type variable, whose bounds/other information are
130    /// stored in the context
131    Free(FreeTyvar),
132}
133
134#[derive(Debug, Clone)]
135pub struct Param<'a> {
136    pub name: Name<'a>,
137    pub ty: Value<'a>,
138}
139
140pub type Result<'a> = Option<Value<'a>>;
141
142/// functype_e in the specification
143#[derive(Debug, Clone)]
144pub struct Func<'a> {
145    pub params: Vec<Param<'a>>,
146    pub result: Result<'a>,
147}
148
149/// In the spec, this does not exist, but a validation rule ensures an
150/// invariant that certain deftype_e s are of this form.
151#[derive(Debug, Clone)]
152pub enum Handleable {
153    Var(Tyvar),
154    Resource(ResourceId),
155}
156
157/// deftype_e in the specification
158#[derive(Debug, Clone)]
159pub enum Defined<'a> {
160    Handleable(Handleable),
161    Value(Value<'a>),
162    Func(Func<'a>),
163    Instance(QualifiedInstance<'a>),
164    Component(Component<'a>),
165}
166
167/// typebound_e in the specification
168#[derive(Debug, Clone)]
169pub enum TypeBound<'a> {
170    Eq(Defined<'a>),
171    SubResource,
172}
173
174/// The name of an import or export of the current
175/// component/context. Not in the spec; only used for
176/// [`BoundedTyvar::origin`] below.
177///
178/// Any string present in one of these should also be present in an
179/// [`ExternDecl::kebab_name`] in a relevant place.
180#[derive(Debug, Clone, PartialEq)]
181pub enum ImportExport<'a> {
182    Import(&'a str),
183    Export(&'a str),
184}
185impl<'a> ImportExport<'a> {
186    pub fn name(&self) -> &'a str {
187        match self {
188            ImportExport::Import(s) => s,
189            ImportExport::Export(s) => s,
190        }
191    }
192    pub fn imported(&self) -> bool {
193        match self {
194            ImportExport::Import(_) => true,
195            ImportExport::Export(_) => false,
196        }
197    }
198}
199
200/// An (optional) path through the imports/exports of a current
201/// component/context. Not in the spec; only used for
202/// [`BoundedTyvar::origin`] below.
203#[derive(Default, Debug, Clone, PartialEq)]
204pub struct TyvarOrigin<'a> {
205    /// Note that the most recent (closest) element is last
206    pub path: Option<Vec<ImportExport<'a>>>,
207}
208
209impl<'a> TyvarOrigin<'a> {
210    pub fn new() -> Self {
211        TyvarOrigin { path: Some(vec![]) }
212    }
213    pub fn push(&self, x: Option<ImportExport<'a>>) -> Self {
214        match (&self.path, x) {
215            (None, _) => TyvarOrigin { path: None },
216            (_, None) => self.clone(),
217            (Some(xs), Some(x)) => {
218                let mut xs = xs.clone();
219                xs.push(x);
220                TyvarOrigin { path: Some(xs) }
221            }
222        }
223    }
224    pub fn matches<I: Iterator<Item = &'a ImportExport<'a>>>(&self, path: I) -> bool {
225        self.path
226            .as_ref()
227            .map(|p| p.iter().rev().eq(path))
228            .unwrap_or(false)
229    }
230    pub fn is_local<
231        I: DoubleEndedIterator<Item = &'a ImportExport<'a>>
232            + ExactSizeIterator<Item = &'a ImportExport<'a>>,
233    >(
234        &self,
235        path: I,
236    ) -> Option<Vec<ImportExport<'a>>> {
237        let other = path.rev().skip(1).rev();
238        let path = self.path.as_ref()?;
239        let path = path.iter();
240        let mut path = path.rev();
241        for elem in other {
242            match path.next() {
243                None => break,
244                Some(oe) if oe != elem => return None,
245                _ => (),
246            }
247        }
248        Some(path.cloned().collect())
249    }
250    pub fn last_name(&self) -> Option<&'a str> {
251        self.path
252            .as_ref()
253            .and_then(|x| x.first())
254            .map(|ie| ie.name())
255    }
256    pub fn is_imported(&self) -> bool {
257        let Some(p) = &self.path else {
258            return false;
259        };
260        p[p.len() - 1].imported()
261    }
262}
263
264/// boundedtyvar_e in the spec
265///
266/// Because we use a de Bruijn representation of type indices, this is
267/// only the type_bound - which variable it is binding is implicit in
268/// its position in the list.
269#[derive(Debug, Clone)]
270pub struct BoundedTyvar<'a> {
271    /// This is not important for typechecking, but is used to keep
272    /// track of where a type variable originated from in order to
273    /// decide on a canonical name to be used in bindings
274    /// generation.
275    pub origin: TyvarOrigin<'a>,
276    pub bound: TypeBound<'a>,
277}
278
279impl<'a> BoundedTyvar<'a> {
280    pub fn new(bound: TypeBound<'a>) -> Self {
281        BoundedTyvar {
282            origin: TyvarOrigin::new(),
283            bound,
284        }
285    }
286    pub fn push_origin(&self, x: Option<ImportExport<'a>>) -> Self {
287        BoundedTyvar {
288            origin: self.origin.push(x),
289            ..self.clone()
290        }
291    }
292}
293
294/// externdesc_e in the specification
295#[derive(Debug, Clone)]
296pub enum ExternDesc<'a> {
297    CoreModule(CoreModule<'a>),
298    Func(Func<'a>),
299    /* TODO: First-class values (when the spec gets them) */
300    Type(Defined<'a>),
301    /// This uses an [`Instance`] rather than a [`QualifiedInstance`]
302    /// because the instance's evars need to be propagated up to the
303    /// surrounding component/instance (so that e.g. `alias`ing them
304    /// and using them in another import/export is possible).
305    Instance(Instance<'a>),
306    Component(Component<'a>),
307}
308
309/// Merely a convenience for [`Ctx::resolve_alias`]
310#[derive(Debug, Clone)]
311pub enum CoreOrComponentExternDesc<'a> {
312    Core(CoreExternDesc),
313    Component(ExternDesc<'a>),
314}
315
316/// externdecl_e in the specification
317#[derive(Debug, Clone)]
318pub struct ExternDecl<'a> {
319    pub kebab_name: &'a str,
320    pub desc: ExternDesc<'a>,
321}
322
323/// `instancetype_e` in the specification.
324///
325/// An "opened" instance, whose existential variables are recorded in
326/// some surrounding context.
327#[derive(Debug, Clone)]
328pub struct Instance<'a> {
329    pub exports: Vec<ExternDecl<'a>>,
330}
331
332/// This is an instance together with its existential variables. This
333/// concept doesn't exist as a named syntax class in the specification, but
334/// is the payload of the instance case of `deftype_e` and the output
335/// of the instance declaration inference judgement.
336#[derive(Debug, Clone)]
337pub struct QualifiedInstance<'a> {
338    /// Existential variables produced by this instance (which may be
339    /// referred to by [`exports`](Instance::exports)). These are stored in
340    /// "outside-in" order that matches how they would be written on
341    /// paper: de Bruijn index Bound(0) in the imports is the last
342    /// element in the list, and later elements can depend on earlier
343    /// ones.
344    pub evars: Vec<BoundedTyvar<'a>>,
345    pub unqualified: Instance<'a>,
346}
347
348/// componenttype_e in the specification
349#[derive(Debug, Clone)]
350pub struct Component<'a> {
351    /// Universal variables over which this component is parameterized
352    /// (which may be referred to by `imports`). These are stored in
353    /// "outside-in" order that matches how they would be written on
354    /// paper: de Bruijn index Bound(0) in the imports is the last
355    /// element in the list, and later elements can depend on earlier
356    /// ones.
357    pub uvars: Vec<BoundedTyvar<'a>>,
358    pub imports: Vec<ExternDecl<'a>>,
359    /// Since we already have [`QualifiedInstance`], we use that to
360    /// keep track of both the evars and the actual instance, unlike
361    /// in the spec; this is quite natural, since during inference the
362    /// evars are generated by the exports. However, they conceptually
363    /// belong here as much as there: instantiating a component should
364    /// add them to the context as non-imported uvars and produce an
365    /// [`Instance`], rather than a [`QualifiedInstance`] directly.
366    pub instance: QualifiedInstance<'a>,
367}
368
369// core:importdecl in the specification is wasmparser::Import
370
371/// core:importdesc in the specification
372#[derive(Debug, Clone)]
373pub enum CoreExternDesc {
374    Func(wasmparser::FuncType),
375    Table(wasmparser::TableType),
376    Memory(wasmparser::MemoryType),
377    Global(wasmparser::GlobalType),
378}
379
380/// core:exportdecl in the specification
381#[derive(Debug, Clone)]
382pub struct CoreExportDecl<'a> {
383    pub name: Name<'a>,
384    pub desc: CoreExternDesc,
385}
386
387// core:functype is wasmparser::FuncType
388
389/// core:instancetype_e in the specification
390#[derive(Debug, Clone)]
391pub struct CoreInstance<'a> {
392    pub exports: Vec<CoreExportDecl<'a>>,
393}
394
395/// core:moduletype_e in the specification
396#[derive(Debug, Clone)]
397pub struct CoreModule<'a> {
398    pub _imports: Vec<wasmparser::Import<'a>>,
399    pub _exports: Vec<CoreExportDecl<'a>>,
400}
401
402/// core:deftype_e in the specification
403#[derive(Debug, Clone)]
404pub enum CoreDefined<'a> {
405    Func(wasmparser::FuncType),
406    Module(CoreModule<'a>),
407}
408
409/// gamma_c in the specification
410#[derive(Default, Debug, Clone)]
411pub struct CoreCtx<'a> {
412    pub types: Vec<CoreDefined<'a>>,
413    pub funcs: Vec<wasmparser::FuncType>,
414    pub modules: Vec<CoreModule<'a>>,
415    pub instances: Vec<CoreInstance<'a>>,
416    pub tables: Vec<wasmparser::TableType>,
417    pub mems: Vec<wasmparser::MemoryType>,
418    pub globals: Vec<wasmparser::GlobalType>,
419}
420
421impl<'a> CoreCtx<'a> {
422    pub fn new() -> Self {
423        CoreCtx {
424            types: Vec::new(),
425            funcs: Vec::new(),
426            modules: Vec::new(),
427            instances: Vec::new(),
428            tables: Vec::new(),
429            mems: Vec::new(),
430            globals: Vec::new(),
431        }
432    }
433}
434
435/// resourcetype_e in the specification
436#[derive(Debug, Clone)]
437pub struct Resource {
438    // One day, there will be a `rep` field here...
439    pub _dtor: Option<FuncIdx>,
440}
441
442/// gamma in the specification
443#[derive(Debug, Clone)]
444pub struct Ctx<'p, 'a> {
445    pub parent: Option<&'p Ctx<'p, 'a>>,
446    pub outer_boundary: bool,
447    pub core: CoreCtx<'a>,
448    /// Universally-quantified variables, specifying for each the
449    /// known bound and whether or not it was imported. Uvars can come
450    /// from imports or component instantiations; only the imported
451    /// ones can be allowed to escape in the type of a components
452    /// exports/imports, since only those can be named outside of the
453    /// component itself.
454    pub uvars: Vec<(BoundedTyvar<'a>, bool)>,
455    /// Existentially-quantified variables, specifying for each the
456    /// known bound and, if it was locally defined, the type which
457    /// instantiates it.
458    pub evars: Vec<(BoundedTyvar<'a>, Option<Defined<'a>>)>,
459    pub rtypes: Vec<Resource>,
460    pub types: Vec<Defined<'a>>,
461    pub components: Vec<Component<'a>>,
462    pub instances: Vec<Instance<'a>>,
463    pub funcs: Vec<Func<'a>>,
464}
465
466impl<'p, 'a> Ctx<'p, 'a> {
467    pub fn new<'c>(parent: Option<&'p Ctx<'c, 'a>>, outer_boundary: bool) -> Self {
468        Ctx {
469            parent,
470            outer_boundary,
471            core: CoreCtx::new(),
472            uvars: Vec::new(),
473            evars: Vec::new(),
474            rtypes: Vec::new(),
475            types: Vec::new(),
476            components: Vec::new(),
477            instances: Vec::new(),
478            funcs: Vec::new(),
479        }
480    }
481}
482
483pub struct CtxParentIterator<'i, 'p: 'i, 'a: 'i> {
484    ctx: Option<&'i Ctx<'p, 'a>>,
485}
486impl<'i, 'p, 'a> Iterator for CtxParentIterator<'i, 'p, 'a> {
487    type Item = &'i Ctx<'p, 'a>;
488    fn next(&mut self) -> Option<Self::Item> {
489        match self.ctx {
490            Some(ctx) => {
491                self.ctx = ctx.parent;
492                Some(ctx)
493            }
494            None => None,
495        }
496    }
497}
498
499impl<'p, 'a> Ctx<'p, 'a> {
500    pub fn parents<'i>(&'i self) -> CtxParentIterator<'i, 'p, 'a> {
501        CtxParentIterator { ctx: Some(self) }
502    }
503}
hyperlight_component_util/etypes.rs

hyperlight_component_util/
etypes.rs
