/*******************************************************************************

        Copyright:
            Copyright (C) 2007 Aaron Craelius and Kris Bell
            Some parts copyright (c) 2009-2016 dunnhumby Germany GmbH.
            All rights reserved.

        License:
            Tango Dual License: 3-Clause BSD License / Academic Free License v3.0.
            See LICENSE_TANGO.txt for details.

        Version: Initial release: February 2008

        Authors: Aaron, Kris

*******************************************************************************/

module ocean.text.xml.Document;

import Array = ocean.core.Array;
import ocean.meta.types.Qualifiers;
import ocean.core.Verify;

package import ocean.text.xml.PullParser;

/*******************************************************************************

        Implements a DOM atop the XML parser, supporting document
        parsing, tree traversal and ad-hoc tree manipulation.

        The DOM API is non-conformant, yet simple and functional in
        style - locate a tree node of interest and operate upon or
        around it. In all cases you will need a document instance to
        begin, whereupon it may be populated either by parsing an
        existing document or via API manipulation.

        This particular DOM employs a simple free-list to allocate
        each of the tree nodes, making it quite efficient at parsing
        XML documents. The tradeoff with such a scheme is that copying
        nodes from one document to another requires a little more care
        than otherwise. We felt this was a reasonable tradeoff, given
        the throughput gains vs the relative infrequency of grafting
        operations. For grafting within or across documents, please
        use the move() and copy() methods.

        Another simplification is related to entity transcoding. This
        is not performed internally, and becomes the responsibility
        of the client. That is, the client should perform appropriate
        entity transcoding as necessary. Paying the (high) transcoding
        cost for all documents doesn't seem appropriate.

        Parse example
        ---
        auto doc = new Document!(char);
        doc.parse (content);

        auto print = new DocPrinter!(char);
        Stdout(print(doc)).newline;
        ---

        API example
        ---
        auto doc = new Document!(char);

        // attach an xml header
        doc.header;

        // attach an element with some attributes, plus
        // a child element with an attached data value
        doc.tree.element   (null, "element")
                .attribute (null, "attrib1", "value")
                .attribute (null, "attrib2")
                .element   (null, "child", "value");

        auto print = new DocPrinter!(char);
        Stdout(print(doc)).newline;
        ---

        Note that the document tree() includes all nodes in the tree,
        and not just elements. Use doc.elements to address the topmost
        element instead. For example, adding an interior sibling to
        the prior illustration
        ---
        doc.elements.element (null, "sibling");
        ---

        Printing the name of the topmost (root) element:
        ---
        Stdout.formatln ("first element is '{}'", doc.elements.name);
        ---

        XPath examples:
        ---
        auto doc = new Document!(char);

        // attach an element with some attributes, plus
        // a child element with an attached data value
        doc.tree.element   (null, "element")
                .attribute (null, "attrib1", "value")
                .attribute (null, "attrib2")
                .element   (null, "child", "value");

        // select named-elements
        auto set = doc.query["element"]["child"];

        // select all attributes named "attrib1"
        set = doc.query.descendant.attribute("attrib1");

        // select elements with one parent and a matching text value
        set = doc.query[].filter((doc.Node n) {return n.children.hasData("value");});
        ---

        Note that path queries are temporal - they do not retain content
        across mulitple queries. That is, the lifetime of a query result
        is limited unless you explicitly copy it. For example, this will
        fail
        ---
        auto elements = doc.query["element"];
        auto children = elements["child"];
        ---

        The above will lose elements because the associated document reuses
        node space for subsequent queries. In order to retain results, do this
        ---
        auto elements = doc.query["element"].dup;
        auto children = elements["child"];
        ---

        The above .dup is generally very small (a set of pointers only). On
        the other hand, recursive queries are fully supported
        ---
        set = doc.query[].filter((doc.Node n) {return n.query[].count > 1;});
        ---

        Typical usage tends to follow the following pattern, Where each query
        result is processed before another is initiated
        ---
        foreach (node; doc.query.child("element"))
                {
                // do something with each node
                }
        ---

        Note that the parser is templated for char, wchar or dchar.

*******************************************************************************/

class Document(T_) : PullParser!(T_)
{
        public alias NodeImpl*  Node;

        private alias const(T_)     T;
        private alias T_             MutT;
        private alias XmlPath!(MutT) XmlPathT;

        private Node            root;
        private NodeImpl[]      list;
        private NodeImpl[][]    lists;
        private int             index,
                                chunks,
                                freelists;
        private XmlPathT     xpath;

        /***********************************************************************

                Construct a DOM instance. The optional parameter indicates
                the initial number of nodes assigned to the freelist

        ***********************************************************************/

        this (uint nodes = 1000)
        {
                verify (nodes > 50);
                super (null);
                xpath = new XmlPathT;

                chunks = nodes;
                newlist;
                root = allocate;
                root.id = XmlNodeType.Document;
        }

        /***********************************************************************

                Return an xpath handle to query this document. This starts
                at the document root.

                See also Node.query

        ***********************************************************************/

        final XmlPathT.NodeSet query ()
        {
                return xpath.start (root);
        }

        /***********************************************************************

                Return the root document node, from which all other nodes
                are descended.

                Returns null where there are no nodes in the document

        ***********************************************************************/

        final Node tree ()
        {
                return root;
        }

        /***********************************************************************

                Return the topmost element node, which is generally the
                root of the element tree.

                Returns null where there are no top-level element nodes

        ***********************************************************************/

        final Node elements ()
        {
                if (root)
                   {
                   auto node = root.lastChild;
                   while (node)
                          if (node.id is XmlNodeType.Element)
                              return node;
                          else
                             node = node.prev;
                   }
                return null;
        }

        /***********************************************************************

                Reset the freelist. Subsequent allocation of document nodes
                will overwrite prior instances.

        ***********************************************************************/

