fre 2.1 重构，从右往左的 diff 算法

halo，大家好，俺是 132，好久没更新 fre 了，趁这周彻底重构了 diff 算法

背景

从 fre2 开始，我使用了一种类似 vue2 的 diff 算法的思路，它使用两个指针，从两端同时遍历，在 leetcode 中，这种优化方法也叫做对撞指针

https://leetcode-cn.com/problems/valid-palindrome/

因为 fre 的 fiber 结构特殊的遍历方式，以及两阶段遍历的局限性，导致两端同时遍历的思路没有办法直接用

两阶段遍历，其实是很难安排的，因为它要求两次遍历的节点数量，顺序都一模一样

在 reconciler 中从两端同时遍历，那么在 commit 阶段也必须从两端遍历

这是很难做到的，因为 fiber 链表是个很鸡肋的结构，它有很多指针，但是遍历方式只有一个，没有反向指针

所以我从 fre2.0 的时候就意识到这个问题，并且一直在思考，最近终于找到一种思路

从左到右

传统的同步框架都是从左往右遍历，因为它们是同步 singlepass 的，相对而言对 dom 指针比较容易安排

但是对于两阶段异步遍历的时候，reconcile 阶段是拿不到 dom 指针的，这是难点之一

old [1, 2, 3]
new [1, 3, 2]

这个遍历，很明显，是 3 插入到 2 前面

在 fiber 中我们只对 newKids 遍历，如果是从左往右，遍历到 3 的时候，2 还没生成呢，像 vue 可以从旧节点中拿到 2

所以我想了一个办法，那就是不管怎样，我们都默认从右往左遍历，两个阶段都按照这个顺序

所以我把整个 fiber 的顺序都给反转了，这么做的另一个好处是，reconcile 阶段不再需要关注 dom 指针了

dom 指针只需要在 commit 阶段更换就好了

effectlist

因为遍历顺序严格按照从右往左了，所以之前的失败的 effectlist 提案也可以搞起来了

之前没有 effectlist 的时候，commit 阶段是递归的，当节点变多的时候会直接爆栈

最佳解决方案就是链表了，effectlist 是依附在 fiber list 上的单链，可以理解为圣诞树上的一串彩灯，啊哈哈

优缺点

经过这一次重构，我终于对 fre 的 diff 算法彻底放心了

甚至可以说，这是两阶段遍历，适用于 fiber 结构的，唯一解

优点是 reconcile 阶段做到 without dom 了，这样一来，fre 的 reconciler 可以轻松跑到 worker 等平台中，而不需要模拟 dom

缺点是，从右往左的遍历顺序，导致 effect 和 refs 执行顺序和 react 完全相反，fre 的测试也崩坏了o(╥﹏╥)o

但是我认为这是值得的，fre 从来就不打算完美兼容 react，相反我更希望面试题多加一条：

fre 中 effects 和 refs 为什么和 react 顺序相反？

总结

其实和大家想象的不一样，我从不刷题，leetcode 只是偶尔上去看看，并不会真的做题目

算法的前提是数据结构，摊上了 fiber 这种结构，算法也要想办法调整

https://github.com/yisar/fre

最后放一下 fre 的 github 链接，虽然现在前端框架已经凉了，什么手写，源码都烂大街了，但 fre 总共只有 400 行，还是积攒了我很多心血的