compiler

package
v0.15.1 Latest Latest
Warning

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

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

Documentation

Overview

Package compiler provides route compilation for the Rivaas router.

The compiler package implements a route matching system through pre-compiled route tables. It improves routing by:

  • Pre-computing route structure information
  • Using bloom filters for negative lookups
  • Building first-segment indexes for route narrowing
  • Enabling single-pass validation and parameter extraction

Architecture

The compiler uses a three-tier strategy for route matching:

  1. Static routes: Hash table lookup
  2. Dynamic routes: Pre-compiled patterns with segment-based matching
  3. Complex routes: Tree fallback

This hybrid approach handles the most common cases while maintaining correctness for complex routing scenarios.

Route Compilation

Routes are compiled through the CompileRoute function, which:

  1. Analyzes route structure (static/dynamic/wildcard segments)
  2. Counts segments for length validation
  3. Stores parameter positions for extraction
  4. Attaches constraint patterns for validation
  5. Computes specificity score for sorting

Example: 

route := compiler.CompileRoute(
    "GET",
    "/api/users/:id/posts/:pid",
    handlers,
    []compiler.RouteConstraint{
        {Param: "id", Pattern: regexp.MustCompile(`^\d+$`)},
        {Param: "pid", Pattern: regexp.MustCompile(`^\d+$`)},
    },
)

Bloom Filter

The bloom filter provides negative lookups for static routes:

  • Membership tests
  • Zero false negatives (if not in bloom filter, definitely not in routes)
  • Rare false positives (< 1% with proper sizing)
  • Checks

The bloom filter eliminates map lookups for non-existent routes.

First-Segment Index

The first-segment index groups dynamic routes by their first static segment: 

/users/:id        -> index["users"]
/posts/:pid       -> index["posts"]
/api/:resource    -> index["api"]

This approach:

  • Reduces candidate routes for typical workloads
  • Enables route narrowing before pattern matching
  • Lazy-initializes on first dynamic route match
  • Only indexes ASCII segments (non-ASCII routes skip indexing)

Lookup Details

Implementation:

  • Static routes: Hash table lookup
  • Dynamic routes: Segment-based matching
  • Bloom filter size depends on route count

Typical behavior:

  • Static lookup: Hash table lookup
  • Dynamic match: Segment-based matching
  • Constrained match: Pattern validation with matching

Design Decisions

## ASCII-Only First-Segment Index

The first-segment index only handles ASCII characters for simplicity:

  • Avoids UTF-8 decoding in hot path
  • Simplifies case-insensitive comparisons (single tolower operation)
  • Non-ASCII routes fall back to linear scan (acceptable trade-off)
  • Most web APIs use ASCII paths anyway

## Import Cycle Prevention

The compiler package is designed to avoid import cycles with the router package:

  • Defines its own HandlerFunc type (function, not interface)
  • Uses []HandlerFunc instead of HandlerChain
  • Defines minimal RouteConstraint type
  • No dependencies on router internals

This allows the router package to import compiler without circular dependencies.

## Storage

Compiled routes store minimal metadata:

  • Fixed-size arrays for parameter positions (max 8 params)
  • String slices are shared, not copied
  • Constraints stored as slice of structs (not pointers)
  • Handler functions shared across router and compiler

Thread Safety

All operations are thread-safe:

  • RouteCompiler uses RWMutex for concurrent access
  • Bloom filter is read-only after initialization
  • First-segment index uses sync.Once for lazy initialization
  • Route compilation is a pure function

Concurrent reads (route matching) do not block each other. Route additions (compilation) are synchronized with a mutex.

Usage Example

Basic usage in the router: 

// Initialize compiler
rc := compiler.NewRouteCompiler(1000, 3) // 1000 routes, 3 hash funcs

// Register routes
r.GET("/users/:id", handler)
r.GET("/posts/:pid", handler)

// Compile routes (called by router.Warmup)
rc.CompileAllRoutes()

// Route matching (called by router.ServeHTTP)
if route := rc.LookupStatic("GET", "/users"); route != nil {
    // Found static route
}

params := make(map[string]string)
if route := rc.MatchDynamic("GET", "/users/123", params); route != nil {
    // Found dynamic route, params["id"] = "123"
}

See Also

  • bloom.go: Bloom filter implementation for negative lookups
  • static.go: Static route compilation and lookup
  • dynamic.go: Dynamic route compilation and matching
  • compiler.go: Main RouteCompiler and route compilation logic

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BloomFilter 

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

BloomFilter provides a simple bloom filter implementation for negative lookups. A bloom filter is a probabilistic data structure that can tell you: - "Definitely NOT in the set" (100% accurate) - "Possibly in the set" (may have false positives)

Use case in routing: Filter out paths that definitely don't exist before checking the route map.

How it works: 1. Hash the input with multiple hash functions (using different seeds) 2. Set bits at the hash positions when adding elements 3. Check if all bits are set when testing membership 4. If any bit is unset → element definitely not in set (true negative) 5. If all bits are set → element might be in set (check actual map)

Uses multiple hash functions (typically 3) Uses bit array for compact storage

