Skip to content

Commit ac27b15

Browse files
perf(studio): resolve a selector's occurrence index once per layer walk (#3831)
The preview flattens several composition files into one DOM, so a layer's identity is its selector plus its occurrence index WITHIN its own source file. `getSourceScopedSelectorIndex` derived that per element: a whole -document `querySelectorAll(selector)`, `resolveSourceFile` on every match, then `indexOf`. Every element sharing a class paid for all of them, so a walk over n such elements did n whole-document queries and n^2 source-file resolutions — the shape a composition of repeated cards or tiles has by construction. Build the occurrence index ONCE per selector instead and share it across one walk. `withSelectorIndexPass(doc, run)` opens that scope; outside it the helper behaves exactly as before, per call. The pass lives in `collectDomEditLayerItems`, which owns the loop, rather than at a call site — its four callers (off-canvas indicators, the layers panel, the marquee hit-test and the agent look tool) all walked the same way and all paid the same cost. Behaviour is unchanged. The occurrence indices are identical, including the misses: an element outside the requested source file, or one not matching the selector, still yields undefined, as do `#`-prefixed and `[data-composition-id=` selectors and an invalid selector. Measured on a 1689-element preview over 80 single-frame seeks, per rebuild: class-selector document queries 171.6 -> 10.8, and the walk's self-timed cost 15.25ms -> 5.37ms. Elements walked per rebuild is unchanged at 973.7, so the two arms did the same work. Tests assert complexity invariance rather than a threshold: the query count must be IDENTICAL at n and 4n elements sharing a selector, which a fixture -sized threshold would not catch. Both fail on the previous algorithm.
1 parent 3ea2f90 commit ac27b15

5 files changed

Lines changed: 387 additions & 8 deletions

File tree

‎packages/studio/src/components/editor/domEditingLayers.test.ts‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -257,3 +257,51 @@ describe("collectDomEditLayerItems item budget", () => {
257257
expect(collectDomEditLayerItems(documentWith(200), opts, 80)).toHaveLength(80);
258258
});
259259
});
260+
261+
describe("collectDomEditLayerItems selector-index cost", () => {
262+
// Attached, unlike the fixture above: a detached subtree is invisible to
263+
// document.querySelectorAll, so the occurrence lookup would find nothing.
264+
function attachedRootWithSharedClass(count: number): HTMLElement {
265+
const root = document.createElement("div");
266+
root.setAttribute("data-composition-id", "index.html");
267+
for (let i = 0; i < count; i++) {
268+
const child = document.createElement("div");
269+
child.className = "box";
270+
root.append(child);
271+
}
272+
document.body.append(root);
273+
return root;
274+
}
275+
276+
/** Class-selector document queries made by one walk over `count` sibling cards. */
277+
function classSelectorQueries(count: number): number {
278+
const root = attachedRootWithSharedClass(count);
279+
const doc = root.ownerDocument;
280+
const real = doc.querySelectorAll.bind(doc);
281+
let calls = 0;
282+
Object.defineProperty(doc, "querySelectorAll", {
283+
configurable: true,
284+
value: (selector: string) => {
285+
if (selector.startsWith(".")) calls += 1;
286+
return real(selector);
287+
},
288+
});
289+
try {
290+
expect(collectDomEditLayerItems(root, opts)).toHaveLength(count);
291+
return calls;
292+
} finally {
293+
delete (doc as Partial<Document>).querySelectorAll;
294+
root.remove();
295+
}
296+
}
297+
298+
// The occurrence index is resolved here, for every item, so an unshared index
299+
// costs one whole-document query per element — quadratic once a composition
300+
// repeats a card or tile class. Owning the pass here rather than at each call
301+
// site is what keeps the layers panel, the marquee and the agent's look tool
302+
// linear too; invariance across a 4x fixture fails for any per-element term.
303+
it("resolves a shared selector once per walk, not once per element", () => {
304+
expect(classSelectorQueries(48)).toBe(classSelectorQueries(12));
305+
expect(classSelectorQueries(12)).toBe(1);
306+
});
307+
});

‎packages/studio/src/components/editor/domEditingLayers.ts‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ import {
3232
getSelectionCandidate,
3333
} from "./domEditingElement";
3434
import { isCompositionRootLayer } from "./domEditingRootLayer";
35+
import { withSelectorIndexPass } from "../../utils/sourceScopedSelectorIndex";
3536

