/*
   +----------------------------------------------------------------------+
   | Copyright (c) The PHP Group                                          |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | https://www.php.net/license/3_01.txt                                 |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
   | Authors: Nora Dossche  <ndossche@php.net>                            |
   +----------------------------------------------------------------------+
*/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "php.h"
#if defined(HAVE_LIBXML) && defined(HAVE_DOM)
#include "php_dom.h"
#include "namespace_compat.h"
#include "private_data.h"
#include "internal_helpers.h"

/* The actual value of these doesn't matter as long as they serve as a unique ID.
 * They need to be pointers because the `_private` field is a pointer, however we can choose the contents ourselves.
 * We need keep these at least 4-byte aligned because the pointer may be tagged (although for now 2 byte alignment works too).
 * We use a trick: we declare a struct with a double member to force the alignment. */
#define DECLARE_NS_TOKEN(name, uri)			\
	static const struct {                   \
		char val[sizeof(uri)];				\
		double align;						\
	} decl_##name = { uri, 0.0 };			\
	PHP_DOM_EXPORT const php_dom_ns_magic_token *(name) = (const php_dom_ns_magic_token *) &decl_##name;
DECLARE_NS_TOKEN(php_dom_ns_is_html_magic_token, DOM_XHTML_NS_URI);
DECLARE_NS_TOKEN(php_dom_ns_is_mathml_magic_token, DOM_MATHML_NS_URI);
DECLARE_NS_TOKEN(php_dom_ns_is_svg_magic_token, DOM_SVG_NS_URI);
DECLARE_NS_TOKEN(php_dom_ns_is_xlink_magic_token, DOM_XLINK_NS_URI);
DECLARE_NS_TOKEN(php_dom_ns_is_xml_magic_token, DOM_XML_NS_URI);
DECLARE_NS_TOKEN(php_dom_ns_is_xmlns_magic_token, DOM_XMLNS_NS_URI);

static void php_dom_libxml_ns_mapper_prefix_map_element_dtor(zval *zv)
{
	if (DOM_Z_IS_OWNED(zv)) {
		efree(Z_PTR_P(zv));
	}
}

static HashTable *php_dom_libxml_ns_mapper_ensure_prefix_map(php_dom_libxml_ns_mapper *mapper, zend_string **uri)
{
	zval *zv = zend_hash_find(&mapper->uri_to_prefix_map, *uri);
	HashTable *prefix_map;
	if (zv == NULL) {
		prefix_map = emalloc(sizeof(HashTable));
		zend_hash_init(prefix_map, 0, NULL, php_dom_libxml_ns_mapper_prefix_map_element_dtor, false);
		zval zv_prefix_map;
		ZVAL_ARR(&zv_prefix_map, prefix_map);
		zend_hash_add_new(&mapper->uri_to_prefix_map, *uri, &zv_prefix_map);
	} else {
		/* cast to Bucket* only works if this holds, I would prefer a static assert but we're stuck at C99. */
		ZEND_ASSERT(XtOffsetOf(Bucket, val) == 0);
		ZEND_ASSERT(Z_TYPE_P(zv) == IS_ARRAY);
		Bucket *bucket = (Bucket *) zv;
		/* Make sure we take the value from the key string that lives long enough. */
		*uri = bucket->key;
		prefix_map = Z_ARRVAL_P(zv);
	}
	return prefix_map;
}

static xmlNsPtr php_dom_libxml_ns_mapper_ensure_cached_ns(php_dom_libxml_ns_mapper *mapper, xmlNsPtr *ptr, const char *uri, size_t length, const php_dom_ns_magic_token *token)
{
	if (EXPECTED(*ptr != NULL)) {
		return *ptr;
	}

	zend_string *uri_str = zend_string_init(uri, length, false);
	*ptr = php_dom_libxml_ns_mapper_get_ns(mapper, NULL, uri_str);
	(*ptr)->_private = (void *) token;
	zend_string_release_ex(uri_str, false);
	return *ptr;
}

