1 files changed, 247 insertions, 69 deletions

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 <assert.h>
@@ -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];