Program Listing for File node.hpp

↰ Return to documentation for file (mxml/node.hpp)

/*-
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2024 Maarten L. Hekkelman
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#pragma once


#include "mxml/error.hpp"
#include "mxml/version.hpp"

#include <algorithm>
#include <cassert>
#include <compare>
#include <string>
#include <utility>
#include <vector>

namespace mxml
{

// forward declarations

class node;
class element;
class text;
class attribute;
class name_space;
class comment;
class cdata;
class processing_instruction;
class document;
class element_container;

using node_set = std::vector<node *>;
using element_set = std::vector<element *>;

template <typename T>
concept NodeType = std::is_base_of_v<mxml::node, std::remove_cvref_t<T>>;

enum class node_type {
    element,
    text,
    attribute,
    comment,
    cdata,
    document,
    processing_instruction,

    header
};

// --------------------------------------------------------------------

struct format_info
{
    bool indent = false;
    bool indent_attributes = false;
    bool collapse_tags = true;
    bool suppress_comments = false;
    bool escape_white_space = false;
    bool escape_double_quote = true;
    bool html = false;
    std::size_t indent_width = 0;
    std::size_t indent_level = 0;
    version_type version{ 1, 0 };
};

// --------------------------------------------------------------------

class node
{
  public:
    virtual ~node();
    virtual constexpr node_type type() const = 0;

    virtual std::string lang() const;

    virtual std::string get_qname() const;

    virtual void set_qname(std::string qn) {}

    void set_qname(std::string prefix, std::string name)
    {
        set_qname(prefix.empty() ? std::move(name) : prefix + ':' + name);
    }

    virtual std::string name() const;
    virtual std::string get_prefix() const;
    virtual std::string get_ns() const;

    virtual std::string namespace_for_prefix(std::string_view prefix) const;

    virtual std::pair<std::string, bool> prefix_for_namespace(std::string_view uri) const;

    virtual std::string prefix_tag(std::string tag, std::string_view uri) const;

    virtual std::string str() const = 0;

    // --------------------------------------------------------------------
    // low level routines

    // basic access

    // All nodes should have a single root node
    virtual element_container *root();
    virtual const element_container *root() const;

    void parent(element_container *p) noexcept { m_parent = p; }
    element_container *parent() { return m_parent; }
    const element_container *parent() const { return m_parent; }

    void next(const node *n) noexcept { m_next = const_cast<node *>(n); }
    node *next() { return m_next; }
    const node *next() const { return m_next; }

    void prev(const node *n) noexcept { m_prev = const_cast<node *>(n); }
    node *prev() { return m_prev; }
    const node *prev() const { return m_prev; }

    virtual bool equals(const node *n) const;

    virtual void write(std::ostream &os, format_info fmt) const = 0;

  protected:
    friend class basic_node_list;
    template <typename>
    friend class node_list;
    friend class element;

    node()
    {
        init();
    }

    node(const node &n) = delete;
    node(node &&n) = delete;
    node &operator=(const node &n) = delete;
    node &operator=(node &&n) = delete;

    friend void swap(node &a, node &b) noexcept
    {
        if (a.m_next == &a) // a empty?
        {
            if (b.m_next != &b) // b empty?
            {
                a.m_next = b.m_next;
                a.m_prev = b.m_prev;
                b.init();
            }
        }
        else if (b.m_next == &b)
        {
            b.m_next = a.m_next;
            b.m_prev = a.m_prev;
            a.init();
        }
        else
        {
            std::swap(a.m_next, b.m_next);
            std::swap(a.m_prev, b.m_prev);
        }

        a.m_next->m_prev = a.m_prev->m_next = &a;
        b.m_next->m_prev = b.m_prev->m_next = &b;
    }

  protected:
    void init()
    {
        m_next = m_prev = this;
    }

    element_container *m_parent = nullptr;
    node *m_next;
    node *m_prev;

};

// --------------------------------------------------------------------
// Basic node list is a private class, it is the base class
// for node_list

class basic_node_list
{
  protected:
    struct node_list_header : public node
    {
        constexpr node_type type() const override { return node_type::header; }

        void write(std::ostream &/* os */, format_info /* fmt */) const override {}
        std::string str() const override { return {}; }

        friend void swap(node_list_header &a, node_list_header &b)
        {
            swap(static_cast<node &>(a), static_cast<node &>(b));

            for (node *n = a.m_next; n != &a; n = n->next())
                n->parent(a.m_parent);

            for (node *n = b.m_next; n != &b; n = n->next())
                n->parent(b.m_parent);
        }
    };

    node_list_header m_header_node;
    node *m_header = nullptr;
    bool m_owner;

    template <typename T>
    friend class node_list;

  protected:
    basic_node_list(element_container *e)
        : m_header(&m_header_node)
    {
        m_header_node.parent(e);
    }

  public:
    virtual ~basic_node_list()
    {
    }

    bool operator==(const basic_node_list &b) const;

    virtual void clear();

  protected:
    basic_node_list(basic_node_list &&nl) = delete;
    basic_node_list &operator=(const basic_node_list &nl) = delete;
    basic_node_list &operator=(basic_node_list &&nl) = delete;

    friend void swap(basic_node_list &a, basic_node_list &b) noexcept
    {
        if (a.m_header != &a.m_header_node and b.m_header != &b.m_header_node)
            std::swap(a.m_header, b.m_header);
        else
        {
            assert((a.m_header != &a.m_header_node) == (b.m_header != &b.m_header_node));
            swap(a.m_header_node, b.m_header_node);
        }
    }

  protected:
    // proxy methods for every insertion

    virtual node *insert_impl(const node *p, node *n);

    node *erase_impl(node *n);
};

