document.go

package helium

import (
	"bytes"
	"errors"
	"fmt"
	"strings"
	"unsafe"

	"github.com/lestrrat-go/helium/enum"
	"github.com/lestrrat-go/helium/internal/lexicon"
	"github.com/lestrrat-go/helium/internal/pool"
)

// DocumentStandaloneType records the state of a document's standalone
// declaration, mirroring libxml2's xmlDoc.standalone. It is one of the
// Standalone* constants; any other value is out of the defined space and is
// treated the same as StandaloneImplicitNo — serialization emits no standalone
// attribute for it and DTD validation treats it as not-standalone. The full
// value space:
//
//   - StandaloneExplicitYes: the XML declaration carried standalone="yes".
//   - StandaloneExplicitNo:  the XML declaration carried standalone="no".
//   - StandaloneImplicitNo:  no explicit standalone="yes"/"no" was seen. This is
//     the parser's default, and the value a parsed document carries both when the
//     XML declaration is absent entirely and when it is present without a
//     standalone pseudo-attribute. It is also the value to pass to NewDocument
//     for an ordinary API-built document. Serialization emits no standalone
//     attribute.
//   - StandaloneNoXMLDecl:   a libxml2-compatible caller-selected sentinel for a
//     constructed document with no XML declaration (used by NewHTMLDocument and
//     the xslt3 serializer). The parser never produces it; serialization treats
//     it as not-standalone and emits no standalone attribute.
//   - StandaloneInvalidValue: an internal parser sentinel for a standalone
//     value that has not been resolved yet; not meaningful on a finished
//     document.
type DocumentStandaloneType int

const (
	StandaloneInvalidValue DocumentStandaloneType = -99
	StandaloneExplicitYes  DocumentStandaloneType = 1
	StandaloneExplicitNo   DocumentStandaloneType = 0
	StandaloneNoXMLDecl    DocumentStandaloneType = -1
	StandaloneImplicitNo   DocumentStandaloneType = -2
)

// DocProperties is a bitmask of document properties, mirroring
// libxml2's xmlDocProperties. Properties are set by the parser
// or by user code to record how the document was produced and
// what validations it passed.
type DocProperties int

const (
	DocWellFormed DocProperties = 1 << iota // document is XML well-formed
	DocNSValid                              // document is namespace-valid
	DocOld10                                // parsed with XML 1.0 (4th edition or earlier)
	DocDTDValid                             // DTD validation was successful
	DocXInclude                             // XInclude substitution was done
	DocUserBuilt                            // built via API, not by parsing
	DocInternal                             // built for internal processing
	DocHTML                                 // parsed or built as HTML
)

// Document represents an XML document (libxml2: xmlDoc).
type Document struct {
	docnode
	version    string
	encoding   string
	standalone DocumentStandaloneType
	url        string // document URI for base URI resolution (mirrors libxml2's xmlDoc.URL)
	properties DocProperties

	intSubset *DTD
	extSubset *DTD
	ids       map[string]*Element
	idsSkip   bool

	// standaloneNormAttrs records specified attributes whose value was changed by
	// tokenized-type normalization driven by an external-subset ATTLIST
	// declaration. Populated by the parser (which alone holds the pre-normalization
	// value) and consulted by DTD validation for the VC: Standalone Document
	// Declaration in a standalone="yes" document. See valid.go.
	standaloneNormAttrs []standaloneNormAttr

	// Slab allocators for high-frequency node types.
	// These reduce per-node heap allocation overhead by allocating
	// nodes in chunks and handing them out one at a time.
	// Pooled chunks are obtained from global pools and returned on Free().
	// A document the parser did not build takes small heap chunks first (see
	// slabGrowthSizes), so a small built tree does not hold a full pooled chunk.
	elemSlab []Element
	textSlab []Text
	nsSlab   []Namespace
	attrSlab []Attribute

	// Track allocated chunks for pool return.
	elemChunks []*[slabSize]Element
	textChunks []*[slabSize]Text
	nsChunks   []*[slabSize]Namespace
	attrChunks []*[slabSize]Attribute

	// Slab allocator for parsed text content bytes.
	textContentSlab   []byte
	textContentChunks []*[textContentSlabSize]byte

	// slabEscaped records that at least one slab-backed node owned by this
	// document was linked into another document (an XInclude/XSLT-style
	// cross-document move). Once set, Free must NOT return this document's chunks
	// to the pool: a moved node still points into one of them, and recycling it
	// would let a later parse overwrite the live node. Set by the tree-insertion
	// paths (node.go noteCrossDocumentEscape).
	slabEscaped bool

	// pooledSlabs makes every slab chunk come from the pools from the first
	// node on. The parser sets it on the document it builds: a parsed document
	// is commonly released with Free and its chunks reused by the next parse,
	// which the small heap chunks of the growth schedule would defeat.
	pooledSlabs bool

	// Number of small heap chunks each slab allocator has taken from its
	// growth schedule (slabGrowthSizes, textContentGrowthSizes). Once a counter
	// reaches the end of its schedule, that allocator draws pooled chunks.
	elemGrowth        uint8
	textGrowth        uint8
	nsGrowth          uint8
	attrGrowth        uint8
	textContentGrowth uint8

	// offChainChildClaim records that a node has been given this document as its
	// parent WITHOUT being linked into the document's child list. The DTD-subset
	// copy paths do it when copying an external subset: the copied subset
	// claims the destination document and is then reachable only through
	// ExtSubset. An append through such a subset records its own result as the
	// document's lastChild, which moves that record off the child list, so the
	// O(1) append-point resolution must stop trusting that record.
	//
	// The record is per-PARENT, and this document IS the parent that was handed
	// the claimant: it declines only for appends onto the document node itself,
	// never for the elements the document owns, whose own lastChild records the
	// claimant says nothing about. (CreateInternalSubset also gives a DTD this
	// document as its parent, but it splices that DTD into the child list, so it
	// creates no claim.) Set by copy_dtd.go; read through
	// node.go holdsOffChainChildClaim by tailJumpTarget and resolveOwnedTail.
	offChainChildClaim bool
}

