lib/fribidi-bidi.c

   1 /* FriBidi
   2  * fribidi-bidi.c - bidirectional algorithm
   3  *
   4  * $Id: fribidi-bidi.c,v 1.21 2007-03-15 18:09:25 behdad Exp $
   5  * $Author: behdad $
   6  * $Date: 2007-03-15 18:09:25 $
   7  * $Revision: 1.21 $
   8  * $Source: /home/behdad/src/fdo/fribidi/togit/git/../fribidi/fribidi2/lib/fribidi-bidi.c,v $
   9  *
  10  * Authors:
  11  *   Behdad Esfahbod, 2001, 2002, 2004
  12  *   Dov Grobgeld, 1999, 2000
  13  *
  14  * Copyright (C) 2004 Sharif FarsiWeb, Inc
  15  * Copyright (C) 2001,2002 Behdad Esfahbod
  16  * Copyright (C) 1999,2000 Dov Grobgeld
  17  *
  18  * This library is free software; you can redistribute it and/or
  19  * modify it under the terms of the GNU Lesser General Public
  20  * License as published by the Free Software Foundation; either
  21  * version 2.1 of the License, or (at your option) any later version.
  22  *
  23  * This library is distributed in the hope that it will be useful,
  24  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26  * Lesser General Public License for more details.
  27  *
  28  * You should have received a copy of the GNU Lesser General Public License
  29  * along with this library, in a file named COPYING; if not, write to the
  30  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  31  * Boston, MA 02110-1301, USA
  32  *
  33  * For licensing issues, contact <license@farsiweb.info>.
  34  */
  35
  36 #include "common.h"
  37
  38 #include <fribidi-bidi.h>
  39 #include <fribidi-mirroring.h>
  40 #include <fribidi-unicode.h>
  41
  42 #include "mem.h"
  43 #include "bidi-types.h"
  44 #include "run.h"
  45
  46 /*
  47  * This file implements most of Unicode Standard Annex #9, Tracking Number 13.
  48  */
  49
  50 #ifndef MAX
  51 # define MAX(a,b) ((a) > (b) ? (a) : (b))
  52 #endif /* !MAX */
  53
  54 /* Some convenience macros */
  55 #define RL_TYPE(list) ((list)->type)
  56 #define RL_LEN(list) ((list)->len)
  57 #define RL_POS(list) ((list)->pos)
  58 #define RL_LEVEL(list) ((list)->level)
  59
  60 static FriBidiRun *
  61 merge_with_prev (
  62   FriBidiRun *second
  63 )
  64 {
  65   FriBidiRun *first;
  66
  67   fribidi_assert (second);
  68   fribidi_assert (second->next);
  69   first = second->prev;
  70   fribidi_assert (first);
  71
  72   first->next = second->next;
  73   first->next->prev = first;
  74   RL_LEN (first) += RL_LEN (second);
  75   free_run (second);
  76   return first;
  77 }
  78
  79 static void
  80 compact_list (
  81   FriBidiRun *list
  82 )
  83 {
  84   fribidi_assert (list);
  85
  86   if (list->next)
  87     for_run_list (list, list)
  88       if (RL_TYPE (list->prev) == RL_TYPE (list)
  89           && RL_LEVEL (list->prev) == RL_LEVEL (list))
  90       list = merge_with_prev (list);
  91 }
  92
  93 static void
  94 compact_neutrals (
  95   FriBidiRun *list
  96 )
  97 {
  98   fribidi_assert (list);
  99
 100   if (list->next)
 101     {
 102       for_run_list (list, list)
 103       {
 104         if (RL_LEVEL (list->prev) == RL_LEVEL (list)
 105             &&
 106             ((RL_TYPE
 107               (list->prev) == RL_TYPE (list)
 108               || (FRIBIDI_IS_NEUTRAL (RL_TYPE (list->prev))
 109                   && FRIBIDI_IS_NEUTRAL (RL_TYPE (list))))))
 110           list = merge_with_prev (list);
 111       }
 112     }
 113 }
 114
 115 #if DEBUG+0
 116 /*======================================================================
 117  *  For debugging, define some functions for printing the types and the
 118  *  levels.
 119  *----------------------------------------------------------------------*/
 120
 121 static char char_from_level_array[] = {
 122   '$',                          /* -1 == FRIBIDI_SENTINEL, indicating
 123                                  * start or end of string. */
 124   /* 0-61 == 0-9,a-z,A-Z are the the only valid levels before resolving
 125    * implicits.  after that the level @ may be appear too. */
 126   '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 127   'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
 128   'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
 129   'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',
 130   'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 131   'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
 132   'Y', 'Z',
 133
 134   '@',                          /* 62 == only must appear after resolving
 135                                  * implicits. */
 136
 137   '!',                          /* 63 == FRIBIDI_LEVEL_INVALID, internal error,
 138                                  * this level shouldn't be seen.  */
 139
 140   '*', '*', '*', '*', '*'       /* >= 64 == overflows, this levels and higher
 141                                  * levels show a real bug!. */
 142 };
 143
 144 #define fribidi_char_from_level(level) char_from_level_array[(level) + 1]
 145
 146 static void
 147 print_types_re (
 148   const FriBidiRun *pp
 149 )
 150 {
 151   fribidi_assert (pp);
 152
 153   MSG ("  Run types  : ");
 154   for_run_list (pp, pp)
 155   {
 156     MSG5 ("%d:%d(%s)[%d] ",
 157           pp->pos, pp->len, fribidi_get_bidi_type_name (pp->type), pp->level);
 158   }
 159   MSG ("\n");
 160 }
 161
 162 static void
 163 print_resolved_levels (
 164   const FriBidiRun *pp
 165 )
 166 {
 167   fribidi_assert (pp);
 168
 169   MSG ("  Res. levels: ");
 170   for_run_list (pp, pp)
 171   {
 172     register FriBidiStrIndex i;
 173     for (i = RL_LEN (pp); i; i--)
 174       MSG2 ("%c", fribidi_char_from_level (RL_LEVEL (pp)));
 175   }
 176   MSG ("\n");
 177 }
 178
 179 static void
 180 print_resolved_types (
 181   const FriBidiRun *pp
 182 )
 183 {
 184   fribidi_assert (pp);
 185
 186   MSG ("  Res. types : ");
 187   for_run_list (pp, pp)
 188   {
 189     FriBidiStrIndex i;
 190     for (i = RL_LEN (pp); i; i--)
 191       MSG2 ("%c", fribidi_char_from_bidi_type (pp->type));
 192   }
 193   MSG ("\n");
 194 }
 195
 196 static void
 197 print_bidi_string (
 198   /* input */
 199   const FriBidiCharType *bidi_types,
 200   const FriBidiStrIndex len
 201 )
 202 {
 203   register FriBidiStrIndex i;
 204
 205   fribidi_assert (bidi_types);
 206
 207   MSG ("  Org. types : ");
 208   for (i = 0; i < len; i++)
 209     MSG2 ("%c", fribidi_char_from_bidi_type (bidi_types[i]));
 210   MSG ("\n");
 211 }
 212 #endif /* DEBUG */
 213
 214
 215 /*=========================================================================
 216  * define macros for push and pop the status in to / out of the stack
 217  *-------------------------------------------------------------------------*/
 218
 219 /* There are a few little points in pushing into and poping from the status
 220    stack:
 221    1. when the embedding level is not valid (more than
 222    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=61), you must reject it, and not to push
 223    into the stack, but when you see a PDF, you must find the matching code,
 224    and if it was pushed in the stack, pop it, it means you must pop if and
 225    only if you have pushed the matching code, the over_pushed var counts the
 226    number of rejected codes so far.
 227    2. there's a more confusing point too, when the embedding level is exactly
 228    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL-1=60, an LRO or LRE is rejected
 229    because the new level would be FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL+1=62, that
 230    is invalid; but an RLO or RLE is accepted because the new level is
 231    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=61, that is valid, so the rejected codes
 232    may be not continuous in the logical order, in fact there are at most two
 233    continuous intervals of codes, with an RLO or RLE between them.  To support
 234    this case, the first_interval var counts the number of rejected codes in
 235    the first interval, when it is 0, means that there is only one interval.
 236 */
 237
 238 /* a. If this new level would be valid, then this embedding code is valid.
 239    Remember (push) the current embedding level and override status.
 240    Reset current level to this new level, and reset the override status to
 241    new_override.
 242    b. If the new level would not be valid, then this code is invalid. Don't
 243    change the current level or override status.
 244 */
 245 #define PUSH_STATUS \
 246     FRIBIDI_BEGIN_STMT \
 247       if LIKELY(new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL) \
 248         { \
 249           if UNLIKELY(level == FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL - 1) \
 250             first_interval = over_pushed; \
 251           status_stack[stack_size].level = level; \
 252           status_stack[stack_size].override = override; \
 253           stack_size++; \
 254           level = new_level; \
 255           override = new_override; \
 256         } else \
 257           over_pushed++; \
 258     FRIBIDI_END_STMT
 259
 260 /* If there was a valid matching code, restore (pop) the last remembered
 261    (pushed) embedding level and directional override.
 262 */
 263 #define POP_STATUS \
 264     FRIBIDI_BEGIN_STMT \
 265       if (stack_size) \
 266       { \
 267         if UNLIKELY(over_pushed > first_interval) \
 268           over_pushed--; \
 269         else \
 270           { \
 271             if LIKELY(over_pushed == first_interval) \
 272               first_interval = 0; \
 273             stack_size--; \
 274             level = status_stack[stack_size].level; \
 275             override = status_stack[stack_size].override; \
 276           } \
 277       } \
 278     FRIBIDI_END_STMT
 279
 280
 281 /* Return the type of previous run or the SOR, if already at the start of
 282    a level run. */
 283 #define PREV_TYPE_OR_SOR(pp) \
 284     ( \
 285       RL_LEVEL(pp->prev) == RL_LEVEL(pp) ? \
 286         RL_TYPE(pp->prev) : \
 287         FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->prev), RL_LEVEL(pp))) \
 288     )
 289
 290 /* Return the type of next run or the EOR, if already at the end of
 291    a level run. */
 292 #define NEXT_TYPE_OR_EOR(pp) \
 293     ( \
 294       RL_LEVEL(pp->next) == RL_LEVEL(pp) ? \
 295         RL_TYPE(pp->next) : \
 296         FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->next), RL_LEVEL(pp))) \
 297     )
 298
 299
 300 /* Return the embedding direction of a link. */
 301 #define FRIBIDI_EMBEDDING_DIRECTION(link) \
 302     FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(link))
 303
 304
 305 FRIBIDI_ENTRY FriBidiParType
 306 fribidi_get_par_direction (
 307   /* input */
 308   const FriBidiCharType *bidi_types,
 309   const FriBidiStrIndex len
 310 )
 311 {
 312   register FriBidiStrIndex i;
 313
 314   fribidi_assert (bidi_types);
 315
 316   for (i = 0; i < len; i++)
 317     if (FRIBIDI_IS_LETTER (bidi_types[i]))
 318       return FRIBIDI_IS_RTL (bidi_types[i]) ? FRIBIDI_PAR_RTL :
 319         FRIBIDI_PAR_LTR;
 320
 321   return FRIBIDI_PAR_ON;
 322 }
 323
 324 FRIBIDI_ENTRY FriBidiLevel
 325 fribidi_get_par_embedding_levels (
 326   /* input */
 327   const FriBidiCharType *bidi_types,
 328   const FriBidiStrIndex len,
 329   /* input and output */
 330   FriBidiParType *pbase_dir,
 331   /* output */
 332   FriBidiLevel *embedding_levels
 333 )
 334 {
 335   FriBidiLevel base_level, max_level = 0;
 336   FriBidiParType base_dir;
 337   FriBidiRun *main_run_list = NULL, *explicits_list = NULL, *pp;
 338   fribidi_boolean status = false;
 339
 340   if UNLIKELY
 341     (!len)
 342     {
 343       status = true;
 344       goto out;
 345     }
 346
 347   DBG ("in fribidi_get_par_embedding_levels");
 348
 349   fribidi_assert (bidi_types);
 350   fribidi_assert (pbase_dir);
 351   fribidi_assert (embedding_levels);
 352
 353   /* Determinate character types */
 354   {
 355     /* Get run-length encoded character types */
 356     main_run_list = run_list_encode_bidi_types (bidi_types, len);
 357     if UNLIKELY
 358       (!main_run_list) goto out;
 359   }
 360
 361   /* Find base level */
 362   /* If no strong base_dir was found, resort to the weak direction
 363      that was passed on input. */
 364   base_level = FRIBIDI_DIR_TO_LEVEL (*pbase_dir);
 365   if (!FRIBIDI_IS_STRONG (*pbase_dir))
 366     /* P2. P3. Search for first strong character and use its direction as
 367        base direction */
 368     {
 369       for_run_list (pp, main_run_list) if (FRIBIDI_IS_LETTER (RL_TYPE (pp)))
 370         {
 371           base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (pp));
 372           *pbase_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 373           break;
 374         }
 375     }
 376   base_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 377   DBG2 ("  base level : %c", fribidi_char_from_level (base_level));
 378   DBG2 ("  base dir   : %c", fribidi_char_from_bidi_type (base_dir));
 379
 380 # if DEBUG
 381   if UNLIKELY
 382     (fribidi_debug_status ())
 383     {
 384       print_types_re (main_run_list);
 385     }
 386 # endif /* DEBUG */
 387
 388   /* Explicit Levels and Directions */
 389   DBG ("explicit levels and directions");
 390   {
 391     FriBidiLevel level, new_level;
 392     FriBidiCharType override, new_override;
 393     FriBidiStrIndex i;
 394     int stack_size, over_pushed, first_interval;
 395     struct
 396     {
 397       FriBidiCharType override; /* only LTR, RTL and ON are valid */
 398       FriBidiLevel level;
 399     } *status_stack;
 400     FriBidiRun temp_link;
 401
 402 /* explicits_list is a list like main_run_list, that holds the explicit
 403    codes that are removed from main_run_list, to reinsert them later by
 404    calling the shadow_run_list.
 405 */
 406     explicits_list = new_run_list ();
 407     if UNLIKELY
 408       (!explicits_list) goto out;
 409
 410     /* X1. Begin by setting the current embedding level to the paragraph
 411        embedding level. Set the directional override status to neutral.
 412        Process each character iteratively, applying rules X2 through X9.
 413        Only embedding levels from 0 to 61 are valid in this phase. */
 414
 415     level = base_level;
 416     override = FRIBIDI_TYPE_ON;
 417     /* stack */
 418     stack_size = 0;
 419     over_pushed = 0;
 420     first_interval = 0;
 421     status_stack = fribidi_malloc (sizeof (status_stack[0]) *
 422                                    FRIBIDI_BIDI_MAX_RESOLVED_LEVELS);
 423
 424     for_run_list (pp, main_run_list)
 425     {
 426       FriBidiCharType this_type = RL_TYPE (pp);
 427       if (FRIBIDI_IS_EXPLICIT_OR_BN (this_type))
 428         {
 429           if (FRIBIDI_IS_STRONG (this_type))
 430             {                   /* LRE, RLE, LRO, RLO */
 431               /* 1. Explicit Embeddings */
 432               /*   X2. With each RLE, compute the least greater odd
 433                  embedding level. */
 434               /*   X3. With each LRE, compute the least greater even
 435                  embedding level. */
 436               /* 2. Explicit Overrides */
 437               /*   X4. With each RLO, compute the least greater odd
 438                  embedding level. */
 439               /*   X5. With each LRO, compute the least greater even
 440                  embedding level. */
 441               new_override = FRIBIDI_EXPLICIT_TO_OVERRIDE_DIR (this_type);
 442               for (i = RL_LEN (pp); i; i--)
 443                 {
 444                   new_level =
 445                     ((level + FRIBIDI_DIR_TO_LEVEL (this_type) + 2) & ~1) -
 446                     FRIBIDI_DIR_TO_LEVEL (this_type);
 447                   PUSH_STATUS;
 448                 }
 449             }
 450           else if (this_type == FRIBIDI_TYPE_PDF)
 451             {
 452               /* 3. Terminating Embeddings and overrides */
 453               /*   X7. With each PDF, determine the matching embedding or
 454                  override code. */
 455               for (i = RL_LEN (pp); i; i--)
 456                 POP_STATUS;
 457             }
 458
 459           /* X9. Remove all RLE, LRE, RLO, LRO, PDF, and BN codes. */
 460           /* Remove element and add it to explicits_list */
 461           RL_LEVEL (pp) = FRIBIDI_SENTINEL;
 462           temp_link.next = pp->next;
 463           move_node_before (pp, explicits_list);
 464           pp = &temp_link;
 465         }
 466       else if (this_type == FRIBIDI_TYPE_BS)
 467         {
 468           /* X8. All explicit directional embeddings and overrides are
 469              completely terminated at the end of each paragraph. Paragraph
 470              separators are not included in the embedding. */
 471           break;
 472         }
 473       else
 474         {
 475           /* X6. For all types besides RLE, LRE, RLO, LRO, and PDF:
 476              a. Set the level of the current character to the current
 477              embedding level.
 478              b. Whenever the directional override status is not neutral,
 479              reset the current character type to the directional override
 480              status. */
 481           RL_LEVEL (pp) = level;
 482           if (!FRIBIDI_IS_NEUTRAL (override))
 483             RL_TYPE (pp) = override;
 484         }
 485     }
 486
 487     /* Implementing X8. It has no effect on a single paragraph! */
 488     level = base_level;
 489     override = FRIBIDI_TYPE_ON;
 490     stack_size = 0;
 491     over_pushed = 0;
 492
 493     fribidi_free (status_stack);
 494   }
 495   /* X10. The remaining rules are applied to each run of characters at the
 496      same level. For each run, determine the start-of-level-run (sor) and
 497      end-of-level-run (eor) type, either L or R. This depends on the
 498      higher of the two levels on either side of the boundary (at the start
 499      or end of the paragraph, the level of the 'other' run is the base
 500      embedding level). If the higher level is odd, the type is R, otherwise
 501      it is L. */
 502   /* Resolving Implicit Levels can be done out of X10 loop, so only change
 503      of Resolving Weak Types and Resolving Neutral Types is needed. */
 504
 505   compact_list (main_run_list);
 506
 507 # if DEBUG
 508   if UNLIKELY
 509     (fribidi_debug_status ())
 510     {
 511       print_types_re (main_run_list);
 512       print_bidi_string (bidi_types, len);
 513       print_resolved_levels (main_run_list);
 514       print_resolved_types (main_run_list);
 515     }
 516 # endif /* DEBUG */
 517
 518   /* 4. Resolving weak types */
 519   DBG ("resolving weak types");
 520   {
 521     FriBidiCharType last_strong, prev_type_orig;
 522     fribidi_boolean w4;
 523
 524     last_strong = base_dir;
 525
 526     for_run_list (pp, main_run_list)
 527     {
 528       register FriBidiCharType prev_type, this_type, next_type;
 529
 530       prev_type = PREV_TYPE_OR_SOR (pp);
 531       this_type = RL_TYPE (pp);
 532       next_type = NEXT_TYPE_OR_EOR (pp);
 533
 534       if (FRIBIDI_IS_STRONG (prev_type))
 535         last_strong = prev_type;
 536
 537       /* W1. NSM
 538          Examine each non-spacing mark (NSM) in the level run, and change the
 539          type of the NSM to the type of the previous character. If the NSM
 540          is at the start of the level run, it will get the type of sor. */
 541       /* Implementation note: it is important that if the previous character
 542          is not sor, then we should merge this run with the previous,
 543          because of rules like W5, that we assume all of a sequence of
 544          adjacent ETs are in one FriBidiRun. */
 545       if (this_type == FRIBIDI_TYPE_NSM)
 546         {
 547           if (RL_LEVEL (pp->prev) == RL_LEVEL (pp))
 548             pp = merge_with_prev (pp);
 549           else
 550             RL_TYPE (pp) = prev_type;
 551           if (prev_type == next_type && RL_LEVEL (pp) == RL_LEVEL (pp->next))
 552             {
 553               pp = merge_with_prev (pp->next);
 554             }
 555           continue;             /* As we know the next condition cannot be true. */
 556         }
 557
 558       /* W2: European numbers. */
 559       if (this_type == FRIBIDI_TYPE_EN && last_strong == FRIBIDI_TYPE_AL)
 560         {
 561           RL_TYPE (pp) = FRIBIDI_TYPE_AN;
 562
 563           /* Resolving dependency of loops for rules W1 and W2, so we
 564              can merge them in one loop. */
 565           if (next_type == FRIBIDI_TYPE_NSM)
 566             RL_TYPE (pp->next) = FRIBIDI_TYPE_AN;
 567         }
 568     }
 569
 570
 571     last_strong = base_dir;
 572     /* Resolving dependency of loops for rules W4 and W5, W5 may
 573        want to prevent W4 to take effect in the next turn, do this
 574        through "w4". */
 575     w4 = true;
 576     /* Resolving dependency of loops for rules W4 and W5 with W7,
 577        W7 may change an EN to L but it sets the prev_type_orig if needed,
 578        so W4 and W5 in next turn can still do their works. */
 579     prev_type_orig = FRIBIDI_TYPE_ON;
 580
 581     for_run_list (pp, main_run_list)
 582     {
 583       register FriBidiCharType prev_type, this_type, next_type;
 584
 585       prev_type = PREV_TYPE_OR_SOR (pp);
 586       this_type = RL_TYPE (pp);
 587       next_type = NEXT_TYPE_OR_EOR (pp);
 588
 589       if (FRIBIDI_IS_STRONG (prev_type))
 590         last_strong = prev_type;
 591
 592       /* W3: Change ALs to R. */
 593       if (this_type == FRIBIDI_TYPE_AL)
 594         {
 595           RL_TYPE (pp) = FRIBIDI_TYPE_RTL;
 596           w4 = true;
 597           prev_type_orig = FRIBIDI_TYPE_ON;
 598           continue;
 599         }
 600
 601       /* W4. A single european separator changes to a european number.
 602          A single common separator between two numbers of the same type
 603          changes to that type. */
 604       if (w4
 605           && RL_LEN (pp) == 1 && FRIBIDI_IS_ES_OR_CS (this_type)
 606           && FRIBIDI_IS_NUMBER (prev_type_orig)
 607           && prev_type_orig == next_type
 608           && (prev_type_orig == FRIBIDI_TYPE_EN
 609               || this_type == FRIBIDI_TYPE_CS))
 610         {
 611           RL_TYPE (pp) = prev_type;
 612           this_type = RL_TYPE (pp);
 613         }
 614       w4 = true;
 615
 616       /* W5. A sequence of European terminators adjacent to European
 617          numbers changes to All European numbers. */
 618       if (this_type == FRIBIDI_TYPE_ET
 619           && (prev_type_orig == FRIBIDI_TYPE_EN
 620               || next_type == FRIBIDI_TYPE_EN))
 621         {
 622           RL_TYPE (pp) = FRIBIDI_TYPE_EN;
 623           w4 = false;
 624           this_type = RL_TYPE (pp);
 625         }
 626
 627       /* W6. Otherwise change separators and terminators to other neutral. */
 628       if (FRIBIDI_IS_NUMBER_SEPARATOR_OR_TERMINATOR (this_type))
 629         RL_TYPE (pp) = FRIBIDI_TYPE_ON;
 630
 631       /* W7. Change european numbers to L. */
 632       if (this_type == FRIBIDI_TYPE_EN && last_strong == FRIBIDI_TYPE_LTR)
 633         {
 634           RL_TYPE (pp) = FRIBIDI_TYPE_LTR;
 635           prev_type_orig = (RL_LEVEL (pp) == RL_LEVEL (pp->next) ?
 636                             FRIBIDI_TYPE_EN : FRIBIDI_TYPE_ON);
 637         }
 638       else
 639         prev_type_orig = PREV_TYPE_OR_SOR (pp->next);
 640     }
 641   }
 642
 643   compact_neutrals (main_run_list);
 644
 645 # if DEBUG
 646   if UNLIKELY
 647     (fribidi_debug_status ())
 648     {
 649       print_resolved_levels (main_run_list);
 650       print_resolved_types (main_run_list);
 651     }
 652 # endif /* DEBUG */
 653
 654   /* 5. Resolving Neutral Types */
 655   DBG ("resolving neutral types");
 656   {
 657     /* N1. and N2.
 658        For each neutral, resolve it. */
 659     for_run_list (pp, main_run_list)
 660     {
 661       FriBidiCharType prev_type, this_type, next_type;
 662
 663       /* "European and Arabic numbers are treated as though they were R"
 664          FRIBIDI_CHANGE_NUMBER_TO_RTL does this. */
 665       this_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE (pp));
 666       prev_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (PREV_TYPE_OR_SOR (pp));
 667       next_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (NEXT_TYPE_OR_EOR (pp));
 668
 669       if (FRIBIDI_IS_NEUTRAL (this_type))
 670         RL_TYPE (pp) = (prev_type == next_type) ?
 671           /* N1. */ prev_type :
 672           /* N2. */ FRIBIDI_EMBEDDING_DIRECTION (pp);
 673     }
 674   }
 675
 676   compact_list (main_run_list);
 677
 678 # if DEBUG
 679   if UNLIKELY
 680     (fribidi_debug_status ())
 681     {
 682       print_resolved_levels (main_run_list);
 683       print_resolved_types (main_run_list);
 684     }
 685 # endif /* DEBUG */
 686
 687   /* 6. Resolving implicit levels */
 688   DBG ("resolving implicit levels");
 689   {
 690     max_level = base_level;
 691
 692     for_run_list (pp, main_run_list)
 693     {
 694       FriBidiCharType this_type;
 695       int level;
 696
 697       this_type = RL_TYPE (pp);
 698       level = RL_LEVEL (pp);
 699
 700       /* I1. Even */
 701       /* I2. Odd */
 702       if (FRIBIDI_IS_NUMBER (this_type))
 703         RL_LEVEL (pp) = (level + 2) & ~1;
 704       else
 705         RL_LEVEL (pp) =
 706           level +
 707           (FRIBIDI_LEVEL_IS_RTL (level) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
 708
 709       if (RL_LEVEL (pp) > max_level)
 710         max_level = RL_LEVEL (pp);
 711     }
 712   }
 713
 714   compact_list (main_run_list);
 715
 716 # if DEBUG
 717   if UNLIKELY
 718     (fribidi_debug_status ())
 719     {
 720       print_bidi_string (bidi_types, len);
 721       print_resolved_levels (main_run_list);
 722       print_resolved_types (main_run_list);
 723     }
 724 # endif /* DEBUG */
 725
 726 /* Reinsert the explicit codes & BN's that are already removed, from the
 727    explicits_list to main_run_list. */
 728   DBG ("reinserting explicit codes");
 729   if UNLIKELY
 730     (explicits_list->next != explicits_list)
 731     {
 732       register FriBidiRun *p;
 733       register fribidi_boolean stat =
 734         shadow_run_list (main_run_list, explicits_list, true);
 735       explicits_list = NULL;
 736       if UNLIKELY
 737         (!stat) goto out;
 738
 739       /* Set level of inserted explicit chars to that of their previous
 740        * char, such that they do not affect reordering. */
 741       p = main_run_list->next;
 742       if (p != main_run_list && p->level == FRIBIDI_SENTINEL)
 743         p->level = base_level;
 744       for_run_list (p, main_run_list) if (p->level == FRIBIDI_SENTINEL)
 745         p->level = p->prev->level;
 746     }
 747
 748 # if DEBUG
 749   if UNLIKELY
 750     (fribidi_debug_status ())
 751     {
 752       print_types_re (main_run_list);
 753       print_resolved_levels (main_run_list);
 754       print_resolved_types (main_run_list);
 755     }
 756 # endif /* DEBUG */
 757
 758   DBG ("reset the embedding levels, 1, 2, 3.");
 759   {
 760     register int j, state, pos;
 761     register FriBidiCharType char_type;
 762     register FriBidiRun *p, *q, *list;
 763
 764     /* L1. Reset the embedding levels of some chars:
 765        1. segment separators,
 766        2. paragraph separators,
 767        3. any sequence of whitespace characters preceding a segment
 768        separator or paragraph separator, and
 769        ... (to be continued in fribidi_reorder_line()). */
 770     list = new_run_list ();
 771     if UNLIKELY
 772       (!list) goto out;
 773     q = list;
 774     state = 1;
 775     pos = len - 1;
 776     for (j = len - 1; j >= -1; j--)
 777       {
 778         /* close up the open link at the end */
 779         if (j >= 0)
 780           char_type = bidi_types[j];
 781         else
 782           char_type = FRIBIDI_TYPE_ON;
 783         if (!state && FRIBIDI_IS_SEPARATOR (char_type))
 784           {
 785             state = 1;
 786             pos = j;
 787           }
 788         else if (state && !FRIBIDI_IS_EXPLICIT_OR_SEPARATOR_OR_BN_OR_WS
 789                  (char_type))
 790           {
 791             state = 0;
 792             p = new_run ();
 793             if UNLIKELY
 794               (!p)
 795               {
 796                 free_run_list (list);
 797                 goto out;
 798               }
 799             p->pos = j + 1;
 800             p->len = pos - j;
 801             p->type = base_dir;
 802             p->level = base_level;
 803             move_node_before (p, q);
 804             q = p;
 805           }
 806       }
 807     if UNLIKELY
 808       (!shadow_run_list (main_run_list, list, false)) goto out;
 809   }
 810
 811 # if DEBUG
 812   if UNLIKELY
 813     (fribidi_debug_status ())
 814     {
 815       print_types_re (main_run_list);
 816       print_resolved_levels (main_run_list);
 817       print_resolved_types (main_run_list);
 818     }
 819 # endif /* DEBUG */
 820
 821   {
 822     FriBidiStrIndex pos = 0;
 823     for_run_list (pp, main_run_list)
 824     {
 825       register FriBidiStrIndex l;
 826       register FriBidiLevel level = pp->level;
 827       for (l = pp->len; l; l--)
 828         embedding_levels[pos++] = level;
 829     }
 830   }
 831
 832   status = true;
 833
 834 out:
 835   DBG ("leaving fribidi_get_par_embedding_levels");
 836
 837   if (main_run_list)
 838     free_run_list (main_run_list);
 839   if UNLIKELY
 840     (explicits_list) free_run_list (explicits_list);
 841
 842   return status ? max_level + 1 : 0;
 843 }
 844
 845
 846 static void
 847 bidi_string_reverse (
 848   FriBidiChar *str,
 849   const FriBidiStrIndex len
 850 )
 851 {
 852   FriBidiStrIndex i;
 853
 854   fribidi_assert (str);
 855
 856   for (i = 0; i < len / 2; i++)
 857     {
 858       FriBidiChar tmp = str[i];
 859       str[i] = str[len - 1 - i];
 860       str[len - 1 - i] = tmp;
 861     }
 862 }
 863
 864 static void
 865 index_array_reverse (
 866   FriBidiStrIndex *arr,
 867   const FriBidiStrIndex len
 868 )
 869 {
 870   FriBidiStrIndex i;
 871
 872   fribidi_assert (arr);
 873
 874   for (i = 0; i < len / 2; i++)
 875     {
 876       FriBidiStrIndex tmp = arr[i];
 877       arr[i] = arr[len - 1 - i];
 878       arr[len - 1 - i] = tmp;
 879     }
 880 }
 881
 882
 883 FRIBIDI_ENTRY FriBidiLevel
 884 fribidi_reorder_line (
 885   /* input */
 886   FriBidiFlags flags, /* reorder flags */
 887   const FriBidiCharType *bidi_types,
 888   const FriBidiStrIndex len,
 889   const FriBidiStrIndex off,
 890   const FriBidiParType base_dir,
 891   /* input and output */
 892   FriBidiLevel *embedding_levels,
 893   FriBidiChar *visual_str,
 894   /* output */
 895   FriBidiStrIndex *map
 896 )
 897 {
 898   fribidi_boolean status = false;
 899   FriBidiLevel max_level = 0;
 900
 901   if UNLIKELY
 902     (len == 0)
 903     {
 904       status = true;
 905       goto out;
 906     }
 907
 908   DBG ("in fribidi_reorder_line");
 909
 910   fribidi_assert (bidi_types);
 911   fribidi_assert (embedding_levels);
 912
 913   DBG ("reset the embedding levels, 4. whitespace at the end of line");
 914   {
 915     register FriBidiStrIndex i;
 916
 917     /* L1. Reset the embedding levels of some chars:
 918        4. any sequence of white space characters at the end of the line. */
 919     for (i = off + len - 1; i >= off &&
 920          FRIBIDI_IS_EXPLICIT_OR_BN_OR_WS (bidi_types[i]); i--)
 921       embedding_levels[i] = FRIBIDI_DIR_TO_LEVEL (base_dir);
 922   }
 923
 924   /* 7. Reordering resolved levels */
 925   {
 926     register FriBidiLevel level;
 927     register FriBidiStrIndex i;
 928
 929     /* Reorder both the outstring and the order array */
 930     {
 931       if (FRIBIDI_TEST_BITS (flags, FRIBIDI_FLAG_REORDER_NSM))
 932         {
 933           /* L3. Reorder NSMs. */
 934           for (i = off + len - 1; i >= off; i--)
 935             if (FRIBIDI_LEVEL_IS_RTL (embedding_levels[i])
 936                 && bidi_types[i] == FRIBIDI_TYPE_NSM)
 937               {
 938                 register FriBidiStrIndex seq_end = i;
 939                 level = embedding_levels[i];
 940
 941                 for (i--; i >= off &&
 942                      FRIBIDI_IS_EXPLICIT_OR_BN_OR_NSM (bidi_types[i])
 943                      && embedding_levels[i] == level; i--)
 944                   ;
 945
 946                 if (i < off || embedding_levels[i] != level)
 947                   {
 948                     i++;
 949                     DBG ("warning: NSM(s) at the beggining of level run");
 950                   }
 951
 952                 if (visual_str)
 953                   {
 954                     bidi_string_reverse (visual_str + i, seq_end - i + 1);
 955                   }
 956                 if (map)
 957                   {
 958                     index_array_reverse (map + i, seq_end - i + 1);
 959                   }
 960               }
 961         }
 962
 963       /* Find max_level of the line.  We don't reuse the paragraph
 964        * max_level, both for a cleaner API, and that the line max_level
 965        * may be far less than paragraph max_level. */
 966       for (i = off + len - 1; i >= off; i--)
 967         if (embedding_levels[i] > max_level)
 968           max_level = embedding_levels[i];
 969
 970       /* L2. Reorder. */
 971       for (level = max_level; level > 0; level--)
 972         for (i = off + len - 1; i >= off; i--)
 973           if (embedding_levels[i] >= level)
 974             {
 975               /* Find all stretches that are >= level_idx */
 976               register FriBidiStrIndex seq_end = i;
 977               for (i--; i >= off && embedding_levels[i] >= level; i--)
 978                 ;
 979
 980               if (visual_str)
 981                 bidi_string_reverse (visual_str + i + 1, seq_end - i);
 982               if (map)
 983                 index_array_reverse (map + i + 1, seq_end - i);
 984             }
 985     }
 986
 987   }
 988
 989   status = true;
 990
 991 out:
 992
 993   return status ? max_level + 1 : 0;
 994 }
 995
 996 /* Editor directions:
 997  * vim:textwidth=78:tabstop=8:shiftwidth=2:autoindent:cindent
 998  */