// --------------------------------------------------------------------

template <typename T>
class iterator_impl
{
  public:
    template <typename T2>
    friend class iterator_impl;

    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using pointer = value_type *;
    using reference = value_type &;
    using difference_type = std::ptrdiff_t;

    iterator_impl() = default;

    iterator_impl(const node *current)
        : m_current(const_cast<node *>(current))
    {
        skip();
    }

    iterator_impl(const iterator_impl &i) = default;

    template <typename Iterator>
        requires(std::is_base_of_v<value_type, typename Iterator::value_type>)
    iterator_impl(const Iterator &i)
        : m_current(const_cast<node *>(i.m_current))
    {
        skip();
    }

    iterator_impl &operator=(iterator_impl i)
    {
        m_current = i.m_current;
        return *this;
    }

    template <typename Iterator>
        requires(std::is_base_of_v<value_type, typename Iterator::value_type>)
    iterator_impl &operator=(const Iterator &i)
    {
        m_current = i.m_current;
        return *this;
    }

    reference operator*() { return *static_cast<value_type *>(m_current); }
    pointer operator->() { return static_cast<value_type *>(m_current); }

    iterator_impl &operator++()
    {
        m_current = m_current->next();
        skip();
        return *this;
    }

    iterator_impl operator++(int)
    {
        iterator_impl iter(*this);
        operator++();
        return iter;
    }

    iterator_impl &operator--()
    {
        m_current = m_current->prev();
        if constexpr (std::is_same_v<std::remove_cv_t<value_type>, element>)
        {
            while (m_current->type() != node_type::element and m_current->type() != node_type::header)
                m_current = m_current->prev();
        }

        return *this;
    }

    iterator_impl operator--(int)
    {
        iterator_impl iter(*this);
        operator--();
        return iter;
    }

    template <typename IteratorType>
        requires NodeType<typename IteratorType::node_type>
    bool operator==(const IteratorType &other) const
    {
        return m_current == other.m_current;
    }

    bool operator==(const iterator_impl &other) const
    {
        return m_current == other.m_current;
    }

    template <NodeType T2>
    bool operator==(const T2 *n) const { return m_current == n; }

    explicit operator pointer() const { return static_cast<pointer>(m_current); }

  private:
    using node_base_type = std::conditional_t<std::is_const_v<T>, const node, node>;

