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