modules/html/dom.zzm

=encoding utf8

=head1 NAME

html/dom - DOM-like classes for parsed HTML documents.

=head1 SYNOPSIS

  from html/dom import HTMLDocument;
  
  let doc := new HTMLDocument();
  let root := doc.createElement("html");
  doc.appendChild( doc.createDoctype() );
  doc.appendChild(root);
  root.appendChild( doc.createElement("body") );

=head1 DESCRIPTION

This module provides the pure ZuzuScript mutable DOM core used by
C<html/parser>. It intentionally mirrors the practical DOM-like API
provided by C<std/data/xml>: construction, traversal, mutation,
attributes, simple selector lookup, cloning, equality, tree walking, and
serialization.

C<HTMLTemplateElement> owns an C<HTMLDocumentFragment> returned by
C<content()>. Parsed template children live in that fragment rather than
as direct children of the template element. Elements and attributes are
namespace-aware for HTML, SVG, MathML, XLink, XML, and XMLNS data used by
the HTML tree builder.

Documents may be created manually through constructors and
C<HTMLDocument> factory methods, or by C<html/parser>.

=head1 EXPORTS

=head2 Classes

=over

=item C<HTMLNode>

Base node class. It implements shared metadata, traversal, mutation,
text content, cloning, equality, tree walking, simple selector lookup,
serialization, and unsupported XPath compatibility methods.

Core methods include C<nodeName>, C<nodeType>, C<nodeValue>,
C<setNodeValue>, C<nodeKind>, C<uniqueKey>, C<unique_id>, C<localName>,
C<namespaceURI>, C<firstChild>, C<lastChild>, C<nextSibling>,
C<previousSibling>, C<parentNode>, C<ownerDocument>, C<childNodes>,
C<children>, C<hasChildNodes>, C<appendChild>, C<prependChild>,
C<insertBefore>, C<replaceChild>, C<removeChild>, C<remove>,
C<textContent>, C<setTextContent>, C<normalize>, C<cloneNode>,
C<isSameNode>, C<isEqualNode>, C<contains>, C<querySelectorAll>,
C<querySelector>, C<findnodes>, C<findvalue>, C<visitEach>,
C<findFirst>, C<toHTML>, C<toXML>, and C<to_String>.

=item C<HTMLDocument>

Document node class. It adds C<documentElement>, node factories,
C<getElementsByTagName>, and C<getElementById>. A document may contain
one doctype, one element root, and comments. Text directly under a
document is rejected.

Factory methods are C<createElement>, C<createElementNS>,
C<createTextNode>, C<createComment>, C<createDoctype>, and
C<createCDATASection>. C<createElement("template")> returns an
C<HTMLTemplateElement>. C<createElementNS> should be used for SVG and
MathML elements. The lookup methods C<getElementsByTagName> and
C<getElementById> search the document's descendant elements.

=item C<HTMLElement>

Element node class. It adds C<tagName>, C<id>, C<setId>,
C<getAttribute>, C<setAttribute>, C<hasAttribute>,
C<removeAttribute>, C<attributeNames>, C<attributes>, namespaced
attribute methods, C<attributeRecords>, and descendant
C<getElementsByTagName>. Namespaced attribute methods are
C<getAttributeNS>, C<setAttributeNS>, C<hasAttributeNS>, and
C<removeAttributeNS>. C<namespaceURI> and C<localName> are authoritative
for HTML, SVG, and MathML elements. Attribute values are stored as
strings; missing attributes return C<null>.

=item C<HTMLTemplateElement>, C<HTMLDocumentFragment>

Template elements and their content fragments. C<HTMLDocument>'s
C<createElement("template")> returns an C<HTMLTemplateElement>.
C<HTMLTemplateElement.content()> returns the fragment containing parsed
or manually inserted template contents. C<HTMLDocumentFragment> supports
the normal container operations and C<getElementsByTagName>. Direct
children of parsed templates live in C<content()>, not in the template
element's own C<childNodes()> array.

=item C<HTMLText>, C<HTMLComment>, C<HTMLDoctype>

Text, comment, and doctype node classes. Text and comments expose
C<data> and C<setData>. Doctypes expose C<name>, C<publicId>, and
C<systemId>. C<HTMLDoctype> is normally created with
C<HTMLDocument.createDoctype>.

=item C<DOMNode>, C<DOMDocument>, C<DOMElement>, C<DOMText>,
C<DOMComment>, C<DOMDoctype>

DOM-compatible aliases implemented as subclasses of the HTML classes.

=back

=head2 Constants

=over

=item C<HTML_NAMESPACE_URI>, C<SVG_NAMESPACE_URI>, C<MATHML_NAMESPACE_URI>,
C<XLINK_NAMESPACE_URI>, C<XML_NAMESPACE_URI>, C<XMLNS_NAMESPACE_URI>

Namespace URI constants used by the parser and DOM namespace APIs.

=back

=head1 LIMITATIONS

=over

=item * C<findnodes> and C<findvalue> throw clear unsupported errors.

There is no XPath or ZPath strategy in this distribution.

=item * C<querySelector> and C<querySelectorAll> support only simple
selectors: tag names, C<#id>, C<.class>, and C<*>.

Combinators, comma lists, pseudo-classes, namespace selectors, and
attribute selectors throw clear unsupported-selector errors.

