# Avoiding “rivers” in successive lines of type

This question led to a new feature in a package:
impnattypo

The following quote is from James Felici, The Complete Manual of Typography (2003), p. 161:

Rivers occur when word spaces stack one above the other in successive lines of type, creating the appearance of fissures running through the text [...]. Rivers are accidents of composition, and software isn't yet smart enough to detect them, much less do anything about them.

On the following page, Felici shows an example of a "mighty river" running through a paragraph. Below, you'll find the LaTeX code and the pictured output of my (somewhat abridged) recreation of Felicis example. (The layout is chosen so that the effect also occurs if one uses the microtype package with its default settings.)

\documentclass{article}

\usepackage{mathptmx}
\usepackage{microtype}

\textwidth 247pt
\parindent 23pt
\frenchspacing

\begin{document}

Though the Pearl measures less than 50~miles in total length from its
modest source as a cool mountain spring to the screaming cascades and
steaming estuary of its downstream reaches, over those miles, the
river has in one place or another everything you could possibly ask
for. You can roam among lush temperate rain forests, turgid white
water canyons, contemplative meanders among aisles of staid aspens
(with trout leaping to slurp all the afternoon insects from its calm
surface), and forbidding swamp land as formidable as any that Humphrey
Bogart muddled through in \emph{The African Queen}.

\end{document}


So, was Felici right that "software isn't yet smart enough" to deal with rivers? Or is this something TeX can handle? And if not TeX, then possibly LuaTeX?

EDIT: As rassie pointed out that TeX is Turing-complete, let me clarify that I'm interested in solutions that either already exist or could be implemented with reasonable time and effort.

-
For what it's worth, osdir.com/ml/tex.context/2001-01/msg00057.html is a nice overview of some ideas. –  Pieter Oct 24 '10 at 17:14
Also, FYI: you don't need all those %s. Consecutive white space is treated as a single space, unless it's two newlines in a row. –  Antal S-Z Oct 24 '10 at 19:18
What a lovely example of a "river" in a text block. But I should note that even though I knew what to look for, the river didn't jump out at me for some time. I think the slight meandering of the spaces helps minimize the visual problems. I see rivers in fixed-width fonts more commonly than variable-width. (For instance I see one covering the first three lines of this text box, though I imagine it will be gone in the published comment.) –  Jon Ericson Jun 6 '11 at 23:11
@Jon: If you like it, upvote it. ;-) –  lockstep Jun 6 '11 at 23:14
Oops. I completely forgot about that! Done. –  Jon Ericson Jun 6 '11 at 23:16

I have added a first version of an algorithm to detect rivers using Lua to the impnattypo package on github. To use it, simply use the rivers option:

\usepackage[draft,rivers]{impnattypo}


Here is an example result:

Beware that there might still be some bugs ;-)

-

I think it's more of an algorithm problem than TeX's. Both TeX and Lua are Turing-complete programming languages, so it's possible to implement any algorithm in it provided enough time.

So let's assume you've got an algorithm which can tell whether a paragraph of text has a river inside it or not, e.g. by graphically putting vertical lines over the paragraph and checking whether all dots underneath are white. Then one could define a \riverpenalty variable bound to the output of that algorithm, which would, if set high enough, force TeX to select an another rendering of that particular paragraph.

However, if I'm not completely mistaken, classic TeX first builds lines and then paragraphs, i.e. a paragraph-bound penalty would not lead to a different rendering for a particular line. That would mean that river detection would be possible with classic TeX but not river correction.

On the other hand, many of PDFTeX's and XeTeX's algorithms, especially those dealing with microtypography, probably need ways to correct a line's rendering based on some paragraph penalty. In that case, implementing a river correction should be possible with one of those advanced engines, either in the engine itself or using its API -- and at that point it doesn't matter which language you take, either pure TeX or Lua or something completely different.

-
@rassie: Thanks for reminding me that TeX is Turing-complete. I've edited my question to clarify that I'm interested in solutions existing in the here and now, so to speak. ;-) –  lockstep Oct 24 '10 at 16:41
"classic TeX first builds lines and then paragraphs" — you're either mistaken on this point or you've just worded this sentence poorly; the line breaks are chosen while taking the entire paragraph into account. –  Will Robertson Oct 25 '10 at 8:13
@Will: I'm far from TeXpert and you are probably right on that one -- on second thinking, it's pretty obvious that line-breaking can't actually be done without taking the paragraph into account. Gotta re-read TeXbook again :) –  Nikolai Prokoschenko Oct 25 '10 at 17:39
@rassie: There's one more thing in your answer that is not quite OK: TeX being Turing complete doesn't necessarily help; you just can't check "whether all dots underneath [a vertical line] are white". TeX only sees the bounding boxes of the characters, not the characters itself. For this problem, the bounding boxes should be a close enough approximation, but for others it's a great obstacle. Here's an example where Turing completeness of TeX doesn't seem to help. –  Hendrik Vogt Oct 27 '10 at 9:50
@rassie: It was clear to me that you wrote your answer before lockstep's edit. But my point was that Turing completeness does not imply "that the problem is generally solvable". There are obstacles that you just can't overcome! –  Hendrik Vogt Oct 27 '10 at 14:15
show 1 more comment

Might not be a very helpful answer, but ANT (which is modelled after TeX) claims to have river detection, so may be some one could look at that and implement it in lua (Hans in a recent talk mentioned his effort to rewrite TeX paragraph builder in lua, so may be both can be combined.)

-
I've tried to get ANT to avoid rivers, but never got any satisfying results, even the author of ANT couldn't help me. –  topskip Oct 24 '10 at 19:36
@Patrick: Didn't you do some experiments on avoiding rivers in plain luatex? –  Aditya Oct 24 '10 at 20:50
@Aditya: Not LuaTeX, but I implemented my own Knuth & Plass total-fit line breaking algorithm and made experiments with that. Detecting rivers wasn't hard, but I have not found a good way to eliminate them (time complexity is a killer here). –  topskip Oct 25 '10 at 17:58

I am not sure if the problem is solvable, and it may require a new generation of very fast computers (trials with different algorithms can take over six hours to iterate). The example below can produce rivers mightier than Felici's example.

\documentclass[11pt]{article}
\begin{document}

\def\samplerivers{%
\hskip1em Repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated.}

\begin{minipage}{1.9in}
\looseness=-1 \hyphenpenalty=0\samplerivers
\end{minipage}\hspace{.8cm}
\begin{minipage}{1.9in}
\hyphenpenalty=100\samplerivers
\end{minipage}\hspace{.8cm}
\begin{minipage}{1.9in}
\hyphenpenalty=100000 \samplerivers
\end{minipage}

\end{document}


One attempt at attacking the problem is that of Holkner. He attempted to optimize over multiple objectives but as he writes:

... performance degrades so badly that some of the tests had to be stopped when they took more than six hours to complete.

TeX's algorithm does not include for any parameters to minimize rivers.

-
Many thanks for the link - I've already started reading. –  lockstep Oct 24 '10 at 19:23