post方法就反回了一個string字符串前臺怎么接_Golang Web入門（2）：如何實現一個RESTful風格的路由...

摘要

在上一篇文章中，我們聊了聊在Golang中怎么實現一個Http服務器。但是在最后我們可以發現，固然DefaultServeMux可以做路由分發的功能，但是他的功能同樣是不完善的。

由DefaultServeMux做路由分發，是不能實現RESTful風格的API的，我們沒有辦法定義請求所需的方法，也沒有辦法在API路徑中加入query參數。其次，我們也希望可以讓路由查找的效率更高。

所以在這篇文章中，我們將分析httprouter這個包，從源碼的層面研究他是如何實現我們上面提到的那些功能。并且，對于這個包中最重要的前綴樹，本文將以圖文結合的方式來解釋。

1 使用

我們同樣以怎么使用作為開始，自頂向下的去研究httprouter。我們先來看看官方文檔中的小例子：

package?main

import?(
????"fmt"
????"net/http"
????"log"

????"github.com/julienschmidt/httprouter"
)

func?Index(w?http.ResponseWriter,?r?*http.Request,?_?httprouter.Params)?{
????fmt.Fprint(w,?"Welcome!\n")
}

func?Hello(w?http.ResponseWriter,?r?*http.Request,?ps?httprouter.Params)?{
????fmt.Fprintf(w,?"hello,?%s!\n",?ps.ByName("name"))
}

func?main()?{
????router?:=?httprouter.New()
????router.GET("/",?Index)
????router.GET("/hello/:name",?Hello)

????log.Fatal(http.ListenAndServe(":8080",?router))
}

其實我們可以發現，這里的做法和使用Golang自帶的net/http包的做法是差不多的。都是先注冊相應的URI和函數，換一句話來說就是將路由和處理器相匹配。

在注冊的時候，使用router.XXX方法，來注冊相對應的方法，比如GET，POST等等。

注冊完之后，使用http.ListenAndServe開始監聽。

至于為什么，我們會在后面的章節詳細介紹，現在只需要先了解做法即可。

2 創建

我們先來看看第一行代碼，我們定義并聲明了一個Router。下面來看看這個Router的結構，這里把與本文無關的其他屬性省略：

type?Router?struct?{
????//這是前綴樹，記錄了相應的路由
????trees?map[string]*node

????//記錄了參數的最大數目
????maxParams??uint16

}

在創建了這個Router的結構后，我們就使用router.XXX方法來注冊路由了。繼續看看路由是怎么注冊的：

func?(r?*Router)?GET(path?string,?handle?Handle)?{
????r.Handle(http.MethodGet,?path,?handle)
}

func?(r?*Router)?POST(path?string,?handle?Handle)?{
????r.Handle(http.MethodPost,?path,?handle)
}

...

在這里還有一長串的方法，他們都是一樣的，調用了

r.Handle(http.MethodPost,?path,?handle)

這個方法。我們再來看看：

func?(r?*Router)?Handle(method,?path?string,?handle?Handle)?{
????...
????if?r.trees?==?nil?{
????????r.trees?=?make(map[string]*node)
????}

????root?:=?r.trees[method]
????if?root?==?nil?{
????????root?=?new(node)
????????r.trees[method]?=?root

????????r.globalAllowed?=?r.allowed("*",?"")
????}

????root.addRoute(path,?handle)
????...
}

在這個方法里，同樣省略了很多細節。我們只關注一下與本文有關的。我們可以看到，在這個方法中，如果tree還沒有初始化，則先初始化這顆前綴樹。

然后我們注意到，這顆樹是一個map結構。也就是說，一個方法，對應了一顆樹。然后，對應這棵樹，調用addRoute方法，把URI和對應的Handle保存進去。

3 前綴樹

3.1 定義

又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和保存大量的字符串(但不僅限于字符串)，所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。

簡單的來講，就是要查找什么，只要跟著這棵樹的某一條路徑找，就可以找得到。

比如在搜索引擎中，你輸入了一個蔡：

他會有這些聯想，也可以理解為是一個前綴樹。

再舉個例子：

在這顆GET方法的前綴樹中，包含了以下的路由：

/wow/awesome
/test
/hello/world
/hello/china
/hello/chinese ?

說到這里你應該可以理解了，在構建這棵樹的過程中，任何兩個節點，只要有了相同的前綴，相同的部分就會被合并成一個節點。

3.2 圖解構建

上面說的addRoute方法，就是這顆前綴樹的插入方法。假設現在數為空，在這里我打算以圖解的方式來說明這棵樹的構建。

