­

Quil-delta-enhanced 簡介

 

Quill 是一款時下非常熱門的富文本編輯器，它擁有非常強大的擴展能力，可以讓開發者根據自己的需要編寫插件，使編輯器支援的內容類型更加豐富。它之所以能夠擁有這麼強大的擴展能力，一方面是因為它的架構和 api 設計從一開始就充分考慮了擴展的需求，另一方面就是它底層採用了一種表達能力很強的的數據存儲模型—— quill-delta。

quill-delta 是一個 ot 演算法的實現，所謂 ot 演算法是指 Operational Transformation，這個演算法主要是用來解決數據協同編輯的問題，但因為演算法本身並不針對特定類型的數據格式，所以其適應性很強，因此基於此演算法實現的 quill-delta 表達能力也很不錯。關於 ot 演算法如果要展開來講內容太多了，本文不打算涉及，大家感興趣可以去搜索一下。

但是，quill-delta 可能更多的還是考慮簡單文檔類型數據的使用場景，所以它的數據基本上都是線性的，對樹狀結構的數據支援能力很弱，這也給他帶來了很多使用場景上的限制。為了解決這個問題，我對 quill-delta 做了一些改造和擴展，於是就有了 quill-delta-enhanced。本文將介紹 quill-delta-enhanced 的設計思路，以及實現過程中面臨的問題及其解決方案。

quill-delta 的問題

quill-delta 的優點是簡單易於理解，花上幾分鐘看看 api 文檔你就能理解它的工作方式。但簡單也有簡單的問題，就是表達能力不夠強，比如，如何表示一個表格？在文檔中嵌入表格其實也算是非常常見的需求，一個表格可以有若干行，每行又可以有若干個單元格，單元格還可以合併，每個單元格裡面的內容也會非常不一樣，甚至有的編輯器還提供了表格嵌套功能，就是一個表格中嵌套另一個表格。對於這樣複雜嵌套的數據，quill-dlta 就顯得有些力不從心了，所以 Quill 一直沒有支援插入表格的操作。

如何增強 quill-delta 的表達能力

那麼如何提升 quill-delta 的表達能力呢？我想到的一個思路是，嵌套 delta —— 既然表格的內容在直觀上是嵌套的，那麼為什麼不把 delta 也設計成可以嵌套的樣子呢？

事實上 quill-delta 本身並不僅僅支援 string 類型的數據，還支援 number 類型和 object 類型的數據，比如：

// string
new Delta().insert('hello world')
// number
new Delta().insert(3, {attr: 'number attributes'})
// object
new Delta().insert({name: 'tiger'})

很明顯，既然 quill-delta 支援 object 類型的數據，就肯定也可以支援插入 delta 類型的數據，畢竟 delta 本身就是一種 object，所以，我們可以插入這樣的數據：

// embed delta
new Delta().insert(new Delta().insert('embed'))

當然，這裡面還有些細節需要處理，比如 compose、invert 和 transform 方法都需要一些變化才能適應嵌入 delta 的做法，具體內容大家可以看源程式碼。

嵌套 delta 如何 diff

在 quill-delta 中 diff 方法可以非常快速地比較兩條 delta 之間的差異，比如：

var a = new Delta().insert('hello world')
var b = new Delta().insert('hi word')

a.diff(b)
// new Delta().retain(1).insert('i').delete(4).retain(4).delete(1)

如果你看過 quill-delta 的程式碼，就知道 quill-delta 是用了一個叫做 fast-diff 的庫來實現 diff 演算法的。fast-diff 這個庫只能用來處理 string 類型數據的 diff，那 quill-delta 是怎麼用它來處理同時包含 string、number、object 三種類型的數據呢？還是看源碼：

const NULL_CHARACTER = String.fromCharCode(0); // Placeholder char for embed in diff()

