1
// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license.
2
// This module is browser compatible.
3
 
4
/* TODO: the following is adopted code, enabling linting one day */
5
/* eslint-disable */
6
 
7
interface FarthestPoint {
8
  y: number;
9
  id: number;
10
}
11
 
12
export const DiffType = {
13
  removed: 'removed',
14
  common: 'common',
15
  added: 'added',
16
};
17
 
18
export interface DiffResult<T> {
19
  type: (typeof DiffType)[keyof typeof DiffType];
20
  value: T;
21
  details?: Array<DiffResult<T>>;
22
}
23
 
24
const REMOVED = 1;
25
const COMMON = 2;
26
const ADDED = 3;
27
 
28
function createCommon<T>(A: T[], B: T[], reverse?: boolean): T[] {
29
  const common = [];
30
  if (A.length === 0 || B.length === 0) return [];
31
  for (let i = 0; i < Math.min(A.length, B.length); i += 1) {
32
    if (
33
      A[reverse ? A.length - i - 1 : i] === B[reverse ? B.length - i - 1 : i]
34
    ) {
35
      common.push(A[reverse ? A.length - i - 1 : i]);
36
    } else {
37
      // @ts-ignore
38
      return common;
39
    }
40
  }
41
  // @ts-ignore
42
  return common;
43
}
44
 
45
/**
46
 * Renders the differences between the actual and expected values
47
 * @param A Actual value
48
 * @param B Expected value
49
 */
50
export function diff<T>(A: T[], B: T[]): Array<DiffResult<T>> {
51
  const prefixCommon = createCommon(A, B);
52
  const suffixCommon = createCommon(
53
    A.slice(prefixCommon.length),
54
    B.slice(prefixCommon.length),
55
    true
56
  ).reverse();
57
  A = suffixCommon.length
58
    ? A.slice(prefixCommon.length, -suffixCommon.length)
59
    : A.slice(prefixCommon.length);
60
  B = suffixCommon.length
61
    ? B.slice(prefixCommon.length, -suffixCommon.length)
62
    : B.slice(prefixCommon.length);
63
  const swapped = B.length > A.length;
64
  [A, B] = swapped ? [B, A] : [A, B];
65
  const M = A.length;
66
  const N = B.length;
67
  if (!M && !N && !suffixCommon.length && !prefixCommon.length) return [];
68
  if (!N) {
69
    return [
70
      ...prefixCommon.map(
71
        (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c })
72
      ),
73
      ...A.map(
74
        (a): DiffResult<typeof a> => ({
75
          type: swapped ? DiffType.added : DiffType.removed,
76
          value: a,
77
        })
78
      ),
79
      ...suffixCommon.map(
80
        (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c })
81
      ),
82
    ];
83
  }
84
  const offset = N;
85
  const delta = M - N;
86
  const size = M + N + 1;
87
  const fp: FarthestPoint[] = Array.from({ length: size }, () => ({
88
    y: -1,
89
    id: -1,
90
  }));
91
  /**
92
   * INFO:
93
   * This buffer is used to save memory and improve performance.
94
   * The first half is used to save route and last half is used to save diff
95
   * type.
96
   * This is because, when I kept new uint8array area to save type,performance
97
   * worsened.
98
   */
99
  const routes = new Uint32Array((M * N + size + 1) * 2);
100
  const diffTypesPtrOffset = routes.length / 2;
101
  let ptr = 0;
102
  let p = -1;
103
 
104
  function backTrace<T>(
105
    A: T[],
106
    B: T[],
107
    current: FarthestPoint,
108
    swapped: boolean
109
  ): Array<{
110
    type: (typeof DiffType)[keyof typeof DiffType];
111
    value: T;
112
  }> {
113
    const M = A.length;
114
    const N = B.length;
115
    const result = [];
116
    let a = M - 1;
117
    let b = N - 1;
118
    let j = routes[current.id];
119
    let type = routes[current.id + diffTypesPtrOffset];
120
    while (true) {
121
      if (!j && !type) break;
122
      const prev = j;
123
      if (type === REMOVED) {
124
        result.unshift({
125
          type: swapped ? DiffType.removed : DiffType.added,
126
          value: B[b],
127
        });
128
        b -= 1;
129
      } else if (type === ADDED) {
130
        result.unshift({
131
          type: swapped ? DiffType.added : DiffType.removed,
132
          value: A[a],
133
        });
134
        a -= 1;
135
      } else {
136
        result.unshift({ type: DiffType.common, value: A[a] });
137
        a -= 1;
138
        b -= 1;
139
      }
140
      // @ts-ignore
141
      j = routes[prev];
142
      // @ts-ignore
143
      type = routes[prev + diffTypesPtrOffset];
144
    }
145
    // @ts-ignore
146
    return result;
147
  }
