关于javascript:PEG实现-git-diff-数据解析器

我的项目中想应用 git diff 的文件变更比对性能，但 git diff 返回的格局是纯文本且未解析的。网上找了相干的库，像是 parse-git-patch，应用的是git format-patch 命令生成的补丁文件，无奈间接接管命令行中返回的文本格式，找了几个都是这样，所以罗唆就本人入手实现一个。

一般解决常见文本个别都是用正则，但这里是大段的文本，用正则即便写进去也很难以保护。网上有篇文章就是讲述 JavaScript 实现的逻辑，但用 JavaScript 解决字符串又比拟繁琐。这里选用语法分析生成器来实现。

网上的文章常常能看到 形象语法树（AST）这个词，将人类编写的文本转换成计算机可初步读懂的数据结构称之为 AST，而在 AST 之前须要先对文本做 词法剖析 和语法分析 ，像是素日天天用的Babel 里的词法和语法分析器就是Babylon。

语法分析器比拟繁琐且干燥，所以又呈现语法分析器的生成器。所有能用 JavaScripts 写的终将用 JavaScript 写，前端天然也有相应可用的库，比拟闻名的有 PEGjs 与Jison两个库。有了生成器咱们能做什么呢？小到代替正则，大到实现本人的 畛域特定语言（DSL）。像是曾一度最有心愿代替 JavaScript 的CoffeeScript，他的 V2 版本就是用 Jison 库做本人的语法分析器。

PEGjs语法规定很容易上手，这里应用 PEGjs 来实现解析器。（PEGjs曾经没有维护者了，在应用的过程中意外发现有人另外建了一个分支版本在保护PEGgy，能够无缝过渡）

PEGGY

peggy能够在浏览器中应用，也能够引入我的项目中应用。又或是编写好规定，应用命令生成解析器提供应用。

简略的规定能够间接应用在线版的调试 https://peggyjs.org/online.html。

装置

npm install peggy

网页应用的话能够间接引入 peggy.min.js。

应用

const PEG = require("peggy");
// 导入规定 生成解析器
const parser = PEG.generate(RULE, {trace: true,});
// 应用解析器
const result = parser.parse(TEST_DATA, {tracer: true,});

generate函数和 parse 函数都能够传入参数。

generate函数参数，网上有向南已翻译了我这里就摘录过去

• allowedStartRules: 指定 parser 开始的 rule. (默认是文法中第一个 rule.)
• cache: 如果设置为true, parser 会将 parse 的后果缓存起来, 能够防止在极其状况下过长的解析工夫, 但同时它带来的副作用是会使得 parser 变慢(默认 false).
• dependencies: 设置 parser 的依赖, 其值是一个对象, 其 key 为拜访依赖的变量, 而 value 为须要加载的依赖 module id. 只有当 format 参数被设置为"amd", "commonjs", "umd" 该参数才失效. (默认为{})
• exportVar: Name of a global variable into which the parser object is assigned to when no module loader is detected; valid only when format is set to “globals” or “umd” (default: null).
• format: 生成的 parser 格局, 可选值为 ("amd", "bare", "commonjs", "globals", or "umd"). 只有output 设置为source, 该参数才失效
• optimize: 为生成的 parser 抉择一个优化计划, 可选值为 "speed" 或者"size". (默认"speed")
• output: 设置 generate() 办法返回格局. 如果值为"parser", 则返回生成的 parser 对象. 如果设置为"source", 则返回 parser source 字符串
• plugins: 要应用的插件
• trace: 追踪 parser 的执行过程(默认是 false).

parse函数参数

• startRule：起始解析的 rule 名称
• tracer：展现 parser 执行 rule 的过程
• ...(任意其余参数)：应用 options 变量接管参数，能够在 parse 函数中传入自定义参数，能够给解析规定提供一些配置性能

规定

规定很简略，会举一个例子说说，形容的会比拟繁琐，疾速了解能够间接看官网文档，一共没几条规定。

整体样子大略是这样：

在 VSCode 里能够装置 Peggy Language 插件，能提供语法高亮、跳转、谬误提醒等性能。

{{function prefix(str){return `Interger:${str.join("")}`
    }
}}

/* 开始 */
start = integer _ content

content
    = "(" integer ")"
    / "[" "TEXT:"i [a-zA-Z+-]* "]"
    / "{" .* "}"
    
integer "整数"
    = digits:[0-9]+ {return prefix(digits); }

// 匹配空格
_ = SPACE+ {return ""}
SPACE = "" /"\t"