Implementation using FNV-1a hash with different seeds

func NewBloomFilter 

func NewBloomFilter(size uint64, numHashFuncs int) *BloomFilter

NewBloomFilter creates a new bloom filter with the specified size and hash functions. Uses FNV-1a hash with different seeds.

Example

ExampleNewBloomFilter demonstrates creating and using a bloom filter. 

package main

import (
	"fmt"

	"rivaas.dev/router/compiler"
)

func main() {
	// Create a bloom filter with size 1000 and 3 hash functions
	bf := compiler.NewBloomFilter(1000, 3)

	// Add items to the filter
	bf.Add([]byte("GET/users"))
	bf.Add([]byte("GET/posts"))

	// Test membership
	if bf.Test([]byte("GET/users")) {
		fmt.Println("GET/users: possibly in set")
	}

	if !bf.Test([]byte("GET/comments")) {
		fmt.Println("GET/comments: definitely not in set")
	}
}

Output:
GET/users: possibly in set
GET/comments: definitely not in set

func (*BloomFilter) Add 

func (bf *BloomFilter) Add(data []byte)

Add adds an element to the bloom filter

func (*BloomFilter) Test 

func (bf *BloomFilter) Test(data []byte) bool

Test checks if an element might be in the bloom filter

Uses early-exit loop for handling of miss cases (common in routing). Bloom filters are most valuable when they can reject non-existent routes, so early exit on first failed bit check is important.

func (*BloomFilter) TestWithPrecomputedHash added in v0.4.0 

func (bf *BloomFilter) TestWithPrecomputedHash(baseHash uint64) bool

TestWithPrecomputedHash checks if an element might be in the bloom filter using a pre-computed FNV-1a hash. This avoids recomputing the hash when the caller has already computed it.

Uses early-exit loop for handling of miss cases (common in routing).

type CompiledRoute 

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

CompiledRoute represents a pre-compiled route with metadata for matching. It pre-computes route structure information during registration, including segment positions, parameter names, and constraint patterns.

func CompileRoute 

func CompileRoute(method, pattern string, handlers []HandlerFunc, constraints []RouteConstraint) *CompiledRoute

CompileRoute compiles a route pattern into a compiled route for matching. It pre-computes route structure information during registration, including segment positions, parameter names, and constraint patterns.

Example

ExampleCompileRoute demonstrates compiling a simple static route. 

package main

import (
	"fmt"

	"rivaas.dev/router/compiler"
)

func main() {
	// Compile a static route (no parameters)
	route := compiler.CompileRoute("GET", "/api/users", nil, nil)

	fmt.Println("Pattern:", route.Pattern())
	fmt.Println("Method:", route.Method())
}

Output:
Pattern: /api/users
Method: GET
Example (WithConstraints)

ExampleCompileRoute_withConstraints demonstrates compiling a route with parameter constraints. 

package main

import (
	"fmt"
	"regexp"

	"rivaas.dev/router/compiler"
)

func main() {
	// Define constraints for parameters
	constraints := []compiler.RouteConstraint{
		{Param: "id", Pattern: regexp.MustCompile(`^\d+$`)},  // id must be numeric
		{Param: "pid", Pattern: regexp.MustCompile(`^\d+$`)}, // pid must be numeric
	}

	// Compile route with constraints
	route := compiler.CompileRoute("GET", "/users/:id/posts/:pid", nil, constraints)

	fmt.Println("Pattern:", route.Pattern())
	fmt.Println("Method:", route.Method())
}

Output:
Pattern: /users/:id/posts/:pid
Method: GET
Example (WithParameters)

ExampleCompileRoute_withParameters demonstrates compiling a route with parameters. 

package main

import (
	"fmt"

	"rivaas.dev/router/compiler"
)

func main() {
	// Compile a route with URL parameters
	route := compiler.CompileRoute("GET", "/users/:id/posts/:pid", nil, nil)

	fmt.Println("Pattern:", route.Pattern())
	fmt.Println("Method:", route.Method())
}

Output:
Pattern: /users/:id/posts/:pid
Method: GET

func (*CompiledRoute) CachedHandlers 

func (r *CompiledRoute) CachedHandlers() unsafe.Pointer

CachedHandlers returns the cached converted handlers, or nil if not set. Returns unsafe.Pointer to []router.HandlerFunc.

func (*CompiledRoute) Handlers 

func (r *CompiledRoute) Handlers() []HandlerFunc

Handlers returns the handler chain for this route

func (*CompiledRoute) Method 

func (r *CompiledRoute) Method() string

Method returns the HTTP method for this route

func (*CompiledRoute) Pattern 

func (r *CompiledRoute) Pattern() string

Pattern returns the route pattern (e.g., "/users/:id")

func (*CompiledRoute) SetCachedHandlers 

func (r *CompiledRoute) SetCachedHandlers(handlers unsafe.Pointer)

SetCachedHandlers stores the converted handler slice. The handlers parameter should be a pointer to []router.HandlerFunc. This is called once during route compilation by the router.

type ContextParamWriter 

