Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * This file is part of Hubbub.
  3.  * Licensed under the MIT License,
  4.  *                http://www.opensource.org/licenses/mit-license.php
  5.  * Copyright 2008 John-Mark Bell <jmb@netsurf-browser.org>
  6.  */
  7.  
  8. #include <assert.h>
  9. #include <string.h>
  10.  
  11. #include <stdio.h>
  12.  
  13. #include "treebuilder/modes.h"
  14. #include "treebuilder/internal.h"
  15. #include "treebuilder/treebuilder.h"
  16. #include "utils/utils.h"
  17. #include "utils/string.h"
  18.  
  19.  
  20. #define S(x)   x, SLEN(x)
  21.  
  22. static const struct {
  23.         const char *name;
  24.         size_t len;
  25.         element_type type;
  26. } name_type_map[] = {
  27.         { S("address"), ADDRESS },      { S("area"), AREA },
  28.         { S("base"), BASE },            { S("basefont"), BASEFONT },
  29.         { S("bgsound"), BGSOUND },      { S("blockquote"), BLOCKQUOTE },
  30.         { S("body"), BODY },            { S("br"), BR },
  31.         { S("center"), CENTER },        { S("col"), COL },
  32.         { S("colgroup"), COLGROUP },    { S("dd"), DD },
  33.         { S("dir"), DIR },              { S("div"), DIV },
  34.         { S("dl"), DL },                { S("dt"), DT },
  35.         { S("embed"), EMBED },          { S("fieldset"), FIELDSET },
  36.         { S("form"), FORM },            { S("frame"), FRAME },
  37.         { S("frameset"), FRAMESET },    { S("h1"), H1 },
  38.         { S("h2"), H2 },                { S("h3"), H3 },
  39.         { S("h4"), H4 },                { S("h5"), H5 },
  40.         { S("h6"), H6 },                { S("head"), HEAD },
  41.         { S("hr"), HR },                { S("iframe"), IFRAME },
  42.         { S("image"), IMAGE },          { S("img"), IMG },
  43.         { S("input"), INPUT },          { S("isindex"), ISINDEX },
  44.         { S("li"), LI },                { S("link"), LINK },
  45.         { S("listing"), LISTING },
  46.         { S("menu"), MENU },
  47.         { S("meta"), META },            { S("noembed"), NOEMBED },
  48.         { S("noframes"), NOFRAMES },    { S("noscript"), NOSCRIPT },
  49.         { S("ol"), OL },                { S("optgroup"), OPTGROUP },
  50.         { S("option"), OPTION },        { S("output"), OUTPUT },
  51.         { S("p"), P },                  { S("param"), PARAM },
  52.         { S("plaintext"), PLAINTEXT },  { S("pre"), PRE },
  53.         { S("script"), SCRIPT },        { S("select"), SELECT },
  54.         { S("spacer"), SPACER },        { S("style"), STYLE },
  55.         { S("tbody"), TBODY },          { S("textarea"), TEXTAREA },
  56.         { S("tfoot"), TFOOT },          { S("thead"), THEAD },
  57.         { S("title"), TITLE },          { S("tr"), TR },
  58.         { S("ul"), UL },                { S("wbr"), WBR },
  59.         { S("applet"), APPLET },        { S("button"), BUTTON },
  60.         { S("caption"), CAPTION },      { S("html"), HTML },
  61.         { S("marquee"), MARQUEE },      { S("object"), OBJECT },
  62.         { S("table"), TABLE },          { S("td"), TD },
  63.         { S("th"), TH },
  64.         { S("a"), A },                  { S("b"), B },
  65.         { S("big"), BIG },              { S("em"), EM },
  66.         { S("font"), FONT },            { S("i"), I },
  67.         { S("nobr"), NOBR },            { S("s"), S },
  68.         { S("small"), SMALL },          { S("strike"), STRIKE },
  69.         { S("strong"), STRONG },        { S("tt"), TT },
  70.         { S("u"), U },                  { S("xmp"), XMP },
  71.  
  72.         { S("math"), MATH },            { S("mglyph"), MGLYPH },
  73.         { S("malignmark"), MALIGNMARK },
  74.         { S("mi"), MI },                { S("mo"), MO },
  75.         { S("mn"), MN },                { S("ms"), MS },
  76.         { S("mtext"), MTEXT },          { S("annotation-xml"), ANNOTATION_XML },
  77.  
  78.         { S("svg"), SVG },              { S("desc"), DESC },
  79.         { S("foreignobject"), FOREIGNOBJECT },
  80. };
  81.  
  82. static bool is_form_associated(element_type type);
  83.  
  84. /**
  85.  * Create a hubbub treebuilder
  86.  *
  87.  * \param tokeniser    Underlying tokeniser instance
  88.  * \param alloc        Memory (de)allocation function
  89.  * \param pw           Pointer to client-specific private data
  90.  * \param treebuilder  Pointer to location to receive treebuilder instance
  91.  * \return HUBBUB_OK on success,
  92.  *         HUBBUB_BADPARM on bad parameters
  93.  *         HUBBUB_NOMEM on memory exhaustion
  94.  */
  95. hubbub_error hubbub_treebuilder_create(hubbub_tokeniser *tokeniser,
  96.                 hubbub_allocator_fn alloc, void *pw,
  97.                 hubbub_treebuilder **treebuilder)
  98. {
  99.         hubbub_error error;
  100.         hubbub_treebuilder *tb;
  101.         hubbub_tokeniser_optparams tokparams;
  102.  
  103.         if (tokeniser == NULL || alloc == NULL || treebuilder == NULL)
  104.                 return HUBBUB_BADPARM;
  105.  
  106.         tb = alloc(NULL, sizeof(hubbub_treebuilder), pw);
  107.         if (tb == NULL)
  108.                 return HUBBUB_NOMEM;
  109.  
  110.         tb->tokeniser = tokeniser;
  111.  
  112.         tb->tree_handler = NULL;
  113.  
  114.         memset(&tb->context, 0, sizeof(hubbub_treebuilder_context));
  115.         tb->context.mode = INITIAL;
  116.  
  117.         tb->context.element_stack = alloc(NULL,
  118.                         ELEMENT_STACK_CHUNK * sizeof(element_context),
  119.                         pw);
  120.         if (tb->context.element_stack == NULL) {
  121.                 alloc(tb, 0, pw);
  122.                 return HUBBUB_NOMEM;
  123.         }
  124.         tb->context.stack_alloc = ELEMENT_STACK_CHUNK;
  125.         /* We rely on HTML not being equal to zero to determine
  126.          * if the first item in the stack is in use. Assert this here. */
  127.         assert(HTML != 0);
  128.         tb->context.element_stack[0].type = (element_type) 0;
  129.  
  130.         tb->context.strip_leading_lr = false;
  131.         tb->context.frameset_ok = true;
  132.  
  133.         tb->error_handler = NULL;
  134.         tb->error_pw = NULL;
  135.  
  136.         tb->alloc = alloc;
  137.         tb->alloc_pw = pw;
  138.  
  139.         tokparams.token_handler.handler = hubbub_treebuilder_token_handler;
  140.         tokparams.token_handler.pw = tb;
  141.  
  142.         error = hubbub_tokeniser_setopt(tokeniser,
  143.                         HUBBUB_TOKENISER_TOKEN_HANDLER, &tokparams);
  144.         if (error != HUBBUB_OK) {
  145.                 alloc(tb->context.element_stack, 0, pw);
  146.                 alloc(tb, 0, pw);
  147.                 return error;
  148.         }
  149.  
  150.         *treebuilder = tb;
  151.  
  152.         return HUBBUB_OK;
  153. }
  154.  
  155. /**
  156.  * Destroy a hubbub treebuilder
  157.  *
  158.  * \param treebuilder  The treebuilder instance to destroy
  159.  * \return HUBBUB_OK on success, appropriate error otherwise
  160.  */
  161. hubbub_error hubbub_treebuilder_destroy(hubbub_treebuilder *treebuilder)
  162. {
  163.         formatting_list_entry *entry, *next;
  164.         hubbub_tokeniser_optparams tokparams;
  165.  
  166.         if (treebuilder == NULL)
  167.                 return HUBBUB_BADPARM;
  168.  
  169.         tokparams.token_handler.handler = NULL;
  170.         tokparams.token_handler.pw = NULL;
  171.  
  172.         hubbub_tokeniser_setopt(treebuilder->tokeniser,
  173.                         HUBBUB_TOKENISER_TOKEN_HANDLER, &tokparams);
  174.  
  175.         /* Clean up context */
  176.         if (treebuilder->tree_handler != NULL) {
  177.                 uint32_t n;
  178.  
  179.                 if (treebuilder->context.head_element != NULL) {
  180.                         treebuilder->tree_handler->unref_node(
  181.                                         treebuilder->tree_handler->ctx,
  182.                                         treebuilder->context.head_element);
  183.                 }
  184.  
  185.                 if (treebuilder->context.form_element != NULL) {
  186.                         treebuilder->tree_handler->unref_node(
  187.                                         treebuilder->tree_handler->ctx,
  188.                                         treebuilder->context.form_element);
  189.                 }
  190.  
  191.                 if (treebuilder->context.document != NULL) {
  192.                         treebuilder->tree_handler->unref_node(
  193.                                         treebuilder->tree_handler->ctx,
  194.                                         treebuilder->context.document);
  195.                 }
  196.  
  197.                 for (n = treebuilder->context.current_node;
  198.                                 n > 0; n--) {
  199.                         treebuilder->tree_handler->unref_node(
  200.                                 treebuilder->tree_handler->ctx,
  201.                                 treebuilder->context.element_stack[n].node);
  202.                 }
  203.                 if (treebuilder->context.element_stack[0].type == HTML) {
  204.                         treebuilder->tree_handler->unref_node(
  205.                                 treebuilder->tree_handler->ctx,
  206.                                 treebuilder->context.element_stack[0].node);
  207.                 }
  208.         }
  209.         treebuilder->alloc(treebuilder->context.element_stack, 0,
  210.                         treebuilder->alloc_pw);
  211.         treebuilder->context.element_stack = NULL;
  212.  
  213.         for (entry = treebuilder->context.formatting_list; entry != NULL;
  214.                         entry = next) {
  215.                 next = entry->next;
  216.  
  217.                 if (treebuilder->tree_handler != NULL) {
  218.                         treebuilder->tree_handler->unref_node(
  219.                                         treebuilder->tree_handler->ctx,
  220.                                         entry->details.node);
  221.                 }
  222.  
  223.                 treebuilder->alloc(entry, 0, treebuilder->alloc_pw);
  224.         }
  225.  
  226.         treebuilder->alloc(treebuilder, 0, treebuilder->alloc_pw);
  227.  
  228.         return HUBBUB_OK;
  229. }
  230.  
  231. /**
  232.  * Configure a hubbub treebuilder
  233.  *
  234.  * \param treebuilder  The treebuilder instance to configure
  235.  * \param type         The option type to configure
  236.  * \param params       Pointer to option-specific parameters
  237.  * \return HUBBUB_OK on success, appropriate error otherwise.
  238.  */
  239. hubbub_error hubbub_treebuilder_setopt(hubbub_treebuilder *treebuilder,
  240.                 hubbub_treebuilder_opttype type,
  241.                 hubbub_treebuilder_optparams *params)
  242. {
  243.         if (treebuilder == NULL || params == NULL)
  244.                 return HUBBUB_BADPARM;
  245.  
  246.         switch (type) {
  247.         case HUBBUB_TREEBUILDER_ERROR_HANDLER:
  248.                 treebuilder->error_handler = params->error_handler.handler;
  249.                 treebuilder->error_pw = params->error_handler.pw;
  250.                 break;
  251.         case HUBBUB_TREEBUILDER_TREE_HANDLER:
  252.                 treebuilder->tree_handler = params->tree_handler;
  253.                 break;
  254.         case HUBBUB_TREEBUILDER_DOCUMENT_NODE:
  255.                 treebuilder->context.document = params->document_node;
  256.                 break;
  257.         case HUBBUB_TREEBUILDER_ENABLE_SCRIPTING:
  258.                 treebuilder->context.enable_scripting =
  259.                                 params->enable_scripting;
  260.                 break;
  261.         }
  262.  
  263.         return HUBBUB_OK;
  264. }
  265.  
  266. /**
  267.  * Handle tokeniser emitting a token
  268.  *
  269.  * \param token  The emitted token
  270.  * \param pw     Pointer to treebuilder instance
  271.  */
  272. hubbub_error hubbub_treebuilder_token_handler(const hubbub_token *token,
  273.                 void *pw)
  274. {
  275.         hubbub_treebuilder *treebuilder = (hubbub_treebuilder *) pw;
  276.         hubbub_error err = HUBBUB_REPROCESS;
  277.  
  278.         /* Do nothing if we have no document node or there's no tree handler */
  279.         if (treebuilder->context.document == NULL ||
  280.                         treebuilder->tree_handler == NULL)
  281.                 return HUBBUB_OK;
  282.  
  283.         assert((signed) treebuilder->context.current_node >= 0);
  284.  
  285. /* A slightly nasty debugging hook, but very useful */
  286. #ifdef NDEBUG
  287. # define mode(x) \
  288.                 case x:
  289. #else
  290. # define mode(x) \
  291.                 case x: \
  292.                         printf( #x "\n");
  293. #endif
  294.  
  295.         while (err == HUBBUB_REPROCESS) {
  296.                 switch (treebuilder->context.mode) {
  297.                 mode(INITIAL)
  298.                         err = handle_initial(treebuilder, token);
  299.                         break;
  300.                 mode(BEFORE_HTML)
  301.                         err = handle_before_html(treebuilder, token);
  302.                         break;
  303.                 mode(BEFORE_HEAD)
  304.                         err = handle_before_head(treebuilder, token);
  305.                         break;
  306.                 mode(IN_HEAD)
  307.                         err = handle_in_head(treebuilder, token);
  308.                         break;
  309.                 mode(IN_HEAD_NOSCRIPT)
  310.                         err = handle_in_head_noscript(treebuilder, token);
  311.                         break;
  312.                 mode(AFTER_HEAD)
  313.                         err = handle_after_head(treebuilder, token);
  314.                         break;
  315.                 mode(IN_BODY)
  316.                         err = handle_in_body(treebuilder, token);
  317.                         break;
  318.                 mode(IN_TABLE)
  319.                         err = handle_in_table(treebuilder, token);
  320.                         break;
  321.                 mode(IN_CAPTION)
  322.                         err = handle_in_caption(treebuilder, token);
  323.                         break;
  324.                 mode(IN_COLUMN_GROUP)
  325.                         err = handle_in_column_group(treebuilder, token);
  326.                         break;
  327.                 mode(IN_TABLE_BODY)
  328.                         err = handle_in_table_body(treebuilder, token);
  329.                         break;
  330.                 mode(IN_ROW)
  331.                         err = handle_in_row(treebuilder, token);
  332.                         break;
  333.                 mode(IN_CELL)
  334.                         err = handle_in_cell(treebuilder, token);
  335.                         break;
  336.                 mode(IN_SELECT)
  337.                         err = handle_in_select(treebuilder, token);
  338.                         break;
  339.                 mode(IN_SELECT_IN_TABLE)
  340.                         err = handle_in_select_in_table(treebuilder, token);
  341.                         break;
  342.                 mode(IN_FOREIGN_CONTENT)
  343.                         err = handle_in_foreign_content(treebuilder, token);
  344.                         break;
  345.                 mode(AFTER_BODY)
  346.                         err = handle_after_body(treebuilder, token);
  347.                         break;
  348.                 mode(IN_FRAMESET)
  349.                         err = handle_in_frameset(treebuilder, token);
  350.                         break;
  351.                 mode(AFTER_FRAMESET)
  352.                         err = handle_after_frameset(treebuilder, token);
  353.                         break;
  354.                 mode(AFTER_AFTER_BODY)
  355.                         err = handle_after_after_body(treebuilder, token);
  356.                         break;
  357.                 mode(AFTER_AFTER_FRAMESET)
  358.                         err = handle_after_after_frameset(treebuilder, token);
  359.                         break;
  360.                 mode(GENERIC_RCDATA)
  361.                         err = handle_generic_rcdata(treebuilder, token);
  362.                         break;
  363.                 }
  364.         }
  365.  
  366.         return err;
  367. }
  368.  
  369.  
  370. /**
  371.  * Process a character token in cases where we expect only whitespace
  372.  *
  373.  * \param treebuilder               The treebuilder instance
  374.  * \param token                     The character token
  375.  * \param insert_into_current_node  Whether to insert whitespace into
  376.  *                                  current node
  377.  * \return HUBBUB_REPROCESS if the token needs reprocessing
  378.  *                          (token data updated to skip any leading whitespace),
  379.  *         HUBBUB_OK if it contained only whitespace,
  380.  *         appropriate error otherwise
  381.  */
  382. hubbub_error process_characters_expect_whitespace(
  383.                 hubbub_treebuilder *treebuilder,
  384.                 const hubbub_token *token, bool insert_into_current_node)
  385. {
  386.         const uint8_t *data = token->data.character.ptr;
  387.         size_t len = token->data.character.len;
  388.         size_t c;
  389.  
  390.         for (c = 0; c < len; c++) {
  391.                 if (data[c] != 0x09 && data[c] != 0x0A &&
  392.                                 data[c] != 0x0C && data[c] != 0x20)
  393.                         break;
  394.         }
  395.  
  396.         if (c > 0 && insert_into_current_node) {
  397.                 hubbub_error error;
  398.                 hubbub_string temp;
  399.  
  400.                 temp.ptr = data;
  401.                 temp.len = c;
  402.  
  403.                 error = append_text(treebuilder, &temp);
  404.                 if (error != HUBBUB_OK)
  405.                         return error;
  406.         }
  407.  
  408.         /* Non-whitespace characters in token, so reprocess */
  409.         if (c != len) {
  410.                 /* Update token data to strip leading whitespace */
  411.                 ((hubbub_token *) token)->data.character.ptr += c;
  412.                 ((hubbub_token *) token)->data.character.len -= c;
  413.  
  414.                 return HUBBUB_REPROCESS;
  415.         }
  416.  
  417.         return HUBBUB_OK;
  418. }
  419.  
  420. /**
  421.  * Process a comment token, appending it to the given parent
  422.  *
  423.  * \param treebuilder  The treebuilder instance
  424.  * \param token        The comment token
  425.  * \param parent       The node to append to
  426.  * \return HUBBUB_OK on success, appropriate error otherwise
  427.  */
  428. hubbub_error process_comment_append(hubbub_treebuilder *treebuilder,
  429.                 const hubbub_token *token, void *parent)
  430. {
  431.         hubbub_error error = HUBBUB_OK;
  432.         element_type type = current_node(treebuilder);
  433.         void *comment, *appended;
  434.  
  435.         error = treebuilder->tree_handler->create_comment(
  436.                         treebuilder->tree_handler->ctx,
  437.                         &token->data.comment, &comment);
  438.         if (error != HUBBUB_OK)
  439.                 return error;
  440.  
  441.         if (treebuilder->context.in_table_foster &&
  442.                         (type == TABLE || type == TBODY || type == TFOOT ||
  443.                         type == THEAD || type == TR)) {
  444.                 error = aa_insert_into_foster_parent(treebuilder, comment,
  445.                                 &appended);
  446.         } else {
  447.                 error = treebuilder->tree_handler->append_child(
  448.                                 treebuilder->tree_handler->ctx,
  449.                                 parent, comment, &appended);
  450.         }
  451.  
  452.         if (error == HUBBUB_OK) {
  453.                 treebuilder->tree_handler->unref_node(
  454.                                 treebuilder->tree_handler->ctx, appended);
  455.         }
  456.  
  457.         treebuilder->tree_handler->unref_node(
  458.                         treebuilder->tree_handler->ctx, comment);
  459.  
  460.         return error;
  461. }
  462.  
  463. /**
  464.  * Trigger parsing of generic (R)CDATA
  465.  *
  466.  * \param treebuilder  The treebuilder instance
  467.  * \param token        The current token
  468.  * \param rcdata       True for RCDATA, false for CDATA
  469.  * \return HUBBUB_OK on success, appropriate error otherwise
  470.  */
  471. hubbub_error parse_generic_rcdata(hubbub_treebuilder *treebuilder,
  472.                 const hubbub_token *token, bool rcdata)
  473. {
  474.         hubbub_error error;
  475.         element_type type;
  476.         hubbub_tokeniser_optparams params;
  477.  
  478.         type = element_type_from_name(treebuilder, &token->data.tag.name);
  479.  
  480.         error = insert_element(treebuilder, &token->data.tag, true);
  481.         if (error != HUBBUB_OK)
  482.                 return error;
  483.  
  484.         params.content_model.model = rcdata ? HUBBUB_CONTENT_MODEL_RCDATA
  485.                                             : HUBBUB_CONTENT_MODEL_CDATA;
  486.         error = hubbub_tokeniser_setopt(treebuilder->tokeniser,
  487.                                 HUBBUB_TOKENISER_CONTENT_MODEL, &params);
  488.         /* There is no way that setopt can fail. Ensure this. */
  489.         assert(error == HUBBUB_OK);
  490.  
  491.         treebuilder->context.collect.mode = treebuilder->context.mode;
  492.         treebuilder->context.collect.type = type;
  493.  
  494.         treebuilder->context.mode = GENERIC_RCDATA;
  495.  
  496.         return HUBBUB_OK;
  497. }
  498.  
  499. /**
  500.  * Determine if an element is in (table) scope
  501.  *
  502.  * \param treebuilder  Treebuilder to look in
  503.  * \param type         Element type to find
  504.  * \param in_table     Whether we're looking in table scope
  505.  * \return Element stack index, or 0 if not in scope
  506.  */
  507. uint32_t element_in_scope(hubbub_treebuilder *treebuilder,
  508.                 element_type type, bool in_table)
  509. {
  510.         uint32_t node;
  511.  
  512.         if (treebuilder->context.element_stack == NULL)
  513.                 return 0;
  514.  
  515.         assert((signed) treebuilder->context.current_node >= 0);
  516.  
  517.         for (node = treebuilder->context.current_node; node > 0; node--) {
  518.                 hubbub_ns node_ns =
  519.                                 treebuilder->context.element_stack[node].ns;
  520.                 element_type node_type =
  521.                                 treebuilder->context.element_stack[node].type;
  522.  
  523.                 if (node_type == type)
  524.                         return node;
  525.  
  526.                 if (node_type == TABLE)
  527.                         break;
  528.  
  529.                 /* The list of element types given in the spec here are the
  530.                  * scoping elements excluding TABLE and HTML. TABLE is handled
  531.                  * in the previous conditional and HTML should only occur
  532.                  * as the first node in the stack, which is never processed
  533.                  * in this loop. */
  534.                 if (!in_table && (is_scoping_element(node_type) ||
  535.                                 (node_type == FOREIGNOBJECT &&
  536.                                                 node_ns == HUBBUB_NS_SVG))) {
  537.                         break;
  538.                 }
  539.         }
  540.  
  541.         return 0;
  542. }
  543.  
  544. /**
  545.  * Reconstruct the list of active formatting elements
  546.  *
  547.  * \param treebuilder  Treebuilder instance containing list
  548.  * \return HUBBUB_OK on success, appropriate error otherwise.
  549.  */
  550. hubbub_error reconstruct_active_formatting_list(hubbub_treebuilder *treebuilder)
  551. {
  552.         hubbub_error error = HUBBUB_OK;
  553.         formatting_list_entry *entry, *initial_entry;
  554.         uint32_t sp = treebuilder->context.current_node;
  555.  
  556.         if (treebuilder->context.formatting_list == NULL)
  557.                 return HUBBUB_OK;
  558.  
  559.         entry = treebuilder->context.formatting_list_end;
  560.  
  561.         /* Assumption: HTML and TABLE elements are not inserted into the list */
  562.         if (is_scoping_element(entry->details.type) || entry->stack_index != 0)
  563.                 return HUBBUB_OK;
  564.  
  565.         while (entry->prev != NULL) {
  566.                 entry = entry->prev;
  567.  
  568.                 if (is_scoping_element(entry->details.type) ||
  569.                                 entry->stack_index != 0) {
  570.                         entry = entry->next;
  571.                         break;
  572.                 }
  573.         }
  574.  
  575.         /* Save initial entry for later */
  576.         initial_entry = entry;
  577.  
  578.         /* Process formatting list entries, cloning nodes and
  579.          * inserting them into the DOM and element stack */
  580.         while (entry != NULL) {
  581.                 void *clone, *appended;
  582.                 bool foster;
  583.                 element_type type = current_node(treebuilder);
  584.  
  585.                 error = treebuilder->tree_handler->clone_node(
  586.                                 treebuilder->tree_handler->ctx,
  587.                                 entry->details.node,
  588.                                 false,
  589.                                 &clone);
  590.                 if (error != HUBBUB_OK)
  591.                         goto cleanup;
  592.  
  593.                 foster = treebuilder->context.in_table_foster &&
  594.                                 (type == TABLE || type == TBODY ||
  595.                                         type == TFOOT || type == THEAD ||
  596.                                         type == TR);
  597.  
  598.                 if (foster) {
  599.                         error = aa_insert_into_foster_parent(treebuilder,
  600.                                         clone, &appended);
  601.                 } else {
  602.                         error = treebuilder->tree_handler->append_child(
  603.                                         treebuilder->tree_handler->ctx,
  604.                                         treebuilder->context.element_stack[
  605.                                         treebuilder->context.current_node].node,
  606.                                         clone,
  607.                                         &appended);
  608.                 }
  609.  
  610.                 /* No longer interested in clone */
  611.                 treebuilder->tree_handler->unref_node(
  612.                                 treebuilder->tree_handler->ctx,
  613.                                 clone);
  614.  
  615.                 if (error != HUBBUB_OK)
  616.                         goto cleanup;
  617.  
  618.                 error = element_stack_push(treebuilder, entry->details.ns,
  619.                                 entry->details.type, appended);
  620.                 if (error != HUBBUB_OK) {
  621.                         remove_node_from_dom(treebuilder, appended);
  622.  
  623.                         treebuilder->tree_handler->unref_node(
  624.                                         treebuilder->tree_handler->ctx,
  625.                                         appended);
  626.  
  627.                         goto cleanup;
  628.                 }
  629.  
  630.                 entry = entry->next;
  631.         }
  632.  
  633.         /* Now, replace the formatting list entries */
  634.         for (entry = initial_entry; entry != NULL; entry = entry->next) {
  635.                 void *node;
  636.                 hubbub_ns prev_ns;
  637.                 element_type prev_type;
  638.                 void *prev_node;
  639.                 uint32_t prev_stack_index;
  640.  
  641.                 node = treebuilder->context.element_stack[++sp].node;
  642.  
  643.                 treebuilder->tree_handler->ref_node(
  644.                                 treebuilder->tree_handler->ctx, node);
  645.  
  646.                 error = formatting_list_replace(treebuilder, entry,
  647.                                 entry->details.ns, entry->details.type,
  648.                                 node, sp,
  649.                                 &prev_ns, &prev_type, &prev_node,
  650.                                 &prev_stack_index);
  651.                 /* Cannot fail. Ensure this. */
  652.                 assert(error == HUBBUB_OK);
  653.  
  654.                 treebuilder->tree_handler->unref_node(
  655.                                 treebuilder->tree_handler->ctx,
  656.                                 prev_node);
  657.         }
  658.  
  659.         return HUBBUB_OK;
  660.  
  661. cleanup:
  662.         /* An error occurred while cloning nodes and inserting them.
  663.          * We must restore the state on entry here. */
  664.         while (treebuilder->context.current_node > sp) {
  665.                 hubbub_ns ns;
  666.                 element_type type;
  667.                 void *node;
  668.  
  669.                 element_stack_pop(treebuilder, &ns, &type, &node);
  670.  
  671.                 remove_node_from_dom(treebuilder, node);
  672.  
  673.                 treebuilder->tree_handler->unref_node(
  674.                                 treebuilder->tree_handler->ctx,
  675.                                 node);
  676.         }
  677.  
  678.         return error;
  679. }
  680.  
  681. /**
  682.  * Remove a node from the DOM
  683.  *
  684.  * \param treebuilder  Treebuilder instance
  685.  * \param node         Node to remove
  686.  * \return HUBBUB_OK on success, appropriate error otherwise.
  687.  */
  688. hubbub_error remove_node_from_dom(hubbub_treebuilder *treebuilder, void *node)
  689. {
  690.         hubbub_error err;
  691.         void *parent = NULL;
  692.         void *removed;
  693.  
  694.         err = treebuilder->tree_handler->get_parent(
  695.                         treebuilder->tree_handler->ctx,
  696.                         node, false, &parent);
  697.         if (err != HUBBUB_OK)
  698.                 return err;
  699.  
  700.         if (parent != NULL) {
  701.                 err = treebuilder->tree_handler->remove_child(
  702.                                 treebuilder->tree_handler->ctx,
  703.                                 parent, node, &removed);
  704.                 if (err != HUBBUB_OK)
  705.                         return err;
  706.  
  707.                 treebuilder->tree_handler->unref_node(
  708.                                 treebuilder->tree_handler->ctx,
  709.                                 parent);
  710.  
  711.                 treebuilder->tree_handler->unref_node(
  712.                                 treebuilder->tree_handler->ctx,
  713.                                 removed);
  714.         }
  715.  
  716.         return HUBBUB_OK;
  717. }
  718.  
  719. /**
  720.  * Clear the list of active formatting elements up to the last marker
  721.  *
  722.  * \param treebuilder  The treebuilder instance containing the list
  723.  */
  724. void clear_active_formatting_list_to_marker(hubbub_treebuilder *treebuilder)
  725. {
  726.         formatting_list_entry *entry;
  727.         bool done = false;
  728.  
  729.         while ((entry = treebuilder->context.formatting_list_end) != NULL) {
  730.                 hubbub_ns ns;
  731.                 element_type type;
  732.                 void *node;
  733.                 uint32_t stack_index;
  734.  
  735.                 if (is_scoping_element(entry->details.type))
  736.                         done = true;
  737.  
  738.                 formatting_list_remove(treebuilder, entry,
  739.                                 &ns, &type, &node, &stack_index);
  740.  
  741.                 treebuilder->tree_handler->unref_node(
  742.                                 treebuilder->tree_handler->ctx,
  743.                                 node);
  744.  
  745.                 if (done)
  746.                         break;
  747.         }
  748. }
  749.  
  750. /**
  751.  * Create element and insert it into the DOM,
  752.  * potentially pushing it on the stack
  753.  *
  754.  * \param treebuilder  The treebuilder instance
  755.  * \param tag          The element to insert
  756.  * \param push         Whether to push the element onto the stack
  757.  * \return HUBBUB_OK on success, appropriate error otherwise.
  758.  */
  759. hubbub_error insert_element(hubbub_treebuilder *treebuilder,
  760.                 const hubbub_tag *tag, bool push)
  761. {
  762.         element_type type = current_node(treebuilder);
  763.         hubbub_error error;
  764.         void *node, *appended;
  765.  
  766.         error = treebuilder->tree_handler->create_element(
  767.                         treebuilder->tree_handler->ctx, tag, &node);
  768.         if (error != HUBBUB_OK)
  769.                 return error;
  770.  
  771.         if (treebuilder->context.in_table_foster &&
  772.                         (type == TABLE || type == TBODY || type == TFOOT ||
  773.                         type == THEAD || type == TR)) {
  774.                 error = aa_insert_into_foster_parent(treebuilder, node,
  775.                                 &appended);
  776.         } else {
  777.                 error = treebuilder->tree_handler->append_child(
  778.                                 treebuilder->tree_handler->ctx,
  779.                                 treebuilder->context.element_stack[
  780.                                         treebuilder->context.current_node].node,
  781.                                 node, &appended);
  782.         }
  783.  
  784.         /* No longer interested in node */
  785.         treebuilder->tree_handler->unref_node(
  786.                         treebuilder->tree_handler->ctx, node);
  787.  
  788.         if (error != HUBBUB_OK)
  789.                 return error;
  790.  
  791.         type = element_type_from_name(treebuilder, &tag->name);
  792.         if (treebuilder->context.form_element != NULL &&
  793.                         is_form_associated(type)) {
  794.                 /* Consideration of @form is left to the client */
  795.                 error = treebuilder->tree_handler->form_associate(
  796.                                 treebuilder->tree_handler->ctx,
  797.                                 treebuilder->context.form_element,
  798.                                 appended);
  799.                 if (error != HUBBUB_OK) {
  800.                         remove_node_from_dom(treebuilder, appended);
  801.  
  802.                         treebuilder->tree_handler->unref_node(
  803.                                         treebuilder->tree_handler->ctx,
  804.                                         appended);
  805.  
  806.                         return error;
  807.                 }
  808.         }
  809.  
  810.         if (push) {
  811.                 error = element_stack_push(treebuilder,
  812.                                 tag->ns, type, appended);
  813.                 if (error != HUBBUB_OK) {
  814.                         remove_node_from_dom(treebuilder, appended);
  815.  
  816.                         treebuilder->tree_handler->unref_node(
  817.                                         treebuilder->tree_handler->ctx,
  818.                                         appended);
  819.                         return error;
  820.                 }
  821.         } else {
  822.                 treebuilder->tree_handler->unref_node(
  823.                                 treebuilder->tree_handler->ctx, appended);
  824.         }
  825.  
  826.         return HUBBUB_OK;
  827. }
  828.  
  829. /**
  830.  * Close implied end tags
  831.  *
  832.  * \param treebuilder  The treebuilder instance
  833.  * \param except       Tag type to exclude from processing [DD,DT,LI,OPTION,
  834.  *                     OPTGROUP,P,RP,RT], UNKNOWN to exclude nothing
  835.  */
  836. void close_implied_end_tags(hubbub_treebuilder *treebuilder,
  837.                 element_type except)
  838. {
  839.         element_type type;
  840.  
  841.         type = treebuilder->context.element_stack[
  842.                         treebuilder->context.current_node].type;
  843.  
  844.         while (type == DD || type == DT || type == LI || type == OPTION ||
  845.                         type == OPTGROUP || type == P || type == RP ||
  846.                         type == RT) {
  847.                 hubbub_ns ns;
  848.                 element_type otype;
  849.                 void *node;
  850.  
  851.                 if (except != UNKNOWN && type == except)
  852.                         break;
  853.  
  854.                 element_stack_pop(treebuilder, &ns, &otype, &node);
  855.  
  856.                 treebuilder->tree_handler->unref_node(
  857.                                 treebuilder->tree_handler->ctx,
  858.                                 node);
  859.  
  860.                 type = treebuilder->context.element_stack[
  861.                                 treebuilder->context.current_node].type;
  862.         }
  863. }
  864.  
  865. /**
  866.  * Reset the insertion mode
  867.  *
  868.  * \param treebuilder  The treebuilder to reset
  869.  */
  870. void reset_insertion_mode(hubbub_treebuilder *treebuilder)
  871. {
  872.         uint32_t node;
  873.         element_context *stack = treebuilder->context.element_stack;
  874.  
  875.         /** \todo fragment parsing algorithm */
  876.  
  877.         for (node = treebuilder->context.current_node; node > 0; node--) {
  878.                 if (stack[node].ns != HUBBUB_NS_HTML) {
  879.                         treebuilder->context.mode = IN_FOREIGN_CONTENT;
  880.                         treebuilder->context.second_mode = IN_BODY;
  881.                         break;
  882.                 }
  883.  
  884.                 switch (stack[node].type) {
  885.                 case SELECT:
  886.                         /* fragment case */
  887.                         break;
  888.                 case TD:
  889.                 case TH:
  890.                         treebuilder->context.mode = IN_CELL;
  891.                         return;
  892.                 case TR:
  893.                         treebuilder->context.mode = IN_ROW;
  894.                         return;
  895.                 case TBODY:
  896.                 case TFOOT:
  897.                 case THEAD:
  898.                         treebuilder->context.mode = IN_TABLE_BODY;
  899.                         return;
  900.                 case CAPTION:
  901.                         treebuilder->context.mode = IN_CAPTION;
  902.                         return;
  903.                 case COLGROUP:
  904.                         /* fragment case */
  905.                         break;
  906.                 case TABLE:
  907.                         treebuilder->context.mode = IN_TABLE;
  908.                         return;
  909.                 case HEAD:
  910.                         /* fragment case */
  911.                         break;
  912.                 case BODY:
  913.                         treebuilder->context.mode = IN_BODY;
  914.                         return;
  915.                 case FRAMESET:
  916.                         /* fragment case */
  917.                         break;
  918.                 case HTML:
  919.                         /* fragment case */
  920.                         break;
  921.                 default:
  922.                         break;
  923.                 }
  924.         }
  925. }
  926.  
  927. /**
  928.  * Script processing and execution
  929.  *
  930.  * \param treebuilder  The treebuilder instance
  931.  * \return HUBBUB_OK on success, appropriate error otherwise
  932.  */
  933. hubbub_error complete_script(hubbub_treebuilder *treebuilder)
  934. {
  935.         hubbub_error error = HUBBUB_OK;
  936.         error = treebuilder->tree_handler->complete_script(
  937.                 treebuilder->tree_handler->ctx,
  938.                 treebuilder->context.element_stack[
  939.                         treebuilder->context.current_node].node);
  940.         return error;
  941. }
  942.  
  943. /**
  944.  * Append text to the current node, inserting into the last child of the
  945.  * current node, iff it's a Text node.
  946.  *
  947.  * \param treebuilder  The treebuilder instance
  948.  * \param string       The string to append
  949.  * \return HUBBUB_OK on success, appropriate error otherwise
  950.  */
  951. hubbub_error append_text(hubbub_treebuilder *treebuilder,
  952.                 const hubbub_string *string)
  953. {
  954.         element_type type = current_node(treebuilder);
  955.         hubbub_error error = HUBBUB_OK;
  956.         void *text, *appended;
  957.  
  958.         error = treebuilder->tree_handler->create_text(
  959.                         treebuilder->tree_handler->ctx, string, &text);
  960.         if (error != HUBBUB_OK)
  961.                 return error;
  962.  
  963.         if (treebuilder->context.in_table_foster &&
  964.                         (type == TABLE || type == TBODY || type == TFOOT ||
  965.                         type == THEAD || type == TR)) {
  966.                 error = aa_insert_into_foster_parent(treebuilder, text,
  967.                                 &appended);
  968.         } else {
  969.                 error = treebuilder->tree_handler->append_child(
  970.                                 treebuilder->tree_handler->ctx,
  971.                                 treebuilder->context.element_stack[
  972.                                         treebuilder->context.current_node].node,
  973.                                                 text, &appended);
  974.         }
  975.  
  976.         if (error == HUBBUB_OK) {
  977.                 treebuilder->tree_handler->unref_node(
  978.                                 treebuilder->tree_handler->ctx, appended);
  979.         }
  980.  
  981.         treebuilder->tree_handler->unref_node(
  982.                         treebuilder->tree_handler->ctx, text);
  983.  
  984.         return error;
  985. }
  986.  
  987. /**
  988.  * Convert an element name into an element type
  989.  *
  990.  * \param treebuilder  The treebuilder instance
  991.  * \param tag_name     The tag name to consider
  992.  * \return The corresponding element type
  993.  */
  994. element_type element_type_from_name(hubbub_treebuilder *treebuilder,
  995.                 const hubbub_string *tag_name)
  996. {
  997.         const uint8_t *name = tag_name->ptr;
  998.         size_t len = tag_name->len;
  999.         uint32_t i;
  1000.  
  1001.         UNUSED(treebuilder);
  1002.  
  1003.         /** \todo optimise this */
  1004.  
  1005.         for (i = 0; i < N_ELEMENTS(name_type_map); i++) {
  1006.                 if (name_type_map[i].len != len)
  1007.                         continue;
  1008.  
  1009.                 if (strncasecmp(name_type_map[i].name,
  1010.                                 (const char *) name, len) == 0)
  1011.                         return name_type_map[i].type;
  1012.         }
  1013.  
  1014.         return UNKNOWN;
  1015. }
  1016.  
  1017. /**
  1018.  * Determine if a node is a special element
  1019.  *
  1020.  * \param type  Node type to consider
  1021.  * \return True iff node is a special element
  1022.  */
  1023. bool is_special_element(element_type type)
  1024. {
  1025.         return (type <= WBR);
  1026. }
  1027.  
  1028. /**
  1029.  * Determine if a node is a scoping element
  1030.  *
  1031.  * \param type  Node type to consider
  1032.  * \return True iff node is a scoping element
  1033.  */
  1034. bool is_scoping_element(element_type type)
  1035. {
  1036.         return (type >= APPLET && type <= TH);
  1037. }
  1038.  
  1039. /**
  1040.  * Determine if a node is a formatting element
  1041.  *
  1042.  * \param type  Node type to consider
  1043.  * \return True iff node is a formatting element
  1044.  */
  1045. bool is_formatting_element(element_type type)
  1046. {
  1047.         return (type >= A && type <= U);
  1048. }
  1049.  
  1050. /**
  1051.  * Determine if a node is a phrasing element
  1052.  *
  1053.  * \param type  Node type to consider
  1054.  * \return True iff node is a phrasing element
  1055.  */
  1056. bool is_phrasing_element(element_type type)
  1057. {
  1058.         return (type > U);
  1059. }
  1060.  
  1061. /**
  1062.  * Determine if a node is form associated
  1063.  *
  1064.  * \param type  Node type to consider
  1065.  * \return True iff node is form associated
  1066.  */
  1067. bool is_form_associated(element_type type)
  1068. {
  1069.         return type == FIELDSET || type == LABEL || type == INPUT ||
  1070.                         type == BUTTON || type == SELECT || type == TEXTAREA ||
  1071.                         type == OUTPUT;
  1072. }
  1073.  
  1074. /**
  1075.  * Push an element onto the stack of open elements
  1076.  *
  1077.  * \param treebuilder  The treebuilder instance containing the stack
  1078.  * \param ns           The namespace of element being pushed
  1079.  * \param type         The type of element being pushed
  1080.  * \param node         The node to push
  1081.  * \return HUBBUB_OK on success, appropriate error otherwise.
  1082.  */
  1083. hubbub_error element_stack_push(hubbub_treebuilder *treebuilder,
  1084.                 hubbub_ns ns, element_type type, void *node)
  1085. {
  1086.         uint32_t slot = treebuilder->context.current_node + 1;
  1087.  
  1088.         if (slot >= treebuilder->context.stack_alloc) {
  1089.                 element_context *temp = treebuilder->alloc(
  1090.                                 treebuilder->context.element_stack,
  1091.                                 (treebuilder->context.stack_alloc +
  1092.                                         ELEMENT_STACK_CHUNK) *
  1093.                                         sizeof(element_context),
  1094.                                 treebuilder->alloc_pw);
  1095.  
  1096.                 if (temp == NULL)
  1097.                         return HUBBUB_NOMEM;
  1098.  
  1099.                 treebuilder->context.element_stack = temp;
  1100.                 treebuilder->context.stack_alloc += ELEMENT_STACK_CHUNK;
  1101.         }
  1102.  
  1103.         treebuilder->context.element_stack[slot].ns = ns;
  1104.         treebuilder->context.element_stack[slot].type = type;
  1105.         treebuilder->context.element_stack[slot].node = node;
  1106.  
  1107.         treebuilder->context.current_node = slot;
  1108.  
  1109.         return HUBBUB_OK;
  1110. }
  1111.  
  1112. /**
  1113.  * Pop an element off the stack of open elements
  1114.  *
  1115.  * \param treebuilder  The treebuilder instance containing the stack
  1116.  * \param ns           Pointer to location to receive element namespace
  1117.  * \param type         Pointer to location to receive element type
  1118.  * \param node         Pointer to location to receive node
  1119.  * \return HUBBUB_OK on success, appropriate error otherwise.
  1120.  */
  1121. hubbub_error element_stack_pop(hubbub_treebuilder *treebuilder,
  1122.                 hubbub_ns *ns, element_type *type, void **node)
  1123. {
  1124.         element_context *stack = treebuilder->context.element_stack;
  1125.         uint32_t slot = treebuilder->context.current_node;
  1126.         formatting_list_entry *entry;
  1127.  
  1128.         /* We're popping a table, find previous */
  1129.         if (stack[slot].type == TABLE) {
  1130.                 uint32_t t;
  1131.                 for (t = slot - 1; t > 0; t--) {
  1132.                         if (stack[t].type == TABLE)
  1133.                                 break;
  1134.                 }
  1135.         }
  1136.  
  1137.         if (is_formatting_element(stack[slot].type) ||
  1138.                         (is_scoping_element(stack[slot].type) &&
  1139.                         stack[slot].type != HTML &&
  1140.                         stack[slot].type != TABLE)) {
  1141.                 /* Find occurrences of the node we're about to pop in the list
  1142.                  * of active formatting elements. We need to invalidate their
  1143.                  * stack index information. */
  1144.                 for (entry = treebuilder->context.formatting_list_end;
  1145.                                 entry != NULL; entry = entry->prev) {
  1146.                         /** \todo Can we optimise this?
  1147.                          * (i.e. by not traversing the entire list) */
  1148.                         if (entry->stack_index == slot)
  1149.                                 entry->stack_index = 0;
  1150.                 }
  1151.         }
  1152.  
  1153.         *ns = stack[slot].ns;
  1154.         *type = stack[slot].type;
  1155.         *node = stack[slot].node;
  1156.  
  1157.         /** \todo reduce allocated stack size once there's enough free */
  1158.  
  1159.         treebuilder->context.current_node = slot - 1;
  1160.         assert((signed) treebuilder->context.current_node >= 0);
  1161.  
  1162.         return HUBBUB_OK;
  1163. }
  1164.  
  1165. /**
  1166.  * Pop elements until an element of type "element" has been popped.
  1167.  *
  1168.  * \return HUBBUB_OK on success, appropriate error otherwise.
  1169.  */
  1170. hubbub_error element_stack_pop_until(hubbub_treebuilder *treebuilder,
  1171.                 element_type type)
  1172. {
  1173.         element_type otype = UNKNOWN;
  1174.         void *node;
  1175.         hubbub_ns ns;
  1176.  
  1177.         while (otype != type) {
  1178.                 element_stack_pop(treebuilder, &ns, &otype, &node);
  1179.  
  1180.                 treebuilder->tree_handler->unref_node(
  1181.                                 treebuilder->tree_handler->ctx, node);
  1182.  
  1183.                 assert((signed) treebuilder->context.current_node >= 0);
  1184.         }
  1185.  
  1186.         return HUBBUB_OK;
  1187. }
  1188.  
  1189. /**
  1190.  * Remove a node from the stack of open elements
  1191.  *
  1192.  * \param treebuilder  The treebuilder instance
  1193.  * \param index        The index of the node to remove
  1194.  * \param ns           Pointer to location to receive namespace
  1195.  * \param type         Pointer to location to receive type
  1196.  * \param removed      Pointer to location to receive removed node
  1197.  * \return HUBBUB_OK on success, appropriate error otherwise.
  1198.  */
  1199. hubbub_error element_stack_remove(hubbub_treebuilder *treebuilder,
  1200.                 uint32_t index, hubbub_ns *ns, element_type *type,
  1201.                 void **removed)
  1202. {
  1203.         element_context *stack = treebuilder->context.element_stack;
  1204.         uint32_t n;
  1205.  
  1206.         assert(index <= treebuilder->context.current_node);
  1207.  
  1208.         /* Scan over subsequent entries in the stack,
  1209.          * searching for them in the list of active formatting
  1210.          * entries. If found, update the corresponding
  1211.          * formatting list entry's stack index to match the
  1212.          * new stack location */
  1213.         for (n = index + 1; n <= treebuilder->context.current_node; n++) {
  1214.                 if (is_formatting_element(stack[n].type) ||
  1215.                                 (is_scoping_element(stack[n].type) &&
  1216.                                 stack[n].type != HTML &&
  1217.                                 stack[n].type != TABLE)) {
  1218.                         formatting_list_entry *e;
  1219.  
  1220.                         for (e = treebuilder->context.formatting_list_end;
  1221.                                         e != NULL; e = e->prev) {
  1222.                                 if (e->stack_index == n)
  1223.                                         e->stack_index--;
  1224.                         }
  1225.                 }
  1226.         }
  1227.  
  1228.         *ns = stack[index].ns;
  1229.         *type = stack[index].type;
  1230.         *removed = stack[index].node;
  1231.  
  1232.         /* Now, shuffle the stack up one, removing node in the process */
  1233.         if (index < treebuilder->context.current_node) {
  1234.                 memmove(&stack[index], &stack[index + 1],
  1235.                                 (treebuilder->context.current_node - index) *
  1236.                                 sizeof(element_context));
  1237.         }
  1238.  
  1239.         treebuilder->context.current_node--;
  1240.  
  1241.         return HUBBUB_OK;
  1242. }
  1243.  
  1244. /**
  1245.  * Find the stack index of the current table.
  1246.  */
  1247. uint32_t current_table(hubbub_treebuilder *treebuilder)
  1248. {
  1249.         element_context *stack = treebuilder->context.element_stack;
  1250.         size_t t;
  1251.  
  1252.         for (t = treebuilder->context.current_node; t != 0; t--) {
  1253.                 if (stack[t].type == TABLE)
  1254.                         return t;
  1255.         }
  1256.  
  1257.         /* fragment case */
  1258.         return 0;
  1259. }
  1260.  
  1261. /**
  1262.  * Peek at the top element of the element stack.
  1263.  *
  1264.  * \param treebuilder  Treebuilder instance
  1265.  * \return Element type on the top of the stack
  1266.  */
  1267. element_type current_node(hubbub_treebuilder *treebuilder)
  1268. {
  1269.         return treebuilder->context.element_stack
  1270.                         [treebuilder->context.current_node].type;
  1271. }
  1272.  
  1273. /**
  1274.  * Peek at the element below the top of the element stack.
  1275.  *
  1276.  * \param treebuilder  Treebuilder instance
  1277.  * \return Element type of the element one below the top of the stack
  1278.  */
  1279. element_type prev_node(hubbub_treebuilder *treebuilder)
  1280. {
  1281.         if (treebuilder->context.current_node == 0)
  1282.                 return UNKNOWN;
  1283.  
  1284.         return treebuilder->context.element_stack
  1285.                         [treebuilder->context.current_node - 1].type;
  1286. }
  1287.  
  1288.  
  1289.  
  1290. /**
  1291.  * Append an element to the end of the list of active formatting elements
  1292.  *
  1293.  * \param treebuilder  Treebuilder instance containing list
  1294.  * \param ns           Namespace of node being inserted
  1295.  * \param type         Type of node being inserted
  1296.  * \param node         Node being inserted
  1297.  * \param stack_index  Index into stack of open elements
  1298.  * \return HUBBUB_OK on success, appropriate error otherwise
  1299.  */
  1300. hubbub_error formatting_list_append(hubbub_treebuilder *treebuilder,
  1301.                 hubbub_ns ns, element_type type, void *node,
  1302.                 uint32_t stack_index)
  1303. {
  1304.         formatting_list_entry *entry;
  1305.  
  1306.         entry = treebuilder->alloc(NULL, sizeof(formatting_list_entry),
  1307.                         treebuilder->alloc_pw);
  1308.         if (entry == NULL)
  1309.                 return HUBBUB_NOMEM;
  1310.  
  1311.         entry->details.ns = ns;
  1312.         entry->details.type = type;
  1313.         entry->details.node = node;
  1314.         entry->stack_index = stack_index;
  1315.  
  1316.         entry->prev = treebuilder->context.formatting_list_end;
  1317.         entry->next = NULL;
  1318.  
  1319.         if (entry->prev != NULL)
  1320.                 entry->prev->next = entry;
  1321.         else
  1322.                 treebuilder->context.formatting_list = entry;
  1323.  
  1324.         treebuilder->context.formatting_list_end = entry;
  1325.  
  1326.         return HUBBUB_OK;
  1327. }
  1328.  
  1329. /**
  1330.  * Insert an element into the list of active formatting elements
  1331.  *
  1332.  * \param treebuilder  Treebuilder instance containing list
  1333.  * \param prev         Previous entry
  1334.  * \param next         Next entry
  1335.  * \param ns           Namespace of node being inserted
  1336.  * \param type         Type of node being inserted
  1337.  * \param node         Node being inserted
  1338.  * \param stack_index  Index into stack of open elements
  1339.  * \return HUBBUB_OK on success, appropriate error otherwise
  1340.  */
  1341. hubbub_error formatting_list_insert(hubbub_treebuilder *treebuilder,
  1342.                 formatting_list_entry *prev, formatting_list_entry *next,
  1343.                 hubbub_ns ns, element_type type, void *node,
  1344.                 uint32_t stack_index)
  1345. {
  1346.         formatting_list_entry *entry;
  1347.  
  1348.         if (prev != NULL) {
  1349.                 assert(prev->next == next);
  1350.         }
  1351.  
  1352.         if (next != NULL) {
  1353.                 assert(next->prev == prev);
  1354.         }
  1355.  
  1356.         entry = treebuilder->alloc(NULL, sizeof(formatting_list_entry),
  1357.                         treebuilder->alloc_pw);
  1358.         if (entry == NULL)
  1359.                 return HUBBUB_NOMEM;
  1360.  
  1361.         entry->details.ns = ns;
  1362.         entry->details.type = type;
  1363.         entry->details.node = node;
  1364.         entry->stack_index = stack_index;
  1365.  
  1366.         entry->prev = prev;
  1367.         entry->next = next;
  1368.  
  1369.         if (entry->prev != NULL)
  1370.                 entry->prev->next = entry;
  1371.         else
  1372.                 treebuilder->context.formatting_list = entry;
  1373.  
  1374.         if (entry->next != NULL)
  1375.                 entry->next->prev = entry;
  1376.         else
  1377.                 treebuilder->context.formatting_list_end = entry;
  1378.  
  1379.         return HUBBUB_OK;
  1380. }
  1381.  
  1382.  
  1383. /**
  1384.  * Remove an element from the list of active formatting elements
  1385.  *
  1386.  * \param treebuilder  Treebuilder instance containing list
  1387.  * \param entry        The item to remove
  1388.  * \param ns           Pointer to location to receive namespace of node
  1389.  * \param type         Pointer to location to receive type of node
  1390.  * \param node         Pointer to location to receive node
  1391.  * \param stack_index  Pointer to location to receive stack index
  1392.  * \return HUBBUB_OK on success, appropriate error otherwise.
  1393.  */
  1394. hubbub_error formatting_list_remove(hubbub_treebuilder *treebuilder,
  1395.                 formatting_list_entry *entry,
  1396.                 hubbub_ns *ns, element_type *type, void **node,
  1397.                 uint32_t *stack_index)
  1398. {
  1399.         *ns = entry->details.ns;
  1400.         *type = entry->details.type;
  1401.         *node = entry->details.node;
  1402.         *stack_index = entry->stack_index;
  1403.  
  1404.         if (entry->prev == NULL)
  1405.                 treebuilder->context.formatting_list = entry->next;
  1406.         else
  1407.                 entry->prev->next = entry->next;
  1408.  
  1409.         if (entry->next == NULL)
  1410.                 treebuilder->context.formatting_list_end = entry->prev;
  1411.         else
  1412.                 entry->next->prev = entry->prev;
  1413.  
  1414.         treebuilder->alloc(entry, 0, treebuilder->alloc_pw);
  1415.  
  1416.         return HUBBUB_OK;
  1417. }
  1418.  
  1419. /**
  1420.  * Remove an element from the list of active formatting elements
  1421.  *
  1422.  * \param treebuilder   Treebuilder instance containing list
  1423.  * \param entry         The item to replace
  1424.  * \param ns            Replacement node namespace
  1425.  * \param type          Replacement node type
  1426.  * \param node          Replacement node
  1427.  * \param stack_index   Replacement stack index
  1428.  * \param ons           Pointer to location to receive old namespace
  1429.  * \param otype         Pointer to location to receive old type
  1430.  * \param onode         Pointer to location to receive old node
  1431.  * \param ostack_index  Pointer to location to receive old stack index
  1432.  * \return HUBBUB_OK on success, appropriate error otherwise
  1433.  */
  1434. hubbub_error formatting_list_replace(hubbub_treebuilder *treebuilder,
  1435.                 formatting_list_entry *entry,
  1436.                 hubbub_ns ns, element_type type, void *node,
  1437.                 uint32_t stack_index,
  1438.                 hubbub_ns *ons, element_type *otype, void **onode,
  1439.                 uint32_t *ostack_index)
  1440. {
  1441.         UNUSED(treebuilder);
  1442.  
  1443.         *ons = entry->details.ns;
  1444.         *otype = entry->details.type;
  1445.         *onode = entry->details.node;
  1446.         *ostack_index = entry->stack_index;
  1447.  
  1448.         entry->details.ns = ns;
  1449.         entry->details.type = type;
  1450.         entry->details.node = node;
  1451.         entry->stack_index = stack_index;
  1452.  
  1453.         return HUBBUB_OK;
  1454. }
  1455.  
  1456.  
  1457.  
  1458. #ifndef NDEBUG
  1459.  
  1460. /**
  1461.  * Dump an element stack to the given file pointer
  1462.  *
  1463.  * \param treebuilder  The treebuilder instance
  1464.  * \param fp           The file to dump to
  1465.  */
  1466. void element_stack_dump(hubbub_treebuilder *treebuilder, FILE *fp)
  1467. {
  1468.         element_context *stack = treebuilder->context.element_stack;
  1469.         uint32_t i;
  1470.  
  1471.         for (i = 0; i <= treebuilder->context.current_node; i++) {
  1472.                 fprintf(fp, "%u: %s %p\n",
  1473.                                 i,
  1474.                                 element_type_to_name(stack[i].type),
  1475.                                 stack[i].node);
  1476.         }
  1477. }
  1478.  
  1479. /**
  1480.  * Dump a formatting list to the given file pointer
  1481.  *
  1482.  * \param treebuilder  The treebuilder instance
  1483.  * \param fp           The file to dump to
  1484.  */
  1485. void formatting_list_dump(hubbub_treebuilder *treebuilder, FILE *fp)
  1486. {
  1487.         formatting_list_entry *entry;
  1488.  
  1489.         for (entry = treebuilder->context.formatting_list; entry != NULL;
  1490.                         entry = entry->next) {
  1491.                 fprintf(fp, "%s %p %u\n",
  1492.                                 element_type_to_name(entry->details.type),
  1493.                                 entry->details.node, entry->stack_index);
  1494.         }
  1495. }
  1496.  
  1497. /**
  1498.  * Convert an element type to a name
  1499.  *
  1500.  * \param type  The element type
  1501.  * \return Pointer to name
  1502.  */
  1503. const char *element_type_to_name(element_type type)
  1504. {
  1505.         size_t i;
  1506.  
  1507.         for (i = 0;
  1508.                         i < sizeof(name_type_map) / sizeof(name_type_map[0]);
  1509.                         i++) {
  1510.                 if (name_type_map[i].type == type)
  1511.                         return name_type_map[i].name;
  1512.         }
  1513.  
  1514.         return "UNKNOWN";
  1515. }
  1516. #endif
  1517.  
  1518.