diff(other: Delta, cursor ?: number | diff.CursorInfo): Delta {
  // ....

  const strings = [this, other].map(delta => {
    return delta
      .map(op => {
        if (op.insert != null) {
          return typeof op.insert === 'string' ? op.insert : NULL_CHARACTER;
        }
        const prep = delta === other ? 'on' : 'with';
        throw new Error('diff() called ' + prep + ' non-document');
      })
      .join('');
  });

  // ....
}

quill-delta 在調用 fast-diff 之前把所有的 insert 操作全部轉成了字元串，對於插入的 number 類型的數據和 object 類型的數據，都轉成了一個特殊字元，然後和 string 類型的數據拼在一起，就成了一個大字元串，然後給 fast-diff 處理。但是，這裡有一個很明顯的問題，如果兩個 delta 中分別插入了兩個不同的 object，由於這裡 diff 的時候全都轉成同一個特殊字元了，那麼 fast-diff 就無法找出這兩個 object 的不同，所以 quill-delta 在拿到 fast-diff 的處理結果之後又做了進一步處理：

const diffResult = diff(strings[0], strings[1], cursor);

diffResult.forEach(component => {
  //....
  switch (component[0]) {
    // ....
    case diff.EQUAL:
      // ....
      if (equal(thisOp.insert, otherOp.insert)) {
        retDelta.retain(
          opLength,
          AttributeMap.diff(thisOp.attributes, otherOp.attributes),
        );
      } else {
        retDelta.push(otherOp).delete(opLength);
      }
      break;
  }
  // ....
})

如上所示，對於 fast-diff 認為是相同的內容，quill-delta 又做了一次 equal 操作來確認兩條內容是不是真的相同，如果是真的相同就 retain，如果不是就粗暴的刪除之前的內容插入新的內容。這樣顯然不能得到一個相對合理的 diff 結果，比如：

var a = new Delta().insert(3)
var b = new Delta().insert(2).insert(3)

a.diff(b)
// new Delta().insert(2).delete(1).insert(3)

對於 number 類型的數據來說，直接刪除原來的內容在插入新的內容似乎影響也不太大，但如果插入的是一個複雜的 object 數據或者 delta，這種操作就顯得太低效了，所以在 delta 支援嵌套後，必須對 diff 演算法做出改進。

改進 quill-delta 的 diff 演算法

delta 中插入的如果都是 string 類型，那麼整個 delta 可以近似看做是一個線性的數據結構，可當我們讓 delta 可以嵌套另一個 delta 的時候，delta 就會變成一個樹形結構，這會給我們的 diff 演算法帶來非常大的挑戰。

傳統的 tree diff 演算法時間複雜度是 O(n^3)，就是說，對於一個 1000 個節點的樹，diff 一次需要進行 10 億輪運算，這樣的開銷顯然是不可接受的。但這個問題讓我想到了一個非常非常非常著名的庫：react。react 中用對 virtual dom 進行 diff，來生成針對 dom 的最小操作，達到盡量不操作 dom 的目的從而提升性能。我們知道 virtual dom 其實也是一種複雜的樹結構數據，這種樹的複雜程度一般要比 delta 的結構更複雜，那麼 react 是怎麼實現高效 diff 的呢？大家可以自行搜索一下，網上講解 react 中 diff 演算法的文章多如牛毛。我這裡只提一下 react 對 diff 演算法的優化其實是一種策略優化，就是通過限制場景來優化性能，主要是四點：分級比較、類型判斷、 shouldComponentUpdate 優化、key 優化。通過這四點優化，react 將 tree diff 的時間複雜度從 O(n^3) 降低到了 O(n)，效果非常顯著。那麼這四個優化策略是不是可以用在 delta 的 diff 演算法上呢？我覺得至少其中兩點是可以的。

首先，分級比較。就是說我們認為把一顆子樹從一個節點下挪到另外一個節點下，這並不是一個常見的操作，diff 僅僅在同級別的元素之間進行，而不去考慮子樹在節點之間挪動的場景，這樣就大大簡化了計算的複雜程度。舉個例子：

