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