Diff
Modified: trunk/Source/WebCore/ChangeLog (176509 => 176510)
--- trunk/Source/WebCore/ChangeLog 2014-11-23 18:00:52 UTC (rev 176509)
+++ trunk/Source/WebCore/ChangeLog 2014-11-23 18:46:18 UTC (rev 176510)
@@ -1,3 +1,55 @@
+2014-11-23 Antti Koivisto <[email protected]>
+
+ 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):
+
2014-11-22 Simon Fraser <[email protected]>
Extend WKRenderObject and WKRenderLayer with some more useful data
Modified: trunk/Source/WebCore/rendering/SimpleLineLayout.cpp (176509 => 176510)
--- trunk/Source/WebCore/rendering/SimpleLineLayout.cpp 2014-11-23 18:00:52 UTC (rev 176509)
+++ trunk/Source/WebCore/rendering/SimpleLineLayout.cpp 2014-11-23 18:46:18 UTC (rev 176510)
@@ -408,7 +408,7 @@
}
// 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.
- if (lastPosition != lineState.position && style.preserveNewline && !flowContents.isEndOfContent(lineState.position) && flowContents.isNewlineCharacter(lineState.position))
+ if (lastPosition != lineState.position && style.preserveNewline && !flowContents.isEnd(lineState.position) && flowContents.isNewlineCharacter(lineState.position))
++lineState.position;
}
@@ -513,7 +513,7 @@
{
const auto& style = flowContents.style();
bool lineCanBeWrapped = style.wrapLines || style.breakWordOnOverflow;
- while (!flowContents.isEndOfContent(lineState.position)) {
+ while (!flowContents.isEnd(lineState.position)) {
// Find the next text fragment. Start from the end of the previous fragment -current line end.
TextFragment fragment = nextFragment(lineState.position, flowContents, lineState.width());
if ((lineCanBeWrapped && !lineState.fits(fragment.width)) || fragment.mustBreak) {
@@ -562,7 +562,7 @@
lineState.addUncommitted(fragment);
}
lineState.commitAndCreateRun(lineRuns);
- return flowContents.isEndOfContent(lineState.position) && lineState.oveflowedFragment.isEmpty();
+ return flowContents.isEnd(lineState.position) && lineState.oveflowedFragment.isEmpty();
}
static void closeLineEndingAndAdjustRuns(LineState& lineState, Layout::RunVector& lineRuns, unsigned& lineCount, const FlowContents& flowContents)
@@ -587,28 +587,25 @@
static void splitRunsAtRendererBoundary(Layout::RunVector& lineRuns, const FlowContents& flowContents)
{
- if (!lineRuns.size())
+ // FIXME: We should probably split during run construction instead of as a separate pass.
+ if (lineRuns.isEmpty())
return;
+ if (flowContents.hasOneSegment())
+ return;
unsigned runIndex = 0;
do {
const Run& run = lineRuns.at(runIndex);
ASSERT(run.start != run.end);
- const RenderText* startRenderer = flowContents.renderer(run.start);
- const RenderText* endRenderer = flowContents.renderer(run.end - 1);
- if (startRenderer == endRenderer)
+ auto& startSegment = flowContents.segmentForPosition(run.start);
+ if (run.end <= startSegment.end)
continue;
// This run overlaps multiple renderers. Split it up.
- unsigned rendererStartPosition = 0;
- unsigned rendererEndPosition = 0;
- bool found = flowContents.resolveRendererPositions(*startRenderer, rendererStartPosition, rendererEndPosition);
- ASSERT_UNUSED(found, found);
-
// 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.
- float logicalRightOfLeftRun = run.logicalLeft + flowContents.textWidth(run.start, rendererEndPosition, run.logicalLeft);
- lineRuns.insert(runIndex, Run(run.start, rendererEndPosition, run.logicalLeft, logicalRightOfLeftRun, false));
+ float logicalRightOfLeftRun = run.logicalLeft + flowContents.textWidth(run.start, startSegment.end, run.logicalLeft);
+ lineRuns.insert(runIndex, Run(run.start, startSegment.end, run.logicalLeft, logicalRightOfLeftRun, false));
Run& rightSideRun = lineRuns.at(runIndex + 1);
- rightSideRun.start = rendererEndPosition;
+ rightSideRun.start = startSegment.end;
rightSideRun.logicalLeft = logicalRightOfLeftRun;
} while (++runIndex < lineRuns.size());
}
@@ -638,8 +635,7 @@
closeLineEndingAndAdjustRuns(lineState, runs, lineCount, flowContents);
} while (!isEndOfContent);
- if (flow.firstChild() != flow.lastChild())
- splitRunsAtRendererBoundary(runs, flowContents);
+ splitRunsAtRendererBoundary(runs, flowContents);
ASSERT(!lineState.uncommittedWidth);
}
Modified: trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.cpp (176509 => 176510)
--- trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.cpp 2014-11-23 18:00:52 UTC (rev 176509)
+++ trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.cpp 2014-11-23 18:46:18 UTC (rev 176510)
@@ -46,22 +46,26 @@
{
}
-FlowContents::FlowContents(const RenderBlockFlow& flow)
- : m_style(flow.style())
- , m_lineBreakIterator(downcast<RenderText>(*flow.firstChild()).text(), flow.style().locale())
- , m_lastRendererIndex(0)
+static Vector<FlowContents::Segment> initializeSegments(const RenderBlockFlow& flow)
{
+ Vector<FlowContents::Segment, 8> segments;
unsigned startPosition = 0;
for (auto& textChild : childrenOfType<RenderText>(flow)) {
- unsigned contentLength = textChild.text()->length();
- m_textRanges.append(std::make_pair(startPosition, &textChild));
- startPosition += contentLength;
+ unsigned textLength = textChild.text()->length();
+ segments.append(FlowContents::Segment { startPosition, startPosition + textLength, textChild });
+ startPosition += textLength;
}
- // End item.
- const RenderText* closingNullItem = nullptr;
- m_textRanges.append(std::make_pair(startPosition, closingNullItem));
+ return segments;
}
+FlowContents::FlowContents(const RenderBlockFlow& flow)
+ : m_style(flow.style())
+ , m_segments(initializeSegments(flow))
+ , m_lineBreakIterator(downcast<RenderText>(*flow.firstChild()).text(), flow.style().locale())
+ , m_lastSegmentIndex(0)
+{
+}
+
unsigned FlowContents::findNextBreakablePosition(unsigned position) const
{
String string = m_lineBreakIterator.string();
@@ -83,93 +87,59 @@
float FlowContents::textWidth(unsigned from, unsigned to, float xPosition) const
{
- unsigned rendererStart = 0;
- const RenderText* textRenderer = renderer(from, &rendererStart);
- ASSERT(textRenderer);
- // Resolved positions are relative to the renderers.
- unsigned absoluteStart = from - rendererStart;
- unsigned absoluteEnd = to - rendererStart;
- if ((m_style.font.isFixedPitch() && textRenderer == renderer(to)) || (!absoluteStart && absoluteEnd == textRenderer->text()->length()))
- return textRenderer->width(absoluteStart, to - from, m_style.font, xPosition, nullptr, nullptr);
+ auto& fromSegment = segmentForPosition(from);
- // We need to split up the text and measure renderers individually due to ligature.
+ if ((m_style.font.isFixedPitch() && fromSegment.end >= to) || (from == fromSegment.start && to == fromSegment.end))
+ return fromSegment.renderer.width(from - fromSegment.start, to - from, m_style.font, xPosition, nullptr, nullptr);
+
+ auto* segment = &fromSegment;
float textWidth = 0;
unsigned fragmentEnd = 0;
- do {
- fragmentEnd = std::min(to, rendererStart + textRenderer->text()->length());
- unsigned absoluteFragmentEnd = fragmentEnd - rendererStart;
- absoluteStart = from - rendererStart;
- textWidth += runWidth(*textRenderer, absoluteStart, absoluteFragmentEnd, xPosition + textWidth);
+ while (true) {
+ fragmentEnd = std::min(to, segment->end);
+ textWidth += runWidth(segment->renderer, from - segment->start, fragmentEnd - segment->start, xPosition + textWidth);
+ if (fragmentEnd == to)
+ break;
from = fragmentEnd;
- if (fragmentEnd < to)
- textRenderer = renderer(fragmentEnd, &rendererStart);
- } while (fragmentEnd < to && textRenderer);
+ segment = &segmentForPosition(fragmentEnd);
+ };
+
return textWidth;
}
-const RenderText* FlowContents::renderer(unsigned position, unsigned* rendererStartPosition) const
+const FlowContents::Segment& FlowContents::segmentForPositionSlow(unsigned position) const
{
- unsigned arraySize = m_textRanges.size();
- // Take advantage of the usage pattern.
- if (position >= m_textRanges.at(m_lastRendererIndex).first && m_lastRendererIndex + 1 < arraySize && position < m_textRanges.at(m_lastRendererIndex + 1).first) {
- if (rendererStartPosition)
- *rendererStartPosition = m_textRanges.at(m_lastRendererIndex).first;
- return m_textRanges.at(m_lastRendererIndex).second;
- }
- 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;
- }
- }
- if (rendererStartPosition)
- *rendererStartPosition = m_textRanges.at(right).first;
- return m_textRanges.at(right).second;
+ auto it = std::lower_bound(m_segments.begin(), m_segments.end(), position, [](const Segment& segment, unsigned position) {
+ return segment.end <= position;
+ });
+ ASSERT(it != m_segments.end());
+ m_lastSegmentIndex = it - m_segments.begin();
+ return *it;
}
-bool FlowContents::resolveRendererPositions(const RenderText& renderer, unsigned& startPosition, unsigned& endPosition) const
+const FlowContents::Segment& FlowContents::segmentForRenderer(const RenderText& renderer) const
{
- unsigned arraySize = m_textRanges.size();
- if (!arraySize)
- return false;
-
- unsigned index = 0;
- do {
- auto range = m_textRanges.at(index);
- if (range.second == &renderer) {
- startPosition = range.first;
- ASSERT(index + 1 < arraySize);
- endPosition = m_textRanges.at(index + 1).first;
- return true;
- }
- } while (++index < arraySize);
- return false;
+ for (auto& segment : m_segments) {
+ if (&segment.renderer == &renderer)
+ return segment;
+ }
+ ASSERT_NOT_REACHED();
+ return m_segments.last();
}
bool FlowContents::appendNextRendererContentIfNeeded(unsigned position) const
{
+ if (isEnd(position))
+ return false;
String string = m_lineBreakIterator.string();
if (position < string.length())
return false;
// Content needs to be requested sequentially.
ASSERT(position == string.length());
- const RenderText* nextRenderer = renderer(position);
- if (!nextRenderer)
- return false;
+ auto& segment = segmentForPosition(position);
- ++m_lastRendererIndex;
- m_lineBreakIterator.resetStringAndReleaseIterator(string + String(nextRenderer->text()), m_style.locale, LineBreakIteratorModeUAX14);
+ m_lineBreakIterator.resetStringAndReleaseIterator(string + String(segment.renderer.text()), m_style.locale, LineBreakIteratorModeUAX14);
return true;
}
Modified: trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.h (176509 => 176510)
--- trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.h 2014-11-23 18:00:52 UTC (rev 176509)
+++ trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContents.h 2014-11-23 18:46:18 UTC (rev 176510)
@@ -46,11 +46,19 @@
float textWidth(unsigned from, unsigned to, float xPosition) const;
bool isNewlineCharacter(unsigned position) const;
- bool isEndOfContent(unsigned position) const;
+ bool isEnd(unsigned position) const;
- bool resolveRendererPositions(const RenderText&, unsigned& startPosition, unsigned& endPosition) const;
- const RenderText* renderer(unsigned position, unsigned* startPosition = nullptr) const;
+ struct Segment {
+ unsigned start;
+ unsigned end;
+ const RenderText& renderer;
+ };
+ const Segment& segmentForPosition(unsigned) const;
+ const Segment& segmentForRenderer(const RenderText&) const;
+ bool hasOneSegment() const { return m_segments.size() == 1; }
+ unsigned length() const { return m_segments.last().end; };
+
struct Style {
explicit Style(const RenderStyle&);
@@ -67,14 +75,16 @@
const Style& style() const { return m_style; }
private:
+ const Segment& segmentForPositionSlow(unsigned) const;
bool appendNextRendererContentIfNeeded(unsigned position) const;
unsigned nextNonWhitespacePosition(unsigned position, unsigned& spaceCount) const;
float runWidth(const RenderText&, unsigned from, unsigned to, float xPosition) const;
const Style m_style;
+ const Vector<Segment, 8> m_segments;
+
mutable LazyLineBreakIterator m_lineBreakIterator;
- Vector<std::pair<unsigned, const RenderText*>> m_textRanges;
- mutable unsigned m_lastRendererIndex;
+ mutable unsigned m_lastSegmentIndex;
};
inline bool FlowContents::isNewlineCharacter(unsigned position) const
@@ -84,12 +94,22 @@
return m_lineBreakIterator.string().at(position) == '\n';
}
-inline bool FlowContents::isEndOfContent(unsigned position) const
+inline bool FlowContents::isEnd(unsigned position) const
{
- return position >= m_lineBreakIterator.string().length() && !renderer(position);
+ return position >= length();
}
+inline const FlowContents::Segment& FlowContents::segmentForPosition(unsigned position) const
+{
+ ASSERT(!isEnd(position));
+
+ auto& lastSegment = m_segments[m_lastSegmentIndex];
+ if (lastSegment.start <= position && position < lastSegment.end)
+ return lastSegment;
+ return segmentForPositionSlow(position);
}
+
}
+}
#endif
Modified: trunk/Source/WebCore/rendering/SimpleLineLayoutResolver.cpp (176509 => 176510)
--- trunk/Source/WebCore/rendering/SimpleLineLayoutResolver.cpp 2014-11-23 18:00:52 UTC (rev 176509)
+++ trunk/Source/WebCore/rendering/SimpleLineLayoutResolver.cpp 2014-11-23 18:46:18 UTC (rev 176510)
@@ -76,11 +76,11 @@
{
auto& resolver = m_iterator.resolver();
auto& run = m_iterator.simpleRun();
- unsigned rendererOffset = 0;
- const auto* renderer = resolver.m_flowContents.renderer(run.start, &rendererOffset);
- ASSERT(renderer);
- ASSERT(renderer->is8Bit());
- return StringView(renderer->characters8(), renderer->textLength()).substring(run.start - rendererOffset, run.end - run.start);
+ auto& segment = resolver.m_flowContents.segmentForPosition(run.start);
+ ASSERT(segment.renderer.is8Bit());
+ // We currently split runs on segment boundaries (different RenderText).
+ ASSERT(run.end <= segment.end);
+ return StringView(segment.renderer.characters8(), segment.renderer.textLength()).substring(run.start - segment.start, run.end - run.start);
}
RunResolver::Iterator::Iterator(const RunResolver& resolver, unsigned runIndex, unsigned lineIndex)
@@ -156,13 +156,14 @@
Range<RunResolver::Iterator> RunResolver::rangeForRenderer(const RenderText& renderer) const
{
- unsigned startPosition = 0;
- unsigned endPosition = 0;
- m_flowContents.resolveRendererPositions(renderer, startPosition, endPosition);
+ auto& segment = m_flowContents.segmentForRenderer(renderer);
+
auto rangeBegin = begin();
- for (;(*rangeBegin).start() < startPosition && rangeBegin != end(); ++rangeBegin) { }
+ for (;(*rangeBegin).start() < segment.start && rangeBegin != end(); ++rangeBegin) { }
+
auto rangeEnd = rangeBegin;
- for (;(*rangeEnd).end() <= endPosition && rangeEnd != end(); ++rangeEnd) { }
+ for (;(*rangeEnd).end() <= segment.end && rangeEnd != end(); ++rangeEnd) { }
+
return Range<Iterator>(rangeBegin, rangeEnd);
}