PHP_DOM_EXPORT xmlNsPtr php_dom_libxml_ns_mapper_ensure_html_ns(php_dom_libxml_ns_mapper *mapper)
{
	return php_dom_libxml_ns_mapper_ensure_cached_ns(mapper, &mapper->html_ns, DOM_XHTML_NS_URI, sizeof(DOM_XHTML_NS_URI) - 1, php_dom_ns_is_html_magic_token);
}

PHP_DOM_EXPORT xmlNsPtr php_dom_libxml_ns_mapper_ensure_prefixless_xmlns_ns(php_dom_libxml_ns_mapper *mapper)
{
	return php_dom_libxml_ns_mapper_ensure_cached_ns(mapper, &mapper->prefixless_xmlns_ns, DOM_XMLNS_NS_URI, sizeof(DOM_XMLNS_NS_URI) - 1, php_dom_ns_is_xmlns_magic_token);
}

static xmlNsPtr dom_create_owned_ns(zend_string *prefix, zend_string *uri)
{
	ZEND_ASSERT(prefix != NULL);
	ZEND_ASSERT(uri != NULL);

	xmlNsPtr ns = emalloc(sizeof(*ns));
	memset(ns, 0, sizeof(*ns));
	ns->type = XML_LOCAL_NAMESPACE;
	/* These two strings are kept alive because they're the hash table keys that lead to this entry. */
	ns->prefix = ZSTR_LEN(prefix) == 0 ? NULL : BAD_CAST ZSTR_VAL(prefix);
	ns->href = BAD_CAST ZSTR_VAL(uri);
	/* Note ns->context is unused in libxml2 at the moment, and if it were used it would be for
	 * LIBXML_NAMESPACE_DICT which is opt-in anyway. */

	return ns;
}

PHP_DOM_EXPORT xmlNsPtr php_dom_libxml_ns_mapper_get_ns(php_dom_libxml_ns_mapper *mapper, zend_string *prefix, zend_string *uri)
{
	if (uri == NULL) {
		uri = zend_empty_string;
	}

	if (prefix == NULL) {
		prefix = zend_empty_string;
	}

	if (ZSTR_LEN(prefix) == 0 && ZSTR_LEN(uri) == 0) {
		return NULL;
	}

	HashTable *prefix_map = php_dom_libxml_ns_mapper_ensure_prefix_map(mapper, &uri);
	xmlNsPtr found = zend_hash_find_ptr(prefix_map, prefix);
	if (found != NULL) {
		return found;
	}

	xmlNsPtr ns = dom_create_owned_ns(prefix, uri);

	zval new_zv;
	DOM_Z_OWNED(&new_zv, ns);
	zend_hash_add_new(prefix_map, prefix, &new_zv);

	return ns;
}

PHP_DOM_EXPORT xmlNsPtr php_dom_libxml_ns_mapper_get_ns_raw_prefix_string(php_dom_libxml_ns_mapper *mapper, const xmlChar *prefix, size_t prefix_len, zend_string *uri)
{
	xmlNsPtr ns;
	if (prefix_len == 0) {
		/* Fast path */
		ns = php_dom_libxml_ns_mapper_get_ns(mapper, zend_empty_string, uri);
	} else {
		zend_string *prefix_str = zend_string_init((const char *) prefix, prefix_len, false);
		ns = php_dom_libxml_ns_mapper_get_ns(mapper, prefix_str, uri);
		zend_string_release_ex(prefix_str, false);
	}
	return ns;
}

static xmlNsPtr php_dom_libxml_ns_mapper_get_ns_raw_strings_ex(php_dom_libxml_ns_mapper *mapper, const char *prefix, size_t prefix_len, const char *uri, size_t uri_len)
{
	zend_string *prefix_str = zend_string_init(prefix, prefix_len, false);
	zend_string *uri_str = zend_string_init(uri, uri_len, false);
	xmlNsPtr ns = php_dom_libxml_ns_mapper_get_ns(mapper, prefix_str, uri_str);
	zend_string_release_ex(prefix_str, false);
	zend_string_release_ex(uri_str, false);
	return ns;
}

