pango/mini-fribidi/fribidi.c

   1 /* FriBidi - Library of BiDi algorithm
   2  * Copyright (C) 1999,2000 Dov Grobgeld, and
   3  * Copyright (C) 2001,2002 Behdad Esfahbod.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public License
  16  * along with this library, in a file named COPYING; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
  18  * Boston, MA 02111-1307, USA
  19  *
  20  * For licensing issues, contact <dov@imagic.weizmann.ac.il> and
  21  * <fwpg@sharif.edu>.
  22  */
  23
  24 #include "config.h"
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include "fribidi.h"
  29
  30 /* Redefine FRIBIDI_CHUNK_SIZE in config.h to override this. */
  31 #ifndef FRIBIDI_CHUNK_SIZE
  32 #ifdef MEM_OPTIMIZED
  33 #define FRIBIDI_CHUNK_SIZE 16
  34 #else
  35 #define FRIBIDI_CHUNK_SIZE 128
  36 #endif
  37 #endif
  38
  39 #define DBG(s)
  40 #define DBG2(s, t)
  41
  42 /*======================================================================
  43  * Typedef for the run-length list.
  44  *----------------------------------------------------------------------*/
  45 typedef struct _TypeLink TypeLink;
  46
  47 struct _TypeLink
  48 {
  49   TypeLink *prev;
  50   TypeLink *next;
  51
  52   FriBidiCharType type;
  53   FriBidiStrIndex pos, len;
  54   FriBidiLevel level;
  55 };
  56
  57 #define FRIBIDI_LEVEL_START   -1
  58 #define FRIBIDI_LEVEL_END     -1
  59 #define FRIBIDI_LEVEL_REMOVED -2
  60
  61 typedef struct
  62 {
  63   FriBidiCharType override;     /* only L, R and N are valid */
  64   FriBidiLevel level;
  65 }
  66 LevelInfo;
  67
  68 static TypeLink *
  69 new_type_link (void)
  70 {
  71   TypeLink *link;
  72
  73   link = g_slice_new0 (TypeLink);
  74
  75   return link;
  76 }
  77
  78 static void
  79 free_type_link (TypeLink *link)
  80 {
  81   g_slice_free (TypeLink, link);
  82 }
  83
  84 #define FRIBIDI_ADD_TYPE_LINK(p,q) \
  85         do {    \
  86                 (p)->len = (q)->pos - (p)->pos; \
  87                 (p)->next = (q);        \
  88                 (q)->prev = (p);        \
  89                 (p) = (q);      \
  90         } while (0)
  91
  92 static TypeLink *
  93 run_length_encode_types_utf8 (const char *s,
  94                               int bytelen,
  95                               FriBidiStrIndex *len,
  96                               FriBidiCharType *pored_types,
  97                               FriBidiCharType *panded_strongs)
  98 {
  99   TypeLink *list, *last, *link;
 100   FriBidiCharType char_type;
 101   FriBidiCharType ored_types = 0;
 102   FriBidiCharType anded_strongs = FRIBIDI_TYPE_RLE;
 103   FriBidiStrIndex i;
 104   const char *p;
 105
 106   /* Add the starting link */
 107   list = new_type_link ();
 108   list->type = FRIBIDI_TYPE_SOT;
 109   list->level = FRIBIDI_LEVEL_START;
 110   last = list;
 111
 112   /* Sweep over the string s */
 113   i = 0;
 114   for (p = s; p < s + bytelen; p = g_utf8_next_char(p)) {
 115     char_type = fribidi_get_type (g_utf8_get_char (p));
 116     ored_types |= char_type;
 117     if (FRIBIDI_IS_STRONG (char_type))
 118       anded_strongs &= char_type;
 119     if (char_type != last->type)
 120       {
 121         link = new_type_link ();
 122         link->type = char_type;
 123         link->pos = i;
 124         FRIBIDI_ADD_TYPE_LINK (last, link);
 125       }
 126     i++;
 127   }
 128
 129   /* Add the ending link */
 130   link = new_type_link ();
 131   link->type = FRIBIDI_TYPE_EOT;
 132   link->level = FRIBIDI_LEVEL_END;
 133   link->pos = i;
 134   FRIBIDI_ADD_TYPE_LINK (last, link);
 135
 136   if (len)
 137     *len = i;
 138
 139   if (pored_types)
 140     *pored_types = ored_types;
 141   if (panded_strongs)
 142     *panded_strongs = anded_strongs;
 143
 144   return list;
 145 }
 146
 147 /* explicits_list is a list like type_rl_list, that holds the explicit
 148    codes that are removed from rl_list, to reinsert them later by calling
 149    the override_list.
 150 */
 151 static void
 152 init_list (TypeLink **start,
 153            TypeLink **end)
 154 {
 155   TypeLink *list;
 156   TypeLink *link;
 157
 158   /* Add the starting link */
 159   list = new_type_link ();
 160   list->type = FRIBIDI_TYPE_SOT;
 161   list->level = FRIBIDI_LEVEL_START;
 162   list->len = 0;
 163   list->pos = 0;
 164
 165   /* Add the ending link */
 166   link = new_type_link ();
 167   link->type = FRIBIDI_TYPE_EOT;
 168   link->level = FRIBIDI_LEVEL_END;
 169   link->len = 0;
 170   link->pos = 0;
 171   list->next = link;
 172   link->prev = list;
 173
 174   *start = list;
 175   *end = link;
 176 }
 177
 178 /* move an element before another element in a list, the list must have a
 179    previous element, used to update explicits_list.
 180    assuming that p have both prev and next or none of them, also update
 181    the list that p is currently in, if any.
 182 */
 183 static void
 184 move_element_before (TypeLink *p,
 185                      TypeLink *list)
 186 {
 187   if (p->prev)
 188     {
 189       p->prev->next = p->next;
 190       p->next->prev = p->prev;
 191     }
 192   p->prev = list->prev;
 193   list->prev->next = p;
 194   p->next = list;
 195   list->prev = p;
 196 }
 197
 198 /* override the rl_list 'base', with the elements in the list 'over', to
 199    reinsert the previously-removed explicit codes (at X9) from
 200    'explicits_list' back into 'type_rl_list'. This is used at the end of I2
 201    to restore the explicit marks, and also to reset the character types of
 202    characters at L1.
 203
 204    it is assumed that the 'pos' of the first element in 'base' list is not
 205    more than the 'pos' of the first element of the 'over' list, and the
 206    'pos' of the last element of the 'base' list is not less than the 'pos'
 207    of the last element of the 'over' list. these two conditions are always
 208    satisfied for the two usages mentioned above.
 209
 210    TBD: use some explanatory names instead of p, q, ...
 211 */
 212 static void
 213 override_list (TypeLink *base,
 214                TypeLink *over)
 215 {
 216   TypeLink *p = base, *q, *r, *s, *t;
 217   FriBidiStrIndex pos = 0, pos2;
 218
 219   if (!over)
 220     return;
 221   q = over;
 222   while (q)
 223     {
 224       if (!q->len || q->pos < pos)
 225         {
 226           t = q;
 227           q = q->next;
 228           free_type_link (t);
 229           continue;
 230         }
 231       pos = q->pos;
 232       while (p->next && p->next->pos <= pos)
 233         p = p->next;
 234       /* now p is the element that q must be inserted 'in'. */
 235       pos2 = pos + q->len;
 236       r = p;
 237       while (r->next && r->next->pos < pos2)
 238         r = r->next;
 239       /* now r is the last element that q affects. */
 240       if (p == r)
 241         {
 242           /* split p into at most 3 interval, and insert q in the place of
 243              the second interval, set r to be the third part. */
 244           /* third part needed? */
 245           if (p->next && p->next->pos == pos2)
 246             r = r->next;
 247           else
 248             {
 249               r = new_type_link ();
 250               *r = *p;
 251               if (r->next)
 252                 {
 253                   r->next->prev = r;
 254                   r->len = r->next->pos - pos2;
 255                 }
 256               else
 257                 r->len -= pos - p->pos;
 258               r->pos = pos2;
 259             }
 260           /* first part needed? */
 261           if (p->prev && p->pos == pos)
 262             {
 263               t = p;
 264               p = p->prev;
 265               free_type_link (t);
 266             }
 267           else
 268             p->len = pos - p->pos;
 269         }
 270       else
 271         {
 272           /* cut the end of p. */
 273           p->len = pos - p->pos;
 274           /* if all of p is cut, remove it. */
 275           if (!p->len && p->prev)
 276             p = p->prev;
 277
 278           /* cut the begining of r. */
 279           r->pos = pos2;
 280           if (r->next)
 281             r->len = r->next->pos - pos2;
 282           /* if all of r is cut, remove it. */
 283           if (!r->len && r->next)
 284             r = r->next;
 285
 286           /* remove the elements between p and r. */
 287           for (s = p->next; s != r;)
 288             {
 289               t = s;
 290               s = s->next;
 291               free_type_link (t);
 292             }
 293         }
 294       /* before updating the next and prev links to point to the inserted q,
 295          we must remember the next element of q in the 'over' list.
 296        */
 297       t = q;
 298       q = q->next;
 299       p->next = t;
 300       t->prev = p;
 301       t->next = r;
 302       r->prev = t;
 303     }
 304 }
 305
 306 /* Some convenience macros */
 307 #define RL_TYPE(list) ((list)->type)
 308 #define RL_LEN(list) ((list)->len)
 309 #define RL_POS(list) ((list)->pos)
 310 #define RL_LEVEL(list) ((list)->level)
 311
 312 static TypeLink *
 313 merge_with_prev (TypeLink *second)
 314 {
 315   TypeLink *first = second->prev;
 316   first->next = second->next;
 317   first->next->prev = first;
 318   RL_LEN (first) += RL_LEN (second);
 319   free_type_link (second);
 320   return first;
 321 }
 322
 323 static void
 324 compact_list (TypeLink *list)
 325 {
 326   if (list->next)
 327     for (list = list->next; list; list = list->next)
 328       if (RL_TYPE (list->prev) == RL_TYPE (list)
 329           && RL_LEVEL (list->prev) == RL_LEVEL (list))
 330         list = merge_with_prev (list);
 331 }
 332
 333 static void
 334 compact_neutrals (TypeLink *list)
 335 {
 336   if (list->next)
 337     {
 338       for (list = list->next; list; list = list->next)
 339         {
 340           if (RL_LEVEL (list->prev) == RL_LEVEL (list)
 341               &&
 342               ((RL_TYPE
 343                 (list->prev) == RL_TYPE (list)
 344                 || (FRIBIDI_IS_NEUTRAL (RL_TYPE (list->prev))
 345                     && FRIBIDI_IS_NEUTRAL (RL_TYPE (list))))))
 346             list = merge_with_prev (list);
 347         }
 348     }
 349 }
 350
 351 /*======================================================================
 352  *  Frees up the rl_list, must be called after each call to
 353  *  fribidi_analyse_string(), after the list is not needed anymore.
 354  *----------------------------------------------------------------------*/
 355 static void
 356 free_rl_list (TypeLink *type_rl_list)
 357 {
 358   DBG ("Entering free_rl_list()\n");
 359
 360   if (!type_rl_list)
 361     {
 362       DBG ("Leaving free_rl_list()\n");
 363       return;
 364     }
 365
 366   g_slice_free_chain (TypeLink, type_rl_list, next);
 367
 368   DBG ("Leaving free_rl_list()\n");
 369   return;
 370 }
 371
 372 /*=========================================================================
 373  * define macros for push and pop the status in to / out of the stack
 374  *-------------------------------------------------------------------------*/
 375
 376 /* There's some little points in pushing and poping into the status stack:
 377    1. when the embedding level is not valid (more than UNI_MAX_BIDI_LEVEL=61),
 378    you must reject it, and not to push into the stack, but when you see a
 379    PDF, you must find the matching code, and if it was pushed in the stack,
 380    pop it, it means you must pop if and only if you have pushed the
 381    matching code, the over_pushed var counts the number of rejected codes yet.
 382    2. there's a more confusing point too, when the embedding level is exactly
 383    UNI_MAX_BIDI_LEVEL-1=60, an LRO or LRE must be rejected because the new
 384    level would be UNI_MAX_BIDI_LEVEL+1=62, that is invalid, but an RLO or RLE
 385    must be accepted because the new level is UNI_MAX_BIDI_LEVEL=61, that is
 386    valid, so the rejected codes may be not continuous in the logical order,
 387    in fact there is at most two continuous intervals of codes, with a RLO or
 388    RLE between them.  To support this case, the first_interval var counts the
 389    number of rejected codes in the first interval, when it is 0, means that
 390    there is only one interval yet.
 391 */
 392
 393 /* a. If this new level would be valid, then this embedding code is valid.
 394    Remember (push) the current embedding level and override status.
 395    Reset current level to this new level, and reset the override status to
 396    new_override.
 397    b. If the new level would not be valid, then this code is invalid. Don't
 398    change the current level or override status.
 399 */
 400 #define PUSH_STATUS \
 401     do { \
 402       if (new_level <= UNI_MAX_BIDI_LEVEL) \
 403         { \
 404           if (level == UNI_MAX_BIDI_LEVEL - 1) \
 405             first_interval = over_pushed; \
 406           status_stack[stack_size].level = level; \
 407           status_stack[stack_size].override = override; \
 408           stack_size++; \
 409           level = new_level; \
 410           override = new_override; \
 411         } else \
 412           over_pushed++; \
 413     } while (0)
 414
 415 /* If there was a valid matching code, restore (pop) the last remembered
 416    (pushed) embedding level and directional override.
 417 */
 418 #define POP_STATUS \
 419     do { \
 420       if (over_pushed || stack_size) \
 421       { \
 422         if (over_pushed > first_interval) \
 423           over_pushed--; \
 424         else \
 425           { \
 426             if (over_pushed == first_interval) \
 427               first_interval = 0; \
 428             stack_size--; \
 429             level = status_stack[stack_size].level; \
 430             override = status_stack[stack_size].override; \
 431           } \
 432       } \
 433     } while (0)
 434
 435 /*==========================================================================
 436  * There was no support for sor and eor in the absence of Explicit Embedding
 437  * Levels, so define macros, to support them, with as less change as needed.
 438  *--------------------------------------------------------------------------*/
 439
 440 /* Return the type of previous char or the sor, if already at the start of
 441    a run level. */
 442 #define PREV_TYPE_OR_SOR(pp) \
 443     ( \
 444      RL_LEVEL(pp->prev) == RL_LEVEL(pp) ? \
 445       RL_TYPE(pp->prev) : \
 446       FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->prev), RL_LEVEL(pp))) \
 447     )
 448
 449 /* Return the type of next char or the eor, if already at the end of
 450    a run level. */
 451 #define NEXT_TYPE_OR_EOR(pp) \
 452     ( \
 453      !pp->next ? \
 454       FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(pp)) : \
 455       (RL_LEVEL(pp->next) == RL_LEVEL(pp) ? \
 456         RL_TYPE(pp->next) : \
 457         FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->next), RL_LEVEL(pp))) \
 458       ) \
 459     )
 460
 461
 462 /* Return the embedding direction of a link. */
 463 #define FRIBIDI_EMBEDDING_DIRECTION(list) \
 464     FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(list))
 465
 466
 467 /*======================================================================
 468  *  This function should follow the Unicode specification closely!
 469  *----------------------------------------------------------------------*/
 470 static fribidi_boolean
 471 fribidi_analyse_string_utf8 (   /* input */
 472                          const char *str,
 473                          int bytelen,
 474                          FriBidiCharType *pbase_dir,
 475                          /* output */
 476                          FriBidiStrIndex *len,
 477                          TypeLink **ptype_rl_list,
 478                          FriBidiLevel *pmax_level)
 479 {
 480   FriBidiLevel base_level, max_level;
 481   FriBidiCharType base_dir;
 482   TypeLink *type_rl_list, *explicits_list, *explicits_list_end, *pp;
 483
 484   DBG ("Entering fribidi_analyse_string()\n");
 485
 486   /* Determinate character types */
 487   DBG ("  Determine character types\n");
 488   {
 489     FriBidiCharType ored_types;
 490     FriBidiCharType anded_strongs;
 491
 492     /* Run length encode the character types */
 493     type_rl_list = run_length_encode_types_utf8 (str, bytelen, len,
 494                                                  &ored_types, &anded_strongs);
 495
 496     /* The case that all resolved levels will be ltr.
 497      * First, all strongs should be ltr, and one of the following:
 498      *
 499      *  o *pbase_dir doesn't have an rtl taste.
 500      *  o there are letters, and *pbase_dir is weak.
 501      */
 502     if (!FRIBIDI_IS_RTL (ored_types) &&
 503              (!FRIBIDI_IS_RTL (*pbase_dir) ||
 504               (FRIBIDI_IS_WEAK (*pbase_dir) && FRIBIDI_IS_LETTER (ored_types))
 505              ))
 506       {
 507         /* all ltr */
 508         free_rl_list (type_rl_list);
 509
 510         *ptype_rl_list = NULL;
 511         *pmax_level = 0;
 512         *pbase_dir = FRIBIDI_TYPE_LTR;
 513
 514         return 0;
 515       }
 516     /* The case that all resolved levels will be rtl is much more complex.
 517      * First, there should be no numbers, all strongs be rtl, and one of
 518      * the following:
 519      *
 520      *  o *pbase_dir has an rtl taste (may be weak).
 521      *  o there are letters, and *pbase_dir is weak.
 522      */
 523     else if (!FRIBIDI_IS_NUMBER (ored_types) && FRIBIDI_IS_RTL (anded_strongs) &&
 524              (FRIBIDI_IS_RTL (*pbase_dir) ||
 525               (FRIBIDI_IS_WEAK (*pbase_dir) && FRIBIDI_IS_LETTER (ored_types))
 526              ))
 527       {
 528         free_rl_list (type_rl_list);
 529
 530         *ptype_rl_list = NULL;
 531         *pmax_level = 1;
 532         *pbase_dir = FRIBIDI_TYPE_RTL;
 533
 534         return 0;
 535       }
 536   }
 537   DBG ("  Determine character types, Done\n");
 538
 539   init_list (&explicits_list, &explicits_list_end);
 540
 541   /* Find base level */
 542   DBG ("  Finding the base level\n");
 543   if (FRIBIDI_IS_STRONG (*pbase_dir))
 544     base_level = FRIBIDI_DIR_TO_LEVEL (*pbase_dir);
 545   /* P2. P3. Search for first strong character and use its direction as
 546      base direction */
 547   else
 548     {
 549       /* If no strong base_dir was found, resort to the weak direction
 550          that was passed on input. */
 551       base_level = FRIBIDI_DIR_TO_LEVEL (*pbase_dir);
 552       base_dir = FRIBIDI_TYPE_ON;
 553       for (pp = type_rl_list; pp; pp = pp->next)
 554         if (FRIBIDI_IS_LETTER (RL_TYPE (pp)))
 555           {
 556             base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (pp));
 557             base_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 558             break;
 559           }
 560     }
 561   base_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 562   DBG2 ("  Base level : %c\n", fribidi_char_from_level (base_level));
 563   DBG2 ("  Base dir   : %c\n", fribidi_char_from_type (base_dir));
 564   DBG ("  Finding the base level, Done\n");
 565
 566   /* Explicit Levels and Directions */
 567   DBG ("Explicit Levels and Directions\n");
 568   {
 569     /* X1. Begin by setting the current embedding level to the paragraph
 570        embedding level. Set the directional override status to neutral.
 571        Process each character iteratively, applying rules X2 through X9.
 572        Only embedding levels from 0 to 61 are valid in this phase. */
 573     FriBidiLevel level, new_level;
 574     FriBidiCharType override, new_override;
 575     FriBidiStrIndex i;
 576     int stack_size, over_pushed, first_interval;
 577     LevelInfo *status_stack;
 578     TypeLink temp_link;
 579
 580     level = base_level;
 581     override = FRIBIDI_TYPE_ON;
 582     /* stack */
 583     stack_size = 0;
 584     over_pushed = 0;
 585     first_interval = 0;
 586     status_stack =
 587       (LevelInfo *) malloc (sizeof (LevelInfo) * (UNI_MAX_BIDI_LEVEL + 2));
 588
 589     for (pp = type_rl_list->next; pp->next; pp = pp->next)
 590       {
 591         FriBidiCharType this_type = RL_TYPE (pp);
 592         if (FRIBIDI_IS_EXPLICIT_OR_BN (this_type))
 593           {
 594             if (FRIBIDI_IS_STRONG (this_type))
 595               {                 /* LRE, RLE, LRO, RLO */
 596                 /* 1. Explicit Embeddings */
 597                 /*   X2. With each RLE, compute the least greater odd embedding level. */
 598                 /*   X3. With each LRE, compute the least greater even embedding level. */
 599                 /* 2. Explicit Overrides */
 600                 /*   X4. With each RLO, compute the least greater odd embedding level. */
 601                 /*   X5. With each LRO, compute the least greater even embedding level. */
 602                 new_override = FRIBIDI_EXPLICIT_TO_OVERRIDE_DIR (this_type);
 603                 for (i = 0; i < RL_LEN (pp); i++)
 604                   {
 605                     new_level =
 606                       ((level + FRIBIDI_DIR_TO_LEVEL (this_type) + 2) & ~1) -
 607                       FRIBIDI_DIR_TO_LEVEL (this_type);
 608                     PUSH_STATUS;
 609                   }
 610               }
 611             else if (this_type == FRIBIDI_TYPE_PDF)
 612               {
 613                 /* 3. Terminating Embeddings and overrides */
 614                 /*   X7. With each PDF, determine the matching embedding or
 615                    override code. */
 616                 for (i = 0; i < RL_LEN (pp); i++)
 617                   POP_STATUS;
 618               }
 619             /* X9. Remove all RLE, LRE, RLO, LRO, PDF, and BN codes. */
 620             /* Remove element and add it to explicits_list */
 621             temp_link.next = pp->next;
 622             pp->level = FRIBIDI_LEVEL_REMOVED;
 623             move_element_before (pp, explicits_list_end);
 624             pp = &temp_link;
 625           }
 626         else
 627           {
 628             /* X6. For all typed besides RLE, LRE, RLO, LRO, and PDF:
 629                a. Set the level of the current character to the current
 630                embedding level.
 631                b. Whenever the directional override status is not neutral,
 632                reset the current character type to the directional override
 633                status. */
 634             RL_LEVEL (pp) = level;
 635             if (!FRIBIDI_IS_NEUTRAL (override))
 636               RL_TYPE (pp) = override;
 637           }
 638         /* X8. All explicit directional embeddings and overrides are
 639            completely terminated at the end of each paragraph. Paragraph
 640            separators are not included in the embedding. */
 641         /* This function is running on a single paragraph, so we can do
 642            X8 after all the input is processed. */
 643       }
 644
 645     /* Implementing X8. It has no effect on a single paragraph! */
 646     level = base_level;
 647     override = FRIBIDI_TYPE_ON;
 648     stack_size = 0;
 649     over_pushed = 0;
 650
 651     free (status_stack);
 652   }
 653   /* X10. The remaining rules are applied to each run of characters at the
 654      same level. For each run, determine the start-of-level-run (sor) and
 655      end-of-level-run (eor) type, either L or R. This depends on the
 656      higher of the two levels on either side of the boundary (at the start
 657      or end of the paragraph, the level of the 'other' run is the base
 658      embedding level). If the higher level is odd, the type is R, otherwise
 659      it is L. */
 660   /* Resolving Implicit Levels can be done out of X10 loop, so only change
 661      of Resolving Weak Types and Resolving Neutral Types is needed. */
 662
 663   compact_list (type_rl_list);
 664
 665   /* 4. Resolving weak types */
 666   DBG ("Resolving weak types\n");
 667   {
 668     FriBidiCharType last_strong, prev_type_org;
 669     fribidi_boolean w4;
 670
 671     last_strong = base_dir;
 672
 673     for (pp = type_rl_list->next; pp->next; pp = pp->next)
 674       {
 675         FriBidiCharType prev_type, this_type, next_type;
 676
 677         prev_type = PREV_TYPE_OR_SOR (pp);
 678         this_type = RL_TYPE (pp);
 679         next_type = NEXT_TYPE_OR_EOR (pp);
 680
 681         if (FRIBIDI_IS_STRONG (prev_type))
 682           last_strong = prev_type;
 683
 684         /* W1. NSM
 685            Examine each non-spacing mark (NSM) in the level run, and change the
 686            type of the NSM to the type of the previous character. If the NSM
 687            is at the start of the level run, it will get the type of sor. */
 688         /* Implementation note: it is important that if the previous character
 689            is not sor, then we should merge this run with the previous,
 690            because of rules like W5, that we assume all of a sequence of
 691            adjacent ETs are in one TypeLink. */
 692         if (this_type == FRIBIDI_TYPE_NSM)
 693           {
 694             if (RL_LEVEL (pp->prev) == RL_LEVEL (pp))
 695               pp = merge_with_prev (pp);
 696             else
 697               RL_TYPE (pp) = prev_type;
 698             continue;           /* As we know the next condition cannot be true. */
 699           }
 700
 701         /* W2: European numbers. */
 702         if (this_type == FRIBIDI_TYPE_EN && last_strong == FRIBIDI_TYPE_AL)
 703           {
 704             RL_TYPE (pp) = FRIBIDI_TYPE_AN;
 705
 706             /* Resolving dependency of loops for rules W1 and W2, so we
 707                can merge them in one loop. */
 708             if (next_type == FRIBIDI_TYPE_NSM)
 709               RL_TYPE (pp->next) = FRIBIDI_TYPE_AN;
 710           }
 711       }
 712
 713
 714     last_strong = base_dir;
 715     /* Resolving dependency of loops for rules W4 and W5, W5 may
 716        want to prevent W4 to take effect in the next turn, do this
 717        through "w4". */
 718     w4 = FRIBIDI_TRUE;
 719     /* Resolving dependency of loops for rules W4 and W5 with W7,
 720        W7 may change an EN to L but it sets the prev_type_org if needed,
 721        so W4 and W5 in next turn can still do their works. */
 722     prev_type_org = FRIBIDI_TYPE_ON;
 723
 724     for (pp = type_rl_list->next; pp->next; pp = pp->next)
 725       {
 726         FriBidiCharType prev_type, this_type, next_type;
 727
 728         prev_type = PREV_TYPE_OR_SOR (pp);
 729         this_type = RL_TYPE (pp);
 730         next_type = NEXT_TYPE_OR_EOR (pp);
 731
 732         if (FRIBIDI_IS_STRONG (prev_type))
 733           last_strong = prev_type;
 734
 735         /* W3: Change ALs to R. */
 736         if (this_type == FRIBIDI_TYPE_AL)
 737           {
 738             RL_TYPE (pp) = FRIBIDI_TYPE_RTL;
 739             w4 = FRIBIDI_TRUE;
 740             prev_type_org = FRIBIDI_TYPE_ON;
 741             continue;
 742           }
 743
 744         /* W4. A single european separator changes to a european number.
 745            A single common separator between two numbers of the same type
 746            changes to that type. */
 747         if (w4
 748             && RL_LEN (pp) == 1 && FRIBIDI_IS_ES_OR_CS (this_type)
 749             && FRIBIDI_IS_NUMBER (prev_type_org) && prev_type_org == next_type
 750             && (prev_type_org == FRIBIDI_TYPE_EN
 751                 || this_type == FRIBIDI_TYPE_CS))
 752           {
 753             RL_TYPE (pp) = prev_type;
 754             this_type = RL_TYPE (pp);
 755           }
 756         w4 = FRIBIDI_TRUE;
 757
 758         /* W5. A sequence of European terminators adjacent to European
 759            numbers changes to All European numbers. */
 760         if (this_type == FRIBIDI_TYPE_ET
 761             && (prev_type_org == FRIBIDI_TYPE_EN
 762                 || next_type == FRIBIDI_TYPE_EN))
 763           {
 764             RL_TYPE (pp) = FRIBIDI_TYPE_EN;
 765             w4 = FRIBIDI_FALSE;
 766             this_type = RL_TYPE (pp);
 767           }
 768
 769         /* W6. Otherwise change separators and terminators to other neutral. */
 770         if (FRIBIDI_IS_NUMBER_SEPARATOR_OR_TERMINATOR (this_type))
 771           RL_TYPE (pp) = FRIBIDI_TYPE_ON;
 772
 773         /* W7. Change european numbers to L. */
 774         if (this_type == FRIBIDI_TYPE_EN && last_strong == FRIBIDI_TYPE_LTR)
 775           {
 776             RL_TYPE (pp) = FRIBIDI_TYPE_LTR;
 777             prev_type_org = (RL_LEVEL (pp) == RL_LEVEL (pp->next) ?
 778                              FRIBIDI_TYPE_EN : FRIBIDI_TYPE_ON);
 779           }
 780         else
 781           prev_type_org = PREV_TYPE_OR_SOR (pp->next);
 782       }
 783   }
 784
 785   compact_neutrals (type_rl_list);
 786
 787   /* 5. Resolving Neutral Types */
 788   DBG ("Resolving neutral types\n");
 789   {
 790     /* N1. and N2.
 791        For each neutral, resolve it. */
 792     for (pp = type_rl_list->next; pp->next; pp = pp->next)
 793       {
 794         FriBidiCharType prev_type, this_type, next_type;
 795
 796         /* "European and arabic numbers are treated as though they were R"
 797            FRIBIDI_CHANGE_NUMBER_TO_RTL does this. */
 798         this_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE (pp));
 799         prev_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (PREV_TYPE_OR_SOR (pp));
 800         next_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (NEXT_TYPE_OR_EOR (pp));
 801
 802         if (FRIBIDI_IS_NEUTRAL (this_type))
 803           RL_TYPE (pp) = (prev_type == next_type) ?
 804             /* N1. */ prev_type :
 805             /* N2. */ FRIBIDI_EMBEDDING_DIRECTION (pp);
 806       }
 807   }
 808
 809   compact_list (type_rl_list);
 810
 811   /* 6. Resolving implicit levels */
 812   DBG ("Resolving implicit levels\n");
 813   {
 814     max_level = base_level;
 815
 816     for (pp = type_rl_list->next; pp->next; pp = pp->next)
 817       {
 818         FriBidiCharType this_type;
 819         int level;
 820
 821         this_type = RL_TYPE (pp);
 822         level = RL_LEVEL (pp);
 823
 824         /* I1. Even */
 825         /* I2. Odd */
 826         if (FRIBIDI_IS_NUMBER (this_type))
 827           RL_LEVEL (pp) = (level + 2) & ~1;
 828         else
 829           RL_LEVEL (pp) = (level ^ FRIBIDI_DIR_TO_LEVEL (this_type)) +
 830             (level & 1);
 831
 832         if (RL_LEVEL (pp) > max_level)
 833           max_level = RL_LEVEL (pp);
 834       }
 835   }
 836
 837   compact_list (type_rl_list);
 838
 839 /* Reinsert the explicit codes & bn's that already removed, from the
 840    explicits_list to type_rl_list. */
 841   DBG ("Reinserting explicit codes\n");
 842   {
 843     TypeLink *p;
 844
 845     override_list (type_rl_list, explicits_list);
 846     p = type_rl_list->next;
 847     if (p->level < 0)
 848       p->level = base_level;
 849     for (; p->next; p = p->next)
 850       if (p->level < 0)
 851         p->level = p->prev->level;
 852   }
 853
 854   DBG ("Reset the embedding levels\n");
 855   {
 856     int j, k, state, pos;
 857     TypeLink *p, *q, *list, *list_end;
 858
 859     const char *strp = str + bytelen;
 860
 861     /* L1. Reset the embedding levels of some chars. */
 862     init_list (&list, &list_end);
 863     q = list_end;
 864     state = 1;
 865     pos = *len - 1;
 866     for (j = *len - 1; j >= -1; j--)
 867       {
 868         /* if state is on at the very first of string, do this too. */
 869         if (j >= 0)
 870           k = fribidi_get_type (g_utf8_get_char (strp = g_utf8_prev_char (strp)));
 871         else
 872           k = FRIBIDI_TYPE_ON;
 873         if (!state && FRIBIDI_IS_SEPARATOR (k))
 874           {
 875             state = 1;
 876             pos = j;
 877           }
 878         else if (state && !FRIBIDI_IS_EXPLICIT_OR_SEPARATOR_OR_BN_OR_WS (k))
 879           {
 880             state = 0;
 881             p = new_type_link ();
 882             p->prev = p->next = NULL;
 883             p->pos = j + 1;
 884             p->len = pos - j;
 885             p->type = base_dir;
 886             p->level = base_level;
 887             move_element_before (p, q);
 888             q = p;
 889           }
 890       }
 891     override_list (type_rl_list, list);
 892   }
 893
 894   *ptype_rl_list = type_rl_list;
 895   *pmax_level = max_level;
 896   *pbase_dir = base_dir;
 897
 898   DBG ("Leaving fribidi_analyse_string()\n");
 899   return 1;
 900 }
 901
 902 /*======================================================================
 903  *  fribidi_log2vis_get_embedding_levels() is used in order to just get
 904  *  the embedding levels.
 905  *----------------------------------------------------------------------*/
 906 FRIBIDI_API FriBidiLevel *
 907 fribidi_log2vis_get_embedding_levels_new_utf8 ( /* input */
 908                                        const char *str,
 909                                        int bytelen,
 910                                        FriBidiCharType *pbase_dir)
 911 {
 912   TypeLink *type_rl_list, *pp;
 913   FriBidiLevel max_level, *embedding_level_list;
 914   FriBidiStrIndex len;
 915
 916   DBG ("Entering fribidi_log2vis_get_embedding_levels()\n");
 917
 918   if (bytelen == 0)
 919     {
 920       DBG ("Leaving fribidi_log2vis_get_embedding_levels()\n");
 921       return NULL;
 922     }
 923
 924   if (!fribidi_analyse_string_utf8 (str, bytelen, pbase_dir,
 925                           /* output */
 926                           &len, &type_rl_list, &max_level))
 927     {
 928      /* unidirectional.  return all-zero or all-one embedding levels */
 929
 930      if (max_level)
 931        {
 932          embedding_level_list = g_new (FriBidiLevel, len);
 933          /* assumes sizeof(FriBidiLevel) == 1, which is true! */
 934          memset (embedding_level_list, max_level, len);
 935          return embedding_level_list;
 936        }
 937      else
 938        {
 939          return g_new0 (FriBidiLevel, len);
 940        }
 941     }
 942
 943   embedding_level_list = g_new (FriBidiLevel, len);
 944   for (pp = type_rl_list->next; pp->next; pp = pp->next)
 945     {
 946       FriBidiStrIndex i, pos = RL_POS (pp), len = RL_LEN (pp);
 947       FriBidiLevel level = RL_LEVEL (pp);
 948       for (i = 0; i < len; i++)
 949         embedding_level_list[pos + i] = level;
 950     }
 951
 952   free_rl_list (type_rl_list);
 953
 954   DBG ("Leaving fribidi_log2vis_get_embedding_levels()\n");
 955   return embedding_level_list;
 956 }
 957