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