Make tree2 perform reference counting.

Fix bits of the treebuilder to perform reference counting correctly in the face of *result not pointing to the same object as the node passed in to the treebuilder client callbacks.

svn path=/trunk/hubbub/; revision=4666

8 files changed, 320 insertions, 65 deletions

diff --git a/src/treebuilder/before_html.c b/src/treebuilder/before_html.c
index ebfc92f..8401087 100644
--- a/src/treebuilder/before_html.c
+++ b/src/treebuilder/before_html.c
@@ -104,21 +104,21 @@ bool handle_before_html(hubbub_treebuilder *treebuilder,
 					html);
 		}
 
+		treebuilder->tree_handler->unref_node(
+				treebuilder->tree_handler->ctx,
+				html);
+
 		/* We can't use element_stack_push() here, as it 
 		 * assumes that current_node is pointing at the index 
 		 * before the one to insert at. For the first entry in 
 		 * the stack, this does not hold so we must insert
 		 * manually. */
 		treebuilder->context.element_stack[0].type = HTML;
-		treebuilder->context.element_stack[0].node = html;
+		treebuilder->context.element_stack[0].node = appended;
 		treebuilder->context.current_node = 0;
 
 		/** \todo cache selection algorithm */
 
-		treebuilder->tree_handler->unref_node(
-				treebuilder->tree_handler->ctx,
-				appended);
-
 		treebuilder->context.mode = BEFORE_HEAD;
 	}
 
diff --git a/src/treebuilder/in_body.c b/src/treebuilder/in_body.c
index 566ef01..57b346d 100644
--- a/src/treebuilder/in_body.c
+++ b/src/treebuilder/in_body.c
@@ -90,7 +90,7 @@ static bool aa_find_furthest_block(hubbub_treebuilder *treebuilder,
 		formatting_list_entry *formatting_element, 
 		uint32_t *furthest_block);
 static void aa_remove_from_parent(hubbub_treebuilder *treebuilder, void *node);
