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

**

** Copyright (C) 2009 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$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, 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.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $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(m_string.utf16(), 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) {

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

                && 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;

}

// 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);

                        dir = eor < length ? QChar::direction(unicode[eor]) : control.basicDirection();

                        status.eor = dir;

                    } 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);

                            dir = eor < length ? QChar::direction(unicode[eor]) : control.basicDirection();

                            status.eor = dir;

                        } 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