How does (or, what happens when) Tex typeset(s) a line and linebreak?

Question

I could not find references to this with a cursory search, so I thought I'd post a question; I'm aware this is probably discussed at length in the Tex book or similar, but unfortunately I don't have the time to delve into those details now.

Basically, I'm trying to understand the code in the answer putting a box around each line of text in a paragraph, in particular this macro:

\def\hmmx{%
  \@tempcnta\z@
  \loop
     \advance\@tempcnta\@ne
     \setbox\z@\lastbox
     \global\dimen@i\ht\z@
     \skip@\lastskip\unskip
     \count@\lastpenalty\unpenalty
     \ifdim 5sp=\wd\z@
     \else
       \global\setbox\@ne\vbox{%
         \penalty\count@
         \vskip\skip@
         \ifodd\@tempcnta
           \hbox{\reflectbox{\box\z@}}%
         \else
           \box\z@
         \fi
         \unvbox\@ne
         }%
     \repeat
  }%

I can see that it loops, and then it basically sets up the initial boxes for a line, which makes sense - but I don't understand, where are the characters read from the source file afterwards? E.g., if there was something like:

\ifodd\@tempcnta
\hbox{\reflectbox{\box\z@}}\PROCEEDwithRESTofLINE%
\else
\box\z@\PROCEEDwithRESTofLINE
\fi

... it would have made more sense to me - but obviously, there is no \PROCEEDwithRESTofLINE there. I would have assumed that something like a \PROCEEDwithRESTofLINE would read next character from input (source file), and decide if it belongs on the line: if it belongs, then a glyph is written to the PDF output; if not, then a line break would be output (except there are no "line breaks" in PDF literals, if I remember correctly - just positioning text glyphs at X/Y); and that would be the signal to "return" to the \hmmx function, so that \repeat could execute again. But again - this is just my speculation; I have no idea how this actually works.

So, could someone provide a breakdown what happens in terms of line processing in (La)Tex: considering tex input character by character (or token by token), when does the engine output glyphs to PDF; how does the engine know when to break the line; and how is that (line break or a new line) signaled to the \loop/\repeat above - so that code can intervene only on "opening" boxes, so to speak? We might as well speak about the simplest example, something like:

\documentclass{article}
\begin{document}
Just a long, or somewhat long line here; long enough to cause a line break within a paragraph in Latex ...
\end{document}

I'm aware this may not be the simplest thing to answer - so just some direct links to docs where this would be explained, would be much appreciated...

Answer 1

Describing the algorithm used by TeX for breaking a paragraph into lines would require a book chapter. You can find the details in the TeXbook or in TeX by Topic.

Let me give a short description for the normal situation, without mentioning hanging indentation or \parshape. To begin with, a paragraph is read in its entirety into memory. Any “horizontal command” causes the paragraph to start; normally an empty box of width \parindent is inserted before the action of the horizontal command, unless the horizontal command is \noindent. A \par command, explicit or generated by an empty line, starts the process of breaking the paragraph into lines.

The first operation is discarding possible glue at the end of the paragraph, adding \penalty10000, the \parfillskip glue and \penalty-'10000000000 that forces the final break.

Next TeX examines the paragraph trying to break lines without using hyphenation. Every feasible break point is tried and only the ones that wouldn't cause lines to exceed the current \pretolerance are taken into account. If a set of line breaks is found, TeX chooses the sequence that produces the least amount of demerits. These are assessed by looking at lines next to each other, high demerits correspond to successive visually incompatible lines: for instance, a loose line next to a tight one; looseness or tightness are referred to the amount of stretching or shrinking of interword spacing.

In case the \pretolerance cannot be respected, TeX tries hyphenation and this time it chooses only the feasible break points that make lines not to exceed the current \tolerance. In this phase, demerits are also assessed for consecutive hyphenated lines or for a hyphen in the last but one line.