static zend_always_inline xmlNsPtr php_dom_libxml_ns_mapper_get_ns_raw_strings(php_dom_libxml_ns_mapper *mapper, const char *prefix, const char *uri)
{
	return php_dom_libxml_ns_mapper_get_ns_raw_strings_ex(mapper, prefix, strlen(prefix), uri, strlen(uri));
}

PHP_DOM_EXPORT xmlNsPtr php_dom_libxml_ns_mapper_get_ns_raw_strings_nullsafe(php_dom_libxml_ns_mapper *mapper, const char *prefix, const char *uri)
{
	if (prefix == NULL) {
		prefix = "";
	}
	if (uri == NULL) {
		uri = "";
	}
	return php_dom_libxml_ns_mapper_get_ns_raw_strings(mapper, prefix, uri);
}

static void php_dom_libxml_ns_mapper_store_and_normalize_parsed_ns(php_dom_libxml_ns_mapper *mapper, xmlNsPtr ns)
{
	ZEND_ASSERT(ns != NULL);

	zend_string *href_str = zend_string_init((const char *) ns->href, xmlStrlen(ns->href), false);
	zend_string *href_str_orig = href_str;
	HashTable *prefix_map = php_dom_libxml_ns_mapper_ensure_prefix_map(mapper, &href_str);
	zend_string_release_ex(href_str_orig, false);

	const char *prefix = (const char *) ns->prefix;
	size_t prefix_len;
	if (prefix == NULL) {
		prefix = "";
		prefix_len = 0;
	} else {
		prefix_len = xmlStrlen(ns->prefix);
	}

	zval new_zv;
	DOM_Z_UNOWNED(&new_zv, ns);
	zend_hash_str_add(prefix_map, prefix, prefix_len, &new_zv);
}

typedef struct {
	/* Fast lookup for created mappings. */
	HashTable old_ns_to_new_ns_ptr;
	/* It is common that the last created mapping will be used for a while,
	 * cache it too to bypass the hash table. */
	xmlNsPtr last_mapped_src, last_mapped_dst;
	php_dom_libxml_ns_mapper *ns_mapper;
} dom_libxml_reconcile_ctx;

PHP_DOM_EXPORT php_dom_libxml_ns_mapper *php_dom_get_ns_mapper(dom_object *object)
{
	return &php_dom_get_private_data(object)->ns_mapper;
}

PHP_DOM_EXPORT xmlAttrPtr php_dom_ns_compat_mark_attribute(php_dom_libxml_ns_mapper *mapper, xmlNodePtr node, xmlNsPtr ns)
{
	xmlNsPtr xmlns_ns;
	const xmlChar *name;
	if (ns->prefix != NULL) {
		xmlns_ns = php_dom_libxml_ns_mapper_get_ns_raw_strings(mapper, "xmlns", DOM_XMLNS_NS_URI);
		name = ns->prefix;
	} else {
		xmlns_ns = php_dom_libxml_ns_mapper_ensure_prefixless_xmlns_ns(mapper);
		name = BAD_CAST "xmlns";
	}

	ZEND_ASSERT(xmlns_ns != NULL);

	return xmlSetNsProp(node, xmlns_ns, name, ns->href);
}

