Changeset 176510 in webkit


Ignore:
Timestamp:
Nov 23, 2014 10:46:18 AM (9 years ago)
Author:
Antti Koivisto
Message:

Use segment vector for FlowContents
​https://bugs.webkit.org/show_bug.cgi?id=139015

Reviewed by Zalan Bujtas.

And FlowContents::Segment struct and use it.

  • rendering/SimpleLineLayout.cpp:

(WebCore::SimpleLineLayout::removeTrailingWhitespace):
(WebCore::SimpleLineLayout::createLineRuns):
(WebCore::SimpleLineLayout::splitRunsAtRendererBoundary):

Use segments.
If there is only one segment there is nothing to do. Bail out.

  • rendering/SimpleLineLayoutFlowContents.cpp:

(WebCore::SimpleLineLayout::initializeSegments):

Move initialization to a function so m_segments can be const.
Don't add empty end segment, handle the end case in code.

(WebCore::SimpleLineLayout::FlowContents::FlowContents):
(WebCore::SimpleLineLayout::FlowContents::textWidth):

Simplify and use segments.

(WebCore::SimpleLineLayout::FlowContents::segmentForPositionSlow):

Replace hand-rolled binary search with std::lower_bounds.

(WebCore::SimpleLineLayout::FlowContents::segmentForRenderer):
(WebCore::SimpleLineLayout::FlowContents::appendNextRendererContentIfNeeded):
(WebCore::SimpleLineLayout::FlowContents::renderer): Deleted.
(WebCore::SimpleLineLayout::FlowContents::resolveRendererPositions): Deleted.

  • rendering/SimpleLineLayoutFlowContents.h:

(WebCore::SimpleLineLayout::FlowContents::hasOneSegment):
(WebCore::SimpleLineLayout::FlowContents::length):
(WebCore::SimpleLineLayout::FlowContents::isEnd):
(WebCore::SimpleLineLayout::FlowContents::isEndOfContent): Deleted.

Renamed.

(WebCore::SimpleLineLayout::FlowContents::segmentForPosition):

Inline the fast path.

  • rendering/SimpleLineLayoutResolver.cpp:

(WebCore::SimpleLineLayout::RunResolver::Run::text):
(WebCore::SimpleLineLayout::RunResolver::rangeForRenderer):

