How does Vue's virtual DOM diff keyed lists?

<script setup>
import { ref } from "vue";

let nextId = 4;
const todos = ref([
  { id: 1, name: "Write tests" },
  { id: 2, name: "Fix bug" },
  { id: 3, name: "Ship it" },
]);

// Prepend: the classic case where index keys go wrong.
const prepend = () => todos.value.unshift({ id: nextId++, name: "New task" });
</script>

<template>
  <button @click="prepend">Prepend a task</button>
  <div class="cols">
    <section>
      <h4>:key="index"</h4>
      <!-- Each row has an uncontrolled input: its typed text lives in the DOM, not in state. -->
      <div v-for="(t, index) in todos" :key="index" class="row">
        <span>{{ t.name }}</span> <input placeholder="note" />
      </div>
    </section>
    <section>
      <h4>:key="t.id"</h4>
      <div v-for="t in todos" :key="t.id" class="row">
        <span>{{ t.name }}</span> <input placeholder="note" />
      </div>
    </section>
  </div>
  <p>Type a note next to "Write tests" in both columns, then prepend.</p>
</template>

import { JSDOM } from "jsdom";
const dom = new JSDOM('<!doctype html><div id="app"></div>');
for (const k of ["window","document","navigator","Node","Element","HTMLElement","SVGElement","Text","Comment"]) { try { globalThis[k] = dom.window[k]; } catch {} }
const { createApp, ref, nextTick } = await import("vue");

// Instrument the DOM operations Vue's renderer performs.
const ops = { create: 0, insert: 0, remove: 0, text: 0, moves: [] };
const P = dom.window.Node.prototype;
const origInsert = P.insertBefore, origRemove = P.removeChild;
const desc = Object.getOwnPropertyDescriptor(P, "textContent");
const origCreate = dom.window.Document.prototype.createElement;
let counting = false;
P.insertBefore = function (n, ref) { if (counting) { ops.insert++; if (n.isConnected) ops.moves.push(n.textContent); } return origInsert.call(this, n, ref); };
P.removeChild = function (n) { if (counting) ops.remove++; return origRemove.call(this, n); };
Object.defineProperty(P, "textContent", { get: desc.get, set(v) { if (counting && this.nodeType === 1 && this.isConnected) ops.text++; desc.set.call(this, v); }, configurable: true });
dom.window.Document.prototype.createElement = function (...a) { if (counting) ops.create++; return origCreate.apply(this, a); };

async function scenario(name, keyMode, from, to) {
  document.body.innerHTML = '<div id="app"></div>';
  const items = ref(from);
  const keyExpr = keyMode === "id" ? ':key="item"' : keyMode === "index" ? ':key="i"' : "";
  const app = createApp({ setup: () => ({ items }), template: `<ul><li v-for="(item, i) in items" ${keyExpr}>{{ item }}</li></ul>` });
  app.mount("#app");
  const before = [...document.querySelectorAll("li")];
  Object.assign(ops, { create: 0, insert: 0, remove: 0, text: 0, moves: [] });
  counting = true; items.value = to; await nextTick(); counting = false;
  const after = [...document.querySelectorAll("li")];
  const reused = after.filter((el) => before.includes(el)).length;
  console.log(`${name.padEnd(34)} key=${keyMode.padEnd(5)} ${from.join("")} -> ${to.join("")}: created ${ops.create}, inserted ${ops.insert} (moves of existing: ${ops.moves.length}${ops.moves.length ? " [" + ops.moves.join(",") + "]" : ""}), removed ${ops.remove}, text rewrites of existing <li> ${ops.text}, reused ${reused}/${after.length}`);
  app.unmount();
}
const L = ["A","B","C","D","E"];
for (const k of ["id", "index"]) {
  await scenario("move last to second", k, L, ["A","E","B","C","D"]);
  await scenario("move B to fourth (LIS keeps C,D)", k, L, ["A","C","D","B","E"]);
  await scenario("reverse", k, L, [...L].reverse());
  await scenario("prepend Z", k, L, ["Z", ...L]);
  await scenario("remove C", k, L, ["A","B","D","E"]);
  await scenario("insert X in the middle", k, L, ["A","B","X","C","D","E"]);
}
await scenario("prepend Z", "none", L, ["Z", ...L]);
await scenario("reverse", "none", L, [...L].reverse());