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