    void skip()
    {
        if constexpr (std::is_same_v<std::remove_cv_t<value_type>, element>)
        {
            while (m_current->type() != node_type::element and m_current->type() != node_type::header)
                m_current = m_current->next();
        }
    }

    node_base_type *m_current = nullptr;
};

// --------------------------------------------------------------------

template <typename T = node>
class node_list : public basic_node_list
{
  public:
    using value_type = T;
    using allocator_type = std::allocator<value_type>;
    using size_type = size_t;
    using difference_type = std::ptrdiff_t;
    using reference = value_type &;
    using const_reference = const value_type &;
    using pointer = value_type *;
    using const_pointer = const value_type *;

    node_list(element_container *e);

    node_list(const node_list &nl) = delete;
    node_list &operator=(const node_list &) = delete;
    using iterator = iterator_impl<value_type>;

    using const_iterator = iterator_impl<const value_type>;

    iterator begin() { return iterator(m_header->m_next); }
    iterator end() { return iterator(m_header); }

    const_iterator cbegin() { return const_iterator(m_header->m_next); }
    const_iterator cend() { return const_iterator(m_header); }

    const_iterator begin() const { return const_iterator(m_header->m_next); }
    const_iterator end() const { return const_iterator(m_header); }

    value_type &front() { return *begin(); }
    const value_type &front() const { return *begin(); }

    value_type &back() { return *std::prev(end()); }
    const value_type &back() const { return *std::prev(end()); }

    size_t size() const { return std::distance(begin(), end()); }
    bool empty() const { return size() == 0; }
    explicit operator bool() const { return not empty(); }

    iterator insert(const_iterator pos, const value_type &e)
    {
        return insert_impl(pos, new value_type(e));
    }

    iterator insert(const_iterator pos, value_type &&e)
    {
        return insert_impl(pos, new value_type(std::move(e)));
    }

    template <typename... Args>
        requires std::is_same_v<value_type, attribute> or std::is_same_v<value_type, element>
    iterator insert(const_iterator p, Args &&...args)
    {
        return insert_impl(p, new value_type(std::forward<Args>(args)...));
    }

    iterator insert(const_iterator pos, size_t count, const value_type &n)
    {
        iterator p(const_cast<value_type *>(&*pos));
        while (count-- > 0)
            p = insert(p, n);
        return p;
    }

    template <typename InputIter>
    iterator insert(const_iterator pos, InputIter first, InputIter last)
    {
        iterator p(const_cast<value_type *>(&*pos));
        iterator result = p;
        bool f = true;
        for (auto i = first; i != last; ++i, ++p)
        {
            p = insert(p, *i);
            if (std::exchange(f, false))
                result = p;
        }
        return result;
    }

    iterator insert(const_iterator pos, std::initializer_list<value_type> nodes)
    {
        return insert(pos, nodes.begin(), nodes.end());
    }

    template <typename InputIter>
    void assign(InputIter first, InputIter last)
    {
        basic_node_list::clear();
        insert(begin(), first, last);
    }

    template <typename... Args>
        requires std::is_same_v<value_type, attribute> or std::is_same_v<value_type, element> or std::is_base_of_v<node, std::remove_cvref_t<Args>...>
    iterator emplace(const_iterator p, Args &&...args)
    {
        return insert(p, std::forward<Args>(args)...);
    }

    template <typename... Args>
        requires std::is_same_v<value_type, attribute> or std::is_same_v<value_type, element> or std::is_base_of_v<node, std::remove_cvref_t<Args>...>
    iterator emplace_front(Args &&...args)
    {
        return emplace(begin(), std::forward<Args>(args)...);
    }

    template <typename... Args>
        requires std::is_same_v<value_type, attribute> or std::is_same_v<value_type, element> or std::is_base_of_v<node, std::remove_cvref_t<Args>...>
    iterator emplace_back(Args &&...args)
    {
        return emplace(end(), std::forward<Args>(args)...);
    }

    iterator erase(const_iterator pos)
    {
        return erase_impl(pos);
    }