-static void aa_reparent_node(hubbub_treebuilder *treebuilder, void *node, 
+static void *aa_reparent_node(hubbub_treebuilder *treebuilder, void *node, 
 		void *new_parent);
 static void aa_find_bookmark_location_reparenting_misnested(
 		hubbub_treebuilder *treebuilder, 
@@ -1329,17 +1329,43 @@ void process_0presentational_in_body(hubbub_treebuilder *treebuilder,
 				&bookmark, &last_node);
 
 		/* 8 */
+		void *reparented;
+
 		if (stack[common_ancestor].type == TABLE ||
 				stack[common_ancestor].type == TBODY ||
 				stack[common_ancestor].type == TFOOT ||
 				stack[common_ancestor].type == THEAD ||
 				stack[common_ancestor].type == TR) {
-			aa_insert_into_foster_parent(treebuilder,
+			reparented = aa_insert_into_foster_parent(treebuilder,
 					stack[last_node].node);
 		} else {
-			aa_reparent_node(treebuilder, stack[last_node].node,
+			reparented = aa_reparent_node(treebuilder, 
+					stack[last_node].node,
 					stack[common_ancestor].node);
 		}
+		/* If the reparented node is not the same as the one we were
+		 * previously using, then have it take the place of the other
+		 * one in the formatting list and stack. */
+		if (reparented != stack[last_node].node) {
+			for (struct formatting_list_entry *node_entry = 
+				treebuilder->context.formatting_list_end;
+					node_entry != NULL; 
+					node_entry = node_entry->prev) {
+				if (node_entry->stack_index == last_node) {
+					treebuilder->tree_handler->ref_node(
+						treebuilder->tree_handler->ctx,
+						reparented);
+					node_entry->details.node = reparented;
+					treebuilder->tree_handler->unref_node(
+						treebuilder->tree_handler->ctx,
+						stack[last_node].node);
+					break;
+				}
+			}
+			/* Already have enough references, so don't need to 
+			 * explicitly reference it here. */
+			stack[last_node].node = reparented;
+		}
 
 		/* 9 */
 		void *fe_clone = NULL;
@@ -1361,6 +1387,18 @@ void process_0presentational_in_body(hubbub_treebuilder *treebuilder,
 				stack[furthest_block].node, fe_clone,
 				&clone_appended);
 
+		if (clone_appended != fe_clone) {
+			/* No longer interested in fe_clone */
+			treebuilder->tree_handler->unref_node(
+					treebuilder->tree_handler->ctx, 
+					fe_clone);
+			/* Need an extra reference, as we'll insert into the 
+			 * formatting list and element stack */
+			treebuilder->tree_handler->ref_node(
+					treebuilder->tree_handler->ctx,
+					clone_appended);
+		}
+
 		/* 12 and 13 are reversed here so that we know the correct
 		 * stack index to use when inserting into the formatting list */
 
@@ -1389,7 +1427,7 @@ void process_0presentational_in_body(hubbub_treebuilder *treebuilder,
 
 		formatting_list_insert(treebuilder,
 				bookmark.prev, bookmark.next,
-				otype, fe_clone, furthest_block + 1);
+				otype, clone_appended, furthest_block + 1);
 
 		/* 14 */
 	}
@@ -1565,8 +1603,9 @@ void aa_remove_from_parent(hubbub_treebuilder *treebuilder, void *node)
  * \param treebuilder  The treebuilder instance
  * \param node         The node to reparent
  * \param new_parent   The new parent
+ * \return Pointer to reparented node
  */
-void aa_reparent_node(hubbub_treebuilder *treebuilder, void *node,
+void *aa_reparent_node(hubbub_treebuilder *treebuilder, void *node,
 		void *new_parent)
 {
 	void *appended;
@@ -1577,7 +1616,9 @@ void aa_reparent_node(hubbub_treebuilder *treebuilder, void *node,
 			new_parent, node, &appended);
 
 	treebuilder->tree_handler->unref_node(treebuilder->tree_handler->ctx,
-			appended);
+			node);
+
+	return appended;
 }
 
 /**
@@ -1652,8 +1693,31 @@ void aa_find_bookmark_location_reparenting_misnested(
 		}
 
 		/* vi */
-		aa_reparent_node(treebuilder,
+		void *reparented = aa_reparent_node(treebuilder,
 				stack[last].node, stack[node].node);
+		/* If the reparented node is not the same as the one we were
+		 * previously using, then have it take the place of the other
+		 * one in the formatting list and stack. */
+		if (reparented != stack[last].node) {
+			for (node_entry = 
+				treebuilder->context.formatting_list_end;
+					node_entry != NULL; 
+					node_entry = node_entry->prev) {
+				if (node_entry->stack_index == last) {
+					treebuilder->tree_handler->ref_node(
+						treebuilder->tree_handler->ctx,
+						reparented);
+					node_entry->details.node = reparented;
+					treebuilder->tree_handler->unref_node(
+						treebuilder->tree_handler->ctx,
+						stack[last].node);
+					break;
+				}
+			}
+			/* Already have enough references, so don't need to 
+			 * explicitly reference it here. */
+			stack[last].node = reparented;
+		}
 
 		/* vii */
 		last = node;
@@ -1753,8 +1817,9 @@ void aa_clone_and_replace_entries(hubbub_treebuilder *treebuilder,
  *
  * \param treebuilder  The treebuilder instance
  * \param node         The node to insert
+ * \return Pointer to inserted node
  */
-void aa_insert_into_foster_parent(hubbub_treebuilder *treebuilder, void *node)
+void *aa_insert_into_foster_parent(hubbub_treebuilder *treebuilder, void *node)
 {
 	element_context *stack = treebuilder->context.element_stack;
 	void *foster_parent = NULL;
@@ -1804,10 +1869,12 @@ void aa_insert_into_foster_parent(hubbub_treebuilder *treebuilder, void *node)
 	}
 
 	treebuilder->tree_handler->unref_node(treebuilder->tree_handler->ctx,
-			inserted);
+			node);
 
 	treebuilder->tree_handler->unref_node(treebuilder->tree_handler->ctx,
 			foster_parent);
+
+	return inserted;
 }
 
 
diff --git a/src/treebuilder/in_table.c b/src/treebuilder/in_table.c
index c5bb22e..ec5173e 100644
--- a/src/treebuilder/in_table.c
+++ b/src/treebuilder/in_table.c
@@ -116,6 +116,10 @@ bool handle_in_table(hubbub_treebuilder *treebuilder,
 
 		if (type == CAPTION) {
 			clear_stack_table_context(treebuilder);
+			treebuilder->tree_handler->ref_node(
+				treebuilder->tree_handler->ctx,
+				treebuilder->context.element_stack[
+				treebuilder->context.current_node].node);
 			formatting_list_append(treebuilder, type,
 					treebuilder->context.element_stack[
 					treebuilder->context.current_node].node,
diff --git a/src/treebuilder/initial.c b/src/treebuilder/initial.c
index 70869b9..1bce044 100644
--- a/src/treebuilder/initial.c
+++ b/src/treebuilder/initial.c
@@ -266,6 +266,11 @@ bool handle_initial(hubbub_treebuilder *treebuilder, const hubbub_token *token)
 					doctype);
 		}
 
+		treebuilder->tree_handler->unref_node(
+				treebuilder->tree_handler->ctx, appended);
+		treebuilder->tree_handler->unref_node(
+				treebuilder->tree_handler->ctx, doctype);
+
 		const hubbub_doctype *cdoc = &token->data.doctype;
 
 		/* Work out whether we need quirks mode or not */
@@ -280,11 +285,6 @@ bool handle_initial(hubbub_treebuilder *treebuilder, const hubbub_token *token)
 					HUBBUB_QUIRKS_MODE_LIMITED);
 		}
 
-		treebuilder->tree_handler->unref_node(
-				treebuilder->tree_handler->ctx, appended);
-		treebuilder->tree_handler->unref_node(
-				treebuilder->tree_handler->ctx, doctype);
-
 		treebuilder->context.mode = BEFORE_HTML;
 	}
 		break;
diff --git a/src/treebuilder/internal.h b/src/treebuilder/internal.h
index 73b618a..ae293a9 100644
--- a/src/treebuilder/internal.h
+++ b/src/treebuilder/internal.h
@@ -184,7 +184,7 @@ void adjust_foreign_attributes(hubbub_treebuilder *treebuilder,
 		hubbub_tag *tag);
 
 /* in_body.c */
-void aa_insert_into_foster_parent(hubbub_treebuilder *treebuilder, void *node);
+void *aa_insert_into_foster_parent(hubbub_treebuilder *treebuilder, void *node);
 
 #ifndef NDEBUG
 #include <stdio.h>
diff --git a/src/treebuilder/treebuilder.c b/src/treebuilder/treebuilder.c
index 63e104c..f739113 100644
--- a/src/treebuilder/treebuilder.c
+++ b/src/treebuilder/treebuilder.c
@@ -477,7 +477,7 @@ void process_comment_append(hubbub_treebuilder *treebuilder,
 	if (treebuilder->context.in_table_foster &&
 			(type == TABLE || type == TBODY || type == TFOOT ||
 			type == THEAD || type == TR)) {
-		aa_insert_into_foster_parent(treebuilder, comment);
+		appended = aa_insert_into_foster_parent(treebuilder, comment);
 	} else {
 		success = treebuilder->tree_handler->append_child(
 				treebuilder->tree_handler->ctx,
@@ -490,10 +490,11 @@ void process_comment_append(hubbub_treebuilder *treebuilder,
 		}
 
 		treebuilder->tree_handler->unref_node(
-				treebuilder->tree_handler->ctx, appended);
-		treebuilder->tree_handler->unref_node(
 				treebuilder->tree_handler->ctx, comment);
 	}
+
+	treebuilder->tree_handler->unref_node(
+			treebuilder->tree_handler->ctx, appended);
 }
 
 /**
@@ -528,7 +529,9 @@ void parse_generic_rcdata(hubbub_treebuilder *treebuilder,
 	}
 
 	if (treebuilder->context.in_table_foster) {
-		aa_insert_into_foster_parent(treebuilder, node);
+		appended = aa_insert_into_foster_parent(treebuilder, node);
+		treebuilder->tree_handler->ref_node(
+				treebuilder->tree_handler->ctx, appended);
 	} else {
 		success = treebuilder->tree_handler->append_child(
 				treebuilder->tree_handler->ctx,
@@ -541,8 +544,20 @@ void parse_generic_rcdata(hubbub_treebuilder *treebuilder,
 					treebuilder->tree_handler->ctx,
 					node);
 		}
+		if (appended != node) {
+			/* Transfer the reference we have on node to appended.
+			 * We're no longer interested in node */
+			treebuilder->tree_handler->unref_node(
+					treebuilder->tree_handler->ctx,
+					node);
+			treebuilder->tree_handler->ref_node(
+					treebuilder->tree_handler->ctx,
+					appended);
+		}
 	}
 
