LoginSignup
22
21

More than 5 years have passed since last update.

@shibukawa(Yoshiki Shibukawa)inフューチャー株式会社

AST時代のJavaScriptで、ASTに深入りせずにASTと仲良くする方法を考える

Last updated at Posted at 2016-10-22

ちょっと、ソースコードをパースして、とある関数(require)を呼び出して作った関数を使っている箇所のピックアップをやろうと思ったのですが、ASTを直接扱うのはいろいろめんどいです。

  • ソースコードをパースしてAST化するのはacornとかesprimaが有名。acornはプラグインでJSXにも対応できたりするらしい。
  • どのパーサを使っても、基本的にはここの定義に準拠するはず
    • https://github.com/estree/estree/blob/master/es2015.md
    • 子供をたどるのに、DOMのchildrenみたいな、「子供を取得するにはこれだ！」という決まった方法はない。
    • ノードごとに子供の名前が違うんだけど、全部のノードごとに分岐して探さないといけないの？
  • var a = 10;だと変数定義(VariableDeclaration)扱いだけど、aがすでにある状態だとa = 10;は式(Expression);

たんなるビジターパターンだとつらい

acornに標準の子供を探索するメソッドを使ってみたのですがなかなかに厳しい。

  • マッチしたノードから、親要素をたどることができない。そういう状態管理は自前でやっていかないといけない。
  • 子供要素を探すのも自分でやらないといけない。

レキシカルスコープをマジメにやるには、最低でも、変数定義された親の関数のボディ内ではすべて有効、という扱いにする必要があります。そして関数定義は入れ子にできてしまう。ステータス管理も二重、三重になっていきます。考えるだけで頭痛が痛いですね。

子供要素をたどるのも、構造体の種類ごとにいろいろやらないといけない雰囲気。

ASTを触る時間ばかり増えてしまうのは本末転倒なので、別な方法を考えることに。

欲しいのはパターンマッチ

要件としては、「var method = require('mymodule')」にマッチするノードをピックアップしたい、ということです。ASTは手段であっても目的ではない。探索過程ではASTは完全隠蔽できる方が自然ですよね。

こんな方法を考えてみました。

  1. 全体のソースコードをAST化
  2. マッチさせたいコードをAST化
  3. それぞれの構造や値が一致したらその先頭のノードを返す。

こんなテストコードみたいな感じで使いたいですよね、と。

describe('matchAST', () => {
    it('can match value assignment', () => {
        const src = `
        var a = 10;
        var a = 20;
        var b = 10;
        `;

        const pattern = {
            assign: `var a = 10;`
        };

        const result = matchAST(src, pattern);
        assert(result.length === 1);
        assert(result[0].name === 'assign');
        console.log(result[0].node);
        console.log(result[0].stack);
    });
})

パターンを複数指定しているのは、三種類とか検知したいパターンがあるときに、毎回トップからトラバーサルするのを繰り返すのはムダそうなので、パターンはまとめて渡して、配列で結果を貰えれば良さそうです。

マッチすると、結果の配列に「パターン名(パターンJSONのキー)、マッチしたノード、親ノードのスタックあたりが入ってれば良さそうです。

作ってみた

というわけで、今日の午前中からぼちぼち書いてみたのがこれです。publicなのはトップの関数だけで、後はそこから使われるだけの関数です。

ASTのノードからは、子要素は

  • this.変数名 = Node
  • this.変数名= = [Node]

の2パターンだけっぽかったので、オブジェクトのキーを使って動的に子供を探すようにしました。とりあえず、ExpressionやらVariableDeclarationやらといった文字列とにらめっこせずに探索できることを確認しました。

'use strict';

const acorn = require('acorn');


function matchAST(source, patterns, acornOption) {
    const patternHeads = {};

    Object.keys(patterns).forEach(key => {
        const patternAST = acorn.parse(patterns[key], acornOption);
        const body = patternAST.body;
        if (body.length === 0) {
            return;
        }
        const heads = patternHeads[body[0].type];
        if (!heads) {
            patternHeads[body[0].type] = [{name: key, ast: body}];
        } else {
            heads.push({name: key, ast: body});
        }
    });

    const stack = [];
    const result = [];

    const ast = acorn.parse(source, acornOption); 
    walk(ast, patternHeads, stack, result);

    return result;
}

