2 * fribidi-bidi.c - bidirectional algorithm
5 * Behdad Esfahbod, 2001, 2002, 2004
6 * Dov Grobgeld, 1999, 2000, 2017
8 * Copyright (C) 2004 Sharif FarsiWeb, Inc
9 * Copyright (C) 2001,2002 Behdad Esfahbod
10 * Copyright (C) 1999,2000,2017 Dov Grobgeld
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.
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.
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
27 * For licensing issues, contact <fribidi.license@gmail.com>.
32 #include <fribidi-bidi.h>
33 #include <fribidi-mirroring.h>
34 #include <fribidi-brackets.h>
35 #include <fribidi-unicode.h>
37 #include "bidi-types.h"
41 * This file implements most of Unicode Standard Annex #9, Tracking Number 13.
45 # define MAX(a,b) ((a) > (b) ? (a) : (b))
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)
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)
59 /* Pairing nodes are used for holding a pair of open/close brackets as
61 struct _FriBidiPairingNodeStruct {
64 struct _FriBidiPairingNodeStruct *next;
66 typedef struct _FriBidiPairingNodeStruct FriBidiPairingNode;
75 fribidi_assert (second);
76 fribidi_assert (second->next);
78 fribidi_assert (first);
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;
87 fribidi_free (second);
96 fribidi_assert (list);
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
105 list = merge_with_prev (list);
113 fribidi_assert (list);
117 for_run_list (list, list)
119 if (RL_LEVEL (list->prev) == RL_LEVEL (list)
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
127 list = merge_with_prev (list);
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.
136 /* The static sentinel is used to signal the end of an isolating
138 static FriBidiRun sentinel = { NULL, NULL, 0,0, FRIBIDI_TYPE_SENTINEL, -1,-1,FRIBIDI_NO_BRACKET, NULL, NULL };
140 static FriBidiRun *get_adjacent_run(FriBidiRun *list, fribidi_boolean forward, fribidi_boolean skip_neutral)
142 FriBidiRun *ppp = forward ? list->next_isolate : list->prev_isolate;
148 FriBidiCharType ppp_type = RL_TYPE (ppp);
150 if (ppp_type == _FRIBIDI_TYPE_SENTINEL)
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)))
161 ppp = forward ? ppp->next_isolate : ppp->prev_isolate;
174 /*======================================================================
175 * For debugging, define some functions for printing the types and the
177 *----------------------------------------------------------------------*/
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',
192 /* TBD - insert another 125-64 levels */
194 '@', /* 62 == only must appear after resolving
197 '!', /* 63 == FRIBIDI_LEVEL_INVALID, internal error,
198 * this level shouldn't be seen. */
200 '*', '*', '*', '*', '*' /* >= 64 == overflows, this levels and higher
201 * levels show a real bug!. */
204 #define fribidi_char_from_level(level) char_from_level_array[(level) + 1]
213 MSG (" Run types : ");
214 for_run_list (pp, pp)
216 MSG6 ("%d:%d(%s)[%d,%d] ",
217 pp->pos, pp->len, fribidi_get_bidi_type_name (pp->type), pp->level, pp->isolate_level);
223 print_resolved_levels (
229 MSG (" Res. levels: ");
230 for_run_list (pp, pp)
232 register FriBidiStrIndex i;
233 for (i = RL_LEN (pp); i; i--)
234 MSG2 ("%c", fribidi_char_from_level (RL_LEVEL (pp)));
240 print_resolved_types (
246 MSG (" Res. types : ");
247 for_run_list (pp, pp)
250 for (i = RL_LEN (pp); i; i--)
251 MSG2 ("%c", fribidi_char_from_bidi_type (pp->type));
259 const FriBidiCharType *bidi_types,
260 const FriBidiStrIndex len
263 register FriBidiStrIndex i;
265 fribidi_assert (bidi_types);
267 MSG (" Org. types : ");
268 for (i = 0; i < len; i++)
269 MSG2 ("%c", fribidi_char_from_bidi_type (bidi_types[i]));
273 static void print_pairing_nodes(FriBidiPairingNode *nodes)
278 MSG3 ("(%d, %d) ", nodes->open->pos, nodes->close->pos);
286 /*=========================================================================
287 * define macros for push and pop the status in to / out of the stack
288 *-------------------------------------------------------------------------*/
290 /* There are a few little points in pushing into and poping from the status
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.
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
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
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.
319 #define PUSH_STATUS \
321 if LIKELY(over_pushed == 0 \
322 && isolate_overflow == 0 \
323 && new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL) \
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; \
333 override = new_override; \
334 } else if LIKELY(isolate_overflow == 0) \
338 /* If there was a valid matching code, restore (pop) the last remembered
339 (pushed) embedding level and directional override.
345 if UNLIKELY(over_pushed > first_interval) \
349 if LIKELY(over_pushed == first_interval) \
350 first_interval = 0; \
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; \
361 /* Return the type of previous run or the SOR, if already at the start of
363 #define PREV_TYPE_OR_SOR(pp) \
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))) \
370 /* Return the type of next run or the EOR, if already at the end of
372 #define NEXT_TYPE_OR_EOR(pp) \
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))) \
380 /* Return the embedding direction of a link. */
381 #define FRIBIDI_EMBEDDING_DIRECTION(link) \
382 FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(link))
385 FRIBIDI_ENTRY FriBidiParType
386 fribidi_get_par_direction (
388 const FriBidiCharType *bidi_types,
389 const FriBidiStrIndex len
392 register FriBidiStrIndex i;
394 fribidi_assert (bidi_types);
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 :
401 return FRIBIDI_PAR_ON;
404 /* Push a new entry to the pairing linked list */
405 static FriBidiPairingNode * pairing_nodes_push(FriBidiPairingNode *nodes,
409 FriBidiPairingNode *node = fribidi_malloc(sizeof(FriBidiPairingNode));
417 /* Sort by merge sort */
418 static void pairing_nodes_front_back_split(FriBidiPairingNode *source,
420 FriBidiPairingNode **front,
421 FriBidiPairingNode **back)
423 FriBidiPairingNode *pfast, *pslow;
424 if (!source || !source->next)
432 pfast = source->next;
448 static FriBidiPairingNode *
449 pairing_nodes_sorted_merge(FriBidiPairingNode *nodes1,
450 FriBidiPairingNode *nodes2)
452 FriBidiPairingNode *res = NULL;
458 if (nodes1->open->pos < nodes2->open->pos)
461 res->next = pairing_nodes_sorted_merge(nodes1->next, nodes2);
466 res->next = pairing_nodes_sorted_merge(nodes1, nodes2->next);
471 static void sort_pairing_nodes(FriBidiPairingNode **nodes)
473 FriBidiPairingNode *front, *back;
475 /* 0 or 1 node case */
476 if (!*nodes || !(*nodes)->next)
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);
485 static void free_pairing_nodes(FriBidiPairingNode *nodes)
489 FriBidiPairingNode *p = nodes;
495 FRIBIDI_ENTRY FriBidiLevel
496 fribidi_get_par_embedding_levels_ex (
498 const FriBidiCharType *bidi_types,
499 const FriBidiBracketType *bracket_types,
500 const FriBidiStrIndex len,
501 /* input and output */
502 FriBidiParType *pbase_dir,
504 FriBidiLevel *embedding_levels
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;
520 DBG ("in fribidi_get_par_embedding_levels");
522 fribidi_assert (bidi_types);
523 fribidi_assert (pbase_dir);
524 fribidi_assert (embedding_levels);
526 /* Determinate character types */
528 /* Get run-length encoded character types */
529 main_run_list = run_list_encode_bidi_types (bidi_types, bracket_types, len);
531 (!main_run_list) goto out;
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
542 int valid_isolate_count = 0;
543 for_run_list (pp, main_run_list)
545 if (RL_TYPE(pp) == FRIBIDI_TYPE_PDI)
547 /* Ignore if there is no matching isolate */
548 if (valid_isolate_count>0)
549 valid_isolate_count--;
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)))
555 base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (pp));
556 *pbase_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
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));
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;
571 (fribidi_debug_status ())
573 print_types_re (main_run_list);
577 /* Explicit Levels and Directions */
578 DBG ("explicit levels and directions");
580 FriBidiLevel level, new_level = 0;
581 int isolate_level = 0;
582 FriBidiCharType override, new_override;
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 */
590 FriBidiCharType override; /* only LTR, RTL and ON are valid */
595 FriBidiRun temp_link;
596 FriBidiRun **run_per_isolate_level; /* Connect the isolate levels */
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);
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.
607 explicits_list = new_run_list ();
609 (!explicits_list) goto out;
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.
615 Process each character iteratively, applying rules X2 through X8.
616 Only embedding levels from 0 to 123 are valid in this phase. */
619 override = FRIBIDI_TYPE_ON;
624 valid_isolate_count = 0;
625 isolate_overflow = 0;
626 status_stack = fribidi_malloc (sizeof (status_stack[0]) *
627 FRIBIDI_BIDI_MAX_RESOLVED_LEVELS);
629 for_run_list (pp, main_run_list)
631 FriBidiCharType this_type = RL_TYPE (pp);
632 RL_ISOLATE_LEVEL (pp) = isolate_level;
634 if (FRIBIDI_IS_EXPLICIT_OR_BN (this_type))
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
641 /* X3. With each LRE, compute the least greater even
643 /* 2. Explicit Overrides */
644 /* X4. With each RLO, compute the least greater odd
646 /* X5. With each LRO, compute the least greater even
648 new_override = FRIBIDI_EXPLICIT_TO_OVERRIDE_DIR (this_type);
649 for (i = RL_LEN (pp); i; i--)
652 ((level + FRIBIDI_DIR_TO_LEVEL (this_type) + 2) & ~1) -
653 FRIBIDI_DIR_TO_LEVEL (this_type);
658 else if (this_type == FRIBIDI_TYPE_PDF)
660 /* 3. Terminating Embeddings and overrides */
661 /* X7. With each PDF, determine the matching embedding or
663 for (i = RL_LEN (pp); i; i--)
665 if (stack_size && status_stack[stack_size-1].isolate != 0)
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);
678 else if (this_type == FRIBIDI_TYPE_PDI)
679 /* X6a. pop the direction of the stack */
681 for (i = RL_LEN (pp); i; i--)
683 if (isolate_overflow > 0)
686 RL_LEVEL (pp) = level;
689 else if (valid_isolate_count > 0)
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)
696 over_pushed = 0; /* The PDI resets the overpushed! */
699 valid_isolate_count--;
700 RL_LEVEL (pp) = level;
701 RL_ISOLATE_LEVEL (pp) = isolate_level;
705 /* Ignore isolated PDI's by turning them into ON's */
706 RL_TYPE (pp) = FRIBIDI_TYPE_ON;
707 RL_LEVEL (pp) = level;
711 else if (FRIBIDI_IS_ISOLATE(this_type))
713 /* TBD support RL_LEN > 1 */
714 new_override = FRIBIDI_TYPE_ON;
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)
722 /* Search for a local strong character until we
723 meet the corresponding PDI or the end of the
726 int isolate_count = 0;
727 int fsi_base_level = 0;
728 for_run_list (fsi_pp, pp)
730 if (RL_TYPE(fsi_pp) == FRIBIDI_TYPE_PDI)
733 if (valid_isolate_count < 0)
736 else if (FRIBIDI_IS_ISOLATE(RL_TYPE(fsi_pp)))
738 else if (isolate_count==0 && FRIBIDI_IS_LETTER (RL_TYPE (fsi_pp)))
740 fsi_base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (fsi_pp));
745 /* Same behavior like RLI and LRI above */
746 if (FRIBIDI_LEVEL_IS_RTL (fsi_base_level))
747 new_level = level + 1 + (level%2);
749 new_level = level + 2 - (level%2);
752 RL_LEVEL (pp) = level;
753 RL_ISOLATE_LEVEL (pp) = isolate_level++;
754 base_level_per_iso_level[isolate_level] = new_level;
756 if (!FRIBIDI_IS_NEUTRAL (override))
757 RL_TYPE (pp) = override;
759 if (new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL)
761 valid_isolate_count++;
766 isolate_overflow += 1;
768 else if (this_type == FRIBIDI_TYPE_BS)
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. */
777 /* X6. For all types besides RLE, LRE, RLO, LRO, and PDF:
778 a. Set the level of the current character to the current
780 b. Whenever the directional override status is not neutral,
781 reset the current character type to the directional override
783 RL_LEVEL (pp) = level;
784 if (!FRIBIDI_IS_NEUTRAL (override))
785 RL_TYPE (pp) = override;
789 /* Build the isolate_level connections */
790 for_run_list (pp, main_run_list)
792 int isolate_level = RL_ISOLATE_LEVEL (pp);
793 if (run_per_isolate_level[isolate_level])
795 run_per_isolate_level[isolate_level]->next_isolate = pp;
796 pp->prev_isolate = run_per_isolate_level[isolate_level];
798 run_per_isolate_level[isolate_level] = pp;
801 /* Implementing X8. It has no effect on a single paragraph! */
803 override = FRIBIDI_TYPE_ON;
807 fribidi_free (status_stack);
808 fribidi_free (run_per_isolate_level);
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
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. */
820 compact_list (main_run_list);
824 (fribidi_debug_status ())
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);
833 /* 4. Resolving weak types. Also calculate the maximum isolate level */
835 DBG ("resolving weak types");
837 int *last_strong_stack;
838 FriBidiCharType prev_type_orig;
841 last_strong_stack = fribidi_malloc (sizeof (int)
842 * FRIBIDI_BIDI_MAX_RESOLVED_LEVELS);
843 last_strong_stack[0] = base_dir;
845 for_run_list (pp, main_run_list)
847 register FriBidiCharType prev_type, this_type, next_type;
848 FriBidiRun *ppp_prev, *ppp_next;
851 ppp_prev = get_adjacent_run(pp, false, false);
852 ppp_next = get_adjacent_run(pp, true, false);
854 this_type = RL_TYPE (pp);
855 iso_level = RL_ISOLATE_LEVEL(pp);
857 if (iso_level > max_iso_level)
858 max_iso_level = iso_level;
860 if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
861 prev_type = RL_TYPE(ppp_prev);
863 prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
865 if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
866 next_type = RL_TYPE(ppp_next);
868 next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
870 if (FRIBIDI_IS_STRONG (prev_type))
871 last_strong_stack[iso_level] = prev_type;
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)
883 /* New rule in Unicode 6.3 */
884 if (FRIBIDI_IS_ISOLATE (RL_TYPE (pp->prev)))
885 RL_TYPE(pp) = FRIBIDI_TYPE_ON;
887 if (RL_LEVEL (ppp_prev) == RL_LEVEL (pp))
889 if (ppp_prev == pp->prev)
890 pp = merge_with_prev (pp);
893 RL_TYPE (pp) = prev_type;
895 if (prev_type == next_type && RL_LEVEL (pp) == RL_LEVEL (pp->next))
897 if (ppp_next == pp->next)
898 pp = merge_with_prev (pp->next);
900 continue; /* As we know the next condition cannot be true. */
903 /* W2: European numbers. */
904 if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_AL)
906 RL_TYPE (pp) = FRIBIDI_TYPE_AN;
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;
916 last_strong_stack[0] = base_dir;
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
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;
927 /* Each isolate level has its own memory of the last strong character */
928 for_run_list (pp, main_run_list)
930 register FriBidiCharType prev_type, this_type, next_type;
932 FriBidiRun *ppp_prev, *ppp_next;
934 this_type = RL_TYPE (pp);
935 iso_level = RL_ISOLATE_LEVEL(pp);
937 ppp_prev = get_adjacent_run(pp, false, false);
938 ppp_next = get_adjacent_run(pp, true, false);
940 if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
941 prev_type = RL_TYPE(ppp_prev);
943 prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
945 if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
946 next_type = RL_TYPE(ppp_next);
948 next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
950 if (FRIBIDI_IS_STRONG (prev_type))
951 last_strong_stack[iso_level] = prev_type;
955 /* W3: Change ALs to R. */
956 if (this_type == FRIBIDI_TYPE_AL)
958 RL_TYPE (pp) = FRIBIDI_TYPE_RTL;
960 prev_type_orig = FRIBIDI_TYPE_ON;
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. */
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))
974 RL_TYPE (pp) = prev_type;
975 this_type = RL_TYPE (pp);
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))
985 RL_TYPE (pp) = FRIBIDI_TYPE_EN;
987 this_type = RL_TYPE (pp);
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;
994 /* W7. Change european numbers to L. */
995 if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_LTR)
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);
1002 prev_type_orig = PREV_TYPE_OR_SOR (pp->next);
1005 fribidi_free (last_strong_stack);
1008 compact_neutrals (main_run_list);
1012 (fribidi_debug_status ())
1014 print_resolved_levels (main_run_list);
1015 print_resolved_types (main_run_list);
1019 /* 5. Resolving Neutral Types */
1021 DBG ("resolving neutral types - N0");
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])
1028 int *bracket_stack_size = fribidi_malloc(sizeof(bracket_stack_size[0])
1030 int last_level = RL_LEVEL(main_run_list);
1031 int last_iso_level = 0;
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);
1036 /* Build the bd16 pair stack. */
1037 for_run_list (pp, main_run_list)
1039 int level = RL_LEVEL(pp);
1040 int iso_level = RL_ISOLATE_LEVEL(pp);
1041 FriBidiBracketType brack_prop = RL_BRACKET_TYPE(pp);
1043 /* Interpret the isolating run sequence as such that they
1044 end at a change in the level, unless the iso_level has been
1046 if (level != last_level && last_iso_level == iso_level)
1047 bracket_stack_size[last_iso_level] = 0;
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)
1054 if (FRIBIDI_IS_BRACKET_OPEN(brack_prop))
1056 if (bracket_stack_size[iso_level]==FRIBIDI_BIDI_MAX_NESTED_BRACKET_PAIRS)
1059 /* push onto the pair stack */
1060 bracket_stack[iso_level][bracket_stack_size[iso_level]++] = pp;
1064 int stack_idx = bracket_stack_size[iso_level] - 1;
1065 while (stack_idx >= 0)
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))
1070 bracket_stack_size[iso_level] = stack_idx;
1072 pairing_nodes = pairing_nodes_push(pairing_nodes,
1073 bracket_stack[iso_level][stack_idx],
1082 last_iso_level = iso_level;
1085 /* The list must now be sorted for the next algo to work! */
1086 sort_pairing_nodes(&pairing_nodes);
1090 (fribidi_debug_status ())
1092 print_pairing_nodes (pairing_nodes);
1098 FriBidiPairingNode *ppairs = pairing_nodes;
1101 int iso_level = ppairs->open->isolate_level;
1102 int embedding_level = base_level_per_iso_level[iso_level];
1104 /* Find matching strong. */
1105 fribidi_boolean found = false;
1107 for (ppn = ppairs->open; ppn!= ppairs->close; ppn = ppn->next)
1109 FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
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));
1117 if (FRIBIDI_IS_STRONG (this_type) && this_level == embedding_level)
1119 RL_TYPE(ppairs->open) = RL_TYPE(ppairs->close) = this_level%2 ? FRIBIDI_TYPE_RTL : FRIBIDI_TYPE_LTR;
1126 /* Search for any strong type preceding and within the bracket pair */
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)
1134 FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1135 if (FRIBIDI_IS_STRONG (this_type) && RL_ISOLATE_LEVEL(ppn) == iso_level)
1137 prec_strong_level = RL_LEVEL (ppn) +
1138 (FRIBIDI_LEVEL_IS_RTL (RL_LEVEL(ppn)) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1144 for (ppn = ppairs->open; ppn!= ppairs->close; ppn = ppn->next)
1146 FriBidiCharType this_type = RL_TYPE_AN_EN_AS_RTL(ppn);
1147 if (FRIBIDI_IS_STRONG (this_type) && RL_ISOLATE_LEVEL(ppn) == iso_level)
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;
1161 ppairs = ppairs->next;
1164 free_pairing_nodes(pairing_nodes);
1167 for (i=0; i<num_iso_levels; i++)
1168 fribidi_free(bracket_stack[i]);
1170 fribidi_free(bracket_stack);
1171 fribidi_free(bracket_stack_size);
1173 /* Remove the bracket property and re-compact */
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);
1184 (fribidi_debug_status ())
1186 print_resolved_levels (main_run_list);
1187 print_resolved_types (main_run_list);
1192 DBG ("resolving neutral types - N1+N2");
1194 for_run_list (pp, main_run_list)
1196 FriBidiCharType prev_type, this_type, next_type;
1197 FriBidiRun *ppp_prev, *ppp_next;
1199 ppp_prev = get_adjacent_run(pp, false, false);
1200 ppp_next = get_adjacent_run(pp, true, false);
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));
1206 if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
1207 prev_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_prev));
1209 prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
1211 if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
1212 next_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_next));
1214 next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
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);
1223 compact_list (main_run_list);
1227 (fribidi_debug_status ())
1229 print_resolved_levels (main_run_list);
1230 print_resolved_types (main_run_list);
1234 /* 6. Resolving implicit levels */
1235 DBG ("resolving implicit levels");
1237 max_level = base_level;
1239 for_run_list (pp, main_run_list)
1241 FriBidiCharType this_type;
1244 this_type = RL_TYPE (pp);
1245 level = RL_LEVEL (pp);
1249 if (FRIBIDI_IS_NUMBER (this_type))
1250 RL_LEVEL (pp) = (level + 2) & ~1;
1254 (FRIBIDI_LEVEL_IS_RTL (level) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1256 if (RL_LEVEL (pp) > max_level)
1257 max_level = RL_LEVEL (pp);
1261 compact_list (main_run_list);
1265 (fribidi_debug_status ())
1267 print_bidi_string (bidi_types, len);
1268 print_resolved_levels (main_run_list);
1269 print_resolved_types (main_run_list);
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");
1277 (explicits_list->next != explicits_list)
1279 register FriBidiRun *p;
1280 register fribidi_boolean stat =
1281 shadow_run_list (main_run_list, explicits_list, true);
1282 explicits_list = NULL;
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;
1297 (fribidi_debug_status ())
1299 print_types_re (main_run_list);
1300 print_resolved_levels (main_run_list);
1301 print_resolved_types (main_run_list);
1305 DBG ("reset the embedding levels, 1, 2, 3.");
1307 register int j, state, pos;
1308 register FriBidiCharType char_type;
1309 register FriBidiRun *p, *q, *list;
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 ();
1325 for (j = len - 1; j >= -1; j--)
1327 /* close up the open link at the end */
1329 char_type = bidi_types[j];
1331 char_type = FRIBIDI_TYPE_ON;
1332 if (!state && FRIBIDI_IS_SEPARATOR (char_type))
1338 !(FRIBIDI_IS_EXPLICIT_OR_SEPARATOR_OR_BN_OR_WS(char_type)
1339 || FRIBIDI_IS_ISOLATE(char_type)))
1346 free_run_list (list);
1352 p->level = base_level;
1353 move_node_before (p, q);
1358 (!shadow_run_list (main_run_list, list, false)) goto out;
1363 (fribidi_debug_status ())
1365 print_types_re (main_run_list);
1366 print_resolved_levels (main_run_list);
1367 print_resolved_types (main_run_list);
1372 FriBidiStrIndex pos = 0;
1373 for_run_list (pp, main_run_list)
1375 register FriBidiStrIndex l;
1376 register FriBidiLevel level = pp->level;
1377 for (l = pp->len; l; l--)
1378 embedding_levels[pos++] = level;
1385 DBG ("leaving fribidi_get_par_embedding_levels");
1388 free_run_list (main_run_list);
1390 (explicits_list) free_run_list (explicits_list);
1391 if (base_level_per_iso_level)
1392 fribidi_free (base_level_per_iso_level);
1394 return status ? max_level + 1 : 0;
1399 bidi_string_reverse (
1401 const FriBidiStrIndex len
1406 fribidi_assert (str);
1408 for (i = 0; i < len / 2; i++)
1410 FriBidiChar tmp = str[i];
1411 str[i] = str[len - 1 - i];
1412 str[len - 1 - i] = tmp;
1417 index_array_reverse (
1418 FriBidiStrIndex *arr,
1419 const FriBidiStrIndex len
1424 fribidi_assert (arr);
1426 for (i = 0; i < len / 2; i++)
1428 FriBidiStrIndex tmp = arr[i];
1429 arr[i] = arr[len - 1 - i];
1430 arr[len - 1 - i] = tmp;
1435 FRIBIDI_ENTRY FriBidiLevel
1436 fribidi_reorder_line (
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,
1447 FriBidiStrIndex *map
1450 fribidi_boolean status = false;
1451 FriBidiLevel max_level = 0;
1460 DBG ("in fribidi_reorder_line");
1462 fribidi_assert (bidi_types);
1463 fribidi_assert (embedding_levels);
1465 DBG ("reset the embedding levels, 4. whitespace at the end of line");
1467 register FriBidiStrIndex i;
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);
1476 /* 7. Reordering resolved levels */
1478 register FriBidiLevel level;
1479 register FriBidiStrIndex i;
1481 /* Reorder both the outstring and the order array */
1483 if (FRIBIDI_TEST_BITS (flags, FRIBIDI_FLAG_REORDER_NSM))
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)
1490 register FriBidiStrIndex seq_end = i;
1491 level = embedding_levels[i];
1493 for (i--; i >= off &&
1494 FRIBIDI_IS_EXPLICIT_OR_BN_OR_NSM (bidi_types[i])
1495 && embedding_levels[i] == level; i--)
1498 if (i < off || embedding_levels[i] != level)
1501 DBG ("warning: NSM(s) at the beginning of level run");
1506 bidi_string_reverse (visual_str + i, seq_end - i + 1);
1510 index_array_reverse (map + i, seq_end - i + 1);
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];
1523 for (level = max_level; level > 0; level--)
1524 for (i = off + len - 1; i >= off; i--)
1525 if (embedding_levels[i] >= level)
1527 /* Find all stretches that are >= level_idx */
1528 register FriBidiStrIndex seq_end = i;
1529 for (i--; i >= off && embedding_levels[i] >= level; i--)
1533 bidi_string_reverse (visual_str + i + 1, seq_end - i);
1535 index_array_reverse (map + i + 1, seq_end - i);
1545 return status ? max_level + 1 : 0;
1548 /* Editor directions:
1549 * vim:textwidth=78:tabstop=8:shiftwidth=2:autoindent:cindent