src/gui/text/qtextdocument_p.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtGui module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  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, quint32(a5), quint32(a6), { int(a7) }, quint32(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(QChar ch)
 130 {
 131     return ch == QChar::ParagraphSeparator
 132         || ch == QTextBeginningOfFrame
 133         || ch == QTextEndOfFrame;
 134 }
 135
 136 #if !defined(QT_NO_DEBUG) || defined(QT_FORCE_ASSERTS)
 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(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         blocks.fragment(b)->userState = blocks.fragment(n)->userState;
 544         b = n;
 545     }
 546     *blockFormat = blocks.fragment(b)->format;
 547
 548     QTextBlockGroup *group = qobject_cast<QTextBlockGroup *>(objectForFormat(blocks.fragment(b)->format));
 549     if (group)
 550         group->blockRemoved(QTextBlock(this, b));
 551
 552     QTextFrame *frame = qobject_cast<QTextFrame *>(objectForFormat(fragments.fragment(x)->format));
 553     if (frame) {
 554         frame->d_func()->fragmentRemoved(text.at(fragments.fragment(x)->stringPosition), x);
 555         framesDirty = true;
 556     }
 557
 558     blocks.erase_single(b);
 559     const int w = fragments.erase_single(x);
 560
 561     adjustDocumentChangesAndCursors(pos, -1, op);
 562
 563     return w;
 564 }
 565
 566 #if !defined(QT_NO_DEBUG)
 567 static bool isAncestorFrame(QTextFrame *possibleAncestor, QTextFrame *child)
 568 {
 569     while (child) {
 570         if (child == possibleAncestor)
 571             return true;
 572         child = child->parentFrame();
 573     }
 574     return false;
 575 }
 576 #endif
 577
 578 void QTextDocumentPrivate::move(int pos, int to, int length, QTextUndoCommand::Operation op)
 579 {
 580     Q_ASSERT(to <= fragments.length() && to <= pos);
 581     Q_ASSERT(pos >= 0 && pos+length <= fragments.length());
 582     Q_ASSERT(blocks.length() == fragments.length());
 583
 584     if (pos == to)
 585         return;
 586
 587     const bool needsInsert = to != -1;
 588
 589 #if !defined(QT_NO_DEBUG)
 590     const bool startAndEndInSameFrame = (frameAt(pos) == frameAt(pos + length - 1));
 591
 592     const bool endIsEndOfChildFrame = (isAncestorFrame(frameAt(pos), frameAt(pos + length - 1))
 593                                        && text.at(find(pos + length - 1)->stringPosition) == QTextEndOfFrame);
 594
 595     const bool startIsStartOfFrameAndEndIsEndOfFrameWithCommonParent
 596                = (text.at(find(pos)->stringPosition) == QTextBeginningOfFrame
 597                   && text.at(find(pos + length - 1)->stringPosition) == QTextEndOfFrame
 598                   && frameAt(pos)->parentFrame() == frameAt(pos + length - 1)->parentFrame());
 599
 600     const bool isFirstTableCell = (qobject_cast<QTextTable *>(frameAt(pos + length - 1))
 601                                   && frameAt(pos + length - 1)->parentFrame() == frameAt(pos));
 602
 603     Q_ASSERT(startAndEndInSameFrame || endIsEndOfChildFrame || startIsStartOfFrameAndEndIsEndOfFrameWithCommonParent || isFirstTableCell);
 604 #endif
 605
 606     split(pos);
 607     split(pos+length);
 608
 609     uint dst = needsInsert ? fragments.findNode(to) : 0;
 610     uint dstKey = needsInsert ? fragments.position(dst) : 0;
 611
 612     uint x = fragments.findNode(pos);
 613     uint end = fragments.findNode(pos+length);
 614
 615     uint w = 0;
 616     while (x != end) {
 617         uint n = fragments.next(x);
 618
 619         uint key = fragments.position(x);
 620         uint b = blocks.findNode(key+1);
 621         QTextBlockData *B = blocks.fragment(b);
 622         int blockRevision = B->revision;
 623
 624         QTextFragmentData *X = fragments.fragment(x);
 625         QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::Removed, (editBlock != 0),
 626                                 op, X->format, X->stringPosition, key, X->size_array[0],
 627                                 blockRevision);
 628         QT_INIT_TEXTUNDOCOMMAND(cInsert, QTextUndoCommand::Inserted, (editBlock != 0),
 629                                 op, X->format, X->stringPosition, dstKey, X->size_array[0],
 630                                 blockRevision);
 631
 632         if (key+1 != blocks.position(b)) {
 633 //          qDebug("remove_string from %d length %d", key, X->size_array[0]);
 634             Q_ASSERT(noBlockInString(text.mid(X->stringPosition, X->size_array[0])));
 635             w = remove_string(key, X->size_array[0], op);
 636
 637             if (needsInsert) {
 638                 insert_string(dstKey, X->stringPosition, X->size_array[0], X->format, op);
 639                 dstKey += X->size_array[0];
 640             }
 641         } else {
 642 //          qDebug("remove_block at %d", key);
 643             Q_ASSERT(X->size_array[0] == 1 && isValidBlockSeparator(text.at(X->stringPosition)));
 644             b = blocks.previous(b);
 645             B = 0;
 646             c.command = blocks.size(b) == 1 ? QTextUndoCommand::BlockDeleted : QTextUndoCommand::BlockRemoved;
 647             w = remove_block(key, &c.blockFormat, QTextUndoCommand::BlockAdded, op);
 648
 649             if (needsInsert) {
 650                 insert_block(dstKey++, X->stringPosition, X->format, c.blockFormat, op, QTextUndoCommand::BlockRemoved);
 651                 cInsert.command = blocks.size(b) == 1 ? QTextUndoCommand::BlockAdded : QTextUndoCommand::BlockInserted;
 652                 cInsert.blockFormat = c.blockFormat;
 653             }
 654         }
 655         appendUndoItem(c);
 656         if (B)
 657             B->revision = revision;
 658         x = n;
 659
 660         if (needsInsert)
 661             appendUndoItem(cInsert);
 662     }
 663     if (w)
 664         unite(w);
 665
 666     Q_ASSERT(blocks.length() == fragments.length());
 667
 668     if (!blockCursorAdjustment)
 669         finishEdit();
 670 }
 671
 672 void QTextDocumentPrivate::remove(int pos, int length, QTextUndoCommand::Operation op)
 673 {
 674     if (length == 0)
 675         return;
 676     blockCursorAdjustment = true;
 677     move(pos, -1, length, op);
 678     blockCursorAdjustment = false;
 679     foreach (QTextCursorPrivate *curs, cursors) {
 680         if (curs->adjustPosition(pos, -length, op) == QTextCursorPrivate::CursorMoved) {
 681             curs->changed = true;
 682         }
 683     }
 684     finishEdit();
 685 }
 686
 687 void QTextDocumentPrivate::setCharFormat(int pos, int length, const QTextCharFormat &newFormat, FormatChangeMode mode)
 688 {
 689     beginEditBlock();
 690
 691     Q_ASSERT(newFormat.isValid());
 692
 693     int newFormatIdx = -1;
 694     if (mode == SetFormatAndPreserveObjectIndices) {
 695         QTextCharFormat cleanFormat = newFormat;
 696         cleanFormat.clearProperty(QTextFormat::ObjectIndex);
 697         newFormatIdx = formats.indexForFormat(cleanFormat);
 698     } else if (mode == SetFormat) {
 699         newFormatIdx = formats.indexForFormat(newFormat);
 700     }
 701
 702     if (pos == -1) {
 703         if (mode == MergeFormat) {
 704             QTextFormat format = formats.format(initialBlockCharFormatIndex);
 705             format.merge(newFormat);
 706             initialBlockCharFormatIndex = formats.indexForFormat(format);
 707         } else if (mode == SetFormatAndPreserveObjectIndices
 708                    && formats.format(initialBlockCharFormatIndex).objectIndex() != -1) {
 709             QTextCharFormat f = newFormat;
 710             f.setObjectIndex(formats.format(initialBlockCharFormatIndex).objectIndex());
 711             initialBlockCharFormatIndex = formats.indexForFormat(f);
 712         } else {
 713             initialBlockCharFormatIndex = newFormatIdx;
 714         }
 715
 716         ++pos;
 717         --length;
 718     }
 719
 720     const int startPos = pos;
 721     const int endPos = pos + length;
 722
 723     split(startPos);
 724     split(endPos);
 725
 726     while (pos < endPos) {
 727         FragmentMap::Iterator it = fragments.find(pos);
 728         Q_ASSERT(!it.atEnd());
 729
 730         QTextFragmentData *fragment = it.value();
 731
 732         Q_ASSERT(formats.format(fragment->format).type() == QTextFormat::CharFormat);
 733
 734         int offset = pos - it.position();
 735         int length = qMin(endPos - pos, int(fragment->size_array[0] - offset));
 736         int oldFormat = fragment->format;
 737
 738         if (mode == MergeFormat) {
 739             QTextFormat format = formats.format(fragment->format);
 740             format.merge(newFormat);
 741             fragment->format = formats.indexForFormat(format);
 742         } else if (mode == SetFormatAndPreserveObjectIndices
 743                    && formats.format(oldFormat).objectIndex() != -1) {
 744             QTextCharFormat f = newFormat;
 745             f.setObjectIndex(formats.format(oldFormat).objectIndex());
 746             fragment->format = formats.indexForFormat(f);
 747         } else {
 748             fragment->format = newFormatIdx;
 749         }
 750
 751         QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::CharFormatChanged, true, QTextUndoCommand::MoveCursor, oldFormat,
 752                                 0, pos, length, 0);
 753         appendUndoItem(c);
 754
 755         pos += length;
 756         Q_ASSERT(pos == (int)(it.position() + fragment->size_array[0]) || pos >= endPos);
 757     }
 758
 759     int n = fragments.findNode(startPos - 1);
 760     if (n)
 761         unite(n);
 762
 763     n = fragments.findNode(endPos);
 764     if (n)
 765         unite(n);
 766
 767     QTextBlock blockIt = blocksFind(startPos);
 768     QTextBlock endIt = blocksFind(endPos);
 769     if (endIt.isValid())
 770         endIt = endIt.next();
 771     for (; blockIt.isValid() && blockIt != endIt; blockIt = blockIt.next())
 772         QTextDocumentPrivate::block(blockIt)->invalidate();
 773
 774     documentChange(startPos, length);
 775
 776     endEditBlock();
 777 }
 778
 779 void QTextDocumentPrivate::setBlockFormat(const QTextBlock &from, const QTextBlock &to,
 780                                      const QTextBlockFormat &newFormat, FormatChangeMode mode)
 781 {
 782     beginEditBlock();
 783
 784     Q_ASSERT(mode != SetFormatAndPreserveObjectIndices); // only implemented for setCharFormat
 785
 786     Q_ASSERT(newFormat.isValid());
 787
 788     int newFormatIdx = -1;
 789     if (mode == SetFormat)
 790         newFormatIdx = formats.indexForFormat(newFormat);
 791     QTextBlockGroup *group = qobject_cast<QTextBlockGroup *>(objectForFormat(newFormat));
 792
 793     QTextBlock it = from;
 794     QTextBlock end = to;
 795     if (end.isValid())
 796         end = end.next();
 797
 798     for (; it != end; it = it.next()) {
 799         int oldFormat = block(it)->format;
 800         QTextBlockFormat format = formats.blockFormat(oldFormat);
 801         QTextBlockGroup *oldGroup = qobject_cast<QTextBlockGroup *>(objectForFormat(format));
 802         if (mode == MergeFormat) {
 803             format.merge(newFormat);
 804             newFormatIdx = formats.indexForFormat(format);
 805             group = qobject_cast<QTextBlockGroup *>(objectForFormat(format));
 806         }
 807         block(it)->format = newFormatIdx;
 808
 809         block(it)->invalidate();
 810
 811         QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::BlockFormatChanged, true, QTextUndoCommand::MoveCursor, oldFormat,
 812                                 0, it.position(), 1, 0);
 813         appendUndoItem(c);
 814
 815         if (group != oldGroup) {
 816             if (oldGroup)
 817                 oldGroup->blockRemoved(it);
 818             if (group)
 819                 group->blockInserted(it);
 820         } else if (group) {
 821             group->blockFormatChanged(it);
 822         }
 823     }
 824
 825     documentChange(from.position(), to.position() + to.length() - from.position());
 826
 827     endEditBlock();
 828 }
 829
 830
 831 bool QTextDocumentPrivate::split(int pos)
 832 {
 833     uint x = fragments.findNode(pos);
 834     if (x) {
 835         int k = fragments.position(x);
 836 //          qDebug("found fragment with key %d, size_left=%d, size=%d to split at %d",
 837 //                k, (*it)->size_left[0], (*it)->size_array[0], pos);
 838         if (k != pos) {
 839             Q_ASSERT(k <= pos);
 840             // need to resize the first fragment and add a new one
 841             QTextFragmentData *X = fragments.fragment(x);
 842             int oldsize = X->size_array[0];
 843             fragments.setSize(x, pos-k);
 844             uint n = fragments.insert_single(pos, oldsize-(pos-k));
 845             X = fragments.fragment(x);
 846             QTextFragmentData *N = fragments.fragment(n);
 847             N->stringPosition = X->stringPosition + pos-k;
 848             N->format = X->format;
 849             return true;
 850         }
 851     }
 852     return false;
 853 }
 854
 855 bool QTextDocumentPrivate::unite(uint f)
 856 {
 857     uint n = fragments.next(f);
 858     if (!n)
 859         return false;
 860
 861     QTextFragmentData *ff = fragments.fragment(f);
 862     QTextFragmentData *nf = fragments.fragment(n);
 863
 864     if (nf->format == ff->format && (ff->stringPosition + (int)ff->size_array[0] == nf->stringPosition)) {
 865         if (isValidBlockSeparator(text.at(ff->stringPosition))
 866             || isValidBlockSeparator(text.at(nf->stringPosition)))
 867             return false;
 868
 869         fragments.setSize(f, ff->size_array[0] + nf->size_array[0]);
 870         fragments.erase_single(n);
 871         return true;
 872     }
 873     return false;
 874 }
 875
 876
 877 int QTextDocumentPrivate::undoRedo(bool undo)
 878 {
 879     PMDEBUG("%s, undoState=%d, undoStack size=%d", undo ? "undo:" : "redo:", undoState, undoStack.size());
 880     if (!undoEnabled || (undo && undoState == 0) || (!undo && undoState == undoStack.size()))
 881         return -1;
 882
 883     undoEnabled = false;
 884     beginEditBlock();
 885     int editPos = -1;
 886     int editLength = -1;
 887     while (1) {
 888         if (undo)
 889             --undoState;
 890         QTextUndoCommand &c = undoStack[undoState];
 891         int resetBlockRevision = c.pos;
 892
 893         switch(c.command) {
 894         case QTextUndoCommand::Inserted:
 895             remove(c.pos, c.length, (QTextUndoCommand::Operation)c.operation);
 896             PMDEBUG("   erase: from %d, length %d", c.pos, c.length);
 897             c.command = QTextUndoCommand::Removed;
 898             editPos = c.pos;
 899             editLength = 0;
 900             break;
 901         case QTextUndoCommand::Removed:
 902             PMDEBUG("   insert: format %d (from %d, length %d, strpos=%d)", c.format, c.pos, c.length, c.strPos);
 903             insert_string(c.pos, c.strPos, c.length, c.format, (QTextUndoCommand::Operation)c.operation);
 904             c.command = QTextUndoCommand::Inserted;
 905             if (editPos != (int)c.pos)
 906                 editLength = 0;
 907             editPos = c.pos;
 908             editLength += c.length;
 909             break;
 910         case QTextUndoCommand::BlockInserted:
 911         case QTextUndoCommand::BlockAdded:
 912             remove_block(c.pos, &c.blockFormat, c.command, (QTextUndoCommand::Operation)c.operation);
 913             PMDEBUG("   blockremove: from %d", c.pos);
 914             if (c.command == QTextUndoCommand::BlockInserted)
 915                 c.command = QTextUndoCommand::BlockRemoved;
 916             else
 917                 c.command = QTextUndoCommand::BlockDeleted;
 918             editPos = c.pos;
 919             editLength = 0;
 920             break;
 921         case QTextUndoCommand::BlockRemoved:
 922         case QTextUndoCommand::BlockDeleted:
 923             PMDEBUG("   blockinsert: charformat %d blockformat %d (pos %d, strpos=%d)", c.format, c.blockFormat, c.pos, c.strPos);
 924             insert_block(c.pos, c.strPos, c.format, c.blockFormat, (QTextUndoCommand::Operation)c.operation, c.command);
 925             resetBlockRevision += 1;
 926             if (c.command == QTextUndoCommand::BlockRemoved)
 927                 c.command = QTextUndoCommand::BlockInserted;
 928             else
 929                 c.command = QTextUndoCommand::BlockAdded;
 930             if (editPos != (int)c.pos)
 931                 editLength = 0;
 932             editPos = c.pos;
 933             editLength += 1;
 934             break;
 935         case QTextUndoCommand::CharFormatChanged: {
 936             resetBlockRevision = -1; // ## TODO
 937             PMDEBUG("   charFormat: format %d (from %d, length %d)", c.format, c.pos, c.length);
 938             FragmentIterator it = find(c.pos);
 939             Q_ASSERT(!it.atEnd());
 940
 941             int oldFormat = it.value()->format;
 942             setCharFormat(c.pos, c.length, formats.charFormat(c.format));
 943             c.format = oldFormat;
 944             if (editPos != (int)c.pos)
 945                 editLength = 0;
 946             editPos = c.pos;
 947             editLength += c.length;
 948             break;
 949         }
 950         case QTextUndoCommand::BlockFormatChanged: {
 951             resetBlockRevision = -1; // ## TODO
 952             PMDEBUG("   blockformat: format %d pos %d", c.format, c.pos);
 953             QTextBlock it = blocksFind(c.pos);
 954             Q_ASSERT(it.isValid());
 955
 956             int oldFormat = block(it)->format;
 957             block(it)->format = c.format;
 958             QTextBlockGroup *oldGroup = qobject_cast<QTextBlockGroup *>(objectForFormat(formats.blockFormat(oldFormat)));
 959             QTextBlockGroup *group = qobject_cast<QTextBlockGroup *>(objectForFormat(formats.blockFormat(c.format)));
 960             c.format = oldFormat;
 961             if (group != oldGroup) {
 962                 if (oldGroup)
 963                     oldGroup->blockRemoved(it);
 964                 if (group)
 965                     group->blockInserted(it);
 966             } else if (group) {
 967                 group->blockFormatChanged(it);
 968             }
 969             documentChange(it.position(), it.length());
 970             editPos = -1;
 971             break;
 972         }
 973         case QTextUndoCommand::GroupFormatChange: {
 974             resetBlockRevision = -1; // ## TODO
 975             PMDEBUG("   group format change");
 976             QTextObject *object = objectForIndex(c.objectIndex);
 977             int oldFormat = formats.objectFormatIndex(c.objectIndex);
 978             changeObjectFormat(object, c.format);
 979             c.format = oldFormat;
 980             editPos = -1;
 981             break;
 982         }
 983         case QTextUndoCommand::CursorMoved:
 984             editPos = c.pos;
 985             editLength = 0;
 986             break;
 987         case QTextUndoCommand::Custom:
 988             resetBlockRevision = -1; // ## TODO
 989             if (undo)
 990                 c.custom->undo();
 991             else
 992                 c.custom->redo();
 993             editPos = -1;
 994             break;
 995         default:
 996             Q_ASSERT(false);
 997         }
 998
 999         if (resetBlockRevision >= 0) {
1000             int b = blocks.findNode(resetBlockRevision);
1001             QTextBlockData *B = blocks.fragment(b);
1002             B->revision = c.revision;
1003         }
1004
1005         if (!undo)
1006             ++undoState;
1007
1008         bool inBlock = (
1009                 undoState > 0
1010                 && undoState < undoStack.size()
1011                 && undoStack[undoState].block_part
1012                 && undoStack[undoState-1].block_part
1013                 && !undoStack[undoState-1].block_end
1014                 );
1015         if (!inBlock)
1016             break;
1017     }
1018     undoEnabled = true;
1019
1020     int newCursorPos = -1;
1021
1022     if (editPos >=0)
1023         newCursorPos = editPos + editLength;
1024     else if (docChangeFrom >= 0)
1025         newCursorPos= qMin(docChangeFrom + docChangeLength, length() - 1);
1026
1027     endEditBlock();
1028     emitUndoAvailable(isUndoAvailable());
1029     emitRedoAvailable(isRedoAvailable());
1030
1031     return newCursorPos;
1032 }
1033
1034 /*!
1035     Appends a custom undo \a item to the undo stack.
1036 */
1037 void QTextDocumentPrivate::appendUndoItem(QAbstractUndoItem *item)
1038 {
1039     if (!undoEnabled) {
1040         delete item;
1041         return;
1042     }
1043
1044     QTextUndoCommand c;
1045     c.command = QTextUndoCommand::Custom;
1046     c.block_part = editBlock != 0;
1047     c.block_end = 0;
1048     c.operation = QTextUndoCommand::MoveCursor;
1049     c.format = 0;
1050     c.strPos = 0;
1051     c.pos = 0;
1052     c.blockFormat = 0;
1053
1054     c.custom = item;
1055     appendUndoItem(c);
1056 }
1057
1058 void QTextDocumentPrivate::appendUndoItem(const QTextUndoCommand &c)
1059 {
1060     PMDEBUG("appendUndoItem, command=%d enabled=%d", c.command, undoEnabled);
1061     if (!undoEnabled)
1062         return;
1063     if (undoState < undoStack.size())
1064         clearUndoRedoStacks(QTextDocument::RedoStack);
1065
1066     if (editBlock != 0 && editBlockCursorPosition >= 0) { // we had a beginEditBlock() with a cursor position
1067         if (c.pos != (quint32) editBlockCursorPosition) { // and that cursor position is different from the command
1068             // generate a CursorMoved undo item
1069             QT_INIT_TEXTUNDOCOMMAND(cc, QTextUndoCommand::CursorMoved, true, QTextUndoCommand::MoveCursor,
1070                                     0, 0, editBlockCursorPosition, 0, 0);
1071             undoStack.append(cc);
1072             undoState++;
1073             editBlockCursorPosition = -1;
1074         }
1075     }
1076
1077
1078     if (!undoStack.isEmpty() && modified) {
1079         QTextUndoCommand &last = undoStack[undoState - 1];
1080
1081         if ( (last.block_part && c.block_part && !last.block_end) // part of the same block => can merge
1082             || (!c.block_part && !last.block_part)) {  // two single undo items => can merge
1083
1084             if (last.tryMerge(c))
1085                 return;
1086         }
1087     }
1088     if (modifiedState > undoState)
1089         modifiedState = -1;
1090     undoStack.append(c);
1091     undoState++;
1092     emitUndoAvailable(true);
1093     emitRedoAvailable(false);
1094
1095     if (!c.block_part)
1096         emit document()->undoCommandAdded();
1097 }
1098
1099 void QTextDocumentPrivate::clearUndoRedoStacks(QTextDocument::Stacks stacksToClear,
1100                                                bool emitSignals)
1101 {
1102     bool undoCommandsAvailable = undoState != 0;
1103     bool redoCommandsAvailable = undoState != undoStack.size();
1104     if (stacksToClear == QTextDocument::UndoStack && undoCommandsAvailable) {
1105         for (int i = 0; i < undoState; ++i) {
1106             QTextUndoCommand c = undoStack[undoState];
1107             if (c.command & QTextUndoCommand::Custom)
1108                 delete c.custom;
1109         }
1110         undoStack.remove(0, undoState);
1111         undoStack.resize(undoStack.size() - undoState);
1112         undoState = 0;
1113         if (emitSignals)
1114             emitUndoAvailable(false);
1115     } else if (stacksToClear == QTextDocument::RedoStack
1116                && redoCommandsAvailable) {
1117         for (int i = undoState; i < undoStack.size(); ++i) {
1118             QTextUndoCommand c = undoStack[i];
1119             if (c.command & QTextUndoCommand::Custom)
1120                 delete c.custom;
1121         }
1122         undoStack.resize(undoState);
1123         if (emitSignals)
1124             emitRedoAvailable(false);
1125     } else if (stacksToClear == QTextDocument::UndoAndRedoStacks
1126                && !undoStack.isEmpty()) {
1127         for (int i = 0; i < undoStack.size(); ++i) {
1128             QTextUndoCommand c = undoStack[i];
1129             if (c.command & QTextUndoCommand::Custom)
1130                 delete c.custom;
1131         }
1132         undoState = 0;
1133         undoStack.resize(0);
1134         if (emitSignals && undoCommandsAvailable)
1135             emitUndoAvailable(false);
1136         if (emitSignals && redoCommandsAvailable)
1137             emitRedoAvailable(false);
1138     }
1139 }
1140
1141 void QTextDocumentPrivate::emitUndoAvailable(bool available)
1142 {
1143     if (available != wasUndoAvailable) {
1144         Q_Q(QTextDocument);
1145         emit q->undoAvailable(available);
1146         wasUndoAvailable = available;
1147     }
1148 }
1149
1150 void QTextDocumentPrivate::emitRedoAvailable(bool available)
1151 {
1152     if (available != wasRedoAvailable) {
1153         Q_Q(QTextDocument);
1154         emit q->redoAvailable(available);
1155         wasRedoAvailable = available;
1156     }
1157 }
1158
1159 void QTextDocumentPrivate::enableUndoRedo(bool enable)
1160 {
1161     if (enable && maximumBlockCount > 0)
1162         return;
1163
1164     if (!enable) {
1165         undoState = 0;
1166         clearUndoRedoStacks(QTextDocument::RedoStack);
1167         emitUndoAvailable(false);
1168         emitRedoAvailable(false);
1169     }
1170     modifiedState = modified ? -1 : undoState;
1171     undoEnabled = enable;
1172     if (!undoEnabled)
1173         compressPieceTable();
1174 }
1175
1176 void QTextDocumentPrivate::joinPreviousEditBlock()
1177 {
1178     beginEditBlock();
1179
1180     if (undoEnabled && undoState)
1181         undoStack[undoState - 1].block_end = false;
1182 }
1183
1184 void QTextDocumentPrivate::endEditBlock()
1185 {
1186     Q_ASSERT(editBlock > 0);
1187     if (--editBlock)
1188         return;
1189
1190     if (undoEnabled && undoState > 0) {
1191         const bool wasBlocking = !undoStack[undoState - 1].block_end;
1192         if (undoStack[undoState - 1].block_part) {
1193             undoStack[undoState - 1].block_end = true;
1194             if (wasBlocking)
1195                 emit document()->undoCommandAdded();
1196         }
1197     }
1198
1199     editBlockCursorPosition = -1;
1200
1201     finishEdit();
1202 }
1203
1204 void QTextDocumentPrivate::finishEdit()
1205 {
1206     Q_Q(QTextDocument);
1207
1208     if (editBlock)
1209         return;
1210
1211     if (framesDirty)
1212         scan_frames(docChangeFrom, docChangeOldLength, docChangeLength);
1213
1214     if (lout && docChangeFrom >= 0) {
1215         if (!inContentsChange) {
1216             inContentsChange = true;
1217             emit q->contentsChange(docChangeFrom, docChangeOldLength, docChangeLength);
1218             inContentsChange = false;
1219         }
1220         lout->documentChanged(docChangeFrom, docChangeOldLength, docChangeLength);
1221     }
1222
1223     docChangeFrom = -1;
1224
1225     if (needsEnsureMaximumBlockCount) {
1226         needsEnsureMaximumBlockCount = false;
1227         if (ensureMaximumBlockCount()) {
1228             // if ensureMaximumBlockCount() returns true
1229             // it will have called endEditBlock() and
1230             // compressPieceTable() itself, so we return here
1231             // to prevent getting two contentsChanged emits
1232             return;
1233         }
1234     }
1235
1236     QList<QTextCursor> changedCursors;
1237     foreach (QTextCursorPrivate *curs, cursors) {
1238         if (curs->changed) {
1239             curs->changed = false;
1240             changedCursors.append(QTextCursor(curs));
1241         }
1242     }
1243     foreach (const QTextCursor &cursor, changedCursors)
1244         emit q->cursorPositionChanged(cursor);
1245
1246     contentsChanged();
1247
1248     if (blocks.numNodes() != lastBlockCount) {
1249         lastBlockCount = blocks.numNodes();
1250         emit q->blockCountChanged(lastBlockCount);
1251     }
1252
1253     if (!undoEnabled && unreachableCharacterCount)
1254         compressPieceTable();
1255 }
1256
1257 void QTextDocumentPrivate::documentChange(int from, int length)
1258 {
1259 //     qDebug("QTextDocumentPrivate::documentChange: from=%d,length=%d", from, length);
1260     if (docChangeFrom < 0) {
1261         docChangeFrom = from;
1262         docChangeOldLength = length;
1263         docChangeLength = length;
1264         return;
1265     }
1266     int start = qMin(from, docChangeFrom);
1267     int end = qMax(from + length, docChangeFrom + docChangeLength);
1268     int diff = qMax(0, end - start - docChangeLength);
1269     docChangeFrom = start;
1270     docChangeOldLength += diff;
1271     docChangeLength += diff;
1272 }
1273
1274 /*
1275     adjustDocumentChangesAndCursors is called whenever there is an insert or remove of characters.
1276     param from is the cursor position in the document
1277     param addedOrRemoved is the amount of characters added or removed.  A negative number means characters are removed.
1278
1279     The function stores information to be emitted when finishEdit() is called.
1280 */
1281 void QTextDocumentPrivate::adjustDocumentChangesAndCursors(int from, int addedOrRemoved, QTextUndoCommand::Operation op)
1282 {
1283     if (!editBlock)
1284         ++revision;
1285
1286     if (blockCursorAdjustment)  {
1287         ; // postpone, will be called again from QTextDocumentPrivate::remove()
1288     } else {
1289         foreach (QTextCursorPrivate *curs, cursors) {
1290             if (curs->adjustPosition(from, addedOrRemoved, op) == QTextCursorPrivate::CursorMoved) {
1291                 curs->changed = true;
1292             }
1293         }
1294     }
1295
1296 //     qDebug("QTextDocumentPrivate::adjustDocumentChanges: from=%d,addedOrRemoved=%d", from, addedOrRemoved);
1297     if (docChangeFrom < 0) {
1298         docChangeFrom = from;
1299         if (addedOrRemoved > 0) {
1300             docChangeOldLength = 0;
1301             docChangeLength = addedOrRemoved;
1302         } else {
1303             docChangeOldLength = -addedOrRemoved;
1304             docChangeLength = 0;
1305         }
1306 //         qDebug("adjustDocumentChanges:");
1307 //         qDebug("    -> %d %d %d", docChangeFrom, docChangeOldLength, docChangeLength);
1308         return;
1309     }
1310
1311     // have to merge the new change with the already existing one.
1312     int added = qMax(0, addedOrRemoved);
1313     int removed = qMax(0, -addedOrRemoved);
1314
1315     int diff = 0;
1316     if(from + removed < docChangeFrom)
1317         diff = docChangeFrom - from - removed;
1318     else if(from > docChangeFrom + docChangeLength)
1319         diff = from - (docChangeFrom + docChangeLength);
1320
1321     int overlap_start = qMax(from, docChangeFrom);
1322     int overlap_end = qMin(from + removed, docChangeFrom + docChangeLength);
1323     int removedInside = qMax(0, overlap_end - overlap_start);
1324     removed -= removedInside;
1325
1326 //     qDebug("adjustDocumentChanges: from=%d, addedOrRemoved=%d, diff=%d, removedInside=%d", from, addedOrRemoved, diff, removedInside);
1327     docChangeFrom = qMin(docChangeFrom, from);
1328     docChangeOldLength += removed + diff;
1329     docChangeLength += added - removedInside + diff;
1330 //     qDebug("    -> %d %d %d", docChangeFrom, docChangeOldLength, docChangeLength);
1331
1332 }
1333
1334
1335 QString QTextDocumentPrivate::plainText() const
1336 {
1337     QString result;
1338     result.resize(length());
1339     const QChar *text_unicode = text.unicode();
1340     QChar *data = result.data();
1341     for (QTextDocumentPrivate::FragmentIterator it = begin(); it != end(); ++it) {
1342         const QTextFragmentData *f = *it;
1343         ::memcpy(data, text_unicode + f->stringPosition, f->size_array[0] * sizeof(QChar));
1344         data += f->size_array[0];
1345     }
1346     // remove trailing block separator
1347     result.chop(1);
1348     return result;
1349 }
1350
1351 int QTextDocumentPrivate::blockCharFormatIndex(int node) const
1352 {
1353     int pos = blocks.position(node);
1354     if (pos == 0)
1355         return initialBlockCharFormatIndex;
1356
1357     return fragments.find(pos - 1)->format;
1358 }
1359
1360 int QTextDocumentPrivate::nextCursorPosition(int position, QTextLayout::CursorMode mode) const
1361 {
1362     if (position == length()-1)
1363         return position;
1364
1365     QTextBlock it = blocksFind(position);
1366     int start = it.position();
1367     int end = start + it.length() - 1;
1368     if (position == end)
1369         return end + 1;
1370
1371     return it.layout()->nextCursorPosition(position-start, mode) + start;
1372 }
1373
1374 int QTextDocumentPrivate::previousCursorPosition(int position, QTextLayout::CursorMode mode) const
1375 {
1376     if (position == 0)
1377         return position;
1378
1379     QTextBlock it = blocksFind(position);
1380     int start = it.position();
1381     if (position == start)
1382         return start - 1;
1383
1384     return it.layout()->previousCursorPosition(position-start, mode) + start;
1385 }
1386
1387 int QTextDocumentPrivate::leftCursorPosition(int position) const
1388 {
1389     QTextBlock it = blocksFind(position);
1390     int start = it.position();
1391     return it.layout()->leftCursorPosition(position-start) + start;
1392 }
1393
1394 int QTextDocumentPrivate::rightCursorPosition(int position) const
1395 {
1396     QTextBlock it = blocksFind(position);
1397     int start = it.position();
1398     return it.layout()->rightCursorPosition(position-start) + start;
1399 }
1400
1401 void QTextDocumentPrivate::changeObjectFormat(QTextObject *obj, int format)
1402 {
1403     beginEditBlock();
1404     int objectIndex = obj->objectIndex();
1405     int oldFormatIndex = formats.objectFormatIndex(objectIndex);
1406     formats.setObjectFormatIndex(objectIndex, format);
1407
1408     QTextBlockGroup *b = qobject_cast<QTextBlockGroup *>(obj);
1409     if (b) {
1410         b->d_func()->markBlocksDirty();
1411     }
1412     QTextFrame *f = qobject_cast<QTextFrame *>(obj);
1413     if (f)
1414         documentChange(f->firstPosition(), f->lastPosition() - f->firstPosition());
1415
1416     QT_INIT_TEXTUNDOCOMMAND(c, QTextUndoCommand::GroupFormatChange, (editBlock != 0), QTextUndoCommand::MoveCursor, oldFormatIndex,
1417                             0, 0, obj->d_func()->objectIndex, 0);
1418     appendUndoItem(c);
1419
1420     endEditBlock();
1421 }
1422
1423 static QTextFrame *findChildFrame(QTextFrame *f, int pos)
1424 {
1425     /* Binary search for frame at pos */
1426     const QList<QTextFrame *> children = f->childFrames();
1427     int first = 0;
1428     int last = children.size() - 1;
1429     while (first <= last) {
1430         int mid = (first + last) / 2;
1431         QTextFrame *c = children.at(mid);
1432         if (pos > c->lastPosition())
1433             first = mid + 1;
1434         else if (pos < c->firstPosition())
1435             last = mid - 1;
1436         else
1437             return c;
1438     }
1439     return 0;
1440 }
1441
1442 QTextFrame *QTextDocumentPrivate::rootFrame() const
1443 {
1444     if (!rtFrame) {
1445         QTextFrameFormat defaultRootFrameFormat;
1446         defaultRootFrameFormat.setMargin(documentMargin);
1447         rtFrame = qobject_cast<QTextFrame *>(const_cast<QTextDocumentPrivate *>(this)->createObject(defaultRootFrameFormat));
1448     }
1449     return rtFrame;
1450 }
1451
1452 QTextFrame *QTextDocumentPrivate::frameAt(int pos) const
1453 {
1454     QTextFrame *f = rootFrame();
1455
1456     while (1) {
1457         QTextFrame *c = findChildFrame(f, pos);
1458         if (!c)
1459             return f;
1460         f = c;
1461     }
1462 }
1463
1464 void QTextDocumentPrivate::clearFrame(QTextFrame *f)
1465 {
1466     for (int i = 0; i < f->d_func()->childFrames.count(); ++i)
1467         clearFrame(f->d_func()->childFrames.at(i));
1468     f->d_func()->childFrames.clear();
1469     f->d_func()->parentFrame = 0;
1470 }
1471
1472 void QTextDocumentPrivate::scan_frames(int pos, int charsRemoved, int charsAdded)
1473 {
1474     // ###### optimize
1475     Q_UNUSED(pos);
1476     Q_UNUSED(charsRemoved);
1477     Q_UNUSED(charsAdded);
1478
1479     QTextFrame *f = rootFrame();
1480     clearFrame(f);
1481
1482     for (FragmentIterator it = begin(); it != end(); ++it) {
1483         // QTextFormat fmt = formats.format(it->format);
1484         QTextFrame *frame = qobject_cast<QTextFrame *>(objectForFormat(it->format));
1485         if (!frame)
1486             continue;
1487
1488         Q_ASSERT(it.size() == 1);
1489         QChar ch = text.at(it->stringPosition);
1490
1491         if (ch == QTextBeginningOfFrame) {
1492             if (f != frame) {
1493                 // f == frame happens for tables
1494                 Q_ASSERT(frame->d_func()->fragment_start == it.n || frame->d_func()->fragment_start == 0);
1495                 frame->d_func()->parentFrame = f;
1496                 f->d_func()->childFrames.append(frame);
1497                 f = frame;
1498             }
1499         } else if (ch == QTextEndOfFrame) {
1500             Q_ASSERT(f == frame);
1501             Q_ASSERT(frame->d_func()->fragment_end == it.n || frame->d_func()->fragment_end == 0);
1502             f = frame->d_func()->parentFrame;
1503         } else if (ch == QChar::ObjectReplacementCharacter) {
1504             Q_ASSERT(f != frame);
1505             Q_ASSERT(frame->d_func()->fragment_start == it.n || frame->d_func()->fragment_start == 0);
1506             Q_ASSERT(frame->d_func()->fragment_end == it.n || frame->d_func()->fragment_end == 0);
1507             frame->d_func()->parentFrame = f;
1508             f->d_func()->childFrames.append(frame);
1509         } else {
1510             Q_ASSERT(false);
1511         }
1512     }
1513     Q_ASSERT(f == rtFrame);
1514     framesDirty = false;
1515 }
1516
1517 void QTextDocumentPrivate::insert_frame(QTextFrame *f)
1518 {
1519     int start = f->firstPosition();
1520     int end = f->lastPosition();
1521     QTextFrame *parent = frameAt(start-1);
1522     Q_ASSERT(parent == frameAt(end+1));
1523
1524     if (start != end) {
1525         // iterator over the parent and move all children contained in my frame to myself
1526         for (int i = 0; i < parent->d_func()->childFrames.size(); ++i) {
1527             QTextFrame *c = parent->d_func()->childFrames.at(i);
1528             if (start < c->firstPosition() && end > c->lastPosition()) {
1529                 parent->d_func()->childFrames.removeAt(i);
1530                 f->d_func()->childFrames.append(c);
1531                 c->d_func()->parentFrame = f;
1532             }
1533         }
1534     }
1535     // insert at the correct position
1536     int i = 0;
1537     for (; i < parent->d_func()->childFrames.size(); ++i) {
1538         QTextFrame *c = parent->d_func()->childFrames.at(i);
1539         if (c->firstPosition() > end)
1540             break;
1541     }
1542     parent->d_func()->childFrames.insert(i, f);
1543     f->d_func()->parentFrame = parent;
1544 }
1545
1546 QTextFrame *QTextDocumentPrivate::insertFrame(int start, int end, const QTextFrameFormat &format)
1547 {
1548     Q_ASSERT(start >= 0 && start < length());
1549     Q_ASSERT(end >= 0 && end < length());
1550     Q_ASSERT(start <= end || end == -1);
1551
1552     if (start != end && frameAt(start) != frameAt(end))
1553         return 0;
1554
1555     beginEditBlock();
1556
1557     QTextFrame *frame = qobject_cast<QTextFrame *>(createObject(format));
1558     Q_ASSERT(frame);
1559
1560     // #### using the default block and char format below might be wrong
1561     int idx = formats.indexForFormat(QTextBlockFormat());
1562     QTextCharFormat cfmt;
1563     cfmt.setObjectIndex(frame->objectIndex());
1564     int charIdx = formats.indexForFormat(cfmt);
1565
1566     insertBlock(QTextBeginningOfFrame, start, idx, charIdx, QTextUndoCommand::MoveCursor);
1567     insertBlock(QTextEndOfFrame, ++end, idx, charIdx, QTextUndoCommand::KeepCursor);
1568
1569     frame->d_func()->fragment_start = find(start).n;
1570     frame->d_func()->fragment_end = find(end).n;
1571
1572     insert_frame(frame);
1573
1574     endEditBlock();
1575
1576     return frame;
1577 }
1578
1579 void QTextDocumentPrivate::removeFrame(QTextFrame *frame)
1580 {
1581     QTextFrame *parent = frame->d_func()->parentFrame;
1582     if (!parent)
1583         return;
1584
1585     int start = frame->firstPosition();
1586     int end = frame->lastPosition();
1587     Q_ASSERT(end >= start);
1588
1589     beginEditBlock();
1590
1591     // remove already removes the frames from the tree
1592     remove(end, 1);
1593     remove(start-1, 1);
1594
1595     endEditBlock();
1596 }
1597
1598 QTextObject *QTextDocumentPrivate::objectForIndex(int objectIndex) const
1599 {
1600     if (objectIndex < 0)
1601         return 0;
1602
1603     QTextObject *object = objects.value(objectIndex, 0);
1604     if (!object) {
1605         QTextDocumentPrivate *that = const_cast<QTextDocumentPrivate *>(this);
1606         QTextFormat fmt = formats.objectFormat(objectIndex);
1607         object = that->createObject(fmt, objectIndex);
1608     }
1609     return object;
1610 }
1611
1612 QTextObject *QTextDocumentPrivate::objectForFormat(int formatIndex) const
1613 {
1614     int objectIndex = formats.format(formatIndex).objectIndex();
1615     return objectForIndex(objectIndex);
1616 }
1617
1618 QTextObject *QTextDocumentPrivate::objectForFormat(const QTextFormat &f) const
1619 {
1620     return objectForIndex(f.objectIndex());
1621 }
1622
1623 QTextObject *QTextDocumentPrivate::createObject(const QTextFormat &f, int objectIndex)
1624 {
1625     QTextObject *obj = document()->createObject(f);
1626
1627     if (obj) {
1628         obj->d_func()->objectIndex = objectIndex == -1 ? formats.createObjectIndex(f) : objectIndex;
1629         objects[obj->d_func()->objectIndex] = obj;
1630     }
1631
1632     return obj;
1633 }
1634
1635 void QTextDocumentPrivate::deleteObject(QTextObject *object)
1636 {
1637     const int objIdx = object->d_func()->objectIndex;
1638     objects.remove(objIdx);
1639     delete object;
1640 }
1641
1642 void QTextDocumentPrivate::contentsChanged()
1643 {
1644     Q_Q(QTextDocument);
1645     if (editBlock)
1646         return;
1647
1648     bool m = undoEnabled ? (modifiedState != undoState) : true;
1649     if (modified != m) {
1650         modified = m;
1651         emit q->modificationChanged(modified);
1652     }
1653
1654     emit q->contentsChanged();
1655 }
1656
1657 void QTextDocumentPrivate::compressPieceTable()
1658 {
1659     if (undoEnabled)
1660         return;
1661
1662     const uint garbageCollectionThreshold = 96 * 1024; // bytes
1663
1664     //qDebug() << "unreachable bytes:" << unreachableCharacterCount * sizeof(QChar) << " -- limit" << garbageCollectionThreshold << "text size =" << text.size() << "capacity:" << text.capacity();
1665
1666     bool compressTable = unreachableCharacterCount * sizeof(QChar) > garbageCollectionThreshold
1667                          && text.size() >= text.capacity() * 0.9;
1668     if (!compressTable)
1669         return;
1670
1671     QString newText;
1672     newText.resize(text.size());
1673     QChar *newTextPtr = newText.data();
1674     int newLen = 0;
1675
1676     for (FragmentMap::Iterator it = fragments.begin(); !it.atEnd(); ++it) {
1677         memcpy(newTextPtr, text.constData() + it->stringPosition, it->size_array[0] * sizeof(QChar));
1678         it->stringPosition = newLen;
1679         newTextPtr += it->size_array[0];
1680         newLen += it->size_array[0];
1681     }
1682
1683     newText.resize(newLen);
1684     newText.squeeze();
1685     //qDebug() << "removed" << text.size() - newText.size() << "characters";
1686     text = newText;
1687     unreachableCharacterCount = 0;
1688 }
1689
1690 void QTextDocumentPrivate::setModified(bool m)
1691 {
1692     Q_Q(QTextDocument);
1693     if (m == modified)
1694         return;
1695
1696     modified = m;
1697     if (!modified)
1698         modifiedState = undoState;
1699     else
1700         modifiedState = -1;
1701
1702     emit q->modificationChanged(modified);
1703 }
1704
1705 bool QTextDocumentPrivate::ensureMaximumBlockCount()
1706 {
1707     if (maximumBlockCount <= 0)
1708         return false;
1709     if (blocks.numNodes() <= maximumBlockCount)
1710         return false;
1711
1712     beginEditBlock();
1713
1714     const int blocksToRemove = blocks.numNodes() - maximumBlockCount;
1715     QTextCursor cursor(this, 0);
1716     cursor.movePosition(QTextCursor::NextBlock, QTextCursor::KeepAnchor, blocksToRemove);
1717
1718     unreachableCharacterCount += cursor.selectionEnd() - cursor.selectionStart();
1719
1720     // preserve the char format of the paragraph that is to become the new first one
1721     QTextCharFormat charFmt = cursor.blockCharFormat();
1722     cursor.removeSelectedText();
1723     cursor.setBlockCharFormat(charFmt);
1724
1725     endEditBlock();
1726
1727     compressPieceTable();
1728
1729     return true;
1730 }
1731
1732 /// This method is called from QTextTable when it is about to remove a table-cell to allow cursors to update their selection.
1733 void QTextDocumentPrivate::aboutToRemoveCell(int from, int to)
1734 {
1735     Q_ASSERT(from <= to);
1736     foreach (QTextCursorPrivate *curs, cursors)
1737         curs->aboutToRemoveCell(from, to);
1738 }
1739
1740 QT_END_NAMESPACE