function walk(node, patterns, stack, result) {
    Object.keys(node).forEach(key => {
        const value = node[key];
        if (Array.isArray(value)) {
            checkPattern(node, key, value, false, patterns, stack, result);
            value.forEach((elem, index) => {
                const copiedStack = stack.slice(0);
                copiedStack.push({node: node, key: key, index: index});
                walk(elem, patterns, copiedStack, result);
            });
        } else if (value instanceof acorn.Node) {
            checkPattern(node, key, [value], true, patterns, stack, result);
            const copiedStack = stack.slice(0);
            copiedStack.push({node: node, key: key});
            walk(value, patterns, copiedStack, result);
        }
    });
}

function checkPattern(parent, key, nodes, isSingle, patterns, stack, result) {
    const matchedPattern = patterns[nodes[0].type];
    if (!matchedPattern) {
        return;
    }
    matchedPattern.forEach(pattern => {
        for (var offset = 0; offset < (nodes.length - pattern.ast.length + 1); offset++) {
            var match = true;
            for (var i = 0; i < pattern.ast.length; i++) {
                if (!matchNode(nodes[offset+i], pattern.ast[i])) {
                    match = false;
                    break;
                }
            }
            if (match) {
                const copiedStack = stack.slice(0);
                if (isSingle) {
                    copiedStack.push({node: parent, key: key});
                } else {
                    copiedStack.push({node: parent, key: key, index: offset});
                }
                result.push({name: pattern.name, stack: stack, node: nodes[offset]});
            }
        }
    });
}

function matchNode(node, patternNode) {
    if (node.type !== patternNode.type) {
        return false;
    }

    // recursive check;
    var keys = Object.keys(node);
    for (var i = 0; i < keys.length; i++) {
        const key = keys[i];
        if (key === 'start' || key === 'end' || key === 'value') {
            continue;
        }
        const value = node[key];
        if (Array.isArray(value)) {
            const array = value;
            const patternArray = patternNode[key];
            if (array.length !== patternArray.length) {
                return false;
            }
            for (var j = 0; j < array.length; j++) {
                if (!matchNode(array[j], patternArray[j])) {
                    return false;
                }
            }
        } else if (value.type) {
            if (!matchNode(value, patternNode[key])) {
                return false;
            }
        } else if (value !== patternNode[key]) {
            return false;
        }
    }

    return true;
}

module.exports = {
    matchAST: matchAST
};

やっていることはシンプルです

  • パターンのテキスト片をAST化
  • パターンを探し安いように、先頭のタグの種類でインデックス化する
  • 子供をたどりつつ(walk())、マッチしているパターンを探す
  • 見つかったら配列に入れて返します。

とはいえ、これでは足りない

とりあえず現段階でできているのは↑ですが、まだ足りない機能があります。

これだと、完全一致しかできません。例えば、割り当てる文字列は任意にしたい、変数名は任意にしたい、マッチする数値は任意にしたい・・・そうなると、今の仕組みだけではダメです。特殊なIdentifierを使ってい、任意のものにマッチできるようにしてみたいですね。

  • __string__: 任意の文字列とマッチする
  • __number__: 任意の数値とマッチする
  • __anysymbol__: 任意の名前とマッチする

こんな感じの識別子を使ってあげれば大丈夫そうです。 最後の matchNode() 関数の中だけでなんとかなります。これはすぐに対応したい。

これだけでは対応できないのが、変数宣言です。

変数定義がvarかletかconstかで、変数定義ノードのkindの文字列が変わります。上記のパターンマッチだけでは対応できません。最初にパターンを分析しているところで、varバージョンと、constバージョンとか複数のパターンを内部的に作って、登録しちゃうのが良さそうです。変数宣言でない代入も、var/let/const付きの行を生成すれば、後段の変更は不要です。

パッケージ化するかどうかは悩み中。

更新 パッケージ化しました。

22
21
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
22
21