Vim script の Lint 作者による誰得 Lint デザインパターン

この記事は、Lint における主要なデザインパターンを紹介します。
紹介するパターンは次の3つです:

- Policy パターン
- AST Visitor パターン
- Chained Config パターン



# 執筆者について

[Vim script の Lint](https://github.com/Kuniwak/vint) 作者です。
詳しくは、[インタビュー記事](http://howivim.com/2016/kuniwak/)をご覧ください。



# デザインパターンの紹介
## Policy パターン

Lint が指摘する項目を、個別のクラスや関数として実装するパターンです。
主要な Lint でも採用されています。


### 対象とするモデル

検査項目の例として、文字列リテラルの開始記号が「`"`（二重引用符）」のとき警告するものを考えます。
この場合、この検査項目は `ProhibitDoubleQuotes` のような名前を持っています。
また、この検査項目に違反したとしても、深刻度はそこまで高くないと推測できます。
このように、**検査項目はそれぞれ名前や深刻度などの属性をもつはず**です。

さらに、それぞれの項目は検査アルゴリズムを持っています。
例えば、先ほどの `ProhibitDoubleQuotes` の検査アルゴリズムは、文字列リテラルの開始トークンを探して「`"`」でないことを確認するといったものになるでしょう。

まとめると、検査項目は、名前・深刻度・検査方法などの組であることがわかります。
そこで、これらの組を `Policy` というクラス（または関数）にまとめると、**複数の検査項目を統一したインターフェースで扱える**ようになります。


### 実現方法

検査項目ごとに、名前・深刻度・検査方法の組をもつ `Policy` というクラス（または関数）を実装します。
こうすることで、それぞれの検査項目の結合度を下げることができます:

```js:abstract_policy.js
class AbstractPolicy {

  // 与えられた Node が検査項目に違反していれば、検査違反オブジェクトを返す。
  getViolations(node) {
    if (this.isValid(node)) return [];

    return [
      {
        name: this.constructor.name,
        severity: this.severity,
        position: node.position,
      }
    ];
  }


  isValid(node) {
    throw new NotImplemented();
  }
}
```

```js:prohibit_double_quotes.js
// 文字列リテラルを二重引用符にすることを禁止する Policy
class ProhibitDoubleQuotes extends AbstractPolicy {
  constructor() {
    super();
    this.severity = Severity.STYLE_PROBLEM;
    this.interested_node_types = [NodeType.STRING];
  }


  isValid(node) {
    return node.syntax !== StringNode.Syntax.DOUBLE_QUOTE;
  }
}
```


また、疎結合性を活かして、サードパーティの検査項目をプラガブルに追加する際にもこのパターンは役立ちます。



## AST Visitor パターン

抽象構文木（Abstract Syntax Tree, AST）の巡回機能だけを独立した関数として実装します。



### 対象とするモデル

Lint の検査方法の一つに、抽象構文木による検査があります。

この抽象構文木というのは、プログラムの構造の表現方法の一つです。
この表現方法では、コードの空白や改行位置などに左右されないという特徴があります。

例えば、次のようなプログラムがあったとします:

```txt:sample
if (true) {
  print("Hello, World!");
}
```

このプログラムの抽象構文木は、次のような木構造のデータになります:

```json:ast.json
{
  "type": "if",
  "condition": {
    "type": "boolean",
    "value": "true",
  },
  "then": {
    "type": "call"
    "callee": {
      "type": "function",
      "name": "print"
    },
    "arguments": [
      {
        "type": "string",
        "value": "Hello, World!"
      }
    ]
  }
}
```

このデータには空白や改行位置などの情報が含まれていません。
そのため、次のように空白や改行を取り除いたとしても、同じ抽象構文木になります:

```txt:sample2
if(true){print("Hello, World!");}
```

このように、抽象構文木はプログラムの構造を表現したものであることがわかります。

さて、抽象構文木を使った検査では、抽象構文木の部分木や葉を巡回しながら検査することになります。
この巡回処理を、Policy クラス（または関数）に個別実装してしまうと、抽象構文木の仕様変更で多くの Policy の修正が必要になってしまいます。

この問題を解決するために、**抽象構文木の巡回処理のみを別関数（またはクラス）へと分離させます**。



### 実現方法

例えば、構文木を深さ優先で巡回する `traverse` という関数を実装します。
この関数は、再帰関数で簡単に実装できます:

```js:traverse.js
function traverse(node, onEnter, onLeave) {
  onEnter(node);

  node.childNodes.forEach((childNode) => {
    traverse(childNode, onEnter, onLeave);
  });

  onLeave(node);
}
```

新しい木の訪問時には `onEnter` が呼ばれ、退出時（兄弟の木に移動する直前）には `onLeave` が呼ばれます。
このように、訪問と退出で処理を分ける理由は、レキシカルスコープの分析などを楽にするためです[^2]。

[^2]: レキシカルスコープを採用している言語では、関数やブロック文などの木を訪れるたびに新しいスコープが作られます。そして、この木の外にでるとき別のスコープへと移ります。つまり、訪問と退出が重要なタイミングになっているのです。

また、上の `traverse` 関数は、簡単のために途中の部分木をスキップしたり、巡回を中断したりする機能を持っていません。
しかし、これらの機能を使えば無駄な処理を省けるため、Lint の高速化の鍵となっています。
したがって、実用的な実装はもう少し複雑になるでしょう。



## Chained Config パターン

優先順序のある複数の設定から、最終的な設定を作り出すパターンです。



### 対象とするモデル

一般的に、Lint は複数の方法で動作設定をおこなえます。
例えば、以下の5つの設定方法は多くの Lint が備えています:

- デフォルトの設定
- ホームディレクトリ下のファイルで設定
    - 例: `~/.vintrc.yaml`
    - 例: `~/.eslintrc.js`
    - 例: `~/.rubocop.yml`
    - 例: `~/.config/flake8`
- プロジェクトディレクトリ下のファイルで設定
    - 例: `.vintrc.yaml`
    - 例: `.eslintrc.js`
    - 例: `.rubocop.yml`
    - 例: `.flake8`
- コマンドライン引数で設定
    - 例: `$ vint --error`
    - 例: `$ eslint --rule 'quotes: [2, double]'`
    - 例: `$ rubocop -a --only Style/DefWithParentheses`
    - 例: `$ flake8 --select E123`
- コメントで設定
    - 例:

        ```vim:sample.vim
        " vint: -ProhibitAbbreviationOption
        ```

    - 例:

        ```js:sample.js
        /* eslint eqeqeq: "off" */
        ```

    - 例:

        ```ruby:sample.rb
        # rubocop:disable Metrics/LineLength
        ```

    - 例:

        ```py:sample.py
        # noqa: E731
        ```

これらの方法によって設定できる内容はほぼ同じです。また、それぞれの方法の間には一貫した優先順序があります。
例えば、ホームディレクトリ下ファイルの設定とプロジェクトディレクトリ下のファイルで違う設定がされたとすると、一般的には後者が優先されます。この優先順序は、次のように**適用範囲が狭いものほど優先される**ように設定されています:

| 設定方法                        | 適用範囲                        | 強さ |
|:------------------------------:|:-----------------------------:|:----:|
| ホームディレクトリ下のファイル      | 最大（複数プロジェクト）          | 最弱 |
| プロジェクトディレクトリ下のファイル | 大（1プロジェクト複数ファイル）    | 弱   |
| コマンドライン引数                | 小（複数ファイル）               | 強   |
| コメント                        | 最小（1ファイルまたは行、スコープ） | 最強 |

この優先順序を矛盾なく実現するのは意外と面倒です。
そこで、**Chained Config パターン**を使います。



### 実現方法

このパターンでは、設定方法を `ConfigSource` というインターフェースで表現します。

この `ConfigSource` は、`get_config_dict` というメソッドだけを要求します:

```py:config_source.py
class ConfigSource(object):
    def get_config_dict():
        raise NotImplementedError()
```

この `get_config_dict` は、設定項目を表現した辞書を返します。
例えば、デフォルト設定を表す `DefaultConfigSource` は、次のような辞書を返します:

```py:default_config_source.py
# デフォルトの設定
class DefaultConfigSource(object):
    def get_config_dict():
        return {
            'ruleA': True,
            'ruleB': True,
            'ruleC': False,
        }
```

ホームディレクトリ下のファイルによる設定を表す `HomeConfigSource` であれば、次のようにファイルの内容から辞書を生成します:

```py:home_config_source.py
# ホームディレクトリ下ファイルからの設定
class HomeConfigSource(object):
    def get_config_dict():
        return parse_yaml('~/config.yaml')
```

このように、設定方法ごとに `ConfigSource` を用意します。

次に、これらの `ConfigSource` を集約する `ChainedConfigSource` を実装します。
`ChainedConfigSource` は、`ConfigSource` から作成され、**それぞれの `get_config_dict` から得られた辞書を順に合成していく機能を持ちます**:

```py:chain_config_source.py
from functools import reduce


class ChainedConfigSource(ConfigSource):
    def __init__(self, *config_sources):
        self.config_sources = config_sources


    # 複数の ConfigSource の優先度を考慮した最終的な設定を返す。
    def get_config_dict(self):
        config_dicts_ordered_by_prior_asc = [config_source.get_config_dict()
                                             for config_source in self.config_sources]

        # ConfigSource の設定を順に合成していく。
        return reduce(extends_deeply, config_dicts_ordered_by_prior_asc, {})


def extends_deeply(dict_to_extend, prior_dict):
    for key, value in prior_dict.items():
        if isinstance(value, dict):
            if key in dict_to_extend:
                extends_deeply(dict_to_extend[key], value)
            else:
                dict_to_extend[key] = value
        else:
            dict_to_extend[key] = value

    return dict_to_extend
```

辞書を順に適用していくことで、それぞれの設定方法の優先順序が矛盾なく実現できます[^1]:

```py
config = ChainedConfigSource(
    # 優先度: 低
    DefaultConfigSource(),
    HomeConfigSource(),
    ProjectConfigSource(),
    CmdArgsConfigSource(),
    CommentConfigSource(),
    # 優先度: 高
)
```

[^1]: `CommentConfigSource` だけは、実行中に内容が更新され続けます。そのため、更新を検知して反映する仕組みが必要です。


# 終わりに

この記事では、3種類の Lint のデザインパターンを紹介しました。
もちろん、この他にも様々なデザインパターンがあると思います（Token Stream Parser パターンなどをモヤモヤと考えています）。

なお、もし、私が設計した Lint 実装に興味があれば、ぜひ読んでみてください（[コード](https://github.com/Kuniwak/vint)）。
読む場合は、先に処理の大まかな流れの図を見ておくことをお勧めします。

![](https://raw.githubusercontent.com/Kuniwak/vint/diagrams/seq_diagram.png)