/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qtextdocumentlayout_p.h"

#include "qtextdocument_p.h"

#include "qtextimagehandler_p.h"

#include "qtexttable.h"

#include "qtextlist.h"

#include "qtextengine_p.h"

#include "private/qcssutil_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 <qstyle.h>

#include <qbasictimer.h>

#include "private/qfunctions_p.h"

// #define LAYOUT_DEBUG

#ifdef LAYOUT_DEBUG

#define LDEBUG qDebug()

#define INC_INDENT debug_indent += "  "

#define DEC_INDENT debug_indent = debug_indent.left(debug_indent.length()-2)

#else

#define LDEBUG if(0) qDebug()

#define INC_INDENT do {} while(0)

#define DEC_INDENT do {} while(0)

#endif

QT_BEGIN_NAMESPACE

extern int qt_defaultDpi();

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

struct QLayoutStruct;

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;

    QLayoutStruct *currentLayoutStruct;

    bool sizeDirty;

    bool layoutDirty;

    QList<QPointer<QTextFrame> > floats;

};

QTextFrameData::QTextFrameData()

    : maximumWidth(QFIXED_MAX),

      currentLayoutStruct(0), sizeDirty(true), layoutDirty(true)

{

}

struct QLayoutStruct {

    QLayoutStruct() : 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 int currentPage() const

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

    inline void newPage()

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

};

class QTextTableData : public QTextFrameData

{

public:

    QFixed cellSpacing, cellPadding;

    qreal deviceScale;

    QVector<QFixed> minWidths;

    QVector<QFixed> maxWidths;

    QVector<QFixed> widths;

    QVector<QFixed> heights;

    QVector<QFixed> columnPositions;

    QVector<QFixed> rowPositions;

    QVector<QFixed> cellVerticalOffsets;

    QFixed headerHeight;

    // 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) + border + cellSpacing + border;

    }

    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() == QVariant::Double || v.userType() == QMetaType::Float);

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

        }

    }

    inline QFixed topPadding(const QTextFormat &format) const

    {

        return paddingProperty(format, QTextFormat::TableCellTopPadding);

    }

    inline QFixed bottomPadding(const QTextFormat &format) const

    {

        return paddingProperty(format, QTextFormat::TableCellBottomPadding);

    }

    inline QFixed leftPadding(const QTextFormat &format) const

    {

        return paddingProperty(format, QTextFormat::TableCellLeftPadding);

    }

    inline QFixed rightPadding(const QTextFormat &format) const

    {

        return paddingProperty(format, QTextFormat::TableCellRightPadding);

    }

    inline QFixedPoint cellPosition(const QTextTableCell &cell) const

    {

        const QTextFormat fmt = cell.format();

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

    }

    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 + border + padding;

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

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

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

    size.height = contentsHeight == -1

                   ? rowPositions.last() + heights.last() + 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(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

           ;

}

