/****************************************************************************

**

** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** GNU Lesser General Public License Usage

** This file may be used under the terms of the GNU Lesser General Public

** License version 2.1 as published by the Free Software Foundation and

** appearing in the file LICENSE.LGPL included in the packaging of this

** file. Please review the following information to ensure the GNU Lesser

** General Public License version 2.1 requirements will be met:

** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights. These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** GNU General Public License Usage

** Alternatively, this file may be used under the terms of the GNU General

** Public License version 3.0 as published by the Free Software Foundation

** and appearing in the file LICENSE.GPL included in the packaging of this

** file. Please review the following information to ensure the GNU General

** Public License version 3.0 requirements will be met:

** http://www.gnu.org/copyleft/gpl.html.

**

** Other Usage

** Alternatively, this file may be used in accordance with the terms and

** conditions contained in a signed written agreement between you and Nokia.

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qdebug.h"

#include "qtextformat.h"

#include "qtextformat_p.h"

#include "qtextengine_p.h"

#include "qabstracttextdocumentlayout.h"

#include "qtextlayout.h"

#include "qtextboundaryfinder.h"

#include "qvarlengtharray.h"

#include "qfont.h"

#include "qfont_p.h"

#include "qfontengine_p.h"

#include "qstring.h"

#include <private/qunicodetables_p.h>

#include "qtextdocument_p.h"

#include <qapplication.h>

#include <stdlib.h>

QT_BEGIN_NAMESPACE

namespace {

// Helper class used in QTextEngine::itemize

// keep it out here to allow us to keep supporting various compilers.

class Itemizer {

public:

    Itemizer(const QString &string, const QScriptAnalysis *analysis, QScriptItemArray &items)

        : m_string(string),

        m_analysis(analysis),

        m_items(items),

        m_splitter(0)

    {

    }

    ~Itemizer()

    {

        delete m_splitter;

    }

    /// generate the script items

    /// The caps parameter is used to choose the algoritm of splitting text and assiging roles to the textitems

    void generate(int start, int length, QFont::Capitalization caps)

    {

        if ((int)caps == (int)QFont::SmallCaps)

            generateScriptItemsSmallCaps(reinterpret_cast<const ushort *>(m_string.unicode()), start, length);

        else if(caps == QFont::Capitalize)

            generateScriptItemsCapitalize(start, length);

        else if(caps != QFont::MixedCase) {

            generateScriptItemsAndChangeCase(start, length,

                caps == QFont::AllLowercase ? QScriptAnalysis::Lowercase : QScriptAnalysis::Uppercase);

        }

        else

            generateScriptItems(start, length);

    }

private:

    enum { MaxItemLength = 4096 };

    void generateScriptItemsAndChangeCase(int start, int length, QScriptAnalysis::Flags flags)

    {

        generateScriptItems(start, length);

        if (m_items.isEmpty()) // the next loop won't work in that case

            return;

        QScriptItemArray::Iterator iter = m_items.end();

        do {

            iter--;

            if (iter->analysis.flags < QScriptAnalysis::TabOrObject)

                iter->analysis.flags = flags;

        } while (iter->position > start);

    }

    void generateScriptItems(int start, int length)

    {

        if (!length)

            return;

        const int end = start + length;

        for (int i = start + 1; i < end; ++i) {

            // According to the unicode spec we should be treating characters in the Common script

            // (punctuation, spaces, etc) as being the same script as the surrounding text for the

            // purpose of splitting up text. This is important because, for example, a fullstop

            // (0x2E) can be used to indicate an abbreviation and so must be treated as part of a

            // word.  Thus it must be passed along with the word in languages that have to calculate

            // word breaks.  For example the thai word "ครม." has no word breaks but the word "ครม"

            // does.

            // Unfortuntely because we split up the strings for both wordwrapping and for setting

            // the font and because Japanese and Chinese are also aliases of the script "Common",

            // doing this would break too many things.  So instead we only pass the full stop

            // along, and nothing else.

            if (m_analysis[i].bidiLevel == m_analysis[start].bidiLevel

                && m_analysis[i].flags == m_analysis[start].flags

                && (m_analysis[i].script == m_analysis[start].script || m_string[i] == QLatin1Char('.'))

                && m_analysis[i].flags < QScriptAnalysis::SpaceTabOrObject

                && i - start < MaxItemLength)

                continue;

            m_items.append(QScriptItem(start, m_analysis[start]));

            start = i;

        }

        m_items.append(QScriptItem(start, m_analysis[start]));

    }

    void generateScriptItemsCapitalize(int start, int length)

    {

        if (!length)

            return;

        if (!m_splitter)

            m_splitter = new QTextBoundaryFinder(QTextBoundaryFinder::Word,

                                                 m_string.constData(), m_string.length(),

                                                 /*buffer*/0, /*buffer size*/0);

        m_splitter->setPosition(start);

        QScriptAnalysis itemAnalysis = m_analysis[start];

        if (m_splitter->boundaryReasons() & QTextBoundaryFinder::StartWord) {

            itemAnalysis.flags = QScriptAnalysis::Uppercase;

            m_splitter->toNextBoundary();

        }

        const int end = start + length;

        for (int i = start + 1; i < end; ++i) {

            bool atWordBoundary = false;

            if (i == m_splitter->position()) {

                if (m_splitter->boundaryReasons() & QTextBoundaryFinder::StartWord

                    && m_analysis[i].flags < QScriptAnalysis::TabOrObject)

                    atWordBoundary = true;

                m_splitter->toNextBoundary();

            }

            if (m_analysis[i] == itemAnalysis

                && m_analysis[i].flags < QScriptAnalysis::TabOrObject

                && !atWordBoundary

                && i - start < MaxItemLength)

                continue;

            m_items.append(QScriptItem(start, itemAnalysis));

            start = i;

            itemAnalysis = m_analysis[start];

            if (atWordBoundary)

                itemAnalysis.flags = QScriptAnalysis::Uppercase;

        }

        m_items.append(QScriptItem(start, itemAnalysis));

    }

    void generateScriptItemsSmallCaps(const ushort *uc, int start, int length)

    {

        if (!length)

            return;

        bool lower = (QChar::category(uc[start]) == QChar::Letter_Lowercase);

        const int end = start + length;

        // split text into parts that are already uppercase and parts that are lowercase, and mark the latter to be uppercased later.

        for (int i = start + 1; i < end; ++i) {

            bool l = (QChar::category(uc[i]) == QChar::Letter_Lowercase);

            if ((m_analysis[i] == m_analysis[start])

                && m_analysis[i].flags < QScriptAnalysis::TabOrObject

                && l == lower

                && i - start < MaxItemLength)

                continue;

            m_items.append(QScriptItem(start, m_analysis[start]));

            if (lower)

                m_items.last().analysis.flags = QScriptAnalysis::SmallCaps;

            start = i;

            lower = l;

        }

        m_items.append(QScriptItem(start, m_analysis[start]));

        if (lower)

            m_items.last().analysis.flags = QScriptAnalysis::SmallCaps;

    }

    const QString &m_string;

    const QScriptAnalysis * const m_analysis;

    QScriptItemArray &m_items;

    QTextBoundaryFinder *m_splitter;

};

}