148
 
149
  function createFP(
150
    slide: FarthestPoint,
151
    down: FarthestPoint,
152
    k: number,
153
    M: number
154
  ): FarthestPoint {
155
    if (slide && slide.y === -1 && down && down.y === -1) {
156
      return { y: 0, id: 0 };
157
    }
158
    if (
159
      (down && down.y === -1) ||
160
      k === M ||
161
      (slide && slide.y) > (down && down.y) + 1
162
    ) {
163
      const prev = slide.id;
164
      ptr++;
165
      routes[ptr] = prev;
166
      routes[ptr + diffTypesPtrOffset] = ADDED;
167
      return { y: slide.y, id: ptr };
168
    } else {
169
      const prev = down.id;
170
      ptr++;
171
      routes[ptr] = prev;
172
      routes[ptr + diffTypesPtrOffset] = REMOVED;
173
      return { y: down.y + 1, id: ptr };
174
    }
175
  }
176
 
177
  function snake<T>(
178
    k: number,
179
    slide: FarthestPoint,
180
    down: FarthestPoint,
181
    _offset: number,
182
    A: T[],
183
    B: T[]
184
  ): FarthestPoint {
185
    const M = A.length;
186
    const N = B.length;
187
    if (k < -N || M < k) return { y: -1, id: -1 };
188
    const fp = createFP(slide, down, k, M);
189
    while (fp.y + k < M && fp.y < N && A[fp.y + k] === B[fp.y]) {
190
      const prev = fp.id;
191
      ptr++;
192
      fp.id = ptr;
193
      fp.y += 1;
194
      routes[ptr] = prev;
195
      routes[ptr + diffTypesPtrOffset] = COMMON;
196
    }
197
    return fp;
198
  }
199
 
200
  // @ts-ignore
201
  while (fp[delta + offset].y < N) {
202
    p = p + 1;
203
    for (let k = -p; k < delta; ++k) {
204
      fp[k + offset] = snake(
205
        k,
206
        // @ts-ignore
207
        fp[k - 1 + offset],
208
        fp[k + 1 + offset],
209
        offset,
210
        A,
211
        B
212
      );
213
    }
214
    for (let k = delta + p; k > delta; --k) {
215
      fp[k + offset] = snake(
216
        k,
217
        // @ts-ignore
218
        fp[k - 1 + offset],
219
        fp[k + 1 + offset],
220
        offset,
221
        A,
222
        B
223
      );
224
    }
225
    fp[delta + offset] = snake(
226
      delta,
227
      // @ts-ignore
228
      fp[delta - 1 + offset],
229
      fp[delta + 1 + offset],
230
      offset,
231
      A,
232
      B
233
    );
234
  }
235
  return [
236
    ...prefixCommon.map(
237
      (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c })
238
    ),
239
    // @ts-ignore
240
    ...backTrace(A, B, fp[delta + offset], swapped),
241
    ...suffixCommon.map(
242
      (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c })
243
    ),
244
  ];
245
}
246
 
247
/**
248
 * Renders the differences between the actual and expected strings
249
 * Partially inspired from https://github.com/kpdecker/jsdiff
250
 * @param A Actual string
251
 * @param B Expected string
252
 */
