5.4 调解算法的实现

你：为了实现调解算法，需要对代码做什么样的修改？

乔：它只需要修改SystemData.commit()的代码，如清单5.1所示。

清单5.1 系统数据类

class SystemData {
    systemData;

    get() {
        return this.systemData;
    }

    set(_systemData) {
        this.systemData = _systemData;
    }

    commit(previous, next) {
        if(!SystemValidity.validate(previous, next)) {
            throw "The system data to be committed is not valid!";
        };
        this.systemData = SystemConsistency.reconcile(this.systemData,
                                                      previous,
                                                      next);
    }
}

你：那么SystemConsistency是如何进行调节的？

乔: 清单5.2中暴露的SystemConsistency类通过比较前一个和当前一个开始调和过程。如果它们是一样的，那么我们就快进并返回下一个。

清单5.2 运行中的调解流程

class SystemConsistency {
    static threeWayMerge(current, previous, next) {
        var previousToCurrent = DataDiff.diff(previous, current);
        var previousToNext = DataDiff.diff(previous, next);
        if(DataDiff.isEmptyIntersection(previousToCurrent, previousToNext)) {
            return DataDiff.patch(current, previousToNext);
        }
        throw "Conflicting concurrent mutations.";
    }
    static reconcile(current, previous, next) {
        if(current == previous) {
            return next;
        }
        return SystemConsistency.threeWayMerge(current,
                                               previous,
                                               next);
    }
}

TIP 一方面，SystemConsistency类的代码是精致的。但另一方面，该代码是无状态的。

你：等一下! 你为什么要通过引用来比较先前和当前？你应该用值来比较它们，如果要比较两个嵌套哈希图的所有叶子，计算量就会非常大。

乔: 这就是不可变数据的另一个好处：当数据没有被变异时，比较引用是安全的，如果它们是相同的，我们就可以确定数据是相同的。

TIP 当数据是不可变的时候，通过引用进行比较是安全的，这样做是超级快的：当引用相同时，意味着数据是相同的。

你：三向合并算法的实现情况如何？

乔: 当previous与current不同时，这意味着同时发生的突变已经运行。为了确定是否存在冲突，我们计算两个差异：previousToCurrent和previousToNext。如果这两个差值的交集是空的，这意味着没有冲突。我们可以安全地合并从上一个到下一个的过渡所引起的变化。就代码而言，我们将previousToNext合并到current。

  你仔细看看清单5.2中SystemConsistency类的代码，你试图弄清楚这些代码是否是线程安全的。

你：我认为清单5.2中的SystemConsistency类的代码不是线程安全的。如果在SystemConsistency类中检查系统是否有变化和在SystemData类中更新状态之间存在上下文切换，那么一个突变可能会覆盖之前突变的变化。

乔: 你是完全正确的! 在像JavaScript这样的单线程环境中，代码工作得很好，在那里，并发性是通过事件循环处理的。然而，在多线程环境中，代码需要改进一下，并使用原子来实现线程安全。我将在第二部分告诉你如何做。

警告 SystemConsistency类不是线程安全的。我们将在第二部分使其成为线程安全的。

5.5 语义差异

NOTE 本节涉及SystemConsistency使用的DataDiff类的实现。如果你现在不想用精炼的递归的细节来挑战你的头脑，请随意跳过这一节。这并不妨碍你在整本书中享受与Joe讨论的其他内容。你可以在以后再来看看这一节。

TODO：承认这是语义差异的简化版本，不涉及删除问题。

TODO: 承认它不是新的。

TODO：重命名为结构性差异

你：你如何计算不同版本的系统状态之间的差异？

乔: 这是调解算法中最具挑战性的部分。SystemConsistency类使用DataDiff类进行差异计算。DataDiff类的代码实现了一个语义差异算法：这绝对不是小事。但是在最后，它只处理数据操作。

清单5.3 数据差异（DataDiff）类

class DataDiff {
    static diffObjects(data1, data2) {
        var emptyObject = _.isArray(data1) ? [] : {};
        if(data1 == data2) {
            return emptyObject;
        }
        var keys = _.union(_.keys(data1), _.keys(data2));
        return _.reduce(keys,
                        function (acc, k) {
                            var res = DataDiff.diff(_.get(data1, k),
                                                    _.get(data2, k));
                            if((_.isObject(res) && _.isEmpty(res)) ||
                               (res == "data-diff:no-diff")) {
                                return acc;
                            }
                            return _.set(acc, [k], res);
                        },
                        emptyObject);
    }

    static diff(data1, data2) {
        if(_.isObject(data1) && _.isObject(data2)) {
            return DataDiff.diffObjects(data1, data2);
        }
        if(data1 !== data2) {
            return data2;
        }
        return "data-diff:no-diff";
    }

    static patch(data, diff) {
        return _.merge(data, diff);
    }

    static leaves(obj, prefix = '') {
        return _.reduce(obj,
                        function(acc, v, k) {
                            if (_.isObject(v)) {
                                return _.concat(acc,
                                                DataDiff.leaves(v,
                                                                prefix + k + "."));
                            }
                            return _.concat(acc, [prefix + k]);
                        },
                        []);
    }
    static isEmptyIntersection(delta1, delta2) {
        return _.isEmpty(_.intersection(DataDiff.leaves(delta1),
                                        DataDiff.leaves(delta2)));
    }
}

你：我想说：精炼的数据处理。它涉及到一个_.reduce()里面的递归!

乔：一方面，它很棘手，但另一方面，它是非常容易写单元测试的代码。在写完几个用例后，你可以确信你的代码是没有错误的!

你：DataDiff.diff()的单元测试会是什么样子？

乔: 类似清单5.4中的代码。我将在第二部分告诉你更多关于为数据操作函数编写单元测试的信息。

清单 5.4 DataDiff.diff()的一个基本单元测试

var data1 = {
    g: {
        c: 3
    },
    x: 2,
    y: {
        z: 1
    },
    w: [5]
}

var data2 = {
    g: {
        c:3
    },
    x: 2,
    y: {
        z: 2
    },
    w: [4]
}

_.isEqual(DataDiff.diff(data1, data2),
          {
              "w":  [
                  4
              ],
              "y":  {
                  "z": 2
              }
          })

TIP 对于一段只处理数据操作的代码，写单元测试是很容易的!

你：我想人们也可以很容易地为SystemConsistency编写单元测试。

乔：肯定是的!

你：DataDiff的性能如何？我们必须对两块数据的所有叶子进行检查吗？

乔：在一般情况下，是的。但在用结构共享的方式操作系统数据的情况下，代码的效率要高得多。

你：什么意思？

JOE: 在结构性共享的情况下，大部分嵌套对象在两个版本的系统状态之间共享。因此大多数时候，当代码进入DataDiff.diffObjects()时，它将立即返回，因为data1和data2是相同的。

TIP 计算两个版本的状态之间的差异是有效的，因为通过结构共享从同一个哈希图创建的两个哈希图有大部分的共同节点。