Skip to main content

Enums, Tagged Unions & Pattern Lowering

This document specifies the physical memory layouts of scalar enumerations and tagged unions (sum types), discriminant byte-width optimizations, decision tree generation algorithms, and pattern matching lowering in Adesh.


1. Scalar Enums​

Scalar enums define a set of distinct named integral constants — no payload data:

enum Severity {
Low = 0,
Medium = 1,
High = 2,
Critical = 3,
}

enum Direction { North, South, East, West } // auto-numbered 0..N-1

Lowered in src/parsing/ast.rs:EnumDecl { name, variants: Vec<(String, Option<String>)> } where the Option<String> is an optional discriminant expression.

1.1 Memory Representation​

Scalar enums require no heap headers and are stored directly as fixed-width integers. The compiler selects the smallest integer type that fits all discriminants (see §2.2):

Scalar Enum Memory:
Severity::Critical --> i64(3) // default width i64
Direction::North --> i64(0)

With explicit width annotation (where supported):

enum Flags: u8 { None = 0, Read = 1, Write = 2, ReadWrite = 3 }

No discriminant byte is stored separately — the scalar value is the discriminant. This makes scalar enums ABI-compatible with C enums for FFI (extern "C").


2. Tagged Unions (Sum Types / ADTs)​

Enums can attach heterogeneous payload data to individual variants, forming Tagged Unions (algebraic data types):

enum Message {
Quit,
Move { x: i64, y: i64 },
Write(string),
ChangeColor(u8, u8, u8),
}

enum Shape {
Circle { radius: f64 },
Rect { width: f64, height: f64 },
Point,
}

enum Option<T> { Some(T), None, }
enum Result<T, E> { Ok(T), Err(E), }

2.1 Memory Layout & Discriminant Optimization​

A tagged union buffer consists of a Discriminant Tag followed by a Payload Union Buffer:

Tagged Union Memory Layout (8-byte aligned, native backend)
+--------------------------+----------------------------------------------------+
| Discriminant Tag (1B) | Payload Union Buffer (max payload size across all variants) |
+--------------------------+----------------------------------------------------+
| Variant Index (0..N-1) | Max variant payload (e.g., sizeof(Write)=24B string header) |
| | Struct payloads laid out inline per variant |
+--------------------------+----------------------------------------------------+
|<---- Tag Offset 0x00 --->|<---------------- Payload Offset 0x08 ------------------------>|
| padding 7B after 1B tag | aligned to 8B |
+--------------------------+----------------------------------------------------+

Concrete example:

Message::Move { x:10, y:20 } (assume Message has tag 1)
Offset 0x00: [ 01 00 00 00 00 00 00 00 ] // tag=1, 7 padding
Offset 0x08: [ 0A 00 00 00 00 00 00 00 ] // x = 10 (i64)
Offset 0x10: [ 14 00 00 00 00 00 00 00 ] // y = 20 (i64)
// no heap allocation for this payload; string payloads store header inline

Message::Write("hello")
Offset 0x00: [ 02 00 00 00 00 00 00 00 ] // tag=2
Offset 0x08: [ string header 24B: ptr(8) len(8) cap(8) ] // payload

2.2 Discriminant Tag Byte-Width Optimization​

The compiler automatically selects the minimum byte width required to represent all variant tags, minimizing memory:

Discriminant Tag Width:
- 1 Byte (u8) if N_variants <= 256
- 2 Bytes (u16) if 256 < N_variants <= 65,536
- 4 Bytes (u32) if N_variants > 65,536

7/6/4 padding bytes are inserted after a 1/2/4-byte discriminant to align the payload to 8 bytes. For interpreter mode (Value::Enum / Value::EnumCtor), the discriminant is a logical index without physical padding.

For Option<T> where T is a non-nullable pointer type, the backend may apply niche optimization: None is represented as null pointer, Some(ptr) as the pointer itself, with no discriminant byte at all.

2.3 Generic Enums & Monomorphization​

Generic enums (Option<T>, Result<T,E>) are monomorphized per instantiation (§ generics.md). Each instantiation may have different payload sizes and thus different union buffer sizes:

enum Result<T, E> { Ok(T), Err(E) }
let r1: Result<i64, string> = Result::Ok(42); // payload max(8, 24) = 24B
let r2: Result<bool, u8> = Result::Err(255); // payload max(1,1)=1B (+ padding -> 8B)

