大前端开发中的“树” (上)
本系列文章共分为上、下两篇，介绍 Web、Android、iOS、Flutter 这些前终端平台下，与 “树” 及视图系统有关的技术话题，并尝试分析它们之间的异同点；方便从事大前端开发的同学对各平台的技术特性有更广泛的了解。 |
|---|
- 读取原始字节并根据文件的相应编码（常见的有：UTF-8、GB2312）将其转换成各个字符。
- 令牌化：浏览器根据 HTML 规定的各种令牌，如：“<html>”、“<body>” 等，将字符转成一个个的令牌，每个令牌也代表着 DOM 树中的一个节点。
- 词法分析：发出的令牌转换成定义其属性和规则的“对象”。
- DOM 构建：标记之间通常以嵌套关系存在，所以我们在创建对象的时候，需要将其链接在一个树数据结构内，从而记录标记中定义的父项-子项关系：html 对象是 body 对象的父项，body 是 paragraph 对象的父项，依此类推。
HTML 解析流程 [1] 一大段文本信息经过这番处理后，就转成一颗可以被浏览器理解的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.2.1 用 JS 对象模拟 DOM 树 我们知道每个 DOM 所包含的信息比较多，其中最核心的主要有三个属性：tag、attrs 和 children。Virtual DOM 本质上就是一个简化版的 JS 对象，下面是一个典型的 Virtual DOM 对象例子： HTML 解析流程 [5] 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 树。 深度遍历对比示意图 [2] 三、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 - 异步生成[6]：通常来说，这个转换步骤需要在主线程进行，保证生产和消费的顺序性；Android 提供了异步执行这个过程的工具 AsyncLayoutInflater，通过提前加载，减少这个过程的显式耗时。
X2C - 预存产物[7]：事实上，通过编写纯 Java 代码，也可以完成与布局资源一致的工作（类比通过 JavaScript 手写 DOM 树）。因此可以通过提前将布局资源转换为其对应的 Java 代码（可以通过注解处理的方式），来减少 XML 解析和视图反射的耗时。
需要注意的是，由于 View 的布局渲染流程还未开始，这时生成的视图树并未包含完整的位置和尺寸信息。
3.3.2 从视图树到上屏展示
Web 在生成渲染树后，就可以进入布局和渲染过程；Android 的这个过程与 Web 处理渲染树上屏过程，从流程上来说较为类似，就不做具体展开。
- 通过 Measure 和 Layout 过程，进行布局，从而确定每一个子视图的位置和尺寸信息。
- 通过 Draw 过程，触发视图绘制，并合成像素信息上屏。
参考资料 [1] 构建对象模型 https://developers.google.com/web/fundamentals/performance/critical-rendering-path/constructing-the-object-model [2] 深度剖析：如何实现一个 Virtual DOM 算法 https://github.com/livoras/blog/issues/13 [3] 重谈 React 优势 —— React 技术栈回顾 https://www.zhoulujun.cn/html/webfront/ECMAScript/jsBase/2018_0424_8101.html [4] JavaScript 是如何影响 DOM 树构建的 https://blog.poetries.top/browser-working-principle/guide/part5/lesson22.html [5] The Inner Workings of Virtual DOM https://rajaraodv.medium.com/the-inner-workings-of-virtual-dom-666ee7ad47cf [6] AsyncLayoutInflater https://developer.android.com/reference/androidx/asynclayoutinflater/view/AsyncLayoutInflater [7] X2C https://github.com/iReaderAndroid/X2C 本系列文章的下篇将介绍 iOS 和 Flutter 平台中相关的技术话题。敬请期待~ QQ音乐招聘 Android / iOS 客户端开发，点击左下方“查看原文”投递简历～ 也可将简历发送至邮箱：tmezp@tencent.com