大前端开发中的“树”

本文介绍 Web、Android、iOS、Flutter 这些前终端平台下，与 “树” 及视图系统有关的技术话题，并尝试分析它们之间的异同点；方便从事大前端开发的同学对各平台的技术特性有更广泛的了解。一、前言从早期 Web 开发中的 DOM 树，再到现在 Flutter 开发中的 “三棵树”，以及 Android 和 iOS 开发中相似的概念，它们有联系又有区别。围绕 “树”，各个平台有一些共同的

短暂又灿烂的

3063人浏览 · 2021-10-28 11:28:53

短暂又灿烂的 · 2021-10-28 11:28:53 发布

本文介绍 Web、Android、iOS、Flutter 这些前终端平台下，与 “树” 及视图系统有关的技术话题，并尝试分析它们之间的异同点；方便从事大前端开发的同学对各平台的技术特性有更广泛的了解。

一、前言

从早期 Web 开发中的 DOM 树，再到现在 Flutter 开发中的 “三棵树”，以及 Android 和 iOS 开发中相似的概念，它们有联系又有区别。围绕 “树”，各个平台有一些共同的技术话题，例如采用合并操作完成性能优化等。在大前端的背景下，弄清楚这些技术点对研发工作非常有必要。

二、Web 中的树

2.1 DOM 树

Web 页面主要由 HTML，CSS，JS 组成。其中 HTML 是由标签和文本组成，每个标签都有它自己的语义，浏览器会根据其语义来展示内容；CSS 又称为层叠样式表，是由选择器和属性组成，负责改变元素的大小、颜色等信息；JavaScript，简称 JS，负责页面的逻辑处理，我们可以通过 JS 来修改 DOM 的数据，从而达到修改页面的目的。

通常，我们编写好 HTML、CSS、JavaScript 等文件，经过浏览器就会显示出漂亮的页面，其中的过程大致如下：

Web 页面渲染过程

可清楚地看到 HTML 被解析成了 DOM 树，CSS 被解析成样式规则树，两者再合成一棵渲染树，浏览器再基于渲染树来进行布局和绘制。其中 DOM 树构建过程如下：

读取原始字节并根据文件的相应编码（常见的有：UTF-8、GB2312）将其转换成各个字符。
令牌化：浏览器根据 HTML 规定的各种令牌，如：“<html>”、“<body>” 等，将字符转成一个个的令牌，每个令牌也代表着 DOM 树中的一个节点。
词法分析：发出的令牌转换成定义其属性和规则的“对象”。
DOM 构建：标记之间通常以嵌套关系存在，所以我们在创建对象的时候，需要将其链接在一个树数据结构内，从而记录标记中定义的父项-子项关系：html 对象是 body 对象的父项，body 是 paragraph 对象的父项，依此类推。

HTML 解析流程

一大段文本信息经过这番处理后，就转成一颗可以被浏览器理解的DOM树，之所以这么处理，主要有以下几个优点：

JS 可通过对 DOM 树的操作，来实现对 Web 界面的操作，而不是对着纯文本进行处理。
随机访问文档中的任一数据，可从父节点逐级遍历到目标节点。

2.2 Virtual DOM 树

基于上面 DOM 树的介绍，我们知道 JS 对界面的影响主要通过 DOM 模型，但是 DOM 模型也存在一些问题，如 JS 对 DOM 操作是比较消耗性能的，这个过程可能需将 JS 引擎挂起、转换传入参数数据、激活 DOM 引擎，DOM 重绘后再转换可能有的返回值，最后激活 JS 引擎并继续执行。

基于这个问题，近年来引申出了 Virtual DOM 的概念，简单来说，就是 JS 中模拟 DOM 的构建，减少操作 DOM 的次数，来提高页面性能的一种方式，目前主流框架 React，Vue 等都有这方面的运用。

2.2.1 用 JS 对象模拟 DOM 树

我们知道每个 DOM 所包含的信息比较多，其中最核心的主要有三个属性：tag、attrs 和 children。Virtual DOM 本质上就是一个简化版的 JS 对象，下面是一个典型的 Virtual DOM 对象例子：

HTML 解析流程

2.2.2 计算新旧 Virtual DOM 树的差异

