Bug 155434 – Set an upper limit for the size or number of pieces of stretchy operators

• Status: RESOLVED
• Resolution: FIXED
• Component: MathML

[Frédéric Wang (:fredw)]

mathml/very-large-stretchy-operators.html still has some random timeout. We can probably workaround that by setting an upper limit for the stretch size of operators or for the number of pieces/extenders to draw them.

[Frédéric Wang (:fredw)]

Created attachment 282125 [details]
Patch

[Brent Fulgham]

Comment on attachment 282125 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=282125&action=review

I don't see anything obviously wrong here, but I'm holding off on a final r+ because of a few questions I had.

> Source/WebCore/rendering/mathml/MathOperator.cpp:35
> +static const unsigned kMaximumExtensionCount = 128;

How did you arrive at this count? Do we approach 128 for our existing test cases?

I wonder if we could get away with a much smaller value based on actual MathML use cases.

> Source/WebCore/rendering/mathml/MathOperator.cpp:495
> +    for (unsigned extensionCount = 0; lastPaintedGlyphRect.maxY() < to.y() && extensionCount < kMaximumExtensionCount; extensionCount++) {

I wonder if this would be clearer remaining a while loop:

Unsigned extensionCount = 0;
while (lastPaintedGlyphRect.maxY() < to.y() && extensionCount < kMaximumExtensionCount) {

> Source/WebCore/rendering/mathml/MathOperator.cpp:497
>          glyphOrigin.setY(glyphOrigin.y() + lastPaintedGlyphRect.height());

If we have nearly exhausted our extensionCount, but lastPaintedGlyphRect.maxY() is still < to.y(), do we need to do a final "fix-up" calculation to make sure we achieve the "to.y()" value we are trying to reach?

> Source/WebCore/rendering/mathml/MathOperator.cpp:533
> +    for (unsigned extensionCount = 0; lastPaintedGlyphRect.maxX() < to.x() && extensionCount < kMaximumExtensionCount; extensionCount++) {

Ditto my above comments, but in the 'x' dimension. :-)

[Frédéric Wang (:fredw)]

Comment on attachment 282125 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=282125&action=review

>> Source/WebCore/rendering/mathml/MathOperator.cpp:35
>> +static const unsigned kMaximumExtensionCount = 128;
> 
> How did you arrive at this count? Do we approach 128 for our existing test cases?
> 
> I wonder if we could get away with a much smaller value based on actual MathML use cases.

So for example for a parenthesis the reasoning is that the glyph for the base size (e.g. U+28) as well as for the pieces of the glyph assembly (U+239B, U+239C, U+239D) will more or less have the same size. So a limit of N extenders is essentially setting the maximum ratio of (assembly size)/(base size) to approximately N (times the number of calls to fillWith*ExtensionGlyph). That seems quite reasonable to say that in practice stretched operators never 128 times as large as their base size. I agree that it's probably still a very large upper bound, but that seems enough to avoid time out in very-large-stretchy-operators.html (at least in my local release build and the build bot in EWS).

>> Source/WebCore/rendering/mathml/MathOperator.cpp:495
>> +    for (unsigned extensionCount = 0; lastPaintedGlyphRect.maxY() < to.y() && extensionCount < kMaximumExtensionCount; extensionCount++) {
> 
> I wonder if this would be clearer remaining a while loop:
> 
> Unsigned extensionCount = 0;
> while (lastPaintedGlyphRect.maxY() < to.y() && extensionCount < kMaximumExtensionCount) {

for loops with the extensionCount counter generally looks more readable to me, but I can change that.

>> Source/WebCore/rendering/mathml/MathOperator.cpp:497
>>          glyphOrigin.setY(glyphOrigin.y() + lastPaintedGlyphRect.height());
> 
> If we have nearly exhausted our extensionCount, but lastPaintedGlyphRect.maxY() is still < to.y(), do we need to do a final "fix-up" calculation to make sure we achieve the "to.y()" value we are trying to reach?

I'm not sure what would be the "fix-up". The only non-const parameters is PaintInfo so we don't need to worry about the local variable glyphOrigin or lastPaintedGlyphRect if that's the question. What will happen is that we will have one big gap at the bottom/left part of the extending part. We could fix it by distributing the gap and extenders equally & symmetrically, but I don't think we want to bother with that given these are really edge cases.

[Brent Fulgham]

Comment on attachment 282125 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=282125&action=review

I feel like that we should be able to satisfy our minimal performance requirements while dealing with these stretched operator edge cases, but perhaps that's a separate issue for us to deal with.

r=me.

>>> Source/WebCore/rendering/mathml/MathOperator.cpp:35
>>> +static const unsigned kMaximumExtensionCount = 128;
>> 
>> How did you arrive at this count? Do we approach 128 for our existing test cases?
>> 
>> I wonder if we could get away with a much smaller value based on actual MathML use cases.
> 
> So for example for a parenthesis the reasoning is that the glyph for the base size (e.g. U+28) as well as for the pieces of the glyph assembly (U+239B, U+239C, U+239D) will more or less have the same size. So a limit of N extenders is essentially setting the maximum ratio of (assembly size)/(base size) to approximately N (times the number of calls to fillWith*ExtensionGlyph). That seems quite reasonable to say that in practice stretched operators never 128 times as large as their base size. I agree that it's probably still a very large upper bound, but that seems enough to avoid time out in very-large-stretchy-operators.html (at least in my local release build and the build bot in EWS).

Sounds reasonable.

>>> Source/WebCore/rendering/mathml/MathOperator.cpp:495
>>> +    for (unsigned extensionCount = 0; lastPaintedGlyphRect.maxY() < to.y() && extensionCount < kMaximumExtensionCount; extensionCount++) {
>> 
>> I wonder if this would be clearer remaining a while loop:
>> 
>> Unsigned extensionCount = 0;
>> while (lastPaintedGlyphRect.maxY() < to.y() && extensionCount < kMaximumExtensionCount) {
> 
> for loops with the extensionCount counter generally looks more readable to me, but I can change that.

I think the 'for' construct makes it seem like there is some set number of extensions we plan on creating. The 'while' loops seems (to me) clearer that we only want to do as much as needed to satisfy the criteria.

However, I don't feel strongly about this (it's a personal preference), so go ahead and leave it as-is.

>>> Source/WebCore/rendering/mathml/MathOperator.cpp:497
>>>          glyphOrigin.setY(glyphOrigin.y() + lastPaintedGlyphRect.height());
>> 
>> If we have nearly exhausted our extensionCount, but lastPaintedGlyphRect.maxY() is still < to.y(), do we need to do a final "fix-up" calculation to make sure we achieve the "to.y()" value we are trying to reach?
> 
> I'm not sure what would be the "fix-up". The only non-const parameters is PaintInfo so we don't need to worry about the local variable glyphOrigin or lastPaintedGlyphRect if that's the question. What will happen is that we will have one big gap at the bottom/left part of the extending part. We could fix it by distributing the gap and extenders equally & symmetrically, but I don't think we want to bother with that given these are really edge cases.

Yes -- that's what I meant by "fix-up". I wasn't sure if our "timeout" case was due to ever-decreasing "lastPaintedGlyphRect.height()" values, so that we approach (as a limit) the desired "to.y()" but never quite achieve it.

It's seems surprising to me that we end up with a large gap at the end of the drawing operation if we are drawing "standard" glyph sizes, unless the stretch operation is covering many many pages of height and we are using relatively small glyphs.

I agree that these are pathological cases, and maybe we just want to make sure we don't do something crazy (like spin the CPU endlessly trying to satisfy bad layout), but it seems like anything that it should be possible to drawn any "finite" math document without timing out.

[Frédéric Wang (:fredw)]

OK, I'm going to land it as it. BTW, I forgot to reply about our test LayoutTests/mathml/very-large-stretchy-operators.html. Basically, it involves several operators of increasing sizes 2500px, 5000px, 20000px, 40000px, 80000px, 160000px, ... 5120000px, 10240000px so that will definitely reach the upper limit.

[Brent Fulgham]

(In reply to comment #5)
> OK, I'm going to land it as it. BTW, I forgot to reply about our test
> LayoutTests/mathml/very-large-stretchy-operators.html. Basically, it
> involves several operators of increasing sizes 2500px, 5000px, 20000px,
> 40000px, 80000px, 160000px, ... 5120000px, 10240000px so that will
> definitely reach the upper limit.

Sounds good.

Should we file a Bugzilla to track the concept of evenly distributing the gaps and extends across large stretch operations? We might not ever do it, but at least we would have a reminder that we should think about it.

[Frédéric Wang (:fredw)]

Committed r202489: <http://trac.webkit.org/changeset/202489>