Why is a discardable item not discardable?

Question

I have the following code

\output={\plainoutput \message{outputpenalty=\the\outputpenalty}} % for debugging 

\hrule
\vskip21.9cm plus1pt % plus1pt because to avoid underfull vbox until output
one paragraph
\par
\hrule % \hrule is here only as an "visualizer", you can remove it
\medskip

\end

This code generates (using the command tex test) two pages on the output. The first page includes both \hrules and the second page is empty. The page break is done at \medskip glue. It means that this glue is discarded from the main vertical list. But the \end primitive produces \hbox to\hsize{} \vfill \penalty-1073741824 (see TeXbook page 264) and this produces the second empty page. But the condition (mentioned in TeXbook: "append this material only if the main vertical list hasn't been entirely output") is not true, IMHO. So, I don't understand why an empty page is generated.

We can do these experiments: If we prefix the \medskip glue by \penalty-10000 (alias \break), then the page break is done at this penalty and the next \medskip glue is discarded, so we have only one page. This is OK. But if we prefix the \medskip by \penalty-9999, then the page break is done at this penalty and the next discardable glue is not discarded and a second empty page is generated. Why?

Note, that last sentence is not exactly true. The \medskip glue is discared in the final output (we see only \hbox to\hsize{} in the log when \tracingoutput=1), but it behaves like non-discardable when the \end primitive evaluates its condition from TeXbook, page 264.

Answer 1

I did more exploration about this problem and I hope that I have an answer.

First, a short summary from TeXbook terminology.

The main vertical list is split to two parts by imaginary horizontal line: current page above this line and recent contributions below it. The current page has the c value (cost) calculated at all possible break points but recent contributions waits for such calculation. The page builder is exercised when \par is finished or when box or penalty is added to the main vertical list (there are more cases irrelevant for this example). It is not exercised when only glue is appended to the main vertical list.

The page builder shifts the imaginary line below, i.e. calculates new c values, i.e. moves material from recent contribution to current page. It stops when recent contributions is empty, i.e. the imaginary line is at the bottom of the vertical list. Typically (in the middle of the page) it does nothing more. But when c=infty (overfull page at this point) or penalty<=-10000 (immediately break) then it starts output process. After output process ends it continues its work.

The output process finds the best c value in the current page. All above will be box255 and it is shifted to the output routine and is removed from vertical list. All below is returned to recent contributions because we need to recalculate entirely new c values. It means that when output process ends then page builder recalculates these c values at all possible break points.

Now, we can trace our example above in the OP. We can add \showlists immediately before the \end primitive in order to show the state of vertical list. We can see that all material from page 1 (plus \medskip) is present in the vertical list (in the current page) when \end primitive starts its execution. So, this primitive adds "box glue penalty" as explained in the OP. The page builder was started immediately before \end at \par (empty line in the example) but it does not invoke output process because breaking point at \medskip has not c=infty (not overfull) and a breaking point after \medskip in not presented in the list.

After adding "box glue penalty" by the \end primitive the page builder is exercised and it finds the glue after box as c=infty (overfull) and starts the output process. The best c is at the \medskip and first page is created. The "box glue penalty" (from the \end primitive) occur again in the recent contributions and this causes the second page.

Exactly the same happens when \penalty-9999 is added before \medskip. But another case is with \penalty-10000 added here. The page builder starts output process immediately and \medskip is returned to recent contributions. After page 1 is created, page builder takes \medskip as discardable (because current page is empty) and ignores it. The \end primitive finds the empty vertical list, only page 1 is created.

What happens when a penalty (say \penalty0) is appended after \medskip? The page builder is exercised when the penalty is added, first page is created because c=infty at this penalty. Then \medskip and this penalty are ignored because they are discardable and the \end finds the empty vertical list. This behaviour is typical when \bye macro is used because it appends "vfill penalty" to the vertical list.

What happens when an empty line before the \end (the \par before the \end) is removed? The \end primitive finds the main vertical list as non empty. Moreover, it is divided to non empty current page and non empty recent contributions because page builder was not exercised immediately before the \end. So, it appends "box glue penalty" and second empty page is printed.

Answer 2

The main vertical list is split into two parts: the current page and the recent contributions. At certain times, TeX exercises the page builder, that is, moves the items in the recent contributions to the current page:

1. when a penalty is added to the main vertical list (which could be from \vadjust);