    iterator erase(iterator first, iterator last)
    {
        while (first != last)
        {
            auto next = first;
            ++next;

            erase(first);
            first = next;
        }
        return last;
    }

    void pop_front()
    {
        erase(begin());
    }

    void pop_back()
    {
        erase(std::prev(end()));
    }

    void push_front(value_type &&e)
    {
        emplace(begin(), std::move(e));
    }

    void push_front(const value_type &e)
    {
        emplace(begin(), e);
    }

    void push_back(value_type &&e)
    {
        emplace(end(), std::move(e));
    }

    void push_back(const value_type &e)
    {
        emplace(end(), e);
    }

    template <typename Pred>
    void sort(Pred &&pred);

  protected:
    using basic_node_list::insert_impl;

    node *insert_impl(const_iterator pos, node *n)
    {
        return insert_impl(&*pos, n);
    }

    using basic_node_list::erase_impl;

    node *erase_impl(iterator pos)
    {
        return basic_node_list::erase_impl(&*pos);
    }
};

// --------------------------------------------------------------------

class element_container : public node, public node_list<element>
{
  public:

    element_container()
        : node_list<element>(this)
    {
    }

    element_container(const element_container &e)
        : node_list<element>(this)
    {
        auto a = nodes();
        auto b = e.nodes();
        a.assign(b.begin(), b.end());
    }

    ~element_container()
    {
        clear();
    }

    // --------------------------------------------------------------------

    friend void swap(element_container &a, element_container &b) noexcept
    {
        swap(static_cast<node_list<element> &>(a), static_cast<node_list<element> &>(b));
    }
    // --------------------------------------------------------------------
    // children

    node_list<> nodes() { return node_list<node>(this); }

    const node_list<> nodes() const { return node_list<node>(const_cast<element_container *>(this)); }

    std::string str() const override;

    element_set find(std::string_view path) const;

    iterator find_first(std::string_view path);
    const_iterator find_first(std::string_view path) const;

  protected:
    void write(std::ostream &os, format_info fmt) const override;
};

// --------------------------------------------------------------------
// internal node base class for storing text

class node_with_text : public node
{
  protected:
    node_with_text() = default;

    node_with_text(std::string s)
        : m_text(std::move(s))
    {
    }

    node_with_text(const node_with_text &n)
        : m_text(n.m_text)
    {
    }

  public:
    friend void swap(node_with_text &a, node_with_text &b) noexcept
    {
        std::swap(a.m_text, b.m_text);
    }

    std::string str() const override { return m_text; }

    virtual std::string get_text() const { return m_text; }

    virtual void set_text(std::string text) { m_text = std::move(text); }

    bool equals(const node *n) const override
    {
        return type() == n->type() and
               static_cast<const node_with_text *>(n)->m_text == m_text;
    }

  protected:
    std::string m_text;
};

// --------------------------------------------------------------------

class comment final : public node_with_text
{
  public:
    constexpr node_type type() const override { return node_type::comment; }

    comment(std::string text = {})
        : node_with_text(std::move(text))
    {
    }

    comment(const comment &c)
        : node_with_text(c)
    {
    }

    comment(comment &&c) noexcept
    {
        swap(*this, c);
    }

    comment &operator=(comment c) noexcept
    {
        swap(*this, c);
        return *this;
    }

    bool equals(const node *n) const override
    {
        return this == n or (n->type() == node_type::comment and node_with_text::equals(n));
    }

    void write(std::ostream &os, format_info fmt) const override;
};

// --------------------------------------------------------------------
class processing_instruction final : public node_with_text
{
  public:
    constexpr node_type type() const override { return node_type::processing_instruction; }

    processing_instruction() = default;

    processing_instruction(std::string target, std::string text)
        : node_with_text(std::move(text))
        , m_target(std::move(target))
    {
    }

    processing_instruction(const processing_instruction &pi)
        : node_with_text(pi)
        , m_target(pi.m_target)
    {
    }

    processing_instruction(processing_instruction &&pi) noexcept
        : node_with_text(std::move(pi.m_text))
        , m_target(std::move(pi.m_target))
    {
    }

