/*

 * Portions Copyright 2000-2004 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

/*

 * (C) Copyright IBM Corp. 1999-2003 - All Rights Reserved

 *

 * The original version of this source code and documentation is

 * copyrighted and owned by IBM. These materials are provided

 * under terms of a License Agreement between IBM and Sun.

 * This technology is protected by multiple US and International

 * patents. This notice and attribution to IBM may not be removed.

 */

/*

*

******************************************************************************

*   file name:  ubidi.c

*   encoding:   US-ASCII

*   tab size:   8 (not used)

*   indentation:4

*

*   created on: 1999jul27

*   created by: Markus W. Scherer

*/

/* set import/export definitions */

#ifndef U_COMMON_IMPLEMENTATION

#   define U_COMMON_IMPLEMENTATION

#endif

#include "cmemory.h"

#include "utypes.h"

#include "uchardir.h"

#include "ubidi.h"

#include "ubidiimp.h"

/*

 * General implementation notes:

 *

 * Throughout the implementation, there are comments like (W2) that refer to

 * rules of the BiDi algorithm in its version 5, in this example to the second

 * rule of the resolution of weak types.

 *

 * For handling surrogate pairs, where two UChar's form one "abstract" (or UTF-32)

 * character according to UTF-16, the second UChar gets the directional property of

 * the entire character assigned, while the first one gets a BN, a boundary

 * neutral, type, which is ignored by most of the algorithm according to

 * rule (X9) and the implementation suggestions of the BiDi algorithm.

 *

 * Later, adjustWSLevels() will set the level for each BN to that of the

 * following character (UChar), which results in surrogate pairs getting the

 * same level on each of their surrogates.

 *

 * In a UTF-8 implementation, the same thing could be done: the last byte of

 * a multi-byte sequence would get the "real" property, while all previous

 * bytes of that sequence would get BN.

 *

 * It is not possible to assign all those parts of a character the same real

 * property because this would fail in the resolution of weak types with rules

 * that look at immediately surrounding types.

 *

 * As a related topic, this implementation does not remove Boundary Neutral

 * types from the input, but ignores them whereever this is relevant.

 * For example, the loop for the resolution of the weak types reads

 * types until it finds a non-BN.

 * Also, explicit embedding codes are neither changed into BN nor removed.

 * They are only treated the same way real BNs are.

 * As stated before, adjustWSLevels() takes care of them at the end.

 * For the purpose of conformance, the levels of all these codes

 * do not matter.

 *

 * Note that this implementation never modifies the dirProps

 * after the initial setup.

 *

 *

 * In this implementation, the resolution of weak types (Wn),

 * neutrals (Nn), and the assignment of the resolved level (In)

 * are all done in one single loop, in resolveImplicitLevels().

 * Changes of dirProp values are done on the fly, without writing

 * them back to the dirProps array.

 *

 *

 * This implementation contains code that allows to bypass steps of the

 * algorithm that are not needed on the specific paragraph

 * in order to speed up the most common cases considerably,

 * like text that is entirely LTR, or RTL text without numbers.

 *

 * Most of this is done by setting a bit for each directional property

 * in a flags variable and later checking for whether there are

 * any LTR characters or any RTL characters, or both, whether

 * there are any explicit embedding codes, etc.

 *

 * If the (Xn) steps are performed, then the flags are re-evaluated,

 * because they will then not contain the embedding codes any more

 * and will be adjusted for override codes, so that subsequently

 * more bypassing may be possible than what the initial flags suggested.

 *

 * If the text is not mixed-directional, then the

 * algorithm steps for the weak type resolution are not performed,

 * and all levels are set to the paragraph level.

 *

 * If there are no explicit embedding codes, then the (Xn) steps

 * are not performed.

 *

 * If embedding levels are supplied as a parameter, then all

 * explicit embedding codes are ignored, and the (Xn) steps

 * are not performed.

 *

 * White Space types could get the level of the run they belong to,

 * and are checked with a test of (flags&MASK_EMBEDDING) to

 * consider if the paragraph direction should be considered in

 * the flags variable.

 *

 * If there are no White Space types in the paragraph, then

 * (L1) is not necessary in adjustWSLevels().

 */

/* prototypes --------------------------------------------------------------- */

static void

getDirProps(UBiDi *pBiDi, const UChar *text);

static UBiDiDirection

resolveExplicitLevels(UBiDi *pBiDi);

