// Copyright 2019 Google LLC.

#include "modules/skparagraph/src/ParagraphImpl.h"

#include "modules/skparagraph/src/TextWrapper.h"

namespace skia {

namespace textlayout {

namespace {

struct LineBreakerWithLittleRounding {

    LineBreakerWithLittleRounding(SkScalar maxWidth)

        : fLower(maxWidth - 0.25f)

        , fMaxWidth(maxWidth)

        , fUpper(maxWidth + 0.25f) {}

    bool breakLine(SkScalar width) const {

        if (width < fLower) {

            return false;

        } else if (width > fUpper) {

            return true;

        }

        auto val = std::fabs(width);

        SkScalar roundedWidth;

        if (val < 10000) {

            roundedWidth = SkScalarRoundToScalar(width * 100) * (1.0f/100);

        } else if (val < 100000) {

            roundedWidth = SkScalarRoundToScalar(width *  10) * (1.0f/10);

        } else {

            roundedWidth = SkScalarFloorToScalar(width);

        }

        return roundedWidth > fMaxWidth;

    }

    const SkScalar fLower, fMaxWidth, fUpper;

};

}  // namespace

// Since we allow cluster clipping when they don't fit

// we have to work with stretches - parts of clusters

void TextWrapper::lookAhead(SkScalar maxWidth, Cluster* endOfClusters) {

    reset();

    fEndLine.metrics().clean();

    fWords.startFrom(fEndLine.startCluster(), fEndLine.startPos());

    fClusters.startFrom(fEndLine.startCluster(), fEndLine.startPos());

    fClip.startFrom(fEndLine.startCluster(), fEndLine.startPos());

    LineBreakerWithLittleRounding breaker(maxWidth);

    Cluster* nextNonBreakingSpace = nullptr;

    for (auto cluster = fEndLine.endCluster(); cluster < endOfClusters; ++cluster) {

        if (cluster->isHardBreak()) {

        } else if (

                // TODO: Trying to deal with flutter rounding problem. Must be removed...

                SkScalar width = fWords.width() + fClusters.width() + cluster->width();

                breaker.breakLine(width)) {

            if (cluster->isWhitespaceBreak()) {

                // It's the end of the word

                fClusters.extend(cluster);

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, getClustersTrimmedWidth());

                fWords.extend(fClusters);

                break;

            } else if (cluster->run().isPlaceholder()) {

                if (!fClusters.empty()) {

                    // Placeholder ends the previous word

                    fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, getClustersTrimmedWidth());

                    fWords.extend(fClusters);

                }

                if (cluster->width() > maxWidth && fWords.empty()) {

                    // Placeholder is the only text and it's longer than the line;

                    // it does not count in fMinIntrinsicWidth

                    fClusters.extend(cluster);

                    fTooLongCluster = true;

                    fTooLongWord = true;

                } else {

                    // Placeholder does not fit the line; it will be considered again on the next line

                }

                break;

            }

            // Walk further to see if there is a too long word, cluster or glyph

            SkScalar nextWordLength = fClusters.width();

            SkScalar nextShortWordLength = nextWordLength;

            for (auto further = cluster; further != endOfClusters; ++further) {

                if (further->isSoftBreak() || further->isHardBreak() || further->isWhitespaceBreak()) {

                    break;

                }

                if (further->run().isPlaceholder()) {

                  // Placeholder ends the word

                  break;

                }

                if (nextWordLength > 0 && nextWordLength <= maxWidth && further->isIntraWordBreak()) {

                    // The cluster is spaces but not the end of the word in a normal sense

                    nextNonBreakingSpace = further;

                    nextShortWordLength = nextWordLength;

                }

                if (maxWidth == 0) {

                    // This is a tricky flutter case: layout(width:0) places 1 cluster on each line

                    nextWordLength = std::max(nextWordLength, further->width());

                } else {

                    nextWordLength += further->width();

                }

            }

            if (nextWordLength > maxWidth) {

                if (nextNonBreakingSpace != nullptr) {

                    // We only get here if the non-breaking space improves our situation

                    // (allows us to break the text to fit the word)

                    if (SkScalar shortLength = fWords.width() + nextShortWordLength;

                        !breaker.breakLine(shortLength)) {

                        // We can add the short word to the existing line

                        fClusters = TextStretch(fClusters.startCluster(), nextNonBreakingSpace, fClusters.metrics().getForceStrut());

                        fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, nextShortWordLength);

                        fWords.extend(fClusters);

                    } else {

                        // We can place the short word on the next line

                        fClusters.clean();

                    }

                    // Either way we are not in "word is too long" situation anymore

                    break;

                }

                // If the word is too long we can break it right now and hope it's enough

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, nextWordLength);