=item * Namespace support covers the HTML, SVG, MathML, XLink, XML, and
XMLNS namespace URIs used by the HTML tree builder.

Use C<createElementNS>, C<setAttributeNS>, C<getAttributeNS>,
C<hasAttributeNS>, C<removeAttributeNS>, and C<attributeRecords> for
namespace-aware code. The older attribute methods remain available and
operate on serialized qualified names.

=item * C<createCDATASection> returns an C<HTMLText> node.

HTML documents do not have CDATA section nodes in this DOM core, but the
method is provided for C<std/data/xml> API compatibility.

=item * C<toHTML(pretty)> and C<toXML(pretty)> accept C<pretty> but
currently serialize compact HTML.

The serializer emits document children in order, doctypes, comments,
escaped text and attributes, and HTML void elements without end tags.

=back

=head1 COPYRIGHT AND LICENCE

B<< html/dom >> is copyright Toby Inkster.

It is free software; you may redistribute it and/or modify it under
the terms of either the Artistic License 1.0 or the GNU General Public
License version 2.

=cut

from std/string import join, replace, split, substr, trim;

let _HTML_DOM_NEXT_UID := 0;

let HTML_NAMESPACE_URI := "http://www.w3.org/1999/xhtml";
let SVG_NAMESPACE_URI := "http://www.w3.org/2000/svg";
let MATHML_NAMESPACE_URI := "http://www.w3.org/1998/Math/MathML";
let XLINK_NAMESPACE_URI := "http://www.w3.org/1999/xlink";
let XML_NAMESPACE_URI := "http://www.w3.org/XML/1998/namespace";
let XMLNS_NAMESPACE_URI := "http://www.w3.org/2000/xmlns/";

function _html_dom_die ( String message ) {
	die "html/dom: " _ message;
}

function _html_dom_next_uid () {
	_HTML_DOM_NEXT_UID++;
	return "html-node-" _ _HTML_DOM_NEXT_UID;
}

function _html_dom_string ( value ) {
	return value ≡ null ? "" : "" _ value;
}

function _html_dom_name ( value ) {
	let name := lc(trim(_html_dom_string(value)));
	_html_dom_die("empty element or attribute name") if name eq "";
	return name;
}

function _html_dom_doctype_name ( value ) {
	return lc(trim(_html_dom_string(value)));
}

function _html_dom_qname_parts ( value ) {
	let qname := trim(_html_dom_string(value));
	_html_dom_die("empty qualified name") if qname eq "";
	let bits := split( qname, ":" );
	_html_dom_die("malformed qualified name") if bits.length() > 2;
	if ( bits.length() == 2 ) {
		_html_dom_die("malformed qualified name")
			if bits[0] eq "" or bits[1] eq "";
		return { prefix: bits[0], localName: bits[1], qualifiedName: qname };
	}
	return { prefix: null, localName: qname, qualifiedName: qname };
}

function _html_dom_normal_namespace ( namespaceURI ) {
	return null if namespaceURI ≡ null;
	let ns := _html_dom_string(namespaceURI);
	return null if ns eq "";
	return ns;
}

function _html_dom_attribute_record (
	namespaceURI,
	qualifiedName,
	value,
	Boolean html_name := false,
) {
	let parts := _html_dom_qname_parts(qualifiedName);
	let display := html_name ? _html_dom_name(qualifiedName) : parts{qualifiedName};
	let local := html_name ? display : parts{localName};
	let prefix := html_name ? null : parts{prefix};
	return {
		name: display,
		qualifiedName: display,
		localName: local,
		prefix: prefix,
		namespaceURI: _html_dom_normal_namespace(namespaceURI),
		value: _html_dom_string(value),
	};
}

function _html_dom_copy_attr_record ( Dict record ) {
	return {
		name: record{name},
		qualifiedName: record{qualifiedName},
		localName: record{localName},
		prefix: record{prefix},
		namespaceURI: record{namespaceURI},
		value: record{value},
	};
}

function _html_dom_copy_array ( Array values ) {
	let out := [];
	for ( let value in values ) {
		out.push(value);
	}
	return out;
}

function _html_dom_escape_text ( value ) {
	let out := _html_dom_string(value);
	out := replace( out, "&", "&amp;", "g" );
	out := replace( out, "<", "&lt;", "g" );
	out := replace( out, ">", "&gt;", "g" );
	return out;
}

function _html_dom_escape_attr ( value ) {
	let out := _html_dom_escape_text(value);
	out := replace( out, "\"", "&quot;", "g" );
	return out;
}

function _html_dom_void_elements () {
	return [
		"area",
		"base",
		"br",
		"col",
		"embed",
		"hr",
		"img",
		"input",
		"link",
		"meta",
		"source",
		"track",
		"wbr",
	];
}

function _html_dom_is_void_element ( String name ) {
	return _html_dom_void_elements().contains(lc(name));
}

class HTMLNode {
	let String _node_kind := "node";
	let String _node_name := "";
	let _node_value := null;
	let _parent_node := null;
	let _owner_document := null;
	let Array _child_nodes := [];
	let String _uid := "";

	method __build__ () {
		self._init_node();
	}

	method _init_node () {
		_child_nodes := [] if _child_nodes ≡ null;
		_uid := _html_dom_next_uid() if _uid ≡ null or _uid eq "";
		_node_name := self._default_node_name()
			if _node_name ≡ null or _node_name eq "";
	}

