Subversion Repositories Kolibri OS

Rev

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

  1. /*
  2.  * Copyright 2005-2007 James Bursa <bursa@users.sourceforge.net>
  3.  * Copyright 2003 Phil Mellor <monkeyson@users.sourceforge.net>
  4.  * Copyright 2005 John M Bell <jmb202@ecs.soton.ac.uk>
  5.  * Copyright 2008 Michael Drake <tlsa@netsurf-browser.org>
  6.  *
  7.  * This file is part of NetSurf, http://www.netsurf-browser.org/
  8.  *
  9.  * NetSurf is free software; you can redistribute it and/or modify
  10.  * it under the terms of the GNU General Public License as published by
  11.  * the Free Software Foundation; version 2 of the License.
  12.  *
  13.  * NetSurf is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.  * GNU General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU General Public License
  19.  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20.  */
  21.  
  22. /** \file
  23.  * Box tree manipulation (implementation).
  24.  */
  25.  
  26. #include <assert.h>
  27. #include <stdbool.h>
  28. #include <stdio.h>
  29. #include <string.h>
  30. #include <dom/dom.h>
  31. #include "content/content_protected.h"
  32. #include "content/hlcache.h"
  33. #include "css/css.h"
  34. #include "css/utils.h"
  35. #include "css/dump.h"
  36. #include "desktop/scrollbar.h"
  37. #include "desktop/options.h"
  38. #include "render/box.h"
  39. #include "render/form.h"
  40. #include "render/html_internal.h"
  41. #include "utils/log.h"
  42. #include "utils/talloc.h"
  43. #include "utils/utils.h"
  44.  
  45. static bool box_contains_point(struct box *box, int x, int y, bool *physically);
  46. static bool box_nearer_text_box(struct box *box, int bx, int by,
  47.                 int x, int y, int dir, struct box **nearest, int *tx, int *ty,
  48.                 int *nr_xd, int *nr_yd);
  49. static bool box_nearest_text_box(struct box *box, int bx, int by,
  50.                 int fx, int fy, int x, int y, int dir, struct box **nearest,
  51.                 int *tx, int *ty, int *nr_xd, int *nr_yd);
  52.  
  53. #define box_is_float(box) (box->type == BOX_FLOAT_LEFT || \
  54.                 box->type == BOX_FLOAT_RIGHT)
  55.  
  56. /**
  57.  * Allocator
  58.  *
  59.  * \param ptr   Pointer to reallocate, or NULL for new allocation
  60.  * \param size  Number of bytes requires
  61.  * \param pw    Allocation context
  62.  * \return Pointer to allocated block, or NULL on failure
  63.  */
  64. void *box_style_alloc(void *ptr, size_t len, void *pw)
  65. {
  66.         if (len == 0) {
  67.                 free(ptr);
  68.                 return NULL;
  69.         }
  70.  
  71.         return realloc(ptr, len);
  72. }
  73.  
  74. /**
  75.  * Destructor for box nodes which own styles
  76.  *
  77.  * \param b The box being destroyed.
  78.  * \return 0 to allow talloc to continue destroying the tree.
  79.  */
  80. static int box_talloc_destructor(struct box *b)
  81. {
  82.         if ((b->flags & STYLE_OWNED) && b->style != NULL) {
  83.                 css_computed_style_destroy(b->style);
  84.                 b->style = NULL;
  85.         }
  86.        
  87.         if (b->styles != NULL) {
  88.                 css_select_results_destroy(b->styles);
  89.                 b->styles = NULL;
  90.         }
  91.  
  92.         if (b->href != NULL)
  93.                 nsurl_unref(b->href);
  94.  
  95.         if (b->id != NULL) {
  96.                 lwc_string_unref(b->id);
  97.         }
  98.  
  99.         if (b->node != NULL) {
  100.                 dom_node_unref(b->node);
  101.         }
  102.  
  103.         return 0;
  104. }
  105.  
  106. /**
  107.  * Create a box tree node.
  108.  *
  109.  * \param  styles       selection results for the box, or NULL
  110.  * \param  style        computed style for the box (not copied), or 0
  111.  * \param  style_owned  whether style is owned by this box
  112.  * \param  href         href for the box (copied), or 0
  113.  * \param  target       target for the box (not copied), or 0
  114.  * \param  title        title for the box (not copied), or 0
  115.  * \param  id           id for the box (not copied), or 0
  116.  * \param  context      context for allocations
  117.  * \return  allocated and initialised box, or 0 on memory exhaustion
  118.  *
  119.  * styles is always owned by the box, if it is set.
  120.  * style is only owned by the box in the case of implied boxes.
  121.  */
  122.  
  123. struct box * box_create(css_select_results *styles, css_computed_style *style,
  124.                 bool style_owned, nsurl *href, const char *target,
  125.                 const char *title, lwc_string *id, void *context)
  126. {
  127.         unsigned int i;
  128.         struct box *box;
  129.  
  130.         box = talloc(context, struct box);
  131.         if (!box) {
  132.                 return 0;
  133.         }
  134.  
  135.         talloc_set_destructor(box, box_talloc_destructor);
  136.  
  137.         box->type = BOX_INLINE;
  138.         box->flags = 0;
  139.         box->flags = style_owned ? (box->flags | STYLE_OWNED) : box->flags;
  140.         box->styles = styles;
  141.         box->style = style;
  142.         box->x = box->y = 0;
  143.         box->width = UNKNOWN_WIDTH;
  144.         box->height = 0;
  145.         box->descendant_x0 = box->descendant_y0 = 0;
  146.         box->descendant_x1 = box->descendant_y1 = 0;
  147.         for (i = 0; i != 4; i++)
  148.                 box->margin[i] = box->padding[i] = box->border[i].width = 0;
  149.         box->scroll_x = box->scroll_y = NULL;
  150.         box->min_width = 0;
  151.         box->max_width = UNKNOWN_MAX_WIDTH;
  152.         box->byte_offset = 0;
  153.         box->text = NULL;
  154.         box->length = 0;
  155.         box->space = 0;
  156.         box->href = (href == NULL) ? NULL : nsurl_ref(href);
  157.         box->target = target;
  158.         box->title = title;
  159.         box->columns = 1;
  160.         box->rows = 1;
  161.         box->start_column = 0;
  162.         box->next = NULL;
  163.         box->prev = NULL;
  164.         box->children = NULL;
  165.         box->last = NULL;
  166.         box->parent = NULL;
  167.         box->inline_end = NULL;
  168.         box->float_children = NULL;
  169.         box->float_container = NULL;
  170.         box->next_float = NULL;
  171.         box->list_marker = NULL;
  172.         box->col = NULL;
  173.         box->gadget = NULL;
  174.         box->usemap = NULL;
  175.         box->id = id;
  176.         box->background = NULL;
  177.         box->object = NULL;
  178.         box->object_params = NULL;
  179.         box->iframe = NULL;
  180.         box->node = NULL;
  181.  
  182.         return box;
  183. }
  184.  
  185. /**
  186.  * Add a child to a box tree node.
  187.  *
  188.  * \param  parent  box giving birth
  189.  * \param  child   box to link as last child of parent
  190.  */
  191.  
  192. void box_add_child(struct box *parent, struct box *child)
  193. {
  194.         assert(parent);
  195.         assert(child);
  196.  
  197.         if (parent->children != 0) {    /* has children already */
  198.                 parent->last->next = child;
  199.                 child->prev = parent->last;
  200.         } else {                        /* this is the first child */
  201.                 parent->children = child;
  202.                 child->prev = 0;
  203.         }
  204.  
  205.         parent->last = child;
  206.         child->parent = parent;
  207. }
  208.  
  209.  
  210. /**
  211.  * Insert a new box as a sibling to a box in a tree.
  212.  *
  213.  * \param  box      box already in tree
  214.  * \param  new_box  box to link into tree as next sibling
  215.  */
  216.  
  217. void box_insert_sibling(struct box *box, struct box *new_box)
  218. {
  219.         new_box->parent = box->parent;
  220.         new_box->prev = box;
  221.         new_box->next = box->next;
  222.         box->next = new_box;
  223.         if (new_box->next)
  224.                 new_box->next->prev = new_box;
  225.         else if (new_box->parent)
  226.                 new_box->parent->last = new_box;
  227. }
  228.  
  229.  
  230. /**
  231.  * Unlink a box from the box tree and then free it recursively.
  232.  *
  233.  * \param  box  box to unlink and free recursively.
  234.  */
  235.  
  236. void box_unlink_and_free(struct box *box)
  237. {
  238.         struct box *parent = box->parent;
  239.         struct box *next = box->next;
  240.         struct box *prev = box->prev;
  241.  
  242.         if (parent) {
  243.                 if (parent->children == box)
  244.                         parent->children = next;
  245.                 if (parent->last == box)
  246.                         parent->last = next ? next : prev;
  247.         }
  248.  
  249.         if (prev)
  250.                 prev->next = next;
  251.         if (next)
  252.                 next->prev = prev;
  253.  
  254.         box_free(box);
  255. }
  256.  
  257.  
  258. /**
  259.  * Free a box tree recursively.
  260.  *
  261.  * \param  box  box to free recursively
  262.  *
  263.  * The box and all its children is freed.
  264.  */
  265.  
  266. void box_free(struct box *box)
  267. {
  268.         struct box *child, *next;
  269.  
  270.         /* free children first */
  271.         for (child = box->children; child; child = next) {
  272.                 next = child->next;
  273.                 box_free(child);
  274.         }
  275.  
  276.         /* last this box */
  277.         box_free_box(box);
  278. }
  279.  
  280.  
  281. /**
  282.  * Free the data in a single box structure.
  283.  *
  284.  * \param  box  box to free
  285.  */
  286.  
  287. void box_free_box(struct box *box)
  288. {
  289.         if (!(box->flags & CLONE)) {
  290.                 if (box->gadget)
  291.                         form_free_control(box->gadget);
  292.                 if (box->scroll_x != NULL)
  293.                         scrollbar_destroy(box->scroll_x);
  294.                 if (box->scroll_y != NULL)
  295.                         scrollbar_destroy(box->scroll_y);
  296.                 if (box->styles != NULL)
  297.                         css_select_results_destroy(box->styles);
  298.         }
  299.  
  300.         talloc_free(box);
  301. }
  302.  
  303.  
  304. /**
  305.  * Find the absolute coordinates of a box.
  306.  *
  307.  * \param  box  the box to calculate coordinates of
  308.  * \param  x    updated to x coordinate
  309.  * \param  y    updated to y coordinate
  310.  */
  311.  
  312. void box_coords(struct box *box, int *x, int *y)
  313. {
  314.         *x = box->x;
  315.         *y = box->y;
  316.         while (box->parent) {
  317.                 if (box_is_float(box)) {
  318.                         do {
  319.                                 box = box->parent;
  320.                         } while (!box->float_children);
  321.                 } else
  322.                         box = box->parent;
  323.                 *x += box->x - scrollbar_get_offset(box->scroll_x);
  324.                 *y += box->y - scrollbar_get_offset(box->scroll_y);
  325.         }
  326. }
  327.  
  328.  
  329. /**
  330.  * Find the bounds of a box.
  331.  *
  332.  * \param  box  the box to calculate bounds of
  333.  * \param  r    receives bounds
  334.  */
  335.  
  336. void box_bounds(struct box *box, struct rect *r)
  337. {
  338.         int width, height;
  339.  
  340.         box_coords(box, &r->x0, &r->y0);
  341.  
  342.         width = box->padding[LEFT] + box->width + box->padding[RIGHT];
  343.         height = box->padding[TOP] + box->height + box->padding[BOTTOM];
  344.  
  345.         r->x1 = r->x0 + width;
  346.         r->y1 = r->y0 + height;
  347. }
  348.  
  349.  
  350. /**
  351.  * Find the boxes at a point.
  352.  *
  353.  * \param  box      box to search children of
  354.  * \param  x        point to find, in global document coordinates
  355.  * \param  y        point to find, in global document coordinates
  356.  * \param  box_x    position of box, in global document coordinates, updated
  357.  *                  to position of returned box, if any
  358.  * \param  box_y    position of box, in global document coordinates, updated
  359.  *                  to position of returned box, if any
  360.  * \return  box at given point, or 0 if none found
  361.  *
  362.  * To find all the boxes in the hierarchy at a certain point, use code like
  363.  * this:
  364.  * \code
  365.  *      struct box *box = top_of_document_to_search;
  366.  *      int box_x = 0, box_y = 0;
  367.  *
  368.  *      while ((box = box_at_point(box, x, y, &box_x, &box_y))) {
  369.  *              // process box
  370.  *      }
  371.  * \endcode
  372.  */
  373.  
  374. struct box *box_at_point(struct box *box, const int x, const int y,
  375.                 int *box_x, int *box_y)
  376. {
  377.         int bx = *box_x, by = *box_y;
  378.         struct box *child, *sibling;
  379.         bool physically;
  380.  
  381.         assert(box);
  382.  
  383.         /* consider floats first, since they will often overlap other boxes */
  384.         for (child = box->float_children; child; child = child->next_float) {
  385.                 if (box_contains_point(child, x - bx, y - by, &physically)) {
  386.                         *box_x = bx + child->x -
  387.                                         scrollbar_get_offset(child->scroll_x);
  388.                         *box_y = by + child->y -
  389.                                         scrollbar_get_offset(child->scroll_y);
  390.  
  391.                         if (physically)
  392.                                 return child;
  393.                         else
  394.                                 return box_at_point(child, x, y, box_x, box_y);
  395.                 }
  396.         }
  397.  
  398. non_float_children:
  399.         /* non-float children */
  400.         for (child = box->children; child; child = child->next) {
  401.                 if (box_is_float(child))
  402.                         continue;
  403.                 if (box_contains_point(child, x - bx, y - by, &physically)) {
  404.                         *box_x = bx + child->x -
  405.                                         scrollbar_get_offset(child->scroll_x);
  406.                         *box_y = by + child->y -
  407.                                         scrollbar_get_offset(child->scroll_y);
  408.  
  409.                         if (physically)
  410.                                 return child;
  411.                         else
  412.                                 return box_at_point(child, x, y, box_x, box_y);
  413.                 }
  414.         }
  415.  
  416.         /* marker boxes */
  417.         if (box->list_marker) {
  418.                 if (box_contains_point(box->list_marker, x - bx, y - by,
  419.                                 &physically)) {
  420.                         *box_x = bx + box->list_marker->x;
  421.                         *box_y = by + box->list_marker->y;
  422.                         return box->list_marker;
  423.                 }
  424.         }
  425.  
  426.         /* siblings and siblings of ancestors */
  427.         while (box) {
  428.                 if (box_is_float(box)) {
  429.                         bx -= box->x - scrollbar_get_offset(box->scroll_x);
  430.                         by -= box->y - scrollbar_get_offset(box->scroll_y);
  431.                         for (sibling = box->next_float; sibling;
  432.                                         sibling = sibling->next_float) {
  433.                                 if (box_contains_point(sibling,
  434.                                                 x - bx, y - by, &physically)) {
  435.                                         *box_x = bx + sibling->x -
  436.                                                         scrollbar_get_offset(
  437.                                                         sibling->scroll_x);
  438.                                         *box_y = by + sibling->y -
  439.                                                         scrollbar_get_offset(
  440.                                                         sibling->scroll_y);
  441.  
  442.                                         if (physically)
  443.                                                 return sibling;
  444.                                         else
  445.                                                 return box_at_point(sibling,
  446.                                                                 x, y,
  447.                                                                 box_x, box_y);
  448.                                 }
  449.                         }
  450.                         /* ascend to float's parent */
  451.                         do {
  452.                                 box = box->parent;
  453.                         } while (!box->float_children);
  454.                         /* process non-float children of float's parent */
  455.                         goto non_float_children;
  456.  
  457.                 } else {
  458.                         bx -= box->x - scrollbar_get_offset(box->scroll_x);
  459.                         by -= box->y - scrollbar_get_offset(box->scroll_y);
  460.                         for (sibling = box->next; sibling;
  461.                                         sibling = sibling->next) {
  462.                                 if (box_is_float(sibling))
  463.                                         continue;
  464.                                 if (box_contains_point(sibling, x - bx, y - by,
  465.                                                 &physically)) {
  466.                                         *box_x = bx + sibling->x -
  467.                                                         scrollbar_get_offset(
  468.                                                         sibling->scroll_x);
  469.                                         *box_y = by + sibling->y -
  470.                                                         scrollbar_get_offset(
  471.                                                         sibling->scroll_y);
  472.  
  473.                                         if (physically)
  474.                                                 return sibling;
  475.                                         else
  476.                                                 return box_at_point(sibling,
  477.                                                                 x, y,
  478.                                                                 box_x, box_y);
  479.                                 }
  480.                         }
  481.                         box = box->parent;
  482.                 }
  483.         }
  484.  
  485.         return 0;
  486. }
  487.  
  488.  
  489. /**
  490.  * Determine if a point lies within a box.
  491.  *
  492.  * \param  box          box to consider
  493.  * \param  x            coordinate relative to box parent
  494.  * \param  y            coordinate relative to box parent
  495.  * \param  physically   if function returning true, physically is set true if
  496.  *                      point is within the box's physical dimensions and false
  497.  *                      if the point is not within the box's physical dimensions
  498.  *                      but is in the area defined by the box's descendants.
  499.  *                      if function returning false, physically is undefined.
  500.  * \return  true if the point is within the box or a descendant box
  501.  *
  502.  * This is a helper function for box_at_point().
  503.  */
  504.  
  505. bool box_contains_point(struct box *box, int x, int y, bool *physically)
  506. {
  507.         css_computed_clip_rect css_rect;
  508.  
  509.         if (box->style != NULL &&
  510.                         css_computed_position(box->style) ==
  511.                                         CSS_POSITION_ABSOLUTE &&
  512.                         css_computed_clip(box->style, &css_rect) ==
  513.                                         CSS_CLIP_RECT) {
  514.                 /* We have an absolutly positioned box with a clip rect */
  515.                 struct rect r = {
  516.                         .x0 = box->x - box->border[LEFT].width,
  517.                         .y0 = box->y - box->border[TOP].width,
  518.                         .x1 = box->x + box->padding[LEFT] + box->width +
  519.                                         box->border[RIGHT].width +
  520.                                         box->padding[RIGHT],
  521.                         .y1 = box->y + box->padding[TOP] + box->height +
  522.                                         box->border[BOTTOM].width +
  523.                                         box->padding[BOTTOM]
  524.                 };
  525.                 if (x >= r.x0 && x < r.x1 && y >= r.y0 && y < r.y1)
  526.                         *physically = true;
  527.                 else
  528.                         *physically = false;
  529.  
  530.                 /* Adjust rect to css clip region */
  531.                 if (css_rect.left_auto == false) {
  532.                         r.x0 += FIXTOINT(nscss_len2px(
  533.                                         css_rect.left, css_rect.lunit,
  534.                                         box->style));
  535.                 }
  536.                 if (css_rect.top_auto == false) {
  537.                         r.y0 += FIXTOINT(nscss_len2px(
  538.                                         css_rect.top, css_rect.tunit,
  539.                                         box->style));
  540.                 }
  541.                 if (css_rect.right_auto == false) {
  542.                         r.x1 = box->x - box->border[LEFT].width +
  543.                                         FIXTOINT(nscss_len2px(
  544.                                                         css_rect.right,
  545.                                                         css_rect.runit,
  546.                                                         box->style));
  547.                 }
  548.                 if (css_rect.bottom_auto == false) {
  549.                         r.y1 = box->y - box->border[TOP].width +
  550.                                         FIXTOINT(nscss_len2px(
  551.                                                         css_rect.bottom,
  552.                                                         css_rect.bunit,
  553.                                                         box->style));
  554.                 }
  555.  
  556.                 /* Test if point is in clipped box */
  557.                 if (x >= r.x0 && x < r.x1 && y >= r.y0 && y < r.y1) {
  558.                         /* inside clip area */
  559.                         return true;
  560.                 }
  561.  
  562.                 /* Not inside clip area */
  563.                 return false;
  564.         }
  565.         if (box->x <= x + box->border[LEFT].width &&
  566.                         x < box->x + box->padding[LEFT] + box->width +
  567.                         box->border[RIGHT].width + box->padding[RIGHT] &&
  568.                         box->y <= y + box->border[TOP].width &&
  569.                         y < box->y + box->padding[TOP] + box->height +
  570.                         box->border[BOTTOM].width + box->padding[BOTTOM]) {
  571.                 *physically = true;
  572.                 return true;
  573.         }
  574.         if (box->list_marker && box->list_marker->x <= x +
  575.                         box->list_marker->border[LEFT].width &&
  576.                         x < box->list_marker->x +
  577.                         box->list_marker->padding[LEFT] +
  578.                         box->list_marker->width +
  579.                         box->list_marker->border[RIGHT].width +
  580.                         box->list_marker->padding[RIGHT] &&
  581.                         box->list_marker->y <= y +
  582.                         box->list_marker->border[TOP].width &&
  583.                         y < box->list_marker->y +
  584.                         box->list_marker->padding[TOP] +
  585.                         box->list_marker->height +
  586.                         box->list_marker->border[BOTTOM].width +
  587.                         box->list_marker->padding[BOTTOM]) {
  588.                 *physically = true;
  589.                 return true;
  590.         }
  591.         if ((box->style && css_computed_overflow(box->style) ==
  592.                         CSS_OVERFLOW_VISIBLE) || !box->style) {
  593.                 if (box->x + box->descendant_x0 <= x &&
  594.                                 x < box->x + box->descendant_x1 &&
  595.                                 box->y + box->descendant_y0 <= y &&
  596.                                 y < box->y + box->descendant_y1) {
  597.                         *physically = false;
  598.                         return true;
  599.                 }
  600.         }
  601.         return false;
  602. }
  603.  
  604.  
  605. /**
  606.  * Check whether box is nearer mouse coordinates than current nearest box
  607.  *
  608.  * \param  box      box to test
  609.  * \param  bx       position of box, in global document coordinates
  610.  * \param  by       position of box, in global document coordinates
  611.  * \param  x        mouse point, in global document coordinates
  612.  * \param  y        mouse point, in global document coordinates
  613.  * \param  dir      direction in which to search (-1 = above-left,
  614.  *                                                +1 = below-right)
  615.  * \param  nearest  nearest text box found, or NULL if none
  616.  *                  updated if box is nearer than existing nearest
  617.  * \param  tx       position of text_box, in global document coordinates
  618.  *                  updated if box is nearer than existing nearest
  619.  * \param  ty       position of text_box, in global document coordinates
  620.  *                  updated if box is nearer than existing nearest
  621.  * \param  nr_xd    distance to nearest text box found
  622.  *                  updated if box is nearer than existing nearest
  623.  * \param  ny_yd    distance to nearest text box found
  624.  *                  updated if box is nearer than existing nearest
  625.  * \return true if mouse point is inside box
  626.  */
  627.  
  628. bool box_nearer_text_box(struct box *box, int bx, int by,
  629.                 int x, int y, int dir, struct box **nearest, int *tx, int *ty,
  630.                 int *nr_xd, int *nr_yd)
  631. {
  632.         int w = box->padding[LEFT] + box->width + box->padding[RIGHT];
  633.         int h = box->padding[TOP] + box->height + box->padding[BOTTOM];
  634.         int y1 = by + h;
  635.         int x1 = bx + w;
  636.         int yd = INT_MAX;
  637.         int xd = INT_MAX;
  638.  
  639.         if (x >= bx && x1 > x && y >= by && y1 > y) {
  640.                 *nearest = box;
  641.                 *tx = bx;
  642.                 *ty = by;
  643.                 return true;
  644.         }
  645.  
  646.         if (box->parent->list_marker != box) {
  647.                 if (dir < 0) {
  648.                         /* consider only those children (partly) above-left */
  649.                         if (by <= y && bx < x) {
  650.                                 yd = y <= y1 ? 0 : y - y1;
  651.                                 xd = x <= x1 ? 0 : x - x1;
  652.                         }
  653.                 } else {
  654.                         /* consider only those children (partly) below-right */
  655.                         if (y1 > y && x1 > x) {
  656.                                 yd = y > by ? 0 : by - y;
  657.                                 xd = x > bx ? 0 : bx - x;
  658.                         }
  659.                 }
  660.  
  661.                 /* give y displacement precedence over x */
  662.                 if (yd < *nr_yd || (yd == *nr_yd && xd <= *nr_xd)) {
  663.                         *nr_yd = yd;
  664.                         *nr_xd = xd;
  665.                         *nearest = box;
  666.                         *tx = bx;
  667.                         *ty = by;
  668.                 }
  669.         }
  670.         return false;
  671. }
  672.  
  673.  
  674. /**
  675.  * Pick the text box child of 'box' that is closest to and above-left
  676.  * (dir -ve) or below-right (dir +ve) of the point 'x,y'
  677.  *
  678.  * \param  box      parent box
  679.  * \param  bx       position of box, in global document coordinates
  680.  * \param  by       position of box, in global document coordinates
  681.  * \param  fx       position of float parent, in global document coordinates
  682.  * \param  fy       position of float parent, in global document coordinates
  683.  * \param  x        mouse point, in global document coordinates
  684.  * \param  y        mouse point, in global document coordinates
  685.  * \param  dir      direction in which to search (-1 = above-left,
  686.  *                                                +1 = below-right)
  687.  * \param  nearest  nearest text box found, or NULL if none
  688.  *                  updated if a descendant of box is nearer than old nearest
  689.  * \param  tx       position of nearest, in global document coordinates
  690.  *                  updated if a descendant of box is nearer than old nearest
  691.  * \param  ty       position of nearest, in global document coordinates
  692.  *                  updated if a descendant of box is nearer than old nearest
  693.  * \param  nr_xd    distance to nearest text box found
  694.  *                  updated if a descendant of box is nearer than old nearest
  695.  * \param  ny_yd    distance to nearest text box found
  696.  *                  updated if a descendant of box is nearer than old nearest
  697.  * \return true if mouse point is inside text_box
  698.  */
  699.  
  700. bool box_nearest_text_box(struct box *box, int bx, int by,
  701.                 int fx, int fy, int x, int y, int dir, struct box **nearest,
  702.                 int *tx, int *ty, int *nr_xd, int *nr_yd)
  703. {
  704.         struct box *child = box->children;
  705.         int c_bx, c_by;
  706.         int c_fx, c_fy;
  707.         bool in_box = false;
  708.  
  709.         if (*nearest == NULL) {
  710.                 *nr_xd = INT_MAX / 2; /* displacement of 'nearest so far' */
  711.                 *nr_yd = INT_MAX / 2;
  712.         }
  713.         if (box->type == BOX_INLINE_CONTAINER) {
  714.                 int bw = box->padding[LEFT] + box->width + box->padding[RIGHT];
  715.                 int bh = box->padding[TOP] + box->height + box->padding[BOTTOM];
  716.                 int b_y1 = by + bh;
  717.                 int b_x1 = bx + bw;
  718.                 if (x >= bx && b_x1 > x && y >= by && b_y1 > y) {
  719.                         in_box = true;
  720.                 }
  721.         }
  722.  
  723.         while (child) {
  724.                 if (child->type == BOX_FLOAT_LEFT ||
  725.                                 child->type == BOX_FLOAT_RIGHT) {
  726.                         c_bx = fx + child->x -
  727.                                         scrollbar_get_offset(child->scroll_x);
  728.                         c_by = fy + child->y -
  729.                                         scrollbar_get_offset(child->scroll_y);
  730.                 } else {
  731.                         c_bx = bx + child->x -
  732.                                         scrollbar_get_offset(child->scroll_x);
  733.                         c_by = by + child->y -
  734.                                         scrollbar_get_offset(child->scroll_y);
  735.                 }
  736.                 if (child->float_children) {
  737.                         c_fx = c_bx;
  738.                         c_fy = c_by;
  739.                 } else {
  740.                         c_fx = fx;
  741.                         c_fy = fy;
  742.                 }
  743.                 if (in_box && child->text && !child->object) {
  744.                         if (box_nearer_text_box(child,
  745.                                         c_bx, c_by, x, y, dir, nearest,
  746.                                         tx, ty, nr_xd, nr_yd))
  747.                                 return true;
  748.                 } else {
  749.                         if (child->list_marker) {
  750.                                 if (box_nearer_text_box(
  751.                                                 child->list_marker,
  752.                                                 c_bx + child->list_marker->x,
  753.                                                 c_by + child->list_marker->y,
  754.                                                 x, y, dir, nearest,
  755.                                                 tx, ty, nr_xd, nr_yd))
  756.                                         return true;
  757.                         }
  758.                         if (box_nearest_text_box(child, c_bx, c_by,
  759.                                         c_fx, c_fy, x, y, dir, nearest, tx, ty,
  760.                                         nr_xd, nr_yd))
  761.                                 return true;
  762.                 }
  763.                 child = child->next;
  764.         }
  765.  
  766.         return false;
  767. }
  768.  
  769.  
  770. /**
  771.  * Peform pick text on browser window contents to locate the box under
  772.  * the mouse pointer, or nearest in the given direction if the pointer is
  773.  * not over a text box.
  774.  *
  775.  * \param html  an HTML content
  776.  * \param x     coordinate of mouse
  777.  * \param y     coordinate of mouse
  778.  * \param dir   direction to search (-1 = above-left, +1 = below-right)
  779.  * \param dx    receives x ordinate of mouse relative to text box
  780.  * \param dy    receives y ordinate of mouse relative to text box
  781.  */
  782.  
  783. struct box *box_pick_text_box(struct html_content *html,
  784.                 int x, int y, int dir, int *dx, int *dy)
  785. {
  786.         struct box *text_box = NULL;
  787.         struct box *box;
  788.         int nr_xd, nr_yd;
  789.         int bx, by;
  790.         int fx, fy;
  791.         int tx, ty;
  792.  
  793.         if (html == NULL)
  794.                 return NULL;
  795.  
  796.         box = html->layout;
  797.         bx = box->margin[LEFT];
  798.         by = box->margin[TOP];
  799.         fx = bx;
  800.         fy = by;
  801.  
  802.         if (!box_nearest_text_box(box, bx, by, fx, fy, x, y,
  803.                         dir, &text_box, &tx, &ty, &nr_xd, &nr_yd)) {
  804.                 if (text_box && text_box->text && !text_box->object) {
  805.                         int w = (text_box->padding[LEFT] +
  806.                                         text_box->width +
  807.                                         text_box->padding[RIGHT]);
  808.                         int h = (text_box->padding[TOP] +
  809.                                         text_box->height +
  810.                                         text_box->padding[BOTTOM]);
  811.                         int x1, y1;
  812.  
  813.                         y1 = ty + h;
  814.                         x1 = tx + w;
  815.  
  816.                         /* ensure point lies within the text box */
  817.                         if (x < tx) x = tx;
  818.                         if (y < ty) y = ty;
  819.                         if (y > y1) y = y1;
  820.                         if (x > x1) x = x1;
  821.                 }
  822.         }
  823.  
  824.         /* return coordinates relative to box */
  825.         *dx = x - tx;
  826.         *dy = y - ty;
  827.  
  828.         return text_box;
  829. }
  830.  
  831.  
  832. /**
  833.  * Find a box based upon its id attribute.
  834.  *
  835.  * \param  box  box tree to search
  836.  * \param  id   id to look for
  837.  * \return  the box or 0 if not found
  838.  */
  839.  
  840. struct box *box_find_by_id(struct box *box, lwc_string *id)
  841. {
  842.         struct box *a, *b;
  843.         bool m;
  844.  
  845.         if (box->id != NULL &&
  846.                         lwc_string_isequal(id, box->id, &m) == lwc_error_ok &&
  847.                         m == true)
  848.                 return box;
  849.  
  850.         for (a = box->children; a; a = a->next) {
  851.                 if ((b = box_find_by_id(a, id)) != NULL)
  852.                         return b;
  853.         }
  854.  
  855.         return NULL;
  856. }
  857.  
  858.  
  859. /**
  860.  * Determine if a box is visible when the tree is rendered.
  861.  *
  862.  * \param  box  box to check
  863.  * \return  true iff the box is rendered
  864.  */
  865.  
  866. bool box_visible(struct box *box)
  867. {
  868.         /* visibility: hidden */
  869.         if (box->style && css_computed_visibility(box->style) ==
  870.                         CSS_VISIBILITY_HIDDEN)
  871.                 return false;
  872.  
  873.         return true;
  874. }
  875.  
  876.  
  877. /**
  878.  * Print a box tree to a file.
  879.  */
  880.  
  881. void box_dump(FILE *stream, struct box *box, unsigned int depth)
  882. {
  883.         unsigned int i;
  884.         struct box *c, *prev;
  885.  
  886.         for (i = 0; i != depth; i++)
  887.                 fprintf(stream, "  ");
  888.  
  889.         fprintf(stream, "%p ", box);
  890.         fprintf(stream, "x%i y%i w%i h%i ", box->x, box->y,
  891.                         box->width, box->height);
  892.         if (box->max_width != UNKNOWN_MAX_WIDTH)
  893.                 fprintf(stream, "min%i max%i ", box->min_width, box->max_width);
  894.         fprintf(stream, "(%i %i %i %i) ",
  895.                         box->descendant_x0, box->descendant_y0,
  896.                         box->descendant_x1, box->descendant_y1);
  897.  
  898.         fprintf(stream, "m(%i %i %i %i) ",
  899.                         box->margin[TOP], box->margin[LEFT],
  900.                         box->margin[BOTTOM], box->margin[RIGHT]);
  901.  
  902.         switch (box->type) {
  903.         case BOX_BLOCK:            fprintf(stream, "BLOCK "); break;
  904.         case BOX_INLINE_CONTAINER: fprintf(stream, "INLINE_CONTAINER "); break;
  905.         case BOX_INLINE:           fprintf(stream, "INLINE "); break;
  906.         case BOX_INLINE_END:       fprintf(stream, "INLINE_END "); break;
  907.         case BOX_INLINE_BLOCK:     fprintf(stream, "INLINE_BLOCK "); break;
  908.         case BOX_TABLE:            fprintf(stream, "TABLE [columns %i] ",
  909.                                            box->columns); break;
  910.         case BOX_TABLE_ROW:        fprintf(stream, "TABLE_ROW "); break;
  911.         case BOX_TABLE_CELL:       fprintf(stream, "TABLE_CELL [columns %i, "
  912.                                            "start %i, rows %i] ", box->columns,
  913.                                            box->start_column, box->rows); break;
  914.         case BOX_TABLE_ROW_GROUP:  fprintf(stream, "TABLE_ROW_GROUP "); break;
  915.         case BOX_FLOAT_LEFT:       fprintf(stream, "FLOAT_LEFT "); break;
  916.         case BOX_FLOAT_RIGHT:      fprintf(stream, "FLOAT_RIGHT "); break;
  917.         case BOX_BR:               fprintf(stream, "BR "); break;
  918.         case BOX_TEXT:             fprintf(stream, "TEXT "); break;
  919.         default:                   fprintf(stream, "Unknown box type ");
  920.         }
  921.  
  922.         if (box->text)
  923.                 fprintf(stream, "%li '%.*s' ", (unsigned long) box->byte_offset,
  924.                                 (int) box->length, box->text);
  925.         if (box->space)
  926.                 fprintf(stream, "space ");
  927.         if (box->object) {
  928.                 fprintf(stream, "(object '%s') ",
  929.                                 nsurl_access(hlcache_handle_get_url(box->object)));
  930.         }
  931.         if (box->iframe) {
  932.                 fprintf(stream, "(iframe) ");
  933.         }
  934.         if (box->gadget)
  935.                 fprintf(stream, "(gadget) ");
  936.         if (box->style)
  937.                 nscss_dump_computed_style(stream, box->style);
  938.         if (box->href)
  939.                 fprintf(stream, " -> '%s'", nsurl_access(box->href));
  940.         if (box->target)
  941.                 fprintf(stream, " |%s|", box->target);
  942.         if (box->title)
  943.                 fprintf(stream, " [%s]", box->title);
  944.         if (box->id)
  945.                 fprintf(stream, " <%s>", lwc_string_data(box->id));
  946.         if (box->type == BOX_INLINE || box->type == BOX_INLINE_END)
  947.                 fprintf(stream, " inline_end %p", box->inline_end);
  948.         if (box->float_children)
  949.                 fprintf(stream, " float_children %p", box->float_children);
  950.         if (box->next_float)
  951.                 fprintf(stream, " next_float %p", box->next_float);
  952.         if (box->col) {
  953.                 fprintf(stream, " (columns");
  954.                 for (i = 0; i != box->columns; i++)
  955.                         fprintf(stream, " (%s %s %i %i %i)",
  956.                                         ((const char *[]) {"UNKNOWN", "FIXED",
  957.                                         "AUTO", "PERCENT", "RELATIVE"})
  958.                                         [box->col[i].type],
  959.                                         ((const char *[]) {"normal",
  960.                                         "positioned"})
  961.                                         [box->col[i].positioned],
  962.                                         box->col[i].width,
  963.                                         box->col[i].min, box->col[i].max);
  964.                 fprintf(stream, ")");
  965.         }
  966.         fprintf(stream, "\n");
  967.  
  968.         if (box->list_marker) {
  969.                 for (i = 0; i != depth; i++)
  970.                         fprintf(stream, "  ");
  971.                 fprintf(stream, "list_marker:\n");
  972.                 box_dump(stream, box->list_marker, depth + 1);
  973.         }
  974.  
  975.         for (c = box->children; c && c->next; c = c->next)
  976.                 ;
  977.         if (box->last != c)
  978.                 fprintf(stream, "warning: box->last %p (should be %p) "
  979.                                 "(box %p)\n", box->last, c, box);
  980.         for (prev = 0, c = box->children; c; prev = c, c = c->next) {
  981.                 if (c->parent != box)
  982.                         fprintf(stream, "warning: box->parent %p (should be "
  983.                                         "%p) (box on next line)\n",
  984.                                         c->parent, box);
  985.                 if (c->prev != prev)
  986.                         fprintf(stream, "warning: box->prev %p (should be "
  987.                                         "%p) (box on next line)\n",
  988.                                         c->prev, prev);
  989.                 box_dump(stream, c, depth + 1);
  990.         }
  991. }
  992.  
  993. /**
  994.  * Applies the given scroll setup to a box. This includes scroll
  995.  * creation/deletion as well as scroll dimension updates.
  996.  *
  997.  * \param c             content in which the box is located
  998.  * \param box           the box to handle the scrolls for
  999.  * \param bottom        whether the horizontal scrollbar should be present
  1000.  * \param right         whether the vertical scrollbar should be present
  1001.  * \return              true on success false otherwise
  1002.  */
  1003. bool box_handle_scrollbars(struct content *c, struct box *box,
  1004.                 bool bottom, bool right)
  1005. {
  1006.         struct html_scrollbar_data *data;
  1007.         int visible_width, visible_height;
  1008.         int full_width, full_height;
  1009.  
  1010.         if (!bottom && box->scroll_x != NULL) {
  1011.                 data = scrollbar_get_data(box->scroll_x);
  1012.                 scrollbar_destroy(box->scroll_x);
  1013.                 free(data);
  1014.                 box->scroll_x = NULL;
  1015.         }
  1016.  
  1017.         if (!right && box->scroll_y != NULL) {
  1018.                 data = scrollbar_get_data(box->scroll_y);
  1019.                 scrollbar_destroy(box->scroll_y);
  1020.                 free(data);
  1021.                 box->scroll_y = NULL;
  1022.         }
  1023.  
  1024.         if (!bottom && !right)
  1025.                 return true;
  1026.  
  1027.         visible_width = box->width + box->padding[RIGHT] + box->padding[LEFT];
  1028.         visible_height = box->height + box->padding[TOP] + box->padding[BOTTOM];
  1029.  
  1030.         full_width = ((box->descendant_x1 - box->border[RIGHT].width) >
  1031.                         visible_width) ?
  1032.                         box->descendant_x1 + box->padding[RIGHT] :
  1033.                         visible_width;
  1034.         full_height = ((box->descendant_y1 - box->border[BOTTOM].width) >
  1035.                         visible_height) ?
  1036.                         box->descendant_y1 + box->padding[BOTTOM] :
  1037.                         visible_height;
  1038.  
  1039.         if (right) {
  1040.                 if (box->scroll_y == NULL) {
  1041.                         data = malloc(sizeof(struct html_scrollbar_data));
  1042.                         if (data == NULL) {
  1043.                                 LOG(("malloc failed"));
  1044.                                 warn_user("NoMemory", 0);
  1045.                                 return false;
  1046.                         }
  1047.                         data->c = c;
  1048.                         data->box = box;
  1049.                         if (!scrollbar_create(false, visible_height,
  1050.                                         full_height, visible_height,
  1051.                                         data, html_overflow_scroll_callback,
  1052.                                         &(box->scroll_y)))
  1053.                                 return false;
  1054.                 } else  {
  1055.                         scrollbar_set_extents(box->scroll_y, visible_height,
  1056.                                         visible_height, full_height);
  1057.                 }
  1058.         }
  1059.         if (bottom) {
  1060.                 if (box->scroll_x == NULL) {
  1061.                         data = malloc(sizeof(struct html_scrollbar_data));
  1062.                         if (data == NULL) {
  1063.                                 LOG(("malloc failed"));
  1064.                                 warn_user("NoMemory", 0);
  1065.                                 return false;
  1066.                         }
  1067.                         data->c = c;
  1068.                         data->box = box;
  1069.                         if (!scrollbar_create(true,
  1070.                                         visible_width -
  1071.                                         (right ? SCROLLBAR_WIDTH : 0),
  1072.                                         full_width, visible_width,
  1073.                                         data, html_overflow_scroll_callback,
  1074.                                         &box->scroll_x))
  1075.                                 return false;
  1076.                 } else {
  1077.                         scrollbar_set_extents(box->scroll_x,
  1078.                                         visible_width -
  1079.                                         (right ? SCROLLBAR_WIDTH : 0),
  1080.                                         visible_width, full_width);
  1081.                 }
  1082.         }
  1083.        
  1084.         if (right && bottom)
  1085.                 scrollbar_make_pair(box->scroll_x, box->scroll_y);
  1086.        
  1087.         return true;
  1088. }
  1089.  
  1090. /**
  1091.  * Determine if a box has a vertical scrollbar.
  1092.  *
  1093.  * \param  box  scrolling box
  1094.  * \return the box has a vertical scrollbar
  1095.  */
  1096.  
  1097. bool box_vscrollbar_present(const struct box * const box)
  1098. {
  1099.         return box->padding[TOP] + box->height + box->padding[BOTTOM] +
  1100.                         box->border[BOTTOM].width < box->descendant_y1;
  1101. }
  1102.  
  1103.  
  1104. /**
  1105.  * Determine if a box has a horizontal scrollbar.
  1106.  *
  1107.  * \param  box  scrolling box
  1108.  * \return the box has a horizontal scrollbar
  1109.  */
  1110.  
  1111. bool box_hscrollbar_present(const struct box * const box)
  1112. {
  1113.         return box->padding[LEFT] + box->width + box->padding[RIGHT] +
  1114.                         box->border[RIGHT].width < box->descendant_x1;
  1115. }
  1116.  
  1117.