簡述
關(guān)于go的web開發(fā)框架冲茸，主要是兩大類屯阀。一類以beego為主缅帘，功能全，配置多难衰，大而全钦无；一類是以gin為主的，基于httprouter進(jìn)行開發(fā)盖袭，輕而快失暂。這個(gè)無所謂好壞，全看個(gè)人選擇鳄虱。今天主要說httprouter是如何實(shí)現(xiàn)弟塞。
httprouter支持參數(shù)類型的URL（
/user/:id）也支持*的通配符URL（/static/*file）。httprouter使用radix tree（前綴樹）對請求的URL進(jìn)行管理拙已，最差時(shí)間復(fù)雜度為O(n)决记，n為URL長度。
httprouter對每種請求方法都會建立一個(gè)tree進(jìn)行管理倍踪。例如所有的GET請求會都用一個(gè)tree系宫，所有的POST用一個(gè)tree，所有的PUT一個(gè)tree......
當(dāng)同時(shí)使用GET方式添加路由
/ff/:id和/ff/kk時(shí)建车，會拋出panic: 'kk' in new path '/ff/kk' conflicts with existing wildcard ':id' in existing prefix '/ff/:id'扩借。是因?yàn)樵贕ET的tree上面，前綴都是/ff的情況下缤至，參數(shù)類型的:id和具體的路由字段kk沖突潮罪。
關(guān)于httprouter目錄
項(xiàng)目總共三個(gè)文件router.go、tree.go领斥、path.go错洁，其中router.go是主文件，路由的添加戒突、異常路由的處理等基本設(shè)置在此完成屯碴，調(diào)用httprouter.New() 返回一個(gè)Router結(jié)構(gòu)的指針。tree.go負(fù)責(zé)前綴樹的操作膊存，包括將路由添加到前綴樹中导而，從樹中查詢到URL對應(yīng)的handler。path.go主要包含CleanPath方法隔崎，返回一個(gè)符合規(guī)范的URL今艺。
關(guān)于router.go 中的 Router結(jié)構(gòu)
type Router struct {
//前綴樹的結(jié)構(gòu)
trees map[string]*node
paramsPool sync.Pool
maxParams uint16
//如果無法匹配到當(dāng)前路由，但是存在帶有（不帶）尾部斜杠的路由時(shí)爵卒，是否自動重定向
//例如虚缎，如果請求了/foo/,但是只存在/foo的路由，那么將301重定向到 /foo
RedirectTrailingSlash bool
//是否修正路徑钓株，主要依靠path.go 的 CleanPath 方法
RedirectFixedPath bool
//如果無法匹配到當(dāng)前路由, 那么檢查是否有其他方法能否拼配到當(dāng)前的路由
HandleMethodNotAllowed bool
//是否允許路由自動拼配到options
HandleOPTIONS bool
//全局的options操作实牡，可以設(shè)置CORS時(shí)調(diào)用
GlobalOPTIONS http.Handler
globalAllowed string
//當(dāng)沒有匹配到路由的時(shí)候, 執(zhí)行這個(gè)handler. 如果沒有配置,那么返回NotFound
NotFound http.Handler
//當(dāng)沒有匹配到路由并且HandleMethodNotAllowed=true的時(shí)候,這個(gè)函數(shù)被使用
MethodNotAllowed http.Handler
PanicHandler func(http.ResponseWriter, *http.Request, interface{})
}
這其中最重要的就是trees節(jié)點(diǎn)陌僵，路由的添加、查找都是通過這個(gè)操作完成创坞。
關(guān)于node的結(jié)構(gòu)
type node struct {
//當(dāng)前node 的路徑
path string
// children對應(yīng)的索引碗短，保存的是分裂分支的第一個(gè)字符
indices string
//判斷子節(jié)點(diǎn)是否為通配節(jié)點(diǎn)，（包括：param题涨、catchAll）
wildChild bool
//節(jié)點(diǎn)類型偎谁。
//root： 第一個(gè)插入的節(jié)點(diǎn)
//catchAll: 有* 匹配的節(jié)點(diǎn)
//param：參數(shù)節(jié)點(diǎn) :id
//static： 靜態(tài)節(jié)點(diǎn)，前幾個(gè)剩下的都是靜態(tài)節(jié)點(diǎn)
nType nodeType
// 優(yōu)先級
priority uint32
//子節(jié)點(diǎn)
children []*node
//當(dāng)前節(jié)點(diǎn)的處理函數(shù)
handle Handle
}
node示意圖
例如GET請求纲堵，/search/:id/info巡雨、/status/:id/info、/user/getall
httprouter.png
關(guān)于addRoute
當(dāng)調(diào)用
GET添加路由時(shí)席函，走的是Router的Handle方法鸯隅。同樣，post向挖、put蝌以、delete等也是一樣
而Handle最后走向addRoute。
addRoute 的基本思路就是先尋找路由的最長公共前綴何之，找到對應(yīng)的節(jié)點(diǎn)位置跟畅，然后調(diào)用insertChild,插入到對應(yīng)的node中。
- tree是一個(gè)空樹時(shí)溶推，那么當(dāng)前URL直接插入path徊件，nType為root
- tree不為空時(shí)，如果匹配的最長前綴小于當(dāng)前節(jié)點(diǎn)path的長度蒜危，那么說明當(dāng)前節(jié)點(diǎn)需要進(jìn)行調(diào)整虱痕。最長公共前綴作為節(jié)點(diǎn)的path，原先節(jié)點(diǎn)成為最長公共前綴的子節(jié)點(diǎn)辐赞。
- tree不為空時(shí)部翘，如果匹配的最長前綴小于傳入的path的長度，說明需要在當(dāng)前節(jié)點(diǎn)下响委，添加一個(gè)新的子節(jié)點(diǎn)新思。當(dāng)然這里可能會有循環(huán)遞歸。
- tree不為空時(shí)赘风，如果匹配的最長前綴等于path夹囚，那么就是在此節(jié)點(diǎn)直接添加handler操作。
代碼說明
// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, handle Handle) {
fullPath := path
n.priority++
// Empty tree
if len(n.path) == 0 && len(n.indices) == 0 {
n.insertChild(path, fullPath, handle)
n.nType = root
return
}
walk:
for {
// Find the longest common prefix.
// This also implies that the common prefix contains no ':' or '*'
// since the existing key can't contain those chars.
// 尋找傳入的路由與節(jié)點(diǎn)的最長公共前綴
i := longestCommonPrefix(path, n.path)
// Split edge--分割 邊際
// 如果最長前綴的長度 < 節(jié)點(diǎn)長度
if i < len(n.path) {
//那么當(dāng)前節(jié)點(diǎn)的path就應(yīng)該是最長前綴邀窃，原先的節(jié)點(diǎn)是最長前綴的子節(jié)點(diǎn)
child := node{
//節(jié)點(diǎn)的路徑就是 當(dāng)前節(jié)點(diǎn)后段字符串
path: n.path[i:],
wildChild: n.wildChild,
nType: static,
indices: n.indices,
children: n.children,
handle: n.handle,
priority: n.priority - 1,
}
//剛分裂的節(jié)點(diǎn)荸哟，作為新節(jié)點(diǎn)的子節(jié)點(diǎn)
n.children = []*node{&child}
// []byte for proper unicode char conversion, see #65
n.indices = string([]byte{n.path[i]})
n.path = path[:i]
n.handle = nil
n.wildChild = false
}
// Make new node a child of this node ----為當(dāng)前節(jié)點(diǎn)創(chuàng)建一個(gè)新的子節(jié)點(diǎn)
//如果最長前綴 < 路徑的長度
//除了tree為空的情況外，只有在這個(gè)判斷下才會走 insertChild ，創(chuàng)建新節(jié)點(diǎn)
if i < len(path) {
path = path[i:]
//如果子節(jié)點(diǎn)是參數(shù)節(jié)點(diǎn)
if n.wildChild {
n = n.children[0]
n.priority++
// Check if the wildcard matches
// 如果子節(jié)點(diǎn)是通配節(jié)點(diǎn)鞍历，需要驗(yàn)證合法性
if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
// Adding a child to a catchAll is not possible
n.nType != catchAll &&
// Check for longer wildcard, e.g. :name and :names
(len(n.path) >= len(path) || path[len(n.path)] == '/') {
continue walk
} else {
// Wildcard conflict
// 通配符沖突
pathSeg := path
if n.nType != catchAll {
// SplitN 根據(jù)/分割字符串舵抹，最多2個(gè)
pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
}
prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
panic("'" + pathSeg +
"' in new path '" + fullPath +
"' conflicts with existing wildcard '" + n.path +
"' in existing prefix '" + prefix +
"'")
}
}
idxc := path[0]
// '/' after param --
if n.nType == param && idxc == '/' && len(n.children) == 1 {
n = n.children[0]
n.priority++
continue walk
}
// Check if a child with the next path byte exists
//判斷當(dāng)前節(jié)點(diǎn)的 indices 索引中是否存在當(dāng)前path的首字母
for i, c := range []byte(n.indices) {
if c == idxc {
i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
// Otherwise insert it ---否則直接插入
if idxc != ':' && idxc != '*' {
// []byte for proper unicode char conversion, see #65
n.indices += string([]byte{idxc})
child := &node{}
n.children = append(n.children, child)
n.incrementChildPrio(len(n.indices) - 1)
n = child
}
n.insertChild(path, fullPath, handle)
return
}
// Otherwise add handle to current node
//如果最長前綴 == 傳入的path，就直接在這個(gè)節(jié)點(diǎn)添加handle
if n.handle != nil {
panic("a handle is already registered for path '" + fullPath + "'")
}
n.handle = handle
return
}
}
