如何检测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
和currentFuncName
variables,我们刚刚到达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的依赖关系
- 设置你的依赖。