From 74ef206f532445a03a9463d4c0a5e0715e9808b4 Mon Sep 17 00:00:00 2001 From: James Bursa Date: Tue, 18 Jun 2002 21:24:21 +0000 Subject: [project @ 2002-06-18 21:24:21 by bursa] Improved inline and float layout, new CSS properties, better debug output. svn path=/import/netsurf/; revision=20 --- render/layout.c | 316 +++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 247 insertions(+), 69 deletions(-) (limited to 'render/layout.c') diff --git a/render/layout.c b/render/layout.c index b7030a658..36c018a9e 100644 --- a/render/layout.c +++ b/render/layout.c @@ -1,5 +1,5 @@ /** - * $Id: layout.c,v 1.5 2002/05/27 23:21:11 bursa Exp $ + * $Id: layout.c,v 1.6 2002/06/18 21:24:21 bursa Exp $ */ #include @@ -18,16 +18,20 @@ * internal functions */ -signed long len(struct css_length * length, unsigned long em); +signed long len(struct css_length * length, struct css_style * style); void layout_block(struct box * box, unsigned long width, struct box * cont, unsigned long cx, unsigned long cy); unsigned long layout_block_children(struct box * box, unsigned long width, struct box * cont, unsigned long cx, unsigned long cy); void find_sides(struct box * fl, unsigned long y0, unsigned long y1, - unsigned long * x0, unsigned long * x1); + unsigned long * x0, unsigned long * x1, struct box ** left, struct box ** right); void layout_inline_container(struct box * box, unsigned long width, struct box * cont, unsigned long cx, unsigned long cy); +signed long line_height(struct css_style * style); +struct box * layout_line(struct box * first, unsigned long width, unsigned long * y, + unsigned long cy, struct box * cont); +void place_float_below(struct box * c, unsigned long width, unsigned long y, struct box * cont); void layout_table(struct box * box, unsigned long width, struct box * cont, unsigned long cx, unsigned long cy); @@ -35,11 +39,12 @@ void layout_table(struct box * box, unsigned long width, struct box * cont, * convert a struct css_length to pixels */ -signed long len(struct css_length * length, unsigned long em) +signed long len(struct css_length * length, struct css_style * style) { + assert(!((length->unit == CSS_UNIT_EM || length->unit == CSS_UNIT_EX) && style == 0)); switch (length->unit) { - case CSS_UNIT_EM: return length->value * em; - case CSS_UNIT_EX: return length->value * em * 0.6; + case CSS_UNIT_EM: return length->value * len(&style->font_size.value.length, 0); + case CSS_UNIT_EX: return length->value * len(&style->font_size.value.length, 0) * 0.6; case CSS_UNIT_PX: return length->value; case CSS_UNIT_IN: return length->value * 90.0; case CSS_UNIT_CM: return length->value * 35.0; @@ -55,22 +60,43 @@ signed long len(struct css_length * length, unsigned long em) * layout algorithm */ +/** + * layout_document -- calculate positions of boxes in a document + * + * doc root of document box tree + * width page width + */ + void layout_document(struct box * doc, unsigned long width) { doc->float_children = 0; layout_block(doc, width, doc, 0, 0); } + +/** + * layout_block -- position block and recursively layout children + * + * box block box to layout + * width horizontal space available + * cont ancestor box which defines horizontal space, for inlines + * cx, cy box position relative to cont + */ + void layout_block(struct box * box, unsigned long width, struct box * cont, unsigned long cx, unsigned long cy) { struct css_style * style = box->style; + + assert(box->type == BOX_BLOCK || box->type == BOX_FLOAT); + switch (style->width.width) { case CSS_WIDTH_AUTO: + /* take all available width */ box->width = width; break; case CSS_WIDTH_LENGTH: - box->width = len(&style->width.value.length, 20); + box->width = len(&style->width.value.length, box->style); break; case CSS_WIDTH_PERCENT: box->width = width * style->width.value.percent / 100; @@ -79,19 +105,29 @@ void layout_block(struct box * box, unsigned long width, struct box * cont, box->height = layout_block_children(box, box->width, cont, cx, cy); switch (style->height.height) { case CSS_HEIGHT_AUTO: + /* use the computed height */ break; case CSS_HEIGHT_LENGTH: - box->height = len(&style->height.length, 20); + box->height = len(&style->height.length, box->style); break; } } + +/** + * layout_block_children -- recursively layout block children + * + * (as above) + */ + unsigned long layout_block_children(struct box * box, unsigned long width, struct box * cont, unsigned long cx, unsigned long cy) { struct box * c; unsigned long y = 0; - + + assert(box->type == BOX_BLOCK || box->type == BOX_FLOAT || box->type == BOX_TABLE_CELL); + for (c = box->children; c != 0; c = c->next) { switch (c->type) { case BOX_BLOCK: @@ -122,91 +158,233 @@ unsigned long layout_block_children(struct box * box, unsigned long width, struc return y; } + +/** + * find_sides -- find left and right margins + * + * fl first float in float list + * y0, y1 y range to search + * x1, x1 margins updated + * left float on left if present + * right float on right if present + */ + void find_sides(struct box * fl, unsigned long y0, unsigned long y1, - unsigned long * x0, unsigned long * x1) + unsigned long * x0, unsigned long * x1, struct box ** left, struct box ** right) { + *left = *right = 0; for (; fl; fl = fl->next_float) { if (y0 <= fl->y + fl->height && fl->y <= y1) { - if (fl->style->float_ == CSS_FLOAT_LEFT && *x0 < fl->x + fl->width) + if (fl->style->float_ == CSS_FLOAT_LEFT && *x0 < fl->x + fl->width) { *x0 = fl->x + fl->width; - else if (fl->style->float_ == CSS_FLOAT_RIGHT && fl->x < *x1) + *left = fl; + } else if (fl->style->float_ == CSS_FLOAT_RIGHT && fl->x < *x1) { *x1 = fl->x; + *right = fl; + } } } fprintf(stderr, "find_sides: y0 %li y1 %li => x0 %li x1 %li\n", y0, y1, *x0, *x1); } + +/** + * layout_inline_container -- layout lines of text or inline boxes with floats + * + * box inline container + * width horizontal space available + * cont ancestor box which defines horizontal space, for inlines + * cx, cy box position relative to cont + */ + void layout_inline_container(struct box * box, unsigned long width, struct box * cont, unsigned long cx, unsigned long cy) { - /* TODO: write this */ struct box * c; unsigned long y = 0; - unsigned long x = 0; - unsigned long x0 = cx, x1 = cx + width; - const char * end; - struct box * c2; - struct font_split split; - find_sides(cont->float_children, cy + y, cy + y, &x0, &x1); - x = x0; + assert(box->type == BOX_INLINE_CONTAINER); for (c = box->children; c != 0; ) { - if (c->type == BOX_FLOAT) { - c->float_children = 0; - layout_block(c, width, c, 0, 0); - c->x = cx; - c->y = cy + y + 30; - fprintf(stderr, "float at %li %li, size %li %li\n", c->x, c->y, c->width, c->height); - c->next_float = cont->float_children; - cont->float_children = c; - c = c->next; - continue; + c = layout_line(c, width, &y, cy + y, cont); + } + + box->width = width; + box->height = y; +} + + +signed long line_height(struct css_style * style) +{ + assert(style->line_height.size == CSS_LINE_HEIGHT_LENGTH || + style->line_height.size == CSS_LINE_HEIGHT_ABSOLUTE); + + if (style->line_height.size == CSS_LINE_HEIGHT_LENGTH) + return len(&style->line_height.value.length, style); + else + return style->line_height.value.absolute * len(&style->font_size.value.length, 0); +} + + +struct box * layout_line(struct box * first, unsigned long width, unsigned long * y, + unsigned long cy, struct box * cont) +{ + unsigned long height; + unsigned long x0 = 0; + unsigned long x1 = width; + unsigned long x, h, xp; + struct box * left; + struct box * right; + struct box * b; + struct box * c; + struct box * d; + + fprintf(stderr, "layout_line: '%.*s' %li %li %li\n", first->length, first->text, width, *y, cy); + + /* find sides at top of line */ + find_sides(cont->float_children, cy, cy, &x0, &x1, &left, &right); + + /* get minimum line height from containing block */ + height = line_height(first->parent->parent->style); + + /* pass 1: find height of line assuming sides at top of line */ + for (x = 0, b = first; x < x1 - x0 && b != 0; b = b->next) { + assert(b->type == BOX_INLINE || b->type == BOX_FLOAT); + if (b->type == BOX_INLINE) { + h = line_height(b->style ? b->style : b->parent->parent->style); + b->height = h; + if (h > height) height = h; + x += font_width(b->style, b->text, b->length); } - - assert(c->type == BOX_INLINE); - - split = font_split(0, c->font, c->text, x1 - x, x == x0); - if (*(split.end) == 0) { - /* fits into this line */ - c->x = x; - c->y = y; - c->width = split.width; - c->height = split.height; - c->length = split.end - c->text; - x += c->width; - c = c->next; - } else if (split.end == c->text) { - /* doesn't fit at all: move down a line */ - y += 30; - x0 = cx; - x1 = cx + width; - find_sides(cont->float_children, cy + y, cy + y, &x0, &x1); - x = x0; + } + + /* find new sides using this height */ + find_sides(cont->float_children, cy, cy + height, &x0, &x1, &left, &right); + + /* pass 2: place boxes in line */ + for (x = xp = 0, b = first; x < x1 - x0 && b != 0; b = b->next) { + if (b->type == BOX_INLINE) { + b->x = x; + xp = x; + b->width = font_width(b->style, b->text, b->length); + x += b->width; + c = b; + fprintf(stderr, "layout_line: '%.*s' %li %li\n", b->length, b->text, xp, x); + } else { + b->float_children = 0; + css_dump_style(b->style); + layout_block(b, width, b, 0, 0); + if (b->width < (x1 - x0) - x || (left == 0 && right == 0 && x == 0)) { + /* fits next to this line, or this line is empty with no floats */ + if (b->style->float_ == CSS_FLOAT_LEFT) { + b->x = x0; + x0 += b->width; + left = b; + } else { + b->x = x1 - b->width; + x1 -= b->width; + right = b; + } + b->y = cy; + fprintf(stderr, "layout_line: float fits %li %li, edges %li %li\n", + b->x, b->y, x0, x1); + } else { + /* doesn't fit: place below */ + place_float_below(b, width, cy + height + 1, cont); + fprintf(stderr, "layout_line: float doesn't fit %li %li\n", b->x, b->y); + } + b->next_float = cont->float_children; + cont->float_children = b; + } + } + + if (x1 - x0 < x) { + /* the last box went over the end */ + char * space = strchr(c->text, ' '); + char * space2 = space; + unsigned long w = font_width(c->style, c->text, space - c->text), wp = w; + struct box * c2; + + if (x1 - x0 < xp + w && left == 0 && right == 0 && c == first) { + /* first word doesn't fit, but no floats and first on line so force in */ + c2 = memcpy(xcalloc(1, sizeof(struct box)), c, sizeof(struct box)); + c2->text = space + 1; + c2->length = c->length - (c2->text - c->text); + c->length = space - c->text; + c2->next = c->next; + c->next = c2; + b = c2; + fprintf(stderr, "layout_line: overflow, forcing\n"); + } else if (x1 - x0 < xp + w) { + /* first word doesn't fit, but full width not available so leave for later */ + b = c; + fprintf(stderr, "layout_line: overflow, leaving\n"); } else { - /* split into two lines */ - c->x = x; - c->y = y; - c->width = split.width; - c->height = split.height; - c->length = split.end - c->text; - y += 30; - x0 = cx; - x1 = cx + width; - find_sides(cont->float_children, cy + y, cy + y, &x0, &x1); - x = x0; + /* fit as many words as possible */ + while (xp + w < x1 - x0) { + fprintf(stderr, "%li + %li = %li < %li = %li - %li\n", + xp, w, xp + w, x1 - x0, x1, x0); + space = space2; + wp = w; + space2 = strchr(space + 1, ' '); + w = font_width(c->style, c->text, space2 - c->text); + } c2 = memcpy(xcalloc(1, sizeof(struct box)), c, sizeof(struct box)); - c2->text = split.end; + c2->text = space + 1; + c2->length = c->length - (c2->text - c->text); + c->length = space - c->text; c2->next = c->next; c->next = c2; - c = c2; + b = c2; + fprintf(stderr, "layout_line: overflow, fit\n"); } + c->width = wp; } - box->width = width; - box->height = y + 30; + /* set positions */ + for (d = first; d != b; d = d->next) { + if (d->type == BOX_INLINE) { + d->x += x0; + d->y = *y; + } + } + + *y += height + 1; + return b; } + + +void place_float_below(struct box * c, unsigned long width, unsigned long y, struct box * cont) +{ + unsigned long x0, x1, yy = y; + struct box * left; + struct box * right; + do { + y = yy; + x0 = 0; + x1 = width; + find_sides(cont->float_children, y, y, &x0, &x1, &left, &right); + if (left != 0 && right != 0) { + yy = (left->y + left->height < right->y + right->height ? + left->y + left->height : right->y + right->height) + 1; + } else if (left == 0 && right != 0) { + yy = right->y + right->height + 1; + } else if (left != 0 && right == 0) { + yy = left->y + left->height + 1; + } + } while (!((left == 0 && right == 0) || (c->width < x1 - x0))); + + if (c->style->float_ == CSS_FLOAT_LEFT) { + c->x = x0; + } else { + c->x = x1 - c->width; + } + c->y = y; +} + + + /** * layout a table * @@ -235,7 +413,7 @@ void layout_table(struct box * table, unsigned long width, struct box * cont, /* find table width */ switch (table->style->width.width) { case CSS_WIDTH_LENGTH: - table_width = len(&table->style->width.value.length, 20); + table_width = len(&table->style->width.value.length, table->style); break; case CSS_WIDTH_PERCENT: table_width = width * table->style->width.value.percent / 100; @@ -252,7 +430,7 @@ void layout_table(struct box * table, unsigned long width, struct box * cont, assert(c->type == BOX_TABLE_CELL); switch (c->style->width.width) { case CSS_WIDTH_LENGTH: - used_width += len(&c->style->width.value.length, 20); + used_width += len(&c->style->width.value.length, c->style); break; case CSS_WIDTH_PERCENT: used_width += table_width * c->style->width.value.percent / 100; @@ -277,7 +455,7 @@ void layout_table(struct box * table, unsigned long width, struct box * cont, for (i = 1, c = table->children->children; c != 0; i++, c = c->next) { switch (c->style->width.width) { case CSS_WIDTH_LENGTH: - x += len(&c->style->width.value.length, 10) + extra_width; + x += len(&c->style->width.value.length, c->style) + extra_width; break; case CSS_WIDTH_PERCENT: x += table_width * c->style->width.value.percent / 100 + extra_width; @@ -305,7 +483,7 @@ void layout_table(struct box * table, unsigned long width, struct box * cont, case CSS_HEIGHT_AUTO: break; case CSS_HEIGHT_LENGTH: - c->height = len(&c->style->height.length, 10); + c->height = len(&c->style->height.length, c->style); break; } c->x = xs[i]; -- cgit v1.2.3