Bug 138274 – Simple line layout: Introduce text fragment continuation.

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[zalan]

The next step to abstract out text handling so that a text fragment can manage continuation (can transition from one render element to another)

[zalan]

Created attachment 241267 [details]
WIP patch

Mostly done though -missing test and changelog entry.

[zalan]

Created attachment 241268 [details]
RenderText -> max 8 chars.

Simple line layout continuation is tested with 8 chars long RenderTexts.

[zalan]

WIP patch causes some regression. -fixing it.

[zalan]

Created attachment 241393 [details]
WIP patch

Performance is ok now. LineResolver needs to be extended to support multiple renderers.

[Antti Koivisto]

Comment on attachment 241393 [details]
WIP patch

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

> Source/WebCore/rendering/RenderTreeAsText.cpp:-544
>          if (auto layout = text.simpleLineLayout()) {
> -            ASSERT(!text.firstTextBox());

Why assertion removal?

> Source/WebCore/rendering/SimpleLineLayout.cpp:98
> +    for (RenderObject* curr = flow.firstChild(); curr; curr = curr->nextSibling()) {

could use childrenOfType<RenderObject>

> Source/WebCore/rendering/SimpleLineLayout.cpp:226
>          : m_flow(flow)
>          , m_style(flow.style())
>          , m_lineBreakIterator(downcast<RenderText>(*flow.firstChild()).text(), flow.style().locale())
> +        , m_stringPositionOffset(0)
> +        , m_onlyChild(!flow.firstChild()->nextSibling())
> +        , m_lastRendererIndexOnLine(0)
>      {
> +        RenderText& firstChild = downcast<RenderText>(*flow.firstChild());
> +        m_textRanges.append(std::make_pair(m_lineBreakIterator.string().length(), &firstChild));

FlowContentIterators is getting slightly confusing. Is it an iterator (that can only move forward) or something offering full random access. The interface looks like you can access any position but implementation of say nextNonWhitespacePosition doesn't look like requesting earlier position would work. I think it might be better to go for full random access (and rename to so SimpleLineLayout::FlowContent). If simple forward movement requires optimization then that can be achieved via caching.

I suspect this type would get simpler if you just initialize m_textRanges fully in constructor and keep it immutable afterwards.

> Source/WebCore/rendering/SimpleLineLayout.cpp:227
> +        firstChild.clearNeedsLayout();

This type should not modify layout bits (or anything at all!) since it doesn't do any layout.

> Source/WebCore/rendering/SimpleLineLayout.cpp:282
> +            if (m_onlyChild)
> +                break;
> +
> +            // Get the next renderer so that we know where to split up the text to measure.
> +            fromRenderer = downcast<RenderText>(fromRenderer->nextSibling());
> +            if (!fromRenderer)
> +                break;

Is m_onlyChild really a valuable optimization? It would be better to leave it out for now to simplify the patch.

> Source/WebCore/rendering/SimpleLineLayout.cpp:302
> +    void resolveRunPositionsAndReleaseIteratorContent(Layout::RunVector& lineRuns, unsigned lineStartRunIndex)

This type should not know about Runs. It should be strictly about accessing content and mutate nothing. Function like this should be standalone.

We probably shouldn't have this sort of adjustment step at all. All positions in SimpleLineLayout code (including Run::start/end) should be in flow relative positions instead of RenderText relative ones. Conversions should be strictly encapsulated to this type.

> Source/WebCore/rendering/SimpleLineLayout.cpp:311
> +        unsigned textOffset = rendererIndex > 0 ? m_textRanges[rendererIndex - 1].first : 0;

Recording start rather than end positions in m_textRanges would feel more natural.

> Source/WebCore/rendering/SimpleLineLayout.cpp:321
> +                    // This run overlaps multiple renderers. Break it up.

I think this is sort of an artifact of having renderer pointer in Run. It should be fine to have a run that overlaps renderers. (if these are not broken the RunResolver would need to synthesize Strings that cross boundaries so breaking might still be justified. depends what is simpler/faster)

> Source/WebCore/rendering/SimpleLineLayout.cpp:385
> +            while (left < right) {
> +                unsigned middle = (left + right) / 2;
> +                unsigned endPosition = m_textRanges.at(middle).first;
> +                if (position > endPosition)
> +                    left = middle + 1;
> +                else if (position < endPosition)
> +                    right = middle;
> +                else {
> +                    right = middle;
> +                    break;
> +                }

Maybe you could just use std::binary_search?

> Source/WebCore/rendering/SimpleLineLayout.cpp:412
> +    Vector<std::pair<unsigned, RenderText*>> m_textRanges;

m_textRanges is bit vague, m_textRendererEndPositions or something? Also it it bit strange that this uses end positions rather than start positions.

> Source/WebCore/rendering/SimpleLineLayout.h:57
> +    Run(unsigned start, unsigned end, float logicalLeft, float logicalRight, bool isEndOfLine, RenderText* renderer)
>          : start(start)
>          , end(end)
>          , isEndOfLine(isEndOfLine)
>          , logicalLeft(logicalLeft)
>          , logicalRight(logicalRight)
> +        , renderer(renderer)
>      { }

I don't think we should include renderer pointer to every run. This would increase memory use by 50% by having a data member that rarely changes.

It might be ok as intermediate step though but we need to get rid of it.

> Source/WebCore/rendering/SimpleLineLayoutFunctions.cpp:94
> +        if (run.renderer() != textRenderer) {
> +            textRenderer = run.renderer();
> +            TextPaintStyle textPaintStyle = computeTextPaintStyle(*textRenderer, style, paintInfo);
> +            if (!saveContext && textPaintStyle.strokeWidth > 0) {
> +                stateSaver.save();
> +                saveContext = true;
> +            }
> +            updateGraphicsContext(context, textPaintStyle);
> +        }

This function does not really need to know the RenderText for each run. If you check computeTextPaintStyle, you'll see it just uses it to access frame() and document() (which makes sense, there is no per-RenderText style). It can be be easily factored to not take RenderText. 

See below.

> Source/WebCore/rendering/SimpleLineLayoutFunctions.cpp:159
> +    // Jump to our renderer.
> +    while(it.renderer() != &textRenderer && it != end)
> +        ++it;
> +    if (it == end)
> +        return IntRect();

There should be a helper function that gives iterator range for a given RenderText.

> Source/WebCore/rendering/SimpleLineLayoutResolver.h:195
>  inline StringView RunResolver::Run::text() const
>  {
> -    auto& resolver = m_iterator.resolver();
>      auto& run = m_iterator.simpleRun();
> -    return StringView(resolver.m_string).substring(run.start, run.end - run.start);
> +    return StringView(run.renderer->text()).substring(run.start, run.end - run.start);
> +}
> +
> +inline RenderText* RunResolver::Run::renderer() const
> +{
> +    return m_iterator.simpleRun().renderer;
>  }

I think RunResolver should be able figure out renderer dynamically without a member in SimpleLineLayout::Run. The strategy might be as follows:
- Move FlowContentIterator to a file of its own
- RunResolver has FlowContentIterator member
- RunResolver::Iterator::advance() also advances FlowContentIterator by the length of the run.
- FlowContentIterator can then always tell the current text renderer (and so the string too) and style when we get to the point that can vary

[zalan]

Created attachment 241731 [details]
WIP

first part.

[zalan]

Created attachment 241735 [details]
WIP -resolver part.

[Antti Koivisto]

Comment on attachment 241731 [details]
WIP

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

> Source/WebCore/rendering/SimpleLineLayoutFlowContents.cpp:49
> +    const RenderText* closingNullItem = NULL;

nullptr

> Source/WebCore/rendering/SimpleLineLayoutFlowContents.cpp:136
> +    unsigned left = 0;
> +    unsigned right = arraySize - 1;
> +    ASSERT(arraySize);
> +    ASSERT(position >= 0);
> +    while (left < right) {
> +        unsigned middle = (left + right) / 2;
> +        unsigned endPosition = m_textRanges.at(middle + 1).first;
> +        if (position > endPosition)
> +            left = middle + 1;
> +        else if (position < endPosition)
> +            right = middle;
> +        else {
> +            right = middle + 1;
> +            break;
> +        }
> +    }

I think this could be replaced with std::lower_bound (or upper_) and a lambda comparator. There are number of example in WebCore how to use those with vectors.

[zalan]

Resolver part is moved to Bug 138818

[zalan]

Created attachment 241870 [details]
Patch

[Antti Koivisto]

Comment on attachment 241870 [details]
Patch

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

r=me with a test

> Source/WebCore/ChangeLog:19
> +        Performance test already been added for the multiple rendere use case,
> +        functionality is covered by existing test cases.

A test that shows this working would still be good to have. It can be done easily using internals.settings.setSimpleLineLayoutDebugBordersEnabled(true) and having test with multiple Text nodes vs ref with only one.

> Source/WebCore/rendering/SimpleLineLayout.cpp:587
> +static void splitRunsAtRendererBoundary(Layout::RunVector& lineRuns, const FlowContents& flowContents)
> +{

We can probably change this to happen at run construction time rather than being a separate pass. Might be simpler/faster. This is ok for now.

> Source/WebCore/rendering/SimpleLineLayout.cpp:592
> +    if (!lineRuns.size())
> +        return;
> +
> +    unsigned runIndex = 0;
> +    do {

You should bail out immediately in the common case that there is only one text renderer in flowContents.

> Source/WebCore/rendering/SimpleLineLayoutFlowContents.h:48
> -    unsigned findNextNonWhitespacePosition(unsigned position, unsigned& spaceCount) const;
> +    unsigned findNextNonWhitespacePosition(unsigned position, unsigned& spaceCount);
>  
>      float textWidth(unsigned from, unsigned to, float xPosition) const;
>  
> -    bool isNewlineCharacter(unsigned position) const;
> +    bool isNewlineCharacter(unsigned position);

Why const removals? These are logically const.

[Antti Koivisto]

Comment on attachment 241870 [details]
Patch

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

> Source/WebCore/rendering/SimpleLineLayoutFlowContents.cpp:154
> +    // Content needs to be requested sequentially.
> +    ASSERT(position == string.length());

The interface for this class looks like it is mean for random access yet it actually only works sequentially. At some point we should either make it work for random access or change to iterator style interface that only allow forward movement.

[zalan]

Created attachment 241878 [details]
Patch

[Antti Koivisto]

Comment on attachment 241878 [details]
Patch

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

> LayoutTests/ChangeLog:11
> +        * fast/text/simple-lines-mutliple-renderers.html: Added.

spelling "multiple"

[zalan]

Created attachment 241888 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 241888 [details]
Patch

Clearing flags on attachment: 241888

Committed r176396: <http://trac.webkit.org/changeset/176396>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[WebKit Commit Bot]

Re-opened since this is blocked by bug 138926

[zalan]

Committed r176401: <http://trac.webkit.org/changeset/176401>