diff options
Diffstat (limited to 'layout/base/nsBidi_noICU.cpp')
| -rw-r--r-- | layout/base/nsBidi_noICU.cpp | 2089 |
1 files changed, 2089 insertions, 0 deletions
diff --git a/layout/base/nsBidi_noICU.cpp b/layout/base/nsBidi_noICU.cpp new file mode 100644 index 000000000..0b9c58e55 --- /dev/null +++ b/layout/base/nsBidi_noICU.cpp @@ -0,0 +1,2089 @@ +/* -*- Mode: C; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "nsBidi.h" +#include "nsUnicodeProperties.h" +#include "nsCRTGlue.h" + +using namespace mozilla::unicode; + +static_assert(mozilla::kBidiLevelNone > NSBIDI_MAX_EXPLICIT_LEVEL + 1, + "The pseudo embedding level should be out-of-range"); + +// These are #defined in <sys/regset.h> under Solaris 10 x86 +#undef CS +#undef ES + +/* Comparing the description of the Bidi algorithm with this implementation + is easier with the same names for the Bidi types in the code as there. +*/ +enum { + L = eCharType_LeftToRight, + R = eCharType_RightToLeft, + EN = eCharType_EuropeanNumber, + ES = eCharType_EuropeanNumberSeparator, + ET = eCharType_EuropeanNumberTerminator, + AN = eCharType_ArabicNumber, + CS = eCharType_CommonNumberSeparator, + B = eCharType_BlockSeparator, + S = eCharType_SegmentSeparator, + WS = eCharType_WhiteSpaceNeutral, + O_N = eCharType_OtherNeutral, + LRE = eCharType_LeftToRightEmbedding, + LRO = eCharType_LeftToRightOverride, + AL = eCharType_RightToLeftArabic, + RLE = eCharType_RightToLeftEmbedding, + RLO = eCharType_RightToLeftOverride, + PDF = eCharType_PopDirectionalFormat, + NSM = eCharType_DirNonSpacingMark, + BN = eCharType_BoundaryNeutral, + LRI = eCharType_LeftToRightIsolate, + RLI = eCharType_RightToLeftIsolate, + FSI = eCharType_FirstStrongIsolate, + PDI = eCharType_PopDirectionalIsolate, + ENL, /* EN after W7 */ /* 23 */ + ENR, /* EN not subject to W7 */ /* 24 */ + dirPropCount +}; + +#define IS_STRONG_TYPE(dirProp) ((dirProp) <= R || (dirProp) == AL) + +/* to avoid some conditional statements, use tiny constant arrays */ +static Flags flagLR[2]={ DIRPROP_FLAG(L), DIRPROP_FLAG(R) }; +static Flags flagE[2]={ DIRPROP_FLAG(LRE), DIRPROP_FLAG(RLE) }; +static 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] + +#define NO_OVERRIDE(level) ((level)&~NSBIDI_LEVEL_OVERRIDE) + +static inline uint8_t +DirFromStrong(uint8_t aDirProp) +{ + MOZ_ASSERT(IS_STRONG_TYPE(aDirProp)); + return aDirProp == L ? L : R; +} + +/* + * 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 whenever 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, except for FSI which is changed to either + * LRI or RLI in GetDirProps(), and paired brackets which may be changed + * to L or R according to N0. + * + * + * 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(). + */ +nsBidi::nsBidi() +{ + Init(); +} + +nsBidi::~nsBidi() +{ + Free(); +} + +void nsBidi::Init() +{ + /* reset the object, all pointers nullptr, all flags false, all sizes 0 */ + mLength = 0; + mParaLevel = 0; + mFlags = 0; + mDirection = NSBIDI_LTR; + mTrailingWSStart = 0; + + mDirPropsSize = 0; + mLevelsSize = 0; + mRunsSize = 0; + mIsolatesSize = 0; + + mRunCount = -1; + mIsolateCount = -1; + + mDirProps=nullptr; + mLevels=nullptr; + mRuns=nullptr; + mIsolates=nullptr; + + mDirPropsMemory=nullptr; + mLevelsMemory=nullptr; + mRunsMemory=nullptr; + mIsolatesMemory=nullptr; +} + +/* + * We are allowed to allocate memory if aMemory==nullptr + * for each array that we need. + * We also try to grow and shrink memory as needed if we + * allocate it. + * + * Assume aSizeNeeded>0. + * If *aMemory!=nullptr, then assume *aSize>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?? + */ +/*static*/ +bool +nsBidi::GetMemory(void **aMemory, size_t *aSize, size_t aSizeNeeded) +{ + /* check for existing memory */ + if(*aMemory==nullptr) { + /* we need to allocate memory */ + *aMemory=malloc(aSizeNeeded); + if (*aMemory!=nullptr) { + *aSize=aSizeNeeded; + return true; + } else { + *aSize=0; + return false; + } + } else { + /* there is some memory, is it enough or too much? */ + if(aSizeNeeded!=*aSize) { + /* we may try to grow or shrink */ + void *memory=realloc(*aMemory, aSizeNeeded); + + if(memory!=nullptr) { + *aMemory=memory; + *aSize=aSizeNeeded; + return true; + } else { + /* we failed to grow */ + return false; + } + } else { + /* we have at least enough memory and must not allocate */ + return true; + } + } +} + +void nsBidi::Free() +{ + free(mDirPropsMemory); + mDirPropsMemory = nullptr; + free(mLevelsMemory); + mLevelsMemory = nullptr; + free(mRunsMemory); + mRunsMemory = nullptr; + free(mIsolatesMemory); + mIsolatesMemory = nullptr; +} + +/* SetPara ------------------------------------------------------------ */ + +nsresult nsBidi::SetPara(const char16_t *aText, int32_t aLength, + nsBidiLevel aParaLevel) +{ + nsBidiDirection direction; + + /* check the argument values */ + if(aText==nullptr || + ((NSBIDI_MAX_EXPLICIT_LEVEL<aParaLevel) && !IS_DEFAULT_LEVEL(aParaLevel)) || + aLength<-1 + ) { + return NS_ERROR_INVALID_ARG; + } + + if(aLength==-1) { + aLength = NS_strlen(aText); + } + + /* initialize member data */ + mLength = aLength; + mParaLevel=aParaLevel; + mDirection=aParaLevel & 1 ? NSBIDI_RTL : NSBIDI_LTR; + mTrailingWSStart=aLength; /* the levels[] will reflect the WS run */ + + mDirProps=nullptr; + mLevels=nullptr; + mRuns=nullptr; + + if(aLength==0) { + /* + * For an empty paragraph, create an nsBidi object with the aParaLevel and + * the flags and the direction set but without allocating zero-length arrays. + * There is nothing more to do. + */ + if(IS_DEFAULT_LEVEL(aParaLevel)) { + mParaLevel&=1; + } + mFlags=DIRPROP_FLAG_LR(aParaLevel); + mRunCount=0; + return NS_OK; + } + + mRunCount=-1; + + /* + * Get the directional properties, + * the flags bit-set, and + * determine the partagraph level if necessary. + */ + if(GETDIRPROPSMEMORY(aLength)) { + mDirProps=mDirPropsMemory; + GetDirProps(aText); + } else { + return NS_ERROR_OUT_OF_MEMORY; + } + + /* determine explicit levels according to the (Xn) rules */ + if(GETLEVELSMEMORY(aLength)) { + mLevels=mLevelsMemory; + ResolveExplicitLevels(&direction, aText); + } else { + return NS_ERROR_OUT_OF_MEMORY; + } + + /* allocate isolate memory */ + if (mIsolateCount <= SIMPLE_ISOLATES_SIZE) { + mIsolates = mSimpleIsolates; + } else { + if (mIsolateCount * sizeof(Isolate) <= mIsolatesSize) { + mIsolates = mIsolatesMemory; + } else { + if (GETISOLATESMEMORY(mIsolateCount)) { + mIsolates = mIsolatesMemory; + } else { + return NS_ERROR_OUT_OF_MEMORY; + } + } + } + mIsolateCount = -1; /* current isolates stack entry == none */ + + /* + * The steps after (X9) in the Bidi algorithm are performed only if + * the paragraph text has mixed directionality! + */ + mDirection = direction; + switch(direction) { + case NSBIDI_LTR: + /* make sure paraLevel is even */ + mParaLevel=(mParaLevel+1)&~1; + + /* all levels are implicitly at paraLevel (important for GetLevels()) */ + mTrailingWSStart=0; + break; + case NSBIDI_RTL: + /* make sure paraLevel is odd */ + mParaLevel|=1; + + /* all levels are implicitly at paraLevel (important for GetLevels()) */ + mTrailingWSStart=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(!(mFlags&DIRPROP_FLAG_MULTI_RUNS)) { + ResolveImplicitLevels(0, aLength, + GET_LR_FROM_LEVEL(mParaLevel), + GET_LR_FROM_LEVEL(mParaLevel)); + } else { + /* sor, eor: start and end types of same-level-run */ + nsBidiLevel *levels=mLevels; + int32_t start, limit=0; + nsBidiLevel level, nextLevel; + DirProp sor, eor; + + /* determine the first sor and set eor to it because of the loop body (sor=eor there) */ + level=mParaLevel; + 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<aLength && + (levels[limit]==level || + (DIRPROP_FLAG(mDirProps[limit])&MASK_BN_EXPLICIT))) {} + + /* get the correct level of the next run */ + if(limit<aLength) { + nextLevel=levels[limit]; + } else { + nextLevel=mParaLevel; + } + + /* determine eor from max(level, nextLevel); sor is last run's eor */ + if((level&~NSBIDI_LEVEL_OVERRIDE)<(nextLevel&~NSBIDI_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&NSBIDI_LEVEL_OVERRIDE)) { + ResolveImplicitLevels(start, limit, sor, eor); + } else { + do { + levels[start++] &= ~NSBIDI_LEVEL_OVERRIDE; + } while (start < limit); + } + } while(limit<aLength); + } + + /* reset the embedding levels for some non-graphic characters (L1), (X9) */ + AdjustWSLevels(); + break; + } + + return NS_OK; +} + +/* perform (P2)..(P3) ------------------------------------------------------- */ + +/* + * Get the directional properties for the text, + * calculate the flags bit-set, and + * determine the partagraph level if necessary. + */ +void nsBidi::GetDirProps(const char16_t *aText) +{ + DirProp *dirProps=mDirPropsMemory; /* mDirProps is const */ + + int32_t i=0, length=mLength; + Flags flags=0; /* collect all directionalities in the text */ + char16_t uchar; + DirProp dirProp; + + bool isDefaultLevel = IS_DEFAULT_LEVEL(mParaLevel); + + enum State { + NOT_SEEKING_STRONG, /* 0: not after FSI */ + SEEKING_STRONG_FOR_PARA, /* 1: looking for first strong char in para */ + SEEKING_STRONG_FOR_FSI, /* 2: looking for first strong after FSI */ + LOOKING_FOR_PDI /* 3: found strong after FSI, looking for PDI */ + }; + State state; + + /* The following stacks are used to manage isolate sequences. Those + sequences may be nested, but obviously never more deeply than the + maximum explicit embedding level. + lastStack is the index of the last used entry in the stack. A value of -1 + means that there is no open isolate sequence. */ + /* The following stack contains the position of the initiator of + each open isolate sequence */ + int32_t isolateStartStack[NSBIDI_MAX_EXPLICIT_LEVEL + 1]; + /* The following stack contains the last known state before + encountering the initiator of an isolate sequence */ + State previousStateStack[NSBIDI_MAX_EXPLICIT_LEVEL + 1]; + int32_t stackLast = -1; + + if(isDefaultLevel) { + /* + * see comment in nsBidi.h: + * the DEFAULT_XXX values are designed so that + * their bit 0 alone yields the intended default + */ + mParaLevel &= 1; + state = SEEKING_STRONG_FOR_PARA; + } else { + state = NOT_SEEKING_STRONG; + } + + /* determine the paragraph level (P2..P3) */ + for(/* i = 0 above */; i < length;) { + uchar=aText[i]; + if(!IS_FIRST_SURROGATE(uchar) || i+1==length || !IS_SECOND_SURROGATE(aText[i+1])) { + /* not a surrogate pair */ + flags|=DIRPROP_FLAG(dirProps[i]=dirProp=GetBidiCat((uint32_t)uchar)); + } else { + /* a surrogate pair */ + dirProps[i++]=BN; /* first surrogate in the pair gets the BN type */ + flags|=DIRPROP_FLAG(dirProps[i]=dirProp=GetBidiCat(GET_UTF_32(uchar, aText[i])))|DIRPROP_FLAG(BN); + } + ++i; + + switch (dirProp) { + case L: + if (state == SEEKING_STRONG_FOR_PARA) { + mParaLevel = 0; + state = NOT_SEEKING_STRONG; + } else if (state == SEEKING_STRONG_FOR_FSI) { + if (stackLast <= NSBIDI_MAX_EXPLICIT_LEVEL) { + dirProps[isolateStartStack[stackLast]] = LRI; + flags |= DIRPROP_FLAG(LRI); + } + state = LOOKING_FOR_PDI; + } + break; + + case R: case AL: + if (state == SEEKING_STRONG_FOR_PARA) { + mParaLevel = 1; + state = NOT_SEEKING_STRONG; + } else if (state == SEEKING_STRONG_FOR_FSI) { + if (stackLast <= NSBIDI_MAX_EXPLICIT_LEVEL) { + dirProps[isolateStartStack[stackLast]] = RLI; + flags |= DIRPROP_FLAG(RLI); + } + state = LOOKING_FOR_PDI; + } + break; + + case FSI: case LRI: case RLI: + stackLast++; + if (stackLast <= NSBIDI_MAX_EXPLICIT_LEVEL) { + isolateStartStack[stackLast] = i - 1; + previousStateStack[stackLast] = state; + } + if (dirProp == FSI) { + state = SEEKING_STRONG_FOR_FSI; + } else { + state = LOOKING_FOR_PDI; + } + break; + + case PDI: + if (state == SEEKING_STRONG_FOR_FSI) { + if (stackLast <= NSBIDI_MAX_EXPLICIT_LEVEL) { + dirProps[isolateStartStack[stackLast]] = LRI; + flags |= DIRPROP_FLAG(LRI); + } + } + if (stackLast >= 0) { + if (stackLast <= NSBIDI_MAX_EXPLICIT_LEVEL) { + state = previousStateStack[stackLast]; + } + stackLast--; + } + break; + + case B: + // This shouldn't happen, since we don't support multiple paragraphs. + NS_NOTREACHED("Unexpected paragraph separator"); + break; + + default: + break; + } + } + + /* Ignore still open isolate sequences with overflow */ + if (stackLast > NSBIDI_MAX_EXPLICIT_LEVEL) { + stackLast = NSBIDI_MAX_EXPLICIT_LEVEL; + if (dirProps[previousStateStack[NSBIDI_MAX_EXPLICIT_LEVEL]] != FSI) { + state = LOOKING_FOR_PDI; + } + } + + /* Resolve direction of still unresolved open FSI sequences */ + while (stackLast >= 0) { + if (state == SEEKING_STRONG_FOR_FSI) { + dirProps[isolateStartStack[stackLast]] = LRI; + flags |= DIRPROP_FLAG(LRI); + } + state = previousStateStack[stackLast]; + stackLast--; + } + + flags|=DIRPROP_FLAG_LR(mParaLevel); + + mFlags = flags; +} + +/* Functions for handling paired brackets ----------------------------------- */ + +/* In the mIsoRuns array, the first entry is used for text outside of any + isolate sequence. Higher entries are used for each more deeply nested + isolate sequence. + mIsoRunLast is the index of the last used entry. + The mOpenings array is used to note the data of opening brackets not yet + matched by a closing bracket, or matched but still susceptible to change + level. + Each isoRun entry contains the index of the first and + one-after-last openings entries for pending opening brackets it + contains. The next mOpenings entry to use is the one-after-last of the + most deeply nested isoRun entry. + mIsoRuns entries also contain their current embedding level and the bidi + class of the last-encountered strong character, since these will be needed + to resolve the level of paired brackets. */ + +nsBidi::BracketData::BracketData(const nsBidi *aBidi) +{ + mIsoRunLast = 0; + mIsoRuns[0].start = 0; + mIsoRuns[0].limit = 0; + mIsoRuns[0].level = aBidi->mParaLevel; + mIsoRuns[0].lastStrong = mIsoRuns[0].lastBase = mIsoRuns[0].contextDir = + GET_LR_FROM_LEVEL(aBidi->mParaLevel); + mIsoRuns[0].contextPos = 0; + mOpenings = mSimpleOpenings; + mOpeningsCount = SIMPLE_OPENINGS_COUNT; + mOpeningsMemory = nullptr; +} + +nsBidi::BracketData::~BracketData() +{ + free(mOpeningsMemory); +} + +/* LRE, LRO, RLE, RLO, PDF */ +void +nsBidi::BracketData::ProcessBoundary(int32_t aLastDirControlCharPos, + nsBidiLevel aContextLevel, + nsBidiLevel aEmbeddingLevel, + const DirProp* aDirProps) +{ + IsoRun& lastIsoRun = mIsoRuns[mIsoRunLast]; + if (DIRPROP_FLAG(aDirProps[aLastDirControlCharPos]) & MASK_ISO) { /* after an isolate */ + return; + } + if (NO_OVERRIDE(aEmbeddingLevel) > NO_OVERRIDE(aContextLevel)) { /* not PDF */ + aContextLevel = aEmbeddingLevel; + } + lastIsoRun.limit = lastIsoRun.start; + lastIsoRun.level = aEmbeddingLevel; + lastIsoRun.lastStrong = lastIsoRun.lastBase = lastIsoRun.contextDir = + GET_LR_FROM_LEVEL(aContextLevel); + lastIsoRun.contextPos = aLastDirControlCharPos; +} + +/* LRI or RLI */ +void +nsBidi::BracketData::ProcessLRI_RLI(nsBidiLevel aLevel) +{ + MOZ_ASSERT(mIsoRunLast <= NSBIDI_MAX_EXPLICIT_LEVEL); + IsoRun& lastIsoRun = mIsoRuns[mIsoRunLast]; + lastIsoRun.lastBase = O_N; + IsoRun& currIsoRun = mIsoRuns[++mIsoRunLast]; + currIsoRun.start = currIsoRun.limit = lastIsoRun.limit; + currIsoRun.level = aLevel; + currIsoRun.lastStrong = currIsoRun.lastBase = currIsoRun.contextDir = + GET_LR_FROM_LEVEL(aLevel); + currIsoRun.contextPos = 0; +} + +/* PDI */ +void +nsBidi::BracketData::ProcessPDI() +{ + MOZ_ASSERT(mIsoRunLast > 0); + mIsoRuns[--mIsoRunLast].lastBase = O_N; +} + +/* newly found opening bracket: create an openings entry */ +bool /* return true if success */ +nsBidi::BracketData::AddOpening(char16_t aMatch, int32_t aPosition) +{ + IsoRun& lastIsoRun = mIsoRuns[mIsoRunLast]; + if (lastIsoRun.limit >= mOpeningsCount) { /* no available new entry */ + if (!GETOPENINGSMEMORY(lastIsoRun.limit * 2)) { + return false; + } + if (mOpenings == mSimpleOpenings) { + memcpy(mOpeningsMemory, mSimpleOpenings, + SIMPLE_OPENINGS_COUNT * sizeof(Opening)); + } + mOpenings = mOpeningsMemory; /* may have changed */ + mOpeningsCount = mOpeningsSize / sizeof(Opening); + } + Opening& o = mOpenings[lastIsoRun.limit]; + o.position = aPosition; + o.match = aMatch; + o.contextDir = lastIsoRun.contextDir; + o.contextPos = lastIsoRun.contextPos; + o.flags = 0; + lastIsoRun.limit++; + return true; +} + +/* change N0c1 to N0c2 when a preceding bracket is assigned the embedding level */ +void +nsBidi::BracketData::FixN0c(int32_t aOpeningIndex, int32_t aNewPropPosition, + DirProp aNewProp, DirProp* aDirProps) +{ + /* This function calls itself recursively */ + IsoRun& lastIsoRun = mIsoRuns[mIsoRunLast]; + for (int32_t k = aOpeningIndex + 1; k < lastIsoRun.limit; k++) { + Opening& o = mOpenings[k]; + if (o.match >= 0) { /* not an N0c match */ + continue; + } + if (aNewPropPosition < o.contextPos) { + break; + } + int32_t openingPosition = o.position; + if (aNewPropPosition >= openingPosition) { + continue; + } + if (aNewProp == o.contextDir) { + break; + } + aDirProps[openingPosition] = aNewProp; + int32_t closingPosition = -(o.match); + aDirProps[closingPosition] = aNewProp; + o.match = 0; /* prevent further changes */ + FixN0c(k, openingPosition, aNewProp, aDirProps); + FixN0c(k, closingPosition, aNewProp, aDirProps); + } +} + +/* process closing bracket */ +DirProp /* return L or R if N0b or N0c, ON if N0d */ +nsBidi::BracketData::ProcessClosing(int32_t aOpenIdx, int32_t aPosition, + DirProp* aDirProps) +{ + IsoRun& lastIsoRun = mIsoRuns[mIsoRunLast]; + Opening& o = mOpenings[aOpenIdx]; + DirProp newProp; + DirProp direction = GET_LR_FROM_LEVEL(lastIsoRun.level); + bool stable = true; // assume stable until proved otherwise + + /* The stable flag is set when brackets are paired and their + level is resolved and cannot be changed by what will be + found later in the source string. + An unstable match can occur only when applying N0c, where + the resolved level depends on the preceding context, and + this context may be affected by text occurring later. + Example: RTL paragraph containing: abc[(latin) HEBREW] + When the closing parenthesis is encountered, it appears + that N0c1 must be applied since 'abc' sets an opposite + direction context and both parentheses receive level 2. + However, when the closing square bracket is processed, + N0b applies because of 'HEBREW' being included within the + brackets, thus the square brackets are treated like R and + receive level 1. However, this changes the preceding + context of the opening parenthesis, and it now appears + that N0c2 must be applied to the parentheses rather than + N0c1. */ + + if ((direction == 0 && o.flags & FOUND_L) || + (direction == 1 && o.flags & FOUND_R)) { /* N0b */ + newProp = direction; + } else if (o.flags & (FOUND_L|FOUND_R)) { /* N0c */ + /* it is stable if there is no containing pair or in + conditions too complicated and not worth checking */ + stable = (aOpenIdx == lastIsoRun.start); + if (direction != o.contextDir) { + newProp = o.contextDir; /* N0c1 */ + } else { + newProp = direction; /* N0c2 */ + } + } else { + /* forget this and any brackets nested within this pair */ + lastIsoRun.limit = aOpenIdx; + return O_N; /* N0d */ + } + aDirProps[o.position] = newProp; + aDirProps[aPosition] = newProp; + /* Update nested N0c pairs that may be affected */ + FixN0c(aOpenIdx, o.position, newProp, aDirProps); + if (stable) { + /* forget any brackets nested within this pair */ + lastIsoRun.limit = aOpenIdx; + } else { + int32_t k; + o.match = -aPosition; + /* neutralize any unmatched opening between the current pair */ + for (k = aOpenIdx + 1; k < lastIsoRun.limit; k++) { + Opening& oo = mOpenings[k]; + if (oo.position > aPosition) { + break; + } + if (oo.match > 0) { + oo.match = 0; + } + } + } + return newProp; +} + +static inline bool +IsMatchingCloseBracket(char16_t aCh1, char16_t aCh2) +{ + // U+232A RIGHT-POINTING ANGLE BRACKET and U+3009 RIGHT ANGLE BRACKET + // are canonical equivalents, so we special-case them here. + return (aCh1 == aCh2) || + (aCh1 == 0x232A && aCh2 == 0x3009) || + (aCh2 == 0x232A && aCh1 == 0x3009); +} + +/* Handle strong characters, digits and candidates for closing brackets. */ +/* Returns true if success. (The only failure mode is an OOM when trying + to allocate memory for the Openings array.) */ +bool +nsBidi::BracketData::ProcessChar(int32_t aPosition, char16_t aCh, + DirProp* aDirProps, nsBidiLevel* aLevels) +{ + IsoRun& lastIsoRun = mIsoRuns[mIsoRunLast]; + DirProp newProp; + DirProp dirProp = aDirProps[aPosition]; + nsBidiLevel level = aLevels[aPosition]; + if (dirProp == O_N) { + /* First see if it is a matching closing bracket. Hopefully, this is + more efficient than checking if it is a closing bracket at all */ + for (int32_t idx = lastIsoRun.limit - 1; idx >= lastIsoRun.start; idx--) { + if (!IsMatchingCloseBracket(aCh, mOpenings[idx].match)) { + continue; + } + /* We have a match */ + newProp = ProcessClosing(idx, aPosition, aDirProps); + if (newProp == O_N) { /* N0d */ + aCh = 0; /* prevent handling as an opening */ + break; + } + lastIsoRun.lastBase = O_N; + lastIsoRun.contextDir = newProp; + lastIsoRun.contextPos = aPosition; + if (level & NSBIDI_LEVEL_OVERRIDE) { /* X4, X5 */ + newProp = GET_LR_FROM_LEVEL(level); + lastIsoRun.lastStrong = newProp; + uint16_t flag = DIRPROP_FLAG(newProp); + for (int32_t i = lastIsoRun.start; i < idx; i++) { + mOpenings[i].flags |= flag; + } + /* matching brackets are not overridden by LRO/RLO */ + aLevels[aPosition] &= ~NSBIDI_LEVEL_OVERRIDE; + } + /* matching brackets are not overridden by LRO/RLO */ + aLevels[mOpenings[idx].position] &= ~NSBIDI_LEVEL_OVERRIDE; + return true; + } + /* We get here only if the ON character is not a matching closing + bracket or it is a case of N0d */ + /* Now see if it is an opening bracket */ + char16_t match = GetPairedBracket(aCh); + if (match != aCh && /* has a matching char */ + GetPairedBracketType(aCh) == PAIRED_BRACKET_TYPE_OPEN) { /* opening bracket */ + if (!AddOpening(match, aPosition)) { + return false; + } + } + } + if (level & NSBIDI_LEVEL_OVERRIDE) { /* X4, X5 */ + newProp = GET_LR_FROM_LEVEL(level); + if (dirProp != S && dirProp != WS && dirProp != O_N) { + aDirProps[aPosition] = newProp; + } + lastIsoRun.lastBase = newProp; + lastIsoRun.lastStrong = newProp; + lastIsoRun.contextDir = newProp; + lastIsoRun.contextPos = aPosition; + } else if (IS_STRONG_TYPE(dirProp)) { + newProp = DirFromStrong(dirProp); + lastIsoRun.lastBase = dirProp; + lastIsoRun.lastStrong = dirProp; + lastIsoRun.contextDir = newProp; + lastIsoRun.contextPos = aPosition; + } else if (dirProp == EN) { + lastIsoRun.lastBase = EN; + if (lastIsoRun.lastStrong == L) { + newProp = L; /* W7 */ + aDirProps[aPosition] = ENL; + lastIsoRun.contextDir = L; + lastIsoRun.contextPos = aPosition; + } else { + newProp = R; /* N0 */ + if (lastIsoRun.lastStrong == AL) { + aDirProps[aPosition] = AN; /* W2 */ + } else { + aDirProps[aPosition] = ENR; + } + lastIsoRun.contextDir = R; + lastIsoRun.contextPos = aPosition; + } + } else if (dirProp == AN) { + newProp = R; /* N0 */ + lastIsoRun.lastBase = AN; + lastIsoRun.contextDir = R; + lastIsoRun.contextPos = aPosition; + } else if (dirProp == NSM) { + /* if the last real char was ON, change NSM to ON so that it + will stay ON even if the last real char is a bracket which + may be changed to L or R */ + newProp = lastIsoRun.lastBase; + if (newProp == O_N) { + aDirProps[aPosition] = newProp; + } + } else { + newProp = dirProp; + lastIsoRun.lastBase = dirProp; + } + if (IS_STRONG_TYPE(newProp)) { + uint16_t flag = DIRPROP_FLAG(DirFromStrong(newProp)); + for (int32_t i = lastIsoRun.start; i < lastIsoRun.limit; i++) { + if (aPosition > mOpenings[i].position) { + mOpenings[i].flags |= flag; + } + } + } + return true; +} + +/* perform (X1)..(X9) ------------------------------------------------------- */ + +/* + * Resolve the explicit levels as specified by explicit embedding codes. + * Recalculate the flags to have them reflect the real properties + * after taking the explicit embeddings into account. + * + * The Bidi algorithm is designed to result in the same behavior whether embedding + * levels are externally specified (from "styled text", supposedly the preferred + * method) or set by explicit embedding codes (LRx, RLx, PDF, FSI, PDI) in the plain text. + * That is why (X9) instructs to remove all not-isolate explicit codes (and BN). + * However, in a real implementation, this removal of these codes and their index + * positions in the plain text is undesirable since it would result in + * reallocated, reindexed text. + * Instead, this implementation leaves the codes in there and just ignores them + * in the subsequent processing. + * In order to get the same reordering behavior, positions with a BN or a not-isolate + * explicit embedding code just get the same level assigned as the last "real" + * character. + * + * Some implementations, not this one, then overwrite some of these + * directionality properties at "real" same-level-run boundaries by + * L or R codes so that the resolution of weak types can be performed on the + * entire paragraph at once instead of having to parse it once more and + * perform that resolution on same-level-runs. + * This limits the scope of the implicit rules in effectively + * the same way as the run limits. + * + * Instead, this implementation does not modify these codes. + * On one hand, the paragraph has to be scanned for same-level-runs, but + * on the other hand, this saves another loop to reset these codes, + * or saves making and modifying a copy of dirProps[]. + * + * + * Note that (Pn) and (Xn) changed significantly from version 4 of the Bidi algorithm. + * + * + * Handling the stack of explicit levels (Xn): + * + * With the Bidi stack of explicit levels, as pushed with each + * LRE, RLE, LRO, and RLO, LRI, RLI, and FSI and popped with each PDF and PDI, + * the explicit level must never exceed NSBIDI_MAX_EXPLICIT_LEVEL. + * + * In order to have a correct push-pop semantics even in the case of overflows, + * overflow counters and a valid isolate counter are used as described in UAX#9 + * section 3.3.2 "Explicit Levels and Direction". + * + * This implementation assumes that NSBIDI_MAX_EXPLICIT_LEVEL is odd. + */ + +void nsBidi::ResolveExplicitLevels(nsBidiDirection *aDirection, const char16_t *aText) +{ + DirProp *dirProps=mDirProps; + nsBidiLevel *levels=mLevels; + + int32_t i=0, length=mLength; + Flags flags=mFlags; /* collect all directionalities in the text */ + DirProp dirProp; + nsBidiLevel level=mParaLevel; + nsBidiDirection direction; + + mIsolateCount = 0; + + /* determine if the text is mixed-directional or single-directional */ + direction=DirectionFromFlags(flags); + + /* we may not need to resolve any explicit levels */ + if(direction!=NSBIDI_MIXED) { + /* not mixed directionality: levels don't matter - trailingWSStart will be 0 */ + } else if(!(flags&(MASK_EXPLICIT|MASK_ISO))) { + BracketData bracketData(this); + /* no embeddings, set all levels to the paragraph level */ + for(i=0; i<length; ++i) { + levels[i]=level; + if (dirProps[i] == BN) { + continue; + } + if (!bracketData.ProcessChar(i, aText[i], mDirProps, mLevels)) { + NS_WARNING("BracketData::ProcessChar failed, out of memory?"); + // Ran out of memory for deeply-nested openings; give up and + // return LTR. This could presumably result in incorrect display, + // but in practice it won't happen except in some artificially- + // constructed torture test -- which is just as likely to die + // altogether with an OOM failure. + *aDirection = NSBIDI_LTR; + return; + } + } + } else { + /* continue to perform (Xn) */ + + /* (X1) level is set for all codes, embeddingLevel keeps track of the push/pop operations */ + /* both variables may carry the NSBIDI_LEVEL_OVERRIDE flag to indicate the override status */ + nsBidiLevel embeddingLevel = level, newLevel; + nsBidiLevel previousLevel = level; /* previous level for regular (not CC) characters */ + int32_t lastDirControlCharPos = 0; /* index of last effective LRx,RLx, PDx */ + + uint16_t stack[NSBIDI_MAX_EXPLICIT_LEVEL + 2]; /* we never push anything >=NSBIDI_MAX_EXPLICIT_LEVEL + but we need one more entry as base */ + int32_t stackLast = 0; + int32_t overflowIsolateCount = 0; + int32_t overflowEmbeddingCount = 0; + int32_t validIsolateCount = 0; + + BracketData bracketData(this); + + stack[0] = level; + + /* recalculate the flags */ + flags=0; + + /* since we assume that this is a single paragraph, we ignore (X8) */ + for(i=0; i<length; ++i) { + dirProp=dirProps[i]; + switch(dirProp) { + case LRE: + case RLE: + case LRO: + case RLO: + /* (X2, X3, X4, X5) */ + flags |= DIRPROP_FLAG(BN); + levels[i] = previousLevel; + if (dirProp == LRE || dirProp == LRO) { + newLevel = (embeddingLevel + 2) & ~(NSBIDI_LEVEL_OVERRIDE | 1); /* least greater even level */ + } else { + newLevel = ((embeddingLevel & ~NSBIDI_LEVEL_OVERRIDE) + 1) | 1; /* least greater odd level */ + } + if(newLevel <= NSBIDI_MAX_EXPLICIT_LEVEL && overflowIsolateCount == 0 && overflowEmbeddingCount == 0) { + lastDirControlCharPos = i; + embeddingLevel = newLevel; + if (dirProp == LRO || dirProp == RLO) { + embeddingLevel |= NSBIDI_LEVEL_OVERRIDE; + } + stackLast++; + stack[stackLast] = embeddingLevel; + /* we don't need to set NSBIDI_LEVEL_OVERRIDE off for LRE and RLE + since this has already been done for newLevel which is + the source for embeddingLevel. + */ + } else { + if (overflowIsolateCount == 0) { + overflowEmbeddingCount++; + } + } + break; + + case PDF: + /* (X7) */ + flags |= DIRPROP_FLAG(BN); + levels[i] = previousLevel; + /* handle all the overflow cases first */ + if (overflowIsolateCount) { + break; + } + if (overflowEmbeddingCount) { + overflowEmbeddingCount--; + break; + } + if (stackLast > 0 && stack[stackLast] < ISOLATE) { /* not an isolate entry */ + lastDirControlCharPos = i; + stackLast--; + embeddingLevel = stack[stackLast]; + } + break; + + case LRI: + case RLI: + flags |= DIRPROP_FLAG(O_N) | DIRPROP_FLAG_LR(embeddingLevel); + levels[i] = NO_OVERRIDE(embeddingLevel); + if (NO_OVERRIDE(embeddingLevel) != NO_OVERRIDE(previousLevel)) { + bracketData.ProcessBoundary(lastDirControlCharPos, previousLevel, + embeddingLevel, mDirProps); + flags |= DIRPROP_FLAG_MULTI_RUNS; + } + previousLevel = embeddingLevel; + /* (X5a, X5b) */ + if (dirProp == LRI) { + newLevel = (embeddingLevel + 2) & ~(NSBIDI_LEVEL_OVERRIDE | 1); /* least greater even level */ + } else { + newLevel = ((embeddingLevel & ~NSBIDI_LEVEL_OVERRIDE) + 1) | 1; /* least greater odd level */ + } + if (newLevel <= NSBIDI_MAX_EXPLICIT_LEVEL && overflowIsolateCount == 0 && overflowEmbeddingCount == 0) { + flags |= DIRPROP_FLAG(dirProp); + lastDirControlCharPos = i; + previousLevel = embeddingLevel; + validIsolateCount++; + if (validIsolateCount > mIsolateCount) { + mIsolateCount = validIsolateCount; + } + embeddingLevel = newLevel; + stackLast++; + stack[stackLast] = embeddingLevel + ISOLATE; + bracketData.ProcessLRI_RLI(embeddingLevel); + } else { + /* make it so that it is handled by AdjustWSLevels() */ + dirProps[i] = WS; + overflowIsolateCount++; + } + break; + + case PDI: + if (NO_OVERRIDE(embeddingLevel) != NO_OVERRIDE(previousLevel)) { + bracketData.ProcessBoundary(lastDirControlCharPos, previousLevel, + embeddingLevel, mDirProps); + flags |= DIRPROP_FLAG_MULTI_RUNS; + } + /* (X6a) */ + if (overflowIsolateCount) { + overflowIsolateCount--; + /* make it so that it is handled by AdjustWSLevels() */ + dirProps[i] = WS; + } else if (validIsolateCount) { + flags |= DIRPROP_FLAG(PDI); + lastDirControlCharPos = i; + overflowEmbeddingCount = 0; + while (stack[stackLast] < ISOLATE) { + /* pop embedding entries */ + /* until the last isolate entry */ + stackLast--; + + // Since validIsolateCount is true, there must be an isolate entry + // on the stack, so the stack is guaranteed to not be empty. + // Still, to eliminate a warning from coverity, we use an assertion. + MOZ_ASSERT(stackLast > 0); + } + stackLast--; /* pop also the last isolate entry */ + MOZ_ASSERT(stackLast >= 0); // For coverity + validIsolateCount--; + bracketData.ProcessPDI(); + } else { + /* make it so that it is handled by AdjustWSLevels() */ + dirProps[i] = WS; + } + embeddingLevel = stack[stackLast] & ~ISOLATE; + flags |= DIRPROP_FLAG(O_N) | DIRPROP_FLAG_LR(embeddingLevel); + previousLevel = embeddingLevel; + levels[i] = NO_OVERRIDE(embeddingLevel); + break; + + case B: + /* + * We do not expect to see a paragraph separator (B), + */ + NS_NOTREACHED("Unexpected paragraph separator"); + break; + + case BN: + /* BN, LRE, RLE, and PDF are supposed to be removed (X9) */ + /* they will get their levels set correctly in AdjustWSLevels() */ + levels[i] = previousLevel; + flags |= DIRPROP_FLAG(BN); + break; + + default: + /* all other types get the "real" level */ + if (NO_OVERRIDE(embeddingLevel) != NO_OVERRIDE(previousLevel)) { + bracketData.ProcessBoundary(lastDirControlCharPos, previousLevel, + embeddingLevel, mDirProps); + flags |= DIRPROP_FLAG_MULTI_RUNS; + if (embeddingLevel & NSBIDI_LEVEL_OVERRIDE) { + flags |= DIRPROP_FLAG_O(embeddingLevel); + } else { + flags |= DIRPROP_FLAG_E(embeddingLevel); + } + } + previousLevel = embeddingLevel; + levels[i] = embeddingLevel; + if (!bracketData.ProcessChar(i, aText[i], mDirProps, mLevels)) { + NS_WARNING("BracketData::ProcessChar failed, out of memory?"); + *aDirection = NSBIDI_LTR; + return; + } + flags |= DIRPROP_FLAG(dirProps[i]); + break; + } + } + + if(flags&MASK_EMBEDDING) { + flags|=DIRPROP_FLAG_LR(mParaLevel); + } + + /* subsequently, ignore the explicit codes and BN (X9) */ + + /* again, determine if the text is mixed-directional or single-directional */ + mFlags=flags; + direction=DirectionFromFlags(flags); + } + + *aDirection = direction; +} + +/* determine if the text is mixed-directional or single-directional */ +nsBidiDirection nsBidi::DirectionFromFlags(Flags aFlags) +{ + /* if the text contains AN and neutrals, then some neutrals may become RTL */ + if(!(aFlags&MASK_RTL || (aFlags&DIRPROP_FLAG(AN) && aFlags&MASK_POSSIBLE_N))) { + return NSBIDI_LTR; + } else if(!(aFlags&MASK_LTR)) { + return NSBIDI_RTL; + } else { + return NSBIDI_MIXED; + } +} + +/****************************************************************** + The Properties state machine table +******************************************************************* + + All table cells are 8 bits: + bits 0..4: next state + bits 5..7: action to perform (if > 0) + + Cells may be of format "n" where n represents the next state + (except for the rightmost column). + Cells may also be of format "s(x,y)" where x represents an action + to perform and y represents the next state. + +******************************************************************* + Definitions and type for properties state table +******************************************************************* +*/ +#define IMPTABPROPS_COLUMNS 16 +#define IMPTABPROPS_RES (IMPTABPROPS_COLUMNS - 1) +#define GET_STATEPROPS(cell) ((cell)&0x1f) +#define GET_ACTIONPROPS(cell) ((cell)>>5) +#undef s +#define s(action, newState) ((uint8_t)(newState+(action<<5))) + +static const uint8_t groupProp[] = /* dirProp regrouped */ +{ +/* L R EN ES ET AN CS B S WS ON LRE LRO AL RLE RLO PDF NSM BN FSI LRI RLI PDI ENL ENR */ + 0, 1, 2, 7, 8, 3, 9, 6, 5, 4, 4, 10, 10, 12, 10, 10, 10, 11, 10, 4, 4, 4, 4, 13, 14 +}; + +/****************************************************************** + + PROPERTIES STATE TABLE + + In table impTabProps, + - the ON column regroups ON and WS, FSI, RLI, LRI and PDI + - the BN column regroups BN, LRE, RLE, LRO, RLO, PDF + - the Res column is the reduced property assigned to a run + + Action 1: process current run1, init new run1 + 2: init new run2 + 3: process run1, process run2, init new run1 + 4: process run1, set run1=run2, init new run2 + + Notes: + 1) This table is used in ResolveImplicitLevels(). + 2) This table triggers actions when there is a change in the Bidi + property of incoming characters (action 1). + 3) Most such property sequences are processed immediately (in + fact, passed to ProcessPropertySeq(). + 4) However, numbers are assembled as one sequence. This means + that undefined situations (like CS following digits, until + it is known if the next char will be a digit) are held until + following chars define them. + Example: digits followed by CS, then comes another CS or ON; + the digits will be processed, then the CS assigned + as the start of an ON sequence (action 3). + 5) There are cases where more than one sequence must be + processed, for instance digits followed by CS followed by L: + the digits must be processed as one sequence, and the CS + must be processed as an ON sequence, all this before starting + assembling chars for the opening L sequence. + + +*/ +static const uint8_t impTabProps[][IMPTABPROPS_COLUMNS] = +{ +/* L , R , EN , AN , ON , S , B , ES , ET , CS , BN , NSM , AL , ENL , ENR , Res */ +/* 0 Init */ { 1 , 2 , 4 , 5 , 7 , 15 , 17 , 7 , 9 , 7 , 0 , 7 , 3 , 18 , 21 , DirProp_ON }, +/* 1 L */ { 1 , s(1,2), s(1,4), s(1,5), s(1,7),s(1,15),s(1,17), s(1,7), s(1,9), s(1,7), 1 , 1 , s(1,3),s(1,18),s(1,21), DirProp_L }, +/* 2 R */ { s(1,1), 2 , s(1,4), s(1,5), s(1,7),s(1,15),s(1,17), s(1,7), s(1,9), s(1,7), 2 , 2 , s(1,3),s(1,18),s(1,21), DirProp_R }, +/* 3 AL */ { s(1,1), s(1,2), s(1,6), s(1,6), s(1,8),s(1,16),s(1,17), s(1,8), s(1,8), s(1,8), 3 , 3 , 3 ,s(1,18),s(1,21), DirProp_R }, +/* 4 EN */ { s(1,1), s(1,2), 4 , s(1,5), s(1,7),s(1,15),s(1,17),s(2,10), 11 ,s(2,10), 4 , 4 , s(1,3), 18 , 21 , DirProp_EN }, +/* 5 AN */ { s(1,1), s(1,2), s(1,4), 5 , s(1,7),s(1,15),s(1,17), s(1,7), s(1,9),s(2,12), 5 , 5 , s(1,3),s(1,18),s(1,21), DirProp_AN }, +/* 6 AL:EN/AN */ { s(1,1), s(1,2), 6 , 6 , s(1,8),s(1,16),s(1,17), s(1,8), s(1,8),s(2,13), 6 , 6 , s(1,3), 18 , 21 , DirProp_AN }, +/* 7 ON */ { s(1,1), s(1,2), s(1,4), s(1,5), 7 ,s(1,15),s(1,17), 7 ,s(2,14), 7 , 7 , 7 , s(1,3),s(1,18),s(1,21), DirProp_ON }, +/* 8 AL:ON */ { s(1,1), s(1,2), s(1,6), s(1,6), 8 ,s(1,16),s(1,17), 8 , 8 , 8 , 8 , 8 , s(1,3),s(1,18),s(1,21), DirProp_ON }, +/* 9 ET */ { s(1,1), s(1,2), 4 , s(1,5), 7 ,s(1,15),s(1,17), 7 , 9 , 7 , 9 , 9 , s(1,3), 18 , 21 , DirProp_ON }, +/*10 EN+ES/CS */ { s(3,1), s(3,2), 4 , s(3,5), s(4,7),s(3,15),s(3,17), s(4,7),s(4,14), s(4,7), 10 , s(4,7), s(3,3), 18 , 21 , DirProp_EN }, +/*11 EN+ET */ { s(1,1), s(1,2), 4 , s(1,5), s(1,7),s(1,15),s(1,17), s(1,7), 11 , s(1,7), 11 , 11 , s(1,3), 18 , 21 , DirProp_EN }, +/*12 AN+CS */ { s(3,1), s(3,2), s(3,4), 5 , s(4,7),s(3,15),s(3,17), s(4,7),s(4,14), s(4,7), 12 , s(4,7), s(3,3),s(3,18),s(3,21), DirProp_AN }, +/*13 AL:EN/AN+CS */ { s(3,1), s(3,2), 6 , 6 , s(4,8),s(3,16),s(3,17), s(4,8), s(4,8), s(4,8), 13 , s(4,8), s(3,3), 18 , 21 , DirProp_AN }, +/*14 ON+ET */ { s(1,1), s(1,2), s(4,4), s(1,5), 7 ,s(1,15),s(1,17), 7 , 14 , 7 , 14 , 14 , s(1,3),s(4,18),s(4,21), DirProp_ON }, +/*15 S */ { s(1,1), s(1,2), s(1,4), s(1,5), s(1,7), 15 ,s(1,17), s(1,7), s(1,9), s(1,7), 15 , s(1,7), s(1,3),s(1,18),s(1,21), DirProp_S }, +/*16 AL:S */ { s(1,1), s(1,2), s(1,6), s(1,6), s(1,8), 16 ,s(1,17), s(1,8), s(1,8), s(1,8), 16 , s(1,8), s(1,3),s(1,18),s(1,21), DirProp_S }, +/*17 B */ { s(1,1), s(1,2), s(1,4), s(1,5), s(1,7),s(1,15), 17 , s(1,7), s(1,9), s(1,7), 17 , s(1,7), s(1,3),s(1,18),s(1,21), DirProp_B }, +/*18 ENL */ { s(1,1), s(1,2), 18 , s(1,5), s(1,7),s(1,15),s(1,17),s(2,19), 20 ,s(2,19), 18 , 18 , s(1,3), 18 , 21 , DirProp_L }, +/*19 ENL+ES/CS */ { s(3,1), s(3,2), 18 , s(3,5), s(4,7),s(3,15),s(3,17), s(4,7),s(4,14), s(4,7), 19 , s(4,7), s(3,3), 18 , 21 , DirProp_L }, +/*20 ENL+ET */ { s(1,1), s(1,2), 18 , s(1,5), s(1,7),s(1,15),s(1,17), s(1,7), 20 , s(1,7), 20 , 20 , s(1,3), 18 , 21 , DirProp_L }, +/*21 ENR */ { s(1,1), s(1,2), 21 , s(1,5), s(1,7),s(1,15),s(1,17),s(2,22), 23 ,s(2,22), 21 , 21 , s(1,3), 18 , 21 , DirProp_AN }, +/*22 ENR+ES/CS */ { s(3,1), s(3,2), 21 , s(3,5), s(4,7),s(3,15),s(3,17), s(4,7),s(4,14), s(4,7), 22 , s(4,7), s(3,3), 18 , 21 , DirProp_AN }, +/*23 ENR+ET */ { s(1,1), s(1,2), 21 , s(1,5), s(1,7),s(1,15),s(1,17), s(1,7), 23 , s(1,7), 23 , 23 , s(1,3), 18 , 21 , DirProp_AN } +}; + +/* we must undef macro s because the levels table have a different + * structure (4 bits for action and 4 bits for next state. + */ +#undef s + +/****************************************************************** + The levels state machine tables +******************************************************************* + + All table cells are 8 bits: + bits 0..3: next state + bits 4..7: action to perform (if > 0) + + Cells may be of format "n" where n represents the next state + (except for the rightmost column). + Cells may also be of format "s(x,y)" where x represents an action + to perform and y represents the next state. + + This format limits each table to 16 states each and to 15 actions. + +******************************************************************* + Definitions and type for levels state tables +******************************************************************* +*/ +#define IMPTABLEVELS_RES (IMPTABLEVELS_COLUMNS - 1) +#define GET_STATE(cell) ((cell)&0x0f) +#define GET_ACTION(cell) ((cell)>>4) +#define s(action, newState) ((uint8_t)(newState+(action<<4))) + +/****************************************************************** + + LEVELS STATE TABLES + + In all levels state tables, + - state 0 is the initial state + - the Res column is the increment to add to the text level + for this property sequence. + + The impAct arrays for each table of a pair map the local action + numbers of the table to the total list of actions. For instance, + action 2 in a given table corresponds to the action number which + appears in entry [2] of the impAct array for that table. + The first entry of all impAct arrays must be 0. + + Action 1: init conditional sequence + 2: prepend conditional sequence to current sequence + 3: set ON sequence to new level - 1 + 4: init EN/AN/ON sequence + 5: fix EN/AN/ON sequence followed by R + 6: set previous level sequence to level 2 + + Notes: + 1) These tables are used in ProcessPropertySeq(). The input + is property sequences as determined by ResolveImplicitLevels. + 2) Most such property sequences are processed immediately + (levels are assigned). + 3) However, some sequences cannot be assigned a final level till + one or more following sequences are received. For instance, + ON following an R sequence within an even-level paragraph. + If the following sequence is R, the ON sequence will be + assigned basic run level+1, and so will the R sequence. + 4) S is generally handled like ON, since its level will be fixed + to paragraph level in AdjustWSLevels(). + +*/ + +static const ImpTab impTabL = /* Even paragraph level */ +/* In this table, conditional sequences receive the higher possible level + until proven otherwise. +*/ +{ +/* L , R , EN , AN , ON , S , B , Res */ +/* 0 : init */ { 0 , 1 , 0 , 2 , 0 , 0 , 0 , 0 }, +/* 1 : R */ { 0 , 1 , 3 , 3 , s(1,4), s(1,4), 0 , 1 }, +/* 2 : AN */ { 0 , 1 , 0 , 2 , s(1,5), s(1,5), 0 , 2 }, +/* 3 : R+EN/AN */ { 0 , 1 , 3 , 3 , s(1,4), s(1,4), 0 , 2 }, +/* 4 : R+ON */ { s(2,0), 1 , 3 , 3 , 4 , 4 , s(2,0), 1 }, +/* 5 : AN+ON */ { s(2,0), 1 , s(2,0), 2 , 5 , 5 , s(2,0), 1 } +}; +static const ImpTab impTabR = /* Odd paragraph level */ +/* In this table, conditional sequences receive the lower possible level + until proven otherwise. +*/ +{ +/* L , R , EN , AN , ON , S , B , Res */ +/* 0 : init */ { 1 , 0 , 2 , 2 , 0 , 0 , 0 , 0 }, +/* 1 : L */ { 1 , 0 , 1 , 3 , s(1,4), s(1,4), 0 , 1 }, +/* 2 : EN/AN */ { 1 , 0 , 2 , 2 , 0 , 0 , 0 , 1 }, +/* 3 : L+AN */ { 1 , 0 , 1 , 3 , 5 , 5 , 0 , 1 }, +/* 4 : L+ON */ { s(2,1), 0 , s(2,1), 3 , 4 , 4 , 0 , 0 }, +/* 5 : L+AN+ON */ { 1 , 0 , 1 , 3 , 5 , 5 , 0 , 0 } +}; + +#undef s + +static ImpAct impAct0 = {0,1,2,3,4,5,6}; +static PImpTab impTab[2] = {impTabL, impTabR}; + +/*------------------------------------------------------------------------*/ + +/* perform rules (Wn), (Nn), and (In) on a run of the text ------------------ */ + +/* + * This implementation of the (Wn) rules applies all rules in one pass. + * In order to do so, it needs a look-ahead of typically 1 character + * (except for W5: sequences of ET) and keeps track of changes + * in a rule Wp that affect a later Wq (p<q). + * + * The (Nn) and (In) rules are also performed in that same single loop, + * but effectively one iteration behind for white space. + * + * Since all implicit rules are performed in one step, it is not necessary + * to actually store the intermediate directional properties in dirProps[]. + */ + +void nsBidi::ProcessPropertySeq(LevState *pLevState, uint8_t _prop, int32_t start, int32_t limit) +{ + uint8_t cell, oldStateSeq, actionSeq; + PImpTab pImpTab = pLevState->pImpTab; + PImpAct pImpAct = pLevState->pImpAct; + nsBidiLevel* levels = mLevels; + nsBidiLevel level, addLevel; + int32_t start0, k; + + start0 = start; /* save original start position */ + oldStateSeq = (uint8_t)pLevState->state; + cell = pImpTab[oldStateSeq][_prop]; + pLevState->state = GET_STATE(cell); /* isolate the new state */ + actionSeq = pImpAct[GET_ACTION(cell)]; /* isolate the action */ + addLevel = pImpTab[pLevState->state][IMPTABLEVELS_RES]; + + if(actionSeq) { + switch(actionSeq) { + case 1: /* init ON seq */ + pLevState->startON = start0; + break; + + case 2: /* prepend ON seq to current seq */ + MOZ_ASSERT(pLevState->startON >= 0, "no valid ON sequence start!"); + start = pLevState->startON; + break; + + default: /* we should never get here */ + MOZ_ASSERT(false); + break; + } + } + if(addLevel || (start < start0)) { + level = pLevState->runLevel + addLevel; + if (start >= pLevState->runStart) { + for (k = start; k < limit; k++) { + levels[k] = level; + } + } else { + DirProp *dirProps = mDirProps, dirProp; + int32_t isolateCount = 0; + for (k = start; k < limit; k++) { + dirProp = dirProps[k]; + if (dirProp == PDI) { + isolateCount--; + } + if (isolateCount == 0) { + levels[k]=level; + } + if (dirProp == LRI || dirProp == RLI) { + isolateCount++; + } + } + } + } +} + +void nsBidi::ResolveImplicitLevels(int32_t aStart, int32_t aLimit, + DirProp aSOR, DirProp aEOR) +{ + const DirProp *dirProps = mDirProps; + DirProp dirProp; + LevState levState; + int32_t i, start1, start2; + uint16_t oldStateImp, stateImp, actionImp; + uint8_t gprop, resProp, cell; + + /* initialize for property and levels state tables */ + levState.runStart = aStart; + levState.runLevel = mLevels[aStart]; + levState.pImpTab = impTab[levState.runLevel & 1]; + levState.pImpAct = impAct0; + levState.startON = -1; /* initialize to invalid start position */ + + /* The isolates[] entries contain enough information to + resume the bidi algorithm in the same state as it was + when it was interrupted by an isolate sequence. */ + if (dirProps[aStart] == PDI && mIsolateCount >= 0) { + start1 = mIsolates[mIsolateCount].start1; + stateImp = mIsolates[mIsolateCount].stateImp; + levState.state = mIsolates[mIsolateCount].state; + mIsolateCount--; + } else { + levState.startON = -1; + start1 = aStart; + if (dirProps[aStart] == NSM) { + stateImp = 1 + aSOR; + } else { + stateImp = 0; + } + levState.state = 0; + ProcessPropertySeq(&levState, aSOR, aStart, aStart); + } + start2 = aStart; + + for (i = aStart; i <= aLimit; i++) { + if (i >= aLimit) { + int32_t k; + for (k = aLimit - 1; + k > aStart && (DIRPROP_FLAG(dirProps[k]) & MASK_BN_EXPLICIT); k--) { + // empty loop body + } + dirProp = mDirProps[k]; + if (dirProp == LRI || dirProp == RLI) { + break; /* no forced closing for sequence ending with LRI/RLI */ + } + gprop = aEOR; + } else { + DirProp prop; + prop = dirProps[i]; + gprop = groupProp[prop]; + } + oldStateImp = stateImp; + cell = impTabProps[oldStateImp][gprop]; + stateImp = GET_STATEPROPS(cell); /* isolate the new state */ + actionImp = GET_ACTIONPROPS(cell); /* isolate the action */ + if ((i == aLimit) && (actionImp == 0)) { + /* there is an unprocessed sequence if its property == eor */ + actionImp = 1; /* process the last sequence */ + } + if (actionImp) { + resProp = impTabProps[oldStateImp][IMPTABPROPS_RES]; + switch (actionImp) { + case 1: /* process current seq1, init new seq1 */ + ProcessPropertySeq(&levState, resProp, start1, i); + start1 = i; + break; + case 2: /* init new seq2 */ + start2 = i; + break; + case 3: /* process seq1, process seq2, init new seq1 */ + ProcessPropertySeq(&levState, resProp, start1, start2); + ProcessPropertySeq(&levState, DirProp_ON, start2, i); + start1 = i; + break; + case 4: /* process seq1, set seq1=seq2, init new seq2 */ + ProcessPropertySeq(&levState, resProp, start1, start2); + start1 = start2; + start2 = i; + break; + default: /* we should never get here */ + MOZ_ASSERT(false); + break; + } + } + } + + for (i = aLimit - 1; + i > aStart && (DIRPROP_FLAG(dirProps[i]) & MASK_BN_EXPLICIT); i--) { + // empty loop body + } + dirProp = dirProps[i]; + if ((dirProp == LRI || dirProp == RLI) && aLimit < mLength) { + mIsolateCount++; + mIsolates[mIsolateCount].stateImp = stateImp; + mIsolates[mIsolateCount].state = levState.state; + mIsolates[mIsolateCount].start1 = start1; + } else { + ProcessPropertySeq(&levState, aEOR, aLimit, aLimit); + } +} + + +/* perform (L1) and (X9) ---------------------------------------------------- */ + +/* + * Reset the embedding levels for some non-graphic characters (L1). + * This function also sets appropriate levels for BN, and + * explicit embedding types that are supposed to have been removed + * from the paragraph in (X9). + */ +void nsBidi::AdjustWSLevels() +{ + const DirProp *dirProps=mDirProps; + nsBidiLevel *levels=mLevels; + int32_t i; + + if(mFlags&MASK_WS) { + nsBidiLevel paraLevel=mParaLevel; + Flags flag; + + i=mTrailingWSStart; + while(i>0) { + /* reset a sequence of WS/BN before eop and B/S to the paragraph paraLevel */ + while (i > 0 && DIRPROP_FLAG(dirProps[--i]) & MASK_WS) { + levels[i]=paraLevel; + } + + /* reset BN to the next character's paraLevel until B/S, which restarts above loop */ + /* here, i+1 is guaranteed to be <length */ + while(i>0) { + flag = DIRPROP_FLAG(dirProps[--i]); + if(flag&MASK_BN_EXPLICIT) { + levels[i]=levels[i+1]; + } else if(flag&MASK_B_S) { + levels[i]=paraLevel; + break; + } + } + } + } +} + +nsresult nsBidi::GetDirection(nsBidiDirection* aDirection) +{ + *aDirection = mDirection; + return NS_OK; +} + +nsresult nsBidi::GetParaLevel(nsBidiLevel* aParaLevel) +{ + *aParaLevel = mParaLevel; + return NS_OK; +} + +nsresult nsBidi::GetLogicalRun(int32_t aLogicalStart, int32_t *aLogicalLimit, nsBidiLevel *aLevel) +{ + int32_t length = mLength; + + if(aLogicalStart<0 || length<=aLogicalStart) { + return NS_ERROR_INVALID_ARG; + } + + int32_t runCount, visualStart, logicalLimit, logicalFirst, i; + Run iRun; + + /* CountRuns will check VALID_PARA_OR_LINE */ + nsresult rv = CountRuns(&runCount); + if (NS_FAILED(rv)) { + return rv; + } + + visualStart = logicalLimit = 0; + iRun = mRuns[0]; + + for (i = 0; i < runCount; i++) { + iRun = mRuns[i]; + logicalFirst = GET_INDEX(iRun.logicalStart); + logicalLimit = logicalFirst + iRun.visualLimit - visualStart; + if ((aLogicalStart >= logicalFirst) && (aLogicalStart < logicalLimit)) { + break; + } + visualStart = iRun.visualLimit; + } + if (aLogicalLimit) { + *aLogicalLimit = logicalLimit; + } + if (aLevel) { + if (mDirection != NSBIDI_MIXED || aLogicalStart >= mTrailingWSStart) { + *aLevel = mParaLevel; + } else { + *aLevel = mLevels[aLogicalStart]; + } + } + return NS_OK; +} + +/* runs API functions ------------------------------------------------------- */ + +nsresult nsBidi::CountRuns(int32_t* aRunCount) +{ + if(mRunCount<0 && !GetRuns()) { + return NS_ERROR_OUT_OF_MEMORY; + } else { + if (aRunCount) + *aRunCount = mRunCount; + return NS_OK; + } +} + +nsresult nsBidi::GetVisualRun(int32_t aRunIndex, int32_t *aLogicalStart, int32_t *aLength, nsBidiDirection *aDirection) +{ + if( aRunIndex<0 || + (mRunCount==-1 && !GetRuns()) || + aRunIndex>=mRunCount + ) { + *aDirection = NSBIDI_LTR; + return NS_OK; + } else { + int32_t start=mRuns[aRunIndex].logicalStart; + if(aLogicalStart!=nullptr) { + *aLogicalStart=GET_INDEX(start); + } + if(aLength!=nullptr) { + if(aRunIndex>0) { + *aLength=mRuns[aRunIndex].visualLimit- + mRuns[aRunIndex-1].visualLimit; + } else { + *aLength=mRuns[0].visualLimit; + } + } + *aDirection = (nsBidiDirection)GET_ODD_BIT(start); + return NS_OK; + } +} + +/* compute the runs array --------------------------------------------------- */ + +/* + * Compute the runs array from the levels array. + * After GetRuns() returns true, runCount is guaranteed to be >0 + * and the runs are reordered. + * Odd-level runs have visualStart on their visual right edge and + * they progress visually to the left. + */ +bool nsBidi::GetRuns() +{ + /* + * This method returns immediately if the runs are already set. This + * includes the case of length==0 (handled in setPara).. + */ + if (mRunCount >= 0) { + return true; + } + + if(mDirection!=NSBIDI_MIXED) { + /* simple, single-run case - this covers length==0 */ + GetSingleRun(mParaLevel); + } else /* NSBIDI_MIXED, length>0 */ { + /* mixed directionality */ + int32_t length=mLength, limit=mTrailingWSStart; + + /* + * If there are WS characters at the end of the line + * and the run preceding them has a level different from + * paraLevel, then they will form their own run at paraLevel (L1). + * Count them separately. + * We need some special treatment for this in order to not + * modify the levels array which a line nsBidi object shares + * with its paragraph parent and its other line siblings. + * In other words, for the trailing WS, it may be + * levels[]!=paraLevel but we have to treat it like it were so. + */ + nsBidiLevel *levels=mLevels; + int32_t i, runCount; + nsBidiLevel level=NSBIDI_DEFAULT_LTR; /* initialize with no valid level */ + + /* count the runs, there is at least one non-WS run, and limit>0 */ + runCount=0; + for(i=0; i<limit; ++i) { + /* increment runCount at the start of each run */ + if(levels[i]!=level) { + ++runCount; + level=levels[i]; + } + } + + /* + * We don't need to see if the last run can be merged with a trailing + * WS run because SetTrailingWSStart() would have done that. + */ + if(runCount==1 && limit==length) { + /* There is only one non-WS run and no trailing WS-run. */ + GetSingleRun(levels[0]); + } else /* runCount>1 || limit<length */ { + /* allocate and set the runs */ + Run *runs; + int32_t runIndex, start; + nsBidiLevel minLevel=NSBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0; + + /* now, count a (non-mergable) WS run */ + if(limit<length) { + ++runCount; + } + + /* runCount>1 */ + if(GETRUNSMEMORY(runCount)) { + runs=mRunsMemory; + } else { + return false; + } + + /* set the runs */ + /* this could be optimized, e.g.: 464->444, 484->444, 575->555, 595->555 */ + /* however, that would take longer and make other functions more complicated */ + runIndex=0; + + /* search for the run ends */ + i = 0; + do { + /* prepare this run */ + start = i; + level = levels[i]; + if(level<minLevel) { + minLevel=level; + } + if(level>maxLevel) { + maxLevel=level; + } + + /* look for the run limit */ + while (++i < limit && levels[i] == level) { + } + + /* i is another run limit */ + runs[runIndex].logicalStart = start; + runs[runIndex].visualLimit = i - start; + ++runIndex; + } while (i < limit); + + if(limit<length) { + /* there is a separate WS run */ + runs[runIndex].logicalStart=limit; + runs[runIndex].visualLimit=length-limit; + if(mParaLevel<minLevel) { + minLevel=mParaLevel; + } + } + + /* set the object fields */ + mRuns=runs; + mRunCount=runCount; + + ReorderLine(minLevel, maxLevel); + + /* now add the direction flags and adjust the visualLimit's to be just that */ + /* this loop will also handling the trailing WS run */ + limit = 0; + for (i = 0; i < runCount; ++i) { + ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]); + limit += runs[i].visualLimit; + runs[i].visualLimit = limit; + } + + /* Set the "odd" bit for the trailing WS run. */ + /* For a RTL paragraph, it will be the *first* run in visual order. */ + if (runIndex < runCount) { + int32_t trailingRun = (mParaLevel & 1) ? 0 : runIndex; + ADD_ODD_BIT_FROM_LEVEL(runs[trailingRun].logicalStart, mParaLevel); + } + } + } + + return true; +} + +/* in trivial cases there is only one trivial run; called by GetRuns() */ +void nsBidi::GetSingleRun(nsBidiLevel aLevel) +{ + /* simple, single-run case */ + mRuns=mSimpleRuns; + mRunCount=1; + + /* fill and reorder the single run */ + mRuns[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, aLevel); + mRuns[0].visualLimit=mLength; +} + +/* reorder the runs array (L2) ---------------------------------------------- */ + +/* + * Reorder the same-level runs in the runs array. + * Here, runCount>1 and maxLevel>=minLevel>=paraLevel. + * All the visualStart fields=logical start before reordering. + * The "odd" bits are not set yet. + * + * Reordering with this data structure lends itself to some handy shortcuts: + * + * Since each run is moved but not modified, and since at the initial maxLevel + * each sequence of same-level runs consists of only one run each, we + * don't need to do anything there and can predecrement maxLevel. + * In many simple cases, the reordering is thus done entirely in the + * index mapping. + * Also, reordering occurs only down to the lowest odd level that occurs, + * which is minLevel|1. However, if the lowest level itself is odd, then + * in the last reordering the sequence of the runs at this level or higher + * will be all runs, and we don't need the elaborate loop to search for them. + * This is covered by ++minLevel instead of minLevel|=1 followed + * by an extra reorder-all after the reorder-some loop. + * About a trailing WS run: + * Such a run would need special treatment because its level is not + * reflected in levels[] if this is not a paragraph object. + * Instead, all characters from trailingWSStart on are implicitly at + * paraLevel. + * However, for all maxLevel>paraLevel, this run will never be reordered + * and does not need to be taken into account. maxLevel==paraLevel is only reordered + * if minLevel==paraLevel is odd, which is done in the extra segment. + * This means that for the main reordering loop we don't need to consider + * this run and can --runCount. If it is later part of the all-runs + * reordering, then runCount is adjusted accordingly. + */ +void nsBidi::ReorderLine(nsBidiLevel aMinLevel, nsBidiLevel aMaxLevel) +{ + Run *runs, tempRun; + nsBidiLevel *levels; + int32_t firstRun, endRun, limitRun, runCount; + + /* nothing to do? */ + if(aMaxLevel<=(aMinLevel|1)) { + return; + } + + /* + * Reorder only down to the lowest odd level + * and reorder at an odd aMinLevel in a separate, simpler loop. + * See comments above for why aMinLevel is always incremented. + */ + ++aMinLevel; + + runs=mRuns; + levels=mLevels; + runCount=mRunCount; + + /* do not include the WS run at paraLevel<=old aMinLevel except in the simple loop */ + if(mTrailingWSStart<mLength) { + --runCount; + } + + while(--aMaxLevel>=aMinLevel) { + firstRun=0; + + /* loop for all sequences of runs */ + for(;;) { + /* look for a sequence of runs that are all at >=aMaxLevel */ + /* look for the first run of such a sequence */ + while(firstRun<runCount && levels[runs[firstRun].logicalStart]<aMaxLevel) { + ++firstRun; + } + if(firstRun>=runCount) { + break; /* no more such runs */ + } + + /* look for the limit run of such a sequence (the run behind it) */ + for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=aMaxLevel;) {} + + /* Swap the entire sequence of runs from firstRun to limitRun-1. */ + endRun=limitRun-1; + while(firstRun<endRun) { + tempRun = runs[firstRun]; + runs[firstRun] = runs[endRun]; + runs[endRun] = tempRun; + ++firstRun; + --endRun; + } + + if(limitRun==runCount) { + break; /* no more such runs */ + } else { + firstRun=limitRun+1; + } + } + } + + /* now do aMaxLevel==old aMinLevel (==odd!), see above */ + if(!(aMinLevel&1)) { + firstRun=0; + + /* include the trailing WS run in this complete reordering */ + if(mTrailingWSStart==mLength) { + --runCount; + } + + /* Swap the entire sequence of all runs. (endRun==runCount) */ + while(firstRun<runCount) { + tempRun = runs[firstRun]; + runs[firstRun] = runs[runCount]; + runs[runCount] = tempRun; + ++firstRun; + --runCount; + } + } +} + +nsresult nsBidi::ReorderVisual(const nsBidiLevel *aLevels, int32_t aLength, int32_t *aIndexMap) +{ + int32_t start, end, limit, temp; + nsBidiLevel minLevel, maxLevel; + + if(aIndexMap==nullptr || + !PrepareReorder(aLevels, aLength, aIndexMap, &minLevel, &maxLevel)) { + return NS_OK; + } + + /* nothing to do? */ + if(minLevel==maxLevel && (minLevel&1)==0) { + return NS_OK; + } + + /* reorder only down to the lowest odd level */ + minLevel|=1; + + /* loop maxLevel..minLevel */ + do { + start=0; + + /* loop for all sequences of levels to reorder at the current maxLevel */ + for(;;) { + /* look for a sequence of levels that are all at >=maxLevel */ + /* look for the first index of such a sequence */ + while(start<aLength && aLevels[start]<maxLevel) { + ++start; + } + if(start>=aLength) { + break; /* no more such runs */ + } + + /* look for the limit of such a sequence (the index behind it) */ + for(limit=start; ++limit<aLength && aLevels[limit]>=maxLevel;) {} + + /* + * Swap the entire interval of indexes from start to limit-1. + * We don't need to swap the levels for the purpose of this + * algorithm: the sequence of levels that we look at does not + * move anyway. + */ + end=limit-1; + while(start<end) { + temp=aIndexMap[start]; + aIndexMap[start]=aIndexMap[end]; + aIndexMap[end]=temp; + + ++start; + --end; + } + + if(limit==aLength) { + break; /* no more such sequences */ + } else { + start=limit+1; + } + } + } while(--maxLevel>=minLevel); + + return NS_OK; +} + +bool nsBidi::PrepareReorder(const nsBidiLevel *aLevels, int32_t aLength, + int32_t *aIndexMap, + nsBidiLevel *aMinLevel, nsBidiLevel *aMaxLevel) +{ + int32_t start; + nsBidiLevel level, minLevel, maxLevel; + + if(aLevels==nullptr || aLength<=0) { + return false; + } + + /* determine minLevel and maxLevel */ + minLevel=NSBIDI_MAX_EXPLICIT_LEVEL+1; + maxLevel=0; + for(start=aLength; start>0;) { + level=aLevels[--start]; + if(level>NSBIDI_MAX_EXPLICIT_LEVEL+1) { + return false; + } + if(level<minLevel) { + minLevel=level; + } + if(level>maxLevel) { + maxLevel=level; + } + } + *aMinLevel=minLevel; + *aMaxLevel=maxLevel; + + /* initialize the index map */ + for(start=aLength; start>0;) { + --start; + aIndexMap[start]=start; + } + + return true; +} |