假設我們需要插入的三個路由分別為：

/hello/world
/hello/china
/hello/chinese ?

(1)插入/hello/world ?

因為此時樹為空，所以可以直接插入：

(2)插入/hello/china ?

此時，發現/hello/world和/hello/china有相同的前綴/hello/。

那么要先將原來的/hello/world結點，拆分出來，然后將要插入的結點/hello/china，截去相同部分，作為/hello/world的子節點。

(3)插入/hello/chinese ?

此時，我們需要插入/hello/chinese，但是發現，/hello/chinese和結點/hello/有公共的前綴/hello/，所以我們去查看/hello/這個結點的子節點。

注意，在結點中有一個屬性，叫indices。它記錄了這個結點的子節點的首字母，便于我們查找。比如這個/hello/結點，他的indices值為wc。而我們要插入的結點是/hello/chinese，除去公共前綴后，chinese的第一個字母也是c，所以我們進入china這個結點。

這時，有沒有發現，情況回到了我們一開始插入/hello/china時候的局面。那個時候公共前綴是/hello/，現在的公共前綴是chin。

所以，我們同樣把chin截出來，作為一個結點，將a作為這個結點的子節點。并且，同樣把ese也作為子節點。

3.3 總結構建算法

到這里，構建就已經結束了。我們來總結一下算法。

具體帶注釋的代碼將在本文最末尾給出，如果想要了解的更深可以自行查看。在這里先理解這個過程：

(1)如果樹為空，則直接插入 ?
(2)否則，查找當前的結點是否與要插入的URI有公共前綴
(3)如果沒有公共前綴，則直接插入
(4)如果有公共前綴，則判斷是否需要分裂當前的結點 ?
(5)如果需要分裂，則將公共部分作為父節點，其余的作為子節點 ?
(6)如果不需要分裂，則尋找有無前綴相同的子節點 ?
(7)如果有前綴相同的，則跳到(4) ?
(8)如果沒有前綴相同的，直接插入 ?
(9)在最后的結點，放入這條路由對應的Handle

但是到了這里，有同學要問了：怎么這里的路由，不帶參數的呀？ ?

其實只要你理解了上面的過程，帶參數也是一樣的。邏輯是這樣的：在每次插入之前，會掃描當前要插入的結點的path是否帶有參數(即掃描有沒有/或者*)。如果帶有參數的話，將當前節點的wildChild屬性設置為true，然后將參數部分，設置為一個新的子節點。

4 監聽

在講完了路由的注冊，我們來聊聊路由的監聽。

在上一篇文章的內容中，我們有提到這個：

type?serverHandler?struct?{
????srv?*Server
}

func?(sh?serverHandler)?ServeHTTP(rw?ResponseWriter,?req?*Request)?{
????handler?:=?sh.srv.Handler
????if?handler?==?nil?{
????????handler?=?DefaultServeMux
????}
????if?req.RequestURI?==?"*"?&&?req.Method?==?"OPTIONS"?{
????????handler?=?globalOptionsHandler{}
????}
????handler.ServeHTTP(rw,?req)
}

當時我們提到，如果我們不傳入任何的Handle方法，Golang將使用默認的DefaultServeMux方法來處理請求。而現在我們傳入了router，所以將會使用router來處理請求。

因此，router也是實現了ServeHTTP方法的。我們來看看(同樣省略了一些步驟)：

func?(r?*Router)?ServeHTTP(w?http.ResponseWriter,?req?*http.Request)?{
????...
????path?:=?req.URL.Path

????if?root?:=?r.trees[req.Method];?root?!=?nil?{
????????if?handle,?ps,?tsr?:=?root.getValue(path,?r.getParams);?handle?!=?nil?{
????????????if?ps?!=?nil?{
????????????????handle(w,?req,?*ps)
????????????????r.putParams(ps)
????????????}?else?{
????????????????handle(w,?req,?nil)
????????????}
????????????return
????????}?
????}
????...
????//?Handle?404
????if?r.NotFound?!=?nil?{
????????r.NotFound.ServeHTTP(w,?req)
????}?else?{
????????http.NotFound(w,?req)
????}
}

在這里，我們選擇請求方法所對應的前綴樹，調用了getValue方法。

簡單解釋一下這個方法：在這個方法中會不斷的去匹配當前路徑與結點中的path，直到找到最后找到這個路由對應的Handle方法。

注意，在這期間，如果路由是RESTful風格的，在路由中含有參數，將會被保存在Param中，這里的Param結構如下：