// NewDefaultDocument creates a minimal user-built document with version "1.0",
// no encoding, and implicit-no standalone (libxml2: xmlNewDoc).
func NewDefaultDocument() *Document {
	doc := NewDocument("1.0", "", StandaloneImplicitNo)
	doc.properties |= DocUserBuilt
	return doc
}

// NewHTMLDocument creates a new HTML document (HTMLDocumentNode type). The
// HTML parser builds its documents through it, so like a document the XML
// parser builds, it draws its slab chunks from the pools from the first node
// on.
func NewHTMLDocument() *Document {
	doc := &Document{
		standalone:  StandaloneNoXMLDecl,
		properties:  DocHTML,
		pooledSlabs: true,
	}
	doc.etype = HTMLDocumentNode
	doc.name = "(document)"
	return doc
}

// NewDocument allocates an empty XML Document with the given XML
// declaration version, character encoding, and standalone status. The
// standalone argument is one of the Standalone* constants (see
// DocumentStandaloneType for the full value space); pass StandaloneImplicitNo
// for an ordinary document with no explicit standalone declaration. The
// returned document owns no children yet; use CreateElement and the other
// Create* methods to build a tree, then attach the root via AddChild.
func NewDocument(version, encoding string, standalone DocumentStandaloneType) *Document {
	doc := &Document{
		encoding:   encoding,
		standalone: standalone,
		version:    version,
	}

	doc.etype = DocumentNode
	doc.name = "(document)"
	return doc
}

// Free returns pooled slab chunks for reuse by future parse calls.
// This is optional — if not called, GC handles cleanup normally.
// Calling Free on a document that is still in use causes undefined behavior.
//
// If any of this document's slab-backed nodes was moved into another document
// (via AddChild/AddSibling/Replace), Free does NOT recycle its chunks: a moved
// node still references one of them, and Free zeroes every chunk it returns
// to the pool, so recycling it would wipe the live node and let a later parse
// overwrite it. In that case Free is a no-op and GC
// reclaims the chunks once they are no longer referenced.
func (d *Document) Free() {
	if d.slabEscaped {
		return
	}
	recycleNodeChunks(elemChunkPool, d.elemChunks, len(d.elemSlab))
	recycleNodeChunks(textChunkPool, d.textChunks, len(d.textSlab))
	recycleNodeChunks(nsChunkPool, d.nsChunks, len(d.nsSlab))
	recycleNodeChunks(attrChunkPool, d.attrChunks, len(d.attrSlab))
	for _, c := range d.textContentChunks {
		textContentChunkPool.Put(c)
	}
	d.elemChunks = nil
	d.textChunks = nil
	d.nsChunks = nil
	d.attrChunks = nil
	d.textContentChunks = nil
	d.elemSlab = nil
	d.textSlab = nil
	d.nsSlab = nil
	d.attrSlab = nil
	d.textContentSlab = nil
}

// Content returns the document's content: the content of its Element, Text,
// CDATA and EntityRef children, with every entity reference expanded and
// comments and PIs left out, the same text XPath string(/) reads. The DTD is
// not document content and adds nothing, so neither does any entity
// declaration it holds. libxml2 2.9's xmlNodeGetContent read a document the
// same way, adding only its element, text and CDATA children. A document with
// no such content returns nil.
func (d *Document) Content() []byte {
	if d.firstChild == nil {
		return nil
	}
	var b bytes.Buffer
	appendDocumentContent(&b, &d.docnode)
	return b.Bytes()
}

// AddChild appends cur as the last child of the document, detaching it from any
// previous parent first. It returns an error if cur is nil or if the insertion
// would create a cycle.
func (d *Document) AddChild(cur Node) error {
	return addChild(d, cur)
}

// AppendText appends b as a Text child of the document, merging into a trailing
// Text node when possible.
func (d *Document) AppendText(b []byte) error {
	return appendText(d, b)
}

// AddSibling returns an error. It exists to satisfy the Node interface.
func (d *Document) AddSibling(_ Node) error {
	return errors.New("can't add sibling to a document")
}

// SetTreeDoc sets doc as this node's owning document, propagating to
// descendants only when this node's owner changes. It is a no-op when this node
// already owns doc.
func (d *Document) SetTreeDoc(doc *Document) {
	setTreeDoc(d, doc)
}

// Encoding returns the document's recorded character encoding, or "utf8" if none
// is recorded. Use RawEncoding to obtain the recorded value without that
// default.
func (d *Document) Encoding() string {
	// In order to differentiate between a document with explicit
	// encoding in the XML declaration and one without, the XML dump
	// routine must check for d.encoding == "", and not Encoding()
	if enc := d.encoding; enc != "" {
		return d.encoding
	}
	return "utf8"
}

// SetEncoding sets the document's recorded encoding; an empty string clears it.
func (d *Document) SetEncoding(enc string) {
	d.encoding = enc
}

// RawEncoding returns the document's encoding exactly as recorded, WITHOUT the
// "utf8" default that Encoding() synthesizes for documents whose XML
// declaration omitted an encoding. An empty result means the source had no
// encoding declaration. This is the value the XML serializer consults (it emits
// encoding="..." only when the raw encoding is non-empty), so a faithful copy
// of a document — e.g. an xsl:strip-space copy — must propagate this rather
// than Encoding(), which would synthesize a spurious encoding="utf8".
func (d *Document) RawEncoding() string {
	return d.encoding
}

// Standalone returns the value of the document's standalone declaration.
func (d *Document) Standalone() DocumentStandaloneType {
	return d.standalone
}

// SkipIDs reports whether ID attribute interning was skipped when this
// document was produced (mirrors the parser's SkipIDs option). When true,
// GetElementByID and fn:id always return no match without an O(n) tree walk.
func (d *Document) SkipIDs() bool {
	return d.idsSkip
}