// ----------------------------------------------------------------------------

//

// The BiDi algorithm

//

// ----------------------------------------------------------------------------

#define BIDI_DEBUG 0

#if (BIDI_DEBUG >= 1)

QT_BEGIN_INCLUDE_NAMESPACE

#include <iostream>

QT_END_INCLUDE_NAMESPACE

using namespace std;

static const char *directions[] = {

    "DirL", "DirR", "DirEN", "DirES", "DirET", "DirAN", "DirCS", "DirB", "DirS", "DirWS", "DirON",

    "DirLRE", "DirLRO", "DirAL", "DirRLE", "DirRLO", "DirPDF", "DirNSM", "DirBN"

};

#endif

struct QBidiStatus {

    QBidiStatus() {

        eor = QChar::DirON;

        lastStrong = QChar::DirON;

        last = QChar:: DirON;

        dir = QChar::DirON;

    }

    QChar::Direction eor;

    QChar::Direction lastStrong;

    QChar::Direction last;

    QChar::Direction dir;

};

enum { MaxBidiLevel = 61 };

struct QBidiControl {

    inline QBidiControl(bool rtl)

        : cCtx(0), base(rtl ? 1 : 0), level(rtl ? 1 : 0), override(false) {}

    inline void embed(bool rtl, bool o = false) {

        unsigned int toAdd = 1;

        if((level%2 != 0) == rtl ) {

            ++toAdd;

        }

        if (level + toAdd <= MaxBidiLevel) {

            ctx[cCtx].level = level;

            ctx[cCtx].override = override;

            cCtx++;

            override = o;

            level += toAdd;

        }

    }

    inline bool canPop() const { return cCtx != 0; }

    inline void pdf() {

        Q_ASSERT(cCtx);

        --cCtx;

        level = ctx[cCtx].level;

        override = ctx[cCtx].override;

    }

    inline QChar::Direction basicDirection() const {

        return (base ? QChar::DirR : QChar:: DirL);

    }

    inline unsigned int baseLevel() const {

        return base;

    }

    inline QChar::Direction direction() const {

        return ((level%2) ? QChar::DirR : QChar:: DirL);

    }

    struct {

        unsigned int level;

        bool override;

    } ctx[MaxBidiLevel];

    unsigned int cCtx;

    const unsigned int base;

    unsigned int level;

    bool override;

};

static void appendItems(QScriptAnalysis *analysis, int &start, int &stop, const QBidiControl &control, QChar::Direction dir)

{

    if (start > stop)

        return;

    int level = control.level;

    if(dir != QChar::DirON && !control.override) {

        // add level of run (cases I1 & I2)

        if(level % 2) {

            if(dir == QChar::DirL || dir == QChar::DirAN || dir == QChar::DirEN)

                level++;

        } else {

            if(dir == QChar::DirR)

                level++;

            else if(dir == QChar::DirAN || dir == QChar::DirEN)

                level += 2;

        }

    }

#if (BIDI_DEBUG >= 1)

    qDebug("new run: dir=%s from %d, to %d level = %d override=%d", directions[dir], start, stop, level, control.override);

#endif

    QScriptAnalysis *s = analysis + start;

    const QScriptAnalysis *e = analysis + stop;

    while (s <= e) {

        s->bidiLevel = level;

        ++s;

    }

    ++stop;

    start = stop;

}

static QChar::Direction skipBoundryNeutrals(QScriptAnalysis *analysis,

                                            const ushort *unicode, int length,

                                            int &sor, int &eor, QBidiControl &control)

{

    QChar::Direction dir = control.basicDirection();

    int level = sor > 0 ? analysis[sor - 1].bidiLevel : control.level;

    while (sor < length) {

        dir = QChar::direction(unicode[sor]);

        // Keep skipping DirBN as if it doesn't exist

        if (dir != QChar::DirBN)

            break;

        analysis[sor++].bidiLevel = level;

    }

    eor = sor;

    if (eor == length)

        dir = control.basicDirection();

    return dir;

}

// creates the next QScript items.

static bool bidiItemize(QTextEngine *engine, QScriptAnalysis *analysis, QBidiControl &control)

