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

**

** 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

// ################ 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;