能够应用在线版，输出 123456 (00) 或是 123456 [text:Yes] 相似格局须要解析的字符串，能够看到匹配出的数据。

这个简短的规定把罕用的规定都列举进去了，来解释一下。

{{function prefix(str){return `Interger:${str.join("")}`
    }
}}

{{}}初始化器

最顶部的花括号的区域称之为初始化器，用一个 {} 两个 {{}} 括号定义都能够，前后括号数匹配的起来就行。在这里能够自定义一些 JavaScript 代码。

能够通过 options 拿到传参做预处理，也能够定义一些工具函数供后续的规定应用。

接下来遇到第一个规定：

/* 开始 */
start = integer _ content

/**/与 // 正文

与其余编程语言一样反对 /**/ 与//的正文。

start规定名

start是规定名称，能够任意拟定，只须要合乎 JavaScript 起名标准即可。

integer _ content解析表达式

=等号前面是 解析的表达式，这里的表达式是integer _ content。

是不是看不懂这些代表什么意思？这就阐明其中的表达式很可能是另一个规定名，所以能够持续往下看：

content
    = "(" integer ")"
    / "[" "TEXT:"i [a-zA-Z+-]* "]"
    / "{" .* "}"

这里看到下面解析表达式中的其中一个规定content。

空白符

会发现这里定义格局不太一样，等号能够换到第二行去。

pegpy在解析规定时，词法剖析先会把文本宰割成一个个 token（像是=、"、/、字符串、正文等），不同于 JavaScript， 空白符 不作为token，所以在之间咱们能够任意换行或者插入空格。

/符号

/符号相似于 或的意思，代表了符号前后是两个规定，先匹配后面的规定，当不匹配时持续匹配前面的。能够有任意多个规定连贯，直到所有的规定匹配不胜利，抛出异样。

""引号

先来看第一个表达式"(" integer ")"，文本数据咱们用引号引起，所以前后是匹配两个括号。

两头的仍然不意识，阐明是另一个规定名。所以能够揣测这段是解析两个括号之间的某些字符，依据名称是匹配两个括号之间的数字。

再来看下一条：

"[" "TEXT:"i [a-zA-Z+-]* "]"，这里一样，但更简单一些，匹配方括号之间的值，但这里没有援用其余规定，而是写了明确的匹配信息。

“”i疏忽大小写

"TEXT:"i一样，引号两头是文本，所以匹配的是 TEXT:，前面的i 是做什么的？这跟正则一样，加 i 是疏忽字符串的大小写，所以也能够匹配 text 等模式。

[]从汇合中匹配

[a-zA-Z+-]*看的是不是很像正则？这里就跟正则一样，匹配 a 到z即所有的英文字母，A-Z是大写的英文字母，同时还有 +、- 两个符号。

*+匹配次数管制

[]方括号示意只会匹配其中所列的一个，所以在最初的 * 示意匹配次数，零次或屡次。

同样，还有 + 号，代表一次或屡次。

?匹配失败返回null

有时在其余解析表达式里还能看到 ? 符号，?不是像正则那样代表零次到一次，而是示意匹配胜利就返回后果，不胜利返回null。

同时也没有 {} 表白额定的反复次数性能，只有 *、+ 两个符号，绝对于正则性能没那么丰盛。

"[" "TEXT:"i [a-zA-Z+-]* "]"，所以这一段就是匹配方括号中以 TEXT: 结尾，前面的所有大小写字母及加减号字符。

第三条规定： "{" .* "}"。

.任意一个字符

按之前学到的，这是匹配花括号中的内容，*代表匹配次数，那 . 呢？.在这里代表匹配任意一个字符，包含空格之类的字符。所以这句实际上是匹配花括号中的所有内容。

到这里其实曾经把根底规定学完了，说的比拟啰嗦，实际上很简略，没几个规定，下面的连起来是这样的：

匹配圆括号中的合乎 integer 规定的信息，如果有不合乎的，则换到下一个规定，匹配方括号以 TEXT: 不分大小写结尾的内容，其中内容只能是大小写字母及加减号字符这些字符，如果有其余字符则匹配不胜利，跳到最初一个规定，匹配花括号中的所有字符。再不胜利，则弹出错误信息。

再往下看，就能看到始终被提及的 integer 规定：

integer "整数"
    = digits:[0-9]+ {return prefix(digits); }

规定别名

这里在规定前面等号后面又多了一个带引号字符串"整数"，这是规定的别名，调试时应用，也能够同后面其余规定一样省略掉。

digits:[0-9]+解析表达式标签

