# operational-transformation 演算法原始碼分析 Operational Transformation演算法解決的問題是如何merge基于相同的狀態產生的不同的操作序列， 首先ot演算法解決了什么問題呢？我們來先看看產生的問題 ## 舉個栗子 服務器內容是abc，用戶A輸入xabc，用戶B輸入ab，這個個時候恰好發給服務器，那么，服務應該要怎么做？其實我們最終想要的結果是xab， ### 解決方案一：丟了丟了 這可能是最簡單粗暴的方法了，我發現有沖突，就告訴用戶，主子，咱這里有沖突了，臣妾解決不了啊，但是顯然這會經常出現，然后主子就把你打入冷宮了，然后按照優先順序排列需要丟失了A用戶輸入的x，最后變成了ab ### 解決方案二：鎖 有些小伙伴想到，上面出現問題，還不是因為大家編輯了都立即應用了，我們編輯后不立即應用不就好了，而且歷史告訴我們，有沖突加鎖應該可以解決， 加鎖問題是這個時候a在輸入，b不能編輯，那協同就沒多大意義了， ### OT演算法 OT演算法全名叫**Operation Transformation**，你看從名字就對應了上面我說的轉變演算法， 那ot演算法是如何做到a，b用戶文本都不丟失的呢？ 他是這樣做的，如果當有兩個版本的時候，他A用戶先和服務器做對比，然后通過演算法知道x是插入的，abc是保留的，然B用戶也和原來服務器內容做對比，知道了c是被洗掉的，ab是保留的，然后他在通過 xabc和ac對比，知道x是新增的，ab是保留的，c是被洗掉的，這樣一合并就得到了xabc 如一下兩個圖 
那來看看我們的原始碼，原始碼一共分為這幾個檔案 tests.js，apply.js，client.js，errors.js，messages.js，operations.js，ot.js，xform.js 那么我們來顯看看這幾個檔案功能 ### tests.js測驗用例檔案 ``` /* * @Date: 2011-05-02 09:43:09 * @Author: Yao guan shou * @LastEditors: Yao guan shou * @LastEditTime: 2022-03-21 16:45:39 * @FilePath: /operational-transformation/tests/tests.js * @Description: */ (function (global, factory) { typeof exports === "object" && typeof module !== "undefined" ? (module.exports = factory( require("../operations"), require("../xform"), require("../apply") )) : typeof define === "function" && define.amd ? define("tests", ["operations", "xform", "apply"], factory) : (global.tests = factory(global.operations, global.xform, global.apply)); })(this, function (ops, xform, apply) { "use strict"; var numTests = 0; var failed = 0; function test( original, // 舊的文本，服務器文本 a, // 文本a b, // 文本b expected // 合并后的預期文本 ) { var operationsA = ops.operation( original, // 舊的文本，服務器文本 a // 新的文本 ); // return var operationsB = ops.operation( original, // 舊的文本，服務器文本 b // 新的文本 ); // ot 演算法函式 xform(operationsA, operationsB, function (ap, bp) { numTests++; // try { console.log(original + " -< (" + a + ", " + b + ") >- " + expected); var docA = apply(operationsA, original); var finalA = apply(bp, docA); console.log(" " + original + " -> " + docA + " -> " + finalA); if (finalA !== expected) { throw new Error(finalA + " !== " + expected); } var docB = apply(operationsB, original); var finalB = apply(ap, docB); console.log(" " + original + " -> " + docB + " -> " + finalB); if (finalB !== expected) { throw new Error(finalB + " !== " + expected); } // } catch (e) { // failed++; // console.log(" ERROR: " + e.message); // } }); } test("abc", "xabc", "ab", "xab"); // // test("nick", "Nick", "nick is cool", "Nick is cool"); // // test("sudo", "sumo", "suo", "sumo"); // // test("hello", "Hello", "Hello", "Hello"); // // test("care", "are", "are", "are"); // // test("air", "fair", "lair", "flair"); // // console.log(numTests - failed + " / " + numTests + " tests passed."); return test; }); ``` ## operations.operation() 通過動態規劃演算法 獲取到 字串是 保留還是新增還是洗掉 首先我們看到他是先呼叫 operations.operation() 的方法傳入服務器的文本和用戶A，與B文本，然后創建一個物件我們來看看這里做了什么， ``` // 通過動態規劃演算法 獲取到 字串是 保留還是新增還是洗掉 operation: function ( s, // 舊的文本，服務器文本 t // 新的文本 ) { var n = s.length, //舊的文本，服務器文本字串的長度 m = t.length, // 新的文本字串的長度 i, j, // 回傳鏈表 edits = makeEditsTable( s, // 舊的文本，服務器文本 t // 新的文本 ); // console.log("edits makeEditsTable=======", edits); // console.log("m=======", m); // console.log("n=======", n); // 兩層嵌套 時間復雜度為 o(n^2) 空間復雜度為 o(2*long) // 新的"abc" for (i = 1; i <= m; i += 1) { // 舊的字串"xabc" for (j = 1; j <= n; j += 1) { // console.log('i=',i) // console.log('j=',j) //選擇單元格對比上面和左邊對比算出下一個table格的資料，這里用到的類似動態規劃演算法 chooseCell( edits, // 鏈表 i, // 新的字串索引 j, // 舊的字串索引 j先 開始增長 再到 i 增長 所以開始 1,1->1,2->1,3 function (direction, prevEdits) { // 在插入新的字串 switch (direction) { case "left": // 插入 put(edits, i, j, cons(insert(t.charAt(i - 1)), prevEdits)); console.log("edits1========", edits); debugger; break; case "up": // 洗掉 debugger; put(edits, i, j, cons(del(s.charAt(j - 1)), prevEdits)); break; case "diagonal": // 洗掉或者保留 // 判斷新的文本和舊的文本是否相同 if ( s.charAt(j - 1) === // 舊的字串"abc" t.charAt(i - 1) // 新的"xabc" ) { console.log("j - 1=", j - 1); console.log("i - 1=", i - 1); console.log("s=", s, "t=", t); // 如果是相同則保留 put( edits, i, j, cons( retain(1), //保留字串比如 xabc , abc 第一個a r1為 2,1 prevEdits ) ); console.log("edits==========", edits); debugger; } else { debugger; // 如果不相同則記錄需要洗掉 put( // 鏈表 edits, i, j, cons( insert(t.charAt(i - 1)), // 插入新的文本 cons( // del(s.charAt(j - 1)), // 洗掉舊的文本 prevEdits ) ) ); } break; default: throw new TypeError("Unknown direction."); } } ); } } console.log("edits=================", JSON.stringify(edits)); console.log("m========", m); console.log("n========", n); console.log( "get(edits, m, n).toArray().reverse()========", get(edits, m, n).toArray().reverse() ); return get(edits, m, n).toArray().reverse(); // 翻轉 }, ``` 我們看到operation 需要兩個引數 第一個是舊的文本，就是服務器文本，第二個引數是用戶輸入文本，然后他呼叫makeEditsTable方法，該方法就是把文本生成一個鏈表結構，那么他資料結構是怎么樣子呢？ 假如我們的測驗用例是 ``` var operationsA = ops.operation( "abc", // 舊的文本，服務器文本 "xabc" // 新的文本 ); ``` 首先他會列舉新的字串 ``` // 回圈新的文本字串的長度 for (i = 1; i <= m; i += 1) { console.log("insert(t.charAt(i - 1)=", insert(t.charAt(i - 1))); console.log("get(table, i - 1, 0)=", get(table, i - 1, 0)); console.log( "cons=", cons( // return "i" + chars; 從第0個開始 insert(t.charAt(i - 1)), //回傳 return "i" + chars; 從第0個開始 get(table, i - 1, 0) // 獲取上一個table快取的資料 ) ); // 添加到把物件edits添加到table物件中 put( table, // 把字串快取成物件陣列 i, // 索引 0, cons( // return "i" + chars; 從第0個開始 insert(t.charAt(i - 1)), //回傳 return "i" + chars; 從第0個開始 get(table, i - 1, 0) // 獲取上一個table快取的資料 ) ); } ``` 然后通過 ``` // 回圈新的文本字串的長度 for (i = 1; i <= m; i += 1) { console.log("insert(t.charAt(i - 1)=", insert(t.charAt(i - 1))); console.log("get(table, i - 1, 0)=", get(table, i - 1, 0)); console.log( "cons=", cons( // return "i" + chars; 從第0個開始 insert(t.charAt(i - 1)), //回傳 return "i" + chars; 從第0個開始 get(table, i - 1, 0) // 獲取上一個table快取的資料 ) ); // 添加到把物件edits添加到table物件中 put( table, // 把字串快取成物件陣列 i, // 索引 0, cons( // return "i" + chars; 從第0個開始 insert(t.charAt(i - 1)), //回傳 return "i" + chars; 從第0個開始 get(table, i - 1, 0) // 獲取上一個table快取的資料 ) ); } ``` 然后我們來看看資料結構 
他是一個物件，其實用圖來表示，感覺有些二維陣列的意思我們來看看圖表示是怎么樣子的 
其實他是通過一個這樣的矩形格式然后一個個資料填充到表格中， 一開始他會填充一個默認的 0,0資料進去,這個時候我們看到table物件中的car字串是這樣子的 ix，ia，ib，ic這個是什么意識呢？其實這個是新字串，他呢前面加i意思是標識這個是插入 我們來先看看以下這幾個方法 這個就是這幾個方法的作用 ``` // 插入 function insert(chars) { return "i" + chars; } // 洗掉 function del(chars) { return "d" + chars; } // 保留 function retain(n) { return "r" + String(n); } ``` 那他是如何形成這個table的陣列資料呢，我們來看看這幾個方法， 我們來看看put，cons， get 然后通過put方法把 ``` // 添加到把物件edits添加到table物件中 function put(table, x, y, edits) { //對應的key return (table[String(x) + "," + String(y)] = edits); } ``` 然后我們再看看cons方法 ``` //連接上一個和下一個物件 形成一個鏈表 function cons(car, cdr) { return { car: car, //回傳 return "i" + chars; "d" + chars; "r" + chars; cdr: cdr, // 獲取上一個table快取的資料 把他變成一個鏈表連接起來 length: 1 + cdr.length, // 添加長度 toArray: toArray, // 鏈表轉換陣列 }; } ``` 連起來是這樣 ``` // 回圈新的文本字串的長度 for (i = 1; i <= m; i += 1) { // 添加到把物件edits添加到table物件中 put( table, // 把字串快取成物件陣列 i, // 索引 0, cons( // return "i" + chars; 從第0個開始 insert(t.charAt(i - 1)), //回傳 return "i" + chars; 從第0個開始 get(table, i - 1, 0) // 獲取上一個table快取的資料 把上一級的字串鏈表插入到子鏈表中 ) ); } ``` 然后到列舉舊的文本 ``` // 舊的文本，服務器文本字串的長度 for (j = 1; j <= n; j += 1) { console.log("del(t.charAt(j - 1)=", del(s.charAt(j - 1))); console.log("get(table, 0, j=", get(table, 0, j - 1)); console.log( "cons=", cons( // return "i" + chars; 從第0個開 del(s.charAt(j - 1)), // 回傳 return "d" + chars; 從第0個開始 get(table, 0, j - 1) // 獲取上一個table快取的資料 ) ); // 添加到把物件edits添加到table物件中 put( table, // 把字串快取成物件陣列 0, // j, // 索引 cons( del(s.charAt(j - 1)), // get(table, 0, j - 1) ) ); } ``` 再次我們來看看table資料是怎么樣子 
因為abc是服務器的文本所以前面顯示是d，這個時候還沒做對比，所以剛開始是以洗掉開頭， 接下來他是要把剛才那個圖表的資料填滿，這個時候只是填滿了紅色框框的資料，那么剩余的資料如何填充呢，我們來看看 
``` // 兩層嵌套 時間復雜度為 o(n^2) 空間復雜度為 o(2*long) // 新的"abc" for (i = 1; i <= m; i += 1) { // 舊的字串"xabc" for (j = 1; j <= n; j += 1) { // console.log('i=',i) // console.log('j=',j) //選擇單元格對比上面和左邊對比算出下一個table格的資料，這里用到的類似動態規劃演算法 chooseCell( edits, // 鏈表 i, // 新的字串索引 j, // 舊的字串索引 j先 開始增長 再到 i 增長 所以開始 1,1->1,2->1,3 function (direction, prevEdits) { // 在插入新的字串 switch (direction) { case "left": // 插入 debugger; put(edits, i, j, cons(insert(t.charAt(i - 1)), prevEdits)); break; case "up": // 洗掉 debugger; put(edits, i, j, cons(del(s.charAt(j - 1)), prevEdits)); break; case "diagonal": // 洗掉或者保留 debugger; // 判斷新的文本和舊的文本是否相同 d r i 等元素 if ( s.charAt(j - 1) === // 舊的字串"at" t.charAt(i - 1) // 新的"tff" ) { console.log("j - 1=", j - 1); console.log("i - 1=", i - 1); console.log("s=", s, "t=", t); debugger; // 如果是相同則保留 put(edits, i, j, cons(retain(1), prevEdits)); } else { debugger; // 如果不相同則記錄需要洗掉 put( edits, i, j, cons( insert(t.charAt(i - 1)), // 插入新的文本 cons(del(s.charAt(j - 1)), prevEdits) // 洗掉舊的文本 ) ); } break; default: throw new TypeError("Unknown direction."); } } ); } } console.log('edits=================',edits) console.log('m========',m) console.log('n========',n) ``` 這里呼叫chooseCell方法然后根據chooseCell方法判斷對比上面，左邊和左右上對角推出右邊的資料 一開始選擇的是 1,0然后推匯出1,1的資料，然后根據1,1的資料推匯出1,2的資料，然后根據1,2的資料推匯出1,3的資料 第二趟是根據2,0資料推匯出推匯出2,1的資料，然后根據2,1的資料推匯出2,2的資料，然后根據2,2的資料推匯出2,3的資料 第三趟是根據3,0資料推匯出推匯出3,1的資料，然后根據3,1的資料推匯出3,2的資料，然后根據3,2的資料推匯出3,3的資料 第四趟是根據4,0資料推匯出推匯出4,1的資料，然后根據4,1的資料推匯出4,2的資料，然后根據4,2的資料推匯出4,3的資料 這種演算法比較明顯像動態規劃法， 那么我們來看看chooseCell方法是如何動態判斷資料的,這里比較復雜我是打了好多個斷點和log才看懂 ``` //選擇單元格對比上面和左邊對比算出下一個table格的資料，這里用到的類似動態規劃演算法 function chooseCell( table, // 鏈表 x, // 新的文本字串指標 y, // 舊的文本字串指標 k // 回呼函式 ) { // 獲取上一次編輯 var prevEdits = get( table, x, // 新的文本字串指標 y - 1 // 舊的文本字串指標 ), min = prevEdits.length, direction = "up"; console.log("table=", table); console.log("prevEdits=", prevEdits); console.log("prevEdits x y=", "x=", x, "y-1=", y - 1); console.log("up=", "x=", x, "y - 1 =", y - 1); console.log("left=", "x - 1=", x - 1, "y=", y); console.log("diagonal=", "x - 1=", x - 1, " y - 1=", y - 1); console.log("add=", "x=", x, " y =", y); if ( get( table, x - 1, // 新的文本字串指標 y // 舊的文本字串指標 ).length < min ) { prevEdits = get( table, x - 1, // 新的文本字串指標 y // 舊的文本字串指標 ); min = prevEdits.length; direction = "left"; // debugger; } if ( get( table, x - 1, // 新的文本字串指標 y - 1 // 舊的文本字串指標 ).length < min ) { prevEdits = get( table, x - 1, // 新的文本字串指標 y - 1 // 舊的文本字串指標 ); min = prevEdits.length; direction = "diagonal"; } console.log("direction=",direction); debugger; return k(direction, prevEdits); } ``` 我看看到這里回圈先取 1,0值 direction = "up";默認為上面 和0,1對比如果0,1里面的length小于1,0的length的話就確定為direction = "left"; 左邊 然后上面條件不成立則在取 x - 1, y - 1 這個時候 就取到 0,0的，所以第一次 direction = "diagonal";對角 但是這個，我剛開始用看這個圖對應代碼都不正確 然后我翻轉了幾下圖才發現他程式應該是這樣表達的，但是這樣看圖有點吃力倒著看，但是圖和程式對上了， 
然后這樣走一遍，在回呼一個函式 這里會根據direction方向判斷是插入還是洗掉還是保留 ``` function (direction, prevEdits) { // 在插入新的字串 switch (direction) { case "left": // 插入 put(edits, i, j, cons(insert(t.charAt(i - 1)), prevEdits)); console.log("edits1========", edits); debugger; break; case "up": // 洗掉 debugger; put(edits, i, j, cons(del(s.charAt(j - 1)), prevEdits)); break; case "diagonal": // 洗掉或者保留 // 判斷新的文本和舊的文本是否相同 if ( s.charAt(j - 1) === // 舊的字串"abc" t.charAt(i - 1) // 新的"xabc" ) { console.log("j - 1=", j - 1); console.log("i - 1=", i - 1); console.log("s=", s, "t=", t); // 如果是相同則保留 put(edits, i, j, cons(retain(1), prevEdits)); console.log("edits==========", edits); debugger; } else { debugger; // 如果不相同則記錄需要洗掉 put( // 鏈表 edits, i, j, cons( insert(t.charAt(i - 1)), // 插入新的文本 cons( // del(s.charAt(j - 1)), // 洗掉舊的文本 prevEdits ) ) ); } break; default: throw new TypeError("Unknown direction."); } } ``` 最后table是這樣子， ``` { "0,0": { length: 0 }, "1,0": { car: "ix", cdr: { length: 0 }, length: 1 }, "2,0": { car: "ia", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, "3,0": { car: "ib", cdr: { car: "ia", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, "4,0": { car: "ic", cdr: { car: "ib", cdr: { car: "ia", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, length: 4, }, "0,1": { car: "da", cdr: { length: 0 }, length: 1 }, "0,2": { car: "db", cdr: { car: "da", cdr: { length: 0 }, length: 1 }, length: 2, }, "0,3": { car: "dc", cdr: { car: "db", cdr: { car: "da", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, "1,1": { car: "ix", cdr: { car: "da", cdr: { length: 0 }, length: 1 }, length: 2, }, "1,2": { car: "ix", cdr: { car: "db", cdr: { car: "da", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, "1,3": { car: "ix", cdr: { car: "dc", cdr: { car: "db", cdr: { car: "da", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, length: 4, }, "2,1": { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, "2,2": { car: "db", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, "2,3": { car: "dc", cdr: { car: "db", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, length: 4, }, "3,1": { car: "ib", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, "3,2": { car: "r1", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, "3,3": { car: "dc", cdr: { car: "r1", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, length: 4, }, "4,1": { car: "ic", cdr: { car: "ib", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, length: 4, }, "4,2": { car: "ic", cdr: { car: "r1", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, length: 4, }, "4,3": { car: "r1", cdr: { car: "r1", cdr: { car: "r1", cdr: { car: "ix", cdr: { length: 0 }, length: 1 }, length: 2, }, length: 3, }, length: 4, }, }; ``` 其實我們發現用動態規劃一下圖是可以猜測出下一個框框中的字串是多少，紅色的abc是代表洗掉的，綠色代表添加的，然后他們形成一個十字架交叉回圈，如果是遇到相同的則是r保留，沒遇到相同的紅色代表d洗掉，綠色代表i插入 ## xform合并操作行為 前面上面代碼代碼我們知道用戶a和服務器檔案對比產生一個操作行為陣列，然后用戶b也和服務器對比產生一個操作行為b，那么xform就是合并對比用戶a和b的操作行為在產生兩個操作行為ap, bp，演算法非常復雜，其實我測驗了好多案例，也是搞得朦朦朧朧也不是很理解這里的操作， 我們來看看代碼 defXformer 為xformTable物件添加編譯函式 ``` // 為xformTable物件添加編譯函式 function defXformer(typeA, typeB, xformer) { xformTable[join(typeA, typeB)] = xformer; } ``` //單個編輯一次只處理一個字符， 第一個型別是a的型別，第二個型別是b的型別 操作型別函式 ``` //假設當前所有的xformer函式 //單個編輯一次只處理一個字符， 第一個型別是a的型別，第二個型別是b的型別 // 保留 保留 defXformer("retain", "retain", function (editA, editB, indexA, indexB, k) { // 演算法 k(editA, editB, indexA + 1, indexB + 1); }); // 洗掉 洗掉 defXformer("delete", "delete", function (editA, editB, indexA, indexB, k) { if (ops.val(editA) === ops.val(editB)) { k(null, null, indexA + 1, indexB + 1); } else { throw new TypeError( "Document state mismatch: delete(" + ops.val(editA) + ") !== delete(" + ops.val(editB) + ")" ); } }); // // 保留 // function retain(n) { // return "r" + String(n); // } // 插入 插入 defXformer("insert", "insert", function (editA, editB, indexA, indexB, k) { if ( // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 ops.val(editA) === // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 ops.val(editB) ) { k( // 保留 ops.retain(1), // 保留 ops.retain(1), indexA + 1, indexB + 1 ); } else { k( editA, // 保留 ops.retain(1), indexA + 1, indexB ); } }); // 保留 洗掉 defXformer("retain", "delete", function (editA, editB, indexA, indexB, k) { k(null, editB, indexA + 1, indexB + 1); }); // 洗掉 保留 defXformer("delete", "retain", function (editA, editB, indexA, indexB, k) { k(editA, null, indexA + 1, indexB + 1); }); // 插入 保留 defXformer("insert", "retain", function (editA, editB, indexA, indexB, k) { k(editA, editB, indexA + 1, indexB); }); //保留 插入 defXformer("retain", "insert", function (editA, editB, indexA, indexB, k) { k(editA, editB, indexA, indexB + 1); }); // 插入 洗掉 defXformer("insert", "delete", function (editA, editB, indexA, indexB, k) { k( editA, // 保留 ops.retain(1), indexA + 1, indexB ); }); //洗掉 插入 defXformer("delete", "insert", function (editA, editB, indexA, indexB, k) { k( // 保留 ops.retain(1), editB, indexA, indexB + 1 ); }); ``` 這里通過a，b用戶操作型別去會呼叫不同的函式， k函式就是這個 這個函式就是把a，b用戶字串添加到operationAPrime和operationAPrime陣列中 ``` // 為operationAPrime和operationAPrime陣列添加字串 function kk( aPrime, //編輯a文本 bPrime, // 編輯b文本 newIndexA, //編輯a索引 newIndexB // 編輯b索引 ) { indexA = newIndexA; // 更新索引 indexB = newIndexB; // 更新索引 if (aPrime) { operationAPrime.push(aPrime); } if (bPrime) { operationBPrime.push(bPrime); } } ``` 通過一個while回圈 a和b用戶的字串，然后獲取他們操作型別，呼叫不同的操作型別函式從而實作合并功能， ``` // 回圈 a字串 和b字串 while (indexA < lenA && indexB < lenB) { editA = operationA[indexA]; editB = operationB[indexB]; xformer = xformTable[ join( // 判斷是否是洗掉 保留，插入 ops.type(editA), // 判斷是否是洗掉 保留，插入 ops.type(editB) ) ]; if (xformer) { //執行相應的函式 xformer( editA, //編輯a文本 editB, // 編輯b文本 indexA, //編輯a索引 indexB, // 編輯b索引 kk // 回呼函式 ); } else { throw new TypeError( "Unknown combination to transform: " + join( // 判斷是否是洗掉 保留，插入 ops.type(editA), // 判斷是否是洗掉 保留，插入 ops.type(editB) ) ); } } ``` ## apply 將操作行為轉換成文本 改文函式接受op操作行為和文本根據操作型別判斷是獲取舊的文本，還是新的操作行為字串 ``` function ( op, // op 字串 陣列 doc // 舊的檔案 ) { var i, len, index = 0, newDoc = ""; // 新的檔案 console.log("doc==============", doc); for (i = 0, len = op.length; i < len; i += 1) { // 判斷是否是洗掉 保留，插入 switch (operations.type(op[i])) { // 如果型別是保留則從舊的檔案找字串 case "retain": // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 newDoc += doc.slice( 0, // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ); console.log("op[i]==", op[i]); console.log(" operations.val(op[i])==", operations.val(op[i])); console.log( "doc.slice(0,operations.val(op[i]))==", doc.slice( 0, // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ) ); debugger; // 舊的檔案洗掉掉一個 doc = doc.slice( // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ); console.log("doc slice==============", doc); debugger break; // 如果是插入則從op查找 case "insert": // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 newDoc += operations.val(op[i]); break; case "delete": // 如果是洗掉，判斷doc是否存在op中 if ( doc.indexOf( // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ) !== 0 ) { throw new TypeError( "Expected '" + // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) + "' to delete, found '" + doc.slice(0, 10) + "'" ); } else { // 洗掉舊的檔案 doc = doc.slice(operations.val(op[i]).length); } break; default: throw new TypeError("Unknown operation: " + operations.type(op[i])); } } return newDoc; }; ``` xform，apply其實他們兩個可以是一個組合模塊的，并且他們非常復雜，光看代碼是很難理解他的思想的，下面我就用好幾個測驗案例來分析該代碼 假如初始字串為c 用戶a輸入 字串a ， 用戶b 輸入字串 b 期望得到結果是 abc 此時我們知道 operationsA=["ia","r1"], operationsB=["ib","r1"] 此時 ap=[] bp=[] indexA=0 indexB=0 那如何推測出ap, bp呢，接下來我們來看xform.js ``` // 回圈 a字串 和b字串 while (indexA < lenA && indexB < lenB) { editA = operationA[indexA]; editB = operationB[indexB]; ..... } ``` 第一次回圈進入因為第一個兩個都是插入所以進入這個函式 ``` // 插入 插入 defXformer("insert", "insert", function (editA, editB, indexA, indexB, k) { if ( // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 ops.val(editA) === // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 ops.val(editB) ) { /* 如果是保留則會從舊的文本中獲取字串 */ k( // 保留 ops.retain(1), // 如果他們都是相同的則保留 // 保留 ops.retain(1),// 如果他們都是相同的則保留 indexA + 1, // 所以指標加1 indexB + 1 ); } else { // 由于他們插入的是不相同的函式所以進入這里 k( editA, // 保留 ops.retain(1), indexA + 1, indexB ); } }); ``` k函式 ``` // 為operationAPrime和operationAPrime陣列添加字串 function kk( aPrime, //編輯a文本 bPrime, // 編輯b文本 newIndexA, //編輯a索引 newIndexB // 編輯b索引 ) { indexA = newIndexA; indexB = newIndexB; if (aPrime) { operationAPrime.push(aPrime); } if (bPrime) { operationBPrime.push(bPrime); } console.log("operationAPrime=", operationAPrime); console.log("operationBPrime=", operationBPrime); debugger; } ``` 此時 第一個while回圈結果為 operationsA=["ia","r1"], operationsB=["ib","r1"] ap=['ia'], bp=['r1'] indexA=1 indexB=0 下一次回圈 走該函式 ``` //保留 插入 defXformer("retain", "insert", function (editA, editB, indexA, indexB, k) { k(editA, editB, indexA, indexB + 1); }); ``` operationsA=["ia","r1"], operationsB=["ib","r1"] ap=['ia','r1'], bp=['r1','ib'] indexA=1 indexB=1 最后一次 indexA=1 indexB=1 執行 ``` // 保留 保留 defXformer("retain", "retain", function (editA, editB, indexA, indexB, k) { // 演算法 k( editA, editB, indexA + 1, //因為大家都是保留所以a和b指標都加1 indexB + 1 ); }); ``` 最后得 ap=['ia','r1' ,'r1'], bp=['r1','ib' ,'r1'] 最后我們需要理解 xform 就需要理解 indexA ，indexB 指標執行，一步步除錯，多試幾次才能理解， 最后我們看看apply是如何將這些操作記錄轉換成文本合并的呢 首先我們看看第一個引數是op 操作記錄，第二個是舊的檔案，也可以理解是上一次檔案內容, 他回圈op判斷操作型別，如果是保留的話則會從舊的檔案取出一個字串，如果是插入，則會從op取值，因為舊的檔案中是沒有這個值的，如果是洗掉則在舊的檔案中洗掉，新檔案則不會添加新的值， ``` function ( op, // op 字串 陣列 doc // 舊的檔案 ) { var i, len, index = 0, newDoc = ""; // 新的檔案 console.log("doc==============", doc); for (i = 0, len = op.length; i < len; i += 1) { // 判斷是否是洗掉 保留，插入 switch (operations.type(op[i])) { // 如果型別是保留則從舊的檔案找字串 case "retain": // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 newDoc += doc.slice( 0, // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ); console.log("op[i]==", op[i]); console.log(" operations.val(op[i])==", operations.val(op[i])); console.log( "doc.slice(0,operations.val(op[i]))==", doc.slice( 0, // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ) ); debugger; // 舊的檔案洗掉掉一個 doc = doc.slice( // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ); console.log("doc slice==============", doc); debugger break; // 如果是插入則從op查找 case "insert": // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 newDoc += operations.val(op[i]); break; case "delete": // 如果是洗掉，判斷doc是否存在op中 if ( doc.indexOf( // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) ) !== 0 ) { throw new TypeError( "Expected '" + // 如果是保留則回傳數字 獲取字串 從第一個開始去掉前面的 operations.val(op[i]) + "' to delete, found '" + doc.slice(0, 10) + "'" ); } else { // 洗掉舊的檔案 doc = doc.slice(operations.val(op[i]).length); } break; default: throw new TypeError("Unknown operation: " + operations.type(op[i])); } } return newDoc; }; ``` 接下來我們來看下測驗用例 原來檔案是 original='c' 用戶a輸入 'ab', 用戶b輸入 'cb'， 期望得到 acb operationsA=['ia','r1'] operationsB=['ib','r1'] ap=['ia','r1' ,'r1'], bp=['r1','ib' ,'r1'] 從上面看我們可以推測出 docA='ac' bp=['r1','ib' ,'r1'] 和 docA='ac' applay 我們就知道 保留a插入b保留c 最后得到 abc ``` // 經過沖突解決后生成的新操作可以達到： var docA = apply(operationsA, original); var finalA = apply(bp, docA); ``` ## 逐行operational-transformation 演算法原始碼分析git地址 開源不容易，希望大家多多給我github點贊，謝謝了！ https://github.com/qq281113270/operational-transformation.git 這博客園不支持md檔案格式建議去我的 掘金看: https://juejin.cn/post/7078930891141038111
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/451321.html
標籤：其他