{

    bool rightToLeft = (control.basicDirection() == 1);

    bool hasBidi = rightToLeft;

#if BIDI_DEBUG >= 2

    qDebug() << "bidiItemize: rightToLeft=" << rightToLeft << engine->layoutData->string;

#endif

    int sor = 0;

    int eor = -1;

    int length = engine->layoutData->string.length();

    const ushort *unicode = (const ushort *)engine->layoutData->string.unicode();

    int current = 0;

    QChar::Direction dir = rightToLeft ? QChar::DirR : QChar::DirL;

    QBidiStatus status;

    QChar::Direction sdir = QChar::direction(*unicode);

    if (sdir != QChar::DirL && sdir != QChar::DirR && sdir != QChar::DirEN && sdir != QChar::DirAN)

        sdir = QChar::DirON;

    else

        dir = QChar::DirON;

    status.eor = sdir;

    status.lastStrong = rightToLeft ? QChar::DirR : QChar::DirL;

    status.last = status.lastStrong;

    status.dir = sdir;

    while (current <= length) {

        QChar::Direction dirCurrent;

        if (current == (int)length)

            dirCurrent = control.basicDirection();

        else

            dirCurrent = QChar::direction(unicode[current]);

#if (BIDI_DEBUG >= 2)

//         qDebug() << "pos=" << current << " dir=" << directions[dir]

//                  << " current=" << directions[dirCurrent] << " last=" << directions[status.last]

//                  << " eor=" << eor << '/' << directions[status.eor]

//                  << " sor=" << sor << " lastStrong="

//                  << directions[status.lastStrong]

//                  << " level=" << (int)control.level << " override=" << (bool)control.override;

#endif

        switch(dirCurrent) {

            // embedding and overrides (X1-X9 in the BiDi specs)

        case QChar::DirRLE:

        case QChar::DirRLO:

        case QChar::DirLRE:

        case QChar::DirLRO:

            {

                bool rtl = (dirCurrent == QChar::DirRLE || dirCurrent == QChar::DirRLO);

                hasBidi |= rtl;

                bool override = (dirCurrent == QChar::DirLRO || dirCurrent == QChar::DirRLO);

                unsigned int level = control.level+1;

                if ((level%2 != 0) == rtl) ++level;

                if(level < MaxBidiLevel) {

                    eor = current-1;

                    appendItems(analysis, sor, eor, control, dir);

                    eor = current;

                    control.embed(rtl, override);

                    QChar::Direction edir = (rtl ? QChar::DirR : QChar::DirL);

                    dir = status.eor = edir;

                    status.lastStrong = edir;

                }

                break;

            }

        case QChar::DirPDF:

            {

                if (control.canPop()) {

                    if (dir != control.direction()) {

                        eor = current-1;

                        appendItems(analysis, sor, eor, control, dir);

                        dir = control.direction();

                    }

                    eor = current;

                    appendItems(analysis, sor, eor, control, dir);

                    control.pdf();

                    dir = QChar::DirON; status.eor = QChar::DirON;

                    status.last = control.direction();

                    if (control.override)

                        dir = control.direction();

                    else

                        dir = QChar::DirON;

                    status.lastStrong = control.direction();

                }

                break;

            }

            // strong types

        case QChar::DirL:

            if(dir == QChar::DirON)

                dir = QChar::DirL;

            switch(status.last)

                {

                case QChar::DirL:

                    eor = current; status.eor = QChar::DirL; break;

                case QChar::DirR:

                case QChar::DirAL:

                case QChar::DirEN:

                case QChar::DirAN:

                    if (eor >= 0) {

                        appendItems(analysis, sor, eor, control, dir);

                        status.eor = dir = skipBoundryNeutrals(analysis, unicode, length, sor, eor, control);

                    } else {

                        eor = current; status.eor = dir;

                    }

                    break;

                case QChar::DirES:

                case QChar::DirET:

                case QChar::DirCS:

                case QChar::DirBN:

                case QChar::DirB:

                case QChar::DirS:

                case QChar::DirWS:

                case QChar::DirON:

                    if(dir != QChar::DirL) {

                        //last stuff takes embedding dir

                        if(control.direction() == QChar::DirR) {

                            if(status.eor != QChar::DirR) {

                                // AN or EN

                                appendItems(analysis, sor, eor, control, dir);

                                status.eor = QChar::DirON;

                                dir = QChar::DirR;

                            }

                            eor = current - 1;

                            appendItems(analysis, sor, eor, control, dir);

                            status.eor = dir = skipBoundryNeutrals(analysis, unicode, length, sor, eor, control);

                        } else {

                            if(status.eor != QChar::DirL) {

                                appendItems(analysis, sor, eor, control, dir);

                                status.eor = QChar::DirON;

                                dir = QChar::DirL;

                            } else {

                                eor = current; status.eor = QChar::DirL; break;

                            }

                        }

                    } else {

                        eor = current; status.eor = QChar::DirL;

                    }

                default:

                    break;

                }

            status.lastStrong = QChar::DirL;

            break;

        case QChar::DirAL:

        case QChar::DirR:

            hasBidi = true;

            if(dir == QChar::DirON) dir = QChar::DirR;

            switch(status.last)

                {

                case QChar::DirL:

                case QChar::DirEN:

                case QChar::DirAN:

                    if (eor >= 0)

                        appendItems(analysis, sor, eor, control, dir);

                    // fall through

                case QChar::DirR:

                case QChar::DirAL:

                    dir = QChar::DirR; eor = current; status.eor = QChar::DirR; break;

                case QChar::DirES:

                case QChar::DirET:

                case QChar::DirCS:

                case QChar::DirBN:

                case QChar::DirB:

                case QChar::DirS:

                case QChar::DirWS:

                case QChar::DirON:

                    if(status.eor != QChar::DirR && status.eor != QChar::DirAL) {

                        //last stuff takes embedding dir

                        if(control.direction() == QChar::DirR

                           || status.lastStrong == QChar::DirR || status.lastStrong == QChar::DirAL) {

                            appendItems(analysis, sor, eor, control, dir);

                            dir = QChar::DirR; status.eor = QChar::DirON;

                            eor = current;

                        } else {

                            eor = current - 1;

                            appendItems(analysis, sor, eor, control, dir);

                            dir = QChar::DirR; status.eor = QChar::DirON;

                        }

                    } else {

                        eor = current; status.eor = QChar::DirR;

                    }

                default:

                    break;

                }

            status.lastStrong = dirCurrent;

            break;

            // weak types:

        case QChar::DirNSM:

            if (eor == current-1)

                eor = current;

            break;

        case QChar::DirEN:

            // if last strong was AL change EN to AN

            if(status.lastStrong != QChar::DirAL) {

                if(dir == QChar::DirON) {

                    if(status.lastStrong == QChar::DirL)

                        dir = QChar::DirL;

                    else

                        dir = QChar::DirEN;

                }

                switch(status.last)

                    {

                    case QChar::DirET:

                        if (status.lastStrong == QChar::DirR || status.lastStrong == QChar::DirAL) {

                            appendItems(analysis, sor, eor, control, dir);

                            status.eor = QChar::DirON;

                            dir = QChar::DirAN;

                        }

                        // fall through

                    case QChar::DirEN:

                    case QChar::DirL:

                        eor = current;

                        status.eor = dirCurrent;

                        break;

                    case QChar::DirR:

                    case QChar::DirAL:

                    case QChar::DirAN:

                        if (eor >= 0)

                            appendItems(analysis, sor, eor, control, dir);

                        else

                            eor = current;

                        status.eor = QChar::DirEN;

                        dir = QChar::DirAN; break;

                    case QChar::DirES:

                    case QChar::DirCS:

                        if(status.eor == QChar::DirEN || dir == QChar::DirAN) {

                            eor = current; break;

                        }

                    case QChar::DirBN:

                    case QChar::DirB:

                    case QChar::DirS:

                    case QChar::DirWS:

                    case QChar::DirON:

                        if(status.eor == QChar::DirR) {

                            // neutrals go to R

                            eor = current - 1;

                            appendItems(analysis, sor, eor, control, dir);

                            dir = QChar::DirON; status.eor = QChar::DirEN;

                            dir = QChar::DirAN;

                        }

                        else if(status.eor == QChar::DirL ||

                                 (status.eor == QChar::DirEN && status.lastStrong == QChar::DirL)) {

                            eor = current; status.eor = dirCurrent;

                        } else {

                            // numbers on both sides, neutrals get right to left direction

                            if(dir != QChar::DirL) {

                                appendItems(analysis, sor, eor, control, dir);

                                dir = QChar::DirON; status.eor = QChar::DirON;

                                eor = current - 1;

                                dir = QChar::DirR;

                                appendItems(analysis, sor, eor, control, dir);

                                dir = QChar::DirON; status.eor = QChar::DirON;

                                dir = QChar::DirAN;

                            } else {

                                eor = current; status.eor = dirCurrent;

                            }

                        }

                    default:

                        break;

                    }

                break;

            }

        case QChar::DirAN:

            hasBidi = true;

            dirCurrent = QChar::DirAN;

            if(dir == QChar::DirON) dir = QChar::DirAN;

            switch(status.last)

                {

                case QChar::DirL:

                case QChar::DirAN:

                    eor = current; status.eor = QChar::DirAN; break;

                case QChar::DirR:

                case QChar::DirAL:

                case QChar::DirEN:

                    if (eor >= 0){

                        appendItems(analysis, sor, eor, control, dir);

                    } else {

                        eor = current;

                    }

                    dir = QChar::DirAN; status.eor = QChar::DirAN;

                    break;

                case QChar::DirCS:

                    if(status.eor == QChar::DirAN) {

                        eor = current; break;

                    }

                case QChar::DirES:

                case QChar::DirET:

                case QChar::DirBN:

                case QChar::DirB:

                case QChar::DirS:

                case QChar::DirWS:

                case QChar::DirON:

                    if(status.eor == QChar::DirR) {

                        // neutrals go to R

                        eor = current - 1;

                        appendItems(analysis, sor, eor, control, dir);

                        status.eor = QChar::DirAN;

                        dir = QChar::DirAN;

                    } else if(status.eor == QChar::DirL ||

                               (status.eor == QChar::DirEN && status.lastStrong == QChar::DirL)) {

                        eor = current; status.eor = dirCurrent;

                    } else {

                        // numbers on both sides, neutrals get right to left direction

                        if(dir != QChar::DirL) {

                            appendItems(analysis, sor, eor, control, dir);

                            status.eor = QChar::DirON;

                            eor = current - 1;

                            dir = QChar::DirR;

                            appendItems(analysis, sor, eor, control, dir);

                            status.eor = QChar::DirAN;

                            dir = QChar::DirAN;

                        } else {

                            eor = current; status.eor = dirCurrent;

                        }

                    }

                default:

                    break;

                }

            break;

        case QChar::DirES:

        case QChar::DirCS:

            break;

        case QChar::DirET:

            if(status.last == QChar::DirEN) {

                dirCurrent = QChar::DirEN;

                eor = current; status.eor = dirCurrent;

            }

            break;

            // boundary neutrals should be ignored

        case QChar::DirBN:

            break;

            // neutrals

        case QChar::DirB:

            // ### what do we do with newline and paragraph separators that come to here?

            break;

        case QChar::DirS:

            // ### implement rule L1

            break;

        case QChar::DirWS:

        case QChar::DirON:

            break;

        default:

            break;

        }

        //qDebug() << "     after: dir=" << //        dir << " current=" << dirCurrent << " last=" << status.last << " eor=" << status.eor << " lastStrong=" << status.lastStrong << " embedding=" << control.direction();

        if(current >= (int)length) break;

        // set status.last as needed.

        switch(dirCurrent) {

        case QChar::DirET:

        case QChar::DirES:

        case QChar::DirCS:

        case QChar::DirS:

        case QChar::DirWS:

        case QChar::DirON:

            switch(status.last)

            {

            case QChar::DirL:

            case QChar::DirR:

            case QChar::DirAL:

            case QChar::DirEN:

            case QChar::DirAN:

                status.last = dirCurrent;

                break;

            default:

                status.last = QChar::DirON;

            }

            break;

        case QChar::DirNSM:

        case QChar::DirBN:

            // ignore these

            break;

        case QChar::DirLRO:

        case QChar::DirLRE:

            status.last = QChar::DirL;

            break;

        case QChar::DirRLO:

        case QChar::DirRLE:

            status.last = QChar::DirR;

            break;

        case QChar::DirEN:

            if (status.last == QChar::DirL) {

                status.last = QChar::DirL;

                break;

            }

            // fall through

        default:

            status.last = dirCurrent;

        }

        ++current;

    }

#if (BIDI_DEBUG >= 1)

    qDebug() << "reached end of line current=" << current << ", eor=" << eor;

#endif

    eor = current - 1; // remove dummy char

    if (sor <= eor)

        appendItems(analysis, sor, eor, control, dir);

    return hasBidi;

}

