// Copyright (C) 2016 The Qt Company Ltd.

// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only

#include "qtextdocumentlayout_p.h"

#include "qtextdocument_p.h"

#include "qtextimagehandler_p.h"

#include "qtexttable.h"

#include "qtextlist.h"

#include "qtextengine_p.h"

#if QT_CONFIG(cssparser)

#include "private/qcssutil_p.h"

#endif

#include "private/qguiapplication_p.h"

#include "qabstracttextdocumentlayout_p.h"

#include "qcssparser_p.h"

#include <qpainter.h>

#include <qmath.h>

#include <qrect.h>

#include <qpalette.h>

#include <qdebug.h>

#include <qvarlengtharray.h>

#include <limits.h>

#include <qbasictimer.h>

#include "private/qfunctions_p.h"

#include <qloggingcategory.h>

#include <QtCore/qpointer.h>

#include <algorithm>

QT_BEGIN_NAMESPACE

Q_STATIC_LOGGING_CATEGORY(lcDraw, "qt.text.drawing")

Q_STATIC_LOGGING_CATEGORY(lcHit, "qt.text.hittest")

Q_LOGGING_CATEGORY(lcLayout, "qt.text.layout")

Q_STATIC_LOGGING_CATEGORY(lcTable, "qt.text.layout.table")

// ################ should probably add frameFormatChange notification!

struct QTextLayoutStruct;

class QTextFrameData : public QTextFrameLayoutData

{

public:

    QTextFrameData();

    // relative to parent frame

    QFixedPoint position;

    QFixedSize size;

    // contents starts at (margin+border/margin+border)

    QFixed topMargin;

    QFixed bottomMargin;

    QFixed leftMargin;

    QFixed rightMargin;

    QFixed border;

    QFixed padding;

    // contents width includes padding (as we need to treat this on a per cell basis for tables)

    QFixed contentsWidth;

    QFixed contentsHeight;

    QFixed oldContentsWidth;

    // accumulated margins

    QFixed effectiveTopMargin;

    QFixed effectiveBottomMargin;

    QFixed minimumWidth;

    QFixed maximumWidth;

    QTextLayoutStruct *currentLayoutStruct;

    bool sizeDirty;

    bool layoutDirty;

    QList<QPointer<QTextFrame>> floats;

};

QTextFrameData::QTextFrameData()

    : maximumWidth(QFIXED_MAX),

      currentLayoutStruct(nullptr), sizeDirty(true), layoutDirty(true)

{

}

struct QTextLayoutStruct {

    QTextLayoutStruct() : maximumWidth(QFIXED_MAX), fullLayout(false)

    {}

    QTextFrame *frame;

    QFixed x_left;

    QFixed x_right;

    QFixed frameY; // absolute y position of the current frame

    QFixed y; // always relative to the current frame

    QFixed contentsWidth;

    QFixed minimumWidth;

    QFixed maximumWidth;

    bool fullLayout;

    QList<QTextFrame *> pendingFloats;

    QFixed pageHeight;

    QFixed pageBottom;

    QFixed pageTopMargin;

    QFixed pageBottomMargin;

    QRectF updateRect;

    QRectF updateRectForFloats;

    inline void addUpdateRectForFloat(const QRectF &rect) {

        if (updateRectForFloats.isValid())

            updateRectForFloats |= rect;

        else

            updateRectForFloats = rect;

    }

    inline QFixed absoluteY() const

    { return frameY + y; }

    inline QFixed contentHeight() const

    { return pageHeight - pageBottomMargin - pageTopMargin; }

    inline int currentPage() const

    { return pageHeight == 0 ? 0 : (absoluteY() / pageHeight).truncate(); }

    inline void newPage()

    { if (pageHeight == QFIXED_MAX) return; pageBottom += pageHeight; y = qMax(y, pageBottom - pageHeight + pageBottomMargin + pageTopMargin - frameY); }

};

#ifndef QT_NO_CSSPARSER

// helper struct to collect edge data and priorize edges for border-collapse mode

struct EdgeData {

    enum EdgeClass {

        // don't change order, used for comparison

        ClassInvalid,     // queried (adjacent) cell does not exist

        ClassNone,        // no explicit border, no grid, no table border

        ClassGrid,        // 1px grid if drawGrid is true

        ClassTableBorder, // an outermost edge

        ClassExplicit     // set in cell's format

    };

    EdgeData(qreal width, const QTextTableCell &cell, QCss::Edge edge, EdgeClass edgeClass) :

