details/recursion —
recursion and iteration in the roff language
The
roff(7)
language is a Turing complete programming language. It provides many different
ways to construct loops. All these ways can be used to construct finite and
infinite loops.
Obviously, a well-written manual page will not use macro definitions, recursion,
or iteration. All the same, a deeper understanding of how these work may be
required to debug existing documents or the
mandoc(1)
source code.
In the following, all statements about groff and mandoc refer to groff-1.22.3
and mandoc-1.13.2.
Call a macro that calls itself.
Minimal example:
The minimal example implements infinite recursion. To implement finite
recursion, the recursive call needs to be placed into the body of a
conditional roff request.
Minimal finite example:
.de rec
.nr i \\$1-1
.if \\ni .rec \\ni
\\$1
..
.rec 8
To avoid waste of time and memory and to prevent the interpreter from dying from
memory exhaustion, both groff and mandoc limit the number of macro invocations
that can result from any single input line. In that case, groff aborts
processing of the document. Mandoc only discards the offending input line and
continues processing the document with the next input line.
In groff, the error message is:
file:line:
fatal error: input stack limit exceeded (probable infinite loop)
In mandoc, the error message is:
mandoc:
file:line:column:
ERROR: input stack limit exceeded, infinite loop?
In the mandoc interpreter, the recursive call is in file
read.c, function
mparse_buf_r(), guarded by the constant
REPARSE_LIMIT.
Interpolate a string that interpolates itself.
Minimal example:
The minimal example implements infinite recursion. Groff supports finite
recursion by using conditional requests in the string definition:
.de s
\\ni\\c
.nr i \\ni-1
.if \\ni \\*s\\c
..
.nr i 8
x\*sx
Since mandoc fully expands strings before interpreting roff requests, it doesn't
support finite recursion in string expansion. An attempt to process a document
using finite recursion in string expansion with mandoc results in the omission
of the affected input lines, and in error messages about infinite loops.
To avoid waste of time and memory and to prevent the interpreter from dying from
memory exhaustion, both groff and mandoc limit the number of string expansions
that can happen in any single input line. In that case, groff aborts
processing of the document. Mandoc only discards the offending input line and
continues processing the document with the next input line.
The error messages are the same as for recursive macro expansion.
In the mandoc roff parser, string expansion is implemented in the file
roff.c, function
roff_res(). It works iteratively rather
than recursively and is protected by the constant
EXPAND_LIMIT.
Call a macro that appends to its own definition before calling itself.
Minimal example:
.de rec
.am rec end
\\ni
.end
.nr i \\ni+1
.rec
..
.rec
The minimal example implements infinite recursion. To understand what it does,
look at the end of the output produced by mandoc. Note that in spite of the
REPARSE_LIMIT, the output is quite massive
(almost two Megabyte).
The minimal example can easily be modified to implement finite recursion:
.de rec
.am rec end
\\ni
.end
.nr i \\ni+1
.if \\ni<8 .rec
..
.rec
If a macro completely redefines itself by containing a
de request and by closing out that
de request itself, the resulting macro is
either no longer self-modifying, or it becomes not self-modifying after a
finite number of invocations. Consequently, the only way to define a macro
that redefines itself and remains self-modifying for an arbitrary number of
invocations is to include a
de request in
the original macro definition without closing out that request in the original
macro definition, such that the scope redefining the macro remains open after
its first invocation returns. The minimal example of a recursive macro
redefining itself in this way is:
.de rec \" Define recursive self-expanding setup macro.
.rec \" Recurse.
.de rec \" Redefine itself, scope remains open.
.. \" End of initial definition.
.rec \" Transform into a non-recursive self-consuming macro.
.. \" Close the first of the scopes opened above.
.nf \" Disable filling.
.cc $ \" Disable macro processing.
\*[rec] \" Show the resulting self-consuming macro.
$cc \" Re-enable macro processing.
For each subsequent invocation, the resulting self-consuming macro shortens
itself by one scope, eventually dwindling to the empty macro.
Adding a payload, a termination condition, and a main program repeatedly calling
the self-consuming macro results in a minimal recursive macro that redefines
itself and actually produces some output. Due to its size, it is provided in a
separate file.
Include a roff source file that includes itself.
As a minimal example, put the following into the file
man1/so_inf.1:
.nr i \ni+1
\ni
.so man1/so_inf.1
The minimal example implements infinite recursion. It can easily be modified to
implement finite recursion:
.nr i \ni+1
\ni
.if \ni<8 .so man1/so_fin.1
Groff doesn't explicitly prevent infinite recursion, but dies with the following
error message:
file:line:
can't open ‘file’: Too many
open files
Too avoid waste of resources, mandoc uses a much lower recursion limit, prints
the error message cited below
Recursive macro
expansion when it is violated, discards the offending input line, and
continues processing with the next input line.
In the mandoc roff interpreter, file inclusion is implemented in the file
read.c, function
mparse_buf_r() which recursively calls
mparse_readfd(). The recursion limit is
implemented in
mparse_parse_buffer(), which
is called from
mparse_readfd(), by skipping
the call to
mparse_buf_r() when recursion
is excessive.
The
roff(7)
while request provides explicit iteration.
It is not implemented in mandoc.
Minimal finite example:
.while \ni<9 \{\ni
.nr i \ni+1\}
By using a loop condition that is always true, infinite iteration can be
requested:
.while 1 \{\ni
.nr i \ni+1\}
In this case, groff produces infinite output.