Something went wrong. Try again.
A small configuration language for Zig: ZON with let, if and templates over a context, evaluated to a struct, always finishing.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Evaluating a parsed program to a `Value`.//!//! A tree walk, and nothing more is needed: there is no loop to run and no//! function to call back into, so every node is visited at most once per//! evaluation and the whole thing finishes in time proportional to the//! program. What `Limits` bounds is the size of what it builds -- `++` on a//! `let` that was itself built with `++` doubles each time -- not how long it//! runs.//!//! Every `let` is evaluated, in order, before the program's result. One that//! fails does not fail the program unless something uses it: the failure is//! kept, and reported where the name is read. So `let cert = ctx.cert.?;` is//! harmless in a program that only reads `cert` when `ctx.cert != null`.//!//! When the host asks, it also learns which of the context's fields the//! program read. Each `let` and each included file keeps what it read, and//! hands that on only where its name is used, so a `let` nothing uses -- or//! one that failed and was never used -- read nothing. Reading `ctx` other//! than as `ctx.name`, or calling a host function that asks for it, reads//! all of it.
const std = @import("std");const Allocator = std.mem.Allocator;
const ast = @import("ast.zig");const Node = ast.Node;const Diagnostic = @import("Diagnostic.zig");const Parser = @import("Parser.zig");const builtins = @import("builtins.zig");const value = @import("value.zig");const Value = value.Value;const Host = value.Host;
pub const Error = error{ OutOfMemory, /// The program did something its values do not allow -- added a string /// to a bool, read a field that is not there, unwrapped a null -- or its /// result does not fit the type it is decoded into. The diagnostic says /// what, and where. Eval, /// The program built something larger than `Limits` allows. LimitExceeded,};
/// How much a program may build. A program cannot run for long -- it has no/// loops -- but it can describe something huge in a few lines, by/// concatenating a value with itself over and over.pub const Limits = struct { /// How deeply expressions may nest, which bounds how deep the parser and /// the evaluator recurse. max_depth: u32 = 64, /// The longest any one string may be, in bytes. max_string: usize = 1 << 20, /// The most items any one list may have. max_list: usize = 1 << 16, /// How many values comparison and decoding may visit in all. A list that /// holds the same list twice, a few levels deep, is small to build and /// large to walk. max_steps: usize = 1 << 22, /// How many different files a program may `@include`, counting each /// file once however often it is included. max_includes: u32 = 256,};
/// A function a host provides, called from a program as `@name(args...)`.////// Built-ins take precedence: a host function with a built-in's name cannot/// be called.pub const Function = struct { name: []const u8, min_args: u8 = 0, max_args: u8 = std.math.maxInt(u8), /// What the host wants handed back to it, as `Call.context`. context: ?*anyopaque = null, call: *const fn (call: *Call, args: []const Value) Error!Value,};
/// One call of a host function.pub const Call = struct { /// For anything the result needs allocated. It lives as long as the /// evaluation, and the result is copied out before that ends. arena: Allocator, /// `Function.context`. context: ?*anyopaque, evaluator: *Evaluator, pos: u32,
/// The context the program was evaluated with, if there was one. A host /// that asks which fields were read is told that this read all of them. pub fn ctx(self: *Call) ?Value { self.evaluator.readAll(); return self.evaluator.ctx; }
/// Fail the call with a message, at the place the program called it. pub fn fail(self: *Call, comptime fmt: []const u8, args: anytype) error{Eval} { return self.evaluator.fail(self.pos, fmt, args); }};
const Slot = union(enum) { unset, value: Value, /// A `let` whose expression failed, kept to be reported if it is used. failed: struct { err: Error, diag: Diagnostic },};
pub const Evaluator = struct { arena: Allocator, sources: []const Diagnostic.Source, tree: Parser.Tree, ctx: ?Value, functions: []const Function, limits: Limits, diag: *Diagnostic, slots: []Slot = &.{}, /// What is left of `limits.max_steps`. steps: usize, /// Set by the context's accessors to whatever they could not read. why: []const u8 = "", /// The names of the context's fields, when the host wants to know which /// of them were read; null when it does not. ctx_fields: ?[]const []const u8 = null, /// Which of `ctx_fields` the expression being evaluated has read: a /// `let`'s, an included file's, or once they are done, the program's. reads: std.DynamicBitSetUnmanaged = .{}, /// What each `let` and included file read, handed on to `reads` where /// the slot is used. A capture's stays empty: what it holds was read by /// the expression it was captured from. slot_reads: []std.DynamicBitSetUnmanaged = &.{},
pub fn init( arena: Allocator, sources: []const Diagnostic.Source, tree: Parser.Tree, ctx: ?Value, functions: []const Function, limits: Limits, diag: *Diagnostic, ) Evaluator { return .{ .arena = arena, .sources = sources, .tree = tree, .ctx = ctx, .functions = functions, .limits = limits, .diag = diag, .steps = limits.max_steps, }; }
pub fn run(self: *Evaluator) Error!Value { self.slots = try self.arena.alloc(Slot, self.tree.slots.len); @memset(self.slots, .unset); if (self.ctx_fields) |names| { self.slot_reads = try self.arena.alloc(std.DynamicBitSetUnmanaged, self.slots.len); for (self.slot_reads) |*r| r.* = try .initEmpty(self.arena, names.len); } for (self.tree.slots, self.slots, 0..) |n, *slot, i| { const expr = n orelse continue; // A copy of the slot's set that shares its bits: what the // expression reads lands in the slot's own. if (self.ctx_fields != null) self.reads = self.slot_reads[i]; slot.* = if (self.eval(expr)) |v| .{ .value = v } else |err| switch (err) { error.OutOfMemory => return err, error.Eval, error.LimitExceeded => .{ .failed = .{ .err = err, .diag = self.diag.* } }, }; } if (self.ctx_fields) |names| self.reads = try .initEmpty(self.arena, names.len); return self.eval(self.tree.root); }
/// Note that the expression being evaluated read all of the context. pub fn readAll(self: *Evaluator) void { if (self.ctx_fields != null) self.reads.setAll(); }
/// Note that it read the context's field `name`. A name that is not a /// field -- `len`, or a mistake -- reads none of them. fn readField(self: *Evaluator, name: []const u8) void { const names = self.ctx_fields orelse return; for (names, 0..) |n, i| { if (std.mem.eql(u8, n, name)) return self.reads.set(i); } }
fn context(self: *Evaluator, pos: u32) Error!Value { return self.ctx orelse self.fail(pos, "this program was evaluated without a context", .{}); }
pub fn fail(self: *Evaluator, pos: u32, comptime fmt: []const u8, args: anytype) error{Eval} { self.diag.setAt(self.sources, pos, fmt, args); return error.Eval; }
pub fn limit(self: *Evaluator, pos: u32, comptime fmt: []const u8, args: anytype) error{LimitExceeded} { self.diag.setAt(self.sources, pos, fmt, args); return error.LimitExceeded; }
/// Say what went wrong reading the context. pub fn hostFail(self: *Evaluator, pos: u32, err: Host.Error) error{Eval} { return switch (err) { error.IntegerOutOfRange => self.fail(pos, "a value of type {s} does not fit in an i64", .{self.why}), error.Unsupported => self.fail(pos, "values of type {s} cannot be read", .{self.why}), error.InactiveUnionField => self.fail(pos, "the union holds .{s}, not that", .{self.why}), }; }
pub fn checkString(self: *Evaluator, pos: u32, len: usize) error{LimitExceeded}!void { if (len > self.limits.max_string) return self.limit(pos, "string longer than {d} bytes", .{self.limits.max_string}); }
pub fn checkList(self: *Evaluator, pos: u32, len: usize) error{LimitExceeded}!void { if (len > self.limits.max_list) return self.limit(pos, "list longer than {d} items", .{self.limits.max_list}); }
pub fn eql(self: *Evaluator, pos: u32, a: Value, b: Value) Error!bool { return Value.eql(a, b, &self.steps, &self.why) catch |err| switch (err) { error.LimitExceeded => self.limit(pos, "comparison visits more than {d} values", .{self.limits.max_steps}), else => |e| self.hostFail(pos, e), }; }
pub fn items(self: *Evaluator, pos: u32, v: Value) Error![]const Value { return v.items(self.arena, &self.why) catch |err| switch (err) { error.OutOfMemory => error.OutOfMemory, else => |e| self.hostFail(pos, e), }; }
pub fn itemAt(self: *Evaluator, pos: u32, v: Value, i: usize) Error!Value { return v.itemAt(i, &self.why) catch |err| self.hostFail(pos, err); }
fn fields(self: *Evaluator, pos: u32, v: Value) Error![]const Value.Field { return v.fields(self.arena, &self.why) catch |err| switch (err) { error.OutOfMemory => error.OutOfMemory, else => |e| self.hostFail(pos, e), }; }
pub fn eval(self: *Evaluator, n: *const Node) Error!Value { return switch (n.data) { .null => .null, .bool => |b| .{ .bool = b }, .int => |i| .{ .int = i }, .float => |f| .{ .float = f }, .string => |s| .{ .string = s }, .enum_literal => |name| .{ .enum_literal = name }, .template => |parts| self.template(n.pos, parts), .ctx => { self.readAll(); return self.context(n.pos); }, .slot => |i| switch (self.slots[i]) { .value => |v| { if (self.ctx_fields != null) self.reads.setUnion(self.slot_reads[i]); return v; }, .failed => |f| { if (self.ctx_fields != null) self.reads.setUnion(self.slot_reads[i]); self.diag.* = f.diag; return f.err; }, .unset => unreachable, }, .record => |fs| self.record(fs), .list => |nodes| self.list(n.pos, nodes), // `ctx.name` reads only that field of the context. .field => |f| if (f.object.data == .ctx) { self.readField(f.name); return self.field(n.pos, try self.context(f.object.pos), f.name); } else self.field(n.pos, try self.eval(f.object), f.name), .index => |x| self.index(x.index.pos, try self.eval(x.object), try self.eval(x.index)), .unwrap => |operand| switch (try self.eval(operand)) { .null => self.fail(n.pos, "attempt to unwrap null", .{}), else => |v| v, }, .unary => |u| self.unary(n.pos, u.op, try self.eval(u.operand)), .binary => |b| self.binary(n.pos, b.op, b.lhs, b.rhs), // Outside a field or a list item every `if` has an `else`, and // a `switch` that matches nothing fails, so there is always // something. .@"if", .@"switch" => (try self.choose(n, false)).?, .call => |c| self.call(n.pos, c.func, c.args), }; }
/// Evaluate a field's value or a list's item: null when it is an `if` /// with no `else` whose condition was false, or a `switch` with no /// `else` that matched nothing, and the item is left out. fn item(self: *Evaluator, n: *const Node) Error!?Value { return switch (n.data) { .@"if", .@"switch" => self.choose(n, true), else => try self.eval(n), }; }
/// An `if` or a `switch`. `in_item` says whether it is a field's value or /// a list's item, where choosing nothing leaves the item out, and it /// carries into the branch chosen. fn choose(self: *Evaluator, n: *const Node, in_item: bool) Error!?Value { const branch = switch (n.data) { .@"if" => |x| try self.chooseIf(x), .@"switch" => |x| try self.chooseProng(n.pos, x, in_item), else => unreachable, } orelse return null; return if (in_item) self.item(branch) else try self.eval(branch); }
fn chooseIf(self: *Evaluator, x: ast.If) Error!?*const Node { const cond = try self.eval(x.cond); const taken = if (x.capture) |slot| blk: { if (cond == .null) break :blk false; self.slots[slot] = .{ .value = cond }; break :blk true; } else switch (cond) { .bool => |b| b, else => |v| return self.fail(x.cond.pos, "expected bool, found {s}", .{v.kindName()}), }; return if (taken) x.then else x.@"else"; }
/// The value of the first prong with a case that matches, or of the /// `else` prong if none does. fn chooseProng(self: *Evaluator, pos: u32, x: ast.Switch, in_item: bool) Error!?*const Node { const subject = try self.eval(x.subject); for (x.prongs) |prong| { for (prong.cases) |case| { const matched = switch (case) { .value => |n| blk: { const v = try self.eval(n); if (!try self.eql(n.pos, subject, v)) break :blk false; if (prong.capture) |slot| self.slots[slot] = .{ .value = try self.payload(n.pos, subject, v) }; break :blk true; }, .range => |r| blk: { const lo = try self.eval(r.lo); const hi = try self.eval(r.hi); if (try self.compare(r.lo.pos, .le, lo, subject) == .gt) break :blk false; if (try self.compare(r.hi.pos, .le, subject, hi) == .gt) break :blk false; if (prong.capture) |slot| self.slots[slot] = .{ .value = subject }; break :blk true; }, }; if (matched) return prong.value; } } const otherwise = x.@"else" orelse { if (in_item) return null; return self.fail(pos, "no prong of the switch matches {f}", .{subject}); }; if (otherwise.capture) |slot| self.slots[slot] = .{ .value = subject }; return otherwise.value; }
/// What a prong captures when `case` matched `subject`: a tagged union's /// payload when it was matched by its tag, and `subject` itself otherwise. fn payload(self: *Evaluator, pos: u32, subject: Value, case: Value) Error!Value { if (case != .enum_literal or subject != .host or subject.host.vt.kind != .@"union") return subject; return (subject.fieldAt(0, &self.why) catch |err| return self.hostFail(pos, err)).value; }
fn record(self: *Evaluator, fs: []const ast.Field) Error!Value { var out: std.ArrayList(Value.Field) = try .initCapacity(self.arena, fs.len); for (fs) |f| { const v = try self.item(f.value) orelse continue; out.appendAssumeCapacity(.{ .name = f.name, .value = v, .pos = f.pos }); } return .{ .record = out.items }; }
fn list(self: *Evaluator, pos: u32, nodes: []const ast.Item) Error!Value { try self.checkList(pos, nodes.len); var out: std.ArrayList(Value) = try .initCapacity(self.arena, nodes.len); for (nodes) |n| { const v = try self.item(n) orelse continue; out.appendAssumeCapacity(v); } return .{ .list = out.items }; }
fn template(self: *Evaluator, pos: u32, parts: []const ast.Part) Error!Value { var buf: std.ArrayList(u8) = .empty; for (parts) |part| switch (part) { .text => |t| try buf.appendSlice(self.arena, t), .expr => |e| try self.appendText(&buf, e.pos, try self.eval(e)), }; try self.checkString(pos, buf.items.len); return .{ .string = buf.items }; }
/// Append `v` as text, the way `"${v}"` writes it. pub fn appendText(self: *Evaluator, buf: *std.ArrayList(u8), pos: u32, v: Value) Error!void { switch (v) { .string => |s| try buf.appendSlice(self.arena, s), .int => |i| try buf.print(self.arena, "{d}", .{i}), .float => |f| { var w: std.Io.Writer.Allocating = .fromArrayList(self.arena, buf); defer buf.* = w.toArrayList(); Value.format(.{ .float = f }, &w.writer) catch return error.OutOfMemory; }, .bool => |b| try buf.appendSlice(self.arena, if (b) "true" else "false"), .enum_literal => |name| try buf.appendSlice(self.arena, name), .null => return self.fail(pos, "cannot turn null into text; use 'orelse' to give a default", .{}), else => return self.fail(pos, "cannot turn {s} into text", .{v.kindName()}), } try self.checkString(pos, buf.items.len); }
fn field(self: *Evaluator, pos: u32, object: Value, name: []const u8) Error!Value { if (object == .null) return self.fail(pos, "cannot read field '{s}' of null", .{name}); const found = object.field(name, &self.why) catch |err| switch (err) { error.InactiveUnionField => return self.fail(pos, "the union holds .{s}, not .{s}", .{ self.why, name }), else => |e| return self.hostFail(pos, e), }; if (found) |v| return v; if (std.mem.eql(u8, name, "len")) { if (object == .string) return .{ .int = @intCast(object.string.len) }; if (object.itemCount()) |len| return .{ .int = @intCast(len) }; } if (object.fieldCount() != null) return self.fail(pos, "no field '{s}' in {s}", .{ name, object.kindName() }); return self.fail(pos, "{s} has no field '{s}'", .{ object.kindName(), name }); }
fn index(self: *Evaluator, pos: u32, object: Value, i: Value) Error!Value { if (i != .int) return self.fail(pos, "index must be an int, not {s}", .{i.kindName()}); const len = if (object == .string) object.string.len else object.itemCount() orelse return self.fail(pos, "{s} cannot be indexed", .{object.kindName()}); if (i.int < 0 or i.int >= len) return self.fail(pos, "index {d} is out of bounds for length {d}", .{ i.int, len }); const at: usize = @intCast(i.int); if (object == .string) return .{ .int = object.string[at] }; return self.itemAt(pos, object, at); }
fn unary(self: *Evaluator, pos: u32, op: ast.UnaryOp, v: Value) Error!Value { switch (op) { .not => if (v == .bool) return .{ .bool = !v.bool }, .negate => switch (v) { .int => |i| return .{ .int = std.math.negate(i) catch return self.fail(pos, "integer overflow", .{}) }, .float => |f| return .{ .float = -f }, else => {}, }, } return self.fail(pos, "cannot apply '{s}' to {s}", .{ if (op == .not) "!" else "-", v.kindName() }); }
fn expectBool(self: *Evaluator, n: *const Node, op: ast.BinaryOp) Error!bool { const v = try self.eval(n); if (v != .bool) return self.fail(n.pos, "'{s}' needs bool operands, not {s}", .{ op.symbol(), v.kindName() }); return v.bool; }
fn binary(self: *Evaluator, pos: u32, op: ast.BinaryOp, lhs_node: *const Node, rhs_node: *const Node) Error!Value { switch (op) { .@"and" => return .{ .bool = try self.expectBool(lhs_node, op) and try self.expectBool(rhs_node, op) }, .@"or" => return .{ .bool = try self.expectBool(lhs_node, op) or try self.expectBool(rhs_node, op) }, .@"orelse" => { const lhs = try self.eval(lhs_node); return if (lhs == .null) self.eval(rhs_node) else lhs; }, else => {}, } const lhs = try self.eval(lhs_node); const rhs = try self.eval(rhs_node); switch (op) { .eq => return .{ .bool = try self.eql(pos, lhs, rhs) }, .ne => return .{ .bool = !try self.eql(pos, lhs, rhs) }, .lt, .le, .gt, .ge => { const order = try self.compare(pos, op, lhs, rhs); return .{ .bool = switch (op) { .lt => order == .lt, .le => order != .gt, .gt => order == .gt, .ge => order != .lt, else => unreachable, } }; }, .concat => return self.concat(pos, lhs, rhs), .add, .sub, .mul, .div, .rem => return self.arithmetic(pos, op, lhs, rhs), .@"and", .@"or", .@"orelse" => unreachable, } }
/// The order of two numbers, or of two strings by their bytes. pub fn compare(self: *Evaluator, pos: u32, op: ast.BinaryOp, lhs: Value, rhs: Value) Error!std.math.Order { if (lhs == .string and rhs == .string) return std.mem.order(u8, lhs.string, rhs.string); if (lhs == .int and rhs == .int) return std.math.order(lhs.int, rhs.int); if (asFloat(lhs)) |a| if (asFloat(rhs)) |b| { if (std.math.isNan(a) or std.math.isNan(b)) return self.fail(pos, "cannot order nan", .{}); return std.math.order(a, b); }; return self.fail(pos, "cannot compare {s} {s} {s}", .{ lhs.kindName(), op.symbol(), rhs.kindName() }); }
fn arithmetic(self: *Evaluator, pos: u32, op: ast.BinaryOp, lhs: Value, rhs: Value) Error!Value { if (lhs == .int and rhs == .int) { const a = lhs.int; const b = rhs.int; const r = switch (op) { .add => std.math.add(i64, a, b), .sub => std.math.sub(i64, a, b), .mul => std.math.mul(i64, a, b), .div => std.math.divTrunc(i64, a, b), .rem => remainder(a, b), else => unreachable, } catch |err| return switch (err) { error.Overflow => self.fail(pos, "integer overflow", .{}), error.DivisionByZero => self.fail(pos, "division by zero", .{}), }; return .{ .int = r }; } if (asFloat(lhs)) |a| if (asFloat(rhs)) |b| { return .{ .float = switch (op) { .add => a + b, .sub => a - b, .mul => a * b, .div => a / b, .rem => if (b == 0) return self.fail(pos, "division by zero", .{}) else @rem(a, b), else => unreachable, } }; }; if (op == .add and lhs == .string and rhs == .string) { return self.fail(pos, "'+' does not join strings; use '++'", .{}); } return self.fail(pos, "cannot apply '{s}' to {s} and {s}", .{ op.symbol(), lhs.kindName(), rhs.kindName() }); }
/// `++`: joins strings, joins lists, and merges structs, the right-hand /// side's fields replacing the left's. fn concat(self: *Evaluator, pos: u32, lhs: Value, rhs: Value) Error!Value { if (lhs == .string and rhs == .string) { try self.checkString(pos, lhs.string.len + rhs.string.len); return .{ .string = try std.mem.concat(self.arena, u8, &.{ lhs.string, rhs.string }) }; } if (lhs.itemCount() != null and rhs.itemCount() != null) { const a = try self.items(pos, lhs); const b = try self.items(pos, rhs); try self.checkList(pos, a.len + b.len); return .{ .list = try std.mem.concat(self.arena, Value, &.{ a, b }) }; } if (lhs.fieldCount() != null and rhs.fieldCount() != null) { const a = try self.fields(pos, lhs); const b = try self.fields(pos, rhs); var out: std.ArrayList(Value.Field) = try .initCapacity(self.arena, a.len + b.len); for (a) |f| { const replaced = for (b) |g| { if (std.mem.eql(u8, f.name, g.name)) break g; } else f; out.appendAssumeCapacity(replaced); } for (b) |g| { const existed = for (a) |f| { if (std.mem.eql(u8, f.name, g.name)) break true; } else false; if (!existed) out.appendAssumeCapacity(g); } return .{ .record = out.items }; } return self.fail(pos, "cannot apply '++' to {s} and {s}", .{ lhs.kindName(), rhs.kindName() }); }
fn call(self: *Evaluator, pos: u32, func: ast.Func, arg_nodes: []const *const Node) Error!Value { const args = try self.arena.alloc(Value, arg_nodes.len); for (args, arg_nodes) |*a, n| a.* = try self.eval(n); switch (func) { .builtin => |b| return builtins.call(self, b, pos, arg_nodes, args), .host => |i| { const f = self.functions[i]; var c: Call = .{ .arena = self.arena, .context = f.context, .evaluator = self, .pos = pos, }; return f.call(&c, args); }, } }};
/// `@rem`, the remainder taking the sign of `a` as C's `%` does, without/// its two traps: a zero divisor is an error, and `minInt % -1` is 0.fn remainder(a: i64, b: i64) error{ Overflow, DivisionByZero }!i64 { if (b == 0) return error.DivisionByZero; if (b == -1) return 0; return @rem(a, b);}
pub fn asFloat(v: Value) ?f64 { return switch (v) { .int => |i| @floatFromInt(i), .float => |f| f, else => null, };}