src/gui/text/qtextengine.cpp

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