概要
この記事はURLルーティング自作入門 エピソード１の続きで、Makuake Development Team Advent Calendar 2019の15日目である。
URLルーティングを自作する
前回の続きである。
ルーターを自作するにあたり、ルーターがどういった処理を行うのかをデータ構造の観点から考えてみる。
ルーターがどんなInputを受け取って、どんなOutputを返すのか、動的なルーティングの場合の例を図示してみた。
URLのパス部分をInputとして受け取り、パスとマッチするデータを判定してOutputし、次の処理につなげるのがルーターの役割である。
どのようにパスのマッチングを行うのかが実装の根幹となる部分である。
ルーターを導入する上でのコンテキスト（アプリケーションの規模感やアーキテクチャの方向性など）によって、ルーターに求めるパフォーマンスは様々だろう。ここでは正規表現だけによるマッチング処理ではなく、木構造を用いたマッチング処理を実装していく方向で考える※。
※その昔、正規表現ベースの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ルーター実装しました。