        width(width), cell(cell), edge(edge), edgeClass(edgeClass) {}

    EdgeData() :

        width(0), edge(QCss::NumEdges), edgeClass(ClassInvalid) {}

    // used for priorization with qMax

    bool operator< (const EdgeData &other) const {

        if (width < other.width) return true;

        if (width > other.width) return false;

        if (edgeClass < other.edgeClass) return true;

        if (edgeClass > other.edgeClass) return false;

        if (edge == QCss::TopEdge && other.edge == QCss::BottomEdge) return true;

        if (edge == QCss::BottomEdge && other.edge == QCss::TopEdge) return false;

        if (edge == QCss::LeftEdge && other.edge == QCss::RightEdge) return true;

        return false;

    }

    bool operator> (const EdgeData &other) const {

        return other < *this;

    }

    qreal width;

    QTextTableCell cell;

    QCss::Edge edge;

    EdgeClass edgeClass;

};

// axisEdgeData is referenced by QTextTableData's inline methods, so predeclare

class QTextTableData;

static inline EdgeData axisEdgeData(QTextTable *table, const QTextTableData *td, const QTextTableCell &cell, QCss::Edge edge);

#endif

class QTextTableData : public QTextFrameData

{

public:

    QFixed cellSpacing, cellPadding;

    qreal deviceScale;

    QList<QFixed> minWidths;

    QList<QFixed> maxWidths;

    QList<QFixed> widths;

    QList<QFixed> heights;

    QList<QFixed> columnPositions;

    QList<QFixed> rowPositions;

    QList<QFixed> cellVerticalOffsets;

    // without borderCollapse, those equal QTextFrameData::border;

    // otherwise the widest outermost cell edge will be used

    QFixed effectiveLeftBorder;

    QFixed effectiveTopBorder;

    QFixed effectiveRightBorder;

    QFixed effectiveBottomBorder;

    QFixed headerHeight;

    QFixed borderCell; // 0 if borderCollapse is enabled, QTextFrameData::border otherwise

    bool borderCollapse;

    bool drawGrid;

    // maps from cell index (row + col * rowCount) to child frames belonging to

    // the specific cell

    QMultiHash<int, QTextFrame *> childFrameMap;

    inline QFixed cellWidth(int column, int colspan) const

    { return columnPositions.at(column + colspan - 1) + widths.at(column + colspan - 1)

             - columnPositions.at(column); }

    inline void calcRowPosition(int row)

    {

        if (row > 0)

            rowPositions[row] = rowPositions.at(row - 1) + heights.at(row - 1) + borderCell + cellSpacing + borderCell;

    }

    QRectF cellRect(const QTextTableCell &cell) const;

    inline QFixed paddingProperty(const QTextFormat &format, QTextFormat::Property property) const

    {

        QVariant v = format.property(property);

        if (v.isNull()) {

            return cellPadding;

        } else {

            Q_ASSERT(v.userType() == QMetaType::Double || v.userType() == QMetaType::Float);

            return QFixed::fromReal(v.toReal() * deviceScale);

        }

    }

#ifndef QT_NO_CSSPARSER

    inline QFixed cellBorderWidth(QTextTable *table, const QTextTableCell &cell, QCss::Edge edge) const

    {

        qreal rv = axisEdgeData(table, this, cell, edge).width;

        if (borderCollapse)

            rv /= 2; // each cell has to add half of the border's width to its own padding

        return QFixed::fromReal(rv * deviceScale);

    }

#endif

    inline QFixed topPadding(QTextTable *table, const QTextTableCell &cell) const

    {

#ifdef QT_NO_CSSPARSER

        Q_UNUSED(table);

#endif

        return paddingProperty(cell.format(), QTextFormat::TableCellTopPadding)

#ifndef QT_NO_CSSPARSER

                + cellBorderWidth(table, cell, QCss::TopEdge)

#endif

        ;

    }

    inline QFixed bottomPadding(QTextTable *table, const QTextTableCell &cell) const

    {

#ifdef QT_NO_CSSPARSER

        Q_UNUSED(table);

#endif

        return paddingProperty(cell.format(), QTextFormat::TableCellBottomPadding)

#ifndef QT_NO_CSSPARSER

                + cellBorderWidth(table, cell, QCss::BottomEdge)

#endif

                ;

    }

    inline QFixed leftPadding(QTextTable *table, const QTextTableCell &cell) const

