Elixir + D3.js で GitHub の awesome リストを可視化する

[GitHub の awesome リスト](https://github.com/sindresorhus/awesome)って、いい感じに重要な技術要素がキュレーションされていて便利ですよね。
個人的にはプログラミング言語のキュレーションが好きで、各言語のライブラリの流行をチェックしたりしています。

今回はそんな awesome programming languages を、Elixir での文字列操作の勉強も兼ねて可視化してみます。

ちなみに完成イメージはこんな感じです。

[<img width="500" alt="cap1.png" src="https://qiita-image-store.s3.amazonaws.com/0/77513/46eccfd8-8df9-b253-f7fa-4089d8f1edbb.png">](http://mserizawa.github.io/awesome-programming-languages/)


# 事前準備 1: 可視化手法の検討

完成イメージの通り、[D3.js の Radial Reingold–Tilford Tree](http://bl.ocks.org/mbostock/4063550) を使います。

「Elixir -> Frameworks -> Phoenix」のようなライブラリの階層構造が、上記リンクのような図で一気に描画されるイメージです。

ちなみに、**階層のルートは各プログラミング言語**です。「Language -> Elixir -> ...」のような可視化も考えたのですが、要素数が多すぎて訳が分からなくなったのでやめました。

また、今回はどちらかというと Elixir での文字列操作が主軸なので、D3.js はほぼ上記リンクの実装ままで、出来上がった JSON を食わせて微調整して完成、という流れに持っていこうと思います。

# 事前準備 2: パース方法の検討

今回パース対象とする各 awesome の README.md は、文字通り Markdown で書かれています。
Markdown を HTML に落とし込んで、DOM セレクタを駆使してパース、とかも考えたのですが、冷静に考えて無駄に大変そうなので、シンプルに一行ずつ解析していくことにします。

上記の可視化に必要な JSON は以下のような形式です。

```js
{
 "name": "flare",  // 今回の場合はここがプログラミング言語の名前になります
 "children": [
  {
   "name": "analytics",
   "children": [
    {
     "name": "cluster",
     "children": [
      // 今回の場合はここの要素がライブラリなどの情報になります
      // これらの要素に description と url を加えます
      {"name": "AgglomerativeCluster", "size": 3938},
      {"name": "CommunityStructure", "size": 3812},
      ...
     ]
    },
  },
  ...
}
```

この JSON に落とし込むため、以下のルールで各行を処理します。

* ヘッダ行（# 始まり）の場合
    * # の数を見て階層を調整（上る・下る・留まる）
    * # 以降の文字列で *name* を形成
* リスト行（-, * 始まり）の場合
    * *chilren* に要素を追加
    * -, * 以降の文字列を分解して、*name*, *description*, *url* を形成
    * *size* は固定で 1
* それ以外の場合
    * スルー

# アプリケーションをセットアップする

mix を使ってアプリケーションを作成しましょう。

```bash
$ mix new awesome_parser
```

`mix.exs` に利用するライブラリを追記します。

```ex:mix.exs
defmodule AwesomeParser.Mixfile do
  use Mix.Project
  ...
  def application do
    # :httpoison を追加
    [applications: [:logger, :httpoison]]
  end
  ...
  defp deps do
    # :httpoison と :poison を追加
    [{:httpoison, "~> 0.7.4"},
     {:poison, "~> 1.5"}]
  end
end
```

これらのライブラリをダウンロードしてセットアップ完了です。

```bash
$ mix deps.get
```

# GitHub から README.md をロードする

早速 `lib/awesome_parser.ex` に処理を書いていきましょう。
まずは GitHub に HTTP リクエストを投げて README.md を取得します。

```ex:awesome_parser.ex
defmodule AwesomeParser do
  def process(repository_url) do
    response = HTTPoison.get!(repository_url)

    case response do
      %{status_code: 200, body: body} ->
        lines = String.split(body, "\n")

      _ ->
        IO.puts "An error occurred while reading repository: #{repository_url}"
    end
  end
end
```

**repository_url** には `https://raw.githubusercontent.com/h4cc/awesome-elixir/master/README.md` といった、README.md の生データに対する URL を渡します。それを HTTPoison を使って取得して、`\n` でスプリットします。

実際は各言語を一気にパースするため、レポジトリのリストから URL を生成する関数でラップしたりするのですが、今回は割愛します。

# １行ずつパースして JSON にまとめる

次に、スプリットされた各行を上記のルールにしたがってパースしていきます。
普通なら「ループ構文」の利用が思い浮かぶのですが、ここは折角なので Elixir っぽく「[再帰 & パターンマッチング & ガード](http://elixir-ja.sena-net.works/getting_started/9.html)」で実装しましょう。

ざっと、こんな感じです（ちょっとカオスったかも...）

```ex:awesome_parser.ex
defmodule AwesomeCrawler do

  # ヘッダ行を階層数と名前に分解します
  def parse_header_line(header) do
    # 正規表現を使って各要素を取得します
    captures = Regex.named_captures(~r"^.*(?<hashes>#+) *(?<name>.*)$", String.strip(header))
    %{level: String.length(captures["hashes"]), name: captures["name"]}
  end

  # 階層が深くなるケースをハンドリングします
  def parse_lines([_head | tail],
      %{level: level, next_level: next_level} = params) when level < next_level do

    # 子階層を生成します
    parsed = parse_lines(tail, %{name: params[:next_name], level: next_level, items: []})
    # 生成された子階層を append します（items が空だった場合は除きます）
    filtered = Enum.filter(params[:items] ++ [parsed[:elem]], fn(elem) -> length(Dict.get(elem, :children, [])) > 0 end)
    # 処理を続行します
    parse_lines(Dict.get(parsed, :remained, tail), %{name: params[:name], level: level, items: filtered})
  end

  # 階層が浅くなる or 同階層で新規要素を作るケースをハンドリングします
  def parse_lines([head | tail],
      %{level: level, next_level: next_level} = params) when level >= next_level do

    # 現階層の構築を終了して処理を続行させます
    %{elem: %{name: params[:name], children: params[:items]}, remained: [head | tail]}
  end

  # 各行を種別に応じてハンドリングします
  def parse_lines([head | tail], params) do
    cond do
      # ヘッダ行
      String.starts_with?(head, "#") ->
        %{level: next_level, name: next_name} = parse_header_line(head)
        # 階層の変化（下 or 上,同）に応じてさらに処理を振り分けます
        parse_lines([head | tail], Dict.merge(params, %{next_level: next_level, next_name: next_name}))

      # リスト行
      String.match?(head, ~r"^ *[\*\-].*\[.*\]\(http.*\).*$") ->
        # 正規表現を使って各要素を取得します
        captures = Regex.named_captures(~r"^ *[\*\-][^\[]*\[(?<label>[^\]]*)\]\((?<url>http[^\)]*)\)[^A-z]*(?<description>.*)$", head)
        # items に append します
        added_items = params[:items] ++ [%{name: captures["label"], url: captures["url"], description: captures["description"], size: 1}]
        # 処理を続行します
        parse_lines(tail, Dict.put(params, :items, added_items))

      # その他
      true ->
        parse_lines(tail, params)
    end
  end

  # 最終行をハンドリングします（階層処理の都合上複数回呼ばれます）
  def parse_lines([], %{name: name, level: level, items: items}) do
    cond do
      level > 0 ->
        %{elem: %{name: name, children: items}, remained: []}

      true ->
        %{name: name, children: items}
    end
  end
  ...
end
```

ポイントとしては、

* セオリー通り、`parse_lines` に各行のリストを延々と渡し１行ずつ消化していく
    * parse_lines を呼ぶ側は基本的に次の処理を知らなくて良い（どの `parse_line` を呼ぶかを考慮しなくて良い）
    * 引数の状態、解析行に応じて勝手に処理が振り分けられる、というスタンス
* 主軸となるのが `parse_lines([head | tail], params)` のパートで、ここでルールにしたがった処理のハンドリングをする
* ヘッダ行が来た場合は階層の変化に応じた複雑な分岐が必要になるため、ガードを使って `parse_line` をオーバーロードする
* 階層の末端に到達したタイミングで再帰を終了して、構築された Dict を返却する
    * その際、残った行も合わせて返却することで、呼出元でスムーズに処理を継続させる

こんな感じです。階層の変化を処理するのが以外と大変で、思いの外複雑になってしまいました。。きっと、もっとスマートな方法があるのだと思います。

ちなみに、正規表現は完璧ではありません。README.md 自体の表記に結構ブレがあり、これで拾えないケースもありました。（とりあえず Elixir の README がそれっぽくパースできればいいかなぁ程度の確認にとどめています）

最後に出来上がった Dict を Poison を使って JSON にダンプしましょう。

```ex:awesome_parser.py
defmodule AwesomeParser do
  ...
  def process(repository_url) do
    response = HTTPoison.get!(repository_url)

    case response do
      %{status_code: 200, body: body} ->
        lines = String.split(body, "\n")
        json = Poison.encode!(parse_lines(lines, %{name: "root", level: 0, items: []}))
        {:ok, file} = File.open "output.json", [:write, :utf8]
        IO.write file, json
        File.close file

      _ ->
        IO.puts "An error occurred while reading repository: #{repository_url}"
    end
  end
end
```

実行してみましょう。

```bash
$ iex -S mix
iex(1)> AwesomeParser.process("https://raw.githubusercontent.com/h4cc/awesome-elixir/master/README.md")
:ok
```

これで、[こんな感じの JSON](https://raw.githubusercontent.com/mserizawa/mserizawa.github.io/master/awesome-programming-languages/json/awesome-elixir.json) が出力されると思います。

# D3.js で描画する

後は [Radial Reingold–Tilford Tree](http://bl.ocks.org/mbostock/4063550) のソースコードをコピーして、出力された JSON を読み込む + α の改修をします。

```js
...
var diameter = 1200; // ちょっと大きめにしておいたほうが良いです
...
d3.json("output.json", function(error, root) { // 作成した JSON へのパスを書きます
...
  node.append("circle")
      .attr("r", 2.5); // 円は小さめにしておいたほうが良いです
...
  node.append("text")
      .attr("dy", "0.25em")
      .style("font-size", "6px") // 文字も小さめにしておいたほうが良いです
...
```

これで冒頭のイメージっぽい図が描画されると思います。
ちなみに、Chrome だとローカルファイルからローカルファイルへの Ajax 通信ができないので、FireFox を利用されることをオススメします。

# 仕上げ

上記の JS をさらにもうちょっと微調整するとこんな感じにインタラクティブに仕上がります。

http://mserizawa.github.io/awesome-programming-languages/

（Retina じゃない端末 + Chrome の組み合わせで見ると微妙に表示崩れします）

# 感想

* 再帰 + パターンマッチングは非常に強力な概念
    * if やループがなくても実装ができてしまう
    * つまり、ネストが深くならなくてすむ
* ただ、可読性のあるソースコードを書くには修行が必要...
    * どういう条件で分岐されてくるのかがパッと見で分かりづらくなる
    * 処理のフローも分かりづらくなる
    * パーサ系ライブラリのソースコードを見て研究する必要アリ