Index: test/tree2.c =================================================================== --- test/tree2.c (revision 4661) +++ test/tree2.c (working copy) @@ -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 @@ node_t *child; node_t *parent; + + uint32_t refcnt; }; struct buf_t { @@ -98,6 +98,9 @@ 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 @@ 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 @@ } } + 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 @@ node->type = COMMENT; node->data.content = strndup((char *)ptr_from_hubbub_string(data), data->len); + node->refcnt = 1; *result = node; @@ -379,6 +402,7 @@ &doctype->system_id), doctype->system_id.len); } + node->refcnt = 1; *result = node; @@ -416,6 +440,7 @@ &tag->attributes[i].value), tag->attributes[i].value.len); } + node->refcnt = 1; *result = node; @@ -429,6 +454,7 @@ 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 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 @@ node_t *insert = NULL; - tchild->parent = tparent; tchild->next = tchild->prev = NULL; #ifndef NDEBUG @@ -496,6 +540,11 @@ } } + if (*result == child) + tchild->parent = tparent; + + ref_node(ctx, *result); + return 0; } @@ -542,6 +591,8 @@ *result = child; } + ref_node(ctx, *result); + return 0; } @@ -553,6 +604,8 @@ 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 @@ *result = child; + ref_node(ctx, *result); + return 0; } @@ -576,32 +631,73 @@ 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 @@ { *result = ((node_t *)node)->parent; + if (*result != NULL) + ref_node(ctx, *result); + return 0; } @@ -781,6 +880,9 @@ 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 @@ 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)); +} + Index: src/treebuilder/treebuilder.c =================================================================== --- src/treebuilder/treebuilder.c (revision 4661) +++ src/treebuilder/treebuilder.c (working copy) @@ -477,7 +477,7 @@ 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 @@ } 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 @@ } 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ } 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 @@ 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 @@ } 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 @@ 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 @@ 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); } /** Index: src/treebuilder/in_table.c =================================================================== --- src/treebuilder/in_table.c (revision 4661) +++ src/treebuilder/in_table.c (working copy) @@ -116,6 +116,10 @@ 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, Index: src/treebuilder/internal.h =================================================================== --- src/treebuilder/internal.h (revision 4661) +++ src/treebuilder/internal.h (working copy) @@ -184,7 +184,7 @@ 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 Index: src/treebuilder/in_body.c =================================================================== --- src/treebuilder/in_body.c (revision 4661) +++ src/treebuilder/in_body.c (working copy) @@ -90,7 +90,7 @@ 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 @@ &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 @@ 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 @@ 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 @@ * \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 @@ new_parent, node, &appended); treebuilder->tree_handler->unref_node(treebuilder->tree_handler->ctx, - appended); + node); + + return appended; } /** @@ -1652,8 +1693,31 @@ } /* 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 @@ * * \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 @@ } treebuilder->tree_handler->unref_node(treebuilder->tree_handler->ctx, - inserted); + node); treebuilder->tree_handler->unref_node(treebuilder->tree_handler->ctx, foster_parent); + + return inserted; } Index: src/treebuilder/before_html.c =================================================================== --- src/treebuilder/before_html.c (revision 4661) +++ src/treebuilder/before_html.c (working copy) @@ -104,21 +104,21 @@ 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; } Index: src/treebuilder/initial.c =================================================================== --- src/treebuilder/initial.c (revision 4661) +++ src/treebuilder/initial.c (working copy) @@ -266,6 +266,11 @@ 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 @@ 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;