match

type BindingChecker ¶

type BindingChecker interface {
	// HasBinding checks if sym with the given scopes has a lexical binding.
	// Returns true if the symbol is bound (to a variable, macro, etc.).
	HasBinding(sym string, scopes []*syntax.Scope) bool

	// GetBinding returns the binding for sym with the given scopes.
	// Returns nil if no binding exists. Bindings can be compared for
	// pointer equality to check if two identifiers have the same
	// binding (per R7RS §4.3.2).
	GetBinding(sym string, scopes []*syntax.Scope) *environment.Binding

	// GetLiteralBinding resolves the USE-SITE side of the R7RS §4.3.2 comparison:
	// the frame's own lexical chain at its own phase, then the special-form
	// registry phase, and no other phase. That second probe is what makes
	// auxiliary syntax visible — else and => are registered at PhaseCompile,
	// ambient to every phase, where GetBinding above (the frame's own phase only)
	// reports them unbound. Searching further would let one phase's binding of the
	// name decide another phase's literal. ok is false when resolution was
	// ambiguous.
	GetLiteralBinding(sym string, scopes []*syntax.Scope) (*environment.Binding, bool)
}

BindingChecker is an interface for checking if a symbol has a lexical binding. This is used for R7RS auxiliary syntax hygiene: literals like => and else should not match when the identifier has been locally bound. Implemented by machine/compilation (*envBindingChecker) to avoid circular imports.

type ByteCodeCaptureCar ¶

type ByteCodeCaptureCar struct {
	Binding string
}

ByteCodeCaptureCar captures the current car as a pattern variable binding.

func (p ByteCodeCaptureCar) String() string

type ByteCodeCaptureCdr ¶

type ByteCodeCaptureCdr struct {
	Binding string
}

ByteCodeCaptureCdr captures the current cdr as a pattern variable binding. This is used for improper list patterns like (_ a . rest) where rest should capture the remaining elements of the input list.

R7RS §4.3.2: In a pattern, an identifier followed by . and another identifier matches any input that is a list of one or more elements, binding the first identifier to the first element and the second identifier to the rest of the list.

func (p ByteCodeCaptureCdr) String() string

type ByteCodeCompareCar ¶

type ByteCodeCompareCar struct {
	Value syntax.SyntaxValue
}

ByteCodeCompareCar compares the current car position with a literal syntax value.

func (p ByteCodeCompareCar) String() string

type ByteCodeCompareCdr ¶

type ByteCodeCompareCdr struct {
	Value syntax.SyntaxValue
}

ByteCodeCompareCdr compares the cdr of the current pair with a literal syntax value. This is used for improper list patterns where the tail is a literal, e.g., (a . b) where b is a literal symbol to match exactly.

func (p ByteCodeCompareCdr) String() string

type ByteCodeDiscardCar ¶ added in v1.20.0

type ByteCodeDiscardCar struct{}

ByteCodeDiscardCar asserts that the current position holds an element and matches it without binding.

R7RS §4.3.2: `_` matches any input and never binds. Emitting NOTHING for it was not equivalent to matching it: the element stays visible to Done, whose one-instruction lookahead then reads the following pattern element's bytecode and cannot tell "the pattern ends here" from "the next pattern element is a wildcard". So `((k (y) _) …)` rejected `(d (1) 9)` and, in the other direction, `((k (y) _ _) …)` accepted a two-element input.

The presence assertion is the whole instruction; advancement is the emitted VisitCdr's job, exactly as for a pattern variable's CaptureCar.

func (ByteCodeDiscardCar) String() string

type ByteCodeDiscardCdr ¶ added in v1.19.0

type ByteCodeDiscardCdr struct{}

ByteCodeDiscardCdr consumes the current cdr without binding it.

R7RS §4.3.2: `_` is a wildcard that matches any input but never binds. In a dotted tail (`(_ a . _)`) it must still consume the rest of the input, so the matcher cannot simply emit nothing — that would leave the trailing elements visible to Done, which requires the position to be exhausted.

