# eudore router radix
RouterCoreStd是使用Radix算法独立实现的高性能路由器，
## Radix基础
RouterCoreStd是基于基数树(Radix)实现，压缩前缀树，是一种更节省空间的Trie（前缀树）。对于基数树的每个节点，如果该节点是唯一的子树的话，就和父节点合并。
如果依次向树添加test、team、api，那么过程应该如下，test和team具有公共前缀te，te是st和am公共前缀。
添加test，只有唯一子节点。
```
test
```
添加team，team和test具有相同前缀te，那么提取te为公共前缀，然后子节点有两个，分叉成st和am。
```
te
--st
--am
```
添加api，api和te没有相同前缀（首字母不同），给根节点添加一个新的子节点api。
```
te
--st
--am
api
```
如果需要查找应该字符串，匹配字符串的和节点字符串是否为查找的字符串前缀，是才表示匹配，然后截取剩余字符串，进行下一步匹配。
如果查找append，根节点只有te、app、interface三个子节点，匹配命中app，剩余未匹配的是le。
然后使用a的子节点le、end，两个子节点匹配恰好le。
```
te
--st
----22
--am
app
---le
---end
interface
```
插入和查找的radix实现：
```
package main
import (
"strings"
"testing"
"fmt"
"github.com/kr/pretty"
)
func main() {
tree := NewRadixTree()
tree.Insert("test", 1)
tree.Insert("test22", 1)
tree.Insert("team", 3)
tree.Insert("apple", 4)
tree.Insert("append", 12)
tree.Insert("app", 5)
tree.Insert("append", 6)
tree.Insert("interface", 7)
fmt.Printf("%# v\n", pretty.Formatter(tree))
t.Log(tree.Lookup("append"))
}
type (
radixTree struct {
root radixNode
}
radixNode struct {
path string
children []*radixNode
key string
val interface{}
}
)
func NewRadixTree() *radixTree {
return &radixTree{radixNode{}}
}
func (r *radixNode) InsertNode(path, key string, value interface{}) {
if len(path) == 0 {
r.key = key
r.val = value
} else {
r.children = append(r.children, &radixNode{path: path, key: key, val: value})
}
}
func (r *radixNode) SplitNode(pathKey, edgeKey string) *radixNode {
for i, _ := range r.children {
if r.children[i].path == edgeKey {
newNode := &radixNode{path: pathKey}
newNode.children = append(newNode.children, &radixNode{
path: strings.TrimPrefix(edgeKey, pathKey),
key: r.children[i].key,
val: r.children[i].val,
children: r.children[i].children,
})
r.children[i] = newNode
return newNode
}
}
return nil
}
func (t *radixTree) Insert(key string, val interface{}) {
t.recursiveInsertTree(&t.root, key, key, val)
}
func (t *radixTree) recursiveInsertTree(currentNode *radixNode, containKey string, targetKey string, targetValue interface{}) {
for i, _ := range currentNode.children {
subStr, find := getSubsetPrefix(containKey, currentNode.children[i].path)
if find {
if subStr == currentNode.children[i].path {
nextTargetKey := strings.TrimPrefix(containKey, currentNode.children[i].path)
t.recursiveInsertTree(currentNode.children[i], nextTargetKey, targetKey, targetValue)
} else {
newNode := currentNode.SplitNode(subStr, currentNode.children[i].path)
if newNode == nil {
panic("Unexpect error on split node")
}
newNode.InsertNode(strings.TrimPrefix(containKey, subStr), targetKey, targetValue)
}
return
}
}
currentNode.InsertNode(containKey, targetKey, targetValue)
}
func (t *radixTree) Lookup(searchKey string) (interface{}, bool) {
return t.recursiveLoopup(&t.root, searchKey)
}
func (t *radixTree) recursiveLoopup(searchNode *radixNode, searchKey string) (interface{}, bool) {
if len(searchKey) == 0 {
return searchNode.val, searchNode.key != ""
}
for _, edgeObj := range searchNode.children {
if contrainPrefix(searchKey, edgeObj.path) {
nextSearchKey := strings.TrimPrefix(searchKey, edgeObj.path)
return t.recursiveLoopup(edgeObj, nextSearchKey)
}
}
return nil, false
}
func contrainPrefix(str1, str2 string) bool {
if sub, find := getSubsetPrefix(str1, str2); find {
return sub == str2
}
return false
}
func getSubsetPrefix(str1, str2 string) (string, bool) {
findSubset := false
for i := 0; i < len(str1) && i < len(str2); i++ {
if str1[i] != str2[i] {
retStr := str1[:i]
return retStr, findSubset
}
findSubset = true
}
if len(str1) > len(str2) {
return str2, findSubset
} else if len(str1) == len(str2) {
return str1, str1 == str2
}
return str1, findSubset
}
```
## RouterCoreRadix
[RouterCoreRadix实现](https://github.com/eudore/eudore/blob/f919218094d32cf319d4ad9a1f33a260b8450014/routerradix.go)
RouterCoreRadix相关代码以及移除，当前默认路由核心为RouterCoreStd,由RouterCoreFull重命名，RouterCoreFull为RouterCoreRadix的强化版本。
RouterCoreRadix基于radix tree算法实现，使用节点按类型分类处理，**实现匹配优先顺序、易扩展、低代码复杂度的特点**，~~是eudore当前使用的默认路由器~~。
RouterCoreRadix支持4种路径，'\\'结尾的常量、常量、':name'形式的变量、'\*'结尾的通配符;第一个路径空格后可以增加额外的匹配命中参数；而RouterCoreFull额外增加了两种校验类型。
一二是常量，三是通配符和附加参数、四是参数、五是通配符。
```
/
/index
/api/v1/* version:v1
/:name
/*
```
RouterCoreRadix代码复杂度均低于15，路由器实现中只存在两处代码复杂度大于15(17,18)，由于RouterCoreRadix处理节点类型增加两种导致的，[代码复杂度](https://goreportcard.com/report/github.com/eudore/eudore#gocyclo)
Radix树只是基本的字符串匹配，但是Radix路由具有常量、变量、通配符三种匹配节点,因此将三种分开处理。
```
type radixNode struct {
kind uint8
path string
name string
Cchildren []*radixNode
Pchildren []*radixNode
Wchildren *radixNode
tags []string
vals []string
handlers HandlerFuncs
}
```
radixNode的kind、path、name保存着结点类型、当前匹配路径、匹配的变量名称；CPW（const、param、wildcard）就是三类结点的集合，tags和vals是默认参数、handlers是多个请求处理者。
### HandleFunc
HandleFunc注册Any方法会给全部方法树都注册一遍。
调用insertRoute方法来实现添加，同时将中间件树匹配到的请求中间件和处理者合并，从全部处理中间件和多个请求处理者合并成一个完整请求处理链。
```
func (r *RouterCoreRadix) HandleFunc(method string, path string, handler HandlerFuncs) {
switch method {
case "NotFound", "404":
r.node404.handlers = handler
case "MethodNotAllowed", "405":
r.node405.Wchildren.handlers = handler
case MethodAny:
for _, method := range RouterAllMethod {
r.insertRoute(method, path, true, handler)
}
default:
r.insertRoute(method, path, false, handler)
}
}
```
insertRoute方法先拿到对应的基数树，如果方法是不允许的就拿到的405树，就结束了添加。
然后将路由注册路径按结点类型切割成多段，按照常量、变量、字符串三类将路径切割出来，每类结点就是一种结点的类型，当前切割实现对应特殊的正则规则支持不够。
在查找时先匹配全部常量子节点，没有就使用变量子节点，uri本段就是变量内容，剩余进行递归匹配，如果变量子节点不匹配，就检查通配符节点，如果存在就是直接匹配通配符。
因此具有路由具有严格的匹配优先顺序，一定是先常量再变量最后通配符，由匹配函数里面代码段的位置决定了顺序。
如果六条路由是`/*`，最先注册的，但是api是常量更有效，就会先检查是否是api，不是才会使用通配符，
而`/api/:user`和`/api/:user/info`两条，会进一步检查是否是info，如果是`/api/eudore/list`只会匹配到`/api/*`。
```
/*
/api/v1
/api/*
/api/user
/api/:user
/api/:user/info
```
`func getSpiltPath(key string) []string`将字符串按Node类型切割。
例如`/api/:get/*`中`:get`和`*`明显是变量和通配符节点。所以两种前后需要切分开来，结果为`[/api/ :get / *]`,`/api/`增加变量子节点`:get`，依次添加完成树。
字符串路径切割例子：
```
/ [/]
/api/note/ [/api/note/]
//api/* [/api/ *]
//api/*name [/api/ *name]
/api/get/ [/api/get/]
/api/get [/api/get]
/api/:get [/api/ :get]
/api/:get/* [/api/ :get / *]
/api/:name/info/* [/api/ :name /info/ *]
/api/:name|^\\d+$/info [/api/ :name|^\d+$ /info]
/api/*|^0/api\\S+$ [/api/ *|^0 /api\S+$]
/api/*|^\\$\\d+$ [/api/ *|^\$\d+$]
```
然后给基数树添加结点，如果结点是存在的就返回的存在的，所以要更新当前的根节点，然后依次向下添加。
最后一个结点就是树底了，然后给树底的新结点设置多个请求处理者和默认参数。
如果添加方法是Any，那么kind会增加一个Any的flag，允许非Any方法覆盖Any方法反之不行。
```
func (r *RouterCoreRadix) insertRoute(method, key string, isany bool, val HandlerFuncs) {
var currentNode = r.getTree(method)
if currentNode == &r.node405 {
return
}
args := strings.Split(key, " ")
for _, path := range getSplitPath(args[0]) {
currentNode = currentNode.InsertNode(path, newRadixNode(path))
}
if isany {
if currentNode.kind&radixNodeKindAnyMethod != radixNodeKindAnyMethod && currentNode.handlers != nil {
return
}
currentNode.kind |= radixNodeKindAnyMethod
} else {
currentNode.kind &^= radixNodeKindAnyMethod
}
currentNode.handlers = val
currentNode.SetTags(args)
}
```
newRadixNode函数就是简单的根据首字符来设置结点的类型和名称。
InsertNode方法就根据结点类型来添加对对应的结点集合中，常量结点需要进行分叉操作，将相同的前缀提取出来。
```
func newRadixNode(path string) *radixNode {
newNode := &radixNode{path: path}
switch path[0] {
case '*':
newNode.kind = radixNodeKindWildcard
if len(path) == 1 {
newNode.name = "*"
} else {
newNode.name = path[1:]
}
case ':':
newNode.kind = radixNodeKindParam
newNode.name = path[1:]
default:
newNode.kind = radixNodeKindConst
}
return newNode
}
func (r *radixNode) InsertNode(path string, nextNode *radixNode) *radixNode {
if len(path) == 0 {
return r
}
nextNode.path = path
switch nextNode.kind &^ radixNodeKindAnyMethod {
case radixNodeKindConst:
for i := range r.Cchildren {
subStr, find := getSubsetPrefix(path, r.Cchildren[i].path)
if find {
if subStr != r.Cchildren[i].path {
r.Cchildren[i].path = strings.TrimPrefix(r.Cchildren[i].path, subStr)
r.Cchildren[i] = &radixNode{
path: subStr,
Cchildren: []*radixNode{r.Cchildren[i]},
}
}
return r.Cchildren[i].InsertNode(strings.TrimPrefix(path, subStr), nextNode)
}
}
r.Cchildren = append(r.Cchildren, nextNode)
for i := len(r.Cchildren) - 1; i > 0; i-- {
if r.Cchildren[i].path[0] < r.Cchildren[i-1].path[0] {
r.Cchildren[i], r.Cchildren[i-1] = r.Cchildren[i-1], r.Cchildren[i]
}
}
case radixNodeKindParam:
for _, i := range r.Pchildren {
if i.path == path {
return i
}
}
r.Pchildren = append(r.Pchildren, nextNode)
case radixNodeKindWildcard:
r.Wchildren = nextNode
default:
panic("Undefined radix node type")
}
return nextNode
}
```
### Match
Match是匹配方法，先使用getTree方法获得请求方法对应的树进行查找，如果405就方法的405树，只会匹配405的结果；如果其他方法树就进行路由匹配，匹配结果非空则返回；如果查找的结果是空，就使用404处理。
```
func (r *RouterCoreRadix) Match(method, path string, params Params) HandlerFuncs {
if n := r.getTree(method).recursiveLoopup(path, params); n != nil {
return n
}
r.node404.AddTagsToParams(params)
return r.node404.handlers
}
```
recursiveLoopup方法递归查找主要分为四步。
第一步检测当前节点是否匹配，匹配则添加参数然后返回。
第二步检测当前节点的常量子节点是否和匹配路径前缀，有前缀表示有可能匹配到了，然后截取路径递归匹配，然后不为空就表示匹配命中，返回对象
第三步检测当前节点的变量子节点是否匹配，直接截取两个‘/’间路径为当前的变量匹配内容，然后检测进一步匹配。
第四步检测当前节点是否拥有通配符结点，如果有直接执行通配符匹配。
最后如果前面四步没有匹配名字，返回nil。
```
func (r *radixNode) recursiveLoopup(searchKey string, params Params) HandlerFuncs {
if len(searchKey) == 0 && r.handlers != nil {
r.AddTagsToParams(params)
return r.handlers
}
if len(searchKey) > 0 {
for _, edgeObj := range r.Cchildren {
if edgeObj.path[0] >= searchKey[0] {
if len(searchKey) >= len(edgeObj.path) && searchKey[:len(edgeObj.path)] == edgeObj.path {
nextSearchKey := searchKey[len(edgeObj.path):]
if n := edgeObj.recursiveLoopup(nextSearchKey, params); n != nil {
return n
}
}
break
}
}
if len(r.Pchildren) > 0 {
pos := strings.IndexByte(searchKey, '/')
if pos == -1 {
pos = len(searchKey)
}
nextSearchKey := searchKey[pos:]
for _, edgeObj := range r.Pchildren {
if n := edgeObj.recursiveLoopup(nextSearchKey, params); n != nil {
params.Add(edgeObj.name, searchKey[:pos])
return n
}
}
}
}
if r.Wchildren != nil {
r.Wchildren.AddTagsToParams(params)
params.Add(r.Wchildren.name, searchKey)
return r.Wchildren.handlers
}
return nil
}
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://docs.eudore.cn/eudore/eudore-router-radix.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.