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 LibCSS
  3.  * Licensed under the MIT License,
  4.  *                http://www.opensource.org/licenses/mit-license.php
  5.  * Copyright 2009 John-Mark Bell <jmb@netsurf-browser.org>
  6.  */
  7.  
  8. #include <assert.h>
  9. #include <string.h>
  10.  
  11. #include <libwapcaplet/libwapcaplet.h>
  12.  
  13. #include <libcss/select.h>
  14.  
  15. #include "bytecode/bytecode.h"
  16. #include "bytecode/opcodes.h"
  17. #include "stylesheet.h"
  18. #include "select/computed.h"
  19. #include "select/dispatch.h"
  20. #include "select/hash.h"
  21. #include "select/propset.h"
  22. #include "select/font_face.h"
  23. #include "select/select.h"
  24. #include "utils/parserutilserror.h"
  25. #include "utils/utils.h"
  26.  
  27. /* Define this to enable verbose messages when matching selector chains */
  28. #undef DEBUG_CHAIN_MATCHING
  29.  
  30. /**
  31.  * Container for stylesheet selection info
  32.  */
  33. typedef struct css_select_sheet {
  34.         const css_stylesheet *sheet;    /**< Stylesheet */
  35.         css_origin origin;              /**< Stylesheet origin */
  36.         uint64_t media;                 /**< Applicable media */
  37. } css_select_sheet;
  38.  
  39. /**
  40.  * CSS selection context
  41.  */
  42. struct css_select_ctx {
  43.         uint32_t n_sheets;              /**< Number of sheets */
  44.  
  45.         css_select_sheet *sheets;       /**< Array of sheets */
  46.  
  47.         css_allocator_fn alloc;         /**< Allocation routine */
  48.         void *pw;                       /**< Client-specific private data */
  49.  
  50.         /* Useful interned strings */
  51.         lwc_string *universal;
  52.         lwc_string *first_child;
  53.         lwc_string *link;
  54.         lwc_string *visited;
  55.         lwc_string *hover;
  56.         lwc_string *active;
  57.         lwc_string *focus;
  58.         lwc_string *nth_child;
  59.         lwc_string *nth_last_child;
  60.         lwc_string *nth_of_type;
  61.         lwc_string *nth_last_of_type;
  62.         lwc_string *last_child;
  63.         lwc_string *first_of_type;
  64.         lwc_string *last_of_type;
  65.         lwc_string *only_child;
  66.         lwc_string *only_of_type;
  67.         lwc_string *root;
  68.         lwc_string *empty;
  69.         lwc_string *target;
  70.         lwc_string *lang;
  71.         lwc_string *enabled;
  72.         lwc_string *disabled;
  73.         lwc_string *checked;
  74.         lwc_string *first_line;
  75.         lwc_string *first_letter;
  76.         lwc_string *before;
  77.         lwc_string *after;
  78. };
  79.  
  80. /**
  81.  * Container for selected font faces
  82.  */
  83. typedef struct css_select_font_faces_list {
  84.         const css_font_face **font_faces;
  85.         size_t count;
  86. } css_select_font_faces_list;
  87.  
  88. /**
  89.  * Font face selection state
  90.  */
  91. typedef struct css_select_font_faces_state {
  92.         lwc_string *font_family;
  93.         uint64_t media;
  94.  
  95.         css_select_font_faces_list ua_font_faces;
  96.         css_select_font_faces_list user_font_faces;
  97.         css_select_font_faces_list author_font_faces;
  98. } css_select_font_faces_state;
  99.  
  100. /**
  101.  * CSS rule source
  102.  */
  103. typedef struct css_select_rule_source {
  104.         enum {
  105.                 CSS_SELECT_RULE_SRC_ELEMENT,
  106.                 CSS_SELECT_RULE_SRC_CLASS,
  107.                 CSS_SELECT_RULE_SRC_ID,
  108.                 CSS_SELECT_RULE_SRC_UNIVERSAL
  109.         } source;
  110.         uint32_t class;
  111. } css_select_rule_source;
  112.  
  113.  
  114. static css_error set_hint(css_select_state *state, uint32_t prop);
  115. static css_error set_initial(css_select_state *state,
  116.                 uint32_t prop, css_pseudo_element pseudo,
  117.                 void *parent);
  118.  
  119. static css_error intern_strings(css_select_ctx *ctx);
  120. static void destroy_strings(css_select_ctx *ctx);
  121.  
  122. static css_error select_from_sheet(css_select_ctx *ctx,
  123.                 const css_stylesheet *sheet, css_origin origin,
  124.                 css_select_state *state);
  125. static css_error match_selectors_in_sheet(css_select_ctx *ctx,
  126.                 const css_stylesheet *sheet, css_select_state *state);
  127. static css_error match_selector_chain(css_select_ctx *ctx,
  128.                 const css_selector *selector, css_select_state *state);
  129. static css_error match_named_combinator(css_select_ctx *ctx,
  130.                 css_combinator type, const css_selector *selector,
  131.                 css_select_state *state, void *node, void **next_node);
  132. static css_error match_universal_combinator(css_select_ctx *ctx,
  133.                 css_combinator type, const css_selector *selector,
  134.                 css_select_state *state, void *node, bool may_optimise,
  135.                 bool *rejected_by_cache, void **next_node);
  136. static css_error match_details(css_select_ctx *ctx, void *node,
  137.                 const css_selector_detail *detail, css_select_state *state,
  138.                 bool *match, css_pseudo_element *pseudo_element);
  139. static css_error match_detail(css_select_ctx *ctx, void *node,
  140.                 const css_selector_detail *detail, css_select_state *state,
  141.                 bool *match, css_pseudo_element *pseudo_element);
  142. static css_error cascade_style(const css_style *style, css_select_state *state);
  143.  
  144. static css_error select_font_faces_from_sheet(css_select_ctx *ctx,
  145.                 const css_stylesheet *sheet,
  146.                 css_origin origin,
  147.                 css_select_font_faces_state *state);
  148.  
  149. #ifdef DEBUG_CHAIN_MATCHING
  150. static void dump_chain(const css_selector *selector);
  151. #endif
  152.  
  153.  
  154. /**
  155.  * Create a selection context
  156.  *
  157.  * \param alloc   Memory (de)allocation function
  158.  * \param pw      Client-specific private data
  159.  * \param result  Pointer to location to receive created context
  160.  * \return CSS_OK on success, appropriate error otherwise.
  161.  */
  162. css_error css_select_ctx_create(css_allocator_fn alloc, void *pw,
  163.                 css_select_ctx **result)
  164. {
  165.         css_select_ctx *c;
  166.         css_error error;
  167.  
  168.         if (alloc == NULL || result == NULL)
  169.                 return CSS_BADPARM;
  170.  
  171.         c = alloc(NULL, sizeof(css_select_ctx), pw);
  172.         if (c == NULL)
  173.                 return CSS_NOMEM;
  174.  
  175.         memset(c, 0, sizeof(css_select_ctx));
  176.  
  177.         error = intern_strings(c);
  178.         if (error != CSS_OK) {
  179.                 alloc(c, 0, pw);
  180.                 return error;
  181.         }
  182.  
  183.         c->alloc = alloc;
  184.         c->pw = pw;
  185.  
  186.         *result = c;
  187.  
  188.         return CSS_OK;
  189. }
  190.  
  191. /**
  192.  * Destroy a selection context
  193.  *
  194.  * \param ctx  The context to destroy
  195.  * \return CSS_OK on success, appropriate error otherwise
  196.  */
  197. css_error css_select_ctx_destroy(css_select_ctx *ctx)
  198. {
  199.         if (ctx == NULL)
  200.                 return CSS_BADPARM;
  201.  
  202.         destroy_strings(ctx);
  203.  
  204.         if (ctx->sheets != NULL)
  205.                 ctx->alloc(ctx->sheets, 0, ctx->pw);
  206.  
  207.         ctx->alloc(ctx, 0, ctx->pw);
  208.  
  209.         return CSS_OK;
  210. }
  211.  
  212. /**
  213.  * Append a stylesheet to a selection context
  214.  *
  215.  * \param ctx     The context to append to
  216.  * \param sheet   The sheet to append
  217.  * \param origin  Origin of the sheet
  218.  * \param media   Media types to which the sheet applies
  219.  * \return CSS_OK on success, appropriate error otherwise
  220.  */
  221. css_error css_select_ctx_append_sheet(css_select_ctx *ctx,
  222.                 const css_stylesheet *sheet, css_origin origin,
  223.                 uint64_t media)
  224. {
  225.         if (ctx == NULL || sheet == NULL)
  226.                 return CSS_BADPARM;
  227.  
  228.         return css_select_ctx_insert_sheet(ctx, sheet, ctx->n_sheets,
  229.                         origin, media);
  230. }
  231.  
  232. /**
  233.  * Insert a stylesheet into a selection context
  234.  *
  235.  * \param ctx    The context to insert into
  236.  * \param sheet  Sheet to insert
  237.  * \param index  Index in context to insert sheet
  238.  * \param origin  Origin of the sheet
  239.  * \param media   Media types to which the sheet applies
  240.  * \return CSS_OK on success, appropriate error otherwise
  241.  */
  242. css_error css_select_ctx_insert_sheet(css_select_ctx *ctx,
  243.                 const css_stylesheet *sheet, uint32_t index,
  244.                 css_origin origin, uint64_t media)
  245. {
  246.         css_select_sheet *temp;
  247.  
  248.         if (ctx == NULL || sheet == NULL)
  249.                 return CSS_BADPARM;
  250.  
  251.         /* Inline styles cannot be inserted into a selection context */
  252.         if (sheet->inline_style)
  253.                 return CSS_INVALID;
  254.  
  255.         /* Index must be in the range [0, n_sheets]
  256.          * The latter being equivalent to append */
  257.         if (index > ctx->n_sheets)
  258.                 return CSS_INVALID;
  259.  
  260.         temp = ctx->alloc(ctx->sheets,
  261.                         (ctx->n_sheets + 1) * sizeof(css_select_sheet),
  262.                         ctx->pw);
  263.         if (temp == NULL)
  264.                 return CSS_NOMEM;
  265.  
  266.         ctx->sheets = temp;
  267.  
  268.         if (index < ctx->n_sheets) {
  269.                 memmove(&ctx->sheets[index + 1], &ctx->sheets[index],
  270.                         (ctx->n_sheets - index) * sizeof(css_select_sheet));
  271.         }
  272.  
  273.         ctx->sheets[index].sheet = sheet;
  274.         ctx->sheets[index].origin = origin;
  275.         ctx->sheets[index].media = media;
  276.  
  277.         ctx->n_sheets++;
  278.  
  279.         return CSS_OK;
  280. }
  281.  
  282. /**
  283.  * Remove a sheet from a selection context
  284.  *
  285.  * \param ctx    The context to remove from
  286.  * \param sheet  Sheet to remove
  287.  * \return CSS_OK on success, appropriate error otherwise
  288.  */
  289. css_error css_select_ctx_remove_sheet(css_select_ctx *ctx,
  290.                 const css_stylesheet *sheet)
  291. {
  292.         uint32_t index;
  293.  
  294.         if (ctx == NULL || sheet == NULL)
  295.                 return CSS_BADPARM;
  296.  
  297.         for (index = 0; index < ctx->n_sheets; index++) {
  298.                 if (ctx->sheets[index].sheet == sheet)
  299.                         break;
  300.         }
  301.  
  302.         if (index == ctx->n_sheets)
  303.                 return CSS_INVALID;
  304.  
  305.         memmove(&ctx->sheets[index], &ctx->sheets[index + 1],
  306.                         (ctx->n_sheets - index) * sizeof(css_select_sheet));
  307.  
  308.         ctx->n_sheets--;
  309.  
  310.         return CSS_OK;
  311.  
  312. }
  313.  
  314. /**
  315.  * Count the number of top-level sheets in a selection context
  316.  *
  317.  * \param ctx    Context to consider
  318.  * \param count  Pointer to location to receive count of sheets
  319.  * \return CSS_OK on success, appropriate error otherwise
  320.  */
  321. css_error css_select_ctx_count_sheets(css_select_ctx *ctx, uint32_t *count)
  322. {
  323.         if (ctx == NULL || count == NULL)
  324.                 return CSS_BADPARM;
  325.  
  326.         *count = ctx->n_sheets;
  327.  
  328.         return CSS_OK;
  329. }
  330.  
  331. /**
  332.  * Retrieve a sheet from a selection context
  333.  *
  334.  * \param ctx    Context to look in
  335.  * \param index  Index in context to look
  336.  * \param sheet  Pointer to location to receive sheet
  337.  * \return CSS_OK on success, appropriate error otherwise
  338.  */
  339. css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
  340.                 const css_stylesheet **sheet)
  341. {
  342.         if (ctx == NULL || sheet == NULL)
  343.                 return CSS_BADPARM;
  344.  
  345.         if (index > ctx->n_sheets)
  346.                 return CSS_INVALID;
  347.  
  348.         *sheet = ctx->sheets[index].sheet;
  349.  
  350.         return CSS_OK;
  351. }
  352.  
  353. /**
  354.  * Select a style for the given node
  355.  *
  356.  * \param ctx             Selection context to use
  357.  * \param node            Node to select style for
  358.  * \param media           Currently active media types
  359.  * \param inline_style    Corresponding inline style for node, or NULL
  360.  * \param handler         Dispatch table of handler functions
  361.  * \param pw              Client-specific private data for handler functions
  362.  * \param result          Pointer to location to receive result set
  363.  * \return CSS_OK on success, appropriate error otherwise.
  364.  *
  365.  * In computing the style, no reference is made to the parent node's
  366.  * style. Therefore, the resultant computed style is not ready for
  367.  * immediate use, as some properties may be marked as inherited.
  368.  * Use css_computed_style_compose() to obtain a fully computed style.
  369.  *
  370.  * This two-step approach to style computation is designed to allow
  371.  * the client to store the partially computed style and efficiently
  372.  * update the fully computed style for a node when layout changes.
  373.  */
  374. css_error css_select_style(css_select_ctx *ctx, void *node,
  375.                 uint64_t media, const css_stylesheet *inline_style,
  376.                 css_select_handler *handler, void *pw,
  377.                 css_select_results **result)
  378. {
  379.         uint32_t i, j;
  380.         css_error error;
  381.         css_select_state state;
  382.         void *parent = NULL;
  383.  
  384.         if (ctx == NULL || node == NULL || result == NULL || handler == NULL ||
  385.                         handler->handler_version !=
  386.                                         CSS_SELECT_HANDLER_VERSION_1)
  387.                 return CSS_BADPARM;
  388.  
  389.         /* Set up the selection state */
  390.         memset(&state, 0, sizeof(css_select_state));
  391.         state.node = node;
  392.         state.media = media;
  393.         state.handler = handler;
  394.         state.pw = pw;
  395.         state.next_reject = state.reject_cache +
  396.                         (N_ELEMENTS(state.reject_cache) - 1);
  397.  
  398.         /* Allocate the result set */
  399.         state.results = ctx->alloc(NULL, sizeof(css_select_results), ctx->pw);
  400.         if (state.results == NULL)
  401.                 return CSS_NOMEM;
  402.  
  403.         state.results->alloc = ctx->alloc;
  404.         state.results->pw = ctx->pw;
  405.  
  406.         for (i = 0; i < CSS_PSEUDO_ELEMENT_COUNT; i++)
  407.                 state.results->styles[i] = NULL;
  408.  
  409.         /* Base element style is guaranteed to exist */
  410.         error = css_computed_style_create(ctx->alloc, ctx->pw,
  411.                         &state.results->styles[CSS_PSEUDO_ELEMENT_NONE]);
  412.         if (error != CSS_OK) {
  413.                 ctx->alloc(state.results, 0, ctx->pw);
  414.                 return error;
  415.         }
  416.  
  417.         error = handler->parent_node(pw, node, &parent);
  418.         if (error != CSS_OK)
  419.                 goto cleanup;
  420.  
  421.         /* Get node's name */
  422.         error = handler->node_name(pw, node, &state.element);
  423.         if (error != CSS_OK)
  424.                 return error;
  425.  
  426.         /* Get node's ID, if any */
  427.         error = handler->node_id(pw, node, &state.id);
  428.         if (error != CSS_OK)
  429.                 goto cleanup;
  430.  
  431.         /* Get node's classes, if any */
  432.         /** \todo Do we really want to force the client to allocate a new array
  433.          * every time we call this? It seems hugely inefficient, given they can
  434.          * cache the data. */
  435.         error = handler->node_classes(pw, node,
  436.                         &state.classes, &state.n_classes);
  437.         if (error != CSS_OK)
  438.                 goto cleanup;
  439.  
  440.         /* Iterate through the top-level stylesheets, selecting styles
  441.          * from those which apply to our current media requirements and
  442.          * are not disabled */
  443.         for (i = 0; i < ctx->n_sheets; i++) {
  444.                 const css_select_sheet s = ctx->sheets[i];
  445.  
  446.                 if ((s.media & media) != 0 &&
  447.                                 s.sheet->disabled == false) {
  448.                         error = select_from_sheet(ctx, s.sheet,
  449.                                         s.origin, &state);
  450.                         if (error != CSS_OK)
  451.                                 goto cleanup;
  452.                 }
  453.         }
  454.  
  455.         /* Consider any inline style for the node */
  456.         if (inline_style != NULL) {
  457.                 css_rule_selector *sel =
  458.                                 (css_rule_selector *) inline_style->rule_list;
  459.  
  460.                 /* Sanity check style */
  461.                 if (inline_style->rule_count != 1 ||
  462.                         inline_style->rule_list->type != CSS_RULE_SELECTOR ||
  463.                                 inline_style->rule_list->items != 0) {
  464.                         error = CSS_INVALID;
  465.                         goto cleanup;
  466.                 }
  467.  
  468.                 /* No bytecode if input was empty or wholly invalid */
  469.                 if (sel->style != NULL) {
  470.                         /* Inline style applies to base element only */
  471.                         state.current_pseudo = CSS_PSEUDO_ELEMENT_NONE;
  472.                         state.computed = state.results->styles[
  473.                                         CSS_PSEUDO_ELEMENT_NONE];
  474.  
  475.                         error = cascade_style(sel->style, &state);
  476.                         if (error != CSS_OK)
  477.                                 goto cleanup;
  478.                 }
  479.         }
  480.  
  481.         /* Take account of presentational hints and fix up any remaining
  482.          * unset properties. */
  483.  
  484.         /* Base element */
  485.         state.current_pseudo = CSS_PSEUDO_ELEMENT_NONE;
  486.         state.computed = state.results->styles[CSS_PSEUDO_ELEMENT_NONE];
  487.         for (i = 0; i < CSS_N_PROPERTIES; i++) {
  488.                 const prop_state *prop =
  489.                                 &state.props[i][CSS_PSEUDO_ELEMENT_NONE];
  490.  
  491.                 /* Apply presentational hints if the property is unset or
  492.                  * the existing property value did not come from an author
  493.                  * stylesheet or a user sheet using !important. */
  494.                 if (prop->set == false ||
  495.                                 (prop->origin != CSS_ORIGIN_AUTHOR &&
  496.                                 prop->important == false)) {
  497.                         error = set_hint(&state, i);
  498.                         if (error != CSS_OK)
  499.                                 goto cleanup;
  500.                 }
  501.  
  502.                 /* If the property is still unset or it's set to inherit
  503.                  * and we're the root element, then set it to its initial
  504.                  * value. */
  505.                 if (prop->set == false ||
  506.                                 (parent == NULL &&
  507.                                 prop->inherit == true)) {
  508.                         error = set_initial(&state, i,
  509.                                         CSS_PSEUDO_ELEMENT_NONE, parent);
  510.                         if (error != CSS_OK)
  511.                                 goto cleanup;
  512.                 }
  513.         }
  514.  
  515.         /* Pseudo elements, if any */
  516.         for (j = CSS_PSEUDO_ELEMENT_NONE + 1; j < CSS_PSEUDO_ELEMENT_COUNT; j++) {
  517.                 state.current_pseudo = j;
  518.                 state.computed = state.results->styles[j];
  519.  
  520.                 /* Skip non-existent pseudo elements */
  521.                 if (state.computed == NULL)
  522.                         continue;
  523.  
  524.                 for (i = 0; i < CSS_N_PROPERTIES; i++) {
  525.                         const prop_state *prop = &state.props[i][j];
  526.  
  527.                         /* If the property is still unset then set it
  528.                          * to its initial value. */
  529.                         if (prop->set == false) {
  530.                                 error = set_initial(&state, i, j, parent);
  531.                                 if (error != CSS_OK)
  532.                                         goto cleanup;
  533.                         }
  534.                 }
  535.         }
  536.  
  537.         /* If this is the root element, then we must ensure that all
  538.          * length values are absolute, display and float are correctly
  539.          * computed, and the default border-{top,right,bottom,left}-color
  540.          * is set to the computed value of color. */
  541.         if (parent == NULL) {
  542.                 /* Only compute absolute values for the base element */
  543.                 error = css__compute_absolute_values(NULL,
  544.                                 state.results->styles[CSS_PSEUDO_ELEMENT_NONE],
  545.                                 handler->compute_font_size, pw);
  546.                 if (error != CSS_OK)
  547.                         goto cleanup;
  548.         }
  549.  
  550.         *result = state.results;
  551.         error = CSS_OK;
  552.  
  553. cleanup:
  554.         /* Only clean up the results if there's an error.
  555.          * If there is no error, we're going to pass ownership of
  556.          * the results to the client */
  557.         if (error != CSS_OK && state.results != NULL) {
  558.                 css_select_results_destroy(state.results);
  559.         }
  560.  
  561.         if (state.classes != NULL) {
  562.                 for (i = 0; i < state.n_classes; i++)
  563.                         lwc_string_unref(state.classes[i]);
  564.  
  565.                 ctx->alloc(state.classes, 0, ctx->pw);
  566.         }
  567.  
  568.         if (state.id != NULL)
  569.                 lwc_string_unref(state.id);
  570.  
  571.         if (state.element.ns != NULL)
  572.                 lwc_string_unref(state.element.ns);
  573.         lwc_string_unref(state.element.name);
  574.  
  575.         return error;
  576. }
  577.  
  578. /**
  579.  * Destroy a selection result set
  580.  *
  581.  * \param results  Result set to destroy
  582.  * \return CSS_OK on success, appropriate error otherwise
  583.  */
  584. css_error css_select_results_destroy(css_select_results *results)
  585. {
  586.         uint32_t i;
  587.  
  588.         if (results == NULL)
  589.                 return CSS_BADPARM;
  590.  
  591.         if (results->styles != NULL) {
  592.                 for (i = 0; i < CSS_PSEUDO_ELEMENT_COUNT; i++) {
  593.                         if (results->styles[i] != NULL)
  594.                                 css_computed_style_destroy(results->styles[i]);
  595.                 }
  596.         }
  597.  
  598.         results->alloc(results, 0, results->pw);
  599.  
  600.         return CSS_OK;
  601. }
  602.  
  603. /**
  604.  * Search a selection context for defined font faces
  605.  *
  606.  * \param ctx          Selection context
  607.  * \param media        Currently active media types
  608.  * \param font_family  Font family to search for
  609.  * \param result       Pointer to location to receive result
  610.  * \return CSS_OK on success, appropriate error otherwise.
  611.  */
  612. css_error css_select_font_faces(css_select_ctx *ctx,
  613.                 uint64_t media, lwc_string *font_family,
  614.                 css_select_font_faces_results **result)
  615. {
  616.         uint32_t i;
  617.         css_error error;
  618.         css_select_font_faces_state state;
  619.         uint32_t n_font_faces;
  620.        
  621.         if (ctx == NULL || font_family == NULL || result == NULL)
  622.                 return CSS_BADPARM;
  623.  
  624.         memset(&state, 0, sizeof(css_select_font_faces_state));
  625.         state.font_family = font_family;
  626.         state.media = media;
  627.        
  628.         /* Iterate through the top-level stylesheets, selecting font-faces
  629.          * from those which apply to our current media requirements and
  630.          * are not disabled */
  631.         for (i = 0; i < ctx->n_sheets; i++) {
  632.                 const css_select_sheet s = ctx->sheets[i];
  633.                
  634.                 if ((s.media & media) != 0 &&
  635.                                 s.sheet->disabled == false) {
  636.                         error = select_font_faces_from_sheet(ctx, s.sheet,
  637.                                         s.origin, &state);
  638.                         if (error != CSS_OK)
  639.                                 goto cleanup;
  640.                 }
  641.         }
  642.        
  643.         n_font_faces = state.ua_font_faces.count +
  644.                         state.user_font_faces.count +
  645.                         state.author_font_faces.count;
  646.                                
  647.        
  648.         if (n_font_faces > 0) {
  649.                 /* We found some matching faces.  Make a results structure with
  650.                  * the font faces in priority order. */
  651.                 css_select_font_faces_results *results;
  652.                
  653.                 results = ctx->alloc(NULL,
  654.                                 sizeof(css_select_font_faces_results),
  655.                                 ctx->pw);
  656.                 if (results == NULL) {
  657.                         error = CSS_NOMEM;
  658.                         goto cleanup;
  659.                 }
  660.                
  661.                 results->alloc = ctx->alloc;
  662.                 results->pw = ctx->pw;
  663.                
  664.                 results->font_faces = ctx->alloc(NULL,
  665.                                 n_font_faces * sizeof(css_font_face *),
  666.                                 ctx->pw);
  667.                 if (results->font_faces == NULL) {
  668.                         ctx->alloc(results, 0, ctx->pw);
  669.                         error = CSS_NOMEM;
  670.                         goto cleanup;
  671.                 }
  672.  
  673.                 results->n_font_faces = n_font_faces;
  674.                
  675.                 i = 0;
  676.                 if (state.ua_font_faces.count != 0) {
  677.                         memcpy(results->font_faces,
  678.                                         state.ua_font_faces.font_faces,
  679.                                         sizeof(css_font_face *) *
  680.                                                 state.ua_font_faces.count);
  681.                        
  682.                         i += state.ua_font_faces.count;
  683.                 }
  684.                                
  685.                 if (state.user_font_faces.count != 0) {
  686.                         memcpy(results->font_faces + i,
  687.                                         state.user_font_faces.font_faces,
  688.                                         sizeof(css_font_face *) *
  689.                                                 state.user_font_faces.count);
  690.                         i += state.user_font_faces.count;
  691.                 }
  692.                
  693.                 if (state.author_font_faces.count != 0) {
  694.                         memcpy(results->font_faces + i,
  695.                                         state.author_font_faces.font_faces,
  696.                                         sizeof(css_font_face *) *
  697.                                                 state.author_font_faces.count);
  698.                 }
  699.  
  700.                 *result = results;
  701.         }
  702.        
  703.         error = CSS_OK;
  704.        
  705. cleanup:
  706.         if (state.ua_font_faces.count != 0)
  707.                 ctx->alloc(state.ua_font_faces.font_faces, 0, ctx->pw);
  708.  
  709.         if (state.user_font_faces.count != 0)
  710.                 ctx->alloc(state.user_font_faces.font_faces, 0, ctx->pw);
  711.        
  712.         if (state.author_font_faces.count != 0)
  713.                 ctx->alloc(state.author_font_faces.font_faces, 0, ctx->pw);
  714.        
  715.         return error;
  716. }
  717.  
  718. /**
  719.  * Destroy a font-face result set
  720.  *
  721.  * \param results  Result set to destroy
  722.  * \return CSS_OK on success, appropriate error otherwise
  723.  */
  724. css_error css_select_font_faces_results_destroy(
  725.                 css_select_font_faces_results *results)
  726. {
  727.         if (results == NULL)
  728.                 return CSS_BADPARM;
  729.        
  730.         if (results->font_faces != NULL) {
  731.                 /* Don't destroy the individual css_font_faces, they're owned
  732.                    by their respective sheets */
  733.                 results->alloc(results->font_faces, 0, results->pw);
  734.         }
  735.        
  736.         results->alloc(results, 0, results->pw);
  737.        
  738.         return CSS_OK;
  739. }
  740.  
  741. /******************************************************************************
  742.  * Selection engine internals below here                                      *
  743.  ******************************************************************************/
  744.  
  745. css_error intern_strings(css_select_ctx *ctx)
  746. {
  747.         lwc_error error;
  748.  
  749.         /* Universal selector */
  750.         error = lwc_intern_string("*", SLEN("*"), &ctx->universal);
  751.         if (error != lwc_error_ok)
  752.                 return css_error_from_lwc_error(error);
  753.  
  754.         /* Pseudo classes */
  755.         error = lwc_intern_string(
  756.                         "first-child", SLEN("first-child"),
  757.                         &ctx->first_child);
  758.         if (error != lwc_error_ok)
  759.                 return css_error_from_lwc_error(error);
  760.  
  761.         error = lwc_intern_string(
  762.                         "link", SLEN("link"),
  763.                         &ctx->link);
  764.         if (error != lwc_error_ok)
  765.                 return css_error_from_lwc_error(error);
  766.  
  767.         error = lwc_intern_string(
  768.                         "visited", SLEN("visited"),
  769.                         &ctx->visited);
  770.         if (error != lwc_error_ok)
  771.                 return css_error_from_lwc_error(error);
  772.  
  773.         error = lwc_intern_string(
  774.                         "hover", SLEN("hover"),
  775.                         &ctx->hover);
  776.         if (error != lwc_error_ok)
  777.                 return css_error_from_lwc_error(error);
  778.  
  779.         error = lwc_intern_string(
  780.                         "active", SLEN("active"),
  781.                         &ctx->active);
  782.         if (error != lwc_error_ok)
  783.                 return css_error_from_lwc_error(error);
  784.  
  785.         error = lwc_intern_string(
  786.                         "focus", SLEN("focus"),
  787.                         &ctx->focus);
  788.         if (error != lwc_error_ok)
  789.                 return css_error_from_lwc_error(error);
  790.  
  791.         error = lwc_intern_string(
  792.                         "nth-child", SLEN("nth-child"),
  793.                         &ctx->nth_child);
  794.         if (error != lwc_error_ok)
  795.                 return css_error_from_lwc_error(error);
  796.  
  797.         error = lwc_intern_string(
  798.                         "nth-last-child", SLEN("nth-last-child"),
  799.                         &ctx->nth_last_child);
  800.         if (error != lwc_error_ok)
  801.                 return css_error_from_lwc_error(error);
  802.  
  803.         error = lwc_intern_string(
  804.                         "nth-of-type", SLEN("nth-of-type"),
  805.                         &ctx->nth_of_type);
  806.         if (error != lwc_error_ok)
  807.                 return css_error_from_lwc_error(error);
  808.  
  809.         error = lwc_intern_string(
  810.                         "nth-last-of-type", SLEN("nth-last-of-type"),
  811.                         &ctx->nth_last_of_type);
  812.         if (error != lwc_error_ok)
  813.                 return css_error_from_lwc_error(error);
  814.  
  815.         error = lwc_intern_string(
  816.                         "last-child", SLEN("last-child"),
  817.                         &ctx->last_child);
  818.         if (error != lwc_error_ok)
  819.                 return css_error_from_lwc_error(error);
  820.  
  821.         error = lwc_intern_string(
  822.                         "first-of-type", SLEN("first-of-type"),
  823.                         &ctx->first_of_type);
  824.         if (error != lwc_error_ok)
  825.                 return css_error_from_lwc_error(error);
  826.  
  827.         error = lwc_intern_string(
  828.                         "last-of-type", SLEN("last-of-type"),
  829.                         &ctx->last_of_type);
  830.         if (error != lwc_error_ok)
  831.                 return css_error_from_lwc_error(error);
  832.  
  833.         error = lwc_intern_string(
  834.                         "only-child", SLEN("only-child"),
  835.                         &ctx->only_child);
  836.         if (error != lwc_error_ok)
  837.                 return css_error_from_lwc_error(error);
  838.  
  839.         error = lwc_intern_string(
  840.                         "only-of-type", SLEN("only-of-type"),
  841.                         &ctx->only_of_type);
  842.         if (error != lwc_error_ok)
  843.                 return css_error_from_lwc_error(error);
  844.  
  845.         error = lwc_intern_string(
  846.                         "root", SLEN("root"),
  847.                         &ctx->root);
  848.         if (error != lwc_error_ok)
  849.                 return css_error_from_lwc_error(error);
  850.  
  851.         error = lwc_intern_string(
  852.                         "empty", SLEN("empty"),
  853.                         &ctx->empty);
  854.         if (error != lwc_error_ok)
  855.                 return css_error_from_lwc_error(error);
  856.  
  857.         error = lwc_intern_string(
  858.                         "target", SLEN("target"),
  859.                         &ctx->target);
  860.         if (error != lwc_error_ok)
  861.                 return css_error_from_lwc_error(error);
  862.  
  863.         error = lwc_intern_string(
  864.                         "lang", SLEN("lang"),
  865.                         &ctx->lang);
  866.         if (error != lwc_error_ok)
  867.                 return css_error_from_lwc_error(error);
  868.  
  869.         error = lwc_intern_string(
  870.                         "enabled", SLEN("enabled"),
  871.                         &ctx->enabled);
  872.         if (error != lwc_error_ok)
  873.                 return css_error_from_lwc_error(error);
  874.  
  875.         error = lwc_intern_string(
  876.                         "disabled", SLEN("disabled"),
  877.                         &ctx->disabled);
  878.         if (error != lwc_error_ok)
  879.                 return css_error_from_lwc_error(error);
  880.  
  881.         error = lwc_intern_string(
  882.                         "checked", SLEN("checked"),
  883.                         &ctx->checked);
  884.         if (error != lwc_error_ok)
  885.                 return css_error_from_lwc_error(error);
  886.  
  887.         /* Pseudo elements */
  888.         error = lwc_intern_string(
  889.                         "first-line", SLEN("first-line"),
  890.                         &ctx->first_line);
  891.         if (error != lwc_error_ok)
  892.                 return css_error_from_lwc_error(error);
  893.  
  894.         error = lwc_intern_string(
  895.                         "first_letter", SLEN("first-letter"),
  896.                         &ctx->first_letter);
  897.         if (error != lwc_error_ok)
  898.                 return css_error_from_lwc_error(error);
  899.  
  900.         error = lwc_intern_string(
  901.                         "before", SLEN("before"),
  902.                         &ctx->before);
  903.         if (error != lwc_error_ok)
  904.                 return css_error_from_lwc_error(error);
  905.  
  906.         error = lwc_intern_string(
  907.                         "after", SLEN("after"),
  908.                         &ctx->after);
  909.         if (error != lwc_error_ok)
  910.                 return css_error_from_lwc_error(error);
  911.  
  912.         return CSS_OK;
  913. }
  914.  
  915. void destroy_strings(css_select_ctx *ctx)
  916. {
  917.         if (ctx->universal != NULL)
  918.                 lwc_string_unref(ctx->universal);
  919.         if (ctx->first_child != NULL)
  920.                 lwc_string_unref(ctx->first_child);
  921.         if (ctx->link != NULL)
  922.                 lwc_string_unref(ctx->link);
  923.         if (ctx->visited != NULL)
  924.                 lwc_string_unref(ctx->visited);
  925.         if (ctx->hover != NULL)
  926.                 lwc_string_unref(ctx->hover);
  927.         if (ctx->active != NULL)
  928.                 lwc_string_unref(ctx->active);
  929.         if (ctx->focus != NULL)
  930.                 lwc_string_unref(ctx->focus);
  931.         if (ctx->nth_child != NULL)
  932.                 lwc_string_unref(ctx->nth_child);
  933.         if (ctx->nth_last_child != NULL)
  934.                 lwc_string_unref(ctx->nth_last_child);
  935.         if (ctx->nth_of_type != NULL)
  936.                 lwc_string_unref(ctx->nth_of_type);
  937.         if (ctx->nth_last_of_type != NULL)
  938.                 lwc_string_unref(ctx->nth_last_of_type);
  939.         if (ctx->last_child != NULL)
  940.                 lwc_string_unref(ctx->last_child);
  941.         if (ctx->first_of_type != NULL)
  942.                 lwc_string_unref(ctx->first_of_type);
  943.         if (ctx->last_of_type != NULL)
  944.                 lwc_string_unref(ctx->last_of_type);
  945.         if (ctx->only_child != NULL)
  946.                 lwc_string_unref(ctx->only_child);
  947.         if (ctx->only_of_type != NULL)
  948.                 lwc_string_unref(ctx->only_of_type);
  949.         if (ctx->root != NULL)
  950.                 lwc_string_unref(ctx->root);
  951.         if (ctx->empty != NULL)
  952.                 lwc_string_unref(ctx->empty);
  953.         if (ctx->target != NULL)
  954.                 lwc_string_unref(ctx->target);
  955.         if (ctx->lang != NULL)
  956.                 lwc_string_unref(ctx->lang);
  957.         if (ctx->enabled != NULL)
  958.                 lwc_string_unref(ctx->enabled);
  959.         if (ctx->disabled != NULL)
  960.                 lwc_string_unref(ctx->disabled);
  961.         if (ctx->checked != NULL)
  962.                 lwc_string_unref(ctx->checked);
  963.         if (ctx->first_line != NULL)
  964.                 lwc_string_unref(ctx->first_line);
  965.         if (ctx->first_letter != NULL)
  966.                 lwc_string_unref(ctx->first_letter);
  967.         if (ctx->before != NULL)
  968.                 lwc_string_unref(ctx->before);
  969.         if (ctx->after != NULL)
  970.                 lwc_string_unref(ctx->after);
  971. }
  972.  
  973. css_error set_hint(css_select_state *state, uint32_t prop)
  974. {
  975.         css_hint hint;
  976.         css_error error;
  977.  
  978.         /* Initialise hint */
  979.         memset(&hint, 0, sizeof(css_hint));
  980.  
  981.         /* Retrieve this property's hint from the client */
  982.         error = state->handler->node_presentational_hint(state->pw,
  983.                         state->node, prop, &hint);
  984.         if (error != CSS_OK)
  985.                 return (error == CSS_PROPERTY_NOT_SET) ? CSS_OK : error;
  986.  
  987.         /* Hint defined -- set it in the result */
  988.         error = prop_dispatch[prop].set_from_hint(&hint, state->computed);
  989.         if (error != CSS_OK)
  990.                 return error;
  991.  
  992.         /* Keep selection state in sync with reality */
  993.         state->props[prop][CSS_PSEUDO_ELEMENT_NONE].set = 1;
  994.         state->props[prop][CSS_PSEUDO_ELEMENT_NONE].specificity = 0;
  995.         state->props[prop][CSS_PSEUDO_ELEMENT_NONE].origin = CSS_ORIGIN_AUTHOR;
  996.         state->props[prop][CSS_PSEUDO_ELEMENT_NONE].important = 0;
  997.         state->props[prop][CSS_PSEUDO_ELEMENT_NONE].inherit =
  998.                         (hint.status == 0);
  999.  
  1000.         return CSS_OK;
  1001. }
  1002.  
  1003. css_error set_initial(css_select_state *state,
  1004.                 uint32_t prop, css_pseudo_element pseudo,
  1005.                 void *parent)
  1006. {
  1007.         css_error error;
  1008.  
  1009.         /* Do nothing if this property is inherited (the default state
  1010.          * of a clean computed style is for everything to be set to inherit)
  1011.          *
  1012.          * If the node is tree root and we're dealing with the base element,
  1013.          * everything should be defaulted.
  1014.          */
  1015.         if (prop_dispatch[prop].inherited == false ||
  1016.                         (pseudo == CSS_PSEUDO_ELEMENT_NONE && parent == NULL)) {
  1017.                 enum prop_group group = prop_dispatch[prop].group;
  1018.  
  1019.                 /* Remaining properties are neither inherited nor
  1020.                  * already set. Thus, we set them to their initial
  1021.                  * values here. Except, however, if the property in
  1022.                  * question resides in one of the extension blocks and
  1023.                  * the extension block has yet to be allocated. In that
  1024.                  * case, we do nothing and leave it to the property
  1025.                  * accessors to return the initial values for the
  1026.                  * property.
  1027.                  */
  1028.                 if (group == GROUP_NORMAL) {
  1029.                         error = prop_dispatch[prop].initial(state);
  1030.                         if (error != CSS_OK)
  1031.                                 return error;
  1032.                 } else if (group == GROUP_UNCOMMON &&
  1033.                                 state->computed->uncommon != NULL) {
  1034.                         error = prop_dispatch[prop].initial(state);
  1035.                         if (error != CSS_OK)
  1036.                                 return error;
  1037.                 } else if (group == GROUP_PAGE &&
  1038.                                 state->computed->page != NULL) {
  1039.                         error = prop_dispatch[prop].initial(state);
  1040.                         if (error != CSS_OK)
  1041.                                 return error;
  1042.                 } else if (group == GROUP_AURAL &&
  1043.                                 state->computed->aural != NULL) {
  1044.                         error = prop_dispatch[prop].initial(state);
  1045.                         if (error != CSS_OK)
  1046.                                 return error;
  1047.                 }
  1048.         }
  1049.  
  1050.         return CSS_OK;
  1051. }
  1052.  
  1053. #define IMPORT_STACK_SIZE 256
  1054.  
  1055. css_error select_from_sheet(css_select_ctx *ctx, const css_stylesheet *sheet,
  1056.                 css_origin origin, css_select_state *state)
  1057. {
  1058.         const css_stylesheet *s = sheet;
  1059.         const css_rule *rule = s->rule_list;
  1060.         uint32_t sp = 0;
  1061.         const css_rule *import_stack[IMPORT_STACK_SIZE];
  1062.  
  1063.         do {
  1064.                 /* Find first non-charset rule, if we're at the list head */
  1065.                 if (rule == s->rule_list) {
  1066.                         while (rule != NULL && rule->type == CSS_RULE_CHARSET)
  1067.                                 rule = rule->next;
  1068.                 }
  1069.  
  1070.                 if (rule != NULL && rule->type == CSS_RULE_IMPORT) {
  1071.                         /* Current rule is an import */
  1072.                         const css_rule_import *import =
  1073.                                         (const css_rule_import *) rule;
  1074.  
  1075.                         if (import->sheet != NULL &&
  1076.                                         (import->media & state->media) != 0) {
  1077.                                 /* It's applicable, so process it */
  1078.                                 if (sp >= IMPORT_STACK_SIZE)
  1079.                                         return CSS_NOMEM;
  1080.  
  1081.                                 import_stack[sp++] = rule;
  1082.  
  1083.                                 s = import->sheet;
  1084.                                 rule = s->rule_list;
  1085.                         } else {
  1086.                                 /* Not applicable; skip over it */
  1087.                                 rule = rule->next;
  1088.                         }
  1089.                 } else {
  1090.                         /* Gone past import rules in this sheet */
  1091.                         css_error error;
  1092.  
  1093.                         /* Process this sheet */
  1094.                         state->sheet = s;
  1095.                         state->current_origin = origin;
  1096.  
  1097.                         error = match_selectors_in_sheet(ctx, s, state);
  1098.                         if (error != CSS_OK)
  1099.                                 return error;
  1100.  
  1101.                         /* Find next sheet to process */
  1102.                         if (sp > 0) {
  1103.                                 sp--;
  1104.                                 rule = import_stack[sp]->next;
  1105.                                 s = import_stack[sp]->parent;
  1106.                         } else {
  1107.                                 s = NULL;
  1108.                         }
  1109.                 }
  1110.         } while (s != NULL);
  1111.  
  1112.         return CSS_OK;
  1113. }
  1114.  
  1115. static inline bool _rule_applies_to_media(const css_rule *rule, uint64_t media)
  1116. {
  1117.         bool applies = true;
  1118.         const css_rule *ancestor = rule;
  1119.  
  1120.         while (ancestor != NULL) {
  1121.                 const css_rule_media *m = (const css_rule_media *) ancestor;
  1122.  
  1123.                 if (ancestor->type == CSS_RULE_MEDIA &&
  1124.                                 (m->media & media) == 0) {
  1125.                         applies = false;
  1126.                         break;
  1127.                 }
  1128.  
  1129.                 if (ancestor->ptype != CSS_RULE_PARENT_STYLESHEET)
  1130.                         ancestor = ancestor->parent;
  1131.                 else
  1132.                         ancestor = NULL;
  1133.         }
  1134.  
  1135.         return applies;
  1136. }
  1137.  
  1138. static css_error _select_font_face_from_rule(css_select_ctx *ctx,
  1139.                 const css_rule_font_face *rule, css_origin origin,
  1140.                 css_select_font_faces_state *state)
  1141. {
  1142.         if (_rule_applies_to_media((const css_rule *) rule, state->media)) {
  1143.                 bool correct_family = false;
  1144.  
  1145.                 if (lwc_string_isequal(
  1146.                                 rule->font_face->font_family,
  1147.                                 state->font_family,
  1148.                                 &correct_family) == lwc_error_ok &&
  1149.                                 correct_family) {
  1150.                         css_select_font_faces_list *faces = NULL;
  1151.                         const css_font_face **new_faces;
  1152.                         uint32_t index;
  1153.                         size_t new_size;
  1154.  
  1155.                         switch (origin) {
  1156.                                 case CSS_ORIGIN_UA:
  1157.                                         faces = &state->ua_font_faces;
  1158.                                         break;
  1159.                                 case CSS_ORIGIN_USER:
  1160.                                         faces = &state->user_font_faces;
  1161.                                         break;
  1162.                                 case CSS_ORIGIN_AUTHOR:
  1163.                                         faces = &state->author_font_faces;
  1164.                                         break;
  1165.                         }
  1166.                        
  1167.                         index = faces->count++;                
  1168.                         new_size = faces->count * sizeof(css_font_face *);
  1169.                        
  1170.                         new_faces = ctx->alloc(faces->font_faces,
  1171.                                         new_size, ctx->pw);
  1172.                         if (new_faces == NULL) {
  1173.                                 faces->count = 0;
  1174.                                 return CSS_NOMEM;
  1175.                         }
  1176.                         faces->font_faces = new_faces;
  1177.                        
  1178.                         faces->font_faces[index] = rule->font_face;
  1179.                 }
  1180.         }
  1181.  
  1182.         return CSS_OK;
  1183. }
  1184.  
  1185. static css_error select_font_faces_from_sheet(css_select_ctx *ctx,
  1186.                 const css_stylesheet *sheet,
  1187.                 css_origin origin,
  1188.                 css_select_font_faces_state *state)
  1189. {
  1190.         const css_stylesheet *s = sheet;
  1191.         const css_rule *rule = s->rule_list;
  1192.         uint32_t sp = 0;
  1193.         const css_rule *import_stack[IMPORT_STACK_SIZE];
  1194.        
  1195.         do {
  1196.                 /* Find first non-charset rule, if we're at the list head */
  1197.                 if (rule == s->rule_list) {
  1198.                         while (rule != NULL && rule->type == CSS_RULE_CHARSET)
  1199.                                 rule = rule->next;
  1200.                 }
  1201.                
  1202.                 if (rule != NULL && rule->type == CSS_RULE_IMPORT) {
  1203.                         /* Current rule is an import */
  1204.                         const css_rule_import *import =
  1205.                                         (const css_rule_import *) rule;
  1206.                        
  1207.                         if (import->sheet != NULL &&
  1208.                                         (import->media & state->media) != 0) {
  1209.                                 /* It's applicable, so process it */
  1210.                                 if (sp >= IMPORT_STACK_SIZE)
  1211.                                         return CSS_NOMEM;
  1212.                                
  1213.                                 import_stack[sp++] = rule;
  1214.                                
  1215.                                 s = import->sheet;
  1216.                                 rule = s->rule_list;
  1217.                         } else {
  1218.                                 /* Not applicable; skip over it */
  1219.                                 rule = rule->next;
  1220.                         }
  1221.                 } else if (rule != NULL && rule->type == CSS_RULE_FONT_FACE) {
  1222.                         css_error error;
  1223.                        
  1224.                         error = _select_font_face_from_rule(
  1225.                                         ctx,
  1226.                                         (const css_rule_font_face *) rule,
  1227.                                         origin,
  1228.                                         state);
  1229.                        
  1230.                         if (error != CSS_OK)
  1231.                                 return error;
  1232.                        
  1233.                         rule = rule->next;
  1234.                 } else if (rule == NULL) {
  1235.                         /* Find next sheet to process */
  1236.                         if (sp > 0) {
  1237.                                 sp--;
  1238.                                 rule = import_stack[sp]->next;
  1239.                                 s = import_stack[sp]->parent;
  1240.                         } else {
  1241.                                 s = NULL;
  1242.                         }
  1243.                 } else {
  1244.                         rule = rule->next;
  1245.                 }
  1246.         } while (s != NULL);
  1247.        
  1248.         return CSS_OK;
  1249. }
  1250.  
  1251. #undef IMPORT_STACK_SIZE
  1252.  
  1253. static inline bool _selectors_pending(const css_selector **node,
  1254.                 const css_selector **id, const css_selector ***classes,
  1255.                 uint32_t n_classes, const css_selector **univ)
  1256. {
  1257.         bool pending = false;
  1258.         uint32_t i;
  1259.  
  1260.         pending |= *node != NULL;
  1261.         pending |= *id != NULL;
  1262.         pending |= *univ != NULL;
  1263.  
  1264.         if (classes != NULL && n_classes > 0) {
  1265.                 for (i = 0; i < n_classes; i++)
  1266.                         pending |= *(classes[i]) != NULL;
  1267.         }
  1268.  
  1269.         return pending;
  1270. }
  1271.  
  1272. static inline bool _selector_less_specific(const css_selector *ref,
  1273.                 const css_selector *cand)
  1274. {
  1275.         bool result = true;
  1276.  
  1277.         if (cand == NULL)
  1278.                 return false;
  1279.  
  1280.         if (ref == NULL)
  1281.                 return true;
  1282.  
  1283.         /* Sort by specificity */
  1284.         if (cand->specificity < ref->specificity) {
  1285.                 result = true;
  1286.         } else if (ref->specificity < cand->specificity) {
  1287.                 result = false;
  1288.         } else {
  1289.                 /* Then by rule index -- earliest wins */
  1290.                 if (cand->rule->index < ref->rule->index)
  1291.                         result = true;
  1292.                 else
  1293.                         result = false;
  1294.         }
  1295.  
  1296.         return result;
  1297. }
  1298.  
  1299. static const css_selector *_selector_next(const css_selector **node,
  1300.                 const css_selector **id, const css_selector ***classes,
  1301.                 uint32_t n_classes, const css_selector **univ,
  1302.                 css_select_rule_source *src)
  1303. {
  1304.         const css_selector *ret = NULL;
  1305.  
  1306.         if (_selector_less_specific(ret, *node)) {
  1307.                 ret = *node;
  1308.                 src->source = CSS_SELECT_RULE_SRC_ELEMENT;
  1309.         }
  1310.  
  1311.         if (_selector_less_specific(ret, *id)) {
  1312.                 ret = *id;
  1313.                 src->source = CSS_SELECT_RULE_SRC_ID;
  1314.         }
  1315.  
  1316.         if (_selector_less_specific(ret, *univ)) {
  1317.                 ret = *univ;
  1318.                 src->source = CSS_SELECT_RULE_SRC_UNIVERSAL;
  1319.         }
  1320.  
  1321.         if (classes != NULL && n_classes > 0) {
  1322.                 uint32_t i;
  1323.  
  1324.                 for (i = 0; i < n_classes; i++) {
  1325.                         if (_selector_less_specific(ret, *(classes[i]))) {
  1326.                                 ret = *(classes[i]);
  1327.                                 src->source = CSS_SELECT_RULE_SRC_CLASS;
  1328.                                 src->class = i;
  1329.                         }
  1330.                 }
  1331.         }
  1332.  
  1333.         return ret;
  1334. }
  1335.  
  1336. static bool _rule_good_for_element_name(const css_selector *selector,
  1337.                 css_select_rule_source *src, css_select_state *state)
  1338. {
  1339.         /* If source of rule is element or universal hash, we know the
  1340.          * element name is a match.  If it comes from the class or id hash,
  1341.          * we have to test for a match */
  1342.         if (src->source == CSS_SELECT_RULE_SRC_ID ||
  1343.                         src->source == CSS_SELECT_RULE_SRC_CLASS) {
  1344.                 if (lwc_string_length(selector->data.qname.name) != 1 ||
  1345.                                 lwc_string_data(
  1346.                                         selector->data.qname.name)[0] != '*') {
  1347.                         bool match;
  1348.                         if (lwc_string_caseless_isequal(
  1349.                                         selector->data.qname.name,
  1350.                                         state->element.name,
  1351.                                         &match) == lwc_error_ok &&
  1352.                                         match == false) {
  1353.                                 return false;
  1354.                         }
  1355.                 }
  1356.         }
  1357.  
  1358.         return true;
  1359. }
  1360.  
  1361. css_error match_selectors_in_sheet(css_select_ctx *ctx,
  1362.                 const css_stylesheet *sheet, css_select_state *state)
  1363. {
  1364.         static const css_selector *empty_selector = NULL;
  1365.         const uint32_t n_classes = state->n_classes;
  1366.         uint32_t i = 0;
  1367.         const css_selector **node_selectors = &empty_selector;
  1368.         css_selector_hash_iterator node_iterator;
  1369.         const css_selector **id_selectors = &empty_selector;
  1370.         css_selector_hash_iterator id_iterator;
  1371.         const css_selector ***class_selectors = NULL;
  1372.         css_selector_hash_iterator class_iterator;
  1373.         const css_selector **univ_selectors = &empty_selector;
  1374.         css_selector_hash_iterator univ_iterator;
  1375.         css_select_rule_source src = { CSS_SELECT_RULE_SRC_ELEMENT, 0 };
  1376.         css_error error;
  1377.  
  1378.         /* Find hash chain that applies to current node */
  1379.         error = css__selector_hash_find(sheet->selectors,
  1380.                         &state->element, &node_iterator,
  1381.                         &node_selectors);
  1382.         if (error != CSS_OK)
  1383.                 goto cleanup;
  1384.  
  1385.         if (state->classes != NULL && n_classes > 0) {
  1386.                 /* Find hash chains for node classes */
  1387.                 class_selectors = ctx->alloc(NULL,
  1388.                                 n_classes * sizeof(css_selector **),
  1389.                                 ctx->pw);
  1390.                 if (class_selectors == NULL) {
  1391.                         error = CSS_NOMEM;
  1392.                         goto cleanup;
  1393.                 }
  1394.  
  1395.                 for (i = 0; i < n_classes; i++) {
  1396.                         error = css__selector_hash_find_by_class(
  1397.                                         sheet->selectors, state->classes[i],
  1398.                                         &class_iterator, &class_selectors[i]);
  1399.                         if (error != CSS_OK)
  1400.                                 goto cleanup;
  1401.                 }
  1402.         }
  1403.  
  1404.         if (state->id != NULL) {
  1405.                 /* Find hash chain for node ID */
  1406.                 error = css__selector_hash_find_by_id(sheet->selectors,
  1407.                                 state->id, &id_iterator, &id_selectors);
  1408.                 if (error != CSS_OK)
  1409.                         goto cleanup;
  1410.         }
  1411.  
  1412.         /* Find hash chain for universal selector */
  1413.         error = css__selector_hash_find_universal(sheet->selectors,
  1414.                         &univ_iterator, &univ_selectors);
  1415.         if (error != CSS_OK)
  1416.                 goto cleanup;
  1417.  
  1418.         /* Process matching selectors, if any */
  1419.         while (_selectors_pending(node_selectors, id_selectors,
  1420.                         class_selectors, n_classes, univ_selectors)) {
  1421.                 const css_selector *selector;
  1422.  
  1423.                 /* Selectors must be matched in ascending order of specificity
  1424.                  * and rule index. (c.f. css__outranks_existing())
  1425.                  *
  1426.                  * Pick the least specific/earliest occurring selector.
  1427.                  */
  1428.                 selector = _selector_next(node_selectors, id_selectors,
  1429.                                 class_selectors, n_classes, univ_selectors,
  1430.                                 &src);
  1431.  
  1432.                 /* We know there are selectors pending, so should have a
  1433.                  * selector here */
  1434.                 assert(selector != NULL);
  1435.  
  1436.                 /* No bytecode if rule body is empty or wholly invalid --
  1437.                  * Only interested in rules with bytecode */
  1438.                 if (((css_rule_selector *) selector->rule)->style != NULL) {
  1439.                         /* Ignore any selectors contained in rules which are a
  1440.                          * child of an @media block that doesn't match the
  1441.                          * current media requirements. */
  1442.                         if (_rule_applies_to_media(selector->rule,
  1443.                                         state->media)) {
  1444.                                 if (_rule_good_for_element_name(selector, &src,
  1445.                                                 state)) {
  1446.                                         error = match_selector_chain(
  1447.                                                         ctx, selector,
  1448.                                                         state);
  1449.                                         if (error != CSS_OK)
  1450.                                                 goto cleanup;
  1451.                                 }
  1452.                         }
  1453.                 }
  1454.  
  1455.                 /* Advance to next selector in whichever chain we extracted
  1456.                  * the processed selector from. */
  1457.                 switch (src.source) {
  1458.                 case CSS_SELECT_RULE_SRC_ELEMENT:
  1459.                         error = node_iterator(
  1460.                                         node_selectors, &node_selectors);
  1461.                         break;
  1462.  
  1463.                 case CSS_SELECT_RULE_SRC_ID:
  1464.                         error = id_iterator(
  1465.                                         id_selectors, &id_selectors);
  1466.                         break;
  1467.  
  1468.                 case CSS_SELECT_RULE_SRC_UNIVERSAL:
  1469.                         error = univ_iterator(
  1470.                                         univ_selectors, &univ_selectors);
  1471.                         break;
  1472.  
  1473.                 case CSS_SELECT_RULE_SRC_CLASS:
  1474.                         error = class_iterator(
  1475.                                         class_selectors[src.class],
  1476.                                         &class_selectors[src.class]);
  1477.                         break;
  1478.                 }
  1479.  
  1480.                 if (error != CSS_OK)
  1481.                         goto cleanup;
  1482.         }
  1483.  
  1484.         error = CSS_OK;
  1485. cleanup:
  1486.         if (class_selectors != NULL)
  1487.                 ctx->alloc(class_selectors, 0, ctx->pw);
  1488.  
  1489.         return error;
  1490. }
  1491.  
  1492. static void update_reject_cache(css_select_state *state,
  1493.                 css_combinator comb, const css_selector *s)
  1494. {
  1495.         const css_selector_detail *detail = &s->data;
  1496.         const css_selector_detail *next_detail = NULL;
  1497.  
  1498.         if (detail->next)
  1499.                 next_detail = detail + 1;
  1500.  
  1501.         if (state->next_reject < state->reject_cache ||
  1502.                         comb != CSS_COMBINATOR_ANCESTOR ||
  1503.                         next_detail == NULL ||
  1504.                         next_detail->next != 0 ||
  1505.                         (next_detail->type != CSS_SELECTOR_CLASS &&
  1506.                          next_detail->type != CSS_SELECTOR_ID))
  1507.                 return;
  1508.  
  1509.         /* Insert */
  1510.         state->next_reject->type = next_detail->type;
  1511.         state->next_reject->value = next_detail->qname.name;
  1512.         state->next_reject--;
  1513. }
  1514.  
  1515. css_error match_selector_chain(css_select_ctx *ctx,
  1516.                 const css_selector *selector, css_select_state *state)
  1517. {
  1518.         const css_selector *s = selector;
  1519.         void *node = state->node;
  1520.         const css_selector_detail *detail = &s->data;
  1521.         bool match = false, may_optimise = true;
  1522.         bool rejected_by_cache;
  1523.         css_pseudo_element pseudo;
  1524.         css_error error;
  1525.  
  1526. #ifdef DEBUG_CHAIN_MATCHING
  1527.         fprintf(stderr, "matching: ");
  1528.         dump_chain(selector);
  1529.         fprintf(stderr, "\n");
  1530. #endif
  1531.  
  1532.         /* Match the details of the first selector in the chain.
  1533.          *
  1534.          * Note that pseudo elements will only appear as details of
  1535.          * the first selector in the chain, as the parser will reject
  1536.          * any selector chains containing pseudo elements anywhere
  1537.          * else.
  1538.          */
  1539.         error = match_details(ctx, node, detail, state, &match, &pseudo);
  1540.         if (error != CSS_OK)
  1541.                 return error;
  1542.  
  1543.         /* Details don't match, so reject selector chain */
  1544.         if (match == false)
  1545.                 return CSS_OK;
  1546.  
  1547.         /* Iterate up the selector chain, matching combinators */
  1548.         do {
  1549.                 void *next_node = NULL;
  1550.  
  1551.                 /* Consider any combinator on this selector */
  1552.                 if (s->data.comb != CSS_COMBINATOR_NONE &&
  1553.                                 s->combinator->data.qname.name !=
  1554.                                         ctx->universal) {
  1555.                         /* Named combinator */
  1556.                         may_optimise &=
  1557.                                 (s->data.comb == CSS_COMBINATOR_ANCESTOR ||
  1558.                                  s->data.comb == CSS_COMBINATOR_PARENT);
  1559.  
  1560.                         error = match_named_combinator(ctx, s->data.comb,
  1561.                                         s->combinator, state, node, &next_node);
  1562.                         if (error != CSS_OK)
  1563.                                 return error;
  1564.  
  1565.                         /* No match for combinator, so reject selector chain */
  1566.                         if (next_node == NULL)
  1567.                                 return CSS_OK;
  1568.                 } else if (s->data.comb != CSS_COMBINATOR_NONE) {
  1569.                         /* Universal combinator */
  1570.                         may_optimise &=
  1571.                                 (s->data.comb == CSS_COMBINATOR_ANCESTOR ||
  1572.                                  s->data.comb == CSS_COMBINATOR_PARENT);
  1573.  
  1574.                         error = match_universal_combinator(ctx, s->data.comb,
  1575.                                         s->combinator, state, node,
  1576.                                         may_optimise, &rejected_by_cache,
  1577.                                         &next_node);
  1578.                         if (error != CSS_OK)
  1579.                                 return error;
  1580.  
  1581.                         /* No match for combinator, so reject selector chain */
  1582.                         if (next_node == NULL) {
  1583.                                 if (may_optimise && s == selector &&
  1584.                                                 rejected_by_cache == false) {
  1585.                                         update_reject_cache(state, s->data.comb,
  1586.                                                         s->combinator);
  1587.                                 }
  1588.  
  1589.                                 return CSS_OK;
  1590.                         }
  1591.                 }
  1592.  
  1593.                 /* Details matched, so progress to combining selector */
  1594.                 s = s->combinator;
  1595.                 node = next_node;
  1596.         } while (s != NULL);
  1597.  
  1598.         /* If we got here, then the entire selector chain matched, so cascade */
  1599.         state->current_specificity = selector->specificity;
  1600.  
  1601.         /* Ensure that the appropriate computed style exists */
  1602.         if (state->results->styles[pseudo] == NULL) {
  1603.                 error = css_computed_style_create(ctx->alloc, ctx->pw,
  1604.                                 &state->results->styles[pseudo]);
  1605.                 if (error != CSS_OK)
  1606.                         return error;
  1607.         }
  1608.  
  1609.         state->current_pseudo = pseudo;
  1610.         state->computed = state->results->styles[pseudo];
  1611.  
  1612.         return cascade_style(((css_rule_selector *) selector->rule)->style,
  1613.                         state);
  1614. }
  1615.  
  1616. css_error match_named_combinator(css_select_ctx *ctx, css_combinator type,
  1617.                 const css_selector *selector, css_select_state *state,
  1618.                 void *node, void **next_node)
  1619. {
  1620.         const css_selector_detail *detail = &selector->data;
  1621.         void *n = node;
  1622.         css_error error;
  1623.  
  1624.         do {
  1625.                 bool match = false;
  1626.  
  1627.                 /* Find candidate node */
  1628.                 switch (type) {
  1629.                 case CSS_COMBINATOR_ANCESTOR:
  1630.                         error = state->handler->named_ancestor_node(state->pw,
  1631.                                         n, &selector->data.qname, &n);
  1632.                         if (error != CSS_OK)
  1633.                                 return error;
  1634.                         break;
  1635.                 case CSS_COMBINATOR_PARENT:
  1636.                         error = state->handler->named_parent_node(state->pw,
  1637.                                         n, &selector->data.qname, &n);
  1638.                         if (error != CSS_OK)
  1639.                                 return error;
  1640.                         break;
  1641.                 case CSS_COMBINATOR_SIBLING:
  1642.                         error = state->handler->named_sibling_node(state->pw,
  1643.                                         n, &selector->data.qname, &n);
  1644.                         if (error != CSS_OK)
  1645.                                 return error;
  1646.                         break;
  1647.                 case CSS_COMBINATOR_GENERIC_SIBLING:
  1648.                         error = state->handler->named_generic_sibling_node(
  1649.                                         state->pw, n, &selector->data.qname,
  1650.                                         &n);
  1651.                         if (error != CSS_OK)
  1652.                                 return error;
  1653.                 case CSS_COMBINATOR_NONE:
  1654.                         break;
  1655.                 }
  1656.  
  1657.                 if (n != NULL) {
  1658.                         /* Match its details */
  1659.                         error = match_details(ctx, n, detail, state,
  1660.                                         &match, NULL);
  1661.                         if (error != CSS_OK)
  1662.                                 return error;
  1663.  
  1664.                         /* If we found a match, use it */
  1665.                         if (match == true)
  1666.                                 break;
  1667.  
  1668.                         /* For parent and sibling selectors, only adjacent
  1669.                          * nodes are valid. Thus, if we failed to match,
  1670.                          * give up. */
  1671.                         if (type == CSS_COMBINATOR_PARENT ||
  1672.                                         type == CSS_COMBINATOR_SIBLING)
  1673.                                 n = NULL;
  1674.                 }
  1675.         } while (n != NULL);
  1676.  
  1677.         *next_node = n;
  1678.  
  1679.         return CSS_OK;
  1680. }
  1681.  
  1682. css_error match_universal_combinator(css_select_ctx *ctx, css_combinator type,
  1683.                 const css_selector *selector, css_select_state *state,
  1684.                 void *node, bool may_optimise, bool *rejected_by_cache,
  1685.                 void **next_node)
  1686. {
  1687.         const css_selector_detail *detail = &selector->data;
  1688.         const css_selector_detail *next_detail = NULL;
  1689.         void *n = node;
  1690.         css_error error;
  1691.  
  1692.         if (detail->next)
  1693.                 next_detail = detail + 1;
  1694.  
  1695.         *rejected_by_cache = false;
  1696.  
  1697.         /* Consult reject cache first */
  1698.         if (may_optimise && (type == CSS_COMBINATOR_ANCESTOR ||
  1699.                              type == CSS_COMBINATOR_PARENT) &&
  1700.                         next_detail != NULL &&
  1701.                         (next_detail->type == CSS_SELECTOR_CLASS ||
  1702.                          next_detail->type == CSS_SELECTOR_ID)) {
  1703.                 reject_item *reject = state->next_reject + 1;
  1704.                 reject_item *last = state->reject_cache +
  1705.                                 N_ELEMENTS(state->reject_cache) - 1;
  1706.                 bool match = false;
  1707.  
  1708.                 while (reject <= last) {
  1709.                         /* Perform pessimistic matching (may hurt quirks) */
  1710.                         if (reject->type == next_detail->type &&
  1711.                                         lwc_string_isequal(reject->value,
  1712.                                                 next_detail->qname.name,
  1713.                                                 &match) == lwc_error_ok &&
  1714.                                         match) {
  1715.                                 /* Found it: can't match */
  1716.                                 *next_node = NULL;
  1717.                                 *rejected_by_cache = true;
  1718.                                 return CSS_OK;
  1719.                         }
  1720.  
  1721.                         reject++;
  1722.                 }
  1723.         }
  1724.  
  1725.         do {
  1726.                 bool match = false;
  1727.  
  1728.                 /* Find candidate node */
  1729.                 switch (type) {
  1730.                 case CSS_COMBINATOR_ANCESTOR:
  1731.                 case CSS_COMBINATOR_PARENT:
  1732.                         error = state->handler->parent_node(state->pw, n, &n);
  1733.                         if (error != CSS_OK)
  1734.                                 return error;
  1735.                         break;
  1736.                 case CSS_COMBINATOR_SIBLING:
  1737.                 case CSS_COMBINATOR_GENERIC_SIBLING:
  1738.                         error = state->handler->sibling_node(state->pw, n, &n);
  1739.                         if (error != CSS_OK)
  1740.                                 return error;
  1741.                         break;
  1742.                 case CSS_COMBINATOR_NONE:
  1743.                         break;
  1744.                 }
  1745.  
  1746.                 if (n != NULL) {
  1747.                         /* Match its details */
  1748.                         error = match_details(ctx, n, detail, state,
  1749.                                         &match, NULL);
  1750.                         if (error != CSS_OK)
  1751.                                 return error;
  1752.  
  1753.                         /* If we found a match, use it */
  1754.                         if (match == true)
  1755.                                 break;
  1756.  
  1757.                         /* For parent and sibling selectors, only adjacent
  1758.                          * nodes are valid. Thus, if we failed to match,
  1759.                          * give up. */
  1760.                         if (type == CSS_COMBINATOR_PARENT ||
  1761.                                         type == CSS_COMBINATOR_SIBLING)
  1762.                                 n = NULL;
  1763.                 }
  1764.         } while (n != NULL);
  1765.  
  1766.         *next_node = n;
  1767.  
  1768.         return CSS_OK;
  1769. }
  1770.  
  1771. css_error match_details(css_select_ctx *ctx, void *node,
  1772.                 const css_selector_detail *detail, css_select_state *state,
  1773.                 bool *match, css_pseudo_element *pseudo_element)
  1774. {
  1775.         css_error error;
  1776.         css_pseudo_element pseudo = CSS_PSEUDO_ELEMENT_NONE;
  1777.  
  1778.         /* Skip the element selector detail, which is always first.
  1779.          * (Named elements are handled by match_named_combinator, so the
  1780.          * element selector detail always matches here.) */
  1781.         if (detail->next)
  1782.                 detail++;
  1783.         else
  1784.                 detail = NULL;
  1785.  
  1786.         /* We match by default (if there are no details other than the element
  1787.          * selector, then we must match) */
  1788.         *match = true;
  1789.  
  1790.         /** \todo Some details are easier to test than others (e.g. dashmatch
  1791.          * actually requires looking at data rather than simply comparing
  1792.          * pointers). Should we consider sorting the detail list such that the
  1793.          * simpler details come first (and thus the expensive match routines
  1794.          * can be avoided unless absolutely necessary)? */
  1795.  
  1796.         while (detail != NULL) {
  1797.                 error = match_detail(ctx, node, detail, state, match, &pseudo);
  1798.                 if (error != CSS_OK)
  1799.                         return error;
  1800.  
  1801.                 /* Detail doesn't match, so reject selector chain */
  1802.                 if (*match == false)
  1803.                         return CSS_OK;
  1804.  
  1805.                 if (detail->next)
  1806.                         detail++;
  1807.                 else
  1808.                         detail = NULL;
  1809.         }
  1810.  
  1811.         /* Return the applicable pseudo element, if required */
  1812.         if (pseudo_element != NULL)
  1813.                 *pseudo_element = pseudo;
  1814.  
  1815.         return CSS_OK;
  1816. }
  1817.  
  1818. static inline bool match_nth(int32_t a, int32_t b, int32_t count)
  1819. {
  1820.         if (a == 0) {
  1821.                 return count == b;
  1822.         } else {
  1823.                 const int32_t delta = count - b;
  1824.  
  1825.                 /* (count - b) / a is positive or (count - b) is 0 */
  1826.                 if (((delta > 0) == (a > 0)) || delta == 0) {
  1827.                         /* (count - b) / a is integer */
  1828.                         return (delta % a == 0);
  1829.                 }
  1830.  
  1831.                 return false;
  1832.         }
  1833. }
  1834.  
  1835. css_error match_detail(css_select_ctx *ctx, void *node,
  1836.                 const css_selector_detail *detail, css_select_state *state,
  1837.                 bool *match, css_pseudo_element *pseudo_element)
  1838. {
  1839.         bool is_root = false;
  1840.         css_error error = CSS_OK;
  1841.  
  1842.         switch (detail->type) {
  1843.         case CSS_SELECTOR_ELEMENT:
  1844.                 if (detail->negate != 0) {
  1845.                         /* Only need to test this inside not(), since
  1846.                          * it will have been considered as a named node
  1847.                          * otherwise. */
  1848.                         error = state->handler->node_has_name(state->pw, node,
  1849.                                         &detail->qname, match);
  1850.                 }
  1851.                 break;
  1852.         case CSS_SELECTOR_CLASS:
  1853.                 error = state->handler->node_has_class(state->pw, node,
  1854.                                 detail->qname.name, match);
  1855.                 break;
  1856.         case CSS_SELECTOR_ID:
  1857.                 error = state->handler->node_has_id(state->pw, node,
  1858.                                 detail->qname.name, match);
  1859.                 break;
  1860.         case CSS_SELECTOR_PSEUDO_CLASS:
  1861.                 error = state->handler->node_is_root(state->pw, node, &is_root);
  1862.                 if (error != CSS_OK)
  1863.                         return error;
  1864.  
  1865.                 if (is_root == false &&
  1866.                                 detail->qname.name == ctx->first_child) {
  1867.                         int32_t num_before = 0;
  1868.  
  1869.                         error = state->handler->node_count_siblings(state->pw,
  1870.                                         node, false, false, &num_before);
  1871.                         if (error == CSS_OK)
  1872.                                 *match = (num_before == 0);
  1873.                 } else if (is_root == false &&
  1874.                                 detail->qname.name == ctx->nth_child) {
  1875.                         int32_t num_before = 0;
  1876.  
  1877.                         error = state->handler->node_count_siblings(state->pw,
  1878.                                         node, false, false, &num_before);
  1879.                         if (error == CSS_OK) {
  1880.                                 int32_t a = detail->value.nth.a;
  1881.                                 int32_t b = detail->value.nth.b;
  1882.  
  1883.                                 *match = match_nth(a, b, num_before + 1);
  1884.                         }
  1885.                 } else if (is_root == false &&
  1886.                                 detail->qname.name == ctx->nth_last_child) {
  1887.                         int32_t num_after = 0;
  1888.  
  1889.                         error = state->handler->node_count_siblings(state->pw,
  1890.                                         node, false, true, &num_after);
  1891.                         if (error == CSS_OK) {
  1892.                                 int32_t a = detail->value.nth.a;
  1893.                                 int32_t b = detail->value.nth.b;
  1894.  
  1895.                                 *match = match_nth(a, b, num_after + 1);
  1896.                         }
  1897.                 } else if (is_root == false &&
  1898.                                 detail->qname.name == ctx->nth_of_type) {
  1899.                         int32_t num_before = 0;
  1900.  
  1901.                         error = state->handler->node_count_siblings(state->pw,
  1902.                                         node, true, false, &num_before);
  1903.                         if (error == CSS_OK) {
  1904.                                 int32_t a = detail->value.nth.a;
  1905.                                 int32_t b = detail->value.nth.b;
  1906.  
  1907.                                 *match = match_nth(a, b, num_before + 1);
  1908.                         }
  1909.                 } else if (is_root == false &&
  1910.                                 detail->qname.name == ctx->nth_last_of_type) {
  1911.                         int32_t num_after = 0;
  1912.  
  1913.                         error = state->handler->node_count_siblings(state->pw,
  1914.                                         node, true, true, &num_after);
  1915.                         if (error == CSS_OK) {
  1916.                                 int32_t a = detail->value.nth.a;
  1917.                                 int32_t b = detail->value.nth.b;
  1918.  
  1919.                                 *match = match_nth(a, b, num_after + 1);
  1920.                         }
  1921.                 } else if (is_root == false &&
  1922.                                 detail->qname.name == ctx->last_child) {
  1923.                         int32_t num_after = 0;
  1924.  
  1925.                         error = state->handler->node_count_siblings(state->pw,
  1926.                                         node, false, true, &num_after);
  1927.                         if (error == CSS_OK)
  1928.                                 *match = (num_after == 0);
  1929.                 } else if (is_root == false &&
  1930.                                 detail->qname.name == ctx->first_of_type) {
  1931.                         int32_t num_before = 0;
  1932.  
  1933.                         error = state->handler->node_count_siblings(state->pw,
  1934.                                         node, true, false, &num_before);
  1935.                         if (error == CSS_OK)
  1936.                                 *match = (num_before == 0);
  1937.                 } else if (is_root == false &&
  1938.                                 detail->qname.name == ctx->last_of_type) {
  1939.                         int32_t num_after = 0;
  1940.  
  1941.                         error = state->handler->node_count_siblings(state->pw,
  1942.                                         node, true, true, &num_after);
  1943.                         if (error == CSS_OK)
  1944.                                 *match = (num_after == 0);
  1945.                 } else if (is_root == false &&
  1946.                                 detail->qname.name == ctx->only_child) {
  1947.                         int32_t num_before = 0, num_after = 0;
  1948.  
  1949.                         error = state->handler->node_count_siblings(state->pw,
  1950.                                         node, false, false, &num_before);
  1951.                         if (error == CSS_OK) {
  1952.                                 error = state->handler->node_count_siblings(
  1953.                                                 state->pw, node, false, true,
  1954.                                                 &num_after);
  1955.                                 if (error == CSS_OK)
  1956.                                         *match = (num_before == 0) &&
  1957.                                                         (num_after == 0);
  1958.                         }
  1959.                 } else if (is_root == false &&
  1960.                                 detail->qname.name == ctx->only_of_type) {
  1961.                         int32_t num_before = 0, num_after = 0;
  1962.  
  1963.                         error = state->handler->node_count_siblings(state->pw,
  1964.                                         node, true, false, &num_before);
  1965.                         if (error == CSS_OK) {
  1966.                                 error = state->handler->node_count_siblings(
  1967.                                                 state->pw, node, true, true,
  1968.                                                 &num_after);
  1969.                                 if (error == CSS_OK)
  1970.                                         *match = (num_before == 0) &&
  1971.                                                         (num_after == 0);
  1972.                         }
  1973.                 } else if (detail->qname.name == ctx->root) {
  1974.                         *match = is_root;
  1975.                 } else if (detail->qname.name == ctx->empty) {
  1976.                         error = state->handler->node_is_empty(state->pw,
  1977.                                         node, match);
  1978.                 } else if (detail->qname.name == ctx->link) {
  1979.                         error = state->handler->node_is_link(state->pw,
  1980.                                         node, match);
  1981.                 } else if (detail->qname.name == ctx->visited) {
  1982.                         error = state->handler->node_is_visited(state->pw,
  1983.                                         node, match);
  1984.                 } else if (detail->qname.name == ctx->hover) {
  1985.                         error = state->handler->node_is_hover(state->pw,
  1986.                                         node, match);
  1987.                 } else if (detail->qname.name == ctx->active) {
  1988.                         error = state->handler->node_is_active(state->pw,
  1989.                                         node, match);
  1990.                 } else if (detail->qname.name == ctx->focus) {
  1991.                         error = state->handler->node_is_focus(state->pw,
  1992.                                         node, match);
  1993.                 } else if (detail->qname.name == ctx->target) {
  1994.                         error = state->handler->node_is_target(state->pw,
  1995.                                         node, match);
  1996.                 } else if (detail->qname.name == ctx->lang) {
  1997.                         error = state->handler->node_is_lang(state->pw,
  1998.                                         node, detail->value.string, match);
  1999.                 } else if (detail->qname.name == ctx->enabled) {
  2000.                         error = state->handler->node_is_enabled(state->pw,
  2001.                                         node, match);
  2002.                 } else if (detail->qname.name == ctx->disabled) {
  2003.                         error = state->handler->node_is_disabled(state->pw,
  2004.                                         node, match);
  2005.                 } else if (detail->qname.name == ctx->checked) {
  2006.                         error = state->handler->node_is_checked(state->pw,
  2007.                                         node, match);
  2008.                 } else
  2009.                         *match = false;
  2010.                 break;
  2011.         case CSS_SELECTOR_PSEUDO_ELEMENT:
  2012.                 *match = true;
  2013.  
  2014.                 if (detail->qname.name == ctx->first_line) {
  2015.                         *pseudo_element = CSS_PSEUDO_ELEMENT_FIRST_LINE;
  2016.                 } else if (detail->qname.name == ctx->first_letter) {
  2017.                         *pseudo_element = CSS_PSEUDO_ELEMENT_FIRST_LETTER;
  2018.                 } else if (detail->qname.name == ctx->before) {
  2019.                         *pseudo_element = CSS_PSEUDO_ELEMENT_BEFORE;
  2020.                 } else if (detail->qname.name == ctx->after) {
  2021.                         *pseudo_element = CSS_PSEUDO_ELEMENT_AFTER;
  2022.                 } else
  2023.                         *match = false;
  2024.                 break;
  2025.         case CSS_SELECTOR_ATTRIBUTE:
  2026.                 error = state->handler->node_has_attribute(state->pw, node,
  2027.                                 &detail->qname, match);
  2028.                 break;
  2029.         case CSS_SELECTOR_ATTRIBUTE_EQUAL:
  2030.                 error = state->handler->node_has_attribute_equal(state->pw,
  2031.                                 node, &detail->qname, detail->value.string,
  2032.                                 match);
  2033.                 break;
  2034.         case CSS_SELECTOR_ATTRIBUTE_DASHMATCH:
  2035.                 error = state->handler->node_has_attribute_dashmatch(state->pw,
  2036.                                 node, &detail->qname, detail->value.string,
  2037.                                 match);
  2038.                 break;
  2039.         case CSS_SELECTOR_ATTRIBUTE_INCLUDES:
  2040.                 error = state->handler->node_has_attribute_includes(state->pw,
  2041.                                 node, &detail->qname, detail->value.string,
  2042.                                 match);
  2043.                 break;
  2044.         case CSS_SELECTOR_ATTRIBUTE_PREFIX:
  2045.                 error = state->handler->node_has_attribute_prefix(state->pw,
  2046.                                 node, &detail->qname, detail->value.string,
  2047.                                 match);
  2048.                 break;
  2049.         case CSS_SELECTOR_ATTRIBUTE_SUFFIX:
  2050.                 error = state->handler->node_has_attribute_suffix(state->pw,
  2051.                                 node, &detail->qname, detail->value.string,
  2052.                                 match);
  2053.                 break;
  2054.         case CSS_SELECTOR_ATTRIBUTE_SUBSTRING:
  2055.                 error = state->handler->node_has_attribute_substring(state->pw,
  2056.                                 node, &detail->qname, detail->value.string,
  2057.                                 match);
  2058.                 break;
  2059.         }
  2060.  
  2061.         /* Invert match, if the detail requests it */
  2062.         if (error == CSS_OK && detail->negate != 0)
  2063.                 *match = !*match;
  2064.  
  2065.         return error;
  2066. }
  2067.  
  2068. css_error cascade_style(const css_style *style, css_select_state *state)
  2069. {
  2070.         css_style s = *style;
  2071.  
  2072.         while (s.used > 0) {
  2073.                 opcode_t op;
  2074.                 css_error error;
  2075.                 css_code_t opv = *s.bytecode;
  2076.  
  2077.                 advance_bytecode(&s, sizeof(opv));
  2078.  
  2079.                 op = getOpcode(opv);
  2080.  
  2081.                 error = prop_dispatch[op].cascade(opv, &s, state);
  2082.                 if (error != CSS_OK)
  2083.                         return error;
  2084.         }
  2085.  
  2086.         return CSS_OK;
  2087. }
  2088.  
  2089. bool css__outranks_existing(uint16_t op, bool important, css_select_state *state,
  2090.                 bool inherit)
  2091. {
  2092.         prop_state *existing = &state->props[op][state->current_pseudo];
  2093.         bool outranks = false;
  2094.  
  2095.         /* Sorting on origin & importance gives the following:
  2096.          *
  2097.          *           | UA, - | UA, i | USER, - | USER, i | AUTHOR, - | AUTHOR, i
  2098.          *           |----------------------------------------------------------
  2099.          * UA    , - |   S       S       Y          Y         Y           Y
  2100.          * UA    , i |   S       S       Y          Y         Y           Y
  2101.          * USER  , - |   -       -       S          Y         Y           Y
  2102.          * USER  , i |   -       -       -          S         -           -
  2103.          * AUTHOR, - |   -       -       -          Y         S           Y
  2104.          * AUTHOR, i |   -       -       -          Y         -           S
  2105.          *
  2106.          * Where the columns represent the origin/importance of the property
  2107.          * being considered and the rows represent the origin/importance of
  2108.          * the existing property.
  2109.          *
  2110.          * - means that the existing property must be preserved
  2111.          * Y means that the new property must be applied
  2112.          * S means that the specificities of the rules must be considered.
  2113.          *
  2114.          * If specificities are considered, the highest specificity wins.
  2115.          * If specificities are equal, then the rule defined last wins.
  2116.          *
  2117.          * We have no need to explicitly consider the ordering of rules if
  2118.          * the specificities are the same because:
  2119.          *
  2120.          * a) We process stylesheets in order
  2121.          * b) The selector hash chains within a sheet are ordered such that
  2122.          *    more specific rules come after less specific ones and, when
  2123.          *    specificities are identical, rules defined later occur after
  2124.          *    those defined earlier.
  2125.          *
  2126.          * Therefore, where we consider specificity, below, the property
  2127.          * currently being considered will always be applied if its specificity
  2128.          * is greater than or equal to that of the existing property.
  2129.          */
  2130.  
  2131.         if (existing->set == 0) {
  2132.                 /* Property hasn't been set before, new one wins */
  2133.                 outranks = true;
  2134.         } else {
  2135.                 assert(CSS_ORIGIN_UA < CSS_ORIGIN_USER);
  2136.                 assert(CSS_ORIGIN_USER < CSS_ORIGIN_AUTHOR);
  2137.  
  2138.                 if (existing->origin < state->current_origin) {
  2139.                         /* New origin has more weight than existing one.
  2140.                          * Thus, new property wins, except when the existing
  2141.                          * one is USER, i. */
  2142.                         if (existing->important == 0 ||
  2143.                                         existing->origin != CSS_ORIGIN_USER) {
  2144.                                 outranks = true;
  2145.                         }
  2146.                 } else if (existing->origin == state->current_origin) {
  2147.                         /* Origins are identical, consider importance, except
  2148.                          * for UA stylesheets, when specificity is always
  2149.                          * considered (as importance is meaningless) */
  2150.                         if (existing->origin == CSS_ORIGIN_UA) {
  2151.                                 if (state->current_specificity >=
  2152.                                                 existing->specificity) {
  2153.                                         outranks = true;
  2154.                                 }
  2155.                         } else if (existing->important == 0 && important) {
  2156.                                 /* New is more important than old. */
  2157.                                 outranks = true;
  2158.                         } else if (existing->important && important == false) {
  2159.                                 /* Old is more important than new */
  2160.                         } else {
  2161.                                 /* Same importance, consider specificity */
  2162.                                 if (state->current_specificity >=
  2163.                                                 existing->specificity) {
  2164.                                         outranks = true;
  2165.                                 }
  2166.                         }
  2167.                 } else {
  2168.                         /* Existing origin has more weight than new one.
  2169.                          * Thus, existing property wins, except when the new
  2170.                          * one is USER, i. */
  2171.                         if (state->current_origin == CSS_ORIGIN_USER &&
  2172.                                         important) {
  2173.                                 outranks = true;
  2174.                         }
  2175.                 }
  2176.         }
  2177.  
  2178.         if (outranks) {
  2179.                 /* The new property is about to replace the old one.
  2180.                  * Update our state to reflect this. */
  2181.                 existing->set = 1;
  2182.                 existing->specificity = state->current_specificity;
  2183.                 existing->origin = state->current_origin;
  2184.                 existing->important = important;
  2185.                 existing->inherit = inherit;
  2186.         }
  2187.  
  2188.         return outranks;
  2189. }
  2190.  
  2191. /******************************************************************************
  2192.  * Debug helpers                                                              *
  2193.  ******************************************************************************/
  2194. #ifdef DEBUG_CHAIN_MATCHING
  2195. void dump_chain(const css_selector *selector)
  2196. {
  2197.         const css_selector_detail *detail = &selector->data;
  2198.  
  2199.         if (selector->data.comb != CSS_COMBINATOR_NONE)
  2200.                 dump_chain(selector->combinator);
  2201.  
  2202.         if (selector->data.comb == CSS_COMBINATOR_ANCESTOR)
  2203.                 fprintf(stderr, " ");
  2204.         else if (selector->data.comb == CSS_COMBINATOR_SIBLING)
  2205.                 fprintf(stderr, " + ");
  2206.         else if (selector->data.comb == CSS_COMBINATOR_PARENT)
  2207.                 fprintf(stderr, " > ");
  2208.  
  2209.         do {
  2210.                 switch (detail->type) {
  2211.                 case CSS_SELECTOR_ELEMENT:
  2212.                         if (lwc_string_length(detail->name) == 1 &&
  2213.                                 lwc_string_data(detail->name)[0] == '*' &&
  2214.                                         detail->next == 1) {
  2215.                                 break;
  2216.                         }
  2217.                         fprintf(stderr, "%.*s",
  2218.                                         (int) lwc_string_length(detail->name),
  2219.                                         lwc_string_data(detail->name));
  2220.                         break;
  2221.                 case CSS_SELECTOR_CLASS:
  2222.                         fprintf(stderr, ".%.*s",
  2223.                                         (int) lwc_string_length(detail->name),
  2224.                                         lwc_string_data(detail->name));
  2225.                         break;
  2226.                 case CSS_SELECTOR_ID:
  2227.                         fprintf(stderr, "#%.*s",
  2228.                                         (int) lwc_string_length(detail->name),
  2229.                                         lwc_string_data(detail->name));
  2230.                         break;
  2231.                 case CSS_SELECTOR_PSEUDO_CLASS:
  2232.                 case CSS_SELECTOR_PSEUDO_ELEMENT:
  2233.                         fprintf(stderr, ":%.*s",
  2234.                                         (int) lwc_string_length(detail->name),
  2235.                                         lwc_string_data(detail->name));
  2236.  
  2237.                         if (detail->value != NULL) {
  2238.                                 fprintf(stderr, "(%.*s)",
  2239.                                         (int) lwc_string_length(detail->value),
  2240.                                         lwc_string_data(detail->value));
  2241.                         }
  2242.                         break;
  2243.                 case CSS_SELECTOR_ATTRIBUTE:
  2244.                         fprintf(stderr, "[%.*s]",
  2245.                                         (int) lwc_string_length(detail->name),
  2246.                                         lwc_string_data(detail->name));
  2247.                         break;
  2248.                 case CSS_SELECTOR_ATTRIBUTE_EQUAL:
  2249.                         fprintf(stderr, "[%.*s=\"%.*s\"]",
  2250.                                         (int) lwc_string_length(detail->name),
  2251.                                         lwc_string_data(detail->name),
  2252.                                         (int) lwc_string_length(detail->value),
  2253.                                         lwc_string_data(detail->value));
  2254.                         break;
  2255.                 case CSS_SELECTOR_ATTRIBUTE_DASHMATCH:
  2256.                         fprintf(stderr, "[%.*s|=\"%.*s\"]",
  2257.                                         (int) lwc_string_length(detail->name),
  2258.                                         lwc_string_data(detail->name),
  2259.                                         (int) lwc_string_length(detail->value),
  2260.                                         lwc_string_data(detail->value));
  2261.                         break;
  2262.                 case CSS_SELECTOR_ATTRIBUTE_INCLUDES:
  2263.                         fprintf(stderr, "[%.*s~=\"%.*s\"]",
  2264.                                         (int) lwc_string_length(detail->name),
  2265.                                         lwc_string_data(detail->name),
  2266.                                         (int) lwc_string_length(detail->value),
  2267.                                         lwc_string_data(detail->value));
  2268.                         break;
  2269.                 case CSS_SELECTOR_ATTRIBUTE_PREFIX:
  2270.                         fprintf(stderr, "[%.*s^=\"%.*s\"]",
  2271.                                         (int) lwc_string_length(detail->name),
  2272.                                         lwc_string_data(detail->name),
  2273.                                         (int) lwc_string_length(detail->value),
  2274.                                         lwc_string_data(detail->value));
  2275.                         break;
  2276.                 case CSS_SELECTOR_ATTRIBUTE_SUFFIX:
  2277.                         fprintf(stderr, "[%.*s$=\"%.*s\"]",
  2278.                                         (int) lwc_string_length(detail->name),
  2279.                                         lwc_string_data(detail->name),
  2280.                                         (int) lwc_string_length(detail->value),
  2281.                                         lwc_string_data(detail->value));
  2282.                         break;
  2283.                 case CSS_SELECTOR_ATTRIBUTE_SUBSTRING:
  2284.                         fprintf(stderr, "[%.*s*=\"%.*s\"]",
  2285.                                         (int) lwc_string_length(detail->name),
  2286.                                         lwc_string_data(detail->name),
  2287.                                         (int) lwc_string_length(detail->value),
  2288.                                         lwc_string_data(detail->value));
  2289.                         break;
  2290.                 }
  2291.  
  2292.                 if (detail->next)
  2293.                         detail++;
  2294.                 else
  2295.                         detail = NULL;
  2296.         } while (detail);
  2297. }
  2298. #endif
  2299.  
  2300.