Make box_at_point use itteration, rather than recursion.

This should reduce stack usage.  The walk logic is split out from
box_at_point so that it might be reused.

1 files changed, 218 insertions, 120 deletions

diff --git a/render/box.c b/render/box.c
index 501bae6de..91f866d2f 100644
--- a/render/box.c
+++ b/render/box.c
@@ -343,6 +343,191 @@ void box_bounds(struct box *box, struct rect *r)
 }
 
 
+/** Direction to move in a box-tree walk */
+enum box_walk_dir {
+	BOX_WALK_CHILDREN,
+	BOX_WALK_PARENT,
+	BOX_WALK_NEXT_SIBLING,
+	BOX_WALK_FLOAT_CHILDREN,
+	BOX_WALK_NEXT_FLOAT_SIBLING,
+	BOX_WALK_FLOAT_CONTAINER
+};
+
+
+/**
+ * Move from box to next box in given direction, adjusting for box coord change
+ *
+ * \param b	box to move from from
+ * \param dir	direction to move in
+ * \param x	box's global x-coord, updated to position of next box
+ * \param y	box's global y-coord, updated to position of next box
+ *
+ * If no box can be found in given direction, NULL is returned.
+ */
+static inline struct box *box_move_xy(struct box *b, enum box_walk_dir dir,
+		int *x, int *y)
+{
+	switch (dir) {
+	case BOX_WALK_CHILDREN:
+		b = b->children;
+		if (b == NULL)
+			return NULL;
+		*x += b->x;
+		*y += b->y;
+		if (!box_is_float(b)) {
+			return b;
+		}
+		/* Fall through */
+
+	case BOX_WALK_NEXT_SIBLING:
+		do {
+			*x -= b->x;
+			*y -= b->y;
+			b = b->next;
+			if (b == NULL)
+				break;
+			*x += b->x;
+			*y += b->y;
+		} while (box_is_float(b));
+		return b;
+
+	case BOX_WALK_PARENT:
+		*x -= b->x;
+		*y -= b->y;
+		return b->parent;
+
+	case BOX_WALK_FLOAT_CHILDREN:
+		b = b->float_children;
+		if (b == NULL)
+			return NULL;
+		*x += b->x;
+		*y += b->y;
+		return b;
+
+	case BOX_WALK_NEXT_FLOAT_SIBLING:
+		*x -= b->x;
+		*y -= b->y;
+		b = b->next_float;
+		if (b == NULL)
+			return NULL;
+		*x += b->x;
+		*y += b->y;
+		return b;
+
+	case BOX_WALK_FLOAT_CONTAINER:
+		*x -= b->x;
+		*y -= b->y;
+		return b->float_container;
+
+	default:
+		assert(0 && "Bad box walk type.");
+	}
+}
+
+
+/**
+ * Itterator for walking to next box in interaction order
+ *
+ * \param b	box to find next box from
+ * \param x	box's global x-coord, updated to position of next box
+ * \param y	box's global y-coord, updated to position of next box
+ * \param skip_children	whether to skip box's children
+ *
+ * This walks to a boxes float children before its children.  When walking
+ * children, floating boxes are skipped.
+ */
+static inline struct box *box_next_xy(struct box *b, int *x, int *y,
+		bool skip_children)
+{
+	struct box *n;
+	int tx, ty;
+
+	assert(b != NULL);
+
+	if (skip_children) {
+		/* Caller is not interested in any kind of children */
+		goto skip_children;
+	}
+
+	tx = *x; ty = *y;
+	n = box_move_xy(b, BOX_WALK_FLOAT_CHILDREN, &tx, &ty);
+	if (n) {
+		/* Next node is float child */
+		*x = tx;
+		*y = ty;
+		return n;
+	}
+done_float_children:
+
+	tx = *x; ty = *y;
+	n = box_move_xy(b, BOX_WALK_CHILDREN, &tx, &ty);
+	if (n) {
+		/* Next node is child */
+		*x = tx;
+		*y = ty;
+		return n;
+	}
+
+skip_children:
+	tx = *x; ty = *y;
+	n = box_move_xy(b, BOX_WALK_NEXT_FLOAT_SIBLING, &tx, &ty);
+	if (n) {
+		/* Go to next float sibling */
+		*x = tx;
+		*y = ty;
+		return n;
+	}
+
+	if (box_is_float(b)) {
+		/* Done floats, but the float container may have children,
+		 * or siblings, or ansestors with siblings.  Change to
+		 * float container and move past handling its float children.
+		 */
+		b = box_move_xy(b, BOX_WALK_FLOAT_CONTAINER, x, y);
+		goto done_float_children;
+	}
+
+	/* Go to next sibling, or nearest ancestor with next sibling. */
+	while (b) {
+		while (!b->next && b->parent) {
+			b = box_move_xy(b, BOX_WALK_PARENT, x, y);
+			if (box_is_float(b)) {
+				/* Go on to next float, if there is one */
+				goto skip_children;
+			}
+		}
+		if (!b->next) {
+			/* No more boxes */
+			return NULL;
+		}
+
+		tx = *x; ty = *y;
+		n = box_move_xy(b, BOX_WALK_NEXT_SIBLING, &tx, &ty);
+		if (n) {
+			/* Go to non-float (ancestor) sibling */
+			*x = tx;
+			*y = ty;
+			return n;
+
+		} else if (b->parent) {
+			b = box_move_xy(b, BOX_WALK_PARENT, x, y);
+			if (box_is_float(b)) {
+				/* Go on to next float, if there is one */
+				goto skip_children;
+			}
+
+		} else {
+			/* No more boxes */
+			return NULL;
+		}
+	}
+
+	assert(b != NULL);
+	return NULL;
+}
+
+
+
 /**
  * Find the boxes at a point.
  *
@@ -370,115 +555,28 @@ void box_bounds(struct box *box, struct rect *r)
 struct box *box_at_point(struct box *box, const int x, const int y,
 		int *box_x, int *box_y)
 {
-	int bx = *box_x, by = *box_y;
-	struct box *child, *sibling;
+	bool skip_children;
 	bool physically;
 
 	assert(box);
 
-	/* consider floats first, since they will often overlap other boxes */
-	for (child = box->float_children; child; child = child->next_float) {
-		if (box_contains_point(child, x - bx, y - by, &physically)) {
-			*box_x = bx + child->x -
-					scrollbar_get_offset(child->scroll_x);
-			*box_y = by + child->y -
-					scrollbar_get_offset(child->scroll_y);
-
-			if (physically)
-				return child;
-			else
-				return box_at_point(child, x, y, box_x, box_y);
-		}
-	}
-
-non_float_children:
-	/* non-float children */
-	for (child = box->children; child; child = child->next) {
-		if (box_is_float(child))
-			continue;
-		if (box_contains_point(child, x - bx, y - by, &physically)) {
-			*box_x = bx + child->x -
-					scrollbar_get_offset(child->scroll_x);
-			*box_y = by + child->y -
-					scrollbar_get_offset(child->scroll_y);
-
-			if (physically)
-				return child;
-			else
-				return box_at_point(child, x, y, box_x, box_y);
-		}
-	}
-
-	/* marker boxes */
-	if (box->list_marker) {
-		if (box_contains_point(box->list_marker, x - bx, y - by,
+	skip_children = false;
+	while ((box = box_next_xy(box, box_x, box_y, skip_children))) {
+		if (box_contains_point(box, x - *box_x, y - *box_y,
 				&physically)) {
-			*box_x = bx + box->list_marker->x;
-			*box_y = by + box->list_marker->y;
-			return box->list_marker;
-		}
-	}
+			*box_x -= scrollbar_get_offset(box->scroll_x);
+			*box_y -= scrollbar_get_offset(box->scroll_y);
 
-	/* siblings and siblings of ancestors */
-	while (box) {
-		if (box_is_float(box)) {
-			bx -= box->x - scrollbar_get_offset(box->scroll_x);
-			by -= box->y - scrollbar_get_offset(box->scroll_y);
-			for (sibling = box->next_float; sibling;
-					sibling = sibling->next_float) {
-				if (box_contains_point(sibling,
-						x - bx, y - by, &physically)) {
-					*box_x = bx + sibling->x -
-							scrollbar_get_offset(
-							sibling->scroll_x);
-					*box_y = by + sibling->y -
-							scrollbar_get_offset(
-							sibling->scroll_y);
-
-					if (physically)
-						return sibling;
-					else
-						return box_at_point(sibling,
-								x, y,
-								box_x, box_y);
-				}
-			}
-			/* ascend to float's parent */
-			do {
-				box = box->parent;
-			} while (!box->float_children);
-			/* process non-float children of float's parent */
-			goto non_float_children;
+			if (physically)
+				return box;
 
+			skip_children = false;
 		} else {
-			bx -= box->x - scrollbar_get_offset(box->scroll_x);
-			by -= box->y - scrollbar_get_offset(box->scroll_y);
-			for (sibling = box->next; sibling;
-					sibling = sibling->next) {
-				if (box_is_float(sibling))
-					continue;
-				if (box_contains_point(sibling, x - bx, y - by,
-						&physically)) {
-					*box_x = bx + sibling->x -
-							scrollbar_get_offset(
-							sibling->scroll_x);
-					*box_y = by + sibling->y -
-							scrollbar_get_offset(
-							sibling->scroll_y);
-
-					if (physically)
-						return sibling;
-					else
-						return box_at_point(sibling,
-								x, y,
-								box_x, box_y);
-				}
-			}
-			box = box->parent;
+			skip_children = true;
 		}
 	}
 
-	return 0;
+	return NULL;
 }
 
 
@@ -486,8 +584,8 @@ non_float_children:
  * Determine if a point lies within a box.
  *
  * \param  box		box to consider
- * \param  x		coordinate relative to box parent
- * \param  y		coordinate relative to box parent
+ * \param  x		coordinate relative to box
+ * \param  y		coordinate relative to box
  * \param  physically	if function returning true, physically is set true if
  *			point is within the box's physical dimensions and false
  *			if the point is not within the box's physical dimensions
@@ -509,12 +607,12 @@ bool box_contains_point(struct box *box, int x, int y, bool *physically)
 					CSS_CLIP_RECT) {
 		/* We have an absolutly positioned box with a clip rect */
 		struct rect r = {
-			.x0 = box->x - box->border[LEFT].width,
-			.y0 = box->y - box->border[TOP].width,
-			.x1 = box->x + box->padding[LEFT] + box->width +
+			.x0 = box->border[LEFT].width,
+			.y0 = box->border[TOP].width,
+			.x1 = box->padding[LEFT] + box->width +
 					box->border[RIGHT].width +
 					box->padding[RIGHT],
-			.y1 = box->y + box->padding[TOP] + box->height +
+			.y1 = box->padding[TOP] + box->height +
 					box->border[BOTTOM].width +
 					box->padding[BOTTOM]
 		};
@@ -535,14 +633,14 @@ bool box_contains_point(struct box *box, int x, int y, bool *physically)
 					box->style));
 		}
 		if (css_rect.right_auto == false) {
-			r.x1 = box->x - box->border[LEFT].width +
+			r.x1 = box->border[LEFT].width +
 					FIXTOINT(nscss_len2px(
 							css_rect.right,
 							css_rect.runit,
 							box->style));
 		}
 		if (css_rect.bottom_auto == false) {
-			r.y1 = box->y - box->border[TOP].width +
+			r.y1 = box->border[TOP].width +
 					FIXTOINT(nscss_len2px(
 							css_rect.bottom,
 							css_rect.bunit,
@@ -558,25 +656,25 @@ bool box_contains_point(struct box *box, int x, int y, bool *physically)
 		/* Not inside clip area */
 		return false;
 	}
-	if (box->x <= x + box->border[LEFT].width &&
-			x < box->x + box->padding[LEFT] + box->width +
-			box->border[RIGHT].width + box->padding[RIGHT] &&
-			box->y <= y + box->border[TOP].width &&
-			y < box->y + box->padding[TOP] + box->height +
-			box->border[BOTTOM].width + box->padding[BOTTOM]) {
+	if (x >= -box->border[LEFT].width &&
+			x < box->padding[LEFT] + box->width +
+			box->padding[RIGHT] + box->border[RIGHT].width &&
+			y >= -box->border[TOP].width &&
+			y < box->padding[TOP] + box->height +
+			box->padding[BOTTOM] + box->border[BOTTOM].width) {
 		*physically = true;
 		return true;
 	}
-	if (box->list_marker && box->list_marker->x <= x +
+	if (box->list_marker && box->list_marker->x - box->x <= x +
 			box->list_marker->border[LEFT].width &&
-			x < box->list_marker->x +
+			x < box->list_marker->x - box->x +
 			box->list_marker->padding[LEFT] +
 			box->list_marker->width +
 			box->list_marker->border[RIGHT].width +
 			box->list_marker->padding[RIGHT] &&
-			box->list_marker->y <= y +
+			box->list_marker->y - box->y <= y +
 			box->list_marker->border[TOP].width &&
-			y < box->list_marker->y +
+			y < box->list_marker->y - box->y +
 			box->list_marker->padding[TOP] +
 			box->list_marker->height +
 			box->list_marker->border[BOTTOM].width +
@@ -586,16 +684,16 @@ bool box_contains_point(struct box *box, int x, int y, bool *physically)
 	}
 	if ((box->style && css_computed_overflow_x(box->style) == 
 			CSS_OVERFLOW_VISIBLE) || !box->style) {
-		if (box->x + box->descendant_x0 <= x &&
-				x < box->x + box->descendant_x1) {
+		if (box->descendant_x0 <= x &&
+				x < box->descendant_x1) {
 			*physically = false;
 			return true;
 		}
 	}
 	if ((box->style && css_computed_overflow_y(box->style) == 
 			CSS_OVERFLOW_VISIBLE) || !box->style) {
-		if (box->y + box->descendant_y0 <= y &&
-				y < box->y + box->descendant_y1) {
+		if (box->descendant_y0 <= y &&
+				y < box->descendant_y1) {
 			*physically = false;
 			return true;
 		}