Better handle automatic column width assignments in the presence of

horizontal spans, by implementing a moderately difficult iterative
algoritm.  The benefit is that spans containing long text no longer
cause an excessive width of their starting column.

The result is likely not optimal, in particular in the presence
of many spans overlapping in complicated ways nor when spans
interact with equalizing or maximizing colums.  But i doubt the
practical usefulness of making this more complicated.

Issue originally reported in synaptics(4), which now looks better,
by tedu@ three years ago, and reminded by Pali Rohar this summer.

1 files changed, 206 insertions, 43 deletions

diff --git a/usr.bin/mandoc/out.c b/usr.bin/mandoc/out.c
index 24c3de02b88..d5d2837f023 100644
--- a/usr.bin/mandoc/out.c
+++ b/usr.bin/mandoc/out.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: out.c,v 1.46 2018/11/25 19:23:59 schwarze Exp $ */
+/*	$OpenBSD: out.c,v 1.47 2018/11/29 01:54:58 schwarze Exp $ */
 /*
  * Copyright (c) 2009, 2010, 2011 Kristaps Dzonsons <kristaps@bsd.lv>
  * Copyright (c) 2011,2014,2015,2017,2018 Ingo Schwarze <schwarze@openbsd.org>
@@ -28,12 +28,19 @@
 #include "mandoc.h"
 #include "out.h"
 
-static	void	tblcalc_data(struct rofftbl *, struct roffcol *,
+struct	tbl_colgroup {
+	struct tbl_colgroup	*next;
+	size_t			 wanted;
+	int			 startcol;
+	int			 endcol;
+};
+
+static	size_t	tblcalc_data(struct rofftbl *, struct roffcol *,
 			const struct tbl_opts *, const struct tbl_dat *,
 			size_t);
-static	void	tblcalc_literal(struct rofftbl *, struct roffcol *,
+static	size_t	tblcalc_literal(struct rofftbl *, struct roffcol *,
 			const struct tbl_dat *, size_t);
-static	void	tblcalc_number(struct rofftbl *, struct roffcol *,
+static	size_t	tblcalc_number(struct rofftbl *, struct roffcol *,
 			const struct tbl_opts *, const struct tbl_dat *);
 
 
@@ -102,16 +109,18 @@ a2roffsu(const char *src, struct roffsu *dst, enum roffscale def)
  * used for the actual width calculations.
  */
 void
