下一篇: 实现一个打包工具 2

变量diff算法


背景

以前在 管理系统 中开发过电话功能的需求, 电话相关接口使用的 第三方外呼服务。通常情况, 在 系统 中添加一个电话条, 拨打和挂断等操作用 ajax 请求 外呼服务 接口即可, 其实情况没那么简单

如何保证多标签中电话条状态同步?

总之, 只要是同一账号, 在任何地方登录电话条状态都应同步, 并且任何一个浏览器任何一个标签挂断或登出, 其他同系统同账号页面都应同步

外呼服务 提供 cmdevt 两个接口, evt 需要不断长轮询 Comet 以同步话机最新状态 (模拟服务器推送), cmd 则是浏览器发送操作请求, 流程如图所示

外呼服务 不记录浏览器打开标签数, 用户打开多个标签会同时轮询 evt 接口且只有一个 evt 接口的响应才会得到正确的状态更新消息, 可能带来的问题是: 当 标签1 请求挂断电话时, 可能 标签2evt 最先请求, 因此其响应得到已挂断消息, 而其他轮询接口得到的结果都是 null, 这直接导致其他标签状态还是通话中

不难理解, 外呼服务的消息队列是有限的, 当挂断消息已经被一个 evt 所消耗, 其他接口得到的结果必然是 null, 否则消息队列不能一直跟踪话机状态

从上可知, 浏览器直接请求 外呼服务 的方案不可行, 必须建立一个持久连接的 websocket 服务 (ws) 作为接入层, 通过 ws服务 来管理所有的标签, 同时 ws服务 还可以使用其他外呼服务并保证接口的一致性, 如图所示

当前账号的电话状态和其他数据需要 ws服务 和浏览器各标签之间同步, 为了便于管理将数据统一存到 state对象 中(对象名随意), 考虑到这个对象可能会非常大, 每次更新对象后发送整个 state 到各标签会导致带宽浪费, 因此需要实现一套 diff 算法, 将 state 修改前后的差异记录下来并同步到浏览器, 浏览器会将其应用到本地的 state, 从而实现浏览器和 ws服务 数据同步, 这样无需每次发送整个大对象, 只需发送差异数据这极小一部分

Diff 算法

假设有对象 ab 如下图所示 (它们也可以是任意类型):

var a = {
  name: 'tom',
  age: 20,
  info: {
    score: 80
  },
  label: ['singer', 'writer', 'painter']
}

var b = {
  name: 'tom',
  age: 20,
  info: {
    score: 99
  },
  label: ['singer', 'writer']
}

那么从 a 变为 b 的过程是:

var a = {
  name: 'tom',
  age: 20,
  info: {
    score: 80
    score: 99
  },
  label: ['singer', 'writer', 'painter']
  label: ['singer', 'writer']
}

用文字描述是这样的:

  1. a.info.score80 -> 99
  2. a.label[2] 删掉了

这些情况使用数组记录比较方便, 这里给数组命名为 patches, 现在要用代码来记录这些修改, 所以必须声明一种规范, 我制定的规范是这样的:

现在根据规范用代码来描述上面的文字:

var patches = [{
  p: ['a', 'info', 'score'],
  t: 3,
  v: 99
}, {
  p: ['a', 'label', 2],
  t: 2
}]

这里的 patches 数组描述了所有从 a 变为 b 的步骤, diff 算法会生成 patches, 此外, 还需要将其应用到对象 a, 并且保证全等于 b, 那么 api 可以这样设计:

var diff = require('diff');
var patches = diff.get(a, b);
var aa = diff.apply(a, patches);  // 将生成的 patches 应用到 a
console.log(JSON.stringify(aa), JSON.stringify(b));

// true

现在归纳总结出变量 ab 是不同类型时的操作:

a b 操作
等于 b 等于 a 跳过
NaN NaN 跳过
对象 对象 递归diff
数组 数组 数组diff
其他类型 其他类型 添加 {t: 3, v: b, ...}patches

从上面列出的这些情况可以大概写出 diff 模块的框架如下:

var diff = function () {
  var hasOwn = Object.prototype.hasOwnProperty;
  var toStr = Object.prototype.toString;
  var is = function (type) {
    return function (e) {
      return toStr.call(e) === '[object ' + type + ']';
    }
  }
  var isObj = is('Object');
  var isArr = is('Array');
  var CREATE = 1, DELETE = 2, UPDATE = 3, REPLACE = 4;
  var isnan = function (e) {
    return typeof e === 'number' && isNaN(e);
  }

  function get (a, b, key) {
    var patches = [];
    getDiff(a, b, []);
    return patches;

    function getDiff (a, b, p) {
      if (a === b || isnan(a) && isnan(b)) return;
      if (isObj(a) && isObj(b)) {
        // ...
      } else if (isArr(a) && isArr(b)) {
        // ...
      } else {
        patches.push({
          t: UPDATE,
          p: p,
          v: b
        });
      }
    }
  }

  return {
    get: get,
    apply: function () {
      // ...
    }
  }
}();

