lisp/emacs-lisp/cl-macs.el: Fix typos in docstrings.
[emacs.git] / src / bidi.c
blobc31d208ecbc8dbf5139ab7915522cc0e1a2b6291
1 /* Low-level bidirectional buffer/string-scanning functions for GNU Emacs.
2 Copyright (C) 2000-2001, 2004-2005, 2009-2013 Free Software
3 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
27 string.
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
41 argument character.
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
46 cache.
48 If you want to understand the code, you will have to read it
49 together with the relevant portions of UAX#9. The comments include
50 references to UAX#9 rules, for that very reason.
52 A note about references to UAX#9 rules: if the reference says
53 something like "X9/Retaining", it means that you need to refer to
54 rule X9 and to its modifications described in the "Implementation
55 Notes" section of UAX#9, under "Retaining Format Codes". */
57 #include <config.h>
58 #include <stdio.h>
60 #include "lisp.h"
61 #include "character.h"
62 #include "buffer.h"
63 #include "dispextern.h"
65 static bool bidi_initialized = 0;
67 static Lisp_Object bidi_type_table, bidi_mirror_table;
69 #define LRM_CHAR 0x200E
70 #define RLM_CHAR 0x200F
71 #define BIDI_EOB -1
73 /* Data type for describing the bidirectional character categories. */
74 typedef enum {
75 UNKNOWN_BC,
76 NEUTRAL,
77 WEAK,
78 STRONG
79 } bidi_category_t;
81 /* UAX#9 says to search only for L, AL, or R types of characters, and
82 ignore RLE, RLO, LRE, and LRO, when determining the base paragraph
83 level. Yudit indeed ignores them. This variable is therefore set
84 by default to ignore them, but clearing it will take them into
85 account. */
86 extern bool bidi_ignore_explicit_marks_for_paragraph_level EXTERNALLY_VISIBLE;
87 bool bidi_ignore_explicit_marks_for_paragraph_level = 1;
89 static Lisp_Object paragraph_start_re, paragraph_separate_re;
90 static Lisp_Object Qparagraph_start, Qparagraph_separate;
93 /***********************************************************************
94 Utilities
95 ***********************************************************************/
97 /* Return the bidi type of a character CH, subject to the current
98 directional OVERRIDE. */
99 static bidi_type_t
100 bidi_get_type (int ch, bidi_dir_t override)
102 bidi_type_t default_type;
104 if (ch == BIDI_EOB)
105 return NEUTRAL_B;
106 if (ch < 0 || ch > MAX_CHAR)
107 emacs_abort ();
109 default_type = (bidi_type_t) XINT (CHAR_TABLE_REF (bidi_type_table, ch));
110 /* Every valid character code, even those that are unassigned by the
111 UCD, have some bidi-class property, according to
112 DerivedBidiClass.txt file. Therefore, if we ever get UNKNOWN_BT
113 (= zero) code from CHAR_TABLE_REF, that's a bug. */
114 if (default_type == UNKNOWN_BT)
115 emacs_abort ();
117 if (override == NEUTRAL_DIR)
118 return default_type;
120 switch (default_type)
122 /* Although UAX#9 does not tell, it doesn't make sense to
123 override NEUTRAL_B and LRM/RLM characters. */
124 case NEUTRAL_B:
125 case LRE:
126 case LRO:
127 case RLE:
128 case RLO:
129 case PDF:
130 return default_type;
131 default:
132 switch (ch)
134 case LRM_CHAR:
135 case RLM_CHAR:
136 return default_type;
137 default:
138 if (override == L2R) /* X6 */
139 return STRONG_L;
140 else if (override == R2L)
141 return STRONG_R;
142 else
143 emacs_abort (); /* can't happen: handled above */
148 static void
149 bidi_check_type (bidi_type_t type)
151 eassert (UNKNOWN_BT <= type && type <= NEUTRAL_ON);
154 /* Given a bidi TYPE of a character, return its category. */
155 static bidi_category_t
156 bidi_get_category (bidi_type_t type)
158 switch (type)
160 case UNKNOWN_BT:
161 return UNKNOWN_BC;
162 case STRONG_L:
163 case STRONG_R:
164 case STRONG_AL:
165 case LRE:
166 case LRO:
167 case RLE:
168 case RLO:
169 return STRONG;
170 case PDF: /* ??? really?? */
171 case WEAK_EN:
172 case WEAK_ES:
173 case WEAK_ET:
174 case WEAK_AN:
175 case WEAK_CS:
176 case WEAK_NSM:
177 case WEAK_BN:
178 return WEAK;
179 case NEUTRAL_B:
180 case NEUTRAL_S:
181 case NEUTRAL_WS:
182 case NEUTRAL_ON:
183 return NEUTRAL;
184 default:
185 emacs_abort ();
189 /* Return the mirrored character of C, if it has one. If C has no
190 mirrored counterpart, return C.
191 Note: The conditions in UAX#9 clause L4 regarding the surrounding
192 context must be tested by the caller. */
194 bidi_mirror_char (int c)
196 Lisp_Object val;
198 if (c == BIDI_EOB)
199 return c;
200 if (c < 0 || c > MAX_CHAR)
201 emacs_abort ();
203 val = CHAR_TABLE_REF (bidi_mirror_table, c);
204 if (INTEGERP (val))
206 int v;
208 /* When debugging, check before assigning to V, so that the check
209 isn't broken by undefined behavior due to int overflow. */
210 eassert (CHAR_VALID_P (XINT (val)));
212 v = XINT (val);
214 /* Minimal test we must do in optimized builds, to prevent weird
215 crashes further down the road. */
216 if (v < 0 || v > MAX_CHAR)
217 emacs_abort ();
219 return v;
222 return c;
225 /* Determine the start-of-run (sor) directional type given the two
226 embedding levels on either side of the run boundary. Also, update
227 the saved info about previously seen characters, since that info is
228 generally valid for a single level run. */
229 static void
230 bidi_set_sor_type (struct bidi_it *bidi_it, int level_before, int level_after)
232 int higher_level = (level_before > level_after ? level_before : level_after);
234 /* The prev_was_pdf gork is required for when we have several PDFs
235 in a row. In that case, we want to compute the sor type for the
236 next level run only once: when we see the first PDF. That's
237 because the sor type depends only on the higher of the two levels
238 that we find on the two sides of the level boundary (see UAX#9,
239 clause X10), and so we don't need to know the final embedding
240 level to which we descend after processing all the PDFs. */
241 if (!bidi_it->prev_was_pdf || level_before < level_after)
242 /* FIXME: should the default sor direction be user selectable? */
243 bidi_it->sor = ((higher_level & 1) != 0 ? R2L : L2R);
244 if (level_before > level_after)
245 bidi_it->prev_was_pdf = 1;
247 bidi_it->prev.type = UNKNOWN_BT;
248 bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1
249 = bidi_it->last_strong.orig_type = UNKNOWN_BT;
250 bidi_it->prev_for_neutral.type = (bidi_it->sor == R2L ? STRONG_R : STRONG_L);
251 bidi_it->prev_for_neutral.charpos = bidi_it->charpos;
252 bidi_it->prev_for_neutral.bytepos = bidi_it->bytepos;
253 bidi_it->next_for_neutral.type = bidi_it->next_for_neutral.type_after_w1
254 = bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
255 bidi_it->ignore_bn_limit = -1; /* meaning it's unknown */
258 /* Push the current embedding level and override status; reset the
259 current level to LEVEL and the current override status to OVERRIDE. */
260 static void
261 bidi_push_embedding_level (struct bidi_it *bidi_it,
262 int level, bidi_dir_t override)
264 bidi_it->stack_idx++;
265 eassert (bidi_it->stack_idx < BIDI_MAXLEVEL);
266 bidi_it->level_stack[bidi_it->stack_idx].level = level;
267 bidi_it->level_stack[bidi_it->stack_idx].override = override;
270 /* Pop the embedding level and directional override status from the
271 stack, and return the new level. */
272 static int
273 bidi_pop_embedding_level (struct bidi_it *bidi_it)
275 /* UAX#9 says to ignore invalid PDFs. */
276 if (bidi_it->stack_idx > 0)
277 bidi_it->stack_idx--;
278 return bidi_it->level_stack[bidi_it->stack_idx].level;
281 /* Record in SAVED_INFO the information about the current character. */
282 static void
283 bidi_remember_char (struct bidi_saved_info *saved_info,
284 struct bidi_it *bidi_it)
286 saved_info->charpos = bidi_it->charpos;
287 saved_info->bytepos = bidi_it->bytepos;
288 saved_info->type = bidi_it->type;
289 bidi_check_type (bidi_it->type);
290 saved_info->type_after_w1 = bidi_it->type_after_w1;
291 bidi_check_type (bidi_it->type_after_w1);
292 saved_info->orig_type = bidi_it->orig_type;
293 bidi_check_type (bidi_it->orig_type);
296 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
297 copies the part of the level stack that is actually in use. */
298 static void
299 bidi_copy_it (struct bidi_it *to, struct bidi_it *from)
301 /* Copy everything from the start through the active part of
302 the level stack. */
303 memcpy (to, from,
304 (offsetof (struct bidi_it, level_stack[1])
305 + from->stack_idx * sizeof from->level_stack[0]));
309 /***********************************************************************
310 Caching the bidi iterator states
311 ***********************************************************************/
313 #define BIDI_CACHE_CHUNK 200
314 static struct bidi_it *bidi_cache;
315 static ptrdiff_t bidi_cache_size = 0;
316 enum { elsz = sizeof (struct bidi_it) };
317 static ptrdiff_t bidi_cache_idx; /* next unused cache slot */
318 static ptrdiff_t bidi_cache_last_idx; /* slot of last cache hit */
319 static ptrdiff_t bidi_cache_start = 0; /* start of cache for this
320 "stack" level */
322 /* 5-slot stack for saving the start of the previous level of the
323 cache. xdisp.c maintains a 5-slot stack for its iterator state,
324 and we need the same size of our stack. */
325 static ptrdiff_t bidi_cache_start_stack[IT_STACK_SIZE];
326 static int bidi_cache_sp;
328 /* Size of header used by bidi_shelve_cache. */
329 enum
331 bidi_shelve_header_size
332 = (sizeof (bidi_cache_idx) + sizeof (bidi_cache_start_stack)
333 + sizeof (bidi_cache_sp) + sizeof (bidi_cache_start)
334 + sizeof (bidi_cache_last_idx))
337 /* Reset the cache state to the empty state. We only reset the part
338 of the cache relevant to iteration of the current object. Previous
339 objects, which are pushed on the display iterator's stack, are left
340 intact. This is called when the cached information is no more
341 useful for the current iteration, e.g. when we were reseated to a
342 new position on the same object. */
343 static void
344 bidi_cache_reset (void)
346 bidi_cache_idx = bidi_cache_start;
347 bidi_cache_last_idx = -1;
350 /* Shrink the cache to its minimal size. Called when we init the bidi
351 iterator for reordering a buffer or a string that does not come
352 from display properties, because that means all the previously
353 cached info is of no further use. */
354 static void
355 bidi_cache_shrink (void)
357 if (bidi_cache_size > BIDI_CACHE_CHUNK)
359 bidi_cache = xrealloc (bidi_cache, BIDI_CACHE_CHUNK * elsz);
360 bidi_cache_size = BIDI_CACHE_CHUNK;
362 bidi_cache_reset ();
365 static void
366 bidi_cache_fetch_state (ptrdiff_t idx, struct bidi_it *bidi_it)
368 int current_scan_dir = bidi_it->scan_dir;
370 if (idx < bidi_cache_start || idx >= bidi_cache_idx)
371 emacs_abort ();
373 bidi_copy_it (bidi_it, &bidi_cache[idx]);
374 bidi_it->scan_dir = current_scan_dir;
375 bidi_cache_last_idx = idx;
378 /* Find a cached state with a given CHARPOS and resolved embedding
379 level less or equal to LEVEL. if LEVEL is -1, disregard the
380 resolved levels in cached states. DIR, if non-zero, means search
381 in that direction from the last cache hit. */
382 static ptrdiff_t
383 bidi_cache_search (ptrdiff_t charpos, int level, int dir)
385 ptrdiff_t i, i_start;
387 if (bidi_cache_idx > bidi_cache_start)
389 if (bidi_cache_last_idx == -1)
390 bidi_cache_last_idx = bidi_cache_idx - 1;
391 if (charpos < bidi_cache[bidi_cache_last_idx].charpos)
393 dir = -1;
394 i_start = bidi_cache_last_idx - 1;
396 else if (charpos > (bidi_cache[bidi_cache_last_idx].charpos
397 + bidi_cache[bidi_cache_last_idx].nchars - 1))
399 dir = 1;
400 i_start = bidi_cache_last_idx + 1;
402 else if (dir)
403 i_start = bidi_cache_last_idx;
404 else
406 dir = -1;
407 i_start = bidi_cache_idx - 1;
410 if (dir < 0)
412 /* Linear search for now; FIXME! */
413 for (i = i_start; i >= bidi_cache_start; i--)
414 if (bidi_cache[i].charpos <= charpos
415 && charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
416 && (level == -1 || bidi_cache[i].resolved_level <= level))
417 return i;
419 else
421 for (i = i_start; i < bidi_cache_idx; i++)
422 if (bidi_cache[i].charpos <= charpos
423 && charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
424 && (level == -1 || bidi_cache[i].resolved_level <= level))
425 return i;
429 return -1;
432 /* Find a cached state where the resolved level changes to a value
433 that is lower than LEVEL, and return its cache slot index. DIR is
434 the direction to search, starting with the last used cache slot.
435 If DIR is zero, we search backwards from the last occupied cache
436 slot. BEFORE means return the index of the slot that
437 is ``before'' the level change in the search direction. That is,
438 given the cached levels like this:
440 1122333442211
441 AB C
443 and assuming we are at the position cached at the slot marked with
444 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
445 index of slot B or A, depending whether BEFORE is, respectively,
446 true or false. */
447 static ptrdiff_t
448 bidi_cache_find_level_change (int level, int dir, bool before)
450 if (bidi_cache_idx)
452 ptrdiff_t i = dir ? bidi_cache_last_idx : bidi_cache_idx - 1;
453 int incr = before ? 1 : 0;
455 eassert (!dir || bidi_cache_last_idx >= 0);
457 if (!dir)
458 dir = -1;
459 else if (!incr)
460 i += dir;
462 if (dir < 0)
464 while (i >= bidi_cache_start + incr)
466 if (bidi_cache[i - incr].resolved_level >= 0
467 && bidi_cache[i - incr].resolved_level < level)
468 return i;
469 i--;
472 else
474 while (i < bidi_cache_idx - incr)
476 if (bidi_cache[i + incr].resolved_level >= 0
477 && bidi_cache[i + incr].resolved_level < level)
478 return i;
479 i++;
484 return -1;
487 static void
488 bidi_cache_ensure_space (ptrdiff_t idx)
490 /* Enlarge the cache as needed. */
491 if (idx >= bidi_cache_size)
493 /* The bidi cache cannot be larger than the largest Lisp string
494 or buffer. */
495 ptrdiff_t string_or_buffer_bound
496 = max (BUF_BYTES_MAX, STRING_BYTES_BOUND);
498 /* Also, it cannot be larger than what C can represent. */
499 ptrdiff_t c_bound
500 = (min (PTRDIFF_MAX, SIZE_MAX) - bidi_shelve_header_size) / elsz;
502 bidi_cache
503 = xpalloc (bidi_cache, &bidi_cache_size,
504 max (BIDI_CACHE_CHUNK, idx - bidi_cache_size + 1),
505 min (string_or_buffer_bound, c_bound), elsz);
509 static void
510 bidi_cache_iterator_state (struct bidi_it *bidi_it, bool resolved)
512 ptrdiff_t idx;
514 /* We should never cache on backward scans. */
515 if (bidi_it->scan_dir == -1)
516 emacs_abort ();
517 idx = bidi_cache_search (bidi_it->charpos, -1, 1);
519 if (idx < 0)
521 idx = bidi_cache_idx;
522 bidi_cache_ensure_space (idx);
523 /* Character positions should correspond to cache positions 1:1.
524 If we are outside the range of cached positions, the cache is
525 useless and must be reset. */
526 if (idx > bidi_cache_start &&
527 (bidi_it->charpos > (bidi_cache[idx - 1].charpos
528 + bidi_cache[idx - 1].nchars)
529 || bidi_it->charpos < bidi_cache[bidi_cache_start].charpos))
531 bidi_cache_reset ();
532 idx = bidi_cache_start;
534 if (bidi_it->nchars <= 0)
535 emacs_abort ();
536 bidi_copy_it (&bidi_cache[idx], bidi_it);
537 if (!resolved)
538 bidi_cache[idx].resolved_level = -1;
540 else
542 /* Copy only the members which could have changed, to avoid
543 costly copying of the entire struct. */
544 bidi_cache[idx].type = bidi_it->type;
545 bidi_check_type (bidi_it->type);
546 bidi_cache[idx].type_after_w1 = bidi_it->type_after_w1;
547 bidi_check_type (bidi_it->type_after_w1);
548 if (resolved)
549 bidi_cache[idx].resolved_level = bidi_it->resolved_level;
550 else
551 bidi_cache[idx].resolved_level = -1;
552 bidi_cache[idx].invalid_levels = bidi_it->invalid_levels;
553 bidi_cache[idx].invalid_rl_levels = bidi_it->invalid_rl_levels;
554 bidi_cache[idx].next_for_neutral = bidi_it->next_for_neutral;
555 bidi_cache[idx].next_for_ws = bidi_it->next_for_ws;
556 bidi_cache[idx].ignore_bn_limit = bidi_it->ignore_bn_limit;
557 bidi_cache[idx].disp_pos = bidi_it->disp_pos;
558 bidi_cache[idx].disp_prop = bidi_it->disp_prop;
561 bidi_cache_last_idx = idx;
562 if (idx >= bidi_cache_idx)
563 bidi_cache_idx = idx + 1;
566 static bidi_type_t
567 bidi_cache_find (ptrdiff_t charpos, int level, struct bidi_it *bidi_it)
569 ptrdiff_t i = bidi_cache_search (charpos, level, bidi_it->scan_dir);
571 if (i >= bidi_cache_start)
573 bidi_dir_t current_scan_dir = bidi_it->scan_dir;
575 bidi_copy_it (bidi_it, &bidi_cache[i]);
576 bidi_cache_last_idx = i;
577 /* Don't let scan direction from the cached state override
578 the current scan direction. */
579 bidi_it->scan_dir = current_scan_dir;
580 return bidi_it->type;
583 return UNKNOWN_BT;
586 static int
587 bidi_peek_at_next_level (struct bidi_it *bidi_it)
589 if (bidi_cache_idx == bidi_cache_start || bidi_cache_last_idx == -1)
590 emacs_abort ();
591 return bidi_cache[bidi_cache_last_idx + bidi_it->scan_dir].resolved_level;
595 /***********************************************************************
596 Pushing and popping the bidi iterator state
597 ***********************************************************************/
599 /* Push the bidi iterator state in preparation for reordering a
600 different object, e.g. display string found at certain buffer
601 position. Pushing the bidi iterator boils down to saving its
602 entire state on the cache and starting a new cache "stacked" on top
603 of the current cache. */
604 void
605 bidi_push_it (struct bidi_it *bidi_it)
607 /* Save the current iterator state in its entirety after the last
608 used cache slot. */
609 bidi_cache_ensure_space (bidi_cache_idx);
610 bidi_cache[bidi_cache_idx++] = *bidi_it;
612 /* Push the current cache start onto the stack. */
613 eassert (bidi_cache_sp < IT_STACK_SIZE);
614 bidi_cache_start_stack[bidi_cache_sp++] = bidi_cache_start;
616 /* Start a new level of cache, and make it empty. */
617 bidi_cache_start = bidi_cache_idx;
618 bidi_cache_last_idx = -1;
621 /* Restore the iterator state saved by bidi_push_it and return the
622 cache to the corresponding state. */
623 void
624 bidi_pop_it (struct bidi_it *bidi_it)
626 if (bidi_cache_start <= 0)
627 emacs_abort ();
629 /* Reset the next free cache slot index to what it was before the
630 call to bidi_push_it. */
631 bidi_cache_idx = bidi_cache_start - 1;
633 /* Restore the bidi iterator state saved in the cache. */
634 *bidi_it = bidi_cache[bidi_cache_idx];
636 /* Pop the previous cache start from the stack. */
637 if (bidi_cache_sp <= 0)
638 emacs_abort ();
639 bidi_cache_start = bidi_cache_start_stack[--bidi_cache_sp];
641 /* Invalidate the last-used cache slot data. */
642 bidi_cache_last_idx = -1;
645 static ptrdiff_t bidi_cache_total_alloc;
647 /* Stash away a copy of the cache and its control variables. */
648 void *
649 bidi_shelve_cache (void)
651 unsigned char *databuf;
652 ptrdiff_t alloc;
654 /* Empty cache. */
655 if (bidi_cache_idx == 0)
656 return NULL;
658 alloc = (bidi_shelve_header_size
659 + bidi_cache_idx * sizeof (struct bidi_it));
660 databuf = xmalloc (alloc);
661 bidi_cache_total_alloc += alloc;
663 memcpy (databuf, &bidi_cache_idx, sizeof (bidi_cache_idx));
664 memcpy (databuf + sizeof (bidi_cache_idx),
665 bidi_cache, bidi_cache_idx * sizeof (struct bidi_it));
666 memcpy (databuf + sizeof (bidi_cache_idx)
667 + bidi_cache_idx * sizeof (struct bidi_it),
668 bidi_cache_start_stack, sizeof (bidi_cache_start_stack));
669 memcpy (databuf + sizeof (bidi_cache_idx)
670 + bidi_cache_idx * sizeof (struct bidi_it)
671 + sizeof (bidi_cache_start_stack),
672 &bidi_cache_sp, sizeof (bidi_cache_sp));
673 memcpy (databuf + sizeof (bidi_cache_idx)
674 + bidi_cache_idx * sizeof (struct bidi_it)
675 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
676 &bidi_cache_start, sizeof (bidi_cache_start));
677 memcpy (databuf + sizeof (bidi_cache_idx)
678 + bidi_cache_idx * sizeof (struct bidi_it)
679 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
680 + sizeof (bidi_cache_start),
681 &bidi_cache_last_idx, sizeof (bidi_cache_last_idx));
683 return databuf;
686 /* Restore the cache state from a copy stashed away by
687 bidi_shelve_cache, and free the buffer used to stash that copy.
688 JUST_FREE means free the buffer, but don't restore the
689 cache; used when the corresponding iterator is discarded instead of
690 being restored. */
691 void
692 bidi_unshelve_cache (void *databuf, bool just_free)
694 unsigned char *p = databuf;
696 if (!p)
698 if (!just_free)
700 /* A NULL pointer means an empty cache. */
701 bidi_cache_start = 0;
702 bidi_cache_sp = 0;
703 bidi_cache_reset ();
706 else
708 if (just_free)
710 ptrdiff_t idx;
712 memcpy (&idx, p, sizeof (bidi_cache_idx));
713 bidi_cache_total_alloc
714 -= bidi_shelve_header_size + idx * sizeof (struct bidi_it);
716 else
718 memcpy (&bidi_cache_idx, p, sizeof (bidi_cache_idx));
719 bidi_cache_ensure_space (bidi_cache_idx);
720 memcpy (bidi_cache, p + sizeof (bidi_cache_idx),
721 bidi_cache_idx * sizeof (struct bidi_it));
722 memcpy (bidi_cache_start_stack,
723 p + sizeof (bidi_cache_idx)
724 + bidi_cache_idx * sizeof (struct bidi_it),
725 sizeof (bidi_cache_start_stack));
726 memcpy (&bidi_cache_sp,
727 p + sizeof (bidi_cache_idx)
728 + bidi_cache_idx * sizeof (struct bidi_it)
729 + sizeof (bidi_cache_start_stack),
730 sizeof (bidi_cache_sp));
731 memcpy (&bidi_cache_start,
732 p + sizeof (bidi_cache_idx)
733 + bidi_cache_idx * sizeof (struct bidi_it)
734 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
735 sizeof (bidi_cache_start));
736 memcpy (&bidi_cache_last_idx,
737 p + sizeof (bidi_cache_idx)
738 + bidi_cache_idx * sizeof (struct bidi_it)
739 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
740 + sizeof (bidi_cache_start),
741 sizeof (bidi_cache_last_idx));
742 bidi_cache_total_alloc
743 -= (bidi_shelve_header_size
744 + bidi_cache_idx * sizeof (struct bidi_it));
747 xfree (p);
752 /***********************************************************************
753 Initialization
754 ***********************************************************************/
755 static void
756 bidi_initialize (void)
758 bidi_type_table = uniprop_table (intern ("bidi-class"));
759 if (NILP (bidi_type_table))
760 emacs_abort ();
761 staticpro (&bidi_type_table);
763 bidi_mirror_table = uniprop_table (intern ("mirroring"));
764 if (NILP (bidi_mirror_table))
765 emacs_abort ();
766 staticpro (&bidi_mirror_table);
768 Qparagraph_start = intern ("paragraph-start");
769 staticpro (&Qparagraph_start);
770 paragraph_start_re = Fsymbol_value (Qparagraph_start);
771 if (!STRINGP (paragraph_start_re))
772 paragraph_start_re = build_string ("\f\\|[ \t]*$");
773 staticpro (&paragraph_start_re);
774 Qparagraph_separate = intern ("paragraph-separate");
775 staticpro (&Qparagraph_separate);
776 paragraph_separate_re = Fsymbol_value (Qparagraph_separate);
777 if (!STRINGP (paragraph_separate_re))
778 paragraph_separate_re = build_string ("[ \t\f]*$");
779 staticpro (&paragraph_separate_re);
781 bidi_cache_sp = 0;
782 bidi_cache_total_alloc = 0;
784 bidi_initialized = 1;
787 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
788 end. */
789 static void
790 bidi_set_paragraph_end (struct bidi_it *bidi_it)
792 bidi_it->invalid_levels = 0;
793 bidi_it->invalid_rl_levels = -1;
794 bidi_it->stack_idx = 0;
795 bidi_it->resolved_level = bidi_it->level_stack[0].level;
798 /* Initialize the bidi iterator from buffer/string position CHARPOS. */
799 void
800 bidi_init_it (ptrdiff_t charpos, ptrdiff_t bytepos, bool frame_window_p,
801 struct bidi_it *bidi_it)
803 if (! bidi_initialized)
804 bidi_initialize ();
805 if (charpos >= 0)
806 bidi_it->charpos = charpos;
807 if (bytepos >= 0)
808 bidi_it->bytepos = bytepos;
809 bidi_it->frame_window_p = frame_window_p;
810 bidi_it->nchars = -1; /* to be computed in bidi_resolve_explicit_1 */
811 bidi_it->first_elt = 1;
812 bidi_set_paragraph_end (bidi_it);
813 bidi_it->new_paragraph = 1;
814 bidi_it->separator_limit = -1;
815 bidi_it->type = NEUTRAL_B;
816 bidi_it->type_after_w1 = NEUTRAL_B;
817 bidi_it->orig_type = NEUTRAL_B;
818 bidi_it->prev_was_pdf = 0;
819 bidi_it->prev.type = bidi_it->prev.type_after_w1
820 = bidi_it->prev.orig_type = UNKNOWN_BT;
821 bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1
822 = bidi_it->last_strong.orig_type = UNKNOWN_BT;
823 bidi_it->next_for_neutral.charpos = -1;
824 bidi_it->next_for_neutral.type
825 = bidi_it->next_for_neutral.type_after_w1
826 = bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
827 bidi_it->prev_for_neutral.charpos = -1;
828 bidi_it->prev_for_neutral.type
829 = bidi_it->prev_for_neutral.type_after_w1
830 = bidi_it->prev_for_neutral.orig_type = UNKNOWN_BT;
831 bidi_it->sor = L2R; /* FIXME: should it be user-selectable? */
832 bidi_it->disp_pos = -1; /* invalid/unknown */
833 bidi_it->disp_prop = 0;
834 /* We can only shrink the cache if we are at the bottom level of its
835 "stack". */
836 if (bidi_cache_start == 0)
837 bidi_cache_shrink ();
838 else
839 bidi_cache_reset ();
842 /* Perform initializations for reordering a new line of bidi text. */
843 static void
844 bidi_line_init (struct bidi_it *bidi_it)
846 bidi_it->scan_dir = 1; /* FIXME: do we need to have control on this? */
847 bidi_it->resolved_level = bidi_it->level_stack[0].level;
848 bidi_it->level_stack[0].override = NEUTRAL_DIR; /* X1 */
849 bidi_it->invalid_levels = 0;
850 bidi_it->invalid_rl_levels = -1;
851 /* Setting this to zero will force its recomputation the first time
852 we need it for W5. */
853 bidi_it->next_en_pos = 0;
854 bidi_it->next_en_type = UNKNOWN_BT;
855 bidi_it->next_for_ws.type = UNKNOWN_BT;
856 bidi_set_sor_type (bidi_it,
857 (bidi_it->paragraph_dir == R2L ? 1 : 0),
858 bidi_it->level_stack[0].level); /* X10 */
860 bidi_cache_reset ();
864 /***********************************************************************
865 Fetching characters
866 ***********************************************************************/
868 /* Count bytes in string S between BEG/BEGBYTE and END. BEG and END
869 are zero-based character positions in S, BEGBYTE is byte position
870 corresponding to BEG. UNIBYTE means S is a unibyte string. */
871 static ptrdiff_t
872 bidi_count_bytes (const unsigned char *s, const ptrdiff_t beg,
873 const ptrdiff_t begbyte, const ptrdiff_t end, bool unibyte)
875 ptrdiff_t pos = beg;
876 const unsigned char *p = s + begbyte, *start = p;
878 if (unibyte)
879 p = s + end;
880 else
882 if (!CHAR_HEAD_P (*p))
883 emacs_abort ();
885 while (pos < end)
887 p += BYTES_BY_CHAR_HEAD (*p);
888 pos++;
892 return p - start;
895 /* Fetch and return the character at byte position BYTEPOS. If S is
896 non-NULL, fetch the character from string S; otherwise fetch the
897 character from the current buffer. UNIBYTE means S is a
898 unibyte string. */
899 static int
900 bidi_char_at_pos (ptrdiff_t bytepos, const unsigned char *s, bool unibyte)
902 if (s)
904 s += bytepos;
905 if (unibyte)
906 return *s;
908 else
909 s = BYTE_POS_ADDR (bytepos);
910 return STRING_CHAR (s);
913 /* Fetch and return the character at CHARPOS/BYTEPOS. If that
914 character is covered by a display string, treat the entire run of
915 covered characters as a single character, either u+2029 or u+FFFC,
916 and return their combined length in CH_LEN and NCHARS. DISP_POS
917 specifies the character position of the next display string, or -1
918 if not yet computed. When the next character is at or beyond that
919 position, the function updates DISP_POS with the position of the
920 next display string. *DISP_PROP non-zero means that there's really
921 a display string at DISP_POS, as opposed to when we searched till
922 DISP_POS without finding one. If *DISP_PROP is 2, it means the
923 display spec is of the form `(space ...)', which is replaced with
924 u+2029 to handle it as a paragraph separator. STRING->s is the C
925 string to iterate, or NULL if iterating over a buffer or a Lisp
926 string; in the latter case, STRING->lstring is the Lisp string. */
927 static int
928 bidi_fetch_char (ptrdiff_t charpos, ptrdiff_t bytepos, ptrdiff_t *disp_pos,
929 int *disp_prop, struct bidi_string_data *string,
930 struct window *w,
931 bool frame_window_p, ptrdiff_t *ch_len, ptrdiff_t *nchars)
933 int ch;
934 ptrdiff_t endpos
935 = (string->s || STRINGP (string->lstring)) ? string->schars : ZV;
936 struct text_pos pos;
937 int len;
939 /* If we got past the last known position of display string, compute
940 the position of the next one. That position could be at CHARPOS. */
941 if (charpos < endpos && charpos > *disp_pos)
943 SET_TEXT_POS (pos, charpos, bytepos);
944 *disp_pos = compute_display_string_pos (&pos, string, w, frame_window_p,
945 disp_prop);
948 /* Fetch the character at BYTEPOS. */
949 if (charpos >= endpos)
951 ch = BIDI_EOB;
952 *ch_len = 1;
953 *nchars = 1;
954 *disp_pos = endpos;
955 *disp_prop = 0;
957 else if (charpos >= *disp_pos && *disp_prop)
959 ptrdiff_t disp_end_pos;
961 /* We don't expect to find ourselves in the middle of a display
962 property. Hopefully, it will never be needed. */
963 if (charpos > *disp_pos)
964 emacs_abort ();
965 /* Text covered by `display' properties and overlays with
966 display properties or display strings is handled as a single
967 character that represents the entire run of characters
968 covered by the display property. */
969 if (*disp_prop == 2)
971 /* `(space ...)' display specs are handled as paragraph
972 separators for the purposes of the reordering; see UAX#9
973 section 3 and clause HL1 in section 4.3 there. */
974 ch = 0x2029;
976 else
978 /* All other display specs are handled as the Unicode Object
979 Replacement Character. */
980 ch = 0xFFFC;
982 disp_end_pos = compute_display_string_end (*disp_pos, string);
983 if (disp_end_pos < 0)
985 /* Somebody removed the display string from the buffer
986 behind our back. Recover by processing this buffer
987 position as if no display property were present there to
988 begin with. */
989 *disp_prop = 0;
990 goto normal_char;
992 *nchars = disp_end_pos - *disp_pos;
993 if (*nchars <= 0)
994 emacs_abort ();
995 if (string->s)
996 *ch_len = bidi_count_bytes (string->s, *disp_pos, bytepos,
997 disp_end_pos, string->unibyte);
998 else if (STRINGP (string->lstring))
999 *ch_len = bidi_count_bytes (SDATA (string->lstring), *disp_pos,
1000 bytepos, disp_end_pos, string->unibyte);
1001 else
1002 *ch_len = CHAR_TO_BYTE (disp_end_pos) - bytepos;
1004 else
1006 normal_char:
1007 if (string->s)
1010 if (!string->unibyte)
1012 ch = STRING_CHAR_AND_LENGTH (string->s + bytepos, len);
1013 *ch_len = len;
1015 else
1017 ch = UNIBYTE_TO_CHAR (string->s[bytepos]);
1018 *ch_len = 1;
1021 else if (STRINGP (string->lstring))
1023 if (!string->unibyte)
1025 ch = STRING_CHAR_AND_LENGTH (SDATA (string->lstring) + bytepos,
1026 len);
1027 *ch_len = len;
1029 else
1031 ch = UNIBYTE_TO_CHAR (SREF (string->lstring, bytepos));
1032 *ch_len = 1;
1035 else
1037 ch = STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (bytepos), len);
1038 *ch_len = len;
1040 *nchars = 1;
1043 /* If we just entered a run of characters covered by a display
1044 string, compute the position of the next display string. */
1045 if (charpos + *nchars <= endpos && charpos + *nchars > *disp_pos
1046 && *disp_prop)
1048 SET_TEXT_POS (pos, charpos + *nchars, bytepos + *ch_len);
1049 *disp_pos = compute_display_string_pos (&pos, string, w, frame_window_p,
1050 disp_prop);
1053 return ch;
1057 /***********************************************************************
1058 Determining paragraph direction
1059 ***********************************************************************/
1061 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
1062 Value is the non-negative length of the paragraph separator
1063 following the buffer position, -1 if position is at the beginning
1064 of a new paragraph, or -2 if position is neither at beginning nor
1065 at end of a paragraph. */
1066 static ptrdiff_t
1067 bidi_at_paragraph_end (ptrdiff_t charpos, ptrdiff_t bytepos)
1069 Lisp_Object sep_re;
1070 Lisp_Object start_re;
1071 ptrdiff_t val;
1073 sep_re = paragraph_separate_re;
1074 start_re = paragraph_start_re;
1076 val = fast_looking_at (sep_re, charpos, bytepos, ZV, ZV_BYTE, Qnil);
1077 if (val < 0)
1079 if (fast_looking_at (start_re, charpos, bytepos, ZV, ZV_BYTE, Qnil) >= 0)
1080 val = -1;
1081 else
1082 val = -2;
1085 return val;
1088 /* On my 2005-vintage machine, searching back for paragraph start
1089 takes ~1 ms per line. And bidi_paragraph_init is called 4 times
1090 when user types C-p. The number below limits each call to
1091 bidi_paragraph_init to about 10 ms. */
1092 #define MAX_PARAGRAPH_SEARCH 7500
1094 /* Find the beginning of this paragraph by looking back in the buffer.
1095 Value is the byte position of the paragraph's beginning, or
1096 BEGV_BYTE if paragraph_start_re is still not found after looking
1097 back MAX_PARAGRAPH_SEARCH lines in the buffer. */
1098 static ptrdiff_t
1099 bidi_find_paragraph_start (ptrdiff_t pos, ptrdiff_t pos_byte)
1101 Lisp_Object re = paragraph_start_re;
1102 ptrdiff_t limit = ZV, limit_byte = ZV_BYTE;
1103 ptrdiff_t n = 0;
1105 while (pos_byte > BEGV_BYTE
1106 && n++ < MAX_PARAGRAPH_SEARCH
1107 && fast_looking_at (re, pos, pos_byte, limit, limit_byte, Qnil) < 0)
1109 /* FIXME: What if the paragraph beginning is covered by a
1110 display string? And what if a display string covering some
1111 of the text over which we scan back includes
1112 paragraph_start_re? */
1113 DEC_BOTH (pos, pos_byte);
1114 pos = find_newline_no_quit (pos, pos_byte, -1, &pos_byte);
1116 if (n >= MAX_PARAGRAPH_SEARCH)
1117 pos_byte = BEGV_BYTE;
1118 return pos_byte;
1121 /* On a 3.4 GHz machine, searching forward for a strong directional
1122 character in a long paragraph full of weaks or neutrals takes about
1123 1 ms for each 20K characters. The number below limits each call to
1124 bidi_paragraph_init to less than 10 ms even on slow machines. */
1125 #define MAX_STRONG_CHAR_SEARCH 100000
1127 /* Determine the base direction, a.k.a. base embedding level, of the
1128 paragraph we are about to iterate through. If DIR is either L2R or
1129 R2L, just use that. Otherwise, determine the paragraph direction
1130 from the first strong directional character of the paragraph.
1132 NO_DEFAULT_P means don't default to L2R if the paragraph
1133 has no strong directional characters and both DIR and
1134 bidi_it->paragraph_dir are NEUTRAL_DIR. In that case, search back
1135 in the buffer until a paragraph is found with a strong character,
1136 or until hitting BEGV. In the latter case, fall back to L2R. This
1137 flag is used in current-bidi-paragraph-direction.
1139 Note that this function gives the paragraph separator the same
1140 direction as the preceding paragraph, even though Emacs generally
1141 views the separator as not belonging to any paragraph. */
1142 void
1143 bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, bool no_default_p)
1145 ptrdiff_t bytepos = bidi_it->bytepos;
1146 bool string_p = bidi_it->string.s || STRINGP (bidi_it->string.lstring);
1147 ptrdiff_t pstartbyte;
1148 /* Note that begbyte is a byte position, while end is a character
1149 position. Yes, this is ugly, but we are trying to avoid costly
1150 calls to BYTE_TO_CHAR and its ilk. */
1151 ptrdiff_t begbyte = string_p ? 0 : BEGV_BYTE;
1152 ptrdiff_t end = string_p ? bidi_it->string.schars : ZV;
1154 /* Special case for an empty buffer. */
1155 if (bytepos == begbyte && bidi_it->charpos == end)
1156 dir = L2R;
1157 /* We should never be called at EOB or before BEGV. */
1158 else if (bidi_it->charpos >= end || bytepos < begbyte)
1159 emacs_abort ();
1161 if (dir == L2R)
1163 bidi_it->paragraph_dir = L2R;
1164 bidi_it->new_paragraph = 0;
1166 else if (dir == R2L)
1168 bidi_it->paragraph_dir = R2L;
1169 bidi_it->new_paragraph = 0;
1171 else if (dir == NEUTRAL_DIR) /* P2 */
1173 int ch;
1174 ptrdiff_t ch_len, nchars;
1175 ptrdiff_t pos, disp_pos = -1;
1176 int disp_prop = 0;
1177 bidi_type_t type;
1178 const unsigned char *s;
1180 if (!bidi_initialized)
1181 bidi_initialize ();
1183 /* If we are inside a paragraph separator, we are just waiting
1184 for the separator to be exhausted; use the previous paragraph
1185 direction. But don't do that if we have been just reseated,
1186 because we need to reinitialize below in that case. */
1187 if (!bidi_it->first_elt
1188 && bidi_it->charpos < bidi_it->separator_limit)
1189 return;
1191 /* If we are on a newline, get past it to where the next
1192 paragraph might start. But don't do that at BEGV since then
1193 we are potentially in a new paragraph that doesn't yet
1194 exist. */
1195 pos = bidi_it->charpos;
1196 s = (STRINGP (bidi_it->string.lstring)
1197 ? SDATA (bidi_it->string.lstring)
1198 : bidi_it->string.s);
1199 if (bytepos > begbyte
1200 && bidi_char_at_pos (bytepos, s, bidi_it->string.unibyte) == '\n')
1202 bytepos++;
1203 pos++;
1206 /* We are either at the beginning of a paragraph or in the
1207 middle of it. Find where this paragraph starts. */
1208 if (string_p)
1210 /* We don't support changes of paragraph direction inside a
1211 string. It is treated as a single paragraph. */
1212 pstartbyte = 0;
1214 else
1215 pstartbyte = bidi_find_paragraph_start (pos, bytepos);
1216 bidi_it->separator_limit = -1;
1217 bidi_it->new_paragraph = 0;
1219 /* The following loop is run more than once only if NO_DEFAULT_P,
1220 and only if we are iterating on a buffer. */
1221 do {
1222 ptrdiff_t pos1;
1224 bytepos = pstartbyte;
1225 if (!string_p)
1226 pos = BYTE_TO_CHAR (bytepos);
1227 ch = bidi_fetch_char (pos, bytepos, &disp_pos, &disp_prop,
1228 &bidi_it->string, bidi_it->w,
1229 bidi_it->frame_window_p, &ch_len, &nchars);
1230 type = bidi_get_type (ch, NEUTRAL_DIR);
1232 pos1 = pos;
1233 for (pos += nchars, bytepos += ch_len;
1234 ((bidi_get_category (type) != STRONG)
1235 || (bidi_ignore_explicit_marks_for_paragraph_level
1236 && (type == RLE || type == RLO
1237 || type == LRE || type == LRO)))
1238 /* Stop when searched too far into an abnormally large
1239 paragraph full of weak or neutral characters. */
1240 && pos - pos1 < MAX_STRONG_CHAR_SEARCH;
1241 type = bidi_get_type (ch, NEUTRAL_DIR))
1243 if (pos >= end)
1245 /* Pretend there's a paragraph separator at end of
1246 buffer/string. */
1247 type = NEUTRAL_B;
1248 break;
1250 if (!string_p
1251 && type == NEUTRAL_B
1252 && bidi_at_paragraph_end (pos, bytepos) >= -1)
1253 break;
1254 /* Fetch next character and advance to get past it. */
1255 ch = bidi_fetch_char (pos, bytepos, &disp_pos,
1256 &disp_prop, &bidi_it->string, bidi_it->w,
1257 bidi_it->frame_window_p, &ch_len, &nchars);
1258 pos += nchars;
1259 bytepos += ch_len;
1261 if ((type == STRONG_R || type == STRONG_AL) /* P3 */
1262 || (!bidi_ignore_explicit_marks_for_paragraph_level
1263 && (type == RLO || type == RLE)))
1264 bidi_it->paragraph_dir = R2L;
1265 else if (type == STRONG_L
1266 || (!bidi_ignore_explicit_marks_for_paragraph_level
1267 && (type == LRO || type == LRE)))
1268 bidi_it->paragraph_dir = L2R;
1269 if (!string_p
1270 && no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR)
1272 /* If this paragraph is at BEGV, default to L2R. */
1273 if (pstartbyte == BEGV_BYTE)
1274 bidi_it->paragraph_dir = L2R; /* P3 and HL1 */
1275 else
1277 ptrdiff_t prevpbyte = pstartbyte;
1278 ptrdiff_t p = BYTE_TO_CHAR (pstartbyte), pbyte = pstartbyte;
1280 /* Find the beginning of the previous paragraph, if any. */
1281 while (pbyte > BEGV_BYTE && prevpbyte >= pstartbyte)
1283 /* FXIME: What if p is covered by a display
1284 string? See also a FIXME inside
1285 bidi_find_paragraph_start. */
1286 DEC_BOTH (p, pbyte);
1287 prevpbyte = bidi_find_paragraph_start (p, pbyte);
1289 pstartbyte = prevpbyte;
1292 } while (!string_p
1293 && no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR);
1295 else
1296 emacs_abort ();
1298 /* Contrary to UAX#9 clause P3, we only default the paragraph
1299 direction to L2R if we have no previous usable paragraph
1300 direction. This is allowed by the HL1 clause. */
1301 if (bidi_it->paragraph_dir != L2R && bidi_it->paragraph_dir != R2L)
1302 bidi_it->paragraph_dir = L2R; /* P3 and HL1 ``higher-level protocols'' */
1303 if (bidi_it->paragraph_dir == R2L)
1304 bidi_it->level_stack[0].level = 1;
1305 else
1306 bidi_it->level_stack[0].level = 0;
1308 bidi_line_init (bidi_it);
1312 /***********************************************************************
1313 Resolving explicit and implicit levels.
1314 The rest of this file constitutes the core of the UBA implementation.
1315 ***********************************************************************/
1317 static bool
1318 bidi_explicit_dir_char (int ch)
1320 bidi_type_t ch_type;
1322 if (!bidi_initialized)
1323 emacs_abort ();
1324 ch_type = (bidi_type_t) XINT (CHAR_TABLE_REF (bidi_type_table, ch));
1325 return (ch_type == LRE || ch_type == LRO
1326 || ch_type == RLE || ch_type == RLO
1327 || ch_type == PDF);
1330 /* A helper function for bidi_resolve_explicit. It advances to the
1331 next character in logical order and determines the new embedding
1332 level and directional override, but does not take into account
1333 empty embeddings. */
1334 static int
1335 bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
1337 int curchar;
1338 bidi_type_t type;
1339 int current_level;
1340 int new_level;
1341 bidi_dir_t override;
1342 bool string_p = bidi_it->string.s || STRINGP (bidi_it->string.lstring);
1344 /* If reseat()'ed, don't advance, so as to start iteration from the
1345 position where we were reseated. bidi_it->bytepos can be less
1346 than BEGV_BYTE after reseat to BEGV. */
1347 if (bidi_it->bytepos < (string_p ? 0 : BEGV_BYTE)
1348 || bidi_it->first_elt)
1350 bidi_it->first_elt = 0;
1351 if (string_p)
1353 const unsigned char *p
1354 = (STRINGP (bidi_it->string.lstring)
1355 ? SDATA (bidi_it->string.lstring)
1356 : bidi_it->string.s);
1358 if (bidi_it->charpos < 0)
1359 bidi_it->charpos = bidi_it->bytepos = 0;
1360 eassert (bidi_it->bytepos == bidi_count_bytes (p, 0, 0,
1361 bidi_it->charpos,
1362 bidi_it->string.unibyte));
1364 else
1366 if (bidi_it->charpos < BEGV)
1368 bidi_it->charpos = BEGV;
1369 bidi_it->bytepos = BEGV_BYTE;
1371 eassert (bidi_it->bytepos == CHAR_TO_BYTE (bidi_it->charpos));
1374 /* Don't move at end of buffer/string. */
1375 else if (bidi_it->charpos < (string_p ? bidi_it->string.schars : ZV))
1377 /* Advance to the next character, skipping characters covered by
1378 display strings (nchars > 1). */
1379 if (bidi_it->nchars <= 0)
1380 emacs_abort ();
1381 bidi_it->charpos += bidi_it->nchars;
1382 if (bidi_it->ch_len == 0)
1383 emacs_abort ();
1384 bidi_it->bytepos += bidi_it->ch_len;
1387 current_level = bidi_it->level_stack[bidi_it->stack_idx].level; /* X1 */
1388 override = bidi_it->level_stack[bidi_it->stack_idx].override;
1389 new_level = current_level;
1391 if (bidi_it->charpos >= (string_p ? bidi_it->string.schars : ZV))
1393 curchar = BIDI_EOB;
1394 bidi_it->ch_len = 1;
1395 bidi_it->nchars = 1;
1396 bidi_it->disp_pos = (string_p ? bidi_it->string.schars : ZV);
1397 bidi_it->disp_prop = 0;
1399 else
1401 /* Fetch the character at BYTEPOS. If it is covered by a
1402 display string, treat the entire run of covered characters as
1403 a single character u+FFFC. */
1404 curchar = bidi_fetch_char (bidi_it->charpos, bidi_it->bytepos,
1405 &bidi_it->disp_pos, &bidi_it->disp_prop,
1406 &bidi_it->string, bidi_it->w,
1407 bidi_it->frame_window_p,
1408 &bidi_it->ch_len, &bidi_it->nchars);
1410 bidi_it->ch = curchar;
1412 /* Don't apply directional override here, as all the types we handle
1413 below will not be affected by the override anyway, and we need
1414 the original type unaltered. The override will be applied in
1415 bidi_resolve_weak. */
1416 type = bidi_get_type (curchar, NEUTRAL_DIR);
1417 bidi_it->orig_type = type;
1418 bidi_check_type (bidi_it->orig_type);
1420 if (type != PDF)
1421 bidi_it->prev_was_pdf = 0;
1423 bidi_it->type_after_w1 = UNKNOWN_BT;
1425 switch (type)
1427 case RLE: /* X2 */
1428 case RLO: /* X4 */
1429 bidi_it->type_after_w1 = type;
1430 bidi_check_type (bidi_it->type_after_w1);
1431 type = WEAK_BN; /* X9/Retaining */
1432 if (bidi_it->ignore_bn_limit <= -1)
1434 if (current_level <= BIDI_MAXLEVEL - 4)
1436 /* Compute the least odd embedding level greater than
1437 the current level. */
1438 new_level = ((current_level + 1) & ~1) + 1;
1439 if (bidi_it->type_after_w1 == RLE)
1440 override = NEUTRAL_DIR;
1441 else
1442 override = R2L;
1443 if (current_level == BIDI_MAXLEVEL - 4)
1444 bidi_it->invalid_rl_levels = 0;
1445 bidi_push_embedding_level (bidi_it, new_level, override);
1447 else
1449 bidi_it->invalid_levels++;
1450 /* See the commentary about invalid_rl_levels below. */
1451 if (bidi_it->invalid_rl_levels < 0)
1452 bidi_it->invalid_rl_levels = 0;
1453 bidi_it->invalid_rl_levels++;
1456 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1457 || (bidi_it->next_en_pos > bidi_it->charpos
1458 && bidi_it->next_en_type == WEAK_EN))
1459 type = WEAK_EN;
1460 break;
1461 case LRE: /* X3 */
1462 case LRO: /* X5 */
1463 bidi_it->type_after_w1 = type;
1464 bidi_check_type (bidi_it->type_after_w1);
1465 type = WEAK_BN; /* X9/Retaining */
1466 if (bidi_it->ignore_bn_limit <= -1)
1468 if (current_level <= BIDI_MAXLEVEL - 5)
1470 /* Compute the least even embedding level greater than
1471 the current level. */
1472 new_level = ((current_level + 2) & ~1);
1473 if (bidi_it->type_after_w1 == LRE)
1474 override = NEUTRAL_DIR;
1475 else
1476 override = L2R;
1477 bidi_push_embedding_level (bidi_it, new_level, override);
1479 else
1481 bidi_it->invalid_levels++;
1482 /* invalid_rl_levels counts invalid levels encountered
1483 while the embedding level was already too high for
1484 LRE/LRO, but not for RLE/RLO. That is because
1485 there may be exactly one PDF which we should not
1486 ignore even though invalid_levels is non-zero.
1487 invalid_rl_levels helps to know what PDF is
1488 that. */
1489 if (bidi_it->invalid_rl_levels >= 0)
1490 bidi_it->invalid_rl_levels++;
1493 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1494 || (bidi_it->next_en_pos > bidi_it->charpos
1495 && bidi_it->next_en_type == WEAK_EN))
1496 type = WEAK_EN;
1497 break;
1498 case PDF: /* X7 */
1499 bidi_it->type_after_w1 = type;
1500 bidi_check_type (bidi_it->type_after_w1);
1501 type = WEAK_BN; /* X9/Retaining */
1502 if (bidi_it->ignore_bn_limit <= -1)
1504 if (!bidi_it->invalid_rl_levels)
1506 new_level = bidi_pop_embedding_level (bidi_it);
1507 bidi_it->invalid_rl_levels = -1;
1508 if (bidi_it->invalid_levels)
1509 bidi_it->invalid_levels--;
1510 /* else nothing: UAX#9 says to ignore invalid PDFs */
1512 if (!bidi_it->invalid_levels)
1513 new_level = bidi_pop_embedding_level (bidi_it);
1514 else
1516 bidi_it->invalid_levels--;
1517 bidi_it->invalid_rl_levels--;
1520 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1521 || (bidi_it->next_en_pos > bidi_it->charpos
1522 && bidi_it->next_en_type == WEAK_EN))
1523 type = WEAK_EN;
1524 break;
1525 default:
1526 /* Nothing. */
1527 break;
1530 bidi_it->type = type;
1531 bidi_check_type (bidi_it->type);
1533 return new_level;
1536 /* Given an iterator state in BIDI_IT, advance one character position
1537 in the buffer/string to the next character (in the logical order),
1538 resolve any explicit embeddings and directional overrides, and
1539 return the embedding level of the character after resolving
1540 explicit directives and ignoring empty embeddings. */
1541 static int
1542 bidi_resolve_explicit (struct bidi_it *bidi_it)
1544 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1545 int new_level = bidi_resolve_explicit_1 (bidi_it);
1546 ptrdiff_t eob = bidi_it->string.s ? bidi_it->string.schars : ZV;
1547 const unsigned char *s
1548 = (STRINGP (bidi_it->string.lstring)
1549 ? SDATA (bidi_it->string.lstring)
1550 : bidi_it->string.s);
1552 if (prev_level < new_level
1553 && bidi_it->type == WEAK_BN
1554 && bidi_it->ignore_bn_limit == -1 /* only if not already known */
1555 && bidi_it->charpos < eob /* not already at EOB */
1556 && bidi_explicit_dir_char (bidi_char_at_pos (bidi_it->bytepos
1557 + bidi_it->ch_len, s,
1558 bidi_it->string.unibyte)))
1560 /* Avoid pushing and popping embedding levels if the level run
1561 is empty, as this breaks level runs where it shouldn't.
1562 UAX#9 removes all the explicit embedding and override codes,
1563 so empty embeddings disappear without a trace. We need to
1564 behave as if we did the same. */
1565 struct bidi_it saved_it;
1566 int level = prev_level;
1568 bidi_copy_it (&saved_it, bidi_it);
1570 while (bidi_explicit_dir_char (bidi_char_at_pos (bidi_it->bytepos
1571 + bidi_it->ch_len, s,
1572 bidi_it->string.unibyte)))
1574 /* This advances to the next character, skipping any
1575 characters covered by display strings. */
1576 level = bidi_resolve_explicit_1 (bidi_it);
1577 /* If string.lstring was relocated inside bidi_resolve_explicit_1,
1578 a pointer to its data is no longer valid. */
1579 if (STRINGP (bidi_it->string.lstring))
1580 s = SDATA (bidi_it->string.lstring);
1583 if (bidi_it->nchars <= 0)
1584 emacs_abort ();
1585 if (level == prev_level) /* empty embedding */
1586 saved_it.ignore_bn_limit = bidi_it->charpos + bidi_it->nchars;
1587 else /* this embedding is non-empty */
1588 saved_it.ignore_bn_limit = -2;
1590 bidi_copy_it (bidi_it, &saved_it);
1591 if (bidi_it->ignore_bn_limit > -1)
1593 /* We pushed a level, but we shouldn't have. Undo that. */
1594 if (!bidi_it->invalid_rl_levels)
1596 new_level = bidi_pop_embedding_level (bidi_it);
1597 bidi_it->invalid_rl_levels = -1;
1598 if (bidi_it->invalid_levels)
1599 bidi_it->invalid_levels--;
1601 if (!bidi_it->invalid_levels)
1602 new_level = bidi_pop_embedding_level (bidi_it);
1603 else
1605 bidi_it->invalid_levels--;
1606 bidi_it->invalid_rl_levels--;
1611 if (bidi_it->type == NEUTRAL_B) /* X8 */
1613 bidi_set_paragraph_end (bidi_it);
1614 /* This is needed by bidi_resolve_weak below, and in L1. */
1615 bidi_it->type_after_w1 = bidi_it->type;
1616 bidi_check_type (bidi_it->type_after_w1);
1619 return new_level;
1622 /* Advance in the buffer/string, resolve weak types and return the
1623 type of the next character after weak type resolution. */
1624 static bidi_type_t
1625 bidi_resolve_weak (struct bidi_it *bidi_it)
1627 bidi_type_t type;
1628 bidi_dir_t override;
1629 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1630 int new_level = bidi_resolve_explicit (bidi_it);
1631 int next_char;
1632 bidi_type_t type_of_next;
1633 struct bidi_it saved_it;
1634 ptrdiff_t eob
1635 = ((STRINGP (bidi_it->string.lstring) || bidi_it->string.s)
1636 ? bidi_it->string.schars : ZV);
1638 type = bidi_it->type;
1639 override = bidi_it->level_stack[bidi_it->stack_idx].override;
1641 if (type == UNKNOWN_BT
1642 || type == LRE
1643 || type == LRO
1644 || type == RLE
1645 || type == RLO
1646 || type == PDF)
1647 emacs_abort ();
1649 if (new_level != prev_level
1650 || bidi_it->type == NEUTRAL_B)
1652 /* We've got a new embedding level run, compute the directional
1653 type of sor and initialize per-run variables (UAX#9, clause
1654 X10). */
1655 bidi_set_sor_type (bidi_it, prev_level, new_level);
1657 else if (type == NEUTRAL_S || type == NEUTRAL_WS
1658 || type == WEAK_BN || type == STRONG_AL)
1659 bidi_it->type_after_w1 = type; /* needed in L1 */
1660 bidi_check_type (bidi_it->type_after_w1);
1662 /* Level and directional override status are already recorded in
1663 bidi_it, and do not need any change; see X6. */
1664 if (override == R2L) /* X6 */
1665 type = STRONG_R;
1666 else if (override == L2R)
1667 type = STRONG_L;
1668 else
1670 if (type == WEAK_NSM) /* W1 */
1672 /* Note that we don't need to consider the case where the
1673 prev character has its type overridden by an RLO or LRO,
1674 because then either the type of this NSM would have been
1675 also overridden, or the previous character is outside the
1676 current level run, and thus not relevant to this NSM.
1677 This is why NSM gets the type_after_w1 of the previous
1678 character. */
1679 if (bidi_it->prev.type_after_w1 != UNKNOWN_BT
1680 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1681 && bidi_it->prev.type_after_w1 != NEUTRAL_B)
1682 type = bidi_it->prev.type_after_w1;
1683 else if (bidi_it->sor == R2L)
1684 type = STRONG_R;
1685 else if (bidi_it->sor == L2R)
1686 type = STRONG_L;
1687 else /* shouldn't happen! */
1688 emacs_abort ();
1690 if (type == WEAK_EN /* W2 */
1691 && bidi_it->last_strong.type_after_w1 == STRONG_AL)
1692 type = WEAK_AN;
1693 else if (type == STRONG_AL) /* W3 */
1694 type = STRONG_R;
1695 else if ((type == WEAK_ES /* W4 */
1696 && bidi_it->prev.type_after_w1 == WEAK_EN
1697 && bidi_it->prev.orig_type == WEAK_EN)
1698 || (type == WEAK_CS
1699 && ((bidi_it->prev.type_after_w1 == WEAK_EN
1700 && bidi_it->prev.orig_type == WEAK_EN)
1701 || bidi_it->prev.type_after_w1 == WEAK_AN)))
1703 const unsigned char *s
1704 = (STRINGP (bidi_it->string.lstring)
1705 ? SDATA (bidi_it->string.lstring)
1706 : bidi_it->string.s);
1708 next_char = (bidi_it->charpos + bidi_it->nchars >= eob
1709 ? BIDI_EOB
1710 : bidi_char_at_pos (bidi_it->bytepos + bidi_it->ch_len,
1711 s, bidi_it->string.unibyte));
1712 type_of_next = bidi_get_type (next_char, override);
1714 if (type_of_next == WEAK_BN
1715 || bidi_explicit_dir_char (next_char))
1717 bidi_copy_it (&saved_it, bidi_it);
1718 while (bidi_resolve_explicit (bidi_it) == new_level
1719 && bidi_it->type == WEAK_BN)
1721 type_of_next = bidi_it->type;
1722 bidi_copy_it (bidi_it, &saved_it);
1725 /* If the next character is EN, but the last strong-type
1726 character is AL, that next EN will be changed to AN when
1727 we process it in W2 above. So in that case, this ES
1728 should not be changed into EN. */
1729 if (type == WEAK_ES
1730 && type_of_next == WEAK_EN
1731 && bidi_it->last_strong.type_after_w1 != STRONG_AL)
1732 type = WEAK_EN;
1733 else if (type == WEAK_CS)
1735 if (bidi_it->prev.type_after_w1 == WEAK_AN
1736 && (type_of_next == WEAK_AN
1737 /* If the next character is EN, but the last
1738 strong-type character is AL, EN will be later
1739 changed to AN when we process it in W2 above.
1740 So in that case, this ES should not be
1741 changed into EN. */
1742 || (type_of_next == WEAK_EN
1743 && bidi_it->last_strong.type_after_w1 == STRONG_AL)))
1744 type = WEAK_AN;
1745 else if (bidi_it->prev.type_after_w1 == WEAK_EN
1746 && type_of_next == WEAK_EN
1747 && bidi_it->last_strong.type_after_w1 != STRONG_AL)
1748 type = WEAK_EN;
1751 else if (type == WEAK_ET /* W5: ET with EN before or after it */
1752 || type == WEAK_BN) /* W5/Retaining */
1754 if (bidi_it->prev.type_after_w1 == WEAK_EN) /* ET/BN w/EN before it */
1755 type = WEAK_EN;
1756 else if (bidi_it->next_en_pos > bidi_it->charpos
1757 && bidi_it->next_en_type != WEAK_BN)
1759 if (bidi_it->next_en_type == WEAK_EN) /* ET/BN with EN after it */
1760 type = WEAK_EN;
1762 else if (bidi_it->next_en_pos >=0)
1764 ptrdiff_t en_pos = bidi_it->charpos + bidi_it->nchars;
1765 const unsigned char *s = (STRINGP (bidi_it->string.lstring)
1766 ? SDATA (bidi_it->string.lstring)
1767 : bidi_it->string.s);
1769 if (bidi_it->nchars <= 0)
1770 emacs_abort ();
1771 next_char
1772 = (bidi_it->charpos + bidi_it->nchars >= eob
1773 ? BIDI_EOB
1774 : bidi_char_at_pos (bidi_it->bytepos + bidi_it->ch_len, s,
1775 bidi_it->string.unibyte));
1776 type_of_next = bidi_get_type (next_char, override);
1778 if (type_of_next == WEAK_ET
1779 || type_of_next == WEAK_BN
1780 || bidi_explicit_dir_char (next_char))
1782 bidi_copy_it (&saved_it, bidi_it);
1783 while (bidi_resolve_explicit (bidi_it) == new_level
1784 && (bidi_it->type == WEAK_BN
1785 || bidi_it->type == WEAK_ET))
1787 type_of_next = bidi_it->type;
1788 en_pos = bidi_it->charpos;
1789 bidi_copy_it (bidi_it, &saved_it);
1791 /* Remember this position, to speed up processing of the
1792 next ETs. */
1793 bidi_it->next_en_pos = en_pos;
1794 if (type_of_next == WEAK_EN)
1796 /* If the last strong character is AL, the EN we've
1797 found will become AN when we get to it (W2). */
1798 if (bidi_it->last_strong.type_after_w1 == STRONG_AL)
1799 type_of_next = WEAK_AN;
1800 else if (type == WEAK_BN)
1801 type = NEUTRAL_ON; /* W6/Retaining */
1802 else
1803 type = WEAK_EN;
1805 else if (type_of_next == NEUTRAL_B)
1806 /* Record the fact that there are no more ENs from
1807 here to the end of paragraph, to avoid entering the
1808 loop above ever again in this paragraph. */
1809 bidi_it->next_en_pos = -1;
1810 /* Record the type of the character where we ended our search. */
1811 bidi_it->next_en_type = type_of_next;
1816 if (type == WEAK_ES || type == WEAK_ET || type == WEAK_CS /* W6 */
1817 || (type == WEAK_BN
1818 && (bidi_it->prev.type_after_w1 == WEAK_CS /* W6/Retaining */
1819 || bidi_it->prev.type_after_w1 == WEAK_ES
1820 || bidi_it->prev.type_after_w1 == WEAK_ET)))
1821 type = NEUTRAL_ON;
1823 /* Store the type we've got so far, before we clobber it with strong
1824 types in W7 and while resolving neutral types. But leave alone
1825 the original types that were recorded above, because we will need
1826 them for the L1 clause. */
1827 if (bidi_it->type_after_w1 == UNKNOWN_BT)
1828 bidi_it->type_after_w1 = type;
1829 bidi_check_type (bidi_it->type_after_w1);
1831 if (type == WEAK_EN) /* W7 */
1833 if ((bidi_it->last_strong.type_after_w1 == STRONG_L)
1834 || (bidi_it->last_strong.type == UNKNOWN_BT && bidi_it->sor == L2R))
1835 type = STRONG_L;
1838 bidi_it->type = type;
1839 bidi_check_type (bidi_it->type);
1840 return type;
1843 /* Resolve the type of a neutral character according to the type of
1844 surrounding strong text and the current embedding level. */
1845 static bidi_type_t
1846 bidi_resolve_neutral_1 (bidi_type_t prev_type, bidi_type_t next_type, int lev)
1848 /* N1: European and Arabic numbers are treated as though they were R. */
1849 if (next_type == WEAK_EN || next_type == WEAK_AN)
1850 next_type = STRONG_R;
1851 if (prev_type == WEAK_EN || prev_type == WEAK_AN)
1852 prev_type = STRONG_R;
1854 if (next_type == prev_type) /* N1 */
1855 return next_type;
1856 else if ((lev & 1) == 0) /* N2 */
1857 return STRONG_L;
1858 else
1859 return STRONG_R;
1862 static bidi_type_t
1863 bidi_resolve_neutral (struct bidi_it *bidi_it)
1865 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1866 bidi_type_t type = bidi_resolve_weak (bidi_it);
1867 int current_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1869 if (!(type == STRONG_R
1870 || type == STRONG_L
1871 || type == WEAK_BN
1872 || type == WEAK_EN
1873 || type == WEAK_AN
1874 || type == NEUTRAL_B
1875 || type == NEUTRAL_S
1876 || type == NEUTRAL_WS
1877 || type == NEUTRAL_ON))
1878 emacs_abort ();
1880 if ((type != NEUTRAL_B /* Don't risk entering the long loop below if
1881 we are already at paragraph end. */
1882 && bidi_get_category (type) == NEUTRAL)
1883 || (type == WEAK_BN && prev_level == current_level))
1885 if (bidi_it->next_for_neutral.type != UNKNOWN_BT)
1886 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1887 bidi_it->next_for_neutral.type,
1888 current_level);
1889 /* The next two "else if" clauses are shortcuts for the
1890 important special case when we have a long sequence of
1891 neutral or WEAK_BN characters, such as whitespace or nulls or
1892 other control characters, on the base embedding level of the
1893 paragraph, and that sequence goes all the way to the end of
1894 the paragraph and follows a character whose resolved
1895 directionality is identical to the base embedding level.
1896 (This is what happens in a buffer with plain L2R text that
1897 happens to include long sequences of control characters.) By
1898 virtue of N1, the result of examining this long sequence will
1899 always be either STRONG_L or STRONG_R, depending on the base
1900 embedding level. So we use this fact directly instead of
1901 entering the expensive loop in the "else" clause. */
1902 else if (current_level == 0
1903 && bidi_it->prev_for_neutral.type == STRONG_L
1904 && !bidi_explicit_dir_char (bidi_it->ch))
1905 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1906 STRONG_L, current_level);
1907 else if (/* current level is 1 */
1908 current_level == 1
1909 /* base embedding level is also 1 */
1910 && bidi_it->level_stack[0].level == 1
1911 /* previous character is one of those considered R for
1912 the purposes of W5 */
1913 && (bidi_it->prev_for_neutral.type == STRONG_R
1914 || bidi_it->prev_for_neutral.type == WEAK_EN
1915 || bidi_it->prev_for_neutral.type == WEAK_AN)
1916 && !bidi_explicit_dir_char (bidi_it->ch))
1917 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1918 STRONG_R, current_level);
1919 else
1921 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1922 the assumption of batch-style processing; see clauses W4,
1923 W5, and especially N1, which require to look far forward
1924 (as well as back) in the buffer/string. May the fleas of
1925 a thousand camels infest the armpits of those who design
1926 supposedly general-purpose algorithms by looking at their
1927 own implementations, and fail to consider other possible
1928 implementations! */
1929 struct bidi_it saved_it;
1930 bidi_type_t next_type;
1932 if (bidi_it->scan_dir == -1)
1933 emacs_abort ();
1935 bidi_copy_it (&saved_it, bidi_it);
1936 /* Scan the text forward until we find the first non-neutral
1937 character, and then use that to resolve the neutral we
1938 are dealing with now. We also cache the scanned iterator
1939 states, to salvage some of the effort later. */
1940 bidi_cache_iterator_state (bidi_it, 0);
1941 do {
1942 /* Record the info about the previous character, so that
1943 it will be cached below with this state. */
1944 if (bidi_it->type_after_w1 != WEAK_BN /* W1/Retaining */
1945 && bidi_it->type != WEAK_BN)
1946 bidi_remember_char (&bidi_it->prev, bidi_it);
1947 type = bidi_resolve_weak (bidi_it);
1948 /* Paragraph separators have their levels fully resolved
1949 at this point, so cache them as resolved. */
1950 bidi_cache_iterator_state (bidi_it, type == NEUTRAL_B);
1951 /* FIXME: implement L1 here, by testing for a newline and
1952 resetting the level for any sequence of whitespace
1953 characters adjacent to it. */
1954 } while (!(type == NEUTRAL_B
1955 || (type != WEAK_BN
1956 && bidi_get_category (type) != NEUTRAL)
1957 /* This is all per level run, so stop when we
1958 reach the end of this level run. */
1959 || (bidi_it->level_stack[bidi_it->stack_idx].level
1960 != current_level)));
1962 bidi_remember_char (&saved_it.next_for_neutral, bidi_it);
1964 switch (type)
1966 case STRONG_L:
1967 case STRONG_R:
1968 case STRONG_AL:
1969 /* Actually, STRONG_AL cannot happen here, because
1970 bidi_resolve_weak converts it to STRONG_R, per W3. */
1971 eassert (type != STRONG_AL);
1972 next_type = type;
1973 break;
1974 case WEAK_EN:
1975 case WEAK_AN:
1976 /* N1: ``European and Arabic numbers are treated as
1977 though they were R.'' */
1978 next_type = STRONG_R;
1979 break;
1980 case WEAK_BN:
1981 case NEUTRAL_ON: /* W6/Retaining */
1982 if (!bidi_explicit_dir_char (bidi_it->ch))
1983 emacs_abort (); /* can't happen: BNs are skipped */
1984 /* FALLTHROUGH */
1985 case NEUTRAL_B:
1986 /* Marched all the way to the end of this level run.
1987 We need to use the eor type, whose information is
1988 stored by bidi_set_sor_type in the prev_for_neutral
1989 member. */
1990 if (saved_it.type != WEAK_BN
1991 || bidi_get_category (bidi_it->prev.type_after_w1) == NEUTRAL)
1992 next_type = bidi_it->prev_for_neutral.type;
1993 else
1995 /* This is a BN which does not adjoin neutrals.
1996 Leave its type alone. */
1997 bidi_copy_it (bidi_it, &saved_it);
1998 return bidi_it->type;
2000 break;
2001 default:
2002 emacs_abort ();
2004 type = bidi_resolve_neutral_1 (saved_it.prev_for_neutral.type,
2005 next_type, current_level);
2006 saved_it.next_for_neutral.type = next_type;
2007 saved_it.type = type;
2008 bidi_check_type (next_type);
2009 bidi_check_type (type);
2010 bidi_copy_it (bidi_it, &saved_it);
2013 return type;
2016 /* Given an iterator state in BIDI_IT, advance one character position
2017 in the buffer/string to the next character (in the logical order),
2018 resolve the bidi type of that next character, and return that
2019 type. */
2020 static bidi_type_t
2021 bidi_type_of_next_char (struct bidi_it *bidi_it)
2023 bidi_type_t type;
2025 /* This should always be called during a forward scan. */
2026 if (bidi_it->scan_dir != 1)
2027 emacs_abort ();
2029 /* Reset the limit until which to ignore BNs if we step out of the
2030 area where we found only empty levels. */
2031 if ((bidi_it->ignore_bn_limit > -1
2032 && bidi_it->ignore_bn_limit <= bidi_it->charpos)
2033 || (bidi_it->ignore_bn_limit == -2
2034 && !bidi_explicit_dir_char (bidi_it->ch)))
2035 bidi_it->ignore_bn_limit = -1;
2037 type = bidi_resolve_neutral (bidi_it);
2039 return type;
2042 /* Given an iterator state BIDI_IT, advance one character position in
2043 the buffer/string to the next character (in the current scan
2044 direction), resolve the embedding and implicit levels of that next
2045 character, and return the resulting level. */
2046 static int
2047 bidi_level_of_next_char (struct bidi_it *bidi_it)
2049 bidi_type_t type;
2050 int level, prev_level = -1;
2051 struct bidi_saved_info next_for_neutral;
2052 ptrdiff_t next_char_pos = -2;
2054 if (bidi_it->scan_dir == 1)
2056 ptrdiff_t eob
2057 = ((bidi_it->string.s || STRINGP (bidi_it->string.lstring))
2058 ? bidi_it->string.schars : ZV);
2060 /* There's no sense in trying to advance if we hit end of text. */
2061 if (bidi_it->charpos >= eob)
2062 return bidi_it->resolved_level;
2064 /* Record the info about the previous character. */
2065 if (bidi_it->type_after_w1 != WEAK_BN /* W1/Retaining */
2066 && bidi_it->type != WEAK_BN)
2067 bidi_remember_char (&bidi_it->prev, bidi_it);
2068 if (bidi_it->type_after_w1 == STRONG_R
2069 || bidi_it->type_after_w1 == STRONG_L
2070 || bidi_it->type_after_w1 == STRONG_AL)
2071 bidi_remember_char (&bidi_it->last_strong, bidi_it);
2072 /* FIXME: it sounds like we don't need both prev and
2073 prev_for_neutral members, but I'm leaving them both for now. */
2074 if (bidi_it->type == STRONG_R || bidi_it->type == STRONG_L
2075 || bidi_it->type == WEAK_EN || bidi_it->type == WEAK_AN)
2076 bidi_remember_char (&bidi_it->prev_for_neutral, bidi_it);
2078 /* If we overstepped the characters used for resolving neutrals
2079 and whitespace, invalidate their info in the iterator. */
2080 if (bidi_it->charpos >= bidi_it->next_for_neutral.charpos)
2081 bidi_it->next_for_neutral.type = UNKNOWN_BT;
2082 if (bidi_it->next_en_pos >= 0
2083 && bidi_it->charpos >= bidi_it->next_en_pos)
2085 bidi_it->next_en_pos = 0;
2086 bidi_it->next_en_type = UNKNOWN_BT;
2088 if (bidi_it->next_for_ws.type != UNKNOWN_BT
2089 && bidi_it->charpos >= bidi_it->next_for_ws.charpos)
2090 bidi_it->next_for_ws.type = UNKNOWN_BT;
2092 /* This must be taken before we fill the iterator with the info
2093 about the next char. If we scan backwards, the iterator
2094 state must be already cached, so there's no need to know the
2095 embedding level of the previous character, since we will be
2096 returning to our caller shortly. */
2097 prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
2099 next_for_neutral = bidi_it->next_for_neutral;
2101 /* Perhaps the character we want is already cached. If it is, the
2102 call to bidi_cache_find below will return a type other than
2103 UNKNOWN_BT. */
2104 if (bidi_cache_idx > bidi_cache_start && !bidi_it->first_elt)
2106 int bob = ((bidi_it->string.s || STRINGP (bidi_it->string.lstring))
2107 ? 0 : 1);
2108 if (bidi_it->scan_dir > 0)
2110 if (bidi_it->nchars <= 0)
2111 emacs_abort ();
2112 next_char_pos = bidi_it->charpos + bidi_it->nchars;
2114 else if (bidi_it->charpos >= bob)
2115 /* Implementation note: we allow next_char_pos to be as low as
2116 0 for buffers or -1 for strings, and that is okay because
2117 that's the "position" of the sentinel iterator state we
2118 cached at the beginning of the iteration. */
2119 next_char_pos = bidi_it->charpos - 1;
2120 if (next_char_pos >= bob - 1)
2121 type = bidi_cache_find (next_char_pos, -1, bidi_it);
2122 else
2123 type = UNKNOWN_BT;
2125 else
2126 type = UNKNOWN_BT;
2127 if (type != UNKNOWN_BT)
2129 /* Don't lose the information for resolving neutrals! The
2130 cached states could have been cached before their
2131 next_for_neutral member was computed. If we are on our way
2132 forward, we can simply take the info from the previous
2133 state. */
2134 if (bidi_it->scan_dir == 1
2135 && bidi_it->next_for_neutral.type == UNKNOWN_BT)
2136 bidi_it->next_for_neutral = next_for_neutral;
2138 /* If resolved_level is -1, it means this state was cached
2139 before it was completely resolved, so we cannot return
2140 it. */
2141 if (bidi_it->resolved_level != -1)
2142 return bidi_it->resolved_level;
2144 if (bidi_it->scan_dir == -1)
2145 /* If we are going backwards, the iterator state is already cached
2146 from previous scans, and should be fully resolved. */
2147 emacs_abort ();
2149 if (type == UNKNOWN_BT)
2150 type = bidi_type_of_next_char (bidi_it);
2152 if (type == NEUTRAL_B)
2153 return bidi_it->resolved_level;
2155 level = bidi_it->level_stack[bidi_it->stack_idx].level;
2156 if ((bidi_get_category (type) == NEUTRAL /* && type != NEUTRAL_B */)
2157 || (type == WEAK_BN && prev_level == level))
2159 if (bidi_it->next_for_neutral.type == UNKNOWN_BT)
2160 emacs_abort ();
2162 /* If the cached state shows a neutral character, it was not
2163 resolved by bidi_resolve_neutral, so do it now. */
2164 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
2165 bidi_it->next_for_neutral.type,
2166 level);
2169 if (!(type == STRONG_R
2170 || type == STRONG_L
2171 || type == WEAK_BN
2172 || type == WEAK_EN
2173 || type == WEAK_AN))
2174 emacs_abort ();
2175 bidi_it->type = type;
2176 bidi_check_type (bidi_it->type);
2178 /* For L1 below, we need to know, for each WS character, whether
2179 it belongs to a sequence of WS characters preceding a newline
2180 or a TAB or a paragraph separator. */
2181 if (bidi_it->orig_type == NEUTRAL_WS
2182 && bidi_it->next_for_ws.type == UNKNOWN_BT)
2184 int ch;
2185 ptrdiff_t clen = bidi_it->ch_len;
2186 ptrdiff_t bpos = bidi_it->bytepos;
2187 ptrdiff_t cpos = bidi_it->charpos;
2188 ptrdiff_t disp_pos = bidi_it->disp_pos;
2189 ptrdiff_t nc = bidi_it->nchars;
2190 struct bidi_string_data bs = bidi_it->string;
2191 bidi_type_t chtype;
2192 bool fwp = bidi_it->frame_window_p;
2193 int dpp = bidi_it->disp_prop;
2195 if (bidi_it->nchars <= 0)
2196 emacs_abort ();
2197 do {
2198 ch = bidi_fetch_char (cpos += nc, bpos += clen, &disp_pos, &dpp, &bs,
2199 bidi_it->w, fwp, &clen, &nc);
2200 if (ch == '\n' || ch == BIDI_EOB)
2201 chtype = NEUTRAL_B;
2202 else
2203 chtype = bidi_get_type (ch, NEUTRAL_DIR);
2204 } while (chtype == NEUTRAL_WS || chtype == WEAK_BN
2205 || bidi_explicit_dir_char (ch)); /* L1/Retaining */
2206 bidi_it->next_for_ws.type = chtype;
2207 bidi_check_type (bidi_it->next_for_ws.type);
2208 bidi_it->next_for_ws.charpos = cpos;
2209 bidi_it->next_for_ws.bytepos = bpos;
2212 /* Resolve implicit levels, with a twist: PDFs get the embedding
2213 level of the embedding they terminate. See below for the
2214 reason. */
2215 if (bidi_it->orig_type == PDF
2216 /* Don't do this if this formatting code didn't change the
2217 embedding level due to invalid or empty embeddings. */
2218 && prev_level != level)
2220 /* Don't look in UAX#9 for the reason for this: it's our own
2221 private quirk. The reason is that we want the formatting
2222 codes to be delivered so that they bracket the text of their
2223 embedding. For example, given the text
2225 {RLO}teST{PDF}
2227 we want it to be displayed as
2229 {PDF}STet{RLO}
2231 not as
2233 STet{RLO}{PDF}
2235 which will result because we bump up the embedding level as
2236 soon as we see the RLO and pop it as soon as we see the PDF,
2237 so RLO itself has the same embedding level as "teST", and
2238 thus would be normally delivered last, just before the PDF.
2239 The switch below fiddles with the level of PDF so that this
2240 ugly side effect does not happen.
2242 (This is, of course, only important if the formatting codes
2243 are actually displayed, but Emacs does need to display them
2244 if the user wants to.) */
2245 level = prev_level;
2247 else if (bidi_it->orig_type == NEUTRAL_B /* L1 */
2248 || bidi_it->orig_type == NEUTRAL_S
2249 || bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB
2250 || (bidi_it->orig_type == NEUTRAL_WS
2251 && (bidi_it->next_for_ws.type == NEUTRAL_B
2252 || bidi_it->next_for_ws.type == NEUTRAL_S)))
2253 level = bidi_it->level_stack[0].level;
2254 else if ((level & 1) == 0) /* I1 */
2256 if (type == STRONG_R)
2257 level++;
2258 else if (type == WEAK_EN || type == WEAK_AN)
2259 level += 2;
2261 else /* I2 */
2263 if (type == STRONG_L || type == WEAK_EN || type == WEAK_AN)
2264 level++;
2267 bidi_it->resolved_level = level;
2268 return level;
2271 /* Move to the other edge of a level given by LEVEL. If END_FLAG,
2272 we are at the end of a level, and we need to prepare to
2273 resume the scan of the lower level.
2275 If this level's other edge is cached, we simply jump to it, filling
2276 the iterator structure with the iterator state on the other edge.
2277 Otherwise, we walk the buffer or string until we come back to the
2278 same level as LEVEL.
2280 Note: we are not talking here about a ``level run'' in the UAX#9
2281 sense of the term, but rather about a ``level'' which includes
2282 all the levels higher than it. In other words, given the levels
2283 like this:
2285 11111112222222333333334443343222222111111112223322111
2286 A B C
2288 and assuming we are at point A scanning left to right, this
2289 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
2290 at point B. */
2291 static void
2292 bidi_find_other_level_edge (struct bidi_it *bidi_it, int level, bool end_flag)
2294 int dir = end_flag ? -bidi_it->scan_dir : bidi_it->scan_dir;
2295 ptrdiff_t idx;
2297 /* Try the cache first. */
2298 if ((idx = bidi_cache_find_level_change (level, dir, end_flag))
2299 >= bidi_cache_start)
2300 bidi_cache_fetch_state (idx, bidi_it);
2301 else
2303 int new_level;
2305 /* If we are at end of level, its edges must be cached. */
2306 if (end_flag)
2307 emacs_abort ();
2309 bidi_cache_iterator_state (bidi_it, 1);
2310 do {
2311 new_level = bidi_level_of_next_char (bidi_it);
2312 bidi_cache_iterator_state (bidi_it, 1);
2313 } while (new_level >= level);
2317 void
2318 bidi_move_to_visually_next (struct bidi_it *bidi_it)
2320 int old_level, new_level, next_level;
2321 struct bidi_it sentinel;
2322 struct gcpro gcpro1;
2324 if (bidi_it->charpos < 0 || bidi_it->bytepos < 0)
2325 emacs_abort ();
2327 if (bidi_it->scan_dir == 0)
2329 bidi_it->scan_dir = 1; /* default to logical order */
2332 /* The code below can call eval, and thus cause GC. If we are
2333 iterating a Lisp string, make sure it won't be GCed. */
2334 if (STRINGP (bidi_it->string.lstring))
2335 GCPRO1 (bidi_it->string.lstring);
2337 /* If we just passed a newline, initialize for the next line. */
2338 if (!bidi_it->first_elt
2339 && (bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB))
2340 bidi_line_init (bidi_it);
2342 /* Prepare the sentinel iterator state, and cache it. When we bump
2343 into it, scanning backwards, we'll know that the last non-base
2344 level is exhausted. */
2345 if (bidi_cache_idx == bidi_cache_start)
2347 bidi_copy_it (&sentinel, bidi_it);
2348 if (bidi_it->first_elt)
2350 sentinel.charpos--; /* cached charpos needs to be monotonic */
2351 sentinel.bytepos--;
2352 sentinel.ch = '\n'; /* doesn't matter, but why not? */
2353 sentinel.ch_len = 1;
2354 sentinel.nchars = 1;
2356 bidi_cache_iterator_state (&sentinel, 1);
2359 old_level = bidi_it->resolved_level;
2360 new_level = bidi_level_of_next_char (bidi_it);
2362 /* Reordering of resolved levels (clause L2) is implemented by
2363 jumping to the other edge of the level and flipping direction of
2364 scanning the text whenever we find a level change. */
2365 if (new_level != old_level)
2367 bool ascending = new_level > old_level;
2368 int level_to_search = ascending ? old_level + 1 : old_level;
2369 int incr = ascending ? 1 : -1;
2370 int expected_next_level = old_level + incr;
2372 /* Jump (or walk) to the other edge of this level. */
2373 bidi_find_other_level_edge (bidi_it, level_to_search, !ascending);
2374 /* Switch scan direction and peek at the next character in the
2375 new direction. */
2376 bidi_it->scan_dir = -bidi_it->scan_dir;
2378 /* The following loop handles the case where the resolved level
2379 jumps by more than one. This is typical for numbers inside a
2380 run of text with left-to-right embedding direction, but can
2381 also happen in other situations. In those cases the decision
2382 where to continue after a level change, and in what direction,
2383 is tricky. For example, given a text like below:
2385 abcdefgh
2386 11336622
2388 (where the numbers below the text show the resolved levels),
2389 the result of reordering according to UAX#9 should be this:
2391 efdcghba
2393 This is implemented by the loop below which flips direction
2394 and jumps to the other edge of the level each time it finds
2395 the new level not to be the expected one. The expected level
2396 is always one more or one less than the previous one. */
2397 next_level = bidi_peek_at_next_level (bidi_it);
2398 while (next_level != expected_next_level)
2400 /* If next_level is -1, it means we have an unresolved level
2401 in the cache, which at this point should not happen. If
2402 it does, we will infloop. */
2403 eassert (next_level >= 0);
2404 expected_next_level += incr;
2405 level_to_search += incr;
2406 bidi_find_other_level_edge (bidi_it, level_to_search, !ascending);
2407 bidi_it->scan_dir = -bidi_it->scan_dir;
2408 next_level = bidi_peek_at_next_level (bidi_it);
2411 /* Finally, deliver the next character in the new direction. */
2412 next_level = bidi_level_of_next_char (bidi_it);
2415 /* Take note when we have just processed the newline that precedes
2416 the end of the paragraph. The next time we are about to be
2417 called, set_iterator_to_next will automatically reinit the
2418 paragraph direction, if needed. We do this at the newline before
2419 the paragraph separator, because the next character might not be
2420 the first character of the next paragraph, due to the bidi
2421 reordering, whereas we _must_ know the paragraph base direction
2422 _before_ we process the paragraph's text, since the base
2423 direction affects the reordering. */
2424 if (bidi_it->scan_dir == 1
2425 && (bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB))
2427 /* The paragraph direction of the entire string, once
2428 determined, is in effect for the entire string. Setting the
2429 separator limit to the end of the string prevents
2430 bidi_paragraph_init from being called automatically on this
2431 string. */
2432 if (bidi_it->string.s || STRINGP (bidi_it->string.lstring))
2433 bidi_it->separator_limit = bidi_it->string.schars;
2434 else if (bidi_it->bytepos < ZV_BYTE)
2436 ptrdiff_t sep_len
2437 = bidi_at_paragraph_end (bidi_it->charpos + bidi_it->nchars,
2438 bidi_it->bytepos + bidi_it->ch_len);
2439 if (bidi_it->nchars <= 0)
2440 emacs_abort ();
2441 if (sep_len >= 0)
2443 bidi_it->new_paragraph = 1;
2444 /* Record the buffer position of the last character of the
2445 paragraph separator. */
2446 bidi_it->separator_limit
2447 = bidi_it->charpos + bidi_it->nchars + sep_len;
2452 if (bidi_it->scan_dir == 1 && bidi_cache_idx > bidi_cache_start)
2454 /* If we are at paragraph's base embedding level and beyond the
2455 last cached position, the cache's job is done and we can
2456 discard it. */
2457 if (bidi_it->resolved_level == bidi_it->level_stack[0].level
2458 && bidi_it->charpos > (bidi_cache[bidi_cache_idx - 1].charpos
2459 + bidi_cache[bidi_cache_idx - 1].nchars - 1))
2460 bidi_cache_reset ();
2461 /* But as long as we are caching during forward scan, we must
2462 cache each state, or else the cache integrity will be
2463 compromised: it assumes cached states correspond to buffer
2464 positions 1:1. */
2465 else
2466 bidi_cache_iterator_state (bidi_it, 1);
2469 if (STRINGP (bidi_it->string.lstring))
2470 UNGCPRO;
2473 /* This is meant to be called from within the debugger, whenever you
2474 wish to examine the cache contents. */
2475 void bidi_dump_cached_states (void) EXTERNALLY_VISIBLE;
2476 void
2477 bidi_dump_cached_states (void)
2479 ptrdiff_t i;
2480 int ndigits = 1;
2482 if (bidi_cache_idx == 0)
2484 fprintf (stderr, "The cache is empty.\n");
2485 return;
2487 fprintf (stderr, "Total of %"pD"d state%s in cache:\n",
2488 bidi_cache_idx, bidi_cache_idx == 1 ? "" : "s");
2490 for (i = bidi_cache[bidi_cache_idx - 1].charpos; i > 0; i /= 10)
2491 ndigits++;
2492 fputs ("ch ", stderr);
2493 for (i = 0; i < bidi_cache_idx; i++)
2494 fprintf (stderr, "%*c", ndigits, bidi_cache[i].ch);
2495 fputs ("\n", stderr);
2496 fputs ("lvl ", stderr);
2497 for (i = 0; i < bidi_cache_idx; i++)
2498 fprintf (stderr, "%*d", ndigits, bidi_cache[i].resolved_level);
2499 fputs ("\n", stderr);
2500 fputs ("pos ", stderr);
2501 for (i = 0; i < bidi_cache_idx; i++)
2502 fprintf (stderr, "%*"pD"d", ndigits, bidi_cache[i].charpos);
2503 fputs ("\n", stderr);