Source/WebCore/layout/inlineformatting/LineLayoutContext.cpp

/*
 * Copyright (C) 2019 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "LineLayoutContext.h"

#if ENABLE(LAYOUT_FORMATTING_CONTEXT)

#include "InlineFormattingContext.h"
#include "LayoutBox.h"
#include "TextUtil.h"

namespace WebCore {
namespace Layout {

static inline bool endsWithSoftWrapOpportunity(const InlineTextItem& currentTextItem, const InlineTextItem& nextInlineTextItem)
{
    ASSERT(!nextInlineTextItem.isWhitespace());
    // We are at the position after a whitespace.
    if (currentTextItem.isWhitespace())
        return true;
    // When both these non-whitespace runs belong to the same layout box, it's guaranteed that
    // they are split at a soft breaking opportunity. See InlineTextItem::moveToNextBreakablePosition.
    if (&currentTextItem.layoutBox() == &nextInlineTextItem.layoutBox())
        return true;
    // Now we need to collect at least 3 adjacent characters to be able to make a decision whether the previous text item ends with breaking opportunity.
    // [ex-][ample] <- second to last[x] last[-] current[a]
    // We need at least 1 character in the current inline text item and 2 more from previous inline items.
    auto previousContent = currentTextItem.layoutBox().textContext()->content;
    auto lineBreakIterator = LazyLineBreakIterator { nextInlineTextItem.layoutBox().textContext()->content };
    auto previousContentLength = previousContent.length();
    // FIXME: We should look into the entire uncommitted content for more text context.
    UChar lastCharacter = previousContentLength ? previousContent[previousContentLength - 1] : 0;
    UChar secondToLastCharacter = previousContentLength > 1 ? previousContent[previousContentLength - 2] : 0;
    lineBreakIterator.setPriorContext(lastCharacter, secondToLastCharacter);
    // Now check if we can break right at the inline item boundary.
    // With the [ex-ample], findNextBreakablePosition should return the startPosition (0).
    // FIXME: Check if there's a more correct way of finding breaking opportunities.
    return !TextUtil::findNextBreakablePosition(lineBreakIterator, 0, nextInlineTextItem.style());
}

static inline bool isAtSoftWrapOpportunity(const InlineItem& current, const InlineItem& next)
{
    // "is at" simple means that there's a soft wrap opportunity right after the [current].
    // [text][ ][text][container start]... (<div>text content<span>..</div>)
    // soft wrap indexes: 0 and 1 definitely, 2 depends on the content after the [container start].

    // https://drafts.csswg.org/css-text-3/#line-break-details
    // Figure out if the new incoming content puts the uncommitted content on a soft wrap opportunity.
    // e.g. [container start][prior_continuous_content][container end] (<span>prior_continuous_content</span>)
    // An incoming <img> box would enable us to commit the "<span>prior_continuous_content</span>" content
    // but an incoming text content would not necessarily.
    ASSERT(current.isText() || current.isBox());
    ASSERT(next.isText() || next.isBox());
    if (current.isText() && next.isText()) {
        auto& currentInlineTextItem = downcast<InlineTextItem>(current);
        auto& nextInlineTextItem = downcast<InlineTextItem>(next);
        if (currentInlineTextItem.isWhitespace()) {
            // [ ][text] : after [whitespace] position is a soft wrap opportunity.
            return true;
        }
        if (nextInlineTextItem.isWhitespace()) {
            // [text][ ] (<span>text</span> )
            // white-space: break-spaces: line breaking opportunity exists after every preserved white space character, but not before.
            return nextInlineTextItem.style().whiteSpace() != WhiteSpace::BreakSpaces;
        }
        if (current.style().lineBreak() == LineBreak::Anywhere || next.style().lineBreak() == LineBreak::Anywhere) {
            // There is a soft wrap opportunity around every typographic character unit, including around any punctuation character
            // or preserved white spaces, or in the middle of words.
            return true;
        }
        // Both current and next items are non-whitespace text.
        // [text][text] : is a continuous content.
        // [text-][text] : after [hyphen] position is a soft wrap opportunity.
        return endsWithSoftWrapOpportunity(currentInlineTextItem, nextInlineTextItem);
    }
    if (current.isBox() || next.isBox()) {
        // [text][container start][container end][inline box] (text<span></span><img>) : there's a soft wrap opportunity between the [text] and [img].
        // The line breaking behavior of a replaced element or other atomic inline is equivalent to an ideographic character.
        return true;
    }
    ASSERT_NOT_REACHED();
    return true;
}

static inline size_t nextWrapOpportunity(const InlineItems& inlineContent, unsigned startIndex)
{
    // 1. Find the start candidate by skipping leading non-content items e.g <span><span>start : skip "<span><span>"
    // 2. Find the end candidate by skipping non-content items inbetween e.g. <span><span>start</span>end: skip "</span>"
    // 3. Check if there's a soft wrap opportunity between the 2 candidate inline items and repeat.
    // 4. Any force line break inbetween is considered as a wrap opportunity.

    // [ex-][container start][container end][float][ample] (ex-<span></span><div style="float:left"></div>ample) : wrap index is at [ex-].
    // [ex][container start][amp-][container start][le] (ex<span>amp-<span>ample) : wrap index is at [amp-].
    // [ex-][container start][line break][ample] (ex-<span><br>ample) : wrap index is after [br].
    unsigned inlineItemCount = inlineContent.size();
    auto isAtLineBreak = false;

    auto inlineItemIndexWithContent = [&] (auto index) {
        // Break at the first text/box/line break inline item.
        for (; index < inlineItemCount; ++index) {
            auto& inlineItem = inlineContent[index];
            if (inlineItem.isText() || inlineItem.isBox())
                return index;
            if (inlineItem.isLineBreak()) {
                isAtLineBreak = true;
                return index;
            }
        }
        return inlineItemCount;
    };

    // Start at the first inline item with content.
    // [container start][ex-] : start at [ex-]
    auto startContentIndex = inlineItemIndexWithContent(startIndex);
    if (isAtLineBreak) {
        // Content starts with a line break. The wrap position is after the line break.
        return startContentIndex + 1;
    }

    while (startContentIndex < inlineItemCount) {
        // 1. Find the next inline item with content.
        // 2. Check if there's a soft wrap opportunity between the start and the next inline item.
        auto nextContentIndex = inlineItemIndexWithContent(startContentIndex + 1);
        if (nextContentIndex == inlineItemCount)
            return nextContentIndex;
        if (isAtLineBreak) {
            // We always stop at line breaks. The wrap position is after the line break.
            return nextContentIndex + 1;
        }
        if (isAtSoftWrapOpportunity(inlineContent[startContentIndex], inlineContent[nextContentIndex])) {
            // There's a soft wrap opportunity between the start and the nextContent.
            // Now forward-find from the start position to see where we can actually wrap.
            // [ex-][ample] vs. [ex-][container start][container end][ample]
            // where [ex-] is startContent and [ample] is the nextContent.
            for (auto candidateIndex = startContentIndex + 1; candidateIndex < nextContentIndex; ++candidateIndex) {
                if (inlineContent[candidateIndex].isContainerStart()) {
                    // inline content and [container start] and [container end] form unbreakable content.
                    // ex-<span></span>ample  : wrap opportunity is after "ex-".
                    // ex-</span></span>ample : wrap opportunity is after "ex-</span></span>".
                    // ex-</span><span>ample</span> : wrap opportunity is after "ex-</span>".
                    // ex-<span><span>ample</span></span> : wrap opportunity is after "ex-".
                    return candidateIndex;
                }
            }
            return nextContentIndex;
        }
        startContentIndex = nextContentIndex;
    }
    return inlineItemCount;
}

struct LineCandidateContent {
    void appendInlineContent(const InlineItem&, InlineLayoutUnit logicalWidth);
    void appendLineBreak(const InlineItem& inlineItem) { setTrailingLineBreak(inlineItem); }
    void appendFloat(const InlineItem& inlineItem) { m_floats.append(&inlineItem); }

    bool hasIntrusiveFloats() const { return !m_floats.isEmpty(); }
    const LineBreaker::RunList& inlineRuns() const { return m_inlineRuns; }
    InlineLayoutUnit inlineContentLogicalWidth() const { return m_inlineContentLogicalWidth; }
    const LineLayoutContext::FloatList& floats() const { return m_floats; }

    const InlineItem* trailingLineBreak() const { return m_trailingLineBreak; }

    void reset();

private:
    void setTrailingLineBreak(const InlineItem& lineBreakItem) { m_trailingLineBreak = &lineBreakItem; }

    InlineLayoutUnit m_inlineContentLogicalWidth { 0 };
    LineBreaker::RunList m_inlineRuns;
    LineLayoutContext::FloatList m_floats;
    const InlineItem* m_trailingLineBreak { nullptr };
};

inline void LineCandidateContent::appendInlineContent(const InlineItem& inlineItem, InlineLayoutUnit logicalWidth)
{
    m_inlineContentLogicalWidth += logicalWidth;
    m_inlineRuns.append({ inlineItem, logicalWidth });
}

inline void LineCandidateContent::reset()
{
    m_inlineContentLogicalWidth = 0;
    m_inlineRuns.clear();
    m_floats.clear();
    m_trailingLineBreak = nullptr;
}

InlineLayoutUnit LineLayoutContext::inlineItemWidth(const InlineItem& inlineItem, InlineLayoutUnit contentLogicalLeft) const
{
    if (is<InlineTextItem>(inlineItem)) {
        auto& inlineTextItem = downcast<InlineTextItem>(inlineItem);
        if (auto contentWidth = inlineTextItem.width())
            return *contentWidth;
        auto end = inlineTextItem.isCollapsible() ? inlineTextItem.start() + 1 : inlineTextItem.end();
        return TextUtil::width(inlineTextItem, inlineTextItem.start(), end, contentLogicalLeft);
    }

    if (inlineItem.isLineBreak())
        return 0;

    auto& layoutBox = inlineItem.layoutBox();
    auto& boxGeometry = m_inlineFormattingContext.geometryForBox(layoutBox);

    if (layoutBox.isFloatingPositioned())
        return boxGeometry.marginBoxWidth();

    if (layoutBox.replaced())
        return boxGeometry.width();

    if (inlineItem.isContainerStart())
        return boxGeometry.marginStart() + boxGeometry.borderLeft() + boxGeometry.paddingLeft().valueOr(0);

    if (inlineItem.isContainerEnd())
        return boxGeometry.marginEnd() + boxGeometry.borderRight() + boxGeometry.paddingRight().valueOr(0);

    // Non-replaced inline box (e.g. inline-block)
    return boxGeometry.width();
}

static inline bool isLineConsideredEmpty(const LineBuilder& line)
{
    return line.isVisuallyEmpty() && !line.hasIntrusiveFloat();
}

LineLayoutContext::LineLayoutContext(const InlineFormattingContext& inlineFormattingContext, const Container& formattingContextRoot, const InlineItems& inlineItems)
    : m_inlineFormattingContext(inlineFormattingContext)
    , m_formattingContextRoot(formattingContextRoot)
    , m_inlineItems(inlineItems)
{
}

LineLayoutContext::LineContent LineLayoutContext::layoutLine(LineBuilder& line, unsigned leadingInlineItemIndex, Optional<unsigned> partialLeadingContentLength)
{
    auto reset = [&] {
        ASSERT(m_floats.isEmpty());
        m_partialTrailingTextItem = { };
        m_partialLeadingTextItem = { };
    };
    reset();
    auto lineBreaker = LineBreaker { };
    auto currentItemIndex = leadingInlineItemIndex;
    unsigned committedInlineItemCount = 0;
    auto candidateContent = LineCandidateContent { };
    while (currentItemIndex < m_inlineItems.size()) {
        // 1. Collect the set of runs that we can commit to the line as one entity e.g. <span>text_and_span_start_span_end</span>.
        // 2. Apply floats and shrink the available horizontal space e.g. <span>intru_<div style="float: left"></div>sive_float</span>.
        // 3. Check if the content fits the line and commit the content accordingly (full, partial or not commit at all).
        // 4. Return if we are at the end of the line either by not being able to fit more content or because of an explicit line break.
        nextContentForLine(candidateContent, currentItemIndex, partialLeadingContentLength, line.lineBox().logicalWidth());
        if (candidateContent.hasIntrusiveFloats()) {
            // Add floats first because they shrink the available horizontal space for the rest of the content.
            auto result = tryAddingFloatItems(line, candidateContent.floats());
            committedInlineItemCount += result.committedCount;
            if (result.isEndOfLine == LineBreaker::IsEndOfLine::Yes) {
                // Floats take up all the horizontal space.
                return close(line, leadingInlineItemIndex, committedInlineItemCount, { });
            }
        }
        if (!candidateContent.inlineRuns().isEmpty()) {
            // Now check if we can put this content on the current line.
            auto result = tryAddingInlineItems(lineBreaker, line, candidateContent);
            if (result.revertTo) {
                ASSERT(!result.committedCount);
                ASSERT(result.isEndOfLine == LineBreaker::IsEndOfLine::Yes);
                // An earlier line wrapping opportunity turned out to be the final breaking position.
                committedInlineItemCount -= line.revert(*result.revertTo);
            }
            committedInlineItemCount += result.committedCount;
            if (result.isEndOfLine == LineBreaker::IsEndOfLine::Yes) {
                // We can't place any more items on the current line.
                return close(line, leadingInlineItemIndex, committedInlineItemCount, result.partialContent);
            }
        } else if (auto* trailingLineBreak = candidateContent.trailingLineBreak()) {
            line.append(*trailingLineBreak, 0);
            return close(line, leadingInlineItemIndex, ++committedInlineItemCount, { });
        }
        currentItemIndex = leadingInlineItemIndex + committedInlineItemCount;
        partialLeadingContentLength = { };
    }
    // Looks like we've run out of runs.
    return close(line, leadingInlineItemIndex, committedInlineItemCount, { });
}

LineLayoutContext::LineContent LineLayoutContext::close(LineBuilder& line, unsigned leadingInlineItemIndex, unsigned committedInlineItemCount, Optional<LineContent::PartialContent> partialContent)
{
    ASSERT(committedInlineItemCount || line.hasIntrusiveFloat());
    if (!committedInlineItemCount)
        return LineContent { { }, { }, WTFMove(m_floats), line.close(), line.lineBox() };

    // Adjust hyphenated line count.
    if (partialContent && partialContent->trailingContentNeedsHyphen)
        ++m_successiveHyphenatedLineCount;
    else
        m_successiveHyphenatedLineCount = 0;

    auto trailingInlineItemIndex = leadingInlineItemIndex + committedInlineItemCount - 1;
    auto isLastLineWithInlineContent = [&] {
        if (trailingInlineItemIndex == m_inlineItems.size() - 1)
            return LineBuilder::IsLastLineWithInlineContent::Yes;
        if (partialContent)
            return LineBuilder::IsLastLineWithInlineContent::No;
        // Omit floats to see if this is the last line with inline content.
        for (auto i = m_inlineItems.size(); i--;) {
            if (!m_inlineItems[i].isFloat())
                return i == trailingInlineItemIndex ? LineBuilder::IsLastLineWithInlineContent::Yes : LineBuilder::IsLastLineWithInlineContent::No;
        }
        // There has to be at least one non-float item.
        ASSERT_NOT_REACHED();
        return LineBuilder::IsLastLineWithInlineContent::No;
    }();
    return LineContent { trailingInlineItemIndex, partialContent, WTFMove(m_floats), line.close(isLastLineWithInlineContent), line.lineBox() };
}

void LineLayoutContext::nextContentForLine(LineCandidateContent& candidateContent, unsigned inlineItemIndex, Optional<unsigned> partialLeadingContentLength, InlineLayoutUnit currentLogicalRight)
{
    ASSERT(inlineItemIndex < m_inlineItems.size());
    candidateContent.reset();
    // 1. Simply add any overflow content from the previous line to the candidate content. It's always a text content.
    // 2. Find the next soft wrap position or explicit line break.
    // 3. Collect floats between the inline content.
    auto softWrapOpportunityIndex = nextWrapOpportunity(m_inlineItems, inlineItemIndex);
    // softWrapOpportunityIndex == m_inlineItems.size() means we don't have any wrap opportunity in this content.
    ASSERT(softWrapOpportunityIndex <= m_inlineItems.size());

    if (partialLeadingContentLength) {
        // Handle leading partial content first (split text from the previous line).
        // Construct a partial leading inline item.
        m_partialLeadingTextItem = downcast<InlineTextItem>(m_inlineItems[inlineItemIndex]).right(*partialLeadingContentLength);
        auto itemWidth = inlineItemWidth(*m_partialLeadingTextItem, currentLogicalRight);
        candidateContent.appendInlineContent(*m_partialLeadingTextItem, itemWidth);
        currentLogicalRight += itemWidth;
        ++inlineItemIndex;
    }

    for (auto index = inlineItemIndex; index < softWrapOpportunityIndex; ++index) {
        auto& inlineItem = m_inlineItems[index];
        if (inlineItem.isText() || inlineItem.isContainerStart() || inlineItem.isContainerEnd()) {
            auto inlineItenmWidth = inlineItemWidth(inlineItem, currentLogicalRight);
            candidateContent.appendInlineContent(inlineItem, inlineItenmWidth);
            currentLogicalRight += inlineItenmWidth;
            continue;
        }
        if (inlineItem.isFloat()) {
            // Floats are not part of the line context.
            // FIXME: Check if their width should be added to currentLogicalRight.
            candidateContent.appendFloat(inlineItem);
            continue;
        }
        if (inlineItem.isLineBreak()) {
            candidateContent.appendLineBreak(inlineItem);
            continue;
        }
        ASSERT_NOT_REACHED();
    }
}

LineLayoutContext::Result LineLayoutContext::tryAddingFloatItems(LineBuilder& line, const FloatList& floats)
{
    size_t committedFloatItemCount = 0;
    for (auto& floatItem : floats) {
        auto logicalWidth = inlineItemWidth(*floatItem, { });

        auto lineIsConsideredEmpty = line.isVisuallyEmpty() && !line.hasIntrusiveFloat();
        if (LineBreaker().shouldWrapFloatBox(logicalWidth, line.availableWidth() + line.trailingCollapsibleWidth(), lineIsConsideredEmpty))
            return { LineBreaker::IsEndOfLine::Yes, committedFloatItemCount };
        // This float can sit on the current line.
        ++committedFloatItemCount;
        auto& floatBox = floatItem->layoutBox();
        // Shrink available space for current line and move existing inline runs.
        line.setHasIntrusiveFloat();
        if (floatBox.isLeftFloatingPositioned())
            line.moveLogicalLeft(logicalWidth);
        else
            line.moveLogicalRight(logicalWidth);
        m_floats.append(floatItem);
    }
    return { LineBreaker::IsEndOfLine::No, committedFloatItemCount };
}

LineLayoutContext::Result LineLayoutContext::tryAddingInlineItems(LineBreaker& lineBreaker, LineBuilder& line, const LineCandidateContent& candidateContent)
{
    auto shouldDisableHyphenation = [&] {
        auto& style = root().style();
        unsigned limitLines = style.hyphenationLimitLines() == RenderStyle::initialHyphenationLimitLines() ? std::numeric_limits<unsigned>::max() : style.hyphenationLimitLines();
        return m_successiveHyphenatedLineCount >= limitLines;
    };
    // Check if this new content fits.
    auto lineStatus = LineBreaker::LineStatus { line.availableWidth(), line.trailingCollapsibleWidth(), line.isTrailingRunFullyCollapsible(), isLineConsideredEmpty(line) };

    if (shouldDisableHyphenation())
        lineBreaker.setHyphenationDisabled();

    auto& candidateRuns = candidateContent.inlineRuns();
    auto result = lineBreaker.shouldWrapInlineContent(candidateRuns, candidateContent.inlineContentLogicalWidth(), lineStatus);
    if (result.action == LineBreaker::Result::Action::Keep) {
        // This continuous content can be fully placed on the current line.
        for (auto& run : candidateRuns)
            line.append(run.inlineItem, run.logicalWidth);
        // Consume trailing line break as well.
        if (auto* lineBreakItem = candidateContent.trailingLineBreak()) {
            line.append(*lineBreakItem, 0);
            return { LineBreaker::IsEndOfLine::Yes, candidateRuns.size() + 1 };
        }
        return { result.isEndOfLine, candidateRuns.size() };
    }
    if (result.action == LineBreaker::Result::Action::Push) {
        // This continuous content can't be placed on the current line. Nothing to commit at this time.
        return { result.isEndOfLine };
    }
    if (result.action == LineBreaker::Result::Action::Revert) {
        // Not only this content can't be placed on the current line, but we even need to revert the line back to an earlier position.
        return { result.isEndOfLine, 0, { }, result.revertTo };
    }
    if (result.action == LineBreaker::Result::Action::Split) {
        // Commit the combination of full and partial content on the current line.
        ASSERT(result.partialTrailingContent);
        commitPartialContent(line, candidateRuns, *result.partialTrailingContent);
        // When splitting multiple runs <span style="word-break: break-all">text</span><span>content</span>, we might end up splitting them at run boundary.
        // It simply means we don't really have a partial run. Partial content yes, but not partial run.
        auto trailingRunIndex = result.partialTrailingContent->trailingRunIndex;
        auto committedInlineItemCount = trailingRunIndex + 1;
        if (!result.partialTrailingContent->partialRun)
            return { result.isEndOfLine, committedInlineItemCount };

        auto partialRun = *result.partialTrailingContent->partialRun;
        auto& trailingInlineTextItem = downcast<InlineTextItem>(candidateRuns[trailingRunIndex].inlineItem);
        auto overflowLength = trailingInlineTextItem.length() - partialRun.length;
        return { result.isEndOfLine, committedInlineItemCount, LineContent::PartialContent { partialRun.needsHyphen, overflowLength } };
    }
    ASSERT_NOT_REACHED();
    return { LineBreaker::IsEndOfLine::No };
}

void LineLayoutContext::commitPartialContent(LineBuilder& line, const LineBreaker::RunList& runs, const LineBreaker::Result::PartialTrailingContent& partialTrailingContent)
{
    for (size_t index = 0; index < runs.size(); ++index) {
        auto& run = runs[index];
        if (partialTrailingContent.trailingRunIndex == index) {
            ASSERT(run.inlineItem.isText());
            // Create and commit partial trailing item.
            if (auto partialRun = partialTrailingContent.partialRun) {
                auto& trailingInlineTextItem = downcast<InlineTextItem>(runs[partialTrailingContent.trailingRunIndex].inlineItem);
                // FIXME: LineBuilder should not hold on to the InlineItem.
                ASSERT(!m_partialTrailingTextItem);
                m_partialTrailingTextItem = trailingInlineTextItem.left(partialRun->length);
                line.append(*m_partialTrailingTextItem, partialRun->logicalWidth);
                return;
            }
            // The partial run is the last content to commit.
            line.append(run.inlineItem, run.logicalWidth);
            return;
        }
        line.append(run.inlineItem, run.logicalWidth);
    }
}

}
}

#endif