[LCF][IFC] Add support for hyphenation.
[WebKit-https.git] / Source / WebCore / layout / inlineformatting / textlayout / simple / SimpleLineBreaker.cpp
1 /*
2  * Copyright (C) 2018 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 "SimpleLineBreaker.h"
28
29 #if ENABLE(LAYOUT_FORMATTING_CONTEXT)
30
31 #include "FontCascade.h"
32 #include "Hyphenation.h"
33 #include "InlineFormattingContext.h"
34 #include "LayoutContext.h"
35 #include "RenderStyle.h"
36 #include "TextContentProvider.h"
37 #include <wtf/IsoMallocInlines.h>
38
39 namespace WebCore {
40 namespace Layout {
41
42 WTF_MAKE_ISO_ALLOCATED_IMPL(SimpleLineBreaker);
43
44 struct TextRunSplitPair {
45     TextRun left;
46     TextRun right;
47 };
48
49 SimpleLineBreaker::TextRunList::TextRunList(const Vector<TextRun>& textRuns)
50     : m_textRuns(textRuns)
51 {
52 }
53
54 SimpleLineBreaker::Line::Line(Vector<LayoutRun>& layoutRuns)
55     : m_layoutRuns(layoutRuns)
56     , m_firstRunIndex(m_layoutRuns.size())
57 {
58 }
59
60 static inline unsigned adjustedEndPosition(const TextRun& textRun)
61 {
62     if (textRun.isCollapsed())
63         return textRun.start() + 1;
64     return textRun.end();
65 }
66
67 void SimpleLineBreaker::Line::setTextAlign(TextAlignMode textAlign)
68 {
69     m_style.textAlign = textAlign;
70     m_collectExpansionOpportunities = textAlign == TextAlignMode::Justify;
71 }
72
73 float SimpleLineBreaker::Line::adjustedLeftForTextAlign(TextAlignMode textAlign) const
74 {
75     float remainingWidth = availableWidth();
76     float left = m_left;
77     switch (textAlign) {
78     case TextAlignMode::Left:
79     case TextAlignMode::WebKitLeft:
80     case TextAlignMode::Start:
81         return left;
82     case TextAlignMode::Right:
83     case TextAlignMode::WebKitRight:
84     case TextAlignMode::End:
85         return left + std::max<float>(remainingWidth, 0);
86     case TextAlignMode::Center:
87     case TextAlignMode::WebKitCenter:
88         return left + std::max<float>(remainingWidth / 2, 0);
89     case TextAlignMode::Justify:
90         ASSERT_NOT_REACHED();
91         break;
92     }
93     ASSERT_NOT_REACHED();
94     return left;
95 }
96
97 void SimpleLineBreaker::Line::justifyRuns()
98 {
99     auto widthToDistribute = availableWidth();
100     if (widthToDistribute <= 0)
101         return;
102
103     unsigned expansionOpportunities = 0;
104     for (auto& expansionEntry : m_expansionOpportunityList)
105         expansionOpportunities += expansionEntry.count;
106
107     if (!expansionOpportunities)
108         return;
109
110     auto expansion = widthToDistribute / expansionOpportunities;
111     float accumulatedExpansion = 0;
112     unsigned runIndex = m_firstRunIndex;
113     for (auto& expansionEntry : m_expansionOpportunityList) {
114         if (runIndex >= m_layoutRuns.size()) {
115             ASSERT_NOT_REACHED();
116             return;
117         }
118         auto& layoutRun = m_layoutRuns.at(runIndex++);
119         auto expansionForRun = expansionEntry.count * expansion;
120
121         layoutRun.setExpansion(expansionEntry.behavior, expansionForRun);
122         layoutRun.setLeft(layoutRun.left() + accumulatedExpansion);
123         layoutRun.setRight(layoutRun.right() + accumulatedExpansion + expansionForRun);
124         accumulatedExpansion += expansionForRun;
125     }
126 }
127
128 void SimpleLineBreaker::Line::adjustRunsForTextAlign(bool lastLine)
129 {
130     // Fallback to TextAlignMode::Left (START) alignment for non-collapsable content or for the last line before a forced break/the end of the block.
131     auto textAlign = m_style.textAlign;
132     if (textAlign == TextAlignMode::Justify && (!m_style.collapseWhitespace || lastLine))
133         textAlign = TextAlignMode::Left;
134
135     if (textAlign == TextAlignMode::Justify) {
136         justifyRuns();
137         return;
138     }
139
140     auto adjustedLeft = adjustedLeftForTextAlign(textAlign);
141     if (adjustedLeft == m_left)
142         return;
143
144     for (auto i = m_firstRunIndex; i < m_layoutRuns.size(); ++i) {
145         auto& layoutRun = m_layoutRuns.at(i);
146         layoutRun.setLeft(layoutRun.left() + adjustedLeft);
147         layoutRun.setRight(layoutRun.right() + adjustedLeft);
148     }
149 }
150
151 static bool expansionOpportunity(TextRun::Type current, TextRun::Type previous)
152 {
153     return current == TextRun::Type::Whitespace || (current == TextRun::Type::NonWhitespace && previous == TextRun::Type::NonWhitespace);
154 }
155
156 static ExpansionBehavior expansionBehavior(bool isAtExpansionOpportunity)
157 {
158     ExpansionBehavior expansionBehavior = AllowTrailingExpansion;
159     expansionBehavior |= isAtExpansionOpportunity ? ForbidLeadingExpansion : AllowLeadingExpansion;
160     return expansionBehavior;
161 }
162
163 void SimpleLineBreaker::Line::collectExpansionOpportunities(const TextRun& textRun, bool textRunCreatesNewLayoutRun)
164 {
165     if (textRunCreatesNewLayoutRun) {
166         // Create an entry for this new layout run.
167         m_expansionOpportunityList.append({ });
168     }
169
170     if (!textRun.length())
171         return;
172
173     auto isAtExpansionOpportunity = expansionOpportunity(textRun.type(), m_lastTextRun ? m_lastTextRun->type() : TextRun::Type::Invalid);
174     m_expansionOpportunityList.last().behavior = expansionBehavior(isAtExpansionOpportunity);
175     if (isAtExpansionOpportunity)
176         ++m_expansionOpportunityList.last().count;
177
178     if (textRun.isNonWhitespace())
179         m_lastNonWhitespaceExpansionOppportunity = m_expansionOpportunityList.last();
180 }
181
182 void SimpleLineBreaker::Line::closeLastRun()
183 {
184     if (!m_layoutRuns.size())
185         return;
186
187     m_layoutRuns.last().setIsEndOfLine();
188
189     // Forbid trailing expansion for the last run on line.
190     if (!m_collectExpansionOpportunities || m_expansionOpportunityList.isEmpty())
191         return;
192
193     auto& lastExpansionEntry = m_expansionOpportunityList.last();
194     auto expansionBehavior = lastExpansionEntry.behavior;
195     // Remove allow and add forbid.
196     expansionBehavior ^= AllowTrailingExpansion;
197     expansionBehavior |= ForbidTrailingExpansion;
198     lastExpansionEntry.behavior = expansionBehavior;
199 }
200
201 void SimpleLineBreaker::Line::append(const TextRun& textRun)
202 {
203     auto start = textRun.start();
204     auto end = adjustedEndPosition(textRun);
205     auto previousLogicalRight = m_left + m_runsWidth;
206     bool textRunCreatesNewLayoutRun = !m_lastTextRun || m_lastTextRun->isCollapsed();
207
208     m_runsWidth += textRun.width();
209     if (textRun.isNonWhitespace()) {
210         m_trailingWhitespaceWidth = 0;
211         m_lastNonWhitespaceTextRun = textRun;
212     } else if (textRun.isWhitespace())
213         m_trailingWhitespaceWidth += textRun.width();
214
215     if (m_collectExpansionOpportunities)
216         collectExpansionOpportunities(textRun, textRunCreatesNewLayoutRun);
217
218     // New line needs new run.
219     if (textRunCreatesNewLayoutRun)
220         m_layoutRuns.append({ start, end, previousLogicalRight, previousLogicalRight + textRun.width(), textRun.hasHyphen() });
221     else {
222         auto& lastRun = m_layoutRuns.last();
223         lastRun.setEnd(end);
224         lastRun.setRight(lastRun.right() + textRun.width());
225         if (textRun.hasHyphen())
226             lastRun.setHasHyphen();
227     }
228
229     m_lastTextRun = textRun;
230 }
231
232 void SimpleLineBreaker::Line::collapseTrailingWhitespace()
233 {
234     if (!m_lastTextRun || !m_lastTextRun->isWhitespace())
235         return;
236
237     if (!m_lastNonWhitespaceTextRun) {
238         // This essentially becomes an empty line.
239         reset();
240         return;
241     }
242
243     m_runsWidth -= m_trailingWhitespaceWidth;
244     m_lastTextRun = m_lastNonWhitespaceTextRun;
245
246     while (m_trailingWhitespaceWidth) {
247         auto& lastLayoutRun = m_layoutRuns.last();
248
249         if (lastLayoutRun.end() <= m_lastNonWhitespaceTextRun->end())
250             break;
251
252         // Full remove.
253         if (lastLayoutRun.start() >= m_lastNonWhitespaceTextRun->end()) {
254             m_trailingWhitespaceWidth -= lastLayoutRun.width();
255             m_layoutRuns.removeLast();
256             continue;
257         }
258         // Partial remove.
259         lastLayoutRun.setRight(lastLayoutRun.right() - m_trailingWhitespaceWidth);
260         lastLayoutRun.setEnd(m_lastNonWhitespaceTextRun->end());
261         m_trailingWhitespaceWidth = 0;
262     }
263
264     if (m_collectExpansionOpportunities) {
265         ASSERT(m_lastNonWhitespaceExpansionOppportunity);
266         ASSERT(!m_expansionOpportunityList.isEmpty());
267         m_expansionOpportunityList.last() = *m_lastNonWhitespaceExpansionOppportunity;
268     }
269 }
270
271 void SimpleLineBreaker::Line::reset()
272 {
273     m_runsWidth = 0;
274     m_firstRunIndex = m_layoutRuns.size();
275     m_availableWidth = 0;
276     m_trailingWhitespaceWidth  = 0;
277     m_expansionOpportunityList.clear();
278     m_lastNonWhitespaceExpansionOppportunity = { };
279     m_lastTextRun = std::nullopt;
280     m_lastNonWhitespaceTextRun = std::nullopt;
281 }
282
283 // FIXME: Use variable style based on the current text run.
284 SimpleLineBreaker::Style::Style(const RenderStyle& style)
285     : font(style.fontCascade())
286     , wrapLines(style.autoWrap())
287     , breakAnyWordOnOverflow(style.wordBreak() == WordBreak::BreakAll && wrapLines)
288     , breakFirstWordOnOverflow(breakAnyWordOnOverflow || (style.breakWords() && (wrapLines || style.preserveNewline())))
289     , collapseWhitespace(style.collapseWhiteSpace())
290     , preWrap(wrapLines && !collapseWhitespace)
291     , preserveNewline(style.preserveNewline())
292     , textAlign(style.textAlign())
293     , shouldHyphenate(style.hyphens() == Hyphens::Auto && canHyphenate(style.locale()))
294     , hyphenStringWidth(shouldHyphenate ? font.width(WebCore::TextRun(String(style.hyphenString()))) : 0)
295     , hyphenLimitBefore(style.hyphenationLimitBefore() < 0 ? 2 : style.hyphenationLimitBefore())
296     , hyphenLimitAfter(style.hyphenationLimitAfter() < 0 ? 2 : style.hyphenationLimitAfter())
297     , locale(style.locale())
298 {
299     if (style.hyphenationLimitLines() > -1)
300         hyphenLimitLines = style.hyphenationLimitLines();
301 }
302
303 SimpleLineBreaker::SimpleLineBreaker(const Vector<TextRun>& textRuns, const TextContentProvider& contentProvider, LineConstraintList&& lineConstraintList, const RenderStyle& style)
304     : m_contentProvider(contentProvider)
305     , m_style(style)
306     , m_textRunList(textRuns)
307     , m_currentLine(m_layoutRuns)
308     , m_lineConstraintList(WTFMove(lineConstraintList))
309     , m_lineConstraintIterator(m_lineConstraintList)
310 {
311     ASSERT(m_lineConstraintList.size());
312     // Since the height of the content is undefined, the last vertical position in the constraint list should always be infinite.
313     ASSERT(!m_lineConstraintList.last().verticalPosition);
314 }
315
316 Vector<LayoutRun> SimpleLineBreaker::runs()
317 {
318     while (m_textRunList.current()) {
319         handleLineStart();
320         createRunsForLine();
321         handleLineEnd();
322     }
323
324     return m_layoutRuns;
325 }
326
327 void SimpleLineBreaker::handleLineEnd()
328 {
329     auto lineHasContent = m_currentLine.hasContent();
330     if (lineHasContent) {
331         ASSERT(m_layoutRuns.size());
332         ++m_numberOfLines;
333         m_currentLine.closeLastRun();
334
335         auto lastLine = !m_textRunList.current();
336         m_currentLine.adjustRunsForTextAlign(lastLine);
337     }
338     // Check if we need to disable hyphenation.
339     if (m_style.hyphenLimitLines) {
340         if (!lineHasContent || (m_layoutRuns.size() && !m_layoutRuns.last().hasHyphen()))
341             m_numberOfPrecedingLinesWithHyphen = 0;
342         else
343             ++m_numberOfPrecedingLinesWithHyphen;
344         m_hyphenationIsDisabled = m_numberOfPrecedingLinesWithHyphen >= *m_style.hyphenLimitLines;
345     }
346
347     m_previousLineHasNonForcedContent = lineHasContent && m_currentLine.availableWidth() >= 0;
348     m_currentLine.reset();
349 }
350
351 void SimpleLineBreaker::handleLineStart()
352 {
353     auto lineConstraint = this->lineConstraint(verticalPosition());
354     m_currentLine.setLeft(lineConstraint.left);
355     m_currentLine.setTextAlign(m_style.textAlign);
356     m_currentLine.setCollapseWhitespace(m_style.collapseWhitespace);
357     m_currentLine.setAvailableWidth(lineConstraint.right - lineConstraint.left);
358 }
359
360 static bool isTextAlignRight(TextAlignMode textAlign)
361 {
362     return textAlign == TextAlignMode::Right || textAlign == TextAlignMode::WebKitRight;
363 }
364
365 void SimpleLineBreaker::createRunsForLine()
366 {
367     collapseLeadingWhitespace();
368
369     while (auto textRun = m_textRunList.current()) {
370
371         if (!textRun->isLineBreak() && (!wrapContentOnOverflow() || m_currentLine.availableWidth() >= textRun->width())) {
372             m_currentLine.append(*textRun);
373             ++m_textRunList;
374             continue;
375         }
376
377         // This run is either a linebreak or it does not fit the current line.
378         if (textRun->isLineBreak()) {
379             // Add the new line only if there's nothing on the line. (otherwise the extra new line character would show up at the end of the content.)
380             if (textRun->isHardLineBreak() || !m_currentLine.hasContent()) {
381                 if (isTextAlignRight(m_style.textAlign))
382                     m_currentLine.collapseTrailingWhitespace();
383                 m_currentLine.append(*textRun);
384             }
385             ++m_textRunList;
386             break;
387         }
388
389         // Overflow wrapping behaviour:
390         // 1. Whitesapce collapse on: whitespace is skipped. Jump to next line.
391         // 2. Whitespace collapse off: whitespace is wrapped.
392         // 3. First, non-whitespace run is either wrapped or kept on the line. (depends on overflow-wrap)
393         // 4. Non-whitespace run when there's already another run on the line either gets wrapped (word-break: break-all) or gets pushed to the next line.
394
395         // Whitespace run.
396         if (textRun->isWhitespace()) {
397             // Process collapsed whitespace again for the next line.
398             if (textRun->isCollapsed())
399                 break;
400             // Try to split the whitespace; left part stays on this line, right is pushed to next line.
401             if (!splitTextRun(*textRun))
402                 ++m_textRunList;
403             break;
404         }
405
406         // Non-whitespace run. (!style.wrapLines: bug138102(preserve existing behavior)
407         if (((!m_currentLine.hasContent() && m_style.breakFirstWordOnOverflow) || m_style.breakAnyWordOnOverflow) || !m_style.wrapLines) {
408             // Try to split the run; left side stays on this line, right side is pushed to next line.
409             if (!splitTextRun(*textRun))
410                 ++m_textRunList;
411             break;
412         }
413
414         ASSERT(textRun->isNonWhitespace());
415         // Find out if this non-whitespace fragment has a hyphen where we can break.
416         if (m_style.shouldHyphenate && !m_hyphenationIsDisabled) {
417             if (!splitTextRun(*textRun)) {
418                 ++m_textRunList;
419                 break;
420             }
421         }
422
423         // Non-breakable non-whitespace first run. Add it to the current line. -it overflows though.
424         if (!m_currentLine.hasContent()) {
425             handleOverflownRun();
426             break;
427         }
428         // Non-breakable non-whitespace run when there's already content on the line. Process it on the next line.
429         break;
430     }
431
432     collapseTrailingWhitespace();
433 }
434
435 void SimpleLineBreaker::handleOverflownRun()
436 {
437     auto textRun = m_textRunList.current();
438     ASSERT(textRun);
439
440     m_currentLine.append(*textRun);
441     ++m_textRunList;
442
443     // If the forced run is followed by a line break, we need to process it on this line, otherwise the next line would start with a line break (double line break).
444     // "foobarlongtext<br>foobar" should produce
445     // foobarlongtext
446     // foobar
447     // and not
448     // foobarlongtext
449     //
450     // foobar
451
452     // First check for collapsable whitespace.
453     textRun = m_textRunList.current();
454     if (!textRun)
455         return;
456
457     if (textRun->isWhitespace() && m_style.collapseWhitespace) {
458         ++m_textRunList;
459         textRun = m_textRunList.current();
460         if (!textRun)
461             return;
462     }
463
464     if (textRun->isHardLineBreak()) {
465         // <br> always produces a run. (required by testing output)
466         m_currentLine.append(*textRun);
467         ++m_textRunList;
468         return;
469     }
470
471     if (textRun->isSoftLineBreak() && !m_style.preserveNewline)
472         ++m_textRunList;
473 }
474
475 void SimpleLineBreaker::collapseLeadingWhitespace()
476 {
477     auto textRun = m_textRunList.current();
478     if (!textRun || !textRun->isWhitespace())
479         return;
480
481     // Special overflow pre-wrap whitespace/newline handling for overflow whitespace: skip the leading whitespace/newline (even when style says not-collapsible)
482     // if we managed to put some content on the previous line.
483     if (m_textRunList.isCurrentOverridden()) {
484         auto collapseWhitespace = m_style.collapseWhitespace || m_style.preWrap;
485         if (collapseWhitespace && m_previousLineHasNonForcedContent) {
486             ++m_textRunList;
487             // If collapsing the whitespace puts us on a newline, skip the soft newline too as we already wrapped the line.
488             textRun = m_textRunList.current();
489             // <br> always produces a run. (required by testing output).
490             if (!textRun || textRun->isHardLineBreak())
491                 return;
492             auto collapseSoftLineBreak = textRun->isSoftLineBreak() && (!m_style.preserveNewline || m_style.preWrap);
493             if (collapseSoftLineBreak) {
494                 ++m_textRunList;
495                 textRun = m_textRunList.current();
496             }
497         }
498     }
499
500     // Collapse leading whitespace if the style says so.
501     if (!m_style.collapseWhitespace)
502         return;
503
504     if (!textRun || !textRun->isWhitespace())
505         return;
506
507     ++m_textRunList;
508 }
509
510 void SimpleLineBreaker::collapseTrailingWhitespace()
511 {
512     if (!m_currentLine.hasTrailingWhitespace())
513         return;
514
515     // Remove collapsed whitespace, or non-collapsed pre-wrap whitespace, unless it's the only content on the line -so removing the whitesapce would produce an empty line.
516     bool collapseWhitespace = m_style.collapseWhitespace || m_style.preWrap;
517     if (!collapseWhitespace)
518         return;
519
520     // pre-wrap?
521     if (m_currentLine.isWhitespaceOnly() && m_style.preWrap)
522         return;
523
524     m_currentLine.collapseTrailingWhitespace();
525 }
526
527 std::optional<ContentPosition> SimpleLineBreaker::hyphenPositionBefore(const TextRun& textRun, ContentPosition before) const
528 {
529     // Enough characters before the split position?
530     if (before <= textRun.start() + m_style.hyphenLimitBefore)
531         return { };
532
533     // Adjust before to accommodate the limit-after value (this is the last potential hyphen location).
534     before = std::min(before, textRun.end() - m_style.hyphenLimitAfter + 1);
535
536     auto hyphenLocation = m_contentProvider.hyphenPositionBefore(textRun.start(), textRun.end(), before);
537     if (!hyphenLocation)
538         return { };
539
540     ASSERT(hyphenLocation >= textRun.start() && hyphenLocation <= textRun.end());
541     // Check if there are enough characters before and after the hyphen.
542     if (*hyphenLocation < textRun.start() + m_style.hyphenLimitBefore || m_style.hyphenLimitAfter > (textRun.end() - *hyphenLocation))
543         return { };
544
545     return hyphenLocation;
546 }
547
548 std::optional<ContentPosition> SimpleLineBreaker::adjustSplitPositionWithHyphenation(const TextRun& textRun, ContentPosition splitPosition, float leftSideWidth) const
549 {
550     ASSERT(textRun.isNonWhitespace());
551
552     // Use hyphen?
553     if (!m_style.shouldHyphenate || m_hyphenationIsDisabled)
554         return { };
555
556     // Check if there are enough characters in the run.
557     auto runLength = textRun.length();
558     if (m_style.hyphenLimitBefore >= runLength || m_style.hyphenLimitAfter >= runLength || m_style.hyphenLimitBefore + m_style.hyphenLimitAfter > runLength)
559         return { };
560
561     // FIXME: This is a workaround for webkit.org/b/169613. See maxPrefixWidth computation in tryHyphenating().
562     // It does not work properly with non-collapsed leading tabs when font is enlarged.
563     auto adjustedAvailableWidth = m_currentLine.availableWidth() - m_style.hyphenStringWidth;
564     if (m_currentLine.hasContent())
565         adjustedAvailableWidth += m_style.font.spaceWidth();
566
567     if (!enoughWidthForHyphenation(adjustedAvailableWidth, m_style.font.pixelSize()))
568         return { };
569
570     // Find the split position where hyphen surely fits (we might be able to fit the hyphen at the split position).
571     auto left = textRun.start();
572     auto right = splitPosition;
573     while (leftSideWidth + m_style.hyphenStringWidth > m_currentLine.availableWidth()) {
574         if (--right <= left)
575             return { }; // No space for hyphen.
576         // FIXME: for correctness (kerning) we should instead measure the left side.
577         leftSideWidth -= m_contentProvider.width(right, right + 1, 0);
578     }
579
580     // Find out if there's an actual hyphen opportinity at this position (or before).
581     return hyphenPositionBefore(textRun, right + 1);
582 }
583
584 bool SimpleLineBreaker::splitTextRun(const TextRun& textRun)
585 {
586     // Single character handling.
587     if (textRun.start() + 1 == textRun.end()) {
588         // Keep at least one character on empty lines.
589         if (!m_currentLine.hasContent()) {
590             m_currentLine.append(textRun);
591             return false;
592         }
593         m_textRunList.overrideCurrent(textRun);
594         return true;
595     }
596
597     auto splitPair = split(textRun, m_currentLine.availableWidth());
598     m_currentLine.append(splitPair.left);
599     m_textRunList.overrideCurrent(splitPair.right);
600     return true;
601 }
602
603 TextRunSplitPair SimpleLineBreaker::split(const TextRun& textRun, float leftSideMaximumWidth) const
604 {
605     // Preserve the left width for the final split position so that we don't need to remeasure the left side again.
606     float leftSideWidth = 0;
607     auto left = textRun.start();
608
609     // Pathological case of (extremely)long string and narrow lines.
610     // Adjust the range so that we can pick a reasonable midpoint.
611     auto averageCharacterWidth = textRun.width() / textRun.length();
612     auto right = std::min<unsigned>(left + (2 * leftSideMaximumWidth / averageCharacterWidth), textRun.end() - 1);
613     while (left < right) {
614         auto middle = (left + right) / 2;
615         auto width = m_contentProvider.width(textRun.start(), middle + 1, 0);
616         if (width < leftSideMaximumWidth) {
617             left = middle + 1;
618             leftSideWidth = width;
619         } else if (width > leftSideMaximumWidth)
620             right = middle;
621         else {
622             right = middle + 1;
623             leftSideWidth = width;
624             break;
625         }
626     }
627
628     // Keep at least one character on empty lines.
629     bool splitHasHypen = false;
630     left = textRun.start();
631     if (left >= right && !m_currentLine.hasContent()) {
632         right = left + 1;
633         leftSideWidth = m_contentProvider.width(left, right, 0);
634     } else if (textRun.isNonWhitespace()) {
635         if (auto hyphenPosition = adjustSplitPositionWithHyphenation(textRun, right, leftSideWidth)) {
636             splitHasHypen = true;
637             right = *hyphenPosition;
638             leftSideWidth = m_contentProvider.width(left, right, 0) + m_style.hyphenStringWidth;
639         }
640     }
641
642     auto rightSideWidth = m_contentProvider.width(right, textRun.end(), 0);
643     if (textRun.isNonWhitespace())
644         return { splitHasHypen ? TextRun::createNonWhitespaceRunWithHyphen(left, right, leftSideWidth) : TextRun::createNonWhitespaceRun(left, right, leftSideWidth),
645             TextRun::createNonWhitespaceRun(right, textRun.end(), rightSideWidth) };
646
647     // We never split collapsed whitespace.
648     ASSERT(textRun.isWhitespace());
649     ASSERT(!textRun.isCollapsed());
650     return { TextRun::createWhitespaceRun(left, right, leftSideWidth, false), TextRun::createWhitespaceRun(right, textRun.end(), rightSideWidth, false) };
651 }
652
653 SimpleLineBreaker::LineConstraint SimpleLineBreaker::lineConstraint(float verticalPosition)
654 {
655     auto* lineConstraint = m_lineConstraintIterator.current();
656     if (!lineConstraint) {
657         ASSERT_NOT_REACHED();
658         return { };
659     }
660
661     while (lineConstraint->verticalPosition && verticalPosition > *lineConstraint->verticalPosition) {
662         lineConstraint = (++m_lineConstraintIterator).current();
663         if (!lineConstraint) {
664             // The vertical position of the last entry in the constraint list is supposed to be infinite.
665             ASSERT_NOT_REACHED();
666             return { };
667         }
668     }
669
670     return *lineConstraint;
671 }
672
673 }
674 }
675 #endif