                if (fClusters.endPos() - fClusters.startPos() > 1 ||

                    fWords.empty()) {

                    fTooLongWord = true;

                } else {

                    // Even if the word is too long there is a very little space on this line.

                    // let's deal with it on the next line.

                }

            }

            if (cluster->width() > maxWidth) {

                fClusters.extend(cluster);

                fTooLongCluster = true;

                fTooLongWord = true;

            }

            break;

        }

        if (cluster->run().isPlaceholder()) {

            if (!fClusters.empty()) {

                // Placeholder ends the previous word (placeholders are ignored in trimming)

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, getClustersTrimmedWidth());

                fWords.extend(fClusters);

            }

            // Placeholder is separate word and its width now is counted in minIntrinsicWidth

            fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, cluster->width());

            fWords.extend(cluster);

        } else {

            fClusters.extend(cluster);

            // Keep adding clusters/words

            if (fClusters.endOfWord()) {

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, getClustersTrimmedWidth());

                fWords.extend(fClusters);

            }

        }

        if ((fHardLineBreak = cluster->isHardBreak())) {

            // Stop at the hard line break

            break;

        }

    }

}

void TextWrapper::moveForward(bool hasEllipsis) {

    // We normally break lines by words.

    // The only way we may go to clusters is if the word is too long or

    // it's the first word and it has an ellipsis attached to it.

    // If nothing fits we show the clipping.

    if (!fWords.empty()) {

        fEndLine.extend(fWords);

        if (!fTooLongWord || hasEllipsis) {

            return;

        }

    }

    if (!fClusters.empty()) {

        fEndLine.extend(fClusters);

        if (!fTooLongCluster) {

            return;

        }

    }

    if (!fClip.empty()) {

        // Flutter: forget the clipped cluster but keep the metrics

        fEndLine.metrics().add(fClip.metrics());

    }

}

// Special case for start/end cluster since they can be clipped

void TextWrapper::trimEndSpaces(TextAlign align) {

    // Remember the breaking position

    fEndLine.saveBreak();

    // Skip all space cluster at the end

    for (auto cluster = fEndLine.endCluster();

         cluster >= fEndLine.startCluster() && cluster->isWhitespaceBreak();

         --cluster) {

        fEndLine.trim(cluster);

    }

    fEndLine.trim();

}

SkScalar TextWrapper::getClustersTrimmedWidth() {

    // Move the end of the line to the left

    SkScalar width = 0;

    bool trailingSpaces = true;

    for (auto cluster = fClusters.endCluster(); cluster >= fClusters.startCluster(); --cluster) {

        if (cluster->run().isPlaceholder()) {

            continue;

        }

        if (trailingSpaces) {

            if (!cluster->isWhitespaceBreak()) {

                width += cluster->trimmedWidth(cluster->endPos());

                trailingSpaces = false;

            }

            continue;

        }

        width += cluster->width();

    }

    return width;

}

// Trim the beginning spaces in case of soft line break

std::tuple<Cluster*, size_t, SkScalar> TextWrapper::trimStartSpaces(Cluster* endOfClusters) {

    if (fHardLineBreak) {

        // End of line is always end of cluster, but need to skip \n

        auto width = fEndLine.width();

        auto cluster = fEndLine.endCluster() + 1;

        while (cluster < fEndLine.breakCluster() && cluster->isWhitespaceBreak())  {

            width += cluster->width();

            ++cluster;

        }

        return std::make_tuple(fEndLine.breakCluster() + 1, 0, width);

    }

    // breakCluster points to the end of the line;

    // It's a soft line break so we need to move lineStart forward skipping all the spaces

    auto width = fEndLine.widthWithGhostSpaces();

    auto cluster = fEndLine.breakCluster() + 1;

    while (cluster < endOfClusters && cluster->isWhitespaceBreak()) {

        width += cluster->width();

        ++cluster;

    }

    return std::make_tuple(cluster, 0, width);

}

// TODO: refactor the code for line ending (with/without ellipsis)