// SetSkipIDs sets the document's ID-skip state. This is used when producing a
// derived document (e.g. an xsl:strip-space copy) that must mirror the source's
// ID semantics.
//
// The ID-skip state is authoritative: while it is true, GetElementByID (and
// therefore fn:id) resolves NO ids and returns nil — even if the document
// already has a populated ID table from a normal parse. Setting it back to
// false restores normal resolution against the existing table (or the lazy
// tree walk for API-built documents).
func (d *Document) SetSkipIDs(v bool) {
	d.idsSkip = v
}

// Version returns the document's recorded XML version (for example "1.0" or
// "1.1"), or an empty string if none is recorded.
func (d *Document) Version() string {
	return d.version
}

// SetVersion sets the document's XML declaration version (e.g. "1.0" or "1.1").
// Serialization consults this to decide whether XML 1.1 restricted control
// characters are emitted as character references instead of being rejected.
func (d *Document) SetVersion(v string) {
	d.version = v
}

// URL returns the document URI, used as the base for relative URI resolution.
// This mirrors libxml2's xmlDoc.URL field. An empty URL is valid for in-memory
// documents; callers that need a non-empty diagnostic label must provide their
// own fallback.
func (d *Document) URL() string {
	return d.url
}

// SetURL sets the document URI.
func (d *Document) SetURL(url string) {
	d.url = url
}

// Properties returns the document's property flags.
func (d *Document) Properties() DocProperties {
	return d.properties
}

// SetProperties replaces the document's property flags.
func (d *Document) SetProperties(p DocProperties) {
	d.properties = p
}

// HasProperty reports whether all bits in p are set.
func (d *Document) HasProperty(p DocProperties) bool {
	return d.properties&p == p
}

// IntSubset returns the document's internal DTD subset, or nil when none is
// present. The abbreviated name mirrors libxml2's xmlGetIntSubset and the
// intSubset document field. InternalSubset is the equivalent accessor that
// reports absence as an error instead of nil.
func (d *Document) IntSubset() *DTD {
	return d.intSubset
}

// RemoveInternalSubset detaches the document's internal-subset DTD (if any) from
// the child list and clears the association, so a subsequent
// CreateInternalSubset can install a fresh one in its place. It is a no-op when
// no internal subset is present.
func (d *Document) RemoveInternalSubset() {
	if d.intSubset == nil {
		return
	}
	unlinkNode(d.intSubset)
	d.intSubset = nil
}

// ExtSubset returns the document's external DTD subset, or nil when none is
// present. The abbreviated name mirrors libxml2's extSubset document field,
// matching the IntSubset accessor.
func (d *Document) ExtSubset() *DTD {
	return d.extSubset
}

// Replace returns ErrInvalidOperation. It exists to satisfy the Node interface.
func (d *Document) Replace(_ ...Node) error {
	return ErrInvalidOperation
}

// DocumentElement returns the root element of the document, or nil if none exists.
//
// The child scan goes through Children, so it applies the owned-boundary rule
// and a per-list seen guard: a corrupt document child list (a cyclic sibling
// pointer before the root) terminates the scan instead of hanging, which would
// otherwise stall DTD/XSD validation before the traversal cycle guards run.
func (d *Document) DocumentElement() *Element {
	for n := range Children(d) {
		if elem, ok := AsNode[*Element](n); ok {
			return elem
		}
	}
	return nil
}

// SetDocumentElement installs root as the document's root element, replacing an
// existing root element if one is present. It returns ErrNilNode if root is nil,
// and an error wrapping ErrInvalidOperation if root is not an *Element.
func (d *Document) SetDocumentElement(root MutableNode) error {
	if d == nil {
		return ErrNilNode
	}

	// Reject a nil or typed-nil operand BEFORE any root.Type() dereference so the
	// call returns ErrNilNode instead of panicking.
	if isNilNode(root) {
		return ErrNilNode
	}

	// The document element must be a concrete *Element. Accepting any node kind
	// here let a Text/Comment/DTD/NamespaceDecl node become the root, producing a
	// document that is not well formed. Checking the concrete type (not root.Type())
	// also rejects a non-element node that merely REPORTS ElementNode — e.g. an
	// XIncludeMarker constructed with ElementNode — which DocumentElement() would
	// never return, leaving the document element effectively nil.
	if _, ok := AsNode[*Element](root); !ok {
		return fmt.Errorf("%w: document element must be an element node, got %s", ErrInvalidOperation, root.Type())
	}

	// Do NOT link root to d here. Let AddChild/Replace perform the linking AFTER
	// their cycle/self preflight so a rejected insertion leaves the candidate and
	// the tree untouched. The scan goes through Children so a corrupt document
	// child list (a cyclic sibling pointer before the root) terminates instead of
	// hanging.
	var old Node
	for n := range Children(d) {
		if n.Type() == ElementNode {
			old = n
			break
		}
	}

	if old == nil {
		if err := d.AddChild(root); err != nil {
			return err
		}
	} else {
		if err := old.(MutableNode).Replace(root); err != nil { //nolint:forcetypeassert
			return err
		}
	}
	return nil
}

// CreateReference builds an entity-reference node and, when a matching entity
// is declared in the document, attaches its replacement content — mirroring
// libxml2's xmlNewReference. Like CreateCharRef (and libxml2's xmlNewCharRef)
// the node is an EntityRefNode that serializes as "&" + Name() + ";"; the only
// difference is the declared-entity lookup performed here.
func (d *Document) CreateReference(name string) (*EntityRef, error) {
	n, err := d.CreateCharRef(name)
	if err != nil {
		return nil, err
	}

	ent, ok := d.GetEntity(n.name)
	if ok {
		bindEntityReference(n, ent)
	}

	return n, nil
}

func bindEntityReference(ref *EntityRef, ent *Entity) {
	ref.content = []byte(ent.content)
	// Original code says:
	// The parent pointer in entity is a DTD pointer and thus is NOT
	// updated.  Not sure if this is 100% correct.
	setFirstChild(ref, ent)
	setLastChild(ref, ent)
}