        final Document reset ()
        {
                root.lastChild = root.firstChild = null;
                freelists = 0;
                newlist;
                index = 1;
                return this;
        }

        /***********************************************************************

               Prepend an XML header to the document tree

        ***********************************************************************/

        final Document header ()
        {
                static immutable header = `xml version="1.0" encoding="UTF-8"`;
                root.prepend (root.create(XmlNodeType.PI, header));
                return this;
        }

        /***********************************************************************

                Prepend an XML header to the document tree. Note that this
                method currently allocates.

                Params:
                    encoding = the encoding of the xml document

        ***********************************************************************/

        final Document header (immutable(T)[] encoding)
        {
                if (encoding.length)
                    encoding = `xml version="1.0" encoding="`~encoding~`"`;
                else
                   encoding = `xml version="1.0" encoding="UTF-8"`;

                root.prepend (root.create(XmlNodeType.PI, encoding.dup));
                return this;
        }

        /***********************************************************************

                Parse the given xml content, which will reuse any existing
                node within this document. The resultant tree is retrieved
                via the document 'tree' attribute

        ***********************************************************************/

        final void parse(T[] xml)
        {
                verify (xml.ptr ! is null);
                reset;
                super.reset (xml);
                auto cur = root;
                uint defNamespace;

                while (true)
                      {
                      auto p = text.point;
                      switch (super.next)
                             {
                             case XmlTokenType.EndElement:
                             case XmlTokenType.EndEmptyElement:
                                  verify (cur !is null);
                                  cur.end = text.point;
                                  cur = cur.host;
                                  break;

                             case XmlTokenType.Data:
                                  auto node = allocate;
                                  Array.copy(node.rawValue, super.rawValue);
                                  node.id = XmlNodeType.Data;
                                  cur.append (node);
                                  break;

                             case XmlTokenType.StartElement:
                                  auto node = allocate;
                                  node.host = cur;
                                  Array.copy(node.prefixed, super.prefix);
                                  node.id = XmlNodeType.Element;
                                  Array.copy(node.localName, super.localName);
                                  node.start = p;

                                  // inline append
                                  if (cur.lastChild)
                                     {
                                     cur.lastChild.nextSibling = node;
                                     node.prevSibling = cur.lastChild;
                                     cur.lastChild = node;
                                     }
                                  else
                                     {
                                     cur.firstChild = node;
                                     cur.lastChild = node;
                                     }
                                  cur = node;
                                  break;

                             case XmlTokenType.Attribute:
                                  auto attr = allocate;
                                  Array.copy(attr.prefixed, super.prefix);
                                  Array.copy(attr.rawValue, super.rawValue);
                                  Array.copy(attr.localName, super.localName);
                                  attr.id = XmlNodeType.Attribute;
                                  cur.attrib (attr);
                                  break;

                             case XmlTokenType.PI:
                                  cur.pi_ (super.rawValue, p[0..text.point-p]);
                                  break;

                             case XmlTokenType.Comment:
                                  cur.comment_ (super.rawValue);
                                  break;

                             case XmlTokenType.CData:
                                  cur.cdata_ (super.rawValue);
                                  break;

                             case XmlTokenType.Doctype:
                                  cur.doctype_ (super.rawValue);
                                  break;

                             case XmlTokenType.Done:
                                  return;

                             default:
                                  break;
                             }
                      }
        }

        /***********************************************************************

                allocate a node from the freelist

        ***********************************************************************/

        private final Node allocate ()
        {
                if (index >= list.length)
                    newlist;

                auto p = &list[index++];
                p.doc = this;
                p.start = p.end = null;
                p.host =
                p.prevSibling =
                p.nextSibling =
                p.firstChild =
                p.lastChild =
                p.firstAttr =
                p.lastAttr = null;
                p.rawValue.length = 0;
                assumeSafeAppend(p.rawValue);
                p.localName.length = 0;
                assumeSafeAppend(p.localName);
                p.prefixed.length = 0;
                assumeSafeAppend(p.prefixed);
                return p;
        }

        /***********************************************************************

                allocate a node from the freelist

        ***********************************************************************/

        private final void newlist ()
        {
                index = 0;
                if (freelists >= lists.length)
                   {
                   lists.length = lists.length + 1;
                   lists[$-1] = new NodeImpl [chunks];
                   }
                list = lists[freelists++];
        }

        /***********************************************************************

                foreach support for visiting and selecting nodes.

                A fruct is a low-overhead mechanism for capturing context
                relating to an opApply, and we use it here to sweep nodes
                when testing for various relationships.

                See Node.attributes and Node.children

        ***********************************************************************/

        private struct Visitor
        {
                private Node node;

                public alias value      data;
                public alias hasValue   hasData;

                /***************************************************************

                        Is there anything to visit here?

                        Time complexity: O(1)

                ***************************************************************/

                bool exist ()
                {
                        return node != null;
                }

                /***************************************************************

                        traverse sibling nodes

                ***************************************************************/

                int opApply (scope int delegate(ref Node) dg)
                {
                        int ret;

                        for (auto n=node; n; n = n.nextSibling)
                             if ((ret = dg(n)) != 0)
                                  break;
                        return ret;
                }

                /***************************************************************

                        Locate a node with a matching name and/or prefix,
                        and which passes an optional filter. Each of the
                        arguments will be ignored where they are null.

                        Time complexity: O(n)

                ***************************************************************/

                Node name (T[] prefix, T[] local, scope bool delegate(Node) dg=null)
                {
                        for (auto n=node; n; n = n.nextSibling)
                            {
                            if (local.ptr && local != n.localName)
                                continue;

                            if (prefix.ptr && prefix != n.prefixed)
                                continue;

                            if (dg.ptr && dg(n) is false)
                                continue;

                            return n;
                            }
                        return null;
                }

