match

package
v1.0.4 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 6, 2026 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Overview

Package match implements the pattern matching engine for syntax-rules and syntax-case.

The package provides three layers:

Pattern Compiler

SyntaxCompiler compiles pattern S-expressions into bytecode at macro definition time. Bytecode instructions handle literal matching, variable capture, and ellipsis repetition.

Matching VM

Matcher executes bytecode against input forms at macro invocation time, capturing pattern variable bindings. The VM uses two stacks:

  • Value stack: tracks position in the input tree
  • Capture stack: tracks captured bindings with nesting for ellipsis

Syntax Adapter

SyntaxMatcher adds hygiene: scope-aware literal matching and template expansion with intro scopes per Flatt's "sets of scopes" model.

Template Expansion

Reference: R7RS Section 4.3.2 (syntax-rules pattern language).

Index

Constants

View Source 
const DefaultEllipsis = "..."

DefaultEllipsis is the standard R7RS ellipsis identifier.

Variables

View Source 
var (
	// ErrUnknownOpCode is returned when an unknown bytecode is encountered.
	ErrUnknownOpCode = errors.New("unknown op code")
	// ErrNotAMatch is returned when the input does not match the pattern.
	ErrNotAMatch = errors.New("not a match")
)

Functions

This section is empty.

Types

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. The returned value is opaque but
	// can be compared for equality to check if two identifiers have the
	// same binding (per R7RS §4.3.2).
	GetBinding(sym string, scopes []*syntax.Scope) any
}

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 package to avoid circular imports.

type ByteCodeCaptureCar 

type ByteCodeCaptureCar struct {
	Binding string
}

ByteCodeCaptureCar captures the current car as a pattern variable binding.

func (ByteCodeCaptureCar) String 

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 (ByteCodeCaptureCdr) String 

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 (ByteCodeCompareCar) String 

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 (ByteCodeCompareCdr) String 

func (p ByteCodeCompareCdr) String() string

type ByteCodeDone 

type ByteCodeDone struct{}

ByteCodeDone signals completion of the current subtree.

func (ByteCodeDone) String 

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 (ByteCodeJump) String 

func (p ByteCodeJump) String() string

type ByteCodePopContext 

type ByteCodePopContext struct {
	EllipsisID int
}

ByteCodePopContext ends the current capture context.

func (ByteCodePopContext) String 

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 (ByteCodePushContext) String 

func (p ByteCodePushContext) String() string

type ByteCodeRequireCarEmpty 

type ByteCodeRequireCarEmpty struct{}

ByteCodeRequireCarEmpty verifies that the car at the current position is an empty list.

Problem: Pattern () should only match input (). Without this check, VisitCar + Done would match any list, because Done only checks that CDR is empty.

Solution: Generate this instruction instead of VisitCar when the pattern element is (). It verifies the input car is also empty before proceeding.

func (ByteCodeRequireCarEmpty) String 

func (p ByteCodeRequireCarEmpty) 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 (ByteCodeSkipIfEmpty) String 

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 (ByteCodeSkipIfTailCount) String 

func (p ByteCodeSkipIfTailCount) String() string

type ByteCodeVisitCar 

type ByteCodeVisitCar struct{}

ByteCodeVisitCar navigates into the car of the current pair.

func (ByteCodeVisitCar) String 

func (ByteCodeVisitCar) String() string

type ByteCodeVisitCdr 

type ByteCodeVisitCdr struct{}

ByteCodeVisitCdr navigates to the cdr of the current pair.

func (ByteCodeVisitCdr) String 

func (ByteCodeVisitCdr) String() string

type CompiledPattern 

type CompiledPattern struct {
	Codes        []SyntaxCommand
	EllipsisVars map[int]map[string]struct{}
	EllipsisID   string // The ellipsis identifier used during compilation
}

CompiledPattern contains the compiled bytecode and ellipsis variable mapping.

func CompileSyntaxPatternFull 

func CompileSyntaxPatternFull(ctx context.Context, pattern syntax.SyntaxValue, variables map[string]struct{}) (*CompiledPattern, error)

CompileSyntaxPatternFull compiles a syntax pattern into bytecode with ellipsis variable mapping. Returns a CompiledPattern containing both the bytecode and the ellipsis variable mapping. Uses the default ellipsis identifier ("...").

func CompileSyntaxPatternWithEllipsis 