比较两棵 DOM 树的差异是 Virtual DOM 算法最核心的部分，这也是所谓的 Virtual DOM 的 Diff 算法。两个树的完全的 Diff 算法是一个时间复杂度为 O(n^3) 的问题。但是在前端开发当中，我们往往只对同层 DOM 元素进行操作，所以 Virtual DOM 只会对同一个层级的元素进行对比。

如图，进行 Component Diff 时，发现组件 D 和 G 是不同类型的组件，会直接删除组件 D 及其子节点，然后重新创建组件 G 及其子节点。此时 Diff 顺序为：delete E → delete F → delete D → create E → create F → create G。

Component Diff 举例

假如将 D 的子节点重新排序，如 E、F 的顺序换成了 F、E，这个该怎么对比？如果按照上面提到的方法进行顺序对比的话，它们都会被替换掉，这前后可能需要进行四次 DOM 操作，而我们是不是一定要替换节点呢？事实上，只需通过节点移动就可以达到更新的目的，所以我们只需计算节点移动的过程即可，这就牵涉到两个列表的对比算法：

R A B C D E F

R A B C D F E

将树的结构转化成一维的结构，求最小的插入、删除操作（移动=删除+插入）。在开发过程中，我们常常只会对同层的 DOM 进行操作，所以针对一些同层内比较常见的移动情况进行优化，就足以解决大部分场景。这也使得整个计算过程变得相对简单一点，理论上算法时间复杂度可达到线性的 O(max(M, N))。大多数算法都是采用 key 加 tagName 方式来进行对比，给每个子节点加上一个 key 作为唯一标志，这样既能有效复用老的 DOM 树上的节点，算法时间复杂度又不会很高。

简化 Diff 计算过程

2.2.3 遍历差异对象并更新 DOM

通过 Virtual DOM 树能生成相应 DOM 树，所以我们可以通过对比新旧树的变更情况，记录每次遍历节点的差异，然后进行相应 DOM 操作，从而得到新的 DOM 树。

深度遍历对比示意图

三、Android 中的树

本节尝试类比 Android 视图系统中，与 Web 语境下的 DOM 树、CSSOM 树和渲染树相类似的概念。需要留意的是，由于视图系统流程的差异，各概念之间只能做到 “形似”，难以进行完全对等的类比。

3.1 布局描述与视图

3.1.1 布局描述

在传统的 Android 开发中，布局描述通常通过布局资源 (Layout Resource，采用 XML 格式) 实现。从外形上看，布局资源类似于 HTML (及 React JSX) 中，与 DOM 树 (及 Virtual DOM 树) 对等的页面布局描述方式。


<LinearLayout     
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical" >
        <TextView android:id="@+id/text"
                  android:layout_width="wrap_content"
                  android:layout_height="wrap_content"
                  android:text="Hello, I am a TextView" />
        <Button android:id="@+id/button"
                android:layout_width="wrap_content"
                android:layout_height="wrap_content"
                android:text="Hello, I am a Button" />
</LinearLayout>

与 Web 通过样式表描述布局有所不同，Android 的视图布局形式一般通过多种支持布局的 “视图组合” (ViewGroup) 完成，例如线性布局、相对布局等。Android 提供自定义视图，支持自定义的布局描述及视图渲染。

布局描述的节点与实际视图，大多数情况下是一对一的关系；通过 <layout>、<merge> 等标签，也可以组合出嵌套、内联等一对多的关系，在布局资源转换为视图树时，进行这些处理。

虽然 HTML 的视图描述与 Android 布局资源的编码形式类似，但 DOM 树不能与布局资源严格类比。例如，相较于 Web 可以通过代码，透过 DOM 树修改 HTML 的内容，Android 布局资源是不可变的，只能在布局资源转换为视图后，在视图层面进行修改。

3.1.2 视图

View 是 Android 视图描述的事实单位，前文提到的视图组合 ViewGroup 也属于 View。视图之间的父子关系建立了一个树形结构，共同描述布局和渲染。

通过 Android Studio 查看视图树

Android 的视图布局和渲染过程通过 Measure、Layout、Draw 三个步骤完成，视图的位置和大小通过 Measure 和 Layout 过程确定，视图需渲染的内容通过 Draw 过程上屏，并最终合成为屏幕内容。通过 requestLayout()、invalidate() 等方法，可以直接控制视图重新布局或渲染。

