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