    {

#ifdef QT_NO_CSSPARSER

        Q_UNUSED(table);

#endif

        return paddingProperty(cell.format(), QTextFormat::TableCellLeftPadding)

#ifndef QT_NO_CSSPARSER

                + cellBorderWidth(table, cell, QCss::LeftEdge)

#endif

        ;

    }

    inline QFixed rightPadding(QTextTable *table, const QTextTableCell &cell) const

    {

#ifdef QT_NO_CSSPARSER

        Q_UNUSED(table);

#endif

        return paddingProperty(cell.format(), QTextFormat::TableCellRightPadding)

#ifndef QT_NO_CSSPARSER

                + cellBorderWidth(table, cell, QCss::RightEdge)

#endif

        ;

    }

    inline QFixedPoint cellPosition(QTextTable *table, const QTextTableCell &cell) const

    {

        return cellPosition(cell.row(), cell.column()) + QFixedPoint(leftPadding(table, cell), topPadding(table, cell));

    }

    void updateTableSize();

private:

    inline QFixedPoint cellPosition(int row, int col) const

    { return QFixedPoint(columnPositions.at(col), rowPositions.at(row) + cellVerticalOffsets.at(col + row * widths.size())); }

};

static QTextFrameData *createData(QTextFrame *f)

{

    QTextFrameData *data;

    if (qobject_cast<QTextTable *>(f))

        data = new QTextTableData;

    else

        data = new QTextFrameData;

    f->setLayoutData(data);

    return data;

}

static inline QTextFrameData *data(QTextFrame *f)

{

    QTextFrameData *data = static_cast<QTextFrameData *>(f->layoutData());

    if (!data)

        data = createData(f);

    return data;

}

static bool isFrameFromInlineObject(QTextFrame *f)

{

    return f->firstPosition() > f->lastPosition();

}

void QTextTableData::updateTableSize()

{

    const QFixed effectiveTopMargin = this->topMargin + effectiveTopBorder + padding;

    const QFixed effectiveBottomMargin = this->bottomMargin + effectiveBottomBorder + padding;

    const QFixed effectiveLeftMargin = this->leftMargin + effectiveLeftBorder + padding;

    const QFixed effectiveRightMargin = this->rightMargin + effectiveRightBorder + padding;

    size.height = contentsHeight == -1

                   ? rowPositions.constLast() + heights.constLast() + padding + border + cellSpacing + effectiveBottomMargin

                   : effectiveTopMargin + contentsHeight + effectiveBottomMargin;

    size.width = effectiveLeftMargin + contentsWidth + effectiveRightMargin;

}

QRectF QTextTableData::cellRect(const QTextTableCell &cell) const

{

    const int row = cell.row();

    const int rowSpan = cell.rowSpan();

    const int column = cell.column();

    const int colSpan = cell.columnSpan();

    return QRectF(columnPositions.at(column).toReal(),

                  rowPositions.at(row).toReal(),

                  (columnPositions.at(column + colSpan - 1) + widths.at(column + colSpan - 1) - columnPositions.at(column)).toReal(),

                  (rowPositions.at(row + rowSpan - 1) + heights.at(row + rowSpan - 1) - rowPositions.at(row)).toReal());

}

static inline bool isEmptyBlockBeforeTable(const QTextBlock &block, const QTextBlockFormat &format, const QTextFrame::Iterator &nextIt)

{

    return !nextIt.atEnd()

           && qobject_cast<QTextTable *>(nextIt.currentFrame())

           && block.isValid()

           && block.length() == 1

           && !format.hasProperty(QTextFormat::BlockTrailingHorizontalRulerWidth)

           && !format.hasProperty(QTextFormat::BackgroundBrush)

           && nextIt.currentFrame()->firstPosition() == block.position() + 1

           ;

}

static inline bool isEmptyBlockBeforeTable(const QTextFrame::Iterator &it)

{

    QTextFrame::Iterator next = it; ++next;

    if (it.currentFrame())

        return false;

    QTextBlock block = it.currentBlock();

    return isEmptyBlockBeforeTable(block, block.blockFormat(), next);

}

static inline bool isEmptyBlockAfterTable(const QTextBlock &block, const QTextFrame *previousFrame)

{

    return qobject_cast<const QTextTable *>(previousFrame)

           && block.isValid()

           && block.length() == 1

           && previousFrame->lastPosition() == block.position() - 1

           ;

}

static inline bool isLineSeparatorBlockAfterTable(const QTextBlock &block, const QTextFrame *previousFrame)

