gin框架之路由前缀树初始化分析

见贤思齐

gin框架之路由前缀树初始化分析 gin框架之路由前缀树初始化分析 李晶@贝壳找房 贝壳产品技术 贝壳产品技术 “贝壳产品技术公众号”作为贝壳官方产品技术号，致力打造贝壳产品、技术干货分享平台，面向互联网/O2O开发/产品从业者，每周推送优质产品技术文章、技术沙龙活动及招聘信息等。欢迎大家关注我们。 242篇内容 2020年08月07日 17:42 gin框架作为Golang的轻量级web框架，包含了路由的dispatch功能，本文将重点分析根据设置的请求path构建路由前缀树的相关功能。本文分析是基于gin 1.6.3版本的代码实现。1. 路由存储的结构和算法Engine是gin框架的实例，在Engine结构中，trees 是一个数组，针对框架支持的每一种方法，都会创建一个节点。例如GET、POST是trees的两个元素。//框架实例包含一个方法数数组typeEnginestruct{treesmethodTrees}typemethodTrees[]methodTree//方法树的定义typemethodTreestruct{methodstringroot*node}1.1前缀树节点的定义//path树的节点结构typenodestruct{pathstringindicesstringchildren[]*nodehandlersHandlersChainpriorityuint32nTypenodeTypemaxParamsuint8wildChildboolfullPathstring}方法树是通过节点包含children的节点数组的结构形成的，在node结构中：path：表示当前节点的path；indices：通常情况下维护了children列表的path的各首字符组成的string，之所以是通常情况，是在处理包含通配符的path处理中会有一些例外情况；priority：代表了有几条路由会经过此节点，用于在节点进行排序时使用；nType：是节点的类型，默认是static类型，还包括了root类型，对于path包含冒号通配符的情况，nType是 param类型，对于包含 * 通配符的情况，nType类型是 catchAll 类型；wildChild：默认是false，当children是 通配符类型时，wildChild为true；fullPath：是从root节点到当前节点的全部path部分；如果此节点为终结节点handlers为对应的处理链，否则为nil；maxParams 是当前节点到各个叶子节点的包含的通配符的最大数量。1.2一个普通的路由前缀树以如下路由配置作为示例：engine.GET("/admin/model/get",api.GetTemplate)engine.GET("/admin/model/query",api.QueryTemplate)engine.POST("/admin/model/set",api.SetTemplate)engine.POST("/admin/model/upload",api.UploadTemplate)engine.POST("/admin/model/uploadv2",api.GetTemplateWithSignature)engine.POST("/admin/model/update",api.UpdateTemplate)形成的前缀树如下图，左边是GET方法的树，右边是POST方法树。2. 路由的初始化过程路由的初始化过程，首先生成绝对path，然后调用Engine的addRoute方法，根据请求的method类型，找到根节点。再调用node的addRoute方法，将path增加到树的合适节点。这个过程是路由初始化过程中构建前缀树的核心流程。2.1Engine的addRoute方法func(engine*Engine)addRoute(method,pathstring,handlersHandlersChain){//根据调用的method获取对应的前缀树，如果为nil进行初始化root:=engine.trees.get(method)ifroot==nil{root=new(node)root.fullPath="/"engine.trees=append(engine.trees,methodTree{method:method,root:root})}//调用node的addRoute方法，其中的path是绝对的pathroot.addRoute(path,handlers)}2.2查找wildCardwildCard是指包含通配符的path段，例如path是 /:id/info 那么id代表了通配符的名字；这个方法用于查找path中是否包含 wildCard；通配支持了path上传参数，但是也增加了path设计的复杂性；如果没有通配符的设计，程序员需要定义每一个path。funcfindWildcard(pathstring)(wildcardstring,iint,validbool){forstart,c:=range[]byte(path){//如果没有遇到通配符就继续向后查找ifc!=':'&c!='*'{continue}//找到通配符设置valid为true，那么通配符在path的起始位置就是startvalid=true//从通配符后面继续查找forend,c:=range[]byte(path[start+1:]){switchc{//如果遇到下划线，返回wildCard（不包括下划线）、start、truecase'/':returnpath[start:start+1+end],start,valid//如果遇到通配符，valid设置为falsecase':','*':valid=false}}//在这个位置返回，遍历完了path，valid为true和false的可能性都有returnpath[start:],start,valid}//在path里没有找到通配符return"",-1,false}2.3增加孩子节点node的addRoute方法分为两步，第一步是根据path和已有的前缀树的匹配，找到剩余的path需要插入的孩子节点的位置，第二步是插入到该节点。当一颗树是空树时，增加第一条path的过程便退化为只有第二步。本小节先分析插入孩子节点的操作。numParams是path包含的通配符的数量，包含冒号和星号；如果path不包含通配符，直接设置当前节点的path为传入的path；按照通配符的数量逐个处理。对于通配符为冒号的处理方法，当前节点设置一个path为 wildCard的子节点，设置handler后结束；特别的如果wildCard不是path的全部，将path更新为剩余的部分，n节点指向wildCard的孩子节点继续循环。循环如果后半部分没有通配符到结尾设置path，否则继续处理通配符节点。对于通配符是星号的处理方法，校验必须是最后一个通配符，星号的前面符号是下划线，生成一个path为空的孩子节点和包含“/*name”的孙子节点。其中孩子节点wildChild设置为true，表明孩子节点是通配符类型。在冒号通配符的处理过程中，当最后的通配符处理完成，但是还有剩余path的时候，n会更新为空path的child节点，循环处理剩下的path，保证了在调用的节点path为空。func(n*node)insertChild(numParamsuint8,pathstring,fullPathstring,handlersHandlersChain){fornumParams>0{//Findprefixuntilfirstwildcardwildcard,i,valid:=findWildcard(path)//path中不包含通配符，直接结束对numParams条件的for循环ifi0{panic("wildcardsegment'"+wildcard+"'conflictswithexistingchildreninpath'"+fullPath+"'")}//冒号类型的通配符处理ifwildcard[0]==':'{//paramifi>0{//Insertprefixbeforethecurrentwildcardn.path=path[:i]//设置当前节点的pathpath=path[i:]//更新path}//孩子节点是通配符，当前节点设置为truen.wildChild=truechild:=&node{nType:param,//冒号类型的通配符类型path:wildcard,//设置path为wildCardpath包含通配符和名字maxParams:numParams,fullPath:fullPath,}n.children=[]*node{child}//children挂接到当前节点n=child//n更新为下沉到孩子节点n.priority++numParams--//控制循环的通配符数量减1//ifthepathdoesn'tendwiththewildcard,thenthere//willbeanothernon-wildcardsubpathstartingwith'/'//如果wildCard的长度小于path，则说明path中还包含以及pathiflen(wildcard)1{panic("catch-allroutesareonlyallowedattheendofthepathinpath'"+fullPath+"'")}iflen(n.path)>0&n.path[len(n.path)-1]=='/'{panic("catch-allconflictswithexistinghandleforthepathsegmentrootinpath'"+fullPath+"'")}//星号通配符的前一个字符，必须为下划线，否则panici--ifpath[i]!='/'{panic("no/beforecatch-allinpath'"+fullPath+"'")}//当前node的path为星号通配符之前的pathn.path=path[:i]//Firstnode:catchAllnodewithemptypathchild:=&node{//一个path为空的节点wildChild:true,//空节点的wildCard为truenType:catchAll,maxParams:1,fullPath:fullPath,}//updatemaxParamsoftheparentnodeifn.maxParamsn.maxParams{n.maxParams=numParams}//Findthelongestcommonprefix.//Thisalsoimpliesthatthecommonprefixcontainsno':'or'*'//sincetheexistingkeycan'tcontainthosechars.i:=longestCommonPrefix(path,n.path)//如果path与当前的node有部分匹配，需要拆分当前的nodeifichild.maxParams{child.maxParams=v.maxParams}}n.children=[]*node{&child}//将后半部分设置为孩子节点//[]byteforproperunicodecharconversion,see#65n.indices=string([]byte{n.path[i]})n.path=path[:i]//当前节点的path只保持前半部分n.handlers=niln.wildChild=false//后半部分节点一定不包含通配符n.fullPath=fullPath[:parentFullPathIndex+i]//当前节点的fullPath截取}//Makenewnodeachildofthisnode//path没有完成匹配，需要继续向下寻找ifin.maxParams{n.maxParams=numParams}numParams--//path为通配符的时候必须一致，然后继续向后iflen(path)>=len(n.path)&n.path==path[:len(n.path)]{//checkforlongerwildcard,e.g.:nameand:names//path与当前node的path长度相同或者path有下划线，继续iflen(n.path)>=len(path)||path[len(n.path)]=='/'{continuewalk}}//其他情况会panicpathSeg:=pathifn.nType!=catchAll{pathSeg=strings.SplitN(path,"/",2)[0]}prefix:=fullPath[:strings.Index(fullPath,pathSeg)]+n.pathpanic("'"+pathSeg+"'innewpath'"+fullPath+"'conflictswithexistingwildcard'"+n.path+"'inexistingprefix'"+prefix+"'")}//当前节点的孩子节点不是通配符类型，取出第一个字符c:=path[0]//slashafterparam//冒号通配符后面的下划线处理ifn.nType==param&c=='/'&len(n.children)==1{parentFullPathIndex+=len(n.path)n=n.children[0]//更新node节点为孩子节点，继续查找n.priority++continuewalk}//Checkifachildwiththenextpathbyteexists//当前节点的某个孩子与path有相同的前缀fori,max:=0,len(n.indices);i1{panic("catch-allroutesareonlyallowedattheendofthepathinpath'"+fullPath+"'")}4.3星号通配符的一个bug对于路由【"/user/info/*name"】 和路由【"/user/info/*name/age"】，在查找的时候只会匹配成功第一个路由，但是第二个路由会新增成功。 预览时标签不可点 GO6后端27GO · 目录#GO上一篇贝壳找房小程序从PHP到Golang的跃迁之路下一篇从操作系统的角度理解Goroutine – Go 协程设计系列（1/2）关闭更多小程序广告搜索「undefined」网络结果