func CompileSyntaxPatternWithEllipsis(ctx context.Context, pattern syntax.SyntaxValue, variables map[string]struct{}, ellipsisID string) (*CompiledPattern, error)

CompileSyntaxPatternWithEllipsis compiles a syntax pattern into bytecode with a custom ellipsis. The ellipsisID parameter specifies the identifier used for ellipsis patterns (default is "..." per R7RS, but can be customized per R7RS §4.3.2).

func CompileSyntaxPatternWithLiterals 

func CompileSyntaxPatternWithLiterals(ctx context.Context, pattern syntax.SyntaxValue, variables map[string]struct{}, literals map[string]struct{}, ellipsisID string) (*CompiledPattern, error)

CompileSyntaxPatternWithLiterals compiles a syntax pattern into bytecode with literals and custom ellipsis. The literals parameter contains identifiers that should be matched literally (not as pattern variables). The ellipsisID parameter specifies the identifier used for ellipsis patterns. R7RS §4.3.2: The first subform of each pattern is the keyword of the macro being transformed; it is not matched against the macro use being transformed.

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 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 

func NewMatcher(variables map[string]struct{}, codes []SyntaxCommand) *Matcher

NewMatcher creates a new pattern matcher with the default ellipsis ("...").

func NewMatcherFull 

func NewMatcherFull(variables map[string]struct{}, codes []SyntaxCommand, ellipsisVars map[int]map[string]struct{}, ellipsisID string) *Matcher

NewMatcherFull creates a matcher with all parameters including custom ellipsis. The ellipsisID parameter specifies the identifier used for ellipsis patterns (default is "..." per R7RS, but can be customized per R7RS §4.3.2).

func NewMatcherWithEllipsisVars 

func NewMatcherWithEllipsisVars(variables map[string]struct{}, codes []SyntaxCommand, ellipsisVars map[int]map[string]struct{}) *Matcher

NewMatcherWithEllipsisVars creates a matcher with ellipsis variable mapping. The ellipsisVars parameter maps each ellipsis ID to its captured pattern variables. Uses the default ellipsis identifier ("...").

func (*Matcher) Expand 

func (p *Matcher) Expand(template values.Value) (values.Value, error)

Expand substitutes pattern variables in template with captured values. This is the legacy API that returns unwrapped values.Value.

func (*Matcher) ExpandPreservingSyntax 

func (p *Matcher) ExpandPreservingSyntax(template values.Value) (values.Value, error)

ExpandPreservingSyntax substitutes pattern variables in template with captured values, but preserves syntax values in the result. This allows callers to maintain syntax context for captured pattern variables.

func (*Matcher) GetBindings 

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

GetBindings returns the captured pattern variable bindings from the last match. Bindings are stored as syntax.SyntaxValue to preserve source context. Returns nil if no match has been performed.

func (*Matcher) Match 

func (p *Matcher) Match(target *values.Pair) error

Match runs the pattern matcher against the target using values-based matching. Captured values are wrapped in syntax objects for uniform bindings storage.

func (*Matcher) MatchSyntax 

func (p *Matcher) MatchSyntax(target *syntax.SyntaxPair) error

MatchSyntax runs the pattern matcher against the syntax target. This is the syntax-native entry point that operates directly on SyntaxPair. Captured values are stored as syntax.SyntaxValue to preserve source context.

func (*Matcher) MatchSyntaxWithLiterals 

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

MatchSyntaxWithLiterals runs the pattern matcher with literal hygiene checking. The literalSyntax map contains pattern literals that need scope/binding checking. The literalMatcher function is called for each literal comparison to check if the input symbol should match (returns true) or is shadowed (returns false).

type PatternAnalysis 

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

PatternAnalysis holds analysis results for a pattern

func AnalyzePattern 

func AnalyzePattern(pattern *values.Pair, variables map[string]struct{}) *PatternAnalysis

AnalyzePattern analyzes a pattern and returns analysis results

func AnalyzePatternWithLiterals 

func AnalyzePatternWithLiterals(pattern *values.Pair, literals map[string]struct{}, isKeyword bool) *PatternAnalysis

AnalyzePatternWithLiterals analyzes a pattern determining variables from literals

func NewPatternAnalysis 

func NewPatternAnalysis() *PatternAnalysis

NewPatternAnalysis creates a new pattern analysis

func (*PatternAnalysis) ContainsVariables 

