deno.land / std@0.224.0 / internal / diff.ts
diff.ts
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466// Copyright 2018-2024 the Deno authors. All rights reserved. MIT license.// This module is browser compatible.
import { bgGreen, bgRed, bold, gray, green, red, white,} from "../fmt/colors.ts";
interface FarthestPoint { y: number; id: number;}
export const DiffType = { removed: "removed", common: "common", added: "added",} as const;
export type DiffType = keyof typeof DiffType;
export interface DiffResult<T> { type: DiffType; value: T; details?: Array<DiffResult<T>>;}
const REMOVED = 1;const COMMON = 2;const ADDED = 3;
function createCommon<T>(A: T[], B: T[], reverse?: boolean): T[] { const common: T[] = []; if (A.length === 0 || B.length === 0) return []; for (let i = 0; i < Math.min(A.length, B.length); i += 1) { const a = reverse ? A[A.length - i - 1] : A[i]; const b = reverse ? B[B.length - i - 1] : B[i]; if (a !== undefined && a === b) { common.push(a); } else { return common; } } return common;}
function ensureDefined<T>(item?: T): T { if (item === undefined) { throw Error("Unexpected missing FarthestPoint"); } return item;}
/** * Renders the differences between the actual and expected values * @param A Actual value * @param B Expected value */export function diff<T>(A: T[], B: T[]): Array<DiffResult<T>> { const prefixCommon = createCommon(A, B); const suffixCommon = createCommon( A.slice(prefixCommon.length), B.slice(prefixCommon.length), true, ).reverse(); A = suffixCommon.length ? A.slice(prefixCommon.length, -suffixCommon.length) : A.slice(prefixCommon.length); B = suffixCommon.length ? B.slice(prefixCommon.length, -suffixCommon.length) : B.slice(prefixCommon.length); const swapped = B.length > A.length; [A, B] = swapped ? [B, A] : [A, B]; const M = A.length; const N = B.length; if (!M && !N && !suffixCommon.length && !prefixCommon.length) return []; if (!N) { return [ ...prefixCommon.map( (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c }), ), ...A.map( (a): DiffResult<typeof a> => ({ type: swapped ? DiffType.added : DiffType.removed, value: a, }), ), ...suffixCommon.map( (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c }), ), ]; } const offset = N; const delta = M - N; const size = M + N + 1; const fp: FarthestPoint[] = Array.from( { length: size }, () => ({ y: -1, id: -1 }), );
/** * INFO: * This buffer is used to save memory and improve performance. * The first half is used to save route and last half is used to save diff * type. * This is because, when I kept new uint8array area to save type,performance * worsened. */ const routes = new Uint32Array((M * N + size + 1) * 2); const diffTypesPtrOffset = routes.length / 2; let ptr = 0; let p = -1;
function backTrace<T>( A: T[], B: T[], current: FarthestPoint, swapped: boolean, ): Array<{ type: DiffType; value: T; }> { const M = A.length; const N = B.length; const result: { type: DiffType; value: T }[] = []; let a = M - 1; let b = N - 1; let j = routes[current.id]; let type = routes[current.id + diffTypesPtrOffset]; while (true) { if (!j && !type) break; const prev = j!; if (type === REMOVED) { result.unshift({ type: swapped ? DiffType.removed : DiffType.added, value: B[b]!, }); b -= 1; } else if (type === ADDED) { result.unshift({ type: swapped ? DiffType.added : DiffType.removed, value: A[a]!, }); a -= 1; } else { result.unshift({ type: DiffType.common, value: A[a]! }); a -= 1; b -= 1; } j = routes[prev]; type = routes[prev + diffTypesPtrOffset]; } return result; }
function createFP( slide: FarthestPoint | undefined, down: FarthestPoint | undefined, k: number, M: number, ): FarthestPoint { if (slide && slide.y === -1 && down && down.y === -1) { return { y: 0, id: 0 }; } const isAdding = (down?.y === -1) || k === M || (slide?.y || 0) > (down?.y || 0) + 1; if (slide && isAdding) { const prev = slide.id; ptr++; routes[ptr] = prev; routes[ptr + diffTypesPtrOffset] = ADDED; return { y: slide.y, id: ptr }; } else if (down && !isAdding) { const prev = down.id; ptr++; routes[ptr] = prev; routes[ptr + diffTypesPtrOffset] = REMOVED; return { y: down.y + 1, id: ptr }; } else { throw new Error("Unexpected missing FarthestPoint"); } }
function snake<T>( k: number, slide: FarthestPoint | undefined, down: FarthestPoint | undefined, _offset: number, A: T[], B: T[], ): FarthestPoint { const M = A.length; const N = B.length; if (k < -N || M < k) return { y: -1, id: -1 }; const fp = createFP(slide, down, k, M); while (fp.y + k < M && fp.y < N && A[fp.y + k] === B[fp.y]) { const prev = fp.id; ptr++; fp.id = ptr; fp.y += 1; routes[ptr] = prev; routes[ptr + diffTypesPtrOffset] = COMMON; } return fp; }
let currentFP = ensureDefined<FarthestPoint>(fp[delta + offset]); while (currentFP && currentFP.y < N) { p = p + 1; for (let k = -p; k < delta; ++k) { fp[k + offset] = snake( k, fp[k - 1 + offset], fp[k + 1 + offset], offset, A, B, ); } for (let k = delta + p; k > delta; --k) { fp[k + offset] = snake( k, fp[k - 1 + offset], fp[k + 1 + offset], offset, A, B, ); } fp[delta + offset] = snake( delta, fp[delta - 1 + offset], fp[delta + 1 + offset], offset, A, B, ); currentFP = ensureDefined(fp[delta + offset]); } return [ ...prefixCommon.map( (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c }), ), ...backTrace(A, B, currentFP, swapped), ...suffixCommon.map( (c): DiffResult<typeof c> => ({ type: DiffType.common, value: c }), ), ];}
/** * Renders the differences between the actual and expected strings * Partially inspired from https://github.com/kpdecker/jsdiff * @param A Actual string * @param B Expected string */export function diffstr(A: string, B: string): DiffResult<string>[] { function unescape(string: string): string { // unescape invisible characters. // ref: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String#escape_sequences return string .replaceAll("\b", "\\b") .replaceAll("\f", "\\f") .replaceAll("\t", "\\t") .replaceAll("\v", "\\v") .replaceAll( // does not remove line breaks /\r\n|\r|\n/g, (str) => str === "\r" ? "\\r" : str === "\n" ? "\\n\n" : "\\r\\n\r\n", ); }
function tokenize(string: string, { wordDiff = false } = {}): string[] { if (wordDiff) { // Split string on whitespace symbols const tokens = string.split(/([^\S\r\n]+|[()[\]{}'"\r\n]|\b)/); // Extended Latin character set const words = /^[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;
// Join boundary splits that we do not consider to be boundaries and merge empty strings surrounded by word chars for (let i = 0; i < tokens.length - 1; i++) { const token = tokens[i]; const tokenPlusTwo = tokens[i + 2]; if ( !tokens[i + 1] && token && tokenPlusTwo && words.test(token) && words.test(tokenPlusTwo) ) { tokens[i] += tokenPlusTwo; tokens.splice(i + 1, 2); i--; } } return tokens.filter((token) => token); } else { // Split string on new lines symbols const tokens: string[] = []; const lines = string.split(/(\n|\r\n)/);
// Ignore final empty token when text ends with a newline if (!lines[lines.length - 1]) { lines.pop(); }
// Merge the content and line separators into single tokens for (const [i, line] of lines.entries()) { if (i % 2) { tokens[tokens.length - 1] += line; } else { tokens.push(line); } } return tokens; } }
// Create details by filtering relevant word-diff for current line // and merge "space-diff" if surrounded by word-diff for cleaner displays function createDetails( line: DiffResult<string>, tokens: Array<DiffResult<string>>, ) { return tokens.filter(({ type }) => type === line.type || type === DiffType.common ).map((result, i, t) => { const token = t[i - 1]; if ( (result.type === DiffType.common) && token && (token.type === t[i + 1]?.type) && /\s+/.test(result.value) ) { return { ...result, type: token.type, }; } return result; }); }
// Compute multi-line diff const diffResult = diff( tokenize(`${unescape(A)}\n`), tokenize(`${unescape(B)}\n`), );
const added = []; const removed = []; for (const result of diffResult) { if (result.type === DiffType.added) { added.push(result); } if (result.type === DiffType.removed) { removed.push(result); } }
// Compute word-diff const hasMoreRemovedLines = added.length < removed.length; const aLines = hasMoreRemovedLines ? added : removed; const bLines = hasMoreRemovedLines ? removed : added; for (const a of aLines) { let tokens = [] as Array<DiffResult<string>>; let b: undefined | DiffResult<string>; // Search another diff line with at least one common token while (bLines.length) { b = bLines.shift(); const tokenized = [ tokenize(a.value, { wordDiff: true }), tokenize(b?.value ?? "", { wordDiff: true }), ] as [string[], string[]]; if (hasMoreRemovedLines) tokenized.reverse(); tokens = diff(tokenized[0], tokenized[1]); if ( tokens.some(({ type, value }) => type === DiffType.common && value.trim().length ) ) { break; } } // Register word-diff details a.details = createDetails(a, tokens); if (b) { b.details = createDetails(b, tokens); } }
return diffResult;}
/** * Colors the output of assertion diffs * @param diffType Difference type, either added or removed */function createColor( diffType: DiffType, { background = false } = {},): (s: string) => string { // TODO(@littledivy): Remove this when we can detect // true color terminals. // https://github.com/denoland/deno_std/issues/2575 background = false; switch (diffType) { case DiffType.added: return (s: string): string => background ? bgGreen(white(s)) : green(bold(s)); case DiffType.removed: return (s: string): string => background ? bgRed(white(s)) : red(bold(s)); default: return white; }}
/** * Prefixes `+` or `-` in diff output * @param diffType Difference type, either added or removed */function createSign(diffType: DiffType): string { switch (diffType) { case DiffType.added: return "+ "; case DiffType.removed: return "- "; default: return " "; }}
export function buildMessage( diffResult: ReadonlyArray<DiffResult<string>>, { stringDiff = false } = {},): string[] { const messages: string[] = []; const diffMessages: string[] = []; messages.push(""); messages.push(""); messages.push( ` ${gray(bold("[Diff]"))} ${red(bold("Actual"))} / ${ green(bold("Expected")) }`, ); messages.push(""); messages.push(""); diffResult.forEach((result: DiffResult<string>) => { const c = createColor(result.type); const line = result.details?.map((detail) => detail.type !== DiffType.common ? createColor(detail.type, { background: true })(detail.value) : detail.value ).join("") ?? result.value; diffMessages.push(c(`${createSign(result.type)}${line}`)); }); messages.push(...(stringDiff ? [diffMessages.join("")] : diffMessages)); messages.push("");
return messages;}
std
Version Info
6 months ago
