src/gui/text/qtextdocumentlayout.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the QtGui module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** No Commercial Usage
  11 ** This file contains pre-release code and may not be distributed.
  12 ** You may use this file in accordance with the terms and conditions
  13 ** contained in the Technology Preview License Agreement accompanying
  14 ** this package.
  15 **
  16 ** GNU Lesser General Public License Usage
  17 ** Alternatively, this file may be used under the terms of the GNU Lesser
  18 ** General Public License version 2.1 as published by the Free Software
  19 ** Foundation and appearing in the file LICENSE.LGPL included in the
  20 ** packaging of this file.  Please review the following information to
  21 ** ensure the GNU Lesser General Public License version 2.1 requirements
  22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  23 **
  24 ** In addition, as a special exception, Nokia gives you certain additional
  25 ** rights.  These rights are described in the Nokia Qt LGPL Exception
  26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  27 **
  28 ** If you have questions regarding the use of this file, please contact
  29 ** Nokia at qt-info@nokia.com.
  30 **
  31 **
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qtextdocumentlayout_p.h"
  43 #include "qtextdocument_p.h"
  44 #include "qtextimagehandler_p.h"
  45 #include "qtexttable.h"
  46 #include "qtextlist.h"
  47 #include "qtextengine_p.h"
  48 #include "private/qcssutil_p.h"
  49
  50 #include "qabstracttextdocumentlayout_p.h"
  51 #include "qcssparser_p.h"
  52
  53 #include <qpainter.h>
  54 #include <qmath.h>
  55 #include <qrect.h>
  56 #include <qpalette.h>
  57 #include <qdebug.h>
  58 #include <qvarlengtharray.h>
  59 #include <limits.h>
  60 #include <qstyle.h>
  61 #include <qbasictimer.h>
  62 #include "private/qfunctions_p.h"
  63
  64 // #define LAYOUT_DEBUG
  65
  66 #ifdef LAYOUT_DEBUG
  67 #define LDEBUG qDebug()
  68 #define INC_INDENT debug_indent += "  "
  69 #define DEC_INDENT debug_indent = debug_indent.left(debug_indent.length()-2)
  70 #else
  71 #define LDEBUG if(0) qDebug()
  72 #define INC_INDENT do {} while(0)
  73 #define DEC_INDENT do {} while(0)
  74 #endif
  75
  76 QT_BEGIN_NAMESPACE
  77
  78 // ################ should probably add frameFormatChange notification!
  79
  80 struct QTextLayoutStruct;
  81
  82 class QTextFrameData : public QTextFrameLayoutData
  83 {
  84 public:
  85     QTextFrameData();
  86
  87     // relative to parent frame
  88     QFixedPoint position;
  89     QFixedSize size;
  90
  91     // contents starts at (margin+border/margin+border)
  92     QFixed topMargin;
  93     QFixed bottomMargin;
  94     QFixed leftMargin;
  95     QFixed rightMargin;
  96     QFixed border;
  97     QFixed padding;
  98     // contents width includes padding (as we need to treat this on a per cell basis for tables)
  99     QFixed contentsWidth;
 100     QFixed contentsHeight;
 101     QFixed oldContentsWidth;
 102
 103     // accumulated margins
 104     QFixed effectiveTopMargin;
 105     QFixed effectiveBottomMargin;
 106
 107     QFixed minimumWidth;
 108     QFixed maximumWidth;
 109
 110     QTextLayoutStruct *currentLayoutStruct;
 111
 112     bool sizeDirty;
 113     bool layoutDirty;
 114
 115     QList<QPointer<QTextFrame> > floats;
 116 };
 117
 118 QTextFrameData::QTextFrameData()
 119     : maximumWidth(QFIXED_MAX),
 120       currentLayoutStruct(0), sizeDirty(true), layoutDirty(true)
 121 {
 122 }
 123
 124 struct QTextLayoutStruct {
 125     QTextLayoutStruct() : maximumWidth(QFIXED_MAX), fullLayout(false)
 126     {}
 127     QTextFrame *frame;
 128     QFixed x_left;
 129     QFixed x_right;
 130     QFixed frameY; // absolute y position of the current frame
 131     QFixed y; // always relative to the current frame
 132     QFixed contentsWidth;
 133     QFixed minimumWidth;
 134     QFixed maximumWidth;
 135     bool fullLayout;
 136     QList<QTextFrame *> pendingFloats;
 137     QFixed pageHeight;
 138     QFixed pageBottom;
 139     QFixed pageTopMargin;
 140     QFixed pageBottomMargin;
 141     QRectF updateRect;
 142     QRectF updateRectForFloats;
 143
 144     inline void addUpdateRectForFloat(const QRectF &rect) {
 145         if (updateRectForFloats.isValid())
 146             updateRectForFloats |= rect;
 147         else
 148             updateRectForFloats = rect;
 149     }
 150
 151     inline QFixed absoluteY() const
 152     { return frameY + y; }
 153
 154     inline int currentPage() const
 155     { return pageHeight == 0 ? 0 : (absoluteY() / pageHeight).truncate(); }
 156
 157     inline void newPage()
 158     { if (pageHeight == QFIXED_MAX) return; pageBottom += pageHeight; y = pageBottom - pageHeight + pageBottomMargin + pageTopMargin - frameY; }
 159 };
 160
 161 class QTextTableData : public QTextFrameData
 162 {
 163 public:
 164     QFixed cellSpacing, cellPadding;
 165     qreal deviceScale;
 166     QVector<QFixed> minWidths;
 167     QVector<QFixed> maxWidths;
 168     QVector<QFixed> widths;
 169     QVector<QFixed> heights;
 170     QVector<QFixed> columnPositions;
 171     QVector<QFixed> rowPositions;
 172
 173     QVector<QFixed> cellVerticalOffsets;
 174
 175     QFixed headerHeight;
 176
 177     // maps from cell index (row + col * rowCount) to child frames belonging to
 178     // the specific cell
 179     QMultiHash<int, QTextFrame *> childFrameMap;
 180
 181     inline QFixed cellWidth(int column, int colspan) const
 182     { return columnPositions.at(column + colspan - 1) + widths.at(column + colspan - 1)
 183              - columnPositions.at(column); }
 184
 185     inline void calcRowPosition(int row)
 186     {
 187         if (row > 0)
 188             rowPositions[row] = rowPositions.at(row - 1) + heights.at(row - 1) + border + cellSpacing + border;
 189     }
 190
 191     QRectF cellRect(const QTextTableCell &cell) const;
 192
 193     inline QFixed paddingProperty(const QTextFormat &format, QTextFormat::Property property) const
 194     {
 195         QVariant v = format.property(property);
 196         if (v.isNull()) {
 197             return cellPadding;
 198         } else {
 199             Q_ASSERT(v.userType() == QVariant::Double || v.userType() == QMetaType::Float);
 200             return QFixed::fromReal(v.toReal() * deviceScale);
 201         }
 202     }
 203
 204     inline QFixed topPadding(const QTextFormat &format) const
 205     {
 206         return paddingProperty(format, QTextFormat::TableCellTopPadding);
 207     }
 208
 209     inline QFixed bottomPadding(const QTextFormat &format) const
 210     {
 211         return paddingProperty(format, QTextFormat::TableCellBottomPadding);
 212     }
 213
 214     inline QFixed leftPadding(const QTextFormat &format) const
 215     {
 216         return paddingProperty(format, QTextFormat::TableCellLeftPadding);
 217     }
 218
 219     inline QFixed rightPadding(const QTextFormat &format) const
 220     {
 221         return paddingProperty(format, QTextFormat::TableCellRightPadding);
 222     }
 223
 224     inline QFixedPoint cellPosition(const QTextTableCell &cell) const
 225     {
 226         const QTextFormat fmt = cell.format();
 227         return cellPosition(cell.row(), cell.column()) + QFixedPoint(leftPadding(fmt), topPadding(fmt));
 228     }
 229
 230     void updateTableSize();
 231
 232 private:
 233     inline QFixedPoint cellPosition(int row, int col) const
 234     { return QFixedPoint(columnPositions.at(col), rowPositions.at(row) + cellVerticalOffsets.at(col + row * widths.size())); }
 235 };
 236
 237 static QTextFrameData *createData(QTextFrame *f)
 238 {
 239     QTextFrameData *data;
 240     if (qobject_cast<QTextTable *>(f))
 241         data = new QTextTableData;
 242     else
 243         data = new QTextFrameData;
 244     f->setLayoutData(data);
 245     return data;
 246 }
 247
 248 static inline QTextFrameData *data(QTextFrame *f)
 249 {
 250     QTextFrameData *data = static_cast<QTextFrameData *>(f->layoutData());
 251     if (!data)
 252         data = createData(f);
 253     return data;
 254 }
 255
 256 static bool isFrameFromInlineObject(QTextFrame *f)
 257 {
 258     return f->firstPosition() > f->lastPosition();
 259 }
 260
 261 void QTextTableData::updateTableSize()
 262 {
 263     const QFixed effectiveTopMargin = this->topMargin + border + padding;
 264     const QFixed effectiveBottomMargin = this->bottomMargin + border + padding;
 265     const QFixed effectiveLeftMargin = this->leftMargin + border + padding;
 266     const QFixed effectiveRightMargin = this->rightMargin + border + padding;
 267     size.height = contentsHeight == -1
 268                    ? rowPositions.last() + heights.last() + padding + border + cellSpacing + effectiveBottomMargin
 269                    : effectiveTopMargin + contentsHeight + effectiveBottomMargin;
 270     size.width = effectiveLeftMargin + contentsWidth + effectiveRightMargin;
 271 }
 272
 273 QRectF QTextTableData::cellRect(const QTextTableCell &cell) const
 274 {
 275     const int row = cell.row();
 276     const int rowSpan = cell.rowSpan();
 277     const int column = cell.column();
 278     const int colSpan = cell.columnSpan();
 279
 280     return QRectF(columnPositions.at(column).toReal(),
 281                   rowPositions.at(row).toReal(),
 282                   (columnPositions.at(column + colSpan - 1) + widths.at(column + colSpan - 1) - columnPositions.at(column)).toReal(),
 283                   (rowPositions.at(row + rowSpan - 1) + heights.at(row + rowSpan - 1) - rowPositions.at(row)).toReal());
 284 }
 285
 286 static inline bool isEmptyBlockBeforeTable(const QTextBlock &block, const QTextBlockFormat &format, const QTextFrame::Iterator &nextIt)
 287 {
 288     return !nextIt.atEnd()
 289            && qobject_cast<QTextTable *>(nextIt.currentFrame())
 290            && block.isValid()
 291            && block.length() == 1
 292            && !format.hasProperty(QTextFormat::BlockTrailingHorizontalRulerWidth)
 293            && !format.hasProperty(QTextFormat::BackgroundBrush)
 294            && nextIt.currentFrame()->firstPosition() == block.position() + 1
 295            ;
 296 }
 297
 298 static inline bool isEmptyBlockBeforeTable(QTextFrame::Iterator it)
 299 {
 300     QTextFrame::Iterator next = it; ++next;
 301     if (it.currentFrame())
 302         return false;
 303     QTextBlock block = it.currentBlock();
 304     return isEmptyBlockBeforeTable(block, block.blockFormat(), next);
 305 }
 306
 307 static inline bool isEmptyBlockAfterTable(const QTextBlock &block, const QTextFrame *previousFrame)
 308 {
 309     return qobject_cast<const QTextTable *>(previousFrame)
 310            && block.isValid()
 311            && block.length() == 1
 312            && previousFrame->lastPosition() == block.position() - 1
 313            ;
 314 }
 315
 316 static inline bool isLineSeparatorBlockAfterTable(const QTextBlock &block, const QTextFrame *previousFrame)
 317 {
 318     return qobject_cast<const QTextTable *>(previousFrame)
 319            && block.isValid()
 320            && block.length() > 1
 321            && block.text().at(0) == QChar::LineSeparator
 322            && previousFrame->lastPosition() == block.position() - 1
 323            ;
 324 }
 325
 326 /*
 327
 328 Optimization strategies:
 329
 330 HTML layout:
 331
 332 * Distinguish between normal and special flow. For normal flow the condition:
 333   y1 > y2 holds for all blocks with b1.key() > b2.key().
 334 * Special flow is: floats, table cells
 335
 336 * Normal flow within table cells. Tables (not cells) are part of the normal flow.
 337
 338
 339 * If blocks grows/shrinks in height and extends over whole page width at the end, move following blocks.
 340 * If height doesn't change, no need to do anything
 341
 342 Table cells:
 343
 344 * If minWidth of cell changes, recalculate table width, relayout if needed.
 345 * What about maxWidth when doing auto layout?
 346
 347 Floats:
 348 * need fixed or proportional width, otherwise don't float!
 349 * On width/height change relayout surrounding paragraphs.
 350
 351 Document width change:
 352 * full relayout needed
 353
 354
 355 Float handling:
 356
 357 * Floats are specified by a special format object.
 358 * currently only floating images are implemented.
 359
 360 */
 361
 362 /*
 363
 364    On the table layouting:
 365
 366    +---[ table border ]-------------------------
 367    |      [ cell spacing ]
 368    |  +------[ cell border ]-----+  +--------
 369    |  |                          |  |
 370    |  |
 371    |  |
 372    |  |
 373    |
 374
 375    rowPositions[i] and columnPositions[i] point at the cell content
 376    position. So for example the left border is drawn at
 377    x = columnPositions[i] - fd->border and similar for y.
 378
 379 */
 380
 381 struct QCheckPoint
 382 {
 383     QFixed y;
 384     QFixed frameY; // absolute y position of the current frame
 385     int positionInFrame;
 386     QFixed minimumWidth;
 387     QFixed maximumWidth;
 388     QFixed contentsWidth;
 389 };
 390 Q_DECLARE_TYPEINFO(QCheckPoint, Q_PRIMITIVE_TYPE);
 391
 392 Q_STATIC_GLOBAL_OPERATOR bool operator<(const QCheckPoint &checkPoint, QFixed y)
 393 {
 394     return checkPoint.y < y;
 395 }
 396
 397 Q_STATIC_GLOBAL_OPERATOR bool operator<(const QCheckPoint &checkPoint, int pos)
 398 {
 399     return checkPoint.positionInFrame < pos;
 400 }
 401
 402 static void fillBackground(QPainter *p, const QRectF &rect, QBrush brush, const QPointF &origin, QRectF gradientRect = QRectF())
 403 {
 404     p->save();
 405     if (brush.style() >= Qt::LinearGradientPattern && brush.style() <= Qt::ConicalGradientPattern) {
 406         if (!gradientRect.isNull()) {
 407             QTransform m;
 408             m.translate(gradientRect.left(), gradientRect.top());
 409             m.scale(gradientRect.width(), gradientRect.height());
 410             brush.setTransform(m);
 411             const_cast<QGradient *>(brush.gradient())->setCoordinateMode(QGradient::LogicalMode);
 412         }
 413     } else {
 414         p->setBrushOrigin(origin);
 415     }
 416     p->fillRect(rect, brush);
 417     p->restore();
 418 }
 419
 420 class QTextDocumentLayoutPrivate : public QAbstractTextDocumentLayoutPrivate
 421 {
 422     Q_DECLARE_PUBLIC(QTextDocumentLayout)
 423 public:
 424     QTextDocumentLayoutPrivate();
 425
 426     QTextOption::WrapMode wordWrapMode;
 427 #ifdef LAYOUT_DEBUG
 428     mutable QString debug_indent;
 429 #endif
 430
 431     int fixedColumnWidth;
 432     int cursorWidth;
 433
 434     QSizeF lastReportedSize;
 435     QRectF viewportRect;
 436     QRectF clipRect;
 437
 438     mutable int currentLazyLayoutPosition;
 439     mutable int lazyLayoutStepSize;
 440     QBasicTimer layoutTimer;
 441     mutable QBasicTimer sizeChangedTimer;
 442     uint showLayoutProgress : 1;
 443     uint insideDocumentChange : 1;
 444
 445     int lastPageCount;
 446     qreal idealWidth;
 447     bool contentHasAlignment;
 448
 449     QFixed blockIndent(const QTextBlockFormat &blockFormat) const;
 450
 451     void drawFrame(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,
 452                    QTextFrame *f) const;
 453     void drawFlow(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,
 454                   QTextFrame::Iterator it, const QList<QTextFrame *> &floats, QTextBlock *cursorBlockNeedingRepaint) const;
 455     void drawBlock(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,
 456                    QTextBlock bl, bool inRootFrame) const;
 457     void drawListItem(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,
 458                       QTextBlock bl, const QTextCharFormat *selectionFormat) const;
 459     void drawTableCell(const QRectF &cellRect, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &cell_context,
 460                        QTextTable *table, QTextTableData *td, int r, int c,
 461                        QTextBlock *cursorBlockNeedingRepaint, QPointF *cursorBlockOffset) const;
 462     void drawBorder(QPainter *painter, const QRectF &rect, qreal topMargin, qreal bottomMargin, qreal border,
 463                     const QBrush &brush, QTextFrameFormat::BorderStyle style) const;
 464     void drawFrameDecoration(QPainter *painter, QTextFrame *frame, QTextFrameData *fd, const QRectF &clip, const QRectF &rect) const;
 465
 466     enum HitPoint {
 467         PointBefore,
 468         PointAfter,
 469         PointInside,
 470         PointExact
 471     };
 472     HitPoint hitTest(QTextFrame *frame, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;
 473     HitPoint hitTest(QTextFrame::Iterator it, HitPoint hit, const QFixedPoint &p,
 474                      int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;
 475     HitPoint hitTest(QTextTable *table, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;
 476     HitPoint hitTest(QTextBlock bl, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const;
 477
 478     QTextLayoutStruct layoutCell(QTextTable *t, const QTextTableCell &cell, QFixed width,
 479                                  int layoutFrom, int layoutTo, QTextTableData *tableData, QFixed absoluteTableY,
 480                                  bool withPageBreaks);
 481     void setCellPosition(QTextTable *t, const QTextTableCell &cell, const QPointF &pos);
 482     QRectF layoutTable(QTextTable *t, int layoutFrom, int layoutTo, QFixed parentY);
 483
 484     void positionFloat(QTextFrame *frame, QTextLine *currentLine = 0);
 485
 486     // calls the next one
 487     QRectF layoutFrame(QTextFrame *f, int layoutFrom, int layoutTo, QFixed parentY = 0);
 488     QRectF layoutFrame(QTextFrame *f, int layoutFrom, int layoutTo, QFixed frameWidth, QFixed frameHeight, QFixed parentY = 0);
 489
 490     void layoutBlock(const QTextBlock &bl, int blockPosition, const QTextBlockFormat &blockFormat,
 491                      QTextLayoutStruct *layoutStruct, int layoutFrom, int layoutTo, const QTextBlockFormat *previousBlockFormat);
 492     void layoutFlow(QTextFrame::Iterator it, QTextLayoutStruct *layoutStruct, int layoutFrom, int layoutTo, QFixed width = 0);
 493     void pageBreakInsideTable(QTextTable *table, QTextLayoutStruct *layoutStruct);
 494
 495
 496     void floatMargins(const QFixed &y, const QTextLayoutStruct *layoutStruct, QFixed *left, QFixed *right) const;
 497     QFixed findY(QFixed yFrom, const QTextLayoutStruct *layoutStruct, QFixed requiredWidth) const;
 498
 499     QVector<QCheckPoint> checkPoints;
 500
 501     QTextFrame::Iterator frameIteratorForYPosition(QFixed y) const;
 502     QTextFrame::Iterator frameIteratorForTextPosition(int position) const;
 503
 504     void ensureLayouted(QFixed y) const;
 505     void ensureLayoutedByPosition(int position) const;
 506     inline void ensureLayoutFinished() const
 507     { ensureLayoutedByPosition(INT_MAX); }
 508     void layoutStep() const;
 509
 510     QRectF frameBoundingRectInternal(QTextFrame *frame) const;
 511
 512     qreal scaleToDevice(qreal value) const;
 513     QFixed scaleToDevice(QFixed value) const;
 514 };
 515
 516 QTextDocumentLayoutPrivate::QTextDocumentLayoutPrivate()
 517     : fixedColumnWidth(-1),
 518       cursorWidth(1),
 519       currentLazyLayoutPosition(-1),
 520       lazyLayoutStepSize(1000),
 521       lastPageCount(-1)
 522 {
 523     showLayoutProgress = true;
 524     insideDocumentChange = false;
 525     idealWidth = 0;
 526     contentHasAlignment = false;
 527 }
 528
 529 QTextFrame::Iterator QTextDocumentLayoutPrivate::frameIteratorForYPosition(QFixed y) const
 530 {
 531     QTextFrame *rootFrame = document->rootFrame();
 532
 533     if (checkPoints.isEmpty()
 534         || y < 0 || y > data(rootFrame)->size.height)
 535         return rootFrame->begin();
 536
 537     QVector<QCheckPoint>::ConstIterator checkPoint = qLowerBound(checkPoints.begin(), checkPoints.end(), y);
 538     if (checkPoint == checkPoints.end())
 539         return rootFrame->begin();
 540
 541     if (checkPoint != checkPoints.begin())
 542         --checkPoint;
 543
 544     const int position = rootFrame->firstPosition() + checkPoint->positionInFrame;
 545     return frameIteratorForTextPosition(position);
 546 }
 547
 548 QTextFrame::Iterator QTextDocumentLayoutPrivate::frameIteratorForTextPosition(int position) const
 549 {
 550     QTextFrame *rootFrame = docPrivate->rootFrame();
 551
 552     const QTextDocumentPrivate::BlockMap &map = docPrivate->blockMap();
 553     const int begin = map.findNode(rootFrame->firstPosition());
 554     const int end = map.findNode(rootFrame->lastPosition()+1);
 555
 556     const int block = map.findNode(position);
 557     const int blockPos = map.position(block);
 558
 559     QTextFrame::iterator it(rootFrame, block, begin, end);
 560
 561     QTextFrame *containingFrame = docPrivate->frameAt(blockPos);
 562     if (containingFrame != rootFrame) {
 563         while (containingFrame->parentFrame() != rootFrame) {
 564             containingFrame = containingFrame->parentFrame();
 565             Q_ASSERT(containingFrame);
 566         }
 567
 568         it.cf = containingFrame;
 569         it.cb = 0;
 570     }
 571
 572     return it;
 573 }
 574
 575 QTextDocumentLayoutPrivate::HitPoint
 576 QTextDocumentLayoutPrivate::hitTest(QTextFrame *frame, const QFixedPoint &point, int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const
 577 {
 578     QTextFrameData *fd = data(frame);
 579     // #########
 580     if (fd->layoutDirty)
 581         return PointAfter;
 582     Q_ASSERT(!fd->layoutDirty);
 583     Q_ASSERT(!fd->sizeDirty);
 584     const QFixedPoint relativePoint(point.x - fd->position.x, point.y - fd->position.y);
 585
 586     QTextFrame *rootFrame = docPrivate->rootFrame();
 587
 588 //     LDEBUG << "checking frame" << frame->firstPosition() << "point=" << point
 589 //            << "position" << fd->position << "size" << fd->size;
 590     if (frame != rootFrame) {
 591         if (relativePoint.y < 0 || relativePoint.x < 0) {
 592             *position = frame->firstPosition() - 1;
 593 //             LDEBUG << "before pos=" << *position;
 594             return PointBefore;
 595         } else if (relativePoint.y > fd->size.height || relativePoint.x > fd->size.width) {
 596             *position = frame->lastPosition() + 1;
 597 //             LDEBUG << "after pos=" << *position;
 598             return PointAfter;
 599         }
 600     }
 601
 602     if (isFrameFromInlineObject(frame)) {
 603         *position = frame->firstPosition() - 1;
 604         return PointExact;
 605     }
 606
 607     if (QTextTable *table = qobject_cast<QTextTable *>(frame)) {
 608         const int rows = table->rows();
 609         const int columns = table->columns();
 610         QTextTableData *td = static_cast<QTextTableData *>(data(table));
 611
 612         if (!td->childFrameMap.isEmpty()) {
 613             for (int r = 0; r < rows; ++r) {
 614                 for (int c = 0; c < columns; ++c) {
 615                     QTextTableCell cell = table->cellAt(r, c);
 616                     if (cell.row() != r || cell.column() != c)
 617                         continue;
 618
 619                     QRectF cellRect = td->cellRect(cell);
 620                     const QFixedPoint cellPos = QFixedPoint::fromPointF(cellRect.topLeft());
 621                     const QFixedPoint pointInCell = relativePoint - cellPos;
 622
 623                     const QList<QTextFrame *> childFrames = td->childFrameMap.values(r + c * rows);
 624                     for (int i = 0; i < childFrames.size(); ++i) {
 625                         QTextFrame *child = childFrames.at(i);
 626                         if (isFrameFromInlineObject(child)
 627                             && child->frameFormat().position() != QTextFrameFormat::InFlow
 628                             && hitTest(child, pointInCell, position, l, accuracy) == PointExact)
 629                         {
 630                             return PointExact;
 631                         }
 632                     }
 633                 }
 634             }
 635         }
 636
 637         return hitTest(table, relativePoint, position, l, accuracy);
 638     }
 639
 640     const QList<QTextFrame *> childFrames = frame->childFrames();
 641     for (int i = 0; i < childFrames.size(); ++i) {
 642         QTextFrame *child = childFrames.at(i);
 643         if (isFrameFromInlineObject(child)
 644             && child->frameFormat().position() != QTextFrameFormat::InFlow
 645             && hitTest(child, relativePoint, position, l, accuracy) == PointExact)
 646         {
 647             return PointExact;
 648         }
 649     }
 650
 651     QTextFrame::Iterator it = frame->begin();
 652
 653     if (frame == rootFrame) {
 654         it = frameIteratorForYPosition(relativePoint.y);
 655
 656         Q_ASSERT(it.parentFrame() == frame);
 657     }
 658
 659     if (it.currentFrame())
 660         *position = it.currentFrame()->firstPosition();
 661     else
 662         *position = it.currentBlock().position();
 663
 664     return hitTest(it, PointBefore, relativePoint, position, l, accuracy);
 665 }
 666
 667 QTextDocumentLayoutPrivate::HitPoint
 668 QTextDocumentLayoutPrivate::hitTest(QTextFrame::Iterator it, HitPoint hit, const QFixedPoint &p,
 669                                     int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const
 670 {
 671     INC_INDENT;
 672
 673     for (; !it.atEnd(); ++it) {
 674         QTextFrame *c = it.currentFrame();
 675         HitPoint hp;
 676         int pos = -1;
 677         if (c) {
 678             hp = hitTest(c, p, &pos, l, accuracy);
 679         } else {
 680             hp = hitTest(it.currentBlock(), p, &pos, l, accuracy);
 681         }
 682         if (hp >= PointInside) {
 683             if (isEmptyBlockBeforeTable(it))
 684                 continue;
 685             hit = hp;
 686             *position = pos;
 687             break;
 688         }
 689         if (hp == PointBefore && pos < *position) {
 690             *position = pos;
 691             hit = hp;
 692         } else if (hp == PointAfter && pos > *position) {
 693             *position = pos;
 694             hit = hp;
 695         }
 696     }
 697
 698     DEC_INDENT;
 699 //     LDEBUG << "inside=" << hit << " pos=" << *position;
 700     return hit;
 701 }
 702
 703 QTextDocumentLayoutPrivate::HitPoint
 704 QTextDocumentLayoutPrivate::hitTest(QTextTable *table, const QFixedPoint &point,
 705                                     int *position, QTextLayout **l, Qt::HitTestAccuracy accuracy) const
 706 {
 707     QTextTableData *td = static_cast<QTextTableData *>(data(table));
 708
 709     QVector<QFixed>::ConstIterator rowIt = qLowerBound(td->rowPositions.constBegin(), td->rowPositions.constEnd(), point.y);
 710     if (rowIt == td->rowPositions.constEnd()) {
 711         rowIt = td->rowPositions.constEnd() - 1;
 712     } else if (rowIt != td->rowPositions.constBegin()) {
 713         --rowIt;
 714     }
 715
 716     QVector<QFixed>::ConstIterator colIt = qLowerBound(td->columnPositions.constBegin(), td->columnPositions.constEnd(), point.x);
 717     if (colIt == td->columnPositions.constEnd()) {
 718         colIt = td->columnPositions.constEnd() - 1;
 719     } else if (colIt != td->columnPositions.constBegin()) {
 720         --colIt;
 721     }
 722
 723     QTextTableCell cell = table->cellAt(rowIt - td->rowPositions.constBegin(),
 724                                         colIt - td->columnPositions.constBegin());
 725     if (!cell.isValid())
 726         return PointBefore;
 727
 728     *position = cell.firstPosition();
 729
 730     HitPoint hp = hitTest(cell.begin(), PointInside, point - td->cellPosition(cell), position, l, accuracy);
 731
 732     if (hp == PointExact)
 733         return hp;
 734     if (hp == PointAfter)
 735         *position = cell.lastPosition();
 736     return PointInside;
 737 }
 738
 739 QTextDocumentLayoutPrivate::HitPoint
 740 QTextDocumentLayoutPrivate::hitTest(QTextBlock bl, const QFixedPoint &point, int *position, QTextLayout **l,
 741                                     Qt::HitTestAccuracy accuracy) const
 742 {
 743     QTextLayout *tl = bl.layout();
 744     QRectF textrect = tl->boundingRect();
 745     textrect.translate(tl->position());
 746 //     LDEBUG << "    checking block" << bl.position() << "point=" << point
 747 //            << "    tlrect" << textrect;
 748     *position = bl.position();
 749     if (point.y.toReal() < textrect.top()) {
 750 //             LDEBUG << "    before pos=" << *position;
 751         return PointBefore;
 752     } else if (point.y.toReal() > textrect.bottom()) {
 753         *position += bl.length();
 754 //             LDEBUG << "    after pos=" << *position;
 755         return PointAfter;
 756     }
 757
 758     QPointF pos = point.toPointF() - tl->position();
 759
 760     // ### rtl?
 761
 762     HitPoint hit = PointInside;
 763     *l = tl;
 764     int off = 0;
 765     for (int i = 0; i < tl->lineCount(); ++i) {
 766         QTextLine line = tl->lineAt(i);
 767         const QRectF lr = line.naturalTextRect();
 768         if (lr.top() > pos.y()) {
 769             off = qMin(off, line.textStart());
 770         } else if (lr.bottom() <= pos.y()) {
 771             off = qMax(off, line.textStart() + line.textLength());
 772         } else {
 773             if (lr.left() <= pos.x() && lr.right() >= pos.x())
 774                 hit = PointExact;
 775             // when trying to hit an anchor we want it to hit not only in the left
 776             // half
 777             if (accuracy == Qt::ExactHit)
 778                 off = line.xToCursor(pos.x(), QTextLine::CursorOnCharacter);
 779             else
 780                 off = line.xToCursor(pos.x(), QTextLine::CursorBetweenCharacters);
 781             break;
 782         }
 783     }
 784     *position += off;
 785
 786 //     LDEBUG << "    inside=" << hit << " pos=" << *position;
 787     return hit;
 788 }
 789
 790 // ### could be moved to QTextBlock
 791 QFixed QTextDocumentLayoutPrivate::blockIndent(const QTextBlockFormat &blockFormat) const
 792 {
 793     qreal indent = blockFormat.indent();
 794
 795     QTextObject *object = document->objectForFormat(blockFormat);
 796     if (object)
 797         indent += object->format().toListFormat().indent();
 798
 799     if (qIsNull(indent))
 800         return 0;
 801
 802     qreal scale = 1;
 803     if (paintDevice) {
 804         scale = qreal(paintDevice->logicalDpiY()) / qreal(qt_defaultDpi());
 805     }
 806
 807     return QFixed::fromReal(indent * scale * document->indentWidth());
 808 }
 809
 810 void QTextDocumentLayoutPrivate::drawBorder(QPainter *painter, const QRectF &rect, qreal topMargin, qreal bottomMargin,
 811                                             qreal border, const QBrush &brush, QTextFrameFormat::BorderStyle style) const
 812 {
 813     const qreal pageHeight = document->pageSize().height();
 814     const int topPage = pageHeight > 0 ? static_cast<int>(rect.top() / pageHeight) : 0;
 815     const int bottomPage = pageHeight > 0 ? static_cast<int>((rect.bottom() + border) / pageHeight) : 0;
 816
 817 #ifndef QT_NO_CSSPARSER
 818     QCss::BorderStyle cssStyle = static_cast<QCss::BorderStyle>(style + 1);
 819 #endif //QT_NO_CSSPARSER
 820
 821     bool turn_off_antialiasing = !(painter->renderHints() & QPainter::Antialiasing);
 822     painter->setRenderHint(QPainter::Antialiasing);
 823
 824     for (int i = topPage; i <= bottomPage; ++i) {
 825         QRectF clipped = rect.toRect();
 826
 827         if (topPage != bottomPage) {
 828             clipped.setTop(qMax(clipped.top(), i * pageHeight + topMargin - border));
 829             clipped.setBottom(qMin(clipped.bottom(), (i + 1) * pageHeight - bottomMargin));
 830
 831             if (clipped.bottom() <= clipped.top())
 832                 continue;
 833         }
 834 #ifndef QT_NO_CSSPARSER
 835         qDrawEdge(painter, clipped.left(), clipped.top(), clipped.left() + border, clipped.bottom() + border, 0, 0, QCss::LeftEdge, cssStyle, brush);
 836         qDrawEdge(painter, clipped.left() + border, clipped.top(), clipped.right() + border, clipped.top() + border, 0, 0, QCss::TopEdge, cssStyle, brush);
 837         qDrawEdge(painter, clipped.right(), clipped.top() + border, clipped.right() + border, clipped.bottom(), 0, 0, QCss::RightEdge, cssStyle, brush);
 838         qDrawEdge(painter, clipped.left() + border, clipped.bottom(), clipped.right() + border, clipped.bottom() + border, 0, 0, QCss::BottomEdge, cssStyle, brush);
 839 #else
 840         painter->save();
 841         painter->setPen(Qt::NoPen);
 842         painter->setBrush(brush);
 843         painter->drawRect(QRectF(clipped.left(), clipped.top(), clipped.left() + border, clipped.bottom() + border));
 844         painter->drawRect(QRectF(clipped.left() + border, clipped.top(), clipped.right() + border, clipped.top() + border));
 845         painter->drawRect(QRectF(clipped.right(), clipped.top() + border, clipped.right() + border, clipped.bottom()));
 846         painter->drawRect(QRectF(clipped.left() + border, clipped.bottom(), clipped.right() + border, clipped.bottom() + border));
 847         painter->restore();
 848 #endif //QT_NO_CSSPARSER
 849     }
 850     if (turn_off_antialiasing)
 851         painter->setRenderHint(QPainter::Antialiasing, false);
 852 }
 853
 854 void QTextDocumentLayoutPrivate::drawFrameDecoration(QPainter *painter, QTextFrame *frame, QTextFrameData *fd, const QRectF &clip, const QRectF &rect) const
 855 {
 856
 857     const QBrush bg = frame->frameFormat().background();
 858     if (bg != Qt::NoBrush) {
 859         QRectF bgRect = rect;
 860         bgRect.adjust((fd->leftMargin + fd->border).toReal(),
 861                       (fd->topMargin + fd->border).toReal(),
 862                       - (fd->rightMargin + fd->border).toReal(),
 863                       - (fd->bottomMargin + fd->border).toReal());
 864
 865         QRectF gradientRect; // invalid makes it default to bgRect
 866         QPointF origin = bgRect.topLeft();
 867         if (!frame->parentFrame()) {
 868             bgRect = clip;
 869             gradientRect.setWidth(painter->device()->width());
 870             gradientRect.setHeight(painter->device()->height());
 871         }
 872         fillBackground(painter, bgRect, bg, origin, gradientRect);
 873     }
 874     if (fd->border != 0) {
 875         painter->save();
 876         painter->setBrush(Qt::lightGray);
 877         painter->setPen(Qt::NoPen);
 878
 879         const qreal leftEdge = rect.left() + fd->leftMargin.toReal();
 880         const qreal border = fd->border.toReal();
 881         const qreal topMargin = fd->topMargin.toReal();
 882         const qreal leftMargin = fd->leftMargin.toReal();
 883         const qreal bottomMargin = fd->bottomMargin.toReal();
 884         const qreal rightMargin = fd->rightMargin.toReal();
 885         const qreal w = rect.width() - 2 * border - leftMargin - rightMargin;
 886         const qreal h = rect.height() - 2 * border - topMargin - bottomMargin;
 887
 888         drawBorder(painter, QRectF(leftEdge, rect.top() + topMargin, w + border, h + border),
 889                    fd->effectiveTopMargin.toReal(), fd->effectiveBottomMargin.toReal(),
 890                    border, frame->frameFormat().borderBrush(), frame->frameFormat().borderStyle());
 891
 892         painter->restore();
 893     }
 894 }
 895
 896 static void adjustContextSelectionsForCell(QAbstractTextDocumentLayout::PaintContext &cell_context,
 897                                            const QTextTableCell &cell,
 898                                            int r, int c,
 899                                            const int *selectedTableCells)
 900 {
 901     for (int i = 0; i < cell_context.selections.size(); ++i) {
 902         int row_start = selectedTableCells[i * 4];
 903         int col_start = selectedTableCells[i * 4 + 1];
 904         int num_rows = selectedTableCells[i * 4 + 2];
 905         int num_cols = selectedTableCells[i * 4 + 3];
 906
 907         if (row_start != -1) {
 908             if (r >= row_start && r < row_start + num_rows
 909                 && c >= col_start && c < col_start + num_cols)
 910             {
 911                 int firstPosition = cell.firstPosition();
 912                 int lastPosition = cell.lastPosition();
 913
 914                 // make sure empty cells are still selected
 915                 if (firstPosition == lastPosition)
 916                     ++lastPosition;
 917
 918                 cell_context.selections[i].cursor.setPosition(firstPosition);
 919                 cell_context.selections[i].cursor.setPosition(lastPosition, QTextCursor::KeepAnchor);
 920             } else {
 921                 cell_context.selections[i].cursor.clearSelection();
 922             }
 923         }
 924
 925         // FullWidthSelection is not useful for tables
 926         cell_context.selections[i].format.clearProperty(QTextFormat::FullWidthSelection);
 927     }
 928 }
 929
 930 void QTextDocumentLayoutPrivate::drawFrame(const QPointF &offset, QPainter *painter,
 931                                            const QAbstractTextDocumentLayout::PaintContext &context,
 932                                            QTextFrame *frame) const
 933 {
 934     QTextFrameData *fd = data(frame);
 935     // #######
 936     if (fd->layoutDirty)
 937         return;
 938     Q_ASSERT(!fd->sizeDirty);
 939     Q_ASSERT(!fd->layoutDirty);
 940
 941     const QPointF off = offset + fd->position.toPointF();
 942     if (context.clip.isValid()
 943         && (off.y() > context.clip.bottom() || off.y() + fd->size.height.toReal() < context.clip.top()
 944             || off.x() > context.clip.right() || off.x() + fd->size.width.toReal() < context.clip.left()))
 945         return;
 946
 947 //     LDEBUG << debug_indent << "drawFrame" << frame->firstPosition() << "--" << frame->lastPosition() << "at" << offset;
 948 //     INC_INDENT;
 949
 950     // if the cursor is /on/ a table border we may need to repaint it
 951     // afterwards, as we usually draw the decoration first
 952     QTextBlock cursorBlockNeedingRepaint;
 953     QPointF offsetOfRepaintedCursorBlock = off;
 954
 955     QTextTable *table = qobject_cast<QTextTable *>(frame);
 956     const QRectF frameRect(off, fd->size.toSizeF());
 957
 958     if (table) {
 959         const int rows = table->rows();
 960         const int columns = table->columns();
 961         QTextTableData *td = static_cast<QTextTableData *>(data(table));
 962
 963         QVarLengthArray<int> selectedTableCells(context.selections.size() * 4);
 964         for (int i = 0; i < context.selections.size(); ++i) {
 965             const QAbstractTextDocumentLayout::Selection &s = context.selections.at(i);
 966             int row_start = -1, col_start = -1, num_rows = -1, num_cols = -1;
 967
 968             if (s.cursor.currentTable() == table)
 969                 s.cursor.selectedTableCells(&row_start, &num_rows, &col_start, &num_cols);
 970
 971             selectedTableCells[i * 4] = row_start;
 972             selectedTableCells[i * 4 + 1] = col_start;
 973             selectedTableCells[i * 4 + 2] = num_rows;
 974             selectedTableCells[i * 4 + 3] = num_cols;
 975         }
 976
 977         QFixed pageHeight = QFixed::fromReal(document->pageSize().height());
 978         if (pageHeight <= 0)
 979             pageHeight = QFIXED_MAX;
 980
 981         const int tableStartPage = (td->position.y / pageHeight).truncate();
 982         const int tableEndPage = ((td->position.y + td->size.height) / pageHeight).truncate();
 983
 984         qreal border = td->border.toReal();
 985         drawFrameDecoration(painter, frame, fd, context.clip, frameRect);
 986
 987         // draw the table headers
 988         const int headerRowCount = qMin(table->format().headerRowCount(), rows - 1);
 989         int page = tableStartPage + 1;
 990         while (page <= tableEndPage) {
 991             const QFixed pageTop = page * pageHeight + td->effectiveTopMargin + td->cellSpacing + td->border;
 992             const qreal headerOffset = (pageTop - td->rowPositions.at(0)).toReal();
 993             for (int r = 0; r < headerRowCount; ++r) {
 994                 for (int c = 0; c < columns; ++c) {
 995                     QTextTableCell cell = table->cellAt(r, c);
 996                     QAbstractTextDocumentLayout::PaintContext cell_context = context;
 997                     adjustContextSelectionsForCell(cell_context, cell, r, c, selectedTableCells.data());
 998                     QRectF cellRect = td->cellRect(cell);
 999
1000                     cellRect.translate(off.x(), headerOffset);
1001                     // we need to account for the cell border in the clipping test
1002                     int leftAdjust = qMin(qreal(0), 1 - border);
1003                     if (cell_context.clip.isValid() && !cellRect.adjusted(leftAdjust, leftAdjust, border, border).intersects(cell_context.clip))
1004                         continue;
1005
1006                     drawTableCell(cellRect, painter, cell_context, table, td, r, c, &cursorBlockNeedingRepaint,
1007                                   &offsetOfRepaintedCursorBlock);
1008                 }
1009             }
1010             ++page;
1011         }
1012
1013         int firstRow = 0;
1014         int lastRow = rows;
1015
1016         if (context.clip.isValid()) {
1017             QVector<QFixed>::ConstIterator rowIt = qLowerBound(td->rowPositions.constBegin(), td->rowPositions.constEnd(), QFixed::fromReal(context.clip.top() - off.y()));
1018             if (rowIt != td->rowPositions.constEnd() && rowIt != td->rowPositions.constBegin()) {
1019                 --rowIt;
1020                 firstRow = rowIt - td->rowPositions.constBegin();
1021             }
1022
1023             rowIt = qUpperBound(td->rowPositions.constBegin(), td->rowPositions.constEnd(), QFixed::fromReal(context.clip.bottom() - off.y()));
1024             if (rowIt != td->rowPositions.constEnd()) {
1025                 ++rowIt;
1026                 lastRow = rowIt - td->rowPositions.constBegin();
1027             }
1028         }
1029
1030         for (int c = 0; c < columns; ++c) {
1031             QTextTableCell cell = table->cellAt(firstRow, c);
1032             firstRow = qMin(firstRow, cell.row());
1033         }
1034
1035         for (int r = firstRow; r < lastRow; ++r) {
1036             for (int c = 0; c < columns; ++c) {
1037                 QTextTableCell cell = table->cellAt(r, c);
1038                 QAbstractTextDocumentLayout::PaintContext cell_context = context;
1039                 adjustContextSelectionsForCell(cell_context, cell, r, c, selectedTableCells.data());
1040                 QRectF cellRect = td->cellRect(cell);
1041
1042                 cellRect.translate(off);
1043                 // we need to account for the cell border in the clipping test
1044                 int leftAdjust = qMin(qreal(0), 1 - border);
1045                 if (cell_context.clip.isValid() && !cellRect.adjusted(leftAdjust, leftAdjust, border, border).intersects(cell_context.clip))
1046                     continue;
1047
1048                 drawTableCell(cellRect, painter, cell_context, table, td, r, c, &cursorBlockNeedingRepaint,
1049                               &offsetOfRepaintedCursorBlock);
1050             }
1051         }
1052
1053     } else {
1054         drawFrameDecoration(painter, frame, fd, context.clip, frameRect);
1055
1056         QTextFrame::Iterator it = frame->begin();
1057
1058         if (frame == docPrivate->rootFrame())
1059             it = frameIteratorForYPosition(QFixed::fromReal(context.clip.top()));
1060
1061         QList<QTextFrame *> floats;
1062         for (int i = 0; i < fd->floats.count(); ++i)
1063             floats.append(fd->floats.at(i));
1064
1065         drawFlow(off, painter, context, it, floats, &cursorBlockNeedingRepaint);
1066     }
1067
1068     if (cursorBlockNeedingRepaint.isValid()) {
1069         const QPen oldPen = painter->pen();
1070         painter->setPen(context.palette.color(QPalette::Text));
1071         const int cursorPos = context.cursorPosition - cursorBlockNeedingRepaint.position();
1072         cursorBlockNeedingRepaint.layout()->drawCursor(painter, offsetOfRepaintedCursorBlock,
1073                                                        cursorPos, cursorWidth);
1074         painter->setPen(oldPen);
1075     }
1076
1077 //     DEC_INDENT;
1078
1079     return;
1080 }
1081
1082 void QTextDocumentLayoutPrivate::drawTableCell(const QRectF &cellRect, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &cell_context,
1083                                                QTextTable *table, QTextTableData *td, int r, int c,
1084                                                QTextBlock *cursorBlockNeedingRepaint, QPointF *cursorBlockOffset) const
1085 {
1086     QTextTableCell cell = table->cellAt(r, c);
1087     int rspan = cell.rowSpan();
1088     int cspan = cell.columnSpan();
1089     if (rspan != 1) {
1090         int cr = cell.row();
1091         if (cr != r)
1092             return;
1093     }
1094     if (cspan != 1) {
1095         int cc = cell.column();
1096         if (cc != c)
1097             return;
1098     }
1099
1100     QTextFormat fmt = cell.format();
1101     const QFixed leftPadding = td->leftPadding(fmt);
1102     const QFixed topPadding = td->topPadding(fmt);
1103
1104     if (td->border != 0) {
1105         const QBrush oldBrush = painter->brush();
1106         const QPen oldPen = painter->pen();
1107
1108         const qreal border = td->border.toReal();
1109
1110         QRectF borderRect(cellRect.left() - border, cellRect.top() - border, cellRect.width() + border, cellRect.height() + border);
1111
1112         // invert the border style for cells
1113         QTextFrameFormat::BorderStyle cellBorder = table->format().borderStyle();
1114         switch (cellBorder) {
1115         case QTextFrameFormat::BorderStyle_Inset:
1116             cellBorder = QTextFrameFormat::BorderStyle_Outset;
1117             break;
1118         case QTextFrameFormat::BorderStyle_Outset:
1119             cellBorder = QTextFrameFormat::BorderStyle_Inset;
1120             break;
1121         case QTextFrameFormat::BorderStyle_Groove:
1122             cellBorder = QTextFrameFormat::BorderStyle_Ridge;
1123             break;
1124         case QTextFrameFormat::BorderStyle_Ridge:
1125             cellBorder = QTextFrameFormat::BorderStyle_Groove;
1126             break;
1127         default:
1128             break;
1129         }
1130
1131         qreal topMargin = (td->effectiveTopMargin + td->cellSpacing + td->border).toReal();
1132         qreal bottomMargin = (td->effectiveBottomMargin + td->cellSpacing + td->border).toReal();
1133
1134         const int headerRowCount = qMin(table->format().headerRowCount(), table->rows() - 1);
1135         if (r >= headerRowCount)
1136             topMargin += td->headerHeight.toReal();
1137
1138         drawBorder(painter, borderRect, topMargin, bottomMargin,
1139                    border, table->format().borderBrush(), cellBorder);
1140
1141         painter->setBrush(oldBrush);
1142         painter->setPen(oldPen);
1143     }
1144
1145     const QBrush bg = cell.format().background();
1146     const QPointF brushOrigin = painter->brushOrigin();
1147     if (bg.style() != Qt::NoBrush) {
1148         fillBackground(painter, cellRect, bg, cellRect.topLeft());
1149
1150         if (bg.style() > Qt::SolidPattern)
1151             painter->setBrushOrigin(cellRect.topLeft());
1152     }
1153
1154     const QFixed verticalOffset = td->cellVerticalOffsets.at(c + r * table->columns());
1155
1156     const QPointF cellPos = QPointF(cellRect.left() + leftPadding.toReal(),
1157                                     cellRect.top() + (topPadding + verticalOffset).toReal());
1158
1159     QTextBlock repaintBlock;
1160     drawFlow(cellPos, painter, cell_context, cell.begin(),
1161              td->childFrameMap.values(r + c * table->rows()),
1162              &repaintBlock);
1163     if (repaintBlock.isValid()) {
1164         *cursorBlockNeedingRepaint = repaintBlock;
1165         *cursorBlockOffset = cellPos;
1166     }
1167
1168     if (bg.style() > Qt::SolidPattern)
1169         painter->setBrushOrigin(brushOrigin);
1170 }
1171
1172 void QTextDocumentLayoutPrivate::drawFlow(const QPointF &offset, QPainter *painter, const QAbstractTextDocumentLayout::PaintContext &context,
1173                                           QTextFrame::Iterator it, const QList<QTextFrame *> &floats, QTextBlock *cursorBlockNeedingRepaint) const
1174 {
1175     Q_Q(const QTextDocumentLayout);
1176     const bool inRootFrame = (!it.atEnd() && it.parentFrame() && it.parentFrame()->parentFrame() == 0);
1177
1178     QVector<QCheckPoint>::ConstIterator lastVisibleCheckPoint = checkPoints.end();
1179     if (inRootFrame && context.clip.isValid()) {
1180         lastVisibleCheckPoint = qLowerBound(checkPoints.begin(), checkPoints.end(), QFixed::fromReal(context.clip.bottom()));
1181     }
1182
1183     QTextBlock previousBlock;
1184     QTextFrame *previousFrame = 0;
1185
1186     for (; !it.atEnd(); ++it) {
1187         QTextFrame *c = it.currentFrame();
1188
1189         if (inRootFrame && !checkPoints.isEmpty()) {
1190             int currentPosInDoc;
1191             if (c)
1192                 currentPosInDoc = c->firstPosition();
1193             else
1194                 currentPosInDoc = it.currentBlock().position();
1195
1196             // if we're past what is already laid out then we're better off
1197             // not trying to draw things that may not be positioned correctly yet
1198             if (currentPosInDoc >= checkPoints.last().positionInFrame)
1199                 break;
1200
1201             if (lastVisibleCheckPoint != checkPoints.end()
1202                 && context.clip.isValid()
1203                 && currentPosInDoc >= lastVisibleCheckPoint->positionInFrame
1204                )
1205                 break;
1206         }
1207
1208         if (c)
1209             drawFrame(offset, painter, context, c);
1210         else {
1211             QAbstractTextDocumentLayout::PaintContext pc = context;
1212             if (isEmptyBlockAfterTable(it.currentBlock(), previousFrame))
1213                 pc.selections.clear();
1214             drawBlock(offset, painter, pc, it.currentBlock(), inRootFrame);
1215         }
1216
1217         // when entering a table and the previous block is empty
1218         // then layoutFlow 'hides' the block that just causes a
1219         // new line by positioning it /on/ the table border. as we
1220         // draw that block before the table itself the decoration
1221         // 'overpaints' the cursor and we need to paint it afterwards
1222         // again
1223         if (isEmptyBlockBeforeTable(previousBlock, previousBlock.blockFormat(), it)
1224             && previousBlock.contains(context.cursorPosition)
1225            ) {
1226             *cursorBlockNeedingRepaint = previousBlock;
1227         }
1228
1229         previousBlock = it.currentBlock();
1230         previousFrame = c;
1231     }
1232
1233     for (int i = 0; i < floats.count(); ++i) {
1234         QTextFrame *frame = floats.at(i);
1235         if (!isFrameFromInlineObject(frame)
1236             || frame->frameFormat().position() == QTextFrameFormat::InFlow)
1237             continue;
1238
1239         const int pos = frame->firstPosition() - 1;
1240         QTextCharFormat format = const_cast<QTextDocumentLayout *>(q)->format(pos);
1241         QTextObjectInterface *handler = q->handlerForObject(format.objectType());
1242         if (handler) {
1243             QRectF rect = frameBoundingRectInternal(frame);
1244             handler->drawObject(painter, rect, document, pos, format);
1245         }
1246     }
1247 }
1248
1249 void QTextDocumentLayoutPrivate::drawBlock(const QPointF &offset, QPainter *painter,
1250                                            const QAbstractTextDocumentLayout::PaintContext &context,
1251                                            QTextBlock bl, bool inRootFrame) const
1252 {
1253     const QTextLayout *tl = bl.layout();
1254     QRectF r = tl->boundingRect();
1255     r.translate(offset + tl->position());
1256     if (context.clip.isValid() && (r.bottom() < context.clip.y() || r.top() > context.clip.bottom()))
1257         return;
1258 //      LDEBUG << debug_indent << "drawBlock" << bl.position() << "at" << offset << "br" << tl->boundingRect();
1259
1260     QTextBlockFormat blockFormat = bl.blockFormat();
1261
1262     QBrush bg = blockFormat.background();
1263     if (bg != Qt::NoBrush) {
1264         QRectF rect = r;
1265
1266         // extend the background rectangle if we're in the root frame with NoWrap,
1267         // as the rect of the text block will then be only the width of the text
1268         // instead of the full page width
1269         if (inRootFrame && document->pageSize().width() <= 0) {
1270             const QTextFrameData *fd = data(document->rootFrame());
1271             rect.setRight((fd->size.width - fd->rightMargin).toReal());
1272         }
1273
1274         fillBackground(painter, rect, bg, r.topLeft());
1275     }
1276
1277     QVector<QTextLayout::FormatRange> selections;
1278     int blpos = bl.position();
1279     int bllen = bl.length();
1280     const QTextCharFormat *selFormat = 0;
1281     for (int i = 0; i < context.selections.size(); ++i) {
1282         const QAbstractTextDocumentLayout::Selection &range = context.selections.at(i);
1283         const int selStart = range.cursor.selectionStart() - blpos;
1284         const int selEnd = range.cursor.selectionEnd() - blpos;
1285         if (selStart < bllen && selEnd > 0
1286              && selEnd > selStart) {
1287             QTextLayout::FormatRange o;
1288             o.start = selStart;
1289             o.length = selEnd - selStart;
1290             o.format = range.format;
1291             selections.append(o);
1292         } else if (! range.cursor.hasSelection() && range.format.hasProperty(QTextFormat::FullWidthSelection)
1293                    && bl.contains(range.cursor.position())) {
1294             // for full width selections we don't require an actual selection, just
1295             // a position to specify the line. that's more convenience in usage.
1296             QTextLayout::FormatRange o;
1297             QTextLine l = tl->lineForTextPosition(range.cursor.position() - blpos);
1298             o.start = l.textStart();
1299             o.length = l.textLength();
1300             if (o.start + o.length == bllen - 1)
1301                 ++o.length; // include newline
1302             o.format = range.format;
1303             selections.append(o);
1304        }
1305         if (selStart < 0 && selEnd >= 1)
1306             selFormat = &range.format;
1307     }
1308
1309     QTextObject *object = document->objectForFormat(bl.blockFormat());
1310     if (object && object->format().toListFormat().style() != QTextListFormat::ListStyleUndefined)
1311         drawListItem(offset, painter, context, bl, selFormat);
1312
1313     QPen oldPen = painter->pen();
1314     painter->setPen(context.palette.color(QPalette::Text));
1315
1316     tl->draw(painter, offset, selections, context.clip.isValid() ? (context.clip & clipRect) : clipRect);
1317
1318     if ((context.cursorPosition >= blpos && context.cursorPosition < blpos + bllen)
1319         || (context.cursorPosition < -1 && !tl->preeditAreaText().isEmpty())) {
1320         int cpos = context.cursorPosition;
1321         if (cpos < -1)
1322             cpos = tl->preeditAreaPosition() - (cpos + 2);
1323         else
1324             cpos -= blpos;
1325         tl->drawCursor(painter, offset, cpos, cursorWidth);
1326     }
1327
1328     if (blockFormat.hasProperty(QTextFormat::BlockTrailingHorizontalRulerWidth)) {
1329         const qreal width = blockFormat.lengthProperty(QTextFormat::BlockTrailingHorizontalRulerWidth).value(r.width());
1330         painter->setPen(context.palette.color(QPalette::Dark));
1331         qreal y = r.bottom();
1332         if (bl.length() == 1)
1333             y = r.top() + r.height() / 2;
1334
1335         const qreal middleX = r.left() + r.width() / 2;
1336         painter->drawLine(QLineF(middleX - width / 2, y, middleX + width / 2, y));
1337     }
1338
1339     painter->setPen(oldPen);
1340 }
1341
1342
1343 void QTextDocumentLayoutPrivate::drawListItem(const QPointF &offset, QPainter *painter,
1344                                               const QAbstractTextDocumentLayout::PaintContext &context,
1345                                               QTextBlock bl, const QTextCharFormat *selectionFormat) const
1346 {
1347     Q_Q(const QTextDocumentLayout);
1348     const QTextBlockFormat blockFormat = bl.blockFormat();
1349     const QTextCharFormat charFormat = QTextCursor(bl).charFormat();
1350     QFont font(charFormat.font());
1351     if (q->paintDevice())
1352         font = QFont(font, q->paintDevice());
1353
1354     const QFontMetrics fontMetrics(font);
1355     QTextObject * const object = document->objectForFormat(blockFormat);
1356     const QTextListFormat lf = object->format().toListFormat();
1357     int style = lf.style();
1358     QString itemText;
1359     QSizeF size;
1360
1361     if (blockFormat.hasProperty(QTextFormat::ListStyle))
1362         style = QTextListFormat::Style(blockFormat.intProperty(QTextFormat::ListStyle));
1363
1364     QTextLayout *layout = bl.layout();
1365     if (layout->lineCount() == 0)
1366         return;
1367     QTextLine firstLine = layout->lineAt(0);
1368     Q_ASSERT(firstLine.isValid());
1369     QPointF pos = (offset + layout->position()).toPoint();
1370     Qt::LayoutDirection dir = bl.textDirection();
1371     {
1372         QRectF textRect = firstLine.naturalTextRect();
1373         pos += textRect.topLeft().toPoint();
1374         if (dir == Qt::RightToLeft)
1375             pos.rx() += textRect.width();
1376     }
1377
1378     switch (style) {
1379     case QTextListFormat::ListDecimal:
1380     case QTextListFormat::ListLowerAlpha:
1381     case QTextListFormat::ListUpperAlpha:
1382     case QTextListFormat::ListLowerRoman:
1383     case QTextListFormat::ListUpperRoman:
1384         itemText = static_cast<QTextList *>(object)->itemText(bl);
1385         size.setWidth(fontMetrics.width(itemText));
1386         size.setHeight(fontMetrics.height());
1387         break;
1388
1389     case QTextListFormat::ListSquare:
1390     case QTextListFormat::ListCircle:
1391     case QTextListFormat::ListDisc:
1392         size.setWidth(fontMetrics.lineSpacing() / 3);
1393         size.setHeight(size.width());
1394         break;
1395
1396     case QTextListFormat::ListStyleUndefined:
1397         return;
1398     default: return;
1399     }
1400
1401     QRectF r(pos, size);
1402
1403     qreal xoff = fontMetrics.width(QLatin1Char(' '));
1404     if (dir == Qt::LeftToRight)
1405         xoff = -xoff - size.width();
1406     r.translate( xoff, (fontMetrics.height() / 2 - size.height() / 2));
1407
1408     painter->save();
1409
1410     painter->setRenderHint(QPainter::Antialiasing);
1411
1412     if (selectionFormat) {
1413         painter->setPen(QPen(selectionFormat->foreground(), 0));
1414         painter->fillRect(r, selectionFormat->background());
1415     } else {
1416         QBrush fg = charFormat.foreground();
1417         if (fg == Qt::NoBrush)
1418             fg = context.palette.text();
1419         painter->setPen(QPen(fg, 0));
1420     }
1421
1422     QBrush brush = context.palette.brush(QPalette::Text);
1423
1424     switch (style) {
1425     case QTextListFormat::ListDecimal:
1426     case QTextListFormat::ListLowerAlpha:
1427     case QTextListFormat::ListUpperAlpha:
1428     case QTextListFormat::ListLowerRoman:
1429     case QTextListFormat::ListUpperRoman: {
1430         QTextLayout layout(itemText, font, q->paintDevice());
1431         layout.setCacheEnabled(true);
1432         QTextOption option(Qt::AlignLeft | Qt::AlignAbsolute);
1433         option.setTextDirection(dir);
1434         layout.setTextOption(option);
1435         layout.beginLayout();
1436         QTextLine line = layout.createLine();
1437         if (line.isValid())
1438             line.setLeadingIncluded(true);
1439         layout.endLayout();
1440         layout.draw(painter, QPointF(r.left(), pos.y()));
1441         break;
1442     }
1443     case QTextListFormat::ListSquare:
1444         painter->fillRect(r, brush);
1445         break;
1446     case QTextListFormat::ListCircle:
1447         painter->setPen(QPen(brush, 0));
1448         painter->drawEllipse(r.translated(0.5, 0.5)); // pixel align for sharper rendering
1449         break;
1450     case QTextListFormat::ListDisc:
1451         painter->setBrush(brush);
1452         painter->setPen(Qt::NoPen);
1453         painter->drawEllipse(r);
1454         break;
1455     case QTextListFormat::ListStyleUndefined:
1456         break;
1457     default:
1458         break;
1459     }
1460
1461     painter->restore();
1462 }
1463
1464 static QFixed flowPosition(const QTextFrame::iterator it)
1465 {
1466     if (it.atEnd())
1467         return 0;
1468
1469     if (it.currentFrame()) {
1470         return data(it.currentFrame())->position.y;
1471     } else {
1472         QTextBlock block = it.currentBlock();
1473         QTextLayout *layout = block.layout();
1474         if (layout->lineCount() == 0)
1475             return QFixed::fromReal(layout->position().y());
1476         else
1477             return QFixed::fromReal(layout->position().y() + layout->lineAt(0).y());
1478     }
1479 }
1480
1481 static QFixed firstChildPos(const QTextFrame *f)
1482 {
1483     return flowPosition(f->begin());
1484 }
1485
1486 QTextLayoutStruct QTextDocumentLayoutPrivate::layoutCell(QTextTable *t, const QTextTableCell &cell, QFixed width,
1487                                                         int layoutFrom, int layoutTo, QTextTableData *td,
1488                                                         QFixed absoluteTableY, bool withPageBreaks)
1489 {
1490     LDEBUG << "layoutCell";
1491     QTextLayoutStruct layoutStruct;
1492     layoutStruct.frame = t;
1493     layoutStruct.minimumWidth = 0;
1494     layoutStruct.maximumWidth = QFIXED_MAX;
1495     layoutStruct.y = 0;
1496
1497     const QTextFormat fmt = cell.format();
1498     const QFixed topPadding = td->topPadding(fmt);
1499     if (withPageBreaks) {
1500         layoutStruct.frameY = absoluteTableY + td->rowPositions.at(cell.row()) + topPadding;
1501     }
1502     layoutStruct.x_left = 0;
1503     layoutStruct.x_right = width;
1504     // we get called with different widths all the time (for example for figuring
1505     // out the min/max widths), so we always have to do the full layout ;(
1506     // also when for example in a table layoutFrom/layoutTo affect only one cell,
1507     // making that one cell grow the available width of the other cells may change
1508     // (shrink) and therefore when layoutCell gets called for them they have to
1509     // be re-laid out, even if layoutFrom/layoutTo is not in their range. Hence
1510     // this line:
1511
1512     layoutStruct.pageHeight = QFixed::fromReal(document->pageSize().height());
1513     if (layoutStruct.pageHeight < 0 || !withPageBreaks)
1514         layoutStruct.pageHeight = QFIXED_MAX;
1515     const int currentPage = layoutStruct.currentPage();
1516     layoutStruct.pageTopMargin = td->effectiveTopMargin + td->cellSpacing + td->border + topPadding;
1517     layoutStruct.pageBottomMargin = td->effectiveBottomMargin + td->cellSpacing + td->border + td->bottomPadding(fmt);
1518     layoutStruct.pageBottom = (currentPage + 1) * layoutStruct.pageHeight - layoutStruct.pageBottomMargin;
1519
1520     layoutStruct.fullLayout = true;
1521
1522     QFixed pageTop = currentPage * layoutStruct.pageHeight + layoutStruct.pageTopMargin - layoutStruct.frameY;
1523     layoutStruct.y = qMax(layoutStruct.y, pageTop);
1524
1525     const QList<QTextFrame *> childFrames = td->childFrameMap.values(cell.row() + cell.column() * t->rows());
1526     for (int i = 0; i < childFrames.size(); ++i) {
1527         QTextFrame *frame = childFrames.at(i);
1528         QTextFrameData *cd = data(frame);
1529         cd->sizeDirty = true;
1530     }
1531
1532     layoutFlow(cell.begin(), &layoutStruct, layoutFrom, layoutTo, width);
1533
1534     QFixed floatMinWidth;
1535
1536     // floats that are located inside the text (like inline images) aren't taken into account by
1537     // layoutFlow with regards to the cell height (layoutStruct->y), so for a safety measure we
1538     // do that here. For example with <td><img align="right" src="..." />blah</td>
1539     // when the image happens to be higher than the text
1540     for (int i = 0; i < childFrames.size(); ++i) {
1541         QTextFrame *frame = childFrames.at(i);
1542         QTextFrameData *cd = data(frame);
1543
1544         if (frame->frameFormat().position() != QTextFrameFormat::InFlow)
1545             layoutStruct.y = qMax(layoutStruct.y, cd->position.y + cd->size.height);
1546
1547         floatMinWidth = qMax(floatMinWidth, cd->minimumWidth);
1548     }
1549
1550     // constraint the maximumWidth by the minimum width of the fixed size floats, to
1551     // keep them visible
1552     layoutStruct.maximumWidth = qMax(layoutStruct.maximumWidth, floatMinWidth);
1553
1554     // as floats in cells get added to the table's float list but must not affect
1555     // floats in other cells we must clear the list here.
1556     data(t)->floats.clear();
1557
1558 //    qDebug() << "layoutCell done";
1559
1560     return layoutStruct;
1561 }
1562
1563 QRectF QTextDocumentLayoutPrivate::layoutTable(QTextTable *table, int layoutFrom, int layoutTo, QFixed parentY)
1564 {
1565     LDEBUG << "layoutTable";
1566     QTextTableData *td = static_cast<QTextTableData *>(data(table));
1567     Q_ASSERT(td->sizeDirty);
1568     const int rows = table->rows();
1569     const int columns = table->columns();
1570
1571     const QTextTableFormat fmt = table->format();
1572
1573     td->childFrameMap.clear();
1574     {
1575         const QList<QTextFrame *> children = table->childFrames();
1576         for (int i = 0; i < children.count(); ++i) {
1577             QTextFrame *frame = children.at(i);
1578             QTextTableCell cell = table->cellAt(frame->firstPosition());
1579             td->childFrameMap.insertMulti(cell.row() + cell.column() * rows, frame);
1580         }
1581     }
1582
1583     QVector<QTextLength> columnWidthConstraints = fmt.columnWidthConstraints();
1584     if (columnWidthConstraints.size() != columns)
1585         columnWidthConstraints.resize(columns);
1586     Q_ASSERT(columnWidthConstraints.count() == columns);
1587
1588     const QFixed cellSpacing = td->cellSpacing = QFixed::fromReal(scaleToDevice(fmt.cellSpacing()));
1589     td->deviceScale = scaleToDevice(qreal(1));
1590     td->cellPadding = QFixed::fromReal(scaleToDevice(fmt.cellPadding()));
1591     const QFixed leftMargin = td->leftMargin + td->border + td->padding;
1592     const QFixed rightMargin = td->rightMargin + td->border + td->padding;
1593     const QFixed topMargin = td->topMargin + td->border + td->padding;
1594
1595     const QFixed absoluteTableY = parentY + td->position.y;
1596
1597     const QTextOption::WrapMode oldDefaultWrapMode = docPrivate->defaultTextOption.wrapMode();
1598
1599 recalc_minmax_widths:
1600
1601     QFixed remainingWidth = td->contentsWidth;
1602     // two (vertical) borders per cell per column
1603     remainingWidth -= columns * 2 * td->border;
1604     // inter-cell spacing
1605     remainingWidth -= (columns - 1) * cellSpacing;
1606     // cell spacing at the left and right hand side
1607     remainingWidth -= 2 * cellSpacing;
1608     // remember the width used to distribute to percentaged columns
1609     const QFixed initialTotalWidth = remainingWidth;
1610
1611     td->widths.resize(columns);
1612     td->widths.fill(0);
1613
1614     td->minWidths.resize(columns);
1615     // start with a minimum width of 0. totally empty
1616     // cells of default created tables are invisible otherwise
1617     // and therefore hardly editable
1618     td->minWidths.fill(1);
1619
1620     td->maxWidths.resize(columns);
1621     td->maxWidths.fill(QFIXED_MAX);
1622
1623     // calculate minimum and maximum sizes of the columns
1624     for (int i = 0; i < columns; ++i) {
1625         for (int row = 0; row < rows; ++row) {
1626             const QTextTableCell cell = table->cellAt(row, i);
1627             const int cspan = cell.columnSpan();
1628
1629             if (cspan > 1 && i != cell.column())
1630                 continue;
1631
1632             const QTextFormat fmt = cell.format();
1633             const QFixed leftPadding = td->leftPadding(fmt);
1634             const QFixed rightPadding = td->rightPadding(fmt);
1635             const QFixed widthPadding = leftPadding + rightPadding;
1636
1637             // to figure out the min and the max width lay out the cell at
1638             // maximum width. otherwise the maxwidth calculation sometimes
1639             // returns wrong values
1640             QTextLayoutStruct layoutStruct = layoutCell(table, cell, QFIXED_MAX, layoutFrom,
1641                                                         layoutTo, td, absoluteTableY,
1642                                                         /*withPageBreaks =*/false);
1643
1644             // distribute the minimum width over all columns the cell spans
1645             QFixed widthToDistribute = layoutStruct.minimumWidth + widthPadding;
1646             for (int n = 0; n < cspan; ++n) {
1647                 const int col = i + n;
1648                 QFixed w = widthToDistribute / (cspan - n);
1649                 td->minWidths[col] = qMax(td->minWidths.at(col), w);
1650                 widthToDistribute -= td->minWidths.at(col);
1651                 if (widthToDistribute <= 0)
1652                     break;
1653             }
1654
1655             QFixed maxW = td->maxWidths.at(i);
1656             if (layoutStruct.maximumWidth != QFIXED_MAX) {
1657                 if (maxW == QFIXED_MAX)
1658                     maxW = layoutStruct.maximumWidth + widthPadding;
1659                 else
1660                     maxW = qMax(maxW, layoutStruct.maximumWidth + widthPadding);
1661             }
1662             if (maxW == QFIXED_MAX)
1663                 continue;
1664
1665             widthToDistribute = maxW;
1666             for (int n = 0; n < cspan; ++n) {
1667                 const int col = i + n;
1668                 QFixed w = widthToDistribute / (cspan - n);
1669                 td->maxWidths[col] = qMax(td->minWidths.at(col), w);
1670                 widthToDistribute -= td->maxWidths.at(col);
1671                 if (widthToDistribute <= 0)
1672                     break;
1673             }
1674         }
1675     }
1676
1677     // set fixed values, figure out total percentages used and number of
1678     // variable length cells. Also assign the minimum width for variable columns.
1679     QFixed totalPercentage;
1680     int variableCols = 0;
1681     QFixed totalMinWidth = 0;
1682     for (int i = 0; i < columns; ++i) {
1683         const QTextLength &length = columnWidthConstraints.at(i);
1684         if (length.type() == QTextLength::FixedLength) {
1685             td->minWidths[i] = td->widths[i] = qMax(scaleToDevice(QFixed::fromReal(length.rawValue())), td->minWidths.at(i));
1686             remainingWidth -= td->widths.at(i);
1687         } else if (length.type() == QTextLength::PercentageLength) {
1688             totalPercentage += QFixed::fromReal(length.rawValue());
1689         } else if (length.type() == QTextLength::VariableLength) {
1690             variableCols++;
1691
1692             td->widths[i] = td->minWidths.at(i);
1693             remainingWidth -= td->minWidths.at(i);
1694         }
1695         totalMinWidth += td->minWidths.at(i);
1696     }
1697
1698     // set percentage values
1699     {
1700         const QFixed totalPercentagedWidth = initialTotalWidth * totalPercentage / 100;
1701         QFixed remainingMinWidths = totalMinWidth;
1702         for (int i = 0; i < columns; ++i) {
1703             remainingMinWidths -= td->minWidths.at(i);
1704             if (columnWidthConstraints.at(i).type() == QTextLength::PercentageLength) {
1705                 const QFixed allottedPercentage = QFixed::fromReal(columnWidthConstraints.at(i).rawValue());
1706
1707                 const QFixed percentWidth = totalPercentagedWidth * allottedPercentage / totalPercentage;
1708                 if (percentWidth >= td->minWidths.at(i)) {
1709                     td->widths[i] = qBound(td->minWidths.at(i), percentWidth, remainingWidth - remainingMinWidths);
1710                 } else {
1711                     td->widths[i] = td->minWidths.at(i);
1712                 }
1713                 remainingWidth -= td->widths.at(i);
1714             }
1715         }
1716     }
1717
1718     // for variable columns distribute the remaining space
1719     if (variableCols > 0 && remainingWidth > 0) {
1720         QVarLengthArray<int> columnsWithProperMaxSize;
1721         for (int i = 0; i < columns; ++i)
1722             if (columnWidthConstraints.at(i).type() == QTextLength::VariableLength
1723                 && td->maxWidths.at(i) != QFIXED_MAX)
1724                 columnsWithProperMaxSize.append(i);
1725
1726         QFixed lastRemainingWidth = remainingWidth;
1727         while (remainingWidth > 0) {
1728             for (int k = 0; k < columnsWithProperMaxSize.count(); ++k) {
1729                 const int col = columnsWithProperMaxSize[k];
1730                 const int colsLeft = columnsWithProperMaxSize.count() - k;
1731                 const QFixed w = qMin(td->maxWidths.at(col) - td->widths.at(col), remainingWidth / colsLeft);
1732                 td->widths[col] += w;
1733                 remainingWidth -= w;
1734             }
1735             if (remainingWidth == lastRemainingWidth)
1736                 break;
1737             lastRemainingWidth = remainingWidth;
1738         }
1739
1740         if (remainingWidth > 0
1741             // don't unnecessarily grow variable length sized tables
1742             && fmt.width().type() != QTextLength::VariableLength) {
1743             const QFixed widthPerAnySizedCol = remainingWidth / variableCols;
1744             for (int col = 0; col < columns; ++col) {
1745                 if (columnWidthConstraints.at(col).type() == QTextLength::VariableLength)
1746                     td->widths[col] += widthPerAnySizedCol;
1747             }
1748         }
1749     }
1750
1751     td->columnPositions.resize(columns);
1752     td->columnPositions[0] = leftMargin /*includes table border*/ + cellSpacing + td->border;
1753
1754     for (int i = 1; i < columns; ++i)
1755         td->columnPositions[i] = td->columnPositions.at(i-1) + td->widths.at(i-1) + 2 * td->border + cellSpacing;
1756
1757     // - margin to compensate the + margin in columnPositions[0]
1758     const QFixed contentsWidth = td->columnPositions.last() + td->widths.last() + td->padding + td->border + cellSpacing - leftMargin;
1759
1760     // if the table is too big and causes an overflow re-do the layout with WrapAnywhere as wrap
1761     // mode
1762     if (docPrivate->defaultTextOption.wrapMode() == QTextOption::WrapAtWordBoundaryOrAnywhere
1763         && contentsWidth > td->contentsWidth) {
1764         docPrivate->defaultTextOption.setWrapMode(QTextOption::WrapAnywhere);
1765         // go back to the top of the function
1766         goto recalc_minmax_widths;
1767     }
1768
1769     td->contentsWidth = contentsWidth;
1770
1771     docPrivate->defaultTextOption.setWrapMode(oldDefaultWrapMode);
1772
1773     td->heights.resize(rows);
1774     td->heights.fill(0);
1775
1776     td->rowPositions.resize(rows);
1777     td->rowPositions[0] = topMargin /*includes table border*/ + cellSpacing + td->border;
1778
1779     bool haveRowSpannedCells = false;
1780
1781     // need to keep track of cell heights for vertical alignment
1782     QVector<QFixed> cellHeights;
1783     cellHeights.reserve(rows * columns);
1784
1785     QFixed pageHeight = QFixed::fromReal(document->pageSize().height());
1786     if (pageHeight <= 0)
1787         pageHeight = QFIXED_MAX;
1788
1789     QVector<QFixed> heightToDistribute;
1790     heightToDistribute.resize(columns);
1791
1792     td->headerHeight = 0;
1793     const int headerRowCount = qMin(table->format().headerRowCount(), rows - 1);
1794     const QFixed originalTopMargin = td->effectiveTopMargin;
1795     bool hasDroppedTable = false;
1796
1797     // now that we have the column widths we can lay out all cells with the right width.
1798     // spanning cells are only allowed to grow the last row spanned by the cell.
1799     //
1800     // ### this could be made faster by iterating over the cells array of QTextTable
1801     for (int r = 0; r < rows; ++r) {
1802         td->calcRowPosition(r);
1803
1804         const int tableStartPage = (absoluteTableY / pageHeight).truncate();
1805         const int currentPage = ((td->rowPositions[r] + absoluteTableY) / pageHeight).truncate();
1806         const QFixed pageBottom = (currentPage + 1) * pageHeight - td->effectiveBottomMargin - absoluteTableY - cellSpacing - td->border;
1807         const QFixed pageTop = currentPage * pageHeight + td->effectiveTopMargin - absoluteTableY + cellSpacing + td->border;
1808         const QFixed nextPageTop = pageTop + pageHeight;
1809
1810         if (td->rowPositions[r] > pageBottom)
1811             td->rowPositions[r] = nextPageTop;
1812         else if (td->rowPositions[r] < pageTop)
1813             td->rowPositions[r] = pageTop;
1814
1815         bool dropRowToNextPage = true;
1816         int cellCountBeforeRow = cellHeights.size();
1817
1818         // if we drop the row to the next page we need to subtract the drop
1819         // distance from any row spanning cells
1820         QFixed dropDistance = 0;
1821
1822 relayout:
1823         const int rowStartPage = ((td->rowPositions[r] + absoluteTableY) / pageHeight).truncate();
1824         // if any of the header rows or the first non-header row start on the next page
1825         // then the entire header should be dropped
1826         if (r <= headerRowCount && rowStartPage > tableStartPage && !hasDroppedTable) {
1827             td->rowPositions[0] = nextPageTop;
1828             cellHeights.clear();
1829             td->effectiveTopMargin = originalTopMargin;
1830             hasDroppedTable = true;
1831             r = -1;
1832             continue;
1833         }
1834
1835         int rowCellCount = 0;
1836         for (int c = 0; c < columns; ++c) {
1837             QTextTableCell cell = table->cellAt(r, c);
1838             const int rspan = cell.rowSpan();
1839             const int cspan = cell.columnSpan();
1840
1841             if (cspan > 1 && cell.column() != c)
1842                 continue;
1843
1844             if (rspan > 1) {
1845                 haveRowSpannedCells = true;
1846
1847                 const int cellRow = cell.row();
1848                 if (cellRow != r) {
1849                     // the last row gets all the remaining space
1850                     if (cellRow + rspan - 1 == r)
1851                         td->heights[r] = qMax(td->heights.at(r), heightToDistribute.at(c) - dropDistance);
1852                     continue;
1853                 }
1854             }
1855
1856             const QTextFormat fmt = cell.format();
1857
1858             const QFixed topPadding = td->topPadding(fmt);
1859             const QFixed bottomPadding = td->bottomPadding(fmt);
1860             const QFixed leftPadding = td->leftPadding(fmt);
1861             const QFixed rightPadding = td->rightPadding(fmt);
1862             const QFixed widthPadding = leftPadding + rightPadding;
1863
1864             ++rowCellCount;
1865
1866             const QFixed width = td->cellWidth(c, cspan) - widthPadding;
1867             QTextLayoutStruct layoutStruct = layoutCell(table, cell, width,
1868                                                        layoutFrom, layoutTo,
1869                                                        td, absoluteTableY,
1870                                                        /*withPageBreaks =*/true);
1871
1872             const QFixed height = layoutStruct.y + bottomPadding + topPadding;
1873
1874             if (rspan > 1)
1875                 heightToDistribute[c] = height + dropDistance;
1876             else
1877                 td->heights[r] = qMax(td->heights.at(r), height);
1878
1879             cellHeights.append(layoutStruct.y);
1880
1881             QFixed childPos = td->rowPositions.at(r) + topPadding + flowPosition(cell.begin());
1882             if (childPos < pageBottom)
1883                 dropRowToNextPage = false;
1884         }
1885
1886         if (rowCellCount > 0 && dropRowToNextPage) {
1887             dropDistance = nextPageTop - td->rowPositions[r];
1888             td->rowPositions[r] = nextPageTop;
1889             td->heights[r] = 0;
1890             dropRowToNextPage = false;
1891             cellHeights.resize(cellCountBeforeRow);
1892             if (r > headerRowCount)
1893                 td->heights[r-1] = pageBottom - td->rowPositions[r-1];
1894             goto relayout;
1895         }
1896
1897         if (haveRowSpannedCells) {
1898             const QFixed effectiveHeight = td->heights.at(r) + td->border + cellSpacing + td->border;
1899             for (int c = 0; c < columns; ++c)
1900                 heightToDistribute[c] = qMax(heightToDistribute.at(c) - effectiveHeight - dropDistance, QFixed(0));
1901         }
1902
1903         if (r == headerRowCount - 1) {
1904             td->headerHeight = td->rowPositions[r] + td->heights[r] - td->rowPositions[0] + td->cellSpacing + 2 * td->border;
1905             td->headerHeight -= td->headerHeight * (td->headerHeight / pageHeight).truncate();
1906             td->effectiveTopMargin += td->headerHeight;
1907         }
1908     }
1909
1910     td->effectiveTopMargin = originalTopMargin;
1911
1912     // now that all cells have been properly laid out, we can compute the
1913     // vertical offsets for vertical alignment
1914     td->cellVerticalOffsets.resize(rows * columns);
1915     int cellIndex = 0;
1916     for (int r = 0; r < rows; ++r) {
1917         for (int c = 0; c < columns; ++c) {
1918             QTextTableCell cell = table->cellAt(r, c);
1919             if (cell.row() != r || cell.column() != c)
1920                 continue;
1921
1922             const int rowSpan = cell.rowSpan();
1923             const QFixed availableHeight = td->rowPositions.at(r + rowSpan - 1) + td->heights.at(r + rowSpan - 1) - td->rowPositions.at(r);
1924
1925             const QTextCharFormat cellFormat = cell.format();
1926             const QFixed cellHeight = cellHeights.at(cellIndex++) + td->topPadding(cellFormat) + td->bottomPadding(cellFormat);
1927
1928             QFixed offset = 0;
1929             switch (cellFormat.verticalAlignment()) {
1930             case QTextCharFormat::AlignMiddle:
1931                 offset = (availableHeight - cellHeight) / 2;
1932                 break;
1933             case QTextCharFormat::AlignBottom:
1934                 offset = availableHeight - cellHeight;
1935                 break;
1936             default:
1937                 break;
1938             };
1939
1940             for (int rd = 0; rd < cell.rowSpan(); ++rd) {
1941                 for (int cd = 0; cd < cell.columnSpan(); ++cd) {
1942                     const int index = (c + cd) + (r + rd) * columns;
1943                     td->cellVerticalOffsets[index] = offset;
1944                 }
1945             }
1946         }
1947     }
1948
1949     td->minimumWidth = td->columnPositions.at(0);
1950     for (int i = 0; i < columns; ++i) {
1951         td->minimumWidth += td->minWidths.at(i) + 2 * td->border + cellSpacing;
1952     }
1953     td->minimumWidth += rightMargin - td->border;
1954
1955     td->maximumWidth = td->columnPositions.at(0);
1956     for (int i = 0; i < columns; ++i)
1957         if (td->maxWidths.at(i) != QFIXED_MAX)
1958             td->maximumWidth += td->maxWidths.at(i) + 2 * td->border + cellSpacing;
1959     td->maximumWidth += rightMargin - td->border;
1960
1961     td->updateTableSize();
1962     td->sizeDirty = false;
1963     return QRectF(); // invalid rect -> update everything
1964 }
1965
1966 void QTextDocumentLayoutPrivate::positionFloat(QTextFrame *frame, QTextLine *currentLine)
1967 {
1968     QTextFrameData *fd = data(frame);
1969
1970     QTextFrame *parent = frame->parentFrame();
1971     Q_ASSERT(parent);
1972     QTextFrameData *pd = data(parent);
1973     Q_ASSERT(pd && pd->currentLayoutStruct);
1974
1975     QTextLayoutStruct *layoutStruct = pd->currentLayoutStruct;
1976
1977     if (!pd->floats.contains(frame))
1978         pd->floats.append(frame);
1979     fd->layoutDirty = true;
1980     Q_ASSERT(!fd->sizeDirty);
1981
1982 //     qDebug() << "positionFloat:" << frame << "width=" << fd->size.width;
1983     QFixed y = layoutStruct->y;
1984     if (currentLine) {
1985         QFixed left, right;
1986         floatMargins(y, layoutStruct, &left, &right);
1987 //         qDebug() << "have line: right=" << right << "left=" << left << "textWidth=" << currentLine->width();
1988         if (right - left < QFixed::fromReal(currentLine->naturalTextWidth()) + fd->size.width) {
1989             layoutStruct->pendingFloats.append(frame);
1990 //             qDebug() << "    adding to pending list";
1991             return;
1992         }
1993     }
1994
1995     bool frameSpansIntoNextPage = (y + layoutStruct->frameY + fd->size.height > layoutStruct->pageBottom);
1996     if (frameSpansIntoNextPage && fd->size.height <= layoutStruct->pageHeight) {
1997         layoutStruct->newPage();
1998         y = layoutStruct->y;
1999
2000         frameSpansIntoNextPage = false;
2001     }
2002
2003     y = findY(y, layoutStruct, fd->size.width);
2004
2005     QFixed left, right;
2006     floatMargins(y, layoutStruct, &left, &right);
2007
2008     if (frame->frameFormat().position() == QTextFrameFormat::FloatLeft) {
2009         fd->position.x = left;
2010         fd->position.y = y;
2011     } else {
2012         fd->position.x = right - fd->size.width;
2013         fd->position.y = y;
2014     }
2015
2016     layoutStruct->minimumWidth = qMax(layoutStruct->minimumWidth, fd->minimumWidth);
2017     layoutStruct->maximumWidth = qMin(layoutStruct->maximumWidth, fd->maximumWidth);
2018
2019 //     qDebug()<< "float positioned at " << fd->position.x << fd->position.y;
2020     fd->layoutDirty = false;
2021
2022     // If the frame is a table, then positioning it will affect the size if it covers more than
2023     // one page, because of page breaks and repeating the header.
2024     if (qobject_cast<QTextTable *>(frame) != 0)
2025         fd->sizeDirty = frameSpansIntoNextPage;
2026 }
2027
2028 QRectF QTextDocumentLayoutPrivate::layoutFrame(QTextFrame *f, int layoutFrom, int layoutTo, QFixed parentY)
2029 {
2030     LDEBUG << "layoutFrame (pre)";
2031     Q_ASSERT(data(f)->sizeDirty);
2032 //     qDebug("layouting frame (%d--%d), parent=%p", f->firstPosition(), f->lastPosition(), f->parentFrame());
2033
2034     QTextFrameFormat fformat = f->frameFormat();
2035
2036     QTextFrame *parent = f->parentFrame();
2037     const QTextFrameData *pd = parent ? data(parent) : 0;
2038
2039     const qreal maximumWidth = qMax(qreal(0), pd ? pd->contentsWidth.toReal() : document->pageSize().width());
2040     QFixed width = QFixed::fromReal(fformat.width().value(maximumWidth));
2041     if (fformat.width().type() == QTextLength::FixedLength)
2042         width = scaleToDevice(width);
2043
2044     const QFixed maximumHeight = pd ? pd->contentsHeight : -1;
2045     const QFixed height = (maximumHeight != -1 || fformat.height().type() != QTextLength::PercentageLength)
2046                             ? QFixed::fromReal(fformat.height().value(maximumHeight.toReal()))
2047                             : -1;
2048
2049     return layoutFrame(f, layoutFrom, layoutTo, width, height, parentY);
2050 }
2051
2052 QRectF QTextDocumentLayoutPrivate::layoutFrame(QTextFrame *f, int layoutFrom, int layoutTo, QFixed frameWidth, QFixed frameHeight, QFixed parentY)
2053 {
2054     LDEBUG << "layoutFrame from=" << layoutFrom << "to=" << layoutTo;
2055     Q_ASSERT(data(f)->sizeDirty);
2056 //     qDebug("layouting frame (%d--%d), parent=%p", f->firstPosition(), f->lastPosition(), f->parentFrame());
2057
2058     QTextFrameData *fd = data(f);
2059     QFixed newContentsWidth;
2060
2061     {
2062         QTextFrameFormat fformat = f->frameFormat();
2063         // set sizes of this frame from the format
2064         fd->topMargin = QFixed::fromReal(fformat.topMargin());
2065         fd->bottomMargin = QFixed::fromReal(fformat.bottomMargin());
2066         fd->leftMargin = QFixed::fromReal(fformat.leftMargin());
2067         fd->rightMargin = QFixed::fromReal(fformat.rightMargin());
2068         fd->border = QFixed::fromReal(fformat.border());
2069         fd->padding = QFixed::fromReal(fformat.padding());
2070
2071         QTextFrame *parent = f->parentFrame();
2072         const QTextFrameData *pd = parent ? data(parent) : 0;
2073
2074         // accumulate top and bottom margins
2075         if (parent) {
2076             fd->effectiveTopMargin = pd->effectiveTopMargin + fd->topMargin + fd->border + fd->padding;
2077             fd->effectiveBottomMargin = pd->effectiveBottomMargin + fd->topMargin + fd->border + fd->padding;
2078
2079             if (qobject_cast<QTextTable *>(parent)) {
2080                 const QTextTableData *td = static_cast<const QTextTableData *>(pd);
2081                 fd->effectiveTopMargin += td->cellSpacing + td->border + td->cellPadding;
2082                 fd->effectiveBottomMargin += td->cellSpacing + td->border + td->cellPadding;
2083             }
2084         } else {
2085             fd->effectiveTopMargin = fd->topMargin + fd->border + fd->padding;
2086             fd->effectiveBottomMargin = fd->bottomMargin + fd->border + fd->padding;
2087         }
2088
2089         newContentsWidth = frameWidth - 2*(fd->border + fd->padding)
2090                            - fd->leftMargin - fd->rightMargin;
2091
2092         if (frameHeight != -1) {
2093             fd->contentsHeight = frameHeight - 2*(fd->border + fd->padding)
2094                                  - fd->topMargin - fd->bottomMargin;
2095         } else {
2096             fd->contentsHeight = frameHeight;
2097         }
2098     }
2099
2100     if (isFrameFromInlineObject(f)) {
2101         // never reached, handled in resizeInlineObject/positionFloat instead
2102         return QRectF();
2103     }
2104
2105     if (QTextTable *table = qobject_cast<QTextTable *>(f)) {
2106         fd->contentsWidth = newContentsWidth;
2107         return layoutTable(table, layoutFrom, layoutTo, parentY);
2108     }
2109
2110     // set fd->contentsWidth temporarily, so that layoutFrame for the children
2111     // picks the right width. We'll initialize it properly at the end of this
2112     // function.
2113     fd->contentsWidth = newContentsWidth;
2114
2115     QTextLayoutStruct layoutStruct;
2116     layoutStruct.frame = f;
2117     layoutStruct.x_left = fd->leftMargin + fd->border + fd->padding;
2118     layoutStruct.x_right = layoutStruct.x_left + newContentsWidth;
2119     layoutStruct.y = fd->topMargin + fd->border + fd->padding;
2120     layoutStruct.frameY = parentY + fd->position.y;
2121     layoutStruct.contentsWidth = 0;
2122     layoutStruct.minimumWidth = 0;
2123     layoutStruct.maximumWidth = QFIXED_MAX;
2124     layoutStruct.fullLayout = fd->oldContentsWidth != newContentsWidth;
2125     layoutStruct.updateRect = QRectF(QPointF(0, 0), QSizeF(qreal(INT_MAX), qreal(INT_MAX)));
2126     LDEBUG << "layoutStruct: x_left" << layoutStruct.x_left << "x_right" << layoutStruct.x_right
2127            << "fullLayout" << layoutStruct.fullLayout;
2128     fd->oldContentsWidth = newContentsWidth;
2129
2130     layoutStruct.pageHeight = QFixed::fromReal(document->pageSize().height());
2131     if (layoutStruct.pageHeight < 0)
2132         layoutStruct.pageHeight = QFIXED_MAX;
2133
2134     const int currentPage = layoutStruct.pageHeight == 0 ? 0 : (layoutStruct.frameY / layoutStruct.pageHeight).truncate();
2135     layoutStruct.pageTopMargin = fd->effectiveTopMargin;
2136     layoutStruct.pageBottomMargin = fd->effectiveBottomMargin;
2137     layoutStruct.pageBottom = (currentPage + 1) * layoutStruct.pageHeight - layoutStruct.pageBottomMargin;
2138
2139     if (!f->parentFrame())
2140         idealWidth = 0; // reset
2141
2142     QTextFrame::Iterator it = f->begin();
2143     layoutFlow(it, &layoutStruct, layoutFrom, layoutTo);
2144
2145     QFixed maxChildFrameWidth = 0;
2146     QList<QTextFrame *> children = f->childFrames();
2147     for (int i = 0; i < children.size(); ++i) {
2148         QTextFrame *c = children.at(i);
2149         QTextFrameData *cd = data(c);
2150         maxChildFrameWidth = qMax(maxChildFrameWidth, cd->size.width);
2151     }
2152
2153     const QFixed marginWidth = 2*(fd->border + fd->padding) + fd->leftMargin + fd->rightMargin;
2154     if (!f->parentFrame()) {
2155         idealWidth = qMax(maxChildFrameWidth, layoutStruct.contentsWidth).toReal();
2156         idealWidth += marginWidth.toReal();
2157     }
2158
2159     QFixed actualWidth = qMax(newContentsWidth, qMax(maxChildFrameWidth, layoutStruct.contentsWidth));
2160     fd->contentsWidth = actualWidth;
2161     if (newContentsWidth <= 0) { // nowrap layout?
2162         fd->contentsWidth = newContentsWidth;
2163     }
2164
2165     fd->minimumWidth = layoutStruct.minimumWidth;
2166     fd->maximumWidth = layoutStruct.maximumWidth;
2167
2168     fd->size.height = fd->contentsHeight == -1
2169                  ? layoutStruct.y + fd->border + fd->padding + fd->bottomMargin
2170                  : fd->contentsHeight + 2*(fd->border + fd->padding) + fd->topMargin + fd->bottomMargin;
2171     fd->size.width = actualWidth + marginWidth;
2172     fd->sizeDirty = false;
2173     if (layoutStruct.updateRectForFloats.isValid())
2174         layoutStruct.updateRect |= layoutStruct.updateRectForFloats;
2175     return layoutStruct.updateRect;
2176 }
2177
2178 void QTextDocumentLayoutPrivate::layoutFlow(QTextFrame::Iterator it, QTextLayoutStruct *layoutStruct,
2179                                             int layoutFrom, int layoutTo, QFixed width)
2180 {
2181     LDEBUG << "layoutFlow from=" << layoutFrom << "to=" << layoutTo;
2182     QTextFrameData *fd = data(layoutStruct->frame);
2183
2184     fd->currentLayoutStruct = layoutStruct;
2185
2186     QTextFrame::Iterator previousIt;
2187
2188     const bool inRootFrame = (it.parentFrame() == document->rootFrame());
2189     if (inRootFrame) {
2190         bool redoCheckPoints = layoutStruct->fullLayout || checkPoints.isEmpty();
2191
2192         if (!redoCheckPoints) {
2193             QVector<QCheckPoint>::Iterator checkPoint = qLowerBound(checkPoints.begin(), checkPoints.end(), layoutFrom);
2194             if (checkPoint != checkPoints.end()) {
2195                 if (checkPoint != checkPoints.begin())
2196                     --checkPoint;
2197
2198                 layoutStruct->y = checkPoint->y;
2199                 layoutStruct->frameY = checkPoint->frameY;
2200                 layoutStruct->minimumWidth = checkPoint->minimumWidth;
2201                 layoutStruct->maximumWidth = checkPoint->maximumWidth;
2202                 layoutStruct->contentsWidth = checkPoint->contentsWidth;
2203
2204                 if (layoutStruct->pageHeight > 0) {
2205                     int page = layoutStruct->currentPage();
2206                     layoutStruct->pageBottom = (page + 1) * layoutStruct->pageHeight - layoutStruct->pageBottomMargin;
2207                 }
2208
2209                 it = frameIteratorForTextPosition(checkPoint->positionInFrame);
2210                 checkPoints.resize(checkPoint - checkPoints.begin() + 1);
2211
2212                 if (checkPoint != checkPoints.begin()) {
2213                     previousIt = it;
2214                     --previousIt;
2215                 }
2216             } else {
2217                 redoCheckPoints = true;
2218             }
2219         }
2220
2221         if (redoCheckPoints) {
2222             checkPoints.clear();
2223             QCheckPoint cp;
2224             cp.y = layoutStruct->y;
2225             cp.frameY = layoutStruct->frameY;
2226             cp.positionInFrame = 0;
2227             cp.minimumWidth = layoutStruct->minimumWidth;
2228             cp.maximumWidth = layoutStruct->maximumWidth;
2229             cp.contentsWidth = layoutStruct->contentsWidth;
2230             checkPoints.append(cp);
2231         }
2232     }
2233
2234     QTextBlockFormat previousBlockFormat = previousIt.currentBlock().blockFormat();
2235
2236     QFixed maximumBlockWidth = 0;
2237     while (!it.atEnd()) {
2238         QTextFrame *c = it.currentFrame();
2239
2240         int docPos;
2241         if (it.currentFrame())
2242             docPos = it.currentFrame()->firstPosition();
2243         else
2244             docPos = it.currentBlock().position();
2245
2246         if (inRootFrame) {
2247             if (qAbs(layoutStruct->y - checkPoints.last().y) > 2000) {
2248                 QFixed left, right;
2249                 floatMargins(layoutStruct->y, layoutStruct, &left, &right);
2250                 if (left == layoutStruct->x_left && right == layoutStruct->x_right) {
2251                     QCheckPoint p;
2252                     p.y = layoutStruct->y;
2253                     p.frameY = layoutStruct->frameY;
2254                     p.positionInFrame = docPos;
2255                     p.minimumWidth = layoutStruct->minimumWidth;
2256                     p.maximumWidth = layoutStruct->maximumWidth;
2257                     p.contentsWidth = layoutStruct->contentsWidth;
2258                     checkPoints.append(p);
2259
2260                     if (currentLazyLayoutPosition != -1
2261                         && docPos > currentLazyLayoutPosition + lazyLayoutStepSize)
2262                         break;
2263
2264                 }
2265             }
2266         }
2267
2268         if (c) {
2269             // position child frame
2270             QTextFrameData *cd = data(c);
2271
2272             QTextFrameFormat fformat = c->frameFormat();
2273
2274             if (fformat.position() == QTextFrameFormat::InFlow) {
2275                 if (fformat.pageBreakPolicy() & QTextFormat::PageBreak_AlwaysBefore)
2276                     layoutStruct->newPage();
2277
2278                 QFixed left, right;
2279                 floatMargins(layoutStruct->y, layoutStruct, &left, &right);
2280                 left = qMax(left, layoutStruct->x_left);
2281                 right = qMin(right, layoutStruct->x_right);
2282
2283                 if (right - left < cd->size.width) {
2284                     layoutStruct->y = findY(layoutStruct->y, layoutStruct, cd->size.width);
2285                     floatMargins(layoutStruct->y, layoutStruct, &left, &right);
2286                 }
2287
2288                 QFixedPoint pos(left, layoutStruct->y);
2289
2290                 Qt::Alignment align = Qt::AlignLeft;
2291
2292                 QTextTable *table = qobject_cast<QTextTable *>(c);
2293
2294                 if (table)
2295                     align = table->format().alignment() & Qt::AlignHorizontal_Mask;
2296
2297                 // detect whether we have any alignment in the document that disallows optimizations,
2298                 // such as not laying out the document again in a textedit with wrapping disabled.
2299                 if (inRootFrame && !(align & Qt::AlignLeft))
2300                     contentHasAlignment = true;
2301
2302                 cd->position = pos;
2303
2304                 if (document->pageSize().height() > 0.0f)
2305                     cd->sizeDirty = true;
2306
2307                 if (cd->sizeDirty) {
2308                     if (width != 0)
2309                         layoutFrame(c, layoutFrom, layoutTo, width, -1, layoutStruct->frameY);
2310                     else
2311                         layoutFrame(c, layoutFrom, layoutTo, layoutStruct->frameY);
2312
2313                     QFixed absoluteChildPos = table ? pos.y + static_cast<QTextTableData *>(data(table))->rowPositions.at(0) : pos.y + firstChildPos(c);
2314                     absoluteChildPos += layoutStruct->frameY;
2315
2316                     // drop entire frame to next page if first child of frame is on next page
2317                     if (absoluteChildPos > layoutStruct->pageBottom) {
2318                         layoutStruct->newPage();
2319                         pos.y = layoutStruct->y;
2320
2321                         cd->position = pos;
2322                         cd->sizeDirty = true;
2323
2324                         if (width != 0)
2325                             layoutFrame(c, layoutFrom, layoutTo, width, -1, layoutStruct->frameY);
2326                         else
2327                             layoutFrame(c, layoutFrom, layoutTo, layoutStruct->frameY);
2328                     }
2329                 }
2330
2331                 // align only if there is space for alignment
2332                 if (right - left > cd->size.width) {
2333                     if (align & Qt::AlignRight)
2334                         pos.x += layoutStruct->x_right - cd->size.width;
2335                     else if (align & Qt::AlignHCenter)
2336                         pos.x += (layoutStruct->x_right - cd->size.width) / 2;
2337                 }
2338
2339                 cd->position = pos;
2340
2341                 layoutStruct->y += cd->size.height;
2342                 const int page = layoutStruct->currentPage();
2343                 layoutStruct->pageBottom = (page + 1) * layoutStruct->pageHeight - layoutStruct->pageBottomMargin;
2344
2345                 cd->layoutDirty = false;
2346
2347                 if (c->frameFormat().pageBreakPolicy() & QTextFormat::PageBreak_AlwaysAfter)
2348                     layoutStruct->newPage();
2349             } else {
2350                 QRectF oldFrameRect(cd->position.toPointF(), cd->size.toSizeF());
2351                 QRectF updateRect;
2352
2353                 if (cd->sizeDirty)
2354                     updateRect = layoutFrame(c, layoutFrom, layoutTo);
2355
2356                 positionFloat(c);
2357
2358                 // If the size was made dirty when the position was set, layout again
2359                 if (cd->sizeDirty)
2360                     updateRect = layoutFrame(c, layoutFrom, layoutTo);
2361
2362                 QRectF frameRect(cd->position.toPointF(), cd->size.toSizeF());
2363
2364                 if (frameRect == oldFrameRect && updateRect.isValid())
2365                     updateRect.translate(cd->position.toPointF());
2366                 else
2367                     updateRect = frameRect;
2368
2369                 layoutStruct->addUpdateRectForFloat(updateRect);
2370                 if (oldFrameRect.isValid())
2371                     layoutStruct->addUpdateRectForFloat(oldFrameRect);
2372             }
2373
2374             layoutStruct->minimumWidth = qMax(layoutStruct->minimumWidth, cd->minimumWidth);
2375             layoutStruct->maximumWidth = qMin(layoutStruct->maximumWidth, cd->maximumWidth);
2376
2377             previousIt = it;
2378             ++it;
2379         } else {
2380             QTextFrame::Iterator lastIt;
2381             if (!previousIt.atEnd())
2382                 lastIt = previousIt;
2383             previousIt = it;
2384             QTextBlock block = it.currentBlock();
2385             ++it;
2386
2387             const QTextBlockFormat blockFormat = block.blockFormat();
2388
2389             if (blockFormat.pageBreakPolicy() & QTextFormat::PageBreak_AlwaysBefore)
2390                 layoutStruct->newPage();
2391
2392             const QFixed origY = layoutStruct->y;
2393             const QFixed origPageBottom = layoutStruct->pageBottom;
2394             const QFixed origMaximumWidth = layoutStruct->maximumWidth;
2395             layoutStruct->maximumWidth = 0;
2396
2397             const QTextBlockFormat *previousBlockFormatPtr = 0;
2398             if (lastIt.currentBlock().isValid())
2399                 previousBlockFormatPtr = &previousBlockFormat;
2400
2401             // layout and position child block
2402             layoutBlock(block, docPos, blockFormat, layoutStruct, layoutFrom, layoutTo, previousBlockFormatPtr);
2403
2404             // detect whether we have any alignment in the document that disallows optimizations,
2405             // such as not laying out the document again in a textedit with wrapping disabled.
2406             if (inRootFrame && !(block.layout()->textOption().alignment() & Qt::AlignLeft))
2407                 contentHasAlignment = true;
2408
2409             // if the block right before a table is empty 'hide' it by
2410             // positioning it into the table border
2411             if (isEmptyBlockBeforeTable(block, blockFormat, it)) {
2412                 const QTextBlock lastBlock = lastIt.currentBlock();
2413                 const qreal lastBlockBottomMargin = lastBlock.isValid() ? lastBlock.blockFormat().bottomMargin() : 0.0f;
2414                 layoutStruct->y = origY + QFixed::fromReal(qMax(lastBlockBottomMargin, block.blockFormat().topMargin()));
2415                 layoutStruct->pageBottom = origPageBottom;
2416             } else {
2417                 // if the block right after a table is empty then 'hide' it, too
2418                 if (isEmptyBlockAfterTable(block, lastIt.currentFrame())) {
2419                     QTextTableData *td = static_cast<QTextTableData *>(data(lastIt.currentFrame()));
2420                     QTextLayout *layout = block.layout();
2421
2422                     QPointF pos((td->position.x + td->size.width).toReal(),
2423                                 (td->position.y + td->size.height).toReal() - layout->boundingRect().height());
2424
2425                     layout->setPosition(pos);
2426                     layoutStruct->y = origY;
2427                     layoutStruct->pageBottom = origPageBottom;
2428                 }
2429
2430                 // if the block right after a table starts with a line separator, shift it up by one line
2431                 if (isLineSeparatorBlockAfterTable(block, lastIt.currentFrame())) {
2432                     QTextTableData *td = static_cast<QTextTableData *>(data(lastIt.currentFrame()));
2433                     QTextLayout *layout = block.layout();
2434
2435                     QFixed height = QFixed::fromReal(layout->lineAt(0).height());
2436
2437                     if (layoutStruct->pageBottom == origPageBottom) {
2438                         layoutStruct->y -= height;
2439                         layout->setPosition(layout->position() - QPointF(0, height.toReal()));
2440                     } else {
2441                         // relayout block to correctly handle page breaks
2442                         layoutStruct->y = origY - height;
2443                         layoutStruct->pageBottom = origPageBottom;
2444                         layoutBlock(block, docPos, blockFormat, layoutStruct, layoutFrom, layoutTo, previousBlockFormatPtr);
2445                     }
2446
2447                     QPointF linePos((td->position.x + td->size.width).toReal(),
2448                                     (td->position.y + td->size.height - height).toReal());
2449
2450                     layout->lineAt(0).setPosition(linePos - layout->position());
2451                 }
2452
2453                 if (blockFormat.pageBreakPolicy() & QTextFormat::PageBreak_AlwaysAfter)
2454                     layoutStruct->newPage();
2455             }
2456
2457             maximumBlockWidth = qMax(maximumBlockWidth, layoutStruct->maximumWidth);
2458             layoutStruct->maximumWidth = origMaximumWidth;
2459             previousBlockFormat = blockFormat;
2460         }
2461     }
2462     if (layoutStruct->maximumWidth == QFIXED_MAX && maximumBlockWidth > 0)
2463         layoutStruct->maximumWidth = maximumBlockWidth;
2464     else
2465         layoutStruct->maximumWidth = qMax(layoutStruct->maximumWidth, maximumBlockWidth);
2466
2467     // a float at the bottom of a frame may make it taller, hence the qMax() for layoutStruct->y.
2468     // we don't need to do it for tables though because floats in tables are per table
2469     // and not per cell and layoutCell already takes care of doing the same as we do here
2470     if (!qobject_cast<QTextTable *>(layoutStruct->frame)) {
2471         QList<QTextFrame *> children = layoutStruct->frame->childFrames();
2472         for (int i = 0; i < children.count(); ++i) {
2473             QTextFrameData *fd = data(children.at(i));
2474             if (!fd->layoutDirty && children.at(i)->frameFormat().position() != QTextFrameFormat::InFlow)
2475                 layoutStruct->y = qMax(layoutStruct->y, fd->position.y + fd->size.height);
2476         }
2477     }
2478
2479     if (inRootFrame) {
2480         // we assume that any float is aligned in a way that disallows the optimizations that rely
2481         // on unaligned content.
2482         if (!fd->floats.isEmpty())
2483             contentHasAlignment = true;
2484
2485         if (it.atEnd()) {
2486             //qDebug() << "layout done!";
2487             currentLazyLayoutPosition = -1;
2488             QCheckPoint cp;
2489             cp.y = layoutStruct->y;
2490             cp.positionInFrame = docPrivate->length();
2491             cp.minimumWidth = layoutStruct->minimumWidth;
2492             cp.maximumWidth = layoutStruct->maximumWidth;
2493             cp.contentsWidth = layoutStruct->contentsWidth;
2494             checkPoints.append(cp);
2495             checkPoints.reserve(checkPoints.size());
2496         } else {
2497             currentLazyLayoutPosition = checkPoints.last().positionInFrame;
2498             // #######
2499             //checkPoints.last().positionInFrame = q->document()->docHandle()->length();
2500         }
2501     }
2502
2503
2504     fd->currentLayoutStruct = 0;
2505 }
2506
2507 static inline void getLineHeightParams(const QTextBlockFormat &blockFormat, const QTextLine &line, qreal scaling,
2508                                        QFixed *lineAdjustment, QFixed *lineBreakHeight, QFixed *lineHeight)
2509 {
2510     *lineHeight = QFixed::fromReal(blockFormat.lineHeight(line.height(), scaling));
2511
2512     if (blockFormat.lineHeightType() == QTextBlockFormat::FixedHeight || blockFormat.lineHeightType() == QTextBlockFormat::MinimumHeight) {
2513         *lineBreakHeight = *lineHeight;
2514         if (blockFormat.lineHeightType() == QTextBlockFormat::FixedHeight)
2515             *lineAdjustment = QFixed::fromReal(line.ascent() + qMax(line.leading(), qreal(0.0))) - ((*lineHeight * 4) / 5);
2516         else
2517             *lineAdjustment = QFixed::fromReal(line.height()) - *lineHeight;
2518     }
2519     else {
2520         *lineBreakHeight = QFixed::fromReal(line.height());
2521         *lineAdjustment = 0;
2522     }
2523 }
2524
2525 void QTextDocumentLayoutPrivate::layoutBlock(const QTextBlock &bl, int blockPosition, const QTextBlockFormat &blockFormat,
2526                                              QTextLayoutStruct *layoutStruct, int layoutFrom, int layoutTo, const QTextBlockFormat *previousBlockFormat)
2527 {
2528     Q_Q(QTextDocumentLayout);
2529
2530     QTextLayout *tl = bl.layout();
2531     const int blockLength = bl.length();
2532
2533     LDEBUG << "layoutBlock from=" << layoutFrom << "to=" << layoutTo;
2534
2535 //    qDebug() << "layoutBlock; width" << layoutStruct->x_right - layoutStruct->x_left << "(maxWidth is btw" << tl->maximumWidth() << ')';
2536
2537     if (previousBlockFormat) {
2538         qreal margin = qMax(blockFormat.topMargin(), previousBlockFormat->bottomMargin());
2539         if (margin > 0 && q->paintDevice()) {
2540             margin *= qreal(q->paintDevice()->logicalDpiY()) / qreal(qt_defaultDpi());
2541         }
2542         layoutStruct->y += QFixed::fromReal(margin);
2543     }
2544
2545     //QTextFrameData *fd = data(layoutStruct->frame);
2546
2547     Qt::LayoutDirection dir = bl.textDirection();
2548
2549     QFixed extraMargin;
2550     if (docPrivate->defaultTextOption.flags() & QTextOption::AddSpaceForLineAndParagraphSeparators) {
2551         QFontMetricsF fm(bl.charFormat().font());
2552         extraMargin = QFixed::fromReal(fm.width(QChar(QChar(0x21B5))));
2553     }
2554
2555     const QFixed indent = this->blockIndent(blockFormat);
2556     const QFixed totalLeftMargin = QFixed::fromReal(blockFormat.leftMargin()) + (dir == Qt::RightToLeft ? extraMargin : indent);
2557     const QFixed totalRightMargin = QFixed::fromReal(blockFormat.rightMargin()) + (dir == Qt::RightToLeft ? indent : extraMargin);
2558
2559     const QPointF oldPosition = tl->position();
2560     tl->setPosition(QPointF(layoutStruct->x_left.toReal(), layoutStruct->y.toReal()));
2561
2562     if (layoutStruct->fullLayout
2563         || (blockPosition + blockLength > layoutFrom && blockPosition <= layoutTo)
2564         // force relayout if we cross a page boundary
2565         || (layoutStruct->pageHeight != QFIXED_MAX && layoutStruct->absoluteY() + QFixed::fromReal(tl->boundingRect().height()) > layoutStruct->pageBottom)) {
2566
2567         LDEBUG << " do layout";
2568         QTextOption option = docPrivate->defaultTextOption;
2569         option.setTextDirection(dir);
2570         option.setTabs( blockFormat.tabPositions() );
2571
2572         Qt::Alignment align = docPrivate->defaultTextOption.alignment();
2573         if (blockFormat.hasProperty(QTextFormat::BlockAlignment))
2574             align = blockFormat.alignment();
2575         option.setAlignment(QStyle::visualAlignment(dir, align)); // for paragraph that are RTL, alignment is auto-reversed;
2576
2577         if (blockFormat.nonBreakableLines() || document->pageSize().width() < 0) {
2578             option.setWrapMode(QTextOption::ManualWrap);
2579         }
2580
2581         tl->setTextOption(option);
2582
2583         const bool haveWordOrAnyWrapMode = (option.wrapMode() == QTextOption::WrapAtWordBoundaryOrAnywhere);
2584
2585 //         qDebug() << "    layouting block at" << bl.position();
2586         const QFixed cy = layoutStruct->y;
2587         const QFixed l = layoutStruct->x_left  + totalLeftMargin;
2588         const QFixed r = layoutStruct->x_right - totalRightMargin;
2589
2590         tl->beginLayout();
2591         bool firstLine = true;
2592         while (1) {
2593             QTextLine line = tl->createLine();
2594             if (!line.isValid())
2595                 break;
2596             line.setLeadingIncluded(true);
2597
2598             QFixed left, right;
2599             floatMargins(layoutStruct->y, layoutStruct, &left, &right);
2600             left = qMax(left, l);
2601             right = qMin(right, r);
2602             QFixed text_indent;
2603             if (firstLine) {
2604                 text_indent = QFixed::fromReal(blockFormat.textIndent());
2605                 if (dir == Qt::LeftToRight)
2606                     left += text_indent;
2607                 else
2608                     right -= text_indent;
2609                 firstLine = false;
2610             }
2611 //         qDebug() << "layout line y=" << currentYPos << "left=" << left << "right=" <<right;
2612
2613             if (fixedColumnWidth != -1)
2614                 line.setNumColumns(fixedColumnWidth, (right - left).toReal());
2615             else
2616                 line.setLineWidth((right - left).toReal());
2617
2618 //        qDebug() << "layoutBlock; layouting line with width" << right - left << "->textWidth" << line.textWidth();
2619             floatMargins(layoutStruct->y, layoutStruct, &left, &right);
2620             left = qMax(left, l);
2621             right = qMin(right, r);
2622             if (dir == Qt::LeftToRight)
2623                 left += text_indent;
2624             else
2625                 right -= text_indent;
2626
2627             if (fixedColumnWidth == -1 && QFixed::fromReal(line.naturalTextWidth()) > right-left) {
2628                 // float has been added in the meantime, redo
2629                 layoutStruct->pendingFloats.clear();
2630
2631                 line.setLineWidth((right-left).toReal());
2632                 if (QFixed::fromReal(line.naturalTextWidth()) > right-left) {
2633                     if (haveWordOrAnyWrapMode) {
2634                         option.setWrapMode(QTextOption::WrapAnywhere);
2635                         tl->setTextOption(option);
2636                     }
2637
2638                     layoutStruct->pendingFloats.clear();
2639                     // lines min width more than what we have
2640                     layoutStruct->y = findY(layoutStruct->y, layoutStruct, QFixed::fromReal(line.naturalTextWidth()));
2641                     floatMargins(layoutStruct->y, layoutStruct, &left, &right);
2642                     left = qMax(left, l);
2643                     right = qMin(right, r);
2644                     if (dir == Qt::LeftToRight)
2645                         left += text_indent;
2646                     else
2647                         right -= text_indent;
2648                     line.setLineWidth(qMax<qreal>(line.naturalTextWidth(), (right-left).toReal()));
2649
2650                     if (haveWordOrAnyWrapMode) {
2651                         option.setWrapMode(QTextOption::WordWrap);
2652                         tl->setTextOption(option);
2653                     }
2654                 }
2655
2656             }
2657
2658             QFixed lineBreakHeight, lineHeight, lineAdjustment;
2659             qreal scaling = (q->paintDevice() && q->paintDevice()->logicalDpiY() != qt_defaultDpi()) ?
2660                             qreal(q->paintDevice()->logicalDpiY()) / qreal(qt_defaultDpi()) : 1;
2661             getLineHeightParams(blockFormat, line, scaling, &lineAdjustment, &lineBreakHeight, &lineHeight);
2662
2663             if (layoutStruct->pageHeight > 0 && layoutStruct->absoluteY() + lineBreakHeight > layoutStruct->pageBottom) {
2664                 layoutStruct->newPage();
2665
2666                 floatMargins(layoutStruct->y, layoutStruct, &left, &right);
2667                 left = qMax(left, l);
2668                 right = qMin(right, r);
2669                 if (dir == Qt::LeftToRight)
2670                     left += text_indent;
2671                 else
2672                     right -= text_indent;
2673             }
2674
2675             line.setPosition(QPointF((left - layoutStruct->x_left).toReal(), (layoutStruct->y - cy - lineAdjustment).toReal()));
2676             layoutStruct->y += lineHeight;
2677             layoutStruct->contentsWidth
2678                 = qMax<QFixed>(layoutStruct->contentsWidth, QFixed::fromReal(line.x() + line.naturalTextWidth()) + totalRightMargin);
2679
2680             // position floats
2681             for (int i = 0; i < layoutStruct->pendingFloats.size(); ++i) {
2682                 QTextFrame *f = layoutStruct->pendingFloats.at(i);
2683                 positionFloat(f);
2684             }
2685             layoutStruct->pendingFloats.clear();
2686         }
2687         tl->endLayout();
2688     } else {
2689         const int cnt = tl->lineCount();
2690         for (int i = 0; i < cnt; ++i) {
2691             LDEBUG << "going to move text line" << i;
2692             QTextLine line = tl->lineAt(i);
2693             layoutStruct->contentsWidth
2694                 = qMax(layoutStruct->contentsWidth, QFixed::fromReal(line.x() + tl->lineAt(i).naturalTextWidth()) + totalRightMargin);
2695
2696             QFixed lineBreakHeight, lineHeight, lineAdjustment;
2697             qreal scaling = (q->paintDevice() && q->paintDevice()->logicalDpiY() != qt_defaultDpi()) ?
2698                             qreal(q->paintDevice()->logicalDpiY()) / qreal(qt_defaultDpi()) : 1;
2699             getLineHeightParams(blockFormat, line, scaling, &lineAdjustment, &lineBreakHeight, &lineHeight);
2700
2701             if (layoutStruct->pageHeight != QFIXED_MAX) {
2702                 if (layoutStruct->absoluteY() + lineBreakHeight > layoutStruct->pageBottom)
2703                     layoutStruct->newPage();
2704                 line.setPosition(QPointF(line.position().x(), (layoutStruct->y - lineAdjustment).toReal() - tl->position().y()));
2705             }
2706             layoutStruct->y += lineHeight;
2707         }
2708         if (layoutStruct->updateRect.isValid()
2709             && blockLength > 1) {
2710             if (layoutFrom >= blockPosition + blockLength) {
2711                 // if our height didn't change and the change in the document is
2712                 // in one of the later paragraphs, then we don't need to repaint
2713                 // this one
2714                 layoutStruct->updateRect.setTop(qMax(layoutStruct->updateRect.top(), layoutStruct->y.toReal()));
2715             } else if (layoutTo < blockPosition) {
2716                 if (oldPosition == tl->position())
2717                     // if the change in the document happened earlier in the document
2718                     // and our position did /not/ change because none of the earlier paragraphs
2719                     // or frames changed their height, then we don't need to repaint
2720                     // this one
2721                     layoutStruct->updateRect.setBottom(qMin(layoutStruct->updateRect.bottom(), tl->position().y()));
2722                 else
2723                     layoutStruct->updateRect.setBottom(qreal(INT_MAX)); // reset
2724             }
2725         }
2726     }
2727
2728     // ### doesn't take floats into account. would need to do it per line. but how to retrieve then? (Simon)
2729     const QFixed margins = totalLeftMargin + totalRightMargin;
2730     layoutStruct->minimumWidth = qMax(layoutStruct->minimumWidth, QFixed::fromReal(tl->minimumWidth()) + margins);
2731
2732     const QFixed maxW = QFixed::fromReal(tl->maximumWidth()) + margins;
2733
2734     if (maxW > 0) {
2735         if (layoutStruct->maximumWidth == QFIXED_MAX)
2736             layoutStruct->maximumWidth = maxW;
2737         else
2738             layoutStruct->maximumWidth = qMax(layoutStruct->maximumWidth, maxW);
2739     }
2740 }
2741
2742 void QTextDocumentLayoutPrivate::floatMargins(const QFixed &y, const QTextLayoutStruct *layoutStruct,
2743                                               QFixed *left, QFixed *right) const
2744 {
2745 //     qDebug() << "floatMargins y=" << y;
2746     *left = layoutStruct->x_left;
2747     *right = layoutStruct->x_right;
2748     QTextFrameData *lfd = data(layoutStruct->frame);
2749     for (int i = 0; i < lfd->floats.size(); ++i) {
2750         QTextFrameData *fd = data(lfd->floats.at(i));
2751         if (!fd->layoutDirty) {
2752             if (fd->position.y <= y && fd->position.y + fd->size.height > y) {
2753 //                 qDebug() << "adjusting with float" << f << fd->position.x()<< fd->size.width();
2754                 if (lfd->floats.at(i)->frameFormat().position() == QTextFrameFormat::FloatLeft)
2755                     *left = qMax(*left, fd->position.x + fd->size.width);
2756                 else
2757                     *right = qMin(*right, fd->position.x);
2758             }
2759         }
2760     }
2761 //     qDebug() << "floatMargins: left="<<*left<<"right="<<*right<<"y="<<y;
2762 }
2763
2764 QFixed QTextDocumentLayoutPrivate::findY(QFixed yFrom, const QTextLayoutStruct *layoutStruct, QFixed requiredWidth) const
2765 {
2766     QFixed right, left;
2767     requiredWidth = qMin(requiredWidth, layoutStruct->x_right - layoutStruct->x_left);
2768
2769 //     qDebug() << "findY:" << yFrom;
2770     while (1) {
2771         floatMargins(yFrom, layoutStruct, &left, &right);
2772 //         qDebug() << "    yFrom=" << yFrom<<"right=" << right << "left=" << left << "requiredWidth=" << requiredWidth;
2773         if (right-left >= requiredWidth)
2774             break;
2775
2776         // move float down until we find enough space
2777         QFixed newY = QFIXED_MAX;
2778         QTextFrameData *lfd = data(layoutStruct->frame);
2779         for (int i = 0; i < lfd->floats.size(); ++i) {
2780             QTextFrameData *fd = data(lfd->floats.at(i));
2781             if (!fd->layoutDirty) {
2782                 if (fd->position.y <= yFrom && fd->position.y + fd->size.height > yFrom)
2783                     newY = qMin(newY, fd->position.y + fd->size.height);
2784             }
2785         }
2786         if (newY == QFIXED_MAX)
2787             break;
2788         yFrom = newY;
2789     }
2790     return yFrom;
2791 }
2792
2793 QTextDocumentLayout::QTextDocumentLayout(QTextDocument *doc)
2794     : QAbstractTextDocumentLayout(*new QTextDocumentLayoutPrivate, doc)
2795 {
2796     registerHandler(QTextFormat::ImageObject, new QTextImageHandler(this));
2797 }
2798
2799
2800 void QTextDocumentLayout::draw(QPainter *painter, const PaintContext &context)
2801 {
2802     Q_D(QTextDocumentLayout);
2803     QTextFrame *frame = d->document->rootFrame();
2804     QTextFrameData *fd = data(frame);
2805
2806     if(fd->sizeDirty)
2807         return;
2808
2809     if (context.clip.isValid()) {
2810         d->ensureLayouted(QFixed::fromReal(context.clip.bottom()));
2811     } else {
2812         d->ensureLayoutFinished();
2813     }
2814
2815     QFixed width = fd->size.width;
2816     if (d->document->pageSize().width() == 0 && d->viewportRect.isValid()) {
2817         // we're in NoWrap mode, meaning the frame should expand to the viewport
2818         // so that backgrounds are drawn correctly
2819         fd->size.width = qMax(width, QFixed::fromReal(d->viewportRect.right()));
2820     }
2821
2822     // Make sure we conform to the root frames bounds when drawing.
2823     d->clipRect = QRectF(fd->position.toPointF(), fd->size.toSizeF()).adjusted(fd->leftMargin.toReal(), 0, -fd->rightMargin.toReal(), 0);
2824     d->drawFrame(QPointF(), painter, context, frame);
2825     fd->size.width = width;
2826 }
2827
2828 void QTextDocumentLayout::setViewport(const QRectF &viewport)
2829 {
2830     Q_D(QTextDocumentLayout);
2831     d->viewportRect = viewport;
2832 }
2833
2834 static void markFrames(QTextFrame *current, int from, int oldLength, int length)
2835 {
2836     int end = qMax(oldLength, length) + from;
2837
2838     if (current->firstPosition() >= end || current->lastPosition() < from)
2839         return;
2840
2841     QTextFrameData *fd = data(current);
2842     for (int i = 0; i < fd->floats.size(); ++i) {
2843         QTextFrame *f = fd->floats[i];
2844         if (!f) {
2845             // float got removed in editing operation
2846             fd->floats.removeAt(i);
2847             --i;
2848         }
2849     }
2850
2851     fd->layoutDirty = true;
2852     fd->sizeDirty = true;
2853
2854 //     qDebug("    marking frame (%d--%d) as dirty", current->firstPosition(), current->lastPosition());
2855     QList<QTextFrame *> children = current->childFrames();
2856     for (int i = 0; i < children.size(); ++i)
2857         markFrames(children.at(i), from, oldLength, length);
2858 }
2859
2860 void QTextDocumentLayout::documentChanged(int from, int oldLength, int length)
2861 {
2862     Q_D(QTextDocumentLayout);
2863
2864     QTextBlock blockIt = document()->findBlock(from);
2865     QTextBlock endIt = document()->findBlock(qMax(0, from + length - 1));
2866     if (endIt.isValid())
2867         endIt = endIt.next();
2868      for (; blockIt.isValid() && blockIt != endIt; blockIt = blockIt.next())
2869          blockIt.clearLayout();
2870
2871     if (d->docPrivate->pageSize.isNull())
2872         return;
2873
2874     QRectF updateRect;
2875
2876     d->lazyLayoutStepSize = 1000;
2877     d->sizeChangedTimer.stop();
2878     d->insideDocumentChange = true;
2879
2880     const int documentLength = d->docPrivate->length();
2881     const bool fullLayout = (oldLength == 0 && length == documentLength);
2882     const bool smallChange = documentLength > 0
2883                              && (qMax(length, oldLength) * 100 / documentLength) < 5;
2884
2885     // don't show incremental layout progress (avoid scroll bar flicker)
2886     // if we see only a small change in the document and we're either starting
2887     // a layout run or we're already in progress for that and we haven't seen
2888     // any bigger change previously (showLayoutProgress already false)
2889     if (smallChange
2890         && (d->currentLazyLayoutPosition == -1 || d->showLayoutProgress == false))
2891         d->showLayoutProgress = false;
2892     else
2893         d->showLayoutProgress = true;
2894
2895     if (fullLayout) {
2896         d->contentHasAlignment = false;
2897         d->currentLazyLayoutPosition = 0;
2898         d->checkPoints.clear();
2899         d->layoutStep();
2900     } else {
2901         d->ensureLayoutedByPosition(from);
2902         updateRect = doLayout(from, oldLength, length);
2903     }
2904
2905     if (!d->layoutTimer.isActive() && d->currentLazyLayoutPosition != -1)
2906         d->layoutTimer.start(10, this);
2907
2908     d->insideDocumentChange = false;
2909
2910     if (d->showLayoutProgress) {
2911         const QSizeF newSize = dynamicDocumentSize();
2912         if (newSize != d->lastReportedSize) {
2913             d->lastReportedSize = newSize;
2914             emit documentSizeChanged(newSize);
2915         }
2916     }
2917
2918     if (!updateRect.isValid()) {
2919         // don't use the frame size, it might have shrunken
2920         updateRect = QRectF(QPointF(0, 0), QSizeF(qreal(INT_MAX), qreal(INT_MAX)));
2921     }
2922
2923     emit update(updateRect);
2924 }
2925
2926 QRectF QTextDocumentLayout::doLayout(int from, int oldLength, int length)
2927 {
2928     Q_D(QTextDocumentLayout);
2929
2930 //     qDebug("documentChange: from=%d, oldLength=%d, length=%d", from, oldLength, length);
2931
2932     // mark all frames between f_start and f_end as dirty
2933     markFrames(d->docPrivate->rootFrame(), from, oldLength, length);
2934
2935     QRectF updateRect;
2936
2937     QTextFrame *root = d->docPrivate->rootFrame();
2938     if(data(root)->sizeDirty)
2939         updateRect = d->layoutFrame(root, from, from + length);
2940     data(root)->layoutDirty = false;
2941
2942     if (d->currentLazyLayoutPosition == -1)
2943         layoutFinished();
2944     else if (d->showLayoutProgress)
2945         d->sizeChangedTimer.start(0, this);
2946
2947     return updateRect;
2948 }
2949
2950 int QTextDocumentLayout::hitTest(const QPointF &point, Qt::HitTestAccuracy accuracy) const
2951 {
2952     Q_D(const QTextDocumentLayout);
2953     d->ensureLayouted(QFixed::fromReal(point.y()));
2954     QTextFrame *f = d->docPrivate->rootFrame();
2955     int position = 0;
2956     QTextLayout *l = 0;
2957     QFixedPoint pointf;
2958     pointf.x = QFixed::fromReal(point.x());
2959     pointf.y = QFixed::fromReal(point.y());
2960     QTextDocumentLayoutPrivate::HitPoint p = d->hitTest(f, pointf, &position, &l, accuracy);
2961     if (accuracy == Qt::ExactHit && p < QTextDocumentLayoutPrivate::PointExact)
2962         return -1;
2963
2964     // ensure we stay within document bounds
2965     int lastPos = f->lastPosition();
2966     if (l && !l->preeditAreaText().isEmpty())
2967         lastPos += l->preeditAreaText().length();
2968     if (position > lastPos)
2969         position = lastPos;
2970     else if (position < 0)
2971         position = 0;
2972
2973     return position;
2974 }
2975
2976 void QTextDocumentLayout::resizeInlineObject(QTextInlineObject item, int posInDocument, const QTextFormat &format)
2977 {
2978     Q_D(QTextDocumentLayout);
2979     QTextCharFormat f = format.toCharFormat();
2980     Q_ASSERT(f.isValid());
2981     QTextObjectHandler handler = d->handlers.value(f.objectType());
2982     if (!handler.component)
2983         return;
2984
2985     QSizeF intrinsic = handler.iface->intrinsicSize(d->document, posInDocument, format);
2986
2987     QTextFrameFormat::Position pos = QTextFrameFormat::InFlow;
2988     QTextFrame *frame = qobject_cast<QTextFrame *>(d->document->objectForFormat(f));
2989     if (frame) {
2990         pos = frame->frameFormat().position();
2991         QTextFrameData *fd = data(frame);
2992         fd->sizeDirty = false;
2993         fd->size = QFixedSize::fromSizeF(intrinsic);
2994         fd->minimumWidth = fd->maximumWidth = fd->size.width;
2995     }
2996
2997     QSizeF inlineSize = (pos == QTextFrameFormat::InFlow ? intrinsic : QSizeF(0, 0));
2998     item.setWidth(inlineSize.width());
2999
3000     QFontMetrics m(f.font());
3001     switch (f.verticalAlignment())
3002     {
3003     case QTextCharFormat::AlignMiddle:
3004         item.setDescent(inlineSize.height() / 2);
3005         item.setAscent(inlineSize.height() / 2 - 1);
3006         break;
3007     case QTextCharFormat::AlignBaseline:
3008         item.setDescent(m.descent());
3009         item.setAscent(inlineSize.height() - m.descent() - 1);
3010         break;
3011     default:
3012         item.setDescent(0);
3013         item.setAscent(inlineSize.height() - 1);
3014     }
3015 }
3016
3017 void QTextDocumentLayout::positionInlineObject(QTextInlineObject item, int posInDocument, const QTextFormat &format)
3018 {
3019     Q_D(QTextDocumentLayout);
3020     Q_UNUSED(posInDocument);
3021     if (item.width() != 0)
3022         // inline
3023         return;
3024
3025     QTextCharFormat f = format.toCharFormat();
3026     Q_ASSERT(f.isValid());
3027     QTextObjectHandler handler = d->handlers.value(f.objectType());
3028     if (!handler.component)
3029         return;
3030
3031     QTextFrame *frame = qobject_cast<QTextFrame *>(d->document->objectForFormat(f));
3032     if (!frame)
3033         return;
3034
3035     QTextBlock b = d->document->findBlock(frame->firstPosition());
3036     QTextLine line;
3037     if (b.position() <= frame->firstPosition() && b.position() + b.length() > frame->lastPosition())
3038         line = b.layout()->lineAt(b.layout()->lineCount()-1);
3039 //     qDebug() << "layoutObject: line.isValid" << line.isValid() << b.position() << b.length() <<
3040 //         frame->firstPosition() << frame->lastPosition();
3041     d->positionFloat(frame, line.isValid() ? &line : 0);
3042 }
3043
3044 void QTextDocumentLayout::drawInlineObject(QPainter *p, const QRectF &rect, QTextInlineObject item,
3045                                            int posInDocument, const QTextFormat &format)
3046 {
3047     Q_D(QTextDocumentLayout);
3048     QTextCharFormat f = format.toCharFormat();
3049     Q_ASSERT(f.isValid());
3050     QTextFrame *frame = qobject_cast<QTextFrame *>(d->document->objectForFormat(f));
3051     if (frame && frame->frameFormat().position() != QTextFrameFormat::InFlow)
3052         return; // don't draw floating frames from inline objects here but in drawFlow instead
3053
3054 //    qDebug() << "drawObject at" << r;
3055     QAbstractTextDocumentLayout::drawInlineObject(p, rect, item, posInDocument, format);
3056 }
3057
3058 int QTextDocumentLayout::dynamicPageCount() const
3059 {
3060     Q_D(const QTextDocumentLayout);
3061     const QSizeF pgSize = d->document->pageSize();
3062     if (pgSize.height() < 0)
3063         return 1;
3064     return qCeil(dynamicDocumentSize().height() / pgSize.height());
3065 }
3066
3067 QSizeF QTextDocumentLayout::dynamicDocumentSize() const
3068 {
3069     Q_D(const QTextDocumentLayout);
3070     return data(d->docPrivate->rootFrame())->size.toSizeF();
3071 }
3072
3073 int QTextDocumentLayout::pageCount() const
3074 {
3075     Q_D(const QTextDocumentLayout);
3076     d->ensureLayoutFinished();
3077     return dynamicPageCount();
3078 }
3079
3080 QSizeF QTextDocumentLayout::documentSize() const
3081 {
3082     Q_D(const QTextDocumentLayout);
3083     d->ensureLayoutFinished();
3084     return dynamicDocumentSize();
3085 }
3086
3087 void QTextDocumentLayoutPrivate::ensureLayouted(QFixed y) const
3088 {
3089     Q_Q(const QTextDocumentLayout);
3090     if (currentLazyLayoutPosition == -1)
3091         return;
3092     const QSizeF oldSize = q->dynamicDocumentSize();
3093     Q_UNUSED(oldSize);
3094
3095     if (checkPoints.isEmpty())
3096         layoutStep();
3097
3098     while (currentLazyLayoutPosition != -1
3099            && checkPoints.last().y < y)
3100         layoutStep();
3101 }
3102
3103 void QTextDocumentLayoutPrivate::ensureLayoutedByPosition(int position) const
3104 {
3105     if (currentLazyLayoutPosition == -1)
3106         return;
3107     if (position < currentLazyLayoutPosition)
3108         return;
3109     while (currentLazyLayoutPosition != -1
3110            && currentLazyLayoutPosition < position) {
3111         const_cast<QTextDocumentLayout *>(q_func())->doLayout(currentLazyLayoutPosition, 0, INT_MAX - currentLazyLayoutPosition);
3112     }
3113 }
3114
3115 void QTextDocumentLayoutPrivate::layoutStep() const
3116 {
3117     ensureLayoutedByPosition(currentLazyLayoutPosition + lazyLayoutStepSize);
3118     lazyLayoutStepSize = qMin(200000, lazyLayoutStepSize * 2);
3119 }
3120
3121 void QTextDocumentLayout::setCursorWidth(int width)
3122 {
3123     Q_D(QTextDocumentLayout);
3124     d->cursorWidth = width;
3125 }
3126
3127 int QTextDocumentLayout::cursorWidth() const
3128 {
3129     Q_D(const QTextDocumentLayout);
3130     return d->cursorWidth;
3131 }
3132
3133 void QTextDocumentLayout::setFixedColumnWidth(int width)
3134 {
3135     Q_D(QTextDocumentLayout);
3136     d->fixedColumnWidth = width;
3137 }
3138
3139 QRectF QTextDocumentLayout::frameBoundingRect(QTextFrame *frame) const
3140 {
3141     Q_D(const QTextDocumentLayout);
3142     if (d->docPrivate->pageSize.isNull())
3143         return QRectF();
3144     d->ensureLayoutFinished();
3145     return d->frameBoundingRectInternal(frame);
3146 }
3147
3148 QRectF QTextDocumentLayoutPrivate::frameBoundingRectInternal(QTextFrame *frame) const
3149 {
3150     QPointF pos;
3151     const int framePos = frame->firstPosition();
3152     QTextFrame *f = frame;
3153     while (f) {
3154         QTextFrameData *fd = data(f);
3155         pos += fd->position.toPointF();
3156
3157         if (QTextTable *table = qobject_cast<QTextTable *>(f)) {
3158             QTextTableCell cell = table->cellAt(framePos);
3159             if (cell.isValid())
3160                 pos += static_cast<QTextTableData *>(fd)->cellPosition(cell).toPointF();
3161         }
3162
3163         f = f->parentFrame();
3164     }
3165     return QRectF(pos, data(frame)->size.toSizeF());
3166 }
3167
3168 QRectF QTextDocumentLayout::blockBoundingRect(const QTextBlock &block) const
3169 {
3170     Q_D(const QTextDocumentLayout);
3171     if (d->docPrivate->pageSize.isNull() || !block.isValid())
3172         return QRectF();
3173     d->ensureLayoutedByPosition(block.position() + block.length());
3174     QTextFrame *frame = d->document->frameAt(block.position());
3175     QPointF offset;
3176     const int blockPos = block.position();
3177
3178     while (frame) {
3179         QTextFrameData *fd = data(frame);
3180         offset += fd->position.toPointF();
3181
3182         if (QTextTable *table = qobject_cast<QTextTable *>(frame)) {
3183             QTextTableCell cell = table->cellAt(blockPos);
3184             if (cell.isValid())
3185                 offset += static_cast<QTextTableData *>(fd)->cellPosition(cell).toPointF();
3186         }
3187
3188         frame = frame->parentFrame();
3189     }
3190
3191     const QTextLayout *layout = block.layout();
3192     QRectF rect = layout->boundingRect();
3193     rect.moveTopLeft(layout->position() + offset);
3194     return rect;
3195 }
3196
3197 int QTextDocumentLayout::layoutStatus() const
3198 {
3199     Q_D(const QTextDocumentLayout);
3200     int pos = d->currentLazyLayoutPosition;
3201     if (pos == -1)
3202         return 100;
3203     return pos * 100 / d->document->docHandle()->length();
3204 }
3205
3206 void QTextDocumentLayout::timerEvent(QTimerEvent *e)
3207 {
3208     Q_D(QTextDocumentLayout);
3209     if (e->timerId() == d->layoutTimer.timerId()) {
3210         if (d->currentLazyLayoutPosition != -1)
3211             d->layoutStep();
3212     } else if (e->timerId() == d->sizeChangedTimer.timerId()) {
3213         d->lastReportedSize = dynamicDocumentSize();
3214         emit documentSizeChanged(d->lastReportedSize);
3215         d->sizeChangedTimer.stop();
3216
3217         if (d->currentLazyLayoutPosition == -1) {
3218             const int newCount = dynamicPageCount();
3219             if (newCount != d->lastPageCount) {
3220                 d->lastPageCount = newCount;
3221                 emit pageCountChanged(newCount);
3222             }
3223         }
3224     } else {
3225         QAbstractTextDocumentLayout::timerEvent(e);
3226     }
3227 }
3228
3229 void QTextDocumentLayout::layoutFinished()
3230 {
3231     Q_D(QTextDocumentLayout);
3232     d->layoutTimer.stop();
3233     if (!d->insideDocumentChange)
3234         d->sizeChangedTimer.start(0, this);
3235     // reset
3236     d->showLayoutProgress = true;
3237 }
3238
3239 void QTextDocumentLayout::ensureLayouted(qreal y)
3240 {
3241     d_func()->ensureLayouted(QFixed::fromReal(y));
3242 }
3243
3244 qreal QTextDocumentLayout::idealWidth() const
3245 {
3246     Q_D(const QTextDocumentLayout);
3247     d->ensureLayoutFinished();
3248     return d->idealWidth;
3249 }
3250
3251 bool QTextDocumentLayout::contentHasAlignment() const
3252 {
3253     Q_D(const QTextDocumentLayout);
3254     return d->contentHasAlignment;
3255 }
3256
3257 qreal QTextDocumentLayoutPrivate::scaleToDevice(qreal value) const
3258 {
3259     if (!paintDevice)
3260         return value;
3261     return value * paintDevice->logicalDpiY() / qreal(qt_defaultDpi());
3262 }
3263
3264 QFixed QTextDocumentLayoutPrivate::scaleToDevice(QFixed value) const
3265 {
3266     if (!paintDevice)
3267         return value;
3268     return value * QFixed(paintDevice->logicalDpiY()) / QFixed(qt_defaultDpi());
3269 }
3270
3271 QT_END_NAMESPACE
3272
3273 #include "moc_qtextdocumentlayout_p.cpp"