                /***************************************************************

                        Scan nodes for a matching name and/or prefix. Each
                        of the arguments will be ignored where they are null.

                        Time complexity: O(n)

                ***************************************************************/

                bool hasName (T[] prefix, T[] local)
                {
                        return name (prefix, local) != null;
                }

                /***************************************************************

                        Locate a node with a matching name and/or prefix,
                        and which matches a specified value. Each of the
                        arguments will be ignored where they are null.

                        Time complexity: O(n)

                ***************************************************************/
version (Filter)
{
                Node value (T[] prefix, T[] local, T[] value)
                {
                        if (value.ptr)
                            return name (prefix, local, (Node n){return value == n.rawValue;});
                        return name (prefix, local);
                }
}
                /***************************************************************

                        Sweep nodes looking for a match, and returns either
                        a node or null. See value(x,y,z) or name(x,y,z) for
                        additional filtering.

                        Time complexity: O(n)

                ***************************************************************/

                Node value (T[] match)
                {
                        if (match.ptr)
                            for (auto n=node; n; n = n.nextSibling)
                                 if (match == n.rawValue)
                                     return n;
                        return null;
                }

                /***************************************************************

                        Sweep the nodes looking for a value match. Returns
                        true if found. See value(x,y,z) or name(x,y,z) for
                        additional filtering.

                        Time complexity: O(n)

                ***************************************************************/

                bool hasValue (T[] match)
                {
                        return value(match) != null;
                }
        }


        /***********************************************************************

                The node implementation

        ***********************************************************************/

        private struct NodeImpl
        {
                public void*            user;           /// open for usage
                package Document        doc;            // owning document
                package XmlNodeType     id;             // node type
                package MutT[]          prefixed;       // namespace
                package MutT[]          localName;      // name
                package MutT[]          rawValue;       // data value

                package Node            host,           // parent node
                                        prevSibling,    // prior
                                        nextSibling,    // next
                                        firstChild,     // head
                                        lastChild,      // tail
                                        firstAttr,      // head
                                        lastAttr;       // tail

                package T*              end,            // slice of the  ...
                                        start;          // original xml text

                /***************************************************************

                        Return the hosting document

                ***************************************************************/

                Document document ()
                {
                        return doc;
                }

                /***************************************************************

                        Return the node type-id

                ***************************************************************/

                XmlNodeType type ()
                {
                        return id;
                }

                /***************************************************************

                        Return the parent, which may be null

                ***************************************************************/

                Node parent ()
                {
                        return host;
                }

                /***************************************************************

                        Return the first child, which may be null

                ***************************************************************/

                Node child ()
                {
                        return firstChild;
                }

                /***************************************************************

                        Return the prior sibling, which may be null

                ***************************************************************/

                Node prev ()
                {
                        return prevSibling;
                }

                /***************************************************************

                        Return the next sibling, which may be null

                ***************************************************************/

                Node next ()
                {
                        return nextSibling;
                }

                /***************************************************************

                        Return the namespace prefix of this node (may be null)

                ***************************************************************/

                T[] prefix ()
                {
                        return prefixed;
                }

                /***************************************************************

                        Set the namespace prefix of this node (may be null)

                ***************************************************************/

                Node prefix (T[] replace)
                {
                        Array.copy(this.prefixed, replace);
                        return &this;
                }

                /***************************************************************

                        Return the vanilla node name (sans prefix)

                ***************************************************************/

                T[] name ()
                {
                        return localName;
                }

                /***************************************************************

                        Set the vanilla node name (sans prefix)

                ***************************************************************/

                Node name (T[] replace)
                {
                        Array.copy(this.localName, replace);
                        return &this;
                }

                /***************************************************************

                        Return the data content, which may be null

                ***************************************************************/

                T[] value ()
                {
                        if (type is XmlNodeType.Element)
                            foreach (child; children)
                                     if (child.id is XmlNodeType.Data ||
                                         child.id is XmlNodeType.CData)
                                         return child.rawValue;
                        return rawValue;
                }

                /***************************************************************

                        Set the raw data content, which may be null

                ***************************************************************/

                void value (T[] val)
                {
                        if (type is XmlNodeType.Element)
                            foreach (child; children)
                                     if (child.id is XmlNodeType.Data)
                                         return child.value (val);
                        Array.copy(this.rawValue, val);
                        mutate;
                }

                /***************************************************************

                        Return the full node name, which is a combination
                        of the prefix & local names. Nodes without a prefix
                        will return local-name only

                ***************************************************************/

                T[] toString (MutT[] output = null)
                {
                        if (prefixed.length)
                           {
                           auto len = prefixed.length + localName.length + 1;

                           // is the prefix already attached to the name?
                           if (prefixed.ptr + prefixed.length + 1 is localName.ptr &&
                               ':' is *(localName.ptr-1))
                               return prefixed.ptr [0 .. len];

                           // nope, copy the discrete segments into output
                           if (output.length < len)
                               output.length = len;
                           output[0..prefixed.length] = prefixed;
                           output[prefixed.length] = ':';
                           output[prefixed.length+1 .. len] = localName;
                           return output[0..len];
                           }

                        return localName;
                }

                /***************************************************************

                        Return the index of this node, or how many
                        prior siblings it has.

                        Time complexity: O(n)

                ***************************************************************/

                uint position ()
                {
                        auto count = 0;
                        auto prior = prevSibling;
                        while (prior)
                               ++count, prior = prior.prevSibling;
                        return count;
                }

                /***************************************************************

                        Detach this node from its parent and siblings

                ***************************************************************/

                Node detach ()
                {
                        return remove;
                }

                /***************************************************************

                        Return an xpath handle to query this node

                        See also Document.query

                ***************************************************************/

                final XmlPathT.NodeSet query ()
                {
                        return doc.xpath.start(&this);
                }

                /***************************************************************

                        Return a foreach iterator for node children

                ***************************************************************/