The compiler generates per-instantiation layouts and mangled symbols (_Adesh_M_main_Result_Ok_i64_string).


3. Pattern Matching Compiler Lowering​

Pattern matching expressions (match) evaluate a selector against structured patterns with exhaustive checking:

let msg = Message::Move { x: 10, y: 20 };

match msg {
Message::Quit => print("Exiting"),
Message::Move { x, y } => print(f"Move to {x}, {y}"),
Message::Write(text) => print(text),
Message::ChangeColor(r, g, b) => print(f"Color: {r},{g},{b}"),
}

3.1 Pattern Forms (EBNF)​

MatchExpr ::= "match" Expr "{" MatchArm { "," MatchArm } [ "," ] "}"
MatchArm ::= Pattern "=>" ( Expr | Block )
Pattern ::= "_" (* wildcard *)
| IDENT (* variable binding: x *)
| Literal (* 42, "hi", true *)
| IDENT "::" IDENT [ "(" Pattern { "," Pattern } ")" ] (* Enum variant *)
| IDENT "{" FieldPat { "," FieldPat } "}" (* struct-like variant *)
| Pattern "|" Pattern (* or pattern *)
| "(" Pattern { "," Pattern } ")" (* tuple pattern *)
| "[" Pattern { "," Pattern } "]" (* array pattern, if supported *)
FieldPat ::= IDENT [ ":" Pattern ]

LetPattern ::= "let" Pattern "=" Expr (* if let / while let / let destructuring *)

In AST: Pattern enum in src/parsing/ast.rs:92-98 (Literal, Variable, Wildcard, Or, EnumVariant), and ExprKind::Match(Box<Expr>, Vec<(Pattern, Expr)>).

3.2 Decision Tree & Jump Table Generation​

For dense variant tags without complex guards, the compiler lowers match into an $O(1)$ native Jump Table (SWITCH_TAG bytecode instruction):

[ Read Discriminant Tag at Offset 0x00 ]
|
+-----------------------+-----------------------+-----------------------+
| (Tag = 0) | (Tag = 1) | (Tag = 2) | (Tag = 3)
v v v v
[ Jump to Quit Block ] [ Extract x, y Payload ] [ Extract String Ptr ] [ Extract r,g,b ]
[ Jump to Move Block ] [ Jump to Write Block ] [ Jump to Color ]

For sparse tags or guarded arms, the compiler emits a Decision Tree with binary search or if-else chains:

[ Read tag ]
if tag == 0 => Quit
else if tag < 2 => Move
else if tag == 2 => Write
else => ChangeColor

Guards (if present) become nested if after tag dispatch:

match msg {
Message::Move { x, y } if x > 0 => print("positive move"),
Message::Move { x, y } => print("any move"),
_ => print("other"),
}

3.3 Exhaustiveness & Reachability Checking​

The type checker verifies that match is exhaustive — every variant has an arm, or a wildcard _ covers the remainder:

enum Color { Red, Green, Blue }
let c = Color::Red;
match c {
Color::Red => print("red"),
Color::Green => print("green"),
// E0300: non-exhaustive match, missing pattern `Color::Blue`
}

Fixes:

match c {
Color::Red => print("red"),
Color::Green => print("green"),
Color::Blue => print("blue"),
}
// or
match c {
Color::Red => print("red"),
_ => print("other"),
}

Reachability: an arm after a wildcard or after all variants are covered is W0301: unreachable pattern. The pass lives in src/parsing/hir_passes.rs / src/semantics/engine.rs.

3.4 Desugaring if let and while let​

if let and while let are syntactic sugar desugared during parsing into single-arm match with a wildcard fallback:

// Source
if let Message::Write(text) = msg {
print(text);
}

Desugared AST:

match msg {
Message::Write(text) => { print(text); },
_ => ()
}

Similarly:

// Source
while let Some(item) = iter.next() {
print(item);
}
// Desugared:
while (true) {
match iter.next() {
Some(item) => { print(item); },
_ => break,
}
}

let destructuring (let (a, b) = pair; / let { x, y } = obj;) uses StmtKind::LetTuple / LetObject in src/parsing/ast.rs and is verified by the same exhaustiveness logic.


4. Option<T> & Result<T, E> — Idiomatic Usage​