type?Param?struct?{
????Key???string
????Value?string
}

如果未找到相對應的路由，則調用后面的404方法。

5 處理

到了這一步，其實和以前的內容幾乎一樣了。

在獲取了該路由對應的Handle之后，調用這個函數。

唯一和之前使用net/http包中的Handler不一樣的是，這里的Handle，封裝了從API中獲取的參數。

type?Handle?func(http.ResponseWriter,?*http.Request,?Params)

6 寫在最后

謝謝你能看到這里~

至此，httprouter介紹完畢，最關鍵的也就是前綴樹的構建了。在上面我用圖文結合的方式，模擬了一次前綴樹的構建過程，希望可以讓你理解前綴樹是怎么回事。當然，如果還有疑問，也可以留言或者在微信中與我交流~

當然，如果你不滿足于此，可以看看后面的附錄，有前綴樹的全代碼注釋。

當然了，作者也是剛入門。所以，可能會有很多的疏漏。如果在閱讀的過程中，有哪些解釋不到位，或者理解出現了偏差，也請你留言指正。

再次感謝~

PS：如果覺得公眾號閱讀代碼困難，可以點擊閱讀原文去掘金閱讀。

7 源碼閱讀

7.1 樹的結構

type?node?struct?{

????path??????string????//當前結點的URI
????indices???string????//子結點的首字母
????wildChild?bool??????//子節點是否為參數結點
????nType?????nodeType??//節點類型
????priority??uint32????//權重
????children??[]*node???//子節點
????handle????Handle????//處理器
}

7.2 addRoute