void QTextEngine::bidiReorder(int numItems, const quint8 *levels, int *visualOrder)

{

    // first find highest and lowest levels

    quint8 levelLow = 128;

    quint8 levelHigh = 0;

    int i = 0;

    while (i < numItems) {

        //printf("level = %d\n", r->level);

        if (levels[i] > levelHigh)

            levelHigh = levels[i];

        if (levels[i] < levelLow)

            levelLow = levels[i];

        i++;

    }

    // implements reordering of the line (L2 according to BiDi spec):

    // L2. From the highest level found in the text to the lowest odd level on each line,

    // reverse any contiguous sequence of characters that are at that level or higher.

    // reversing is only done up to the lowest odd level

    if(!(levelLow%2)) levelLow++;

#if (BIDI_DEBUG >= 1)

//     qDebug() << "reorderLine: lineLow = " << (uint)levelLow << ", lineHigh = " << (uint)levelHigh;

#endif

    int count = numItems - 1;

    for (i = 0; i < numItems; i++)

        visualOrder[i] = i;

    while(levelHigh >= levelLow) {

        int i = 0;

        while (i < count) {

            while(i < count && levels[i] < levelHigh) i++;

            int start = i;

            while(i <= count && levels[i] >= levelHigh) i++;

            int end = i-1;

            if(start != end) {

                //qDebug() << "reversing from " << start << " to " << end;

                for(int j = 0; j < (end-start+1)/2; j++) {

                    int tmp = visualOrder[start+j];

                    visualOrder[start+j] = visualOrder[end-j];

                    visualOrder[end-j] = tmp;

                }

            }

            i++;

        }

        levelHigh--;

    }

#if (BIDI_DEBUG >= 1)

//     qDebug() << "visual order is:";

//     for (i = 0; i < numItems; i++)

//         qDebug() << visualOrder[i];

#endif

}

QT_BEGIN_INCLUDE_NAMESPACE

#if defined(Q_WS_X11) || defined (Q_WS_QWS)

#   include "qfontengine_ft_p.h"

#elif defined(Q_WS_MAC)

# include "qtextengine_mac.cpp"

#endif

#include <private/qharfbuzz_p.h>

QT_END_INCLUDE_NAMESPACE

// ask the font engine to find out which glyphs (as an index in the specific font) to use for the text in one item.

static bool stringToGlyphs(HB_ShaperItem *item, QGlyphLayout *glyphs, QFontEngine *fontEngine)

{

    int nGlyphs = item->num_glyphs;

    QTextEngine::ShaperFlags shaperFlags(QTextEngine::GlyphIndicesOnly);

    if (item->item.bidiLevel % 2)

        shaperFlags |= QTextEngine::RightToLeft;

    bool result = fontEngine->stringToCMap(reinterpret_cast<const QChar *>(item->string + item->item.pos), item->item.length, glyphs, &nGlyphs, shaperFlags);

    item->num_glyphs = nGlyphs;

    glyphs->numGlyphs = nGlyphs;

    return result;

}

// shape all the items that intersect with the line, taking tab widths into account to find out what text actually fits in the line.

