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

6 files changed, 148 insertions, 49 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);
 }
 
 /**