{

    return qobject_cast<const QTextTable *>(previousFrame)

           && block.isValid()

           && block.length() > 1

           && block.text().at(0) == QChar::LineSeparator

           && previousFrame->lastPosition() == block.position() - 1

           ;

}

/*

Optimization strategies:

HTML layout:

* Distinguish between normal and special flow. For normal flow the condition:

  y1 > y2 holds for all blocks with b1.key() > b2.key().

* Special flow is: floats, table cells

* Normal flow within table cells. Tables (not cells) are part of the normal flow.

* If blocks grows/shrinks in height and extends over whole page width at the end, move following blocks.

* If height doesn't change, no need to do anything

Table cells:

* If minWidth of cell changes, recalculate table width, relayout if needed.

* What about maxWidth when doing auto layout?

Floats:

* need fixed or proportional width, otherwise don't float!

* On width/height change relayout surrounding paragraphs.

Document width change:

* full relayout needed

Float handling:

* Floats are specified by a special format object.

* currently only floating images are implemented.

*/

/*

   On the table layouting:

   +---[ table border ]-------------------------

   |      [ cell spacing ]

   |  +------[ cell border ]-----+  +--------

   |  |                          |  |

   |  |

   |  |

   |  |

   |

   rowPositions[i] and columnPositions[i] point at the cell content

   position. So for example the left border is drawn at

   x = columnPositions[i] - fd->border and similar for y.

*/

struct QCheckPoint

{

    QFixed y;

    QFixed frameY; // absolute y position of the current frame

    int positionInFrame;

    QFixed minimumWidth;

    QFixed maximumWidth;

    QFixed contentsWidth;

};

Q_DECLARE_TYPEINFO(QCheckPoint, Q_PRIMITIVE_TYPE);

static bool operator<(const QCheckPoint &checkPoint, QFixed y)

{

    return checkPoint.y < y;

}

static bool operator<(const QCheckPoint &checkPoint, int pos)

{

    return checkPoint.positionInFrame < pos;

}

static void fillBackground(QPainter *p, const QRectF &rect, QBrush brush, const QPointF &origin, const QRectF &gradientRect = QRectF())

{

    p->save();

    if (brush.style() >= Qt::LinearGradientPattern && brush.style() <= Qt::ConicalGradientPattern) {

        if (!gradientRect.isNull()) {

            QTransform m;

            m.translate(gradientRect.left(), gradientRect.top());

            m.scale(gradientRect.width(), gradientRect.height());

            brush.setTransform(m);

            const_cast<QGradient *>(brush.gradient())->setCoordinateMode(QGradient::LogicalMode);

        }

    } else {

        p->setBrushOrigin(origin);

    }

    p->fillRect(rect, brush);

    p->restore();

}

class QTextDocumentLayoutPrivate : public QAbstractTextDocumentLayoutPrivate

{

    Q_DECLARE_PUBLIC(QTextDocumentLayout)

public:

    QTextDocumentLayoutPrivate();

    QTextOption::WrapMode wordWrapMode;

#ifdef LAYOUT_DEBUG

    mutable QString debug_indent;

#endif

    int fixedColumnWidth;

    int cursorWidth;

    QSizeF lastReportedSize;

    QRectF viewportRect;

    QRectF clipRect;

    mutable int currentLazyLayoutPosition;

    mutable int lazyLayoutStepSize;

    QBasicTimer layoutTimer;

    mutable QBasicTimer sizeChangedTimer;

    uint showLayoutProgress : 1;

    uint insideDocumentChange : 1;

    int lastPageCount;

    qreal idealWidth;

    bool contentHasAlignment;

    QFixed blockIndent(const QTextBlockFormat &blockFormat) const;

    void drawFrame(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,

                   QTextFrame *f) const;

    void drawFlow(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,

                  QTextFrame::Iterator it, const QList<QTextFrame *> &floats, QTextBlock *cursorBlockNeedingRepaint) const;

    void drawBlock(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,

                   const QTextBlock &bl, bool inRootFrame) const;

    void drawListItem(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,

                      const QTextBlock &bl, const QTextCharFormat *selectionFormat) const;

    void drawTableCellBorder(const QRectF &cellRect, QPainter *painter, QTextTable *table, QTextTableData *td, const QTextTableCell &cell) const;

    void drawTableCell(const QRectF &cellRect, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &cell_context,

                       QTextTable *table, QTextTableData *td, int r, int c,

                       QTextBlock *cursorBlockNeedingRepaint, QPointF *cursorBlockOffset) const;

