pub const LIST_JS: &str = "// Keyed list reconciliation \u{2014} `each item in list`.\n//\n// **Its own module, and that is a size decision rather than a tidiness\n// one** \u{2014} the same decision `foreign.js` and `markup.js` record. A list is\n// something a program can go its whole life without writing, and \u{a7}16.3.1\n// promises a bundle ships nothing it does not use. Left in `dom.js` these\n// bytes were downloaded by every page ever served, including one with no\n// list in it, which is a fixed cost paid for an optional feature.\n// `Bundle::runtime` already computes a transitive import closure, so this\n// is that existing mechanism applied once more and not a new exemption\n// from the size gate: a null program must not reach this file, and a\n// program with an `each` must.\n//\n// It needs the reactivity core and one function from `dom.js` \u{2014} `anchors`,\n// for the unanchored `each` wrapper \u{2014} so a program that links this already\n// had both.\n\nimport { signal, effect, batch, owned, onCleanup } from \'./signal.js\';\nimport { anchors } from \'./dom.js\';\n\n/** A value that may be a signal getter or a constant. */\nfunction read(value) {\n return typeof value === \'function\' ? value() : value;\n}\n\n/**\n * Keyed list rendering \u{2014} `each item in list`.\n *\n * Keys are required, not optional. Without identity, reordering destroys\n * and recreates nodes, which loses focus, scroll position, and the\n * contents of any input inside a row. That is a correctness bug, not a\n * performance one, which is why `keyOf` has no default.\n *\n * `render` receives a GETTER for its item, not the item. Reusing a node\n * across an update is a decision about DOM identity only; the row\'s\n * content still flows through a signal, so a changed value reaches the\n * bindings that read it without rebuilding the row.\n */\nexport function each(listGetter, keyOf, render) {\n const fragment = anchors();\n eachInto(fragment.firstChild, fragment.lastChild, listGetter, keyOf, render);\n return fragment;\n}\n\n/**\n * The positions of a longest increasing subsequence of `from`.\n *\n * `from[i]` is where row `i` sits in the DOM *now*, or `-1` if the row is\n * new. A subsequence that is already increasing is already in the right\n * relative order, so every row in it can stay where it is; every other row\n * has to move. Taking the *longest* such subsequence is therefore the same\n * thing as making the fewest moves, which is what \u{a7}16.10 schedules and\n * what the cursor walk this replaced could not do \u{2014} that walk moved every\n * row it found out of place, so exchanging the second and the\n * second-to-last of a thousand rows moved 997 of them.\n *\n * Patience sorting, O(n log n): `tails[k]` is the position ending the\n * shortest increasing run of length `k + 1` found so far, `previous[i]` is\n * what precedes `i` in the run that ends there, and the answer is read\n * back along `previous` from the last element of the longest run. New rows\n * are skipped rather than assigned a position, because a row that does not\n * exist yet cannot be left where it is.\n */\nfunction settledPositions(from) {\n const previous = new Array(from.length);\n const tails = [];\n for (let i = 0; i < from.length; i += 1) {\n if (from[i] === -1) continue;\n let low = 0;\n let high = tails.length;\n while (low < high) {\n const middle = (low + high) >> 1;\n if (from[tails[middle]] < from[i]) low = middle + 1;\n else high = middle;\n }\n previous[i] = low === 0 ? -1 : tails[low - 1];\n tails[low] = i;\n }\n const settled = new Set();\n let i = tails.length === 0 ? -1 : tails[tails.length - 1];\n while (i !== -1) {\n settled.add(i);\n i = previous[i];\n }\n return settled;\n}\n\n/**\n * Keyed list rendering between two existing anchors.\n *\n * Three passes, and the order matters.\n *\n * Departed rows are retired *before* anything is placed: a node about to\n * be removed must not block the cursor, or every row after a deletion gets\n * moved. Measured at N=1000, removing one row cost 994 moves under a\n * single pass and 0 under this one.\n *\n * Placement then runs right to left over a minimal move set, rather than\n * left to right over a cursor. The two agree on what the DOM should look\n * like and disagree on how many `insertBefore` calls it takes to get\n * there: see [`settledPositions`].\n */\nexport function eachInto(start, end, listGetter, keyOf, render) {\n /** key -> { nodes, set, dispose } */\n let mounted = new Map();\n\n // Rows are built inside the effect, where no scope is current.\n onCleanup(() => mounted.forEach((entry) => entry.dispose()));\n\n effect(() => {\n // Spread, not the value itself: pass 2 indexes `items`, and a list a\n // program built with `append` is an iterable chain until something\n // asks it to be an array. Iterating it is what asks. Pass 1 walks the\n // whole list anyway, so this costs no order of growth.\n const items = [...(read(listGetter) ?? [])];\n const parent = end.parentNode;\n\n batch(() => {\n // Pass 1: key the items, refusing duplicates before anything moves\n // (this used to fire in pass 2), and retire what left the list.\n const keys = [];\n const live = new Set();\n for (const item of items) {\n const key = keyOf(item, keys.length);\n if (live.has(key)) {\n throw new Error(`Duplicate key ${JSON.stringify(key)} in a list. Keys must be unique.`);\n }\n live.add(key);\n keys.push(key);\n }\n // `forEach` rather than `for\u{2026}of` \u{2014} see the engine note in\n // `signal.js`, which is a crash and not a style rule. Deleting the\n // entry being visited is defined behaviour and is what this does.\n mounted.forEach((entry, key) => {\n if (live.has(key)) return;\n for (const node of entry.nodes) node.remove();\n entry.dispose();\n mounted.delete(key);\n });\n\n // Pass 2: create, re-supply, and record where each survivor sits.\n //\n // `mounted` now holds exactly the surviving rows, and a `Map`\n // iterates in insertion order, so walking it gives them in the order\n // pass 3 last placed them \u{2014} which is DOM order. That walk is the\n // only reason this needs no per-row bookkeeping between updates.\n const was = new Map();\n mounted.forEach((_entry, key) => was.set(key, was.size));\n\n const next = new Map();\n const rows = new Array(items.length);\n const from = new Array(items.length);\n for (let i = 0; i < items.length; i += 1) {\n const item = items[i];\n const key = keys[i];\n let entry = mounted.get(key);\n if (entry === undefined) {\n // `render` receives a GETTER, not a value: the row outlives any\n // one version of the item, so its bindings must read through the\n // graph. Reusing a node is then only a decision about DOM\n // identity \u{2014} the row\'s *content* still flows reactively.\n const [get, set] = signal(item);\n // Own the row\'s bindings so removing it unsubscribes them.\n const [rendered, dispose] = owned(() => render(get));\n // A row may legally have several roots, so an entry holds a node\n // LIST. Capture it before insertion empties the fragment.\n const nodes =\n rendered.nodeType === 11 ? [...rendered.childNodes] : [rendered];\n entry = { nodes, set, dispose };\n from[i] = -1;\n } else {\n // The key survived; the value need not have. Re-supplying it is\n // what makes an update to a row that kept its key visible.\n entry.set(item);\n from[i] = was.get(key);\n }\n rows[i] = entry;\n next.set(key, entry);\n }\n\n // Pass 3: place, right to left, moving only what has to move.\n //\n // Right to left because the anchor a row is inserted before is the\n // row after it, and that row is already final by the time this one\n // is considered. A settled row is skipped rather than reinserted at\n // the position it already occupies, which is where the saving is: a\n // multi-root row costs one `insertBefore` per root, so a move that\n // did not need making is not one call but as many as the row has\n // roots.\n const settled = settledPositions(from);\n let cursor = end;\n for (let i = items.length - 1; i >= 0; i -= 1) {\n const entry = rows[i];\n if (!settled.has(i)) {\n for (const node of entry.nodes) parent.insertBefore(node, cursor);\n }\n cursor = entry.nodes[0];\n }\n\n mounted = next;\n // $dev\n assertPlaced(start, end, keys, mounted);\n // $end\n });\n });\n}\n// $dev\n\n/**\n * Assert the nodes between the anchors are this list\'s rows, in order.\n *\n * The reconciliation above is the one piece of this runtime whose mistakes\n * are invisible: a row placed at the wrong index still renders, still\n * updates, and still reads correctly to every test that asks a binding for\n * its value \u{2014} it is simply in the wrong place, which only a person looking\n * at the page notices. That is the shape of defect this repository has\n * repeatedly found by running the emitted program and no other way.\n *\n * So the invariant the three passes exist to establish is stated here and\n * checked: the anchored region holds exactly each row\'s nodes, each row\n * once, in the order the list gave. It is O(rows) on top of a pass that is\n * already O(rows), which is affordable in a development build and is\n * exactly why it is not in a release one.\n *\n * It is worth more here than it was against the cursor walk this replaced.\n * A minimal move set is computed rather than swept: `settledPositions`\n * decides which rows are *not* touched, so a wrong answer from it leaves a\n * row where it was and moves nothing \u{2014} which is precisely the failure no\n * move count and no binding read can see.\n */\nfunction assertPlaced(start, end, keys, mounted) {\n const placed = [];\n for (let node = start.nextSibling; node && node !== end; node = node.nextSibling) {\n placed.push(node);\n }\n const expected = [];\n for (const key of keys) {\n for (const node of mounted.get(key).nodes) expected.push(node);\n }\n for (let i = 0; i < Math.max(placed.length, expected.length); i += 1) {\n if (placed[i] !== expected[i]) {\n throw new Error(\n `A list of ${keys.length} rows placed ${placed.length} nodes where ` +\n `${expected.length} were reconciled, first differing at ${i}. ` +\n `Reconciliation moved a row to the wrong place.`\n );\n }\n }\n}\n// $end\n\n/**\n * The interim key function: identity is the slot a row occupies.\n *\n * Spec \u{a7}14G.6a reconciles by identity when the element type is a record\n * declaring `unique`, and positionally otherwise. There are no `record`\n * declarations yet, so every list is positional today. When `unique`\n * lands this is the one argument at the one call site that changes.\n */\nexport function byPosition(item, index) {\n return index;\n}\n";Expand description
Keyed list reconciliation: each, eachInto and the interim key
function.
Its own module for the reason foreign.js and markup.js are: a
program with no list must not download a reconciler it never calls
(§16.3.1), and the minimal-move reconciler §16.10 scheduled is the
largest single thing the renderer contains. It imports signal.js and
one function from dom.js, both of which a program with a list has
already linked.