	method _configure_node ( String kind, String name ) {
		_node_kind := kind;
		_node_name := name;
		return self;
	}

	method _normalise_node_value () {
		_node_value := _html_dom_string(_node_value);
		return self;
	}

	method _use_data_alias ( data ) {
		_node_value := data unless data ≡ null;
		return self;
	}

	method _default_node_name () {
		switch ( _node_kind: eq ) {
			case "document": return "#document";
			case "fragment": return "#document-fragment";
			case "text": return "#text";
			case "comment": return "#comment";
			case "doctype": return "html";
			default: return _node_name;
		}
	}

	method _set_owner_document_recursive ( owner ) {
		_owner_document := owner;
		for ( let child in _child_nodes ) {
			child._set_owner_document_recursive(owner);
		}
		return self;
	}

	method nodeName () {
		return _node_name;
	}

	method nodeType () {
		switch ( _node_kind: eq ) {
			case "element": return "1";
			case "text": return "3";
			case "comment": return "8";
			case "document": return "9";
			case "doctype": return "10";
			case "fragment": return "11";
			default: return "0";
		}
	}

	method nodeValue () {
		if ( _node_kind eq "text" or _node_kind eq "comment" ) {
			return _node_value;
		}
		return null;
	}

	method setNodeValue ( value ) {
		if ( _node_kind eq "text" or _node_kind eq "comment" ) {
			_node_value := _html_dom_string(value);
			return self;
		}
		_html_dom_die("setNodeValue is only supported for text and comment nodes");
	}

	method nodeKind () {
		return _node_kind;
	}

	method uniqueKey () {
		return _uid;
	}

	method unique_id () {
		return _uid;
	}

	method localName () {
		return self.nodeName();
	}

	method namespaceURI () {
		return null;
	}

	method firstChild () {
		return null if _child_nodes.length() == 0;
		return _child_nodes[0];
	}

	method lastChild () {
		return null if _child_nodes.length() == 0;
		return _child_nodes[ _child_nodes.length() - 1 ];
	}

	method _sibling ( Number offset ) {
		return null if _parent_node ≡ null;
		let siblings := _parent_node.childNodes();
		let i := 0;
		while ( i < siblings.length() ) {
			if ( siblings[i] ≡ self ) {
				let wanted := i + offset;
				return null if wanted < 0 or wanted >= siblings.length();
				return siblings[wanted];
			}
			i++;
		}
		return null;
	}

	method nextSibling () {
		return self._sibling(1);
	}

	method previousSibling () {
		return self._sibling(-1);
	}

	method parentNode () {
		return _parent_node;
	}

	method ownerDocument () {
		return self if _node_kind eq "document";
		return _owner_document;
	}

	method childNodes () {
		return _html_dom_copy_array(_child_nodes);
	}

	method children () {
		let out := [];
		for ( let child in _child_nodes ) {
			out.push(child) if child.nodeKind() eq "element";
		}
		return out;
	}

	method hasChildNodes () {
		return _child_nodes.length() > 0;
	}

	method _assert_can_insert ( node ) {
		_html_dom_die("cannot insert null node") if node ≡ null;
		_html_dom_die("cannot insert document node")
			if node.nodeKind() eq "document";
		_html_dom_die("cannot insert node into itself")
			if node ≡ self;
		_html_dom_die("cannot insert ancestor into descendant")
			if node.contains(self);

		if ( self.nodeKind() eq "document" ) {
			_html_dom_die("cannot insert text directly under document")
				if node.nodeKind() eq "text";
			if ( node.nodeKind() eq "element" ) {
				for ( let child in _child_nodes ) {
					_html_dom_die("document already has a root element")
						if child.nodeKind() eq "element" and child ≢ node;
				}
			}
			if ( node.nodeKind() eq "doctype" ) {
				for ( let child in _child_nodes ) {
					_html_dom_die("document already has a doctype")
						if child.nodeKind() eq "doctype" and child ≢ node;
				}
			}
		}
		return self;
	}

	method _owner_for_insert () {
		if ( self.nodeKind() eq "document" ) {
			return self;
		}
		return self.ownerDocument();
	}

	method _insert_at ( node, Number index ) {
		self._assert_can_insert(node);
		node.remove() if node.parentNode() ≢ null;

		let kept := [];
		let inserted := false;
		let i := 0;
		if ( index <= 0 ) {
			kept.push(node);
			inserted := true;
		}
		while ( i < _child_nodes.length() ) {
			if ( not inserted and i >= index ) {
				kept.push(node);
				inserted := true;
			}
			kept.push(_child_nodes[i]);
			i++;
		}
		kept.push(node) unless inserted;

		_child_nodes := kept;
		node{_parent_node} := self;
		node._set_owner_document_recursive(self._owner_for_insert());
		return node;
	}

	method appendChild ( node ) {
		return self._insert_at( node, _child_nodes.length() );
	}

	method prependChild ( node ) {
		return self._insert_at( node, 0 );
	}

	method insertBefore ( newNode, refNode ) {
		let i := 0;
		while ( i < _child_nodes.length() ) {
			return self._insert_at( newNode, i ) if _child_nodes[i] ≡ refNode;
			i++;
		}
		_html_dom_die("insertBefore reference node is not a child");
	}