+	/* Appended node's reference count is 2 */
+
 	params.content_model.model = rcdata ? HUBBUB_CONTENT_MODEL_RCDATA 
 					    : HUBBUB_CONTENT_MODEL_CDATA;
 	hubbub_tokeniser_setopt(treebuilder->tokeniser,
@@ -550,13 +565,12 @@ void parse_generic_rcdata(hubbub_treebuilder *treebuilder,
 
 	treebuilder->context.collect.mode = treebuilder->context.mode;
 	treebuilder->context.collect.type = type;
-	treebuilder->context.collect.node = node;
+	treebuilder->context.collect.node = appended;
 	treebuilder->context.collect.string.data.off = 0;
 	treebuilder->context.collect.string.len = 0;
 
 	treebuilder->tree_handler->unref_node(
-			treebuilder->tree_handler->ctx,
-			appended);
+			treebuilder->tree_handler->ctx, appended);
 
 	treebuilder->context.mode = GENERIC_RCDATA;
 }
@@ -659,14 +673,19 @@ void reconstruct_active_formatting_list(hubbub_treebuilder *treebuilder)
 					type == TR);
 
 		if (foster) {
-			aa_insert_into_foster_parent(treebuilder, clone);
+			appended = aa_insert_into_foster_parent(treebuilder, 
+					clone);
+			treebuilder->tree_handler->ref_node(
+					treebuilder->tree_handler->ctx,
+					appended);
 		} else {
 			success = treebuilder->tree_handler->append_child(
 					treebuilder->tree_handler->ctx,
 					treebuilder->context.element_stack[
-						treebuilder->context.current_node].node,
+					treebuilder->context.current_node].node,
 					clone,
 					&appended);
