概要
この記事はURLルーティング自作入門 エピソード１の続きで、Makuake Development Team Advent Calendar 2019の15日目となります。
URLルーティングを自作する
前回の続きです。
ルーターを自作するにあたり、ルーターがどういった処理を行うのかデータ構造の観点から考えてみます。
ルーターがどんなInputを受け取って、どんなOutputを返すのか、動的なルーティングの場合の例を図示してみました。
URLのパス部分をInputとして受け取り、パスとマッチするデータを判定してOuputして次の処理につなげる、というのルーターの役割です。
どのようにパスのマッチングを行うのかというのが実装の根幹となる部分になります。
ルーターを導入する上でのコンテキスト（アプリケーションの規模感だったり、アーキテクチャの方向性だったり、、）によってルーターに求めるパフォーマンスは様々かと思いますが、ここでは正規表現だけによるマッチング処理ではなく、木構造を用いたマッチング処理を実装していく方向で考えてみたいと思います。※
※その昔正規表現ベースのbmf-san/bmf-react-routerというReactで使うライブラリを書いたことがある。path-to-regexpという便利なライブラリの恩恵に授かっただけなので、マッチング処理がラッピングされた単なるコンポーネントですが...
では木構造について簡単に説明します。
木構造とは、根（Root）、枝（Edge）、節点（Node）、葉（Leaf 終端の節点のこと）を持つデータ構造のことです。データの格納方法や探索方法のパターンにより様々な種類の木構造があります。URLルーティングでは文字列を主に扱いたいので、文字列探索に特化したトライ木というデータ構造を採用します。 トライ木についてはbmf-tech.com - A Trie implementation in Golangを参照してください。
トライ木をカスタマイズして、URLのパスマッチングのためのデータを以下のように格納します。
例として、GETのみに対応するルーティングを定義しています。
/foo//baz//foo/bar//foo/:name[string]//foo/bar/:id[int]
根の直下にHTTPメソッド分ノードを生やし、それぞれのHTTPメソッドごとにパスを格納している形になります。:から始まるノードはパスパラメータを保存するノードで、[int]というDSLは正規表現をそのパラメータに対応させるためのものになります。Outputにつながる値（基本的には値を関数呼び出しするところまでルーターの責務かと思います）は各ノードが保持していたり、保持していなかったりします。これは予め定義するルーティングの内容次第です。
ルーティングの定義を元に、上で定義したデータ構造を再現するコードをかくことができれば、あとはルーターを利用するクライアントのためのコードを書くことで理論上は自作できます。理論上は。※
※実装しているものがあるのだが、まだ途中なので・・Qiita - Go6 Advent Calendar 2019の20日目までに頑張る。
後半は飛ばし気味で雑になってしまいましたが、イメージが分かればコードを書くだけなので、自作できたも同然です（）。
今回はトライ木のオレオレ拡張みたいなデータ構造を説明しましたが、メモリ効率とかをより意識するならパトリシア木という木構造を採用すると良さそうです。Golangの実装を漁っていたとき採用しているのを散見しました。
筆者はパトリシア木の実装に挑戦したことがあるのですが、一度挫折してしまったのでそのうちまた挑戦したいと思います。。。※
※パトリシア木のコードを読めばわかると思いきや、単純なトライ木とは違って実装パターンが「みんな違ってみんないい」みたいになっているので、パトリシア木というデータ構造をちゃんと腹落ちさせて実装すべきだろうと思って色々試みたのですが、難しすぎました...
所感
ルーターはOSSのライブラリとしては競合が多いジャンルだと思いますが、後発のものでも肩を並べられるようなものができればより楽しさも見える世界もまた変わると思うので、今後も飽きが来ない限りは付き合っていきたい分野です。
追記
GolangでURLルーター実装しました。