在 第 24 行中, 当 ab 都是对象的时候, 对他们进行 for in 循环, 情况如下:

因此第 24 行插入的代码如下:

var k;
for (k in a) {
  if (!hasOwn.call(a, k)) continue;
  if (hasOwn.call(b, k)) {
    getDiff(a[k], b[k], p.concat(k));
  } else {
    patches.push({
      t: DELETE,
      p: p.concat(k)
    });
  }
}
for (k in b) {
  if (!hasOwn.call(b, k)) continue;
  if (!hasOwn.call(a, k)) {
    patches.push({
      t: CREATE,
      p: p.concat(k),
      v: b[k]
    });
  }
}

在 第 26 行中当 ab 都是数组的时候, 情况要复杂很多, 这里添加一个 diffArr 的函数来比较, 基本情况如下:

a[n] 为对象时

例子:

var a = [{id: 1, name: 'tom', age: 20}, 1, 2];
var b = [2, 1, {id: 1, name: 'jack', age: 20}];

diff.get(a, b, 'id');

在比较过程中, 默认遍历到 a[0] 是对象时, 因为无法获取其内存地址所以不能直接高效地判断引用是否在 b 中存在, 所以默认会执行删除操作 {t: 2, p: [0]}, 遍历到 b 时, 又会执行添加操作 {t: 1, p: [2], v: {id: 1, name: 'jack', age: 20}}, 这样可能导致 patches 过大。仔细观察你会发现, 其实 a[0]b[2] 很相似, 只是其中的 name 字段做了修改, 所以只需要让 a[0] 的索引进行 0 -> 2 的交换操作, 再进一步 diff 即可, 如果 a[0] 体积非常大, 这样的优化其实效果非常明显

那么知道 a[0] 被移动到了 b 中的哪个位置呢? 从上面代码的第 4 行可以看出, 第2(基于0)个参数传入了 id, 这样 diff 算法会根据对象的 id 字段构建一个映射表, 可直接获取对象在 b 中的位置, 这是一个可选的参数, 如果不添加, 则会使用默认方式(先删除再添加)操作

a[n] 为基本类型时

当元素是基本类型时, 映射难度会更大, 因为基本类型的值可能重复出现多次, 如果 a[n] 是对象, 可直接判断 a[n].id 的唯一性来解决重复问题, 而基本类型, 例如 1 可能在 ab 中都出现若干次, 如何保证谁该映射到谁?

例子:

var a = [1, 2, 3, 1, 2, 2];
var b = [2, 3, 2, 1, 3, 1];

因此我不得不声明一种更为复杂的映射表解决这个问题:

var amap = {
  name: 'origin',
  key: {},
  num: {},
  str: {},
  true: [],
  false: [],
  null: [],
  undef: [],
}


var bmap = {
  name: 'target',
  key: {},
  num: {},
  str: {},
  true: [],
  false: [],
  null: [],
  undef: []
}

经过构建映射之后, amapbmap 结构应该是下图:

// amap
{
  name: 'origin',
  key: {},
  num: {
    1: [0, 3],
    2: [1, 4, 5],
    3: [2]
  },
  str: {},
  true: [],
  false: [],
  null: [],
  undef: [],
}

// bmap
{
  name: 'origin',
  key: {},
  num: {
    1: [3, 5],
    2: [0, 2],
    3: [1, 4]
  },
  str: {},
  true: [],
  false: [],
  null: [],
  undef: [],
}

因此基本类型的 diff 过程是检查 a[n] 是否在 b 中存在:

通过这些逻辑分析, 可以构建一个完整的 diff 算法, 细节这里不再赘述, diffArr 可参考以下代码的第 207-294 行