PHP_DOM_EXPORT void php_dom_ns_compat_mark_attribute_list(php_dom_libxml_ns_mapper *mapper, xmlNodePtr node)
{
	if (node->nsDef == NULL) {
		return;
	}

	/* We want to prepend at the front, but in order of the namespace definitions.
	 * So temporarily unlink the existing properties and add them again at the end. */
	xmlAttrPtr attr = node->properties;
	node->properties = NULL;

	xmlNsPtr ns = node->nsDef;
	xmlAttrPtr last_added = NULL;
	do {
		last_added = php_dom_ns_compat_mark_attribute(mapper, node, ns);
		php_dom_libxml_ns_mapper_store_and_normalize_parsed_ns(mapper, ns);
		xmlNsPtr next = ns->next;
		ns->next = NULL;
		php_libxml_set_old_ns(node->doc, ns);
		ns = next;
	} while (ns != NULL);

	if (last_added != NULL) {
		/* node->properties now points to the first namespace declaration attribute. */
		if (attr != NULL) {
			last_added->next = attr;
			attr->prev = last_added;
		}
	} else {
		/* Nothing added, so nothing changed. Only really possible on OOM. */
		node->properties = attr;
	}

	node->nsDef = NULL;
}

PHP_DOM_EXPORT bool php_dom_ns_is_fast_ex(xmlNsPtr ns, const php_dom_ns_magic_token *magic_token)
{
	ZEND_ASSERT(ns != NULL);
	/* cached for fast checking */
	if (ns->_private == magic_token) {
		return true;
	} else if (ns->_private != NULL && ((uintptr_t) ns->_private & 1) == 0) {
		/* Other token stored */
		return false;
	}
	/* Slow path */
	if (xmlStrEqual(ns->href, BAD_CAST magic_token)) {
		if (ns->_private == NULL) {
			/* Only overwrite the private data if there is no other token stored. */
			ns->_private = (void *) magic_token;
		}
		return true;
	}
	return false;
}

PHP_DOM_EXPORT bool php_dom_ns_is_fast(const xmlNode *nodep, const php_dom_ns_magic_token *magic_token)
{
	ZEND_ASSERT(nodep != NULL);
	xmlNsPtr ns = nodep->ns;
	if (ns != NULL) {
		return php_dom_ns_is_fast_ex(ns, magic_token);
	}
	return false;
}

PHP_DOM_EXPORT bool php_dom_ns_is_html_and_document_is_html(const xmlNode *nodep)
{
	ZEND_ASSERT(nodep != NULL);
	return nodep->doc && nodep->doc->type == XML_HTML_DOCUMENT_NODE && php_dom_ns_is_fast(nodep, php_dom_ns_is_html_magic_token);
}

/* will rename prefixes if there is a declaration with the same prefix but different uri. */
PHP_DOM_EXPORT void php_dom_reconcile_attribute_namespace_after_insertion(xmlAttrPtr attrp)
{
	ZEND_ASSERT(attrp != NULL);

	if (attrp->ns != NULL) {
		/* Try to link to an existing namespace. If that won't work, reconcile. */
		xmlNodePtr nodep = attrp->parent;
		xmlNsPtr matching_ns = xmlSearchNs(nodep->doc, nodep, attrp->ns->prefix);
		if (matching_ns && xmlStrEqual(matching_ns->href, attrp->ns->href)) {
			/* Doesn't leak because this doesn't define the declaration. */
			attrp->ns = matching_ns;
		} else {
			if (attrp->ns->prefix != NULL) {
				/* Note: explicitly use the legacy reconciliation as it mostly (i.e. as good as it gets for legacy DOM)
				* does the right thing for attributes. */
				xmlReconciliateNs(nodep->doc, nodep);
			}
		}
	}
}

static zend_always_inline void php_dom_libxml_reconcile_modern_single_node(dom_libxml_reconcile_ctx *ctx, xmlNodePtr node)
{
	ZEND_ASSERT(node->ns != NULL);

	if (node->ns == ctx->last_mapped_src) {
		node->ns = ctx->last_mapped_dst;
		return;
	}

	/* If the namespace is the same as in the map, we're good. */
	xmlNsPtr new_ns = zend_hash_index_find_ptr(&ctx->old_ns_to_new_ns_ptr, dom_mangle_pointer_for_key(node->ns));
	if (new_ns == NULL) {
		/* We have to create an alternative declaration, and we'll add it to the map. */
		const char *prefix = (const char *) node->ns->prefix;
		const char *href = (const char *) node->ns->href;
		new_ns = php_dom_libxml_ns_mapper_get_ns_raw_strings_nullsafe(ctx->ns_mapper, prefix, href);
		zend_hash_index_add_new_ptr(&ctx->old_ns_to_new_ns_ptr, dom_mangle_pointer_for_key(node->ns), new_ns);
		ctx->last_mapped_src = node->ns;
		ctx->last_mapped_dst = new_ns;
		node->ns = new_ns;
	} else if (node->ns != new_ns) {
		/* The namespace is different, so we have to replace it. */
		node->ns = new_ns;
	}
}