在解析表达式中能够看到除了后面已知的局部 [0-9]+，还多了 一个冒号的语法，这是给解析后果起一个名称，不便前面的action 调用。

{return prefix(digits); }解析表达式的 action

绝对于其余规定，这个规定咱们在开端定义了相似函数的货色，这就是 JavaScript 函数。咱们能够在解析表达式之后减少花括号，其中写 JavaScript 代码。像是这句，就是调用了咱们在初始化器中定义的函数，将获取到的文本处理一下再返回。

这个就是 peggy 自在的中央，当自身语法解析能力不够的时候，或者解析进去的文本比拟系统（字符串经常会被宰割成一个个存到数组中），这时候咱们就须要用到action。

这里联合起来 integer 规定是匹配一到多个数字字符，并且解决成间断的字符串（解决前匹配进去的数据是 [1,2,3,4,5] 这样的，为了不便浏览与应用，往往须要解决成 12345），并且加上Interger: 的前缀。

最初一段是解析空格的规定：

// 匹配空格
_ = SPACE+ {return ""}
SPACE = "" /"\t"

之前有提到，在 token 之间的空白符会疏忽，所以如果文本中有空格，也须要独自匹配。

用冒号即可""，如果须要匹配制表符之类的也能够间接写"\t"。

为了不影响解析表达式的浏览，命名为 _ 不便辨认。同时将匹配到的后果用一个 action 转换为空，不便后续将数据处理掉。

运行起来匹配文本返回的数据大略是这样，有需要的话能够再加 action 将数据处理成指定格局：

git diff 的数据格式

说了这么多，当初才能够开始进入到咱们要做的需要中。要解析 git diff 返回数据，天然先要晓得格局标准。

返回数据大略长这样：