+
 			if (success != 0) {
 				/** \todo handle errors */
 				treebuilder->tree_handler->unref_node(
@@ -674,30 +693,40 @@ void reconstruct_active_formatting_list(hubbub_treebuilder *treebuilder)
 						clone);
 				return;
 			}
+
+			if (appended != clone) {
+				/* Transfer the reference we hold on clone to
+				 * appended. We're no longer interested in 
+				 * clone.*/
+				treebuilder->tree_handler->unref_node(
+						treebuilder->tree_handler->ctx,
+						clone);
+				treebuilder->tree_handler->ref_node(
+						treebuilder->tree_handler->ctx,
+						appended);
+			}
 		}
 
+		/* At this point, appended's reference count will be 2 */
+
 		if (!element_stack_push(treebuilder,
 				entry->details.ns, entry->details.type,
-				clone)) {
+				appended)) {
 			/** \todo handle memory exhaustion */
 			treebuilder->tree_handler->unref_node(
 					treebuilder->tree_handler->ctx,
-					clone);
-			if (foster)
-				treebuilder->tree_handler->unref_node(
-						treebuilder->tree_handler->ctx,
-						appended);
+					appended);
 		}
 
 		if (!formatting_list_replace(treebuilder, entry,
-				entry->details.type, clone,
+				entry->details.type, appended,
 				treebuilder->context.current_node,
 				&prev_type, &prev_node,
 				&prev_stack_index)) {
 			/** \todo handle errors */
 			treebuilder->tree_handler->unref_node(
 					treebuilder->tree_handler->ctx,
-					clone);
+					appended);
 		}
 
 		treebuilder->tree_handler->unref_node(
@@ -761,7 +790,7 @@ void insert_element(hubbub_treebuilder *treebuilder, const hubbub_tag *tag)
 	if (treebuilder->context.in_table_foster &&
 			(type == TABLE || type == TBODY || type == TFOOT ||
 			type == THEAD || type == TR)) {
-		aa_insert_into_foster_parent(treebuilder, node);
+		appended = aa_insert_into_foster_parent(treebuilder, node);
 	} else {
 		success = treebuilder->tree_handler->append_child(
 				treebuilder->tree_handler->ctx,
@@ -773,13 +802,13 @@ void insert_element(hubbub_treebuilder *treebuilder, const hubbub_tag *tag)
 		}
 
 		treebuilder->tree_handler->unref_node(
-				treebuilder->tree_handler->ctx, appended);
+				treebuilder->tree_handler->ctx, node);
 	}
 
 	if (!element_stack_push(treebuilder,
 			tag->ns,
 			element_type_from_name(treebuilder, &tag->name),
-			node)) {
+			appended)) {
 		/** \todo errors */
 	}
 }
