(我提前道歉:我通常会尝试使我的答案变得幽默,以使读者轻松通过它们,但在这种情况下我无法成功地做到这一点。考虑到对这个答案的长度的双重道歉。)
0. TL;DR(对于“正常人”)的问题
这不是一个容易的问题。我们不会完全解决它,而是限制它的范围——我们只会解决我们关心的问题的一部分。我们将通过使用 JavaScript 解析器解析输入并使用简单的递归下降算法对其进行处理。我们的算法将分析程序的范围并正确识别函数调用。
其余的只是填补空白!结果在答案的底部,因此如果您不想通读,我建议您抓住第一条评论。
1. 限制问题
正如Benjamin Gruenbaum 的回答所说,由于 JavaScript 的动态特性,这是一个非常非常困难的问题。然而,如果我们不是为 100% 的程序制定解决方案,而是为程序的一个子集做,如果我们限制自己处理某些事情怎么办?
最重要的限制:
- 没有
eval
。如果我们包括eval
,那就是陷入混乱的漩涡。这是因为 eval 让您使用任意字符串,这使得在不检查每个可能的输入的情况下跟踪依赖关系是不可能的。在 NodeJS 中没有document.write
s 并且setTimeout
只接受一个函数,所以我们不必担心这些。但是,我们也不允许使用vm 模块。
以下限制是为了简化该过程。它们可能是可解决的,但解决它们超出了此答案的范围:
- 没有动态键
obj[key]()
让我很难过引入这个限制,但在某些情况下它绝对是可以解决的(例如key = 'foo'
但不是key = userInput()
)
- 变量不是阴影,不是
var self = this
。绝对可以使用完整的范围解析器解决。
- 没有时髦的表达,例如
(a, b)()
最后,这个答案中的实施限制 - 由于复杂性限制或时间限制(但它们非常容易解决):
- 没有提升,所以函数声明不会在作用域中出现。
- 没有对象处理。这很糟糕,但处理类似
foo.bar()
或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();
为了理解一个程序,我们需要分解它的代码,我们需要理解它的语义:我们需要一个解析器。我选择了橡子,因为我从未使用过它并且听到了很好的赞誉。我建议你玩一下,看看SpiderMonkeys 的 AST中的程序是什么样的。
现在我们有了一个神奇的解析器,可以将 JavaScript 转换为 AST(抽象语法树),我们将如何在逻辑上处理查找依赖项?我们需要做两件事:
- 正确构建范围
- 了解函数调用所指的函数。
我们可以看到为什么上面的示例 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
和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
调用中的哪一个,并且我们的依赖查找器将是 toast。此外,我们将无法在依赖管理中区分它们——如果我们只是通过函数名添加到结果中,我们将被覆盖。换句话说,我们需要一个绝对的函数名。
#
我选择用一个字符来表示嵌套。那么,上面有一个函数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);
}
现在我们在说话!是时候继续实际做点什么了!也许我一直对你撒谎,我一无所知,也许我失败得很惨,我一直写到现在,因为我知道没有人会读到这么远,我会得到很多赞成,因为答案很长!?
哈哈!继续做梦!还有更多!这几天我无缘无故没坐!(作为一个有趣的社会实验,任何人都可以点赞评论,说“Crunchpants 船长很高兴见到你”这样的话吗?)
更严肃地说,我们应该开始制作解析器:什么保持我们的状态并遍历节点。由于最后我们将有两个解析器,范围和依赖关系,我们将创建一个“主解析器”,在需要时调用每个解析器:
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
}
同样,主要是技术性 - 要理解这些,您需要使用橡子。我们要确保我们正确地迭代并进入节点。表达式节点(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. 依赖
哇,你还记得我们有节号吗?在一个无关的音符上,当我输入最后一句话时,我的键盘发出的声音让人想起超级马里奥主题曲的第一个音符。现在卡在我的脑海里。
好的!所以,我们有了作用域,有了函数名,是时候识别函数调用了!这不会花很长时间。做acorn.parse('foo()')
给:
{
"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;
};
现在,请原谅我,我需要洗个澡。