2 * Unicode Bidirectional Algorithm implementation
4 * Copyright 2003 Shachar Shemesh
5 * Copyright 2007 Maarten Lankhorst
6 * Copyright 2010 CodeWeavers, Aric Stewart
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
22 * Code derived from the modified reference implementation
23 * that was found in revision 17 of http://unicode.org/reports/tr9/
24 * "Unicode Standard Annex #9: THE BIDIRECTIONAL ALGORITHM"
26 * -- Copyright (C) 1999-2005, ASMUS, Inc.
28 * Permission is hereby granted, free of charge, to any person obtaining a
29 * copy of the Unicode data files and any associated documentation (the
30 * "Data Files") or Unicode software and any associated documentation (the
31 * "Software") to deal in the Data Files or Software without restriction,
32 * including without limitation the rights to use, copy, modify, merge,
33 * publish, distribute, and/or sell copies of the Data Files or Software,
34 * and to permit persons to whom the Data Files or Software are furnished
35 * to do so, provided that (a) the above copyright notice(s) and this
36 * permission notice appear with all copies of the Data Files or Software,
37 * (b) both the above copyright notice(s) and this permission notice appear
38 * in associated documentation, and (c) there is clear notice in each
39 * modified Data File or in the Software as well as in the documentation
40 * associated with the Data File(s) or Software that the data or software
48 #include "wine/debug.h"
49 #include "wine/list.h"
51 #include "dwrite_private.h"
53 WINE_DEFAULT_DEBUG_CHANNEL(bidi
);
55 extern const unsigned short bidi_bracket_table
[] DECLSPEC_HIDDEN
;
57 #define ASSERT(x) do { if (!(x)) FIXME("assert failed: %s\n", #x); } while(0)
60 #define odd(x) ((x) & 1)
62 /*------------------------------------------------------------------------
63 Bidirectional Character Types
65 as defined by the Unicode Bidirectional Algorithm Table 3-7.
69 The list of bidirectional character types here is not grouped the
70 same way as the table 3-7, since the numberic values for the types
71 are chosen to keep the state and action tables compact.
72 ------------------------------------------------------------------------*/
76 /* ON MUST be zero, code relies on ON = NI = 0 */
77 ON
= 0, /* Other Neutral */
80 AN
, /* Arabic Number */
81 EN
, /* European Number */
82 AL
, /* Arabic Letter (Right-to-left) */
83 NSM
, /* Non-spacing Mark */
84 CS
, /* Common Separator */
85 ES
, /* European Separator */
86 ET
, /* European Terminator (post/prefix e.g. $ and %) */
89 BN
, /* Boundary neutral (type of RLE etc after explicit levels) */
92 S
, /* Segment Separator (TAB) // used only in L1 */
93 WS
, /* White space // used only in L1 */
94 B
, /* Paragraph Separator (aka as PS) */
96 /* types for explicit controls */
97 RLO
, /* these are used only in X1-X9 */
103 LRI
, /* Isolate formatting characters new with 6.3 */
108 /* resolved types, also resolved directions */
109 NI
= ON
, /* alias, where ON, WS, S and Isolates are treated the same */
112 static const char debug_type
[][4] =
114 "ON", /* Other Neutral */
115 "L", /* Left Letter */
116 "R", /* Right Letter */
117 "AN", /* Arabic Number */
118 "EN", /* European Number */
119 "AL", /* Arabic Letter (Right-to-left) */
120 "NSM", /* Non-spacing Mark */
121 "CS", /* Common Separator */
122 "ES", /* European Separator */
123 "ET", /* European Terminator (post/prefix e.g. $ and %) */
124 "BN", /* Boundary neutral (type of RLE etc after explicit levels) */
125 "S", /* Segment Separator (TAB) used only in L1 */
126 "WS", /* White space used only in L1 */
127 "B", /* Paragraph Separator (aka as PS) */
128 "RLO", /* these are used only in X1-X9 */
133 "LRI", /* Isolate formatting characters new with 6.3 */
139 static inline void bidi_dump_types(const char* header
, const UINT8
*types
, UINT32 start
, UINT32 end
)
142 TRACE("%s:", header
);
143 for (i
= start
; i
< end
&& len
< 200; i
++) {
144 TRACE(" %s", debug_type
[types
[i
]]);
145 len
+= strlen(debug_type
[types
[i
]])+1;
152 /* Convert the libwine information to the direction enum */
153 static void bidi_classify(const WCHAR
*string
, UINT8
*chartype
, UINT32 count
)
155 static const enum directions dir_map
[16] =
157 L
, /* unassigned defaults to L */
172 PDF
/* also LRE, LRO, RLE, RLO */
177 for (i
= 0; i
< count
; ++i
) {
178 chartype
[i
] = dir_map
[get_char_typeW(string
[i
]) >> 12];
180 switch (chartype
[i
]) {
185 case 0x202a: chartype
[i
] = LRE
; break;
186 case 0x202b: chartype
[i
] = RLE
; break;
187 case 0x202c: chartype
[i
] = PDF
; break;
188 case 0x202d: chartype
[i
] = LRO
; break;
189 case 0x202e: chartype
[i
] = RLO
; break;
190 case 0x2066: chartype
[i
] = LRI
; break;
191 case 0x2067: chartype
[i
] = RLI
; break;
192 case 0x2068: chartype
[i
] = FSI
; break;
193 case 0x2069: chartype
[i
] = PDI
; break;
200 WCHAR
bidi_get_mirrored_char(WCHAR ch
)
202 extern const WCHAR wine_mirror_map
[] DECLSPEC_HIDDEN
;
203 return ch
+ wine_mirror_map
[wine_mirror_map
[ch
>> 8] + (ch
& 0xff)];
206 /* RESOLVE EXPLICIT */
208 static inline UINT8
get_greater_even_level(UINT8 level
)
210 return odd(level
) ? level
+ 1 : level
+ 2;
213 static inline UINT8
get_greater_odd_level(UINT8 level
)
215 return odd(level
) ? level
+ 2 : level
+ 1;
218 static inline UINT8
get_embedding_direction(UINT8 level
)
220 return odd(level
) ? R
: L
;
223 /*------------------------------------------------------------------------
224 Function: bidi_resolve_explicit
226 Recursively resolves explicit embedding levels and overrides.
227 Implements rules X1-X9, of the Unicode Bidirectional Algorithm.
229 Input: Base embedding level and direction
232 Output: Array of embedding levels
234 In/Out: Array of direction classes
237 Note: The function uses two simple counters to keep track of
238 matching explicit codes and PDF. Use the default argument for
239 the outermost call. The nesting counter counts the recursion
240 depth and not the embedding level.
241 ------------------------------------------------------------------------*/
242 typedef struct tagStackItem
249 #define push_stack(l,o,i) \
251 stack[stack_top].level = l; \
252 stack[stack_top].override = o; \
253 stack[stack_top].isolate = i;} while(0)
255 #define pop_stack() do { stack_top++; } while(0)
257 #define valid_level(x) (x <= MAX_DEPTH && overflow_isolate_count == 0 && overflow_embedding_count == 0)
259 static void bidi_resolve_explicit(UINT8 baselevel
, UINT8
*classes
, UINT8
*levels
, UINT32 count
)
262 int overflow_isolate_count
= 0;
263 int overflow_embedding_count
= 0;
264 int valid_isolate_count
= 0;
267 StackItem stack
[MAX_DEPTH
+2];
268 int stack_top
= MAX_DEPTH
+1;
270 stack
[stack_top
].level
= baselevel
;
271 stack
[stack_top
].override
= NI
;
272 stack
[stack_top
].isolate
= FALSE
;
274 for (i
= 0; i
< count
; i
++) {
275 UINT8 least_odd
, least_even
;
277 switch (classes
[i
]) {
281 least_odd
= get_greater_odd_level(stack
[stack_top
].level
);
282 levels
[i
] = stack
[stack_top
].level
;
283 if (valid_level(least_odd
))
284 push_stack(least_odd
, NI
, FALSE
);
285 else if (overflow_isolate_count
== 0)
286 overflow_embedding_count
++;
291 least_even
= get_greater_even_level(stack
[stack_top
].level
);
292 levels
[i
] = stack
[stack_top
].level
;
293 if (valid_level(least_even
))
294 push_stack(least_even
, NI
, FALSE
);
295 else if (overflow_isolate_count
== 0)
296 overflow_embedding_count
++;
301 least_odd
= get_greater_odd_level(stack
[stack_top
].level
);
302 levels
[i
] = stack
[stack_top
].level
;
303 if (valid_level(least_odd
))
304 push_stack(least_odd
, R
, FALSE
);
305 else if (overflow_isolate_count
== 0)
306 overflow_embedding_count
++;
311 least_even
= get_greater_even_level(stack
[stack_top
].level
);
312 levels
[i
] = stack
[stack_top
].level
;
313 if (valid_level(least_even
))
314 push_stack(least_even
, L
, FALSE
);
315 else if (overflow_isolate_count
== 0)
316 overflow_embedding_count
++;
321 least_odd
= get_greater_odd_level(stack
[stack_top
].level
);
322 levels
[i
] = stack
[stack_top
].level
;
323 if (valid_level(least_odd
))
325 valid_isolate_count
++;
326 push_stack(least_odd
, NI
, TRUE
);
329 overflow_isolate_count
++;
334 least_even
= get_greater_even_level(stack
[stack_top
].level
);
335 levels
[i
] = stack
[stack_top
].level
;
336 if (valid_level(least_even
))
338 valid_isolate_count
++;
339 push_stack(least_even
, NI
, TRUE
);
342 overflow_isolate_count
++;
352 levels
[i
] = stack
[stack_top
].level
;
353 for (j
= i
+1; j
< count
; j
++)
355 if (classes
[j
] == LRI
|| classes
[j
] == RLI
|| classes
[j
] == FSI
)
360 else if (classes
[j
] == PDI
)
369 if (skipping
) continue;
376 else if (classes
[j
] == R
|| classes
[j
] == AL
)
384 least_odd
= get_greater_odd_level(stack
[stack_top
].level
);
385 if (valid_level(least_odd
))
387 valid_isolate_count
++;
388 push_stack(least_odd
, NI
, TRUE
);
391 overflow_isolate_count
++;
395 least_even
= get_greater_even_level(stack
[stack_top
].level
);
396 if (valid_level(least_even
))
398 valid_isolate_count
++;
399 push_stack(least_even
, NI
, TRUE
);
402 overflow_isolate_count
++;
420 levels
[i
] = stack
[stack_top
].level
;
421 if (stack
[stack_top
].override
!= NI
)
422 classes
[i
] = stack
[stack_top
].override
;
427 if (overflow_isolate_count
) overflow_isolate_count
--;
428 else if (!valid_isolate_count
) {/* do nothing */}
431 overflow_embedding_count
= 0;
432 while (!stack
[stack_top
].isolate
) pop_stack();
434 valid_isolate_count
--;
436 levels
[i
] = stack
[stack_top
].level
;
441 levels
[i
] = stack
[stack_top
].level
;
442 if (overflow_isolate_count
) {/* do nothing */}
443 else if (overflow_embedding_count
) overflow_embedding_count
--;
444 else if (!stack
[stack_top
].isolate
&& stack_top
< (MAX_DEPTH
+1))
450 levels
[i
] = baselevel
;
454 /* X9: Based on 5.2 Retaining Explicit Formatting Characters */
455 for (i
= 0; i
< count
; i
++)
456 if (classes
[i
] == RLE
|| classes
[i
] == LRE
|| classes
[i
] == RLO
|| classes
[i
] == LRO
|| classes
[i
] == PDF
)
460 static inline int get_prev_valid_char_index(const UINT8
*classes
, int index
, int back_fence
)
462 if (index
== -1 || index
== back_fence
) return index
;
464 while (index
> back_fence
&& classes
[index
] == BN
) index
--;
468 static inline int get_next_valid_char_index(const UINT8
*classes
, int index
, int front_fence
)
470 if (index
== front_fence
) return index
;
472 while (index
< front_fence
&& classes
[index
] == BN
) index
++;
476 typedef struct tagRun
483 typedef struct tagRunChar
489 typedef struct tagIsolatedRun
500 static inline int get_next_valid_char_from_run(IsolatedRun
*run
, int index
)
502 if (index
>= (run
->length
-1)) return -1;
504 while (index
< run
->length
&& *run
->item
[index
].class == BN
) index
++;
505 if (index
== run
->length
) return -1;
509 static inline int get_prev_valid_char_from_run(IsolatedRun
*run
, int index
)
511 if (index
<= 0) return -1;
513 while (index
> -1 && *run
->item
[index
].class == BN
) index
--;
517 static inline void iso_dump_types(const char* header
, IsolatedRun
*run
)
522 for (i
= 0; i
< run
->length
&& len
< 200; i
++) {
523 TRACE(" %s", debug_type
[*run
->item
[i
].class]);
524 len
+= strlen(debug_type
[*run
->item
[i
].class])+1;
526 if (i
!= run
->length
)
531 /*------------------------------------------------------------------------
532 Function: bidi_resolve_weak
534 Resolves the directionality of numeric and other weak character types
536 Implements rules X10 and W1-W6 of the Unicode Bidirectional Algorithm.
538 Input: Array of embedding levels
541 In/Out: Array of directional classes
543 Note: On input only these directional classes are expected
544 AL, HL, R, L, ON, BN, NSM, AN, EN, ES, ET, CS,
545 ------------------------------------------------------------------------*/
546 static BOOL
bidi_is_isolate(UINT8
class)
548 return class == LRI
|| class == RLI
|| class == FSI
|| class == PDI
;
551 static void bidi_resolve_weak(IsolatedRun
*iso_run
)
556 for (i
=0; i
< iso_run
->length
; i
++) {
557 if (*iso_run
->item
[i
].class == NSM
) {
558 int j
= get_prev_valid_char_from_run(iso_run
, i
);
560 *iso_run
->item
[i
].class = iso_run
->sos
;
561 else if (bidi_is_isolate(*iso_run
->item
[j
].class))
562 *iso_run
->item
[i
].class = ON
;
564 *iso_run
->item
[i
].class = *iso_run
->item
[j
].class;
569 for (i
= 0; i
< iso_run
->length
; i
++) {
570 if (*iso_run
->item
[i
].class == EN
) {
571 int j
= get_prev_valid_char_from_run(iso_run
, i
);
573 if (*iso_run
->item
[j
].class == R
|| *iso_run
->item
[j
].class == L
|| *iso_run
->item
[j
].class == AL
) {
574 if (*iso_run
->item
[j
].class == AL
)
575 *iso_run
->item
[i
].class = AN
;
578 j
= get_prev_valid_char_from_run(iso_run
, j
);
584 for (i
= 0; i
< iso_run
->length
; i
++) {
585 if (*iso_run
->item
[i
].class == AL
)
586 *iso_run
->item
[i
].class = R
;
590 for (i
= 0; i
< iso_run
->length
; i
++) {
591 if (*iso_run
->item
[i
].class == ES
) {
592 int b
= get_prev_valid_char_from_run(iso_run
, i
);
593 int f
= get_next_valid_char_from_run(iso_run
, i
);
595 if (b
> -1 && f
> -1 && *iso_run
->item
[b
].class == EN
&& *iso_run
->item
[f
].class == EN
)
596 *iso_run
->item
[i
].class = EN
;
598 else if (*iso_run
->item
[i
].class == CS
) {
599 int b
= get_prev_valid_char_from_run(iso_run
, i
);
600 int f
= get_next_valid_char_from_run(iso_run
, i
);
602 if (b
> -1 && f
> -1 && *iso_run
->item
[b
].class == EN
&& *iso_run
->item
[f
].class == EN
)
603 *iso_run
->item
[i
].class = EN
;
604 else if (b
> -1 && f
> -1 && *iso_run
->item
[b
].class == AN
&& *iso_run
->item
[f
].class == AN
)
605 *iso_run
->item
[i
].class = AN
;
610 for (i
= 0; i
< iso_run
->length
; i
++) {
611 if (*iso_run
->item
[i
].class == ET
) {
613 for (j
= i
-1 ; j
> -1; j
--) {
614 if (*iso_run
->item
[j
].class == BN
) continue;
615 if (*iso_run
->item
[j
].class == ET
) continue;
616 else if (*iso_run
->item
[j
].class == EN
) *iso_run
->item
[i
].class = EN
;
619 if (*iso_run
->item
[i
].class == ET
) {
620 for (j
= i
+1; j
< iso_run
->length
; j
++) {
621 if (*iso_run
->item
[j
].class == BN
) continue;
622 if (*iso_run
->item
[j
].class == ET
) continue;
623 else if (*iso_run
->item
[j
].class == EN
) *iso_run
->item
[i
].class = EN
;
631 for (i
= 0; i
< iso_run
->length
; i
++) {
632 if (*iso_run
->item
[i
].class == ET
|| *iso_run
->item
[i
].class == ES
|| *iso_run
->item
[i
].class == CS
|| *iso_run
->item
[i
].class == ON
)
636 if (b
> -1 && *iso_run
->item
[b
].class == BN
)
637 *iso_run
->item
[b
].class = ON
;
638 if (f
< iso_run
->length
&& *iso_run
->item
[f
].class == BN
)
639 *iso_run
->item
[f
].class = ON
;
641 *iso_run
->item
[i
].class = ON
;
646 for (i
= 0; i
< iso_run
->length
; i
++) {
647 if (*iso_run
->item
[i
].class == EN
) {
649 for (j
= get_prev_valid_char_from_run(iso_run
, i
); j
> -1; j
= get_prev_valid_char_from_run(iso_run
, j
))
650 if (*iso_run
->item
[j
].class == R
|| *iso_run
->item
[j
].class == L
) {
651 if (*iso_run
->item
[j
].class == L
)
652 *iso_run
->item
[i
].class = L
;
655 if (iso_run
->sos
== L
&& j
== -1)
656 *iso_run
->item
[i
].class = L
;
661 typedef struct tagBracketPair
667 static int bracketpair_compr(const void *a
, const void* b
)
669 return ((BracketPair
*)a
)->start
- ((BracketPair
*)b
)->start
;
672 static BracketPair
*bidi_compute_bracket_pairs(IsolatedRun
*iso_run
)
676 int stack_top
= iso_run
->length
;
677 BracketPair
*out
= NULL
;
681 open_stack
= heap_alloc(sizeof(WCHAR
) * iso_run
->length
);
682 stack_index
= heap_alloc(sizeof(int) * iso_run
->length
);
684 for (i
= 0; i
< iso_run
->length
; i
++) {
685 unsigned short ubv
= get_table_entry(bidi_bracket_table
, iso_run
->item
[i
].ch
);
688 out
= heap_alloc(sizeof(BracketPair
));
692 if ((ubv
>> 8) == 0) {
694 open_stack
[stack_top
] = iso_run
->item
[i
].ch
+ (signed char)(ubv
& 0xff);
695 /* deal with canonical equivalent U+2329/232A and U+3008/3009 */
696 if (open_stack
[stack_top
] == 0x232A)
697 open_stack
[stack_top
] = 0x3009;
698 stack_index
[stack_top
] = i
;
700 else if ((ubv
>> 8) == 1) {
703 if (stack_top
== iso_run
->length
) continue;
704 for (j
= stack_top
; j
< iso_run
->length
; j
++) {
705 WCHAR c
= iso_run
->item
[i
].ch
;
706 if (c
== 0x232A) c
= 0x3009;
707 if (c
== open_stack
[j
]) {
708 out
[pair_count
].start
= stack_index
[j
];
709 out
[pair_count
].end
= i
;
711 out
= heap_realloc(out
, sizeof(BracketPair
) * (pair_count
+1));
712 out
[pair_count
].start
= -1;
720 if (pair_count
== 0) {
724 else if (pair_count
> 1)
725 qsort(out
, pair_count
, sizeof(BracketPair
), bracketpair_compr
);
727 heap_free(open_stack
);
728 heap_free(stack_index
);
732 static inline UINT8
get_rule_N0_class(UINT8
class)
734 return (class == AN
|| class == EN
) ? R
: class;
737 /*------------------------------------------------------------------------
738 Function: bidi_resolve_neutrals
740 Resolves the directionality of neutral character types.
742 Implements rules N1 and N2 of the Unicode Bidi Algorithm.
744 Input: Array of embedding levels
748 In/Out: Array of directional classes
750 Note: On input only these directional classes are expected
751 R, L, NI, AN, EN and BN
753 W8 resolves a number of ENs to L
754 ------------------------------------------------------------------------*/
755 static void bidi_resolve_neutrals(IsolatedRun
*run
)
760 /* Translate isolates into NI */
761 for (i
= 0; i
< run
->length
; i
++) {
762 switch (*run
->item
[i
].class) {
769 case PDI
: *run
->item
[i
].class = NI
;
772 /* "Only NI, L, R, AN, EN and BN are allowed" */
773 ASSERT(*run
->item
[i
].class <= EN
|| *run
->item
[i
].class == BN
);
776 /* N0: Skipping bracketed pairs for now */
777 pairs
= bidi_compute_bracket_pairs(run
);
779 BracketPair
*p
= pairs
;
781 while (p
->start
>= 0) {
782 UINT8 e
= get_embedding_direction(run
->e
);
783 UINT8 o
= get_embedding_direction(run
->e
+ 1);
787 TRACE("Bracket Pair [%i - %i]\n", p
->start
, p
->end
);
790 for (j
= p
->start
+1; j
< p
->end
; j
++) {
791 if (get_rule_N0_class(*run
->item
[j
].class) == e
) {
792 *run
->item
[p
->start
].class = e
;
793 *run
->item
[p
->end
].class = e
;
796 else if (get_rule_N0_class(*run
->item
[j
].class) == o
)
800 if (j
== p
->end
&& flag_o
) {
801 for (j
= p
->start
; j
>= 0; j
--) {
802 if (get_rule_N0_class(*run
->item
[j
].class) == o
) {
803 *run
->item
[p
->start
].class = o
;
804 *run
->item
[p
->end
].class = o
;
807 else if (get_rule_N0_class(*run
->item
[j
].class) == e
) {
808 *run
->item
[p
->start
].class = e
;
809 *run
->item
[p
->end
].class = e
;
814 *run
->item
[p
->start
].class = run
->sos
;
815 *run
->item
[p
->end
].class = run
->sos
;
826 for (i
= 0; i
< run
->length
; i
++) {
829 if (*run
->item
[i
].class == NI
) {
830 int b
= get_prev_valid_char_from_run(run
, i
);
838 if (*run
->item
[b
].class == R
|| *run
->item
[b
].class == AN
|| *run
->item
[b
].class == EN
)
840 else if (*run
->item
[b
].class == L
)
842 else /* No string type */
845 j
= get_next_valid_char_from_run(run
, i
);
846 while (j
> -1 && *run
->item
[j
].class == NI
) j
= get_next_valid_char_from_run(run
, j
);
851 else if (*run
->item
[j
].class == R
|| *run
->item
[j
].class == AN
|| *run
->item
[j
].class == EN
)
853 else if (*run
->item
[j
].class == L
)
855 else /* No string type */
859 for (b
= i
; b
< j
&& b
< run
->length
; b
++)
860 *run
->item
[b
].class = r
;
866 for (i
= 0; i
< run
->length
; i
++) {
867 if (*run
->item
[i
].class == NI
) {
871 *run
->item
[i
].class = get_embedding_direction(run
->e
);
872 if (b
> -1 && *run
->item
[b
].class == BN
)
873 *run
->item
[b
].class = get_embedding_direction(run
->e
);
874 if (f
< run
->length
&& *run
->item
[f
].class == BN
)
875 *run
->item
[f
].class = get_embedding_direction(run
->e
);
880 /*------------------------------------------------------------------------
881 Function: bidi_resolve_implicit
883 Recursively resolves implicit embedding levels.
884 Implements rules I1 and I2 of the Unicode Bidirectional Algorithm.
886 Input: Array of direction classes
890 In/Out: Array of embedding levels
892 Note: levels may exceed 15 on output.
893 Accepted subset of direction classes
895 ------------------------------------------------------------------------*/
896 static void bidi_resolve_implicit(const UINT8
*classes
, UINT8
*levels
, int sos
, int eos
)
901 for (i
= sos
; i
<= eos
; i
++) {
902 if (classes
[i
] == BN
)
905 ASSERT(classes
[i
] != ON
); /* "No Neutrals allowed to survive here." */
906 ASSERT(classes
[i
] <= EN
); /* "Out of range." */
908 if (odd(levels
[i
]) && (classes
[i
] == L
|| classes
[i
] == EN
|| classes
[i
] == AN
))
910 else if (!odd(levels
[i
]) && classes
[i
] == R
)
912 else if (!odd(levels
[i
]) && (classes
[i
] == EN
|| classes
[i
] == AN
))
917 static inline BOOL
is_rule_L1_reset_class(UINT8
class)
937 static void bidi_resolve_resolved(UINT8 baselevel
, const UINT8
*classes
, UINT8
*levels
, int sos
, int eos
)
942 for (i
= sos
; i
<= eos
; i
++) {
943 if (classes
[i
] == B
|| classes
[i
] == S
) {
945 while (i
> sos
&& j
>= sos
&& is_rule_L1_reset_class(classes
[j
]))
946 levels
[j
--] = baselevel
;
947 levels
[i
] = baselevel
;
949 else if (classes
[i
] == LRE
|| classes
[i
] == RLE
|| classes
[i
] == LRO
|| classes
[i
] == RLO
||
950 classes
[i
] == PDF
|| classes
[i
] == BN
) {
951 levels
[i
] = i
? levels
[i
- 1] : baselevel
;
953 if (i
== eos
&& is_rule_L1_reset_class(classes
[i
])) {
955 while (j
>= sos
&& is_rule_L1_reset_class(classes
[j
]))
956 levels
[j
--] = baselevel
;
961 static HRESULT
bidi_compute_isolating_runs_set(UINT8 baselevel
, UINT8
*classes
, UINT8
*levels
, const WCHAR
*string
, UINT32 count
, struct list
*set
)
963 int run_start
, run_end
, i
;
968 runs
= heap_alloc(count
* sizeof(Run
));
970 return E_OUTOFMEMORY
;
976 while (run_start
< count
) {
977 run_end
= get_next_valid_char_index(classes
, run_start
, count
);
978 while (run_end
< count
&& levels
[run_end
] == levels
[run_start
])
979 run_end
= get_next_valid_char_index(classes
, run_end
, count
);
981 runs
[run_count
].start
= run_start
;
982 runs
[run_count
].end
= run_end
;
983 runs
[run_count
].e
= levels
[run_start
];
984 run_start
= get_next_valid_char_index(classes
, run_end
, count
);
988 /* Build Isolating Runs */
990 while (i
< run_count
) {
992 if (runs
[k
].start
>= 0) {
993 IsolatedRun
*current_isolated
;
994 int type_fence
, real_end
;
997 current_isolated
= heap_alloc(sizeof(IsolatedRun
) + sizeof(RunChar
)*count
);
998 if (!current_isolated
) {
1003 run_start
= runs
[k
].start
;
1004 current_isolated
->e
= runs
[k
].e
;
1005 current_isolated
->length
= (runs
[k
].end
- runs
[k
].start
)+1;
1007 for (j
= 0; j
< current_isolated
->length
; j
++) {
1008 current_isolated
->item
[j
].class = &classes
[runs
[k
].start
+j
];
1009 current_isolated
->item
[j
].ch
= string
[runs
[k
].start
+j
];
1012 run_end
= runs
[k
].end
;
1014 TRACE("{ [%i -- %i]",run_start
, run_end
);
1016 if (classes
[run_end
] == BN
)
1017 run_end
= get_prev_valid_char_index(classes
, run_end
, runs
[k
].start
);
1019 while (run_end
< count
&& (classes
[run_end
] == RLI
|| classes
[run_end
] == LRI
|| classes
[run_end
] == FSI
)) {
1022 while (j
< run_count
&& classes
[runs
[j
].start
] != PDI
) j
++;
1023 if (j
< run_count
&& runs
[i
].e
!= runs
[j
].e
) {
1028 if (j
!= run_count
) {
1029 int l
= current_isolated
->length
;
1032 current_isolated
->length
+= (runs
[j
].end
- runs
[j
].start
)+1;
1033 for (m
= 0; l
< current_isolated
->length
; l
++, m
++) {
1034 current_isolated
->item
[l
].class = &classes
[runs
[j
].start
+m
];
1035 current_isolated
->item
[l
].ch
= string
[runs
[j
].start
+m
];
1038 TRACE("[%i -- %i]", runs
[j
].start
, runs
[j
].end
);
1040 run_end
= runs
[j
].end
;
1041 if (classes
[run_end
] == BN
)
1042 run_end
= get_prev_valid_char_index(classes
, run_end
, runs
[i
].start
);
1052 type_fence
= get_prev_valid_char_index(classes
, run_start
, -1);
1054 if (type_fence
== -1)
1055 current_isolated
->sos
= (baselevel
> levels
[run_start
]) ? baselevel
: levels
[run_start
];
1057 current_isolated
->sos
= (levels
[type_fence
] > levels
[run_start
]) ? levels
[type_fence
] : levels
[run_start
];
1059 current_isolated
->sos
= get_embedding_direction(current_isolated
->sos
);
1061 if (run_end
== count
)
1062 current_isolated
->eos
= current_isolated
->sos
;
1064 /* eos could be an BN */
1065 if (classes
[run_end
] == BN
) {
1066 real_end
= get_prev_valid_char_index(classes
, run_end
, run_start
-1);
1067 if (real_end
< run_start
)
1068 real_end
= run_start
;
1073 type_fence
= get_next_valid_char_index(classes
, run_end
, count
);
1074 if (type_fence
== count
)
1075 current_isolated
->eos
= (baselevel
> levels
[real_end
]) ? baselevel
: levels
[real_end
];
1077 current_isolated
->eos
= (levels
[type_fence
] > levels
[real_end
]) ? levels
[type_fence
] : levels
[real_end
];
1079 current_isolated
->eos
= get_embedding_direction(current_isolated
->eos
);
1082 list_add_tail(set
, ¤t_isolated
->entry
);
1083 TRACE(" } level %i {%s <--> %s}\n", current_isolated
->e
, debug_type
[current_isolated
->sos
], debug_type
[current_isolated
->eos
]);
1092 HRESULT
bidi_computelevels(const WCHAR
*string
, UINT32 count
, UINT8 baselevel
, UINT8
*explicit, UINT8
*levels
)
1094 IsolatedRun
*iso_run
, *next
;
1095 struct list IsolatingRuns
;
1099 TRACE("%s, %u\n", debugstr_wn(string
, count
), count
);
1101 chartype
= heap_alloc(count
*sizeof(*chartype
));
1103 return E_OUTOFMEMORY
;
1105 bidi_classify(string
, chartype
, count
);
1106 if (TRACE_ON(bidi
)) bidi_dump_types("start ", chartype
, 0, count
);
1108 bidi_resolve_explicit(baselevel
, chartype
, levels
, count
);
1109 memcpy(explicit, levels
, count
*sizeof(*explicit));
1111 if (TRACE_ON(bidi
)) bidi_dump_types("after explicit", chartype
, 0, count
);
1113 /* X10/BD13: Compute Isolating runs */
1114 hr
= bidi_compute_isolating_runs_set(baselevel
, chartype
, levels
, string
, count
, &IsolatingRuns
);
1118 LIST_FOR_EACH_ENTRY_SAFE(iso_run
, next
, &IsolatingRuns
, IsolatedRun
, entry
)
1120 if (TRACE_ON(bidi
)) iso_dump_types("run", iso_run
);
1122 bidi_resolve_weak(iso_run
);
1123 if (TRACE_ON(bidi
)) iso_dump_types("after weak", iso_run
);
1125 bidi_resolve_neutrals(iso_run
);
1126 if (TRACE_ON(bidi
)) iso_dump_types("after neutrals", iso_run
);
1128 list_remove(&iso_run
->entry
);
1132 if (TRACE_ON(bidi
)) bidi_dump_types("before implicit", chartype
, 0, count
);
1133 bidi_resolve_implicit(chartype
, levels
, 0, count
-1);
1135 bidi_classify(string
, chartype
, count
);
1136 bidi_resolve_resolved(baselevel
, chartype
, levels
, 0, count
-1);
1139 heap_free(chartype
);