import type {

SemanticNode,

SemanticNodeState,

SemanticTreeChange,

SemanticTreeObserverOptions,

SemanticTreeOptions,

} from "./types";

type WalkContext = {

options: Required<SemanticTreeOptions>;

nextId: number;

rootDocument: Document;

};

const defaultOptions: Required<SemanticTreeOptions> = {

mode: "compact",

includeBounds: true,

includeAttributes: true,

includeTextNodes: true,

includeHidden: false,

includeSelectOptions: true,

excludeLikelyAds: false,

excludeLikelyBoilerplate: false,

pruneCustomElementWrappers: true,

pruneCollapsedSubtrees: true,

pruneLikelyClosedOverlays: false,

summarizeLargeSubtrees: false,

summarizeLikelyLinkFarms: false,

summarizeRepeatedSubtrees: false,

maxChildrenPerNode: 80,

maxLinkFarmChildren: 24,

maxRepeatedSubtreeInstances: 3,

maxTextLength: 240,

};

const defaultObserverOptions: Required<Pick<SemanticTreeObserverOptions, "debounceMs">> = {

debounceMs: 50,

};

const interactiveRoles = new Set([

"button",

"checkbox",

"combobox",

"link",

"listbox",

"menuitem",

"menuitemcheckbox",

"menuitemradio",

"option",

"radio",

"searchbox",

"slider",

"spinbutton",

"switch",

"tab",

"textbox",

"treeitem",

]);

const landmarkTags: Record<string, string> = {

article: "article",

aside: "complementary",

footer: "contentinfo",

form: "form",

header: "banner",

main: "main",

nav: "navigation",

section: "region",

};

const rolesNamedFromContents = new Set([

"button",

"cell",

"checkbox",

"columnheader",

"heading",

"link",

"menuitem",

"menuitemcheckbox",

"menuitemradio",

"option",

"radio",

"rowheader",

"switch",

"tab",

"treeitem",

]);

export function extractSemanticTree(options: SemanticTreeOptions = {}): SemanticNode {

const rootDocument = document;

const context: WalkContext = {

options: { ...defaultOptions, ...options },

nextId: 1,

rootDocument,

};

return (

walkElement(rootDocument.body ?? rootDocument.documentElement, context) ??

unavailableNode(context, "document", "Document has no inspectable body")

);

}

export { extractSemanticTree as extract };

export function formatSemanticTreeText(node: SemanticNode): string {

const lines: string[] = [];

function visit(current: SemanticNode, depth: number): void {

const prefix = " ".repeat(depth);

const role = current.role ?? current.tag;

const marker = current.interactive ? "[i] " : "";

const name = current.name ? ` '${current.name}'` : "";

const state = formatState(current.state);

const unavailable = current.unavailableReason ? ` (${current.unavailableReason})` : "";

lines.push(`${prefix}${marker}${role}${name}${state}${unavailable}`);

for (const child of current.children) visit(child, depth + 1);

}

visit(node, 0);

return lines.join("\n");

}

export function observeSemanticTree(

onChange: (change: SemanticTreeChange) => void,

options: SemanticTreeObserverOptions = {},

): { disconnect: () => void; snapshot: () => SemanticNode } {

const root = document.documentElement;

const observerOptions = { ...defaultObserverOptions, ...options };

let mutationCount = 0;

let timeoutId: number | undefined;

function snapshot(): SemanticNode {

return extractSemanticTree(options);

}

function emit(): void {

timeoutId = undefined;

onChange({

tree: snapshot(),

changedAt: Date.now(),

mutationCount,

});

mutationCount = 0;

}

const observer = new MutationObserver((mutations) => {

mutationCount += mutations.length;

if (timeoutId !== undefined) window.clearTimeout(timeoutId);

timeoutId = window.setTimeout(emit, observerOptions.debounceMs);

});

observer.observe(root, {

attributes: true,

characterData: true,

childList: true,

subtree: true,

});

return {

disconnect() {

if (timeoutId !== undefined) window.clearTimeout(timeoutId);

observer.disconnect();

},

snapshot,

};

}

