ujsx/test/lis-move-detection.test.ts

import { describe, it, expect } from "vitest";
import type { Fiber } from "../src/host/fiber.js";
import type { UNode } from "../src/core/schema.js";
import { longestIncreasingSubsequence, reconcileChildren } from "../src/host/reconcile.js";

function makeFiber(key: string | undefined, tag: string): Fiber<string> {
  return {
    instance: `inst-${tag}-${key ?? "nokey"}`,
    tag,
    props: {},
    key,
    children: [],
    parent: null,
    effect: null,
    signalDisposers: [],
    prevProps: null,
    cachedNode: null,
  };
}

function makeElement(type: string, key?: string): UNode {
  return { type, props: {}, children: [], ...(key !== undefined ? { key } : {}) };
}

describe("longestIncreasingSubsequence", () => {
  it("empty array → empty result", () => {
    expect(longestIncreasingSubsequence([])).toEqual([]);
  });

  it("single element → [0]", () => {
    expect(longestIncreasingSubsequence([5])).toEqual([0]);
  });

  it("already ordered [0, 1, 2] → all stay", () => {
    const result = longestIncreasingSubsequence([0, 1, 2]);
    expect(result).toEqual([0, 1, 2]);
  });

  it("[2, 0, 1] → LIS positions: [1, 2] (values 0, 1 stay)", () => {
    const result = longestIncreasingSubsequence([2, 0, 1]);
    expect(result).toEqual([1, 2]);
    const moved = [0, 1, 2].filter((i) => !result.includes(i));
    expect(moved).toEqual([0]);
  });

  it("reversed [3, 2, 1, 0] → LIS length 1, three moves", () => {
    const result = longestIncreasingSubsequence([3, 2, 1, 0]);
    expect(result).toHaveLength(1);
    const moved = [0, 1, 2, 3].filter((i) => !result.includes(i));
    expect(moved).toHaveLength(3);
  });

  it("[0, 4, 2, 3, 1] → LIS covers 0, 2, 3", () => {
    const result = longestIncreasingSubsequence([0, 4, 2, 3, 1]);
    expect(result.length).toBeGreaterThanOrEqual(3);
    const vals = result.map((i) => [0, 4, 2, 3, 1][i]!);
    for (let i = 1; i < vals.length; i++) {
      expect(vals[i]).toBeGreaterThan(vals[i - 1]!);
    }
  });
});

describe("reconcileChildren LIS move detection", () => {
  it("already ordered children → no moves", () => {
    const oldFibers = [
      makeFiber("a", "div"),
      makeFiber("b", "span"),
      makeFiber("c", "p"),
    ];
    const newChildren = [
      makeElement("div", "a"),
      makeElement("span", "b"),
      makeElement("p", "c"),
    ];
    const result = reconcileChildren(oldFibers, newChildren);
    expect(result.moves.size).toBe(0);
  });

  it("reordered children → moves for out-of-order", () => {
    const oldFibers = [
      makeFiber("a", "div"),
      makeFiber("b", "span"),
      makeFiber("c", "p"),
    ];
    const newChildren = [
      makeElement("p", "c"),
      makeElement("div", "a"),
      makeElement("span", "b"),
    ];
    const result = reconcileChildren(oldFibers, newChildren);
    expect(result.moves.size).toBeGreaterThan(0);
    expect(result.matched).toHaveLength(3);
  });

  it("adding child at start doesn't move existing ones (LIS covers all old)", () => {
    const oldFibers = [
      makeFiber("b", "span"),
      makeFiber("c", "p"),
    ];
    const newChildren = [
      makeElement("div", "a"),
      makeElement("span", "b"),
      makeElement("p", "c"),
    ];
    const result = reconcileChildren(oldFibers, newChildren);

    expect(result.matched).toHaveLength(2);
    expect(result.added).toHaveLength(1);
    expect(result.moves.size).toBe(0);
  });

  it("reversed list → LIS of length 1, three moves", () => {
    const oldFibers = [
      makeFiber("a", "div"),
      makeFiber("b", "span"),
      makeFiber("c", "p"),
      makeFiber("d", "section"),
    ];
    const newChildren = [
      makeElement("section", "d"),
      makeElement("p", "c"),
      makeElement("span", "b"),
      makeElement("div", "a"),
    ];
    const result = reconcileChildren(oldFibers, newChildren);
    expect(result.matched).toHaveLength(4);
    expect(result.moves.size).toBe(3);
  });

  it("[2, 0, 1] pattern → index 0 stays, indices 2 and 1 move", () => {
    const oldFibers = [
      makeFiber("a", "div"),
      makeFiber("b", "span"),
      makeFiber("c", "p"),
    ];
    const newChildren = [
      makeElement("p", "c"),
      makeElement("div", "a"),
      makeElement("span", "b"),
    ];
    const result = reconcileChildren(oldFibers, newChildren);

    const oldIndices = result.matched.map((m) => oldFibers.indexOf(m.oldFiber));
    const lisPositions = longestIncreasingSubsequence(oldIndices);
    const lisSet = new Set(lisPositions);

    const movedIndices = result.matched
      .map((_, i) => i)
      .filter((i) => !lisSet.has(i));
    expect(movedIndices.length).toBeGreaterThan(0);

    const stayedIndices = result.matched
      .map((_, i) => i)
      .filter((i) => lisSet.has(i));
    expect(stayedIndices.length).toBeGreaterThan(0);
  });

  it("moves map contains old fibers that need moving", () => {
    const oldFibers = [
      makeFiber("a", "div"),
      makeFiber("b", "span"),
    ];
    const newChildren = [
      makeElement("span", "b"),
      makeElement("div", "a"),
    ];
    const result = reconcileChildren(oldFibers, newChildren);

    expect(result.moves.size).toBe(1);
    for (const fiber of result.moves.values()) {
      expect(oldFibers).toContain(fiber);
    }
  });

  it("no matched children → empty moves", () => {
    const result = reconcileChildren([], [makeElement("div", "a")]);
    expect(result.moves.size).toBe(0);
  });
});