If the tolerance cannot be respected, TeX tries another similar pass, by adding the current amount of \emergencystretch to the stretchability of the glue in the paragraph, in order to scale badness down. If even this pass doesn't succeed, TeX will typeset the paragraph with an overfull or underfull line.

In any case, a sequence of break points has been chosen. TeX now passes the material to the next stage, where each line is packed into an \hbox of width \hsize, by stretching or shrinking the available glue.

These boxes are stacked and between them a penalty item can be inserted (for instance, after the first line \clubpenalty is inserted, before the last one \widowpenalty is used); these penalties will influence page breaking. After this penalty (that can be missing), the interline glue is computed and inserted.

Finally, TeX contributes the sequence of boxes, penalties and glue to the current vertical list and exercises the page builder (basically, it tries to see if a page has been completed).

If all this happens in internal vertical mode (basically inside a \vbox), this list is still available until a new box is contributed. So if one does

\setbox0=\lastbox

the last line of the paragraph will be removed from the vertical list and stored in box register 0. Then one can do

\skip0=\lastskip\unskip

that will store the interline glue above the last line in skip register 0 and remove it. Similarly, one can store in a count register the possible penalty with \lastpenalty and remove it with \unpenalty. This process can continue until all the contributed boxes, glues and penalties are removed. Such items can be used in various ways; in the case under scrutiny, these items are used for rebuilding the same paragraph, but by alternately reflecting the boxes horizontally. Note that the process goes backwards from the last to the first line.

After a paragraph has been completed, the number of lines is available in the internal register \prevgraf. This might be used for ensuring the even lines are reflected, by setting \@tempcnta=\prevgraf and doing \advance\@tempcnta by -1 instead of \advance\@tempcnta by 1. This could also avoid the trick of using a special box with a “strange” thickness for ending the recursion.

Answer 2