253
export function diffstr(A: string, B: string) {
254
  function unescape(string: string): string {
255
    // unescape invisible characters.
256
    // ref: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String#escape_sequences
257
    return string
258
      .replaceAll('\b', '\\b')
259
      .replaceAll('\f', '\\f')
260
      .replaceAll('\t', '\\t')
261
      .replaceAll('\v', '\\v')
262
      .replaceAll(
263
        // does not remove line breaks
264
        /\r\n|\r|\n/g,
265
        (str) => (str === '\r' ? '\\r' : str === '\n' ? '\\n\n' : '\\r\\n\r\n')
266
      );
267
  }
268
 
269
  function tokenize(string: string, { wordDiff = false } = {}): string[] {
270
    if (wordDiff) {
271
      // Split string on whitespace symbols
272
      const tokens = string.split(/([^\S\r\n]+|[()[\]{}'"\r\n]|\b)/);
273
      // Extended Latin character set
274
      const words =
275
        /^[a-zA-Z\u{C0}-\u{FF}\u{D8}-\u{F6}\u{F8}-\u{2C6}\u{2C8}-\u{2D7}\u{2DE}-\u{2FF}\u{1E00}-\u{1EFF}]+$/u;
276
 
277
      // Join boundary splits that we do not consider to be boundaries and merge empty strings surrounded by word chars
278
      for (let i = 0; i < tokens.length - 1; i++) {
279
        if (
280
          !tokens[i + 1] &&
281
          tokens[i + 2] &&
282
          // @ts-ignore
283
          words.test(tokens[i]) &&
284
          // @ts-ignore
285
          words.test(tokens[i + 2])
286
        ) {
287
          tokens[i] += tokens[i + 2] as string;
288
          tokens.splice(i + 1, 2);
289
          i--;
290
        }
291
      }
292
      return tokens.filter((token) => token);
293
    } else {
294
      // Split string on new lines symbols
295
      const tokens = [],
296
        lines = string.split(/(\n|\r\n)/);
297
 
298
      // Ignore final empty token when text ends with a newline
299
      if (!lines[lines.length - 1]) {
300
        lines.pop();
301
      }
302
 
303
      // Merge the content and line separators into single tokens
304
      for (let i = 0; i < lines.length; i++) {
305
        if (i % 2) {
306
          // @ts-ignore
307
          tokens[tokens.length - 1] += lines[i];
308
        } else {
309
          tokens.push(lines[i]);
310
        }
311
      }
312
      // @ts-ignore
313
      return tokens;
314
    }
315
  }
316
 
317
  // Create details by filtering relevant word-diff for current line
318
  // and merge "space-diff" if surrounded by word-diff for cleaner displays
319
  function createDetails(
320
    line: DiffResult<string>,
321
    tokens: Array<DiffResult<string>>
322
  ) {
323
    return tokens
324
      .filter(({ type }) => type === line.type || type === DiffType.common)
325
      .map((result, i, t) => {
326
        if (
327
          result.type === DiffType.common &&
328
          t[i - 1] &&
329
          t[i - 1]?.type === t[i + 1]?.type &&
330
          /\s+/.test(result.value)
331
        ) {
332
          return {
333
            ...result,
334
            // @ts-ignore
335
            type: t[i - 1].type,
336
          };
337
        }
338
        return result;
339
      });
340
  }
341
 
342
  // Compute multi-line diff
343
  const diffResult = diff(
344
    tokenize(`${unescape(A)}\n`),
345
    tokenize(`${unescape(B)}\n`)
346
  );
347
 
348
  const added = [],
349
    removed = [];
350
  for (const result of diffResult) {
351
    if (result.type === DiffType.added) {
352
      added.push(result);
353
    }
354
    if (result.type === DiffType.removed) {
355
      removed.push(result);
356
    }
357
  }
358
 
359
  // Compute word-diff
360
  const aLines = added.length < removed.length ? added : removed;
361
  const bLines = aLines === removed ? added : removed;
362
  for (const a of aLines) {
363
    let tokens = [] as Array<DiffResult<string>>,
364
      b: undefined | DiffResult<string>;
365
    // Search another diff line with at least one common token
366
    while (bLines.length) {
367
      b = bLines.shift();
368
      tokens = diff(
369
        tokenize(a.value, { wordDiff: true }),
370
        tokenize(b?.value ?? '', { wordDiff: true })
371
      );
372
      if (
373
        tokens.some(
374
          ({ type, value }) => type === DiffType.common && value.trim().length
375
        )
376
      ) {
377
        break;
378
      }
379
    }
380
    // Register word-diff details
381
    a.details = createDetails(a, tokens);
382
    if (b) {
383
      b.details = createDetails(b, tokens);
384
    }
385
  }
386
 
387
  return diffResult;
388
}
389
 
390
/**
391
 * Prefixes `+` or `-` in diff output
392
 * @param diffType Difference type, either added or removed
393
 */
394
function createSign(
395
  diffType: (typeof DiffType)[keyof typeof DiffType]
396
): string {
397
  switch (diffType) {
398
    case DiffType.added:
399
      return '+   ';
400
    case DiffType.removed:
401
      return '-   ';
402
    default:
403
      return '    ';
404
  }
405
}
406
 
407
export function buildMessage(
408
  diffResult: ReadonlyArray<DiffResult<string>>,
409
  { stringDiff = false } = {}
410
): string[] {
411
  const messages: string[] = [],
412
    diffMessages: string[] = [];
413
  messages.push('');
414
  messages.push('');
415
  messages.push('[Diff] Actual / Expected');
416
  messages.push('');
417
  messages.push('');
418
  diffResult.forEach((result: DiffResult<string>) => {
419
    const line =
420
      result.details?.map((detail) => detail.value).join('') ?? result.value;
421
    diffMessages.push(`${createSign(result.type)}${line}`);
422
  });
423
  messages.push(...(stringDiff ? [diffMessages.join('')] : diffMessages));
424
  messages.push('');
425
 
426
  return messages;
427
}