// CreateAttribute builds an attribute node named name, with value parsed into
// its child node list, and optional namespace ns. A colon in name is rejected;
// supply a namespaced name through ns instead. name is not otherwise checked
// against the XML Name/NCName grammar. When d is non-nil the attribute is
// drawn from the document's slab allocator and records d as its owner
// document, so it must not outlive a call to Document.Free. A nil receiver
// allocates a standalone attribute with no owning document.
func (d *Document) CreateAttribute(name, value string, ns *Namespace) (attr *Attribute, err error) {
	if strings.ContainsRune(name, ':') {
		return nil, fmt.Errorf("attribute name %q contains a colon: use CreateAttribute with a local name and Namespace parameter", name)
	}
	var n Node
	if d != nil {
		attr = d.allocAttribute(name, ns)
	} else {
		attr = newAttribute(name, ns)
	}
	if value != "" {
		n, err = d.stringToNodeList(value)
		if err != nil {
			attr = nil
			return
		}

		setFirstChild(attr, n)
		for n != nil {
			n.baseDocNode().parent = attr
			x := n.NextSibling()
			if x == nil {
				setLastChild(attr, n)
			}
			n = x
		}
	}
	return attr, nil
}

// CreateNamespace builds a namespace node binding prefix to uri. An empty prefix
// denotes the default namespace.
func (d *Document) CreateNamespace(prefix, uri string) (*Namespace, error) {
	var ns *Namespace
	if d != nil {
		ns = d.allocNamespace()
	} else {
		ns = &Namespace{}
	}
	ns.prefix = prefix
	ns.href = uri
	ns.etype = NamespaceNode
	ns.context = d
	return ns, nil
}

func (d *Document) allocNamespace() *Namespace {
	if len(d.nsSlab) == 0 {
		d.nsSlab = growthChunk[Namespace](d.pooledSlabs, &d.nsGrowth)
	}
	if len(d.nsSlab) == 0 {
		chunk := nsChunkPool.Get()
		d.nsChunks = append(d.nsChunks, chunk)
		d.nsSlab = chunk[:]
	}
	ns := &d.nsSlab[0]
	d.nsSlab = d.nsSlab[1:]
	return ns
}

func (d *Document) allocAttribute(name string, ns *Namespace) *Attribute {
	if len(d.attrSlab) == 0 {
		d.attrSlab = growthChunk[Attribute](d.pooledSlabs, &d.attrGrowth)
	}
	if len(d.attrSlab) == 0 {
		chunk := attrChunkPool.Get()
		d.attrChunks = append(d.attrChunks, chunk)
		d.attrSlab = chunk[:]
	}
	attr := &d.attrSlab[0]
	d.attrSlab = d.attrSlab[1:]
	attr.etype = AttributeNode
	attr.name = name
	attr.ns = ns
	// Record the owning document, mirroring CreateElement/CreateText: a
	// slab-backed attribute must report its owner so a cross-document move can
	// mark the source document escaped (noteCrossDocumentEscape) and keep Free
	// from recycling the chunk out from under the moved attribute.
	attr.doc = d
	return attr
}

// createLiteralAttribute builds an attribute whose value holds no entity
// reference: a single Text child with value as its content, or no child for an
// empty value. The Text shares value's bytes (see below), which is safe for any
// string; the parser's values come from its valueArena.
func (d *Document) createLiteralAttribute(name, value string, ns *Namespace) *Attribute {
	var attr *Attribute
	if d != nil {
		attr = d.allocAttribute(name, ns)
	} else {
		attr = newAttribute(name, ns)
	}

	if value == "" {
		return attr
	}

	var t *Text
	if d != nil {
		t = d.allocText()
	} else {
		t = &Text{}
	}
	t.etype = TextNode
	t.name = textNodeName
	t.doc = d
	// The text reads value's bytes in place instead of copying them. Nothing
	// writes a Text's content bytes in place: the slice's capacity equals its
	// length, so AppendText moves the content to new memory before it appends,
	// and every reader (rawContent) treats the bytes as read-only.
	t.content = unsafe.Slice(unsafe.StringData(value), len(value))
	setFirstChild(attr, t)
	setLastChild(attr, t)
	t.parent = attr
	return attr
}

// CreatePI builds a processing-instruction node with the given target and data.
func (d *Document) CreatePI(target, data string) *ProcessingInstruction {
	pi := &ProcessingInstruction{
		target: target,
		data:   data,
	}
	pi.doc = d
	return pi
}

// CreateDTD builds a detached DTD node. It is not linked into the tree; use
// CreateInternalSubset to install an internal subset.
func (d *Document) CreateDTD() (*DTD, error) {
	dtd := newDTD()
	dtd.doc = d
	return dtd, nil
}

// InternalSubset returns the document's internal DTD subset, reporting absence
// as an error. IntSubset is the equivalent accessor that returns nil instead.
func (d *Document) InternalSubset() (*DTD, error) {
	// equiv: xmlGetIntSubset (tree.c)
	if d.intSubset == nil {
		return nil, ErrNoInternalSubset
	}
	return d.intSubset, nil
}

// CreateInternalSubset creates the document's internal DTD subset with the given
// root element name and external identifiers, and installs it on the document.
// It returns an error if the document already has an internal subset.
func (d *Document) CreateInternalSubset(name, externalID, systemID string) (*DTD, error) {
	// equiv: xmlCreateIntSubset (tree.c)
	if _, err := d.InternalSubset(); err == nil {
		return nil, errors.New("document " + d.name + " already has an internal subset")
	}

	cur, err := d.CreateDTD()
	if err != nil {
		return nil, err
	}

	cur.name = name
	cur.externalID = externalID
	cur.systemID = systemID

	if d == nil {
		return cur, nil
	}

	d.intSubset = cur
	cur.parent = d
	cur.doc = d

	// Insert before the root element (matching libxml2's xmlCreateIntSubset).
	// If no children exist yet, just append. The scan goes through Children so a
	// corrupt document child list terminates instead of hanging.
	var root Node
	for c := range Children(d) {
		if c.Type() == ElementNode {
			root = c
			break
		}
	}
	if root == nil {
		if err := d.AddChild(cur); err != nil {
			return nil, err
		}
	} else {
		// Insert cur before root.
		cur.next = root
		if prev := root.PrevSibling(); prev != nil {
			prev.baseDocNode().next = cur
			cur.prev = prev
		} else {
			setFirstChild(d, cur)
		}
		root.baseDocNode().prev = cur
	}

	return cur, nil
}