function walkElement(element: Element, context: WalkContext): SemanticNode | null {

if (!context.options.includeHidden && isHidden(element)) return null;

if (context.options.excludeLikelyAds && isLikelyAd(element)) return null;

const role = getRole(element);

const state = getState(element, context);

const focusable = isFocusable(element);

const interactive = isInteractive(element, role, focusable);

const name = role ? computeName(element, role, context) : "";

const description = computeDescription(element, context);

const tag = element.tagName.toLowerCase();

const children = collectChildren(element, context);

if (context.options.mode === "interactive" && !interactive) {

return children.length > 0

? containerNode(context, tag, children)

: null;

}

if (shouldPrune(element, role, name, interactive, children, context)) {

return children.length === 1 ? children[0] ?? null : containerNode(context, tag, children);

}

const node: SemanticNode = {

id: nextId(context),

tag,

role,

name,

interactive,

focusable,

children,

};

if (description) node.description = description;

const text = getDirectText(element, context.options.maxTextLength);

if (text) node.text = text;

const value = getValue(element);

if (value) node.value = value;

if (Object.keys(state).length > 0) node.state = state;

node.selector = getCssPath(element);

node.xpath = getXPath(element);

if (context.options.includeBounds) node.bounds = getBounds(element);

if (context.options.includeAttributes) node.attributes = getAttributes(element);

appendSpecialChildren(element, node, context);

appendShadowChildren(element, node, context);

appendFrameChildren(element, node, context);

return node;

}

function collectChildren(element: Element, context: WalkContext): SemanticNode[] {

const children: SemanticNode[] = [];

for (const child of Array.from(element.childNodes)) {

if (child.nodeType === Node.ELEMENT_NODE) {

if (!context.options.includeSelectOptions && element instanceof HTMLSelectElement) continue;

const semanticChild = walkElement(child as Element, context);

if (semanticChild) children.push(semanticChild);

continue;

}

if (context.options.includeTextNodes && child.nodeType === Node.TEXT_NODE) {

const text = normalizeText(child.textContent ?? "", context.options.maxTextLength);

if (text) {

children.push({

id: nextId(context),

tag: "#text",

role: "text",

name: text,

text,

interactive: false,

focusable: false,

children: [],

});

}

}

}

return children;

}

function shouldPrune(

element: Element,

role: string | null,

name: string,

interactive: boolean,

children: SemanticNode[],

context: WalkContext,

): boolean {

if (context.options.mode === "full") return false;

if (role === "none" || role === "presentation") return true;

if (interactive) return false;

if (context.options.pruneCustomElementWrappers && isCustomElement(element)) return children.length > 0;

if (role && role !== "generic") return false;

if (name) return false;

if (element.id || element.getAttribute("aria-label") || element.getAttribute("aria-labelledby")) return false;

return children.length > 0;

}

function getRole(element: Element): string | null {

const explicit = firstToken(element.getAttribute("role"));

if (explicit) return explicit;

const tag = element.tagName.toLowerCase();

if (tag === "section" && !hasExplicitNameSource(element)) return null;

if (tag === "form" && !hasExplicitNameSource(element)) return null;

if (tag in landmarkTags) return landmarkTags[tag] ?? null;

if (/^h[1-6]$/.test(tag)) return "heading";

if (tag === "a" || tag === "area") return element.hasAttribute("href") ? "link" : null;

if (tag === "button") return "button";

if (tag === "details") return "group";

if (tag === "dialog") return "dialog";

if (tag === "fieldset") return "group";

if (tag === "figure") return "figure";

if (tag === "iframe") return "iframe";

if (tag === "img") return hasEmptyAlt(element) ? "presentation" : "img";

if (tag === "li") return "listitem";

if (tag === "ol" || tag === "ul") return "list";

if (tag === "optgroup") return "group";

if (tag === "option") return "option";

if (tag === "output") return "status";

if (tag === "progress") return "progressbar";

if (tag === "select") return element.hasAttribute("multiple") ? "listbox" : "combobox";

if (tag === "summary") return "button";

if (tag === "table") return "table";

if (tag === "caption") return "caption";

if (tag === "tbody" || tag === "tfoot" || tag === "thead") return "rowgroup";

if (tag === "td") return "cell";

if (tag === "textarea") return "textbox";

if (tag === "th") return element.getAttribute("scope") === "row" ? "rowheader" : "columnheader";

if (tag === "tr") return "row";

if (tag === "input") return inputRole(element as HTMLInputElement);

return null;

}

