依存ライブラリの順番によって mix deps.get の結果が違うこともある

この記事は弊社の Advent Calender 2019 の 2 日目の記事です。入社してから一番たくさん書いた言語が Elixir なので[^1]、Elixir に関連した記事を書きたいと思います。前日の @ufoo68 さんは LINE に関連した内容を書いていてキャッチーでいいですね。対照的に、私の記事はかなりコーナーケースで地味です。。

## はじめに

タイトルをもう少し具体的に説明したいと思います。

例えば、`mix.exs` に書いてある project の config に `deps: deps()` と書いてある場合に、

```elixir
  defp deps do
    [
      {:project_x, ...},
      {:project_y, ...},
    ]
  end
```

と書くか

```elixir
  defp deps do
    [
      {:project_y, ...},
      {:project_x, ...},
    ]
  end
```

と書くかによって `$ mix deps.get` の結果が変わるケースがあります。

このようなケースは多々あると思いますが、間接的な依存ライブラリのバージョン指定が複数ある場合に問題が起きやすそうな気がしています。この記事では、そのような場合のうち、とくに以下 2 つのケースを紹介したいと思います。

- Hex に問い合わせる前にバージョン指定が複数あることが分かる場合
- `:build_embedded` が `true` の場合

まず `$ mix deps.get` の中身を説明したあとに、上の 2 つのケースについて個別に書いていきたいと思います。ちなみに、master branch の Elixir を使っています。

## `mix deps.get` の中身を調べてみる

