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