                Visitor children ()
                {
                        Visitor v = {firstChild};
                        return v;
                }

                /***************************************************************

                        Return a foreach iterator for node attributes

                ***************************************************************/

                Visitor attributes ()
                {
                        Visitor v = {firstAttr};
                        return v;
                }

                /***************************************************************

                        Duplicate the given sub-tree into place as a child
                        of this node.

                        Returns a reference to the subtree

                ***************************************************************/

                Node copy (Node tree)
                {
                        verify (tree !is null);
                        tree = tree.clone;
                        tree.migrate (document);

                        if (tree.id is XmlNodeType.Attribute)
                            attrib (tree);
                        else
                            append (tree);
                        return tree;
                }

                /***************************************************************

                        Relocate the given sub-tree into place as a child
                        of this node.

                        Returns a reference to the subtree

                ***************************************************************/

                Node move (Node tree)
                {
                        tree.detach;
                        if (tree.doc is doc)
                           {
                           if (tree.id is XmlNodeType.Attribute)
                               attrib (tree);
                           else
                              append (tree);
                           }
                        else
                           tree = copy (tree);
                        return tree;
                }

                /***************************************************************

                        Appends a new (child) Element and returns a reference
                        to it.

                ***************************************************************/

                Node element (T[] prefix, T[] local, T[] value = null)
                {
                        return element_ (prefix, local, value).mutate;
                }

                /***************************************************************

                        Attaches an Attribute and returns this, the host

                ***************************************************************/

                Node attribute (T[] prefix, T[] local, T[] value = null)
                {
                        return attribute_ (prefix, local, value).mutate;
                }

                /***************************************************************

                        Attaches a Data node and returns this, the host

                ***************************************************************/

                Node data (T[] data)
                {
                        return data_ (data).mutate;
                }

                /***************************************************************

                        Attaches a CData node and returns this, the host

                ***************************************************************/

                Node cdata (T[] cdata)
                {
                        return cdata_ (cdata).mutate;
                }

                /***************************************************************

                        Attaches a Comment node and returns this, the host

                ***************************************************************/

                Node comment (T[] comment)
                {
                        return comment_ (comment).mutate;
                }

                /***************************************************************

                        Attaches a Doctype node and returns this, the host

                ***************************************************************/

                Node doctype (T[] doctype)
                {
                        return doctype_ (doctype).mutate;
                }

                /***************************************************************

                        Attaches a PI node and returns this, the host

                ***************************************************************/

                Node pi (T[] pi)
                {
                        return pi_ (pi, null).mutate;
                }

                /***************************************************************

                        Attaches a child Element, and returns a reference
                        to the child

                ***************************************************************/

                private Node element_ (T[] prefix, T[] local, T[] value = null)
                {
                        auto node = create (XmlNodeType.Element, null);
                        append (node.set (prefix, local));
                        if (value.length)
                            node.data_ (value);
                        return node;
                }

                /***************************************************************

                        Attaches an Attribute, and returns the host

                ***************************************************************/

                private Node attribute_ (T[] prefix, T[] local, T[] value = null)
                {
                        auto node = create (XmlNodeType.Attribute, value);
                        attrib (node.set (prefix, local));
                        return &this;
                }

                /***************************************************************

                        Attaches a Data node, and returns the host

                ***************************************************************/

                private Node data_ (T[] data)
                {
                        append (create (XmlNodeType.Data, data));
                        return &this;
                }

                /***************************************************************

                        Attaches a CData node, and returns the host

                ***************************************************************/

                private Node cdata_ (T[] cdata)
                {
                        append (create (XmlNodeType.CData, cdata));
                        return &this;
                }

                /***************************************************************

                        Attaches a Comment node, and returns the host

                ***************************************************************/

                private Node comment_ (T[] comment)
                {
                        append (create (XmlNodeType.Comment, comment));
                        return &this;
                }

                /***************************************************************

                        Attaches a PI node, and returns the host

                ***************************************************************/

                private Node pi_ (T[] pi, T[] patch)
                {
                        append (create(XmlNodeType.PI, pi).patch(patch));
                        return &this;
                }

                /***************************************************************

                        Attaches a Doctype node, and returns the host

                ***************************************************************/

                private Node doctype_ (T[] doctype)
                {
                        append (create (XmlNodeType.Doctype, doctype));
                        return &this;
                }

                /***************************************************************

                        Append an attribute to this node, The given attribute
                        cannot have an existing parent.

                ***************************************************************/

                private void attrib (Node node)
                {
                        verify (node.parent is null);
                        node.host = &this;
                        if (lastAttr)
                           {
                           lastAttr.nextSibling = node;
                           node.prevSibling = lastAttr;
                           lastAttr = node;
                           }
                        else
                           firstAttr = lastAttr = node;
                }

                /***************************************************************

                        Append a node to this one. The given node cannot
                        have an existing parent.

                ***************************************************************/

                private void append (Node node)
                {
                        verify (node.parent is null);
                        node.host = &this;
                        if (lastChild)
                           {
                           lastChild.nextSibling = node;
                           node.prevSibling = lastChild;
                           lastChild = node;
                           }
                        else
                           firstChild = lastChild = node;
                }

                /***************************************************************

                        Prepend a node to this one. The given node cannot
                        have an existing parent.

                ***************************************************************/

                private void prepend (Node node)
                {
                        verify (node.parent is null);
                        node.host = &this;
                        if (firstChild)
                           {
                           firstChild.prevSibling = node;
                           node.nextSibling = firstChild;
                           firstChild = node;
                           }
                        else
                           firstChild = lastChild = node;
                }

                /***************************************************************

                        Configure node values

                ***************************************************************/

                private Node set (T[] prefix, T[] local)
                {
                        Array.copy(this.localName, local);
                        Array.copy(this.prefixed, prefix);
                        return &this;
                }