type ContextParamWriter interface {
	SetParam(index int, key, value string)
	SetParamMap(key, value string)
	SetParamCount(count int32)
}

ContextParamWriter is an interface for writing route parameters to a context. This avoids import cycles by not importing router.Context directly.

type HandlerFunc 

type HandlerFunc any

HandlerFunc defines the handler function signature. This is a copy of router.HandlerFunc to avoid import cycles.

type RouteCompiler 

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

RouteCompiler manages compiled routes for lookup. It organizes routes into static routes (exact path matches) and dynamic routes (routes with parameters). Routes are matched using the compiled metadata stored in CompiledRoute.

func NewRouteCompiler 

func NewRouteCompiler(bloomSize uint64, numHashFuncs int) *RouteCompiler

NewRouteCompiler creates a new route compiler

Example

ExampleNewRouteCompiler demonstrates creating a new route compiler. 

package main

import (
	"fmt"

	"rivaas.dev/router/compiler"
)

func main() {
	// Create a route compiler with bloom filter size 1000 and 3 hash functions
	rc := compiler.NewRouteCompiler(1000, 3)

	// Add routes to the compiler
	route := compiler.CompileRoute("GET", "/users", nil, nil)
	rc.AddRoute(route)

	fmt.Println("Route compiler created successfully")
}

Output:
Route compiler created successfully

func (*RouteCompiler) AddRoute 

func (rc *RouteCompiler) AddRoute(route *CompiledRoute)

AddRoute adds a compiled route to the compiler

Example

ExampleRouteCompiler_AddRoute demonstrates adding routes to a compiler. 

package main

import (
	"fmt"

	"rivaas.dev/router/compiler"
)

func main() {
	rc := compiler.NewRouteCompiler(1000, 3)

	// Add a static route
	staticRoute := compiler.CompileRoute("GET", "/health", nil, nil)
	rc.AddRoute(staticRoute)

	// Add a dynamic route
	dynamicRoute := compiler.CompileRoute("GET", "/users/:id", nil, nil)
	rc.AddRoute(dynamicRoute)

	fmt.Println("Routes added successfully")
}

Output:
Routes added successfully

func (*RouteCompiler) Freeze added in v0.4.0 

func (rc *RouteCompiler) Freeze()

Freeze marks the route compiler as immutable. After calling Freeze, the mutex is bypassed in lookup operations since the data can no longer change. This eliminates lock overhead in the hot path.

Freeze also builds the first-segment index if there are enough routes. This should be called after all routes are registered.

func (*RouteCompiler) HasStatic added in v0.4.0 

func (rc *RouteCompiler) HasStatic() bool

HasStatic returns true if any static routes are registered. This is a cheap check that avoids calling LookupStatic entirely.

func (*RouteCompiler) HasStaticRoutes added in v0.4.0 

func (rc *RouteCompiler) HasStaticRoutes() bool

HasStaticRoutes returns true if there are any static routes registered. This can be used to skip LookupStatic entirely when there are no static routes. After Freeze(), this returns a cached value for maximum performance.

func (*RouteCompiler) IsFrozen added in v0.4.0 

func (rc *RouteCompiler) IsFrozen() bool

IsFrozen returns true if the route compiler has been frozen.

func (*RouteCompiler) LookupStatic 

func (rc *RouteCompiler) LookupStatic(method, path string) *CompiledRoute

LookupStatic attempts to find a static route in the hash table. After Freeze() is called, this method bypasses the mutex for better performance.

Optimized to avoid allocations: - Computes FNV-1a hash inline without creating hash objects - Uses pre-computed hash for bloom filter test - Skips entirely if no static routes are registered

Example

ExampleRouteCompiler_LookupStatic demonstrates looking up static routes. 

package main

import (
	"fmt"

	"rivaas.dev/router/compiler"
)

func main() {
	rc := compiler.NewRouteCompiler(1000, 3)

	// Add static routes
	route := compiler.CompileRoute("GET", "/health", nil, nil)
	rc.AddRoute(route)

	// Lookup the route
	found := rc.LookupStatic("GET", "/health")
	if found != nil {
		fmt.Println("Found route:", found.Pattern())
	}

	// Lookup non-existent route
	notFound := rc.LookupStatic("GET", "/nonexistent")
	if notFound == nil {
		fmt.Println("Route not found")
	}
}

Output:
Found route: /health
Route not found

func (*RouteCompiler) MatchDynamic 

func (rc *RouteCompiler) MatchDynamic(method, path string, ctx ContextParamWriter) *CompiledRoute

MatchDynamic attempts to match path against dynamic routes. Uses first-segment index for filtering. After Freeze() is called, this method bypasses the mutex for better performance.

func (*RouteCompiler) RemoveRoute 

func (rc *RouteCompiler) RemoveRoute(method, pattern string)

RemoveRoute removes a route from the compiler (used when updating constraints)

type RouteConstraint 

type RouteConstraint struct {
	Param   string
	Pattern *regexp.Regexp
}

RouteConstraint represents a compiled constraint for route parameters. This is a copy of router.RouteConstraint to avoid import cycles.

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.