Go: trie redirects with wildcard support

redirect.go

// First complete match wins. 
// Because exact children are tried before `*` which is tried before `**`. 
// The most-specific rule wins without an explicit priority sort.
package redirect

import (
	"fmt"
	"strings"
)

// Rule represents a redirect destination pattern.
type Rule struct {
	Destination string
}

// Substitute replaces $1, $2, etc. with captured values.
func (r *Rule) Substitute(captures []string) string {
	result := r.Destination
	for i, c := range captures {
		result = strings.ReplaceAll(result, fmt.Sprintf("$%d", i+1), c)
	}
	return result
}

// Node represents a single segment in the trie.
type Node struct {
	Children map[string]*Node
	Rule     *Rule
}

// Trie holds redirect rules indexed by path segment.
type Trie struct {
	Root *Node
}

// NewTrie returns an empty trie.
func NewTrie() *Trie {
	return &Trie{Root: &Node{Children: make(map[string]*Node)}}
}

// Insert adds a rule to the trie. Pattern segments may be literals, "*", or "**".
func (t *Trie) Insert(pattern, destination string) {
	current := t.Root
	for _, seg := range strings.Split(strings.Trim(pattern, "/"), "/") {
		if current.Children[seg] == nil {
			current.Children[seg] = &Node{Children: make(map[string]*Node)}
		}
		current = current.Children[seg]
	}
	current.Rule = &Rule{Destination: destination}
}

// Lookup walks the trie and returns the substituted destination, or "" on no match.
func (t *Trie) Lookup(path string) string {
	return t.Root.match(strings.Trim(path, "/"), nil)
}

func (n *Node) match(remaining string, captures []string) string {
	// Base case: no segments left.
	if remaining == "" {
		if n.Rule != nil {
			return n.Rule.Substitute(captures)
		}
		// "**" matches zero remaining segments.
		if glob, ok := n.Children["**"]; ok && glob.Rule != nil {
			return glob.Rule.Substitute(append(captures, ""))
		}
		return ""
	}

	seg, rest, _ := strings.Cut(remaining, "/")

	// 1. Exact match (most specific).
	if child, ok := n.Children[seg]; ok {
		if result := child.match(rest, captures); result != "" {
			return result
		}
	}

	// 2. Single-segment wildcard.
	if child, ok := n.Children["*"]; ok {
		if result := child.match(rest, append(captures, seg)); result != "" {
			return result
		}
	}

	// 3. Globstar — capture all remaining segments.
	if glob, ok := n.Children["**"]; ok && glob.Rule != nil {
		return glob.Rule.Substitute(append(captures, remaining))
	}

	return ""
}

redirect_test.go

package redirect

import "testing"

func TestLookup(t *testing.T) {
	trie := NewTrie()
	trie.Insert("/old-blog/*", "/blog/$1")
	trie.Insert("/products/*/reviews", "/items/$1/feedback")
	trie.Insert("/a/*/b/*/c", "/x/$1/y/$2")
	trie.Insert("/docs/**", "/documentation/$1")
	trie.Insert("/legacy/**", "/v2/$1")
	trie.Insert("/exact/match", "/target")

	tests := []struct {
		name string
		path string
		want string
	}{
		// Exact match.
		{name: "exact hit", path: "/exact/match", want: "/target"},
		{name: "exact miss", path: "/exact/other", want: ""},

		// Single-segment wildcard.
		{name: "prefix wildcard", path: "/old-blog/hello-world", want: "/blog/hello-world"},
		{name: "mid-path wildcard", path: "/products/widget/reviews", want: "/items/widget/feedback"},
		{name: "multiple wildcards", path: "/a/1/b/2/c", want: "/x/1/y/2"},

		// Single-segment wildcard does NOT match multiple segments.
		{name: "star won't cross segments", path: "/old-blog/a/b", want: ""},

		// Globstar.
		{name: "globstar deep path", path: "/docs/api/v2/auth", want: "/documentation/api/v2/auth"},
		{name: "globstar single segment", path: "/docs/overview", want: "/documentation/overview"},
		{name: "globstar zero segments", path: "/docs", want: "/documentation/"},
		{name: "globstar preserves path", path: "/legacy/users/42/profile", want: "/v2/users/42/profile"},

		// No match.
		{name: "unknown path", path: "/unknown/path", want: ""},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			got := trie.Lookup(tt.path)
			if got != tt.want {
				t.Errorf("Lookup(%q) = %q, want %q", tt.path, got, tt.want)
			}
		})
	}
}