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