	method replaceChild ( newNode, oldNode ) {
		let i := 0;
		while ( i < _child_nodes.length() ) {
			if ( _child_nodes[i] ≡ oldNode ) {
				self._assert_can_insert(newNode);
				newNode.remove() if newNode.parentNode() ≢ null;
				let kept := [];
				let j := 0;
				while ( j < _child_nodes.length() ) {
					kept.push( j == i ? newNode : _child_nodes[j] );
					j++;
				}
				_child_nodes := kept;
				oldNode{_parent_node} := null;
				newNode{_parent_node} := self;
				newNode._set_owner_document_recursive(self._owner_for_insert());
				return oldNode;
			}
			i++;
		}
		_html_dom_die("replaceChild old node is not a child");
	}

	method removeChild ( childNode ) {
		let kept := [];
		let removed := null;
		for ( let child in _child_nodes ) {
			if ( child ≡ childNode and removed ≡ null ) {
				removed := child;
				child{_parent_node} := null;
			}
			else {
				kept.push(child);
			}
		}
		_html_dom_die("removeChild node is not a child") if removed ≡ null;
		_child_nodes := kept;
		return removed;
	}

	method remove () {
		return self if _parent_node ≡ null;
		_parent_node.removeChild(self);
		return self;
	}

	method textContent () {
		if ( _node_kind eq "text" or _node_kind eq "comment" ) {
			return _node_value;
		}
		return "" if _node_kind eq "doctype";

		let out := "";
		for ( let child in _child_nodes ) {
			out _= child.textContent();
		}
		return out;
	}

	method setTextContent ( value ) {
		if ( _node_kind eq "text" or _node_kind eq "comment" ) {
			return self.setNodeValue(value);
		}
		_html_dom_die("setTextContent is not supported for doctypes")
			if _node_kind eq "doctype";
		if ( self.nodeKind() eq "document" and _html_dom_string(value) ne "" ) {
			_html_dom_die("cannot set non-empty document textContent");
		}
		for ( let child in _child_nodes ) {
			child{_parent_node} := null;
		}
		_child_nodes := [];
		_html_dom_die("setTextContent on detached container needs owner document")
			if _html_dom_string(value) ne "" and self.ownerDocument() ≡ null;
		self.appendChild(self.ownerDocument().createTextNode(value))
			if _html_dom_string(value) ne "";
		return self;
	}

	method normalize () {
		let kept := [];
		let previous_text := null;
		for ( let child in _child_nodes ) {
			child.normalize();
			if ( child.nodeKind() eq "text" ) {
				if ( child.data() eq "" ) {
					child{_parent_node} := null;
					next;
				}
				if ( previous_text ≢ null ) {
					previous_text.setData(previous_text.data() _ child.data());
					child{_parent_node} := null;
					next;
				}
				previous_text := child;
			}
			else {
				previous_text := null;
			}
			kept.push(child);
		}
		_child_nodes := kept;
		return self;
	}

	method cloneNode ( deep := false ) {
		let clone := new HTMLNode(
			_node_kind: _node_kind,
			_node_name: _node_name,
			_node_value: _node_value,
			_owner_document: self.ownerDocument(),
		);
		return self._clone_children_into( clone, deep );
	}

	method _clone_children_into ( clone, deep ) {
		clone._set_owner_document_recursive(self.ownerDocument());
		if ( deep ) {
			for ( let child in _child_nodes ) {
				clone.appendChild(child.cloneNode(true));
			}
		}
		return clone;
	}

	method isSameNode ( other ) {
		return self ≡ other;
	}

	method isEqualNode ( other ) {
		return false if other ≡ null;
		return false if self.nodeType() ne other.nodeType();
		return false if self.nodeName() ne other.nodeName();
		return false if self.nodeValue() ne other.nodeValue();

		if ( self.nodeKind() eq "doctype" ) {
			return false if self.publicId() ne other.publicId();
			return false if self.systemId() ne other.systemId();
		}
		if ( self.nodeKind() eq "element" ) {
			return false if self.namespaceURI() ne other.namespaceURI();
			return false if self.localName() ne other.localName();
			let names := self.attributeNames();
			let other_names := other.attributeNames();
			return false if names.length() != other_names.length();
			let records := self.attributeRecords();
			let other_records := other.attributeRecords();
			let i := 0;
			while ( i < records.length() ) {
				return false if records[i]{qualifiedName} ne other_records[i]{qualifiedName};
				return false if records[i]{localName} ne other_records[i]{localName};
				return false if records[i]{namespaceURI} ne other_records[i]{namespaceURI};
				return false if records[i]{prefix} ne other_records[i]{prefix};
				return false if records[i]{value} ne other_records[i]{value};
				i++;
			}
		}
		return false if _child_nodes.length() != other.childNodes().length();
		let other_children := other.childNodes();
		let i := 0;
		while ( i < _child_nodes.length() ) {
			return false unless _child_nodes[i].isEqualNode(other_children[i]);
			i++;
		}
		return true;
	}

	method contains ( other ) {
		return false if other ≡ null;
		return true if self ≡ other;
		for ( let child in _child_nodes ) {
			return true if child.contains(other);
		}
		return false;
	}

	method _descendant_elements () {
		let out := [];
		self._collect_descendant_elements(out);
		return out;
	}

