Larva HIR

Larva HIR (high-level intermediate representation) is the model of a program that every language on Larva produces. A frontend reads its own syntax and writes HIR; from there on, everything is Larva's: linking, lowering to the IR, the back ends, reflection, the catalog the editor and larva show use, and the .lva files libraries ship as.

The model lives in the Larva.Hir project: HirAssembly (assemblies, types, members, constants), HirTypes (types and tokens), HirBody (statements, expressions, patterns), HirWalker, Text/HirPrinter, Encoding/ (the binary format) and Linking/HirLinker. It depends on nothing else in Larva.

Why HIR exists

Before HIR, the Antril frontend did almost everything: classes, interfaces, inheritance, closures, async, reflection, boxing, enums, strings and projects, all lowered straight to Larva's low-level IR (structs, gc handles, basic blocks). Libraries were referenced by reparsing the text of their declarations. The design document lists the principles of the rearchitecture that replaced this:

• HIR is the truth of the program. Types, members, generics, attributes and typed bodies, with full metadata. Every frontend, tool and library speaks HIR.
• The frontend does not decide run-time semantics. It resolves names, overloads, types and inference, and emits HIR that is already typed. How a virtual method dispatches, how a closure is built, how an async method becomes a state machine: Larva decides, once, for every language.
• Libraries are referenced by their HIR metadata, never by reparsing declarations. A library's declarations are never rewritten as source text.
• Everything native is extern. The runtime exposes services (memory, GC, threads, files, network, time) as extern functions with stable names; the base library is written in a language on top of them.
• Ahead of time first. No JIT: generics are specialized, reflection is generated from metadata.
• Tools belong to Larva. Build, packages, the language server and the object formats serve any frontend; a language brings only its syntax.

The level of HIR follows from those principles. It is above IR (it still has classes, interfaces, virtual calls, lambdas, try, patterns, generics) so that Larva lowers them with full context, and it is below source (names are resolved, every expression knows its type, overloads are chosen, operators of user types are calls of their methods) so that Larva never has to understand a language.

The model at a glance

HirAssembly ── Name, Version, EntryPoint (MemberToken?)
 ├─ References : AssemblyRef(Name, Version[])           other assemblies it uses
 ├─ TypeRefs   : TypeRef(Assembly, Namespace, Name, Arity)      their types, by name
 ├─ MemberRefs : MemberRef(Kind, Parent, Name, GenericArity, Parameters, Result)
 ├─ Types      : TypeDef ──┬─ Namespace, Name, Kind, Flags, Access, DeclaringType
 │                         ├─ Generics : GenericParam (constraints)
 │                         ├─ Base, Interfaces, Underlying
 │                         ├─ Fields     : FieldDef(Name, Type, Flags, Access, Value?)
 │                         ├─ Methods    : MethodDef(Name, Kind, Flags, Parameters, Result, Body?)
 │                         ├─ Properties : PropertyDef(Getter, Setter = method indices)
 │                         ├─ Events     : EventDef(Adder, Remover)
 │                         ├─ Operators  : OperatorDef(Symbol, Fixity, Precedence, Method)
 │                         └─ Attributes, Location, Doc
 ├─ Attributes : HirAttribute(Constructor, Arguments, Named)
 ├─ Resources  : HirResource(Name, Data)                linked into the program
 ├─ LanguageData : HirResource(Name, Data)              kept for the language, never linked
 └─ Files      : source paths that SourceLocation.File indexes

Tokens: how HIR names things

Inside an assembly, types and members are named by small integer tokens, not by strings:

A reference names its target the way a person would: a TypeRef by assembly, namespace, name and generic arity; a MemberRef by its kind, parent type, name, generic arity, parameter types and result type (the signature tells overloads apart). HirAssembly.Reference creates each reference once and reuses it. When assemblies are loaded together, references are resolved by those names; the HIR linker turns them into definitions.

Types

HirType is a small closed hierarchy, compared structurally (two NamedTypes with the same token and arguments are equal):

