f2c3345dd3f90910193e4c782fc386b6e0acca6a
[WebKit-https.git] / Source / WebCore / rendering / SimpleLineLayout.cpp
1 /*
2  * Copyright (C) 2013 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "SimpleLineLayout.h"
28
29 #include "FontCache.h"
30 #include "Frame.h"
31 #include "GraphicsContext.h"
32 #include "HTMLTextFormControlElement.h"
33 #include "HitTestLocation.h"
34 #include "HitTestRequest.h"
35 #include "HitTestResult.h"
36 #include "InlineTextBox.h"
37 #include "LineWidth.h"
38 #include "PaintInfo.h"
39 #include "RenderBlockFlow.h"
40 #include "RenderChildIterator.h"
41 #include "RenderStyle.h"
42 #include "RenderText.h"
43 #include "RenderTextControl.h"
44 #include "RenderView.h"
45 #include "Settings.h"
46 #include "SimpleLineLayoutFlowContents.h"
47 #include "SimpleLineLayoutFunctions.h"
48 #include "Text.h"
49 #include "TextPaintStyle.h"
50
51 namespace WebCore {
52 namespace SimpleLineLayout {
53
54 template <typename CharacterType>
55 static bool canUseForText(const CharacterType* text, unsigned length, const SimpleFontData& fontData)
56 {
57     // FIXME: <textarea maxlength=0> generates empty text node.
58     if (!length)
59         return false;
60     for (unsigned i = 0; i < length; ++i) {
61         UChar character = text[i];
62         if (character == ' ')
63             continue;
64
65         // These would be easy to support.
66         if (character == noBreakSpace)
67             return false;
68         if (character == softHyphen)
69             return false;
70
71         UCharDirection direction = u_charDirection(character);
72         if (direction == U_RIGHT_TO_LEFT || direction == U_RIGHT_TO_LEFT_ARABIC
73             || direction == U_RIGHT_TO_LEFT_EMBEDDING || direction == U_RIGHT_TO_LEFT_OVERRIDE
74             || direction == U_LEFT_TO_RIGHT_EMBEDDING || direction == U_LEFT_TO_RIGHT_OVERRIDE
75             || direction == U_POP_DIRECTIONAL_FORMAT || direction == U_BOUNDARY_NEUTRAL)
76             return false;
77
78         if (!fontData.glyphForCharacter(character))
79             return false;
80     }
81     return true;
82 }
83
84 static bool canUseForText(const RenderText& textRenderer, const SimpleFontData& fontData)
85 {
86     if (textRenderer.is8Bit())
87         return canUseForText(textRenderer.characters8(), textRenderer.textLength(), fontData);
88     return canUseForText(textRenderer.characters16(), textRenderer.textLength(), fontData);
89 }
90
91 bool canUseFor(const RenderBlockFlow& flow)
92 {
93     if (!flow.frame().settings().simpleLineLayoutEnabled())
94         return false;
95     if (!flow.firstChild())
96         return false;
97     // This currently covers <blockflow>#text</blockflow> and mutiple (sibling) RenderText cases.
98     // The <blockflow><inline>#text</inline></blockflow> case is also popular and should be relatively easy to cover.
99     for (const auto& renderer : childrenOfType<RenderObject>(flow)) {
100         if (!is<RenderText>(renderer) || !downcast<RenderText>(renderer).text()->is8Bit())
101             return false;
102     }
103     if (!flow.isHorizontalWritingMode())
104         return false;
105     if (flow.flowThreadState() != RenderObject::NotInsideFlowThread)
106         return false;
107     // Printing does pagination without a flow thread.
108     if (flow.document().paginated())
109         return false;
110     if (flow.hasOutline())
111         return false;
112     if (flow.isRubyText() || flow.isRubyBase())
113         return false;
114     if (flow.parent()->isDeprecatedFlexibleBox())
115         return false;
116     // FIXME: Implementation of wrap=hard looks into lineboxes.
117     if (flow.parent()->isTextArea() && flow.parent()->element()->fastHasAttribute(HTMLNames::wrapAttr))
118         return false;
119     // FIXME: Placeholders do something strange.
120     if (is<RenderTextControl>(*flow.parent()) && downcast<RenderTextControl>(*flow.parent()).textFormControlElement().placeholderElement())
121         return false;
122     const RenderStyle& style = flow.style();
123     if (style.textDecorationsInEffect() != TextDecorationNone)
124         return false;
125     if (style.textAlign() == JUSTIFY)
126         return false;
127     // Non-visible overflow should be pretty easy to support.
128     if (style.overflowX() != OVISIBLE || style.overflowY() != OVISIBLE)
129         return false;
130     if (!style.textIndent().isZero())
131         return false;
132     if (!style.wordSpacing().isZero() || style.letterSpacing())
133         return false;
134     if (!style.isLeftToRightDirection())
135         return false;
136     if (style.lineBoxContain() != RenderStyle::initialLineBoxContain())
137         return false;
138     if (style.writingMode() != TopToBottomWritingMode)
139         return false;
140     if (style.lineBreak() != LineBreakAuto)
141         return false;
142     if (style.wordBreak() != NormalWordBreak)
143         return false;
144     if (style.unicodeBidi() != UBNormal || style.rtlOrdering() != LogicalOrder)
145         return false;
146     if (style.lineAlign() != LineAlignNone || style.lineSnap() != LineSnapNone)
147         return false;
148     if (style.hyphens() == HyphensAuto)
149         return false;
150     if (style.textEmphasisFill() != TextEmphasisFillFilled || style.textEmphasisMark() != TextEmphasisMarkNone)
151         return false;
152     if (style.textShadow())
153         return false;
154     if (style.textOverflow() || (flow.isAnonymousBlock() && flow.parent()->style().textOverflow()))
155         return false;
156     if (style.hasPseudoStyle(FIRST_LINE) || style.hasPseudoStyle(FIRST_LETTER))
157         return false;
158     if (style.hasTextCombine())
159         return false;
160     if (style.backgroundClip() == TextFillBox)
161         return false;
162     if (style.borderFit() == BorderFitLines)
163         return false;
164     const RenderText& textRenderer = downcast<RenderText>(*flow.firstChild());
165     if (flow.containsFloats()) {
166         // We can't use the code path if any lines would need to be shifted below floats. This is because we don't keep per-line y coordinates.
167         float minimumWidthNeeded = textRenderer.minLogicalWidth();
168         for (auto& floatRenderer : *flow.floatingObjectSet()) {
169             ASSERT(floatRenderer);
170             float availableWidth = flow.availableLogicalWidthForLine(floatRenderer->y(), false);
171             if (availableWidth < minimumWidthNeeded)
172                 return false;
173         }
174     }
175     if (textRenderer.isCombineText() || textRenderer.isCounter() || textRenderer.isQuote() || textRenderer.isTextFragment()
176         || textRenderer.isSVGInlineText())
177         return false;
178     if (style.font().codePath(TextRun(textRenderer.text())) != Font::Simple)
179         return false;
180     if (style.font().primaryFont()->isSVGFont())
181         return false;
182
183     // We assume that all lines have metrics based purely on the primary font.
184     auto& primaryFontData = *style.font().primaryFont();
185     if (primaryFontData.isLoading())
186         return false;
187     if (!canUseForText(textRenderer, primaryFontData))
188         return false;
189
190     return true;
191 }
192
193 struct Style {
194     Style(const RenderStyle& style)
195         : font(style.font())
196         , textAlign(style.textAlign())
197         , collapseWhitespace(style.collapseWhiteSpace())
198         , preserveNewline(style.preserveNewline())
199         , wrapLines(style.autoWrap())
200         , breakWordOnOverflow(style.overflowWrap() == BreakOverflowWrap && (wrapLines || preserveNewline))
201         , spaceWidth(font.width(TextRun(&space, 1)))
202         , tabWidth(collapseWhitespace ? 0 : style.tabSize())
203     {
204     }
205     const Font& font;
206     ETextAlign textAlign;
207     bool collapseWhitespace;
208     bool preserveNewline;
209     bool wrapLines;
210     bool breakWordOnOverflow;
211     float spaceWidth;
212     unsigned tabWidth;
213 };
214
215 static float computeLineLeft(ETextAlign textAlign, float availableWidth, float committedWidth, float logicalLeftOffset)
216 {
217     float remainingWidth = availableWidth - committedWidth;
218     float left = logicalLeftOffset;
219     switch (textAlign) {
220     case LEFT:
221     case WEBKIT_LEFT:
222     case TASTART:
223         return left;
224     case RIGHT:
225     case WEBKIT_RIGHT:
226     case TAEND:
227         return left + std::max<float>(remainingWidth, 0);
228     case CENTER:
229     case WEBKIT_CENTER:
230         return left + std::max<float>(remainingWidth / 2, 0);
231     case JUSTIFY:
232         ASSERT_NOT_REACHED();
233         break;
234     }
235     ASSERT_NOT_REACHED();
236     return 0;
237 }
238
239 struct TextFragment {
240     TextFragment()
241         : start(0)
242         , isCollapsedWhitespace(false)
243         , end(0)
244         , isWhitespaceOnly(false)
245         , isBreakable(false)
246         , mustBreak(false)
247         , width(0)
248     {
249     }
250
251     TextFragment(unsigned textStart, unsigned textEnd, float textWidth, bool isWhitespaceOnly)
252         : start(textStart)
253         , isCollapsedWhitespace(false)
254         , end(textEnd)
255         , isWhitespaceOnly(isWhitespaceOnly)
256         , isBreakable(false)
257         , mustBreak(false)
258         , width(textWidth)
259     {
260     }
261
262     bool isEmpty() const
263     {
264         return start == end;
265     }
266
267     unsigned start : 31;
268     bool isCollapsedWhitespace : 1;
269     unsigned end : 31;
270     bool isWhitespaceOnly : 1;
271     bool isBreakable;
272     bool mustBreak;
273     float width;
274 };
275
276 struct LineState {
277     LineState()
278         : availableWidth(0)
279         , logicalLeftOffset(0)
280         , lineStartRunIndex(0)
281         , uncommittedStart(0)
282         , uncommittedEnd(0)
283         , uncommittedWidth(0)
284         , committedWidth(0)
285         , committedLogicalRight(0)
286         , position(0)
287         , trailingWhitespaceWidth(0)
288     {
289     }
290
291     void commitAndCreateRun(Layout::RunVector& lineRuns)
292     {
293         if (uncommittedStart == uncommittedEnd)
294             return;
295
296         lineRuns.append(Run(uncommittedStart, uncommittedEnd, committedLogicalRight, committedLogicalRight + uncommittedWidth, false));
297         // Move uncommitted to committed.
298         committedWidth += uncommittedWidth;
299         committedLogicalRight += committedWidth;
300
301         uncommittedStart = uncommittedEnd;
302         uncommittedWidth = 0;
303     }
304
305     void addUncommitted(const TextFragment& fragment)
306     {
307         unsigned uncomittedFragmentLength = fragment.end - uncommittedEnd;
308         uncommittedWidth += fragment.width;
309         uncommittedEnd = fragment.end;
310         position = uncommittedEnd;
311         trailingWhitespaceWidth = fragment.isWhitespaceOnly ? fragment.width : 0;
312         trailingWhitespaceLength = fragment.isWhitespaceOnly ? uncomittedFragmentLength  : 0;
313     }
314
315     void addUncommittedWhitespace(float whitespaceWidth)
316     {
317         addUncommitted(TextFragment(uncommittedEnd, uncommittedEnd + 1, whitespaceWidth, true));
318     }
319
320     void jumpTo(unsigned newPositon, float logicalRight)
321     {
322         position = newPositon;
323
324         uncommittedStart = newPositon;
325         uncommittedEnd = newPositon;
326         uncommittedWidth = 0;
327         committedLogicalRight = logicalRight;
328     }
329
330     float width() const
331     {
332         return committedWidth + uncommittedWidth;
333     }
334
335     bool fits(float extra) const
336     {
337         return availableWidth >= width() + extra;
338     }
339
340     void removeCommittedTrailingWhitespace()
341     {
342         ASSERT(!uncommittedWidth);
343         committedWidth -= trailingWhitespaceWidth;
344         committedLogicalRight -= trailingWhitespaceWidth;
345     }
346
347     void resetTrailingWhitespace()
348     {
349         trailingWhitespaceWidth = 0;
350         trailingWhitespaceLength = 0;
351     }
352
353     float availableWidth;
354     float logicalLeftOffset;
355     unsigned lineStartRunIndex; // The run that the line starts with.
356
357     unsigned uncommittedStart;
358     unsigned uncommittedEnd;
359     float uncommittedWidth;
360     float committedWidth;
361     float committedLogicalRight; // Last committed X (coordinate) position.
362
363     unsigned position;
364
365     float trailingWhitespaceWidth; // Use this to remove trailing whitespace without re-mesuring the text.
366     float trailingWhitespaceLength;
367
368     TextFragment oveflowedFragment;
369 };
370
371 static void removeTrailingWhitespace(LineState& lineState, Layout::RunVector& lineRuns, const FlowContents& flowContents)
372 {
373     const auto& style = flowContents.style();
374     bool preWrap = style.wrapLines && !style.collapseWhitespace;
375     // Trailing whitespace gets removed when we either collapse whitespace or pre-wrap is present.
376     if (!(style.collapseWhitespace || preWrap)) {
377         lineState.resetTrailingWhitespace();
378         return;
379     }
380
381     ASSERT(lineRuns.size());
382     Run& lastRun = lineRuns.last();
383
384     unsigned lastPosition = lineState.position;
385     bool trailingPreWrapWhitespaceNeedsToBeRemoved = false;
386     // When pre-wrap is present, trailing whitespace needs to be removed:
387     // 1. from the "next line": when at least the first charater fits. When even the first whitespace is wider that the available width,
388     // we don't remove any whitespace at all.
389     // 2. from this line: remove whitespace, unless it's the only fragment on the line -so removing the whitesapce would produce an empty line.
390     if (preWrap) {
391         if (lineState.oveflowedFragment.isWhitespaceOnly && !lineState.oveflowedFragment.isEmpty() && lineState.availableWidth >= lineState.committedWidth) {
392             lineState.position = lineState.oveflowedFragment.end;
393             lineState.oveflowedFragment = TextFragment();
394         }
395         if (lineState.trailingWhitespaceLength) {
396             // Check if we've got only whitespace on this line.
397             trailingPreWrapWhitespaceNeedsToBeRemoved = !(lineState.committedWidth == lineState.trailingWhitespaceWidth);
398         }
399     }
400     if (lineState.trailingWhitespaceLength && (style.collapseWhitespace || trailingPreWrapWhitespaceNeedsToBeRemoved)) {
401         lastRun.logicalRight -= lineState.trailingWhitespaceWidth;
402         lastRun.end -= lineState.trailingWhitespaceLength;
403         if (lastRun.start == lastRun.end)
404             lineRuns.removeLast();
405         lineState.removeCommittedTrailingWhitespace();
406     }
407
408     // 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.
409     if (lastPosition != lineState.position && style.preserveNewline && !flowContents.isEndOfContent(lineState.position) && flowContents.isNewlineCharacter(lineState.position))
410         ++lineState.position;
411 }
412
413 static void initializeNewLine(LineState& lineState, const FlowContents& flowContents, unsigned lineStartRunIndex)
414 {
415     lineState.lineStartRunIndex = lineStartRunIndex;
416     // Skip leading whitespace if collapsing whitespace, unless there's an uncommitted fragment pushed from the previous line.
417     // FIXME: Be smarter when the run from the previous line does not fit the current line. Right now, we just reprocess it.
418     if (lineState.oveflowedFragment.width) {
419         if (lineState.fits(lineState.oveflowedFragment.width))
420             lineState.addUncommitted(lineState.oveflowedFragment);
421         else
422             lineState.jumpTo(lineState.oveflowedFragment.start, 0); // Start over with this fragment.
423     } else {
424         unsigned spaceCount = 0;
425         lineState.jumpTo(flowContents.style().collapseWhitespace ? flowContents.findNextNonWhitespacePosition(lineState.position, spaceCount) : lineState.position, 0);
426     }
427     lineState.oveflowedFragment = TextFragment();
428 }
429
430 static TextFragment splitFragmentToFitLine(TextFragment& fragmentToSplit, float availableWidth, bool keepAtLeastOneCharacter, const FlowContents& flowContents)
431 {
432     // Fast path for single char fragments.
433     if (fragmentToSplit.start + 1 == fragmentToSplit.end) {
434         if (keepAtLeastOneCharacter)
435             return TextFragment();
436
437         TextFragment fragmentForNextLine(fragmentToSplit);
438         fragmentToSplit.end = fragmentToSplit.start;
439         fragmentToSplit.width = 0;
440         return fragmentForNextLine;
441     }
442     // Simple binary search to find out what fits the current line.
443     // FIXME: add surrogate pair support.
444     unsigned left = fragmentToSplit.start;
445     unsigned right = fragmentToSplit.end - 1; // We can ignore the last character. It surely does not fit.
446     float width = 0;
447     while (left < right) {
448         unsigned middle = (left + right) / 2;
449         width = flowContents.textWidth(fragmentToSplit.start, middle + 1, 0);
450         if (availableWidth > width)
451             left = middle + 1;
452         else if (availableWidth < width)
453             right = middle;
454         else {
455             right = middle + 1;
456             break;
457         }
458     }
459
460     if (keepAtLeastOneCharacter && right == fragmentToSplit.start)
461         ++right;
462     TextFragment fragmentForNextLine(fragmentToSplit);
463     fragmentToSplit.end = right;
464     fragmentToSplit.width = fragmentToSplit.isEmpty() ? 0 : flowContents.textWidth(fragmentToSplit.start, right, 0);
465
466     fragmentForNextLine.start = fragmentToSplit.end;
467     fragmentForNextLine.width -= fragmentToSplit.width;
468     return fragmentForNextLine;
469 }
470
471 static TextFragment nextFragment(unsigned previousFragmentEnd, const FlowContents& flowContents, float xPosition)
472 {
473     // A fragment can have
474     // 1. new line character when preserveNewline is on (not considered as whitespace) or
475     // 2. whitespace (collasped, non-collapsed multi or single) or
476     // 3. non-whitespace characters.
477     const auto& style = flowContents.style();
478     TextFragment fragment;
479     fragment.mustBreak = style.preserveNewline && flowContents.isNewlineCharacter(previousFragmentEnd);
480     unsigned spaceCount = 0;
481     unsigned whitespaceEnd = previousFragmentEnd;
482     if (!fragment.mustBreak)
483         whitespaceEnd = flowContents.findNextNonWhitespacePosition(previousFragmentEnd, spaceCount);
484     fragment.isWhitespaceOnly = previousFragmentEnd < whitespaceEnd;
485     fragment.start = previousFragmentEnd;
486     if (fragment.isWhitespaceOnly)
487         fragment.end = whitespaceEnd;
488     else if (fragment.mustBreak)
489         fragment.end = fragment.start + 1;
490     else
491         fragment.end = flowContents.findNextBreakablePosition(previousFragmentEnd + 1);
492     bool multiple = fragment.start + 1 < fragment.end;
493     fragment.isCollapsedWhitespace = multiple && fragment.isWhitespaceOnly && style.collapseWhitespace;
494     // Non-collapsed whitespace or just plain words when "break word on overflow" is on can wrap.
495     fragment.isBreakable = multiple && ((fragment.isWhitespaceOnly && !fragment.isCollapsedWhitespace) || (!fragment.isWhitespaceOnly && style.breakWordOnOverflow));
496
497     // Compute fragment width or just use the pre-computed whitespace widths.
498     unsigned fragmentLength = fragment.end - fragment.start;
499     if (fragment.isCollapsedWhitespace)
500         fragment.width = style.spaceWidth;
501     else if (fragment.mustBreak)
502         fragment.width = 0; // Newline character's width is 0.
503     else if (fragmentLength == spaceCount) // Space only.
504         fragment.width = style.spaceWidth * spaceCount;
505     else
506         fragment.width = flowContents.textWidth(fragment.start, fragment.end, xPosition);
507     return fragment;
508 }
509
510 static bool createLineRuns(LineState& lineState, Layout::RunVector& lineRuns, const FlowContents& flowContents)
511 {
512     const auto& style = flowContents.style();
513     bool lineCanBeWrapped = style.wrapLines || style.breakWordOnOverflow;
514     while (!flowContents.isEndOfContent(lineState.position)) {
515         // Find the next text fragment. Start from the end of the previous fragment -current line end.
516         TextFragment fragment = nextFragment(lineState.position, flowContents, lineState.width());
517         if ((lineCanBeWrapped && !lineState.fits(fragment.width)) || fragment.mustBreak) {
518             // Overflow wrapping behaviour:
519             // 1. Newline character: wraps the line unless it's treated as whitespace.
520             // 2. Whitesapce collapse on: whitespace is skipped.
521             // 3. Whitespace collapse off: whitespace is wrapped.
522             // 4. First, non-whitespace fragment is either wrapped or kept on the line. (depends on overflow-wrap)
523             // 5. Non-whitespace fragment when there's already another fragment on the line gets pushed to the next line.
524             bool isFirstFragment = !lineState.width();
525             if (fragment.mustBreak) {
526                 if (isFirstFragment)
527                     lineState.addUncommitted(fragment);
528                 else {
529                     // No need to add the new line fragment if there's already content on the line. We are about to close this line anyway.
530                     ++lineState.position;
531                 }
532             } else if (style.collapseWhitespace && fragment.isWhitespaceOnly) {
533                 // Whitespace collapse is on: whitespace that doesn't fit is simply skipped.
534                 lineState.position = fragment.end;
535             } else if (fragment.isWhitespaceOnly || ((isFirstFragment && style.breakWordOnOverflow) || !style.wrapLines)) { // !style.wrapLines: bug138102(preserve existing behavior)
536                 // Whitespace collapse is off or non-whitespace content. split the fragment; (modified)fragment -> this lineState, oveflowedFragment -> next line.
537                 // When this is the only (first) fragment, the first character stays on the line, even if it does not fit.
538                 lineState.oveflowedFragment = splitFragmentToFitLine(fragment, lineState.availableWidth - lineState.width(), isFirstFragment, flowContents);
539                 if (!fragment.isEmpty()) {
540                     // Whitespace fragments can get pushed entirely to the next line.
541                     lineState.addUncommitted(fragment);
542                 }
543             } else if (isFirstFragment) {
544                 // Non-breakable non-whitespace first fragment. Add it to the current line. -it overflows though.
545                 lineState.addUncommitted(fragment);
546             } else {
547                 // Non-breakable non-whitespace fragment when there's already a fragment on the line. Push it to the next line.
548                 lineState.oveflowedFragment = fragment;
549             }
550             break;
551         }
552         // When the current fragment is collapsed whitespace, we need to create a run for what we've processed so far.
553         if (fragment.isCollapsedWhitespace) {
554             // One trailing whitespace to preserve.
555             lineState.addUncommittedWhitespace(style.spaceWidth);
556             lineState.commitAndCreateRun(lineRuns);
557             // And skip the collapsed whitespace.
558             lineState.jumpTo(fragment.end, lineState.width() + fragment.width - style.spaceWidth);
559         } else
560             lineState.addUncommitted(fragment);
561     }
562     lineState.commitAndCreateRun(lineRuns);
563     return flowContents.isEndOfContent(lineState.position) && lineState.oveflowedFragment.isEmpty();
564 }
565
566 static void closeLineEndingAndAdjustRuns(LineState& lineState, Layout::RunVector& lineRuns, unsigned& lineCount, const FlowContents& flowContents)
567 {
568     if (lineState.lineStartRunIndex == lineRuns.size())
569         return;
570
571     ASSERT(lineRuns.size());
572     removeTrailingWhitespace(lineState, lineRuns, flowContents);
573     // Adjust runs' position by taking line's alignment into account.
574     if (float lineLogicalLeft = computeLineLeft(flowContents.style().textAlign, lineState.availableWidth, lineState.committedWidth, lineState.logicalLeftOffset)) {
575         for (unsigned i = lineState.lineStartRunIndex; i < lineRuns.size(); ++i) {
576             lineRuns[i].logicalLeft += lineLogicalLeft;
577             lineRuns[i].logicalRight += lineLogicalLeft;
578         }
579     }
580     lineRuns.last().isEndOfLine = true;
581     lineState.committedWidth = 0;
582     lineState.committedLogicalRight = 0;
583     ++lineCount;
584 }
585
586 static void splitRunsAtRendererBoundary(Layout::RunVector& lineRuns, const FlowContents& flowContents)
587 {
588     if (!lineRuns.size())
589         return;
590
591     unsigned runIndex = 0;
592     do {
593         const Run& run = lineRuns.at(runIndex);
594         ASSERT(run.start != run.end);
595         const RenderText* startRenderer = flowContents.renderer(run.start);
596         const RenderText* endRenderer = flowContents.renderer(run.end - 1);
597         if (startRenderer == endRenderer)
598             continue;
599         // This run overlaps multiple renderers. Split it up.
600         unsigned rendererStartPosition = 0;
601         unsigned rendererEndPosition = 0;
602         bool found = flowContents.resolveRendererPositions(*startRenderer, rendererStartPosition, rendererEndPosition);
603         ASSERT_UNUSED(found, found);
604
605         // 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.
606         float logicalRightOfLeftRun = run.logicalLeft + flowContents.textWidth(run.start, rendererEndPosition, run.logicalLeft);
607         lineRuns.insert(runIndex, Run(run.start, rendererEndPosition, run.logicalLeft, logicalRightOfLeftRun, false));
608         Run& rightSideRun = lineRuns.at(runIndex + 1);
609         rightSideRun.start = rendererEndPosition;
610         rightSideRun.logicalLeft = logicalRightOfLeftRun;
611     } while (++runIndex < lineRuns.size());
612 }
613
614 static void updateLineConstrains(const RenderBlockFlow& flow, float& availableWidth, float& logicalLeftOffset)
615 {
616     LayoutUnit height = flow.logicalHeight();
617     LayoutUnit logicalHeight = flow.minLineHeightForReplacedRenderer(false, 0);
618     float logicalRightOffset = flow.logicalRightOffsetForLine(height, false, logicalHeight);
619     logicalLeftOffset = flow.logicalLeftOffsetForLine(height, false, logicalHeight);
620     availableWidth = std::max<float>(0, logicalRightOffset - logicalLeftOffset);
621 }
622
623 static void createTextRuns(Layout::RunVector& runs, RenderBlockFlow& flow, unsigned& lineCount)
624 {
625     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
626     LayoutUnit lineHeight = lineHeightFromFlow(flow);
627     LineState lineState;
628     bool isEndOfContent = false;
629     FlowContents flowContents = FlowContents(flow);
630
631     do {
632         flow.setLogicalHeight(lineHeight * lineCount + borderAndPaddingBefore);
633         updateLineConstrains(flow, lineState.availableWidth, lineState.logicalLeftOffset);
634         initializeNewLine(lineState, flowContents, runs.size());
635         isEndOfContent = createLineRuns(lineState, runs, flowContents);
636         closeLineEndingAndAdjustRuns(lineState, runs, lineCount, flowContents);
637     } while (!isEndOfContent);
638
639     if (flow.firstChild() != flow.lastChild())
640         splitRunsAtRendererBoundary(runs, flowContents);
641     ASSERT(!lineState.uncommittedWidth);
642 }
643
644 std::unique_ptr<Layout> create(RenderBlockFlow& flow)
645 {
646     unsigned lineCount = 0;
647     Layout::RunVector runs;
648
649     createTextRuns(runs, flow, lineCount);
650     for (auto& renderer : childrenOfType<RenderObject>(flow)) {
651         ASSERT(is<RenderText>(renderer));
652         renderer.clearNeedsLayout();
653     }
654     return Layout::create(runs, lineCount);
655 }
656
657 std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
658 {
659     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
660     return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
661 }
662
663 Layout::Layout(const RunVector& runVector, unsigned lineCount)
664     : m_lineCount(lineCount)
665     , m_runCount(runVector.size())
666 {
667     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
668 }
669
670 }
671 }