Bug 57916 – Cull out most of the line boxes from the line box tree

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Dave Hyatt]

This bug is about implementing an optimization to avoid creating line boxes at all for most RenderInlines.  Basically barring use of more advanced features, the line box tree will end up consisting only of a root line box and "leaf" children like images and text.

[Dave Hyatt]

Created attachment 88365 [details]
Patch

[WebKit Review Bot]

Attachment 88365 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style']" exit_code: 1

Source/WebCore/rendering/RenderInline.cpp:167:  Should only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Source/WebCore/platform/graphics/FloatRect.cpp:110:  l is incorrectly named. Don't use the single letter 'l' as an identifier name.  [readability/naming] [4]
Source/WebCore/platform/graphics/IntRect.cpp:109:  l is incorrectly named. Don't use the single letter 'l' as an identifier name.  [readability/naming] [4]
Total errors found: 3 in 25 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Dave Hyatt]

Created attachment 88367 [details]
Patch that passes style queue.

Comment on attachment 88367 [details]
Patch that passes style queue.

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

The change log alone warrants an r+, but I can’t r+ yet for two reasons: (1) I need an answer to my question in RenderInline::dirtyLineBoxes() and (2) I’ve reviewed everything except the four brand new functions in RenderInline.

> Source/WebCore/ChangeLog:43
> +        getting the side individually and wastefully doing 4 isHorizontal queries.

Typo: side

> Source/WebCore/rendering/InlineBox.h:266
> -    FloatRect logicalFrameRect() const { return isHorizontal() ? IntRect(m_x, m_y, m_logicalWidth, logicalHeight()) : IntRect(m_y, m_x, logicalHeight(), m_logicalWidth); }
> +    FloatRect logicalFrameRect() const { return isHorizontal() ? IntRect(m_x, m_y, m_logicalWidth, logicalHeight()) : IntRect(m_y, m_x, m_logicalWidth, logicalHeight()); }

Your change log says this is a new function, but it isn’t, it’s just changed and you started using it.

> Source/WebCore/rendering/InlineFlowBox.cpp:796
>      logicalVisualOverflow = IntRect(logicalLeftVisualOverflow, logicalTopVisualOverflow,
>                                      logicalRightVisualOverflow - logicalLeftVisualOverflow, logicalBottomVisualOverflow - logicalTopVisualOverflow);

Not new code, but it would be nicer to write this as logicalVisualOverflow.unite( rect computed above ) and avoid all the max/min computations.

> Source/WebCore/rendering/InlineTextBox.cpp:51
> +typedef WTF::HashMap<const InlineTextBox*, IntRect> InlineTextBoxMap;

Should this say “Overflow” in the name?

> Source/WebCore/rendering/InlineTextBox.cpp:52
> +static InlineTextBoxMap* gTextBoxesWithOverflow = 0;

No need to initialize statics to 0.

> Source/WebCore/rendering/InlineTextBox.cpp:73
> +    gTextBoxesWithOverflow->add(this, rect);

Since you’re doing add(), you may want to assert that the key isn’t already in the table.

> Source/WebCore/rendering/InlineTextBox.cpp:80
> +    if (parent()->renderer() == renderer()->parent())

:->

> Source/WebCore/rendering/RenderInline.cpp:183
> +    bool alwaysCreateLineBoxes = (parentRenderInline && parentRenderInline->alwaysCreateLineBoxes())
> +                                 || (parentRenderInline && parentStyle->verticalAlign() != BASELINE)
> +                                 || style()->verticalAlign() != BASELINE
> +                                 || style()->textEmphasisMark() != TextEmphasisMarkNone
> +                                 || (checkFonts && (parentStyle->font().fontMetrics().ascent() != style()->font().fontMetrics().ascent()
> +                                 || parentStyle->font().fontMetrics().descent() != style()->font().fontMetrics().descent()
> +                                 || parentStyle->font().fontMetrics().lineGap() != style()->font().fontMetrics().lineGap()
> +                                 || parentStyle->lineHeight() != style()->lineHeight()));
> +

This indentation is making Darin sad! Just use normal 4-space indentation. Maybe we need a helper function in FontMetrics that compares ascent, descent and lineGap.

> Source/WebCore/rendering/RenderInline.cpp:493
> +void RenderInline::culledInlineAbsoluteRects(const RenderInline* container, Vector<IntRect>& rects, int tx, int ty)

