# line breaking mystery in \@dottedtocline

I'm trying to understand why some entries in a table of contents are overfull even if a sensible break points exist. I pulled down the problem (and the definition of \@dottedtocline) to this example:

\documentclass[a4paper,twoside, 12pt]{article}
\usepackage[inner=27mm, outer=27mm]{geometry}
\usepackage[ngerman]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\begin{document}

\makeatletter
\def\@dottedtocline#1#2#3#4#5{%
{\leftskip #2\relax \rightskip \@tocrmarg \parfillskip -\rightskip
\parindent #2\relax
\leavevmode
\@tempdima #3\relax
\advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip
{#4}\nobreak\par}}

\tracingparagraphs=1

\@dottedtocline{2}{1.5em}{2.3em}{%
\numberline {0.2}Marktabgrenzung für Sekundärrohstoffe aus der Eisen- und Stahlerzeu\-gung}{1}

\@dottedtocline{2}{1.5em}{2.3em}{%
\numberline {0.2}Marktabgrenzung für Sekundärrohstoffe aus der Eisen- und Stahlerzeu\-gu\-ng}{1}

\end{document}


Which give in TL14 this linebreaks:

The only difference between the two lines is the additional breakpoint. Why does it matter? Why doesn't break TeX at the discretionary without it? (Removing the \nobreak is (probably) not a solution as it in a real toc keeps imho the dots attached to the toc entry.)

# Edit

Cut down tex example from Joseph:

\hsize330pt
\parfillskip-2.55em

Marktabgrenzung fur Sekundarrohstoffe aus der Eisen- und Stahlerzeu\-gung
\par
Marktabgrenzung fur Sekundarrohstoffe aus der Eisen- und Stahlerzeu\-gu\-ng\bye


The negative \parfillskip explains why TeX accepts the overfull box in the first line, but not why the same doesn't happen in the second line (where we get an underfull hbox message).

• Quite curious that the first paragraph succeeds at the first pass, whereas the second one does the second pass. – egreg Dec 4 '14 at 17:39
• Example can be cut down as least as far as \hsize355pt\rightskip2.55em\parfillskip-\rightskip Marktabgrenzung fur Sekundarrohstoffe aus der Eisen- und Stahlerzeu\-gung\par Marktabgrenzung fur Sekundarrohstoffe aus der Eisen- und Stahlerzeu\-gu\-ng\bye. – Joseph Wright Dec 4 '14 at 17:51
• there is nothing overfull in the example really :-) – Frank Mittelbach Dec 4 '14 at 20:54

Nice example.

This is actually not really a TeX bug or anything but a design approach (or rather some uptimization to keep computing expense low --- remember when TeX was designed) in the paragraph breaking algorithm.

In a nutshell TeX keeps looking at breakpoints in a paragraph starting at the beginning and working towards the end. In this manner it builds out a graph of possible ways through the paragraph that start at the baragraph beginning then fans out and eventually comes together again at the \par. The algorithm then essentially finds the shortest path through that graph given certain criteria (like badness of lines).

Now you could draw a very huge graph, say one node ending line 1 after "Marktabgrenzung" and line two 2 there after "fur" and one for line 1 ending after "fur" etc. However many of those are completely rubbish, so TeX is not bothering with them at all (badness far too bad, ie empty line). In the opposite direction TeX will stop considering building lines from a certain breakpoint to a later breakpoint if those lines if the distances is getting too large (the breakpoint gets "deactivated" as far as building this graph is concerned).

In other words: if TeX has a break point A and now it finds breakpoint B next and the distance between A and B is kind of right to form a line then this gets added to the graph (and so are other edges if B also can form a line with an earlier breakpoints)

But at some point TeX finds breakpoint G, say, and while A-F was a nice line A-G gets overfull. At that point TeX deactivates "A" so when it comes to break point H it will not even try to form a line back to A but only to B or C ... if those are still active.

So that means, TeX assumes that once a line is overfull there will not something come up that shortens it again such that A-H suddenly would work again. That's quite reasonable for normal text but it doesn't work if you do have something like a huge negative space such as the special \parfillskip in the above example.

This then explains why the extra \-breakpoint matters: without it the paragraph start will still be "active" as the break point after "Stahlerzeu-" can form a line. The next breakpoint then is the \par and that works too because the width of the extra letters are canceled out by the negative \parfillskip. However with the additional hyphen TeX looks back and sees that there is no way to make a line back to the beginning and ergo the beginning of the paragraph gets deactivated so when we reach \par that is no longer a valid option.

well ...

A few more thoughts: one could do better these days by keeping the list of active breakpoints longer around, e.g., only activating them after the line go more overfull than X where X cound be determined by a first fast scan through the whole paragraph to find the largest negative space (remember infinitive shrinkage is frowned upon in §826 so that will be a finite value). That approach wouldn't make the actual graph much bigger as an overfull line would not generate a new feasible node in the graph but it would obviously mean more checks while building it up.

• I understand. Due to the "stopover" on the additional breakpoint tex sees the negative \parfillskip to late. And I now also understand why there are "overfull" lines in the toc at all: I was so baffled by the breaking mystery that I didn't really acknowledged the meaning of the negative \parfillskip. – Ulrike Fischer Dec 5 '14 at 8:36
• And just for the records: with luatex both lines are identical (without linebreak), so it looks as if luatex is doing better. – Ulrike Fischer Dec 5 '14 at 8:57
• @UlrikeFischer without knowing what they do, it is not clear that they do better. Sure case in this example, but it really depends on what goes on behind the scene and at least I haven't seen any documentation of info about changes or improvements to the TeX paragraph handler. – Frank Mittelbach Dec 5 '14 at 12:55