static zend_always_inline bool dom_libxml_reconcile_fast_element_skip(xmlNodePtr node)
{
	/* Fast path: this is a lone element and the namespace is defined by the node (or the namespace is NULL). */
	ZEND_ASSERT(node->type == XML_ELEMENT_NODE);
	return node->children == NULL && node->properties == NULL && node->ns == node->nsDef;
}

static zend_always_inline void php_dom_libxml_reconcile_modern_single_element_node(dom_libxml_reconcile_ctx *ctx, xmlNodePtr node)
{
	ZEND_ASSERT(node->type == XML_ELEMENT_NODE);

	/* Since this is modern DOM, the declarations are not on the node and thus there's nothing to add from nsDef. */
	ZEND_ASSERT(node->nsDef == NULL);

	if (node->ns != NULL) {
		php_dom_libxml_reconcile_modern_single_node(ctx, node);
	}

	for (xmlAttrPtr attr = node->properties; attr != NULL; attr = attr->next) {
		if (attr->ns != NULL) {
			php_dom_libxml_reconcile_modern_single_node(ctx, (xmlNodePtr) attr);
		}
	}
}

PHP_DOM_EXPORT void php_dom_libxml_reconcile_modern(php_dom_libxml_ns_mapper *ns_mapper, xmlNodePtr node)
{
	if (node->type == XML_ATTRIBUTE_NODE) {
		if (node->ns != NULL) {
			node->ns = php_dom_libxml_ns_mapper_get_ns_raw_strings_nullsafe(ns_mapper, (const char *) node->ns->prefix, (const char *) node->ns->href);
		}
		return;
	}

	if (node->type != XML_ELEMENT_NODE || dom_libxml_reconcile_fast_element_skip(node)) {
		return;
	}

	dom_libxml_reconcile_ctx ctx;
	zend_hash_init(&ctx.old_ns_to_new_ns_ptr, 0, NULL, NULL, 0);
	ctx.last_mapped_src = NULL;
	ctx.last_mapped_dst = NULL;
	ctx.ns_mapper = ns_mapper;

	php_dom_libxml_reconcile_modern_single_element_node(&ctx, node);

	xmlNodePtr base = node;
	node = node->children;
	while (node != NULL) {
		ZEND_ASSERT(node != base);

		if (node->type == XML_ELEMENT_NODE) {
			php_dom_libxml_reconcile_modern_single_element_node(&ctx, node);
		}

		node = php_dom_next_in_tree_order(node, base);
	}

	zend_hash_destroy(&ctx.old_ns_to_new_ns_ptr);
}

