1 /* Low-level bidirectional buffer/string-scanning functions for GNU Emacs.
2 Copyright (C) 2000-2001, 2004-2005, 2009-2012
3 Free Software Foundation, Inc.
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
10 (at 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 and most other implementations, this one is
26 designed to be called once for every character in the buffer or
29 The main entry point is bidi_move_to_visually_next. Each time it
30 is called, it finds the next character in the visual order, and
31 returns its information in a special structure. The caller is then
32 expected to process this character for display or any other
33 purposes, and call bidi_move_to_visually_next for the next
34 character. See the comments in bidi_move_to_visually_next for more
35 details about its algorithm that finds the next visual-order
36 character by resolving their levels on the fly.
38 Two other entry points are bidi_paragraph_init and
39 bidi_mirror_char. The first determines the base direction of a
40 paragraph, while the second returns the mirrored version of its
43 A few auxiliary entry points are used to initialize the bidi
44 iterator for iterating an object (buffer or string), push and pop
45 the bidi iterator state, and save and restore the state of the bidi
48 If you want to understand the code, you will have to read it
49 together with the relevant portions of UAX#9. The comments include
50 references to UAX#9 rules, for that very reason.
52 A note about references to UAX#9 rules: if the reference says
53 something like "X9/Retaining", it means that you need to refer to
54 rule X9 and to its modifications described in the "Implementation
55 Notes" section of UAX#9, under "Retaining Format Codes". */
62 #include "character.h"
64 #include "dispextern.h"
66 static int bidi_initialized
= 0;
68 static Lisp_Object bidi_type_table
, bidi_mirror_table
;
70 #define LRM_CHAR 0x200E
71 #define RLM_CHAR 0x200F
74 /* Data type for describing the bidirectional character categories. */
82 /* UAX#9 says to search only for L, AL, or R types of characters, and
83 ignore RLE, RLO, LRE, and LRO, when determining the base paragraph
84 level. Yudit indeed ignores them. This variable is therefore set
85 by default to ignore them, but setting it to zero will take them
87 extern int bidi_ignore_explicit_marks_for_paragraph_level EXTERNALLY_VISIBLE
;
88 int bidi_ignore_explicit_marks_for_paragraph_level
= 1;
90 static Lisp_Object paragraph_start_re
, paragraph_separate_re
;
91 static Lisp_Object Qparagraph_start
, Qparagraph_separate
;
94 /***********************************************************************
96 ***********************************************************************/
98 /* Return the bidi type of a character CH, subject to the current
99 directional OVERRIDE. */
100 static inline bidi_type_t
101 bidi_get_type (int ch
, bidi_dir_t override
)
103 bidi_type_t default_type
;
107 if (ch
< 0 || ch
> MAX_CHAR
)
110 default_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
111 /* Every valid character code, even those that are unassigned by the
112 UCD, have some bidi-class property, according to
113 DerivedBidiClass.txt file. Therefore, if we ever get UNKNOWN_BT
114 (= zero) code from CHAR_TABLE_REF, that's a bug. */
115 if (default_type
== UNKNOWN_BT
)
118 if (override
== NEUTRAL_DIR
)
121 switch (default_type
)
123 /* Although UAX#9 does not tell, it doesn't make sense to
124 override NEUTRAL_B and LRM/RLM characters. */
139 if (override
== L2R
) /* X6 */
141 else if (override
== R2L
)
144 abort (); /* can't happen: handled above */
150 bidi_check_type (bidi_type_t type
)
152 eassert (UNKNOWN_BT
<= type
&& type
<= NEUTRAL_ON
);
155 /* Given a bidi TYPE of a character, return its category. */
156 static inline bidi_category_t
157 bidi_get_category (bidi_type_t type
)
171 case PDF
: /* ??? really?? */
190 /* Return the mirrored character of C, if it has one. If C has no
191 mirrored counterpart, return C.
192 Note: The conditions in UAX#9 clause L4 regarding the surrounding
193 context must be tested by the caller. */
195 bidi_mirror_char (int c
)
201 if (c
< 0 || c
> MAX_CHAR
)
204 val
= CHAR_TABLE_REF (bidi_mirror_table
, c
);
209 /* When debugging, check before assigning to V, so that the check
210 isn't broken by undefined behavior due to int overflow. */
211 eassert (CHAR_VALID_P (XINT (val
)));
215 /* Minimal test we must do in optimized builds, to prevent weird
216 crashes further down the road. */
217 if (v
< 0 || v
> MAX_CHAR
)
226 /* Determine the start-of-run (sor) directional type given the two
227 embedding levels on either side of the run boundary. Also, update
228 the saved info about previously seen characters, since that info is
229 generally valid for a single level run. */
231 bidi_set_sor_type (struct bidi_it
*bidi_it
, int level_before
, int level_after
)
233 int higher_level
= (level_before
> level_after
? level_before
: level_after
);
235 /* The prev_was_pdf gork is required for when we have several PDFs
236 in a row. In that case, we want to compute the sor type for the
237 next level run only once: when we see the first PDF. That's
238 because the sor type depends only on the higher of the two levels
239 that we find on the two sides of the level boundary (see UAX#9,
240 clause X10), and so we don't need to know the final embedding
241 level to which we descend after processing all the PDFs. */
242 if (!bidi_it
->prev_was_pdf
|| level_before
< level_after
)
243 /* FIXME: should the default sor direction be user selectable? */
244 bidi_it
->sor
= ((higher_level
& 1) != 0 ? R2L
: L2R
);
245 if (level_before
> level_after
)
246 bidi_it
->prev_was_pdf
= 1;
248 bidi_it
->prev
.type
= UNKNOWN_BT
;
249 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
250 = bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
251 bidi_it
->prev_for_neutral
.type
= (bidi_it
->sor
== R2L
? STRONG_R
: STRONG_L
);
252 bidi_it
->prev_for_neutral
.charpos
= bidi_it
->charpos
;
253 bidi_it
->prev_for_neutral
.bytepos
= bidi_it
->bytepos
;
254 bidi_it
->next_for_neutral
.type
= bidi_it
->next_for_neutral
.type_after_w1
255 = bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
256 bidi_it
->ignore_bn_limit
= -1; /* meaning it's unknown */
259 /* Push the current embedding level and override status; reset the
260 current level to LEVEL and the current override status to OVERRIDE. */
262 bidi_push_embedding_level (struct bidi_it
*bidi_it
,
263 int level
, bidi_dir_t override
)
265 bidi_it
->stack_idx
++;
266 eassert (bidi_it
->stack_idx
< BIDI_MAXLEVEL
);
267 bidi_it
->level_stack
[bidi_it
->stack_idx
].level
= level
;
268 bidi_it
->level_stack
[bidi_it
->stack_idx
].override
= override
;
271 /* Pop the embedding level and directional override status from the
272 stack, and return the new level. */
274 bidi_pop_embedding_level (struct bidi_it
*bidi_it
)
276 /* UAX#9 says to ignore invalid PDFs. */
277 if (bidi_it
->stack_idx
> 0)
278 bidi_it
->stack_idx
--;
279 return bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
282 /* Record in SAVED_INFO the information about the current character. */
284 bidi_remember_char (struct bidi_saved_info
*saved_info
,
285 struct bidi_it
*bidi_it
)
287 saved_info
->charpos
= bidi_it
->charpos
;
288 saved_info
->bytepos
= bidi_it
->bytepos
;
289 saved_info
->type
= bidi_it
->type
;
290 bidi_check_type (bidi_it
->type
);
291 saved_info
->type_after_w1
= bidi_it
->type_after_w1
;
292 bidi_check_type (bidi_it
->type_after_w1
);
293 saved_info
->orig_type
= bidi_it
->orig_type
;
294 bidi_check_type (bidi_it
->orig_type
);
297 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
298 copies the part of the level stack that is actually in use. */
300 bidi_copy_it (struct bidi_it
*to
, struct bidi_it
*from
)
304 /* Copy everything except the level stack and beyond. */
305 memcpy (to
, from
, offsetof (struct bidi_it
, level_stack
[0]));
307 /* Copy the active part of the level stack. */
308 to
->level_stack
[0] = from
->level_stack
[0]; /* level zero is always in use */
309 for (i
= 1; i
<= from
->stack_idx
; i
++)
310 to
->level_stack
[i
] = from
->level_stack
[i
];
314 /***********************************************************************
315 Caching the bidi iterator states
316 ***********************************************************************/
318 #define BIDI_CACHE_CHUNK 200
319 static struct bidi_it
*bidi_cache
;
320 static ptrdiff_t bidi_cache_size
= 0;
321 enum { elsz
= sizeof (struct bidi_it
) };
322 static ptrdiff_t bidi_cache_idx
; /* next unused cache slot */
323 static ptrdiff_t bidi_cache_last_idx
; /* slot of last cache hit */
324 static ptrdiff_t bidi_cache_start
= 0; /* start of cache for this
327 /* 5-slot stack for saving the start of the previous level of the
328 cache. xdisp.c maintains a 5-slot stack for its iterator state,
329 and we need the same size of our stack. */
330 static ptrdiff_t bidi_cache_start_stack
[IT_STACK_SIZE
];
331 static int bidi_cache_sp
;
333 /* Size of header used by bidi_shelve_cache. */
336 bidi_shelve_header_size
337 = (sizeof (bidi_cache_idx
) + sizeof (bidi_cache_start_stack
)
338 + sizeof (bidi_cache_sp
) + sizeof (bidi_cache_start
)
339 + sizeof (bidi_cache_last_idx
))
342 /* Reset the cache state to the empty state. We only reset the part
343 of the cache relevant to iteration of the current object. Previous
344 objects, which are pushed on the display iterator's stack, are left
345 intact. This is called when the cached information is no more
346 useful for the current iteration, e.g. when we were reseated to a
347 new position on the same object. */
349 bidi_cache_reset (void)
351 bidi_cache_idx
= bidi_cache_start
;
352 bidi_cache_last_idx
= -1;
355 /* Shrink the cache to its minimal size. Called when we init the bidi
356 iterator for reordering a buffer or a string that does not come
357 from display properties, because that means all the previously
358 cached info is of no further use. */
360 bidi_cache_shrink (void)
362 if (bidi_cache_size
> BIDI_CACHE_CHUNK
)
364 bidi_cache
= xrealloc (bidi_cache
, BIDI_CACHE_CHUNK
* elsz
);
365 bidi_cache_size
= BIDI_CACHE_CHUNK
;
371 bidi_cache_fetch_state (ptrdiff_t idx
, struct bidi_it
*bidi_it
)
373 int current_scan_dir
= bidi_it
->scan_dir
;
375 if (idx
< bidi_cache_start
|| idx
>= bidi_cache_idx
)
378 bidi_copy_it (bidi_it
, &bidi_cache
[idx
]);
379 bidi_it
->scan_dir
= current_scan_dir
;
380 bidi_cache_last_idx
= idx
;
383 /* Find a cached state with a given CHARPOS and resolved embedding
384 level less or equal to LEVEL. if LEVEL is -1, disregard the
385 resolved levels in cached states. DIR, if non-zero, means search
386 in that direction from the last cache hit. */
387 static inline ptrdiff_t
388 bidi_cache_search (ptrdiff_t charpos
, int level
, int dir
)
390 ptrdiff_t i
, i_start
;
392 if (bidi_cache_idx
> bidi_cache_start
)
394 if (bidi_cache_last_idx
== -1)
395 bidi_cache_last_idx
= bidi_cache_idx
- 1;
396 if (charpos
< bidi_cache
[bidi_cache_last_idx
].charpos
)
399 i_start
= bidi_cache_last_idx
- 1;
401 else if (charpos
> (bidi_cache
[bidi_cache_last_idx
].charpos
402 + bidi_cache
[bidi_cache_last_idx
].nchars
- 1))
405 i_start
= bidi_cache_last_idx
+ 1;
408 i_start
= bidi_cache_last_idx
;
412 i_start
= bidi_cache_idx
- 1;
417 /* Linear search for now; FIXME! */
418 for (i
= i_start
; i
>= bidi_cache_start
; i
--)
419 if (bidi_cache
[i
].charpos
<= charpos
420 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
421 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
426 for (i
= i_start
; i
< bidi_cache_idx
; i
++)
427 if (bidi_cache
[i
].charpos
<= charpos
428 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
429 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
437 /* Find a cached state where the resolved level changes to a value
438 that is lower than LEVEL, and return its cache slot index. DIR is
439 the direction to search, starting with the last used cache slot.
440 If DIR is zero, we search backwards from the last occupied cache
441 slot. BEFORE, if non-zero, means return the index of the slot that
442 is ``before'' the level change in the search direction. That is,
443 given the cached levels like this:
448 and assuming we are at the position cached at the slot marked with
449 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
450 index of slot B or A, depending whether BEFORE is, respectively,
453 bidi_cache_find_level_change (int level
, int dir
, int before
)
457 ptrdiff_t i
= dir
? bidi_cache_last_idx
: bidi_cache_idx
- 1;
458 int incr
= before
? 1 : 0;
460 eassert (!dir
|| bidi_cache_last_idx
>= 0);
469 while (i
>= bidi_cache_start
+ incr
)
471 if (bidi_cache
[i
- incr
].resolved_level
>= 0
472 && bidi_cache
[i
- incr
].resolved_level
< level
)
479 while (i
< bidi_cache_idx
- incr
)
481 if (bidi_cache
[i
+ incr
].resolved_level
>= 0
482 && bidi_cache
[i
+ incr
].resolved_level
< level
)
493 bidi_cache_ensure_space (ptrdiff_t idx
)
495 /* Enlarge the cache as needed. */
496 if (idx
>= bidi_cache_size
)
498 /* The bidi cache cannot be larger than the largest Lisp string
500 ptrdiff_t string_or_buffer_bound
501 = max (BUF_BYTES_MAX
, STRING_BYTES_BOUND
);
503 /* Also, it cannot be larger than what C can represent. */
505 = (min (PTRDIFF_MAX
, SIZE_MAX
) - bidi_shelve_header_size
) / elsz
;
508 = xpalloc (bidi_cache
, &bidi_cache_size
,
509 max (BIDI_CACHE_CHUNK
, idx
- bidi_cache_size
+ 1),
510 min (string_or_buffer_bound
, c_bound
), elsz
);
515 bidi_cache_iterator_state (struct bidi_it
*bidi_it
, int resolved
)
519 /* We should never cache on backward scans. */
520 if (bidi_it
->scan_dir
== -1)
522 idx
= bidi_cache_search (bidi_it
->charpos
, -1, 1);
526 idx
= bidi_cache_idx
;
527 bidi_cache_ensure_space (idx
);
528 /* Character positions should correspond to cache positions 1:1.
529 If we are outside the range of cached positions, the cache is
530 useless and must be reset. */
531 if (idx
> bidi_cache_start
&&
532 (bidi_it
->charpos
> (bidi_cache
[idx
- 1].charpos
533 + bidi_cache
[idx
- 1].nchars
)
534 || bidi_it
->charpos
< bidi_cache
[bidi_cache_start
].charpos
))
537 idx
= bidi_cache_start
;
539 if (bidi_it
->nchars
<= 0)
541 bidi_copy_it (&bidi_cache
[idx
], bidi_it
);
543 bidi_cache
[idx
].resolved_level
= -1;
547 /* Copy only the members which could have changed, to avoid
548 costly copying of the entire struct. */
549 bidi_cache
[idx
].type
= bidi_it
->type
;
550 bidi_check_type (bidi_it
->type
);
551 bidi_cache
[idx
].type_after_w1
= bidi_it
->type_after_w1
;
552 bidi_check_type (bidi_it
->type_after_w1
);
554 bidi_cache
[idx
].resolved_level
= bidi_it
->resolved_level
;
556 bidi_cache
[idx
].resolved_level
= -1;
557 bidi_cache
[idx
].invalid_levels
= bidi_it
->invalid_levels
;
558 bidi_cache
[idx
].invalid_rl_levels
= bidi_it
->invalid_rl_levels
;
559 bidi_cache
[idx
].next_for_neutral
= bidi_it
->next_for_neutral
;
560 bidi_cache
[idx
].next_for_ws
= bidi_it
->next_for_ws
;
561 bidi_cache
[idx
].ignore_bn_limit
= bidi_it
->ignore_bn_limit
;
562 bidi_cache
[idx
].disp_pos
= bidi_it
->disp_pos
;
563 bidi_cache
[idx
].disp_prop
= bidi_it
->disp_prop
;
566 bidi_cache_last_idx
= idx
;
567 if (idx
>= bidi_cache_idx
)
568 bidi_cache_idx
= idx
+ 1;
571 static inline bidi_type_t
572 bidi_cache_find (ptrdiff_t charpos
, int level
, struct bidi_it
*bidi_it
)
574 ptrdiff_t i
= bidi_cache_search (charpos
, level
, bidi_it
->scan_dir
);
576 if (i
>= bidi_cache_start
)
578 bidi_dir_t current_scan_dir
= bidi_it
->scan_dir
;
580 bidi_copy_it (bidi_it
, &bidi_cache
[i
]);
581 bidi_cache_last_idx
= i
;
582 /* Don't let scan direction from the cached state override
583 the current scan direction. */
584 bidi_it
->scan_dir
= current_scan_dir
;
585 return bidi_it
->type
;
592 bidi_peek_at_next_level (struct bidi_it
*bidi_it
)
594 if (bidi_cache_idx
== bidi_cache_start
|| bidi_cache_last_idx
== -1)
596 return bidi_cache
[bidi_cache_last_idx
+ bidi_it
->scan_dir
].resolved_level
;
600 /***********************************************************************
601 Pushing and popping the bidi iterator state
602 ***********************************************************************/
604 /* Push the bidi iterator state in preparation for reordering a
605 different object, e.g. display string found at certain buffer
606 position. Pushing the bidi iterator boils down to saving its
607 entire state on the cache and starting a new cache "stacked" on top
608 of the current cache. */
610 bidi_push_it (struct bidi_it
*bidi_it
)
612 /* Save the current iterator state in its entirety after the last
614 bidi_cache_ensure_space (bidi_cache_idx
);
615 memcpy (&bidi_cache
[bidi_cache_idx
++], bidi_it
, sizeof (struct bidi_it
));
617 /* Push the current cache start onto the stack. */
618 eassert (bidi_cache_sp
< IT_STACK_SIZE
);
619 bidi_cache_start_stack
[bidi_cache_sp
++] = bidi_cache_start
;
621 /* Start a new level of cache, and make it empty. */
622 bidi_cache_start
= bidi_cache_idx
;
623 bidi_cache_last_idx
= -1;
626 /* Restore the iterator state saved by bidi_push_it and return the
627 cache to the corresponding state. */
629 bidi_pop_it (struct bidi_it
*bidi_it
)
631 if (bidi_cache_start
<= 0)
634 /* Reset the next free cache slot index to what it was before the
635 call to bidi_push_it. */
636 bidi_cache_idx
= bidi_cache_start
- 1;
638 /* Restore the bidi iterator state saved in the cache. */
639 memcpy (bidi_it
, &bidi_cache
[bidi_cache_idx
], sizeof (struct bidi_it
));
641 /* Pop the previous cache start from the stack. */
642 if (bidi_cache_sp
<= 0)
644 bidi_cache_start
= bidi_cache_start_stack
[--bidi_cache_sp
];
646 /* Invalidate the last-used cache slot data. */
647 bidi_cache_last_idx
= -1;
650 static ptrdiff_t bidi_cache_total_alloc
;
652 /* Stash away a copy of the cache and its control variables. */
654 bidi_shelve_cache (void)
656 unsigned char *databuf
;
660 if (bidi_cache_idx
== 0)
663 alloc
= (bidi_shelve_header_size
664 + bidi_cache_idx
* sizeof (struct bidi_it
));
665 databuf
= xmalloc (alloc
);
666 bidi_cache_total_alloc
+= alloc
;
668 memcpy (databuf
, &bidi_cache_idx
, sizeof (bidi_cache_idx
));
669 memcpy (databuf
+ sizeof (bidi_cache_idx
),
670 bidi_cache
, bidi_cache_idx
* sizeof (struct bidi_it
));
671 memcpy (databuf
+ sizeof (bidi_cache_idx
)
672 + bidi_cache_idx
* sizeof (struct bidi_it
),
673 bidi_cache_start_stack
, sizeof (bidi_cache_start_stack
));
674 memcpy (databuf
+ sizeof (bidi_cache_idx
)
675 + bidi_cache_idx
* sizeof (struct bidi_it
)
676 + sizeof (bidi_cache_start_stack
),
677 &bidi_cache_sp
, sizeof (bidi_cache_sp
));
678 memcpy (databuf
+ sizeof (bidi_cache_idx
)
679 + bidi_cache_idx
* sizeof (struct bidi_it
)
680 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
681 &bidi_cache_start
, sizeof (bidi_cache_start
));
682 memcpy (databuf
+ sizeof (bidi_cache_idx
)
683 + bidi_cache_idx
* sizeof (struct bidi_it
)
684 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
685 + sizeof (bidi_cache_start
),
686 &bidi_cache_last_idx
, sizeof (bidi_cache_last_idx
));
691 /* Restore the cache state from a copy stashed away by
692 bidi_shelve_cache, and free the buffer used to stash that copy.
693 JUST_FREE non-zero means free the buffer, but don't restore the
694 cache; used when the corresponding iterator is discarded instead of
697 bidi_unshelve_cache (void *databuf
, int just_free
)
699 unsigned char *p
= databuf
;
705 /* A NULL pointer means an empty cache. */
706 bidi_cache_start
= 0;
717 memcpy (&idx
, p
, sizeof (bidi_cache_idx
));
718 bidi_cache_total_alloc
719 -= bidi_shelve_header_size
+ idx
* sizeof (struct bidi_it
);
723 memcpy (&bidi_cache_idx
, p
, sizeof (bidi_cache_idx
));
724 bidi_cache_ensure_space (bidi_cache_idx
);
725 memcpy (bidi_cache
, p
+ sizeof (bidi_cache_idx
),
726 bidi_cache_idx
* sizeof (struct bidi_it
));
727 memcpy (bidi_cache_start_stack
,
728 p
+ sizeof (bidi_cache_idx
)
729 + bidi_cache_idx
* sizeof (struct bidi_it
),
730 sizeof (bidi_cache_start_stack
));
731 memcpy (&bidi_cache_sp
,
732 p
+ sizeof (bidi_cache_idx
)
733 + bidi_cache_idx
* sizeof (struct bidi_it
)
734 + sizeof (bidi_cache_start_stack
),
735 sizeof (bidi_cache_sp
));
736 memcpy (&bidi_cache_start
,
737 p
+ sizeof (bidi_cache_idx
)
738 + bidi_cache_idx
* sizeof (struct bidi_it
)
739 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
740 sizeof (bidi_cache_start
));
741 memcpy (&bidi_cache_last_idx
,
742 p
+ sizeof (bidi_cache_idx
)
743 + bidi_cache_idx
* sizeof (struct bidi_it
)
744 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
745 + sizeof (bidi_cache_start
),
746 sizeof (bidi_cache_last_idx
));
747 bidi_cache_total_alloc
748 -= (bidi_shelve_header_size
749 + bidi_cache_idx
* sizeof (struct bidi_it
));
757 /***********************************************************************
759 ***********************************************************************/
761 bidi_initialize (void)
763 bidi_type_table
= uniprop_table (intern ("bidi-class"));
764 if (NILP (bidi_type_table
))
766 staticpro (&bidi_type_table
);
768 bidi_mirror_table
= uniprop_table (intern ("mirroring"));
769 if (NILP (bidi_mirror_table
))
771 staticpro (&bidi_mirror_table
);
773 Qparagraph_start
= intern ("paragraph-start");
774 staticpro (&Qparagraph_start
);
775 paragraph_start_re
= Fsymbol_value (Qparagraph_start
);
776 if (!STRINGP (paragraph_start_re
))
777 paragraph_start_re
= build_string ("\f\\|[ \t]*$");
778 staticpro (¶graph_start_re
);
779 Qparagraph_separate
= intern ("paragraph-separate");
780 staticpro (&Qparagraph_separate
);
781 paragraph_separate_re
= Fsymbol_value (Qparagraph_separate
);
782 if (!STRINGP (paragraph_separate_re
))
783 paragraph_separate_re
= build_string ("[ \t\f]*$");
784 staticpro (¶graph_separate_re
);
787 bidi_cache_total_alloc
= 0;
789 bidi_initialized
= 1;
792 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
795 bidi_set_paragraph_end (struct bidi_it
*bidi_it
)
797 bidi_it
->invalid_levels
= 0;
798 bidi_it
->invalid_rl_levels
= -1;
799 bidi_it
->stack_idx
= 0;
800 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
803 /* Initialize the bidi iterator from buffer/string position CHARPOS. */
805 bidi_init_it (ptrdiff_t charpos
, ptrdiff_t bytepos
, int frame_window_p
,
806 struct bidi_it
*bidi_it
)
808 if (! bidi_initialized
)
811 bidi_it
->charpos
= charpos
;
813 bidi_it
->bytepos
= bytepos
;
814 bidi_it
->frame_window_p
= frame_window_p
;
815 bidi_it
->nchars
= -1; /* to be computed in bidi_resolve_explicit_1 */
816 bidi_it
->first_elt
= 1;
817 bidi_set_paragraph_end (bidi_it
);
818 bidi_it
->new_paragraph
= 1;
819 bidi_it
->separator_limit
= -1;
820 bidi_it
->type
= NEUTRAL_B
;
821 bidi_it
->type_after_w1
= NEUTRAL_B
;
822 bidi_it
->orig_type
= NEUTRAL_B
;
823 bidi_it
->prev_was_pdf
= 0;
824 bidi_it
->prev
.type
= bidi_it
->prev
.type_after_w1
825 = bidi_it
->prev
.orig_type
= UNKNOWN_BT
;
826 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
827 = bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
828 bidi_it
->next_for_neutral
.charpos
= -1;
829 bidi_it
->next_for_neutral
.type
830 = bidi_it
->next_for_neutral
.type_after_w1
831 = bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
832 bidi_it
->prev_for_neutral
.charpos
= -1;
833 bidi_it
->prev_for_neutral
.type
834 = bidi_it
->prev_for_neutral
.type_after_w1
835 = bidi_it
->prev_for_neutral
.orig_type
= UNKNOWN_BT
;
836 bidi_it
->sor
= L2R
; /* FIXME: should it be user-selectable? */
837 bidi_it
->disp_pos
= -1; /* invalid/unknown */
838 bidi_it
->disp_prop
= 0;
839 /* We can only shrink the cache if we are at the bottom level of its
841 if (bidi_cache_start
== 0)
842 bidi_cache_shrink ();
847 /* Perform initializations for reordering a new line of bidi text. */
849 bidi_line_init (struct bidi_it
*bidi_it
)
851 bidi_it
->scan_dir
= 1; /* FIXME: do we need to have control on this? */
852 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
853 bidi_it
->level_stack
[0].override
= NEUTRAL_DIR
; /* X1 */
854 bidi_it
->invalid_levels
= 0;
855 bidi_it
->invalid_rl_levels
= -1;
856 /* Setting this to zero will force its recomputation the first time
857 we need it for W5. */
858 bidi_it
->next_en_pos
= 0;
859 bidi_it
->next_en_type
= UNKNOWN_BT
;
860 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
861 bidi_set_sor_type (bidi_it
,
862 (bidi_it
->paragraph_dir
== R2L
? 1 : 0),
863 bidi_it
->level_stack
[0].level
); /* X10 */
869 /***********************************************************************
871 ***********************************************************************/
873 /* Count bytes in string S between BEG/BEGBYTE and END. BEG and END
874 are zero-based character positions in S, BEGBYTE is byte position
875 corresponding to BEG. UNIBYTE, if non-zero, means S is a unibyte
877 static inline ptrdiff_t
878 bidi_count_bytes (const unsigned char *s
, const ptrdiff_t beg
,
879 const ptrdiff_t begbyte
, const ptrdiff_t end
, int unibyte
)
882 const unsigned char *p
= s
+ begbyte
, *start
= p
;
888 if (!CHAR_HEAD_P (*p
))
893 p
+= BYTES_BY_CHAR_HEAD (*p
);
901 /* Fetch and returns the character at byte position BYTEPOS. If S is
902 non-NULL, fetch the character from string S; otherwise fetch the
903 character from the current buffer. UNIBYTE non-zero means S is a
906 bidi_char_at_pos (ptrdiff_t bytepos
, const unsigned char *s
, int unibyte
)
913 return STRING_CHAR (s
+ bytepos
);
916 return FETCH_MULTIBYTE_CHAR (bytepos
);
919 /* Fetch and return the character at BYTEPOS/CHARPOS. If that
920 character is covered by a display string, treat the entire run of
921 covered characters as a single character, either u+2029 or u+FFFC,
922 and return their combined length in CH_LEN and NCHARS. DISP_POS
923 specifies the character position of the next display string, or -1
924 if not yet computed. When the next character is at or beyond that
925 position, the function updates DISP_POS with the position of the
926 next display string. DISP_PROP non-zero means that there's really
927 a display string at DISP_POS, as opposed to when we searched till
928 DISP_POS without finding one. If DISP_PROP is 2, it means the
929 display spec is of the form `(space ...)', which is replaced with
930 u+2029 to handle it as a paragraph separator. STRING->s is the C
931 string to iterate, or NULL if iterating over a buffer or a Lisp
932 string; in the latter case, STRING->lstring is the Lisp string. */
934 bidi_fetch_char (ptrdiff_t bytepos
, ptrdiff_t charpos
, ptrdiff_t *disp_pos
,
935 int *disp_prop
, struct bidi_string_data
*string
,
936 int frame_window_p
, ptrdiff_t *ch_len
, ptrdiff_t *nchars
)
940 = (string
->s
|| STRINGP (string
->lstring
)) ? string
->schars
: ZV
;
944 /* If we got past the last known position of display string, compute
945 the position of the next one. That position could be at CHARPOS. */
946 if (charpos
< endpos
&& charpos
> *disp_pos
)
948 SET_TEXT_POS (pos
, charpos
, bytepos
);
949 *disp_pos
= compute_display_string_pos (&pos
, string
, frame_window_p
,
953 /* Fetch the character at BYTEPOS. */
954 if (charpos
>= endpos
)
962 else if (charpos
>= *disp_pos
&& *disp_prop
)
964 ptrdiff_t disp_end_pos
;
966 /* We don't expect to find ourselves in the middle of a display
967 property. Hopefully, it will never be needed. */
968 if (charpos
> *disp_pos
)
970 /* Text covered by `display' properties and overlays with
971 display properties or display strings is handled as a single
972 character that represents the entire run of characters
973 covered by the display property. */
976 /* `(space ...)' display specs are handled as paragraph
977 separators for the purposes of the reordering; see UAX#9
978 section 3 and clause HL1 in section 4.3 there. */
983 /* All other display specs are handled as the Unicode Object
984 Replacement Character. */
987 disp_end_pos
= compute_display_string_end (*disp_pos
, string
);
988 if (disp_end_pos
< 0)
990 /* Somebody removed the display string from the buffer
991 behind our back. Recover by processing this buffer
992 position as if no display property were present there to
997 *nchars
= disp_end_pos
- *disp_pos
;
1001 *ch_len
= bidi_count_bytes (string
->s
, *disp_pos
, bytepos
,
1002 disp_end_pos
, string
->unibyte
);
1003 else if (STRINGP (string
->lstring
))
1004 *ch_len
= bidi_count_bytes (SDATA (string
->lstring
), *disp_pos
,
1005 bytepos
, disp_end_pos
, string
->unibyte
);
1007 *ch_len
= CHAR_TO_BYTE (disp_end_pos
) - bytepos
;
1015 if (!string
->unibyte
)
1017 ch
= STRING_CHAR_AND_LENGTH (string
->s
+ bytepos
, len
);
1022 ch
= UNIBYTE_TO_CHAR (string
->s
[bytepos
]);
1026 else if (STRINGP (string
->lstring
))
1028 if (!string
->unibyte
)
1030 ch
= STRING_CHAR_AND_LENGTH (SDATA (string
->lstring
) + bytepos
,
1036 ch
= UNIBYTE_TO_CHAR (SREF (string
->lstring
, bytepos
));
1042 ch
= STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (bytepos
), len
);
1048 /* If we just entered a run of characters covered by a display
1049 string, compute the position of the next display string. */
1050 if (charpos
+ *nchars
<= endpos
&& charpos
+ *nchars
> *disp_pos
1053 SET_TEXT_POS (pos
, charpos
+ *nchars
, bytepos
+ *ch_len
);
1054 *disp_pos
= compute_display_string_pos (&pos
, string
, frame_window_p
,
1062 /***********************************************************************
1063 Determining paragraph direction
1064 ***********************************************************************/
1066 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
1067 Value is the non-negative length of the paragraph separator
1068 following the buffer position, -1 if position is at the beginning
1069 of a new paragraph, or -2 if position is neither at beginning nor
1070 at end of a paragraph. */
1072 bidi_at_paragraph_end (ptrdiff_t charpos
, ptrdiff_t bytepos
)
1075 Lisp_Object start_re
;
1078 sep_re
= paragraph_separate_re
;
1079 start_re
= paragraph_start_re
;
1081 val
= fast_looking_at (sep_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
);
1084 if (fast_looking_at (start_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
) >= 0)
1093 /* On my 2005-vintage machine, searching back for paragraph start
1094 takes ~1 ms per line. And bidi_paragraph_init is called 4 times
1095 when user types C-p. The number below limits each call to
1096 bidi_paragraph_init to about 10 ms. */
1097 #define MAX_PARAGRAPH_SEARCH 7500
1099 /* Find the beginning of this paragraph by looking back in the buffer.
1100 Value is the byte position of the paragraph's beginning, or
1101 BEGV_BYTE if paragraph_start_re is still not found after looking
1102 back MAX_PARAGRAPH_SEARCH lines in the buffer. */
1104 bidi_find_paragraph_start (ptrdiff_t pos
, ptrdiff_t pos_byte
)
1106 Lisp_Object re
= paragraph_start_re
;
1107 ptrdiff_t limit
= ZV
, limit_byte
= ZV_BYTE
;
1110 while (pos_byte
> BEGV_BYTE
1111 && n
++ < MAX_PARAGRAPH_SEARCH
1112 && fast_looking_at (re
, pos
, pos_byte
, limit
, limit_byte
, Qnil
) < 0)
1114 /* FIXME: What if the paragraph beginning is covered by a
1115 display string? And what if a display string covering some
1116 of the text over which we scan back includes
1117 paragraph_start_re? */
1118 pos
= find_next_newline_no_quit (pos
- 1, -1);
1119 pos_byte
= CHAR_TO_BYTE (pos
);
1121 if (n
>= MAX_PARAGRAPH_SEARCH
)
1122 pos_byte
= BEGV_BYTE
;
1126 /* On a 3.4 GHz machine, searching forward for a strong directional
1127 character in a long paragraph full of weaks or neutrals takes about
1128 1 ms for each 20K characters. The number below limits each call to
1129 bidi_paragraph_init to less than 10 ms even on slow machines. */
1130 #define MAX_STRONG_CHAR_SEARCH 100000
1132 /* Determine the base direction, a.k.a. base embedding level, of the
1133 paragraph we are about to iterate through. If DIR is either L2R or
1134 R2L, just use that. Otherwise, determine the paragraph direction
1135 from the first strong directional character of the paragraph.
1137 NO_DEFAULT_P non-zero means don't default to L2R if the paragraph
1138 has no strong directional characters and both DIR and
1139 bidi_it->paragraph_dir are NEUTRAL_DIR. In that case, search back
1140 in the buffer until a paragraph is found with a strong character,
1141 or until hitting BEGV. In the latter case, fall back to L2R. This
1142 flag is used in current-bidi-paragraph-direction.
1144 Note that this function gives the paragraph separator the same
1145 direction as the preceding paragraph, even though Emacs generally
1146 views the separator as not belonging to any paragraph. */
1148 bidi_paragraph_init (bidi_dir_t dir
, struct bidi_it
*bidi_it
, int no_default_p
)
1150 ptrdiff_t bytepos
= bidi_it
->bytepos
;
1151 int string_p
= bidi_it
->string
.s
!= NULL
|| STRINGP (bidi_it
->string
.lstring
);
1152 ptrdiff_t pstartbyte
;
1153 /* Note that begbyte is a byte position, while end is a character
1154 position. Yes, this is ugly, but we are trying to avoid costly
1155 calls to BYTE_TO_CHAR and its ilk. */
1156 ptrdiff_t begbyte
= string_p
? 0 : BEGV_BYTE
;
1157 ptrdiff_t end
= string_p
? bidi_it
->string
.schars
: ZV
;
1159 /* Special case for an empty buffer. */
1160 if (bytepos
== begbyte
&& bidi_it
->charpos
== end
)
1162 /* We should never be called at EOB or before BEGV. */
1163 else if (bidi_it
->charpos
>= end
|| bytepos
< begbyte
)
1168 bidi_it
->paragraph_dir
= L2R
;
1169 bidi_it
->new_paragraph
= 0;
1171 else if (dir
== R2L
)
1173 bidi_it
->paragraph_dir
= R2L
;
1174 bidi_it
->new_paragraph
= 0;
1176 else if (dir
== NEUTRAL_DIR
) /* P2 */
1179 ptrdiff_t ch_len
, nchars
;
1180 ptrdiff_t pos
, disp_pos
= -1;
1183 const unsigned char *s
;
1185 if (!bidi_initialized
)
1188 /* If we are inside a paragraph separator, we are just waiting
1189 for the separator to be exhausted; use the previous paragraph
1190 direction. But don't do that if we have been just reseated,
1191 because we need to reinitialize below in that case. */
1192 if (!bidi_it
->first_elt
1193 && bidi_it
->charpos
< bidi_it
->separator_limit
)
1196 /* If we are on a newline, get past it to where the next
1197 paragraph might start. But don't do that at BEGV since then
1198 we are potentially in a new paragraph that doesn't yet
1200 pos
= bidi_it
->charpos
;
1201 s
= (STRINGP (bidi_it
->string
.lstring
)
1202 ? SDATA (bidi_it
->string
.lstring
)
1203 : bidi_it
->string
.s
);
1204 if (bytepos
> begbyte
1205 && bidi_char_at_pos (bytepos
, s
, bidi_it
->string
.unibyte
) == '\n')
1211 /* We are either at the beginning of a paragraph or in the
1212 middle of it. Find where this paragraph starts. */
1215 /* We don't support changes of paragraph direction inside a
1216 string. It is treated as a single paragraph. */
1220 pstartbyte
= bidi_find_paragraph_start (pos
, bytepos
);
1221 bidi_it
->separator_limit
= -1;
1222 bidi_it
->new_paragraph
= 0;
1224 /* The following loop is run more than once only if NO_DEFAULT_P
1225 is non-zero, and only if we are iterating on a buffer. */
1229 bytepos
= pstartbyte
;
1231 pos
= BYTE_TO_CHAR (bytepos
);
1232 ch
= bidi_fetch_char (bytepos
, pos
, &disp_pos
, &disp_prop
,
1234 bidi_it
->frame_window_p
, &ch_len
, &nchars
);
1235 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
1238 for (pos
+= nchars
, bytepos
+= ch_len
;
1239 ((bidi_get_category (type
) != STRONG
)
1240 || (bidi_ignore_explicit_marks_for_paragraph_level
1241 && (type
== RLE
|| type
== RLO
1242 || type
== LRE
|| type
== LRO
)))
1243 /* Stop when searched too far into an abnormally large
1244 paragraph full of weak or neutral characters. */
1245 && pos
- pos1
< MAX_STRONG_CHAR_SEARCH
;
1246 type
= bidi_get_type (ch
, NEUTRAL_DIR
))
1250 /* Pretend there's a paragraph separator at end of
1256 && type
== NEUTRAL_B
1257 && bidi_at_paragraph_end (pos
, bytepos
) >= -1)
1259 /* Fetch next character and advance to get past it. */
1260 ch
= bidi_fetch_char (bytepos
, pos
, &disp_pos
,
1261 &disp_prop
, &bidi_it
->string
,
1262 bidi_it
->frame_window_p
, &ch_len
, &nchars
);
1266 if ((type
== STRONG_R
|| type
== STRONG_AL
) /* P3 */
1267 || (!bidi_ignore_explicit_marks_for_paragraph_level
1268 && (type
== RLO
|| type
== RLE
)))
1269 bidi_it
->paragraph_dir
= R2L
;
1270 else if (type
== STRONG_L
1271 || (!bidi_ignore_explicit_marks_for_paragraph_level
1272 && (type
== LRO
|| type
== LRE
)))
1273 bidi_it
->paragraph_dir
= L2R
;
1275 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
)
1277 /* If this paragraph is at BEGV, default to L2R. */
1278 if (pstartbyte
== BEGV_BYTE
)
1279 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 */
1282 ptrdiff_t prevpbyte
= pstartbyte
;
1283 ptrdiff_t p
= BYTE_TO_CHAR (pstartbyte
), pbyte
= pstartbyte
;
1285 /* Find the beginning of the previous paragraph, if any. */
1286 while (pbyte
> BEGV_BYTE
&& prevpbyte
>= pstartbyte
)
1288 /* FXIME: What if p is covered by a display
1289 string? See also a FIXME inside
1290 bidi_find_paragraph_start. */
1292 pbyte
= CHAR_TO_BYTE (p
);
1293 prevpbyte
= bidi_find_paragraph_start (p
, pbyte
);
1295 pstartbyte
= prevpbyte
;
1299 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
);
1304 /* Contrary to UAX#9 clause P3, we only default the paragraph
1305 direction to L2R if we have no previous usable paragraph
1306 direction. This is allowed by the HL1 clause. */
1307 if (bidi_it
->paragraph_dir
!= L2R
&& bidi_it
->paragraph_dir
!= R2L
)
1308 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 ``higher-level protocols'' */
1309 if (bidi_it
->paragraph_dir
== R2L
)
1310 bidi_it
->level_stack
[0].level
= 1;
1312 bidi_it
->level_stack
[0].level
= 0;
1314 bidi_line_init (bidi_it
);
1318 /***********************************************************************
1319 Resolving explicit and implicit levels.
1320 The rest of this file constitutes the core of the UBA implementation.
1321 ***********************************************************************/
1324 bidi_explicit_dir_char (int ch
)
1326 bidi_type_t ch_type
;
1328 if (!bidi_initialized
)
1330 ch_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
1331 return (ch_type
== LRE
|| ch_type
== LRO
1332 || ch_type
== RLE
|| ch_type
== RLO
1336 /* A helper function for bidi_resolve_explicit. It advances to the
1337 next character in logical order and determines the new embedding
1338 level and directional override, but does not take into account
1339 empty embeddings. */
1341 bidi_resolve_explicit_1 (struct bidi_it
*bidi_it
)
1347 bidi_dir_t override
;
1348 int string_p
= bidi_it
->string
.s
!= NULL
|| STRINGP (bidi_it
->string
.lstring
);
1350 /* If reseat()'ed, don't advance, so as to start iteration from the
1351 position where we were reseated. bidi_it->bytepos can be less
1352 than BEGV_BYTE after reseat to BEGV. */
1353 if (bidi_it
->bytepos
< (string_p
? 0 : BEGV_BYTE
)
1354 || bidi_it
->first_elt
)
1356 bidi_it
->first_elt
= 0;
1359 const unsigned char *p
1360 = (STRINGP (bidi_it
->string
.lstring
)
1361 ? SDATA (bidi_it
->string
.lstring
)
1362 : bidi_it
->string
.s
);
1364 if (bidi_it
->charpos
< 0)
1365 bidi_it
->charpos
= 0;
1366 bidi_it
->bytepos
= bidi_count_bytes (p
, 0, 0, bidi_it
->charpos
,
1367 bidi_it
->string
.unibyte
);
1371 if (bidi_it
->charpos
< BEGV
)
1372 bidi_it
->charpos
= BEGV
;
1373 bidi_it
->bytepos
= CHAR_TO_BYTE (bidi_it
->charpos
);
1376 /* Don't move at end of buffer/string. */
1377 else if (bidi_it
->charpos
< (string_p
? bidi_it
->string
.schars
: ZV
))
1379 /* Advance to the next character, skipping characters covered by
1380 display strings (nchars > 1). */
1381 if (bidi_it
->nchars
<= 0)
1383 bidi_it
->charpos
+= bidi_it
->nchars
;
1384 if (bidi_it
->ch_len
== 0)
1386 bidi_it
->bytepos
+= bidi_it
->ch_len
;
1389 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
; /* X1 */
1390 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1391 new_level
= current_level
;
1393 if (bidi_it
->charpos
>= (string_p
? bidi_it
->string
.schars
: ZV
))
1396 bidi_it
->ch_len
= 1;
1397 bidi_it
->nchars
= 1;
1398 bidi_it
->disp_pos
= (string_p
? bidi_it
->string
.schars
: ZV
);
1399 bidi_it
->disp_prop
= 0;
1403 /* Fetch the character at BYTEPOS. If it is covered by a
1404 display string, treat the entire run of covered characters as
1405 a single character u+FFFC. */
1406 curchar
= bidi_fetch_char (bidi_it
->bytepos
, bidi_it
->charpos
,
1407 &bidi_it
->disp_pos
, &bidi_it
->disp_prop
,
1408 &bidi_it
->string
, bidi_it
->frame_window_p
,
1409 &bidi_it
->ch_len
, &bidi_it
->nchars
);
1411 bidi_it
->ch
= curchar
;
1413 /* Don't apply directional override here, as all the types we handle
1414 below will not be affected by the override anyway, and we need
1415 the original type unaltered. The override will be applied in
1416 bidi_resolve_weak. */
1417 type
= bidi_get_type (curchar
, NEUTRAL_DIR
);
1418 bidi_it
->orig_type
= type
;
1419 bidi_check_type (bidi_it
->orig_type
);
1422 bidi_it
->prev_was_pdf
= 0;
1424 bidi_it
->type_after_w1
= UNKNOWN_BT
;
1430 bidi_it
->type_after_w1
= type
;
1431 bidi_check_type (bidi_it
->type_after_w1
);
1432 type
= WEAK_BN
; /* X9/Retaining */
1433 if (bidi_it
->ignore_bn_limit
<= -1)
1435 if (current_level
<= BIDI_MAXLEVEL
- 4)
1437 /* Compute the least odd embedding level greater than
1438 the current level. */
1439 new_level
= ((current_level
+ 1) & ~1) + 1;
1440 if (bidi_it
->type_after_w1
== RLE
)
1441 override
= NEUTRAL_DIR
;
1444 if (current_level
== BIDI_MAXLEVEL
- 4)
1445 bidi_it
->invalid_rl_levels
= 0;
1446 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1450 bidi_it
->invalid_levels
++;
1451 /* See the commentary about invalid_rl_levels below. */
1452 if (bidi_it
->invalid_rl_levels
< 0)
1453 bidi_it
->invalid_rl_levels
= 0;
1454 bidi_it
->invalid_rl_levels
++;
1457 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1458 || (bidi_it
->next_en_pos
> bidi_it
->charpos
1459 && bidi_it
->next_en_type
== WEAK_EN
))
1464 bidi_it
->type_after_w1
= type
;
1465 bidi_check_type (bidi_it
->type_after_w1
);
1466 type
= WEAK_BN
; /* X9/Retaining */
1467 if (bidi_it
->ignore_bn_limit
<= -1)
1469 if (current_level
<= BIDI_MAXLEVEL
- 5)
1471 /* Compute the least even embedding level greater than
1472 the current level. */
1473 new_level
= ((current_level
+ 2) & ~1);
1474 if (bidi_it
->type_after_w1
== LRE
)
1475 override
= NEUTRAL_DIR
;
1478 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1482 bidi_it
->invalid_levels
++;
1483 /* invalid_rl_levels counts invalid levels encountered
1484 while the embedding level was already too high for
1485 LRE/LRO, but not for RLE/RLO. That is because
1486 there may be exactly one PDF which we should not
1487 ignore even though invalid_levels is non-zero.
1488 invalid_rl_levels helps to know what PDF is
1490 if (bidi_it
->invalid_rl_levels
>= 0)
1491 bidi_it
->invalid_rl_levels
++;
1494 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1495 || (bidi_it
->next_en_pos
> bidi_it
->charpos
1496 && bidi_it
->next_en_type
== WEAK_EN
))
1500 bidi_it
->type_after_w1
= type
;
1501 bidi_check_type (bidi_it
->type_after_w1
);
1502 type
= WEAK_BN
; /* X9/Retaining */
1503 if (bidi_it
->ignore_bn_limit
<= -1)
1505 if (!bidi_it
->invalid_rl_levels
)
1507 new_level
= bidi_pop_embedding_level (bidi_it
);
1508 bidi_it
->invalid_rl_levels
= -1;
1509 if (bidi_it
->invalid_levels
)
1510 bidi_it
->invalid_levels
--;
1511 /* else nothing: UAX#9 says to ignore invalid PDFs */
1513 if (!bidi_it
->invalid_levels
)
1514 new_level
= bidi_pop_embedding_level (bidi_it
);
1517 bidi_it
->invalid_levels
--;
1518 bidi_it
->invalid_rl_levels
--;
1521 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1522 || (bidi_it
->next_en_pos
> bidi_it
->charpos
1523 && bidi_it
->next_en_type
== WEAK_EN
))
1531 bidi_it
->type
= type
;
1532 bidi_check_type (bidi_it
->type
);
1537 /* Given an iterator state in BIDI_IT, advance one character position
1538 in the buffer/string to the next character (in the logical order),
1539 resolve any explicit embeddings and directional overrides, and
1540 return the embedding level of the character after resolving
1541 explicit directives and ignoring empty embeddings. */
1543 bidi_resolve_explicit (struct bidi_it
*bidi_it
)
1545 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1546 int new_level
= bidi_resolve_explicit_1 (bidi_it
);
1547 ptrdiff_t eob
= bidi_it
->string
.s
? bidi_it
->string
.schars
: ZV
;
1548 const unsigned char *s
1549 = (STRINGP (bidi_it
->string
.lstring
)
1550 ? SDATA (bidi_it
->string
.lstring
)
1551 : bidi_it
->string
.s
);
1553 if (prev_level
< new_level
1554 && bidi_it
->type
== WEAK_BN
1555 && bidi_it
->ignore_bn_limit
== -1 /* only if not already known */
1556 && bidi_it
->charpos
< eob
/* not already at EOB */
1557 && bidi_explicit_dir_char (bidi_char_at_pos (bidi_it
->bytepos
1558 + bidi_it
->ch_len
, s
,
1559 bidi_it
->string
.unibyte
)))
1561 /* Avoid pushing and popping embedding levels if the level run
1562 is empty, as this breaks level runs where it shouldn't.
1563 UAX#9 removes all the explicit embedding and override codes,
1564 so empty embeddings disappear without a trace. We need to
1565 behave as if we did the same. */
1566 struct bidi_it saved_it
;
1567 int level
= prev_level
;
1569 bidi_copy_it (&saved_it
, bidi_it
);
1571 while (bidi_explicit_dir_char (bidi_char_at_pos (bidi_it
->bytepos
1572 + bidi_it
->ch_len
, s
,
1573 bidi_it
->string
.unibyte
)))
1575 /* This advances to the next character, skipping any
1576 characters covered by display strings. */
1577 level
= bidi_resolve_explicit_1 (bidi_it
);
1578 /* If string.lstring was relocated inside bidi_resolve_explicit_1,
1579 a pointer to its data is no longer valid. */
1580 if (STRINGP (bidi_it
->string
.lstring
))
1581 s
= SDATA (bidi_it
->string
.lstring
);
1584 if (bidi_it
->nchars
<= 0)
1586 if (level
== prev_level
) /* empty embedding */
1587 saved_it
.ignore_bn_limit
= bidi_it
->charpos
+ bidi_it
->nchars
;
1588 else /* this embedding is non-empty */
1589 saved_it
.ignore_bn_limit
= -2;
1591 bidi_copy_it (bidi_it
, &saved_it
);
1592 if (bidi_it
->ignore_bn_limit
> -1)
1594 /* We pushed a level, but we shouldn't have. Undo that. */
1595 if (!bidi_it
->invalid_rl_levels
)
1597 new_level
= bidi_pop_embedding_level (bidi_it
);
1598 bidi_it
->invalid_rl_levels
= -1;
1599 if (bidi_it
->invalid_levels
)
1600 bidi_it
->invalid_levels
--;
1602 if (!bidi_it
->invalid_levels
)
1603 new_level
= bidi_pop_embedding_level (bidi_it
);
1606 bidi_it
->invalid_levels
--;
1607 bidi_it
->invalid_rl_levels
--;
1612 if (bidi_it
->type
== NEUTRAL_B
) /* X8 */
1614 bidi_set_paragraph_end (bidi_it
);
1615 /* This is needed by bidi_resolve_weak below, and in L1. */
1616 bidi_it
->type_after_w1
= bidi_it
->type
;
1617 bidi_check_type (bidi_it
->type_after_w1
);
1623 /* Advance in the buffer/string, resolve weak types and return the
1624 type of the next character after weak type resolution. */
1626 bidi_resolve_weak (struct bidi_it
*bidi_it
)
1629 bidi_dir_t override
;
1630 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1631 int new_level
= bidi_resolve_explicit (bidi_it
);
1633 bidi_type_t type_of_next
;
1634 struct bidi_it saved_it
;
1636 = ((STRINGP (bidi_it
->string
.lstring
) || bidi_it
->string
.s
)
1637 ? bidi_it
->string
.schars
: ZV
);
1639 type
= bidi_it
->type
;
1640 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1642 if (type
== UNKNOWN_BT
1650 if (new_level
!= prev_level
1651 || bidi_it
->type
== NEUTRAL_B
)
1653 /* We've got a new embedding level run, compute the directional
1654 type of sor and initialize per-run variables (UAX#9, clause
1656 bidi_set_sor_type (bidi_it
, prev_level
, new_level
);
1658 else if (type
== NEUTRAL_S
|| type
== NEUTRAL_WS
1659 || type
== WEAK_BN
|| type
== STRONG_AL
)
1660 bidi_it
->type_after_w1
= type
; /* needed in L1 */
1661 bidi_check_type (bidi_it
->type_after_w1
);
1663 /* Level and directional override status are already recorded in
1664 bidi_it, and do not need any change; see X6. */
1665 if (override
== R2L
) /* X6 */
1667 else if (override
== L2R
)
1671 if (type
== WEAK_NSM
) /* W1 */
1673 /* Note that we don't need to consider the case where the
1674 prev character has its type overridden by an RLO or LRO,
1675 because then either the type of this NSM would have been
1676 also overridden, or the previous character is outside the
1677 current level run, and thus not relevant to this NSM.
1678 This is why NSM gets the type_after_w1 of the previous
1680 if (bidi_it
->prev
.type_after_w1
!= UNKNOWN_BT
1681 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1682 && bidi_it
->prev
.type_after_w1
!= NEUTRAL_B
)
1683 type
= bidi_it
->prev
.type_after_w1
;
1684 else if (bidi_it
->sor
== R2L
)
1686 else if (bidi_it
->sor
== L2R
)
1688 else /* shouldn't happen! */
1691 if (type
== WEAK_EN
/* W2 */
1692 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1694 else if (type
== STRONG_AL
) /* W3 */
1696 else if ((type
== WEAK_ES
/* W4 */
1697 && bidi_it
->prev
.type_after_w1
== WEAK_EN
1698 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1700 && ((bidi_it
->prev
.type_after_w1
== WEAK_EN
1701 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1702 || bidi_it
->prev
.type_after_w1
== WEAK_AN
)))
1704 const unsigned char *s
1705 = (STRINGP (bidi_it
->string
.lstring
)
1706 ? SDATA (bidi_it
->string
.lstring
)
1707 : bidi_it
->string
.s
);
1709 next_char
= (bidi_it
->charpos
+ bidi_it
->nchars
>= eob
1711 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
,
1712 s
, bidi_it
->string
.unibyte
));
1713 type_of_next
= bidi_get_type (next_char
, override
);
1715 if (type_of_next
== WEAK_BN
1716 || bidi_explicit_dir_char (next_char
))
1718 bidi_copy_it (&saved_it
, bidi_it
);
1719 while (bidi_resolve_explicit (bidi_it
) == new_level
1720 && bidi_it
->type
== WEAK_BN
)
1722 type_of_next
= bidi_it
->type
;
1723 bidi_copy_it (bidi_it
, &saved_it
);
1726 /* If the next character is EN, but the last strong-type
1727 character is AL, that next EN will be changed to AN when
1728 we process it in W2 above. So in that case, this ES
1729 should not be changed into EN. */
1731 && type_of_next
== WEAK_EN
1732 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1734 else if (type
== WEAK_CS
)
1736 if (bidi_it
->prev
.type_after_w1
== WEAK_AN
1737 && (type_of_next
== WEAK_AN
1738 /* If the next character is EN, but the last
1739 strong-type character is AL, EN will be later
1740 changed to AN when we process it in W2 above.
1741 So in that case, this ES should not be
1743 || (type_of_next
== WEAK_EN
1744 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)))
1746 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
1747 && type_of_next
== WEAK_EN
1748 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1752 else if (type
== WEAK_ET
/* W5: ET with EN before or after it */
1753 || type
== WEAK_BN
) /* W5/Retaining */
1755 if (bidi_it
->prev
.type_after_w1
== WEAK_EN
) /* ET/BN w/EN before it */
1757 else if (bidi_it
->next_en_pos
> bidi_it
->charpos
1758 && bidi_it
->next_en_type
!= WEAK_BN
)
1760 if (bidi_it
->next_en_type
== WEAK_EN
) /* ET/BN with EN after it */
1763 else if (bidi_it
->next_en_pos
>=0)
1765 ptrdiff_t en_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
1766 const unsigned char *s
= (STRINGP (bidi_it
->string
.lstring
)
1767 ? SDATA (bidi_it
->string
.lstring
)
1768 : bidi_it
->string
.s
);
1770 if (bidi_it
->nchars
<= 0)
1773 = (bidi_it
->charpos
+ bidi_it
->nchars
>= eob
1775 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
, s
,
1776 bidi_it
->string
.unibyte
));
1777 type_of_next
= bidi_get_type (next_char
, override
);
1779 if (type_of_next
== WEAK_ET
1780 || type_of_next
== WEAK_BN
1781 || bidi_explicit_dir_char (next_char
))
1783 bidi_copy_it (&saved_it
, bidi_it
);
1784 while (bidi_resolve_explicit (bidi_it
) == new_level
1785 && (bidi_it
->type
== WEAK_BN
1786 || bidi_it
->type
== WEAK_ET
))
1788 type_of_next
= bidi_it
->type
;
1789 en_pos
= bidi_it
->charpos
;
1790 bidi_copy_it (bidi_it
, &saved_it
);
1792 /* Remember this position, to speed up processing of the
1794 bidi_it
->next_en_pos
= en_pos
;
1795 if (type_of_next
== WEAK_EN
)
1797 /* If the last strong character is AL, the EN we've
1798 found will become AN when we get to it (W2). */
1799 if (bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1800 type_of_next
= WEAK_AN
;
1801 else if (type
== WEAK_BN
)
1802 type
= NEUTRAL_ON
; /* W6/Retaining */
1806 else if (type_of_next
== NEUTRAL_B
)
1807 /* Record the fact that there are no more ENs from
1808 here to the end of paragraph, to avoid entering the
1809 loop above ever again in this paragraph. */
1810 bidi_it
->next_en_pos
= -1;
1811 /* Record the type of the character where we ended our search. */
1812 bidi_it
->next_en_type
= type_of_next
;
1817 if (type
== WEAK_ES
|| type
== WEAK_ET
|| type
== WEAK_CS
/* W6 */
1819 && (bidi_it
->prev
.type_after_w1
== WEAK_CS
/* W6/Retaining */
1820 || bidi_it
->prev
.type_after_w1
== WEAK_ES
1821 || bidi_it
->prev
.type_after_w1
== WEAK_ET
)))
1824 /* Store the type we've got so far, before we clobber it with strong
1825 types in W7 and while resolving neutral types. But leave alone
1826 the original types that were recorded above, because we will need
1827 them for the L1 clause. */
1828 if (bidi_it
->type_after_w1
== UNKNOWN_BT
)
1829 bidi_it
->type_after_w1
= type
;
1830 bidi_check_type (bidi_it
->type_after_w1
);
1832 if (type
== WEAK_EN
) /* W7 */
1834 if ((bidi_it
->last_strong
.type_after_w1
== STRONG_L
)
1835 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
&& bidi_it
->sor
== L2R
))
1839 bidi_it
->type
= type
;
1840 bidi_check_type (bidi_it
->type
);
1844 /* Resolve the type of a neutral character according to the type of
1845 surrounding strong text and the current embedding level. */
1846 static inline bidi_type_t
1847 bidi_resolve_neutral_1 (bidi_type_t prev_type
, bidi_type_t next_type
, int lev
)
1849 /* N1: European and Arabic numbers are treated as though they were R. */
1850 if (next_type
== WEAK_EN
|| next_type
== WEAK_AN
)
1851 next_type
= STRONG_R
;
1852 if (prev_type
== WEAK_EN
|| prev_type
== WEAK_AN
)
1853 prev_type
= STRONG_R
;
1855 if (next_type
== prev_type
) /* N1 */
1857 else if ((lev
& 1) == 0) /* N2 */
1864 bidi_resolve_neutral (struct bidi_it
*bidi_it
)
1866 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1867 bidi_type_t type
= bidi_resolve_weak (bidi_it
);
1868 int current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1870 if (!(type
== STRONG_R
1875 || type
== NEUTRAL_B
1876 || type
== NEUTRAL_S
1877 || type
== NEUTRAL_WS
1878 || type
== NEUTRAL_ON
))
1881 if ((type
!= NEUTRAL_B
/* Don't risk entering the long loop below if
1882 we are already at paragraph end. */
1883 && bidi_get_category (type
) == NEUTRAL
)
1884 || (type
== WEAK_BN
&& prev_level
== current_level
))
1886 if (bidi_it
->next_for_neutral
.type
!= UNKNOWN_BT
)
1887 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1888 bidi_it
->next_for_neutral
.type
,
1890 /* The next two "else if" clauses are shortcuts for the
1891 important special case when we have a long sequence of
1892 neutral or WEAK_BN characters, such as whitespace or nulls or
1893 other control characters, on the base embedding level of the
1894 paragraph, and that sequence goes all the way to the end of
1895 the paragraph and follows a character whose resolved
1896 directionality is identical to the base embedding level.
1897 (This is what happens in a buffer with plain L2R text that
1898 happens to include long sequences of control characters.) By
1899 virtue of N1, the result of examining this long sequence will
1900 always be either STRONG_L or STRONG_R, depending on the base
1901 embedding level. So we use this fact directly instead of
1902 entering the expensive loop in the "else" clause. */
1903 else if (current_level
== 0
1904 && bidi_it
->prev_for_neutral
.type
== STRONG_L
1905 && !bidi_explicit_dir_char (bidi_it
->ch
))
1906 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1907 STRONG_L
, current_level
);
1908 else if (/* current level is 1 */
1910 /* base embedding level is also 1 */
1911 && bidi_it
->level_stack
[0].level
== 1
1912 /* previous character is one of those considered R for
1913 the purposes of W5 */
1914 && (bidi_it
->prev_for_neutral
.type
== STRONG_R
1915 || bidi_it
->prev_for_neutral
.type
== WEAK_EN
1916 || bidi_it
->prev_for_neutral
.type
== WEAK_AN
)
1917 && !bidi_explicit_dir_char (bidi_it
->ch
))
1918 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1919 STRONG_R
, current_level
);
1922 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1923 the assumption of batch-style processing; see clauses W4,
1924 W5, and especially N1, which require to look far forward
1925 (as well as back) in the buffer/string. May the fleas of
1926 a thousand camels infest the armpits of those who design
1927 supposedly general-purpose algorithms by looking at their
1928 own implementations, and fail to consider other possible
1930 struct bidi_it saved_it
;
1931 bidi_type_t next_type
;
1933 if (bidi_it
->scan_dir
== -1)
1936 bidi_copy_it (&saved_it
, bidi_it
);
1937 /* Scan the text forward until we find the first non-neutral
1938 character, and then use that to resolve the neutral we
1939 are dealing with now. We also cache the scanned iterator
1940 states, to salvage some of the effort later. */
1941 bidi_cache_iterator_state (bidi_it
, 0);
1943 /* Record the info about the previous character, so that
1944 it will be cached below with this state. */
1945 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1946 && bidi_it
->type
!= WEAK_BN
)
1947 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1948 type
= bidi_resolve_weak (bidi_it
);
1949 /* Paragraph separators have their levels fully resolved
1950 at this point, so cache them as resolved. */
1951 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
);
1952 /* FIXME: implement L1 here, by testing for a newline and
1953 resetting the level for any sequence of whitespace
1954 characters adjacent to it. */
1955 } while (!(type
== NEUTRAL_B
1957 && bidi_get_category (type
) != NEUTRAL
)
1958 /* This is all per level run, so stop when we
1959 reach the end of this level run. */
1960 || (bidi_it
->level_stack
[bidi_it
->stack_idx
].level
1961 != current_level
)));
1963 bidi_remember_char (&saved_it
.next_for_neutral
, bidi_it
);
1970 /* Actually, STRONG_AL cannot happen here, because
1971 bidi_resolve_weak converts it to STRONG_R, per W3. */
1972 eassert (type
!= STRONG_AL
);
1977 /* N1: ``European and Arabic numbers are treated as
1978 though they were R.'' */
1979 next_type
= STRONG_R
;
1982 if (!bidi_explicit_dir_char (bidi_it
->ch
))
1983 abort (); /* can't happen: BNs are skipped */
1986 /* Marched all the way to the end of this level run.
1987 We need to use the eor type, whose information is
1988 stored by bidi_set_sor_type in the prev_for_neutral
1990 if (saved_it
.type
!= WEAK_BN
1991 || bidi_get_category (bidi_it
->prev
.type_after_w1
) == NEUTRAL
)
1992 next_type
= bidi_it
->prev_for_neutral
.type
;
1995 /* This is a BN which does not adjoin neutrals.
1996 Leave its type alone. */
1997 bidi_copy_it (bidi_it
, &saved_it
);
1998 return bidi_it
->type
;
2004 type
= bidi_resolve_neutral_1 (saved_it
.prev_for_neutral
.type
,
2005 next_type
, current_level
);
2006 saved_it
.next_for_neutral
.type
= next_type
;
2007 saved_it
.type
= type
;
2008 bidi_check_type (next_type
);
2009 bidi_check_type (type
);
2010 bidi_copy_it (bidi_it
, &saved_it
);
2016 /* Given an iterator state in BIDI_IT, advance one character position
2017 in the buffer/string to the next character (in the logical order),
2018 resolve the bidi type of that next character, and return that
2021 bidi_type_of_next_char (struct bidi_it
*bidi_it
)
2025 /* This should always be called during a forward scan. */
2026 if (bidi_it
->scan_dir
!= 1)
2029 /* Reset the limit until which to ignore BNs if we step out of the
2030 area where we found only empty levels. */
2031 if ((bidi_it
->ignore_bn_limit
> -1
2032 && bidi_it
->ignore_bn_limit
<= bidi_it
->charpos
)
2033 || (bidi_it
->ignore_bn_limit
== -2
2034 && !bidi_explicit_dir_char (bidi_it
->ch
)))
2035 bidi_it
->ignore_bn_limit
= -1;
2037 type
= bidi_resolve_neutral (bidi_it
);
2042 /* Given an iterator state BIDI_IT, advance one character position in
2043 the buffer/string to the next character (in the current scan
2044 direction), resolve the embedding and implicit levels of that next
2045 character, and return the resulting level. */
2047 bidi_level_of_next_char (struct bidi_it
*bidi_it
)
2050 int level
, prev_level
= -1;
2051 struct bidi_saved_info next_for_neutral
;
2052 ptrdiff_t next_char_pos
= -2;
2054 if (bidi_it
->scan_dir
== 1)
2057 = ((bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
2058 ? bidi_it
->string
.schars
: ZV
);
2060 /* There's no sense in trying to advance if we hit end of text. */
2061 if (bidi_it
->charpos
>= eob
)
2062 return bidi_it
->resolved_level
;
2064 /* Record the info about the previous character. */
2065 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
2066 && bidi_it
->type
!= WEAK_BN
)
2067 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
2068 if (bidi_it
->type_after_w1
== STRONG_R
2069 || bidi_it
->type_after_w1
== STRONG_L
2070 || bidi_it
->type_after_w1
== STRONG_AL
)
2071 bidi_remember_char (&bidi_it
->last_strong
, bidi_it
);
2072 /* FIXME: it sounds like we don't need both prev and
2073 prev_for_neutral members, but I'm leaving them both for now. */
2074 if (bidi_it
->type
== STRONG_R
|| bidi_it
->type
== STRONG_L
2075 || bidi_it
->type
== WEAK_EN
|| bidi_it
->type
== WEAK_AN
)
2076 bidi_remember_char (&bidi_it
->prev_for_neutral
, bidi_it
);
2078 /* If we overstepped the characters used for resolving neutrals
2079 and whitespace, invalidate their info in the iterator. */
2080 if (bidi_it
->charpos
>= bidi_it
->next_for_neutral
.charpos
)
2081 bidi_it
->next_for_neutral
.type
= UNKNOWN_BT
;
2082 if (bidi_it
->next_en_pos
>= 0
2083 && bidi_it
->charpos
>= bidi_it
->next_en_pos
)
2085 bidi_it
->next_en_pos
= 0;
2086 bidi_it
->next_en_type
= UNKNOWN_BT
;
2088 if (bidi_it
->next_for_ws
.type
!= UNKNOWN_BT
2089 && bidi_it
->charpos
>= bidi_it
->next_for_ws
.charpos
)
2090 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
2092 /* This must be taken before we fill the iterator with the info
2093 about the next char. If we scan backwards, the iterator
2094 state must be already cached, so there's no need to know the
2095 embedding level of the previous character, since we will be
2096 returning to our caller shortly. */
2097 prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2099 next_for_neutral
= bidi_it
->next_for_neutral
;
2101 /* Perhaps the character we want is already cached. If it is, the
2102 call to bidi_cache_find below will return a type other than
2104 if (bidi_cache_idx
> bidi_cache_start
&& !bidi_it
->first_elt
)
2106 int bob
= ((bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
2108 if (bidi_it
->scan_dir
> 0)
2110 if (bidi_it
->nchars
<= 0)
2112 next_char_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
2114 else if (bidi_it
->charpos
>= bob
)
2115 /* Implementation note: we allow next_char_pos to be as low as
2116 0 for buffers or -1 for strings, and that is okay because
2117 that's the "position" of the sentinel iterator state we
2118 cached at the beginning of the iteration. */
2119 next_char_pos
= bidi_it
->charpos
- 1;
2120 if (next_char_pos
>= bob
- 1)
2121 type
= bidi_cache_find (next_char_pos
, -1, bidi_it
);
2127 if (type
!= UNKNOWN_BT
)
2129 /* Don't lose the information for resolving neutrals! The
2130 cached states could have been cached before their
2131 next_for_neutral member was computed. If we are on our way
2132 forward, we can simply take the info from the previous
2134 if (bidi_it
->scan_dir
== 1
2135 && bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
2136 bidi_it
->next_for_neutral
= next_for_neutral
;
2138 /* If resolved_level is -1, it means this state was cached
2139 before it was completely resolved, so we cannot return
2141 if (bidi_it
->resolved_level
!= -1)
2142 return bidi_it
->resolved_level
;
2144 if (bidi_it
->scan_dir
== -1)
2145 /* If we are going backwards, the iterator state is already cached
2146 from previous scans, and should be fully resolved. */
2149 if (type
== UNKNOWN_BT
)
2150 type
= bidi_type_of_next_char (bidi_it
);
2152 if (type
== NEUTRAL_B
)
2153 return bidi_it
->resolved_level
;
2155 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2156 if ((bidi_get_category (type
) == NEUTRAL
/* && type != NEUTRAL_B */)
2157 || (type
== WEAK_BN
&& prev_level
== level
))
2159 if (bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
2162 /* If the cached state shows a neutral character, it was not
2163 resolved by bidi_resolve_neutral, so do it now. */
2164 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
2165 bidi_it
->next_for_neutral
.type
,
2169 if (!(type
== STRONG_R
2173 || type
== WEAK_AN
))
2175 bidi_it
->type
= type
;
2176 bidi_check_type (bidi_it
->type
);
2178 /* For L1 below, we need to know, for each WS character, whether
2179 it belongs to a sequence of WS characters preceding a newline
2180 or a TAB or a paragraph separator. */
2181 if (bidi_it
->orig_type
== NEUTRAL_WS
2182 && bidi_it
->next_for_ws
.type
== UNKNOWN_BT
)
2185 ptrdiff_t clen
= bidi_it
->ch_len
;
2186 ptrdiff_t bpos
= bidi_it
->bytepos
;
2187 ptrdiff_t cpos
= bidi_it
->charpos
;
2188 ptrdiff_t disp_pos
= bidi_it
->disp_pos
;
2189 ptrdiff_t nc
= bidi_it
->nchars
;
2190 struct bidi_string_data bs
= bidi_it
->string
;
2192 int fwp
= bidi_it
->frame_window_p
;
2193 int dpp
= bidi_it
->disp_prop
;
2195 if (bidi_it
->nchars
<= 0)
2198 ch
= bidi_fetch_char (bpos
+= clen
, cpos
+= nc
, &disp_pos
, &dpp
, &bs
,
2200 if (ch
== '\n' || ch
== BIDI_EOB
)
2203 chtype
= bidi_get_type (ch
, NEUTRAL_DIR
);
2204 } while (chtype
== NEUTRAL_WS
|| chtype
== WEAK_BN
2205 || bidi_explicit_dir_char (ch
)); /* L1/Retaining */
2206 bidi_it
->next_for_ws
.type
= chtype
;
2207 bidi_check_type (bidi_it
->next_for_ws
.type
);
2208 bidi_it
->next_for_ws
.charpos
= cpos
;
2209 bidi_it
->next_for_ws
.bytepos
= bpos
;
2212 /* Resolve implicit levels, with a twist: PDFs get the embedding
2213 level of the embedding they terminate. See below for the
2215 if (bidi_it
->orig_type
== PDF
2216 /* Don't do this if this formatting code didn't change the
2217 embedding level due to invalid or empty embeddings. */
2218 && prev_level
!= level
)
2220 /* Don't look in UAX#9 for the reason for this: it's our own
2221 private quirk. The reason is that we want the formatting
2222 codes to be delivered so that they bracket the text of their
2223 embedding. For example, given the text
2227 we want it to be displayed as
2235 which will result because we bump up the embedding level as
2236 soon as we see the RLO and pop it as soon as we see the PDF,
2237 so RLO itself has the same embedding level as "teST", and
2238 thus would be normally delivered last, just before the PDF.
2239 The switch below fiddles with the level of PDF so that this
2240 ugly side effect does not happen.
2242 (This is, of course, only important if the formatting codes
2243 are actually displayed, but Emacs does need to display them
2244 if the user wants to.) */
2247 else if (bidi_it
->orig_type
== NEUTRAL_B
/* L1 */
2248 || bidi_it
->orig_type
== NEUTRAL_S
2249 || bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
2250 || (bidi_it
->orig_type
== NEUTRAL_WS
2251 && (bidi_it
->next_for_ws
.type
== NEUTRAL_B
2252 || bidi_it
->next_for_ws
.type
== NEUTRAL_S
)))
2253 level
= bidi_it
->level_stack
[0].level
;
2254 else if ((level
& 1) == 0) /* I1 */
2256 if (type
== STRONG_R
)
2258 else if (type
== WEAK_EN
|| type
== WEAK_AN
)
2263 if (type
== STRONG_L
|| type
== WEAK_EN
|| type
== WEAK_AN
)
2267 bidi_it
->resolved_level
= level
;
2271 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
2272 non-zero, we are at the end of a level, and we need to prepare to
2273 resume the scan of the lower level.
2275 If this level's other edge is cached, we simply jump to it, filling
2276 the iterator structure with the iterator state on the other edge.
2277 Otherwise, we walk the buffer or string until we come back to the
2278 same level as LEVEL.
2280 Note: we are not talking here about a ``level run'' in the UAX#9
2281 sense of the term, but rather about a ``level'' which includes
2282 all the levels higher than it. In other words, given the levels
2285 11111112222222333333334443343222222111111112223322111
2288 and assuming we are at point A scanning left to right, this
2289 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
2292 bidi_find_other_level_edge (struct bidi_it
*bidi_it
, int level
, int end_flag
)
2294 int dir
= end_flag
? -bidi_it
->scan_dir
: bidi_it
->scan_dir
;
2297 /* Try the cache first. */
2298 if ((idx
= bidi_cache_find_level_change (level
, dir
, end_flag
))
2299 >= bidi_cache_start
)
2300 bidi_cache_fetch_state (idx
, bidi_it
);
2306 abort (); /* if we are at end of level, its edges must be cached */
2308 bidi_cache_iterator_state (bidi_it
, 1);
2310 new_level
= bidi_level_of_next_char (bidi_it
);
2311 bidi_cache_iterator_state (bidi_it
, 1);
2312 } while (new_level
>= level
);
2317 bidi_move_to_visually_next (struct bidi_it
*bidi_it
)
2319 int old_level
, new_level
, next_level
;
2320 struct bidi_it sentinel
;
2321 struct gcpro gcpro1
;
2323 if (bidi_it
->charpos
< 0 || bidi_it
->bytepos
< 0)
2326 if (bidi_it
->scan_dir
== 0)
2328 bidi_it
->scan_dir
= 1; /* default to logical order */
2331 /* The code below can call eval, and thus cause GC. If we are
2332 iterating a Lisp string, make sure it won't be GCed. */
2333 if (STRINGP (bidi_it
->string
.lstring
))
2334 GCPRO1 (bidi_it
->string
.lstring
);
2336 /* If we just passed a newline, initialize for the next line. */
2337 if (!bidi_it
->first_elt
2338 && (bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
))
2339 bidi_line_init (bidi_it
);
2341 /* Prepare the sentinel iterator state, and cache it. When we bump
2342 into it, scanning backwards, we'll know that the last non-base
2343 level is exhausted. */
2344 if (bidi_cache_idx
== bidi_cache_start
)
2346 bidi_copy_it (&sentinel
, bidi_it
);
2347 if (bidi_it
->first_elt
)
2349 sentinel
.charpos
--; /* cached charpos needs to be monotonic */
2351 sentinel
.ch
= '\n'; /* doesn't matter, but why not? */
2352 sentinel
.ch_len
= 1;
2353 sentinel
.nchars
= 1;
2355 bidi_cache_iterator_state (&sentinel
, 1);
2358 old_level
= bidi_it
->resolved_level
;
2359 new_level
= bidi_level_of_next_char (bidi_it
);
2361 /* Reordering of resolved levels (clause L2) is implemented by
2362 jumping to the other edge of the level and flipping direction of
2363 scanning the text whenever we find a level change. */
2364 if (new_level
!= old_level
)
2366 int ascending
= new_level
> old_level
;
2367 int level_to_search
= ascending
? old_level
+ 1 : old_level
;
2368 int incr
= ascending
? 1 : -1;
2369 int expected_next_level
= old_level
+ incr
;
2371 /* Jump (or walk) to the other edge of this level. */
2372 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
2373 /* Switch scan direction and peek at the next character in the
2375 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
2377 /* The following loop handles the case where the resolved level
2378 jumps by more than one. This is typical for numbers inside a
2379 run of text with left-to-right embedding direction, but can
2380 also happen in other situations. In those cases the decision
2381 where to continue after a level change, and in what direction,
2382 is tricky. For example, given a text like below:
2387 (where the numbers below the text show the resolved levels),
2388 the result of reordering according to UAX#9 should be this:
2392 This is implemented by the loop below which flips direction
2393 and jumps to the other edge of the level each time it finds
2394 the new level not to be the expected one. The expected level
2395 is always one more or one less than the previous one. */
2396 next_level
= bidi_peek_at_next_level (bidi_it
);
2397 while (next_level
!= expected_next_level
)
2399 expected_next_level
+= incr
;
2400 level_to_search
+= incr
;
2401 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
2402 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
2403 next_level
= bidi_peek_at_next_level (bidi_it
);
2406 /* Finally, deliver the next character in the new direction. */
2407 next_level
= bidi_level_of_next_char (bidi_it
);
2410 /* Take note when we have just processed the newline that precedes
2411 the end of the paragraph. The next time we are about to be
2412 called, set_iterator_to_next will automatically reinit the
2413 paragraph direction, if needed. We do this at the newline before
2414 the paragraph separator, because the next character might not be
2415 the first character of the next paragraph, due to the bidi
2416 reordering, whereas we _must_ know the paragraph base direction
2417 _before_ we process the paragraph's text, since the base
2418 direction affects the reordering. */
2419 if (bidi_it
->scan_dir
== 1
2420 && (bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
))
2422 /* The paragraph direction of the entire string, once
2423 determined, is in effect for the entire string. Setting the
2424 separator limit to the end of the string prevents
2425 bidi_paragraph_init from being called automatically on this
2427 if (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
2428 bidi_it
->separator_limit
= bidi_it
->string
.schars
;
2429 else if (bidi_it
->bytepos
< ZV_BYTE
)
2432 = bidi_at_paragraph_end (bidi_it
->charpos
+ bidi_it
->nchars
,
2433 bidi_it
->bytepos
+ bidi_it
->ch_len
);
2434 if (bidi_it
->nchars
<= 0)
2438 bidi_it
->new_paragraph
= 1;
2439 /* Record the buffer position of the last character of the
2440 paragraph separator. */
2441 bidi_it
->separator_limit
2442 = bidi_it
->charpos
+ bidi_it
->nchars
+ sep_len
;
2447 if (bidi_it
->scan_dir
== 1 && bidi_cache_idx
> bidi_cache_start
)
2449 /* If we are at paragraph's base embedding level and beyond the
2450 last cached position, the cache's job is done and we can
2452 if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
2453 && bidi_it
->charpos
> (bidi_cache
[bidi_cache_idx
- 1].charpos
2454 + bidi_cache
[bidi_cache_idx
- 1].nchars
- 1))
2455 bidi_cache_reset ();
2456 /* But as long as we are caching during forward scan, we must
2457 cache each state, or else the cache integrity will be
2458 compromised: it assumes cached states correspond to buffer
2461 bidi_cache_iterator_state (bidi_it
, 1);
2464 if (STRINGP (bidi_it
->string
.lstring
))
2468 /* This is meant to be called from within the debugger, whenever you
2469 wish to examine the cache contents. */
2470 void bidi_dump_cached_states (void) EXTERNALLY_VISIBLE
;
2472 bidi_dump_cached_states (void)
2477 if (bidi_cache_idx
== 0)
2479 fprintf (stderr
, "The cache is empty.\n");
2482 fprintf (stderr
, "Total of %"pD
"d state%s in cache:\n",
2483 bidi_cache_idx
, bidi_cache_idx
== 1 ? "" : "s");
2485 for (i
= bidi_cache
[bidi_cache_idx
- 1].charpos
; i
> 0; i
/= 10)
2487 fputs ("ch ", stderr
);
2488 for (i
= 0; i
< bidi_cache_idx
; i
++)
2489 fprintf (stderr
, "%*c", ndigits
, bidi_cache
[i
].ch
);
2490 fputs ("\n", stderr
);
2491 fputs ("lvl ", stderr
);
2492 for (i
= 0; i
< bidi_cache_idx
; i
++)
2493 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].resolved_level
);
2494 fputs ("\n", stderr
);
2495 fputs ("pos ", stderr
);
2496 for (i
= 0; i
< bidi_cache_idx
; i
++)
2497 fprintf (stderr
, "%*"pD
"d", ndigits
, bidi_cache
[i
].charpos
);
2498 fputs ("\n", stderr
);