4.1 Option<T> for Nullable Values​

fn find_user(id: string): Option<User> {
for u in users { if (u.id == id) { return Option::Some(u); } }
return Option::None;
}

let user = find_user("42");
match user {
Option::Some(u) => print(f"found {u.name}"),
Option::None => print("not found"),
}

// Combinators (via extend on)
let name = find_user("42").map((u) => u.name).unwrap_or("guest");
let email = find_user("42").and_then((u) => u.email); // Option<string>

4.2 Result<T, E> for Fallible Operations​

fn parse_int(s: string): Result<i64, string> {
// ...
if (valid) { return Result::Ok(n); } else { return Result::Err("invalid"); }
}
let res = parse_int("42");
match res {
Result::Ok(n) => print(f"ok {n}"),
Result::Err(e) => print(f"err {e}"),
}
let n = parse_int("42")?; // early return Err on failure (see error-handling.md)

Option and Result are enums like any other — extend on can add methods, match is exhaustive, and they participate in generic monomorphization (§ generics.md).


5. extend on for Enums​

Enums support retroactive method extension via extend on, identical to struct/class extension:

enum Shape {
Circle { radius: f64 },
Rect { width: f64, height: f64 },
}

extend on Shape {
fn area(&self): f64 {
match self {
Shape::Circle { radius } => 3.1415926535 * radius * radius,
Shape::Rect { width, height } => width * height,
}
}
fn is_circle(&self): bool {
match self {
Shape::Circle { .. } => true,
_ => false,
}
}
}
let c = Shape::Circle { radius: 10.0 };
print(c.area());
print(c.is_circle());

Method generics on enums are also supported:

enum Wrapper<T> { Value(T), Empty, }

extend on Wrapper<T> {
fn map<U>(self: Wrapper<T>, f: fn(T): U): Wrapper<U> {
match self {
Wrapper::Value(v) => Wrapper::Value(f(v)),
Wrapper::Empty => Wrapper::Empty,
}
}
}
let w: Wrapper<i64> = Wrapper::Value(42);
let w2 = w.map<string>((n) => f"{n}");

Desugaring: each extend on enum method is a function taking self: &Shape or self: Shape (move/borrow) and dispatched after match tag check. See src/parsing/ast.rs:StmtKind::Extend.


6. Advanced Patterns​

6.1 Or Patterns |​

match severity {
Severity::Low | Severity::Medium => print("low"),
Severity::High | Severity::Critical => print("high"),
}

Lowered as Pattern::Or(Box<Pattern>, Box<Pattern>) — multiple discriminant checks share the same arm body.

6.2 Nested & Tuple Patterns​

enum Tree<T> { Leaf(T), Node { left: Tree<T>, right: Tree<T> }, }

fn sum(tree: Tree<i64>): i64 {
match tree {
Tree::Leaf(n) => n,
Tree::Node { left, right } => sum(left) + sum(right),
}
}

let pair: (Option<i64>, Option<i64>) = (Option::Some(1), Option::None);
match pair {
(Option::Some(a), Option::Some(b)) => print(f"both {a},{b}"),
(Option::Some(a), Option::None) => print(f"only a {a}"),
(Option::None, Option::Some(b)) => print(f"only b {b}"),
(Option::None, Option::None) => print("neither"),
}

6.3 Wildcard & Variable Binding​

match msg {
Message::Move { x, y } => print(f"{x},{y}"), // binds x, y from payload
Message::Write(text) => print(text), // binds text
_ => print("other"), // wildcard, no binding
}

Variable patterns introduce new let bindings in the arm's scope; wildcard _ binds nothing.


7. Compilation Pipeline & Source References​

