Capstan is a Golang web framework that shares some similarities with others in its segment.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

559 lines
15 KiB

package capstan
import (
"fmt"
"net/http"
"strings"
)
// DefaultMappableNodeFunc is the default mappableNode generator used whenever a
// mappableNodeFunc has not been assigned to the radix trie.
var DefaultMappableNodeFunc = func() mappableNode {
return &binaryTree{}
}
// mappableNodeFunc defines the type used for generating mappableNodes when new
// nodes are added to the radix tree.
type mappableNodeFunc func() mappableNode
// mappableNode defines the interface that all mappers must implement.
type mappableNode interface {
Insert(node *proxyTrie)
IsEmpty() bool
Lookup(label rune) (*proxyTrie, error)
}
// binaryTree is the default mapper used internally by the radix trie in our
// implementation. This is a simple and rather naïve binary tree that performs
// no balancing. It behaves adequately for most workloads with roughly
// middle-of-the-road performance in the worst case.
//
// The performance of binaryTree is slightly faster than mappedNode and slightly
// inferior to arrayNode when using small data sets. When using large data sets
// its performance is suprior to arrayNode and slightly faster than mappedNode.
// When used in radix tries that deal with a handful of common prefixes it is
// slightly interior to both arrayNode and mappedNode.
//
// There are two other mapper implementations for mapping labels to nodes at the
// radix trie edges which use a map (mappedNode) or an array (arrayNode).
type binaryTree struct {
left *binaryTree
right *binaryTree
node *proxyTrie
}
// BinaryTreeMapperFunc returns a new binary tree.
func BinaryTreeMapperFunc() mappableNode {
return &binaryTree{}
}
func (b *binaryTree) Insert(node *proxyTrie) {
switch {
// Edge.
case b.node == nil:
b.node = node
return
case node.label < b.node.label:
if b.left == nil {
b.left = &binaryTree{
node: node,
}
} else {
b.left.Insert(node)
}
default:
if node.label == b.node.label {
b.node.handler = node.handler
return
}
if b.right == nil {
b.right = &binaryTree{
node: node,
}
} else {
b.right.Insert(node)
}
}
}
func (b *binaryTree) IsEmpty() bool {
return b.left == nil && b.right == nil && b.node == nil
}
func (b *binaryTree) Lookup(label rune) (*proxyTrie, error) {
switch {
case b.node == nil:
return nil, fmt.Errorf("not found")
case b.node.label == label:
return b.node, nil
default:
if b.left != nil && label < b.node.label {
return b.left.Lookup(label)
} else if b.right != nil && label > b.node.label {
return b.right.Lookup(label)
} else {
return nil, fmt.Errorf("not found")
}
}
}
func (b *binaryTree) String() string {
if b.left == nil && b.right == nil && b.node == nil {
return "&binaryTree{}"
}
return fmt.Sprintf(`&binaryTree<left="%v", right="%v", value="%s">`,
b.left, b.right, b.node)
}
// mappedNode uses a map for mapping labels to their respective nodes. When
// using workloads where you expect a handful of common prefixes to occur in
// your data set this is probably the fastest option.
type mappedNode struct {
keys map[rune]*proxyTrie
}
// NewMappedNode returns a new, initialized mappedNode.
func NewMappedNode() *mappedNode {
return &mappedNode{
keys: make(map[rune]*proxyTrie),
}
}
func (m *mappedNode) Insert(node *proxyTrie) {
if node == nil {
return
}
m.keys[node.label] = node
}
func (m *mappedNode) IsEmpty() bool {
return len(m.keys) == 0
}
func (m *mappedNode) String() string {
var out string
if len(m.keys) > 0 {
out += "&mappedNode{\n"
i := 0
for k, v := range m.keys {
i++
out += " " + string(k) + " => " + v.String() + ",\n"
}
out += "}"
return out
}
return "&mappedNode{}"
}
func (m *mappedNode) Lookup(label rune) (*proxyTrie, error) {
node, ok := m.keys[label]
if !ok {
return nil, fmt.Errorf("not found")
}
return node, nil
}
// arrayNode is a label to edge node mapper that performs a naïve lookup using
// an array. When matching a label, it traverses the array from the first
// element to the last. For exceedingly small data sets this is usually the
// fastest implementation. Be ware that as your data set grows, this
// implementation becomes *significantly* slower.
type arrayNode struct {
keys []*proxyTrie
}
// ArrayMapperFunc returns a new, initialized arrayNode.
func ArrayMapperFunc() mappableNode {
return &arrayNode{
keys: make([]*proxyTrie, 0),
}
}
func (a *arrayNode) Insert(node *proxyTrie) {
for i := 0; i < len(a.keys); i++ {
if a.keys[i].label == node.label {
a.keys[i].handler = node.handler
return
}
}
a.keys = append(a.keys, node)
}
func (a *arrayNode) IsEmpty() bool {
return len(a.keys) == 0
}
func (a *arrayNode) String() string {
return "&arrayNode{}"
}
func (a *arrayNode) Lookup(label rune) (*proxyTrie, error) {
for i := 0; i < len(a.keys); i++ {
if a.keys[i].label == label {
return a.keys[i], nil
}
}
return nil, fmt.Errorf("no such key")
}
// proxyTrie is the data structure the backs our radix trie implementation.
//
// As with most radix tries, each node contains a label plus its assigned
// prefix. Labels are used to perform a comparison lookup to find the next
// appropriate node. `keys` may be assigned anything that implements the
// mappableNode interface and is used for looking up the next matching node.
type proxyTrie struct {
// label is the first character matching the current node's prefix.
label rune
// prefix is the string for this node, either in part or in full. If in
// part, this acts as the prefix for its children nodes.
prefix string
// HTTP handler assigned to this node. If nil, this is an edge node.
handler http.Handler
// Map keys for child nodes. These are stored in a binary tree and consist
// of the child nodes' labels. This allows comapratively fast lookups for
// child node prefixes.
keys mappableNode
// KeyFunc contains a keying function for mapping labels to nodes at trie
// edges. If unset, this will be configured to use the
// DefaultMappableNodeFunc.
KeyFunc func() mappableNode
}
// NewProxyTrie returns a root radix trie node.
func NewProxyTrie() *proxyTrie {
return &proxyTrie{
keys: &binaryTree{},
KeyFunc: DefaultMappableNodeFunc,
}
}
// NewTrieNode returns a new radix trie node for use within a radix trie root node.
func NewTrieNode(label rune, prefix string, fn mappableNodeFunc) *proxyTrie {
return &proxyTrie{
label: label,
prefix: prefix,
keys: fn(),
KeyFunc: fn,
}
}
// Returns the longest common prefix shared between the strings s1 and s2.
func longestPrefix(s1, s2 string) string {
c1 := s1
c2 := s2
if len(s2) < len(s1) {
c1 = s2
c2 = s1
}
var offset int
for offset = 0; offset < len(c1); offset++ {
if c1[offset] != c2[offset] {
break
}
}
if offset == 0 {
return ""
}
return c1[:offset]
}
// Returns the best matching edge node along with the attributes: edge node,
// revised pattern (rather the *unmatched* pattern suffix), the common string
// between `pattern` and the edge node, whether the node should be split when
// adding a node (first bool), or whether the node should be re-rooted under its
// parent (second bool).
//
// This function makes additional assignments internally so as to match the
// returned values making their purpose a bit more clear.
func (t *proxyTrie) getEdge(pattern string) (trie *proxyTrie, newPattern string, commonPrefix string, split bool, newLeaf bool) {
var err error
newPattern = pattern
label := rune(newPattern[0])
split = false
newLeaf = false
if trie, err = t.keys.Lookup(label); err == nil {
// Incoming pattern matches the edge prefix exactly.
if newPattern == trie.prefix {
// If the matched edge is not empty, we need to set it as a new leaf
// as well as a (likely) node parent.
if !trie.keys.IsEmpty() {
newLeaf = true
return
}
return
}
// If the incoming pattern matches the node prefix, we know we'll still
// have some characters left in the pattern to examine. So we'll split
// the pattern up and keep looking.
if strings.HasPrefix(newPattern, trie.prefix) {
newPattern = newPattern[len(trie.prefix):]
return trie.getEdge(newPattern)
}
// We don't have an exact match so we must now examine the incoming
// pattern versus the prefix of the node we've just discovered.
commonPrefix = longestPrefix(newPattern, trie.prefix)
// If the only prefix we have that matches our incoming pattern is the
// commonPrefix we'll need to split this node. So, we'll return with
// split=true to signal to Insert() that the node must be split. Since
// we return some additional metadata, including the new pattern
// (suffix--or pattern minus the common prefix) in addition to the
// common prefix, Insert() will know whether to re-parent the edge or
// create multiple child nodes.
if strings.HasPrefix(newPattern, commonPrefix) {
newPattern = newPattern[len(commonPrefix):]
split = true
return
}
}
// If we've made it this far, we haven't found the node we're looking for,
// so we return the current node (t) as the new edge.
trie = t
return
}
// Insert a new handler into the trie using pattern `pattern`. Returns the
// generated node.
func (t *proxyTrie) Insert(pattern string, handler http.Handler) *proxyTrie {
edge, newpattern, common, split, newLeaf := t.getEdge(pattern)
// Root node detection.
if edge.label == rune(0) && edge.prefix == "" {
node := NewTrieNode(rune(pattern[0]), pattern, t.KeyFunc)
node.handler = handler
edge.keys.Insert(node)
return node
}
// Edge node is now itself a leaf. This occurs when the incoming pattern
// terminates at an edge node that did not previously have a handler
// assigned.
if newLeaf {
edge.handler = handler
return edge
}
if split {
// Node split is required since it already contains a value. Node splits
// occur when the node contains a common prefix that is now shared by
// the incoming node.
leftPrefix := edge.prefix[len(common):]
rightPrefix := newpattern
// Splits the prefix into a child and edge node with the incoming
// handler configured on the edge and the prior edge handler as the
// child node. This occurs if the edge contains, for example, "abc" and
// the incoming pattern is simply "ab" since we need to split the prefix
// ("ab") and create a new node with the old suffix ("c").
if rightPrefix == "" {
node := NewTrieNode(rune(leftPrefix[0]), leftPrefix, t.KeyFunc)
node.handler = edge.handler
node.keys = edge.keys
edge.prefix = common
edge.keys = t.KeyFunc()
edge.keys.Insert(node)
edge.handler = handler
return edge
}
// Dual prefix split where the edge node no longer contains a handler as
// it is no longer an endpoint in the prefix search. This can occur when
// adding patterns with similar suffixes, up to a point, such as
// "testing" and "testify." In this case, "test" is added as its own
// node with an edge of "ing." As "testify" is added to the nodes, "ing"
// is split off into an edge node ("i") with two child nodes ("ng" and
// "fy"). These are the "left" and "right" prefixes.
//
// Do not mistake left and right for a binary radix trie, which this is
// not. This is just inline semantics to make it easier to reaspon about
// when the edge nodes are re-parented.
lnode := NewTrieNode(rune(leftPrefix[0]), leftPrefix, t.KeyFunc)
rnode := NewTrieNode(rune(rightPrefix[0]), rightPrefix, t.KeyFunc)
lnode.handler = edge.handler
rnode.handler = handler
lnode.keys = edge.keys
edge.keys = t.KeyFunc()
edge.keys.Insert(lnode)
edge.keys.Insert(rnode)
edge.handler = nil
edge.prefix = common
return rnode
} else {
// No node split is required so we simply attach a new node to the
// current edge.
node := NewTrieNode(rune(newpattern[0]), newpattern, t.KeyFunc)
node.handler = handler
edge.keys.Insert(node)
}
return edge
}
// IsEdge returns whether the node is an edge node.
func (t *proxyTrie) IsEdge() bool {
return t.handler == nil
}
// IsLeaf returns whether the node is a leaf node.
func (t *proxyTrie) IsLeaf() bool {
return t.handler != nil
}
// IsRoot returns whether the node is the root node.
func (t *proxyTrie) IsRoot() bool {
return t.label == rune(0) && t.prefix == "" && t.handler == nil
}
// Overwrite the handler contained in the specified pattern. If the pattern
// doesn't exist, Overwrite returns false.
func (t *proxyTrie) Overwrite(pattern string, handler http.Handler) bool {
node := t.lookup(pattern)
if node == nil {
return false
}
node.handler = handler
return true
}
// Lookup accepts a single pattern string and traverses the radix trie,
// returning the handler associated with the pattern or nil if the pattern
// cannot be found.
func (t *proxyTrie) Lookup(pattern string) http.Handler {
n := t.lookup(pattern)
if n != nil {
return n.handler
}
return nil
}
// lookup returns the appropriate matching node when traversing the radix trie.
// This is used by Lookup to return a handler.
func (t *proxyTrie) lookup(pattern string) *proxyTrie {
var err error
node := t
label := rune(pattern[0])
for {
if len(pattern) == 0 {
if node != nil {
return node
}
return nil
}
node, err = node.keys.Lookup(label)
if err != nil {
return nil
}
if pattern == node.prefix {
return node
}
common := longestPrefix(pattern, node.prefix)
pattern = pattern[len(common):]
if len(pattern) > 0 {
label = rune(pattern[0])
}
}
}
// LongestMatch behaves similarly to Lookup with the exception that it accepts a
// pattern and finds the node that matches the longest portion of the pattern
// string, returning the handler associated (or nil if no node was found).
//
// Since this is best illustrated through example, assume that the following as
// inserted into the trie:
//
// String: app.example.com/blog String: app.example.com/store
//
// Incoming pattern: app.example.com/store/new-mexico
//
// LongestMatch will match the incoming pattern to the second string,
// "app.example.com/store", as it is the *longest* possible match contained
// within the trie that can be matched against the incoming pattern. This will
// *not* match:
//
// - app.example.com/stow
//
// ...but will match:
//
// - app.example.com/stores/new-mexico
//
// It is important to understand the LongestMatch limitations when designing
// your application around it as it is currently path agnostic. Care must be
// taken to ensure that the handlers attached to any given pattern will fail as
// expected when passed unexpected URLs.
func (t *proxyTrie) LongestMatch(pattern string) http.Handler {
var last *proxyTrie
var err error
node := t
last = node
label := rune(pattern[0])
for {
if len(pattern) == 0 {
if node != nil {
return node.handler
}
return last.handler
}
last = node
node, err = node.keys.Lookup(label)
if err != nil {
return last.handler
}
common := longestPrefix(pattern, node.prefix)
if common == node.prefix {
pattern = pattern[len(common):]
} else {
return last.handler
}
if len(pattern) == 0 {
return node.handler
}
label = rune(pattern[0])
}
}
// String representation of the trie.
func (t *proxyTrie) String() string {
return fmt.Sprintf(`&proxyTrie{label="%c", prefix="%s", handler="%v" keys="%v"}`,
t.label, t.prefix, t.handler, t.keys)
}
// SwitchKeyFunc changes the keying function to fn.
func (t *proxyTrie) SwitchKeyFunc(fn mappableNodeFunc) {
t.keys = fn()
t.KeyFunc = fn
}