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