    processing_instruction &operator=(processing_instruction pi) noexcept
    {
        swap(*this, pi);
        return *this;
    }

    friend void swap(processing_instruction &a, processing_instruction &b) noexcept
    {
        swap(static_cast<node_with_text &>(a), static_cast<node_with_text &>(b));
        std::swap(a.m_target, b.m_target);
    }
    std::string get_qname() const override { return m_target; }

    std::string get_target() const { return m_target; }

    void set_target(std::string target) { m_target = std::move(target); }

    bool equals(const node *n) const override
    {
        return this == n or (n->type() == node_type::processing_instruction and node_with_text::equals(n));
    }

    void write(std::ostream &os, format_info fmt) const override;

  private:
    std::string m_target;

};

// --------------------------------------------------------------------
class text final : public node_with_text
{
  public:
    constexpr node_type type() const override { return node_type::text; }

    text(std::string text = {})
        : node_with_text(std::move(text))
    {
    }

    text(const text &t)
        : node_with_text(t)
    {
    }

    text(text &&t) noexcept
        : node_with_text(std::move(t.m_text))
    {
    }

    text &operator=(text txt) noexcept
    {
        swap(*this, txt);
        return *this;
    }

    void append(std::string_view text) { m_text.append(text.begin(), text.end()); }

    bool equals(const node *n) const override;

    bool is_space() const;

    void write(std::ostream &os, format_info fmt) const override;
};

// --------------------------------------------------------------------
class cdata final : public node_with_text
{
  public:
    constexpr node_type type() const override { return node_type::cdata; }

    cdata(std::string s = {})
        : node_with_text(std::move(s))
    {
    }

    cdata(const cdata &cd)
        : node_with_text(cd)
    {
    }

    cdata(cdata &&cd) noexcept
        : node_with_text(std::move(cd))
    {
    }

    cdata &operator=(cdata cd) noexcept
    {
        swap(*this, cd);
        return *this;
    }

    void append(std::string_view text) { m_text.append(text.begin(), text.end()); }

    bool equals(const node *n) const override
    {
        return this == n or (n->type() == node_type::cdata and node_with_text::equals(n));
    }

    void write(std::ostream &os, format_info fmt) const override;
};

// --------------------------------------------------------------------
class attribute final : public node
{
  public:
    constexpr node_type type() const override { return node_type::attribute; }

    attribute(std::string_view qname, std::string_view value, bool id = false)
        : m_qname(qname)
        , m_value(value)
        , m_id(id)
    {
    }

    attribute(const attribute &attr)
        : m_qname(attr.m_qname)
        , m_value(attr.m_value)
        , m_id(attr.m_id)
    {
    }

    attribute(attribute &&attr) noexcept
        : m_qname(std::move(attr.m_qname))
        , m_value(std::move(attr.m_value))
        , m_id(attr.m_id)
    {
    }

    attribute &operator=(attribute attr) noexcept
    {
        swap(*this, attr);
        return *this;
    }

    friend void swap(attribute &a, attribute &b) noexcept
    {
        std::swap(a.m_qname, b.m_qname);
        std::swap(a.m_value, b.m_value);
        std::swap(a.m_id, b.m_id);
    }
    friend std::strong_ordering operator<=>(const attribute &a, const attribute &b)
    {
        if (auto cmp = (a.m_qname <=> b.m_qname); cmp != 0)
            return cmp;
        if (auto cmp = (a.m_id <=> b.m_id); cmp != 0)
            return cmp;
        return a.m_value <=> b.m_value;
    }

    bool operator==(const attribute &rhs) const
    {
        return equals(&rhs);
    }

    std::string get_qname() const override { return m_qname; }

    void set_qname(std::string qn) override { m_qname = std::move(qn); }

    using node::set_qname;

    bool is_namespace() const
    {
        return m_qname.compare(0, 5, "xmlns") == 0 and (m_qname[5] == 0 or m_qname[5] == ':');
    }

    std::string value() const { return m_value; }

