1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/layout/base/nsBidi.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,2219 @@
1.4 +/* -*- Mode: C; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
1.5 + *
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "nsBidi.h"
1.11 +#include "nsUnicodeProperties.h"
1.12 +#include "nsCRTGlue.h"
1.13 +
1.14 +using namespace mozilla::unicode;
1.15 +
1.16 +// These are #defined in <sys/regset.h> under Solaris 10 x86
1.17 +#undef CS
1.18 +#undef ES
1.19 +
1.20 +/* Comparing the description of the Bidi algorithm with this implementation
1.21 + is easier with the same names for the Bidi types in the code as there.
1.22 +*/
1.23 +enum {
1.24 + L = eCharType_LeftToRight,
1.25 + R = eCharType_RightToLeft,
1.26 + EN = eCharType_EuropeanNumber,
1.27 + ES = eCharType_EuropeanNumberSeparator,
1.28 + ET = eCharType_EuropeanNumberTerminator,
1.29 + AN = eCharType_ArabicNumber,
1.30 + CS = eCharType_CommonNumberSeparator,
1.31 + B = eCharType_BlockSeparator,
1.32 + S = eCharType_SegmentSeparator,
1.33 + WS = eCharType_WhiteSpaceNeutral,
1.34 + O_N = eCharType_OtherNeutral,
1.35 + LRE = eCharType_LeftToRightEmbedding,
1.36 + LRO = eCharType_LeftToRightOverride,
1.37 + AL = eCharType_RightToLeftArabic,
1.38 + RLE = eCharType_RightToLeftEmbedding,
1.39 + RLO = eCharType_RightToLeftOverride,
1.40 + PDF = eCharType_PopDirectionalFormat,
1.41 + NSM = eCharType_DirNonSpacingMark,
1.42 + BN = eCharType_BoundaryNeutral,
1.43 + dirPropCount
1.44 +};
1.45 +
1.46 +/* to avoid some conditional statements, use tiny constant arrays */
1.47 +static Flags flagLR[2]={ DIRPROP_FLAG(L), DIRPROP_FLAG(R) };
1.48 +static Flags flagE[2]={ DIRPROP_FLAG(LRE), DIRPROP_FLAG(RLE) };
1.49 +static Flags flagO[2]={ DIRPROP_FLAG(LRO), DIRPROP_FLAG(RLO) };
1.50 +
1.51 +#define DIRPROP_FLAG_LR(level) flagLR[(level)&1]
1.52 +#define DIRPROP_FLAG_E(level) flagE[(level)&1]
1.53 +#define DIRPROP_FLAG_O(level) flagO[(level)&1]
1.54 +
1.55 +/*
1.56 + * General implementation notes:
1.57 + *
1.58 + * Throughout the implementation, there are comments like (W2) that refer to
1.59 + * rules of the Bidi algorithm in its version 5, in this example to the second
1.60 + * rule of the resolution of weak types.
1.61 + *
1.62 + * For handling surrogate pairs, where two UChar's form one "abstract" (or UTF-32)
1.63 + * character according to UTF-16, the second UChar gets the directional property of
1.64 + * the entire character assigned, while the first one gets a BN, a boundary
1.65 + * neutral, type, which is ignored by most of the algorithm according to
1.66 + * rule (X9) and the implementation suggestions of the Bidi algorithm.
1.67 + *
1.68 + * Later, AdjustWSLevels() will set the level for each BN to that of the
1.69 + * following character (UChar), which results in surrogate pairs getting the
1.70 + * same level on each of their surrogates.
1.71 + *
1.72 + * In a UTF-8 implementation, the same thing could be done: the last byte of
1.73 + * a multi-byte sequence would get the "real" property, while all previous
1.74 + * bytes of that sequence would get BN.
1.75 + *
1.76 + * It is not possible to assign all those parts of a character the same real
1.77 + * property because this would fail in the resolution of weak types with rules
1.78 + * that look at immediately surrounding types.
1.79 + *
1.80 + * As a related topic, this implementation does not remove Boundary Neutral
1.81 + * types from the input, but ignores them whenever this is relevant.
1.82 + * For example, the loop for the resolution of the weak types reads
1.83 + * types until it finds a non-BN.
1.84 + * Also, explicit embedding codes are neither changed into BN nor removed.
1.85 + * They are only treated the same way real BNs are.
1.86 + * As stated before, AdjustWSLevels() takes care of them at the end.
1.87 + * For the purpose of conformance, the levels of all these codes
1.88 + * do not matter.
1.89 + *
1.90 + * Note that this implementation never modifies the dirProps
1.91 + * after the initial setup.
1.92 + *
1.93 + *
1.94 + * In this implementation, the resolution of weak types (Wn),
1.95 + * neutrals (Nn), and the assignment of the resolved level (In)
1.96 + * are all done in one single loop, in ResolveImplicitLevels().
1.97 + * Changes of dirProp values are done on the fly, without writing
1.98 + * them back to the dirProps array.
1.99 + *
1.100 + *
1.101 + * This implementation contains code that allows to bypass steps of the
1.102 + * algorithm that are not needed on the specific paragraph
1.103 + * in order to speed up the most common cases considerably,
1.104 + * like text that is entirely LTR, or RTL text without numbers.
1.105 + *
1.106 + * Most of this is done by setting a bit for each directional property
1.107 + * in a flags variable and later checking for whether there are
1.108 + * any LTR characters or any RTL characters, or both, whether
1.109 + * there are any explicit embedding codes, etc.
1.110 + *
1.111 + * If the (Xn) steps are performed, then the flags are re-evaluated,
1.112 + * because they will then not contain the embedding codes any more
1.113 + * and will be adjusted for override codes, so that subsequently
1.114 + * more bypassing may be possible than what the initial flags suggested.
1.115 + *
1.116 + * If the text is not mixed-directional, then the
1.117 + * algorithm steps for the weak type resolution are not performed,
1.118 + * and all levels are set to the paragraph level.
1.119 + *
1.120 + * If there are no explicit embedding codes, then the (Xn) steps
1.121 + * are not performed.
1.122 + *
1.123 + * If embedding levels are supplied as a parameter, then all
1.124 + * explicit embedding codes are ignored, and the (Xn) steps
1.125 + * are not performed.
1.126 + *
1.127 + * White Space types could get the level of the run they belong to,
1.128 + * and are checked with a test of (flags&MASK_EMBEDDING) to
1.129 + * consider if the paragraph direction should be considered in
1.130 + * the flags variable.
1.131 + *
1.132 + * If there are no White Space types in the paragraph, then
1.133 + * (L1) is not necessary in AdjustWSLevels().
1.134 + */
1.135 +nsBidi::nsBidi()
1.136 +{
1.137 + Init();
1.138 +
1.139 + mMayAllocateText=true;
1.140 + mMayAllocateRuns=true;
1.141 +}
1.142 +
1.143 +nsBidi::~nsBidi()
1.144 +{
1.145 + Free();
1.146 +}
1.147 +
1.148 +void nsBidi::Init()
1.149 +{
1.150 + /* reset the object, all pointers nullptr, all flags false, all sizes 0 */
1.151 + mLength = 0;
1.152 + mParaLevel = 0;
1.153 + mFlags = 0;
1.154 + mDirection = NSBIDI_LTR;
1.155 + mTrailingWSStart = 0;
1.156 +
1.157 + mDirPropsSize = 0;
1.158 + mLevelsSize = 0;
1.159 + mRunsSize = 0;
1.160 + mRunCount = -1;
1.161 +
1.162 + mDirProps=nullptr;
1.163 + mLevels=nullptr;
1.164 + mRuns=nullptr;
1.165 +
1.166 + mDirPropsMemory=nullptr;
1.167 + mLevelsMemory=nullptr;
1.168 + mRunsMemory=nullptr;
1.169 +
1.170 + mMayAllocateText=false;
1.171 + mMayAllocateRuns=false;
1.172 +
1.173 +}
1.174 +
1.175 +/*
1.176 + * We are allowed to allocate memory if aMemory==nullptr or
1.177 + * aMayAllocate==true for each array that we need.
1.178 + * We also try to grow and shrink memory as needed if we
1.179 + * allocate it.
1.180 + *
1.181 + * Assume aSizeNeeded>0.
1.182 + * If *aMemory!=nullptr, then assume *aSize>0.
1.183 + *
1.184 + * ### this realloc() may unnecessarily copy the old data,
1.185 + * which we know we don't need any more;
1.186 + * is this the best way to do this??
1.187 + */
1.188 +bool nsBidi::GetMemory(void **aMemory, size_t *aSize, bool aMayAllocate, size_t aSizeNeeded)
1.189 +{
1.190 + /* check for existing memory */
1.191 + if(*aMemory==nullptr) {
1.192 + /* we need to allocate memory */
1.193 + if(!aMayAllocate) {
1.194 + return false;
1.195 + } else {
1.196 + *aMemory=moz_malloc(aSizeNeeded);
1.197 + if (*aMemory!=nullptr) {
1.198 + *aSize=aSizeNeeded;
1.199 + return true;
1.200 + } else {
1.201 + *aSize=0;
1.202 + return false;
1.203 + }
1.204 + }
1.205 + } else {
1.206 + /* there is some memory, is it enough or too much? */
1.207 + if(aSizeNeeded>*aSize && !aMayAllocate) {
1.208 + /* not enough memory, and we must not allocate */
1.209 + return false;
1.210 + } else if(aSizeNeeded!=*aSize && aMayAllocate) {
1.211 + /* we may try to grow or shrink */
1.212 + void *memory=moz_realloc(*aMemory, aSizeNeeded);
1.213 +
1.214 + if(memory!=nullptr) {
1.215 + *aMemory=memory;
1.216 + *aSize=aSizeNeeded;
1.217 + return true;
1.218 + } else {
1.219 + /* we failed to grow */
1.220 + return false;
1.221 + }
1.222 + } else {
1.223 + /* we have at least enough memory and must not allocate */
1.224 + return true;
1.225 + }
1.226 + }
1.227 +}
1.228 +
1.229 +void nsBidi::Free()
1.230 +{
1.231 + moz_free(mDirPropsMemory);
1.232 + mDirPropsMemory = nullptr;
1.233 + moz_free(mLevelsMemory);
1.234 + mLevelsMemory = nullptr;
1.235 + moz_free(mRunsMemory);
1.236 + mRunsMemory = nullptr;
1.237 +}
1.238 +
1.239 +/* SetPara ------------------------------------------------------------ */
1.240 +
1.241 +nsresult nsBidi::SetPara(const char16_t *aText, int32_t aLength,
1.242 + nsBidiLevel aParaLevel, nsBidiLevel *aEmbeddingLevels)
1.243 +{
1.244 + nsBidiDirection direction;
1.245 +
1.246 + /* check the argument values */
1.247 + if(aText==nullptr ||
1.248 + ((NSBIDI_MAX_EXPLICIT_LEVEL<aParaLevel) && !IS_DEFAULT_LEVEL(aParaLevel)) ||
1.249 + aLength<-1
1.250 + ) {
1.251 + return NS_ERROR_INVALID_ARG;
1.252 + }
1.253 +
1.254 + if(aLength==-1) {
1.255 + aLength = NS_strlen(aText);
1.256 + }
1.257 +
1.258 + /* initialize member data */
1.259 + mLength=aLength;
1.260 + mParaLevel=aParaLevel;
1.261 + mDirection=NSBIDI_LTR;
1.262 + mTrailingWSStart=aLength; /* the levels[] will reflect the WS run */
1.263 +
1.264 + mDirProps=nullptr;
1.265 + mLevels=nullptr;
1.266 + mRuns=nullptr;
1.267 +
1.268 + if(aLength==0) {
1.269 + /*
1.270 + * For an empty paragraph, create an nsBidi object with the aParaLevel and
1.271 + * the flags and the direction set but without allocating zero-length arrays.
1.272 + * There is nothing more to do.
1.273 + */
1.274 + if(IS_DEFAULT_LEVEL(aParaLevel)) {
1.275 + mParaLevel&=1;
1.276 + }
1.277 + if(aParaLevel&1) {
1.278 + mFlags=DIRPROP_FLAG(R);
1.279 + mDirection=NSBIDI_RTL;
1.280 + } else {
1.281 + mFlags=DIRPROP_FLAG(L);
1.282 + mDirection=NSBIDI_LTR;
1.283 + }
1.284 +
1.285 + mRunCount=0;
1.286 + return NS_OK;
1.287 + }
1.288 +
1.289 + mRunCount=-1;
1.290 +
1.291 + /*
1.292 + * Get the directional properties,
1.293 + * the flags bit-set, and
1.294 + * determine the partagraph level if necessary.
1.295 + */
1.296 + if(GETDIRPROPSMEMORY(aLength)) {
1.297 + mDirProps=mDirPropsMemory;
1.298 + GetDirProps(aText);
1.299 + } else {
1.300 + return NS_ERROR_OUT_OF_MEMORY;
1.301 + }
1.302 +
1.303 + /* are explicit levels specified? */
1.304 + if(aEmbeddingLevels==nullptr) {
1.305 + /* no: determine explicit levels according to the (Xn) rules */\
1.306 + if(GETLEVELSMEMORY(aLength)) {
1.307 + mLevels=mLevelsMemory;
1.308 + direction=ResolveExplicitLevels();
1.309 + } else {
1.310 + return NS_ERROR_OUT_OF_MEMORY;
1.311 + }
1.312 + } else {
1.313 + /* set BN for all explicit codes, check that all levels are aParaLevel..NSBIDI_MAX_EXPLICIT_LEVEL */
1.314 + mLevels=aEmbeddingLevels;
1.315 + nsresult rv = CheckExplicitLevels(&direction);
1.316 + if(NS_FAILED(rv)) {
1.317 + return rv;
1.318 + }
1.319 + }
1.320 +
1.321 + /*
1.322 + * The steps after (X9) in the Bidi algorithm are performed only if
1.323 + * the paragraph text has mixed directionality!
1.324 + */
1.325 + switch(direction) {
1.326 + case NSBIDI_LTR:
1.327 + /* make sure paraLevel is even */
1.328 + mParaLevel=(mParaLevel+1)&~1;
1.329 +
1.330 + /* all levels are implicitly at paraLevel (important for GetLevels()) */
1.331 + mTrailingWSStart=0;
1.332 + break;
1.333 + case NSBIDI_RTL:
1.334 + /* make sure paraLevel is odd */
1.335 + mParaLevel|=1;
1.336 +
1.337 + /* all levels are implicitly at paraLevel (important for GetLevels()) */
1.338 + mTrailingWSStart=0;
1.339 + break;
1.340 + default:
1.341 + /*
1.342 + * If there are no external levels specified and there
1.343 + * are no significant explicit level codes in the text,
1.344 + * then we can treat the entire paragraph as one run.
1.345 + * Otherwise, we need to perform the following rules on runs of
1.346 + * the text with the same embedding levels. (X10)
1.347 + * "Significant" explicit level codes are ones that actually
1.348 + * affect non-BN characters.
1.349 + * Examples for "insignificant" ones are empty embeddings
1.350 + * LRE-PDF, LRE-RLE-PDF-PDF, etc.
1.351 + */
1.352 + if(aEmbeddingLevels==nullptr && !(mFlags&DIRPROP_FLAG_MULTI_RUNS)) {
1.353 + ResolveImplicitLevels(0, aLength,
1.354 + GET_LR_FROM_LEVEL(mParaLevel),
1.355 + GET_LR_FROM_LEVEL(mParaLevel));
1.356 + } else {
1.357 + /* sor, eor: start and end types of same-level-run */
1.358 + nsBidiLevel *levels=mLevels;
1.359 + int32_t start, limit=0;
1.360 + nsBidiLevel level, nextLevel;
1.361 + DirProp sor, eor;
1.362 +
1.363 + /* determine the first sor and set eor to it because of the loop body (sor=eor there) */
1.364 + level=mParaLevel;
1.365 + nextLevel=levels[0];
1.366 + if(level<nextLevel) {
1.367 + eor=GET_LR_FROM_LEVEL(nextLevel);
1.368 + } else {
1.369 + eor=GET_LR_FROM_LEVEL(level);
1.370 + }
1.371 +
1.372 + do {
1.373 + /* determine start and limit of the run (end points just behind the run) */
1.374 +
1.375 + /* the values for this run's start are the same as for the previous run's end */
1.376 + sor=eor;
1.377 + start=limit;
1.378 + level=nextLevel;
1.379 +
1.380 + /* search for the limit of this run */
1.381 + while(++limit<aLength && levels[limit]==level) {}
1.382 +
1.383 + /* get the correct level of the next run */
1.384 + if(limit<aLength) {
1.385 + nextLevel=levels[limit];
1.386 + } else {
1.387 + nextLevel=mParaLevel;
1.388 + }
1.389 +
1.390 + /* determine eor from max(level, nextLevel); sor is last run's eor */
1.391 + if((level&~NSBIDI_LEVEL_OVERRIDE)<(nextLevel&~NSBIDI_LEVEL_OVERRIDE)) {
1.392 + eor=GET_LR_FROM_LEVEL(nextLevel);
1.393 + } else {
1.394 + eor=GET_LR_FROM_LEVEL(level);
1.395 + }
1.396 +
1.397 + /* if the run consists of overridden directional types, then there
1.398 + are no implicit types to be resolved */
1.399 + if(!(level&NSBIDI_LEVEL_OVERRIDE)) {
1.400 + ResolveImplicitLevels(start, limit, sor, eor);
1.401 + }
1.402 + } while(limit<aLength);
1.403 + }
1.404 +
1.405 + /* reset the embedding levels for some non-graphic characters (L1), (X9) */
1.406 + AdjustWSLevels();
1.407 + break;
1.408 + }
1.409 +
1.410 + mDirection=direction;
1.411 + return NS_OK;
1.412 +}
1.413 +
1.414 +/* perform (P2)..(P3) ------------------------------------------------------- */
1.415 +
1.416 +/*
1.417 + * Get the directional properties for the text,
1.418 + * calculate the flags bit-set, and
1.419 + * determine the partagraph level if necessary.
1.420 + */
1.421 +void nsBidi::GetDirProps(const char16_t *aText)
1.422 +{
1.423 + DirProp *dirProps=mDirPropsMemory; /* mDirProps is const */
1.424 +
1.425 + int32_t i=0, length=mLength;
1.426 + Flags flags=0; /* collect all directionalities in the text */
1.427 + char16_t uchar;
1.428 + DirProp dirProp;
1.429 +
1.430 + if(IS_DEFAULT_LEVEL(mParaLevel)) {
1.431 + /* determine the paragraph level (P2..P3) */
1.432 + for(;;) {
1.433 + uchar=aText[i];
1.434 + if(!IS_FIRST_SURROGATE(uchar) || i+1==length || !IS_SECOND_SURROGATE(aText[i+1])) {
1.435 + /* not a surrogate pair */
1.436 + flags|=DIRPROP_FLAG(dirProps[i]=dirProp=GetBidiCat((uint32_t)uchar));
1.437 + } else {
1.438 + /* a surrogate pair */
1.439 + dirProps[i++]=BN; /* first surrogate in the pair gets the BN type */
1.440 + flags|=DIRPROP_FLAG(dirProps[i]=dirProp=GetBidiCat(GET_UTF_32(uchar, aText[i])))|DIRPROP_FLAG(BN);
1.441 + }
1.442 + ++i;
1.443 + if(dirProp==L) {
1.444 + mParaLevel=0;
1.445 + break;
1.446 + } else if(dirProp==R || dirProp==AL) {
1.447 + mParaLevel=1;
1.448 + break;
1.449 + } else if(i==length) {
1.450 + /*
1.451 + * see comment in nsIBidi.h:
1.452 + * the DEFAULT_XXX values are designed so that
1.453 + * their bit 0 alone yields the intended default
1.454 + */
1.455 + mParaLevel&=1;
1.456 + break;
1.457 + }
1.458 + }
1.459 + }
1.460 +
1.461 + /* get the rest of the directional properties and the flags bits */
1.462 + while(i<length) {
1.463 + uchar=aText[i];
1.464 + if(!IS_FIRST_SURROGATE(uchar) || i+1==length || !IS_SECOND_SURROGATE(aText[i+1])) {
1.465 + /* not a surrogate pair */
1.466 + flags|=DIRPROP_FLAG(dirProps[i]=GetBidiCat((uint32_t)uchar));
1.467 + } else {
1.468 + /* a surrogate pair */
1.469 + dirProps[i++]=BN; /* second surrogate in the pair gets the BN type */
1.470 + flags|=DIRPROP_FLAG(dirProps[i]=GetBidiCat(GET_UTF_32(uchar, aText[i])))|DIRPROP_FLAG(BN);
1.471 + }
1.472 + ++i;
1.473 + }
1.474 + if(flags&MASK_EMBEDDING) {
1.475 + flags|=DIRPROP_FLAG_LR(mParaLevel);
1.476 + }
1.477 + mFlags=flags;
1.478 +}
1.479 +
1.480 +/* perform (X1)..(X9) ------------------------------------------------------- */
1.481 +
1.482 +/*
1.483 + * Resolve the explicit levels as specified by explicit embedding codes.
1.484 + * Recalculate the flags to have them reflect the real properties
1.485 + * after taking the explicit embeddings into account.
1.486 + *
1.487 + * The Bidi algorithm is designed to result in the same behavior whether embedding
1.488 + * levels are externally specified (from "styled text", supposedly the preferred
1.489 + * method) or set by explicit embedding codes (LRx, RLx, PDF) in the plain text.
1.490 + * That is why (X9) instructs to remove all explicit codes (and BN).
1.491 + * However, in a real implementation, this removal of these codes and their index
1.492 + * positions in the plain text is undesirable since it would result in
1.493 + * reallocated, reindexed text.
1.494 + * Instead, this implementation leaves the codes in there and just ignores them
1.495 + * in the subsequent processing.
1.496 + * In order to get the same reordering behavior, positions with a BN or an
1.497 + * explicit embedding code just get the same level assigned as the last "real"
1.498 + * character.
1.499 + *
1.500 + * Some implementations, not this one, then overwrite some of these
1.501 + * directionality properties at "real" same-level-run boundaries by
1.502 + * L or R codes so that the resolution of weak types can be performed on the
1.503 + * entire paragraph at once instead of having to parse it once more and
1.504 + * perform that resolution on same-level-runs.
1.505 + * This limits the scope of the implicit rules in effectively
1.506 + * the same way as the run limits.
1.507 + *
1.508 + * Instead, this implementation does not modify these codes.
1.509 + * On one hand, the paragraph has to be scanned for same-level-runs, but
1.510 + * on the other hand, this saves another loop to reset these codes,
1.511 + * or saves making and modifying a copy of dirProps[].
1.512 + *
1.513 + *
1.514 + * Note that (Pn) and (Xn) changed significantly from version 4 of the Bidi algorithm.
1.515 + *
1.516 + *
1.517 + * Handling the stack of explicit levels (Xn):
1.518 + *
1.519 + * With the Bidi stack of explicit levels,
1.520 + * as pushed with each LRE, RLE, LRO, and RLO and popped with each PDF,
1.521 + * the explicit level must never exceed NSBIDI_MAX_EXPLICIT_LEVEL==61.
1.522 + *
1.523 + * In order to have a correct push-pop semantics even in the case of overflows,
1.524 + * there are two overflow counters:
1.525 + * - countOver60 is incremented with each LRx at level 60
1.526 + * - from level 60, one RLx increases the level to 61
1.527 + * - countOver61 is incremented with each LRx and RLx at level 61
1.528 + *
1.529 + * Popping levels with PDF must work in the opposite order so that level 61
1.530 + * is correct at the correct point. Underflows (too many PDFs) must be checked.
1.531 + *
1.532 + * This implementation assumes that NSBIDI_MAX_EXPLICIT_LEVEL is odd.
1.533 + */
1.534 +
1.535 +nsBidiDirection nsBidi::ResolveExplicitLevels()
1.536 +{
1.537 + const DirProp *dirProps=mDirProps;
1.538 + nsBidiLevel *levels=mLevels;
1.539 +
1.540 + int32_t i=0, length=mLength;
1.541 + Flags flags=mFlags; /* collect all directionalities in the text */
1.542 + DirProp dirProp;
1.543 + nsBidiLevel level=mParaLevel;
1.544 +
1.545 + nsBidiDirection direction;
1.546 +
1.547 + /* determine if the text is mixed-directional or single-directional */
1.548 + direction=DirectionFromFlags(flags);
1.549 +
1.550 + /* we may not need to resolve any explicit levels */
1.551 + if(direction!=NSBIDI_MIXED) {
1.552 + /* not mixed directionality: levels don't matter - trailingWSStart will be 0 */
1.553 + } else if(!(flags&MASK_EXPLICIT)) {
1.554 + /* mixed, but all characters are at the same embedding level */
1.555 + /* set all levels to the paragraph level */
1.556 + for(i=0; i<length; ++i) {
1.557 + levels[i]=level;
1.558 + }
1.559 + } else {
1.560 + /* continue to perform (Xn) */
1.561 +
1.562 + /* (X1) level is set for all codes, embeddingLevel keeps track of the push/pop operations */
1.563 + /* both variables may carry the NSBIDI_LEVEL_OVERRIDE flag to indicate the override status */
1.564 + nsBidiLevel embeddingLevel=level, newLevel, stackTop=0;
1.565 +
1.566 + nsBidiLevel stack[NSBIDI_MAX_EXPLICIT_LEVEL]; /* we never push anything >=NSBIDI_MAX_EXPLICIT_LEVEL */
1.567 + uint32_t countOver60=0, countOver61=0; /* count overflows of explicit levels */
1.568 +
1.569 + /* recalculate the flags */
1.570 + flags=0;
1.571 +
1.572 + /* since we assume that this is a single paragraph, we ignore (X8) */
1.573 + for(i=0; i<length; ++i) {
1.574 + dirProp=dirProps[i];
1.575 + switch(dirProp) {
1.576 + case LRE:
1.577 + case LRO:
1.578 + /* (X3, X5) */
1.579 + newLevel=(embeddingLevel+2)&~(NSBIDI_LEVEL_OVERRIDE|1); /* least greater even level */
1.580 + if(newLevel<=NSBIDI_MAX_EXPLICIT_LEVEL) {
1.581 + stack[stackTop]=embeddingLevel;
1.582 + ++stackTop;
1.583 + embeddingLevel=newLevel;
1.584 + if(dirProp==LRO) {
1.585 + embeddingLevel|=NSBIDI_LEVEL_OVERRIDE;
1.586 + } else {
1.587 + embeddingLevel&=~NSBIDI_LEVEL_OVERRIDE;
1.588 + }
1.589 + } else if((embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)==NSBIDI_MAX_EXPLICIT_LEVEL) {
1.590 + ++countOver61;
1.591 + } else /* (embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)==NSBIDI_MAX_EXPLICIT_LEVEL-1 */ {
1.592 + ++countOver60;
1.593 + }
1.594 + flags|=DIRPROP_FLAG(BN);
1.595 + break;
1.596 + case RLE:
1.597 + case RLO:
1.598 + /* (X2, X4) */
1.599 + newLevel=((embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)+1)|1; /* least greater odd level */
1.600 + if(newLevel<=NSBIDI_MAX_EXPLICIT_LEVEL) {
1.601 + stack[stackTop]=embeddingLevel;
1.602 + ++stackTop;
1.603 + embeddingLevel=newLevel;
1.604 + if(dirProp==RLO) {
1.605 + embeddingLevel|=NSBIDI_LEVEL_OVERRIDE;
1.606 + } else {
1.607 + embeddingLevel&=~NSBIDI_LEVEL_OVERRIDE;
1.608 + }
1.609 + } else {
1.610 + ++countOver61;
1.611 + }
1.612 + flags|=DIRPROP_FLAG(BN);
1.613 + break;
1.614 + case PDF:
1.615 + /* (X7) */
1.616 + /* handle all the overflow cases first */
1.617 + if(countOver61>0) {
1.618 + --countOver61;
1.619 + } else if(countOver60>0 && (embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)!=NSBIDI_MAX_EXPLICIT_LEVEL) {
1.620 + /* handle LRx overflows from level 60 */
1.621 + --countOver60;
1.622 + } else if(stackTop>0) {
1.623 + /* this is the pop operation; it also pops level 61 while countOver60>0 */
1.624 + --stackTop;
1.625 + embeddingLevel=stack[stackTop];
1.626 + /* } else { (underflow) */
1.627 + }
1.628 + flags|=DIRPROP_FLAG(BN);
1.629 + break;
1.630 + case B:
1.631 + /*
1.632 + * We do not really expect to see a paragraph separator (B),
1.633 + * but we should do something reasonable with it,
1.634 + * especially at the end of the text.
1.635 + */
1.636 + stackTop=0;
1.637 + countOver60=countOver61=0;
1.638 + embeddingLevel=level=mParaLevel;
1.639 + flags|=DIRPROP_FLAG(B);
1.640 + break;
1.641 + case BN:
1.642 + /* BN, LRE, RLE, and PDF are supposed to be removed (X9) */
1.643 + /* they will get their levels set correctly in AdjustWSLevels() */
1.644 + flags|=DIRPROP_FLAG(BN);
1.645 + break;
1.646 + default:
1.647 + /* all other types get the "real" level */
1.648 + if(level!=embeddingLevel) {
1.649 + level=embeddingLevel;
1.650 + if(level&NSBIDI_LEVEL_OVERRIDE) {
1.651 + flags|=DIRPROP_FLAG_O(level)|DIRPROP_FLAG_MULTI_RUNS;
1.652 + } else {
1.653 + flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG_MULTI_RUNS;
1.654 + }
1.655 + }
1.656 + if(!(level&NSBIDI_LEVEL_OVERRIDE)) {
1.657 + flags|=DIRPROP_FLAG(dirProp);
1.658 + }
1.659 + break;
1.660 + }
1.661 +
1.662 + /*
1.663 + * We need to set reasonable levels even on BN codes and
1.664 + * explicit codes because we will later look at same-level runs (X10).
1.665 + */
1.666 + levels[i]=level;
1.667 + }
1.668 + if(flags&MASK_EMBEDDING) {
1.669 + flags|=DIRPROP_FLAG_LR(mParaLevel);
1.670 + }
1.671 +
1.672 + /* subsequently, ignore the explicit codes and BN (X9) */
1.673 +
1.674 + /* again, determine if the text is mixed-directional or single-directional */
1.675 + mFlags=flags;
1.676 + direction=DirectionFromFlags(flags);
1.677 + }
1.678 + return direction;
1.679 +}
1.680 +
1.681 +/*
1.682 + * Use a pre-specified embedding levels array:
1.683 + *
1.684 + * Adjust the directional properties for overrides (->LEVEL_OVERRIDE),
1.685 + * ignore all explicit codes (X9),
1.686 + * and check all the preset levels.
1.687 + *
1.688 + * Recalculate the flags to have them reflect the real properties
1.689 + * after taking the explicit embeddings into account.
1.690 + */
1.691 +nsresult nsBidi::CheckExplicitLevels(nsBidiDirection *aDirection)
1.692 +{
1.693 + const DirProp *dirProps=mDirProps;
1.694 + nsBidiLevel *levels=mLevels;
1.695 +
1.696 + int32_t i, length=mLength;
1.697 + Flags flags=0; /* collect all directionalities in the text */
1.698 + nsBidiLevel level, paraLevel=mParaLevel;
1.699 +
1.700 + for(i=0; i<length; ++i) {
1.701 + level=levels[i];
1.702 + if(level&NSBIDI_LEVEL_OVERRIDE) {
1.703 + /* keep the override flag in levels[i] but adjust the flags */
1.704 + level&=~NSBIDI_LEVEL_OVERRIDE; /* make the range check below simpler */
1.705 + flags|=DIRPROP_FLAG_O(level);
1.706 + } else {
1.707 + /* set the flags */
1.708 + flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG(dirProps[i]);
1.709 + }
1.710 + if(level<paraLevel || NSBIDI_MAX_EXPLICIT_LEVEL<level) {
1.711 + /* level out of bounds */
1.712 + *aDirection = NSBIDI_LTR;
1.713 + return NS_ERROR_INVALID_ARG;
1.714 + }
1.715 + }
1.716 + if(flags&MASK_EMBEDDING) {
1.717 + flags|=DIRPROP_FLAG_LR(mParaLevel);
1.718 + }
1.719 +
1.720 + /* determine if the text is mixed-directional or single-directional */
1.721 + mFlags=flags;
1.722 + *aDirection = DirectionFromFlags(flags);
1.723 + return NS_OK;
1.724 +}
1.725 +
1.726 +/* determine if the text is mixed-directional or single-directional */
1.727 +nsBidiDirection nsBidi::DirectionFromFlags(Flags aFlags)
1.728 +{
1.729 + /* if the text contains AN and neutrals, then some neutrals may become RTL */
1.730 + if(!(aFlags&MASK_RTL || (aFlags&DIRPROP_FLAG(AN) && aFlags&MASK_POSSIBLE_N))) {
1.731 + return NSBIDI_LTR;
1.732 + } else if(!(aFlags&MASK_LTR)) {
1.733 + return NSBIDI_RTL;
1.734 + } else {
1.735 + return NSBIDI_MIXED;
1.736 + }
1.737 +}
1.738 +
1.739 +/* perform rules (Wn), (Nn), and (In) on a run of the text ------------------ */
1.740 +
1.741 +/*
1.742 + * This implementation of the (Wn) rules applies all rules in one pass.
1.743 + * In order to do so, it needs a look-ahead of typically 1 character
1.744 + * (except for W5: sequences of ET) and keeps track of changes
1.745 + * in a rule Wp that affect a later Wq (p<q).
1.746 + *
1.747 + * historyOfEN is a variable-saver: it contains 4 boolean states;
1.748 + * a bit in it set to 1 means:
1.749 + * bit 0: the current code is an EN after W2
1.750 + * bit 1: the current code is an EN after W4
1.751 + * bit 2: the previous code was an EN after W2
1.752 + * bit 3: the previous code was an EN after W4
1.753 + * In other words, b0..1 have transitions of EN in the current iteration,
1.754 + * while b2..3 have the transitions of EN in the previous iteration.
1.755 + * A simple historyOfEN<<=2 suffices for the propagation.
1.756 + *
1.757 + * The (Nn) and (In) rules are also performed in that same single loop,
1.758 + * but effectively one iteration behind for white space.
1.759 + *
1.760 + * Since all implicit rules are performed in one step, it is not necessary
1.761 + * to actually store the intermediate directional properties in dirProps[].
1.762 + */
1.763 +
1.764 +#define EN_SHIFT 2
1.765 +#define EN_AFTER_W2 1
1.766 +#define EN_AFTER_W4 2
1.767 +#define EN_ALL 3
1.768 +#define PREV_EN_AFTER_W2 4
1.769 +#define PREV_EN_AFTER_W4 8
1.770 +
1.771 +void nsBidi::ResolveImplicitLevels(int32_t aStart, int32_t aLimit,
1.772 + DirProp aSOR, DirProp aEOR)
1.773 +{
1.774 + const DirProp *dirProps=mDirProps;
1.775 + nsBidiLevel *levels=mLevels;
1.776 +
1.777 + int32_t i, next, neutralStart=-1;
1.778 + DirProp prevDirProp, dirProp, nextDirProp, lastStrong, beforeNeutral;
1.779 + uint8_t historyOfEN;
1.780 +
1.781 + /* initialize: current at aSOR, next at aStart (it is aStart<aLimit) */
1.782 + next=aStart;
1.783 + beforeNeutral=dirProp=lastStrong=aSOR;
1.784 + nextDirProp=dirProps[next];
1.785 + historyOfEN=0;
1.786 +
1.787 + /*
1.788 + * In all steps of this implementation, BN and explicit embedding codes
1.789 + * must be treated as if they didn't exist (X9).
1.790 + * They will get levels set before a non-neutral character, and remain
1.791 + * undefined before a neutral one, but AdjustWSLevels() will take care
1.792 + * of all of them.
1.793 + */
1.794 + while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT) {
1.795 + if(++next<aLimit) {
1.796 + nextDirProp=dirProps[next];
1.797 + } else {
1.798 + nextDirProp=aEOR;
1.799 + break;
1.800 + }
1.801 + }
1.802 +
1.803 + /* loop for entire run */
1.804 + while(next<aLimit) {
1.805 + /* advance */
1.806 + prevDirProp=dirProp;
1.807 + dirProp=nextDirProp;
1.808 + i=next;
1.809 + do {
1.810 + if(++next<aLimit) {
1.811 + nextDirProp=dirProps[next];
1.812 + } else {
1.813 + nextDirProp=aEOR;
1.814 + break;
1.815 + }
1.816 + } while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT);
1.817 + historyOfEN<<=EN_SHIFT;
1.818 +
1.819 + /* (W1..W7) */
1.820 + switch(dirProp) {
1.821 + case L:
1.822 + lastStrong=L;
1.823 + break;
1.824 + case R:
1.825 + lastStrong=R;
1.826 + break;
1.827 + case AL:
1.828 + /* (W3) */
1.829 + lastStrong=AL;
1.830 + dirProp=R;
1.831 + break;
1.832 + case EN:
1.833 + /* we have to set historyOfEN correctly */
1.834 + if(lastStrong==AL) {
1.835 + /* (W2) */
1.836 + dirProp=AN;
1.837 + } else {
1.838 + if(lastStrong==L) {
1.839 + /* (W7) */
1.840 + dirProp=L;
1.841 + }
1.842 + /* this EN stays after (W2) and (W4) - at least before (W7) */
1.843 + historyOfEN|=EN_ALL;
1.844 + }
1.845 + break;
1.846 + case ES:
1.847 + if( historyOfEN&PREV_EN_AFTER_W2 && /* previous was EN before (W4) */
1.848 + nextDirProp==EN && lastStrong!=AL /* next is EN and (W2) won't make it AN */
1.849 + ) {
1.850 + /* (W4) */
1.851 + if(lastStrong!=L) {
1.852 + dirProp=EN;
1.853 + } else {
1.854 + /* (W7) */
1.855 + dirProp=L;
1.856 + }
1.857 + historyOfEN|=EN_AFTER_W4;
1.858 + } else {
1.859 + /* (W6) */
1.860 + dirProp=O_N;
1.861 + }
1.862 + break;
1.863 + case CS:
1.864 + if( historyOfEN&PREV_EN_AFTER_W2 && /* previous was EN before (W4) */
1.865 + nextDirProp==EN && lastStrong!=AL /* next is EN and (W2) won't make it AN */
1.866 + ) {
1.867 + /* (W4) */
1.868 + if(lastStrong!=L) {
1.869 + dirProp=EN;
1.870 + } else {
1.871 + /* (W7) */
1.872 + dirProp=L;
1.873 + }
1.874 + historyOfEN|=EN_AFTER_W4;
1.875 + } else if(prevDirProp==AN && /* previous was AN */
1.876 + (nextDirProp==AN || /* next is AN */
1.877 + (nextDirProp==EN && lastStrong==AL)) /* or (W2) will make it one */
1.878 + ) {
1.879 + /* (W4) */
1.880 + dirProp=AN;
1.881 + } else {
1.882 + /* (W6) */
1.883 + dirProp=O_N;
1.884 + }
1.885 + break;
1.886 + case ET:
1.887 + /* get sequence of ET; advance only next, not current, previous or historyOfEN */
1.888 + while(next<aLimit && DIRPROP_FLAG(nextDirProp)&MASK_ET_NSM_BN /* (W1), (X9) */) {
1.889 + if(++next<aLimit) {
1.890 + nextDirProp=dirProps[next];
1.891 + } else {
1.892 + nextDirProp=aEOR;
1.893 + break;
1.894 + }
1.895 + }
1.896 +
1.897 + if( historyOfEN&PREV_EN_AFTER_W4 || /* previous was EN before (W5) */
1.898 + (nextDirProp==EN && lastStrong!=AL) /* next is EN and (W2) won't make it AN */
1.899 + ) {
1.900 + /* (W5) */
1.901 + if(lastStrong!=L) {
1.902 + dirProp=EN;
1.903 + } else {
1.904 + /* (W7) */
1.905 + dirProp=L;
1.906 + }
1.907 + } else {
1.908 + /* (W6) */
1.909 + dirProp=O_N;
1.910 + }
1.911 +
1.912 + /* apply the result of (W1), (W5)..(W7) to the entire sequence of ET */
1.913 + break;
1.914 + case NSM:
1.915 + /* (W1) */
1.916 + dirProp=prevDirProp;
1.917 + /* set historyOfEN back to prevDirProp's historyOfEN */
1.918 + historyOfEN>>=EN_SHIFT;
1.919 + /*
1.920 + * Technically, this should be done before the switch() in the form
1.921 + * if(nextDirProp==NSM) {
1.922 + * dirProps[next]=nextDirProp=dirProp;
1.923 + * }
1.924 + *
1.925 + * - effectively one iteration ahead.
1.926 + * However, whether the next dirProp is NSM or is equal to the current dirProp
1.927 + * does not change the outcome of any condition in (W2)..(W7).
1.928 + */
1.929 + break;
1.930 + default:
1.931 + break;
1.932 + }
1.933 +
1.934 + /* here, it is always [prev,this,next]dirProp!=BN; it may be next>i+1 */
1.935 +
1.936 + /* perform (Nn) - here, only L, R, EN, AN, and neutrals are left */
1.937 + /* this is one iteration late for the neutrals */
1.938 + if(DIRPROP_FLAG(dirProp)&MASK_N) {
1.939 + if(neutralStart<0) {
1.940 + /* start of a sequence of neutrals */
1.941 + neutralStart=i;
1.942 + beforeNeutral=prevDirProp;
1.943 + }
1.944 + } else /* not a neutral, can be only one of { L, R, EN, AN } */ {
1.945 + /*
1.946 + * Note that all levels[] values are still the same at this
1.947 + * point because this function is called for an entire
1.948 + * same-level run.
1.949 + * Therefore, we need to read only one actual level.
1.950 + */
1.951 + nsBidiLevel level=levels[i];
1.952 +
1.953 + if(neutralStart>=0) {
1.954 + nsBidiLevel final;
1.955 + /* end of a sequence of neutrals (dirProp is "afterNeutral") */
1.956 + if(beforeNeutral==L) {
1.957 + if(dirProp==L) {
1.958 + final=0; /* make all neutrals L (N1) */
1.959 + } else {
1.960 + final=level; /* make all neutrals "e" (N2) */
1.961 + }
1.962 + } else /* beforeNeutral is one of { R, EN, AN } */ {
1.963 + if(dirProp==L) {
1.964 + final=level; /* make all neutrals "e" (N2) */
1.965 + } else {
1.966 + final=1; /* make all neutrals R (N1) */
1.967 + }
1.968 + }
1.969 + /* perform (In) on the sequence of neutrals */
1.970 + if((level^final)&1) {
1.971 + /* do something only if we need to _change_ the level */
1.972 + do {
1.973 + ++levels[neutralStart];
1.974 + } while(++neutralStart<i);
1.975 + }
1.976 + neutralStart=-1;
1.977 + }
1.978 +
1.979 + /* perform (In) on the non-neutral character */
1.980 + /*
1.981 + * in the cases of (W5), processing a sequence of ET,
1.982 + * and of (X9), skipping BN,
1.983 + * there may be multiple characters from i to <next
1.984 + * that all get (virtually) the same dirProp and (really) the same level
1.985 + */
1.986 + if(dirProp==L) {
1.987 + if(level&1) {
1.988 + ++level;
1.989 + } else {
1.990 + i=next; /* we keep the levels */
1.991 + }
1.992 + } else if(dirProp==R) {
1.993 + if(!(level&1)) {
1.994 + ++level;
1.995 + } else {
1.996 + i=next; /* we keep the levels */
1.997 + }
1.998 + } else /* EN or AN */ {
1.999 + level=(level+2)&~1; /* least greater even level */
1.1000 + }
1.1001 +
1.1002 + /* apply the new level to the sequence, if necessary */
1.1003 + while(i<next) {
1.1004 + levels[i++]=level;
1.1005 + }
1.1006 + }
1.1007 + }
1.1008 +
1.1009 + /* perform (Nn) - here,
1.1010 + the character after the neutrals is aEOR, which is either L or R */
1.1011 + /* this is one iteration late for the neutrals */
1.1012 + if(neutralStart>=0) {
1.1013 + /*
1.1014 + * Note that all levels[] values are still the same at this
1.1015 + * point because this function is called for an entire
1.1016 + * same-level run.
1.1017 + * Therefore, we need to read only one actual level.
1.1018 + */
1.1019 + nsBidiLevel level=levels[neutralStart], final;
1.1020 +
1.1021 + /* end of a sequence of neutrals (aEOR is "afterNeutral") */
1.1022 + if(beforeNeutral==L) {
1.1023 + if(aEOR==L) {
1.1024 + final=0; /* make all neutrals L (N1) */
1.1025 + } else {
1.1026 + final=level; /* make all neutrals "e" (N2) */
1.1027 + }
1.1028 + } else /* beforeNeutral is one of { R, EN, AN } */ {
1.1029 + if(aEOR==L) {
1.1030 + final=level; /* make all neutrals "e" (N2) */
1.1031 + } else {
1.1032 + final=1; /* make all neutrals R (N1) */
1.1033 + }
1.1034 + }
1.1035 + /* perform (In) on the sequence of neutrals */
1.1036 + if((level^final)&1) {
1.1037 + /* do something only if we need to _change_ the level */
1.1038 + do {
1.1039 + ++levels[neutralStart];
1.1040 + } while(++neutralStart<aLimit);
1.1041 + }
1.1042 + }
1.1043 +}
1.1044 +
1.1045 +/* perform (L1) and (X9) ---------------------------------------------------- */
1.1046 +
1.1047 +/*
1.1048 + * Reset the embedding levels for some non-graphic characters (L1).
1.1049 + * This function also sets appropriate levels for BN, and
1.1050 + * explicit embedding types that are supposed to have been removed
1.1051 + * from the paragraph in (X9).
1.1052 + */
1.1053 +void nsBidi::AdjustWSLevels()
1.1054 +{
1.1055 + const DirProp *dirProps=mDirProps;
1.1056 + nsBidiLevel *levels=mLevels;
1.1057 + int32_t i;
1.1058 +
1.1059 + if(mFlags&MASK_WS) {
1.1060 + nsBidiLevel paraLevel=mParaLevel;
1.1061 + Flags flag;
1.1062 +
1.1063 + i=mTrailingWSStart;
1.1064 + while(i>0) {
1.1065 + /* reset a sequence of WS/BN before eop and B/S to the paragraph paraLevel */
1.1066 + while(i>0 && DIRPROP_FLAG(dirProps[--i])&MASK_WS) {
1.1067 + levels[i]=paraLevel;
1.1068 + }
1.1069 +
1.1070 + /* reset BN to the next character's paraLevel until B/S, which restarts above loop */
1.1071 + /* here, i+1 is guaranteed to be <length */
1.1072 + while(i>0) {
1.1073 + flag=DIRPROP_FLAG(dirProps[--i]);
1.1074 + if(flag&MASK_BN_EXPLICIT) {
1.1075 + levels[i]=levels[i+1];
1.1076 + } else if(flag&MASK_B_S) {
1.1077 + levels[i]=paraLevel;
1.1078 + break;
1.1079 + }
1.1080 + }
1.1081 + }
1.1082 + }
1.1083 +
1.1084 + /* now remove the NSBIDI_LEVEL_OVERRIDE flags, if any */
1.1085 + /* (a separate loop can be optimized more easily by a compiler) */
1.1086 + if(mFlags&MASK_OVERRIDE) {
1.1087 + for(i=mTrailingWSStart; i>0;) {
1.1088 + levels[--i]&=~NSBIDI_LEVEL_OVERRIDE;
1.1089 + }
1.1090 + }
1.1091 +}
1.1092 +
1.1093 +nsresult nsBidi::GetDirection(nsBidiDirection* aDirection)
1.1094 +{
1.1095 + *aDirection = mDirection;
1.1096 + return NS_OK;
1.1097 +}
1.1098 +
1.1099 +nsresult nsBidi::GetParaLevel(nsBidiLevel* aParaLevel)
1.1100 +{
1.1101 + *aParaLevel = mParaLevel;
1.1102 + return NS_OK;
1.1103 +}
1.1104 +#ifdef FULL_BIDI_ENGINE
1.1105 +
1.1106 +/* -------------------------------------------------------------------------- */
1.1107 +
1.1108 +nsresult nsBidi::GetLength(int32_t* aLength)
1.1109 +{
1.1110 + *aLength = mLength;
1.1111 + return NS_OK;
1.1112 +}
1.1113 +
1.1114 +/*
1.1115 + * General remarks about the functions in this section:
1.1116 + *
1.1117 + * These functions deal with the aspects of potentially mixed-directional
1.1118 + * text in a single paragraph or in a line of a single paragraph
1.1119 + * which has already been processed according to
1.1120 + * the Unicode 3.0 Bidi algorithm as defined in
1.1121 + * http://www.unicode.org/unicode/reports/tr9/ , version 5,
1.1122 + * also described in The Unicode Standard, Version 3.0 .
1.1123 + *
1.1124 + * This means that there is a nsBidi object with a levels
1.1125 + * and a dirProps array.
1.1126 + * paraLevel and direction are also set.
1.1127 + * Only if the length of the text is zero, then levels==dirProps==nullptr.
1.1128 + *
1.1129 + * The overall directionality of the paragraph
1.1130 + * or line is used to bypass the reordering steps if possible.
1.1131 + * Even purely RTL text does not need reordering there because
1.1132 + * the getLogical/VisualIndex() functions can compute the
1.1133 + * index on the fly in such a case.
1.1134 + *
1.1135 + * The implementation of the access to same-level-runs and of the reordering
1.1136 + * do attempt to provide better performance and less memory usage compared to
1.1137 + * a direct implementation of especially rule (L2) with an array of
1.1138 + * one (32-bit) integer per text character.
1.1139 + *
1.1140 + * Here, the levels array is scanned as soon as necessary, and a vector of
1.1141 + * same-level-runs is created. Reordering then is done on this vector.
1.1142 + * For each run of text positions that were resolved to the same level,
1.1143 + * only 8 bytes are stored: the first text position of the run and the visual
1.1144 + * position behind the run after reordering.
1.1145 + * One sign bit is used to hold the directionality of the run.
1.1146 + * This is inefficient if there are many very short runs. If the average run
1.1147 + * length is <2, then this uses more memory.
1.1148 + *
1.1149 + * In a further attempt to save memory, the levels array is never changed
1.1150 + * after all the resolution rules (Xn, Wn, Nn, In).
1.1151 + * Many functions have to consider the field trailingWSStart:
1.1152 + * if it is less than length, then there is an implicit trailing run
1.1153 + * at the paraLevel,
1.1154 + * which is not reflected in the levels array.
1.1155 + * This allows a line nsBidi object to use the same levels array as
1.1156 + * its paragraph parent object.
1.1157 + *
1.1158 + * When a nsBidi object is created for a line of a paragraph, then the
1.1159 + * paragraph's levels and dirProps arrays are reused by way of setting
1.1160 + * a pointer into them, not by copying. This again saves memory and forbids to
1.1161 + * change the now shared levels for (L1).
1.1162 + */
1.1163 +nsresult nsBidi::SetLine(nsIBidi* aParaBidi, int32_t aStart, int32_t aLimit)
1.1164 +{
1.1165 + nsBidi* pParent = (nsBidi*)aParaBidi;
1.1166 + int32_t length;
1.1167 +
1.1168 + /* check the argument values */
1.1169 + if(pParent==nullptr) {
1.1170 + return NS_ERROR_INVALID_POINTER;
1.1171 + } else if(aStart<0 || aStart>aLimit || aLimit>pParent->mLength) {
1.1172 + return NS_ERROR_INVALID_ARG;
1.1173 + }
1.1174 +
1.1175 + /* set members from our aParaBidi parent */
1.1176 + length=mLength=aLimit-aStart;
1.1177 + mParaLevel=pParent->mParaLevel;
1.1178 +
1.1179 + mRuns=nullptr;
1.1180 + mFlags=0;
1.1181 +
1.1182 + if(length>0) {
1.1183 + mDirProps=pParent->mDirProps+aStart;
1.1184 + mLevels=pParent->mLevels+aStart;
1.1185 + mRunCount=-1;
1.1186 +
1.1187 + if(pParent->mDirection!=NSBIDI_MIXED) {
1.1188 + /* the parent is already trivial */
1.1189 + mDirection=pParent->mDirection;
1.1190 +
1.1191 + /*
1.1192 + * The parent's levels are all either
1.1193 + * implicitly or explicitly ==paraLevel;
1.1194 + * do the same here.
1.1195 + */
1.1196 + if(pParent->mTrailingWSStart<=aStart) {
1.1197 + mTrailingWSStart=0;
1.1198 + } else if(pParent->mTrailingWSStart<aLimit) {
1.1199 + mTrailingWSStart=pParent->mTrailingWSStart-aStart;
1.1200 + } else {
1.1201 + mTrailingWSStart=length;
1.1202 + }
1.1203 + } else {
1.1204 + const nsBidiLevel *levels=mLevels;
1.1205 + int32_t i, trailingWSStart;
1.1206 + nsBidiLevel level;
1.1207 + Flags flags=0;
1.1208 +
1.1209 + SetTrailingWSStart();
1.1210 + trailingWSStart=mTrailingWSStart;
1.1211 +
1.1212 + /* recalculate pLineBidi->direction */
1.1213 + if(trailingWSStart==0) {
1.1214 + /* all levels are at paraLevel */
1.1215 + mDirection=(nsBidiDirection)(mParaLevel&1);
1.1216 + } else {
1.1217 + /* get the level of the first character */
1.1218 + level=levels[0]&1;
1.1219 +
1.1220 + /* if there is anything of a different level, then the line is mixed */
1.1221 + if(trailingWSStart<length && (mParaLevel&1)!=level) {
1.1222 + /* the trailing WS is at paraLevel, which differs from levels[0] */
1.1223 + mDirection=NSBIDI_MIXED;
1.1224 + } else {
1.1225 + /* see if levels[1..trailingWSStart-1] have the same direction as levels[0] and paraLevel */
1.1226 + i=1;
1.1227 + for(;;) {
1.1228 + if(i==trailingWSStart) {
1.1229 + /* the direction values match those in level */
1.1230 + mDirection=(nsBidiDirection)level;
1.1231 + break;
1.1232 + } else if((levels[i]&1)!=level) {
1.1233 + mDirection=NSBIDI_MIXED;
1.1234 + break;
1.1235 + }
1.1236 + ++i;
1.1237 + }
1.1238 + }
1.1239 + }
1.1240 +
1.1241 + switch(mDirection) {
1.1242 + case NSBIDI_LTR:
1.1243 + /* make sure paraLevel is even */
1.1244 + mParaLevel=(mParaLevel+1)&~1;
1.1245 +
1.1246 + /* all levels are implicitly at paraLevel (important for GetLevels()) */
1.1247 + mTrailingWSStart=0;
1.1248 + break;
1.1249 + case NSBIDI_RTL:
1.1250 + /* make sure paraLevel is odd */
1.1251 + mParaLevel|=1;
1.1252 +
1.1253 + /* all levels are implicitly at paraLevel (important for GetLevels()) */
1.1254 + mTrailingWSStart=0;
1.1255 + break;
1.1256 + default:
1.1257 + break;
1.1258 + }
1.1259 + }
1.1260 + } else {
1.1261 + /* create an object for a zero-length line */
1.1262 + mDirection=mParaLevel&1 ? NSBIDI_RTL : NSBIDI_LTR;
1.1263 + mTrailingWSStart=mRunCount=0;
1.1264 +
1.1265 + mDirProps=nullptr;
1.1266 + mLevels=nullptr;
1.1267 + }
1.1268 + return NS_OK;
1.1269 +}
1.1270 +
1.1271 +/* handle trailing WS (L1) -------------------------------------------------- */
1.1272 +
1.1273 +/*
1.1274 + * SetTrailingWSStart() sets the start index for a trailing
1.1275 + * run of WS in the line. This is necessary because we do not modify
1.1276 + * the paragraph's levels array that we just point into.
1.1277 + * Using trailingWSStart is another form of performing (L1).
1.1278 + *
1.1279 + * To make subsequent operations easier, we also include the run
1.1280 + * before the WS if it is at the paraLevel - we merge the two here.
1.1281 + */
1.1282 +void nsBidi::SetTrailingWSStart() {
1.1283 + /* mDirection!=NSBIDI_MIXED */
1.1284 +
1.1285 + const DirProp *dirProps=mDirProps;
1.1286 + nsBidiLevel *levels=mLevels;
1.1287 + int32_t start=mLength;
1.1288 + nsBidiLevel paraLevel=mParaLevel;
1.1289 +
1.1290 + /* go backwards across all WS, BN, explicit codes */
1.1291 + while(start>0 && DIRPROP_FLAG(dirProps[start-1])&MASK_WS) {
1.1292 + --start;
1.1293 + }
1.1294 +
1.1295 + /* if the WS run can be merged with the previous run then do so here */
1.1296 + while(start>0 && levels[start-1]==paraLevel) {
1.1297 + --start;
1.1298 + }
1.1299 +
1.1300 + mTrailingWSStart=start;
1.1301 +}
1.1302 +
1.1303 +nsresult nsBidi::GetLevelAt(int32_t aCharIndex, nsBidiLevel* aLevel)
1.1304 +{
1.1305 + /* return paraLevel if in the trailing WS run, otherwise the real level */
1.1306 + if(aCharIndex<0 || mLength<=aCharIndex) {
1.1307 + *aLevel = 0;
1.1308 + } else if(mDirection!=NSBIDI_MIXED || aCharIndex>=mTrailingWSStart) {
1.1309 + *aLevel = mParaLevel;
1.1310 + } else {
1.1311 + *aLevel = mLevels[aCharIndex];
1.1312 + }
1.1313 + return NS_OK;
1.1314 +}
1.1315 +
1.1316 +nsresult nsBidi::GetLevels(nsBidiLevel** aLevels)
1.1317 +{
1.1318 + int32_t start, length;
1.1319 +
1.1320 + length = mLength;
1.1321 + if(length<=0) {
1.1322 + *aLevels = nullptr;
1.1323 + return NS_ERROR_INVALID_ARG;
1.1324 + }
1.1325 +
1.1326 + start = mTrailingWSStart;
1.1327 + if(start==length) {
1.1328 + /* the current levels array reflects the WS run */
1.1329 + *aLevels = mLevels;
1.1330 + return NS_OK;
1.1331 + }
1.1332 +
1.1333 + /*
1.1334 + * After the previous if(), we know that the levels array
1.1335 + * has an implicit trailing WS run and therefore does not fully
1.1336 + * reflect itself all the levels.
1.1337 + * This must be a nsBidi object for a line, and
1.1338 + * we need to create a new levels array.
1.1339 + */
1.1340 +
1.1341 + if(GETLEVELSMEMORY(length)) {
1.1342 + nsBidiLevel *levels=mLevelsMemory;
1.1343 +
1.1344 + if(start>0 && levels!=mLevels) {
1.1345 + memcpy(levels, mLevels, start);
1.1346 + }
1.1347 + memset(levels+start, mParaLevel, length-start);
1.1348 +
1.1349 + /* this new levels array is set for the line and reflects the WS run */
1.1350 + mTrailingWSStart=length;
1.1351 + *aLevels=mLevels=levels;
1.1352 + return NS_OK;
1.1353 + } else {
1.1354 + /* out of memory */
1.1355 + *aLevels = nullptr;
1.1356 + return NS_ERROR_OUT_OF_MEMORY;
1.1357 + }
1.1358 +}
1.1359 +#endif // FULL_BIDI_ENGINE
1.1360 +
1.1361 +nsresult nsBidi::GetCharTypeAt(int32_t aCharIndex, nsCharType* pType)
1.1362 +{
1.1363 + if(aCharIndex<0 || mLength<=aCharIndex) {
1.1364 + return NS_ERROR_INVALID_ARG;
1.1365 + }
1.1366 + *pType = (nsCharType)mDirProps[aCharIndex];
1.1367 + return NS_OK;
1.1368 +}
1.1369 +
1.1370 +nsresult nsBidi::GetLogicalRun(int32_t aLogicalStart, int32_t *aLogicalLimit, nsBidiLevel *aLevel)
1.1371 +{
1.1372 + int32_t length = mLength;
1.1373 +
1.1374 + if(aLogicalStart<0 || length<=aLogicalStart) {
1.1375 + return NS_ERROR_INVALID_ARG;
1.1376 + }
1.1377 +
1.1378 + if(mDirection!=NSBIDI_MIXED || aLogicalStart>=mTrailingWSStart) {
1.1379 + if(aLogicalLimit!=nullptr) {
1.1380 + *aLogicalLimit=length;
1.1381 + }
1.1382 + if(aLevel!=nullptr) {
1.1383 + *aLevel=mParaLevel;
1.1384 + }
1.1385 + } else {
1.1386 + nsBidiLevel *levels=mLevels;
1.1387 + nsBidiLevel level=levels[aLogicalStart];
1.1388 +
1.1389 + /* search for the end of the run */
1.1390 + length=mTrailingWSStart;
1.1391 + while(++aLogicalStart<length && level==levels[aLogicalStart]) {}
1.1392 +
1.1393 + if(aLogicalLimit!=nullptr) {
1.1394 + *aLogicalLimit=aLogicalStart;
1.1395 + }
1.1396 + if(aLevel!=nullptr) {
1.1397 + *aLevel=level;
1.1398 + }
1.1399 + }
1.1400 + return NS_OK;
1.1401 +}
1.1402 +
1.1403 +/* runs API functions ------------------------------------------------------- */
1.1404 +
1.1405 +nsresult nsBidi::CountRuns(int32_t* aRunCount)
1.1406 +{
1.1407 + if(mRunCount<0 && !GetRuns()) {
1.1408 + return NS_ERROR_OUT_OF_MEMORY;
1.1409 + } else {
1.1410 + if (aRunCount)
1.1411 + *aRunCount = mRunCount;
1.1412 + return NS_OK;
1.1413 + }
1.1414 +}
1.1415 +
1.1416 +nsresult nsBidi::GetVisualRun(int32_t aRunIndex, int32_t *aLogicalStart, int32_t *aLength, nsBidiDirection *aDirection)
1.1417 +{
1.1418 + if( aRunIndex<0 ||
1.1419 + (mRunCount==-1 && !GetRuns()) ||
1.1420 + aRunIndex>=mRunCount
1.1421 + ) {
1.1422 + *aDirection = NSBIDI_LTR;
1.1423 + return NS_OK;
1.1424 + } else {
1.1425 + int32_t start=mRuns[aRunIndex].logicalStart;
1.1426 + if(aLogicalStart!=nullptr) {
1.1427 + *aLogicalStart=GET_INDEX(start);
1.1428 + }
1.1429 + if(aLength!=nullptr) {
1.1430 + if(aRunIndex>0) {
1.1431 + *aLength=mRuns[aRunIndex].visualLimit-
1.1432 + mRuns[aRunIndex-1].visualLimit;
1.1433 + } else {
1.1434 + *aLength=mRuns[0].visualLimit;
1.1435 + }
1.1436 + }
1.1437 + *aDirection = (nsBidiDirection)GET_ODD_BIT(start);
1.1438 + return NS_OK;
1.1439 + }
1.1440 +}
1.1441 +
1.1442 +/* compute the runs array --------------------------------------------------- */
1.1443 +
1.1444 +/*
1.1445 + * Compute the runs array from the levels array.
1.1446 + * After GetRuns() returns true, runCount is guaranteed to be >0
1.1447 + * and the runs are reordered.
1.1448 + * Odd-level runs have visualStart on their visual right edge and
1.1449 + * they progress visually to the left.
1.1450 + */
1.1451 +bool nsBidi::GetRuns()
1.1452 +{
1.1453 + if(mDirection!=NSBIDI_MIXED) {
1.1454 + /* simple, single-run case - this covers length==0 */
1.1455 + GetSingleRun(mParaLevel);
1.1456 + } else /* NSBIDI_MIXED, length>0 */ {
1.1457 + /* mixed directionality */
1.1458 + int32_t length=mLength, limit=length;
1.1459 +
1.1460 + /*
1.1461 + * If there are WS characters at the end of the line
1.1462 + * and the run preceding them has a level different from
1.1463 + * paraLevel, then they will form their own run at paraLevel (L1).
1.1464 + * Count them separately.
1.1465 + * We need some special treatment for this in order to not
1.1466 + * modify the levels array which a line nsBidi object shares
1.1467 + * with its paragraph parent and its other line siblings.
1.1468 + * In other words, for the trailing WS, it may be
1.1469 + * levels[]!=paraLevel but we have to treat it like it were so.
1.1470 + */
1.1471 + limit=mTrailingWSStart;
1.1472 + if(limit==0) {
1.1473 + /* there is only WS on this line */
1.1474 + GetSingleRun(mParaLevel);
1.1475 + } else {
1.1476 + nsBidiLevel *levels=mLevels;
1.1477 + int32_t i, runCount;
1.1478 + nsBidiLevel level=NSBIDI_DEFAULT_LTR; /* initialize with no valid level */
1.1479 +
1.1480 + /* count the runs, there is at least one non-WS run, and limit>0 */
1.1481 + runCount=0;
1.1482 + for(i=0; i<limit; ++i) {
1.1483 + /* increment runCount at the start of each run */
1.1484 + if(levels[i]!=level) {
1.1485 + ++runCount;
1.1486 + level=levels[i];
1.1487 + }
1.1488 + }
1.1489 +
1.1490 + /*
1.1491 + * We don't need to see if the last run can be merged with a trailing
1.1492 + * WS run because SetTrailingWSStart() would have done that.
1.1493 + */
1.1494 + if(runCount==1 && limit==length) {
1.1495 + /* There is only one non-WS run and no trailing WS-run. */
1.1496 + GetSingleRun(levels[0]);
1.1497 + } else /* runCount>1 || limit<length */ {
1.1498 + /* allocate and set the runs */
1.1499 + Run *runs;
1.1500 + int32_t runIndex, start;
1.1501 + nsBidiLevel minLevel=NSBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;
1.1502 +
1.1503 + /* now, count a (non-mergable) WS run */
1.1504 + if(limit<length) {
1.1505 + ++runCount;
1.1506 + }
1.1507 +
1.1508 + /* runCount>1 */
1.1509 + if(GETRUNSMEMORY(runCount)) {
1.1510 + runs=mRunsMemory;
1.1511 + } else {
1.1512 + return false;
1.1513 + }
1.1514 +
1.1515 + /* set the runs */
1.1516 + /* this could be optimized, e.g.: 464->444, 484->444, 575->555, 595->555 */
1.1517 + /* however, that would take longer and make other functions more complicated */
1.1518 + runIndex=0;
1.1519 +
1.1520 + /* search for the run ends */
1.1521 + start=0;
1.1522 + level=levels[0];
1.1523 + if(level<minLevel) {
1.1524 + minLevel=level;
1.1525 + }
1.1526 + if(level>maxLevel) {
1.1527 + maxLevel=level;
1.1528 + }
1.1529 +
1.1530 + /* initialize visualLimit values with the run lengths */
1.1531 + for(i=1; i<limit; ++i) {
1.1532 + if(levels[i]!=level) {
1.1533 + /* i is another run limit */
1.1534 + runs[runIndex].logicalStart=start;
1.1535 + runs[runIndex].visualLimit=i-start;
1.1536 + start=i;
1.1537 +
1.1538 + level=levels[i];
1.1539 + if(level<minLevel) {
1.1540 + minLevel=level;
1.1541 + }
1.1542 + if(level>maxLevel) {
1.1543 + maxLevel=level;
1.1544 + }
1.1545 + ++runIndex;
1.1546 + }
1.1547 + }
1.1548 +
1.1549 + /* finish the last run at i==limit */
1.1550 + runs[runIndex].logicalStart=start;
1.1551 + runs[runIndex].visualLimit=limit-start;
1.1552 + ++runIndex;
1.1553 +
1.1554 + if(limit<length) {
1.1555 + /* there is a separate WS run */
1.1556 + runs[runIndex].logicalStart=limit;
1.1557 + runs[runIndex].visualLimit=length-limit;
1.1558 + if(mParaLevel<minLevel) {
1.1559 + minLevel=mParaLevel;
1.1560 + }
1.1561 + }
1.1562 +
1.1563 + /* set the object fields */
1.1564 + mRuns=runs;
1.1565 + mRunCount=runCount;
1.1566 +
1.1567 + ReorderLine(minLevel, maxLevel);
1.1568 +
1.1569 + /* now add the direction flags and adjust the visualLimit's to be just that */
1.1570 + ADD_ODD_BIT_FROM_LEVEL(runs[0].logicalStart, levels[runs[0].logicalStart]);
1.1571 + limit=runs[0].visualLimit;
1.1572 + for(i=1; i<runIndex; ++i) {
1.1573 + ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
1.1574 + limit=runs[i].visualLimit+=limit;
1.1575 + }
1.1576 +
1.1577 + /* same for the trailing WS run */
1.1578 + if(runIndex<runCount) {
1.1579 + ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, mParaLevel);
1.1580 + runs[runIndex].visualLimit+=limit;
1.1581 + }
1.1582 + }
1.1583 + }
1.1584 + }
1.1585 + return true;
1.1586 +}
1.1587 +
1.1588 +/* in trivial cases there is only one trivial run; called by GetRuns() */
1.1589 +void nsBidi::GetSingleRun(nsBidiLevel aLevel)
1.1590 +{
1.1591 + /* simple, single-run case */
1.1592 + mRuns=mSimpleRuns;
1.1593 + mRunCount=1;
1.1594 +
1.1595 + /* fill and reorder the single run */
1.1596 + mRuns[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, aLevel);
1.1597 + mRuns[0].visualLimit=mLength;
1.1598 +}
1.1599 +
1.1600 +/* reorder the runs array (L2) ---------------------------------------------- */
1.1601 +
1.1602 +/*
1.1603 + * Reorder the same-level runs in the runs array.
1.1604 + * Here, runCount>1 and maxLevel>=minLevel>=paraLevel.
1.1605 + * All the visualStart fields=logical start before reordering.
1.1606 + * The "odd" bits are not set yet.
1.1607 + *
1.1608 + * Reordering with this data structure lends itself to some handy shortcuts:
1.1609 + *
1.1610 + * Since each run is moved but not modified, and since at the initial maxLevel
1.1611 + * each sequence of same-level runs consists of only one run each, we
1.1612 + * don't need to do anything there and can predecrement maxLevel.
1.1613 + * In many simple cases, the reordering is thus done entirely in the
1.1614 + * index mapping.
1.1615 + * Also, reordering occurs only down to the lowest odd level that occurs,
1.1616 + * which is minLevel|1. However, if the lowest level itself is odd, then
1.1617 + * in the last reordering the sequence of the runs at this level or higher
1.1618 + * will be all runs, and we don't need the elaborate loop to search for them.
1.1619 + * This is covered by ++minLevel instead of minLevel|=1 followed
1.1620 + * by an extra reorder-all after the reorder-some loop.
1.1621 + * About a trailing WS run:
1.1622 + * Such a run would need special treatment because its level is not
1.1623 + * reflected in levels[] if this is not a paragraph object.
1.1624 + * Instead, all characters from trailingWSStart on are implicitly at
1.1625 + * paraLevel.
1.1626 + * However, for all maxLevel>paraLevel, this run will never be reordered
1.1627 + * and does not need to be taken into account. maxLevel==paraLevel is only reordered
1.1628 + * if minLevel==paraLevel is odd, which is done in the extra segment.
1.1629 + * This means that for the main reordering loop we don't need to consider
1.1630 + * this run and can --runCount. If it is later part of the all-runs
1.1631 + * reordering, then runCount is adjusted accordingly.
1.1632 + */
1.1633 +void nsBidi::ReorderLine(nsBidiLevel aMinLevel, nsBidiLevel aMaxLevel)
1.1634 +{
1.1635 + Run *runs;
1.1636 + nsBidiLevel *levels;
1.1637 + int32_t firstRun, endRun, limitRun, runCount, temp;
1.1638 +
1.1639 + /* nothing to do? */
1.1640 + if(aMaxLevel<=(aMinLevel|1)) {
1.1641 + return;
1.1642 + }
1.1643 +
1.1644 + /*
1.1645 + * Reorder only down to the lowest odd level
1.1646 + * and reorder at an odd aMinLevel in a separate, simpler loop.
1.1647 + * See comments above for why aMinLevel is always incremented.
1.1648 + */
1.1649 + ++aMinLevel;
1.1650 +
1.1651 + runs=mRuns;
1.1652 + levels=mLevels;
1.1653 + runCount=mRunCount;
1.1654 +
1.1655 + /* do not include the WS run at paraLevel<=old aMinLevel except in the simple loop */
1.1656 + if(mTrailingWSStart<mLength) {
1.1657 + --runCount;
1.1658 + }
1.1659 +
1.1660 + while(--aMaxLevel>=aMinLevel) {
1.1661 + firstRun=0;
1.1662 +
1.1663 + /* loop for all sequences of runs */
1.1664 + for(;;) {
1.1665 + /* look for a sequence of runs that are all at >=aMaxLevel */
1.1666 + /* look for the first run of such a sequence */
1.1667 + while(firstRun<runCount && levels[runs[firstRun].logicalStart]<aMaxLevel) {
1.1668 + ++firstRun;
1.1669 + }
1.1670 + if(firstRun>=runCount) {
1.1671 + break; /* no more such runs */
1.1672 + }
1.1673 +
1.1674 + /* look for the limit run of such a sequence (the run behind it) */
1.1675 + for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=aMaxLevel;) {}
1.1676 +
1.1677 + /* Swap the entire sequence of runs from firstRun to limitRun-1. */
1.1678 + endRun=limitRun-1;
1.1679 + while(firstRun<endRun) {
1.1680 + temp=runs[firstRun].logicalStart;
1.1681 + runs[firstRun].logicalStart=runs[endRun].logicalStart;
1.1682 + runs[endRun].logicalStart=temp;
1.1683 +
1.1684 + temp=runs[firstRun].visualLimit;
1.1685 + runs[firstRun].visualLimit=runs[endRun].visualLimit;
1.1686 + runs[endRun].visualLimit=temp;
1.1687 +
1.1688 + ++firstRun;
1.1689 + --endRun;
1.1690 + }
1.1691 +
1.1692 + if(limitRun==runCount) {
1.1693 + break; /* no more such runs */
1.1694 + } else {
1.1695 + firstRun=limitRun+1;
1.1696 + }
1.1697 + }
1.1698 + }
1.1699 +
1.1700 + /* now do aMaxLevel==old aMinLevel (==odd!), see above */
1.1701 + if(!(aMinLevel&1)) {
1.1702 + firstRun=0;
1.1703 +
1.1704 + /* include the trailing WS run in this complete reordering */
1.1705 + if(mTrailingWSStart==mLength) {
1.1706 + --runCount;
1.1707 + }
1.1708 +
1.1709 + /* Swap the entire sequence of all runs. (endRun==runCount) */
1.1710 + while(firstRun<runCount) {
1.1711 + temp=runs[firstRun].logicalStart;
1.1712 + runs[firstRun].logicalStart=runs[runCount].logicalStart;
1.1713 + runs[runCount].logicalStart=temp;
1.1714 +
1.1715 + temp=runs[firstRun].visualLimit;
1.1716 + runs[firstRun].visualLimit=runs[runCount].visualLimit;
1.1717 + runs[runCount].visualLimit=temp;
1.1718 +
1.1719 + ++firstRun;
1.1720 + --runCount;
1.1721 + }
1.1722 + }
1.1723 +}
1.1724 +
1.1725 +nsresult nsBidi::ReorderVisual(const nsBidiLevel *aLevels, int32_t aLength, int32_t *aIndexMap)
1.1726 +{
1.1727 + int32_t start, end, limit, temp;
1.1728 + nsBidiLevel minLevel, maxLevel;
1.1729 +
1.1730 + if(aIndexMap==nullptr ||
1.1731 + !PrepareReorder(aLevels, aLength, aIndexMap, &minLevel, &maxLevel)) {
1.1732 + return NS_OK;
1.1733 + }
1.1734 +
1.1735 + /* nothing to do? */
1.1736 + if(minLevel==maxLevel && (minLevel&1)==0) {
1.1737 + return NS_OK;
1.1738 + }
1.1739 +
1.1740 + /* reorder only down to the lowest odd level */
1.1741 + minLevel|=1;
1.1742 +
1.1743 + /* loop maxLevel..minLevel */
1.1744 + do {
1.1745 + start=0;
1.1746 +
1.1747 + /* loop for all sequences of levels to reorder at the current maxLevel */
1.1748 + for(;;) {
1.1749 + /* look for a sequence of levels that are all at >=maxLevel */
1.1750 + /* look for the first index of such a sequence */
1.1751 + while(start<aLength && aLevels[start]<maxLevel) {
1.1752 + ++start;
1.1753 + }
1.1754 + if(start>=aLength) {
1.1755 + break; /* no more such runs */
1.1756 + }
1.1757 +
1.1758 + /* look for the limit of such a sequence (the index behind it) */
1.1759 + for(limit=start; ++limit<aLength && aLevels[limit]>=maxLevel;) {}
1.1760 +
1.1761 + /*
1.1762 + * Swap the entire interval of indexes from start to limit-1.
1.1763 + * We don't need to swap the levels for the purpose of this
1.1764 + * algorithm: the sequence of levels that we look at does not
1.1765 + * move anyway.
1.1766 + */
1.1767 + end=limit-1;
1.1768 + while(start<end) {
1.1769 + temp=aIndexMap[start];
1.1770 + aIndexMap[start]=aIndexMap[end];
1.1771 + aIndexMap[end]=temp;
1.1772 +
1.1773 + ++start;
1.1774 + --end;
1.1775 + }
1.1776 +
1.1777 + if(limit==aLength) {
1.1778 + break; /* no more such sequences */
1.1779 + } else {
1.1780 + start=limit+1;
1.1781 + }
1.1782 + }
1.1783 + } while(--maxLevel>=minLevel);
1.1784 +
1.1785 + return NS_OK;
1.1786 +}
1.1787 +
1.1788 +bool nsBidi::PrepareReorder(const nsBidiLevel *aLevels, int32_t aLength,
1.1789 + int32_t *aIndexMap,
1.1790 + nsBidiLevel *aMinLevel, nsBidiLevel *aMaxLevel)
1.1791 +{
1.1792 + int32_t start;
1.1793 + nsBidiLevel level, minLevel, maxLevel;
1.1794 +
1.1795 + if(aLevels==nullptr || aLength<=0) {
1.1796 + return false;
1.1797 + }
1.1798 +
1.1799 + /* determine minLevel and maxLevel */
1.1800 + minLevel=NSBIDI_MAX_EXPLICIT_LEVEL+1;
1.1801 + maxLevel=0;
1.1802 + for(start=aLength; start>0;) {
1.1803 + level=aLevels[--start];
1.1804 + if(level>NSBIDI_MAX_EXPLICIT_LEVEL+1) {
1.1805 + return false;
1.1806 + }
1.1807 + if(level<minLevel) {
1.1808 + minLevel=level;
1.1809 + }
1.1810 + if(level>maxLevel) {
1.1811 + maxLevel=level;
1.1812 + }
1.1813 + }
1.1814 + *aMinLevel=minLevel;
1.1815 + *aMaxLevel=maxLevel;
1.1816 +
1.1817 + /* initialize the index map */
1.1818 + for(start=aLength; start>0;) {
1.1819 + --start;
1.1820 + aIndexMap[start]=start;
1.1821 + }
1.1822 +
1.1823 + return true;
1.1824 +}
1.1825 +
1.1826 +#ifdef FULL_BIDI_ENGINE
1.1827 +/* API functions for logical<->visual mapping ------------------------------- */
1.1828 +
1.1829 +nsresult nsBidi::GetVisualIndex(int32_t aLogicalIndex, int32_t* aVisualIndex) {
1.1830 + if(aLogicalIndex<0 || mLength<=aLogicalIndex) {
1.1831 + return NS_ERROR_INVALID_ARG;
1.1832 + } else {
1.1833 + /* we can do the trivial cases without the runs array */
1.1834 + switch(mDirection) {
1.1835 + case NSBIDI_LTR:
1.1836 + *aVisualIndex = aLogicalIndex;
1.1837 + return NS_OK;
1.1838 + case NSBIDI_RTL:
1.1839 + *aVisualIndex = mLength-aLogicalIndex-1;
1.1840 + return NS_OK;
1.1841 + default:
1.1842 + if(mRunCount<0 && !GetRuns()) {
1.1843 + return NS_ERROR_OUT_OF_MEMORY;
1.1844 + } else {
1.1845 + Run *runs=mRuns;
1.1846 + int32_t i, visualStart=0, offset, length;
1.1847 +
1.1848 + /* linear search for the run, search on the visual runs */
1.1849 + for(i=0;; ++i) {
1.1850 + length=runs[i].visualLimit-visualStart;
1.1851 + offset=aLogicalIndex-GET_INDEX(runs[i].logicalStart);
1.1852 + if(offset>=0 && offset<length) {
1.1853 + if(IS_EVEN_RUN(runs[i].logicalStart)) {
1.1854 + /* LTR */
1.1855 + *aVisualIndex = visualStart+offset;
1.1856 + return NS_OK;
1.1857 + } else {
1.1858 + /* RTL */
1.1859 + *aVisualIndex = visualStart+length-offset-1;
1.1860 + return NS_OK;
1.1861 + }
1.1862 + }
1.1863 + visualStart+=length;
1.1864 + }
1.1865 + }
1.1866 + }
1.1867 + }
1.1868 +}
1.1869 +
1.1870 +nsresult nsBidi::GetLogicalIndex(int32_t aVisualIndex, int32_t *aLogicalIndex)
1.1871 +{
1.1872 + if(aVisualIndex<0 || mLength<=aVisualIndex) {
1.1873 + return NS_ERROR_INVALID_ARG;
1.1874 + } else {
1.1875 + /* we can do the trivial cases without the runs array */
1.1876 + switch(mDirection) {
1.1877 + case NSBIDI_LTR:
1.1878 + *aLogicalIndex = aVisualIndex;
1.1879 + return NS_OK;
1.1880 + case NSBIDI_RTL:
1.1881 + *aLogicalIndex = mLength-aVisualIndex-1;
1.1882 + return NS_OK;
1.1883 + default:
1.1884 + if(mRunCount<0 && !GetRuns()) {
1.1885 + return NS_ERROR_OUT_OF_MEMORY;
1.1886 + } else {
1.1887 + Run *runs=mRuns;
1.1888 + int32_t i, runCount=mRunCount, start;
1.1889 +
1.1890 + if(runCount<=10) {
1.1891 + /* linear search for the run */
1.1892 + for(i=0; aVisualIndex>=runs[i].visualLimit; ++i) {}
1.1893 + } else {
1.1894 + /* binary search for the run */
1.1895 + int32_t start=0, limit=runCount;
1.1896 +
1.1897 + /* the middle if() will guaranteed find the run, we don't need a loop limit */
1.1898 + for(;;) {
1.1899 + i=(start+limit)/2;
1.1900 + if(aVisualIndex>=runs[i].visualLimit) {
1.1901 + start=i+1;
1.1902 + } else if(i==0 || aVisualIndex>=runs[i-1].visualLimit) {
1.1903 + break;
1.1904 + } else {
1.1905 + limit=i;
1.1906 + }
1.1907 + }
1.1908 + }
1.1909 +
1.1910 + start=runs[i].logicalStart;
1.1911 + if(IS_EVEN_RUN(start)) {
1.1912 + /* LTR */
1.1913 + /* the offset in runs[i] is aVisualIndex-runs[i-1].visualLimit */
1.1914 + if(i>0) {
1.1915 + aVisualIndex-=runs[i-1].visualLimit;
1.1916 + }
1.1917 + *aLogicalIndex = GET_INDEX(start)+aVisualIndex;
1.1918 + return NS_OK;
1.1919 + } else {
1.1920 + /* RTL */
1.1921 + *aLogicalIndex = GET_INDEX(start)+runs[i].visualLimit-aVisualIndex-1;
1.1922 + return NS_OK;
1.1923 + }
1.1924 + }
1.1925 + }
1.1926 + }
1.1927 +}
1.1928 +
1.1929 +nsresult nsBidi::GetLogicalMap(int32_t *aIndexMap)
1.1930 +{
1.1931 + nsBidiLevel *levels;
1.1932 + nsresult rv;
1.1933 +
1.1934 + /* GetLevels() checks all of its and our arguments */
1.1935 + rv = GetLevels(&levels);
1.1936 + if(NS_FAILED(rv)) {
1.1937 + return rv;
1.1938 + } else if(aIndexMap==nullptr) {
1.1939 + return NS_ERROR_INVALID_ARG;
1.1940 + } else {
1.1941 + return ReorderLogical(levels, mLength, aIndexMap);
1.1942 + }
1.1943 +}
1.1944 +
1.1945 +nsresult nsBidi::GetVisualMap(int32_t *aIndexMap)
1.1946 +{
1.1947 + int32_t* runCount=nullptr;
1.1948 + nsresult rv;
1.1949 +
1.1950 + /* CountRuns() checks all of its and our arguments */
1.1951 + rv = CountRuns(runCount);
1.1952 + if(NS_FAILED(rv)) {
1.1953 + return rv;
1.1954 + } else if(aIndexMap==nullptr) {
1.1955 + return NS_ERROR_INVALID_ARG;
1.1956 + } else {
1.1957 + /* fill a visual-to-logical index map using the runs[] */
1.1958 + Run *runs=mRuns, *runsLimit=runs+mRunCount;
1.1959 + int32_t logicalStart, visualStart, visualLimit;
1.1960 +
1.1961 + visualStart=0;
1.1962 + for(; runs<runsLimit; ++runs) {
1.1963 + logicalStart=runs->logicalStart;
1.1964 + visualLimit=runs->visualLimit;
1.1965 + if(IS_EVEN_RUN(logicalStart)) {
1.1966 + do { /* LTR */
1.1967 + *aIndexMap++ = logicalStart++;
1.1968 + } while(++visualStart<visualLimit);
1.1969 + } else {
1.1970 + REMOVE_ODD_BIT(logicalStart);
1.1971 + logicalStart+=visualLimit-visualStart; /* logicalLimit */
1.1972 + do { /* RTL */
1.1973 + *aIndexMap++ = --logicalStart;
1.1974 + } while(++visualStart<visualLimit);
1.1975 + }
1.1976 + /* visualStart==visualLimit; */
1.1977 + }
1.1978 + return NS_OK;
1.1979 + }
1.1980 +}
1.1981 +
1.1982 +/* reorder a line based on a levels array (L2) ------------------------------ */
1.1983 +
1.1984 +nsresult nsBidi::ReorderLogical(const nsBidiLevel *aLevels, int32_t aLength, int32_t *aIndexMap)
1.1985 +{
1.1986 + int32_t start, limit, sumOfSosEos;
1.1987 + nsBidiLevel minLevel, maxLevel;
1.1988 +
1.1989 + if(aIndexMap==nullptr ||
1.1990 + !PrepareReorder(aLevels, aLength, aIndexMap, &minLevel, &maxLevel)) {
1.1991 + return NS_OK;
1.1992 + }
1.1993 +
1.1994 + /* nothing to do? */
1.1995 + if(minLevel==maxLevel && (minLevel&1)==0) {
1.1996 + return NS_OK;
1.1997 + }
1.1998 +
1.1999 + /* reorder only down to the lowest odd level */
1.2000 + minLevel|=1;
1.2001 +
1.2002 + /* loop maxLevel..minLevel */
1.2003 + do {
1.2004 + start=0;
1.2005 +
1.2006 + /* loop for all sequences of levels to reorder at the current maxLevel */
1.2007 + for(;;) {
1.2008 + /* look for a sequence of levels that are all at >=maxLevel */
1.2009 + /* look for the first index of such a sequence */
1.2010 + while(start<aLength && aLevels[start]<maxLevel) {
1.2011 + ++start;
1.2012 + }
1.2013 + if(start>=aLength) {
1.2014 + break; /* no more such sequences */
1.2015 + }
1.2016 +
1.2017 + /* look for the limit of such a sequence (the index behind it) */
1.2018 + for(limit=start; ++limit<aLength && aLevels[limit]>=maxLevel;) {}
1.2019 +
1.2020 + /*
1.2021 + * sos=start of sequence, eos=end of sequence
1.2022 + *
1.2023 + * The closed (inclusive) interval from sos to eos includes all the logical
1.2024 + * and visual indexes within this sequence. They are logically and
1.2025 + * visually contiguous and in the same range.
1.2026 + *
1.2027 + * For each run, the new visual index=sos+eos-old visual index;
1.2028 + * we pre-add sos+eos into sumOfSosEos ->
1.2029 + * new visual index=sumOfSosEos-old visual index;
1.2030 + */
1.2031 + sumOfSosEos=start+limit-1;
1.2032 +
1.2033 + /* reorder each index in the sequence */
1.2034 + do {
1.2035 + aIndexMap[start]=sumOfSosEos-aIndexMap[start];
1.2036 + } while(++start<limit);
1.2037 +
1.2038 + /* start==limit */
1.2039 + if(limit==aLength) {
1.2040 + break; /* no more such sequences */
1.2041 + } else {
1.2042 + start=limit+1;
1.2043 + }
1.2044 + }
1.2045 + } while(--maxLevel>=minLevel);
1.2046 +
1.2047 + return NS_OK;
1.2048 +}
1.2049 +
1.2050 +nsresult nsBidi::InvertMap(const int32_t *aSrcMap, int32_t *aDestMap, int32_t aLength)
1.2051 +{
1.2052 + if(aSrcMap!=nullptr && aDestMap!=nullptr) {
1.2053 + aSrcMap+=aLength;
1.2054 + while(aLength>0) {
1.2055 + aDestMap[*--aSrcMap]=--aLength;
1.2056 + }
1.2057 + }
1.2058 + return NS_OK;
1.2059 +}
1.2060 +
1.2061 +int32_t nsBidi::doWriteReverse(const char16_t *src, int32_t srcLength,
1.2062 + char16_t *dest, uint16_t options) {
1.2063 + /*
1.2064 + * RTL run -
1.2065 + *
1.2066 + * RTL runs need to be copied to the destination in reverse order
1.2067 + * of code points, not code units, to keep Unicode characters intact.
1.2068 + *
1.2069 + * The general strategy for this is to read the source text
1.2070 + * in backward order, collect all code units for a code point
1.2071 + * (and optionally following combining characters, see below),
1.2072 + * and copy all these code units in ascending order
1.2073 + * to the destination for this run.
1.2074 + *
1.2075 + * Several options request whether combining characters
1.2076 + * should be kept after their base characters,
1.2077 + * whether Bidi control characters should be removed, and
1.2078 + * whether characters should be replaced by their mirror-image
1.2079 + * equivalent Unicode characters.
1.2080 + */
1.2081 + int32_t i, j, destSize;
1.2082 + uint32_t c;
1.2083 +
1.2084 + /* optimize for several combinations of options */
1.2085 + switch(options&(NSBIDI_REMOVE_BIDI_CONTROLS|NSBIDI_DO_MIRRORING|NSBIDI_KEEP_BASE_COMBINING)) {
1.2086 + case 0:
1.2087 + /*
1.2088 + * With none of the "complicated" options set, the destination
1.2089 + * run will have the same length as the source run,
1.2090 + * and there is no mirroring and no keeping combining characters
1.2091 + * with their base characters.
1.2092 + */
1.2093 + destSize=srcLength;
1.2094 +
1.2095 + /* preserve character integrity */
1.2096 + do {
1.2097 + /* i is always after the last code unit known to need to be kept in this segment */
1.2098 + i=srcLength;
1.2099 +
1.2100 + /* collect code units for one base character */
1.2101 + UTF_BACK_1(src, 0, srcLength);
1.2102 +
1.2103 + /* copy this base character */
1.2104 + j=srcLength;
1.2105 + do {
1.2106 + *dest++=src[j++];
1.2107 + } while(j<i);
1.2108 + } while(srcLength>0);
1.2109 + break;
1.2110 + case NSBIDI_KEEP_BASE_COMBINING:
1.2111 + /*
1.2112 + * Here, too, the destination
1.2113 + * run will have the same length as the source run,
1.2114 + * and there is no mirroring.
1.2115 + * We do need to keep combining characters with their base characters.
1.2116 + */
1.2117 + destSize=srcLength;
1.2118 +
1.2119 + /* preserve character integrity */
1.2120 + do {
1.2121 + /* i is always after the last code unit known to need to be kept in this segment */
1.2122 + i=srcLength;
1.2123 +
1.2124 + /* collect code units and modifier letters for one base character */
1.2125 + do {
1.2126 + UTF_PREV_CHAR(src, 0, srcLength, c);
1.2127 + } while(srcLength>0 && IsBidiCategory(c, eBidiCat_NSM));
1.2128 +
1.2129 + /* copy this "user character" */
1.2130 + j=srcLength;
1.2131 + do {
1.2132 + *dest++=src[j++];
1.2133 + } while(j<i);
1.2134 + } while(srcLength>0);
1.2135 + break;
1.2136 + default:
1.2137 + /*
1.2138 + * With several "complicated" options set, this is the most
1.2139 + * general and the slowest copying of an RTL run.
1.2140 + * We will do mirroring, remove Bidi controls, and
1.2141 + * keep combining characters with their base characters
1.2142 + * as requested.
1.2143 + */
1.2144 + if(!(options&NSBIDI_REMOVE_BIDI_CONTROLS)) {
1.2145 + i=srcLength;
1.2146 + } else {
1.2147 + /* we need to find out the destination length of the run,
1.2148 + which will not include the Bidi control characters */
1.2149 + int32_t length=srcLength;
1.2150 + char16_t ch;
1.2151 +
1.2152 + i=0;
1.2153 + do {
1.2154 + ch=*src++;
1.2155 + if (!IsBidiControl((uint32_t)ch)) {
1.2156 + ++i;
1.2157 + }
1.2158 + } while(--length>0);
1.2159 + src-=srcLength;
1.2160 + }
1.2161 + destSize=i;
1.2162 +
1.2163 + /* preserve character integrity */
1.2164 + do {
1.2165 + /* i is always after the last code unit known to need to be kept in this segment */
1.2166 + i=srcLength;
1.2167 +
1.2168 + /* collect code units for one base character */
1.2169 + UTF_PREV_CHAR(src, 0, srcLength, c);
1.2170 + if(options&NSBIDI_KEEP_BASE_COMBINING) {
1.2171 + /* collect modifier letters for this base character */
1.2172 + while(srcLength>0 && IsBidiCategory(c, eBidiCat_NSM)) {
1.2173 + UTF_PREV_CHAR(src, 0, srcLength, c);
1.2174 + }
1.2175 + }
1.2176 +
1.2177 + if(options&NSBIDI_REMOVE_BIDI_CONTROLS && IsBidiControl(c)) {
1.2178 + /* do not copy this Bidi control character */
1.2179 + continue;
1.2180 + }
1.2181 +
1.2182 + /* copy this "user character" */
1.2183 + j=srcLength;
1.2184 + if(options&NSBIDI_DO_MIRRORING) {
1.2185 + /* mirror only the base character */
1.2186 + c = SymmSwap(c);
1.2187 +
1.2188 + int32_t k=0;
1.2189 + UTF_APPEND_CHAR_UNSAFE(dest, k, c);
1.2190 + dest+=k;
1.2191 + j+=k;
1.2192 + }
1.2193 + while(j<i) {
1.2194 + *dest++=src[j++];
1.2195 + }
1.2196 + } while(srcLength>0);
1.2197 + break;
1.2198 + } /* end of switch */
1.2199 + return destSize;
1.2200 +}
1.2201 +
1.2202 +nsresult nsBidi::WriteReverse(const char16_t *aSrc, int32_t aSrcLength, char16_t *aDest, uint16_t aOptions, int32_t *aDestSize)
1.2203 +{
1.2204 + if( aSrc==nullptr || aSrcLength<0 ||
1.2205 + aDest==nullptr
1.2206 + ) {
1.2207 + return NS_ERROR_INVALID_ARG;
1.2208 + }
1.2209 +
1.2210 + /* do input and output overlap? */
1.2211 + if( aSrc>=aDest && aSrc<aDest+aSrcLength ||
1.2212 + aDest>=aSrc && aDest<aSrc+aSrcLength
1.2213 + ) {
1.2214 + return NS_ERROR_INVALID_ARG;
1.2215 + }
1.2216 +
1.2217 + if(aSrcLength>0) {
1.2218 + *aDestSize = doWriteReverse(aSrc, aSrcLength, aDest, aOptions);
1.2219 + }
1.2220 + return NS_OK;
1.2221 +}
1.2222 +#endif // FULL_BIDI_ENGINE
