01.路由树-Beego&GIN&Echo实现与设计总结

PART1. 学习路线

我们分成以下步骤来实现一颗路由树:

全静态匹配
支持通配符匹配
支持参数路由
作业:支持正则匹配

PART2. Beego的路由树实现

2.1 ControllerRegister

在之前的框架概览部分讲到过,Beego的ControllerRegister结构体负责路由相关的功能.

ControllerRegister:类似于容器,存储了所有的路由树.

// ControllerRegister containers registered router rules, controller handlers and filters.
type ControllerRegister struct {
	routers      map[string]*Tree
	enablePolicy bool
	enableFilter bool
	policies     map[string]*Tree
	filters      [FinishRouter + 1][]*FilterRouter
	pool         sync.Pool

	// the filter created by FilterChain
	chainRoot *FilterRouter

	// keep registered chain and build it when serve http
	filterChains []filterChainConfig

	cfg *Config
}

ControllerRegister.routers即为路由树.可以看到其类型为map[string]*Tree,其中的key表示HTTP动词.也就是说,Beego的路由树是按照HTTP动词来组织的,每个HTTP动词对应一棵路由树.因此说ControllerRegister存储了所有的路由树.

2.2 Tree

Tree:它代表的就是路由树,在Beego中,一棵路由树可以被看做由子树组成.Tree实际上是一种多叉树的数据结构.

// Tree has three elements: FixRouter/wildcard/leaves
// fixRouter stores Fixed Router
// wildcard stores params
// leaves store the endpoint information
type Tree struct {
	// prefix set for static router
	prefix string
	// search fix route first
	fixrouters []*Tree
	// if set, failure to match fixrouters search then search wildcard
	wildcard *Tree
	// if set, failure to match wildcard search
	leaves []*leafInfo
}

其中:

fixrouters:静态路由
wildcard:通配符路由
leaves:叶子节点

2.3 leafInfo

Beego的路由树中区分了叶子节点和非叶子节点,但可能实际意义并不大.leafInfo结构体表示了叶子节点:

type leafInfo struct {
	// names of wildcards that lead to this leaf. eg, ["id" "name"] for the wildcard ":id" and ":name"
	wildcards []string

	// if the leaf is regexp
	regexps *regexp.Regexp

	runObject interface{}
}

2.4 Beego设计抽象

如下图示,Beego的树定义,并没有采用children式的定义,而是采用递归式的定义,即:一棵树由根节点+子树组成.也就是说实际上ControllerRegister.routers实际上是路由森林而非路由树

PART3. GIN的路由树实现

3.1 methodTrees

在之前的框架概览部分讲到过,GIN的路由树功能本质上是依赖于Engine结构体的trees字段的

type Engine struct {
	// some other fields
	trees            methodTrees
	// some other fields
}

methodTrees的定义:

type methodTrees []methodTree

methodTrees类型是methodTree的切片.实际上GIN的路由树也是按照HTTP动词来组织的,每个HTTP动词对应一棵路由树.只是相比于Beego使用了map[string]*Tree的方式存储路由森林,GIN使用了[]methodTree,也就是切片的方式来存储路由森林,而实际上这个切片中元素的数量只是和HTTP动词的数量(9个)相等.该切片中的每个元素表示了一棵路由树.

3.2 methodTree

type methodTree struct {
	method string
	root   *node
}

methodTree定义了单棵路由树.树在GIN里边采用的是children的定义方式,即树由节点构成.

methodTree.method:HTTP动词
methodTree.root:根节点

3.3 node

node结构体表示树上的1个节点:

type node struct {
	path      string
	indices   string
	wildChild bool
	nType     nodeType
	priority  uint32
	children  []*node // child nodes, at most 1 :param style node at the end of the array
	handlers  HandlersChain
	fullPath  string
}

其中:

children字段表示该节点的子节点
nType:实际上是一个uint8类型,用于标记节点类型
wildChild:标记特殊节点
handlers:责任链

3.4 GIN设计抽象

GIN利用路由的最长公共前缀来构造路由树.

图中的??表示特殊字符

所谓的最长公共前缀,指的是:

/
- c
  - o
    ntact
    m
- a
  - b
- doc/
  - go(注意go_faq.html和go1.html的最长公共前缀是go而不是g,因此基址是go)
    _faq.html
    1.html
  - ??(表示路由中的特殊字符)
    α
    β
- hi

这个数据结构也被称为前缀树.

PART4. Echo的路由树实现

4.1 Router

在之前的框架概览部分讲到过,Echo结构体中的routers字段表示根据Host将路由树隔离,可以看做是类似namespace之类的概念,既是一种组织方式,也是一种隔离机制;而router字段表示路由树

type Echo struct {
	// some other fields
	router           *Router
	routers          map[string]*Router
	// some other fields
}

注意和Beego的HTTP动词不同,Echo.routers字段的map[string]*Router中,key表示Host

而Router结构体表示路由注册中心,其中维护了路由树(routes字段)

Router struct {
	tree   *node
	routes map[string]*Route
	echo   *Echo
}

4.2 Route

Route结构体表示具体的路由:

Route struct {
	Method string `json:"method"`
	Path   string `json:"path"`
	Name   string `json:"name"`
}

4.3 node

node结构体也是常规的树节点设计,内部也采用的是children字段来表示子节点的数据

node struct {
	kind           kind
	label          byte
	prefix         string
	parent         *node
	staticChildren children
	originalPath   string
	methods        *routeMethods
	paramChild     *node
	anyChild       *node
	paramsCount    int
	// isLeaf indicates that node does not have child routes
	isLeaf bool
	// isHandler indicates that node has at least one handler registered to it
	isHandler bool

	// notFoundHandler is handler registered with RouteNotFound method and is executed for 404 cases
	notFoundHandler *routeMethod
}