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	log_clusters[0] = glyphs_shaped;
1751	}
1752
1753	if (Q_UNLIKELY(engineIdx != 0)) {
1754	for (quint32 i = 0; i < num_glyphs; ++i)
1755	g.glyphs[i] |= (engineIdx << 24);
1756	}
1757
1758	if (!actualFontEngine->supportsHorizontalSubPixelPositions()) {
1759	for (uint i = 0; i < num_glyphs; ++i) {
1760	g.advances[i] = g.advances[i].round();
1761	g.offsets[i].x = g.offsets[i].x.round();
1762	}
1763	}
1764
1765	glyphs_shaped += num_glyphs;
1766	}
1767
1768	hb_buffer_destroy(buffer);
1769
1770	return glyphs_shaped;
1771	}
1772
1773	#endif // harfbuzz
1774
1775	void QTextEngine::init(QTextEngine *e)
1776	{
1777	e->ignoreBidi = false;
1778	e->cacheGlyphs = false;
1779	e->forceJustification = false;
1780	e->visualMovement = false;
1781	e->delayDecorations = false;
1782
1783	e->layoutData = nullptr;
1784
1785	e->minWidth = 0;
1786	e->maxWidth = 0;
1787
1788	e->specialData = nullptr;
1789	e->stackEngine = false;
1790	#ifndef QT_NO_RAWFONT
1791	e->useRawFont = false;
1792	#endif
1793	}
1794
1795	QTextEngine::QTextEngine()
1796	{
1797	init(e: this);
1798	}
1799
1800	QTextEngine::QTextEngine(const QString &str, const QFont &f)
1801	: text(str),
1802	fnt(f)
1803	{
1804	init(e: this);
1805	}
1806
1807	QTextEngine::~QTextEngine()
1808	{
1809	if (!stackEngine)
1810	delete layoutData;
1811	delete specialData;
1812	resetFontEngineCache();
1813	}
1814
1815	const QCharAttributes *QTextEngine::attributes() const
1816	{
1817	if (layoutData && layoutData->haveCharAttributes)
1818	return (QCharAttributes *) layoutData->memory;
1819
1820	itemize();
1821	if (! ensureSpace(nGlyphs: layoutData->string.size()))
1822	return nullptr;
1823
1824	QVarLengthArray<QUnicodeTools::ScriptItem> scriptItems(layoutData->items.size());
1825	for (int i = 0; i < layoutData->items.size(); ++i) {
1826	const QScriptItem &si = layoutData->items.at(i);
1827	scriptItems[i].position = si.position;
1828	scriptItems[i].script = QChar::Script(si.analysis.script);
1829	}
1830
1831	QUnicodeTools::initCharAttributes(
1832	str: layoutData->string,
1833	items: scriptItems.data(), numItems: scriptItems.size(),
1834	attributes: reinterpret_cast<QCharAttributes *>(layoutData->memory),
1835	options: QUnicodeTools::CharAttributeOptions(QUnicodeTools::GraphemeBreaks
1836	| QUnicodeTools::LineBreaks
1837	| QUnicodeTools::WhiteSpaces
1838	| QUnicodeTools::HangulLineBreakTailoring));
1839
1840
1841	layoutData->haveCharAttributes = true;
1842	return (QCharAttributes *) layoutData->memory;
1843	}
1844
1845	void QTextEngine::shape(int item) const
1846	{
1847	auto &li = layoutData->items[item];
1848	if (li.analysis.flags == QScriptAnalysis::Object) {
1849	ensureSpace(nGlyphs: 1);
1850	if (QTextDocumentPrivate::get(block) != nullptr) {
1851	docLayout()->resizeInlineObject(item: QTextInlineObject(item, const_cast<QTextEngine *>(this)),
1852	posInDocument: li.position + block.position(),
1853	format: format(si: &li));
1854	}
1855	// fix log clusters to point to the previous glyph, as the object doesn't have a glyph of it's own.
1856	// This is required so that all entries in the array get initialized and are ordered correctly.
1857	if (layoutData->logClustersPtr) {
1858	ushort *lc = logClusters(si: &li);
1859	*lc = (lc != layoutData->logClustersPtr) ? lc[-1] : 0;
1860	}
1861	} else if (li.analysis.flags == QScriptAnalysis::Tab) {
1862	// set up at least the ascent/descent/leading of the script item for the tab
1863	fontEngine(si: li, ascent: &li.ascent, descent: &li.descent, leading: &li.leading);
1864	// see the comment above
1865	if (layoutData->logClustersPtr) {
1866	ushort *lc = logClusters(si: &li);
1867	*lc = (lc != layoutData->logClustersPtr) ? lc[-1] : 0;
1868	}
1869	} else {
1870	shapeText(item);
1871	}
1872	}
1873
1874	static inline void releaseCachedFontEngine(QFontEngine *fontEngine)
1875	{
1876	if (fontEngine && !fontEngine->ref.deref())
1877	delete fontEngine;
1878	}
1879
1880	void QTextEngine::resetFontEngineCache()
1881	{
1882	releaseCachedFontEngine(fontEngine: feCache.prevFontEngine);
1883	releaseCachedFontEngine(fontEngine: feCache.prevScaledFontEngine);
1884	feCache.reset();
1885	}
1886
1887	void QTextEngine::invalidate()
1888	{
1889	freeMemory();
1890	minWidth = 0;
1891	maxWidth = 0;
1892
1893	resetFontEngineCache();
1894	}
1895
1896	void QTextEngine::clearLineData()
1897	{
1898	lines.clear();
1899	}
1900
1901	void QTextEngine::validate() const
1902	{
1903	if (layoutData)
1904	return;
1905	layoutData = new LayoutData();
1906	if (QTextDocumentPrivate::get(block) != nullptr) {
1907	layoutData->string = block.text();
1908	const bool nextBlockValid = block.next().isValid();
1909	if (!nextBlockValid && option.flags() & QTextOption::ShowDocumentTerminator) {
1910	layoutData->string += QLatin1Char('\xA7');
1911	} else if (option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
1912	layoutData->string += QLatin1Char(nextBlockValid ? '\xB6' : '\x20');
1913	}
1914
1915	} else {
1916	layoutData->string = text;
1917	}
1918	if (specialData && specialData->preeditPosition != -1)
1919	layoutData->string.insert(i: specialData->preeditPosition, s: specialData->preeditText);
1920	}
1921
1922	void QTextEngine::itemize() const
1923	{
1924	validate();
1925	if (layoutData->items.size())
1926	return;
1927
1928	int length = layoutData->string.size();
1929	if (!length)
1930	return;
1931
1932	const ushort *string = reinterpret_cast<const ushort *>(layoutData->string.unicode());
1933
1934	bool rtl = isRightToLeft();
1935
1936	QVarLengthArray<QScriptAnalysis, 4096> scriptAnalysis(length);
1937	QScriptAnalysis *analysis = scriptAnalysis.data();
1938
1939	QBidiAlgorithm bidi(layoutData->string.constData(), analysis, length, rtl);
1940	layoutData->hasBidi = bidi.process();
1941
1942	{
1943	QUnicodeTools::ScriptItemArray scriptItems;
1944	QUnicodeTools::initScripts(str: layoutData->string, scripts: &scriptItems);
1945	for (int i = 0; i < scriptItems.size(); ++i) {
1946	const auto &item = scriptItems.at(idx: i);
1947	int end = i < scriptItems.size() - 1 ? scriptItems.at(idx: i + 1).position : length;
1948	for (int j = item.position; j < end; ++j)
1949	analysis[j].script = item.script;
1950	}
1951	}
1952
1953	const ushort *uc = string;
1954	const ushort *e = uc + length;
1955	while (uc < e) {
1956	switch (*uc) {
1957	case QChar::ObjectReplacementCharacter:
1958	{
1959	const QTextDocumentPrivate *doc_p = QTextDocumentPrivate::get(block);
1960	if (doc_p != nullptr
1961	&& doc_p->layout() != nullptr
1962	&& QAbstractTextDocumentLayoutPrivate::get(layout: doc_p->layout()) != nullptr
1963	&& QAbstractTextDocumentLayoutPrivate::get(layout: doc_p->layout())->hasHandlers()) {
1964	analysis->flags = QScriptAnalysis::Object;
1965	} else {
1966	analysis->flags = QScriptAnalysis::None;
1967	}
1968	}
1969	break;
1970	case QChar::LineSeparator:
1971	analysis->flags = QScriptAnalysis::LineOrParagraphSeparator;
1972	if (option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
1973	const int offset = uc - string;
1974	layoutData->string.detach();
1975	string = reinterpret_cast<const ushort *>(layoutData->string.unicode());
1976	uc = string + offset;
1977	e = string + length;
1978	*const_cast<ushort*>(uc) = 0x21B5; // visual line separator
1979	}
1980	break;
1981	case QChar::Tabulation:
1982	analysis->flags = QScriptAnalysis::Tab;
1983	analysis->bidiLevel = bidi.baseLevel;
1984	break;
1985	case QChar::Space:
1986	case QChar::Nbsp:
1987	if (option.flags() & QTextOption::ShowTabsAndSpaces) {
1988	analysis->flags = (*uc == QChar::Space) ? QScriptAnalysis::Space : QScriptAnalysis::Nbsp;
1989	break;
1990	}
1991	Q_FALLTHROUGH();
1992	default:
1993	analysis->flags = QScriptAnalysis::None;
1994	break;
1995	}
1996	++uc;
1997	++analysis;
1998	}
1999	if (option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
2000	(analysis-1)->flags = QScriptAnalysis::LineOrParagraphSeparator; // to exclude it from width
2001	}
2002
2003	Itemizer itemizer(layoutData->string, scriptAnalysis.data(), layoutData->items);
2004
2005	const QTextDocumentPrivate *p = QTextDocumentPrivate::get(block);
2006	if (p) {
2007	SpecialData *s = specialData;
2008
2009	QTextDocumentPrivate::FragmentIterator it = p->find(pos: block.position());
2010	QTextDocumentPrivate::FragmentIterator end = p->find(pos: block.position() + block.length() - 1); // -1 to omit the block separator char
2011	int format = it.value()->format;
2012
2013	int preeditPosition = s ? s->preeditPosition : INT_MAX;
2014	int prevPosition = 0;
2015	int position = prevPosition;
2016	while (1) {
2017	const QTextFragmentData * const frag = it.value();
2018	if (it == end || format != frag->format) {
2019	if (s && position >= preeditPosition) {
2020	position += s->preeditText.size();
2021	preeditPosition = INT_MAX;
2022	}
2023	Q_ASSERT(position <= length);
2024	QFont::Capitalization capitalization =
2025	formatCollection()->charFormat(index: format).hasProperty(propertyId: QTextFormat::FontCapitalization)
2026	? formatCollection()->charFormat(index: format).fontCapitalization()
2027	: formatCollection()->defaultFont().capitalization();
2028	if (s) {
2029	for (const auto &range : std::as_const(t&: s->formats)) {
2030	if (range.start + range.length <= prevPosition || range.start >= position)
2031	continue;
2032	if (range.format.hasProperty(propertyId: QTextFormat::FontCapitalization)) {
2033	if (range.start > prevPosition)
2034	itemizer.generate(start: prevPosition, length: range.start - prevPosition, caps: capitalization);
2035	int newStart = std::max(a: prevPosition, b: range.start);
2036	int newEnd = std::min(a: position, b: range.start + range.length);
2037	itemizer.generate(start: newStart, length: newEnd - newStart, caps: range.format.fontCapitalization());
2038	prevPosition = newEnd;
2039	}
2040	}
2041	}
2042	itemizer.generate(start: prevPosition, length: position - prevPosition, caps: capitalization);
2043	if (it == end) {
2044	if (position < length)
2045	itemizer.generate(start: position, length: length - position, caps: capitalization);
2046	break;
2047	}
2048	format = frag->format;
2049	prevPosition = position;
2050	}
2051	position += frag->size_array[0];
2052	++it;
2053	}
2054	} else {
2055	#ifndef QT_NO_RAWFONT
2056	if (useRawFont && specialData) {
2057	int lastIndex = 0;
2058	for (int i = 0; i < specialData->formats.size(); ++i) {
2059	const QTextLayout::FormatRange &range = specialData->formats.at(i);
2060	const QTextCharFormat &format = range.format;
2061	if (format.hasProperty(propertyId: QTextFormat::FontCapitalization)) {
2062	itemizer.generate(start: lastIndex, length: range.start - lastIndex, caps: QFont::MixedCase);
2063	itemizer.generate(start: range.start, length: range.length, caps: format.fontCapitalization());
2064	lastIndex = range.start + range.length;
2065	}
2066	}
2067	itemizer.generate(start: lastIndex, length: length - lastIndex, caps: QFont::MixedCase);
2068	} else
2069	#endif
2070	itemizer.generate(start: 0, length, caps: static_cast<QFont::Capitalization> (fnt.d->capital));
2071	}
2072
2073	addRequiredBoundaries();
2074	resolveFormats();
2075	}
2076
2077	bool QTextEngine::isRightToLeft() const
2078	{
2079	switch (option.textDirection()) {
2080	case Qt::LeftToRight:
2081	return false;
2082	case Qt::RightToLeft:
2083	return true;
2084	default:
2085	break;
2086	}
2087	if (!layoutData)
2088	itemize();
2089	// this places the cursor in the right position depending on the keyboard layout
2090	if (layoutData->string.isEmpty())
2091	return QGuiApplication::inputMethod()->inputDirection() == Qt::RightToLeft;
2092	return layoutData->string.isRightToLeft();
2093	}
2094
2095
2096	int QTextEngine::findItem(int strPos, int firstItem) const
2097	{
2098	itemize();
2099	if (strPos < 0 || strPos >= layoutData->string.size() || firstItem < 0)
2100	return -1;
2101
2102	int left = firstItem + 1;
2103	int right = layoutData->items.size()-1;
2104	while(left <= right) {
2105	int middle = ((right-left)/2)+left;
2106	if (strPos > layoutData->items.at(i: middle).position)
2107	left = middle+1;
2108	else if (strPos < layoutData->items.at(i: middle).position)
2109	right = middle-1;
2110	else {
2111	return middle;
2112	}
2113	}
2114	return right;
2115	}
2116
2117	namespace {
2118	template<typename InnerFunc>
2119	void textIterator(const QTextEngine *textEngine, int from, int len, QFixed &width, InnerFunc &&innerFunc)
2120	{
2121	for (int i = 0; i < textEngine->layoutData->items.size(); i++) {
2122	const QScriptItem *si = textEngine->layoutData->items.constData() + i;
2123	int pos = si->position;
2124	int ilen = textEngine->length(item: i);
2125	// qDebug("item %d: from %d len %d", i, pos, ilen);
2126	if (pos >= from + len)
2127	break;
2128	if (pos + ilen > from) {
2129	if (!si->num_glyphs)
2130	textEngine->shape(item: i);
2131
2132	if (si->analysis.flags == QScriptAnalysis::Object) {
2133	width += si->width;
2134	continue;
2135	} else if (si->analysis.flags == QScriptAnalysis::Tab) {
2136	width += textEngine->calculateTabWidth(index: i, x: width);
2137	continue;
2138	}
2139
2140	unsigned short *logClusters = textEngine->logClusters(si);
2141
2142	// fprintf(stderr, " logclusters:");
2143	// for (int k = 0; k < ilen; k++)
2144	// fprintf(stderr, " %d", logClusters[k]);
2145	// fprintf(stderr, "\n");
2146	// do the simple thing for now and give the first glyph in a cluster the full width, all other ones 0.
2147	int charFrom = from - pos;
2148	if (charFrom < 0)
2149	charFrom = 0;
2150	int glyphStart = logClusters[charFrom];
2151	if (charFrom > 0 && logClusters[charFrom-1] == glyphStart)
2152	while (charFrom < ilen && logClusters[charFrom] == glyphStart)
2153	charFrom++;
2154	if (charFrom < ilen) {
2155	glyphStart = logClusters[charFrom];
2156	int charEnd = from + len - 1 - pos;
2157	if (charEnd >= ilen)
2158	charEnd = ilen-1;
2159	int glyphEnd = logClusters[charEnd];
2160	while (charEnd < ilen && logClusters[charEnd] == glyphEnd)
2161	charEnd++;
2162	glyphEnd = (charEnd == ilen) ? si->num_glyphs : logClusters[charEnd];
2163
2164	// qDebug("char: start=%d end=%d / glyph: start = %d, end = %d", charFrom, charEnd, glyphStart, glyphEnd);
2165	innerFunc(glyphStart, glyphEnd, si);
2166	}
2167	}
2168	}
2169	}
2170	} // namespace
2171
2172	QFixed QTextEngine::width(int from, int len) const
2173	{
2174	itemize();
2175
2176	QFixed w = 0;
2177	// qDebug("QTextEngine::width(from = %d, len = %d), numItems=%d, strleng=%d", from, len, items.size(), string.length());
2178	textIterator(textEngine: this, from, len, width&: w, innerFunc: [this, &w](int glyphStart, int glyphEnd, const QScriptItem *si) {
2179	QGlyphLayout glyphs = this->shapedGlyphs(si);
2180	for (int j = glyphStart; j < glyphEnd; j++)
2181	w += glyphs.advances[j] * !glyphs.attributes[j].dontPrint;
2182	});
2183	// qDebug(" --> w= %d ", w);
2184	return w;
2185	}
2186
2187	glyph_metrics_t QTextEngine::boundingBox(int from, int len) const
2188	{
2189	itemize();
2190
2191	glyph_metrics_t gm;
2192
2193	textIterator(textEngine: this, from, len, width&: gm.width, innerFunc: [this, &gm](int glyphStart, int glyphEnd, const QScriptItem *si) {
2194	if (glyphStart <= glyphEnd) {
2195	QGlyphLayout glyphs = this->shapedGlyphs(si);
2196	QFontEngine *fe = this->fontEngine(si: *si);
2197	glyph_metrics_t m = fe->boundingBox(glyphs: glyphs.mid(position: glyphStart, n: glyphEnd - glyphStart));
2198	gm.x = qMin(a: gm.x, b: m.x + gm.xoff);
2199	gm.y = qMin(a: gm.y, b: m.y + gm.yoff);
2200	gm.width = qMax(a: gm.width, b: m.width + gm.xoff);
2201	gm.height = qMax(a: gm.height, b: m.height + gm.yoff);
2202	gm.xoff += m.xoff;
2203	gm.yoff += m.yoff;
2204	}
2205	});
2206
2207	return gm;
2208	}
2209
2210	glyph_metrics_t QTextEngine::tightBoundingBox(int from, int len) const
2211	{
2212	itemize();
2213
2214	glyph_metrics_t gm;
2215
2216	textIterator(textEngine: this, from, len, width&: gm.width, innerFunc: [this, &gm](int glyphStart, int glyphEnd, const QScriptItem *si) {
2217	if (glyphStart <= glyphEnd) {
2218	QGlyphLayout glyphs = this->shapedGlyphs(si);
2219	QFontEngine *fe = fontEngine(si: *si);
2220	glyph_metrics_t m = fe->tightBoundingBox(glyphs: glyphs.mid(position: glyphStart, n: glyphEnd - glyphStart));
2221	gm.x = qMin(a: gm.x, b: m.x + gm.xoff);
2222	gm.y = qMin(a: gm.y, b: m.y + gm.yoff);
2223	gm.width = qMax(a: gm.width, b: m.width + gm.xoff);
2224	gm.height = qMax(a: gm.height, b: m.height + gm.yoff);
2225	gm.xoff += m.xoff;
2226	gm.yoff += m.yoff;
2227	}
2228	});
2229	return gm;
2230	}
2231
2232	QFont QTextEngine::font(const QScriptItem &si) const
2233	{
2234	QFont font = fnt;
2235	if (hasFormats()) {
2236	QTextCharFormat f = format(si: &si);
2237	font = f.font();
2238
2239	const QTextDocumentPrivate *document_d = QTextDocumentPrivate::get(block);
2240	if (document_d != nullptr && document_d->layout() != nullptr) {
2241	// Make sure we get the right dpi on printers
2242	QPaintDevice *pdev = document_d->layout()->paintDevice();
2243	if (pdev)
2244	font = QFont(font, pdev);
2245	} else {
2246	font = font.resolve(fnt);
2247	}
2248	QTextCharFormat::VerticalAlignment valign = f.verticalAlignment();
2249	if (valign == QTextCharFormat::AlignSuperScript || valign == QTextCharFormat::AlignSubScript) {
2250	if (font.pointSize() != -1)
2251	font.setPointSize((font.pointSize() * 2) / 3);
2252	else
2253	font.setPixelSize((font.pixelSize() * 2) / 3);
2254	}
2255	}
2256
2257	if (si.analysis.flags == QScriptAnalysis::SmallCaps)
2258	font = font.d->smallCapsFont();
2259
2260	return font;
2261	}
2262
2263	QTextEngine::FontEngineCache::FontEngineCache()
2264	{
2265	reset();
2266	}
2267
2268	//we cache the previous results of this function, as calling it numerous times with the same effective
2269	//input is common (and hard to cache at a higher level)
2270	QFontEngine *QTextEngine::fontEngine(const QScriptItem &si, QFixed *ascent, QFixed *descent, QFixed *leading) const
2271	{
2272	QFontEngine *engine = nullptr;
2273	QFontEngine *scaledEngine = nullptr;
2274	int script = si.analysis.script;
2275
2276	QFont font = fnt;
2277	#ifndef QT_NO_RAWFONT
2278	if (useRawFont && rawFont.isValid()) {
2279	if (feCache.prevFontEngine && feCache.prevFontEngine->type() == QFontEngine::Multi && feCache.prevScript == script) {
2280	engine = feCache.prevFontEngine;
2281	} else {
2282	engine = QFontEngineMulti::createMultiFontEngine(fe: rawFont.d->fontEngine, script);
2283	feCache.prevFontEngine = engine;
2284	feCache.prevScript = script;
2285	engine->ref.ref();
2286	if (feCache.prevScaledFontEngine) {
2287	releaseCachedFontEngine(fontEngine: feCache.prevScaledFontEngine);
2288	feCache.prevScaledFontEngine = nullptr;
2289	}
2290	}
2291	if (si.analysis.flags == QScriptAnalysis::SmallCaps) {
2292	if (feCache.prevScaledFontEngine) {
2293	scaledEngine = feCache.prevScaledFontEngine;
2294	} else {
2295	// GCC 12 gets confused about QFontEngine::ref, for some non-obvious reason
2296	// warning: ‘unsigned int __atomic_or_fetch_4(volatile void*, unsigned int, int)’ writing 4 bytes
2297	// into a region of size 0 overflows the destination [-Wstringop-overflow=]
2298	QT_WARNING_PUSH
2299	QT_WARNING_DISABLE_GCC("-Wstringop-overflow")
2300
2301	QFontEngine *scEngine = rawFont.d->fontEngine->cloneWithSize(smallCapsFraction * rawFont.pixelSize());
2302	scEngine->ref.ref();
2303	scaledEngine = QFontEngineMulti::createMultiFontEngine(fe: scEngine, script);
2304	scaledEngine->ref.ref();
2305	feCache.prevScaledFontEngine = scaledEngine;
2306	// If scEngine is not ref'ed by scaledEngine, make sure it is deallocated and not leaked.
2307	if (!scEngine->ref.deref())
2308	delete scEngine;
2309
2310	QT_WARNING_POP
2311	}
2312	}
2313	} else
2314	#endif
2315	{
2316	if (hasFormats()) {
2317	if (feCache.prevFontEngine && feCache.prevPosition == si.position && feCache.prevLength == length(si: &si) && feCache.prevScript == script) {
2318	engine = feCache.prevFontEngine;
2319	scaledEngine = feCache.prevScaledFontEngine;
2320	} else {
2321	QTextCharFormat f = format(si: &si);
2322	font = f.font();
2323
2324	if (QTextDocumentPrivate::get(block) != nullptr && QTextDocumentPrivate::get(block)->layout() != nullptr) {
2325	// Make sure we get the right dpi on printers
2326	QPaintDevice *pdev = QTextDocumentPrivate::get(block)->layout()->paintDevice();
2327	if (pdev)
2328	font = QFont(font, pdev);
2329	} else {
2330	font = font.resolve(fnt);
2331	}
2332	engine = font.d->engineForScript(script);
2333	Q_ASSERT(engine);
2334	engine->ref.ref();
2335
2336	QTextCharFormat::VerticalAlignment valign = f.verticalAlignment();
2337	if (valign == QTextCharFormat::AlignSuperScript || valign == QTextCharFormat::AlignSubScript) {
2338	if (font.pointSize() != -1)
2339	font.setPointSize((font.pointSize() * 2) / 3);
2340	else
2341	font.setPixelSize((font.pixelSize() * 2) / 3);
2342	scaledEngine = font.d->engineForScript(script);
2343	if (scaledEngine)
2344	scaledEngine->ref.ref();
2345	}
2346
2347	if (feCache.prevFontEngine)
2348	releaseCachedFontEngine(fontEngine: feCache.prevFontEngine);
2349	feCache.prevFontEngine = engine;
2350
2351	if (feCache.prevScaledFontEngine)
2352	releaseCachedFontEngine(fontEngine: feCache.prevScaledFontEngine);
2353	feCache.prevScaledFontEngine = scaledEngine;
2354
2355	feCache.prevScript = script;
2356	feCache.prevPosition = si.position;
2357	feCache.prevLength = length(si: &si);
2358	}
2359	} else {
2360	if (feCache.prevFontEngine && feCache.prevScript == script && feCache.prevPosition == -1) {
2361	engine = feCache.prevFontEngine;
2362	} else {
2363	engine = font.d->engineForScript(script);
2364	Q_ASSERT(engine);
2365	engine->ref.ref();
2366	if (feCache.prevFontEngine)
2367	releaseCachedFontEngine(fontEngine: feCache.prevFontEngine);
2368	feCache.prevFontEngine = engine;
2369
2370	feCache.prevScript = script;
2371	feCache.prevPosition = -1;
2372	feCache.prevLength = -1;
2373	feCache.prevScaledFontEngine = nullptr;
2374	}
2375	}
2376
2377	if (si.analysis.flags == QScriptAnalysis::SmallCaps) {
2378	QFontPrivate *p = font.d->smallCapsFontPrivate();
2379	scaledEngine = p->engineForScript(script);
2380	}
2381	}
2382
2383	if (leading) {
2384	Q_ASSERT(engine);
2385	Q_ASSERT(ascent);
2386	Q_ASSERT(descent);
2387	*ascent = engine->ascent();
2388	*descent = engine->descent();
2389	*leading = engine->leading();
2390	}
2391
2392	if (scaledEngine)
2393	return scaledEngine;
2394	return engine;
2395	}
2396
2397	struct QJustificationPoint {
2398	int type;
2399	QFixed kashidaWidth;
2400	QGlyphLayout glyph;
2401	};
2402
2403	Q_DECLARE_TYPEINFO(QJustificationPoint, Q_PRIMITIVE_TYPE);
2404
2405	static void set(QJustificationPoint *point, int type, const QGlyphLayout &glyph, QFontEngine *fe)
2406	{
2407	point->type = type;
2408	point->glyph = glyph;
2409
2410	if (type >= Justification_Arabic_Normal) {
2411	const char32_t ch = U'\x640'; // Kashida character
2412
2413	glyph_t kashidaGlyph = fe->glyphIndex(ucs4: ch);
2414	if (kashidaGlyph != 0) {
2415	QGlyphLayout g;
2416	g.numGlyphs = 1;
2417	g.glyphs = &kashidaGlyph;
2418	g.advances = &point->kashidaWidth;
2419	fe->recalcAdvances(&g, { });
2420
2421	if (point->kashidaWidth == 0)
2422	point->type = Justification_Prohibited;
2423	} else {
2424	point->type = Justification_Prohibited;
2425	point->kashidaWidth = 0;
2426	}
2427	}
2428	}
2429
2430
2431	void QTextEngine::justify(const QScriptLine &line)
2432	{
2433	// qDebug("justify: line.gridfitted = %d, line.justified=%d", line.gridfitted, line.justified);
2434	if (line.gridfitted && line.justified)
2435	return;
2436
2437	if (!line.gridfitted) {
2438	// redo layout in device metrics, then adjust
2439	const_cast<QScriptLine &>(line).gridfitted = true;
2440	}
2441
2442	if ((option.alignment() & Qt::AlignHorizontal_Mask) != Qt::AlignJustify)
2443	return;
2444
2445	itemize();
2446
2447	if (!forceJustification) {
2448	int end = line.from + (int)line.length + line.trailingSpaces;
2449	if (end == layoutData->string.size())
2450	return; // no justification at end of paragraph
2451	if (end && layoutData->items.at(i: findItem(strPos: end - 1)).analysis.flags == QScriptAnalysis::LineOrParagraphSeparator)
2452	return; // no justification at the end of an explicitly separated line
2453	}
2454
2455	// justify line
2456	int maxJustify = 0;
2457
2458	// don't include trailing white spaces when doing justification
2459	int line_length = line.length;
2460	const QCharAttributes *a = attributes();
2461	if (! a)
2462	return;
2463	a += line.from;
2464	while (line_length && a[line_length-1].whiteSpace)
2465	--line_length;
2466	// subtract one char more, as we can't justfy after the last character
2467	--line_length;
2468
2469	if (line_length <= 0)
2470	return;
2471
2472	int firstItem = findItem(strPos: line.from);
2473	int lastItem = findItem(strPos: line.from + line_length - 1, firstItem);
2474	int nItems = (firstItem >= 0 && lastItem >= firstItem)? (lastItem-firstItem+1) : 0;
2475
2476	QVarLengthArray<QJustificationPoint> justificationPoints;
2477	int nPoints = 0;
2478	// 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());
2479	QFixed minKashida = 0x100000;
2480
2481	// we need to do all shaping before we go into the next loop, as we there
2482	// store pointers to the glyph data that could get reallocated by the shaping
2483	// process.
2484	for (int i = 0; i < nItems; ++i) {
2485	const QScriptItem &si = layoutData->items.at(i: firstItem + i);
2486	if (!si.num_glyphs)
2487	shape(item: firstItem + i);
2488	}
2489
2490	for (int i = 0; i < nItems; ++i) {
2491	const QScriptItem &si = layoutData->items.at(i: firstItem + i);
2492
2493	int kashida_type = Justification_Arabic_Normal;
2494	int kashida_pos = -1;
2495
2496	int start = qMax(a: line.from - si.position, b: 0);
2497	int end = qMin(a: line.from + line_length - (int)si.position, b: length(item: firstItem+i));
2498
2499	unsigned short *log_clusters = logClusters(si: &si);
2500
2501	int gs = log_clusters[start];
2502	int ge = (end == length(item: firstItem+i) ? si.num_glyphs : log_clusters[end]);
2503
2504	Q_ASSERT(ge <= si.num_glyphs);
2505
2506	const QGlyphLayout g = shapedGlyphs(si: &si);
2507
2508	for (int i = gs; i < ge; ++i) {
2509	g.justifications[i].type = QGlyphJustification::JustifyNone;
2510	g.justifications[i].nKashidas = 0;
2511	g.justifications[i].space_18d6 = 0;
2512
2513	justificationPoints.resize(sz: nPoints+3);
2514	int justification = g.attributes[i].justification;
2515
2516	switch(justification) {
2517	case Justification_Prohibited:
2518	break;
2519	case Justification_Space:
2520	case Justification_Arabic_Space:
2521	if (kashida_pos >= 0) {
2522	// qDebug("kashida position at %d in word", kashida_pos);
2523	set(point: &justificationPoints[nPoints], type: kashida_type, glyph: g.mid(position: kashida_pos), fe: fontEngine(si));
2524	if (justificationPoints[nPoints].kashidaWidth > 0) {
2525	minKashida = qMin(a: minKashida, b: justificationPoints[nPoints].kashidaWidth);
2526	maxJustify = qMax(a: maxJustify, b: justificationPoints[nPoints].type);
2527	++nPoints;
2528	}
2529	}
2530	kashida_pos = -1;
2531	kashida_type = Justification_Arabic_Normal;
2532	Q_FALLTHROUGH();
2533	case Justification_Character:
2534	set(point: &justificationPoints[nPoints++], type: justification, glyph: g.mid(position: i), fe: fontEngine(si));
2535	maxJustify = qMax(a: maxJustify, b: justification);
2536	break;
2537	case Justification_Arabic_Normal:
2538	case Justification_Arabic_Waw:
2539	case Justification_Arabic_BaRa:
2540	case Justification_Arabic_Alef:
2541	case Justification_Arabic_HahDal:
2542	case Justification_Arabic_Seen:
2543	case Justification_Arabic_Kashida:
2544	if (justification >= kashida_type) {
2545	kashida_pos = i;
2546	kashida_type = justification;
2547	}
2548	}
2549	}
2550	if (kashida_pos >= 0) {
2551	set(point: &justificationPoints[nPoints], type: kashida_type, glyph: g.mid(position: kashida_pos), fe: fontEngine(si));
2552	if (justificationPoints[nPoints].kashidaWidth > 0) {
2553	minKashida = qMin(a: minKashida, b: justificationPoints[nPoints].kashidaWidth);
2554	maxJustify = qMax(a: maxJustify, b: justificationPoints[nPoints].type);
2555	++nPoints;
2556	}
2557	}
2558	}
2559
2560	QFixed leading = leadingSpaceWidth(line);
2561	QFixed need = line.width - line.textWidth - leading;
2562	if (need < 0) {
2563	// line overflows already!
2564	const_cast<QScriptLine &>(line).justified = true;
2565	return;
2566	}
2567
2568	// qDebug("doing justification: textWidth=%x, requested=%x, maxJustify=%d", line.textWidth.value(), line.width.value(), maxJustify);
2569	// qDebug(" minKashida=%f, need=%f", minKashida.toReal(), need.toReal());
2570
2571	// distribute in priority order
2572	if (maxJustify >= Justification_Arabic_Normal) {
2573	while (need >= minKashida) {
2574	for (int type = maxJustify; need >= minKashida && type >= Justification_Arabic_Normal; --type) {
2575	for (int i = 0; need >= minKashida && i < nPoints; ++i) {
2576	if (justificationPoints[i].type == type && justificationPoints[i].kashidaWidth <= need) {
2577	justificationPoints[i].glyph.justifications->nKashidas++;
2578	// ############
2579	justificationPoints[i].glyph.justifications->space_18d6 += justificationPoints[i].kashidaWidth.value();
2580	need -= justificationPoints[i].kashidaWidth;
2581	// qDebug("adding kashida type %d with width %x, neednow %x", type, justificationPoints[i].kashidaWidth, need.value());
2582	}
2583	}
2584	}
2585	}
2586	}
2587	Q_ASSERT(need >= 0);
2588	if (!need)
2589	goto end;
2590
2591	maxJustify = qMin(a: maxJustify, b: int(Justification_Space));
2592	for (int type = maxJustify; need != 0 && type > 0; --type) {
2593	int n = 0;
2594	for (int i = 0; i < nPoints; ++i) {
2595	if (justificationPoints[i].type == type)
2596	++n;
2597	}
2598	// qDebug("number of points for justification type %d: %d", type, n);
2599
2600
2601	if (!n)
2602	continue;
2603
2604	for (int i = 0; i < nPoints; ++i) {
2605	if (justificationPoints[i].type == type) {
2606	QFixed add = need/n;
2607	// qDebug("adding %x to glyph %x", add.value(), justificationPoints[i].glyph->glyph);
2608	justificationPoints[i].glyph.justifications[0].space_18d6 = add.value();
2609	need -= add;
2610	--n;
2611	}
2612	}
2613
2614	Q_ASSERT(!need);
2615	}
2616	end:
2617	const_cast<QScriptLine &>(line).justified = true;
2618	}
2619
2620	void QScriptLine::setDefaultHeight(QTextEngine *eng)
2621	{
2622	QFont f;
2623	QFontEngine *e;
2624
2625	if (QTextDocumentPrivate::get(block&: eng->block) != nullptr && QTextDocumentPrivate::get(block&: eng->block)->layout() != nullptr) {
2626	f = eng->block.charFormat().font();
2627	// Make sure we get the right dpi on printers
2628	QPaintDevice *pdev = QTextDocumentPrivate::get(block&: eng->block)->layout()->paintDevice();
2629	if (pdev)
2630	f = QFont(f, pdev);
2631	e = f.d->engineForScript(script: QChar::Script_Common);
2632	} else {
2633	e = eng->fnt.d->engineForScript(script: QChar::Script_Common);
2634	}
2635
2636	QFixed other_ascent = e->ascent();
2637	QFixed other_descent = e->descent();
2638	QFixed other_leading = e->leading();
2639	leading = qMax(a: leading + ascent, b: other_leading + other_ascent) - qMax(a: ascent, b: other_ascent);
2640	ascent = qMax(a: ascent, b: other_ascent);
2641	descent = qMax(a: descent, b: other_descent);
2642	}
2643
2644	QTextEngine::LayoutData::LayoutData()
2645	{
2646	memory = nullptr;
2647	allocated = 0;
2648	memory_on_stack = false;
2649	used = 0;
2650	hasBidi = false;
2651	layoutState = LayoutEmpty;
2652	haveCharAttributes = false;
2653	logClustersPtr = nullptr;
2654	available_glyphs = 0;
2655	currentMaxWidth = 0;
2656	}
2657
2658	QTextEngine::LayoutData::LayoutData(const QString &str, void **stack_memory, qsizetype _allocated)
2659	: string(str)
2660	{
2661	allocated = _allocated;
2662
2663	constexpr qsizetype voidSize = sizeof(void*);
2664	qsizetype space_charAttributes = sizeof(QCharAttributes) * string.size() / voidSize + 1;
2665	qsizetype space_logClusters = sizeof(unsigned short) * string.size() / voidSize + 1;
2666	available_glyphs = (allocated - space_charAttributes - space_logClusters) * voidSize / QGlyphLayout::SpaceNeeded;
2667
2668	if (available_glyphs < str.size()) {
2669	// need to allocate on the heap
2670	allocated = 0;
2671
2672	memory_on_stack = false;
2673	memory = nullptr;
2674	logClustersPtr = nullptr;
2675	} else {
2676	memory_on_stack = true;
2677	memory = stack_memory;
2678	logClustersPtr = (unsigned short *)(memory + space_charAttributes);
2679
2680	void *m = memory + space_charAttributes + space_logClusters;
2681	glyphLayout = QGlyphLayout(reinterpret_cast<char *>(m), str.size());
2682	glyphLayout.clear();
2683	memset(s: memory, c: 0, n: space_charAttributes*sizeof(void *));
2684	}
2685	used = 0;
2686	hasBidi = false;
2687	layoutState = LayoutEmpty;
2688	haveCharAttributes = false;
2689	currentMaxWidth = 0;
2690	}
2691
2692	QTextEngine::LayoutData::~LayoutData()
2693	{
2694	if (!memory_on_stack)
2695	free(ptr: memory);
2696	memory = nullptr;
2697	}
2698
2699	bool QTextEngine::LayoutData::reallocate(int totalGlyphs)
2700	{
2701	Q_ASSERT(totalGlyphs >= glyphLayout.numGlyphs);
2702	if (memory_on_stack && available_glyphs >= totalGlyphs) {
2703	glyphLayout.grow(address: glyphLayout.data(), totalGlyphs);
2704	return true;
2705	}
2706
2707	const qsizetype space_charAttributes = (sizeof(QCharAttributes) * string.size() / sizeof(void*) + 1);
2708	const qsizetype space_logClusters = (sizeof(unsigned short) * string.size() / sizeof(void*) + 1);
2709	const qsizetype space_glyphs = qsizetype(totalGlyphs) * QGlyphLayout::SpaceNeeded / sizeof(void *) + 2;
2710
2711	const qsizetype newAllocated = space_charAttributes + space_glyphs + space_logClusters;
2712	// Check if the length of string/glyphs causes int overflow,
2713	// we can't layout such a long string all at once, so return false here to
2714	// indicate there is a failure
2715	if (size_t(space_charAttributes) > INT_MAX || size_t(space_logClusters) > INT_MAX || totalGlyphs < 0
2716	|| size_t(space_glyphs) > INT_MAX || size_t(newAllocated) > INT_MAX || newAllocated < allocated) {
2717	layoutState = LayoutFailed;
2718	return false;
2719	}
2720
2721	void **newMem = (void **)::realloc(ptr: memory_on_stack ? nullptr : memory, size: newAllocated*sizeof(void *));
2722	if (!newMem) {
2723	layoutState = LayoutFailed;
2724	return false;
2725	}
2726	if (memory_on_stack)
2727	memcpy(dest: newMem, src: memory, n: allocated*sizeof(void *));
2728	memory = newMem;
2729	memory_on_stack = false;
2730
2731	void **m = memory;
2732	m += space_charAttributes;
2733	logClustersPtr = (unsigned short *) m;
2734	m += space_logClusters;
2735
2736	const qsizetype space_preGlyphLayout = space_charAttributes + space_logClusters;
2737	if (allocated < space_preGlyphLayout)
2738	memset(s: memory + allocated, c: 0, n: (space_preGlyphLayout - allocated)*sizeof(void *));
2739
2740	glyphLayout.grow(address: reinterpret_cast<char *>(m), totalGlyphs);
2741
2742	allocated = newAllocated;
2743	return true;
2744	}
2745
2746	void QGlyphLayout::copy(QGlyphLayout *oldLayout)
2747	{
2748	Q_ASSERT(offsets != oldLayout->offsets);
2749
2750	int n = std::min(a: numGlyphs, b: oldLayout->numGlyphs);
2751
2752	memcpy(dest: offsets, src: oldLayout->offsets, n: n * sizeof(QFixedPoint));
2753	memcpy(dest: attributes, src: oldLayout->attributes, n: n * sizeof(QGlyphAttributes));
2754	memcpy(dest: justifications, src: oldLayout->justifications, n: n * sizeof(QGlyphJustification));
2755	memcpy(dest: advances, src: oldLayout->advances, n: n * sizeof(QFixed));
2756	memcpy(dest: glyphs, src: oldLayout->glyphs, n: n * sizeof(glyph_t));
2757
2758	numGlyphs = n;
2759	}
2760
2761	// grow to the new size, copying the existing data to the new layout
2762	void QGlyphLayout::grow(char *address, int totalGlyphs)
2763	{
2764	QGlyphLayout oldLayout(address, numGlyphs);
2765	QGlyphLayout newLayout(address, totalGlyphs);
2766
2767	if (numGlyphs) {
2768	// move the existing data
2769	memmove(dest: newLayout.attributes, src: oldLayout.attributes, n: numGlyphs * sizeof(QGlyphAttributes));
2770	memmove(dest: newLayout.justifications, src: oldLayout.justifications, n: numGlyphs * sizeof(QGlyphJustification));
2771	memmove(dest: newLayout.advances, src: oldLayout.advances, n: numGlyphs * sizeof(QFixed));
2772	memmove(dest: newLayout.glyphs, src: oldLayout.glyphs, n: numGlyphs * sizeof(glyph_t));
2773	}
2774
2775	// clear the new data
2776	newLayout.clear(first: numGlyphs);
2777
2778	*this = newLayout;
2779	}
2780
2781	void QTextEngine::freeMemory()
2782	{
2783	if (!stackEngine) {
2784	delete layoutData;
2785	layoutData = nullptr;
2786	} else {
2787	layoutData->used = 0;
2788	layoutData->hasBidi = false;
2789	layoutData->layoutState = LayoutEmpty;
2790	layoutData->haveCharAttributes = false;
2791	layoutData->currentMaxWidth = 0;
2792	layoutData->items.clear();
2793	}
2794	if (specialData)
2795	specialData->resolvedFormats.clear();
2796	for (int i = 0; i < lines.size(); ++i) {
2797	lines[i].justified = 0;
2798	lines[i].gridfitted = 0;
2799	}
2800	}
2801
2802	int QTextEngine::formatIndex(const QScriptItem *si) const
2803	{
2804	if (specialData && !specialData->resolvedFormats.isEmpty()) {
2805	QTextFormatCollection *collection = formatCollection();
2806	Q_ASSERT(collection);
2807	return collection->indexForFormat(f: specialData->resolvedFormats.at(i: si - &layoutData->items.at(i: 0)));
2808	}
2809
2810	const QTextDocumentPrivate *p = QTextDocumentPrivate::get(block);
2811	if (!p)
2812	return -1;
2813	int pos = si->position;
2814	if (specialData && si->position >= specialData->preeditPosition) {
2815	if (si->position < specialData->preeditPosition + specialData->preeditText.size())
2816	pos = qMax(a: qMin(a: block.length(), b: specialData->preeditPosition) - 1, b: 0);
2817	else
2818	pos -= specialData->preeditText.size();
2819	}
2820	QTextDocumentPrivate::FragmentIterator it = p->find(pos: block.position() + pos);
2821	return it.value()->format;
2822	}
2823
2824
2825	QTextCharFormat QTextEngine::format(const QScriptItem *si) const
2826	{
2827	if (const QTextFormatCollection *collection = formatCollection())
2828	return collection->charFormat(index: formatIndex(si));
2829	return QTextCharFormat();
2830	}
2831
2832	void QTextEngine::addRequiredBoundaries() const
2833	{
2834	if (specialData) {
2835	for (int i = 0; i < specialData->formats.size(); ++i) {
2836	const QTextLayout::FormatRange &r = specialData->formats.at(i);
2837	setBoundary(r.start);
2838	setBoundary(r.start + r.length);
2839	//qDebug("adding boundaries %d %d", r.start, r.start+r.length);
2840	}
2841	}
2842	}
2843
2844	bool QTextEngine::atWordSeparator(int position) const
2845	{
2846	const QChar c = layoutData->string.at(i: position);
2847	switch (c.unicode()) {
2848	case '.':
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	return true;
2880	default:
2881	break;
2882	}
2883	return false;
2884	}
2885
2886	void QTextEngine::setPreeditArea(int position, const QString &preeditText)
2887	{
2888	if (preeditText.isEmpty()) {
2889	if (!specialData)
2890	return;
2891	if (specialData->formats.isEmpty()) {
2892	delete specialData;
2893	specialData = nullptr;
2894	} else {
2895	specialData->preeditText = QString();
2896	specialData->preeditPosition = -1;
2897	}
2898	} else {
2899	if (!specialData)
2900	specialData = new SpecialData;
2901	specialData->preeditPosition = position;
2902	specialData->preeditText = preeditText;
2903	}
2904	invalidate();
2905	clearLineData();
2906	}
2907
2908	void QTextEngine::setFormats(const QList<QTextLayout::FormatRange> &formats)
2909	{
2910	if (formats.isEmpty()) {
2911	if (!specialData)
2912	return;
2913	if (specialData->preeditText.isEmpty()) {
2914	delete specialData;
2915	specialData = nullptr;
2916	} else {
2917	specialData->formats.clear();
2918	}
2919	} else {
2920	if (!specialData) {
2921	specialData = new SpecialData;
2922	specialData->preeditPosition = -1;
2923	}
2924	specialData->formats = formats;
2925	indexFormats();
2926	}
2927	invalidate();
2928	clearLineData();
2929	}
2930
2931	void QTextEngine::indexFormats()
2932	{
2933	QTextFormatCollection *collection = formatCollection();
2934	if (!collection) {
2935	Q_ASSERT(QTextDocumentPrivate::get(block) == nullptr);
2936	specialData->formatCollection.reset(other: new QTextFormatCollection);
2937	collection = specialData->formatCollection.data();
2938	}
2939
2940	// replace with shared copies
2941	for (int i = 0; i < specialData->formats.size(); ++i) {
2942	QTextCharFormat &format = specialData->formats[i].format;
2943	format = collection->charFormat(index: collection->indexForFormat(f: format));
2944	}
2945	}
2946
2947	/* These two helper functions are used to determine whether we need to insert a ZWJ character
2948	between the text that gets truncated and the ellipsis. This is important to get
2949	correctly shaped results for arabic text.
2950	*/
2951	static inline bool nextCharJoins(const QString &string, int pos)
2952	{
2953	while (pos < string.size() && string.at(i: pos).category() == QChar::Mark_NonSpacing)
2954	++pos;
2955	if (pos == string.size())
2956	return false;
2957	QChar::JoiningType joining = string.at(i: pos).joiningType();
2958	return joining != QChar::Joining_None && joining != QChar::Joining_Transparent;
2959	}
2960
2961	static inline bool prevCharJoins(const QString &string, int pos)
2962	{
2963	while (pos > 0 && string.at(i: pos - 1).category() == QChar::Mark_NonSpacing)
2964	--pos;
2965	if (pos == 0)
2966	return false;
2967	QChar::JoiningType joining = string.at(i: pos - 1).joiningType();
2968	return joining == QChar::Joining_Dual || joining == QChar::Joining_Causing;
2969	}
2970
2971	static constexpr bool isRetainableControlCode(char16_t c) noexcept
2972	{
2973	return (c >= 0x202a && c <= 0x202e) // LRE, RLE, PDF, LRO, RLO
2974	|| (c >= 0x200e && c <= 0x200f) // LRM, RLM
2975	|| (c >= 0x2066 && c <= 0x2069); // LRI, RLI, FSI, PDI
2976	}
2977
2978	static QString stringMidRetainingBidiCC(const QString &string,
2979	const QString &ellidePrefix,
2980	const QString &ellideSuffix,
2981	int subStringFrom,
2982	int subStringTo,
2983	int midStart,
2984	int midLength)
2985	{
2986	QString prefix;
2987	for (int i=subStringFrom; i<midStart; ++i) {
2988	char16_t c = string.at(i).unicode();
2989	if (isRetainableControlCode(c))
2990	prefix += c;
2991	}
2992
2993	QString suffix;
2994	for (int i=midStart + midLength; i<subStringTo; ++i) {
2995	char16_t c = string.at(i).unicode();
2996	if (isRetainableControlCode(c))
2997	suffix += c;
2998	}
2999
3000	return prefix + ellidePrefix + QStringView{string}.mid(pos: midStart, n: midLength) + ellideSuffix + suffix;
3001	}
3002
3003	QString QTextEngine::elidedText(Qt::TextElideMode mode, QFixed width, int flags, int from, int count) const
3004	{
3005	// qDebug() << "elidedText; available width" << width.toReal() << "text width:" << this->width(0, layoutData->string.length()).toReal();
3006
3007	if (flags & Qt::TextShowMnemonic) {
3008	itemize();
3009	QCharAttributes *attributes = const_cast<QCharAttributes *>(this->attributes());
3010	if (!attributes)
3011	return QString();
3012	for (int i = 0; i < layoutData->items.size(); ++i) {
3013	const QScriptItem &si = layoutData->items.at(i);
3014	if (!si.num_glyphs)
3015	shape(item: i);
3016
3017	unsigned short *logClusters = this->logClusters(si: &si);
3018	QGlyphLayout glyphs = shapedGlyphs(si: &si);
3019
3020	const int end = si.position + length(si: &si);
3021	for (int i = si.position; i < end - 1; ++i) {
3022	if (layoutData->string.at(i) == u'&'
3023	&& !attributes[i + 1].whiteSpace && attributes[i + 1].graphemeBoundary) {
3024	const int gp = logClusters[i - si.position];
3025	glyphs.attributes[gp].dontPrint = true;
3026	// emulate grapheme cluster
3027	attributes[i] = attributes[i + 1];
3028	memset(s: attributes + i + 1, c: 0, n: sizeof(QCharAttributes));
3029	if (layoutData->string.at(i: i + 1) == u'&')
3030	++i;
3031	}
3032	}
3033	}
3034	}
3035
3036	validate();
3037
3038	const int to = count >= 0 && count <= layoutData->string.size() - from
3039	? from + count
3040	: layoutData->string.size();
3041
3042	if (mode == Qt::ElideNone
3043	|| this->width(from, len: layoutData->string.size()) <= width
3044	|| to - from <= 1)
3045	return layoutData->string.mid(position: from, n: from - to);
3046
3047	QFixed ellipsisWidth;
3048	QString ellipsisText;
3049	{
3050	QFontEngine *engine = fnt.d->engineForScript(script: QChar::Script_Common);
3051
3052	constexpr char16_t ellipsisChar = u'\x2026';
3053
3054	// We only want to use the ellipsis character if it is from the main
3055	// font (not one of the fallbacks), since using a fallback font
3056	// will affect the metrics of the text, potentially causing it to shift
3057	// when it is being elided.
3058	if (engine->type() == QFontEngine::Multi) {
3059	QFontEngineMulti *multiEngine = static_cast<QFontEngineMulti *>(engine);
3060	multiEngine->ensureEngineAt(at: 0);
3061	engine = multiEngine->engine(at: 0);
3062	}
3063
3064	glyph_t glyph = engine->glyphIndex(ucs4: ellipsisChar);
3065
3066	QGlyphLayout glyphs;
3067	glyphs.numGlyphs = 1;
3068	glyphs.glyphs = &glyph;
3069	glyphs.advances = &ellipsisWidth;
3070
3071	if (glyph != 0) {
3072	engine->recalcAdvances(&glyphs, { });
3073
3074	ellipsisText = ellipsisChar;
3075	} else {
3076	glyph = engine->glyphIndex(ucs4: '.');
3077	if (glyph != 0) {
3078	engine->recalcAdvances(&glyphs, { });
3079
3080	ellipsisWidth *= 3;
3081	ellipsisText = QStringLiteral("...");
3082	} else {
3083	engine = fnt.d->engineForScript(script: QChar::Script_Common);
3084	glyph = engine->glyphIndex(ucs4: ellipsisChar);
3085	engine->recalcAdvances(&glyphs, { });
3086	ellipsisText = ellipsisChar;
3087	}
3088	}
3089	}
3090
3091	const QFixed availableWidth = width - ellipsisWidth;
3092	if (availableWidth < 0)
3093	return QString();
3094
3095	const QCharAttributes *attributes = this->attributes();
3096	if (!attributes)
3097	return QString();
3098
3099	constexpr char16_t ZWJ = u'\x200d'; // ZERO-WIDTH JOINER
3100
3101	if (mode == Qt::ElideRight) {
3102	QFixed currentWidth;
3103	int pos;
3104	int nextBreak = from;
3105
3106	do {
3107	pos = nextBreak;
3108
3109	++nextBreak;
3110	while (nextBreak < layoutData->string.size() && !attributes[nextBreak].graphemeBoundary)
3111	++nextBreak;
3112
3113	currentWidth += this->width(from: pos, len: nextBreak - pos);
3114	} while (nextBreak < to
3115	&& currentWidth < availableWidth);
3116
3117	if (nextCharJoins(string: layoutData->string, pos))
3118	ellipsisText.prepend(c: ZWJ);
3119
3120	return stringMidRetainingBidiCC(string: layoutData->string,
3121	ellidePrefix: QString(), ellideSuffix: ellipsisText,
3122	subStringFrom: from, subStringTo: to,
3123	midStart: from, midLength: pos - from);
3124	} else if (mode == Qt::ElideLeft) {
3125	QFixed currentWidth;
3126	int pos;
3127	int nextBreak = to;
3128
3129	do {
3130	pos = nextBreak;
3131
3132	--nextBreak;
3133	while (nextBreak > 0 && !attributes[nextBreak].graphemeBoundary)
3134	--nextBreak;
3135
3136	currentWidth += this->width(from: nextBreak, len: pos - nextBreak);
3137	} while (nextBreak > from
3138	&& currentWidth < availableWidth);
3139
3140	if (prevCharJoins(string: layoutData->string, pos))
3141	ellipsisText.append(c: ZWJ);
3142
3143	return stringMidRetainingBidiCC(string: layoutData->string,
3144	ellidePrefix: ellipsisText, ellideSuffix: QString(),
3145	subStringFrom: from, subStringTo: to,
3146	midStart: pos, midLength: to - pos);
3147	} else if (mode == Qt::ElideMiddle) {
3148	QFixed leftWidth;
3149	QFixed rightWidth;
3150
3151	int leftPos = from;
3152	int nextLeftBreak = from;
3153
3154	int rightPos = to;
3155	int nextRightBreak = to;
3156
3157	do {
3158	leftPos = nextLeftBreak;
3159	rightPos = nextRightBreak;
3160
3161	++nextLeftBreak;
3162	while (nextLeftBreak < layoutData->string.size() && !attributes[nextLeftBreak].graphemeBoundary)
3163	++nextLeftBreak;
3164
3165	--nextRightBreak;
3166	while (nextRightBreak > from && !attributes[nextRightBreak].graphemeBoundary)
3167	--nextRightBreak;
3168
3169	leftWidth += this->width(from: leftPos, len: nextLeftBreak - leftPos);
3170	rightWidth += this->width(from: nextRightBreak, len: rightPos - nextRightBreak);
3171	} while (nextLeftBreak < to
3172	&& nextRightBreak > from
3173	&& leftWidth + rightWidth < availableWidth);
3174
3175	if (nextCharJoins(string: layoutData->string, pos: leftPos))
3176	ellipsisText.prepend(c: ZWJ);
3177	if (prevCharJoins(string: layoutData->string, pos: rightPos))
3178	ellipsisText.append(c: ZWJ);
3179
3180	return QStringView{layoutData->string}.mid(pos: from, n: leftPos - from) + ellipsisText + QStringView{layoutData->string}.mid(pos: rightPos, n: to - rightPos);
3181	}
3182
3183	return layoutData->string.mid(position: from, n: to - from);
3184	}
3185
3186	void QTextEngine::setBoundary(int strPos) const
3187	{
3188	const int item = findItem(strPos);
3189	if (item < 0)
3190	return;
3191
3192	QScriptItem newItem = layoutData->items.at(i: item);
3193	if (newItem.position != strPos) {
3194	newItem.position = strPos;
3195	layoutData->items.insert(i: item + 1, t: newItem);
3196	}
3197	}
3198
3199	QFixed QTextEngine::calculateTabWidth(int item, QFixed x) const
3200	{
3201	const QScriptItem &si = layoutData->items.at(i: item);
3202
3203	QFixed dpiScale = 1;
3204	if (QTextDocumentPrivate::get(block) != nullptr && QTextDocumentPrivate::get(block)->layout() != nullptr) {
3205	QPaintDevice *pdev = QTextDocumentPrivate::get(block)->layout()->paintDevice();
3206	if (pdev)
3207	dpiScale = QFixed::fromReal(r: pdev->logicalDpiY() / qreal(qt_defaultDpiY()));
3208	} else {
3209	dpiScale = QFixed::fromReal(r: fnt.d->dpi / qreal(qt_defaultDpiY()));
3210	}
3211
3212	QList<QTextOption::Tab> tabArray = option.tabs();
3213	if (!tabArray.isEmpty()) {
3214	if (isRightToLeft()) { // rebase the tabArray positions.
3215	auto isLeftOrRightTab = [](const QTextOption::Tab &tab) {
3216	return tab.type == QTextOption::LeftTab || tab.type == QTextOption::RightTab;
3217	};
3218	const auto cbegin = tabArray.cbegin();
3219	const auto cend = tabArray.cend();
3220	const auto cit = std::find_if(first: cbegin, last: cend, pred: isLeftOrRightTab);
3221	if (cit != cend) {
3222	const int index = std::distance(first: cbegin, last: cit);
3223	auto iter = tabArray.begin() + index;
3224	const auto end = tabArray.end();
3225	while (iter != end) {
3226	QTextOption::Tab &tab = *iter;
3227	if (tab.type == QTextOption::LeftTab)
3228	tab.type = QTextOption::RightTab;
3229	else if (tab.type == QTextOption::RightTab)
3230	tab.type = QTextOption::LeftTab;
3231	++iter;
3232	}
3233	}
3234	}
3235	for (const QTextOption::Tab &tabSpec : std::as_const(t&: tabArray)) {
3236	QFixed tab = QFixed::fromReal(r: tabSpec.position) * dpiScale;
3237	if (tab > x) { // this is the tab we need.
3238	int tabSectionEnd = layoutData->string.size();
3239	if (tabSpec.type == QTextOption::RightTab || tabSpec.type == QTextOption::CenterTab) {
3240	// find next tab to calculate the width required.
3241	tab = QFixed::fromReal(r: tabSpec.position);
3242	for (int i=item + 1; i < layoutData->items.size(); i++) {
3243	const QScriptItem &item = layoutData->items.at(i);
3244	if (item.analysis.flags == QScriptAnalysis::TabOrObject) { // found it.
3245	tabSectionEnd = item.position;
3246	break;
3247	}
3248	}
3249	}
3250	else if (tabSpec.type == QTextOption::DelimiterTab)
3251	// find delimiter character to calculate the width required
3252	tabSectionEnd = qMax(a: si.position, b: layoutData->string.indexOf(ch: tabSpec.delimiter, from: si.position) + 1);
3253
3254	if (tabSectionEnd > si.position) {
3255	QFixed length;
3256	// Calculate the length of text between this tab and the tabSectionEnd
3257	for (int i=item; i < layoutData->items.size(); i++) {
3258	const QScriptItem &item = layoutData->items.at(i);
3259	if (item.position > tabSectionEnd || item.position <= si.position)
3260	continue;
3261	shape(item: i); // first, lets make sure relevant text is already shaped
3262	if (item.analysis.flags == QScriptAnalysis::Object) {
3263	length += item.width;
3264	continue;
3265	}
3266	QGlyphLayout glyphs = this->shapedGlyphs(si: &item);
3267	const int end = qMin(a: item.position + item.num_glyphs, b: tabSectionEnd) - item.position;
3268	for (int i=0; i < end; i++)
3269	length += glyphs.advances[i] * !glyphs.attributes[i].dontPrint;
3270	if (end + item.position == tabSectionEnd && tabSpec.type == QTextOption::DelimiterTab) // remove half of matching char
3271	length -= glyphs.advances[end] / 2 * !glyphs.attributes[end].dontPrint;
3272	}
3273
3274	switch (tabSpec.type) {
3275	case QTextOption::CenterTab:
3276	length /= 2;
3277	Q_FALLTHROUGH();
3278	case QTextOption::DelimiterTab:
3279	case QTextOption::RightTab:
3280	tab = QFixed::fromReal(r: tabSpec.position) * dpiScale - length;
3281	if (tab < x) // default to tab taking no space
3282	return QFixed();
3283	break;
3284	case QTextOption::LeftTab:
3285	break;
3286	}
3287	}
3288	return tab - x;
3289	}
3290	}
3291	}
3292	QFixed tab = QFixed::fromReal(r: option.tabStopDistance());
3293	if (tab <= 0)
3294	tab = 80; // default
3295	tab *= dpiScale;
3296	QFixed nextTabPos = ((x / tab).truncate() + 1) * tab;
3297	QFixed tabWidth = nextTabPos - x;
3298
3299	return tabWidth;
3300	}
3301
3302	namespace {
3303	class FormatRangeComparatorByStart {
3304	const QList<QTextLayout::FormatRange> &list;
3305	public:
3306	FormatRangeComparatorByStart(const QList<QTextLayout::FormatRange> &list) : list(list) { }
3307	bool operator()(int a, int b) {
3308	return list.at(i: a).start < list.at(i: b).start;
3309	}
3310	};
3311	class FormatRangeComparatorByEnd {
3312	const QList<QTextLayout::FormatRange> &list;
3313	public:
3314	FormatRangeComparatorByEnd(const QList<QTextLayout::FormatRange> &list) : list(list) { }
3315	bool operator()(int a, int b) {
3316	return list.at(i: a).start + list.at(i: a).length < list.at(i: b).start + list.at(i: b).length;
3317	}
3318	};
3319	}
3320
3321	void QTextEngine::resolveFormats() const
3322	{
3323	if (!specialData || specialData->formats.isEmpty())
3324	return;
3325	Q_ASSERT(specialData->resolvedFormats.isEmpty());
3326
3327	QTextFormatCollection *collection = formatCollection();
3328
3329	QList<QTextCharFormat> resolvedFormats(layoutData->items.size());
3330
3331	QVarLengthArray<int, 64> formatsSortedByStart;
3332	formatsSortedByStart.reserve(sz: specialData->formats.size());
3333	for (int i = 0; i < specialData->formats.size(); ++i) {
3334	if (specialData->formats.at(i).length >= 0)
3335	formatsSortedByStart.append(t: i);
3336	}
3337	QVarLengthArray<int, 64> formatsSortedByEnd = formatsSortedByStart;
3338	std::sort(first: formatsSortedByStart.begin(), last: formatsSortedByStart.end(),
3339	comp: FormatRangeComparatorByStart(specialData->formats));
3340	std::sort(first: formatsSortedByEnd.begin(), last: formatsSortedByEnd.end(),
3341	comp: FormatRangeComparatorByEnd(specialData->formats));
3342
3343	QVarLengthArray<int, 16> currentFormats;
3344	const int *startIt = formatsSortedByStart.constBegin();
3345	const int *endIt = formatsSortedByEnd.constBegin();
3346
3347	for (int i = 0; i < layoutData->items.size(); ++i) {
3348	const QScriptItem *si = &layoutData->items.at(i);
3349	int end = si->position + length(si);
3350
3351	while (startIt != formatsSortedByStart.constEnd() &&
3352	specialData->formats.at(i: *startIt).start <= si->position) {
3353	currentFormats.insert(before: std::upper_bound(first: currentFormats.begin(), last: currentFormats.end(), val: *startIt),
3354	x: *startIt);
3355	++startIt;
3356	}
3357	while (endIt != formatsSortedByEnd.constEnd() &&
3358	specialData->formats.at(i: *endIt).start + specialData->formats.at(i: *endIt).length < end) {
3359	int *currentFormatIterator = std::lower_bound(first: currentFormats.begin(), last: currentFormats.end(), val: *endIt);
3360	if (*endIt < *currentFormatIterator)
3361	currentFormatIterator = currentFormats.end();
3362	currentFormats.remove(i: currentFormatIterator - currentFormats.begin());
3363	++endIt;
3364	}
3365
3366	QTextCharFormat &format = resolvedFormats[i];
3367	if (QTextDocumentPrivate::get(block) != nullptr) {
3368	// when we have a QTextDocumentPrivate, formatIndex might still return a valid index based
3369	// on the preeditPosition. for all other cases, we cleared the resolved format indices
3370	format = collection->charFormat(index: formatIndex(si));
3371	}
3372	if (!currentFormats.isEmpty()) {
3373	for (int cur : currentFormats) {
3374	const QTextLayout::FormatRange &range = specialData->formats.at(i: cur);
3375	Q_ASSERT(range.start <= si->position && range.start + range.length >= end);
3376	format.merge(other: range.format);
3377	}
3378	format = collection->charFormat(index: collection->indexForFormat(f: format)); // get shared copy
3379	}
3380	}
3381
3382	specialData->resolvedFormats = resolvedFormats;
3383	}
3384
3385	QFixed QTextEngine::leadingSpaceWidth(const QScriptLine &line)
3386	{
3387	if (!line.hasTrailingSpaces
3388	|| (option.flags() & QTextOption::IncludeTrailingSpaces)
3389	|| !isRightToLeft())
3390	return QFixed();
3391
3392	return width(from: line.from + line.length, len: line.trailingSpaces);
3393	}
3394
3395	QFixed QTextEngine::alignLine(const QScriptLine &line)
3396	{
3397	QFixed x = 0;
3398	justify(line);
3399	// if width is QFIXED_MAX that means we used setNumColumns() and that implicitly makes this line left aligned.
3400	if (!line.justified && line.width != QFIXED_MAX) {
3401	int align = option.alignment();
3402	if (align & Qt::AlignJustify && isRightToLeft())
3403	align = Qt::AlignRight;
3404	if (align & Qt::AlignRight)
3405	x = line.width - (line.textAdvance);
3406	else if (align & Qt::AlignHCenter)
3407	x = (line.width - line.textAdvance)/2;
3408	}
3409	return x;
3410	}
3411
3412	QFixed QTextEngine::offsetInLigature(const QScriptItem *si, int pos, int max, int glyph_pos)
3413	{
3414	unsigned short *logClusters = this->logClusters(si);
3415	const QGlyphLayout &glyphs = shapedGlyphs(si);
3416
3417	int offsetInCluster = 0;
3418	for (int i = pos - 1; i >= 0; i--) {
3419	if (logClusters[i] == glyph_pos)
3420	offsetInCluster++;
3421	else
3422	break;
3423	}
3424
3425	// in the case that the offset is inside a (multi-character) glyph,
3426	// interpolate the position.
3427	if (offsetInCluster > 0) {
3428	int clusterLength = 0;
3429	for (int i = pos - offsetInCluster; i < max; i++) {
3430	if (logClusters[i] == glyph_pos)
3431	clusterLength++;
3432	else
3433	break;
3434	}
3435	if (clusterLength)
3436	return glyphs.advances[glyph_pos] * offsetInCluster / clusterLength;
3437	}
3438
3439	return 0;
3440	}
3441
3442	// Scan in logClusters[from..to-1] for glyph_pos
3443	int QTextEngine::getClusterLength(unsigned short *logClusters,
3444	const QCharAttributes *attributes,
3445	int from, int to, int glyph_pos, int *start)
3446	{
3447	int clusterLength = 0;
3448	for (int i = from; i < to; i++) {
3449	if (logClusters[i] == glyph_pos && attributes[i].graphemeBoundary) {
3450	if (*start < 0)
3451	*start = i;
3452	clusterLength++;
3453	}
3454	else if (clusterLength)
3455	break;
3456	}
3457	return clusterLength;
3458	}
3459
3460	int QTextEngine::positionInLigature(const QScriptItem *si, int end,
3461	QFixed x, QFixed edge, int glyph_pos,
3462	bool cursorOnCharacter)
3463	{
3464	unsigned short *logClusters = this->logClusters(si);
3465	int clusterStart = -1;
3466	int clusterLength = 0;
3467
3468	if (si->analysis.script != QChar::Script_Common &&
3469	si->analysis.script != QChar::Script_Greek &&
3470	si->analysis.script != QChar::Script_Latin &&
3471	si->analysis.script != QChar::Script_Hiragana &&
3472	si->analysis.script != QChar::Script_Katakana &&
3473	si->analysis.script != QChar::Script_Bopomofo &&
3474	si->analysis.script != QChar::Script_Han) {
3475	if (glyph_pos == -1)
3476	return si->position + end;
3477	else {
3478	int i;
3479	for (i = 0; i < end; i++)
3480	if (logClusters[i] == glyph_pos)
3481	break;
3482	return si->position + i;
3483	}
3484	}
3485
3486	if (glyph_pos == -1 && end > 0)
3487	glyph_pos = logClusters[end - 1];
3488	else {
3489	if (x <= edge)
3490	glyph_pos--;
3491	}
3492
3493	const QCharAttributes *attrs = attributes() + si->position;
3494	logClusters = this->logClusters(si);
3495	clusterLength = getClusterLength(logClusters, attributes: attrs, from: 0, to: end, glyph_pos, start: &clusterStart);
3496
3497	if (clusterLength) {
3498	const QGlyphLayout &glyphs = shapedGlyphs(si);
3499	QFixed glyphWidth = glyphs.effectiveAdvance(item: glyph_pos);
3500	// the approximate width of each individual element of the ligature
3501	QFixed perItemWidth = glyphWidth / clusterLength;
3502	if (perItemWidth <= 0)
3503	return si->position + clusterStart;
3504	QFixed left = x > edge ? edge : edge - glyphWidth;
3505	int n = ((x - left) / perItemWidth).floor().toInt();
3506	QFixed dist = x - left - n * perItemWidth;
3507	int closestItem = dist > (perItemWidth / 2) ? n + 1 : n;
3508	if (cursorOnCharacter && closestItem > 0)
3509	closestItem--;
3510	int pos = clusterStart + closestItem;
3511	// Jump to the next grapheme boundary
3512	while (pos < end && !attrs[pos].graphemeBoundary)
3513	pos++;
3514	return si->position + pos;
3515	}
3516	return si->position + end;
3517	}
3518
3519	int QTextEngine::previousLogicalPosition(int oldPos) const
3520	{
3521	const QCharAttributes *attrs = attributes();
3522	int len = block.isValid() ? block.length() - 1
3523	: layoutData->string.size();
3524	Q_ASSERT(len <= layoutData->string.size());
3525	if (!attrs || oldPos <= 0 || oldPos > len)
3526	return oldPos;
3527
3528	oldPos--;
3529	while (oldPos && !attrs[oldPos].graphemeBoundary)
3530	oldPos--;
3531	return oldPos;
3532	}
3533
3534	int QTextEngine::nextLogicalPosition(int oldPos) const
3535	{
3536	const QCharAttributes *attrs = attributes();
3537	int len = block.isValid() ? block.length() - 1
3538	: layoutData->string.size();
3539	Q_ASSERT(len <= layoutData->string.size());
3540	if (!attrs || oldPos < 0 || oldPos >= len)
3541	return oldPos;
3542
3543	oldPos++;
3544	while (oldPos < len && !attrs[oldPos].graphemeBoundary)
3545	oldPos++;
3546	return oldPos;
3547	}
3548
3549	int QTextEngine::lineNumberForTextPosition(int pos)
3550	{
3551	if (!layoutData)
3552	itemize();
3553	if (pos == layoutData->string.size() && lines.size())
3554	return lines.size() - 1;
3555	for (int i = 0; i < lines.size(); ++i) {
3556	const QScriptLine& line = lines[i];
3557	if (line.from + line.length + line.trailingSpaces > pos)
3558	return i;
3559	}
3560	return -1;
3561	}
3562
3563	std::vector<int> QTextEngine::insertionPointsForLine(int lineNum)
3564	{
3565	QTextLineItemIterator iterator(this, lineNum);
3566
3567	std::vector<int> insertionPoints;
3568	insertionPoints.reserve(n: size_t(iterator.line.length));
3569
3570	bool lastLine = lineNum >= lines.size() - 1;
3571
3572	while (!iterator.atEnd()) {
3573	const QScriptItem &si = iterator.next();
3574
3575	int end = iterator.itemEnd;
3576	if (lastLine && iterator.item == iterator.lastItem)
3577	++end; // the last item in the last line -> insert eol position
3578	if (si.analysis.bidiLevel % 2) {
3579	for (int i = end - 1; i >= iterator.itemStart; --i)
3580	insertionPoints.push_back(x: i);
3581	} else {
3582	for (int i = iterator.itemStart; i < end; ++i)
3583	insertionPoints.push_back(x: i);
3584	}
3585	}
3586	return insertionPoints;
3587	}
3588
3589	int QTextEngine::endOfLine(int lineNum)
3590	{
3591	const auto insertionPoints = insertionPointsForLine(lineNum);
3592	if (insertionPoints.size() > 0)
3593	return insertionPoints.back();
3594	return 0;
3595	}
3596
3597	int QTextEngine::beginningOfLine(int lineNum)
3598	{
3599	const auto insertionPoints = insertionPointsForLine(lineNum);
3600	if (insertionPoints.size() > 0)
3601	return insertionPoints.front();
3602	return 0;
3603	}
3604
3605	int QTextEngine::positionAfterVisualMovement(int pos, QTextCursor::MoveOperation op)
3606	{
3607	itemize();
3608
3609	bool moveRight = (op == QTextCursor::Right);
3610	bool alignRight = isRightToLeft();
3611	if (!layoutData->hasBidi)
3612	return moveRight ^ alignRight ? nextLogicalPosition(oldPos: pos) : previousLogicalPosition(oldPos: pos);
3613
3614	int lineNum = lineNumberForTextPosition(pos);
3615	if (lineNum < 0)
3616	return pos;
3617
3618	const auto insertionPoints = insertionPointsForLine(lineNum);
3619	for (size_t i = 0, max = insertionPoints.size(); i < max; ++i)
3620	if (pos == insertionPoints[i]) {
3621	if (moveRight) {
3622	if (i + 1 < max)
3623	return insertionPoints[i + 1];
3624	} else {
3625	if (i > 0)
3626	return insertionPoints[i - 1];
3627	}
3628
3629	if (moveRight ^ alignRight) {
3630	if (lineNum + 1 < lines.size())
3631	return alignRight ? endOfLine(lineNum: lineNum + 1) : beginningOfLine(lineNum: lineNum + 1);
3632	}
3633	else {
3634	if (lineNum > 0)
3635	return alignRight ? beginningOfLine(lineNum: lineNum - 1) : endOfLine(lineNum: lineNum - 1);
3636	}
3637
3638	break;
3639	}
3640
3641	return pos;
3642	}
3643
3644	void QTextEngine::addItemDecoration(QPainter *painter, const QLineF &line, ItemDecorationList *decorationList)
3645	{
3646	if (delayDecorations) {
3647	decorationList->append(t: ItemDecoration(line.x1(), line.x2(), line.y1(), painter->pen()));
3648	} else {
3649	painter->drawLine(l: line);
3650	}
3651	}
3652
3653	void QTextEngine::addUnderline(QPainter *painter, const QLineF &line)
3654	{
3655	// qDebug() << "Adding underline:" << line;
3656	addItemDecoration(painter, line, decorationList: &underlineList);
3657	}
3658
3659	void QTextEngine::addStrikeOut(QPainter *painter, const QLineF &line)
3660	{
3661	addItemDecoration(painter, line, decorationList: &strikeOutList);
3662	}
3663
3664	void QTextEngine::addOverline(QPainter *painter, const QLineF &line)
3665	{
3666	addItemDecoration(painter, line, decorationList: &overlineList);
3667	}
3668
3669	void QTextEngine::drawItemDecorationList(QPainter *painter, const ItemDecorationList &decorationList)
3670	{
3671	// qDebug() << "Drawing" << decorationList.size() << "decorations";
3672	if (decorationList.isEmpty())
3673	return;
3674
3675	for (const ItemDecoration &decoration : decorationList) {
3676	painter->setPen(decoration.pen);
3677	painter->drawLine(l: QLineF(decoration.x1, decoration.y, decoration.x2, decoration.y));
3678	}
3679	}
3680
3681	void QTextEngine::drawDecorations(QPainter *painter)
3682	{
3683	QPen oldPen = painter->pen();
3684
3685	adjustUnderlines();
3686	drawItemDecorationList(painter, decorationList: underlineList);
3687	drawItemDecorationList(painter, decorationList: strikeOutList);
3688	drawItemDecorationList(painter, decorationList: overlineList);
3689
3690	clearDecorations();
3691
3692	painter->setPen(oldPen);
3693	}
3694
3695	void QTextEngine::clearDecorations()
3696	{
3697	underlineList.clear();
3698	strikeOutList.clear();
3699	overlineList.clear();
3700	}
3701
3702	void QTextEngine::adjustUnderlines()
3703	{
3704	// qDebug() << __PRETTY_FUNCTION__ << underlineList.count() << "underlines";
3705	if (underlineList.isEmpty())
3706	return;
3707
3708	ItemDecorationList::iterator start = underlineList.begin();
3709	ItemDecorationList::iterator end = underlineList.end();
3710	ItemDecorationList::iterator it = start;
3711	qreal underlinePos = start->y;
3712	qreal penWidth = start->pen.widthF();
3713	qreal lastLineEnd = start->x1;
3714
3715	while (it != end) {
3716	if (qFuzzyCompare(p1: lastLineEnd, p2: it->x1)) { // no gap between underlines
3717	underlinePos = qMax(a: underlinePos, b: it->y);
3718	penWidth = qMax(a: penWidth, b: it->pen.widthF());
3719	} else { // gap between this and the last underline
3720	adjustUnderlines(start, end: it, underlinePos, penWidth);
3721	start = it;
3722	underlinePos = start->y;
3723	penWidth = start->pen.widthF();
3724	}
3725	lastLineEnd = it->x2;
3726	++it;
3727	}
3728
3729	adjustUnderlines(start, end, underlinePos, penWidth);
3730	}
3731
3732	void QTextEngine::adjustUnderlines(ItemDecorationList::iterator start,
3733	ItemDecorationList::iterator end,
3734	qreal underlinePos, qreal penWidth)
3735	{
3736	for (ItemDecorationList::iterator it = start; it != end; ++it) {
3737	it->y = underlinePos;
3738	it->pen.setWidthF(penWidth);
3739	}
3740	}
3741
3742	QStackTextEngine::QStackTextEngine(const QString &string, const QFont &f)
3743	: QTextEngine(string, f),
3744	_layoutData(string, _memory, MemSize)
3745	{
3746	stackEngine = true;
3747	layoutData = &_layoutData;
3748	}
3749
3750	QTextItemInt::QTextItemInt(const QScriptItem &si, QFont *font, const QTextCharFormat &format)
3751	: charFormat(format),
3752	f(font),
3753	fontEngine(font->d->engineForScript(script: si.analysis.script))
3754	{
3755	Q_ASSERT(fontEngine);
3756
3757	initWithScriptItem(si);
3758	}
3759
3760	QTextItemInt::QTextItemInt(const QGlyphLayout &g, QFont *font, const QChar *chars_, int numChars, QFontEngine *fe, const QTextCharFormat &format)
3761	: charFormat(format),
3762	num_chars(numChars),
3763	chars(chars_),
3764	f(font),
3765	glyphs(g),
3766	fontEngine(fe)
3767	{
3768	}
3769
3770	// Fix up flags and underlineStyle with given info
3771	void QTextItemInt::initWithScriptItem(const QScriptItem &si)
3772	{
3773	// explicitly initialize flags so that initFontAttributes can be called
3774	// multiple times on the same TextItem
3775	flags = { };
3776	if (si.analysis.bidiLevel %2)
3777	flags |= QTextItem::RightToLeft;
3778	ascent = si.ascent;
3779	descent = si.descent;
3780
3781	if (charFormat.hasProperty(propertyId: QTextFormat::TextUnderlineStyle)) {
3782	underlineStyle = charFormat.underlineStyle();
3783	} else if (charFormat.boolProperty(propertyId: QTextFormat::FontUnderline)
3784	|| f->d->underline) {
3785	underlineStyle = QTextCharFormat::SingleUnderline;
3786	}
3787
3788	// compat
3789	if (underlineStyle == QTextCharFormat::SingleUnderline)
3790	flags |= QTextItem::Underline;
3791
3792	if (f->d->overline || charFormat.fontOverline())
3793	flags |= QTextItem::Overline;
3794	if (f->d->strikeOut || charFormat.fontStrikeOut())
3795	flags |= QTextItem::StrikeOut;
3796	}
3797
3798	QTextItemInt QTextItemInt::midItem(QFontEngine *fontEngine, int firstGlyphIndex, int numGlyphs) const
3799	{
3800	QTextItemInt ti = *this;
3801	const int end = firstGlyphIndex + numGlyphs;
3802	ti.glyphs = glyphs.mid(position: firstGlyphIndex, n: numGlyphs);
3803	ti.fontEngine = fontEngine;
3804
3805	if (logClusters && chars) {
3806	const int logClusterOffset = logClusters[0];
3807	while (logClusters[ti.chars - chars] - logClusterOffset < firstGlyphIndex)
3808	++ti.chars;
3809
3810	ti.logClusters += (ti.chars - chars);
3811
3812	ti.num_chars = 0;
3813	int char_start = ti.chars - chars;
3814	while (char_start + ti.num_chars < num_chars && ti.logClusters[ti.num_chars] - logClusterOffset < end)
3815	++ti.num_chars;
3816	}
3817	return ti;
3818	}
3819
3820
3821	QTransform qt_true_matrix(qreal w, qreal h, const QTransform &x)
3822	{
3823	QRectF rect = x.mapRect(QRectF(0, 0, w, h));
3824	return x * QTransform::fromTranslate(dx: -rect.x(), dy: -rect.y());
3825	}
3826
3827
3828	glyph_metrics_t glyph_metrics_t::transformed(const QTransform &matrix) const
3829	{
3830	if (matrix.type() < QTransform::TxTranslate)
3831	return *this;
3832
3833	glyph_metrics_t m = *this;
3834
3835	qreal w = width.toReal();
3836	qreal h = height.toReal();
3837	QTransform xform = qt_true_matrix(w, h, x: matrix);
3838
3839	QRectF rect(0, 0, w, h);
3840	rect = xform.mapRect(rect);
3841	m.width = QFixed::fromReal(r: rect.width());
3842	m.height = QFixed::fromReal(r: rect.height());
3843
3844	QLineF l = xform.map(l: QLineF(x.toReal(), y.toReal(), xoff.toReal(), yoff.toReal()));
3845
3846	m.x = QFixed::fromReal(r: l.x1());
3847	m.y = QFixed::fromReal(r: l.y1());
3848
3849	// The offset is relative to the baseline which is why we use dx/dy of the line
3850	m.xoff = QFixed::fromReal(r: l.dx());
3851	m.yoff = QFixed::fromReal(r: l.dy());
3852
3853	return m;
3854	}
3855
3856	QTextLineItemIterator::QTextLineItemIterator(QTextEngine *_eng, int _lineNum, const QPointF &pos,
3857	const QTextLayout::FormatRange *_selection)
3858	: eng(_eng),
3859	line(eng->lines[_lineNum]),
3860	si(nullptr),
3861	lineNum(_lineNum),
3862	lineEnd(line.from + line.length),
3863	firstItem(eng->findItem(strPos: line.from)),
3864	lastItem(eng->findItem(strPos: lineEnd - 1, firstItem)),
3865	nItems((firstItem >= 0 && lastItem >= firstItem)? (lastItem-firstItem+1) : 0),
3866	logicalItem(-1),
3867	item(-1),
3868	visualOrder(nItems),
3869	selection(_selection)
3870	{
3871	x = QFixed::fromReal(r: pos.x());
3872
3873	x += line.x;
3874
3875	x += eng->alignLine(line);
3876
3877	if (nItems > 0) {
3878	QVarLengthArray<uchar> levels(nItems);
3879	for (int i = 0; i < nItems; ++i)
3880	levels[i] = eng->layoutData->items.at(i: i + firstItem).analysis.bidiLevel;
3881	QTextEngine::bidiReorder(numItems: nItems, levels: levels.data(), visualOrder: visualOrder.data());
3882	}
3883
3884	eng->shapeLine(line);
3885	}
3886
3887	QScriptItem &QTextLineItemIterator::next()
3888	{
3889	x += itemWidth;
3890
3891	++logicalItem;
3892	item = visualOrder[logicalItem] + firstItem;
3893	itemLength = eng->length(item);
3894	si = &eng->layoutData->items[item];
3895	if (!si->num_glyphs)
3896	eng->shape(item);
3897
3898	itemStart = qMax(a: line.from, b: si->position);
3899	itemEnd = qMin(a: lineEnd, b: si->position + itemLength);
3900
3901	if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
3902	glyphsStart = 0;
3903	glyphsEnd = 1;
3904	itemWidth = si->width;
3905	return *si;
3906	}
3907
3908	unsigned short *logClusters = eng->logClusters(si);
3909	QGlyphLayout glyphs = eng->shapedGlyphs(si);
3910
3911	glyphsStart = logClusters[itemStart - si->position];
3912	glyphsEnd = (itemEnd == si->position + itemLength) ? si->num_glyphs : logClusters[itemEnd - si->position];
3913
3914	// show soft-hyphen at line-break
3915	if (si->position + itemLength >= lineEnd
3916	&& eng->layoutData->string.at(i: lineEnd - 1).unicode() == QChar::SoftHyphen)
3917	glyphs.attributes[glyphsEnd - 1].dontPrint = false;
3918
3919	itemWidth = 0;
3920	for (int g = glyphsStart; g < glyphsEnd; ++g)
3921	itemWidth += glyphs.effectiveAdvance(item: g);
3922
3923	return *si;
3924	}
3925
3926	bool QTextLineItemIterator::getSelectionBounds(QFixed *selectionX, QFixed *selectionWidth) const
3927	{
3928	*selectionX = *selectionWidth = 0;
3929
3930	if (!selection)
3931	return false;
3932
3933	if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
3934	if (si->position >= selection->start + selection->length
3935	|| si->position + itemLength <= selection->start)
3936	return false;
3937
3938	*selectionX = x;
3939	*selectionWidth = itemWidth;
3940	} else {
3941	unsigned short *logClusters = eng->logClusters(si);
3942	QGlyphLayout glyphs = eng->shapedGlyphs(si);
3943
3944	int from = qMax(a: itemStart, b: selection->start) - si->position;
3945	int to = qMin(a: itemEnd, b: selection->start + selection->length) - si->position;
3946	if (from >= to)
3947	return false;
3948
3949	int start_glyph = logClusters[from];
3950	int end_glyph = (to == itemLength) ? si->num_glyphs : logClusters[to];
3951	QFixed soff;
3952	QFixed swidth;
3953	if (si->analysis.bidiLevel %2) {
3954	for (int g = glyphsEnd - 1; g >= end_glyph; --g)
3955	soff += glyphs.effectiveAdvance(item: g);
3956	for (int g = end_glyph - 1; g >= start_glyph; --g)
3957	swidth += glyphs.effectiveAdvance(item: g);
3958	} else {
3959	for (int g = glyphsStart; g < start_glyph; ++g)
3960	soff += glyphs.effectiveAdvance(item: g);
3961	for (int g = start_glyph; g < end_glyph; ++g)
3962	swidth += glyphs.effectiveAdvance(item: g);
3963	}
3964
3965	// If the starting character is in the middle of a ligature,
3966	// selection should only contain the right part of that ligature
3967	// glyph, so we need to get the width of the left part here and
3968	// add it to *selectionX
3969	QFixed leftOffsetInLigature = eng->offsetInLigature(si, pos: from, max: to, glyph_pos: start_glyph);
3970	*selectionX = x + soff + leftOffsetInLigature;
3971	*selectionWidth = swidth - leftOffsetInLigature;
3972	// If the ending character is also part of a ligature, swidth does
3973	// not contain that part yet, we also need to find out the width of
3974	// that left part
3975	*selectionWidth += eng->offsetInLigature(si, pos: to, max: itemLength, glyph_pos: end_glyph);
3976	}
3977	return true;
3978	}
3979
3980	QT_END_NAMESPACE
3981