src/gui/text/qtextengine.cpp

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