[代码]解析nodejs的require,吃豆人的故事

时间:2021-12-05 03:31:21

最近在项目中需要对nodejs的require关键字做解析,并且替换require里的路径。一开始我希望nodejs既然作为脚本语言,内核提供一个官方的parser库应该是一个稳定可靠又灵活的渠道,然而nodejs里面只一个了一个加载js文件并得到对应的module的能力,module能获取export的函数及其对应的源代码的能力,但是代码已经是闭包过后的,实际上能力很有限。

而我实际上需要的是一个官方的js parser,我希望它是用nodejs写的,轻量的,能得到完整的AST。这样我们就可以在转换代码的环节做很多自动化的工作。既然nodejs官方没有提供这样的模块,应该有多第三方可用的库。我上*上搜一下,这个帖子里有涉及到一些:https://*.com/questions/2554519/javascript-parser-in-javascript

可以从帖子中track到这几个库:

这几个库各有千秋,有时间可以慢慢看,或者重点挑1-2个仔细阅读。不过看了这几个库之后,我又改变了主意,我觉的就我的需求来说,只要能找到require('xxx')的地方做替换就好了,杀鸡何必用牛刀。我的第一想法是直接逐行用正则表达式匹配下就好。核心正则表达式如下:

let regexs = [
/[(\s=?:,;]require\s*(\s*'([^"'`]+)'\s*\)/,
/[(\s=?:,;]require\s*\(\s*"([^"'`]+)"\s*\)/,
/[(\s=?:,;]require\s*\(`([^"'`]+)`\s*\)/,
];

其中[(\s=?:,;]表示上一个表达式的可能结束符;中间是require关键字;然后是左括号(前后可能有空格),接着是字符串,最后是右括号(前后可能有空格)。第一时间写的当然是漏洞很多了,跑几个例子就发现问题:

  • 任何可能插入空格的地方,都可能插入注释(comment),并且js有两种注释:
    • 单行注释(//)
    • 多行注释(/*...*/)
  • require关键字可能出现的位置
    • 可能出现在普通代码里,
    • 可能出现在字符串里
    • 可能出现在注释里
  • 表达式本身可能跨行

光前两点,直接会把正则表达式的匹配搞的很复杂,如果是个正则表达式狂人,当然可以继续折腾,并且最后折腾出来。毕竟JavaScript最新标准,正则表达式模块的能力已经很完备了,几乎不逊于C#的正则表达式。

但是我写腻了正则表达式,我觉的还是老老实实写一个逐字符的parser来的更简洁。我不要求性能多高,只要求代码直观易读,结果正确,优化的事情,留给后面来做。那就动手开始写。

分析一下,根据上面的3点,nodejs的代码可以被切成5种大的token即可:

  • 连续的空格,注意这里说的是whitespace,包括这些字符:
    • let spaces = [' ','\t','\b','\n','\v','\r','\r\n'];
  • 注释,又分成两种:
    • 单行注释:以//开头,到行尾结束
    • 多行注释:以/*开头,到*/结束
  • 字符串,又分成三种:
    • 单引号字符串:'xxxxxx'
    • 双引号字符串:"yyyyyy"
    • 表达式字符串:`id: ${id}, value:${value}`
  • require表达式,产生式的顺序如下:
    • 可能的前缀: let prefix=[' ','=','?',':',',',';','('],例如问号表达式的?:后面都可以合法的require。
    • 可能的空格,注释
    • require关键字匹配
    • 可能的空格,注释
    • 左括号
    • 可能的空格,注释
    • 字符串,此处不考虑非字符串情况(例如变量)
    • 可能的空格,注释
    • 右括号
  • 其他代码

分析完上面5种token之后,思路就清晰了,我们不需要把代码解析到JavaScript级别的Token,只需要解析出上述5种token,则就可以替换掉其中的require部分。然而,在此之前,我们需要提供一组非常基本的字符串解析函数。

在此之前的在此之前,做一个简化:一次性把代码文件读出来,作为utf8字符串使用。这样便于parser的编写,后续如果有必要优化的话,我们再换成stream就好了:

const fs = require('fs');

/**
* 注释中的require('你不应该解析到我,我不是真的require,我只是个注释,别当真');
*/
let filePath = __filename;//测试中,直接使用正在编写的代码作为测试输入
let text = fs.readFileSync(filePath); /**
* 定义一个存储解析过程中状态的对象
* 实际上,这种对象包含的字段往往是在写代码中随时添加/删除的,而不是
* 一开始就是最终代码里的样子,所以,我们可以还原这个过程。现在,它
* 只有两个字段:filePath和text,在后续的代码中根据需要,我们随时
* 调整。
**/
let context = {
filePath: filePath,
text: text
};

回到在此之前,我们需要一组基础的读取字符串的方法。解析字符串的过程中,最基本的两个动作是:

  • 向前查看一个或多个字符串
  • 前进一个或多个字符串

尝试一下,写个最简单的版本:

function nextChar(count){
// context需要一个end字段表示是否已经遍历结束
if(context.end){
return null;
} let from = context.pos; //当然,我们需要给他context添加一个变量pos表示当前下标
let to = from + count;
return context.text.substring(from, to);
}

可以看到,为了写nextChar,我们需要给context增加两个字段:

let context = {
filePath: filePath,
text: text,
pos: 0, // +1 当前字符下标
end: false // +1 遍历是否结束
};

实际上,nextChar函数可以再做一下改进:

  • 如果不传入count的时候,我们希望它默认只返回下一个字符
  • 如果to >= context.text.length,应该结束

改进版如下,很不幸,有时候很难第一次写对,按需修补使得最后满足需求是常态:

function nextChar(count=1){
// context需要一个end字段表示是否已经遍历结束
if(context.end){
return null;
} let from = context.pos; //当然,我们需要给他context添加一个变量pos表示当前下标
let to = from + count;
to = Math.min(to,context.text.length);
return context.text.substring(from,to);
}

好了,是时候准备好另一个不起眼的小函数了:向前走几步。千里之行,始于足下,走一步再说:

function stepChar(){
context.pos++; // 检测是否结束
if(context.pos>=context.text.length){
context.end = true;
}
}

Pefect! 功能越小代码越好写,我希望世界上所有的函数都是需求明确而又功能简单的,不过很快就发现,往往需要步进多次,代码会是这样的:

stepChar();
stepChar();
stepChar();

很早的时候,Uncle Wang就说过逢三则优:

function stepChar(count=1){
// 换个马甲,定义一个stepOnce:
let stepOnce = ()=>{
context.pos++;
if(context.pos>=context.text.length){
context.end = true;
}
}; // 正步走,让走几步就走几步,除非走不动了
for(let i=0;i<count;i++){
if(context.end){
return;
}
stepOnce();
}
}

Pefect! Again! 这次,怎么看都像是完成了必要的工作了。No, No, No,看到context.pos++,总会“自然而然”联想到矩阵,或者Excel,Matlab,什么都行,他们和文本文件有一个共同的需求,就是换行,纸片人需要知道自己在二维坐标里的位置,Excel、Matlab往往是方方的二维世界,而文本文件则充满了锯齿。引入锯齿换行二维世界的坐标,便于肉眼快速定位到代码:

function stepChar(count=1){
// 换个马甲,定义一个stepOnce:
let stepOnce = ()=>{
console.assert(context.end===false);
let c = context.text[context.pos]; // 锯齿世界的纸片人坐标
let line = ['\n','\r','\r\n'];
if(line.indexOf(c)>=0){
context.lineNo++;
context.column = 0;
}else{
context.column++;
} // 步进
context.pos++;
if(context.pos>=context.text.length){
context.end = true;
}
}; // 正步走,让走几步就走几步,除非走不动了
for(let i=0;i<count;i++){
if(context.end){
return;
}
stepOnce();
}
}

Again,你看到,由于需要记录锯齿世界的纸片人的坐标,context再次扩充:

let context = {
filePath: filePath,
text: text,
pos: 0,
end: false,
lineNo:0, // +1 当前行号
column: 0, // +1 当前列号
}

现在,我们可以使用nextChar函数来实现向前看一下,下面的token是什么?。如果我们实现了向前看一下,下面的token是什么?,那么,只要我们再实现那么,吃掉下面这个token,你猜会发生什么?先把这两个动作记录下来:

  • 吃豆人向前看一下,下面的豆子是什么品种?
  • 吃豆人知道了下一个品种的豆子吃掉。

当然,随着吃豆人吃了一个又一个豆子,纸片人的锯齿世界里的豆子就会一直一直的变少。一开始是这样的:

   --------------
---/****/-------
---------//--
--- -----
--`${a}/${b}`----"..."-----'...'-------
---- require('fs') --------

吃掉连续的空格,剩下:

--------------
---/****/-------
---------//--
--- -----
--`${a}/${b}`----"..."-----'...'-------
---- require('fs') --------

吃掉连续的其他代码,剩下:

/****/-------
---------//--
--- -----
--`${a}/${b}`----"..."-----'...'-------
---- require('fs') --------

吃掉注释,剩下:

-------
---------//--
--- -----
--`${a}/${b}`----"..."-----'...'-------
---- require('fs') --------

吃掉其他代码注释,其他代码,空格,其他代码字符串,其他代码,字符串,其他代码,字符串,其他代码空格,剩下:

require('fs') --------

哦,耶!,吃到了require表达式,记录下它在锯齿世界的坐标: lineNo,column,begin,end,剩下:

 --------

再吃掉空格,吃掉其他代码,哦哦,吃豆人没的吃了。

好的,那我们就来做第一件事,实现吃豆人向前看一下,下面的豆子是什么品种?,从最基本的开始,分别实现5种向前看函数:

  • 向前看,可能是空格么?
  • 向前看,可能是注释么?单行注释或者多行注释?
  • 向前看,可能是字符串么?单引号,双引号,还是表达式引号?
  • 向前看,可能是require表达式么?
  • 都不是,那就是其他代码吧?

first, we try:

function lookupSpace(){
const c = nextChar();
const spaces = [' ','\t','\b','\n','\v','\r','\r\n'];
return spaces.indexOf(c)>=0;
}

then, we trust:

function lookupSingleLineComment(){
let c = nextChar(2);
return c==='//';
} function lookupMultiLineComment(){
let c = nextChar(2);
return c==='/*';
} function lookupComment(){
let c = nextChar(2);
return c==='//'||c==='/*';
}

now, repeat:

function lookupString(){
let c = nextChar();
let quotes = [`'`,`"`,'`'];
return quotes.indexOf(c)>=0;
}

but, how to implement lookup require?

不,我们应该在此休息一下,虽然require看上去比较复杂一点,但是根据我们的原则,我们是不会因为它的步骤可能更多而失去信心的,我们应该相信基于我们一直采用的手法是有效的证据,来增强信心,步骤多不是问题,方式对了问题就能收敛。严肃点分析,require表达式是这样的一种故事结构:

“一开始可能是空格、等号、问号、冒号、逗号、分号,左括号前缀,然后可能是空格、注释/空格,注释/空格...,进而一定是require7个字符,接着又可能是空格、注释/空格,注释/空格...,一定是左括号,接着又可能是空格、注释/空格,注释/空格...,一定是字符串,接着又可能是空格、注释/空格,注释/空格...,一定是右括号,game over”。

我猜,这个故事结构是很棒的儿童故事题材,吃豆人系列故事。

言归正传,我们看到可能多次出现的可能是空格、注释/空格,注释/空格...,你是在逗我么,绕晕我了。不,这是吃豆人最喜欢的游戏,为此,吃豆人必须准备好一系列的跳过那个豆子,别踩坏了!,或者嘿!这是个字符串豆子,请跳过去!之类的游戏文本。

跳过指定字符序列?如下:

function skipChar(ch){
let c = nextChar(ch.length);
if(c===ch){
stepChar(ch.length);
return true;
}
return false;
}

跳过空格?如下:

function skipSpaces(){
let spaces = [' ','\t','\b','\n','\v','\r','\r\n'];
let hint=false;
while(true){
// 动作<1> 取出一个当前字符
let c = nextChar();
if(c==null){
return hint;
} // 动作<2> 判断豆子是否能吃
if(spaces.indexOf(c)>=0){
// 动作<2.1> 吃豆子
if(!hint){
hint = true;
context.token.type='whitespace'; // 当前token
}
stepChar();
}else{
// 动作<2.2> 没有豆子!(注意,当我们说“没有豆子”,和我们说“最后一个豆子”了,是不一样的哦)
return hint;
}
}
};

注意到,当我们吃掉一个某种类型的豆子的时候,我们需要记录它的类型、位置等信息,我们在context里增加一些字段,用于记录。

let context = {
filePath: filePath,
text: text,
pos: 0,
end: false,
lineNo:0,
column: 0,
token:{ // +1 当前token信息
begin:0, // 开始下标
end:0, // 结束下标
text: 0, // 原始文本
type: null, // 类型
lineNo:0, // 在第几行
column:0, // 在第几列
},
tokens:[], // +1 存放所有搜集到的token
}

跳过字符串?倒车,请注意!倒车,请注意!,你需要注意,要检测真正的右引号,而不是在字符串内部的被转义的右引号。转义字符是理解编码的一个钥匙,一个字符被用来做token开始结束的标志,那么在开始和结束的中间,你需要表达这个边界字符的时候,你就需要用到转义字符,这就是编码。

function skipQuoteString(sc){
let last = null; let c = nextChar();
if(c==null){
return false;
} // 左引号
if(c===`${sc}`){
stepChar(); while(true){ // 动作<1> 取出一个豆子
c = nextChar();
if(c==null){
return false;
} // 动作<2> 判断豆子是否能吃
if(c!==`${sc}`||last!==`\\`){
// 动作<2.1> 吃豆子
if(last==='\\'&&c==='\\'){
last = null;
}else{
last = c;
}
stepChar();
}else{
// 动作<2.2> 最后一个豆子(当然是“右引号”豆子)
stepChar();
return true;
}
}
}else{
return false;
}
}

在跳过注释之前,我们先增加一个一直往前跳,直到遇到下一行的规则:

function skipLine(){
let line = ['\n','\r','\r\n'];
let hint=false;
while(true){
// 动作<1>: 取出豆子
let c = nextChar();
if(c==null){
return hint;
} // 动作<2>:判断豆子是否能吃
if(line.indexOf(c)<0){
// 动作<2.1> 吃豆子
if(!hint){
hint = true;
}
stepChar();
}else{
// 动作<2.2> 最后一个豆子,
stepChar();
return hint;
}
}
}

我希望,你能在一次又一次的重复中注意到这两个过程:

  • 过程<1>
    • 取出一个豆子
    • 判断豆子是否能吃
      • 豆子能吃,吃掉那个豆子,重复过程<1>
      • 没有豆子,结束
  • 过程<2>
    • 取出一个豆子
    • 判断豆子是否能吃
      • 豆子能吃,吃掉那个豆子,重复过程<2>
      • 最后一个豆子,吃掉,结束

无论是过程<1>,还是过程<2>,你会发现吃豆人,吃完一波后,当前的nextChar()是预留给下一波吃的。这个过程是这样的:

AAABBBCCC

假设吃豆人要分三次分别吃掉AAA、BBB、CCC,那么用数字表示context.pos,动作序列如下:

豆列:AAABBBCCC
pos: 0

则,动作:skip AAA结束后,变成:

豆列:AAABBBCCC
pos: 3

当前的pos=3,指向了第一个B,动作:skip BBB结束后,变成:

豆列:AAABBBCCC
pos: 6

当前的pos=6,指向了第一个C,动作:skip CCC结束后,变成:

豆列:AAABBBCCC
pos: 8

pos到了末尾,就不再+1了。

万事俱备,只欠东风。可以开工把注释给吃掉了,无论是单行还是多行,都不在话下。

function skipComment(){
let c = nextChar(2);
if(c==null){
return false;
} // 判断是单行还是多行
if(c=='//'){
// 吃掉'//'
stepChar(2); // 单行注释,直接吃掉这行剩下的
skipLine();
context.token.type='singleLineComment';
return true;
}else if(c=='/*'){
// 吃掉'/*'
stepChar(2); // 多行注释,一直吃到看到'*/'为止
while (true) { // 动作<1> 取出两个豆子
c = nextChar(2); // 动作<2> 判断豆子是否能吃
if(c!=='*/'){
// 动作<2.1> 吃掉豆子,不过如果遇到 x* 的模式,
// 后面那个*要保留,因为可能和下一个字符构成*/
if(c[1]==='*'){
stepChar();
}else {
stepChar(2);
}
}else{
// 最后两个豆子了,吃掉 
stepChar(2);
context.token.type='multiLineComment';
return true;
}
}
}else{
return false;
}
};

我们看到,在吃多行注释的过程,稍有有所变化,不过基本上和过程<2>是一样的,稍加泛化,可以得到一个更灵活的版本:

  • 过程<3>
    • 取出N个豆子
    • 判断这N个豆子是否能吃
      • 豆子能吃,吃掉N个豆子中的M个,重复过程<3>
      • 豆子不能吃,判断是否结束
        • 如果没有豆子,结束
        • 如果是最后L个豆子,吃掉这L个豆子,结束

终于,我们可以表达空格,注释/空格,注释/空格...的时刻了,我们决定,把注释/空格,注释/空格,...这个模式实现出来:

skipComments(){
// 假设连续的空格已经被吃掉了
let hint = false;
while (true) {
// 注释
if(skipComment()){
hint = true;
// 空格
skipSpaces();
}else{
// 结束
return hint;
}
}
};

之前,我们提到过,要在解析的过程中记录token的信息,因此,我们需要提供一个记录窗口。类似:

  • 开始计时
  • 跑步
  • 结束计时,显示计时统计信息

好的,是这样的:

function tokenStart(){
// 记录开始位置
context.token.begin = context.pos;
context.token.end = 0;
context.token.type = null;
} function tokenEnd(ret){ if(!ret){
return null;
} // 计算结束位置
context.token.end = context.pos;
if(context.token.type==='singleLineComment'){
context.token.end--;
} // 记录token信息
let t = context.text.substring(context.token.begin, context.token.end);
context.token.lineNo = context.lineNo+1;
context.token.column = context.column;
context.token.text = t;
context.token.next = context.text.substring(context.token.end,context.token.end+10);; // 拷贝一份收集起来,避免覆盖
let token = Object.assign({},context.token);
if(context.token.type!=='whitespace'){
context.tokens.push(token);
} return token;
}

有了开始、结束的记录仪,就可以着手提供真正的吃豆人函数了:

  • 吃掉空格
  • 吃掉注释
  • 吃掉字符串

吃掉空格:

function eatSpaces(){
tokenStart();
let ret = skipSpaces();
tokenEnd(ret);
return ret;
};

吃掉注释:

function eatComment(){
tokenStart();
let ret = skipComment();
tokenEnd(ret);
return ret;
};

当然,吃掉注释/空格,注释/空格,...:

function eatComments(){
// 假设连续的空格已经被吃了
let hint = false;
while (true) {
// 注释
if(eatComment()){
// 空格
hint = true;
eatSpaces();
}else{
return hint;
}
}
};

还有,吃掉字符串:

eatString(){
tokenStart();
let ret = skipString();
tokenEnd(ret);
return ret;
}

以及,吃掉字符串, 【空格, 注释/空格,注释/空格..】,字符串, 【空格, 注释/空格,注释/空格..】,...:

function eatStrings(){
// 假设连续的空格已经被吃了
let hint = false;
while (true) {
// 字符串
if(eatString()){
// 空格
hint = true;
eatSpaces(); // 注释/空格
eatComments();
}else{
return hint;
}
}
}

吃豆人,吃了这么多快餐之后,决定来一个大餐。之前的nextChar(count)只能往前看几个字符,吃豆人想:“世界那么大,我想去远方看看”。于是它改造了下nextChar,使得它具有去“远方”看看的能力:

function nextCharOffset(offset,count){
if(context.end){
return null;
}else{
console.assert(offset!=null);
console.assert(count!=null);
if(context.pos+offset+count>=context.text.length){
return null;
}else{
return context.text.substring(context.pos+offset,context.pos+offset+count);
}
}
}

如果只拿着望远镜瞄一眼,吃豆人觉的不够,还需要亲自去走一圈才好。但是走完还是要回来的。于是,它造了一个回城卷轴:

let totalOffset = 0;
let offset = 0; let store = {
pos: context.pos,
lineNo: context.lineNo,
column: context.column,
end: context.end
} function push(){
offset = 0;
store.pos = context.pos;
store.lineNo = context.lineNo;
store.column = context.column;
store.end = context.end;
}; function pop(addOffset){
offset = context.pos - store.pos;
if(addOffset){
totalOffset += offset;
} context.pos = store.pos;
context.lineNo = store.lineNo;
context.column = store.column;
context.end = store.end;
return offset;
}

有了望远镜+回城卷轴,吃豆人终于可以开心的吃require表达式了:

function lookupRequire(info){
// 设定回城点
push(); // 取出一个字符,判断是否是前缀
let c = nextChar();
if(['=','?',':','(',',',';'].indexOf(c)>=0){ // 走一步
stepChar(); // 跳过连续的空格
skipSpaces(); // 跳过连续的注释/空格
skipComments();
} // 回城!
pop(true); // 跳过前面的内容,取出7个字符,看是否是require
if(nextCharOffset(totalOffset,7)==='require'){
totalOffset += 7;// add for 'require' // 埋点
push(); // 跳过连续的空格+连续的注释/空格
skipSpaces();
skipComments(); // 回城
pop(true); // 下一个应该是左括号了
if(nextCharOffset(totalOffset, 1)==='('){
totalOffset += 1; // add for '(' // 接下来校验左括号和右括号之间是否是一个精确的静态字符串
let valid = false; // 埋点,留下起点
push(); // 直接跳过前面lookup的部分
stepChar(totalOffset); // 跳过连续的空格+连续的注释/空格
skipSpaces();
skipComments(); // 精确匹配一个静态字符串,动态require忽略,例如require(item)
skipString(); // 跳过连续的空格+连续的注释/空格
skipSpaces();
skipComments(); // 下一个应该精确的是右括号
if(nextChar(1)===')'){
valid = true;
} // 回城,回到起点, do not increase totalOffset
pop(); // 如果有效,则lookup成功
if(valid){
// recored info.offset, so that we can
// directly skip to '(' when eating require.
info.offset = totalOffset;
return true;
}else{
return false;
}
}else{
// 失败
return false;
}
}else{
// 失败
return false;
}
}

在lookupRequire里面,我们使用info来记录实际上跳过的那些offset,便于复用。剩下的就是eat方法,有了前面的基础,现在就简单了:

function eatRequire(info){
stepChar(info.offset);
skipSpaces();
skipComments(); tokenStart();
ret = skipString();
let r = tokenEnd(ret);
if(r!=null){
context.requires.push(r); // 保存起来require里的字符串位置信息,这是我们的目的
} skipSpaces();
skipComments(); ret = skipChar(')');
console.assert(ret); return true;
}

好了,已经够长了。回顾一下,现在回到我们的核心目标,实现:

  • 吃豆人向前看一下,下面的豆子是什么品种?
  • 吃豆人知道了下一个品种的豆子吃掉。

首先,步进,向前看:

stepAndLookup = ()=>{
let info = {
offset: context.pos
}; if(context.text.length===0){
context.end = true;
} while(true){
if(context.end){
return {
type: 'end',
info: info
};
} if(lookupSpace(info)){
return {
type:'space',
info:info
};
} if(lookupComment(info)){
return {
type:'comment',
info:info
};
} if(lookupString(info)){
return {
type:'string',
info:info
};
} if(lookupRequire(info)){
return {
type:'require',
info:info
};
} // step
stepChar(); info.offset = context.pos;
}
}

其次,分类,吃豆子:

function eat(){
let r = stepAndLookup();
let ret = false;
switch (r.type) {
case 'space':
ret = eatSpaces(r.info);
break;
case 'comment':
ret = eatComments(r.info);
break;
case 'string':
ret = eatStrings(r.info);
break;
case 'require':
ret = eatRequire(r.info);
break;
default:
break;
}
return ret;
}

Now, repeat:

function parse(){
while(eat()){
//ignore
}
}

一旦完成解析,就可以做很多事情了,例如打印和替换:

dump:

function dump(){
console.log('');
console.log('requires:');
console.log('==============');
for(let t of context.requires){
console.log(
`source:`,context.text.substring(t.begin,t.end),
`, line:${t.lineNo}, column:${t.column}`,
t);
}
}

translate:

function translate(replace){
if(context.requires.length===0){
context.output = context.text;
return;
} let lastEnd = 0;
let outputs = []; for(let t of context.requires){
outputs.push(context.text.substring(lastEnd,t.begin));
outputs.push('`'+replace(context.text.substring(t.begin+1,t.end-1))+'`');
lastEnd = t.end;
} if(lastEnd<context.text.length){
outputs.push(context.text.substring(lastEnd,context.text.length));
} context.output = outputs.join('');
return;
}

没有豆子啦!!!

-- end --