function inputRole(input: HTMLInputElement): string | null {

const type = (input.getAttribute("type") || "text").toLowerCase();

if (type === "button" || type === "image" || type === "reset" || type === "submit") return "button";

if (type === "checkbox") return "checkbox";

if (type === "email" || type === "tel" || type === "text" || type === "url") return "textbox";

if (type === "number") return "spinbutton";

if (type === "radio") return "radio";

if (type === "range") return "slider";

if (type === "search") return "searchbox";

if (type === "hidden") return null;

return "textbox";

}

function computeName(element: Element, role: string, context: WalkContext): string {

if (element.getAttribute("aria-labelledby")) {

const labelled = textFromIds(element.getAttribute("aria-labelledby") ?? "", context.rootDocument);

if (labelled) return labelled;

}

const ariaLabel = element.getAttribute("aria-label");

if (ariaLabel) return normalizeText(ariaLabel, context.options.maxTextLength);

if (element instanceof HTMLInputElement && isButtonLikeInput(element)) {

return normalizeText(element.value || element.getAttribute("value") || inputFallbackName(element), context.options.maxTextLength);

}

if (element instanceof HTMLInputElement || element instanceof HTMLTextAreaElement || element instanceof HTMLSelectElement) {

const label = labelText(element, context);

if (label) return label;

const placeholder = element.getAttribute("placeholder");

if (placeholder) return normalizeText(placeholder, context.options.maxTextLength);

}

if (element instanceof HTMLImageElement) {

return normalizeText(element.alt || element.getAttribute("title") || "", context.options.maxTextLength);

}

if (element instanceof HTMLFieldSetElement) {

const legend = element.querySelector(":scope > legend");

if (legend) return getVisibleText(legend, context.options.maxTextLength);

}

if (rolesNamedFromContents.has(role)) {

const ownText = getVisibleText(element, context.options.maxTextLength);

if (ownText) return ownText;

}

return normalizeText(element.getAttribute("title") ?? "", context.options.maxTextLength);

}

function computeDescription(element: Element, context: WalkContext): string {

const describedBy = element.getAttribute("aria-describedby");

if (describedBy) return textFromIds(describedBy, context.rootDocument);

return normalizeText(element.getAttribute("title") ?? "", context.options.maxTextLength);

}

function labelText(

element: HTMLInputElement | HTMLTextAreaElement | HTMLSelectElement,

context: WalkContext,

): string {

if (element.labels && element.labels.length > 0) {

return normalizeText(Array.from(element.labels).map((label) => getVisibleText(label, context.options.maxTextLength)).join(" "), context.options.maxTextLength);

}

return "";

}

