1 /* Low-level bidirectional buffer/string-scanning functions for GNU Emacs.
2 Copyright (C) 2000-2001, 2004-2005, 2009-2011
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 decribed in the "Implementation
55 Notes" section of UAX#9, under "Retaining Format Codes". */
63 #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 extern int bidi_ignore_explicit_marks_for_paragraph_level EXTERNALLY_VISIBLE
;
83 int bidi_ignore_explicit_marks_for_paragraph_level
= 1;
85 static Lisp_Object paragraph_start_re
, paragraph_separate_re
;
86 static Lisp_Object Qparagraph_start
, Qparagraph_separate
;
89 /***********************************************************************
91 ***********************************************************************/
93 /* Return the bidi type of a character CH, subject to the current
94 directional OVERRIDE. */
95 static inline bidi_type_t
96 bidi_get_type (int ch
, bidi_dir_t override
)
98 bidi_type_t default_type
;
102 if (ch
< 0 || ch
> MAX_CHAR
)
105 default_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
107 if (override
== NEUTRAL_DIR
)
110 switch (default_type
)
112 /* Although UAX#9 does not tell, it doesn't make sense to
113 override NEUTRAL_B and LRM/RLM characters. */
128 if (override
== L2R
) /* X6 */
130 else if (override
== R2L
)
133 abort (); /* can't happen: handled above */
139 bidi_check_type (bidi_type_t type
)
141 if (type
< UNKNOWN_BT
|| type
> NEUTRAL_ON
)
145 /* Given a bidi TYPE of a character, return its category. */
146 static inline bidi_category_t
147 bidi_get_category (bidi_type_t type
)
161 case PDF
: /* ??? really?? */
180 /* Return the mirrored character of C, if it has one. If C has no
181 mirrored counterpart, return C.
182 Note: The conditions in UAX#9 clause L4 regarding the surrounding
183 context must be tested by the caller. */
185 bidi_mirror_char (int c
)
191 if (c
< 0 || c
> MAX_CHAR
)
194 val
= CHAR_TABLE_REF (bidi_mirror_table
, c
);
199 if (v
< 0 || v
> MAX_CHAR
)
208 /* Determine the start-of-run (sor) directional type given the two
209 embedding levels on either side of the run boundary. Also, update
210 the saved info about previously seen characters, since that info is
211 generally valid for a single level run. */
213 bidi_set_sor_type (struct bidi_it
*bidi_it
, int level_before
, int level_after
)
215 int higher_level
= level_before
> level_after
? level_before
: level_after
;
217 /* The prev_was_pdf gork is required for when we have several PDFs
218 in a row. In that case, we want to compute the sor type for the
219 next level run only once: when we see the first PDF. That's
220 because the sor type depends only on the higher of the two levels
221 that we find on the two sides of the level boundary (see UAX#9,
222 clause X10), and so we don't need to know the final embedding
223 level to which we descend after processing all the PDFs. */
224 if (!bidi_it
->prev_was_pdf
|| level_before
< level_after
)
225 /* FIXME: should the default sor direction be user selectable? */
226 bidi_it
->sor
= (higher_level
& 1) != 0 ? R2L
: L2R
;
227 if (level_before
> level_after
)
228 bidi_it
->prev_was_pdf
= 1;
230 bidi_it
->prev
.type
= UNKNOWN_BT
;
231 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
232 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
233 bidi_it
->prev_for_neutral
.type
= bidi_it
->sor
== R2L
? STRONG_R
: STRONG_L
;
234 bidi_it
->prev_for_neutral
.charpos
= bidi_it
->charpos
;
235 bidi_it
->prev_for_neutral
.bytepos
= bidi_it
->bytepos
;
236 bidi_it
->next_for_neutral
.type
= bidi_it
->next_for_neutral
.type_after_w1
=
237 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
238 bidi_it
->ignore_bn_limit
= -1; /* meaning it's unknown */
241 /* Push the current embedding level and override status; reset the
242 current level to LEVEL and the current override status to OVERRIDE. */
244 bidi_push_embedding_level (struct bidi_it
*bidi_it
,
245 int level
, bidi_dir_t override
)
247 bidi_it
->stack_idx
++;
248 xassert (bidi_it
->stack_idx
< BIDI_MAXLEVEL
);
249 bidi_it
->level_stack
[bidi_it
->stack_idx
].level
= level
;
250 bidi_it
->level_stack
[bidi_it
->stack_idx
].override
= override
;
253 /* Pop the embedding level and directional override status from the
254 stack, and return the new level. */
256 bidi_pop_embedding_level (struct bidi_it
*bidi_it
)
258 /* UAX#9 says to ignore invalid PDFs. */
259 if (bidi_it
->stack_idx
> 0)
260 bidi_it
->stack_idx
--;
261 return bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
264 /* Record in SAVED_INFO the information about the current character. */
266 bidi_remember_char (struct bidi_saved_info
*saved_info
,
267 struct bidi_it
*bidi_it
)
269 saved_info
->charpos
= bidi_it
->charpos
;
270 saved_info
->bytepos
= bidi_it
->bytepos
;
271 saved_info
->type
= bidi_it
->type
;
272 bidi_check_type (bidi_it
->type
);
273 saved_info
->type_after_w1
= bidi_it
->type_after_w1
;
274 bidi_check_type (bidi_it
->type_after_w1
);
275 saved_info
->orig_type
= bidi_it
->orig_type
;
276 bidi_check_type (bidi_it
->orig_type
);
279 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
280 copies the part of the level stack that is actually in use. */
282 bidi_copy_it (struct bidi_it
*to
, struct bidi_it
*from
)
286 /* Copy everything except the level stack and beyond. */
287 memcpy (to
, from
, offsetof (struct bidi_it
, level_stack
[0]));
289 /* Copy the active part of the level stack. */
290 to
->level_stack
[0] = from
->level_stack
[0]; /* level zero is always in use */
291 for (i
= 1; i
<= from
->stack_idx
; i
++)
292 to
->level_stack
[i
] = from
->level_stack
[i
];
296 /***********************************************************************
297 Caching the bidi iterator states
298 ***********************************************************************/
300 #define BIDI_CACHE_CHUNK 200
301 static struct bidi_it
*bidi_cache
;
302 static ptrdiff_t bidi_cache_size
= 0;
303 enum { elsz
= sizeof (struct bidi_it
) };
304 static ptrdiff_t bidi_cache_idx
; /* next unused cache slot */
305 static ptrdiff_t bidi_cache_last_idx
; /* slot of last cache hit */
306 static ptrdiff_t bidi_cache_start
= 0; /* start of cache for this
309 /* 5-slot stack for saving the start of the previous level of the
310 cache. xdisp.c maintains a 5-slot stack for its iterator state,
311 and we need the same size of our stack. */
312 static ptrdiff_t bidi_cache_start_stack
[IT_STACK_SIZE
];
313 static int bidi_cache_sp
;
315 /* Size of header used by bidi_shelve_cache. */
318 bidi_shelve_header_size
=
319 (sizeof (bidi_cache_idx
) + sizeof (bidi_cache_start_stack
)
320 + sizeof (bidi_cache_sp
) + sizeof (bidi_cache_start
)
321 + sizeof (bidi_cache_last_idx
))
324 /* Reset the cache state to the empty state. We only reset the part
325 of the cache relevant to iteration of the current object. Previous
326 objects, which are pushed on the display iterator's stack, are left
327 intact. This is called when the cached information is no more
328 useful for the current iteration, e.g. when we were reseated to a
329 new position on the same object. */
331 bidi_cache_reset (void)
333 bidi_cache_idx
= bidi_cache_start
;
334 bidi_cache_last_idx
= -1;
337 /* Shrink the cache to its minimal size. Called when we init the bidi
338 iterator for reordering a buffer or a string that does not come
339 from display properties, because that means all the previously
340 cached info is of no further use. */
342 bidi_cache_shrink (void)
344 if (bidi_cache_size
> BIDI_CACHE_CHUNK
)
346 bidi_cache_size
= BIDI_CACHE_CHUNK
;
348 (struct bidi_it
*) xrealloc (bidi_cache
, bidi_cache_size
* elsz
);
354 bidi_cache_fetch_state (ptrdiff_t idx
, struct bidi_it
*bidi_it
)
356 int current_scan_dir
= bidi_it
->scan_dir
;
358 if (idx
< bidi_cache_start
|| idx
>= bidi_cache_idx
)
361 bidi_copy_it (bidi_it
, &bidi_cache
[idx
]);
362 bidi_it
->scan_dir
= current_scan_dir
;
363 bidi_cache_last_idx
= idx
;
366 /* Find a cached state with a given CHARPOS and resolved embedding
367 level less or equal to LEVEL. if LEVEL is -1, disregard the
368 resolved levels in cached states. DIR, if non-zero, means search
369 in that direction from the last cache hit. */
370 static inline ptrdiff_t
371 bidi_cache_search (EMACS_INT charpos
, int level
, int dir
)
373 ptrdiff_t i
, i_start
;
375 if (bidi_cache_idx
> bidi_cache_start
)
377 if (bidi_cache_last_idx
== -1)
378 bidi_cache_last_idx
= bidi_cache_idx
- 1;
379 if (charpos
< bidi_cache
[bidi_cache_last_idx
].charpos
)
382 i_start
= bidi_cache_last_idx
- 1;
384 else if (charpos
> (bidi_cache
[bidi_cache_last_idx
].charpos
385 + bidi_cache
[bidi_cache_last_idx
].nchars
- 1))
388 i_start
= bidi_cache_last_idx
+ 1;
391 i_start
= bidi_cache_last_idx
;
395 i_start
= bidi_cache_idx
- 1;
400 /* Linear search for now; FIXME! */
401 for (i
= i_start
; i
>= bidi_cache_start
; i
--)
402 if (bidi_cache
[i
].charpos
<= charpos
403 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
404 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
409 for (i
= i_start
; i
< bidi_cache_idx
; i
++)
410 if (bidi_cache
[i
].charpos
<= charpos
411 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
412 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
420 /* Find a cached state where the resolved level changes to a value
421 that is lower than LEVEL, and return its cache slot index. DIR is
422 the direction to search, starting with the last used cache slot.
423 If DIR is zero, we search backwards from the last occupied cache
424 slot. BEFORE, if non-zero, means return the index of the slot that
425 is ``before'' the level change in the search direction. That is,
426 given the cached levels like this:
431 and assuming we are at the position cached at the slot marked with
432 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
433 index of slot B or A, depending whether BEFORE is, respectively,
436 bidi_cache_find_level_change (int level
, int dir
, int before
)
440 ptrdiff_t i
= dir
? bidi_cache_last_idx
: bidi_cache_idx
- 1;
441 int incr
= before
? 1 : 0;
443 xassert (!dir
|| bidi_cache_last_idx
>= 0);
452 while (i
>= bidi_cache_start
+ incr
)
454 if (bidi_cache
[i
- incr
].resolved_level
>= 0
455 && bidi_cache
[i
- incr
].resolved_level
< level
)
462 while (i
< bidi_cache_idx
- incr
)
464 if (bidi_cache
[i
+ incr
].resolved_level
>= 0
465 && bidi_cache
[i
+ incr
].resolved_level
< level
)
476 bidi_cache_ensure_space (ptrdiff_t idx
)
478 /* Enlarge the cache as needed. */
479 if (idx
>= bidi_cache_size
)
481 /* The bidi cache cannot be larger than the largest Lisp string
483 ptrdiff_t string_or_buffer_bound
=
484 max (BUF_BYTES_MAX
, STRING_BYTES_BOUND
);
486 /* Also, it cannot be larger than what C can represent. */
488 (min (PTRDIFF_MAX
, SIZE_MAX
) - bidi_shelve_header_size
) / elsz
;
491 xpalloc (bidi_cache
, &bidi_cache_size
,
492 max (BIDI_CACHE_CHUNK
, idx
- bidi_cache_size
+ 1),
493 min (string_or_buffer_bound
, c_bound
), elsz
);
498 bidi_cache_iterator_state (struct bidi_it
*bidi_it
, int resolved
)
502 /* We should never cache on backward scans. */
503 if (bidi_it
->scan_dir
== -1)
505 idx
= bidi_cache_search (bidi_it
->charpos
, -1, 1);
509 idx
= bidi_cache_idx
;
510 bidi_cache_ensure_space (idx
);
511 /* Character positions should correspond to cache positions 1:1.
512 If we are outside the range of cached positions, the cache is
513 useless and must be reset. */
514 if (idx
> bidi_cache_start
&&
515 (bidi_it
->charpos
> (bidi_cache
[idx
- 1].charpos
516 + bidi_cache
[idx
- 1].nchars
)
517 || bidi_it
->charpos
< bidi_cache
[bidi_cache_start
].charpos
))
520 idx
= bidi_cache_start
;
522 if (bidi_it
->nchars
<= 0)
524 bidi_copy_it (&bidi_cache
[idx
], bidi_it
);
526 bidi_cache
[idx
].resolved_level
= -1;
530 /* Copy only the members which could have changed, to avoid
531 costly copying of the entire struct. */
532 bidi_cache
[idx
].type
= bidi_it
->type
;
533 bidi_check_type (bidi_it
->type
);
534 bidi_cache
[idx
].type_after_w1
= bidi_it
->type_after_w1
;
535 bidi_check_type (bidi_it
->type_after_w1
);
537 bidi_cache
[idx
].resolved_level
= bidi_it
->resolved_level
;
539 bidi_cache
[idx
].resolved_level
= -1;
540 bidi_cache
[idx
].invalid_levels
= bidi_it
->invalid_levels
;
541 bidi_cache
[idx
].invalid_rl_levels
= bidi_it
->invalid_rl_levels
;
542 bidi_cache
[idx
].next_for_neutral
= bidi_it
->next_for_neutral
;
543 bidi_cache
[idx
].next_for_ws
= bidi_it
->next_for_ws
;
544 bidi_cache
[idx
].ignore_bn_limit
= bidi_it
->ignore_bn_limit
;
547 bidi_cache_last_idx
= idx
;
548 if (idx
>= bidi_cache_idx
)
549 bidi_cache_idx
= idx
+ 1;
552 static inline bidi_type_t
553 bidi_cache_find (EMACS_INT charpos
, int level
, struct bidi_it
*bidi_it
)
555 ptrdiff_t i
= bidi_cache_search (charpos
, level
, bidi_it
->scan_dir
);
557 if (i
>= bidi_cache_start
)
559 bidi_dir_t current_scan_dir
= bidi_it
->scan_dir
;
561 bidi_copy_it (bidi_it
, &bidi_cache
[i
]);
562 bidi_cache_last_idx
= i
;
563 /* Don't let scan direction from from the cached state override
564 the current scan direction. */
565 bidi_it
->scan_dir
= current_scan_dir
;
566 return bidi_it
->type
;
573 bidi_peek_at_next_level (struct bidi_it
*bidi_it
)
575 if (bidi_cache_idx
== bidi_cache_start
|| bidi_cache_last_idx
== -1)
577 return bidi_cache
[bidi_cache_last_idx
+ bidi_it
->scan_dir
].resolved_level
;
581 /***********************************************************************
582 Pushing and popping the bidi iterator state
583 ***********************************************************************/
585 /* Push the bidi iterator state in preparation for reordering a
586 different object, e.g. display string found at certain buffer
587 position. Pushing the bidi iterator boils down to saving its
588 entire state on the cache and starting a new cache "stacked" on top
589 of the current cache. */
591 bidi_push_it (struct bidi_it
*bidi_it
)
593 /* Save the current iterator state in its entirety after the last
595 bidi_cache_ensure_space (bidi_cache_idx
);
596 memcpy (&bidi_cache
[bidi_cache_idx
++], bidi_it
, sizeof (struct bidi_it
));
598 /* Push the current cache start onto the stack. */
599 xassert (bidi_cache_sp
< IT_STACK_SIZE
);
600 bidi_cache_start_stack
[bidi_cache_sp
++] = bidi_cache_start
;
602 /* Start a new level of cache, and make it empty. */
603 bidi_cache_start
= bidi_cache_idx
;
604 bidi_cache_last_idx
= -1;
607 /* Restore the iterator state saved by bidi_push_it and return the
608 cache to the corresponding state. */
610 bidi_pop_it (struct bidi_it
*bidi_it
)
612 if (bidi_cache_start
<= 0)
615 /* Reset the next free cache slot index to what it was before the
616 call to bidi_push_it. */
617 bidi_cache_idx
= bidi_cache_start
- 1;
619 /* Restore the bidi iterator state saved in the cache. */
620 memcpy (bidi_it
, &bidi_cache
[bidi_cache_idx
], sizeof (struct bidi_it
));
622 /* Pop the previous cache start from the stack. */
623 if (bidi_cache_sp
<= 0)
625 bidi_cache_start
= bidi_cache_start_stack
[--bidi_cache_sp
];
627 /* Invalidate the last-used cache slot data. */
628 bidi_cache_last_idx
= -1;
631 static ptrdiff_t bidi_cache_total_alloc
;
633 /* Stash away a copy of the cache and its control variables. */
635 bidi_shelve_cache (void)
637 unsigned char *databuf
;
641 if (bidi_cache_idx
== 0)
644 alloc
= (bidi_shelve_header_size
645 + bidi_cache_idx
* sizeof (struct bidi_it
));
646 databuf
= xmalloc (alloc
);
647 bidi_cache_total_alloc
+= alloc
;
649 memcpy (databuf
, &bidi_cache_idx
, sizeof (bidi_cache_idx
));
650 memcpy (databuf
+ sizeof (bidi_cache_idx
),
651 bidi_cache
, bidi_cache_idx
* sizeof (struct bidi_it
));
652 memcpy (databuf
+ sizeof (bidi_cache_idx
)
653 + bidi_cache_idx
* sizeof (struct bidi_it
),
654 bidi_cache_start_stack
, sizeof (bidi_cache_start_stack
));
655 memcpy (databuf
+ sizeof (bidi_cache_idx
)
656 + bidi_cache_idx
* sizeof (struct bidi_it
)
657 + sizeof (bidi_cache_start_stack
),
658 &bidi_cache_sp
, sizeof (bidi_cache_sp
));
659 memcpy (databuf
+ sizeof (bidi_cache_idx
)
660 + bidi_cache_idx
* sizeof (struct bidi_it
)
661 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
662 &bidi_cache_start
, sizeof (bidi_cache_start
));
663 memcpy (databuf
+ sizeof (bidi_cache_idx
)
664 + bidi_cache_idx
* sizeof (struct bidi_it
)
665 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
666 + sizeof (bidi_cache_start
),
667 &bidi_cache_last_idx
, sizeof (bidi_cache_last_idx
));
672 /* Restore the cache state from a copy stashed away by bidi_shelve_cache. */
674 bidi_unshelve_cache (void *databuf
, int just_free
)
676 unsigned char *p
= databuf
;
680 /* A NULL pointer means an empty cache. */
681 bidi_cache_start
= 0;
691 memcpy (&idx
, p
, sizeof (bidi_cache_idx
));
692 bidi_cache_total_alloc
-=
693 bidi_shelve_header_size
+ idx
* sizeof (struct bidi_it
);
697 memcpy (&bidi_cache_idx
, p
, sizeof (bidi_cache_idx
));
698 bidi_cache_ensure_space (bidi_cache_idx
);
699 memcpy (bidi_cache
, p
+ sizeof (bidi_cache_idx
),
700 bidi_cache_idx
* sizeof (struct bidi_it
));
701 memcpy (bidi_cache_start_stack
,
702 p
+ sizeof (bidi_cache_idx
)
703 + bidi_cache_idx
* sizeof (struct bidi_it
),
704 sizeof (bidi_cache_start_stack
));
705 memcpy (&bidi_cache_sp
,
706 p
+ sizeof (bidi_cache_idx
)
707 + bidi_cache_idx
* sizeof (struct bidi_it
)
708 + sizeof (bidi_cache_start_stack
),
709 sizeof (bidi_cache_sp
));
710 memcpy (&bidi_cache_start
,
711 p
+ sizeof (bidi_cache_idx
)
712 + bidi_cache_idx
* sizeof (struct bidi_it
)
713 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
714 sizeof (bidi_cache_start
));
715 memcpy (&bidi_cache_last_idx
,
716 p
+ sizeof (bidi_cache_idx
)
717 + bidi_cache_idx
* sizeof (struct bidi_it
)
718 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
719 + sizeof (bidi_cache_start
),
720 sizeof (bidi_cache_last_idx
));
721 bidi_cache_total_alloc
-=
722 bidi_shelve_header_size
+ bidi_cache_idx
* sizeof (struct bidi_it
);
730 /***********************************************************************
732 ***********************************************************************/
734 bidi_initialize (void)
737 #include "biditype.h"
738 #include "bidimirror.h"
742 bidi_type_table
= Fmake_char_table (Qnil
, make_number (STRONG_L
));
743 staticpro (&bidi_type_table
);
745 for (i
= 0; i
< sizeof bidi_type
/ sizeof bidi_type
[0]; i
++)
746 char_table_set_range (bidi_type_table
, bidi_type
[i
].from
, bidi_type
[i
].to
,
747 make_number (bidi_type
[i
].type
));
749 bidi_mirror_table
= Fmake_char_table (Qnil
, Qnil
);
750 staticpro (&bidi_mirror_table
);
752 for (i
= 0; i
< sizeof bidi_mirror
/ sizeof bidi_mirror
[0]; i
++)
753 char_table_set (bidi_mirror_table
, bidi_mirror
[i
].from
,
754 make_number (bidi_mirror
[i
].to
));
756 Qparagraph_start
= intern ("paragraph-start");
757 staticpro (&Qparagraph_start
);
758 paragraph_start_re
= Fsymbol_value (Qparagraph_start
);
759 if (!STRINGP (paragraph_start_re
))
760 paragraph_start_re
= build_string ("\f\\|[ \t]*$");
761 staticpro (¶graph_start_re
);
762 Qparagraph_separate
= intern ("paragraph-separate");
763 staticpro (&Qparagraph_separate
);
764 paragraph_separate_re
= Fsymbol_value (Qparagraph_separate
);
765 if (!STRINGP (paragraph_separate_re
))
766 paragraph_separate_re
= build_string ("[ \t\f]*$");
767 staticpro (¶graph_separate_re
);
770 bidi_cache_total_alloc
= 0;
772 bidi_initialized
= 1;
775 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
778 bidi_set_paragraph_end (struct bidi_it
*bidi_it
)
780 bidi_it
->invalid_levels
= 0;
781 bidi_it
->invalid_rl_levels
= -1;
782 bidi_it
->stack_idx
= 0;
783 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
786 /* Initialize the bidi iterator from buffer/string position CHARPOS. */
788 bidi_init_it (EMACS_INT charpos
, EMACS_INT bytepos
, int frame_window_p
,
789 struct bidi_it
*bidi_it
)
791 if (! bidi_initialized
)
794 bidi_it
->charpos
= charpos
;
796 bidi_it
->bytepos
= bytepos
;
797 bidi_it
->frame_window_p
= frame_window_p
;
798 bidi_it
->nchars
= -1; /* to be computed in bidi_resolve_explicit_1 */
799 bidi_it
->first_elt
= 1;
800 bidi_set_paragraph_end (bidi_it
);
801 bidi_it
->new_paragraph
= 1;
802 bidi_it
->separator_limit
= -1;
803 bidi_it
->type
= NEUTRAL_B
;
804 bidi_it
->type_after_w1
= NEUTRAL_B
;
805 bidi_it
->orig_type
= NEUTRAL_B
;
806 bidi_it
->prev_was_pdf
= 0;
807 bidi_it
->prev
.type
= bidi_it
->prev
.type_after_w1
=
808 bidi_it
->prev
.orig_type
= UNKNOWN_BT
;
809 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
810 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
811 bidi_it
->next_for_neutral
.charpos
= -1;
812 bidi_it
->next_for_neutral
.type
=
813 bidi_it
->next_for_neutral
.type_after_w1
=
814 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
815 bidi_it
->prev_for_neutral
.charpos
= -1;
816 bidi_it
->prev_for_neutral
.type
=
817 bidi_it
->prev_for_neutral
.type_after_w1
=
818 bidi_it
->prev_for_neutral
.orig_type
= UNKNOWN_BT
;
819 bidi_it
->sor
= L2R
; /* FIXME: should it be user-selectable? */
820 bidi_it
->disp_pos
= -1; /* invalid/unknown */
821 bidi_it
->disp_prop_p
= 0;
822 /* We can only shrink the cache if we are at the bottom level of its
824 if (bidi_cache_start
== 0)
825 bidi_cache_shrink ();
830 /* Perform initializations for reordering a new line of bidi text. */
832 bidi_line_init (struct bidi_it
*bidi_it
)
834 bidi_it
->scan_dir
= 1; /* FIXME: do we need to have control on this? */
835 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
836 bidi_it
->level_stack
[0].override
= NEUTRAL_DIR
; /* X1 */
837 bidi_it
->invalid_levels
= 0;
838 bidi_it
->invalid_rl_levels
= -1;
839 bidi_it
->next_en_pos
= -1;
840 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
841 bidi_set_sor_type (bidi_it
,
842 bidi_it
->paragraph_dir
== R2L
? 1 : 0,
843 bidi_it
->level_stack
[0].level
); /* X10 */
849 /***********************************************************************
851 ***********************************************************************/
853 /* Count bytes in string S between BEG/BEGBYTE and END. BEG and END
854 are zero-based character positions in S, BEGBYTE is byte position
855 corresponding to BEG. UNIBYTE, if non-zero, means S is a unibyte
857 static inline EMACS_INT
858 bidi_count_bytes (const unsigned char *s
, const EMACS_INT beg
,
859 const EMACS_INT begbyte
, const EMACS_INT end
, int unibyte
)
862 const unsigned char *p
= s
+ begbyte
, *start
= p
;
868 if (!CHAR_HEAD_P (*p
))
873 p
+= BYTES_BY_CHAR_HEAD (*p
);
881 /* Fetch and returns the character at byte position BYTEPOS. If S is
882 non-NULL, fetch the character from string S; otherwise fetch the
883 character from the current buffer. UNIBYTE non-zero means S is a
886 bidi_char_at_pos (EMACS_INT bytepos
, const unsigned char *s
, int unibyte
)
893 return STRING_CHAR (s
+ bytepos
);
896 return FETCH_MULTIBYTE_CHAR (bytepos
);
899 /* Fetch and return the character at BYTEPOS/CHARPOS. If that
900 character is covered by a display string, treat the entire run of
901 covered characters as a single character u+FFFC, and return their
902 combined length in CH_LEN and NCHARS. DISP_POS specifies the
903 character position of the next display string, or -1 if not yet
904 computed. DISP_PROP_P non-zero means that there's really a display
905 string at DISP_POS, as opposed to when we searched till DISP_POS
906 without findingone. When the next character is at or beyond that
907 position, the function updates DISP_POS with the position of the
908 next display string. STRING->s is the C string to iterate, or NULL
909 if iterating over a buffer or a Lisp string; in the latter case,
910 STRING->lstring is the Lisp string. */
912 bidi_fetch_char (EMACS_INT bytepos
, EMACS_INT charpos
, EMACS_INT
*disp_pos
,
913 int *disp_prop_p
, struct bidi_string_data
*string
,
914 int frame_window_p
, EMACS_INT
*ch_len
, EMACS_INT
*nchars
)
918 (string
->s
|| STRINGP (string
->lstring
)) ? string
->schars
: ZV
;
921 /* If we got past the last known position of display string, compute
922 the position of the next one. That position could be at CHARPOS. */
923 if (charpos
< endpos
&& charpos
> *disp_pos
)
925 SET_TEXT_POS (pos
, charpos
, bytepos
);
926 *disp_pos
= compute_display_string_pos (&pos
, string
, frame_window_p
,
930 /* Fetch the character at BYTEPOS. */
931 if (charpos
>= endpos
)
939 else if (charpos
>= *disp_pos
&& *disp_prop_p
)
941 EMACS_INT disp_end_pos
;
943 /* We don't expect to find ourselves in the middle of a display
944 property. Hopefully, it will never be needed. */
945 if (charpos
> *disp_pos
)
947 /* Return the Unicode Object Replacement Character to represent
948 the entire run of characters covered by the display string. */
950 disp_end_pos
= compute_display_string_end (*disp_pos
, string
);
951 *nchars
= disp_end_pos
- *disp_pos
;
955 *ch_len
= bidi_count_bytes (string
->s
, *disp_pos
, bytepos
,
956 disp_end_pos
, string
->unibyte
);
957 else if (STRINGP (string
->lstring
))
958 *ch_len
= bidi_count_bytes (SDATA (string
->lstring
), *disp_pos
,
959 bytepos
, disp_end_pos
, string
->unibyte
);
961 *ch_len
= CHAR_TO_BYTE (disp_end_pos
) - bytepos
;
969 if (!string
->unibyte
)
971 ch
= STRING_CHAR_AND_LENGTH (string
->s
+ bytepos
, len
);
976 ch
= UNIBYTE_TO_CHAR (string
->s
[bytepos
]);
980 else if (STRINGP (string
->lstring
))
984 if (!string
->unibyte
)
986 ch
= STRING_CHAR_AND_LENGTH (SDATA (string
->lstring
) + bytepos
,
992 ch
= UNIBYTE_TO_CHAR (SREF (string
->lstring
, bytepos
));
998 ch
= FETCH_MULTIBYTE_CHAR (bytepos
);
999 *ch_len
= CHAR_BYTES (ch
);
1004 /* If we just entered a run of characters covered by a display
1005 string, compute the position of the next display string. */
1006 if (charpos
+ *nchars
<= endpos
&& charpos
+ *nchars
> *disp_pos
1009 SET_TEXT_POS (pos
, charpos
+ *nchars
, bytepos
+ *ch_len
);
1010 *disp_pos
= compute_display_string_pos (&pos
, string
, frame_window_p
,
1018 /***********************************************************************
1019 Determining paragraph direction
1020 ***********************************************************************/
1022 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
1023 Value is the non-negative length of the paragraph separator
1024 following the buffer position, -1 if position is at the beginning
1025 of a new paragraph, or -2 if position is neither at beginning nor
1026 at end of a paragraph. */
1028 bidi_at_paragraph_end (EMACS_INT charpos
, EMACS_INT bytepos
)
1031 Lisp_Object start_re
;
1034 sep_re
= paragraph_separate_re
;
1035 start_re
= paragraph_start_re
;
1037 val
= fast_looking_at (sep_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
);
1040 if (fast_looking_at (start_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
) >= 0)
1049 /* Find the beginning of this paragraph by looking back in the buffer.
1050 Value is the byte position of the paragraph's beginning. */
1052 bidi_find_paragraph_start (EMACS_INT pos
, EMACS_INT pos_byte
)
1054 Lisp_Object re
= paragraph_start_re
;
1055 EMACS_INT limit
= ZV
, limit_byte
= ZV_BYTE
;
1057 while (pos_byte
> BEGV_BYTE
1058 && fast_looking_at (re
, pos
, pos_byte
, limit
, limit_byte
, Qnil
) < 0)
1060 /* FIXME: What if the paragraph beginning is covered by a
1061 display string? And what if a display string covering some
1062 of the text over which we scan back includes
1063 paragraph_start_re? */
1064 pos
= find_next_newline_no_quit (pos
- 1, -1);
1065 pos_byte
= CHAR_TO_BYTE (pos
);
1070 /* Determine the base direction, a.k.a. base embedding level, of the
1071 paragraph we are about to iterate through. If DIR is either L2R or
1072 R2L, just use that. Otherwise, determine the paragraph direction
1073 from the first strong directional character of the paragraph.
1075 NO_DEFAULT_P non-zero means don't default to L2R if the paragraph
1076 has no strong directional characters and both DIR and
1077 bidi_it->paragraph_dir are NEUTRAL_DIR. In that case, search back
1078 in the buffer until a paragraph is found with a strong character,
1079 or until hitting BEGV. In the latter case, fall back to L2R. This
1080 flag is used in current-bidi-paragraph-direction.
1082 Note that this function gives the paragraph separator the same
1083 direction as the preceding paragraph, even though Emacs generally
1084 views the separartor as not belonging to any paragraph. */
1086 bidi_paragraph_init (bidi_dir_t dir
, struct bidi_it
*bidi_it
, int no_default_p
)
1088 EMACS_INT bytepos
= bidi_it
->bytepos
;
1089 int string_p
= bidi_it
->string
.s
!= NULL
|| STRINGP (bidi_it
->string
.lstring
);
1090 EMACS_INT pstartbyte
;
1091 /* Note that begbyte is a byte position, while end is a character
1092 position. Yes, this is ugly, but we are trying to avoid costly
1093 calls to BYTE_TO_CHAR and its ilk. */
1094 EMACS_INT begbyte
= string_p
? 0 : BEGV_BYTE
;
1095 EMACS_INT end
= string_p
? bidi_it
->string
.schars
: ZV
;
1097 /* Special case for an empty buffer. */
1098 if (bytepos
== begbyte
&& bidi_it
->charpos
== end
)
1100 /* We should never be called at EOB or before BEGV. */
1101 else if (bidi_it
->charpos
>= end
|| bytepos
< begbyte
)
1106 bidi_it
->paragraph_dir
= L2R
;
1107 bidi_it
->new_paragraph
= 0;
1109 else if (dir
== R2L
)
1111 bidi_it
->paragraph_dir
= R2L
;
1112 bidi_it
->new_paragraph
= 0;
1114 else if (dir
== NEUTRAL_DIR
) /* P2 */
1117 EMACS_INT ch_len
, nchars
;
1118 EMACS_INT pos
, disp_pos
= -1;
1119 int disp_prop_p
= 0;
1121 const unsigned char *s
;
1123 if (!bidi_initialized
)
1126 /* If we are inside a paragraph separator, we are just waiting
1127 for the separator to be exhausted; use the previous paragraph
1128 direction. But don't do that if we have been just reseated,
1129 because we need to reinitialize below in that case. */
1130 if (!bidi_it
->first_elt
1131 && bidi_it
->charpos
< bidi_it
->separator_limit
)
1134 /* If we are on a newline, get past it to where the next
1135 paragraph might start. But don't do that at BEGV since then
1136 we are potentially in a new paragraph that doesn't yet
1138 pos
= bidi_it
->charpos
;
1139 s
= STRINGP (bidi_it
->string
.lstring
) ?
1140 SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1141 if (bytepos
> begbyte
1142 && bidi_char_at_pos (bytepos
, s
, bidi_it
->string
.unibyte
) == '\n')
1148 /* We are either at the beginning of a paragraph or in the
1149 middle of it. Find where this paragraph starts. */
1152 /* We don't support changes of paragraph direction inside a
1153 string. It is treated as a single paragraph. */
1157 pstartbyte
= bidi_find_paragraph_start (pos
, bytepos
);
1158 bidi_it
->separator_limit
= -1;
1159 bidi_it
->new_paragraph
= 0;
1161 /* The following loop is run more than once only if NO_DEFAULT_P
1162 is non-zero, and only if we are iterating on a buffer. */
1164 bytepos
= pstartbyte
;
1166 pos
= BYTE_TO_CHAR (bytepos
);
1167 ch
= bidi_fetch_char (bytepos
, pos
, &disp_pos
, &disp_prop_p
,
1169 bidi_it
->frame_window_p
, &ch_len
, &nchars
);
1170 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
1172 for (pos
+= nchars
, bytepos
+= ch_len
;
1173 /* NOTE: UAX#9 says to search only for L, AL, or R types
1174 of characters, and ignore RLE, RLO, LRE, and LRO.
1175 However, I'm not sure it makes sense to omit those 4;
1176 should try with and without that to see the effect. */
1177 (bidi_get_category (type
) != STRONG
)
1178 || (bidi_ignore_explicit_marks_for_paragraph_level
1179 && (type
== RLE
|| type
== RLO
1180 || type
== LRE
|| type
== LRO
));
1181 type
= bidi_get_type (ch
, NEUTRAL_DIR
))
1185 /* Pretend there's a paragraph separator at end of
1191 && type
== NEUTRAL_B
1192 && bidi_at_paragraph_end (pos
, bytepos
) >= -1)
1194 /* Fetch next character and advance to get past it. */
1195 ch
= bidi_fetch_char (bytepos
, pos
, &disp_pos
,
1196 &disp_prop_p
, &bidi_it
->string
,
1197 bidi_it
->frame_window_p
, &ch_len
, &nchars
);
1201 if (type
== STRONG_R
|| type
== STRONG_AL
) /* P3 */
1202 bidi_it
->paragraph_dir
= R2L
;
1203 else if (type
== STRONG_L
)
1204 bidi_it
->paragraph_dir
= L2R
;
1206 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
)
1208 /* If this paragraph is at BEGV, default to L2R. */
1209 if (pstartbyte
== BEGV_BYTE
)
1210 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 */
1213 EMACS_INT prevpbyte
= pstartbyte
;
1214 EMACS_INT p
= BYTE_TO_CHAR (pstartbyte
), pbyte
= pstartbyte
;
1216 /* Find the beginning of the previous paragraph, if any. */
1217 while (pbyte
> BEGV_BYTE
&& prevpbyte
>= pstartbyte
)
1219 /* FXIME: What if p is covered by a display
1220 string? See also a FIXME inside
1221 bidi_find_paragraph_start. */
1223 pbyte
= CHAR_TO_BYTE (p
);
1224 prevpbyte
= bidi_find_paragraph_start (p
, pbyte
);
1226 pstartbyte
= prevpbyte
;
1230 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
);
1235 /* Contrary to UAX#9 clause P3, we only default the paragraph
1236 direction to L2R if we have no previous usable paragraph
1237 direction. This is allowed by the HL1 clause. */
1238 if (bidi_it
->paragraph_dir
!= L2R
&& bidi_it
->paragraph_dir
!= R2L
)
1239 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 ``higher-level protocols'' */
1240 if (bidi_it
->paragraph_dir
== R2L
)
1241 bidi_it
->level_stack
[0].level
= 1;
1243 bidi_it
->level_stack
[0].level
= 0;
1245 bidi_line_init (bidi_it
);
1249 /***********************************************************************
1250 Resolving explicit and implicit levels.
1251 The rest of this file constitutes the core of the UBA implementation.
1252 ***********************************************************************/
1255 bidi_explicit_dir_char (int ch
)
1257 bidi_type_t ch_type
;
1259 if (!bidi_initialized
)
1261 ch_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
1262 return (ch_type
== LRE
|| ch_type
== LRO
1263 || ch_type
== RLE
|| ch_type
== RLO
1267 /* A helper function for bidi_resolve_explicit. It advances to the
1268 next character in logical order and determines the new embedding
1269 level and directional override, but does not take into account
1270 empty embeddings. */
1272 bidi_resolve_explicit_1 (struct bidi_it
*bidi_it
)
1278 bidi_dir_t override
;
1279 int string_p
= bidi_it
->string
.s
!= NULL
|| STRINGP (bidi_it
->string
.lstring
);
1281 /* If reseat()'ed, don't advance, so as to start iteration from the
1282 position where we were reseated. bidi_it->bytepos can be less
1283 than BEGV_BYTE after reseat to BEGV. */
1284 if (bidi_it
->bytepos
< (string_p
? 0 : BEGV_BYTE
)
1285 || bidi_it
->first_elt
)
1287 bidi_it
->first_elt
= 0;
1290 const unsigned char *p
=
1291 STRINGP (bidi_it
->string
.lstring
)
1292 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1294 if (bidi_it
->charpos
< 0)
1295 bidi_it
->charpos
= 0;
1296 bidi_it
->bytepos
= bidi_count_bytes (p
, 0, 0, bidi_it
->charpos
,
1297 bidi_it
->string
.unibyte
);
1301 if (bidi_it
->charpos
< BEGV
)
1302 bidi_it
->charpos
= BEGV
;
1303 bidi_it
->bytepos
= CHAR_TO_BYTE (bidi_it
->charpos
);
1306 /* Don't move at end of buffer/string. */
1307 else if (bidi_it
->charpos
< (string_p
? bidi_it
->string
.schars
: ZV
))
1309 /* Advance to the next character, skipping characters covered by
1310 display strings (nchars > 1). */
1311 if (bidi_it
->nchars
<= 0)
1313 bidi_it
->charpos
+= bidi_it
->nchars
;
1314 if (bidi_it
->ch_len
== 0)
1316 bidi_it
->bytepos
+= bidi_it
->ch_len
;
1319 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
; /* X1 */
1320 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1321 new_level
= current_level
;
1323 if (bidi_it
->charpos
>= (string_p
? bidi_it
->string
.schars
: ZV
))
1326 bidi_it
->ch_len
= 1;
1327 bidi_it
->nchars
= 1;
1328 bidi_it
->disp_pos
= (string_p
? bidi_it
->string
.schars
: ZV
);
1329 bidi_it
->disp_prop_p
= 0;
1333 /* Fetch the character at BYTEPOS. If it is covered by a
1334 display string, treat the entire run of covered characters as
1335 a single character u+FFFC. */
1336 curchar
= bidi_fetch_char (bidi_it
->bytepos
, bidi_it
->charpos
,
1337 &bidi_it
->disp_pos
, &bidi_it
->disp_prop_p
,
1338 &bidi_it
->string
, bidi_it
->frame_window_p
,
1339 &bidi_it
->ch_len
, &bidi_it
->nchars
);
1341 bidi_it
->ch
= curchar
;
1343 /* Don't apply directional override here, as all the types we handle
1344 below will not be affected by the override anyway, and we need
1345 the original type unaltered. The override will be applied in
1346 bidi_resolve_weak. */
1347 type
= bidi_get_type (curchar
, NEUTRAL_DIR
);
1348 bidi_it
->orig_type
= type
;
1349 bidi_check_type (bidi_it
->orig_type
);
1352 bidi_it
->prev_was_pdf
= 0;
1354 bidi_it
->type_after_w1
= UNKNOWN_BT
;
1360 bidi_it
->type_after_w1
= type
;
1361 bidi_check_type (bidi_it
->type_after_w1
);
1362 type
= WEAK_BN
; /* X9/Retaining */
1363 if (bidi_it
->ignore_bn_limit
<= -1)
1365 if (current_level
<= BIDI_MAXLEVEL
- 4)
1367 /* Compute the least odd embedding level greater than
1368 the current level. */
1369 new_level
= ((current_level
+ 1) & ~1) + 1;
1370 if (bidi_it
->type_after_w1
== RLE
)
1371 override
= NEUTRAL_DIR
;
1374 if (current_level
== BIDI_MAXLEVEL
- 4)
1375 bidi_it
->invalid_rl_levels
= 0;
1376 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1380 bidi_it
->invalid_levels
++;
1381 /* See the commentary about invalid_rl_levels below. */
1382 if (bidi_it
->invalid_rl_levels
< 0)
1383 bidi_it
->invalid_rl_levels
= 0;
1384 bidi_it
->invalid_rl_levels
++;
1387 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1388 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1393 bidi_it
->type_after_w1
= type
;
1394 bidi_check_type (bidi_it
->type_after_w1
);
1395 type
= WEAK_BN
; /* X9/Retaining */
1396 if (bidi_it
->ignore_bn_limit
<= -1)
1398 if (current_level
<= BIDI_MAXLEVEL
- 5)
1400 /* Compute the least even embedding level greater than
1401 the current level. */
1402 new_level
= ((current_level
+ 2) & ~1);
1403 if (bidi_it
->type_after_w1
== LRE
)
1404 override
= NEUTRAL_DIR
;
1407 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1411 bidi_it
->invalid_levels
++;
1412 /* invalid_rl_levels counts invalid levels encountered
1413 while the embedding level was already too high for
1414 LRE/LRO, but not for RLE/RLO. That is because
1415 there may be exactly one PDF which we should not
1416 ignore even though invalid_levels is non-zero.
1417 invalid_rl_levels helps to know what PDF is
1419 if (bidi_it
->invalid_rl_levels
>= 0)
1420 bidi_it
->invalid_rl_levels
++;
1423 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1424 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1428 bidi_it
->type_after_w1
= type
;
1429 bidi_check_type (bidi_it
->type_after_w1
);
1430 type
= WEAK_BN
; /* X9/Retaining */
1431 if (bidi_it
->ignore_bn_limit
<= -1)
1433 if (!bidi_it
->invalid_rl_levels
)
1435 new_level
= bidi_pop_embedding_level (bidi_it
);
1436 bidi_it
->invalid_rl_levels
= -1;
1437 if (bidi_it
->invalid_levels
)
1438 bidi_it
->invalid_levels
--;
1439 /* else nothing: UAX#9 says to ignore invalid PDFs */
1441 if (!bidi_it
->invalid_levels
)
1442 new_level
= bidi_pop_embedding_level (bidi_it
);
1445 bidi_it
->invalid_levels
--;
1446 bidi_it
->invalid_rl_levels
--;
1449 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1450 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1458 bidi_it
->type
= type
;
1459 bidi_check_type (bidi_it
->type
);
1464 /* Given an iterator state in BIDI_IT, advance one character position
1465 in the buffer/string to the next character (in the logical order),
1466 resolve any explicit embeddings and directional overrides, and
1467 return the embedding level of the character after resolving
1468 explicit directives and ignoring empty embeddings. */
1470 bidi_resolve_explicit (struct bidi_it
*bidi_it
)
1472 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1473 int new_level
= bidi_resolve_explicit_1 (bidi_it
);
1474 EMACS_INT eob
= bidi_it
->string
.s
? bidi_it
->string
.schars
: ZV
;
1475 const unsigned char *s
= STRINGP (bidi_it
->string
.lstring
)
1476 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1478 if (prev_level
< new_level
1479 && bidi_it
->type
== WEAK_BN
1480 && bidi_it
->ignore_bn_limit
== -1 /* only if not already known */
1481 && bidi_it
->charpos
< eob
/* not already at EOB */
1482 && bidi_explicit_dir_char (bidi_char_at_pos (bidi_it
->bytepos
1483 + bidi_it
->ch_len
, s
,
1484 bidi_it
->string
.unibyte
)))
1486 /* Avoid pushing and popping embedding levels if the level run
1487 is empty, as this breaks level runs where it shouldn't.
1488 UAX#9 removes all the explicit embedding and override codes,
1489 so empty embeddings disappear without a trace. We need to
1490 behave as if we did the same. */
1491 struct bidi_it saved_it
;
1492 int level
= prev_level
;
1494 bidi_copy_it (&saved_it
, bidi_it
);
1496 while (bidi_explicit_dir_char (bidi_char_at_pos (bidi_it
->bytepos
1497 + bidi_it
->ch_len
, s
,
1498 bidi_it
->string
.unibyte
)))
1500 /* This advances to the next character, skipping any
1501 characters covered by display strings. */
1502 level
= bidi_resolve_explicit_1 (bidi_it
);
1503 /* If string.lstring was relocated inside bidi_resolve_explicit_1,
1504 a pointer to its data is no longer valid. */
1505 if (STRINGP (bidi_it
->string
.lstring
))
1506 s
= SDATA (bidi_it
->string
.lstring
);
1509 if (bidi_it
->nchars
<= 0)
1511 if (level
== prev_level
) /* empty embedding */
1512 saved_it
.ignore_bn_limit
= bidi_it
->charpos
+ bidi_it
->nchars
;
1513 else /* this embedding is non-empty */
1514 saved_it
.ignore_bn_limit
= -2;
1516 bidi_copy_it (bidi_it
, &saved_it
);
1517 if (bidi_it
->ignore_bn_limit
> -1)
1519 /* We pushed a level, but we shouldn't have. Undo that. */
1520 if (!bidi_it
->invalid_rl_levels
)
1522 new_level
= bidi_pop_embedding_level (bidi_it
);
1523 bidi_it
->invalid_rl_levels
= -1;
1524 if (bidi_it
->invalid_levels
)
1525 bidi_it
->invalid_levels
--;
1527 if (!bidi_it
->invalid_levels
)
1528 new_level
= bidi_pop_embedding_level (bidi_it
);
1531 bidi_it
->invalid_levels
--;
1532 bidi_it
->invalid_rl_levels
--;
1537 if (bidi_it
->type
== NEUTRAL_B
) /* X8 */
1539 bidi_set_paragraph_end (bidi_it
);
1540 /* This is needed by bidi_resolve_weak below, and in L1. */
1541 bidi_it
->type_after_w1
= bidi_it
->type
;
1542 bidi_check_type (bidi_it
->type_after_w1
);
1548 /* Advance in the buffer/string, resolve weak types and return the
1549 type of the next character after weak type resolution. */
1551 bidi_resolve_weak (struct bidi_it
*bidi_it
)
1554 bidi_dir_t override
;
1555 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1556 int new_level
= bidi_resolve_explicit (bidi_it
);
1558 bidi_type_t type_of_next
;
1559 struct bidi_it saved_it
;
1561 (STRINGP (bidi_it
->string
.lstring
) || bidi_it
->string
.s
)
1562 ? bidi_it
->string
.schars
: ZV
;
1564 type
= bidi_it
->type
;
1565 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1567 if (type
== UNKNOWN_BT
1575 if (new_level
!= prev_level
1576 || bidi_it
->type
== NEUTRAL_B
)
1578 /* We've got a new embedding level run, compute the directional
1579 type of sor and initialize per-run variables (UAX#9, clause
1581 bidi_set_sor_type (bidi_it
, prev_level
, new_level
);
1583 else if (type
== NEUTRAL_S
|| type
== NEUTRAL_WS
1584 || type
== WEAK_BN
|| type
== STRONG_AL
)
1585 bidi_it
->type_after_w1
= type
; /* needed in L1 */
1586 bidi_check_type (bidi_it
->type_after_w1
);
1588 /* Level and directional override status are already recorded in
1589 bidi_it, and do not need any change; see X6. */
1590 if (override
== R2L
) /* X6 */
1592 else if (override
== L2R
)
1596 if (type
== WEAK_NSM
) /* W1 */
1598 /* Note that we don't need to consider the case where the
1599 prev character has its type overridden by an RLO or LRO,
1600 because then either the type of this NSM would have been
1601 also overridden, or the previous character is outside the
1602 current level run, and thus not relevant to this NSM.
1603 This is why NSM gets the type_after_w1 of the previous
1605 if (bidi_it
->prev
.type_after_w1
!= UNKNOWN_BT
1606 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1607 && bidi_it
->prev
.type_after_w1
!= NEUTRAL_B
)
1608 type
= bidi_it
->prev
.type_after_w1
;
1609 else if (bidi_it
->sor
== R2L
)
1611 else if (bidi_it
->sor
== L2R
)
1613 else /* shouldn't happen! */
1616 if (type
== WEAK_EN
/* W2 */
1617 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1619 else if (type
== STRONG_AL
) /* W3 */
1621 else if ((type
== WEAK_ES
/* W4 */
1622 && bidi_it
->prev
.type_after_w1
== WEAK_EN
1623 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1625 && ((bidi_it
->prev
.type_after_w1
== WEAK_EN
1626 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1627 || bidi_it
->prev
.type_after_w1
== WEAK_AN
)))
1629 const unsigned char *s
=
1630 STRINGP (bidi_it
->string
.lstring
)
1631 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1634 bidi_it
->charpos
+ bidi_it
->nchars
>= eob
1636 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
, s
,
1637 bidi_it
->string
.unibyte
);
1638 type_of_next
= bidi_get_type (next_char
, override
);
1640 if (type_of_next
== WEAK_BN
1641 || bidi_explicit_dir_char (next_char
))
1643 bidi_copy_it (&saved_it
, bidi_it
);
1644 while (bidi_resolve_explicit (bidi_it
) == new_level
1645 && bidi_it
->type
== WEAK_BN
)
1647 type_of_next
= bidi_it
->type
;
1648 bidi_copy_it (bidi_it
, &saved_it
);
1651 /* If the next character is EN, but the last strong-type
1652 character is AL, that next EN will be changed to AN when
1653 we process it in W2 above. So in that case, this ES
1654 should not be changed into EN. */
1656 && type_of_next
== WEAK_EN
1657 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1659 else if (type
== WEAK_CS
)
1661 if (bidi_it
->prev
.type_after_w1
== WEAK_AN
1662 && (type_of_next
== WEAK_AN
1663 /* If the next character is EN, but the last
1664 strong-type character is AL, EN will be later
1665 changed to AN when we process it in W2 above.
1666 So in that case, this ES should not be
1668 || (type_of_next
== WEAK_EN
1669 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)))
1671 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
1672 && type_of_next
== WEAK_EN
1673 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1677 else if (type
== WEAK_ET
/* W5: ET with EN before or after it */
1678 || type
== WEAK_BN
) /* W5/Retaining */
1680 if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* ET/BN w/EN before it */
1681 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1683 else /* W5: ET/BN with EN after it. */
1685 EMACS_INT en_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
1686 const unsigned char *s
=
1687 STRINGP (bidi_it
->string
.lstring
)
1688 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1690 if (bidi_it
->nchars
<= 0)
1693 bidi_it
->charpos
+ bidi_it
->nchars
>= eob
1695 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
, s
,
1696 bidi_it
->string
.unibyte
);
1697 type_of_next
= bidi_get_type (next_char
, override
);
1699 if (type_of_next
== WEAK_ET
1700 || type_of_next
== WEAK_BN
1701 || bidi_explicit_dir_char (next_char
))
1703 bidi_copy_it (&saved_it
, bidi_it
);
1704 while (bidi_resolve_explicit (bidi_it
) == new_level
1705 && (bidi_it
->type
== WEAK_BN
1706 || bidi_it
->type
== WEAK_ET
))
1708 type_of_next
= bidi_it
->type
;
1709 en_pos
= bidi_it
->charpos
;
1710 bidi_copy_it (bidi_it
, &saved_it
);
1712 if (type_of_next
== WEAK_EN
)
1714 /* If the last strong character is AL, the EN we've
1715 found will become AN when we get to it (W2). */
1716 if (bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1719 /* Remember this EN position, to speed up processing
1721 bidi_it
->next_en_pos
= en_pos
;
1723 else if (type
== WEAK_BN
)
1724 type
= NEUTRAL_ON
; /* W6/Retaining */
1730 if (type
== WEAK_ES
|| type
== WEAK_ET
|| type
== WEAK_CS
/* W6 */
1732 && (bidi_it
->prev
.type_after_w1
== WEAK_CS
/* W6/Retaining */
1733 || bidi_it
->prev
.type_after_w1
== WEAK_ES
1734 || bidi_it
->prev
.type_after_w1
== WEAK_ET
)))
1737 /* Store the type we've got so far, before we clobber it with strong
1738 types in W7 and while resolving neutral types. But leave alone
1739 the original types that were recorded above, because we will need
1740 them for the L1 clause. */
1741 if (bidi_it
->type_after_w1
== UNKNOWN_BT
)
1742 bidi_it
->type_after_w1
= type
;
1743 bidi_check_type (bidi_it
->type_after_w1
);
1745 if (type
== WEAK_EN
) /* W7 */
1747 if ((bidi_it
->last_strong
.type_after_w1
== STRONG_L
)
1748 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
&& bidi_it
->sor
== L2R
))
1752 bidi_it
->type
= type
;
1753 bidi_check_type (bidi_it
->type
);
1757 /* Resolve the type of a neutral character according to the type of
1758 surrounding strong text and the current embedding level. */
1759 static inline bidi_type_t
1760 bidi_resolve_neutral_1 (bidi_type_t prev_type
, bidi_type_t next_type
, int lev
)
1762 /* N1: European and Arabic numbers are treated as though they were R. */
1763 if (next_type
== WEAK_EN
|| next_type
== WEAK_AN
)
1764 next_type
= STRONG_R
;
1765 if (prev_type
== WEAK_EN
|| prev_type
== WEAK_AN
)
1766 prev_type
= STRONG_R
;
1768 if (next_type
== prev_type
) /* N1 */
1770 else if ((lev
& 1) == 0) /* N2 */
1777 bidi_resolve_neutral (struct bidi_it
*bidi_it
)
1779 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1780 bidi_type_t type
= bidi_resolve_weak (bidi_it
);
1781 int current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1783 if (!(type
== STRONG_R
1788 || type
== NEUTRAL_B
1789 || type
== NEUTRAL_S
1790 || type
== NEUTRAL_WS
1791 || type
== NEUTRAL_ON
))
1794 if (bidi_get_category (type
) == NEUTRAL
1795 || (type
== WEAK_BN
&& prev_level
== current_level
))
1797 if (bidi_it
->next_for_neutral
.type
!= UNKNOWN_BT
)
1798 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1799 bidi_it
->next_for_neutral
.type
,
1803 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1804 the assumption of batch-style processing; see clauses W4,
1805 W5, and especially N1, which require to look far forward
1806 (as well as back) in the buffer/string. May the fleas of
1807 a thousand camels infest the armpits of those who design
1808 supposedly general-purpose algorithms by looking at their
1809 own implementations, and fail to consider other possible
1811 struct bidi_it saved_it
;
1812 bidi_type_t next_type
;
1814 if (bidi_it
->scan_dir
== -1)
1817 bidi_copy_it (&saved_it
, bidi_it
);
1818 /* Scan the text forward until we find the first non-neutral
1819 character, and then use that to resolve the neutral we
1820 are dealing with now. We also cache the scanned iterator
1821 states, to salvage some of the effort later. */
1822 bidi_cache_iterator_state (bidi_it
, 0);
1824 /* Record the info about the previous character, so that
1825 it will be cached below with this state. */
1826 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1827 && bidi_it
->type
!= WEAK_BN
)
1828 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1829 type
= bidi_resolve_weak (bidi_it
);
1830 /* Paragraph separators have their levels fully resolved
1831 at this point, so cache them as resolved. */
1832 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
);
1833 /* FIXME: implement L1 here, by testing for a newline and
1834 resetting the level for any sequence of whitespace
1835 characters adjacent to it. */
1836 } while (!(type
== NEUTRAL_B
1838 && bidi_get_category (type
) != NEUTRAL
)
1839 /* This is all per level run, so stop when we
1840 reach the end of this level run. */
1841 || bidi_it
->level_stack
[bidi_it
->stack_idx
].level
!=
1844 bidi_remember_char (&saved_it
.next_for_neutral
, bidi_it
);
1855 /* N1: ``European and Arabic numbers are treated as
1856 though they were R.'' */
1857 next_type
= STRONG_R
;
1858 saved_it
.next_for_neutral
.type
= STRONG_R
;
1861 if (!bidi_explicit_dir_char (bidi_it
->ch
))
1862 abort (); /* can't happen: BNs are skipped */
1865 /* Marched all the way to the end of this level run.
1866 We need to use the eor type, whose information is
1867 stored by bidi_set_sor_type in the prev_for_neutral
1869 if (saved_it
.type
!= WEAK_BN
1870 || bidi_get_category (bidi_it
->prev
.type_after_w1
) == NEUTRAL
)
1872 next_type
= bidi_it
->prev_for_neutral
.type
;
1873 saved_it
.next_for_neutral
.type
= next_type
;
1874 bidi_check_type (next_type
);
1878 /* This is a BN which does not adjoin neutrals.
1879 Leave its type alone. */
1880 bidi_copy_it (bidi_it
, &saved_it
);
1881 return bidi_it
->type
;
1887 type
= bidi_resolve_neutral_1 (saved_it
.prev_for_neutral
.type
,
1888 next_type
, current_level
);
1889 saved_it
.type
= type
;
1890 bidi_check_type (type
);
1891 bidi_copy_it (bidi_it
, &saved_it
);
1897 /* Given an iterator state in BIDI_IT, advance one character position
1898 in the buffer/string to the next character (in the logical order),
1899 resolve the bidi type of that next character, and return that
1902 bidi_type_of_next_char (struct bidi_it
*bidi_it
)
1906 /* This should always be called during a forward scan. */
1907 if (bidi_it
->scan_dir
!= 1)
1910 /* Reset the limit until which to ignore BNs if we step out of the
1911 area where we found only empty levels. */
1912 if ((bidi_it
->ignore_bn_limit
> -1
1913 && bidi_it
->ignore_bn_limit
<= bidi_it
->charpos
)
1914 || (bidi_it
->ignore_bn_limit
== -2
1915 && !bidi_explicit_dir_char (bidi_it
->ch
)))
1916 bidi_it
->ignore_bn_limit
= -1;
1918 type
= bidi_resolve_neutral (bidi_it
);
1923 /* Given an iterator state BIDI_IT, advance one character position in
1924 the buffer/string to the next character (in the current scan
1925 direction), resolve the embedding and implicit levels of that next
1926 character, and return the resulting level. */
1928 bidi_level_of_next_char (struct bidi_it
*bidi_it
)
1931 int level
, prev_level
= -1;
1932 struct bidi_saved_info next_for_neutral
;
1933 EMACS_INT next_char_pos
= -2;
1935 if (bidi_it
->scan_dir
== 1)
1938 (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
1939 ? bidi_it
->string
.schars
: ZV
;
1941 /* There's no sense in trying to advance if we hit end of text. */
1942 if (bidi_it
->charpos
>= eob
)
1943 return bidi_it
->resolved_level
;
1945 /* Record the info about the previous character. */
1946 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1947 && bidi_it
->type
!= WEAK_BN
)
1948 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1949 if (bidi_it
->type_after_w1
== STRONG_R
1950 || bidi_it
->type_after_w1
== STRONG_L
1951 || bidi_it
->type_after_w1
== STRONG_AL
)
1952 bidi_remember_char (&bidi_it
->last_strong
, bidi_it
);
1953 /* FIXME: it sounds like we don't need both prev and
1954 prev_for_neutral members, but I'm leaving them both for now. */
1955 if (bidi_it
->type
== STRONG_R
|| bidi_it
->type
== STRONG_L
1956 || bidi_it
->type
== WEAK_EN
|| bidi_it
->type
== WEAK_AN
)
1957 bidi_remember_char (&bidi_it
->prev_for_neutral
, bidi_it
);
1959 /* If we overstepped the characters used for resolving neutrals
1960 and whitespace, invalidate their info in the iterator. */
1961 if (bidi_it
->charpos
>= bidi_it
->next_for_neutral
.charpos
)
1962 bidi_it
->next_for_neutral
.type
= UNKNOWN_BT
;
1963 if (bidi_it
->next_en_pos
>= 0
1964 && bidi_it
->charpos
>= bidi_it
->next_en_pos
)
1965 bidi_it
->next_en_pos
= -1;
1966 if (bidi_it
->next_for_ws
.type
!= UNKNOWN_BT
1967 && bidi_it
->charpos
>= bidi_it
->next_for_ws
.charpos
)
1968 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
1970 /* This must be taken before we fill the iterator with the info
1971 about the next char. If we scan backwards, the iterator
1972 state must be already cached, so there's no need to know the
1973 embedding level of the previous character, since we will be
1974 returning to our caller shortly. */
1975 prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1977 next_for_neutral
= bidi_it
->next_for_neutral
;
1979 /* Perhaps the character we want is already cached. If it is, the
1980 call to bidi_cache_find below will return a type other than
1982 if (bidi_cache_idx
> bidi_cache_start
&& !bidi_it
->first_elt
)
1985 (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
)) ? 0 : 1;
1987 if (bidi_it
->scan_dir
> 0)
1989 if (bidi_it
->nchars
<= 0)
1991 next_char_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
1993 else if (bidi_it
->charpos
>= bob
)
1994 /* Implementation note: we allow next_char_pos to be as low as
1995 0 for buffers or -1 for strings, and that is okay because
1996 that's the "position" of the sentinel iterator state we
1997 cached at the beginning of the iteration. */
1998 next_char_pos
= bidi_it
->charpos
- 1;
1999 if (next_char_pos
>= bob
- 1)
2000 type
= bidi_cache_find (next_char_pos
, -1, bidi_it
);
2006 if (type
!= UNKNOWN_BT
)
2008 /* Don't lose the information for resolving neutrals! The
2009 cached states could have been cached before their
2010 next_for_neutral member was computed. If we are on our way
2011 forward, we can simply take the info from the previous
2013 if (bidi_it
->scan_dir
== 1
2014 && bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
2015 bidi_it
->next_for_neutral
= next_for_neutral
;
2017 /* If resolved_level is -1, it means this state was cached
2018 before it was completely resolved, so we cannot return
2020 if (bidi_it
->resolved_level
!= -1)
2021 return bidi_it
->resolved_level
;
2023 if (bidi_it
->scan_dir
== -1)
2024 /* If we are going backwards, the iterator state is already cached
2025 from previous scans, and should be fully resolved. */
2028 if (type
== UNKNOWN_BT
)
2029 type
= bidi_type_of_next_char (bidi_it
);
2031 if (type
== NEUTRAL_B
)
2032 return bidi_it
->resolved_level
;
2034 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
2035 if ((bidi_get_category (type
) == NEUTRAL
/* && type != NEUTRAL_B */)
2036 || (type
== WEAK_BN
&& prev_level
== level
))
2038 if (bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
2041 /* If the cached state shows a neutral character, it was not
2042 resolved by bidi_resolve_neutral, so do it now. */
2043 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
2044 bidi_it
->next_for_neutral
.type
,
2048 if (!(type
== STRONG_R
2052 || type
== WEAK_AN
))
2054 bidi_it
->type
= type
;
2055 bidi_check_type (bidi_it
->type
);
2057 /* For L1 below, we need to know, for each WS character, whether
2058 it belongs to a sequence of WS characters preceding a newline
2059 or a TAB or a paragraph separator. */
2060 if (bidi_it
->orig_type
== NEUTRAL_WS
2061 && bidi_it
->next_for_ws
.type
== UNKNOWN_BT
)
2064 EMACS_INT clen
= bidi_it
->ch_len
;
2065 EMACS_INT bpos
= bidi_it
->bytepos
;
2066 EMACS_INT cpos
= bidi_it
->charpos
;
2067 EMACS_INT disp_pos
= bidi_it
->disp_pos
;
2068 EMACS_INT nc
= bidi_it
->nchars
;
2069 struct bidi_string_data bs
= bidi_it
->string
;
2071 int fwp
= bidi_it
->frame_window_p
;
2072 int dpp
= bidi_it
->disp_prop_p
;
2074 if (bidi_it
->nchars
<= 0)
2077 ch
= bidi_fetch_char (bpos
+= clen
, cpos
+= nc
, &disp_pos
, &dpp
, &bs
,
2079 if (ch
== '\n' || ch
== BIDI_EOB
/* || ch == LINESEP_CHAR */)
2082 chtype
= bidi_get_type (ch
, NEUTRAL_DIR
);
2083 } while (chtype
== NEUTRAL_WS
|| chtype
== WEAK_BN
2084 || bidi_explicit_dir_char (ch
)); /* L1/Retaining */
2085 bidi_it
->next_for_ws
.type
= chtype
;
2086 bidi_check_type (bidi_it
->next_for_ws
.type
);
2087 bidi_it
->next_for_ws
.charpos
= cpos
;
2088 bidi_it
->next_for_ws
.bytepos
= bpos
;
2091 /* Resolve implicit levels, with a twist: PDFs get the embedding
2092 level of the enbedding they terminate. See below for the
2094 if (bidi_it
->orig_type
== PDF
2095 /* Don't do this if this formatting code didn't change the
2096 embedding level due to invalid or empty embeddings. */
2097 && prev_level
!= level
)
2099 /* Don't look in UAX#9 for the reason for this: it's our own
2100 private quirk. The reason is that we want the formatting
2101 codes to be delivered so that they bracket the text of their
2102 embedding. For example, given the text
2106 we want it to be displayed as
2114 which will result because we bump up the embedding level as
2115 soon as we see the RLO and pop it as soon as we see the PDF,
2116 so RLO itself has the same embedding level as "teST", and
2117 thus would be normally delivered last, just before the PDF.
2118 The switch below fiddles with the level of PDF so that this
2119 ugly side effect does not happen.
2121 (This is, of course, only important if the formatting codes
2122 are actually displayed, but Emacs does need to display them
2123 if the user wants to.) */
2126 else if (bidi_it
->orig_type
== NEUTRAL_B
/* L1 */
2127 || bidi_it
->orig_type
== NEUTRAL_S
2128 || bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
2129 /* || bidi_it->ch == LINESEP_CHAR */
2130 || (bidi_it
->orig_type
== NEUTRAL_WS
2131 && (bidi_it
->next_for_ws
.type
== NEUTRAL_B
2132 || bidi_it
->next_for_ws
.type
== NEUTRAL_S
)))
2133 level
= bidi_it
->level_stack
[0].level
;
2134 else if ((level
& 1) == 0) /* I1 */
2136 if (type
== STRONG_R
)
2138 else if (type
== WEAK_EN
|| type
== WEAK_AN
)
2143 if (type
== STRONG_L
|| type
== WEAK_EN
|| type
== WEAK_AN
)
2147 bidi_it
->resolved_level
= level
;
2151 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
2152 non-zero, we are at the end of a level, and we need to prepare to
2153 resume the scan of the lower level.
2155 If this level's other edge is cached, we simply jump to it, filling
2156 the iterator structure with the iterator state on the other edge.
2157 Otherwise, we walk the buffer or string until we come back to the
2158 same level as LEVEL.
2160 Note: we are not talking here about a ``level run'' in the UAX#9
2161 sense of the term, but rather about a ``level'' which includes
2162 all the levels higher than it. In other words, given the levels
2165 11111112222222333333334443343222222111111112223322111
2168 and assuming we are at point A scanning left to right, this
2169 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
2172 bidi_find_other_level_edge (struct bidi_it
*bidi_it
, int level
, int end_flag
)
2174 int dir
= end_flag
? -bidi_it
->scan_dir
: bidi_it
->scan_dir
;
2177 /* Try the cache first. */
2178 if ((idx
= bidi_cache_find_level_change (level
, dir
, end_flag
))
2179 >= bidi_cache_start
)
2180 bidi_cache_fetch_state (idx
, bidi_it
);
2186 abort (); /* if we are at end of level, its edges must be cached */
2188 bidi_cache_iterator_state (bidi_it
, 1);
2190 new_level
= bidi_level_of_next_char (bidi_it
);
2191 bidi_cache_iterator_state (bidi_it
, 1);
2192 } while (new_level
>= level
);
2197 bidi_move_to_visually_next (struct bidi_it
*bidi_it
)
2199 int old_level
, new_level
, next_level
;
2200 struct bidi_it sentinel
;
2201 struct gcpro gcpro1
;
2203 if (bidi_it
->charpos
< 0 || bidi_it
->bytepos
< 0)
2206 if (bidi_it
->scan_dir
== 0)
2208 bidi_it
->scan_dir
= 1; /* default to logical order */
2211 /* The code below can call eval, and thus cause GC. If we are
2212 iterating a Lisp string, make sure it won't be GCed. */
2213 if (STRINGP (bidi_it
->string
.lstring
))
2214 GCPRO1 (bidi_it
->string
.lstring
);
2216 /* If we just passed a newline, initialize for the next line. */
2217 if (!bidi_it
->first_elt
&& bidi_it
->orig_type
== NEUTRAL_B
)
2218 bidi_line_init (bidi_it
);
2220 /* Prepare the sentinel iterator state, and cache it. When we bump
2221 into it, scanning backwards, we'll know that the last non-base
2222 level is exhausted. */
2223 if (bidi_cache_idx
== bidi_cache_start
)
2225 bidi_copy_it (&sentinel
, bidi_it
);
2226 if (bidi_it
->first_elt
)
2228 sentinel
.charpos
--; /* cached charpos needs to be monotonic */
2230 sentinel
.ch
= '\n'; /* doesn't matter, but why not? */
2231 sentinel
.ch_len
= 1;
2232 sentinel
.nchars
= 1;
2234 bidi_cache_iterator_state (&sentinel
, 1);
2237 old_level
= bidi_it
->resolved_level
;
2238 new_level
= bidi_level_of_next_char (bidi_it
);
2240 /* Reordering of resolved levels (clause L2) is implemented by
2241 jumping to the other edge of the level and flipping direction of
2242 scanning the text whenever we find a level change. */
2243 if (new_level
!= old_level
)
2245 int ascending
= new_level
> old_level
;
2246 int level_to_search
= ascending
? old_level
+ 1 : old_level
;
2247 int incr
= ascending
? 1 : -1;
2248 int expected_next_level
= old_level
+ incr
;
2250 /* Jump (or walk) to the other edge of this level. */
2251 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
2252 /* Switch scan direction and peek at the next character in the
2254 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
2256 /* The following loop handles the case where the resolved level
2257 jumps by more than one. This is typical for numbers inside a
2258 run of text with left-to-right embedding direction, but can
2259 also happen in other situations. In those cases the decision
2260 where to continue after a level change, and in what direction,
2261 is tricky. For example, given a text like below:
2266 (where the numbers below the text show the resolved levels),
2267 the result of reordering according to UAX#9 should be this:
2271 This is implemented by the loop below which flips direction
2272 and jumps to the other edge of the level each time it finds
2273 the new level not to be the expected one. The expected level
2274 is always one more or one less than the previous one. */
2275 next_level
= bidi_peek_at_next_level (bidi_it
);
2276 while (next_level
!= expected_next_level
)
2278 expected_next_level
+= incr
;
2279 level_to_search
+= incr
;
2280 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
2281 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
2282 next_level
= bidi_peek_at_next_level (bidi_it
);
2285 /* Finally, deliver the next character in the new direction. */
2286 next_level
= bidi_level_of_next_char (bidi_it
);
2289 /* Take note when we have just processed the newline that precedes
2290 the end of the paragraph. The next time we are about to be
2291 called, set_iterator_to_next will automatically reinit the
2292 paragraph direction, if needed. We do this at the newline before
2293 the paragraph separator, because the next character might not be
2294 the first character of the next paragraph, due to the bidi
2295 reordering, whereas we _must_ know the paragraph base direction
2296 _before_ we process the paragraph's text, since the base
2297 direction affects the reordering. */
2298 if (bidi_it
->scan_dir
== 1 && bidi_it
->orig_type
== NEUTRAL_B
)
2300 /* The paragraph direction of the entire string, once
2301 determined, is in effect for the entire string. Setting the
2302 separator limit to the end of the string prevents
2303 bidi_paragraph_init from being called automatically on this
2305 if (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
2306 bidi_it
->separator_limit
= bidi_it
->string
.schars
;
2307 else if (bidi_it
->bytepos
< ZV_BYTE
)
2310 bidi_at_paragraph_end (bidi_it
->charpos
+ bidi_it
->nchars
,
2311 bidi_it
->bytepos
+ bidi_it
->ch_len
);
2312 if (bidi_it
->nchars
<= 0)
2316 bidi_it
->new_paragraph
= 1;
2317 /* Record the buffer position of the last character of the
2318 paragraph separator. */
2319 bidi_it
->separator_limit
=
2320 bidi_it
->charpos
+ bidi_it
->nchars
+ sep_len
;
2325 if (bidi_it
->scan_dir
== 1 && bidi_cache_idx
> bidi_cache_start
)
2327 /* If we are at paragraph's base embedding level and beyond the
2328 last cached position, the cache's job is done and we can
2330 if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
2331 && bidi_it
->charpos
> (bidi_cache
[bidi_cache_idx
- 1].charpos
2332 + bidi_cache
[bidi_cache_idx
- 1].nchars
- 1))
2333 bidi_cache_reset ();
2334 /* But as long as we are caching during forward scan, we must
2335 cache each state, or else the cache integrity will be
2336 compromised: it assumes cached states correspond to buffer
2339 bidi_cache_iterator_state (bidi_it
, 1);
2342 if (STRINGP (bidi_it
->string
.lstring
))
2346 /* This is meant to be called from within the debugger, whenever you
2347 wish to examine the cache contents. */
2348 void bidi_dump_cached_states (void) EXTERNALLY_VISIBLE
;
2350 bidi_dump_cached_states (void)
2355 if (bidi_cache_idx
== 0)
2357 fprintf (stderr
, "The cache is empty.\n");
2360 fprintf (stderr
, "Total of %"pD
"d state%s in cache:\n",
2361 bidi_cache_idx
, bidi_cache_idx
== 1 ? "" : "s");
2363 for (i
= bidi_cache
[bidi_cache_idx
- 1].charpos
; i
> 0; i
/= 10)
2365 fputs ("ch ", stderr
);
2366 for (i
= 0; i
< bidi_cache_idx
; i
++)
2367 fprintf (stderr
, "%*c", ndigits
, bidi_cache
[i
].ch
);
2368 fputs ("\n", stderr
);
2369 fputs ("lvl ", stderr
);
2370 for (i
= 0; i
< bidi_cache_idx
; i
++)
2371 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].resolved_level
);
2372 fputs ("\n", stderr
);
2373 fputs ("pos ", stderr
);
2374 for (i
= 0; i
< bidi_cache_idx
; i
++)
2375 fprintf (stderr
, "%*"pI
"d", ndigits
, bidi_cache
[i
].charpos
);
2376 fputs ("\n", stderr
);