func?(n?*node)?addRoute(path?string,?handle?Handle)?{

????fullPath?:=?path
????n.priority++

????//?如果這是個空樹，那么直接插入
????if?len(n.path)?==?0?&&?len(n.indices)?==?0?{

????????//這個方法其實是在n這個結點插入path，但是會處理參數
????????//詳細實現在后文會給出
????????n.insertChild(path,?fullPath,?handle)
????????n.nType?=?root
????????return
????}

????//設置一個flag
walk:
????for?{
????????//?找到當前結點path和要插入的path中最長的前綴
????????//?i為第一位不相同的下標
????????i?:=?longestCommonPrefix(path,?n.path)

????????//?此時相同的部分比這個結點記錄的path短
????????//?也就是說需要把當前的結點分裂開
????????if?i?len(n.path)?{
????????????child?:=?node{

????????????????//?把不相同的部分設置為一個切片，作為子節點
????????????????path:??????n.path[i:],
????????????????wildChild:?n.wildChild,
????????????????nType:?????static,
????????????????indices:???n.indices,
????????????????children:??n.children,
????????????????handle:????n.handle,
????????????????priority:??n.priority?-?1,
????????????}

????????????//?將新的結點作為這個結點的子節點
????????????n.children?=?[]*node{&child}
????????????//?把這個結點的首字母加入indices中
????????????//?目的是查找更快
????????????n.indices?=?string([]byte{n.path[i]})
????????????n.path?=?path[:i]
????????????n.handle?=?nil
????????????n.wildChild?=?false
????????}

????????//?此時相同的部分只占了新URI的一部分
????????//?所以把path后面不相同的部分要設置成一個新的結點
????????if?i?len(path)?{
????????????path?=?path[i:]

????????????//?此時如果n的子節點是帶參數的
????????????if?n.wildChild?{
????????????????n?=?n.children[0]
????????????????n.priority++

????????????????//?判斷是否會不合法
????????????????if?len(path)?>=?len(n.path)?&&?n.path?==?path[:len(n.path)]?&&
????????????????????n.nType?!=?catchAll?&&
????????????????????(len(n.path)?>=?len(path)?||?path[len(n.path)]?==?'/')?{
????????????????????continue?walk
????????????????}?else?{
????????????????????pathSeg?:=?path
????????????????????if?n.nType?!=?catchAll?{
????????????????????????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?+
????????????????????????"'")
????????????????}
????????????}

????????????//?把截取的path的第一位記錄下來
????????????idxc?:=?path[0]

????????????//?如果此時n的子節點是帶參數的
????????????if?n.nType?==?param?&&?idxc?==?'/'?&&?len(n.children)?==?1?{
????????????????n?=?n.children[0]
????????????????n.priority++
????????????????continue?walk
????????????}

????????????//?這一步是檢查拆分出的path，是否應該被合并入子節點中
????????????//?具體例子可看上文中的圖解
????????????//?如果是這樣的話，把這個子節點設置為n，然后開始一輪新的循環
????????????for?i,?c?:=?range?[]byte(n.indices)?{
????????????????if?c?==?idxc?{
????????????????????//?這一部分是為了把權重更高的首字符調整到前面
????????????????????i?=?n.incrementChildPrio(i)
????????????????????n?=?n.children[i]
????????????????????continue?walk
????????????????}
????????????}

????????????//?如果這個結點不用被合并
????????????if?idxc?!=?':'?&&?idxc?!=?'*'?{
????????????????//?把這個結點的首字母也加入n的indices中
????????????????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
????????}

????????//?直接插入到當前的結點
????????if?n.handle?!=?nil?{
????????????panic("a?handle?is?already?registered?for?path?'"?+?fullPath?+?"'")
????????}
????????n.handle?=?handle
????????return
????}
}

7.3 insertChild

func?(n?*node)?insertChild(path,?fullPath?string,?handle?Handle)?{
????for?{
????????//?這個方法是用來找這個path是否含有參數的
????????wildcard,?i,?valid?:=?findWildcard(path)
????????//?如果不含參數，直接跳出循環，看最后兩行
????????if?i?0?{
????????????break
????????}

????????//?條件校驗
????????if?!valid?{
????????????panic("only?one?wildcard?per?path?segment?is?allowed,?has:?'"?+
????????????????wildcard?+?"'?in?path?'"?+?fullPath?+?"'")
????????}

????????//?同樣判斷是否合法
????????if?len(wildcard)?2?{
????????????panic("wildcards?must?be?named?with?a?non-empty?name?in?path?'"?+?fullPath?+?"'")
????????}

????????if?len(n.children)?>?0?{
????????????panic("wildcard?segment?'"?+?wildcard?+
????????????????"'?conflicts?with?existing?children?in?path?'"?+?fullPath?+?"'")
????????}

????????//?如果參數的第一位是`:`，則說明這是一個參數類型
????????if?wildcard[0]?==?':'?{
????????????if?i?>?0?{
????????????????//?把當前的path設置為參數之前的那部分
????????????????n.path?=?path[:i]
????????????????//?準備把參數后面的部分作為一個新的結點
????????????????path?=?path[i:]
????????????}

????????????//然后把參數部分作為新的結點
????????????n.wildChild?=?true
????????????child?:=?&node{
????????????????nType:?param,
????????????????path:??wildcard,
????????????}
????????????n.children?=?[]*node{child}
????????????n?=?child
????????????n.priority++

????????????//?這里的意思是，path在參數后面還沒有結束
????????????if?len(wildcard)?len(path)?{
????????????????//?把參數后面那部分再分出一個結點，continue繼續處理
????????????????path?=?path[len(wildcard):]
????????????????child?:=?&node{
????????????????????priority:?1,
????????????????}
????????????????n.children?=?[]*node{child}
????????????????n?=?child
????????????????continue
????????????}

????????????//?把處理器設置進去
????????????n.handle?=?handle
????????????return

????????}?else?{?//?另外一種情況
????????????if?i+len(wildcard)?!=?len(path)?{
????????????????panic("catch-all?routes?are?only?allowed?at?the?end?of?the?path?in?path?'"?+?fullPath?+?"'")
????????????}

????????????if?len(n.path)?>?0?&&?n.path[len(n.path)-1]?==?'/'?{
????????????????panic("catch-all?conflicts?with?existing?handle?for?the?path?segment?root?in?path?'"?+?fullPath?+?"'")
????????????}

????????????//?判斷在這之前有沒有一個/
????????????i--
????????????if?path[i]?!=?'/'?{
????????????????panic("no?/?before?catch-all?in?path?'"?+?fullPath?+?"'")
????????????}

????????????n.path?=?path[:i]

????????????//?設置一個catchAll類型的子節點
????????????child?:=?&node{
????????????????wildChild:?true,
????????????????nType:?????catchAll,
????????????}
????????????n.children?=?[]*node{child}
????????????n.indices?=?string('/')
????????????n?=?child
????????????n.priority++

????????????//?把后面的參數部分設置為新節點
????????????child?=?&node{
????????????????path:?????path[i:],
????????????????nType:????catchAll,
????????????????handle:???handle,
????????????????priority:?1,
????????????}
????????????n.children?=?[]*node{child}

????????????return
????????}
????}

????//?對應最開頭的部分，如果這個path里面沒有參數，直接設置
????n.path?=?path
????n.handle?=?handle
}