2. after the closing brace of an \insert;

3. a box is added to the main vertical list (in this case also the \prevdepth is updated);

4. when \par is executed (so the boxes the paragraph has been split into invoke the page builder only once);

5. when $$ starts a display, after the \everydisplay tokens have been delivered;

6. when $$ ends a display;

7. after an output routine has ended its job.

When the page builder is exercised, the items in the recent contributions list are moved to the current page and page breaking costs are computed; if the current page has no box in it, a discardable item at the top of the recent contributions list is discarded. The TeXbook, page 112:

Whenever TeX is moving an item from the top of the “recent contributions” to the bottom of the “current page,” it discards a discardable item (glue, kern, or penalty) if the current page does not contain any boxes. This is how glue disappears at a page break.

Note that Knuth doesn't say that “all discardable items following a page break are discarded”: in this respect page breaking is quite different from line breaking.

In your example, the \par makes TeX into exercising the page builder; the computed cost of page breaking is not infinite, so the \medskip glue is appended to the recent contributions and now \end comes along, which adds the equivalent of

\line{} \vfill \penalty-’10000000000

to the main vertical list (in the recent contributions). These items are inserted by \end only if the not everything has been output.

At the penalty TeX exercises the page builder; the glue at the top is not discarded because the current page has boxes in it. However, this glue makes the cost of page break infinite, so what was moved is put back in the recent contributions, starting from the glue up to the end-job penalty, and the page is output.

After the page is shipped out, the page builder is exercised again; the current page is empty, so the \medskip glue is discarded. The \line{} makes TeX insert \topskip glue, then the empty \hbox and the penalty ends the game, because the \end token is still there after the penalty. Another page is output.

---

If a penalty comes along after the \medskip, which is the case when \bye is used, this penalty comes before \end, so TeX exercises the page builder at it, and the glue disappears. No \line{} is added because there's nothing else to output in the main vertical list.

Answer 3

Two excellent answers have already been given, that explain in detail what happens and why: I would just like to add a few remarks, and corroborate the analysis with evidence coming from appropriate tracing commands.

I will use the following diagnostic program:

% !TEX TS-program = pdftex
\showboxbreadth = 1000
\showboxdepth = 10
\output={%
    \tracingcommands = 0
    \immediate\write -1 {Entering output routine,
            \string\outputpenalty\space = \number\outputpenalty.}%
    \showlists % output
    \plainoutput
    \immediate\write -1 {Exiting output routine.}%
}
\tracingpages = 1

\hrule
\vskip 21.9cm plus 1pt \relax % as it was in the question
one paragraph
\par
\hrule % \hrule is here only as a "visualizer", you can remove it
\tracingcommands = 1
\medskip
\showlists % #1
\par % let's make it explicit
\showlists % #2
\end

Note the use of \tracingpages = 1: this will emit a tracing line at the exact moment at which TeX moves an item, which is a legal breakpoint, from the list of “recent contributions” to the “current page” and computes the cost of cutting off the page just above the item it is moving; this tracing line shows how this cost is computed.

I will now go through the transcript file it produces and add my remarks; you are invited to compile the above code, open the transcript file, and follow the forthcoming discussion looking at your copy of it.

This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015) (preloaded format=pdftex 2016.3.5)  20 APR 2016 11:35
entering extended mode
 restricted \write18 enabled.
 file:line:error style messages enabled.
 %&-line parsing enabled.
