import {
    Container,
    ContainerID,
    isContainer,
    isContainerId,
    LoroDoc,
    LoroMap,
    TreeID,
} from "loro-crdt";
import {
    ContainerSchemaType,
    isLoroListSchema,
    isLoroMapSchema,
    isLoroMovableListSchema,
    isLoroTreeSchema,
    isRootSchemaType,
    LoroListSchema,
    LoroMapSchema,
    LoroMovableListSchema,
    LoroTreeSchema,
    RootSchemaType,
    SchemaType,
    type InferContainerOptions,
} from "../schema/index.js";
import { getMapFieldSchema } from "../schema/resolver.js";
import { ChangeKinds, type Change } from "./mirror.js";
import { CID_KEY } from "../constants.js";

import {
    containerIdToContainerType,
    deepEqual,
    getRootContainerByType,
    insertChildToMap,
    applySchemaToInferOptions,
    isObjectLike,
    isStateAndSchemaOfType,
    isValueOfContainerType,
    type ObjectLike,
    type ArrayLike,
    tryInferContainerType,
    tryUpdateToContainer,
    isArrayLike,
    isTreeID,
    defineCidProperty,
    valuesEqual,
    applyEncode,
    hasTransform,
} from "./utils.js";

/**
 * Finds the longest increasing subsequence of a sequence of numbers
 * @param sequence The sequence of numbers
 * @returns The longest increasing subsequence
 */