	method _collect_descendant_elements ( Array out ) {
		for ( let child in _child_nodes ) {
			if ( child.nodeKind() eq "element" ) {
				out.push(child);
			}
			child._collect_descendant_elements(out);
		}
	}

	method _matches_selector ( String selector ) {
		return false unless self.nodeKind() eq "element";
		if ( selector eq "*" ) {
			return true;
		}
		if ( selector ~ /^#[A-Za-z_][A-Za-z0-9_-]*$/ ) {
			return self.id() eq substr( selector, 1 );
		}
		if ( selector ~ /^\.[A-Za-z_][A-Za-z0-9_-]*$/ ) {
			let wanted := substr( selector, 1 );
			for ( let token in split( self.getAttribute("class") ?: "", " " ) ) {
				return true if token eq wanted;
			}
			return false;
		}
		if ( selector ~ /^[A-Za-z][A-Za-z0-9_-]*$/ ) {
			return lc(self.tagName()) eq lc(selector);
		}
		_html_dom_die("unsupported selector: " _ selector);
	}

	method querySelectorAll ( selector ) {
		let normalized := trim(_html_dom_string(selector));
		_html_dom_die("unsupported selector: " _ _html_dom_string(selector))
			if normalized eq "";
		let out := [];
		for ( let node in self._descendant_elements() ) {
			out.push(node) if node._matches_selector(normalized);
		}
		return out;
	}

	method querySelector ( selector ) {
		let nodes := self.querySelectorAll(selector);
		return null if nodes.length() == 0;
		return nodes[0];
	}

	method findnodes ( path ) {
		_html_dom_die(
			"findnodes is not implemented; use querySelectorAll "
				_ "or getElementsByTagName",
		);
	}

	method findvalue ( path ) {
		_html_dom_die(
			"findvalue is not implemented; use querySelector "
				_ "or textContent",
		);
	}

	method visitEach ( callback ) {
		callback(self);
		for ( let child in _child_nodes ) {
			child.visitEach(callback);
		}
		return self;
	}

	method findFirst ( callback ) {
		for ( let child in _child_nodes ) {
			return child if callback(child);
			let found := child.findFirst(callback);
			return found if found ≢ null;
		}
		return null;
	}

	method _serialize_attrs () {
		return "";
	}

	method toHTML ( pretty := false ) {
		if ( self.nodeKind() eq "document" ) {
			let parts := [];
			for ( let child in _child_nodes ) {
				parts.push(child.toHTML(false));
			}
			return join( "", parts );
		}
		if ( self.nodeKind() eq "fragment" ) {
			let parts := [];
			for ( let child in _child_nodes ) {
				parts.push(child.toHTML(false));
			}
			return join( "", parts );
		}
		if ( self.nodeKind() eq "element" ) {
			let tag := self.tagName();
			let out := "<" _ tag _ self._serialize_attrs() _ ">";
			return out if self.namespaceURI() eq HTML_NAMESPACE_URI
				and _html_dom_is_void_element(tag);
			for ( let child in _child_nodes ) {
				out _= child.toHTML(false);
			}
			return out _ "</" _ tag _ ">";
		}
		if ( self.nodeKind() eq "text" ) {
			return _html_dom_escape_text(self.data());
		}
		if ( self.nodeKind() eq "comment" ) {
			return "<!--" _ self.data() _ "-->";
		}
		if ( self.nodeKind() eq "doctype" ) {
			let out := "<!DOCTYPE " _ self.name();
			if ( self.publicId() ne "" ) {
				out _= " PUBLIC \"" _ _html_dom_escape_attr(self.publicId()) _ "\"";
				out _= " \"" _ _html_dom_escape_attr(self.systemId()) _ "\""
					if self.systemId() ne "";
			}
			else if ( self.systemId() ne "" ) {
				out _= " SYSTEM \"" _ _html_dom_escape_attr(self.systemId()) _ "\"";
			}
			return out _ ">";
		}
		return "";
	}

	method toXML ( pretty := false ) {
		return self.toHTML(pretty);
	}

	method to_String () {
		return self.toHTML(false);
	}
}

class HTMLElement extends HTMLNode {
	let String _tag_name := "";
	let Dict _attributes := {};
	let Array _attribute_records := [];
	let _namespace_uri := HTML_NAMESPACE_URI;
	let _prefix := null;

	method __build__ () {
		if ( _namespace_uri ≡ null or _namespace_uri eq HTML_NAMESPACE_URI ) {
			_namespace_uri := HTML_NAMESPACE_URI;
			_tag_name := _html_dom_name(_tag_name);
		}
		else {
			let parts := _html_dom_qname_parts(_tag_name);
			_prefix := parts{prefix} if _prefix ≡ null;
			_tag_name := parts{localName};
		}
		_attributes := {} if _attributes ≡ null;
		_attribute_records := [] if _attribute_records ≡ null;
		self._sync_attribute_index();
		self._configure_node( "element", _tag_name );
		self._init_node();
	}

	method tagName () {
		return _tag_name;
	}

	method localName () {
		return _tag_name;
	}

	method namespaceURI () {
		return _namespace_uri;
	}

	method _sync_attribute_index () {
		_attributes := {};
		for ( let record in _attribute_records ) {
			_attributes{(record{qualifiedName})} := record{value};
		}
		return self;
	}

