src/gui/text/qtextengine.cpp

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