(我提前道歉:我通常会尝试让我的答案变得幽默,以方便读者阅读,但在这种情况下我无法成功做到这一点。考虑到这个答案的长度双重道歉。)
0. TL;DR(针对“正常人”)问题
这不是一个容易的问题。我们不会完全解决它,而是会限制它的范围——我们只会解决我们关心的问题的一部分。我们将通过使用 JavaScript 解析器解析输入并使用简单的方法对其进行检查来完成此操作递归下降 http://en.wikipedia.org/wiki/Recursive_descent_parser算法。我们的算法将分析程序的范围并正确识别函数调用。
剩下的只是填补空白!结果位于答案的底部,因此我建议您抓住第一条评论 https://stackoverflow.com/questions/17905249/how-can-i-detect-all-dependencies-of-a-function-in-node-js/18004786#comment26329922_18004786如果你不想通读。
1. 限制问题
As 本杰明·格伦鲍姆的回答 https://stackoverflow.com/a/17905485/1348195说,由于 JavaScript 的动态特性,这是一个非常非常困难的问题。但是,如果我们限制自己处理某些事情,而不是制定适用于 100% 程序的解决方案,而是针对一小部分程序,会怎么样?
最重要的限制:
-
No
eval
。如果我们包括eval
,这是一个螺旋式的混乱。这是因为 eval 允许您使用任意字符串,这使得在不检查每个可能的输入的情况下无法跟踪依赖关系。 NodeJS 中没有document.write
s and setTimeout
只接受一个函数,所以我们不必担心这些。但是,我们也不允许虚拟机模块 http://nodejs.org/docs/latest/api/vm.html.
以下限制是为了简化该过程。它们可能是可以解决的,但解决它们超出了这个答案的范围:
-
没有动态键
obj[key]()
引入这个限制让我感到很难过,但在某些情况下它绝对是可以解决的(例如key = 'foo'
但不是key = userInput()
)
-
变量不是影子, no
var self = this
。绝对可以使用完整的范围解析器来解决。
-
没有时髦的表情, e.g.
(a, b)()
最后,这个答案中的实现的限制 - 要么是因为复杂性限制,要么是时间限制(但它们是非常容易解决的):
-
无需吊装,因此函数声明不会在作用域中浮动。
-
无对象处理。这很糟糕,但是处理类似的事情
foo.bar()
or this.foo()
程序复杂度至少会增加一倍。投入足够的时间,这是非常可行的。
-
仅尊重函数范围。 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 http://marijnhaverbeke.nl/acorn/因为我从来没有使用过它并且听到了很好的好评。我建议你玩一下,看看程序是什么样子的SpiderMonkeys 的 AST https://developer.mozilla.org/en-US/docs/SpiderMonkey/Parser_API#Node_objects.
现在我们有了一个神奇的解析器,它可以将 JavaScript 转换为 AST(一个抽象语法树 http://en.wikipedia.org/wiki/Abstract_syntax_tree),我们将如何从逻辑上处理寻找依赖关系?我们需要做两件事:
- 正确构建范围
- 了解函数调用引用的是哪个函数。
我们可以看到为什么上面的示例 D 可能不明确:有两个函数称为foo
,我们怎么知道是哪一个foo()
方法?这就是为什么我们需要实施范围界定。
3、解决问题
由于解决方案分为两部分,所以我们就这样解决。从最大的问题开始:
3.1.范围界定
所以...我们有一个 AST。它有一堆节点。我们如何建立一个范围?好吧,我们只关心函数范围。这简化了这个过程,因为我们知道我们只需要处理函数。但在我们讨论如何使用作用域之前,让我们先定义创建作用域的函数。
范围有什么?它不是一个复杂的存在:它有一个父范围(或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
节点与id
财产。那id
的名字就是我们函数的名字!假设我们有一个函数walk
它负责遍历节点,并且currentScope
and 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
调用,我们的依赖项查找器将会被干掉。此外,我们无法在依赖管理中区分它们 - 如果我们只是按函数名称添加到结果中,我们就会被覆盖。换句话说,我们需要一个绝对的函数名。
我选择用 a 来表示嵌套与分离#
特点。那么上面有一个函数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);
}
现在我们正在说话!是时候继续实际行动了doing某物!也许我一直在骗你,我什么都不知道,也许我惨败了,我继续写到现在,因为我知道没有人会读到这里,我会得到很多赞成票,因为这是一个很长的答案!?
哈!继续做梦吧!还有更多精彩!我无缘无故几天没坐这个! (作为一个有趣的社会实验,有人可以投票评论,说一些类似“脆裤船长很高兴见到你”的话吗?)
更严肃地说,我们应该开始制作解析器:什么保存我们的状态并遍历节点。由于我们最后将有两个解析器,作用域和依赖关系,因此我们将创建一个“主解析器”,在需要时调用每个解析器:
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
and 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
}
再说一次,主要是技术性问题 - 要理解这些,您需要使用橡子。我们希望确保正确地迭代并进入节点。表达式节点如(function foo() {})
has an 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 () {};
一个很好(而且很有趣!)的练习就是自己添加它们。但不用担心 - 它们将包含在最终的解析器中;
谁信啊!?是done带瞄准镜!完毕!让我们一起欢呼吧!
哦哦哦……你以为你要去哪里!?我们只解决了部分问题——我们仍然需要找到依赖关系!还是你把这一切都忘了!?好吧,你可以去厕所了。但最好是#1。
3.2.依赖性
哇,你甚至remember我们有部分编号吗?在一个不相关的音符上,当我输入最后一句时,我的键盘发出的声音让人想起超级马里奥主题曲的第一个音符。现在这件事一直萦绕在我的脑海里。
好的!所以,我们有了作用域,有了函数名称,是时候识别函数调用了!这不会花很长时间。正在做acorn.parse('foo()')
gives:
{
"type": "Program",
"body": [{
"type": "ExpressionStatement",
"expression": {
"type": "CallExpression",
"callee": {
"type": "Identifier",
"name": "f"
},
"arguments": []
}
}]
}
所以我们正在寻找一个CallExpression
。但在我们全部走之前walk
在此之前,我们首先回顾一下我们的逻辑。给定这个节点,我们做什么?我们如何添加依赖项?
这不是一个困难的问题,因为我们已经处理了所有的范围界定。我们添加到包含函数的依赖项(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.模拟问题
哈哈!在你面前,问题!呜呜呜!
你可以开始庆祝活动。脱掉裤子,在城里跑来跑去,声称自己是镇鸡,烧掉流浪垃圾桶(Zirak 及其附属公司绝不支持任何形式的纵火或不雅暴露。哦,比如说,任何读者采取的任何行动都不应归咎于 Zirak 和/或附属公司).
但现在说真的。我们解决了问题的非常非常有限的子集,为了解决一小部分实际场景,需要做很多事情。这并不是一种沮丧——恰恰相反!我敦促你尝试这样做。好有趣! (Zirak 和附属公司对因尝试执行刚才所说的内容而导致的任何精神崩溃不承担任何责任)
这里展示的是解析器的源代码,没有任何 NodeJS 特定的东西(即需要 acorn 或公开解析器):
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;
};
现在请原谅,我需要洗个长时间的澡。