grunt-incrediff

v3.3.33

Published

2 years ago

auto-generate tool of difference between two version

Downloads

0High
0Medium
0Low

senyu

chesihui

grunt-incrediff

grunt构建时自动生成文件间增量更新差异数据

使用文档

注意

仅支持 alibaba gitlab 构建时 grunt，其他环境路径不同不保证需求(可能因为CDN路径不同需要修改options)
模块加入 chunk / chunkLcs 两种差异生成算法，各有使用场景，为了避免算法的不完备性导致差异生成错误，加入强校验，若生成的差异合并失败会使grunt过程fail。

安装

通过 npm 安装：

$ npm install grunt-incrediff -g

配置使用

version: [],   
指定要生成差异文件的原始文件的版本号,如["1.0.2","1.0.1","1.0.0"]，

chunkSize: 20,   
newChunk算法调用时使用的参数，分块大小，建议>=10

isSingleDiff: true,    
若 `isSingleDiff` 为 true ，则
生成 v[1]旧版 和 v[0]新版 的差异文件，否则生成 v[1-end] 和 v[0]新版 的所有差异文件

isHashStr: true,
生成差异信息中，是否压缩重复字符串

sourceFormat:  '%{CDNURL}/%{OLDVERSION}/%{FILEPATH}',   
CDN上原始文件的获取地址，此处的oldversion 
  当`isSingleDiff===FALSE`时会匹配 version[>=1]的所有元素，
  当`isSingleDiff===TRUE`时会匹配 version[1]的元素

format: '%{FILEPATH}\_%{OLDVERSION}\_%{NEWVERSION}.js'    
需要生成在build目录的差异文件的路径

dest: 'build'    
差异文件生成目录

algorithm: 'chunk'    
枚举类型 `chunk` / `chunklcs`/`auto`，两种差分算法
  `chunk`: 时间复杂度低,当差异巨大,(如两个完全不同的文件时),此算法速度较快,但差异文件较大
  `chunklcs`: 时间复杂度略高,当差异巨大时,速度较慢,300K的文件间比较能跑5s左右,但在差异小时数据量很小,大约是 `chunk` 算法的 80% 左右
  `auto`: 自动选择两者之间 数据量小的那个

newsrc: 'build'    
新版本文件在之前的grunt构建中的生成目录

cdnUrl: 'http://g.assets.daily.taobao.net/dd/h5/'
CDN存储路径, 会从此地址下拉取 旧版本 资源文件

构建步骤

grunt 配置

 grunt.initConfig({
 		incrediff: {
 			incre: {
 				options: {
 					version: ["1.0.1","1.0.0"],
 					chunkSize: 20, 
 	                isSingleDiff: true,
 	                dest: 'build',
 	                sourceFormat: '%{CDNURL}/%{OLDVERSION}/%{FILEPATH}',
 	                format: '%{FILEPATH}_%{OLDVERSION}_%{NEWVERSION}.js',
 	                newsrc: 'build',
 	                algorithm: 'auto',
 					cdnUrl: 'http://cdnurl/pathprefix/',
 	            },
 	        files: {
 	            src: ['path/to/css.css', 'path/to/js.js']
 	            }
 	        },
 	    }
 });

如果将 version: ["1.0.1","1.0.0"]变量单独放在其他文件中，请主动修改
本地执行 grunt incrediff / 服务端自动 grunt 时会生成到指定目录
增加差异输出强校验，会对差异进行一次合并测试，如果合并测试失败则grunt会fail(如果算法某些点没测试到可能报错)

差异数据文件格式

默认文件命名 format: '%{FILEPATH}_%{OLDVERSION}_%{NEWVERSION}.js',即生成 path/to/file.ext_1.0.0_1.0.1.js 文件
文件中的内容
- 差异数据 var data = {hash: (Array), diff: (Array), chunkSize: (Number)};
  - 示例
    - originStr = '1234567u'
    - targetStr = '12abc567u'
    - {hash: ['abc'], diff: [ [0,1], [0], [2,2] ], chunkSize: 2}
  - data.hash 表示可以把 data.diff 中的重复字符串存到 data.hash 数组中节省空间(可选)
  - data.diff 表示有3种结构，按以下解释，依次连接起来即能生成 targetStr
    - [x, y] : 表示 originStr.substr( x * data.chunkSize, y * data.chunkSize );
    - [i] : 表示 data.hash[i]
    - 'string' : 表示字符串
  - data.chunkSize 表示分块大小，chunk算法默认为20 / chunklcs算法默认为1
- 对差异数据进行以下操作
  - var write = JSON.stringify( data ) + '/*"""*/';
  - fs.writeSync(pathto, write, 'utf8');
  - 执行此操作的原因：
    - 为了考虑到把文件放在CDN上，让多个文件能被combo下载后在客户端能正常分割开
    - 需要对每个差异文件标记分隔符 /*"""*/ (考虑css和js会被一次combo起来)
    - 由于JSON.stringify处理后形如",\等字符会被转义处理, 因此分隔符 **/*"""*/**在理论上并不会在 data的转义序列中出现, 不会出现本地误识别的情况
- 文件中最终内容示例
  - URL: http://g.assets.daily.taobao.net/dd/h5/1.3.772/js/app/app_all.js_1.3.771_1.3.772.js
  - {"hash":[],"diff":[[0,115765],[115796,673],";console.log(\"进入1.3.772 静态渲染方法\");var ",[116470,105278]],"chunkSize":1}/*"""*/