	method _find_attr_index_by_name ( String name ) {
		let wanted := _namespace_uri eq HTML_NAMESPACE_URI
			? _html_dom_name(name)
			: _html_dom_string(name);
		let i := 0;
		while ( i < _attribute_records.length() ) {
			return i if _attribute_records[i]{qualifiedName} eq wanted;
			return i if _namespace_uri eq HTML_NAMESPACE_URI
				and lc(_attribute_records[i]{qualifiedName}) eq wanted;
			i++;
		}
		return -1;
	}

	method _find_attr_index_ns ( namespaceURI, String localName ) {
		let ns := _html_dom_normal_namespace(namespaceURI);
		let local := _html_dom_string(localName);
		let i := 0;
		while ( i < _attribute_records.length() ) {
			return i if _attribute_records[i]{namespaceURI} eq ns
				and _attribute_records[i]{localName} eq local;
			i++;
		}
		return -1;
	}

	method id () {
		return self.getAttribute("id");
	}

	method setId ( value ) {
		return self.setAttribute( "id", value );
	}

	method getAttribute ( name ) {
		let i := self._find_attr_index_by_name(name);
		return null if i < 0;
		return _attribute_records[i]{value};
	}

	method setAttribute ( name, value ) {
		let record := _html_dom_attribute_record(
			null,
			name,
			value,
			_namespace_uri eq HTML_NAMESPACE_URI,
		);
		let i := self._find_attr_index_by_name(record{qualifiedName});
		if ( i >= 0 ) {
			_attribute_records[i] := record;
		}
		else {
			_attribute_records.push(record);
		}
		self._sync_attribute_index();
		return self;
	}

	method hasAttribute ( name ) {
		return self._find_attr_index_by_name(name) >= 0;
	}

	method removeAttribute ( name ) {
		let i := self._find_attr_index_by_name(name);
		if ( i >= 0 ) {
			let kept := [];
			let j := 0;
			while ( j < _attribute_records.length() ) {
				kept.push(_attribute_records[j]) unless j == i;
				j++;
			}
			_attribute_records := kept;
			self._sync_attribute_index();
		}
		return self;
	}

	method getAttributeNS ( namespaceURI, String localName ) {
		let i := self._find_attr_index_ns( namespaceURI, localName );
		return null if i < 0;
		return _attribute_records[i]{value};
	}

	method setAttributeNS ( namespaceURI, qualifiedName, value ) {
		let record := _html_dom_attribute_record(
			namespaceURI,
			qualifiedName,
			value,
			false,
		);
		let i := self._find_attr_index_ns(
			record{namespaceURI},
			record{localName},
		);
		if ( i >= 0 ) {
			_attribute_records[i] := record;
		}
		else {
			_attribute_records.push(record);
		}
		self._sync_attribute_index();
		return self;
	}

	method hasAttributeNS ( namespaceURI, String localName ) {
		return self._find_attr_index_ns( namespaceURI, localName ) >= 0;
	}

	method removeAttributeNS ( namespaceURI, String localName ) {
		let i := self._find_attr_index_ns( namespaceURI, localName );
		if ( i >= 0 ) {
			let kept := [];
			let j := 0;
			while ( j < _attribute_records.length() ) {
				kept.push(_attribute_records[j]) unless j == i;
				j++;
			}
			_attribute_records := kept;
			self._sync_attribute_index();
		}
		return self;
	}

	method attributeNames () {
		let out := [];
		for ( let record in _attribute_records ) {
			out.push(record{qualifiedName});
		}
		return out.sort( fn ( a, b ) -> a cmp b );
	}

	method attributes () {
		let out := {};
		for ( let key in self.attributeNames() ) {
			out{(key)} := _attributes{(key)};
		}
		return out;
	}

	method attributeRecords () {
		let out := [];
		for ( let name in self.attributeNames() ) {
			for ( let record in _attribute_records ) {
				out.push(_html_dom_copy_attr_record(record))
					if record{qualifiedName} eq name;
			}
		}
		return out;
	}

	method getElementsByTagName ( name ) {
		let wanted := lc(_html_dom_string(name));
		let out := [];
		for ( let node in self._descendant_elements() ) {
			out.push(node) if wanted eq "*" or lc(node.tagName()) eq wanted;
		}
		return out;
	}

	method _serialize_attrs () {
		let out := "";
		for ( let record in self.attributeRecords() ) {
			out _= " " _ record{qualifiedName} _ "=\""
				_ _html_dom_escape_attr(record{value})
				_ "\"";
		}
		return out;
	}

	method cloneNode ( deep := false ) {
		let clone := new HTMLElement(
			_tag_name: self.tagName(),
			_namespace_uri: self.namespaceURI(),
			_prefix: _prefix,
			_owner_document: self.ownerDocument(),
		);
		for ( let record in self.attributeRecords() ) {
			if ( record{namespaceURI} ≡ null ) {
				clone.setAttribute( record{qualifiedName}, record{value} );
			}
			else {
				clone.setAttributeNS(
					record{namespaceURI},
					record{qualifiedName},
					record{value},
				);
			}
		}
		return self._clone_children_into( clone, deep );
	}
}

class HTMLDocumentFragment extends HTMLNode {
	method __build__ () {
		self._configure_node( "fragment", "#document-fragment" );
		self._init_node();
	}