function getState(element: Element, context: WalkContext): SemanticNodeState {

const state: SemanticNodeState = {};

if (isHidden(element)) state.hidden = true;

if (isDisabled(element)) state.disabled = true;

const busy = ariaBoolean(element.getAttribute("aria-busy"));

if (busy !== undefined) state.busy = busy;

const multiselectable = ariaBoolean(element.getAttribute("aria-multiselectable"));

if (multiselectable !== undefined) state.multiselectable = multiselectable;

const sort = element.getAttribute("aria-sort");

if (sort) state.sort = normalizeText(sort, 40);

const grabbed = ariaBoolean(element.getAttribute("aria-grabbed"));

if (grabbed !== undefined) state.grabbed = grabbed;

const dropEffect = element.getAttribute("aria-dropeffect");

if (dropEffect) state.dropEffect = normalizeText(dropEffect, 80);

if (element === document.activeElement) state.focused = true;

const checked = ariaBooleanOrMixed(element.getAttribute("aria-checked"));

if (checked !== undefined) state.checked = checked;

else if (element instanceof HTMLInputElement && (element.type === "checkbox" || element.type === "radio")) {

state.checked = element.checked;

}

const selected = ariaBoolean(element.getAttribute("aria-selected"));

if (selected !== undefined) state.selected = selected;

else if (element instanceof HTMLOptionElement) state.selected = element.selected;

const expanded = ariaBoolean(element.getAttribute("aria-expanded"));

if (expanded !== undefined) state.expanded = expanded;

const pressed = ariaBooleanOrMixed(element.getAttribute("aria-pressed"));

if (pressed !== undefined) state.pressed = pressed;

const required = ariaBoolean(element.getAttribute("aria-required"));

if (required !== undefined) state.required = required;

else if ("required" in element && Boolean((element as HTMLInputElement).required)) state.required = true;

const invalid = element.getAttribute("aria-invalid");

if (invalid && invalid !== "false") state.invalid = invalid === "true" ? true : invalid;

if (element instanceof HTMLInputElement || element instanceof HTMLTextAreaElement) {

if (element.readOnly) state.readonly = true;

}

const current = element.getAttribute("aria-current");

if (current && current !== "false") state.current = current === "true" ? true : current;

const haspopup = element.getAttribute("aria-haspopup");

if (haspopup && haspopup !== "false") state.haspopup = haspopup === "true" ? true : haspopup;

const controls = element.getAttribute("aria-controls");

if (controls) state.controls = normalizeText(controls, context.options.maxTextLength);

const live = element.getAttribute("aria-live");

if (live) state.live = normalizeText(live, context.options.maxTextLength);

if (element.getAttribute("aria-modal") === "true") state.modal = true;

const orientation = element.getAttribute("aria-orientation");

if (orientation) state.orientation = normalizeText(orientation, 40);

const valueMin = ariaNumber(element.getAttribute("aria-valuemin"));

if (typeof valueMin === "number") state.valueMin = valueMin;

const valueMax = ariaNumber(element.getAttribute("aria-valuemax"));

if (typeof valueMax === "number") state.valueMax = valueMax;

const valueNow = ariaNumber(element.getAttribute("aria-valuenow"));

if (typeof valueNow === "number") state.valueNow = valueNow;

const valueText = element.getAttribute("aria-valuetext");

if (valueText) state.valueText = normalizeText(valueText, context.options.maxTextLength);

return state;

}

function isHidden(element: Element): boolean {

if (element.hasAttribute("hidden")) return true;

if (element.getAttribute("aria-hidden") === "true") return true;

const style = getComputedStyle(element);

if (

style.display === "none" ||

style.visibility === "hidden" ||

style.contentVisibility === "hidden"

) return true;

if (Number(style.opacity) === 0) return true;

return false;

}

function isLikelyAd(element: Element): boolean {

const haystack = [

element.id,

element.getAttribute("class"),

element.getAttribute("aria-label"),

element.getAttribute("data-testid"),

element.getAttribute("data-test-id"),

element.getAttribute("data-name"),

].filter(Boolean).join(" ").toLowerCase();

if (/\b(ad|ads|advert|advertisement|sponsor|sponsored|placement)\b/.test(haystack)) return true;

if (element instanceof HTMLAnchorElement && normalizeText(element.textContent ?? "", 80).toLowerCase() === "ad") return true;

return false;

}

function isDisabled(element: Element): boolean {

if (element.getAttribute("aria-disabled") === "true") return true;

return "disabled" in element && Boolean((element as HTMLButtonElement).disabled);

}

function isFocusable(element: Element): boolean {

if (isDisabled(element) || isHidden(element)) return false;

const tabindex = element.getAttribute("tabindex");

if (tabindex !== null) return Number(tabindex) >= 0;

return element.matches("a[href],area[href],button,input,select,textarea,summary,iframe,[contenteditable=''],[contenteditable='true']");

}

