wikimedia / parsoid / 1011 / 1
85%
master: 85%

DEFAULT BRANCH: master
Ran
Files 79
Run time 4s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 83.769% (+0.001%) from 83.768%
1011.1

push

travis-ci

subbuss 
Template wrapping: Eliminate pathological tpl-range nesting scenario

wikidata.org/wiki/Wikidata:Database_reports/items_without_claims_categories/enwiki
and other such pages on wikidata have been timing out regularly
for several months now.

It turns out that this was exercising a pathological scenario in
template wrapping.

That page has ~4000 transclusions of the form: {{TR noclaims site|...}}

This transclusion generates a <tr>...</tr> which then causes the start
and end-template marker meta tags to lie outside the <tr> which seems
to be causing template ranges to expand to the entire table (that
behavior will be investigated separately to see if we can make it stick
to the <tr> instead).

So, we effectively have ~4K transclusions whose template wrapping
range is identical (the entire table).

Given a set of ranges, the findToplevelNonOverlappingRanges algorithm
tries to find how ranges nest within one another.

Given ranges A & B that overlap perfectly, we could mark A nested in B
or vice versa.  Normally, this shouldn't be an issue since no matter
which one we pick as the "outermost" range, the whole table will get wrapped.

However, the algorithm also has code to prevent nesting cycles.
This cycle detection code encounters pathological behavior on this page.
We have ranges R_1 .. R_4000 where R_n is being marked as nested in R_n+1.
So, you now have this nesting tree that ends up as a long chain from
R_1 ... R_n for all values of n. The cycle-detection code uses this
nesting tree to prevent cyclical nesting and this ends up walking these
n-long paths for every value of n and thus has O(n^2) behavior.

A better nesting tree would be to mark R_2 .. R_4000 as being nested
in R_1. So, given ranges A & B that overlap perfectly, this patch
adds a new test to ensure that B is marked nested in A whenever
B's starting offset is larger than A's offset.

With this fix, the tpl-wrapping code finishes rapidly and the page
parses without a timeout.

Bug: T119883

Change-Id: Iaaa2fc2cf

12970 of 15483 relevant lines covered (83.77%)

21297.22 hits per line

Source Files on job 1011.1