	method getElementsByTagName ( name ) {
		let wanted := lc(_html_dom_string(name));
		let out := [];
		for ( let node in self._descendant_elements() ) {
			out.push(node) if wanted eq "*" or lc(node.tagName()) eq wanted;
		}
		return out;
	}

	method cloneNode ( deep := false ) {
		let clone := new HTMLDocumentFragment(
			_owner_document: self.ownerDocument(),
		);
		return self._clone_children_into( clone, deep );
	}
}

class HTMLTemplateElement extends HTMLElement {
	let String _tag_name := "template";
	let Dict _attributes := {};
	let Array _attribute_records := [];
	let _namespace_uri := HTML_NAMESPACE_URI;
	let _prefix := null;
	let _content := null;

	method __build__ () {
		_tag_name := "template";
		_attributes := {} if _attributes ≡ null;
		_attribute_records := [] if _attribute_records ≡ null;
		self._sync_attribute_index();
		self._configure_node( "element", _tag_name );
		self._init_node();
		_content := new HTMLDocumentFragment(
			_owner_document: self.ownerDocument(),
		) if _content ≡ null;
	}

	method content () {
		return _content;
	}

	method tagName () {
		return _tag_name;
	}

	method localName () {
		return _tag_name;
	}

	method namespaceURI () {
		return _namespace_uri;
	}

	method id () {
		return self.getAttribute("id");
	}

	method setId ( value ) {
		return self.setAttribute( "id", value );
	}

	method getAttribute ( name ) {
		let i := self._find_attr_index_by_name(name);
		return null if i < 0;
		return _attribute_records[i]{value};
	}

	method setAttribute ( name, value ) {
		let record := _html_dom_attribute_record( null, name, value, true );
		let i := self._find_attr_index_by_name(record{qualifiedName});
		if ( i >= 0 ) {
			_attribute_records[i] := record;
		}
		else {
			_attribute_records.push(record);
		}
		self._sync_attribute_index();
		return self;
	}

	method hasAttribute ( name ) {
		return self._find_attr_index_by_name(name) >= 0;
	}

	method removeAttribute ( name ) {
		let i := self._find_attr_index_by_name(name);
		if ( i >= 0 ) {
			let kept := [];
			let j := 0;
			while ( j < _attribute_records.length() ) {
				kept.push(_attribute_records[j]) unless j == i;
				j++;
			}
			_attribute_records := kept;
			self._sync_attribute_index();
		}
		return self;
	}

	method attributeNames () {
		let out := [];
		for ( let record in _attribute_records ) {
			out.push(record{qualifiedName});
		}
		return out.sort( fn ( a, b ) -> a cmp b );
	}

	method attributes () {
		let out := {};
		for ( let key in self.attributeNames() ) {
			out{(key)} := _attributes{(key)};
		}
		return out;
	}

	method attributeRecords () {
		let out := [];
		for ( let name in self.attributeNames() ) {
			for ( let record in _attribute_records ) {
				out.push(_html_dom_copy_attr_record(record))
					if record{qualifiedName} eq name;
			}
		}
		return out;
	}

	method getElementsByTagName ( name ) {
		let wanted := lc(_html_dom_string(name));
		let out := [];
		for ( let node in self._descendant_elements() ) {
			out.push(node) if wanted eq "*" or lc(node.tagName()) eq wanted;
		}
		return out;
	}

	method _serialize_attrs () {
		let out := "";
		for ( let record in self.attributeRecords() ) {
			out _= " " _ record{qualifiedName} _ "=\""
				_ _html_dom_escape_attr(record{value})
				_ "\"";
		}
		return out;
	}

	method _collect_descendant_elements ( Array out ) {
		for ( let child in self.childNodes() ) {
			if ( child.nodeKind() eq "element" ) {
				out.push(child);
			}
			child._collect_descendant_elements(out);
		}
		_content._collect_descendant_elements(out) if _content ≢ null;
		return self;
	}

	method textContent () {
		let out := "";
		for ( let child in _content.childNodes() ) {
			out _= child.textContent();
		}
		return out;
	}

	method toHTML ( pretty := false ) {
		let out := "<template" _ self._serialize_attrs() _ ">";
		for ( let child in _content.childNodes() ) {
			out _= child.toHTML(false);
		}
		return out _ "</template>";
	}

	method isEqualNode ( other ) {
		return false if other ≡ null;
		return false unless other instanceof HTMLTemplateElement;
		return false if self.nodeType() ne other.nodeType();
		return false if self.nodeName() ne other.nodeName();
		return false if self.namespaceURI() ne other.namespaceURI();

		let records := self.attributeRecords();
		let other_records := other.attributeRecords();
		return false if records.length() != other_records.length();
		let r := 0;
		while ( r < records.length() ) {
			return false if records[r]{qualifiedName} ne other_records[r]{qualifiedName};
			return false if records[r]{localName} ne other_records[r]{localName};
			return false if records[r]{namespaceURI} ne other_records[r]{namespaceURI};
			return false if records[r]{prefix} ne other_records[r]{prefix};
			return false if records[r]{value} ne other_records[r]{value};
			r++;
		}

		let children := _content.childNodes();
		let other_children := other.content().childNodes();
		return false if children.length() != other_children.length();
		let i := 0;
		while ( i < children.length() ) {
			return false unless children[i].isEqualNode(other_children[i]);
			i++;
		}
		return true;
	}