func (ByteCodeDiscardCdr) String() string

type ByteCodeDone ¶

type ByteCodeDone struct{}

ByteCodeDone signals completion of the current subtree.

func (ByteCodeDone) String() string

type ByteCodeJump ¶

type ByteCodeJump struct {
	Offset int
}

ByteCodeJump performs an unconditional jump by a relative offset. Used for looping back in ellipsis patterns.

func (p ByteCodeJump) String() string

type ByteCodePopContext ¶

type ByteCodePopContext struct {
	EllipsisID int
}

ByteCodePopContext ends the current capture context.

func (p ByteCodePopContext) String() string

type ByteCodePushContext ¶

type ByteCodePushContext struct {
	EllipsisID int
}

ByteCodePushContext starts a new capture context for an ellipsis iteration. EllipsisID identifies which ellipsis pattern this context belongs to, enabling multiple independent ellipsis patterns in the same clause.

func (p ByteCodePushContext) String() string

type ByteCodeRequireCarEmptyVector ¶

type ByteCodeRequireCarEmptyVector struct{}

ByteCodeRequireCarEmptyVector verifies that the car at the current position is an empty SyntaxVector. Used for empty vector patterns #().

func (ByteCodeRequireCarEmptyVector) String() string

type ByteCodeSkipIfEmpty ¶

type ByteCodeSkipIfEmpty struct {
	Offset int
}

ByteCodeSkipIfEmpty implements while-loop semantics for ellipsis patterns.

Problem: Without this, ellipsis patterns use do-while semantics, executing the loop body at least once. This breaks patterns like (foo e1 e2 ...) when matching (foo x) - the e2... part should match zero elements.

Solution: Check if the list is empty BEFORE entering the loop body. If empty, skip forward by Offset instructions to exit the loop.

This is the key fix for zero-iteration ellipsis matching in R7RS.

func (p ByteCodeSkipIfEmpty) String() string

type ByteCodeSkipIfTailCount ¶

type ByteCodeSkipIfTailCount struct {
	Offset int // Instructions to skip forward when exiting loop
	Count  int // Number of elements required for trailing pattern
}

ByteCodeSkipIfTailCount implements ellipsis-in-middle pattern matching.

R7RS §4.3.2 allows patterns like (a ... b c) where the ellipsis is followed by additional pattern elements. This instruction enables matching such patterns by checking if exactly Count elements remain in the list.

Behavior:

• If remaining elements == Count: jump forward by Offset (exit loop, match tail)
• If remaining elements > Count: continue (match more ellipsis iterations)
• If remaining elements < Count: return ErrNotAMatch (not enough for tail)

When Count == 0, this behaves identically to ByteCodeSkipIfEmpty.

func (p ByteCodeSkipIfTailCount) String() string

type ByteCodeVisitCar ¶

type ByteCodeVisitCar struct{}

ByteCodeVisitCar navigates into the car of the current pair.

func (ByteCodeVisitCar) String() string

type ByteCodeVisitCarAsBox ¶ added in v1.20.0

type ByteCodeVisitCarAsBox struct{}

ByteCodeVisitCarAsBox checks that the car of the current pair is a SyntaxBox, wraps its content in a one-element SyntaxPair chain, and pushes the chain onto the syntax stack. A box holds exactly one datum, so `#&<pattern>` matches as the one-element sub-list `(<pattern>)` and every pair opcode applies unchanged.

func (ByteCodeVisitCarAsBox) String() string

type ByteCodeVisitCarAsVector ¶

type ByteCodeVisitCarAsVector struct{}

ByteCodeVisitCarAsVector checks that the car of the current pair is a SyntaxVector, converts its elements to a SyntaxPair chain, and pushes the chain onto the syntax stack. This enables pair-based matching of vector pattern contents per R7RS §4.3.2.

func (ByteCodeVisitCarAsVector) String() string

type ByteCodeVisitCdr ¶

