goparser

Go parser producing a flat token stream with control flow encoded as Label/Goto/JumpFalse -- no AST.

Overview

The goparser package takes scanner tokens and produces a flat Tokens slice suitable for single-pass code generation. It performs scope tracking, type resolution, and expression rewriting (infix to postfix). It is the most complex stage in the pipeline.

Key types and functions

• Parser -- embeds *scan.Scanner and a symbol.SymMap. Holds a Packages map (map[string]*symbol.Package) for imported packages and a pkgfs filesystem for reading imported source files. Tracks the current scope path, break/continue labels, closure state, and named return variables.
• Token -- extends scan.Token with an Arg []any field for label targets, type info, etc.
• Tokens -- slice of Token with helper methods (Index, Split, SplitStart).
• Parse(src string) (Tokens, error) -- full parse: scan, then parse all statements into a postfix token stream.
• ParseAll(name, src string) ([]Tokens, error) -- top-level entry point for multi-file compilation. If src is empty and name is a directory, loads its .go files via LoadPackageSources and runs Phase 1 (declaration resolution with retry loop) on the union; returns remaining declarations for Phase 2 code generation. Handles import statements by recursively calling itself.
• LoadPackageSources(importPath string, includeTests bool) ([]PackageSource, error) -- enumerates the .go files of a package directory through the FS chain (pkgfs -> stdlibfs -> remotefs) and applies build-tag filtering (MatchFileName + //go:build directives). When includeTests is false the result excludes _test.go (the import path uses this); mvm test <importpath> flips it on. Result order matches fs.ReadDir, which is sorted by filename.
• PackageSource{Name, Content string} -- one .go file's basename and content, as returned by LoadPackageSources.
• ImportPackageValues(m map[string]map[string]reflect.Value) -- populates Packages with binary (native Go) package values, using symbol.BinPkg to wrap them.
• SetPkgfs(pkgPath string) -- sets the parser's primary virtual filesystem for resolving imported source packages.
• SetStdlibFS(fsys fs.FS) -- second-tier fallback, typically stdlib.SrcFS() for embedded generics-first packages.
• SetRemoteFS(fsys fs.FS) -- third-tier fallback, typically a modfs.FS that fetches modules from a Go module proxy on demand. See modfs.
• SetIncludeTests(b bool) -- toggle whether dir-mode ParseAll (and therefore LoadPackageSources) includes _test.go files. Saved and restored across importSrc so the flag stays local to the top-level test target and never leaks into transitive imports.
• ParseDecl(toks Tokens) (handled bool, err error) -- resolve a single declaration during Phase 1 without emitting code. Delegates to parsePackage, parseImports, parseConst, parseType, registerFunc, or parseVarDecl. Returns handled=false when the declaration needs full parse + code generation (func bodies, var initializers).
• ParseOneStmt(toks Tokens) (Tokens, error) -- parse a single statement (used during compilation phase 2).
• registerFunc(toks Tokens) error -- register a function or method signature in the symbol table without parsing its body. For methods (func (recv) Name(...)), extracts the receiver type via recvTypeName and registers under TypeName.MethodName. Caches parameter names in the Type and receiver variable name in Symbol.RecvName so parseFunc can skip re-parsing the signature. Parses in typeOnly mode to suppress parameter symbol registration. Generic functions (func Name[T any](...)) are detected here and stored as symbol.Generic templates instead of being parsed immediately.
• SplitAndSortVarDecls(decls []Tokens) []Tokens -- expands var(...) blocks into individual declarations and topologically sorts them by dependency (references between var initializers). Non-var declarations keep their original positions.
• recvTypeName(recvr Tokens) string -- extracts the type name from scanned receiver tokens (e.g. "T" from (t T), "*T" from (t *T)).

Error types and diagnostics

• ErrUndefined{Name, Loc} -- symbol not yet defined. The Phase 1 retry loop matches via errors.As(err, &eu), so the type is preserved while the optional Loc ("file:line:col") prefixes the rendered message when set. The compiler populates Loc via c.errUndef; the parser leaves it empty for retry-only paths where the location is irrelevant.
• p.errAt(tok, format, args...) (unexported helper, mirrored as c.errAt on the compiler). Formats an error with the source position of tok resolved through Sources.FormatPos. Falls back to the bare message when the position cannot be resolved (synthetic tokens, empty Sources). This is the canonical way to raise position-aware errors from the parser and is the pattern most user-facing structural errors are migrated to.

Source-position resolution relies on tokens carrying absolute positions in a unified pos space. ParseAll calls p.PosBase = p.Sources.Add(name, src) before invoking scanDecls, so scanAt(p.PosBase, src, true) shifts every scanned token's Pos into the right [Base, Base+Len) window. The directory-mode loader registers each file under name+"/"+f.Name(), so a parse error from inside an imported module reports the actual filename rather than just the package path.

Internal design

Expression parsing

parseExpr converts infix expressions to postfix using a shunting-yard algorithm. Operator precedence and associativity come from lang.TokenProps.

Binary operators are left-associative: when a binary operator op is pushed onto the operator stack, the shunting-yard loop flushes all pending operators with precedence >= prec(op) before pushing op. Unary operators flush only > prec(op), making them right-associative.

A token preceded by a colon (e.g. in composite literals) is treated as a unary context, so that & or * there is not misclassified as binary.

Position propagation

Every token reaches comp.emit with Pos already shifted into the unified scan.Sources byte-offset space. The rule: any helper that produces tokens from a sub-string must call scanAt(basePos, ...) with the absolute byte offset of where that sub-string starts.

• The top-level path uses scanDecls(src) -> scanAt(p.PosBase, src, true), where p.PosBase is set by Sources.Add(name, content).
• scanBlock(bt, ...) and parseTokBlock(bt) derive basePos = bt.Pos + bt.Beg from a previously-absolute brace token.
• parseComposite(s, typ, basePos) takes basePos = t.Pos + t.Beg from its BraceBlock caller. Without this, every Call/CallImm emitted from inside a composite literal would have an invalid Pos pointing into the first source -- making runtime.Callers-style stack traces (and DumpCallStack output) collapse to file 0 line 1 for any code defined inside []struct{...}{ ... }.
• p.scan(s, false) is shorthand for scanAt(0, s, false) and is reserved for token streams that never reach emit, e.g. numItems in stmt.go (counts only).

comp.emit then writes inst.Pos = vm.Pos(t.Pos) directly; see comp.md and ADR-015.

Control flow encoding

Instead of building an AST, control structures are lowered to Label/Goto/JumpFalse tokens:

if cond { body }
-->  cond, JumpFalse(L1), body..., Label(L1)

for init; cond; post { body }
-->  init, Label(L0), cond, JumpFalse(L1), body..., post, Goto(L0), Label(L1)

Labels are scoped and auto-numbered (e.g. for0, if1) via labelCount.

Switch and select clause splitting

switch, type-switch and select bodies all reach the parser as a single BraceBlock. The parser splits the body into per-case clauses via Tokens.SplitStart(lang.Case) and then moves any default clause to the last position. A small helper, caseClauses(body), wraps these two steps with a filter: it discards leading or trailing segments that do not start with Case or Default. This drops the [Comment] clauses produced when the scanner inserts a synthetic semicolon after a stray comment between { and the first case (a pattern that appears in github.com/google/uuid/uuid.go). Without the filter, moveDefaultLast and downstream parseCaseClause indexing would panic on the short clause.

Scope tracking

Scopes are slash-separated paths pushed/popped as the parser enters/leaves blocks. The scope path is used as a prefix key in symbol.SymMap.

Bare braced blocks ({ ... } as a statement, not controlled by if, for, or switch) are supported as anonymous nested scopes. parseStmt detects a leading BraceBlock token, pushes a synthetic block<n> scope label, parses the block body, then pops the scope on exit. This matches Go semantics for variable shadowing inside bare blocks.

Goroutine and channel syntax

go statements. parseGo validates that the statement is go expr(args) -- it requires the last token of the function expression to be a ParenBlock. It parses the callee expression with parseExpr, then the argument block with parseBlock, and appends a lang.Go{narg} token. The resulting token stream mirrors the shape of a call statement and is handled symmetrically by the compiler.

Channel send statements. parseStmt detects <- with a positive index before any = or :=, which unambiguously identifies a send statement. It calls parseChanSend(in, arrowIdx), which parses the channel expression and value expression separately and appends a lang.ChanSend token.

Unary channel receive. In parseExpr, lang.Arrow (<-) is treated as a unary prefix operator with precedence 6 (equal to unary minus). In a two-result assignment (v, ok := <-ch), parseAssign sets t.Arg[0] = 1 on the trailing Arrow token to signal the ok-form to the compiler.

Channel types. parseTypeExpr handles chan T by recursively calling itself for the element type and constructing a vm.ChanOf type. Directional channels (chan<-, <-chan) are syntactically accepted but mapped to bidirectional channels.

Closure analysis

When a function literal references a variable from an outer scope, the parser marks that variable as Captured and records it in FreeVars. This drives HeapAlloc/HeapGet/HeapSet emission during compilation.

Method registration and receiver handling

registerFunc (Phase 1) and parseFunc (Phase 2) both handle methods.

In Phase 1, registerFunc detects the receiver ParenBlock before the method name, scans it, and calls recvTypeName to extract the type name (handling both value and pointer receivers). The method is registered under TypeName.MethodName in the symbol table.

In Phase 2, parseFunc parses the full method body. A subtlety: calling parseParamTypes on the receiver block registers a LocalVar symbol at the outer scope, which may clobber an existing global symbol with the same name. parseFunc saves the original symbol (savedRecvOuter) before parsing, copies the receiver symbol into the function scope, then restores (or deletes) the outer-scope entry.

A second subtlety: an anonymous function whose return type starts with an Ident (e.g. func() time.Time { ... }) reaches parseFunc looking syntactically like a method declaration -- func, ParenBlock, Ident. The parser disambiguates by checking that the Ident is a known Type; otherwise it falls into the method branch, scans an empty receiver block, and would synthesize a bogus <scope>.<ident> symbol name (e.g. TestClockSeq.time if time is a Pkg, not a Type). The method branch is gated by recvTypeName(recvr) != "" so an empty receiver yields no name and the function is treated as anonymous (#fN) instead.

Variadic parameters

parseParamTypes detects ...T syntax (the Ellipsis token) and converts it to a []T slice type, setting a variadic flag. This flag propagates through FuncOf so the compiler knows to pack trailing arguments at the call site.

Package and import handling

Import resolution lives in import.go. ParseAll is the main entry point:

1. If src is empty and name is a directory, calls LoadPackageSources to enumerate .go files through the FS chain (pkgfs -> stdlibfs -> remotefs). The pkgfs error is preserved when all fallbacks miss, so downstream error messages still reference the user's primary filesystem. The includeTests flag (set via SetIncludeTests) controls whether _test.go files are included; default off.
2. For each loaded source, registers it with Sources.Add(name+"/"+filename, content) before scanning, so scanDecls produces tokens with absolute positions resolvable back to the right file.
3. scanDecls (unexported) splits each source into top-level declaration groups without parsing bodies.
4. Runs preRegisterStructTypes to insert placeholder *vm.Type entries for struct type definitions, enabling forward and mutual type references (e.g. type F func(*A); type A struct{F}).
5. Enters the Phase 1 retry loop: each declaration is passed to ParseDecl. Failures with ErrUndefined are retried until convergence; rollback is lightweight (only SymTracker keys are deleted).
6. Returns the remaining declarations (func bodies, var initializers) after running SplitAndSortVarDecls.

importSrc handles import statements by calling ParseAll recursively for the imported package path. It saves/restores both pkgName and includeTests around the recursive call, so the imported package's own package X declaration does not clash with the current one and a test target's _test.go files do not leak into its transitive imports.

Dependencies

• scan/ -- scanner tokens.
• lang/ -- token types, Spec.
• symbol/ -- symbol table, Package.
• vm/ -- Type, Value (for symbol metadata).
• io/fs -- virtual filesystem for imported sources.

Type references carry identity

When the parser resolves a type reference it attaches the resolved *vm.Type to the emitted token (Token.ResolvedType), so the compiler binds it to the type's global slot by identity rather than re-resolving the name against the mutable shared symbol table (the compiler's symAt does no scope walk). Three emit sites attach it: registerType (compound type exprs -- pointers, slices, maps, structs), the Type-kind ident handler in parseExpr (bare named types, including conversions T(x) and method expressions T.M), and zeroInitLocals (var z T). Type assertions and type switches already carried their *vm.Type. The token still carries the name in Str, used for method lookup (which is name-keyed) and as a fallback. See comp and ADR-020.

Generics (monomorphization)

Generic functions and types are supported via compile-time monomorphization. A generic declaration is stored as a token-level template; each use with concrete type arguments produces a specialized copy by textual substitution. No new VM opcodes are needed -- the instantiated code is indistinguishable from hand-written non-generic code.

flowchart LR
    decl["func Max[T any](a,b T) T"] -->|Phase 1| tmpl["genericTemplate\n{name, typeParams, rawTokens}"]
    tmpl -->|"Max[int](...)"| sub["token substitution\nT -> int"]
    sub --> inst["func Max#int(a,b int) int"]
    inst -->|"registerFunc + parseFunc"| code["normal compilation"]

Registration. During Phase 1, registerFunc and parseTypeLine detect a BracketBlock after the name, call parseTypeParamList to extract the parameter names and constraints, and register the symbol with Kind: symbol.Generic. The raw token slice is stored in Symbol.Data as a *genericTemplate. No compilation happens at this point.

parseTypeParamList requires the constraint to start with an identifier (any, comparable, an interface name). This disambiguates generic types from array declarations like type T [3]int where the bracket contains a numeric expression.

Instantiation. When the parser encounters Name[TypeArgs] in an expression (parseExpr) or type context (parseTypeExpr), it resolves the concrete types, calls instantiate to produce a rewritten token stream (substituting type param names, removing the bracket block, renaming to a mangled name like Max#int), and parses the result through the normal function or type path. Already-instantiated combinations are detected by symbol table lookup and skipped.

ensureTypeInstantiated is a convenience wrapper for type templates: it resolves type arguments, instantiates, and registers the concrete type in the symbol table at package scope.

Mangled names. mangledName produces Base#Type1#Type2 strings. These are internal symbol table keys; user code always references the generic name with explicit type arguments.

Generic methods. Methods on generic receivers (func (b Box[T]) Get() T) are supported. registerFunc attaches the method template to the generic type's genericTemplate. ensureTypeInstantiated records every instantiation as a genericInstance{typeArgs, typeArgSources}. When a method is declared after the type has already been instantiated, finalizeGenericMethods (run at the end of ParseAll's Phase 1 retry loop) walks templates x instances x methods and monomorphizes the missing combinations. Output goes to pendingMethodDefs, drained by the first Phase 2 statement.

Inference. inferTypeArgs in generic.go unifies call-site arguments against declared parameter shapes. unifyTypeParam walks compound types (*T, []T, *[]T, map[K]V, chan T, func(...)...) in parallel through the Pointer/Slice/Array/Chan/Map/Func constructors and binds type-param identifiers. A second fixed-point pass (unpackConstraint + extractFromShape) derives missing type parameters by matching already-bound siblings against approximation-constraint shapes (~[]E, ~map[K]V). Range-loop LHS variables have their types populated at parse time via inferRangeTypes, unblocking nested generic calls in for _, v := range s { cmp.Compare(v, ...) }-style loops.

Partial type arguments. A prefix of explicit type args with the rest inferred (Grow[S](nil, n), Equal[M1, M2](a, b)) is supported. inferTypeArgs takes a prefix that seeds the inferred map before unification; the explicit-bracket call sites in expr.go detect a short list followed by a call and fill the trailing params via inferPartialTypeArgs.

Local-var inference. := locals are typed at parse time so a later generic call can infer from them. inferDefineType / inferCallDefineTypes fall back to postfixType on the already-parsed RHS for make/new, slice-expr, and index RHS (not just composite literals). postfixType is pure, so this typing never instantiates -- which is why a :=-bound generic-call RHS no longer regresses source loading. This is what lets slices/maps interpret without explicit-type-arg workarounds (e.g. the former rotateRight[E] mirror patch).

Constraint satisfaction. checkConstraint validates each type argument against its constraint elements (~T approximations, unions, comparable, interface method sets). For an interface constraint, argImplementsIface accepts a type arg by method-set membership: a native type via reflect.Implements, an interpreted concrete type via its registered method symbols, and -- via ifaceContainsMethod -- an interpreted INTERFACE type arg whose own IfaceMethods (set at parse, invisible to reflect and to method symbols) cover the constraint's methods. Constraints are still matched for shape, not enforced as a hard structural type check.

See ADR-011 and ADR-020.

Open questions / TODOs

• Constraint enforcement at instantiation time.
• A few mvm test slices inferences (e.g. AppendSeq([]int{...}, testSeq)) fail only under the in-package file-by-file test compile, not under mvm run; likely a package-load-vs-REPL inference-state difference (see the multi-file package compile TODO).
• Transitive-import alias leak: when slices imports cmp, importing slices creates incidental slices.Ordered, slices.Less aliases pointing to cmp's originals. Harmless but leaky.