I really wish we didn’t add more functions with “int tx, int ty” and used IntSize instead

> Source/WebCore/rendering/RenderInline.cpp:530
> +                                           ty + logicalTop,
> +                                           childLine->logicalWidth() + childLine->marginLogicalLeft() + childLine->marginLogicalRight(),
> +                                           logicalHeight);

Poor Darin

> Source/WebCore/rendering/RenderInline.cpp:639
> +    InlineBox* firstBox = firstLineBoxIncludingCulling();
> +    if (firstBox)

You can just write
if (InlineBox* firstBox = firstLineBoxIncludingCulling())

> Source/WebCore/rendering/RenderInline.cpp:648
> +    InlineBox* firstBox = firstLineBoxIncludingCulling();
> +    if (firstBox)

Ditto.

> Source/WebCore/rendering/RenderInline.cpp:956
> -    float logicalLeft = firstLineBox()->logicalLeftVisualOverflow();
>      float logicalTop = firstLineBox()->logicalTopVisualOverflow(firstRootBox->lineTop());
>      float logicalWidth = logicalRightSide - logicalLeftSide;
>      float logicalHeight = lastLineBox()->logicalBottomVisualOverflow(lastRootBox->lineBottom()) - logicalTop;
>      
> -    IntRect rect = enclosingIntRect(FloatRect(logicalLeft, logicalTop, logicalWidth, logicalHeight));
> +    IntRect rect = enclosingIntRect(FloatRect(logicalLeftSide, logicalTop, logicalWidth, logicalHeight));

This should be a separate patch.

> Source/WebCore/rendering/RenderInline.cpp:1251
> +                    // If the child doesn't need line boxes either, then we can recur.

I am confused by this. How do we know that the child doesn’t need line boxes?

> Source/WebCore/rendering/RenderInline.cpp:1355
> +    else if (InlineFlowBox* curr = firstLineBox()) {
> +        for (; curr; curr = curr->nextLineBox())
> +            rects.append(enclosingIntRect(FloatRect(tx + curr->x(), ty + curr->y(), curr->width(), curr->height())));
>      }

