Как я могу обнаружить все зависимости функции в Node.js?

Ответ 1

(Я извиняюсь заранее: я обычно стараюсь и даю свои ответы с юмором, чтобы облегчить читателю через них, но я не смог бы это сделать в этом случае. Рассмотрим двойное извинение за длину этого ответа.)

0. TL; DR (для "нормальных людей" ) проблемы

Это непростая задача. Вместо того, чтобы решать его в полном объеме, мы ограничим его сферу действия - мы решим только часть проблемы, о которой мы заботимся. Мы сделаем это, проанализируя ввод с помощью парсера JavaScript и перейдем к нему с помощью простого алгоритма recurive-descent. Наш алгоритм будет анализировать область программы и правильно идентифицировать вызовы функций.

Все остальное просто заполняет пробелы! Результат находится в нижней части ответа, поэтому я рекомендую вам воспользоваться первым комментарием если вы не хотите читать.

1. Ограничение проблемы

Как ответ Бенджамина Грюнбаума говорит, что это очень и очень сложная проблема из-за динамичной природы JavaScript. Однако, что, если вместо того, чтобы делать решение, которое будет работать для 100% программ, мы вместо этого делаем это для подмножества программ, если ограничимся обработкой определенных вещей?

Самое важное ограничение:

• Нет eval. Если мы включим eval, это будет спираль в хаос. Это связано с тем, что eval позволяет использовать произвольные строки, что делает невозможным отслеживание зависимостей без проверки всех возможных входных данных. В NodeJS нет document.write, а setTimeout принимает только функцию, поэтому нам не о чем беспокоиться. Однако мы также запрещаем vm module.

Следующие ограничения предназначены для облегчения процесса. Они могут быть разрешимы, но их решение не подходит для этого ответа:

• Никаких динамических клавиш obj[key]() мне не следует вводить это ограничение, но оно определенно разрешимо для некоторых случаев (например, key = 'foo', но не key = userInput())
• Переменные не являются тенями, no var self = this. Определенно разрешимо с полным анализатором возможностей.
• Нет фанковых выражений, например. (a, b)()

И, наконец, ограничения на реализацию в этом ответе - либо из-за ограничений сложности или временных ограничений (но они очень разрешимы):

4. Нет подъема, поэтому объявления функций не будут расширяться в области видимости.
5. Обработка объектов. Это отстой, но обработка таких вещей, как foo.bar() или this.foo(), по крайней мере удвоила бы сложность программы. Положите достаточно времени, и это очень выполнимо.
6. Выполняется только область функций. В JavaScript есть способы определения областей, отличных от функций (оператор with, catch). Мы не имеем дело с ними.

В этом ответе я опишу (и предоставим) анализатор концептуальных понятий.

2. Приближение проблемы

Учитывая программу, как мы можем расшифровать ее функциональные зависимости?

//A. just a global function
globalFunction();
//B. a function within a function
var outer = function () {
    function foo () {}
    foo();
};
//C. calling a function within itself
var outer = function inner () {
    inner();
};
//D. disambiguating between two identically named functions
function foo () {
    var foo = function () {};
    foo();
}
foo();

Чтобы понять программу, нам нужно разбить ее код на части, нам нужно понять его семантику: нам нужен синтаксический анализатор. Я выбрал acorn, потому что я никогда не использовал его и не слышал хорошей оценки. Я предлагаю вам немного поиграть с ним, посмотреть, какие программы выглядят в SpiderMonkeys AST.

Теперь, когда у нас есть волшебный синтаксический анализатор, который преобразует JavaScript в AST (a Абстрактное дерево синтаксиса), как мы будем логически обрабатывать поиск зависимостей? Нам нужно сделать две вещи:

• Правильно строить области.
• Понять, к какой функции относится вызов функции.

Мы можем видеть, почему пример D выше может быть неоднозначным: существуют две функции, называемые foo, откуда мы можем знать, какая из них foo() означает? Вот почему нам нужно реализовать обзор.

3. Решение проблемы

Так как решение состоит из двух частей, разрешите его таким образом. Начиная с самой большой проблемы:

3.1. Обзорное

