No code in this step. Before you write a new pass, you should be able to point at a program that is wrong today and watch izvor say nothing about it.
Chapter five's evaluator catches an undefined name, but it catches it inside
eval's NODE_IDENT case, and eval only runs on a
piece of the tree once control actually reaches it. That is a run time check wearing the
clothes of a compile time one. Here is the program that exposes the difference.
if 1 < 0 { print oops;oops was never declared anywhere in this program. That is a fact about the source text, true before a single statement runs.
}print 1;Run this file today and it prints 1 and exits cleanly. Nothing ever told you about line 2.
1 < 0 is never true, so eval never evaluates the
then_branch, so it never reaches the NODE_IDENT case for
oops, so env_find never gets asked about a name that does not
exist. The mistake is real and it is sitting right there in the source, but the compiler
only ever finds a mistake by tripping over it while running the program, and this
particular trip wire is wired to a branch nobody takes. Change the condition to
1 < 2 and the exact same source file starts crashing with
undefined name 'oops'. The program did not get more broken. You just got
unlucky enough to run the part that was broken all along.
A real compiler refuses to hand you a binary, or in izvor's case refuses to evaluate
anything at all, until it has looked at every line, not just the ones a particular run
happens to execute. That is a different kind of walk than eval does, and it
is this chapter's whole job.
Checkpoint
Start from a clean tree.
No code yet. Chapter six's type.c already refuses x + y when
the types disagree, at compile time. It would be reasonable to ask why that pass cannot
just grow a few more rules instead of a whole new file existing.
type.c answers one question, over and over, about every node in the tree:
do these things combine into a sensible type? That question has a clean,
local answer for arithmetic and for an annotation. It has no answer at all for the
seven questions below, because none of them are about types. They are about whether the
program's shape makes sense, and that is what semantic analysis means here: not "is this
syntax legal," which the parser already owns, and not "do these types agree," which
type.c already owns, but "does this program, as a whole, refer to things
that exist and use them the way they were declared."
undefined namesChapter one's oops. A name used where nothing declared it, in the scope it was used in.
use before definitionlet y = x + 1; let x = 10;. x is declared, just not yet, at the point y needs it. Worth a different message than "does not exist at all."
assigning to a letChapter five's immutability rule. Caught today only when eval reaches the assignment at run time.
calling something that is not a functionThere is no such thing as a first-class function value in izvor, so this mostly means: the name exists, as a variable, and you tried to call it anyway.
wrong argument countChapter seven's eval_call already checks this, but only once the call is actually reached while running.
duplicate parameter namesfn f(n: Int, n: Int). Nothing anywhere catches this today. Try it and the second n just shadows the first one, silently, at every call.
a non-void function that can finish without returningChapter seven's eval_call treats falling off the end of a function as returning 0. That is a real value nobody asked for, standing in for one that was never computed.
Notice how many of these chapter seven already half-handles, at the wrong time. Wrong
argument count and assigning to a let both already produce a real diag_error
message today, word for word the messages this chapter reuses. What changes is not the
wording. What changes is when the message can fire: before eval ever starts,
instead of however many statements into a run it takes to reach the mistake.
Checkpoint
The whole pass is reachable through one entry point. It takes the parsed program and the
source text, the same two things type_check_program already takes, and it
hands back a count instead of setting a flag.
src/sema.h · new file
/* Semantic analysis: name resolution, call checking, and the
return-path check a type alone cannot answer. Runs after parsing
and after type checking, before anything is evaluated. */#ifndef IZVOR_SEMA_H#define IZVOR_SEMA_Htypedef struct NodeList NodeList;A forward declaration, the same move type.h made in chapter six. Enough for a pointer to appear in the signature below without sema.h having to #include "ast.h". sema.c includes ast.h directly, where NodeList is actually defined.
/* sema_check_program - walk the whole program once, reporting every
name, call and return-path mistake it finds through diag_error.
Returns the number of errors found. Zero means the program is
safe to hand to eval. */A count instead of a bool, on purpose. type_check_program from chapter six returns nothing and leaves "did it fail" to a separate flag you set yourself. This chapter is the one that has to report several mistakes in one run, so its entry point hands back the number directly, and the driver in step 12 just checks whether it is nonzero.
int sema_check_program(const NodeList *program, const char *src);#endifCheckpoint
This is supposed to fail, the same way type.h did in
chapter six: nothing includes it yet and sema.c does not exist, so the
Makefile does not know the file is there. That is fine. It exists for the next steps to
fill in.
Chapter seven turned env.c into a chain of scopes so a function's locals
stop colliding with the caller's. This pass needs the exact same shape, walked at a
different time, for a different reason, and it cannot reuse env.c to get it.
env.c's chain holds Bindings: a name and the value
sitting in it right now, because the evaluator can only know a value once it has actually
run the statement that produced one. This pass runs before anything has run. It never has
a value to store, only the fact that a name exists in a given scope, and whether it is
allowed to be reassigned. So, the same call chapter six made when it needed a name table
that was not about runtime values: build a second, smaller structure that looks like
Env but is not it, because bolting a second, unrelated meaning onto
Env would make every future reader ask which one a given call is about.
src/sema.c · new file, top of the file
/* Semantic analysis: a resolve pass over its own scope chain, a
pre-pass that lets a function call one declared later in the file,
and a structural check that a non-void function cannot finish
without returning. */#include <stdbool.h>#include <string.h>#include "ast.h"#include "diag.h"#include "sema.h"#include "type.h"For TypeKind and TYPE_VOID, needed in step 7 to decide whether a function is even required to return anything.
typedef struct {The equivalent of chapter seven's Binding, minus the value it has no way to know yet.
const char *name; int length; bool mutable;Needed for rule 3 from step 2: assigning to a name that was declared with let.
} SemaName;#define MAX_SCOPE_NAMES 64Smaller than chapter six's 256, on purpose. That table held every name in a whole program with no scoping. This one is per-scope: one function's parameters and locals, or one block's, not the entire file at once.
typedef struct SemaScope {The struct names itself, the same way chapter seven's Env does, so parent below can point at another one before the typedef finishes.
struct SemaScope *parent; SemaName items[MAX_SCOPE_NAMES]; int count;} SemaScope;static void scope_init(SemaScope *scope, SemaScope *parent) { scope->parent = parent; scope->count = 0;}static void scope_define(SemaScope *scope, const char *name, int length, bool mutable) {Always writes into scope directly, never into scope->parent. That is the one rule that makes an inner name shadow an outer one instead of fighting it for a slot, exactly the property chapter seven's env_define already has.
if (scope->count < MAX_SCOPE_NAMES) { scope->items[scope->count].name = name; scope->items[scope->count].length = length; scope->items[scope->count].mutable = mutable; scope->count++; }Sixty-four names is a lot for one function or one block. Silently refusing to record the sixty-fifth, rather than crashing or growing the array, is the same honest-about-its-limit choice chapter six made for its own table. A real program will never notice.
}static SemaName *scope_lookup(SemaScope *scope, const char *name, int length) {The walk chapter seven's env_find does, at compile time, over this pass's own chain instead of the runtime one. Same shape: search this scope, then its parent, then its parent's parent, until something matches or there is nowhere left to climb.
for (SemaScope *s = scope; s != NULL; s = s->parent) { for (int i = 0; i < s->count; i++) { if (s->items[i].length == length && memcmp(s->items[i].name, name, (size_t)length) == 0) { return &s->items[i]; } } } return NULL;}
That is the whole difference between this walk and the evaluator's, stated as plainly as
I can: eval climbs a chain of scopes that exist because statements before it
actually ran and put things in them. This pass climbs a chain of scopes that exist
because statements before it, in the text, were read. No program has executed a
single instruction by the time this chain has anything in it. Same shape of walk, built
for a world where nothing has happened yet.
Now the first half of the function that uses it. resolve_expr walks an
expression, reports a name it cannot account for, and hands nothing back, because unlike
type.c's check_node this pass has no type to propagate. It only
has "did I find a problem," and that lives in one file-scope counter.
src/sema.c · below the scope functions
static int error_count; static void resolve_expr(Node *node, SemaScope *scope,stmts and index exist for one reason: so an undefined name can tell you it is coming later in this same list, rather than just that it does not exist. Step 2's let y = x + 1; let x = 10; example is exactly what these two parameters are for.
const NodeList *stmts, int index, const char *src) { switch (node->type) {Over NodeType, the same enum check_node switches over, so it carries the same rule: no default:, every one of the sixteen values gets a case, even the ten that can never actually be an expression. The switch cannot tell the difference between "this case is impossible" and "you forgot this case," and that is exactly the point of leaving it out.
case NODE_NUMBER: case NODE_BOOL: break; case NODE_IDENT: {Rule 1 and rule 2 from step 2 both live here.
if (scope_lookup(scope, node->as.ident.name, node->as.ident.length) != NULL) { break; } error_count++; if (stmts != NULL &&The lookahead. declared_later is step 9's job to write; it is used here already, the same forward-reference the parser has used since chapter seven, where parse_factor calls parse_call before either is fully defined.
declared_later(stmts, index + 1, node->as.ident.name, node->as.ident.length)) { diag_error(src, node->offset, "'%.*s' is used before it is defined", node->as.ident.length, node->as.ident.name); } else { diag_error(src, node->offset, "'%.*s' is not declared",The exact wording type.c's lookup_type already uses for the same fact. Reusing it is deliberate: this is the same mistake reported by a different pass, and a reader should not have to learn two spellings for it.
node->as.ident.length, node->as.ident.name); } scope_define(scope, node->as.ident.name, node->as.ident.length, true);Step 10 explains this line in full. In short: define the broken name anyway, right here, so every later reference to the same typo stops asking about it a second time.
break; } case NODE_UNARY: resolve_expr(node->as.unary.operand, scope, stmts, index, src); break; case NODE_BINARY: resolve_expr(node->as.binary.left, scope, stmts, index, src); resolve_expr(node->as.binary.right, scope, stmts, index, src); break; /* NODE_CALL: step 5.
NODE_LET .. NODE_RETURN: statements, never reached here. */ }}
resolve_expr is only ever called with an expression: a number, a name, a
unary or binary operator, or a call. It is never handed a NODE_LET or a
NODE_BLOCK. So writing cases for those ten kinds looks like dead weight.
It is not. The switch is over NodeType, which describes every node in the
language, not just the ones this particular function happens to receive. Leaving a case
out because "it can't happen here" is exactly the reasoning that lets a real mistake
hide: the day someone adds a seventeenth NodeType in chapter eleven,
-Werror lists this switch alongside eval's and
check_node's, and you find out here too, instead of only where the new
case actually needed real logic.
Checkpoint
Plain make test, not -Werror, same reason as every earlier
chapter's incomplete switch: the warning is correct, and it is not done being wrong
yet. declared_later does not exist until step 9 either, so this will not
actually link. That is expected too.
Walk the program top to bottom, in one pass, and a call to a function declared three
lines further down looks exactly like a call to one that does not exist. Chapter seven's
eval_call never has this problem, because it does not walk the tree in
order. It searches the whole program for a match every single time it needs one. This
pass does not get to cheat that way twice a statement, so it does the search once, up
front, and remembers the answer.
fn main_logic() -> int { return helper(); }fn helper() -> int { return 42; }Declared after its own caller. Chapter seven's eval_call already handles this, because its search covers the entire program list regardless of where the call sits inside it.
print main_logic();
Without a pre-pass, a single top-to-bottom walk would check main_logic's
body, see a call to helper, and find nothing, because nothing has told this
pass helper exists yet. It would report undefined function 'helper'
against a program that runs perfectly fine today. That would be a regression this chapter
introduced by being stricter than the language actually is. The fix is the same one real
compilers use for this exact shape of problem: collect every top-level function
declaration into a small table before checking the body of any of them, so by the time
any call is checked, every function that will ever exist in this file already does, as
far as this pass is concerned.
src/sema.c · below error_count, above resolve_expr
typedef struct { const char *name; int length; int param_count;Only the count, not the parameter types. izvor still has no way for two calls to the same function to need different argument types, so the count is the whole signature this pass cares about.
} FnSig; #define MAX_FUNCTIONS 128static FnSig functions[MAX_FUNCTIONS];static int function_count;File-scope, like chapter six's binding_count, and for the same reason it needs resetting: a second call to sema_check_program in the same process, exactly what a test binary does, would otherwise see functions left over from whichever program ran through it first.
static void collect_functions(const NodeList *program) {One flat scan of the top level only. A function declared inside a block is not visible to a pre-pass that only looks at program->items, which mirrors the fact that eval_call's own search only ever looks at the top-level program list too.
for (int i = 0; i < program->count; i++) { Node *stmt = program->items[i]; if (stmt->type != NODE_FN) { continue; } if (function_count < MAX_FUNCTIONS) {Same honesty-about-limits choice as scope_define. A program with more than 128 top-level functions is not one this stage of izvor needs to worry about yet.
functions[function_count].name = stmt->as.fn.name; functions[function_count].length = stmt->as.fn.length; functions[function_count].param_count = stmt->as.fn.params.count; function_count++; } }} static FnSig *find_function(const char *name, int length) { for (int i = 0; i < function_count; i++) { if (functions[i].length == length && memcmp(functions[i].name, name, (size_t)length) == 0) { return &functions[i]; } } return NULL;}
Now the case in resolve_expr this table exists to serve: rule 4 and rule 5
from step 2, existence and argument count, in one place, because both questions are
answered by the same lookup.
src/sema.c · inside resolve_expr's switch, replacing the NODE_CALL comment placeholder
case NODE_CALL: { FnSig *fn = find_function(node->as.call.name, node->as.call.length); if (fn == NULL) { error_count++; if (scope_lookup(scope, node->as.call.name, node->as.call.length) != NULL) {Rule 4: the name exists, it is just not a function. This is the one place the two separate namespaces, variables in scope and functions in functions[], both get consulted about the same name, specifically so the error can tell them apart.
diag_error(src, node->offset, "'%.*s' is not a function", node->as.call.length, node->as.call.name); } else { diag_error(src, node->offset, "undefined function '%.*s'", node->as.call.length, node->as.call.name); } } else if (fn->param_count != node->as.call.args.count) {The exact message eval_call already prints at run time, moved to a point before eval ever starts.
error_count++; diag_error(src, node->offset, "'%.*s' expects %d argument%s, got %d", node->as.call.length, node->as.call.name, fn->param_count, fn->param_count == 1 ? "" : "s", node->as.call.args.count); } for (int i = 0; i < node->as.call.args.count; i++) {Checked unconditionally, even when the call itself was already wrong. Chapter six's binary-operator rule made the same call for the exact same reason: a bad call name should not hide a second, unrelated mistake sitting inside one of its arguments.
resolve_expr(node->as.call.args.items[i], scope, stmts, index, src); } break; }Checkpoint
resolve_expr is now complete for every kind of expression the language
has. The remaining warning is entirely about the statement kinds step 7 still owes it.
A small, self-contained check, unrelated to the scope chain and unrelated to the function
table. fn f(n: Int, n: Int) { ... } parses today, and nothing anywhere
objects to it. Try it: the second n silently wins, because chapter seven's
eval_call defines each parameter into the same frame in order, and the
second env_define for n just adds a second entry that
env_find happens to find first.
src/sema.c · above resolve_expr, or below it; it does not depend on the scope chain or the function table
static void check_duplicate_params(Node *fn, const char *src) { const NodeList *params = &fn->as.fn.params;Each entry is a NODE_IDENT, exactly what chapter seven's parse_fn pushes into params, one per parameter, each carrying its own param_type that this check does not need to look at.
for (int i = 0; i < params->count; i++) { Node *a = params->items[i]; for (int j = 0; j < i; j++) {Every pair, compared once. A function with a dozen parameters is unusual enough that the O(n²) cost of comparing each one against every earlier one is not worth a smarter structure here.
Node *b = params->items[j]; if (a->as.ident.length == b->as.ident.length && memcmp(a->as.ident.name, b->as.ident.name, (size_t)a->as.ident.length) == 0) { error_count++;Reported against a's own offset, the second occurrence, because that is the one a reader would not expect to be a problem: the first n looks completely ordinary on its own.
diag_error(src, a->offset, "duplicate parameter '%.*s'", a->as.ident.length, a->as.ident.name); break; } } }}Nothing calls this yet. Step 7 wires it into the one place a function declaration is actually visited.
Checkpoint
Expected, same as chapter four's dead is_ident_start before step 5 wired it up.
The last rule from step 2, and the one that needs its own small function, because it is
not a question about names at all. It is a question about the shape of the code: can
control reach the closing brace of this function without ever hitting a
return.
fn double(n: Int) -> Int { if n > 0 { return n * 2; } } parses, type
checks, and runs. Call it with -1 and chapter seven's eval_call
falls off the end of the body and hands back 0, a value nobody wrote, standing
in for a return that never happened. Answering "can this finish without
returning" needs no name and no type. It needs to look at the shape of the statements
themselves: a block returns if any statement inside it definitely returns; an
if only returns for certain if it has an else and both
branches return; a while never counts, because this pass has no way to know
how many times, if any, a loop body will run.
src/sema.c · above resolve_expr, or anywhere above the point that calls it
static bool always_returns(Node *stmt) {Same discipline as type_name in chapter six: every case returns a value, so there is nothing after the switch's closing brace, and a case you forget to add is a build failure instead of a silent wrong answer.
switch (stmt->type) { case NODE_RETURN: return true; case NODE_BLOCK:One statement guaranteeing a return is enough for the whole block to, even if statements after it would never run. Whether that later code is actually reachable is a different question this chapter does not ask.
for (int i = 0; i < stmt->as.block.stmts.count; i++) { if (always_returns(stmt->as.block.stmts.items[i])) { return true; } } return false; case NODE_IF:No else_branch means there is always a way through this if that returns nothing, namely the condition being false. && short-circuits, so else_branch is only recursed into once then_branch already came back true, which costs nothing extra to reason about.
if (stmt->as.if_stmt.else_branch == NULL) { return false; } return always_returns(stmt->as.if_stmt.then_branch) && always_returns(stmt->as.if_stmt.else_branch); case NODE_WHILE:Always false, deliberately conservative. A while true { return 1; } really does always return, but proving that would mean reasoning about whether the condition can ever be false, which this pass does not attempt. It would rather refuse a handful of functions that are secretly fine than accept one that is not.
case NODE_LET: case NODE_VAR: case NODE_ASSIGN: case NODE_PRINT: case NODE_EXPR_STMT: case NODE_FN: return false;None of these can end a function on their own. A nested fn is its own separate function with its own separate return-path question, checked separately when this same walk reaches it.
case NODE_NUMBER:This function is only ever called on a statement, so these six can never actually arrive. Written anyway, same reasoning as step 4's trap: the switch does not know that, and it should not have to trust a comment instead of the compiler.
case NODE_IDENT: case NODE_UNARY: case NODE_BINARY: case NODE_BOOL: case NODE_CALL: return false; }}
Now the function that actually walks the tree, resolve_stmt. It is the
missing other half of what step 4 started: every statement kind, each doing exactly what
its counterpart in eval or check_node does, except that instead
of producing a value or a type, it either defines a name, checks one, or recurses.
src/sema.c · below always_returns
static void resolve_stmt(Node *stmt, SemaScope *scope, const NodeList *stmts, int index, const char *src) { switch (stmt->type) { case NODE_LET:Check the initializer before defining the name, in that order, on purpose: let x = x; should see the right-hand x as not-yet-declared, not as referring to the binding it is itself in the middle of creating.
case NODE_VAR: resolve_expr(stmt->as.binding.value, scope, stmts, index, src); scope_define(scope, stmt->as.binding.name, stmt->as.binding.length, stmt->type == NODE_VAR); break; case NODE_ASSIGN: {Rule 3 from step 2. The exact wording eval's NODE_ASSIGN case already uses, moved earlier.
SemaName *existing = scope_lookup(scope, stmt->as.binding.name, stmt->as.binding.length); if (existing == NULL) { error_count++; diag_error(src, stmt->offset, "'%.*s' is not declared", stmt->as.binding.length, stmt->as.binding.name); scope_define(scope, stmt->as.binding.name, stmt->as.binding.length, true); } else if (!existing->mutable) { error_count++; diag_error(src, stmt->offset, "cannot assign to '%.*s', it is a let binding", stmt->as.binding.length, stmt->as.binding.name); } resolve_expr(stmt->as.binding.value, scope, stmts, index, src); break; } case NODE_PRINT: case NODE_EXPR_STMT: resolve_expr(stmt->as.stmt.value, scope, stmts, index, src); break; case NODE_BLOCK: {A fresh scope, parented to whatever scope this block sits inside of, exactly like eval's own NODE_BLOCK case builds a fresh Env the same way, one plain local variable, no allocation.
SemaScope inner; scope_init(&inner, scope); for (int i = 0; i < stmt->as.block.stmts.count; i++) { resolve_stmt(stmt->as.block.stmts.items[i], &inner, &stmt->as.block.stmts, i, src); } break; } case NODE_IF: resolve_expr(stmt->as.if_stmt.cond, scope, stmts, index, src); resolve_stmt(stmt->as.if_stmt.then_branch, scope, stmts, index, src); if (stmt->as.if_stmt.else_branch != NULL) { resolve_stmt(stmt->as.if_stmt.else_branch, scope, stmts, index, src); } break; case NODE_WHILE: resolve_expr(stmt->as.while_stmt.cond, scope, stmts, index, src); resolve_stmt(stmt->as.while_stmt.body, scope, stmts, index, src); break; case NODE_FN: {Rules 6 and 7 from step 2, plus the one piece of setup they both needed: a scope that starts with the parameters already in it.
check_duplicate_params(stmt, src); if (stmt->as.fn.ret_type != TYPE_VOID && !always_returns(stmt->as.fn.body)) { error_count++; diag_error(src, stmt->offset, "'%.*s' can finish without returning a value", stmt->as.fn.length, stmt->as.fn.name); } SemaScope frame;Parented to global_scope, not to scope, the same choice chapter seven's eval_call makes when it calls env_init(&frame, global_env(env)) instead of parenting to the caller. A function's meaning depends on what is written next to it, never on where it happened to be called from, so its body has to resolve names against the top level, not against whatever block its own declaration is sitting in.
scope_init(&frame, global_scope); for (int i = 0; i < stmt->as.fn.params.count; i++) { Node *param = stmt->as.fn.params.items[i]; scope_define(&frame, param->as.ident.name, param->as.ident.length, false);false: a parameter cannot be reassigned, the same rule chapter seven's eval_call enforces by calling env_define(&frame, ..., false) for every parameter it binds.
} resolve_stmt(stmt->as.fn.body, &frame, NULL, 0, src);stmt->as.fn.body is always a NODE_BLOCK, guaranteed by parse_fn calling parse_block for it. Its own NODE_BLOCK case above will give it a further, nested scope parented to frame, exactly the same layering the runtime has between a call frame and the block inside it.
break; } case NODE_RETURN: if (stmt->as.return_stmt.value != NULL) { resolve_expr(stmt->as.return_stmt.value, scope, stmts, index, src); } break; case NODE_NUMBER: case NODE_IDENT: case NODE_UNARY: case NODE_BINARY: case NODE_BOOL: case NODE_CALL: break;Expressions never arrive as a bare statement on their own; NODE_EXPR_STMT above is what wraps one when that happens. Listed anyway, same exhaustiveness rule as everywhere else in this file.
}}
One name is still undefined: global_scope. It has to point at the one scope
every function body resolves against, which means it has to be set before
resolve_stmt ever runs, by the function that owns the whole walk from end to
end.
src/sema.c · above resolve_expr, near error_count
static SemaScope *global_scope;src/sema.c · at the bottom of the file
int sema_check_program(const NodeList *program, const char *src) { error_count = 0;Every file-scope static reset here, the same discipline as chapter six's type_check_program: compiling a program is a fresh start, and a second call in the same process must not see anything left behind by an earlier one.
function_count = 0; SemaScope root; scope_init(&root, NULL); global_scope = &root; collect_functions(program);The pre-pass, run to completion, before a single call is checked.
for (int i = 0; i < program->count; i++) { resolve_stmt(program->items[i], &root, program, i, src); } return error_count;}Checkpoint
declared_later still does not exist, so this will not link yet; that is
step 9. Every switch in sema.c is otherwise complete and clean under
-Werror on its own.
Everything above finds several sema mistakes in one run for free, because
resolve_stmt never stops walking just because one statement had a problem.
The parser is not that lucky. Go look at chapter five's parser_parse: the
moment parse_statement returns NULL, it frees everything parsed
so far and gives up on the whole file. A source file with three missing semicolons in it
gets you exactly one error message, for the first one, and the other two are invisible
until you fix the first and run the compiler again.
The standard fix is called panic mode recovery, and the idea is one sentence: when a statement fails to parse, do not stop, skip forward until you are somewhere the parser can plausibly make sense of again, and keep going. In izvor, "somewhere that makes sense again" has an obvious answer, because chapter five made semicolons mandatory. The token right after a semicolon is always the start of a fresh statement, no matter how confused the parser was about the statement before it. That is the whole reason a required terminator earns its keep here: it gives recovery a landmark to aim for that a newline-terminated or terminator-free grammar would not have.
src/parser.c · above parse_statement, or anywhere above parser_parse
static bool starts_statement(TokenType type) {Every token that a legal statement can begin with, read straight off the grammar chapters five and seven already wrote: let, var, print, if, while, fn, return, and { for a bare block.
return type == TOK_LET || type == TOK_VAR || type == TOK_PRINT || type == TOK_IF || type == TOK_WHILE || type == TOK_FN || type == TOK_RETURN || type == TOK_LBRACE;} /* synchronize - after a bad statement, skip tokens until parsing can
plausibly resume: just past a semicolon, since that almost always
ends whatever went wrong, or at a token that starts a fresh
statement even without one. Stops at EOF too, so a file that never
recovers cannot make this loop spin forever. */static void synchronize(Parser *p) {No lookbehind needed. Rather than ask "was the token I just consumed a semicolon," which would need a previous field this Parser has never had, this checks p->current for a semicolon before consuming it, then advances past it either way.
while (!parser_check(p, TOK_EOF)) { bool at_semicolon = parser_check(p, TOK_SEMICOLON); parser_advance(p); if (at_semicolon || starts_statement(p->current.type)) {Stop either because the semicolon that ended the mess is now behind us, or because, semicolon or not, the very next token already looks like the start of something the parser knows how to read.
return; } }}
Chapter five's parser_parse called nodelist_free(out) the
moment any statement failed, which meant every caller could treat "parse failed" and
"there is nothing in out to clean up" as the same fact. That stops being
true the moment recovery exists. The whole point of synchronizing is to keep the
statements that did parse successfully, in the same list, so more errors can
be found in the same run, so parser_parse can no longer free
out on the first failure without throwing away exactly the information
recovery exists to collect. Step 9 rewrites parser_parse with that in
mind, and once it does, main.c has a new responsibility it did not have
before: on a failed parse, it now has to call nodelist_free on the program
itself, because the function that used to do that for it no longer can.
Checkpoint
Two small pieces left before either pass can actually run to completion: the parser has
to use synchronize instead of giving up, and resolve_expr is
still calling a function, declared_later, that step 4 promised but never
wrote.
src/parser.h · inside struct Parser, alongside fn_depth
int error_count;A second counter, next to fn_depth, for the same reason chapter seven added that one: a fact parser_parse needs to track across the whole file, not just within one call to parse_statement.
src/parser.c · parser_init, alongside p->fn_depth = 0;
p->error_count = 0;src/parser.c · replacing the existing parser_parse from chapter five
int parser_parse(Parser *p, NodeList *out) { nodelist_init(out); p->error_count = 0; while (!parser_check(p, TOK_EOF)) { Node *stmt = parse_statement(p); if (stmt == NULL) {This used to free out and return immediately. Now it counts the failure, resynchronizes, and loops back around to try the next statement, so parse_statement gets called again instead of the whole function bailing.
p->error_count++; synchronize(p); continue; } if (!nodelist_push(out, stmt)) { ast_free(stmt); nodelist_free(out); return 0; } } return p->error_count == 0;Success still means exactly what it meant before: a caller checking if (!parser_parse(...)) does not need to change at all. What changed is everything inside the call: a file with three bad statements now runs parse_statement three separate times against three separate parts of the file, instead of stopping after the first.
}
Reporting in source order needs no extra work at all. Every message, from either pass,
fires the moment its own walk reaches the node responsible, and both walks move forward
through the file and never backward. Trace a file with a bad statement on line 2, an
undefined name on line 5, and a wrong argument count on line 9: parser_parse
hits line 2 first because it is scanning top to bottom, reports it, resynchronizes, and
reaches lines 5 and 9 as ordinary, parseable statements. Assuming the parse as a whole
still fails only because of line 2's error count, main would stop there in
practice; but if line 2 had instead been something sema catches instead of the parser,
sema_check_program's single top-to-bottom loop reaches line 5 before line 9
for the same reason: it is walking the array in order, and it never jumps ahead or back
to reconsider anything.
Now the lookahead resolve_expr has been calling since step 4.
src/sema.c · above resolve_expr
/* declared_later - true if stmts, starting at from, contains a let
or var that would define name. Used only to choose the clearer of
two messages: a name arriving later in this same block was written
in the wrong order, not misspelled and not missing entirely. */static bool declared_later(const NodeList *stmts, int from, const char *name, int length) { for (int i = from; i < stmts->count; i++) { Node *stmt = stmts->items[i]; if ((stmt->type == NODE_LET || stmt->type == NODE_VAR) && stmt->as.binding.length == length && memcmp(stmt->as.binding.name, name, (size_t)length) == 0) { return true; } } return false;}
It only looks at the exact list it is handed, one level of nesting at a time, never into
a nested block. let y = x + 1; if 1 > 0 { let x = 10; } should still say
x is not declared, not that it is used early, because the x
inside the if lives in a different, inner scope that the outer y
was never going to see regardless of order.
Checkpoint
First clean, fully linked build since step 3. Try a file with three separate missing semicolons in it by hand and count the error lines on stderr.
No new code in this step. Two lines already written, back in step 4, deserve a second look, because without them, everything this chapter just built would make izvor's error output worse, not better.
Panic mode recovery has a well-known failure of its own: resynchronizing after one
mistake can leave the parser in a slightly wrong position, and the very next statement,
which was actually fine, gets misread and reported as a second error that only exists
because of the first one. Chapter eight's synchronize keeps this small by
aiming at the most reliable landmark the grammar has, the token right after a semicolon,
which is also exactly where a real statement is guaranteed to start. It cannot eliminate
every possible avalanche, but it gives the parser the best-anchored place to resume that
this grammar offers.
Sema has the exact same problem in a different shape, and chapter six already solved it
once. Go back to resolve_expr's NODE_IDENT case:
error_count++;diag_error(src, node->offset, "'%.*s' is not declared", ...);scope_define(scope, node->as.ident.name, node->as.ident.length, true);Defining the name immediately after reporting it missing.
Picture print z; print z; print z;, three references to the same
never-declared name. Without that third line, every single one of those three would
independently fail the same scope_lookup and independently report the exact
same fact about the exact same name. One root cause, three identical messages, and a
reader left wondering whether they are looking at three bugs or one. The line above
poisons the name into the current scope the moment it is first reported: the second and
third print z; now find z sitting right there in
scope, scope_lookup succeeds, and nothing fires a second time.
This is TYPE_ERROR from chapter six, wearing a different hat. Chapter six's
checker hands back a sentinel type meaning "already told you, do not tell you again" so
one bad addition does not cascade into every later expression that touches its result.
This pass has no type to hand back; it has a scope to write into instead. Same rule,
same reason, different mechanism: the first time a mistake is found, immediately do
whatever makes this exact mistake invisible to the rest of the walk, so what should be
one message never turns into ten. Every new check this pass or a later one adds has to
ask itself the same question chapter six's step 9 already asked: after I report this,
what do I do to stop myself from reporting it again on the next line.
Look back at step 7's NODE_ASSIGN case: an assignment to an undeclared
name also calls scope_define after reporting it, for the identical reason.
x = 1; x = 2; x = 3; against a never-declared x reports once,
not three times, because the first bad assignment defines x well enough
for the second and third to pass the lookup cleanly. It is defined as mutable there on
purpose, even though the error is unrelated to mutability, so a poisoned name never
goes on to trigger a second, unrelated "it is a let binding" message about a binding
that was never real in the first place.
Checkpoint
One test file, written by you, and it is the most important one in this chapter. Every earlier golden test in this project has pinned down what a single mistake says. This one proves the chapter's actual promise: that a broken file does not make you fix mistakes one at a time, rerunning the compiler after each one.
tests/test_sema_1.c · new file · copy the shape of tests/test_type_1.c
Assertions to write, cheapest and most specific to most integrated.
"print z;"Refused with 'z' is not declared, and sema_check_program returns 1. The plain undefined-name case, proving rule 1.
"let y = x + 1; let x = 10;"Refused with 'x' is used before it is defined, not the plainer "not declared" message. Proves declared_later actually runs, not just that some error fires.
"let n = 5; n = 6;"Refused with cannot assign to 'n', it is a let binding. Then "var n = 5; n = 6;", which must be accepted: the happy case for rule 3, so a later regression that broke mutability entirely would fail here too.
"fn add(a: Int, a: Int) -> Int { return a; }"Refused with duplicate parameter 'a'.
"fn maybe(n: Int) -> Int { if n > 0 { return n; } }"Refused with 'maybe' can finish without returning a value. Then the same function with an else { return 0; } added, which must be accepted.
"print z; print z;"Redirect stderr to a buffer and count lines starting with error:. Exactly one, not two. This is step 10's poisoning guard, and it is the assertion most likely to quietly break if a later change touches scope_define's placement.
Now the one that matters most, and the reason this chapter exists.
tests/golden/three-mistakes.iz · new fixture, with a matching tests/golden/three-mistakes.expected
let a = 1let b = 2;Line 1 is missing its semicolon. That is a parser mistake, and it is the one synchronize exists for: without recovery, this single missing character used to make everything below it unreachable.
print unknown_name;A sema mistake: an undefined name, entirely unrelated to line 1.
fn broken(n: int) -> int { print n; }A second, different sema mistake: broken promises an Int and can fall off the end without returning one.
Run this through the driver you finish in step 12 and stderr should hold three separate
error: blocks, in this order: a parse error naming the missing semicolon on
line 1, then 'unknown_name' is not declared for line 3, then
'broken' can finish without returning a value for line 4. Line 2 never gets
mentioned at all, which is exactly right: it has nothing wrong with it, and the fact that
it sits one line below a syntax error is no longer enough to make it collateral damage.
Checkpoint
Every earlier golden case still matches, and the three-mistake fixture reports all three, in order, and nothing else.
Two small edits close the chapter: a call in the driver, and a line in the Makefile so the new file actually gets compiled and linked into everything.
src/main.c · the failed-parse check, right where chapter five's driver already handles parser_parse returning 0
if (!parser_parse(&parser, &program)) {Substitute your driver's own variable names here; the shape is what matters.
nodelist_free(&program);The line step 8's trap called out. parser_parse no longer frees the partial program on failure, since it needs to survive long enough for recovery to keep collecting more errors, so the caller now owns that cleanup, the same way it already owns cleanup after every other failure point in main.
return 1; }src/main.c · in main(), directly after chapter six's type_check_program call and its own failure check, before the loop that calls eval
#include "sema.h" if (sema_check_program(&program, src) > 0) {Placed after type checking and before evaluation, exactly where the task this pass does belongs: types have already been confirmed sound, nothing has been evaluated yet, and sema gets the final say before anything runs. Every error it found is already on stderr by the time this line runs, printed as it was found rather than collected and dumped at the end.
nodelist_free(&program); return 1; }Makefile · the SRC := line
SRC := src/lexer.c src/ast.c src/parser.c src/diag.c src/env.c src/type.cSRC := src/lexer.c src/ast.c src/parser.c src/diag.c src/env.c src/type.c src/sema.cLeave it off this list and every test that touches sema_check_program or any of its static helpers fails to link, naming them as undefined symbols. The same linker-problem-dressed-as-a-compiler-problem chapter six's step 3 already walked through once.
Checkpoint
Three error: blocks on stderr, none of them about line 2, and a nonzero
exit status. A program with none of these seven mistakes in it still compiles and runs
exactly as it did at the end of chapter seven; this pass has nothing to say about a
program that was already correct.