const slabSize = 256
const textContentSlabSize = 64 * 1024

// slabGrowthSizes is the growth schedule of the node slab allocators for a
// document the parser did not build: its first chunks are small heap slices of
// these sizes, and only once they are used up does it draw pooled chunks of
// slabSize nodes. A small tree built through the Create* methods, such as an
// XSLT temporary tree, then holds a few hundred bytes per node type in place of
// a pooled chunk of tens of kilobytes. textContentGrowthSizes is the same
// schedule, in bytes, for text content; a request larger than the next size
// takes a chunk of its own size. Heap chunks are left to the GC and never go to
// the pools.
var (
	slabGrowthSizes        = [...]int{8, 32}
	textContentGrowthSizes = [...]int{256, 2048}
)

// growthChunk returns the next small heap chunk from slabGrowthSizes and advances
// *taken, or nil when pooled is set or the schedule is used up, in which case
// the caller draws a pooled chunk.
func growthChunk[T any](pooled bool, taken *uint8) []T {
	if pooled || int(*taken) >= len(slabGrowthSizes) {
		return nil
	}
	n := slabGrowthSizes[*taken]
	*taken++
	return make([]T, n)
}

// recycleNodeChunks zeroes the used nodes of each chunk and returns the chunk
// to p. Node allocation does not clear a node: a chunk is zero when it comes
// from p, either fresh from the runtime or cleared here, and a growth-schedule
// chunk is a fresh heap slice. Clearing here also keeps a pooled chunk from
// holding pointers into the freed tree.
//
// chunks are in allocation order and only the last one can be partly used. A
// document draws a pooled chunk only once its growth schedule is used up, so
// while it holds any pooled chunk its slab is the unused tail of the last one:
// unused (the slab's length) counts the nodes in that tail, which are still
// zero, so only the used prefix is cleared.
//
// Free is the only path that returns a node chunk to a pool, and it goes
// through here.
func recycleNodeChunks[T any](p *pool.Pool[*[slabSize]T], chunks []*[slabSize]T, unused int) {
	last := len(chunks) - 1
	for i, c := range chunks {
		used := slabSize
		if i == last {
			used -= unused
		}
		clear(c[:used])
		p.Put(c)
	}
}

var (
	elemChunkPool        = pool.New(func() *[slabSize]Element { return new([slabSize]Element) }, nil)
	textChunkPool        = pool.New(func() *[slabSize]Text { return new([slabSize]Text) }, nil)
	nsChunkPool          = pool.New(func() *[slabSize]Namespace { return new([slabSize]Namespace) }, nil)
	attrChunkPool        = pool.New(func() *[slabSize]Attribute { return new([slabSize]Attribute) }, nil)
	textContentChunkPool = pool.New(func() *[textContentSlabSize]byte { return new([textContentSlabSize]byte) }, nil)
)

// CreateElement allocates a new Element named name and owned by this
// document, but does not attach it to the tree; the caller must insert it
// via AddChild or a sibling/parent method. A colon in name is rejected;
// supply a namespaced name through CreateElementNS instead. name is not
// otherwise checked against the XML Name/NCName grammar. When d is non-nil the
// element is drawn from the document's slab allocator, so the element must not
// outlive a call to Document.Free. A nil receiver allocates a standalone
// element with no owning document.
func (d *Document) CreateElement(name string) (*Element, error) {
	if strings.ContainsRune(name, ':') {
		return nil, fmt.Errorf("element name %q contains a colon: use CreateElementNS with a local name and Namespace parameter", name)
	}
	var e *Element
	if d != nil {
		e = d.allocElement()
	} else {
		e = newElement(name)
	}
	e.name = name
	e.etype = ElementNode
	e.doc = d
	return e, nil
}

// CreateElementNS allocates a new Element with local name localname and active
// namespace ns, owned by this document, without attaching it to the tree. The
// local name must not contain a colon; supply the namespace through ns. This is
// the namespaced analogue of CreateElement (mirroring the SetAttribute /
// SetAttributeNS pairing). A nil ns leaves the element unqualified. A nil
// receiver allocates a standalone element with no owning document. When ns is
// slab-backed by a different document, the installing SetNamespace marks that source
// document escaped so its Free will not recycle the namespace slab.
func (d *Document) CreateElementNS(localname string, ns *Namespace) (*Element, error) {
	e, err := d.CreateElement(localname)
	if err != nil {
		return nil, err
	}
	e.SetNamespace(ns)
	return e, nil
}

func (d *Document) allocElement() *Element {
	if len(d.elemSlab) == 0 {
		d.elemSlab = growthChunk[Element](d.pooledSlabs, &d.elemGrowth)
	}
	if len(d.elemSlab) == 0 {
		chunk := elemChunkPool.Get()
		d.elemChunks = append(d.elemChunks, chunk)
		d.elemSlab = chunk[:]
	}
	e := &d.elemSlab[0]
	d.elemSlab = d.elemSlab[1:]
	return e
}

// CreateText allocates a new Text node holding a copy of value, owned by this
// document, without attaching it to the tree. When d is non-nil both the node
// and its content bytes come from the document's slab allocators and must not
// outlive a call to Document.Free. A nil receiver allocates a standalone text
// node.
func (d *Document) CreateText(value []byte) *Text {
	var e *Text
	if d != nil {
		e = d.allocText()
	} else {
		e = &Text{}
	}
	e.etype = TextNode
	if d != nil {
		e.content = d.allocTextContent(len(value))
		copy(e.content, value)
	} else {
		e.content = make([]byte, len(value))
		copy(e.content, value)
	}
	e.name = textNodeName
	e.doc = d
	return e
}