void QTextEngine::shapeLine(const QScriptLine &line)

{

    QFixed x;

    bool first = true;

    const int end = findItem(line.from + line.length - 1);

    int item = findItem(line.from);

    if (item == -1)

        return;

    for (item = findItem(line.from); item <= end; ++item) {

        QScriptItem &si = layoutData->items[item];

        if (si.analysis.flags == QScriptAnalysis::Tab) {

            ensureSpace(1);

            si.width = calculateTabWidth(item, x);

        } else {

            shape(item);

        }

        if (first && si.position != line.from) { // that means our x position has to be offset

            QGlyphLayout glyphs = shapedGlyphs(&si);

            Q_ASSERT(line.from > si.position);

            for (int i = line.from - si.position - 1; i >= 0; i--) {

                x -= glyphs.effectiveAdvance(i);

            }

        }

        first = false;

        x += si.width;

    }

}

#if !defined(QT_ENABLE_HARFBUZZ_FOR_MAC) && defined(Q_WS_MAC)

static bool enableHarfBuzz()

{

    static enum { Yes, No, Unknown } status = Unknown;

    if (status == Unknown) {

        QByteArray v = qgetenv("QT_ENABLE_HARFBUZZ");

        bool value = !v.isEmpty() && v != "0" && v != "false";

        if (value) status = Yes;

        else status = No;

    }

    return status == Yes;

}

#endif

void QTextEngine::shapeText(int item) const

{

    Q_ASSERT(item < layoutData->items.size());

    QScriptItem &si = layoutData->items[item];

    if (si.num_glyphs)

        return;

#if defined(Q_WS_MAC)

#if !defined(QT_ENABLE_HARFBUZZ_FOR_MAC)

    if (enableHarfBuzz()) {

#endif

        QFontEngine *actualFontEngine = fontEngine(si, &si.ascent, &si.descent, &si.leading);

        if (actualFontEngine->type() == QFontEngine::Multi)

            actualFontEngine = static_cast<QFontEngineMulti *>(actualFontEngine)->engine(0);

        HB_Face face = actualFontEngine->harfbuzzFace();

        HB_Script script = (HB_Script) si.analysis.script;

        if (face->supported_scripts[script])

            shapeTextWithHarfbuzz(item);

        else

            shapeTextMac(item);

#if !defined(QT_ENABLE_HARFBUZZ_FOR_MAC)

    } else {

        shapeTextMac(item);

    }

#endif

#elif defined(Q_WS_WINCE)

    shapeTextWithCE(item);

#else

    shapeTextWithHarfbuzz(item);

#endif

    si.width = 0;

    if (!si.num_glyphs)

        return;

    QGlyphLayout glyphs = shapedGlyphs(&si);

    QFont font = this->font(si);

    bool letterSpacingIsAbsolute = font.d->letterSpacingIsAbsolute;

    QFixed letterSpacing = font.d->letterSpacing;

    QFixed wordSpacing = font.d->wordSpacing;

    if (letterSpacingIsAbsolute && letterSpacing.value())

        letterSpacing *= font.d->dpi / qt_defaultDpiY();

    if (letterSpacing != 0) {

        for (int i = 1; i < si.num_glyphs; ++i) {

            if (glyphs.attributes[i].clusterStart) {

                if (letterSpacingIsAbsolute)

                    glyphs.advances_x[i-1] += letterSpacing;

                else {

                    QFixed &advance = glyphs.advances_x[i-1];

                    advance += (letterSpacing - 100) * advance / 100;

                }

            }

        }

        if (letterSpacingIsAbsolute)

            glyphs.advances_x[si.num_glyphs-1] += letterSpacing;

        else {

            QFixed &advance = glyphs.advances_x[si.num_glyphs-1];

            advance += (letterSpacing - 100) * advance / 100;

        }

    }

    if (wordSpacing != 0) {

        for (int i = 0; i < si.num_glyphs; ++i) {

            if (glyphs.attributes[i].justification == HB_Space

                || glyphs.attributes[i].justification == HB_Arabic_Space) {

                // word spacing only gets added once to a consecutive run of spaces (see CSS spec)

                if (i + 1 == si.num_glyphs

                    ||(glyphs.attributes[i+1].justification != HB_Space

                       && glyphs.attributes[i+1].justification != HB_Arabic_Space))

                    glyphs.advances_x[i] += wordSpacing;

            }

        }

    }

    for (int i = 0; i < si.num_glyphs; ++i)

        si.width += glyphs.advances_x[i] * !glyphs.attributes[i].dontPrint;

}

static inline bool hasCaseChange(const QScriptItem &si)

{

    return si.analysis.flags == QScriptAnalysis::SmallCaps ||

           si.analysis.flags == QScriptAnalysis::Uppercase ||

           si.analysis.flags == QScriptAnalysis::Lowercase;

}

#if defined(Q_WS_WINCE) //TODO

// set the glyph attributes heuristically. Assumes a 1 to 1 relationship between chars and glyphs

// and no reordering.

// also computes logClusters heuristically

static void heuristicSetGlyphAttributes(const QChar *uc, int length, QGlyphLayout *glyphs, unsigned short *logClusters, int num_glyphs)

