lib/fribidi-bidi.c

   1 /* FriBidi
   2  * fribidi-bidi.c - bidirectional algorithm
   3  *
   4  * Authors:
   5  *   Behdad Esfahbod, 2001, 2002, 2004
   6  *   Dov Grobgeld, 1999, 2000, 2017
   7  *
   8  * Copyright (C) 2004 Sharif FarsiWeb, Inc
   9  * Copyright (C) 2001,2002 Behdad Esfahbod
  10  * Copyright (C) 1999,2000,2017 Dov Grobgeld
  11  *
  12  * This library is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public
  14  * License as published by the Free Software Foundation; either
  15  * version 2.1 of the License, or (at your option) any later version.
  16  *
  17  * This library is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public License
  23  * along with this library, in a file named COPYING; if not, write to the
  24  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  25  * Boston, MA 02110-1301, USA
  26  *
  27  * For licensing issues, contact <fribidi.license@gmail.com>.
  28  */
  29
  30 #include "common.h"
  31
  32 #include <fribidi-bidi.h>
  33 #include <fribidi-mirroring.h>
  34 #include <fribidi-brackets.h>
  35 #include <fribidi-unicode.h>
  36
  37 #include "bidi-types.h"
  38 #include "run.h"
  39
  40 /*
  41  * This file implements most of Unicode Standard Annex #9, Tracking Number 13.
  42  */
  43
  44 #ifndef MAX
  45 # define MAX(a,b) ((a) > (b) ? (a) : (b))
  46 #endif /* !MAX */
  47
  48 /* Some convenience macros */
  49 #define RL_TYPE(list) ((list)->type)
  50 #define RL_LEN(list) ((list)->len)
  51 #define RL_LEVEL(list) ((list)->level)
  52
  53 /* "Within this scope, bidirectional types EN and AN are treated as R" */
  54 #define RL_TYPE_AN_EN_AS_RTL(list) ( \
  55  (((list)->type == FRIBIDI_TYPE_AN) || ((list)->type == FRIBIDI_TYPE_EN) | ((list)->type == FRIBIDI_TYPE_RTL)) ? FRIBIDI_TYPE_RTL : (list)->type)
  56 #define RL_BRACKET_TYPE(list) ((list)->bracket_type)
  57 #define RL_ISOLATE_LEVEL(list) ((list)->isolate_level)
  58
  59 #define LOCAL_BRACKET_SIZE 16
  60
  61 /* Pairing nodes are used for holding a pair of open/close brackets as
  62    described in BD16. */
  63 struct _FriBidiPairingNodeStruct {
  64   FriBidiRun *open;
  65   FriBidiRun *close;
  66   struct _FriBidiPairingNodeStruct *next;
  67 };
  68 typedef struct _FriBidiPairingNodeStruct FriBidiPairingNode;
  69
  70 static FriBidiRun *
  71 merge_with_prev (
  72   FriBidiRun *second
  73 )
  74 {
  75   FriBidiRun *first;
  76
  77   fribidi_assert (second);
  78   fribidi_assert (second->next);
  79   first = second->prev;
  80   fribidi_assert (first);
  81
  82   first->next = second->next;
  83   first->next->prev = first;
  84   RL_LEN (first) += RL_LEN (second);
  85   if (second->next_isolate)
  86     second->next_isolate->prev_isolate = first;
  87   first->next_isolate = second->next_isolate;
  88
  89   fribidi_free (second);
  90   return first;
  91 }
  92
  93 static void
  94 compact_list (
  95   FriBidiRun *list
  96 )
  97 {
  98   fribidi_assert (list);
  99
 100   if (list->next)
 101     for_run_list (list, list)
 102       if (RL_TYPE (list->prev) == RL_TYPE (list)
 103           && RL_LEVEL (list->prev) == RL_LEVEL (list)
 104           && RL_BRACKET_TYPE(list) == FRIBIDI_NO_BRACKET /* Don't join brackets! */
 105           && RL_BRACKET_TYPE(list->prev) == FRIBIDI_NO_BRACKET
 106           )
 107       list = merge_with_prev (list);
 108 }
 109
 110 static void
 111 compact_neutrals (
 112   FriBidiRun *list
 113 )
 114 {
 115   fribidi_assert (list);
 116
 117   if (list->next)
 118     {
 119       for_run_list (list, list)
 120       {
 121         if (RL_LEVEL (list->prev) == RL_LEVEL (list)
 122             &&
 123             ((RL_TYPE (list->prev) == RL_TYPE (list)
 124               || (FRIBIDI_IS_NEUTRAL (RL_TYPE (list->prev))
 125                   && FRIBIDI_IS_NEUTRAL (RL_TYPE (list)))))
 126             && RL_BRACKET_TYPE(list) == FRIBIDI_NO_BRACKET /* Don't join brackets! */
 127             && RL_BRACKET_TYPE(list->prev) == FRIBIDI_NO_BRACKET
 128             )
 129           list = merge_with_prev (list);
 130       }
 131     }
 132 }
 133
 134 /* Search for an adjacent run in the forward or backward direction.
 135    It uses the next_isolate and prev_isolate run for short circuited searching.
 136  */
 137
 138 /* The static sentinel is used to signal the end of an isolating
 139    sequence */
 140 static FriBidiRun sentinel = { NULL, NULL, 0,0, FRIBIDI_TYPE_SENTINEL, -1,-1,FRIBIDI_NO_BRACKET, NULL, NULL };
 141
 142 static FriBidiRun *get_adjacent_run(FriBidiRun *list, fribidi_boolean forward, fribidi_boolean skip_neutral)
 143 {
 144   FriBidiRun *ppp = forward ? list->next_isolate : list->prev_isolate;
 145   if (!ppp)
 146     return &sentinel;
 147
 148   while (ppp)
 149     {
 150       FriBidiCharType ppp_type = RL_TYPE (ppp);
 151
 152       if (ppp_type == _FRIBIDI_TYPE_SENTINEL)
 153         break;
 154
 155       /* Note that when sweeping forward we continue one run
 156          beyond the PDI to see what lies behind. When looking
 157          backwards, this is not necessary as the leading isolate
 158          run has already been assigned the resolved level. */
 159       if (ppp->isolate_level > list->isolate_level   /* <- How can this be true? */
 160           || (forward && ppp_type == FRIBIDI_TYPE_PDI)
 161           || (skip_neutral && !FRIBIDI_IS_STRONG(ppp_type)))
 162         {
 163           ppp = forward ? ppp->next_isolate : ppp->prev_isolate;
 164           if (!ppp)
 165             ppp = &sentinel;
 166
 167           continue;
 168         }
 169       break;
 170     }
 171
 172   return ppp;
 173 }
 174
 175 #ifdef DEBUG
 176 /*======================================================================
 177  *  For debugging, define some functions for printing the types and the
 178  *  levels.
 179  *----------------------------------------------------------------------*/
 180
 181 static char char_from_level_array[] = {
 182   '$',                          /* -1 == FRIBIDI_SENTINEL, indicating
 183                                  * start or end of string. */
 184   /* 0-61 == 0-9,a-z,A-Z are the the only valid levels before resolving
 185    * implicits.  after that the level @ may be appear too. */
 186   '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 187   'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
 188   'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
 189   'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',
 190   'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 191   'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
 192   'Y', 'Z',
 193
 194   /* TBD - insert another 125-64 levels */
 195
 196   '@',                          /* 62 == only must appear after resolving
 197                                  * implicits. */
 198
 199   '!',                          /* 63 == FRIBIDI_LEVEL_INVALID, internal error,
 200                                  * this level shouldn't be seen.  */
 201
 202   '*', '*', '*', '*', '*'       /* >= 64 == overflows, this levels and higher
 203                                  * levels show a real bug!. */
 204 };
 205
 206 #define fribidi_char_from_level(level) char_from_level_array[(level) + 1]
 207
 208 static void
 209 print_types_re (
 210   const FriBidiRun *pp
 211 )
 212 {
 213   fribidi_assert (pp);
 214
 215   MSG ("  Run types  : ");
 216   for_run_list (pp, pp)
 217   {
 218     MSG6 ("%d:%d(%s)[%d,%d] ",
 219           pp->pos, pp->len, fribidi_get_bidi_type_name (pp->type), pp->level, pp->isolate_level);
 220   }
 221   MSG ("\n");
 222 }
 223
 224 static void
 225 print_resolved_levels (
 226   const FriBidiRun *pp
 227 )
 228 {
 229   fribidi_assert (pp);
 230
 231   MSG ("  Res. levels: ");
 232   for_run_list (pp, pp)
 233   {
 234     register FriBidiStrIndex i;
 235     for (i = RL_LEN (pp); i; i--)
 236       MSG2 ("%c", fribidi_char_from_level (RL_LEVEL (pp)));
 237   }
 238   MSG ("\n");
 239 }
 240
 241 static void
 242 print_resolved_types (
 243   const FriBidiRun *pp
 244 )
 245 {
 246   fribidi_assert (pp);
 247
 248   MSG ("  Res. types : ");
 249   for_run_list (pp, pp)
 250   {
 251     FriBidiStrIndex i;
 252     for (i = RL_LEN (pp); i; i--)
 253       MSG2 ("%s ", fribidi_get_bidi_type_name (pp->type));
 254   }
 255   MSG ("\n");
 256 }
 257
 258 static void
 259 print_bidi_string (
 260   /* input */
 261   const FriBidiCharType *bidi_types,
 262   const FriBidiStrIndex len
 263 )
 264 {
 265   register FriBidiStrIndex i;
 266
 267   fribidi_assert (bidi_types);
 268
 269   MSG ("  Org. types : ");
 270   for (i = 0; i < len; i++)
 271     MSG2 ("%s ", fribidi_get_bidi_type_name (bidi_types[i]));
 272   MSG ("\n");
 273 }
 274
 275 static void print_pairing_nodes(FriBidiPairingNode *nodes)
 276 {
 277   MSG ("Pairs: ");
 278   while (nodes)
 279     {
 280       MSG3 ("(%d, %d) ", nodes->open->pos, nodes->close->pos);
 281       nodes = nodes->next;
 282     }
 283   MSG ("\n");
 284 }
 285 #endif /* DEBUG */
 286
 287
 288 /*=========================================================================
 289  * define macros for push and pop the status in to / out of the stack
 290  *-------------------------------------------------------------------------*/
 291
 292 /* There are a few little points in pushing into and poping from the status
 293    stack:
 294    1. when the embedding level is not valid (more than
 295    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=125), you must reject it, and not to push
 296    into the stack, but when you see a PDF, you must find the matching code,
 297    and if it was pushed in the stack, pop it, it means you must pop if and
 298    only if you have pushed the matching code, the over_pushed var counts the
 299    number of rejected codes so far.
 300
 301    2. there's a more confusing point too, when the embedding level is exactly
 302    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL-1=124, an LRO, LRE, or LRI is rejected
 303    because the new level would be FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL+1=126, that
 304    is invalid; but an RLO, RLE, or RLI is accepted because the new level is
 305    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=125, that is valid, so the rejected codes
 306    may be not continuous in the logical order, in fact there are at most two
 307    continuous intervals of codes, with an RLO, RLE, or RLI between them.  To
 308    support this case, the first_interval var counts the number of rejected
 309    codes in the first interval, when it is 0, means that there is only one
 310    interval.
 311
 312 */
 313
 314 /* a. If this new level would be valid, then this embedding code is valid.
 315    Remember (push) the current embedding level and override status.
 316    Reset current level to this new level, and reset the override status to
 317    new_override.
 318    b. If the new level would not be valid, then this code is invalid. Don't
 319    change the current level or override status.
 320 */
 321 #define PUSH_STATUS \
 322     FRIBIDI_BEGIN_STMT \
 323       if LIKELY(over_pushed == 0 \
 324                 && isolate_overflow == 0 \
 325                 && new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL)   \
 326         { \
 327           if UNLIKELY(level == FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL - 1) \
 328             first_interval = over_pushed; \
 329           status_stack[stack_size].level = level; \
 330           status_stack[stack_size].isolate_level = isolate_level; \
 331           status_stack[stack_size].isolate = isolate; \
 332           status_stack[stack_size].override = override; \
 333           stack_size++; \
 334           level = new_level; \
 335           override = new_override; \
 336         } else if LIKELY(isolate_overflow == 0) \
 337           over_pushed++; \
 338     FRIBIDI_END_STMT
 339
 340 /* If there was a valid matching code, restore (pop) the last remembered
 341    (pushed) embedding level and directional override.
 342 */
 343 #define POP_STATUS \
 344     FRIBIDI_BEGIN_STMT \
 345       if (stack_size) \
 346       { \
 347         if UNLIKELY(over_pushed > first_interval) \
 348           over_pushed--; \
 349         else \
 350           { \
 351             if LIKELY(over_pushed == first_interval) \
 352               first_interval = 0; \
 353             stack_size--; \
 354             level = status_stack[stack_size].level; \
 355             override = status_stack[stack_size].override; \
 356             isolate = status_stack[stack_size].isolate; \
 357             isolate_level = status_stack[stack_size].isolate_level; \
 358           } \
 359       } \
 360     FRIBIDI_END_STMT
 361
 362
 363 /* Return the type of previous run or the SOR, if already at the start of
 364    a level run. */
 365 #define PREV_TYPE_OR_SOR(pp) \
 366     ( \
 367       RL_LEVEL(pp->prev) == RL_LEVEL(pp) ? \
 368         RL_TYPE(pp->prev) : \
 369         FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->prev), RL_LEVEL(pp))) \
 370     )
 371
 372 /* Return the type of next run or the EOR, if already at the end of
 373    a level run. */
 374 #define NEXT_TYPE_OR_EOR(pp) \
 375     ( \
 376       RL_LEVEL(pp->next) == RL_LEVEL(pp) ? \
 377         RL_TYPE(pp->next) : \
 378         FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->next), RL_LEVEL(pp))) \
 379     )
 380
 381
 382 /* Return the embedding direction of a link. */
 383 #define FRIBIDI_EMBEDDING_DIRECTION(link) \
 384     FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(link))
 385
 386
 387 FRIBIDI_ENTRY FriBidiParType
 388 fribidi_get_par_direction (
 389   /* input */
 390   const FriBidiCharType *bidi_types,
 391   const FriBidiStrIndex len
 392 )
 393 {
 394   register FriBidiStrIndex i;
 395
 396   fribidi_assert (bidi_types);
 397
 398   for (i = 0; i < len; i++)
 399     if (FRIBIDI_IS_LETTER (bidi_types[i]))
 400       return FRIBIDI_IS_RTL (bidi_types[i]) ? FRIBIDI_PAR_RTL :
 401         FRIBIDI_PAR_LTR;
 402
 403   return FRIBIDI_PAR_ON;
 404 }
 405
 406 /* Push a new entry to the pairing linked list */
 407 static FriBidiPairingNode * pairing_nodes_push(FriBidiPairingNode *nodes,
 408                                                FriBidiRun *open,
 409                                                FriBidiRun *close)
 410 {
 411   FriBidiPairingNode *node = fribidi_malloc(sizeof(FriBidiPairingNode));
 412   node->open = open;
 413   node->close = close;
 414   node->next = nodes;
 415   nodes = node;
 416   return nodes;
 417 }
 418
 419 /* Sort by merge sort */
 420 static void pairing_nodes_front_back_split(FriBidiPairingNode *source,
 421                                            /* output */
 422                                            FriBidiPairingNode **front,
 423                                            FriBidiPairingNode **back)
 424 {
 425   FriBidiPairingNode *pfast, *pslow;
 426   if (!source || !source->next)
 427     {
 428       *front = source;
 429       *back = NULL;
 430     }
 431   else
 432     {
 433       pslow = source;
 434       pfast = source->next;
 435       while (pfast)
 436         {
 437           pfast= pfast->next;
 438           if (pfast)
 439             {
 440               pfast = pfast->next;
 441               pslow = pslow->next;
 442             }
 443         }
 444       *front = source;
 445       *back = pslow->next;
 446       pslow->next = NULL;
 447     }
 448 }
 449
 450 static FriBidiPairingNode *
 451 pairing_nodes_sorted_merge(FriBidiPairingNode *nodes1,
 452                            FriBidiPairingNode *nodes2)
 453 {
 454   FriBidiPairingNode *res = NULL;
 455   if (!nodes1)
 456     return nodes2;
 457   if (!nodes2)
 458     return nodes1;
 459
 460   if (nodes1->open->pos < nodes2->open->pos)
 461     {
 462       res = nodes1;
 463       res->next = pairing_nodes_sorted_merge(nodes1->next, nodes2);
 464     }
 465   else
 466     {
 467       res = nodes2;
 468       res->next = pairing_nodes_sorted_merge(nodes1, nodes2->next);
 469     }
 470   return res;
 471 }
 472
 473 static void sort_pairing_nodes(FriBidiPairingNode **nodes)
 474 {
 475   FriBidiPairingNode *front, *back;
 476
 477   /* 0 or 1 node case */
 478   if (!*nodes || !(*nodes)->next)
 479     return;
 480
 481   pairing_nodes_front_back_split(*nodes, &front, &back);
 482   sort_pairing_nodes(&front);
 483   sort_pairing_nodes(&back);
 484   *nodes = pairing_nodes_sorted_merge(front, back);
 485 }
 486
 487 static void free_pairing_nodes(FriBidiPairingNode *nodes)
 488 {
 489   while (nodes)
 490     {
 491       FriBidiPairingNode *p = nodes;
 492       nodes = nodes->next;
 493       fribidi_free(p);
 494     }
 495 }
 496
 497 FRIBIDI_ENTRY FriBidiLevel
 498 fribidi_get_par_embedding_levels_ex (
 499   /* input */
 500   const FriBidiCharType *bidi_types,
 501   const FriBidiBracketType *bracket_types,
 502   const FriBidiStrIndex len,
 503   /* input and output */
 504   FriBidiParType *pbase_dir,
 505   /* output */
 506   FriBidiLevel *embedding_levels
 507 )
 508 {
 509   FriBidiLevel base_level_per_iso_level[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
 510   FriBidiLevel base_level, max_level = 0;
 511   FriBidiParType base_dir;
 512   FriBidiRun *main_run_list = NULL, *explicits_list = NULL, *pp;
 513   fribidi_boolean status = false;
 514   int max_iso_level = 0;
 515
 516   if UNLIKELY
 517     (!len)
 518     {
 519       status = true;
 520       goto out;
 521     }
 522
 523   DBG ("in fribidi_get_par_embedding_levels");
 524
 525   fribidi_assert (bidi_types);
 526   fribidi_assert (pbase_dir);
 527   fribidi_assert (embedding_levels);
 528
 529   /* Determinate character types */
 530   {
 531     /* Get run-length encoded character types */
 532     main_run_list = run_list_encode_bidi_types (bidi_types, bracket_types, len);
 533     if UNLIKELY
 534       (!main_run_list) goto out;
 535   }
 536
 537   /* Find base level */
 538   /* If no strong base_dir was found, resort to the weak direction
 539      that was passed on input. */
 540   base_level = FRIBIDI_DIR_TO_LEVEL (*pbase_dir);
 541   if (!FRIBIDI_IS_STRONG (*pbase_dir))
 542     /* P2. P3. Search for first strong character and use its direction as
 543        base direction */
 544     {
 545       int valid_isolate_count = 0;
 546       for_run_list (pp, main_run_list)
 547         {
 548           if (RL_TYPE(pp) == FRIBIDI_TYPE_PDI)
 549             {
 550               /* Ignore if there is no matching isolate */
 551               if (valid_isolate_count>0)
 552                 valid_isolate_count--;
 553             }
 554           else if (FRIBIDI_IS_ISOLATE(RL_TYPE(pp)))
 555             valid_isolate_count++;
 556           else if (valid_isolate_count==0 && FRIBIDI_IS_LETTER (RL_TYPE (pp)))
 557             {
 558               base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (pp));
 559               *pbase_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 560               break;
 561             }
 562         }
 563     }
 564   base_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 565   DBG2 ("  base level : %c", fribidi_char_from_level (base_level));
 566   DBG2 ("  base dir   : %s", fribidi_get_bidi_type_name (base_dir));
 567
 568   base_level_per_iso_level[0] = base_level;
 569
 570 # if DEBUG
 571   if UNLIKELY
 572     (fribidi_debug_status ())
 573     {
 574       print_types_re (main_run_list);
 575     }
 576 # endif /* DEBUG */
 577
 578   /* Explicit Levels and Directions */
 579   DBG ("explicit levels and directions");
 580   {
 581     FriBidiLevel level, new_level = 0;
 582     int isolate_level = 0;
 583     FriBidiCharType override, new_override;
 584     FriBidiStrIndex i;
 585     int stack_size, over_pushed, first_interval;
 586     int valid_isolate_count = 0;
 587     int isolate_overflow = 0;
 588     int isolate = 0; /* The isolate status flag */
 589     struct
 590     {
 591       FriBidiCharType override; /* only LTR, RTL and ON are valid */
 592       FriBidiLevel level;
 593       int isolate;
 594       int isolate_level;
 595     } status_stack[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
 596     FriBidiRun temp_link;
 597     FriBidiRun *run_per_isolate_level[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
 598
 599     memset(run_per_isolate_level, 0, sizeof(run_per_isolate_level[0])
 600            * FRIBIDI_BIDI_MAX_RESOLVED_LEVELS);
 601
 602 /* explicits_list is a list like main_run_list, that holds the explicit
 603    codes that are removed from main_run_list, to reinsert them later by
 604    calling the shadow_run_list.
 605 */
 606     explicits_list = new_run_list ();
 607     if UNLIKELY
 608       (!explicits_list) goto out;
 609
 610     /* X1. Begin by setting the current embedding level to the paragraph
 611        embedding level. Set the directional override status to neutral,
 612        and directional isolate status to false.
 613
 614        Process each character iteratively, applying rules X2 through X8.
 615        Only embedding levels from 0 to 123 are valid in this phase. */
 616
 617     level = base_level;
 618     override = FRIBIDI_TYPE_ON;
 619     /* stack */
 620     stack_size = 0;
 621     over_pushed = 0;
 622     first_interval = 0;
 623     valid_isolate_count = 0;
 624     isolate_overflow = 0;
 625
 626     for_run_list (pp, main_run_list)
 627     {
 628       FriBidiCharType this_type = RL_TYPE (pp);
 629       RL_ISOLATE_LEVEL (pp) = isolate_level;
 630
 631       if (FRIBIDI_IS_EXPLICIT_OR_BN (this_type))
 632         {
 633           if (FRIBIDI_IS_STRONG (this_type))
 634             {                   /* LRE, RLE, LRO, RLO */
 635               /* 1. Explicit Embeddings */
 636               /*   X2. With each RLE, compute the least greater odd
 637                  embedding level. */
 638               /*   X3. With each LRE, compute the least greater even
 639                  embedding level. */
 640               /* 2. Explicit Overrides */
 641               /*   X4. With each RLO, compute the least greater odd
 642                  embedding level. */
 643               /*   X5. With each LRO, compute the least greater even
 644                  embedding level. */
 645               new_override = FRIBIDI_EXPLICIT_TO_OVERRIDE_DIR (this_type);
 646               for (i = RL_LEN (pp); i; i--)
 647                 {
 648                   new_level =
 649                     ((level + FRIBIDI_DIR_TO_LEVEL (this_type) + 2) & ~1) -
 650                     FRIBIDI_DIR_TO_LEVEL (this_type);
 651                   isolate = 0;
 652                   PUSH_STATUS;
 653                 }
 654             }
 655           else if (this_type == FRIBIDI_TYPE_PDF)
 656             {
 657               /* 3. Terminating Embeddings and overrides */
 658               /*   X7. With each PDF, determine the matching embedding or
 659                  override code. */
 660               for (i = RL_LEN (pp); i; i--)
 661                 {
 662                   if (stack_size && status_stack[stack_size-1].isolate != 0)
 663                     break;
 664                   POP_STATUS;
 665                 }
 666             }
 667
 668           /* X9. Remove all RLE, LRE, RLO, LRO, PDF, and BN codes. */
 669           /* Remove element and add it to explicits_list */
 670           RL_LEVEL (pp) = FRIBIDI_SENTINEL;
 671           temp_link.next = pp->next;
 672           move_node_before (pp, explicits_list);
 673           pp = &temp_link;
 674         }
 675       else if (this_type == FRIBIDI_TYPE_PDI)
 676         /* X6a. pop the direction of the stack */
 677         {
 678           for (i = RL_LEN (pp); i; i--)
 679             {
 680               if (isolate_overflow > 0)
 681                 {
 682                   isolate_overflow--;
 683                   RL_LEVEL (pp) = level;
 684                 }
 685
 686               else if (valid_isolate_count > 0)
 687                 {
 688                   /* Pop away all LRE,RLE,LRO, RLO levels
 689                      from the stack, as these are implicitly
 690                      terminated by the PDI */
 691                   while (stack_size && !status_stack[stack_size-1].isolate)
 692                     POP_STATUS;
 693                   over_pushed = 0; /* The PDI resets the overpushed! */
 694                   POP_STATUS;
 695                   isolate_level-- ;
 696                   valid_isolate_count--;
 697                   RL_LEVEL (pp) = level;
 698                   RL_ISOLATE_LEVEL (pp) = isolate_level;
 699                 }
 700               else
 701                 {
 702                   /* Ignore isolated PDI's by turning them into ON's */
 703                   RL_TYPE (pp) = FRIBIDI_TYPE_ON;
 704                   RL_LEVEL (pp) = level;
 705                 }
 706             }
 707         }
 708       else if (FRIBIDI_IS_ISOLATE(this_type))
 709         {
 710           /* TBD support RL_LEN > 1 */
 711           new_override = FRIBIDI_TYPE_ON;
 712           isolate = 1;
 713           if (this_type == FRIBIDI_TYPE_LRI)
 714             new_level = level + 2 - (level%2);
 715           else if (this_type == FRIBIDI_TYPE_RLI)
 716             new_level = level + 1 + (level%2);
 717           else if (this_type == FRIBIDI_TYPE_FSI)
 718             {
 719               /* Search for a local strong character until we
 720                  meet the corresponding PDI or the end of the
 721                  paragraph */
 722               FriBidiRun *fsi_pp;
 723               int isolate_count = 0;
 724               int fsi_base_level = 0;
 725               for_run_list (fsi_pp, pp)
 726                 {
 727                   if (RL_TYPE(fsi_pp) == FRIBIDI_TYPE_PDI)
 728                     {
 729                       isolate_count--;
 730                       if (valid_isolate_count < 0)
 731                         break;
 732                     }
 733                   else if (FRIBIDI_IS_ISOLATE(RL_TYPE(fsi_pp)))
 734                     isolate_count++;
 735                   else if (isolate_count==0 && FRIBIDI_IS_LETTER (RL_TYPE (fsi_pp)))
 736                     {
 737                       fsi_base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (fsi_pp));
 738                       break;
 739                     }
 740                 }
 741
 742               /* Same behavior like RLI and LRI above */
 743               if (FRIBIDI_LEVEL_IS_RTL (fsi_base_level))
 744                 new_level = level + 1 + (level%2);
 745               else
 746                 new_level = level + 2 - (level%2);
 747             }
 748
 749           RL_LEVEL (pp) = level;
 750           RL_ISOLATE_LEVEL (pp) = isolate_level++;
 751           base_level_per_iso_level[isolate_level] = new_level;
 752
 753           if (!FRIBIDI_IS_NEUTRAL (override))
 754             RL_TYPE (pp) = override;
 755
 756           if (new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL)
 757             {
 758               valid_isolate_count++;
 759               PUSH_STATUS;
 760               level = new_level;
 761             }
 762           else
 763             isolate_overflow += 1;
 764         }
 765       else if (this_type == FRIBIDI_TYPE_BS)
 766         {
 767           /* X8. All explicit directional embeddings and overrides are
 768              completely terminated at the end of each paragraph. Paragraph
 769              separators are not included in the embedding. */
 770           break;
 771         }
 772       else
 773         {
 774           /* X6. For all types besides RLE, LRE, RLO, LRO, and PDF:
 775              a. Set the level of the current character to the current
 776              embedding level.
 777              b. Whenever the directional override status is not neutral,
 778              reset the current character type to the directional override
 779              status. */
 780           RL_LEVEL (pp) = level;
 781           if (!FRIBIDI_IS_NEUTRAL (override))
 782             RL_TYPE (pp) = override;
 783         }
 784     }
 785
 786     /* Build the isolate_level connections */
 787     for_run_list (pp, main_run_list)
 788     {
 789       int isolate_level = RL_ISOLATE_LEVEL (pp);
 790       if (run_per_isolate_level[isolate_level])
 791         {
 792           run_per_isolate_level[isolate_level]->next_isolate = pp;
 793           pp->prev_isolate = run_per_isolate_level[isolate_level];
 794         }
 795       run_per_isolate_level[isolate_level] = pp;
 796     }
 797
 798     /* Implementing X8. It has no effect on a single paragraph! */
 799     level = base_level;
 800     override = FRIBIDI_TYPE_ON;
 801     stack_size = 0;
 802     over_pushed = 0;
 803   }
 804   /* X10. The remaining rules are applied to each run of characters at the
 805      same level. For each run, determine the start-of-level-run (sor) and
 806      end-of-level-run (eor) type, either L or R. This depends on the
 807      higher of the two levels on either side of the boundary (at the start
 808      or end of the paragraph, the level of the 'other' run is the base
 809      embedding level). If the higher level is odd, the type is R, otherwise
 810      it is L. */
 811   /* Resolving Implicit Levels can be done out of X10 loop, so only change
 812      of Resolving Weak Types and Resolving Neutral Types is needed. */
 813
 814   compact_list (main_run_list);
 815
 816 # if DEBUG
 817   if UNLIKELY
 818     (fribidi_debug_status ())
 819     {
 820       print_types_re (main_run_list);
 821       print_bidi_string (bidi_types, len);
 822       print_resolved_levels (main_run_list);
 823       print_resolved_types (main_run_list);
 824     }
 825 # endif /* DEBUG */
 826
 827   /* 4. Resolving weak types. Also calculate the maximum isolate level */
 828   max_iso_level = 0;
 829   DBG ("resolving weak types");
 830   {
 831     int last_strong_stack[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
 832     FriBidiCharType prev_type_orig;
 833     fribidi_boolean w4;
 834
 835     last_strong_stack[0] = base_dir;
 836
 837     for_run_list (pp, main_run_list)
 838     {
 839       register FriBidiCharType prev_type, this_type, next_type;
 840       FriBidiRun *ppp_prev, *ppp_next;
 841       int iso_level;
 842
 843       ppp_prev = get_adjacent_run(pp, false, false);
 844       ppp_next = get_adjacent_run(pp, true, false);
 845
 846       this_type = RL_TYPE (pp);
 847       iso_level = RL_ISOLATE_LEVEL(pp);
 848
 849       if (iso_level > max_iso_level)
 850         max_iso_level = iso_level;
 851
 852       if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
 853         prev_type = RL_TYPE(ppp_prev);
 854       else
 855         prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
 856
 857       if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
 858         next_type = RL_TYPE(ppp_next);
 859       else
 860         next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
 861
 862       if (FRIBIDI_IS_STRONG (prev_type))
 863         last_strong_stack[iso_level] = prev_type;
 864
 865       /* W1. NSM
 866          Examine each non-spacing mark (NSM) in the level run, and change the
 867          type of the NSM to the type of the previous character. If the NSM
 868          is at the start of the level run, it will get the type of sor. */
 869       /* Implementation note: it is important that if the previous character
 870          is not sor, then we should merge this run with the previous,
 871          because of rules like W5, that we assume all of a sequence of
 872          adjacent ETs are in one FriBidiRun. */
 873       if (this_type == FRIBIDI_TYPE_NSM)
 874         {
 875           /* New rule in Unicode 6.3 */
 876           if (FRIBIDI_IS_ISOLATE (RL_TYPE (pp->prev)))
 877               RL_TYPE(pp) = FRIBIDI_TYPE_ON;
 878
 879           if (RL_LEVEL (ppp_prev) == RL_LEVEL (pp))
 880             {
 881               if (ppp_prev == pp->prev)
 882                 pp = merge_with_prev (pp);
 883             }
 884           else
 885             RL_TYPE (pp) = prev_type;
 886
 887           if (prev_type == next_type && RL_LEVEL (pp) == RL_LEVEL (pp->next))
 888             {
 889               if (ppp_next == pp->next)
 890                 pp = merge_with_prev (pp->next);
 891             }
 892           continue;             /* As we know the next condition cannot be true. */
 893         }
 894
 895       /* W2: European numbers. */
 896       if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_AL)
 897         {
 898           RL_TYPE (pp) = FRIBIDI_TYPE_AN;
 899
 900           /* Resolving dependency of loops for rules W1 and W2, so we
 901              can merge them in one loop. */
 902           if (next_type == FRIBIDI_TYPE_NSM)
 903             RL_TYPE (ppp_next) = FRIBIDI_TYPE_AN;
 904         }
 905     }
 906
 907
 908     last_strong_stack[0] = base_dir;
 909
 910     /* Resolving dependency of loops for rules W4 and W5, W5 may
 911        want to prevent W4 to take effect in the next turn, do this
 912        through "w4". */
 913     w4 = true;
 914     /* Resolving dependency of loops for rules W4 and W5 with W7,
 915        W7 may change an EN to L but it sets the prev_type_orig if needed,
 916        so W4 and W5 in next turn can still do their works. */
 917     prev_type_orig = FRIBIDI_TYPE_ON;
 918
 919     /* Each isolate level has its own memory of the last strong character */
 920     for_run_list (pp, main_run_list)
 921     {
 922       register FriBidiCharType prev_type, this_type, next_type;
 923       int iso_level;
 924       FriBidiRun *ppp_prev, *ppp_next;
 925
 926       this_type = RL_TYPE (pp);
 927       iso_level = RL_ISOLATE_LEVEL(pp);
 928
 929       ppp_prev = get_adjacent_run(pp, false, false);
 930       ppp_next = get_adjacent_run(pp, true, false);
 931
 932       if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
 933         prev_type = RL_TYPE(ppp_prev);
 934       else
 935         prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
 936
 937       if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
 938         next_type = RL_TYPE(ppp_next);
 939       else
 940         next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
 941
 942       if (FRIBIDI_IS_STRONG (prev_type))
 943         last_strong_stack[iso_level] = prev_type;
 944
 945       /* W2 ??? */
 946
 947       /* W3: Change ALs to R. */
 948       if (this_type == FRIBIDI_TYPE_AL)
 949         {
 950           RL_TYPE (pp) = FRIBIDI_TYPE_RTL;
 951           w4 = true;
 952           prev_type_orig = FRIBIDI_TYPE_ON;
 953           continue;
 954         }
 955
 956       /* W4. A single european separator changes to a european number.
 957          A single common separator between two numbers of the same type
 958          changes to that type. */
 959       if (w4
 960           && RL_LEN (pp) == 1 && FRIBIDI_IS_ES_OR_CS (this_type)
 961           && FRIBIDI_IS_NUMBER (prev_type_orig)
 962           && prev_type_orig == next_type
 963           && (prev_type_orig == FRIBIDI_TYPE_EN
 964               || this_type == FRIBIDI_TYPE_CS))
 965         {
 966           RL_TYPE (pp) = prev_type;
 967           this_type = RL_TYPE (pp);
 968         }
 969       w4 = true;
 970
 971       /* W5. A sequence of European terminators adjacent to European
 972          numbers changes to All European numbers. */
 973       if (this_type == FRIBIDI_TYPE_ET
 974           && (prev_type_orig == FRIBIDI_TYPE_EN
 975               || next_type == FRIBIDI_TYPE_EN))
 976         {
 977           RL_TYPE (pp) = FRIBIDI_TYPE_EN;
 978           w4 = false;
 979           this_type = RL_TYPE (pp);
 980         }
 981
 982       /* W6. Otherwise change separators and terminators to other neutral. */
 983       if (FRIBIDI_IS_NUMBER_SEPARATOR_OR_TERMINATOR (this_type))
 984         RL_TYPE (pp) = FRIBIDI_TYPE_ON;
 985
 986       /* W7. Change european numbers to L. */
 987       if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_LTR)
 988         {
 989           RL_TYPE (pp) = FRIBIDI_TYPE_LTR;
 990           prev_type_orig = (RL_LEVEL (pp) == RL_LEVEL (pp->next) ?
 991                             FRIBIDI_TYPE_EN : FRIBIDI_TYPE_ON);
 992         }
 993       else
 994         prev_type_orig = PREV_TYPE_OR_SOR (pp->next);
 995     }
 996   }
 997
 998   compact_neutrals (main_run_list);
 999
1000 # if DEBUG
1001   if UNLIKELY
1002     (fribidi_debug_status ())
1003     {
1004       print_resolved_levels (main_run_list);
1005       print_resolved_types (main_run_list);
1006     }
1007 # endif /* DEBUG */
1008
1009   /* 5. Resolving Neutral Types */
1010
1011   DBG ("resolving neutral types - N0");
1012   {
1013     /*  BD16 - Build list of all pairs*/
1014     int num_iso_levels = max_iso_level + 1;
1015     FriBidiPairingNode *pairing_nodes = NULL;
1016     FriBidiRun *local_bracket_stack[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL][LOCAL_BRACKET_SIZE];
1017     FriBidiRun **bracket_stack[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
1018     int bracket_stack_size[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
1019     int last_level = RL_LEVEL(main_run_list);
1020     int last_iso_level = 0;
1021
1022     memset(bracket_stack, 0, sizeof(bracket_stack[0])*num_iso_levels);
1023     memset(bracket_stack_size, 0, sizeof(bracket_stack_size[0])*num_iso_levels);
1024
1025     /* populate the bracket_size. The first LOCAL_BRACKET_SIZE entries
1026        of the stack are one the stack. Allocate the rest of the entries.
1027      */
1028     {
1029       int iso_level;
1030       for (iso_level=0; iso_level < LOCAL_BRACKET_SIZE; iso_level++)
1031         bracket_stack[iso_level] = local_bracket_stack[iso_level];
1032
1033       for (iso_level=LOCAL_BRACKET_SIZE; iso_level < num_iso_levels; iso_level++)
1034         bracket_stack[iso_level] = fribidi_malloc (sizeof (bracket_stack[0])
1035                                                        * FRIBIDI_BIDI_MAX_NESTED_BRACKET_PAIRS);
1036     }
1037
1038     /* Build the bd16 pair stack. */
1039     for_run_list (pp, main_run_list)
1040       {
1041         int level = RL_LEVEL(pp);
1042         int iso_level = RL_ISOLATE_LEVEL(pp);
1043         FriBidiBracketType brack_prop = RL_BRACKET_TYPE(pp);
1044
1045         /* Interpret the isolating run sequence as such that they
1046            end at a change in the level, unless the iso_level has been
1047            raised. */
1048         if (level != last_level && last_iso_level == iso_level)
1049           bracket_stack_size[last_iso_level] = 0;
1050
1051         if (brack_prop!= FRIBIDI_NO_BRACKET
1052             && RL_TYPE(pp)==FRIBIDI_TYPE_ON)
1053           {
1054             if (FRIBIDI_IS_BRACKET_OPEN(brack_prop))
1055               {
1056                 if (bracket_stack_size[iso_level]==FRIBIDI_BIDI_MAX_NESTED_BRACKET_PAIRS)
1057                   break;
1058
1059                 /* push onto the pair stack */
1060                 bracket_stack[iso_level][bracket_stack_size[iso_level]++] = pp;
1061               }
1062             else
1063               {
1064                 int stack_idx = bracket_stack_size[iso_level] - 1;
1065                 while (stack_idx >= 0)
1066                   {
1067                     FriBidiBracketType se_brack_prop = RL_BRACKET_TYPE(bracket_stack[iso_level][stack_idx]);
1068                     if (FRIBIDI_BRACKET_ID(se_brack_prop) == FRIBIDI_BRACKET_ID(brack_prop))
1069                       {
1070                         bracket_stack_size[iso_level] = stack_idx;
1071
1072                         pairing_nodes = pairing_nodes_push(pairing_nodes,
1073                                                            bracket_stack[iso_level][stack_idx],
1074                                                            pp);
1075                         break;
1076                     }
1077                     stack_idx--;
1078                   }
1079               }
1080           }
1081         last_level = level;
1082         last_iso_level = iso_level;
1083       }
1084
1085     /* The list must now be sorted for the next algo to work! */
1086     sort_pairing_nodes(&pairing_nodes);
1087
1088 # if DEBUG
1089     if UNLIKELY
1090     (fribidi_debug_status ())
1091       {
1092         print_pairing_nodes (pairing_nodes);
1093       }
1094 # endif /* DEBUG */
1095
1096     /* Start the N0 */
1097     {
1098       FriBidiPairingNode *ppairs = pairing_nodes;
1099       while (ppairs)
1100         {
1101           int iso_level = ppairs->open->isolate_level;
1102           int embedding_level = base_level_per_iso_level[iso_level];
1103
1104           /* Find matching strong. */
1105           fribidi_boolean found = false;
1106           FriBidiRun *ppn;
1107           for (ppn = ppairs->open; ppn!= ppairs->close; ppn = ppn->next)
1108             {
1109               FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1110
1111               /* Calculate level like in resolve implicit levels below to prevent
1112                  embedded levels not to match the base_level */
1113               int this_level = RL_LEVEL (ppn) +
1114                 (FRIBIDI_LEVEL_IS_RTL (RL_LEVEL(ppn)) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1115
1116               /* N0b */
1117               if (FRIBIDI_IS_STRONG (this_type) && this_level == embedding_level)
1118                 {
1119                   RL_TYPE(ppairs->open) = RL_TYPE(ppairs->close) = this_level%2 ? FRIBIDI_TYPE_RTL : FRIBIDI_TYPE_LTR;
1120                   found = true;
1121                   break;
1122                 }
1123             }
1124
1125           /* N0c */
1126           /* Search for any strong type preceding and within the bracket pair */
1127           if (!found)
1128             {
1129               /* Search for a preceding strong */
1130               int prec_strong_level = embedding_level; /* TBDov! Extract from Isolate level in effect */
1131               int iso_level = RL_ISOLATE_LEVEL(ppairs->open);
1132               for (ppn = ppairs->open->prev; ppn->type != FRIBIDI_TYPE_SENTINEL; ppn=ppn->prev)
1133                 {
1134                   FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1135                   if (FRIBIDI_IS_STRONG (this_type) && RL_ISOLATE_LEVEL(ppn) == iso_level)
1136                     {
1137                       prec_strong_level = RL_LEVEL (ppn) +
1138                         (FRIBIDI_LEVEL_IS_RTL (RL_LEVEL(ppn)) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1139
1140                       break;
1141                     }
1142                 }
1143
1144               for (ppn = ppairs->open; ppn!= ppairs->close; ppn = ppn->next)
1145                 {
1146                   FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1147                   if (FRIBIDI_IS_STRONG (this_type) && RL_ISOLATE_LEVEL(ppn) == iso_level)
1148                     {
1149                       /* By constraint this is opposite the embedding direction,
1150                          since we did not match the N0b rule. We must now
1151                          compare with the preceding strong to establish whether
1152                          to apply N0c1 (opposite) or N0c2 embedding */
1153                       RL_TYPE(ppairs->open) = RL_TYPE(ppairs->close) = prec_strong_level % 2 ? FRIBIDI_TYPE_RTL : FRIBIDI_TYPE_LTR;
1154                       RL_LEVEL(ppairs->open) = RL_LEVEL(ppairs->close) = prec_strong_level;
1155                       found = true;
1156                       break;
1157                     }
1158                 }
1159             }
1160
1161           ppairs = ppairs->next;
1162         }
1163
1164       free_pairing_nodes(pairing_nodes);
1165
1166       if (num_iso_levels >= LOCAL_BRACKET_SIZE)
1167         {
1168           int i;
1169           /* Only need to free the non static members */
1170           for (i=LOCAL_BRACKET_SIZE; i<num_iso_levels; i++)
1171             fribidi_free(bracket_stack[i]);
1172         }
1173
1174       /* Remove the bracket property and re-compact */
1175       {
1176         const FriBidiBracketType NoBracket = FRIBIDI_NO_BRACKET;
1177         for_run_list (pp, main_run_list)
1178           pp->bracket_type = NoBracket;
1179         compact_neutrals (main_run_list);
1180       }
1181     }
1182
1183 # if DEBUG
1184   if UNLIKELY
1185     (fribidi_debug_status ())
1186     {
1187       print_resolved_levels (main_run_list);
1188       print_resolved_types (main_run_list);
1189     }
1190 # endif /* DEBUG */
1191   }
1192
1193   DBG ("resolving neutral types - N1+N2");
1194   {
1195     for_run_list (pp, main_run_list)
1196     {
1197       FriBidiCharType prev_type, this_type, next_type;
1198       FriBidiRun *ppp_prev, *ppp_next;
1199
1200       ppp_prev = get_adjacent_run(pp, false, false);
1201       ppp_next = get_adjacent_run(pp, true, false);
1202
1203       /* "European and Arabic numbers are treated as though they were R"
1204          FRIBIDI_CHANGE_NUMBER_TO_RTL does this. */
1205       this_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE (pp));
1206
1207       if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
1208         prev_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_prev));
1209       else
1210         prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
1211
1212       if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
1213         next_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_next));
1214       else
1215         next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
1216
1217       if (FRIBIDI_IS_NEUTRAL (this_type))
1218         RL_TYPE (pp) = (prev_type == next_type) ?
1219           /* N1. */ prev_type :
1220           /* N2. */ FRIBIDI_EMBEDDING_DIRECTION (pp);
1221     }
1222   }
1223
1224   compact_list (main_run_list);
1225
1226 # if DEBUG
1227   if UNLIKELY
1228     (fribidi_debug_status ())
1229     {
1230       print_resolved_levels (main_run_list);
1231       print_resolved_types (main_run_list);
1232     }
1233 # endif /* DEBUG */
1234
1235   /* 6. Resolving implicit levels */
1236   DBG ("resolving implicit levels");
1237   {
1238     max_level = base_level;
1239
1240     for_run_list (pp, main_run_list)
1241     {
1242       FriBidiCharType this_type;
1243       int level;
1244
1245       this_type = RL_TYPE (pp);
1246       level = RL_LEVEL (pp);
1247
1248       /* I1. Even */
1249       /* I2. Odd */
1250       if (FRIBIDI_IS_NUMBER (this_type))
1251         RL_LEVEL (pp) = (level + 2) & ~1;
1252       else
1253         RL_LEVEL (pp) =
1254           level +
1255           (FRIBIDI_LEVEL_IS_RTL (level) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1256
1257       if (RL_LEVEL (pp) > max_level)
1258         max_level = RL_LEVEL (pp);
1259     }
1260   }
1261
1262   compact_list (main_run_list);
1263
1264 # if DEBUG
1265   if UNLIKELY
1266     (fribidi_debug_status ())
1267     {
1268       print_bidi_string (bidi_types, len);
1269       print_resolved_levels (main_run_list);
1270       print_resolved_types (main_run_list);
1271     }
1272 # endif /* DEBUG */
1273
1274 /* Reinsert the explicit codes & BN's that are already removed, from the
1275    explicits_list to main_run_list. */
1276   DBG ("reinserting explicit codes");
1277   if UNLIKELY
1278     (explicits_list->next != explicits_list)
1279     {
1280       register FriBidiRun *p;
1281       register fribidi_boolean stat =
1282         shadow_run_list (main_run_list, explicits_list, true);
1283       explicits_list = NULL;
1284       if UNLIKELY
1285         (!stat) goto out;
1286
1287       /* Set level of inserted explicit chars to that of their previous
1288        * char, such that they do not affect reordering. */
1289       p = main_run_list->next;
1290       if (p != main_run_list && p->level == FRIBIDI_SENTINEL)
1291         p->level = base_level;
1292       for_run_list (p, main_run_list) if (p->level == FRIBIDI_SENTINEL)
1293         p->level = p->prev->level;
1294     }
1295
1296 # if DEBUG
1297   if UNLIKELY
1298     (fribidi_debug_status ())
1299     {
1300       print_types_re (main_run_list);
1301       print_resolved_levels (main_run_list);
1302       print_resolved_types (main_run_list);
1303     }
1304 # endif /* DEBUG */
1305
1306   DBG ("reset the embedding levels, 1, 2, 3.");
1307   {
1308     register int j, state, pos;
1309     register FriBidiCharType char_type;
1310     register FriBidiRun *p, *q, *list;
1311
1312     /* L1. Reset the embedding levels of some chars:
1313        1. segment separators,
1314        2. paragraph separators,
1315        3. any sequence of whitespace characters preceding a segment
1316           separator or paragraph separator, and
1317        4. any sequence of whitespace characters and/or isolate formatting
1318           characters at the end of the line.
1319        ... (to be continued in fribidi_reorder_line()). */
1320     list = new_run_list ();
1321     if UNLIKELY
1322       (!list) goto out;
1323     q = list;
1324     state = 1;
1325     pos = len - 1;
1326     for (j = len - 1; j >= -1; j--)
1327       {
1328         /* close up the open link at the end */
1329         if (j >= 0)
1330           char_type = bidi_types[j];
1331         else
1332           char_type = FRIBIDI_TYPE_ON;
1333         if (!state && FRIBIDI_IS_SEPARATOR (char_type))
1334           {
1335             state = 1;
1336             pos = j;
1337           }
1338         else if (state &&
1339                  !(FRIBIDI_IS_EXPLICIT_OR_SEPARATOR_OR_BN_OR_WS(char_type)
1340                    || FRIBIDI_IS_ISOLATE(char_type)))
1341           {
1342             state = 0;
1343             p = new_run ();
1344             if UNLIKELY
1345               (!p)
1346               {
1347                 free_run_list (list);
1348                 goto out;
1349               }
1350             p->pos = j + 1;
1351             p->len = pos - j;
1352             p->type = base_dir;
1353             p->level = base_level;
1354             move_node_before (p, q);
1355             q = p;
1356           }
1357       }
1358     if UNLIKELY
1359       (!shadow_run_list (main_run_list, list, false)) goto out;
1360   }
1361
1362 # if DEBUG
1363   if UNLIKELY
1364     (fribidi_debug_status ())
1365     {
1366       print_types_re (main_run_list);
1367       print_resolved_levels (main_run_list);
1368       print_resolved_types (main_run_list);
1369     }
1370 # endif /* DEBUG */
1371
1372   {
1373     FriBidiStrIndex pos = 0;
1374     for_run_list (pp, main_run_list)
1375     {
1376       register FriBidiStrIndex l;
1377       register FriBidiLevel level = pp->level;
1378       for (l = pp->len; l; l--)
1379         embedding_levels[pos++] = level;
1380     }
1381   }
1382
1383   status = true;
1384
1385 out:
1386   DBG ("leaving fribidi_get_par_embedding_levels");
1387
1388   if (main_run_list)
1389     free_run_list (main_run_list);
1390   if UNLIKELY
1391     (explicits_list) free_run_list (explicits_list);
1392
1393   return status ? max_level + 1 : 0;
1394 }
1395
1396
1397 static void
1398 bidi_string_reverse (
1399   FriBidiChar *str,
1400   const FriBidiStrIndex len
1401 )
1402 {
1403   FriBidiStrIndex i;
1404
1405   fribidi_assert (str);
1406
1407   for (i = 0; i < len / 2; i++)
1408     {
1409       FriBidiChar tmp = str[i];
1410       str[i] = str[len - 1 - i];
1411       str[len - 1 - i] = tmp;
1412     }
1413 }
1414
1415 static void
1416 index_array_reverse (
1417   FriBidiStrIndex *arr,
1418   const FriBidiStrIndex len
1419 )
1420 {
1421   FriBidiStrIndex i;
1422
1423   fribidi_assert (arr);
1424
1425   for (i = 0; i < len / 2; i++)
1426     {
1427       FriBidiStrIndex tmp = arr[i];
1428       arr[i] = arr[len - 1 - i];
1429       arr[len - 1 - i] = tmp;
1430     }
1431 }
1432
1433
1434 FRIBIDI_ENTRY FriBidiLevel
1435 fribidi_reorder_line (
1436   /* input */
1437   FriBidiFlags flags, /* reorder flags */
1438   const FriBidiCharType *bidi_types,
1439   const FriBidiStrIndex len,
1440   const FriBidiStrIndex off,
1441   const FriBidiParType base_dir,
1442   /* input and output */
1443   FriBidiLevel *embedding_levels,
1444   FriBidiChar *visual_str,
1445   /* output */
1446   FriBidiStrIndex *map
1447 )
1448 {
1449   fribidi_boolean status = false;
1450   FriBidiLevel max_level = 0;
1451
1452   if UNLIKELY
1453     (len == 0)
1454     {
1455       status = true;
1456       goto out;
1457     }
1458
1459   DBG ("in fribidi_reorder_line");
1460
1461   fribidi_assert (bidi_types);
1462   fribidi_assert (embedding_levels);
1463
1464   DBG ("reset the embedding levels, 4. whitespace at the end of line");
1465   {
1466     register FriBidiStrIndex i;
1467
1468     /* L1. Reset the embedding levels of some chars:
1469        4. any sequence of white space characters at the end of the line. */
1470     for (i = off + len - 1; i >= off &&
1471          FRIBIDI_IS_EXPLICIT_OR_BN_OR_WS (bidi_types[i]); i--)
1472       embedding_levels[i] = FRIBIDI_DIR_TO_LEVEL (base_dir);
1473   }
1474
1475   /* 7. Reordering resolved levels */
1476   {
1477     register FriBidiLevel level;
1478     register FriBidiStrIndex i;
1479
1480     /* Reorder both the outstring and the order array */
1481     {
1482       if (FRIBIDI_TEST_BITS (flags, FRIBIDI_FLAG_REORDER_NSM))
1483         {
1484           /* L3. Reorder NSMs. */
1485           for (i = off + len - 1; i >= off; i--)
1486             if (FRIBIDI_LEVEL_IS_RTL (embedding_levels[i])
1487                 && bidi_types[i] == FRIBIDI_TYPE_NSM)
1488               {
1489                 register FriBidiStrIndex seq_end = i;
1490                 level = embedding_levels[i];
1491
1492                 for (i--; i >= off &&
1493                      FRIBIDI_IS_EXPLICIT_OR_BN_OR_NSM (bidi_types[i])
1494                      && embedding_levels[i] == level; i--)
1495                   ;
1496
1497                 if (i < off || embedding_levels[i] != level)
1498                   {
1499                     i++;
1500                     DBG ("warning: NSM(s) at the beginning of level run");
1501                   }
1502
1503                 if (visual_str)
1504                   {
1505                     bidi_string_reverse (visual_str + i, seq_end - i + 1);
1506                   }
1507                 if (map)
1508                   {
1509                     index_array_reverse (map + i, seq_end - i + 1);
1510                   }
1511               }
1512         }
1513
1514       /* Find max_level of the line.  We don't reuse the paragraph
1515        * max_level, both for a cleaner API, and that the line max_level
1516        * may be far less than paragraph max_level. */
1517       for (i = off + len - 1; i >= off; i--)
1518         if (embedding_levels[i] > max_level)
1519           max_level = embedding_levels[i];
1520
1521       /* L2. Reorder. */
1522       for (level = max_level; level > 0; level--)
1523         for (i = off + len - 1; i >= off; i--)
1524           if (embedding_levels[i] >= level)
1525             {
1526               /* Find all stretches that are >= level_idx */
1527               register FriBidiStrIndex seq_end = i;
1528               for (i--; i >= off && embedding_levels[i] >= level; i--)
1529                 ;
1530
1531               if (visual_str)
1532                 bidi_string_reverse (visual_str + i + 1, seq_end - i);
1533               if (map)
1534                 index_array_reverse (map + i + 1, seq_end - i);
1535             }
1536     }
1537
1538   }
1539
1540   status = true;
1541
1542 out:
1543
1544   return status ? max_level + 1 : 0;
1545 }
1546
1547 /* Editor directions:
1548  * vim:textwidth=78:tabstop=8:shiftwidth=2:autoindent:cindent
1549  */