-tblcalc(struct rofftbl *tbl, const struct tbl_span *sp,
+tblcalc(struct rofftbl *tbl, const struct tbl_span *sp_first,
     size_t offset, size_t rmargin)
 {
 	struct roffsu		 su;
 	const struct tbl_opts	*opts;
+	const struct tbl_span	*sp;
 	const struct tbl_dat	*dp;
 	struct roffcol		*col;
-	size_t			 ewidth, xwidth;
-	int			 hspans;
-	int			 icol, maxcol, necol, nxcol, quirkcol;
+	struct tbl_colgroup	*first_group, **gp, *g;
+	size_t			*colwidth;
+	size_t			 ewidth, min1, min2, wanted, width, xwidth;
+	int			 done, icol, maxcol, necol, nxcol, quirkcol;
 
 	/*
 	 * Allocate the master column specifiers.  These will hold the
@@ -119,33 +128,34 @@ tblcalc(struct rofftbl *tbl, const struct tbl_span *sp,
 	 * must be freed and nullified by the caller.
 	 */
 
-	assert(NULL == tbl->cols);
-	tbl->cols = mandoc_calloc((size_t)sp->opts->cols,
+	assert(tbl->cols == NULL);
+	tbl->cols = mandoc_calloc((size_t)sp_first->opts->cols,
 	    sizeof(struct roffcol));
-	opts = sp->opts;
+	opts = sp_first->opts;
 
-	for (maxcol = -1; sp; sp = sp->next) {
-		if (TBL_SPAN_DATA != sp->pos)
+	maxcol = -1;
+	first_group = NULL;
+	for (sp = sp_first; sp != NULL; sp = sp->next) {
+		if (sp->pos != TBL_SPAN_DATA)
 			continue;
-		hspans = 1;
+
 		/*
 		 * Account for the data cells in the layout, matching it
 		 * to data cells in the data section.
 		 */
-		for (dp = sp->first; dp; dp = dp->next) {
-			/* Do not used spanned cells in the calculation. */
-			if (0 < --hspans)
-				continue;
-			hspans = dp->hspans;
-			if (1 < hspans)
-				continue;
+
+		gp = &first_group;
+		for (dp = sp->first; dp != NULL; dp = dp->next) {
 			icol = dp->layout->col;
-			while (maxcol < icol)
+			while (icol > maxcol)
 				tbl->cols[++maxcol].spacing = SIZE_MAX;
 			col = tbl->cols + icol;
 			col->flags |= dp->layout->flags;
 			if (dp->layout->flags & TBL_CELL_WIGN)
 				continue;
+
+			/* Handle explicit width specifications. */
+
 			if (dp->layout->wstr != NULL &&
 			    dp->layout->width == 0 &&
 			    a2roffsu(dp->layout->wstr, &su, SCALE_EN)
@@ -158,15 +168,164 @@ tblcalc(struct rofftbl *tbl, const struct tbl_span *sp,
 			    (col->spacing == SIZE_MAX ||
 			     col->spacing < dp->layout->spacing))
 				col->spacing = dp->layout->spacing;
-			tblcalc_data(tbl, col, opts, dp,
+
+			/*
+			 * Calculate an automatic width.
+			 * Except for spanning cells, apply it.
+			 */
+
+			width = tblcalc_data(tbl,
+			    dp->hspans == 0 ? col : NULL,
+			    opts, dp,
 			    dp->block == 0 ? 0 :
 			    dp->layout->width ? dp->layout->width :
 			    rmargin ? (rmargin + sp->opts->cols / 2)
 			    / (sp->opts->cols + 1) : 0);
+			if (dp->hspans == 0)
+				continue;
+
+			/*
+			 * Build an ordered, singly linked list
+			 * of all groups of columns joined by spans,
+			 * recording the minimum width for each group.
+			 */
+
+			while (*gp != NULL && ((*gp)->startcol < icol ||
+			    (*gp)->endcol < icol + dp->hspans))
+				gp = &(*gp)->next;
+			if (*gp == NULL || (*gp)->startcol > icol ||
+                            (*gp)->endcol > icol + dp->hspans) {
+				g = mandoc_malloc(sizeof(*g));
+				g->next = *gp;
+				g->wanted = width;
+				g->startcol = icol;
+				g->endcol = icol + dp->hspans;
+				*gp = g;
+			} else if ((*gp)->wanted < width)
+				(*gp)->wanted = width;
 		}
 	}
 
 	/*
+	 * Column spacings are needed for span width calculations,
+	 * so set the default values now.
+	 */
+
+	for (icol = 0; icol <= maxcol; icol++)
+		if (tbl->cols[icol].spacing == SIZE_MAX || icol == maxcol)
+			tbl->cols[icol].spacing = 3;
+
+	/*
+	 * Replace the minimum widths with the missing widths,
+	 * and dismiss groups that are already wide enough.
+	 */
+
+	gp = &first_group;
+	while ((g = *gp) != NULL) {
+		done = 0;
+		for (icol = g->startcol; icol <= g->endcol; icol++) {
+			width = tbl->cols[icol].width;
+			if (icol < g->endcol)
+				width += tbl->cols[icol].spacing;
+			if (g->wanted <= width) {
+				done = 1;
+				break;
+			} else
+				(*gp)->wanted -= width;
+		}
+		if (done) {
+			*gp = g->next;
+			free(g);
+		} else
+			gp = &(*gp)->next;
+	}
+
+	colwidth = mandoc_reallocarray(NULL, maxcol + 1, sizeof(*colwidth));
+	while (first_group != NULL) {
+
+		/*
+		 * Rebuild the array of the widths of all columns
+		 * participating in spans that require expansion.
+		 */
+
+		for (icol = 0; icol <= maxcol; icol++)
+			colwidth[icol] = SIZE_MAX;
+		for (g = first_group; g != NULL; g = g->next)
+			for (icol = g->startcol; icol <= g->endcol; icol++)
+				colwidth[icol] = tbl->cols[icol].width;
+
+		/*
+		 * Find the smallest and second smallest column width
+		 * among the columns which may need expamsion.
+		 */
+
+		min1 = min2 = SIZE_MAX;
+		for (icol = 0; icol <= maxcol; icol++) {
+			if (min1 > colwidth[icol]) {
+				min2 = min1;
+				min1 = colwidth[icol];
+			} else if (min1 < colwidth[icol] &&
+			    min2 > colwidth[icol])
+				min2 = colwidth[icol];
+		}
+
+		/*
+		 * Find the minimum wanted width
+		 * for any one of the narrowest columns,
+		 * and mark the columns wanting that width.
+		 */
+
+		wanted = min2;
+		for (g = first_group; g != NULL; g = g->next) {
+			necol = 0;
+			for (icol = g->startcol; icol <= g->endcol; icol++)
+				if (tbl->cols[icol].width == min1)
+					necol++;
+			if (necol == 0)
+				continue;
+			width = min1 + (g->wanted - 1) / necol + 1;
+			if (width > min2)
+				width = min2;
+			if (wanted > width)
+				wanted = width;
+			for (icol = g->startcol; icol <= g->endcol; icol++)
+				if (colwidth[icol] == min1 ||
+				    (colwidth[icol] < min2 &&
+				     colwidth[icol] > width))
+					colwidth[icol] = width;
+		}
+
+		/* Record the effect of the widening on the group list. */
+
+		gp = &first_group;
+		while ((g = *gp) != NULL) {
+			done = 0;
+			for (icol = g->startcol; icol <= g->endcol; icol++) {
+				if (colwidth[icol] != wanted ||
+				    tbl->cols[icol].width == wanted)
+					continue;
+				if (g->wanted <= wanted - min1) {
+					done = 1;
+					break;
+				}
+				g->wanted -= wanted - min1;
+			}
+			if (done) {
+				*gp = g->next;
+				free(g);
+			} else
+				gp = &(*gp)->next;
+		}
+
+		/* Record the effect of the widening on the columns. */
+
+		for (icol = 0; icol <= maxcol; icol++)
+			if (colwidth[icol] == wanted)
+				tbl->cols[icol].width = wanted;
+	}
+	free(colwidth);
+
+	/*
 	 * Align numbers with text.
 	 * Count columns to equalize and columns to maximize.
 	 * Find maximum width of the columns to equalize.
@@ -181,8 +340,6 @@ tblcalc(struct rofftbl *tbl, const struct tbl_span *sp,
 			col->decimal += (col->width - col->nwidth) / 2;
 		else
 			col->width = col->nwidth;
-		if (col->spacing == SIZE_MAX || icol == maxcol)
-			col->spacing = 3;
 		if (col->flags & TBL_CELL_EQUAL) {
 			necol++;
 			if (ewidth < col->width)
@@ -255,7 +412,7 @@ tblcalc(struct rofftbl *tbl, const struct tbl_span *sp,
 	}
 }
 
-static void
+static size_t
 tblcalc_data(struct rofftbl *tbl, struct roffcol *col,
     const struct tbl_opts *opts, const struct tbl_dat *dp, size_t mw)
 {
@@ -267,26 +424,24 @@ tblcalc_data(struct rofftbl *tbl, struct roffcol *col,
 	case TBL_CELL_HORIZ:
 	case TBL_CELL_DHORIZ:
 		sz = (*tbl->len)(1, tbl->arg);
-		if (col->width < sz)
+		if (col != NULL && col->width < sz)
 			col->width = sz;
-		break;
+		return sz;
 	case TBL_CELL_LONG:
 	case TBL_CELL_CENTRE:
 	case TBL_CELL_LEFT:
 	case TBL_CELL_RIGHT:
-		tblcalc_literal(tbl, col, dp, mw);
-		break;
+		return tblcalc_literal(tbl, col, dp, mw);
 	case TBL_CELL_NUMBER:
-		tblcalc_number(tbl, col, opts, dp);
-		break;
+		return tblcalc_number(tbl, col, opts, dp);
 	case TBL_CELL_DOWN:
-		break;
+		return 0;
 	default:
 		abort();
 	}
 }
 
-static void
+static size_t
 tblcalc_literal(struct rofftbl *tbl, struct roffcol *col,
     const struct tbl_dat *dp, size_t mw)
 {
@@ -295,11 +450,12 @@ tblcalc_literal(struct rofftbl *tbl, struct roffcol *col,
 	char		*end;	/* End of the current line. */
 	size_t		 lsz;	/* Length of the current line. */
 	size_t		 wsz;	/* Length of the current word. */
+	size_t		 msz;   /* Length of the longest line. */
 
 	if (dp->string == NULL || *dp->string == '\0')
-		return;
+		return 0;
 	str = mw ? mandoc_strdup(dp->string) : dp->string;
-	lsz = 0;
+	msz = lsz = 0;
 	for (beg = str; beg != NULL && *beg != '\0'; beg = end) {
 		end = mw ? strchr(beg, ' ') : NULL;
 		if (end != NULL) {
@@ -312,14 +468,17 @@ tblcalc_literal(struct rofftbl *tbl, struct roffcol *col,
 			lsz += 1 + wsz;
 		else
 			lsz = wsz;
-		if (col->width < lsz)
-			col->width = lsz;
+		if (msz < lsz)
+			msz = lsz;
 	}
 	if (mw)
 		free((void *)str);
+	if (col != NULL && col->width < msz)
+		col->width = msz;
+	return msz;
 }
 
-static void
+static size_t
 tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
 		const struct tbl_opts *opts, const struct tbl_dat *dp)
 {
@@ -328,7 +487,11 @@ tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
 	char		 buf[2];
 
 	if (dp->string == NULL || *dp->string == '\0')
-		return;
+		return 0;
+
+	totsz = (*tbl->slen)(dp->string, tbl->arg);
+	if (col == NULL)
+		return totsz;
 
 	/*
 	 * Find the last digit and
@@ -351,11 +514,10 @@ tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
 
 	/* Not a number, treat as a literal string. */
 
-	totsz = (*tbl->slen)(dp->string, tbl->arg);
 	if (lastdigit == NULL) {
-		if (col->width < totsz)
+		if (col != NULL && col->width < totsz)
 			col->width = totsz;
-		return;
+		return totsz;
 	}
 
 	/* Measure the width of the integer part. */
@@ -385,4 +547,5 @@ tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
 
 	if (totsz > col->nwidth)
 		col->nwidth = totsz;
+	return totsz;
 }