{

    // ### zeroWidth and justification are missing here!!!!!

    Q_UNUSED(num_glyphs);

    Q_ASSERT(num_glyphs <= length);

//     qDebug("QScriptEngine::heuristicSetGlyphAttributes, num_glyphs=%d", item->num_glyphs);

    int glyph_pos = 0;

    for (int i = 0; i < length; i++) {

        if (uc[i].isHighSurrogate() && i < length-1 && uc[i+1].isLowSurrogate()) {

            logClusters[i] = glyph_pos;

            logClusters[++i] = glyph_pos;

        } else {

            logClusters[i] = glyph_pos;

        }

        ++glyph_pos;

    }

    // first char in a run is never (treated as) a mark

    int cStart = 0;

    const bool symbolFont = false; // ####

    glyphs->attributes[0].mark = false;

    glyphs->attributes[0].clusterStart = true;

    glyphs->attributes[0].dontPrint = (!symbolFont && uc[0].unicode() == 0x00ad) || qIsControlChar(uc[0].unicode());

    int pos = 0;

    int lastCat = QChar::category(uc[0].unicode());

    for (int i = 1; i < length; ++i) {

        if (logClusters[i] == pos)

            // same glyph

            continue;

        ++pos;

        while (pos < logClusters[i]) {

            glyphs[pos].attributes = glyphs[pos-1].attributes;

            ++pos;

        }

        // hide soft-hyphens by default

        if ((!symbolFont && uc[i].unicode() == 0x00ad) || qIsControlChar(uc[i].unicode()))

            glyphs->attributes[pos].dontPrint = true;

        const QUnicodeTables::Properties *prop = QUnicodeTables::properties(uc[i].unicode());

        int cat = prop->category;

        if (cat != QChar::Mark_NonSpacing) {

            glyphs->attributes[pos].mark = false;

            glyphs->attributes[pos].clusterStart = true;

            glyphs->attributes[pos].combiningClass = 0;

            cStart = logClusters[i];

        } else {

            int cmb = prop->combiningClass;

            if (cmb == 0) {

                // Fix 0 combining classes

                if ((uc[pos].unicode() & 0xff00) == 0x0e00) {

                    // thai or lao

                    unsigned char col = uc[pos].cell();

                    if (col == 0x31 ||

                         col == 0x34 ||

                         col == 0x35 ||

                         col == 0x36 ||

                         col == 0x37 ||

                         col == 0x47 ||

                         col == 0x4c ||

                         col == 0x4d ||

                         col == 0x4e) {

                        cmb = QChar::Combining_AboveRight;

                    } else if (col == 0xb1 ||

                                col == 0xb4 ||

                                col == 0xb5 ||

                                col == 0xb6 ||

                                col == 0xb7 ||

                                col == 0xbb ||

                                col == 0xcc ||

                                col == 0xcd) {

                        cmb = QChar::Combining_Above;

                    } else if (col == 0xbc) {

                        cmb = QChar::Combining_Below;

                    }

                }

            }

            glyphs->attributes[pos].mark = true;

            glyphs->attributes[pos].clusterStart = false;

            glyphs->attributes[pos].combiningClass = cmb;

            logClusters[i] = cStart;

            glyphs->advances_x[pos] = 0;

            glyphs->advances_y[pos] = 0;

        }

        // one gets an inter character justification point if the current char is not a non spacing mark.

        // as then the current char belongs to the last one and one gets a space justification point

        // after the space char.

        if (lastCat == QChar::Separator_Space)

            glyphs->attributes[pos-1].justification = HB_Space;

        else if (cat != QChar::Mark_NonSpacing)

            glyphs->attributes[pos-1].justification = HB_Character;

        else

            glyphs->attributes[pos-1].justification = HB_NoJustification;

        lastCat = cat;

    }

    pos = logClusters[length-1];

    if (lastCat == QChar::Separator_Space)

        glyphs->attributes[pos].justification = HB_Space;

    else

        glyphs->attributes[pos].justification = HB_Character;

}

void QTextEngine::shapeTextWithCE(int item) const

{

    QScriptItem &si = layoutData->items[item];

    si.glyph_data_offset = layoutData->used;

    QFontEngine *fe = fontEngine(si, &si.ascent, &si.descent, &si.leading);

    QTextEngine::ShaperFlags flags;

    if (si.analysis.bidiLevel % 2)

        flags |= RightToLeft;

    if (option.useDesignMetrics())

	flags |= DesignMetrics;

    // pre-initialize char attributes

    if (! attributes())

        return;

    const int len = length(item);

    int num_glyphs = length(item);

    const QChar *str = layoutData->string.unicode() + si.position;

    ushort upperCased[256];

    if (hasCaseChange(si)) {

        ushort *uc = upperCased;

        if (len > 256)

            uc = new ushort[len];

        for (int i = 0; i < len; ++i) {

            if(si.analysis.flags == QScriptAnalysis::Lowercase)

                uc[i] = str[i].toLower().unicode();

            else

                uc[i] = str[i].toUpper().unicode();

        }

        str = reinterpret_cast<const QChar *>(uc);

    }

    while (true) {

        if (! ensureSpace(num_glyphs)) {

            // If str is converted to uppercase/lowercase form with a new buffer,

            // we need to delete that buffer before return for error

            const ushort *uc = reinterpret_cast<const ushort *>(str);

            if (hasCaseChange(si) && uc != upperCased)

                delete [] uc;

            return;

        }

        num_glyphs = layoutData->glyphLayout.numGlyphs - layoutData->used;

        QGlyphLayout g = availableGlyphs(&si);

        unsigned short *log_clusters = logClusters(&si);

        if (fe->stringToCMap(str,

                             len,

                             &g,

                             &num_glyphs,

                             flags)) {

            heuristicSetGlyphAttributes(str, len, &g, log_clusters, num_glyphs);

		    break;

        }

    }

    si.num_glyphs = num_glyphs;

    layoutData->used += si.num_glyphs;

    const ushort *uc = reinterpret_cast<const ushort *>(str);

    if (hasCaseChange(si) && uc != upperCased)

        delete [] uc;

}

#endif

static inline void moveGlyphData(const QGlyphLayout &destination, const QGlyphLayout &source, int num)

{

    if (num > 0 && destination.glyphs != source.glyphs) {

        memmove(destination.glyphs, source.glyphs, num * sizeof(HB_Glyph));

        memmove(destination.attributes, source.attributes, num * sizeof(HB_GlyphAttributes));

        memmove(destination.advances_x, source.advances_x, num * sizeof(HB_Fixed));

        memmove(destination.offsets, source.offsets, num * sizeof(HB_FixedPoint));

    }

}

/// take the item from layoutData->items and

void QTextEngine::shapeTextWithHarfbuzz(int item) const