Итак... у нас есть АСТ. У этого есть куча узлов. Как мы создаем область? Ну, мы только заботимся о сфере действия. Это облегчает процесс, поскольку мы знаем, что нам нужно иметь дело только с функциями. Но прежде чем мы поговорим о том, как использовать области действия, задайте функцию, которая делает области.

Что такое область видимости? Это не сложное существо: у него есть родительская область (или null, если она глобальная область), и она содержит элементы, которые она содержит. Нам нужен способ добавить вещи в сферу действия и получить вещи от одного. Позвольте сделать это:

var Scope = function (parent) {
    var ret = { items : {}, parent : parent, children : [] };

    ret.get = function (name) {
        if (this.items[name]) {
            return this.items[name];
        }

        if (this.parent) {
            return this.parent.get(name);
        }

        //this is fake, as it also assumes every global reference is legit
        return name;
    };

    ret.add = function (name, val) {
        this.items[name] = val;
    };

    if (parent) {
        parent.children.push(ret);
    }
    return ret;
};

Как вы, возможно, заметили, я обманываю в двух аспектах: во-первых, я назначаю дочерние области. То есть, чтобы облегчить для нас людей, которые видят, что все работает (в противном случае все области охвата будут внутренними, мы увидим только глобальный охват). Во-вторых, я предполагаю, что глобальная область содержит все - то есть, если foo не определена в какой-либо области, то она должна быть существующей глобальной переменной. Это может быть или не быть желательным.

ОК, у нас есть способ представления областей. Не вскрывайте шампанское, мы все равно должны их изготовить! Посмотрим, как выглядит простая декларация функции, function f(){} в AST:

{
  "type": "Program",
  "start": 0,
  "end": 14,
  "body": [{
    "type": "FunctionDeclaration",
    "start": 0,
    "end": 14,
    "id": {
      "type": "Identifier",
      "start": 9,
      "end": 10,
      "name": "f"
    },
    "params": [],
    "body": {
      "type": "BlockStatement",
      "start": 12,
      "end": 14,
      "body": []
    }
  }]
}

Это довольно глоток, но мы можем смело пройти через это! Сочная часть такова:

{
  "type": "FunctionDeclaration",
  "id": {
    "type": "Identifier",
    "name": "f"
  },
  "params": [ ... ],
  "body": { ... }
}

Мы имеем FunctionDeclaration node с свойством id. Это имя id - это наше имя функции! Предположим, что мы имеем функцию walk, которая заботится о переходе по узлам и переменные currentScope и currentFuncName, и мы только что пришли к разбору объявления нашей функции node. Как мы делаем это? Код говорит громче слов:

//save our state, so we will return to it after we handled the function
var cachedScope = currentScope,
    cachedName = currentFuncName;

//and now we change the state
currentScope = Scope(cachedScope);
currentFuncName = node.id.name;

//create the bindings in the parent and current scopes
//the following lines have a serious bug, we'll get to it later (remember that
// we have to meet Captain Crunchypants)
cachedScope.add(currentFuncName, currentName);
currentScope.add(currentFuncName, currentName);

//continue with the parsing
walk(node.body);

//and restore the state
currentScope = cachedScope;
currentFuncName = cachedName;

Но подождите, а как насчет выражений функции? Они ведут себя по-другому! Прежде всего, они не обязательно имеют имя, и если они это делают, это видно только внутри них:

var outer = function inner () {
    //outer doesn't exist, inner is visible
};
//outer is visible, inner doesn't exist

Давайте сделаем еще одно огромное предположение о том, что мы рассмотрели часть объявления переменных - мы создали правильное связывание в родительской области. Тогда логика выше для обработки функций изменяется незначительно:

...
//and now we change the state
currentScope = Scope(cachedScope);
//we  signify anonymous functions with <anon>, since a function can never be called that
currentFuncName = node.id ? node.id.name : '<anon>';
...
if (node.id) {
    currentScope.add(currentFuncName, currentFuncName);
}
if (node.type === 'FunctionDeclaration') {
    cachedScope.add(currentFuncName, currentFuncName);
}
...

И верьте или нет, что более или менее весь механизм обработки области в конечном решении. Я ожидаю, когда вы добавите что-то вроде объектов, это будет немного сложнее, но это не сильно.

Пришло время встретиться с капитаном Кранчпанцем. Самый наблюдательный слушатель уже вспомнит пример D. Пусть освежит нашу память:

function foo () {
    function foo () {}
    foo();
}
foo();

При анализе этого вопроса нам нужен способ рассказать внешний foo и внутренний foo друг от друга - в противном случае мы не сможем узнать, какой из этих вызовов foo, и наш искатель зависимостей будет тост. Кроме того, мы не сможем разделить их в управлении зависимостями - если мы просто добавим результаты по имени функции, мы получим перезапись. Другими словами, нам нужно абсолютное имя функции.

Я выбрал представление с разнесением с символом #. Вышесказанное имеет функцию foo с внутренней функцией foo#foo с вызовом foo#foo и вызовом foo. Или, для менее запутывающего примера:

var outer = function () {
    function inner () {}
    inner();
};
outer();

Имеет функцию outer и функцию outer#inner. Там вызов outer#inner и вызов outer.

Итак, создайте эту функцию, которая принимает предыдущее имя и текущее имя функции и объединяет их:

function nameToAbsolute (parent, child) {
    //foo + bar => foo#bar
    if (parent) {
        return parent + '#' + name;
    }
    return name;
}

И измените нашу функцию, обрабатывая псевдокод (который вот-вот оживет! Я обещаю!):

...
currentScope = Scope(cachedScope);
var name = node.id ? node.id.name : '<anon>';
currentFuncName = nameToAbsolute(cachedName, name);
...
if (node.id) {
    currentScope.add(name, currentFuncName);
}
if (node.type === 'FunctionDeclaration') {
    cachedScope.add(name, currentFuncName);
}

Теперь мы говорим! Это время, чтобы перейти к тому, чтобы что-то делать! Возможно, я лгал вам все время, и я ничего не знаю, может быть, я потерпел неудачу, и я продолжал писать до сих пор, потому что знал, что никто не зачитает это далеко, и я получу много голосов, потому что это длинный ответ!

ХА! Держись! Там еще много впереди! Я не сидел на этом несколько дней без причины! (Как интересный социальный эксперимент, кто-нибудь мог бы поддержать комментарий, сказав что-то вокруг строк "Капитан Хрустпанц был рад вас видеть"?)

В более серьезной заметке мы должны начать составлять парсер: что удерживает наше состояние и идет по узлам. Поскольку у нас будет два парсера в конце, области и зависимости, мы создадим "главный парсер", который вызывает каждый из них при необходимости:

var parser = {
    results : {},
    state : {},

    parse : function (string) {
        this.freshen();

        var root = acorn.parse(string);
        this.walk(root);

        return this.results;
    },

    freshen : function () {
        this.results = {};
        this.results.deps = {};

        this.state = {};
        this.state.scope = this.results.scope = Scope(null);
        this.state.name = '';
    },

    walk : function (node) {
        //insert logic here
    },

    // ''    =>  'foo'
    // 'bar' =>  'bar#foo'
    nameToAbsolute : function (parent, name) {
        return parent ? parent + '#' + name : name;
    },

    cacheState : function () {
        var subject = this.state;
        return Object.keys( subject ).reduce(reduce, {});

        function reduce (ret, key) {
            ret[key] = subject[key];
            return ret;
        }
    },
    restoreState : function (st) {
        var subject = this.state;

        Object.keys(st).forEach(function (key) {
            subject[key] = st[key];
        });
    }
};

Это немного круто, но, надеюсь, это понятно. Мы сделали state в объект и сделали его гибким, cacheState и restoreState просто клонировали/сливали.

Теперь, для нашего любимого scopeParser:

var scopeParser = {
    parseFunction : function (func) {
        var startState = parser.cacheState(),

            state = parser.state,
            name = node.id ? node.id.name : '<anon>';

        state.scope = Scope(startState.scope);
        state.name = parser.nameToAbsolute(startState.name, name);

        if (func.id) {
            state.scope.add(name, state.name);
        }
        if (func.type === 'FunctionDeclaration') {
            startState.scope.add(name, state.name);
        }

        this.addParamsToScope(func);
        parser.walk(func.body);

        parser.restoreState(startState);
    }
};

Случайно наблюдательный читатель заметит, что parser.walk пуст. Время для заполнения 'er up!