单独调用

1. chunk 算法

var diff = require('./tasks/lib/newChunk'); var oldS = '1234567890'; var newS = '12345678toString90';
生成差异
var d = diff(oldS, newS, 2, true /是否不压缩字符串/);
合并差异
var m = diff.merge(oldS, null /若d不带chunkSize可以外部输入/, d)

2. chunkLcs 算法

var diff = require('./tasks/lib/chunkLCS'); var oldS = '1234567890'; var newS = '12345678toString90';
生成差异
var d = diff(oldS, newS);
合并差异
var m = diff.merge(oldS, null, d);

代码文档

其实啊...直接去看代码最好...算法都写在那里...
以下内容为代码实现逻辑，当发现bug/需要修改代码逻辑的时候可以参考一下

目录说明

/tasks
- /incrediff.js grunt插件代码
- /libs
  - newChunk.js chunk 差分算法实现
  - newLcs.js lcs 算法实现,复杂度太高不提供外部调用
  - chunkLCS.js chunkLcs 两种算法结合,具体实现

incrediff DOC

依赖项

/* http请求，下载历史版本文件 */
request = require('request')
async = require('async')

/* 显示差异文件大小 */
maxmin = require('maxmin')
chalk = require('chalk')

/* 差异算法库 */
diff = require('./lib/newChunk')

调用方法

responseHandler

http响应的回调，为了获取dest, done, container, _name, url, cnt, all，而产生的闭包

入参
- {object} done async异步回调对象
- {object} container 统一存储下载下来的字符串
- {string} _name 存储的名称
- {string} url 下载路径，显示用
- {string} cnt 下载顺序，显示用
- {string} all 下载总数，显示用
返回
- {Function} 返回闭包函数,用于request回调执行

strFormat

字符串处理格式化，按照指定的 %{XXX} 进行替换

入参
- {string} source 源格式串
- {object} kvd 替换数据
返回
- {string} 结果字串

generateDiffData

根据输入新旧数据源计算差异，并存储到指定位置，如果algorithm === 'auto' 则会调用两个方法分别运算选取数据量小的那个

入参
- {string} newdata 新数据源
- {string} olddata旧数据源
- {string} oldver 旧版本号
- {string} path 存储路径
返回
- 无

generateFullData

根据输入数据源生成全量数据，并存储到指定位置，(考虑到所有文件,包括CSS和JS能被combo在一起,必须要做一定处理,让本地接收时能够分离成单个文件)

入参
- {string} 数据内容
- {string} path 存储路径
返回
- 无

执行逻辑

初始化 options
详见 配置使用
- 路径修正(添加'/'或去除'/')
- 版本修正(添加最后一个''元素)
- 根据配置选择差分算法('chunk'/'chunkLcs')
读取本地最新资源文件(由之前的grunt生成的),存入newContent数组
根据 sourceFormat 的格式生成需要下载的旧版本资源文件URL,存入reqQueue数组
调用async.each(reqQueue, ***) 对所有指定旧版本资源进行下载,把下载后文本存入reqContent
async.each 全部执行done之后,开始生成差异
- 调用 generateDiffData 生成版本间差异数据
- 调用 generateFullData 生成全量更新数据

lib/newChunk DOC

调用方法

generateOriginBlock

由o原始字符串按照chunkSize分块大小生成对应块的hashmap，用来标记块是否存在

入参
- {string} o 原始字符串
- {number} chunkSize 分块大小
- {object} originHash hashmap记录
返回
- 无

generateOriginBlock

对n按照rsync的思想进行滑动块查询，如果在originHash中查询到了就是未被修改，没查询到就当做新增一个字节然后继续，把生成的差异数据存入diffRecord
可以参照 rsync算法描述

入参
- {object} originHash hashmap记录
- {string} n 目标新字符串
- {number} chunkSize 分块大小
- {object} diffRecord 差异数据
返回
- 无

getCorrectHashID

寻找最优分块hashID,由于复杂度原因，不可能做到绝对最优，采用这个O(N)的遍历来寻找一个相对最优的，找一个距离上次正确匹配最相近的匹配块

入参
- {string} curStr 需要查找的块
- {number} priorHashID 最近一次成功匹配
返回
- {number} 返回最优匹配块号

concatDiffBlock

把相邻的数组标记块或者相邻的字符连接起来，节省空间

入参
- {object} diff 差异数组，[[0,1],[1,1],'2','3']
- {object} seq 连接之后存储在这里,会被处理成 [[0,2], '23']
- {boolean} noIndex TRUE时不适用hash存储字符串，FALSE时使用
返回
- 无

执行逻辑

generateOriginBlock 计算源数据分块哈希映射
generateDiffBlock 根据源哈希映射和新数据计算差异
- getCorrectHashID 计算寻找较优匹配
concatDiffBlock 把差异中满足一定条件的相邻块合并

