match

package
v1.15.0 Latest Latest
Warning

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

 Go to latest Published: May 5, 2026 License: Apache-2.0 Imports: 9 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 (syntax_expand.go)

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 = werr.ErrUnknownOpCode
	// ErrNotAMatch is returned when the input does not match the pattern.
	ErrNotAMatch = werr.ErrNotAMatch
)

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

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 ByteCodeRequireCarEmptyVector added in v1.5.0 

type ByteCodeRequireCarEmptyVector struct{}

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

func (ByteCodeRequireCarEmptyVector) String added in v1.5.0 

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 (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 ByteCodeVisitCarAsVector added in v1.5.0 

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 added in v1.5.0 

func (ByteCodeVisitCarAsVector) String() string

type ByteCodeVisitCdr 

type ByteCodeVisitCdr struct{}

ByteCodeVisitCdr navigates to the cdr of the current pair.

func (ByteCodeVisitCdr) String 

func (ByteCodeVisitCdr) String() string

type CompilePatternOpts added in v1.5.0 

type CompilePatternOpts struct {
	Literals         map[string]struct{}
	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]map[string]struct{}
	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 

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

CompileSyntaxPattern compiles a syntax pattern into bytecode with optional literals and custom ellipsis. Pass nil opts for default behavior.

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 ExpandOptions added in v1.3.0 

type ExpandOptions struct {
	// IntroScope is the hygiene scope added to newly created syntax objects (from the
	// template), but NOT to syntax objects preserved from pattern variable substitution.
	IntroScope *syntax.Scope

	// FreeIds maps free identifier names 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.
	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).

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, meaning the template symbol and pattern variable have exactly the same set of scopes (pattern scopes ⊆ template scopes and template scopes ⊆ pattern scopes). A template symbol with any additional or missing scopes (e.g., from an outer macro's intro scope) is not substituted.

type FreeIdResolver added in v1.10.5 

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.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 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 NewMatcherFullWithDepths added in v1.10.7 

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

NewMatcherFullWithDepths creates a matcher with all parameters including custom ellipsis and compilation-order metadata. The ellipsisDepths parameter maps each ellipsis ID to its compilation order (lower = inner, higher = outer). When nil, order is inferred from the ID values (the compiler assigns IDs sequentially, inner-first).

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

func (p *Matcher) MatchSyntax(ctx context.Context, 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.

Delegates to MatchSyntaxWithLiterals with nil literal arguments, which skips the literal hygiene check in ByteCodeCompareCar.

func (*Matcher) MatchSyntaxWithLiterals 

func (p *Matcher) MatchSyntaxWithLiterals(ctx context.Context, 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 *syntax.SyntaxPair, variables map[string]struct{}) *PatternAnalysis

AnalyzePattern analyzes a pattern and returns analysis results

func AnalyzePatternWithLiterals 

func AnalyzePatternWithLiterals(pattern *syntax.SyntaxPair, 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 *syntax.SyntaxPair) bool

ContainsVariables returns whether a subtree contains pattern variables

func (*PatternAnalysis) GetVariables 

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

GetVariables returns the set of variables in a subtree

func (*PatternAnalysis) Merge added in v1.5.0 

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

Merge incorporates analysis results from another PatternAnalysis. Used when vector patterns are converted to pair chains at compile time, creating fresh SyntaxPair nodes that need analysis entries.

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 

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 *syntax.SyntaxPair) 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,
	opts *SyntaxMatcherOpts,
) *SyntaxMatcher

NewSyntaxMatcher creates a syntax-aware matcher that wraps the core Matcher with hygiene support. Pass nil opts for default behavior (default ellipsis "...", no literal syntax).

The literalSyntax in opts 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.

func (*SyntaxMatcher) Expand 

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

Expand performs template expansion with the given hygiene options. Pass a zero-value ExpandOptions{} for expansion without hygiene.

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(ctx context.Context, 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(ctx context.Context, 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).

type SyntaxMatcherOpts added in v1.5.0 

type SyntaxMatcherOpts struct {
	EllipsisVars   map[int]map[string]struct{}
	EllipsisDepths map[int]int // ellipsisID -> compilation order (lower = inner)
	EllipsisID     string
	LiteralSyntax  map[string]*syntax.SyntaxSymbol
}

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

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.