Revert previous patch, it introduces other problems.
[emacs.git] / src / bidi.c
blobb96cc24bbd17995802b2cc02e187a81aa2e03c57
1 /* Low-level bidirectional buffer/string-scanning functions for GNU Emacs.
2 Copyright (C) 2000-2001, 2004-2005, 2009-2014 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"
64 #include "region-cache.h"
66 static bool bidi_initialized = 0;
68 static Lisp_Object bidi_type_table, bidi_mirror_table;
70 #define BIDI_EOB (-1)
72 /* Data type for describing the bidirectional character categories. */
73 typedef enum {
74 UNKNOWN_BC,
75 NEUTRAL,
76 WEAK,
77 STRONG,
78 EXPLICIT_FORMATTING
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 switch (default_type)
119 case WEAK_BN:
120 case NEUTRAL_B:
121 case LRE:
122 case LRO:
123 case RLE:
124 case RLO:
125 case PDF:
126 return default_type;
127 /* FIXME: The isolate controls are treated as BN until we add
128 support for UBA v6.3. */
129 case LRI:
130 case RLI:
131 case FSI:
132 case PDI:
133 return WEAK_BN;
134 default:
135 if (override == L2R)
136 return STRONG_L;
137 else if (override == R2L)
138 return STRONG_R;
139 else
140 return default_type;
144 static void
145 bidi_check_type (bidi_type_t type)
147 eassert (UNKNOWN_BT <= type && type <= NEUTRAL_ON);
150 /* Given a bidi TYPE of a character, return its category. */
151 static bidi_category_t
152 bidi_get_category (bidi_type_t type)
154 switch (type)
156 case UNKNOWN_BT:
157 return UNKNOWN_BC;
158 case STRONG_L:
159 case STRONG_R:
160 case STRONG_AL:
161 return STRONG;
162 case WEAK_EN:
163 case WEAK_ES:
164 case WEAK_ET:
165 case WEAK_AN:
166 case WEAK_CS:
167 case WEAK_NSM:
168 case WEAK_BN:
169 /* FIXME */
170 case LRI:
171 case RLI:
172 case FSI:
173 case PDI:
174 return WEAK;
175 case NEUTRAL_B:
176 case NEUTRAL_S:
177 case NEUTRAL_WS:
178 case NEUTRAL_ON:
179 return NEUTRAL;
180 case LRE:
181 case LRO:
182 case RLE:
183 case RLO:
184 case PDF:
185 #if 0
186 /* FIXME: This awaits implementation of isolate support. */
187 case LRI:
188 case RLI:
189 case FSI:
190 case PDI:
191 #endif
192 return EXPLICIT_FORMATTING;
193 default:
194 emacs_abort ();
198 /* Return the mirrored character of C, if it has one. If C has no
199 mirrored counterpart, return C.
200 Note: The conditions in UAX#9 clause L4 regarding the surrounding
201 context must be tested by the caller. */
203 bidi_mirror_char (int c)
205 Lisp_Object val;
207 if (c == BIDI_EOB)
208 return c;
209 if (c < 0 || c > MAX_CHAR)
210 emacs_abort ();
212 val = CHAR_TABLE_REF (bidi_mirror_table, c);
213 if (INTEGERP (val))
215 int v;
217 /* When debugging, check before assigning to V, so that the check
218 isn't broken by undefined behavior due to int overflow. */
219 eassert (CHAR_VALID_P (XINT (val)));
221 v = XINT (val);
223 /* Minimal test we must do in optimized builds, to prevent weird
224 crashes further down the road. */
225 if (v < 0 || v > MAX_CHAR)
226 emacs_abort ();
228 return v;
231 return c;
234 /* Determine the start-of-run (sor) directional type given the two
235 embedding levels on either side of the run boundary. Also, update
236 the saved info about previously seen characters, since that info is
237 generally valid for a single level run. */
238 static void
239 bidi_set_sor_type (struct bidi_it *bidi_it, int level_before, int level_after)
241 int higher_level = (level_before > level_after ? level_before : level_after);
243 /* The prev_was_pdf gork is required for when we have several PDFs
244 in a row. In that case, we want to compute the sor type for the
245 next level run only once: when we see the first PDF. That's
246 because the sor type depends only on the higher of the two levels
247 that we find on the two sides of the level boundary (see UAX#9,
248 clause X10), and so we don't need to know the final embedding
249 level to which we descend after processing all the PDFs. */
250 if (!bidi_it->prev_was_pdf || level_before < level_after)
251 /* FIXME: should the default sor direction be user selectable? */
252 bidi_it->sor = ((higher_level & 1) != 0 ? R2L : L2R);
253 if (level_before > level_after)
254 bidi_it->prev_was_pdf = 1;
256 bidi_it->prev.type = UNKNOWN_BT;
257 bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1
258 = bidi_it->last_strong.orig_type = UNKNOWN_BT;
259 bidi_it->prev_for_neutral.type = (bidi_it->sor == R2L ? STRONG_R : STRONG_L);
260 bidi_it->prev_for_neutral.charpos = bidi_it->charpos;
261 bidi_it->prev_for_neutral.bytepos = bidi_it->bytepos;
262 bidi_it->next_for_neutral.type = bidi_it->next_for_neutral.type_after_w1
263 = bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
264 bidi_it->ignore_bn_limit = -1; /* meaning it's unknown */
267 /* Push the current embedding level and override status; reset the
268 current level to LEVEL and the current override status to OVERRIDE. */
269 static void
270 bidi_push_embedding_level (struct bidi_it *bidi_it,
271 int level, bidi_dir_t override)
273 bidi_it->stack_idx++;
274 eassert (bidi_it->stack_idx < BIDI_MAXLEVEL);
275 bidi_it->level_stack[bidi_it->stack_idx].level = level;
276 bidi_it->level_stack[bidi_it->stack_idx].override = override;
279 /* Pop the embedding level and directional override status from the
280 stack, and return the new level. */
281 static int
282 bidi_pop_embedding_level (struct bidi_it *bidi_it)
284 /* UAX#9 says to ignore invalid PDFs. */
285 if (bidi_it->stack_idx > 0)
286 bidi_it->stack_idx--;
287 return bidi_it->level_stack[bidi_it->stack_idx].level;
290 /* Record in SAVED_INFO the information about the current character. */
291 static void
292 bidi_remember_char (struct bidi_saved_info *saved_info,
293 struct bidi_it *bidi_it)
295 saved_info->charpos = bidi_it->charpos;
296 saved_info->bytepos = bidi_it->bytepos;
297 saved_info->type = bidi_it->type;
298 bidi_check_type (bidi_it->type);
299 saved_info->type_after_w1 = bidi_it->type_after_w1;
300 bidi_check_type (bidi_it->type_after_w1);
301 saved_info->orig_type = bidi_it->orig_type;
302 bidi_check_type (bidi_it->orig_type);
305 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
306 copies the part of the level stack that is actually in use. */
307 static void
308 bidi_copy_it (struct bidi_it *to, struct bidi_it *from)
310 /* Copy everything from the start through the active part of
311 the level stack. */
312 memcpy (to, from,
313 (offsetof (struct bidi_it, level_stack[1])
314 + from->stack_idx * sizeof from->level_stack[0]));
318 /***********************************************************************
319 Caching the bidi iterator states
320 ***********************************************************************/
322 #define BIDI_CACHE_CHUNK 200
323 static struct bidi_it *bidi_cache;
324 static ptrdiff_t bidi_cache_size = 0;
325 enum { elsz = sizeof (struct bidi_it) };
326 static ptrdiff_t bidi_cache_idx; /* next unused cache slot */
327 static ptrdiff_t bidi_cache_last_idx; /* slot of last cache hit */
328 static ptrdiff_t bidi_cache_start = 0; /* start of cache for this
329 "stack" level */
331 /* 5-slot stack for saving the start of the previous level of the
332 cache. xdisp.c maintains a 5-slot stack for its iterator state,
333 and we need the same size of our stack. */
334 static ptrdiff_t bidi_cache_start_stack[IT_STACK_SIZE];
335 static int bidi_cache_sp;
337 /* Size of header used by bidi_shelve_cache. */
338 enum
340 bidi_shelve_header_size
341 = (sizeof (bidi_cache_idx) + sizeof (bidi_cache_start_stack)
342 + sizeof (bidi_cache_sp) + sizeof (bidi_cache_start)
343 + sizeof (bidi_cache_last_idx))
346 /* Reset the cache state to the empty state. We only reset the part
347 of the cache relevant to iteration of the current object. Previous
348 objects, which are pushed on the display iterator's stack, are left
349 intact. This is called when the cached information is no more
350 useful for the current iteration, e.g. when we were reseated to a
351 new position on the same object. */
352 static void
353 bidi_cache_reset (void)
355 bidi_cache_idx = bidi_cache_start;
356 bidi_cache_last_idx = -1;
359 /* Shrink the cache to its minimal size. Called when we init the bidi
360 iterator for reordering a buffer or a string that does not come
361 from display properties, because that means all the previously
362 cached info is of no further use. */
363 static void
364 bidi_cache_shrink (void)
366 if (bidi_cache_size > BIDI_CACHE_CHUNK)
368 bidi_cache = xrealloc (bidi_cache, BIDI_CACHE_CHUNK * elsz);
369 bidi_cache_size = BIDI_CACHE_CHUNK;
371 bidi_cache_reset ();
374 static void
375 bidi_cache_fetch_state (ptrdiff_t idx, struct bidi_it *bidi_it)
377 int current_scan_dir = bidi_it->scan_dir;
379 if (idx < bidi_cache_start || idx >= bidi_cache_idx)
380 emacs_abort ();
382 bidi_copy_it (bidi_it, &bidi_cache[idx]);
383 bidi_it->scan_dir = current_scan_dir;
384 bidi_cache_last_idx = idx;
387 /* Find a cached state with a given CHARPOS and resolved embedding
388 level less or equal to LEVEL. if LEVEL is -1, disregard the
389 resolved levels in cached states. DIR, if non-zero, means search
390 in that direction from the last cache hit. */
391 static ptrdiff_t
392 bidi_cache_search (ptrdiff_t charpos, int level, int dir)
394 ptrdiff_t i, i_start;
396 if (bidi_cache_idx > bidi_cache_start)
398 if (bidi_cache_last_idx == -1)
399 bidi_cache_last_idx = bidi_cache_idx - 1;
400 if (charpos < bidi_cache[bidi_cache_last_idx].charpos)
402 dir = -1;
403 i_start = bidi_cache_last_idx - 1;
405 else if (charpos > (bidi_cache[bidi_cache_last_idx].charpos
406 + bidi_cache[bidi_cache_last_idx].nchars - 1))
408 dir = 1;
409 i_start = bidi_cache_last_idx + 1;
411 else if (dir)
412 i_start = bidi_cache_last_idx;
413 else
415 dir = -1;
416 i_start = bidi_cache_idx - 1;
419 if (dir < 0)
421 /* Linear search for now; FIXME! */
422 for (i = i_start; i >= bidi_cache_start; i--)
423 if (bidi_cache[i].charpos <= charpos
424 && charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
425 && (level == -1 || bidi_cache[i].resolved_level <= level))
426 return i;
428 else
430 for (i = i_start; i < bidi_cache_idx; i++)
431 if (bidi_cache[i].charpos <= charpos
432 && charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
433 && (level == -1 || bidi_cache[i].resolved_level <= level))
434 return i;
438 return -1;
441 /* Find a cached state where the resolved level changes to a value
442 that is lower than LEVEL, and return its cache slot index. DIR is
443 the direction to search, starting with the last used cache slot.
444 If DIR is zero, we search backwards from the last occupied cache
445 slot. BEFORE means return the index of the slot that
446 is ``before'' the level change in the search direction. That is,
447 given the cached levels like this:
449 1122333442211
450 AB C
452 and assuming we are at the position cached at the slot marked with
453 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
454 index of slot B or A, depending whether BEFORE is, respectively,
455 true or false. */
456 static ptrdiff_t
457 bidi_cache_find_level_change (int level, int dir, bool before)
459 if (bidi_cache_idx)
461 ptrdiff_t i = dir ? bidi_cache_last_idx : bidi_cache_idx - 1;
462 int incr = before ? 1 : 0;
464 eassert (!dir || bidi_cache_last_idx >= 0);
466 if (!dir)
467 dir = -1;
468 else if (!incr)
469 i += dir;
471 if (dir < 0)
473 while (i >= bidi_cache_start + incr)
475 if (bidi_cache[i - incr].resolved_level >= 0
476 && bidi_cache[i - incr].resolved_level < level)
477 return i;
478 i--;
481 else
483 while (i < bidi_cache_idx - incr)
485 if (bidi_cache[i + incr].resolved_level >= 0
486 && bidi_cache[i + incr].resolved_level < level)
487 return i;
488 i++;
493 return -1;
496 static void
497 bidi_cache_ensure_space (ptrdiff_t idx)
499 /* Enlarge the cache as needed. */
500 if (idx >= bidi_cache_size)
502 /* The bidi cache cannot be larger than the largest Lisp string
503 or buffer. */
504 ptrdiff_t string_or_buffer_bound
505 = max (BUF_BYTES_MAX, STRING_BYTES_BOUND);
507 /* Also, it cannot be larger than what C can represent. */
508 ptrdiff_t c_bound
509 = (min (PTRDIFF_MAX, SIZE_MAX) - bidi_shelve_header_size) / elsz;
511 bidi_cache
512 = xpalloc (bidi_cache, &bidi_cache_size,
513 max (BIDI_CACHE_CHUNK, idx - bidi_cache_size + 1),
514 min (string_or_buffer_bound, c_bound), elsz);
518 static void
519 bidi_cache_iterator_state (struct bidi_it *bidi_it, bool resolved)
521 ptrdiff_t idx;
523 /* We should never cache on backward scans. */
524 if (bidi_it->scan_dir == -1)
525 emacs_abort ();
526 idx = bidi_cache_search (bidi_it->charpos, -1, 1);
528 if (idx < 0)
530 idx = bidi_cache_idx;
531 bidi_cache_ensure_space (idx);
532 /* Character positions should correspond to cache positions 1:1.
533 If we are outside the range of cached positions, the cache is
534 useless and must be reset. */
535 if (idx > bidi_cache_start &&
536 (bidi_it->charpos > (bidi_cache[idx - 1].charpos
537 + bidi_cache[idx - 1].nchars)
538 || bidi_it->charpos < bidi_cache[bidi_cache_start].charpos))
540 bidi_cache_reset ();
541 idx = bidi_cache_start;
543 if (bidi_it->nchars <= 0)
544 emacs_abort ();
545 bidi_copy_it (&bidi_cache[idx], bidi_it);
546 if (!resolved)
547 bidi_cache[idx].resolved_level = -1;
549 else
551 /* Copy only the members which could have changed, to avoid
552 costly copying of the entire struct. */
553 bidi_cache[idx].type = bidi_it->type;
554 bidi_check_type (bidi_it->type);
555 bidi_cache[idx].type_after_w1 = bidi_it->type_after_w1;
556 bidi_check_type (bidi_it->type_after_w1);
557 if (resolved)
558 bidi_cache[idx].resolved_level = bidi_it->resolved_level;
559 else
560 bidi_cache[idx].resolved_level = -1;
561 bidi_cache[idx].invalid_levels = bidi_it->invalid_levels;
562 bidi_cache[idx].invalid_rl_levels = bidi_it->invalid_rl_levels;
563 bidi_cache[idx].next_for_neutral = bidi_it->next_for_neutral;
564 bidi_cache[idx].next_for_ws = bidi_it->next_for_ws;
565 bidi_cache[idx].ignore_bn_limit = bidi_it->ignore_bn_limit;
566 bidi_cache[idx].disp_pos = bidi_it->disp_pos;
567 bidi_cache[idx].disp_prop = bidi_it->disp_prop;
570 bidi_cache_last_idx = idx;
571 if (idx >= bidi_cache_idx)
572 bidi_cache_idx = idx + 1;
575 static bidi_type_t
576 bidi_cache_find (ptrdiff_t charpos, int level, struct bidi_it *bidi_it)
578 ptrdiff_t i = bidi_cache_search (charpos, level, bidi_it->scan_dir);
580 if (i >= bidi_cache_start)
582 bidi_dir_t current_scan_dir = bidi_it->scan_dir;
584 bidi_copy_it (bidi_it, &bidi_cache[i]);
585 bidi_cache_last_idx = i;
586 /* Don't let scan direction from the cached state override
587 the current scan direction. */
588 bidi_it->scan_dir = current_scan_dir;
589 return bidi_it->type;
592 return UNKNOWN_BT;
595 static int
596 bidi_peek_at_next_level (struct bidi_it *bidi_it)
598 if (bidi_cache_idx == bidi_cache_start || bidi_cache_last_idx == -1)
599 emacs_abort ();
600 return bidi_cache[bidi_cache_last_idx + bidi_it->scan_dir].resolved_level;
604 /***********************************************************************
605 Pushing and popping the bidi iterator state
606 ***********************************************************************/
608 /* Push the bidi iterator state in preparation for reordering a
609 different object, e.g. display string found at certain buffer
610 position. Pushing the bidi iterator boils down to saving its
611 entire state on the cache and starting a new cache "stacked" on top
612 of the current cache. */
613 void
614 bidi_push_it (struct bidi_it *bidi_it)
616 /* Save the current iterator state in its entirety after the last
617 used cache slot. */
618 bidi_cache_ensure_space (bidi_cache_idx);
619 bidi_cache[bidi_cache_idx++] = *bidi_it;
621 /* Push the current cache start onto the stack. */
622 eassert (bidi_cache_sp < IT_STACK_SIZE);
623 bidi_cache_start_stack[bidi_cache_sp++] = bidi_cache_start;
625 /* Start a new level of cache, and make it empty. */
626 bidi_cache_start = bidi_cache_idx;
627 bidi_cache_last_idx = -1;
630 /* Restore the iterator state saved by bidi_push_it and return the
631 cache to the corresponding state. */
632 void
633 bidi_pop_it (struct bidi_it *bidi_it)
635 if (bidi_cache_start <= 0)
636 emacs_abort ();
638 /* Reset the next free cache slot index to what it was before the
639 call to bidi_push_it. */
640 bidi_cache_idx = bidi_cache_start - 1;
642 /* Restore the bidi iterator state saved in the cache. */
643 *bidi_it = bidi_cache[bidi_cache_idx];
645 /* Pop the previous cache start from the stack. */
646 if (bidi_cache_sp <= 0)
647 emacs_abort ();
648 bidi_cache_start = bidi_cache_start_stack[--bidi_cache_sp];
650 /* Invalidate the last-used cache slot data. */
651 bidi_cache_last_idx = -1;
654 static ptrdiff_t bidi_cache_total_alloc;
656 /* Stash away a copy of the cache and its control variables. */
657 void *
658 bidi_shelve_cache (void)
660 unsigned char *databuf;
661 ptrdiff_t alloc;
663 /* Empty cache. */
664 if (bidi_cache_idx == 0)
665 return NULL;
667 alloc = (bidi_shelve_header_size
668 + bidi_cache_idx * sizeof (struct bidi_it));
669 databuf = xmalloc (alloc);
670 bidi_cache_total_alloc += alloc;
672 memcpy (databuf, &bidi_cache_idx, sizeof (bidi_cache_idx));
673 memcpy (databuf + sizeof (bidi_cache_idx),
674 bidi_cache, bidi_cache_idx * sizeof (struct bidi_it));
675 memcpy (databuf + sizeof (bidi_cache_idx)
676 + bidi_cache_idx * sizeof (struct bidi_it),
677 bidi_cache_start_stack, sizeof (bidi_cache_start_stack));
678 memcpy (databuf + sizeof (bidi_cache_idx)
679 + bidi_cache_idx * sizeof (struct bidi_it)
680 + sizeof (bidi_cache_start_stack),
681 &bidi_cache_sp, sizeof (bidi_cache_sp));
682 memcpy (databuf + sizeof (bidi_cache_idx)
683 + bidi_cache_idx * sizeof (struct bidi_it)
684 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
685 &bidi_cache_start, sizeof (bidi_cache_start));
686 memcpy (databuf + sizeof (bidi_cache_idx)
687 + bidi_cache_idx * sizeof (struct bidi_it)
688 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
689 + sizeof (bidi_cache_start),
690 &bidi_cache_last_idx, sizeof (bidi_cache_last_idx));
692 return databuf;
695 /* Restore the cache state from a copy stashed away by
696 bidi_shelve_cache, and free the buffer used to stash that copy.
697 JUST_FREE means free the buffer, but don't restore the
698 cache; used when the corresponding iterator is discarded instead of
699 being restored. */
700 void
701 bidi_unshelve_cache (void *databuf, bool just_free)
703 unsigned char *p = databuf;
705 if (!p)
707 if (!just_free)
709 /* A NULL pointer means an empty cache. */
710 bidi_cache_start = 0;
711 bidi_cache_sp = 0;
712 bidi_cache_reset ();
715 else
717 if (just_free)
719 ptrdiff_t idx;
721 memcpy (&idx, p, sizeof (bidi_cache_idx));
722 bidi_cache_total_alloc
723 -= bidi_shelve_header_size + idx * sizeof (struct bidi_it);
725 else
727 memcpy (&bidi_cache_idx, p, sizeof (bidi_cache_idx));
728 bidi_cache_ensure_space (bidi_cache_idx);
729 memcpy (bidi_cache, p + sizeof (bidi_cache_idx),
730 bidi_cache_idx * sizeof (struct bidi_it));
731 memcpy (bidi_cache_start_stack,
732 p + sizeof (bidi_cache_idx)
733 + bidi_cache_idx * sizeof (struct bidi_it),
734 sizeof (bidi_cache_start_stack));
735 memcpy (&bidi_cache_sp,
736 p + sizeof (bidi_cache_idx)
737 + bidi_cache_idx * sizeof (struct bidi_it)
738 + sizeof (bidi_cache_start_stack),
739 sizeof (bidi_cache_sp));
740 memcpy (&bidi_cache_start,
741 p + sizeof (bidi_cache_idx)
742 + bidi_cache_idx * sizeof (struct bidi_it)
743 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
744 sizeof (bidi_cache_start));
745 memcpy (&bidi_cache_last_idx,
746 p + sizeof (bidi_cache_idx)
747 + bidi_cache_idx * sizeof (struct bidi_it)
748 + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
749 + sizeof (bidi_cache_start),
750 sizeof (bidi_cache_last_idx));
751 bidi_cache_total_alloc
752 -= (bidi_shelve_header_size
753 + bidi_cache_idx * sizeof (struct bidi_it));
756 xfree (p);
761 /***********************************************************************
762 Initialization
763 ***********************************************************************/
764 static void
765 bidi_initialize (void)
767 bidi_type_table = uniprop_table (intern ("bidi-class"));
768 if (NILP (bidi_type_table))
769 emacs_abort ();
770 staticpro (&bidi_type_table);
772 bidi_mirror_table = uniprop_table (intern ("mirroring"));
773 if (NILP (bidi_mirror_table))
774 emacs_abort ();
775 staticpro (&bidi_mirror_table);
777 Qparagraph_start = intern ("paragraph-start");
778 staticpro (&Qparagraph_start);
779 paragraph_start_re = Fsymbol_value (Qparagraph_start);
780 if (!STRINGP (paragraph_start_re))
781 paragraph_start_re = build_string ("\f\\|[ \t]*$");
782 staticpro (&paragraph_start_re);
783 Qparagraph_separate = intern ("paragraph-separate");
784 staticpro (&Qparagraph_separate);
785 paragraph_separate_re = Fsymbol_value (Qparagraph_separate);
786 if (!STRINGP (paragraph_separate_re))
787 paragraph_separate_re = build_string ("[ \t\f]*$");
788 staticpro (&paragraph_separate_re);
790 bidi_cache_sp = 0;
791 bidi_cache_total_alloc = 0;
793 bidi_initialized = 1;
796 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
797 end. */
798 static void
799 bidi_set_paragraph_end (struct bidi_it *bidi_it)
801 bidi_it->invalid_levels = 0;
802 bidi_it->invalid_rl_levels = -1;
803 bidi_it->stack_idx = 0;
804 bidi_it->resolved_level = bidi_it->level_stack[0].level;
807 /* Initialize the bidi iterator from buffer/string position CHARPOS. */
808 void
809 bidi_init_it (ptrdiff_t charpos, ptrdiff_t bytepos, bool frame_window_p,
810 struct bidi_it *bidi_it)
812 if (! bidi_initialized)
813 bidi_initialize ();
814 if (charpos >= 0)
815 bidi_it->charpos = charpos;
816 if (bytepos >= 0)
817 bidi_it->bytepos = bytepos;
818 bidi_it->frame_window_p = frame_window_p;
819 bidi_it->nchars = -1; /* to be computed in bidi_resolve_explicit_1 */
820 bidi_it->first_elt = 1;
821 bidi_set_paragraph_end (bidi_it);
822 bidi_it->new_paragraph = 1;
823 bidi_it->separator_limit = -1;
824 bidi_it->type = NEUTRAL_B;
825 bidi_it->type_after_w1 = NEUTRAL_B;
826 bidi_it->orig_type = NEUTRAL_B;
827 bidi_it->prev_was_pdf = 0;
828 bidi_it->prev.type = bidi_it->prev.type_after_w1
829 = bidi_it->prev.orig_type = UNKNOWN_BT;
830 bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1
831 = bidi_it->last_strong.orig_type = UNKNOWN_BT;
832 bidi_it->next_for_neutral.charpos = -1;
833 bidi_it->next_for_neutral.type
834 = bidi_it->next_for_neutral.type_after_w1
835 = bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
836 bidi_it->prev_for_neutral.charpos = -1;
837 bidi_it->prev_for_neutral.type
838 = bidi_it->prev_for_neutral.type_after_w1
839 = bidi_it->prev_for_neutral.orig_type = UNKNOWN_BT;
840 bidi_it->sor = L2R; /* FIXME: should it be user-selectable? */
841 bidi_it->disp_pos = -1; /* invalid/unknown */
842 bidi_it->disp_prop = 0;
843 /* We can only shrink the cache if we are at the bottom level of its
844 "stack". */
845 if (bidi_cache_start == 0)
846 bidi_cache_shrink ();
847 else
848 bidi_cache_reset ();
851 /* Perform initializations for reordering a new line of bidi text. */
852 static void
853 bidi_line_init (struct bidi_it *bidi_it)
855 bidi_it->scan_dir = 1; /* FIXME: do we need to have control on this? */
856 bidi_it->resolved_level = bidi_it->level_stack[0].level;
857 bidi_it->level_stack[0].override = NEUTRAL_DIR; /* X1 */
858 bidi_it->invalid_levels = 0;
859 bidi_it->invalid_rl_levels = -1;
860 /* Setting this to zero will force its recomputation the first time
861 we need it for W5. */
862 bidi_it->next_en_pos = 0;
863 bidi_it->next_en_type = UNKNOWN_BT;
864 bidi_it->next_for_ws.type = UNKNOWN_BT;
865 bidi_set_sor_type (bidi_it,
866 (bidi_it->paragraph_dir == R2L ? 1 : 0),
867 bidi_it->level_stack[0].level); /* X10 */
869 bidi_cache_reset ();
873 /***********************************************************************
874 Fetching characters
875 ***********************************************************************/
877 /* Count bytes in string S between BEG/BEGBYTE and END. BEG and END
878 are zero-based character positions in S, BEGBYTE is byte position
879 corresponding to BEG. UNIBYTE means S is a unibyte string. */
880 static ptrdiff_t
881 bidi_count_bytes (const unsigned char *s, ptrdiff_t beg,
882 ptrdiff_t begbyte, ptrdiff_t end, bool unibyte)
884 ptrdiff_t pos = beg;
885 const unsigned char *p = s + begbyte, *start = p;
887 if (unibyte)
888 p = s + end;
889 else
891 if (!CHAR_HEAD_P (*p))
892 emacs_abort ();
894 while (pos < end)
896 p += BYTES_BY_CHAR_HEAD (*p);
897 pos++;
901 return p - start;
904 /* Fetch and return the character at byte position BYTEPOS. If S is
905 non-NULL, fetch the character from string S; otherwise fetch the
906 character from the current buffer. UNIBYTE means S is a
907 unibyte string. */
908 static int
909 bidi_char_at_pos (ptrdiff_t bytepos, const unsigned char *s, bool unibyte)
911 if (s)
913 s += bytepos;
914 if (unibyte)
915 return *s;
917 else
918 s = BYTE_POS_ADDR (bytepos);
919 return STRING_CHAR (s);
922 /* Fetch and return the character at CHARPOS/BYTEPOS. If that
923 character is covered by a display string, treat the entire run of
924 covered characters as a single character, either u+2029 or u+FFFC,
925 and return their combined length in CH_LEN and NCHARS. DISP_POS
926 specifies the character position of the next display string, or -1
927 if not yet computed. When the next character is at or beyond that
928 position, the function updates DISP_POS with the position of the
929 next display string. *DISP_PROP non-zero means that there's really
930 a display string at DISP_POS, as opposed to when we searched till
931 DISP_POS without finding one. If *DISP_PROP is 2, it means the
932 display spec is of the form `(space ...)', which is replaced with
933 u+2029 to handle it as a paragraph separator. STRING->s is the C
934 string to iterate, or NULL if iterating over a buffer or a Lisp
935 string; in the latter case, STRING->lstring is the Lisp string. */
936 static int
937 bidi_fetch_char (ptrdiff_t charpos, ptrdiff_t bytepos, ptrdiff_t *disp_pos,
938 int *disp_prop, struct bidi_string_data *string,
939 struct window *w,
940 bool frame_window_p, ptrdiff_t *ch_len, ptrdiff_t *nchars)
942 int ch;
943 ptrdiff_t endpos
944 = (string->s || STRINGP (string->lstring)) ? string->schars : ZV;
945 struct text_pos pos;
946 int len;
948 /* If we got past the last known position of display string, compute
949 the position of the next one. That position could be at CHARPOS. */
950 if (charpos < endpos && charpos > *disp_pos)
952 SET_TEXT_POS (pos, charpos, bytepos);
953 *disp_pos = compute_display_string_pos (&pos, string, w, frame_window_p,
954 disp_prop);
957 /* Fetch the character at BYTEPOS. */
958 if (charpos >= endpos)
960 ch = BIDI_EOB;
961 *ch_len = 1;
962 *nchars = 1;
963 *disp_pos = endpos;
964 *disp_prop = 0;
966 else if (charpos >= *disp_pos && *disp_prop)
968 ptrdiff_t disp_end_pos;
970 /* We don't expect to find ourselves in the middle of a display
971 property. Hopefully, it will never be needed. */
972 if (charpos > *disp_pos)
973 emacs_abort ();
974 /* Text covered by `display' properties and overlays with
975 display properties or display strings is handled as a single
976 character that represents the entire run of characters
977 covered by the display property. */
978 if (*disp_prop == 2)
980 /* `(space ...)' display specs are handled as paragraph
981 separators for the purposes of the reordering; see UAX#9
982 section 3 and clause HL1 in section 4.3 there. */
983 ch = 0x2029;
985 else
987 /* All other display specs are handled as the Unicode Object
988 Replacement Character. */
989 ch = 0xFFFC;
991 disp_end_pos = compute_display_string_end (*disp_pos, string);
992 if (disp_end_pos < 0)
994 /* Somebody removed the display string from the buffer
995 behind our back. Recover by processing this buffer
996 position as if no display property were present there to
997 begin with. */
998 *disp_prop = 0;
999 goto normal_char;
1001 *nchars = disp_end_pos - *disp_pos;
1002 if (*nchars <= 0)
1003 emacs_abort ();
1004 if (string->s)
1005 *ch_len = bidi_count_bytes (string->s, *disp_pos, bytepos,
1006 disp_end_pos, string->unibyte);
1007 else if (STRINGP (string->lstring))
1008 *ch_len = bidi_count_bytes (SDATA (string->lstring), *disp_pos,
1009 bytepos, disp_end_pos, string->unibyte);
1010 else
1011 *ch_len = CHAR_TO_BYTE (disp_end_pos) - bytepos;
1013 else
1015 normal_char:
1016 if (string->s)
1019 if (!string->unibyte)
1021 ch = STRING_CHAR_AND_LENGTH (string->s + bytepos, len);
1022 *ch_len = len;
1024 else
1026 ch = UNIBYTE_TO_CHAR (string->s[bytepos]);
1027 *ch_len = 1;
1030 else if (STRINGP (string->lstring))
1032 if (!string->unibyte)
1034 ch = STRING_CHAR_AND_LENGTH (SDATA (string->lstring) + bytepos,
1035 len);
1036 *ch_len = len;
1038 else
1040 ch = UNIBYTE_TO_CHAR (SREF (string->lstring, bytepos));
1041 *ch_len = 1;
1044 else
1046 ch = STRING_CHAR_AND_LENGTH (BYTE_POS_ADDR (bytepos), len);
1047 *ch_len = len;
1049 *nchars = 1;
1052 /* If we just entered a run of characters covered by a display
1053 string, compute the position of the next display string. */
1054 if (charpos + *nchars <= endpos && charpos + *nchars > *disp_pos
1055 && *disp_prop)
1057 SET_TEXT_POS (pos, charpos + *nchars, bytepos + *ch_len);
1058 *disp_pos = compute_display_string_pos (&pos, string, w, frame_window_p,
1059 disp_prop);
1062 return ch;
1066 /***********************************************************************
1067 Determining paragraph direction
1068 ***********************************************************************/
1070 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
1071 Value is the non-negative length of the paragraph separator
1072 following the buffer position, -1 if position is at the beginning
1073 of a new paragraph, or -2 if position is neither at beginning nor
1074 at end of a paragraph. */
1075 static ptrdiff_t
1076 bidi_at_paragraph_end (ptrdiff_t charpos, ptrdiff_t bytepos)
1078 Lisp_Object sep_re;
1079 Lisp_Object start_re;
1080 ptrdiff_t val;
1082 sep_re = paragraph_separate_re;
1083 start_re = paragraph_start_re;
1085 val = fast_looking_at (sep_re, charpos, bytepos, ZV, ZV_BYTE, Qnil);
1086 if (val < 0)
1088 if (fast_looking_at (start_re, charpos, bytepos, ZV, ZV_BYTE, Qnil) >= 0)
1089 val = -1;
1090 else
1091 val = -2;
1094 return val;
1097 /* If the user has requested the long scans caching, make sure that
1098 BIDI cache is enabled. Otherwise, make sure it's disabled. */
1100 static struct region_cache *
1101 bidi_paragraph_cache_on_off (void)
1103 struct buffer *cache_buffer = current_buffer;
1104 bool indirect_p = false;
1106 /* For indirect buffers, make sure to use the cache of their base
1107 buffer. */
1108 if (cache_buffer->base_buffer)
1110 cache_buffer = cache_buffer->base_buffer;
1111 indirect_p = true;
1114 /* Don't turn on or off the cache in the base buffer, if the value
1115 of cache-long-scans of the base buffer is inconsistent with that.
1116 This is because doing so will just make the cache pure overhead,
1117 since if we turn it on via indirect buffer, it will be
1118 immediately turned off by its base buffer. */
1119 if (NILP (BVAR (current_buffer, cache_long_scans)))
1121 if (!indirect_p
1122 || NILP (BVAR (cache_buffer, cache_long_scans)))
1124 if (cache_buffer->bidi_paragraph_cache)
1126 free_region_cache (cache_buffer->bidi_paragraph_cache);
1127 cache_buffer->bidi_paragraph_cache = 0;
1130 return NULL;
1132 else
1134 if (!indirect_p
1135 || !NILP (BVAR (cache_buffer, cache_long_scans)))
1137 if (!cache_buffer->bidi_paragraph_cache)
1138 cache_buffer->bidi_paragraph_cache = new_region_cache ();
1140 return cache_buffer->bidi_paragraph_cache;
1144 /* On my 2005-vintage machine, searching back for paragraph start
1145 takes ~1 ms per line. And bidi_paragraph_init is called 4 times
1146 when user types C-p. The number below limits each call to
1147 bidi_paragraph_init to about 10 ms. */
1148 #define MAX_PARAGRAPH_SEARCH 7500
1150 /* Find the beginning of this paragraph by looking back in the buffer.
1151 Value is the byte position of the paragraph's beginning, or
1152 BEGV_BYTE if paragraph_start_re is still not found after looking
1153 back MAX_PARAGRAPH_SEARCH lines in the buffer. */
1154 static ptrdiff_t
1155 bidi_find_paragraph_start (ptrdiff_t pos, ptrdiff_t pos_byte)
1157 Lisp_Object re = paragraph_start_re;
1158 ptrdiff_t limit = ZV, limit_byte = ZV_BYTE;
1159 struct region_cache *bpc = bidi_paragraph_cache_on_off ();
1160 ptrdiff_t n = 0, oldpos = pos, next;
1161 struct buffer *cache_buffer = current_buffer;
1163 if (cache_buffer->base_buffer)
1164 cache_buffer = cache_buffer->base_buffer;
1166 while (pos_byte > BEGV_BYTE
1167 && n++ < MAX_PARAGRAPH_SEARCH
1168 && fast_looking_at (re, pos, pos_byte, limit, limit_byte, Qnil) < 0)
1170 /* FIXME: What if the paragraph beginning is covered by a
1171 display string? And what if a display string covering some
1172 of the text over which we scan back includes
1173 paragraph_start_re? */
1174 DEC_BOTH (pos, pos_byte);
1175 if (bpc && region_cache_backward (cache_buffer, bpc, pos, &next))
1177 pos = next, pos_byte = CHAR_TO_BYTE (pos);
1178 break;
1180 else
1181 pos = find_newline_no_quit (pos, pos_byte, -1, &pos_byte);
1183 if (n >= MAX_PARAGRAPH_SEARCH)
1184 pos = BEGV, pos_byte = BEGV_BYTE;
1185 if (bpc)
1186 know_region_cache (cache_buffer, bpc, pos, oldpos);
1187 /* Positions returned by the region cache are not limited to
1188 BEGV..ZV range, so we limit them here. */
1189 pos_byte = clip_to_bounds (BEGV_BYTE, pos_byte, ZV_BYTE);
1190 return pos_byte;
1193 /* On a 3.4 GHz machine, searching forward for a strong directional
1194 character in a long paragraph full of weaks or neutrals takes about
1195 1 ms for each 20K characters. The number below limits each call to
1196 bidi_paragraph_init to less than 10 ms even on slow machines. */
1197 #define MAX_STRONG_CHAR_SEARCH 100000
1199 /* Determine the base direction, a.k.a. base embedding level, of the
1200 paragraph we are about to iterate through. If DIR is either L2R or
1201 R2L, just use that. Otherwise, determine the paragraph direction
1202 from the first strong directional character of the paragraph.
1204 NO_DEFAULT_P means don't default to L2R if the paragraph
1205 has no strong directional characters and both DIR and
1206 bidi_it->paragraph_dir are NEUTRAL_DIR. In that case, search back
1207 in the buffer until a paragraph is found with a strong character,
1208 or until hitting BEGV. In the latter case, fall back to L2R. This
1209 flag is used in current-bidi-paragraph-direction.
1211 Note that this function gives the paragraph separator the same
1212 direction as the preceding paragraph, even though Emacs generally
1213 views the separator as not belonging to any paragraph. */
1214 void
1215 bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, bool no_default_p)
1217 ptrdiff_t bytepos = bidi_it->bytepos;
1218 bool string_p = bidi_it->string.s || STRINGP (bidi_it->string.lstring);
1219 ptrdiff_t pstartbyte;
1220 /* Note that begbyte is a byte position, while end is a character
1221 position. Yes, this is ugly, but we are trying to avoid costly
1222 calls to BYTE_TO_CHAR and its ilk. */
1223 ptrdiff_t begbyte = string_p ? 0 : BEGV_BYTE;
1224 ptrdiff_t end = string_p ? bidi_it->string.schars : ZV;
1226 /* Special case for an empty buffer. */
1227 if (bytepos == begbyte && bidi_it->charpos == end)
1228 dir = L2R;
1229 /* We should never be called at EOB or before BEGV. */
1230 else if (bidi_it->charpos >= end || bytepos < begbyte)
1231 emacs_abort ();
1233 if (dir == L2R)
1235 bidi_it->paragraph_dir = L2R;
1236 bidi_it->new_paragraph = 0;
1238 else if (dir == R2L)
1240 bidi_it->paragraph_dir = R2L;
1241 bidi_it->new_paragraph = 0;
1243 else if (dir == NEUTRAL_DIR) /* P2 */
1245 int ch;
1246 ptrdiff_t ch_len, nchars;
1247 ptrdiff_t pos, disp_pos = -1;
1248 int disp_prop = 0;
1249 bidi_type_t type;
1250 const unsigned char *s;
1252 if (!bidi_initialized)
1253 bidi_initialize ();
1255 /* If we are inside a paragraph separator, we are just waiting
1256 for the separator to be exhausted; use the previous paragraph
1257 direction. But don't do that if we have been just reseated,
1258 because we need to reinitialize below in that case. */
1259 if (!bidi_it->first_elt
1260 && bidi_it->charpos < bidi_it->separator_limit)
1261 return;
1263 /* If we are on a newline, get past it to where the next
1264 paragraph might start. But don't do that at BEGV since then
1265 we are potentially in a new paragraph that doesn't yet
1266 exist. */
1267 pos = bidi_it->charpos;
1268 s = (STRINGP (bidi_it->string.lstring)
1269 ? SDATA (bidi_it->string.lstring)
1270 : bidi_it->string.s);
1271 if (bytepos > begbyte
1272 && bidi_char_at_pos (bytepos, s, bidi_it->string.unibyte) == '\n')
1274 bytepos++;
1275 pos++;
1278 /* We are either at the beginning of a paragraph or in the
1279 middle of it. Find where this paragraph starts. */
1280 if (string_p)
1282 /* We don't support changes of paragraph direction inside a
1283 string. It is treated as a single paragraph. */
1284 pstartbyte = 0;
1286 else
1287 pstartbyte = bidi_find_paragraph_start (pos, bytepos);
1288 bidi_it->separator_limit = -1;
1289 bidi_it->new_paragraph = 0;
1291 /* The following loop is run more than once only if NO_DEFAULT_P,
1292 and only if we are iterating on a buffer. */
1293 do {
1294 ptrdiff_t pos1;
1296 bytepos = pstartbyte;
1297 if (!string_p)
1298 pos = BYTE_TO_CHAR (bytepos);
1299 ch = bidi_fetch_char (pos, bytepos, &disp_pos, &disp_prop,
1300 &bidi_it->string, bidi_it->w,
1301 bidi_it->frame_window_p, &ch_len, &nchars);
1302 type = bidi_get_type (ch, NEUTRAL_DIR);
1304 pos1 = pos;
1305 for (pos += nchars, bytepos += ch_len;
1306 ((bidi_get_category (type) != STRONG)
1307 || (bidi_ignore_explicit_marks_for_paragraph_level
1308 && (type == RLE || type == RLO
1309 || type == LRE || type == LRO)))
1310 /* Stop when searched too far into an abnormally large
1311 paragraph full of weak or neutral characters. */
1312 && pos - pos1 < MAX_STRONG_CHAR_SEARCH;
1313 type = bidi_get_type (ch, NEUTRAL_DIR))
1315 if (pos >= end)
1317 /* Pretend there's a paragraph separator at end of
1318 buffer/string. */
1319 type = NEUTRAL_B;
1320 break;
1322 if (!string_p
1323 && type == NEUTRAL_B
1324 && bidi_at_paragraph_end (pos, bytepos) >= -1)
1325 break;
1326 /* Fetch next character and advance to get past it. */
1327 ch = bidi_fetch_char (pos, bytepos, &disp_pos,
1328 &disp_prop, &bidi_it->string, bidi_it->w,
1329 bidi_it->frame_window_p, &ch_len, &nchars);
1330 pos += nchars;
1331 bytepos += ch_len;
1333 if ((type == STRONG_R || type == STRONG_AL) /* P3 */
1334 || (!bidi_ignore_explicit_marks_for_paragraph_level
1335 && (type == RLO || type == RLE)))
1336 bidi_it->paragraph_dir = R2L;
1337 else if (type == STRONG_L
1338 || (!bidi_ignore_explicit_marks_for_paragraph_level
1339 && (type == LRO || type == LRE)))
1340 bidi_it->paragraph_dir = L2R;
1341 if (!string_p
1342 && no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR)
1344 /* If this paragraph is at BEGV, default to L2R. */
1345 if (pstartbyte == BEGV_BYTE)
1346 bidi_it->paragraph_dir = L2R; /* P3 and HL1 */
1347 else
1349 ptrdiff_t prevpbyte = pstartbyte;
1350 ptrdiff_t p = BYTE_TO_CHAR (pstartbyte), pbyte = pstartbyte;
1352 /* Find the beginning of the previous paragraph, if any. */
1353 while (pbyte > BEGV_BYTE && prevpbyte >= pstartbyte)
1355 /* FXIME: What if p is covered by a display
1356 string? See also a FIXME inside
1357 bidi_find_paragraph_start. */
1358 DEC_BOTH (p, pbyte);
1359 prevpbyte = bidi_find_paragraph_start (p, pbyte);
1361 pstartbyte = prevpbyte;
1364 } while (!string_p
1365 && no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR);
1367 else
1368 emacs_abort ();
1370 /* Contrary to UAX#9 clause P3, we only default the paragraph
1371 direction to L2R if we have no previous usable paragraph
1372 direction. This is allowed by the HL1 clause. */
1373 if (bidi_it->paragraph_dir != L2R && bidi_it->paragraph_dir != R2L)
1374 bidi_it->paragraph_dir = L2R; /* P3 and HL1 ``higher-level protocols'' */
1375 if (bidi_it->paragraph_dir == R2L)
1376 bidi_it->level_stack[0].level = 1;
1377 else
1378 bidi_it->level_stack[0].level = 0;
1380 bidi_line_init (bidi_it);
1384 /***********************************************************************
1385 Resolving explicit and implicit levels.
1386 The rest of this file constitutes the core of the UBA implementation.
1387 ***********************************************************************/
1389 static bool
1390 bidi_explicit_dir_char (int ch)
1392 bidi_type_t ch_type;
1394 if (!bidi_initialized)
1395 emacs_abort ();
1396 ch_type = (bidi_type_t) XINT (CHAR_TABLE_REF (bidi_type_table, ch));
1397 return (ch_type == LRE || ch_type == LRO
1398 || ch_type == RLE || ch_type == RLO
1399 || ch_type == PDF);
1402 /* A helper function for bidi_resolve_explicit. It advances to the
1403 next character in logical order and determines the new embedding
1404 level and directional override, but does not take into account
1405 empty embeddings. */
1406 static int
1407 bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
1409 int curchar;
1410 bidi_type_t type;
1411 int current_level;
1412 int new_level;
1413 bidi_dir_t override;
1414 bool string_p = bidi_it->string.s || STRINGP (bidi_it->string.lstring);
1416 /* If reseat()'ed, don't advance, so as to start iteration from the
1417 position where we were reseated. bidi_it->bytepos can be less
1418 than BEGV_BYTE after reseat to BEGV. */
1419 if (bidi_it->bytepos < (string_p ? 0 : BEGV_BYTE)
1420 || bidi_it->first_elt)
1422 bidi_it->first_elt = 0;
1423 if (string_p)
1425 const unsigned char *p
1426 = (STRINGP (bidi_it->string.lstring)
1427 ? SDATA (bidi_it->string.lstring)
1428 : bidi_it->string.s);
1430 if (bidi_it->charpos < 0)
1431 bidi_it->charpos = bidi_it->bytepos = 0;
1432 eassert (bidi_it->bytepos == bidi_count_bytes (p, 0, 0,
1433 bidi_it->charpos,
1434 bidi_it->string.unibyte));
1436 else
1438 if (bidi_it->charpos < BEGV)
1440 bidi_it->charpos = BEGV;
1441 bidi_it->bytepos = BEGV_BYTE;
1443 eassert (bidi_it->bytepos == CHAR_TO_BYTE (bidi_it->charpos));
1446 /* Don't move at end of buffer/string. */
1447 else if (bidi_it->charpos < (string_p ? bidi_it->string.schars : ZV))
1449 /* Advance to the next character, skipping characters covered by
1450 display strings (nchars > 1). */
1451 if (bidi_it->nchars <= 0)
1452 emacs_abort ();
1453 bidi_it->charpos += bidi_it->nchars;
1454 if (bidi_it->ch_len == 0)
1455 emacs_abort ();
1456 bidi_it->bytepos += bidi_it->ch_len;
1459 current_level = bidi_it->level_stack[bidi_it->stack_idx].level; /* X1 */
1460 override = bidi_it->level_stack[bidi_it->stack_idx].override;
1461 new_level = current_level;
1463 if (bidi_it->charpos >= (string_p ? bidi_it->string.schars : ZV))
1465 curchar = BIDI_EOB;
1466 bidi_it->ch_len = 1;
1467 bidi_it->nchars = 1;
1468 bidi_it->disp_pos = (string_p ? bidi_it->string.schars : ZV);
1469 bidi_it->disp_prop = 0;
1471 else
1473 /* Fetch the character at BYTEPOS. If it is covered by a
1474 display string, treat the entire run of covered characters as
1475 a single character u+FFFC. */
1476 curchar = bidi_fetch_char (bidi_it->charpos, bidi_it->bytepos,
1477 &bidi_it->disp_pos, &bidi_it->disp_prop,
1478 &bidi_it->string, bidi_it->w,
1479 bidi_it->frame_window_p,
1480 &bidi_it->ch_len, &bidi_it->nchars);
1482 bidi_it->ch = curchar;
1484 /* Don't apply directional override here, as all the types we handle
1485 below will not be affected by the override anyway, and we need
1486 the original type unaltered. The override will be applied in
1487 bidi_resolve_weak. */
1488 type = bidi_get_type (curchar, NEUTRAL_DIR);
1489 bidi_it->orig_type = type;
1490 bidi_check_type (bidi_it->orig_type);
1492 if (type != PDF)
1493 bidi_it->prev_was_pdf = 0;
1495 bidi_it->type_after_w1 = UNKNOWN_BT;
1497 switch (type)
1499 case RLE: /* X2 */
1500 case RLO: /* X4 */
1501 bidi_it->type_after_w1 = type;
1502 bidi_check_type (bidi_it->type_after_w1);
1503 type = WEAK_BN; /* X9/Retaining */
1504 if (bidi_it->ignore_bn_limit <= -1)
1506 if (current_level <= BIDI_MAXLEVEL - 4)
1508 /* Compute the least odd embedding level greater than
1509 the current level. */
1510 new_level = ((current_level + 1) & ~1) + 1;
1511 if (bidi_it->type_after_w1 == RLE)
1512 override = NEUTRAL_DIR;
1513 else
1514 override = R2L;
1515 if (current_level == BIDI_MAXLEVEL - 4)
1516 bidi_it->invalid_rl_levels = 0;
1517 bidi_push_embedding_level (bidi_it, new_level, override);
1519 else
1521 bidi_it->invalid_levels++;
1522 /* See the commentary about invalid_rl_levels below. */
1523 if (bidi_it->invalid_rl_levels < 0)
1524 bidi_it->invalid_rl_levels = 0;
1525 bidi_it->invalid_rl_levels++;
1528 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1529 || (bidi_it->next_en_pos > bidi_it->charpos
1530 && bidi_it->next_en_type == WEAK_EN))
1531 type = WEAK_EN;
1532 break;
1533 case LRE: /* X3 */
1534 case LRO: /* X5 */
1535 bidi_it->type_after_w1 = type;
1536 bidi_check_type (bidi_it->type_after_w1);
1537 type = WEAK_BN; /* X9/Retaining */
1538 if (bidi_it->ignore_bn_limit <= -1)
1540 if (current_level <= BIDI_MAXLEVEL - 5)
1542 /* Compute the least even embedding level greater than
1543 the current level. */
1544 new_level = ((current_level + 2) & ~1);
1545 if (bidi_it->type_after_w1 == LRE)
1546 override = NEUTRAL_DIR;
1547 else
1548 override = L2R;
1549 bidi_push_embedding_level (bidi_it, new_level, override);
1551 else
1553 bidi_it->invalid_levels++;
1554 /* invalid_rl_levels counts invalid levels encountered
1555 while the embedding level was already too high for
1556 LRE/LRO, but not for RLE/RLO. That is because
1557 there may be exactly one PDF which we should not
1558 ignore even though invalid_levels is non-zero.
1559 invalid_rl_levels helps to know what PDF is
1560 that. */
1561 if (bidi_it->invalid_rl_levels >= 0)
1562 bidi_it->invalid_rl_levels++;
1565 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1566 || (bidi_it->next_en_pos > bidi_it->charpos
1567 && bidi_it->next_en_type == WEAK_EN))
1568 type = WEAK_EN;
1569 break;
1570 case PDF: /* X7 */
1571 bidi_it->type_after_w1 = type;
1572 bidi_check_type (bidi_it->type_after_w1);
1573 type = WEAK_BN; /* X9/Retaining */
1574 if (bidi_it->ignore_bn_limit <= -1)
1576 if (!bidi_it->invalid_rl_levels)
1578 new_level = bidi_pop_embedding_level (bidi_it);
1579 bidi_it->invalid_rl_levels = -1;
1580 if (bidi_it->invalid_levels)
1581 bidi_it->invalid_levels--;
1582 /* else nothing: UAX#9 says to ignore invalid PDFs */
1584 if (!bidi_it->invalid_levels)
1585 new_level = bidi_pop_embedding_level (bidi_it);
1586 else
1588 bidi_it->invalid_levels--;
1589 bidi_it->invalid_rl_levels--;
1592 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1593 || (bidi_it->next_en_pos > bidi_it->charpos
1594 && bidi_it->next_en_type == WEAK_EN))
1595 type = WEAK_EN;
1596 break;
1597 default:
1598 /* Nothing. */
1599 break;
1602 bidi_it->type = type;
1603 bidi_check_type (bidi_it->type);
1605 return new_level;
1608 /* Given an iterator state in BIDI_IT, advance one character position
1609 in the buffer/string to the next character (in the logical order),
1610 resolve any explicit embeddings and directional overrides, and
1611 return the embedding level of the character after resolving
1612 explicit directives and ignoring empty embeddings. */
1613 static int
1614 bidi_resolve_explicit (struct bidi_it *bidi_it)
1616 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1617 int new_level = bidi_resolve_explicit_1 (bidi_it);
1618 ptrdiff_t eob = bidi_it->string.s ? bidi_it->string.schars : ZV;
1619 const unsigned char *s
1620 = (STRINGP (bidi_it->string.lstring)
1621 ? SDATA (bidi_it->string.lstring)
1622 : bidi_it->string.s);
1624 if (prev_level < new_level
1625 && bidi_it->type == WEAK_BN
1626 && bidi_it->ignore_bn_limit == -1 /* only if not already known */
1627 && bidi_it->charpos < eob /* not already at EOB */
1628 && bidi_explicit_dir_char (bidi_char_at_pos (bidi_it->bytepos
1629 + bidi_it->ch_len, s,
1630 bidi_it->string.unibyte)))
1632 /* Avoid pushing and popping embedding levels if the level run
1633 is empty, as this breaks level runs where it shouldn't.
1634 UAX#9 removes all the explicit embedding and override codes,
1635 so empty embeddings disappear without a trace. We need to
1636 behave as if we did the same. */
1637 struct bidi_it saved_it;
1638 int level = prev_level;
1640 bidi_copy_it (&saved_it, bidi_it);
1642 while (bidi_explicit_dir_char (bidi_char_at_pos (bidi_it->bytepos
1643 + bidi_it->ch_len, s,
1644 bidi_it->string.unibyte)))
1646 /* This advances to the next character, skipping any
1647 characters covered by display strings. */
1648 level = bidi_resolve_explicit_1 (bidi_it);
1649 /* If string.lstring was relocated inside bidi_resolve_explicit_1,
1650 a pointer to its data is no longer valid. */
1651 if (STRINGP (bidi_it->string.lstring))
1652 s = SDATA (bidi_it->string.lstring);
1655 if (bidi_it->nchars <= 0)
1656 emacs_abort ();
1657 if (level == prev_level) /* empty embedding */
1658 saved_it.ignore_bn_limit = bidi_it->charpos + bidi_it->nchars;
1659 else /* this embedding is non-empty */
1660 saved_it.ignore_bn_limit = -2;
1662 bidi_copy_it (bidi_it, &saved_it);
1663 if (bidi_it->ignore_bn_limit > -1)
1665 /* We pushed a level, but we shouldn't have. Undo that. */
1666 if (!bidi_it->invalid_rl_levels)
1668 new_level = bidi_pop_embedding_level (bidi_it);
1669 bidi_it->invalid_rl_levels = -1;
1670 if (bidi_it->invalid_levels)
1671 bidi_it->invalid_levels--;
1673 if (!bidi_it->invalid_levels)
1674 new_level = bidi_pop_embedding_level (bidi_it);
1675 else
1677 bidi_it->invalid_levels--;
1678 bidi_it->invalid_rl_levels--;
1683 if (bidi_it->type == NEUTRAL_B) /* X8 */
1685 bidi_set_paragraph_end (bidi_it);
1686 /* This is needed by bidi_resolve_weak below, and in L1. */
1687 bidi_it->type_after_w1 = bidi_it->type;
1688 bidi_check_type (bidi_it->type_after_w1);
1691 return new_level;
1694 /* Advance in the buffer/string, resolve weak types and return the
1695 type of the next character after weak type resolution. */
1696 static bidi_type_t
1697 bidi_resolve_weak (struct bidi_it *bidi_it)
1699 bidi_type_t type;
1700 bidi_dir_t override;
1701 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1702 int new_level = bidi_resolve_explicit (bidi_it);
1703 int next_char;
1704 bidi_type_t type_of_next;
1705 struct bidi_it saved_it;
1706 ptrdiff_t eob
1707 = ((STRINGP (bidi_it->string.lstring) || bidi_it->string.s)
1708 ? bidi_it->string.schars : ZV);
1710 type = bidi_it->type;
1711 override = bidi_it->level_stack[bidi_it->stack_idx].override;
1713 if (type == UNKNOWN_BT
1714 || type == LRE
1715 || type == LRO
1716 || type == RLE
1717 || type == RLO
1718 || type == PDF)
1719 emacs_abort ();
1721 if (new_level != prev_level
1722 || bidi_it->type == NEUTRAL_B)
1724 /* We've got a new embedding level run, compute the directional
1725 type of sor and initialize per-run variables (UAX#9, clause
1726 X10). */
1727 bidi_set_sor_type (bidi_it, prev_level, new_level);
1729 else if (type == NEUTRAL_S || type == NEUTRAL_WS
1730 || type == WEAK_BN || type == STRONG_AL)
1731 bidi_it->type_after_w1 = type; /* needed in L1 */
1732 bidi_check_type (bidi_it->type_after_w1);
1734 /* Level and directional override status are already recorded in
1735 bidi_it, and do not need any change; see X6. */
1736 if (override == R2L) /* X6 */
1737 type = STRONG_R;
1738 else if (override == L2R)
1739 type = STRONG_L;
1740 else
1742 if (type == WEAK_NSM) /* W1 */
1744 /* Note that we don't need to consider the case where the
1745 prev character has its type overridden by an RLO or LRO,
1746 because then either the type of this NSM would have been
1747 also overridden, or the previous character is outside the
1748 current level run, and thus not relevant to this NSM.
1749 This is why NSM gets the type_after_w1 of the previous
1750 character. */
1751 if (bidi_it->prev.type_after_w1 != UNKNOWN_BT
1752 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1753 && bidi_it->prev.type_after_w1 != NEUTRAL_B)
1754 type = bidi_it->prev.type_after_w1;
1755 else if (bidi_it->sor == R2L)
1756 type = STRONG_R;
1757 else if (bidi_it->sor == L2R)
1758 type = STRONG_L;
1759 else /* shouldn't happen! */
1760 emacs_abort ();
1762 if (type == WEAK_EN /* W2 */
1763 && bidi_it->last_strong.type_after_w1 == STRONG_AL)
1764 type = WEAK_AN;
1765 else if (type == STRONG_AL) /* W3 */
1766 type = STRONG_R;
1767 else if ((type == WEAK_ES /* W4 */
1768 && bidi_it->prev.type_after_w1 == WEAK_EN
1769 && bidi_it->prev.orig_type == WEAK_EN)
1770 || (type == WEAK_CS
1771 && ((bidi_it->prev.type_after_w1 == WEAK_EN
1772 && bidi_it->prev.orig_type == WEAK_EN)
1773 || bidi_it->prev.type_after_w1 == WEAK_AN)))
1775 const unsigned char *s
1776 = (STRINGP (bidi_it->string.lstring)
1777 ? SDATA (bidi_it->string.lstring)
1778 : bidi_it->string.s);
1780 next_char = (bidi_it->charpos + bidi_it->nchars >= eob
1781 ? BIDI_EOB
1782 : bidi_char_at_pos (bidi_it->bytepos + bidi_it->ch_len,
1783 s, bidi_it->string.unibyte));
1784 type_of_next = bidi_get_type (next_char, override);
1786 if (type_of_next == WEAK_BN
1787 || bidi_explicit_dir_char (next_char))
1789 bidi_copy_it (&saved_it, bidi_it);
1790 while (bidi_resolve_explicit (bidi_it) == new_level
1791 && bidi_it->type == WEAK_BN)
1793 type_of_next = bidi_it->type;
1794 bidi_copy_it (bidi_it, &saved_it);
1797 /* If the next character is EN, but the last strong-type
1798 character is AL, that next EN will be changed to AN when
1799 we process it in W2 above. So in that case, this ES
1800 should not be changed into EN. */
1801 if (type == WEAK_ES
1802 && type_of_next == WEAK_EN
1803 && bidi_it->last_strong.type_after_w1 != STRONG_AL)
1804 type = WEAK_EN;
1805 else if (type == WEAK_CS)
1807 if (bidi_it->prev.type_after_w1 == WEAK_AN
1808 && (type_of_next == WEAK_AN
1809 /* If the next character is EN, but the last
1810 strong-type character is AL, EN will be later
1811 changed to AN when we process it in W2 above.
1812 So in that case, this ES should not be
1813 changed into EN. */
1814 || (type_of_next == WEAK_EN
1815 && bidi_it->last_strong.type_after_w1 == STRONG_AL)))
1816 type = WEAK_AN;
1817 else if (bidi_it->prev.type_after_w1 == WEAK_EN
1818 && type_of_next == WEAK_EN
1819 && bidi_it->last_strong.type_after_w1 != STRONG_AL)
1820 type = WEAK_EN;
1823 else if (type == WEAK_ET /* W5: ET with EN before or after it */
1824 || type == WEAK_BN) /* W5/Retaining */
1826 if (bidi_it->prev.type_after_w1 == WEAK_EN) /* ET/BN w/EN before it */
1827 type = WEAK_EN;
1828 else if (bidi_it->next_en_pos > bidi_it->charpos
1829 && bidi_it->next_en_type != WEAK_BN)
1831 if (bidi_it->next_en_type == WEAK_EN) /* ET/BN with EN after it */
1832 type = WEAK_EN;
1834 else if (bidi_it->next_en_pos >=0)
1836 ptrdiff_t en_pos = bidi_it->charpos + bidi_it->nchars;
1837 const unsigned char *s = (STRINGP (bidi_it->string.lstring)
1838 ? SDATA (bidi_it->string.lstring)
1839 : bidi_it->string.s);
1841 if (bidi_it->nchars <= 0)
1842 emacs_abort ();
1843 next_char
1844 = (bidi_it->charpos + bidi_it->nchars >= eob
1845 ? BIDI_EOB
1846 : bidi_char_at_pos (bidi_it->bytepos + bidi_it->ch_len, s,
1847 bidi_it->string.unibyte));
1848 type_of_next = bidi_get_type (next_char, override);
1850 if (type_of_next == WEAK_ET
1851 || type_of_next == WEAK_BN
1852 || bidi_explicit_dir_char (next_char))
1854 bidi_copy_it (&saved_it, bidi_it);
1855 while (bidi_resolve_explicit (bidi_it) == new_level
1856 && (bidi_it->type == WEAK_BN
1857 || bidi_it->type == WEAK_ET))
1859 type_of_next = bidi_it->type;
1860 en_pos = bidi_it->charpos;
1861 bidi_copy_it (bidi_it, &saved_it);
1863 /* Remember this position, to speed up processing of the
1864 next ETs. */
1865 bidi_it->next_en_pos = en_pos;
1866 if (type_of_next == WEAK_EN)
1868 /* If the last strong character is AL, the EN we've
1869 found will become AN when we get to it (W2). */
1870 if (bidi_it->last_strong.type_after_w1 == STRONG_AL)
1871 type_of_next = WEAK_AN;
1872 else if (type == WEAK_BN)
1873 type = NEUTRAL_ON; /* W6/Retaining */
1874 else
1875 type = WEAK_EN;
1877 else if (type_of_next == NEUTRAL_B)
1878 /* Record the fact that there are no more ENs from
1879 here to the end of paragraph, to avoid entering the
1880 loop above ever again in this paragraph. */
1881 bidi_it->next_en_pos = -1;
1882 /* Record the type of the character where we ended our search. */
1883 bidi_it->next_en_type = type_of_next;
1888 if (type == WEAK_ES || type == WEAK_ET || type == WEAK_CS /* W6 */
1889 || (type == WEAK_BN
1890 && (bidi_it->prev.type_after_w1 == WEAK_CS /* W6/Retaining */
1891 || bidi_it->prev.type_after_w1 == WEAK_ES
1892 || bidi_it->prev.type_after_w1 == WEAK_ET)))
1893 type = NEUTRAL_ON;
1895 /* Store the type we've got so far, before we clobber it with strong
1896 types in W7 and while resolving neutral types. But leave alone
1897 the original types that were recorded above, because we will need
1898 them for the L1 clause. */
1899 if (bidi_it->type_after_w1 == UNKNOWN_BT)
1900 bidi_it->type_after_w1 = type;
1901 bidi_check_type (bidi_it->type_after_w1);
1903 if (type == WEAK_EN) /* W7 */
1905 if ((bidi_it->last_strong.type_after_w1 == STRONG_L)
1906 || (bidi_it->last_strong.type == UNKNOWN_BT && bidi_it->sor == L2R))
1907 type = STRONG_L;
1910 bidi_it->type = type;
1911 bidi_check_type (bidi_it->type);
1912 return type;
1915 /* Resolve the type of a neutral character according to the type of
1916 surrounding strong text and the current embedding level. */
1917 static bidi_type_t
1918 bidi_resolve_neutral_1 (bidi_type_t prev_type, bidi_type_t next_type, int lev)
1920 /* N1: European and Arabic numbers are treated as though they were R. */
1921 if (next_type == WEAK_EN || next_type == WEAK_AN)
1922 next_type = STRONG_R;
1923 if (prev_type == WEAK_EN || prev_type == WEAK_AN)
1924 prev_type = STRONG_R;
1926 if (next_type == prev_type) /* N1 */
1927 return next_type;
1928 else if ((lev & 1) == 0) /* N2 */
1929 return STRONG_L;
1930 else
1931 return STRONG_R;
1934 static bidi_type_t
1935 bidi_resolve_neutral (struct bidi_it *bidi_it)
1937 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1938 bidi_type_t type = bidi_resolve_weak (bidi_it);
1939 int current_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1941 if (!(type == STRONG_R
1942 || type == STRONG_L
1943 || type == WEAK_BN
1944 || type == WEAK_EN
1945 || type == WEAK_AN
1946 || type == NEUTRAL_B
1947 || type == NEUTRAL_S
1948 || type == NEUTRAL_WS
1949 || type == NEUTRAL_ON))
1950 emacs_abort ();
1952 if ((type != NEUTRAL_B /* Don't risk entering the long loop below if
1953 we are already at paragraph end. */
1954 && bidi_get_category (type) == NEUTRAL)
1955 || (type == WEAK_BN && prev_level == current_level))
1957 if (bidi_it->next_for_neutral.type != UNKNOWN_BT)
1958 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1959 bidi_it->next_for_neutral.type,
1960 current_level);
1961 /* The next two "else if" clauses are shortcuts for the
1962 important special case when we have a long sequence of
1963 neutral or WEAK_BN characters, such as whitespace or nulls or
1964 other control characters, on the base embedding level of the
1965 paragraph, and that sequence goes all the way to the end of
1966 the paragraph and follows a character whose resolved
1967 directionality is identical to the base embedding level.
1968 (This is what happens in a buffer with plain L2R text that
1969 happens to include long sequences of control characters.) By
1970 virtue of N1, the result of examining this long sequence will
1971 always be either STRONG_L or STRONG_R, depending on the base
1972 embedding level. So we use this fact directly instead of
1973 entering the expensive loop in the "else" clause. */
1974 else if (current_level == 0
1975 && bidi_it->prev_for_neutral.type == STRONG_L
1976 && !bidi_explicit_dir_char (bidi_it->ch))
1977 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1978 STRONG_L, current_level);
1979 else if (/* current level is 1 */
1980 current_level == 1
1981 /* base embedding level is also 1 */
1982 && bidi_it->level_stack[0].level == 1
1983 /* previous character is one of those considered R for
1984 the purposes of W5 */
1985 && (bidi_it->prev_for_neutral.type == STRONG_R
1986 || bidi_it->prev_for_neutral.type == WEAK_EN
1987 || bidi_it->prev_for_neutral.type == WEAK_AN)
1988 && !bidi_explicit_dir_char (bidi_it->ch))
1989 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1990 STRONG_R, current_level);
1991 else
1993 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1994 the assumption of batch-style processing; see clauses W4,
1995 W5, and especially N1, which require to look far forward
1996 (as well as back) in the buffer/string. May the fleas of
1997 a thousand camels infest the armpits of those who design
1998 supposedly general-purpose algorithms by looking at their
1999 own implementations, and fail to consider other possible
2000 implementations! */
2001 struct bidi_it saved_it;
2002 bidi_type_t next_type;
2004 if (bidi_it->scan_dir == -1)
2005 emacs_abort ();
2007 bidi_copy_it (&saved_it, bidi_it);
2008 /* Scan the text forward until we find the first non-neutral
2009 character, and then use that to resolve the neutral we
2010 are dealing with now. We also cache the scanned iterator
2011 states, to salvage some of the effort later. */
2012 bidi_cache_iterator_state (bidi_it, 0);
2013 do {
2014 /* Record the info about the previous character, so that
2015 it will be cached below with this state. */
2016 if (bidi_it->type_after_w1 != WEAK_BN /* W1/Retaining */
2017 && bidi_it->type != WEAK_BN)
2018 bidi_remember_char (&bidi_it->prev, bidi_it);
2019 type = bidi_resolve_weak (bidi_it);
2020 /* Paragraph separators have their levels fully resolved
2021 at this point, so cache them as resolved. */
2022 bidi_cache_iterator_state (bidi_it, type == NEUTRAL_B);
2023 /* FIXME: implement L1 here, by testing for a newline and
2024 resetting the level for any sequence of whitespace
2025 characters adjacent to it. */
2026 } while (!(type == NEUTRAL_B
2027 || (type != WEAK_BN
2028 && bidi_get_category (type) != NEUTRAL)
2029 /* This is all per level run, so stop when we
2030 reach the end of this level run. */
2031 || (bidi_it->level_stack[bidi_it->stack_idx].level
2032 != current_level)));
2034 bidi_remember_char (&saved_it.next_for_neutral, bidi_it);
2036 switch (type)
2038 case STRONG_L:
2039 case STRONG_R:
2040 case STRONG_AL:
2041 /* Actually, STRONG_AL cannot happen here, because
2042 bidi_resolve_weak converts it to STRONG_R, per W3. */
2043 eassert (type != STRONG_AL);
2044 next_type = type;
2045 break;
2046 case WEAK_EN:
2047 case WEAK_AN:
2048 /* N1: ``European and Arabic numbers are treated as
2049 though they were R.'' */
2050 next_type = STRONG_R;
2051 break;
2052 case WEAK_BN:
2053 case NEUTRAL_ON: /* W6/Retaining */
2054 if (!bidi_explicit_dir_char (bidi_it->ch))
2055 emacs_abort (); /* can't happen: BNs are skipped */
2056 /* FALLTHROUGH */
2057 case NEUTRAL_B:
2058 /* Marched all the way to the end of this level run.
2059 We need to use the eor type, whose information is
2060 stored by bidi_set_sor_type in the prev_for_neutral
2061 member. */
2062 if (saved_it.type != WEAK_BN
2063 || bidi_get_category (bidi_it->prev.type_after_w1) == NEUTRAL)
2064 next_type = bidi_it->prev_for_neutral.type;
2065 else
2067 /* This is a BN which does not adjoin neutrals.
2068 Leave its type alone. */
2069 bidi_copy_it (bidi_it, &saved_it);
2070 return bidi_it->type;
2072 break;
2073 default:
2074 emacs_abort ();
2076 type = bidi_resolve_neutral_1 (saved_it.prev_for_neutral.type,
2077 next_type, current_level);
2078 saved_it.next_for_neutral.type = next_type;
2079 saved_it.type = type;
2080 bidi_check_type (next_type);
2081 bidi_check_type (type);
2082 bidi_copy_it (bidi_it, &saved_it);
2085 return type;
2088 /* Given an iterator state in BIDI_IT, advance one character position
2089 in the buffer/string to the next character (in the logical order),
2090 resolve the bidi type of that next character, and return that
2091 type. */
2092 static bidi_type_t
2093 bidi_type_of_next_char (struct bidi_it *bidi_it)
2095 bidi_type_t type;
2097 /* This should always be called during a forward scan. */
2098 if (bidi_it->scan_dir != 1)
2099 emacs_abort ();
2101 /* Reset the limit until which to ignore BNs if we step out of the
2102 area where we found only empty levels. */
2103 if ((bidi_it->ignore_bn_limit > -1
2104 && bidi_it->ignore_bn_limit <= bidi_it->charpos)
2105 || (bidi_it->ignore_bn_limit == -2
2106 && !bidi_explicit_dir_char (bidi_it->ch)))
2107 bidi_it->ignore_bn_limit = -1;
2109 type = bidi_resolve_neutral (bidi_it);
2111 return type;
2114 /* Given an iterator state BIDI_IT, advance one character position in
2115 the buffer/string to the next character (in the current scan
2116 direction), resolve the embedding and implicit levels of that next
2117 character, and return the resulting level. */
2118 static int
2119 bidi_level_of_next_char (struct bidi_it *bidi_it)
2121 bidi_type_t type;
2122 int level, prev_level = -1;
2123 struct bidi_saved_info next_for_neutral;
2124 ptrdiff_t next_char_pos = -2;
2126 if (bidi_it->scan_dir == 1)
2128 ptrdiff_t eob
2129 = ((bidi_it->string.s || STRINGP (bidi_it->string.lstring))
2130 ? bidi_it->string.schars : ZV);
2132 /* There's no sense in trying to advance if we hit end of text. */
2133 if (bidi_it->charpos >= eob)
2134 return bidi_it->resolved_level;
2136 /* Record the info about the previous character. */
2137 if (bidi_it->type_after_w1 != WEAK_BN /* W1/Retaining */
2138 && bidi_it->type != WEAK_BN)
2139 bidi_remember_char (&bidi_it->prev, bidi_it);
2140 if (bidi_it->type_after_w1 == STRONG_R
2141 || bidi_it->type_after_w1 == STRONG_L
2142 || bidi_it->type_after_w1 == STRONG_AL)
2143 bidi_remember_char (&bidi_it->last_strong, bidi_it);
2144 /* FIXME: it sounds like we don't need both prev and
2145 prev_for_neutral members, but I'm leaving them both for now. */
2146 if (bidi_it->type == STRONG_R || bidi_it->type == STRONG_L
2147 || bidi_it->type == WEAK_EN || bidi_it->type == WEAK_AN)
2148 bidi_remember_char (&bidi_it->prev_for_neutral, bidi_it);
2150 /* If we overstepped the characters used for resolving neutrals
2151 and whitespace, invalidate their info in the iterator. */
2152 if (bidi_it->charpos >= bidi_it->next_for_neutral.charpos)
2153 bidi_it->next_for_neutral.type = UNKNOWN_BT;
2154 if (bidi_it->next_en_pos >= 0
2155 && bidi_it->charpos >= bidi_it->next_en_pos)
2157 bidi_it->next_en_pos = 0;
2158 bidi_it->next_en_type = UNKNOWN_BT;
2160 if (bidi_it->next_for_ws.type != UNKNOWN_BT
2161 && bidi_it->charpos >= bidi_it->next_for_ws.charpos)
2162 bidi_it->next_for_ws.type = UNKNOWN_BT;
2164 /* This must be taken before we fill the iterator with the info
2165 about the next char. If we scan backwards, the iterator
2166 state must be already cached, so there's no need to know the
2167 embedding level of the previous character, since we will be
2168 returning to our caller shortly. */
2169 prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
2171 next_for_neutral = bidi_it->next_for_neutral;
2173 /* Perhaps the character we want is already cached. If it is, the
2174 call to bidi_cache_find below will return a type other than
2175 UNKNOWN_BT. */
2176 if (bidi_cache_idx > bidi_cache_start && !bidi_it->first_elt)
2178 int bob = ((bidi_it->string.s || STRINGP (bidi_it->string.lstring))
2179 ? 0 : 1);
2180 if (bidi_it->scan_dir > 0)
2182 if (bidi_it->nchars <= 0)
2183 emacs_abort ();
2184 next_char_pos = bidi_it->charpos + bidi_it->nchars;
2186 else if (bidi_it->charpos >= bob)
2187 /* Implementation note: we allow next_char_pos to be as low as
2188 0 for buffers or -1 for strings, and that is okay because
2189 that's the "position" of the sentinel iterator state we
2190 cached at the beginning of the iteration. */
2191 next_char_pos = bidi_it->charpos - 1;
2192 if (next_char_pos >= bob - 1)
2193 type = bidi_cache_find (next_char_pos, -1, bidi_it);
2194 else
2195 type = UNKNOWN_BT;
2197 else
2198 type = UNKNOWN_BT;
2199 if (type != UNKNOWN_BT)
2201 /* Don't lose the information for resolving neutrals! The
2202 cached states could have been cached before their
2203 next_for_neutral member was computed. If we are on our way
2204 forward, we can simply take the info from the previous
2205 state. */
2206 if (bidi_it->scan_dir == 1
2207 && bidi_it->next_for_neutral.type == UNKNOWN_BT)
2208 bidi_it->next_for_neutral = next_for_neutral;
2210 /* If resolved_level is -1, it means this state was cached
2211 before it was completely resolved, so we cannot return
2212 it. */
2213 if (bidi_it->resolved_level != -1)
2214 return bidi_it->resolved_level;
2216 if (bidi_it->scan_dir == -1)
2217 /* If we are going backwards, the iterator state is already cached
2218 from previous scans, and should be fully resolved. */
2219 emacs_abort ();
2221 if (type == UNKNOWN_BT)
2222 type = bidi_type_of_next_char (bidi_it);
2224 if (type == NEUTRAL_B)
2225 return bidi_it->resolved_level;
2227 level = bidi_it->level_stack[bidi_it->stack_idx].level;
2228 if ((bidi_get_category (type) == NEUTRAL /* && type != NEUTRAL_B */)
2229 || (type == WEAK_BN && prev_level == level))
2231 if (bidi_it->next_for_neutral.type == UNKNOWN_BT)
2232 emacs_abort ();
2234 /* If the cached state shows a neutral character, it was not
2235 resolved by bidi_resolve_neutral, so do it now. */
2236 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
2237 bidi_it->next_for_neutral.type,
2238 level);
2241 if (!(type == STRONG_R
2242 || type == STRONG_L
2243 || type == WEAK_BN
2244 || type == WEAK_EN
2245 || type == WEAK_AN))
2246 emacs_abort ();
2247 bidi_it->type = type;
2248 bidi_check_type (bidi_it->type);
2250 /* For L1 below, we need to know, for each WS character, whether
2251 it belongs to a sequence of WS characters preceding a newline
2252 or a TAB or a paragraph separator. */
2253 if (bidi_it->orig_type == NEUTRAL_WS
2254 && bidi_it->next_for_ws.type == UNKNOWN_BT)
2256 int ch;
2257 ptrdiff_t clen = bidi_it->ch_len;
2258 ptrdiff_t bpos = bidi_it->bytepos;
2259 ptrdiff_t cpos = bidi_it->charpos;
2260 ptrdiff_t disp_pos = bidi_it->disp_pos;
2261 ptrdiff_t nc = bidi_it->nchars;
2262 struct bidi_string_data bs = bidi_it->string;
2263 bidi_type_t chtype;
2264 bool fwp = bidi_it->frame_window_p;
2265 int dpp = bidi_it->disp_prop;
2267 if (bidi_it->nchars <= 0)
2268 emacs_abort ();
2269 do {
2270 ch = bidi_fetch_char (cpos += nc, bpos += clen, &disp_pos, &dpp, &bs,
2271 bidi_it->w, fwp, &clen, &nc);
2272 if (ch == '\n' || ch == BIDI_EOB)
2273 chtype = NEUTRAL_B;
2274 else
2275 chtype = bidi_get_type (ch, NEUTRAL_DIR);
2276 } while (chtype == NEUTRAL_WS || chtype == WEAK_BN
2277 || bidi_explicit_dir_char (ch)); /* L1/Retaining */
2278 bidi_it->next_for_ws.type = chtype;
2279 bidi_check_type (bidi_it->next_for_ws.type);
2280 bidi_it->next_for_ws.charpos = cpos;
2281 bidi_it->next_for_ws.bytepos = bpos;
2284 /* Resolve implicit levels, with a twist: PDFs get the embedding
2285 level of the embedding they terminate. See below for the
2286 reason. */
2287 if (bidi_it->orig_type == PDF
2288 /* Don't do this if this formatting code didn't change the
2289 embedding level due to invalid or empty embeddings. */
2290 && prev_level != level)
2292 /* Don't look in UAX#9 for the reason for this: it's our own
2293 private quirk. The reason is that we want the formatting
2294 codes to be delivered so that they bracket the text of their
2295 embedding. For example, given the text
2297 {RLO}teST{PDF}
2299 we want it to be displayed as
2301 {PDF}STet{RLO}
2303 not as
2305 STet{RLO}{PDF}
2307 which will result because we bump up the embedding level as
2308 soon as we see the RLO and pop it as soon as we see the PDF,
2309 so RLO itself has the same embedding level as "teST", and
2310 thus would be normally delivered last, just before the PDF.
2311 The switch below fiddles with the level of PDF so that this
2312 ugly side effect does not happen.
2314 (This is, of course, only important if the formatting codes
2315 are actually displayed, but Emacs does need to display them
2316 if the user wants to.) */
2317 level = prev_level;
2319 else if (bidi_it->orig_type == NEUTRAL_B /* L1 */
2320 || bidi_it->orig_type == NEUTRAL_S
2321 || bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB
2322 || (bidi_it->orig_type == NEUTRAL_WS
2323 && (bidi_it->next_for_ws.type == NEUTRAL_B
2324 || bidi_it->next_for_ws.type == NEUTRAL_S)))
2325 level = bidi_it->level_stack[0].level;
2326 else if ((level & 1) == 0) /* I1 */
2328 if (type == STRONG_R)
2329 level++;
2330 else if (type == WEAK_EN || type == WEAK_AN)
2331 level += 2;
2333 else /* I2 */
2335 if (type == STRONG_L || type == WEAK_EN || type == WEAK_AN)
2336 level++;
2339 bidi_it->resolved_level = level;
2340 return level;
2343 /* Move to the other edge of a level given by LEVEL. If END_FLAG,
2344 we are at the end of a level, and we need to prepare to
2345 resume the scan of the lower level.
2347 If this level's other edge is cached, we simply jump to it, filling
2348 the iterator structure with the iterator state on the other edge.
2349 Otherwise, we walk the buffer or string until we come back to the
2350 same level as LEVEL.
2352 Note: we are not talking here about a ``level run'' in the UAX#9
2353 sense of the term, but rather about a ``level'' which includes
2354 all the levels higher than it. In other words, given the levels
2355 like this:
2357 11111112222222333333334443343222222111111112223322111
2358 A B C
2360 and assuming we are at point A scanning left to right, this
2361 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
2362 at point B. */
2363 static void
2364 bidi_find_other_level_edge (struct bidi_it *bidi_it, int level, bool end_flag)
2366 int dir = end_flag ? -bidi_it->scan_dir : bidi_it->scan_dir;
2367 ptrdiff_t idx;
2369 /* Try the cache first. */
2370 if ((idx = bidi_cache_find_level_change (level, dir, end_flag))
2371 >= bidi_cache_start)
2372 bidi_cache_fetch_state (idx, bidi_it);
2373 else
2375 int new_level;
2377 /* If we are at end of level, its edges must be cached. */
2378 if (end_flag)
2379 emacs_abort ();
2381 bidi_cache_iterator_state (bidi_it, 1);
2382 do {
2383 new_level = bidi_level_of_next_char (bidi_it);
2384 bidi_cache_iterator_state (bidi_it, 1);
2385 } while (new_level >= level);
2389 void
2390 bidi_move_to_visually_next (struct bidi_it *bidi_it)
2392 int old_level, new_level, next_level;
2393 struct bidi_it sentinel;
2394 struct gcpro gcpro1;
2396 if (bidi_it->charpos < 0 || bidi_it->bytepos < 0)
2397 emacs_abort ();
2399 if (bidi_it->scan_dir == 0)
2401 bidi_it->scan_dir = 1; /* default to logical order */
2404 /* The code below can call eval, and thus cause GC. If we are
2405 iterating a Lisp string, make sure it won't be GCed. */
2406 if (STRINGP (bidi_it->string.lstring))
2407 GCPRO1 (bidi_it->string.lstring);
2409 /* If we just passed a newline, initialize for the next line. */
2410 if (!bidi_it->first_elt
2411 && (bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB))
2412 bidi_line_init (bidi_it);
2414 /* Prepare the sentinel iterator state, and cache it. When we bump
2415 into it, scanning backwards, we'll know that the last non-base
2416 level is exhausted. */
2417 if (bidi_cache_idx == bidi_cache_start)
2419 bidi_copy_it (&sentinel, bidi_it);
2420 if (bidi_it->first_elt)
2422 sentinel.charpos--; /* cached charpos needs to be monotonic */
2423 sentinel.bytepos--;
2424 sentinel.ch = '\n'; /* doesn't matter, but why not? */
2425 sentinel.ch_len = 1;
2426 sentinel.nchars = 1;
2428 bidi_cache_iterator_state (&sentinel, 1);
2431 old_level = bidi_it->resolved_level;
2432 new_level = bidi_level_of_next_char (bidi_it);
2434 /* Reordering of resolved levels (clause L2) is implemented by
2435 jumping to the other edge of the level and flipping direction of
2436 scanning the text whenever we find a level change. */
2437 if (new_level != old_level)
2439 bool ascending = new_level > old_level;
2440 int level_to_search = ascending ? old_level + 1 : old_level;
2441 int incr = ascending ? 1 : -1;
2442 int expected_next_level = old_level + incr;
2444 /* Jump (or walk) to the other edge of this level. */
2445 bidi_find_other_level_edge (bidi_it, level_to_search, !ascending);
2446 /* Switch scan direction and peek at the next character in the
2447 new direction. */
2448 bidi_it->scan_dir = -bidi_it->scan_dir;
2450 /* The following loop handles the case where the resolved level
2451 jumps by more than one. This is typical for numbers inside a
2452 run of text with left-to-right embedding direction, but can
2453 also happen in other situations. In those cases the decision
2454 where to continue after a level change, and in what direction,
2455 is tricky. For example, given a text like below:
2457 abcdefgh
2458 11336622
2460 (where the numbers below the text show the resolved levels),
2461 the result of reordering according to UAX#9 should be this:
2463 efdcghba
2465 This is implemented by the loop below which flips direction
2466 and jumps to the other edge of the level each time it finds
2467 the new level not to be the expected one. The expected level
2468 is always one more or one less than the previous one. */
2469 next_level = bidi_peek_at_next_level (bidi_it);
2470 while (next_level != expected_next_level)
2472 /* If next_level is -1, it means we have an unresolved level
2473 in the cache, which at this point should not happen. If
2474 it does, we will infloop. */
2475 eassert (next_level >= 0);
2476 expected_next_level += incr;
2477 level_to_search += incr;
2478 bidi_find_other_level_edge (bidi_it, level_to_search, !ascending);
2479 bidi_it->scan_dir = -bidi_it->scan_dir;
2480 next_level = bidi_peek_at_next_level (bidi_it);
2483 /* Finally, deliver the next character in the new direction. */
2484 next_level = bidi_level_of_next_char (bidi_it);
2487 /* Take note when we have just processed the newline that precedes
2488 the end of the paragraph. The next time we are about to be
2489 called, set_iterator_to_next will automatically reinit the
2490 paragraph direction, if needed. We do this at the newline before
2491 the paragraph separator, because the next character might not be
2492 the first character of the next paragraph, due to the bidi
2493 reordering, whereas we _must_ know the paragraph base direction
2494 _before_ we process the paragraph's text, since the base
2495 direction affects the reordering. */
2496 if (bidi_it->scan_dir == 1
2497 && (bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB))
2499 /* The paragraph direction of the entire string, once
2500 determined, is in effect for the entire string. Setting the
2501 separator limit to the end of the string prevents
2502 bidi_paragraph_init from being called automatically on this
2503 string. */
2504 if (bidi_it->string.s || STRINGP (bidi_it->string.lstring))
2505 bidi_it->separator_limit = bidi_it->string.schars;
2506 else if (bidi_it->bytepos < ZV_BYTE)
2508 ptrdiff_t sep_len
2509 = bidi_at_paragraph_end (bidi_it->charpos + bidi_it->nchars,
2510 bidi_it->bytepos + bidi_it->ch_len);
2511 if (bidi_it->nchars <= 0)
2512 emacs_abort ();
2513 if (sep_len >= 0)
2515 bidi_it->new_paragraph = 1;
2516 /* Record the buffer position of the last character of the
2517 paragraph separator. */
2518 bidi_it->separator_limit
2519 = bidi_it->charpos + bidi_it->nchars + sep_len;
2524 if (bidi_it->scan_dir == 1 && bidi_cache_idx > bidi_cache_start)
2526 /* If we are at paragraph's base embedding level and beyond the
2527 last cached position, the cache's job is done and we can
2528 discard it. */
2529 if (bidi_it->resolved_level == bidi_it->level_stack[0].level
2530 && bidi_it->charpos > (bidi_cache[bidi_cache_idx - 1].charpos
2531 + bidi_cache[bidi_cache_idx - 1].nchars - 1))
2532 bidi_cache_reset ();
2533 /* But as long as we are caching during forward scan, we must
2534 cache each state, or else the cache integrity will be
2535 compromised: it assumes cached states correspond to buffer
2536 positions 1:1. */
2537 else
2538 bidi_cache_iterator_state (bidi_it, 1);
2541 if (STRINGP (bidi_it->string.lstring))
2542 UNGCPRO;
2545 /* This is meant to be called from within the debugger, whenever you
2546 wish to examine the cache contents. */
2547 void bidi_dump_cached_states (void) EXTERNALLY_VISIBLE;
2548 void
2549 bidi_dump_cached_states (void)
2551 ptrdiff_t i;
2552 int ndigits = 1;
2554 if (bidi_cache_idx == 0)
2556 fprintf (stderr, "The cache is empty.\n");
2557 return;
2559 fprintf (stderr, "Total of %"pD"d state%s in cache:\n",
2560 bidi_cache_idx, bidi_cache_idx == 1 ? "" : "s");
2562 for (i = bidi_cache[bidi_cache_idx - 1].charpos; i > 0; i /= 10)
2563 ndigits++;
2564 fputs ("ch ", stderr);
2565 for (i = 0; i < bidi_cache_idx; i++)
2566 fprintf (stderr, "%*c", ndigits, bidi_cache[i].ch);
2567 fputs ("\n", stderr);
2568 fputs ("lvl ", stderr);
2569 for (i = 0; i < bidi_cache_idx; i++)
2570 fprintf (stderr, "%*d", ndigits, bidi_cache[i].resolved_level);
2571 fputs ("\n", stderr);
2572 fputs ("pos ", stderr);
2573 for (i = 0; i < bidi_cache_idx; i++)
2574 fprintf (stderr, "%*"pD"d", ndigits, bidi_cache[i].charpos);
2575 fputs ("\n", stderr);