@@ -806,7 +835,7 @@ void insert_element_no_push(hubbub_treebuilder *treebuilder,
 	if (treebuilder->context.in_table_foster &&
 			(type == TABLE || type == TBODY || type == TFOOT ||
 			type == THEAD || type == TR)) {
-		aa_insert_into_foster_parent(treebuilder, node);
+		appended = aa_insert_into_foster_parent(treebuilder, node);
 	} else {
 		success = treebuilder->tree_handler->append_child(
 				treebuilder->tree_handler->ctx,
@@ -818,10 +847,11 @@ void insert_element_no_push(hubbub_treebuilder *treebuilder,
 		}
 
 		treebuilder->tree_handler->unref_node(
-				treebuilder->tree_handler->ctx, appended);
-		treebuilder->tree_handler->unref_node(
 				treebuilder->tree_handler->ctx, node);
 	}
+
+	treebuilder->tree_handler->unref_node(
+			treebuilder->tree_handler->ctx, appended);
 }
 
 /**
@@ -950,7 +980,7 @@ void append_text(hubbub_treebuilder *treebuilder,
 	if (treebuilder->context.in_table_foster &&
 			(type == TABLE || type == TBODY || type == TFOOT ||
 			type == THEAD || type == TR)) {
-		aa_insert_into_foster_parent(treebuilder, text);
+		appended = aa_insert_into_foster_parent(treebuilder, text);
 	} else {
 		success = treebuilder->tree_handler->append_child(
 				treebuilder->tree_handler->ctx,
@@ -959,16 +989,14 @@ void append_text(hubbub_treebuilder *treebuilder,
 						text, &appended);
 		if (success != 0) {
 			/** \todo errors */
-			treebuilder->tree_handler->unref_node(
-					treebuilder->tree_handler->ctx,
-					text);
 		}
 
 		treebuilder->tree_handler->unref_node(
-				treebuilder->tree_handler->ctx, appended);
-		treebuilder->tree_handler->unref_node(
 				treebuilder->tree_handler->ctx, text);
 	}
+
+	treebuilder->tree_handler->unref_node(
+			treebuilder->tree_handler->ctx, appended);
 }
 
 /**
diff --git a/test/Makefile b/test/Makefile
index 72ad345..20aa6ce 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -36,7 +36,7 @@ d              := $(DIR)
 CFLAGS := $(CFLAGS) -I$(TOP)/src/ -I$(d) \
 		`$(PKGCONFIG) $(PKGCONFIGFLAGS) --cflags json` \
 		-Wno-unused-parameter
-LDFLAGS := $(LDFLAGS) `$(PKGCONFIG) $(PKGCONFIGFLAGS) --libs json`
+LDFLAGS := $(LDFLAGS) `$(PKGCONFIG) $(PKGCONFIGFLAGS) --libs json` -liconv
 
 # Tests
 TESTS_$(d) := aliases cscodec csdetect dict entities filter hubbub \
diff --git a/test/tree2.c b/test/tree2.c
index 6f78fb5..53876fb 100644
--- a/test/tree2.c
+++ b/test/tree2.c
@@ -1,7 +1,5 @@
 /*
  * Tree construction tester.
- * Leaks a fair bit of memory, because it doesn't make use of reference
- * counting.
  */
 
 #define _GNU_SOURCE
@@ -54,6 +52,8 @@ struct node_t {
 
 	node_t *child;
 	node_t *parent;
+
+	uint32_t refcnt;
 };
 
 struct buf_t {
@@ -98,6 +98,9 @@ static int add_attributes(void *ctx, void *node,
 		const hubbub_attribute *attributes, uint32_t n_attributes);
 static int set_quirks_mode(void *ctx, hubbub_quirks_mode mode);
 
+static void delete_node(node_t *node);
+static void delete_attr(attr_t *attr);
+
 static hubbub_tree_handler tree_handler = {
 	create_comment,
 	create_doctype,
@@ -264,6 +267,11 @@ int main(int argc, char **argv)
 			buf_clear(&expected);
 
 			hubbub_parser_destroy(parser);
+			while (Document) {
+				node_t *victim = Document;
+				Document = victim->next;
+				delete_node(victim);
+			}
 			Document = NULL;
 
 			state = EXPECT_DATA;
@@ -334,8 +342,22 @@ int main(int argc, char **argv)
 		}
 	}
 
