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 (ptr: 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 (second: 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 (second: 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(size: 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: nodes1->next, nodes2); |
483 | } |
484 | else |
485 | { |
486 | res = nodes2; |
487 | res->next = pairing_nodes_sorted_merge(nodes1, nodes2: 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(source: *nodes, front: &front, back: &back); |
501 | sort_pairing_nodes(nodes: &front); |
502 | sort_pairing_nodes(nodes: &back); |
503 | *nodes = pairing_nodes_sorted_merge(nodes1: front, nodes2: 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(ptr: 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 (pp: 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(s: run_per_isolate_level, c: 0, n: 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 (list: main_run_list); |
844 | |
845 | # if DEBUG |
846 | if UNLIKELY |
847 | (fribidi_debug_status ()) |
848 | { |
849 | print_types_re (pp: main_run_list); |
850 | print_bidi_string (bidi_types, len); |
851 | print_resolved_levels (pp: main_run_list); |
852 | print_resolved_types (pp: 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(list: pp, false, false); |
873 | ppp_next = get_adjacent_run(list: 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 (second: 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 (second: 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 (pp: main_run_list); |
941 | print_resolved_types (pp: 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(list: pp, false, false); |
972 | ppp_next = get_adjacent_run(list: 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 (list: main_run_list); |
1041 | |
1042 | # if DEBUG |
1043 | if UNLIKELY |
1044 | (fribidi_debug_status ()) |
1045 | { |
1046 | print_resolved_levels (pp: main_run_list); |
1047 | print_resolved_types (pp: 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(s: bracket_stack, c: 0, n: sizeof(bracket_stack[0])*num_iso_levels); |
1065 | memset(s: bracket_stack_size, c: 0, n: 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 (size: 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(nodes: pairing_nodes, |
1115 | open: bracket_stack[iso_level][stack_idx], |
1116 | close: 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(nodes: &pairing_nodes); |
1129 | |
1130 | # if DEBUG |
1131 | if UNLIKELY |
1132 | (fribidi_debug_status ()) |
1133 | { |
1134 | print_pairing_nodes (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(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(ptr: 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 (list: main_run_list); |
1220 | } |
1221 | } |
1222 | |
1223 | # if DEBUG |
1224 | if UNLIKELY |
1225 | (fribidi_debug_status ()) |
1226 | { |
1227 | print_resolved_levels (pp: main_run_list); |
1228 | print_resolved_types (pp: 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(list: pp, false, false); |
1241 | ppp_next = get_adjacent_run(list: 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 (list: main_run_list); |
1265 | |
1266 | # if DEBUG |
1267 | if UNLIKELY |
1268 | (fribidi_debug_status ()) |
1269 | { |
1270 | print_resolved_levels (pp: main_run_list); |
1271 | print_resolved_types (pp: 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 (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 (pp: main_run_list); |
1310 | print_resolved_types (pp: 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 (base: main_run_list, over: 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 (pp: main_run_list); |
1341 | print_resolved_levels (pp: main_run_list); |
1342 | print_resolved_types (pp: 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 (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 (pp: main_run_list); |
1407 | print_resolved_levels (pp: main_run_list); |
1408 | print_resolved_types (pp: 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 (run_list: main_run_list); |
1430 | if UNLIKELY |
1431 | (explicits_list) free_run_list (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 (str: visual_str + i, len: seq_end - i + 1); |
1546 | } |
1547 | if (map) |
1548 | { |
1549 | index_array_reverse (arr: map + i, len: 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 (str: visual_str + i + 1, len: seq_end - i); |
1573 | if (map) |
1574 | index_array_reverse (arr: map + i + 1, len: 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 | */ |
1590 | |