Blog

双向预览热更新技术

在诸如SwiftUI这种可以双向编辑的体系中，实时的反馈用户于控制面板和预览窗口修改的信息并更新源代码的体验中不可或缺的就是热更新的机制。这里我们探讨一种可行技术来实现类似的功能体验。

背景

双向预览

SwiftUI 是典型的双向预览机制的一个实例，至少包含如下两种模式：

  1. 修改源代码，IDE做出实时Preview的能力
  2. 编辑Preview和属性面板，IDE做出实时更新源码的能力

来自Web前端框架的启发

不论是双向绑定抑或是Virtual DOM都有热更新的能力，要么用脏检查，要么用Pub-Sub模式监听，要么就是VDOM或者单向数据流等技术。我们这里不抠名词而是专注于如何借鉴前端框架技术来实现我们IDE层面的双向预览热更新支持。

这里要明确的是热更新并不是实现双向预览的必要组成。双向预览可以依托事件驱动来完成实现，而热更新可以视作一种优化，我们这次主要讨论这种优化。

问题定义

假设UI由UI Tree定义，每一次的更新都有产生一个新的UI Tree请求，我们通过计算新的Tree与旧的Tree之间的最小差异并输出一个patch，旧的Tree通过打patch与新的Tree内容一致。

分析

React的启发式

严格的树与树之间的最小修改方案要使用 Levenshtein Distance 动态规划算法，又叫 编辑距离。然而在 树上的编辑距离 复杂度非常高，且难以优化。这里我们借鉴React中的启发式算法：

  1. Two components of the same class will generate similar trees and two components of different classes will generate different trees.
  2. It is possible to provide a unique key for elements that is stable across different renders.

第一个约定下，我们处理节点比对有如下几种情况：

  1. 结点类型不同，从当前结点开始的子树整体更新(重建)
  2. 结点类型相同，增量更新内部差异数据
  3. 不考虑跨层级的修改，因此如果结点因为跨层级移动而出现类型不匹配则按1处理

启发式的实现

一个BFS即可实现，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
BFS(source, target): // source and target are maps
Begin
    Queue = [source]
    while Queue not empty:
        head = Queue.pop()
        for key in head:
            if source[key] == target[key]:
                update(source[key], target[key], patch)
                Queue.push(source[key])
            else:
                insertOrDelete(source[key], target[key], patch)
End

动态规划优化

考虑一种情况，有如下两个列表，使用React的增量更新算法后产生一个三次移动的序列：

1
2
A: [a b c d]
B: [d a b c]

可是肉眼观察发现，其实仅需要将d元素挪动即可完成操作。产生这样结果的情况是React的算法还不够强，虽然保证了整体时间复杂度为O(n)，但是却容易有其他的副作用：滚动条或者动画在无需刷新时产生了刷新。尽管整体时效看上去乐观可是却会影响到用户体验。根本原因是React没有计算最小移动次数，这貌似又回到来先前提到的编辑距离的问题，但是除去编辑距离外还有最长公共子序列的算法，上述例子当中，我们可以看出最长公共子序列是a b c，这样我们仅挪动原始集合与LCS之间的差集即可完成最小挪动，这里的最小挪动集是d。

LCS算法相较于一般的编辑距离有一个优势就是可以转化为LIS算法，而LIS算法是有O(NlogN)时间的解的。

具体算法

欲将LCS转化为LIS算法我们还需要借助HashMap，用它来存储原始集合中元素在新集合中的位置。然后对位置序列求出LIS，这个结果与直接求LCS是等效的，证明请自行探索。

1
2
3
4
5
6
7
8
9
10
A: [b c d e f]
B: [c b h f e]
P: [1 0 . 4 3] // .为无意义值，求解方法为遍历A数组，并在HashMap中对应的B数组的位置填写A中当前元素的坐标
LIS:     [1 4]
HashMap: {c:0,
          b:1,
          h:2
          f:3
          e:4
         }

LIS的O(NlogN)解法

LIS状态转移方程： dp[i] = max{dp[i], dp[j] + 1} (0 <= j <= i, a[j] < a[i])

二分查找贪心优化：

  • 定义d[k]为长度为k的LIS的最末元素，若有多个k长度的LIS序列，则记录最小最末的元素，此处贪心。
  • 枚举a[i]，如果a[i] > d[len]那么d[++len] = a[i]，否则，从d[1]到d[len]中找到满足d[j - 1] < a[i] < d[j]，并且令d[j] = a[i]

保存方案的技巧：这里因为用了O(NlogN)的解法，保存方案需要额外的工作，方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let trace = list of list of pair // trace为2纬数组，第一个纬度是LIS的长度，第二纬度是某一长度下的更新序列
                                 // pair中第一个值存储元素数据，第二个存储层级信息
                                 // 如果发生了二分查找更新，则上升一个层级，层级越大代表当前的值位置越靠后
trace[0] = [(MIN, MAX)]; 
// trace的更新逻辑
if (a[i] > dp[len]) {
    dp.push(a[i])
    trace.push([Pair(a[i], currentLevel)])
} else {
    j = binary_search(dp, a[i]);
    if(dp[j - 1] < a[i] and a[i] < dp[j]) {
        dp[j] = a[i]
        trace[j].push(Pair(a[i], ++currentLevel))
    }
} 

let lastLevel = trace[dp.length - 1][trace[dp.length - 1].length - 1][1]
// 之后用二分法求每个更新序列中最接近lastLevel且不大于它的值即可找到最优解方案。

一个例子[1, 0, 3, 4, 2]：

1
2
3
       |0, 1|2, 2|
trace: |1, 0|3, 1|4, 1|
LIS:   [0, 3, 4]

解释：因为最末元素4的层级为1，所以前面每个位置不大于1的最小元素分别是0, 3。因为每个位置的序列一定是有序的，所以可以二分查找获得最优方案。

演示

move操作

对于P和LIS序列，从头开始同时扫描，逐个匹配结果，如果匹配说明属于LCS集合中，不做任何操作，否则产生move。

1
2
3
4
5
6
A:   [b c d e f]
B:   [c b h f e]
P:   [1 0 . 4 3] 
      ^
LIS: [0 3]
      ^

1与0不匹配，因此c元素产生move操作。

LCS集合中的元素不移动

匹配则不产生任何操作，匹配后指针右移。

1
2
3
4
5
6
A:   [b c d e f]
B:   [c b h f e]
P:   [1 0 . 4 3] 
        ^
LIS: [0 3]
      ^

遇到 . 则产生insert

产生插入h元素的操作，同时伴随着删除d元素。

1
2
3
4
5
6
A:   [b c d e f]
B:   [c b h f e]
P:   [1 0 . 4 3] 
          ^
LIS: [0 3]
        ^

(此后省略)

结果

所以我们有如下操作序列，此序列保证代价最小：

1
2
3
4
move c: 1 -> 0
move f: 4 -> 3
delete d
insert h: 2