source@mandoc.bsd.lv
 help / color / mirror / Atom feed
* mandoc: Fix an infinite loop that could occur during some cases of
@ 2021-09-07 17:08 schwarze
  0 siblings, 0 replies; only message in thread
From: schwarze @ 2021-09-07 17:08 UTC (permalink / raw)
  To: source

Log Message:
-----------
Fix an infinite loop that could occur during some cases of horizontally
overlapping horizontal spans.  One span would calculate a desired
target width and start preparations for applying it to some columns,
then the other span would overwrite the target width with a different
value and also start preparations for applying that one to some
columns, which could sometimes confuse the code doing the final
distribution to the point of not doing anything at all before
entering the next iteration.

Fix this by making sure the distribution is done step by step, doing
one step at a time rather than allowing multiple steps to conflict.
Specifically, always do the smallest useful step first.  This change
also simplifies the code.  For example, the local "colwidth" array
is no longer needed.

Note that the algorithm still differs from the one implemented in
GNU tbl(1), which appears to not even try to harmonize column widths
but seems to simply distribute the same amount to all constituent
columns, no matter whether their intrinsic width is narrow or wide.
Adopting a GNU-compatible algorithm might allow further simplifiction
in addition to yielding even more similar output, but i do not want
to implement any major changes of the algorithm at this time.

The infinite loop was reported by <Oliver dot Corff at email dot de>.

Modified Files:
--------------
    mandoc:
        out.c

Revision Data
-------------
Index: out.c
===================================================================
RCS file: /home/cvs/mandoc/mandoc/out.c,v
retrieving revision 1.81
retrieving revision 1.82
diff -Lout.c -Lout.c -u -p -r1.81 -r1.82
--- out.c
+++ out.c
@@ -123,7 +123,6 @@ tblcalc(struct rofftbl *tbl, const struc
 	const struct tbl_dat	*dp;
 	struct roffcol		*col;
 	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;
 
@@ -257,33 +256,21 @@ tblcalc(struct rofftbl *tbl, const struc
 			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]) {
+			width = tbl->cols[icol].width;
+			if (min1 > width) {
 				min2 = min1;
-				min1 = colwidth[icol];
-			} else if (min1 < colwidth[icol] &&
-			    min2 > colwidth[icol])
-				min2 = colwidth[icol];
+				min1 = width;
+			} else if (min1 < width && min2 > width)
+				min2 = width;
 		}
 
 		/*
@@ -305,26 +292,22 @@ tblcalc(struct rofftbl *tbl, const struc
 				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. */
+		/* Record the effect of the widening. */
 
 		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)
+				if (tbl->cols[icol].width != min1)
 					continue;
 				if (g->wanted <= wanted - min1) {
+					tbl->cols[icol].width += g->wanted;
 					done = 1;
 					break;
 				}
+				tbl->cols[icol].width = wanted;
 				g->wanted -= wanted - min1;
 			}
 			if (done) {
@@ -333,14 +316,7 @@ tblcalc(struct rofftbl *tbl, const struc
 			} 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.
--
 To unsubscribe send an email to source+unsubscribe@mandoc.bsd.lv


^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2021-09-07 17:08 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-07 17:08 mandoc: Fix an infinite loop that could occur during some cases of schwarze

source@mandoc.bsd.lv

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://inbox.vuxu.org/mandoc-source

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V1 mandoc-source mandoc-source/ https://inbox.vuxu.org/mandoc-source \
		source@mandoc.bsd.lv
	public-inbox-index mandoc-source

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://inbox.vuxu.org/vuxu.archive.mandoc.source


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git