Commit 4eb28a7f authored by David Sveningsson's avatar David Sveningsson Committed by David Sveningsson
Browse files

perf: rewrite and optimize `HtmlElement.matches()` increasing performance of large documents 

Under some workloads this can increase performance by 2-3x times.

Fixes #45
parent 8fb0cc74

etc/browser.api.md

+1 −1
Original line number Diff line number Diff line
@@ -510,7 +510,7 @@ export class HtmlElement extends DOMNode { 
    is(tagName: string): boolean;

    get lastElementChild(): HtmlElement | null;

    loadMeta(meta: MetaElement): void;

    matches(selector: string): boolean;

    matches(selectorList: string): boolean;

    // (undocumented)

    get meta(): MetaElement | null;

    // (undocumented)

etc/index.api.md

+1 −1
Original line number Diff line number Diff line
@@ -601,7 +601,7 @@ export class HtmlElement extends DOMNode { 
    is(tagName: string): boolean;

    get lastElementChild(): HtmlElement | null;

    loadMeta(meta: MetaElement): void;

    matches(selector: string): boolean;

    matches(selectorList: string): boolean;

    // (undocumented)

    get meta(): MetaElement | null;

    // (undocumented)

src/dom/htmlelement.ts

+5 −19
Original line number Diff line number Diff line
@@ -375,25 +375,11 @@ export class HtmlElement extends DOMNode { 
	 *

	 * Implementation of DOM specification of Element.matches(selectors).

	 */

	public matches(selector: string): boolean {

		/* find root element */

		/* eslint-disable-next-line @typescript-eslint/no-this-alias -- false positive */

		let root: HtmlElement = this;

		while (root.parent) {

			root = root.parent;

		}



		/* a bit slow implementation as it finds all candidates for the selector and

		 * then tests if any of them are the current element. A better

		 * implementation would be to walk the selector right-to-left and test

		 * ancestors. */

		for (const match of root.querySelectorAll(selector)) {

			if (match.unique === this.unique) {

				return true;

			}

		}



		return false;

	public matches(selectorList: string): boolean {

		return selectorList.split(",").some((it) => {

			const selector = new Selector(it.trim());

			return selector.matchElement(this);

		});

	}



	public get meta(): MetaElement | null {

src/dom/pseudoclass/scope.ts

+1 −1
Original line number Diff line number Diff line
@@ -2,5 +2,5 @@ import { type HtmlElement } from "../htmlelement"; 
import { type SelectorContext } from "../selector";



export function scope(this: SelectorContext, node: HtmlElement): boolean {

	return node.isSameNode(this.scope);

	return Boolean(this.scope && node.isSameNode(this.scope));

}

src/dom/selector/match-element.spec.ts

0 → 100644
+100 −0
Original line number Diff line number Diff line 
import { Config } from "../../config";

import { Parser } from "../../parser";

import { Selector } from "./selector";



let parser: Parser;



beforeAll(async () => {

	const resolvedConfig = await Config.empty().resolve();

	parser = new Parser(resolvedConfig);

});



it("should match simple selector", () => {

	expect.assertions(8);

	const markup = /* HTML */ ` <p class="foo">lorem <em>ipsum</em></p> `;

	const document = parser.parseHtml(markup);

	const p = document.querySelector("p")!;

	const em = document.querySelector("em")!;

	expect(new Selector("p").matchElement(p)).toBeTruthy();

	expect(new Selector("p").matchElement(em)).toBeFalsy();

	expect(new Selector("em").matchElement(p)).toBeFalsy();

	expect(new Selector("em").matchElement(em)).toBeTruthy();

	expect(new Selector("div").matchElement(p)).toBeFalsy();

	expect(new Selector("div").matchElement(em)).toBeFalsy();

	expect(new Selector(".foo").matchElement(p)).toBeTruthy();

	expect(new Selector(".foo").matchElement(em)).toBeFalsy();

});



it("should match simple selectors with descendant combinator", () => {

	expect.assertions(5);

	const markup = /* HTML */ `

		<div>

			<h1>lorem <em>ipsum</em></h1>

			<p>lorem <em>ipsum</em></p>

			<h2>lorem <em>ipsum</em></h2>

		</div>

	`;

	const document = parser.parseHtml(markup);

	const em = document.querySelector("p > em")!;

	expect(new Selector("p em").matchElement(em)).toBeTruthy();

	expect(new Selector("div em").matchElement(em)).toBeTruthy();

	expect(new Selector("div p em").matchElement(em)).toBeTruthy();

	expect(new Selector("h1 em").matchElement(em)).toBeFalsy();

	expect(new Selector("h2 em").matchElement(em)).toBeFalsy();

});



it("should match simple selectors with child combinator", () => {

	expect.assertions(5);

	const markup = /* HTML */ `

		<div>

			<h1>lorem <em>ipsum</em></h1>

			<p>lorem <em>ipsum</em></p>

			<h2>lorem <em>ipsum</em></h2>

		</div>

	`;

	const document = parser.parseHtml(markup);

	const em = document.querySelector("p > em")!;

	expect(new Selector("p > em").matchElement(em)).toBeTruthy();

	expect(new Selector("div > em").matchElement(em)).toBeFalsy();

	expect(new Selector("div > p > em").matchElement(em)).toBeTruthy();

	expect(new Selector("h1 > em").matchElement(em)).toBeFalsy();

	expect(new Selector("h2 > em").matchElement(em)).toBeFalsy();

});



it("should match simple selectors with adjacent sibling combinator", () => {

	expect.assertions(5);

	const markup = /* HTML */ `

		<div>

			<h1>lorem <em>ipsum</em></h1>

			<p>lorem <em>ipsum</em></p>

			<h2>lorem <em>ipsum</em></h2>

		</div>

	`;

	const document = parser.parseHtml(markup);

	const p = document.querySelector("p")!;

	const h2 = document.querySelector("h2")!;

	expect(new Selector("h1 + p").matchElement(p)).toBeTruthy();

	expect(new Selector("p + h2").matchElement(h2)).toBeTruthy();

	expect(new Selector("h2 + p").matchElement(p)).toBeFalsy();

	expect(new Selector("h1 + h2").matchElement(h2)).toBeFalsy();

	expect(new Selector("div + p").matchElement(p)).toBeFalsy();

});



it("should match simple selectors with general sibling combinator", () => {

	expect.assertions(5);

	const markup = /* HTML */ `

		<div>

			<h1>lorem <em>ipsum</em></h1>

			<p>lorem <em>ipsum</em></p>

			<h2>lorem <em>ipsum</em></h2>

		</div>

	`;

	const document = parser.parseHtml(markup);

	const p = document.querySelector("p")!;

	const h2 = document.querySelector("h2")!;

	expect(new Selector("h1 ~ p").matchElement(p)).toBeTruthy();

	expect(new Selector("p ~ h2").matchElement(h2)).toBeTruthy();

	expect(new Selector("h2 ~ p").matchElement(p)).toBeFalsy();

	expect(new Selector("h1 ~ h2").matchElement(h2)).toBeTruthy();

	expect(new Selector("div ~ p").matchElement(p)).toBeFalsy();

});