func (p *PatternAnalysis) ContainsVariables(pair *values.Pair) bool

ContainsVariables returns whether a subtree contains pattern variables

func (*PatternAnalysis) GetVariables 

func (p *PatternAnalysis) GetVariables(pair *values.Pair) map[string]struct{}

GetVariables returns the set of variables in a subtree

type SyntaxCommand 

type SyntaxCommand interface {
	fmt.Stringer
}

SyntaxCommand represents a pattern bytecode instruction.

func CompileSyntaxPattern 

func CompileSyntaxPattern(ctx context.Context, pattern syntax.SyntaxValue, variables map[string]struct{}) ([]SyntaxCommand, error)

CompileSyntaxPattern compiles a syntax pattern into bytecode. This is a convenience function that unwraps syntax before compilation. Uses the default ellipsis identifier ("...").

type SyntaxCompiler 

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

SyntaxCompiler compiles pattern syntax into bytecode.

func NewSyntaxCompiler 

func NewSyntaxCompiler() *SyntaxCompiler

NewSyntaxCompiler creates a new syntax compiler with the default ellipsis ("...").

func NewSyntaxCompilerWithEllipsis 

func NewSyntaxCompilerWithEllipsis(ellipsis string) *SyntaxCompiler

NewSyntaxCompilerWithEllipsis creates a new syntax compiler with a custom ellipsis identifier. Per R7RS §4.3.2, syntax-rules can specify an alternative ellipsis identifier.

func (*SyntaxCompiler) Compile 

func (p *SyntaxCompiler) Compile(ctx context.Context, pr *values.Pair) error

Compile compiles a pattern pair into bytecode.

func (*SyntaxCompiler) SetSkipMacroKeyword 

func (p *SyntaxCompiler) SetSkipMacroKeyword(skip bool)

SetSkipMacroKeyword enables or disables skipping the first pattern element as a macro keyword. R7RS §4.3.2: The first subform of each syntax-rules pattern is the keyword of the macro being transformed; it is not matched against the macro use. Call this with true when compiling syntax-rules patterns.

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), we also check if the input identifier has a lexical binding. If it does and the pattern literal doesn't, they don't match. This is handled via the bindingChecker field set during Match().

func NewSyntaxMatcher 

func NewSyntaxMatcher(variables map[string]struct{}, codes []SyntaxCommand) *SyntaxMatcher

NewSyntaxMatcher creates a new syntax-aware matcher with default ellipsis ("...").

func NewSyntaxMatcherFull 

func NewSyntaxMatcherFull(variables map[string]struct{}, codes []SyntaxCommand, ellipsisVars map[int]map[string]struct{}, ellipsisID string) *SyntaxMatcher

NewSyntaxMatcherFull creates a syntax-aware matcher with all parameters including custom ellipsis. The ellipsisID parameter specifies the identifier used for ellipsis patterns (default is "..." per R7RS, but can be customized per R7RS §4.3.2).

func NewSyntaxMatcherWithEllipsisVars 

func NewSyntaxMatcherWithEllipsisVars(variables map[string]struct{}, codes []SyntaxCommand, ellipsisVars map[int]map[string]struct{}) *SyntaxMatcher

NewSyntaxMatcherWithEllipsisVars creates a syntax-aware matcher with ellipsis variable mapping. The ellipsisVars parameter maps each ellipsis ID to its captured pattern variables. Uses the default ellipsis identifier ("...").

func NewSyntaxMatcherWithLiterals 

func NewSyntaxMatcherWithLiterals(
	variables map[string]struct{},
	codes []SyntaxCommand,
	ellipsisVars map[int]map[string]struct{},
	ellipsisID string,
	literalSyntax map[string]*syntax.SyntaxSymbol,
) *SyntaxMatcher

NewSyntaxMatcherWithLiterals creates a syntax-aware matcher with literal syntax for hygiene. The literalSyntax parameter maps literal names to their syntax symbols from the pattern. This enables scope-aware literal matching: if an input symbol has a literal's name but has been shadowed (has additional scopes), it won't match the pattern literal. R7RS §4.3.2 requires this for auxiliary syntax like => and else in cond/case.

func (*SyntaxMatcher) Expand 

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

Expand performs template expansion, preserving syntax wrappers

func (*SyntaxMatcher) ExpandWithIntroScope 