This code works backwards up the paragraph. First the entire paragraph is broken into lines and placed into a box (which is assumed to contain alternating items of an hbox with a line of text and a glue item of baselineskip glue.

Then from the end of the list the box is removed (with \lastbox) and either put into a new box being constructed or flipped first, depending on the parity, any penalties and skips are similarly removed and copied with \unpenalty and \unskip, then once the whole new box is constructed in box 1 the next bit of code in the origial answer unboxes it on to the main vertical list so it takes part in page breaking.

Answer 3

Just a note: the best I could find to explore this, is to go through the trouble of installing Latex3, and then use the unravel package on the file in OP, like this:

\documentclass{article}
\tracingonline=1
\tracingoutput=1
\tracingpages=1
\tracingparagraphs=1
\usepackage{unravel}
\begin{document}
\showoutput
\unravel{
Just a long, or somewhat long line here; long enough to cause a line break within a paragraph in Latex ...
\end{document}
}\relax

... and then run pdflatex test.tex, and step in the terminal typing Enter.

I'll try eventually to write a better answer; but basically, there is character scanning first; only during \end{document} is a \par added, and only thereafter, apparently, is the line first calculated for breaking:

|| 
|>  Just a long, or somewhat long line here; long enough to cause a line
|> break within a paragraph in Latex ... \end {document} 

[===== Step 1 =====]  = blank space  
|| 
|> Just a long, or somewhat long line here; long enough to cause a line
|> break within a paragraph in Latex ... \end {document} 

[===== Step 2 =====] J= the letter J : \everypar={}
|| 
|> Just a long, or somewhat long line here; long enough to cause a line
|> break within a paragraph in Latex ... \end {document} 
...
[===== Step 109 =====]  = blank space  
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... 
|| 
|> \end {document} 

[===== Step 110 =====] \end = macro:#1->\csname end#1\endcsname \@chec...
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... 
|| 
|> \csname enddocument\endcsname \@checkend {document}\expandafter
|> \endgroup \if@endpe \@doendpe \fi \if@ignore \@ignorefalse \ignorespaces
|> \fi  
...
[===== Step 133 =====] \if@nobreak =false
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... 
|| 
|> \par \vfil \penalty -\@M \write \m@ne {}\vbox {}\penalty -\@Mi
|> \begingroup \if@filesw \immediate \closeout \@mainaux \let \@setckpt
|> \@gobbletwo \let \@newl@bel \@testdef \@tempswafalse \makeatletter \@@input
|> \jobname .aux \fi \@dofilelist \ifdim \font@submax >\fontsubfuzz \relax
|> \@font... (465 chars)

@firstpass
[]\OT1/cmr/m/n/10 Just a long, or somewhat long line here; long enough to cause
 a line break 
@ via @@0 b=1 p=0 d=121
@@1: line 1.2 t=121 -> @@0
within a paragraph in Latex ... 
@\par via @@1 b=0 p=-10000 d=100
@@2: line 2.2- t=221 -> @@1

%% goal height=550.0, max depth=5.0
% t=0.0 g=550.0 b=10000 p=0 c=100000#
% t=10.0 g=550.0 b=10000 p=300 c=100000#
[===== Step 134 =====] Paragraph end.
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par 
|| 
|> \vfil \penalty -\@M \write \m@ne {}\vbox {}\penalty -\@Mi \begingroup
|> \if@filesw \immediate \closeout \@mainaux \let \@setckpt \@gobbletwo \let
|> \@newl@bel \@testdef \@tempswafalse \makeatletter \@@input \jobname .aux
|> \fi \@dofilelist \ifdim \font@submax >\fontsubfuzz \relax \@font@warn...
|> (460 chars)
...
[===== Step 137 =====] -
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par 
|| \penalty -
|> \@M \write \m@ne {}\vbox {}\penalty -\@Mi \begingroup \if@filesw
|> \immediate \closeout \@mainaux \let \@setckpt \@gobbletwo \let \@newl@bel
|> \@testdef \@tempswafalse \makeatletter \@@input \jobname .aux \fi
|> \@dofilelist \ifdim \font@submax >\fontsubfuzz \relax \@font@warning {Size
|> substi... (444 chars)

[===== Step 138 =====] \@M = \mathchar"2710= 10000
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par 
|| \penalty -10000
|> \write \m@ne {}\vbox {}\penalty -\@Mi \begingroup \if@filesw \immediate
|> \closeout \@mainaux \let \@setckpt \@gobbletwo \let \@newl@bel \@testdef
|> \@tempswafalse \makeatletter \@@input \jobname .aux \fi \@dofilelist \ifdim
|> \font@submax >\fontsubfuzz \relax \@font@warning {Size substituti... (440
|> chars)

% t=22.0 g=550.0 b=10000 p=0 c=100000#
% t=23.94444 plus 1.0fil g=550.0 b=0 p=-10000 c=-10000#

Completed box being shipped out [1]
\vbox(633.0+0.0)x407.0
.\glue 16.0
.\vbox(617.0+0.0)x345.0, shifted 62.0
..\vbox(12.0+0.0)x345.0, glue set 12.0fil
...\glue 0.0 plus 1.0fil
[...]
...\hbox(6.94444+1.94444)x345.0, glue set 0.19885
....\hbox(0.0+0.0)x15.0
....\OT1/cmr/m/n/10 J
....\OT1/cmr/m/n/10 u
....\OT1/cmr/m/n/10 s
....\OT1/cmr/m/n/10 t
....\glue 3.33333 plus 1.66666 minus 1.11111
....\OT1/cmr/m/n/10 a
[...]
[===== Step 144 =====] \vbox 
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par 
|| \vbox 
|> {}\penalty -\@Mi \begingroup \if@filesw \immediate \closeout \@mainaux
|> \let \@setckpt \@gobbletwo \let \@newl@bel \@testdef \@tempswafalse
|> \makeatletter \@@input \jobname .aux \fi \@dofilelist \ifdim \font@submax
|> >\fontsubfuzz \relax \@font@warning {Size substitutions with
|> differences\... (419 chars)

[===== Step 145 =====] \vbox {
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {
|| 
|> }\penalty -\@Mi \begingroup \if@filesw \immediate \closeout \@mainaux
|> \let \@setckpt \@gobbletwo \let \@newl@bel \@testdef \@tempswafalse
|> \makeatletter \@@input \jobname .aux \fi \@dofilelist \ifdim \font@submax
|> >\fontsubfuzz \relax \@font@warning {Size substitutions with
|> differences\M... (418 chars)

%% goal height=550.0, max depth=5.0
% t=0.0 g=550.0 b=10000 p=0 c=100000#
...
[===== Step 203 =====] Set \deadcycles(\deadcycles)=0
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {}\begingroup \endgroup 
|| 
|> \@@end \@checkend {document}\expandafter \endgroup \if@endpe \@doendpe
|> \fi \if@ignore \@ignorefalse \ignorespaces \fi  

[===== Step 204 =====] End everything!
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {}\begingroup \endgroup 
|| 
|> \tex_hbox:D to\tex_hsize:D {}\tex_vfill:D \tex_penalty:D -'10000000000
|> \@@end \@checkend {document}\expandafter \endgroup \if@endpe \@doendpe \fi
|> \if@ignore \@ignorefalse \ignorespaces \fi  

[===== Step 205 =====] \tex_hbox:D 
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {}\begingroup \endgroup 
|| \tex_hbox:D 
|> to\tex_hsize:D {}\tex_vfill:D \tex_penalty:D -'10000000000 \@@end
|> \@checkend {document}\expandafter \endgroup \if@endpe \@doendpe \fi
|> \if@ignore \@ignorefalse \ignorespaces \fi  
...
[===== Step 208 =====] \tex_hbox:D to345.0pt{
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {}\begingroup \endgroup
<| \tex_hbox:D to345.0pt{
|| 
|> }\tex_vfill:D \tex_penalty:D -'10000000000 \@@end \@checkend
|> {document}\expandafter \endgroup \if@endpe \@doendpe \fi \if@ignore
|> \@ignorefalse \ignorespaces \fi  

%% goal height=550.0, max depth=5.0
% t=0.0 g=550.0 b=10000 p=0 c=100000#
...
[===== Step 224 =====] 0
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {}\begingroup \endgroup
<| \tex_hbox:D to345.0pt{}
|| \tex_penalty:D -'10000000000
|>  \@@end \@checkend {document}\expandafter \endgroup \if@endpe \@doendpe
|> \fi \if@ignore \@ignorefalse \ignorespaces \fi  

% t=10.0 g=550.0 b=10000 p=0 c=100000#
% t=10.0 plus 1.0fill g=550.0 b=0 p=-1073741824 c=-1073741824#
...
[===== Step 246 =====] 0
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {}\begingroup \endgroup
<| \tex_hbox:D to345.0pt{}\tex_hbox:D to345.0pt{}
|| \tex_penalty:D -'10000000000
|>  \@@end \@checkend {document}\expandafter \endgroup \if@endpe \@doendpe
|> \fi \if@ignore \@ignorefalse \ignorespaces \fi  

% t=10.0 g=16383.99998 b=10000 p=0 c=100000#
% t=10.0 plus 1.0fill g=16383.99998 b=0 p=-1073741824 c=-1073741824#
[===== Step 247 =====] \tex_penalty:D -'10000000000
<| Just a long, or somewhat long line here; long enough to cause a line
<| break within a paragraph in Latex ... \par \vbox {}\begingroup \endgroup
<| \tex_hbox:D to345.0pt{}\tex_hbox:D to345.0pt{}
|| 
|> \@@end \@checkend {document}\expandafter \endgroup \if@endpe \@doendpe
|> \fi \if@ignore \@ignorefalse \ignorespaces \fi  

[===== The end! =====]

 )</path/to/texlive/2011/texmf-dist/fonts/type1/public/amsfonts/cm/cmr
10.pfb>
Output written on teest.pdf (1 page, 15383 bytes).