                /***************************************************************

                        Creates and returns a child Element node

                ***************************************************************/

                private Node create (XmlNodeType type, T[] value)
                {
                        auto node = document.allocate;
                        Array.copy(node.rawValue, value);
                        node.id = type;
                        return node;
                }

                /***************************************************************

                        Detach this node from its parent and siblings

                ***************************************************************/

                private Node remove()
                {
                        if (! host)
                              return &this;

                        mutate;
                        if (prevSibling && nextSibling)
                           {
                           prevSibling.nextSibling = nextSibling;
                           nextSibling.prevSibling = prevSibling;
                           prevSibling = null;
                           nextSibling = null;
                           host = null;
                           }
                        else
                           if (nextSibling)
                              {
                              verify(host.firstChild == &this);
                              parent.firstChild = nextSibling;
                              nextSibling.prevSibling = null;
                              nextSibling = null;
                              host = null;
                              }
                           else
                              if (type != XmlNodeType.Attribute)
                                 {
                                 if (prevSibling)
                                    {
                                    verify(host.lastChild == &this);
                                    host.lastChild = prevSibling;
                                    prevSibling.nextSibling = null;
                                    prevSibling = null;
                                    host = null;
                                    }
                                 else
                                    {
                                    verify(host.firstChild == &this);
                                    verify(host.lastChild == &this);
                                    host.firstChild = null;
                                    host.lastChild = null;
                                    host = null;
                                    }
                                 }
                              else
                                 {
                                 if (prevSibling)
                                    {
                                    verify(host.lastAttr == &this);
                                    host.lastAttr = prevSibling;
                                    prevSibling.nextSibling = null;
                                    prevSibling = null;
                                    host = null;
                                    }
                                 else
                                    {
                                    verify(host.firstAttr == &this);
                                    verify(host.lastAttr == &this);
                                    host.firstAttr = null;
                                    host.lastAttr = null;
                                    host = null;
                                    }
                                 }

                        return &this;
                }

                /***************************************************************

                        Patch the serialization text, causing DocPrinter
                        to ignore the subtree of this node, and instead
                        emit the provided text as raw XML output.

                        Warning: this function does *not* copy the provided
                        text, and may be removed from future revisions

                ***************************************************************/

                private Node patch (T[] text)
                {
                        end = text.ptr + text.length;
                        start = text.ptr;
                        return &this;
                }

                /***************************************************************

                        purge serialization cache for this node and its
                        ancestors

                ***************************************************************/

                private Node mutate ()
                {
                        auto node = &this;
                        do {
                           node.end = null;
                           } while ((node = node.host) !is null);

                        return &this;
                }

                /***************************************************************

                        Duplicate a single node

                ***************************************************************/

                private Node dup ()
                {
                        return create(type, rawValue.dup).set(prefixed.dup, localName.dup);
                }

                /***************************************************************

                        Duplicate a subtree

                ***************************************************************/

                private Node clone ()
                {
                        auto p = dup;

                        foreach (attr; attributes)
                                 p.attrib (attr.dup);
                        foreach (child; children)
                                 p.append (child.clone);
                        return p;
                }

                /***************************************************************

                        Reset the document host for this subtree

                ***************************************************************/

                private void migrate (Document host)
                {
                        this.doc = host;
                        foreach (attr; attributes)
                                 attr.migrate (host);
                        foreach (child; children)
                                 child.migrate (host);
                }
        }
}


/*******************************************************************************

        XPath support

        Provides support for common XPath axis and filtering functions,
        via a native-D interface instead of typical interpreted notation.

        The general idea here is to generate a NodeSet consisting of those
        tree-nodes which satisfy a filtering function. The direction, or
        axis, of tree traversal is governed by one of several predefined
        operations. All methods facilitiate call-chaining, where each step
        returns a new NodeSet instance to be operated upon.

        The set of nodes themselves are collected in a freelist, avoiding
        heap-activity and making good use of D array-slicing facilities.

        XPath examples
        ---
        auto doc = new Document!(char);

        // attach an element with some attributes, plus
        // a child element with an attached data value
        doc.tree.element   (null, "element")
                .attribute (null, "attrib1", "value")
                .attribute (null, "attrib2")
                .element   (null, "child", "value");

        // select named-elements
        auto set = doc.query["element"]["child"];

        // select all attributes named "attrib1"
        set = doc.query.descendant.attribute("attrib1");

        // select elements with one parent and a matching text value
        set = doc.query[].filter((doc.Node n) {return n.children.hasData("value");});
        ---

        Note that path queries are temporal - they do not retain content
        across mulitple queries. That is, the lifetime of a query result
        is limited unless you explicitly copy it. For example, this will
        fail to operate as one might expect
        ---
        auto elements = doc.query["element"];
        auto children = elements["child"];
        ---

        The above will lose elements, because the associated document reuses
        node space for subsequent queries. In order to retain results, do this
        ---
        auto elements = doc.query["element"].dup;
        auto children = elements["child"];
        ---

        The above .dup is generally very small (a set of pointers only). On
        the other hand, recursive queries are fully supported
        ---
        set = doc.query[].filter((doc.Node n) {return n.query[].count > 1;});
        ---

        Typical usage tends to exhibit the following pattern, Where each query
        result is processed before another is initiated
        ---
        foreach (node; doc.query.child("element"))
                {
                // do something with each node
                }
        ---

        Supported axis include:
        ---
        .child                  immediate children
        .parent                 immediate parent
        .next                   following siblings
        .prev                   prior siblings
        .ancestor               all parents
        .descendant             all descendants
        .data                   text children
        .cdata                  cdata children
        .attribute              attribute children
        ---

        Each of the above accept an optional string, which is used in an
        axis-specific way to filter nodes. For instance, a .child("food")
        will filter <food> child elements. These variants are shortcuts
        to using a filter to post-process a result. Each of the above also
        have variants which accept a delegate instead.

        In general, you traverse an axis and operate upon the results. The
        operation applied may be another axis traversal, or a filtering
        step. All steps can be, and generally should be chained together.
        Filters are implemented via a delegate mechanism
        ---
        .filter (bool delegate(Node))
        ---

        Where the delegate returns true if the node passes the filter. An
        example might be selecting all nodes with a specific attribute
        ---
        auto set = doc.query.descendant.filter (
                    (doc.Node n){return n.attributes.hasName (null, "test");}
                   );
        ---

        Obviously this is not as clean and tidy as true XPath notation, but
        that can be wrapped atop this API instead. The benefit here is one
        of raw throughput - important for some applications.

        Note that every operation returns a discrete result. Methods first()
        and last() also return a set of one or zero elements. Some language
        specific extensions are provided for too
        ---
        * .child() can be substituted with [] notation instead

        * [] notation can be used to index a specific element, like .nth()

        * the .nodes attribute exposes an underlying Node[], which may be
          sliced or traversed in the usual D manner
        ---

       Other (query result) utility methods include
       ---
       .dup
       .first
       .last
       .opIndex
       .nth
       .count
       .opApply
       ---

       XmlPath itself needs to be a class in order to avoid forward-ref issues.

*******************************************************************************/