void TextWrapper::breakTextIntoLines(ParagraphImpl* parent,

                                     SkScalar maxWidth,

                                     const AddLineToParagraph& addLine) {

    fHeight = 0;

    fMinIntrinsicWidth = std::numeric_limits<SkScalar>::min();

    fMaxIntrinsicWidth = std::numeric_limits<SkScalar>::min();

    auto span = parent->clusters();

    if (span.size() == 0) {

        return;

    }

    auto maxLines = parent->paragraphStyle().getMaxLines();

    auto align = parent->paragraphStyle().effective_align();

    auto unlimitedLines = maxLines == std::numeric_limits<size_t>::max();

    auto endlessLine = !SkScalarIsFinite(maxWidth);

    auto hasEllipsis = parent->paragraphStyle().ellipsized();

    auto disableFirstAscent = parent->paragraphStyle().getTextHeightBehavior() & TextHeightBehavior::kDisableFirstAscent;

    auto disableLastDescent = parent->paragraphStyle().getTextHeightBehavior() & TextHeightBehavior::kDisableLastDescent;

    bool firstLine = true; // We only interested in fist line if we have to disable the first ascent

    SkScalar softLineMaxIntrinsicWidth = 0;

    fEndLine = TextStretch(span.begin(), span.begin(), parent->strutForceHeight());

    auto end = span.end() - 1;

    auto start = span.begin();

    InternalLineMetrics maxRunMetrics;

    bool needEllipsis = false;

    while (fEndLine.endCluster() != end) {

        lookAhead(maxWidth, end);

        auto lastLine = (hasEllipsis && unlimitedLines) || fLineNumber >= maxLines;

        needEllipsis = hasEllipsis && !endlessLine && lastLine;

        moveForward(needEllipsis);

        needEllipsis &= fEndLine.endCluster() < end - 1; // Only if we have some text to ellipsize

        // Do not trim end spaces on the naturally last line of the left aligned text

        trimEndSpaces(align);

        // For soft line breaks add to the line all the spaces next to it

        Cluster* startLine;

        size_t pos;

        SkScalar widthWithSpaces;

        std::tie(startLine, pos, widthWithSpaces) = trimStartSpaces(end);

        if (needEllipsis && !fHardLineBreak) {

            // This is what we need to do to preserve a space before the ellipsis

            fEndLine.restoreBreak();

            widthWithSpaces = fEndLine.widthWithGhostSpaces();

        }

        // If the line is empty with the hard line break, let's take the paragraph font (flutter???)

        if (fHardLineBreak && fEndLine.width() == 0) {

            fEndLine.setMetrics(parent->getEmptyMetrics());

        }

        // Deal with placeholder clusters == runs[@size==1]

        Run* lastRun = nullptr;

        for (auto cluster = fEndLine.startCluster(); cluster <= fEndLine.endCluster(); ++cluster) {

            auto r = cluster->runOrNull();

            if (r == lastRun) {

                continue;

            }

            lastRun = r;

            if (lastRun->placeholderStyle() != nullptr) {

                SkASSERT(lastRun->size() == 1);

                // Update the placeholder metrics so we can get the placeholder positions later

                // and the line metrics (to make sure the placeholder fits)

                lastRun->updateMetrics(&fEndLine.metrics());

            }

        }

        // Before we update the line metrics with struts,

        // let's save it for GetRectsForRange(RectHeightStyle::kMax)

        maxRunMetrics = fEndLine.metrics();

        maxRunMetrics.fForceStrut = false;

        if (parent->strutEnabled()) {

            // Make sure font metrics are not less than the strut

            parent->strutMetrics().updateLineMetrics(fEndLine.metrics());

        }

        // TODO: keep start/end/break info for text and runs but in a better way that below

        TextRange textExcludingSpaces(fEndLine.startCluster()->textRange().start, fEndLine.endCluster()->textRange().end);

        TextRange text(fEndLine.startCluster()->textRange().start, fEndLine.breakCluster()->textRange().start);

        TextRange textIncludingNewlines(fEndLine.startCluster()->textRange().start, startLine->textRange().start);

        if (startLine == end) {

            textIncludingNewlines.end = parent->text().size();

            text.end = parent->text().size();

        }

        ClusterRange clusters(fEndLine.startCluster() - start, fEndLine.endCluster() - start + 1);

        ClusterRange clustersWithGhosts(fEndLine.startCluster() - start, startLine - start);

        if (disableFirstAscent && firstLine) {

            fEndLine.metrics().fAscent = fEndLine.metrics().fRawAscent;

        }

        if (disableLastDescent && (lastLine || (startLine == end && !fHardLineBreak ))) {

            fEndLine.metrics().fDescent = fEndLine.metrics().fRawDescent;

        }

        SkScalar lineHeight = fEndLine.metrics().height();

        firstLine = false;

        if (fEndLine.empty()) {

            // Correct text and clusters (make it empty for an empty line)

            textExcludingSpaces.end = textExcludingSpaces.start;

            clusters.end = clusters.start;

        }

        // In case of a force wrapping we don't have a break cluster and have to use the end cluster

        text.end = std::max(text.end, textExcludingSpaces.end);

        addLine(textExcludingSpaces,

                text,

                textIncludingNewlines, clusters, clustersWithGhosts, widthWithSpaces,

                fEndLine.startPos(),

                fEndLine.endPos(),

                SkVector::Make(0, fHeight),

                SkVector::Make(fEndLine.width(), lineHeight),

                fEndLine.metrics(),

                needEllipsis && !fHardLineBreak);

        softLineMaxIntrinsicWidth += widthWithSpaces;

        fMaxIntrinsicWidth = std::max(fMaxIntrinsicWidth, softLineMaxIntrinsicWidth);

        if (fHardLineBreak) {

            softLineMaxIntrinsicWidth = 0;

        }

        // Start a new line

        fHeight += lineHeight;

        if (!fHardLineBreak || startLine != end) {

            fEndLine.clean();

        }

        fEndLine.startFrom(startLine, pos);

        parent->fMaxWidthWithTrailingSpaces = std::max(parent->fMaxWidthWithTrailingSpaces, widthWithSpaces);

        if (hasEllipsis && unlimitedLines) {

            // There is one case when we need an ellipsis on a separate line

            // after a line break when width is infinite

            if (!fHardLineBreak) {

                break;

            }

        } else if (lastLine) {

            // There is nothing more to draw

            fHardLineBreak = false;

            break;

        }

        ++fLineNumber;

    }

    // We finished formatting the text but we need to scan the rest for some numbers

    // TODO: make it a case of a normal flow

    if (fEndLine.endCluster() != nullptr) {

        auto lastWordLength = 0.0f;

        auto cluster = fEndLine.endCluster();

        while (cluster != end || cluster->endPos() < end->endPos()) {

            fExceededMaxLines = true;

            if (cluster->isHardBreak()) {

                // Hard line break ends the word and the line

                fMaxIntrinsicWidth = std::max(fMaxIntrinsicWidth, softLineMaxIntrinsicWidth);

                softLineMaxIntrinsicWidth = 0;

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, lastWordLength);

                lastWordLength = 0;

            } else if (cluster->isWhitespaceBreak()) {

                // Whitespaces end the word

                softLineMaxIntrinsicWidth += cluster->width();

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, lastWordLength);

                lastWordLength = 0;

            } else if (cluster->run().isPlaceholder()) {

                // Placeholder ends the previous word and creates a separate one

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, lastWordLength);

                // Placeholder width now counts in fMinIntrinsicWidth

                softLineMaxIntrinsicWidth += cluster->width();

                fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, cluster->width());

                lastWordLength = 0;

            } else {

                // Nothing out of ordinary - just add this cluster to the word and to the line

                softLineMaxIntrinsicWidth += cluster->width();

                lastWordLength += cluster->width();

            }

            ++cluster;

        }

        fMinIntrinsicWidth = std::max(fMinIntrinsicWidth, lastWordLength);

        fMaxIntrinsicWidth = std::max(fMaxIntrinsicWidth, softLineMaxIntrinsicWidth);

        if (parent->lines().empty()) {

            // In case we could not place even a single cluster on the line

            if (disableFirstAscent) {

                fEndLine.metrics().fAscent = fEndLine.metrics().fRawAscent;

            }

            if (disableLastDescent && !fHardLineBreak) {

                fEndLine.metrics().fDescent = fEndLine.metrics().fRawDescent;

            }

            fHeight = std::max(fHeight, fEndLine.metrics().height());

        }

    }

    if (fHardLineBreak) {

        // Last character is a line break

        if (parent->strutEnabled()) {

            // Make sure font metrics are not less than the strut

            parent->strutMetrics().updateLineMetrics(fEndLine.metrics());

        }

        if (disableLastDescent) {

            fEndLine.metrics().fDescent = fEndLine.metrics().fRawDescent;

        }

        ClusterRange clusters(fEndLine.breakCluster() - start, fEndLine.endCluster() - start);

        addLine(fEndLine.breakCluster()->textRange(),

                fEndLine.breakCluster()->textRange(),

                fEndLine.endCluster()->textRange(),

                clusters,

                clusters,

                0,

                0,

                0,

                SkVector::Make(0, fHeight),

                SkVector::Make(0, fEndLine.metrics().height()),

                fEndLine.metrics(),

                needEllipsis);

        fHeight += fEndLine.metrics().height();

        parent->lines().back().setMaxRunMetrics(maxRunMetrics);

    }

}

}  // namespace textlayout

}  // namespace skia