UpdateCompressor.js 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278
  1. /*
  2. * decaffeinate suggestions:
  3. * DS101: Remove unnecessary use of Array.from
  4. * DS103: Rewrite code to no longer use __guard__
  5. * DS207: Consider shorter variations of null checks
  6. * Full docs: https://github.com/decaffeinate/decaffeinate/blob/master/docs/suggestions.md
  7. */
  8. let oneMinute, twoMegabytes, UpdateCompressor;
  9. const strInject = (s1, pos, s2) => s1.slice(0, pos) + s2 + s1.slice(pos);
  10. const strRemove = (s1, pos, length) => s1.slice(0, pos) + s1.slice((pos + length));
  11. const { diff_match_patch } = require("../lib/diff_match_patch");
  12. const dmp = new diff_match_patch();
  13. module.exports = (UpdateCompressor = {
  14. NOOP: "noop",
  15. // Updates come from the doc updater in format
  16. // {
  17. // op: [ { ... op1 ... }, { ... op2 ... } ]
  18. // meta: { ts: ..., user_id: ... }
  19. // }
  20. // but it's easier to work with on op per update, so convert these updates to
  21. // our compressed format
  22. // [{
  23. // op: op1
  24. // meta: { start_ts: ... , end_ts: ..., user_id: ... }
  25. // }, {
  26. // op: op2
  27. // meta: { start_ts: ... , end_ts: ..., user_id: ... }
  28. // }]
  29. convertToSingleOpUpdates(updates) {
  30. const splitUpdates = [];
  31. for (let update of Array.from(updates)) {
  32. // Reject any non-insert or delete ops, i.e. comments
  33. const ops = update.op.filter(o => (o.i != null) || (o.d != null));
  34. if (ops.length === 0) {
  35. splitUpdates.push({
  36. op: UpdateCompressor.NOOP,
  37. meta: {
  38. start_ts: update.meta.start_ts || update.meta.ts,
  39. end_ts: update.meta.end_ts || update.meta.ts,
  40. user_id: update.meta.user_id
  41. },
  42. v: update.v
  43. });
  44. } else {
  45. for (let op of Array.from(ops)) {
  46. splitUpdates.push({
  47. op,
  48. meta: {
  49. start_ts: update.meta.start_ts || update.meta.ts,
  50. end_ts: update.meta.end_ts || update.meta.ts,
  51. user_id: update.meta.user_id
  52. },
  53. v: update.v
  54. });
  55. }
  56. }
  57. }
  58. return splitUpdates;
  59. },
  60. concatUpdatesWithSameVersion(updates) {
  61. const concattedUpdates = [];
  62. for (let update of Array.from(updates)) {
  63. const lastUpdate = concattedUpdates[concattedUpdates.length - 1];
  64. if ((lastUpdate != null) && (lastUpdate.v === update.v)) {
  65. if (update.op !== UpdateCompressor.NOOP) { lastUpdate.op.push(update.op); }
  66. } else {
  67. const nextUpdate = {
  68. op: [],
  69. meta: update.meta,
  70. v: update.v
  71. };
  72. if (update.op !== UpdateCompressor.NOOP) { nextUpdate.op.push(update.op); }
  73. concattedUpdates.push(nextUpdate);
  74. }
  75. }
  76. return concattedUpdates;
  77. },
  78. compressRawUpdates(lastPreviousUpdate, rawUpdates) {
  79. if (__guard__(lastPreviousUpdate != null ? lastPreviousUpdate.op : undefined, x => x.length) > 1) {
  80. // if the last previous update was an array op, don't compress onto it.
  81. // The avoids cases where array length changes but version number doesn't
  82. return [lastPreviousUpdate].concat(UpdateCompressor.compressRawUpdates(null,rawUpdates));
  83. }
  84. if (lastPreviousUpdate != null) {
  85. rawUpdates = [lastPreviousUpdate].concat(rawUpdates);
  86. }
  87. let updates = UpdateCompressor.convertToSingleOpUpdates(rawUpdates);
  88. updates = UpdateCompressor.compressUpdates(updates);
  89. return UpdateCompressor.concatUpdatesWithSameVersion(updates);
  90. },
  91. compressUpdates(updates) {
  92. if (updates.length === 0) { return []; }
  93. let compressedUpdates = [updates.shift()];
  94. for (let update of Array.from(updates)) {
  95. const lastCompressedUpdate = compressedUpdates.pop();
  96. if (lastCompressedUpdate != null) {
  97. compressedUpdates = compressedUpdates.concat(UpdateCompressor._concatTwoUpdates(lastCompressedUpdate, update));
  98. } else {
  99. compressedUpdates.push(update);
  100. }
  101. }
  102. return compressedUpdates;
  103. },
  104. MAX_TIME_BETWEEN_UPDATES: (oneMinute = 60 * 1000),
  105. MAX_UPDATE_SIZE: (twoMegabytes = 2* 1024 * 1024),
  106. _concatTwoUpdates(firstUpdate, secondUpdate) {
  107. let offset;
  108. firstUpdate = {
  109. op: firstUpdate.op,
  110. meta: {
  111. user_id: firstUpdate.meta.user_id || null,
  112. start_ts: firstUpdate.meta.start_ts || firstUpdate.meta.ts,
  113. end_ts: firstUpdate.meta.end_ts || firstUpdate.meta.ts
  114. },
  115. v: firstUpdate.v
  116. };
  117. secondUpdate = {
  118. op: secondUpdate.op,
  119. meta: {
  120. user_id: secondUpdate.meta.user_id || null,
  121. start_ts: secondUpdate.meta.start_ts || secondUpdate.meta.ts,
  122. end_ts: secondUpdate.meta.end_ts || secondUpdate.meta.ts
  123. },
  124. v: secondUpdate.v
  125. };
  126. if (firstUpdate.meta.user_id !== secondUpdate.meta.user_id) {
  127. return [firstUpdate, secondUpdate];
  128. }
  129. if ((secondUpdate.meta.start_ts - firstUpdate.meta.end_ts) > UpdateCompressor.MAX_TIME_BETWEEN_UPDATES) {
  130. return [firstUpdate, secondUpdate];
  131. }
  132. const firstOp = firstUpdate.op;
  133. const secondOp = secondUpdate.op;
  134. const firstSize = (firstOp.i != null ? firstOp.i.length : undefined) || (firstOp.d != null ? firstOp.d.length : undefined);
  135. const secondSize = (secondOp.i != null ? secondOp.i.length : undefined) || (secondOp.d != null ? secondOp.d.length : undefined);
  136. // Two inserts
  137. if ((firstOp.i != null) && (secondOp.i != null) && (firstOp.p <= secondOp.p && secondOp.p <= (firstOp.p + firstOp.i.length)) && ((firstSize + secondSize) < UpdateCompressor.MAX_UPDATE_SIZE)) {
  138. return [{
  139. meta: {
  140. start_ts: firstUpdate.meta.start_ts,
  141. end_ts: secondUpdate.meta.end_ts,
  142. user_id: firstUpdate.meta.user_id
  143. },
  144. op: {
  145. p: firstOp.p,
  146. i: strInject(firstOp.i, secondOp.p - firstOp.p, secondOp.i)
  147. },
  148. v: secondUpdate.v
  149. }
  150. ];
  151. // Two deletes
  152. } else if ((firstOp.d != null) && (secondOp.d != null) && (secondOp.p <= firstOp.p && firstOp.p <= (secondOp.p + secondOp.d.length)) && ((firstSize + secondSize) < UpdateCompressor.MAX_UPDATE_SIZE)) {
  153. return [{
  154. meta: {
  155. start_ts: firstUpdate.meta.start_ts,
  156. end_ts: secondUpdate.meta.end_ts,
  157. user_id: firstUpdate.meta.user_id
  158. },
  159. op: {
  160. p: secondOp.p,
  161. d: strInject(secondOp.d, firstOp.p - secondOp.p, firstOp.d)
  162. },
  163. v: secondUpdate.v
  164. }
  165. ];
  166. // An insert and then a delete
  167. } else if ((firstOp.i != null) && (secondOp.d != null) && (firstOp.p <= secondOp.p && secondOp.p <= (firstOp.p + firstOp.i.length))) {
  168. offset = secondOp.p - firstOp.p;
  169. const insertedText = firstOp.i.slice(offset, offset + secondOp.d.length);
  170. // Only trim the insert when the delete is fully contained within in it
  171. if (insertedText === secondOp.d) {
  172. const insert = strRemove(firstOp.i, offset, secondOp.d.length);
  173. return [{
  174. meta: {
  175. start_ts: firstUpdate.meta.start_ts,
  176. end_ts: secondUpdate.meta.end_ts,
  177. user_id: firstUpdate.meta.user_id
  178. },
  179. op: {
  180. p: firstOp.p,
  181. i: insert
  182. },
  183. v: secondUpdate.v
  184. }
  185. ];
  186. } else {
  187. // This will only happen if the delete extends outside the insert
  188. return [firstUpdate, secondUpdate];
  189. }
  190. // A delete then an insert at the same place, likely a copy-paste of a chunk of content
  191. } else if ((firstOp.d != null) && (secondOp.i != null) && (firstOp.p === secondOp.p)) {
  192. offset = firstOp.p;
  193. const diff_ops = this.diffAsShareJsOps(firstOp.d, secondOp.i);
  194. if (diff_ops.length === 0) {
  195. return [{ // Noop
  196. meta: {
  197. start_ts: firstUpdate.meta.start_ts,
  198. end_ts: secondUpdate.meta.end_ts,
  199. user_id: firstUpdate.meta.user_id
  200. },
  201. op: {
  202. p: firstOp.p,
  203. i: ""
  204. },
  205. v: secondUpdate.v
  206. }];
  207. } else {
  208. return diff_ops.map(function(op) {
  209. op.p += offset;
  210. return {
  211. meta: {
  212. start_ts: firstUpdate.meta.start_ts,
  213. end_ts: secondUpdate.meta.end_ts,
  214. user_id: firstUpdate.meta.user_id
  215. },
  216. op,
  217. v: secondUpdate.v
  218. };});
  219. }
  220. } else {
  221. return [firstUpdate, secondUpdate];
  222. }
  223. },
  224. ADDED: 1,
  225. REMOVED: -1,
  226. UNCHANGED: 0,
  227. diffAsShareJsOps(before, after, callback) {
  228. if (callback == null) { callback = function(error, ops) {}; }
  229. const diffs = dmp.diff_main(before, after);
  230. dmp.diff_cleanupSemantic(diffs);
  231. const ops = [];
  232. let position = 0;
  233. for (let diff of Array.from(diffs)) {
  234. const type = diff[0];
  235. const content = diff[1];
  236. if (type === this.ADDED) {
  237. ops.push({
  238. i: content,
  239. p: position
  240. });
  241. position += content.length;
  242. } else if (type === this.REMOVED) {
  243. ops.push({
  244. d: content,
  245. p: position
  246. });
  247. } else if (type === this.UNCHANGED) {
  248. position += content.length;
  249. } else {
  250. throw "Unknown type";
  251. }
  252. }
  253. return ops;
  254. }
  255. });
  256. function __guard__(value, transform) {
  257. return (typeof value !== 'undefined' && value !== null) ? transform(value) : undefined;
  258. }