static UBiDiDirection

checkExplicitLevels(UBiDi *pBiDi, UErrorCode *pErrorCode);

static UBiDiDirection

directionFromFlags(Flags flags);

static void

resolveImplicitLevels(UBiDi *pBiDi,

                      int32_t start, int32_t limit,

                      DirProp sor, DirProp eor);

static void

adjustWSLevels(UBiDi *pBiDi);

/* to avoid some conditional statements, use tiny constant arrays */

static const Flags flagLR[2]={ DIRPROP_FLAG(L), DIRPROP_FLAG(R) };

static const Flags flagE[2]={ DIRPROP_FLAG(LRE), DIRPROP_FLAG(RLE) };

static const Flags flagO[2]={ DIRPROP_FLAG(LRO), DIRPROP_FLAG(RLO) };

#define DIRPROP_FLAG_LR(level) flagLR[(level)&1]

#define DIRPROP_FLAG_E(level) flagE[(level)&1]

#define DIRPROP_FLAG_O(level) flagO[(level)&1]

/* UBiDi object management -------------------------------------------------- */

U_CAPI UBiDi * U_EXPORT2

ubidi_open(void)

{

    UErrorCode errorCode=U_ZERO_ERROR;

    return ubidi_openSized(0, 0, &errorCode);

}

U_CAPI UBiDi * U_EXPORT2

ubidi_openSized(int32_t maxLength, int32_t maxRunCount, UErrorCode *pErrorCode) {

    UBiDi *pBiDi;

    /* check the argument values */

    if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {

        return NULL;

    } else if(maxLength<0 || maxRunCount<0) {

        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;

        return NULL;    /* invalid arguments */

    }

    /* allocate memory for the object */

    pBiDi=(UBiDi *)icu_malloc(sizeof(UBiDi));

    if(pBiDi==NULL) {

        *pErrorCode=U_MEMORY_ALLOCATION_ERROR;

        return NULL;

    }

    /* reset the object, all pointers NULL, all flags FALSE, all sizes 0 */

    icu_memset(pBiDi, 0, sizeof(UBiDi));

    /* allocate memory for arrays as requested */

    if(maxLength>0) {

        if( !getInitialDirPropsMemory(pBiDi, maxLength) ||

            !getInitialLevelsMemory(pBiDi, maxLength)

        ) {

            *pErrorCode=U_MEMORY_ALLOCATION_ERROR;

        }

    } else {

        pBiDi->mayAllocateText=TRUE;

    }

    if(maxRunCount>0) {

        if(maxRunCount==1) {

            /* use simpleRuns[] */

            pBiDi->runsSize=sizeof(Run);

        } else if(!getInitialRunsMemory(pBiDi, maxRunCount)) {

            *pErrorCode=U_MEMORY_ALLOCATION_ERROR;

        }

    } else {

        pBiDi->mayAllocateRuns=TRUE;

    }

    if(U_SUCCESS(*pErrorCode)) {

        return pBiDi;

    } else {

        ubidi_close(pBiDi);

        return NULL;

    }

}

/*

 * We are allowed to allocate memory if memory==NULL or

 * mayAllocate==TRUE for each array that we need.

 * We also try to grow and shrink memory as needed if we

 * allocate it.

 *

 * Assume sizeNeeded>0.

 * If *pMemory!=NULL, then assume *pSize>0.

 *

 * ### this realloc() may unnecessarily copy the old data,

 * which we know we don't need any more;

 * is this the best way to do this??

 */

extern bool_t

ubidi_getMemory(void **pMemory, int32_t *pSize, bool_t mayAllocate, int32_t sizeNeeded) {

    /* check for existing memory */

    if(*pMemory==NULL) {

        /* we need to allocate memory */

        if(mayAllocate && (*pMemory=icu_malloc(sizeNeeded))!=NULL) {

            *pSize=sizeNeeded;

            return TRUE;

        } else {

            return FALSE;

        }

    } else {

        /* there is some memory, is it enough or too much? */

        if(sizeNeeded>*pSize && !mayAllocate) {

            /* not enough memory, and we must not allocate */

            return FALSE;

        } else if(sizeNeeded!=*pSize && mayAllocate) {

            /* we may try to grow or shrink */

            void *memory;

            if((memory=icu_realloc(*pMemory, sizeNeeded))!=NULL) {

                *pMemory=memory;

                *pSize=sizeNeeded;

                return TRUE;

            } else {

                /* we failed to grow */

                return FALSE;

            }

        } else {

            /* we have at least enough memory and must not allocate */

            return TRUE;

        }

    }

}

