• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1import type { Attribute, TagToken } from '../common/token.js';
2import type { TreeAdapter, TreeAdapterTypeMap } from '../tree-adapters/interface.js';
3
4//Const
5const NOAH_ARK_CAPACITY = 3;
6
7export enum EntryType {
8    Marker,
9    Element,
10}
11
12interface MarkerEntry {
13    type: EntryType.Marker;
14}
15
16export interface ElementEntry<T extends TreeAdapterTypeMap> {
17    type: EntryType.Element;
18    element: T['element'];
19    token: TagToken;
20}
21
22export type Entry<T extends TreeAdapterTypeMap> = MarkerEntry | ElementEntry<T>;
23
24const MARKER: MarkerEntry = { type: EntryType.Marker };
25
26//List of formatting elements
27export class FormattingElementList<T extends TreeAdapterTypeMap> {
28    entries: Entry<T>[] = [];
29    bookmark: Entry<T> | null = null;
30
31    constructor(private treeAdapter: TreeAdapter<T>) {}
32
33    //Noah Ark's condition
34    //OPTIMIZATION: at first we try to find possible candidates for exclusion using
35    //lightweight heuristics without thorough attributes check.
36    private _getNoahArkConditionCandidates(
37        newElement: T['element'],
38        neAttrs: Attribute[]
39    ): { idx: number; attrs: Attribute[] }[] {
40        const candidates = [];
41
42        const neAttrsLength = neAttrs.length;
43        const neTagName = this.treeAdapter.getTagName(newElement);
44        const neNamespaceURI = this.treeAdapter.getNamespaceURI(newElement);
45
46        for (let i = 0; i < this.entries.length; i++) {
47            const entry = this.entries[i];
48
49            if (entry.type === EntryType.Marker) {
50                break;
51            }
52
53            const { element } = entry;
54
55            if (
56                this.treeAdapter.getTagName(element) === neTagName &&
57                this.treeAdapter.getNamespaceURI(element) === neNamespaceURI
58            ) {
59                const elementAttrs = this.treeAdapter.getAttrList(element);
60
61                if (elementAttrs.length === neAttrsLength) {
62                    candidates.push({ idx: i, attrs: elementAttrs });
63                }
64            }
65        }
66
67        return candidates;
68    }
69
70    private _ensureNoahArkCondition(newElement: T['element']): void {
71        if (this.entries.length < NOAH_ARK_CAPACITY) return;
72
73        const neAttrs = this.treeAdapter.getAttrList(newElement);
74        const candidates = this._getNoahArkConditionCandidates(newElement, neAttrs);
75
76        if (candidates.length < NOAH_ARK_CAPACITY) return;
77
78        //NOTE: build attrs map for the new element, so we can perform fast lookups
79        const neAttrsMap = new Map(neAttrs.map((neAttr: Attribute) => [neAttr.name, neAttr.value]));
80        let validCandidates = 0;
81
82        //NOTE: remove bottommost candidates, until Noah's Ark condition will not be met
83        for (let i = 0; i < candidates.length; i++) {
84            const candidate = candidates[i];
85
86            // We know that `candidate.attrs.length === neAttrs.length`
87            if (candidate.attrs.every((cAttr) => neAttrsMap.get(cAttr.name) === cAttr.value)) {
88                validCandidates += 1;
89
90                if (validCandidates >= NOAH_ARK_CAPACITY) {
91                    this.entries.splice(candidate.idx, 1);
92                }
93            }
94        }
95    }
96
97    //Mutations
98    insertMarker(): void {
99        this.entries.unshift(MARKER);
100    }
101
102    pushElement(element: T['element'], token: TagToken): void {
103        this._ensureNoahArkCondition(element);
104
105        this.entries.unshift({
106            type: EntryType.Element,
107            element,
108            token,
109        });
110    }
111
112    insertElementAfterBookmark(element: T['element'], token: TagToken): void {
113        const bookmarkIdx = this.entries.indexOf(this.bookmark!);
114
115        this.entries.splice(bookmarkIdx, 0, {
116            type: EntryType.Element,
117            element,
118            token,
119        });
120    }
121
122    removeEntry(entry: Entry<T>): void {
123        const entryIndex = this.entries.indexOf(entry);
124
125        if (entryIndex >= 0) {
126            this.entries.splice(entryIndex, 1);
127        }
128    }
129
130    /**
131     * Clears the list of formatting elements up to the last marker.
132     *
133     * @see https://html.spec.whatwg.org/multipage/parsing.html#clear-the-list-of-active-formatting-elements-up-to-the-last-marker
134     */
135    clearToLastMarker(): void {
136        const markerIdx = this.entries.indexOf(MARKER);
137
138        if (markerIdx >= 0) {
139            this.entries.splice(0, markerIdx + 1);
140        } else {
141            this.entries.length = 0;
142        }
143    }
144
145    //Search
146    getElementEntryInScopeWithTagName(tagName: string): ElementEntry<T> | null {
147        const entry = this.entries.find(
148            (entry) => entry.type === EntryType.Marker || this.treeAdapter.getTagName(entry.element) === tagName
149        );
150
151        return entry && entry.type === EntryType.Element ? entry : null;
152    }
153
154    getElementEntry(element: T['element']): ElementEntry<T> | undefined {
155        return this.entries.find(
156            (entry): entry is ElementEntry<T> => entry.type === EntryType.Element && entry.element === element
157        );
158    }
159}
160