function isInteractive(element: Element, role: string | null, focusable: boolean): boolean {

if (role && interactiveRoles.has(role)) return true;

if (element.matches("a[href],button,input,select,textarea,summary,option")) return true;

if (element.hasAttribute("onclick")) return true;

return focusable && Boolean(role);

}

function appendSpecialChildren(element: Element, node: SemanticNode, context: WalkContext): void {

if (!context.options.includeSelectOptions) return;

if (element instanceof HTMLSelectElement) {

for (const option of Array.from(element.options)) {

node.children.push({

id: nextId(context),

tag: "option",

role: "option",

name: normalizeText(option.textContent ?? "", context.options.maxTextLength),

value: option.value,

state: { selected: option.selected, disabled: option.disabled },

interactive: false,

focusable: false,

selector: getCssPath(option),

xpath: getXPath(option),

children: [],

});

}

}

}

function isCustomElement(element: Element): boolean {

return element.tagName.includes("-");

}

function appendShadowChildren(element: Element, node: SemanticNode, context: WalkContext): void {

const shadowRoot = element.shadowRoot;

if (!shadowRoot) return;

for (const child of Array.from(shadowRoot.children)) {

const semanticChild = walkElement(child, context);

if (semanticChild) node.children.push(semanticChild);

}

}

function appendFrameChildren(element: Element, node: SemanticNode, context: WalkContext): void {

if (!(element instanceof HTMLIFrameElement)) return;

try {

const frameDocument = element.contentDocument;

if (!frameDocument?.body) {

node.children.push(unavailableNode(context, "iframe", "iframe document unavailable"));

return;

}

const previousDocument = context.rootDocument;

context.rootDocument = frameDocument;

const child = walkElement(frameDocument.body, context);

context.rootDocument = previousDocument;

if (child) node.children.push(child);

} catch {

node.children.push(unavailableNode(context, "iframe", "cross-origin iframe"));

}

}

function unavailableNode(context: WalkContext, tag: string, reason: string): SemanticNode {

return {

id: nextId(context),

tag,

role: null,

name: "",

interactive: false,

focusable: false,

unavailableReason: reason,

children: [],

};

}

function containerNode(context: WalkContext, tag: string, children: SemanticNode[]): SemanticNode {

return {

id: nextId(context),

tag,

role: null,

name: "",

interactive: false,

focusable: false,

children,

};

}

function getValue(element: Element): string {

if (element instanceof HTMLInputElement || element instanceof HTMLTextAreaElement || element instanceof HTMLSelectElement) {

return element.value;

}

return normalizeText(element.getAttribute("aria-valuetext") ?? element.getAttribute("aria-valuenow") ?? "", 80);

}

function getDirectText(element: Element, maxLength: number): string {

return normalizeText(

Array.from(element.childNodes)

.filter((node) => node.nodeType === Node.TEXT_NODE)

.map((node) => node.textContent ?? "")

.join(" "),

maxLength,

);

}

function getVisibleText(element: Element, maxLength: number): string {

const parts: string[] = [];

function visit(node: Node): void {

if (node.nodeType === Node.TEXT_NODE) {

parts.push(node.textContent ?? "");

return;

}

if (node.nodeType !== Node.ELEMENT_NODE) return;

const childElement = node as Element;

if (isHidden(childElement)) return;

for (const child of Array.from(childElement.childNodes)) visit(child);

}

visit(element);

return normalizeText(parts.join(" "), maxLength);

}

function getAttributes(element: Element): Record<string, string> {

const attributes: Record<string, string> = {};

for (const attribute of Array.from(element.attributes)) {

if (

attribute.name === "id" ||

attribute.name === "href" ||

attribute.name === "type" ||

attribute.name === "role" ||

attribute.name === "alt" ||

attribute.name === "title" ||

attribute.name.startsWith("aria-") ||

attribute.name.startsWith("data-")

) {

attributes[attribute.name] = attribute.value;

}

}

return attributes;

}

function getBounds(element: Element) {

const rect = element.getBoundingClientRect();

return {

x: round(rect.x),

y: round(rect.y),

width: round(rect.width),

height: round(rect.height),

};

}

