Revert "Speed up QTextEngine::resolveAdditionalFormats"
[qt:qt.git] / src / gui / text / qtextengine.cpp
1 /****************************************************************************
2 **
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
5 **
6 ** This file is part of the QtGui module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** GNU Lesser General Public License Usage
10 ** This file may be used under the terms of the GNU Lesser General Public
11 ** License version 2.1 as published by the Free Software Foundation and
12 ** appearing in the file LICENSE.LGPL included in the packaging of this
13 ** file. Please review the following information to ensure the GNU Lesser
14 ** General Public License version 2.1 requirements will be met:
15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
16 **
17 ** In addition, as a special exception, Nokia gives you certain additional
18 ** rights. These rights are described in the Nokia Qt LGPL Exception
19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
20 **
21 ** GNU General Public License Usage
22 ** Alternatively, this file may be used under the terms of the GNU General
23 ** Public License version 3.0 as published by the Free Software Foundation
24 ** and appearing in the file LICENSE.GPL included in the packaging of this
25 ** file. Please review the following information to ensure the GNU General
26 ** Public License version 3.0 requirements will be met:
27 ** http://www.gnu.org/copyleft/gpl.html.
28 **
29 ** Other Usage
30 ** Alternatively, this file may be used in accordance with the terms and
31 ** conditions contained in a signed written agreement between you and Nokia.
32 **
33 **
34 **
35 **
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41
42 #include "qdebug.h"
43 #include "qtextformat.h"
44 #include "qtextformat_p.h"
45 #include "qtextengine_p.h"
46 #include "qabstracttextdocumentlayout.h"
47 #include "qtextlayout.h"
48 #include "qtextboundaryfinder.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 <private/qunicodetables_p.h>
55 #include "qtextdocument_p.h"
56 #include <qapplication.h>
57 #include <stdlib.h>
58
59
60 QT_BEGIN_NAMESPACE
61
62 namespace {
63 // Helper class used in QTextEngine::itemize
64 // keep it out here to allow us to keep supporting various compilers.
65 class Itemizer {
66 public:
67     Itemizer(const QString &string, const QScriptAnalysis *analysis, QScriptItemArray &items)
68         : m_string(string),
69         m_analysis(analysis),
70         m_items(items),
71         m_splitter(0)
72     {
73     }
74     ~Itemizer()
75     {
76         delete m_splitter;
77     }
78
79     /// generate the script items
80     /// The caps parameter is used to choose the algoritm of splitting text and assiging roles to the textitems
81     void generate(int start, int length, QFont::Capitalization caps)
82     {
83         if ((int)caps == (int)QFont::SmallCaps)
84             generateScriptItemsSmallCaps(reinterpret_cast<const ushort *>(m_string.unicode()), start, length);
85         else if(caps == QFont::Capitalize)
86             generateScriptItemsCapitalize(start, length);
87         else if(caps != QFont::MixedCase) {
88             generateScriptItemsAndChangeCase(start, length,
89                 caps == QFont::AllLowercase ? QScriptAnalysis::Lowercase : QScriptAnalysis::Uppercase);
90         }
91         else
92             generateScriptItems(start, length);
93     }
94
95 private:
96     enum { MaxItemLength = 4096 };
97
98     void generateScriptItemsAndChangeCase(int start, int length, QScriptAnalysis::Flags flags)
99     {
100         generateScriptItems(start, length);
101         if (m_items.isEmpty()) // the next loop won't work in that case
102             return;
103         QScriptItemArray::Iterator iter = m_items.end();
104         do {
105             iter--;
106             if (iter->analysis.flags < QScriptAnalysis::TabOrObject)
107                 iter->analysis.flags = flags;
108         } while (iter->position > start);
109     }
110
111     void generateScriptItems(int start, int length)
112     {
113         if (!length)
114             return;
115         const int end = start + length;
116         for (int i = start + 1; i < end; ++i) {
117             // According to the unicode spec we should be treating characters in the Common script
118             // (punctuation, spaces, etc) as being the same script as the surrounding text for the
119             // purpose of splitting up text. This is important because, for example, a fullstop
120             // (0x2E) can be used to indicate an abbreviation and so must be treated as part of a
121             // word.  Thus it must be passed along with the word in languages that have to calculate
122             // word breaks.  For example the thai word "ครม." has no word breaks but the word "ครม"
123             // does.
124             // Unfortuntely because we split up the strings for both wordwrapping and for setting
125             // the font and because Japanese and Chinese are also aliases of the script "Common",
126             // doing this would break too many things.  So instead we only pass the full stop
127             // along, and nothing else.
128             if (m_analysis[i].bidiLevel == m_analysis[start].bidiLevel
129                 && m_analysis[i].flags == m_analysis[start].flags
130                 && (m_analysis[i].script == m_analysis[start].script || m_string[i] == QLatin1Char('.'))
131                 && m_analysis[i].flags < QScriptAnalysis::SpaceTabOrObject
132                 && i - start < MaxItemLength)
133                 continue;
134             m_items.append(QScriptItem(start, m_analysis[start]));
135             start = i;
136         }
137         m_items.append(QScriptItem(start, m_analysis[start]));
138     }
139
140     void generateScriptItemsCapitalize(int start, int length)
141     {
142         if (!length)
143             return;
144
145         if (!m_splitter)
146             m_splitter = new QTextBoundaryFinder(QTextBoundaryFinder::Word,
147                                                  m_string.constData(), m_string.length(),
148                                                  /*buffer*/0, /*buffer size*/0);
149
150         m_splitter->setPosition(start);
151         QScriptAnalysis itemAnalysis = m_analysis[start];
152
153         if (m_splitter->boundaryReasons() & QTextBoundaryFinder::StartWord) {
154             itemAnalysis.flags = QScriptAnalysis::Uppercase;
155             m_splitter->toNextBoundary();
156         }
157
158         const int end = start + length;
159         for (int i = start + 1; i < end; ++i) {
160
161             bool atWordBoundary = false;
162
163             if (i == m_splitter->position()) {
164                 if (m_splitter->boundaryReasons() & QTextBoundaryFinder::StartWord
165                     && m_analysis[i].flags < QScriptAnalysis::TabOrObject)
166                     atWordBoundary = true;
167
168                 m_splitter->toNextBoundary();
169             }
170
171             if (m_analysis[i] == itemAnalysis
172                 && m_analysis[i].flags < QScriptAnalysis::TabOrObject
173                 && !atWordBoundary
174                 && i - start < MaxItemLength)
175                 continue;
176
177             m_items.append(QScriptItem(start, itemAnalysis));
178             start = i;
179             itemAnalysis = m_analysis[start];
180
181             if (atWordBoundary)
182                 itemAnalysis.flags = QScriptAnalysis::Uppercase;
183         }
184         m_items.append(QScriptItem(start, itemAnalysis));
185     }
186
187     void generateScriptItemsSmallCaps(const ushort *uc, int start, int length)
188     {
189         if (!length)
190             return;
191         bool lower = (QChar::category(uc[start]) == QChar::Letter_Lowercase);
192         const int end = start + length;
193         // split text into parts that are already uppercase and parts that are lowercase, and mark the latter to be uppercased later.
194         for (int i = start + 1; i < end; ++i) {
195             bool l = (QChar::category(uc[i]) == QChar::Letter_Lowercase);
196             if ((m_analysis[i] == m_analysis[start])
197                 && m_analysis[i].flags < QScriptAnalysis::TabOrObject
198                 && l == lower
199                 && i - start < MaxItemLength)
200                 continue;
201             m_items.append(QScriptItem(start, m_analysis[start]));
202             if (lower)
203                 m_items.last().analysis.flags = QScriptAnalysis::SmallCaps;
204
205             start = i;
206             lower = l;
207         }
208         m_items.append(QScriptItem(start, m_analysis[start]));
209         if (lower)
210             m_items.last().analysis.flags = QScriptAnalysis::SmallCaps;
211     }
212
213     const QString &m_string;
214     const QScriptAnalysis * const m_analysis;
215     QScriptItemArray &m_items;
216     QTextBoundaryFinder *m_splitter;
217 };
218 }
219
220
221 // ----------------------------------------------------------------------------
222 //
223 // The BiDi algorithm
224 //
225 // ----------------------------------------------------------------------------
226
227 #define BIDI_DEBUG 0
228 #if (BIDI_DEBUG >= 1)
229 QT_BEGIN_INCLUDE_NAMESPACE
230 #include <iostream>
231 QT_END_INCLUDE_NAMESPACE
232 using namespace std;
233
234 static const char *directions[] = {
235     "DirL", "DirR", "DirEN", "DirES", "DirET", "DirAN", "DirCS", "DirB", "DirS", "DirWS", "DirON",
236     "DirLRE", "DirLRO", "DirAL", "DirRLE", "DirRLO", "DirPDF", "DirNSM", "DirBN"
237 };
238
239 #endif
240
241 struct QBidiStatus {
242     QBidiStatus() {
243         eor = QChar::DirON;
244         lastStrong = QChar::DirON;
245         last = QChar:: DirON;
246         dir = QChar::DirON;
247     }
248     QChar::Direction eor;
249     QChar::Direction lastStrong;
250     QChar::Direction last;
251     QChar::Direction dir;
252 };
253
254 enum { MaxBidiLevel = 61 };
255
256 struct QBidiControl {
257     inline QBidiControl(bool rtl)
258         : cCtx(0), base(rtl ? 1 : 0), level(rtl ? 1 : 0), override(false) {}
259
260     inline void embed(bool rtl, bool o = false) {
261         unsigned int toAdd = 1;
262         if((level%2 != 0) == rtl ) {
263             ++toAdd;
264         }
265         if (level + toAdd <= MaxBidiLevel) {
266             ctx[cCtx].level = level;
267             ctx[cCtx].override = override;
268             cCtx++;
269             override = o;
270             level += toAdd;
271         }
272     }
273     inline bool canPop() const { return cCtx != 0; }
274     inline void pdf() {
275         Q_ASSERT(cCtx);
276         --cCtx;
277         level = ctx[cCtx].level;
278         override = ctx[cCtx].override;
279     }
280
281     inline QChar::Direction basicDirection() const {
282         return (base ? QChar::DirR : QChar:: DirL);
283     }
284     inline unsigned int baseLevel() const {
285         return base;
286     }
287     inline QChar::Direction direction() const {
288         return ((level%2) ? QChar::DirR : QChar:: DirL);
289     }
290
291     struct {
292         unsigned int level;
293         bool override;
294     } ctx[MaxBidiLevel];
295     unsigned int cCtx;
296     const unsigned int base;
297     unsigned int level;
298     bool override;
299 };
300
301
302 static void appendItems(QScriptAnalysis *analysis, int &start, int &stop, const QBidiControl &control, QChar::Direction dir)
303 {
304     if (start > stop)
305         return;
306
307     int level = control.level;
308
309     if(dir != QChar::DirON && !control.override) {
310         // add level of run (cases I1 & I2)
311         if(level % 2) {
312             if(dir == QChar::DirL || dir == QChar::DirAN || dir == QChar::DirEN)
313                 level++;
314         } else {
315             if(dir == QChar::DirR)
316                 level++;
317             else if(dir == QChar::DirAN || dir == QChar::DirEN)
318                 level += 2;
319         }
320     }
321
322 #if (BIDI_DEBUG >= 1)
323     qDebug("new run: dir=%s from %d, to %d level = %d override=%d", directions[dir], start, stop, level, control.override);
324 #endif
325     QScriptAnalysis *s = analysis + start;
326     const QScriptAnalysis *e = analysis + stop;
327     while (s <= e) {
328         s->bidiLevel = level;
329         ++s;
330     }
331     ++stop;
332     start = stop;
333 }
334
335 static QChar::Direction skipBoundryNeutrals(QScriptAnalysis *analysis,
336                                             const ushort *unicode, int length,
337                                             int &sor, int &eor, QBidiControl &control)
338 {
339     QChar::Direction dir = control.basicDirection();
340     int level = sor > 0 ? analysis[sor - 1].bidiLevel : control.level;
341     while (sor < length) {
342         dir = QChar::direction(unicode[sor]);
343         // Keep skipping DirBN as if it doesn't exist
344         if (dir != QChar::DirBN)
345             break;
346         analysis[sor++].bidiLevel = level;
347     }
348
349     eor = sor;
350     if (eor == length)
351         dir = control.basicDirection();
352
353     return dir;
354 }
355
356 // creates the next QScript items.
357 static bool bidiItemize(QTextEngine *engine, QScriptAnalysis *analysis, QBidiControl &control)
358 {
359     bool rightToLeft = (control.basicDirection() == 1);
360     bool hasBidi = rightToLeft;
361 #if BIDI_DEBUG >= 2
362     qDebug() << "bidiItemize: rightToLeft=" << rightToLeft << engine->layoutData->string;
363 #endif
364
365     int sor = 0;
366     int eor = -1;
367
368
369     int length = engine->layoutData->string.length();
370
371     const ushort *unicode = (const ushort *)engine->layoutData->string.unicode();
372     int current = 0;
373
374     QChar::Direction dir = rightToLeft ? QChar::DirR : QChar::DirL;
375     QBidiStatus status;
376
377     QChar::Direction sdir = QChar::direction(*unicode);
378     if (sdir != QChar::DirL && sdir != QChar::DirR && sdir != QChar::DirEN && sdir != QChar::DirAN)
379         sdir = QChar::DirON;
380     else
381         dir = QChar::DirON;
382     status.eor = sdir;
383     status.lastStrong = rightToLeft ? QChar::DirR : QChar::DirL;
384     status.last = status.lastStrong;
385     status.dir = sdir;
386
387
388     while (current <= length) {
389
390         QChar::Direction dirCurrent;
391         if (current == (int)length)
392             dirCurrent = control.basicDirection();
393         else
394             dirCurrent = QChar::direction(unicode[current]);
395
396 #if (BIDI_DEBUG >= 2)
397 //         qDebug() << "pos=" << current << " dir=" << directions[dir]
398 //                  << " current=" << directions[dirCurrent] << " last=" << directions[status.last]
399 //                  << " eor=" << eor << '/' << directions[status.eor]
400 //                  << " sor=" << sor << " lastStrong="
401 //                  << directions[status.lastStrong]
402 //                  << " level=" << (int)control.level << " override=" << (bool)control.override;
403 #endif
404
405         switch(dirCurrent) {
406
407             // embedding and overrides (X1-X9 in the BiDi specs)
408         case QChar::DirRLE:
409         case QChar::DirRLO:
410         case QChar::DirLRE:
411         case QChar::DirLRO:
412             {
413                 bool rtl = (dirCurrent == QChar::DirRLE || dirCurrent == QChar::DirRLO);
414                 hasBidi |= rtl;
415                 bool override = (dirCurrent == QChar::DirLRO || dirCurrent == QChar::DirRLO);
416
417                 unsigned int level = control.level+1;
418                 if ((level%2 != 0) == rtl) ++level;
419                 if(level < MaxBidiLevel) {
420                     eor = current-1;
421                     appendItems(analysis, sor, eor, control, dir);
422                     eor = current;
423                     control.embed(rtl, override);
424                     QChar::Direction edir = (rtl ? QChar::DirR : QChar::DirL);
425                     dir = status.eor = edir;
426                     status.lastStrong = edir;
427                 }
428                 break;
429             }
430         case QChar::DirPDF:
431             {
432                 if (control.canPop()) {
433                     if (dir != control.direction()) {
434                         eor = current-1;
435                         appendItems(analysis, sor, eor, control, dir);
436                         dir = control.direction();
437                     }
438                     eor = current;
439                     appendItems(analysis, sor, eor, control, dir);
440                     control.pdf();
441                     dir = QChar::DirON; status.eor = QChar::DirON;
442                     status.last = control.direction();
443                     if (control.override)
444                         dir = control.direction();
445                     else
446                         dir = QChar::DirON;
447                     status.lastStrong = control.direction();
448                 }
449                 break;
450             }
451
452             // strong types
453         case QChar::DirL:
454             if(dir == QChar::DirON)
455                 dir = QChar::DirL;
456             switch(status.last)
457                 {
458                 case QChar::DirL:
459                     eor = current; status.eor = QChar::DirL; break;
460                 case QChar::DirR:
461                 case QChar::DirAL:
462                 case QChar::DirEN:
463                 case QChar::DirAN:
464                     if (eor >= 0) {
465                         appendItems(analysis, sor, eor, control, dir);
466                         status.eor = dir = skipBoundryNeutrals(analysis, unicode, length, sor, eor, control);
467                     } else {
468                         eor = current; status.eor = dir;
469                     }
470                     break;
471                 case QChar::DirES:
472                 case QChar::DirET:
473                 case QChar::DirCS:
474                 case QChar::DirBN:
475                 case QChar::DirB:
476                 case QChar::DirS:
477                 case QChar::DirWS:
478                 case QChar::DirON:
479                     if(dir != QChar::DirL) {
480                         //last stuff takes embedding dir
481                         if(control.direction() == QChar::DirR) {
482                             if(status.eor != QChar::DirR) {
483                                 // AN or EN
484                                 appendItems(analysis, sor, eor, control, dir);
485                                 status.eor = QChar::DirON;
486                                 dir = QChar::DirR;
487                             }
488                             eor = current - 1;
489                             appendItems(analysis, sor, eor, control, dir);
490                             status.eor = dir = skipBoundryNeutrals(analysis, unicode, length, sor, eor, control);
491                         } else {
492                             if(status.eor != QChar::DirL) {
493                                 appendItems(analysis, sor, eor, control, dir);
494                                 status.eor = QChar::DirON;
495                                 dir = QChar::DirL;
496                             } else {
497                                 eor = current; status.eor = QChar::DirL; break;
498                             }
499                         }
500                     } else {
501                         eor = current; status.eor = QChar::DirL;
502                     }
503                 default:
504                     break;
505                 }
506             status.lastStrong = QChar::DirL;
507             break;
508         case QChar::DirAL:
509         case QChar::DirR:
510             hasBidi = true;
511             if(dir == QChar::DirON) dir = QChar::DirR;
512             switch(status.last)
513                 {
514                 case QChar::DirL:
515                 case QChar::DirEN:
516                 case QChar::DirAN:
517                     if (eor >= 0)
518                         appendItems(analysis, sor, eor, control, dir);
519                     // fall through
520                 case QChar::DirR:
521                 case QChar::DirAL:
522                     dir = QChar::DirR; eor = current; status.eor = QChar::DirR; break;
523                 case QChar::DirES:
524                 case QChar::DirET:
525                 case QChar::DirCS:
526                 case QChar::DirBN:
527                 case QChar::DirB:
528                 case QChar::DirS:
529                 case QChar::DirWS:
530                 case QChar::DirON:
531                     if(status.eor != QChar::DirR && status.eor != QChar::DirAL) {
532                         //last stuff takes embedding dir
533                         if(control.direction() == QChar::DirR
534                            || status.lastStrong == QChar::DirR || status.lastStrong == QChar::DirAL) {
535                             appendItems(analysis, sor, eor, control, dir);
536                             dir = QChar::DirR; status.eor = QChar::DirON;
537                             eor = current;
538                         } else {
539                             eor = current - 1;
540                             appendItems(analysis, sor, eor, control, dir);
541                             dir = QChar::DirR; status.eor = QChar::DirON;
542                         }
543                     } else {
544                         eor = current; status.eor = QChar::DirR;
545                     }
546                 default:
547                     break;
548                 }
549             status.lastStrong = dirCurrent;
550             break;
551
552             // weak types:
553
554         case QChar::DirNSM:
555             if (eor == current-1)
556                 eor = current;
557             break;
558         case QChar::DirEN:
559             // if last strong was AL change EN to AN
560             if(status.lastStrong != QChar::DirAL) {
561                 if(dir == QChar::DirON) {
562                     if(status.lastStrong == QChar::DirL)
563                         dir = QChar::DirL;
564                     else
565                         dir = QChar::DirEN;
566                 }
567                 switch(status.last)
568                     {
569                     case QChar::DirET:
570                         if (status.lastStrong == QChar::DirR || status.lastStrong == QChar::DirAL) {
571                             appendItems(analysis, sor, eor, control, dir);
572                             status.eor = QChar::DirON;
573                             dir = QChar::DirAN;
574                         }
575                         // fall through
576                     case QChar::DirEN:
577                     case QChar::DirL:
578                         eor = current;
579                         status.eor = dirCurrent;
580                         break;
581                     case QChar::DirR:
582                     case QChar::DirAL:
583                     case QChar::DirAN:
584                         if (eor >= 0)
585                             appendItems(analysis, sor, eor, control, dir);
586                         else
587                             eor = current;
588                         status.eor = QChar::DirEN;
589                         dir = QChar::DirAN; break;
590                     case QChar::DirES:
591                     case QChar::DirCS:
592                         if(status.eor == QChar::DirEN || dir == QChar::DirAN) {
593                             eor = current; break;
594                         }
595                     case QChar::DirBN:
596                     case QChar::DirB:
597                     case QChar::DirS:
598                     case QChar::DirWS:
599                     case QChar::DirON:
600                         if(status.eor == QChar::DirR) {
601                             // neutrals go to R
602                             eor = current - 1;
603                             appendItems(analysis, sor, eor, control, dir);
604                             dir = QChar::DirON; status.eor = QChar::DirEN;
605                             dir = QChar::DirAN;
606                         }
607                         else if(status.eor == QChar::DirL ||
608                                  (status.eor == QChar::DirEN && status.lastStrong == QChar::DirL)) {
609                             eor = current; status.eor = dirCurrent;
610                         } else {
611                             // numbers on both sides, neutrals get right to left direction
612                             if(dir != QChar::DirL) {
613                                 appendItems(analysis, sor, eor, control, dir);
614                                 dir = QChar::DirON; status.eor = QChar::DirON;
615                                 eor = current - 1;
616                                 dir = QChar::DirR;
617                                 appendItems(analysis, sor, eor, control, dir);
618                                 dir = QChar::DirON; status.eor = QChar::DirON;
619                                 dir = QChar::DirAN;
620                             } else {
621                                 eor = current; status.eor = dirCurrent;
622                             }
623                         }
624                     default:
625                         break;
626                     }
627                 break;
628             }
629         case QChar::DirAN:
630             hasBidi = true;
631             dirCurrent = QChar::DirAN;
632             if(dir == QChar::DirON) dir = QChar::DirAN;
633             switch(status.last)
634                 {
635                 case QChar::DirL:
636                 case QChar::DirAN:
637                     eor = current; status.eor = QChar::DirAN; break;
638                 case QChar::DirR:
639                 case QChar::DirAL:
640                 case QChar::DirEN:
641                     if (eor >= 0){
642                         appendItems(analysis, sor, eor, control, dir);
643                     } else {
644                         eor = current;
645                     }
646                     dir = QChar::DirAN; status.eor = QChar::DirAN;
647                     break;
648                 case QChar::DirCS:
649                     if(status.eor == QChar::DirAN) {
650                         eor = current; break;
651                     }
652                 case QChar::DirES:
653                 case QChar::DirET:
654                 case QChar::DirBN:
655                 case QChar::DirB:
656                 case QChar::DirS:
657                 case QChar::DirWS:
658                 case QChar::DirON:
659                     if(status.eor == QChar::DirR) {
660                         // neutrals go to R
661                         eor = current - 1;
662                         appendItems(analysis, sor, eor, control, dir);
663                         status.eor = QChar::DirAN;
664                         dir = QChar::DirAN;
665                     } else if(status.eor == QChar::DirL ||
666                                (status.eor == QChar::DirEN && status.lastStrong == QChar::DirL)) {
667                         eor = current; status.eor = dirCurrent;
668                     } else {
669                         // numbers on both sides, neutrals get right to left direction
670                         if(dir != QChar::DirL) {
671                             appendItems(analysis, sor, eor, control, dir);
672                             status.eor = QChar::DirON;
673                             eor = current - 1;
674                             dir = QChar::DirR;
675                             appendItems(analysis, sor, eor, control, dir);
676                             status.eor = QChar::DirAN;
677                             dir = QChar::DirAN;
678                         } else {
679                             eor = current; status.eor = dirCurrent;
680                         }
681                     }
682                 default:
683                     break;
684                 }
685             break;
686         case QChar::DirES:
687         case QChar::DirCS:
688             break;
689         case QChar::DirET:
690             if(status.last == QChar::DirEN) {
691                 dirCurrent = QChar::DirEN;
692                 eor = current; status.eor = dirCurrent;
693             }
694             break;
695
696             // boundary neutrals should be ignored
697         case QChar::DirBN:
698             break;
699             // neutrals
700         case QChar::DirB:
701             // ### what do we do with newline and paragraph separators that come to here?
702             break;
703         case QChar::DirS:
704             // ### implement rule L1
705             break;
706         case QChar::DirWS:
707         case QChar::DirON:
708             break;
709         default:
710             break;
711         }
712
713         //qDebug() << "     after: dir=" << //        dir << " current=" << dirCurrent << " last=" << status.last << " eor=" << status.eor << " lastStrong=" << status.lastStrong << " embedding=" << control.direction();
714
715         if(current >= (int)length) break;
716
717         // set status.last as needed.
718         switch(dirCurrent) {
719         case QChar::DirET:
720         case QChar::DirES:
721         case QChar::DirCS:
722         case QChar::DirS:
723         case QChar::DirWS:
724         case QChar::DirON:
725             switch(status.last)
726             {
727             case QChar::DirL:
728             case QChar::DirR:
729             case QChar::DirAL:
730             case QChar::DirEN:
731             case QChar::DirAN:
732                 status.last = dirCurrent;
733                 break;
734             default:
735                 status.last = QChar::DirON;
736             }
737             break;
738         case QChar::DirNSM:
739         case QChar::DirBN:
740             // ignore these
741             break;
742         case QChar::DirLRO:
743         case QChar::DirLRE:
744             status.last = QChar::DirL;
745             break;
746         case QChar::DirRLO:
747         case QChar::DirRLE:
748             status.last = QChar::DirR;
749             break;
750         case QChar::DirEN:
751             if (status.last == QChar::DirL) {
752                 status.last = QChar::DirL;
753                 break;
754             }
755             // fall through
756         default:
757             status.last = dirCurrent;
758         }
759
760         ++current;
761     }
762
763 #if (BIDI_DEBUG >= 1)
764     qDebug() << "reached end of line current=" << current << ", eor=" << eor;
765 #endif
766     eor = current - 1; // remove dummy char
767
768     if (sor <= eor)
769         appendItems(analysis, sor, eor, control, dir);
770
771     return hasBidi;
772 }
773
774 void QTextEngine::bidiReorder(int numItems, const quint8 *levels, int *visualOrder)
775 {
776
777     // first find highest and lowest levels
778     quint8 levelLow = 128;
779     quint8 levelHigh = 0;
780     int i = 0;
781     while (i < numItems) {
782         //printf("level = %d\n", r->level);
783         if (levels[i] > levelHigh)
784             levelHigh = levels[i];
785         if (levels[i] < levelLow)
786             levelLow = levels[i];
787         i++;
788     }
789
790     // implements reordering of the line (L2 according to BiDi spec):
791     // L2. From the highest level found in the text to the lowest odd level on each line,
792     // reverse any contiguous sequence of characters that are at that level or higher.
793
794     // reversing is only done up to the lowest odd level
795     if(!(levelLow%2)) levelLow++;
796
797 #if (BIDI_DEBUG >= 1)
798 //     qDebug() << "reorderLine: lineLow = " << (uint)levelLow << ", lineHigh = " << (uint)levelHigh;
799 #endif
800
801     int count = numItems - 1;
802     for (i = 0; i < numItems; i++)
803         visualOrder[i] = i;
804
805     while(levelHigh >= levelLow) {
806         int i = 0;
807         while (i < count) {
808             while(i < count && levels[i] < levelHigh) i++;
809             int start = i;
810             while(i <= count && levels[i] >= levelHigh) i++;
811             int end = i-1;
812
813             if(start != end) {
814                 //qDebug() << "reversing from " << start << " to " << end;
815                 for(int j = 0; j < (end-start+1)/2; j++) {
816                     int tmp = visualOrder[start+j];
817                     visualOrder[start+j] = visualOrder[end-j];
818                     visualOrder[end-j] = tmp;
819                 }
820             }
821             i++;
822         }
823         levelHigh--;
824     }
825
826 #if (BIDI_DEBUG >= 1)
827 //     qDebug() << "visual order is:";
828 //     for (i = 0; i < numItems; i++)
829 //         qDebug() << visualOrder[i];
830 #endif
831 }
832
833 QT_BEGIN_INCLUDE_NAMESPACE
834
835 #if defined(Q_WS_X11) || defined (Q_WS_QWS)
836 #   include "qfontengine_ft_p.h"
837 #elif defined(Q_WS_MAC)
838 # include "qtextengine_mac.cpp"
839 #endif
840
841 #include <private/qharfbuzz_p.h>
842
843 QT_END_INCLUDE_NAMESPACE
844
845 // ask the font engine to find out which glyphs (as an index in the specific font) to use for the text in one item.
846 static bool stringToGlyphs(HB_ShaperItem *item, QGlyphLayout *glyphs, QFontEngine *fontEngine)
847 {
848     int nGlyphs = item->num_glyphs;
849
850     QTextEngine::ShaperFlags shaperFlags(QTextEngine::GlyphIndicesOnly);
851     if (item->item.bidiLevel % 2)
852         shaperFlags |= QTextEngine::RightToLeft;
853
854     bool result = fontEngine->stringToCMap(reinterpret_cast<const QChar *>(item->string + item->item.pos), item->item.length, glyphs, &nGlyphs, shaperFlags);
855     item->num_glyphs = nGlyphs;
856     glyphs->numGlyphs = nGlyphs;
857     return result;
858 }
859
860 // shape all the items that intersect with the line, taking tab widths into account to find out what text actually fits in the line.
861 void QTextEngine::shapeLine(const QScriptLine &line)
862 {
863     QFixed x;
864     bool first = true;
865     const int end = findItem(line.from + line.length - 1);
866     int item = findItem(line.from);
867     if (item == -1)
868         return;
869     for (item = findItem(line.from); item <= end; ++item) {
870         QScriptItem &si = layoutData->items[item];
871         if (si.analysis.flags == QScriptAnalysis::Tab) {
872             ensureSpace(1);
873             si.width = calculateTabWidth(item, x);
874         } else {
875             shape(item);
876         }
877         if (first && si.position != line.from) { // that means our x position has to be offset
878             QGlyphLayout glyphs = shapedGlyphs(&si);
879             Q_ASSERT(line.from > si.position);
880             for (int i = line.from - si.position - 1; i >= 0; i--) {
881                 x -= glyphs.effectiveAdvance(i);
882             }
883         }
884         first = false;
885
886         x += si.width;
887     }
888 }
889
890 #if !defined(QT_ENABLE_HARFBUZZ_FOR_MAC) && defined(Q_WS_MAC)
891 static bool enableHarfBuzz()
892 {
893     static enum { Yes, No, Unknown } status = Unknown;
894
895     if (status == Unknown) {
896         QByteArray v = qgetenv("QT_ENABLE_HARFBUZZ");
897         bool value = !v.isEmpty() && v != "0" && v != "false";
898         if (value) status = Yes;
899         else status = No;
900     }
901     return status == Yes;
902 }
903 #endif
904
905 void QTextEngine::shapeText(int item) const
906 {
907     Q_ASSERT(item < layoutData->items.size());
908     QScriptItem &si = layoutData->items[item];
909
910     if (si.num_glyphs)
911         return;
912
913 #if defined(Q_WS_MAC)
914 #if !defined(QT_ENABLE_HARFBUZZ_FOR_MAC)
915     if (enableHarfBuzz()) {
916 #endif
917         QFontEngine *actualFontEngine = fontEngine(si, &si.ascent, &si.descent, &si.leading);
918         if (actualFontEngine->type() == QFontEngine::Multi)
919             actualFontEngine = static_cast<QFontEngineMulti *>(actualFontEngine)->engine(0);
920
921         HB_Face face = actualFontEngine->harfbuzzFace();
922         HB_Script script = (HB_Script) si.analysis.script;
923         if (face->supported_scripts[script])
924             shapeTextWithHarfbuzz(item);
925         else
926             shapeTextMac(item);
927 #if !defined(QT_ENABLE_HARFBUZZ_FOR_MAC)
928     } else {
929         shapeTextMac(item);
930     }
931 #endif
932 #elif defined(Q_WS_WINCE)
933     shapeTextWithCE(item);
934 #else
935     shapeTextWithHarfbuzz(item);
936 #endif
937
938     si.width = 0;
939
940     if (!si.num_glyphs)
941         return;
942     QGlyphLayout glyphs = shapedGlyphs(&si);
943
944     QFont font = this->font(si);
945     bool letterSpacingIsAbsolute = font.d->letterSpacingIsAbsolute;
946     QFixed letterSpacing = font.d->letterSpacing;
947     QFixed wordSpacing = font.d->wordSpacing;
948
949     if (letterSpacingIsAbsolute && letterSpacing.value())
950         letterSpacing *= font.d->dpi / qt_defaultDpiY();
951
952     if (letterSpacing != 0) {
953         for (int i = 1; i < si.num_glyphs; ++i) {
954             if (glyphs.attributes[i].clusterStart) {
955                 if (letterSpacingIsAbsolute)
956                     glyphs.advances_x[i-1] += letterSpacing;
957                 else {
958                     QFixed &advance = glyphs.advances_x[i-1];
959                     advance += (letterSpacing - 100) * advance / 100;
960                 }
961             }
962         }
963         if (letterSpacingIsAbsolute)
964             glyphs.advances_x[si.num_glyphs-1] += letterSpacing;
965         else {
966             QFixed &advance = glyphs.advances_x[si.num_glyphs-1];
967             advance += (letterSpacing - 100) * advance / 100;
968         }
969     }
970     if (wordSpacing != 0) {
971         for (int i = 0; i < si.num_glyphs; ++i) {
972             if (glyphs.attributes[i].justification == HB_Space
973                 || glyphs.attributes[i].justification == HB_Arabic_Space) {
974                 // word spacing only gets added once to a consecutive run of spaces (see CSS spec)
975                 if (i + 1 == si.num_glyphs
976                     ||(glyphs.attributes[i+1].justification != HB_Space
977                        && glyphs.attributes[i+1].justification != HB_Arabic_Space))
978                     glyphs.advances_x[i] += wordSpacing;
979             }
980         }
981     }
982
983     for (int i = 0; i < si.num_glyphs; ++i)
984         si.width += glyphs.advances_x[i] * !glyphs.attributes[i].dontPrint;
985 }
986
987 static inline bool hasCaseChange(const QScriptItem &si)
988 {
989     return si.analysis.flags == QScriptAnalysis::SmallCaps ||
990            si.analysis.flags == QScriptAnalysis::Uppercase ||
991            si.analysis.flags == QScriptAnalysis::Lowercase;
992 }
993
994 #if defined(Q_WS_WINCE) //TODO
995 // set the glyph attributes heuristically. Assumes a 1 to 1 relationship between chars and glyphs
996 // and no reordering.
997 // also computes logClusters heuristically
998 static void heuristicSetGlyphAttributes(const QChar *uc, int length, QGlyphLayout *glyphs, unsigned short *logClusters, int num_glyphs)
999 {
1000     // ### zeroWidth and justification are missing here!!!!!
1001
1002     Q_UNUSED(num_glyphs);
1003     Q_ASSERT(num_glyphs <= length);
1004
1005 //     qDebug("QScriptEngine::heuristicSetGlyphAttributes, num_glyphs=%d", item->num_glyphs);
1006
1007     int glyph_pos = 0;
1008     for (int i = 0; i < length; i++) {
1009         if (uc[i].isHighSurrogate() && i < length-1 && uc[i+1].isLowSurrogate()) {
1010             logClusters[i] = glyph_pos;
1011             logClusters[++i] = glyph_pos;
1012         } else {
1013             logClusters[i] = glyph_pos;
1014         }
1015         ++glyph_pos;
1016     }
1017
1018     // first char in a run is never (treated as) a mark
1019     int cStart = 0;
1020
1021     const bool symbolFont = false; // ####
1022     glyphs->attributes[0].mark = false;
1023     glyphs->attributes[0].clusterStart = true;
1024     glyphs->attributes[0].dontPrint = (!symbolFont && uc[0].unicode() == 0x00ad) || qIsControlChar(uc[0].unicode());
1025
1026     int pos = 0;
1027     int lastCat = QChar::category(uc[0].unicode());
1028     for (int i = 1; i < length; ++i) {
1029         if (logClusters[i] == pos)
1030             // same glyph
1031             continue;
1032         ++pos;
1033         while (pos < logClusters[i]) {
1034             glyphs[pos].attributes = glyphs[pos-1].attributes;
1035             ++pos;
1036         }
1037         // hide soft-hyphens by default
1038         if ((!symbolFont && uc[i].unicode() == 0x00ad) || qIsControlChar(uc[i].unicode()))
1039             glyphs->attributes[pos].dontPrint = true;
1040         const QUnicodeTables::Properties *prop = QUnicodeTables::properties(uc[i].unicode());
1041         int cat = prop->category;
1042         if (cat != QChar::Mark_NonSpacing) {
1043             glyphs->attributes[pos].mark = false;
1044             glyphs->attributes[pos].clusterStart = true;
1045             glyphs->attributes[pos].combiningClass = 0;
1046             cStart = logClusters[i];
1047         } else {
1048             int cmb = prop->combiningClass;
1049
1050             if (cmb == 0) {
1051                 // Fix 0 combining classes
1052                 if ((uc[pos].unicode() & 0xff00) == 0x0e00) {
1053                     // thai or lao
1054                     unsigned char col = uc[pos].cell();
1055                     if (col == 0x31 ||
1056                          col == 0x34 ||
1057                          col == 0x35 ||
1058                          col == 0x36 ||
1059                          col == 0x37 ||
1060                          col == 0x47 ||
1061                          col == 0x4c ||
1062                          col == 0x4d ||
1063                          col == 0x4e) {
1064                         cmb = QChar::Combining_AboveRight;
1065                     } else if (col == 0xb1 ||
1066                                 col == 0xb4 ||
1067                                 col == 0xb5 ||
1068                                 col == 0xb6 ||
1069                                 col == 0xb7 ||
1070                                 col == 0xbb ||
1071                                 col == 0xcc ||
1072                                 col == 0xcd) {
1073                         cmb = QChar::Combining_Above;
1074                     } else if (col == 0xbc) {
1075                         cmb = QChar::Combining_Below;
1076                     }
1077                 }
1078             }
1079
1080             glyphs->attributes[pos].mark = true;
1081             glyphs->attributes[pos].clusterStart = false;
1082             glyphs->attributes[pos].combiningClass = cmb;
1083             logClusters[i] = cStart;
1084             glyphs->advances_x[pos] = 0;
1085             glyphs->advances_y[pos] = 0;
1086         }
1087
1088         // one gets an inter character justification point if the current char is not a non spacing mark.
1089         // as then the current char belongs to the last one and one gets a space justification point
1090         // after the space char.
1091         if (lastCat == QChar::Separator_Space)
1092             glyphs->attributes[pos-1].justification = HB_Space;
1093         else if (cat != QChar::Mark_NonSpacing)
1094             glyphs->attributes[pos-1].justification = HB_Character;
1095         else
1096             glyphs->attributes[pos-1].justification = HB_NoJustification;
1097
1098         lastCat = cat;
1099     }
1100     pos = logClusters[length-1];
1101     if (lastCat == QChar::Separator_Space)
1102         glyphs->attributes[pos].justification = HB_Space;
1103     else
1104         glyphs->attributes[pos].justification = HB_Character;
1105 }
1106
1107 void QTextEngine::shapeTextWithCE(int item) const
1108 {
1109     QScriptItem &si = layoutData->items[item];
1110     si.glyph_data_offset = layoutData->used;
1111
1112     QFontEngine *fe = fontEngine(si, &si.ascent, &si.descent, &si.leading);
1113
1114     QTextEngine::ShaperFlags flags;
1115     if (si.analysis.bidiLevel % 2)
1116         flags |= RightToLeft;
1117     if (option.useDesignMetrics())
1118         flags |= DesignMetrics;
1119
1120     // pre-initialize char attributes
1121     if (! attributes())
1122         return;
1123
1124     const int len = length(item);
1125     int num_glyphs = length(item);
1126     const QChar *str = layoutData->string.unicode() + si.position;
1127     ushort upperCased[256];
1128     if (hasCaseChange(si)) {
1129         ushort *uc = upperCased;
1130         if (len > 256)
1131             uc = new ushort[len];
1132         for (int i = 0; i < len; ++i) {
1133             if(si.analysis.flags == QScriptAnalysis::Lowercase)
1134                 uc[i] = str[i].toLower().unicode();
1135             else
1136                 uc[i] = str[i].toUpper().unicode();
1137         }
1138         str = reinterpret_cast<const QChar *>(uc);
1139     }
1140
1141     while (true) {
1142         if (! ensureSpace(num_glyphs)) {
1143             // If str is converted to uppercase/lowercase form with a new buffer,
1144             // we need to delete that buffer before return for error
1145             const ushort *uc = reinterpret_cast<const ushort *>(str);
1146             if (hasCaseChange(si) && uc != upperCased)
1147                 delete [] uc;
1148             return;
1149         }
1150         num_glyphs = layoutData->glyphLayout.numGlyphs - layoutData->used;
1151
1152         QGlyphLayout g = availableGlyphs(&si);
1153         unsigned short *log_clusters = logClusters(&si);
1154
1155         if (fe->stringToCMap(str,
1156                              len,
1157                              &g,
1158                              &num_glyphs,
1159                              flags)) {
1160             heuristicSetGlyphAttributes(str, len, &g, log_clusters, num_glyphs);
1161                     break;
1162         }
1163     }
1164
1165     si.num_glyphs = num_glyphs;
1166
1167     layoutData->used += si.num_glyphs;
1168
1169     const ushort *uc = reinterpret_cast<const ushort *>(str);
1170     if (hasCaseChange(si) && uc != upperCased)
1171         delete [] uc;
1172 }
1173 #endif
1174
1175 static inline void moveGlyphData(const QGlyphLayout &destination, const QGlyphLayout &source, int num)
1176 {
1177     if (num > 0 && destination.glyphs != source.glyphs) {
1178         memmove(destination.glyphs, source.glyphs, num * sizeof(HB_Glyph));
1179         memmove(destination.attributes, source.attributes, num * sizeof(HB_GlyphAttributes));
1180         memmove(destination.advances_x, source.advances_x, num * sizeof(HB_Fixed));
1181         memmove(destination.offsets, source.offsets, num * sizeof(HB_FixedPoint));
1182     }
1183 }
1184
1185 /// take the item from layoutData->items and
1186 void QTextEngine::shapeTextWithHarfbuzz(int item) const
1187 {
1188     Q_ASSERT(sizeof(HB_Fixed) == sizeof(QFixed));
1189     Q_ASSERT(sizeof(HB_FixedPoint) == sizeof(QFixedPoint));
1190
1191     QScriptItem &si = layoutData->items[item];
1192
1193     si.glyph_data_offset = layoutData->used;
1194
1195     QFontEngine *font = fontEngine(si, &si.ascent, &si.descent, &si.leading);
1196
1197     bool kerningEnabled = this->font(si).d->kerning;
1198
1199     HB_ShaperItem entire_shaper_item;
1200     qMemSet(&entire_shaper_item, 0, sizeof(entire_shaper_item));
1201     entire_shaper_item.string = reinterpret_cast<const HB_UChar16 *>(layoutData->string.constData());
1202     entire_shaper_item.stringLength = layoutData->string.length();
1203     entire_shaper_item.item.script = (HB_Script)si.analysis.script;
1204     entire_shaper_item.item.pos = si.position;
1205     entire_shaper_item.item.length = length(item);
1206     entire_shaper_item.item.bidiLevel = si.analysis.bidiLevel;
1207
1208     HB_UChar16 upperCased[256]; // XXX what about making this 4096, so we don't have to extend it ever.
1209     if (hasCaseChange(si)) {
1210         HB_UChar16 *uc = upperCased;
1211         if (entire_shaper_item.item.length > 256)
1212             uc = new HB_UChar16[entire_shaper_item.item.length];
1213         for (uint i = 0; i < entire_shaper_item.item.length; ++i) {
1214             if(si.analysis.flags == QScriptAnalysis::Lowercase)
1215                 uc[i] = QChar::toLower(entire_shaper_item.string[si.position + i]);
1216             else
1217                 uc[i] = QChar::toUpper(entire_shaper_item.string[si.position + i]);
1218         }
1219         entire_shaper_item.item.pos = 0;
1220         entire_shaper_item.string = uc;
1221         entire_shaper_item.stringLength = entire_shaper_item.item.length;
1222     }
1223
1224     entire_shaper_item.shaperFlags = 0;
1225     if (!kerningEnabled)
1226         entire_shaper_item.shaperFlags |= HB_ShaperFlag_NoKerning;
1227     if (option.useDesignMetrics())
1228         entire_shaper_item.shaperFlags |= HB_ShaperFlag_UseDesignMetrics;
1229
1230     entire_shaper_item.num_glyphs = qMax(layoutData->glyphLayout.numGlyphs - layoutData->used, int(entire_shaper_item.item.length));
1231     if (! ensureSpace(entire_shaper_item.num_glyphs)) {
1232         if (hasCaseChange(si))
1233             delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);
1234         return;
1235     }
1236     QGlyphLayout initialGlyphs = availableGlyphs(&si).mid(0, entire_shaper_item.num_glyphs);
1237
1238     if (!stringToGlyphs(&entire_shaper_item, &initialGlyphs, font)) {
1239         if (! ensureSpace(entire_shaper_item.num_glyphs)) {
1240             if (hasCaseChange(si))
1241                 delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);
1242             return;
1243         }
1244         initialGlyphs = availableGlyphs(&si).mid(0, entire_shaper_item.num_glyphs);
1245
1246         if (!stringToGlyphs(&entire_shaper_item, &initialGlyphs, font)) {
1247             // ############ if this happens there's a bug in the fontengine
1248             if (hasCaseChange(si) && entire_shaper_item.string != upperCased)
1249                 delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);
1250             return;
1251         }
1252     }
1253
1254     // split up the item into parts that come from different font engines.
1255     QVarLengthArray<int> itemBoundaries(2);
1256     // k * 2 entries, array[k] == index in string, array[k + 1] == index in glyphs
1257     itemBoundaries[0] = entire_shaper_item.item.pos;
1258     itemBoundaries[1] = 0;
1259
1260     if (font->type() == QFontEngine::Multi) {
1261         uint lastEngine = 0;
1262         int charIdx = entire_shaper_item.item.pos;
1263         const int stringEnd = charIdx + entire_shaper_item.item.length;
1264         for (quint32 i = 0; i < entire_shaper_item.num_glyphs; ++i, ++charIdx) {
1265             uint engineIdx = initialGlyphs.glyphs[i] >> 24;
1266             if (engineIdx != lastEngine && i > 0) {
1267                 itemBoundaries.append(charIdx);
1268                 itemBoundaries.append(i);
1269             }
1270             lastEngine = engineIdx;
1271             if (HB_IsHighSurrogate(entire_shaper_item.string[charIdx])
1272                 && charIdx < stringEnd - 1
1273                 && HB_IsLowSurrogate(entire_shaper_item.string[charIdx + 1]))
1274                 ++charIdx;
1275         }
1276     }
1277
1278
1279
1280     int remaining_glyphs = entire_shaper_item.num_glyphs;
1281     int glyph_pos = 0;
1282     // for each item shape using harfbuzz and store the results in our layoutData's glyphs array.
1283     for (int k = 0; k < itemBoundaries.size(); k += 2) { // for the +2, see the comment at the definition of itemBoundaries
1284
1285         HB_ShaperItem shaper_item = entire_shaper_item;
1286
1287         shaper_item.item.pos = itemBoundaries[k];
1288         if (k < itemBoundaries.size() - 3) {
1289             shaper_item.item.length = itemBoundaries[k + 2] - shaper_item.item.pos;
1290             shaper_item.num_glyphs = itemBoundaries[k + 3] - itemBoundaries[k + 1];
1291         } else { // last combo in the list, avoid out of bounds access.
1292             shaper_item.item.length -= shaper_item.item.pos - entire_shaper_item.item.pos;
1293             shaper_item.num_glyphs -= itemBoundaries[k + 1];
1294         }
1295         shaper_item.initialGlyphCount = shaper_item.num_glyphs;
1296         if (shaper_item.num_glyphs < shaper_item.item.length)
1297             shaper_item.num_glyphs = shaper_item.item.length;
1298
1299         QFontEngine *actualFontEngine = font;
1300         uint engineIdx = 0;
1301         if (font->type() == QFontEngine::Multi) {
1302             engineIdx = uint(availableGlyphs(&si).glyphs[glyph_pos] >> 24);
1303
1304             actualFontEngine = static_cast<QFontEngineMulti *>(font)->engine(engineIdx);
1305         }
1306
1307         si.ascent = qMax(actualFontEngine->ascent(), si.ascent);
1308         si.descent = qMax(actualFontEngine->descent(), si.descent);
1309         si.leading = qMax(actualFontEngine->leading(), si.leading);
1310
1311         shaper_item.font = actualFontEngine->harfbuzzFont();
1312         shaper_item.face = actualFontEngine->harfbuzzFace();
1313
1314         shaper_item.glyphIndicesPresent = true;
1315
1316         remaining_glyphs -= shaper_item.initialGlyphCount;
1317
1318         do {
1319             if (! ensureSpace(glyph_pos + shaper_item.num_glyphs + remaining_glyphs)) {
1320                 if (hasCaseChange(si))
1321                     delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);
1322                 return;
1323             }
1324
1325             const QGlyphLayout g = availableGlyphs(&si).mid(glyph_pos);
1326             if (shaper_item.num_glyphs > shaper_item.item.length)
1327                 moveGlyphData(g.mid(shaper_item.num_glyphs), g.mid(shaper_item.initialGlyphCount), remaining_glyphs);
1328
1329             shaper_item.glyphs = g.glyphs;
1330             shaper_item.attributes = g.attributes;
1331             shaper_item.advances = reinterpret_cast<HB_Fixed *>(g.advances_x);
1332             shaper_item.offsets = reinterpret_cast<HB_FixedPoint *>(g.offsets);
1333
1334             if (shaper_item.glyphIndicesPresent) {
1335                 for (hb_uint32 i = 0; i < shaper_item.initialGlyphCount; ++i)
1336                     shaper_item.glyphs[i] &= 0x00ffffff;
1337             }
1338
1339             shaper_item.log_clusters = logClusters(&si) + shaper_item.item.pos - entire_shaper_item.item.pos;
1340
1341 //          qDebug("    .. num_glyphs=%d, used=%d, item.num_glyphs=%d", num_glyphs, used, shaper_item.num_glyphs);
1342         } while (!qShapeItem(&shaper_item)); // this does the actual shaping via harfbuzz.
1343
1344         QGlyphLayout g = availableGlyphs(&si).mid(glyph_pos, shaper_item.num_glyphs);
1345         moveGlyphData(g.mid(shaper_item.num_glyphs), g.mid(shaper_item.initialGlyphCount), remaining_glyphs);
1346
1347         for (hb_uint32 i = 0; i < shaper_item.num_glyphs; ++i)
1348             g.glyphs[i] = g.glyphs[i] | (engineIdx << 24);
1349
1350         for (hb_uint32 i = 0; i < shaper_item.item.length; ++i)
1351             shaper_item.log_clusters[i] += glyph_pos;
1352
1353         if (kerningEnabled && !shaper_item.kerning_applied)
1354             font->doKerning(&g, option.useDesignMetrics() ? QFlag(QTextEngine::DesignMetrics) : QFlag(0));
1355
1356         glyph_pos += shaper_item.num_glyphs;
1357     }
1358
1359 //     qDebug("    -> item: script=%d num_glyphs=%d", shaper_item.script, shaper_item.num_glyphs);
1360     si.num_glyphs = glyph_pos;
1361
1362     layoutData->used += si.num_glyphs;
1363
1364     if (hasCaseChange(si) && entire_shaper_item.string != upperCased)
1365         delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);
1366 }
1367
1368 static void init(QTextEngine *e)
1369 {
1370     e->ignoreBidi = false;
1371     e->cacheGlyphs = false;
1372     e->forceJustification = false;
1373     e->visualMovement = false;
1374
1375     e->layoutData = 0;
1376
1377     e->minWidth = 0;
1378     e->maxWidth = 0;
1379
1380     e->underlinePositions = 0;
1381     e->specialData = 0;
1382     e->stackEngine = false;
1383 }
1384
1385 QTextEngine::QTextEngine()
1386 {
1387     init(this);
1388 }
1389
1390 QTextEngine::QTextEngine(const QString &str, const QFont &f)
1391     : text(str),
1392       fnt(f)
1393 {
1394     init(this);
1395 }
1396
1397 QTextEngine::~QTextEngine()
1398 {
1399     if (!stackEngine)
1400         delete layoutData;
1401     delete specialData;
1402     resetFontEngineCache();
1403 }
1404
1405 const HB_CharAttributes *QTextEngine::attributes() const
1406 {
1407     if (layoutData && layoutData->haveCharAttributes)
1408         return (HB_CharAttributes *) layoutData->memory;
1409
1410     itemize();
1411     if (! ensureSpace(layoutData->string.length()))
1412         return NULL;
1413
1414     QVarLengthArray<HB_ScriptItem> hbScriptItems(layoutData->items.size());
1415
1416     for (int i = 0; i < layoutData->items.size(); ++i) {
1417         const QScriptItem &si = layoutData->items[i];
1418         hbScriptItems[i].pos = si.position;
1419         hbScriptItems[i].length = length(i);
1420         hbScriptItems[i].bidiLevel = si.analysis.bidiLevel;
1421         hbScriptItems[i].script = (HB_Script)si.analysis.script;
1422     }
1423
1424     qGetCharAttributes(reinterpret_cast<const HB_UChar16 *>(layoutData->string.constData()),
1425                        layoutData->string.length(),
1426                        hbScriptItems.data(), hbScriptItems.size(),
1427                        (HB_CharAttributes *)layoutData->memory);
1428
1429
1430     layoutData->haveCharAttributes = true;
1431     return (HB_CharAttributes *) layoutData->memory;
1432 }
1433
1434 void QTextEngine::shape(int item) const
1435 {
1436     if (layoutData->items[item].analysis.flags == QScriptAnalysis::Object) {
1437         ensureSpace(1);
1438         if (block.docHandle()) {
1439             QTextFormat format = formats()->format(formatIndex(&layoutData->items[item]));
1440             docLayout()->resizeInlineObject(QTextInlineObject(item, const_cast<QTextEngine *>(this)),
1441                                             layoutData->items[item].position + block.position(), format);
1442         }
1443     } else if (layoutData->items[item].analysis.flags == QScriptAnalysis::Tab) {
1444         // set up at least the ascent/descent/leading of the script item for the tab
1445         fontEngine(layoutData->items[item],
1446                    &layoutData->items[item].ascent,
1447                    &layoutData->items[item].descent,
1448                    &layoutData->items[item].leading);
1449     } else {
1450         shapeText(item);
1451     }
1452 }
1453
1454 static inline void releaseCachedFontEngine(QFontEngine *fontEngine)
1455 {
1456     if (fontEngine) {
1457         fontEngine->ref.deref();
1458         if (fontEngine->cache_count == 0 && fontEngine->ref == 0)
1459             delete fontEngine;
1460     }
1461 }
1462
1463 void QTextEngine::resetFontEngineCache()
1464 {
1465     releaseCachedFontEngine(feCache.prevFontEngine);
1466     releaseCachedFontEngine(feCache.prevScaledFontEngine);
1467     feCache.reset();
1468 }
1469
1470 void QTextEngine::invalidate()
1471 {
1472     freeMemory();
1473     minWidth = 0;
1474     maxWidth = 0;
1475     if (specialData)
1476         specialData->resolvedFormatIndices.clear();
1477
1478     resetFontEngineCache();
1479 }
1480
1481 void QTextEngine::clearLineData()
1482 {
1483     lines.clear();
1484 }
1485
1486 void QTextEngine::validate() const
1487 {
1488     if (layoutData)
1489         return;
1490     layoutData = new LayoutData();
1491     if (block.docHandle()) {
1492         layoutData->string = block.text();
1493         if (option.flags() & QTextOption::ShowLineAndParagraphSeparators)
1494             layoutData->string += QLatin1Char(block.next().isValid() ? 0xb6 : 0x20);
1495     } else {
1496         layoutData->string = text;
1497     }
1498     if (specialData && specialData->preeditPosition != -1)
1499         layoutData->string.insert(specialData->preeditPosition, specialData->preeditText);
1500 }
1501
1502 void QTextEngine::itemize() const
1503 {
1504     validate();
1505     if (layoutData->items.size())
1506         return;
1507
1508     int length = layoutData->string.length();
1509     if (!length)
1510         return;
1511 #if defined(Q_WS_MAC) && !defined(QT_MAC_USE_COCOA)
1512     // ATSUI requires RTL flags to correctly identify the character stops.
1513     bool ignore = false;
1514 #else
1515     bool ignore = ignoreBidi;
1516 #endif
1517
1518     bool rtl = isRightToLeft();
1519
1520     if (!ignore && !rtl) {
1521         ignore = true;
1522         const QChar *start = layoutData->string.unicode();
1523         const QChar * const end = start + length;
1524         while (start < end) {
1525             if (start->unicode() >= 0x590) {
1526                 ignore = false;
1527                 break;
1528             }
1529             ++start;
1530         }
1531     }
1532
1533     QVarLengthArray<QScriptAnalysis, 4096> scriptAnalysis(length);
1534     QScriptAnalysis *analysis = scriptAnalysis.data();
1535
1536     QBidiControl control(rtl);
1537
1538     if (ignore) {
1539         memset(analysis, 0, length*sizeof(QScriptAnalysis));
1540         if (option.textDirection() == Qt::RightToLeft) {
1541             for (int i = 0; i < length; ++i)
1542                 analysis[i].bidiLevel = 1;
1543             layoutData->hasBidi = true;
1544         }
1545     } else {
1546         layoutData->hasBidi = bidiItemize(const_cast<QTextEngine *>(this), analysis, control);
1547     }
1548
1549     const ushort *uc = reinterpret_cast<const ushort *>(layoutData->string.unicode());
1550     const ushort *e = uc + length;
1551     int lastScript = QUnicodeTables::Common;
1552     while (uc < e) {
1553         switch (*uc) {
1554         case QChar::ObjectReplacementCharacter:
1555             analysis->script = QUnicodeTables::Common;
1556             analysis->flags = QScriptAnalysis::Object;
1557             break;
1558         case QChar::LineSeparator:
1559             if (analysis->bidiLevel % 2)
1560                 --analysis->bidiLevel;
1561             analysis->script = QUnicodeTables::Common;
1562             analysis->flags = QScriptAnalysis::LineOrParagraphSeparator;
1563             if (option.flags() & QTextOption::ShowLineAndParagraphSeparators)
1564                 *const_cast<ushort*>(uc) = 0x21B5; // visual line separator
1565             break;
1566         case 9: // Tab
1567             analysis->script = QUnicodeTables::Common;
1568             analysis->flags = QScriptAnalysis::Tab;
1569             analysis->bidiLevel = control.baseLevel();
1570             break;
1571         case 32: // Space
1572         case QChar::Nbsp:
1573             if (option.flags() & QTextOption::ShowTabsAndSpaces) {
1574                 analysis->script = QUnicodeTables::Common;
1575                 analysis->flags = QScriptAnalysis::Space;
1576                 analysis->bidiLevel = control.baseLevel();
1577                 break;
1578             }
1579         // fall through
1580         default:
1581             int script = QUnicodeTables::script(*uc);
1582             analysis->script = script == QUnicodeTables::Inherited ? lastScript : script;
1583             analysis->flags = QScriptAnalysis::None;
1584             break;
1585         }
1586         lastScript = analysis->script;
1587         ++uc;
1588         ++analysis;
1589     }
1590     if (option.flags() & QTextOption::ShowLineAndParagraphSeparators) {
1591         (analysis-1)->flags = QScriptAnalysis::LineOrParagraphSeparator; // to exclude it from width
1592     }
1593
1594     Itemizer itemizer(layoutData->string, scriptAnalysis.data(), layoutData->items);
1595
1596     const QTextDocumentPrivate *p = block.docHandle();
1597     if (p) {
1598         SpecialData *s = specialData;
1599
1600         QTextDocumentPrivate::FragmentIterator it = p->find(block.position());
1601         QTextDocumentPrivate::FragmentIterator end = p->find(block.position() + block.length() - 1); // -1 to omit the block separator char
1602         int format = it.value()->format;
1603
1604         int prevPosition = 0;
1605         int position = prevPosition;
1606         while (1) {
1607             const QTextFragmentData * const frag = it.value();
1608             if (it == end || format != frag->format) {
1609                 if (s && position >= s->preeditPosition) {
1610                     position += s->preeditText.length();
1611                     s = 0;
1612                 }
1613                 Q_ASSERT(position <= length);
1614                 itemizer.generate(prevPosition, position - prevPosition,
1615                     formats()->charFormat(format).fontCapitalization());
1616                 if (it == end) {
1617                     if (position < length)
1618                         itemizer.generate(position, length - position,
1619                                           formats()->charFormat(format).fontCapitalization());
1620                     break;
1621                 }
1622                 format = frag->format;
1623                 prevPosition = position;
1624             }
1625             position += frag->size_array[0];
1626             ++it;
1627         }
1628     } else {
1629         itemizer.generate(0, length, static_cast<QFont::Capitalization> (fnt.d->capital));
1630     }
1631
1632     addRequiredBoundaries();
1633     resolveAdditionalFormats();
1634 }
1635
1636 bool QTextEngine::isRightToLeft() const
1637 {
1638     switch (option.textDirection()) {
1639     case Qt::LeftToRight:
1640         return false;
1641     case Qt::RightToLeft:
1642         return true;
1643     default:
1644         break;
1645     }
1646     if (!layoutData)
1647         itemize();
1648     // this places the cursor in the right position depending on the keyboard layout
1649     if (layoutData->string.isEmpty())
1650         return QApplication::keyboardInputDirection() == Qt::RightToLeft;
1651     return layoutData->string.isRightToLeft();
1652 }
1653
1654
1655 int QTextEngine::findItem(int strPos) const
1656 {
1657     itemize();
1658
1659     int left = 1;
1660     int right = layoutData->items.size()-1;
1661     while (left <= right) {
1662         int middle = ((right-left)/2)+left;
1663         if (strPos > layoutData->items[middle].position)
1664             left = middle+1;
1665         else if (strPos < layoutData->items[middle].position)
1666             right = middle-1;
1667         else {
1668             return middle;
1669         }
1670     }
1671     return right;
1672 }
1673
1674 QFixed QTextEngine::width(int from, int len) const
1675 {
1676     itemize();
1677
1678     QFixed w = 0;
1679
1680 //     qDebug("QTextEngine::width(from = %d, len = %d), numItems=%d, strleng=%d", from,  len, items.size(), string.length());
1681     for (int i = 0; i < layoutData->items.size(); i++) {
1682         const QScriptItem *si = layoutData->items.constData() + i;
1683         int pos = si->position;
1684         int ilen = length(i);
1685 //          qDebug("item %d: from %d len %d", i, pos, ilen);
1686         if (pos >= from + len)
1687             break;
1688         if (pos + ilen > from) {
1689             if (!si->num_glyphs)
1690                 shape(i);
1691
1692             if (si->analysis.flags == QScriptAnalysis::Object) {
1693                 w += si->width;
1694                 continue;
1695             } else if (si->analysis.flags == QScriptAnalysis::Tab) {
1696                 w += calculateTabWidth(i, w);
1697                 continue;
1698             }
1699
1700
1701             QGlyphLayout glyphs = shapedGlyphs(si);
1702             unsigned short *logClusters = this->logClusters(si);
1703
1704 //             fprintf(stderr, "  logclusters:");
1705 //             for (int k = 0; k < ilen; k++)
1706 //                 fprintf(stderr, " %d", logClusters[k]);
1707 //             fprintf(stderr, "\n");
1708             // do the simple thing for now and give the first glyph in a cluster the full width, all other ones 0.
1709             int charFrom = from - pos;
1710             if (charFrom < 0)
1711                 charFrom = 0;
1712             int glyphStart = logClusters[charFrom];
1713             if (charFrom > 0 && logClusters[charFrom-1] == glyphStart)
1714                 while (charFrom < ilen && logClusters[charFrom] == glyphStart)
1715                     charFrom++;
1716             if (charFrom < ilen) {
1717                 glyphStart = logClusters[charFrom];
1718                 int charEnd = from + len - 1 - pos;
1719                 if (charEnd >= ilen)
1720                     charEnd = ilen-1;
1721                 int glyphEnd = logClusters[charEnd];
1722                 while (charEnd < ilen && logClusters[charEnd] == glyphEnd)
1723                     charEnd++;
1724                 glyphEnd = (charEnd == ilen) ? si->num_glyphs : logClusters[charEnd];
1725
1726 //                 qDebug("char: start=%d end=%d / glyph: start = %d, end = %d", charFrom, charEnd, glyphStart, glyphEnd);
1727                 for (int i = glyphStart; i < glyphEnd; i++)
1728                     w += glyphs.advances_x[i] * !glyphs.attributes[i].dontPrint;
1729             }
1730         }
1731     }
1732 //     qDebug("   --> w= %d ", w);
1733     return w;
1734 }
1735
1736 glyph_metrics_t QTextEngine::boundingBox(int from,  int len) const
1737 {
1738     itemize();
1739
1740     glyph_metrics_t gm;
1741
1742     for (int i = 0; i < layoutData->items.size(); i++) {
1743         const QScriptItem *si = layoutData->items.constData() + i;
1744
1745         int pos = si->position;
1746         int ilen = length(i);
1747         if (pos > from + len)
1748             break;
1749         if (pos + ilen > from) {
1750             if (!si->num_glyphs)
1751                 shape(i);
1752
1753             if (si->analysis.flags == QScriptAnalysis::Object) {
1754                 gm.width += si->width;
1755                 continue;
1756             } else if (si->analysis.flags == QScriptAnalysis::Tab) {
1757                 gm.width += calculateTabWidth(i, gm.width);
1758                 continue;
1759             }
1760
1761             unsigned short *logClusters = this->logClusters(si);
1762             QGlyphLayout glyphs = shapedGlyphs(si);
1763
1764             // do the simple thing for now and give the first glyph in a cluster the full width, all other ones 0.
1765             int charFrom = from - pos;
1766             if (charFrom < 0)
1767                 charFrom = 0;
1768             int glyphStart = logClusters[charFrom];
1769             if (charFrom > 0 && logClusters[charFrom-1] == glyphStart)
1770                 while (charFrom < ilen && logClusters[charFrom] == glyphStart)
1771                     charFrom++;
1772             if (charFrom < ilen) {
1773                 QFontEngine *fe = fontEngine(*si);
1774                 glyphStart = logClusters[charFrom];
1775                 int charEnd = from + len - 1 - pos;
1776                 if (charEnd >= ilen)
1777                     charEnd = ilen-1;
1778                 int glyphEnd = logClusters[charEnd];
1779                 while (charEnd < ilen && logClusters[charEnd] == glyphEnd)
1780                     charEnd++;
1781                 glyphEnd = (charEnd == ilen) ? si->num_glyphs : logClusters[charEnd];
1782                 if (glyphStart <= glyphEnd ) {
1783                     glyph_metrics_t m = fe->boundingBox(glyphs.mid(glyphStart, glyphEnd - glyphStart));
1784                     gm.x = qMin(gm.x, m.x + gm.xoff);
1785                     gm.y = qMin(gm.y, m.y + gm.yoff);
1786                     gm.width = qMax(gm.width, m.width+gm.xoff);
1787                     gm.height = qMax(gm.height, m.height+gm.yoff);
1788                     gm.xoff += m.xoff;
1789                     gm.yoff += m.yoff;
1790                 }
1791             }
1792         }
1793     }
1794     return gm;
1795 }
1796
1797 glyph_metrics_t QTextEngine::tightBoundingBox(int from,  int len) const
1798 {
1799     itemize();
1800
1801     glyph_metrics_t gm;
1802
1803     for (int i = 0; i < layoutData->items.size(); i++) {
1804         const QScriptItem *si = layoutData->items.constData() + i;
1805         int pos = si->position;
1806         int ilen = length(i);
1807         if (pos > from + len)
1808             break;
1809         if (pos + len > from) {
1810             if (!si->num_glyphs)
1811                 shape(i);
1812             unsigned short *logClusters = this->logClusters(si);
1813             QGlyphLayout glyphs = shapedGlyphs(si);
1814
1815             // do the simple thing for now and give the first glyph in a cluster the full width, all other ones 0.
1816             int charFrom = from - pos;
1817             if (charFrom < 0)
1818                 charFrom = 0;
1819             int glyphStart = logClusters[charFrom];
1820             if (charFrom > 0 && logClusters[charFrom-1] == glyphStart)
1821                 while (charFrom < ilen && logClusters[charFrom] == glyphStart)
1822                     charFrom++;
1823             if (charFrom < ilen) {
1824                 glyphStart = logClusters[charFrom];
1825                 int charEnd = from + len - 1 - pos;
1826                 if (charEnd >= ilen)
1827                     charEnd = ilen-1;
1828                 int glyphEnd = logClusters[charEnd];
1829                 while (charEnd < ilen && logClusters[charEnd] == glyphEnd)
1830                     charEnd++;
1831                 glyphEnd = (charEnd == ilen) ? si->num_glyphs : logClusters[charEnd];
1832                 if (glyphStart <= glyphEnd ) {
1833                     QFontEngine *fe = fontEngine(*si);
1834                     glyph_metrics_t m = fe->tightBoundingBox(glyphs.mid(glyphStart, glyphEnd - glyphStart));
1835                     gm.x = qMin(gm.x, m.x + gm.xoff);
1836                     gm.y = qMin(gm.y, m.y + gm.yoff);
1837                     gm.width = qMax(gm.width, m.width+gm.xoff);
1838                     gm.height = qMax(gm.height, m.height+gm.yoff);
1839                     gm.xoff += m.xoff;
1840                     gm.yoff += m.yoff;
1841                 }
1842             }
1843         }
1844     }
1845     return gm;
1846 }
1847
1848 QFont QTextEngine::font(const QScriptItem &si) const
1849 {
1850     QFont font = fnt;
1851     if (hasFormats()) {
1852         QTextCharFormat f = format(&si);
1853         font = f.font();
1854
1855         if (block.docHandle() && block.docHandle()->layout()) {
1856             // Make sure we get the right dpi on printers
1857             QPaintDevice *pdev = block.docHandle()->layout()->paintDevice();
1858             if (pdev)
1859                 font = QFont(font, pdev);
1860         } else {
1861             font = font.resolve(fnt);
1862         }
1863         QTextCharFormat::VerticalAlignment valign = f.verticalAlignment();
1864         if (valign == QTextCharFormat::AlignSuperScript || valign == QTextCharFormat::AlignSubScript) {
1865             if (font.pointSize() != -1)
1866                 font.setPointSize((font.pointSize() * 2) / 3);
1867             else
1868                 font.setPixelSize((font.pixelSize() * 2) / 3);
1869         }
1870     }
1871
1872     if (si.analysis.flags == QScriptAnalysis::SmallCaps)
1873         font = font.d->smallCapsFont();
1874
1875     return font;
1876 }
1877
1878 QTextEngine::FontEngineCache::FontEngineCache()
1879 {
1880     reset();
1881 }
1882
1883 //we cache the previous results of this function, as calling it numerous times with the same effective
1884 //input is common (and hard to cache at a higher level)
1885 QFontEngine *QTextEngine::fontEngine(const QScriptItem &si, QFixed *ascent, QFixed *descent, QFixed *leading) const
1886 {
1887     QFontEngine *engine = 0;
1888     QFontEngine *scaledEngine = 0;
1889     int script = si.analysis.script;
1890
1891     QFont font = fnt;
1892     if (hasFormats()) {
1893         if (feCache.prevFontEngine && feCache.prevPosition == si.position && feCache.prevLength == length(&si) && feCache.prevScript == script) {
1894             engine = feCache.prevFontEngine;
1895             scaledEngine = feCache.prevScaledFontEngine;
1896         } else {
1897             QTextCharFormat f = format(&si);
1898             font = f.font();
1899
1900             if (block.docHandle() && block.docHandle()->layout()) {
1901                 // Make sure we get the right dpi on printers
1902                 QPaintDevice *pdev = block.docHandle()->layout()->paintDevice();
1903                 if (pdev)
1904                     font = QFont(font, pdev);
1905             } else {
1906                 font = font.resolve(fnt);
1907             }
1908             engine = font.d->engineForScript(script);
1909             QTextCharFormat::VerticalAlignment valign = f.verticalAlignment();
1910             if (valign == QTextCharFormat::AlignSuperScript || valign == QTextCharFormat::AlignSubScript) {
1911                 if (font.pointSize() != -1)
1912                     font.setPointSize((font.pointSize() * 2) / 3);
1913                 else
1914                     font.setPixelSize((font.pixelSize() * 2) / 3);
1915                 scaledEngine = font.d->engineForScript(script);
1916             }
1917             if (engine)
1918                 engine->ref.ref();
1919             if (feCache.prevFontEngine)
1920                 releaseCachedFontEngine(feCache.prevFontEngine);
1921             feCache.prevFontEngine = engine;
1922
1923             if (scaledEngine)
1924                 scaledEngine->ref.ref();
1925             if (feCache.prevScaledFontEngine)
1926                 releaseCachedFontEngine(feCache.prevScaledFontEngine);
1927             feCache.prevScaledFontEngine = scaledEngine;
1928             feCache.prevScript = script;
1929             feCache.prevPosition = si.position;
1930             feCache.prevLength = length(&si);
1931         }
1932     } else {
1933         if (feCache.prevFontEngine && feCache.prevScript == script && feCache.prevPosition == -1)
1934             engine = feCache.prevFontEngine;
1935         else {
1936             engine = font.d->engineForScript(script);
1937             if (engine)
1938                 engine->ref.ref();
1939             if (feCache.prevFontEngine)
1940                 releaseCachedFontEngine(feCache.prevFontEngine);
1941             feCache.prevFontEngine = engine;
1942             feCache.prevScript = script;
1943             feCache.prevPosition = -1;
1944             feCache.prevLength = -1;
1945             feCache.prevScaledFontEngine = 0;
1946         }
1947     }
1948
1949     if (si.analysis.flags == QScriptAnalysis::SmallCaps) {
1950         QFontPrivate *p = font.d->smallCapsFontPrivate();
1951         scaledEngine = p->engineForScript(script);
1952     }
1953
1954     if (ascent) {
1955         *ascent = engine->ascent();
1956         *descent = engine->descent();
1957         *leading = engine->leading();
1958     }
1959
1960     if (scaledEngine)
1961         return scaledEngine;
1962     return engine;
1963 }
1964
1965 struct QJustificationPoint {
1966     int type;
1967     QFixed kashidaWidth;
1968     QGlyphLayout glyph;
1969     QFontEngine *fontEngine;
1970 };
1971
1972 Q_DECLARE_TYPEINFO(QJustificationPoint, Q_PRIMITIVE_TYPE);
1973
1974 static void set(QJustificationPoint *point, int type, const QGlyphLayout &glyph, QFontEngine *fe)
1975 {
1976     point->type = type;
1977     point->glyph = glyph;
1978     point->fontEngine = fe;
1979
1980     if (type >= HB_Arabic_Normal) {
1981         QChar ch(0x640); // Kashida character
1982         QGlyphLayoutArray<8> glyphs;
1983         int nglyphs = 7;
1984         fe->stringToCMap(&ch, 1, &glyphs, &nglyphs, 0);
1985         if (glyphs.glyphs[0] && glyphs.advances_x[0] != 0) {
1986             point->kashidaWidth = glyphs.advances_x[0];
1987         } else {
1988             point->type = HB_NoJustification;
1989             point->kashidaWidth = 0;
1990         }
1991     }
1992 }
1993
1994
1995 void QTextEngine::justify(const QScriptLine &line)
1996 {
1997 //     qDebug("justify: line.gridfitted = %d, line.justified=%d", line.gridfitted, line.justified);
1998     if (line.gridfitted && line.justified)
1999         return;
2000
2001     if (!line.gridfitted) {
2002         // redo layout in device metrics, then adjust
2003         const_cast<QScriptLine &>(line).gridfitted = true;
2004     }
2005
2006     if ((option.alignment() & Qt::AlignHorizontal_Mask) != Qt::AlignJustify)
2007         return;
2008
2009     itemize();
2010
2011     if (!forceJustification) {
2012         int end = line.from + (int)line.length;
2013         if (end == layoutData->string.length())
2014             return; // no justification at end of paragraph
2015         if (end && layoutData->items[findItem(end-1)].analysis.flags == QScriptAnalysis::LineOrParagraphSeparator)
2016             return; // no justification at the end of an explicitly separated line
2017     }
2018
2019     // justify line
2020     int maxJustify = 0;
2021
2022     // don't include trailing white spaces when doing justification
2023     int line_length = line.length;
2024     const HB_CharAttributes *a = attributes();
2025     if (! a)
2026         return;
2027     a += line.from;
2028     while (line_length && a[line_length-1].whiteSpace)
2029         --line_length;
2030     // subtract one char more, as we can't justfy after the last character
2031     --line_length;
2032
2033     if (!line_length)
2034         return;
2035
2036     int firstItem = findItem(line.from);
2037     int nItems = findItem(line.from + line_length - 1) - firstItem + 1;
2038
2039     QVarLengthArray<QJustificationPoint> justificationPoints;
2040     int nPoints = 0;
2041 //     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());
2042     QFixed minKashida = 0x100000;
2043
2044     // we need to do all shaping before we go into the next loop, as we there
2045     // store pointers to the glyph data that could get reallocated by the shaping
2046     // process.
2047     for (int i = 0; i < nItems; ++i) {
2048         QScriptItem &si = layoutData->items[firstItem + i];
2049         if (!si.num_glyphs)
2050             shape(firstItem + i);
2051     }
2052
2053     for (int i = 0; i < nItems; ++i) {
2054         QScriptItem &si = layoutData->items[firstItem + i];
2055
2056         int kashida_type = HB_Arabic_Normal;
2057         int kashida_pos = -1;
2058
2059         int start = qMax(line.from - si.position, 0);
2060         int end = qMin(line.from + line_length - (int)si.position, length(firstItem+i));
2061
2062         unsigned short *log_clusters = logClusters(&si);
2063
2064         int gs = log_clusters[start];
2065         int ge = (end == length(firstItem+i) ? si.num_glyphs : log_clusters[end]);
2066
2067         const QGlyphLayout g = shapedGlyphs(&si);
2068
2069         for (int i = gs; i < ge; ++i) {
2070             g.justifications[i].type = QGlyphJustification::JustifyNone;
2071             g.justifications[i].nKashidas = 0;
2072             g.justifications[i].space_18d6 = 0;
2073
2074             justificationPoints.resize(nPoints+3);
2075             int justification = g.attributes[i].justification;
2076
2077             switch(justification) {
2078             case HB_NoJustification:
2079                 break;
2080             case HB_Space          :
2081                 // fall through
2082             case HB_Arabic_Space   :
2083                 if (kashida_pos >= 0) {
2084 //                     qDebug("kashida position at %d in word", kashida_pos);
2085                     set(&justificationPoints[nPoints], kashida_type, g.mid(kashida_pos), fontEngine(si));
2086                     if (justificationPoints[nPoints].kashidaWidth > 0) {
2087                         minKashida = qMin(minKashida, justificationPoints[nPoints].kashidaWidth);
2088                         maxJustify = qMax(maxJustify, justificationPoints[nPoints].type);
2089                         ++nPoints;
2090                     }
2091                 }
2092                 kashida_pos = -1;
2093                 kashida_type = HB_Arabic_Normal;
2094                 // fall through
2095             case HB_Character      :
2096                 set(&justificationPoints[nPoints++], justification, g.mid(i), fontEngine(si));
2097                 maxJustify = qMax(maxJustify, justification);
2098                 break;
2099             case HB_Arabic_Normal  :
2100             case HB_Arabic_Waw     :
2101             case HB_Arabic_BaRa    :
2102             case HB_Arabic_Alef    :
2103             case HB_Arabic_HaaDal  :
2104             case HB_Arabic_Seen    :
2105             case HB_Arabic_Kashida :
2106                 if (justification >= kashida_type) {
2107                     kashida_pos = i;
2108                     kashida_type = justification;
2109                 }
2110             }
2111         }
2112         if (kashida_pos >= 0) {
2113             set(&justificationPoints[nPoints], kashida_type, g.mid(kashida_pos), fontEngine(si));
2114             if (justificationPoints[nPoints].kashidaWidth > 0) {
2115                 minKashida = qMin(minKashida, justificationPoints[nPoints].kashidaWidth);
2116                 maxJustify = qMax(maxJustify, justificationPoints[nPoints].type);
2117                 ++nPoints;
2118             }
2119         }
2120     }
2121
2122     QFixed leading = leadingSpaceWidth(line);
2123     QFixed need = line.width - line.textWidth - leading;
2124     if (need < 0) {
2125         // line overflows already!
2126         const_cast<QScriptLine &>(line).justified = true;
2127         return;
2128     }
2129
2130 //     qDebug("doing justification: textWidth=%x, requested=%x, maxJustify=%d", line.textWidth.value(), line.width.value(), maxJustify);
2131 //     qDebug("     minKashida=%f, need=%f", minKashida.toReal(), need.toReal());
2132
2133     // distribute in priority order
2134     if (maxJustify >= HB_Arabic_Normal) {
2135         while (need >= minKashida) {
2136             for (int type = maxJustify; need >= minKashida && type >= HB_Arabic_Normal; --type) {
2137                 for (int i = 0; need >= minKashida && i < nPoints; ++i) {
2138                     if (justificationPoints[i].type == type && justificationPoints[i].kashidaWidth <= need) {
2139                         justificationPoints[i].glyph.justifications->nKashidas++;
2140                         // ############
2141                         justificationPoints[i].glyph.justifications->space_18d6 += justificationPoints[i].kashidaWidth.value();
2142                         need -= justificationPoints[i].kashidaWidth;
2143 //                         qDebug("adding kashida type %d with width %x, neednow %x", type, justificationPoints[i].kashidaWidth, need.value());
2144                     }
2145                 }
2146             }
2147         }
2148     }
2149     Q_ASSERT(need >= 0);
2150     if (!need)
2151         goto end;
2152
2153     maxJustify = qMin(maxJustify, (int)HB_Space);
2154     for (int type = maxJustify; need != 0 && type > 0; --type) {
2155         int n = 0;
2156         for (int i = 0; i < nPoints; ++i) {
2157             if (justificationPoints[i].type == type)
2158                 ++n;
2159         }
2160 //          qDebug("number of points for justification type %d: %d", type, n);
2161
2162
2163         if (!n)
2164             continue;
2165
2166         for (int i = 0; i < nPoints; ++i) {
2167             if (justificationPoints[i].type == type) {
2168                 QFixed add = need/n;
2169 //                  qDebug("adding %x to glyph %x", add.value(), justificationPoints[i].glyph->glyph);
2170                 justificationPoints[i].glyph.justifications[0].space_18d6 = add.value();
2171                 need -= add;
2172                 --n;
2173             }
2174         }
2175
2176         Q_ASSERT(!need);
2177     }
2178  end:
2179     const_cast<QScriptLine &>(line).justified = true;
2180 }
2181
2182 void QScriptLine::setDefaultHeight(QTextEngine *eng)
2183 {
2184     QFont f;
2185     QFontEngine *e;
2186
2187     if (eng->block.docHandle() && eng->block.docHandle()->layout()) {
2188         f = eng->block.charFormat().font();
2189         // Make sure we get the right dpi on printers
2190         QPaintDevice *pdev = eng->block.docHandle()->layout()->paintDevice();
2191         if (pdev)
2192             f = QFont(f, pdev);
2193         e = f.d->engineForScript(QUnicodeTables::Common);
2194     } else {
2195         e = eng->fnt.d->engineForScript(QUnicodeTables::Common);
2196     }
2197
2198     QFixed other_ascent = e->ascent();
2199     QFixed other_descent = e->descent();
2200     QFixed other_leading = e->leading();
2201     leading = qMax(leading + ascent, other_leading + other_ascent) - qMax(ascent, other_ascent);
2202     ascent = qMax(ascent, other_ascent);
2203     descent = qMax(descent, other_descent);
2204 }
2205
2206 QTextEngine::LayoutData::LayoutData()
2207 {
2208     memory = 0;
2209     allocated = 0;
2210     memory_on_stack = false;
2211     used = 0;
2212     hasBidi = false;
2213     layoutState = LayoutEmpty;
2214     haveCharAttributes = false;
2215     logClustersPtr = 0;
2216     available_glyphs = 0;
2217 }
2218
2219 QTextEngine::LayoutData::LayoutData(const QString &str, void **stack_memory, int _allocated)
2220     : string(str)
2221 {
2222     allocated = _allocated;
2223
2224     int space_charAttributes = sizeof(HB_CharAttributes)*string.length()/sizeof(void*) + 1;
2225     int space_logClusters = sizeof(unsigned short)*string.length()/sizeof(void*) + 1;
2226     available_glyphs = ((int)allocated - space_charAttributes - space_logClusters)*(int)sizeof(void*)/(int)QGlyphLayout::spaceNeededForGlyphLayout(1);
2227
2228     if (available_glyphs < str.length()) {
2229         // need to allocate on the heap
2230         allocated = 0;
2231
2232         memory_on_stack = false;
2233         memory = 0;
2234         logClustersPtr = 0;
2235     } else {
2236         memory_on_stack = true;
2237         memory = stack_memory;
2238         logClustersPtr = (unsigned short *)(memory + space_charAttributes);
2239
2240         void *m = memory + space_charAttributes + space_logClusters;
2241         glyphLayout = QGlyphLayout(reinterpret_cast<char *>(m), str.length());
2242         glyphLayout.clear();
2243         memset(memory, 0, space_charAttributes*sizeof(void *));
2244     }
2245     used = 0;
2246     hasBidi = false;
2247     layoutState = LayoutEmpty;
2248     haveCharAttributes = false;
2249 }
2250
2251 QTextEngine::LayoutData::~LayoutData()
2252 {
2253     if (!memory_on_stack)
2254         free(memory);
2255     memory = 0;
2256 }
2257
2258 bool QTextEngine::LayoutData::reallocate(int totalGlyphs)
2259 {
2260     Q_ASSERT(totalGlyphs >= glyphLayout.numGlyphs);
2261     if (memory_on_stack && available_glyphs >= totalGlyphs) {
2262         glyphLayout.grow(glyphLayout.data(), totalGlyphs);
2263         return true;
2264     }
2265
2266     int space_charAttributes = sizeof(HB_CharAttributes)*string.length()/sizeof(void*) + 1;
2267     int space_logClusters = sizeof(unsigned short)*string.length()/sizeof(void*) + 1;
2268     int space_glyphs = QGlyphLayout::spaceNeededForGlyphLayout(totalGlyphs)/sizeof(void*) + 2;
2269
2270     int newAllocated = space_charAttributes + space_glyphs + space_logClusters;
2271     // These values can be negative if the length of string/glyphs causes overflow,
2272     // we can't layout such a long string all at once, so return false here to
2273     // indicate there is a failure
2274     if (space_charAttributes < 0 || space_logClusters < 0 || space_glyphs < 0 || newAllocated < allocated) {
2275         layoutState = LayoutFailed;
2276         return false;
2277     }
2278
2279     void **newMem = memory;
2280     newMem = (void **)::realloc(memory_on_stack ? 0 : memory, newAllocated*sizeof(void *));
2281     if (!newMem) {
2282         layoutState = LayoutFailed;
2283         return false;
2284     }
2285     if (memory_on_stack)
2286         memcpy(newMem, memory, allocated*sizeof(void *));
2287     memory = newMem;
2288     memory_on_stack = false;
2289
2290     void **m = memory;
2291     m += space_charAttributes;
2292     logClustersPtr = (unsigned short *) m;
2293     m += space_logClusters;
2294
2295     const int space_preGlyphLayout = space_charAttributes + space_logClusters;
2296     if (allocated < space_preGlyphLayout)
2297         memset(memory + allocated, 0, (space_preGlyphLayout - allocated)*sizeof(void *));
2298
2299     glyphLayout.grow(reinterpret_cast<char *>(m), totalGlyphs);
2300
2301     allocated = newAllocated;
2302     return true;
2303 }
2304
2305 // grow to the new size, copying the existing data to the new layout
2306 void QGlyphLayout::grow(char *address, int totalGlyphs)
2307 {
2308     QGlyphLayout oldLayout(address, numGlyphs);
2309     QGlyphLayout newLayout(address, totalGlyphs);
2310
2311     if (numGlyphs) {
2312         // move the existing data
2313         memmove(newLayout.attributes, oldLayout.attributes, numGlyphs * sizeof(HB_GlyphAttributes));
2314         memmove(newLayout.justifications, oldLayout.justifications, numGlyphs * sizeof(QGlyphJustification));
2315         memmove(newLayout.advances_y, oldLayout.advances_y, numGlyphs * sizeof(QFixed));
2316         memmove(newLayout.advances_x, oldLayout.advances_x, numGlyphs * sizeof(QFixed));
2317         memmove(newLayout.glyphs, oldLayout.glyphs, numGlyphs * sizeof(HB_Glyph));
2318     }
2319
2320     // clear the new data
2321     newLayout.clear(numGlyphs);
2322
2323     *this = newLayout;
2324 }
2325
2326 void QTextEngine::freeMemory()
2327 {
2328     if (!stackEngine) {
2329         delete layoutData;
2330         layoutData = 0;
2331     } else {
2332         layoutData->used = 0;
2333         layoutData->hasBidi = false;
2334         layoutData->layoutState = LayoutEmpty;
2335         layoutData->haveCharAttributes = false;
2336     }
2337     for (int i = 0; i < lines.size(); ++i) {
2338         lines[i].justified = 0;
2339         lines[i].gridfitted = 0;
2340     }
2341 }
2342
2343 int QTextEngine::formatIndex(const QScriptItem *si) const
2344 {
2345     if (specialData && !specialData->resolvedFormatIndices.isEmpty())
2346         return specialData->resolvedFormatIndices.at(si - &layoutData->items[0]);
2347     QTextDocumentPrivate *p = block.docHandle();
2348     if (!p)
2349         return -1;
2350     int pos = si->position;
2351     if (specialData && si->position >= specialData->preeditPosition) {
2352         if (si->position < specialData->preeditPosition + specialData->preeditText.length())
2353             pos = qMax(specialData->preeditPosition - 1, 0);
2354         else
2355             pos -= specialData->preeditText.length();
2356     }
2357     QTextDocumentPrivate::FragmentIterator it = p->find(block.position() + pos);
2358     return it.value()->format;
2359 }
2360
2361
2362 QTextCharFormat QTextEngine::format(const QScriptItem *si) const
2363 {
2364     QTextCharFormat format;
2365     const QTextFormatCollection *formats = 0;
2366     if (block.docHandle()) {
2367         formats = this->formats();
2368         format = formats->charFormat(formatIndex(si));
2369     }
2370     if (specialData && specialData->resolvedFormatIndices.isEmpty()) {
2371         int end = si->position + length(si);
2372         for (int i = 0; i < specialData->addFormats.size(); ++i) {
2373             const QTextLayout::FormatRange &r = specialData->addFormats.at(i);
2374             if (r.start <= si->position && r.start + r.length >= end) {
2375                 if (!specialData->addFormatIndices.isEmpty())
2376                     format.merge(formats->format(specialData->addFormatIndices.at(i)));
2377                 else
2378                     format.merge(r.format);
2379             }
2380         }
2381     }
2382     return format;
2383 }
2384
2385 void QTextEngine::addRequiredBoundaries() const
2386 {
2387     if (specialData) {
2388         for (int i = 0; i < specialData->addFormats.size(); ++i) {
2389             const QTextLayout::FormatRange &r = specialData->addFormats.at(i);
2390             setBoundary(r.start);
2391             setBoundary(r.start + r.length);
2392             //qDebug("adding boundaries %d %d", r.start, r.start+r.length);
2393         }
2394     }
2395 }
2396
2397 bool QTextEngine::atWordSeparator(int position) const
2398 {
2399     const QChar c = layoutData->string.at(position);
2400     switch (c.toLatin1()) {
2401     case '.':
2402     case ',':
2403     case '?':
2404     case '!':
2405     case '@':
2406     case '#':
2407     case '$':
2408     case ':':
2409     case ';':
2410     case '-':
2411     case '<':
2412     case '>':
2413     case '[':
2414     case ']':
2415     case '(':
2416     case ')':
2417     case '{':
2418     case '}':
2419     case '=':
2420     case '/':
2421     case '+':
2422     case '%':
2423     case '&':
2424     case '^':
2425     case '*':
2426     case '\'':
2427     case '"':
2428     case '`':
2429     case '~':
2430     case '|':
2431         return true;
2432     default:
2433         return false;
2434     }
2435 }
2436
2437 bool QTextEngine::atSpace(int position) const
2438 {
2439     const QChar c = layoutData->string.at(position);
2440
2441     return c == QLatin1Char(' ')
2442         || c == QChar::Nbsp
2443         || c == QChar::LineSeparator
2444         || c == QLatin1Char('\t')
2445         ;
2446 }
2447
2448
2449 void QTextEngine::indexAdditionalFormats()
2450 {
2451     if (!block.docHandle())
2452         return;
2453
2454     specialData->addFormatIndices.resize(specialData->addFormats.count());
2455     QTextFormatCollection * const formats = this->formats();
2456
2457     for (int i = 0; i < specialData->addFormats.count(); ++i) {
2458         specialData->addFormatIndices[i] = formats->indexForFormat(specialData->addFormats.at(i).format);
2459         specialData->addFormats[i].format = QTextCharFormat();
2460     }
2461 }
2462
2463 /* These two helper functions are used to determine whether we need to insert a ZWJ character
2464    between the text that gets truncated and the ellipsis. This is important to get
2465    correctly shaped results for arabic text.
2466 */
2467 static inline bool nextCharJoins(const QString &string, int pos)
2468 {
2469     while (pos < string.length() && string.at(pos).category() == QChar::Mark_NonSpacing)
2470         ++pos;
2471     if (pos == string.length())
2472         return false;
2473     return string.at(pos).joining() != QChar::OtherJoining;
2474 }
2475
2476 static inline bool prevCharJoins(const QString &string, int pos)
2477 {
2478     while (pos > 0 && string.at(pos - 1).category() == QChar::Mark_NonSpacing)
2479         --pos;
2480     if (pos == 0)
2481         return false;
2482     QChar::Joining joining = string.at(pos - 1).joining();
2483     return (joining == QChar::Dual || joining == QChar::Center);
2484 }
2485
2486 QString QTextEngine::elidedText(Qt::TextElideMode mode, const QFixed &width, int flags) const
2487 {
2488 //    qDebug() << "elidedText; available width" << width.toReal() << "text width:" << this->width(0, layoutData->string.length()).toReal();
2489
2490     if (flags & Qt::TextShowMnemonic) {
2491         itemize();
2492         HB_CharAttributes *attributes = const_cast<HB_CharAttributes *>(this->attributes());
2493         if (!attributes)
2494             return QString();
2495         for (int i = 0; i < layoutData->items.size(); ++i) {
2496             QScriptItem &si = layoutData->items[i];
2497             if (!si.num_glyphs)
2498                 shape(i);
2499
2500             unsigned short *logClusters = this->logClusters(&si);
2501             QGlyphLayout glyphs = shapedGlyphs(&si);
2502
2503             const int end = si.position + length(&si);
2504             for (int i = si.position; i < end - 1; ++i) {
2505                 if (layoutData->string.at(i) == QLatin1Char('&')) {
2506                     const int gp = logClusters[i - si.position];
2507                     glyphs.attributes[gp].dontPrint = true;
2508                     attributes[i + 1].charStop = false;
2509                     attributes[i + 1].whiteSpace = false;
2510                     attributes[i + 1].lineBreakType = HB_NoBreak;
2511                     if (layoutData->string.at(i + 1) == QLatin1Char('&'))
2512                         ++i;
2513                 }
2514             }
2515         }
2516     }
2517
2518     validate();
2519
2520     if (mode == Qt::ElideNone
2521         || this->width(0, layoutData->string.length()) <= width
2522         || layoutData->string.length() <= 1)
2523         return layoutData->string;
2524
2525     QFixed ellipsisWidth;
2526     QString ellipsisText;
2527     {
2528         QChar ellipsisChar(0x2026);
2529
2530         QFontEngine *fe = fnt.d->engineForScript(QUnicodeTables::Common);
2531
2532         QGlyphLayoutArray<1> ellipsisGlyph;
2533         {
2534             QFontEngine *feForEllipsis = (fe->type() == QFontEngine::Multi)
2535                 ? static_cast<QFontEngineMulti *>(fe)->engine(0)
2536                 : fe;
2537
2538             if (feForEllipsis->type() == QFontEngine::Mac)
2539                 feForEllipsis = fe;
2540
2541             // the lookup can be really slow when we use XLFD fonts
2542             if (feForEllipsis->type() != QFontEngine::XLFD
2543                 && feForEllipsis->canRender(&ellipsisChar, 1)) {
2544                     int nGlyphs = 1;
2545                     feForEllipsis->stringToCMap(&ellipsisChar, 1, &ellipsisGlyph, &nGlyphs, 0);
2546                 }
2547         }
2548
2549         if (ellipsisGlyph.glyphs[0]) {
2550             ellipsisWidth = ellipsisGlyph.advances_x[0];
2551             ellipsisText = ellipsisChar;
2552         } else {
2553             QString dotDotDot(QLatin1String("..."));
2554
2555             QGlyphLayoutArray<3> glyphs;
2556             int nGlyphs = 3;
2557             if (!fe->stringToCMap(dotDotDot.constData(), 3, &glyphs, &nGlyphs, 0))
2558                 // should never happen...
2559                 return layoutData->string;
2560             for (int i = 0; i < nGlyphs; ++i)
2561                 ellipsisWidth += glyphs.advances_x[i];
2562             ellipsisText = dotDotDot;
2563         }
2564     }
2565
2566     const QFixed availableWidth = width - ellipsisWidth;
2567     if (availableWidth < 0)
2568         return QString();
2569
2570     const HB_CharAttributes *attributes = this->attributes();
2571     if (!attributes)
2572         return QString();
2573
2574     if (mode == Qt::ElideRight) {
2575         QFixed currentWidth;
2576         int pos;
2577         int nextBreak = 0;
2578
2579         do {
2580             pos = nextBreak;
2581
2582             ++nextBreak;
2583             while (nextBreak < layoutData->string.length() && !attributes[nextBreak].charStop)
2584                 ++nextBreak;
2585
2586             currentWidth += this->width(pos, nextBreak - pos);
2587         } while (nextBreak < layoutData->string.length()
2588                  && currentWidth < availableWidth);
2589
2590         if (nextCharJoins(layoutData->string, pos))
2591             ellipsisText.prepend(QChar(0x200d) /* ZWJ */);
2592
2593         return layoutData->string.left(pos) + ellipsisText;
2594     } else if (mode == Qt::ElideLeft) {
2595         QFixed currentWidth;
2596         int pos;
2597         int nextBreak = layoutData->string.length();
2598
2599         do {
2600             pos = nextBreak;
2601
2602             --nextBreak;
2603             while (nextBreak > 0 && !attributes[nextBreak].charStop)
2604                 --nextBreak;
2605
2606             currentWidth += this->width(nextBreak, pos - nextBreak);
2607         } while (nextBreak > 0
2608                  && currentWidth < availableWidth);
2609
2610         if (prevCharJoins(layoutData->string, pos))
2611             ellipsisText.append(QChar(0x200d) /* ZWJ */);
2612
2613         return ellipsisText + layoutData->string.mid(pos);
2614     } else if (mode == Qt::ElideMiddle) {
2615         QFixed leftWidth;
2616         QFixed rightWidth;
2617
2618         int leftPos = 0;
2619         int nextLeftBreak = 0;
2620
2621         int rightPos = layoutData->string.length();
2622         int nextRightBreak = layoutData->string.length();
2623
2624         do {
2625             leftPos = nextLeftBreak;
2626             rightPos = nextRightBreak;
2627
2628             ++nextLeftBreak;
2629             while (nextLeftBreak < layoutData->string.length() && !attributes[nextLeftBreak].charStop)
2630                 ++nextLeftBreak;
2631
2632             --nextRightBreak;
2633             while (nextRightBreak > 0 && !attributes[nextRightBreak].charStop)
2634                 --nextRightBreak;
2635
2636             leftWidth += this->width(leftPos, nextLeftBreak - leftPos);
2637             rightWidth += this->width(nextRightBreak, rightPos - nextRightBreak);
2638         } while (nextLeftBreak < layoutData->string.length()
2639                  && nextRightBreak > 0
2640                  && leftWidth + rightWidth < availableWidth);
2641
2642         if (nextCharJoins(layoutData->string, leftPos))
2643             ellipsisText.prepend(QChar(0x200d) /* ZWJ */);
2644         if (prevCharJoins(layoutData->string, rightPos))
2645             ellipsisText.append(QChar(0x200d) /* ZWJ */);
2646
2647         return layoutData->string.left(leftPos) + ellipsisText + layoutData->string.mid(rightPos);
2648     }
2649
2650     return layoutData->string;
2651 }
2652
2653 namespace {
2654 struct QScriptItemComparator {
2655     bool operator()(const QScriptItem &a, const QScriptItem &b) { return a.position < b.position; }
2656     bool operator()(int p, const QScriptItem &b) { return p < b.position; }
2657     //bool operator()(const QScriptItem &a, int p) { return a.position < p; }
2658 };
2659 }
2660
2661 void QTextEngine::setBoundary(int strPos) const
2662 {
2663     if (strPos <= 0 || strPos >= layoutData->string.length())
2664         return;
2665
2666     const QScriptItem* it = qUpperBound(layoutData->items.constBegin(), layoutData->items.constEnd(),
2667                                         strPos, QScriptItemComparator());
2668     Q_ASSERT(it > layoutData->items.constBegin());
2669     --it;
2670     if (it->position == strPos) {
2671         // already a split at the requested position
2672         return;
2673     }
2674     splitItem(it - layoutData->items.constBegin(), strPos - it->position);
2675 }
2676
2677 void QTextEngine::splitItem(int item, int pos) const
2678 {
2679     if (pos <= 0)
2680         return;
2681
2682     layoutData->items.insert(item + 1, layoutData->items[item]);
2683     QScriptItem &oldItem = layoutData->items[item];
2684     QScriptItem &newItem = layoutData->items[item+1];
2685     newItem.position += pos;
2686
2687     if (oldItem.num_glyphs) {
2688         // already shaped, break glyphs aswell
2689         int breakGlyph = logClusters(&oldItem)[pos];
2690
2691         newItem.num_glyphs = oldItem.num_glyphs - breakGlyph;
2692         oldItem.num_glyphs = breakGlyph;
2693         newItem.glyph_data_offset = oldItem.glyph_data_offset + breakGlyph;
2694
2695         for (int i = 0; i < newItem.num_glyphs; i++)
2696             logClusters(&newItem)[i] -= breakGlyph;
2697
2698         QFixed w = 0;
2699         const QGlyphLayout g = shapedGlyphs(&oldItem);
2700         for(int j = 0; j < breakGlyph; ++j)
2701             w += g.advances_x[j] * !g.attributes[j].dontPrint;
2702
2703         newItem.width = oldItem.width - w;
2704         oldItem.width = w;
2705     }
2706
2707 //     qDebug("split at position %d itempos=%d", pos, item);
2708 }
2709
2710 QFixed QTextEngine::calculateTabWidth(int item, QFixed x) const
2711 {
2712     const QScriptItem &si = layoutData->items[item];
2713
2714     QFixed dpiScale = 1;
2715     if (block.docHandle() && block.docHandle()->layout()) {
2716         QPaintDevice *pdev = block.docHandle()->layout()->paintDevice();
2717         if (pdev)
2718             dpiScale = QFixed::fromReal(pdev->logicalDpiY() / qreal(qt_defaultDpiY()));
2719     } else {
2720         dpiScale = QFixed::fromReal(fnt.d->dpi / qreal(qt_defaultDpiY()));
2721     }
2722
2723     QList<QTextOption::Tab> tabArray = option.tabs();
2724     if (!tabArray.isEmpty()) {
2725         if (isRightToLeft()) { // rebase the tabArray positions.
2726             QList<QTextOption::Tab> newTabs;
2727             QList<QTextOption::Tab>::Iterator iter = tabArray.begin();
2728             while(iter != tabArray.end()) {
2729                 QTextOption::Tab tab = *iter;
2730                 if (tab.type == QTextOption::LeftTab)
2731                     tab.type = QTextOption::RightTab;
2732                 else if (tab.type == QTextOption::RightTab)
2733                     tab.type = QTextOption::LeftTab;
2734                 newTabs << tab;
2735                 ++iter;
2736             }
2737             tabArray = newTabs;
2738         }
2739         for (int i = 0; i < tabArray.size(); ++i) {
2740             QFixed tab = QFixed::fromReal(tabArray[i].position) * dpiScale;
2741             if (tab > x) {  // this is the tab we need.
2742                 QTextOption::Tab tabSpec = tabArray[i];
2743                 int tabSectionEnd = layoutData->string.count();
2744                 if (tabSpec.type == QTextOption::RightTab || tabSpec.type == QTextOption::CenterTab) {
2745                     // find next tab to calculate the width required.
2746                     tab = QFixed::fromReal(tabSpec.position);
2747                     for (int i=item + 1; i < layoutData->items.count(); i++) {
2748                         const QScriptItem &item = layoutData->items[i];
2749                         if (item.analysis.flags == QScriptAnalysis::TabOrObject) { // found it.
2750                             tabSectionEnd = item.position;
2751                             break;
2752                         }
2753                     }
2754                 }
2755                 else if (tabSpec.type == QTextOption::DelimiterTab)
2756                     // find delimitor character to calculate the width required
2757                     tabSectionEnd = qMax(si.position, layoutData->string.indexOf(tabSpec.delimiter, si.position) + 1);
2758
2759                 if (tabSectionEnd > si.position) {
2760                     QFixed length;
2761                     // Calculate the length of text between this tab and the tabSectionEnd
2762                     for (int i=item; i < layoutData->items.count(); i++) {
2763                         QScriptItem &item = layoutData->items[i];
2764                         if (item.position > tabSectionEnd || item.position <= si.position)
2765                             continue;
2766                         shape(i); // first, lets make sure relevant text is already shaped
2767                         QGlyphLayout glyphs = this->shapedGlyphs(&item);
2768                         const int end = qMin(item.position + item.num_glyphs, tabSectionEnd) - item.position;
2769                         for (int i=0; i < end; i++)
2770                             length += glyphs.advances_x[i] * !glyphs.attributes[i].dontPrint;
2771                         if (end + item.position == tabSectionEnd && tabSpec.type == QTextOption::DelimiterTab) // remove half of matching char
2772                             length -= glyphs.advances_x[end] / 2 * !glyphs.attributes[end].dontPrint;
2773                     }
2774
2775                     switch (tabSpec.type) {
2776                     case QTextOption::CenterTab:
2777                         length /= 2;
2778                         // fall through
2779                     case QTextOption::DelimiterTab:
2780                         // fall through
2781                     case QTextOption::RightTab:
2782                         tab = QFixed::fromReal(tabSpec.position) * dpiScale - length;
2783                         if (tab < 0) // default to tab taking no space
2784                             return QFixed();
2785                         break;
2786                     case QTextOption::LeftTab:
2787                         break;
2788                     }
2789                 }
2790                 return tab - x;
2791             }
2792         }
2793     }
2794     QFixed tab = QFixed::fromReal(option.tabStop());
2795     if (tab <= 0)
2796         tab = 80; // default
2797     tab *= dpiScale;
2798     QFixed nextTabPos = ((x / tab).truncate() + 1) * tab;
2799     QFixed tabWidth = nextTabPos - x;
2800
2801     return tabWidth;
2802 }
2803
2804 void QTextEngine::resolveAdditionalFormats() const
2805 {
2806     if (!specialData || specialData->addFormats.isEmpty()
2807         || !block.docHandle()
2808         || !specialData->resolvedFormatIndices.isEmpty())
2809         return;
2810
2811     QTextFormatCollection *collection = this->formats();
2812
2813     specialData->resolvedFormatIndices.clear();
2814     QVector<int> indices(layoutData->items.count());
2815     for (int i = 0; i < layoutData->items.count(); ++i) {
2816         QTextCharFormat f = format(&layoutData->items.at(i));
2817         indices[i] = collection->indexForFormat(f);
2818     }
2819     specialData->resolvedFormatIndices = indices;
2820 }
2821
2822 QFixed QTextEngine::leadingSpaceWidth(const QScriptLine &line)
2823 {
2824     if (!line.hasTrailingSpaces
2825         || (option.flags() & QTextOption::IncludeTrailingSpaces)
2826         || !isRightToLeft())
2827         return QFixed();
2828
2829     int pos = line.length;
2830     const HB_CharAttributes *attributes = this->attributes();
2831     if (!attributes)
2832         return QFixed();
2833     while (pos > 0 && attributes[line.from + pos - 1].whiteSpace)
2834         --pos;
2835     return width(line.from + pos, line.length - pos);
2836 }
2837
2838 QFixed QTextEngine::alignLine(const QScriptLine &line)
2839 {
2840     QFixed x = 0;
2841     justify(line);
2842     // if width is QFIXED_MAX that means we used setNumColumns() and that implicitly makes this line left aligned.
2843     if (!line.justified && line.width != QFIXED_MAX) {
2844         int align = option.alignment();
2845         if (align & Qt::AlignLeft)
2846             x -= leadingSpaceWidth(line);
2847         if (align & Qt::AlignJustify && isRightToLeft())
2848             align = Qt::AlignRight;
2849         if (align & Qt::AlignRight)
2850             x = line.width - (line.textAdvance + leadingSpaceWidth(line));
2851         else if (align & Qt::AlignHCenter)
2852             x = (line.width - line.textAdvance)/2 - leadingSpaceWidth(line);
2853     }
2854     return x;
2855 }
2856
2857 QFixed QTextEngine::offsetInLigature(const QScriptItem *si, int pos, int max, int glyph_pos)
2858 {
2859     unsigned short *logClusters = this->logClusters(si);
2860     const QGlyphLayout &glyphs = shapedGlyphs(si);
2861
2862     int offsetInCluster = 0;
2863     for (int i = pos - 1; i >= 0; i--) {
2864         if (logClusters[i] == glyph_pos)
2865             offsetInCluster++;
2866         else
2867             break;
2868     }
2869
2870     // in the case that the offset is inside a (multi-character) glyph,
2871     // interpolate the position.
2872     if (offsetInCluster > 0) {
2873         int clusterLength = 0;
2874         for (int i = pos - offsetInCluster; i < max; i++) {
2875             if (logClusters[i] == glyph_pos)
2876                 clusterLength++;
2877             else
2878                 break;
2879         }
2880         if (clusterLength)
2881             return glyphs.advances_x[glyph_pos] * offsetInCluster / clusterLength;
2882     }
2883
2884     return 0;
2885 }
2886
2887 // Scan in logClusters[from..to-1] for glyph_pos
2888 int QTextEngine::getClusterLength(unsigned short *logClusters,
2889                                   const HB_CharAttributes *attributes,
2890                                   int from, int to, int glyph_pos, int *start)
2891 {
2892     int clusterLength = 0;
2893     for (int i = from; i < to; i++) {
2894         if (logClusters[i] == glyph_pos && attributes[i].charStop) {
2895             if (*start < 0)
2896                 *start = i;
2897             clusterLength++;
2898         }
2899         else if (clusterLength)
2900             break;
2901     }
2902     return clusterLength;
2903 }
2904
2905 int QTextEngine::positionInLigature(const QScriptItem *si, int end,
2906                                     QFixed x, QFixed edge, int glyph_pos,
2907                                     bool cursorOnCharacter)
2908 {
2909     unsigned short *logClusters = this->logClusters(si);
2910     int clusterStart = -1;
2911     int clusterLength = 0;
2912
2913     if (si->analysis.script != QUnicodeTables::Common &&
2914         si->analysis.script != QUnicodeTables::Greek) {
2915         if (glyph_pos == -1)
2916             return si->position + end;
2917         else {
2918             int i;
2919             for (i = 0; i < end; i++)
2920                 if (logClusters[i] == glyph_pos)
2921                     break;
2922             return si->position + i;
2923         }
2924     }
2925
2926     if (glyph_pos == -1 && end > 0)
2927         glyph_pos = logClusters[end - 1];
2928     else {
2929         if (x <= edge)
2930             glyph_pos--;
2931     }
2932
2933     const HB_CharAttributes *attrs = attributes();
2934     logClusters = this->logClusters(si);
2935     clusterLength = getClusterLength(logClusters, attrs, 0, end, glyph_pos, &clusterStart);
2936
2937     if (clusterLength) {
2938         const QGlyphLayout &glyphs = shapedGlyphs(si);
2939         QFixed glyphWidth = glyphs.effectiveAdvance(glyph_pos);
2940         // the approximate width of each individual element of the ligature
2941         QFixed perItemWidth = glyphWidth / clusterLength;
2942         if (perItemWidth <= 0)
2943             return si->position + clusterStart;
2944         QFixed left = x > edge ? edge : edge - glyphWidth;
2945         int n = ((x - left) / perItemWidth).floor().toInt();
2946         QFixed dist = x - left - n * perItemWidth;
2947         int closestItem = dist > (perItemWidth / 2) ? n + 1 : n;
2948         if (cursorOnCharacter && closestItem > 0)
2949             closestItem--;
2950         int pos = si->position + clusterStart + closestItem;
2951         // Jump to the next charStop
2952         while (pos < end && !attrs[pos].charStop)
2953             pos++;
2954         return pos;
2955     }
2956     return si->position + end;
2957 }
2958
2959 int QTextEngine::previousLogicalPosition(int oldPos) const
2960 {
2961     const HB_CharAttributes *attrs = attributes();
2962     if (!attrs || oldPos < 0)
2963         return oldPos;
2964
2965     if (oldPos <= 0)
2966         return 0;
2967     oldPos--;
2968     while (oldPos && !attrs[oldPos].charStop)
2969         oldPos--;
2970     return oldPos;
2971 }
2972
2973 int QTextEngine::nextLogicalPosition(int oldPos) const
2974 {
2975     const HB_CharAttributes *attrs = attributes();
2976     int len = block.isValid() ? block.length() - 1
2977                               : layoutData->string.length();
2978     Q_ASSERT(len <= layoutData->string.length());
2979     if (!attrs || oldPos < 0 || oldPos >= len)
2980         return oldPos;
2981
2982     oldPos++;
2983     while (oldPos < len && !attrs[oldPos].charStop)
2984         oldPos++;
2985     return oldPos;
2986 }
2987
2988 int QTextEngine::lineNumberForTextPosition(int pos)
2989 {
2990     if (!layoutData)
2991         itemize();
2992     if (pos == layoutData->string.length() && lines.size())
2993         return lines.size() - 1;
2994     for (int i = 0; i < lines.size(); ++i) {
2995         const QScriptLine& line = lines[i];
2996         if (line.from + line.length + line.trailingSpaces > pos)
2997             return i;
2998     }
2999     return -1;
3000 }
3001
3002 void QTextEngine::insertionPointsForLine(int lineNum, QVector<int> &insertionPoints)
3003 {
3004     QTextLineItemIterator iterator(this, lineNum);
3005     bool rtl = isRightToLeft();
3006     bool lastLine = lineNum >= lines.size() - 1;
3007
3008     while (!iterator.atEnd()) {
3009         iterator.next();
3010         const QScriptItem *si = &layoutData->items[iterator.item];
3011         if (si->analysis.bidiLevel % 2) {
3012             int i = iterator.itemEnd - 1, min = iterator.itemStart;
3013             if (lastLine && (rtl ? iterator.atBeginning() : iterator.atEnd()))
3014                 i++;
3015             for (; i >= min; i--)
3016                 insertionPoints.push_back(i);
3017         } else {
3018             int i = iterator.itemStart, max = iterator.itemEnd;
3019             if (lastLine && (rtl ? iterator.atBeginning() : iterator.atEnd()))
3020                 max++;
3021             for (; i < max; i++)
3022                 insertionPoints.push_back(i);
3023         }
3024     }
3025 }
3026
3027 int QTextEngine::endOfLine(int lineNum)
3028 {
3029     QVector<int> insertionPoints;
3030     insertionPointsForLine(lineNum, insertionPoints);
3031
3032     if (insertionPoints.size() > 0)
3033         return insertionPoints.last();
3034     return 0;
3035 }
3036
3037 int QTextEngine::beginningOfLine(int lineNum)
3038 {
3039     QVector<int> insertionPoints;
3040     insertionPointsForLine(lineNum, insertionPoints);
3041
3042     if (insertionPoints.size() > 0)
3043         return insertionPoints.first();
3044     return 0;
3045 }
3046
3047 int QTextEngine::positionAfterVisualMovement(int pos, QTextCursor::MoveOperation op)
3048 {
3049     if (!layoutData)
3050         itemize();
3051
3052     bool moveRight = (op == QTextCursor::Right);
3053     bool alignRight = isRightToLeft();
3054     if (!layoutData->hasBidi)
3055         return moveRight ^ alignRight ? nextLogicalPosition(pos) : previousLogicalPosition(pos);
3056
3057     int lineNum = lineNumberForTextPosition(pos);
3058     Q_ASSERT(lineNum >= 0);
3059
3060     QVector<int> insertionPoints;
3061     insertionPointsForLine(lineNum, insertionPoints);
3062     int i, max = insertionPoints.size();
3063     for (i = 0; i < max; i++)
3064         if (pos == insertionPoints[i]) {
3065             if (moveRight) {
3066                 if (i + 1 < max)
3067                     return insertionPoints[i + 1];
3068             } else {
3069                 if (i > 0)
3070                     return insertionPoints[i - 1];
3071             }
3072
3073             if (moveRight ^ alignRight) {
3074                 if (lineNum + 1 < lines.size())
3075                     return alignRight ? endOfLine(lineNum + 1) : beginningOfLine(lineNum + 1);
3076             }
3077             else {
3078                 if (lineNum > 0)
3079                     return alignRight ? beginningOfLine(lineNum - 1) : endOfLine(lineNum - 1);
3080             }
3081         }
3082
3083     return pos;
3084 }
3085
3086 QStackTextEngine::QStackTextEngine(const QString &string, const QFont &f)
3087     : QTextEngine(string, f),
3088       _layoutData(string, _memory, MemSize)
3089 {
3090     stackEngine = true;
3091     layoutData = &_layoutData;
3092 }
3093
3094 QTextItemInt::QTextItemInt(const QScriptItem &si, QFont *font, const QTextCharFormat &format)
3095     : justified(false), underlineStyle(QTextCharFormat::NoUnderline), charFormat(format),
3096       num_chars(0), chars(0), logClusters(0), f(0), fontEngine(0)
3097 {
3098     f = font;
3099     fontEngine = f->d->engineForScript(si.analysis.script);
3100     Q_ASSERT(fontEngine);
3101
3102     initWithScriptItem(si);
3103 }
3104
3105 QTextItemInt::QTextItemInt(const QGlyphLayout &g, QFont *font, const QChar *chars_, int numChars, QFontEngine *fe, const QTextCharFormat &format)
3106     : flags(0), justified(false), underlineStyle(QTextCharFormat::NoUnderline), charFormat(format),
3107       num_chars(numChars), chars(chars_), logClusters(0), f(font),  glyphs(g), fontEngine(fe)
3108 {
3109 }
3110
3111 // Fix up flags and underlineStyle with given info
3112 void QTextItemInt::initWithScriptItem(const QScriptItem &si)
3113 {
3114     // explicitly initialize flags so that initFontAttributes can be called
3115     // multiple times on the same TextItem
3116     flags = 0;
3117     if (si.analysis.bidiLevel %2)
3118         flags |= QTextItem::RightToLeft;
3119     ascent = si.ascent;
3120     descent = si.descent;
3121
3122     if (charFormat.hasProperty(QTextFormat::TextUnderlineStyle)) {
3123         underlineStyle = charFormat.underlineStyle();
3124     } else if (charFormat.boolProperty(QTextFormat::FontUnderline)
3125                || f->d->underline) {
3126         underlineStyle = QTextCharFormat::SingleUnderline;
3127     }
3128
3129     // compat
3130     if (underlineStyle == QTextCharFormat::SingleUnderline)
3131         flags |= QTextItem::Underline;
3132
3133     if (f->d->overline || charFormat.fontOverline())
3134         flags |= QTextItem::Overline;
3135     if (f->d->strikeOut || charFormat.fontStrikeOut())
3136         flags |= QTextItem::StrikeOut;
3137 }
3138
3139 QTextItemInt QTextItemInt::midItem(QFontEngine *fontEngine, int firstGlyphIndex, int numGlyphs) const
3140 {
3141     QTextItemInt ti = *this;
3142     const int end = firstGlyphIndex + numGlyphs;
3143     ti.glyphs = glyphs.mid(firstGlyphIndex, numGlyphs);
3144     ti.fontEngine = fontEngine;
3145
3146     if (logClusters && chars) {
3147         const int logClusterOffset = logClusters[0];
3148         while (logClusters[ti.chars - chars] - logClusterOffset < firstGlyphIndex)
3149             ++ti.chars;
3150
3151         ti.logClusters += (ti.chars - chars);
3152
3153         ti.num_chars = 0;
3154         int char_start = ti.chars - chars;
3155         while (char_start + ti.num_chars < num_chars && ti.logClusters[ti.num_chars] - logClusterOffset < end)
3156             ++ti.num_chars;
3157     }
3158     return ti;
3159 }
3160
3161
3162 QTransform qt_true_matrix(qreal w, qreal h, QTransform x)
3163 {
3164     QRectF rect = x.mapRect(QRectF(0, 0, w, h));
3165     return x * QTransform::fromTranslate(-rect.x(), -rect.y());
3166 }
3167
3168
3169 glyph_metrics_t glyph_metrics_t::transformed(const QTransform &matrix) const
3170 {
3171     if (matrix.type() < QTransform::TxTranslate)
3172         return *this;
3173
3174     glyph_metrics_t m = *this;
3175
3176     qreal w = width.toReal();
3177     qreal h = height.toReal();
3178     QTransform xform = qt_true_matrix(w, h, matrix);
3179
3180     QRectF rect(0, 0, w, h);
3181     rect = xform.mapRect(rect);
3182     m.width = QFixed::fromReal(rect.width());
3183     m.height = QFixed::fromReal(rect.height());
3184
3185     QLineF l = xform.map(QLineF(x.toReal(), y.toReal(), xoff.toReal(), yoff.toReal()));
3186
3187     m.x = QFixed::fromReal(l.x1());
3188     m.y = QFixed::fromReal(l.y1());
3189
3190     // The offset is relative to the baseline which is why we use dx/dy of the line
3191     m.xoff = QFixed::fromReal(l.dx());
3192     m.yoff = QFixed::fromReal(l.dy());
3193
3194     return m;
3195 }
3196
3197 QTextLineItemIterator::QTextLineItemIterator(QTextEngine *_eng, int _lineNum, const QPointF &pos,
3198                                              const QTextLayout::FormatRange *_selection)
3199     : eng(_eng),
3200       line(eng->lines[_lineNum]),
3201       si(0),
3202       lineNum(_lineNum),
3203       lineEnd(line.from + line.length),
3204       firstItem(eng->findItem(line.from)),
3205       lastItem(eng->findItem(lineEnd - 1)),
3206       nItems((firstItem >= 0 && lastItem >= firstItem)? (lastItem-firstItem+1) : 0),
3207       logicalItem(-1),
3208       item(-1),
3209       visualOrder(nItems),
3210       levels(nItems),
3211       selection(_selection)
3212 {
3213     pos_x = x = QFixed::fromReal(pos.x());
3214
3215     x += line.x;
3216
3217     x += eng->alignLine(line);
3218
3219     for (int i = 0; i < nItems; ++i)
3220         levels[i] = eng->layoutData->items[i+firstItem].analysis.bidiLevel;
3221     QTextEngine::bidiReorder(nItems, levels.data(), visualOrder.data());
3222
3223     eng->shapeLine(line);
3224 }
3225
3226 QScriptItem &QTextLineItemIterator::next()
3227 {
3228     x += itemWidth;
3229
3230     ++logicalItem;
3231     item = visualOrder[logicalItem] + firstItem;
3232     itemLength = eng->length(item);
3233     si = &eng->layoutData->items[item];
3234     if (!si->num_glyphs)
3235         eng->shape(item);
3236
3237     if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
3238         itemWidth = si->width;
3239         return *si;
3240     }
3241
3242     unsigned short *logClusters = eng->logClusters(si);
3243     QGlyphLayout glyphs = eng->shapedGlyphs(si);
3244
3245     itemStart = qMax(line.from, si->position);
3246     glyphsStart = logClusters[itemStart - si->position];
3247     if (lineEnd < si->position + itemLength) {
3248         itemEnd = lineEnd;
3249         glyphsEnd = logClusters[itemEnd-si->position];
3250     } else {
3251         itemEnd = si->position + itemLength;
3252         glyphsEnd = si->num_glyphs;
3253     }
3254     // show soft-hyphen at line-break
3255     if (si->position + itemLength >= lineEnd
3256         && eng->layoutData->string.at(lineEnd - 1) == 0x00ad)
3257         glyphs.attributes[glyphsEnd - 1].dontPrint = false;
3258
3259     itemWidth = 0;
3260     for (int g = glyphsStart; g < glyphsEnd; ++g)
3261         itemWidth += glyphs.effectiveAdvance(g);
3262
3263     return *si;
3264 }
3265
3266 bool QTextLineItemIterator::getSelectionBounds(QFixed *selectionX, QFixed *selectionWidth) const
3267 {
3268     *selectionX = *selectionWidth = 0;
3269
3270     if (!selection)
3271         return false;
3272
3273     if (si->analysis.flags >= QScriptAnalysis::TabOrObject) {
3274         if (si->position >= selection->start + selection->length
3275             || si->position + itemLength <= selection->start)
3276             return false;
3277
3278         *selectionX = x;
3279         *selectionWidth = itemWidth;
3280     } else {
3281         unsigned short *logClusters = eng->logClusters(si);
3282         QGlyphLayout glyphs = eng->shapedGlyphs(si);
3283
3284         int from = qMax(itemStart, selection->start) - si->position;
3285         int to = qMin(itemEnd, selection->start + selection->length) - si->position;
3286         if (from >= to)
3287             return false;
3288
3289         int start_glyph = logClusters[from];
3290         int end_glyph = (to == eng->length(item)) ? si->num_glyphs : logClusters[to];
3291         QFixed soff;
3292         QFixed swidth;
3293         if (si->analysis.bidiLevel %2) {
3294             for (int g = glyphsEnd - 1; g >= end_glyph; --g)
3295                 soff += glyphs.effectiveAdvance(g);
3296             for (int g = end_glyph - 1; g >= start_glyph; --g)
3297                 swidth += glyphs.effectiveAdvance(g);
3298         } else {
3299             for (int g = glyphsStart; g < start_glyph; ++g)
3300                 soff += glyphs.effectiveAdvance(g);
3301             for (int g = start_glyph; g < end_glyph; ++g)
3302                 swidth += glyphs.effectiveAdvance(g);
3303         }
3304
3305         // If the starting character is in the middle of a ligature,
3306         // selection should only contain the right part of that ligature
3307         // glyph, so we need to get the width of the left part here and
3308         // add it to *selectionX
3309         QFixed leftOffsetInLigature = eng->offsetInLigature(si, from, to, start_glyph);
3310         *selectionX = x + soff + leftOffsetInLigature;
3311         *selectionWidth = swidth - leftOffsetInLigature;
3312         // If the ending character is also part of a ligature, swidth does
3313         // not contain that part yet, we also need to find out the width of
3314         // that left part
3315         *selectionWidth += eng->offsetInLigature(si, to, eng->length(item), end_glyph);
3316     }
3317     return true;
3318 }
3319
3320 QT_END_NAMESPACE