{

    Q_ASSERT(sizeof(HB_Fixed) == sizeof(QFixed));

    Q_ASSERT(sizeof(HB_FixedPoint) == sizeof(QFixedPoint));

    QScriptItem &si = layoutData->items[item];

    si.glyph_data_offset = layoutData->used;

    QFontEngine *font = fontEngine(si, &si.ascent, &si.descent, &si.leading);

    bool kerningEnabled = this->font(si).d->kerning;

    HB_ShaperItem entire_shaper_item;

    qMemSet(&entire_shaper_item, 0, sizeof(entire_shaper_item));

    entire_shaper_item.string = reinterpret_cast<const HB_UChar16 *>(layoutData->string.constData());

    entire_shaper_item.stringLength = layoutData->string.length();

    entire_shaper_item.item.script = (HB_Script)si.analysis.script;

    entire_shaper_item.item.pos = si.position;

    entire_shaper_item.item.length = length(item);

    entire_shaper_item.item.bidiLevel = si.analysis.bidiLevel;

    HB_UChar16 upperCased[256]; // XXX what about making this 4096, so we don't have to extend it ever.

    if (hasCaseChange(si)) {

        HB_UChar16 *uc = upperCased;

        if (entire_shaper_item.item.length > 256)

            uc = new HB_UChar16[entire_shaper_item.item.length];

        for (uint i = 0; i < entire_shaper_item.item.length; ++i) {

            if(si.analysis.flags == QScriptAnalysis::Lowercase)

                uc[i] = QChar::toLower(entire_shaper_item.string[si.position + i]);

            else

                uc[i] = QChar::toUpper(entire_shaper_item.string[si.position + i]);

        }

        entire_shaper_item.item.pos = 0;

        entire_shaper_item.string = uc;

        entire_shaper_item.stringLength = entire_shaper_item.item.length;

    }

    entire_shaper_item.shaperFlags = 0;

    if (!kerningEnabled)

        entire_shaper_item.shaperFlags |= HB_ShaperFlag_NoKerning;

    if (option.useDesignMetrics())

        entire_shaper_item.shaperFlags |= HB_ShaperFlag_UseDesignMetrics;

    entire_shaper_item.num_glyphs = qMax(layoutData->glyphLayout.numGlyphs - layoutData->used, int(entire_shaper_item.item.length));

    if (! ensureSpace(entire_shaper_item.num_glyphs)) {

        if (hasCaseChange(si))

            delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);

        return;

    }

    QGlyphLayout initialGlyphs = availableGlyphs(&si).mid(0, entire_shaper_item.num_glyphs);

    if (!stringToGlyphs(&entire_shaper_item, &initialGlyphs, font)) {

        if (! ensureSpace(entire_shaper_item.num_glyphs)) {

            if (hasCaseChange(si))

                delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);

            return;

        }

        initialGlyphs = availableGlyphs(&si).mid(0, entire_shaper_item.num_glyphs);

        if (!stringToGlyphs(&entire_shaper_item, &initialGlyphs, font)) {

            // ############ if this happens there's a bug in the fontengine

            if (hasCaseChange(si) && entire_shaper_item.string != upperCased)

                delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);

            return;

        }

    }

    // split up the item into parts that come from different font engines.

    QVarLengthArray<int> itemBoundaries(2);

    // k * 2 entries, array[k] == index in string, array[k + 1] == index in glyphs

    itemBoundaries[0] = entire_shaper_item.item.pos;

    itemBoundaries[1] = 0;

    if (font->type() == QFontEngine::Multi) {

        uint lastEngine = 0;

        int charIdx = entire_shaper_item.item.pos;

        const int stringEnd = charIdx + entire_shaper_item.item.length;

        for (quint32 i = 0; i < entire_shaper_item.num_glyphs; ++i, ++charIdx) {

            uint engineIdx = initialGlyphs.glyphs[i] >> 24;

            if (engineIdx != lastEngine && i > 0) {

                itemBoundaries.append(charIdx);

                itemBoundaries.append(i);

            }

            lastEngine = engineIdx;

            if (HB_IsHighSurrogate(entire_shaper_item.string[charIdx])

                && charIdx < stringEnd - 1

                && HB_IsLowSurrogate(entire_shaper_item.string[charIdx + 1]))

                ++charIdx;

        }

    }

    int remaining_glyphs = entire_shaper_item.num_glyphs;

    int glyph_pos = 0;

    // for each item shape using harfbuzz and store the results in our layoutData's glyphs array.

    for (int k = 0; k < itemBoundaries.size(); k += 2) { // for the +2, see the comment at the definition of itemBoundaries

        HB_ShaperItem shaper_item = entire_shaper_item;

        shaper_item.item.pos = itemBoundaries[k];

        if (k < itemBoundaries.size() - 3) {

            shaper_item.item.length = itemBoundaries[k + 2] - shaper_item.item.pos;

            shaper_item.num_glyphs = itemBoundaries[k + 3] - itemBoundaries[k + 1];

        } else { // last combo in the list, avoid out of bounds access.

            shaper_item.item.length -= shaper_item.item.pos - entire_shaper_item.item.pos;

            shaper_item.num_glyphs -= itemBoundaries[k + 1];

        }

        shaper_item.initialGlyphCount = shaper_item.num_glyphs;

        if (shaper_item.num_glyphs < shaper_item.item.length)

            shaper_item.num_glyphs = shaper_item.item.length;

        QFontEngine *actualFontEngine = font;

        uint engineIdx = 0;

        if (font->type() == QFontEngine::Multi) {

            engineIdx = uint(availableGlyphs(&si).glyphs[glyph_pos] >> 24);

            actualFontEngine = static_cast<QFontEngineMulti *>(font)->engine(engineIdx);

        }

        si.ascent = qMax(actualFontEngine->ascent(), si.ascent);

        si.descent = qMax(actualFontEngine->descent(), si.descent);

        si.leading = qMax(actualFontEngine->leading(), si.leading);

        shaper_item.font = actualFontEngine->harfbuzzFont();

        shaper_item.face = actualFontEngine->harfbuzzFace();

        shaper_item.glyphIndicesPresent = true;

        remaining_glyphs -= shaper_item.initialGlyphCount;

        do {

            if (! ensureSpace(glyph_pos + shaper_item.num_glyphs + remaining_glyphs)) {

                if (hasCaseChange(si))

                    delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);

                return;

            }

            const QGlyphLayout g = availableGlyphs(&si).mid(glyph_pos);

            if (shaper_item.num_glyphs > shaper_item.item.length)

                moveGlyphData(g.mid(shaper_item.num_glyphs), g.mid(shaper_item.initialGlyphCount), remaining_glyphs);

            shaper_item.glyphs = g.glyphs;

            shaper_item.attributes = g.attributes;

            shaper_item.advances = reinterpret_cast<HB_Fixed *>(g.advances_x);

            shaper_item.offsets = reinterpret_cast<HB_FixedPoint *>(g.offsets);

            if (shaper_item.glyphIndicesPresent) {

                for (hb_uint32 i = 0; i < shaper_item.initialGlyphCount; ++i)

                    shaper_item.glyphs[i] &= 0x00ffffff;

            }

            shaper_item.log_clusters = logClusters(&si) + shaper_item.item.pos - entire_shaper_item.item.pos;

//          qDebug("    .. num_glyphs=%d, used=%d, item.num_glyphs=%d", num_glyphs, used, shaper_item.num_glyphs);

        } while (!qShapeItem(&shaper_item)); // this does the actual shaping via harfbuzz.

        QGlyphLayout g = availableGlyphs(&si).mid(glyph_pos, shaper_item.num_glyphs);

        moveGlyphData(g.mid(shaper_item.num_glyphs), g.mid(shaper_item.initialGlyphCount), remaining_glyphs);

        for (hb_uint32 i = 0; i < shaper_item.num_glyphs; ++i)

            g.glyphs[i] = g.glyphs[i] | (engineIdx << 24);

        for (hb_uint32 i = 0; i < shaper_item.item.length; ++i)

            shaper_item.log_clusters[i] += glyph_pos;

        if (kerningEnabled && !shaper_item.kerning_applied)

            font->doKerning(&g, option.useDesignMetrics() ? QFlag(QTextEngine::DesignMetrics) : QFlag(0));

        glyph_pos += shaper_item.num_glyphs;

    }

//     qDebug("    -> item: script=%d num_glyphs=%d", shaper_item.script, shaper_item.num_glyphs);

    si.num_glyphs = glyph_pos;

    layoutData->used += si.num_glyphs;

    if (hasCaseChange(si) && entire_shaper_item.string != upperCased)

        delete [] const_cast<HB_UChar16 *>(entire_shaper_item.string);

}