func (d *Document) allocTextContent(size int) []byte {
	if size <= 0 {
		return nil
	}
	if size > textContentSlabSize {
		return make([]byte, size)
	}
	if len(d.textContentSlab) < size && !d.pooledSlabs && int(d.textContentGrowth) < len(textContentGrowthSizes) {
		d.textContentSlab = make([]byte, max(textContentGrowthSizes[d.textContentGrowth], size))
		d.textContentGrowth++
	}
	if len(d.textContentSlab) < size {
		chunk := textContentChunkPool.Get()
		d.textContentChunks = append(d.textContentChunks, chunk)
		d.textContentSlab = chunk[:]
	}
	buf := d.textContentSlab[:size:size]
	d.textContentSlab = d.textContentSlab[size:]
	return buf
}

func (d *Document) growOwnedTextContent(cur []byte, extra int) []byte {
	if extra <= 0 {
		return cur
	}

	need := len(cur) + extra
	if cap(cur) >= need {
		return cur
	}

	newCap := max(cap(cur)*2, need, 64)

	next := d.allocTextContent(newCap)
	next = next[:len(cur)]
	copy(next, cur)
	return next
}

func (d *Document) allocText() *Text {
	if len(d.textSlab) == 0 {
		d.textSlab = growthChunk[Text](d.pooledSlabs, &d.textGrowth)
	}
	if len(d.textSlab) == 0 {
		chunk := textChunkPool.Get()
		d.textChunks = append(d.textChunks, chunk)
		d.textSlab = chunk[:]
	}
	t := &d.textSlab[0]
	d.textSlab = d.textSlab[1:]
	return t
}

// CreateComment allocates a new Comment node holding value, owned by this
// document, without attaching it to the tree.
func (d *Document) CreateComment(value []byte) *Comment {
	e := newComment(value)
	e.doc = d
	return e
}

// CreateCDATASection mirrors xmlNewCDataBlock in libxml2's tree.c.
func (d *Document) CreateCDATASection(value []byte) *CDATASection {
	e := newCDATASection(value)
	e.doc = d
	return e
}

// CreateElementContent builds an ElementContent leaf node of the given type for
// use in a DTD content model: an element-reference leaf ([ElementContentElement],
// which requires a name) or a #PCDATA leaf ([ElementContentPCDATA], which
// requires an empty name). To build a sequence (,) or choice (|) node use
// [Document.CreateElementContentSeq] / [Document.CreateElementContentChoice],
// which attach and validate the two children; a bare sequence/choice leaf built
// here has nil children and cannot be serialized. The node defaults to the
// "once" occurrence; use [ElementContent.SetOccurrence] to change it.
func (d *Document) CreateElementContent(name string, etype ElementContentType) (*ElementContent, error) {
	e, err := newElementContent(name, etype)
	if err != nil {
		return nil, err
	}
	return e, nil
}

// CreateElementContentSeq builds a sequence (,) content node with the two given
// children and occurrence indicator. Both children must be non-nil and
// structurally complete; otherwise it returns an error. This is the safe way to
// compose a multi-particle content model — the resulting node can be serialized
// and matched without a nil dereference.
func (d *Document) CreateElementContentSeq(c1, c2 *ElementContent, occur ElementContentOccur) (*ElementContent, error) {
	return newElementContentBinary(ElementContentSeq, c1, c2, occur)
}

// CreateElementContentChoice builds a choice (|) content node with the two given
// children and occurrence indicator. Both children must be non-nil and
// structurally complete; otherwise it returns an error. This is the safe way to
// compose a multi-particle content model — the resulting node can be serialized
// and matched without a nil dereference.
func (d *Document) CreateElementContentChoice(c1, c2 *ElementContent, occur ElementContentOccur) (*ElementContent, error) {
	return newElementContentBinary(ElementContentOr, c1, c2, occur)
}

// GetEntity looks up a general entity declaration by name, searching the
// internal subset first and then the external subset (the latter is skipped
// for standalone="yes" documents). found reports whether a declaration was
// located.
func (d *Document) GetEntity(name string) (ent *Entity, found bool) {
	if ints := d.intSubset; ints != nil {
		ent, found = ints.LookupEntity(name)
		if found {
			return
		}
	}

	if d.standalone != StandaloneExplicitYes {
		if exts := d.extSubset; exts != nil {
			ent, found = exts.LookupEntity(name)
			return
		}
	}

	return
}

// GetParameterEntity looks up a parameter entity declaration by name,
// searching the internal subset first and then the external subset (the
// latter is skipped for standalone="yes" documents). The boolean result
// reports whether a declaration was located.
func (d *Document) GetParameterEntity(name string) (*Entity, bool) {
	if ints := d.intSubset; ints != nil {
		if ent, ok := ints.LookupParameterEntity(name); ok {
			return ent, true
		}
	}

	if d.standalone != StandaloneExplicitYes {
		if exts := d.extSubset; exts != nil {
			return exts.LookupParameterEntity(name)
		}
	}

	return nil, false
}

// IsMixedElement reports whether the element named name is declared with mixed
// (or EMPTY/ANY) content. It returns ErrElementDeclNotFound (match with
// errors.Is) if no element declaration is found for name.
//
// It faithfully preserves the content-type classification of libxml2's
// xmlIsMixedElement: EMPTY and ANY are collapsed with MIXED into a single
// "mixed" true so validity-constraint callers get an error on, e.g.,
// "<empty>     </empty>"; only an element-only content model returns false.
// It is therefore NOT a pure "is this a #PCDATA mixed model" predicate; callers
// needing the raw content-model type should inspect the element declaration
// directly (see elementDeclType, which whitespace classification uses instead).
//
// Mirroring libxml2's xmlIsMixedElement, lookup requires an internal subset
// (a document with none reports ErrElementDeclNotFound) and then searches the
// internal subset first, falling back to the external subset when the internal
// subset has no declaration for name.
func (d *Document) IsMixedElement(name string) (bool, error) {
	if d.intSubset == nil {
		return false, ErrElementDeclNotFound
	}

	edecl, ok := d.intSubset.GetElementDesc(name)
	if !ok && d.extSubset != nil {
		edecl, ok = d.extSubset.GetElementDesc(name)
	}
	if !ok {
		return false, ErrElementDeclNotFound
	}

	switch edecl.decltype {
	case enum.UndefinedElementType:
		return false, ErrElementDeclNotFound
	case enum.ElementElementType:
		return false, nil
	case enum.EmptyElementType, enum.AnyElementType, enum.MixedElementType:
		/*
		 * return 1 for EMPTY since we want VC error to pop up
		 * on <empty>     </empty> for example
		 */
		return true, nil
	}
	return true, nil
}