public class XmlPath(T)
{
        public alias Document!(T) Doc;          /// the typed document
        public alias Doc.Node     Node;         /// generic document node

        private Node[]          freelist;
        private uint            freeIndex,
                                markIndex;
        private uint            recursion;

        /***********************************************************************

                Prime a query

                Returns a NodeSet containing just the given node, which
                can then be used to cascade results into subsequent NodeSet
                instances.

        ***********************************************************************/

        final NodeSet start (Node root)
        {
                // we have to support recursion which may occur within
                // a filter callback
                if (recursion is 0)
                   {
                   if (freelist.length is 0)
                       freelist.length = 256;
                   freeIndex = 0;
                   }

                NodeSet set = {this};
                auto mark = freeIndex;
                allocate(root);
                return set.assign (mark);
        }

        /***********************************************************************

                This is the meat of XPath support. All of the NodeSet
                operators exist here, in order to enable call-chaining.

                Note that some of the axis do double-duty as a filter
                also. This is just a convenience factor, and doesn't
                change the underlying mechanisms.

        ***********************************************************************/

        struct NodeSet
        {
                private XmlPath host;
                public  Node[]  nodes;  /// array of selected nodes

                /***************************************************************

                        Return a duplicate NodeSet

                ***************************************************************/

                NodeSet dup ()
                {
                        NodeSet copy = {host};
                        copy.nodes = nodes.dup;
                        return copy;
                }

                /***************************************************************

                        Return the number of selected nodes in the set

                ***************************************************************/

                size_t count ()
                {
                        return nodes.length;
                }

                /***************************************************************

                        Return a set containing just the first node of
                        the current set

                ***************************************************************/

                NodeSet first ()
                {
                        return nth (0);
                }

                /***************************************************************

                        Return a set containing just the last node of
                        the current set

                ***************************************************************/

                NodeSet last ()
                {
                        auto i = nodes.length;
                        if (i > 0)
                            --i;
                        return nth (i);
                }

                /***************************************************************

                        Return a set containing just the nth node of
                        the current set

                ***************************************************************/

                NodeSet opIndex (uint i)
                {
                        return nth (i);
                }

                /***************************************************************

                        Return a set containing just the nth node of
                        the current set

                ***************************************************************/

                NodeSet nth (size_t index)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;
                        if (index < nodes.length)
                            host.allocate (nodes [index]);
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all child elements of the
                        nodes within this set

                ***************************************************************/

                NodeSet opSlice ()
                {
                        return child();
                }

                /***************************************************************

                        Return a set containing all child elements of the
                        nodes within this set, which match the given name

                ***************************************************************/

                NodeSet opIndex (in T[] name)
                {
                        return child (name);
                }

                /***************************************************************

                        Return a set containing all parent elements of the
                        nodes within this set, which match the optional name

                ***************************************************************/

                NodeSet parent (in T[] name = null)
                {
                        if (name.ptr)
                            return parent ((Node node){return node.name == name;});
                        return parent (&always);
                }

                /***************************************************************

                        Return a set containing all data nodes of the
                        nodes within this set, which match the optional
                        value

                ***************************************************************/

                NodeSet data (in T[] value = null)
                {
                        if (value.ptr)
                            return child ((Node node){return node.value == value;},
                                           XmlNodeType.Data);
                        return child (&always, XmlNodeType.Data);
                }

                /***************************************************************

                        Return a set containing all cdata nodes of the
                        nodes within this set, which match the optional
                        value

                ***************************************************************/

                NodeSet cdata (in T[] value = null)
                {
                        if (value.ptr)
                            return child ((Node node){return node.value == value;},
                                           XmlNodeType.CData);
                        return child (&always, XmlNodeType.CData);
                }

                /***************************************************************

                        Return a set containing all attributes of the
                        nodes within this set, which match the optional
                        name

                ***************************************************************/

                NodeSet attribute (in T[] name = null)
                {
                        if (name.ptr)
                            return attribute ((Node node){return node.name == name;});
                        return attribute (&always);
                }

                /***************************************************************

                        Return a set containing all descendant elements of
                        the nodes within this set, which match the given name

                ***************************************************************/

                NodeSet descendant (in T[] name = null)
                {
                        if (name.ptr)
                            return descendant ((Node node){return node.name == name;});
                        return descendant (&always);
                }

                /***************************************************************

                        Return a set containing all child elements of the
                        nodes within this set, which match the optional name

                ***************************************************************/