    void set_value(std::string v) { m_value = std::move(v); }

    std::string uri() const;

    std::string str() const override { return m_value; }

    bool equals(const node *n) const override
    {
        bool result = false;
        if (type() == n->type())
        {
            auto an = static_cast<const attribute *>(n);
            result = an->m_id == m_id and an->m_qname == m_qname and an->m_value == m_value;
        }
        return result;
    }

    bool is_id() const { return m_id; }

    template <size_t N>
    decltype(auto) get() const
    {
        if constexpr (N == 0)
            return name();
        else if constexpr (N == 1)
            return value();
    }

    void write(std::ostream &os, format_info fmt) const override;

  private:
    std::string m_qname, m_value;
    bool m_id;
};

// --------------------------------------------------------------------
class attribute_set : public node_list<attribute>
{
  public:
    attribute_set(element_container *el)
        : node_list(el)
    {
    }

    ~attribute_set()
    {
        clear();
    }

    friend void swap(attribute_set &a, attribute_set &b) noexcept
    {
        swap(static_cast<node_list<attribute> &>(a), static_cast<node_list<attribute> &>(b));
    }
    bool contains(std::string_view key) const
    {
        return find(key) != end();
    }

    const_iterator find(std::string_view key) const
    {
        for (auto i = begin(); i != end(); ++i)
        {
            if (i->get_qname() == key)
                return i;
        }
        return end();
    }

    iterator find(std::string_view key)
    {
        return const_cast<const attribute_set &>(*this).find(key);
    }

    template <typename... Args>
    std::pair<iterator, bool> emplace(Args... args)
    {
        value_type a(std::forward<Args>(args)...);
        return emplace(std::move(a));
    }

    std::pair<iterator, bool> emplace(value_type &&a)
    {
        bool inserted = false;

        auto i = find(a.get_qname());

        if (i != node_list::end())
            *i = std::move(a); // move assign value of a
        else
        {
            i = node_list::insert_impl(node_list::end(), new attribute(std::move(a)));
            inserted = true;
        }

        return std::make_pair(i, inserted);
    }

    using node_list::erase;

    size_type erase(std::string_view key)
    {
        size_type result = 0;
        auto i = find(key);
        if (i != node_list::end())
        {
            erase(i);
            result = 1;
        }
        return result;
    }
};

// --------------------------------------------------------------------
class element final : public element_container
{
  public:
    constexpr node_type type() const override { return node_type::element; }

    element()
        : m_attributes(this)
    {
    }

    element(std::string_view qname, std::initializer_list<attribute> attributes = {})
        : m_qname(qname)
        , m_attributes(this)
    {
        m_attributes.assign(attributes.begin(), attributes.end());
    }

    element(std::string_view qname, std::initializer_list<element> il)
        : m_qname(qname)
        , m_attributes(this)
    {
        assign(il.begin(), il.end());
    }

    element(const element &e)
        : element_container(e)
        , m_qname(e.m_qname)
        , m_attributes(this)
    {
        m_attributes.assign(e.m_attributes.begin(), e.m_attributes.end());
    }

    element(element &&e) noexcept
        : m_attributes(this)
    {
        swap(*this, e);
    }

    element &operator=(element e) noexcept
    {
        swap(*this, e);
        return *this;
    }

    friend void swap(element &a, element &b) noexcept
    {
        // swap(static_cast<node&>(a), static_cast<node&>(b));
        swap(static_cast<element_container &>(a), static_cast<element_container &>(b));

        std::swap(a.m_qname, b.m_qname);
        swap(a.m_attributes, b.m_attributes);
    }
    using node::set_qname;

    std::string get_qname() const override { return m_qname; }

    void set_qname(std::string qn) override { m_qname = std::move(qn); }

    std::string lang() const override;

    std::string id() const;

    bool operator==(const element &e) const
    {
        return equals(&e);
    }

    bool equals(const node *n) const override;

    // --------------------------------------------------------------------
    // attribute support

    attribute_set &attributes() { return m_attributes; }