PHP_DOM_EXPORT php_dom_in_scope_ns php_dom_get_in_scope_ns(php_dom_libxml_ns_mapper *ns_mapper, const xmlNode *node, bool ignore_elements)
{
	ZEND_ASSERT(node != NULL);

	php_dom_in_scope_ns in_scope_ns;
	in_scope_ns.origin_is_ns_compat = true;

	/* libxml fetches all nsDef items from bottom to top - left to right, ignoring prefixes already in the list.
	 * We don't have nsDef, but we can use the ns pointer (as that is necessarily in scope),
	 * and check the xmlns attributes. */
	HashTable tmp_prefix_to_ns_table;
	zend_hash_init(&tmp_prefix_to_ns_table, 0, NULL, NULL, false);
	zend_hash_real_init_mixed(&tmp_prefix_to_ns_table);

	for (const xmlNode *cur = node; cur != NULL; cur = cur->parent) {
		if (cur->type == XML_ELEMENT_NODE) {
			/* Register namespace of element */
			if (!ignore_elements && cur->ns != NULL && cur->ns->prefix != NULL) {
				const char *prefix = (const char *) cur->ns->prefix;
				zend_hash_str_add_ptr(&tmp_prefix_to_ns_table, prefix, strlen(prefix), cur->ns);
			}

			/* Register xmlns attributes */
			for (const xmlAttr *attr = cur->properties; attr != NULL; attr = attr->next) {
				if (attr->ns != NULL && attr->ns->prefix != NULL && php_dom_ns_is_fast_ex(attr->ns, php_dom_ns_is_xmlns_magic_token)
					&& attr->children != NULL && attr->children->content != NULL) {
					/* This attribute declares a namespace, get the relevant instance.
					 * The declared namespace is not the same as the namespace of this attribute (which is xmlns). */
					const char *prefix = (const char *) attr->name;
					xmlNsPtr ns = php_dom_libxml_ns_mapper_get_ns_raw_strings(ns_mapper, prefix, (const char *) attr->children->content);
					zend_hash_str_add_ptr(&tmp_prefix_to_ns_table, prefix, strlen(prefix), ns);
				}
			}
		}
	}

	in_scope_ns.count = zend_hash_num_elements(&tmp_prefix_to_ns_table);
	in_scope_ns.list = safe_emalloc(in_scope_ns.count, sizeof(xmlNsPtr), 0);

	size_t index = 0;
	xmlNsPtr ns;
	ZEND_HASH_MAP_FOREACH_PTR(&tmp_prefix_to_ns_table, ns) {
		in_scope_ns.list[index++] = ns;
	} ZEND_HASH_FOREACH_END();

	zend_hash_destroy(&tmp_prefix_to_ns_table);

	return in_scope_ns;
}

PHP_DOM_EXPORT php_dom_in_scope_ns php_dom_get_in_scope_ns_legacy(const xmlNode *node)
{
	ZEND_ASSERT(node != NULL);

	php_dom_in_scope_ns in_scope_ns;
	in_scope_ns.origin_is_ns_compat = false;
	in_scope_ns.list = xmlGetNsList(node->doc, node);
	in_scope_ns.count = 0;

	if (in_scope_ns.list != NULL) {
		while (in_scope_ns.list[in_scope_ns.count] != NULL) {
			in_scope_ns.count++;
		}
	}

	return in_scope_ns;
}

PHP_DOM_EXPORT void php_dom_in_scope_ns_destroy(php_dom_in_scope_ns *in_scope_ns)
{
	ZEND_ASSERT(in_scope_ns != NULL);
	if (in_scope_ns->origin_is_ns_compat) {
		efree(in_scope_ns->list);
	} else {
		xmlFree(in_scope_ns->list);
	}
}

static xmlNsPtr dom_alloc_ns_decl(HashTable *links, xmlNodePtr node)
{
	xmlNsPtr ns = xmlMalloc(sizeof(*ns));
	if (!ns) {
		return NULL;
	}

	zval *zv = zend_hash_index_lookup(links, (zend_ulong) node);
	if (Z_ISNULL_P(zv)) {
		ZVAL_LONG(zv, 1);
	} else {
		Z_LVAL_P(zv)++;
	}

	memset(ns, 0, sizeof(*ns));
	ns->type = XML_LOCAL_NAMESPACE;
	ns->next = node->nsDef;
	node->nsDef = ns;

	return ns;
}

/* Mint a temporary nsDef entry so C14N finds namespaces that live on node->ns
 * but have no matching xmlns attribute (typical for createElementNS). */
static void dom_add_synthetic_ns_decl(HashTable *links, xmlNodePtr node, xmlNsPtr src_ns)
{
	xmlNsPtr ns = dom_alloc_ns_decl(links, node);
	if (!ns) {
		return;
	}

	ns->href = xmlStrdup(src_ns->href);
	ns->prefix = src_ns->prefix ? xmlStrdup(src_ns->prefix) : NULL;
}

