radix

Documentation

Overview

Package radix implements a compressed radix tree (Patricia trie) for HTTP request routing. It supports named parameters ({id}), regex-constrained parameters ({id:[0-9]+}), and catch-all parameters ({path...}).

The tree is generic over its payload: Node[V] stores opaque values of type V at its endpoints and never inspects or invokes them — the router that owns the tree defines what a payload means.

This package is internal to the Credo module and should not be imported directly by external consumers. Use the router package instead.

Index

• func AllMethods() map[string]MethodTyp
• func FindMatchingBrace(pattern string, openIdx int) int
• func MethodTypToString(mtyp MethodTyp) []string
• type DuplicateRouteError
  • func (e *DuplicateRouteError[V]) Error() string
• type Endpoint
• type Endpoints
• type MethodTyp
  • func LookupMethod(method string) (MethodTyp, bool)
• type Node
  • func NewTree[V any]() *Node[V]
  • func (n *Node[V]) FindEndpoint(method MethodTyp, pattern string) (*Endpoint[V], bool)
  • func (n *Node[V]) FindRoute(rctx *RouteContext, method MethodTyp, path string) (V, bool)
  • func (n *Node[V]) InsertRoute(method MethodTyp, pattern string, value V, autoGenerated ...bool) (*Node[V], error)
• type NodeTyp
• type Nodes
  • func (ns Nodes[V]) FindEdge(label byte) *Node[V]
  • func (ns Nodes[V]) Sort()
• type PatternSegment
• type RouteContext
  • func (rc *RouteContext) MethodsAllowed() MethodTyp
  • func (rc *RouteContext) Reset()
  • func (rc *RouteContext) URLParam(name string) string
• type RouteParams
  • func (p *RouteParams) Add(key, value string)

Functions

func AllMethods

func AllMethods() map[string]MethodTyp

AllMethods returns a copy of all registered method string-to-MethodTyp pairs.

func FindMatchingBrace

func FindMatchingBrace(pattern string, openIdx int) int

FindMatchingBrace returns the index of the closing '}' that matches the opening '{' at position openIdx, accounting for nested braces in regex quantifiers like {id:[0-9]{2,4}}, escaped braces (\{, \}), and character classes ([...]). Returns -1 if no matching brace is found.

func MethodTypToString

func MethodTypToString(mtyp MethodTyp) []string

MethodTypToString converts a MethodTyp bitmask to a sorted slice of HTTP method strings. Only known (registered) methods are included.

Types

type DuplicateRouteError

type DuplicateRouteError[V any] struct {
	// Method is the HTTP method of the conflicting registration.
	Method MethodTyp
	// Pattern is the pattern being registered now.
	Pattern string
	// ExistingPattern is the pattern the prior endpoint was registered as
	// (may differ from Pattern when both normalize to the same node).
	ExistingPattern string
	// Existing is the prior endpoint's payload.
	Existing V
}

DuplicateRouteError reports an attempt to register a method+pattern that already has an explicit (non-auto-generated) endpoint. Existing is the payload of the prior registration, so a caller that knows V's concrete type can surface registration-site detail (e.g. the original file:line) that the generic tree itself cannot read.

func (*DuplicateRouteError[V]) Error

func (e *DuplicateRouteError[V]) Error() string

type Endpoint

type Endpoint[V any] struct {
	Value         V
	Pattern       string
	AutoGenerated bool // true for auto-generated endpoints (e.g., HEAD from GET)
}

Endpoint holds the payload value for a specific HTTP method on a node.

type Endpoints

type Endpoints[V any] map[MethodTyp]*Endpoint[V]

Endpoints maps MethodTyp bitflags to their Endpoint.

type MethodTyp

type MethodTyp uint

MethodTyp is a bitmask representing one or more HTTP methods.

const (
	MConnect MethodTyp // CONNECT
	MDelete            // DELETE
	MGet               // GET
	MHead              // HEAD
	MOptions           // OPTIONS
	MPatch             // PATCH
	MPost              // POST
	MPut               // PUT
	MTrace             // TRACE

)

func LookupMethod

func LookupMethod(method string) (MethodTyp, bool)

LookupMethod returns the MethodTyp for the given HTTP method string and a boolean indicating whether it was found. Standard HTTP methods are resolved via a lock-free switch for hot-path performance; only custom methods fall through to the locked map.

type Node

type Node[V any] struct {
	// Typ is the node type (static, param, regexp, catch-all).
	Typ NodeTyp

	// Label is the first byte of the prefix (for fast edge lookup).
	Label byte

	// Prefix is the compressed path prefix stored in this node.
	Prefix string

	// Tail is the byte following a parameter segment (for scan optimization).
	Tail byte

	// ParamKey is the parameter name for param/regexp/catch-all nodes.
	ParamKey string

	// RegexpSeg is the parsed pattern segment for NtRegexp nodes.
	// Named RegexpSeg (not Regexp) to avoid confusing double-dereference
	// like node.Regexp.Regexp when accessing the compiled *regexp.Regexp.
	RegexpSeg *PatternSegment

	// Children holds child nodes, sorted by routing priority.
	Children [NtCatchAll + 1]Nodes[V]

	// Endpoints maps HTTP methods to their payloads.
	Endpoints Endpoints[V]
}