    void drawBorder(QPainter *painter, const QRectF &rect, qreal topMargin, qreal bottomMargin, qreal border,

                    const QBrush &brush, QTextFrameFormat::BorderStyle style) const;

    void drawFrameDecoration(QPainter *painter, QTextFrame *frame, QTextFrameData *fd, const QRectF &clip, const QRectF &rect) const;

    enum HitPoint {

        PointBefore,

        PointAfter,

        PointInside,

        PointExact

    };

    HitPoint hitTest(QTextFrame *frame, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;

    HitPoint hitTest(QTextFrame::Iterator it, HitPoint hit, const QFixedPoint &p,

                     int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;

    HitPoint hitTest(QTextTable *table, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;

    HitPoint hitTest(const QTextBlock &bl, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;

    QTextLayoutStruct layoutCell(QTextTable *t, const QTextTableCell &cell, QFixed width,

                                 int layoutFrom, int layoutTo, QTextTableData *tableData, QFixed absoluteTableY,

                                 bool withPageBreaks);

    void setCellPosition(QTextTable *t, const QTextTableCell &cell, const QPointF &pos);

    QRectF layoutTable(QTextTable *t, int layoutFrom, int layoutTo, QFixed parentY);

    void positionFloat(QTextFrame *frame, QTextLine *currentLine = nullptr);

    // calls the next one

    QRectF layoutFrame(QTextFrame *f, int layoutFrom, int layoutTo, QFixed parentY = 0);

    QRectF layoutFrame(QTextFrame *f, int layoutFrom, int layoutTo, QFixed frameWidth, QFixed frameHeight, QFixed parentY = 0);

    void layoutBlock(const QTextBlock &bl, int blockPosition, const QTextBlockFormat &blockFormat,

                     QTextLayoutStruct *layoutStruct, int layoutFrom, int layoutTo, const QTextBlockFormat *previousBlockFormat);

    void layoutFlow(QTextFrame::Iterator it, QTextLayoutStruct *layoutStruct, int layoutFrom, int layoutTo, QFixed width = 0);

    void floatMargins(QFixed y, const QTextLayoutStruct *layoutStruct, QFixed *left, QFixed *right) const;

    QFixed findY(QFixed yFrom, const QTextLayoutStruct *layoutStruct, QFixed requiredWidth) const;

    QList<QCheckPoint> checkPoints;

    QTextFrame::Iterator frameIteratorForYPosition(QFixed y) const;

    QTextFrame::Iterator frameIteratorForTextPosition(int position) const;

    void ensureLayouted(QFixed y) const;

    void ensureLayoutedByPosition(int position) const;

    inline void ensureLayoutFinished() const

    { ensureLayoutedByPosition(INT_MAX); }

    void layoutStep() const;

    QRectF frameBoundingRectInternal(QTextFrame *frame) const;

    qreal scaleToDevice(qreal value) const;

    QFixed scaleToDevice(QFixed value) const;

};

QTextDocumentLayoutPrivate::QTextDocumentLayoutPrivate()

    : fixedColumnWidth(-1),

      cursorWidth(1),

      currentLazyLayoutPosition(-1),

      lazyLayoutStepSize(1000),

      lastPageCount(-1)

{

    showLayoutProgress = true;

    insideDocumentChange = false;

    idealWidth = 0;

    contentHasAlignment = false;

}

QTextFrame::Iterator QTextDocumentLayoutPrivate::frameIteratorForYPosition(QFixed y) const

{

    QTextFrame *rootFrame = document->rootFrame();

    if (checkPoints.isEmpty()

        || y < 0 || y > data(rootFrame)->size.height)

        return rootFrame->begin();

    auto checkPoint = std::lower_bound(checkPoints.begin(), checkPoints.end(), y);

    if (checkPoint == checkPoints.end())

        return rootFrame->begin();

    if (checkPoint != checkPoints.begin())

        --checkPoint;

    const int position = rootFrame->firstPosition() + checkPoint->positionInFrame;

    return frameIteratorForTextPosition(position);

}

QTextFrame::Iterator QTextDocumentLayoutPrivate::frameIteratorForTextPosition(int position) const

{

    QTextFrame *rootFrame = docPrivate->rootFrame();

    const QTextDocumentPrivate::BlockMap &map = docPrivate->blockMap();

    const int begin = map.findNode(rootFrame->firstPosition());

    const int end = map.findNode(rootFrame->lastPosition()+1);

    const int block = map.findNode(position);

    const int blockPos = map.position(block);

    QTextFrame::iterator it(rootFrame, block, begin, end);

    QTextFrame *containingFrame = docPrivate->frameAt(blockPos);

    if (containingFrame != rootFrame) {

        while (containingFrame->parentFrame() != rootFrame) {

            containingFrame = containingFrame->parentFrame();

            Q_ASSERT(containingFrame);

        }

        it.cf = containingFrame;

        it.cb = 0;

    }

    return it;

}

QTextDocumentLayoutPrivate::HitPoint

QTextDocumentLayoutPrivate::hitTest(QTextFrame *frame, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const

{

    QTextFrameData *fd = data(frame);

    // #########

    if (fd->layoutDirty)

        return PointAfter;

    Q_ASSERT(!fd->layoutDirty);

    Q_ASSERT(!fd->sizeDirty);

    const QFixedPoint relativePoint(point.x - fd->position.x, point.y - fd->position.y);

    QTextFrame *rootFrame = docPrivate->rootFrame();

    qCDebug(lcHit) << "checking frame" << frame->firstPosition() << "point=" << point.toPointF()

                   << "position" << fd->position.toPointF() << "size" << fd->size.toSizeF();

    if (frame != rootFrame) {

        if (relativePoint.y < 0 || relativePoint.x < 0) {

            *position = frame->firstPosition() - 1;

            qCDebug(lcHit) << "before pos=" << *position;

            return PointBefore;

        } else if (relativePoint.y > fd->size.height || relativePoint.x > fd->size.width) {

            *position = frame->lastPosition() + 1;

            qCDebug(lcHit) << "after pos=" << *position;

            return PointAfter;

        }

    }

    if (isFrameFromInlineObject(frame)) {

        *position = frame->firstPosition() - 1;

        return PointExact;

    }

    if (QTextTable *table = qobject_cast<QTextTable *>(frame)) {

        const int rows = table->rows();

        const int columns = table->columns();

        QTextTableData *td = static_cast<QTextTableData *>(data(table));

        if (!td->childFrameMap.isEmpty()) {

            for (int r = 0; r < rows; ++r) {

                for (int c = 0; c < columns; ++c) {

                    QTextTableCell cell = table->cellAt(r, c);

                    if (cell.row() != r || cell.column() != c)

                        continue;

                    QRectF cellRect = td->cellRect(cell);

                    const QFixedPoint cellPos = QFixedPoint::fromPointF(cellRect.topLeft());

                    const QFixedPoint pointInCell = relativePoint - cellPos;

                    const QList<QTextFrame *> childFrames = td->childFrameMap.values(r + c * rows);

                    for (int i = 0; i < childFrames.size(); ++i) {

                        QTextFrame *child = childFrames.at(i);

                        if (isFrameFromInlineObject(child)

                            && child->frameFormat().position() != QTextFrameFormat::InFlow

                            && hitTest(child, pointInCell, position, l, accuracy) == PointExact)

                        {

                            return PointExact;

                        }

                    }

                }

            }

        }

        return hitTest(table, relativePoint, position, l, accuracy);

    }

    const QList<QTextFrame *> childFrames = frame->childFrames();

    for (int i = 0; i < childFrames.size(); ++i) {

        QTextFrame *child = childFrames.at(i);

        if (isFrameFromInlineObject(child)

            && child->frameFormat().position() != QTextFrameFormat::InFlow

            && hitTest(child, relativePoint, position, l, accuracy) == PointExact)

        {

            return PointExact;

        }

    }

    QTextFrame::Iterator it = frame->begin();

    if (frame == rootFrame) {

        it = frameIteratorForYPosition(relativePoint.y);

        Q_ASSERT(it.parentFrame() == frame);

    }

    if (it.currentFrame())

        *position = it.currentFrame()->firstPosition();

    else

        *position = it.currentBlock().position();

    return hitTest(it, PointBefore, relativePoint, position, l, accuracy);

}

QTextDocumentLayoutPrivate::HitPoint

QTextDocumentLayoutPrivate::hitTest(QTextFrame::Iterator it, HitPoint hit, const QFixedPoint &p,

                                    int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const

{

    for (; !it.atEnd(); ++it) {

        QTextFrame *c = it.currentFrame();

        HitPoint hp;

        int pos = -1;

        if (c) {

            hp = hitTest(c, p, &pos, l, accuracy);

        } else {

            hp = hitTest(it.currentBlock(), p, &pos, l, accuracy);

        }

        if (hp >= PointInside) {

            if (isEmptyBlockBeforeTable(it))

                continue;

            hit = hp;

            *position = pos;

            break;

        }

        if (hp == PointBefore && pos < *position) {

            *position = pos;

            hit = hp;

        } else if (hp == PointAfter && pos > *position) {

            *position = pos;

            hit = hp;

        }

    }

    qCDebug(lcHit) << "inside=" << hit << " pos=" << *position;

    return hit;

}

QTextDocumentLayoutPrivate::HitPoint

QTextDocumentLayoutPrivate::hitTest(QTextTable *table, const QFixedPoint &point,

                                    int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const

{

    QTextTableData *td = static_cast<QTextTableData *>(data(table));

    auto rowIt = std::lower_bound(td->rowPositions.constBegin(), td->rowPositions.constEnd(), point.y);

    if (rowIt == td->rowPositions.constEnd()) {

        rowIt = td->rowPositions.constEnd() - 1;

    } else if (rowIt != td->rowPositions.constBegin()) {

        --rowIt;

    }

    auto colIt = std::lower_bound(td->columnPositions.constBegin(), td->columnPositions.constEnd(), point.x);

    if (colIt == td->columnPositions.constEnd()) {

        colIt = td->columnPositions.constEnd() - 1;

    } else if (colIt != td->columnPositions.constBegin()) {

        --colIt;

    }

    QTextTableCell cell = table->cellAt(rowIt - td->rowPositions.constBegin(),

                                        colIt - td->columnPositions.constBegin());

    if (!cell.isValid())

        return PointBefore;

    *position = cell.firstPosition();

    HitPoint hp = hitTest(cell.begin(), PointInside, point - td->cellPosition(table, cell), position, l, accuracy);

    if (hp == PointExact)

        return hp;

    if (hp == PointAfter)

        *position = cell.lastPosition();

    return PointInside;

}

QTextDocumentLayoutPrivate::HitPoint

QTextDocumentLayoutPrivate::hitTest(const QTextBlock &bl, const QFixedPoint &point, int *position, QTextLayout **l,

                                    Qt::HitTestAccuracy accuracy) const

{

    QTextLayout *tl = bl.layout();

    QRectF textrect = tl->boundingRect();

    textrect.translate(tl->position());

    qCDebug(lcHit) << "    checking block" << bl.position() << "point=" << point.toPointF() << "    tlrect" << textrect;

    *position = bl.position();

    if (point.y.toReal() < textrect.top() - bl.blockFormat().topMargin()) {

        qCDebug(lcHit) << "    before pos=" << *position;

        return PointBefore;

    } else if (point.y.toReal() > textrect.bottom()) {

        *position += bl.length();

        qCDebug(lcHit) << "    after pos=" << *position;

        return PointAfter;

    }

    QPointF pos = point.toPointF() - tl->position();

    // ### rtl?

    HitPoint hit = PointInside;

    *l = tl;

    int off = 0;

    for (int i = 0; i < tl->lineCount(); ++i) {

        QTextLine line = tl->lineAt(i);

        const QRectF lr = line.naturalTextRect();

        if (lr.top() > pos.y()) {

            off = qMin(off, line.textStart());

        } else if (lr.bottom() <= pos.y()) {

            off = qMax(off, line.textStart() + line.textLength());

        } else {

            if (lr.left() <= pos.x() && lr.right() >= pos.x())

                hit = PointExact;

            // when trying to hit an anchor we want it to hit not only in the left

            // half

            if (accuracy == Qt::ExactHit)

                off = line.xToCursor(pos.x(), QTextLine::CursorOnCharacter);

            else

                off = line.xToCursor(pos.x(), QTextLine::CursorBetweenCharacters);

            break;

        }

    }

    *position += off;

    qCDebug(lcHit) << "    inside=" << hit << " pos=" << *position;

    return hit;

}

// ### could be moved to QTextBlock

QFixed QTextDocumentLayoutPrivate::blockIndent(const QTextBlockFormat &blockFormat) const

{

    qreal indent = blockFormat.indent();

    QTextObject *object = document->objectForFormat(blockFormat);

    if (object)

        indent += object->format().toListFormat().indent();

    if (qIsNull(indent))

        return 0;

    qreal scale = 1;

    if (paintDevice) {

        scale = qreal(paintDevice->logicalDpiY()) / qreal(qt_defaultDpi());

    }

    return QFixed::fromReal(indent * scale * document->indentWidth());

}

struct BorderPaginator

{

    BorderPaginator(QTextDocument *document, const QRectF &rect, qreal topMarginAfterPageBreak, qreal bottomMargin, qreal border) :

        pageHeight(document->pageSize().height()),

        topPage(pageHeight > 0 ? static_cast<int>(rect.top() / pageHeight) : 0),

        bottomPage(pageHeight > 0 ? static_cast<int>((rect.bottom() + border) / pageHeight) : 0),

        rect(rect),

        topMarginAfterPageBreak(topMarginAfterPageBreak),

        bottomMargin(bottomMargin), border(border)

    {}

    QRectF clipRect(int page) const

    {

        QRectF clipped = rect.toRect();

        if (topPage != bottomPage) {

            clipped.setTop(qMax(clipped.top(), page * pageHeight + topMarginAfterPageBreak - border));

            clipped.setBottom(qMin(clipped.bottom(), (page + 1) * pageHeight - bottomMargin));

            if (clipped.bottom() <= clipped.top())

                return QRectF();

        }

        return clipped;

    }

    qreal pageHeight;

    int topPage;

    int bottomPage;

    QRectF rect;

    qreal topMarginAfterPageBreak;

    qreal bottomMargin;

    qreal border;

};

void QTextDocumentLayoutPrivate::drawBorder(QPainter *painter, const QRectF &rect, qreal topMargin, qreal bottomMargin,

                                            qreal border, const QBrush &brush, QTextFrameFormat::BorderStyle style) const

{

    BorderPaginator paginator(document, rect, topMargin, bottomMargin, border);

#ifndef QT_NO_CSSPARSER

    QCss::BorderStyle cssStyle = static_cast<QCss::BorderStyle>(style + 1);

#else

    Q_UNUSED(style);

#endif //QT_NO_CSSPARSER

    bool turn_off_antialiasing = !(painter->renderHints() & QPainter::Antialiasing);

    painter->setRenderHint(QPainter::Antialiasing);

    for (int i = paginator.topPage; i <= paginator.bottomPage; ++i) {

        QRectF clipped = paginator.clipRect(i);

        if (!clipped.isValid())

            continue;

#ifndef QT_NO_CSSPARSER

        qDrawEdge(painter, clipped.left(), clipped.top(), clipped.left() + border, clipped.bottom() + border, 0, 0, QCss::LeftEdge, cssStyle, brush);

        qDrawEdge(painter, clipped.left() + border, clipped.top(), clipped.right() + border, clipped.top() + border, 0, 0, QCss::TopEdge, cssStyle, brush);

        qDrawEdge(painter, clipped.right(), clipped.top() + border, clipped.right() + border, clipped.bottom(), 0, 0, QCss::RightEdge, cssStyle, brush);

        qDrawEdge(painter, clipped.left() + border, clipped.bottom(), clipped.right() + border, clipped.bottom() + border, 0, 0, QCss::BottomEdge, cssStyle, brush);

#else

        painter->save();

        painter->setPen(Qt::NoPen);

        painter->setBrush(brush);

        painter->drawRect(QRectF(clipped.left(), clipped.top(), clipped.left() + border, clipped.bottom() + border));

        painter->drawRect(QRectF(clipped.left() + border, clipped.top(), clipped.right() + border, clipped.top() + border));

        painter->drawRect(QRectF(clipped.right(), clipped.top() + border, clipped.right() + border, clipped.bottom()));

        painter->drawRect(QRectF(clipped.left() + border, clipped.bottom(), clipped.right() + border, clipped.bottom() + border));

        painter->restore();

#endif //QT_NO_CSSPARSER

    }

    if (turn_off_antialiasing)

        painter->setRenderHint(QPainter::Antialiasing, false);

}

void QTextDocumentLayoutPrivate::drawFrameDecoration(QPainter *painter, QTextFrame *frame, QTextFrameData *fd, const QRectF &clip, const QRectF &rect) const

{

    const QBrush bg = frame->frameFormat().background();

    if (bg != Qt::NoBrush) {

        QRectF bgRect = rect;

        bgRect.adjust((fd->leftMargin + fd->border).toReal(),

                      (fd->topMargin + fd->border).toReal(),

                      - (fd->rightMargin + fd->border).toReal(),

                      - (fd->bottomMargin + fd->border).toReal());

        QRectF gradientRect; // invalid makes it default to bgRect

        QPointF origin = bgRect.topLeft();