U_CAPI void U_EXPORT2

ubidi_close(UBiDi *pBiDi) {

    if(pBiDi!=NULL) {

        if(pBiDi->dirPropsMemory!=NULL) {

            icu_free(pBiDi->dirPropsMemory);

        }

        if(pBiDi->levelsMemory!=NULL) {

            icu_free(pBiDi->levelsMemory);

        }

        if(pBiDi->runsMemory!=NULL) {

            icu_free(pBiDi->runsMemory);

        }

        icu_free(pBiDi);

    }

}

/* set to approximate "inverse BiDi" ---------------------------------------- */

U_CAPI void U_EXPORT2

ubidi_setInverse(UBiDi *pBiDi, bool_t isInverse) {

    if(pBiDi!=NULL) {

        pBiDi->isInverse=isInverse;

    }

}

U_CAPI bool_t U_EXPORT2

ubidi_isInverse(UBiDi *pBiDi) {

    if(pBiDi!=NULL) {

        return pBiDi->isInverse;

    } else {

        return FALSE;

    }

}

/* ubidi_setPara ------------------------------------------------------------ */

U_CAPI void U_EXPORT2

ubidi_setPara(UBiDi *pBiDi, const UChar *text, int32_t length,

              UBiDiLevel paraLevel, UBiDiLevel *embeddingLevels,

              UErrorCode *pErrorCode) {

    UBiDiDirection direction;

    /* check the argument values */

    if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {

        return;

    } else if(pBiDi==NULL || text==NULL ||

              ((UBIDI_MAX_EXPLICIT_LEVEL<paraLevel) && !IS_DEFAULT_LEVEL(paraLevel)) ||

              length<-1

    ) {

        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;

        return;

    }

    if(length==-1) {

        // length=u_strlen(text);

                const UChar *p = text - 1;

                while(*++p);

                length = p - text;

    }

    /* initialize the UBiDi structure */

    pBiDi->text=text;

    pBiDi->length=length;

    pBiDi->paraLevel=paraLevel;

    pBiDi->direction=UBIDI_LTR;

    pBiDi->trailingWSStart=length;  /* the levels[] will reflect the WS run */

    pBiDi->dirProps=NULL;

    pBiDi->levels=NULL;

    pBiDi->runs=NULL;

    if(length==0) {

        /*

         * For an empty paragraph, create a UBiDi object with the paraLevel and

         * the flags and the direction set but without allocating zero-length arrays.

         * There is nothing more to do.

         */

        if(IS_DEFAULT_LEVEL(paraLevel)) {

            pBiDi->paraLevel&=1;

        }

        if(paraLevel&1) {

            pBiDi->flags=DIRPROP_FLAG(R);

            pBiDi->direction=UBIDI_RTL;

        } else {

            pBiDi->flags=DIRPROP_FLAG(L);

            pBiDi->direction=UBIDI_LTR;

        }

        pBiDi->runCount=0;

        return;

    }

    pBiDi->runCount=-1;

    /*

     * Get the directional properties,

     * the flags bit-set, and

     * determine the partagraph level if necessary.

     */

    if(getDirPropsMemory(pBiDi, length)) {

        pBiDi->dirProps=pBiDi->dirPropsMemory;

        getDirProps(pBiDi, text);

    } else {

        *pErrorCode=U_MEMORY_ALLOCATION_ERROR;

        return;

    }

    /* are explicit levels specified? */

    if(embeddingLevels==NULL) {

        /* no: determine explicit levels according to the (Xn) rules */\

        if(getLevelsMemory(pBiDi, length)) {

            pBiDi->levels=pBiDi->levelsMemory;

            direction=resolveExplicitLevels(pBiDi);

        } else {

            *pErrorCode=U_MEMORY_ALLOCATION_ERROR;

            return;

        }

    } else {

        /* set BN for all explicit codes, check that all levels are paraLevel..UBIDI_MAX_EXPLICIT_LEVEL */

        pBiDi->levels=embeddingLevels;

        direction=checkExplicitLevels(pBiDi, pErrorCode);

        if(U_FAILURE(*pErrorCode)) {

            return;

        }

    }

    /*

     * The steps after (X9) in the UBiDi algorithm are performed only if

     * the paragraph text has mixed directionality!

     */

    pBiDi->direction=direction;

    switch(direction) {

    case UBIDI_LTR:

        /* make sure paraLevel is even */

        pBiDi->paraLevel=(UBiDiLevel)((pBiDi->paraLevel+1)&~1);

        /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */

        pBiDi->trailingWSStart=0;

        break;

    case UBIDI_RTL:

        /* make sure paraLevel is odd */

        pBiDi->paraLevel|=1;

        /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */

        pBiDi->trailingWSStart=0;

        break;

    default:

        /*

         * If there are no external levels specified and there

         * are no significant explicit level codes in the text,

         * then we can treat the entire paragraph as one run.

         * Otherwise, we need to perform the following rules on runs of

         * the text with the same embedding levels. (X10)

         * "Significant" explicit level codes are ones that actually

         * affect non-BN characters.

         * Examples for "insignificant" ones are empty embeddings

         * LRE-PDF, LRE-RLE-PDF-PDF, etc.

         */

        if(embeddingLevels==NULL && !(pBiDi->flags&DIRPROP_FLAG_MULTI_RUNS)) {

            resolveImplicitLevels(pBiDi, 0, length,

                                    GET_LR_FROM_LEVEL(pBiDi->paraLevel),

                                    GET_LR_FROM_LEVEL(pBiDi->paraLevel));

        } else {

            /* sor, eor: start and end types of same-level-run */

            UBiDiLevel *levels=pBiDi->levels;

            int32_t start, limit=0;

            UBiDiLevel level, nextLevel;

            DirProp sor, eor;

            /* determine the first sor and set eor to it because of the loop body (sor=eor there) */

            level=pBiDi->paraLevel;

            nextLevel=levels[0];

            if(level<nextLevel) {

                eor=GET_LR_FROM_LEVEL(nextLevel);

            } else {

                eor=GET_LR_FROM_LEVEL(level);

            }

            do {

                /* determine start and limit of the run (end points just behind the run) */

                /* the values for this run's start are the same as for the previous run's end */

                sor=eor;

                start=limit;

                level=nextLevel;

                /* search for the limit of this run */

                while(++limit<length && levels[limit]==level) {}

                /* get the correct level of the next run */

                if(limit<length) {

                    nextLevel=levels[limit];

                } else {

                    nextLevel=pBiDi->paraLevel;

                }

                /* determine eor from max(level, nextLevel); sor is last run's eor */

                if((level&~UBIDI_LEVEL_OVERRIDE)<(nextLevel&~UBIDI_LEVEL_OVERRIDE)) {

                    eor=GET_LR_FROM_LEVEL(nextLevel);

                } else {

                    eor=GET_LR_FROM_LEVEL(level);

                }

                /* if the run consists of overridden directional types, then there

                   are no implicit types to be resolved */

                if(!(level&UBIDI_LEVEL_OVERRIDE)) {

                    resolveImplicitLevels(pBiDi, start, limit, sor, eor);

                } else {

                    /* remove the UBIDI_LEVEL_OVERRIDE flags */

                    do {

                        levels[start++]&=~UBIDI_LEVEL_OVERRIDE;

                    } while(start<limit);

                }

            } while(limit<length);

        }

        /* reset the embedding levels for some non-graphic characters (L1), (X9) */

        adjustWSLevels(pBiDi);

        /* for "inverse BiDi", ubidi_getRuns() modifies the levels of numeric runs following RTL runs */

        if(pBiDi->isInverse) {

            if(!ubidi_getRuns(pBiDi)) {

                *pErrorCode=U_MEMORY_ALLOCATION_ERROR;

                return;

            }

        }

        break;

    }

}

/* perform (P2)..(P3) ------------------------------------------------------- */

/*

 * Get the directional properties for the text,

 * calculate the flags bit-set, and

 * determine the partagraph level if necessary.

 */

static void

getDirProps(UBiDi *pBiDi, const UChar *text) {

    DirProp *dirProps=pBiDi->dirPropsMemory;    /* pBiDi->dirProps is const */

    int32_t i=0, i0, i1, length=pBiDi->length;

    Flags flags=0;      /* collect all directionalities in the text */

    UChar uchar;

    DirProp dirProp;

    if(IS_DEFAULT_LEVEL(pBiDi->paraLevel)) {

        /* determine the paragraph level (P2..P3) */

        for(;;) {

            uchar=text[i];