func (p *SyntaxMatcher) ExpandWithIntroScope(template syntax.SyntaxValue, introScope *syntax.Scope, freeIds map[string]any) (syntax.SyntaxValue, error)

ExpandWithIntroScope performs template expansion with hygiene support. The introScope is added to newly created syntax objects (from the template), but NOT to syntax objects preserved from pattern variable substitution. The freeIds map contains identifiers that should not receive the intro scope. Values in the map are pre-resolved bindings (nil means just skip intro scope).

func (*SyntaxMatcher) ExpandWithOrigin 

func (p *SyntaxMatcher) ExpandWithOrigin(template syntax.SyntaxValue, introScope *syntax.Scope, freeIds map[string]any, useSiteCtx *syntax.SourceContext, origin *syntax.OriginInfo) (syntax.SyntaxValue, error)

ExpandWithOrigin performs template expansion with full hygiene and origin tracking. Parameters:

  • template: The template to expand
  • introScope: Hygiene scope added to newly created syntax (not pattern variables)
  • freeIds: Map of free identifier names to their pre-resolved bindings (any type to avoid circular imports)
  • useSiteCtx: Source context for newly created syntax (use-site vs template-site)
  • origin: Origin info for tracking macro expansion chains

func (*SyntaxMatcher) ExpandWithPatternVarSyntax 

func (p *SyntaxMatcher) ExpandWithPatternVarSyntax(
	template syntax.SyntaxValue,
	introScope *syntax.Scope,
	freeIds map[string]any,
	useSiteCtx *syntax.SourceContext,
	origin *syntax.OriginInfo,
	patternVarSyntax map[string]*syntax.SyntaxSymbol,
) (syntax.SyntaxValue, error)

ExpandWithPatternVarSyntax performs template expansion with full nested macro hygiene. This is the scope-aware expansion that correctly handles the case where an outer macro introduces a symbol into an inner macro's template. The patternVarSyntax map contains the syntax symbols from the pattern, allowing scope comparison during substitution.

Per Flatt 2016 "sets of scopes" model: when deciding whether to substitute a template symbol with a captured value, we compare the template symbol's scopes with the pattern variable's scopes. Only substitute if the scopes are compatible (pattern var scopes ⊆ template symbol scopes). If the template symbol has additional scopes (e.g., from an outer macro's intro scope), it should NOT be substituted.

Example: When outer macro `foo` expands `(foo bar x)` producing: 

(define-syntax bar (syntax-rules () ((bar x) 'x)))

The pattern's `x` has scopes from the outer expansion (S_outer), while the template's `'x` was substituted from the input and has use-site scopes. When `bar` is compiled, both `x` symbols have different scopes, so template `'x` should NOT be substituted when inner macro expands.

func (*SyntaxMatcher) ExpandWithUseSite 

func (p *SyntaxMatcher) ExpandWithUseSite(template syntax.SyntaxValue, introScope *syntax.Scope, freeIds map[string]any, useSiteCtx *syntax.SourceContext) (syntax.SyntaxValue, error)

ExpandWithUseSite performs template expansion with hygiene support and use-site tracking. The introScope is added to newly created syntax objects (from the template), but NOT to syntax objects preserved from pattern variable substitution. The freeIds map contains identifiers that should not receive the intro scope. Values in the map are pre-resolved bindings (nil means just skip intro scope). The 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.

func (*SyntaxMatcher) GetBindings 

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

GetBindings returns the captured pattern variable bindings from the last match. Bindings are now stored as syntax.SyntaxValue directly, preserving source context. This is used by syntax-case to bind pattern variables in the body's environment.

func (*SyntaxMatcher) Match 

func (p *SyntaxMatcher) Match(input syntax.SyntaxValue) error

Match performs pattern matching on syntax objects. This is the basic method without binding checking. For full R7RS compliance with auxiliary syntax hygiene, use MatchWithBindingChecker instead.

func (*SyntaxMatcher) MatchWithBindingChecker 

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

MatchWithBindingChecker performs pattern matching on syntax objects with R7RS-compliant auxiliary syntax hygiene.

The checker parameter enables R7RS §4.3.2 compliant literal matching: literals match only if both identifiers have the same lexical binding, or both have no lexical binding. If the input has a binding (from let, lambda, etc.) but the pattern literal doesn't, they won't match.

Pass nil for checker to use scope-based matching only (less strict).

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.