walk : function (node) {
    var type = node.type;

    //yes, this is tight coupling. I will not apologise.
    if (type === 'FunctionDeclaration' || type === 'FunctionExpression') {
        scopeParser.parseFunction(node)
    }
    else if (node.type === 'ExpressionStatement') {
        this.walk(node.expression);
    }
    //Program, BlockStatement, ...
    else if (node.body && node.body.length) {
        node.body.forEach(this.walk, this);
    }
    else {
        console.log(node, 'pass through');
    }
    //...I'm sorry
}

Опять же, в основном технические вопросы - чтобы понять их, вам нужно играть с желудком. Мы хотим убедиться, что мы итерации и правильно ходим в узлы. Выражения Узлы, такие как (function foo() {}), имеют свойство expression, над которым мы переходим, BlockStatement Узлы (например, фактическое тело функции) и программные узлы имеют массив body и т.д.

Поскольку у нас есть что-то похожее на логику, попробуйте:

> parser.parse('function foo() {}').scope
{ items: { foo: 'foo' },
  parent: null,
  children:
   [ { items: [Object],
       parent: [Circular],
       children: [],
       get: [Function],
       add: [Function] } ],
  get: [Function],
  add: [Function] }

Ухоженная! Играйте с объявлениями функций и выражениями, убедитесь, что они правильно вложены. Однако мы забыли включить объявление переменной:

var foo = function () {};
bar = function () {};

Хорошее (и забавное!) упражнение добавляет их самостоятельно. Но не беспокойтесь - они будут включены в итоговый парсер;

Кто бы поверил!? Мы закончили работу! СДЕЛАННЫЙ! Позвольте сделать приветствие!

О, о, о... как ты думаешь, что идешь!? Мы решили только часть проблемы - нам еще нужно найти зависимости! Или ты забыл все об этом!? Хорошо, ты можешь пойти в туалет. Но лучше быть # 1.

3,2. Зависимость

Вау, ты даже помнишь, что у нас были номера разделов? На несвязанной ноте, когда я набрал последнее предложение, моя клавиатура произвела звук, напоминающий первую ноту в Super Mario Theme Song. Что сейчас застряло у меня в голове.

Ok! Итак, у нас есть наши возможности, у нас есть имена наших функций, время для идентификации вызовов функций! Это не займет много времени. Выполнение acorn.parse('foo()') дает:

{
  "type": "Program",
  "body": [{
    "type": "ExpressionStatement",
    "expression": {
      "type": "CallExpression",
      "callee": {
        "type": "Identifier",
        "name": "f"
      },
      "arguments": []
    }
  }]
}

Итак, мы ищем CallExpression. Но прежде чем мы перейдем к нему через walk, сначала рассмотрим нашу логику. Учитывая это node, что мы делаем? Как добавить зависимость?

Это не сложная проблема, поскольку мы уже позаботились обо всех областях. Мы добавляем к зависимостям содержащейся функции (parser.state.name) разрешение области callExpression.callee.name. Звучит просто!

var deps = parser.results.deps,
    scope = parser.state.scope,
    context = parser.state.name || '<global>';

if (!deps[context]) {
    deps[context] = [];
}

deps[context].push(scope.get(node.callee.name));

Есть еще один трюк с обработкой глобального контекста. Если текущее состояние является безымянным, мы предполагаем его глобальным контекстом и присвоим ему специальное имя <global>.

Теперь, когда у нас есть это, построим наш dependencyParser:

var dependencyParser = {
    parseCall : function (node) {
         ...the code above...
    }
};

Действительно красиво. Нам еще нужно изменить parser.walk, чтобы включить CallExpression s:

walk : function (node) {
    ...
    else if (type === 'CallExpression') {
        dependencyParser.parseCall(node);
    }
}

И попробуйте на примере D:

> parser.parse('function foo() { var foo = function () {}; foo(); } foo()').deps
{ foo: [ 'foo#foo' ], '<global>': [ 'foo' ] }

4. Откажитесь от проблемы

HAHA! В ВАШЕМ ЛИЦЕ, ПРОБЛЕМА! WOOOOOOOOOOO!

Вы можете начать празднование. Снимите штаны, бегите по городу, заявляйте, что вы - городская курица, и сжигаете мусорные баки (Zirak и Affiliates никоим образом не поддерживают поджог любого рода или непристойного воздействия. Любые действия, предпринятые о, скажем, любым читателем, не быть обвиненным в Zirak и/или Affiliates).

