textChange.js 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243
  1. /*---------------------------------------------------------------------------------------------
  2. * Copyright (c) Microsoft Corporation. All rights reserved.
  3. * Licensed under the MIT License. See License.txt in the project root for license information.
  4. *--------------------------------------------------------------------------------------------*/
  5. import * as buffer from '../../../base/common/buffer.js';
  6. import { decodeUTF16LE } from '../core/stringBuilder.js';
  7. function escapeNewLine(str) {
  8. return (str
  9. .replace(/\n/g, '\\n')
  10. .replace(/\r/g, '\\r'));
  11. }
  12. export class TextChange {
  13. constructor(oldPosition, oldText, newPosition, newText) {
  14. this.oldPosition = oldPosition;
  15. this.oldText = oldText;
  16. this.newPosition = newPosition;
  17. this.newText = newText;
  18. }
  19. get oldLength() {
  20. return this.oldText.length;
  21. }
  22. get oldEnd() {
  23. return this.oldPosition + this.oldText.length;
  24. }
  25. get newLength() {
  26. return this.newText.length;
  27. }
  28. get newEnd() {
  29. return this.newPosition + this.newText.length;
  30. }
  31. toString() {
  32. if (this.oldText.length === 0) {
  33. return `(insert@${this.oldPosition} "${escapeNewLine(this.newText)}")`;
  34. }
  35. if (this.newText.length === 0) {
  36. return `(delete@${this.oldPosition} "${escapeNewLine(this.oldText)}")`;
  37. }
  38. return `(replace@${this.oldPosition} "${escapeNewLine(this.oldText)}" with "${escapeNewLine(this.newText)}")`;
  39. }
  40. static _writeStringSize(str) {
  41. return (4 + 2 * str.length);
  42. }
  43. static _writeString(b, str, offset) {
  44. const len = str.length;
  45. buffer.writeUInt32BE(b, len, offset);
  46. offset += 4;
  47. for (let i = 0; i < len; i++) {
  48. buffer.writeUInt16LE(b, str.charCodeAt(i), offset);
  49. offset += 2;
  50. }
  51. return offset;
  52. }
  53. static _readString(b, offset) {
  54. const len = buffer.readUInt32BE(b, offset);
  55. offset += 4;
  56. return decodeUTF16LE(b, offset, len);
  57. }
  58. writeSize() {
  59. return (+4 // oldPosition
  60. + 4 // newPosition
  61. + TextChange._writeStringSize(this.oldText)
  62. + TextChange._writeStringSize(this.newText));
  63. }
  64. write(b, offset) {
  65. buffer.writeUInt32BE(b, this.oldPosition, offset);
  66. offset += 4;
  67. buffer.writeUInt32BE(b, this.newPosition, offset);
  68. offset += 4;
  69. offset = TextChange._writeString(b, this.oldText, offset);
  70. offset = TextChange._writeString(b, this.newText, offset);
  71. return offset;
  72. }
  73. static read(b, offset, dest) {
  74. const oldPosition = buffer.readUInt32BE(b, offset);
  75. offset += 4;
  76. const newPosition = buffer.readUInt32BE(b, offset);
  77. offset += 4;
  78. const oldText = TextChange._readString(b, offset);
  79. offset += TextChange._writeStringSize(oldText);
  80. const newText = TextChange._readString(b, offset);
  81. offset += TextChange._writeStringSize(newText);
  82. dest.push(new TextChange(oldPosition, oldText, newPosition, newText));
  83. return offset;
  84. }
  85. }
  86. export function compressConsecutiveTextChanges(prevEdits, currEdits) {
  87. if (prevEdits === null || prevEdits.length === 0) {
  88. return currEdits;
  89. }
  90. const compressor = new TextChangeCompressor(prevEdits, currEdits);
  91. return compressor.compress();
  92. }
  93. class TextChangeCompressor {
  94. constructor(prevEdits, currEdits) {
  95. this._prevEdits = prevEdits;
  96. this._currEdits = currEdits;
  97. this._result = [];
  98. this._resultLen = 0;
  99. this._prevLen = this._prevEdits.length;
  100. this._prevDeltaOffset = 0;
  101. this._currLen = this._currEdits.length;
  102. this._currDeltaOffset = 0;
  103. }
  104. compress() {
  105. let prevIndex = 0;
  106. let currIndex = 0;
  107. let prevEdit = this._getPrev(prevIndex);
  108. let currEdit = this._getCurr(currIndex);
  109. while (prevIndex < this._prevLen || currIndex < this._currLen) {
  110. if (prevEdit === null) {
  111. this._acceptCurr(currEdit);
  112. currEdit = this._getCurr(++currIndex);
  113. continue;
  114. }
  115. if (currEdit === null) {
  116. this._acceptPrev(prevEdit);
  117. prevEdit = this._getPrev(++prevIndex);
  118. continue;
  119. }
  120. if (currEdit.oldEnd <= prevEdit.newPosition) {
  121. this._acceptCurr(currEdit);
  122. currEdit = this._getCurr(++currIndex);
  123. continue;
  124. }
  125. if (prevEdit.newEnd <= currEdit.oldPosition) {
  126. this._acceptPrev(prevEdit);
  127. prevEdit = this._getPrev(++prevIndex);
  128. continue;
  129. }
  130. if (currEdit.oldPosition < prevEdit.newPosition) {
  131. const [e1, e2] = TextChangeCompressor._splitCurr(currEdit, prevEdit.newPosition - currEdit.oldPosition);
  132. this._acceptCurr(e1);
  133. currEdit = e2;
  134. continue;
  135. }
  136. if (prevEdit.newPosition < currEdit.oldPosition) {
  137. const [e1, e2] = TextChangeCompressor._splitPrev(prevEdit, currEdit.oldPosition - prevEdit.newPosition);
  138. this._acceptPrev(e1);
  139. prevEdit = e2;
  140. continue;
  141. }
  142. // At this point, currEdit.oldPosition === prevEdit.newPosition
  143. let mergePrev;
  144. let mergeCurr;
  145. if (currEdit.oldEnd === prevEdit.newEnd) {
  146. mergePrev = prevEdit;
  147. mergeCurr = currEdit;
  148. prevEdit = this._getPrev(++prevIndex);
  149. currEdit = this._getCurr(++currIndex);
  150. }
  151. else if (currEdit.oldEnd < prevEdit.newEnd) {
  152. const [e1, e2] = TextChangeCompressor._splitPrev(prevEdit, currEdit.oldLength);
  153. mergePrev = e1;
  154. mergeCurr = currEdit;
  155. prevEdit = e2;
  156. currEdit = this._getCurr(++currIndex);
  157. }
  158. else {
  159. const [e1, e2] = TextChangeCompressor._splitCurr(currEdit, prevEdit.newLength);
  160. mergePrev = prevEdit;
  161. mergeCurr = e1;
  162. prevEdit = this._getPrev(++prevIndex);
  163. currEdit = e2;
  164. }
  165. this._result[this._resultLen++] = new TextChange(mergePrev.oldPosition, mergePrev.oldText, mergeCurr.newPosition, mergeCurr.newText);
  166. this._prevDeltaOffset += mergePrev.newLength - mergePrev.oldLength;
  167. this._currDeltaOffset += mergeCurr.newLength - mergeCurr.oldLength;
  168. }
  169. const merged = TextChangeCompressor._merge(this._result);
  170. const cleaned = TextChangeCompressor._removeNoOps(merged);
  171. return cleaned;
  172. }
  173. _acceptCurr(currEdit) {
  174. this._result[this._resultLen++] = TextChangeCompressor._rebaseCurr(this._prevDeltaOffset, currEdit);
  175. this._currDeltaOffset += currEdit.newLength - currEdit.oldLength;
  176. }
  177. _getCurr(currIndex) {
  178. return (currIndex < this._currLen ? this._currEdits[currIndex] : null);
  179. }
  180. _acceptPrev(prevEdit) {
  181. this._result[this._resultLen++] = TextChangeCompressor._rebasePrev(this._currDeltaOffset, prevEdit);
  182. this._prevDeltaOffset += prevEdit.newLength - prevEdit.oldLength;
  183. }
  184. _getPrev(prevIndex) {
  185. return (prevIndex < this._prevLen ? this._prevEdits[prevIndex] : null);
  186. }
  187. static _rebaseCurr(prevDeltaOffset, currEdit) {
  188. return new TextChange(currEdit.oldPosition - prevDeltaOffset, currEdit.oldText, currEdit.newPosition, currEdit.newText);
  189. }
  190. static _rebasePrev(currDeltaOffset, prevEdit) {
  191. return new TextChange(prevEdit.oldPosition, prevEdit.oldText, prevEdit.newPosition + currDeltaOffset, prevEdit.newText);
  192. }
  193. static _splitPrev(edit, offset) {
  194. const preText = edit.newText.substr(0, offset);
  195. const postText = edit.newText.substr(offset);
  196. return [
  197. new TextChange(edit.oldPosition, edit.oldText, edit.newPosition, preText),
  198. new TextChange(edit.oldEnd, '', edit.newPosition + offset, postText)
  199. ];
  200. }
  201. static _splitCurr(edit, offset) {
  202. const preText = edit.oldText.substr(0, offset);
  203. const postText = edit.oldText.substr(offset);
  204. return [
  205. new TextChange(edit.oldPosition, preText, edit.newPosition, edit.newText),
  206. new TextChange(edit.oldPosition + offset, postText, edit.newEnd, '')
  207. ];
  208. }
  209. static _merge(edits) {
  210. if (edits.length === 0) {
  211. return edits;
  212. }
  213. let result = [], resultLen = 0;
  214. let prev = edits[0];
  215. for (let i = 1; i < edits.length; i++) {
  216. const curr = edits[i];
  217. if (prev.oldEnd === curr.oldPosition) {
  218. // Merge into `prev`
  219. prev = new TextChange(prev.oldPosition, prev.oldText + curr.oldText, prev.newPosition, prev.newText + curr.newText);
  220. }
  221. else {
  222. result[resultLen++] = prev;
  223. prev = curr;
  224. }
  225. }
  226. result[resultLen++] = prev;
  227. return result;
  228. }
  229. static _removeNoOps(edits) {
  230. if (edits.length === 0) {
  231. return edits;
  232. }
  233. let result = [], resultLen = 0;
  234. for (let i = 0; i < edits.length; i++) {
  235. const edit = edits[i];
  236. if (edit.oldText === edit.newText) {
  237. continue;
  238. }
  239. result[resultLen++] = edit;
  240. }
  241. return result;
  242. }
  243. }