| 如何实现git | 您所在的位置：网站首页 › bigo怎样 › 如何实现git |
如何实现git
|
本文首发于：https://github.com/bigo-frontend/blog/ 欢迎关注、转载。 需求背景DMS DaemonSet（bigo k8s系统）发布，会在每个节点部署一个pod，影响面比较大。业务期望在发布的时候，可以展示当前修改的配置，与线上的配置的yaml文件diff，效果如下： jsdiff + diff2html jsdiff获取文本差异。 diff2html将差异转化为html。diff2html提供了2种方式展示diff效果： parse+html 问题：highlight语法高亮不生效。 diff2html-ui: 支持json、代码高亮。 支持文件目录概要显示/隐藏。 支持收起已查看文件（side-by-side 模式下，viewed功能失效）。 diff2html格式化类型：side-by-side、line-by-line。 实现效果本文样例均使用diff2html-ui展示，功能点： 支持语法高亮。 支持显示/隐藏差异概要。 支持文件锚点跳转。 支持文件差异数量展示。 支持文件折叠（必须是line-by-line模式下才能正常使用）。 代码 多文件 支持普通文本、json、yaml的diff。 支持多文件列表展示。 支持parse+html以及diff2html-ui 2种diff展示方式。 // diffDataList 对比文件列表数据 [ {...diffDataItem} ] // diffDataItem : // { // prevData: any(string、json), // 旧数据 // newData: any(string、json), // 新数据 // isYaml?: boolean, // 是否yaml文件 // isJson?: boolean, // 是否json // fileName?: string, // 文件名 // oldHeader?: string, // 重命名，旧文件名 // newHeader?: string // 重命名，新文件名 // }, // outputFormat diff格式，line-by-line || side-by-side // isUseUi 是否使用Diff2HtmlUI // id Diff2HtmlUI 挂载html的id，多实例的情况下，各个实例需要唯一id，防止页面冲突 // fileListToggle Diff2HtmlUI 文件目录概要是否要隐藏，true显示，false隐藏 import React, { useEffect, useState } from "react"; import { createPatch } from "diff"; import { html, parse } from "diff2html"; import { Diff2HtmlUI } from "diff2html/lib/ui/js/diff2html-ui"; import yaml from 'js-yaml'; import "highlight.js/styles/googlecode.css"; import "diff2html/bundles/css/diff2html.min.css"; const DiffComponent = ({ diffDataList, outputFormat, isUseUi, id, fileListToggle }) => { const [ diffData, setDiffData ] = useState(""); useEffect(() => { createDiffData(diffDataList); }, [ diffDataList ]) const createDiffData = (fileList) => { let diffJsonList = []; fileList.forEach(item => { let { fileName, oldHeader, newHeader, prevData, newData, isJson, isYaml } = item; let oldString = prevData || ""; let newString = newData || ""; // 特定需求处理 if(isYaml){ // 将json转化为yaml格式 oldString = yaml.dump(prevData); newString = yaml.dump(newData); }else if(isJson){ // 格式化json oldString = JSON.stringify(prevData, null, 2); newString = JSON.stringify(newData, null, 2); } let args = [ fileName || "", oldString, newString, oldHeader || "", newHeader || "", { context: 99999 } ]; // 对比差异 const diffStr = createPatch(...args); // 差异json化 const diffJson = parse(diffStr); diffJsonList.push(diffJson[0]); }) if(isUseUi){ // 使用diff2html-ui const targetElement = document.getElementById(id); const configuration = { drawFileList: true, matching: "lines", highlight: true, outputFormat, }; const diff2htmlUi = new Diff2HtmlUI(targetElement, diffJsonList, configuration); diff2htmlUi.draw(); //绘制页面 diff2htmlUi.highlightCode(); // 高亮数据 diff2htmlUi.fileListToggle(fileListToggle); // 是否折叠概要 }else{ // 使用html方法 const diffHtml = html(diffJsonList, { drawFileList: true, matching: "lines", showFiles: true, outputFormat }); setDiffData(diffHtml); } } return ( isUseUi ? {__html: diffData}} /> ) } export default DiffComponent 组件使用 // parse+html outputFormat} /> // 使用diff2html-ui "diff-ui-mult"} fileListToggle={true} diffDataList={fileDiffList} outputFormat={outputFormat} /> jsdiff原理 抽象寻找 diff 的过程可以被抽象为图搜索。 以两个字符串，src=ABCABBA，dst=CBABAC 为例，根据这两个字符串我们可以构造下面一张图，横轴是 src 内容，纵轴是 dst 内容。 那么，图中每一条从左上角到右下角的路径，都表示一个 diff。向右表示“删除”，向下表示”新增“，对角线则表示“原内容保持不动“。
根据图中形成的线路，我们可以选择一条路径看看它的效果。
现在，“寻找 diff” 这件事，被抽象成了“寻找图的路径”了。那么，“最短的直观的” diff 对应的路径有什么特点呢？ 路径长度最短（对角线不算长度） 先向右，再向下（先删除，后新增） Myers 算法Myers 算法就是一个能在大部分情况产生”最短的直观的“ diff 的一个算法，算法原理如下。 首先，定义参数 d 和 k，d 代表路径的长度，k 代表当前坐标 x - y 的值。定义一个”最优坐标“的概念，最优坐标表示 d 和 k 值固定的情况下，x 值最大的坐标。x 大，表示向右走的多，表示优先删除。 还是用上面那张图为例。我们从坐标 (0, 0) 开始，此时，d=0，k=0，然后逐步增加 d，计算每个 k 值下对应的最优坐标。 因为每一步要么向右（x + 1），要么向下（y + 1），对角线不影响路径长度，所以，当 d=1 时，k 只可能有两个取值，要么是 1，要么是 -1。 当 d=1，k=1 时，最优坐标是 (1, 0)。 当 d=1，k=-1 时，最优坐标是 (0, 1)。 因为 d=1 时，k 要么是 1，要么是 -1，当 d=2 时，表示在 d=1 的基础上再走一步，k 只有三个可能的取值，分别是 -2，0，2。 当 d=2，k=-2 时，最优坐标是 (2, 4)。 当 d=2，k=0 时，最优坐标是 (2, 2)。 当 d=2，k=2 时，最优坐标是 (3, 1)。 以此类推，直到我们找到一个 d 和 k 值，达到最终的目标坐标 (7, 6)。 下图横轴代表 d，纵轴代表 k，中间是最优坐标，从这张图可以清晰的看出，当 d=5，k=1 时，我们到达了目标坐标 (7, 6)，因此，”最短的直观的“路径就是 (0, 0) -> (1, 0) -> (3, 1) -> (5, 4) -> (7, 5) -> (7, 6)。
Myers 算法是一个典型的”动态规划“算法，也就是说，父问题的求解归结为子问题的求解。要知道 d=5 时所有 k 对应的最优坐标，必须先要知道 d=4 时所有 k 对应的最优坐标，要知道 d=4 时的答案，必须先求解 d=3，以此类推。 Myers 算法基本流程迭代 d，d 的取值范围为 0 到 n+m，其中 n 和 m 分别代表源文本和目标文本的长度（这里我们选择以行为单位） 每个 d 内部，迭代 k，k 的取值范围为 -d 到 d，以 2 为步长，也就是 -d，-d + 2，-d + 2 + 2… 使用一个字典 v，以 k 值为索引，存储最优坐标的 x 值 将每个 d 对应的 v 字典存储起来，后面回溯的时候需要用 当我们找到一个 d 和 k，到达目标坐标 (n, m) 时就跳出循环 使用上面存储的 v 字典（每个 d 对应一个这样的字典），从终点反向得出路径 总结目前该功能DMS已经上线，BRPC服务管理平台配置下发需求也即将引入。这个功能其实相对比较容易，就是jsdiff+diff2html的组合，但是在找资料的时候，发现diff2html更新速度较快，目前网上的教程基本都是用的废弃的api；另外就是公司各种内部系统比较多，配置文件diff需求也比较常见，基于这两个原因写个总结，大家可以相互借鉴学习。 如有错误，欢迎指正。 相关资料jsdiff diff2html Myers论文 Git 是怎样生成 diff 的：Myers 算法 欢迎大家留言讨论，祝工作顺利、生活愉快！ 我是bigo前端，下期见。 |
【本文地址】