# 003 — HIR

- **Status:** Draft
- **Normative language:** `MUST`, `MUST NOT`, `SHOULD`, `SHOULD NOT`, and `MAY` are to be
  interpreted as described in RFC 2119.

## 1. Purpose

HIR (High-level IR) is the tree-shaped abstract syntax that a frontend builds and libVCT annotates
in place. It is the discovery half of the two-stage IR: HIR establishes node identity, attaches
traits, and performs cheap folds. Lowering consumes annotated HIR and produces VIR (see
[005 — Lowering](005-lowering.md)).

This file specifies the HIR node model, the node kinds, node identity, the builder/emitter contract,
the `defer` statement, and the textual HIR format.

## 2. Scope

In scope: the HIR data model and its observable contract toward frontends, the HIR optimizer, and
lowering. Out of scope: the trait vocabulary itself (see [002 — Traits](002-traits.md)), the
optimizer's pass framework and cascade (see
[004 — HIR Optimizer](004-hir-optimizer.md)), and the HIR-to-VIR mapping (see
[005 — Lowering](005-lowering.md)).

A frontend that embeds libVCT interacts with HIR through the builder API and the trait query API.
The textual HIR format is a tool surface, not a frontend surface.

## 3. Node model

Key properties, all normative:

1. HIR is **tree-shaped**. Every node except the module root has exactly one parent. A node has an
   ordered list of children whose meaning is determined by the node kind.
2. HIR is **arena-owned**. Nodes are allocated from the module's arena and are never individually
   freed. An arena is reclaimed wholesale (see [001 — Architecture](001-architecture.md) and
   [013 — Build & Packaging](013-build-packaging.md)).
3. HIR is **annotated in place**. Every node carries one embedded `Trait` (see
   [002 — Traits](002-traits.md)) that the HIR optimizer mutates as it derives facts. There is no
   separate side table for the common case.
4. HIR is **high-level**. It preserves structured control flow (`if`/`while`/`for`/`switch`/`block`)
   and expressions; it is not SSA and has no phi-nodes.
5. Nodes are mutable during the HIR optimizer's cascade and become read-only to a consumer once
   traits are epoch-valid. A frontend **MUST NOT** mutate a module after finishing it.

Every node exposes at least:

```d
struct HirNode {
    NodeId   id;      // stable identity, unique within the module
    NodeKind kind;
    Span     span;    // optional frontend source span
    Trait    trait;   // attribute + requests + relationships
    NodeId[] children;
}
```

`span` **MAY** be absent. Absence **MUST** degrade diagnostics gracefully and **MUST NOT** affect
optimization correctness.

## 4. Node kinds

The following is the **reference node set** for v1. A frontend **MUST** build modules only from
these kinds. Additional kinds are reserved and require a specification change. A frontend **MAY**
use any subset of the set.

### 4.1 Structural kinds

| Kind | Description | Children / payload |
|---|---|---|
| `Module` | Root of one translation unit. | functions, globals |
| `Function` | A function definition or declaration. | params, body `Block` |
| `Param` | A function parameter. | none |
| `Block` | An ordered statement scope. | statements |

### 4.2 Declaration kinds

| Kind | Description | Children / payload |
|---|---|---|
| `GlobalVar` | A module-level storage object. | optional init expression |
| `LocalVar` | A local binding with optional initializer. | optional init expression |

A declaration **MUST** carry a `ty` attribute. A declaration whose initializer is compile-time
known **MUST** be eligible for `is_comptime`/`const_value` annotation by the optimizer.

### 4.3 Statement kinds

| Kind | Description | Children / payload |
|---|---|---|
| `ExprStmt` | Evaluate an expression for effect. | expression |
| `Return` | Return from the enclosing function. | optional value |
| `If` | Two-way branch. | condition, then-block, optional else-block |
| `While` | Pre-test loop. | condition, body |
| `For` | C-style loop. | optional init, optional condition, optional step, body |
| `Switch` | Multi-way branch. | subject, cases |
| `Case` | One switch arm. | optional value, body |
| `Break` | Exit the innermost loop or switch. | none |
| `Continue` | Continue the innermost loop. | none |
| `Defer` | Scope-exit action; see the `defer` section below. | deferred expression or statement |

### 4.4 Expression kinds

| Kind | Description | Children / payload |
|---|---|---|
| `Literal` | Integer, float, string, boolean, or null constant. | literal payload |
| `NameRef` | Reference to a declared name. | resolved target identity |
| `Unary` | Prefix or postfix unary operator. | operand |
| `Binary` | Binary operator. | left, right |
| `Assign` | Assignment to an lvalue. | target, value |
| `Call` | Function or intrinsic call. | callee, arguments |
| `Member` | Aggregate field access. | base, field index |
| `Index` | Pointer or array element access. | base, index |
| `Cast` | Type conversion. | operand, target type |

Every expression node **MUST** carry a `ty` attribute once HIR has validated it. `Literal` nodes
**MUST** additionally carry `const_value` when their value is representable in the type.

## 5. Node identity

1. Every node **MUST** have a `NodeId` that is unique within its `Module`.
2. Identity **MUST** be assigned deterministically from construction order, so that two runs over
   the same input produce the same identity assignment.
3. Identity **MUST** remain stable across trait annotation and optimizer rewrites of the same node.
4. A deleted node's identity **MUST NOT** be reused for a different node.
5. VIR depends on HIR for **traits and node identity only** (see
   [001 — Architecture](001-architecture.md)). Lowering records the mapping from HIR identity to
   VIR entities (see [005 — Lowering](005-lowering.md)).