diff --git a/package.json b/package.json
index cb2f4bc..35455a2 100644
--- a/package.json
+++ b/package.json
@@ -1,13 +1,14 @@
 {
   "name": "peg-git-diff-parser",
-  "version": "0.0.0",
+  "version": "1.0.0",
   "description": "git diff 文本解析器",
-  "main": "index.js",
+  "main": "src/index.js",
   "scripts": {
     "build": "peggy -o dist/gitDiffParser.js src/gitDiffParser.peggy",
     "test": "node src/index.js"
   },
   "author": "LnnCoCo",
+  "new": "new",
   "license": "ISC",
   "dependencies": {"peggy": "^1.2.0"

咱们一行一行来阐明。

diff --git a/package.json b/package.json

diff --git是固定字符，a 和 b 示意变动前与变动后的文件。

index cb2f4bc..35455a2 100644

..是分隔符，示意 index 区域 hash 为 cb2f4bc 的对象，与工作区 hash 为 35455a2 的对象。100644为对象的模式，100代表一般文件，644代表权限信息。

--- a/package.json
+++ b/package.json

比拟的文件名信息，---变动前，+++变动后。

@@ -1,13 +1,14 @@
 {
   "name": "peg-git-diff-parser",
-  "version": "0.0.0",
+  "version": "1.0.0",
   "description": "git diff 文本解析器",
-  "main": "index.js",
+  "main": "src/index.js",
   "scripts": {
     "build": "peggy -o dist/gitDiffParser.js src/gitDiffParser.peggy",
     "test": "node src/index.js"
   },
   "author": "LnnCoCo",
+  "new": "new",
   "license": "ISC",
   "dependencies": {"peggy": "^1.2.0"

从这里开始就是每个变动的信息块。以 @@...@@ 起头，有多个块就有多个@@...@@，这里目前只有一个。

-1,13 +1,14，-代表变动前、+代表变动后，1,13，代表从第一行开始展现之后的十三行。1,14同理，因为有一行是新增，所以变动后会多一行。

而后接下去的是文本，这里容易看见的是两个符号，实际上是有三个：+、-、空格 。这个对解析很重要，所有行都是以这三个起始。- 是变动前，+是变动后，空格 是未变更内容。

未变更内容展现逻辑是，以变动行为核心，展现高低最多三行内容。

这样整个 git diff 输入格局就清晰了。

在查资料的时候发现理论还有 新增 、 已删除 、 重命名 ，文件还有分二进制非二进制的状况，但在单纯的命令行git diff 状况下，这些是无奈输入数据的，所以而且以后需要也没用到，就疏忽了这些其余状况。

实现解析规定

新建一个我的项目，而后装置peggy。

新建一个 gitDiffParser.peggy 文件来编写规定，其余读取测试数据传入插件之类测试性代码能够本人补充。

残缺的我的项目地址：peg-git-diff-parser

在 VSCode 中能够装置 Peggy Language 插件，能提供高亮语法和谬误提醒之类的。

先定义一些公共的规定

/**
 * 公共定义
 */

// 门路文件名
filePath = hit:[A-Za-z0-9\\\/\._\-@$()*&^+!]+ {return hit.join("") }

// 换行
LINE_END = "\r\n" / "\n"

// 空白符
__ = SPACE* {return ""}
_ = SPACE+ {return ""}
SPACE = "" /"\t"

而后开始吧。

diff --git a/package.json b/package.json

这里变动的内容就只有文件名，所以其余局部都能够写死，大略是这样。

header = "diff --git" _ filePath _ filePath LINE_END

很简略吧，只须要把变动的局部规定匹配起来就行了。

这里为了下层不便辨认，所以减少了标签，包成了对象返回了。

/** 
 * 首行
 **/
header
  = "diff"i _ "--git"i _ 'a'beforePath:filePath _ 'b'afterPath:filePath LINE_END
  {
    return {
      beforePath,
      afterPath
    }
  }

接下来都差不多。间接来看看比拟麻烦的变动块的数据解析。

先解析头部

@@ -1,13 +1,14 @@

很容易，从 @@ 开始定位，到 @@ 完结。

changeHeader
  = "@@" _ beforeChangeLine:changeLineInfo _ afterChangeLine:changeLineInfo _ "@@" LINE_END
  {
    return {changeHeader: `@@ ${beforeChangeLine.text} ${afterChangeLine.text} @@`,
      beforeChangeLine,
      afterChangeLine
    }
  }
  
// 变动行信息  第 N 行开始, 一共 N 行  1,6 第一行开始, 一共 6 行（变动的 -+ 两行算一行）changeLineInfo
  = type:([-|+]) line:([0-9]+","[0-9]+)
  {const lineFormatText = formatLine(line);
    return {text: `${type}${lineFormatText}`,
      type,
      line: lineFormatText
    }
  }

因为行信息写在一起比拟麻烦，所以另外写了个 formatLine 函数解决。

而后就是麻烦的中央，之后的数据是不定长的。而且 +、-、 空格 符号在其余部分也会呈现，所以只能限定结尾的局部匹配到这三个别离进入三个不同的规定中。

但这里没有像是正则一样的结尾标识符，所以换个角度想，每一行的开始，在上一行必然有一个换行符，所以能够这样定义 LINE_END "-" 或LINE_END "+".

之后的内容须要全副匹配，间接 .* 必定是不行的，会将之后的所有信息一起匹配进去。好在文档中还写到有 [] 能够配合 ^ 符号用来反向匹配，比方 [^ABC] 就是匹配除了 A、B、C 的任意字符。

比拟遗憾的是无奈间接将规定配合 ^ 符号，不然能够写出较为简单的匹配逻辑。所以目前信息曾经能够解决了，变动块的数据必然是一行的，所以咱们只有辨认到 换行符 就进行匹配即可。

规定如下：

changeBeforeContent = LINE_END "-" hit:[^\r\n]+ {
  return {
    type: "-",
    text: hit.join("")
  }
}
changeAfterContent = LINE_END "+" hit:[^\r\n]+ {
  return {
    type: "+",
    text: hit.join("")
  }
}

但咱们变动数据是在两头，其前后还有上下文相干的背景数据，这些数据是以 空格 结尾的，或者是当结尾不是 +、- 符号的时候，就全作为上下文相干内容解决。所以规定很简略

changeContext = . {return null}

而后咱们将规定组合一下，这样四种状况就能包含所有文本了。

changeChunk
  = line:changeHeader
    / beforeContent:changeBeforeContent
    / afterContent:changeAfterContent
    / changeContext

但这样只能匹配一行内容，所以咱们还须要加上次数信息和将上下文内容返回的空数据过滤了。

changeChunk
  = hit:(
      line:changeHeader
      / beforeContent:changeBeforeContent
      / afterContent:changeAfterContent
      / changeContext
    )*
    {return hit.filter(item => item)
    }

再入口处将所须要的信息格式整顿一下，就能返回咱们预期的格式化后的 diff 数据了。

具体的细节能够到这里查看：peg-git-diff-parser

相干浏览

Peggy 官网

Peggy Github

PEG.js 文档 [译]

不懂编译也能造 JavaScript 解释器 第 0 章、前置常识

如何实现一个 Git Diff 解析器

读懂 diff