type ByteCodeVisitCdr struct{}

ByteCodeVisitCdr navigates to the cdr of the current pair.

func (ByteCodeVisitCdr) String() string

type CompilePatternOpts ¶

type CompilePatternOpts struct {
	Literals         values.StringSet
	EllipsisID       string
	MatchAllElements bool // false (default): skip first element (R7RS syntax-rules macro keyword); true: match all elements (syntax-case)
}

CompilePatternOpts holds optional parameters for CompileSyntaxPattern. A nil opts pointer means all defaults (no literals, default "...").

type CompiledPattern ¶

type CompiledPattern struct {
	Codes          []SyntaxCommand
	EllipsisVars   map[int]values.StringSet
	EllipsisDepths map[int]int // ellipsisID -> compilation order (lower = inner)
	EllipsisID     string      // The ellipsis identifier used during compilation
}

CompiledPattern contains the compiled bytecode and ellipsis variable mapping.

func CompileSyntaxPattern(
	ctx context.Context,
	pattern syntax.SyntaxValue,
	variables values.StringSet,
	opts *CompilePatternOpts,
) (*CompiledPattern, error)

type ExpandOptions ¶

type ExpandOptions struct {
	// IntroScope is the hygiene scope added to template-introduced symbols. It is
	// not added to newly created pairs or vectors (those carry only a source
	// context), nor to symbols preserved from pattern variable substitution, nor
	// to symbols resolved to a definition-site local binding.
	IntroScope *syntax.Scope

	// FreeIds maps free identifiers to their pre-resolved bindings. A non-nil
	// value carries resolved binding info from macro definition time (local
	// scopes, global index, library scope). A nil value is treated the same as an
	// absent key — the identifier receives the intro scope normally.
	//
	// Keyed by FreeIdKey (name + scope fingerprint), NOT by bare name: one clause
	// template can hold two same-named free identifiers under different scope sets
	// (a macro-generating macro splices the name in from two scope sources), and
	// each resolves to its own binding. A bare-name key let the second collapse
	// onto the first. The collector writes each occurrence under its own key; this
	// map reads back under the template symbol's own scope set at expansion.
	FreeIds map[string]FreeIdResolver

	// UseSiteCtx, if provided, is used for the source context of newly created syntax
	// objects instead of the template's context. This allows error messages to point to
	// where the macro was invoked rather than where it was defined.
	UseSiteCtx *syntax.SourceContext

	// Origin tracks the macro expansion chain for debugging and error reporting.
	// WithOrigin replaces (not appends to) a SourceContext's Origin field, so the
	// last expansion pass wins. This is correct because the caller constructs the
	// OriginInfo with the full chain: it reads the previous SourceContext.Origin and
	// sets it as Parent on the new OriginInfo before calling Expand. The chain lives
	// inside OriginInfo.Parent, not across successive SourceContext.Origin values.
	//
	// The nil guard at each call site skips when no origin is provided — avoiding a
	// pointless allocation and preserving any existing origin on the SourceContext
	// (e.g., syntax-case expands with ExpandOptions{}, where Origin is nil).
	Origin *syntax.OriginInfo

	// PatternVarSyntax contains the syntax symbols from the pattern, enabling nested
	// macro hygiene via scope comparison. When set, template symbols are only substituted
	// if their scopes match the corresponding pattern variable's scopes.
	PatternVarSyntax map[string]*syntax.SyntaxSymbol
}

ExpandOptions holds the hygiene and source-tracking parameters for template expansion. All fields are optional; the zero value expands without hygiene (useful for testing).

Whether a template symbol is replaced by a capture is decided by TemplateDenotesPatternVariable over PatternVarSyntax; see that function for the rule and for why plain subset resolution is sufficient.

type FreeIdResolver ¶

type FreeIdResolver interface {
	GetLocalScopes() []*syntax.Scope
	GetGlobal() *environment.GlobalIndex
	GetHasLocalBinding() bool
	GetLibraryScope() *syntax.Scope
}