Can’t this just be written as
else {
    for (InlineFlowBox* curr = firstLineBox(); curr; curr = curr->nextLineBox())
…
?

> Source/WebCore/rendering/RenderInline.h:26
> +#include "InlineFlowBox.h"

Why is this needed?

> Source/WebCore/rendering/RenderText.cpp:182
>      if (!documentBeingDestroyed()) {

Should the documentBeingDestroyed() check be here or in destroy()?

> Source/WebCore/rendering/RenderText.cpp:1315
> +    float logicalLeftSide = numeric_limits<int>::max();
> +    float logicalRightSide = numeric_limits<int>::min();

Why are these floats? I don’t see how they could ever be assigned a float value. If they need to be floats, then they need to be initialized to the float—not int—limits.

> Source/WebCore/rendering/RenderText.cpp:1323
> +    float logicalTop = firstTextBox()->logicalTopVisualOverflow();
> +    float logicalWidth = logicalRightSide - logicalLeftSide;
> +    float logicalHeight = lastTextBox()->logicalBottomVisualOverflow() - logicalTop;

Really not clear on the use of floats here.

[Dave Hyatt]

Comment on attachment 88367 [details]
Patch that passes style queue.

Marking minus while I address Dan's comments.

[Dave Hyatt]

(In reply to comment #4)
> 
> > Source/WebCore/rendering/InlineTextBox.cpp:52
> > +static InlineTextBoxMap* gTextBoxesWithOverflow = 0;
> 
> No need to initialize statics to 0.
> 

Yeah, knew this. I cut and pasted the HashMap typedef and declaration from an example in RenderBlock for speed, so I guess we should fix the = 0 over there. :)

> 
> > Source/WebCore/rendering/RenderInline.cpp:183
> > +    bool alwaysCreateLineBoxes = (parentRenderInline && parentRenderInline->alwaysCreateLineBoxes())
> > +                                 || (parentRenderInline && parentStyle->verticalAlign() != BASELINE)
> > +                                 || style()->verticalAlign() != BASELINE
> > +                                 || style()->textEmphasisMark() != TextEmphasisMarkNone
> > +                                 || (checkFonts && (parentStyle->font().fontMetrics().ascent() != style()->font().fontMetrics().ascent()
> > +                                 || parentStyle->font().fontMetrics().descent() != style()->font().fontMetrics().descent()
> > +                                 || parentStyle->font().fontMetrics().lineGap() != style()->font().fontMetrics().lineGap()
> > +                                 || parentStyle->lineHeight() != style()->lineHeight()));
> > +
> 
> This indentation is making Darin sad! Just use normal 4-space indentation. Maybe we need a helper function in FontMetrics that compares ascent, descent and lineGap.
> 

Ok will fix the indentation.

> > Source/WebCore/rendering/RenderInline.cpp:1251
> > +                    // If the child doesn't need line boxes either, then we can recur.
> 
> I am confused by this. How do we know that the child doesn’t need line boxes?
> 

That comment is a cut and paste error.  I cut and pasted the loop and casts from culledInlineBoundingBox.  It doesn't apply.  I removed it.

>
> > Source/WebCore/rendering/RenderInline.h:26
> > +#include "InlineFlowBox.h"
> 
> Why is this needed?
> 

To inline firstLineBoxIncludingCulling() and lastLineBoxIncludingCulling().

> > Source/WebCore/rendering/RenderText.cpp:182
> >      if (!documentBeingDestroyed()) {
> 
> Should the documentBeingDestroyed() check be here or in destroy()?
> 

I think it's fine where it is in case someone else calls the helper in the future.

> > Source/WebCore/rendering/RenderText.cpp:1315
> > +    float logicalLeftSide = numeric_limits<int>::max();
> > +    float logicalRightSide = numeric_limits<int>::min();
> 
> Why are these floats? I don’t see how they could ever be assigned a float value. If they need to be floats, then they need to be initialized to the float—not int—limits.
> 
> > Source/WebCore/rendering/RenderText.cpp:1323
> > +    float logicalTop = firstTextBox()->logicalTopVisualOverflow();
> > +    float logicalWidth = logicalRightSide - logicalLeftSide;
> > +    float logicalHeight = lastTextBox()->logicalBottomVisualOverflow() - logicalTop;
> 
> Really not clear on the use of floats here.

None of this code should be using floats.  I cut and pasted from RenderInline::linesVisualOverflowBoundingBox and just didn't complete the conversion.  (This overflow issue was the last thing I added to the patch to fix the repaint tests.)  Will fix.

Will address all the other comments as well.

[Dave Hyatt]

Created attachment 88456 [details]
Patch

Comment on attachment 88456 [details]
Patch

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

One comment below (repeated).

> Source/WebCore/rendering/RenderInline.cpp:853
> +        } else if (curr->isRenderInline()) {
> +            // If the child doesn't need line boxes either, then we can recur.
> +            RenderInline* currInline = toRenderInline(curr);
> +            InlineBox* result = currInline->firstLineBoxIncludingCulling();
> +            if (result)
> +                return result;

The comment is mysterious because the logic is now encompasses in firstLineBoxIncludingCulling(). This whole block can be replaced with
} else if (curr->isRenderInline())
    return toRenderInline(cure)->firstLineBoxIncludingCulling();

> Source/WebCore/rendering/RenderInline.cpp:880
> +        } else if (curr->isRenderInline()) {
> +            // If the child doesn't need line boxes either, then we can recur.
> +            RenderInline* currInline = toRenderInline(curr);
> +            InlineBox* result = currInline->lastLineBoxIncludingCulling();
> +            if (result)
> +                return result;

Ditto.

[Dave Hyatt]

Fixed in r83075.

[WebKit Review Bot]

http://trac.webkit.org/changeset/83075 might have broken Qt Linux Release

[Eric Seidel (no email)]

Comment on attachment 88456 [details]
Patch

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

> Source/WebCore/rendering/HitTestResult.cpp:579
> +    if (node->renderer()->isInline()) {

I would have reversed this so as to use early return.

> Source/WebCore/rendering/RenderInline.cpp:490
> +void RenderInline::culledInlineAbsoluteRects(const RenderInline* container, Vector<IntRect>& rects, const IntSize& offset)

This function is huge. :(  And contributes to the general unreadability of the line layout code :(

> Source/WebCore/rendering/RenderInline.cpp:569
> +void RenderInline::culledInlineAbsoluteQuads(const RenderInline* container, Vector<FloatQuad>& quads)

There must have been a way to share more code between this and the absolute rects one.  Geez.  Sooooo much duplicated code. :(