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