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 popping 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, max_level = 0;
 510   FriBidiParType base_dir;
 511   FriBidiRun *main_run_list = NULL, *explicits_list = NULL, *pp;
 512   fribidi_boolean status = false;
 513   int max_iso_level = 0;
 514
 515   if UNLIKELY
 516     (!len)
 517     {
 518       status = true;
 519       goto out;
 520     }
 521
 522   DBG ("in fribidi_get_par_embedding_levels");
 523
 524   fribidi_assert (bidi_types);
 525   fribidi_assert (pbase_dir);
 526   fribidi_assert (embedding_levels);
 527
 528   /* Determinate character types */
 529   {
 530     /* Get run-length encoded character types */
 531     main_run_list = run_list_encode_bidi_types (bidi_types, bracket_types, len);
 532     if UNLIKELY
 533       (!main_run_list) goto out;
 534   }
 535
 536   /* Find base level */
 537   /* If no strong base_dir was found, resort to the weak direction
 538      that was passed on input. */
 539   base_level = FRIBIDI_DIR_TO_LEVEL (*pbase_dir);
 540   if (!FRIBIDI_IS_STRONG (*pbase_dir))
 541     /* P2. P3. Search for first strong character and use its direction as
 542        base direction */
 543     {
 544       int valid_isolate_count = 0;
 545       for_run_list (pp, main_run_list)
 546         {
 547           if (RL_TYPE(pp) == FRIBIDI_TYPE_PDI)
 548             {
 549               /* Ignore if there is no matching isolate */
 550               if (valid_isolate_count>0)
 551                 valid_isolate_count--;
 552             }
 553           else if (FRIBIDI_IS_ISOLATE(RL_TYPE(pp)))
 554             valid_isolate_count++;
 555           else if (valid_isolate_count==0 && FRIBIDI_IS_LETTER (RL_TYPE (pp)))
 556             {
 557               base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (pp));
 558               *pbase_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 559               break;
 560             }
 561         }
 562     }
 563   base_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 564   DBG2 ("  base level : %c", fribidi_char_from_level (base_level));
 565   DBG2 ("  base dir   : %s", fribidi_get_bidi_type_name (base_dir));
 566
 567 # if DEBUG
 568   if UNLIKELY
 569     (fribidi_debug_status ())
 570     {
 571       print_types_re (main_run_list);
 572     }
 573 # endif /* DEBUG */
 574
 575   /* Explicit Levels and Directions */
 576   DBG ("explicit levels and directions");
 577   {
 578     FriBidiLevel level, new_level = 0;
 579     int isolate_level = 0;
 580     FriBidiCharType override, new_override;
 581     FriBidiStrIndex i;
 582     int stack_size, over_pushed, first_interval;
 583     int valid_isolate_count = 0;
 584     int isolate_overflow = 0;
 585     int isolate = 0; /* The isolate status flag */
 586     struct
 587     {
 588       FriBidiCharType override; /* only LTR, RTL and ON are valid */
 589       FriBidiLevel level;
 590       int isolate;
 591       int isolate_level;
 592     } status_stack[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
 593     FriBidiRun temp_link;
 594     FriBidiRun *run_per_isolate_level[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
 595     int prev_isolate_level = 0; /* When running over the isolate levels, remember the previous level */
 596
 597     memset(run_per_isolate_level, 0, sizeof(run_per_isolate_level[0])
 598            * FRIBIDI_BIDI_MAX_RESOLVED_LEVELS);
 599
 600 /* explicits_list is a list like main_run_list, that holds the explicit
 601    codes that are removed from main_run_list, to reinsert them later by
 602    calling the shadow_run_list.
 603 */
 604     explicits_list = new_run_list ();
 605     if UNLIKELY
 606       (!explicits_list) goto out;
 607
 608     /* X1. Begin by setting the current embedding level to the paragraph
 609        embedding level. Set the directional override status to neutral,
 610        and directional isolate status to false.
 611
 612        Process each character iteratively, applying rules X2 through X8.
 613        Only embedding levels from 0 to 123 are valid in this phase. */
 614
 615     level = base_level;
 616     override = FRIBIDI_TYPE_ON;
 617     /* stack */
 618     stack_size = 0;
 619     over_pushed = 0;
 620     first_interval = 0;
 621     valid_isolate_count = 0;
 622     isolate_overflow = 0;
 623
 624     for_run_list (pp, main_run_list)
 625     {
 626       FriBidiCharType this_type = RL_TYPE (pp);
 627       RL_ISOLATE_LEVEL (pp) = isolate_level;
 628
 629       if (FRIBIDI_IS_EXPLICIT_OR_BN (this_type))
 630         {
 631           if (FRIBIDI_IS_STRONG (this_type))
 632             {                   /* LRE, RLE, LRO, RLO */
 633               /* 1. Explicit Embeddings */
 634               /*   X2. With each RLE, compute the least greater odd
 635                  embedding level. */
 636               /*   X3. With each LRE, compute the least greater even
 637                  embedding level. */
 638               /* 2. Explicit Overrides */
 639               /*   X4. With each RLO, compute the least greater odd
 640                  embedding level. */
 641               /*   X5. With each LRO, compute the least greater even
 642                  embedding level. */
 643               new_override = FRIBIDI_EXPLICIT_TO_OVERRIDE_DIR (this_type);
 644               for (i = RL_LEN (pp); i; i--)
 645                 {
 646                   new_level =
 647                     ((level + FRIBIDI_DIR_TO_LEVEL (this_type) + 2) & ~1) -
 648                     FRIBIDI_DIR_TO_LEVEL (this_type);
 649                   isolate = 0;
 650                   PUSH_STATUS;
 651                 }
 652             }
 653           else if (this_type == FRIBIDI_TYPE_PDF)
 654             {
 655               /* 3. Terminating Embeddings and overrides */
 656               /*   X7. With each PDF, determine the matching embedding or
 657                  override code. */
 658               for (i = RL_LEN (pp); i; i--)
 659                 {
 660                   if (stack_size && status_stack[stack_size-1].isolate != 0)
 661                     break;
 662                   POP_STATUS;
 663                 }
 664             }
 665
 666           /* X9. Remove all RLE, LRE, RLO, LRO, PDF, and BN codes. */
 667           /* Remove element and add it to explicits_list */
 668           RL_LEVEL (pp) = FRIBIDI_SENTINEL;
 669           temp_link.next = pp->next;
 670           move_node_before (pp, explicits_list);
 671           pp = &temp_link;
 672         }
 673       else if (this_type == FRIBIDI_TYPE_PDI)
 674         /* X6a. pop the direction of the stack */
 675         {
 676           for (i = RL_LEN (pp); i; i--)
 677             {
 678               if (isolate_overflow > 0)
 679                 {
 680                   isolate_overflow--;
 681                   RL_LEVEL (pp) = level;
 682                 }
 683
 684               else if (valid_isolate_count > 0)
 685                 {
 686                   /* Pop away all LRE,RLE,LRO, RLO levels
 687                      from the stack, as these are implicitly
 688                      terminated by the PDI */
 689                   while (stack_size && !status_stack[stack_size-1].isolate)
 690                     POP_STATUS;
 691                   over_pushed = 0; /* The PDI resets the overpushed! */
 692                   POP_STATUS;
 693                   isolate_level-- ;
 694                   valid_isolate_count--;
 695                   RL_LEVEL (pp) = level;
 696                   RL_ISOLATE_LEVEL (pp) = isolate_level;
 697                 }
 698               else
 699                 {
 700                   /* Ignore isolated PDI's by turning them into ON's */
 701                   RL_TYPE (pp) = FRIBIDI_TYPE_ON;
 702                   RL_LEVEL (pp) = level;
 703                 }
 704             }
 705         }
 706       else if (FRIBIDI_IS_ISOLATE(this_type))
 707         {
 708           /* TBD support RL_LEN > 1 */
 709           new_override = FRIBIDI_TYPE_ON;
 710           isolate = 1;
 711           if (this_type == FRIBIDI_TYPE_LRI)
 712             new_level = level + 2 - (level%2);
 713           else if (this_type == FRIBIDI_TYPE_RLI)
 714             new_level = level + 1 + (level%2);
 715           else if (this_type == FRIBIDI_TYPE_FSI)
 716             {
 717               /* Search for a local strong character until we
 718                  meet the corresponding PDI or the end of the
 719                  paragraph */
 720               FriBidiRun *fsi_pp;
 721               int isolate_count = 0;
 722               int fsi_base_level = 0;
 723               for_run_list (fsi_pp, pp)
 724                 {
 725                   if (RL_TYPE(fsi_pp) == FRIBIDI_TYPE_PDI)
 726                     {
 727                       isolate_count--;
 728                       if (valid_isolate_count < 0)
 729                         break;
 730                     }
 731                   else if (FRIBIDI_IS_ISOLATE(RL_TYPE(fsi_pp)))
 732                     isolate_count++;
 733                   else if (isolate_count==0 && FRIBIDI_IS_LETTER (RL_TYPE (fsi_pp)))
 734                     {
 735                       fsi_base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (fsi_pp));
 736                       break;
 737                     }
 738                 }
 739
 740               /* Same behavior like RLI and LRI above */
 741               if (FRIBIDI_LEVEL_IS_RTL (fsi_base_level))
 742                 new_level = level + 1 + (level%2);
 743               else
 744                 new_level = level + 2 - (level%2);
 745             }
 746
 747           RL_LEVEL (pp) = level;
 748           RL_ISOLATE_LEVEL (pp) = isolate_level;
 749           if (isolate_level < FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL-1)
 750               isolate_level++;
 751
 752           if (!FRIBIDI_IS_NEUTRAL (override))
 753             RL_TYPE (pp) = override;
 754
 755           if (new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL)
 756             {
 757               valid_isolate_count++;
 758               PUSH_STATUS;
 759               level = new_level;
 760             }
 761           else
 762             isolate_overflow += 1;
 763         }
 764       else if (this_type == FRIBIDI_TYPE_BS)
 765         {
 766           /* X8. All explicit directional embeddings and overrides are
 767              completely terminated at the end of each paragraph. Paragraph
 768              separators are not included in the embedding. */
 769           break;
 770         }
 771       else
 772         {
 773           /* X6. For all types besides RLE, LRE, RLO, LRO, and PDF:
 774              a. Set the level of the current character to the current
 775              embedding level.
 776              b. Whenever the directional override status is not neutral,
 777              reset the current character type to the directional override
 778              status. */
 779           RL_LEVEL (pp) = level;
 780           if (!FRIBIDI_IS_NEUTRAL (override))
 781             RL_TYPE (pp) = override;
 782         }
 783     }
 784
 785     /* Build the isolate_level connections */
 786     prev_isolate_level = 0;
 787     for_run_list (pp, main_run_list)
 788     {
 789       int isolate_level = RL_ISOLATE_LEVEL (pp);
 790       int i;
 791
 792       /* When going from an upper to a lower level, zero out all higher levels
 793          in order not erroneous connections! */
 794       if (isolate_level<prev_isolate_level)
 795         for (i=isolate_level+1; i<=prev_isolate_level; i++)
 796           run_per_isolate_level[i]=0;
 797       prev_isolate_level = isolate_level;
 798
 799       if (run_per_isolate_level[isolate_level])
 800         {
 801           run_per_isolate_level[isolate_level]->next_isolate = pp;
 802           pp->prev_isolate = run_per_isolate_level[isolate_level];
 803         }
 804       run_per_isolate_level[isolate_level] = pp;
 805     }
 806
 807     /* Implementing X8. It has no effect on a single paragraph! */
 808     level = base_level;
 809     override = FRIBIDI_TYPE_ON;
 810     stack_size = 0;
 811     over_pushed = 0;
 812   }
 813   /* X10. The remaining rules are applied to each run of characters at the
 814      same level. For each run, determine the start-of-level-run (sor) and
 815      end-of-level-run (eor) type, either L or R. This depends on the
 816      higher of the two levels on either side of the boundary (at the start
 817      or end of the paragraph, the level of the 'other' run is the base
 818      embedding level). If the higher level is odd, the type is R, otherwise
 819      it is L. */
 820   /* Resolving Implicit Levels can be done out of X10 loop, so only change
 821      of Resolving Weak Types and Resolving Neutral Types is needed. */
 822
 823   compact_list (main_run_list);
 824
 825 # if DEBUG
 826   if UNLIKELY
 827     (fribidi_debug_status ())
 828     {
 829       print_types_re (main_run_list);
 830       print_bidi_string (bidi_types, len);
 831       print_resolved_levels (main_run_list);
 832       print_resolved_types (main_run_list);
 833     }
 834 # endif /* DEBUG */
 835
 836   /* 4. Resolving weak types. Also calculate the maximum isolate level */
 837   max_iso_level = 0;
 838   DBG ("4a. resolving weak types");
 839   {
 840     int last_strong_stack[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
 841     FriBidiCharType prev_type_orig;
 842     fribidi_boolean w4;
 843
 844     last_strong_stack[0] = base_dir;
 845
 846     for_run_list (pp, main_run_list)
 847     {
 848       register FriBidiCharType prev_type, this_type, next_type;
 849       FriBidiRun *ppp_prev, *ppp_next;
 850       int iso_level;
 851
 852       ppp_prev = get_adjacent_run(pp, false, false);
 853       ppp_next = get_adjacent_run(pp, true, false);
 854
 855       this_type = RL_TYPE (pp);
 856       iso_level = RL_ISOLATE_LEVEL(pp);
 857
 858       if (iso_level > max_iso_level)
 859         max_iso_level = iso_level;
 860
 861       if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
 862         prev_type = RL_TYPE(ppp_prev);
 863       else
 864         prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
 865
 866       if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
 867         next_type = RL_TYPE(ppp_next);
 868       else
 869         next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
 870
 871       if (FRIBIDI_IS_STRONG (prev_type))
 872         last_strong_stack[iso_level] = prev_type;
 873
 874       /* W1. NSM
 875          Examine each non-spacing mark (NSM) in the level run, and change the
 876          type of the NSM to the type of the previous character. If the NSM
 877          is at the start of the level run, it will get the type of sor. */
 878       /* Implementation note: it is important that if the previous character
 879          is not sor, then we should merge this run with the previous,
 880          because of rules like W5, that we assume all of a sequence of
 881          adjacent ETs are in one FriBidiRun. */
 882       if (this_type == FRIBIDI_TYPE_NSM)
 883         {
 884           /* New rule in Unicode 6.3 */
 885           if (FRIBIDI_IS_ISOLATE (RL_TYPE (pp->prev)))
 886               RL_TYPE(pp) = FRIBIDI_TYPE_ON;
 887
 888           if (RL_LEVEL (ppp_prev) == RL_LEVEL (pp))
 889             {
 890               if (ppp_prev == pp->prev)
 891                 pp = merge_with_prev (pp);
 892             }
 893           else
 894             RL_TYPE (pp) = prev_type;
 895
 896           if (prev_type == next_type && RL_LEVEL (pp) == RL_LEVEL (pp->next))
 897             {
 898               if (ppp_next == pp->next)
 899                 pp = merge_with_prev (pp->next);
 900             }
 901           continue;             /* As we know the next condition cannot be true. */
 902         }
 903
 904       /* W2: European numbers. */
 905       if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_AL)
 906         {
 907           RL_TYPE (pp) = FRIBIDI_TYPE_AN;
 908
 909           /* Resolving dependency of loops for rules W1 and W2, so we
 910              can merge them in one loop. */
 911           if (next_type == FRIBIDI_TYPE_NSM)
 912             RL_TYPE (ppp_next) = FRIBIDI_TYPE_AN;
 913         }
 914     }
 915
 916 # if DEBUG
 917   if UNLIKELY
 918     (fribidi_debug_status ())
 919     {
 920       print_resolved_levels (main_run_list);
 921       print_resolved_types (main_run_list);
 922     }
 923 # endif /* DEBUG */
 924
 925     /* The last iso level is used to invalidate the the last strong values when going from
 926        a higher to a lower iso level. When this occur, all "last_strong" values are
 927        set to the base_dir. */
 928     last_strong_stack[0] = base_dir;
 929
 930     DBG ("4b. resolving weak types. W4 and W5");
 931
 932     /* Resolving dependency of loops for rules W4 and W5, W5 may
 933        want to prevent W4 to take effect in the next turn, do this
 934        through "w4". */
 935     w4 = true;
 936     /* Resolving dependency of loops for rules W4 and W5 with W7,
 937        W7 may change an EN to L but it sets the prev_type_orig if needed,
 938        so W4 and W5 in next turn can still do their works. */
 939     prev_type_orig = FRIBIDI_TYPE_ON;
 940
 941     /* Each isolate level has its own memory of the last strong character */
 942     for_run_list (pp, main_run_list)
 943     {
 944       register FriBidiCharType prev_type, this_type, next_type;
 945       int iso_level;
 946       FriBidiRun *ppp_prev, *ppp_next;
 947
 948       this_type = RL_TYPE (pp);
 949       iso_level = RL_ISOLATE_LEVEL(pp);
 950
 951       ppp_prev = get_adjacent_run(pp, false, false);
 952       ppp_next = get_adjacent_run(pp, true, false);
 953
 954       if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
 955         prev_type = RL_TYPE(ppp_prev);
 956       else
 957         prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
 958
 959       if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
 960         next_type = RL_TYPE(ppp_next);
 961       else
 962         next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
 963
 964       if (FRIBIDI_IS_STRONG (prev_type))
 965         last_strong_stack[iso_level] = prev_type;
 966
 967       /* W2 ??? */
 968
 969       /* W3: Change ALs to R. */
 970       if (this_type == FRIBIDI_TYPE_AL)
 971         {
 972           RL_TYPE (pp) = FRIBIDI_TYPE_RTL;
 973           w4 = true;
 974           prev_type_orig = FRIBIDI_TYPE_ON;
 975           continue;
 976         }
 977
 978       /* W4. A single european separator changes to a european number.
 979          A single common separator between two numbers of the same type
 980          changes to that type. */
 981       if (w4
 982           && RL_LEN (pp) == 1 && FRIBIDI_IS_ES_OR_CS (this_type)
 983           && FRIBIDI_IS_NUMBER (prev_type_orig)
 984           && prev_type_orig == next_type
 985           && (prev_type_orig == FRIBIDI_TYPE_EN
 986               || this_type == FRIBIDI_TYPE_CS))
 987         {
 988           RL_TYPE (pp) = prev_type;
 989           this_type = RL_TYPE (pp);
 990         }
 991       w4 = true;
 992
 993       /* W5. A sequence of European terminators adjacent to European
 994          numbers changes to All European numbers. */
 995       if (this_type == FRIBIDI_TYPE_ET
 996           && (prev_type_orig == FRIBIDI_TYPE_EN
 997               || next_type == FRIBIDI_TYPE_EN))
 998         {
 999           RL_TYPE (pp) = FRIBIDI_TYPE_EN;
1000           w4 = false;
1001           this_type = RL_TYPE (pp);
1002         }
1003
1004       /* W6. Otherwise change separators and terminators to other neutral. */
1005       if (FRIBIDI_IS_NUMBER_SEPARATOR_OR_TERMINATOR (this_type))
1006         RL_TYPE (pp) = FRIBIDI_TYPE_ON;
1007
1008       /* W7. Change european numbers to L. */
1009       if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_LTR)
1010         {
1011           RL_TYPE (pp) = FRIBIDI_TYPE_LTR;
1012           prev_type_orig = (RL_LEVEL (pp) == RL_LEVEL (pp->next) ?
1013                             FRIBIDI_TYPE_EN : FRIBIDI_TYPE_ON);
1014         }
1015       else
1016         prev_type_orig = PREV_TYPE_OR_SOR (pp->next);
1017     }
1018   }
1019
1020   compact_neutrals (main_run_list);
1021
1022 # if DEBUG
1023   if UNLIKELY
1024     (fribidi_debug_status ())
1025     {
1026       print_resolved_levels (main_run_list);
1027       print_resolved_types (main_run_list);
1028     }
1029 # endif /* DEBUG */
1030
1031   /* 5. Resolving Neutral Types */
1032
1033   DBG ("5. resolving neutral types - N0");
1034   {
1035     /*  BD16 - Build list of all pairs*/
1036     int num_iso_levels = max_iso_level + 1;
1037     FriBidiPairingNode *pairing_nodes = NULL;
1038     FriBidiRun *local_bracket_stack[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL][LOCAL_BRACKET_SIZE];
1039     FriBidiRun **bracket_stack[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
1040     int bracket_stack_size[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
1041     int last_level = RL_LEVEL(main_run_list);
1042     int last_iso_level = 0;
1043
1044     memset(bracket_stack, 0, sizeof(bracket_stack[0])*num_iso_levels);
1045     memset(bracket_stack_size, 0, sizeof(bracket_stack_size[0])*num_iso_levels);
1046
1047     /* populate the bracket_size. The first LOCAL_BRACKET_SIZE entries
1048        of the stack are one the stack. Allocate the rest of the entries.
1049      */
1050     {
1051       int iso_level;
1052       for (iso_level=0; iso_level < LOCAL_BRACKET_SIZE; iso_level++)
1053         bracket_stack[iso_level] = local_bracket_stack[iso_level];
1054
1055       for (iso_level=LOCAL_BRACKET_SIZE; iso_level < num_iso_levels; iso_level++)
1056         bracket_stack[iso_level] = fribidi_malloc (sizeof (bracket_stack[0])
1057                                                        * FRIBIDI_BIDI_MAX_NESTED_BRACKET_PAIRS);
1058     }
1059
1060     /* Build the bd16 pair stack. */
1061     for_run_list (pp, main_run_list)
1062       {
1063         int level = RL_LEVEL(pp);
1064         int iso_level = RL_ISOLATE_LEVEL(pp);
1065         FriBidiBracketType brack_prop = RL_BRACKET_TYPE(pp);
1066
1067         /* Interpret the isolating run sequence as such that they
1068            end at a change in the level, unless the iso_level has been
1069            raised. */
1070         if (level != last_level && last_iso_level == iso_level)
1071           bracket_stack_size[last_iso_level] = 0;
1072
1073         if (brack_prop!= FRIBIDI_NO_BRACKET
1074             && RL_TYPE(pp)==FRIBIDI_TYPE_ON)
1075           {
1076             if (FRIBIDI_IS_BRACKET_OPEN(brack_prop))
1077               {
1078                 if (bracket_stack_size[iso_level]==FRIBIDI_BIDI_MAX_NESTED_BRACKET_PAIRS)
1079                   break;
1080
1081                 /* push onto the pair stack */
1082                 bracket_stack[iso_level][bracket_stack_size[iso_level]++] = pp;
1083               }
1084             else
1085               {
1086                 int stack_idx = bracket_stack_size[iso_level] - 1;
1087                 while (stack_idx >= 0)
1088                   {
1089                     FriBidiBracketType se_brack_prop = RL_BRACKET_TYPE(bracket_stack[iso_level][stack_idx]);
1090                     if (FRIBIDI_BRACKET_ID(se_brack_prop) == FRIBIDI_BRACKET_ID(brack_prop))
1091                       {
1092                         bracket_stack_size[iso_level] = stack_idx;
1093
1094                         pairing_nodes = pairing_nodes_push(pairing_nodes,
1095                                                            bracket_stack[iso_level][stack_idx],
1096                                                            pp);
1097                         break;
1098                     }
1099                     stack_idx--;
1100                   }
1101               }
1102           }
1103         last_level = level;
1104         last_iso_level = iso_level;
1105       }
1106
1107     /* The list must now be sorted for the next algo to work! */
1108     sort_pairing_nodes(&pairing_nodes);
1109
1110 # if DEBUG
1111     if UNLIKELY
1112     (fribidi_debug_status ())
1113       {
1114         print_pairing_nodes (pairing_nodes);
1115       }
1116 # endif /* DEBUG */
1117
1118     /* Start the N0 */
1119     {
1120       FriBidiPairingNode *ppairs = pairing_nodes;
1121       while (ppairs)
1122         {
1123           int embedding_level = ppairs->open->level;
1124
1125           /* Find matching strong. */
1126           fribidi_boolean found = false;
1127           FriBidiRun *ppn;
1128           for (ppn = ppairs->open; ppn!= ppairs->close; ppn = ppn->next)
1129             {
1130               FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1131
1132               /* Calculate level like in resolve implicit levels below to prevent
1133                  embedded levels not to match the base_level */
1134               int this_level = RL_LEVEL (ppn) +
1135                 (FRIBIDI_LEVEL_IS_RTL (RL_LEVEL(ppn)) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1136
1137               /* N0b */
1138               if (FRIBIDI_IS_STRONG (this_type) && this_level == embedding_level)
1139                 {
1140                   RL_TYPE(ppairs->open) = RL_TYPE(ppairs->close) = this_level%2 ? FRIBIDI_TYPE_RTL : FRIBIDI_TYPE_LTR;
1141                   found = true;
1142                   break;
1143                 }
1144             }
1145
1146           /* N0c */
1147           /* Search for any strong type preceding and within the bracket pair */
1148           if (!found)
1149             {
1150               /* Search for a preceding strong */
1151               int prec_strong_level = embedding_level; /* TBDov! Extract from Isolate level in effect */
1152               int iso_level = RL_ISOLATE_LEVEL(ppairs->open);
1153               for (ppn = ppairs->open->prev; ppn->type != FRIBIDI_TYPE_SENTINEL; ppn=ppn->prev)
1154                 {
1155                   FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1156                   if (FRIBIDI_IS_STRONG (this_type) && RL_ISOLATE_LEVEL(ppn) == iso_level)
1157                     {
1158                       prec_strong_level = RL_LEVEL (ppn) +
1159                         (FRIBIDI_LEVEL_IS_RTL (RL_LEVEL(ppn)) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1160
1161                       break;
1162                     }
1163                 }
1164
1165               for (ppn = ppairs->open; ppn!= ppairs->close; ppn = ppn->next)
1166                 {
1167                   FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1168                   if (FRIBIDI_IS_STRONG (this_type) && RL_ISOLATE_LEVEL(ppn) == iso_level)
1169                     {
1170                       /* By constraint this is opposite the embedding direction,
1171                          since we did not match the N0b rule. We must now
1172                          compare with the preceding strong to establish whether
1173                          to apply N0c1 (opposite) or N0c2 embedding */
1174                       RL_TYPE(ppairs->open) = RL_TYPE(ppairs->close) = prec_strong_level % 2 ? FRIBIDI_TYPE_RTL : FRIBIDI_TYPE_LTR;
1175                       found = true;
1176                       break;
1177                     }
1178                 }
1179             }
1180
1181           ppairs = ppairs->next;
1182         }
1183
1184       free_pairing_nodes(pairing_nodes);
1185
1186       if (num_iso_levels >= LOCAL_BRACKET_SIZE)
1187         {
1188           int i;
1189           /* Only need to free the non static members */
1190           for (i=LOCAL_BRACKET_SIZE; i<num_iso_levels; i++)
1191             fribidi_free(bracket_stack[i]);
1192         }
1193
1194       /* Remove the bracket property and re-compact */
1195       {
1196         const FriBidiBracketType NoBracket = FRIBIDI_NO_BRACKET;
1197         for_run_list (pp, main_run_list)
1198           pp->bracket_type = NoBracket;
1199         compact_neutrals (main_run_list);
1200       }
1201     }
1202
1203 # if DEBUG
1204   if UNLIKELY
1205     (fribidi_debug_status ())
1206     {
1207       print_resolved_levels (main_run_list);
1208       print_resolved_types (main_run_list);
1209     }
1210 # endif /* DEBUG */
1211   }
1212
1213   DBG ("resolving neutral types - N1+N2");
1214   {
1215     for_run_list (pp, main_run_list)
1216     {
1217       FriBidiCharType prev_type, this_type, next_type;
1218       FriBidiRun *ppp_prev, *ppp_next;
1219
1220       ppp_prev = get_adjacent_run(pp, false, false);
1221       ppp_next = get_adjacent_run(pp, true, false);
1222
1223       /* "European and Arabic numbers are treated as though they were R"
1224          FRIBIDI_CHANGE_NUMBER_TO_RTL does this. */
1225       this_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE (pp));
1226
1227       if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
1228         prev_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_prev));
1229       else
1230         prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
1231
1232       if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
1233         next_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_next));
1234       else
1235         next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
1236
1237       if (FRIBIDI_IS_NEUTRAL (this_type))
1238         RL_TYPE (pp) = (prev_type == next_type) ?
1239           /* N1. */ prev_type :
1240           /* N2. */ FRIBIDI_EMBEDDING_DIRECTION (pp);
1241     }
1242   }
1243
1244   compact_list (main_run_list);
1245
1246 # if DEBUG
1247   if UNLIKELY
1248     (fribidi_debug_status ())
1249     {
1250       print_resolved_levels (main_run_list);
1251       print_resolved_types (main_run_list);
1252     }
1253 # endif /* DEBUG */
1254
1255   /* 6. Resolving implicit levels */
1256   DBG ("resolving implicit levels");
1257   {
1258     max_level = base_level;
1259
1260     for_run_list (pp, main_run_list)
1261     {
1262       FriBidiCharType this_type;
1263       int level;
1264
1265       this_type = RL_TYPE (pp);
1266       level = RL_LEVEL (pp);
1267
1268       /* I1. Even */
1269       /* I2. Odd */
1270       if (FRIBIDI_IS_NUMBER (this_type))
1271         RL_LEVEL (pp) = (level + 2) & ~1;
1272       else
1273         RL_LEVEL (pp) =
1274           level +
1275           (FRIBIDI_LEVEL_IS_RTL (level) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1276
1277       if (RL_LEVEL (pp) > max_level)
1278         max_level = RL_LEVEL (pp);
1279     }
1280   }
1281
1282   compact_list (main_run_list);
1283
1284 # if DEBUG
1285   if UNLIKELY
1286     (fribidi_debug_status ())
1287     {
1288       print_bidi_string (bidi_types, len);
1289       print_resolved_levels (main_run_list);
1290       print_resolved_types (main_run_list);
1291     }
1292 # endif /* DEBUG */
1293
1294 /* Reinsert the explicit codes & BN's that are already removed, from the
1295    explicits_list to main_run_list. */
1296   DBG ("reinserting explicit codes");
1297   if UNLIKELY
1298     (explicits_list->next != explicits_list)
1299     {
1300       register FriBidiRun *p;
1301       register fribidi_boolean stat =
1302         shadow_run_list (main_run_list, explicits_list, true);
1303       explicits_list = NULL;
1304       if UNLIKELY
1305         (!stat) goto out;
1306
1307       /* Set level of inserted explicit chars to that of their previous
1308        * char, such that they do not affect reordering. */
1309       p = main_run_list->next;
1310       if (p != main_run_list && p->level == FRIBIDI_SENTINEL)
1311         p->level = base_level;
1312       for_run_list (p, main_run_list) if (p->level == FRIBIDI_SENTINEL)
1313         p->level = p->prev->level;
1314     }
1315
1316 # if DEBUG
1317   if UNLIKELY
1318     (fribidi_debug_status ())
1319     {
1320       print_types_re (main_run_list);
1321       print_resolved_levels (main_run_list);
1322       print_resolved_types (main_run_list);
1323     }
1324 # endif /* DEBUG */
1325
1326   DBG ("reset the embedding levels, 1, 2, 3.");
1327   {
1328     register int j, state, pos;
1329     register FriBidiCharType char_type;
1330     register FriBidiRun *p, *q, *list;
1331
1332     /* L1. Reset the embedding levels of some chars:
1333        1. segment separators,
1334        2. paragraph separators,
1335        3. any sequence of whitespace characters preceding a segment
1336           separator or paragraph separator, and
1337        4. any sequence of whitespace characters and/or isolate formatting
1338           characters at the end of the line.
1339        ... (to be continued in fribidi_reorder_line()). */
1340     list = new_run_list ();
1341     if UNLIKELY
1342       (!list) goto out;
1343     q = list;
1344     state = 1;
1345     pos = len - 1;
1346     for (j = len - 1; j >= -1; j--)
1347       {
1348         /* close up the open link at the end */
1349         if (j >= 0)
1350           char_type = bidi_types[j];
1351         else
1352           char_type = FRIBIDI_TYPE_ON;
1353         if (!state && FRIBIDI_IS_SEPARATOR (char_type))
1354           {
1355             state = 1;
1356             pos = j;
1357           }
1358         else if (state &&
1359                  !(FRIBIDI_IS_EXPLICIT_OR_SEPARATOR_OR_BN_OR_WS(char_type)
1360                    || FRIBIDI_IS_ISOLATE(char_type)))
1361           {
1362             state = 0;
1363             p = new_run ();
1364             if UNLIKELY
1365               (!p)
1366               {
1367                 free_run_list (list);
1368                 goto out;
1369               }
1370             p->pos = j + 1;
1371             p->len = pos - j;
1372             p->type = base_dir;
1373             p->level = base_level;
1374             move_node_before (p, q);
1375             q = p;
1376           }
1377       }
1378     if UNLIKELY
1379       (!shadow_run_list (main_run_list, list, false)) goto out;
1380   }
1381
1382 # if DEBUG
1383   if UNLIKELY
1384     (fribidi_debug_status ())
1385     {
1386       print_types_re (main_run_list);
1387       print_resolved_levels (main_run_list);
1388       print_resolved_types (main_run_list);
1389     }
1390 # endif /* DEBUG */
1391
1392   {
1393     FriBidiStrIndex pos = 0;
1394     for_run_list (pp, main_run_list)
1395     {
1396       register FriBidiStrIndex l;
1397       register FriBidiLevel level = pp->level;
1398       for (l = pp->len; l; l--)
1399         embedding_levels[pos++] = level;
1400     }
1401   }
1402
1403   status = true;
1404
1405 out:
1406   DBG ("leaving fribidi_get_par_embedding_levels");
1407
1408   if (main_run_list)
1409     free_run_list (main_run_list);
1410   if UNLIKELY
1411     (explicits_list) free_run_list (explicits_list);
1412
1413   return status ? max_level + 1 : 0;
1414 }
1415
1416
1417 static void
1418 bidi_string_reverse (
1419   FriBidiChar *str,
1420   const FriBidiStrIndex len
1421 )
1422 {
1423   FriBidiStrIndex i;
1424
1425   fribidi_assert (str);
1426
1427   for (i = 0; i < len / 2; i++)
1428     {
1429       FriBidiChar tmp = str[i];
1430       str[i] = str[len - 1 - i];
1431       str[len - 1 - i] = tmp;
1432     }
1433 }
1434
1435 static void
1436 index_array_reverse (
1437   FriBidiStrIndex *arr,
1438   const FriBidiStrIndex len
1439 )
1440 {
1441   FriBidiStrIndex i;
1442
1443   fribidi_assert (arr);
1444
1445   for (i = 0; i < len / 2; i++)
1446     {
1447       FriBidiStrIndex tmp = arr[i];
1448       arr[i] = arr[len - 1 - i];
1449       arr[len - 1 - i] = tmp;
1450     }
1451 }
1452
1453
1454 FRIBIDI_ENTRY FriBidiLevel
1455 fribidi_reorder_line (
1456   /* input */
1457   FriBidiFlags flags, /* reorder flags */
1458   const FriBidiCharType *bidi_types,
1459   const FriBidiStrIndex len,
1460   const FriBidiStrIndex off,
1461   const FriBidiParType base_dir,
1462   /* input and output */
1463   FriBidiLevel *embedding_levels,
1464   FriBidiChar *visual_str,
1465   /* output */
1466   FriBidiStrIndex *map
1467 )
1468 {
1469   fribidi_boolean status = false;
1470   FriBidiLevel max_level = 0;
1471
1472   if UNLIKELY
1473     (len == 0)
1474     {
1475       status = true;
1476       goto out;
1477     }
1478
1479   DBG ("in fribidi_reorder_line");
1480
1481   fribidi_assert (bidi_types);
1482   fribidi_assert (embedding_levels);
1483
1484   DBG ("reset the embedding levels, 4. whitespace at the end of line");
1485   {
1486     register FriBidiStrIndex i;
1487
1488     /* L1. Reset the embedding levels of some chars:
1489        4. any sequence of white space characters at the end of the line. */
1490     for (i = off + len - 1; i >= off &&
1491          FRIBIDI_IS_EXPLICIT_OR_BN_OR_WS (bidi_types[i]); i--)
1492       embedding_levels[i] = FRIBIDI_DIR_TO_LEVEL (base_dir);
1493   }
1494
1495   /* 7. Reordering resolved levels */
1496   {
1497     register FriBidiLevel level;
1498     register FriBidiStrIndex i;
1499
1500     /* Reorder both the outstring and the order array */
1501     {
1502       if (FRIBIDI_TEST_BITS (flags, FRIBIDI_FLAG_REORDER_NSM))
1503         {
1504           /* L3. Reorder NSMs. */
1505           for (i = off + len - 1; i >= off; i--)
1506             if (FRIBIDI_LEVEL_IS_RTL (embedding_levels[i])
1507                 && bidi_types[i] == FRIBIDI_TYPE_NSM)
1508               {
1509                 register FriBidiStrIndex seq_end = i;
1510                 level = embedding_levels[i];
1511
1512                 for (i--; i >= off &&
1513                      FRIBIDI_IS_EXPLICIT_OR_BN_OR_NSM (bidi_types[i])
1514                      && embedding_levels[i] == level; i--)
1515                   ;
1516
1517                 if (i < off || embedding_levels[i] != level)
1518                   {
1519                     i++;
1520                     DBG ("warning: NSM(s) at the beginning of level run");
1521                   }
1522
1523                 if (visual_str)
1524                   {
1525                     bidi_string_reverse (visual_str + i, seq_end - i + 1);
1526                   }
1527                 if (map)
1528                   {
1529                     index_array_reverse (map + i, seq_end - i + 1);
1530                   }
1531               }
1532         }
1533
1534       /* Find max_level of the line.  We don't reuse the paragraph
1535        * max_level, both for a cleaner API, and that the line max_level
1536        * may be far less than paragraph max_level. */
1537       for (i = off + len - 1; i >= off; i--)
1538         if (embedding_levels[i] > max_level)
1539           max_level = embedding_levels[i];
1540
1541       /* L2. Reorder. */
1542       for (level = max_level; level > 0; level--)
1543         for (i = off + len - 1; i >= off; i--)
1544           if (embedding_levels[i] >= level)
1545             {
1546               /* Find all stretches that are >= level_idx */
1547               register FriBidiStrIndex seq_end = i;
1548               for (i--; i >= off && embedding_levels[i] >= level; i--)
1549                 ;
1550
1551               if (visual_str)
1552                 bidi_string_reverse (visual_str + i + 1, seq_end - i);
1553               if (map)
1554                 index_array_reverse (map + i + 1, seq_end - i);
1555             }
1556     }
1557
1558   }
1559
1560   status = true;
1561
1562 out:
1563
1564   return status ? max_level + 1 : 0;
1565 }
1566
1567 /* Editor directions:
1568  * vim:textwidth=78:tabstop=8:shiftwidth=2:autoindent:cindent
1569  */