src/gui/text/qtextdocument_p.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 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include <private/qtools_p.h>
  43 #include <qdebug.h>
  44
  45 #include "qtextdocument_p.h"
  46 #include "qtextdocument.h"
  47 #include <qtextformat.h>
  48 #include "qtextformat_p.h"
  49 #include "qtextobject_p.h"
  50 #include "qtextcursor.h"
  51 #include "qtextimagehandler_p.h"
  52 #include "qtextcursor_p.h"
  53 #include "qtextdocumentlayout_p.h"
  54 #include "qtexttable.h"
  55 #include "qtextengine_p.h"
  56
  57 #include <stdlib.h>
  58
  59 QT_BEGIN_NAMESPACE
  60
  61 #define PMDEBUG if(0) qDebug
  62
  63 // The VxWorks DIAB compiler crashes when initializing the anonymouse union with { a7 }
  64 #if !defined(Q_CC_DIAB)
  65 #  define QT_INIT_TEXTUNDOCOMMAND(c, a1, a2, a3, a4, a5, a6, a7, a8) \
  66           QTextUndoCommand c = { a1, a2, 0, 0, quint8(a3), a4, a5, a6, { a7 }, a8 }
  67 #else
  68 #  define QT_INIT_TEXTUNDOCOMMAND(c, a1, a2, a3, a4, a5, a6, a7, a8) \
  69           QTextUndoCommand c = { a1, a2, 0, 0, a3, a4, a5, a6 }; c.blockFormat = a7; c.revision = a8
  70 #endif
  71
  72 /*
  73   Structure of a document:
  74
  75   DOCUMENT :== FRAME_CONTENTS
  76   FRAME :== START_OF_FRAME  FRAME_CONTENTS END_OF_FRAME
  77   FRAME_CONTENTS = LIST_OF_BLOCKS ((FRAME | TABLE) LIST_OF_BLOCKS)*
  78   TABLE :== (START_OF_FRAME TABLE_CELL)+ END_OF_FRAME
  79   TABLE_CELL = FRAME_CONTENTS
  80   LIST_OF_BLOCKS :== (BLOCK END_OF_PARA)* BLOCK
  81   BLOCK :== (FRAGMENT)*
  82   FRAGMENT :== String of characters
  83
  84   END_OF_PARA :== 0x2029 # Paragraph separator in Unicode
  85   START_OF_FRAME :== 0xfdd0
  86   END_OF_FRAME := 0xfdd1
  87
  88   Note also that LIST_OF_BLOCKS can be empty. Nevertheless, there is
  89   at least one valid cursor position there where you could start
  90   typing. The block format is in this case determined by the last
  91   END_OF_PARA/START_OF_FRAME/END_OF_FRAME (see below).
  92
  93   Lists are not in here, as they are treated specially. A list is just
  94   a collection of (not necessarily connected) blocks, that share the
  95   same objectIndex() in the format that refers to the list format and
  96   object.
  97
  98   The above does not clearly note where formats are. Here's
  99   how it looks currently:
 100
 101   FRAGMENT: one charFormat associated
 102
 103   END_OF_PARA: one charFormat, and a blockFormat for the _next_ block.
 104
 105   START_OF_FRAME: one char format, and a blockFormat (for the next
 106   block). The format associated with the objectIndex() of the
 107   charFormat decides whether this is a frame or table and its
 108   properties
 109
 110   END_OF_FRAME: one charFormat and a blockFormat (for the next
 111   block). The object() of the charFormat is the same as for the
 112   corresponding START_OF_BLOCK.
 113
 114
 115   The document is independent of the layout with certain restrictions:
 116
 117   * Cursor movement (esp. up and down) depend on the layout.
 118   * You cannot have more than one layout, as the layout data of QTextObjects
 119     is stored in the text object itself.
 120
 121 */
 122
 123 void QTextBlockData::invalidate() const
 124 {
 125     if (layout)
 126         layout->engine()->invalidate();
 127 }
 128
 129 static bool isValidBlockSeparator(const QChar &ch)
 130 {
 131     return ch == QChar::ParagraphSeparator
 132         || ch == QTextBeginningOfFrame
 133         || ch == QTextEndOfFrame;
 134 }
 135
 136 #ifndef QT_NO_DEBUG
 137 static bool noBlockInString(const QString &str)
 138 {
 139     return !str.contains(QChar::ParagraphSeparator)
 140         && !str.contains(QTextBeginningOfFrame)
 141         && !str.contains(QTextEndOfFrame);
 142 }
 143 #endif
 144
 145 bool QTextUndoCommand::tryMerge(const QTextUndoCommand &other)
 146 {
 147     if (command != other.command)
 148         return false;
 149
 150     if (command == Inserted
 151         && (pos + length == other.pos)
 152         && (strPos + length == other.strPos)
 153         && format == other.format) {
 154
 155         length += other.length;
 156         return true;
 157     }
 158
 159     // removal to the 'right' using 'Delete' key
 160     if (command == Removed
 161         && pos == other.pos
 162         && (strPos + length == other.strPos)
 163         && format == other.format) {
 164
 165         length += other.length;
 166         return true;
 167     }
 168
 169     // removal to the 'left' using 'Backspace'
 170     if (command == Removed
 171         && (other.pos + other.length == pos)
 172         && (other.strPos + other.length == strPos)
 173         && (format == other.format)) {
 174
 175         int l = length;
 176         (*this) = other;
 177
 178         length += l;
 179         return true;
 180     }
 181
 182     return false;
 183 }
 184
 185 QTextDocumentPrivate::QTextDocumentPrivate()
 186     : wasUndoAvailable(false),
 187     wasRedoAvailable(false),
 188     docChangeOldLength(0),
 189     docChangeLength(0),
 190     framesDirty(true),
 191     rtFrame(0),
 192     initialBlockCharFormatIndex(-1) // set correctly later in init()
 193 {
 194     editBlock = 0;
 195     editBlockCursorPosition = -1;
 196     docChangeFrom = -1;
 197
 198     undoState = 0;
 199     revision = -1; // init() inserts a block, bringing it to 0
 200
 201     lout = 0;
 202
 203     modified = false;
 204     modifiedState = 0;
 205
 206     undoEnabled = true;
 207     inContentsChange = false;
 208     blockCursorAdjustment = false;
 209
 210     defaultTextOption.setTabStop(80); // same as in qtextengine.cpp
 211     defaultTextOption.setWrapMode(QTextOption::WrapAtWordBoundaryOrAnywhere);
 212     defaultCursorMoveStyle = Qt::LogicalMoveStyle;
 213
 214     indentWidth = 40;
 215     documentMargin = 4;
 216
 217     maximumBlockCount = 0;
 218     needsEnsureMaximumBlockCount = false;
 219     unreachableCharacterCount = 0;
 220     lastBlockCount = 0;
 221 }
 222
 223 void QTextDocumentPrivate::init()
 224 {
 225     framesDirty = false;
 226
 227     bool undoState = undoEnabled;
 228     undoEnabled = false;
 229     initialBlockCharFormatIndex = formats.indexForFormat(QTextCharFormat());
 230     insertBlock(0, formats.indexForFormat(QTextBlockFormat()), formats.indexForFormat(QTextCharFormat()));
 231     undoEnabled = undoState;
 232     modified = false;
 233     modifiedState = 0;
 234 }
 235
 236 void QTextDocumentPrivate::clear()
 237 {
 238     Q_Q(QTextDocument);
 239
 240     foreach (QTextCursorPrivate *curs, cursors) {
 241         curs->setPosition(0);
 242         curs->currentCharFormat = -1;
 243         curs->anchor = 0;
 244         curs->adjusted_anchor = 0;
 245     }
 246
 247     QList<QTextCursorPrivate *>oldCursors = cursors;
 248     QT_TRY{
 249         cursors.clear();
 250
 251         QMap<int, QTextObject *>::Iterator objectIt = objects.begin();
 252         while (objectIt != objects.end()) {
 253             if (*objectIt != rtFrame) {
 254                 delete *objectIt;
 255                 objectIt = objects.erase(objectIt);
 256             } else {
 257                 ++objectIt;
 258             }
 259         }
 260         // also clear out the remaining root frame pointer
 261         // (we're going to delete the object further down)
 262         objects.clear();
 263
 264         title.clear();
 265         clearUndoRedoStacks(QTextDocument::UndoAndRedoStacks);
 266         text = QString();
 267         unreachableCharacterCount = 0;
 268         modifiedState = 0;
 269         modified = false;
 270         formats = QTextFormatCollection();
 271         int len = fragments.length();
 272         fragments.clear();
 273         blocks.clear();
 274         cachedResources.clear();
 275         delete rtFrame;
 276         rtFrame = 0;
 277         init();
 278         cursors = oldCursors;
 279         inContentsChange = true;
 280         q->contentsChange(0, len, 0);
 281         inContentsChange = false;
 282         if (lout)
 283             lout->documentChanged(0, len, 0);
 284     } QT_CATCH(...) {
 285         cursors = oldCursors; // at least recover the cursors
 286         QT_RETHROW;
 287     }
 288 }
 289
 290 QTextDocumentPrivate::~QTextDocumentPrivate()
 291 {
 292     foreach (QTextCursorPrivate *curs, cursors)
 293         curs->priv = 0;
 294     cursors.clear();
 295     undoState = 0;
 296     undoEnabled = true;
 297     clearUndoRedoStacks(QTextDocument::RedoStack);
 298 }
 299
 300 void QTextDocumentPrivate::setLayout(QAbstractTextDocumentLayout *layout)
 301 {
 302     Q_Q(QTextDocument);
 303     if (lout == layout)
 304         return;
 305     const bool firstLayout = !lout;
 306     delete lout;
 307     lout = layout;
 308
 309     if (!firstLayout)
 310         for (BlockMap::Iterator it = blocks.begin(); !it.atEnd(); ++it)
 311             it->free();
 312
 313     emit q->documentLayoutChanged();
 314     inContentsChange = true;
 315     emit q->contentsChange(0, 0, length());
 316     inContentsChange = false;
 317     if (lout)
 318         lout->documentChanged(0, 0, length());
 319 }
 320
 321
 322 void QTextDocumentPrivate::insert_string(int pos, uint strPos, uint length, int format, QTextUndoCommand::Operation op)
 323 {
 324     // ##### optimize when only appending to the fragment!
 325     Q_ASSERT(noBlockInString(text.mid(strPos, length)));
 326
 327     split(pos);
 328     uint x = fragments.insert_single(pos, length);
 329     QTextFragmentData *X = fragments.fragment(x);
 330     X->format = format;
 331     X->stringPosition = strPos;
 332     uint w = fragments.previous(x);
 333     if (w)
 334         unite(w);
 335
 336     int b = blocks.findNode(pos);
 337     blocks.setSize(b, blocks.size(b)+length);
 338
 339     Q_ASSERT(blocks.length() == fragments.length());
 340
 341     QTextFrame *frame = qobject_cast<QTextFrame *>(objectForFormat(format));
 342     if (frame) {
 343         frame->d_func()->fragmentAdded(text.at(strPos), x);
 344         framesDirty = true;
 345     }
 346
 347     adjustDocumentChangesAndCursors(pos, length, op);
 348 }
 349
 350 int QTextDocumentPrivate::insert_block(int pos, uint strPos, int format, int blockFormat, QTextUndoCommand::Operation op, int command)
 351 {
 352     split(pos);
 353     uint x = fragments.insert_single(pos, 1);
 354     QTextFragmentData *X = fragments.fragment(x);
 355     X->format = format;
 356     X->stringPosition = strPos;
 357     // no need trying to unite, since paragraph separators are always in a fragment of their own
 358
 359     Q_ASSERT(isValidBlockSeparator(text.at(strPos)));
 360     Q_ASSERT(blocks.length()+1 == fragments.length());
 361
 362     int block_pos = pos;
 363     if (blocks.length() && command == QTextUndoCommand::BlockRemoved)
 364         ++block_pos;
 365     int size = 1;
 366     int n = blocks.findNode(block_pos);
 367     int key = n ? blocks.position(n) : blocks.length();
 368
 369     Q_ASSERT(n || (!n && block_pos == blocks.length()));
 370     if (key != block_pos) {
 371         Q_ASSERT(key < block_pos);
 372         int oldSize = blocks.size(n);
 373         blocks.setSize(n, block_pos-key);
 374         size += oldSize - (block_pos-key);
 375     }
 376     int b = blocks.insert_single(block_pos, size);
 377     QTextBlockData *B = blocks.fragment(b);
 378     B->format = blockFormat;
 379
 380     Q_ASSERT(blocks.length() == fragments.length());
 381
 382     QTextBlockGroup *group = qobject_cast<QTextBlockGroup *>(objectForFormat(blockFormat));
 383     if (group)
 384         group->blockInserted(QTextBlock(this, b));
 385
 386     QTextFrame *frame = qobject_cast<QTextFrame *>(objectForFormat(formats.format(format)));
 387     if (frame) {
 388         frame->d_func()->fragmentAdded(text.at(strPos), x);
 389         framesDirty = true;
 390     }
 391
 392     adjustDocumentChangesAndCursors(pos, 1, op);
 393     return x;
 394 }
 395
 396 int QTextDocumentPrivate::insertBlock(const QChar &blockSeparator,
 397                                   int pos, int blockFormat, int charFormat, QTextUndoCommand::Operation op)
 398 {
 399     Q_ASSERT(formats.format(blockFormat).isBlockFormat());
 400     Q_ASSERT(formats.format(charFormat).isCharFormat());
 401     Q_ASSERT(pos >= 0 && (pos < fragments.length() || (pos == 0 && fragments.length() == 0)));
 402     Q_ASSERT(isValidBlockSeparator(blockSeparator));
 403
 404     beginEditBlock();
 405
 406     int strPos = text.length();
 407     text.append(blockSeparator);
 408
 409     int ob = blocks.findNode(pos);
 410     bool atBlockEnd = true;
 411     bool atBlockStart = true;
 412     int oldRevision = 0;
 413     if (ob) {
 414         atBlockEnd = (pos - blocks.position(ob) == blocks.size(ob)-1);
 415         atBlockStart = ((int)blocks.position(ob) == pos);
 416         oldRevision = blocks.fragment(ob)->revision;
 417     }
 418
 419     const int fragment = insert_block(pos, strPos, charFormat, blockFormat, op, QTextUndoCommand::BlockRemoved);
 420
 421     Q_ASSERT(blocks.length() == fragments.length());
 422
 423     int b = blocks.findNode(pos);
 424     QTextBlockData *B = blocks.fragment(b);
 425
 426     QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::BlockInserted, (editBlock != 0),
 427                             op, charFormat, strPos, pos, blockFormat,
 428                             B->revision);
 429
 430     appendUndoItem(c);
 431     Q_ASSERT(undoState == undoStack.size());
 432
 433     // update revision numbers of the modified blocks.
 434     B->revision = (atBlockEnd && !atBlockStart)? oldRevision : revision;
 435     b = blocks.next(b);
 436     if (b) {
 437         B = blocks.fragment(b);
 438         B->revision = atBlockStart ? oldRevision : revision;
 439     }
 440
 441     if (formats.charFormat(charFormat).objectIndex() == -1)
 442         needsEnsureMaximumBlockCount = true;
 443
 444     endEditBlock();
 445     return fragment;
 446 }
 447
 448 int QTextDocumentPrivate::insertBlock(int pos, int blockFormat, int charFormat, QTextUndoCommand::Operation op)
 449 {
 450     return insertBlock(QChar::ParagraphSeparator, pos, blockFormat, charFormat, op);
 451 }
 452
 453 void QTextDocumentPrivate::insert(int pos, int strPos, int strLength, int format)
 454 {
 455     if (strLength <= 0)
 456         return;
 457
 458     Q_ASSERT(pos >= 0 && pos < fragments.length());
 459     Q_ASSERT(formats.format(format).isCharFormat());
 460
 461     insert_string(pos, strPos, strLength, format, QTextUndoCommand::MoveCursor);
 462     if (undoEnabled) {
 463         int b = blocks.findNode(pos);
 464         QTextBlockData *B = blocks.fragment(b);
 465
 466         QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::Inserted, (editBlock != 0),
 467                                 QTextUndoCommand::MoveCursor, format, strPos, pos, strLength,
 468                                 B->revision);
 469         appendUndoItem(c);
 470         B->revision = revision;
 471         Q_ASSERT(undoState == undoStack.size());
 472     }
 473     finishEdit();
 474 }
 475
 476 void QTextDocumentPrivate::insert(int pos, const QString &str, int format)
 477 {
 478     if (str.size() == 0)
 479         return;
 480
 481     Q_ASSERT(noBlockInString(str));
 482
 483     int strPos = text.length();
 484     text.append(str);
 485     insert(pos, strPos, str.length(), format);
 486 }
 487
 488 int QTextDocumentPrivate::remove_string(int pos, uint length, QTextUndoCommand::Operation op)
 489 {
 490     Q_ASSERT(pos >= 0);
 491     Q_ASSERT(blocks.length() == fragments.length());
 492     Q_ASSERT(blocks.length() >= pos+(int)length);
 493
 494     int b = blocks.findNode(pos);
 495     uint x = fragments.findNode(pos);
 496
 497     Q_ASSERT(blocks.size(b) > length);
 498     Q_ASSERT(x && fragments.position(x) == (uint)pos && fragments.size(x) == length);
 499     Q_ASSERT(noBlockInString(text.mid(fragments.fragment(x)->stringPosition, length)));
 500
 501     blocks.setSize(b, blocks.size(b)-length);
 502
 503     QTextFrame *frame = qobject_cast<QTextFrame *>(objectForFormat(fragments.fragment(x)->format));
 504     if (frame) {
 505         frame->d_func()->fragmentRemoved(text.at(fragments.fragment(x)->stringPosition), x);
 506         framesDirty = true;
 507     }
 508
 509     const int w = fragments.erase_single(x);
 510
 511     if (!undoEnabled)
 512         unreachableCharacterCount += length;
 513
 514     adjustDocumentChangesAndCursors(pos, -int(length), op);
 515
 516     return w;
 517 }
 518
 519 int QTextDocumentPrivate::remove_block(int pos, int *blockFormat, int command, QTextUndoCommand::Operation op)
 520 {
 521     Q_ASSERT(pos >= 0);
 522     Q_ASSERT(blocks.length() == fragments.length());
 523     Q_ASSERT(blocks.length() > pos);
 524
 525     int b = blocks.findNode(pos);
 526     uint x = fragments.findNode(pos);
 527
 528     Q_ASSERT(x && (int)fragments.position(x) == pos);
 529     Q_ASSERT(fragments.size(x) == 1);
 530     Q_ASSERT(isValidBlockSeparator(text.at(fragments.fragment(x)->stringPosition)));
 531     Q_ASSERT(b);
 532
 533     if (blocks.size(b) == 1 && command == QTextUndoCommand::BlockAdded) {
 534         Q_ASSERT((int)blocks.position(b) == pos);
 535 //      qDebug("removing empty block");
 536         // empty block remove the block itself
 537     } else {
 538         // non empty block, merge with next one into this block
 539 //      qDebug("merging block with next");
 540         int n = blocks.next(b);
 541         Q_ASSERT((int)blocks.position(n) == pos + 1);
 542         blocks.setSize(b, blocks.size(b) + blocks.size(n) - 1);
 543         b = n;
 544     }
 545     *blockFormat = blocks.fragment(b)->format;
 546
 547     QTextBlockGroup *group = qobject_cast<QTextBlockGroup *>(objectForFormat(blocks.fragment(b)->format));
 548     if (group)
 549         group->blockRemoved(QTextBlock(this, b));
 550
 551     QTextFrame *frame = qobject_cast<QTextFrame *>(objectForFormat(fragments.fragment(x)->format));
 552     if (frame) {
 553         frame->d_func()->fragmentRemoved(text.at(fragments.fragment(x)->stringPosition), x);
 554         framesDirty = true;
 555     }
 556
 557     blocks.erase_single(b);
 558     const int w = fragments.erase_single(x);
 559
 560     adjustDocumentChangesAndCursors(pos, -1, op);
 561
 562     return w;
 563 }
 564
 565 #if !defined(QT_NO_DEBUG)
 566 static bool isAncestorFrame(QTextFrame *possibleAncestor, QTextFrame *child)
 567 {
 568     while (child) {
 569         if (child == possibleAncestor)
 570             return true;
 571         child = child->parentFrame();
 572     }
 573     return false;
 574 }
 575 #endif
 576
 577 void QTextDocumentPrivate::move(int pos, int to, int length, QTextUndoCommand::Operation op)
 578 {
 579     Q_ASSERT(to <= fragments.length() && to <= pos);
 580     Q_ASSERT(pos >= 0 && pos+length <= fragments.length());
 581     Q_ASSERT(blocks.length() == fragments.length());
 582
 583     if (pos == to)
 584         return;
 585
 586     const bool needsInsert = to != -1;
 587
 588 #if !defined(QT_NO_DEBUG)
 589     const bool startAndEndInSameFrame = (frameAt(pos) == frameAt(pos + length - 1));
 590
 591     const bool endIsEndOfChildFrame = (isAncestorFrame(frameAt(pos), frameAt(pos + length - 1))
 592                                        && text.at(find(pos + length - 1)->stringPosition) == QTextEndOfFrame);
 593
 594     const bool startIsStartOfFrameAndEndIsEndOfFrameWithCommonParent
 595                = (text.at(find(pos)->stringPosition) == QTextBeginningOfFrame
 596                   && text.at(find(pos + length - 1)->stringPosition) == QTextEndOfFrame
 597                   && frameAt(pos)->parentFrame() == frameAt(pos + length - 1)->parentFrame());
 598
 599     const bool isFirstTableCell = (qobject_cast<QTextTable *>(frameAt(pos + length - 1))
 600                                   && frameAt(pos + length - 1)->parentFrame() == frameAt(pos));
 601
 602     Q_ASSERT(startAndEndInSameFrame || endIsEndOfChildFrame || startIsStartOfFrameAndEndIsEndOfFrameWithCommonParent || isFirstTableCell);
 603 #endif
 604
 605     split(pos);
 606     split(pos+length);
 607
 608     uint dst = needsInsert ? fragments.findNode(to) : 0;
 609     uint dstKey = needsInsert ? fragments.position(dst) : 0;
 610
 611     uint x = fragments.findNode(pos);
 612     uint end = fragments.findNode(pos+length);
 613
 614     uint w = 0;
 615     while (x != end) {
 616         uint n = fragments.next(x);
 617
 618         uint key = fragments.position(x);
 619         uint b = blocks.findNode(key+1);
 620         QTextBlockData *B = blocks.fragment(b);
 621         int blockRevision = B->revision;
 622
 623         QTextFragmentData *X = fragments.fragment(x);
 624         QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::Removed, (editBlock != 0),
 625                                 op, X->format, X->stringPosition, key, X->size_array[0],
 626                                 blockRevision);
 627         QT_INIT_TEXTUNDOCOMMAND(cInsert, QTextUndoCommand::Inserted, (editBlock != 0),
 628                                 op, X->format, X->stringPosition, dstKey, X->size_array[0],
 629                                 blockRevision);
 630
 631         if (key+1 != blocks.position(b)) {
 632 //          qDebug("remove_string from %d length %d", key, X->size_array[0]);
 633             Q_ASSERT(noBlockInString(text.mid(X->stringPosition, X->size_array[0])));
 634             w = remove_string(key, X->size_array[0], op);
 635
 636             if (needsInsert) {
 637                 insert_string(dstKey, X->stringPosition, X->size_array[0], X->format, op);
 638                 dstKey += X->size_array[0];
 639             }
 640         } else {
 641 //          qDebug("remove_block at %d", key);
 642             Q_ASSERT(X->size_array[0] == 1 && isValidBlockSeparator(text.at(X->stringPosition)));
 643             b = blocks.previous(b);
 644             B = 0;
 645             c.command = blocks.size(b) == 1 ? QTextUndoCommand::BlockDeleted : QTextUndoCommand::BlockRemoved;
 646             w = remove_block(key, &c.blockFormat, QTextUndoCommand::BlockAdded, op);
 647
 648             if (needsInsert) {
 649                 insert_block(dstKey++, X->stringPosition, X->format, c.blockFormat, op, QTextUndoCommand::BlockRemoved);
 650                 cInsert.command = blocks.size(b) == 1 ? QTextUndoCommand::BlockAdded : QTextUndoCommand::BlockInserted;
 651                 cInsert.blockFormat = c.blockFormat;
 652             }
 653         }
 654         appendUndoItem(c);
 655         if (B)
 656             B->revision = revision;
 657         x = n;
 658
 659         if (needsInsert)
 660             appendUndoItem(cInsert);
 661     }
 662     if (w)
 663         unite(w);
 664
 665     Q_ASSERT(blocks.length() == fragments.length());
 666
 667     if (!blockCursorAdjustment)
 668         finishEdit();
 669 }
 670
 671 void QTextDocumentPrivate::remove(int pos, int length, QTextUndoCommand::Operation op)
 672 {
 673     if (length == 0)
 674         return;
 675     blockCursorAdjustment = true;
 676     move(pos, -1, length, op);
 677     blockCursorAdjustment = false;
 678     foreach (QTextCursorPrivate *curs, cursors) {
 679         if (curs->adjustPosition(pos, -length, op) == QTextCursorPrivate::CursorMoved) {
 680             curs->changed = true;
 681         }
 682     }
 683     finishEdit();
 684 }
 685
 686 void QTextDocumentPrivate::setCharFormat(int pos, int length, const QTextCharFormat &newFormat, FormatChangeMode mode)
 687 {
 688     beginEditBlock();
 689
 690     Q_ASSERT(newFormat.isValid());
 691
 692     int newFormatIdx = -1;
 693     if (mode == SetFormatAndPreserveObjectIndices) {
 694         QTextCharFormat cleanFormat = newFormat;
 695         cleanFormat.clearProperty(QTextFormat::ObjectIndex);
 696         newFormatIdx = formats.indexForFormat(cleanFormat);
 697     } else if (mode == SetFormat) {
 698         newFormatIdx = formats.indexForFormat(newFormat);
 699     }
 700
 701     if (pos == -1) {
 702         if (mode == MergeFormat) {
 703             QTextFormat format = formats.format(initialBlockCharFormatIndex);
 704             format.merge(newFormat);
 705             initialBlockCharFormatIndex = formats.indexForFormat(format);
 706         } else if (mode == SetFormatAndPreserveObjectIndices
 707                    && formats.format(initialBlockCharFormatIndex).objectIndex() != -1) {
 708             QTextCharFormat f = newFormat;
 709             f.setObjectIndex(formats.format(initialBlockCharFormatIndex).objectIndex());
 710             initialBlockCharFormatIndex = formats.indexForFormat(f);
 711         } else {
 712             initialBlockCharFormatIndex = newFormatIdx;
 713         }
 714
 715         ++pos;
 716         --length;
 717     }
 718
 719     const int startPos = pos;
 720     const int endPos = pos + length;
 721
 722     split(startPos);
 723     split(endPos);
 724
 725     while (pos < endPos) {
 726         FragmentMap::Iterator it = fragments.find(pos);
 727         Q_ASSERT(!it.atEnd());
 728
 729         QTextFragmentData *fragment = it.value();
 730
 731         Q_ASSERT(formats.format(fragment->format).type() == QTextFormat::CharFormat);
 732
 733         int offset = pos - it.position();
 734         int length = qMin(endPos - pos, int(fragment->size_array[0] - offset));
 735         int oldFormat = fragment->format;
 736
 737         if (mode == MergeFormat) {
 738             QTextFormat format = formats.format(fragment->format);
 739             format.merge(newFormat);
 740             fragment->format = formats.indexForFormat(format);
 741         } else if (mode == SetFormatAndPreserveObjectIndices
 742                    && formats.format(oldFormat).objectIndex() != -1) {
 743             QTextCharFormat f = newFormat;
 744             f.setObjectIndex(formats.format(oldFormat).objectIndex());
 745             fragment->format = formats.indexForFormat(f);
 746         } else {
 747             fragment->format = newFormatIdx;
 748         }
 749
 750         QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::CharFormatChanged, true, QTextUndoCommand::MoveCursor, oldFormat,
 751                                 0, pos, length, 0);
 752         appendUndoItem(c);
 753
 754         pos += length;
 755         Q_ASSERT(pos == (int)(it.position() + fragment->size_array[0]) || pos >= endPos);
 756     }
 757
 758     int n = fragments.findNode(startPos - 1);
 759     if (n)
 760         unite(n);
 761
 762     n = fragments.findNode(endPos);
 763     if (n)
 764         unite(n);
 765
 766     QTextBlock blockIt = blocksFind(startPos);
 767     QTextBlock endIt = blocksFind(endPos);
 768     if (endIt.isValid())
 769         endIt = endIt.next();
 770     for (; blockIt.isValid() && blockIt != endIt; blockIt = blockIt.next())
 771         QTextDocumentPrivate::block(blockIt)->invalidate();
 772
 773     documentChange(startPos, length);
 774
 775     endEditBlock();
 776 }
 777
 778 void QTextDocumentPrivate::setBlockFormat(const QTextBlock &from, const QTextBlock &to,
 779                                      const QTextBlockFormat &newFormat, FormatChangeMode mode)
 780 {
 781     beginEditBlock();
 782
 783     Q_ASSERT(mode != SetFormatAndPreserveObjectIndices); // only implemented for setCharFormat
 784
 785     Q_ASSERT(newFormat.isValid());
 786
 787     int newFormatIdx = -1;
 788     if (mode == SetFormat)
 789         newFormatIdx = formats.indexForFormat(newFormat);
 790     QTextBlockGroup *group = qobject_cast<QTextBlockGroup *>(objectForFormat(newFormat));
 791
 792     QTextBlock it = from;
 793     QTextBlock end = to;
 794     if (end.isValid())
 795         end = end.next();
 796
 797     for (; it != end; it = it.next()) {
 798         int oldFormat = block(it)->format;
 799         QTextBlockFormat format = formats.blockFormat(oldFormat);
 800         QTextBlockGroup *oldGroup = qobject_cast<QTextBlockGroup *>(objectForFormat(format));
 801         if (mode == MergeFormat) {
 802             format.merge(newFormat);
 803             newFormatIdx = formats.indexForFormat(format);
 804             group = qobject_cast<QTextBlockGroup *>(objectForFormat(format));
 805         }
 806         block(it)->format = newFormatIdx;
 807
 808         block(it)->invalidate();
 809
 810         QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::BlockFormatChanged, true, QTextUndoCommand::MoveCursor, oldFormat,
 811                                 0, it.position(), 1, 0);
 812         appendUndoItem(c);
 813
 814         if (group != oldGroup) {
 815             if (oldGroup)
 816                 oldGroup->blockRemoved(it);
 817             if (group)
 818                 group->blockInserted(it);
 819         } else if (group) {
 820             group->blockFormatChanged(it);
 821         }
 822     }
 823
 824     documentChange(from.position(), to.position() + to.length() - from.position());
 825
 826     endEditBlock();
 827 }
 828
 829
 830 bool QTextDocumentPrivate::split(int pos)
 831 {
 832     uint x = fragments.findNode(pos);
 833     if (x) {
 834         int k = fragments.position(x);
 835 //          qDebug("found fragment with key %d, size_left=%d, size=%d to split at %d",
 836 //                k, (*it)->size_left[0], (*it)->size_array[0], pos);
 837         if (k != pos) {
 838             Q_ASSERT(k <= pos);
 839             // need to resize the first fragment and add a new one
 840             QTextFragmentData *X = fragments.fragment(x);
 841             int oldsize = X->size_array[0];
 842             fragments.setSize(x, pos-k);
 843             uint n = fragments.insert_single(pos, oldsize-(pos-k));
 844             X = fragments.fragment(x);
 845             QTextFragmentData *N = fragments.fragment(n);
 846             N->stringPosition = X->stringPosition + pos-k;
 847             N->format = X->format;
 848             return true;
 849         }
 850     }
 851     return false;
 852 }
 853
 854 bool QTextDocumentPrivate::unite(uint f)
 855 {
 856     uint n = fragments.next(f);
 857     if (!n)
 858         return false;
 859
 860     QTextFragmentData *ff = fragments.fragment(f);
 861     QTextFragmentData *nf = fragments.fragment(n);
 862
 863     if (nf->format == ff->format && (ff->stringPosition + (int)ff->size_array[0] == nf->stringPosition)) {
 864         if (isValidBlockSeparator(text.at(ff->stringPosition))
 865             || isValidBlockSeparator(text.at(nf->stringPosition)))
 866             return false;
 867
 868         fragments.setSize(f, ff->size_array[0] + nf->size_array[0]);
 869         fragments.erase_single(n);
 870         return true;
 871     }
 872     return false;
 873 }
 874
 875
 876 int QTextDocumentPrivate::undoRedo(bool undo)
 877 {
 878     PMDEBUG("%s, undoState=%d, undoStack size=%d", undo ? "undo:" : "redo:", undoState, undoStack.size());
 879     if (!undoEnabled || (undo && undoState == 0) || (!undo && undoState == undoStack.size()))
 880         return -1;
 881
 882     undoEnabled = false;
 883     beginEditBlock();
 884     int editPos = -1;
 885     int editLength = -1;
 886     while (1) {
 887         if (undo)
 888             --undoState;
 889         QTextUndoCommand &c = undoStack[undoState];
 890         int resetBlockRevision = c.pos;
 891
 892         switch(c.command) {
 893         case QTextUndoCommand::Inserted:
 894             remove(c.pos, c.length, (QTextUndoCommand::Operation)c.operation);
 895             PMDEBUG("   erase: from %d, length %d", c.pos, c.length);
 896             c.command = QTextUndoCommand::Removed;
 897             editPos = c.pos;
 898             editLength = 0;
 899             break;
 900         case QTextUndoCommand::Removed:
 901             PMDEBUG("   insert: format %d (from %d, length %d, strpos=%d)", c.format, c.pos, c.length, c.strPos);
 902             insert_string(c.pos, c.strPos, c.length, c.format, (QTextUndoCommand::Operation)c.operation);
 903             c.command = QTextUndoCommand::Inserted;
 904             if (editPos != (int)c.pos)
 905                 editLength = 0;
 906             editPos = c.pos;
 907             editLength += c.length;
 908             break;
 909         case QTextUndoCommand::BlockInserted:
 910         case QTextUndoCommand::BlockAdded:
 911             remove_block(c.pos, &c.blockFormat, c.command, (QTextUndoCommand::Operation)c.operation);
 912             PMDEBUG("   blockremove: from %d", c.pos);
 913             if (c.command == QTextUndoCommand::BlockInserted)
 914                 c.command = QTextUndoCommand::BlockRemoved;
 915             else
 916                 c.command = QTextUndoCommand::BlockDeleted;
 917             editPos = c.pos;
 918             editLength = 0;
 919             break;
 920         case QTextUndoCommand::BlockRemoved:
 921         case QTextUndoCommand::BlockDeleted:
 922             PMDEBUG("   blockinsert: charformat %d blockformat %d (pos %d, strpos=%d)", c.format, c.blockFormat, c.pos, c.strPos);
 923             insert_block(c.pos, c.strPos, c.format, c.blockFormat, (QTextUndoCommand::Operation)c.operation, c.command);
 924             resetBlockRevision += 1;
 925             if (c.command == QTextUndoCommand::BlockRemoved)
 926                 c.command = QTextUndoCommand::BlockInserted;
 927             else
 928                 c.command = QTextUndoCommand::BlockAdded;
 929             if (editPos != (int)c.pos)
 930                 editLength = 0;
 931             editPos = c.pos;
 932             editLength += 1;
 933             break;
 934         case QTextUndoCommand::CharFormatChanged: {
 935             resetBlockRevision = -1; // ## TODO
 936             PMDEBUG("   charFormat: format %d (from %d, length %d)", c.format, c.pos, c.length);
 937             FragmentIterator it = find(c.pos);
 938             Q_ASSERT(!it.atEnd());
 939
 940             int oldFormat = it.value()->format;
 941             setCharFormat(c.pos, c.length, formats.charFormat(c.format));
 942             c.format = oldFormat;
 943             if (editPos != (int)c.pos)
 944                 editLength = 0;
 945             editPos = c.pos;
 946             editLength += c.length;
 947             break;
 948         }
 949         case QTextUndoCommand::BlockFormatChanged: {
 950             resetBlockRevision = -1; // ## TODO
 951             PMDEBUG("   blockformat: format %d pos %d", c.format, c.pos);
 952             QTextBlock it = blocksFind(c.pos);
 953             Q_ASSERT(it.isValid());
 954
 955             int oldFormat = block(it)->format;
 956             block(it)->format = c.format;
 957             QTextBlockGroup *oldGroup = qobject_cast<QTextBlockGroup *>(objectForFormat(formats.blockFormat(oldFormat)));
 958             QTextBlockGroup *group = qobject_cast<QTextBlockGroup *>(objectForFormat(formats.blockFormat(c.format)));
 959             c.format = oldFormat;
 960             if (group != oldGroup) {
 961                 if (oldGroup)
 962                     oldGroup->blockRemoved(it);
 963                 if (group)
 964                     group->blockInserted(it);
 965             } else if (group) {
 966                 group->blockFormatChanged(it);
 967             }
 968             documentChange(it.position(), it.length());
 969             editPos = -1;
 970             break;
 971         }
 972         case QTextUndoCommand::GroupFormatChange: {
 973             resetBlockRevision = -1; // ## TODO
 974             PMDEBUG("   group format change");
 975             QTextObject *object = objectForIndex(c.objectIndex);
 976             int oldFormat = formats.objectFormatIndex(c.objectIndex);
 977             changeObjectFormat(object, c.format);
 978             c.format = oldFormat;
 979             editPos = -1;
 980             break;
 981         }
 982         case QTextUndoCommand::CursorMoved:
 983             editPos = c.pos;
 984             editLength = 0;
 985             break;
 986         case QTextUndoCommand::Custom:
 987             resetBlockRevision = -1; // ## TODO
 988             if (undo)
 989                 c.custom->undo();
 990             else
 991                 c.custom->redo();
 992             editPos = -1;
 993             break;
 994         default:
 995             Q_ASSERT(false);
 996         }
 997
 998         if (resetBlockRevision >= 0) {
 999             int b = blocks.findNode(resetBlockRevision);
1000             QTextBlockData *B = blocks.fragment(b);
1001             B->revision = c.revision;
1002         }
1003
1004         if (!undo)
1005             ++undoState;
1006
1007         bool inBlock = (
1008                 undoState > 0
1009                 && undoState < undoStack.size()
1010                 && undoStack[undoState].block_part
1011                 && undoStack[undoState-1].block_part
1012                 && !undoStack[undoState-1].block_end
1013                 );
1014         if (!inBlock)
1015             break;
1016     }
1017     undoEnabled = true;
1018
1019     int newCursorPos = -1;
1020
1021     if (editPos >=0)
1022         newCursorPos = editPos + editLength;
1023     else if (docChangeFrom >= 0)
1024         newCursorPos= qMin(docChangeFrom + docChangeLength, length() - 1);
1025
1026     endEditBlock();
1027     emitUndoAvailable(isUndoAvailable());
1028     emitRedoAvailable(isRedoAvailable());
1029
1030     return newCursorPos;
1031 }
1032
1033 /*!
1034     Appends a custom undo \a item to the undo stack.
1035 */
1036 void QTextDocumentPrivate::appendUndoItem(QAbstractUndoItem *item)
1037 {
1038     if (!undoEnabled) {
1039         delete item;
1040         return;
1041     }
1042
1043     QTextUndoCommand c;
1044     c.command = QTextUndoCommand::Custom;
1045     c.block_part = editBlock != 0;
1046     c.block_end = 0;
1047     c.operation = QTextUndoCommand::MoveCursor;
1048     c.format = 0;
1049     c.strPos = 0;
1050     c.pos = 0;
1051     c.blockFormat = 0;
1052
1053     c.custom = item;
1054     appendUndoItem(c);
1055 }
1056
1057 void QTextDocumentPrivate::appendUndoItem(const QTextUndoCommand &c)
1058 {
1059     PMDEBUG("appendUndoItem, command=%d enabled=%d", c.command, undoEnabled);
1060     if (!undoEnabled)
1061         return;
1062     if (undoState < undoStack.size())
1063         clearUndoRedoStacks(QTextDocument::RedoStack);
1064
1065     if (editBlock != 0 && editBlockCursorPosition >= 0) { // we had a beginEditBlock() with a cursor position
1066         if (c.pos != (quint32) editBlockCursorPosition) { // and that cursor position is different from the command
1067             // generate a CursorMoved undo item
1068             QT_INIT_TEXTUNDOCOMMAND(cc, QTextUndoCommand::CursorMoved, true, QTextUndoCommand::MoveCursor,
1069                                     0, 0, editBlockCursorPosition, 0, 0);
1070             undoStack.append(cc);
1071             undoState++;
1072             editBlockCursorPosition = -1;
1073         }
1074     }
1075
1076
1077     if (!undoStack.isEmpty() && modified) {
1078         QTextUndoCommand &last = undoStack[undoState - 1];
1079
1080         if ( (last.block_part && c.block_part && !last.block_end) // part of the same block => can merge
1081             || (!c.block_part && !last.block_part)) {  // two single undo items => can merge
1082
1083             if (last.tryMerge(c))
1084                 return;
1085         }
1086     }
1087     if (modifiedState > undoState)
1088         modifiedState = -1;
1089     undoStack.append(c);
1090     undoState++;
1091     emitUndoAvailable(true);
1092     emitRedoAvailable(false);
1093
1094     if (!c.block_part)
1095         emit document()->undoCommandAdded();
1096 }
1097
1098 void QTextDocumentPrivate::clearUndoRedoStacks(QTextDocument::Stacks stacksToClear,
1099                                                bool emitSignals)
1100 {
1101     bool undoCommandsAvailable = undoState != 0;
1102     bool redoCommandsAvailable = undoState != undoStack.size();
1103     if (stacksToClear == QTextDocument::UndoStack && undoCommandsAvailable) {
1104         for (int i = 0; i < undoState; ++i) {
1105             QTextUndoCommand c = undoStack[undoState];
1106             if (c.command & QTextUndoCommand::Custom)
1107                 delete c.custom;
1108         }
1109         undoStack.remove(0, undoState);
1110         undoStack.resize(undoStack.size() - undoState);
1111         undoState = 0;
1112         if (emitSignals)
1113             emitUndoAvailable(false);
1114     } else if (stacksToClear == QTextDocument::RedoStack
1115                && redoCommandsAvailable) {
1116         for (int i = undoState; i < undoStack.size(); ++i) {
1117             QTextUndoCommand c = undoStack[i];
1118             if (c.command & QTextUndoCommand::Custom)
1119                 delete c.custom;
1120         }
1121         undoStack.resize(undoState);
1122         if (emitSignals)
1123             emitRedoAvailable(false);
1124     } else if (stacksToClear == QTextDocument::UndoAndRedoStacks
1125                && !undoStack.isEmpty()) {
1126         for (int i = 0; i < undoStack.size(); ++i) {
1127             QTextUndoCommand c = undoStack[i];
1128             if (c.command & QTextUndoCommand::Custom)
1129                 delete c.custom;
1130         }
1131         undoState = 0;
1132         undoStack.resize(0);
1133         if (emitSignals && undoCommandsAvailable)
1134             emitUndoAvailable(false);
1135         if (emitSignals && redoCommandsAvailable)
1136             emitRedoAvailable(false);
1137     }
1138 }
1139
1140 void QTextDocumentPrivate::emitUndoAvailable(bool available)
1141 {
1142     if (available != wasUndoAvailable) {
1143         Q_Q(QTextDocument);
1144         emit q->undoAvailable(available);
1145         wasUndoAvailable = available;
1146     }
1147 }
1148
1149 void QTextDocumentPrivate::emitRedoAvailable(bool available)
1150 {
1151     if (available != wasRedoAvailable) {
1152         Q_Q(QTextDocument);
1153         emit q->redoAvailable(available);
1154         wasRedoAvailable = available;
1155     }
1156 }
1157
1158 void QTextDocumentPrivate::enableUndoRedo(bool enable)
1159 {
1160     if (enable && maximumBlockCount > 0)
1161         return;
1162
1163     if (!enable) {
1164         undoState = 0;
1165         clearUndoRedoStacks(QTextDocument::RedoStack);
1166         emitUndoAvailable(false);
1167         emitRedoAvailable(false);
1168     }
1169     modifiedState = modified ? -1 : undoState;
1170     undoEnabled = enable;
1171     if (!undoEnabled)
1172         compressPieceTable();
1173 }
1174
1175 void QTextDocumentPrivate::joinPreviousEditBlock()
1176 {
1177     beginEditBlock();
1178
1179     if (undoEnabled && undoState)
1180         undoStack[undoState - 1].block_end = false;
1181 }
1182
1183 void QTextDocumentPrivate::endEditBlock()
1184 {
1185     Q_ASSERT(editBlock > 0);
1186     if (--editBlock)
1187         return;
1188
1189     if (undoEnabled && undoState > 0) {
1190         const bool wasBlocking = !undoStack[undoState - 1].block_end;
1191         if (undoStack[undoState - 1].block_part) {
1192             undoStack[undoState - 1].block_end = true;
1193             if (wasBlocking)
1194                 emit document()->undoCommandAdded();
1195         }
1196     }
1197
1198     editBlockCursorPosition = -1;
1199
1200     finishEdit();
1201 }
1202
1203 void QTextDocumentPrivate::finishEdit()
1204 {
1205     Q_Q(QTextDocument);
1206
1207     if (editBlock)
1208         return;
1209
1210     if (framesDirty)
1211         scan_frames(docChangeFrom, docChangeOldLength, docChangeLength);
1212
1213     if (lout && docChangeFrom >= 0) {
1214         if (!inContentsChange) {
1215             inContentsChange = true;
1216             emit q->contentsChange(docChangeFrom, docChangeOldLength, docChangeLength);
1217             inContentsChange = false;
1218         }
1219         lout->documentChanged(docChangeFrom, docChangeOldLength, docChangeLength);
1220     }
1221
1222     docChangeFrom = -1;
1223
1224     if (needsEnsureMaximumBlockCount) {
1225         needsEnsureMaximumBlockCount = false;
1226         if (ensureMaximumBlockCount()) {
1227             // if ensureMaximumBlockCount() returns true
1228             // it will have called endEditBlock() and
1229             // compressPieceTable() itself, so we return here
1230             // to prevent getting two contentsChanged emits
1231             return;
1232         }
1233     }
1234
1235     QList<QTextCursor> changedCursors;
1236     foreach (QTextCursorPrivate *curs, cursors) {
1237         if (curs->changed) {
1238             curs->changed = false;
1239             changedCursors.append(QTextCursor(curs));
1240         }
1241     }
1242     foreach (const QTextCursor &cursor, changedCursors)
1243         emit q->cursorPositionChanged(cursor);
1244
1245     contentsChanged();
1246
1247     if (blocks.numNodes() != lastBlockCount) {
1248         lastBlockCount = blocks.numNodes();
1249         emit q->blockCountChanged(lastBlockCount);
1250     }
1251
1252     if (!undoEnabled && unreachableCharacterCount)
1253         compressPieceTable();
1254 }
1255
1256 void QTextDocumentPrivate::documentChange(int from, int length)
1257 {
1258 //     qDebug("QTextDocumentPrivate::documentChange: from=%d,length=%d", from, length);
1259     if (docChangeFrom < 0) {
1260         docChangeFrom = from;
1261         docChangeOldLength = length;
1262         docChangeLength = length;
1263         return;
1264     }
1265     int start = qMin(from, docChangeFrom);
1266     int end = qMax(from + length, docChangeFrom + docChangeLength);
1267     int diff = qMax(0, end - start - docChangeLength);
1268     docChangeFrom = start;
1269     docChangeOldLength += diff;
1270     docChangeLength += diff;
1271 }
1272
1273 /*
1274     adjustDocumentChangesAndCursors is called whenever there is an insert or remove of characters.
1275     param from is the cursor position in the document
1276     param addedOrRemoved is the amount of characters added or removed.  A negative number means characters are removed.
1277
1278     The function stores information to be emitted when finishEdit() is called.
1279 */
1280 void QTextDocumentPrivate::adjustDocumentChangesAndCursors(int from, int addedOrRemoved, QTextUndoCommand::Operation op)
1281 {
1282     if (!editBlock)
1283         ++revision;
1284
1285     if (blockCursorAdjustment)  {
1286         ; // postpone, will be called again from QTextDocumentPrivate::remove()
1287     } else {
1288         foreach (QTextCursorPrivate *curs, cursors) {
1289             if (curs->adjustPosition(from, addedOrRemoved, op) == QTextCursorPrivate::CursorMoved) {
1290                 curs->changed = true;
1291             }
1292         }
1293     }
1294
1295 //     qDebug("QTextDocumentPrivate::adjustDocumentChanges: from=%d,addedOrRemoved=%d", from, addedOrRemoved);
1296     if (docChangeFrom < 0) {
1297         docChangeFrom = from;
1298         if (addedOrRemoved > 0) {
1299             docChangeOldLength = 0;
1300             docChangeLength = addedOrRemoved;
1301         } else {
1302             docChangeOldLength = -addedOrRemoved;
1303             docChangeLength = 0;
1304         }
1305 //         qDebug("adjustDocumentChanges:");
1306 //         qDebug("    -> %d %d %d", docChangeFrom, docChangeOldLength, docChangeLength);
1307         return;
1308     }
1309
1310     // have to merge the new change with the already existing one.
1311     int added = qMax(0, addedOrRemoved);
1312     int removed = qMax(0, -addedOrRemoved);
1313
1314     int diff = 0;
1315     if(from + removed < docChangeFrom)
1316         diff = docChangeFrom - from - removed;
1317     else if(from > docChangeFrom + docChangeLength)
1318         diff = from - (docChangeFrom + docChangeLength);
1319
1320     int overlap_start = qMax(from, docChangeFrom);
1321     int overlap_end = qMin(from + removed, docChangeFrom + docChangeLength);
1322     int removedInside = qMax(0, overlap_end - overlap_start);
1323     removed -= removedInside;
1324
1325 //     qDebug("adjustDocumentChanges: from=%d, addedOrRemoved=%d, diff=%d, removedInside=%d", from, addedOrRemoved, diff, removedInside);
1326     docChangeFrom = qMin(docChangeFrom, from);
1327     docChangeOldLength += removed + diff;
1328     docChangeLength += added - removedInside + diff;
1329 //     qDebug("    -> %d %d %d", docChangeFrom, docChangeOldLength, docChangeLength);
1330
1331 }
1332
1333
1334 QString QTextDocumentPrivate::plainText() const
1335 {
1336     QString result;
1337     result.resize(length());
1338     const QChar *text_unicode = text.unicode();
1339     QChar *data = result.data();
1340     for (QTextDocumentPrivate::FragmentIterator it = begin(); it != end(); ++it) {
1341         const QTextFragmentData *f = *it;
1342         ::memcpy(data, text_unicode + f->stringPosition, f->size_array[0] * sizeof(QChar));
1343         data += f->size_array[0];
1344     }
1345     // remove trailing block separator
1346     result.chop(1);
1347     return result;
1348 }
1349
1350 int QTextDocumentPrivate::blockCharFormatIndex(int node) const
1351 {
1352     int pos = blocks.position(node);
1353     if (pos == 0)
1354         return initialBlockCharFormatIndex;
1355
1356     return fragments.find(pos - 1)->format;
1357 }
1358
1359 int QTextDocumentPrivate::nextCursorPosition(int position, QTextLayout::CursorMode mode) const
1360 {
1361     if (position == length()-1)
1362         return position;
1363
1364     QTextBlock it = blocksFind(position);
1365     int start = it.position();
1366     int end = start + it.length() - 1;
1367     if (position == end)
1368         return end + 1;
1369
1370     return it.layout()->nextCursorPosition(position-start, mode) + start;
1371 }
1372
1373 int QTextDocumentPrivate::previousCursorPosition(int position, QTextLayout::CursorMode mode) const
1374 {
1375     if (position == 0)
1376         return position;
1377
1378     QTextBlock it = blocksFind(position);
1379     int start = it.position();
1380     if (position == start)
1381         return start - 1;
1382
1383     return it.layout()->previousCursorPosition(position-start, mode) + start;
1384 }
1385
1386 int QTextDocumentPrivate::leftCursorPosition(int position) const
1387 {
1388     QTextBlock it = blocksFind(position);
1389     int start = it.position();
1390     return it.layout()->leftCursorPosition(position-start) + start;
1391 }
1392
1393 int QTextDocumentPrivate::rightCursorPosition(int position) const
1394 {
1395     QTextBlock it = blocksFind(position);
1396     int start = it.position();
1397     return it.layout()->rightCursorPosition(position-start) + start;
1398 }
1399
1400 void QTextDocumentPrivate::changeObjectFormat(QTextObject *obj, int format)
1401 {
1402     beginEditBlock();
1403     int objectIndex = obj->objectIndex();
1404     int oldFormatIndex = formats.objectFormatIndex(objectIndex);
1405     formats.setObjectFormatIndex(objectIndex, format);
1406
1407     QTextBlockGroup *b = qobject_cast<QTextBlockGroup *>(obj);
1408     if (b) {
1409         b->d_func()->markBlocksDirty();
1410     }
1411     QTextFrame *f = qobject_cast<QTextFrame *>(obj);
1412     if (f)
1413         documentChange(f->firstPosition(), f->lastPosition() - f->firstPosition());
1414
1415     QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::GroupFormatChange, (editBlock != 0), QTextUndoCommand::MoveCursor, oldFormatIndex,
1416                             0, 0, obj->d_func()->objectIndex, 0);
1417     appendUndoItem(c);
1418
1419     endEditBlock();
1420 }
1421
1422 static QTextFrame *findChildFrame(QTextFrame *f, int pos)
1423 {
1424     /* Binary search for frame at pos */
1425     const QList<QTextFrame *> children = f->childFrames();
1426     int first = 0;
1427     int last = children.size() - 1;
1428     while (first <= last) {
1429         int mid = (first + last) / 2;
1430         QTextFrame *c = children.at(mid);
1431         if (pos > c->lastPosition())
1432             first = mid + 1;
1433         else if (pos < c->firstPosition())
1434             last = mid - 1;
1435         else
1436             return c;
1437     }
1438     return 0;
1439 }
1440
1441 QTextFrame *QTextDocumentPrivate::rootFrame() const
1442 {
1443     if (!rtFrame) {
1444         QTextFrameFormat defaultRootFrameFormat;
1445         defaultRootFrameFormat.setMargin(documentMargin);
1446         rtFrame = qobject_cast<QTextFrame *>(const_cast<QTextDocumentPrivate *>(this)->createObject(defaultRootFrameFormat));
1447     }
1448     return rtFrame;
1449 }
1450
1451 QTextFrame *QTextDocumentPrivate::frameAt(int pos) const
1452 {
1453     QTextFrame *f = rootFrame();
1454
1455     while (1) {
1456         QTextFrame *c = findChildFrame(f, pos);
1457         if (!c)
1458             return f;
1459         f = c;
1460     }
1461 }
1462
1463 void QTextDocumentPrivate::clearFrame(QTextFrame *f)
1464 {
1465     for (int i = 0; i < f->d_func()->childFrames.count(); ++i)
1466         clearFrame(f->d_func()->childFrames.at(i));
1467     f->d_func()->childFrames.clear();
1468     f->d_func()->parentFrame = 0;
1469 }
1470
1471 void QTextDocumentPrivate::scan_frames(int pos, int charsRemoved, int charsAdded)
1472 {
1473     // ###### optimize
1474     Q_UNUSED(pos);
1475     Q_UNUSED(charsRemoved);
1476     Q_UNUSED(charsAdded);
1477
1478     QTextFrame *f = rootFrame();
1479     clearFrame(f);
1480
1481     for (FragmentIterator it = begin(); it != end(); ++it) {
1482         // QTextFormat fmt = formats.format(it->format);
1483         QTextFrame *frame = qobject_cast<QTextFrame *>(objectForFormat(it->format));
1484         if (!frame)
1485             continue;
1486
1487         Q_ASSERT(it.size() == 1);
1488         QChar ch = text.at(it->stringPosition);
1489
1490         if (ch == QTextBeginningOfFrame) {
1491             if (f != frame) {
1492                 // f == frame happens for tables
1493                 Q_ASSERT(frame->d_func()->fragment_start == it.n || frame->d_func()->fragment_start == 0);
1494                 frame->d_func()->parentFrame = f;
1495                 f->d_func()->childFrames.append(frame);
1496                 f = frame;
1497             }
1498         } else if (ch == QTextEndOfFrame) {
1499             Q_ASSERT(f == frame);
1500             Q_ASSERT(frame->d_func()->fragment_end == it.n || frame->d_func()->fragment_end == 0);
1501             f = frame->d_func()->parentFrame;
1502         } else if (ch == QChar::ObjectReplacementCharacter) {
1503             Q_ASSERT(f != frame);
1504             Q_ASSERT(frame->d_func()->fragment_start == it.n || frame->d_func()->fragment_start == 0);
1505             Q_ASSERT(frame->d_func()->fragment_end == it.n || frame->d_func()->fragment_end == 0);
1506             frame->d_func()->parentFrame = f;
1507             f->d_func()->childFrames.append(frame);
1508         } else {
1509             Q_ASSERT(false);
1510         }
1511     }
1512     Q_ASSERT(f == rtFrame);
1513     framesDirty = false;
1514 }
1515
1516 void QTextDocumentPrivate::insert_frame(QTextFrame *f)
1517 {
1518     int start = f->firstPosition();
1519     int end = f->lastPosition();
1520     QTextFrame *parent = frameAt(start-1);
1521     Q_ASSERT(parent == frameAt(end+1));
1522
1523     if (start != end) {
1524         // iterator over the parent and move all children contained in my frame to myself
1525         for (int i = 0; i < parent->d_func()->childFrames.size(); ++i) {
1526             QTextFrame *c = parent->d_func()->childFrames.at(i);
1527             if (start < c->firstPosition() && end > c->lastPosition()) {
1528                 parent->d_func()->childFrames.removeAt(i);
1529                 f->d_func()->childFrames.append(c);
1530                 c->d_func()->parentFrame = f;
1531             }
1532         }
1533     }
1534     // insert at the correct position
1535     int i = 0;
1536     for (; i < parent->d_func()->childFrames.size(); ++i) {
1537         QTextFrame *c = parent->d_func()->childFrames.at(i);
1538         if (c->firstPosition() > end)
1539             break;
1540     }
1541     parent->d_func()->childFrames.insert(i, f);
1542     f->d_func()->parentFrame = parent;
1543 }
1544
1545 QTextFrame *QTextDocumentPrivate::insertFrame(int start, int end, const QTextFrameFormat &format)
1546 {
1547     Q_ASSERT(start >= 0 && start < length());
1548     Q_ASSERT(end >= 0 && end < length());
1549     Q_ASSERT(start <= end || end == -1);
1550
1551     if (start != end && frameAt(start) != frameAt(end))
1552         return 0;
1553
1554     beginEditBlock();
1555
1556     QTextFrame *frame = qobject_cast<QTextFrame *>(createObject(format));
1557     Q_ASSERT(frame);
1558
1559     // #### using the default block and char format below might be wrong
1560     int idx = formats.indexForFormat(QTextBlockFormat());
1561     QTextCharFormat cfmt;
1562     cfmt.setObjectIndex(frame->objectIndex());
1563     int charIdx = formats.indexForFormat(cfmt);
1564
1565     insertBlock(QTextBeginningOfFrame, start, idx, charIdx, QTextUndoCommand::MoveCursor);
1566     insertBlock(QTextEndOfFrame, ++end, idx, charIdx, QTextUndoCommand::KeepCursor);
1567
1568     frame->d_func()->fragment_start = find(start).n;
1569     frame->d_func()->fragment_end = find(end).n;
1570
1571     insert_frame(frame);
1572
1573     endEditBlock();
1574
1575     return frame;
1576 }
1577
1578 void QTextDocumentPrivate::removeFrame(QTextFrame *frame)
1579 {
1580     QTextFrame *parent = frame->d_func()->parentFrame;
1581     if (!parent)
1582         return;
1583
1584     int start = frame->firstPosition();
1585     int end = frame->lastPosition();
1586     Q_ASSERT(end >= start);
1587
1588     beginEditBlock();
1589
1590     // remove already removes the frames from the tree
1591     remove(end, 1);
1592     remove(start-1, 1);
1593
1594     endEditBlock();
1595 }
1596
1597 QTextObject *QTextDocumentPrivate::objectForIndex(int objectIndex) const
1598 {
1599     if (objectIndex < 0)
1600         return 0;
1601
1602     QTextObject *object = objects.value(objectIndex, 0);
1603     if (!object) {
1604         QTextDocumentPrivate *that = const_cast<QTextDocumentPrivate *>(this);
1605         QTextFormat fmt = formats.objectFormat(objectIndex);
1606         object = that->createObject(fmt, objectIndex);
1607     }
1608     return object;
1609 }
1610
1611 QTextObject *QTextDocumentPrivate::objectForFormat(int formatIndex) const
1612 {
1613     int objectIndex = formats.format(formatIndex).objectIndex();
1614     return objectForIndex(objectIndex);
1615 }
1616
1617 QTextObject *QTextDocumentPrivate::objectForFormat(const QTextFormat &f) const
1618 {
1619     return objectForIndex(f.objectIndex());
1620 }
1621
1622 QTextObject *QTextDocumentPrivate::createObject(const QTextFormat &f, int objectIndex)
1623 {
1624     QTextObject *obj = document()->createObject(f);
1625
1626     if (obj) {
1627         obj->d_func()->objectIndex = objectIndex == -1 ? formats.createObjectIndex(f) : objectIndex;
1628         objects[obj->d_func()->objectIndex] = obj;
1629     }
1630
1631     return obj;
1632 }
1633
1634 void QTextDocumentPrivate::deleteObject(QTextObject *object)
1635 {
1636     const int objIdx = object->d_func()->objectIndex;
1637     objects.remove(objIdx);
1638     delete object;
1639 }
1640
1641 void QTextDocumentPrivate::contentsChanged()
1642 {
1643     Q_Q(QTextDocument);
1644     if (editBlock)
1645         return;
1646
1647     bool m = undoEnabled ? (modifiedState != undoState) : true;
1648     if (modified != m) {
1649         modified = m;
1650         emit q->modificationChanged(modified);
1651     }
1652
1653     emit q->contentsChanged();
1654 }
1655
1656 void QTextDocumentPrivate::compressPieceTable()
1657 {
1658     if (undoEnabled)
1659         return;
1660
1661     const uint garbageCollectionThreshold = 96 * 1024; // bytes
1662
1663     //qDebug() << "unreachable bytes:" << unreachableCharacterCount * sizeof(QChar) << " -- limit" << garbageCollectionThreshold << "text size =" << text.size() << "capacity:" << text.capacity();
1664
1665     bool compressTable = unreachableCharacterCount * sizeof(QChar) > garbageCollectionThreshold
1666                          && text.size() >= text.capacity() * 0.9;
1667     if (!compressTable)
1668         return;
1669
1670     QString newText;
1671     newText.resize(text.size());
1672     QChar *newTextPtr = newText.data();
1673     int newLen = 0;
1674
1675     for (FragmentMap::Iterator it = fragments.begin(); !it.atEnd(); ++it) {
1676         memcpy(newTextPtr, text.constData() + it->stringPosition, it->size_array[0] * sizeof(QChar));
1677         it->stringPosition = newLen;
1678         newTextPtr += it->size_array[0];
1679         newLen += it->size_array[0];
1680     }
1681
1682     newText.resize(newLen);
1683     newText.squeeze();
1684     //qDebug() << "removed" << text.size() - newText.size() << "characters";
1685     text = newText;
1686     unreachableCharacterCount = 0;
1687 }
1688
1689 void QTextDocumentPrivate::setModified(bool m)
1690 {
1691     Q_Q(QTextDocument);
1692     if (m == modified)
1693         return;
1694
1695     modified = m;
1696     if (!modified)
1697         modifiedState = undoState;
1698     else
1699         modifiedState = -1;
1700
1701     emit q->modificationChanged(modified);
1702 }
1703
1704 bool QTextDocumentPrivate::ensureMaximumBlockCount()
1705 {
1706     if (maximumBlockCount <= 0)
1707         return false;
1708     if (blocks.numNodes() <= maximumBlockCount)
1709         return false;
1710
1711     beginEditBlock();
1712
1713     const int blocksToRemove = blocks.numNodes() - maximumBlockCount;
1714     QTextCursor cursor(this, 0);
1715     cursor.movePosition(QTextCursor::NextBlock, QTextCursor::KeepAnchor, blocksToRemove);
1716
1717     unreachableCharacterCount += cursor.selectionEnd() - cursor.selectionStart();
1718
1719     // preserve the char format of the paragraph that is to become the new first one
1720     QTextCharFormat charFmt = cursor.blockCharFormat();
1721     cursor.removeSelectedText();
1722     cursor.setBlockCharFormat(charFmt);
1723
1724     endEditBlock();
1725
1726     compressPieceTable();
1727
1728     return true;
1729 }
1730
1731 /// This method is called from QTextTable when it is about to remove a table-cell to allow cursors to update their selection.
1732 void QTextDocumentPrivate::aboutToRemoveCell(int from, int to)
1733 {
1734     Q_ASSERT(from <= to);
1735     foreach (QTextCursorPrivate *curs, cursors)
1736         curs->aboutToRemoveCell(from, to);
1737 }
1738
1739 QT_END_NAMESPACE