    const attribute_set &attributes() const { return m_attributes; }

    // --------------------------------------------------------------------

    std::string namespace_for_prefix(std::string_view prefix) const override;

    std::pair<std::string, bool> prefix_for_namespace(std::string_view uri) const override;

    void move_to_name_space(std::string prefix, std::string uri,
        bool recursive, bool including_attributes);

    // --------------------------------------------------------------------

    friend std::ostream &operator<<(std::ostream &os, const element &e);
    //  friend class document;

    std::string get_content() const;

    void set_content(std::string content);

    std::string get_attribute(std::string_view qname) const;

    void set_attribute(std::string_view qname, std::string_view value);

    virtual void set_text(std::string s);

    void add_text(std::string s);

    void flatten_text();

    void write(std::ostream &os, format_info fmt) const override;

  private:
    std::string m_qname;
    attribute_set m_attributes;
};

// --------------------------------------------------------------------
template <typename T>
inline node_list<T>::node_list(element_container *e)
    : basic_node_list(e)
{
    if constexpr (std::is_same_v<value_type, node>)
        m_header = e->m_header;
}

template <>
inline auto node_list<node>::insert(const_iterator pos, const value_type &e) -> iterator
{
    switch (e.type())
    {
        case node_type::element:
            return insert_impl(pos, new element(static_cast<const element &>(e)));
            break;
        case node_type::text:
            return insert_impl(pos, new text(static_cast<const text &>(e)));
            break;
        case node_type::attribute:
            return insert_impl(pos, new attribute(static_cast<const attribute &>(e)));
            break;
        case node_type::comment:
            return insert_impl(pos, new comment(static_cast<const comment &>(e)));
            break;
        case node_type::cdata:
            return insert_impl(pos, new cdata(static_cast<const cdata &>(e)));
            break;
        case node_type::processing_instruction:
            return insert_impl(pos, new processing_instruction(static_cast<const processing_instruction &>(e)));
            break;
        default:
            throw exception("internal error");
    }
}

template <>
inline auto node_list<node>::insert(const_iterator pos, value_type &&e) -> iterator
{
    switch (e.type())
    {
        case node_type::element:
            return insert_impl(pos, new element(static_cast<element &&>(e)));
            break;
        case node_type::text:
            return insert_impl(pos, new text(static_cast<text &&>(e)));
            break;
        case node_type::attribute:
            return insert_impl(pos, new attribute(static_cast<attribute &&>(e)));
            break;
        case node_type::comment:
            return insert_impl(pos, new comment(static_cast<comment &&>(e)));
            break;
        case node_type::cdata:
            return insert_impl(pos, new cdata(static_cast<cdata &&>(e)));
            break;
        case node_type::processing_instruction:
            return insert_impl(pos, new processing_instruction(static_cast<processing_instruction &&>(e)));
            break;
        default:
            throw exception("internal error");
    }
}

template <typename T>
template <typename Pred>
void node_list<T>::sort(Pred &&pred)
{
    std::vector<node *> t;
    for (auto n = m_header->m_next; n != m_header; n = n->m_next)
        t.push_back(n);

    std::sort(t.begin(), t.end(), [pred](node *a, node *b) { return pred(static_cast<T&>(*a), static_cast<T&>(*b)); });

    auto p = m_header;
    for (auto n : t)
    {
        n->m_prev = p;
        p->m_next = n;
        p = n;
    }
    p->m_next = m_header;
    m_header->m_prev = p;
}

// --------------------------------------------------------------------

void fix_namespaces(element &e, const element &source, const element &dest);

} // namespace mxml

// --------------------------------------------------------------------
// structured binding support
namespace std
{

template <>
struct tuple_size<::mxml::attribute>
    : public std::integral_constant<std::size_t, 2>
{
};

template <>
struct tuple_element<0, ::mxml::attribute>
{
    using type = decltype(std::declval<::mxml::attribute>().name());
};

template <>
struct tuple_element<1, ::mxml::attribute>
{
    using type = decltype(std::declval<::mxml::attribute>().value());
};

} // namespace std