                NodeSet child (in T[] name = null)
                {
                        if (name.ptr)
                            return child ((Node node){return node.name == name;});
                        return  child (&always);
                }

                /***************************************************************

                        Return a set containing all ancestor elements of
                        the nodes within this set, which match the optional
                        name

                ***************************************************************/

                NodeSet ancestor (in T[] name = null)
                {
                        if (name.ptr)
                            return ancestor ((Node node){return node.name == name;});
                        return ancestor (&always);
                }

                /***************************************************************

                        Return a set containing all prior sibling elements of
                        the nodes within this set, which match the optional
                        name

                ***************************************************************/

                NodeSet prev (in T[] name = null)
                {
                        if (name.ptr)
                            return prev ((Node node){return node.name == name;});
                        return prev (&always);
                }

                /***************************************************************

                        Return a set containing all subsequent sibling
                        elements of the nodes within this set, which
                        match the optional name

                ***************************************************************/

                NodeSet next (in T[] name = null)
                {
                        if (name.ptr)
                            return next ((Node node){return node.name == name;});
                        return next (&always);
                }

                /***************************************************************

                        Return a set containing all nodes within this set
                        which pass the filtering test

                ***************************************************************/

                NodeSet filter (scope bool delegate(Node) filter)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;

                        foreach (node; nodes)
                                 test (filter, node);
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all child nodes of
                        the nodes within this set which pass the
                        filtering test

                ***************************************************************/

                NodeSet child (scope bool delegate(Node) filter,
                               XmlNodeType type = XmlNodeType.Element)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;

                        foreach (parent; nodes)
                                 foreach (child; parent.children)
                                          if (child.id is type)
                                              test (filter, child);
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all attribute nodes of
                        the nodes within this set which pass the given
                        filtering test

                ***************************************************************/

                NodeSet attribute (scope bool delegate(Node) filter)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;

                        foreach (node; nodes)
                                 foreach (attr; node.attributes)
                                          test (filter, attr);
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all descendant nodes of
                        the nodes within this set, which pass the given
                        filtering test

                ***************************************************************/

                NodeSet descendant (scope bool delegate(Node) filter,
                                    XmlNodeType type = XmlNodeType.Element)
                {
                        void traverse (Node parent)
                        {
                                 foreach (child; parent.children)
                                         {
                                         if (child.id is type)
                                             test (filter, child);
                                         if (child.firstChild)
                                             traverse (child);
                                         }
                        }

                        NodeSet set = {host};
                        auto mark = host.mark;

                        foreach (node; nodes)
                                 traverse (node);
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all parent nodes of
                        the nodes within this set which pass the given
                        filtering test

                ***************************************************************/

                NodeSet parent (scope bool delegate(Node) filter)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;

                        foreach (node; nodes)
                                {
                                auto p = node.parent;
                                if (p && p.id != XmlNodeType.Document && !set.has(p))
                                   {
                                   test (filter, p);
                                   // continually update our set of nodes, so
                                   // that set.has() can see a prior entry.
                                   // Ideally we'd avoid invoking test() on
                                   // prior nodes, but I don't feel the added
                                   // complexity is warranted
                                   set.nodes = host.slice (mark);
                                   }
                                }
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all ancestor nodes of
                        the nodes within this set, which pass the given
                        filtering test

                ***************************************************************/

                NodeSet ancestor (scope bool delegate(Node) filter)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;

                        void traverse (Node child)
                        {
                                auto p = child.host;
                                if (p && p.id != XmlNodeType.Document && !set.has(p))
                                   {
                                   test (filter, p);
                                   // continually update our set of nodes, so
                                   // that set.has() can see a prior entry.
                                   // Ideally we'd avoid invoking test() on
                                   // prior nodes, but I don't feel the added
                                   // complexity is warranted
                                   set.nodes = host.slice (mark);
                                   traverse (p);
                                   }
                        }

                        foreach (node; nodes)
                                 traverse (node);
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all following siblings
                        of the ones within this set, which pass the given
                        filtering test

                ***************************************************************/

                NodeSet next (scope bool delegate(Node) filter,
                              XmlNodeType type = XmlNodeType.Element)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;

                        foreach (node; nodes)
                                {
                                auto p = node.nextSibling;
                                while (p)
                                      {
                                      if (p.id is type)
                                          test (filter, p);
                                      p = p.nextSibling;
                                      }
                                }
                        return set.assign (mark);
                }

                /***************************************************************

                        Return a set containing all prior sibling nodes
                        of the ones within this set, which pass the given
                        filtering test

                ***************************************************************/

                NodeSet prev (scope bool delegate(Node) filter,
                              XmlNodeType type = XmlNodeType.Element)
                {
                        NodeSet set = {host};
                        auto mark = host.mark;

                        foreach (node; nodes)
                                {
                                auto p = node.prevSibling;
                                while (p)
                                      {
                                      if (p.id is type)
                                          test (filter, p);
                                      p = p.prevSibling;
                                      }
                                }
                        return set.assign (mark);
                }

                /***************************************************************

                        Traverse the nodes of this set

                ***************************************************************/

                int opApply (scope int delegate(ref Node) dg)
                {
                        int ret;

                        foreach (node; nodes)
                                 if ((ret = dg (node)) != 0)
                                      break;
                        return ret;
                }

                /***************************************************************

                        Common predicate

                ***************************************************************/

                private bool always (Node node)
                {
                        return true;
                }

                /***************************************************************

                        Assign a slice of the freelist to this NodeSet

                ***************************************************************/

                private NodeSet assign (uint mark)
                {
                        nodes = host.slice (mark);
                        return this;
                }

                /***************************************************************

                        Execute a filter on the given node. We have to
                        deal with potential query recusion, so we set
                        all kinda crap to recover from that

                ***************************************************************/

                private void test (scope bool delegate(Node) filter, Node node)
                {
                        auto pop = host.push;
                        auto add = filter (node);
                        host.pop (pop);
                        if (add)
                            host.allocate (node);
                }