Identity is the join key that lets diagnostics, relationships, and the lowering map refer to the
same node across stages.

## 6. The `defer` statement

HIR carries `defer` as a **real high-level statement**. Its observable semantics:

1. A `Defer` node names a body that runs at **every scope exit** of the enclosing `Block`.
2. Scope exits include normal fall-through, `Break`, `Continue`, and `Return`.
3. Deferred bodies within one scope run in **reverse declaration order** (last declared runs first).
4. A backend **MUST NOT** ever observe a `Defer` node. Before VIR is produced, every `Defer` marker
   **MUST** be erased with zero runtime residue. The behavior **MUST** be identical to writing the
   deferred body textually at each exit point.
5. Expansion is performed by the HIR optimizer when HIR optimization is enabled. If HIR
   optimization is disabled (`-O0`, see
   [004 — HIR Optimizer](004-hir-optimizer.md)), **lowering itself MUST expand `defer` at every
   scope exit** (see [005 — Lowering](005-lowering.md)).
6. Expansion **MUST** be deterministic. When a scope has multiple exits, the emitted bodies **MUST**
   appear in a stable, specified order so that output is byte-identical across runs.

Because expansion is always resolved before VIR, `defer` costs nothing at runtime.

## 7. Builder and emitter contract

### 7.1 Frontend-facing builder

The builder is the frontend's only construction surface. It provides operations to create each
node kind, link children, set a node's type and value, and attach frontend-suggested traits
(including `is_static` and optimization hints). Its contract:

1. The builder **MUST** assign node identity per the node identity section above.
2. The builder **MUST** allow a frontend to construct a module without supplying derived
   attributes. Derived facts are HIR's responsibility, not the frontend's.
3. The builder **MUST** accept a frontend-suggested attribute or request, record it with
   `attr_source = suggested`, and defer validation to HIR.
4. `finish(module)` **MUST** validate every suggested trait. Validation follows the rule in
   [002 — Traits](002-traits.md): on a wrong or unprovable suggestion HIR emits a warning (an error
   under `-Werror`), **overwrites** the value with the correct one, and marks it `derived`. A
   correct suggestion is preserved.
5. After `finish`, the builder **MUST** reject further structural mutation of that module by the
   frontend. Optimization mutates in place internally, under epoch guards.

### 7.2 Trait attachment

The frontend attaches a `Trait` to each node. The trait is incomplete at build time: the frontend
supplies `ty`, `is_static`, and `complex` where it knows them, and the HIR optimizer fills in the
rest. A node lacking a derived attribute is not an error at build time; it becomes one only if
lowering finds the trait incomplete (see [005 — Lowering](005-lowering.md)).

HIR **MUST NOT** require a frontend to compute `is_used`, `escapes`, `is_addressed`,
`const_value`, or any other derived attribute.

### 7.3 Textual emitter

The textual emitter is a distinct, non-authoring surface (see the textual HIR format section). It
**MUST** be able to serialize a finished HIR module and to parse that serialization back into an
equivalent module.

## 8. Textual HIR format

HIR has a textual form used **solely for tools and round-trip tests**. It is explicitly **NOT** an
authoring surface: frontends embed the library and build HIR through the builder API. The format is
versioned independently of the library and of the trait vocabulary (see
[013 — Build & Packaging](013-build-packaging.md)).

The format carries, per node: kind, identity, child references, type, and the node's trait (with
each attribute's value and `attr_source`, its requests and strengths, and its relationships). The
reference round-trip property is:

```
print(parse(print(m))) == print(m)
```

A conforming implementation **MUST** satisfy this property for any module it can emit. Parsing
**MUST NOT** be required to accept hand-written input beyond what the emitter produces.

Illustrative fragment (shape only, not a complete grammar):

```
fn @main() -> i32 {
  %v1: i32 = literal 4            ; attr: const_value=4 is_comptime=true (derived)
  %v2: i32 = binary add %v1, 4    ; req: Inline (soft)
  defer %v3
  ret %v2
}
```

## 9. Invariants

- Every non-root node has exactly one parent; the module root has none.
- Every node has a unique `NodeId` within its module, and ids are not reused.
- Every node carries exactly one `Trait`.
- After `finish`, every suggested attribute has been validated and either preserved or overwritten.
- No `Defer` node survives into VIR.
- HIR is not SSA and **MUST NOT** be required to answer SSA questions.
- Frontend-supplied types and values are suggestions, never authoritative facts.

## 10. Example

A frontend builds:

```
fn main() -> int {
    x = 4;
    y = x + 4;
    z = foo(x, y);
    a = sqrt(z);
    println(a);
}
```

It creates `Function`, `LocalVar`, `Binary`, `Call`, and `Return` nodes, sets each node's `ty`,
attaches `is_static` where known, and calls `finish`. HIR then validates the suggestions, derives
`const_value` for `x`, `y`, and the folded `sqrt` result, and issues an `Inline` request for
`foo` (see [004 — HIR Optimizer](004-hir-optimizer.md)). Content that `defer` would add is expanded
at scope exits, so the emitted VIR contains no defer marker. The full walkthrough is normative in
[014 — Worked Example](014-worked-example.md).

## 11. Cross-references

- [000 — Overview](000-overview.md)
- [001 — Architecture](001-architecture.md)
- [002 — Traits](002-traits.md)
- [004 — HIR Optimizer](004-hir-optimizer.md)
- [005 — Lowering](005-lowering.md)
- [011 — Diagnostics](011-diagnostics.md)
- [013 — Build & Packaging](013-build-packaging.md)
- [014 — Worked Example](014-worked-example.md)