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