Но серьезно сейчас. Мы решили очень, очень ограниченное подмножество проблемы, и для ее решения в небольшом проценте реальных сценариев есть много вещей, которые нужно сделать. Это не разочарование - все наоборот! Я призываю вас попробовать и сделать это. Это весело! (Zirak и Affiliates никоим образом не ответственны за какие-либо умственные расстройства в результате попыток сделать то, что было сказано)

Представлен здесь исходный код анализатора, без каких-либо специфичных для NodeJS элементов (т.е. требующих желуди или выставления парсера):

var parser = {
    results : {},
    state : {},

    verbose : false,

    parse : function (string) {
        this.freshen();

        var root = acorn.parse(string);
        this.walk(root);

        return this.results;
    },

    freshen : function () {
        this.results = {};
        this.results.deps = {};

        this.state = {};
        this.state.scope = this.results.scope = Scope(null);
        this.state.name = '';
    },

    walk : function (node) {
        var type = node.type;

        //yes, this is tight coupling. I will not apologise.
        if (type === 'FunctionDeclaration' || type === 'FunctionExpression') {
            scopeParser.parseFunction(node)
        }
        else if (type === 'AssignmentExpression') {
            scopeParser.parseBareAssignmentExpression(node);
        }
        else if (type === 'VariableDeclaration') {
            scopeParser.parseVarDeclaration(node);
        }
        else if (type === 'CallExpression') {
            dependencyParser.parseCall(node);
        }
        else if (node.type === 'ExpressionStatement') {
            this.walk(node.expression);
        }
        //Program, BlockStatement, ...
        else if (node.body && node.body.length) {
            node.body.forEach(this.walk, this);
        }
        else if (this.verbose) {
            console.log(node, 'pass through');
        }
        //...I'm sorry
    },

    // ''    =>  'foo'
    // 'bar' =>  'bar#foo'
    nameToAbsolute : function (parent, name) {
        return parent ? parent + '#' + name : name;
    },

    cacheState : function () {
        var subject = this.state;
        return Object.keys( subject ).reduce(reduce, {});

        function reduce (ret, key) {
            ret[key] = subject[key];
            return ret;
        }
    },
    restoreState : function (st) {
        var subject = this.state;

        Object.keys(st).forEach(function (key) {
            subject[key] = st[key];
        });
    }
};

var dependencyParser = {
    //foo()
    //yes. that all.
    parseCall : function (node) {
        if (parser.verbose) {
            console.log(node, 'parseCall');
        }

        var deps = parser.results.deps,
            scope = parser.state.scope,
            context = parser.state.name || '<global>';

        if (!deps[context]) {
            deps[context] = [];
        }

        deps[context].push(scope.get(node.callee.name));
    }
};