;(function (global, factory) {
  if (typeof module === 'object' && module.exports) {
    module.exports = factory();
  } else if (typeof define === 'function' && define.amd) {
    define(factory);
  } else {
    global.diff = factory();
  }
})(typeof window === 'object' ? window : this, function () {
  var hasOwn = Object.prototype.hasOwnProperty;
  var toStr = Object.prototype.toString;

  var is = function (type) {
    return function (e) {
      return toStr.call(e) === '[object ' + type + ']';
    }
  }

  var isObj = is('Object');
  var isArr = is('Array');

  var rtype = /\[object (\w+)\]/;
  var getType = function (e) {
    var arr = toStr.call(e).match(rtype);
    return (arr && arr[1] || '').toLowerCase();
  }

  function apply (data, patches) {
    if (!isArr(patches))
      throw new TypeError('patches must be an array');

    patches.forEach(function (e) {
      var t = e.t
        , p = e.p
        , v = e.v
        , i = e.i
        , d = data
        , pp

      if (!p.length) {
        if (t === 3) return data = v;
      }

      for (var j = 0, l = p.length - 1; j < l; j++) {
        pp = p[j];
        d = d[pp];
      }

      pp = p[p.length - 1];

      switch (t) {
        case 1:
        case 3: d[pp] = v;
          break;
        case 4: swap(d, pp, i);
          break;
        case 2:
          typeof pp === 'number'
            ? d.splice(pp, 1)
            : delete d[pp]
          break;
      }
    });
    return data;
  }

  function swap (arr, i, j) {
    var e = arr[i];
    arr[i] = arr[j];
    arr[j] = e;
  }

  var CREATE = 1;
  var DELETE = 2;
  var UPDATE = 3;
  var REPLACE = 4;

  var isnan = function (e) {
    return typeof e === 'number' && isNaN(e);
  }

  var isKey = function (id) {
    return typeof id === 'number'
      || typeof id === 'string';
  }

  var format = function (p) {
    return p.reduce(function (prev, e) {
      return typeof e === 'number'
        ? prev + '[' + e + ']'
        : prev && prev + '.' || e
    }, '')
  }

  function get (a, b, key) {
    var patches = [];
    getDiff(a, b, []);
    return patches;

    function getDiff (a, b, p) {
      var k;
      if (a === b || isnan(a) && isnan(b)) return;
      if (isObj(a) && isObj(b)) {
        for (k in a) {
          if (!hasOwn.call(a, k)) continue;
          if (hasOwn.call(b, k)) {
            getDiff(a[k], b[k], p.concat(k));
          } else {
            patches.push({
              t: DELETE,
              p: p.concat(k)
            });
          }
        }
        for (k in b) {
          if (!hasOwn.call(b, k)) continue;
          if (!hasOwn.call(a, k)) {
            patches.push({
              t: CREATE,
              p: p.concat(k),
              v: b[k]
            });
          }
        }
      } else if (isArr(a) && isArr(b)) {
        diffArr(a, b, p);
      } else {
        patches.push({
          t: UPDATE,
          p: p,
          v: b
        });
      }
    }

    function saveIndex (map, e, i, p, d) {
      switch (getType(e)) {
        case 'object':
          id = e[key];
          if (isKey(id)) {
            if (id in map.key)
              throw new Error(
                'repetitive key "'
                + format(p.concat(i + d))
                + '.' + key + ': ' + id
                + '" in ' + map.name + ' variable'
              );
            map.key[id] = i;
          }
          break;
        case 'number':
          e in map.num
            ? map.num[e].push(i)
            : map.num[e] = [i]
          break;
        case 'string':
          e in map.str
            ? map.str[e].push(i)
            : map.str[e] = [i]
          break;
        case 'boolean':
          (e ? map.true : map.false).push(i);
          break;
        case 'null':
          map.null.push(i);
          break;
        case 'undefined':
          map.undef.push(i);
          break;
      }
    }

    function getIndex (map, e) {
      switch (getType(e)) {
        case 'object':
          id = e[key];
          if (isKey(id) && id in map.key)
            return map.key[id];
          break;
        case 'number':
          if (e in map.num && map.num[e].length)
            return map.num[e].shift();
          break;
        case 'string':
          if (e in map.str && map.str[e].length)
            return map.str[e].shift();
          break;
        case 'boolean':
          if (e && map.true.length) {
            return map.true.shift();
          } else if (!e && map.false.length) {
            return map.false.shift();
          }
          break;
        case 'null':
          if (map.null.length)
            return map.null.shift();
          break;
        case 'undefined':
          if (map.undef.length)
            return map.undef.shift();
          break;
      }
      return -1;
    }

    function diffArr (a, b, p) {
      var amap = {
        name: 'origin',
        key: {},
        num: {},
        str: {},
        true: [],
        false: [],
        null: [],
        undef: [],
      }

      var bmap = {
        name: 'target',
        key: {},
        num: {},
        str: {},
        true: [],
        false: [],
        null: [],
        undef: []
      }

      var la = a.length
        , lb = b.length
        , i
        , n = 0
        , d = 0
        , ai
        , bi
        , e
        , map = {}
        , map2 = {}
        , ii

      for (i = 0; i < lb; i++) {
        saveIndex(bmap, b[i], i, p, d);
      }

      for (i = 0; i < la; i++) {
        e = a[i];
        bi = getIndex(bmap, e);

        if (~bi) {
          getDiff(e, b[bi], p.concat(i - d));
          saveIndex(amap, a[i], n++, p, d);
        } else {
          patches.push({
            t: DELETE,
            p: p.concat(i - d),
          });
          d++;
        }
      }

      for (i = 0; i < lb; i++) {
        e = b[i];
        ai = getIndex(amap, e);

        if (ai === -1) {
          patches.push({
            t: CREATE,
            p: p.concat(n),
            v: e
          });

          ai = n++;
        }

        ii = ai in map ? map[ai] : ai;
        if (i < ii) {
          patches.push({
            t: REPLACE,
            p: p.concat(ii),
            i: i
          });

          if (map2[i] in map) {
            map[map2[i]] = ii;
            map2[ii] = map2[i];
            delete map2[i];
          } else {
            map[i] = ii;
            map2[ii] = i;
          }
        }
      }
    }
  }

  return {
    get: get,
    apply: apply
  }

});

github: var-diff

下一篇: 实现一个打包工具 2