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