export function longestIncreasingSubsequence(sequence: number[]): number[] {
    const n = sequence.length;
    const p = Array.from({ length: n }, () => -1);
    const m: number[] = [];
    for (let i = 0; i < n; i++) {
        const x = sequence[i];
        let low = 0;
        let high = m.length;
        while (low < high) {
            const mid = Math.floor((low + high) / 2);
            if (sequence[m[mid]] < x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (low >= m.length) {
            m.push(i);
        } else {
            m[low] = i;
        }
        if (low > 0) {
            p[i] = m[low - 1];
        }
    }
    const lis: number[] = [];
    let k = m[m.length - 1];
    for (let i = m.length - 1; i >= 0; i--) {
        lis[i] = k;
        k = p[k];
    }
    return lis;
}

/**
 * Helper Type for common list item information
 */
type CommonListItemInfo = {
    id: string;
    oldIndex: number;
    newIndex: number;
    oldItem: unknown;
    newItem: unknown;
};

type IdSelector<T> = (item: T) => string | undefined;

/**
 * Diffs a container between two states
 *
 * @param doc The LoroDoc instance
 * @param oldState The old state
 * @param newState The new state
 * @param containerId The container ID can be "" for root level changes
 * @param schema The schema for the container (can be undefined)
 * @returns The list of changes
 */
export function diffContainer(
    doc: LoroDoc,
    oldState: unknown,
    newState: unknown,
    containerId: ContainerID | "",
    schema: SchemaType | undefined,
    inferOptions?: InferContainerOptions,
): Change[] {
    const effectiveInferOptions = applySchemaToInferOptions(schema, inferOptions);
    const stateAndSchema = { oldState, newState, schema };
    if (containerId === "") {
        if (
            !isStateAndSchemaOfType<
                ObjectLike,
                RootSchemaType<Record<string, ContainerSchemaType>>
            >(stateAndSchema, isObjectLike, isRootSchemaType)
        ) {
            console.log("stateAndSchema:", stateAndSchema);
            throw new Error(
                "Failed to diff container. Old and new state must be objects",
            );
        }

        return diffMap(
            doc,
            stateAndSchema.oldState,
            stateAndSchema.newState,
            containerId,
            stateAndSchema.schema,
            effectiveInferOptions,
        );
    }

    const containerType = containerIdToContainerType(containerId);

    switch (containerType) {
        case "Map": {
            if (!isObjectLike(oldState) || !isObjectLike(newState)) {
                throw new Error(
                    "Failed to diff container(map). Old and new state must be objects",
                );
            }

            const mapSchema = isLoroMapSchema(schema) ? schema : undefined;

            return diffMap(
                doc,
                oldState,
                newState,
                containerId,
                mapSchema,
                effectiveInferOptions,
            );
        }
        case "List": {
            if (!isArrayLike(oldState) || !isArrayLike(newState)) {
                throw new Error(
                    "Failed to diff container(list). Old and new state must be arrays",
                );
            }

            const listSchema = isLoroListSchema(schema) ? schema : undefined;
            const idSelector = listSchema?.idSelector;

            if (idSelector) {
                return diffListWithIdSelector(
                    doc,
                    oldState,
                    newState,
                    containerId,
                    listSchema,
                    idSelector,
                    effectiveInferOptions,
                );
            }

            return diffList(
                doc,
                oldState,
                newState,
                containerId,
                listSchema,
                effectiveInferOptions,
            );
        }
        case "MovableList": {
            if (!isArrayLike(oldState) || !isArrayLike(newState)) {
                throw new Error(
                    "Failed to diff container(movable list). Old and new state must be arrays",
                );
            }

            const movableSchema = isLoroMovableListSchema(schema)
                ? schema
                : undefined;
            const idSelector = movableSchema?.idSelector;

            if (idSelector) {
                return diffMovableList(
                    doc,
                    oldState,
                    newState,
                    containerId,
                    movableSchema,
                    idSelector,
                    effectiveInferOptions,
                );
            }

            return diffMovableListByIndex(
                doc,
                oldState,
                newState,
                containerId,
                movableSchema,
                effectiveInferOptions,
            );
        }
        case "Text": {
            if (typeof oldState !== "string" || typeof newState !== "string") {
                throw new Error(
                    "Failed to diff container(text). Old and new state must be strings",
                );
            }

            return diffText(oldState, newState, containerId);
        }
        case "Tree": {
            if (!isArrayLike(oldState) || !isArrayLike(newState)) {
                throw new Error(
                    "Failed to diff container(tree). Old and new state must be arrays",
                );
            }

            const treeSchema = isLoroTreeSchema(schema) ? schema : undefined;
            return diffTree(
                doc,
                oldState,
                newState,
                containerId,
                treeSchema,
                effectiveInferOptions,
            );
        }
        default:
            throw new Error(`Unsupported container type: ${containerType}`);
    }
}

/**
 * Diffs a [LoroText] between two states
 *
 * @param oldState The old state
 * @param newState The new state
 * @param containerId The container ID
 * @returns The list of changes
 */
export function diffText(
    oldState: string,
    newState: string,
    containerId: ContainerID | "",
): Change[] {
    if (newState === oldState) {
        return [];
    }

    return [
        {
            container: containerId,
            key: "",
            value: newState,
            kind: "insert",
        },
    ];
}

/**
 * Diffs a LoroTree between two states
 *
 * Produces structural tree operations (create/move/delete) and per-node data updates.
 */
export function diffTree(
    doc: LoroDoc,
    oldState: ArrayLike,
    newState: ArrayLike,
    containerId: ContainerID,
    schema: LoroTreeSchema<Record<string, SchemaType>> | undefined,
    inferOptions?: InferContainerOptions,
): Change[] {
    const changes: Change[] = [];
    if (oldState === newState) return changes;

    type Node = { id?: string; data?: unknown; children?: unknown[] };

    const toArray = (arr: ArrayLike) => arr as unknown as Node[];
    const oldArr = toArray(oldState);
    const newArr = toArray(newState);

    // Walk helpers
    type NodeInfo = { id: string; parent?: string; index: number; node: Node };

    const oldInfoById = new Map<string, NodeInfo>();
    const newInfoById = new Map<string, NodeInfo>();

    function walk(arr: Node[], map: Map<string, NodeInfo>, parent?: string) {
        for (let i = 0; i < arr.length; i++) {
            const n = arr[i];
            if (n && typeof n === "object" && typeof n.id === "string") {
                map.set(n.id, { id: n.id, parent, index: i, node: n });
            }
            if (n && Array.isArray(n.children)) {
                walk(
                    n.children as Node[],
                    map,
                    typeof n.id === "string" ? n.id : undefined,
                );
            }
        }
    }

    walk(oldArr, oldInfoById);
    walk(newArr, newInfoById);

    // Deletions (ids in old but not in new) – delete deepest nodes first
    // TODO: PERF: maybe we don't need to sort by depth
    const toDelete: NodeInfo[] = [];
    for (const [id, info] of oldInfoById) {
        if (!newInfoById.has(id)) toDelete.push(info);
    }

    // Compute depth for stable deletion order
    const depth = (info: NodeInfo): number => {
        let d = 0;
        let p = info.parent ? oldInfoById.get(info.parent) : undefined;
        while (p) {
            d++;
            p = p.parent ? oldInfoById.get(p.parent) : undefined;
        }
        return d;
    };
    toDelete.sort((a, b) => depth(b) - depth(a));
    for (const info of toDelete) {
        changes.push({
            container: containerId,
            kind: "tree-delete",
            target: info.id as TreeID,
        });
    }

    // Creates (nodes in new but not in old) – create parents before children (preorder)
    //
    // Why this is tricky for trees:
    // - New nodes don't have stable IDs yet. Loro assigns a TreeID only when we actually
    //   call `tree.createNode(...)`. But our app state must contain that ID afterwards so
    //   that subsequent diffs and FROM_LORO events can reference it correctly.
    // - When creating a parent and its children in the same batch, children's `parent`
    //   TreeID is unknown at diff time (because the parent has not been created yet).
    //
    // Design:
    // - We schedule a `tree-create` change per new node and attach an `onCreate(id)`
    //   callback. When the create is applied, `onCreate` receives the real TreeID assigned
    //   by Loro. We then:
    //     1) write that ID back into the newState node (so user state now carries the
    //        correct, canonical ID), and
    //     2) patch any pending child creates so their `parent` field becomes this new ID.
    // - This introduces an ordering requirement: apply tree creates one-by-one and invoke
    //   `onCreate` immediately so downstream child creates have the right parent.
    function pushCreates(
        arr: Node[],
        parent: string | undefined,
        notifyWhenParentCreated?: ChangeKinds["treeCreate"][],
    ) {
        for (let i = 0; i < arr.length; i++) {
            const n = arr[i];
            const id = isTreeID(n.id) ? n.id : undefined;
            const needCreate = !id || !oldInfoById.has(id);
            const notifySet: ChangeKinds["treeCreate"][] = [];
            if (needCreate) {
                const c: ChangeKinds["treeCreate"] = {
                    container: containerId,
                    kind: "tree-create",
                    parent: parent as TreeID | undefined,
                    index: i,
                    value: n?.data,
                    // When Loro assigns the concrete TreeID for this newly created node,
                    // we immediately:
                    // - store it back onto the node in the newState (so future diffs/events
                    //   use a consistent ID), and
                    // - update any pending child create ops so their `parent` now refers to
                    //   this new ID.
                    onCreate: (id) => {
                        n.id = id;
                        for (const c of notifySet) {
                            c.parent = id;
                        }
                    },
                };
                changes.push(c);
                notifyWhenParentCreated?.push(c);
            }

            if (n && Array.isArray(n.children)) {
                const pid = isTreeID(n.id) ? n.id : undefined;
                if (needCreate) {
                    // We don't yet know the parent's ID; collect children's create ops so
                    // we can patch their `parent` after the parent is created.
                    pushCreates(n.children as Node[], pid, notifySet);
                } else {
                    pushCreates(n.children as Node[], pid);
                }
            }
        }
    }

    pushCreates(newArr, undefined);
    // Moves and data updates for common nodes
    for (const [id, newInfo] of newInfoById) {
        const oldInfo = oldInfoById.get(id);
        if (!oldInfo) continue; // created above

        const parentChanged =
            (oldInfo.parent ?? undefined) !== (newInfo.parent ?? undefined);
        const indexChanged = oldInfo.index !== newInfo.index;
        if (parentChanged || indexChanged) {
            changes.push({
                container: containerId,
                kind: "tree-move",
                target: id as TreeID,
                parent: newInfo.parent as TreeID | undefined,
                index: newInfo.index,
            });
        }

        // Data updates: diff node.data via its map container id
        try {
            const tree = doc.getTree(containerId);
            const node = tree.getNodeByID(id as TreeID);
            if (node && schema) {
                // Ensure $cid is present on incoming node.data when omitted.
                const incoming = newInfo.node?.data;
                if (
                    incoming &&
                    typeof incoming === "object" &&
                    !(CID_KEY in (incoming as Record<string, unknown>))
                ) {
                    defineCidProperty(incoming, node.data.id);
                }
                const nested = diffContainer(
                    doc,
                    oldInfo.node?.data,
                    newInfo.node?.data,
                    node.data.id,
                    schema.nodeSchema,
                    inferOptions,
                );
                changes.push(...nested);
            }
        } catch (e) {
            console.error(`Failed to diff node.data for node ${id}:`, e);
        }
    }

    return changes;
}

/**
 * Finds the difference between two lists based on an idSelector function
 *
 * Time Complexity:
 *
 * - O(1) if not changed
 * - O(n + klogk) for insertions/deletions/replacements, where k is the number of deletions
 * - O(n) for one move op
 * - Worst case O(n^2) for move op
 *
 * @param doc The LoroDoc instance
 * @param oldState The old state
 * @param newState The new state
 * @param containerId The container ID
 * @param schema The schema for the container
 * @param idSelector The idSelector function
 * @returns The list of changes
 */
export function diffMovableList<S extends ArrayLike>(
    doc: LoroDoc,
    oldState: S,
    newState: S,
    containerId: ContainerID,
    schema:
        | LoroListSchema<SchemaType>
        | LoroMovableListSchema<SchemaType>
        | undefined,
    idSelector: IdSelector<unknown>,
    inferOptions?: InferContainerOptions,
): Change[] {
    const changes: Change[] = [];
    if (oldState === newState) return changes;

    type IndexItemMap = Map<string, { index: number; item: unknown }>;

    // 1) Build per-state maps and collect common items (ordered by new state)
    const oldMap: IndexItemMap = new Map();
    const newMap: IndexItemMap = new Map();
    const common: CommonListItemInfo[] = [];

    for (const [i, item] of oldState.entries()) {
        const id = idSelector(item);
        if (id) oldMap.set(id, { index: i, item });
    }

    for (const [newIndex, item] of newState.entries()) {
        const id = idSelector(item);
        // New items may not have an id yet (e.g., $cid is assigned during apply).
        // Treat them as pure inserts later; only track items that already have an id.
        if (!id) continue;
        if (newMap.has(id)) throw new Error("Duplicate item id in new state");
        newMap.set(id, { index: newIndex, item });
        const oldEntry = oldMap.get(id);
        if (oldEntry) {
            common.push({
                id,
                oldIndex: oldEntry.index,
                newIndex,
                oldItem: oldEntry.item,
                newItem: item,
            });
        }
    }

    // 2) Deletions (from highest index to lowest)
    const deletions: ChangeKinds["delete"][] = [];
    for (const [id, { index }] of oldMap) {
        if (!newMap.has(id)) {
            deletions.push({
                container: containerId,
                key: index,
                value: undefined,
                kind: "delete" as const,
            });
        }
    }
    deletions.sort((a, b) => (b.key as number) - (a.key as number));
    changes.push(...deletions);

    // 3) Moves (simulate post-deletion order; place each target item)
    const oldCommonIds: string[] = [];
    for (const item of oldState) {
        const id = idSelector(item);
        if (id && newMap.has(id)) oldCommonIds.push(id);
    }
    const newCommonIds: string[] = common.map((c) => c.id);
    if (!deepEqual(oldCommonIds, newCommonIds)) {
        // Need to move.
        //
        // Use LIS to keep the longest subsequence of items that are already in the correct
        // relative order, and move only the remaining items. This minimizes the number of
        // `move` operations for pure reorders.
        const oldPosById = new Map<string, number>();
        oldCommonIds.forEach((id, i) => oldPosById.set(id, i));
        const oldPositionsInNewOrder = newCommonIds.map((id) => {
            const pos = oldPosById.get(id);
            if (pos == null) {
                throw new Error("Invariant violation: common id missing in old state");
            }
            return pos;
        });
        const stableNewIndices = new Set(
            longestIncreasingSubsequence(oldPositionsInNewOrder),
        );

        const order = [...oldCommonIds];
        const idxOf = new Map<string, number>();
        order.forEach((id, i) => idxOf.set(id, i));

        for (let i = newCommonIds.length - 1; i >= 0; i--) {
            const id = newCommonIds[i];
            if (stableNewIndices.has(i)) continue;
            const from = idxOf.get(id);
            if (from == null) continue;

            // Place `id` right before the already-processed "anchor" (the next id in new order).
            // This matches the standard LIS-based list diff strategy and avoids index drift when
            // earlier moves shift later indices.
            const anchorId = i + 1 < newCommonIds.length ? newCommonIds[i + 1] : undefined;
            const anchorIndex = anchorId ? idxOf.get(anchorId) : undefined;
            if (anchorId && anchorIndex == null) {
                throw new Error("Invariant violation: anchor id missing in current order");
            }

            // `toIndex` is defined in the list *after* the removal.
            //
            // - If we have an anchor, we want to insert right before it.
            // - If we don't have an anchor (end of the list), treat it as an append.
            //
            // For the anchor case, when `from < anchorIndex`, removing the element shifts
            // the anchor left by 1, so we subtract 1.
            const targetBeforeRemoval = anchorIndex ?? order.length;
            let to = targetBeforeRemoval;
            if (from < targetBeforeRemoval) {
                to -= 1;
            }

            if (from === to) continue;

            changes.push({
                container: containerId,
                key: from,
                value: undefined,
                kind: "move",
                fromIndex: from,
                toIndex: to,
            });

            const [moved] = order.splice(from, 1);
            order.splice(to, 0, moved);
            const start = Math.min(from, to);
            const end = Math.max(from, to);
            for (let i = start; i <= end; i++) idxOf.set(order[i], i);
        }
    }

    // 4) Insertions (items only in new state)
    const itemSchema = schema?.itemSchema;
    for (const [newIndex, item] of newState.entries()) {
        const id = idSelector(item);
        if (!id || !oldMap.has(id)) {
            changes.push(
                tryUpdateToContainer(
                    {
                        container: containerId,
                        key: newIndex,
                        value: item,
                        kind: "insert",
                    },
                    true,
                    itemSchema,
                    inferOptions,
                ),
            );
        }
    }

    // 5) Updates (for items present in both states)
    for (const info of common) {
        if (valuesEqual(itemSchema, info.oldItem, info.newItem, "deep-equality")) continue;

        const movableList = doc.getMovableList(containerId);
        const currentItem = movableList.get(info.oldIndex);
        if (isContainer(currentItem)) {
            const nested = diffContainer(
                doc,
                info.oldItem,
                info.newItem,
                currentItem.id,
                itemSchema,
                inferOptions,
            );
            changes.push(...nested);
        } else {
            changes.push(
                tryUpdateToContainer(
                    {
                        container: containerId,
                        key: info.newIndex,
                        value: info.newItem,
                        kind: "set",
                    },
                    true,
                    itemSchema,
                    inferOptions,
                ),
            );
        }
    }

    return changes;
}

/**
 * Finds the difference between two lists based on an idSelector function
 *
 * @param doc The LoroDoc instance
 * @param oldState The old state
 * @param newState The new state
 * @param containerId The container ID
 * @param schema The schema for the container
 * @param idSelector The idSelector function
 * @returns The list of changes
 */
export function diffListWithIdSelector<S extends ArrayLike>(
    doc: LoroDoc,
    oldState: S,
    newState: S,
    containerId: ContainerID,
    schema: LoroListSchema<SchemaType> | undefined,
    idSelector: IdSelector<unknown>,
    inferOptions?: InferContainerOptions,
): Change[] {
    const changes: Change[] = [];
    if (oldState === newState) {
        return changes;
    }

    const useContainer = !!(schema?.itemSchema.getContainerType() ?? true);
    const oldItemsById = new Map<string, { item: unknown; index: number }>();
    const newItemsById = new Map<string, { item: unknown; newIndex: number }>();

    for (const [index, item] of oldState.entries()) {
        const id = idSelector(item);
        if (id) {
            oldItemsById.set(id, { item, index });
        }
    }

    // Note: Items in the NEW state may legitimately be missing an ID when
    // using $cid injection; IDs are stamped during apply. Treat them as new inserts
    // later instead of throwing here.
    for (const [newIndex, item] of newState.entries()) {
        const id = idSelector(item);
        if (id) {
            newItemsById.set(id, { item, newIndex });
        }
    }

    // Compute the longest common subsequence (LCS) between old/new id sequences via LIS on
    // old indices in new order (ids are expected to be unique).
    const commonIdsInNewOrder: string[] = [];
    const oldIndexInNewOrder: number[] = [];
    for (const item of newState) {
        const id = idSelector(item);
        if (!id) continue;
        const oldInfo = oldItemsById.get(id);
        if (!oldInfo) continue;
        commonIdsInNewOrder.push(id);
        oldIndexInNewOrder.push(oldInfo.index);
    }

    const keepIdSet = new Set<string>();
    for (const i of longestIncreasingSubsequence(oldIndexInNewOrder)) {
        keepIdSet.add(commonIdsInNewOrder[i]);
    }

    // 1) Deletions (from highest index to lowest).
    for (let i = oldState.length - 1; i >= 0; i--) {
        const id = idSelector(oldState[i]);
        if (!id || !keepIdSet.has(id)) {
            changes.push({
                container: containerId,
                key: i,
                value: undefined,
                kind: "delete",
            });
        }
    }

    // 2) Insertions (items that are new or moved).
    const itemSchema = schema?.itemSchema;
    for (const [newIndex, item] of newState.entries()) {
        const id = idSelector(item);
        if (!id || !keepIdSet.has(id)) {
            changes.push(
                tryUpdateToContainer(
                    {
                        container: containerId,
                        key: newIndex,
                        value: item,
                        kind: "insert",
                    },
                    useContainer,
                    itemSchema,
                    inferOptions,
                ),
            );
        }
    }

    // 3) Updates for kept items (preserve nested containers when possible).
    const list = doc.getList(containerId);
    for (const id of commonIdsInNewOrder) {
        if (!keepIdSet.has(id)) continue;
        const oldInfo = oldItemsById.get(id);
        const newInfo = newItemsById.get(id);
        if (!oldInfo || !newInfo) continue;

        const oldItem = oldInfo.item;
        const newItem = newInfo.item;
        if (valuesEqual(itemSchema, oldItem, newItem, "deep-equality")) continue;

        const itemOnLoro = list.get(oldInfo.index);
        if (isContainer(itemOnLoro)) {
            changes.push(
                ...diffContainer(
                    doc,
                    oldItem,
                    newItem,
                    itemOnLoro.id,
                    itemSchema,
                    inferOptions,
                ),
            );
        } else {
            changes.push({
                container: containerId,
                key: newInfo.newIndex,
                value: undefined,
                kind: "delete",
            });
            changes.push(
                tryUpdateToContainer(
                    {
                        container: containerId,
                        key: newInfo.newIndex,
                        value: newItem,
                        kind: "insert",
                    },
                    useContainer,
                    itemSchema,
                    inferOptions,
                ),
            );
        }
    }

    return changes;
}

/**
 * Diffs a [LoroList] between two states
 *
 * This function handles list diffing without an ID selector.
 * This can result in less precise updates, and can cause clone/fork of items.
 *
 * If an ID selector is possible, use [diffMovableList] instead.
 *
 * @param doc The LoroDoc instance
 * @param oldState The old state
 * @param newState The new state
 * @param containerId The container ID of the list
 * @param schema The schema for the container
 * @returns The list of changes
 */
export function diffList<S extends ArrayLike>(
    doc: LoroDoc,
    oldState: S,
    newState: S,
    containerId: ContainerID,
    schema: LoroListSchema<SchemaType> | undefined,
    inferOptions?: InferContainerOptions,
): Change[] {
    if (oldState === newState) {
        return [];
    }

    const changes: Change[] = [];
    const oldLen = oldState.length;
    const newLen = newState.length;
    const list = doc.getList(containerId);
    const itemSchema = schema?.itemSchema;

    // Find common prefix
    let start = 0;
    while (
        start < oldLen &&
        start < newLen &&
        valuesEqual(itemSchema, oldState[start], newState[start], "reference-equality")
    ) {
        start++;
    }

    // Find common suffix (after the differing middle), ensuring no overlap with prefix
    let suffix = 0;
    while (
        suffix < oldLen - start &&
        suffix < newLen - start &&
        valuesEqual(itemSchema, oldState[oldLen - 1 - suffix], newState[newLen - 1 - suffix], "reference-equality")
    ) {
        suffix++;
    }

    const oldBlockLen = oldLen - start - suffix;
    const newBlockLen = newLen - start - suffix;

    // First, handle overlapping part in the middle block as updates (preserve nested containers)
    const overlap = Math.min(oldBlockLen, newBlockLen);
    for (let j = 0; j < overlap; j++) {
        const i = start + j;
        if (valuesEqual(itemSchema, oldState[i], newState[i], "reference-equality")) continue;

        const itemOnLoro = list.get(i);
        if (isContainer(itemOnLoro)) {
            const nestedChanges = diffContainer(
                doc,
                oldState[i],
                newState[i],
                itemOnLoro.id,
                itemSchema,
                inferOptions,
            );
            changes.push(...nestedChanges);
        } else {
            changes.push({
                container: containerId,
                key: i,
                value: undefined,
                kind: "delete",
            });
            changes.push(
                tryUpdateToContainer(
                    {
                        container: containerId,
                        key: i,
                        value: newState[i],
                        kind: "insert",
                    },
                    true,
                    itemSchema,
                    inferOptions,
                ),
            );
        }
    }

    // Then handle extra deletions (when old middle block is longer)
    for (let k = 0; k < oldBlockLen - overlap; k++) {
        // Always delete at the same index (start + overlap) to remove a contiguous block
        changes.push({
            container: containerId,
            key: start + overlap,
            value: undefined,
            kind: "delete",
        });
    }

    // Finally handle extra insertions (when new middle block is longer)
    for (let k = 0; k < newBlockLen - overlap; k++) {
        const insertIndex = start + overlap + k;
        changes.push(
            tryUpdateToContainer(
                {
                    container: containerId,
                    key: insertIndex,
                    value: newState[insertIndex],
                    kind: "insert",
                },
                true,
                itemSchema,
                inferOptions,
            ),
        );
    }

    return changes;
}

/**
 * Diffs a [LoroMovableList] between two states without requiring an idSelector.
 *
 * This is an index-based fallback intended for inference-driven movable lists
 * (e.g. when `inferOptions.defaultMovableList` is enabled).
 */
export function diffMovableListByIndex(
    doc: LoroDoc,
    oldState: ArrayLike,
    newState: ArrayLike,
    containerId: ContainerID,
    schema: LoroMovableListSchema<SchemaType> | undefined,
    inferOptions?: InferContainerOptions,
): Change[] {
    /**
     * Index-based fallback for MovableList diffs.
     *
     * Why this exists:
     * - A MovableList can appear without an explicit `LoroMovableListSchema` (e.g. when
     *   `inferOptions.defaultMovableList` is enabled or when `schema.Any()` infers an array
     *   as MovableList). In such cases we may not have an `idSelector`, so we cannot emit
     *   true `move` operations.
     *
     * Algorithm (similar to `diffList`):
     * 0) `$cid` idSelector fallback:
     *    - If every element in both old/new arrays has a `$cid`, use `$cid` as an implicit
     *      idSelector and delegate to `diffMovableList` (supports complex move detection).
     * 1) Best-effort single-move detection:
     *    - If the list length is unchanged and `newState` equals `oldState` after moving exactly
     *      one element, emit a single `move` op and stop. Element identity is matched by either
     *      strict equality (`===`) or a shared `$cid` (for map containers).
     * 2) Find a common prefix and suffix by strict reference equality.
     * 3) For the overlapping middle region, prefer preserving nested container identity:
     *    - If the current Loro item is a container and the next JS value is compatible with
     *      that container kind, recursively diff the child container.
     *    - Otherwise, emit a `set`/`set-container` at that index (via `tryUpdateToContainer`).
     * 4) Delete extra trailing items (when the old middle block is longer).
     * 5) Insert extra items (when the new middle block is longer).
     *
     * Limitations:
     * - If `$cid` is missing on any element, move detection is limited to the
     *   "single move and nothing else changed" case. Complex reorders typically degrade into
     *   a sequence of `set`/`insert`/`delete` operations.
     * - Without stable IDs, "minimal diff" is not guaranteed; large shuffles can cause many writes.
     * - Container identity is only preserved when the container stays at the same index AND the
     *   next value remains compatible with that container kind.
     */
    if (oldState === newState) return [];

    const cidSelector: IdSelector<unknown> = (item) => {
        if (!item || typeof item !== "object") return;
        const cid = (item as Record<string, unknown>)[CID_KEY];
        if (typeof cid === "string" && isContainerId(cid)) {
            return cid
        }
        return undefined;
    };
    const allHaveCid = (arr: ArrayLike) =>
        arr.every((x) => cidSelector(x) !== undefined);

    if (allHaveCid(oldState) && allHaveCid(newState)) {
        return diffMovableList(
            doc,
            oldState,
            newState,
            containerId,
            schema,
            cidSelector,
            inferOptions,
        );
    }

    const identityEquals = (a: unknown, b: unknown) => {
        if (a === b) return true;
        if (!a || !b) return false;
        if (typeof a !== "object" || typeof b !== "object") return false;
        const aa = a as Record<string, unknown>;
        const bb = b as Record<string, unknown>;
        const ac = aa[CID_KEY];
        const bc = bb[CID_KEY];
        return typeof ac === "string" && typeof bc === "string" && ac === bc;
    };

    const tryDetectSingleMove = (
        oldArr: ArrayLike,
        newArr: ArrayLike,
    ): { from: number; to: number } | undefined => {
        if (oldArr.length !== newArr.length) return;
        const n = oldArr.length;
        if (n <= 1) return;

        let start = 0;
        while (start < n && identityEquals(oldArr[start], newArr[start])) start++;
        if (start === n) return;

        // Case A: element moved forward (from=start, to>start)
        const movedForward = oldArr[start];
        for (let to = start + 1; to < n; to++) {
            if (!identityEquals(newArr[to], movedForward)) continue;
            let ok = true;
            for (let i = start; i < to; i++) {
                if (!identityEquals(newArr[i], oldArr[i + 1])) {
                    ok = false;
                    break;
                }
            }
            if (!ok) continue;
            for (let i = to + 1; i < n; i++) {
                if (!identityEquals(newArr[i], oldArr[i])) {
                    ok = false;
                    break;
                }
            }
            if (ok) return { from: start, to };
        }

        // Case B: element moved backward (to=start, from>start)
        const movedBackward = newArr[start];
        for (let from = start + 1; from < n; from++) {
            if (!identityEquals(oldArr[from], movedBackward)) continue;
            let ok = true;
            for (let i = start; i < from; i++) {
                if (!identityEquals(newArr[i + 1], oldArr[i])) {
                    ok = false;
                    break;
                }
            }
            if (!ok) continue;
            for (let i = from + 1; i < n; i++) {
                if (!identityEquals(newArr[i], oldArr[i])) {
                    ok = false;
                    break;
                }
            }
            if (ok) return { from, to: start };
        }

        return;
    };

    const singleMove = tryDetectSingleMove(oldState, newState);
    if (singleMove) {
        return [
            {
                container: containerId,
                key: singleMove.from,
                value: undefined,
                kind: "move",
                fromIndex: singleMove.from,
                toIndex: singleMove.to,
            },
        ];
    }

    const changes: Change[] = [];
    const oldLen = oldState.length;
    const newLen = newState.length;
    const list = doc.getMovableList(containerId);
    const itemSchema = schema?.itemSchema;

    // Find common prefix
    let start = 0;
    while (
        start < oldLen &&
        start < newLen &&
        valuesEqual(itemSchema, oldState[start], newState[start], "reference-equality")
    ) {
        start++;
    }

    // Find common suffix (after the differing middle), ensuring no overlap with prefix
    let suffix = 0;
    while (
        suffix < oldLen - start &&
        suffix < newLen - start &&
        valuesEqual(itemSchema, oldState[oldLen - 1 - suffix], newState[newLen - 1 - suffix], "reference-equality")
    ) {
        suffix++;
    }

    const oldBlockLen = oldLen - start - suffix;
    const newBlockLen = newLen - start - suffix;

    // First, handle overlapping part in the middle block as updates (preserve nested containers)
    const overlap = Math.min(oldBlockLen, newBlockLen);
    for (let j = 0; j < overlap; j++) {
        const i = start + j;
        if (valuesEqual(itemSchema, oldState[i], newState[i], "reference-equality")) continue;

        const itemOnLoro = list.get(i);
        const next = newState[i];

        if (isContainer(itemOnLoro)) {
            const ct = containerIdToContainerType(itemOnLoro.id);
            if (ct && isValueOfContainerType(ct, next)) {
                changes.push(
                    ...diffContainer(
                        doc,
                        oldState[i],
                        next,
                        itemOnLoro.id,
                        itemSchema,
                        inferOptions,
                    ),
                );
                continue;
            }
        }

        changes.push(
            tryUpdateToContainer(
                {
                    container: containerId,
                    key: i,
                    value: next,
                    kind: "set",
                },
                true,
                itemSchema,
                inferOptions,
            ),
        );
    }

    // Then handle extra deletions (when old middle block is longer)
    for (let k = 0; k < oldBlockLen - overlap; k++) {
        // Always delete at the same index (start + overlap) to remove a contiguous block
        changes.push({
            container: containerId,
            key: start + overlap,
            value: undefined,
            kind: "delete",
        });
    }

    // Finally handle extra insertions (when new middle block is longer)
    for (let k = 0; k < newBlockLen - overlap; k++) {
        const insertIndex = start + overlap + k;
        changes.push(
            tryUpdateToContainer(
                {
                    container: containerId,
                    key: insertIndex,
                    value: newState[insertIndex],
                    kind: "insert",
                },
                true,
                itemSchema,
                inferOptions,
            ),
        );
    }

    return changes;
}

/**
 * Diffs a [LoroMap] between two states
 *
 * @param doc The LoroDoc instance
 * @param oldState The old state
 * @param newState The new state
 * @param containerId The container ID of the map
 * @param schema The schema for the container
 * @returns The list of changes
 */
export function diffMap<S extends ObjectLike>(
    doc: LoroDoc,
    oldState: S,
    newState: S,
    containerId: ContainerID | "",
    schema:
        | LoroMapSchema<Record<string, SchemaType>>
        | RootSchemaType<Record<string, ContainerSchemaType>>
        | undefined,
    inferOptions?: InferContainerOptions,
): Change[] {
    const changes: Change[] = [];
    const oldStateObj = oldState as Record<string, unknown>;
    const newStateObj = newState as Record<string, unknown>;

    // Check for removed keys
    for (const key in oldStateObj) {
        // Skip synthetic CID field for maps
        if (key === CID_KEY) {
            continue;
        }
        // Skip ignored fields defined in schema
        const childSchemaForDelete = getMapFieldSchema(schema, key);
        if (childSchemaForDelete && childSchemaForDelete.type === "ignore") {
            continue;
        }
        if (!(key in newStateObj)) {
            changes.push({
                container: containerId,
                key,
                value: undefined,
                kind: "delete",
            });
        }
    }

    // Check for added or modified keys
    for (const key in newStateObj) {
        // Skip synthetic CID field for maps
        if (key === CID_KEY) {
            continue;
        }
        const oldItem = oldStateObj[key];
        const newItem = newStateObj[key];

        // Treat undefined values as non-existent fields.
        // This allows users to pass objects with undefined values without causing errors.
        if (newItem === undefined) {
            // If old item exists, we need to delete it
            if (key in oldStateObj && oldItem !== undefined) {
                const childSchemaForDelete = getMapFieldSchema(schema, key);
                if (!(childSchemaForDelete && childSchemaForDelete.type === "ignore")) {
                    changes.push({
                        container: containerId,
                        key,
                        value: undefined,
                        kind: "delete",
                    });
                }
            }
            continue;
        }

        // Figure out if the modified new value is a container
        const childSchema = getMapFieldSchema(schema, key);

        // Skip ignored fields defined in schema
        if (childSchema && childSchema.type === "ignore") {
            continue;
        }

        // Determine container type with schema-first, but respect actual value.
        // If schema suggests a container but the provided value doesn't match it,
        // log a warning and fall back to inferring from the value to avoid divergence.
        const childInferOptions = applySchemaToInferOptions(
            childSchema,
            inferOptions,
        );
        let containerType =
            hasTransform(childSchema)
                ? undefined
                : (childSchema?.getContainerType() ??
                  tryInferContainerType(newItem, childInferOptions));
        if (
            childSchema?.getContainerType() &&
            containerType &&
            !isValueOfContainerType(containerType, newItem)
        ) {
            console.warn(
                `Schema mismatch on key "${key}": expected ${childSchema.getContainerType()} but got value ${JSON.stringify(
                    newItem,
                )}. Falling back to value-based inference to avoid divergence.`,
            );
            containerType = tryInferContainerType(newItem, childInferOptions);
        }

        // Added new key: detect by property presence, not truthiness.
        // Using `!oldItem` breaks for valid falsy values like "" or null.
        if (!(key in oldStateObj)) {
            // Inserted a new container
            if (
                containerType &&
                isValueOfContainerType(containerType, newItem)
            ) {
                changes.push({
                    container: containerId,
                    key,
                    value: newItem,
                    kind: "insert-container",
                    childContainerType: containerType,
                });
                // Inserted a new value
            } else {
                changes.push({
                    container: containerId,
                    key,
                    value: applyEncode(childSchema, newItem),
                    kind: "insert",
                });
            }
            continue;
        }

        // Item inside map has changed
        if (oldItem !== newItem) {
            // The key was previously a container and new item is also a container
            if (
                containerType &&
                isValueOfContainerType(containerType, newItem) &&
                isValueOfContainerType(containerType, oldItem)
            ) {
                // the parent is the root container
                if (containerId === "") {
                    const container = getRootContainerByType(
                        doc,
                        key,
                        containerType,
                    );
                    // Reattach $cid on the incoming object if missing when the child
                    // is an existing map container but the new value omitted $cid.
                    // This keeps container identity stable for subsequent updates.
                    if (
                        containerType === "Map" &&
                        newItem &&
                        typeof newItem === "object" &&
                        !(CID_KEY in (newItem as Record<string, unknown>))
                    ) {
                        defineCidProperty(newItem, container.id);
                    }
                    changes.push(
                        ...diffContainer(
                            doc,
                            oldStateObj[key],
                            newStateObj[key],
                            container.id,
                            childSchema,
                            inferOptions,
                        ),
                    );
                    continue;
                }

                const container = doc.getContainerById(containerId);

                if (container?.kind() !== "Map") {
                    throw new Error("Expected map container");
                }

                const map = container as LoroMap;
                const child = map.get(key) as Container | undefined;
                if (!child || !isContainer(child)) {
                    changes.push(
                        insertChildToMap(
                            containerId,
                            key,
                            newStateObj[key],
                            applySchemaToInferOptions(childSchema, inferOptions),
                        ),
                    );
                } else {
                    // Reattach $cid on the incoming object if missing when the child
                    // is an existing map container but the new value omitted $cid.
                    if (
                        containerType === "Map" &&
                        newItem &&
                        typeof newItem === "object" &&
                        !(CID_KEY in (newItem as Record<string, unknown>))
                    ) {
                        defineCidProperty(newItem, child.id);
                    }
                    changes.push(
                        ...diffContainer(
                            doc,
                            oldStateObj[key],
                            newStateObj[key],
                            child.id,
                            childSchema,
                            inferOptions,
                        ),
                    );
                }
            } else {
                if (valuesEqual(childSchema, oldItem, newItem, "reference-equality")) {
                    continue; 
                }

                // The type or value of the child has changed
                // Either the value has changed, or it was previously a container and now it's not,
                // or it was not a container and now it is
                changes.push(
                    insertChildToMap(
                        containerId,
                        key,
                        applyEncode(childSchema, newItem),
                        applySchemaToInferOptions(childSchema, inferOptions),
                    ),
                );
            }
        }
    }

    return changes;
}