FreeIdResolver provides free identifier resolution information for template expansion hygiene. Implemented by machine/compilation.FreeIdResolution.

In ExpandOptions.FreeIds, a non-nil FreeIdResolver carries binding information from macro definition time. A nil map value is treated the same as an absent key (the identifier receives the intro scope). Methods return zero values when that aspect of resolution is absent.

type LiteralMatcher ¶

type LiteralMatcher func(inputSym *syntax.SyntaxSymbol, patternLiteralKey string) bool

LiteralMatcher is a function that checks if an input symbol matches a pattern literal. Returns true if the input should match, false if it's shadowed and should not match.

type LiteralPin ¶ added in v1.20.0

type LiteralPin struct {
	Binding   *environment.Binding
	Ambiguous bool
}

LiteralPin is the DEFINITION-site resolution of one pattern literal, captured when the syntax-rules or syntax-case form was compiled.

R7RS §4.3.2 compares the literal's binding at the macro DEFINITION site with the input identifier's binding at the USE site. Resolving both sides through the one use-site environment answers neither question for a zero-scoped global: a top-level (define else #f) made after the macro was defined is visible from the definition frame too (both reach one owner store), so the two sides resolve to the identical *Binding and the comparison is vacuous. Only a definition-TIME snapshot discriminates.

The zero value is deliberately NOT a pin. A nil Binding with Ambiguous false means "unbound at definition time", which is R7RS's "the two identifiers are the same and both have no lexical binding" arm, and must leave the use-site-only comparison verbatim — the pin tightens, it never loosens. Ambiguous records an ErrAmbiguousBinding tie at definition time; a scope-aware lookup has three answers, and for this consumer the conservative one is "the literal does not match".

type Matcher ¶

type Matcher struct {
	// contains filtered or unexported fields
}

Matcher is the pattern matching VM for syntax-rules.

It executes compiled pattern bytecode against an input form, capturing pattern variable bindings that can be used for template expansion.

func NewMatcher(variables values.StringSet, codes []SyntaxCommand, opts ...MatcherOption) *Matcher

func (p *Matcher) GetBindings() map[string]syntax.SyntaxValue

func (p *Matcher) MatchSyntax(ctx context.Context, target *syntax.SyntaxPair) error

func (p *Matcher) MatchSyntaxWithLiterals(ctx context.Context, target *syntax.SyntaxPair, literalSyntax map[string]*syntax.SyntaxSymbol, literalMatcher LiteralMatcher) error

type MatcherOption ¶

type MatcherOption func(*Matcher)

MatcherOption configures a Matcher at construction time. Pass options to NewMatcher; later options override earlier ones if they touch the same field.

func WithEllipsisDepths(d map[int]int) MatcherOption

func WithEllipsisID(id string) MatcherOption

func WithEllipsisVars(v map[int]values.StringSet) MatcherOption

type PatternAnalysis ¶

type PatternAnalysis struct {
	// contains filtered or unexported fields
}

PatternAnalysis holds analysis results for a pattern

func AnalyzePattern(pattern *syntax.SyntaxPair, variables values.StringSet) *PatternAnalysis

func NewPatternAnalysis() *PatternAnalysis

func (p *PatternAnalysis) ContainsVariables(pair *syntax.SyntaxPair) bool

func (p *PatternAnalysis) GetVariables(pair *syntax.SyntaxPair) values.StringSet

func (p *PatternAnalysis) Merge(other *PatternAnalysis)

type SyntaxCommand ¶

type SyntaxCommand interface {
	fmt.Stringer
}

SyntaxCommand represents a pattern bytecode instruction.

type SyntaxCompiler ¶

type SyntaxCompiler struct {
	// contains filtered or unexported fields
}

SyntaxCompiler compiles pattern syntax into bytecode.

func NewSyntaxCompiler() *SyntaxCompiler

func NewSyntaxCompilerWithEllipsis(ellipsis string) *SyntaxCompiler

func (p *SyntaxCompiler) Compile(ctx context.Context, pr *syntax.SyntaxPair) error

func (p *SyntaxCompiler) SetSkipMacroKeyword(skip bool)

type SyntaxMatcher ¶

type SyntaxMatcher struct {
	// contains filtered or unexported fields
}

SyntaxMatcher adapts the core Matcher to work with syntax objects and hygiene.

It provides:

• Syntax-native pattern matching with source location preservation
• Template expansion with hygiene (intro scope for newly created syntax)
• Literal hygiene checking for R7RS auxiliary syntax

Key features:

Pattern Variable Capture: Pattern variables are captured directly as syntax.SyntaxValue, preserving source context through the entire match. No conversion to raw values is needed - the Matcher's MatchSyntaxWithLiterals operates on SyntaxPair directly.

Literal Hygiene: The literalSyntax map stores pattern literals with their scopes. During matching, if an input symbol has a literal's name but incompatible scopes (e.g., shadowed by let), it won't match the literal. This implements R7RS's requirement that auxiliary syntax like => and else be treated as regular expressions when locally shadowed.

R7RS Binding Check: For full R7RS compliance (§4.3.2), the input identifier's binding is compared with the pattern literal's. WHICH binding stands for the literal depends on literalDefs, the definition-site pins:

• Pinned (the primary path — every syntax-rules/syntax-case form with literals compiled against a non-nil env): the pattern literal is never resolved at match time. pin.Binding, captured when the macro was compiled, is compared against a phase-scoped use-site resolution. An Ambiguous pin refuses the literal outright, before any checker is consulted.
• Unpinned (a literal unbound at definition time, or no env): both sides are resolved through the use-site checker, which is the pre-pin behaviour and is left verbatim so the pin only ever tightens.

The checker can arrive two ways, and both are read-only after construction: on the opts struct, for a matcher built per invocation (syntax-case, whose clause is matched in the environment it was compiled against), or as MatchWithBindingChecker's argument, for a matcher compiled once at macro-definition time and matched against a different use-site environment each expansion (syntax-rules). Match() supplies no per-call checker and falls back to the opts one — that fallback is how syntax-case gets its checker at all. With a checker in neither position the binding comparison is skipped, but an Ambiguous pin still refuses the literal.

func NewSyntaxMatcher(
	variables values.StringSet,
	codes []SyntaxCommand,
	opts *SyntaxMatcherOpts,
) *SyntaxMatcher

func (p *SyntaxMatcher) CloneForMatch() *SyntaxMatcher

func (p *SyntaxMatcher) Expand(template syntax.SyntaxValue, opts ExpandOptions) (syntax.SyntaxValue, error)

func (p *SyntaxMatcher) GetBindings() map[string]syntax.SyntaxValue

func (p *SyntaxMatcher) Match(ctx context.Context, input syntax.SyntaxValue) error

func (p *SyntaxMatcher) MatchWithBindingChecker(ctx context.Context, input syntax.SyntaxValue, checker BindingChecker) error

type SyntaxMatcherOpts ¶

type SyntaxMatcherOpts struct {
	EllipsisVars   map[int]values.StringSet
	EllipsisDepths map[int]int // ellipsisID -> compilation order (lower = inner)
	EllipsisID     string
	LiteralSyntax  map[string]*syntax.SyntaxSymbol
	// LiteralDefs pins each pattern literal to its definition-site binding. It is
	// optional and tightening-only: an absent or zero LiteralPin leaves the
	// use-site-only comparison in place.
	LiteralDefs map[string]LiteralPin
	// BindingChecker resolves an identifier to its binding for the R7RS §4.3.2
	// literal check. Pair it with LiteralSyntax: the check needs both, and a
	// nil in either position turns it off.
	BindingChecker BindingChecker
}

SyntaxMatcherOpts holds optional parameters for NewSyntaxMatcher. A nil opts pointer means all defaults (no ellipsis vars, default "...", no literals).