由此可见，View、ViewGroup 及它们构成的视图树直接决定了渲染过程和结果。View 与 ViewGroup 之间构成的树形层级关系和渲染描述，可以大致类比渲染树在 Web 渲染中的角色。

3.2 样式与主题

类比样式表，Android 在视图描述中引入了样式 (Style) 和主题 (Theme)。样式和主题可用于视图的属性描述，还可用于 Application、Activity 等层级的全局属性描述。

样式和主题都携带一组视图属性的集合，从而可类比 CSS 用于描述同类元素的共性外观。
样式和主题具有继承关系，从而可类比 CSSOM 的树形结构。
以主题形式应用在父级视图的公共视图属性，会同时作为优先级较低的属性应用在子视图中：如果子视图自己没设置这个属性，就使用主题设置的属性。

声明样式


<resources>
    <style name="GreenText" parent="TextAppearance.AppCompat">
        <item name="android:textColor">#00FF00</item>
    </style>
</resources>

使用样式


<TextView
    style="@style/GreenText"
    android:text="Hello">
</TextView>

使用主题

<application 
    android:theme="@style/CustomTheme">
</application>

3.3 视图渲染过程

3.3.1 从布局描述到视图树

Android 通过 LayoutInflater 将布局描述转换为视图树，解析布局资源的 XML，并通过反射或查表，生成对应的 View 实例。

在创建每个子视图时，会同时考虑其所属上下文的主题信息，这里体现上一节中主题的全局生效、作为较低优先级属性的作用。

针对这个过程的性能优化，有两个成熟方案：

AsyncLayoutInflater - 异步生成：通常来说，这个转换步骤需要在主线程进行，保证生产和消费的顺序性；Android 提供了异步执行这个过程的工具 AsyncLayoutInflater，通过提前加载，减少这个过程的显式耗时。

X2C - 预存产物：事实上，通过编写纯 Java 代码，也可以完成与布局资源一致的工作（类比通过 JavaScript 手写 DOM 树）。因此可以通过提前将布局资源转换为其对应的 Java 代码（可以通过注解处理的方式），来减少 XML 解析和视图反射的耗时。

需要注意的是，由于 View 的布局渲染流程还未开始，这时生成的视图树并未包含完整的位置和尺寸信息。

3.3.2 从视图树到上屏展示

Web 在生成渲染树后，就可以进入布局和渲染过程；Android 的这个过程与 Web 处理渲染树上屏过程，从流程上来说较为类似，就不做具体展开。

通过 Measure 和 Layout 过程，进行布局，从而确定每一个子视图的位置和尺寸信息。
通过 Draw 过程，触发视图绘制，并合成像素信息上屏。

四、iOS 中的树

4.1 视图

iOS 中的视图就是在屏幕上显示的一个矩形块（比如图片，文字或者视频等），它能够拦截触摸手势等用户输入。视图在层级关系中可以互相嵌套，一个视图可以管理它的所有子视图的位置。

在 iOS 当中，所有的视图都从一个叫做 UIView 的基类派生而来，UIView 可以处理触摸事件，可以支持基于 Core Graphics 绘图，可以做仿射变换（例如旋转或者缩放），或者简单的类似于滑动或者渐变的动画。

4.2 iOS 坐标系统

在介绍UIView前，先介绍一下iOS的坐标系统概念： [1]

视图左上角为坐标原点 (0，0)
CGPoint(x, y) 创建坐标点
CGSize(width, height) 表示视图宽度和高度
CGRect 结合了CGPoint 和 CGSize
origin 表示左上角所在的 CGPoint(x, y)
bounds 是指在自身视图中的 CGRect(x=0, y=0, width, height)
frame 是在父视图的 CGRect(x, y, width, height)
center 是指在父视图中的 CGPoint(x + width / 2, y + height / 2)

iOS 坐标系统概念图

4.3 UIView

UIView 负责接收触摸手势事件通过 UIResponder 来响应，负责显示、支持动画效果等则由 CALayer 来支持。

UIView 声明

4.4 事件响应链机制

上面介绍 UIView 负责响应触摸手势等事件有 UIResponder 负责， UIResponder 是 UIView 的父类，主要实现了事件响应链（Responder Chain）：当 UI 收到某个信号的响应后这种控件间自上到下消息传递的链路。其中最重要的就是 事件传递流程 以及 如何找到第一响应者。