Node represents a node in the radix tree. The tree stores opaque payload values of type V — the router defines what a payload is; the tree never inspects or invokes it.

func NewTree

func NewTree[V any]() *Node[V]

NewTree returns an empty root node ready for InsertRoute.

func (*Node[V]) FindEndpoint

func (n *Node[V]) FindEndpoint(method MethodTyp, pattern string) (*Endpoint[V], bool)

FindEndpoint walks the tree read-only along pattern, using the same edge-selection logic as Node.InsertRoute but without creating or splitting any node. It returns the endpoint already registered for method at the exact pattern location, or (nil, false) when an InsertRoute of pattern would instead build new structure (a fresh child or a node split) — in which case no endpoint can pre-exist there.

It is the read-only twin of the duplicate check in setEndpoint: a non-nil, non-auto-generated result means InsertRoute(method, pattern) would return a DuplicateRouteError. FindEndpoint reports only endpoint existence; it does not surface the structural conflicts (mismatched parameter keys or regexp matchers) that InsertRoute also rejects — a mismatch during navigation simply yields (nil, false), since no endpoint exists at the resulting location.

func (*Node[V]) FindRoute

func (n *Node[V]) FindRoute(rctx *RouteContext, method MethodTyp, path string) (V, bool)

FindRoute traverses the tree to find the payload registered for the given method and path. It populates rctx with matched parameters. The boolean reports whether a route matched; when it is false, rctx.MethodNotAllowed tells a 404 apart from a 405.

func (*Node[V]) InsertRoute

func (n *Node[V]) InsertRoute(method MethodTyp, pattern string, value V, autoGenerated ...bool) (*Node[V], error)

InsertRoute adds a route pattern and payload value to the tree. Returns the leaf node and an error if the pattern conflicts with existing routes. If autoGenerated is true, the endpoint is marked as auto-generated and can be overwritten by explicit (non-auto-generated) registrations.

type NodeTyp

type NodeTyp uint8

NodeTyp classifies the type of a radix tree node.

const (
	NtStatic   NodeTyp = iota // Static path segment (e.g., "/users")
	NtRegexp                  // Regex-constrained parameter (e.g., "{id:[0-9]+}")
	NtParam                   // Named parameter (e.g., "{id}")
	NtCatchAll                // Catch-all parameter (e.g., "{path...}")
)

type Nodes

type Nodes[V any] []*Node[V]

Nodes is a sortable slice of Node pointers.

func (Nodes[V]) FindEdge

func (ns Nodes[V]) FindEdge(label byte) *Node[V]

FindEdge returns the child node whose prefix starts with the given label byte.

func (Nodes[V]) Sort

func (ns Nodes[V]) Sort()

Sort orders nodes for correct routing precedence: Static > Regexp > Param > CatchAll Within the same type, longer prefixes come first.

Each Children slot holds a single node type, so the type comparison below is normally a no-op; it stays as a guard in case a mixed slice is ever sorted.

type PatternSegment

type PatternSegment struct {
	// Typ is the type of this segment.
	Typ NodeTyp

	// Prefix is the static string before the parameter.
	Prefix string

	// ParamKey is the parameter name (without braces).
	ParamKey string

	// Regexp is the compiled regex for NtRegexp segments.
	Regexp *regexp.Regexp

	// Suffix is the remaining pattern after this segment.
	Suffix string

	// TailByte is the first byte after the parameter
	// (used for fast scanning during match).
	TailByte byte
}

PatternSegment holds the parsed result from patNextSegment.

type RouteContext

type RouteContext struct {
	// RoutePath is the path to match against. Updated during sub-router mounting.
	RoutePath string

	// RouteMethod is the HTTP method of the request.
	RouteMethod string

	// RoutePatterns collects path patterns matched along the route chain.
	RoutePatterns []string

	// Params holds the URL parameter key-value pairs.
	Params RouteParams

	// MethodNotAllowed indicates that the path matched but not the method.
	MethodNotAllowed bool
	// contains filtered or unexported fields
}

RouteContext holds routing state for a single request. It is stored in the request context and populated by the router during route matching.

func (*RouteContext) MethodsAllowed

func (rc *RouteContext) MethodsAllowed() MethodTyp

MethodsAllowed returns the set of methods allowed for the matched path.

func (*RouteContext) Reset

func (rc *RouteContext) Reset()

Reset clears the RouteContext for reuse.

func (*RouteContext) URLParam

func (rc *RouteContext) URLParam(name string) string

URLParam returns the value of a URL parameter by name. Returns empty string if the parameter doesn't exist. Iterates in reverse so that the last-added value wins (supports nested routes with shadowed parameters).

type RouteParams

type RouteParams struct {
	Keys   []string
	Values []string
}

RouteParams holds key-value pairs of URL parameters extracted from the matched route pattern.

func (*RouteParams) Add

func (p *RouteParams) Add(key, value string)

Add appends a key-value pair to the route parameters.