var scopeParser = {
    // We only care about these kinds of tokens:
    // (1) Function declarations
    // function foo () {}
    // (2) Function expressions assigned to variables
    // var foo = function () {};
    // bar = function () {};
    //
    // Do note the following property:
    // var foo = function bar () {
    //     `bar` is visible, `foo` is not
    // };
    // `bar` is not visible, `foo` is

    /*
      function foo () {}
        =>
      {
        "type": 'FunctionDeclaration',
        "id": {
          "type": Identifier,
          "name": 'foo'
        },
        "params": [],
        "body": { ... }
      }

      (function () {})
        =>
      {
        "type": "FunctionExpression",
        "id": null,
        "params": [],
        "body": { ... }
      }
    */
    parseFunction : function (func) {
        if (parser.verbose) {
            console.log(func, 'parseFunction');
        }
        var startState = parser.cacheState(),
            state = parser.state,
            name = this.grabFuncName(func);

        state.scope = Scope(startState.scope);
        state.name = parser.nameToAbsolute(startState.name, name);

        if (func.id) {
            state.scope.add(name, state.name);
        }
        if (func.type === 'FunctionDeclaration') {
            startState.scope.add(name, state.name);
        }

        this.addParamsToScope(func);
        parser.walk(func.body);

        parser.restoreState(startState);
    },

    grabFuncName : function (func) {
        if (func.id) {
            return func.id.name;
        }
        else if (func.type === 'FunctionExpression') {
            return '<anon>';
        }
        else {
            //...this shouldn't happen
            throw new Error(
                'scope.parseFunction encountered an anomalous function: ' +
                    'nameless and is not an expression');
        }
    },

    /*
      [{
        "type": "Identifier",
        "name": "a"
      }, {
        "type": "Identifier",
        "name": "b"
      }, {
        "type": "Identifier",
        "name": "c"
      }]
    */
    addParamsToScope : function (func) {
        var scope = parser.state.scope,
            fullName = parser.state.name;

        func.params.forEach(addParam);

        function addParam (param) {
            var name = param.name;
            scope.add(name, parser.nameToAbsolute(fullName, name));
        }
    },

    parseVarDeclaration : function (tok) {
        if (parser.verbose) {
            console.log(tok, 'parseVarDeclaration');
        }

        tok.declarations.forEach(parseDecl, this);

        function parseDecl (decl) {
            this.parseAssignment(decl.id, decl.init);
        }
    },

    // Lacking a better name, this:
    // foo = function () {}
    // without a `var`, I call a "bare assignment"
    parseBareAssignmentExpression : function (exp) {
        if (parser.verbose) {
            console.log(exp, 'parseBareAssignmentExpression');
        }
        this.parseAssignment(exp.left, exp.right);
    },

    parseAssignment : function (id, value) {
        if (parser.verbose) {
            console.log(id, value, 'parseAssignment');
        }

        if (!value || value.type !== 'FunctionExpression') {
            return;
        }

        var name = id.name,
            val = parser.nameToAbsolute(parser.state.name, name);
        parser.state.scope.add(name, val);

        this.parseFunction(value);
    }
};

var Scope = function (parent) {
    var ret = { items : {}, parent : parent, children : [] };

    ret.get = function (name) {
        if (this.items[name]) {
            return this.items[name];
        }

        if (this.parent) {
            return this.parent.get(name);
        }

        //this is fake, as it also assumes every global reference is legit
        return name;
    };

    ret.add = function (name, val) {
        this.items[name] = val;
    };

    if (parent) {
        parent.children.push(ret);
    }
    return ret;
};

Теперь, если вы извините меня, мне нужен длинный душ.

Ответ 2

Нет.

Извините, это невозможно на довольно теоретическом уровне на динамическом языке с eval. Хорошие IDE обнаруживают основные вещи, но есть некоторые вещи, которые вы просто не можете обнаружить очень хорошо:

Возьмем ваш простой случай:

function a() {
   //do something
   b();
};

Немного усложни его:

function a() {
   //do something
   eval("b();")
};

Теперь нам нужно обнаружить материал в строках, отпустить на один шаг вперед:

function a() {
   //do something
   eval("b"+"();");
};

Теперь нам нужно определить результат выполнения строк. Позвольте сделать еще пару из них:

function a() {
   //do something
   var d = ["b"];
   eval(d.join("")+"();");
};

Все еще не доволен? Позвольте закодировать его:

function a() {
   //do something
   var d = "YigpOw==";
   eval(atob(d));
};

Теперь, это некоторые очень простые случаи, я могу усложнить их столько, сколько захочу. Там на самом деле нет способа запуска кода - вам придется запускать его на каждом возможном входе и проверке, и все мы знаем, что это непрактично.

Итак, что вы можете сделать?

Зависимые параметры в качестве параметров для функции и использование инверсии управления. Всегда указывайте на свои более сложные зависимости и не подразумевайте. Таким образом вам не понадобятся инструменты, чтобы узнать, что ваши зависимости:)

Ответ 3

Вы можете использовать статистический журнал профилирования (node --prof yourprogram, v8.log) для вычисления статистического графика вызовов. Взгляните на исходный код процессора журнала здесь и здесь

Ответ 4

• Получить код функции в виде строки: a.toString()
• Обратитесь к RegEx за возможными вызовами функций, такими как possiblefuncname( и possiblefuncname.call( и possiblefuncname.apply(
• Убедитесь, что `typeof possiblefuncname == 'function'
• IF 3 имеет значение TRUE, рекурсивно проверяет имя возможного имени для зависимостей
• Задайте свою зависимость.