/* Same, but for attribute namespaces, which may collide by prefix with the
 * element's own ns or with a sibling attribute's ns. */
static void dom_add_synthetic_ns_decl_for_attr(HashTable *links, xmlNodePtr node, xmlNsPtr src_ns)
{
	for (xmlNsPtr existing = node->nsDef; existing; existing = existing->next) {
		if (xmlStrEqual(existing->prefix, src_ns->prefix)) {
			return;
		}
	}

	dom_add_synthetic_ns_decl(links, node, src_ns);
}

static void dom_relink_ns_decls_element(HashTable *links, xmlNodePtr node)
{
	if (node->type == XML_ELEMENT_NODE) {
		for (xmlAttrPtr attr = node->properties; attr; attr = attr->next) {
			if (php_dom_ns_is_fast((const xmlNode *) attr, php_dom_ns_is_xmlns_magic_token)) {
				xmlNsPtr ns = dom_alloc_ns_decl(links, node);
				if (!ns) {
					return;
				}

				bool should_free;
				xmlChar *attr_value = php_libxml_attr_value(attr, &should_free);

				ns->href = should_free ? attr_value : xmlStrdup(attr_value);
				ns->prefix = attr->ns->prefix ? xmlStrdup(attr->name) : NULL;
				ns->_private = attr;
				if (attr->prev) {
					attr->prev->next = attr->next;
				} else {
					node->properties = attr->next;
				}
				if (attr->next) {
					attr->next->prev = attr->prev;
				}
			}
		}

		/* The default namespace is handled separately from the other namespaces in C14N.
		 * The default namespace is explicitly looked up while the other namespaces are
		 * deduplicated and compared to a list of visible namespaces. */
		if (node->ns && !node->ns->prefix) {
			/* Workaround for the behaviour where the xmlSearchNs() call inside c14n.c
			 * can return the current namespace. */
			zend_hash_index_add_new_ptr(links, (zend_ulong) node | 1, node->ns);
			node->ns = xmlSearchNs(node->doc, node, NULL);
		} else if (node->ns) {
			dom_add_synthetic_ns_decl(links, node, node->ns);
		}

		for (xmlAttrPtr attr = node->properties; attr; attr = attr->next) {
			if (attr->ns && !php_dom_ns_is_fast((const xmlNode *) attr, php_dom_ns_is_xmlns_magic_token)) {
				dom_add_synthetic_ns_decl_for_attr(links, node, attr->ns);
			}
		}
	}
}

void dom_relink_ns_decls(HashTable *links, xmlNodePtr root)
{
	dom_relink_ns_decls_element(links, root);

	xmlNodePtr base = root;
	xmlNodePtr node = base->children;
	while (node != NULL) {
		dom_relink_ns_decls_element(links, node);
		node = php_dom_next_in_tree_order(node, base);
	}
}

void dom_unlink_ns_decls(HashTable *links)
{
	ZEND_HASH_MAP_FOREACH_NUM_KEY_VAL(links, zend_ulong h, zval *data) {
		if (h & 1) {
			xmlNodePtr node = (xmlNodePtr) (h ^ 1);
			node->ns = Z_PTR_P(data);
		} else {
			xmlNodePtr node = (xmlNodePtr) h;
			while (Z_LVAL_P(data)-- > 0) {
				xmlNsPtr ns = node->nsDef;
				node->nsDef = ns->next;

				xmlAttrPtr attr = ns->_private;
				if (attr) {
					if (attr->prev) {
						attr->prev->next = attr;
					} else {
						node->properties = attr;
					}
					if (attr->next) {
						attr->next->prev = attr;
					}
				}

				xmlFreeNs(ns);
			}
		}
	} ZEND_HASH_FOREACH_END();
}


#endif  /* HAVE_LIBXML && HAVE_DOM */
