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