Jump to content

Wikipedia:Avoiding MediaWiki expansion depth limit

From Wikipedia, the free encyclopedia
(Redirected from Wikipedia:UNNEST)

This essay covers issues about the MediaWiki version 1.16 "expansion depth limit" for the nesting of templates and if-logic. All during 2009-2016, the nesting limit has been only a mere 40 levels of nested if-then-else (or nested templates) invoked inside other templates (it was later set to 100 levels in 2021). Some templates end up being counted twice in this list. NOTE THE DANGER: When the depth limit is exceeded, not all templates die, but rather, they simply generate the wrong results (from the remainder of the template) and keep going, as if nothing were wrong. The limits were chosen to thwart denial of service (DoS) attacks being caused by very large or complex templates.

What is not affected: Typically, large templates can be invoked, together, in article text without reaching the limit. The main worry is when using large templates inside an infobox or deeper inside the coding of other templates (when editing a large template). Using large templates together in an article paragraph is rarely a problem.

Reducing expansion depth: The nest-levels can be reduced, inside large templates, by rewriting some of the nested if-else-if-else logic as non-nested if-then-if-then-if-then, or using a #switch outside of the if-then logic. In some cases, avoiding the use of other templates inside a template can also reduce the nesting: whereas using a #ifexpr increases the depth by 1 level, invoking another template containing that #ifexpr increases depth by 2 levels. Putting a default value in a parameter does NOT increase the nesting level: {{{1}}} and {{{1|78.5}}} are both at zero (0) levels of nesting.

Checking the current expansion limit

[edit]

The current limit (as 50 levels of nested templates called directly on this page) can be demonstrated by the following live examples which repeatedly nest the Template:1x to try multiple levels:

 * Nest 50 templates:
  {{1x|{{1x|{{1x|{{1x|{{1x| {{1x|{{1x|{{1x|{{1x|{{1x
 |{{1x|{{1x|{{1x|{{1x|{{1x| {{1x|{{1x|{{1x|{{1x|{{1x
 |{{1x|{{1x|{{1x|{{1x|{{1x| {{1x|{{1x|{{1x|{{1x|{{1x
 |{{1x|{{1x|{{1x|{{1x|{{1x| {{1x|{{1x|{{1x|{{1x|{{1x
 |{{1x|{{1x|{{1x|{{1x|{{1x| {{1x|{{1x|{{1x|{{1x|{{1x
 |'''Level 50 here'''.
 }}}} }}}} }}}} }}}} }}}}
 }}}} }}}} }}}} }}}} }}}}
 }}}} }}}} }}}} }}}} }}}}
 }}}} }}}} }}}} }}}} }}}}
 }}}} }}}} }}}} }}}} }}}}
  • Nest 20 templates:
      Level 50 here.
    
    
    
    
    

By contrast, the following example, with more than 50 nested templates, will cause problems, as with excessively nested templates all during 2009-2016:

  • Nest 51 templates:
      {{Expansion depth limit exceeded|
|Level 51 here.
}}    
    
    
    
    

Reducing the if-else nesting

[edit]

Within a template, the nesting can be reduced by moving each if-expression to be outside another if-expression, or by combining the logic into compound conditions, such as "#ifexpr:|a=b and c=d..." rather than have a #ifexpr nested inside an outer #ifexpr. However, care must be taken to not change the overall effect of the logic, when shifting the nesting of each #ifeq or #ifexpr.

Changes can be tested faster by copying a section of code to be edited (and debugged) separately. It can be easier to copy a section of code to the beginning of a template during edit-preview, or to just edit an empty page, copying a section of code, for checking repeated use, during edit-preview, with different values set as the defaults for parameters.

As an example, a 3-nested stack for 3 #ifexpr can be reduced to a sequence of 3 separate uses of #ifexpr:

Original 3-nested #ifexpr:
{{#ifexpr: {{{1}}}*3 = 12.6| is 12.6
  |<!--else-->{{#ifexpr: {{{1}}}*3 = 27.3| is 27.3
    |<!--else-->{{#ifexpr: {{{1}}}*3 > 57| is over 57}}
  }}
}}
Reduced as 3 separate #ifexpr:
{{#ifexpr: {{{1}}}*3 = 12.6| is 12.6}}{{
  #ifexpr: {{{1}}}*3 = 27.3| is 27.3}}{{
  #ifexpr: {{{1}}}*3 > 57| is over 57}}

Alternatively, a #switch can be used to check a parameter when equal to some specific values:

Using #switch for equal values, plus #ifexpr:
{{#switch: {{#expr: {{{1}}}*3 }}
  | 12.6 = is 12.6 | 27.3 = is 27.3 | #default = <!--continue-->
}}{{#ifexpr: {{{1}}}*3 > 57| is over 57}}

By keeping the nesting of #if, #ifeq, #ifexpr or #switch to just 1-level coding, then the template would have a total nesting depth of just 2 levels. Of course, some cases will require nesting of the #ifexpr coding to handle multiple conditions which trigger extended processing with some nested #ifexpr coding to handle other options.

In general, a total expansion depth of 10 levels should be viewed as acceptable, but the specific restrictions will depend on how often a template might be used in large templates. The amount of re-writing needed, to reduce the nesting levels, will depend on the likelihood that a template will be used in combination with other templates which have large, multi-nested expansions.

In many computer systems, such nesting of if-else logic is allowed to exceed 100 levels, or perhaps unlimited levels, and hence, many people from computer backgrounds might be stunned to realize that the MediaWiki parser had severely limited such nesting to a mere, shallow 40 levels deep, all during 2009–2024.

Reducing a mathematical formula

[edit]

As noted previously, the parser function {{#expr:...}} consumes 1 level of expansion depth, as does {{formatnum:...}}. So, a calculation which removes commas, multiples the amounts, and then re-adds commas will nest 3 levels deep:

  • {{formatnum: {{#expr: 5* {{formatnum:21,001|R}} }} }} → 105,005

Omitting formatnum reduces 1 level: In many cases, it is unavoidable to remove commas from numbers, so formatnum is then used to drop any commas, {{formatnum:21,001|R}}, but in an extreme case, require the input to contain no commas, and reduce the expansion depth by 1 level by omitting {formatnum}.

Combining nested expressions avoids 1 level: In rare cases, a calculation might contain another nested calculation. The refactoring of both calculations into a single {#expr} can reduce the nesting by 1 level:

  • {{#expr: 10 * {{#expr: 2 + 3}} }} → 50
  • {{#expr: 10 * (2 + 3) }} → 50

The use of parentheses "( )" allows a single {#expr} calculation to combine each formula, inside others, as only 1 level of expansion depth.

Templates designed for unnested logic

[edit]

Fortunately, many common templates can be rewritten to unnest the if-else logic or avoid using too many embedded templates. Some examples of highly efficient templates are:

  • {{str_left|str|n}}: extract left-side of a string for 'n' length
  • {{strloc_insert|str1|str2|strloc=n}}: insert string at 'n' or append when strloc <= 0

Those templates were specifically designed to use the minimal nesting of if-else logic and avoid too many embedded templates.

Relatively few understand the problems

[edit]

Because not everyone working in Wikipedia has been trained in the limits of the MediaWiki software, even some of the admins might not be aware how the nested if-else logic has been limiting the use of templates inside of other large templates. Consequently, many people have tried to write templates as if they were writing computer software for modern computer systems, totally unaware of the unusual restriction of 40 levels of nested logic, where other computer software would allow 300, or perhaps unlimited, levels of nesting.

Optimising "recursive" depth

[edit]

As the template language does not allow iteration or recursion, processing that requires repetition needs careful coding. An example is the traversal of the taxonomic hierarchy stored in templates with names of the form "Template:Taxonomy/taxon". Each template has a parameter |parent=parent-taxon. Accessing templates in succession moves up the taxonomic hierarchy, ending at, e.g., Life, which does not have a parent.

The parent of taxon can be found via {{Taxonomy/taxon|machine code=parent}}, thus

{{Taxonomy/Felis|machine code=parent}} → Felinae
{{Taxonomy/Felinae|machine code=parent}} → Felidae
{{Taxonomy/{{Taxonomy/Felis|machine code=parent}}|machine code=parent}} → Felidae

Suppose we wanted to list all ancestral taxa, starting from a given taxon. This could be coded inside a template with an anonymous first parameter as:

{{Taxonomy/{{{1}}}|machine code=parent}},
{{Taxonomy/{{Taxonomy/{{{1}}}|machine code=parent}}|machine code=parent}},
{{Taxonomy/{{Taxonomy/{{Taxonomy/{{{1}}}|machine code=parent}}|machine code=parent}}|machine code=parent}},
...
{{Taxonomy/{{Taxonomy/{{Taxonomy/{{Taxonomy/...|machine code=parent}}|machine code=parent}}|machine code=parent}}|machine code=parent}}

Five levels of this approach applied to Homo yielded Hominini, Homininae, Hominidae, Hominoidea, Catarrhini.

However, we know from the discussion above that inside a template that is itself expanded at most 20 nested template calls are possible, so it would appear that this is the maximum number of levels of the taxonomic hierarchy that can be processed. However, this is not the case. The trick is to process k levels and then call another template, passing the k+1'th level as a parameter. With k=4, the template Proc1 would have the form:

{{Taxonomy/{{{1}}}|machine code=parent}},
{{Taxonomy/{{Taxonomy/{{{1}}}|machine code=parent}}|machine code=parent}},
{{Taxonomy/{{Taxonomy/{{Taxonomy/{{{1}}}|machine code=parent}}|machine code=parent}}|machine code=parent}},
{{Taxonomy/{{Taxonomy/{{Taxonomy/{{Taxonomy/{{{1}}}|machine code=parent}}|machine code=parent}}|machine code=parent}}|machine code=parent}},
{{Proc2|{{Taxonomy/{{Taxonomy/{{Taxonomy/{{Taxonomy/{{Taxonomy/{{{1}}}|machine code=parent}}|machine code=parent}}|machine code=parent}}|machine code=parent}}|machine code=parent}}}}

Then the template Proc2 would be identical other than calling Proc3, and so on. If we have N such templates, from Proc1 to ProcN, with all but the last calling the next in the sequence, then it can be shown by theory and experiment that:

Expansion depth, D = A + N + k (where A represents some fixed overhead)
Maximum level reached, L = N * k

Some elementary calculus shows that for a given L, the optimum is at N = k. Thus to reach 49 levels, N = k = 7, and the expansion depth will be A + 14.

A problem will be that applied to a taxon with fewer than k2-1 levels above it, the code will go over the top of the hierarchy, which is wasteful of processing time, even if it does not generate an error. Unfortunately, it's impossible to completely prevent this happening, because adding #if: expressions to test for the highest level being reached greatly increases the expansion depth and hence greatly reduces the maximum level that can be reached.

A practical example of this approach, used in determining the correct colour to be applied to an automated taxobox, will be found at {{Findall taxa}}. A single test for running over the top of the hierarchy is applied (in {{Findall taxa/5}}).

The Mediawiki restriction on expansion depth results in significant increases in processing time through the necessarily inefficient coding that results.

See also

[edit]

Notes

[edit]