// elementDeclType returns the declared content-model type of the element named
// name and reports whether a declaration was found. It searches the internal
// subset first and consults the external subset only when the internal subset
// has no declaration for name (mirroring libxml2 areBlanks' two-subset lookup,
// where doc->extSubset is checked only if the doc->intSubset lookup is NULL). An
// internal-subset placeholder declaration (UndefinedElementType) counts as found
// and stops the search, exactly as a non-NULL elemDecl does in libxml2.
//
// Unlike IsMixedElement (which collapses EMPTY/ANY/MIXED into a single "mixed"
// bool for VC-error callers, mirroring xmlIsMixedElement), this returns the raw
// content-model type so whitespace classification can apply libxml2 areBlanks'
// own decl switch, in which EMPTY and UNDEFINED fall through to the heuristic
// instead of counting as mixed.
func (d *Document) elementDeclType(name string) (enum.ElementType, bool) {
	if dtd := d.intSubset; dtd != nil {
		if edecl, ok := dtd.GetElementDesc(name); ok {
			return edecl.decltype, true
		}
	}
	if dtd := d.extSubset; dtd != nil {
		if edecl, ok := dtd.GetElementDesc(name); ok {
			return edecl.decltype, true
		}
	}
	return enum.UndefinedElementType, false
}

/*
 * @doc:  the document
 * @value:  the value of the attribute
 *
 * Parse the value string and build the node list associated. Should
 * produce a flat tree with only TEXTs and ENTITY_REFs.
 * Returns a pointer to the first child
 */
func (d *Document) stringToNodeList(value string) (ret Node, err error) {
	// Fast path: no entity references — create a single text node directly.
	if strings.IndexByte(value, '&') < 0 {
		return d.CreateText([]byte(value)), nil
	}

	rdr := strings.NewReader(value)
	buf := bytes.Buffer{}
	var last Node
	var charval int32
	var r rune
	var r2 rune
	for rdr.Len() > 0 {
		r, _, err = rdr.ReadRune()
		if err != nil {
			return
		}

		// if this is not any sort of an entity , just go
		if r != '&' {
			_, _ = buf.WriteRune(r)
			continue
		}

		// well, at least the first rune sure looks like an entity, see what
		// else we have.
		r, _, err = rdr.ReadRune()
		if err != nil {
			return
		}

		if r == '#' {
			r2, _, err = rdr.ReadRune()
			if err != nil {
				return
			}

			var accumulator func(int32, rune) (int32, error)
			if r2 == 'x' {
				accumulator = accumulateHexCharRef
			} else {
				if err2 := rdr.UnreadRune(); err2 != nil {
					err = err2
					return
				}
				accumulator = accumulateDecimalCharRef
			}
			for {
				r, _, err = rdr.ReadRune()
				if err != nil {
					return
				}
				if r == ';' {
					break
				}
				charval, err = accumulator(charval, r)
				if err != nil {
					return
				}
			}
		} else {
			if err2 := rdr.UnreadRune(); err2 != nil {
				err = err2
				return
			}
			entbuf := bytes.Buffer{}
			for rdr.Len() > 0 {
				r, _, err = rdr.ReadRune()
				if err != nil {
					return
				}
				if r == ';' {
					break
				}
				_, _ = entbuf.WriteRune(r)
			}

			if r != ';' {
				err = errors.New("entity was unterminated (could not find terminating semicolon)")
				return
			}

			val := entbuf.String()

			// Predefined entities (amp, lt, gt, apos, quot) are not
			// document-dependent, so resolve them up front. This ensures
			// they inline correctly even when the document (and thus its
			// internal/external subset) is nil.
			ent, err2 := resolvePredefinedEntity(val)
			ok := err2 == nil
			if !ok {
				ent, ok = d.GetEntity(val)
			}

			// Predefined entities are inlined; all others (resolved or not)
			// become entity reference nodes. This matches libxml2's
			// xmlNodeParseAttValue behavior in tree.c.
			if ok && ent.EntityType() == enum.InternalPredefinedEntity {
				_, _ = buf.Write(ent.Content())
			} else {
				// flush the buffer so far
				if buf.Len() > 0 {
					node := d.CreateText(buf.Bytes())
					buf.Reset()

					if last == nil {
						last = node
						ret = node
					} else {
						if err2 := last.(MutableNode).AddSibling(node); err2 != nil { //nolint:forcetypeassert
							err = err2
							return
						}
						last = node
					}
				}

				// create a new REFERENCE_REF node
				var node Node
				node, err = d.CreateReference(val)
				if err != nil {
					return
				}

				// Parse entity content to build children, mirroring
				// xmlNodeParseAttValue in libxml2 tree.c.
				// Use the expanding flag to prevent infinite recursion
				// when entities reference each other.
				if ok && ent.FirstChild() == nil && !ent.expanding {
					ent.expanding = true
					var refchildren Node
					refchildren, err = d.stringToNodeList(string(ent.Content()))
					ent.expanding = false
					if err != nil {
						return
					}
					setFirstChild(ent, refchildren)
					for n := refchildren; n != nil; {
						n.baseDocNode().parent = ent
						if x := n.NextSibling(); x != nil {
							n = x
						} else {
							n = nil
						}
					}
				}

				if last == nil {
					last = node
					ret = node
				} else {
					if err2 := last.(MutableNode).AddSibling(node); err2 != nil { //nolint:forcetypeassert
						err = err2
						return
					}
					last = node
				}
			}
		}

		if charval != 0 {
			_, _ = buf.WriteRune(charval)
			charval = 0
		}
	}

	if buf.Len() > 0 {
		n := d.CreateText(buf.Bytes())

		if last == nil {
			ret = n
		} else {
			if err := last.(MutableNode).AddSibling(n); err != nil { //nolint:forcetypeassert
				return nil, err
			}
		}
	}

	return
}