**wipet.tex
(./wipet.tex
%% goal height=643.20255, max depth=4.0
% t=10.0 g=643.20255 b=10000 p=0 c=100000#

The last line is emitted when TeX is moving from the “contribution list” to the “current page” the glue coming from the “big” \vskip 29.1cm ... command, which is a legal breakpoint: TeX is now reckoning of cutting off the page above this glue, that is, after the \topskip glue and the top rule. This would of course yield a page of infinite badness, so a cost of c=100000# is computed (the # mark at the end tells that this is, notwithstanding all, the best breakpoint appeared thus far).

The following two lines come from our request of tracing down the execution of every primitive command (\tracingcommands = 1):

{vertical mode: \vskip}
{\showlists}

Thus we see that the \medskip command is executed, but, as @egreg and @wipet have already explained, this merely has the effect of appending a glue item to the list of “recent contributions”, without exercising the page builder. The tracing produced by the ensuing \showlists commands (the one marked % #1 in the source code) confirms this:

### vertical mode entered at line 0
### current page:
\glue(\topskip) 9.6
\rule(0.4+0.0)x*
\glue 623.11517 plus 1.0
\glue(\parskip) 0.0 plus 1.0
\hbox(6.94444+1.94444)x469.75499, glue set 386.92151fil
.\hbox(0.0+0.0)x20.0
.\tenrm o
.\tenrm n
.\tenrm e
.\glue 3.33333 plus 1.66666 minus 1.11111
.\tenrm p
.\tenrm a
.\tenrm r
.\tenrm a
.\tenrm g
.\tenrm r
.\tenrm a
.\tenrm p
.\tenrm h
.\penalty 10000
.\glue(\parfillskip) 0.0 plus 1.0fil
.\glue(\rightskip) 0.0
total height 640.05962 plus 2.0
 goal height 643.20255
### recent contributions:
\rule(0.4+0.0)x*
\glue 6.0 plus 2.0 minus 2.0
prevdepth ignored, prevgraf 1 line


./wipet.tex:21: OK.
l.21 \showlists
                % #1
? 

Note that no further line coming from \tracingpages has been emitted yet, but nonetheless the “total height” of the page already includes the “large” \vskip 29.1cm ... and the height, but not the depth, of the line of text. Don’t be confused by this: TeX is still remembering as “best break so far” the break above the large \vskip, because no one of the items that currently follow on the page is a legal breakpoint (the \parskip glue is not, since it is preceded by a discardable item). If a page break occurred now at that point, the ensuing items would be moved back to the “recent contributions” list.

Then the \par command gets executed:

{\par}

This one does exercise the page builder, and indeed it is immediately followed by a line emitted by \tracingpages:

% t=642.40405 plus 2.0 g=643.20255 b=6 p=0 c=6#

TeX has just moved the rule and the glue from the “recent contributions” to the current page (actually, what triggered the above line is the glue, which is a legal breakpoint), and it is now evaluating the cost of cutting off the page above the \medskip. This cost is appealing, but TeX is still waiting to see if anything better is coming along (the badness isn’t infinite yet, neither is the penalty lower than or equal to -10000).

Next comes the second \showlists command (that marked % #2)

{\showlists}

whose output confirms that the \medskip has been incorporated into the “current page”:

### vertical mode entered at line 0
### current page:
\glue(\topskip) 9.6
\rule(0.4+0.0)x*
\glue 623.11517 plus 1.0
\glue(\parskip) 0.0 plus 1.0
\hbox(6.94444+1.94444)x469.75499, glue set 386.92151fil
.\hbox(0.0+0.0)x20.0
.\tenrm o
.\tenrm n
.\tenrm e
.\glue 3.33333 plus 1.66666 minus 1.11111
.\tenrm p
.\tenrm a
.\tenrm r
.\tenrm a
.\tenrm g
.\tenrm r
.\tenrm a
.\tenrm p
.\tenrm h
.\penalty 10000
.\glue(\parfillskip) 0.0 plus 1.0fil
.\glue(\rightskip) 0.0
\rule(0.4+0.0)x*
\glue 6.0 plus 2.0 minus 2.0
total height 648.40405 plus 4.0 minus 2.0
 goal height 643.20255
prevdepth ignored, prevgraf 1 line

./wipet.tex:23: OK.
l.23 \showlists
                % #2
? 

But again, recall that, although the “total height” of the “current page” now includes the “large” \vskip 29.1cm ..., the line of text (both height and depth), the bottom rule, and the \medskip glue, the “best remembered breakpoint” is still above the \medskip (the one of the line that says t=642.40405 plus 2.0 ...): as we’ll see, this will be the chosen breakpoint, and the \glue 6.0 plus 2.0 minus 2.0 will be returned to the “recent contributions”.

Well then, this is the state of affairs when the \end command is digested:

{\end}

Since the main vertical has not been entirely output (cf. The TeXbook, p. 264, first paragraph), this commands inserts the equivalent of

\line{} \vfill \penalty-’10000000000

into the main vertical list—more precisely, into the “recent contributions”; both the box produced by \line{} and the \penalty exercise the page builder, causing the box, the infinite glue and the penalty themselves to be immediately forwarded to the “current page”; the glue is a legal breakpoint, so TeX computes the cost of cutting off the page above it, that is, just after the empty box, and emits the following tracing line (always from \tracingpages):

% t=648.40405 plus 4.0 minus 2.0 g=643.20255 b=* p=0 c=*

This time the badness is infinite, so the output routine is invoked (also note that the line says p=0, from which you can tell that the breakpoint being considered is indeed the glue, not the highly negative penalty; but the page is broken at the best remembered breakpoint, which, let us repeat it once again, is still above the \medskip, at t=642.40405 plus 2.0, with c=6, the last computation marked with the # sign). And actually, what immediately follows is the tracing produced by the commands we included in our custom output routine:

{internal vertical mode: \tracingcommands}
Entering output routine, \outputpenalty = 10000.

(note that \outputpenalty has the expected value for a break “at glue”). Among these commands is the \showlists marked with % output:

### internal vertical mode entered at line 24 (\output routine)
prevdepth ignored
### vertical mode entered at line 0
### recent contributions:
\glue 6.0 plus 2.0 minus 2.0
\hbox(0.0+0.0)x469.75499
\glue 0.0 plus 1.0fill
\penalty -1073741824
prevdepth ignored, prevgraf 1 line

./wipet.tex:24: OK.
<output> ...= \number \outputpenalty .}\showlists 
                                                  \plainoutput \immediate \w...
<to be read again> 
                   \end 
l.24 \end

? 

Again, everything is as we expect: the internal vertical list being constructed by the output routine is, obviously, still empty, and the main vertical list contains the items that follow the chosen breakpoint, starting with the chosen brakpoint itself, which have been returned to the “recent contributions”.

The first page is therefore ejected…

[1{/usr/local/texlive/2015/texmf-var/fonts/map/pdftex/updmap/pdftex.map}]

…then the output routine terminates.

Exiting output routine.

When an output routine ends, the page builder is immediately exercised again. The current page is empty, in particular it does not contain any box, so the \glue 6.0 ... is discarded. Then comes the empty box: since this is the first box contributed to the page, TeX inserts the \topskip glue above it and emits the line

%% goal height=643.20255, max depth=4.0

Note that the \topskip glue is not a legal breakpoint (because it is not preceded by a non-discardable item); indeed, the current page hasn’t got any legal breakpoint yet. The first one is the infinite glue, and when it moves it to the “current page” list, TeX emits the line

% t=10.0 g=643.20255 b=10000 p=0 c=100000#

This corresponds to the cost of breaking the page above the infinite glue. But the chosen breakpoint will be the next one, that TeX consider when it is moving the \penalty-’10000000000 from the “recent contributions” to the “current page”:

% t=10.0 plus 1.0fill g=643.20255 b=0 p=-1073741824 c=-1073741824#

(“above” the penalty, as it were). Here p≤-10000, so the output routine is immediately invoked:

{\tracingcommands}
Entering output routine, \outputpenalty = -1073741824.

(note the value of \outputpenalty). The state of the lists is now as follows:

### internal vertical mode entered at line 24 (\output routine)
prevdepth ignored
### vertical mode entered at line 0
### recent contributions:
\penalty 10000
prevdepth ignored, prevgraf 1 line


./wipet.tex:24: OK.
<output> ...= \number \outputpenalty .}\showlists 
                                                  \plainoutput \immediate \w...
<to be read again> 
                   \end 
l.24 \end

? 

You can see, once again, that the chosen breakpoint has been returned to the “recent contributions”, but with the value of the penalty changed to 10000 (The TeXbook, p. 125). The output routine terminates, ejecting the second page…

[2]
Exiting output routine.

…and another turn on the roundabout begins: the page builder is exercised because an output routine has just ended, and the penalty item is discarded because the current page is empty. After this, the \end commands is executed again (p. 264)…

{vertical mode: \end}

…but this time the main vertical list is empty, so a “happy ending” ensues:

 )</usr/local/texlive/2015/texmf-dist/fonts/type1/public/amsfonts/cm/cmr10.pfb>

Output written on wipet.pdf (2 pages, 12562 bytes).
PDF statistics:
 15 PDF objects out of 1000 (max. 8388607)
 9 compressed objects within 1 object stream
 0 named destinations out of 1000 (max. 500000)
 1 words of extra memory for PDF output out of 10000 (max. 10000000)

(Deep breath.)

---

Maybe someone else will now volunteer to write a similar analysis for the other two scenarios…