1 /* Low-level bidirectional buffer/string-scanning functions for GNU Emacs.
2 Copyright (C) 2000-2001, 2004-2005, 2009-2017 Free Software
5 This file is part of GNU Emacs.
7 GNU Emacs is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or (at
10 your option) any later version.
12 GNU Emacs is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
20 /* Written by Eli Zaretskii <eliz@gnu.org>.
22 A sequential implementation of the Unicode Bidirectional algorithm,
23 (UBA) as per UAX#9, a part of the Unicode Standard.
25 Unlike the Reference Implementation and most other implementations,
26 this one is designed to be called once for every character in the
27 buffer or string. That way, we can leave intact the design of the
28 Emacs display engine, whereby an iterator object is used to
29 traverse buffer or string text character by character, and generate
30 the necessary data for displaying each character in 'struct glyph'
31 objects. (See xdisp.c for the details of that iteration.) The
32 functions on this file replace the original linear iteration in the
33 logical order of the text with a non-linear iteration in the visual
34 order, i.e. in the order characters should be shown on display.
36 The main entry point is bidi_move_to_visually_next. Each time it
37 is called, it finds the next character in the visual order, and
38 returns its information in a special structure. The caller is then
39 expected to process this character for display or any other
40 purposes, and call bidi_move_to_visually_next for the next
41 character. See the comments in bidi_move_to_visually_next for more
42 details about its algorithm that finds the next visual-order
43 character by resolving their levels on the fly.
45 Two other entry points are bidi_paragraph_init and
46 bidi_mirror_char. The first determines the base direction of a
47 paragraph, while the second returns the mirrored version of its
50 A few auxiliary entry points are used to initialize the bidi
51 iterator for iterating an object (buffer or string), push and pop
52 the bidi iterator state, and save and restore the state of the bidi
55 If you want to understand the code, you will have to read it
56 together with the relevant portions of UAX#9. The comments include
57 references to UAX#9 rules, for that very reason.
59 A note about references to UAX#9 rules: if the reference says
60 something like "X9/Retaining", it means that you need to refer to
61 rule X9 and to its modifications described in the "Implementation
62 Notes" section of UAX#9, under "Retaining Format Codes".
64 Here's the overview of the design of the reordering engine
65 implemented by this file.
67 Basic implementation structure
68 ------------------------------
70 The sequential processing steps described by UAX#9 are implemented
71 as recursive levels of processing, all of which examine the next
72 character in the logical order. This hierarchy of processing looks
73 as follows, from the innermost (deepest) to the outermost level,
74 omitting some subroutines used by each level:
76 bidi_fetch_char -- fetch next character
77 bidi_resolve_explicit -- resolve explicit levels and directions
78 bidi_resolve_weak -- resolve weak types
79 bidi_resolve_brackets -- resolve "paired brackets" neutral types
80 bidi_resolve_neutral -- resolve neutral types
81 bidi_level_of_next_char -- resolve implicit levels
83 Each level calls the level below it, and works on the result
84 returned by the lower level, including all of its sub-levels.
86 Unlike all the levels below it, bidi_level_of_next_char can return
87 the information about either the next or previous character in the
88 logical order, depending on the current direction of scanning the
89 buffer or string. For the next character, it calls all the levels
90 below it; for the previous character, it uses the cache, described
93 Thus, the result of calling bidi_level_of_next_char is the resolved
94 level of the next or the previous character in the logical order.
95 Based on this information, the function bidi_move_to_visually_next
96 finds the next character in the visual order and updates the
97 direction in which the buffer is scanned, either forward or
98 backward, to find the next character to be displayed. (Text is
99 scanned backwards when it needs to be reversed for display, i.e. if
100 the visual order is the inverse of the logical order.) This
101 implements the last, reordering steps of the UBA, by successively
102 calling bidi_level_of_next_char until the character of the required
103 embedding level is found; the scan direction is dynamically updated
104 as a side effect. See the commentary before the 'while' loop in
105 bidi_move_to_visually_next, for the details.
110 In a nutshell, fetching the next character boils down to calling
111 STRING_CHAR_AND_LENGTH, passing it the address of a buffer or
112 string position. See bidi_fetch_char. However, if the next
113 character is "covered" by a display property of some kind,
114 bidi_fetch_char returns the u+FFFC "object replacement character"
115 that represents the entire run of text covered by the display
116 property. (The ch_len and nchars members of 'struct bidi_it'
117 reflect the length in bytes and characters of that text.) This is
118 so we reorder text on both sides of the display property as
119 appropriate for an image or embedded string. Similarly, text
120 covered by a display spec of the form '(space ...)', is replaced
121 with the u+2029 paragraph separator character, so such display
122 specs produce the same effect as a TAB under UBA. Both these
123 special characters are not actually displayed -- the display
124 property is displayed instead -- but just used to compute the
125 embedding level of the surrounding text so as to produce the
131 The UBA is highly context dependent in some of its parts,
132 i.e. results of processing a character can generally depend on
133 characters very far away. The UAX#9 description of the UBA
134 prescribes a stateful processing of each character, whereby the
135 results of this processing depend on various state variables, such
136 as the current embedding level, level stack, and directional
137 override status. In addition, the UAX#9 description includes many
138 passages like this (from rule W2 in this case):
140 Search backward from each instance of a European number until the
141 first strong type (R, L, AL, or sos) is found. If an AL is found,
142 change the type of the European number to Arabic number.
144 To support this, we use a bidi iterator object, 'struct bidi_it',
145 which is a sub-structure of 'struct it' used by xdisp.c (see
146 dispextern.h for the definition of both of these structures). The
147 bidi iterator holds the entire state of the iteration required by
148 the UBA, and is updated as the text is traversed. In particular,
149 the embedding level of the current character being resolved is
150 recorded in the iterator state. To avoid costly searches backward
151 in support of rules like W2 above, the necessary character types
152 are also recorded in the iterator state as they are found during
153 the forward scan, and then used when such rules need to be applied.
154 (Forward scans cannot be avoided in this way; they need to be
155 performed at least once, and the results recorded in the iterator
156 state, to be reused until the forward scan oversteps the recorded
159 In this manner, the iterator state acts as a mini-cache of
160 contextual information required for resolving the level of the
161 current character by various UBA rules.
163 Caching of bidi iterator states
164 -------------------------------
166 As described above, the reordering engine uses the information
167 recorded in the bidi iterator state in order to resolve the
168 embedding level of the current character. When the reordering
169 engine needs to process the next character in the logical order, it
170 fetches it and applies to it all the UBA levels, updating the
171 iterator state as it goes. But when the buffer or string is
172 scanned backwards, i.e. in the reverse order of buffer/string
173 positions, the scanned characters were already processed during the
174 preceding forward scan (see bidi_find_other_level_edge). To avoid
175 costly re-processing of characters that were already processed
176 during the forward scan, the iterator states computed while
177 scanning forward are cached.
179 The cache is just a linear array of 'struct bidi_it' objects, which
180 is dynamically allocated and reallocated as needed, since the size
181 of the cache depends on the text being processed. We only need the
182 cache while processing embedded levels higher than the base
183 paragraph embedding level, because these higher levels require
184 changes in scan direction. Therefore, as soon as we are back to
185 the base embedding level, we can free the cache; see the calls to
186 bidi_cache_reset and bidi_cache_shrink, for the conditions to do
189 The cache maintains the index of the next unused cache slot -- this
190 is where the next iterator state will be cached. The function
191 bidi_cache_iterator_state saves an instance of the state in the
192 cache and increments the unused slot index. The companion function
193 bidi_cache_find looks up a cached state that corresponds to a given
194 buffer/string position. All of the cached states must correspond
195 1:1 to the buffer or string region whose processing they reflect;
196 bidi.c will abort if it finds cache slots that violate this 1:1
199 When the parent iterator 'struct it' is pushed (see push_it in
200 xdisp.c) to pause the current iteration and start iterating over a
201 different object (e.g., a 'display' string that covers some buffer
202 text), the bidi iterator cache needs to be "pushed" as well, so
203 that a new empty cache could be used while iterating over the new
204 object. Later, when the new object is exhausted, and xdisp.c calls
205 pop_it, we need to "pop" the bidi cache as well and return to the
206 original cache. See bidi_push_it and bidi_pop_it for how this is
209 Some functions of the display engine save copies of 'struct it' in
210 local variables, and restore them later. For examples, see
211 pos_visible_p and move_it_in_display_line_to in xdisp.c, and
212 window_scroll_pixel_based in window.c. When this happens, we need
213 to save and restore the bidi cache as well, because conceptually
214 the cache is part of the 'struct it' state, and needs to be in
215 perfect sync with the portion of the buffer/string that is being
216 processed. This saving and restoring of the cache state is handled
217 by bidi_shelve_cache and bidi_unshelve_cache, and the helper macros
218 SAVE_IT and RESTORE_IT defined on xdisp.c.
220 Note that, because reordering is implemented below the level in
221 xdisp.c that breaks glyphs into screen lines, we are violating
222 paragraph 3.4 of UAX#9. which mandates that line breaking shall be
223 done before reordering each screen line separately. However,
224 following UAX#9 to the letter in this matter goes against the basic
225 design of the Emacs display engine, and so we choose here this
226 minor deviation from the UBA letter in preference to redesign of
227 the display engine. The effect of this is only seen in continued
228 lines that are broken into screen lines in the middle of a run
229 whose direction is opposite to the paragraph's base direction.
231 Important design and implementation note: when the code needs to
232 scan far ahead, be sure to avoid such scans as much as possible
233 when the buffer/string doesn't contain any RTL characters. Users
234 of left-to-right scripts will never forgive you if you introduce
235 some slow-down due to bidi in situations that don't involve any
236 bidirectional text. See the large comment near the beginning of
237 bidi_resolve_neutral, for one situation where such shortcut was
244 #include "character.h"
246 #include "dispextern.h"
247 #include "region-cache.h"
249 static bool bidi_initialized
= 0;
251 static Lisp_Object bidi_type_table
, bidi_mirror_table
, bidi_brackets_table
;
253 #define BIDI_EOB (-1)
255 /* Data type for describing the bidirectional character categories. */
264 static Lisp_Object paragraph_start_re
, paragraph_separate_re
;
267 /***********************************************************************
269 ***********************************************************************/
271 /* Return the bidi type of a character CH, subject to the current
272 directional OVERRIDE. */
274 bidi_get_type (int ch
, bidi_dir_t override
)
276 bidi_type_t default_type
;
280 if (ch
< 0 || ch
> MAX_CHAR
)
283 default_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
284 /* Every valid character code, even those that are unassigned by the
285 UCD, have some bidi-class property, according to
286 DerivedBidiClass.txt file. Therefore, if we ever get UNKNOWN_BT
287 (= zero) code from CHAR_TABLE_REF, that's a bug. */
288 if (default_type
== UNKNOWN_BT
)
291 switch (default_type
)
308 else if (override
== R2L
)
316 bidi_check_type (bidi_type_t type
)
318 eassert (UNKNOWN_BT
<= type
&& type
<= NEUTRAL_ON
);
321 /* Given a bidi TYPE of a character, return its category. */
322 static bidi_category_t
323 bidi_get_category (bidi_type_t type
)
355 return EXPLICIT_FORMATTING
;
362 bidi_isolate_fmt_char (bidi_type_t ch_type
)
364 return (ch_type
== LRI
|| ch_type
== RLI
|| ch_type
== PDI
|| ch_type
== FSI
);
367 /* Return the mirrored character of C, if it has one. If C has no
368 mirrored counterpart, return C.
369 Note: The conditions in UAX#9 clause L4 regarding the surrounding
370 context must be tested by the caller. */
372 bidi_mirror_char (int c
)
378 if (c
< 0 || c
> MAX_CHAR
)
381 val
= CHAR_TABLE_REF (bidi_mirror_table
, c
);
386 /* When debugging, check before assigning to V, so that the check
387 isn't broken by undefined behavior due to int overflow. */
388 eassert (CHAR_VALID_P (XINT (val
)));
392 /* Minimal test we must do in optimized builds, to prevent weird
393 crashes further down the road. */
394 if (v
< 0 || v
> MAX_CHAR
)
403 /* Return the Bidi_Paired_Bracket_Type property of the character C. */
404 static bidi_bracket_type_t
405 bidi_paired_bracket_type (int c
)
408 return BIDI_BRACKET_NONE
;
409 if (c
< 0 || c
> MAX_CHAR
)
412 return (bidi_bracket_type_t
) XINT (CHAR_TABLE_REF (bidi_brackets_table
, c
));
415 /* Determine the start-of-sequence (sos) directional type given the two
416 embedding levels on either side of the run boundary. Also, update
417 the saved info about previously seen characters, since that info is
418 generally valid for a single level run. */
420 bidi_set_sos_type (struct bidi_it
*bidi_it
, int level_before
, int level_after
)
422 int higher_level
= (level_before
> level_after
? level_before
: level_after
);
424 /* FIXME: should the default sos direction be user selectable? */
425 bidi_it
->sos
= ((higher_level
& 1) != 0 ? R2L
: L2R
); /* X10 */
427 bidi_it
->prev
.type
= UNKNOWN_BT
;
428 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
429 bidi_it
->prev_for_neutral
.type
= (bidi_it
->sos
== R2L
? STRONG_R
: STRONG_L
);
430 bidi_it
->prev_for_neutral
.charpos
= bidi_it
->charpos
;
431 bidi_it
->next_for_neutral
.type
432 = bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
435 #define ISOLATE_STATUS(BIDI_IT, IDX) ((BIDI_IT)->level_stack[IDX].flags & 1)
436 #define OVERRIDE(BIDI_IT, IDX) (((BIDI_IT)->level_stack[IDX].flags >> 1) & 3)
438 /* Push the current embedding level and override status; reset the
439 current level to LEVEL and the current override status to OVERRIDE. */
441 bidi_push_embedding_level (struct bidi_it
*bidi_it
,
442 int level
, bidi_dir_t override
, bool isolate_status
)
444 struct bidi_stack
*st
;
445 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
447 bidi_it
->stack_idx
++;
448 eassert (bidi_it
->stack_idx
< BIDI_MAXDEPTH
+2+1);
449 st
= &bidi_it
->level_stack
[bidi_it
->stack_idx
];
450 eassert (level
<= (1 << 7));
452 st
->flags
= (((override
& 3) << 1) | (isolate_status
!= 0));
455 st
->last_strong_type
= bidi_it
->last_strong
.type
;
456 st
->prev_for_neutral_type
= bidi_it
->prev_for_neutral
.type
;
457 st
->next_for_neutral_type
= bidi_it
->next_for_neutral
.type
;
458 st
->next_for_neutral_pos
= bidi_it
->next_for_neutral
.charpos
;
459 st
->flags
|= ((bidi_it
->sos
== L2R
? 0 : 1) << 3);
461 /* We've got a new isolating sequence, compute the directional type
462 of sos and initialize per-sequence variables (UAX#9, clause X10). */
463 bidi_set_sos_type (bidi_it
, prev_level
, level
);
466 /* Pop from the stack the embedding level, the directional override
467 status, and optionally saved information for the isolating run
468 sequence. Return the new level. */
470 bidi_pop_embedding_level (struct bidi_it
*bidi_it
)
474 /* UAX#9 says to ignore invalid PDFs (X7, last bullet)
475 and PDIs (X6a, 2nd bullet). */
476 if (bidi_it
->stack_idx
> 0)
478 bool isolate_status
= ISOLATE_STATUS (bidi_it
, bidi_it
->stack_idx
);
479 int old_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
481 struct bidi_stack st
;
483 st
= bidi_it
->level_stack
[bidi_it
->stack_idx
];
486 bidi_dir_t sos
= ((st
.flags
>> 3) & 1);
487 /* PREV is used in W1 for resolving WEAK_NSM. By the time
488 we get to an NSM, we must have gotten past at least one
489 character: the PDI that ends the isolate from which we
490 are popping here. So PREV will have been filled up by
491 the time we first use it. We initialize it here to
492 UNKNOWN_BT to be able to catch any blunders in this
494 bidi_it
->prev
.orig_type
= bidi_it
->prev
.type
= UNKNOWN_BT
;
495 bidi_it
->last_strong
.type
= st
.last_strong_type
;
496 bidi_it
->prev_for_neutral
.type
= st
.prev_for_neutral_type
;
497 bidi_it
->next_for_neutral
.type
= st
.next_for_neutral_type
;
498 bidi_it
->next_for_neutral
.charpos
= st
.next_for_neutral_pos
;
499 bidi_it
->sos
= (sos
== 0 ? L2R
: R2L
);
502 bidi_set_sos_type (bidi_it
, old_level
,
503 bidi_it
->level_stack
[bidi_it
->stack_idx
- 1].level
);
505 bidi_it
->stack_idx
--;
507 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
508 eassert (0 <= level
&& level
<= BIDI_MAXDEPTH
+ 1);
512 /* Record in SAVED_INFO the information about the current character. */
514 bidi_remember_char (struct bidi_saved_info
*saved_info
,
515 struct bidi_it
*bidi_it
, bool from_type
)
517 saved_info
->charpos
= bidi_it
->charpos
;
519 saved_info
->type
= bidi_it
->type
;
521 saved_info
->type
= bidi_it
->type_after_wn
;
522 bidi_check_type (saved_info
->type
);
523 saved_info
->orig_type
= bidi_it
->orig_type
;
524 bidi_check_type (saved_info
->orig_type
);
527 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
528 copies the part of the level stack that is actually in use. */
530 bidi_copy_it (struct bidi_it
*to
, struct bidi_it
*from
)
532 /* Copy everything from the start through the active part of
535 (offsetof (struct bidi_it
, level_stack
) + sizeof from
->level_stack
[0]
536 + from
->stack_idx
* sizeof from
->level_stack
[0]));
540 /***********************************************************************
541 Caching the bidi iterator states
542 ***********************************************************************/
544 /* We allocate and de-allocate the cache in chunks of this size (in
545 characters). 200 was chosen as an upper limit for reasonably-long
546 lines in a text file/buffer. */
547 #define BIDI_CACHE_CHUNK 200
548 /* Maximum size we allow the cache to become, per iterator stack slot,
549 in units of struct bidi_it size. If we allow unlimited growth, we
550 could run out of memory for pathologically long bracketed text or
551 very long text lines that need to be reordered. This is aggravated
552 when word-wrap is in effect, since then functions display_line and
553 move_it_in_display_line_to need to keep up to 4 copies of the
556 This limitation means there can be no more than that amount of
557 contiguous RTL text on any single physical line in a LTR paragraph,
558 and similarly with contiguous LTR + numeric text in a RTL
559 paragraph. (LTR text in a LTR paragraph and RTL text in a RTL
560 paragraph are not reordered, and so don't need the cache, and
561 cannot hit this limit.) More importantly, no single line can have
562 text longer than this inside paired brackets (because bracket pairs
563 resolution uses the cache). If the limit is exceeded, the fallback
564 code will produce visual order that will be incorrect if there are
565 RTL characters in the offending line of text. */
566 /* Do we need to allow customization of this limit? */
567 #define BIDI_CACHE_MAX_ELTS_PER_SLOT 50000
568 verify (BIDI_CACHE_CHUNK
< BIDI_CACHE_MAX_ELTS_PER_SLOT
);
569 static ptrdiff_t bidi_cache_max_elts
= BIDI_CACHE_MAX_ELTS_PER_SLOT
;
570 static struct bidi_it
*bidi_cache
;
571 static ptrdiff_t bidi_cache_size
= 0;
572 enum { elsz
= sizeof (struct bidi_it
) };
573 static ptrdiff_t bidi_cache_idx
; /* next unused cache slot */
574 static ptrdiff_t bidi_cache_last_idx
; /* slot of last cache hit */
575 static ptrdiff_t bidi_cache_start
= 0; /* start of cache for this
578 /* 5-slot stack for saving the start of the previous level of the
579 cache. xdisp.c maintains a 5-slot stack for its iterator state,
580 and we need the same size of our stack. */
581 static ptrdiff_t bidi_cache_start_stack
[IT_STACK_SIZE
];
582 static int bidi_cache_sp
;
584 /* Size of header used by bidi_shelve_cache. */
587 bidi_shelve_header_size
588 = (sizeof (bidi_cache_idx
) + sizeof (bidi_cache_start_stack
)
589 + sizeof (bidi_cache_sp
) + sizeof (bidi_cache_start
)
590 + sizeof (bidi_cache_last_idx
) + sizeof (bidi_cache_max_elts
))
593 /* Effectively remove the cached states beyond the Nth state from the
594 part of the cache relevant to iteration of the current object
595 (buffer or string). */
597 bidi_cache_reset_to (int n
)
599 bidi_cache_idx
= bidi_cache_start
+ n
;
600 bidi_cache_last_idx
= -1;
603 /* Reset the cache state to the empty state. We only reset the part
604 of the cache relevant to iteration of the current object. Previous
605 objects, which are pushed on the display iterator's stack, are left
606 intact. This is called when the cached information is no more
607 useful for the current iteration, e.g. when we were reseated to a
608 new position on the same object. */
610 bidi_cache_reset (void)
612 bidi_cache_reset_to (0);
615 /* Shrink the cache to its minimal size. Called when we init the bidi
616 iterator for reordering a buffer or a string that does not come
617 from display properties, because that means all the previously
618 cached info is of no further use. */
620 bidi_cache_shrink (void)
622 if (bidi_cache_size
> BIDI_CACHE_CHUNK
)
624 bidi_cache
= xrealloc (bidi_cache
, BIDI_CACHE_CHUNK
* elsz
);
625 bidi_cache_size
= BIDI_CACHE_CHUNK
;
628 bidi_cache_max_elts
= BIDI_CACHE_MAX_ELTS_PER_SLOT
;
632 bidi_cache_fetch_state (ptrdiff_t idx
, struct bidi_it
*bidi_it
)
634 int current_scan_dir
= bidi_it
->scan_dir
;
636 if (idx
< bidi_cache_start
|| idx
>= bidi_cache_idx
)
639 bidi_copy_it (bidi_it
, &bidi_cache
[idx
]);
640 bidi_it
->scan_dir
= current_scan_dir
;
641 bidi_cache_last_idx
= idx
;
644 /* Find a cached state with a given CHARPOS and resolved embedding
645 level less or equal to LEVEL. If LEVEL is -1, disregard the
646 resolved levels in cached states. DIR, if non-zero, means search
647 in that direction from the last cache hit.
649 Value is the index of the cached state, or -1 if not found. */
651 bidi_cache_search (ptrdiff_t charpos
, int level
, int dir
)
653 ptrdiff_t i
, i_start
;
655 if (bidi_cache_idx
> bidi_cache_start
)
657 if (bidi_cache_last_idx
== -1)
658 bidi_cache_last_idx
= bidi_cache_idx
- 1;
659 if (charpos
< bidi_cache
[bidi_cache_last_idx
].charpos
)
662 i_start
= bidi_cache_last_idx
- 1;
664 else if (charpos
> (bidi_cache
[bidi_cache_last_idx
].charpos
665 + bidi_cache
[bidi_cache_last_idx
].nchars
- 1))
668 i_start
= bidi_cache_last_idx
+ 1;
671 i_start
= bidi_cache_last_idx
;
675 i_start
= bidi_cache_idx
- 1;
680 /* Linear search for now; FIXME! */
681 for (i
= i_start
; i
>= bidi_cache_start
; i
--)
682 if (bidi_cache
[i
].charpos
<= charpos
683 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
684 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
689 for (i
= i_start
; i
< bidi_cache_idx
; i
++)
690 if (bidi_cache
[i
].charpos
<= charpos
691 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
692 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
700 /* Find a cached state where the resolved level changes to a value
701 that is lower than LEVEL, and return its cache slot index. DIR is
702 the direction to search, starting with the last used cache slot.
703 If DIR is zero, we search backwards from the last occupied cache
704 slot. BEFORE means return the index of the slot that
705 is ``before'' the level change in the search direction. That is,
706 given the cached levels like this:
711 and assuming we are at the position cached at the slot marked with
712 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
713 index of slot B or A, depending whether BEFORE is, respectively,
716 bidi_cache_find_level_change (int level
, int dir
, bool before
)
720 ptrdiff_t i
= dir
? bidi_cache_last_idx
: bidi_cache_idx
- 1;
721 int incr
= before
? 1 : 0;
723 if (i
< 0) /* cache overflowed? */
733 while (i
>= bidi_cache_start
+ incr
)
735 if (bidi_cache
[i
- incr
].resolved_level
>= 0
736 && bidi_cache
[i
- incr
].resolved_level
< level
)
743 while (i
< bidi_cache_idx
- incr
)
745 if (bidi_cache
[i
+ incr
].resolved_level
>= 0
746 && bidi_cache
[i
+ incr
].resolved_level
< level
)
757 bidi_cache_ensure_space (ptrdiff_t idx
)
759 /* Enlarge the cache as needed. */
760 if (idx
>= bidi_cache_size
)
762 ptrdiff_t chunk_size
= BIDI_CACHE_CHUNK
;
764 if (bidi_cache_size
> bidi_cache_max_elts
- chunk_size
)
765 chunk_size
= bidi_cache_max_elts
- bidi_cache_size
;
768 bidi_cache_size
+ chunk_size
) <= bidi_cache_max_elts
)
770 /* The bidi cache cannot be larger than the largest Lisp
772 ptrdiff_t string_or_buffer_bound
773 = max (BUF_BYTES_MAX
, STRING_BYTES_BOUND
);
775 /* Also, it cannot be larger than what C can represent. */
777 = (min (PTRDIFF_MAX
, SIZE_MAX
) - bidi_shelve_header_size
) / elsz
;
778 ptrdiff_t max_elts
= bidi_cache_max_elts
;
780 max_elts
= min (max_elts
, min (string_or_buffer_bound
, c_bound
));
782 /* Force xpalloc not to over-allocate by passing it MAX_ELTS
783 as its 4th argument. */
784 bidi_cache
= xpalloc (bidi_cache
, &bidi_cache_size
,
785 max (chunk_size
, idx
- bidi_cache_size
+ 1),
787 eassert (bidi_cache_size
> idx
);
793 bidi_cache_iterator_state (struct bidi_it
*bidi_it
, bool resolved
,
798 /* We should never cache on backward scans. */
799 if (bidi_it
->scan_dir
== -1)
801 idx
= bidi_cache_search (bidi_it
->charpos
, -1, 1);
803 if (idx
< 0 && update_only
)
808 idx
= bidi_cache_idx
;
809 bidi_cache_ensure_space (idx
);
810 /* Character positions should correspond to cache positions 1:1.
811 If we are outside the range of cached positions, the cache is
812 useless and must be reset. */
813 if (bidi_cache_start
< idx
&& idx
< bidi_cache_size
814 && (bidi_it
->charpos
> (bidi_cache
[idx
- 1].charpos
815 + bidi_cache
[idx
- 1].nchars
)
816 || bidi_it
->charpos
< bidi_cache
[bidi_cache_start
].charpos
))
819 idx
= bidi_cache_start
;
821 if (bidi_it
->nchars
<= 0)
823 /* Don't cache if no available space in the cache. */
824 if (bidi_cache_size
> idx
)
826 bidi_copy_it (&bidi_cache
[idx
], bidi_it
);
828 bidi_cache
[idx
].resolved_level
= -1;
833 /* Copy only the members which could have changed, to avoid
834 costly copying of the entire struct. */
835 bidi_cache
[idx
].type
= bidi_it
->type
;
836 bidi_check_type (bidi_it
->type
);
837 bidi_cache
[idx
].type_after_wn
= bidi_it
->type_after_wn
;
838 bidi_check_type (bidi_it
->type_after_wn
);
840 bidi_cache
[idx
].resolved_level
= bidi_it
->resolved_level
;
842 bidi_cache
[idx
].resolved_level
= -1;
843 bidi_cache
[idx
].invalid_levels
= bidi_it
->invalid_levels
;
844 bidi_cache
[idx
].next_for_neutral
= bidi_it
->next_for_neutral
;
845 bidi_cache
[idx
].next_for_ws
= bidi_it
->next_for_ws
;
846 bidi_cache
[idx
].disp_pos
= bidi_it
->disp_pos
;
847 bidi_cache
[idx
].disp_prop
= bidi_it
->disp_prop
;
848 bidi_cache
[idx
].bracket_pairing_pos
= bidi_it
->bracket_pairing_pos
;
849 bidi_cache
[idx
].bracket_enclosed_type
= bidi_it
->bracket_enclosed_type
;
852 if (bidi_cache_size
> idx
)
854 bidi_cache_last_idx
= idx
;
855 if (idx
>= bidi_cache_idx
)
856 bidi_cache_idx
= idx
+ 1;
861 /* The cache overflowed. */
862 bidi_cache_last_idx
= -1;
867 /* Look for a cached iterator state that corresponds to CHARPOS. If
868 found, copy the cached state into BIDI_IT and return the type of
869 the cached entry. If not found, return UNKNOWN_BT. RESOLVED_ONLY
870 zero means it is OK to return cached states that were not fully
871 resolved yet. This can happen if the state was cached before it
872 was resolved in bidi_resolve_neutral. */
874 bidi_cache_find (ptrdiff_t charpos
, bool resolved_only
, struct bidi_it
*bidi_it
)
876 ptrdiff_t i
= bidi_cache_search (charpos
, -1, bidi_it
->scan_dir
);
878 if (i
>= bidi_cache_start
880 /* Callers that want only fully resolved states (and set
881 resolved_only = true) need to be sure that there's enough
882 info in the cached state to return the state as final,
883 and if not, they don't want the cached state. */
884 || bidi_cache
[i
].resolved_level
>= 0))
886 bidi_dir_t current_scan_dir
= bidi_it
->scan_dir
;
888 bidi_copy_it (bidi_it
, &bidi_cache
[i
]);
889 bidi_cache_last_idx
= i
;
890 /* Don't let scan direction from the cached state override
891 the current scan direction. */
892 bidi_it
->scan_dir
= current_scan_dir
;
893 return bidi_it
->type
;
900 bidi_peek_at_next_level (struct bidi_it
*bidi_it
)
902 if (bidi_cache_idx
== bidi_cache_start
)
904 /* If the cache overflowed, return the level of the last cached
906 if (bidi_cache_last_idx
== -1
907 || (bidi_cache_last_idx
>= bidi_cache_idx
- 1 && bidi_it
->scan_dir
> 0))
908 return bidi_cache
[bidi_cache_idx
- 1].resolved_level
;
909 return bidi_cache
[bidi_cache_last_idx
+ bidi_it
->scan_dir
].resolved_level
;
913 /***********************************************************************
914 Pushing and popping the bidi iterator state
915 ***********************************************************************/
917 /* Push the bidi iterator state in preparation for reordering a
918 different object, e.g. display string found at certain buffer
919 position. Pushing the bidi iterator boils down to saving its
920 entire state on the cache and starting a new cache "stacked" on top
921 of the current cache. */
923 bidi_push_it (struct bidi_it
*bidi_it
)
925 /* Give this stack slot its cache room. */
926 bidi_cache_max_elts
+= BIDI_CACHE_MAX_ELTS_PER_SLOT
;
927 /* Save the current iterator state in its entirety after the last
929 bidi_cache_ensure_space (bidi_cache_idx
);
930 bidi_cache
[bidi_cache_idx
++] = *bidi_it
;
932 /* Push the current cache start onto the stack. */
933 eassert (bidi_cache_sp
< IT_STACK_SIZE
);
934 bidi_cache_start_stack
[bidi_cache_sp
++] = bidi_cache_start
;
936 /* Start a new level of cache, and make it empty. */
937 bidi_cache_start
= bidi_cache_idx
;
938 bidi_cache_last_idx
= -1;
941 /* Restore the iterator state saved by bidi_push_it and return the
942 cache to the corresponding state. */
944 bidi_pop_it (struct bidi_it
*bidi_it
)
946 if (bidi_cache_start
<= 0)
949 /* Reset the next free cache slot index to what it was before the
950 call to bidi_push_it. */
951 bidi_cache_idx
= bidi_cache_start
- 1;
953 /* Restore the bidi iterator state saved in the cache. */
954 *bidi_it
= bidi_cache
[bidi_cache_idx
];
956 /* Pop the previous cache start from the stack. */
957 if (bidi_cache_sp
<= 0)
959 bidi_cache_start
= bidi_cache_start_stack
[--bidi_cache_sp
];
961 /* Invalidate the last-used cache slot data. */
962 bidi_cache_last_idx
= -1;
964 bidi_cache_max_elts
-= BIDI_CACHE_MAX_ELTS_PER_SLOT
;
965 eassert (bidi_cache_max_elts
> 0);
968 static ptrdiff_t bidi_cache_total_alloc
;
970 /* Stash away a copy of the cache and its control variables. */
972 bidi_shelve_cache (void)
974 unsigned char *databuf
;
978 if (bidi_cache_idx
== 0)
981 alloc
= (bidi_shelve_header_size
982 + bidi_cache_idx
* sizeof (struct bidi_it
));
983 databuf
= xmalloc (alloc
);
984 bidi_cache_total_alloc
+= alloc
;
986 memcpy (databuf
, &bidi_cache_idx
, sizeof (bidi_cache_idx
));
987 memcpy (databuf
+ sizeof (bidi_cache_idx
),
988 bidi_cache
, bidi_cache_idx
* sizeof (struct bidi_it
));
989 memcpy (databuf
+ sizeof (bidi_cache_idx
)
990 + bidi_cache_idx
* sizeof (struct bidi_it
),
991 bidi_cache_start_stack
, sizeof (bidi_cache_start_stack
));
992 memcpy (databuf
+ sizeof (bidi_cache_idx
)
993 + bidi_cache_idx
* sizeof (struct bidi_it
)
994 + sizeof (bidi_cache_start_stack
),
995 &bidi_cache_sp
, sizeof (bidi_cache_sp
));
996 memcpy (databuf
+ sizeof (bidi_cache_idx
)
997 + bidi_cache_idx
* sizeof (struct bidi_it
)
998 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
999 &bidi_cache_start
, sizeof (bidi_cache_start
));
1000 memcpy (databuf
+ sizeof (bidi_cache_idx
)
1001 + bidi_cache_idx
* sizeof (struct bidi_it
)
1002 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
1003 + sizeof (bidi_cache_start
),
1004 &bidi_cache_last_idx
, sizeof (bidi_cache_last_idx
));
1005 memcpy (databuf
+ sizeof (bidi_cache_idx
)
1006 + bidi_cache_idx
* sizeof (struct bidi_it
)
1007 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
1008 + sizeof (bidi_cache_start
) + sizeof (bidi_cache_last_idx
),
1009 &bidi_cache_max_elts
, sizeof (bidi_cache_max_elts
));
1014 /* Restore the cache state from a copy stashed away by
1015 bidi_shelve_cache, and free the buffer used to stash that copy.
1016 JUST_FREE means free the buffer, but don't restore the
1017 cache; used when the corresponding iterator is discarded instead of
1020 bidi_unshelve_cache (void *databuf
, bool just_free
)
1022 unsigned char *p
= databuf
;
1028 /* A NULL pointer means an empty cache. */
1029 bidi_cache_start
= 0;
1031 bidi_cache_max_elts
= BIDI_CACHE_MAX_ELTS_PER_SLOT
;
1032 bidi_cache_reset ();
1041 memcpy (&idx
, p
, sizeof (bidi_cache_idx
));
1042 bidi_cache_total_alloc
1043 -= bidi_shelve_header_size
+ idx
* sizeof (struct bidi_it
);
1047 memcpy (&bidi_cache_idx
, p
, sizeof (bidi_cache_idx
));
1048 bidi_cache_ensure_space (bidi_cache_idx
);
1049 memcpy (bidi_cache
, p
+ sizeof (bidi_cache_idx
),
1050 bidi_cache_idx
* sizeof (struct bidi_it
));
1051 memcpy (bidi_cache_start_stack
,
1052 p
+ sizeof (bidi_cache_idx
)
1053 + bidi_cache_idx
* sizeof (struct bidi_it
),
1054 sizeof (bidi_cache_start_stack
));
1055 memcpy (&bidi_cache_sp
,
1056 p
+ sizeof (bidi_cache_idx
)
1057 + bidi_cache_idx
* sizeof (struct bidi_it
)
1058 + sizeof (bidi_cache_start_stack
),
1059 sizeof (bidi_cache_sp
));
1060 memcpy (&bidi_cache_start
,
1061 p
+ sizeof (bidi_cache_idx
)
1062 + bidi_cache_idx
* sizeof (struct bidi_it
)
1063 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
1064 sizeof (bidi_cache_start
));
1065 memcpy (&bidi_cache_last_idx
,
1066 p
+ sizeof (bidi_cache_idx
)
1067 + bidi_cache_idx
* sizeof (struct bidi_it
)
1068 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
1069 + sizeof (bidi_cache_start
),
1070 sizeof (bidi_cache_last_idx
));
1071 memcpy (&bidi_cache_max_elts
,
1072 p
+ sizeof (bidi_cache_idx
)
1073 + bidi_cache_idx
* sizeof (struct bidi_it
)
1074 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
1075 + sizeof (bidi_cache_start
) + sizeof (bidi_cache_last_idx
),
1076 sizeof (bidi_cache_max_elts
));
1077 bidi_cache_total_alloc
1078 -= (bidi_shelve_header_size
1079 + bidi_cache_idx
* sizeof (struct bidi_it
));
1087 /***********************************************************************
1089 ***********************************************************************/
1091 bidi_initialize (void)
1093 bidi_type_table
= uniprop_table (intern ("bidi-class"));
1094 if (NILP (bidi_type_table
))
1096 staticpro (&bidi_type_table
);
1098 bidi_mirror_table
= uniprop_table (intern ("mirroring"));
1099 if (NILP (bidi_mirror_table
))
1101 staticpro (&bidi_mirror_table
);
1103 bidi_brackets_table
= uniprop_table (intern ("bracket-type"));
1104 if (NILP (bidi_brackets_table
))
1106 staticpro (&bidi_brackets_table
);
1108 paragraph_start_re
= build_string ("^\\(\f\\|[ \t]*\\)$");
1109 staticpro (¶graph_start_re
);
1110 paragraph_separate_re
= build_string ("^[ \t\f]*$");
1111 staticpro (¶graph_separate_re
);
1114 bidi_cache_total_alloc
= 0;
1115 bidi_cache_max_elts
= BIDI_CACHE_MAX_ELTS_PER_SLOT
;
1117 bidi_initialized
= 1;
1120 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
1123 bidi_set_paragraph_end (struct bidi_it
*bidi_it
)
1125 bidi_it
->invalid_levels
= 0;
1126 bidi_it
->invalid_isolates
= 0;
1127 bidi_it
->stack_idx
= 0;
1128 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
1131 /* Initialize the bidi iterator from buffer/string position CHARPOS. */
1133 bidi_init_it (ptrdiff_t charpos
, ptrdiff_t bytepos
, bool frame_window_p
,
1134 struct bidi_it
*bidi_it
)
1136 if (! bidi_initialized
)
1139 bidi_it
->charpos
= charpos
;
1141 bidi_it
->bytepos
= bytepos
;
1142 bidi_it
->frame_window_p
= frame_window_p
;
1143 bidi_it
->nchars
= -1; /* to be computed in bidi_resolve_explicit */
1144 bidi_it
->first_elt
= 1;
1145 bidi_set_paragraph_end (bidi_it
);
1146 bidi_it
->new_paragraph
= 1;
1147 bidi_it
->separator_limit
= -1;
1148 bidi_it
->type
= NEUTRAL_B
;
1149 bidi_it
->type_after_wn
= NEUTRAL_B
;
1150 bidi_it
->orig_type
= NEUTRAL_B
;
1151 /* FIXME: Review this!!! */
1152 bidi_it
->prev
.type
= bidi_it
->prev
.orig_type
= UNKNOWN_BT
;
1153 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
1154 bidi_it
->next_for_neutral
.charpos
= -1;
1155 bidi_it
->next_for_neutral
.type
1156 = bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
1157 bidi_it
->prev_for_neutral
.charpos
= -1;
1158 bidi_it
->prev_for_neutral
.type
1159 = bidi_it
->prev_for_neutral
.orig_type
= UNKNOWN_BT
;
1160 bidi_it
->bracket_pairing_pos
= -1;
1161 bidi_it
->sos
= L2R
; /* FIXME: should it be user-selectable? */
1162 bidi_it
->disp_pos
= -1; /* invalid/unknown */
1163 bidi_it
->disp_prop
= 0;
1164 /* We can only shrink the cache if we are at the bottom level of its
1166 if (bidi_cache_start
== 0)
1167 bidi_cache_shrink ();
1169 bidi_cache_reset ();
1172 /* Perform initializations for reordering a new line of bidi text. */
1174 bidi_line_init (struct bidi_it
*bidi_it
)
1176 bidi_it
->scan_dir
= 1; /* FIXME: do we need to have control on this? */
1177 bidi_it
->stack_idx
= 0;
1178 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
1179 bidi_it
->level_stack
[0].flags
= 0; /* NEUTRAL_DIR, false per X1 */
1180 bidi_it
->invalid_levels
= 0;
1181 bidi_it
->isolate_level
= 0; /* X1 */
1182 bidi_it
->invalid_isolates
= 0; /* X1 */
1183 /* Setting this to zero will force its recomputation the first time
1184 we need it for W5. */
1185 bidi_it
->next_en_pos
= 0;
1186 bidi_it
->next_en_type
= UNKNOWN_BT
;
1187 bidi_it
->next_for_ws
.charpos
= -1;
1188 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
1189 bidi_it
->bracket_pairing_pos
= -1;
1190 bidi_set_sos_type (bidi_it
,
1191 (bidi_it
->paragraph_dir
== R2L
? 1 : 0),
1192 bidi_it
->level_stack
[0].level
); /* X10 */
1194 bidi_cache_reset ();
1198 /***********************************************************************
1200 ***********************************************************************/
1202 /* Count bytes in string S between BEG/BEGBYTE and END. BEG and END
1203 are zero-based character positions in S, BEGBYTE is byte position
1204 corresponding to BEG. UNIBYTE means S is a unibyte string. */
1206 bidi_count_bytes (const unsigned char *s
, ptrdiff_t beg
,
1207 ptrdiff_t begbyte
, ptrdiff_t end
, bool unibyte
)
1209 ptrdiff_t pos
= beg
;
1210 const unsigned char *p
= s
+ begbyte
, *start
= p
;
1216 if (!CHAR_HEAD_P (*p
))
1221 p
+= BYTES_BY_CHAR_HEAD (*p
);
1229 /* Fetch and return the character at byte position BYTEPOS. If S is
1230 non-NULL, fetch the character from string S; otherwise fetch the
1231 character from the current buffer. UNIBYTE means S is a
1234 bidi_char_at_pos (ptrdiff_t bytepos
, const unsigned char *s
, bool unibyte
)
1243 s
= BYTE_POS_ADDR (bytepos
);
1244 return STRING_CHAR (s
);
1247 /* Fetch and return the character at CHARPOS/BYTEPOS. If that
1248 character is covered by a display string, treat the entire run of
1249 covered characters as a single character, either u+2029 or u+FFFC,
1250 and return their combined length in CH_LEN and NCHARS. DISP_POS
1251 specifies the character position of the next display string, or -1
1252 if not yet computed. When the next character is at or beyond that
1253 position, the function updates DISP_POS with the position of the
1254 next display string. *DISP_PROP non-zero means that there's really
1255 a display string at DISP_POS, as opposed to when we searched till
1256 DISP_POS without finding one. If *DISP_PROP is 2, it means the
1257 display spec is of the form `(space ...)', which is replaced with
1258 u+2029 to handle it as a paragraph separator. STRING->s is the C
1259 string to iterate, or NULL if iterating over a buffer or a Lisp
1260 string; in the latter case, STRING->lstring is the Lisp string. */
1262 bidi_fetch_char (ptrdiff_t charpos
, ptrdiff_t bytepos
, ptrdiff_t *disp_pos
,
1263 int *disp_prop
, struct bidi_string_data
*string
,
1265 bool frame_window_p
, ptrdiff_t *ch_len
, ptrdiff_t *nchars
)
1269 = (string
->s
|| STRINGP (string
->lstring
)) ? string
->schars
: ZV
;
1270 struct text_pos pos
;
1273 /* If we got past the last known position of display string, compute
1274 the position of the next one. That position could be at CHARPOS. */
1275 if (charpos
< endpos
&& charpos
> *disp_pos
)
1277 SET_TEXT_POS (pos
, charpos
, bytepos
);
1278 *disp_pos
= compute_display_string_pos (&pos
, string
, w
, frame_window_p
,
1282 /* Fetch the character at BYTEPOS. */
1283 if (charpos
>= endpos
)
1291 else if (charpos
>= *disp_pos
&& *disp_prop
)
1293 ptrdiff_t disp_end_pos
;
1295 /* We don't expect to find ourselves in the middle of a display
1296 property. Hopefully, it will never be needed. */
1297 if (charpos
> *disp_pos
)
1299 /* Text covered by `display' properties and overlays with
1300 display properties or display strings is handled as a single
1301 character that represents the entire run of characters
1302 covered by the display property. */
1303 if (*disp_prop
== 2)
1305 /* `(space ...)' display specs are handled as paragraph
1306 separators for the purposes of the reordering; see UAX#9
1307 section 3 and clause HL1 in section 4.3 there. */
1308 ch
= PARAGRAPH_SEPARATOR
;
1312 /* All other display specs are handled as the Unicode Object
1313 Replacement Character. */
1314 ch
= OBJECT_REPLACEMENT_CHARACTER
;
1316 disp_end_pos
= compute_display_string_end (*disp_pos
, string
);
1317 if (disp_end_pos
< 0)
1319 /* Somebody removed the display string from the buffer
1320 behind our back. Recover by processing this buffer
1321 position as if no display property were present there to
1326 *nchars
= disp_end_pos
- *disp_pos
;
1330 *ch_len
= bidi_count_bytes (string
->s
, *disp_pos
, bytepos
,
1331 disp_end_pos
, string
->unibyte
);
1332 else if (STRINGP (string
->lstring
))
1333 *ch_len
= bidi_count_bytes (SDATA (string
->lstring
), *disp_pos
,
1334 bytepos
, disp_end_pos
, string
->unibyte
);
1336 *ch_len
= CHAR_TO_BYTE (disp_end_pos
) - bytepos
;
1344 if (!string
->unibyte
)
1346 ch
= STRING_CHAR_AND_LENGTH (string
->s
+ bytepos
, len
);
1351 ch
= UNIBYTE_TO_CHAR (string
->s
[bytepos
]);
1355 else if (STRINGP (string
->lstring
))
1357 if (!string
->unibyte
)
1359 ch
= STRING_CHAR_AND_LENGTH (SDATA (string
->lstring
) + bytepos
,
1365 ch
= UNIBYTE_TO_CHAR (SREF (string
->lstring
, bytepos
));
1371 ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (bytepos
), len
);
1377 /* If we just entered a run of characters covered by a display
1378 string, compute the position of the next display string. */
1379 if (charpos
+ *nchars
<= endpos
&& charpos
+ *nchars
> *disp_pos
1382 SET_TEXT_POS (pos
, charpos
+ *nchars
, bytepos
+ *ch_len
);
1383 *disp_pos
= compute_display_string_pos (&pos
, string
, w
, frame_window_p
,
1390 /* Like bidi_fetch_char, but ignore any text between an isolate
1391 initiator and its matching PDI or, if it has no matching PDI, the
1392 end of the paragraph. If isolates were skipped, CH_LEN and NCHARS
1393 are set to the number of bytes and characters between BYTEPOS/CHARPOS
1394 and the character that was fetched after skipping the isolates. */
1396 bidi_fetch_char_skip_isolates (ptrdiff_t charpos
, ptrdiff_t bytepos
,
1397 ptrdiff_t *disp_pos
, int *disp_prop
,
1398 struct bidi_string_data
*string
,
1399 struct window
*w
, bool frame_window_p
,
1400 ptrdiff_t *ch_len
, ptrdiff_t *nchars
)
1402 ptrdiff_t orig_charpos
= charpos
, orig_bytepos
= bytepos
;
1403 int ch
= bidi_fetch_char (charpos
, bytepos
, disp_pos
, disp_prop
, string
, w
,
1404 frame_window_p
, ch_len
, nchars
);
1405 bidi_type_t ch_type
= bidi_get_type (ch
, NEUTRAL_DIR
);
1406 ptrdiff_t level
= 0;
1408 if (ch_type
== LRI
|| ch_type
== RLI
|| ch_type
== FSI
)
1411 while (level
> 0 && ch_type
!= NEUTRAL_B
)
1415 ch
= bidi_fetch_char (charpos
, bytepos
, disp_pos
, disp_prop
, string
,
1416 w
, frame_window_p
, ch_len
, nchars
);
1417 ch_type
= bidi_get_type (ch
, NEUTRAL_DIR
);
1418 /* A Note to P2 says to ignore max_depth limit. */
1419 if (ch_type
== LRI
|| ch_type
== RLI
|| ch_type
== FSI
)
1421 else if (ch_type
== PDI
)
1426 /* Communicate to the caller how much did we skip, so it could get
1427 past the last character position we examined. */
1428 *nchars
+= charpos
- orig_charpos
;
1429 *ch_len
+= bytepos
- orig_bytepos
;
1435 /***********************************************************************
1436 Determining paragraph direction
1437 ***********************************************************************/
1439 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
1440 Value is the non-negative length of the paragraph separator
1441 following the buffer position, -1 if position is at the beginning
1442 of a new paragraph, or -2 if position is neither at beginning nor
1443 at end of a paragraph. */
1445 bidi_at_paragraph_end (ptrdiff_t charpos
, ptrdiff_t bytepos
)
1448 Lisp_Object start_re
;
1451 sep_re
= paragraph_separate_re
;
1452 start_re
= paragraph_start_re
;
1454 val
= fast_looking_at (sep_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
);
1457 if (fast_looking_at (start_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
) >= 0)
1466 /* If the user has requested the long scans caching, make sure that
1467 BIDI cache is enabled. Otherwise, make sure it's disabled. */
1469 static struct region_cache
*
1470 bidi_paragraph_cache_on_off (void)
1472 struct buffer
*cache_buffer
= current_buffer
;
1473 bool indirect_p
= false;
1475 /* For indirect buffers, make sure to use the cache of their base
1477 if (cache_buffer
->base_buffer
)
1479 cache_buffer
= cache_buffer
->base_buffer
;
1483 /* Don't turn on or off the cache in the base buffer, if the value
1484 of cache-long-scans of the base buffer is inconsistent with that.
1485 This is because doing so will just make the cache pure overhead,
1486 since if we turn it on via indirect buffer, it will be
1487 immediately turned off by its base buffer. */
1488 if (NILP (BVAR (current_buffer
, cache_long_scans
)))
1491 || NILP (BVAR (cache_buffer
, cache_long_scans
)))
1493 if (cache_buffer
->bidi_paragraph_cache
)
1495 free_region_cache (cache_buffer
->bidi_paragraph_cache
);
1496 cache_buffer
->bidi_paragraph_cache
= 0;
1504 || !NILP (BVAR (cache_buffer
, cache_long_scans
)))
1506 if (!cache_buffer
->bidi_paragraph_cache
)
1507 cache_buffer
->bidi_paragraph_cache
= new_region_cache ();
1509 return cache_buffer
->bidi_paragraph_cache
;
1513 /* On my 2005-vintage machine, searching back for paragraph start
1514 takes ~1 ms per line. And bidi_paragraph_init is called 4 times
1515 when user types C-p. The number below limits each call to
1516 bidi_paragraph_init to about 10 ms. */
1517 #define MAX_PARAGRAPH_SEARCH 7500
1519 /* Find the beginning of this paragraph by looking back in the buffer.
1520 Value is the byte position of the paragraph's beginning, or
1521 BEGV_BYTE if paragraph_start_re is still not found after looking
1522 back MAX_PARAGRAPH_SEARCH lines in the buffer. */
1524 bidi_find_paragraph_start (ptrdiff_t pos
, ptrdiff_t pos_byte
)
1526 Lisp_Object re
= paragraph_start_re
;
1527 ptrdiff_t limit
= ZV
, limit_byte
= ZV_BYTE
;
1528 struct region_cache
*bpc
= bidi_paragraph_cache_on_off ();
1529 ptrdiff_t n
= 0, oldpos
= pos
, next
;
1530 struct buffer
*cache_buffer
= current_buffer
;
1532 if (cache_buffer
->base_buffer
)
1533 cache_buffer
= cache_buffer
->base_buffer
;
1535 while (pos_byte
> BEGV_BYTE
1536 && n
++ < MAX_PARAGRAPH_SEARCH
1537 && fast_looking_at (re
, pos
, pos_byte
, limit
, limit_byte
, Qnil
) < 0)
1539 /* FIXME: What if the paragraph beginning is covered by a
1540 display string? And what if a display string covering some
1541 of the text over which we scan back includes
1542 paragraph_start_re? */
1543 DEC_BOTH (pos
, pos_byte
);
1544 if (bpc
&& region_cache_backward (cache_buffer
, bpc
, pos
, &next
))
1546 pos
= next
, pos_byte
= CHAR_TO_BYTE (pos
);
1550 pos
= find_newline_no_quit (pos
, pos_byte
, -1, &pos_byte
);
1552 if (n
>= MAX_PARAGRAPH_SEARCH
)
1553 pos
= BEGV
, pos_byte
= BEGV_BYTE
;
1555 know_region_cache (cache_buffer
, bpc
, pos
, oldpos
);
1556 /* Positions returned by the region cache are not limited to
1557 BEGV..ZV range, so we limit them here. */
1558 pos_byte
= clip_to_bounds (BEGV_BYTE
, pos_byte
, ZV_BYTE
);
1562 /* On a 3.4 GHz machine, searching forward for a strong directional
1563 character in a long paragraph full of weaks or neutrals takes about
1564 1 ms for each 20K characters. The number below limits each call to
1565 bidi_paragraph_init to less than 10 ms even on slow machines. */
1566 #define MAX_STRONG_CHAR_SEARCH 100000
1568 /* Starting from POS, find the first strong (L, R, or AL) character,
1569 while skipping over any characters between an isolate initiator and
1570 its matching PDI. STOP_AT_PDI non-zero means stop at the PDI that
1571 matches the isolate initiator at POS. Return the bidi type of the
1572 character where the search stopped. Give up if after examining
1573 MAX_STRONG_CHAR_SEARCH buffer or string positions no strong
1574 character was found. */
1576 find_first_strong_char (ptrdiff_t pos
, ptrdiff_t bytepos
, ptrdiff_t end
,
1577 ptrdiff_t *disp_pos
, int *disp_prop
,
1578 struct bidi_string_data
*string
, struct window
*w
,
1579 bool string_p
, bool frame_window_p
,
1580 ptrdiff_t *ch_len
, ptrdiff_t *nchars
, bool stop_at_pdi
)
1588 /* If STOP_AT_PDI is non-zero, we must have been called with FSI
1589 at POS. Get past it. */
1590 #ifdef ENABLE_CHECKING
1591 ch
= bidi_fetch_char (pos
, bytepos
, disp_pos
, disp_prop
, string
, w
,
1592 frame_window_p
, ch_len
, nchars
);
1593 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
1594 eassert (type
== FSI
/* || type == LRI || type == RLI */);
1599 ch
= bidi_fetch_char_skip_isolates (pos
, bytepos
, disp_pos
, disp_prop
, string
,
1600 w
, frame_window_p
, ch_len
, nchars
);
1601 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
1604 for (pos
+= *nchars
, bytepos
+= *ch_len
;
1605 bidi_get_category (type
) != STRONG
1606 /* If requested to stop at first PDI, stop there. */
1607 && !(stop_at_pdi
&& type
== PDI
)
1608 /* Stop when searched too far into an abnormally large
1609 paragraph full of weak or neutral characters. */
1610 && pos
- pos1
< MAX_STRONG_CHAR_SEARCH
;
1611 type
= bidi_get_type (ch
, NEUTRAL_DIR
))
1615 /* Pretend there's a paragraph separator at end of
1621 && type
== NEUTRAL_B
1622 && bidi_at_paragraph_end (pos
, bytepos
) >= -1)
1624 /* Fetch next character and advance to get past it. */
1625 ch
= bidi_fetch_char_skip_isolates (pos
, bytepos
, disp_pos
, disp_prop
,
1626 string
, w
, frame_window_p
,
1634 /* Determine the base direction, a.k.a. base embedding level, of the
1635 paragraph we are about to iterate through. If DIR is either L2R or
1636 R2L, just use that. Otherwise, determine the paragraph direction
1637 from the first strong directional character of the paragraph.
1639 NO_DEFAULT_P means don't default to L2R if the paragraph
1640 has no strong directional characters and both DIR and
1641 bidi_it->paragraph_dir are NEUTRAL_DIR. In that case, search back
1642 in the buffer until a paragraph is found with a strong character,
1643 or until hitting BEGV. In the latter case, fall back to L2R. This
1644 flag is used in current-bidi-paragraph-direction.
1646 Note that this function gives the paragraph separator the same
1647 direction as the preceding paragraph, even though Emacs generally
1648 views the separator as not belonging to any paragraph. */
1650 bidi_paragraph_init (bidi_dir_t dir
, struct bidi_it
*bidi_it
, bool no_default_p
)
1652 ptrdiff_t bytepos
= bidi_it
->bytepos
;
1653 bool string_p
= bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
);
1654 ptrdiff_t pstartbyte
;
1655 /* Note that begbyte is a byte position, while end is a character
1656 position. Yes, this is ugly, but we are trying to avoid costly
1657 calls to BYTE_TO_CHAR and its ilk. */
1658 ptrdiff_t begbyte
= string_p
? 0 : BEGV_BYTE
;
1659 ptrdiff_t end
= string_p
? bidi_it
->string
.schars
: ZV
;
1661 /* Special case for an empty buffer. */
1662 if (bytepos
== begbyte
&& bidi_it
->charpos
== end
)
1664 /* We should never be called at EOB or before BEGV. */
1665 else if (bidi_it
->charpos
>= end
|| bytepos
< begbyte
)
1670 bidi_it
->paragraph_dir
= L2R
;
1671 bidi_it
->new_paragraph
= 0;
1673 else if (dir
== R2L
)
1675 bidi_it
->paragraph_dir
= R2L
;
1676 bidi_it
->new_paragraph
= 0;
1678 else if (dir
== NEUTRAL_DIR
) /* P2 */
1680 ptrdiff_t ch_len
, nchars
;
1681 ptrdiff_t pos
, disp_pos
= -1;
1684 const unsigned char *s
;
1686 if (!bidi_initialized
)
1689 /* If we are inside a paragraph separator, we are just waiting
1690 for the separator to be exhausted; use the previous paragraph
1691 direction. But don't do that if we have been just reseated,
1692 because we need to reinitialize below in that case. */
1693 if (!bidi_it
->first_elt
1694 && bidi_it
->charpos
< bidi_it
->separator_limit
)
1697 /* If we are on a newline, get past it to where the next
1698 paragraph might start. But don't do that at BEGV since then
1699 we are potentially in a new paragraph that doesn't yet
1701 pos
= bidi_it
->charpos
;
1702 s
= (STRINGP (bidi_it
->string
.lstring
)
1703 ? SDATA (bidi_it
->string
.lstring
)
1704 : bidi_it
->string
.s
);
1705 if (bytepos
> begbyte
1706 && bidi_char_at_pos (bytepos
, s
, bidi_it
->string
.unibyte
) == '\n')
1712 /* We are either at the beginning of a paragraph or in the
1713 middle of it. Find where this paragraph starts. */
1716 /* We don't support changes of paragraph direction inside a
1717 string. It is treated as a single paragraph. */
1721 pstartbyte
= bidi_find_paragraph_start (pos
, bytepos
);
1722 bidi_it
->separator_limit
= -1;
1723 bidi_it
->new_paragraph
= 0;
1725 /* The following loop is run more than once only if NO_DEFAULT_P,
1726 and only if we are iterating on a buffer. */
1728 bytepos
= pstartbyte
;
1730 pos
= BYTE_TO_CHAR (bytepos
);
1731 type
= find_first_strong_char (pos
, bytepos
, end
, &disp_pos
, &disp_prop
,
1732 &bidi_it
->string
, bidi_it
->w
,
1733 string_p
, bidi_it
->frame_window_p
,
1734 &ch_len
, &nchars
, false);
1735 if (type
== STRONG_R
|| type
== STRONG_AL
) /* P3 */
1736 bidi_it
->paragraph_dir
= R2L
;
1737 else if (type
== STRONG_L
)
1738 bidi_it
->paragraph_dir
= L2R
;
1740 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
)
1742 /* If this paragraph is at BEGV, default to L2R. */
1743 if (pstartbyte
== BEGV_BYTE
)
1744 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 */
1747 ptrdiff_t prevpbyte
= pstartbyte
;
1748 ptrdiff_t p
= BYTE_TO_CHAR (pstartbyte
), pbyte
= pstartbyte
;
1750 /* Find the beginning of the previous paragraph, if any. */
1751 while (pbyte
> BEGV_BYTE
&& prevpbyte
>= pstartbyte
)
1753 /* FXIME: What if p is covered by a display
1754 string? See also a FIXME inside
1755 bidi_find_paragraph_start. */
1756 DEC_BOTH (p
, pbyte
);
1757 prevpbyte
= bidi_find_paragraph_start (p
, pbyte
);
1759 pstartbyte
= prevpbyte
;
1763 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
);
1768 /* Contrary to UAX#9 clause P3, we only default the paragraph
1769 direction to L2R if we have no previous usable paragraph
1770 direction. This is allowed by the HL1 clause. */
1771 if (bidi_it
->paragraph_dir
!= L2R
&& bidi_it
->paragraph_dir
!= R2L
)
1772 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 ``higher-level protocols'' */
1773 if (bidi_it
->paragraph_dir
== R2L
)
1774 bidi_it
->level_stack
[0].level
= 1;
1776 bidi_it
->level_stack
[0].level
= 0;
1778 bidi_line_init (bidi_it
);
1782 /***********************************************************************
1783 Resolving explicit and implicit levels.
1784 The rest of this file constitutes the core of the UBA implementation.
1785 ***********************************************************************/
1788 bidi_explicit_dir_char (int ch
)
1790 bidi_type_t ch_type
;
1792 if (!bidi_initialized
)
1796 eassert (ch
== BIDI_EOB
);
1799 ch_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
1800 return (ch_type
== LRE
|| ch_type
== LRO
1801 || ch_type
== RLE
|| ch_type
== RLO
1805 /* Given an iterator state in BIDI_IT, advance one character position
1806 in the buffer/string to the next character (in the logical order),
1807 resolve any explicit embeddings, directional overrides, and isolate
1808 initiators and terminators, and return the embedding level of the
1809 character after resolving these explicit directives. */
1811 bidi_resolve_explicit (struct bidi_it
*bidi_it
)
1814 bidi_type_t type
, typ1
, prev_type
= UNKNOWN_BT
;
1817 bidi_dir_t override
;
1818 bool isolate_status
;
1819 bool string_p
= bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
);
1820 ptrdiff_t ch_len
, nchars
, disp_pos
, end
;
1823 = ((bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
1824 ? bidi_it
->string
.schars
: ZV
);
1826 /* Record the info about the previous character. */
1827 if (bidi_it
->type_after_wn
!= WEAK_BN
/* W1/Retaining */
1828 && bidi_it
->type
!= WEAK_BN
)
1830 /* This special case is needed in support of Unicode 8.0
1831 correction to N0, as implemented in bidi_resolve_weak/W1
1833 if (bidi_it
->type_after_wn
== NEUTRAL_ON
1834 && bidi_get_category (bidi_it
->type
) == STRONG
1835 && bidi_paired_bracket_type (bidi_it
->ch
) == BIDI_BRACKET_CLOSE
)
1836 bidi_remember_char (&bidi_it
->prev
, bidi_it
, 1);
1838 bidi_remember_char (&bidi_it
->prev
, bidi_it
, 0);
1840 if (bidi_it
->type_after_wn
== STRONG_R
1841 || bidi_it
->type_after_wn
== STRONG_L
1842 || bidi_it
->type_after_wn
== STRONG_AL
)
1843 bidi_remember_char (&bidi_it
->last_strong
, bidi_it
, 0);
1844 if (bidi_it
->type
== STRONG_R
|| bidi_it
->type
== STRONG_L
1845 || bidi_it
->type
== WEAK_EN
|| bidi_it
->type
== WEAK_AN
)
1846 bidi_remember_char (&bidi_it
->prev_for_neutral
, bidi_it
, 1);
1848 /* If we overstepped the characters used for resolving neutrals
1849 and whitespace, invalidate their info in the iterator. */
1850 if (bidi_it
->charpos
>= bidi_it
->next_for_neutral
.charpos
)
1852 bidi_it
->next_for_neutral
.type
= UNKNOWN_BT
;
1853 /* If needed, reset the "magical" value of pairing bracket
1854 position, so that bidi_resolve_brackets will resume
1855 resolution of brackets according to BPA. */
1856 if (bidi_it
->bracket_pairing_pos
== eob
)
1857 bidi_it
->bracket_pairing_pos
= -1;
1859 if (bidi_it
->next_en_pos
>= 0
1860 && bidi_it
->charpos
>= bidi_it
->next_en_pos
)
1862 bidi_it
->next_en_pos
= 0;
1863 bidi_it
->next_en_type
= UNKNOWN_BT
;
1866 /* Reset the bracket resolution info, unless we previously decided
1867 (in bidi_find_bracket_pairs) that brackets in this level run
1868 should be resolved as neutrals. */
1869 if (bidi_it
->bracket_pairing_pos
!= eob
)
1871 bidi_it
->bracket_pairing_pos
= -1;
1872 bidi_it
->bracket_enclosed_type
= UNKNOWN_BT
;
1875 /* If reseat()'ed, don't advance, so as to start iteration from the
1876 position where we were reseated. bidi_it->bytepos can be less
1877 than BEGV_BYTE after reseat to BEGV. */
1878 if (bidi_it
->bytepos
< (string_p
? 0 : BEGV_BYTE
)
1879 || bidi_it
->first_elt
)
1881 bidi_it
->first_elt
= 0;
1884 const unsigned char *p
1885 = (STRINGP (bidi_it
->string
.lstring
)
1886 ? SDATA (bidi_it
->string
.lstring
)
1887 : bidi_it
->string
.s
);
1889 if (bidi_it
->charpos
< 0)
1890 bidi_it
->charpos
= bidi_it
->bytepos
= 0;
1891 eassert (bidi_it
->bytepos
== bidi_count_bytes (p
, 0, 0,
1893 bidi_it
->string
.unibyte
));
1897 if (bidi_it
->charpos
< BEGV
)
1899 bidi_it
->charpos
= BEGV
;
1900 bidi_it
->bytepos
= BEGV_BYTE
;
1902 eassert (bidi_it
->bytepos
== CHAR_TO_BYTE (bidi_it
->charpos
));
1904 /* Determine the original bidi type of the previous character,
1905 which is needed for handling isolate initiators and PDF. The
1906 type of the previous character will be non-trivial only if
1907 our caller moved through some previous text in
1908 get_visually_first_element, in which case bidi_it->prev holds
1909 the information we want. */
1910 if (bidi_it
->first_elt
&& bidi_it
->prev
.type
!= UNKNOWN_BT
)
1912 eassert (bidi_it
->prev
.charpos
== bidi_it
->charpos
- 1);
1913 prev_type
= bidi_it
->prev
.orig_type
;
1916 /* Don't move at end of buffer/string. */
1917 else if (bidi_it
->charpos
< (string_p
? bidi_it
->string
.schars
: ZV
))
1919 /* Advance to the next character, skipping characters covered by
1920 display strings (nchars > 1). */
1921 if (bidi_it
->nchars
<= 0)
1923 bidi_it
->charpos
+= bidi_it
->nchars
;
1924 if (bidi_it
->ch_len
== 0)
1926 bidi_it
->bytepos
+= bidi_it
->ch_len
;
1927 prev_type
= bidi_it
->orig_type
;
1929 else /* EOB or end of string */
1930 prev_type
= NEUTRAL_B
;
1932 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
; /* X1 */
1933 isolate_status
= ISOLATE_STATUS (bidi_it
, bidi_it
->stack_idx
);
1934 override
= OVERRIDE (bidi_it
, bidi_it
->stack_idx
);
1935 new_level
= current_level
;
1937 if (bidi_it
->charpos
>= (string_p
? bidi_it
->string
.schars
: ZV
))
1940 bidi_it
->ch_len
= 1;
1941 bidi_it
->nchars
= 1;
1942 bidi_it
->disp_pos
= (string_p
? bidi_it
->string
.schars
: ZV
);
1943 bidi_it
->disp_prop
= 0;
1947 /* LRI, RLI, and FSI increment, and PDF decrements, the
1948 embedding level of the _following_ characters, so we must
1949 first look at the type of the previous character to support
1954 if (current_level
< BIDI_MAXDEPTH
1955 && bidi_it
->invalid_levels
== 0
1956 && bidi_it
->invalid_isolates
== 0)
1958 new_level
= ((current_level
+ 1) & ~1) + 1;
1959 bidi_it
->isolate_level
++;
1960 bidi_push_embedding_level (bidi_it
, new_level
,
1964 bidi_it
->invalid_isolates
++;
1967 if (current_level
< BIDI_MAXDEPTH
- 1
1968 && bidi_it
->invalid_levels
== 0
1969 && bidi_it
->invalid_isolates
== 0)
1971 new_level
= ((current_level
+ 2) & ~1);
1972 bidi_it
->isolate_level
++;
1973 bidi_push_embedding_level (bidi_it
, new_level
,
1977 bidi_it
->invalid_isolates
++;
1980 if (!bidi_it
->invalid_isolates
)
1982 if (bidi_it
->invalid_levels
)
1983 bidi_it
->invalid_levels
--;
1984 else if (!isolate_status
&& bidi_it
->stack_idx
>= 1)
1985 new_level
= bidi_pop_embedding_level (bidi_it
);
1989 eassert (prev_type
!= FSI
);
1993 /* Fetch the character at BYTEPOS. If it is covered by a
1994 display string, treat the entire run of covered characters as
1995 a single character u+FFFC. */
1996 curchar
= bidi_fetch_char (bidi_it
->charpos
, bidi_it
->bytepos
,
1997 &bidi_it
->disp_pos
, &bidi_it
->disp_prop
,
1998 &bidi_it
->string
, bidi_it
->w
,
1999 bidi_it
->frame_window_p
,
2000 &bidi_it
->ch_len
, &bidi_it
->nchars
);
2002 bidi_it
->ch
= curchar
;
2003 bidi_it
->resolved_level
= new_level
;
2005 /* Don't apply directional override here, as all the types we handle
2006 below will not be affected by the override anyway, and we need
2007 the original type unaltered. The override will be applied in
2008 bidi_resolve_weak. */
2009 type
= bidi_get_type (curchar
, NEUTRAL_DIR
);
2010 bidi_it
->orig_type
= type
;
2011 bidi_check_type (bidi_it
->orig_type
);
2013 bidi_it
->type_after_wn
= UNKNOWN_BT
;
2019 bidi_it
->type_after_wn
= type
;
2020 bidi_check_type (bidi_it
->type_after_wn
);
2021 type
= WEAK_BN
; /* X9/Retaining */
2022 if (new_level
< BIDI_MAXDEPTH
2023 && bidi_it
->invalid_levels
== 0
2024 && bidi_it
->invalid_isolates
== 0)
2026 /* Compute the least odd embedding level greater than
2027 the current level. */
2028 new_level
= ((new_level
+ 1) & ~1) + 1;
2029 if (bidi_it
->type_after_wn
== RLE
)
2030 override
= NEUTRAL_DIR
;
2033 bidi_push_embedding_level (bidi_it
, new_level
, override
, false);
2034 bidi_it
->resolved_level
= new_level
;
2038 if (bidi_it
->invalid_isolates
== 0)
2039 bidi_it
->invalid_levels
++;
2044 bidi_it
->type_after_wn
= type
;
2045 bidi_check_type (bidi_it
->type_after_wn
);
2046 type
= WEAK_BN
; /* X9/Retaining */
2047 if (new_level
< BIDI_MAXDEPTH
- 1
2048 && bidi_it
->invalid_levels
== 0
2049 && bidi_it
->invalid_isolates
== 0)
2051 /* Compute the least even embedding level greater than
2052 the current level. */
2053 new_level
= ((new_level
+ 2) & ~1);
2054 if (bidi_it
->type_after_wn
== LRE
)
2055 override
= NEUTRAL_DIR
;
2058 bidi_push_embedding_level (bidi_it
, new_level
, override
, false);
2059 bidi_it
->resolved_level
= new_level
;
2063 if (bidi_it
->invalid_isolates
== 0)
2064 bidi_it
->invalid_levels
++;
2068 end
= string_p
? bidi_it
->string
.schars
: ZV
;
2069 disp_pos
= bidi_it
->disp_pos
;
2070 disp_prop
= bidi_it
->disp_prop
;
2071 nchars
= bidi_it
->nchars
;
2072 ch_len
= bidi_it
->ch_len
;
2073 typ1
= find_first_strong_char (bidi_it
->charpos
,
2074 bidi_it
->bytepos
, end
,
2075 &disp_pos
, &disp_prop
,
2076 &bidi_it
->string
, bidi_it
->w
,
2077 string_p
, bidi_it
->frame_window_p
,
2078 &ch_len
, &nchars
, true);
2079 if (typ1
!= STRONG_R
&& typ1
!= STRONG_AL
)
2082 /* Override orig_type, which will be needed when we come to
2083 examine the next character, which is the first character
2084 inside the isolate. */
2085 bidi_it
->orig_type
= type
;
2091 bidi_it
->orig_type
= type
;
2095 if (override
== NEUTRAL_DIR
)
2096 bidi_it
->type_after_wn
= type
;
2097 else /* Unicode 8.0 correction. */
2098 bidi_it
->type_after_wn
= (override
== L2R
? STRONG_L
: STRONG_R
);
2099 bidi_check_type (bidi_it
->type_after_wn
);
2103 if (override
== NEUTRAL_DIR
)
2104 bidi_it
->type_after_wn
= type
;
2105 else /* Unicode 8.0 correction. */
2106 bidi_it
->type_after_wn
= (override
== L2R
? STRONG_L
: STRONG_R
);
2107 bidi_check_type (bidi_it
->type_after_wn
);
2110 if (bidi_it
->invalid_isolates
)
2111 bidi_it
->invalid_isolates
--;
2112 else if (bidi_it
->isolate_level
> 0)
2114 bidi_it
->invalid_levels
= 0;
2115 while (!ISOLATE_STATUS (bidi_it
, bidi_it
->stack_idx
))
2116 bidi_pop_embedding_level (bidi_it
);
2117 eassert (bidi_it
->stack_idx
> 0);
2118 new_level
= bidi_pop_embedding_level (bidi_it
);
2119 bidi_it
->isolate_level
--;
2121 bidi_it
->resolved_level
= new_level
;
2122 /* Unicode 8.0 correction. */
2124 bidi_dir_t stack_override
= OVERRIDE (bidi_it
, bidi_it
->stack_idx
);
2125 if (stack_override
== L2R
)
2126 bidi_it
->type_after_wn
= STRONG_L
;
2127 else if (stack_override
== R2L
)
2128 bidi_it
->type_after_wn
= STRONG_R
;
2130 bidi_it
->type_after_wn
= type
;
2134 bidi_it
->type_after_wn
= type
;
2135 bidi_check_type (bidi_it
->type_after_wn
);
2136 type
= WEAK_BN
; /* X9/Retaining */
2143 bidi_it
->type
= type
;
2144 bidi_check_type (bidi_it
->type
);
2146 if (bidi_it
->type
== NEUTRAL_B
) /* X8 */
2148 bidi_set_paragraph_end (bidi_it
);
2149 /* This is needed by bidi_resolve_weak below, and in L1. */
2150 bidi_it
->type_after_wn
= bidi_it
->type
;
2153 eassert (bidi_it
->resolved_level
>= 0);
2154 return bidi_it
->resolved_level
;
2157 /* Advance in the buffer/string, resolve weak types and return the
2158 type of the next character after weak type resolution. */
2160 bidi_resolve_weak (struct bidi_it
*bidi_it
)
2163 bidi_dir_t override
;
2164 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2165 int new_level
= bidi_resolve_explicit (bidi_it
);
2167 bidi_type_t type_of_next
;
2168 struct bidi_it saved_it
;
2170 = ((STRINGP (bidi_it
->string
.lstring
) || bidi_it
->string
.s
)
2171 ? bidi_it
->string
.schars
: ZV
);
2173 type
= bidi_it
->type
;
2174 override
= OVERRIDE (bidi_it
, bidi_it
->stack_idx
);
2176 eassert (!(type
== UNKNOWN_BT
2183 eassert (prev_level
>= 0);
2184 if (bidi_it
->type
== NEUTRAL_B
)
2186 /* We've got a new isolating sequence, compute the directional
2187 type of sos and initialize per-run variables (UAX#9, clause
2189 bidi_set_sos_type (bidi_it
, prev_level
, new_level
);
2191 if (type
== NEUTRAL_S
|| type
== NEUTRAL_WS
2192 || type
== WEAK_BN
|| type
== STRONG_AL
)
2193 bidi_it
->type_after_wn
= type
; /* needed in L1 */
2194 bidi_check_type (bidi_it
->type_after_wn
);
2196 /* Level and directional override status are already recorded in
2197 bidi_it, and do not need any change; see X6. */
2198 if (override
== R2L
) /* X6 */
2200 else if (override
== L2R
)
2204 if (type
== WEAK_NSM
) /* W1 */
2206 /* Note that we don't need to consider the case where the
2207 prev character has its type overridden by an RLO or LRO,
2208 because then either the type of this NSM would have been
2209 also overridden, or the previous character is outside the
2210 current level run, and thus not relevant to this NSM.
2211 This is why NSM gets the type_after_wn of the previous
2213 /* bidi_set_sos_type sets type_after_wn to UNKNOWN_BT. */
2214 if (bidi_it
->prev
.type
!= UNKNOWN_BT
2215 /* If type_after_wn is NEUTRAL_B, this NSM is at sos. */
2216 && bidi_it
->prev
.type
!= NEUTRAL_B
)
2218 if (bidi_isolate_fmt_char (bidi_it
->prev
.type
))
2220 /* From W1: "Note that in an isolating run sequence,
2221 an isolate initiator followed by an NSM or any
2222 type other than PDI must be an overflow isolate
2224 eassert (bidi_it
->invalid_isolates
> 0);
2229 /* This includes the Unicode 8.0 correction for N0,
2230 due to how we set prev.type in bidi_resolve_explicit,
2232 type
= bidi_it
->prev
.type
;
2235 else if (bidi_it
->sos
== R2L
)
2237 else if (bidi_it
->sos
== L2R
)
2239 else /* shouldn't happen! */
2242 if (type
== WEAK_EN
/* W2 */
2243 && bidi_it
->last_strong
.type
== STRONG_AL
)
2245 else if (type
== STRONG_AL
) /* W3 */
2247 else if ((type
== WEAK_ES
/* W4 */
2248 && bidi_it
->prev
.type
== WEAK_EN
2249 && bidi_it
->prev
.orig_type
== WEAK_EN
)
2251 && ((bidi_it
->prev
.type
== WEAK_EN
2252 && bidi_it
->prev
.orig_type
== WEAK_EN
)
2253 || bidi_it
->prev
.type
== WEAK_AN
)))
2255 const unsigned char *s
2256 = (STRINGP (bidi_it
->string
.lstring
)
2257 ? SDATA (bidi_it
->string
.lstring
)
2258 : bidi_it
->string
.s
);
2260 next_char
= (bidi_it
->charpos
+ bidi_it
->nchars
>= eob
2262 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
,
2263 s
, bidi_it
->string
.unibyte
));
2264 type_of_next
= bidi_get_type (next_char
, override
);
2266 if (type_of_next
== WEAK_BN
2267 || bidi_explicit_dir_char (next_char
))
2269 bidi_copy_it (&saved_it
, bidi_it
);
2270 while (bidi_resolve_explicit (bidi_it
) == new_level
2271 && bidi_it
->type
== WEAK_BN
)
2272 type_of_next
= bidi_it
->type
;
2273 bidi_copy_it (bidi_it
, &saved_it
);
2276 /* If the next character is EN, but the last strong-type
2277 character is AL, that next EN will be changed to AN when
2278 we process it in W2 above. So in that case, this ES
2279 should not be changed into EN. */
2281 && type_of_next
== WEAK_EN
2282 && bidi_it
->last_strong
.type
!= STRONG_AL
)
2284 else if (type
== WEAK_CS
)
2286 if (bidi_it
->prev
.type
== WEAK_AN
2287 && (type_of_next
== WEAK_AN
2288 /* If the next character is EN, but the last
2289 strong-type character is AL, EN will be later
2290 changed to AN when we process it in W2 above.
2291 So in that case, this ES should not be
2293 || (type_of_next
== WEAK_EN
2294 && bidi_it
->last_strong
.type
== STRONG_AL
)))
2296 else if (bidi_it
->prev
.type
== WEAK_EN
2297 && type_of_next
== WEAK_EN
2298 && bidi_it
->last_strong
.type
!= STRONG_AL
)
2302 else if (type
== WEAK_ET
/* W5: ET with EN before or after it */
2303 || type
== WEAK_BN
) /* W5/Retaining */
2305 if (bidi_it
->prev
.type
== WEAK_EN
) /* ET/BN w/EN before it */
2307 else if (bidi_it
->next_en_pos
> bidi_it
->charpos
2308 && bidi_it
->next_en_type
!= WEAK_BN
)
2310 if (bidi_it
->next_en_type
== WEAK_EN
) /* ET/BN with EN after it */
2313 else if (type
== WEAK_BN
2314 /* This condition is for the following important case:
2316 . we are at level zero
2317 . either previous strong character was L,
2318 or we've seen no strong characters since sos
2319 and the base paragraph direction is L2R
2320 . this BN is NOT a bidi directional control
2322 For such a situation, either this BN will be
2323 converted to EN per W5, and then to L by virtue
2324 of W7; or it will become ON per W6, and then L
2325 because of N1/N2. So we take a shortcut here
2326 and make it L right away, to avoid the
2327 potentially costly loop below. This is
2328 important when the buffer has a long series of
2329 control characters, like binary nulls, and no
2330 R2L characters at all. */
2332 && !bidi_explicit_dir_char (bidi_it
->ch
)
2333 && ((bidi_it
->last_strong
.type
== STRONG_L
)
2334 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
2335 && bidi_it
->sos
== L2R
)))
2337 else if (bidi_it
->next_en_pos
>= 0)
2339 /* We overstepped the last known position for ET
2340 resolution but there could be other such characters
2341 in this paragraph (when we are sure there are no more
2342 such positions, we set next_en_pos to a negative
2343 value). Try to find the next position for ET
2345 ptrdiff_t en_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
2346 const unsigned char *s
= (STRINGP (bidi_it
->string
.lstring
)
2347 ? SDATA (bidi_it
->string
.lstring
)
2348 : bidi_it
->string
.s
);
2350 if (bidi_it
->nchars
<= 0)
2353 = (bidi_it
->charpos
+ bidi_it
->nchars
>= eob
2355 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
, s
,
2356 bidi_it
->string
.unibyte
));
2357 type_of_next
= bidi_get_type (next_char
, override
);
2359 if (type_of_next
== WEAK_ET
2360 || type_of_next
== WEAK_BN
2361 || bidi_explicit_dir_char (next_char
))
2363 bidi_copy_it (&saved_it
, bidi_it
);
2364 while (bidi_resolve_explicit (bidi_it
) == new_level
2365 && (bidi_it
->type
== WEAK_BN
2366 || bidi_it
->type
== WEAK_ET
))
2367 type_of_next
= bidi_it
->type
;
2369 && bidi_it
->charpos
== saved_it
.charpos
+ saved_it
.nchars
)
2371 /* If we entered the above loop with a BN that
2372 changes the level, the type of next
2373 character, which is in a different level, is
2374 not relevant to resolving this series of ET
2376 en_pos
= saved_it
.charpos
;
2377 type_of_next
= type
;
2380 en_pos
= bidi_it
->charpos
;
2381 bidi_copy_it (bidi_it
, &saved_it
);
2383 /* Remember this position, to speed up processing of the
2385 bidi_it
->next_en_pos
= en_pos
;
2386 if (type_of_next
== WEAK_EN
)
2388 /* If the last strong character is AL, the EN we've
2389 found will become AN when we get to it (W2). */
2390 if (bidi_it
->last_strong
.type
== STRONG_AL
)
2391 type_of_next
= WEAK_AN
;
2392 else if (type
== WEAK_BN
)
2393 type
= NEUTRAL_ON
; /* W6/Retaining */
2397 else if (type_of_next
== NEUTRAL_B
)
2398 /* Record the fact that there are no more ENs from
2399 here to the end of paragraph, to avoid entering the
2400 loop above ever again in this paragraph. */
2401 bidi_it
->next_en_pos
= -1;
2402 /* Record the type of the character where we ended our search. */
2403 bidi_it
->next_en_type
= type_of_next
;
2408 if (type
== WEAK_ES
|| type
== WEAK_ET
|| type
== WEAK_CS
/* W6 */
2410 && (bidi_it
->prev
.type
== WEAK_CS
/* W6/Retaining */
2411 || bidi_it
->prev
.type
== WEAK_ES
2412 || bidi_it
->prev
.type
== WEAK_ET
)))
2415 /* Store the type we've got so far, before we clobber it with strong
2416 types in W7 and while resolving neutral types. But leave alone
2417 the original types that were recorded above, because we will need
2418 them for the L1 clause. */
2419 if (bidi_it
->type_after_wn
== UNKNOWN_BT
)
2420 bidi_it
->type_after_wn
= type
;
2421 bidi_check_type (bidi_it
->type_after_wn
);
2423 if (type
== WEAK_EN
) /* W7 */
2425 if ((bidi_it
->last_strong
.type
== STRONG_L
)
2426 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
&& bidi_it
->sos
== L2R
))
2430 bidi_it
->type
= type
;
2431 bidi_check_type (bidi_it
->type
);
2435 /* Resolve the type of a neutral character according to the type of
2436 surrounding strong text and the current embedding level. */
2438 bidi_resolve_neutral_1 (bidi_type_t prev_type
, bidi_type_t next_type
, int lev
)
2440 /* N1: "European and Arabic numbers act as if they were R in terms
2441 of their influence on NIs." */
2442 if (next_type
== WEAK_EN
|| next_type
== WEAK_AN
)
2443 next_type
= STRONG_R
;
2444 if (prev_type
== WEAK_EN
|| prev_type
== WEAK_AN
)
2445 prev_type
= STRONG_R
;
2447 if (next_type
== prev_type
) /* N1 */
2449 else if ((lev
& 1) == 0) /* N2 */
2455 #define FLAG_EMBEDDING_INSIDE 1
2456 #define FLAG_OPPOSITE_INSIDE 2
2458 /* A data type used in the stack maintained by
2459 bidi_find_bracket_pairs below. */
2460 typedef struct bpa_stack_entry
{
2461 int close_bracket_char
;
2462 int open_bracket_idx
;
2463 #ifdef ENABLE_CHECKING
2464 ptrdiff_t open_bracket_pos
;
2469 /* Allow for the two struct bidi_it objects too, since they can be big.
2470 With MAX_ALLOCA of 16 KiB, this should allow at least 900 slots in the
2471 BPA stack, which should be more than enough for actual bidi text. */
2472 enum { MAX_BPA_STACK
= max (1, ((MAX_ALLOCA
- 2 * sizeof (struct bidi_it
))
2473 / sizeof (bpa_stack_entry
))) };
2475 /* UAX#9 says to match opening brackets with the matching closing
2476 brackets or their canonical equivalents. As of Unicode 8.0, there
2477 are only 2 bracket characters that have canonical equivalence
2478 decompositions: u+2329 and u+232A. So instead of accessing the
2479 table in uni-decomposition.el, we just handle these 2 characters
2480 with this simple macro. Note that ASCII characters don't have
2481 canonical equivalents by definition. */
2483 /* To find all the characters that need to be processed by
2484 CANONICAL_EQU, first find all the characters which have
2485 decompositions in UnicodeData.txt, with this Awk script:
2487 awk -F ";" " {if ($6 != \"\") print $1, $6}" UnicodeData.txt
2489 Then produce a list of all the bracket characters in BidiBrackets.txt:
2491 awk -F "[ ;]" " {if ($1 != \"#\" && $1 != \"\") print $1}" BidiBrackets.txt
2493 And finally, cross-reference these two:
2495 grep -Fw -f brackets.txt decompositions.txt
2497 where "decompositions.txt" was produced by the 1st script, and
2498 "brackets.txt" by the 2nd script. In the output of grep, look
2499 only for decompositions that don't begin with some compatibility
2500 formatting tag, such as "<compat>". Only decompositions that
2501 consist solely of character codepoints are relevant to bidi
2502 brackets processing. */
2504 #define CANONICAL_EQU(c) \
2505 ( ASCII_CHAR_P (c) ? c \
2506 : (c) == LEFT_POINTING_ANGLE_BRACKET ? LEFT_ANGLE_BRACKET \
2507 : (c) == RIGHT_POINTING_ANGLE_BRACKET ? RIGHT_ANGLE_BRACKET \
2510 #ifdef ENABLE_CHECKING
2511 # define STORE_BRACKET_CHARPOS \
2512 bpa_stack[bpa_sp].open_bracket_pos = bidi_it->charpos
2514 # define STORE_BRACKET_CHARPOS /* nothing */
2517 #define PUSH_BPA_STACK \
2520 if (bpa_sp < MAX_BPA_STACK - 1 && bidi_cache_last_idx <= INT_MAX) \
2523 ch = CANONICAL_EQU (bidi_it->ch); \
2524 bpa_stack[bpa_sp].close_bracket_char = bidi_mirror_char (ch); \
2525 bpa_stack[bpa_sp].open_bracket_idx = bidi_cache_last_idx; \
2526 bpa_stack[bpa_sp].flags = 0; \
2527 STORE_BRACKET_CHARPOS; \
2532 /* This function implements BPA, the Bidi Parenthesis Algorithm,
2533 described in BD16 and N0 of UAX#9. It finds all the bracket pairs
2534 in the current isolating sequence, and records the enclosed type
2535 and the position of the matching bracket in the cache. It returns
2536 non-zero if called with the iterator on the opening bracket which
2537 has a matching closing bracket in the current isolating sequence,
2540 bidi_find_bracket_pairs (struct bidi_it
*bidi_it
)
2542 bidi_bracket_type_t btype
;
2543 bidi_type_t type
= bidi_it
->type
;
2544 bool retval
= false;
2546 /* When scanning backwards, we don't expect any unresolved bidi
2547 bracket characters. */
2548 if (bidi_it
->scan_dir
!= 1)
2551 btype
= bidi_paired_bracket_type (bidi_it
->ch
);
2552 if (btype
== BIDI_BRACKET_OPEN
)
2554 bpa_stack_entry bpa_stack
[MAX_BPA_STACK
];
2556 struct bidi_it saved_it
;
2557 int base_level
= bidi_it
->level_stack
[0].level
;
2558 int embedding_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2559 int maxlevel
= embedding_level
;
2560 bidi_type_t embedding_type
= (embedding_level
& 1) ? STRONG_R
: STRONG_L
;
2561 struct bidi_it tem_it
;
2562 bool l2r_seen
= false, r2l_seen
= false;
2563 ptrdiff_t pairing_pos
;
2564 int idx_at_entry
= bidi_cache_idx
;
2566 verify (MAX_BPA_STACK
>= 100);
2567 bidi_copy_it (&saved_it
, bidi_it
);
2568 /* bidi_cache_iterator_state refuses to cache on backward scans,
2569 and bidi_cache_fetch_state doesn't bring scan_dir from the
2570 cache, so we must initialize this explicitly. */
2571 tem_it
.scan_dir
= 1;
2575 int old_sidx
, new_sidx
;
2576 int current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2578 if (maxlevel
< current_level
)
2579 maxlevel
= current_level
;
2580 /* Mark every opening bracket character we've traversed by
2581 putting its own position into bracket_pairing_pos. This
2582 is examined in bidi_resolve_brackets to distinguish
2583 brackets that were already resolved to stay NEUTRAL_ON,
2584 and those that were not yet processed by this function
2585 (because they were skipped when we skip higher embedding
2587 if (btype
== BIDI_BRACKET_OPEN
&& bidi_it
->bracket_pairing_pos
== -1)
2588 bidi_it
->bracket_pairing_pos
= bidi_it
->charpos
;
2589 if (!bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
, 0))
2591 /* No more space in cache -- give up and let the opening
2592 bracket that started this be processed as a
2594 bidi_cache_reset_to (idx_at_entry
- bidi_cache_start
);
2595 bidi_copy_it (bidi_it
, &saved_it
);
2598 if (btype
== BIDI_BRACKET_OPEN
)
2600 else if (btype
== BIDI_BRACKET_CLOSE
)
2603 int curchar
= CANONICAL_EQU (bidi_it
->ch
);
2606 while (sp
>= 0 && bpa_stack
[sp
].close_bracket_char
!= curchar
)
2610 /* Update and cache the corresponding opening bracket. */
2611 bidi_cache_fetch_state (bpa_stack
[sp
].open_bracket_idx
,
2613 #ifdef ENABLE_CHECKING
2614 eassert (bpa_stack
[sp
].open_bracket_pos
== tem_it
.charpos
);
2616 /* Determine the enclosed type for this bracket
2617 pair's type resolution according to N0. */
2618 if (bpa_stack
[sp
].flags
& FLAG_EMBEDDING_INSIDE
)
2619 tem_it
.bracket_enclosed_type
= embedding_type
; /* N0b */
2620 else if (bpa_stack
[sp
].flags
& FLAG_OPPOSITE_INSIDE
)
2621 tem_it
.bracket_enclosed_type
/* N0c */
2622 = (embedding_type
== STRONG_L
? STRONG_R
: STRONG_L
);
2624 tem_it
.bracket_enclosed_type
= UNKNOWN_BT
;
2626 /* Record the position of the matching closing
2627 bracket, and update the cache. */
2628 tem_it
.bracket_pairing_pos
= bidi_it
->charpos
;
2629 bidi_cache_iterator_state (&tem_it
, 0, 1);
2631 /* Pop the BPA stack. */
2640 else if (bidi_get_category (bidi_it
->type_after_wn
) != NEUTRAL
)
2645 /* Whenever we see a strong type, update the flags of
2646 all the slots on the stack. */
2647 switch (bidi_it
->type
)
2650 flag
= ((embedding_level
& 1) == 0
2651 ? FLAG_EMBEDDING_INSIDE
2652 : FLAG_OPPOSITE_INSIDE
);
2658 flag
= ((embedding_level
& 1) == 1
2659 ? FLAG_EMBEDDING_INSIDE
2660 : FLAG_OPPOSITE_INSIDE
);
2668 for (sp
= bpa_sp
; sp
>= 0; sp
--)
2669 bpa_stack
[sp
].flags
|= flag
;
2672 old_sidx
= bidi_it
->stack_idx
;
2673 type
= bidi_resolve_weak (bidi_it
);
2674 /* Skip level runs excluded from this isolating run sequence. */
2675 new_sidx
= bidi_it
->stack_idx
;
2676 if (bidi_it
->level_stack
[new_sidx
].level
> current_level
2677 && (ISOLATE_STATUS (bidi_it
, new_sidx
)
2678 || (new_sidx
> old_sidx
+ 1
2679 && ISOLATE_STATUS (bidi_it
, new_sidx
- 1))))
2681 while (bidi_it
->level_stack
[bidi_it
->stack_idx
].level
2684 if (maxlevel
< bidi_it
->level_stack
[bidi_it
->stack_idx
].level
)
2685 maxlevel
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2686 if (!bidi_cache_iterator_state (bidi_it
,
2687 type
== NEUTRAL_B
, 0))
2689 /* No more space in cache -- give up and let the
2690 opening bracket that started this be
2691 processed as any other NEUTRAL_ON. */
2692 bidi_cache_reset_to (idx_at_entry
- bidi_cache_start
);
2693 bidi_copy_it (bidi_it
, &saved_it
);
2696 type
= bidi_resolve_weak (bidi_it
);
2699 if (type
== NEUTRAL_B
2700 || (bidi_it
->level_stack
[bidi_it
->stack_idx
].level
2703 /* We've marched all the way to the end of this
2704 isolating run sequence, and didn't find matching
2705 closing brackets for some opening brackets. Leave
2706 their type unchanged. */
2707 pairing_pos
= bidi_it
->charpos
;
2710 if (bidi_it
->type_after_wn
== NEUTRAL_ON
) /* Unicode 8.0 correction */
2711 btype
= bidi_paired_bracket_type (bidi_it
->ch
);
2713 btype
= BIDI_BRACKET_NONE
;
2716 /* Restore bidi_it from the cache, which should have the bracket
2717 resolution members set as determined by the above loop. */
2718 type
= bidi_cache_find (saved_it
.charpos
, 0, bidi_it
);
2719 eassert (type
== NEUTRAL_ON
);
2721 /* The following is an optimization for bracketed text that has
2722 only one level which is equal to the paragraph's base
2723 embedding level. That is, only L2R and weak/neutral
2724 characters in a L2R paragraph, or only R2L and weak/neutral
2725 characters in a R2L paragraph. Such brackets can be resolved
2726 by bidi_resolve_neutral, which has a further shortcut for
2727 this case. So we pretend we did not resolve the brackets in
2728 this case, set up next_for_neutral for the entire bracketed
2729 text, and reset the cache to the character before the opening
2730 bracket. The upshot is to allow bidi_move_to_visually_next
2731 reset the cache when it returns this opening bracket, thus
2732 cutting significantly on the size of the cache, which is
2733 important with long lines, especially if word-wrap is non-nil
2734 (which requires the display engine to copy the cache back and
2735 forth many times). */
2736 if (maxlevel
== base_level
2737 && ((base_level
== 0 && !r2l_seen
)
2738 || (base_level
== 1 && !l2r_seen
)))
2741 = ((bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
2742 ? bidi_it
->string
.schars
: ZV
);
2745 pairing_pos
= bidi_it
->bracket_pairing_pos
;
2747 /* This special value (which cannot possibly happen when
2748 brackets are resolved, since there's no character at ZV)
2749 will be noticed by bidi_resolve_explicit, and will be
2750 copied to the following iterator states, instead of being
2752 bidi_it
->bracket_pairing_pos
= eob
;
2753 /* This type value will be used for resolving the outermost
2754 closing bracket in bidi_resolve_brackets. */
2755 bidi_it
->bracket_enclosed_type
= embedding_type
;
2756 /* bidi_cache_last_idx is set to the index of the current
2757 state, because we just called bidi_cache_find above.
2758 That state describes the outermost opening bracket, the
2759 one with which we entered this function. Force the cache
2760 to "forget" all the cached states starting from that state. */
2761 bidi_cache_reset_to (bidi_cache_last_idx
- bidi_cache_start
);
2762 /* Set up the next_for_neutral member, to help
2763 bidi_resolve_neutral. */
2764 bidi_it
->next_for_neutral
.type
= embedding_type
;
2765 bidi_it
->next_for_neutral
.charpos
= pairing_pos
;
2766 /* Pretend we didn't resolve this bracket. */
2776 bidi_record_type_for_neutral (struct bidi_saved_info
*info
, int level
,
2781 for (idx
= bidi_cache_last_idx
+ 1; idx
< bidi_cache_idx
; idx
++)
2783 int lev
= bidi_cache
[idx
].level_stack
[bidi_cache
[idx
].stack_idx
].level
;
2787 eassert (lev
== level
);
2789 bidi_cache
[idx
].next_for_neutral
= *info
;
2791 bidi_cache
[idx
].prev_for_neutral
= *info
;
2798 bidi_resolve_brackets (struct bidi_it
*bidi_it
)
2800 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2801 bool resolve_bracket
= false;
2802 bidi_type_t type
= UNKNOWN_BT
;
2804 struct bidi_saved_info prev_for_neutral
, next_for_neutral
;
2806 = ((bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
2807 ? bidi_it
->string
.schars
: ZV
);
2809 /* Record the prev_for_neutral type either from the previous
2810 character, if it was a strong or AN/EN, or from the
2811 prev_for_neutral information recorded previously. */
2812 if (bidi_it
->type
== STRONG_L
|| bidi_it
->type
== STRONG_R
2813 || bidi_it
->type
== WEAK_AN
|| bidi_it
->type
== WEAK_EN
)
2814 bidi_remember_char (&prev_for_neutral
, bidi_it
, 1);
2816 prev_for_neutral
= bidi_it
->prev_for_neutral
;
2817 /* Record the next_for_neutral type information. */
2818 if (bidi_it
->next_for_neutral
.charpos
> bidi_it
->charpos
)
2819 next_for_neutral
= bidi_it
->next_for_neutral
;
2821 next_for_neutral
.charpos
= -1;
2822 if (!bidi_it
->first_elt
)
2824 type
= bidi_cache_find (bidi_it
->charpos
+ bidi_it
->nchars
, 0, bidi_it
);
2827 if (type
== UNKNOWN_BT
)
2829 type
= bidi_resolve_weak (bidi_it
);
2830 if (type
== NEUTRAL_ON
)
2832 /* bracket_pairing_pos == eob means this bracket does not
2833 need to be resolved as a bracket, but as a neutral, see
2834 the optimization trick we play near the end of
2835 bidi_find_bracket_pairs. */
2836 if (bidi_it
->bracket_pairing_pos
== eob
)
2838 /* If this is the outermost closing bracket of a run of
2839 characters in which we decided to resolve brackets as
2840 neutrals, use the embedding level's type, recorded in
2841 bracket_enclosed_type, to resolve the bracket. */
2842 if (bidi_it
->next_for_neutral
.charpos
== bidi_it
->charpos
2843 && bidi_paired_bracket_type (bidi_it
->ch
) == BIDI_BRACKET_CLOSE
)
2844 type
= bidi_it
->bracket_enclosed_type
;
2846 else if (bidi_find_bracket_pairs (bidi_it
))
2847 resolve_bracket
= true;
2850 else if (bidi_it
->bracket_pairing_pos
!= eob
)
2852 eassert (bidi_it
->resolved_level
== -1);
2853 /* If the cached state shows an increase of embedding level due
2854 to an isolate initiator, we need to update the 1st cached
2855 state of the next run of the current isolating sequence with
2856 the prev_for_neutral and next_for_neutral information, so
2857 that it will be picked up when we advance to that next run. */
2858 if (bidi_it
->level_stack
[bidi_it
->stack_idx
].level
> prev_level
2859 && ISOLATE_STATUS (bidi_it
, bidi_it
->stack_idx
))
2861 bidi_record_type_for_neutral (&prev_for_neutral
, prev_level
, 0);
2862 bidi_record_type_for_neutral (&next_for_neutral
, prev_level
, 1);
2864 if (type
== NEUTRAL_ON
2865 && bidi_paired_bracket_type (ch
) == BIDI_BRACKET_OPEN
)
2867 if (bidi_it
->bracket_pairing_pos
> bidi_it
->charpos
)
2869 /* A cached opening bracket that wasn't completely
2871 resolve_bracket
= true;
2873 else if (bidi_it
->bracket_pairing_pos
== -1)
2875 /* Higher levels were not BPA-resolved yet, even if
2876 cached by bidi_find_bracket_pairs. Force application
2877 of BPA to the new level now. */
2878 if (bidi_find_bracket_pairs (bidi_it
))
2879 resolve_bracket
= true;
2882 /* Keep track of the prev_for_neutral and next_for_neutral
2883 types, needed for resolving brackets below and for resolving
2884 neutrals in bidi_resolve_neutral. */
2885 if (bidi_it
->level_stack
[bidi_it
->stack_idx
].level
== prev_level
)
2887 bidi_it
->prev_for_neutral
= prev_for_neutral
;
2888 if (next_for_neutral
.charpos
> 0)
2889 bidi_it
->next_for_neutral
= next_for_neutral
;
2893 /* If needed, resolve the bracket type according to N0. */
2894 if (resolve_bracket
)
2896 int embedding_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2897 bidi_type_t embedding_type
= (embedding_level
& 1) ? STRONG_R
: STRONG_L
;
2899 eassert (bidi_it
->prev_for_neutral
.type
!= UNKNOWN_BT
);
2900 eassert (bidi_it
->bracket_pairing_pos
> bidi_it
->charpos
);
2901 if (bidi_it
->bracket_enclosed_type
== embedding_type
) /* N0b */
2902 type
= embedding_type
;
2905 switch (bidi_it
->prev_for_neutral
.type
)
2911 (bidi_it
->bracket_enclosed_type
== STRONG_R
) /* N0c */
2912 ? STRONG_R
/* N0c1 */
2913 : embedding_type
; /* N0c2 */
2917 (bidi_it
->bracket_enclosed_type
== STRONG_L
) /* N0c */
2918 ? STRONG_L
/* N0c1 */
2919 : embedding_type
; /* N0c2 */
2922 /* N0d: Do not set the type for that bracket pair. */
2926 eassert (type
== STRONG_L
|| type
== STRONG_R
|| type
== NEUTRAL_ON
);
2928 /* Update the type of the paired closing bracket to the same
2929 type as for the resolved opening bracket. */
2930 if (type
!= NEUTRAL_ON
)
2932 ptrdiff_t idx
= bidi_cache_search (bidi_it
->bracket_pairing_pos
,
2935 if (idx
< bidi_cache_start
)
2937 bidi_cache
[idx
].type
= type
;
2945 bidi_resolve_neutral (struct bidi_it
*bidi_it
)
2947 bidi_type_t type
= bidi_resolve_brackets (bidi_it
);
2951 eassert (type
== STRONG_R
2956 || type
== NEUTRAL_B
2957 || type
== NEUTRAL_S
2958 || type
== NEUTRAL_WS
2959 || type
== NEUTRAL_ON
2964 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2965 eassert (current_level
>= 0);
2966 is_neutral
= bidi_get_category (type
) == NEUTRAL
;
2968 if ((type
!= NEUTRAL_B
/* Don't risk entering the long loop below if
2969 we are already at paragraph end. */
2970 && (is_neutral
|| bidi_isolate_fmt_char (type
)))
2971 /* N1-N2/Retaining */
2974 if (bidi_it
->next_for_neutral
.type
!= UNKNOWN_BT
2975 && (bidi_it
->next_for_neutral
.charpos
> bidi_it
->charpos
2976 /* PDI defines an eos, so it's OK for it to serve as its
2977 own next_for_neutral. */
2978 || (bidi_it
->next_for_neutral
.charpos
== bidi_it
->charpos
2979 && bidi_it
->type
== PDI
)))
2981 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
2982 bidi_it
->next_for_neutral
.type
,
2985 /* The next two "else if" clauses are shortcuts for the
2986 important special case when we have a long sequence of
2987 neutral or WEAK_BN characters, such as whitespace or nulls or
2988 other control characters, on the base embedding level of the
2989 paragraph, and that sequence goes all the way to the end of
2990 the paragraph and follows a character whose resolved
2991 directionality is identical to the base embedding level.
2992 (This is what happens in a buffer with plain L2R text that
2993 happens to include long sequences of control characters.) By
2994 virtue of N1, the result of examining this long sequence will
2995 always be either STRONG_L or STRONG_R, depending on the base
2996 embedding level. So we use this fact directly instead of
2997 entering the expensive loop in the "else" clause. */
2998 else if (current_level
== 0
2999 && bidi_it
->prev_for_neutral
.type
== STRONG_L
3000 && (ASCII_CHAR_P (bidi_it
->ch
)
3002 && !bidi_explicit_dir_char (bidi_it
->ch
)
3003 && !bidi_isolate_fmt_char (type
))))
3004 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
3005 STRONG_L
, current_level
);
3006 else if (/* current level is 1 */
3008 /* base embedding level is also 1 */
3009 && bidi_it
->level_stack
[0].level
== 1
3010 /* previous character is one of those considered R for
3011 the purposes of W5 */
3012 && (bidi_it
->prev_for_neutral
.type
== STRONG_R
3013 || bidi_it
->prev_for_neutral
.type
== WEAK_EN
3014 || bidi_it
->prev_for_neutral
.type
== WEAK_AN
)
3016 && !bidi_explicit_dir_char (bidi_it
->ch
)
3017 && !bidi_isolate_fmt_char (type
))
3018 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
3019 STRONG_R
, current_level
);
3022 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
3023 the assumption of batch-style processing; see clauses W4,
3024 W5, and especially N1, which require looking far forward
3025 (as well as back) in the buffer/string. May the fleas of
3026 a thousand camels infest the armpits of those who design
3027 supposedly general-purpose algorithms by looking at their
3028 own implementations, and fail to consider other possible
3030 struct bidi_it saved_it
;
3031 bidi_type_t next_type
;
3032 bool adjacent_to_neutrals
= is_neutral
;
3034 bidi_copy_it (&saved_it
, bidi_it
);
3035 /* Scan the text forward until we find the first non-neutral
3036 character, and then use that to resolve the neutral we
3037 are dealing with now. We also cache the scanned iterator
3038 states, to salvage some of the effort later. */
3040 int old_sidx
, new_sidx
;
3042 /* Paragraph separators have their levels fully resolved
3043 at this point, so cache them as resolved. */
3044 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
, 0);
3045 old_sidx
= bidi_it
->stack_idx
;
3046 type
= bidi_resolve_brackets (bidi_it
);
3047 /* Skip level runs excluded from this isolating run sequence. */
3048 new_sidx
= bidi_it
->stack_idx
;
3049 if (bidi_it
->level_stack
[new_sidx
].level
> current_level
3050 && (ISOLATE_STATUS (bidi_it
, new_sidx
)
3051 /* This is for when we have an isolate initiator
3052 immediately followed by an embedding or
3053 override initiator, in which case we get the
3054 level stack pushed twice by the single call to
3055 bidi_resolve_weak above. */
3056 || (new_sidx
> old_sidx
+ 1
3057 && ISOLATE_STATUS (bidi_it
, new_sidx
- 1))))
3059 while (bidi_it
->level_stack
[bidi_it
->stack_idx
].level
3062 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
, 0);
3063 type
= bidi_resolve_brackets (bidi_it
);
3066 if (!adjacent_to_neutrals
3067 && (bidi_get_category (type
) == NEUTRAL
3068 || bidi_isolate_fmt_char (type
)))
3069 adjacent_to_neutrals
= true;
3070 } while (!(type
== NEUTRAL_B
3072 && bidi_get_category (type
) != NEUTRAL
3073 && !bidi_isolate_fmt_char (type
))
3074 /* This is all per level run, so stop when we
3075 reach the end of this level run. */
3076 || (bidi_it
->level_stack
[bidi_it
->stack_idx
].level
3077 != current_level
)));
3079 /* Record the character we stopped at. */
3080 bidi_remember_char (&saved_it
.next_for_neutral
, bidi_it
, 1);
3082 if ((bidi_it
->level_stack
[bidi_it
->stack_idx
].level
!= current_level
)
3083 || type
== NEUTRAL_B
)
3085 /* Marched all the way to the end of this level run. We
3086 need to use the eos type, whose information is stored
3087 by bidi_set_sos_type in the prev_for_neutral
3089 if (adjacent_to_neutrals
)
3090 next_type
= bidi_it
->prev_for_neutral
.type
;
3093 /* This is a BN which does not adjoin neutrals.
3094 Leave its type alone. */
3095 bidi_copy_it (bidi_it
, &saved_it
);
3096 return bidi_it
->type
;
3106 /* Actually, STRONG_AL cannot happen here, because
3107 bidi_resolve_weak converts it to STRONG_R, per W3. */
3108 eassert (type
!= STRONG_AL
);
3113 /* N1: "European and Arabic numbers act as if they
3114 were R in terms of their influence on NIs." */
3115 next_type
= STRONG_R
;
3122 /* Resolve the type of all the NIs found during the above loop. */
3123 type
= bidi_resolve_neutral_1 (saved_it
.prev_for_neutral
.type
,
3124 next_type
, current_level
);
3125 /* Update next_for_neutral with the resolved type, so we
3126 could use it for all the other NIs up to the place where
3127 we exited the loop. */
3128 saved_it
.next_for_neutral
.type
= next_type
;
3129 bidi_check_type (type
);
3130 /* Update the character which caused us to enter the above loop. */
3131 saved_it
.type
= type
;
3132 bidi_check_type (next_type
);
3133 bidi_copy_it (bidi_it
, &saved_it
);
3139 /* Given an iterator state in BIDI_IT, advance one character position
3140 in the buffer/string to the next character (in the logical order),
3141 resolve the bidi type of that next character, and return that
3144 bidi_type_of_next_char (struct bidi_it
*bidi_it
)
3148 /* This should always be called during a forward scan. */
3149 if (bidi_it
->scan_dir
!= 1)
3152 type
= bidi_resolve_neutral (bidi_it
);
3157 /* Given an iterator state BIDI_IT, advance one character position in
3158 the buffer/string to the next character (in the current scan
3159 direction), resolve the embedding and implicit levels of that next
3160 character, and return the resulting level. */
3162 bidi_level_of_next_char (struct bidi_it
*bidi_it
)
3164 bidi_type_t type
= UNKNOWN_BT
;
3166 ptrdiff_t next_char_pos
= -2;
3168 if (bidi_it
->scan_dir
== 1)
3171 = ((bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
3172 ? bidi_it
->string
.schars
: ZV
);
3174 /* There's no sense in trying to advance if we've already hit
3176 if (bidi_it
->charpos
>= eob
)
3178 eassert (bidi_it
->resolved_level
>= 0);
3179 return bidi_it
->resolved_level
;
3183 /* Perhaps the character we want is already cached as fully resolved.
3184 If it is, the call to bidi_cache_find below will return a type
3185 other than UNKNOWN_BT. */
3186 if (bidi_cache_idx
> bidi_cache_start
&& !bidi_it
->first_elt
)
3188 int bob
= ((bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
3191 if (bidi_it
->scan_dir
> 0)
3193 if (bidi_it
->nchars
<= 0)
3195 next_char_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
3197 else if (bidi_it
->charpos
>= bob
)
3198 /* Implementation note: we allow next_char_pos to be as low as
3199 0 for buffers or -1 for strings, and that is okay because
3200 that's the "position" of the sentinel iterator state we
3201 cached at the beginning of the iteration. */
3202 next_char_pos
= bidi_it
->charpos
- 1;
3203 if (next_char_pos
>= bob
- 1)
3204 type
= bidi_cache_find (next_char_pos
, 1, bidi_it
);
3205 if (type
!= UNKNOWN_BT
)
3207 /* We asked the cache for fully resolved states. */
3208 eassert (bidi_it
->resolved_level
>= 0);
3209 return bidi_it
->resolved_level
;
3213 if (bidi_it
->scan_dir
== -1)
3214 /* If we are going backwards, the iterator state is already cached
3215 from previous scans, and should be fully resolved. */
3218 if (type
== UNKNOWN_BT
)
3219 type
= bidi_type_of_next_char (bidi_it
);
3221 if (type
== NEUTRAL_B
)
3223 eassert (bidi_it
->resolved_level
>= 0);
3224 return bidi_it
->resolved_level
;
3227 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
3229 eassert ((type
== STRONG_R
3233 || type
== WEAK_AN
));
3234 bidi_it
->type
= type
;
3235 bidi_check_type (bidi_it
->type
);
3237 /* For L1 below, we need to know, for each WS character, whether
3238 it belongs to a sequence of WS characters preceding a newline
3239 or a TAB or a paragraph separator. */
3240 if ((bidi_it
->orig_type
== NEUTRAL_WS
3241 || bidi_it
->orig_type
== WEAK_BN
3242 || bidi_isolate_fmt_char (bidi_it
->orig_type
))
3243 && bidi_it
->next_for_ws
.charpos
< bidi_it
->charpos
3244 /* If this character is already at base level, we don't need to
3245 reset it, so avoid the potentially costly loop below. */
3246 && level
!= bidi_it
->level_stack
[0].level
)
3249 ptrdiff_t clen
= bidi_it
->ch_len
;
3250 ptrdiff_t bpos
= bidi_it
->bytepos
;
3251 ptrdiff_t cpos
= bidi_it
->charpos
;
3252 ptrdiff_t disp_pos
= bidi_it
->disp_pos
;
3253 ptrdiff_t nc
= bidi_it
->nchars
;
3254 struct bidi_string_data bs
= bidi_it
->string
;
3256 bool fwp
= bidi_it
->frame_window_p
;
3257 int dpp
= bidi_it
->disp_prop
;
3259 if (bidi_it
->nchars
<= 0)
3262 ch
= bidi_fetch_char (cpos
+= nc
, bpos
+= clen
, &disp_pos
, &dpp
, &bs
,
3263 bidi_it
->w
, fwp
, &clen
, &nc
);
3264 chtype
= bidi_get_type (ch
, NEUTRAL_DIR
);
3265 } while (chtype
== NEUTRAL_WS
|| chtype
== WEAK_BN
3266 || bidi_isolate_fmt_char (chtype
)
3267 || bidi_explicit_dir_char (ch
)); /* L1/Retaining */
3268 bidi_it
->next_for_ws
.type
= chtype
;
3269 bidi_check_type (bidi_it
->next_for_ws
.type
);
3270 bidi_it
->next_for_ws
.charpos
= cpos
;
3273 /* Update the cache, but only if this state was already cached. */
3274 bidi_cache_iterator_state (bidi_it
, 1, 1);
3276 /* Resolve implicit levels. */
3277 if (bidi_it
->orig_type
== NEUTRAL_B
/* L1 */
3278 || bidi_it
->orig_type
== NEUTRAL_S
3279 || bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
3280 || ((bidi_it
->orig_type
== NEUTRAL_WS
3281 || bidi_it
->orig_type
== WEAK_BN
3282 || bidi_isolate_fmt_char (bidi_it
->orig_type
)
3283 || bidi_explicit_dir_char (bidi_it
->ch
))
3284 && (bidi_it
->next_for_ws
.type
== NEUTRAL_B
3285 || bidi_it
->next_for_ws
.type
== NEUTRAL_S
)))
3286 level
= bidi_it
->level_stack
[0].level
;
3287 else if ((level
& 1) == 0) /* I1 */
3289 if (type
== STRONG_R
)
3291 else if (type
== WEAK_EN
|| type
== WEAK_AN
)
3296 if (type
== STRONG_L
|| type
== WEAK_EN
|| type
== WEAK_AN
)
3300 bidi_it
->resolved_level
= level
;
3304 /* Move to the other edge of a level given by LEVEL. If END_FLAG,
3305 we are at the end of a level, and we need to prepare to
3306 resume the scan of the lower level.
3308 If this level's other edge is cached, we simply jump to it, filling
3309 the iterator structure with the iterator state on the other edge.
3310 Otherwise, we walk the buffer or string until we come back to the
3311 same level as LEVEL.
3313 Note: we are not talking here about a ``level run'' in the UAX#9
3314 sense of the term, but rather about a ``level'' which includes
3315 all the levels higher than it. In other words, given the levels
3318 11111112222222333333334443343222222111111112223322111
3321 and assuming we are at point A scanning left to right, this
3322 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
3325 bidi_find_other_level_edge (struct bidi_it
*bidi_it
, int level
, bool end_flag
)
3327 int dir
= end_flag
? -bidi_it
->scan_dir
: bidi_it
->scan_dir
;
3330 /* Try the cache first. */
3331 if ((idx
= bidi_cache_find_level_change (level
, dir
, end_flag
))
3332 >= bidi_cache_start
)
3333 bidi_cache_fetch_state (idx
, bidi_it
);
3338 /* If we are at end of level, its edges must be cached. */
3342 if (!bidi_cache_iterator_state (bidi_it
, 1, 0))
3344 /* Can't happen: if the cache needs to grow, it means we
3345 were at base embedding level, so the cache should have
3346 been either empty or already large enough to cover this
3347 character position. */
3351 new_level
= bidi_level_of_next_char (bidi_it
);
3352 /* If the cache is full, perform an emergency return by
3353 pretending that the level ended. */
3354 if (!bidi_cache_iterator_state (bidi_it
, 1, 0))
3356 new_level
= level
- 1;
3357 /* Since the cache should only grow when we are scanning
3358 forward looking for the edge of the level that is one
3359 above the base embedding level, we can only have this
3360 contingency when LEVEL - 1 is the base embedding
3362 eassert (new_level
== bidi_it
->level_stack
[0].level
);
3363 /* Plan B, for when the cache overflows: Back up to the
3364 previous character by fetching the last cached state,
3365 and force the resolved level of that character be the
3366 base embedding level. */
3367 bidi_cache_fetch_state (bidi_cache_idx
- 1, bidi_it
);
3368 bidi_it
->resolved_level
= new_level
;
3369 bidi_cache_iterator_state (bidi_it
, 1, 1);
3371 } while (new_level
>= level
);
3376 bidi_move_to_visually_next (struct bidi_it
*bidi_it
)
3378 int old_level
, new_level
, next_level
;
3379 struct bidi_it sentinel
;
3381 if (bidi_it
->charpos
< 0 || bidi_it
->bytepos
< 0)
3384 if (bidi_it
->scan_dir
== 0)
3386 bidi_it
->scan_dir
= 1; /* default to logical order */
3389 /* If we just passed a newline, initialize for the next line. */
3390 if (!bidi_it
->first_elt
3391 && (bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
))
3392 bidi_line_init (bidi_it
);
3394 /* Prepare the sentinel iterator state, and cache it. When we bump
3395 into it, scanning backwards, we'll know that the last non-base
3396 level is exhausted. */
3397 if (bidi_cache_idx
== bidi_cache_start
)
3399 bidi_copy_it (&sentinel
, bidi_it
);
3400 if (bidi_it
->first_elt
)
3402 sentinel
.charpos
--; /* cached charpos needs to be monotonic */
3404 sentinel
.ch
= '\n'; /* doesn't matter, but why not? */
3405 sentinel
.ch_len
= 1;
3406 sentinel
.nchars
= 1;
3408 bidi_cache_iterator_state (&sentinel
, 1, 0);
3411 old_level
= bidi_it
->resolved_level
;
3412 new_level
= bidi_level_of_next_char (bidi_it
);
3414 /* Reordering of resolved levels (clause L2) is implemented by
3415 jumping to the other edge of the level and flipping direction of
3416 scanning the text whenever we find a level change. */
3417 if (new_level
!= old_level
)
3419 bool ascending
= new_level
> old_level
;
3420 int level_to_search
= ascending
? old_level
+ 1 : old_level
;
3421 int incr
= ascending
? 1 : -1;
3422 int expected_next_level
= old_level
+ incr
;
3424 /* Jump (or walk) to the other edge of this level. */
3425 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
3426 /* Switch scan direction and peek at the next character in the
3428 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
3430 /* The following loop handles the case where the resolved level
3431 jumps by more than one. This is typical for numbers inside a
3432 run of text with left-to-right embedding direction, but can
3433 also happen in other situations. In those cases the decision
3434 where to continue after a level change, and in what direction,
3435 is tricky. For example, given a text like below:
3440 (where the numbers below the text show the resolved levels),
3441 the result of reordering according to UAX#9 should be this:
3445 This is implemented by the loop below which flips direction
3446 and jumps to the other edge of the level each time it finds
3447 the new level not to be the expected one. The expected level
3448 is always one more or one less than the previous one. */
3449 next_level
= bidi_peek_at_next_level (bidi_it
);
3450 while (next_level
!= expected_next_level
)
3452 /* If next_level is -1, it means we have an unresolved level
3453 in the cache, which at this point should not happen. If
3454 it does, we will infloop. */
3455 eassert (next_level
>= 0);
3456 /* If next_level is not consistent with incr, we might
3459 ? next_level
> expected_next_level
3460 : next_level
< expected_next_level
);
3461 expected_next_level
+= incr
;
3462 level_to_search
+= incr
;
3463 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
3464 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
3465 next_level
= bidi_peek_at_next_level (bidi_it
);
3468 /* Finally, deliver the next character in the new direction. */
3469 next_level
= bidi_level_of_next_char (bidi_it
);
3472 /* Take note when we have just processed the newline that precedes
3473 the end of the paragraph. The next time we are about to be
3474 called, set_iterator_to_next will automatically reinit the
3475 paragraph direction, if needed. We do this at the newline before
3476 the paragraph separator, because the next character might not be
3477 the first character of the next paragraph, due to the bidi
3478 reordering, whereas we _must_ know the paragraph base direction
3479 _before_ we process the paragraph's text, since the base
3480 direction affects the reordering. */
3481 if (bidi_it
->scan_dir
== 1
3482 && (bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
))
3484 /* The paragraph direction of the entire string, once
3485 determined, is in effect for the entire string. Setting the
3486 separator limit to the end of the string prevents
3487 bidi_paragraph_init from being called automatically on this
3489 if (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
3490 bidi_it
->separator_limit
= bidi_it
->string
.schars
;
3491 else if (bidi_it
->bytepos
< ZV_BYTE
)
3494 = bidi_at_paragraph_end (bidi_it
->charpos
+ bidi_it
->nchars
,
3495 bidi_it
->bytepos
+ bidi_it
->ch_len
);
3496 if (bidi_it
->nchars
<= 0)
3500 bidi_it
->new_paragraph
= 1;
3501 /* Record the buffer position of the last character of the
3502 paragraph separator. */
3503 bidi_it
->separator_limit
3504 = bidi_it
->charpos
+ bidi_it
->nchars
+ sep_len
;
3509 if (bidi_it
->scan_dir
== 1 && bidi_cache_idx
> bidi_cache_start
)
3511 /* If we are at paragraph's base embedding level and beyond the
3512 last cached position, the cache's job is done and we can
3514 if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
3515 && bidi_it
->charpos
> (bidi_cache
[bidi_cache_idx
- 1].charpos
3516 + bidi_cache
[bidi_cache_idx
- 1].nchars
- 1))
3517 bidi_cache_reset ();
3518 /* Also reset the cache if it overflowed and we have just
3519 emergency-exited using Plan B. */
3520 else if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
3521 && bidi_cache_idx
>= bidi_cache_size
3522 && bidi_it
->charpos
== bidi_cache
[bidi_cache_idx
- 1].charpos
)
3523 bidi_cache_reset ();
3524 /* But as long as we are caching during forward scan, we must
3525 cache each state, or else the cache integrity will be
3526 compromised: it assumes cached states correspond to buffer
3529 bidi_cache_iterator_state (bidi_it
, 1, 0);
3532 eassert (bidi_it
->resolved_level
>= 0
3533 && bidi_it
->resolved_level
<= BIDI_MAXDEPTH
+ 2);
3536 /* Utility function for looking for strong directional characters
3537 whose bidi type was overridden by a directional override. */
3539 bidi_find_first_overridden (struct bidi_it
*bidi_it
)
3541 ptrdiff_t found_pos
= ZV
;
3545 /* Need to call bidi_resolve_weak, not bidi_resolve_explicit,
3546 because the directional overrides are applied by the
3548 bidi_type_t type
= bidi_resolve_weak (bidi_it
);
3550 if ((type
== STRONG_R
&& bidi_it
->orig_type
== STRONG_L
)
3551 || (type
== STRONG_L
3552 && (bidi_it
->orig_type
== STRONG_R
3553 || bidi_it
->orig_type
== STRONG_AL
)))
3554 found_pos
= bidi_it
->charpos
;
3555 } while (found_pos
== ZV
3556 && bidi_it
->charpos
< ZV
3557 && bidi_it
->ch
!= BIDI_EOB
3558 && bidi_it
->ch
!= '\n');
3563 /* This is meant to be called from within the debugger, whenever you
3564 wish to examine the cache contents. */
3565 void bidi_dump_cached_states (void) EXTERNALLY_VISIBLE
;
3567 bidi_dump_cached_states (void)
3572 if (bidi_cache_idx
== 0)
3574 fprintf (stderr
, "The cache is empty.\n");
3577 fprintf (stderr
, "Total of %"pD
"d state%s in cache:\n",
3578 bidi_cache_idx
, bidi_cache_idx
== 1 ? "" : "s");
3580 for (i
= bidi_cache
[bidi_cache_idx
- 1].charpos
; i
> 0; i
/= 10)
3582 fputs ("ch ", stderr
);
3583 for (i
= 0; i
< bidi_cache_idx
; i
++)
3584 fprintf (stderr
, "%*c", ndigits
, bidi_cache
[i
].ch
);
3585 fputs ("\n", stderr
);
3586 fputs ("lvl ", stderr
);
3587 for (i
= 0; i
< bidi_cache_idx
; i
++)
3588 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].resolved_level
);
3589 fputs ("\n", stderr
);
3590 fputs ("pos ", stderr
);
3591 for (i
= 0; i
< bidi_cache_idx
; i
++)
3592 fprintf (stderr
, "%*"pD
"d", ndigits
, bidi_cache
[i
].charpos
);
3593 fputs ("\n", stderr
);