                /***************************************************************

                        We typically need to filter ancestors in order
                        to avoid duplicates, so this is used for those
                        purposes

                ***************************************************************/

                private bool has (Node p)
                {
                        foreach (node; nodes)
                                 if (node is p)
                                     return true;
                        return false;
                }
        }

        /***********************************************************************

                Return the current freelist index

        ***********************************************************************/

        private uint mark ()
        {
                return freeIndex;
        }

        /***********************************************************************

                Recurse and save the current state

        ***********************************************************************/

        private uint push ()
        {
                ++recursion;
                return freeIndex;
        }

        /***********************************************************************

                Restore prior state

        ***********************************************************************/

        private void pop (uint prior)
        {
                freeIndex = prior;
                --recursion;
        }

        /***********************************************************************

                Return a slice of the freelist

        ***********************************************************************/

        private Node[] slice (uint mark)
        {
                verify (mark <= freeIndex);
                return freelist [mark .. freeIndex];
        }

        /***********************************************************************

                Allocate an entry in the freelist, expanding as necessary

        ***********************************************************************/

        private uint allocate (Node node)
        {
                if (freeIndex >= freelist.length)
                    freelist.length = freelist.length + freelist.length / 2;

                freelist[freeIndex] = node;
                return ++freeIndex;
        }
}

version (unittest)
{
    import ocean.core.Test;
    import ocean.text.xml.DocPrinter;
}

unittest
{
    auto doc = new Document!(char);
    auto printer = new DocPrinter!(char);
    mstring buffer;

    auto doc1 = `<?xml version="1.0" encoding="UTF-8"?>
<root>123456789
  <second>second</second>
  <third>third</third>
</root>`;

    auto doc2 = `<?xml version="1.0" encoding="UTF-8"?>
<root>12345
  <one>one</one>
  <two>two</two>
</root>`;

    void generateBasicXML (cstring root_value, cstring node1, cstring value1,
        cstring node2, cstring value2)
    {
        // A single text buffer is used to hold the elements to test that the
        // elements do not just slice the input but actually copy it to the
        // elements.
        Array.copy(buffer, root_value);

        doc.header();

        auto root = doc.tree.element(null, "root", buffer);

        Array.copy(buffer, node1);
        root.element(null, node1, buffer);

        Array.copy(buffer, node2);
        root.element(null, node2, buffer);
    }

    // Test basic XML file generation.
    generateBasicXML("123456789", "second", "second", "third", "third");
    auto result1 = printer.print(doc);
    test!("==")(result1, doc1);

    // Now do a second document generation that re-uses the same root doc and
    // check for no memory allocations.
    testNoAlloc({
        doc.reset();
        generateBasicXML("12345", "one", "one", "two", "two");
    }());

    auto result2 = printer.print(doc);
    test!("==")(result2, doc2);
}

unittest
{
    auto doc = new Document!(char);
    auto printer = new DocPrinter!(char);
    mstring buffer;

    auto complex_doc = `
<VAST version="3.0">
  <InLine>
    <AdTitle>VAST 3.0 Instream Test</AdTitle>
    <Creatives>
      <Creative id="123456" adId="654321"/>
    </Creatives>
  </InLine>
</VAST>`;

    // Generate a more complex XML document.
    auto root = doc.tree.element(null, "VAST").attribute(null, "version", "3.0");

    auto inline = root.element(null, "InLine");

    Array.copy(buffer, "VAST 3.0 Instream Test");
    inline.element(null, "AdTitle", buffer);

    auto creatives = inline.element(null, "Creatives");

    Array.copy(buffer, "123456");
    auto creative = creatives.element(null, `Creative`).
        attribute(null, `id`, buffer);
    Array.copy(buffer, "654321");
    creative.attribute(null, `adId`, buffer);

    auto complex_result = printer.print(doc);
    test!("==")(complex_result, complex_doc);
}


version (Old)
{
/*******************************************************************************

        Specification for an XML serializer

*******************************************************************************/

interface IXmlPrinter(T)
{
        public alias Document!(T) Doc;          /// the typed document
        public alias Doc.Node Node;             /// generic document node
        public alias print opCall;              /// alias for print method

        /***********************************************************************

                Generate a text representation of the document tree

        ***********************************************************************/

        T[] print (Doc doc);

        /***********************************************************************

                Generate a representation of the given node-subtree

        ***********************************************************************/

        void print (Node root, scope void delegate(T[][]...) emit);
}
}



/*******************************************************************************

*******************************************************************************/

debug (Document)
{
        import ocean.io.Stdout;
        import ocean.text.xml.DocPrinter;

        void main()
        {
                auto doc = new Document!(char);

                // attach an xml header
                doc.header;

                // attach an element with some attributes, plus
                // a child element with an attached data value
                doc.tree.element   (null, "root")
                        .attribute (null, "attrib1", "value")
                        .attribute (null, "attrib2", "other")
                        .element   (null, "child")
                        .cdata     ("some text");

                // attach a sibling to the interior elements
                doc.elements.element (null, "sibling");

                bool foo (doc.Node node)
                {
                        node = node.attributes.name(null, "attrib1");
                        return node && "value" == node.value;
                }

                foreach (node; doc.query.descendant("root").filter(&foo).child)
                         Stdout.formatln(">> {}", node.name);

                foreach (node; doc.elements.attributes)
                         Stdout.formatln("<< {}", node.name);

                foreach (node; doc.elements.children)
                         Stdout.formatln("<< {}", node.name);

                foreach (node; doc.query.descendant.cdata)
                         Stdout.formatln ("{}: {}", node.parent.name, node.value);

                // emit the result
                auto printer = new DocPrinter!(char);
                printer.print (doc, stdout);
                doc.reset;
        }
}