var a = new Delta()
  .insert(new Delta().insert('a').insert(1))
  .insert(new Delta().insert('b'))
var b = new Delta()
  .insert(new Delta().insert('a'))
  .insert(new Delta().insert('b').insert(1))

這兩條 delta 在做 diff 的時候，我們並不會去看 b 中的第二個子 delta 下的 insert(1) 操作是不是在 a 中的某個子 delta 中存在過，而僅僅將 b 中的第一、二兩條子 delta 分別和 a 中的第一、二兩條子 delta 做內容上的對比。

其次，key 優化。react 中對於同級別且同類型的元素會用一個該層級下唯一的 key 來標記元素的唯一性，通過這個 key 來判斷哪個元素是新增的，哪個元素是之前就存在的。比如：

var a = new Delta()
  .insert(new Delta().insert('a'))
var b = new Delta()
  .insert(new Delta().insert('b'))
  .insert(new Delta().insert('a'))

上面這兩條 delta 如果不用 key 來標記唯一性的話，很可能 diff 出來的結果會是這樣：

new Delta()
  .retain(new Delta().insert('b').delete(1))
  .insert(new Delta().insert('a'))

因為沒有 key 來標記 a 中已經存在的子 delta，在 diff 的時候，程式只能拿 b 中的第一條子 delta 和 a 中的子 delta 對比，於是得到了結果中的 retain 操作。而如果我們能給子 delta 添加一個唯一的 key 來標記它，diff 的時候就可以通過 key 很容易地判斷出哪些 delta 是之前就存在的。從而得到正確的結果：

new Delta()
  .insert(new Delta().insert('b'))

修改思路

談了優化策略，我們再來講講具體如何實現。還是只講思路，具體修改的程式碼大家自己看 git 上的提交記錄吧。

首先，fast-diff 是一個非常好用的 diff 演算法庫，我希望能盡量復用他，但是子 delta 添加 key 之後，顯然就沒法像之前那樣把 delta 里的 op 都轉成純 string 類型的數據了，這就要求 fast-diff 能支援混合類型的 diff，比如

['abc', 1, 'defgh', 2, 'xyz']

上面的數據代表了一條 delta ，其中有 5 段內容分別是 abc、一條 key 為 1 的子 delta、defgh、一條 key 為 2 的子 delta，最後是 xyz。好在對 fast-diff 的修改其實並沒有很複雜，大家可以想像一下，fast-diff 雖然是用來處理 string 類型的數據的，但其實 string 類型和 array 是非常類似的，我們可以把 string 想像成一個 char 類型的 array（一般C 語言裡面就是這麼來存儲字元串的），所以修改起來並不算很複雜，大家可以參考這個提交：enhance diff to support diff sequence of characters and numbers

在 fast-diff 支援了這種字元串和數字類型數據混標的 array 之後，quill-delta 自身的 diff 邏輯修改就相對簡單了，主要是要給 insert 介面添加 number 類型的 key 參數，以及處理 fast-diff 的結果的時候需要一點點特殊處理，參考這個提交：Improve diff algorithm, support efficient diff of nested delta

其他

quill-delta-enhanced 對還做了一些其他的改動，比如 insert 和 retain 操作支援的數據類型有稍作修改，原有的 number 類型的數據的含義也有些許變化，具體變化的內容大家可以在程式碼倉庫的 README 文檔中查看。

總結

quill-delta 是一個非常簡潔實用的 ot 演算法庫，對於簡單文檔內容來說，他的表達能力已經很不錯了，不過加入了嵌套 delta 的能力之後，其表達能力進一步增強。雖然嵌套 delta 讓有些邏輯的複雜度大大增加，但其實冷靜分析還是可以找到一些性價比很高的解決辦法的。

 

如需轉載，請註明轉自：//www.cnblogs.com/silenttiger/p/12704594.html

 

歡迎關注我的微信公眾號：老虎的小窩

 

 

Tags:

VirMach 便宜 VPS

QNews

QNews