RECURSION(MDOC) MDOC RECURSION(MDOC)

NAME

details/recursionrecursion and iteration in the roff language

DESCRIPTION

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.

Recursive macro expansion

Call a macro that calls itself.
Minimal example:
.de rec 
.rec 
.. 
.rec
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.

Recursive string expansion

Interpolate a string that interpolates itself.
Minimal example:
.ds s \\*s 
\*s
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.

Recursive macro content addition

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

Recursive macro redefinition

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.

Recursive file inclusion

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.

Iteration

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.
January 7, 2014 bsd.lv