3637
export function isEditableTextLeaf(el: HTMLElement): boolean {
3738
return isTextBearingTag(el.tagName.toLowerCase()) && el.children.length === 0;
@@ -475,8 +476,15 @@ export function collectDomEditLayerItems(
475476
}
476477
};
477478

478-
// Drilled into a group → show only its members; otherwise the whole tree.
479-
for (const el of groupScopedLayerRoots(root, options.activeGroupElement ?? null)) visit(el, 0);
479+
// Every item resolves its selector's occurrence index, and unshared that is a
480+
// whole-document query per element — quadratic once a composition repeats a
481+
// card or tile class. The walk is one synchronous read of a document it does
482+
// not mutate, so one index per selector serves the whole of it. The pass lives
483+
// here rather than in each caller because this function owns the loop.
484+
withSelectorIndexPass(root.ownerDocument, () => {
485+
// Drilled into a group → show only its members; otherwise the whole tree.
486+
for (const el of groupScopedLayerRoots(root, options.activeGroupElement ?? null)) visit(el, 0);
487+
});
480488
return items;
481489
}
482490

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
// @vitest-environment happy-dom
2+
3+
import type React from "react";
4+
import { afterEach, describe, expect, it } from "vitest";
5+
import type { OffCanvasRect } from "./OffCanvasIndicators";
6+
import { recomputeOffCanvasIndicators } from "./offCanvasIndicatorGeometry";
7+
8+
const realGetBoundingClientRect = Element.prototype.getBoundingClientRect;
9+
afterEach(() => {
10+
Element.prototype.getBoundingClientRect = realGetBoundingClientRect;
11+
});
12+
13+
interface Rebuild {
14+
/** querySelectorAll calls on the preview document, per selector. */
15+
queriesBySelector: Map<string, number>;
16+
/** The indicator keys, which carry each element's selector occurrence index. */
17+
keys: string[];
18+
}
19+
20+
/**
21+
* One real rebuild over a preview whose `cardCount` cards all share `.box`,
22+
* counting the preview document's queries. Everything below the entry point is
23+
* production code: the layer walk, the patch targets, and the selector
24+
* occurrence indices that end up in each indicator's key.
25+
*/
26+
function rebuildWithSharedSelector(cardCount: number): Rebuild {
27+
const iframe = document.createElement("iframe");
28+
document.body.append(iframe);
29+
const doc = iframe.contentDocument;
30+
if (!doc) throw new Error("Expected iframe content document");
31+
32+
const cards = Array.from(
33+
{ length: cardCount },
34+
(_unused, i) => `<div class="box"><span class="label">card ${i}</span></div>`,
35+
).join("");
36+
doc.body.innerHTML = `<div data-composition-id="root" data-width="800" data-height="450">${cards}</div>`;
37+
38+
const overlay = document.createElement("div");
39+
document.body.append(overlay);
40+
41+
// Cards sit left of the composition, so every one of them is off-canvas and
42+
// reaches the indicator list; everything else measures empty and does not.
43+
Element.prototype.getBoundingClientRect = function (): DOMRect {
44+
if (this === iframe || this === overlay) return new DOMRect(0, 0, 800, 450);
45+
if (this instanceof doc.defaultView!.Element && this.classList.contains("box")) {
46+
return new DOMRect(-500, 40, 100, 40);
47+
}
48+
return new DOMRect(0, 0, 0, 0);
49+
};
50+
51+
const queriesBySelector = new Map<string, number>();
52+
const realQuerySelectorAll = doc.querySelectorAll.bind(doc);
53+
Object.defineProperty(doc, "querySelectorAll", {
54+
configurable: true,
55+
value: (selector: string) => {
56+
queriesBySelector.set(selector, (queriesBySelector.get(selector) ?? 0) + 1);
57+
return realQuerySelectorAll(selector);
58+
},
59+
});
60+
61+
const sigRef = { current: "" } as React.MutableRefObject<string>;
62+
const elementsRef = { current: new Map<string, HTMLElement>() } as React.MutableRefObject<
63+
Map<string, HTMLElement>
64+
>;
65+
let rects: OffCanvasRect[] = [];
66+
67+
recomputeOffCanvasIndicators(
68+
iframe,
69+
overlay,
70+
doc,
71+
{ left: 0, top: 0, width: 800, height: 450 },
72+
"index.html",
73+
sigRef,
74+
elementsRef,
75+
(next) => {
76+
rects = next;
77+
},
78+
);
79+
80+
iframe.remove();
81+
overlay.remove();
82+
return { queriesBySelector, keys: rects.map((rect) => rect.key) };
83+
}
84+
85+
/** The queries that resolve a class selector's occurrence index — the work this
86+
* guards. Excluded: the per-element `[data-composition-id]` ancestor lookup and
87+
* the stylesheet scan, which are linear per element and a separate seam. */
88+
function classSelectorQueries(rebuild: Rebuild): Array<[string, number]> {
89+
return [...rebuild.queriesBySelector].filter(([selector]) => selector.startsWith(".")).sort();
90+
}
91+
92+
describe("recomputeOffCanvasIndicators selector-index cost", () => {
93+
// The defect this guards: the occurrence index used to be resolved with its
94+
// own whole-document querySelectorAll PER element, so n cards sharing a class
95+
// cost n queries and n² source-file resolutions. A threshold would pass on a
96+
// small fixture while a real composition runs hundreds of cards. Invariance
97+
// across a 4x fixture cannot — it fails for any per-element term at all.
98+
it("resolves shared selectors with the same number of queries at n and at 4n", () => {
99+
const small = rebuildWithSharedSelector(12);
100+
const large = rebuildWithSharedSelector(48);
101+
102+
expect(classSelectorQueries(large)).toEqual(classSelectorQueries(small));
103+
expect(classSelectorQueries(small)).toEqual([
104+
[".box", 1],
105+
[".label", 1],
106+
]);
107+
});
108+
109+
it("still numbers every shared-selector element in document order", () => {
110+
for (const cardCount of [12, 48]) {
111+
const { keys } = rebuildWithSharedSelector(cardCount);
112+
expect(keys).toEqual(
113+
Array.from({ length: cardCount }, (_unused, i) => `index.html:.box:${i}`),
114+
);
115+
}
116+
});
117+
});
Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
// @vitest-environment happy-dom
2+
3+
import { describe, expect, it } from "vitest";
4+
import { getSourceScopedSelectorIndex, withSelectorIndexPass } from "./sourceScopedSelectorIndex";
5+
6+
// The per-element algorithm this helper used before it grew a per-pass index,
7+
// transcribed verbatim. It is the independent source the memoized results are
8+
// checked against — including the misses, which are `indexOf` returning -1.
9+
function referenceIndex(
10+
doc: Document,
11+
el: Element,
12+
selector: string | undefined,
13+
sourceFile: string | undefined,
14+
resolveSourceFile: (candidate: Element) => string | undefined,
15+
): number | undefined {
16+
if (!selector || selector.startsWith("#") || selector.startsWith("[data-composition-id=")) {
17+
return undefined;
18+
}
19+
try {
20+
const scope = sourceFile ?? "index.html";
21+
const matches = Array.from(doc.querySelectorAll(selector)).filter(
22+
(candidate) => (resolveSourceFile(candidate) ?? "index.html") === scope,
23+
);
24+
const matchIndex = matches.indexOf(el);
25+
return matchIndex >= 0 ? matchIndex : undefined;
26+
} catch {
27+
return undefined;
28+
}
29+
}
30+
31+
const bySourceFile = (candidate: Element): string | undefined =>
32+
candidate.closest("[data-composition-file]")?.getAttribute("data-composition-file") ?? undefined;
33+
34+
// Two source files sharing one class, plus an unscoped element, is the case
35+
// source-file scoping exists for: raw document order would number these 0..4.
36+
function mixedSourceDocument(): Document {
37+
const doc = document.implementation.createHTMLDocument("mixed");
38+
doc.body.innerHTML = `
39+
<div data-composition-id="root">
40+
<section data-composition-file="a.html">
41+
<p class="box" id="a0">a0</p>
42+
<p class="box" id="a1">a1</p>
43+
</section>
44+
<section data-composition-file="b.html">
45+
<p class="box" id="b0">b0</p>
46+
<p class="box" id="b1">b1</p>
47+
</section>
48+
<p class="box" id="root0">root0</p>
49+
</div>
50+
`;
51+
return doc;
52+
}
53+
54+
describe("getSourceScopedSelectorIndex", () => {
55+
it("numbers occurrences within each source file, not across the flattened document", () => {
56+
const doc = mixedSourceDocument();
57+
const read = (id: string, sourceFile: string | undefined) =>
58+
getSourceScopedSelectorIndex(doc, doc.getElementById(id)!, ".box", sourceFile, bySourceFile);
59+
60+
expect(read("a0", "a.html")).toBe(0);
61+
expect(read("a1", "a.html")).toBe(1);
62+
expect(read("b0", "b.html")).toBe(0);
63+
expect(read("b1", "b.html")).toBe(1);
64+
expect(read("root0", undefined)).toBe(0);
65+
// Asking for an element under the wrong scope is a miss, not a neighbour's index.
66+
expect(read("b0", "a.html")).toBeUndefined();
67+
});
68+
69+
it("matches the per-element reference for every element, inside a pass and outside it", () => {
70+
const doc = mixedSourceDocument();
71+
const boxes = Array.from(doc.querySelectorAll(".box"));
72+
const scopes = [undefined, "index.html", "a.html", "b.html", "missing.html"];
73+
const cases = boxes.flatMap((el) => scopes.map((scope) => ({ el, scope })));
74+
75+
const expected = cases.map(({ el, scope }) =>
76+
referenceIndex(doc, el, ".box", scope, bySourceFile),
77+
);
78+
79+
const outsidePass = cases.map(({ el, scope }) =>
80+
getSourceScopedSelectorIndex(doc, el, ".box", scope, bySourceFile),
81+
);
82+
const insidePass = withSelectorIndexPass(doc, () =>
83+
cases.map(({ el, scope }) =>
84+
getSourceScopedSelectorIndex(doc, el, ".box", scope, bySourceFile),
85+
),
86+
);
87+
88+
expect(outsidePass).toEqual(expected);
89+
expect(insidePass).toEqual(expected);
90+
});
91+
92+
it("returns undefined for the selectors that carry their own identity", () => {
93+
const doc = mixedSourceDocument();
94+
const el = doc.getElementById("a0")!;
95+
for (const selector of [undefined, "#a0", '[data-composition-id="root"]']) {
96+
expect(
97+
getSourceScopedSelectorIndex(doc, el, selector, "a.html", bySourceFile),
98+
).toBeUndefined();
99+
expect(
100+
withSelectorIndexPass(doc, () =>
101+
getSourceScopedSelectorIndex(doc, el, selector, "a.html", bySourceFile),
102+
),
103+
).toBeUndefined();
104+
}
105+
});
106+
107+
it("returns undefined for an invalid selector rather than throwing", () => {
108+
const doc = mixedSourceDocument();
109+
const el = doc.getElementById("a0")!;
110+
expect(getSourceScopedSelectorIndex(doc, el, ".((", "a.html", bySourceFile)).toBeUndefined();
111+
expect(
112+
withSelectorIndexPass(doc, () =>
113+
getSourceScopedSelectorIndex(doc, el, ".((", "a.html", bySourceFile),
114+
),
115+
).toBeUndefined();
116+
});
117+
118+
it("does not reuse one document's index for another, and restores the outer pass", () => {
119+
const inner = mixedSourceDocument();
120+
const outer = mixedSourceDocument();
121+
// A nested pass over a different document must not answer from, or poison,
122+
// the outer document's index.
123+
const nested = withSelectorIndexPass(outer, () =>
124+
withSelectorIndexPass(inner, () =>
125+
getSourceScopedSelectorIndex(
126+
inner,
127+
inner.getElementById("b1")!,
128+
".box",
129+
"b.html",
130+
bySourceFile,
131+
),
132+
),
133+
);
134+
expect(nested).toBe(1);
135+
136+
const afterNested = withSelectorIndexPass(outer, () => {
137+
withSelectorIndexPass(inner, () => undefined);
138+
return getSourceScopedSelectorIndex(
139+
outer,
140+
outer.getElementById("a1")!,
141+
".box",
142+
"a.html",
143+
bySourceFile,
144+
);
145+
});
146+
expect(afterNested).toBe(1);
147+
});
148+
});

0 commit comments

Comments
 (0)