- commit
- 4f6e091219172b08c720c61baabf9c228c019b0f
- parent
- 8ef424d54c9ce9f7cfe8c95e10571e8500db2b3c
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2020-05-03 08:46
context approach
Diffstat
| A | context.mjs | 101 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| R | ot.mjs -> fuzzy.mjs | 76 | ++++++++++++------------------------------------------------- |
| M | index.html | 3 | +-- |
| M | index.js | 40 | ++++++++++++++++++++++------------------ |
| D | transport.mjs | 33 | --------------------------------- |
5 files changed, 138 insertions, 115 deletions
diff --git a/context.mjs b/context.mjs
@@ -0,0 +1,101 @@
-1 1 import * as fuzzy from './fuzzy.mjs';
-1 2
-1 3 var applyExact = function(text, [pos, before, after]) {
-1 4 if (text.slice(pos).startsWith(before)) {
-1 5 return text.slice(0, pos) + after + text.slice(pos + before.length);
-1 6 } else {
-1 7 throw 'no match';
-1 8 }
-1 9 };
-1 10
-1 11 export var apply = function(text, [pos, before, after]) {
-1 12 // try exact match
-1 13 try {
-1 14 return applyExact(text, [pos, before, after]);
-1 15 } catch (e) {}
-1 16
-1 17 // try exact match in similar position
-1 18 var best = -1;
-1 19 var bestDist = Infinity;
-1 20 for (var i = text.indexOf(before); i !== -1; i = text.indexOf(before, i + 1)) {
-1 21 var dist = Math.abs(i - pos);
-1 22 if (dist < bestDist) {
-1 23 best = i;
-1 24 bestDist = dist;
-1 25 } else {
-1 26 break;
-1 27 }
-1 28 }
-1 29 if (best !== -1) {
-1 30 return applyExact(text, [best, before, after]);
-1 31 }
-1 32
-1 33 // fall back to fuzzy merge
-1 34 var ctxLen = 3;
-1 35 var ctxStart = Math.max(pos - ctxLen, 0);
-1 36 var ctxEnd = Math.min(pos + before.length + ctxLen, text.length);
-1 37 var ctx = text.slice(ctxStart, ctxEnd);
-1 38 var ctxAfter = fuzzy.mergeText(before, after, ctx);
-1 39 return applyExact(text, [ctxStart, ctx, ctxAfter]);
-1 40 };
-1 41
-1 42 export var diff = function(text1, text2, ctx) {
-1 43 var start = 0;
-1 44 var end1 = text1.length;
-1 45 var end2 = text2.length;
-1 46
-1 47 while (start < text1.length && start < text2.length && text1[start] === text2[start]) {
-1 48 start += 1;
-1 49 }
-1 50 while (end1 >= start && end2 >= start && text1[end1 - 1] === text2[end2 - 1]) {
-1 51 end1 -= 1;
-1 52 end2 -= 1;
-1 53 }
-1 54
-1 55 start = Math.max(0, start - ctx);
-1 56 end1 += ctx;
-1 57 end2 += ctx;
-1 58
-1 59 return [start, text1.slice(start, end1), text2.slice(start, end2)];
-1 60 };
-1 61
-1 62 export var merge = function([pos1, before1, after1], [pos2, before2, after2]) {
-1 63 // merge subsequent inserts
-1 64 try {
-1 65 var after = applyExact(after1, [pos2 - pos1, before2, after2]);
-1 66 return [[pos1, before1, after]];
-1 67 } catch (e) {}
-1 68
-1 69 // merge subsequent deletes (inverse insert)
-1 70 try {
-1 71 var before = applyExact(before2, [pos1 - pos2, after1, before1]);
-1 72 return [[pos2, before, after2]];
-1 73 } catch (e) {}
-1 74
-1 75 return [
-1 76 [pos1, before1, after1],
-1 77 [pos2, before2, after2],
-1 78 ];
-1 79 };
-1 80
-1 81 export var pushChange = function(changes, change) {
-1 82 if (!changes.length) {
-1 83 changes.push(change);
-1 84 } else {
-1 85 var last = changes.pop();
-1 86 var merged = merge(last, change);
-1 87 for (var i = 0; i < merged.length; i++) {
-1 88 changes.push(merged[i]);
-1 89 }
-1 90 }
-1 91 };
-1 92
-1 93
-1 94 var assertEqual = function(a, b, msg) {
-1 95 if (JSON.stringify(a) !== JSON.stringify(b)) {
-1 96 console.warn('test failed:', msg, a, b);
-1 97 }
-1 98 };
-1 99
-1 100 assertEqual(merge([1, 'foobaz', 'foobbaz'], [2, 'oobbaz', 'oobabaz']), [[1, 'foobaz', 'foobabaz']], 'merge insert');
-1 101 assertEqual(merge([1, 'foobaz', 'fobaz'], [0, 'Xfobaz', 'Xfbaz']), [[0, 'Xfoobaz', 'Xfbaz']], 'merge delete');
diff --git a/ot.mjs b/fuzzy.mjs
@@ -1,24 +1,3 @@1 -1 // https://github.com/ether/etherpad-lite/raw/master/doc/easysync/easysync-full-description.pdf2 -13 -1 var fixPos = function(pos, a) {4 -1 var ret = 0;5 -1 for (var i = 0; i < a.length; i++) {6 -1 var part = a[i];7 -1 if (Array.isArray(part)) {8 -1 if (part[0] > pos) {9 -1 break;10 -1 } else if (part[1] <= pos) {11 -1 ret += part[1] - part[0];12 -1 } else {13 -1 return ret + pos - part[0];14 -1 }15 -1 } else {16 -1 ret += part.length;17 -1 }18 -1 }19 -1 return ret;20 -1 };21 -122 1 var intersectRetain = function(a, b) { 23 2 var parts = []; 24 3 a.filter(Array.isArray).forEach(pa => { @@ -74,33 +53,7 @@ var normalize = function(parts) { 74 53 return ret; 75 54 }; 76 5577 -1 export var follow = function(a, b) {78 -1 if (!a || !b) {79 -1 return b;80 -1 }81 -182 -1 var parts = [];83 -184 -1 getInsertions(a).forEach(ins => {85 -1 parts.push([ins[0], ins[0] + ins[1].length]);86 -1 });87 -1 getInsertions(b).forEach(ins => {88 -1 parts.push([fixPos(ins[0], a), ins[1]]);89 -1 });90 -1 intersectRetain(a, b).forEach(part => {91 -1 parts.push([92 -1 fixPos(part[0], a),93 -1 fixPos(part[1], a),94 -1 ]);95 -1 });96 -197 -1 parts.sort((x, y) => x[0] - y[0]);98 -1 parts = parts.map(part => Number.isInteger(part[1]) ? part : part[1]);99 -1100 -1 return normalize(parts);101 -1 };102 -1103 -1 export var merge = function(a, b) {-1 56 var merge = function(a, b) { 104 57 if (!a || !b) { 105 58 return a || b; 106 59 } @@ -123,7 +76,7 @@ export var merge = function(a, b) { 123 76 return normalize(parts); 124 77 }; 125 78126 -1 export var apply = function(s, parts) {-1 79 var apply = function(s, parts) { 127 80 if (!parts) { 128 81 return s; 129 82 } @@ -138,7 +91,7 @@ export var apply = function(s, parts) { 138 91 return ret; 139 92 }; 140 93141 -1 export var diff = function(s1, s2) {-1 94 var diff = function(s1, s2) { 142 95 // https://en.wikipedia.org/wiki/Longest_common_subsequence_problem 143 96 if (s1 === s2) { 144 97 return null; @@ -193,6 +146,13 @@ export var diff = function(s1, s2) { 193 146 return normalize(parts); 194 147 }; 195 148 -1 149 export var mergeText = function(base, text1, text2) { -1 150 var a = diff(base, text1); -1 151 var b = diff(base, text2); -1 152 var combined = merge(a, b); -1 153 return apply(base, combined); -1 154 }; -1 155 196 156 197 157 var assertEqual = function(a, b, msg) { 198 158 if (JSON.stringify(a) !== JSON.stringify(b)) { @@ -203,28 +163,20 @@ var assertEqual = function(a, b, msg) { 203 163 var a = [[0, 2], 'si', [7, 8]]; 204 164 var b = [[0, 1], 'e', [6, 7], 'ow']; 205 165206 -1 assertEqual(fixPos(0, a), 0, 'fixPos(0)');207 -1 assertEqual(fixPos(1, a), 1, 'fixPos(1)');208 -1 assertEqual(fixPos(3, a), 4, 'fixPos(3)');209 -1 assertEqual(fixPos(4, a), 4, 'fixPos(4)');210 -1 assertEqual(fixPos(7, a), 4, 'fixPos(7)');211 -1 assertEqual(fixPos(8, a), 5, 'fixPos(8)');212 -1213 166 assertEqual(normalize(['foo', 'bar']), ['foobar'], 'normalize'); 214 167 assertEqual(normalize([[1, 5], [3, 6]]), [[1, 6]], 'normalize'); 215 168 assertEqual(normalize([[1, 3], [3, 6]]), [[1, 6]], 'normalize'); 216 169 assertEqual(normalize([[1, 3], [4, 6]]), [[1, 3], [4, 6]], 'normalize'); 217 170 assertEqual(normalize([[1, 3], [2, 3]]), [[1, 3]], 'normalize'); 218 171219 -1 assertEqual(follow(a, b), [[0, 1], 'e', [2, 4], 'ow'], 'follow');220 -1 assertEqual(follow(b, a), [[0, 2], 'si', [3, 5]], 'follow');221 -1222 172 assertEqual(merge(a, b), [[0, 1], 'esiow'], 'merge'); 223 173 assertEqual(merge(b, a), [[0, 1], 'esiow'], 'merge'); 224 174 225 175 assertEqual(apply('baseball', a), 'basil', 'apply(a)'); 226 176 assertEqual(apply('baseball', b), 'below', 'apply(b)'); 227 177228 -1 assertEqual(diff('baseball', 'basil'), a, 'diff(a)');229 -1 assertEqual(diff('baseball', 'below'), b, 'diff(b)');-1 178 // assertEqual(diff('baseball', 'basil'), a, 'diff(a)'); -1 179 // assertEqual(diff('baseball', 'below'), b, 'diff(b)'); 230 180 assertEqual(diff('', 'asd'), ['asd'], 'diff("", "asd")'); -1 181 -1 182 assertEqual(mergeText('asd', 'asd.', 'Asd'), 'Asd.', 'mergeText');
diff --git a/index.html b/index.html
@@ -9,8 +9,7 @@ 9 9 <link rel="stylesheet" href="rtc.css"> 10 10 </head> 11 11 <body>12 -1 <textarea id="local"></textarea>13 -1 <textarea id="remote"></textarea>-1 12 <textarea autocomplete="off"></textarea> 14 13 <script type="module" src="index.js"></script> 15 14 </body> 16 15 </html>
diff --git a/index.js b/index.js
@@ -1,39 +1,43 @@1 -1 import * as ot from './ot.mjs';-1 1 import * as context from './context.mjs'; 2 2 3 3 var local = document.querySelector('#local'); 4 4 var remote = document.querySelector('#remote'); 5 5 6 6 7 7 var listeners = [];8 -1 var send = function(sender, patch) {9 -1 listeners.forEach(l => l(sender, patch));-1 8 var send = function(sender, changes) { -1 9 listeners.forEach(l => l(sender, changes)); 10 10 }; 11 1112 -113 12 var pad = function(el) { 14 13 var id = el.id; 15 14 var old = el.value;16 -1 var remote = null;17 1518 -1 setInterval(function() {19 -1 // FIXME: diff does loose some information on user intent20 -1 var patch = ot.diff(old, el.value);21 -1 send(id, patch);-1 16 var localChanges = []; -1 17 var remoteChanges = []; 22 1823 -1 var rel = ot.follow(patch, remote);24 -1 if (patch || remote) {25 -1 console.log(patch, remote, rel, old, el.value);26 -1 }-1 19 el.addEventListener('input', function() { -1 20 var change = context.diff(old, el.value, 3); -1 21 context.pushChange(localChanges, change); -1 22 old = el.value; -1 23 }); 27 2428 -1 el.value = ot.apply(el.value, rel);-1 25 setInterval(function() { -1 26 if (localChanges.length) { -1 27 send(id, localChanges); -1 28 localChanges = []; -1 29 } 29 3030 -1 remote = null;31 -1 old = el.value;-1 31 var text = el.value; -1 32 while (remoteChanges.length) { -1 33 text = context.apply(text, remoteChanges.shift()); -1 34 } -1 35 el.value = text; 32 36 }, 500); 33 3734 -1 listeners.push(function(sender, patch) {-1 38 listeners.push(function(sender, changes) { 35 39 if (sender !== id) {36 -1 remote = ot.merge(remote, patch);-1 40 remoteChanges = remoteChanges.concat(changes); 37 41 } 38 42 }); 39 43 };
diff --git a/transport.mjs b/transport.mjs
@@ -1,33 +0,0 @@1 -1 var text = '';2 -1 var staged = null;3 -1 var local = null;4 -15 -1 var onLocal = function(patch) {6 -1 local = ot.merge(local, patch);7 -1 };8 -19 -1 var submit = function() {10 -1 if (staged || !local) {11 -1 return;12 -1 }13 -1 server_send(local); // TODO: retry14 -1 staged = local;15 -1 local = null;16 -1 };17 -118 -1 var onAck = function() {19 -1 staged = null;20 -1 };21 -122 -1 var onPatch = function(remote) {23 -1 var i = ot.follow(staged, remote);24 -1 text = ot.apply(text, ot.follow(local, i));25 -1 local = ot.follow(i, local);26 -1 staged = ot.follow(remote, staged);27 -1 };28 -129 -1 var init = function(head) {30 -1 text = head;31 -1 staged = null;32 -1 local = null;33 -1 };