Source: enum E { A, B(T) } / match x { ... }
|
v
Lexer (src/parsing/lexer.rs: "enum", "match")
|
v
Parser --> EnumDecl { name, variants } (src/parsing/ast.rs:933-937)
--> ExprKind::Match(Box<Expr>, Vec<(Pattern, Expr)>) (src/parsing/ast.rs:564)
--> Pattern::{Literal, Variable, Wildcard, Or, EnumVariant} (src/parsing/ast.rs:92-98)
|
v
HIR Lower (src/parsing/hir_lower.rs) --> HirType::Enum, payload size = max variant size
|
v
Type Check (src/semantics/engine.rs) --> variant existence, exhaustiveness E0300, reachability W0301
|
v
Pattern Lowering (src/parsing/hir_passes.rs) --> jump table vs decision tree
|
v
Codegen (src/backends/*) --> SWITCH_TAG bytecode / native jump table, payload extraction
Interpreter --> Value::Enum / EnumCtor (src/parsing/ast.rs:1003-1005)

8. Common Errors​

CodeMessageFix
E0300non-exhaustive match, missing pattern XAdd missing arm or _ => ...
E0301unknown variant 'X' for enum 'E'Check spelling or import
E0302wrong number of fields for variant 'V': expected 2, found 1Match variant arity
E0303cannot match on non-enum typeEnsure selector is enum
W0301unreachable patternRemove arm after exhaustive coverage
W0302wildcard _ matches everything, subsequent arms unreachableMove wildcard to last arm

9. Extended Examples​

9.1 State Machine with Enums​

enum State { Idle, Running { progress: f64 }, Done { result: string }, Failed { error: string }, }

fn poll_state(s: State): string {
match s {
State::Idle => "idle",
State::Running { progress } => f"running {progress}%",
State::Done { result } => f"done: {result}",
State::Failed { error } => f"failed: {error}",
}
}
let states: [State] = [State::Idle, State::Running { progress: 50.0 }, State::Done { result: "ok" }];
for st in states { print(poll_state(st)); }

9.2 Recursive Enum & Match​

enum List<T> { Nil, Cons { head: T, tail: List<T> }, }

extend on List<T> {
fn len(&self): u64 {
match self {
List::Nil => 0,
List::Cons { head, tail } => 1 + tail.len(),
}
}
fn map<U>(self: List<T>, f: fn(T): U): List<U> {
match self {
List::Nil => List::Nil,
List::Cons { head, tail } => List::Cons { head: f(head), tail: tail.map(f) },
}
}
}
let lst: List<i64> = List::Cons { head: 1, tail: List::Cons { head: 2, tail: List::Nil } };
print(lst.len()); // 2

9.3 Option/Result Composition with Match​

fn get_user_email(id: string): Option<string> {
let user = find_user(id)?; // Option early return (desugars to match None => return None)
return user.email; // Option<string>
}
fn parse_user_id(s: string): Result<string, string> {
let n = parse_int(s).map_err((e) => f"bad id: {e}")?;
if (n < 0) { return Result::Err("negative id"); }
return Result::Ok(f"{n}");
}
match parse_user_id("42") {
Result::Ok(id) => print(get_user_email(id).unwrap_or("no email")),
Result::Err(e) => print(f"error: {e}"),
}

9.4 Or Pattern with Guards​

fn classify(msg: Message): string {
match msg {
Message::Quit | Message::Write("") => "empty/quit",
Message::Move { x, y } if x == 0 && y == 0 => "origin",
Message::Move { x, y } => f"move {x},{y}",
Message::Write(text) => f"write {text}",
Message::ChangeColor(r, g, b) => f"color {r},{g},{b}",
}
}

9.5 Extending Result with Combinators​

extend on Result<T, E> {
fn is_ok(&self): bool {
match self {
Result::Ok(_) => true,
Result::Err(_) => false,
}
}
fn unwrap_or(self: Result<T, E>, default: T): T {
match self {
Result::Ok(v) => v,
Result::Err(_) => default,
}
}
}
let r: Result<i64, string> = Result::Ok(42);
print(r.is_ok()); // true
print(r.unwrap_or(0)); // 42

10. Best Practices​

  1. Prefer match over if let chains when more than two arms — exhaustiveness checking catches missing variants at compile time.
  2. Place wildcard _ last; keep concrete variants before wildcards to avoid W0301.
  3. Use Option<T> and Result<T,E> for nullable/fallible APIs instead of sentinel values or exceptions where errors are expected.
  4. Keep enum variant payloads consistent: prefer named fields (Move { x, y }) over positional (Move(i64,i64)) for readability.
  5. Extend enums with extend on for behavior, but keep core enum definitions minimal and stable — adding variants is a breaking change for exhaustive matches.
  6. For large enums (> 256 variants), be aware discriminant widens to 2/4 bytes — benchmark if cache-sensitive.
  7. Leverage niche optimization: use Option<Share<T>> or Option<&T> where possible to avoid discriminant overhead.