Location:
trunk/Source/WebCore
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r176509 r176510  
     12014-11-23  Antti Koivisto  <antti@apple.com>
     2
     3        Use segment vector for FlowContents
     4        https://bugs.webkit.org/show_bug.cgi?id=139015
     5
     6        Reviewed by Zalan Bujtas.
     7
     8        And FlowContents::Segment struct and use it.
     9
     10        * rendering/SimpleLineLayout.cpp:
     11        (WebCore::SimpleLineLayout::removeTrailingWhitespace):
     12        (WebCore::SimpleLineLayout::createLineRuns):
     13        (WebCore::SimpleLineLayout::splitRunsAtRendererBoundary):
     14
     15            Use segments.
     16            If there is only one segment there is nothing to do. Bail out.
     17
     18        * rendering/SimpleLineLayoutFlowContents.cpp:
     19        (WebCore::SimpleLineLayout::initializeSegments):
     20
     21            Move initialization to a function so m_segments can be const.
     22            Don't add empty end segment, handle the end case in code.
     23
     24        (WebCore::SimpleLineLayout::FlowContents::FlowContents):
     25        (WebCore::SimpleLineLayout::FlowContents::textWidth):
     26
     27            Simplify and use segments.
     28
     29        (WebCore::SimpleLineLayout::FlowContents::segmentForPositionSlow):
     30
     31            Replace hand-rolled binary search with std::lower_bounds.
     32
     33        (WebCore::SimpleLineLayout::FlowContents::segmentForRenderer):
     34        (WebCore::SimpleLineLayout::FlowContents::appendNextRendererContentIfNeeded):
     35        (WebCore::SimpleLineLayout::FlowContents::renderer): Deleted.
     36        (WebCore::SimpleLineLayout::FlowContents::resolveRendererPositions): Deleted.
     37        * rendering/SimpleLineLayoutFlowContents.h:
     38        (WebCore::SimpleLineLayout::FlowContents::hasOneSegment):
     39        (WebCore::SimpleLineLayout::FlowContents::length):
     40        (WebCore::SimpleLineLayout::FlowContents::isEnd):
     41        (WebCore::SimpleLineLayout::FlowContents::isEndOfContent): Deleted.
     42
     43            Renamed.
     44
     45        (WebCore::SimpleLineLayout::FlowContents::segmentForPosition):
     46
     47            Inline the fast path.
     48
     49        * rendering/SimpleLineLayoutResolver.cpp:
     50        (WebCore::SimpleLineLayout::RunResolver::Run::text):
     51        (WebCore::SimpleLineLayout::RunResolver::rangeForRenderer):
     52
    1532014-11-22  Simon Fraser  <simon.fraser@apple.com>
    254

  • trunk/Source/WebCore/rendering/SimpleLineLayout.cpp

    r176473 r176510  
    409409
    410410    // If we skipped any whitespace and now the line end is a "preserved" newline, skip the newline too as we are wrapping the line here already.
    411     if (lastPosition != lineState.position && style.preserveNewline && !flowContents.isEndOfContent(lineState.position) && flowContents.isNewlineCharacter(lineState.position))
     411    if (lastPosition != lineState.position && style.preserveNewline && !flowContents.isEnd(lineState.position) && flowContents.isNewlineCharacter(lineState.position))
    412412        ++lineState.position;
    413413}
    … …  
    514514    const auto& style = flowContents.style();
    515515    bool lineCanBeWrapped = style.wrapLines || style.breakWordOnOverflow;
    516     while (!flowContents.isEndOfContent(lineState.position)) {
     516    while (!flowContents.isEnd(lineState.position)) {
    517517        // Find the next text fragment. Start from the end of the previous fragment -current line end.
    518518        TextFragment fragment = nextFragment(lineState.position, flowContents, lineState.width());
    … …  
    563563    }
    564564    lineState.commitAndCreateRun(lineRuns);
    565     return flowContents.isEndOfContent(lineState.position) && lineState.oveflowedFragment.isEmpty();
     565    return flowContents.isEnd(lineState.position) && lineState.oveflowedFragment.isEmpty();
    566566}
    567567
    … …  
    588588static void splitRunsAtRendererBoundary(Layout::RunVector& lineRuns, const FlowContents& flowContents)
    589589{
    590     if (!lineRuns.size())
     590    // FIXME: We should probably split during run construction instead of as a separate pass.
     591    if (lineRuns.isEmpty())
     592        return;
     593    if (flowContents.hasOneSegment())
    591594        return;
    592595
    … …  
    595598        const Run& run = lineRuns.at(runIndex);
    596599        ASSERT(run.start != run.end);
    597         const RenderText* startRenderer = flowContents.renderer(run.start);
    598         const RenderText* endRenderer = flowContents.renderer(run.end - 1);
    599         if (startRenderer == endRenderer)
     600        auto& startSegment = flowContents.segmentForPosition(run.start);
     601        if (run.end <= startSegment.end)
    600602            continue;
    601603        // This run overlaps multiple renderers. Split it up.
    602         unsigned rendererStartPosition = 0;
    603         unsigned rendererEndPosition = 0;
    604         bool found = flowContents.resolveRendererPositions(*startRenderer, rendererStartPosition, rendererEndPosition);
    605         ASSERT_UNUSED(found, found);
    606 
    607604        // Split run at the renderer's boundary and create a new run for the left side, while use the current run as the right side.
    608         float logicalRightOfLeftRun = run.logicalLeft + flowContents.textWidth(run.start, rendererEndPosition, run.logicalLeft);
    609         lineRuns.insert(runIndex, Run(run.start, rendererEndPosition, run.logicalLeft, logicalRightOfLeftRun, false));
     605        float logicalRightOfLeftRun = run.logicalLeft + flowContents.textWidth(run.start, startSegment.end, run.logicalLeft);
     606        lineRuns.insert(runIndex, Run(run.start, startSegment.end, run.logicalLeft, logicalRightOfLeftRun, false));
    610607        Run& rightSideRun = lineRuns.at(runIndex + 1);
    611         rightSideRun.start = rendererEndPosition;
     608        rightSideRun.start = startSegment.end;
    612609        rightSideRun.logicalLeft = logicalRightOfLeftRun;
    613610    } while (++runIndex < lineRuns.size());
    … …  
    639636    } while (!isEndOfContent);
    640637
    641     if (flow.firstChild() != flow.lastChild())
    642         splitRunsAtRendererBoundary(runs, flowContents);
     638    splitRunsAtRendererBoundary(runs, flowContents);
    643639    ASSERT(!lineState.uncommittedWidth);
    644640}

  • trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.cpp

    r176507 r176510  
    4747}
    4848
     49static Vector<FlowContents::Segment> initializeSegments(const RenderBlockFlow& flow)
     50{
     51    Vector<FlowContents::Segment, 8> segments;
     52    unsigned startPosition = 0;
     53    for (auto& textChild : childrenOfType<RenderText>(flow)) {
     54        unsigned textLength = textChild.text()->length();
     55        segments.append(FlowContents::Segment { startPosition, startPosition + textLength, textChild });
     56        startPosition += textLength;
     57    }
     58    return segments;
     59}
     60
    4961FlowContents::FlowContents(const RenderBlockFlow& flow)
    5062    : m_style(flow.style())
     63    , m_segments(initializeSegments(flow))
    5164    , m_lineBreakIterator(downcast<RenderText>(*flow.firstChild()).text(), flow.style().locale())
    52     , m_lastRendererIndex(0)
     65    , m_lastSegmentIndex(0)
    5366{
    54     unsigned startPosition = 0;
    55     for (auto& textChild : childrenOfType<RenderText>(flow)) {
    56         unsigned contentLength = textChild.text()->length();
    57         m_textRanges.append(std::make_pair(startPosition, &textChild));
    58         startPosition += contentLength;
    59     }
    60     // End item.
    61     const RenderText* closingNullItem = nullptr;
    62     m_textRanges.append(std::make_pair(startPosition, closingNullItem));
    6367}
    6468
    … …  
    8488float FlowContents::textWidth(unsigned from, unsigned to, float xPosition) const
    8589{
    86     unsigned rendererStart = 0;
    87     const RenderText* textRenderer = renderer(from, &rendererStart);
    88     ASSERT(textRenderer);
    89     // Resolved positions are relative to the renderers.
    90     unsigned absoluteStart = from - rendererStart;
    91     unsigned absoluteEnd = to - rendererStart;
    92     if ((m_style.font.isFixedPitch() && textRenderer == renderer(to)) || (!absoluteStart && absoluteEnd == textRenderer->text()->length()))
    93         return textRenderer->width(absoluteStart, to - from, m_style.font, xPosition, nullptr, nullptr);
     90    auto& fromSegment = segmentForPosition(from);
    9491
    95     // We need to split up the text and measure renderers individually due to ligature.
     92    if ((m_style.font.isFixedPitch() && fromSegment.end >= to) || (from == fromSegment.start && to == fromSegment.end))
     93        return fromSegment.renderer.width(from - fromSegment.start, to - from, m_style.font, xPosition, nullptr, nullptr);
     94
     95    auto* segment = &fromSegment;
    9696    float textWidth = 0;
    9797    unsigned fragmentEnd = 0;
    98     do {
    99         fragmentEnd = std::min(to, rendererStart + textRenderer->text()->length());
    100         unsigned absoluteFragmentEnd = fragmentEnd - rendererStart;
    101         absoluteStart = from - rendererStart;
    102         textWidth += runWidth(*textRenderer, absoluteStart, absoluteFragmentEnd, xPosition + textWidth);
     98    while (true) {
     99        fragmentEnd = std::min(to, segment->end);
     100        textWidth += runWidth(segment->renderer, from - segment->start, fragmentEnd - segment->start, xPosition + textWidth);
     101        if (fragmentEnd == to)
     102            break;
    103103        from = fragmentEnd;
    104         if (fragmentEnd < to)
    105             textRenderer = renderer(fragmentEnd, &rendererStart);
    106     } while (fragmentEnd < to && textRenderer);
     104        segment = &segmentForPosition(fragmentEnd);
     105    };
     106
    107107    return textWidth;
    108108}
    109109
    110 const RenderText* FlowContents::renderer(unsigned position, unsigned* rendererStartPosition) const
     110const FlowContents::Segment& FlowContents::segmentForPositionSlow(unsigned position) const
    111111{
    112     unsigned arraySize = m_textRanges.size();
    113     // Take advantage of the usage pattern.
    114     if (position >= m_textRanges.at(m_lastRendererIndex).first && m_lastRendererIndex + 1 < arraySize && position < m_textRanges.at(m_lastRendererIndex + 1).first) {
    115         if (rendererStartPosition)
    116             *rendererStartPosition = m_textRanges.at(m_lastRendererIndex).first;
    117         return m_textRanges.at(m_lastRendererIndex).second;
    118     }
    119     unsigned left = 0;
    120     unsigned right = arraySize - 1;
    121     ASSERT(arraySize);
    122     ASSERT(position >= 0);
    123     while (left < right) {
    124         unsigned middle = (left + right) / 2;
    125         unsigned endPosition = m_textRanges.at(middle + 1).first;
    126         if (position > endPosition)
    127             left = middle + 1;
    128         else if (position < endPosition)
    129             right = middle;
    130         else {
    131             right = middle + 1;
    132             break;
    133         }
    134     }
    135     if (rendererStartPosition)
    136         *rendererStartPosition = m_textRanges.at(right).first;
    137     return m_textRanges.at(right).second;
     112    auto it = std::lower_bound(m_segments.begin(), m_segments.end(), position, [](const Segment& segment, unsigned position) {
     113        return segment.end <= position;
     114    });
     115    ASSERT(it != m_segments.end());
     116    m_lastSegmentIndex = it - m_segments.begin();
     117    return *it;
    138118}
    139119
    140 bool FlowContents::resolveRendererPositions(const RenderText& renderer, unsigned& startPosition, unsigned& endPosition) const
     120const FlowContents::Segment& FlowContents::segmentForRenderer(const RenderText& renderer) const
    141121{
    142     unsigned arraySize = m_textRanges.size();
    143     if (!arraySize)
    144         return false;
    145 
    146     unsigned index = 0;
    147     do {
    148         auto range = m_textRanges.at(index);
    149         if (range.second == &renderer) {
    150             startPosition = range.first;
    151             ASSERT(index + 1 < arraySize);
    152             endPosition = m_textRanges.at(index + 1).first;
    153             return true;
    154         }
    155     } while (++index < arraySize);
    156     return false;
     122    for (auto& segment : m_segments) {
     123        if (&segment.renderer == &renderer)
     124            return segment;
     125    }
     126    ASSERT_NOT_REACHED();
     127    return m_segments.last();
    157128}
    158129
    159130bool FlowContents::appendNextRendererContentIfNeeded(unsigned position) const
    160131{
     132    if (isEnd(position))
     133        return false;
    161134    String string = m_lineBreakIterator.string();
    162135    if (position < string.length())
    … …  
    165138    // Content needs to be requested sequentially.
    166139    ASSERT(position == string.length());
    167     const RenderText* nextRenderer = renderer(position);
    168     if (!nextRenderer)
    169         return false;
     140    auto& segment = segmentForPosition(position);
    170141
    171     ++m_lastRendererIndex;
    172     m_lineBreakIterator.resetStringAndReleaseIterator(string + String(nextRenderer->text()), m_style.locale, LineBreakIteratorModeUAX14);
     142    m_lineBreakIterator.resetStringAndReleaseIterator(string + String(segment.renderer.text()), m_style.locale, LineBreakIteratorModeUAX14);
    173143    return true;
    174144}

  • trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.h

    r176507 r176510  
    4747
    4848    bool isNewlineCharacter(unsigned position) const;
    49     bool isEndOfContent(unsigned position) const;
     49    bool isEnd(unsigned position) const;
    5050
    51     bool resolveRendererPositions(const RenderText&, unsigned& startPosition, unsigned& endPosition) const;
    52     const RenderText* renderer(unsigned position, unsigned* startPosition = nullptr) const;
     51    struct Segment {
     52        unsigned start;
     53        unsigned end;
     54        const RenderText& renderer;
     55    };
     56    const Segment& segmentForPosition(unsigned) const;
     57    const Segment& segmentForRenderer(const RenderText&) const;
     58
     59    bool hasOneSegment() const { return m_segments.size() == 1; }
     60    unsigned length() const { return m_segments.last().end; };
    5361
    5462    struct Style {
    … …  
    6876
    6977private:
     78    const Segment& segmentForPositionSlow(unsigned) const;
    7079    bool appendNextRendererContentIfNeeded(unsigned position) const;
    7180    unsigned nextNonWhitespacePosition(unsigned position, unsigned& spaceCount) const;
    … …  
    7382
    7483    const Style m_style;
     84    const Vector<Segment, 8> m_segments;
     85
    7586    mutable LazyLineBreakIterator m_lineBreakIterator;
    76     Vector<std::pair<unsigned, const RenderText*>> m_textRanges;
    77     mutable unsigned m_lastRendererIndex;
     87    mutable unsigned m_lastSegmentIndex;
    7888};
    7989
    … …  
    8595}
    8696
    87 inline bool FlowContents::isEndOfContent(unsigned position) const
     97inline bool FlowContents::isEnd(unsigned position) const
    8898{
    89     return position >= m_lineBreakIterator.string().length() && !renderer(position);
     99    return position >= length();
     100}
     101
     102inline const FlowContents::Segment& FlowContents::segmentForPosition(unsigned position) const
     103{
     104    ASSERT(!isEnd(position));
     105
     106    auto& lastSegment = m_segments[m_lastSegmentIndex];
     107    if (lastSegment.start <= position && position < lastSegment.end)
     108        return lastSegment;
     109    return segmentForPositionSlow(position);
    90110}
    91111

  • trunk/Source/WebCore/rendering/SimpleLineLayoutResolver.cpp

    r176401 r176510  
    7777    auto& resolver = m_iterator.resolver();
    7878    auto& run = m_iterator.simpleRun();
    79     unsigned rendererOffset = 0;
    80     const auto* renderer = resolver.m_flowContents.renderer(run.start, &rendererOffset);
    81     ASSERT(renderer);
    82     ASSERT(renderer->is8Bit());
    83     return StringView(renderer->characters8(), renderer->textLength()).substring(run.start - rendererOffset, run.end - run.start);
     79    auto& segment = resolver.m_flowContents.segmentForPosition(run.start);
     80    ASSERT(segment.renderer.is8Bit());
     81    // We currently split runs on segment boundaries (different RenderText).
     82    ASSERT(run.end <= segment.end);
     83    return StringView(segment.renderer.characters8(), segment.renderer.textLength()).substring(run.start - segment.start, run.end - run.start);
    8484}
    8585
    … …  
    157157Range<RunResolver::Iterator> RunResolver::rangeForRenderer(const RenderText& renderer) const
    158158{
    159     unsigned startPosition = 0;
    160     unsigned endPosition = 0;
    161     m_flowContents.resolveRendererPositions(renderer, startPosition, endPosition);
     159    auto& segment = m_flowContents.segmentForRenderer(renderer);
     160
    162161    auto rangeBegin = begin();
    163     for (;(*rangeBegin).start() < startPosition && rangeBegin != end(); ++rangeBegin) { }
     162    for (;(*rangeBegin).start() < segment.start && rangeBegin != end(); ++rangeBegin) { }
     163
    164164    auto rangeEnd = rangeBegin;
    165     for (;(*rangeEnd).end() <= endPosition && rangeEnd != end(); ++rangeEnd) { }
     165    for (;(*rangeEnd).end() <= segment.end && rangeEnd != end(); ++rangeEnd) { }
     166
    166167    return Range<Iterator>(rangeBegin, rangeEnd);
    167168}
Note: See TracChangeset for help on using the changeset viewer.