lib/newLcs DOC

调用方法

lcsDiff

时间、空间复杂度均为O(N^2)，在 dp 中存储编辑距离，在 step 中存储具体路径，然后进行一些处理把差异规则化

入参
- {string} o 源字符串
- {string} n 新字符串
返回
- {object} 差异数据对象

buildPaths

由于路径是逆序记录在二维数组中的，需要重新遍历路径才能得到一维的编辑路径

入参
- {number} i 数组一维大小，源字符串长度
- {number} j 数组二维大小，新字符串长度
- {string} o 源字符串
- {string} n 新字符串
- {object} step 路径二维数组
返回
- {array} infoQueue 路径一维数据，MOD/EQUAL/DEL/ADD

buildDiff

处理之前构造的一维路径数组,把MOD/EUQALL/DEL/ADD,转换成和newChunk一样的形式

入参
- {array} infoPaths 构造的一维路径数组
返回
- {array} diffQueue 基本差异数组,还没有优化过

concatDiff

把生成的差异数组中符合一定条件的相邻项进行合并,同newChunk中的concatDiffBlock,合并相邻数组或相邻字符

入参
- {array} diffQueue 基本差异数组,还没有优化过
返回
- {array} sequence 优化完成的数组

执行逻辑

lcsDiff 先跑动态规划,把编辑距离路径记录的二维数组跑出来
- buildPaths 根据二维路径生成一维最短编辑路径,二维包好了所有编辑路径,不论好坏,生成的一维是最优解
- buildDiff 把之前的一维路径的结果(MOD/EUQALL/DEL/ADD)处理成仅由源字符串o.substr 和新字符串拼接就能构成的[[0,2], '23']如此的数组形式
- concatDiff 优化,拼接差异数组中满足某些特定条件的相邻项(数组相邻或都是字符串)

lib/chunkLcs DOC

调用方法

algoWrap

对外调用做的一个包裹函数,添加了 diff, chunkSize 等通用属性(后来做了点数组优化,增加一个合并小块的过程)

入参
- {string} o 源字符串
- {string} n 新字符串
返回
- {object} 差异数据对象

ChunkLCS

递归调用的主函数,进入后,先试用chunk算法分出最(较大,非绝对最大)大公共字串,及其前缀和后缀,然后对其前缀和后缀字符串递归调用该函数

入参
- {number} lcsLimit 执行lcs算法的阀值
- {number} preStart 递归调用时指明后缀的开始位置
- {object} arguments[2] 分情况，1个的话是 chunkSplit生成的对象，2个的话是2个一旧一新的字符串
返回
- {object} 指定块的差异数据对象

chunkSplit

对指定的源数据块o，和新数据块n，执行最(较)大公共块计算,并返回含有前缀,公共,后缀信息的对象

入参
- {string} o 源数据'块'
- {string} n 新数据'块'
- {number} preStart 递归调用时指明后缀的开始位置
返回
- {object} splitInfo 分隔之后的信息

lcsAdapter

lcs算法适配器，需要适配 preStart的预制数，必须加上，否则会错乱

入参
- {string} o 源数据'块'
- {string} n 新数据'块'
- {number} preStart 递归调用时指明后缀的开始位置
返回
- {object} lcsDiff 经过preStart修正的差异数据

mergeBlock

由于chunkSplit进行了前中后的拆分，这是重新组装的函数，并且要考虑两个差分数组拼接时连接处是否可以合并的问题

入参
- {object} source 被组装的前面部分
- {object} addition 被组装的后面部分
返回
- {object} source 组装好的结果

miniLcsBlock

后期发现的一个问题, 本算法能精确到字节级别,那么即chunkSize分块大小===1,所以后期会出现好多[123123,1],这代表了源字符串的一个字符，却要占用10个左右的字节进行表示，对这种情况，直接插入字符，节省差异数据

入参
- {object} diff 差异对象
- {string} o 源字符串，从中取需要的
返回
- {object} newDiff 新差异对象，优化之后的

执行逻辑

algoWrap 计算差异
- 最初调用 ChunkLCS ,初始化参数 ChunkLCS( 100, 0, o, n )
  - 若满足 lcsLimit 条件,调用 lcsAdapter 计算差异并返回
  - 若不满足
    - 调用 chunkSplit 寻找最(较)大公共字符串, 并对其前缀和后缀分别递归调用 ChunkLCS 计算差异
    - 对计算完成的前缀和后缀调用 mergeBlock 合并差异
- 得到完整差异后, 调用 miniLcsBlock 进行数据优化合并

Published

Vulnerabilities

Links

Maintainers

Keywords

Readme

grunt-incrediff

使用文档

注意

安装

配置使用

构建步骤

差异数据文件格式

单独调用

1. chunk 算法

2. chunkLcs 算法

代码文档

目录说明

incrediff DOC

依赖项

调用方法

执行逻辑

lib/newChunk DOC

调用方法

执行逻辑

lib/newLcs DOC

调用方法

执行逻辑

lib/chunkLcs DOC

调用方法

执行逻辑