str and any are not primitives: they are classes of the core library (System.String<u8> and System.Any), named like any other type. Lowering finds the ones it needs by their full names. HirTypes.Substitute replaces type parameters with arguments; IsGeneric says whether a type mentions one.

Type definitions

A namespace has no entity of its own: it is a prefix of type names. The free functions and fields of a namespace live in a class named $Module (a program's Main is App.$Module.Main).

Members

MethodKind is Normal, Constructor (named .new), StaticConstructor, Finalizer, Getter, Setter, Adder, Remover, Operator or Conversion. Accessors are ordinary methods of the type; a property only points at them. Operator definitions travel in the metadata so that a frontend can parse code that uses another library's own operators.

Parameter has a name, a type, flags (Params: the last parameter takes any number of arguments as an array; Optional) and a Default constant.

Generics and constraints

Types and methods carry a list of GenericParam. A parameter states everything an argument must satisfy, so that lowering can specialize generic code without asking the frontend:

Attributes, resources and language data

• Attributes (HirAttribute) are a constructor token, positional constant arguments and named ones. They can sit on the assembly, types, fields, methods, parameters, properties and events.
• Constants (HirConstant) appear as field values, parameter defaults, attribute arguments, literals and patterns: integers of any width (BigInteger plus the primitive), floats as their IEEE bits, bool, char, strings, null, types, enum members (with their text for an enum based on str) and arrays.
• Resources (HirResource: name and bytes) are files the program carries. The linker concatenates them into the program, and a body reads one by name with ResourceExpr (Antril's $resource("name")).
• Language data is also name and bytes, but it is the language's own: what it keeps next to a library for its own compiler, read back when a program references the library and never linked into a program. Antril stores there, as antril.template:<file>, the text of each variadic template (such as its tuple types), which a program expands for the sizes it uses.
• Debug information: Files lists source paths and SourceLocation(File, Line, Column) places types, members and statements. Documentation comments are kept in Doc.

Bodies

A method body (HirBody) is its locals and a block. It is a structured, fully typed tree, at the level of a bound syntax tree, not of a stack machine: it keeps loops, try, switch and patterns so that Larva lowers them with all the context. Every expression carries its type, and every call points at the exact member already chosen.

Parameters are not locals: ParamExpr(i) reads parameter i. A lambda's parameters and the locals it declares are locals of the enclosing body; the lambda (LambdaExpr) lists them, and lowering finds what it captures.

Patterns: DiscardPattern, ConstantPattern, RelationalPattern, RangePattern, TypePattern, BindingPattern, AndPattern, OrPattern, NotPattern, PropertyPattern, PositionalPattern (through a deconstructor), ListPattern (with a slice).

What stays in the frontend: pure syntax. Sections such as public:, into namespace, counting loops, reactive and effect are expanded by the frontend into ordinary HIR or library calls. For example, Antril writes loop (Point p in points) over an array as a ForStmt over an index, as the printed body below shows.

Method bodies are decoded lazily: MethodDef.Body reads the body from the file the first time it is asked for (BodyPending says whether it still has to). Referencing a large library costs only its metadata.

The text form

HirPrinter (Larva.Hir/Text/HirPrinter) writes an assembly as text, for people and for tests. With types: true every expression also shows its type (x:i32), so two assemblies print the same exactly when they are the same. HirAssembly.ToString() returns this text; there is no larva command for the full form yet (see larva show --lang hir for the declarations).

Take this library:

into namespace Tiny
{
	public class Calc
	{
		public:
			static Twice(i32 n) : i32 => n * 2;
	}
}

Compiled with larva lib -o Tiny.lva Tiny.ant, its HIR prints as follows (211 typeref lines cut: the Antril frontend references every type of System.Core it may need by name, and the .lva keeps those references):

assembly Tiny v1.0
reference System.Core
typeref TR0 = [System.Core]System.Type`0
typeref TR1 = [System.Core]System.String`1
typeref TR2 = [System.Core]System.Any`0
…
file 0 "docs-larva-hir/Tiny.ant"

public class Tiny.Calc : [System.Core]System.Any @0:3:15
{
    #0 public static Twice(i32 n) : i32 @0:6:11
    {
        return (%0 * 2i32) @0:6:33
    }
}

With types on every expression, the body line is return (%0:i32 * 2i32:i32):i32 @0:6:33. The file name is the folder and the file, not the full path: a library names its files that way because it leaves the machine it was built on.

A larger example, with a struct, a constructor, a call into System.Core and a loop:

import System;

into namespace Geometry
{
	/// A point on a plane.
	public value Point
	{
		public:
			f64 X;
			f64 Y;

			new(f64 x, f64 y)
			{
				X = x;
				Y = y;
			}

			/// How far the point is from the origin.
			Length() : f64 => Math.Sqrt(X * X + Y * Y);
	}

	public class Shapes
	{
		public:
			static Farthest(Point[] points) : Point
			{
				Point best = points[0];
				loop (Point p in points)
				{
					if (p.Length() > best.Length())
						best = p;
				}
				return best;
			}
	}
}

assembly Geometry v1.0
reference System.Core
…
memberref MR0 = method [System.Core]System.Math::Sqrt`1(!!0) : !!0
file 0 "docs-larva-hir/Geometry.ant"

public struct Geometry.Point @0:6:15
{
    field public f64 X
    field public f64 Y
    #0 constructor public .new(f64 x, f64 y) : void @0:12:4
    {
        (this.Geometry.Point::X = %0) @0:14:5
        (this.Geometry.Point::Y = %1) @0:15:5
    }
    #1 public Length() : f64 @0:19:4
    {
        return [System.Core]System.Math::Sqrt~0<f64>(((this.Geometry.Point::X * this.Geometry.Point::X) + (this.Geometry.Point::Y * this.Geometry.Point::Y))) @0:19:22
    }
}

public class Geometry.Shapes : [System.Core]System.Any @0:22:15
{
    #0 public static Farthest(Geometry.Point[] points) : Geometry.Point @0:25:11
    {
        local $0 mut Geometry.Point best
        local $1 mut Geometry.Point[] $items1
        local $2 mut i32 $index2
        local $3 mut Geometry.Point p
        let $0 = %0[0i32] @0:27:5
        for @0:28:5
            let $1 = %0
            let $2 = 0i32
        cond ($2 < len $1); step ($2++)
        {
            let $3 = $1[$2]
            { @0:29:5
                if ($3.Geometry.Point::Length#1() > $0.Geometry.Point::Length#1()) @0:30:6
                    ($0 = $3) @0:31:7
            }
        }
        return $0 @0:33:5
    }
}

Things to notice:

• Math.Sqrt is generic (Sqrt<T>(T) : T), so the call names the reference MR0 with the type argument <f64>: the frontend inferred it, lowering will specialize it.
• p.Length() is resolved to method #1 of Point (Length#1); overloads share a name, so the printer adds the index.
• The loop became a for over a hidden array local and index ($items1, $index2): that is the frontend's sugar, expanded before HIR.
• A value type's constructor is a constructor method named .new whose this is the value being built.

Notation

A third example shows an enum, a property, a generic class with a constraint and a function value. Note how Antril's T : number became an interface constraint INumber<!0>, and how the enum got a synthesized ToString:

public enum Store.Color : i32 @0:5:14
{
    field public static const Store.Color Red = Store.Color(0)
    field public static const Store.Color Green = Store.Color(1)
    field public static const Store.Color Blue = Store.Color(2)
    #0 public ToString() : [System.Core]System.String<u8> @0:5:14
    {
        local $0 mut Store.Color $enum0
        return this switch { Store.Color(0) => "Red"; Store.Color(1) => "Green"; Store.Color(2) => "Blue"; $0 => enum<i32>($0).[System.Core]System.Int32::ToString~0() }
    }
}

public class Store.Counter<T : [System.Core]System.INumber<!0>> : [System.Core]System.Any @0:7:15
{
    field private !0 total
    property public !0 Total get #1 set #-1
    #0 constructor public .new() : void @0:13:4
    {
        (this.Store.Counter::total = [System.Core]System.INumber::get_Zero~1<!0>()) @0:15:5
    }
    #1 getter public get_Total() : !0 @0:18:14
    {
        return this.Store.Counter::total @0:18:21
    }
    …
}

larva show --lang hir

larva show --lang hir prints a type through the HIR view of the catalog: declarations only, with every type fully qualified, in any language's library:

$ larva show --lang hir Geometry.Point Geometry.ant
// A point on a plane.
public struct Geometry.Point
{
    field X: f64
    field Y: f64
    constructor Point(x: f64, y: f64)
    // How far the point is from the origin.
    method Length() -> f64
}

This view is described in The catalog and language views.

HirWalker

HirWalker visits every statement, expression and pattern of a body, a parent before its children. A subclass overrides Visit(Stmt?), Visit(Expr?) or Visit(Pattern?), looks at the node, and calls the base method to go on into the children (or does not, to stop there). Lambda bodies are visited as part of the expression that holds them.

Larva's own passes use it where they need facts about whole bodies before lowering:

Frontends use it too: the Antril binder walks bodies to find uses of in-place arrays (InPlaceUses).

Linking HIR assemblies

A program is compiled against libraries (System.Core, a project's .dll dependencies, bindings) that are separate HIR assemblies. Before lowering, HirLinker.Link(name, inputs) (Larva.Hir/Linking/HirLinker) merges them into one assembly with no references left, so lowering sees the whole program. larva build links [System.Core, external domains…, libraries…, program]:

$ larva build --timings --backend x64 -o app.exe App.ant Tiny.dll
app.exe (x64 back end, entry app::App.$Module.Main)
timings: System.Core (compiled library) 45 ms, Tiny.dll 4 ms, frontend 1146 ms, HIR link 55 ms, lowering 640 ms, IR checks 366 ms, IR link 118 ms, native (x64) 1410 ms; total 3805 ms

How it works:

inputs (.lva bytes, any order)
   │  pass 1: read each one's metadata ("its own view": references unresolved)
   ▼
order: each assembly after those it references (depth-first; a cycle is an error)
   │  number every type: offset[a] = types of the assemblies before it
   │  byName[(assembly, namespace, name, arity)] = merged index
   ▼
   │  pass 2, per assembly in order:
   │    MapType:   T5  -> T(offset + 5)        TR2 -> byName[[System.Core]System.Any]
   │    MapMember: T3.1 -> T(offset + 3).1     MR0 -> the definition with that name and signature
   │    re-read the .lva with that TokenMap (LvaReader), file indices moved too
   ▼
merged HirAssembly: Types, Files, Attributes, Resources concatenated; EntryPoint = the last input's
                    Origins: which input each run of types came from

Details that matter:

• Order. The assemblies are sorted so each comes after the ones it references. An assembly that references one not given ("App references Lib, which is not linked"), or that reaches itself through others, is an error.
• Type references resolve by (assembly, namespace, name, arity). A missing one is "Ns.Name is not in Lib".
• Member references resolve by name and signature, after mapping the signature's types: a method must match name, generic arity, parameter types and result exactly; a field, property or event matches by name. A miss is "Type has no method Name with that signature". All member references are resolved up front, because bodies are read later, on several threads, and only look them up.
• Bodies stay unread. The merged assembly's methods still point into each input's bytes; a body is decoded, already mapped, when lowering first asks for it.
• Duplicates. Two types with the same identity in one assembly fail ("is defined twice"); two inputs with the same assembly name fail before anything else:

$ larva build --check -o Tiny.exe App.ant Tiny.dll
larva: two assemblies are named `Tiny` (a program and a library it uses, say): rename one (a project's PROJ name, or a library's assembly)

• What is merged. Types, files, assembly attributes and resources. LanguageData is not: it belongs to the language's compiler, not to the program.
• Origins records, in memory only, which input each run of types came from (HirAssembly.OriginOf). Lowering uses it to tell which types come from an assembly built for a GC domain of its own: those are lowered as declarations that the IR linker binds to that library's object (assembly::name), not as definitions.

HIR linking is the first of two linkers. After lowering, the IR linker joins IR objects (for example a library built for another GC); see IR objects and linking.