+	if (Document != NULL) {
+		hubbub_parser_destroy(parser);
+		while (Document) {
+			node_t *victim = Document;
+			Document = victim->next;
+			delete_node(victim);
+		}
+	}
+
 	printf("%s\n", passed ? "PASS" : "FAIL");
 
+	fclose(fp);
+
+	free(got.buf);
+	free(expected.buf);
+
 	assert(hubbub_finalise(myrealloc, NULL) == HUBBUB_OK);
 
 	return 0;
@@ -351,6 +373,7 @@ int create_comment(void *ctx, const hubbub_string *data, void **result)
 	node->type = COMMENT;
 	node->data.content = strndup((char *)ptr_from_hubbub_string(data),
 			data->len);
+	node->refcnt = 1;
 
 	*result = node;
 
@@ -379,6 +402,7 @@ int create_doctype(void *ctx, const hubbub_doctype *doctype, void **result)
 					&doctype->system_id),
 				doctype->system_id.len);
 	}
+	node->refcnt = 1;
 
 	*result = node;
 
@@ -416,6 +440,7 @@ int create_element(void *ctx, const hubbub_tag *tag, void **result)
 						&tag->attributes[i].value),
 				tag->attributes[i].value.len);
 	}
+	node->refcnt = 1;
 
 	*result = node;
 
@@ -429,6 +454,7 @@ int create_text(void *ctx, const hubbub_string *data, void **result)
 	node->type = CHARACTER;
 	node->data.content = strndup((char *)ptr_from_hubbub_string(data),
 			data->len);
+	node->refcnt = 1;
 
 	*result = node;
 
@@ -437,11 +463,30 @@ int create_text(void *ctx, const hubbub_string *data, void **result)
 
 int ref_node(void *ctx, void *node)
 {
+	node_t *n = node;
+
+	if (node != (void *) 1)
+		n->refcnt++;
+
 	return 0;
 }
 
 int unref_node(void *ctx, void *node)
 {
+	node_t *n = node;
+
+	if (n != (void *) 1) {
+		assert(n->refcnt > 0);
+
+		n->refcnt--;
+
+		printf("Unreferencing node %p (%d)\n", node, n->refcnt);
+
+		if (n->refcnt == 0 && n->parent == NULL) {
+			delete_node(n);
+		}
+	}
+
 	return 0;
 }
 
@@ -452,7 +497,6 @@ int append_child(void *ctx, void *parent, void *child, void **result)
 
 	node_t *insert = NULL;
 
-	tchild->parent = tparent;
 	tchild->next = tchild->prev = NULL;
 
 #ifndef NDEBUG
@@ -496,6 +540,11 @@ int append_child(void *ctx, void *parent, void *child, void **result)
 		}
 	}
 
+	if (*result == child)
+		tchild->parent = tparent;
+
+	ref_node(ctx, *result);
+
 	return 0;
 }
 
@@ -542,6 +591,8 @@ int insert_before(void *ctx, void *parent, void *child, void *ref_child,
 		*result = child;
 	}
 
+	ref_node(ctx, *result);
+
 	return 0;
 }
 
@@ -553,6 +604,8 @@ int remove_child(void *ctx, void *parent, void *child, void **result)
 	assert(tparent->child);
 	assert(tchild->parent == tparent);
 
+	printf("Removing child %p\n", child);
+
 	if (tchild->parent->child == tchild) {
 		tchild->parent->child = tchild->next;
 	}
@@ -568,6 +621,8 @@ int remove_child(void *ctx, void *parent, void *child, void **result)
 
 	*result = child;
 
+	ref_node(ctx, *result);
+
 	return 0;
 }
 
@@ -576,32 +631,73 @@ int clone_node(void *ctx, void *node, bool deep, void **result)
 	node_t *old_node = node;
 	node_t *new_node = calloc(1, sizeof *new_node);
 
