1 | /**
|
2 | * Efficient diffs.
|
3 | *
|
4 | * @module diff
|
5 | */
|
6 |
|
7 | import { equalityStrict } from './function.js'
|
8 |
|
9 | /**
|
10 | * A SimpleDiff describes a change on a String.
|
11 | *
|
12 | * ```js
|
13 | * console.log(a) // the old value
|
14 | * console.log(b) // the updated value
|
15 | * // Apply changes of diff (pseudocode)
|
16 | * a.remove(diff.index, diff.remove) // Remove `diff.remove` characters
|
17 | * a.insert(diff.index, diff.insert) // Insert `diff.insert`
|
18 | * a === b // values match
|
19 | * ```
|
20 | *
|
21 | * @typedef {Object} SimpleDiff
|
22 | * @property {Number} index The index where changes were applied
|
23 | * @property {Number} remove The number of characters to delete starting
|
24 | * at `index`.
|
25 | * @property {T} insert The new text to insert at `index` after applying
|
26 | * `delete`
|
27 | *
|
28 | * @template T
|
29 | */
|
30 |
|
31 | const highSurrogateRegex = /[\uD800-\uDBFF]/
|
32 | const lowSurrogateRegex = /[\uDC00-\uDFFF]/
|
33 |
|
34 | /**
|
35 | * Create a diff between two strings. This diff implementation is highly
|
36 | * efficient, but not very sophisticated.
|
37 | *
|
38 | * @function
|
39 | *
|
40 | * @param {string} a The old version of the string
|
41 | * @param {string} b The updated version of the string
|
42 | * @return {SimpleDiff<string>} The diff description.
|
43 | */
|
44 | export const simpleDiffString = (a, b) => {
|
45 | let left = 0 // number of same characters counting from left
|
46 | let right = 0 // number of same characters counting from right
|
47 | while (left < a.length && left < b.length && a[left] === b[left]) {
|
48 | left++
|
49 | }
|
50 | // If the last same character is a high surrogate, we need to rollback to the previous character
|
51 | if (left > 0 && highSurrogateRegex.test(a[left - 1])) left--
|
52 | while (right + left < a.length && right + left < b.length && a[a.length - right - 1] === b[b.length - right - 1]) {
|
53 | right++
|
54 | }
|
55 | // If the last same character is a low surrogate, we need to rollback to the previous character
|
56 | if (right > 0 && lowSurrogateRegex.test(a[a.length - right])) right--
|
57 | return {
|
58 | index: left,
|
59 | remove: a.length - left - right,
|
60 | insert: b.slice(left, b.length - right)
|
61 | }
|
62 | }
|
63 |
|
64 | /**
|
65 | * @todo Remove in favor of simpleDiffString
|
66 | * @deprecated
|
67 | */
|
68 | export const simpleDiff = simpleDiffString
|
69 |
|
70 | /**
|
71 | * Create a diff between two arrays. This diff implementation is highly
|
72 | * efficient, but not very sophisticated.
|
73 | *
|
74 | * Note: This is basically the same function as above. Another function was created so that the runtime
|
75 | * can better optimize these function calls.
|
76 | *
|
77 | * @function
|
78 | * @template T
|
79 | *
|
80 | * @param {Array<T>} a The old version of the array
|
81 | * @param {Array<T>} b The updated version of the array
|
82 | * @param {function(T, T):boolean} [compare]
|
83 | * @return {SimpleDiff<Array<T>>} The diff description.
|
84 | */
|
85 | export const simpleDiffArray = (a, b, compare = equalityStrict) => {
|
86 | let left = 0 // number of same characters counting from left
|
87 | let right = 0 // number of same characters counting from right
|
88 | while (left < a.length && left < b.length && compare(a[left], b[left])) {
|
89 | left++
|
90 | }
|
91 | while (right + left < a.length && right + left < b.length && compare(a[a.length - right - 1], b[b.length - right - 1])) {
|
92 | right++
|
93 | }
|
94 | return {
|
95 | index: left,
|
96 | remove: a.length - left - right,
|
97 | insert: b.slice(left, b.length - right)
|
98 | }
|
99 | }
|
100 |
|
101 | /**
|
102 | * Diff text and try to diff at the current cursor position.
|
103 | *
|
104 | * @param {string} a
|
105 | * @param {string} b
|
106 | * @param {number} cursor This should refer to the current left cursor-range position
|
107 | */
|
108 | export const simpleDiffStringWithCursor = (a, b, cursor) => {
|
109 | let left = 0 // number of same characters counting from left
|
110 | let right = 0 // number of same characters counting from right
|
111 | // Iterate left to the right until we find a changed character
|
112 | // First iteration considers the current cursor position
|
113 | while (
|
114 | left < a.length &&
|
115 | left < b.length &&
|
116 | a[left] === b[left] &&
|
117 | left < cursor
|
118 | ) {
|
119 | left++
|
120 | }
|
121 | // If the last same character is a high surrogate, we need to rollback to the previous character
|
122 | if (left > 0 && highSurrogateRegex.test(a[left - 1])) left--
|
123 | // Iterate right to the left until we find a changed character
|
124 | while (
|
125 | right + left < a.length &&
|
126 | right + left < b.length &&
|
127 | a[a.length - right - 1] === b[b.length - right - 1]
|
128 | ) {
|
129 | right++
|
130 | }
|
131 | // If the last same character is a low surrogate, we need to rollback to the previous character
|
132 | if (right > 0 && lowSurrogateRegex.test(a[a.length - right])) right--
|
133 | // Try to iterate left further to the right without caring about the current cursor position
|
134 | while (
|
135 | right + left < a.length &&
|
136 | right + left < b.length &&
|
137 | a[left] === b[left]
|
138 | ) {
|
139 | left++
|
140 | }
|
141 | if (left > 0 && highSurrogateRegex.test(a[left - 1])) left--
|
142 | return {
|
143 | index: left,
|
144 | remove: a.length - left - right,
|
145 | insert: b.slice(left, b.length - right)
|
146 | }
|
147 | }
|