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 #define LOCAL_BRACKET_SIZE 16
61 /* Pairing nodes are used for holding a pair of open/close brackets as
63 struct _FriBidiPairingNodeStruct {
66 struct _FriBidiPairingNodeStruct *next;
68 typedef struct _FriBidiPairingNodeStruct FriBidiPairingNode;
77 fribidi_assert (second);
78 fribidi_assert (second->next);
80 fribidi_assert (first);
82 first->next = second->next;
83 first->next->prev = first;
84 RL_LEN (first) += RL_LEN (second);
85 if (second->next_isolate)
86 second->next_isolate->prev_isolate = first;
87 first->next_isolate = second->next_isolate;
89 fribidi_free (second);
98 fribidi_assert (list);
101 for_run_list (list, list)
102 if (RL_TYPE (list->prev) == RL_TYPE (list)
103 && RL_LEVEL (list->prev) == RL_LEVEL (list)
104 && RL_BRACKET_TYPE(list) == FRIBIDI_NO_BRACKET /* Don't join brackets! */
105 && RL_BRACKET_TYPE(list->prev) == FRIBIDI_NO_BRACKET
107 list = merge_with_prev (list);
115 fribidi_assert (list);
119 for_run_list (list, list)
121 if (RL_LEVEL (list->prev) == RL_LEVEL (list)
123 ((RL_TYPE (list->prev) == RL_TYPE (list)
124 || (FRIBIDI_IS_NEUTRAL (RL_TYPE (list->prev))
125 && FRIBIDI_IS_NEUTRAL (RL_TYPE (list)))))
126 && RL_BRACKET_TYPE(list) == FRIBIDI_NO_BRACKET /* Don't join brackets! */
127 && RL_BRACKET_TYPE(list->prev) == FRIBIDI_NO_BRACKET
129 list = merge_with_prev (list);
134 /* Search for an adjacent run in the forward or backward direction.
135 It uses the next_isolate and prev_isolate run for short circuited searching.
138 /* The static sentinel is used to signal the end of an isolating
140 static FriBidiRun sentinel = { NULL, NULL, 0,0, FRIBIDI_TYPE_SENTINEL, -1,-1,FRIBIDI_NO_BRACKET, NULL, NULL };
142 static FriBidiRun *get_adjacent_run(FriBidiRun *list, fribidi_boolean forward, fribidi_boolean skip_neutral)
144 FriBidiRun *ppp = forward ? list->next_isolate : list->prev_isolate;
150 FriBidiCharType ppp_type = RL_TYPE (ppp);
152 if (ppp_type == _FRIBIDI_TYPE_SENTINEL)
155 /* Note that when sweeping forward we continue one run
156 beyond the PDI to see what lies behind. When looking
157 backwards, this is not necessary as the leading isolate
158 run has already been assigned the resolved level. */
159 if (ppp->isolate_level > list->isolate_level /* <- How can this be true? */
160 || (forward && ppp_type == FRIBIDI_TYPE_PDI)
161 || (skip_neutral && !FRIBIDI_IS_STRONG(ppp_type)))
163 ppp = forward ? ppp->next_isolate : ppp->prev_isolate;
176 /*======================================================================
177 * For debugging, define some functions for printing the types and the
179 *----------------------------------------------------------------------*/
181 static char char_from_level_array[] = {
182 '$', /* -1 == FRIBIDI_SENTINEL, indicating
183 * start or end of string. */
184 /* 0-61 == 0-9,a-z,A-Z are the the only valid levels before resolving
185 * implicits. after that the level @ may be appear too. */
186 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
187 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
188 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
189 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',
190 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
191 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
194 /* TBD - insert another 125-64 levels */
196 '@', /* 62 == only must appear after resolving
199 '!', /* 63 == FRIBIDI_LEVEL_INVALID, internal error,
200 * this level shouldn't be seen. */
202 '*', '*', '*', '*', '*' /* >= 64 == overflows, this levels and higher
203 * levels show a real bug!. */
206 #define fribidi_char_from_level(level) char_from_level_array[(level) + 1]
215 MSG (" Run types : ");
216 for_run_list (pp, pp)
218 MSG6 ("%d:%d(%s)[%d,%d] ",
219 pp->pos, pp->len, fribidi_get_bidi_type_name (pp->type), pp->level, pp->isolate_level);
225 print_resolved_levels (
231 MSG (" Res. levels: ");
232 for_run_list (pp, pp)
234 register FriBidiStrIndex i;
235 for (i = RL_LEN (pp); i; i--)
236 MSG2 ("%c", fribidi_char_from_level (RL_LEVEL (pp)));
242 print_resolved_types (
248 MSG (" Res. types : ");
249 for_run_list (pp, pp)
252 for (i = RL_LEN (pp); i; i--)
253 MSG2 ("%s ", fribidi_get_bidi_type_name (pp->type));
261 const FriBidiCharType *bidi_types,
262 const FriBidiStrIndex len
265 register FriBidiStrIndex i;
267 fribidi_assert (bidi_types);
269 MSG (" Org. types : ");
270 for (i = 0; i < len; i++)
271 MSG2 ("%s ", fribidi_get_bidi_type_name (bidi_types[i]));
275 static void print_pairing_nodes(FriBidiPairingNode *nodes)
280 MSG3 ("(%d, %d) ", nodes->open->pos, nodes->close->pos);
288 /*=========================================================================
289 * define macros for push and pop the status in to / out of the stack
290 *-------------------------------------------------------------------------*/
292 /* There are a few little points in pushing into and poping from the status
294 1. when the embedding level is not valid (more than
295 FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=125), you must reject it, and not to push
296 into the stack, but when you see a PDF, you must find the matching code,
297 and if it was pushed in the stack, pop it, it means you must pop if and
298 only if you have pushed the matching code, the over_pushed var counts the
299 number of rejected codes so far.
301 2. there's a more confusing point too, when the embedding level is exactly
302 FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL-1=124, an LRO, LRE, or LRI is rejected
303 because the new level would be FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL+1=126, that
304 is invalid; but an RLO, RLE, or RLI is accepted because the new level is
305 FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=125, that is valid, so the rejected codes
306 may be not continuous in the logical order, in fact there are at most two
307 continuous intervals of codes, with an RLO, RLE, or RLI between them. To
308 support this case, the first_interval var counts the number of rejected
309 codes in the first interval, when it is 0, means that there is only one
314 /* a. If this new level would be valid, then this embedding code is valid.
315 Remember (push) the current embedding level and override status.
316 Reset current level to this new level, and reset the override status to
318 b. If the new level would not be valid, then this code is invalid. Don't
319 change the current level or override status.
321 #define PUSH_STATUS \
323 if LIKELY(over_pushed == 0 \
324 && isolate_overflow == 0 \
325 && new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL) \
327 if UNLIKELY(level == FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL - 1) \
328 first_interval = over_pushed; \
329 status_stack[stack_size].level = level; \
330 status_stack[stack_size].isolate_level = isolate_level; \
331 status_stack[stack_size].isolate = isolate; \
332 status_stack[stack_size].override = override; \
335 override = new_override; \
336 } else if LIKELY(isolate_overflow == 0) \
340 /* If there was a valid matching code, restore (pop) the last remembered
341 (pushed) embedding level and directional override.
347 if UNLIKELY(over_pushed > first_interval) \
351 if LIKELY(over_pushed == first_interval) \
352 first_interval = 0; \
354 level = status_stack[stack_size].level; \
355 override = status_stack[stack_size].override; \
356 isolate = status_stack[stack_size].isolate; \
357 isolate_level = status_stack[stack_size].isolate_level; \
363 /* Return the type of previous run or the SOR, if already at the start of
365 #define PREV_TYPE_OR_SOR(pp) \
367 RL_LEVEL(pp->prev) == RL_LEVEL(pp) ? \
368 RL_TYPE(pp->prev) : \
369 FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->prev), RL_LEVEL(pp))) \
372 /* Return the type of next run or the EOR, if already at the end of
374 #define NEXT_TYPE_OR_EOR(pp) \
376 RL_LEVEL(pp->next) == RL_LEVEL(pp) ? \
377 RL_TYPE(pp->next) : \
378 FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->next), RL_LEVEL(pp))) \
382 /* Return the embedding direction of a link. */
383 #define FRIBIDI_EMBEDDING_DIRECTION(link) \
384 FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(link))
387 FRIBIDI_ENTRY FriBidiParType
388 fribidi_get_par_direction (
390 const FriBidiCharType *bidi_types,
391 const FriBidiStrIndex len
394 register FriBidiStrIndex i;
396 fribidi_assert (bidi_types);
398 for (i = 0; i < len; i++)
399 if (FRIBIDI_IS_LETTER (bidi_types[i]))
400 return FRIBIDI_IS_RTL (bidi_types[i]) ? FRIBIDI_PAR_RTL :
403 return FRIBIDI_PAR_ON;
406 /* Push a new entry to the pairing linked list */
407 static FriBidiPairingNode * pairing_nodes_push(FriBidiPairingNode *nodes,
411 FriBidiPairingNode *node = fribidi_malloc(sizeof(FriBidiPairingNode));
419 /* Sort by merge sort */
420 static void pairing_nodes_front_back_split(FriBidiPairingNode *source,
422 FriBidiPairingNode **front,
423 FriBidiPairingNode **back)
425 FriBidiPairingNode *pfast, *pslow;
426 if (!source || !source->next)
434 pfast = source->next;
450 static FriBidiPairingNode *
451 pairing_nodes_sorted_merge(FriBidiPairingNode *nodes1,
452 FriBidiPairingNode *nodes2)
454 FriBidiPairingNode *res = NULL;
460 if (nodes1->open->pos < nodes2->open->pos)
463 res->next = pairing_nodes_sorted_merge(nodes1->next, nodes2);
468 res->next = pairing_nodes_sorted_merge(nodes1, nodes2->next);
473 static void sort_pairing_nodes(FriBidiPairingNode **nodes)
475 FriBidiPairingNode *front, *back;
477 /* 0 or 1 node case */
478 if (!*nodes || !(*nodes)->next)
481 pairing_nodes_front_back_split(*nodes, &front, &back);
482 sort_pairing_nodes(&front);
483 sort_pairing_nodes(&back);
484 *nodes = pairing_nodes_sorted_merge(front, back);
487 static void free_pairing_nodes(FriBidiPairingNode *nodes)
491 FriBidiPairingNode *p = nodes;
497 FRIBIDI_ENTRY FriBidiLevel
498 fribidi_get_par_embedding_levels_ex (
500 const FriBidiCharType *bidi_types,
501 const FriBidiBracketType *bracket_types,
502 const FriBidiStrIndex len,
503 /* input and output */
504 FriBidiParType *pbase_dir,
506 FriBidiLevel *embedding_levels
509 FriBidiLevel base_level_per_iso_level[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
510 FriBidiLevel base_level, max_level = 0;
511 FriBidiParType base_dir;
512 FriBidiRun *main_run_list = NULL, *explicits_list = NULL, *pp;
513 fribidi_boolean status = false;
514 int max_iso_level = 0;
523 DBG ("in fribidi_get_par_embedding_levels");
525 fribidi_assert (bidi_types);
526 fribidi_assert (pbase_dir);
527 fribidi_assert (embedding_levels);
529 /* Determinate character types */
531 /* Get run-length encoded character types */
532 main_run_list = run_list_encode_bidi_types (bidi_types, bracket_types, len);
534 (!main_run_list) goto out;
537 /* Find base level */
538 /* If no strong base_dir was found, resort to the weak direction
539 that was passed on input. */
540 base_level = FRIBIDI_DIR_TO_LEVEL (*pbase_dir);
541 if (!FRIBIDI_IS_STRONG (*pbase_dir))
542 /* P2. P3. Search for first strong character and use its direction as
545 int valid_isolate_count = 0;
546 for_run_list (pp, main_run_list)
548 if (RL_TYPE(pp) == FRIBIDI_TYPE_PDI)
550 /* Ignore if there is no matching isolate */
551 if (valid_isolate_count>0)
552 valid_isolate_count--;
554 else if (FRIBIDI_IS_ISOLATE(RL_TYPE(pp)))
555 valid_isolate_count++;
556 else if (valid_isolate_count==0 && FRIBIDI_IS_LETTER (RL_TYPE (pp)))
558 base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (pp));
559 *pbase_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
564 base_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
565 DBG2 (" base level : %c", fribidi_char_from_level (base_level));
566 DBG2 (" base dir : %s", fribidi_get_bidi_type_name (base_dir));
568 base_level_per_iso_level[0] = base_level;
572 (fribidi_debug_status ())
574 print_types_re (main_run_list);
578 /* Explicit Levels and Directions */
579 DBG ("explicit levels and directions");
581 FriBidiLevel level, new_level = 0;
582 int isolate_level = 0;
583 FriBidiCharType override, new_override;
585 int stack_size, over_pushed, first_interval;
586 int valid_isolate_count = 0;
587 int isolate_overflow = 0;
588 int isolate = 0; /* The isolate status flag */
591 FriBidiCharType override; /* only LTR, RTL and ON are valid */
595 } status_stack[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
596 FriBidiRun temp_link;
597 FriBidiRun *run_per_isolate_level[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
599 memset(run_per_isolate_level, 0, sizeof(run_per_isolate_level[0])
600 * FRIBIDI_BIDI_MAX_RESOLVED_LEVELS);
602 /* explicits_list is a list like main_run_list, that holds the explicit
603 codes that are removed from main_run_list, to reinsert them later by
604 calling the shadow_run_list.
606 explicits_list = new_run_list ();
608 (!explicits_list) goto out;
610 /* X1. Begin by setting the current embedding level to the paragraph
611 embedding level. Set the directional override status to neutral,
612 and directional isolate status to false.
614 Process each character iteratively, applying rules X2 through X8.
615 Only embedding levels from 0 to 123 are valid in this phase. */
618 override = FRIBIDI_TYPE_ON;
623 valid_isolate_count = 0;
624 isolate_overflow = 0;
626 for_run_list (pp, main_run_list)
628 FriBidiCharType this_type = RL_TYPE (pp);
629 RL_ISOLATE_LEVEL (pp) = isolate_level;
631 if (FRIBIDI_IS_EXPLICIT_OR_BN (this_type))
633 if (FRIBIDI_IS_STRONG (this_type))
634 { /* LRE, RLE, LRO, RLO */
635 /* 1. Explicit Embeddings */
636 /* X2. With each RLE, compute the least greater odd
638 /* X3. With each LRE, compute the least greater even
640 /* 2. Explicit Overrides */
641 /* X4. With each RLO, compute the least greater odd
643 /* X5. With each LRO, compute the least greater even
645 new_override = FRIBIDI_EXPLICIT_TO_OVERRIDE_DIR (this_type);
646 for (i = RL_LEN (pp); i; i--)
649 ((level + FRIBIDI_DIR_TO_LEVEL (this_type) + 2) & ~1) -
650 FRIBIDI_DIR_TO_LEVEL (this_type);
655 else if (this_type == FRIBIDI_TYPE_PDF)
657 /* 3. Terminating Embeddings and overrides */
658 /* X7. With each PDF, determine the matching embedding or
660 for (i = RL_LEN (pp); i; i--)
662 if (stack_size && status_stack[stack_size-1].isolate != 0)
668 /* X9. Remove all RLE, LRE, RLO, LRO, PDF, and BN codes. */
669 /* Remove element and add it to explicits_list */
670 RL_LEVEL (pp) = FRIBIDI_SENTINEL;
671 temp_link.next = pp->next;
672 move_node_before (pp, explicits_list);
675 else if (this_type == FRIBIDI_TYPE_PDI)
676 /* X6a. pop the direction of the stack */
678 for (i = RL_LEN (pp); i; i--)
680 if (isolate_overflow > 0)
683 RL_LEVEL (pp) = level;
686 else if (valid_isolate_count > 0)
688 /* Pop away all LRE,RLE,LRO, RLO levels
689 from the stack, as these are implicitly
690 terminated by the PDI */
691 while (stack_size && !status_stack[stack_size-1].isolate)
693 over_pushed = 0; /* The PDI resets the overpushed! */
696 valid_isolate_count--;
697 RL_LEVEL (pp) = level;
698 RL_ISOLATE_LEVEL (pp) = isolate_level;
702 /* Ignore isolated PDI's by turning them into ON's */
703 RL_TYPE (pp) = FRIBIDI_TYPE_ON;
704 RL_LEVEL (pp) = level;
708 else if (FRIBIDI_IS_ISOLATE(this_type))
710 /* TBD support RL_LEN > 1 */
711 new_override = FRIBIDI_TYPE_ON;
713 if (this_type == FRIBIDI_TYPE_LRI)
714 new_level = level + 2 - (level%2);
715 else if (this_type == FRIBIDI_TYPE_RLI)
716 new_level = level + 1 + (level%2);
717 else if (this_type == FRIBIDI_TYPE_FSI)
719 /* Search for a local strong character until we
720 meet the corresponding PDI or the end of the
723 int isolate_count = 0;
724 int fsi_base_level = 0;
725 for_run_list (fsi_pp, pp)
727 if (RL_TYPE(fsi_pp) == FRIBIDI_TYPE_PDI)
730 if (valid_isolate_count < 0)
733 else if (FRIBIDI_IS_ISOLATE(RL_TYPE(fsi_pp)))
735 else if (isolate_count==0 && FRIBIDI_IS_LETTER (RL_TYPE (fsi_pp)))
737 fsi_base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (fsi_pp));
742 /* Same behavior like RLI and LRI above */
743 if (FRIBIDI_LEVEL_IS_RTL (fsi_base_level))
744 new_level = level + 1 + (level%2);
746 new_level = level + 2 - (level%2);
749 RL_LEVEL (pp) = level;
750 RL_ISOLATE_LEVEL (pp) = isolate_level++;
751 base_level_per_iso_level[isolate_level] = new_level;
753 if (!FRIBIDI_IS_NEUTRAL (override))
754 RL_TYPE (pp) = override;
756 if (new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL)
758 valid_isolate_count++;
763 isolate_overflow += 1;
765 else if (this_type == FRIBIDI_TYPE_BS)
767 /* X8. All explicit directional embeddings and overrides are
768 completely terminated at the end of each paragraph. Paragraph
769 separators are not included in the embedding. */
774 /* X6. For all types besides RLE, LRE, RLO, LRO, and PDF:
775 a. Set the level of the current character to the current
777 b. Whenever the directional override status is not neutral,
778 reset the current character type to the directional override
780 RL_LEVEL (pp) = level;
781 if (!FRIBIDI_IS_NEUTRAL (override))
782 RL_TYPE (pp) = override;
786 /* Build the isolate_level connections */
787 for_run_list (pp, main_run_list)
789 int isolate_level = RL_ISOLATE_LEVEL (pp);
790 if (run_per_isolate_level[isolate_level])
792 run_per_isolate_level[isolate_level]->next_isolate = pp;
793 pp->prev_isolate = run_per_isolate_level[isolate_level];
795 run_per_isolate_level[isolate_level] = pp;
798 /* Implementing X8. It has no effect on a single paragraph! */
800 override = FRIBIDI_TYPE_ON;
804 /* X10. The remaining rules are applied to each run of characters at the
805 same level. For each run, determine the start-of-level-run (sor) and
806 end-of-level-run (eor) type, either L or R. This depends on the
807 higher of the two levels on either side of the boundary (at the start
808 or end of the paragraph, the level of the 'other' run is the base
809 embedding level). If the higher level is odd, the type is R, otherwise
811 /* Resolving Implicit Levels can be done out of X10 loop, so only change
812 of Resolving Weak Types and Resolving Neutral Types is needed. */
814 compact_list (main_run_list);
818 (fribidi_debug_status ())
820 print_types_re (main_run_list);
821 print_bidi_string (bidi_types, len);
822 print_resolved_levels (main_run_list);
823 print_resolved_types (main_run_list);
827 /* 4. Resolving weak types. Also calculate the maximum isolate level */
829 DBG ("resolving weak types");
831 int last_strong_stack[FRIBIDI_BIDI_MAX_RESOLVED_LEVELS];
832 FriBidiCharType prev_type_orig;
835 last_strong_stack[0] = base_dir;
837 for_run_list (pp, main_run_list)
839 register FriBidiCharType prev_type, this_type, next_type;
840 FriBidiRun *ppp_prev, *ppp_next;
843 ppp_prev = get_adjacent_run(pp, false, false);
844 ppp_next = get_adjacent_run(pp, true, false);
846 this_type = RL_TYPE (pp);
847 iso_level = RL_ISOLATE_LEVEL(pp);
849 if (iso_level > max_iso_level)
850 max_iso_level = iso_level;
852 if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
853 prev_type = RL_TYPE(ppp_prev);
855 prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
857 if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
858 next_type = RL_TYPE(ppp_next);
860 next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
862 if (FRIBIDI_IS_STRONG (prev_type))
863 last_strong_stack[iso_level] = prev_type;
866 Examine each non-spacing mark (NSM) in the level run, and change the
867 type of the NSM to the type of the previous character. If the NSM
868 is at the start of the level run, it will get the type of sor. */
869 /* Implementation note: it is important that if the previous character
870 is not sor, then we should merge this run with the previous,
871 because of rules like W5, that we assume all of a sequence of
872 adjacent ETs are in one FriBidiRun. */
873 if (this_type == FRIBIDI_TYPE_NSM)
875 /* New rule in Unicode 6.3 */
876 if (FRIBIDI_IS_ISOLATE (RL_TYPE (pp->prev)))
877 RL_TYPE(pp) = FRIBIDI_TYPE_ON;
879 if (RL_LEVEL (ppp_prev) == RL_LEVEL (pp))
881 if (ppp_prev == pp->prev)
882 pp = merge_with_prev (pp);
885 RL_TYPE (pp) = prev_type;
887 if (prev_type == next_type && RL_LEVEL (pp) == RL_LEVEL (pp->next))
889 if (ppp_next == pp->next)
890 pp = merge_with_prev (pp->next);
892 continue; /* As we know the next condition cannot be true. */
895 /* W2: European numbers. */
896 if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_AL)
898 RL_TYPE (pp) = FRIBIDI_TYPE_AN;
900 /* Resolving dependency of loops for rules W1 and W2, so we
901 can merge them in one loop. */
902 if (next_type == FRIBIDI_TYPE_NSM)
903 RL_TYPE (ppp_next) = FRIBIDI_TYPE_AN;
908 last_strong_stack[0] = base_dir;
910 /* Resolving dependency of loops for rules W4 and W5, W5 may
911 want to prevent W4 to take effect in the next turn, do this
914 /* Resolving dependency of loops for rules W4 and W5 with W7,
915 W7 may change an EN to L but it sets the prev_type_orig if needed,
916 so W4 and W5 in next turn can still do their works. */
917 prev_type_orig = FRIBIDI_TYPE_ON;
919 /* Each isolate level has its own memory of the last strong character */
920 for_run_list (pp, main_run_list)
922 register FriBidiCharType prev_type, this_type, next_type;
924 FriBidiRun *ppp_prev, *ppp_next;
926 this_type = RL_TYPE (pp);
927 iso_level = RL_ISOLATE_LEVEL(pp);
929 ppp_prev = get_adjacent_run(pp, false, false);
930 ppp_next = get_adjacent_run(pp, true, false);
932 if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
933 prev_type = RL_TYPE(ppp_prev);
935 prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
937 if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
938 next_type = RL_TYPE(ppp_next);
940 next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
942 if (FRIBIDI_IS_STRONG (prev_type))
943 last_strong_stack[iso_level] = prev_type;
947 /* W3: Change ALs to R. */
948 if (this_type == FRIBIDI_TYPE_AL)
950 RL_TYPE (pp) = FRIBIDI_TYPE_RTL;
952 prev_type_orig = FRIBIDI_TYPE_ON;
956 /* W4. A single european separator changes to a european number.
957 A single common separator between two numbers of the same type
958 changes to that type. */
960 && RL_LEN (pp) == 1 && FRIBIDI_IS_ES_OR_CS (this_type)
961 && FRIBIDI_IS_NUMBER (prev_type_orig)
962 && prev_type_orig == next_type
963 && (prev_type_orig == FRIBIDI_TYPE_EN
964 || this_type == FRIBIDI_TYPE_CS))
966 RL_TYPE (pp) = prev_type;
967 this_type = RL_TYPE (pp);
971 /* W5. A sequence of European terminators adjacent to European
972 numbers changes to All European numbers. */
973 if (this_type == FRIBIDI_TYPE_ET
974 && (prev_type_orig == FRIBIDI_TYPE_EN
975 || next_type == FRIBIDI_TYPE_EN))
977 RL_TYPE (pp) = FRIBIDI_TYPE_EN;
979 this_type = RL_TYPE (pp);
982 /* W6. Otherwise change separators and terminators to other neutral. */
983 if (FRIBIDI_IS_NUMBER_SEPARATOR_OR_TERMINATOR (this_type))
984 RL_TYPE (pp) = FRIBIDI_TYPE_ON;
986 /* W7. Change european numbers to L. */
987 if (this_type == FRIBIDI_TYPE_EN && last_strong_stack[iso_level] == FRIBIDI_TYPE_LTR)
989 RL_TYPE (pp) = FRIBIDI_TYPE_LTR;
990 prev_type_orig = (RL_LEVEL (pp) == RL_LEVEL (pp->next) ?
991 FRIBIDI_TYPE_EN : FRIBIDI_TYPE_ON);
994 prev_type_orig = PREV_TYPE_OR_SOR (pp->next);
998 compact_neutrals (main_run_list);
1002 (fribidi_debug_status ())
1004 print_resolved_levels (main_run_list);
1005 print_resolved_types (main_run_list);
1009 /* 5. Resolving Neutral Types */
1011 DBG ("resolving neutral types - N0");
1013 /* BD16 - Build list of all pairs*/
1014 int num_iso_levels = max_iso_level + 1;
1015 FriBidiPairingNode *pairing_nodes = NULL;
1016 FriBidiRun *local_bracket_stack[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL][LOCAL_BRACKET_SIZE];
1017 FriBidiRun **bracket_stack[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
1018 int bracket_stack_size[FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL];
1019 int last_level = RL_LEVEL(main_run_list);
1020 int last_iso_level = 0;
1022 memset(bracket_stack, 0, sizeof(bracket_stack[0])*num_iso_levels);
1023 memset(bracket_stack_size, 0, sizeof(bracket_stack_size[0])*num_iso_levels);
1025 /* populate the bracket_size. The first LOCAL_BRACKET_SIZE entries
1026 of the stack are one the stack. Allocate the rest of the entries.
1030 for (iso_level=0; iso_level < LOCAL_BRACKET_SIZE; iso_level++)
1031 bracket_stack[iso_level] = local_bracket_stack[iso_level];
1033 for (iso_level=LOCAL_BRACKET_SIZE; iso_level < num_iso_levels; iso_level++)
1034 bracket_stack[iso_level] = fribidi_malloc (sizeof (bracket_stack[0])
1035 * FRIBIDI_BIDI_MAX_NESTED_BRACKET_PAIRS);
1038 /* Build the bd16 pair stack. */
1039 for_run_list (pp, main_run_list)
1041 int level = RL_LEVEL(pp);
1042 int iso_level = RL_ISOLATE_LEVEL(pp);
1043 FriBidiBracketType brack_prop = RL_BRACKET_TYPE(pp);
1045 /* Interpret the isolating run sequence as such that they
1046 end at a change in the level, unless the iso_level has been
1048 if (level != last_level && last_iso_level == iso_level)
1049 bracket_stack_size[last_iso_level] = 0;
1051 if (brack_prop!= FRIBIDI_NO_BRACKET
1052 && RL_TYPE(pp)==FRIBIDI_TYPE_ON)
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);
1166 if (num_iso_levels >= LOCAL_BRACKET_SIZE)
1169 /* Only need to free the non static members */
1170 for (i=LOCAL_BRACKET_SIZE; i<num_iso_levels; i++)
1171 fribidi_free(bracket_stack[i]);
1174 /* Remove the bracket property and re-compact */
1176 const FriBidiBracketType NoBracket = FRIBIDI_NO_BRACKET;
1177 for_run_list (pp, main_run_list)
1178 pp->bracket_type = NoBracket;
1179 compact_neutrals (main_run_list);
1185 (fribidi_debug_status ())
1187 print_resolved_levels (main_run_list);
1188 print_resolved_types (main_run_list);
1193 DBG ("resolving neutral types - N1+N2");
1195 for_run_list (pp, main_run_list)
1197 FriBidiCharType prev_type, this_type, next_type;
1198 FriBidiRun *ppp_prev, *ppp_next;
1200 ppp_prev = get_adjacent_run(pp, false, false);
1201 ppp_next = get_adjacent_run(pp, true, false);
1203 /* "European and Arabic numbers are treated as though they were R"
1204 FRIBIDI_CHANGE_NUMBER_TO_RTL does this. */
1205 this_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE (pp));
1207 if (RL_LEVEL(ppp_prev) == RL_LEVEL(pp))
1208 prev_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_prev));
1210 prev_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_prev), RL_LEVEL(pp)));
1212 if (RL_LEVEL(ppp_next) == RL_LEVEL(pp))
1213 next_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE(ppp_next));
1215 next_type = FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(ppp_next), RL_LEVEL(pp)));
1217 if (FRIBIDI_IS_NEUTRAL (this_type))
1218 RL_TYPE (pp) = (prev_type == next_type) ?
1219 /* N1. */ prev_type :
1220 /* N2. */ FRIBIDI_EMBEDDING_DIRECTION (pp);
1224 compact_list (main_run_list);
1228 (fribidi_debug_status ())
1230 print_resolved_levels (main_run_list);
1231 print_resolved_types (main_run_list);
1235 /* 6. Resolving implicit levels */
1236 DBG ("resolving implicit levels");
1238 max_level = base_level;
1240 for_run_list (pp, main_run_list)
1242 FriBidiCharType this_type;
1245 this_type = RL_TYPE (pp);
1246 level = RL_LEVEL (pp);
1250 if (FRIBIDI_IS_NUMBER (this_type))
1251 RL_LEVEL (pp) = (level + 2) & ~1;
1255 (FRIBIDI_LEVEL_IS_RTL (level) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
1257 if (RL_LEVEL (pp) > max_level)
1258 max_level = RL_LEVEL (pp);
1262 compact_list (main_run_list);
1266 (fribidi_debug_status ())
1268 print_bidi_string (bidi_types, len);
1269 print_resolved_levels (main_run_list);
1270 print_resolved_types (main_run_list);
1274 /* Reinsert the explicit codes & BN's that are already removed, from the
1275 explicits_list to main_run_list. */
1276 DBG ("reinserting explicit codes");
1278 (explicits_list->next != explicits_list)
1280 register FriBidiRun *p;
1281 register fribidi_boolean stat =
1282 shadow_run_list (main_run_list, explicits_list, true);
1283 explicits_list = NULL;
1287 /* Set level of inserted explicit chars to that of their previous
1288 * char, such that they do not affect reordering. */
1289 p = main_run_list->next;
1290 if (p != main_run_list && p->level == FRIBIDI_SENTINEL)
1291 p->level = base_level;
1292 for_run_list (p, main_run_list) if (p->level == FRIBIDI_SENTINEL)
1293 p->level = p->prev->level;
1298 (fribidi_debug_status ())
1300 print_types_re (main_run_list);
1301 print_resolved_levels (main_run_list);
1302 print_resolved_types (main_run_list);
1306 DBG ("reset the embedding levels, 1, 2, 3.");
1308 register int j, state, pos;
1309 register FriBidiCharType char_type;
1310 register FriBidiRun *p, *q, *list;
1312 /* L1. Reset the embedding levels of some chars:
1313 1. segment separators,
1314 2. paragraph separators,
1315 3. any sequence of whitespace characters preceding a segment
1316 separator or paragraph separator, and
1317 4. any sequence of whitespace characters and/or isolate formatting
1318 characters at the end of the line.
1319 ... (to be continued in fribidi_reorder_line()). */
1320 list = new_run_list ();
1326 for (j = len - 1; j >= -1; j--)
1328 /* close up the open link at the end */
1330 char_type = bidi_types[j];
1332 char_type = FRIBIDI_TYPE_ON;
1333 if (!state && FRIBIDI_IS_SEPARATOR (char_type))
1339 !(FRIBIDI_IS_EXPLICIT_OR_SEPARATOR_OR_BN_OR_WS(char_type)
1340 || FRIBIDI_IS_ISOLATE(char_type)))
1347 free_run_list (list);
1353 p->level = base_level;
1354 move_node_before (p, q);
1359 (!shadow_run_list (main_run_list, list, false)) goto out;
1364 (fribidi_debug_status ())
1366 print_types_re (main_run_list);
1367 print_resolved_levels (main_run_list);
1368 print_resolved_types (main_run_list);
1373 FriBidiStrIndex pos = 0;
1374 for_run_list (pp, main_run_list)
1376 register FriBidiStrIndex l;
1377 register FriBidiLevel level = pp->level;
1378 for (l = pp->len; l; l--)
1379 embedding_levels[pos++] = level;
1386 DBG ("leaving fribidi_get_par_embedding_levels");
1389 free_run_list (main_run_list);
1391 (explicits_list) free_run_list (explicits_list);
1393 return status ? max_level + 1 : 0;
1398 bidi_string_reverse (
1400 const FriBidiStrIndex len
1405 fribidi_assert (str);
1407 for (i = 0; i < len / 2; i++)
1409 FriBidiChar tmp = str[i];
1410 str[i] = str[len - 1 - i];
1411 str[len - 1 - i] = tmp;
1416 index_array_reverse (
1417 FriBidiStrIndex *arr,
1418 const FriBidiStrIndex len
1423 fribidi_assert (arr);
1425 for (i = 0; i < len / 2; i++)
1427 FriBidiStrIndex tmp = arr[i];
1428 arr[i] = arr[len - 1 - i];
1429 arr[len - 1 - i] = tmp;
1434 FRIBIDI_ENTRY FriBidiLevel
1435 fribidi_reorder_line (
1437 FriBidiFlags flags, /* reorder flags */
1438 const FriBidiCharType *bidi_types,
1439 const FriBidiStrIndex len,
1440 const FriBidiStrIndex off,
1441 const FriBidiParType base_dir,
1442 /* input and output */
1443 FriBidiLevel *embedding_levels,
1444 FriBidiChar *visual_str,
1446 FriBidiStrIndex *map
1449 fribidi_boolean status = false;
1450 FriBidiLevel max_level = 0;
1459 DBG ("in fribidi_reorder_line");
1461 fribidi_assert (bidi_types);
1462 fribidi_assert (embedding_levels);
1464 DBG ("reset the embedding levels, 4. whitespace at the end of line");
1466 register FriBidiStrIndex i;
1468 /* L1. Reset the embedding levels of some chars:
1469 4. any sequence of white space characters at the end of the line. */
1470 for (i = off + len - 1; i >= off &&
1471 FRIBIDI_IS_EXPLICIT_OR_BN_OR_WS (bidi_types[i]); i--)
1472 embedding_levels[i] = FRIBIDI_DIR_TO_LEVEL (base_dir);
1475 /* 7. Reordering resolved levels */
1477 register FriBidiLevel level;
1478 register FriBidiStrIndex i;
1480 /* Reorder both the outstring and the order array */
1482 if (FRIBIDI_TEST_BITS (flags, FRIBIDI_FLAG_REORDER_NSM))
1484 /* L3. Reorder NSMs. */
1485 for (i = off + len - 1; i >= off; i--)
1486 if (FRIBIDI_LEVEL_IS_RTL (embedding_levels[i])
1487 && bidi_types[i] == FRIBIDI_TYPE_NSM)
1489 register FriBidiStrIndex seq_end = i;
1490 level = embedding_levels[i];
1492 for (i--; i >= off &&
1493 FRIBIDI_IS_EXPLICIT_OR_BN_OR_NSM (bidi_types[i])
1494 && embedding_levels[i] == level; i--)
1497 if (i < off || embedding_levels[i] != level)
1500 DBG ("warning: NSM(s) at the beginning of level run");
1505 bidi_string_reverse (visual_str + i, seq_end - i + 1);
1509 index_array_reverse (map + i, seq_end - i + 1);
1514 /* Find max_level of the line. We don't reuse the paragraph
1515 * max_level, both for a cleaner API, and that the line max_level
1516 * may be far less than paragraph max_level. */
1517 for (i = off + len - 1; i >= off; i--)
1518 if (embedding_levels[i] > max_level)
1519 max_level = embedding_levels[i];
1522 for (level = max_level; level > 0; level--)
1523 for (i = off + len - 1; i >= off; i--)
1524 if (embedding_levels[i] >= level)
1526 /* Find all stretches that are >= level_idx */
1527 register FriBidiStrIndex seq_end = i;
1528 for (i--; i >= off && embedding_levels[i] >= level; i--)
1532 bidi_string_reverse (visual_str + i + 1, seq_end - i);
1534 index_array_reverse (map + i + 1, seq_end - i);
1544 return status ? max_level + 1 : 0;
1547 /* Editor directions:
1548 * vim:textwidth=78:tabstop=8:shiftwidth=2:autoindent:cindent