1	// Copyright (C) 2021 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 <QtGui/private/qtguiglobal_p.h>
5	#include "qdebug.h"
6	#include "qtextformat.h"
7	#include "qtextformat_p.h"
8	#include "qtextengine_p.h"
9	#include "qabstracttextdocumentlayout.h"
10	#include "qabstracttextdocumentlayout_p.h"
11	#include "qtextlayout.h"
12	#include "qtextboundaryfinder.h"
13	#include <QtCore/private/qunicodetables_p.h>
14	#include "qvarlengtharray.h"
15	#include "qfont.h"
16	#include "qfont_p.h"
17	#include "qfontengine_p.h"
18	#include "qstring.h"
19	#include "qtextdocument_p.h"
20	#include "qrawfont.h"
21	#include "qrawfont_p.h"
22	#include <qguiapplication.h>
23	#include <qinputmethod.h>
24	#include <algorithm>
25	#include <stdlib.h>
26
27	QT_BEGIN_NAMESPACE
28
29	static const float smallCapsFraction = 0.7f;
30
31	namespace {
32	// Helper class used in QTextEngine::itemize
33	// keep it out here to allow us to keep supporting various compilers.
34	class Itemizer {
35	public:
36	Itemizer(const QString &string, const QScriptAnalysis *analysis, QScriptItemArray &items)
37	: m_string(string),
38	m_analysis(analysis),
39	m_items(items)
40	{
41	}
42	~Itemizer() = default;
43	/// generate the script items
44	/// The caps parameter is used to choose the algorithm of splitting text and assigning roles to the textitems
45	void generate(int start, int length, QFont::Capitalization caps)
46	{
47	if (caps == QFont::SmallCaps)
48	generateScriptItemsSmallCaps(uc: reinterpret_cast<const ushort *>(m_string.unicode()), start, length);
49	else if (caps == QFont::Capitalize)
50	generateScriptItemsCapitalize(start, length);
51	else if (caps != QFont::MixedCase) {
52	generateScriptItemsAndChangeCase(start, length,
53	flags: caps == QFont::AllLowercase ? QScriptAnalysis::Lowercase : QScriptAnalysis::Uppercase);
54	}
55	else
56	generateScriptItems(start, length);
57	}
58
59	private:
60	enum { MaxItemLength = 4096 };
61
62	void generateScriptItemsAndChangeCase(int start, int length, QScriptAnalysis::Flags flags)
63	{
64	generateScriptItems(start, length);
65	if (m_items.isEmpty()) // the next loop won't work in that case
66	return;
67	QScriptItemArray::Iterator iter = m_items.end();
68	do {
69	iter--;
70	if (iter->analysis.flags < QScriptAnalysis::LineOrParagraphSeparator)
71	iter->analysis.flags = flags;
72	} while (iter->position > start);
73	}
74
75	void generateScriptItems(int start, int length)
76	{
77	if (!length)
78	return;
79	const int end = start + length;
80	for (int i = start + 1; i < end; ++i) {
81	if (m_analysis[i].bidiLevel == m_analysis[start].bidiLevel
82	&& m_analysis[i].flags == m_analysis[start].flags
83	&& (m_analysis[i].script == m_analysis[start].script || m_string[i] == u'.')
84	&& m_analysis[i].flags < QScriptAnalysis::SpaceTabOrObject
85	&& i - start < MaxItemLength)
86	continue;
87	m_items.append(t: QScriptItem(start, m_analysis[start]));
88	start = i;
89	}
90	m_items.append(t: QScriptItem(start, m_analysis[start]));
91	}
92
93	void generateScriptItemsCapitalize(int start, int length)
94	{
95	if (!length)
96	return;
97
98	if (!m_splitter)
99	m_splitter = std::make_unique<QTextBoundaryFinder>(args: QTextBoundaryFinder::Word,
100	args: m_string.constData(), args: m_string.size(),
101	/*buffer*/args: nullptr, /*buffer size*/args: 0);
102
103	m_splitter->setPosition(start);
104	QScriptAnalysis itemAnalysis = m_analysis[start];
105
106	if (m_splitter->boundaryReasons() & QTextBoundaryFinder::StartOfItem)
107	itemAnalysis.flags = QScriptAnalysis::Uppercase;
108
109	m_splitter->toNextBoundary();
110
111	const int end = start + length;
112	for (int i = start + 1; i < end; ++i) {
113	bool atWordStart = false;
114
115	if (i == m_splitter->position()) {
116	if (m_splitter->boundaryReasons() & QTextBoundaryFinder::StartOfItem) {
117	Q_ASSERT(m_analysis[i].flags < QScriptAnalysis::TabOrObject);
118	atWordStart = true;
119	}
120
121	m_splitter->toNextBoundary();
122	}
123
124	if (m_analysis[i] == itemAnalysis
125	&& m_analysis[i].flags < QScriptAnalysis::TabOrObject
126	&& !atWordStart
127	&& i - start < MaxItemLength)
128	continue;
129
130	m_items.append(t: QScriptItem(start, itemAnalysis));
131	start = i;
132	itemAnalysis = m_analysis[start];
133
134	if (atWordStart)
135	itemAnalysis.flags = QScriptAnalysis::Uppercase;
136	}
137	m_items.append(t: QScriptItem(start, itemAnalysis));
138	}
139
140	void generateScriptItemsSmallCaps(const ushort *uc, int start, int length)
141	{
142	if (!length)
143	return;
144	bool lower = (QChar::category(ucs4: uc[start]) == QChar::Letter_Lowercase);
145	const int end = start + length;
146	// split text into parts that are already uppercase and parts that are lowercase, and mark the latter to be uppercased later.
147	for (int i = start + 1; i < end; ++i) {
148	bool l = (QChar::category(ucs4: uc[i]) == QChar::Letter_Lowercase);
149	if ((m_analysis[i] == m_analysis[start])
150	&& m_analysis[i].flags < QScriptAnalysis::TabOrObject
151	&& l == lower
152	&& i - start < MaxItemLength)
153	continue;
154	m_items.append(t: QScriptItem(start, m_analysis[start]));
155	if (lower)
156	m_items.last().analysis.flags = QScriptAnalysis::SmallCaps;
157
158	start = i;
159	lower = l;
160	}
161	m_items.append(t: QScriptItem(start, m_analysis[start]));
162	if (lower)
163	m_items.last().analysis.flags = QScriptAnalysis::SmallCaps;
164	}
165
166	const QString &m_string;
167	const QScriptAnalysis * const m_analysis;
168	QScriptItemArray &m_items;
169	std::unique_ptr<QTextBoundaryFinder> m_splitter;
170	};
171
172	// -----------------------------------------------------------------------------------------------------
173	//
174	// The Unicode Bidi algorithm.
175	// See http://www.unicode.org/reports/tr9/tr9-37.html
176	//
177	// -----------------------------------------------------------------------------------------------------
178
179	// #define DEBUG_BIDI
180	#ifndef DEBUG_BIDI
181	enum { BidiDebugEnabled = false };
182	#define BIDI_DEBUG if (1) ; else qDebug
183	#else
184	enum { BidiDebugEnabled = true };
185	static const char *directions[] = {
186	"DirL", "DirR", "DirEN", "DirES", "DirET", "DirAN", "DirCS", "DirB", "DirS", "DirWS", "DirON",
187	"DirLRE", "DirLRO", "DirAL", "DirRLE", "DirRLO", "DirPDF", "DirNSM", "DirBN",
188	"DirLRI", "DirRLI", "DirFSI", "DirPDI"
189	};
190	#define BIDI_DEBUG qDebug
191	QDebug operator<<(QDebug d, QChar::Direction dir) {
192	return (d << directions[dir]);
193	}
194	#endif
195
196	struct QBidiAlgorithm {
197	template<typename T> using Vector = QVarLengthArray<T, 64>;
198
199	QBidiAlgorithm(const QChar *text, QScriptAnalysis *analysis, int length, bool baseDirectionIsRtl)
200	: text(text),
201	analysis(analysis),
202	length(length),
203	baseLevel(baseDirectionIsRtl ? 1 : 0)
204	{
205
206	}
207
208	struct IsolatePair {
209	int start;
210	int end;
211	};
212
213	void initScriptAnalysisAndIsolatePairs(Vector<IsolatePair> &isolatePairs)
214	{
215	int isolateStack[128];
216	int isolateLevel = 0;
217	// load directions of string, and determine isolate pairs
218	for (int i = 0; i < length; ++i) {
219	int pos = i;
220	char32_t uc = text[i].unicode();
221	if (QChar::isHighSurrogate(ucs4: uc) && i < length - 1 && text[i + 1].isLowSurrogate()) {
222	++i;
223	analysis[i].bidiDirection = QChar::DirNSM;
224	uc = QChar::surrogateToUcs4(high: ushort(uc), low: text[i].unicode());
225	}
226	const QUnicodeTables::Properties *p = QUnicodeTables::properties(ucs4: uc);
227	analysis[pos].bidiDirection = QChar::Direction(p->direction);
228	switch (QChar::Direction(p->direction)) {
229	case QChar::DirON:
230	// all mirrored chars are DirON
231	if (p->mirrorDiff)
232	analysis[pos].bidiFlags = QScriptAnalysis::BidiMirrored;
233	break;
234	case QChar::DirLRE:
235	case QChar::DirRLE:
236	case QChar::DirLRO:
237	case QChar::DirRLO:
238	case QChar::DirPDF:
239	case QChar::DirBN:
240	analysis[pos].bidiFlags = QScriptAnalysis::BidiMaybeResetToParagraphLevel|QScriptAnalysis::BidiBN;
241	break;
242	case QChar::DirLRI:
243	case QChar::DirRLI:
244	case QChar::DirFSI:
245	if (isolateLevel < 128) {
246	isolateStack[isolateLevel] = isolatePairs.size();
247	isolatePairs.append(t: { .start: pos, .end: length });
248	}
249	++isolateLevel;
250	analysis[pos].bidiFlags = QScriptAnalysis::BidiMaybeResetToParagraphLevel;
251	break;
252	case QChar::DirPDI:
253	if (isolateLevel > 0) {
254	--isolateLevel;
255	if (isolateLevel < 128)
256	isolatePairs[isolateStack[isolateLevel]].end = pos;
257	}
258	Q_FALLTHROUGH();
259	case QChar::DirWS:
260	analysis[pos].bidiFlags = QScriptAnalysis::BidiMaybeResetToParagraphLevel;
261	break;
262	case QChar::DirS:
263	case QChar::DirB:
264	analysis[pos].bidiFlags = QScriptAnalysis::BidiResetToParagraphLevel;
265	if (uc == QChar::ParagraphSeparator) {
266	// close all open isolates as we start a new paragraph
267	while (isolateLevel > 0) {
268	--isolateLevel;
269	if (isolateLevel < 128)
270	isolatePairs[isolateStack[isolateLevel]].end = pos;
271	}
272	}
273	break;
274	default:
275	break;
276	}
277	}
278	}
279
280	struct DirectionalRun {
281	int start;
282	int end;
283	int continuation;
284	ushort level;
285	bool isContinuation;
286	bool hasContent;
287	};
288
289	void generateDirectionalRuns(const Vector<IsolatePair> &isolatePairs, Vector<DirectionalRun> &runs)
290	{
291	struct DirectionalStack {
292	enum { MaxDepth = 125 };
293	struct Item {
294	ushort level;
295	bool isOverride;
296	bool isIsolate;
297	int runBeforeIsolate;
298	};
299	Item items[128];
300	int counter = 0;
301
302	void push(Item i) {
303	items[counter] = i;
304	++counter;
305	}
306	void pop() {
307	--counter;
308	}
309	int depth() const {
310	return counter;
311	}
312	const Item &top() const {
313	return items[counter - 1];
314	}
315	} stack;
316	int overflowIsolateCount = 0;
317	int overflowEmbeddingCount = 0;
318	int validIsolateCount = 0;
319
320	ushort level = baseLevel;
321	bool override = false;
322	stack.push(i: { .level: level, .isOverride: false, .isIsolate: false, .runBeforeIsolate: -1 });
323
324	BIDI_DEBUG() << "resolving explicit levels";
325	int runStart = 0;
326	int continuationFrom = -1;
327	int lastRunWithContent = -1;
328	bool runHasContent = false;
329
330	auto appendRun = [&](int runEnd) {
331	if (runEnd < runStart)
332	return;
333	bool isContinuation = false;
334	if (continuationFrom != -1) {
335	runs[continuationFrom].continuation = runs.size();
336	isContinuation = true;
337	} else if (lastRunWithContent != -1 && level == runs.at(idx: lastRunWithContent).level) {
338	runs[lastRunWithContent].continuation = runs.size();
339	isContinuation = true;
340	}
341	if (runHasContent)
342	lastRunWithContent = runs.size();
343	BIDI_DEBUG() << " appending run start/end" << runStart << runEnd << "level" << level;
344	runs.append(t: { .start: runStart, .end: runEnd, .continuation: -1, .level: level, .isContinuation: isContinuation, .hasContent: runHasContent });
345	runHasContent = false;
346	runStart = runEnd + 1;
347	continuationFrom = -1;
348	};
349
350	int isolatePairPosition = 0;
351
352	for (int i = 0; i < length; ++i) {
353	QChar::Direction dir = analysis[i].bidiDirection;
354
355
356	auto doEmbed = [&](bool isRtl, bool isOverride, bool isIsolate) {
357	if (isIsolate) {
358	if (override)
359	analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
360	runHasContent = true;
361	lastRunWithContent = -1;
362	++isolatePairPosition;
363	}
364	int runBeforeIsolate = runs.size();
365	ushort newLevel = isRtl ? ((stack.top().level + 1) | 1) : ((stack.top().level + 2) & ~1);
366	if (newLevel <= DirectionalStack::MaxDepth && !overflowEmbeddingCount && !overflowIsolateCount) {
367	if (isIsolate)
368	++validIsolateCount;
369	else
370	runBeforeIsolate = -1;
371	appendRun(isIsolate ? i : i - 1);
372	BIDI_DEBUG() << "pushing new item on stack: level" << (int)newLevel << "isOverride" << isOverride << "isIsolate" << isIsolate << runBeforeIsolate;
373	stack.push(i: { .level: newLevel, .isOverride: isOverride, .isIsolate: isIsolate, .runBeforeIsolate: runBeforeIsolate });
374	override = isOverride;
375	level = newLevel;
376	} else {
377	if (isIsolate)
378	++overflowIsolateCount;
379	else if (!overflowIsolateCount)
380	++overflowEmbeddingCount;
381	}
382	if (!isIsolate) {
383	if (override)
384	analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
385	else
386	analysis[i].bidiDirection = QChar::DirBN;
387	}
388	};
389
390	switch (dir) {
391	case QChar::DirLRE:
392	doEmbed(false, false, false);
393	break;
394	case QChar::DirRLE:
395	doEmbed(true, false, false);
396	break;
397	case QChar::DirLRO:
398	doEmbed(false, true, false);
399	break;
400	case QChar::DirRLO:
401	doEmbed(true, true, false);
402	break;
403	case QChar::DirLRI:
404	doEmbed(false, false, true);
405	break;
406	case QChar::DirRLI:
407	doEmbed(true, false, true);
408	break;
409	case QChar::DirFSI: {
410	bool isRtl = false;
411	if (isolatePairPosition < isolatePairs.size()) {
412	const auto &pair = isolatePairs.at(idx: isolatePairPosition);
413	Q_ASSERT(pair.start == i);
414	isRtl = QStringView(text + pair.start + 1, pair.end - pair.start - 1).isRightToLeft();
415	}
416	doEmbed(isRtl, false, true);
417	break;
418	}
419
420	case QChar::DirPDF:
421	if (override)
422	analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
423	else
424	analysis[i].bidiDirection = QChar::DirBN;
425	if (overflowIsolateCount) {
426	; // do nothing
427	} else if (overflowEmbeddingCount) {
428	--overflowEmbeddingCount;
429	} else if (!stack.top().isIsolate && stack.depth() >= 2) {
430	appendRun(i);
431	stack.pop();
432	override = stack.top().isOverride;
433	level = stack.top().level;
434	BIDI_DEBUG() << "popped PDF from stack, level now" << (int)stack.top().level;
435	}
436	break;
437	case QChar::DirPDI:
438	runHasContent = true;
439	if (overflowIsolateCount) {
440	--overflowIsolateCount;
441	} else if (validIsolateCount == 0) {
442	; // do nothing
443	} else {
444	appendRun(i - 1);
445	overflowEmbeddingCount = 0;
446	while (!stack.top().isIsolate)
447	stack.pop();
448	continuationFrom = stack.top().runBeforeIsolate;
449	BIDI_DEBUG() << "popped PDI from stack, level now" << (int)stack.top().level << "continuation from" << continuationFrom;
450	stack.pop();
451	override = stack.top().isOverride;
452	level = stack.top().level;
453	lastRunWithContent = -1;
454	--validIsolateCount;
455	}
456	if (override)
457	analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
458	break;
459	case QChar::DirB:
460	// paragraph separator, go down to base direction, reset all state
461	if (text[i].unicode() == QChar::ParagraphSeparator) {
462	appendRun(i - 1);
463	while (stack.counter > 1) {
464	// there might be remaining isolates on the stack that are missing a PDI. Those need to get
465	// a continuation indicating to take the eos from the end of the string (ie. the paragraph level)
466	const auto &t = stack.top();
467	if (t.isIsolate) {
468	runs[t.runBeforeIsolate].continuation = -2;
469	}
470	--stack.counter;
471	}
472	continuationFrom = -1;
473	lastRunWithContent = -1;
474	validIsolateCount = 0;
475	overflowIsolateCount = 0;
476	overflowEmbeddingCount = 0;
477	level = baseLevel;
478	}
479	break;
480	default:
481	runHasContent = true;
482	Q_FALLTHROUGH();
483	case QChar::DirBN:
484	if (override)
485	analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
486	break;
487	}
488	}
489	appendRun(length - 1);
490	while (stack.counter > 1) {
491	// there might be remaining isolates on the stack that are missing a PDI. Those need to get
492	// a continuation indicating to take the eos from the end of the string (ie. the paragraph level)
493	const auto &t = stack.top();
494	if (t.isIsolate) {
495	runs[t.runBeforeIsolate].continuation = -2;
496	}
497	--stack.counter;
498	}
499	}
500
501	void resolveExplicitLevels(Vector<DirectionalRun> &runs)
502	{
503	Vector<IsolatePair> isolatePairs;
504
505	initScriptAnalysisAndIsolatePairs(isolatePairs);
506	generateDirectionalRuns(isolatePairs, runs);
507	}
508
509	struct IsolatedRunSequenceIterator {
510	struct Position {
511	int current = -1;
512	int pos = -1;
513
514	Position() = default;
515	Position(int current, int pos) : current(current), pos(pos) {}
516
517	bool isValid() const { return pos != -1; }
518	void clear() { pos = -1; }
519	};
520	IsolatedRunSequenceIterator(const Vector<DirectionalRun> &runs, int i)
521	: runs(runs),
522	current(i)
523	{
524	pos = runs.at(idx: current).start;
525	}
526	int operator *() const { return pos; }
527	bool atEnd() const { return pos < 0; }
528	void operator++() {
529	++pos;
530	if (pos > runs.at(idx: current).end) {
531	current = runs.at(idx: current).continuation;
532	if (current > -1)
533	pos = runs.at(idx: current).start;
534	else
535	pos = -1;
536	}
537	}
538	void setPosition(Position p) {
539	current = p.current;
540	pos = p.pos;
541	}
542	Position position() const {
543	return Position(current, pos);
544	}
545	bool operator !=(int position) const {
546	return pos != position;
547	}
548
549	const Vector<DirectionalRun> &runs;
550	int current;
551	int pos;
552	};
553
554
555	void resolveW1W2W3(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
556	{
557	QChar::Direction last = sos;
558	QChar::Direction lastStrong = sos;
559	IsolatedRunSequenceIterator it(runs, i);
560	while (!it.atEnd()) {
561	int pos = *it;
562
563	// Rule W1: Resolve NSM
564	QChar::Direction current = analysis[pos].bidiDirection;
565	if (current == QChar::DirNSM) {
566	current = last;
567	analysis[pos].bidiDirection = current;
568	} else if (current >= QChar::DirLRI) {
569	last = QChar::DirON;
570	} else if (current == QChar::DirBN) {
571	current = last;
572	} else {
573	// there shouldn't be any explicit embedding marks here
574	Q_ASSERT(current != QChar::DirLRE);
575	Q_ASSERT(current != QChar::DirRLE);
576	Q_ASSERT(current != QChar::DirLRO);
577	Q_ASSERT(current != QChar::DirRLO);
578	Q_ASSERT(current != QChar::DirPDF);
579
580	last = current;
581	}
582
583	// Rule W2
584	if (current == QChar::DirEN && lastStrong == QChar::DirAL) {
585	current = QChar::DirAN;
586	analysis[pos].bidiDirection = current;
587	}
588
589	// remember last strong char for rule W2
590	if (current == QChar::DirL || current == QChar::DirR) {
591	lastStrong = current;
592	} else if (current == QChar::DirAL) {
593	// Rule W3
594	lastStrong = current;
595	analysis[pos].bidiDirection = QChar::DirR;
596	}
597	last = current;
598	++it;
599	}
600	}
601
602
603	void resolveW4(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
604	{
605	// Rule W4
606	QChar::Direction secondLast = sos;
607
608	IsolatedRunSequenceIterator it(runs, i);
609	int lastPos = *it;
610	QChar::Direction last = analysis[lastPos].bidiDirection;
611
612	// BIDI_DEBUG() << "Applying rule W4/W5";
613	++it;
614	while (!it.atEnd()) {
615	int pos = *it;
616	QChar::Direction current = analysis[pos].bidiDirection;
617	if (current == QChar::DirBN) {
618	++it;
619	continue;
620	}
621	// BIDI_DEBUG() << pos << secondLast << last << current;
622	if (last == QChar::DirES && current == QChar::DirEN && secondLast == QChar::DirEN) {
623	last = QChar::DirEN;
624	analysis[lastPos].bidiDirection = last;
625	} else if (last == QChar::DirCS) {
626	if (current == QChar::DirEN && secondLast == QChar::DirEN) {
627	last = QChar::DirEN;
628	analysis[lastPos].bidiDirection = last;
629	} else if (current == QChar::DirAN && secondLast == QChar::DirAN) {
630	last = QChar::DirAN;
631	analysis[lastPos].bidiDirection = last;
632	}
633	}
634	secondLast = last;
635	last = current;
636	lastPos = pos;
637	++it;
638	}
639	}
640
641	void resolveW5(const Vector<DirectionalRun> &runs, int i)
642	{
643	// Rule W5
644	IsolatedRunSequenceIterator::Position lastETPosition;
645
646	IsolatedRunSequenceIterator it(runs, i);
647	int lastPos = *it;
648	QChar::Direction last = analysis[lastPos].bidiDirection;
649	if (last == QChar::DirET || last == QChar::DirBN)
650	lastETPosition = it.position();
651
652	++it;
653	while (!it.atEnd()) {
654	int pos = *it;
655	QChar::Direction current = analysis[pos].bidiDirection;
656	if (current == QChar::DirBN) {
657	++it;
658	continue;
659	}
660	if (current == QChar::DirET) {
661	if (last == QChar::DirEN) {
662	current = QChar::DirEN;
663	analysis[pos].bidiDirection = current;
664	} else if (!lastETPosition.isValid()) {
665	lastETPosition = it.position();
666	}
667	} else if (lastETPosition.isValid()) {
668	if (current == QChar::DirEN) {
669	it.setPosition(lastETPosition);
670	while (it != pos) {
671	int pos = *it;
672	analysis[pos].bidiDirection = QChar::DirEN;
673	++it;
674	}
675	}
676	lastETPosition.clear();
677	}
678	last = current;
679	lastPos = pos;
680	++it;
681	}
682	}
683
684	void resolveW6W7(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
685	{
686	QChar::Direction lastStrong = sos;
687	IsolatedRunSequenceIterator it(runs, i);
688	while (!it.atEnd()) {
689	int pos = *it;
690
691	// Rule W6
692	QChar::Direction current = analysis[pos].bidiDirection;
693	if (current == QChar::DirBN) {
694	++it;
695	continue;
696	}
697	if (current == QChar::DirET || current == QChar::DirES || current == QChar::DirCS) {
698	analysis[pos].bidiDirection = QChar::DirON;
699	}
700
701	// Rule W7
702	else if (current == QChar::DirL || current == QChar::DirR) {
703	lastStrong = current;
704	} else if (current == QChar::DirEN && lastStrong == QChar::DirL) {
705	analysis[pos].bidiDirection = lastStrong;
706	}
707	++it;
708	}
709	}
710
711	struct BracketPair {
712	int first;
713	int second;
714
715	bool isValid() const { return second > 0; }
716
717	QChar::Direction containedDirection(const QScriptAnalysis *analysis, QChar::Direction embeddingDir) const {
718	int isolateCounter = 0;
719	QChar::Direction containedDir = QChar::DirON;
720	for (int i = first + 1; i < second; ++i) {
721	QChar::Direction dir = analysis[i].bidiDirection;
722	if (isolateCounter) {
723	if (dir == QChar::DirPDI)
724	--isolateCounter;
725	continue;
726	}
727	if (dir == QChar::DirL) {
728	containedDir = dir;
729	if (embeddingDir == dir)
730	break;
731	} else if (dir == QChar::DirR || dir == QChar::DirAN || dir == QChar::DirEN) {
732	containedDir = QChar::DirR;
733	if (embeddingDir == QChar::DirR)
734	break;
735	} else if (dir == QChar::DirLRI || dir == QChar::DirRLI || dir == QChar::DirFSI)
736	++isolateCounter;
737	}
738	BIDI_DEBUG() << " contained dir for backet pair" << first << "/" << second << "is" << containedDir;
739	return containedDir;
740	}
741	};
742
743
744	struct BracketStack {
745	struct Item {
746	Item() = default;
747	Item(uint pairedBracked, int position) : pairedBracked(pairedBracked), position(position) {}
748	uint pairedBracked = 0;
749	int position = 0;
750	};
751
752	void push(uint closingUnicode, int pos) {
753	if (position < MaxDepth)
754	stack[position] = Item(closingUnicode, pos);
755	++position;
756	}
757	int match(uint unicode) {
758	Q_ASSERT(!overflowed());
759	int p = position;
760	while (--p >= 0) {
761	if (stack[p].pairedBracked == unicode ||
762	// U+3009 and U+2329 are canonical equivalents of each other. Fortunately it's the only pair in Unicode 10
763	(stack[p].pairedBracked == 0x3009 && unicode == 0x232a) ||
764	(stack[p].pairedBracked == 0x232a && unicode == 0x3009)) {
765	position = p;
766	return stack[p].position;
767	}
768
769	}
770	return -1;
771	}
772
773	enum { MaxDepth = 63 };
774	Item stack[MaxDepth];
775	int position = 0;
776
777	bool overflowed() const { return position > MaxDepth; }
778	};
779
780	void resolveN0(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
781	{
782	ushort level = runs.at(idx: i).level;
783
784	Vector<BracketPair> bracketPairs;
785	{
786	BracketStack bracketStack;
787	IsolatedRunSequenceIterator it(runs, i);
788	while (!it.atEnd()) {
789	int pos = *it;
790	QChar::Direction dir = analysis[pos].bidiDirection;
791	if (dir == QChar::DirON) {
792	const QUnicodeTables::Properties *p = QUnicodeTables::properties(ucs2: char16_t{text[pos].unicode()});
793	if (p->mirrorDiff) {
794	// either opening or closing bracket
795	if (p->category == QChar::Punctuation_Open) {
796	// opening bracked
797	uint closingBracked = text[pos].unicode() + p->mirrorDiff;
798	bracketStack.push(closingUnicode: closingBracked, pos: bracketPairs.size());
799	if (bracketStack.overflowed()) {
800	bracketPairs.clear();
801	break;
802	}
803	bracketPairs.append(t: { .first: pos, .second: -1 });
804	} else if (p->category == QChar::Punctuation_Close) {
805	int pairPos = bracketStack.match(unicode: text[pos].unicode());
806	if (pairPos != -1)
807	bracketPairs[pairPos].second = pos;
808	}
809	}
810	}
811	++it;
812	}
813	}
814
815	if (BidiDebugEnabled && bracketPairs.size()) {
816	BIDI_DEBUG() << "matched bracket pairs:";
817	for (int i = 0; i < bracketPairs.size(); ++i)
818	BIDI_DEBUG() << " " << bracketPairs.at(idx: i).first << bracketPairs.at(idx: i).second;
819	}
820
821	QChar::Direction lastStrong = sos;
822	IsolatedRunSequenceIterator it(runs, i);
823	QChar::Direction embeddingDir = (level & 1) ? QChar::DirR : QChar::DirL;
824	for (int i = 0; i < bracketPairs.size(); ++i) {
825	const auto &pair = bracketPairs.at(idx: i);
826	if (!pair.isValid())
827	continue;
828	QChar::Direction containedDir = pair.containedDirection(analysis, embeddingDir);
829	if (containedDir == QChar::DirON) {
830	BIDI_DEBUG() << " 3: resolve bracket pair" << i << "to DirON";
831	continue;
832	} else if (containedDir == embeddingDir) {
833	analysis[pair.first].bidiDirection = embeddingDir;
834	analysis[pair.second].bidiDirection = embeddingDir;
835	BIDI_DEBUG() << " 1: resolve bracket pair" << i << "to" << embeddingDir;
836	} else {
837	// case c.
838	while (it.pos < pair.first) {
839	int pos = *it;
840	switch (analysis[pos].bidiDirection) {
841	case QChar::DirR:
842	case QChar::DirEN:
843	case QChar::DirAN:
844	lastStrong = QChar::DirR;
845	break;
846	case QChar::DirL:
847	lastStrong = QChar::DirL;
848	break;
849	default:
850	break;
851	}
852	++it;
853	}
854	analysis[pair.first].bidiDirection = lastStrong;
855	analysis[pair.second].bidiDirection = lastStrong;
856	BIDI_DEBUG() << " 2: resolve bracket pair" << i << "to" << lastStrong;
857	}
858	for (int i = pair.second + 1; i < length; ++i) {
859	if (text[i].direction() == QChar::DirNSM)
860	analysis[i].bidiDirection = analysis[pair.second].bidiDirection;
861	else
862	break;
863	}
864	}
865	}
866
867	void resolveN1N2(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos, QChar::Direction eos)
868	{
869	// Rule N1 & N2
870	QChar::Direction lastStrong = sos;
871	IsolatedRunSequenceIterator::Position niPos;
872	IsolatedRunSequenceIterator it(runs, i);
873	// QChar::Direction last = QChar::DirON;
874	while (1) {
875	int pos = *it;
876
877	QChar::Direction current = pos >= 0 ? analysis[pos].bidiDirection : eos;
878	QChar::Direction currentStrong = current;
879	switch (current) {
880	case QChar::DirEN:
881	case QChar::DirAN:
882	currentStrong = QChar::DirR;
883	Q_FALLTHROUGH();
884	case QChar::DirL:
885	case QChar::DirR:
886	if (niPos.isValid()) {
887	QChar::Direction dir = currentStrong;
888	if (lastStrong != currentStrong)
889	dir = (runs.at(idx: i).level) & 1 ? QChar::DirR : QChar::DirL;
890	it.setPosition(niPos);
891	while (*it != pos) {
892	if (analysis[*it].bidiDirection != QChar::DirBN)
893	analysis[*it].bidiDirection = dir;
894	++it;
895	}
896	niPos.clear();
897	}
898	lastStrong = currentStrong;
899	break;
900
901	case QChar::DirBN:
902	case QChar::DirS:
903	case QChar::DirWS:
904	case QChar::DirON:
905	case QChar::DirFSI:
906	case QChar::DirLRI:
907	case QChar::DirRLI:
908	case QChar::DirPDI:
909	case QChar::DirB:
910	if (!niPos.isValid())
911	niPos = it.position();
912	break;
913
914	default:
915	Q_UNREACHABLE();
916	}
917	if (it.atEnd())
918	break;
919	// last = current;
920	++it;
921	}
922	}
923
924	void resolveImplicitLevelsForIsolatedRun(const Vector<DirectionalRun> &runs, int i)
925	{
926	// Rule X10
927	int level = runs.at(idx: i).level;
928	int before = i - 1;
929	while (before >= 0 && !runs.at(idx: before).hasContent)
930	--before;
931	int level_before = (before >= 0) ? runs.at(idx: before).level : baseLevel;
932	int after = i;
933	while (runs.at(idx: after).continuation >= 0)
934	after = runs.at(idx: after).continuation;
935	if (runs.at(idx: after).continuation == -2) {
936	after = runs.size();
937	} else {
938	++after;
939	while (after < runs.size() && !runs.at(idx: after).hasContent)
940	++after;
941	}
942	int level_after = (after == runs.size()) ? baseLevel : runs.at(idx: after).level;
943	QChar::Direction sos = (qMax(a: level_before, b: level) & 1) ? QChar::DirR : QChar::DirL;
944	QChar::Direction eos = (qMax(a: level_after, b: level) & 1) ? QChar::DirR : QChar::DirL;
945
946	if (BidiDebugEnabled) {
947	BIDI_DEBUG() << "Isolated run starting at" << i << "sos/eos" << sos << eos;
948	BIDI_DEBUG() << "before implicit level processing:";
949	IsolatedRunSequenceIterator it(runs, i);
950	while (!it.atEnd()) {
951	BIDI_DEBUG() << " " << *it << Qt::hex << text[*it].unicode() << analysis[*it].bidiDirection;
952	++it;
953	}
954	}
955
956	resolveW1W2W3(runs, i, sos);
957	resolveW4(runs, i, sos);
958	resolveW5(runs, i);
959
960	if (BidiDebugEnabled) {
961	BIDI_DEBUG() << "after W4/W5";
962	IsolatedRunSequenceIterator it(runs, i);
963	while (!it.atEnd()) {
964	BIDI_DEBUG() << " " << *it << Qt::hex << text[*it].unicode() << analysis[*it].bidiDirection;
965	++it;
966	}
967	}
968
969	resolveW6W7(runs, i, sos);
970
971	// Resolve neutral types
972
973	// Rule N0
974	resolveN0(runs, i, sos);
975	resolveN1N2(runs, i, sos, eos);
976
977	BIDI_DEBUG() << "setting levels (run at" << level << ")";
978	// Rules I1 & I2: set correct levels
979	{
980	ushort level = runs.at(idx: i).level;
981	IsolatedRunSequenceIterator it(runs, i);
982	while (!it.atEnd()) {
983	int pos = *it;
984
985	QChar::Direction current = analysis[pos].bidiDirection;
986	switch (current) {
987	case QChar::DirBN:
988	break;
989	case QChar::DirL:
990	analysis[pos].bidiLevel = (level + 1) & ~1;
991	break;
992	case QChar::DirR:
993	analysis[pos].bidiLevel = level | 1;
994	break;
995	case QChar::DirAN:
996	case QChar::DirEN:
997	analysis[pos].bidiLevel = (level + 2) & ~1;
998	break;
999	default:
1000	Q_UNREACHABLE();
1001	}
1002	BIDI_DEBUG() << " " << pos << current << analysis[pos].bidiLevel;
1003	++it;
1004	}
1005	}
1006	}
1007
1008	void resolveImplicitLevels(const Vector<DirectionalRun> &runs)
1009	{
1010	for (int i = 0; i < runs.size(); ++i) {
1011	if (runs.at(idx: i).isContinuation)
1012	continue;
1013
1014	resolveImplicitLevelsForIsolatedRun(runs, i);
1015	}
1016	}
1017
1018	bool checkForBidi() const
1019	{
1020	if (baseLevel != 0)
1021	return true;
1022	for (int i = 0; i < length; ++i) {
1023	if (text[i].unicode() >= 0x590) {
1024	switch (text[i].direction()) {
1025	case QChar::DirR: case QChar::DirAN:
1026	case QChar::DirLRE: case QChar::DirLRO: case QChar::DirAL:
1027	case QChar::DirRLE: case QChar::DirRLO: case QChar::DirPDF:
1028	case QChar::DirLRI: case QChar::DirRLI: case QChar::DirFSI: case QChar::DirPDI:
1029	return true;
1030	default:
1031	break;
1032	}
1033	}
1034	}
1035	return false;
1036	}
1037
1038	bool process()
1039	{
1040	memset(s: analysis, c: 0, n: length * sizeof(QScriptAnalysis));
1041
1042	bool hasBidi = checkForBidi();
1043
1044	if (!hasBidi)
1045	return false;
1046
1047	if (BidiDebugEnabled) {
1048	BIDI_DEBUG() << ">>>> start bidi, text length" << length;
1049	for (int i = 0; i < length; ++i)
1050	BIDI_DEBUG() << Qt::hex << " (" << i << ")" << text[i].unicode() << text[i].direction();
1051	}
1052
1053	{
1054	Vector<DirectionalRun> runs;
1055	resolveExplicitLevels(runs);
1056
1057	if (BidiDebugEnabled) {
1058	BIDI_DEBUG() << "resolved explicit levels, nruns" << runs.size();
1059	for (int i = 0; i < runs.size(); ++i)
1060	BIDI_DEBUG() << " " << i << "start/end" << runs.at(idx: i).start << runs.at(idx: i).end << "level" << (int)runs.at(idx: i).level << "continuation" << runs.at(idx: i).continuation;
1061	}
1062
1063	// now we have a list of isolated run sequences inside the vector of runs, that can be fed
1064	// through the implicit level resolving
1065
1066	resolveImplicitLevels(runs);
1067	}
1068
1069	BIDI_DEBUG() << "Rule L1:";
1070	// Rule L1:
1071	bool resetLevel = true;
1072	for (int i = length - 1; i >= 0; --i) {
1073	if (analysis[i].bidiFlags & QScriptAnalysis::BidiResetToParagraphLevel) {
1074	BIDI_DEBUG() << "resetting pos" << i << "to baselevel";
1075	analysis[i].bidiLevel = baseLevel;
1076	resetLevel = true;
1077	} else if (resetLevel && analysis[i].bidiFlags & QScriptAnalysis::BidiMaybeResetToParagraphLevel) {
1078	BIDI_DEBUG() << "resetting pos" << i << "to baselevel (maybereset flag)";
1079	analysis[i].bidiLevel = baseLevel;
1080	} else {
1081	resetLevel = false;
1082	}
1083	}
1084
1085	// set directions for BN to the minimum of adjacent chars
1086	// This makes is possible to be conformant with the Bidi algorithm even though we don't
1087	// remove BN and explicit embedding chars from the stream of characters to reorder
1088	int lastLevel = baseLevel;
1089	int lastBNPos = -1;
1090	for (int i = 0; i < length; ++i) {
1091	if (analysis[i].bidiFlags & QScriptAnalysis::BidiBN) {
1092	if (lastBNPos < 0)
1093	lastBNPos = i;
1094	analysis[i].bidiLevel = lastLevel;
1095	} else {
1096	int l = analysis[i].bidiLevel;
1097	if (lastBNPos >= 0) {
1098	if (l < lastLevel) {
1099	while (lastBNPos < i) {
1100	analysis[lastBNPos].bidiLevel = l;
1101	++lastBNPos;
1102	}
1103	}
1104	lastBNPos = -1;
1105	}
1106	lastLevel = l;
1107	}
1108	}
1109	if (lastBNPos >= 0 && baseLevel < lastLevel) {
1110	while (lastBNPos < length) {
1111	analysis[lastBNPos].bidiLevel = baseLevel;
1112	++lastBNPos;
1113	}
1114	}
1115
1116	if (BidiDebugEnabled) {
1117	BIDI_DEBUG() << "final resolved levels:";
1118	for (int i = 0; i < length; ++i)
1119	BIDI_DEBUG() << " " << i << Qt::hex << text[i].unicode() << Qt::dec << (int)analysis[i].bidiLevel;
1120	}
1121
1122	return true;
1123	}
1124
1125
1126	const QChar *text;
1127	QScriptAnalysis *analysis;
1128	int length;
1129	char baseLevel;
1130	};
1131
1132	} // namespace
1133
1134	void QTextEngine::bidiReorder(int numItems, const quint8 *levels, int *visualOrder)
1135	{
1136
1137	// first find highest and lowest levels
1138	quint8 levelLow = 128;
1139	quint8 levelHigh = 0;
1140	int i = 0;
1141	while (i < numItems) {
1142	//printf("level = %d\n", r->level);
1143	if (levels[i] > levelHigh)
1144	levelHigh = levels[i];
1145	if (levels[i] < levelLow)
1146	levelLow = levels[i];
1147	i++;
1148	}
1149
1150	// implements reordering of the line (L2 according to BiDi spec):
1151	// L2. From the highest level found in the text to the lowest odd level on each line,
1152	// reverse any contiguous sequence of characters that are at that level or higher.
1153
1154	// reversing is only done up to the lowest odd level
1155	if (!(levelLow%2)) levelLow++;
1156
1157	BIDI_DEBUG() << "reorderLine: lineLow = " << (uint)levelLow << ", lineHigh = " << (uint)levelHigh;
1158
1159	int count = numItems - 1;
1160	for (i = 0; i < numItems; i++)
1161	visualOrder[i] = i;
1162
1163	while(levelHigh >= levelLow) {
1164	int i = 0;
1165	while (i < count) {
1166	while(i < count && levels[i] < levelHigh) i++;
1167	int start = i;
1168	while(i <= count && levels[i] >= levelHigh) i++;
1169	int end = i-1;
1170
1171	if (start != end) {
1172	//qDebug() << "reversing from " << start << " to " << end;
1173	for(int j = 0; j < (end-start+1)/2; j++) {
1174	int tmp = visualOrder[start+j];
1175	visualOrder[start+j] = visualOrder[end-j];
1176	visualOrder[end-j] = tmp;
1177	}
1178	}
1179	i++;
1180	}
1181	levelHigh--;
1182	}
1183
1184	// BIDI_DEBUG("visual order is:");
1185	// for (i = 0; i < numItems; i++)
1186	// BIDI_DEBUG() << visualOrder[i];
1187	}
1188
1189
1190	enum JustificationClass {
1191	Justification_Prohibited = 0, // Justification can not be applied after this glyph
1192	Justification_Arabic_Space = 1, // This glyph represents a space inside arabic text
1193	Justification_Character = 2, // Inter-character justification point follows this glyph
1194	Justification_Space = 4, // This glyph represents a blank outside an Arabic run
1195	Justification_Arabic_Normal = 7, // Normal Middle-Of-Word glyph that connects to the right (begin)
1196	Justification_Arabic_Waw = 8, // Next character is final form of Waw/Ain/Qaf/Feh
1197	Justification_Arabic_BaRa = 9, // Next two characters are Ba + Ra/Ya/AlefMaksura
1198	Justification_Arabic_Alef = 10, // Next character is final form of Alef/Tah/Lam/Kaf/Gaf
1199	Justification_Arabic_HahDal = 11, // Next character is final form of Hah/Dal/Teh Marbuta
1200	Justification_Arabic_Seen = 12, // Initial or medial form of Seen/Sad
1201	Justification_Arabic_Kashida = 13 // User-inserted Kashida(U+0640)
1202	};
1203
1204	#if QT_CONFIG(harfbuzz)
1205
1206	/*
1207	Adds an inter character justification opportunity after the number or letter
1208	character and a space justification opportunity after the space character.
1209	*/
1210	static inline void qt_getDefaultJustificationOpportunities(const ushort *string, qsizetype length, const QGlyphLayout &g, ushort *log_clusters, int spaceAs)
1211	{
1212	qsizetype str_pos = 0;
1213	while (str_pos < length) {
1214	int glyph_pos = log_clusters[str_pos];
1215
1216	Q_ASSERT(glyph_pos < g.numGlyphs && g.attributes[glyph_pos].clusterStart);
1217
1218	uint ucs4 = string[str_pos];
1219	if (QChar::isHighSurrogate(ucs4) && str_pos + 1 < length) {
1220	ushort low = string[str_pos + 1];
1221	if (QChar::isLowSurrogate(ucs4: low)) {
1222	++str_pos;
1223	ucs4 = QChar::surrogateToUcs4(high: ucs4, low);
1224	}
1225	}
1226
1227	// skip whole cluster
1228	do {
1229	++str_pos;
1230	} while (str_pos < length && log_clusters[str_pos] == glyph_pos);
1231	do {
1232	++glyph_pos;
1233	} while (glyph_pos < g.numGlyphs && !g.attributes[glyph_pos].clusterStart);
1234	--glyph_pos;
1235
1236	// justification opportunity at the end of cluster
1237	if (Q_LIKELY(QChar::isLetterOrNumber(ucs4)))
1238	g.attributes[glyph_pos].justification = Justification_Character;
1239	else if (Q_LIKELY(QChar::isSpace(ucs4)))
1240	g.attributes[glyph_pos].justification = spaceAs;
1241	}
1242	}
1243
1244	static inline void qt_getJustificationOpportunities(const ushort *string, qsizetype length, const QScriptItem &si, const QGlyphLayout &g, ushort *log_clusters)
1245	{
1246	Q_ASSERT(length > 0 && g.numGlyphs > 0);
1247
1248	for (int glyph_pos = 0; glyph_pos < g.numGlyphs; ++glyph_pos)
1249	g.attributes[glyph_pos].justification = Justification_Prohibited;
1250
1251	int spaceAs;
1252
1253	switch (si.analysis.script) {
1254	case QChar::Script_Arabic:
1255	case QChar::Script_Syriac:
1256	case QChar::Script_Nko:
1257	case QChar::Script_Mandaic:
1258	case QChar::Script_Mongolian:
1259	case QChar::Script_PhagsPa:
1260	case QChar::Script_Manichaean:
1261	case QChar::Script_PsalterPahlavi:
1262	// same as default but inter character justification takes precedence
1263	spaceAs = Justification_Arabic_Space;
1264	break;
1265
1266	case QChar::Script_Tibetan:
1267	case QChar::Script_Hiragana:
1268	case QChar::Script_Katakana:
1269	case QChar::Script_Bopomofo:
1270	case QChar::Script_Han:
1271	// same as default but inter character justification is the only option
1272	spaceAs = Justification_Character;
1273	break;
1274
1275	default:
1276	spaceAs = Justification_Space;
1277	break;
1278	}
1279
1280	qt_getDefaultJustificationOpportunities(string, length, g, log_clusters, spaceAs);
1281	}
1282
1283	#endif // harfbuzz
1284
1285
1286	// shape all the items that intersect with the line, taking tab widths into account to find out what text actually fits in the line.
1287	void QTextEngine::shapeLine(const QScriptLine &line)
1288	{
1289	QFixed x;
1290	bool first = true;
1291	int item = findItem(strPos: line.from);
1292	if (item == -1)
1293	return;
1294
1295	const int end = findItem(strPos: line.from + line.length + line.trailingSpaces - 1, firstItem: item);
1296	for ( ; item <= end; ++item) {
1297	QScriptItem &si = layoutData->items[item];
1298	if (si.analysis.flags == QScriptAnalysis::Tab) {
1299	ensureSpace(nGlyphs: 1);
1300	si.width = calculateTabWidth(index: item, x);
1301	} else {
1302	shape(item);
1303	}
1304	if (first && si.position != line.from) { // that means our x position has to be offset
1305	QGlyphLayout glyphs = shapedGlyphs(si: &si);
1306	Q_ASSERT(line.from > si.position);
1307	for (int i = line.from - si.position - 1; i >= 0; i--) {
1308	x -= glyphs.effectiveAdvance(item: i);
1309	}
1310	}
1311	first = false;
1312
1313	x += si.width;
1314	}
1315	}
1316
1317	static void applyVisibilityRules(ushort ucs, QGlyphLayout *glyphs, uint glyphPosition, QFontEngine *fontEngine)
1318	{
1319	// hide characters that should normally be invisible
1320	switch (ucs) {
1321	case QChar::LineFeed:
1322	case 0x000c: // FormFeed
1323	case QChar::CarriageReturn:
1324	case QChar::LineSeparator:
1325	case QChar::ParagraphSeparator:
1326	glyphs->attributes[glyphPosition].dontPrint = true;
1327	break;
1328	case QChar::SoftHyphen:
1329	if (!fontEngine->symbol) {
1330	// U+00AD [SOFT HYPHEN] is a default ignorable codepoint,
1331	// so we replace its glyph and metrics with ones for
1332	// U+002D [HYPHEN-MINUS] or U+2010 [HYPHEN] and make
1333	// it visible if it appears at line-break
1334	const uint engineIndex = glyphs->glyphs[glyphPosition] & 0xff000000;
1335	glyph_t glyph = fontEngine->glyphIndex(ucs4: 0x002d);
1336	if (glyph == 0)
1337	glyph = fontEngine->glyphIndex(ucs4: 0x2010);
1338	if (glyph == 0)
1339	glyph = fontEngine->glyphIndex(ucs4: 0x00ad);
1340	glyphs->glyphs[glyphPosition] = glyph;
1341	if (Q_LIKELY(glyphs->glyphs[glyphPosition] != 0)) {
1342	glyphs->glyphs[glyphPosition] |= engineIndex;
1343	QGlyphLayout tmp = glyphs->mid(position: glyphPosition, n: 1);
1344	fontEngine->recalcAdvances(&tmp, { });
1345	}
1346	glyphs->attributes[glyphPosition].dontPrint = true;
1347	}
1348	break;
1349	default:
1350	break;
1351	}
1352	}
1353
1354	void QTextEngine::shapeText(int item) const
1355	{
1356	Q_ASSERT(item < layoutData->items.size());
1357	QScriptItem &si = layoutData->items[item];
1358
1359	if (si.num_glyphs)
1360	return;
1361
1362	si.width = 0;
1363	si.glyph_data_offset = layoutData->used;
1364
1365	const ushort *string = reinterpret_cast<const ushort *>(layoutData->string.constData()) + si.position;
1366	const int itemLength = length(item);
1367
1368	QString casedString;
1369	if (si.analysis.flags && si.analysis.flags <= QScriptAnalysis::SmallCaps) {
1370	casedString.resize(size: itemLength);
1371	ushort *uc = reinterpret_cast<ushort *>(casedString.data());
1372	for (int i = 0; i < itemLength; ++i) {
1373	uint ucs4 = string[i];
1374	if (QChar::isHighSurrogate(ucs4) && i + 1 < itemLength) {
1375	uint low = string[i + 1];
1376	if (QChar::isLowSurrogate(ucs4: low)) {
1377	// high part never changes in simple casing
1378	uc[i] = ucs4;
1379	++i;
1380	ucs4 = QChar::surrogateToUcs4(high: ucs4, low);
1381	ucs4 = si.analysis.flags == QScriptAnalysis::Lowercase ? QChar::toLower(ucs4)
1382	: QChar::toUpper(ucs4);
1383	uc[i] = QChar::lowSurrogate(ucs4);
1384	}
1385	} else {
1386	uc[i] = si.analysis.flags == QScriptAnalysis::Lowercase ? QChar::toLower(ucs4)
1387	: QChar::toUpper(ucs4);
1388	}
1389	}
1390	string = reinterpret_cast<const ushort *>(casedString.constData());
1391	}
1392
1393	if (Q_UNLIKELY(!ensureSpace(itemLength))) {
1394	Q_UNREACHABLE_RETURN(); // ### report OOM error somehow
1395	}
1396
1397	QFontEngine *fontEngine = this->fontEngine(si, ascent: &si.ascent, descent: &si.descent, leading: &si.leading);
1398
1399	#if QT_CONFIG(harfbuzz)
1400	bool kerningEnabled;
1401	#endif
1402	bool letterSpacingIsAbsolute;
1403	bool shapingEnabled = false;
1404	QHash<QFont::Tag, quint32> features;
1405	QFixed letterSpacing, wordSpacing;
1406	#ifndef QT_NO_RAWFONT
1407	if (useRawFont) {
1408	QTextCharFormat f = format(si: &si);
1409	QFont font = f.font();
1410	# if QT_CONFIG(harfbuzz)
1411	kerningEnabled = font.kerning();
1412	shapingEnabled = QFontEngine::scriptRequiresOpenType(script: QChar::Script(si.analysis.script))
1413	|| (font.styleStrategy() & QFont::PreferNoShaping) == 0;
1414	# endif
1415	wordSpacing = QFixed::fromReal(r: font.wordSpacing());
1416	letterSpacing = QFixed::fromReal(r: font.letterSpacing());
1417	letterSpacingIsAbsolute = true;
1418	features = font.d->features;
1419	} else
1420	#endif
1421	{
1422	QFont font = this->font(si);
1423	#if QT_CONFIG(harfbuzz)
1424	kerningEnabled = font.d->kerning;
1425	shapingEnabled = QFontEngine::scriptRequiresOpenType(script: QChar::Script(si.analysis.script))
1426	|| (font.d->request.styleStrategy & QFont::PreferNoShaping) == 0;
1427	#endif
1428	letterSpacingIsAbsolute = font.d->letterSpacingIsAbsolute;
1429	letterSpacing = font.d->letterSpacing;
1430	wordSpacing = font.d->wordSpacing;
1431	features = font.d->features;
1432
1433	if (letterSpacingIsAbsolute && letterSpacing.value())
1434	letterSpacing *= font.d->dpi / qt_defaultDpiY();
1435	}
1436
1437	// split up the item into parts that come from different font engines
1438	// k * 3 entries, array[k] == index in string, array[k + 1] == index in glyphs, array[k + 2] == engine index
1439	QVarLengthArray<uint, 24> itemBoundaries;
1440
1441	QGlyphLayout initialGlyphs = availableGlyphs(si: &si);
1442	int nGlyphs = initialGlyphs.numGlyphs;
1443	if (fontEngine->type() == QFontEngine::Multi || !shapingEnabled) {
1444	// ask the font engine to find out which glyphs (as an index in the specific font)
1445	// to use for the text in one item.
1446	QFontEngine::ShaperFlags shaperFlags =
1447	shapingEnabled
1448	? QFontEngine::GlyphIndicesOnly
1449	: QFontEngine::ShaperFlag(0);
1450	if (fontEngine->stringToCMap(str: reinterpret_cast<const QChar *>(string), len: itemLength, glyphs: &initialGlyphs, nglyphs: &nGlyphs, flags: shaperFlags) < 0)
1451	Q_UNREACHABLE();
1452	}
1453
1454	if (fontEngine->type() == QFontEngine::Multi) {
1455	uint lastEngine = ~0u;
1456	for (int i = 0, glyph_pos = 0; i < itemLength; ++i, ++glyph_pos) {
1457	const uint engineIdx = initialGlyphs.glyphs[glyph_pos] >> 24;
1458	if (lastEngine != engineIdx) {
1459	itemBoundaries.push_back(t: i);
1460	itemBoundaries.push_back(t: glyph_pos);
1461	itemBoundaries.push_back(t: engineIdx);
1462
1463	if (engineIdx != 0) {
1464	QFontEngine *actualFontEngine = static_cast<QFontEngineMulti *>(fontEngine)->engine(at: engineIdx);
1465	si.ascent = qMax(a: actualFontEngine->ascent(), b: si.ascent);
1466	si.descent = qMax(a: actualFontEngine->descent(), b: si.descent);
1467	si.leading = qMax(a: actualFontEngine->leading(), b: si.leading);
1468	}
1469
1470	lastEngine = engineIdx;
1471	}
1472
1473	if (QChar::isHighSurrogate(ucs4: string[i]) && i + 1 < itemLength && QChar::isLowSurrogate(ucs4: string[i + 1]))
1474	++i;
1475	}
1476	} else {
1477	itemBoundaries.push_back(t: 0);
1478	itemBoundaries.push_back(t: 0);
1479	itemBoundaries.push_back(t: 0);
1480	}
1481
1482	#if QT_CONFIG(harfbuzz)
1483	if (Q_LIKELY(shapingEnabled)) {
1484	si.num_glyphs = shapeTextWithHarfbuzzNG(si,
1485	string,
1486	itemLength,
1487	fontEngine,
1488	itemBoundaries,
1489	kerningEnabled,
1490	hasLetterSpacing: letterSpacing != 0,
1491	features);
1492	} else
1493	#endif
1494	{
1495	ushort *log_clusters = logClusters(si: &si);
1496
1497	int glyph_pos = 0;
1498	for (int i = 0; i < itemLength; ++i, ++glyph_pos) {
1499	log_clusters[i] = glyph_pos;
1500	initialGlyphs.attributes[glyph_pos].clusterStart = true;
1501	if (QChar::isHighSurrogate(ucs4: string[i])
1502	&& i + 1 < itemLength
1503	&& QChar::isLowSurrogate(ucs4: string[i + 1])) {
1504	initialGlyphs.attributes[glyph_pos].dontPrint = !QChar::isPrint(ucs4: QChar::surrogateToUcs4(high: string[i], low: string[i + 1]));
1505	++i;
1506	log_clusters[i] = glyph_pos;
1507
1508	} else {
1509	initialGlyphs.attributes[glyph_pos].dontPrint = !QChar::isPrint(ucs4: string[i]);
1510	}
1511
1512	if (Q_UNLIKELY(!initialGlyphs.attributes[glyph_pos].dontPrint)) {
1513	QFontEngine *actualFontEngine = fontEngine;
1514	if (actualFontEngine->type() == QFontEngine::Multi) {
1515	const uint engineIdx = initialGlyphs.glyphs[glyph_pos] >> 24;
1516	actualFontEngine = static_cast<QFontEngineMulti *>(fontEngine)->engine(at: engineIdx);
1517	}
1518
1519	applyVisibilityRules(ucs: string[i], glyphs: &initialGlyphs, glyphPosition: glyph_pos, fontEngine: actualFontEngine);
1520	}
1521	}
1522
1523	si.num_glyphs = glyph_pos;
1524	}
1525
1526	if (Q_UNLIKELY(si.num_glyphs == 0)) {
1527	if (Q_UNLIKELY(!ensureSpace(si.glyph_data_offset + 1))) {
1528	qWarning() << "Unable to allocate space for place-holder glyph";
1529	return;
1530	}
1531
1532	si.num_glyphs = 1;
1533
1534	// Overwrite with 0 token to indicate failure
1535	QGlyphLayout g = availableGlyphs(si: &si);
1536	g.glyphs[0] = 0;
1537	g.attributes[0].clusterStart = true;
1538
1539	ushort *log_clusters = logClusters(si: &si);
1540	for (int i = 0; i < itemLength; ++i)
1541	log_clusters[i] = 0;
1542
1543	return;
1544	}
1545
1546	layoutData->used += si.num_glyphs;
1547
1548	QGlyphLayout glyphs = shapedGlyphs(si: &si);
1549
1550	#if QT_CONFIG(harfbuzz)
1551	qt_getJustificationOpportunities(string, length: itemLength, si, g: glyphs, log_clusters: logClusters(si: &si));
1552	#endif
1553
1554	if (letterSpacing != 0) {
1555	for (int i = 1; i < si.num_glyphs; ++i) {
1556	if (glyphs.attributes[i].clusterStart) {
1557	if (letterSpacingIsAbsolute)
1558	glyphs.advances[i - 1] += letterSpacing;
1559	else {
1560	QFixed &advance = glyphs.advances[i - 1];
1561	advance += (letterSpacing - 100) * advance / 100;
1562	}
1563	}
1564	}
1565	if (letterSpacingIsAbsolute)
1566	glyphs.advances[si.num_glyphs - 1] += letterSpacing;
1567	else {
1568	QFixed &advance = glyphs.advances[si.num_glyphs - 1];
1569	advance += (letterSpacing - 100) * advance / 100;
1570	}
1571	}
1572	if (wordSpacing != 0) {
1573	for (int i = 0; i < si.num_glyphs; ++i) {
1574	if (glyphs.attributes[i].justification == Justification_Space
1575	|| glyphs.attributes[i].justification == Justification_Arabic_Space) {
1576	// word spacing only gets added once to a consecutive run of spaces (see CSS spec)
1577	if (i + 1 == si.num_glyphs
1578	||(glyphs.attributes[i+1].justification != Justification_Space
1579	&& glyphs.attributes[i+1].justification != Justification_Arabic_Space))
1580	glyphs.advances[i] += wordSpacing;
1581	}
1582	}
1583	}
1584
1585	for (int i = 0; i < si.num_glyphs; ++i)
1586	si.width += glyphs.advances[i] * !glyphs.attributes[i].dontPrint;
1587	}
1588
1589	#if QT_CONFIG(harfbuzz)
1590
1591	QT_BEGIN_INCLUDE_NAMESPACE
1592
1593	#include "qharfbuzzng_p.h"
1594
1595	QT_END_INCLUDE_NAMESPACE
1596
1597	int QTextEngine::shapeTextWithHarfbuzzNG(const QScriptItem &si,
1598	const ushort *string,
1599	int itemLength,
1600	QFontEngine *fontEngine,
1601	QSpan<uint> itemBoundaries,
1602	bool kerningEnabled,
1603	bool hasLetterSpacing,
1604	const QHash<QFont::Tag, quint32> &fontFeatures) const
1605	{
1606	uint glyphs_shaped = 0;
1607
1608	hb_buffer_t *buffer = hb_buffer_create();
1609	hb_buffer_set_unicode_funcs(buffer, unicode_funcs: hb_qt_get_unicode_funcs());
1610	hb_buffer_pre_allocate(buffer, size: itemLength);
1611	if (Q_UNLIKELY(!hb_buffer_allocation_successful(buffer))) {
1612	hb_buffer_destroy(buffer);
1613	return 0;
1614	}
1615
1616	hb_segment_properties_t props = HB_SEGMENT_PROPERTIES_DEFAULT;
1617	props.direction = si.analysis.bidiLevel % 2 ? HB_DIRECTION_RTL : HB_DIRECTION_LTR;
1618	QChar::Script script = QChar::Script(si.analysis.script);
1619	props.script = hb_qt_script_to_script(script);
1620	// ### TODO get_default_for_script?
1621	props.language = hb_language_get_default(); // use default language from locale
1622
1623	for (qsizetype k = 0; k < itemBoundaries.size(); k += 3) {
1624	const uint item_pos = itemBoundaries[k];
1625	const uint item_length = (k + 4 < itemBoundaries.size() ? itemBoundaries[k + 3] : itemLength) - item_pos;
1626	const uint engineIdx = itemBoundaries[k + 2];
1627
1628	QFontEngine *actualFontEngine = fontEngine->type() != QFontEngine::Multi ? fontEngine
1629	: static_cast<QFontEngineMulti *>(fontEngine)->engine(at: engineIdx);
1630
1631
1632	// prepare buffer
1633	hb_buffer_clear_contents(buffer);
1634	hb_buffer_add_utf16(buffer, text: reinterpret_cast<const uint16_t *>(string) + item_pos, text_length: item_length, item_offset: 0, item_length);
1635
1636	hb_buffer_set_segment_properties(buffer, props: &props);
1637
1638	uint buffer_flags = HB_BUFFER_FLAG_DEFAULT;
1639	// Symbol encoding used to encode various crap in the 32..255 character code range,
1640	// and thus might override U+00AD [SHY]; avoid hiding default ignorables
1641	if (Q_UNLIKELY(actualFontEngine->symbol))
1642	buffer_flags |= HB_BUFFER_FLAG_PRESERVE_DEFAULT_IGNORABLES;
1643	hb_buffer_set_flags(buffer, flags: hb_buffer_flags_t(buffer_flags));
1644
1645
1646	// shape
1647	{
1648	hb_font_t *hb_font = hb_qt_font_get_for_engine(fe: actualFontEngine);
1649	Q_ASSERT(hb_font);
1650	hb_qt_font_set_use_design_metrics(font: hb_font, value: option.useDesignMetrics() ? uint(QFontEngine::DesignMetrics) : 0); // ###
1651
1652	// Ligatures are incompatible with custom letter spacing, so when a letter spacing is set,
1653	// we disable them for writing systems where they are purely cosmetic.
1654	bool scriptRequiresOpenType = ((script >= QChar::Script_Syriac && script <= QChar::Script_Sinhala)
1655	|| script == QChar::Script_Khmer || script == QChar::Script_Nko);
1656
1657	bool dontLigate = hasLetterSpacing && !scriptRequiresOpenType;
1658
1659	QHash<QFont::Tag, quint32> features;
1660	features.insert(key: QFont::Tag("kern"), value: !!kerningEnabled);
1661	if (dontLigate) {
1662	features.insert(key: QFont::Tag("liga"), value: false);
1663	features.insert(key: QFont::Tag("clig"), value: false);
1664	features.insert(key: QFont::Tag("dlig"), value: false);
1665	features.insert(key: QFont::Tag("hlig"), value: false);
1666	}
1667	features.insert(hash: fontFeatures);
1668
1669	QVarLengthArray<hb_feature_t, 16> featureArray;
1670	for (auto it = features.constBegin(); it != features.constEnd(); ++it) {
1671	featureArray.append(t: { .tag: it.key().value(),
1672	.value: it.value(),
1673	HB_FEATURE_GLOBAL_START,
1674	HB_FEATURE_GLOBAL_END });
1675	}
1676
1677	// whitelist cross-platforms shapers only
1678	static const char *shaper_list[] = {
1679	"graphite2",
1680	"ot",
1681	"fallback",
1682	nullptr
1683	};
1684
1685	bool shapedOk = hb_shape_full(font: hb_font,
1686	buffer,
1687	features: featureArray.constData(),
1688	num_features: features.size(),
1689	shaper_list);
1690	if (Q_UNLIKELY(!shapedOk)) {
1691	hb_buffer_destroy(buffer);
1692	return 0;
1693	}
1694
1695	if (Q_UNLIKELY(HB_DIRECTION_IS_BACKWARD(props.direction)))
1696	hb_buffer_reverse(buffer);
1697	}
1698
1699	uint num_glyphs = hb_buffer_get_length(buffer);
1700	const bool has_glyphs = num_glyphs > 0;
1701	// If Harfbuzz returns zero glyphs, we have to manually add a missing glyph
1702	if (Q_UNLIKELY(!has_glyphs))
1703	num_glyphs = 1;
1704
1705	// ensure we have enough space for shaped glyphs and metrics
1706	if (Q_UNLIKELY(!ensureSpace(glyphs_shaped + num_glyphs))) {
1707	hb_buffer_destroy(buffer);
1708	return 0;
1709	}
1710
1711	// fetch the shaped glyphs and metrics
1712	QGlyphLayout g = availableGlyphs(si: &si).mid(position: glyphs_shaped, n: num_glyphs);
1713	ushort *log_clusters = logClusters(si: &si) + item_pos;
1714	if (Q_LIKELY(has_glyphs)) {
1715	hb_glyph_info_t *infos = hb_buffer_get_glyph_infos(buffer, length: nullptr);
1716	hb_glyph_position_t *positions = hb_buffer_get_glyph_positions(buffer, length: nullptr);
1717	uint str_pos = 0;
1718	uint last_cluster = ~0u;
1719	uint last_glyph_pos = glyphs_shaped;
1720	for (uint i = 0; i < num_glyphs; ++i, ++infos, ++positions) {
1721	g.glyphs[i] = infos->codepoint;
1722
1723	g.advances[i] = QFixed::fromFixed(fixed: positions->x_advance);
1724	g.offsets[i].x = QFixed::fromFixed(fixed: positions->x_offset);
1725	g.offsets[i].y = QFixed::fromFixed(fixed: positions->y_offset);
1726
1727	uint cluster = infos->cluster;
1728	if (Q_LIKELY(last_cluster != cluster)) {
1729	g.attributes[i].clusterStart = true;
1730
1731	// fix up clusters so that the cluster indices will be monotonic
1732	// and thus we never return out-of-order indices
1733	while (last_cluster++ < cluster && str_pos < item_length)
1734	log_clusters[str_pos++] = last_glyph_pos;
1735	last_glyph_pos = i + glyphs_shaped;
1736	last_cluster = cluster;
1737
1738	applyVisibilityRules(ucs: string[item_pos + str_pos], glyphs: &g, glyphPosition: i, fontEngine: actualFontEngine);
1739	}
1740	}
1741	while (str_pos < item_length)
1742	log_clusters[str_pos++] = last_glyph_pos;
1743	} else { // Harfbuzz did not return a glyph for the character, so we add a placeholder
1744	g.glyphs[0] = 0;
1745	g.advances[0] = QFixed{};
1746	g.offsets[0].x = QFixed{};
1747	g.offsets[0].y = QFixed{};
1748	g.attributes[0].clusterStart = true;
1749	g.attributes[0].dontPrint = true;
1750	for (uint str_pos = 0; str_pos < item_length; ++str_pos)
1751	log_clusters[str_pos] = glyphs_shaped;
1752	}
1753
1754	if (Q_UNLIKELY(engineIdx != 0)) {
1755	for (quint32 i = 0; i < num_glyphs; ++i)
1756	g.glyphs[i] |= (engineIdx << 24);
1757	}
1758
1759	if (!actualFontEngine->supportsHorizontalSubPixelPositions()) {
1760	for (uint i = 0; i < num_glyphs; ++i) {
1761	g.advances[i] = g.advances[i].round();
1762	g.offsets[i].x = g.offsets[i].x.round();
1763	}
1764	}
1765
1766	glyphs_shaped += num_glyphs;
1767	}
1768
1769	hb_buffer_destroy(buffer);
1770
1771	return glyphs_shaped;
1772	}
1773
1774	#endif // harfbuzz
1775
1776	void QTextEngine::init(QTextEngine *e)
1777	{
1778	e->ignoreBidi = false;
1779	e->cacheGlyphs = false;
1780	e->forceJustification = false;
1781	e->visualMovement = false;
1782	e->delayDecorations = false;
1783
1784	e->layoutData = nullptr;
1785
1786	e->minWidth = 0;
1787	e->maxWidth = 0;
1788
1789	e->specialData = nullptr;
1790	e->stackEngine = false;
1791	#ifndef QT_NO_RAWFONT
1792	e->useRawFont = false;
1793	#endif
1794	}
1795
1796	QTextEngine::QTextEngine()
1797	{
1798	init(e: this);
1799	}
1800
1801	QTextEngine::QTextEngine(const QString &str, const QFont &f)
1802	: text(str),
1803	fnt(f)
1804	{
1805	init(e: this);
1806	}
1807
1808	QTextEngine::~QTextEngine()
1809	{
1810	if (!stackEngine)
1811	delete layoutData;
1812	delete specialData;
1813	resetFontEngineCache();
1814	}
1815
1816	const QCharAttributes *QTextEngine::attributes() const
1817	{
1818	if (layoutData && layoutData->haveCharAttributes)
1819	return (QCharAttributes *) layoutData->memory;
1820
1821	itemize();
1822	if (! ensureSpace(nGlyphs: layoutData->string.size()))
1823	return nullptr;
1824
1825	QVarLengthArray<QUnicodeTools::ScriptItem> scriptItems(layoutData->items.size());
1826	for (int i = 0; i < layoutData->items.size(); ++i) {
1827	const QScriptItem &si = layoutData->items.at(i);
1828	scriptItems[i].position = si.position;
1829	scriptItems[i].script = QChar::Script(si.analysis.script);
1830	}
1831
1832	QUnicodeTools::initCharAttributes(
1833	str: layoutData->string,
1834	items: scriptItems.data(), numItems: scriptItems.size(),
1835	attributes: reinterpret_cast<QCharAttributes *>(layoutData->memory),
1836	options: QUnicodeTools::CharAttributeOptions(QUnicodeTools::GraphemeBreaks
1837	| QUnicodeTools::LineBreaks
1838	| QUnicodeTools::WhiteSpaces
1839	| QUnicodeTools::HangulLineBreakTailoring));
1840
1841
1842	layoutData->haveCharAttributes = true;
1843	return (QCharAttributes *) layoutData->memory;
1844	}
1845
1846	void QTextEngine::shape(int item) const
1847	{
1848	auto &li = layoutData->items[item];
1849	if (li.analysis.flags == QScriptAnalysis::Object) {
1850	ensureSpace(nGlyphs: 1);
1851	if (QTextDocumentPrivate::get(block) != nullptr) {
1852	docLayout()->resizeInlineObject(item: QTextInlineObject(item, const_cast<QTextEngine *>(this)),
1853	posInDocument: li.position + block.position(),
1854	format: format(si: &li));
1855	}
1856	// fix log clusters to point to the previous glyph, as the object doesn't have a glyph of it's own.
1857	// This is required so that all entries in the array get initialized and are ordered correctly.
1858	if (layoutData->logClustersPtr) {
1859	ushort *lc = logClusters(si: &li);
1860	*lc = (lc != layoutData->logClustersPtr) ? lc[-1] : 0;
1861	}
1862	} else if (li.analysis.flags == QScriptAnalysis::Tab) {
1863	// set up at least the ascent/descent/leading of the script item for the tab
1864	fontEngine(si: li, ascent: &li.ascent, descent: &li.descent, leading: &li.leading);
1865	// see the comment above
1866	if (layoutData->logClustersPtr) {
1867	ushort *lc = logClusters(si: &li);
1868	*lc = (lc != layoutData->logClustersPtr) ? lc[-1] : 0;
1869	}
1870	} else {
1871	shapeText(item);
1872	}
1873	}
1874
1875	static inline void releaseCachedFontEngine(QFontEngine *fontEngine)
1876	{
1877	if (fontEngine && !fontEngine->ref.deref())
1878	delete fontEngine;
1879	}
1880
1881	void QTextEngine::resetFontEngineCache()
1882	{
1883	releaseCachedFontEngine(fontEngine: feCache.prevFontEngine);
1884	releaseCachedFontEngine(fontEngine: feCache.prevScaledFontEngine);
1885	feCache.reset();
1886	}
1887
1888	void QTextEngine::invalidate()
1889	{
1890	freeMemory();
1891	minWidth = 0;
1892	maxWidth = 0;
1893
1894	resetFontEngineCache();
1895	}
1896
1897	void QTextEngine::clearLineData()
1898	{
1899	lines.clear();
1900	}
1901
1902	void QTextEngine::validate() const
1903	{
1904	if (layoutData)
1905	return;
1906	layoutData = new LayoutData();
1907	if (QTextDocumentPrivate::get(block) != nullptr) {
1908	layoutData->string = block.text();
1909	const bool nextBlockValid = block.next().isValid();
1910	if (!nextBlockValid && option.flags() & QTextOption::ShowDocumentTerminator) {
1911	layoutData->string += QLatin1Char('\xA7');
1912	} else if (option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
1913	layoutData->string += QLatin1Char(nextBlockValid ? '\xB6' : '\x20');
1914	}
1915
1916	} else {
1917	layoutData->string = text;
1918	}
1919	if (specialData && specialData->preeditPosition != -1)
1920	layoutData->string.insert(i: specialData->preeditPosition, s: specialData->preeditText);
1921	}
1922
1923	void QTextEngine::itemize() const
1924	{
1925	validate();
1926	if (layoutData->items.size())
1927	return;
1928
1929	int length = layoutData->string.size();
1930	if (!length)
1931	return;
1932
1933	const ushort *string = reinterpret_cast<const ushort *>(layoutData->string.unicode());
1934
1935	bool rtl = isRightToLeft();
1936
1937	QVarLengthArray<QScriptAnalysis, 4096> scriptAnalysis(length);
1938	QScriptAnalysis *analysis = scriptAnalysis.data();
1939
1940	QBidiAlgorithm bidi(layoutData->string.constData(), analysis, length, rtl);
1941	layoutData->hasBidi = bidi.process();
1942
1943	{
1944	QUnicodeTools::ScriptItemArray scriptItems;
1945	QUnicodeTools::initScripts(str: layoutData->string, scripts: &scriptItems);
1946	for (int i = 0; i < scriptItems.size(); ++i) {
1947	const auto &item = scriptItems.at(idx: i);
1948	int end = i < scriptItems.size() - 1 ? scriptItems.at(idx: i + 1).position : length;
1949	for (int j = item.position; j < end; ++j)
1950	analysis[j].script = item.script;
1951	}
1952	}
1953
1954	const ushort *uc = string;
1955	const ushort *e = uc + length;
1956	while (uc < e) {
1957	switch (*uc) {
1958	case QChar::ObjectReplacementCharacter:
1959	{
1960	const QTextDocumentPrivate *doc_p = QTextDocumentPrivate::get(block);
1961	if (doc_p != nullptr
1962	&& doc_p->layout() != nullptr
1963	&& QAbstractTextDocumentLayoutPrivate::get(layout: doc_p->layout()) != nullptr
1964	&& QAbstractTextDocumentLayoutPrivate::get(layout: doc_p->layout())->hasHandlers()) {
1965	analysis->flags = QScriptAnalysis::Object;
1966	} else {
1967	analysis->flags = QScriptAnalysis::None;
1968	}
1969	}
1970	break;
1971	case QChar::LineSeparator:
1972	analysis->flags = QScriptAnalysis::LineOrParagraphSeparator;
1973	if (option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
1974	const int offset = uc - string;
1975	layoutData->string.detach();
1976	string = reinterpret_cast<const ushort *>(layoutData->string.unicode());
1977	uc = string + offset;
1978	e = string + length;
1979	*const_cast<ushort*>(uc) = 0x21B5; // visual line separator
1980	}
1981	break;
1982	case QChar::Tabulation:
1983	analysis->flags = QScriptAnalysis::Tab;
1984	analysis->bidiLevel = bidi.baseLevel;
1985	break;
1986	case QChar::Space:
1987	case QChar::Nbsp:
1988	if (option.flags() & QTextOption::ShowTabsAndSpaces) {
1989	analysis->flags = (*uc == QChar::Space) ? QScriptAnalysis::Space : QScriptAnalysis::Nbsp;
1990	break;
1991	}
1992	Q_FALLTHROUGH();
1993	default:
1994	analysis->flags = QScriptAnalysis::None;
1995	break;
1996	}
1997	++uc;
1998	++analysis;
1999	}
2000	if (option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
2001	(analysis-1)->flags = QScriptAnalysis::LineOrParagraphSeparator; // to exclude it from width
2002	}
2003
2004	Itemizer itemizer(layoutData->string, scriptAnalysis.data(), layoutData->items);
2005
2006	const QTextDocumentPrivate *p = QTextDocumentPrivate::get(block);
2007	if (p) {
2008	SpecialData *s = specialData;
2009
2010	QTextDocumentPrivate::FragmentIterator it = p->find(pos: block.position());
2011	QTextDocumentPrivate::FragmentIterator end = p->find(pos: block.position() + block.length() - 1); // -1 to omit the block separator char
2012	int format = it.value()->format;
2013
2014	int preeditPosition = s ? s->preeditPosition : INT_MAX;
2015	int prevPosition = 0;
2016	int position = prevPosition;
2017	while (1) {
2018	const QTextFragmentData * const frag = it.value();
2019	if (it == end || format != frag->format) {
2020	if (s && position >= preeditPosition) {
2021	position += s->preeditText.size();
2022	preeditPosition = INT_MAX;
2023	}
2024	Q_ASSERT(position <= length);
2025	QFont::Capitalization capitalization =
2026	formatCollection()->charFormat(index: format).hasProperty(propertyId: QTextFormat::FontCapitalization)
2027	? formatCollection()->charFormat(index: format).fontCapitalization()
2028	: formatCollection()->defaultFont().capitalization();
2029	if (s) {
2030	for (const auto &range : std::as_const(t&: s->formats)) {
2031	if (range.start + range.length <= prevPosition || range.start >= position)
2032	continue;
2033	if (range.format.hasProperty(propertyId: QTextFormat::FontCapitalization)) {
2034	if (range.start > prevPosition)
2035	itemizer.generate(start: prevPosition, length: range.start - prevPosition, caps: capitalization);
2036	int newStart = std::max(a: prevPosition, b: range.start);
2037	int newEnd = std::min(a: position, b: range.start + range.length);
2038	itemizer.generate(start: newStart, length: newEnd - newStart, caps: range.format.fontCapitalization());
2039	prevPosition = newEnd;
2040	}
2041	}
2042	}
2043	itemizer.generate(start: prevPosition, length: position - prevPosition, caps: capitalization);
2044	if (it == end) {
2045	if (position < length)
2046	itemizer.generate(start: position, length: length - position, caps: capitalization);
2047	break;
2048	}
2049	format = frag->format;
2050	prevPosition = position;
2051	}
2052	position += frag->size_array[0];
2053	++it;
2054	}
2055	} else {
2056	#ifndef QT_NO_RAWFONT
2057	if (useRawFont && specialData) {
2058	int lastIndex = 0;
2059	for (int i = 0; i < specialData->formats.size(); ++i) {
2060	const QTextLayout::FormatRange &range = specialData->formats.at(i);
2061	const QTextCharFormat &format = range.format;
2062	if (format.hasProperty(propertyId: QTextFormat::FontCapitalization)) {
2063	itemizer.generate(start: lastIndex, length: range.start - lastIndex, caps: QFont::MixedCase);
2064	itemizer.generate(start: range.start, length: range.length, caps: format.fontCapitalization());
2065	lastIndex = range.start + range.length;
2066	}
2067	}
2068	itemizer.generate(start: lastIndex, length: length - lastIndex, caps: QFont::MixedCase);
2069	} else
2070	#endif
2071	itemizer.generate(start: 0, length, caps: static_cast<QFont::Capitalization> (fnt.d->capital));
2072	}
2073
2074	addRequiredBoundaries();
2075	resolveFormats();
2076	}
2077
2078	bool QTextEngine::isRightToLeft() const
2079	{
2080	switch (option.textDirection()) {
2081	case Qt::LeftToRight:
2082	return false;
2083	case Qt::RightToLeft:
2084	return true;
2085	default:
2086	break;
2087	}
2088	if (!layoutData)
2089	itemize();
2090	// this places the cursor in the right position depending on the keyboard layout
2091	if (layoutData->string.isEmpty())
2092	return QGuiApplication::inputMethod()->inputDirection() == Qt::RightToLeft;
2093	return layoutData->string.isRightToLeft();
2094	}
2095
2096
2097	int QTextEngine::findItem(int strPos, int firstItem) const
2098	{
2099	itemize();
2100	if (strPos < 0 || strPos >= layoutData->string.size() || firstItem < 0)
2101	return -1;
2102
2103	int left = firstItem + 1;
2104	int right = layoutData->items.size()-1;
2105	while(left <= right) {
2106	int middle = ((right-left)/2)+left;
2107	if (strPos > layoutData->items.at(i: middle).position)
2108	left = middle+1;
2109	else if (strPos < layoutData->items.at(i: middle).position)
2110	right = middle-1;
2111	else {
2112	return middle;
2113	}
2114	}
2115	return right;
2116	}
2117
2118	namespace {
2119	template<typename InnerFunc>
2120	void textIterator(const QTextEngine *textEngine, int from, int len, QFixed &width, InnerFunc &&innerFunc)
2121	{
2122	for (int i = 0; i < textEngine->layoutData->items.size(); i++) {
2123	const QScriptItem *si = textEngine->layoutData->items.constData() + i;
2124	int pos = si->position;
2125	int ilen = textEngine->length(item: i);
2126	// qDebug("item %d: from %d len %d", i, pos, ilen);
2127	if (pos >= from + len)
2128	break;
2129	if (pos + ilen > from) {
2130	if (!si->num_glyphs)
2131	textEngine->shape(item: i);
2132
2133	if (si->analysis.flags == QScriptAnalysis::Object) {
2134	width += si->width;
2135	continue;
2136	} else if (si->analysis.flags == QScriptAnalysis::Tab) {
2137	width += textEngine->calculateTabWidth(index: i, x: width);
2138	continue;
2139	}
2140
2141	unsigned short *logClusters = textEngine->logClusters(si);
2142
2143	// fprintf(stderr, " logclusters:");
2144	// for (int k = 0; k < ilen; k++)
2145	// fprintf(stderr, " %d", logClusters[k]);
2146	// fprintf(stderr, "\n");
2147	// do the simple thing for now and give the first glyph in a cluster the full width, all other ones 0.
2148	int charFrom = from - pos;
2149	if (charFrom < 0)
2150	charFrom = 0;
2151	int glyphStart = logClusters[charFrom];
2152	if (charFrom > 0 && logClusters[charFrom-1] == glyphStart)
2153	while (charFrom < ilen && logClusters[charFrom] == glyphStart)
2154	charFrom++;
2155	if (charFrom < ilen) {
2156	glyphStart = logClusters[charFrom];
2157	int charEnd = from + len - 1 - pos;
2158	if (charEnd >= ilen)
2159	charEnd = ilen-1;
2160	int glyphEnd = logClusters[charEnd];
2161	while (charEnd < ilen && logClusters[charEnd] == glyphEnd)
2162	charEnd++;
2163	glyphEnd = (charEnd == ilen) ? si->num_glyphs : logClusters[charEnd];
2164
2165	// qDebug("char: start=%d end=%d / glyph: start = %d, end = %d", charFrom, charEnd, glyphStart, glyphEnd);
2166	innerFunc(glyphStart, glyphEnd, si);
2167	}
2168	}
2169	}
2170	}
2171	} // namespace
2172
2173	QFixed QTextEngine::width(int from, int len) const
2174	{
2175	itemize();
2176
2177	QFixed w = 0;
2178	// qDebug("QTextEngine::width(from = %d, len = %d), numItems=%d, strleng=%d", from, len, items.size(), string.length());
2179	textIterator(textEngine: this, from, len, width&: w, innerFunc: [this, &w](int glyphStart, int glyphEnd, const QScriptItem *si) {
2180	QGlyphLayout glyphs = this->shapedGlyphs(si);
2181	for (int j = glyphStart; j < glyphEnd; j++)
2182	w += glyphs.advances[j] * !glyphs.attributes[j].dontPrint;
2183	});
2184	// qDebug(" --> w= %d ", w);
2185	return w;
2186	}
2187
2188	glyph_metrics_t QTextEngine::boundingBox(int from, int len) const
2189	{
2190	itemize();
2191
2192	glyph_metrics_t gm;
2193
2194	textIterator(textEngine: this, from, len, width&: gm.width, innerFunc: [this, &gm](int glyphStart, int glyphEnd, const QScriptItem *si) {
2195	if (glyphStart <= glyphEnd) {
2196	QGlyphLayout glyphs = this->shapedGlyphs(si);
2197	QFontEngine *fe = this->fontEngine(si: *si);
2198	glyph_metrics_t m = fe->boundingBox(glyphs: glyphs.mid(position: glyphStart, n: glyphEnd - glyphStart));
2199	gm.x = qMin(a: gm.x, b: m.x + gm.xoff);
2200	gm.y = qMin(a: gm.y, b: m.y + gm.yoff);
2201	gm.width = qMax(a: gm.width, b: m.width + gm.xoff);
2202	gm.height = qMax(a: gm.height, b: m.height + gm.yoff);
2203	gm.xoff += m.xoff;
2204	gm.yoff += m.yoff;
2205	}
2206	});
2207
2208	return gm;
2209	}
2210
2211	glyph_metrics_t QTextEngine::tightBoundingBox(int from, int len) const
2212	{
2213	itemize();
2214
2215	glyph_metrics_t gm;
2216
2217	textIterator(textEngine: this, from, len, width&: gm.width, innerFunc: [this, &gm](int glyphStart, int glyphEnd, const QScriptItem *si) {
2218	if (glyphStart <= glyphEnd) {
2219	QGlyphLayout glyphs = this->shapedGlyphs(si);
2220	QFontEngine *fe = fontEngine(si: *si);
2221	glyph_metrics_t m = fe->tightBoundingBox(glyphs: glyphs.mid(position: glyphStart, n: glyphEnd - glyphStart));
2222	gm.x = qMin(a: gm.x, b: m.x + gm.xoff);
2223	gm.y = qMin(a: gm.y, b: m.y + gm.yoff);
2224	gm.width = qMax(a: gm.width, b: m.width + gm.xoff);
2225	gm.height = qMax(a: gm.height, b: m.height + gm.yoff);
2226	gm.xoff += m.xoff;
2227	gm.yoff += m.yoff;
2228	}
2229	});
2230	return gm;
2231	}
2232
2233	QFont QTextEngine::font(const QScriptItem &si) const
2234	{
2235	QFont font = fnt;
2236	if (hasFormats()) {
2237	QTextCharFormat f = format(si: &si);
2238	font = f.font();
2239
2240	const QTextDocumentPrivate *document_d = QTextDocumentPrivate::get(block);
2241	if (document_d != nullptr && document_d->layout() != nullptr) {
2242	// Make sure we get the right dpi on printers
2243	QPaintDevice *pdev = document_d->layout()->paintDevice();
2244	if (pdev)
2245	font = QFont(font, pdev);
2246	} else {
2247	font = font.resolve(fnt);
2248	}
2249	QTextCharFormat::VerticalAlignment valign = f.verticalAlignment();
2250	if (valign == QTextCharFormat::AlignSuperScript || valign == QTextCharFormat::AlignSubScript) {
2251	if (font.pointSize() != -1)
2252	font.setPointSize((font.pointSize() * 2) / 3);
2253	else
2254	font.setPixelSize((font.pixelSize() * 2) / 3);
2255	}
2256	}
2257
2258	if (si.analysis.flags == QScriptAnalysis::SmallCaps)
2259	font = font.d->smallCapsFont();
2260
2261	return font;
2262	}
2263
2264	QTextEngine::FontEngineCache::FontEngineCache()
2265	{
2266	reset();
2267	}
2268
2269	//we cache the previous results of this function, as calling it numerous times with the same effective
2270	//input is common (and hard to cache at a higher level)
2271	QFontEngine *QTextEngine::fontEngine(const QScriptItem &si, QFixed *ascent, QFixed *descent, QFixed *leading) const
2272	{
2273	QFontEngine *engine = nullptr;
2274	QFontEngine *scaledEngine = nullptr;
2275	int script = si.analysis.script;
2276
2277	QFont font = fnt;
2278	#ifndef QT_NO_RAWFONT
2279	if (useRawFont && rawFont.isValid()) {
2280	if (feCache.prevFontEngine && feCache.prevFontEngine->type() == QFontEngine::Multi && feCache.prevScript == script) {
2281	engine = feCache.prevFontEngine;
2282	} else {
2283	engine = QFontEngineMulti::createMultiFontEngine(fe: rawFont.d->fontEngine, script);
2284	feCache.prevFontEngine = engine;
2285	feCache.prevScript = script;
2286	engine->ref.ref();
2287	if (feCache.prevScaledFontEngine) {
2288	releaseCachedFontEngine(fontEngine: feCache.prevScaledFontEngine);
2289	feCache.prevScaledFontEngine = nullptr;
2290	}
2291	}
2292	if (si.analysis.flags == QScriptAnalysis::SmallCaps) {
2293	if (feCache.prevScaledFontEngine) {
2294	scaledEngine = feCache.prevScaledFontEngine;
2295	} else {
2296	// GCC 12 gets confused about QFontEngine::ref, for some non-obvious reason
2297	// warning: ‘unsigned int __atomic_or_fetch_4(volatile void*, unsigned int, int)’ writing 4 bytes
2298	// into a region of size 0 overflows the destination [-Wstringop-overflow=]
2299	QT_WARNING_PUSH
2300	QT_WARNING_DISABLE_GCC("-Wstringop-overflow")
2301
2302	QFontEngine *scEngine = rawFont.d->fontEngine->cloneWithSize(smallCapsFraction * rawFont.pixelSize());
2303	scEngine->ref.ref();
2304	scaledEngine = QFontEngineMulti::createMultiFontEngine(fe: scEngine, script);
2305	scaledEngine->ref.ref();
2306	feCache.prevScaledFontEngine = scaledEngine;
2307	// If scEngine is not ref'ed by scaledEngine, make sure it is deallocated and not leaked.
2308	if (!scEngine->ref.deref())
2309	delete scEngine;
2310
2311	QT_WARNING_POP
2312	}
2313	}
2314	} else
2315	#endif
2316	{
2317	if (hasFormats()) {
2318	if (feCache.prevFontEngine && feCache.prevPosition == si.position && feCache.prevLength == length(si: &si) && feCache.prevScript == script) {
2319	engine = feCache.prevFontEngine;
2320	scaledEngine = feCache.prevScaledFontEngine;
2321	} else {
2322	QTextCharFormat f = format(si: &si);
2323	font = f.font();
2324
2325	if (QTextDocumentPrivate::get(block) != nullptr && QTextDocumentPrivate::get(block)->layout() != nullptr) {
2326	// Make sure we get the right dpi on printers
2327	QPaintDevice *pdev = QTextDocumentPrivate::get(block)->layout()->paintDevice();
2328	if (pdev)
2329	font = QFont(font, pdev);
2330	} else {
2331	font = font.resolve(fnt);
2332	}
2333	engine = font.d->engineForScript(script);
2334	Q_ASSERT(engine);
2335	engine->ref.ref();
2336
2337	QTextCharFormat::VerticalAlignment valign = f.verticalAlignment();
2338	if (valign == QTextCharFormat::AlignSuperScript || valign == QTextCharFormat::AlignSubScript) {
2339	if (font.pointSize() != -1)
2340	font.setPointSize((font.pointSize() * 2) / 3);
2341	else
2342	font.setPixelSize((font.pixelSize() * 2) / 3);
2343	scaledEngine = font.d->engineForScript(script);
2344	if (scaledEngine)
2345	scaledEngine->ref.ref();
2346	}
2347
2348	if (feCache.prevFontEngine)
2349	releaseCachedFontEngine(fontEngine: feCache.prevFontEngine);
2350	feCache.prevFontEngine = engine;
2351
2352	if (feCache.prevScaledFontEngine)
2353	releaseCachedFontEngine(fontEngine: feCache.prevScaledFontEngine);
2354	feCache.prevScaledFontEngine = scaledEngine;
2355
2356	feCache.prevScript = script;
2357	feCache.prevPosition = si.position;
2358	feCache.prevLength = length(si: &si);
2359	}
2360	} else {
2361	if (feCache.prevFontEngine && feCache.prevScript == script && feCache.prevPosition == -1) {
2362	engine = feCache.prevFontEngine;
2363	} else {
2364	engine = font.d->engineForScript(script);
2365	Q_ASSERT(engine);
2366	engine->ref.ref();
2367	if (feCache.prevFontEngine)
2368	releaseCachedFontEngine(fontEngine: feCache.prevFontEngine);
2369	feCache.prevFontEngine = engine;
2370
2371	feCache.prevScript = script;
2372	feCache.prevPosition = -1;
2373	feCache.prevLength = -1;
2374	feCache.prevScaledFontEngine = nullptr;
2375	}
2376	}
2377
2378	if (si.analysis.flags == QScriptAnalysis::SmallCaps) {
2379	QFontPrivate *p = font.d->smallCapsFontPrivate();
2380	scaledEngine = p->engineForScript(script);
2381	}
2382	}
2383
2384	if (leading) {
2385	Q_ASSERT(engine);
2386	Q_ASSERT(ascent);
2387	Q_ASSERT(descent);
2388	*ascent = engine->ascent();
2389	*descent = engine->descent();
2390	*leading = engine->leading();
2391	}
2392
2393	if (scaledEngine)
2394	return scaledEngine;
2395	return engine;
2396	}
2397
2398	struct QJustificationPoint {
2399	int type;
2400	QFixed kashidaWidth;
2401	QGlyphLayout glyph;
2402	};
2403
2404	Q_DECLARE_TYPEINFO(QJustificationPoint, Q_PRIMITIVE_TYPE);
2405
2406	static void set(QJustificationPoint *point, int type, const QGlyphLayout &glyph, QFontEngine *fe)
2407	{
2408	point->type = type;
2409	point->glyph = glyph;
2410
2411	if (type >= Justification_Arabic_Normal) {
2412	const char32_t ch = U'\x640'; // Kashida character
2413
2414	glyph_t kashidaGlyph = fe->glyphIndex(ucs4: ch);
2415	if (kashidaGlyph != 0) {
2416	QGlyphLayout g;
2417	g.numGlyphs = 1;
2418	g.glyphs = &kashidaGlyph;
2419	g.advances = &point->kashidaWidth;
2420	fe->recalcAdvances(&g, { });
2421
2422	if (point->kashidaWidth == 0)
2423	point->type = Justification_Prohibited;
2424	} else {
2425	point->type = Justification_Prohibited;
2426	point->kashidaWidth = 0;
2427	}
2428	}
2429	}
2430
2431
2432	void QTextEngine::justify(const QScriptLine &line)
2433	{
2434	// qDebug("justify: line.gridfitted = %d, line.justified=%d", line.gridfitted, line.justified);
2435	if (line.gridfitted && line.justified)
2436	return;
2437
2438	if (!line.gridfitted) {
2439	// redo layout in device metrics, then adjust
2440	const_cast<QScriptLine &>(line).gridfitted = true;
2441	}
2442
2443	if ((option.alignment() & Qt::AlignHorizontal_Mask) != Qt::AlignJustify)
2444	return;
2445
2446	itemize();
2447
2448	if (!forceJustification) {
2449	int end = line.from + (int)line.length + line.trailingSpaces;
2450	if (end == layoutData->string.size())
2451	return; // no justification at end of paragraph
2452	if (end && layoutData->items.at(i: findItem(strPos: end - 1)).analysis.flags == QScriptAnalysis::LineOrParagraphSeparator)
2453	return; // no justification at the end of an explicitly separated line
2454	}
2455
2456	// justify line
2457	int maxJustify = 0;
2458
2459	// don't include trailing white spaces when doing justification
2460	int line_length = line.length;
2461	const QCharAttributes *a = attributes();
2462	if (! a)
2463	return;
2464	a += line.from;
2465	while (line_length && a[line_length-1].whiteSpace)
2466	--line_length;
2467	// subtract one char more, as we can't justfy after the last character
2468	--line_length;
2469
2470	if (line_length <= 0)
2471	return;
2472
2473	int firstItem = findItem(strPos: line.from);
2474	int lastItem = findItem(strPos: line.from + line_length - 1, firstItem);
2475	int nItems = (firstItem >= 0 && lastItem >= firstItem)? (lastItem-firstItem+1) : 0;
2476
2477	QVarLengthArray<QJustificationPoint> justificationPoints;
2478	int nPoints = 0;
2479	// qDebug("justifying from %d len %d, firstItem=%d, nItems=%d (%s)", line.from, line_length, firstItem, nItems, layoutData->string.mid(line.from, line_length).toUtf8().constData());
2480	QFixed minKashida = 0x100000;
2481
2482	// we need to do all shaping before we go into the next loop, as we there
2483	// store pointers to the glyph data that could get reallocated by the shaping
2484	// process.
2485	for (int i = 0; i < nItems; ++i) {
2486	const QScriptItem &si = layoutData->items.at(i: firstItem + i);
2487	if (!si.num_glyphs)
2488	shape(item: firstItem + i);
2489	}
2490
2491	for (int i = 0; i < nItems; ++i) {
2492	const QScriptItem &si = layoutData->items.at(i: firstItem + i);
2493
2494	int kashida_type = Justification_Arabic_Normal;
2495	int kashida_pos = -1;
2496
2497	int start = qMax(a: line.from - si.position, b: 0);
2498	int end = qMin(a: line.from + line_length - (int)si.position, b: length(item: firstItem+i));
2499
2500	unsigned short *log_clusters = logClusters(si: &si);
2501
2502	int gs = log_clusters[start];
2503	int ge = (end == length(item: firstItem+i) ? si.num_glyphs : log_clusters[end]);
2504
2505	Q_ASSERT(ge <= si.num_glyphs);
2506
2507	const QGlyphLayout g = shapedGlyphs(si: &si);
2508
2509	for (int i = gs; i < ge; ++i) {
2510	g.justifications[i].type = QGlyphJustification::JustifyNone;
2511	g.justifications[i].nKashidas = 0;
2512	g.justifications[i].space_18d6 = 0;
2513
2514	justificationPoints.resize(sz: nPoints+3);
2515	int justification = g.attributes[i].justification;
2516
2517	switch(justification) {
2518	case Justification_Prohibited:
2519	break;
2520	case Justification_Space:
2521	case Justification_Arabic_Space:
2522	if (kashida_pos >= 0) {
2523	// qDebug("kashida position at %d in word", kashida_pos);
2524	set(point: &justificationPoints[nPoints], type: kashida_type, glyph: g.mid(position: kashida_pos), fe: fontEngine(si));
2525	if (justificationPoints[nPoints].kashidaWidth > 0) {
2526	minKashida = qMin(a: minKashida, b: justificationPoints[nPoints].kashidaWidth);
2527	maxJustify = qMax(a: maxJustify, b: justificationPoints[nPoints].type);
2528	++nPoints;
2529	}
2530	}
2531	kashida_pos = -1;
2532	kashida_type = Justification_Arabic_Normal;
2533	Q_FALLTHROUGH();
2534	case Justification_Character:
2535	set(point: &justificationPoints[nPoints++], type: justification, glyph: g.mid(position: i), fe: fontEngine(si));
2536	maxJustify = qMax(a: maxJustify, b: justification);
2537	break;
2538	case Justification_Arabic_Normal:
2539	case Justification_Arabic_Waw:
2540	case Justification_Arabic_BaRa:
2541	case Justification_Arabic_Alef:
2542	case Justification_Arabic_HahDal:
2543	case Justification_Arabic_Seen:
2544	case Justification_Arabic_Kashida:
2545	if (justification >= kashida_type) {
2546	kashida_pos = i;
2547	kashida_type = justification;
2548	}
2549	}
2550	}
2551	if (kashida_pos >= 0) {
2552	set(point: &justificationPoints[nPoints], type: kashida_type, glyph: g.mid(position: kashida_pos), fe: fontEngine(si));
2553	if (justificationPoints[nPoints].kashidaWidth > 0) {
2554	minKashida = qMin(a: minKashida, b: justificationPoints[nPoints].kashidaWidth);
2555	maxJustify = qMax(a: maxJustify, b: justificationPoints[nPoints].type);
2556	++nPoints;
2557	}
2558	}
2559	}
2560
2561	QFixed leading = leadingSpaceWidth(line);
2562	QFixed need = line.width - line.textWidth - leading;
2563	if (need < 0) {
2564	// line overflows already!
2565	const_cast<QScriptLine &>(line).justified = true;
2566	return;
2567	}
2568
2569	// qDebug("doing justification: textWidth=%x, requested=%x, maxJustify=%d", line.textWidth.value(), line.width.value(), maxJustify);
2570	// qDebug(" minKashida=%f, need=%f", minKashida.toReal(), need.toReal());
2571
2572	// distribute in priority order
2573	if (maxJustify >= Justification_Arabic_Normal) {
2574	while (need >= minKashida) {
2575	for (int type = maxJustify; need >= minKashida && type >= Justification_Arabic_Normal; --type) {
2576	for (int i = 0; need >= minKashida && i < nPoints; ++i) {
2577	if (justificationPoints[i].type == type && justificationPoints[i].kashidaWidth <= need) {
2578	justificationPoints[i].glyph.justifications->nKashidas++;
2579	// ############
2580	justificationPoints[i].glyph.justifications->space_18d6 += justificationPoints[i].kashidaWidth.value();
2581	need -= justificationPoints[i].kashidaWidth;
2582	// qDebug("adding kashida type %d with width %x, neednow %x", type, justificationPoints[i].kashidaWidth, need.value());
2583	}
2584	}
2585	}
2586	}
2587	}
2588	Q_ASSERT(need >= 0);
2589	if (!need)
2590	goto end;
2591
2592	maxJustify = qMin(a: maxJustify, b: int(Justification_Space));
2593	for (int type = maxJustify; need != 0 && type > 0; --type) {
2594	int n = 0;
2595	for (int i = 0; i < nPoints; ++i) {
2596	if (justificationPoints[i].type == type)
2597	++n;
2598	}
2599	// qDebug("number of points for justification type %d: %d", type, n);
2600
2601
2602	if (!n)
2603	continue;
2604
2605	for (int i = 0; i < nPoints; ++i) {
2606	if (justificationPoints[i].type == type) {
2607	QFixed add = need/n;
2608	// qDebug("adding %x to glyph %x", add.value(), justificationPoints[i].glyph->glyph);
2609	justificationPoints[i].glyph.justifications[0].space_18d6 = add.value();
2610	need -= add;
2611	--n;
2612	}
2613	}
2614
2615	Q_ASSERT(!need);
2616	}
2617	end:
2618	const_cast<QScriptLine &>(line).justified = true;
2619	}
2620
2621	void QScriptLine::setDefaultHeight(QTextEngine *eng)
2622	{
2623	QFont f;
2624	QFontEngine *e;
2625
2626	if (QTextDocumentPrivate::get(block&: eng->block) != nullptr && QTextDocumentPrivate::get(block&: eng->block)->layout() != nullptr) {
2627	f = eng->block.charFormat().font();
2628	// Make sure we get the right dpi on printers
2629	QPaintDevice *pdev = QTextDocumentPrivate::get(block&: eng->block)->layout()->paintDevice();
2630	if (pdev)
2631	f = QFont(f, pdev);
2632	e = f.d->engineForScript(script: QChar::Script_Common);
2633	} else {
2634	e = eng->fnt.d->engineForScript(script: QChar::Script_Common);
2635	}
2636
2637	QFixed other_ascent = e->ascent();
2638	QFixed other_descent = e->descent();
2639	QFixed other_leading = e->leading();
2640	leading = qMax(a: leading + ascent, b: other_leading + other_ascent) - qMax(a: ascent, b: other_ascent);
2641	ascent = qMax(a: ascent, b: other_ascent);
2642	descent = qMax(a: descent, b: other_descent);
2643	}
2644
2645	QTextEngine::LayoutData::LayoutData()
2646	{
2647	memory = nullptr;
2648	allocated = 0;
2649	memory_on_stack = false;
2650	used = 0;
2651	hasBidi = false;
2652	layoutState = LayoutEmpty;
2653	haveCharAttributes = false;
2654	logClustersPtr = nullptr;
2655	available_glyphs = 0;
2656	currentMaxWidth = 0;
2657	}
2658
2659	QTextEngine::LayoutData::LayoutData(const QString &str, void **stack_memory, qsizetype _allocated)
2660	: string(str)
2661	{
2662	allocated = _allocated;
2663
2664	constexpr qsizetype voidSize = sizeof(void*);
2665	qsizetype space_charAttributes = sizeof(QCharAttributes) * string.size() / voidSize + 1;
2666	qsizetype space_logClusters = sizeof(unsigned short) * string.size() / voidSize + 1;
2667	available_glyphs = (allocated - space_charAttributes - space_logClusters) * voidSize / QGlyphLayout::SpaceNeeded;
2668
2669	if (available_glyphs < str.size()) {
2670	// need to allocate on the heap
2671	allocated = 0;
2672
2673	memory_on_stack = false;
2674	memory = nullptr;
2675	logClustersPtr = nullptr;
2676	} else {
2677	memory_on_stack = true;
2678	memory = stack_memory;
2679	logClustersPtr = (unsigned short *)(memory + space_charAttributes);
2680
2681	void *m = memory + space_charAttributes + space_logClusters;
2682	glyphLayout = QGlyphLayout(reinterpret_cast<char *>(m), str.size());
2683	glyphLayout.clear();
2684	memset(s: memory, c: 0, n: space_charAttributes*sizeof(void *));
2685	}
2686	used = 0;
2687	hasBidi = false;
2688	layoutState = LayoutEmpty;
2689	haveCharAttributes = false;
2690	currentMaxWidth = 0;
2691	}
2692
2693	QTextEngine::LayoutData::~LayoutData()
2694	{
2695	if (!memory_on_stack)
2696	free(ptr: memory);
2697	memory = nullptr;
2698	}
2699
2700	bool QTextEngine::LayoutData::reallocate(int totalGlyphs)
2701	{
2702	Q_ASSERT(totalGlyphs >= glyphLayout.numGlyphs);
2703	if (memory_on_stack && available_glyphs >= totalGlyphs) {
2704	glyphLayout.grow(address: glyphLayout.data(), totalGlyphs);
2705	return true;
2706	}
2707
2708	const qsizetype space_charAttributes = (sizeof(QCharAttributes) * string.size() / sizeof(void*) + 1);
2709	const qsizetype space_logClusters = (sizeof(unsigned short) * string.size() / sizeof(void*) + 1);
2710	const qsizetype space_glyphs = qsizetype(totalGlyphs) * QGlyphLayout::SpaceNeeded / sizeof(void *) + 2;
2711
2712	const qsizetype newAllocated = space_charAttributes + space_glyphs + space_logClusters;
2713	// Check if the length of string/glyphs causes int overflow,
2714	// we can't layout such a long string all at once, so return false here to
2715	// indicate there is a failure
2716	if (size_t(space_charAttributes) > INT_MAX || size_t(space_logClusters) > INT_MAX || totalGlyphs < 0
2717	|| size_t(space_glyphs) > INT_MAX || size_t(newAllocated) > INT_MAX || newAllocated < allocated) {
2718	layoutState = LayoutFailed;
2719	return false;
2720	}
2721
2722	void **newMem = (void **)::realloc(ptr: memory_on_stack ? nullptr : memory, size: newAllocated*sizeof(void *));
2723	if (!newMem) {
2724	layoutState = LayoutFailed;
2725	return false;
2726	}
2727	if (memory_on_stack)
2728	memcpy(dest: newMem, src: memory, n: allocated*sizeof(void *));
2729	memory = newMem;
2730	memory_on_stack = false;
2731
2732	void **m = memory;
2733	m += space_charAttributes;
2734	logClustersPtr = (unsigned short *) m;
2735	m += space_logClusters;
2736
2737	const qsizetype space_preGlyphLayout = space_charAttributes + space_logClusters;
2738	if (allocated < space_preGlyphLayout)
2739	memset(s: memory + allocated, c: 0, n: (space_preGlyphLayout - allocated)*sizeof(void *));
2740
2741	glyphLayout.grow(address: reinterpret_cast<char *>(m), totalGlyphs);
2742
2743	allocated = newAllocated;
2744	return true;
2745	}
2746
2747	void QGlyphLayout::copy(QGlyphLayout *oldLayout)
2748	{
2749	Q_ASSERT(offsets != oldLayout->offsets);
2750
2751	int n = std::min(a: numGlyphs, b: oldLayout->numGlyphs);
2752
2753	memcpy(dest: offsets, src: oldLayout->offsets, n: n * sizeof(QFixedPoint));
2754	memcpy(dest: attributes, src: oldLayout->attributes, n: n * sizeof(QGlyphAttributes));
2755	memcpy(dest: justifications, src: oldLayout->justifications, n: n * sizeof(QGlyphJustification));
2756	memcpy(dest: advances, src: oldLayout->advances, n: n * sizeof(QFixed));
2757	memcpy(dest: glyphs, src: oldLayout->glyphs, n: n * sizeof(glyph_t));
2758
2759	numGlyphs = n;
2760	}
2761
2762	// grow to the new size, copying the existing data to the new layout
2763	void QGlyphLayout::grow(char *address, int totalGlyphs)
2764	{
2765	QGlyphLayout oldLayout(address, numGlyphs);
2766	QGlyphLayout newLayout(address, totalGlyphs);
2767
2768	if (numGlyphs) {
2769	// move the existing data
2770	memmove(dest: newLayout.attributes, src: oldLayout.attributes, n: numGlyphs * sizeof(QGlyphAttributes));
2771	memmove(dest: newLayout.justifications, src: oldLayout.justifications, n: numGlyphs * sizeof(QGlyphJustification));
2772	memmove(dest: newLayout.advances, src: oldLayout.advances, n: numGlyphs * sizeof(QFixed));
2773	memmove(dest: newLayout.glyphs, src: oldLayout.glyphs, n: numGlyphs * sizeof(glyph_t));
2774	}
2775
2776	// clear the new data
2777	newLayout.clear(first: numGlyphs);
2778
2779	*this = newLayout;
2780	}
2781
2782	void QTextEngine::freeMemory()
2783	{
2784	if (!stackEngine) {
2785	delete layoutData;
2786	layoutData = nullptr;
2787	} else {
2788	layoutData->used = 0;
2789	layoutData->hasBidi = false;
2790	layoutData->layoutState = LayoutEmpty;
2791	layoutData->haveCharAttributes = false;
2792	layoutData->currentMaxWidth = 0;
2793	layoutData->items.clear();
2794	}
2795	if (specialData)
2796	specialData->resolvedFormats.clear();
2797	for (int i = 0; i < lines.size(); ++i) {
2798	lines[i].justified = 0;
2799	lines[i].gridfitted = 0;
2800	}
2801	}
2802
2803	int QTextEngine::formatIndex(const QScriptItem *si) const
2804	{
2805	if (specialData && !specialData->resolvedFormats.isEmpty()) {
2806	QTextFormatCollection *collection = formatCollection();
2807	Q_ASSERT(collection);
2808	return collection->indexForFormat(f: specialData->resolvedFormats.at(i: si - &layoutData->items.at(i: 0)));
2809	}
2810
2811	const QTextDocumentPrivate *p = QTextDocumentPrivate::get(block);
2812	if (!p)
2813	return -1;
2814	int pos = si->position;
2815	if (specialData && si->position >= specialData->preeditPosition) {
2816	if (si->position < specialData->preeditPosition + specialData->preeditText.size())
2817	pos = qMax(a: qMin(a: block.length(), b: specialData->preeditPosition) - 1, b: 0);
2818	else
2819	pos -= specialData->preeditText.size();
2820	}
2821	QTextDocumentPrivate::FragmentIterator it = p->find(pos: block.position() + pos);
2822	return it.value()->format;
2823	}
2824
2825
2826	QTextCharFormat QTextEngine::format(const QScriptItem *si) const
2827	{
2828	if (const QTextFormatCollection *collection = formatCollection())
2829	return collection->charFormat(index: formatIndex(si));
2830	return QTextCharFormat();
2831	}
2832
2833	void QTextEngine::addRequiredBoundaries() const
2834	{
2835	if (specialData) {
2836	for (int i = 0; i < specialData->formats.size(); ++i) {
2837	const QTextLayout::FormatRange &r = specialData->formats.at(i);
2838	setBoundary(r.start);
2839	setBoundary(r.start + r.length);
2840	//qDebug("adding boundaries %d %d", r.start, r.start+r.length);
2841	}
2842	}
2843	}
2844
2845	bool QTextEngine::atWordSeparator(int position) const
2846	{
2847	const QChar c = layoutData->string.at(i: position);
2848	switch (c.unicode()) {
2849	case '.':
2850	case ',':
2851	case '?':
2852	case '!':
2853	case '@':
2854	case '#':
2855	case '$':
2856	case ':':
2857	case ';':
2858	case '-':
2859	case '<':
2860	case '>':
2861	case '[':
2862	case ']':
2863	case '(':
2864	case ')':
2865	case '{':
2866	case '}':
2867	case '=':
2868	case '/':
2869	case '+':
2870	case '%':
2871	case '&':
2872	case '^':
2873	case '*':
2874	case '\'':
2875	case '"':
2876	case '`':
2877	case '~':
2878	case '|':
2879	case '\\':
2880	return true;
2881	default:
2882	break;
2883	}
2884	return false;
2885	}
2886
2887	void QTextEngine::setPreeditArea(int position, const QString &preeditText)
2888	{
2889	if (preeditText.isEmpty()) {
2890	if (!specialData)
2891	return;
2892	if (specialData->formats.isEmpty()) {
2893	delete specialData;
2894	specialData = nullptr;
2895	} else {
2896	specialData->preeditText = QString();
2897	specialData->preeditPosition = -1;
2898	}
2899	} else {
2900	if (!specialData)
2901	specialData = new SpecialData;
2902	specialData->preeditPosition = position;
2903	specialData->preeditText = preeditText;
2904	}
2905	invalidate();
2906	clearLineData();
2907	}
2908
2909	void QTextEngine::setFormats(const QList<QTextLayout::FormatRange> &formats)
2910	{
2911	if (formats.isEmpty()) {
2912	if (!specialData)
2913	return;
2914	if (specialData->preeditText.isEmpty()) {
2915	delete specialData;
2916	specialData = nullptr;
2917	} else {
2918	specialData->formats.clear();
2919	}
2920	} else {
2921	if (!specialData) {
2922	specialData = new SpecialData;
2923	specialData->preeditPosition = -1;
2924	}
2925	specialData->formats = formats;
2926	indexFormats();
2927	}
2928	invalidate();
2929	clearLineData();
2930	}
2931
2932	void QTextEngine::indexFormats()
2933	{
2934	QTextFormatCollection *collection = formatCollection();
2935	if (!collection) {
2936	Q_ASSERT(QTextDocumentPrivate::get(block) == nullptr);
2937	specialData->formatCollection.reset(other: new QTextFormatCollection);
2938	collection = specialData->formatCollection.data();
2939	}
2940
2941	// replace with shared copies
2942	for (int i = 0; i < specialData->formats.size(); ++i) {
2943	QTextCharFormat &format = specialData->formats[i].format;
2944	format = collection->charFormat(index: collection->indexForFormat(f: format));
2945	}
2946	}
2947
2948	/* These two helper functions are used to determine whether we need to insert a ZWJ character
2949	between the text that gets truncated and the ellipsis. This is important to get
2950	correctly shaped results for arabic text.
2951	*/
2952	static inline bool nextCharJoins(const QString &string, int pos)
2953	{
2954	while (pos < string.size() && string.at(i: pos).category() == QChar::Mark_NonSpacing)
2955	++pos;
2956	if (pos == string.size())
2957	return false;
2958	QChar::JoiningType joining = string.at(i: pos).joiningType();
2959	return joining != QChar::Joining_None && joining != QChar::Joining_Transparent;
2960	}
2961
2962	static inline bool prevCharJoins(const QString &string, int pos)
2963	{
2964	while (pos > 0 && string.at(i: pos - 1).category() == QChar::Mark_NonSpacing)
2965	--pos;
2966	if (pos == 0)
2967	return false;
2968	QChar::JoiningType joining = string.at(i: pos - 1).joiningType();
2969	return joining == QChar::Joining_Dual || joining == QChar::Joining_Causing;
2970	}
2971
2972	static constexpr bool isRetainableControlCode(char16_t c) noexcept
2973	{
2974	return (c >= 0x202a && c <= 0x202e) // LRE, RLE, PDF, LRO, RLO
2975	|| (c >= 0x200e && c <= 0x200f) // LRM, RLM
2976	|| (c >= 0x2066 && c <= 0x2069); // LRI, RLI, FSI, PDI
2977	}
2978
2979	static QString stringMidRetainingBidiCC(const QString &string,
2980	const QString &ellidePrefix,
2981	const QString &ellideSuffix,
2982	int subStringFrom,
2983	int subStringTo,
2984	int midStart,
2985	int midLength)
2986	{
2987	QString prefix;
2988	for (int i=subStringFrom; i<midStart; ++i) {
2989	char16_t c = string.at(i).unicode();
2990	if (isRetainableControlCode(c))
2991	prefix += c;
2992	}
2993
2994	QString suffix;
2995	for (int i=midStart + midLength; i<subStringTo; ++i) {
2996	char16_t c = string.at(i).unicode();
2997	if (isRetainableControlCode(c))
2998	suffix += c;
2999	}
3000
3001	return prefix + ellidePrefix + QStringView{string}.mid(pos: midStart, n: midLength) + ellideSuffix + suffix;
3002	}
3003
3004	QString QTextEngine::elidedText(Qt::TextElideMode mode, QFixed width, int flags, int from, int count) const
3005	{
3006	// qDebug() << "elidedText; available width" << width.toReal() << "text width:" << this->width(0, layoutData->string.length()).toReal();
3007
3008	if (flags & Qt::TextShowMnemonic) {
3009	itemize();
3010	QCharAttributes *attributes = const_cast<QCharAttributes *>(this->attributes());
3011	if (!attributes)
3012	return QString();
3013	for (int i = 0; i < layoutData->items.size(); ++i) {
3014	const QScriptItem &si = layoutData->items.at(i);
3015	if (!si.num_glyphs)
3016	shape(item: i);
3017
3018	unsigned short *logClusters = this->logClusters(si: &si);
3019	QGlyphLayout glyphs = shapedGlyphs(si: &si);
3020
3021	const int end = si.position + length(si: &si);
3022	for (int i = si.position; i < end - 1; ++i) {
3023	if (layoutData->string.at(i) == u'&'
3024	&& !attributes[i + 1].whiteSpace && attributes[i + 1].graphemeBoundary) {
3025	const int gp = logClusters[i - si.position];
3026	glyphs.attributes[gp].dontPrint = true;
3027	// emulate grapheme cluster
3028	attributes[i] = attributes[i + 1];
3029	memset(s: attributes + i + 1, c: 0, n: sizeof(QCharAttributes));
3030	if (layoutData->string.at(i: i + 1) == u'&')
3031	++i;
3032	}
3033	}
3034	}
3035	}
3036
3037	validate();
3038
3039	const int to = count >= 0 && count <= layoutData->string.size() - from
3040	? from + count
3041	: layoutData->string.size();
3042
3043	if (mode == Qt::ElideNone
3044	|| this->width(from, len: layoutData->string.size()) <= width
3045	|| to - from <= 1)
3046	return layoutData->string.mid(position: from, n: from - to);
3047
3048	QFixed ellipsisWidth;
3049	QString ellipsisText;
3050	{
3051	QFontEngine *engine = fnt.d->engineForScript(script: QChar::Script_Common);
3052
3053	constexpr char16_t ellipsisChar = u'\x2026';
3054
3055	// We only want to use the ellipsis character if it is from the main
3056	// font (not one of the fallbacks), since using a fallback font
3057	// will affect the metrics of the text, potentially causing it to shift
3058	// when it is being elided.
3059	if (engine->type() == QFontEngine::Multi) {
3060	QFontEngineMulti *multiEngine = static_cast<QFontEngineMulti *>(engine);
3061	multiEngine->ensureEngineAt(at: 0);
3062	engine = multiEngine->engine(at: 0);
3063	}
3064
3065	glyph_t glyph = engine->glyphIndex(ucs4: ellipsisChar);
3066
3067	QGlyphLayout glyphs;
3068	glyphs.numGlyphs = 1;
3069	glyphs.glyphs = &glyph;
3070	glyphs.advances = &ellipsisWidth;
3071
3072	if (glyph != 0) {
3073	engine->recalcAdvances(&glyphs, { });
3074
3075	ellipsisText = ellipsisChar;
3076	} else {
3077	glyph = engine->glyphIndex(ucs4: '.');
3078	if (glyph != 0) {
3079	engine->recalcAdvances(&glyphs, { });
3080
3081	ellipsisWidth *= 3;
3082	ellipsisText = QStringLiteral("...");
3083	} else {
3084	engine = fnt.d->engineForScript(script: QChar::Script_Common);
3085	glyph = engine->glyphIndex(ucs4: ellipsisChar);
3086	engine->recalcAdvances(&glyphs, { });
3087	ellipsisText = ellipsisChar;
3088	}
3089	}
3090	}
3091
3092	const QFixed availableWidth = width - ellipsisWidth;
3093	if (availableWidth < 0)
3094	return QString();
3095
3096	const QCharAttributes *attributes = this->attributes();
3097	if (!attributes)
3098	return QString();
3099
3100	constexpr char16_t ZWJ = u'\x200d'; // ZERO-WIDTH JOINER
3101
3102	if (mode == Qt::ElideRight) {
3103	QFixed currentWidth;
3104	int pos;
3105	int nextBreak = from;
3106
3107	do {
3108	pos = nextBreak;
3109
3110	++nextBreak;
3111	while (nextBreak < layoutData->string.size() && !attributes[nextBreak].graphemeBoundary)
3112	++nextBreak;
3113
3114	currentWidth += this->width(from: pos, len: nextBreak - pos);
3115	} while (nextBreak < to
3116	&& currentWidth < availableWidth);
3117
3118	if (nextCharJoins(string: layoutData->string, pos))
3119	ellipsisText.prepend(c: ZWJ);
3120
3121	return stringMidRetainingBidiCC(string: layoutData->string,
3122	ellidePrefix: QString(), ellideSuffix: ellipsisText,
3123	subStringFrom: from, subStringTo: to,
3124	midStart: from, midLength: pos - from);
3125	} else if (mode == Qt::ElideLeft) {
3126	QFixed currentWidth;
3127	int pos;
3128	int nextBreak = to;
3129
3130	do {
3131	pos = nextBreak;
3132
3133	--nextBreak;
3134	while (nextBreak > 0 && !attributes[nextBreak].graphemeBoundary)
3135	--nextBreak;
3136
3137	currentWidth += this->width(from: nextBreak, len: pos - nextBreak);
3138	} while (nextBreak > from
3139	&& currentWidth < availableWidth);
3140
3141	if (prevCharJoins(string: layoutData->string, pos))
3142	ellipsisText.append(c: ZWJ);
3143
3144	return stringMidRetainingBidiCC(string: layoutData->string,
3145	ellidePrefix: ellipsisText, ellideSuffix: QString(),
3146	subStringFrom: from, subStringTo: to,
3147	midStart: pos, midLength: to - pos);
3148	} else if (mode == Qt::ElideMiddle) {
3149	QFixed leftWidth;
3150	QFixed rightWidth;
3151
3152	int leftPos = from;
3153	int nextLeftBreak = from;
3154
3155	int rightPos = to;
3156	int nextRightBreak = to;
3157
3158	do {
3159	leftPos = nextLeftBreak;
3160	rightPos = nextRightBreak;
3161
3162	++nextLeftBreak;
3163	while (nextLeftBreak < layoutData->string.size() && !attributes[nextLeftBreak].graphemeBoundary)
3164	++nextLeftBreak;
3165
3166	--nextRightBreak;
3167	while (nextRightBreak > from && !attributes[nextRightBreak].graphemeBoundary)
3168	--nextRightBreak;
3169
3170	leftWidth += this->width(from: leftPos, len: nextLeftBreak - leftPos);
3171	rightWidth += this->width(from: nextRightBreak, len: rightPos - nextRightBreak);
3172	} while (nextLeftBreak < to
3173	&& nextRightBreak > from
3174	&& leftWidth + rightWidth < availableWidth);
3175
3176	if (nextCharJoins(string: layoutData->string, pos: leftPos))
3177	ellipsisText.prepend(c: ZWJ);
3178	if (prevCharJoins(string: layoutData->string, pos: rightPos))
3179	ellipsisText.append(c: ZWJ);
3180
3181	return QStringView{layoutData->string}.mid(pos: from, n: leftPos - from) + ellipsisText + QStringView{layoutData->string}.mid(pos: rightPos, n: to - rightPos);
3182	}
3183
3184	return layoutData->string.mid(position: from, n: to - from);
3185	}
3186
3187	void QTextEngine::setBoundary(int strPos) const
3188	{
3189	const int item = findItem(strPos);
3190	if (item < 0)
3191	return;
3192
3193	QScriptItem newItem = layoutData->items.at(i: item);
3194	if (newItem.position != strPos) {
3195	newItem.position = strPos;
3196	layoutData->items.insert(i: item + 1, t: newItem);
3197	}
3198	}
3199
3200	QFixed QTextEngine::calculateTabWidth(int item, QFixed x) const
3201	{
3202	const QScriptItem &si = layoutData->items.at(i: item);
3203
3204	QFixed dpiScale = 1;
3205	if (QTextDocumentPrivate::get(block) != nullptr && QTextDocumentPrivate::get(block)->layout() != nullptr) {
3206	QPaintDevice *pdev = QTextDocumentPrivate::get(block)->layout()->paintDevice();
3207	if (pdev)
3208	dpiScale = QFixed::fromReal(r: pdev->logicalDpiY() / qreal(qt_defaultDpiY()));
3209	} else {
3210	dpiScale = QFixed::fromReal(r: fnt.d->dpi / qreal(qt_defaultDpiY()));
3211	}
3212
3213	QList<QTextOption::Tab> tabArray = option.tabs();
3214	if (!tabArray.isEmpty()) {
3215	if (isRightToLeft()) { // rebase the tabArray positions.
3216	auto isLeftOrRightTab = [](const QTextOption::Tab &tab) {
3217	return tab.type == QTextOption::LeftTab || tab.type == QTextOption::RightTab;
3218	};
3219	const auto cbegin = tabArray.cbegin();
3220	const auto cend = tabArray.cend();
3221	const auto cit = std::find_if(first: cbegin, last: cend, pred: isLeftOrRightTab);
3222	if (cit != cend) {
3223	const int index = std::distance(first: cbegin, last: cit);
3224	auto iter = tabArray.begin() + index;
3225	const auto end = tabArray.end();
3226	while (iter != end) {
3227	QTextOption::Tab &tab = *iter;
3228	if (tab.type == QTextOption::LeftTab)
3229	tab.type = QTextOption::RightTab;
3230	else if (tab.type == QTextOption::RightTab)
3231	tab.type = QTextOption::LeftTab;
3232	++iter;
3233	}
3234	}
3235	}
3236	for (const QTextOption::Tab &tabSpec : std::as_const(t&: tabArray)) {
3237	QFixed tab = QFixed::fromReal(r: tabSpec.position) * dpiScale;
3238	if (tab > x) { // this is the tab we need.
3239	int tabSectionEnd = layoutData->string.size();
3240	if (tabSpec.type == QTextOption::RightTab || tabSpec.type == QTextOption::CenterTab) {
3241	// find next tab to calculate the width required.
3242	tab = QFixed::fromReal(r: tabSpec.position);
3243	for (int i=item + 1; i < layoutData->items.size(); i++) {
3244	const QScriptItem &item = layoutData->items.at(i);
3245	if (item.analysis.flags == QScriptAnalysis::TabOrObject) { // found it.
3246	tabSectionEnd = item.position;
3247	break;
3248	}
3249	}
3250	}
3251	else if (tabSpec.type == QTextOption::DelimiterTab)
3252	// find delimiter character to calculate the width required
3253	tabSectionEnd = qMax(a: si.position, b: layoutData->string.indexOf(ch: tabSpec.delimiter, from: si.position) + 1);
3254
3255	if (tabSectionEnd > si.position) {
3256	QFixed length;
3257	// Calculate the length of text between this tab and the tabSectionEnd
3258	for (int i=item; i < layoutData->items.size(); i++) {
3259	const QScriptItem &item = layoutData->items.at(i);
3260	if (item.position > tabSectionEnd || item.position <= si.position)
3261	continue;
3262	shape(item: i); // first, lets make sure relevant text is already shaped
3263	if (item.analysis.flags == QScriptAnalysis::Object) {
3264	length += item.width;
3265	continue;
3266	}
3267	QGlyphLayout glyphs = this->shapedGlyphs(si: &item);
3268	const int end = qMin(a: item.position + item.num_glyphs, b: tabSectionEnd) - item.position;
3269	for (int i=0; i < end; i++)
3270	length += glyphs.advances[i] * !glyphs.attributes[i].dontPrint;
3271	if (end + item.position == tabSectionEnd && tabSpec.type == QTextOption::DelimiterTab) // remove half of matching char
3272	length -= glyphs.advances[end] / 2 * !glyphs.attributes[end].dontPrint;
3273	}
3274
3275	switch (tabSpec.type) {
3276	case QTextOption::CenterTab:
3277	length /= 2;
3278	Q_FALLTHROUGH();
3279	case QTextOption::DelimiterTab:
3280	case QTextOption::RightTab:
3281	tab = QFixed::fromReal(r: tabSpec.position) * dpiScale - length;
3282	if (tab < x) // default to tab taking no space
3283	return QFixed();
3284	break;
3285	case QTextOption::LeftTab:
3286	break;
3287	}
3288	}
3289	return tab - x;
3290	}
3291	}
3292	}
3293	QFixed tab = QFixed::fromReal(r: option.tabStopDistance());
3294	if (tab <= 0)
3295	tab = 80; // default
3296	tab *= dpiScale;
3297	QFixed nextTabPos = ((x / tab).truncate() + 1) * tab;
3298	QFixed tabWidth = nextTabPos - x;
3299
3300	return tabWidth;
3301	}
3302
3303	namespace {
3304	class FormatRangeComparatorByStart {
3305	const QList<QTextLayout::FormatRange> &list;
3306	public:
3307	FormatRangeComparatorByStart(const QList<QTextLayout::FormatRange> &list) : list(list) { }
3308	bool operator()(int a, int b) {
3309	return list.at(i: a).start < list.at(i: b).start;
3310	}
3311	};
3312	class FormatRangeComparatorByEnd {
3313	const QList<QTextLayout::FormatRange> &list;
3314	public:
3315	FormatRangeComparatorByEnd(const QList<QTextLayout::FormatRange> &list) : list(list) { }
3316	bool operator()(int a, int b) {
3317	return list.at(i: a).start + list.at(i: a).length < list.at(i: b).start + list.at(i: b).length;
3318	}
3319	};
3320	}
3321
3322	void QTextEngine::resolveFormats() const
3323	{
3324	if (!specialData || specialData->formats.isEmpty())
3325	return;
3326	Q_ASSERT(specialData->resolvedFormats.isEmpty());
3327
3328	QTextFormatCollection *collection = formatCollection();
3329
3330	QList<QTextCharFormat> resolvedFormats(layoutData->items.size());
3331
3332	QVarLengthArray<int, 64> formatsSortedByStart;
3333	formatsSortedByStart.reserve(sz: specialData->formats.size());
3334	for (int i = 0; i < specialData->formats.size(); ++i) {
3335	if (specialData->formats.at(i).length >= 0)
3336	formatsSortedByStart.append(t: i);
3337	}
3338	QVarLengthArray<int, 64> formatsSortedByEnd = formatsSortedByStart;
3339	std::sort(first: formatsSortedByStart.begin(), last: formatsSortedByStart.end(),
3340	comp: FormatRangeComparatorByStart(specialData->formats));
3341	std::sort(first: formatsSortedByEnd.begin(), last: formatsSortedByEnd.end(),
3342	comp: FormatRangeComparatorByEnd(specialData->formats));
3343
3344	QVarLengthArray<int, 16> currentFormats;
3345	const int *startIt = formatsSortedByStart.constBegin();
3346	const int *endIt = formatsSortedByEnd.constBegin();
3347
3348	for (int i = 0; i < layoutData->items.size(); ++i) {
3349	const QScriptItem *si = &layoutData->items.at(i);
3350	int end = si->position + length(si);
3351
3352	while (startIt != formatsSortedByStart.constEnd() &&
3353	specialData->formats.at(i: *startIt).start <= si->position) {
3354	currentFormats.insert(before: std::upper_bound(first: currentFormats.begin(), last: currentFormats.end(), val: *startIt),
3355	x: *startIt);
3356	++startIt;
3357	}
3358	while (endIt != formatsSortedByEnd.constEnd() &&
3359	specialData->formats.at(i: *endIt).start + specialData->formats.at(i: *endIt).length < end) {
3360	int *currentFormatIterator = std::lower_bound(first: currentFormats.begin(), last: currentFormats.end(), val: *endIt);
3361	if (*endIt < *currentFormatIterator)
3362	currentFormatIterator = currentFormats.end();
3363	currentFormats.remove(i: currentFormatIterator - currentFormats.begin());
3364	++endIt;
3365	}
3366
3367	QTextCharFormat &format = resolvedFormats[i];
3368	if (QTextDocumentPrivate::get(block) != nullptr) {
3369	// when we have a QTextDocumentPrivate, formatIndex might still return a valid index based
3370	// on the preeditPosition. for all other cases, we cleared the resolved format indices
3371	format = collection->charFormat(index: formatIndex(si));
3372	}
3373	if (!currentFormats.isEmpty()) {
3374	for (int cur : currentFormats) {
3375	const QTextLayout::FormatRange &range = specialData->formats.at(i: cur);
3376	Q_ASSERT(range.start <= si->position && range.start + range.length >= end);
3377	format.merge(other: range.format);
3378	}
3379	format = collection->charFormat(index: collection->indexForFormat(f: format)); // get shared copy
3380	}
3381	}
3382
3383	specialData->resolvedFormats = resolvedFormats;
3384	}
3385
3386	QFixed QTextEngine::leadingSpaceWidth(const QScriptLine &line)
3387	{
3388	if (!line.hasTrailingSpaces
3389	|| (option.flags() & QTextOption::IncludeTrailingSpaces)
3390	|| !isRightToLeft())
3391	return QFixed();
3392
3393	return width(from: line.from + line.length, len: line.trailingSpaces);
3394	}
3395
3396	QFixed QTextEngine::alignLine(const QScriptLine &line)
3397	{
3398	QFixed x = 0;
3399	justify(line);
3400	// if width is QFIXED_MAX that means we used setNumColumns() and that implicitly makes this line left aligned.
3401	if (!line.justified && line.width != QFIXED_MAX) {
3402	int align = option.alignment();
3403	if (align & Qt::AlignJustify && isRightToLeft())
3404	align = Qt::AlignRight;
3405	if (align & Qt::AlignRight)
3406	x = line.width - (line.textAdvance);
3407	else if (align & Qt::AlignHCenter)
3408	x = (line.width - line.textAdvance)/2;
3409	}
3410	return x;
3411	}
3412
3413	QFixed QTextEngine::offsetInLigature(const QScriptItem *si, int pos, int max, int glyph_pos)
3414	{
3415	unsigned short *logClusters = this->logClusters(si);
3416	const QGlyphLayout &glyphs = shapedGlyphs(si);
3417
3418	int offsetInCluster = 0;
3419	for (int i = pos - 1; i >= 0; i--) {
3420	if (logClusters[i] == glyph_pos)
3421	offsetInCluster++;
3422	else
3423	break;
3424	}
3425
3426	// in the case that the offset is inside a (multi-character) glyph,
3427	// interpolate the position.
3428	if (offsetInCluster > 0) {
3429	int clusterLength = 0;
3430	for (int i = pos - offsetInCluster; i < max; i++) {
3431	if (logClusters[i] == glyph_pos)
3432	clusterLength++;
3433	else
3434	break;
3435	}
3436	if (clusterLength)
3437	return glyphs.advances[glyph_pos] * offsetInCluster / clusterLength;
3438	}
3439
3440	return 0;
3441	}
3442
3443	// Scan in logClusters[from..to-1] for glyph_pos
3444	int QTextEngine::getClusterLength(unsigned short *logClusters,
3445	const QCharAttributes *attributes,
3446	int from, int to, int glyph_pos, int *start)
3447	{
3448	int clusterLength = 0;
3449	for (int i = from; i < to; i++) {
3450	if (logClusters[i] == glyph_pos && attributes[i].graphemeBoundary) {
3451	if (*start < 0)
3452	*start = i;
3453	clusterLength++;
3454	}
3455	else if (clusterLength)
3456	break;
3457	}
3458	return clusterLength;
3459	}
3460
3461	int QTextEngine::positionInLigature(const QScriptItem *si, int end,
3462	QFixed x, QFixed edge, int glyph_pos,
3463	bool cursorOnCharacter)
3464	{
3465	unsigned short *logClusters = this->logClusters(si);
3466	int clusterStart = -1;
3467	int clusterLength = 0;
3468
3469	if (si->analysis.script != QChar::Script_Common &&
3470	si->analysis.script != QChar::Script_Greek &&
3471	si->analysis.script != QChar::Script_Latin &&
3472	si->analysis.script != QChar::Script_Hiragana &&
3473	si->analysis.script != QChar::Script_Katakana &&
3474	si->analysis.script != QChar::Script_Bopomofo &&
3475	si->analysis.script != QChar::Script_Han) {
3476	if (glyph_pos == -1)
3477	return si->position + end;
3478	else {
3479	int i;
3480	for (i = 0; i < end; i++)
3481	if (logClusters[i] == glyph_pos)
3482	break;
3483	return si->position + i;
3484	}
3485	}
3486
3487	if (glyph_pos == -1 && end > 0)
3488	glyph_pos = logClusters[end - 1];
3489	else {
3490	if (x <= edge)
3491	glyph_pos--;
3492	}
3493
3494	const QCharAttributes *attrs = attributes() + si->position;
3495	logClusters = this->logClusters(si);
3496	clusterLength = getClusterLength(logClusters, attributes: attrs, from: 0, to: end, glyph_pos, start: &clusterStart);
3497
3498	if (clusterLength) {
3499	const QGlyphLayout &glyphs = shapedGlyphs(si);
3500	QFixed glyphWidth = glyphs.effectiveAdvance(item: glyph_pos);
3501	// the approximate width of each individual element of the ligature
3502	QFixed perItemWidth = glyphWidth / clusterLength;
3503	if (perItemWidth <= 0)
3504	return si->position + clusterStart;
3505	QFixed left = x > edge ? edge : edge - glyphWidth;
3506	int n = ((x - left) / perItemWidth).floor().toInt();
3507	QFixed dist = x - left - n * perItemWidth;
3508	int closestItem = dist > (perItemWidth / 2) ? n + 1 : n;
3509	if (cursorOnCharacter && closestItem > 0)
3510	closestItem--;
3511	int pos = clusterStart + closestItem;
3512	// Jump to the next grapheme boundary
3513	while (pos < end && !attrs[pos].graphemeBoundary)
3514	pos++;
3515	return si->position + pos;
3516	}
3517	return si->position + end;
3518	}
3519
3520	int QTextEngine::previousLogicalPosition(int oldPos) const
3521	{
3522	const QCharAttributes *attrs = attributes();
3523	int len = block.isValid() ? block.length() - 1
3524	: layoutData->string.size();
3525	Q_ASSERT(len <= layoutData->string.size());
3526	if (!attrs || oldPos <= 0 || oldPos > len)
3527	return oldPos;
3528
3529	oldPos--;
3530	while (oldPos && !attrs[oldPos].graphemeBoundary)
3531	oldPos--;
3532	return oldPos;
3533	}
3534
3535	int QTextEngine::nextLogicalPosition(int oldPos) const
3536	{
3537	const QCharAttributes *attrs = attributes();
3538	int len = block.isValid() ? block.length() - 1
3539	: layoutData->string.size();
3540	Q_ASSERT(len <= layoutData->string.size());
3541	if (!attrs || oldPos < 0 || oldPos >= len)
3542	return oldPos;
3543
3544	oldPos++;
3545	while (oldPos < len && !attrs[oldPos].graphemeBoundary)
3546	oldPos++;
3547	return oldPos;
3548	}
3549
3550	int QTextEngine::lineNumberForTextPosition(int pos)
3551	{
3552	if (!layoutData)
3553	itemize();
3554	if (pos == layoutData->string.size() && lines.size())
3555	return lines.size() - 1;
3556	for (int i = 0; i < lines.size(); ++i) {
3557	const QScriptLine& line = lines[i];
3558	if (line.from + line.length + line.trailingSpaces > pos)
3559	return i;
3560	}
3561	return -1;
3562	}
3563
3564	std::vector<int> QTextEngine::insertionPointsForLine(int lineNum)
3565	{
3566	QTextLineItemIterator iterator(this, lineNum);
3567
3568	std::vector<int> insertionPoints;
3569	insertionPoints.reserve(n: size_t(iterator.line.length));
3570
3571	bool lastLine = lineNum >= lines.size() - 1;
3572
3573	while (!iterator.atEnd()) {
3574	const QScriptItem &si = iterator.next();
3575
3576	int end = iterator.itemEnd;
3577	if (lastLine && iterator.item == iterator.lastItem)
3578	++end; // the last item in the last line -> insert eol position
3579	if (si.analysis.bidiLevel % 2) {
3580	for (int i = end - 1; i >= iterator.itemStart; --i)
3581	insertionPoints.push_back(x: i);
3582	} else {
3583	for (int i = iterator.itemStart; i < end; ++i)
3584	insertionPoints.push_back(x: i);
3585	}
3586	}
3587	return insertionPoints;
3588	}
3589
3590	int QTextEngine::endOfLine(int lineNum)
3591	{
3592	const auto insertionPoints = insertionPointsForLine(lineNum);
3593	if (insertionPoints.size() > 0)
3594	return insertionPoints.back();
3595	return 0;
3596	}
3597
3598	int QTextEngine::beginningOfLine(int lineNum)
3599	{
3600	const auto insertionPoints = insertionPointsForLine(lineNum);
3601	if (insertionPoints.size() > 0)
3602	return insertionPoints.front();
3603	return 0;
3604	}
3605
3606	int QTextEngine::positionAfterVisualMovement(int pos, QTextCursor::MoveOperation op)
3607	{
3608	itemize();
3609
3610	bool moveRight = (op == QTextCursor::Right);
3611	bool alignRight = isRightToLeft();
3612	if (!layoutData->hasBidi)
3613	return moveRight ^ alignRight ? nextLogicalPosition(oldPos: pos) : previousLogicalPosition(oldPos: pos);
3614
3615	int lineNum = lineNumberForTextPosition(pos);
3616	if (lineNum < 0)
3617	return pos;
3618
3619	const auto insertionPoints = insertionPointsForLine(lineNum);
3620	for (size_t i = 0, max = insertionPoints.size(); i < max; ++i)
3621	if (pos == insertionPoints[i]) {
3622	if (moveRight) {
3623	if (i + 1 < max)
3624	return insertionPoints[i + 1];
3625	} else {
3626	if (i > 0)
3627	return insertionPoints[i - 1];
3628	}
3629
3630	if (moveRight ^ alignRight) {
3631	if (lineNum + 1 < lines.size())
3632	return alignRight ? endOfLine(lineNum: lineNum + 1) : beginningOfLine(lineNum: lineNum + 1);
3633	}
3634	else {
3635	if (lineNum > 0)
3636	return alignRight ? beginningOfLine(lineNum: lineNum - 1) : endOfLine(lineNum: lineNum - 1);
3637	}
3638
3639	break;
3640	}
3641
3642	return pos;
3643	}
3644
3645	void QTextEngine::addItemDecoration(QPainter *painter, const QLineF &line, ItemDecorationList *decorationList)
3646	{
3647	if (delayDecorations) {
3648	decorationList->append(t: ItemDecoration(line.x1(), line.x2(), line.y1(), painter->pen()));
3649	} else {
3650	painter->drawLine(l: line);
3651	}
3652	}
3653
3654	void QTextEngine::addUnderline(QPainter *painter, const QLineF &line)
3655	{
3656	// qDebug() << "Adding underline:" << line;
3657	addItemDecoration(painter, line, decorationList: &underlineList);
3658	}
3659
3660	void QTextEngine::addStrikeOut(QPainter *painter, const QLineF &line)
3661	{
3662	addItemDecoration(painter, line, decorationList: &strikeOutList);
3663	}
3664
3665	void QTextEngine::addOverline(QPainter *painter, const QLineF &line)
3666	{
3667	addItemDecoration(painter, line, decorationList: &overlineList);
3668	}
3669
3670	void QTextEngine::drawItemDecorationList(QPainter *painter, const ItemDecorationList &decorationList)
3671	{
3672	// qDebug() << "Drawing" << decorationList.size() << "decorations";
3673	if (decorationList.isEmpty())
3674	return;
3675
3676	for (const ItemDecoration &decoration : decorationList) {
3677	painter->setPen(decoration.pen);
3678	painter->drawLine(l: QLineF(decoration.x1, decoration.y, decoration.x2, decoration.y));
3679	}
3680	}
3681
3682	void QTextEngine::drawDecorations(QPainter *painter)
3683	{
3684	QPen oldPen = painter->pen();
3685
3686	adjustUnderlines();
3687	drawItemDecorationList(painter, decorationList: underlineList);
3688	drawItemDecorationList(painter, decorationList: strikeOutList);
3689	drawItemDecorationList(painter, decorationList: overlineList);
3690
3691	clearDecorations();
3692
3693	painter->setPen(oldPen);
3694	}
3695
3696	void QTextEngine::clearDecorations()
3697	{
3698	underlineList.clear();
3699	strikeOutList.clear();
3700	overlineList.clear();
3701	}
3702
3703	void QTextEngine::adjustUnderlines()
3704	{
3705	// qDebug() << __PRETTY_FUNCTION__ << underlineList.count() << "underlines";
3706	if (underlineList.isEmpty())
3707	return;
3708
3709	ItemDecorationList::iterator start = underlineList.begin();
3710	ItemDecorationList::iterator end = underlineList.end();
3711	ItemDecorationList::iterator it = start;
3712	qreal underlinePos = start->y;
3713	qreal penWidth = start->pen.widthF();
3714	qreal lastLineEnd = start->x1;
3715
3716	while (it != end) {
3717	if (qFuzzyCompare(p1: lastLineEnd, p2: it->x1)) { // no gap between underlines
3718	underlinePos = qMax(a: underlinePos, b: it->y);
3719	penWidth = qMax(a: penWidth, b: it->pen.widthF());
3720	} else { // gap between this and the last underline
3721	adjustUnderlines(start, end: it, underlinePos, penWidth);
3722	start = it;
3723	underlinePos = start->y;
3724	penWidth = start->pen.widthF();
3725	}
3726	lastLineEnd = it->x2;
3727	++it;
3728	}
3729
3730	adjustUnderlines(start, end, underlinePos, penWidth);
3731	}
3732
3733	void QTextEngine::adjustUnderlines(ItemDecorationList::iterator start,
3734	ItemDecorationList::iterator end,
3735	qreal underlinePos, qreal penWidth)
3736	{
3737	for (ItemDecorationList::iterator it = start; it != end; ++it) {
3738	it->y = underlinePos;
3739	it->pen.setWidthF(penWidth);
3740	}
3741	}
3742
3743	QStackTextEngine::QStackTextEngine(const QString &string, const QFont &f)
3744	: QTextEngine(string, f),
3745	_layoutData(string, _memory, MemSize)
3746	{
3747	stackEngine = true;
3748	layoutData = &_layoutData;
3749	}
3750
3751	QTextItemInt::QTextItemInt(const QScriptItem &si, QFont *font, const QTextCharFormat &format)
3752	: charFormat(format),
3753	f(font),
3754	fontEngine(font->d->engineForScript(script: si.analysis.script))
3755	{
3756	Q_ASSERT(fontEngine);
3757
3758	initWithScriptItem(si);
3759	}
3760
3761	QTextItemInt::QTextItemInt(const QGlyphLayout &g, QFont *font, const QChar *chars_, int numChars, QFontEngine *fe, const QTextCharFormat &format)
3762	: charFormat(format),
3763	num_chars(numChars),
3764	chars(chars_),
3765	f(font),
3766	glyphs(g),
3767	fontEngine(fe)
3768	{
3769	}
3770
3771	// Fix up flags and underlineStyle with given info
3772	void QTextItemInt::initWithScriptItem(const QScriptItem &si)
3773	{
3774	// explicitly initialize flags so that initFontAttributes can be called
3775	// multiple times on the same TextItem
3776	flags = { };
3777	if (si.analysis.bidiLevel %2)
3778	flags |= QTextItem::RightToLeft;
3779	ascent = si.ascent;
3780	descent = si.descent;
3781
3782	if (charFormat.hasProperty(propertyId: QTextFormat::TextUnderlineStyle)) {
3783	underlineStyle = charFormat.underlineStyle();
3784	} else if (charFormat.boolProperty(propertyId: QTextFormat::FontUnderline)
3785	|| f->d->underline) {
3786	underlineStyle = QTextCharFormat::SingleUnderline;
3787	}
3788
3789	// compat
3790	if (underlineStyle == QTextCharFormat::SingleUnderline)
3791	flags |= QTextItem::Underline;
3792
3793	if (f->d->overline || charFormat.fontOverline())
3794	flags |= QTextItem::Overline;
3795	if (f->d->strikeOut || charFormat.fontStrikeOut())
3796	flags |= QTextItem::StrikeOut;
3797	}
3798
3799	QTextItemInt QTextItemInt::midItem(QFontEngine *fontEngine, int firstGlyphIndex, int numGlyphs) const
3800	{
3801	QTextItemInt ti = *this;
3802	const int end = firstGlyphIndex + numGlyphs;
3803	ti.glyphs = glyphs.mid(position: firstGlyphIndex, n: numGlyphs);
3804	ti.fontEngine = fontEngine;
3805
3806	if (logClusters && chars) {
3807	const int logClusterOffset = logClusters[0];
3808	while (logClusters[ti.chars - chars] - logClusterOffset < firstGlyphIndex)
3809	++ti.chars;
3810
3811	ti.logClusters += (ti.chars - chars);
3812
3813	ti.num_chars = 0;
3814	int char_start = ti.chars - chars;
3815	while (char_start + ti.num_chars < num_chars && ti.logClusters[ti.num_chars] - logClusterOffset < end)
3816	++ti.num_chars;
3817	}
3818	return ti;
3819	}
3820
3821
3822	QTransform qt_true_matrix(qreal w, qreal h, const QTransform &x)
3823	{
3824	QRectF rect = x.mapRect(QRectF(0, 0, w, h));
3825	return x * QTransform::fromTranslate(dx: -rect.x(), dy: -rect.y());
3826	}
3827
3828
3829	glyph_metrics_t glyph_metrics_t::transformed(const QTransform &matrix) const
3830	{
3831	if (matrix.type() < QTransform::TxTranslate)
3832	return *this;
3833
3834	glyph_metrics_t m = *this;
3835
3836	qreal w = width.toReal();
3837	qreal h = height.toReal();
3838	QTransform xform = qt_true_matrix(w, h, x: matrix);
3839
3840	QRectF rect(0, 0, w, h);
3841	rect = xform.mapRect(rect);
3842	m.width = QFixed::fromReal(r: rect.width());
3843	m.height = QFixed::fromReal(r: rect.height());
3844
3845	QLineF l = xform.map(l: QLineF(x.toReal(), y.toReal(), xoff.toReal(), yoff.toReal()));
3846
3847	m.x = QFixed::fromReal(r: l.x1());
3848	m.y = QFixed::fromReal(r: l.y1());
3849
3850	// The offset is relative to the baseline which is why we use dx/dy of the line
3851	m.xoff = QFixed::fromReal(r: l.dx());
3852	m.yoff = QFixed::fromReal(r: l.dy());
3853
3854	return m;
3855	}
3856
3857	QTextLineItemIterator::QTextLineItemIterator(QTextEngine *_eng, int _lineNum, const QPointF &pos,
3858	const QTextLayout::FormatRange *_selection)
3859	: eng(_eng),
3860	line(eng->lines[_lineNum]),
3861	si(nullptr),
3862	lineNum(_lineNum),
3863	lineEnd(line.from + line.length),
3864	firstItem(eng->findItem(strPos: line.from)),
3865	lastItem(eng->findItem(strPos: lineEnd - 1, firstItem)),
3866	nItems((firstItem >= 0 && lastItem >= firstItem)? (lastItem-firstItem+1) : 0),
3867	logicalItem(-1),
3868	item(-1),
3869	visualOrder(nItems),
3870	selection(_selection)
3871	{
3872	x = QFixed::fromReal(r: pos.x());
3873
3874	x += line.x;
3875
3876	x += eng->alignLine(line);
3877
3878	if (nItems > 0) {
3879	QVarLengthArray<uchar> levels(nItems);
3880	for (int i = 0; i < nItems; ++i)
3881	levels[i] = eng->layoutData->items.at(i: i + firstItem).analysis.bidiLevel;
3882	QTextEngine::bidiReorder(numItems: nItems, levels: levels.data(), visualOrder: visualOrder.data());
3883	}
3884
3885	eng->shapeLine(line);
3886	}
3887
3888	QScriptItem &QTextLineItemIterator::next()
3889	{
3890	x += itemWidth;
3891
3892	++logicalItem;
3893	item = visualOrder[logicalItem] + firstItem;
3894	itemLength = eng->length(item);
3895	si = &eng->layoutData->items[item];
3896	if (!si->num_glyphs)
3897	eng->shape(item);
3898
3899	itemStart = qMax(a: line.from, b: si->position);
3900	itemEnd = qMin(a: lineEnd, b: si->position + itemLength);
3901
3902	if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
3903	glyphsStart = 0;
3904	glyphsEnd = 1;
3905	itemWidth = si->width;
3906	return *si;
3907	}
3908
3909	unsigned short *logClusters = eng->logClusters(si);
3910	QGlyphLayout glyphs = eng->shapedGlyphs(si);
3911
3912	glyphsStart = logClusters[itemStart - si->position];
3913	glyphsEnd = (itemEnd == si->position + itemLength) ? si->num_glyphs : logClusters[itemEnd - si->position];
3914
3915	// show soft-hyphen at line-break
3916	if (si->position + itemLength >= lineEnd
3917	&& eng->layoutData->string.at(i: lineEnd - 1).unicode() == QChar::SoftHyphen)
3918	glyphs.attributes[glyphsEnd - 1].dontPrint = false;
3919
3920	itemWidth = 0;
3921	for (int g = glyphsStart; g < glyphsEnd; ++g)
3922	itemWidth += glyphs.effectiveAdvance(item: g);
3923
3924	return *si;
3925	}
3926
3927	bool QTextLineItemIterator::getSelectionBounds(QFixed *selectionX, QFixed *selectionWidth) const
3928	{
3929	*selectionX = *selectionWidth = 0;
3930
3931	if (!selection)
3932	return false;
3933
3934	if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
3935	if (si->position >= selection->start + selection->length
3936	|| si->position + itemLength <= selection->start)
3937	return false;
3938
3939	*selectionX = x;
3940	*selectionWidth = itemWidth;
3941	} else {
3942	unsigned short *logClusters = eng->logClusters(si);
3943	QGlyphLayout glyphs = eng->shapedGlyphs(si);
3944
3945	int from = qMax(a: itemStart, b: selection->start) - si->position;
3946	int to = qMin(a: itemEnd, b: selection->start + selection->length) - si->position;
3947	if (from >= to)
3948	return false;
3949
3950	int start_glyph = logClusters[from];
3951	int end_glyph = (to == itemLength) ? si->num_glyphs : logClusters[to];
3952	QFixed soff;
3953	QFixed swidth;
3954	if (si->analysis.bidiLevel %2) {
3955	for (int g = glyphsEnd - 1; g >= end_glyph; --g)
3956	soff += glyphs.effectiveAdvance(item: g);
3957	for (int g = end_glyph - 1; g >= start_glyph; --g)
3958	swidth += glyphs.effectiveAdvance(item: g);
3959	} else {
3960	for (int g = glyphsStart; g < start_glyph; ++g)
3961	soff += glyphs.effectiveAdvance(item: g);
3962	for (int g = start_glyph; g < end_glyph; ++g)
3963	swidth += glyphs.effectiveAdvance(item: g);
3964	}
3965
3966	// If the starting character is in the middle of a ligature,
3967	// selection should only contain the right part of that ligature
3968	// glyph, so we need to get the width of the left part here and
3969	// add it to *selectionX
3970	QFixed leftOffsetInLigature = eng->offsetInLigature(si, pos: from, max: to, glyph_pos: start_glyph);
3971	*selectionX = x + soff + leftOffsetInLigature;
3972	*selectionWidth = swidth - leftOffsetInLigature;
3973	// If the ending character is also part of a ligature, swidth does
3974	// not contain that part yet, we also need to find out the width of
3975	// that left part
3976	*selectionWidth += eng->offsetInLigature(si, pos: to, max: itemLength, glyph_pos: end_glyph);
3977	}
3978	return true;
3979	}
3980
3981	QT_END_NAMESPACE
3982