// CreateCharRef builds an entity-reference node, mirroring libxml2's
// xmlNewCharRef. In the libxml2 DOM (which helium follows) a character
// reference is NOT a distinct node type: both a character reference (&#123;,
// &#xAB;) and a named entity reference (&amp;) are represented as an
// EntityRefNode, and the serializer emits the node as "&" + Name() + ";".
// The name is the reference body with any surrounding "&"/";" stripped, so a
// name of "#123"/"#xAB" serializes as the character reference "&#123;"/"&#xAB;"
// and a name of "amp" serializes as "&amp;". Unlike CreateReference, this does
// NOT look up a declared entity or attach its replacement content — it only
// constructs the bare reference node.
func (d *Document) CreateCharRef(name string) (*EntityRef, error) {
	if name == "" {
		return nil, errors.New("empty name")
	}

	var decoded string
	if name[0] != '&' {
		decoded = name
	} else {
		// the name should be everything but '&' and ';'
		if name[len(name)-1] == ';' {
			decoded = name[1 : len(name)-1]
		} else {
			decoded = name[1:]
		}
	}
	if decoded == "" {
		return nil, fmt.Errorf("char ref %q has an empty name", name)
	}

	n := newEntityRef()
	n.doc = d
	n.name = decoded
	return n, nil
}

// RegisterID associates an ID value with an element in the document's
// ID table. This is called during parsing to build an O(1) lookup table
// for GetElementByID, mirroring libxml2's xmlAddID.
func (d *Document) RegisterID(id string, elem *Element) {
	if d.ids == nil {
		d.ids = make(map[string]*Element)
	}
	// Normalize the ID value: xs:ID is derived from xs:NCName which
	// collapses whitespace. Strip leading/trailing whitespace so that
	// xml:id="id3 " is findable as "id3".
	id = strings.TrimSpace(id)
	d.ids[id] = elem
}

// IDTable returns the document's ID->element table populated during parsing
// (mirroring libxml2's xmlAddID). The returned map is the document's own, not a
// copy, and is nil for documents built without an interned ID table (e.g. one the API built and
// the parser never saw); callers MUST NOT mutate it — writing to it
// corrupts the document's ID index. It lets a derived document (e.g. an
// xsl:strip-space copy) rebuild an equivalent table by translating each entry's
// element through the original->copy correspondence, preserving the interned
// table's identity and O(1) lookup fidelity. Re-deriving ids would fall back to
// the lazy O(n) GetElementByID walk.
func (d *Document) IDTable() map[string]*Element {
	return d.ids
}

// GetElementByID returns the element in the document whose ID matches the given
// value, or nil if none matches. In a valid document an ID value is unique, so
// there is at most one such element. If the document's ID table has been
// populated (during parsing), it performs an O(1) hash lookup. Otherwise it
// falls back to an O(n) tree walk checking xml:id and DTD-declared ID
// attributes.
//
// Duplicate IDs make a document invalid, not not-well-formed: a document with
// duplicate IDs still parses successfully with DocWellFormed set. If several
// elements share an ID, the two paths pick different winners: the O(1) table
// returns the last-registered element for that value — RegisterID overwrites by
// call order, which is NOT necessarily last in document order — while the O(n)
// fallback walk returns the first in document order. Do not rely on either for
// duplicate IDs.
//
// The ID-skip state (see SetSkipIDs) is authoritative and is checked FIRST: a
// document with SkipIDs() == true resolves NO ids — it returns nil without
// consulting the ID table or performing the lazy walk. This keeps GetElementByID
// and fn:id consistent with the SkipIDs contract even on a document that already
// has a populated ID table (e.g. one parsed normally and then SetSkipIDs(true)).
func (d *Document) GetElementByID(id string) *Element {
	if d.idsSkip {
		return nil
	}
	if d.ids != nil {
		return d.ids[id]
	}

	// Fallback: O(n) tree walk for documents not built via parser. The walk
	// error is a best-effort signal only: the walker returns a sentinel error
	// to stop early once the id is found, and a Walk-detected tree cycle
	// (ErrWalkCycle) simply ends the search over the traversable portion — a
	// lookup has no error channel, so it degrades to returning any match found
	// before the cycle (nil if none), never spinning.
	var found *Element
	_ = Walk(d, NodeWalkerFunc(func(n Node) error {
		elem, ok := AsNode[*Element](n)
		if !ok {
			return nil
		}
		for _, a := range elem.Attributes() {
			// Check xml:id (normalize value — xs:ID collapses whitespace)
			if a.Name() == lexicon.QNameXMLID && strings.TrimSpace(a.Value()) == id {
				found = elem
				return errors.New("found")
			}
		}
		// Check DTD-declared ID attributes (internal and external subsets)
		for _, dtd := range []*DTD{d.intSubset, d.extSubset} {
			if dtd == nil {
				continue
			}
			for _, adecl := range dtd.attrsByElem[elem.Name()] {
				if adecl.AType() != enum.AttrID {
					continue
				}
				for _, a := range elem.Attributes() {
					if a.LocalName() == adecl.LocalName() && a.Prefix() == adecl.prefix && a.Value() == id {
						found = elem
						return errors.New("found")
					}
				}
			}
		}
		return nil
	}))
	return found
}

// AddEntity declares an entity in the document's internal subset. It returns an
// error if the document has no internal subset (create one with
// CreateInternalSubset first).
func (d *Document) AddEntity(name string, typ enum.EntityType, externalID, systemID, content string) (*Entity, error) {
	if d.intSubset == nil {
		return nil, errors.New("document without internal subset")
	}

	return d.intSubset.AddEntity(name, typ, externalID, systemID, content)
}