static void init(QTextEngine *e)

{

    e->ignoreBidi = false;

    e->cacheGlyphs = false;

    e->forceJustification = false;

    e->visualMovement = false;

    e->layoutData = 0;

    e->minWidth = 0;

    e->maxWidth = 0;

    e->underlinePositions = 0;

    e->specialData = 0;

    e->stackEngine = false;

}

QTextEngine::QTextEngine()

{

    init(this);

}

QTextEngine::QTextEngine(const QString &str, const QFont &f)

    : text(str),

      fnt(f)

{

    init(this);

}

QTextEngine::~QTextEngine()

{

    if (!stackEngine)

        delete layoutData;

    delete specialData;

    resetFontEngineCache();

}

const HB_CharAttributes *QTextEngine::attributes() const

{

    if (layoutData && layoutData->haveCharAttributes)

        return (HB_CharAttributes *) layoutData->memory;

    itemize();

    if (! ensureSpace(layoutData->string.length()))

        return NULL;

    QVarLengthArray<HB_ScriptItem> hbScriptItems(layoutData->items.size());

    for (int i = 0; i < layoutData->items.size(); ++i) {

        const QScriptItem &si = layoutData->items[i];

        hbScriptItems[i].pos = si.position;

        hbScriptItems[i].length = length(i);

        hbScriptItems[i].bidiLevel = si.analysis.bidiLevel;

        hbScriptItems[i].script = (HB_Script)si.analysis.script;

    }

    qGetCharAttributes(reinterpret_cast<const HB_UChar16 *>(layoutData->string.constData()),

                       layoutData->string.length(),

                       hbScriptItems.data(), hbScriptItems.size(),

                       (HB_CharAttributes *)layoutData->memory);

    layoutData->haveCharAttributes = true;

    return (HB_CharAttributes *) layoutData->memory;

}

void QTextEngine::shape(int item) const

{

    if (layoutData->items[item].analysis.flags == QScriptAnalysis::Object) {

        ensureSpace(1);

        if (block.docHandle()) {

            QTextFormat format = formats()->format(formatIndex(&layoutData->items[item]));

            docLayout()->resizeInlineObject(QTextInlineObject(item, const_cast<QTextEngine *>(this)),

                                            layoutData->items[item].position + block.position(), format);

        }

    } else if (layoutData->items[item].analysis.flags == QScriptAnalysis::Tab) {

        // set up at least the ascent/descent/leading of the script item for the tab

        fontEngine(layoutData->items[item],

                   &layoutData->items[item].ascent,

                   &layoutData->items[item].descent,

                   &layoutData->items[item].leading);

    } else {

        shapeText(item);

    }

}

static inline void releaseCachedFontEngine(QFontEngine *fontEngine)

{

    if (fontEngine) {

        fontEngine->ref.deref();

        if (fontEngine->cache_count == 0 && fontEngine->ref == 0)

            delete fontEngine;

    }

}

void QTextEngine::resetFontEngineCache()

{

    releaseCachedFontEngine(feCache.prevFontEngine);

    releaseCachedFontEngine(feCache.prevScaledFontEngine);

    feCache.reset();

}

void QTextEngine::invalidate()

{

    freeMemory();

    minWidth = 0;

    maxWidth = 0;

    if (specialData)

        specialData->resolvedFormatIndices.clear();

    resetFontEngineCache();

}

void QTextEngine::clearLineData()

{

    lines.clear();

}

void QTextEngine::validate() const

{

    if (layoutData)

        return;

    layoutData = new LayoutData();

    if (block.docHandle()) {

        layoutData->string = block.text();

        if (option.flags() & QTextOption::ShowLineAndParagraphSeparators)

            layoutData->string += QLatin1Char(block.next().isValid() ? 0xb6 : 0x20);

    } else {

        layoutData->string = text;

    }

    if (specialData && specialData->preeditPosition != -1)

        layoutData->string.insert(specialData->preeditPosition, specialData->preeditText);

}

void QTextEngine::itemize() const

{

    validate();

    if (layoutData->items.size())

        return;

    int length = layoutData->string.length();

    if (!length)

        return;

#if defined(Q_WS_MAC) && !defined(QT_MAC_USE_COCOA)

    // ATSUI requires RTL flags to correctly identify the character stops.

    bool ignore = false;

#else

    bool ignore = ignoreBidi;

#endif

    bool rtl = isRightToLeft();

    if (!ignore && !rtl) {

        ignore = true;

        const QChar *start = layoutData->string.unicode();

        const QChar * const end = start + length;

        while (start < end) {

            if (start->unicode() >= 0x590) {

                ignore = false;

                break;

            }

            ++start;

        }

    }

    QVarLengthArray<QScriptAnalysis, 4096> scriptAnalysis(length);

    QScriptAnalysis *analysis = scriptAnalysis.data();

    QBidiControl control(rtl);

    if (ignore) {

        memset(analysis, 0, length*sizeof(QScriptAnalysis));

        if (option.textDirection() == Qt::RightToLeft) {

            for (int i = 0; i < length; ++i)

                analysis[i].bidiLevel = 1;

            layoutData->hasBidi = true;

        }

    } else {

        layoutData->hasBidi = bidiItemize(const_cast<QTextEngine *>(this), analysis, control);

    }

    const ushort *uc = reinterpret_cast<const ushort *>(layoutData->string.unicode());

    const ushort *e = uc + length;

    int lastScript = QUnicodeTables::Common;

    while (uc < e) {

        switch (*uc) {

        case QChar::ObjectReplacementCharacter:

            analysis->script = QUnicodeTables::Common;

            analysis->flags = QScriptAnalysis::Object;

            break;

        case QChar::LineSeparator:

            if (analysis->bidiLevel % 2)

                --analysis->bidiLevel;

            analysis->script = QUnicodeTables::Common;

            analysis->flags = QScriptAnalysis::LineOrParagraphSeparator;

            if (option.flags() & QTextOption::ShowLineAndParagraphSeparators)

                *const_cast<ushort*>(uc) = 0x21B5; // visual line separator

            break;

        case 9: // Tab

            analysis->script = QUnicodeTables::Common;

            analysis->flags = QScriptAnalysis::Tab;

            analysis->bidiLevel = control.baseLevel();

            break;

        case 32: // Space

        case QChar::Nbsp:

            if (option.flags() & QTextOption::ShowTabsAndSpaces) {

                analysis->script = QUnicodeTables::Common;

                analysis->flags = QScriptAnalysis::Space;

                analysis->bidiLevel = control.baseLevel();

                break;

            }

        // fall through

        default:

            int script = QUnicodeTables::script(*uc);

            analysis->script = script == QUnicodeTables::Inherited ? lastScript : script;

            analysis->flags = QScriptAnalysis::None;

            break;

        }

        lastScript = analysis->script;

        ++uc;