Simple line layout should support floats
[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 "RenderStyle.h"
41 #include "RenderText.h"
42 #include "RenderTextControl.h"
43 #include "RenderView.h"
44 #include "Settings.h"
45 #include "SimpleLineLayoutFunctions.h"
46 #include "Text.h"
47 #include "TextPaintStyle.h"
48 #include "break_lines.h"
49 #include <wtf/unicode/Unicode.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 !PLATFORM(MAC) && !PLATFORM(GTK) && !PLATFORM(EFL)
94     // FIXME: Non-mac platforms are hitting ASSERT(run.charactersLength() >= run.length())
95     // https://bugs.webkit.org/show_bug.cgi?id=123338
96     return false;
97 #endif
98     if (!flow.frame().settings().simpleLineLayoutEnabled())
99         return false;
100     if (!flow.firstChild())
101         return false;
102     // This currently covers <blockflow>#text</blockflow> case.
103     // The <blockflow><inline>#text</inline></blockflow> case is also popular and should be relatively easy to cover.
104     if (flow.firstChild() != flow.lastChild())
105         return false;
106     if (!flow.firstChild()->isText())
107         return false;
108     if (!flow.isHorizontalWritingMode())
109         return false;
110     if (flow.flowThreadState() != RenderObject::NotInsideFlowThread)
111         return false;
112     if (flow.hasOutline())
113         return false;
114     if (flow.isRubyText() || flow.isRubyBase())
115         return false;
116     if (flow.parent()->isDeprecatedFlexibleBox())
117         return false;
118     // FIXME: Implementation of wrap=hard looks into lineboxes.
119     if (flow.parent()->isTextArea() && flow.parent()->element()->fastHasAttribute(HTMLNames::wrapAttr))
120         return false;
121     // FIXME: Placeholders do something strange.
122     if (flow.parent()->isTextControl() && toRenderTextControl(*flow.parent()).textFormControlElement().placeholderElement())
123         return false;
124     // These tests only works during layout. Outside layout this function may give false positives.
125     if (flow.view().layoutState()) {
126 #if ENABLE(CSS_SHAPES)
127         if (flow.view().layoutState()->shapeInsideInfo())
128             return false;
129 #endif
130         if (flow.view().layoutState()->m_columnInfo)
131             return false;
132     }
133     const RenderStyle& style = flow.style();
134     if (style.textDecorationsInEffect() != TextDecorationNone)
135         return false;
136     if (style.textAlign() == JUSTIFY)
137         return false;
138     // Non-visible overflow should be pretty easy to support.
139     if (style.overflowX() != OVISIBLE || style.overflowY() != OVISIBLE)
140         return false;
141     if (!style.textIndent().isZero())
142         return false;
143     if (style.wordSpacing() || style.letterSpacing())
144         return false;
145     if (style.textTransform() != TTNONE)
146         return false;
147     if (!style.isLeftToRightDirection())
148         return false;
149     if (style.lineBoxContain() != RenderStyle::initialLineBoxContain())
150         return false;
151     if (style.writingMode() != TopToBottomWritingMode)
152         return false;
153     if (style.lineBreak() != LineBreakAuto)
154         return false;
155     if (style.wordBreak() != NormalWordBreak)
156         return false;
157     if (style.unicodeBidi() != UBNormal || style.rtlOrdering() != LogicalOrder)
158         return false;
159     if (style.lineAlign() != LineAlignNone || style.lineSnap() != LineSnapNone)
160         return false;
161     if (style.hyphens() == HyphensAuto)
162         return false;
163     if (style.textEmphasisFill() != TextEmphasisFillFilled || style.textEmphasisMark() != TextEmphasisMarkNone)
164         return false;
165     if (style.textShadow())
166         return false;
167 #if ENABLE(CSS_SHAPES)
168     if (style.resolvedShapeInside())
169         return true;
170 #endif
171     if (style.textOverflow() || (flow.isAnonymousBlock() && flow.parent()->style().textOverflow()))
172         return false;
173     if (style.hasPseudoStyle(FIRST_LINE) || style.hasPseudoStyle(FIRST_LETTER))
174         return false;
175     if (style.hasTextCombine())
176         return false;
177     if (style.backgroundClip() == TextFillBox)
178         return false;
179     if (style.borderFit() == BorderFitLines)
180         return false;
181     const RenderText& textRenderer = toRenderText(*flow.firstChild());
182     if (flow.containsFloats()) {
183         // 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.
184         // It is enough to test the first line width only as currently all floats must be overhanging.
185         if (textRenderer.minLogicalWidth() > LineWidth(const_cast<RenderBlockFlow&>(flow), false, DoNotIndentText).availableWidth())
186             return false;
187     }
188     if (textRenderer.isCombineText() || textRenderer.isCounter() || textRenderer.isQuote() || textRenderer.isTextFragment()
189 #if ENABLE(SVG)
190         || textRenderer.isSVGInlineText()
191 #endif
192         )
193         return false;
194     if (style.font().codePath(TextRun(textRenderer.text())) != Font::Simple)
195         return false;
196     if (style.font().isSVGFont())
197         return false;
198
199     // We assume that all lines have metrics based purely on the primary font.
200     auto& primaryFontData = *style.font().primaryFont();
201     if (primaryFontData.isLoading())
202         return false;
203     if (!canUseForText(textRenderer, primaryFontData))
204         return false;
205
206     return true;
207 }
208
209 struct Style {
210     Style(const RenderStyle& style)
211         : font(style.font())
212         , textAlign(style.textAlign())
213         , collapseWhitespace(style.collapseWhiteSpace())
214         , preserveNewline(style.preserveNewline())
215         , wrapLines(style.autoWrap())
216         , breakWordOnOverflow(style.overflowWrap() == BreakOverflowWrap && (wrapLines || preserveNewline))
217         , spaceWidth(font.width(TextRun(&space, 1)))
218         , tabWidth(collapseWhitespace ? 0 : style.tabSize())
219     {
220     }
221     const Font& font;
222     ETextAlign textAlign;
223     bool collapseWhitespace;
224     bool preserveNewline;
225     bool wrapLines;
226     bool breakWordOnOverflow;
227     float spaceWidth;
228     unsigned tabWidth;
229 };
230
231 static inline bool isWhitespace(UChar character, bool preserveNewline)
232 {
233     return character == ' ' || character == '\t' || (!preserveNewline && character == '\n');
234 }
235
236 template <typename CharacterType>
237 static inline unsigned skipWhitespaces(const CharacterType* text, unsigned offset, unsigned length, bool preserveNewline)
238 {
239     for (; offset < length; ++offset) {
240         if (!isWhitespace(text[offset], preserveNewline))
241             return offset;
242     }
243     return length;
244 }
245
246 template <typename CharacterType>
247 static float textWidth(const RenderText& renderText, const CharacterType* text, unsigned textLength, unsigned from, unsigned to, float xPosition, const Style& style)
248 {
249     if (style.font.isFixedPitch() || (!from && to == textLength))
250         return renderText.width(from, to - from, style.font, xPosition, nullptr, nullptr);
251
252     TextRun run(text + from, to - from);
253     run.setXPos(xPosition);
254     run.setCharactersLength(textLength - from);
255     run.setTabSize(!!style.tabWidth, style.tabWidth);
256
257     ASSERT(run.charactersLength() >= run.length());
258
259     return style.font.width(run);
260 }
261
262 template <typename CharacterType>
263 static float measureWord(unsigned start, unsigned end, float lineWidth, const Style& style, const CharacterType* text, unsigned textLength, const RenderText& textRenderer)
264 {
265     if (text[start] == ' ' && end == start + 1)
266         return style.spaceWidth;
267
268     bool measureWithEndSpace = style.collapseWhitespace && end < textLength && text[end] == ' ';
269     if (measureWithEndSpace)
270         ++end;
271     float width = textWidth(textRenderer, text, textLength, start, end, lineWidth, style);
272
273     return measureWithEndSpace ? width - style.spaceWidth : width;
274 }
275
276 template <typename CharacterType>
277 Vector<Run, 4> createLineRuns(unsigned lineStart, LineWidth& lineWidth, LazyLineBreakIterator& lineBreakIterator, const Style& style, const CharacterType* text, unsigned textLength, const RenderText& textRenderer)
278 {
279     Vector<Run, 4> lineRuns;
280     lineRuns.uncheckedAppend(Run(lineStart, 0));
281
282     unsigned wordEnd = lineStart;
283     while (wordEnd < textLength) {
284         ASSERT(!style.collapseWhitespace || !isWhitespace(text[wordEnd], style.preserveNewline));
285
286         unsigned wordStart = wordEnd;
287
288         if (style.preserveNewline && text[wordStart] == '\n') {
289             ++wordEnd;
290             // FIXME: This creates a dedicated run for newline. This is wasteful and unnecessary but it keeps test results unchanged.
291             if (wordStart > lineStart)
292                 lineRuns.append(Run(wordStart, lineRuns.last().right));
293             lineRuns.last().right = lineRuns.last().left;
294             lineRuns.last().end = wordEnd;
295             break;
296         }
297
298         if (!style.collapseWhitespace && isWhitespace(text[wordStart], style.preserveNewline))
299             wordEnd = wordStart + 1;
300         else
301             wordEnd = nextBreakablePosition<CharacterType, false>(lineBreakIterator, text, textLength, wordStart + 1);
302
303         bool wordIsPrecededByWhitespace = style.collapseWhitespace && wordStart > lineStart && isWhitespace(text[wordStart - 1], style.preserveNewline);
304         if (wordIsPrecededByWhitespace)
305             --wordStart;
306
307         float wordWidth = measureWord(wordStart, wordEnd, lineWidth.committedWidth(), style, text, textLength, textRenderer);
308
309         lineWidth.addUncommittedWidth(wordWidth);
310
311         if (style.wrapLines) {
312             // Move to the next line if the current one is full and we have something on it.
313             if (!lineWidth.fitsOnLine() && lineWidth.committedWidth())
314                 break;
315
316             // This is for white-space: pre-wrap which requires special handling for end line whitespace.
317             if (!style.collapseWhitespace && lineWidth.fitsOnLine() && wordEnd < textLength && isWhitespace(text[wordEnd], style.preserveNewline)) {
318                 // Look ahead to see if the next whitespace would fit.
319                 float whitespaceWidth = textWidth(textRenderer, text, textLength, wordEnd, wordEnd + 1, lineWidth.committedWidth(), style);
320                 if (!lineWidth.fitsOnLineIncludingExtraWidth(whitespaceWidth)) {
321                     // If not eat away the rest of the whitespace on the line.
322                     unsigned whitespaceEnd = skipWhitespaces(text, wordEnd, textLength, style.preserveNewline);
323                     // Include newline to this run too.
324                     if (whitespaceEnd < textLength && text[whitespaceEnd] == '\n')
325                         ++whitespaceEnd;
326                     lineRuns.last().end = whitespaceEnd;
327                     lineRuns.last().right = lineWidth.availableWidth();
328                     break;
329                 }
330             }
331         }
332
333         if (wordStart > lineRuns.last().end) {
334             // There were more than one consecutive whitespace.
335             ASSERT(wordIsPrecededByWhitespace);
336             // Include space to the end of the previous run.
337             lineRuns.last().end++;
338             lineRuns.last().right += style.spaceWidth;
339             // Start a new run on the same line.
340             lineRuns.append(Run(wordStart + 1, lineRuns.last().right));
341         }
342
343         if (!lineWidth.fitsOnLine() && style.breakWordOnOverflow) {
344             // Backtrack and start measuring character-by-character.
345             lineWidth.addUncommittedWidth(-lineWidth.uncommittedWidth());
346             unsigned splitEnd = wordStart;
347             for (; splitEnd < wordEnd; ++splitEnd) {
348                 float charWidth = textWidth(textRenderer, text, textLength, splitEnd, splitEnd + 1, 0, style);
349                 lineWidth.addUncommittedWidth(charWidth);
350                 if (!lineWidth.fitsOnLine() && splitEnd > lineStart)
351                     break;
352                 lineWidth.commit();
353             }
354             lineRuns.last().end = splitEnd;
355             lineRuns.last().right = lineWidth.committedWidth();
356             // To match line boxes, set single-space-only line width to zero.
357             if (text[lineRuns.last().start] == ' ' && lineRuns.last().start + 1 == lineRuns.last().end)
358                 lineRuns.last().right = lineRuns.last().left;
359             break;
360         }
361
362         lineWidth.commit();
363
364         lineRuns.last().right = lineWidth.committedWidth();
365         lineRuns.last().end = wordEnd;
366
367         if (style.collapseWhitespace)
368             wordEnd = skipWhitespaces(text, wordEnd, textLength, style.preserveNewline);
369
370         if (!lineWidth.fitsOnLine() && style.wrapLines) {
371             // The first run on the line overflows.
372             ASSERT(lineRuns.size() == 1);
373             break;
374         }
375     }
376     return lineRuns;
377 }
378
379 static float computeLineLeft(ETextAlign textAlign, const LineWidth& lineWidth)
380 {
381     float remainingWidth = lineWidth.availableWidth() - lineWidth.committedWidth();
382     float left = lineWidth.logicalLeftOffset();
383     switch (textAlign) {
384     case LEFT:
385     case WEBKIT_LEFT:
386     case TASTART:
387         return left;
388     case RIGHT:
389     case WEBKIT_RIGHT:
390     case TAEND:
391         return left + std::max<float>(remainingWidth, 0);
392     case CENTER:
393     case WEBKIT_CENTER:
394         return left + std::max<float>(remainingWidth / 2, 0);
395     case JUSTIFY:
396         break;
397     }
398     ASSERT_NOT_REACHED();
399     return 0;
400 }
401
402 static void adjustRunOffsets(Vector<Run, 4>& lineRuns, float adjustment)
403 {
404     if (!adjustment)
405         return;
406     for (unsigned i = 0; i < lineRuns.size(); ++i) {
407         lineRuns[i].left += adjustment;
408         lineRuns[i].right += adjustment;
409     }
410 }
411
412 template <typename CharacterType>
413 void createTextRuns(Layout::RunVector& runs, unsigned& lineCount, RenderBlockFlow& flow, RenderText& textRenderer)
414 {
415     const Style style(flow.style());
416
417     const CharacterType* text = textRenderer.text()->getCharacters<CharacterType>();
418     const unsigned textLength = textRenderer.textLength();
419
420     LayoutUnit borderAndPaddingBefore = flow.borderAndPaddingBefore();
421     LayoutUnit lineHeight = lineHeightFromFlow(flow);
422
423     LazyLineBreakIterator lineBreakIterator(textRenderer.text(), flow.style().locale());
424
425     unsigned lineEnd = 0;
426     while (lineEnd < textLength) {
427         if (style.collapseWhitespace)
428             lineEnd = skipWhitespaces(text, lineEnd, textLength, style.preserveNewline);
429
430         unsigned lineStart = lineEnd;
431
432         // LineWidth reads the current y position from the flow so keep it updated.
433         flow.setLogicalHeight(lineHeight * lineCount + borderAndPaddingBefore);
434         LineWidth lineWidth(flow, false, DoNotIndentText);
435
436         auto lineRuns = createLineRuns(lineStart, lineWidth, lineBreakIterator, style, text, textLength, textRenderer);
437
438         lineEnd = lineRuns.last().end;
439         if (lineStart == lineEnd)
440             continue;
441
442         lineRuns.last().isEndOfLine = true;
443
444         float lineLeft = computeLineLeft(style.textAlign, lineWidth);
445         adjustRunOffsets(lineRuns, lineLeft);
446
447         for (unsigned i = 0; i < lineRuns.size(); ++i)
448             runs.append(lineRuns[i]);
449
450         ++lineCount;
451     }
452 }
453
454 std::unique_ptr<Layout> create(RenderBlockFlow& flow)
455 {
456     Layout::RunVector runs;
457     unsigned lineCount = 0;
458
459     RenderText& textRenderer = toRenderText(*flow.firstChild());
460     ASSERT(!textRenderer.firstTextBox());
461
462     if (textRenderer.is8Bit())
463         createTextRuns<LChar>(runs, lineCount, flow, textRenderer);
464     else
465         createTextRuns<UChar>(runs, lineCount, flow, textRenderer);
466
467     textRenderer.clearNeedsLayout();
468
469     return Layout::create(runs, lineCount);
470 }
471
472 std::unique_ptr<Layout> Layout::create(const RunVector& runVector, unsigned lineCount)
473 {
474     void* slot = WTF::fastMalloc(sizeof(Layout) + sizeof(Run) * runVector.size());
475     return std::unique_ptr<Layout>(new (NotNull, slot) Layout(runVector, lineCount));
476 }
477
478 Layout::Layout(const RunVector& runVector, unsigned lineCount)
479     : m_lineCount(lineCount)
480     , m_runCount(runVector.size())
481 {
482     memcpy(m_runs, runVector.data(), m_runCount * sizeof(Run));
483 }
484
485 }
486 }