事件响应链流程图

4.5 CALayer

CALayer 与 UIView 的关系是：

UIView 为 CALayer 提供内容，专门负责处理触摸等事件，参与响应链
CALayer 全权负责显示内容 (contents)

视图显示原理图

4.5.1 图层树

CALayer 在概念上与 UIView 类似，同样也是一些被层级关系树管理的矩形块，同样也可以包含一些内容（像图片，文本或者背景色），管理子图层的位置，在数据结构上构成树的形式，称之为图层树；图层树的能力包括：

阴影、圆角、带颜色的边框
3D 变换
非矩形范围
透明遮罩
多级非线性动画

在 CALayer 的工作过程中，又衍生出了三种树：呈现树、模型树、渲染树。

4.5.2 呈现树与模型树

呈现树是图层树中所有图层的呈现图层所形成，模型树是所有图层的模型图层所形成。

呈现图层仅在图层首次被提交的时候创建。它的作用是，CALayer 在做隐式动画时，CoreAnimation 就需要在设置一次新值和新值生效之间，对屏幕上的图层进行重新组织。这意味着 CALayer 除了 “真实” 值（视图描述中设置的值）之外，必须要知道当前显示在屏幕上的属性值，而每个图层属性的显示值都被存储在呈现图层中。

不过，为了让 CoreAnimation 更新显示，大多数情况下不需要直接访问呈现图层，而是通过和模型图层交互即可。典型场景包括同步动画和处理用户交互：

如果是实现一个基于定时器的动画，而不仅仅是基于事务的动画，这个时候需要准确知道在某一时刻图层显示在什么位置，以便正确摆放图层；
如果想让做动画的图层响应用户输入，可以使用 hitTest 方法来判断指定图层是否被触摸，这个时候呈现图层而不是模型图层调用 hitTest 会显得更有意义，因为呈现图层代表了用户当前看到的图层位置，而不是当前动画结束之后的位置。

4.5.3 渲染进程与渲染树

动画和屏幕上组合的图层被一个单独的进程管理，而不是应用程序，这个进程就是所谓的渲染服务。

渲染过程会被细分为四个分离的阶段：

布局：准备视图 / 图层的层级关系，以及设置图层属性（位置、背景色、边框等）的阶段
显示：图层的寄宿图片被绘制的阶段
准备：CoreAnimation 准备发送动画数据到渲染服务，同时也是 CoreAnimation 将要执行一些别的事务例如解码动画过程中将要显示图片的时间点
提交：CoreAnimation 打包所有图层和动画属性，然后通过 IPC 发送到渲染服务进行显示

打包的图层和动画到达渲染服务进程，他们会被反序列化来形成叫做渲染树的图层树。使用这个树状结构，渲染服务对动画的每一帧做出如下工作：

对所有的图层属性计算中间值，设置 OpenGL 几何形状（纹理化的三角形）来执行渲染
在屏幕上渲染可见的三角形

五、Flutter 中的树

Flutter 中树的结构和 Web 中的非常相似。本节尝试会它们进行一些类比，同时也会展示 Flutter 中的树实际是如何运行的。

5.1 和其他平台的相似点

在很多资料中都会提及 Flutter 有三颗树 (Widget 树、Element 树、RenderObject 树)，这个概念有助于我们从其他平台快速过渡到 Flutter ，我们暂且使用这个概念叙述，后文再探讨 Flutter 中具体的树组织形式。

5.1.1 Widget

本质上是一个配置文件，它决定了节点的配置信息。比如：颜色、图片、文字、控件大小等。它和 Android View、iOS UIView 、 Web HTML + CSS 有一定的对应关系。

5.1.2 Element

对比差异减少操作对底层绘制操作次数的中间节点。类比到 Web 就是前文提到的 Virtual DOM，在 Android Composed 和 iOS 的 SwiftUI 中也有相似的概念。

5.1.3 RenderObject

实现 layout、paint 两套协议，确定在 Canvas 在局部位置应该如何绘制。在 Web 的语境下它就相当于 DOM 树，在Android 和 iOS 的语境中它覆盖了 View 中 layout 和 paint 流程。

5.2 运作流程

前文提到，Flutter 的树用三棵树来描述并不完全精确。这小节尝试揭示它的全貌。先上一张总览图：

