Bug Summary

File:libraries/qtbidi/qt_bidi.cpp
Warning:line 428, column 17
Value stored to 'last' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -O2 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name qt_bidi.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/runner/work/LibreCAD/LibreCAD/libraries/qtbidi -fcoverage-compilation-dir=/home/runner/work/LibreCAD/LibreCAD/libraries/qtbidi -resource-dir /usr/lib/llvm-21/lib/clang/21 -D _REENTRANT -D QT_NO_DEBUG -D QT_CORE_LIB -I . -I ../../../Qt/6.9.0/gcc_64/include -I ../../../Qt/6.9.0/gcc_64/include/QtCore -I release -I ../../../Qt/6.9.0/gcc_64/mkspecs/linux-g++ -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/15/../../../../include/c++/15 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/15/../../../../include/x86_64-linux-gnu/c++/15 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/15/../../../../include/c++/15/backward -internal-isystem /usr/lib/llvm-21/lib/clang/21/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/15/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -std=gnu++1z -fdeprecated-macro -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcxx-exceptions -fexceptions -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/runner/work/LibreCAD/LibreCAD/out/2026-11-06-031751-4837-1 -x c++ qt_bidi.cpp
1// Copyright (C) 2021 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3// Copyright (C) 2026 LibreCAD.org
4// Copyright (C) 2026 Dongxu Li (github.com/dxli)
5//
6// Qt-derived bidi resolver. See README.librecad for provenance and local changes.
7// Qt code is used under GPL-2.0-only; modifications are GPL-2.0-or-later.
8
9#include "qt_bidi.h"
10#include <QDebug>
11#include <QStringView>
12#include <QVarLengthArray>
13#include <algorithm>
14#include <cstring>
15#include <numeric>
16#include <limits>
17#include <stdexcept>
18
19namespace lc::qtbidi {
20namespace {
21struct BidiAnalysis {
22 enum BidiFlags {
23 BidiResetToParagraphLevel = 1,
24 BidiMaybeResetToParagraphLevel = 2,
25 BidiMirrored = 4,
26 BidiBN = 8
27 };
28 unsigned short bidiFlags;
29 unsigned char bidiLevel;
30 QChar::Direction bidiDirection;
31};
32
33// #define DEBUG_BIDI
34#ifndef DEBUG_BIDI
35enum { BidiDebugEnabled = false };
36#define BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug if (1) ; else qDebugQMessageLogger(nullptr, 0, nullptr).debug
37#else
38enum { BidiDebugEnabled = true };
39static const char *directions[] = {
40 "DirL", "DirR", "DirEN", "DirES", "DirET", "DirAN", "DirCS", "DirB", "DirS", "DirWS", "DirON",
41 "DirLRE", "DirLRO", "DirAL", "DirRLE", "DirRLO", "DirPDF", "DirNSM", "DirBN",
42 "DirLRI", "DirRLI", "DirFSI", "DirPDI"
43};
44#define BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug qDebugQMessageLogger(nullptr, 0, nullptr).debug
45QDebug operator<<(QDebug d, QChar::Direction dir) {
46 return (d << directions[dir]);
47}
48#endif
49
50struct QBidiAlgorithm {
51 template<typename T> using Vector = QVarLengthArray<T, 64>;
52
53 QBidiAlgorithm(const QChar *text, BidiAnalysis *analysis, int length, bool baseDirectionIsRtl)
54 : text(text),
55 analysis(analysis),
56 length(length),
57 baseLevel(baseDirectionIsRtl ? 1 : 0)
58 {
59
60 }
61
62 struct IsolatePair {
63 int start;
64 int end;
65 };
66
67 void initScriptAnalysisAndIsolatePairs(Vector<IsolatePair> &isolatePairs)
68 {
69 Vector<int> isolateStack;
70 // load directions of string, and determine isolate pairs
71 for (int i = 0; i < length; ++i) {
72 int pos = i;
73 char32_t uc = text[i].unicode();
74 if (QChar::isHighSurrogate(uc) && i < length - 1 && text[i + 1].isLowSurrogate()) {
75 ++i;
76 analysis[i].bidiDirection = QChar::DirNSM;
77 uc = QChar::surrogateToUcs4(ushort(uc), text[i].unicode());
78 }
79 const auto direction = QChar::direction(uc);
80 analysis[pos].bidiDirection = direction;
81 switch (direction) {
82 case QChar::DirON:
83 // all mirrored chars are DirON
84 if (QChar::mirroredChar(uc) != uc)
85 analysis[pos].bidiFlags = BidiAnalysis::BidiMirrored;
86 break;
87 case QChar::DirLRE:
88 case QChar::DirRLE:
89 case QChar::DirLRO:
90 case QChar::DirRLO:
91 case QChar::DirPDF:
92 case QChar::DirBN:
93 analysis[pos].bidiFlags = BidiAnalysis::BidiMaybeResetToParagraphLevel|BidiAnalysis::BidiBN;
94 break;
95 case QChar::DirLRI:
96 case QChar::DirRLI:
97 case QChar::DirFSI:
98 isolateStack.append(isolatePairs.size());
99 isolatePairs.append({ pos, length });
100 analysis[pos].bidiFlags = BidiAnalysis::BidiMaybeResetToParagraphLevel;
101 break;
102 case QChar::DirPDI:
103 if (!isolateStack.isEmpty()) {
104 isolatePairs[isolateStack.last()].end = pos;
105 isolateStack.removeLast();
106 }
107 Q_FALLTHROUGH()[[clang::fallthrough]];
108 case QChar::DirWS:
109 analysis[pos].bidiFlags = BidiAnalysis::BidiMaybeResetToParagraphLevel;
110 break;
111 case QChar::DirS:
112 case QChar::DirB:
113 analysis[pos].bidiFlags = BidiAnalysis::BidiResetToParagraphLevel;
114 if (uc == QChar::ParagraphSeparator) {
115 // close all open isolates as we start a new paragraph
116 while (!isolateStack.isEmpty()) {
117 isolatePairs[isolateStack.last()].end = pos;
118 isolateStack.removeLast();
119 }
120 }
121 break;
122 default:
123 break;
124 }
125 if (i != pos) {
126 analysis[i].bidiFlags = analysis[pos].bidiFlags;
127 if (analysis[pos].bidiFlags & BidiAnalysis::BidiBN)
128 analysis[i].bidiDirection = QChar::DirBN;
129 }
130 }
131 }
132
133 struct DirectionalRun {
134 int start;
135 int end;
136 int continuation;
137 ushort level;
138 bool isContinuation;
139 bool hasContent;
140 };
141
142 void generateDirectionalRuns(const Vector<IsolatePair> &isolatePairs, Vector<DirectionalRun> &runs)
143 {
144 struct DirectionalStack {
145 enum { MaxDepth = 125 };
146 struct Item {
147 ushort level;
148 bool isOverride;
149 bool isIsolate;
150 int runBeforeIsolate;
151 };
152 Item items[128];
153 int counter = 0;
154
155 void push(Item i) {
156 items[counter] = i;
157 ++counter;
158 }
159 void pop() {
160 --counter;
161 }
162 int depth() const {
163 return counter;
164 }
165 const Item &top() const {
166 return items[counter - 1];
167 }
168 } stack;
169 int overflowIsolateCount = 0;
170 int overflowEmbeddingCount = 0;
171 int validIsolateCount = 0;
172
173 ushort level = baseLevel;
174 bool override = false;
175 stack.push({ level, false, false, -1 });
176
177 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "resolving explicit levels";
178 int runStart = 0;
179 int continuationFrom = -1;
180 int lastRunWithContent = -1;
181 bool runHasContent = false;
182
183 auto appendRun = [&](int runEnd) {
184 if (runEnd < runStart)
185 return;
186 bool isContinuation = false;
187 if (continuationFrom != -1) {
188 runs[continuationFrom].continuation = runs.size();
189 isContinuation = true;
190 } else if (lastRunWithContent != -1 && level == runs.at(lastRunWithContent).level) {
191 runs[lastRunWithContent].continuation = runs.size();
192 isContinuation = true;
193 }
194 if (runHasContent)
195 lastRunWithContent = runs.size();
196 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " appending run start/end" << runStart << runEnd << "level" << level;
197 runs.append({ runStart, runEnd, -1, level, isContinuation, runHasContent });
198 runHasContent = false;
199 runStart = runEnd + 1;
200 continuationFrom = -1;
201 };
202
203 int isolatePairPosition = 0;
204
205 for (int i = 0; i < length; ++i) {
206 QChar::Direction dir = analysis[i].bidiDirection;
207
208
209 auto doEmbed = [&](bool isRtl, bool isOverride, bool isIsolate) {
210 if (isIsolate) {
211 if (override)
212 analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
213 runHasContent = true;
214 ++isolatePairPosition;
215 }
216 int runBeforeIsolate = runs.size();
217 ushort newLevel = isRtl ? ((stack.top().level + 1) | 1) : ((stack.top().level + 2) & ~1);
218 if (newLevel <= DirectionalStack::MaxDepth && !overflowEmbeddingCount && !overflowIsolateCount) {
219 if (isIsolate)
220 ++validIsolateCount;
221 else
222 runBeforeIsolate = -1;
223 appendRun(isIsolate ? i : i - 1);
224 if (isIsolate)
225 lastRunWithContent = -1;
226 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "pushing new item on stack: level" << (int)newLevel << "isOverride" << isOverride << "isIsolate" << isIsolate << runBeforeIsolate;
227 stack.push({ newLevel, isOverride, isIsolate, runBeforeIsolate });
228 override = isOverride;
229 level = newLevel;
230 } else {
231 if (isIsolate)
232 ++overflowIsolateCount;
233 else if (!overflowIsolateCount)
234 ++overflowEmbeddingCount;
235 }
236 if (!isIsolate) {
237 analysis[i].bidiDirection = QChar::DirBN;
238 }
239 };
240
241 switch (dir) {
242 case QChar::DirLRE:
243 doEmbed(false, false, false);
244 break;
245 case QChar::DirRLE:
246 doEmbed(true, false, false);
247 break;
248 case QChar::DirLRO:
249 doEmbed(false, true, false);
250 break;
251 case QChar::DirRLO:
252 doEmbed(true, true, false);
253 break;
254 case QChar::DirLRI:
255 doEmbed(false, false, true);
256 break;
257 case QChar::DirRLI:
258 doEmbed(true, false, true);
259 break;
260 case QChar::DirFSI: {
261 bool isRtl = false;
262 if (isolatePairPosition < isolatePairs.size()) {
263 const auto &pair = isolatePairs.at(isolatePairPosition);
264 Q_ASSERT(pair.start == i)static_cast<void>(false && (pair.start == i));
265 isRtl = QStringView(text + pair.start + 1, pair.end - pair.start - 1).isRightToLeft();
266 }
267 doEmbed(isRtl, false, true);
268 break;
269 }
270
271 case QChar::DirPDF:
272 analysis[i].bidiDirection = QChar::DirBN;
273 if (overflowIsolateCount) {
274 ; // do nothing
275 } else if (overflowEmbeddingCount) {
276 --overflowEmbeddingCount;
277 } else if (!stack.top().isIsolate && stack.depth() >= 2) {
278 appendRun(i);
279 stack.pop();
280 override = stack.top().isOverride;
281 level = stack.top().level;
282 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "popped PDF from stack, level now" << (int)stack.top().level;
283 }
284 break;
285 case QChar::DirPDI:
286 if (overflowIsolateCount) {
287 --overflowIsolateCount;
288 } else if (validIsolateCount == 0) {
289 ; // do nothing
290 } else {
291 appendRun(i - 1);
292 overflowEmbeddingCount = 0;
293 while (!stack.top().isIsolate)
294 stack.pop();
295 continuationFrom = stack.top().runBeforeIsolate;
296 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "popped PDI from stack, level now" << (int)stack.top().level << "continuation from" << continuationFrom;
297 stack.pop();
298 override = stack.top().isOverride;
299 level = stack.top().level;
300 lastRunWithContent = -1;
301 --validIsolateCount;
302 }
303 runHasContent = true;
304 if (override)
305 analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
306 break;
307 case QChar::DirB:
308 // paragraph separator, go down to base direction, reset all state
309 if (text[i].unicode() == QChar::ParagraphSeparator) {
310 appendRun(i - 1);
311 while (stack.counter > 1) {
312 // there might be remaining isolates on the stack that are missing a PDI. Those need to get
313 // a continuation indicating to take the eos from the end of the string (ie. the paragraph level)
314 const auto &t = stack.top();
315 if (t.isIsolate) {
316 runs[t.runBeforeIsolate].continuation = -2;
317 }
318 --stack.counter;
319 }
320 continuationFrom = -1;
321 lastRunWithContent = -1;
322 validIsolateCount = 0;
323 overflowIsolateCount = 0;
324 overflowEmbeddingCount = 0;
325 level = baseLevel;
326 }
327 break;
328 default:
329 runHasContent = true;
330 if (override)
331 analysis[i].bidiDirection = (level & 1) ? QChar::DirR : QChar::DirL;
332 break;
333 case QChar::DirBN:
334 break;
335 }
336 }
337 appendRun(length - 1);
338 while (stack.counter > 1) {
339 // there might be remaining isolates on the stack that are missing a PDI. Those need to get
340 // a continuation indicating to take the eos from the end of the string (ie. the paragraph level)
341 const auto &t = stack.top();
342 if (t.isIsolate) {
343 runs[t.runBeforeIsolate].continuation = -2;
344 }
345 --stack.counter;
346 }
347 }
348
349 void resolveExplicitLevels(Vector<DirectionalRun> &runs)
350 {
351 Vector<IsolatePair> isolatePairs;
352
353 initScriptAnalysisAndIsolatePairs(isolatePairs);
354 generateDirectionalRuns(isolatePairs, runs);
355 }
356
357 struct IsolatedRunSequenceIterator {
358 struct Position {
359 int current = -1;
360 int pos = -1;
361
362 Position() = default;
363 Position(int current, int pos) : current(current), pos(pos) {}
364
365 bool isValid() const { return pos != -1; }
366 void clear() { pos = -1; }
367 };
368 IsolatedRunSequenceIterator(const Vector<DirectionalRun> &runs, int i)
369 : runs(runs),
370 current(i)
371 {
372 pos = runs.at(current).start;
373 }
374 int operator *() const { return pos; }
375 bool atEnd() const { return pos < 0; }
376 void operator++() {
377 ++pos;
378 if (pos > runs.at(current).end) {
379 current = runs.at(current).continuation;
380 if (current > -1)
381 pos = runs.at(current).start;
382 else
383 pos = -1;
384 }
385 }
386 void setPosition(Position p) {
387 current = p.current;
388 pos = p.pos;
389 }
390 Position position() const {
391 return Position(current, pos);
392 }
393 bool operator !=(int position) const {
394 return pos != position;
395 }
396
397 const Vector<DirectionalRun> &runs;
398 int current;
399 int pos;
400 };
401
402
403 void resolveW1W2W3(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
404 {
405 QChar::Direction last = sos;
406 QChar::Direction lastStrong = sos;
407 IsolatedRunSequenceIterator it(runs, i);
408 while (!it.atEnd()) {
409 int pos = *it;
410
411 // Rule W1: Resolve NSM
412 QChar::Direction current = analysis[pos].bidiDirection;
413 if (current == QChar::DirNSM) {
414 current = last;
415 analysis[pos].bidiDirection = current;
416 } else if (current >= QChar::DirLRI) {
417 last = QChar::DirON;
418 } else if (current == QChar::DirBN) {
419 current = last;
420 } else {
421 // there shouldn't be any explicit embedding marks here
422 Q_ASSERT(current != QChar::DirLRE)static_cast<void>(false && (current != QChar::DirLRE
));
423 Q_ASSERT(current != QChar::DirRLE)static_cast<void>(false && (current != QChar::DirRLE
));
424 Q_ASSERT(current != QChar::DirLRO)static_cast<void>(false && (current != QChar::DirLRO
));
425 Q_ASSERT(current != QChar::DirRLO)static_cast<void>(false && (current != QChar::DirRLO
));
426 Q_ASSERT(current != QChar::DirPDF)static_cast<void>(false && (current != QChar::DirPDF
));
427
428 last = current;
Value stored to 'last' is never read
429 }
430
431 // Rule W2
432 if (current == QChar::DirEN && lastStrong == QChar::DirAL) {
433 current = QChar::DirAN;
434 analysis[pos].bidiDirection = current;
435 }
436
437 // remember last strong char for rule W2
438 if (current == QChar::DirL || current == QChar::DirR) {
439 lastStrong = current;
440 } else if (current == QChar::DirAL) {
441 // Rule W3
442 lastStrong = current;
443 analysis[pos].bidiDirection = QChar::DirR;
444 }
445 last = current;
446 ++it;
447 }
448 }
449
450
451 void resolveW4(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
452 {
453 // Rule W4
454 QChar::Direction secondLast = sos;
455
456 IsolatedRunSequenceIterator it(runs, i);
457 int lastPos = *it;
458 QChar::Direction last = analysis[lastPos].bidiDirection;
459
460// BIDI_DEBUG() << "Applying rule W4/W5";
461 ++it;
462 while (!it.atEnd()) {
463 int pos = *it;
464 QChar::Direction current = analysis[pos].bidiDirection;
465 if (current == QChar::DirBN) {
466 ++it;
467 continue;
468 }
469// BIDI_DEBUG() << pos << secondLast << last << current;
470 if (last == QChar::DirES && current == QChar::DirEN && secondLast == QChar::DirEN) {
471 last = QChar::DirEN;
472 analysis[lastPos].bidiDirection = last;
473 } else if (last == QChar::DirCS) {
474 if (current == QChar::DirEN && secondLast == QChar::DirEN) {
475 last = QChar::DirEN;
476 analysis[lastPos].bidiDirection = last;
477 } else if (current == QChar::DirAN && secondLast == QChar::DirAN) {
478 last = QChar::DirAN;
479 analysis[lastPos].bidiDirection = last;
480 }
481 }
482 secondLast = last;
483 last = current;
484 lastPos = pos;
485 ++it;
486 }
487 }
488
489 void resolveW5(const Vector<DirectionalRun> &runs, int i)
490 {
491 // Rule W5
492 IsolatedRunSequenceIterator::Position lastETPosition;
493
494 IsolatedRunSequenceIterator it(runs, i);
495 int lastPos = *it;
496 QChar::Direction last = analysis[lastPos].bidiDirection;
497 if (last == QChar::DirET || last == QChar::DirBN)
498 lastETPosition = it.position();
499
500 ++it;
501 while (!it.atEnd()) {
502 int pos = *it;
503 QChar::Direction current = analysis[pos].bidiDirection;
504 if (current == QChar::DirBN) {
505 ++it;
506 continue;
507 }
508 if (current == QChar::DirET) {
509 if (last == QChar::DirEN) {
510 current = QChar::DirEN;
511 analysis[pos].bidiDirection = current;
512 } else if (!lastETPosition.isValid()) {
513 lastETPosition = it.position();
514 }
515 } else if (lastETPosition.isValid()) {
516 if (current == QChar::DirEN) {
517 it.setPosition(lastETPosition);
518 while (it != pos) {
519 int pos = *it;
520 analysis[pos].bidiDirection = QChar::DirEN;
521 ++it;
522 }
523 }
524 lastETPosition.clear();
525 }
526 last = current;
527 lastPos = pos;
528 ++it;
529 }
530 }
531
532 void resolveW6W7(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
533 {
534 QChar::Direction lastStrong = sos;
535 IsolatedRunSequenceIterator it(runs, i);
536 while (!it.atEnd()) {
537 int pos = *it;
538
539 // Rule W6
540 QChar::Direction current = analysis[pos].bidiDirection;
541 if (current == QChar::DirBN) {
542 ++it;
543 continue;
544 }
545 if (current == QChar::DirET || current == QChar::DirES || current == QChar::DirCS) {
546 analysis[pos].bidiDirection = QChar::DirON;
547 }
548
549 // Rule W7
550 else if (current == QChar::DirL || current == QChar::DirR) {
551 lastStrong = current;
552 } else if (current == QChar::DirEN && lastStrong == QChar::DirL) {
553 analysis[pos].bidiDirection = lastStrong;
554 }
555 ++it;
556 }
557 }
558
559 struct BracketPair {
560 int first;
561 int second;
562
563 bool isValid() const { return second > 0; }
564
565 QChar::Direction containedDirection(IsolatedRunSequenceIterator it, const BidiAnalysis *analysis,
566 QChar::Direction embeddingDir) const {
567 QChar::Direction containedDir = QChar::DirON;
568 ++it;
569 while (!it.atEnd() && *it < second) {
570 QChar::Direction dir = analysis[*it].bidiDirection;
571 if (dir == QChar::DirL) {
572 containedDir = dir;
573 if (embeddingDir == dir)
574 break;
575 } else if (dir == QChar::DirR || dir == QChar::DirAN || dir == QChar::DirEN) {
576 containedDir = QChar::DirR;
577 if (embeddingDir == QChar::DirR)
578 break;
579 }
580 ++it;
581 }
582 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " contained dir for backet pair" << first << "/" << second << "is" << containedDir;
583 return containedDir;
584 }
585 };
586
587
588 struct BracketStack {
589 struct Item {
590 Item() = default;
591 Item(uint pairedBracked, int position) : pairedBracked(pairedBracked), position(position) {}
592 uint pairedBracked = 0;
593 int position = 0;
594 };
595
596 void push(uint closingUnicode, int pos) {
597 if (position < MaxDepth)
598 stack[position] = Item(closingUnicode, pos);
599 ++position;
600 }
601 int match(uint unicode) {
602 Q_ASSERT(!overflowed())static_cast<void>(false && (!overflowed()));
603 int p = position;
604 while (--p >= 0) {
605 if (stack[p].pairedBracked == unicode) {
606 position = p;
607 return stack[p].position;
608 }
609
610 }
611 return -1;
612 }
613
614 enum { MaxDepth = 63 };
615 Item stack[MaxDepth];
616 int position = 0;
617
618 bool overflowed() const { return position > MaxDepth; }
619 };
620
621 void resolveN0(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos)
622 {
623 const int runIndex = i;
624 ushort level = runs.at(i).level;
625
626 Vector<BracketPair> bracketPairs;
627 {
628 BracketStack bracketStack;
629 IsolatedRunSequenceIterator it(runs, i);
630 while (!it.atEnd()) {
631 int pos = *it;
632 QChar::Direction dir = analysis[pos].bidiDirection;
633 if (dir == QChar::DirON) {
634 const char32_t scalar = text[pos].unicode();
635 const auto category = QChar::category(scalar);
636 const char32_t mirrored = QChar::mirroredChar(scalar);
637 if (scalar != mirrored) {
638 // either opening or closing bracket
639 if (category == QChar::Punctuation_Open
640 && QChar::category(mirrored) == QChar::Punctuation_Close) {
641 // opening bracked
642 uint closingBracked = canonicalBracket(mirrored);
643 bracketStack.push(closingBracked, bracketPairs.size());
644 if (bracketStack.overflowed()) {
645 bracketPairs.clear();
646 break;
647 }
648 bracketPairs.append({ pos, -1 });
649 } else if (category == QChar::Punctuation_Close
650 && QChar::category(mirrored) == QChar::Punctuation_Open) {
651 int pairPos = bracketStack.match(canonicalBracket(scalar));
652 if (pairPos != -1)
653 bracketPairs[pairPos].second = pos;
654 }
655 }
656 }
657 ++it;
658 }
659 }
660
661 if (BidiDebugEnabled && bracketPairs.size()) {
662 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "matched bracket pairs:";
663 for (int i = 0; i < bracketPairs.size(); ++i)
664 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " " << bracketPairs.at(i).first << bracketPairs.at(i).second;
665 }
666
667 QChar::Direction lastStrong = sos;
668 IsolatedRunSequenceIterator it(runs, i);
669 QChar::Direction embeddingDir = (level & 1) ? QChar::DirR : QChar::DirL;
670 IsolatedRunSequenceIterator opening(runs, runIndex);
671 for (int i = 0; i < bracketPairs.size(); ++i) {
672 const auto &pair = bracketPairs.at(i);
673 if (!pair.isValid())
674 continue;
675 // N0 considers only this isolating run sequence, not embedded/isolate contents.
676 while (!opening.atEnd() && *opening != pair.first) ++opening;
677 QChar::Direction containedDir = pair.containedDirection(opening, analysis, embeddingDir);
678 if (containedDir == QChar::DirON) {
679 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " 3: resolve bracket pair" << i << "to DirON";
680 continue;
681 } else if (containedDir == embeddingDir) {
682 analysis[pair.first].bidiDirection = embeddingDir;
683 analysis[pair.second].bidiDirection = embeddingDir;
684 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " 1: resolve bracket pair" << i << "to" << embeddingDir;
685 } else {
686 // case c.
687 while (it.pos < pair.first) {
688 int pos = *it;
689 switch (analysis[pos].bidiDirection) {
690 case QChar::DirR:
691 case QChar::DirEN:
692 case QChar::DirAN:
693 lastStrong = QChar::DirR;
694 break;
695 case QChar::DirL:
696 lastStrong = QChar::DirL;
697 break;
698 default:
699 break;
700 }
701 ++it;
702 }
703 analysis[pair.first].bidiDirection = lastStrong;
704 analysis[pair.second].bidiDirection = lastStrong;
705 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " 2: resolve bracket pair" << i << "to" << lastStrong;
706 }
707 // N0 applies to original NSMs after either bracket, ignoring X9 removals.
708 for (int bracket : {pair.first, pair.second}) {
709 auto trailing = opening;
710 while (!trailing.atEnd() && *trailing != bracket) ++trailing;
711 if (trailing.atEnd()) continue;
712 ++trailing;
713 while (!trailing.atEnd()) {
714 const int pos = *trailing;
715 if (analysis[pos].bidiFlags & BidiAnalysis::BidiBN) {
716 ++trailing;
717 continue;
718 }
719 if (originalDirection(pos) != QChar::DirNSM) break;
720 analysis[pos].bidiDirection = analysis[bracket].bidiDirection;
721 ++trailing;
722 }
723 }
724 }
725 }
726
727 void resolveN1N2(const Vector<DirectionalRun> &runs, int i, QChar::Direction sos, QChar::Direction eos)
728 {
729 // Rule N1 & N2
730 QChar::Direction lastStrong = sos;
731 IsolatedRunSequenceIterator::Position niPos;
732 IsolatedRunSequenceIterator it(runs, i);
733// QChar::Direction last = QChar::DirON;
734 while (1) {
735 int pos = *it;
736
737 QChar::Direction current = pos >= 0 ? analysis[pos].bidiDirection : eos;
738 QChar::Direction currentStrong = current;
739 switch (current) {
740 case QChar::DirEN:
741 case QChar::DirAN:
742 currentStrong = QChar::DirR;
743 Q_FALLTHROUGH()[[clang::fallthrough]];
744 case QChar::DirL:
745 case QChar::DirR:
746 if (niPos.isValid()) {
747 QChar::Direction dir = currentStrong;
748 if (lastStrong != currentStrong)
749 dir = (runs.at(i).level) & 1 ? QChar::DirR : QChar::DirL;
750 it.setPosition(niPos);
751 while (*it != pos) {
752 if (analysis[*it].bidiDirection != QChar::DirBN)
753 analysis[*it].bidiDirection = dir;
754 ++it;
755 }
756 niPos.clear();
757 }
758 lastStrong = currentStrong;
759 break;
760
761 case QChar::DirBN:
762 case QChar::DirS:
763 case QChar::DirWS:
764 case QChar::DirON:
765 case QChar::DirFSI:
766 case QChar::DirLRI:
767 case QChar::DirRLI:
768 case QChar::DirPDI:
769 case QChar::DirB:
770 if (!niPos.isValid())
771 niPos = it.position();
772 break;
773
774 default:
775 Q_UNREACHABLE()do { static_cast<void>(false && (false)); __builtin_unreachable
(); } while (false);
776 }
777 if (it.atEnd())
778 break;
779// last = current;
780 ++it;
781 }
782 }
783
784 void resolveImplicitLevelsForIsolatedRun(const Vector<DirectionalRun> &runs, int i)
785 {
786 // Rule X10
787 int level = runs.at(i).level;
788 int before = i - 1;
789 while (before >= 0 && !runs.at(before).hasContent)
790 --before;
791 int level_before = (before >= 0) ? runs.at(before).level : baseLevel;
792 int after = i;
793 while (runs.at(after).continuation >= 0)
794 after = runs.at(after).continuation;
795 if (runs.at(after).continuation == -2) {
796 after = runs.size();
797 } else {
798 ++after;
799 while (after < runs.size() && !runs.at(after).hasContent)
800 ++after;
801 }
802 int level_after = (after == runs.size()) ? baseLevel : runs.at(after).level;
803 QChar::Direction sos = (qMax(level_before, level) & 1) ? QChar::DirR : QChar::DirL;
804 QChar::Direction eos = (qMax(level_after, level) & 1) ? QChar::DirR : QChar::DirL;
805
806 if (BidiDebugEnabled) {
807 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "Isolated run starting at" << i << "sos/eos" << sos << eos;
808 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "before implicit level processing:";
809 IsolatedRunSequenceIterator it(runs, i);
810 while (!it.atEnd()) {
811 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " " << *it << Qt::hex << text[*it].unicode() << analysis[*it].bidiDirection;
812 ++it;
813 }
814 }
815
816 resolveW1W2W3(runs, i, sos);
817 resolveW4(runs, i, sos);
818 resolveW5(runs, i);
819
820 if (BidiDebugEnabled) {
821 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "after W4/W5";
822 IsolatedRunSequenceIterator it(runs, i);
823 while (!it.atEnd()) {
824 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " " << *it << Qt::hex << text[*it].unicode() << analysis[*it].bidiDirection;
825 ++it;
826 }
827 }
828
829 resolveW6W7(runs, i, sos);
830
831 // Resolve neutral types
832
833 // Rule N0
834 resolveN0(runs, i, sos);
835 resolveN1N2(runs, i, sos, eos);
836
837 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "setting levels (run at" << level << ")";
838 // Rules I1 & I2: set correct levels
839 {
840 ushort level = runs.at(i).level;
841 IsolatedRunSequenceIterator it(runs, i);
842 while (!it.atEnd()) {
843 int pos = *it;
844
845 QChar::Direction current = analysis[pos].bidiDirection;
846 switch (current) {
847 case QChar::DirBN:
848 break;
849 case QChar::DirL:
850 analysis[pos].bidiLevel = (level + 1) & ~1;
851 break;
852 case QChar::DirR:
853 analysis[pos].bidiLevel = level | 1;
854 break;
855 case QChar::DirAN:
856 case QChar::DirEN:
857 analysis[pos].bidiLevel = (level + 2) & ~1;
858 break;
859 default:
860 Q_UNREACHABLE()do { static_cast<void>(false && (false)); __builtin_unreachable
(); } while (false);
861 }
862 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " " << pos << current << analysis[pos].bidiLevel;
863 ++it;
864 }
865 }
866 }
867
868 void resolveImplicitLevels(const Vector<DirectionalRun> &runs)
869 {
870 for (int i = 0; i < runs.size(); ++i) {
871 if (runs.at(i).isContinuation)
872 continue;
873
874 resolveImplicitLevelsForIsolatedRun(runs, i);
875 }
876 }
877
878 bool checkForBidi() const
879 {
880 if (baseLevel != 0)
881 return true;
882 for (int i = 0; i < length; ++i) {
883 if (text[i].unicode() >= 0x590) {
884 switch (originalDirection(i)) {
885 case QChar::DirR: case QChar::DirAN:
886 case QChar::DirLRE: case QChar::DirLRO: case QChar::DirAL:
887 case QChar::DirRLE: case QChar::DirRLO: case QChar::DirPDF:
888 case QChar::DirLRI: case QChar::DirRLI: case QChar::DirFSI: case QChar::DirPDI:
889 return true;
890 default:
891 break;
892 }
893 }
894 }
895 return false;
896 }
897
898 QChar::Direction originalDirection(int position) const {
899 const QChar ch = text[position];
900 if (ch.isLowSurrogate() && position > 0 && text[position - 1].isHighSurrogate())
901 return QChar::DirNSM;
902 char32_t scalar = ch.unicode();
903 if (ch.isHighSurrogate() && position + 1 < length && text[position + 1].isLowSurrogate())
904 scalar = QChar::surrogateToUcs4(ch, text[position + 1]);
905 return QChar::direction(scalar);
906 }
907
908 static uint canonicalBracket(char32_t scalar) {
909 const auto normalized = QString::fromUcs4(&scalar, 1)
910 .normalized(QString::NormalizationForm_D).toUcs4();
911 Q_ASSERT(normalized.size() == 1)static_cast<void>(false && (normalized.size() ==
1));
912 return normalized.front();
913 }
914
915 bool process(std::vector<int> *shapingLevels = nullptr)
916 {
917 memset(analysis, 0, length * sizeof(BidiAnalysis));
918
919 bool hasBidi = checkForBidi();
920
921 if (!hasBidi) {
922 if (shapingLevels) {
923 shapingLevels->assign(length, 0);
924 for (int i = 0; i < length; ++i) {
925 // The fast path skips script analysis. Preserve X9 status
926 // even for paragraphs containing only LTR text and BN.
927 const auto direction = originalDirection(i);
928 if (direction == QChar::DirBN)
929 (*shapingLevels)[i] = -1;
930 else if (i > 0 && text[i].isLowSurrogate() && text[i - 1].isHighSurrogate())
931 (*shapingLevels)[i] = (*shapingLevels)[i - 1];
932 }
933 }
934 return false;
935 }
936
937 if (BidiDebugEnabled) {
938 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << ">>>> start bidi, text length" << length;
939 for (int i = 0; i < length; ++i)
940 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << Qt::hex << " (" << i << ")" << text[i].unicode() << text[i].direction();
941 }
942
943 {
944 Vector<DirectionalRun> runs;
945 resolveExplicitLevels(runs);
946
947 if (BidiDebugEnabled) {
948 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "resolved explicit levels, nruns" << runs.size();
949 for (int i = 0; i < runs.size(); ++i)
950 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " " << i << "start/end" << runs.at(i).start << runs.at(i).end << "level" << (int)runs.at(i).level << "continuation" << runs.at(i).continuation;
951 }
952
953 // now we have a list of isolated run sequences inside the vector of runs, that can be fed
954 // through the implicit level resolving
955
956 resolveImplicitLevels(runs);
957 }
958
959 if (shapingLevels) {
960 shapingLevels->reserve(length);
961 for (int i = 0; i < length; ++i) {
962 shapingLevels->push_back(analysis[i].bidiFlags & BidiAnalysis::BidiBN
963 ? -1 : analysis[i].bidiLevel);
964 }
965 }
966
967 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "Rule L1:";
968 // Rule L1:
969 bool resetLevel = true;
970 for (int i = length - 1; i >= 0; --i) {
971 if (analysis[i].bidiFlags & BidiAnalysis::BidiResetToParagraphLevel) {
972 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "resetting pos" << i << "to baselevel";
973 analysis[i].bidiLevel = baseLevel;
974 resetLevel = true;
975 } else if (resetLevel && analysis[i].bidiFlags & BidiAnalysis::BidiMaybeResetToParagraphLevel) {
976 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "resetting pos" << i << "to baselevel (maybereset flag)";
977 analysis[i].bidiLevel = baseLevel;
978 } else {
979 resetLevel = false;
980 }
981 }
982
983 // set directions for BN to the minimum of adjacent chars
984 // This makes is possible to be conformant with the Bidi algorithm even though we don't
985 // remove BN and explicit embedding chars from the stream of characters to reorder
986 int lastLevel = baseLevel;
987 int lastBNPos = -1;
988 for (int i = 0; i < length; ++i) {
989 if (analysis[i].bidiFlags & BidiAnalysis::BidiBN) {
990 if (lastBNPos < 0)
991 lastBNPos = i;
992 analysis[i].bidiLevel = lastLevel;
993 } else {
994 int l = analysis[i].bidiLevel;
995 if (lastBNPos >= 0) {
996 if (l < lastLevel) {
997 while (lastBNPos < i) {
998 analysis[lastBNPos].bidiLevel = l;
999 ++lastBNPos;
1000 }
1001 }
1002 lastBNPos = -1;
1003 }
1004 lastLevel = l;
1005 }
1006 }
1007 if (lastBNPos >= 0 && baseLevel < lastLevel) {
1008 while (lastBNPos < length) {
1009 analysis[lastBNPos].bidiLevel = baseLevel;
1010 ++lastBNPos;
1011 }
1012 }
1013
1014 if (BidiDebugEnabled) {
1015 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << "final resolved levels:";
1016 for (int i = 0; i < length; ++i)
1017 BIDI_DEBUGif (1) ; else QMessageLogger(nullptr, 0, nullptr).debug() << " " << i << Qt::hex << text[i].unicode() << Qt::dec << (int)analysis[i].bidiLevel;
1018 }
1019
1020 return true;
1021 }
1022
1023
1024 const QChar *text;
1025 BidiAnalysis *analysis;
1026 int length;
1027 char baseLevel;
1028};
1029
1030
1031} // namespace
1032
1033namespace {
1034Paragraph resolveParagraph(const QString &text, Qt::LayoutDirection direction,
1035 std::vector<int> *shapingLevels) {
1036 if (text.size() > std::numeric_limits<int>::max())
1037 throw std::length_error("Bidi text exceeds index range");
1038 Paragraph result;
1039 result.base = direction == Qt::RightToLeft
1040 || (direction == Qt::LayoutDirectionAuto && text.isRightToLeft());
1041 if (text.isEmpty()) return result;
1042 std::vector<BidiAnalysis> analysis(text.size());
1043 QBidiAlgorithm algorithm(text.constData(), analysis.data(), text.size(), result.base != 0);
1044 algorithm.process(shapingLevels);
1045 result.levels.reserve(analysis.size());
1046 for (const auto &item : analysis) result.levels.push_back(item.bidiLevel);
1047 return result;
1048}
1049} // namespace
1050
1051Paragraph resolve(const QString &text, Qt::LayoutDirection direction) {
1052 return resolveParagraph(text, direction, nullptr);
1053}
1054
1055ShapingParagraph resolveForShaping(const QString &text, Qt::LayoutDirection direction) {
1056 ShapingParagraph result;
1057 result.display = resolveParagraph(text, direction, &result.shapingLevels);
1058 result.isolateBoundaries.assign(text.size(), false);
1059 for (int i = 0; i < text.size(); ++i) {
1060 const auto direction = text.at(i).direction();
1061 result.isolateBoundaries[i] = direction == QChar::DirLRI
1062 || direction == QChar::DirRLI || direction == QChar::DirFSI
1063 || direction == QChar::DirPDI;
1064 }
1065 return result;
1066}
1067
1068std::vector<int> reorder(const std::vector<quint8> &levels) {
1069 if (levels.size() > size_t(std::numeric_limits<int>::max()))
1070 throw std::length_error("Bidi levels exceed index range");
1071 std::vector<int> order(levels.size());
1072 std::iota(order.begin(), order.end(), 0);
1073 if (levels.empty()) return order;
1074 const auto bounds = std::minmax_element(levels.begin(), levels.end());
1075 const int lowestOdd = *bounds.first | 1;
1076 for (int level = *bounds.second; level >= lowestOdd; --level) {
1077 for (size_t begin = 0; begin < levels.size();) {
1078 if (levels[begin] < level) { ++begin; continue; }
1079 size_t end = begin + 1;
1080 while (end < levels.size() && levels[end] >= level) ++end;
1081 std::reverse(order.begin() + begin, order.begin() + end);
1082 begin = end;
1083 }
1084 }
1085 return order;
1086}
1087
1088} // namespace lc::qtbidi