	method cloneNode ( deep := false ) {
		let clone := new HTMLTemplateElement(
			_owner_document: self.ownerDocument(),
		);
		for ( let record in self.attributeRecords() ) {
			if ( record{namespaceURI} ≡ null ) {
				clone.setAttribute( record{qualifiedName}, record{value} );
			}
			else {
				clone.setAttributeNS(
					record{namespaceURI},
					record{qualifiedName},
					record{value},
				);
			}
		}
		if ( deep ) {
			for ( let child in _content.childNodes() ) {
				clone.content().appendChild(child.cloneNode(true));
			}
		}
		return clone;
	}
}

class HTMLText extends HTMLNode {
	let _data := null;

	method __build__ () {
		self._use_data_alias(_data);
		self._configure_node( "text", "#text" );
		self._normalise_node_value();
		self._init_node();
	}

	method data () {
		return self.nodeValue();
	}

	method setData ( value ) {
		return self.setNodeValue(value);
	}

	method cloneNode ( deep := false ) {
		return new HTMLText(
			_node_value: self.data(),
			_owner_document: self.ownerDocument(),
		);
	}
}

class HTMLComment extends HTMLNode {
	let _data := null;

	method __build__ () {
		self._use_data_alias(_data);
		self._configure_node( "comment", "#comment" );
		self._normalise_node_value();
		_html_dom_die("comment data must not contain -->")
			if self.nodeValue() ~ /-->/;
		self._init_node();
	}

	method data () {
		return self.nodeValue();
	}

	method setData ( value ) {
		let data := _html_dom_string(value);
		_html_dom_die("comment data must not contain -->") if data ~ /-->/;
		return self.setNodeValue(data);
	}

	method cloneNode ( deep := false ) {
		return new HTMLComment(
			_node_value: self.data(),
			_owner_document: self.ownerDocument(),
		);
	}
}

class HTMLDoctype extends HTMLNode {
	let String _name := "html";
	let String _public_id := "";
	let String _system_id := "";

	method __build__ () {
		_name := _html_dom_doctype_name(_name);
		_public_id := _html_dom_string(_public_id);
		_system_id := _html_dom_string(_system_id);
		self._configure_node( "doctype", _name );
		self._init_node();
	}

	method name () {
		return _name;
	}

	method publicId () {
		return _public_id;
	}

	method systemId () {
		return _system_id;
	}

	method localName () {
		return _name;
	}

	method cloneNode ( deep := false ) {
		return new HTMLDoctype(
			_name: self.name(),
			_public_id: self.publicId(),
			_system_id: self.systemId(),
			_owner_document: self.ownerDocument(),
		);
	}
}

class HTMLDocument extends HTMLNode {
	method __build__ () {
		self._configure_node( "document", "#document" );
		self._init_node();
		self._set_owner_document_recursive(self);
	}

	method documentElement () {
		for ( let child in self.childNodes() ) {
			return child if child.nodeKind() eq "element";
		}
		return null;
	}

	method createElement ( name ) {
		return new HTMLTemplateElement(
			_owner_document: self,
		) if _html_dom_name(name) eq "template";
		return new HTMLElement(
			_tag_name: _html_dom_name(name),
			_namespace_uri: HTML_NAMESPACE_URI,
			_owner_document: self,
		);
	}

	method createElementNS ( namespaceURI, qualifiedName ) {
		let ns := _html_dom_normal_namespace(namespaceURI);
		ns := HTML_NAMESPACE_URI if ns ≡ null;
		let parts := _html_dom_qname_parts(qualifiedName);
		if ( ns eq HTML_NAMESPACE_URI ) {
			return self.createElement(parts{localName});
		}
		return new HTMLElement(
			_tag_name: parts{localName},
			_namespace_uri: ns,
			_prefix: parts{prefix},
			_owner_document: self,
		);
	}

	method createTextNode ( text ) {
		return new HTMLText(
			_node_value: _html_dom_string(text),
			_owner_document: self,
		);
	}

	method createComment ( text ) {
		let data := _html_dom_string(text);
		_html_dom_die("comment data must not contain -->") if data ~ /-->/;
		return new HTMLComment( _node_value: data, _owner_document: self );
	}

	method createDoctype ( name := "html", publicId := "", systemId := "" ) {
		return new HTMLDoctype(
			_name: _html_dom_doctype_name(name),
			_public_id: _html_dom_string(publicId),
			_system_id: _html_dom_string(systemId),
			_owner_document: self,
		);
	}

	method createCDATASection ( text ) {
		return self.createTextNode(text);
	}

	method getElementsByTagName ( name ) {
		let wanted := lc(_html_dom_string(name));
		let out := [];
		for ( let node in self._descendant_elements() ) {
			out.push(node) if wanted eq "*" or lc(node.tagName()) eq wanted;
		}
		return out;
	}

	method getElementById ( id ) {
		for ( let node in self._descendant_elements() ) {
			return node if node.id() eq _html_dom_string(id);
		}
		return null;
	}

	method cloneNode ( deep := false ) {
		let clone := new HTMLDocument();
		return self._clone_children_into( clone, deep );
	}
}

class DOMNode extends HTMLNode {}
class DOMDocument extends HTMLDocument {}
class DOMElement extends HTMLElement {}
class DOMText extends HTMLText {}
class DOMComment extends HTMLComment {}
class DOMDoctype extends HTMLDoctype {}