From 5590b97670206df957c43742f47601356982c658 Mon Sep 17 00:00:00 2001 From: tokiedokie Date: Fri, 2 Oct 2020 02:15:05 +0900 Subject: refactor(std/testing): Get rid of default export and make std/testing/diff.ts private (#7592) --- std/testing/_diff.ts | 223 ++++++++++++++++++++++++++++++++++++++++++++++ std/testing/_diff_test.ts | 111 +++++++++++++++++++++++ std/testing/asserts.ts | 2 +- std/testing/diff.ts | 223 ---------------------------------------------- std/testing/diff_test.ts | 111 ----------------------- 5 files changed, 335 insertions(+), 335 deletions(-) create mode 100644 std/testing/_diff.ts create mode 100644 std/testing/_diff_test.ts delete mode 100644 std/testing/diff.ts delete mode 100644 std/testing/diff_test.ts (limited to 'std/testing') diff --git a/std/testing/_diff.ts b/std/testing/_diff.ts new file mode 100644 index 000000000..5c84e891f --- /dev/null +++ b/std/testing/_diff.ts @@ -0,0 +1,223 @@ +// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license. +/** This module is browser compatible. */ + +interface FarthestPoint { + y: number; + id: number; +} + +export enum DiffType { + removed = "removed", + common = "common", + added = "added", +} + +export interface DiffResult { + type: DiffType; + value: T; +} + +const REMOVED = 1; +const COMMON = 2; +const ADDED = 3; + +function createCommon(A: T[], B: T[], reverse?: boolean): T[] { + const common = []; + if (A.length === 0 || B.length === 0) return []; + for (let i = 0; i < Math.min(A.length, B.length); i += 1) { + if ( + A[reverse ? A.length - i - 1 : i] === B[reverse ? B.length - i - 1 : i] + ) { + common.push(A[reverse ? A.length - i - 1 : i]); + } else { + return common; + } + } + return common; +} + +export function diff(A: T[], B: T[]): Array> { + 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 => ({ type: DiffType.common, value: c }), + ), + ...A.map( + (a): DiffResult => ({ + type: swapped ? DiffType.added : DiffType.removed, + value: a, + }), + ), + ...suffixCommon.map( + (c): DiffResult => ({ type: DiffType.common, value: c }), + ), + ]; + } + const offset = N; + const delta = M - N; + const size = M + N + 1; + const fp = new Array(size).fill({ y: -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( + A: T[], + B: T[], + current: FarthestPoint, + swapped: boolean, + ): Array<{ + type: DiffType; + value: T; + }> { + const M = A.length; + const N = B.length; + const result = []; + 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, + down: FarthestPoint, + k: number, + M: number, + ): FarthestPoint { + if (slide && slide.y === -1 && down && down.y === -1) { + return { y: 0, id: 0 }; + } + if ( + (down && down.y === -1) || + k === M || + (slide && slide.y) > (down && down.y) + 1 + ) { + const prev = slide.id; + ptr++; + routes[ptr] = prev; + routes[ptr + diffTypesPtrOffset] = ADDED; + return { y: slide.y, id: ptr }; + } else { + const prev = down.id; + ptr++; + routes[ptr] = prev; + routes[ptr + diffTypesPtrOffset] = REMOVED; + return { y: down.y + 1, id: ptr }; + } + } + + function snake( + k: number, + slide: FarthestPoint, + down: FarthestPoint, + _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; + } + + while (fp[delta + offset].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, + ); + } + return [ + ...prefixCommon.map( + (c): DiffResult => ({ type: DiffType.common, value: c }), + ), + ...backTrace(A, B, fp[delta + offset], swapped), + ...suffixCommon.map( + (c): DiffResult => ({ type: DiffType.common, value: c }), + ), + ]; +} diff --git a/std/testing/_diff_test.ts b/std/testing/_diff_test.ts new file mode 100644 index 000000000..211a34c34 --- /dev/null +++ b/std/testing/_diff_test.ts @@ -0,0 +1,111 @@ +// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license. +import { diff } from "./_diff.ts"; +import { assertEquals } from "../testing/asserts.ts"; + +Deno.test({ + name: "empty", + fn(): void { + assertEquals(diff([], []), []); + }, +}); + +Deno.test({ + name: '"a" vs "b"', + fn(): void { + assertEquals(diff(["a"], ["b"]), [ + { type: "removed", value: "a" }, + { type: "added", value: "b" }, + ]); + }, +}); + +Deno.test({ + name: '"a" vs "a"', + fn(): void { + assertEquals(diff(["a"], ["a"]), [{ type: "common", value: "a" }]); + }, +}); + +Deno.test({ + name: '"a" vs ""', + fn(): void { + assertEquals(diff(["a"], []), [{ type: "removed", value: "a" }]); + }, +}); + +Deno.test({ + name: '"" vs "a"', + fn(): void { + assertEquals(diff([], ["a"]), [{ type: "added", value: "a" }]); + }, +}); + +Deno.test({ + name: '"a" vs "a, b"', + fn(): void { + assertEquals(diff(["a"], ["a", "b"]), [ + { type: "common", value: "a" }, + { type: "added", value: "b" }, + ]); + }, +}); + +Deno.test({ + name: '"strength" vs "string"', + fn(): void { + assertEquals(diff(Array.from("strength"), Array.from("string")), [ + { type: "common", value: "s" }, + { type: "common", value: "t" }, + { type: "common", value: "r" }, + { type: "removed", value: "e" }, + { type: "added", value: "i" }, + { type: "common", value: "n" }, + { type: "common", value: "g" }, + { type: "removed", value: "t" }, + { type: "removed", value: "h" }, + ]); + }, +}); + +Deno.test({ + name: '"strength" vs ""', + fn(): void { + assertEquals(diff(Array.from("strength"), Array.from("")), [ + { type: "removed", value: "s" }, + { type: "removed", value: "t" }, + { type: "removed", value: "r" }, + { type: "removed", value: "e" }, + { type: "removed", value: "n" }, + { type: "removed", value: "g" }, + { type: "removed", value: "t" }, + { type: "removed", value: "h" }, + ]); + }, +}); + +Deno.test({ + name: '"" vs "strength"', + fn(): void { + assertEquals(diff(Array.from(""), Array.from("strength")), [ + { type: "added", value: "s" }, + { type: "added", value: "t" }, + { type: "added", value: "r" }, + { type: "added", value: "e" }, + { type: "added", value: "n" }, + { type: "added", value: "g" }, + { type: "added", value: "t" }, + { type: "added", value: "h" }, + ]); + }, +}); + +Deno.test({ + name: '"abc", "c" vs "abc", "bcd", "c"', + fn(): void { + assertEquals(diff(["abc", "c"], ["abc", "bcd", "c"]), [ + { type: "common", value: "abc" }, + { type: "added", value: "bcd" }, + { type: "common", value: "c" }, + ]); + }, +}); diff --git a/std/testing/asserts.ts b/std/testing/asserts.ts index 889a622fd..f93e043dc 100644 --- a/std/testing/asserts.ts +++ b/std/testing/asserts.ts @@ -3,7 +3,7 @@ * for AssertionError messages in browsers. */ import { bold, gray, green, red, stripColor, white } from "../fmt/colors.ts"; -import diff, { DiffResult, DiffType } from "./diff.ts"; +import { diff, DiffResult, DiffType } from "./_diff.ts"; const CAN_NOT_DISPLAY = "[Cannot display]"; diff --git a/std/testing/diff.ts b/std/testing/diff.ts deleted file mode 100644 index 3a9eca4bb..000000000 --- a/std/testing/diff.ts +++ /dev/null @@ -1,223 +0,0 @@ -// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license. -/** This module is browser compatible. */ - -interface FarthestPoint { - y: number; - id: number; -} - -export enum DiffType { - removed = "removed", - common = "common", - added = "added", -} - -export interface DiffResult { - type: DiffType; - value: T; -} - -const REMOVED = 1; -const COMMON = 2; -const ADDED = 3; - -function createCommon(A: T[], B: T[], reverse?: boolean): T[] { - const common = []; - if (A.length === 0 || B.length === 0) return []; - for (let i = 0; i < Math.min(A.length, B.length); i += 1) { - if ( - A[reverse ? A.length - i - 1 : i] === B[reverse ? B.length - i - 1 : i] - ) { - common.push(A[reverse ? A.length - i - 1 : i]); - } else { - return common; - } - } - return common; -} - -export default function diff(A: T[], B: T[]): Array> { - 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 => ({ type: DiffType.common, value: c }), - ), - ...A.map( - (a): DiffResult => ({ - type: swapped ? DiffType.added : DiffType.removed, - value: a, - }), - ), - ...suffixCommon.map( - (c): DiffResult => ({ type: DiffType.common, value: c }), - ), - ]; - } - const offset = N; - const delta = M - N; - const size = M + N + 1; - const fp = new Array(size).fill({ y: -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( - A: T[], - B: T[], - current: FarthestPoint, - swapped: boolean, - ): Array<{ - type: DiffType; - value: T; - }> { - const M = A.length; - const N = B.length; - const result = []; - 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, - down: FarthestPoint, - k: number, - M: number, - ): FarthestPoint { - if (slide && slide.y === -1 && down && down.y === -1) { - return { y: 0, id: 0 }; - } - if ( - (down && down.y === -1) || - k === M || - (slide && slide.y) > (down && down.y) + 1 - ) { - const prev = slide.id; - ptr++; - routes[ptr] = prev; - routes[ptr + diffTypesPtrOffset] = ADDED; - return { y: slide.y, id: ptr }; - } else { - const prev = down.id; - ptr++; - routes[ptr] = prev; - routes[ptr + diffTypesPtrOffset] = REMOVED; - return { y: down.y + 1, id: ptr }; - } - } - - function snake( - k: number, - slide: FarthestPoint, - down: FarthestPoint, - _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; - } - - while (fp[delta + offset].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, - ); - } - return [ - ...prefixCommon.map( - (c): DiffResult => ({ type: DiffType.common, value: c }), - ), - ...backTrace(A, B, fp[delta + offset], swapped), - ...suffixCommon.map( - (c): DiffResult => ({ type: DiffType.common, value: c }), - ), - ]; -} diff --git a/std/testing/diff_test.ts b/std/testing/diff_test.ts deleted file mode 100644 index 33752d89f..000000000 --- a/std/testing/diff_test.ts +++ /dev/null @@ -1,111 +0,0 @@ -// Copyright 2018-2020 the Deno authors. All rights reserved. MIT license. -import diff from "./diff.ts"; -import { assertEquals } from "../testing/asserts.ts"; - -Deno.test({ - name: "empty", - fn(): void { - assertEquals(diff([], []), []); - }, -}); - -Deno.test({ - name: '"a" vs "b"', - fn(): void { - assertEquals(diff(["a"], ["b"]), [ - { type: "removed", value: "a" }, - { type: "added", value: "b" }, - ]); - }, -}); - -Deno.test({ - name: '"a" vs "a"', - fn(): void { - assertEquals(diff(["a"], ["a"]), [{ type: "common", value: "a" }]); - }, -}); - -Deno.test({ - name: '"a" vs ""', - fn(): void { - assertEquals(diff(["a"], []), [{ type: "removed", value: "a" }]); - }, -}); - -Deno.test({ - name: '"" vs "a"', - fn(): void { - assertEquals(diff([], ["a"]), [{ type: "added", value: "a" }]); - }, -}); - -Deno.test({ - name: '"a" vs "a, b"', - fn(): void { - assertEquals(diff(["a"], ["a", "b"]), [ - { type: "common", value: "a" }, - { type: "added", value: "b" }, - ]); - }, -}); - -Deno.test({ - name: '"strength" vs "string"', - fn(): void { - assertEquals(diff(Array.from("strength"), Array.from("string")), [ - { type: "common", value: "s" }, - { type: "common", value: "t" }, - { type: "common", value: "r" }, - { type: "removed", value: "e" }, - { type: "added", value: "i" }, - { type: "common", value: "n" }, - { type: "common", value: "g" }, - { type: "removed", value: "t" }, - { type: "removed", value: "h" }, - ]); - }, -}); - -Deno.test({ - name: '"strength" vs ""', - fn(): void { - assertEquals(diff(Array.from("strength"), Array.from("")), [ - { type: "removed", value: "s" }, - { type: "removed", value: "t" }, - { type: "removed", value: "r" }, - { type: "removed", value: "e" }, - { type: "removed", value: "n" }, - { type: "removed", value: "g" }, - { type: "removed", value: "t" }, - { type: "removed", value: "h" }, - ]); - }, -}); - -Deno.test({ - name: '"" vs "strength"', - fn(): void { - assertEquals(diff(Array.from(""), Array.from("strength")), [ - { type: "added", value: "s" }, - { type: "added", value: "t" }, - { type: "added", value: "r" }, - { type: "added", value: "e" }, - { type: "added", value: "n" }, - { type: "added", value: "g" }, - { type: "added", value: "t" }, - { type: "added", value: "h" }, - ]); - }, -}); - -Deno.test({ - name: '"abc", "c" vs "abc", "bcd", "c"', - fn(): void { - assertEquals(diff(["abc", "c"], ["abc", "bcd", "c"]), [ - { type: "common", value: "abc" }, - { type: "added", value: "bcd" }, - { type: "common", value: "c" }, - ]); - }, -}); -- cgit v1.2.3