如何检测Node.js中的所有函数的依赖关系？
我试图给我一个广泛的图片我的问题。 我需要用Node.js编写一个应该能够检测到所有依赖关系的程序。
例如
function a() { //do something b(); }; function b() { console.log("Hey, This is b"); }; 在上面的例子中，我需要像这样的JSON：
{ "a": { dependencies: ["b"], range: [1, 4] }, "b": { dependencies: [], range: [5, 8] } }
在dependencies属性中，我需要有一个函数内部调用的函数的数组， range我的意思是函数定义的行范围。
我需要一个解决scheme来实现这个目标。 有Node.js的工具或插件吗？
（我提前道歉：我通常会尽量让自己的答案幽默，让读者顺利通过它们，但在这种情况下，我不能成功地做到这一点，考虑到这个答案的长度，双重道歉。
0. TL; DR（对于“正常人”）的问题
这不是一个简单的问题。 我们不是全部解决问题，而是限制其范围 – 我们只能解决我们所关心的问题的一部分。 我们将通过使用JavaScriptparsing器parsinginput并使用简单的recursion下降algorithm来解决此问题。 我们的algorithm将分析程序的范围并正确识别函数调用。
其余的只是填补空白！ 结果是在答案的底部，所以我build议你抓住第一个评论，如果你不想通读。
1.限制问题
正如Benjamin Gruenbaum的回答所说，由于JavaScript的dynamic性，这是一个非常非常困难的问题。 但是，如果我们不去制定一个解决scheme，而这个解决scheme可以为100％的程序工作，那么如果我们限制自己去处理某些事情的话，我们反而会做一些子程序呢？
最重要的限制：
- 没有
eval。 如果我们包括eval，这是一个混乱的螺旋。 这是因为eval让我们使用任意的string，这使得跟踪依赖不可能没有检查每个可能的input。 在NodeJS中没有document.write和setTimeout只接受一个函数，所以我们不必担心这些。 但是，我们也禁止vm模块 。
以下限制是为了简化过程。 他们可能是可以解决的，但解决这个问题已经超出了这个答案的范围：
- 没有dynamic键
obj[key]()它让我难过，介绍这个限制，但它是肯定可以解决一些情况下（例如key = 'foo'而不是key = userInput()） - variables不是阴影 ，没有
var self = this。 完全可以解决的范围parsing器。 - 没有时髦的expression ，例如
(a, b)()
最后，在这个答案中的实现的限制 – 或者是因为复杂性约束或者时间限制（但是它们是非常可以解决的）：
- 没有提升 ，所以函数声明不会在范围内浮动。
- 没有对象处理 。 这很糟糕，但是处理像
foo.bar()或this.foo()这样的东西至less会使程序复杂度增加一倍。 投入足够的时间，这是非常可行的。 - 只有function范围是荣幸的 。 JavaScript中有很多方法来定义函数以外的作用域（
with语句，catch块）。 我们不处理它们。
在这个答案中，我将概述（并提供）一个概念certificate分析器。
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();
为了理解一个程序，我们需要分开它的代码，我们需要理解它的语义：我们需要一个parsing器。 我select了橡子，因为我从来没有使用它，并听到好评。 我build议你玩一下，看看SpiderMonkeys的AST里有什么程序。
现在我们有一个将JavaScript转换成AST（一种抽象语法树 ）的神奇parsing器，我们将如何在逻辑上处理查找依赖关系？ 我们需要做两件事情：
- 正确构build范围
- 了解函数调用引用哪个函数。
我们可以看到为什么上面的例子D可能是模糊的：有两个函数叫做foo ，我们怎么知道foo()是什么意思？ 这就是为什么我们需要实施范围界定。
3.解决问题
由于解决scheme分为两部分，我们就这样解决。 从最大的问题开始：
3.1。 作用域
所以…我们有一个AST。 它有一堆节点。 我们如何build立一个范围？ 那么，我们只关心function范围。 这简化了这个过程，因为我们知道我们只需要处理function。 但是在我们讨论如何使用范围之前，我们来定义一下这个范围的函数。
范围有什么？ 它不是一个复杂的存在：它有一个父范围（如果它是全局范围，则为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没有在任何范围内定义，那么它必须是一个现有的全局variables。 这可能是也可能不是可取的。
好的，我们有一种方法来表示范围。 不要破开香槟酒，我们还是要真正做出来！ 让我们看看一个简单的函数声明， 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": { ... } }
我们有一个带有id属性的FunctionDeclaration节点。 这个id的名字是我们的function的名字！ 我们假设我们有一个遍历节点的函数walk ， currentScope和currentFuncNamevariables，我们刚刚到达parsing我们的函数声明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;
但是等等，函数expression式呢？ 他们的行为有点不同！ 首先，他们不一定有一个名字，如果他们这样做，它只是在他们内部可见：
var outer = function inner () { //outer doesn't exist, inner is visible }; //outer is visible, inner doesn't exist
让我们做一个大的假设，我们已经处理了variables声明部分 – 我们在父范围创build了适当的绑定。 那么，处理函数的上面的逻辑只会稍微改变：
... //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); } ...
信不信由你，这或多或less是最终解决scheme中的整个范围处理机制。 我希望在添加对象之类的东西的时候会变得更加复杂一些，但不是太多。
现在是时候认识Crunchpants队长了。 现在非常细心的听众会记得例子D.让我们来回忆我们的记忆：
function foo () { function foo () {} foo(); } foo();
在parsing中，我们需要一种方法来告诉外部foo和内部foo分开 – 否则，我们将无法知道这些foo调用中的哪一个，并且我们的依赖查找器将被烘烤。 而且，我们无法在依赖pipe理中将它们分开 – 如果我们只是通过函数名称添加结果，我们将会覆盖。 换句话说，我们需要一个绝对的函数名称。
我select用#分隔嵌套。 然后，上面有一个函数foo ，内部函数foo#foo ，调用foo#foo和调用foo 。 或者，一个不太令人困惑的例子：
var outer = function () { function inner () {} inner(); }; outer();
有一个函数outer和一个函数outer#inner 。 有一个呼叫outer#inner和呼吁outer 。
所以，我们创build一个采用前一个名称和当前函数名称的函数，并将它们组合在一起：
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); }
现在我们在说话！ 现在是时候继续做实际的事情了！ 也许我一直对你撒谎，我一无所知，也许我失败了，我继续写作，直到现在，因为我知道没有人会读到这么远，我会得到很多upvotes，因为这是一个长的答案！
哈！ 保持梦想！ 还有更多要来！ 我没有理由坐这几天。 （作为一个有趣的社会实验，有没有人可以提出评论，说一句“Crunchpants队长很高兴见到你”？）
更严重的一点是，我们应该开始制作parsing器 ：什么保持我们的状态，并且遍历节点。 由于我们在最后有两个parsing器，范围和依赖关系，所以我们将创build一个“主parsing器”，在需要时调用每个parsing器：
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是空的。 时间来填补呃！
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 }
再次，主要是技术 – 要理解这些，你需要玩橡子。 我们要确保我们迭代并正确地走进节点。 expression式类似于(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] }
整齐！ 玩弄函数声明和expression式，看它们是否正确嵌套。 但是我们忘记了包含variables声明：
var foo = function () {}; bar = function () {};
一个好的（好玩的）练习是自己添加它们。 但是别担心，它们将被包含在最终的parsing器中。
谁会相信！？ 我们完成了范围！ DONE！ 我们来欢呼吧！
哦，哦，哦，你以为你要去哪里？ 我们只解决了部分问题 – 我们仍然需要find依赖关系！ 还是你忘了一切！？ 好的，你可以去厕所。 但最好是＃1。
3.2。 依赖
哇，你还记得我们有章节号吗？ 在一个不相干的笔记上，当我input最后一句话时，我的键盘听起来让人联想到超级马里奥主题曲的第一个音符。 这现在困在我的头上。
好！ 所以，我们有我们的范围，我们有我们的函数名称，是时候确定函数调用！ 这不会太久。 做acorn.parse('foo()')给出：
{ "type": "Program", "body": [{ "type": "ExpressionStatement", "expression": { "type": "CallExpression", "callee": { "type": "Identifier", "name": "f" }, "arguments": [] } }] }
所以我们正在寻找一个CallExpression 。 但在我们走之前，我们先来回顾一下我们的逻辑。 鉴于这个节点，我们做什么？ 我们如何添加一个依赖？
这不是一个难题，因为我们已经考虑了所有的范围。 我们向包含函数（ 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> 。
现在我们有了，我们来构build我们的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.嘲笑这个问题
哈哈！ 在你的脸上，问题！ WOOOOOOOOOOO！
你可以开始庆祝活动。 去掉你的裤子，在城市里跑来跑去，声称你是城里的鸡，烧毁stream浪的垃圾桶（ Zirak和联属公司绝不会支持任何forms的暴力或不雅暴露的纵火。被指责Zirak和/或分支机构 ）。
但现在严重。 我们解决了这个问题的一个非常非常有限的子集，为了解决这个问题，只有一小部分的实际情况需要做很多事情。 这不是一种灰心 – 恰恰相反！ 我强烈build议你这样做。 好有趣！ （ Zirak和附属公司不会因为尝试刚才所说的而导致精神崩溃 ）
这里展示的是parsing器的源代码，没有任何NodeJS特定的东西（即需要橡子或暴露parsing器）：
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's 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; };
现在，如果你能原谅我，我需要长时间的淋浴。
没有。
对不起，在eval的dynamic语言中，这在理论上是不可能的。 良好的IDE检测基本的东西，但有一些东西，你根本无法很好地检测：
让我们把你的简单情况：
function a() { //do something b(); };
让我们复杂一点：
function a() { //do something eval("b();") };
现在我们必须检测string中的东西，让我们先走一步：
function a() { //do something eval("b"+"();"); };
现在我们必须检测stringconcats的结果。 让我们再做一些：
function a() { //do something var d = ["b"]; eval(d.join("")+"();"); };
还是不开心？ 让我们编码它：
function a() { //do something var d = "YigpOw=="; eval(atob(d)); };
现在，这些是一些非常基本的情况，我可以尽可能多地把它们复杂化。 实际上没有办法运行代码 – 你必须在每个可能的input和检查上运行它，我们都知道这是不切实际的。
所以，你可以做什么？
将依赖关系作为parameter passing给函数并使用控制的反转。 始终明确你的更复杂的依赖关系，而不是隐含的。 这样你就不需要工具来知道你的依赖是什么:)
您可以使用统计分析器日志（ node --prof yourprogram ，v8.log）来计算“统计”调用图。 看看这里和这里的日志处理器源代码
- 以stringforms获取函数的代码：
a.toString() - 使用RegEx检查可能的函数调用，如
possiblefuncname(和possiblefuncname.call(和possiblefuncname.apply( - 检查'typeof possiblefuncname =='函数'
- IF 3是TRUE，recursion地检查possiblefuncname的依赖关系
- 设置你的依赖。