❤
npm
Sign UpSign In

grunt-incrediff

3.3.33 • Public • Published

grunt-incrediff

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

使用文档

注意

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

安装

通过 npm 安装：

$ npm install grunt-incrediff -g

配置使用

GruntFiles.js 
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存储路径, 会从此地址下拉取 旧版本 资源文件

构建步骤

  1. 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']
 	            }
 	        },
 	    }
 });

  2. 如果将 version: ["1.0.1","1.0.0"]变量单独放在其他文件中，请主动修改

  3. 本地执行 grunt incrediff / 服务端自动 grunt 时会生成到指定目录

  4. 增加差异输出强校验，会对差异进行一次合并测试，如果合并测试失败则grunt会fail(如果算法某些点没测试到可能报错)

差异数据文件格式

  1. 默认文件命名 format: '%{FILEPATH}_%{OLDVERSION}_%{NEWVERSION}.js',即生成 path/to/file.ext_1.0.0_1.0.1.js 文件
  2. 文件中的内容
    • 差异数据 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的转义序列中出现, 不会出现本地误识别的情况
    • 文件中最终内容示例

单独调用

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 进行数据优化合并

Readme

Keywords

none

Package Sidebar

Install

npm i grunt-incrediff

Repository

github.com/SenYu/grunt-incrediff

Homepage

github.com/SenYu/grunt-incrediff

Weekly Downloads

2

Version

3.3.33

License

MIT

Last publish

Collaborators

  • senyu
  • chesihui
Try on RunKit
Report malware