What exactly is the procedure that the TeX line-breaking algorithm uses when it needs to set overfull boxes?

Question

The TeXbook describes (in chapter 14) in detail how TeX calculates the total demerits associated with breaking a paragraph into lines and that TeX chooses the sequence of breakpoints that yield the fewest total demerits (in a process with three passes). However, it only briefly describes what exactly happens if no sequence of breakpoints exists that satisfies the requirements:

Roughly speaking, \TeX\ breaks paragraphs into lines in the following way: Breakpoints are inserted between words or after hyphens so as to produce lines whose badnesses do not exceed the current ^|\tolerance|. If there's no way to insert such breakpoints, an ^{overfull box} is set.

No further details on the overfull box scenario follow. I am interested in these details: Can one describe in simple terms which words TeX chooses to stick out into the margin in such a case? (Or do you have to read the TeX source code to understand that?) Since TeX considers a paragraph as a whole, the issue of not having a permissible sequence of breakpoints is not really caused by a single word.

Furthermore, I think that the above statement from the TeXbook is not entirely correct: When a paragraph contains a \linebreak, it may be set with underfull lines instead. This scenario basically satisfies the premise "there's no way to insert such breakpoints", yet TeX sets underfull lines instead of overfull lines as stated above.

(This question is mainly out of interest. But there is indeed a scenario where a paragraph with overfull lines may end up in a finished document, namely if the excess size of the overfull lines is not more than \hfuzz.)

Answer 1

TeX chooses line breaks based on a calculation of line demerits that are totaled in an amount called total demerits.

A first pass that doesn't apply the hyphenation capability of TeX might fail to obey the limits that are set by an integer parameter \pretolerance. But the second pass of TeX always succeed. It might not be successful in the sense that TeX has to create overfull lines. Underfull lines are only created if the user wants them.

What I mean. You can set \parfillskip=0pt and give TeX a short line with, say, just one space and TeX reports and underfull line. The author is always responsible for the last line break; nothing is inserted by TeX in a one-line paragraph. Similar, a line break command that outputs \penalty-10000 forces TeX to obey the wish of the author to break the line at this point. It's a forced break nothing that TeX inserts.

Here is how TeX operates; I try to use simple words but it is a technical topic: TeX breaks lines at glue (including at kern followed by glue and at the end of inline math followed by glue) or at a penalty, i.e., a hyphen in the text, a hyphen inserted by TeX in the second pass, after a relation in math mode, etc. as well as a \penalty-10000 as explained above.

Of course, TeX counts the beginning of the text as the initial breakpoint. To create a paragraph TeX goes from a place where a break is possible---in the second pass the place might be created by TeX through an inserted hyphen---to the next until the width of the collected material including either shrink- or stretchability allows TeX to build a line with a badness obeying the current tolerance together with one of the earlier found (or forced) breakpoints. TeX marks such a place as a breakpoint and remembers for it the associated previous breakpoint so that it can later go from the end of the paragraph back to the start with the lines that minimize the total demerits.

TeX also creates a breakpoint if it sees a user inserted \penalty-10000. Then it starts the process as if it were at the start of the paragraph. No following breakpoint can reach over this breakpoint, i.e., the next breakpoint must record this user forced breakpoint as the previous breakpoint.

If no place can be found to build a line with a badness at most as large as the current tolerance TeX stops the processing if it is in the first pass and then it starts the second pass. Otherwise if TeX is in the second pass it looks for the next place where a break is possible without building an underfull line. This becomes a breakpoint although the line is overfull. Next, TeX continues the process. Thus the second pass goes through the whole paragraph. Note, a paragraph can have more than one overfull line.

If \emergencystretch isn't 0pt and the second pass couldn't do what was requested, i.e., find breakpoints without an overfull line or reduce the number of lines if \looseness=-1, then TeX starts a third pass that works like the second. The difference is that TeX adds the dimension of the \emergencystretch to the stretchability of every line. Thus, TeX accepts a place as a breakpoint although the width of the collected material and the stretchability in the material cannot fill the line with a badness less or equal to the current tolerance. But the width plus the stretchability plus the dimension \emergencystretch is large enough to do that; visually such a line is underfull.

There are several parameters that influence the reporting and the marking. As you said the \hfuzz dimen can omit the overfull rule but it doesn't change the fact: there is an overfull line. Another parameter called \hbadness is responsible if a warning is issued.

Thus, I don't see why the cited text of the TeXbook is wrong as it is a high level informal description.