Redux 中的一个隐藏 Bug

Bug 的成因

我在 这篇文章 中曾经说了一句关于 Redux 的话：“就算程序员未经过专门的训练（例如掌握框架的 Best Practice），也可以显著降低 Bug 出现的概率。”然而最近同学遇到的一个 Bug 让我想把这句话改掉：只有当 Redux 配合 Immutable-js 的时候，才可以显著降低 Bug 出现的概率。我相信这个坑大部分人都踩过：

// action
function updateData(data) {
    // ....
    dispatch({ data });
    // ....
}

// component
class X extends React.Component {
    // ....
    update(newData) {
        // get current data
        const { data } = this.props;
        // change data
        data.x = newData;
        // update new data to store
        updateStore(data);
    }
    // ....
    render() {
        return <div>{this.props.data.x}</div>;
    }
}
export default connect(
    ({ data }) => ({ data })
)(X);

当执行 update 的时候，界面并不会发生改变。在使用 Redux Devtools 查看 Diff 的时候，会发现 (states are equal)。有经验的大佬一眼就能看出来问题所在：由于 JavaScript 对于非基础类型是引用传值，因此当你在执行 data.x = newData 的时候，你已经把 Store 中的 data 改掉了，于是 Redux 在 Shallow Equal 的时候，会判断你传进来的值与 Store 中的值相等，本质上，上面的代码大概相当于下面的这段，这样看起来是不是简单多了：

const a = { x: 1 };
const b = a;
b.x = 2;
if (a.x !== b.x) {
    console.log(`update: ${a.x} -> ${b.x}`);
} else {
    // always execute this line
    console.log(`a.x === b.x === ${a.x}`);
}

一个很暴力的解决方案

有一个很暴力的解决方式，就是将原来的数据深克隆一份，修改之后再传回去。对于绝大部分编程语言来说，除了当对象的属性比较多，或者嵌套比较深的时候，会比较慢以外，对于空间的占用不会有太大影响，毕竟在一轮更新操作之后，之前的对象就不会被任何变量引用了，于是会被自动垃圾回收掉。但是可以有更好的方法，那就是不可变数据。

不可变数据的概念

不可变数据在函数式编程中经常出现，而且也是函数式编程语言最常见的几个特性之一。它的思想就是，每次尝试修改其中的内容，就创建一个新的数据。用代码描述的话，大概如下：

data = ['x', 1, 'y', 2, 'z', ['w', 3]]
a = make_immutable(data)
b = set(a, 'x', 2)
print(get(a, 'x')) // -> 1
print(get(b, 'x')) // -> 2

当然，具体的实现可以看本文第一段链接中的 Immutable-js（用起来与上面的代码有很大差别），我不打算在这儿讲这个库，因为官方文档已经足够详细了。

不可变数据的应用

可持久化数据结构

我在高中的时候曾经听过一个“可持久化线段树”的概念，它本质上也算一种不可变数据，因为每次对树的修改都会产生一个新的线段树，与真正的不可变数据比起来，它保存了每一个历史版本，通过共用节点来节省内存空间。

图片来源：https://www.cnblogs.com/zinthos/p/3899565.html

虽然它并不是专门用来解决上文中 Redux 的问题，但它竟然可以很方便地解决“区间第 k 大值”这样的问题（以前只知道线段树套平衡树），还是很让人惊讶的。在这里先膜拜一下提出一种实现方法（主席树）的 fotile 主席。顺便提一个梗，fotile 当年被称为“中国高端数据结构专家与领导者”……

后来我又看到了丽洁神犇的一篇文章《可持久化数据结构研究》，里面讲了可持久化线段树、可持久化块状链表、可持久化平衡树这三个数据结构以及应用场景。除了能解决被当作入门题的“区间第 k 大值”问题以外，它们还能解决离线转在线问题和动态凸包问题。文中也分析了几道真实的题目。这算是我见过的这类数据结构在算法中最优雅的运用了。唯一的缺点是，由于丽洁实在是太神，所以文章对新手挺不友好的……

函数式编程

又提到了这个词。前两周刚看了前同事翻译的《Elixir 程序设计》。后半部分并没有特别详细去看，因为我一时半会儿还用不上，但我对前面的内容印象挺深刻的。尤其是 Elixir 这样的函数式编程语言天生适合高并发的场景，一个很重要的原因是里面的数据都是不可变的，因此不需要信号量和锁来保证读写冲突；而且因为数据不可变，所以不用担心当前使用的数据在什么时候被哪段代码改掉了，这是不可能发生的。

追踪状态的改变

Redux 对于经常写 React 的同学已经比较熟悉了。在 Redux Devtools 里面可以追踪每一个时段的 Store 树，查看每次 Action 的 Payload，甚至还可以 Diff 被 Action 修改前后的数据。

Vuex 的原理并不是通过状态机来改变 Store，而是通过 Vue 通用的监听器来监听数据的改变，这就决定了 Vuex 是不可能对 Store 本身使用不可变数据的（Store 内部依旧可以使用不可变数据，但好像也没什么意义的样子）。

不过 Redux Devtools 和 Vuex Devtools 这两个工具并没有用不可变数据，我查看了一下它们的源码，发现 前者 是从 @@redux/INIT 时的状态（computedStates = []）开始不断使用 Reducer 计算，后者 则是在 state.history 中保存了所有完整的 Store 数据。我没法断定这两种方案哪个比较好，因为算法设计中有两个方法，一个是反复计算（用时间换空间），一个是缓存（用空间换时间），对于 Devtools 的需求，我认为这两种方法都是可行的。

不可变数据结构的实现

首先，将之前的元素深克隆一份再修改是绝对没问题的，但这太暴力了，不在本文的讨论范围之内……

高级语言中的实现

对于 JavaScript 这样的高级语言，可以参考 Immutable-js 的方式，对于不同的类型分别处理，对于一般的应用，也可以只考虑处理 Object。为了节省内存占用，在 make_immutable 的时候可以从小到大构造这个对象，修改的时候只需要从它开始往上走，创建新的对象，除了被修改的属性以外，其它属性保持之前的引用即可。对于旧的值，一旦引用数清零，就会被垃圾回收清理掉。举个例子，对于下面的数据：

const a = {
    x: 1,
    y: 2,
    z: { w: 3 }
};

应该先构造 { w: 3 } 这个数据，然后再构造整个 a 数据。最简单的实现方法当然是使用递归。然后如果在后文中 a.z 被“改掉”了，之前的 a 也被删掉了，那么 { w: 3 } 这个数据就可以被垃圾回收清理掉了。

数据结构 / 底层的实现

可以参考可持久化线段树的做法，为“修改”的数据建立新节点，修改指针的指向，通过共用节点的方式节约内存。如果是 C 这样没有垃圾回收功能的语言，还得手动写一下垃圾回收，其实也不难，只需要劫持一下赋值操作，使用引用计数就可以了。