在富文本編輯器中實現 Markdown 流式增量解析算法
在先前我們我們實現了SSE流式輸出的實現，以及基于向量檢索的RAG服務，這些實現都可以算作是AI Infra的范疇。這里我們再來聊一下在SSE流式輸出的基礎上，將Markdown解析和富文本編輯器的渲染結合起來，實現編輯器的增量解析算法，同樣屬于文檔場景下的Infra建設。
概述
在SSE流式輸出的場景下，LLMs模型會逐步輸出Markdown文本，在基本場景下我們只需要實現DOM的渲染即可。然而，在富文本編輯器的場景下，這件事就變得復雜了起來，因為編輯器通常都是自行維護一套數據結構，并不可以直接接受DOM結構，再疊加性能問題就需要考慮到下面幾點:
- 流式: 流式意味著我們需要處理不完整的
Markdown文本，在不完整的情況下語法會出現問題，因此需要支持已渲染內容的重建。 - 增量: 增量意味著我們不需要每次都進行全量渲染，已經穩定的內容實際上不需要再次解析，而是只需要在已有內容的基礎上進行增量更新。
- 富文本解析: 富文本解析意味著我們需要完整地對應到
Md的解析情況，無論是流式處理還是增量解析都需要在編輯器結構基礎上對等實現。
當然，即使是在基本場景下的DOM渲染，也會涉及到很多邊界情況的處理，例如若是每次都是SSE輸出Md時都進行全量渲染的性能問題、以及類似圖片節點重渲染可能存在的重新加載問題等。因此，這里的增量解析算法流程，即使是對于基本場景也是很值得參考的。
并且，還有更復雜的場景，例如在SSE流式輸出的過程中，用戶總是會存在臨時的不完整的Md文本，在完整輸出Md文本之前，就會存在不符合規范的Md解析，或者是錯誤地匹配到另一種Md語法的情況。這些情況都需要額外的算法處理，實現一些額外的語法修復方案。
<img src="http://
<img src="http://example.com/
<img src="http://example.com/image.png" alt=
此外，諸如渲染的語法擴展、自定義組件等等，也會涉及到額外的語法處理，關于自定義解析渲染的實現可以參考react-markdown。這其實是是一個很龐大的管道實現，同樣也會是很好的自定義處理AST并渲染的案例，remark也是非常豐富的生態系統，給予了關于Md解析的各種實現。
markdown -> remark + mdast -> remark plugins + mdast -> remark-rehype + hast -> rehype plugins + hast-> components + ->react elements
不過在這里我們并不展開討論這些自定義語法解析的內容，而是主要聚焦在基本的Md語法解析和增量渲染上，但是在解析的過程中我們還是會涉及到針對語法錯誤匹配的相關問題處理。文中的相關實現可以參考 BlockKit 以及 StreamDelta 中。
Markdown增量解析
首先我們來實現Markdown的流式增量解析，能夠實現增量解析的重要的基礎是，Md輸出的后續內容格式通常不會影響先前的格式，即我們可以歸檔已經穩定的內容。因此我們可以設計一套數據處理方案，在解析的過程中需要遵循的整體大原則:
- 非全量解析
Markdown, 基于流漸進式分割結構處理數據。 - 基于
Lexer解析的結構, 雙指針綁定Delta的增量變更。
詞法解析
首先我們需要一個詞法解析器將Md解析成Token流，或者是需要一個語法解析器將Md解析成AST。由于我們的數據結構是扁平化的，標準詞法解析的扁平Token流對我們的二次解析并非難事，而若是完全嵌套結構的數據結構，語法解析生成AST的解析方案對則可能更加方便。
當前的主流解析器有比較多的相關實現，marked提供了lexer方法以及marked.Lexer作為解析器，remark作為unified龐大生態系統的一部分，也提供了mdast-util-from-markdown獨立的解析器，markdown-it同樣也提供了parse方法以及parseInline作為解析器。
在這里我們選擇了marked作為解析器，主要是由于marked比較簡單且易于理解。remark系列的生態系統過于龐大，但是作為標準的AST解析是非常不錯的選擇。markdown-it的Token解析器稍微復雜一些，其不直接嵌套而是使用heading_open等類型標簽進行數據處理。
從名字上也可以看出marked提供的lexer是偏向于詞法解析的，但是其也并非完全純粹的詞法解析器。因為輸出的結構也是存在嵌套存在嵌套的結構，當然其也并非比較標準的AST結構，這里更像是偏向Token流的混合結構實現。一段Md文本的解析結構如下所示:
// marked.lexer("> use marked")
{
"type": "blockquote",
"raw": "> use marked",
"tokens": [
{
"type": "paragraph",
"raw": "use marked",
"text": "use marked",
"tokens": [{ "type": "text", "raw": "use marked", "text": "use marked", "escaped": false }]
}
],
"text": "use marked"
}
歸檔索引
那么在解析的過程中，我們需要維護幾個變量來持有當前解析的狀態。content維護了當前正在解析的片段，接受流式的數據需要不斷拿到新片段來組裝，indexIds以索引值作為穩定的鍵用來映射id值，archiveLexerIndex則維護了已經歸檔的主級Tokens節點索引值。
/** 正在解析的內容 */
protected content: string;
/** 索引冪等的記錄 */
public indexIds: O.Map<O.Map<string>>;
/** 歸檔的主級節點索引值 */
public archiveLexerIndex: number;
當執行追加內容時，我們直接將content與本次追加的text內容合并解析，然后借助marked詞法解析就可以得到Token Tree，在調度的主框架中，我們只解析主級節點。只解析主級節點可以盡可能簡化我們需要處理的數據，而子級節點可以再建立二級擴展索引處理。
const tree = marked.lexer(this.content);
const archiveLexerIndex = this.archiveLexerIndex;
// 只迭代 root 的首層子節點
for (let i = 0; i < tree.length; i++) {
// ...
}
接著我們需要將歸檔的位置處理一下，歸檔就意味著我們認為該Token將不會再處理了，因此持有的索引index就自增。而block.raw就是該Token就是解析的原始內容，這也是使用marked的簡單之處，否則還需要自行根據索引解析一下，文本歸檔的部分我們直接移除即可。
/**
* 歸檔部分內容
* @returns archived 字符長度
*/
public archive(block: Token) {
this.archiveLexerIndex++;
const len = block.raw.length;
this.content = this.content.slice(len);
return len;
}
在處理好歸檔索引之后，我們就可以在循環中具體處理這歸檔的部分。這里的策略非常簡單，如果循環時某個節點存在前個節點，就可以歸檔上一個節點了。當然這里的歸檔并沒有那么理想，特別是存在列表、表格等節點時，這里就需要特殊地處理，我們后續會討論這個問題。
而后續就是解析當前的Token了，這部分是需要適配編輯器本身數據結構的實現。在當前編輯器中，我們認為Token作為主級節點存在，然而其本身并不能夠完整對應到編輯器行的狀態，例如list節點會存在嵌套的list_item節點，而我們的結構是純扁平化的行結構，因此需要獨立適配處理。
const prev = tree[i - 1];
const child = tree[i];
// 首層子節點存在第二級時，歸檔上一個節點
// 此外諸如表格等節點可以正則匹配來避免過早歸檔
if (prev && child) {
this.archive(prev);
}
const section = parseLexerToken(child, {
depth: 0,
mc: this,
parent: null,
index: archiveLexerIndex + i,
});
將Token轉換到Delta片段的過程我們以heading行格式以及bold行內格式為例，簡單地說明一下解析過程。對于行節點而言，執行順序很重要，需要先遞歸地處理所有行內節點，然后再執行行節點的處理，而無論是行節點還是行內，都是封裝好的原地修改的方式來修改屬性值。
switch (token.type) {
case "heading": {
const tokens = token.tokens || [];
const delta = parseChildTokens(tokens, { ...options, depth: depth + 1, parent: token });
applyLineMarks(delta, { heading: "h" + token.depth });
return delta;
}
case "strong": {
const tokens = token.tokens || [];
const delta = parseChildTokens(tokens, { ...options, depth: depth, parent: token });
applyMarks(delta, { bold: "true" });
return delta;
}
}
此外，如果需要再繼續解析HTML節點的話，則需要引入parse5/htmlparse2等獨立解析HTML片段，不過parse5的解析結果會嚴格處理DOM的嵌套結構，因此用htmlparse2來處理HTML片段更合適。當然還有一種常見的解析方案，將所有數據處理為HTML，再行解析HTML-AST。
語法修復
在上述的實現中，我們已經能夠實現針對于Markdown部分的增量解析了。雖然這個策略多數情況下是沒有什么問題的，但是在流式輸出的過程中，會出現兩個問題，一是流式輸入過程中會存在臨態節點，會導致錯誤的歸檔，例如縮進的列表，二是錯誤的語法匹配，例如無序列表縮進時的-解析為標題。
因此我們需要處理這些Case，當然這里目標主要是針對于語法的錯誤匹配修復，而并非補全不完整的語法。首先我們來看一下列表的縮進問題，若是直接使用上述的策略，那么在下面這個例子中，就會導致第一行1節點被歸檔，然后導致1.1節點沒有縮進格式，因為此時不存在嵌套的list token。
- 無序列表項1
- 無序列表項1.1
先來分析一下這個問題所在，流式的輸出過程中，1.1行會有一個臨態 也就是縮進的前置三個空格的狀態，而其在輸出到-字符之前，這個Token的解析格式是下面的內容。則按照上述策略，先前的Token存在且當前的Token存在，則前置的Token進行歸檔。
[{ type: "list", raw: "1. xxx", ordered: true, start: 1, loose: false, items: [ /* ... */ ]},
{ type:"space", raw:"\n \n" }]
因此在歸檔之后，就僅剩下1.1的節點需要解析了，而由于前一行的1節點已經被歸檔，那么此時1.1就是新的list以及list_item節點了。因為不存在嵌套節點，所以其雖然能夠正常解析內容，但是就不存在縮進的格式了。
{ type:"list", raw:" -\n", ordered: false, start: "", loose: false, items: [ /* ... */ ]}
因此，針對這個問題，我們需要對解析的Token進行一些額外的處理。在上述的這個Case中，我們可以認為是由于space節點的存在，導致了前一個list節點被過早歸檔了，因此我們可以認為space節點是臨時狀態，不應該導致前一個節點的歸檔。
export const normalizeTokenTree = (tree: Token[]) => {
const copied = [...tree];
if (!copied.length) return copied;
const last = copied[copied.length - 1];
// 若是需要等待后續的數據處理, 就移除最后一個節點
// Case1: 出現 space 節點可能會存在等待輸入的情況, 例如上述的 list
// 1. xxx
// [前方三個空格會出現 space 導致歸檔]
if (last.type === "space") {
copied.pop();
}
return copied;
};
而針對于第二個問題，同樣會表現的很明顯，由于格式的錯誤匹配會導致樣式，而這個狀態同樣也是臨態，因此在繼續解析的過程中，會匹配到正確的結構，在這個過程中就會導致明顯的樣式突變，在輸出的過程中非常明顯。例如下面的這個例子中，本應該認為是無序列表的-，卻被錯誤地解析為標題。
- xxx
-
({
type: "list",
items: [
{
type: "list_item",
tokens: [ { type: "heading", tokens: [ /* ...*/ ] } ],
},
],
});
實際上這個格式并沒有什么問題，因為這本身就是規范中的格式，只不過通過---設置標題的格式在平時并不常用。我們自然也可以去查閱一下規范中的格式定義，在Setext headings部分中可以看到相關的定義:
The setext heading underline can be preceded by up to three spaces of indentation, and may have trailing spaces or tabs - Example 86
Foo
----
A list item can contain a heading - Example 300
- # Foo
- Bar
---
baz
因此，處理這個問題的方法也很簡單，即我們避免這個臨時狀態的出現，這也是我們處理這兩個問題所要遵循的原則。因此我們可以通過正則來匹配這個臨態，若是匹配成功則將該行移除掉，等待后續的正確格式出現。
export const normalizeFragment = (md: string) => {
// Case 1: 在縮進的無序列表尾部出現單個 - 時, 需要避免被解析為標題
// - xxx
// -
const lines = md.split("\n");
const lastLine = lines[lines.length - 1];
if (lastLine && /^[ ]{2,}-[ \n]?$/.test(lastLine)) { // $
lines.pop();
}
return lines.join("\n");
};
編輯器流式渲染
在Markdown的增量解析實現之后，我們還需要將解析的結果映射到編輯器本身的數據結構中，這里的主體流程則需要配合Md解析流程的實現。同樣的，我們也遵循上述Md解析的流程，同樣是實現歸檔索引，以及當前數據的解析數據重建等方法。
流式解析
在流式解析的過程中同樣需要幾個變量，首先是正在解析的Token Delta，這部分是需要保證獨立頂級的Token節點，這也是匹配Md解析的主級節點。其次是已經歸檔的Delta長度，與Md解析不同的是其索引為Token數組索引，此時是Delta的文本長度索引。
/** 歸檔的索引 */
public archiveIndex: number;
/** 正在處理的 token-delta */
public current: Delta | null;
在追加內容時，我們需要將最新的Token應用到編輯器上，但是由于編輯器此時已經應用了編輯器的內容，編輯器應用的是變更內容，因此則需要計算出已經應用的內容和目標的內容差異，才可以直接將其應用到編輯器本身。
/**
* 追加 delta
* @returns 變更的差異
*/
public compose(delta: Delta) {
const copied = new Delta(cloneOps(delta.ops));
if (!this.current) {
this.current = copied;
return delta;
}
// 這里也可以避免 diff, 直接構造刪除原始內容再添加新內容即可
// 由于本身會歸檔內容, 無論是比較差異還是刪除/新增都不會太耗費性能
const diff = this.current.diff(copied);
this.current = copied;
return diff;
}
歸檔的實現則比較簡單，主要是將當前的Delta歸檔掉，并且更新歸檔的索引。由于此處理論上僅會存在insert操作，因此可以直接調用length方法來得到此時的Delta長度，實際上這里還是應該檢查一下操作類型。
/**
* 歸檔部分內容
* @returns archived 的 delta 長度
*/
public archive() {
if (this.current) {
// 此處理論上只有 insert, 因此無需考慮 delete 的指針問題
const len = this.current.length();
this.archiveIndex = this.archiveIndex + len;
this.current = null;
return len;
}
return 0;
}
接下來我們就需要將Delta的組合流程結合到Md的解析流程當中了。首先我們需要取得當前已經歸檔的索引，這部分需要轉換為retain以對齊索引。然后在循環歸檔的時候，需要處理繼續處理索引信息，主要是因為后續的處理是merge diff, 此時的長度并非是dc的長度。
而最后的compose方法則是將剩余解析的Token轉換的Delta進行合并，最終返回的delta就是本次追加內容的變更差異，也就是先前提到的diff方法。最后的merge方法則是將變更合并先前的retain指針，以此來保證索引的正確。
// 因為 delta 首個值是 retain, 這里同樣需要對齊其長度表達
let archiveLength = this.dc.archiveIndex;
for (let i = 0; i < tree.length; i++) {
if (prev && child) {
this.archive(prev);
archiveLength = archiveLength + this.dc.archive();
const deltaLength = getDeltaPointerPosition(delta);
// 若歸檔長度大于當前 delta 長度, 則需要移動指針
if (archiveLength - deltaLength > 0) {
delta.push({ retain: archiveLength - deltaLength });
}
}
// ...
const diff = this.dc.compose(section);
delta.merge(diff);
}
實際上這部分實現是非常需要測試來保證穩定性的，特別是在不斷處理各種Case中，需要避免之前測試過的內容解析出現問題，因此維持一個測試集是非常有必要的，在單元測試的過程中我們主要專注于下面幾種類型的輸入以及輸出:
- 首先是完整的
Md文本輸入，這部分主要測試的是將所有的Token解析的正確性。 - 其次就是文本內容的流式輸入，這部分測試就可以完全使用單個字符的流渲染輸出即可。
- 還有就是隨機的字符流式輸入，這種情況下不容易維持穩定的單元測試的輸出，此時需要測試最終的輸出。
穩定鍵值
雖然此時我們的編輯器當前并未實現塊級的結構嵌套，但是塊級結構通常是不可避免的，例如代碼塊、表格等結構的實現。而無論是單純的塊結構嵌套，還是Blocks模式下的結構實現，通常都是存在id值來標識唯一的塊級結構。
那么在流式輸出的過程中，就很容易出現id值被重建的問題，特別是在表格種復雜的結構中，在僅實現主級節點解析歸檔的情況下，每個單元格都可能會被重新解析而生成新的id值。因此我們需要在解析的過程中，維持一個id值的映射表，就比較重要，也可以避免重復的渲染帶來性能問題。
因此維持id映射表就需要實現一個穩定的鍵值，若是沒有穩定的鍵值，那么在解析的過程中就無法確定上次解析的id和當前解析的id應該是一致的。那么在這里我們使用index以及depth的組合值作為索引，以此來映射復雜結構的id值，這也就是之前的indexIds作用。
const key = `depth:${depth}-index:${index}`;
const id = (mc.indexIds[key] && mc.indexIds[key].id) || generateId();
const delta = parseChildTokens(tokens, { ...options, depth: depth + 1, parent: token });
const block = new Block({ id, delta });
// ...
編輯模式
通常來說，我們一般是不需要在流式輸出的過程中允許用戶進行編輯的，因此只需要在流式輸出的過程中將readonly設置為true，等到流式輸出完成之后再將readonly設置為false即可。然而，若是用戶需要在流式輸出的過程中進行編輯，這個問題就變得復雜起來。
回到編輯模式這個問題本身，由于存在多種輸入模式可能導致的數據沖突，解決這個問題通常都是使用OT算法來解決的。若是編輯器結構是能夠支持CRDT數據模式的話，這個問題應該會更加簡單，畢竟理論上而言其處理的編輯位置是相對的，而我們需要處理索引沖突本質是由于絕對位置引起的。
OT的實現中最重要的就是transform方法，我們可以先看看transform所代表的意義。如果是在協同中的話，b'=a.t(b)的意思是，假設a和b都是從相同的draft分支出來的，那么b'就是假設a已經應用了，此時b需要在a的基礎上變換出b'才能直接應用。
而我們也可以換種理解方式，即transform解決了a操作對b操作造成的影響。那么類似于History模塊中undoable的實現，transform同樣可以來解決單機客戶端Opa以及Opb操作帶來的影響，那么自然也可以解決流式輸出以及用戶輸入本身相互的數據影響。
由于我們已經記錄了archiveLength，在archiveLength內的文檔內容變更我們認為是已經穩定的結構，而archiveLength外的文檔內容我們認為是臨時的狀態。因此這里的OT則變得簡單了很多，我們需要做的計算拆分為了兩部分:
- 對于
archiveLength內的變更，對于insert操作我們就將索引值相加，而對于delete操作我們就將索引值相減。 - 對于
archiveLength外的變更，我們則需要根據索引構造一個retain操作，然后將用戶變更的changes組合到當前的Delta中。
總結
在本文中我們實現了Md的詞法解析，在此基礎上處理了增量的Token歸檔以及增量處理，在Md整個流程的基礎上結合了，編輯器數據結構本身的增量渲染。并且還處理了具體的語法匹配問題，以及編輯器細節id索引和編輯模式。在這些內容的基礎上，實現了流式Markdown增量富文本解析算法。
由于編輯器數據結構通常都是各自維護的一套模式，因此在這里我們更偏向于業務代碼實現，而并非通用的解析模式，在不同的業務場景下都需要額外的適配。不過在Md解析的流程上抽象出來更底層的實現是比較通用的模式，這部分確實是可以提供通用算法出來的。
實際上到這里，還需要考慮一個問題，若是不需要實現流式輸出時編輯，我們也完全可以實現一套流式輸出的純HTML渲染模式，等待流式輸出完成之后再替換為編輯器。這當然是個可行的方案，并且還可以避免很多復雜的實現，只不過這樣實現成本就轉移到了需要額外做一套純渲染的樣式，以保證用戶體驗。
浙公網安備 33010602011771號