/*

Optimisation 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);

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

{

    return checkPoint.y < y;

}

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

{

    return checkPoint.positionInFrame < pos;

}

static void fillBackground(QPainter *p, const QRectF &rect, QBrush brush, const QPointF &origin, 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,

                   QTextBlock bl, bool inRootFrame) const;

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

                      QTextBlock bl, const QTextCharFormat *selectionFormat) 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(QTextBlock bl, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;

    QLayoutStruct 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 = 0);

    // 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,

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

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

    void pageBreakInsideTable(QTextTable *table, QLayoutStruct *layoutStruct);

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

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

    QVector<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();

    QVector<QCheckPoint>::ConstIterator checkPoint = qLowerBound(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();

//     LDEBUG << "checking frame" << frame->firstPosition() << "point=" << point

//            << "position" << fd->position << "size" << fd->size;

    if (frame != rootFrame) {

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

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

//             LDEBUG << "before pos=" << *position;

            return PointBefore;

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

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

//             LDEBUG << "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

{

    INC_INDENT;

    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;

        }

    }

    DEC_INDENT;

//     LDEBUG << "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));

    QVector<QFixed>::ConstIterator rowIt = qLowerBound(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;

    }

    QVector<QFixed>::ConstIterator colIt = qLowerBound(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(cell), position, l, accuracy);

    if (hp == PointExact)

        return hp;

    if (hp == PointAfter)

        *position = cell.lastPosition();

    return PointInside;

}

QTextDocumentLayoutPrivate::HitPoint

QTextDocumentLayoutPrivate::hitTest(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());

//     LDEBUG << "    checking block" << bl.position() << "point=" << point

//            << "    tlrect" << textrect;

    *position = bl.position();

    if (point.y.toReal() < textrect.top()) {

//             LDEBUG << "    before pos=" << *position;

        return PointBefore;

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

        *position += bl.length();

//             LDEBUG << "    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;

//     LDEBUG << "    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());

}

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

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

{

    const qreal pageHeight = document->pageSize().height();

    const int topPage = pageHeight > 0 ? static_cast<int>(rect.top() / pageHeight) : 0;

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

#ifndef QT_NO_CSSPARSER

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

#endif //QT_NO_CSSPARSER

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

    painter->setRenderHint(QPainter::Antialiasing);

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

        QRectF clipped = rect.toRect();

        if (topPage != bottomPage) {

            clipped.setTop(qMax(clipped.top(), i * pageHeight + topMargin - border));

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

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

                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();

        if (!frame->parentFrame()) {

            bgRect = clip;

            gradientRect.setWidth(painter->device()->width());

            gradientRect.setHeight(painter->device()->height());

        }

        fillBackground(painter, bgRect, bg, origin, gradientRect);

    }

    if (fd->border != 0) {

        painter->save();

        painter->setBrush(Qt::lightGray);

        painter->setPen(Qt::NoPen);

        const qreal leftEdge = rect.left() + fd->leftMargin.toReal();

        const qreal border = fd->border.toReal();

        const qreal topMargin = fd->topMargin.toReal();

        const qreal leftMargin = fd->leftMargin.toReal();

        const qreal bottomMargin = fd->bottomMargin.toReal();

        const qreal rightMargin = fd->rightMargin.toReal();

        const qreal w = rect.width() - 2 * border - leftMargin - rightMargin;

        const qreal h = rect.height() - 2 * border - topMargin - bottomMargin;

        drawBorder(painter, QRectF(leftEdge, rect.top() + topMargin, w + border, h + border),

                   fd->effectiveTopMargin.toReal(), fd->effectiveBottomMargin.toReal(),

                   border, frame->frameFormat().borderBrush(), frame->frameFormat().borderStyle());

        painter->restore();

    }

}

static void adjustContextSelectionsForCell(QAbstractTextDocumentLayout::PaintContext &cell_context,

                                           const QTextTableCell &cell,

                                           int r, int c,

                                           const int *selectedTableCells)

{

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

        int row_start = selectedTableCells[i * 4];

        int col_start = selectedTableCells[i * 4 + 1];

        int num_rows = selectedTableCells[i * 4 + 2];

        int num_cols = selectedTableCells[i * 4 + 3];

        if (row_start != -1) {

            if (r >= row_start && r < row_start + num_rows

                && c >= col_start && c < col_start + num_cols)

            {

                int firstPosition = cell.firstPosition();

                int lastPosition = cell.lastPosition();

                // make sure empty cells are still selected

                if (firstPosition == lastPosition)

                    ++lastPosition;

                cell_context.selections[i].cursor.setPosition(firstPosition);

                cell_context.selections[i].cursor.setPosition(lastPosition, QTextCursor::KeepAnchor);

            } else {

                cell_context.selections[i].cursor.clearSelection();

            }

        }

        // FullWidthSelection is not useful for tables

        cell_context.selections[i].format.clearProperty(QTextFormat::FullWidthSelection);

    }

}

void QTextDocumentLayoutPrivate::drawFrame(const QPointF &offset, QPainter *painter,

                                           const QAbstractTextDocumentLayout::PaintContext &context,

                                           QTextFrame *frame) const

{

    QTextFrameData *fd = data(frame);

    // #######

    if (fd->layoutDirty)

        return;

    Q_ASSERT(!fd->sizeDirty);

    Q_ASSERT(!fd->layoutDirty);

    const QPointF off = offset + fd->position.toPointF();

    if (context.clip.isValid()

        && (off.y() > context.clip.bottom() || off.y() + fd->size.height.toReal() < context.clip.top()

            || off.x() > context.clip.right() || off.x() + fd->size.width.toReal() < context.clip.left()))

        return;

//     LDEBUG << debug_indent << "drawFrame" << frame->firstPosition() << "--" << frame->lastPosition() << "at" << offset;

//     INC_INDENT;

    // if the cursor is /on/ a table border we may need to repaint it

    // afterwards, as we usually draw the decoration first

    QTextBlock cursorBlockNeedingRepaint;

    QPointF offsetOfRepaintedCursorBlock = off;

    QTextTable *table = qobject_cast<QTextTable *>(frame);

    const QRectF frameRect(off, fd->size.toSizeF());

    if (table) {

        const int rows = table->rows();

        const int columns = table->columns();

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

        QVarLengthArray<int> selectedTableCells(context.selections.size() * 4);

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

            const QAbstractTextDocumentLayout::Selection &s = context.selections.at(i);

            int row_start = -1, col_start = -1, num_rows = -1, num_cols = -1;

            if (s.cursor.currentTable() == table)

                s.cursor.selectedTableCells(&row_start, &num_rows, &col_start, &num_cols);

            selectedTableCells[i * 4] = row_start;

            selectedTableCells[i * 4 + 1] = col_start;

            selectedTableCells[i * 4 + 2] = num_rows;

            selectedTableCells[i * 4 + 3] = num_cols;

        }

        QFixed pageHeight = QFixed::fromReal(document->pageSize().height());

        if (pageHeight <= 0)

            pageHeight = QFIXED_MAX;

        const int tableStartPage = (td->position.y / pageHeight).truncate();

        const int tableEndPage = ((td->position.y + td->size.height) / pageHeight).truncate();

        qreal border = td->border.toReal();

        drawFrameDecoration(painter, frame, fd, context.clip, frameRect);

        // draw the table headers

        const int headerRowCount = qMin(table->format().headerRowCount(), rows - 1);

        int page = tableStartPage + 1;

        while (page <= tableEndPage) {

            const QFixed pageTop = page * pageHeight + td->effectiveTopMargin + td->cellSpacing + td->border;

            const qreal headerOffset = (pageTop - td->rowPositions.at(0)).toReal();

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

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

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

                    QAbstractTextDocumentLayout::PaintContext cell_context = context;

                    adjustContextSelectionsForCell(cell_context, cell, r, c, selectedTableCells.data());

                    QRectF cellRect = td->cellRect(cell);

                    cellRect.translate(off.x(), headerOffset);

                    // we need to account for the cell border in the clipping test

                    int leftAdjust = qMin(qreal(0), 1 - border);

                    if (cell_context.clip.isValid() && !cellRect.adjusted(leftAdjust, leftAdjust, border, border).intersects(cell_context.clip))

                        continue;

                    drawTableCell(cellRect, painter, cell_context, table, td, r, c, &cursorBlockNeedingRepaint,

                                  &offsetOfRepaintedCursorBlock);

                }

            }

            ++page;

        }

        int firstRow = 0;

        int lastRow = rows;

        if (context.clip.isValid()) {

            QVector<QFixed>::ConstIterator rowIt = qLowerBound(td->rowPositions.constBegin(), td->rowPositions.constEnd(), QFixed::fromReal(context.clip.top() - off.y()));

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

                --rowIt;

                firstRow = rowIt - td->rowPositions.constBegin();

            }

            rowIt = qUpperBound(td->rowPositions.constBegin(), td->rowPositions.constEnd(), QFixed::fromReal(context.clip.bottom() - off.y()));

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

                ++rowIt;

                lastRow = rowIt - td->rowPositions.constBegin();

            }

        }

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

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

            firstRow = qMin(firstRow, cell.row());

        }

        for (int r = firstRow; r < lastRow; ++r) {

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

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

                QAbstractTextDocumentLayout::PaintContext cell_context = context;

                adjustContextSelectionsForCell(cell_context, cell, r, c, selectedTableCells.data());

                QRectF cellRect = td->cellRect(cell);

                cellRect.translate(off);

                // we need to account for the cell border in the clipping test

                int leftAdjust = qMin(qreal(0), 1 - border);

                if (cell_context.clip.isValid() && !cellRect.adjusted(leftAdjust, leftAdjust, border, border).intersects(cell_context.clip))

                    continue;

                drawTableCell(cellRect, painter, cell_context, table, td, r, c, &cursorBlockNeedingRepaint,

                              &offsetOfRepaintedCursorBlock);

            }

        }

    } else {

        drawFrameDecoration(painter, frame, fd, context.clip, frameRect);

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

        if (frame == docPrivate->rootFrame())

            it = frameIteratorForYPosition(QFixed::fromReal(context.clip.top()));

        QList<QTextFrame *> floats;

        for (int i = 0; i < fd->floats.count(); ++i)

            floats.append(fd->floats.at(i));

        drawFlow(off, painter, context, it, floats, &cursorBlockNeedingRepaint);

    }

    if (cursorBlockNeedingRepaint.isValid()) {

        const QPen oldPen = painter->pen();

        painter->setPen(context.palette.color(QPalette::Text));

        const int cursorPos = context.cursorPosition - cursorBlockNeedingRepaint.position();

        cursorBlockNeedingRepaint.layout()->drawCursor(painter, offsetOfRepaintedCursorBlock,

                                                       cursorPos, cursorWidth);

        painter->setPen(oldPen);

    }

//     DEC_INDENT;

    return;

}

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

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

                                               QTextBlock *cursorBlockNeedingRepaint, QPointF *cursorBlockOffset) const

{

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

    int rspan = cell.rowSpan();

    int cspan = cell.columnSpan();

    if (rspan != 1) {

        int cr = cell.row();

        if (cr != r)

            return;

    }

    if (cspan != 1) {

        int cc = cell.column();

        if (cc != c)

            return;

    }

    QTextFormat fmt = cell.format();

    const QFixed leftPadding = td->leftPadding(fmt);

    const QFixed topPadding = td->topPadding(fmt);

    if (td->border != 0) {

        const QBrush oldBrush = painter->brush();

        const QPen oldPen = painter->pen();

        const qreal border = td->border.toReal();

        QRectF borderRect(cellRect.left() - border, cellRect.top() - border, cellRect.width() + border, cellRect.height() + border);

        // invert the border style for cells

        QTextFrameFormat::BorderStyle cellBorder = table->format().borderStyle();

        switch (cellBorder) {

        case QTextFrameFormat::BorderStyle_Inset:

            cellBorder = QTextFrameFormat::BorderStyle_Outset;

            break;

        case QTextFrameFormat::BorderStyle_Outset:

            cellBorder = QTextFrameFormat::BorderStyle_Inset;

            break;

        case QTextFrameFormat::BorderStyle_Groove:

            cellBorder = QTextFrameFormat::BorderStyle_Ridge;

            break;

        case QTextFrameFormat::BorderStyle_Ridge:

            cellBorder = QTextFrameFormat::BorderStyle_Groove;

            break;

        default:

            break;

        }

        qreal topMargin = (td->effectiveTopMargin + td->cellSpacing + td->border).toReal();

        qreal bottomMargin = (td->effectiveBottomMargin + td->cellSpacing + td->border).toReal();

        const int headerRowCount = qMin(table->format().headerRowCount(), table->rows() - 1);

        if (r >= headerRowCount)

            topMargin += td->headerHeight.toReal();

        drawBorder(painter, borderRect, topMargin, bottomMargin,

                   border, table->format().borderBrush(), cellBorder);

        painter->setBrush(oldBrush);

        painter->setPen(oldPen);

    }

    const QBrush bg = cell.format().background();

    const QPointF brushOrigin = painter->brushOrigin();

    if (bg.style() != Qt::NoBrush) {

        fillBackground(painter, cellRect, bg, cellRect.topLeft());

        if (bg.style() > Qt::SolidPattern)

            painter->setBrushOrigin(cellRect.topLeft());

    }

    const QFixed verticalOffset = td->cellVerticalOffsets.at(c + r * table->columns());

    const QPointF cellPos = QPointF(cellRect.left() + leftPadding.toReal(),

                                    cellRect.top() + (topPadding + verticalOffset).toReal());

    QTextBlock repaintBlock;

    drawFlow(cellPos, painter, cell_context, cell.begin(),

             td->childFrameMap.values(r + c * table->rows()),

             &repaintBlock);

    if (repaintBlock.isValid()) {

        *cursorBlockNeedingRepaint = repaintBlock;

        *cursorBlockOffset = cellPos;

    }

    if (bg.style() > Qt::SolidPattern)

        painter->setBrushOrigin(brushOrigin);

}

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

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

{

    Q_Q(const QTextDocumentLayout);

    const bool inRootFrame = (!it.atEnd() && it.parentFrame() && it.parentFrame()->parentFrame() == 0);

    QVector<QCheckPoint>::ConstIterator lastVisibleCheckPoint = checkPoints.end();

    if (inRootFrame && context.clip.isValid()) {

        lastVisibleCheckPoint = qLowerBound(checkPoints.begin(), checkPoints.end(), QFixed::fromReal(context.clip.bottom()));

    }

    QTextBlock previousBlock;

    QTextFrame *previousFrame = 0;

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

        QTextFrame *c = it.currentFrame();

        if (inRootFrame && !checkPoints.isEmpty()) {

            int currentPosInDoc;

            if (c)

                currentPosInDoc = c->firstPosition();

            else

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

            // if we're past what is already laid out then we're better off

            // not trying to draw things that may not be positioned correctly yet

            if (currentPosInDoc >= checkPoints.last().positionInFrame)

                break;

            if (lastVisibleCheckPoint != checkPoints.end()

                && context.clip.isValid()

                && currentPosInDoc >= lastVisibleCheckPoint->positionInFrame

               )

                break;

        }

        if (c)

            drawFrame(offset, painter, context, c);

        else {

            QAbstractTextDocumentLayout::PaintContext pc = context;

            if (isEmptyBlockAfterTable(it.currentBlock(), previousFrame))

                pc.selections.clear();

            drawBlock(offset, painter, pc, it.currentBlock(), inRootFrame);

        }

        // when entering a table and the previous block is empty

        // then layoutFlow 'hides' the block that just causes a

        // new line by positioning it /on/ the table border. as we

        // draw that block before the table itself the decoration

        // 'overpaints' the cursor and we need to paint it afterwards

        // again

        if (isEmptyBlockBeforeTable(previousBlock, previousBlock.blockFormat(), it)

            && previousBlock.contains(context.cursorPosition)

           ) {

            *cursorBlockNeedingRepaint = previousBlock;

        }

        previousBlock = it.currentBlock();

        previousFrame = c;

    }

    for (int i = 0; i < floats.count(); ++i) {

        QTextFrame *frame = floats.at(i);

        if (!isFrameFromInlineObject(frame)

            || frame->frameFormat().position() == QTextFrameFormat::InFlow)

            continue;

        const int pos = frame->firstPosition() - 1;

        QTextCharFormat format = const_cast<QTextDocumentLayout *>(q)->format(pos);

        QTextObjectInterface *handler = q->handlerForObject(format.objectType());

        if (handler) {

            QRectF rect = frameBoundingRectInternal(frame);

            handler->drawObject(painter, rect, document, pos, format);

        }

    }

}

void QTextDocumentLayoutPrivate::drawBlock(const QPointF &offset, QPainter *painter,

                                           const QAbstractTextDocumentLayout::PaintContext &context,

                                           QTextBlock bl, bool inRootFrame) const

{

    const QTextLayout *tl = bl.layout();

    QRectF r = tl->boundingRect();

    r.translate(offset + tl->position());

    if (context.clip.isValid() && (r.bottom() < context.clip.y() || r.top() > context.clip.bottom()))

        return;

//      LDEBUG << debug_indent << "drawBlock" << bl.position() << "at" << offset << "br" << tl->boundingRect();

    QTextBlockFormat blockFormat = bl.blockFormat();

    QBrush bg = blockFormat.background();

    if (bg != Qt::NoBrush) {

        QRectF rect = r;

        // extend the background rectangle if we're in the root frame with NoWrap,

        // as the rect of the text block will then be only the width of the text

        // instead of the full page width

        if (inRootFrame && document->pageSize().width() <= 0) {

            const QTextFrameData *fd = data(document->rootFrame());

            rect.setRight((fd->size.width - fd->rightMargin).toReal());

        }

        fillBackground(painter, rect, bg, r.topLeft());

    }

    QVector<QTextLayout::FormatRange> selections;

    int blpos = bl.position();

    int bllen = bl.length();

    const QTextCharFormat *selFormat = 0;

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

        const QAbstractTextDocumentLayout::Selection &range = context.selections.at(i);

        const int selStart = range.cursor.selectionStart() - blpos;

        const int selEnd = range.cursor.selectionEnd() - blpos;

        if (selStart < bllen && selEnd > 0

             && selEnd > selStart) {

            QTextLayout::FormatRange o;

            o.start = selStart;

            o.length = selEnd - selStart;

            o.format = range.format;

            selections.append(o);

        } else if (! range.cursor.hasSelection() && range.format.hasProperty(QTextFormat::FullWidthSelection)

                   && bl.contains(range.cursor.position())) {

            // for full width selections we don't require an actual selection, just

            // a position to specify the line. that's more convenience in usage.

            QTextLayout::FormatRange o;

            QTextLine l = tl->lineForTextPosition(range.cursor.position() - blpos);

            o.start = l.textStart();

            o.length = l.textLength();

            if (o.start + o.length == bllen - 1)

                ++o.length; // include newline

            o.format = range.format;

            selections.append(o);

       }

        if (selStart < 0 && selEnd >= 1)

            selFormat = &range.format;

    }

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

    if (object && object->format().toListFormat().style() != QTextListFormat::ListStyleUndefined)

        drawListItem(offset, painter, context, bl, selFormat);

    QPen oldPen = painter->pen();

    painter->setPen(context.palette.color(QPalette::Text));

    tl->draw(painter, offset, selections, context.clip.isValid() ? (context.clip & clipRect) : clipRect);

    if ((context.cursorPosition >= blpos && context.cursorPosition < blpos + bllen)

        || (context.cursorPosition < -1 && !tl->preeditAreaText().isEmpty())) {

        int cpos = context.cursorPosition;

        if (cpos < -1)

            cpos = tl->preeditAreaPosition() - (cpos + 2);

        else

            cpos -= blpos;

        tl->drawCursor(painter, offset, cpos, cursorWidth);

    }

    if (blockFormat.hasProperty(QTextFormat::BlockTrailingHorizontalRulerWidth)) {

        const qreal width = blockFormat.lengthProperty(QTextFormat::BlockTrailingHorizontalRulerWidth).value(r.width());

        painter->setPen(context.palette.color(QPalette::Dark));

        qreal y = r.bottom();

        if (bl.length() == 1)

            y = r.top() + r.height() / 2;

        const qreal middleX = r.left() + r.width() / 2;

        painter->drawLine(QLineF(middleX - width / 2, y, middleX + width / 2, y));

    }

    painter->setPen(oldPen);

}

void QTextDocumentLayoutPrivate::drawListItem(const QPointF &offset, QPainter *painter,

                                              const QAbstractTextDocumentLayout::PaintContext &context,

                                              QTextBlock bl, const QTextCharFormat *selectionFormat) const

{

    Q_Q(const QTextDocumentLayout);

    const QTextBlockFormat blockFormat = bl.blockFormat();

    const QTextCharFormat charFormat = QTextCursor(bl).charFormat();

    QFont font(charFormat.font());

    if (q->paintDevice())

        font = QFont(font, q->paintDevice());

    const QFontMetrics fontMetrics(font);

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

    const QTextListFormat lf = object->format().toListFormat();

    int style = lf.style();

    QString itemText;

    QSizeF size;

    if (blockFormat.hasProperty(QTextFormat::ListStyle))

        style = QTextListFormat::Style(blockFormat.intProperty(QTextFormat::ListStyle));

    QTextLayout *layout = bl.layout();

    if (layout->lineCount() == 0)

        return;

    QTextLine firstLine = layout->lineAt(0);

    Q_ASSERT(firstLine.isValid());

    QPointF pos = (offset + layout->position()).toPoint();

    Qt::LayoutDirection dir = docPrivate->defaultTextOption.textDirection();

    if (blockFormat.hasProperty(QTextFormat::LayoutDirection))

        dir = blockFormat.layoutDirection();

    {

        QRectF textRect = firstLine.naturalTextRect();

        pos += textRect.topLeft().toPoint();

        if (dir == Qt::RightToLeft)

            pos.rx() += textRect.width();

    }

    switch (style) {

    case QTextListFormat::ListDecimal:

    case QTextListFormat::ListLowerAlpha:

    case QTextListFormat::ListUpperAlpha:

    case QTextListFormat::ListLowerRoman:

    case QTextListFormat::ListUpperRoman:

        itemText = static_cast<QTextList *>(object)->itemText(bl);

        size.setWidth(fontMetrics.width(itemText));

        size.setHeight(fontMetrics.height());

        break;

    case QTextListFormat::ListSquare:

    case QTextListFormat::ListCircle:

    case QTextListFormat::ListDisc:

        size.setWidth(fontMetrics.lineSpacing() / 3);

        size.setHeight(size.width());

        break;

    case QTextListFormat::ListStyleUndefined:

        return;

    default: return;

    }

    QRectF r(pos, size);

    qreal xoff = fontMetrics.width(QLatin1Char(' '));

    if (dir == Qt::LeftToRight)

        xoff = -xoff - size.width();

    r.translate( xoff, (fontMetrics.height() / 2 - size.height() / 2));

    painter->save();

    painter->setRenderHint(QPainter::Antialiasing);

    if (selectionFormat) {

        painter->setPen(QPen(selectionFormat->foreground(), 0));

        painter->fillRect(r, selectionFormat->background());

    } else {

        QBrush fg = charFormat.foreground();

        if (fg == Qt::NoBrush)

            fg = context.palette.text();

        painter->setPen(QPen(fg, 0));

    }

    QBrush brush = context.palette.brush(QPalette::Text);

    switch (style) {

    case QTextListFormat::ListDecimal:

    case QTextListFormat::ListLowerAlpha:

    case QTextListFormat::ListUpperAlpha:

    case QTextListFormat::ListLowerRoman:

    case QTextListFormat::ListUpperRoman: {

        QTextLayout layout(itemText, font, q->paintDevice());

        layout.setCacheEnabled(true);

        QTextOption option(Qt::AlignLeft | Qt::AlignAbsolute);

        option.setTextDirection(dir);

        layout.setTextOption(option);

        layout.beginLayout();

        QTextLine line = layout.createLine();

        if (line.isValid())

            line.setLeadingIncluded(true);

        layout.endLayout();

        layout.draw(painter, QPointF(r.left(), pos.y()));

        break;

    }

    case QTextListFormat::ListSquare:

        painter->fillRect(r, brush);

        break;

    case QTextListFormat::ListCircle:

        painter->setPen(QPen(brush, 0));

        painter->drawEllipse(r.translated(0.5, 0.5)); // pixel align for sharper rendering

        break;

    case QTextListFormat::ListDisc:

        painter->setBrush(brush);

        painter->setPen(Qt::NoPen);

        painter->drawEllipse(r);

        break;

    case QTextListFormat::ListStyleUndefined:

        break;

    default:

        break;

    }

    painter->restore();

}

static QFixed flowPosition(const QTextFrame::iterator it)

{

    if (it.atEnd())

        return 0;

    if (it.currentFrame()) {

        return data(it.currentFrame())->position.y;

    } else {

        QTextBlock block = it.currentBlock();

        QTextLayout *layout = block.layout();

        if (layout->lineCount() == 0)

            return QFixed::fromReal(layout->position().y());

        else

            return QFixed::fromReal(layout->position().y() + layout->lineAt(0).y());

    }

}

static QFixed firstChildPos(const QTextFrame *f)

{

    return flowPosition(f->begin());

}

QLayoutStruct QTextDocumentLayoutPrivate::layoutCell(QTextTable *t, const QTextTableCell &cell, QFixed width,

                                                    int layoutFrom, int layoutTo, QTextTableData *td,

                                                    QFixed absoluteTableY, bool withPageBreaks)

{

    LDEBUG << "layoutCell";

    QLayoutStruct layoutStruct;

    layoutStruct.frame = t;

    layoutStruct.minimumWidth = 0;

    layoutStruct.maximumWidth = QFIXED_MAX;

    layoutStruct.y = 0;

    const QTextFormat fmt = cell.format();

    const QFixed topPadding = td->topPadding(fmt);

    if (withPageBreaks) {

        layoutStruct.frameY = absoluteTableY + td->rowPositions.at(cell.row()) + topPadding;

    }

    layoutStruct.x_left = 0;

    layoutStruct.x_right = width;

    // we get called with different widths all the time (for example for figuring

    // out the min/max widths), so we always have to do the full layout ;(

    // also when for example in a table layoutFrom/layoutTo affect only one cell,

    // making that one cell grow the available width of the other cells may change

    // (shrink) and therefore when layoutCell gets called for them they have to

    // be re-laid out, even if layoutFrom/layoutTo is not in their range. Hence

    // this line:

    layoutStruct.pageHeight = QFixed::fromReal(document->pageSize().height());

    if (layoutStruct.pageHeight < 0 || !withPageBreaks)

        layoutStruct.pageHeight = QFIXED_MAX;

    const int currentPage = layoutStruct.currentPage();

    layoutStruct.pageTopMargin = td->effectiveTopMargin + td->cellSpacing + td->border + topPadding;

    layoutStruct.pageBottomMargin = td->effectiveBottomMargin + td->cellSpacing + td->border + td->bottomPadding(fmt);

    layoutStruct.pageBottom = (currentPage + 1) * layoutStruct.pageHeight - layoutStruct.pageBottomMargin;

    layoutStruct.fullLayout = true;

    QFixed pageTop = currentPage * layoutStruct.pageHeight + layoutStruct.pageTopMargin - layoutStruct.frameY;

    layoutStruct.y = qMax(layoutStruct.y, pageTop);

    const QList<QTextFrame *> childFrames = td->childFrameMap.values(cell.row() + cell.column() * t->rows());

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

        QTextFrame *frame = childFrames.at(i);

        QTextFrameData *cd = data(frame);

        cd->sizeDirty = true;

    }

    layoutFlow(cell.begin(), &layoutStruct, layoutFrom, layoutTo, width);

    QFixed floatMinWidth;

    // floats that are located inside the text (like inline images) aren't taken into account by

    // layoutFlow with regards to the cell height (layoutStruct->y), so for a safety measure we

    // do that here. For example with <td><img align="right" src="..." />blah</td>

    // when the image happens to be higher than the text

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

        QTextFrame *frame = childFrames.at(i);

        QTextFrameData *cd = data(frame);

        if (frame->frameFormat().position() != QTextFrameFormat::InFlow)

            layoutStruct.y = qMax(layoutStruct.y, cd->position.y + cd->size.height);

        floatMinWidth = qMax(floatMinWidth, cd->minimumWidth);

    }

    // constraint the maximumWidth by the minimum width of the fixed size floats, to

    // keep them visible

    layoutStruct.maximumWidth = qMax(layoutStruct.maximumWidth, floatMinWidth);

    // as floats in cells get added to the table's float list but must not affect

    // floats in other cells we must clear the list here.

    data(t)->floats.clear();

//    qDebug() << "layoutCell done";

    return layoutStruct;

}

QRectF QTextDocumentLayoutPrivate::layoutTable(QTextTable *table, int layoutFrom, int layoutTo, QFixed parentY)

{

    LDEBUG << "layoutTable";

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

    Q_ASSERT(td->sizeDirty);

    const int rows = table->rows();

    const int columns = table->columns();

    const QTextTableFormat fmt = table->format();

    td->childFrameMap.clear();

    {

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

        for (int i = 0; i < children.count(); ++i) {

            QTextFrame *frame = children.at(i);

            QTextTableCell cell = table->cellAt(frame->firstPosition());

            td->childFrameMap.insertMulti(cell.row() + cell.column() * rows, frame);

        }

    }

    QVector<QTextLength> columnWidthConstraints = fmt.columnWidthConstraints();

    if (columnWidthConstraints.size() != columns)

        columnWidthConstraints.resize(columns);

    Q_ASSERT(columnWidthConstraints.count() == columns);