-	*new_node = *old_node;
+	new_node->type = old_node->type;
+
+	switch (old_node->type) {
+	case DOCTYPE:
+		new_node->data.doctype.name = 
+				strdup(old_node->data.doctype.name);
+		if (old_node->data.doctype.public_id)
+			new_node->data.doctype.public_id = 
+				strdup(old_node->data.doctype.public_id);
+		if (old_node->data.doctype.system_id)
+			new_node->data.doctype.system_id =
+				strdup(old_node->data.doctype.system_id);
+		break;
+	case COMMENT:
+	case CHARACTER:
+		new_node->data.content = strdup(old_node->data.content);
+		break;
+	case ELEMENT:
+		new_node->data.element.ns = old_node->data.element.ns;
+		new_node->data.element.name = 
+				strdup(old_node->data.element.name);
+		new_node->data.element.attrs = 
+				calloc(old_node->data.element.n_attrs, 
+					sizeof *new_node->data.element.attrs);
+		for (size_t i = 0; i < old_node->data.element.n_attrs; i++) {
+			attr_t *attr = &new_node->data.element.attrs[i];
+
+			attr->ns = old_node->data.element.attrs[i].ns;
+			attr->name = 
+				strdup(old_node->data.element.attrs[i].name);
+			attr->value =
+				strdup(old_node->data.element.attrs[i].value);
+		}
+		new_node->data.element.n_attrs = old_node->data.element.n_attrs;
+		break;
+	}
+
 	*result = new_node;
 
 	new_node->child = new_node->parent =
 			new_node->next = new_node->prev =
 			NULL;
 
+	new_node->refcnt = 1;
+
 	if (deep == false)
 		return 0;
 
-	if (old_node->next) {
-		void *n;
+	node_t *last = NULL;
 
-		clone_node(ctx, old_node->next, true, &n);
+	for (node_t *child = old_node->child; child != NULL; 
+			child = child->next) {
+		node_t *n;
 
-		new_node->next = n;
-		new_node->next->prev = new_node;
-	}
+		clone_node(ctx, child, true, (void **) &n);
 
-	if (old_node->child) {
-		void *n;
+		n->refcnt = 0;
 
-		clone_node(ctx, old_node->child, true, &n);
+		if (last == NULL) {
+			new_node->child = n;
+		} else {
+			last->next = n;
+			n->prev = last;
+		}
 
-		new_node->child = n;
-		new_node->child->parent = new_node;
+		n->parent = new_node;
+		last = n;
 	}
 
 	return 0;
@@ -645,6 +741,9 @@ int get_parent(void *ctx, void *node, bool element_only, void **result)
 {
 	*result = ((node_t *)node)->parent;
 
+	if (*result != NULL)
+		ref_node(ctx, *result);
+
 	return 0;
 }
 
@@ -781,6 +880,9 @@ static void node_print(buf_t *buf, node_t *node, unsigned depth)
 		buf_add(buf, node->data.content);
 		buf_add(buf, " -->\n");
 		break;
+	default:
+		printf("Unexpected node type %d\n", node->type);
+		assert(0);
 	}
 
 	if (node->child) {
@@ -791,3 +893,57 @@ static void node_print(buf_t *buf, node_t *node, unsigned depth)
 		node_print(buf, node->next, depth);
 	}
 }
+
+static void delete_node(node_t *node)
+{
+	if (node == NULL)
+		return;
+
+	if (node->refcnt != 0) {
+		printf("Node %p has non-zero refcount %d\n", 
+				(void *) node, node->refcnt);
+		assert(0);
+	}
+
+	switch (node->type) {
+	case DOCTYPE:
+		free(node->data.doctype.name);
+		free(node->data.doctype.public_id);
+		free(node->data.doctype.system_id);
+		break;
+	case COMMENT:
+	case CHARACTER:
+		free(node->data.content);
+		break;
+	case ELEMENT:
+		free(node->data.element.name);
+		for (size_t i = 0; i < node->data.element.n_attrs; i++)
+			delete_attr(&node->data.element.attrs[i]);
+		free(node->data.element.attrs);
+		break;
+	}
+
+	node_t *c, *d;
+
+	for (c = node->child; c != NULL; c = d) {
+		d = c->next;
+
+		delete_node(c);
+	}
+
+	memset(node, 0xdf, sizeof(node_t));
+
+	free(node);
+}
+
+static void delete_attr(attr_t *attr)
+{
+	if (attr == NULL)
+		return;
+
+	free(attr->name);
+	free(attr->value);
+
+	memset(attr, 0xdf, sizeof(attr_t));
+}
+