总览图

可以看到 Flutter 中有四个和视图相关的树形结构 (Widget、Element、RenderObject、Layer)，它们之间又相互关联汇总成一棵以 RootElement 为根节点的视图树。接下来将从树的构建以及视图更新两个过程展开描述。

5.2.1 树的构建

在一个 Flutter App 创建的同时会配套地生成三个根节点 (Widget、Element、RenderObject)，也就是总览图中标记为红色的节点。紧接着 Flutter 会从 rootElement 出发，触发一次 build 流程。

build 流程由一个 Element 节点触发，首先与它相连的 Widget 节点获取到它的子节点，并用它产生一个 Element 节点和一个RenderObject 节点 (可能没有，根据 Widget 类型决定)，新产生的节点会挂载到原先的父节点下。参照下图 build 流程理解起来会更直观一些。

build 流程

接下来将不断的重复这一个过程，直到 Widget 获取不到子节点，树的第一次构建就结束了。最终获得一个类似总览图中显示的数据结构。

5.2.2 视图更新

Flutter 中视图更新有三个类型分别是 build、layout、paint。这三种类型都遵循一个统一的流程，下面用更新流程图展示。

build 流程

某一个节点需要刷新时，会将自己添加到一个单例对象 Owner 的 dirty 列表中，表示自己需要更新。当下次 vsync 信号到来时，Owner 会遍历 dirty 列表中的元素，让它们都重新执行一次对应的步骤。

build

我们在树的构建一节已经提到 build 的流程，视图更新的流程基本一致，区别在于 Element (或者 RenderObject) 此时可能已经存在子节点了，因此在 Widget 创建新对象之前会有一个 Diff 逻辑，以确定是否需要更新。Diff 的逻辑和本系列文章的上篇中提到的 Web Diff 逻辑相似，这里不作详细展开。

layout、paint

在 paint 的流程中会产生若干 Layer (详见 Layer 小节) 并且它们形成一个树的结构，完成了整棵大树的最后拼图。

layout 和 paint 的具体过程与其他平台的处理过程相近，这里不作详细展开。

Layer

RenderObject 可以被理解为画布的局部，Layer 则代表在这个局部画布中的一个图层。我们可以通过将图层按顺序叠放起来最终得到想要的图案。它的行为相对较独立，并且主要作用于创建它的 RenderObject ，因此在其他资料的树结构中常常不会提及它。

5.2.3 小结

Flutter 中各个组件构成一整棵树的整体，通过组件间的协同来完成视图的绘制。Widget 暴露给开发者使用，借由它的轻量级允许开发者在数据变化的时候频繁的创建；Element 充当一个过滤网隔绝不必要的变化；RenderObjcet 藏在最底层处理页面的绘制。

六、总结

本节尝试从共性特征、实现对比和演进过程的角度，加以总结。

共性特征

“树” 作为视图元素层级化的组织形式，普遍存在于各个前端视图系统中。
前端视图系统均基本遵循 解析视图描述 → 布局 → 渲染的处理过程。此外，在解析视图描述环节，通过引入 Virtual DOM 类 “逻辑树” ，可以有效增强视图变更性能。

实现对比：窥探平台间性能差异

在各具体平台下，树结构携带的信息及其对渲染结果的影响程度不完全相同。

以动画系统为例，iOS 的视图系统把动画配置作为视图树描述的一部分，直到渲染时才计算实际值，从而提升动画性能；而 Android 渲染过程一般依靠视图树的变化实现动画，相比之下增加了处理环节。这在一定程度上反映了 iOS 和 Android 设计思路的差异，或许也可以作为早期 iOS 动画性能优于 Android 的佐证。

演进过程：Virtual DOM 思想的开枝散叶

自 React 引入 Virtual DOM 开始，维护一个 “抽象的视图描述”，成为近代 Web 开发的主流方案。Virtual DOM 通过屏蔽上层代码对 DOM 的直接维护，可以实现更可控的局部更新，从而提升性能和易用性。

而 Flutter 的视图系统进一步实践了这个思想：通过 Widget - Element 树的工作机制，筛选变化、减少操作，支撑高性能渲染。更进一步，上层业务代码可以在 Widget 声明 “有状态” 和 “无状态” 来显式控制更新。