正しく詳しい情報が欲しい方は [ここ](https://github.com/elixir-lang/elixir/blob/master/lib/mix/lib/mix/tasks/deps.get.ex) から辿っていくのが間違いないです。

### 用語

出典はありません。コードから読み取ったことを自分の言葉で書いているだけであることをご了承ください。

#### converge

間接的な依存ライブラリを含めると、一つのライブラリに対して条件指定 (specification) が複数存在することがあります。各ライブラリに対して、すべての specification を満足するような一つの specification ("converged" specification) を確定していく作業を converge と呼んでいます。逆に、この作業に失敗したライブラリは "diverged" な状態にあると言われます。

#### fetch

SCM (source code manager) を使ってライブラリを取得・更新する作業です。ライブラリが古くなければ特に何も起きません。

#### load

Fetch したライブラリの状態（すでに `*.app` が存在しているかどうかなど）や依存情報（大元の project にとっては間接的な依存情報）を読み込む作業です。

#### remote converger

Converge の一部を担う module です。

Mix 本体に予め実装されている SCM は `:path` と `:git` です。この 2 つの SCM に関連した converge の処理も Mix に実装されています。一方、Hex (package manager) も SCM として使えますが、その実装は Mix 本体とは分離しています。そのため、Hex に関連した converge のロジックを Mix 側に実装することはできません。Mix 側で `Mix.RemoteConverger` という behaviour を用意し、Hex 側でそれを実装しています。したがって、remote converger は converge の処理を外部で実装するときに使われる interface のようなものだと言えます。

### 処理の流れ

`$ mix deps.get` の目的はライブラリの取得ですが、処理の流れを考えるときはライブラリの converged specification を求めることを目標として考えると分かりやすいと思います。なお、specification という言葉を使っていますが、dependency そのもの、あるいはメタ情報全体に置き換えたほうが説明として正しい気がする箇所もあります。ですが、converge という言葉との相性を考えて specification で統一してあります。腑に落ちない方はコードをご覧ください！

`$ mix deps.get` を実行すると、依存ライブラリの木構造が幅優先探索で converge が行われていきます。各ノードにおいて、ライブラリの specification をチェックし、さらに特定の条件下では fetch と load も行います（詳しくは後述します）。

Converge は 2 つのフェーズに分かれています。一つ目が remote converger を使わないフェーズ、二つ目がそれを使うフェーズです。どちらのフェーズでも同様の幅優先探索が行われますが、その探索順序が少し変則的なので注意が必要です。

第一フェーズにおける依存木構造（ここでは `$ mix deps.tree` の出力を簡略化したものを使っています[^2]）と探索順序の例を以下に図示しました。なお、ノードに `aaa`, ..., `nnn` と記号を書きましたが、これらは依存ライブラリ名を意図しています。同じ階層に同じライブラリが存在したり、循環依存が存在したりすることにならなければ、異なる記号が同じライブラリを指しているかもしれません。例えば、`aaa` と `iii` が同じライブラリを指して (`aaa` = `iii`) いても良いということです。また、各ノードはそれぞれ specification をもっています。同じライブラリであっても specification は異なるかもしれません。

```
project
├── aaa (git@...) ------------------(1)
│   ├── bbb (Hex package) ----------(6)
│   │   ├── ccc (Hex package)
│   │   └── ddd (Hex package)
│   └── eee (Hex package) ----------(7)
│       ├── fff (Hex package)
│       └── ggg (Hex package)
├── hhh (git@...) ------------------(2)
│   ├── iii (Hex package) ----------(4)
│   │   └── jjj (Hex package)
│   │       ├── kkk (Hex package)
│   │       └── lll (Hex package)
│   └── mmm (Hex package) ----------(5)
└── nnn (Hex package) --------------(3)
    ├── ooo (Hex package)
    └── ppp (Hex package)
```

同じ階層では（画面上の）上のノードから順に探索しますが、次の深さに進むときは下にあるノードの subtree から探索を始めます。このときの上下関係は Mix project の config にある `:deps` の順番で決まるようです。また、remote converger を使わないため、Hex package の subtree を深掘りすることはできません。

第二フェーズはさらに二つに分けることができます。前半は Mix の外で実装される処理であり、remote converger を介して実行されます。この記事では詳しく触れません（大枠を理解するにあたっては知らなくても問題無いと思います）。後半は Mix の中に実装があり、第一フェーズと同様の処理が行われます。後半部分について、依存木構造と探索順序の例を以下に図示しました。

```
project
├── aaa (git@...) ------------------(1)
│   ├── bbb (Hex package) ----------(11)
│   │   ├── ccc (Hex package) ------(15)
│   │   └── ddd (Hex package) ------(16)
│   └── eee (Hex package) ----------(12)
│       ├── fff (Hex package) ------(13)
│       └── ggg (Hex package) ------(14)
├── hhh (git@...) ------------------(2)
│   ├── iii (Hex package) ----------(6)
│   │   └── jjj (Hex package) ------(8)
│   │       ├── kkk (Hex package) --(9)
│   │       └── lll (Hex package) --(10)
│   └── mmm (Hex package) ----------(7)
└── nnn (Hex package) --------------(3)
    ├── ooo (Hex package) ----------(4)
    └── ppp (Hex package) ----------(5)
```

今度は Hex package の subtree を深掘りできています。

#### 各ノードにおける処理

処理の流れが依存木構造の幅優先探索になっていることを紹介しましたが、各ノードではどんな処理が行われているのでしょうか？探索において初めて出会ったライブラリかどうかで処理が変わります。

初めての場合は、そのノードの specification が暫定的な converged specification になり、fetch, load が行われます。

そうでない場合は、specification がチェックされ、必要があれば更新が試みられます。このとき、ノードの specification と暫定的な converged specification が食い違うと、そのライブラリは diverged な状態と見なされます。この状態になっても依存木構造の探索は進んでいき、エラーメッセージは最後に出力されます。そのため、エラーが出たけど `deps/` に更新されたライブラリが存在している、みたいなことが起き得ます。

なお、第一フェーズでは、Hex package などの remote converger に関わるライブラリは fetch, load されません。また、第二フェーズの後半は第一フェーズの結果を忘れて converged specification が未定の状態から始まります。

## Hex に問い合わせる前にバージョン指定が複数あることが分かる場合

Remote converger という言葉を知った後では、remote converger を使わずに間接的な依存ライブラリのバージョン指定が複数あることが分かる場合、と言い換えたほうが分かりやすいです。

### 再現手順

- 1. 3 つの Mix project: `project_a`, `project_b`, `project_c` をつくります。

```elixir
# project_a/mix.exs
  defp deps do
    [
      {:hackney, "1.14.3"},
    ]
  end
```

```elixir
# project_b/mix.exs
  defp deps do
    [
      {:hackney, "~> 1.0"},
    ]
  end
```

```elixir
# project_c/mix.exs
  defp deps do
    [
      {:project_a, path: "../project_a"},
      {:project_b, path: "../project_b"},
    ]
  end
```

hackney を使っていますが、他のライブラリでもたぶん再現します。

- 2. `project_c` のディレクトリで `$ mix deps.get`、`$ mix compile` を実行します。
    - 実は `$ mix compile` が必須かどうか知らないです。
- 3. `project_a` の hackney のバージョンを上げます。
    - ここでは `{:hackney, "1.14.3"}` を `{:hackney, "1.15.2"}` にします。
- 4. `project_c` のディレクトリで `$ mix deps.get` を実行します。

下記のエラーが出ます。

```
$ mix deps.get
Resolving Hex dependencies...

Failed to use "hackney" (version 1.14.3) because
  /path/to/project_a/mix.exs requires 1.15.2
  /path/to/project_b/mix.exs requires ~> 1.0
  mix.lock specifies 1.14.3

** (Mix) Hex dependency resolution failed, change the version requirements of your dependencies or unlock them (by using mix deps.update or mix deps.unlock). If you are unable to resolve the conflicts you can try overriding with {:dependency, "~> 1.0", override: true}
```

しかし、`project_c` の設定を

```elixir
# project_c/mix.exs
  defp deps do
    [
      {:project_b, path: "../project_b"},
      {:project_a, path: "../project_a"},
    ]
  end
```

のように書き換え、手順の 2-4 を行うと、今度は hackney が更新されます。

```
$ mix deps.get
Resolving Hex dependencies...
Dependency resolution completed:
Unchanged:
  idna 6.0.0
  metrics 1.0.1
  parse_trans 3.3.0
  unicode_util_compat 0.4.1
Upgraded:
  certifi 2.4.2 => 2.5.1
  hackney 1.14.3 => 1.15.2
  mimerl 1.0.2 => 1.2.0
  ssl_verify_fun 1.1.4 => 1.1.5
* Updating hackney (Hex package)
* Updating certifi (Hex package)
* Updating mimerl (Hex package)
* Updating ssl_verify_fun (Hex package)
```

### 何が起きているのか？

まず、エラーが出る場合についてです。依存木構造（主要部のみ）は下記のようになっています。

```
project_c
├── project_a (../project_a)
│   └── hackney 1.15.2 (Hex package)
└── project_b (../project_b)
    └── hackney ~> 1.0 (Hex package)
```

依存木構造から、hackney に関して `hackney ~> 1.0`、`hackney 1.15.2` の順で converge が進むことが分かります。`~> 1.0` や `1.15.2` は specification の一部であり、version requirement と（私は）呼んでいます。Converge の第一フェーズ終了後、暫定的な converged specification の version requirement は `~> 1.0` になります。`1.15.2` になっていて欲しいところですが、いまの Mix には version requirement を更新する機構はありません。。

そして、version requirement が `~> 1.0` であるため、第二フェーズの前半で、Hex に「version requirement が `~> 1.0` で lock には `1.14.3` と書かれているから `1.14.3` で進めたいんだけど、`1.15.2` が必要っぽい感じもするよね。はっきりさせてから出直してきてね！」と怒られます（コードをちゃんと読んだわけではないため、このセリフはエラーメッセージからの推測によるところ大きいです）。

次に、更新できる場合についてです。依存木構造（主要部のみ）は下記のようになっています。

```
project_c
├── project_b (../project_b)
│   └── hackney ~> 1.0 (Hex package)
└── project_a (../project_a)
    └── hackney 1.15.2 (Hex package)
```

今度は `hackney 1.15.2`、`hackney ~> 1.0` の順で hackney の converge が行われます。第一フェーズ終了後、暫定的な converged specification の version requirement は `1.15.2` になります。そのため、第二フェーズの前半で Hex が「version requirement が `1.15.2` だけど lock には `1.14.3` と書かれているから更新しなきゃ！」と判断してくれます。

## `:build_embedded` が `true` の場合

まず `:build_embedded` について少し説明しておきます。`:build_embedded` は Mix project の config として設定でき、デフォルトでは `false` です。デフォルトの場合、依存ライブラリのコンパイル生成物は `deps/{app_name}/ebin/` にあり、`_build/{mix_env}/lib/{app_name}/ebin` はそのディレクトリへのリンクになります。

`:build_embedded` を `true` にすると、`_build/{mix_env}/lib/{app_name}/ebin` にはリンクの代わりにコピーが配置されます。これにより、symlink traversal の危険を避けることができます。

~~実は、このケースが起きる条件は `:build_embedded` が `true` であることだけではないのですが、言葉で表すのが難しいため、次の再現手順をご覧ください。~~
と思いましたが、`:build_embedded` を `true` にするだけで再現できなかったのは別のバグがあったためでした。[PR](https://github.com/elixir-lang/elixir/pull/9619) を出して修正してもらいました！

### 再現手順

- 1. 一つ目のケースの再現で使った `project_a` と `project_c` を流用します。
    - `project_c` が `project_b` の代わりに excoveralls に依存するように書き換えます。
        - excoveralls も `{:hackney, "~> 1.0"}` のように hackney に依存しています。
    - `project_c` に `build_embedded: true` を設定します。

```elixir
# project_c/mix.exs
  defp deps do
    [
      {:project_a, path: "../project_a"},
      {:excoveralls, "0.12.1"},
    ]
  end
```

- 2. `project_c` のディレクトリで `$ mix deps.get`、`$ mix compile` を実行します。
- 3. `project_a` の hackney のバージョンを上げます。
    - ここでは `{:hackney, "1.14.3"}` を `{:hackney, "1.15.2"}` にします。
- 4. `project_c` のディレクトリで `$ mix deps.get` を実行します。

下記のように、更新自体はできるのですがエラーが出ます。

```
$ mix deps.get
Resolving Hex dependencies...
Dependency resolution completed:
Unchanged:
  excoveralls 0.12.1
  idna 6.0.0
  jason 1.1.2
  metrics 1.0.1
  parse_trans 3.3.0
  unicode_util_compat 0.4.1
Upgraded:
  certifi 2.4.2 => 2.5.1
  hackney 1.14.3 => 1.15.2
  mimerl 1.0.2 => 1.2.0
  ssl_verify_fun 1.1.4 => 1.1.5
* Updating hackney (Hex package)
* Updating certifi (Hex package)
* Updating mimerl (Hex package)
* Updating ssl_verify_fun (Hex package)
Dependencies have diverged:
* hackney (Hex package)
  the dependency hackney 1.14.3

  > In deps/excoveralls/mix.exs:
    {:hackney, "~> 1.0", [env: :prod, hex: "hackney", repo: "hexpm", optional: false]}

  does not match the requirement specified

  > In /path/to/project_a/mix.exs:
    {:hackney, "1.15.2", [env: :prod, repo: "hexpm", hex: "hackney"]}

  Ensure they match or specify one of the above in your deps and set "override: true"
** (Mix) Can't continue due to errors on dependencies
```

しかし、`project_c` の設定を

```elixir
# project_c/mix.exs
  defp deps do
    [
      {:excoveralls, "0.12.1"},
      {:project_a, path: "../project_a"},
    ]
  end
```

のように書き換え、手順の 2-4 を行うと、今度は hackney が更新されます。

```
$ mix deps.get
Resolving Hex dependencies...
Dependency resolution completed:
Unchanged:
  excoveralls 0.12.1
  idna 6.0.0
  jason 1.1.2
  metrics 1.0.1
  parse_trans 3.3.0
  unicode_util_compat 0.4.1
Upgraded:
  certifi 2.4.2 => 2.5.1
  hackney 1.14.3 => 1.15.2
  mimerl 1.0.2 => 1.2.0
  ssl_verify_fun 1.1.4 => 1.1.5
* Updating hackney (Hex package)
* Updating certifi (Hex package)
* Updating mimerl (Hex package)
* Updating ssl_verify_fun (Hex package)
```

### 何が起きているのか？

まず、エラーが出る場合についてです。依存木構造（主要部のみ）は下記のようになっています。

```
project_c
├── project_a (../project_a)
│   └── hackney 1.15.2 (Hex package) --(1) --(2')
└── excoveralls 0.12.1 (Hex package)
    └── hackney ~> 1.0 (Hex package) --------(1')
```

まず、converge の第一フェーズおいて、hackney に対する処理が行われるのは `(1)` だけですので、version requirement は `1.15.2` になります。第二フェーズの前半で `1.15.2` へ更新できることが確認され、後半は `(1')`、`(2')` の順で進みます。

`(1')` のときに version requirement が `~> 1.0` となり、fetch と load が行われます。

Fetch では、`1.14.3` のパッケージが cleanup されて `1.15.2` のパッケージが新しく配置されます。このとき、`deps/hackney/ebin` は削除されます。

Load では、`:build_embedded` が `false` か `true` かによって挙動が変わります。どちらの場合も `_build/{env}/lib/hackney/ebin/hackney.app` に対して `:file.consult/1` が呼ばれます。

- `false` の場合
    - `_build/{env}/lib/hackney/ebin` は存在しない `deps/hackney/ebin` へのリンクになっており、`:file.consult/1` は失敗します。
        - この文脈において失敗自体はエラーではなく、単にまだ新しいバージョンの hackney に対してコンパイルが行われていないことを意味しています。
- `true` の場合
    - `_build/{env}/lib/hackney/ebin` はコピーであり、`deps/hackney/ebin` の有無に関わらず存在しています。そのため、`:file.consult/1` は成功し、その後の処理で [vsn](https://hexdocs.pm/elixir/Module.html#module-vsn) が読み取られます。`_build/{env}/lib/hackney/ebin` に残っているのは以前のバージョンなので、vsn は `1.4.3` となります。`1.4.3` は version requirement `~> 1.0` を満たしているため、この時点ではおかしなことが起きていると判断されません。

結果として、`:build_embedded` が `true` の場合は vsn が `1.4.3` という状態をもって `(2')` に進みます。そして、「`1.5.2` を求められているけど、既存の `1.4.3` の application を使うことになっているから、食い違いが起きている！」と Mix に怒られます。

次に、更新できる場合についてです。依存木構造（主要部のみ）は下記のようになっています。

```
project_c
├── excoveralls 0.12.1 (Hex package)
│   └── hackney ~> 1.0 (Hex package) --------(2')
└── project_a (../project_a)
    └── hackney 1.15.2 (Hex package) --(1) --(1')
```

今度は第二フェーズの後半において、`(1')`、`(2')` の順で hackney の converge が行われます。

`(1')` のときに version requirement が `1.15.2` となり、fetch と load が行われます。

Load における `:build_embedded` が `true` のときの挙動がエラーが出る場合と異なります。vsn `1.4.3` が version requirement `1.15.2` を満たさないため、今ある application は古いと判断されます。古くても後でコンパイルすれば良いだけなので、エラーとは見なされず、vsn を無視して converge が正常に進んでいきます。

## おわりに

具体例はかなりのコーナーケースだと思いますが、`$ mix deps.get` を実行したときの内部的な動作として、変則的な幅優先探索に基づいて converge, fetch, load という処理が行われている、ということは覚えておいても損はないと思います（得もなさそうですが。。）。また、間接的な依存ライブラリの条件指定解決で問題が起きた場合は、そのライブラリを明示的な（トップレベルの）依存として自分の Mix project に設定するとうまくいくかもしれません（[参考](https://github.com/elixir-lang/elixir/blob/28671b0909f9cc278cfb37a76f6e097caaa5495b/lib/mix/lib/mix/dep/converger.ex#L153)）。 個人的には、Mix がすべてうまくやってくれるだろうと頼り切りになるのではなく、自分で明示的にコントロールしようと頑張るほうが Elixir ぽい感じがします :laughing:

次は @knagauchi さんの投稿です。お楽しみに！

[^1]: 入社は今年の 4 月、Elixir 歴は半年くらいです。
[^2]: `$ mix deps.tree` の出力は重複部分が省略されています。また、ライブラリの並びが一部辞書順に変えられてしまう場合もあるようです。