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