function getCssPath(element: Element): string {

if (element.id) return `#${cssEscape(element.id)}`;

const segments: string[] = [];

let current: Element | null = element;

while (current && current.nodeType === Node.ELEMENT_NODE && current !== document.documentElement) {

const elementAtLevel: Element = current;

const tag = elementAtLevel.tagName.toLowerCase();

const parent: Element | null = elementAtLevel.parentElement;

if (!parent) {

segments.unshift(tag);

break;

}

const siblings = Array.from(parent.children).filter((child) => child.tagName === elementAtLevel.tagName);

const index = siblings.indexOf(elementAtLevel) + 1;

segments.unshift(siblings.length > 1 ? `${tag}:nth-of-type(${index})` : tag);

current = parent;

}

return segments.join(" > ");

}

function getXPath(element: Element): string {

const segments: string[] = [];

let current: Element | null = element;

while (current && current.nodeType === Node.ELEMENT_NODE) {

const elementAtLevel: Element = current;

const tag = elementAtLevel.tagName.toLowerCase();

const parent: Element | null = elementAtLevel.parentElement;

if (!parent) {

segments.unshift(`/${tag}[1]`);

break;

}

const sameTag = Array.from(parent.children).filter((child) => child.tagName === elementAtLevel.tagName);

segments.unshift(`/${tag}[${sameTag.indexOf(elementAtLevel) + 1}]`);

current = parent;

}

return segments.join("");

}

function textFromIds(ids: string, rootDocument: Document): string {

return normalizeText(

ids

.split(/\s+/)

.map((id) => {

const element = rootDocument.getElementById(id);

return element ? getVisibleText(element, 240) : "";

})

.filter(Boolean)

.join(" "),

240,

);

}

function normalizeText(value: string, maxLength: number): string {

const normalized = value.replace(/\s+/g, " ").trim();

return normalized.length > maxLength ? `${normalized.slice(0, maxLength - 1)}…` : normalized;

}

function firstToken(value: string | null): string | null {

return value?.trim().split(/\s+/)[0] || null;

}

function hasExplicitNameSource(element: Element): boolean {

return Boolean(

element.getAttribute("aria-label") ||

element.getAttribute("aria-labelledby") ||

element.getAttribute("title"),

);

}

function hasEmptyAlt(element: Element): boolean {

return element.hasAttribute("alt") && element.getAttribute("alt") === "";

}

function isButtonLikeInput(input: HTMLInputElement): boolean {

return ["button", "image", "reset", "submit"].includes((input.getAttribute("type") || "").toLowerCase());

}

function inputFallbackName(input: HTMLInputElement): string {

const type = (input.getAttribute("type") || "").toLowerCase();

if (type === "submit") return "Submit";

if (type === "reset") return "Reset";

return "";

}

function ariaBoolean(value: string | null): boolean | undefined {

if (value === "true") return true;

if (value === "false") return false;

return undefined;

}

function ariaBooleanOrMixed(value: string | null): boolean | "mixed" | undefined {

if (value === "mixed") return "mixed";

return ariaBoolean(value);

}

function ariaNumber(value: string | null): number | undefined {

if (value === null || value.trim() === "") return undefined;

const parsed = Number(value);

return Number.isFinite(parsed) ? parsed : undefined;

}

function formatState(state: SemanticNodeState | undefined): string {

if (!state) return "";

const entries = Object.entries(state).filter(([, value]) => value !== undefined);

return entries.length > 0

? ` [${entries.map(([key, value]) => `${key}=${String(value)}`).join(" ")}]`

: "";

}

function nextId(context: WalkContext): string {

const id = `n${context.nextId}`;

context.nextId += 1;

return id;

}

function round(value: number): number {

return Math.round(value * 100) / 100;

}

function cssEscape(value: string): string {

if (typeof CSS !== "undefined" && typeof CSS.escape === "function") {

return CSS.escape(value);

}

return value.replace(/[^a-zA-Z0-9_-]/g, (char) => `\\${char}`);

}