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 EMACS_INT bidi_cache_size
= 0;
303 enum { elsz
= sizeof (struct bidi_it
) };
304 static EMACS_INT bidi_cache_idx
; /* next unused cache slot */
305 static EMACS_INT bidi_cache_last_idx
; /* slot of last cache hit */
306 static EMACS_INT bidi_cache_start
= 0; /* start of cache for this
309 /* Reset the cache state to the empty state. We only reset the part
310 of the cache relevant to iteration of the current object. Previous
311 objects, which are pushed on the display iterator's stack, are left
312 intact. This is called when the cached information is no more
313 useful for the current iteration, e.g. when we were reseated to a
314 new position on the same object. */
316 bidi_cache_reset (void)
318 bidi_cache_idx
= bidi_cache_start
;
319 bidi_cache_last_idx
= -1;
322 /* Shrink the cache to its minimal size. Called when we init the bidi
323 iterator for reordering a buffer or a string that does not come
324 from display properties, because that means all the previously
325 cached info is of no further use. */
327 bidi_cache_shrink (void)
329 if (bidi_cache_size
> BIDI_CACHE_CHUNK
)
331 bidi_cache_size
= BIDI_CACHE_CHUNK
;
333 (struct bidi_it
*) xrealloc (bidi_cache
, bidi_cache_size
* elsz
);
339 bidi_cache_fetch_state (EMACS_INT idx
, struct bidi_it
*bidi_it
)
341 int current_scan_dir
= bidi_it
->scan_dir
;
343 if (idx
< bidi_cache_start
|| idx
>= bidi_cache_idx
)
346 bidi_copy_it (bidi_it
, &bidi_cache
[idx
]);
347 bidi_it
->scan_dir
= current_scan_dir
;
348 bidi_cache_last_idx
= idx
;
351 /* Find a cached state with a given CHARPOS and resolved embedding
352 level less or equal to LEVEL. if LEVEL is -1, disregard the
353 resolved levels in cached states. DIR, if non-zero, means search
354 in that direction from the last cache hit. */
355 static inline EMACS_INT
356 bidi_cache_search (EMACS_INT charpos
, int level
, int dir
)
358 EMACS_INT i
, i_start
;
360 if (bidi_cache_idx
> bidi_cache_start
)
362 if (bidi_cache_last_idx
== -1)
363 bidi_cache_last_idx
= bidi_cache_idx
- 1;
364 if (charpos
< bidi_cache
[bidi_cache_last_idx
].charpos
)
367 i_start
= bidi_cache_last_idx
- 1;
369 else if (charpos
> (bidi_cache
[bidi_cache_last_idx
].charpos
370 + bidi_cache
[bidi_cache_last_idx
].nchars
- 1))
373 i_start
= bidi_cache_last_idx
+ 1;
376 i_start
= bidi_cache_last_idx
;
380 i_start
= bidi_cache_idx
- 1;
385 /* Linear search for now; FIXME! */
386 for (i
= i_start
; i
>= bidi_cache_start
; i
--)
387 if (bidi_cache
[i
].charpos
<= charpos
388 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
389 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
394 for (i
= i_start
; i
< bidi_cache_idx
; i
++)
395 if (bidi_cache
[i
].charpos
<= charpos
396 && charpos
< bidi_cache
[i
].charpos
+ bidi_cache
[i
].nchars
397 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
405 /* Find a cached state where the resolved level changes to a value
406 that is lower than LEVEL, and return its cache slot index. DIR is
407 the direction to search, starting with the last used cache slot.
408 If DIR is zero, we search backwards from the last occupied cache
409 slot. BEFORE, if non-zero, means return the index of the slot that
410 is ``before'' the level change in the search direction. That is,
411 given the cached levels like this:
416 and assuming we are at the position cached at the slot marked with
417 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
418 index of slot B or A, depending whether BEFORE is, respectively,
421 bidi_cache_find_level_change (int level
, int dir
, int before
)
425 EMACS_INT i
= dir
? bidi_cache_last_idx
: bidi_cache_idx
- 1;
426 int incr
= before
? 1 : 0;
428 xassert (!dir
|| bidi_cache_last_idx
>= 0);
437 while (i
>= bidi_cache_start
+ incr
)
439 if (bidi_cache
[i
- incr
].resolved_level
>= 0
440 && bidi_cache
[i
- incr
].resolved_level
< level
)
447 while (i
< bidi_cache_idx
- incr
)
449 if (bidi_cache
[i
+ incr
].resolved_level
>= 0
450 && bidi_cache
[i
+ incr
].resolved_level
< level
)
461 bidi_cache_ensure_space (EMACS_INT idx
)
463 /* Enlarge the cache as needed. */
464 if (idx
>= bidi_cache_size
)
466 while (idx
>= bidi_cache_size
)
467 bidi_cache_size
+= BIDI_CACHE_CHUNK
;
469 (struct bidi_it
*) xrealloc (bidi_cache
, bidi_cache_size
* elsz
);
474 bidi_cache_iterator_state (struct bidi_it
*bidi_it
, int resolved
)
478 /* We should never cache on backward scans. */
479 if (bidi_it
->scan_dir
== -1)
481 idx
= bidi_cache_search (bidi_it
->charpos
, -1, 1);
485 idx
= bidi_cache_idx
;
486 bidi_cache_ensure_space (idx
);
487 /* Character positions should correspond to cache positions 1:1.
488 If we are outside the range of cached positions, the cache is
489 useless and must be reset. */
490 if (idx
> bidi_cache_start
&&
491 (bidi_it
->charpos
> (bidi_cache
[idx
- 1].charpos
492 + bidi_cache
[idx
- 1].nchars
)
493 || bidi_it
->charpos
< bidi_cache
[bidi_cache_start
].charpos
))
496 idx
= bidi_cache_start
;
498 if (bidi_it
->nchars
<= 0)
500 bidi_copy_it (&bidi_cache
[idx
], bidi_it
);
502 bidi_cache
[idx
].resolved_level
= -1;
506 /* Copy only the members which could have changed, to avoid
507 costly copying of the entire struct. */
508 bidi_cache
[idx
].type
= bidi_it
->type
;
509 bidi_check_type (bidi_it
->type
);
510 bidi_cache
[idx
].type_after_w1
= bidi_it
->type_after_w1
;
511 bidi_check_type (bidi_it
->type_after_w1
);
513 bidi_cache
[idx
].resolved_level
= bidi_it
->resolved_level
;
515 bidi_cache
[idx
].resolved_level
= -1;
516 bidi_cache
[idx
].invalid_levels
= bidi_it
->invalid_levels
;
517 bidi_cache
[idx
].invalid_rl_levels
= bidi_it
->invalid_rl_levels
;
518 bidi_cache
[idx
].next_for_neutral
= bidi_it
->next_for_neutral
;
519 bidi_cache
[idx
].next_for_ws
= bidi_it
->next_for_ws
;
520 bidi_cache
[idx
].ignore_bn_limit
= bidi_it
->ignore_bn_limit
;
523 bidi_cache_last_idx
= idx
;
524 if (idx
>= bidi_cache_idx
)
525 bidi_cache_idx
= idx
+ 1;
528 static inline bidi_type_t
529 bidi_cache_find (EMACS_INT charpos
, int level
, struct bidi_it
*bidi_it
)
531 EMACS_INT i
= bidi_cache_search (charpos
, level
, bidi_it
->scan_dir
);
533 if (i
>= bidi_cache_start
)
535 bidi_dir_t current_scan_dir
= bidi_it
->scan_dir
;
537 bidi_copy_it (bidi_it
, &bidi_cache
[i
]);
538 bidi_cache_last_idx
= i
;
539 /* Don't let scan direction from from the cached state override
540 the current scan direction. */
541 bidi_it
->scan_dir
= current_scan_dir
;
542 return bidi_it
->type
;
549 bidi_peek_at_next_level (struct bidi_it
*bidi_it
)
551 if (bidi_cache_idx
== bidi_cache_start
|| bidi_cache_last_idx
== -1)
553 return bidi_cache
[bidi_cache_last_idx
+ bidi_it
->scan_dir
].resolved_level
;
557 /***********************************************************************
558 Pushing and popping the bidi iterator state
559 ***********************************************************************/
560 /* 5-slot stack for saving the start of the previous level of the
561 cache. xdisp.c maintains a 5-slot stack for its iterator state,
562 and we need the same size of our stack. */
563 static EMACS_INT bidi_cache_start_stack
[IT_STACK_SIZE
];
564 static int bidi_cache_sp
;
566 /* Push the bidi iterator state in preparation for reordering a
567 different object, e.g. display string found at certain buffer
568 position. Pushing the bidi iterator boils down to saving its
569 entire state on the cache and starting a new cache "stacked" on top
570 of the current cache. */
572 bidi_push_it (struct bidi_it
*bidi_it
)
574 /* Save the current iterator state in its entirety after the last
576 bidi_cache_ensure_space (bidi_cache_idx
);
577 memcpy (&bidi_cache
[bidi_cache_idx
++], bidi_it
, sizeof (struct bidi_it
));
579 /* Push the current cache start onto the stack. */
580 xassert (bidi_cache_sp
< IT_STACK_SIZE
);
581 bidi_cache_start_stack
[bidi_cache_sp
++] = bidi_cache_start
;
583 /* Start a new level of cache, and make it empty. */
584 bidi_cache_start
= bidi_cache_idx
;
585 bidi_cache_last_idx
= -1;
588 /* Restore the iterator state saved by bidi_push_it and return the
589 cache to the corresponding state. */
591 bidi_pop_it (struct bidi_it
*bidi_it
)
593 if (bidi_cache_start
<= 0)
596 /* Reset the next free cache slot index to what it was before the
597 call to bidi_push_it. */
598 bidi_cache_idx
= bidi_cache_start
- 1;
600 /* Restore the bidi iterator state saved in the cache. */
601 memcpy (bidi_it
, &bidi_cache
[bidi_cache_idx
], sizeof (struct bidi_it
));
603 /* Pop the previous cache start from the stack. */
604 if (bidi_cache_sp
<= 0)
606 bidi_cache_start
= bidi_cache_start_stack
[--bidi_cache_sp
];
608 /* Invalidate the last-used cache slot data. */
609 bidi_cache_last_idx
= -1;
612 /* Stash away a copy of the cache and its control variables. */
614 bidi_shelve_cache (void)
616 unsigned char *databuf
;
618 if (bidi_cache_idx
== 0)
621 databuf
= xmalloc (sizeof (bidi_cache_idx
)
622 + bidi_cache_idx
* sizeof (struct bidi_it
)
623 + sizeof (bidi_cache_start_stack
)
624 + sizeof (bidi_cache_sp
) + sizeof (bidi_cache_start
)
625 + sizeof (bidi_cache_last_idx
));
626 memcpy (databuf
, &bidi_cache_idx
, sizeof (bidi_cache_idx
));
627 memcpy (databuf
+ sizeof (bidi_cache_idx
),
628 bidi_cache
, bidi_cache_idx
* sizeof (struct bidi_it
));
629 memcpy (databuf
+ sizeof (bidi_cache_idx
)
630 + bidi_cache_idx
* sizeof (struct bidi_it
),
631 bidi_cache_start_stack
, sizeof (bidi_cache_start_stack
));
632 memcpy (databuf
+ sizeof (bidi_cache_idx
)
633 + bidi_cache_idx
* sizeof (struct bidi_it
)
634 + sizeof (bidi_cache_start_stack
),
635 &bidi_cache_sp
, sizeof (bidi_cache_sp
));
636 memcpy (databuf
+ sizeof (bidi_cache_idx
)
637 + bidi_cache_idx
* sizeof (struct bidi_it
)
638 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
639 &bidi_cache_start
, sizeof (bidi_cache_start
));
640 memcpy (databuf
+ sizeof (bidi_cache_idx
)
641 + bidi_cache_idx
* sizeof (struct bidi_it
)
642 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
643 + sizeof (bidi_cache_start
),
644 &bidi_cache_last_idx
, sizeof (bidi_cache_last_idx
));
649 /* Restore the cache state from a copy stashed away by bidi_shelve_cache. */
651 bidi_unshelve_cache (void *databuf
)
653 unsigned char *p
= databuf
;
657 /* A NULL pointer means an empty cache. */
658 bidi_cache_start
= 0;
664 memcpy (&bidi_cache_idx
, p
, sizeof (bidi_cache_idx
));
665 bidi_cache_ensure_space (bidi_cache_idx
);
666 memcpy (bidi_cache
, p
+ sizeof (bidi_cache_idx
),
667 bidi_cache_idx
* sizeof (struct bidi_it
));
668 memcpy (bidi_cache_start_stack
,
669 p
+ sizeof (bidi_cache_idx
)
670 + bidi_cache_idx
* sizeof (struct bidi_it
),
671 sizeof (bidi_cache_start_stack
));
672 memcpy (&bidi_cache_sp
,
673 p
+ sizeof (bidi_cache_idx
)
674 + bidi_cache_idx
* sizeof (struct bidi_it
)
675 + sizeof (bidi_cache_start_stack
),
676 sizeof (bidi_cache_sp
));
677 memcpy (&bidi_cache_start
,
678 p
+ sizeof (bidi_cache_idx
)
679 + bidi_cache_idx
* sizeof (struct bidi_it
)
680 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
),
681 sizeof (bidi_cache_start
));
682 memcpy (&bidi_cache_last_idx
,
683 p
+ sizeof (bidi_cache_idx
)
684 + bidi_cache_idx
* sizeof (struct bidi_it
)
685 + sizeof (bidi_cache_start_stack
) + sizeof (bidi_cache_sp
)
686 + sizeof (bidi_cache_start
),
687 sizeof (bidi_cache_last_idx
));
694 /***********************************************************************
696 ***********************************************************************/
698 bidi_initialize (void)
701 #include "biditype.h"
702 #include "bidimirror.h"
706 bidi_type_table
= Fmake_char_table (Qnil
, make_number (STRONG_L
));
707 staticpro (&bidi_type_table
);
709 for (i
= 0; i
< sizeof bidi_type
/ sizeof bidi_type
[0]; i
++)
710 char_table_set_range (bidi_type_table
, bidi_type
[i
].from
, bidi_type
[i
].to
,
711 make_number (bidi_type
[i
].type
));
713 bidi_mirror_table
= Fmake_char_table (Qnil
, Qnil
);
714 staticpro (&bidi_mirror_table
);
716 for (i
= 0; i
< sizeof bidi_mirror
/ sizeof bidi_mirror
[0]; i
++)
717 char_table_set (bidi_mirror_table
, bidi_mirror
[i
].from
,
718 make_number (bidi_mirror
[i
].to
));
720 Qparagraph_start
= intern ("paragraph-start");
721 staticpro (&Qparagraph_start
);
722 paragraph_start_re
= Fsymbol_value (Qparagraph_start
);
723 if (!STRINGP (paragraph_start_re
))
724 paragraph_start_re
= build_string ("\f\\|[ \t]*$");
725 staticpro (¶graph_start_re
);
726 Qparagraph_separate
= intern ("paragraph-separate");
727 staticpro (&Qparagraph_separate
);
728 paragraph_separate_re
= Fsymbol_value (Qparagraph_separate
);
729 if (!STRINGP (paragraph_separate_re
))
730 paragraph_separate_re
= build_string ("[ \t\f]*$");
731 staticpro (¶graph_separate_re
);
735 bidi_initialized
= 1;
738 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
741 bidi_set_paragraph_end (struct bidi_it
*bidi_it
)
743 bidi_it
->invalid_levels
= 0;
744 bidi_it
->invalid_rl_levels
= -1;
745 bidi_it
->stack_idx
= 0;
746 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
749 /* Initialize the bidi iterator from buffer/string position CHARPOS. */
751 bidi_init_it (EMACS_INT charpos
, EMACS_INT bytepos
, int frame_window_p
,
752 struct bidi_it
*bidi_it
)
754 if (! bidi_initialized
)
757 bidi_it
->charpos
= charpos
;
759 bidi_it
->bytepos
= bytepos
;
760 bidi_it
->frame_window_p
= frame_window_p
;
761 bidi_it
->nchars
= -1; /* to be computed in bidi_resolve_explicit_1 */
762 bidi_it
->first_elt
= 1;
763 bidi_set_paragraph_end (bidi_it
);
764 bidi_it
->new_paragraph
= 1;
765 bidi_it
->separator_limit
= -1;
766 bidi_it
->type
= NEUTRAL_B
;
767 bidi_it
->type_after_w1
= NEUTRAL_B
;
768 bidi_it
->orig_type
= NEUTRAL_B
;
769 bidi_it
->prev_was_pdf
= 0;
770 bidi_it
->prev
.type
= bidi_it
->prev
.type_after_w1
=
771 bidi_it
->prev
.orig_type
= UNKNOWN_BT
;
772 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
773 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
774 bidi_it
->next_for_neutral
.charpos
= -1;
775 bidi_it
->next_for_neutral
.type
=
776 bidi_it
->next_for_neutral
.type_after_w1
=
777 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
778 bidi_it
->prev_for_neutral
.charpos
= -1;
779 bidi_it
->prev_for_neutral
.type
=
780 bidi_it
->prev_for_neutral
.type_after_w1
=
781 bidi_it
->prev_for_neutral
.orig_type
= UNKNOWN_BT
;
782 bidi_it
->sor
= L2R
; /* FIXME: should it be user-selectable? */
783 bidi_it
->disp_pos
= -1; /* invalid/unknown */
784 /* We can only shrink the cache if we are at the bottom level of its
786 if (bidi_cache_start
== 0)
787 bidi_cache_shrink ();
792 /* Perform initializations for reordering a new line of bidi text. */
794 bidi_line_init (struct bidi_it
*bidi_it
)
796 bidi_it
->scan_dir
= 1; /* FIXME: do we need to have control on this? */
797 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
798 bidi_it
->level_stack
[0].override
= NEUTRAL_DIR
; /* X1 */
799 bidi_it
->invalid_levels
= 0;
800 bidi_it
->invalid_rl_levels
= -1;
801 bidi_it
->next_en_pos
= -1;
802 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
803 bidi_set_sor_type (bidi_it
,
804 bidi_it
->paragraph_dir
== R2L
? 1 : 0,
805 bidi_it
->level_stack
[0].level
); /* X10 */
811 /***********************************************************************
813 ***********************************************************************/
815 /* Count bytes in string S between BEG/BEGBYTE and END. BEG and END
816 are zero-based character positions in S, BEGBYTE is byte position
817 corresponding to BEG. UNIBYTE, if non-zero, means S is a unibyte
819 static inline EMACS_INT
820 bidi_count_bytes (const unsigned char *s
, const EMACS_INT beg
,
821 const EMACS_INT begbyte
, const EMACS_INT end
, int unibyte
)
824 const unsigned char *p
= s
+ begbyte
, *start
= p
;
830 if (!CHAR_HEAD_P (*p
))
835 p
+= BYTES_BY_CHAR_HEAD (*p
);
843 /* Fetch and returns the character at byte position BYTEPOS. If S is
844 non-NULL, fetch the character from string S; otherwise fetch the
845 character from the current buffer. UNIBYTE non-zero means S is a
848 bidi_char_at_pos (EMACS_INT bytepos
, const unsigned char *s
, int unibyte
)
855 return STRING_CHAR (s
+ bytepos
);
858 return FETCH_MULTIBYTE_CHAR (bytepos
);
861 /* Fetch and return the character at BYTEPOS/CHARPOS. If that
862 character is covered by a display string, treat the entire run of
863 covered characters as a single character u+FFFC, and return their
864 combined length in CH_LEN and NCHARS. DISP_POS specifies the
865 character position of the next display string, or -1 if not yet
866 computed. When the next character is at or beyond that position,
867 the function updates DISP_POS with the position of the next display
868 string. STRING->s is the C string to iterate, or NULL if iterating
869 over a buffer or a Lisp string; in the latter case, STRING->lstring
870 is the Lisp string. */
872 bidi_fetch_char (EMACS_INT bytepos
, EMACS_INT charpos
, EMACS_INT
*disp_pos
,
873 struct bidi_string_data
*string
,
874 int frame_window_p
, EMACS_INT
*ch_len
, EMACS_INT
*nchars
)
878 (string
->s
|| STRINGP (string
->lstring
)) ? string
->schars
: ZV
;
881 /* If we got past the last known position of display string, compute
882 the position of the next one. That position could be at CHARPOS. */
883 if (charpos
< endpos
&& charpos
> *disp_pos
)
885 SET_TEXT_POS (pos
, charpos
, bytepos
);
886 *disp_pos
= compute_display_string_pos (&pos
, string
, frame_window_p
);
889 /* Fetch the character at BYTEPOS. */
890 if (charpos
>= endpos
)
897 else if (charpos
>= *disp_pos
)
899 EMACS_INT disp_end_pos
;
901 /* We don't expect to find ourselves in the middle of a display
902 property. Hopefully, it will never be needed. */
903 if (charpos
> *disp_pos
)
905 /* Return the Unicode Object Replacement Character to represent
906 the entire run of characters covered by the display string. */
908 disp_end_pos
= compute_display_string_end (*disp_pos
, string
);
909 *nchars
= disp_end_pos
- *disp_pos
;
913 *ch_len
= bidi_count_bytes (string
->s
, *disp_pos
, bytepos
,
914 disp_end_pos
, string
->unibyte
);
915 else if (STRINGP (string
->lstring
))
916 *ch_len
= bidi_count_bytes (SDATA (string
->lstring
), *disp_pos
,
917 bytepos
, disp_end_pos
, string
->unibyte
);
919 *ch_len
= CHAR_TO_BYTE (disp_end_pos
) - bytepos
;
927 if (!string
->unibyte
)
929 ch
= STRING_CHAR_AND_LENGTH (string
->s
+ bytepos
, len
);
934 ch
= UNIBYTE_TO_CHAR (string
->s
[bytepos
]);
938 else if (STRINGP (string
->lstring
))
942 if (!string
->unibyte
)
944 ch
= STRING_CHAR_AND_LENGTH (SDATA (string
->lstring
) + bytepos
,
950 ch
= UNIBYTE_TO_CHAR (SREF (string
->lstring
, bytepos
));
956 ch
= FETCH_MULTIBYTE_CHAR (bytepos
);
957 *ch_len
= CHAR_BYTES (ch
);
962 /* If we just entered a run of characters covered by a display
963 string, compute the position of the next display string. */
964 if (charpos
+ *nchars
<= endpos
&& charpos
+ *nchars
> *disp_pos
)
966 SET_TEXT_POS (pos
, charpos
+ *nchars
, bytepos
+ *ch_len
);
967 *disp_pos
= compute_display_string_pos (&pos
, string
, frame_window_p
);
974 /***********************************************************************
975 Determining paragraph direction
976 ***********************************************************************/
978 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
979 Value is the non-negative length of the paragraph separator
980 following the buffer position, -1 if position is at the beginning
981 of a new paragraph, or -2 if position is neither at beginning nor
982 at end of a paragraph. */
984 bidi_at_paragraph_end (EMACS_INT charpos
, EMACS_INT bytepos
)
987 Lisp_Object start_re
;
990 sep_re
= paragraph_separate_re
;
991 start_re
= paragraph_start_re
;
993 val
= fast_looking_at (sep_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
);
996 if (fast_looking_at (start_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
) >= 0)
1005 /* Find the beginning of this paragraph by looking back in the buffer.
1006 Value is the byte position of the paragraph's beginning. */
1008 bidi_find_paragraph_start (EMACS_INT pos
, EMACS_INT pos_byte
)
1010 Lisp_Object re
= paragraph_start_re
;
1011 EMACS_INT limit
= ZV
, limit_byte
= ZV_BYTE
;
1013 while (pos_byte
> BEGV_BYTE
1014 && fast_looking_at (re
, pos
, pos_byte
, limit
, limit_byte
, Qnil
) < 0)
1016 /* FIXME: What if the paragraph beginning is covered by a
1017 display string? And what if a display string covering some
1018 of the text over which we scan back includes
1019 paragraph_start_re? */
1020 pos
= find_next_newline_no_quit (pos
- 1, -1);
1021 pos_byte
= CHAR_TO_BYTE (pos
);
1026 /* Determine the base direction, a.k.a. base embedding level, of the
1027 paragraph we are about to iterate through. If DIR is either L2R or
1028 R2L, just use that. Otherwise, determine the paragraph direction
1029 from the first strong directional character of the paragraph.
1031 NO_DEFAULT_P non-zero means don't default to L2R if the paragraph
1032 has no strong directional characters and both DIR and
1033 bidi_it->paragraph_dir are NEUTRAL_DIR. In that case, search back
1034 in the buffer until a paragraph is found with a strong character,
1035 or until hitting BEGV. In the latter case, fall back to L2R. This
1036 flag is used in current-bidi-paragraph-direction.
1038 Note that this function gives the paragraph separator the same
1039 direction as the preceding paragraph, even though Emacs generally
1040 views the separartor as not belonging to any paragraph. */
1042 bidi_paragraph_init (bidi_dir_t dir
, struct bidi_it
*bidi_it
, int no_default_p
)
1044 EMACS_INT bytepos
= bidi_it
->bytepos
;
1045 int string_p
= bidi_it
->string
.s
!= NULL
|| STRINGP (bidi_it
->string
.lstring
);
1046 EMACS_INT pstartbyte
;
1047 /* Note that begbyte is a byte position, while end is a character
1048 position. Yes, this is ugly, but we are trying to avoid costly
1049 calls to BYTE_TO_CHAR and its ilk. */
1050 EMACS_INT begbyte
= string_p
? 0 : BEGV_BYTE
;
1051 EMACS_INT end
= string_p
? bidi_it
->string
.schars
: ZV
;
1053 /* Special case for an empty buffer. */
1054 if (bytepos
== begbyte
&& bidi_it
->charpos
== end
)
1056 /* We should never be called at EOB or before BEGV. */
1057 else if (bidi_it
->charpos
>= end
|| bytepos
< begbyte
)
1062 bidi_it
->paragraph_dir
= L2R
;
1063 bidi_it
->new_paragraph
= 0;
1065 else if (dir
== R2L
)
1067 bidi_it
->paragraph_dir
= R2L
;
1068 bidi_it
->new_paragraph
= 0;
1070 else if (dir
== NEUTRAL_DIR
) /* P2 */
1073 EMACS_INT ch_len
, nchars
;
1074 EMACS_INT pos
, disp_pos
= -1;
1076 const unsigned char *s
;
1078 if (!bidi_initialized
)
1081 /* If we are inside a paragraph separator, we are just waiting
1082 for the separator to be exhausted; use the previous paragraph
1083 direction. But don't do that if we have been just reseated,
1084 because we need to reinitialize below in that case. */
1085 if (!bidi_it
->first_elt
1086 && bidi_it
->charpos
< bidi_it
->separator_limit
)
1089 /* If we are on a newline, get past it to where the next
1090 paragraph might start. But don't do that at BEGV since then
1091 we are potentially in a new paragraph that doesn't yet
1093 pos
= bidi_it
->charpos
;
1094 s
= STRINGP (bidi_it
->string
.lstring
) ?
1095 SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1096 if (bytepos
> begbyte
1097 && bidi_char_at_pos (bytepos
, s
, bidi_it
->string
.unibyte
) == '\n')
1103 /* We are either at the beginning of a paragraph or in the
1104 middle of it. Find where this paragraph starts. */
1107 /* We don't support changes of paragraph direction inside a
1108 string. It is treated as a single paragraph. */
1112 pstartbyte
= bidi_find_paragraph_start (pos
, bytepos
);
1113 bidi_it
->separator_limit
= -1;
1114 bidi_it
->new_paragraph
= 0;
1116 /* The following loop is run more than once only if NO_DEFAULT_P
1117 is non-zero, and only if we are iterating on a buffer. */
1119 bytepos
= pstartbyte
;
1121 pos
= BYTE_TO_CHAR (bytepos
);
1122 ch
= bidi_fetch_char (bytepos
, pos
, &disp_pos
, &bidi_it
->string
,
1123 bidi_it
->frame_window_p
, &ch_len
, &nchars
);
1124 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
1126 for (pos
+= nchars
, bytepos
+= ch_len
;
1127 /* NOTE: UAX#9 says to search only for L, AL, or R types
1128 of characters, and ignore RLE, RLO, LRE, and LRO.
1129 However, I'm not sure it makes sense to omit those 4;
1130 should try with and without that to see the effect. */
1131 (bidi_get_category (type
) != STRONG
)
1132 || (bidi_ignore_explicit_marks_for_paragraph_level
1133 && (type
== RLE
|| type
== RLO
1134 || type
== LRE
|| type
== LRO
));
1135 type
= bidi_get_type (ch
, NEUTRAL_DIR
))
1139 /* Pretend there's a paragraph separator at end of
1145 && type
== NEUTRAL_B
1146 && bidi_at_paragraph_end (pos
, bytepos
) >= -1)
1148 /* Fetch next character and advance to get past it. */
1149 ch
= bidi_fetch_char (bytepos
, pos
, &disp_pos
, &bidi_it
->string
,
1150 bidi_it
->frame_window_p
, &ch_len
, &nchars
);
1154 if (type
== STRONG_R
|| type
== STRONG_AL
) /* P3 */
1155 bidi_it
->paragraph_dir
= R2L
;
1156 else if (type
== STRONG_L
)
1157 bidi_it
->paragraph_dir
= L2R
;
1159 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
)
1161 /* If this paragraph is at BEGV, default to L2R. */
1162 if (pstartbyte
== BEGV_BYTE
)
1163 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 */
1166 EMACS_INT prevpbyte
= pstartbyte
;
1167 EMACS_INT p
= BYTE_TO_CHAR (pstartbyte
), pbyte
= pstartbyte
;
1169 /* Find the beginning of the previous paragraph, if any. */
1170 while (pbyte
> BEGV_BYTE
&& prevpbyte
>= pstartbyte
)
1172 /* FXIME: What if p is covered by a display
1173 string? See also a FIXME inside
1174 bidi_find_paragraph_start. */
1176 pbyte
= CHAR_TO_BYTE (p
);
1177 prevpbyte
= bidi_find_paragraph_start (p
, pbyte
);
1179 pstartbyte
= prevpbyte
;
1183 && no_default_p
&& bidi_it
->paragraph_dir
== NEUTRAL_DIR
);
1188 /* Contrary to UAX#9 clause P3, we only default the paragraph
1189 direction to L2R if we have no previous usable paragraph
1190 direction. This is allowed by the HL1 clause. */
1191 if (bidi_it
->paragraph_dir
!= L2R
&& bidi_it
->paragraph_dir
!= R2L
)
1192 bidi_it
->paragraph_dir
= L2R
; /* P3 and HL1 ``higher-level protocols'' */
1193 if (bidi_it
->paragraph_dir
== R2L
)
1194 bidi_it
->level_stack
[0].level
= 1;
1196 bidi_it
->level_stack
[0].level
= 0;
1198 bidi_line_init (bidi_it
);
1202 /***********************************************************************
1203 Resolving explicit and implicit levels.
1204 The rest of this file constitutes the core of the UBA implementation.
1205 ***********************************************************************/
1208 bidi_explicit_dir_char (int ch
)
1210 bidi_type_t ch_type
;
1212 if (!bidi_initialized
)
1214 ch_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
1215 return (ch_type
== LRE
|| ch_type
== LRO
1216 || ch_type
== RLE
|| ch_type
== RLO
1220 /* A helper function for bidi_resolve_explicit. It advances to the
1221 next character in logical order and determines the new embedding
1222 level and directional override, but does not take into account
1223 empty embeddings. */
1225 bidi_resolve_explicit_1 (struct bidi_it
*bidi_it
)
1231 bidi_dir_t override
;
1232 int string_p
= bidi_it
->string
.s
!= NULL
|| STRINGP (bidi_it
->string
.lstring
);
1234 /* If reseat()'ed, don't advance, so as to start iteration from the
1235 position where we were reseated. bidi_it->bytepos can be less
1236 than BEGV_BYTE after reseat to BEGV. */
1237 if (bidi_it
->bytepos
< (string_p
? 0 : BEGV_BYTE
)
1238 || bidi_it
->first_elt
)
1240 bidi_it
->first_elt
= 0;
1243 const unsigned char *p
=
1244 STRINGP (bidi_it
->string
.lstring
)
1245 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1247 if (bidi_it
->charpos
< 0)
1248 bidi_it
->charpos
= 0;
1249 bidi_it
->bytepos
= bidi_count_bytes (p
, 0, 0, bidi_it
->charpos
,
1250 bidi_it
->string
.unibyte
);
1254 if (bidi_it
->charpos
< BEGV
)
1255 bidi_it
->charpos
= BEGV
;
1256 bidi_it
->bytepos
= CHAR_TO_BYTE (bidi_it
->charpos
);
1259 /* Don't move at end of buffer/string. */
1260 else if (bidi_it
->charpos
< (string_p
? bidi_it
->string
.schars
: ZV
))
1262 /* Advance to the next character, skipping characters covered by
1263 display strings (nchars > 1). */
1264 if (bidi_it
->nchars
<= 0)
1266 bidi_it
->charpos
+= bidi_it
->nchars
;
1267 if (bidi_it
->ch_len
== 0)
1269 bidi_it
->bytepos
+= bidi_it
->ch_len
;
1272 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
; /* X1 */
1273 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1274 new_level
= current_level
;
1276 if (bidi_it
->charpos
>= (string_p
? bidi_it
->string
.schars
: ZV
))
1279 bidi_it
->ch_len
= 1;
1280 bidi_it
->nchars
= 1;
1281 bidi_it
->disp_pos
= (string_p
? bidi_it
->string
.schars
: ZV
);
1285 /* Fetch the character at BYTEPOS. If it is covered by a
1286 display string, treat the entire run of covered characters as
1287 a single character u+FFFC. */
1288 curchar
= bidi_fetch_char (bidi_it
->bytepos
, bidi_it
->charpos
,
1289 &bidi_it
->disp_pos
, &bidi_it
->string
,
1290 bidi_it
->frame_window_p
,
1291 &bidi_it
->ch_len
, &bidi_it
->nchars
);
1293 bidi_it
->ch
= curchar
;
1295 /* Don't apply directional override here, as all the types we handle
1296 below will not be affected by the override anyway, and we need
1297 the original type unaltered. The override will be applied in
1298 bidi_resolve_weak. */
1299 type
= bidi_get_type (curchar
, NEUTRAL_DIR
);
1300 bidi_it
->orig_type
= type
;
1301 bidi_check_type (bidi_it
->orig_type
);
1304 bidi_it
->prev_was_pdf
= 0;
1306 bidi_it
->type_after_w1
= UNKNOWN_BT
;
1312 bidi_it
->type_after_w1
= type
;
1313 bidi_check_type (bidi_it
->type_after_w1
);
1314 type
= WEAK_BN
; /* X9/Retaining */
1315 if (bidi_it
->ignore_bn_limit
<= -1)
1317 if (current_level
<= BIDI_MAXLEVEL
- 4)
1319 /* Compute the least odd embedding level greater than
1320 the current level. */
1321 new_level
= ((current_level
+ 1) & ~1) + 1;
1322 if (bidi_it
->type_after_w1
== RLE
)
1323 override
= NEUTRAL_DIR
;
1326 if (current_level
== BIDI_MAXLEVEL
- 4)
1327 bidi_it
->invalid_rl_levels
= 0;
1328 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1332 bidi_it
->invalid_levels
++;
1333 /* See the commentary about invalid_rl_levels below. */
1334 if (bidi_it
->invalid_rl_levels
< 0)
1335 bidi_it
->invalid_rl_levels
= 0;
1336 bidi_it
->invalid_rl_levels
++;
1339 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1340 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1345 bidi_it
->type_after_w1
= type
;
1346 bidi_check_type (bidi_it
->type_after_w1
);
1347 type
= WEAK_BN
; /* X9/Retaining */
1348 if (bidi_it
->ignore_bn_limit
<= -1)
1350 if (current_level
<= BIDI_MAXLEVEL
- 5)
1352 /* Compute the least even embedding level greater than
1353 the current level. */
1354 new_level
= ((current_level
+ 2) & ~1);
1355 if (bidi_it
->type_after_w1
== LRE
)
1356 override
= NEUTRAL_DIR
;
1359 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1363 bidi_it
->invalid_levels
++;
1364 /* invalid_rl_levels counts invalid levels encountered
1365 while the embedding level was already too high for
1366 LRE/LRO, but not for RLE/RLO. That is because
1367 there may be exactly one PDF which we should not
1368 ignore even though invalid_levels is non-zero.
1369 invalid_rl_levels helps to know what PDF is
1371 if (bidi_it
->invalid_rl_levels
>= 0)
1372 bidi_it
->invalid_rl_levels
++;
1375 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1376 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1380 bidi_it
->type_after_w1
= type
;
1381 bidi_check_type (bidi_it
->type_after_w1
);
1382 type
= WEAK_BN
; /* X9/Retaining */
1383 if (bidi_it
->ignore_bn_limit
<= -1)
1385 if (!bidi_it
->invalid_rl_levels
)
1387 new_level
= bidi_pop_embedding_level (bidi_it
);
1388 bidi_it
->invalid_rl_levels
= -1;
1389 if (bidi_it
->invalid_levels
)
1390 bidi_it
->invalid_levels
--;
1391 /* else nothing: UAX#9 says to ignore invalid PDFs */
1393 if (!bidi_it
->invalid_levels
)
1394 new_level
= bidi_pop_embedding_level (bidi_it
);
1397 bidi_it
->invalid_levels
--;
1398 bidi_it
->invalid_rl_levels
--;
1401 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1402 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1410 bidi_it
->type
= type
;
1411 bidi_check_type (bidi_it
->type
);
1416 /* Given an iterator state in BIDI_IT, advance one character position
1417 in the buffer/string to the next character (in the logical order),
1418 resolve any explicit embeddings and directional overrides, and
1419 return the embedding level of the character after resolving
1420 explicit directives and ignoring empty embeddings. */
1422 bidi_resolve_explicit (struct bidi_it
*bidi_it
)
1424 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1425 int new_level
= bidi_resolve_explicit_1 (bidi_it
);
1426 EMACS_INT eob
= bidi_it
->string
.s
? bidi_it
->string
.schars
: ZV
;
1427 const unsigned char *s
= STRINGP (bidi_it
->string
.lstring
)
1428 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1430 if (prev_level
< new_level
1431 && bidi_it
->type
== WEAK_BN
1432 && bidi_it
->ignore_bn_limit
== -1 /* only if not already known */
1433 && bidi_it
->charpos
< eob
/* not already at EOB */
1434 && bidi_explicit_dir_char (bidi_char_at_pos (bidi_it
->bytepos
1435 + bidi_it
->ch_len
, s
,
1436 bidi_it
->string
.unibyte
)))
1438 /* Avoid pushing and popping embedding levels if the level run
1439 is empty, as this breaks level runs where it shouldn't.
1440 UAX#9 removes all the explicit embedding and override codes,
1441 so empty embeddings disappear without a trace. We need to
1442 behave as if we did the same. */
1443 struct bidi_it saved_it
;
1444 int level
= prev_level
;
1446 bidi_copy_it (&saved_it
, bidi_it
);
1448 while (bidi_explicit_dir_char (bidi_char_at_pos (bidi_it
->bytepos
1449 + bidi_it
->ch_len
, s
,
1450 bidi_it
->string
.unibyte
)))
1452 /* This advances to the next character, skipping any
1453 characters covered by display strings. */
1454 level
= bidi_resolve_explicit_1 (bidi_it
);
1455 /* If string.lstring was relocated inside bidi_resolve_explicit_1,
1456 a pointer to its data is no longer valid. */
1457 if (STRINGP (bidi_it
->string
.lstring
))
1458 s
= SDATA (bidi_it
->string
.lstring
);
1461 if (bidi_it
->nchars
<= 0)
1463 if (level
== prev_level
) /* empty embedding */
1464 saved_it
.ignore_bn_limit
= bidi_it
->charpos
+ bidi_it
->nchars
;
1465 else /* this embedding is non-empty */
1466 saved_it
.ignore_bn_limit
= -2;
1468 bidi_copy_it (bidi_it
, &saved_it
);
1469 if (bidi_it
->ignore_bn_limit
> -1)
1471 /* We pushed a level, but we shouldn't have. Undo that. */
1472 if (!bidi_it
->invalid_rl_levels
)
1474 new_level
= bidi_pop_embedding_level (bidi_it
);
1475 bidi_it
->invalid_rl_levels
= -1;
1476 if (bidi_it
->invalid_levels
)
1477 bidi_it
->invalid_levels
--;
1479 if (!bidi_it
->invalid_levels
)
1480 new_level
= bidi_pop_embedding_level (bidi_it
);
1483 bidi_it
->invalid_levels
--;
1484 bidi_it
->invalid_rl_levels
--;
1489 if (bidi_it
->type
== NEUTRAL_B
) /* X8 */
1491 bidi_set_paragraph_end (bidi_it
);
1492 /* This is needed by bidi_resolve_weak below, and in L1. */
1493 bidi_it
->type_after_w1
= bidi_it
->type
;
1494 bidi_check_type (bidi_it
->type_after_w1
);
1500 /* Advance in the buffer/string, resolve weak types and return the
1501 type of the next character after weak type resolution. */
1503 bidi_resolve_weak (struct bidi_it
*bidi_it
)
1506 bidi_dir_t override
;
1507 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1508 int new_level
= bidi_resolve_explicit (bidi_it
);
1510 bidi_type_t type_of_next
;
1511 struct bidi_it saved_it
;
1513 (STRINGP (bidi_it
->string
.lstring
) || bidi_it
->string
.s
)
1514 ? bidi_it
->string
.schars
: ZV
;
1516 type
= bidi_it
->type
;
1517 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1519 if (type
== UNKNOWN_BT
1527 if (new_level
!= prev_level
1528 || bidi_it
->type
== NEUTRAL_B
)
1530 /* We've got a new embedding level run, compute the directional
1531 type of sor and initialize per-run variables (UAX#9, clause
1533 bidi_set_sor_type (bidi_it
, prev_level
, new_level
);
1535 else if (type
== NEUTRAL_S
|| type
== NEUTRAL_WS
1536 || type
== WEAK_BN
|| type
== STRONG_AL
)
1537 bidi_it
->type_after_w1
= type
; /* needed in L1 */
1538 bidi_check_type (bidi_it
->type_after_w1
);
1540 /* Level and directional override status are already recorded in
1541 bidi_it, and do not need any change; see X6. */
1542 if (override
== R2L
) /* X6 */
1544 else if (override
== L2R
)
1548 if (type
== WEAK_NSM
) /* W1 */
1550 /* Note that we don't need to consider the case where the
1551 prev character has its type overridden by an RLO or LRO,
1552 because then either the type of this NSM would have been
1553 also overridden, or the previous character is outside the
1554 current level run, and thus not relevant to this NSM.
1555 This is why NSM gets the type_after_w1 of the previous
1557 if (bidi_it
->prev
.type_after_w1
!= UNKNOWN_BT
1558 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1559 && bidi_it
->prev
.type_after_w1
!= NEUTRAL_B
)
1560 type
= bidi_it
->prev
.type_after_w1
;
1561 else if (bidi_it
->sor
== R2L
)
1563 else if (bidi_it
->sor
== L2R
)
1565 else /* shouldn't happen! */
1568 if (type
== WEAK_EN
/* W2 */
1569 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1571 else if (type
== STRONG_AL
) /* W3 */
1573 else if ((type
== WEAK_ES
/* W4 */
1574 && bidi_it
->prev
.type_after_w1
== WEAK_EN
1575 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1577 && ((bidi_it
->prev
.type_after_w1
== WEAK_EN
1578 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1579 || bidi_it
->prev
.type_after_w1
== WEAK_AN
)))
1581 const unsigned char *s
=
1582 STRINGP (bidi_it
->string
.lstring
)
1583 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1586 bidi_it
->charpos
+ bidi_it
->nchars
>= eob
1588 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
, s
,
1589 bidi_it
->string
.unibyte
);
1590 type_of_next
= bidi_get_type (next_char
, override
);
1592 if (type_of_next
== WEAK_BN
1593 || bidi_explicit_dir_char (next_char
))
1595 bidi_copy_it (&saved_it
, bidi_it
);
1596 while (bidi_resolve_explicit (bidi_it
) == new_level
1597 && bidi_it
->type
== WEAK_BN
)
1599 type_of_next
= bidi_it
->type
;
1600 bidi_copy_it (bidi_it
, &saved_it
);
1603 /* If the next character is EN, but the last strong-type
1604 character is AL, that next EN will be changed to AN when
1605 we process it in W2 above. So in that case, this ES
1606 should not be changed into EN. */
1608 && type_of_next
== WEAK_EN
1609 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1611 else if (type
== WEAK_CS
)
1613 if (bidi_it
->prev
.type_after_w1
== WEAK_AN
1614 && (type_of_next
== WEAK_AN
1615 /* If the next character is EN, but the last
1616 strong-type character is AL, EN will be later
1617 changed to AN when we process it in W2 above.
1618 So in that case, this ES should not be
1620 || (type_of_next
== WEAK_EN
1621 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)))
1623 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
1624 && type_of_next
== WEAK_EN
1625 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1629 else if (type
== WEAK_ET
/* W5: ET with EN before or after it */
1630 || type
== WEAK_BN
) /* W5/Retaining */
1632 if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* ET/BN w/EN before it */
1633 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1635 else /* W5: ET/BN with EN after it. */
1637 EMACS_INT en_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
1638 const unsigned char *s
=
1639 STRINGP (bidi_it
->string
.lstring
)
1640 ? SDATA (bidi_it
->string
.lstring
) : bidi_it
->string
.s
;
1642 if (bidi_it
->nchars
<= 0)
1645 bidi_it
->charpos
+ bidi_it
->nchars
>= eob
1647 : bidi_char_at_pos (bidi_it
->bytepos
+ bidi_it
->ch_len
, s
,
1648 bidi_it
->string
.unibyte
);
1649 type_of_next
= bidi_get_type (next_char
, override
);
1651 if (type_of_next
== WEAK_ET
1652 || type_of_next
== WEAK_BN
1653 || bidi_explicit_dir_char (next_char
))
1655 bidi_copy_it (&saved_it
, bidi_it
);
1656 while (bidi_resolve_explicit (bidi_it
) == new_level
1657 && (bidi_it
->type
== WEAK_BN
1658 || bidi_it
->type
== WEAK_ET
))
1660 type_of_next
= bidi_it
->type
;
1661 en_pos
= bidi_it
->charpos
;
1662 bidi_copy_it (bidi_it
, &saved_it
);
1664 if (type_of_next
== WEAK_EN
)
1666 /* If the last strong character is AL, the EN we've
1667 found will become AN when we get to it (W2). */
1668 if (bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1671 /* Remember this EN position, to speed up processing
1673 bidi_it
->next_en_pos
= en_pos
;
1675 else if (type
== WEAK_BN
)
1676 type
= NEUTRAL_ON
; /* W6/Retaining */
1682 if (type
== WEAK_ES
|| type
== WEAK_ET
|| type
== WEAK_CS
/* W6 */
1684 && (bidi_it
->prev
.type_after_w1
== WEAK_CS
/* W6/Retaining */
1685 || bidi_it
->prev
.type_after_w1
== WEAK_ES
1686 || bidi_it
->prev
.type_after_w1
== WEAK_ET
)))
1689 /* Store the type we've got so far, before we clobber it with strong
1690 types in W7 and while resolving neutral types. But leave alone
1691 the original types that were recorded above, because we will need
1692 them for the L1 clause. */
1693 if (bidi_it
->type_after_w1
== UNKNOWN_BT
)
1694 bidi_it
->type_after_w1
= type
;
1695 bidi_check_type (bidi_it
->type_after_w1
);
1697 if (type
== WEAK_EN
) /* W7 */
1699 if ((bidi_it
->last_strong
.type_after_w1
== STRONG_L
)
1700 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
&& bidi_it
->sor
== L2R
))
1704 bidi_it
->type
= type
;
1705 bidi_check_type (bidi_it
->type
);
1709 /* Resolve the type of a neutral character according to the type of
1710 surrounding strong text and the current embedding level. */
1711 static inline bidi_type_t
1712 bidi_resolve_neutral_1 (bidi_type_t prev_type
, bidi_type_t next_type
, int lev
)
1714 /* N1: European and Arabic numbers are treated as though they were R. */
1715 if (next_type
== WEAK_EN
|| next_type
== WEAK_AN
)
1716 next_type
= STRONG_R
;
1717 if (prev_type
== WEAK_EN
|| prev_type
== WEAK_AN
)
1718 prev_type
= STRONG_R
;
1720 if (next_type
== prev_type
) /* N1 */
1722 else if ((lev
& 1) == 0) /* N2 */
1729 bidi_resolve_neutral (struct bidi_it
*bidi_it
)
1731 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1732 bidi_type_t type
= bidi_resolve_weak (bidi_it
);
1733 int current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1735 if (!(type
== STRONG_R
1740 || type
== NEUTRAL_B
1741 || type
== NEUTRAL_S
1742 || type
== NEUTRAL_WS
1743 || type
== NEUTRAL_ON
))
1746 if (bidi_get_category (type
) == NEUTRAL
1747 || (type
== WEAK_BN
&& prev_level
== current_level
))
1749 if (bidi_it
->next_for_neutral
.type
!= UNKNOWN_BT
)
1750 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1751 bidi_it
->next_for_neutral
.type
,
1755 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1756 the assumption of batch-style processing; see clauses W4,
1757 W5, and especially N1, which require to look far forward
1758 (as well as back) in the buffer/string. May the fleas of
1759 a thousand camels infest the armpits of those who design
1760 supposedly general-purpose algorithms by looking at their
1761 own implementations, and fail to consider other possible
1763 struct bidi_it saved_it
;
1764 bidi_type_t next_type
;
1766 if (bidi_it
->scan_dir
== -1)
1769 bidi_copy_it (&saved_it
, bidi_it
);
1770 /* Scan the text forward until we find the first non-neutral
1771 character, and then use that to resolve the neutral we
1772 are dealing with now. We also cache the scanned iterator
1773 states, to salvage some of the effort later. */
1774 bidi_cache_iterator_state (bidi_it
, 0);
1776 /* Record the info about the previous character, so that
1777 it will be cached below with this state. */
1778 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1779 && bidi_it
->type
!= WEAK_BN
)
1780 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1781 type
= bidi_resolve_weak (bidi_it
);
1782 /* Paragraph separators have their levels fully resolved
1783 at this point, so cache them as resolved. */
1784 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
);
1785 /* FIXME: implement L1 here, by testing for a newline and
1786 resetting the level for any sequence of whitespace
1787 characters adjacent to it. */
1788 } while (!(type
== NEUTRAL_B
1790 && bidi_get_category (type
) != NEUTRAL
)
1791 /* This is all per level run, so stop when we
1792 reach the end of this level run. */
1793 || bidi_it
->level_stack
[bidi_it
->stack_idx
].level
!=
1796 bidi_remember_char (&saved_it
.next_for_neutral
, bidi_it
);
1807 /* N1: ``European and Arabic numbers are treated as
1808 though they were R.'' */
1809 next_type
= STRONG_R
;
1810 saved_it
.next_for_neutral
.type
= STRONG_R
;
1813 if (!bidi_explicit_dir_char (bidi_it
->ch
))
1814 abort (); /* can't happen: BNs are skipped */
1817 /* Marched all the way to the end of this level run.
1818 We need to use the eor type, whose information is
1819 stored by bidi_set_sor_type in the prev_for_neutral
1821 if (saved_it
.type
!= WEAK_BN
1822 || bidi_get_category (bidi_it
->prev
.type_after_w1
) == NEUTRAL
)
1824 next_type
= bidi_it
->prev_for_neutral
.type
;
1825 saved_it
.next_for_neutral
.type
= next_type
;
1826 bidi_check_type (next_type
);
1830 /* This is a BN which does not adjoin neutrals.
1831 Leave its type alone. */
1832 bidi_copy_it (bidi_it
, &saved_it
);
1833 return bidi_it
->type
;
1839 type
= bidi_resolve_neutral_1 (saved_it
.prev_for_neutral
.type
,
1840 next_type
, current_level
);
1841 saved_it
.type
= type
;
1842 bidi_check_type (type
);
1843 bidi_copy_it (bidi_it
, &saved_it
);
1849 /* Given an iterator state in BIDI_IT, advance one character position
1850 in the buffer/string to the next character (in the logical order),
1851 resolve the bidi type of that next character, and return that
1854 bidi_type_of_next_char (struct bidi_it
*bidi_it
)
1858 /* This should always be called during a forward scan. */
1859 if (bidi_it
->scan_dir
!= 1)
1862 /* Reset the limit until which to ignore BNs if we step out of the
1863 area where we found only empty levels. */
1864 if ((bidi_it
->ignore_bn_limit
> -1
1865 && bidi_it
->ignore_bn_limit
<= bidi_it
->charpos
)
1866 || (bidi_it
->ignore_bn_limit
== -2
1867 && !bidi_explicit_dir_char (bidi_it
->ch
)))
1868 bidi_it
->ignore_bn_limit
= -1;
1870 type
= bidi_resolve_neutral (bidi_it
);
1875 /* Given an iterator state BIDI_IT, advance one character position in
1876 the buffer/string to the next character (in the current scan
1877 direction), resolve the embedding and implicit levels of that next
1878 character, and return the resulting level. */
1880 bidi_level_of_next_char (struct bidi_it
*bidi_it
)
1883 int level
, prev_level
= -1;
1884 struct bidi_saved_info next_for_neutral
;
1885 EMACS_INT next_char_pos
= -2;
1887 if (bidi_it
->scan_dir
== 1)
1890 (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
1891 ? bidi_it
->string
.schars
: ZV
;
1893 /* There's no sense in trying to advance if we hit end of text. */
1894 if (bidi_it
->charpos
>= eob
)
1895 return bidi_it
->resolved_level
;
1897 /* Record the info about the previous character. */
1898 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1899 && bidi_it
->type
!= WEAK_BN
)
1900 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1901 if (bidi_it
->type_after_w1
== STRONG_R
1902 || bidi_it
->type_after_w1
== STRONG_L
1903 || bidi_it
->type_after_w1
== STRONG_AL
)
1904 bidi_remember_char (&bidi_it
->last_strong
, bidi_it
);
1905 /* FIXME: it sounds like we don't need both prev and
1906 prev_for_neutral members, but I'm leaving them both for now. */
1907 if (bidi_it
->type
== STRONG_R
|| bidi_it
->type
== STRONG_L
1908 || bidi_it
->type
== WEAK_EN
|| bidi_it
->type
== WEAK_AN
)
1909 bidi_remember_char (&bidi_it
->prev_for_neutral
, bidi_it
);
1911 /* If we overstepped the characters used for resolving neutrals
1912 and whitespace, invalidate their info in the iterator. */
1913 if (bidi_it
->charpos
>= bidi_it
->next_for_neutral
.charpos
)
1914 bidi_it
->next_for_neutral
.type
= UNKNOWN_BT
;
1915 if (bidi_it
->next_en_pos
>= 0
1916 && bidi_it
->charpos
>= bidi_it
->next_en_pos
)
1917 bidi_it
->next_en_pos
= -1;
1918 if (bidi_it
->next_for_ws
.type
!= UNKNOWN_BT
1919 && bidi_it
->charpos
>= bidi_it
->next_for_ws
.charpos
)
1920 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
1922 /* This must be taken before we fill the iterator with the info
1923 about the next char. If we scan backwards, the iterator
1924 state must be already cached, so there's no need to know the
1925 embedding level of the previous character, since we will be
1926 returning to our caller shortly. */
1927 prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1929 next_for_neutral
= bidi_it
->next_for_neutral
;
1931 /* Perhaps the character we want is already cached. If it is, the
1932 call to bidi_cache_find below will return a type other than
1934 if (bidi_cache_idx
> bidi_cache_start
&& !bidi_it
->first_elt
)
1937 (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
)) ? 0 : 1;
1939 if (bidi_it
->scan_dir
> 0)
1941 if (bidi_it
->nchars
<= 0)
1943 next_char_pos
= bidi_it
->charpos
+ bidi_it
->nchars
;
1945 else if (bidi_it
->charpos
>= bob
)
1946 /* Implementation note: we allow next_char_pos to be as low as
1947 0 for buffers or -1 for strings, and that is okay because
1948 that's the "position" of the sentinel iterator state we
1949 cached at the beginning of the iteration. */
1950 next_char_pos
= bidi_it
->charpos
- 1;
1951 if (next_char_pos
>= bob
- 1)
1952 type
= bidi_cache_find (next_char_pos
, -1, bidi_it
);
1958 if (type
!= UNKNOWN_BT
)
1960 /* Don't lose the information for resolving neutrals! The
1961 cached states could have been cached before their
1962 next_for_neutral member was computed. If we are on our way
1963 forward, we can simply take the info from the previous
1965 if (bidi_it
->scan_dir
== 1
1966 && bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1967 bidi_it
->next_for_neutral
= next_for_neutral
;
1969 /* If resolved_level is -1, it means this state was cached
1970 before it was completely resolved, so we cannot return
1972 if (bidi_it
->resolved_level
!= -1)
1973 return bidi_it
->resolved_level
;
1975 if (bidi_it
->scan_dir
== -1)
1976 /* If we are going backwards, the iterator state is already cached
1977 from previous scans, and should be fully resolved. */
1980 if (type
== UNKNOWN_BT
)
1981 type
= bidi_type_of_next_char (bidi_it
);
1983 if (type
== NEUTRAL_B
)
1984 return bidi_it
->resolved_level
;
1986 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1987 if ((bidi_get_category (type
) == NEUTRAL
/* && type != NEUTRAL_B */)
1988 || (type
== WEAK_BN
&& prev_level
== level
))
1990 if (bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1993 /* If the cached state shows a neutral character, it was not
1994 resolved by bidi_resolve_neutral, so do it now. */
1995 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1996 bidi_it
->next_for_neutral
.type
,
2000 if (!(type
== STRONG_R
2004 || type
== WEAK_AN
))
2006 bidi_it
->type
= type
;
2007 bidi_check_type (bidi_it
->type
);
2009 /* For L1 below, we need to know, for each WS character, whether
2010 it belongs to a sequence of WS characters preceding a newline
2011 or a TAB or a paragraph separator. */
2012 if (bidi_it
->orig_type
== NEUTRAL_WS
2013 && bidi_it
->next_for_ws
.type
== UNKNOWN_BT
)
2016 EMACS_INT clen
= bidi_it
->ch_len
;
2017 EMACS_INT bpos
= bidi_it
->bytepos
;
2018 EMACS_INT cpos
= bidi_it
->charpos
;
2019 EMACS_INT disp_pos
= bidi_it
->disp_pos
;
2020 EMACS_INT nc
= bidi_it
->nchars
;
2021 struct bidi_string_data bs
= bidi_it
->string
;
2023 int fwp
= bidi_it
->frame_window_p
;
2025 if (bidi_it
->nchars
<= 0)
2028 ch
= bidi_fetch_char (bpos
+= clen
, cpos
+= nc
, &disp_pos
, &bs
, fwp
,
2030 if (ch
== '\n' || ch
== BIDI_EOB
/* || ch == LINESEP_CHAR */)
2033 chtype
= bidi_get_type (ch
, NEUTRAL_DIR
);
2034 } while (chtype
== NEUTRAL_WS
|| chtype
== WEAK_BN
2035 || bidi_explicit_dir_char (ch
)); /* L1/Retaining */
2036 bidi_it
->next_for_ws
.type
= chtype
;
2037 bidi_check_type (bidi_it
->next_for_ws
.type
);
2038 bidi_it
->next_for_ws
.charpos
= cpos
;
2039 bidi_it
->next_for_ws
.bytepos
= bpos
;
2042 /* Resolve implicit levels, with a twist: PDFs get the embedding
2043 level of the enbedding they terminate. See below for the
2045 if (bidi_it
->orig_type
== PDF
2046 /* Don't do this if this formatting code didn't change the
2047 embedding level due to invalid or empty embeddings. */
2048 && prev_level
!= level
)
2050 /* Don't look in UAX#9 for the reason for this: it's our own
2051 private quirk. The reason is that we want the formatting
2052 codes to be delivered so that they bracket the text of their
2053 embedding. For example, given the text
2057 we want it to be displayed as
2065 which will result because we bump up the embedding level as
2066 soon as we see the RLO and pop it as soon as we see the PDF,
2067 so RLO itself has the same embedding level as "teST", and
2068 thus would be normally delivered last, just before the PDF.
2069 The switch below fiddles with the level of PDF so that this
2070 ugly side effect does not happen.
2072 (This is, of course, only important if the formatting codes
2073 are actually displayed, but Emacs does need to display them
2074 if the user wants to.) */
2077 else if (bidi_it
->orig_type
== NEUTRAL_B
/* L1 */
2078 || bidi_it
->orig_type
== NEUTRAL_S
2079 || bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
2080 /* || bidi_it->ch == LINESEP_CHAR */
2081 || (bidi_it
->orig_type
== NEUTRAL_WS
2082 && (bidi_it
->next_for_ws
.type
== NEUTRAL_B
2083 || bidi_it
->next_for_ws
.type
== NEUTRAL_S
)))
2084 level
= bidi_it
->level_stack
[0].level
;
2085 else if ((level
& 1) == 0) /* I1 */
2087 if (type
== STRONG_R
)
2089 else if (type
== WEAK_EN
|| type
== WEAK_AN
)
2094 if (type
== STRONG_L
|| type
== WEAK_EN
|| type
== WEAK_AN
)
2098 bidi_it
->resolved_level
= level
;
2102 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
2103 non-zero, we are at the end of a level, and we need to prepare to
2104 resume the scan of the lower level.
2106 If this level's other edge is cached, we simply jump to it, filling
2107 the iterator structure with the iterator state on the other edge.
2108 Otherwise, we walk the buffer or string until we come back to the
2109 same level as LEVEL.
2111 Note: we are not talking here about a ``level run'' in the UAX#9
2112 sense of the term, but rather about a ``level'' which includes
2113 all the levels higher than it. In other words, given the levels
2116 11111112222222333333334443343222222111111112223322111
2119 and assuming we are at point A scanning left to right, this
2120 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
2123 bidi_find_other_level_edge (struct bidi_it
*bidi_it
, int level
, int end_flag
)
2125 int dir
= end_flag
? -bidi_it
->scan_dir
: bidi_it
->scan_dir
;
2128 /* Try the cache first. */
2129 if ((idx
= bidi_cache_find_level_change (level
, dir
, end_flag
))
2130 >= bidi_cache_start
)
2131 bidi_cache_fetch_state (idx
, bidi_it
);
2137 abort (); /* if we are at end of level, its edges must be cached */
2139 bidi_cache_iterator_state (bidi_it
, 1);
2141 new_level
= bidi_level_of_next_char (bidi_it
);
2142 bidi_cache_iterator_state (bidi_it
, 1);
2143 } while (new_level
>= level
);
2148 bidi_move_to_visually_next (struct bidi_it
*bidi_it
)
2150 int old_level
, new_level
, next_level
;
2151 struct bidi_it sentinel
;
2152 struct gcpro gcpro1
;
2154 if (bidi_it
->charpos
< 0 || bidi_it
->bytepos
< 0)
2157 if (bidi_it
->scan_dir
== 0)
2159 bidi_it
->scan_dir
= 1; /* default to logical order */
2162 /* The code below can call eval, and thus cause GC. If we are
2163 iterating a Lisp string, make sure it won't be GCed. */
2164 if (STRINGP (bidi_it
->string
.lstring
))
2165 GCPRO1 (bidi_it
->string
.lstring
);
2167 /* If we just passed a newline, initialize for the next line. */
2168 if (!bidi_it
->first_elt
&& bidi_it
->orig_type
== NEUTRAL_B
)
2169 bidi_line_init (bidi_it
);
2171 /* Prepare the sentinel iterator state, and cache it. When we bump
2172 into it, scanning backwards, we'll know that the last non-base
2173 level is exhausted. */
2174 if (bidi_cache_idx
== bidi_cache_start
)
2176 bidi_copy_it (&sentinel
, bidi_it
);
2177 if (bidi_it
->first_elt
)
2179 sentinel
.charpos
--; /* cached charpos needs to be monotonic */
2181 sentinel
.ch
= '\n'; /* doesn't matter, but why not? */
2182 sentinel
.ch_len
= 1;
2183 sentinel
.nchars
= 1;
2185 bidi_cache_iterator_state (&sentinel
, 1);
2188 old_level
= bidi_it
->resolved_level
;
2189 new_level
= bidi_level_of_next_char (bidi_it
);
2191 /* Reordering of resolved levels (clause L2) is implemented by
2192 jumping to the other edge of the level and flipping direction of
2193 scanning the text whenever we find a level change. */
2194 if (new_level
!= old_level
)
2196 int ascending
= new_level
> old_level
;
2197 int level_to_search
= ascending
? old_level
+ 1 : old_level
;
2198 int incr
= ascending
? 1 : -1;
2199 int expected_next_level
= old_level
+ incr
;
2201 /* Jump (or walk) to the other edge of this level. */
2202 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
2203 /* Switch scan direction and peek at the next character in the
2205 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
2207 /* The following loop handles the case where the resolved level
2208 jumps by more than one. This is typical for numbers inside a
2209 run of text with left-to-right embedding direction, but can
2210 also happen in other situations. In those cases the decision
2211 where to continue after a level change, and in what direction,
2212 is tricky. For example, given a text like below:
2217 (where the numbers below the text show the resolved levels),
2218 the result of reordering according to UAX#9 should be this:
2222 This is implemented by the loop below which flips direction
2223 and jumps to the other edge of the level each time it finds
2224 the new level not to be the expected one. The expected level
2225 is always one more or one less than the previous one. */
2226 next_level
= bidi_peek_at_next_level (bidi_it
);
2227 while (next_level
!= expected_next_level
)
2229 expected_next_level
+= incr
;
2230 level_to_search
+= incr
;
2231 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
2232 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
2233 next_level
= bidi_peek_at_next_level (bidi_it
);
2236 /* Finally, deliver the next character in the new direction. */
2237 next_level
= bidi_level_of_next_char (bidi_it
);
2240 /* Take note when we have just processed the newline that precedes
2241 the end of the paragraph. The next time we are about to be
2242 called, set_iterator_to_next will automatically reinit the
2243 paragraph direction, if needed. We do this at the newline before
2244 the paragraph separator, because the next character might not be
2245 the first character of the next paragraph, due to the bidi
2246 reordering, whereas we _must_ know the paragraph base direction
2247 _before_ we process the paragraph's text, since the base
2248 direction affects the reordering. */
2249 if (bidi_it
->scan_dir
== 1 && bidi_it
->orig_type
== NEUTRAL_B
)
2251 /* The paragraph direction of the entire string, once
2252 determined, is in effect for the entire string. Setting the
2253 separator limit to the end of the string prevents
2254 bidi_paragraph_init from being called automatically on this
2256 if (bidi_it
->string
.s
|| STRINGP (bidi_it
->string
.lstring
))
2257 bidi_it
->separator_limit
= bidi_it
->string
.schars
;
2258 else if (bidi_it
->bytepos
< ZV_BYTE
)
2261 bidi_at_paragraph_end (bidi_it
->charpos
+ bidi_it
->nchars
,
2262 bidi_it
->bytepos
+ bidi_it
->ch_len
);
2263 if (bidi_it
->nchars
<= 0)
2267 bidi_it
->new_paragraph
= 1;
2268 /* Record the buffer position of the last character of the
2269 paragraph separator. */
2270 bidi_it
->separator_limit
=
2271 bidi_it
->charpos
+ bidi_it
->nchars
+ sep_len
;
2276 if (bidi_it
->scan_dir
== 1 && bidi_cache_idx
> bidi_cache_start
)
2278 /* If we are at paragraph's base embedding level and beyond the
2279 last cached position, the cache's job is done and we can
2281 if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
2282 && bidi_it
->charpos
> (bidi_cache
[bidi_cache_idx
- 1].charpos
2283 + bidi_cache
[bidi_cache_idx
- 1].nchars
- 1))
2284 bidi_cache_reset ();
2285 /* But as long as we are caching during forward scan, we must
2286 cache each state, or else the cache integrity will be
2287 compromised: it assumes cached states correspond to buffer
2290 bidi_cache_iterator_state (bidi_it
, 1);
2293 if (STRINGP (bidi_it
->string
.lstring
))
2297 /* This is meant to be called from within the debugger, whenever you
2298 wish to examine the cache contents. */
2299 void bidi_dump_cached_states (void) EXTERNALLY_VISIBLE
;
2301 bidi_dump_cached_states (void)
2306 if (bidi_cache_idx
== 0)
2308 fprintf (stderr
, "The cache is empty.\n");
2311 fprintf (stderr
, "Total of %"pD
"d state%s in cache:\n",
2312 bidi_cache_idx
, bidi_cache_idx
== 1 ? "" : "s");
2314 for (i
= bidi_cache
[bidi_cache_idx
- 1].charpos
; i
> 0; i
/= 10)
2316 fputs ("ch ", stderr
);
2317 for (i
= 0; i
< bidi_cache_idx
; i
++)
2318 fprintf (stderr
, "%*c", ndigits
, bidi_cache
[i
].ch
);
2319 fputs ("\n", stderr
);
2320 fputs ("lvl ", stderr
);
2321 for (i
= 0; i
< bidi_cache_idx
; i
++)
2322 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].resolved_level
);
2323 fputs ("\n", stderr
);
2324 fputs ("pos ", stderr
);
2325 for (i
= 0; i
< bidi_cache_idx
; i
++)
2326 fprintf (stderr
, "%*"pI
"d", ndigits
, bidi_cache
[i
].charpos
);
2327 fputs ("\n", stderr
);