基于ast思维的html字符串编辑

在一个项目中,我需要获取当前页面的html字符串,然后发送到worker中,对html进行编辑、对比等。和在DOM环境下可以方便的编辑DOM不同,如果只有字符串,想要编辑,而且还要对两个html进行diff操作,其实还是有点难度。在virtual dom中,我们可以通过node的type来知道这个节点是否是同一个,但是如果只有纯字符串,这个确认动作就会比较麻烦。我想,我已经对ast有一定了解了,能不能把html抽象为ast,然后对ast对象进行编辑,再由ast还原为html呢?于是,我开动脑筋,写了一个叫做abs-html的库,用于对html转化为基于HyperJSON的ast对象,并且提供了两个对象的diff和patch方法,以及重新生成html字符串的rebuild方法。

生成HTML的AST

Robust第25期中,我详细阐述了简单的编译原理,基于这一原理,我可以将html字符串转化为一个token序列,并拼成一个ast。由于我并不需要一个完整的编译逻辑,我的目标是一个编译的子集。而且html是xml的子集,天然具有非常强的数据结构特征,因此,遍历过程中可以很快生成ast,不需要分多步。

今年年初我发布了HyperJSON协议,它是一个基于hyperscript衍生的布局描述协议,具有极小的体积,和完备的布局特性描述数据。而用HyperJSON来描述html具有非常大的优势:体积可以变的特别小,阅读也很方便。因此,我生成的ast是一个基于该协议的对象。

你可以通过下面的代码快速尝试一下这个效果:

<script type="module">
  import { parseHTMLToHyperJSON } from 'https://unpkg.com/abs-html/src/index.js'
  const json = parseHTMLToHyperJSON(`
    <!DOCTYPE html>
    <main>
      <article>
        <h1>Title</h1>
        <p>content</p>
      </article>
    </main>
  `)
  console.log(json)
</script>

得到的对象会是一个阅读起来非常容易的对象。你甚至可以在不同线程,或者客户端与服务端之间,随意的传输这个对象(当然,不推荐,因为字符串性能会更好)。

原本我还想封装几个查询方法,但是由于考虑到暂时没有这个需求,所以就没有开放查找方法。你可以通过HyperJSON协议,方便的通过路径找到一个节点对象。接下来,你可以随意编辑这个对象,但是需要注意,编辑后,它仍然需要符合HyperJSON协议的要求。

从AST回到HTML

利用HyperJSON协议对象,我们可以非常方便的通过遍历生成新的HTML字符串。

import { rebuildHyperJSONToHTML } from 'abs-html'
const html = rebuildHyperJSONToHTML(json)

不过在这里还是有一些坑的,主要是html中有一些强制的自关闭标签,比如<link /> <img />等。这些标签在HyperJSON中没有特意强调,但是我规定,当一个节点没有children部分时,就代表它是一个自关闭标签。例如:

['div', null, ''] // 闭合标签,一定存在children,虽然是一个空字符串
['img'] // 自关闭标签,不存在children,可以存在props

还有一点,为了小HyperJSON的体积,纯文本节点直接用字符串,而非用#text类型节点,例如:

['div', 0, 'content'] // 本来应该写成 ['div', null, ['#text', null, 'content']]

我们每一个设计,都有它独特的地方,有些设计是为了追求完备性,而有些设计则是在理想与现实之间平衡。

Diff两个AST

当我拿到两个html字符串之后,通过parse操作得到两个ast,接下来的事,就是对比这两个纯js对象。市面上有很多diff库,其中我比较喜欢的一个叫deep-diff,原因在于它的diff结果是非常易于阅读的数组形式。但是,我并没有用它来diff两个ast,原因很简单,html的ast是有规律的结构化数据,而非无规律的js对象。把ast当作纯对象对比,会多出很多无用的信息,例如:

path: [3, 4, 1, 'name']
next: 'new name'

实际上它表达的是根节点的第1个child的第2个child的name prop发生变化。虽然用数字作为路径确实节省了一些空间,但是却无法让我们很轻松的阅读,所以,我自己提供了一个diff工具,这个diff工具给出的结果是:

path: div[1]/div[2]
type: 'attribute'
name: 'name'
next: 'new name'

它比用deep-diff对纯js对象对比时多出一些信息,但是阅读起来却更方便。最重要的是,它为patch做准备,因为patch时,直接根据type来决定进行什么操作。

相似算法

在diff时,我需要确认,这个节点是新增的,还是原来就有的(可能发生了一些细微变化)。我想到了一种相似算法(目前还没有在abs-html中使用)。两个对象是否是对同一个HTML节点的描述呢?我主要看它们的相似的,有些特征可以直接排除它们不是同一个节点的描述,比如nodeName、id、data-id不一样,那么这两个对象不可能是对同一个节点的描述。我为不同节点的相似度进行权重分类和分数划分,以节点的属性、属性值的相似度、children的相似度为维度,在每个维度上进行打分,每个维度的权重不同,例如前面的nodeName,因为它具有巨高的权重,所以直接作为特殊情况处理。当两个对象在nodeName或id等一致的情况下,拥有相同的props时,我认为它们具有较高的相似度,在props这个维度上,给出了高分,但是它们的children完全不同,那么在这个维度上,我给出了0分。但是不同维度的权重是不一样的,children不同,很有可能是同一个DOM节点,更换了children而已,因此,它的权重低很多。完成这个打分之后,我们就可以得出,一个对象描述的最有可能是哪一个对象描述的节点,从而在diff的时候,把它们当作一个节点,并给予相同的identifier,这样,它就不会被移除,而只会被移动和更新。

另外,在遍历时,我发现从尾往头遍历真的是一个很不错的方法,特别是在这种有移动或插入的场景下,从末尾开始遍历可以有效的避免遍历过程中再去查找的逻辑,复杂度从O(n2)~O(n3)降到了O(n)。

Path变化

把diff结果存起来之后,形成了一个关于HTML变化的序列。我提供的patchHyerJSON方法基于这一序列,可以重建HTML字符串。这样就可以做到对html的回放。因为保存的是比较小的diff的结果,所以,占用的存储空间比保存html字符串小很多。

纯计算

这一系列的计算都是纯js计算,因此,它可以在worker中运行,我们将当前DOM的outerHTML发送到worker中,由worker中的程序完成parse和diff,再将diff结果发送到服务器保存。在服务器的另外一端,我们读取这些diff结果,并通过其他程序,还原html的变化,从而可以观看当前数据源一端的情况,这可以用在在线教育场景下,授课老师在基于html的编辑器(如codemirror)中撰写代码,学生可以立即在自己的电脑上看到老师的写作过程,并且在条件允许的情况下,我们可以加入协同能力,让学生参与到写作中。而由于这些计算全都在worker中执行,只要机器性能良好,就不会对用户当前操作的页面产生任何性能上的影响。

结语

有了abs-html这个利器之后,我可以做很多事情,之前想到react-worker-dom这个库,我也可以实现了,我可以在worker中使用react-reconciler创建ast,并把diff结果发送给主线程,再利用主线程的patch程序去更新对应的DOM,就可以做到一种新的类似小程序一样的架构。

2021-06-12 108

为价值买单

本文价值1.08RMB