Fix crash due to incorrect resolution of type of NSM characters (bug#5858).
[emacs.git] / src / bidi.c
blob0c8a3182510a084282f5a6606d6b5aa4b26fb637
1 /* Low-level bidirectional buffer-scanning functions for GNU Emacs.
2 Copyright (C) 2000, 2001, 2004, 2005, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GNU Emacs.
7 GNU Emacs is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 GNU Emacs is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
20 /* Written by Eli Zaretskii <eliz@gnu.org>.
22 A sequential implementation of the Unicode Bidirectional algorithm,
23 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.
28 The main entry point is bidi_get_next_char_visually. Each time it
29 is called, it finds the next character in the visual order, and
30 returns its information in a special structure. The caller is then
31 expected to process this character for display or any other
32 purposes, and call bidi_get_next_char_visually for the next
33 character. See the comments in bidi_get_next_char_visually for
34 more details about its algorithm that finds the next visual-order
35 character by resolving their levels on the fly.
37 If you want to understand the code, you will have to read it
38 together with the relevant portions of UAX#9. The comments include
39 references to UAX#9 rules, for that very reason.
41 A note about references to UAX#9 rules: if the reference says
42 something like "X9/Retaining", it means that you need to refer to
43 rule X9 and to its modifications decribed in the "Implementation
44 Notes" section of UAX#9, under "Retaining Format Codes". */
46 #ifdef HAVE_CONFIG_H
47 #include <config.h>
48 #endif
50 #include <stdio.h>
52 #ifdef HAVE_STRING_H
53 #include <string.h>
54 #endif
56 #include <setjmp.h>
58 #include "lisp.h"
59 #include "buffer.h"
60 #include "character.h"
61 #include "dispextern.h"
63 static int bidi_initialized = 0;
65 static Lisp_Object bidi_type_table;
67 /* FIXME: Remove these when bidi_explicit_dir_char uses a lookup table. */
68 #define LRM_CHAR 0x200E
69 #define RLM_CHAR 0x200F
70 #define LRE_CHAR 0x202A
71 #define RLE_CHAR 0x202B
72 #define PDF_CHAR 0x202C
73 #define LRO_CHAR 0x202D
74 #define RLO_CHAR 0x202E
76 #define BIDI_EOB -1
77 #define BIDI_BOB -2 /* FIXME: Is this needed? */
79 /* Local data structures. (Look in dispextern.h for the rest.) */
81 /* What we need to know about the current paragraph. */
82 struct bidi_paragraph_info {
83 int start_bytepos; /* byte position where it begins */
84 int end_bytepos; /* byte position where it ends */
85 int embedding_level; /* its basic embedding level */
86 bidi_dir_t base_dir; /* its base direction */
89 /* Data type for describing the bidirectional character categories. */
90 typedef enum {
91 UNKNOWN_BC,
92 NEUTRAL,
93 WEAK,
94 STRONG
95 } bidi_category_t;
97 int bidi_ignore_explicit_marks_for_paragraph_level = 1;
99 static Lisp_Object fallback_paragraph_start_re, fallback_paragraph_separate_re;
100 static Lisp_Object Qparagraph_start, Qparagraph_separate;
102 static void
103 bidi_initialize ()
105 /* FIXME: This should come from the Unicode Database. */
106 struct {
107 int from, to;
108 bidi_type_t type;
109 } bidi_type[] =
110 { { 0x0000, 0x0008, WEAK_BN },
111 { 0x0009, 0x0000, NEUTRAL_S },
112 { 0x000A, 0x0000, NEUTRAL_B },
113 { 0x000B, 0x0000, NEUTRAL_S },
114 { 0x000C, 0x0000, NEUTRAL_WS },
115 { 0x000D, 0x0000, NEUTRAL_B },
116 { 0x000E, 0x001B, WEAK_BN },
117 { 0x001C, 0x001E, NEUTRAL_B },
118 { 0x001F, 0x0000, NEUTRAL_S },
119 { 0x0020, 0x0000, NEUTRAL_WS },
120 { 0x0021, 0x0022, NEUTRAL_ON },
121 { 0x0023, 0x0025, WEAK_ET },
122 { 0x0026, 0x002A, NEUTRAL_ON },
123 { 0x002B, 0x0000, WEAK_ES },
124 { 0x002C, 0x0000, WEAK_CS },
125 { 0x002D, 0x0000, WEAK_ES },
126 { 0x002E, 0x002F, WEAK_CS },
127 { 0x0030, 0x0039, WEAK_EN },
128 { 0x003A, 0x0000, WEAK_CS },
129 { 0x003B, 0x0040, NEUTRAL_ON },
130 { 0x005B, 0x0060, NEUTRAL_ON },
131 { 0x007B, 0x007E, NEUTRAL_ON },
132 { 0x007F, 0x0084, WEAK_BN },
133 { 0x0085, 0x0000, NEUTRAL_B },
134 { 0x0086, 0x009F, WEAK_BN },
135 { 0x00A0, 0x0000, WEAK_CS },
136 { 0x00A1, 0x0000, NEUTRAL_ON },
137 { 0x00A2, 0x00A5, WEAK_ET },
138 { 0x00A6, 0x00A9, NEUTRAL_ON },
139 { 0x00AB, 0x00AC, NEUTRAL_ON },
140 { 0x00AD, 0x0000, WEAK_BN },
141 { 0x00AE, 0x00Af, NEUTRAL_ON },
142 { 0x00B0, 0x00B1, WEAK_ET },
143 { 0x00B2, 0x00B3, WEAK_EN },
144 { 0x00B4, 0x0000, NEUTRAL_ON },
145 { 0x00B6, 0x00B8, NEUTRAL_ON },
146 { 0x00B9, 0x0000, WEAK_EN },
147 { 0x00BB, 0x00BF, NEUTRAL_ON },
148 { 0x00D7, 0x0000, NEUTRAL_ON },
149 { 0x00F7, 0x0000, NEUTRAL_ON },
150 { 0x02B9, 0x02BA, NEUTRAL_ON },
151 { 0x02C2, 0x02CF, NEUTRAL_ON },
152 { 0x02D2, 0x02DF, NEUTRAL_ON },
153 { 0x02E5, 0x02ED, NEUTRAL_ON },
154 { 0x0300, 0x036F, WEAK_NSM },
155 { 0x0374, 0x0375, NEUTRAL_ON },
156 { 0x037E, 0x0385, NEUTRAL_ON },
157 { 0x0387, 0x0000, NEUTRAL_ON },
158 { 0x03F6, 0x0000, NEUTRAL_ON },
159 { 0x0483, 0x0489, WEAK_NSM },
160 { 0x058A, 0x0000, NEUTRAL_ON },
161 { 0x0591, 0x05BD, WEAK_NSM },
162 { 0x05BE, 0x0000, STRONG_R },
163 { 0x05BF, 0x0000, WEAK_NSM },
164 { 0x05C0, 0x0000, STRONG_R },
165 { 0x05C1, 0x05C2, WEAK_NSM },
166 { 0x05C3, 0x0000, STRONG_R },
167 { 0x05C4, 0x05C5, WEAK_NSM },
168 { 0x05C6, 0x0000, STRONG_R },
169 { 0x05C7, 0x0000, WEAK_NSM },
170 { 0x05D0, 0x05F4, STRONG_R },
171 { 0x060C, 0x0000, WEAK_CS },
172 { 0x061B, 0x064A, STRONG_AL },
173 { 0x064B, 0x0655, WEAK_NSM },
174 { 0x0660, 0x0669, WEAK_AN },
175 { 0x066A, 0x0000, WEAK_ET },
176 { 0x066B, 0x066C, WEAK_AN },
177 { 0x066D, 0x066F, STRONG_AL },
178 { 0x0670, 0x0000, WEAK_NSM },
179 { 0x0671, 0x06D5, STRONG_AL },
180 { 0x06D6, 0x06DC, WEAK_NSM },
181 { 0x06DD, 0x0000, STRONG_AL },
182 { 0x06DE, 0x06E4, WEAK_NSM },
183 { 0x06E5, 0x06E6, STRONG_AL },
184 { 0x06E7, 0x06E8, WEAK_NSM },
185 { 0x06E9, 0x0000, NEUTRAL_ON },
186 { 0x06EA, 0x06ED, WEAK_NSM },
187 { 0x06F0, 0x06F9, WEAK_EN },
188 { 0x06FA, 0x070D, STRONG_AL },
189 { 0x070F, 0x0000, WEAK_BN },
190 { 0x0710, 0x0000, STRONG_AL },
191 { 0x0711, 0x0000, WEAK_NSM },
192 { 0x0712, 0x072C, STRONG_AL },
193 { 0x0730, 0x074A, WEAK_NSM },
194 { 0x0780, 0x07A5, STRONG_AL },
195 { 0x07A6, 0x07B0, WEAK_NSM },
196 { 0x07B1, 0x0000, STRONG_AL },
197 { 0x0901, 0x0902, WEAK_NSM },
198 { 0x093C, 0x0000, WEAK_NSM },
199 { 0x0941, 0x0948, WEAK_NSM },
200 { 0x094D, 0x0000, WEAK_NSM },
201 { 0x0951, 0x0954, WEAK_NSM },
202 { 0x0962, 0x0963, WEAK_NSM },
203 { 0x0981, 0x0000, WEAK_NSM },
204 { 0x09BC, 0x0000, WEAK_NSM },
205 { 0x09C1, 0x09C4, WEAK_NSM },
206 { 0x09CD, 0x0000, WEAK_NSM },
207 { 0x09E2, 0x09E3, WEAK_NSM },
208 { 0x09F2, 0x09F3, WEAK_ET },
209 { 0x0A02, 0x0000, WEAK_NSM },
210 { 0x0A3C, 0x0000, WEAK_NSM },
211 { 0x0A41, 0x0A4D, WEAK_NSM },
212 { 0x0A70, 0x0A71, WEAK_NSM },
213 { 0x0A81, 0x0A82, WEAK_NSM },
214 { 0x0ABC, 0x0000, WEAK_NSM },
215 { 0x0AC1, 0x0AC8, WEAK_NSM },
216 { 0x0ACD, 0x0000, WEAK_NSM },
217 { 0x0B01, 0x0000, WEAK_NSM },
218 { 0x0B3C, 0x0000, WEAK_NSM },
219 { 0x0B3F, 0x0000, WEAK_NSM },
220 { 0x0B41, 0x0B43, WEAK_NSM },
221 { 0x0B4D, 0x0B56, WEAK_NSM },
222 { 0x0B82, 0x0000, WEAK_NSM },
223 { 0x0BC0, 0x0000, WEAK_NSM },
224 { 0x0BCD, 0x0000, WEAK_NSM },
225 { 0x0C3E, 0x0C40, WEAK_NSM },
226 { 0x0C46, 0x0C56, WEAK_NSM },
227 { 0x0CBF, 0x0000, WEAK_NSM },
228 { 0x0CC6, 0x0000, WEAK_NSM },
229 { 0x0CCC, 0x0CCD, WEAK_NSM },
230 { 0x0D41, 0x0D43, WEAK_NSM },
231 { 0x0D4D, 0x0000, WEAK_NSM },
232 { 0x0DCA, 0x0000, WEAK_NSM },
233 { 0x0DD2, 0x0DD6, WEAK_NSM },
234 { 0x0E31, 0x0000, WEAK_NSM },
235 { 0x0E34, 0x0E3A, WEAK_NSM },
236 { 0x0E3F, 0x0000, WEAK_ET },
237 { 0x0E47, 0x0E4E, WEAK_NSM },
238 { 0x0EB1, 0x0000, WEAK_NSM },
239 { 0x0EB4, 0x0EBC, WEAK_NSM },
240 { 0x0EC8, 0x0ECD, WEAK_NSM },
241 { 0x0F18, 0x0F19, WEAK_NSM },
242 { 0x0F35, 0x0000, WEAK_NSM },
243 { 0x0F37, 0x0000, WEAK_NSM },
244 { 0x0F39, 0x0000, WEAK_NSM },
245 { 0x0F3A, 0x0F3D, NEUTRAL_ON },
246 { 0x0F71, 0x0F7E, WEAK_NSM },
247 { 0x0F80, 0x0F84, WEAK_NSM },
248 { 0x0F86, 0x0F87, WEAK_NSM },
249 { 0x0F90, 0x0FBC, WEAK_NSM },
250 { 0x0FC6, 0x0000, WEAK_NSM },
251 { 0x102D, 0x1030, WEAK_NSM },
252 { 0x1032, 0x1037, WEAK_NSM },
253 { 0x1039, 0x0000, WEAK_NSM },
254 { 0x1058, 0x1059, WEAK_NSM },
255 { 0x1680, 0x0000, NEUTRAL_WS },
256 { 0x169B, 0x169C, NEUTRAL_ON },
257 { 0x1712, 0x1714, WEAK_NSM },
258 { 0x1732, 0x1734, WEAK_NSM },
259 { 0x1752, 0x1753, WEAK_NSM },
260 { 0x1772, 0x1773, WEAK_NSM },
261 { 0x17B7, 0x17BD, WEAK_NSM },
262 { 0x17C6, 0x0000, WEAK_NSM },
263 { 0x17C9, 0x17D3, WEAK_NSM },
264 { 0x17DB, 0x0000, WEAK_ET },
265 { 0x1800, 0x180A, NEUTRAL_ON },
266 { 0x180B, 0x180D, WEAK_NSM },
267 { 0x180E, 0x0000, WEAK_BN },
268 { 0x18A9, 0x0000, WEAK_NSM },
269 { 0x1FBD, 0x0000, NEUTRAL_ON },
270 { 0x1FBF, 0x1FC1, NEUTRAL_ON },
271 { 0x1FCD, 0x1FCF, NEUTRAL_ON },
272 { 0x1FDD, 0x1FDF, NEUTRAL_ON },
273 { 0x1FED, 0x1FEF, NEUTRAL_ON },
274 { 0x1FFD, 0x1FFE, NEUTRAL_ON },
275 { 0x2000, 0x200A, NEUTRAL_WS },
276 { 0x200B, 0x200D, WEAK_BN },
277 { 0x200F, 0x0000, STRONG_R },
278 { 0x2010, 0x2027, NEUTRAL_ON },
279 { 0x2028, 0x0000, NEUTRAL_WS },
280 { 0x2029, 0x0000, NEUTRAL_B },
281 { 0x202A, 0x0000, LRE },
282 { 0x202B, 0x0000, RLE },
283 { 0x202C, 0x0000, PDF },
284 { 0x202D, 0x0000, LRO },
285 { 0x202E, 0x0000, RLO },
286 { 0x202F, 0x0000, NEUTRAL_WS },
287 { 0x2030, 0x2034, WEAK_ET },
288 { 0x2035, 0x2057, NEUTRAL_ON },
289 { 0x205F, 0x0000, NEUTRAL_WS },
290 { 0x2060, 0x206F, WEAK_BN },
291 { 0x2070, 0x0000, WEAK_EN },
292 { 0x2074, 0x2079, WEAK_EN },
293 { 0x207A, 0x207B, WEAK_ET },
294 { 0x207C, 0x207E, NEUTRAL_ON },
295 { 0x2080, 0x2089, WEAK_EN },
296 { 0x208A, 0x208B, WEAK_ET },
297 { 0x208C, 0x208E, NEUTRAL_ON },
298 { 0x20A0, 0x20B1, WEAK_ET },
299 { 0x20D0, 0x20EA, WEAK_NSM },
300 { 0x2100, 0x2101, NEUTRAL_ON },
301 { 0x2103, 0x2106, NEUTRAL_ON },
302 { 0x2108, 0x2109, NEUTRAL_ON },
303 { 0x2114, 0x0000, NEUTRAL_ON },
304 { 0x2116, 0x2118, NEUTRAL_ON },
305 { 0x211E, 0x2123, NEUTRAL_ON },
306 { 0x2125, 0x0000, NEUTRAL_ON },
307 { 0x2127, 0x0000, NEUTRAL_ON },
308 { 0x2129, 0x0000, NEUTRAL_ON },
309 { 0x212E, 0x0000, WEAK_ET },
310 { 0x2132, 0x0000, NEUTRAL_ON },
311 { 0x213A, 0x0000, NEUTRAL_ON },
312 { 0x2140, 0x2144, NEUTRAL_ON },
313 { 0x214A, 0x215F, NEUTRAL_ON },
314 { 0x2190, 0x2211, NEUTRAL_ON },
315 { 0x2212, 0x2213, WEAK_ET },
316 { 0x2214, 0x2335, NEUTRAL_ON },
317 { 0x237B, 0x2394, NEUTRAL_ON },
318 { 0x2396, 0x244A, NEUTRAL_ON },
319 { 0x2460, 0x249B, WEAK_EN },
320 { 0x24EA, 0x0000, WEAK_EN },
321 { 0x24EB, 0x2FFB, NEUTRAL_ON },
322 { 0x3000, 0x0000, NEUTRAL_WS },
323 { 0x3001, 0x3004, NEUTRAL_ON },
324 { 0x3008, 0x3020, NEUTRAL_ON },
325 { 0x302A, 0x302F, WEAK_NSM },
326 { 0x3030, 0x0000, NEUTRAL_ON },
327 { 0x3036, 0x3037, NEUTRAL_ON },
328 { 0x303D, 0x303F, NEUTRAL_ON },
329 { 0x3099, 0x309A, WEAK_NSM },
330 { 0x309B, 0x309C, NEUTRAL_ON },
331 { 0x30A0, 0x0000, NEUTRAL_ON },
332 { 0x30FB, 0x0000, NEUTRAL_ON },
333 { 0x3251, 0x325F, NEUTRAL_ON },
334 { 0x32B1, 0x32BF, NEUTRAL_ON },
335 { 0xA490, 0xA4C6, NEUTRAL_ON },
336 { 0xFB1D, 0x0000, STRONG_R },
337 { 0xFB1E, 0x0000, WEAK_NSM },
338 { 0xFB1F, 0xFB28, STRONG_R },
339 { 0xFB29, 0x0000, WEAK_ET },
340 { 0xFB2A, 0xFB4F, STRONG_R },
341 { 0xFB50, 0xFD3D, STRONG_AL },
342 { 0xFD3E, 0xFD3F, NEUTRAL_ON },
343 { 0xFD50, 0xFDFC, STRONG_AL },
344 { 0xFE00, 0xFE23, WEAK_NSM },
345 { 0xFE30, 0xFE4F, NEUTRAL_ON },
346 { 0xFE50, 0x0000, WEAK_CS },
347 { 0xFE51, 0x0000, NEUTRAL_ON },
348 { 0xFE52, 0x0000, WEAK_CS },
349 { 0xFE54, 0x0000, NEUTRAL_ON },
350 { 0xFE55, 0x0000, WEAK_CS },
351 { 0xFE56, 0xFE5E, NEUTRAL_ON },
352 { 0xFE5F, 0x0000, WEAK_ET },
353 { 0xFE60, 0xFE61, NEUTRAL_ON },
354 { 0xFE62, 0xFE63, WEAK_ET },
355 { 0xFE64, 0xFE68, NEUTRAL_ON },
356 { 0xFE69, 0xFE6A, WEAK_ET },
357 { 0xFE6B, 0x0000, NEUTRAL_ON },
358 { 0xFE70, 0xFEFC, STRONG_AL },
359 { 0xFEFF, 0x0000, WEAK_BN },
360 { 0xFF01, 0xFF02, NEUTRAL_ON },
361 { 0xFF03, 0xFF05, WEAK_ET },
362 { 0xFF06, 0xFF0A, NEUTRAL_ON },
363 { 0xFF0B, 0x0000, WEAK_ET },
364 { 0xFF0C, 0x0000, WEAK_CS },
365 { 0xFF0D, 0x0000, WEAK_ET },
366 { 0xFF0E, 0x0000, WEAK_CS },
367 { 0xFF0F, 0x0000, WEAK_ES },
368 { 0xFF10, 0xFF19, WEAK_EN },
369 { 0xFF1A, 0x0000, WEAK_CS },
370 { 0xFF1B, 0xFF20, NEUTRAL_ON },
371 { 0xFF3B, 0xFF40, NEUTRAL_ON },
372 { 0xFF5B, 0xFF65, NEUTRAL_ON },
373 { 0xFFE0, 0xFFE1, WEAK_ET },
374 { 0xFFE2, 0xFFE4, NEUTRAL_ON },
375 { 0xFFE5, 0xFFE6, WEAK_ET },
376 { 0xFFE8, 0xFFEE, NEUTRAL_ON },
377 { 0xFFF9, 0xFFFB, WEAK_BN },
378 { 0xFFFC, 0xFFFD, NEUTRAL_ON },
379 { 0x1D167, 0x1D169, WEAK_NSM },
380 { 0x1D173, 0x1D17A, WEAK_BN },
381 { 0x1D17B, 0x1D182, WEAK_NSM },
382 { 0x1D185, 0x1D18B, WEAK_NSM },
383 { 0x1D1AA, 0x1D1AD, WEAK_NSM },
384 { 0x1D7CE, 0x1D7FF, WEAK_EN },
385 { 0xE0001, 0xE007F, WEAK_BN } };
386 int i;
388 bidi_type_table = Fmake_char_table (Qnil, make_number (STRONG_L));
389 staticpro (&bidi_type_table);
391 for (i = 0; i < sizeof bidi_type / sizeof bidi_type[0]; i++)
392 char_table_set_range (bidi_type_table, bidi_type[i].from,
393 bidi_type[i].to ? bidi_type[i].to : bidi_type[i].from,
394 make_number (bidi_type[i].type));
396 fallback_paragraph_start_re =
397 XSYMBOL (Fintern_soft (build_string ("paragraph-start"), Qnil))->value;
398 if (!STRINGP (fallback_paragraph_start_re))
399 fallback_paragraph_start_re = build_string ("\f\\|[ \t]*$");
400 staticpro (&fallback_paragraph_start_re);
401 Qparagraph_start = intern ("paragraph-start");
402 staticpro (&Qparagraph_start);
403 fallback_paragraph_separate_re =
404 XSYMBOL (Fintern_soft (build_string ("paragraph-separate"), Qnil))->value;
405 if (!STRINGP (fallback_paragraph_separate_re))
406 fallback_paragraph_separate_re = build_string ("[ \t\f]*$");
407 staticpro (&fallback_paragraph_separate_re);
408 Qparagraph_separate = intern ("paragraph-separate");
409 staticpro (&Qparagraph_separate);
410 bidi_initialized = 1;
413 /* Return the bidi type of a character CH, subject to the current
414 directional OVERRIDE. */
415 bidi_type_t
416 bidi_get_type (int ch, bidi_dir_t override)
418 bidi_type_t default_type;
420 if (ch == BIDI_EOB)
421 return NEUTRAL_B;
422 if (ch < 0 || ch > MAX_CHAR)
423 abort ();
425 default_type = (bidi_type_t) XINT (CHAR_TABLE_REF (bidi_type_table, ch));
427 if (override == NEUTRAL_DIR)
428 return default_type;
430 switch (default_type)
432 /* Although UAX#9 does not tell, it doesn't make sense to
433 override NEUTRAL_B and LRM/RLM characters. */
434 case NEUTRAL_B:
435 case LRE:
436 case LRO:
437 case RLE:
438 case RLO:
439 case PDF:
440 return default_type;
441 default:
442 switch (ch)
444 case LRM_CHAR:
445 case RLM_CHAR:
446 return default_type;
447 default:
448 if (override == L2R) /* X6 */
449 return STRONG_L;
450 else if (override == R2L)
451 return STRONG_R;
452 else
453 abort (); /* can't happen: handled above */
458 void
459 bidi_check_type (bidi_type_t type)
461 if (type < UNKNOWN_BT || type > NEUTRAL_ON)
462 abort ();
465 /* Given a bidi TYPE of a character, return its category. */
466 bidi_category_t
467 bidi_get_category (bidi_type_t type)
469 switch (type)
471 case UNKNOWN_BT:
472 return UNKNOWN_BC;
473 case STRONG_L:
474 case STRONG_R:
475 case STRONG_AL:
476 case LRE:
477 case LRO:
478 case RLE:
479 case RLO:
480 return STRONG;
481 case PDF: /* ??? really?? */
482 case WEAK_EN:
483 case WEAK_ES:
484 case WEAK_ET:
485 case WEAK_AN:
486 case WEAK_CS:
487 case WEAK_NSM:
488 case WEAK_BN:
489 return WEAK;
490 case NEUTRAL_B:
491 case NEUTRAL_S:
492 case NEUTRAL_WS:
493 case NEUTRAL_ON:
494 return NEUTRAL;
495 default:
496 abort ();
500 /* Return the mirrored character of C, if any.
502 Note: The conditions in UAX#9 clause L4 must be tested by the
503 caller. */
504 /* FIXME: exceedingly temporary! Should consult the Unicode database
505 of character properties. */
507 bidi_mirror_char (int c)
509 static const char mirrored_pairs[] = "()<>[]{}";
510 const char *p = c > 0 && c < 128 ? strchr (mirrored_pairs, c) : NULL;
512 if (p)
514 size_t i = p - mirrored_pairs;
516 return mirrored_pairs [(i ^ 1)];
518 return c;
521 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
522 copies the part of the level stack that is actually in use. */
523 static inline void
524 bidi_copy_it (struct bidi_it *to, struct bidi_it *from)
526 int i;
528 /* Copy everything except the level stack and beyond. */
529 memcpy (to, from, ((size_t)&((struct bidi_it *)0)->level_stack[0]));
531 /* Copy the active part of the level stack. */
532 to->level_stack[0] = from->level_stack[0]; /* level zero is always in use */
533 for (i = 1; i <= from->stack_idx; i++)
534 to->level_stack[i] = from->level_stack[i];
537 /* Caching the bidi iterator states. */
539 static struct bidi_it bidi_cache[1000]; /* FIXME: make this dynamically allocated! */
540 static int bidi_cache_idx;
541 static int bidi_cache_last_idx;
543 static inline void
544 bidi_cache_reset (void)
546 bidi_cache_idx = 0;
547 bidi_cache_last_idx = -1;
550 static inline void
551 bidi_cache_fetch_state (int idx, struct bidi_it *bidi_it)
553 int current_scan_dir = bidi_it->scan_dir;
555 if (idx < 0 || idx >= bidi_cache_idx)
556 abort ();
558 bidi_copy_it (bidi_it, &bidi_cache[idx]);
559 bidi_it->scan_dir = current_scan_dir;
560 bidi_cache_last_idx = idx;
563 /* Find a cached state with a given CHARPOS and resolved embedding
564 level less or equal to LEVEL. if LEVEL is -1, disregard the
565 resolved levels in cached states. DIR, if non-zero, means search
566 in that direction from the last cache hit. */
567 static inline int
568 bidi_cache_search (int charpos, int level, int dir)
570 int i, i_start;
572 if (bidi_cache_idx)
574 if (charpos < bidi_cache[bidi_cache_last_idx].charpos)
575 dir = -1;
576 else if (charpos > bidi_cache[bidi_cache_last_idx].charpos)
577 dir = 1;
578 if (dir)
579 i_start = bidi_cache_last_idx;
580 else
582 dir = -1;
583 i_start = bidi_cache_idx - 1;
586 if (dir < 0)
588 /* Linear search for now; FIXME! */
589 for (i = i_start; i >= 0; i--)
590 if (bidi_cache[i].charpos == charpos
591 && (level == -1 || bidi_cache[i].resolved_level <= level))
592 return i;
594 else
596 for (i = i_start; i < bidi_cache_idx; i++)
597 if (bidi_cache[i].charpos == charpos
598 && (level == -1 || bidi_cache[i].resolved_level <= level))
599 return i;
603 return -1;
606 /* Find a cached state where the resolved level changes to a value
607 that is lower than LEVEL, and return its cache slot index. DIR is
608 the direction to search, starting with the last used cache slot.
609 BEFORE, if non-zero, means return the index of the slot that is
610 ``before'' the level change in the search direction. That is,
611 given the cached levels like this:
613 1122333442211
614 AB C
616 and assuming we are at the position cached at the slot marked with
617 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
618 index of slot B or A, depending whether BEFORE is, respectively,
619 non-zero or zero. */
620 static int
621 bidi_cache_find_level_change (int level, int dir, int before)
623 if (bidi_cache_idx)
625 int i = dir ? bidi_cache_last_idx : bidi_cache_idx - 1;
626 int incr = before ? 1 : 0;
628 if (!dir)
629 dir = -1;
630 else if (!incr)
631 i += dir;
633 if (dir < 0)
635 while (i >= incr)
637 if (bidi_cache[i - incr].resolved_level >= 0
638 && bidi_cache[i - incr].resolved_level < level)
639 return i;
640 i--;
643 else
645 while (i < bidi_cache_idx - incr)
647 if (bidi_cache[i + incr].resolved_level >= 0
648 && bidi_cache[i + incr].resolved_level < level)
649 return i;
650 i++;
655 return -1;
658 static inline void
659 bidi_cache_iterator_state (struct bidi_it *bidi_it, int resolved)
661 int idx;
663 /* We should never cache on backward scans. */
664 if (bidi_it->scan_dir == -1)
665 abort ();
666 idx = bidi_cache_search (bidi_it->charpos, -1, 1);
668 if (idx < 0)
670 idx = bidi_cache_idx;
671 /* Don't overrun the cache limit. */
672 if (idx > sizeof (bidi_cache) / sizeof (bidi_cache[0]) - 1)
673 abort ();
674 /* Character positions should correspond to cache positions 1:1.
675 If we are outside the range of cached positions, the cache is
676 useless and must be reset. */
677 if (idx > 0 &&
678 (bidi_it->charpos > bidi_cache[idx - 1].charpos + 1
679 || bidi_it->charpos < bidi_cache[0].charpos))
681 bidi_cache_reset ();
682 idx = 0;
684 bidi_copy_it (&bidi_cache[idx], bidi_it);
685 if (!resolved)
686 bidi_cache[idx].resolved_level = -1;
687 bidi_cache[idx].new_paragraph = 0;
689 else
691 /* Copy only the members which could have changed, to avoid
692 costly copying of the entire struct. */
693 bidi_cache[idx].type = bidi_it->type;
694 bidi_check_type (bidi_it->type);
695 bidi_cache[idx].type_after_w1 = bidi_it->type_after_w1;
696 bidi_check_type (bidi_it->type_after_w1);
697 if (resolved)
698 bidi_cache[idx].resolved_level = bidi_it->resolved_level;
699 else
700 bidi_cache[idx].resolved_level = -1;
701 bidi_cache[idx].invalid_levels = bidi_it->invalid_levels;
702 bidi_cache[idx].invalid_rl_levels = bidi_it->invalid_rl_levels;
703 bidi_cache[idx].next_for_neutral = bidi_it->next_for_neutral;
704 bidi_cache[idx].next_for_ws = bidi_it->next_for_ws;
705 bidi_cache[idx].ignore_bn_limit = bidi_it->ignore_bn_limit;
708 bidi_cache_last_idx = idx;
709 if (idx >= bidi_cache_idx)
710 bidi_cache_idx = idx + 1;
713 static inline bidi_type_t
714 bidi_cache_find (int charpos, int level, struct bidi_it *bidi_it)
716 int i = bidi_cache_search (charpos, level, bidi_it->scan_dir);
718 if (i >= 0)
720 bidi_dir_t current_scan_dir = bidi_it->scan_dir;
722 bidi_copy_it (bidi_it, &bidi_cache[i]);
723 bidi_cache_last_idx = i;
724 /* Don't let scan direction from from the cached state override
725 the current scan direction. */
726 bidi_it->scan_dir = current_scan_dir;
727 return bidi_it->type;
730 return UNKNOWN_BT;
733 static inline int
734 bidi_peek_at_next_level (struct bidi_it *bidi_it)
736 if (bidi_cache_idx == 0 || bidi_cache_last_idx == -1)
737 abort ();
738 return bidi_cache[bidi_cache_last_idx + bidi_it->scan_dir].resolved_level;
741 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
742 Value is the non-negative length of the paragraph separator
743 following the buffer position, -1 if position is at the beginning
744 of a new paragraph, or -2 if position is neither at beginning nor
745 at end of a paragraph. */
746 EMACS_INT
747 bidi_at_paragraph_end (EMACS_INT charpos, EMACS_INT bytepos)
749 Lisp_Object sep_re = Fbuffer_local_value (Qparagraph_separate,
750 Fcurrent_buffer ());
751 Lisp_Object start_re = Fbuffer_local_value (Qparagraph_start,
752 Fcurrent_buffer ());
753 EMACS_INT val;
755 if (!STRINGP (sep_re))
756 sep_re = fallback_paragraph_separate_re;
757 if (!STRINGP (start_re))
758 start_re = fallback_paragraph_start_re;
760 val = fast_looking_at (sep_re, charpos, bytepos, ZV, ZV_BYTE, Qnil);
761 if (val < 0)
763 if (fast_looking_at (start_re, charpos, bytepos, ZV, ZV_BYTE, Qnil) >= 0)
764 val = -1;
765 else
766 val = -2;
769 return val;
772 /* Determine the start-of-run (sor) directional type given the two
773 embedding levels on either side of the run boundary. Also, update
774 the saved info about previously seen characters, since that info is
775 generally valid for a single level run. */
776 static inline void
777 bidi_set_sor_type (struct bidi_it *bidi_it, int level_before, int level_after)
779 int higher_level = level_before > level_after ? level_before : level_after;
781 /* The prev_was_pdf gork is required for when we have several PDFs
782 in a row. In that case, we want to compute the sor type for the
783 next level run only once: when we see the first PDF. That's
784 because the sor type depends only on the higher of the two levels
785 that we find on the two sides of the level boundary (see UAX#9,
786 clause X10), and so we don't need to know the final embedding
787 level to which we descend after processing all the PDFs. */
788 if (!bidi_it->prev_was_pdf || level_before < level_after)
789 /* FIXME: should the default sor direction be user selectable? */
790 bidi_it->sor = (higher_level & 1) != 0 ? R2L : L2R;
791 if (level_before > level_after)
792 bidi_it->prev_was_pdf = 1;
794 bidi_it->prev.type = UNKNOWN_BT;
795 bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1 =
796 bidi_it->last_strong.orig_type = UNKNOWN_BT;
797 bidi_it->prev_for_neutral.type = bidi_it->sor == R2L ? STRONG_R : STRONG_L;
798 bidi_it->prev_for_neutral.charpos = bidi_it->charpos;
799 bidi_it->prev_for_neutral.bytepos = bidi_it->bytepos;
800 bidi_it->next_for_neutral.type = bidi_it->next_for_neutral.type_after_w1 =
801 bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
802 bidi_it->ignore_bn_limit = 0; /* meaning it's unknown */
805 static void
806 bidi_line_init (struct bidi_it *bidi_it)
808 bidi_it->scan_dir = 1; /* FIXME: do we need to have control on this? */
809 bidi_it->resolved_level = bidi_it->level_stack[0].level;
810 bidi_it->level_stack[0].override = NEUTRAL_DIR; /* X1 */
811 bidi_it->invalid_levels = 0;
812 bidi_it->invalid_rl_levels = -1;
813 bidi_it->next_en_pos = -1;
814 bidi_it->next_for_ws.type = UNKNOWN_BT;
815 bidi_set_sor_type (bidi_it,
816 bidi_it->paragraph_dir == R2L ? 1 : 0,
817 bidi_it->level_stack[0].level); /* X10 */
819 bidi_cache_reset ();
822 /* Find the beginning of this paragraph by looking back in the buffer.
823 Value is the byte position of the paragraph's beginning. */
824 static EMACS_INT
825 bidi_find_paragraph_start (EMACS_INT pos, EMACS_INT pos_byte)
827 Lisp_Object re = Fbuffer_local_value (Qparagraph_start, Fcurrent_buffer ());
828 EMACS_INT limit = ZV, limit_byte = ZV_BYTE;
830 if (!STRINGP (re))
831 re = fallback_paragraph_start_re;
832 while (pos_byte > BEGV_BYTE
833 && fast_looking_at (re, pos, pos_byte, limit, limit_byte, Qnil) < 0)
835 pos = find_next_newline_no_quit (pos - 1, -1);
836 pos_byte = CHAR_TO_BYTE (pos);
838 return pos_byte;
841 /* Determine the direction, a.k.a. base embedding level, of the
842 paragraph we are about to iterate through. If DIR is either L2R or
843 R2L, just use that. Otherwise, determine the paragraph direction
844 from the first strong character of the paragraph.
846 Note that this gives the paragraph separator the same direction as
847 the preceding paragraph, even though Emacs generally views the
848 separartor as not belonging to any paragraph. */
849 void
850 bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it)
852 EMACS_INT bytepos = bidi_it->bytepos;
854 /* Special case for an empty buffer. */
855 if (bytepos == BEGV_BYTE && bytepos == ZV_BYTE)
856 dir = L2R;
857 /* We should never be called at EOB or before BEGV. */
858 else if (bytepos >= ZV_BYTE || bytepos < BEGV_BYTE)
859 abort ();
861 if (dir == L2R)
863 bidi_it->paragraph_dir = L2R;
864 bidi_it->new_paragraph = 0;
866 else if (dir == R2L)
868 bidi_it->paragraph_dir = R2L;
869 bidi_it->new_paragraph = 0;
871 else if (dir == NEUTRAL_DIR) /* P2 */
873 int ch, ch_len;
874 EMACS_INT pos;
875 bidi_type_t type;
876 EMACS_INT sep_len;
878 /* If we are inside a paragraph separator, we are just waiting
879 for the separator to be exhausted; use the previous paragraph
880 direction. But don't do that if we have been just reseated,
881 because we need to reinitialize below in that case. */
882 if (!bidi_it->first_elt
883 && bidi_it->charpos < bidi_it->separator_limit)
884 return;
886 /* If we are on a newline, get past it to where the next
887 paragraph might start. But don't do that at BEGV since then
888 we are potentially in a new paragraph that doesn't yet
889 exist. */
890 pos = bidi_it->charpos;
891 if (bytepos > BEGV_BYTE && FETCH_CHAR (bytepos) == '\n')
893 bytepos++;
894 pos++;
897 /* We are either at the beginning of a paragraph or in the
898 middle of it. Find where this paragraph starts. */
899 bytepos = bidi_find_paragraph_start (pos, bytepos);
901 /* We should always be at the beginning of a new line at this
902 point. */
903 if (!(bytepos == BEGV_BYTE || FETCH_CHAR (bytepos - 1) == '\n'))
904 abort ();
906 bidi_it->separator_limit = -1;
907 bidi_it->new_paragraph = 0;
908 ch = FETCH_CHAR (bytepos);
909 ch_len = CHAR_BYTES (ch);
910 pos = BYTE_TO_CHAR (bytepos);
911 type = bidi_get_type (ch, NEUTRAL_DIR);
913 for (pos++, bytepos += ch_len;
914 /* NOTE: UAX#9 says to search only for L, AL, or R types of
915 characters, and ignore RLE, RLO, LRE, and LRO. However,
916 I'm not sure it makes sense to omit those 4; should try
917 with and without that to see the effect. */
918 (bidi_get_category (type) != STRONG)
919 || (bidi_ignore_explicit_marks_for_paragraph_level
920 && (type == RLE || type == RLO
921 || type == LRE || type == LRO));
922 type = bidi_get_type (ch, NEUTRAL_DIR))
924 if (type == NEUTRAL_B && bidi_at_paragraph_end (pos, bytepos) >= -1)
925 break;
926 if (bytepos >= ZV_BYTE)
928 /* Pretend there's a paragraph separator at end of buffer. */
929 type = NEUTRAL_B;
930 break;
932 FETCH_CHAR_ADVANCE (ch, pos, bytepos);
934 if (type == STRONG_R || type == STRONG_AL) /* P3 */
935 bidi_it->paragraph_dir = R2L;
936 else if (type == STRONG_L)
937 bidi_it->paragraph_dir = L2R;
939 else
940 abort ();
942 /* Contrary to UAX#9 clause P3, we only default the paragraph
943 direction to L2R if we have no previous usable paragraph
944 direction. */
945 if (bidi_it->paragraph_dir == NEUTRAL_DIR)
946 bidi_it->paragraph_dir = L2R; /* P3 and ``higher protocols'' */
947 if (bidi_it->paragraph_dir == R2L)
948 bidi_it->level_stack[0].level = 1;
949 else
950 bidi_it->level_stack[0].level = 0;
952 bidi_line_init (bidi_it);
955 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
956 end. */
957 static inline void
958 bidi_set_paragraph_end (struct bidi_it *bidi_it)
960 bidi_it->invalid_levels = 0;
961 bidi_it->invalid_rl_levels = -1;
962 bidi_it->stack_idx = 0;
963 bidi_it->resolved_level = bidi_it->level_stack[0].level;
966 /* Initialize the bidi iterator from buffer position CHARPOS. */
967 void
968 bidi_init_it (EMACS_INT charpos, EMACS_INT bytepos, struct bidi_it *bidi_it)
970 if (! bidi_initialized)
971 bidi_initialize ();
972 bidi_it->charpos = charpos;
973 bidi_it->bytepos = bytepos;
974 bidi_it->first_elt = 1;
975 bidi_set_paragraph_end (bidi_it);
976 bidi_it->new_paragraph = 1;
977 bidi_it->separator_limit = -1;
978 bidi_it->type = NEUTRAL_B;
979 bidi_it->type_after_w1 = UNKNOWN_BT;
980 bidi_it->orig_type = UNKNOWN_BT;
981 bidi_it->prev_was_pdf = 0;
982 bidi_it->prev.type = bidi_it->prev.type_after_w1 = UNKNOWN_BT;
983 bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1 =
984 bidi_it->last_strong.orig_type = UNKNOWN_BT;
985 bidi_it->next_for_neutral.charpos = -1;
986 bidi_it->next_for_neutral.type =
987 bidi_it->next_for_neutral.type_after_w1 =
988 bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
989 bidi_it->prev_for_neutral.charpos = -1;
990 bidi_it->prev_for_neutral.type =
991 bidi_it->prev_for_neutral.type_after_w1 =
992 bidi_it->prev_for_neutral.orig_type = UNKNOWN_BT;
993 bidi_it->sor = L2R; /* FIXME: should it be user-selectable? */
996 /* Push the current embedding level and override status; reset the
997 current level to LEVEL and the current override status to OVERRIDE. */
998 static inline void
999 bidi_push_embedding_level (struct bidi_it *bidi_it,
1000 int level, bidi_dir_t override)
1002 bidi_it->stack_idx++;
1003 if (bidi_it->stack_idx >= BIDI_MAXLEVEL)
1004 abort ();
1005 bidi_it->level_stack[bidi_it->stack_idx].level = level;
1006 bidi_it->level_stack[bidi_it->stack_idx].override = override;
1009 /* Pop the embedding level and directional override status from the
1010 stack, and return the new level. */
1011 static inline int
1012 bidi_pop_embedding_level (struct bidi_it *bidi_it)
1014 /* UAX#9 says to ignore invalid PDFs. */
1015 if (bidi_it->stack_idx > 0)
1016 bidi_it->stack_idx--;
1017 return bidi_it->level_stack[bidi_it->stack_idx].level;
1020 /* Record in SAVED_INFO the information about the current character. */
1021 static inline void
1022 bidi_remember_char (struct bidi_saved_info *saved_info,
1023 struct bidi_it *bidi_it)
1025 saved_info->charpos = bidi_it->charpos;
1026 saved_info->bytepos = bidi_it->bytepos;
1027 saved_info->type = bidi_it->type;
1028 bidi_check_type (bidi_it->type);
1029 saved_info->type_after_w1 = bidi_it->type_after_w1;
1030 bidi_check_type (bidi_it->type_after_w1);
1031 saved_info->orig_type = bidi_it->orig_type;
1032 bidi_check_type (bidi_it->orig_type);
1035 /* Resolve the type of a neutral character according to the type of
1036 surrounding strong text and the current embedding level. */
1037 static inline bidi_type_t
1038 bidi_resolve_neutral_1 (bidi_type_t prev_type, bidi_type_t next_type, int lev)
1040 /* N1: European and Arabic numbers are treated as though they were R. */
1041 if (next_type == WEAK_EN || next_type == WEAK_AN)
1042 next_type = STRONG_R;
1043 if (prev_type == WEAK_EN || prev_type == WEAK_AN)
1044 prev_type = STRONG_R;
1046 if (next_type == prev_type) /* N1 */
1047 return next_type;
1048 else if ((lev & 1) == 0) /* N2 */
1049 return STRONG_L;
1050 else
1051 return STRONG_R;
1054 static inline int
1055 bidi_explicit_dir_char (int c)
1057 /* FIXME: this should be replaced with a lookup table with suitable
1058 bits set, like standard C ctype macros do. */
1059 return (c == LRE_CHAR || c == LRO_CHAR
1060 || c == RLE_CHAR || c == RLO_CHAR || c == PDF_CHAR);
1063 /* A helper function for bidi_resolve_explicit. It advances to the
1064 next character in logical order and determines the new embedding
1065 level and directional override, but does not take into account
1066 empty embeddings. */
1067 static int
1068 bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
1070 int curchar;
1071 bidi_type_t type;
1072 int current_level;
1073 int new_level;
1074 bidi_dir_t override;
1076 if (bidi_it->bytepos < BEGV_BYTE /* after reseat to BEGV? */
1077 || bidi_it->first_elt)
1079 bidi_it->first_elt = 0;
1080 if (bidi_it->charpos < BEGV)
1081 bidi_it->charpos = BEGV;
1082 bidi_it->bytepos = CHAR_TO_BYTE (bidi_it->charpos);
1084 else if (bidi_it->bytepos < ZV_BYTE) /* don't move at ZV */
1086 bidi_it->charpos++;
1087 if (bidi_it->ch_len == 0)
1088 abort ();
1089 bidi_it->bytepos += bidi_it->ch_len;
1092 current_level = bidi_it->level_stack[bidi_it->stack_idx].level; /* X1 */
1093 override = bidi_it->level_stack[bidi_it->stack_idx].override;
1094 new_level = current_level;
1096 /* in case it is a unibyte character (not yet implemented) */
1097 /* _fetch_multibyte_char_len = 1; */
1098 if (bidi_it->bytepos >= ZV_BYTE)
1100 curchar = BIDI_EOB;
1101 bidi_it->ch_len = 1;
1103 else
1105 curchar = FETCH_CHAR (bidi_it->bytepos);
1106 bidi_it->ch_len = CHAR_BYTES (curchar);
1108 bidi_it->ch = curchar;
1110 /* Don't apply directional override here, as all the types we handle
1111 below will not be affected by the override anyway, and we need
1112 the original type unaltered. The override will be applied in
1113 bidi_resolve_weak. */
1114 type = bidi_get_type (curchar, NEUTRAL_DIR);
1115 bidi_it->orig_type = type;
1116 bidi_check_type (bidi_it->orig_type);
1118 if (type != PDF)
1119 bidi_it->prev_was_pdf = 0;
1121 bidi_it->type_after_w1 = UNKNOWN_BT;
1123 switch (type)
1125 case RLE: /* X2 */
1126 case RLO: /* X4 */
1127 bidi_it->type_after_w1 = type;
1128 bidi_check_type (bidi_it->type_after_w1);
1129 type = WEAK_BN; /* X9/Retaining */
1130 if (bidi_it->ignore_bn_limit <= 0)
1132 if (current_level <= BIDI_MAXLEVEL - 4)
1134 /* Compute the least odd embedding level greater than
1135 the current level. */
1136 new_level = ((current_level + 1) & ~1) + 1;
1137 if (bidi_it->type_after_w1 == RLE)
1138 override = NEUTRAL_DIR;
1139 else
1140 override = R2L;
1141 if (current_level == BIDI_MAXLEVEL - 4)
1142 bidi_it->invalid_rl_levels = 0;
1143 bidi_push_embedding_level (bidi_it, new_level, override);
1145 else
1147 bidi_it->invalid_levels++;
1148 /* See the commentary about invalid_rl_levels below. */
1149 if (bidi_it->invalid_rl_levels < 0)
1150 bidi_it->invalid_rl_levels = 0;
1151 bidi_it->invalid_rl_levels++;
1154 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1155 || bidi_it->next_en_pos > bidi_it->charpos)
1156 type = WEAK_EN;
1157 break;
1158 case LRE: /* X3 */
1159 case LRO: /* X5 */
1160 bidi_it->type_after_w1 = type;
1161 bidi_check_type (bidi_it->type_after_w1);
1162 type = WEAK_BN; /* X9/Retaining */
1163 if (bidi_it->ignore_bn_limit <= 0)
1165 if (current_level <= BIDI_MAXLEVEL - 5)
1167 /* Compute the least even embedding level greater than
1168 the current level. */
1169 new_level = ((current_level + 2) & ~1);
1170 if (bidi_it->type_after_w1 == LRE)
1171 override = NEUTRAL_DIR;
1172 else
1173 override = L2R;
1174 bidi_push_embedding_level (bidi_it, new_level, override);
1176 else
1178 bidi_it->invalid_levels++;
1179 /* invalid_rl_levels counts invalid levels encountered
1180 while the embedding level was already too high for
1181 LRE/LRO, but not for RLE/RLO. That is because
1182 there may be exactly one PDF which we should not
1183 ignore even though invalid_levels is non-zero.
1184 invalid_rl_levels helps to know what PDF is
1185 that. */
1186 if (bidi_it->invalid_rl_levels >= 0)
1187 bidi_it->invalid_rl_levels++;
1190 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1191 || bidi_it->next_en_pos > bidi_it->charpos)
1192 type = WEAK_EN;
1193 break;
1194 case PDF: /* X7 */
1195 bidi_it->type_after_w1 = type;
1196 bidi_check_type (bidi_it->type_after_w1);
1197 type = WEAK_BN; /* X9/Retaining */
1198 if (bidi_it->ignore_bn_limit <= 0)
1200 if (!bidi_it->invalid_rl_levels)
1202 new_level = bidi_pop_embedding_level (bidi_it);
1203 bidi_it->invalid_rl_levels = -1;
1204 if (bidi_it->invalid_levels)
1205 bidi_it->invalid_levels--;
1206 /* else nothing: UAX#9 says to ignore invalid PDFs */
1208 if (!bidi_it->invalid_levels)
1209 new_level = bidi_pop_embedding_level (bidi_it);
1210 else
1212 bidi_it->invalid_levels--;
1213 bidi_it->invalid_rl_levels--;
1216 else if (bidi_it->prev.type_after_w1 == WEAK_EN /* W5/Retaining */
1217 || bidi_it->next_en_pos > bidi_it->charpos)
1218 type = WEAK_EN;
1219 break;
1220 default:
1221 /* Nothing. */
1222 break;
1225 bidi_it->type = type;
1226 bidi_check_type (bidi_it->type);
1228 return new_level;
1231 /* Given an iterator state in BIDI_IT, advance one character position
1232 in the buffer to the next character (in the logical order), resolve
1233 any explicit embeddings and directional overrides, and return the
1234 embedding level of the character after resolving explicit
1235 directives and ignoring empty embeddings. */
1236 static int
1237 bidi_resolve_explicit (struct bidi_it *bidi_it)
1239 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1240 int new_level = bidi_resolve_explicit_1 (bidi_it);
1242 if (prev_level < new_level
1243 && bidi_it->type == WEAK_BN
1244 && bidi_it->ignore_bn_limit == 0 /* only if not already known */
1245 && bidi_it->bytepos < ZV_BYTE /* not already at EOB */
1246 && bidi_explicit_dir_char (FETCH_CHAR (bidi_it->bytepos
1247 + bidi_it->ch_len)))
1249 /* Avoid pushing and popping embedding levels if the level run
1250 is empty, as this breaks level runs where it shouldn't.
1251 UAX#9 removes all the explicit embedding and override codes,
1252 so empty embeddings disappear without a trace. We need to
1253 behave as if we did the same. */
1254 struct bidi_it saved_it;
1255 int level = prev_level;
1257 bidi_copy_it (&saved_it, bidi_it);
1259 while (bidi_explicit_dir_char (FETCH_CHAR (bidi_it->bytepos
1260 + bidi_it->ch_len)))
1262 level = bidi_resolve_explicit_1 (bidi_it);
1265 if (level == prev_level) /* empty embedding */
1266 saved_it.ignore_bn_limit = bidi_it->charpos + 1;
1267 else /* this embedding is non-empty */
1268 saved_it.ignore_bn_limit = -1;
1270 bidi_copy_it (bidi_it, &saved_it);
1271 if (bidi_it->ignore_bn_limit > 0)
1273 /* We pushed a level, but we shouldn't have. Undo that. */
1274 if (!bidi_it->invalid_rl_levels)
1276 new_level = bidi_pop_embedding_level (bidi_it);
1277 bidi_it->invalid_rl_levels = -1;
1278 if (bidi_it->invalid_levels)
1279 bidi_it->invalid_levels--;
1281 if (!bidi_it->invalid_levels)
1282 new_level = bidi_pop_embedding_level (bidi_it);
1283 else
1285 bidi_it->invalid_levels--;
1286 bidi_it->invalid_rl_levels--;
1291 if (bidi_it->type == NEUTRAL_B) /* X8 */
1293 bidi_set_paragraph_end (bidi_it);
1294 /* This is needed by bidi_resolve_weak below, and in L1. */
1295 bidi_it->type_after_w1 = bidi_it->type;
1296 bidi_check_type (bidi_it->type_after_w1);
1299 return new_level;
1302 /* Advance in the buffer, resolve weak types and return the type of
1303 the next character after weak type resolution. */
1304 bidi_type_t
1305 bidi_resolve_weak (struct bidi_it *bidi_it)
1307 bidi_type_t type;
1308 bidi_dir_t override;
1309 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1310 int new_level = bidi_resolve_explicit (bidi_it);
1311 int next_char;
1312 bidi_type_t type_of_next;
1313 struct bidi_it saved_it;
1315 type = bidi_it->type;
1316 override = bidi_it->level_stack[bidi_it->stack_idx].override;
1318 if (type == UNKNOWN_BT
1319 || type == LRE
1320 || type == LRO
1321 || type == RLE
1322 || type == RLO
1323 || type == PDF)
1324 abort ();
1326 if (new_level != prev_level
1327 || bidi_it->type == NEUTRAL_B)
1329 /* We've got a new embedding level run, compute the directional
1330 type of sor and initialize per-run variables (UAX#9, clause
1331 X10). */
1332 bidi_set_sor_type (bidi_it, prev_level, new_level);
1334 else if (type == NEUTRAL_S || type == NEUTRAL_WS
1335 || type == WEAK_BN || type == STRONG_AL)
1336 bidi_it->type_after_w1 = type; /* needed in L1 */
1337 bidi_check_type (bidi_it->type_after_w1);
1339 /* Level and directional override status are already recorded in
1340 bidi_it, and do not need any change; see X6. */
1341 if (override == R2L) /* X6 */
1342 type = STRONG_R;
1343 else if (override == L2R)
1344 type = STRONG_L;
1345 else
1347 if (type == WEAK_NSM) /* W1 */
1349 /* Note that we don't need to consider the case where the
1350 prev character has its type overridden by an RLO or LRO,
1351 because then either the type of this NSM would have been
1352 also overridden, or the previous character is outside the
1353 current level run, and thus not relevant to this NSM.
1354 This is why NSM gets the type_after_w1 of the previous
1355 character. */
1356 if (bidi_it->prev.type != UNKNOWN_BT)
1357 type = bidi_it->prev.type_after_w1;
1358 else if (bidi_it->sor == R2L)
1359 type = STRONG_R;
1360 else if (bidi_it->sor == L2R)
1361 type = STRONG_L;
1362 else /* shouldn't happen! */
1363 abort ();
1365 if (type == WEAK_EN /* W2 */
1366 && bidi_it->last_strong.type_after_w1 == STRONG_AL)
1367 type = WEAK_AN;
1368 else if (type == STRONG_AL) /* W3 */
1369 type = STRONG_R;
1370 else if ((type == WEAK_ES /* W4 */
1371 && bidi_it->prev.type_after_w1 == WEAK_EN
1372 && bidi_it->prev.orig_type == WEAK_EN)
1373 || (type == WEAK_CS
1374 && ((bidi_it->prev.type_after_w1 == WEAK_EN
1375 && bidi_it->prev.orig_type == WEAK_EN)
1376 || bidi_it->prev.type_after_w1 == WEAK_AN)))
1378 next_char =
1379 bidi_it->bytepos + bidi_it->ch_len >= ZV_BYTE
1380 ? BIDI_EOB : FETCH_CHAR (bidi_it->bytepos + bidi_it->ch_len);
1381 type_of_next = bidi_get_type (next_char, override);
1383 if (type_of_next == WEAK_BN
1384 || bidi_explicit_dir_char (next_char))
1386 bidi_copy_it (&saved_it, bidi_it);
1387 while (bidi_resolve_explicit (bidi_it) == new_level
1388 && bidi_it->type == WEAK_BN)
1390 type_of_next = bidi_it->type;
1391 bidi_copy_it (bidi_it, &saved_it);
1394 /* If the next character is EN, but the last strong-type
1395 character is AL, that next EN will be changed to AN when
1396 we process it in W2 above. So in that case, this ES
1397 should not be changed into EN. */
1398 if (type == WEAK_ES
1399 && type_of_next == WEAK_EN
1400 && bidi_it->last_strong.type_after_w1 != STRONG_AL)
1401 type = WEAK_EN;
1402 else if (type == WEAK_CS)
1404 if (bidi_it->prev.type_after_w1 == WEAK_AN
1405 && (type_of_next == WEAK_AN
1406 /* If the next character is EN, but the last
1407 strong-type character is AL, EN will be later
1408 changed to AN when we process it in W2 above.
1409 So in that case, this ES should not be
1410 changed into EN. */
1411 || (type_of_next == WEAK_EN
1412 && bidi_it->last_strong.type_after_w1 == STRONG_AL)))
1413 type = WEAK_AN;
1414 else if (bidi_it->prev.type_after_w1 == WEAK_EN
1415 && type_of_next == WEAK_EN
1416 && bidi_it->last_strong.type_after_w1 != STRONG_AL)
1417 type = WEAK_EN;
1420 else if (type == WEAK_ET /* W5: ET with EN before or after it */
1421 || type == WEAK_BN) /* W5/Retaining */
1423 if (bidi_it->prev.type_after_w1 == WEAK_EN /* ET/BN w/EN before it */
1424 || bidi_it->next_en_pos > bidi_it->charpos)
1425 type = WEAK_EN;
1426 else /* W5: ET/BN with EN after it. */
1428 EMACS_INT en_pos = bidi_it->charpos + 1;
1430 next_char =
1431 bidi_it->bytepos + bidi_it->ch_len >= ZV_BYTE
1432 ? BIDI_EOB : FETCH_CHAR (bidi_it->bytepos + bidi_it->ch_len);
1433 type_of_next = bidi_get_type (next_char, override);
1435 if (type_of_next == WEAK_ET
1436 || type_of_next == WEAK_BN
1437 || bidi_explicit_dir_char (next_char))
1439 bidi_copy_it (&saved_it, bidi_it);
1440 while (bidi_resolve_explicit (bidi_it) == new_level
1441 && (bidi_it->type == WEAK_BN
1442 || bidi_it->type == WEAK_ET))
1444 type_of_next = bidi_it->type;
1445 en_pos = bidi_it->charpos;
1446 bidi_copy_it (bidi_it, &saved_it);
1448 if (type_of_next == WEAK_EN)
1450 /* If the last strong character is AL, the EN we've
1451 found will become AN when we get to it (W2). */
1452 if (bidi_it->last_strong.type_after_w1 != STRONG_AL)
1454 type = WEAK_EN;
1455 /* Remember this EN position, to speed up processing
1456 of the next ETs. */
1457 bidi_it->next_en_pos = en_pos;
1459 else if (type == WEAK_BN)
1460 type = NEUTRAL_ON; /* W6/Retaining */
1466 if (type == WEAK_ES || type == WEAK_ET || type == WEAK_CS /* W6 */
1467 || (type == WEAK_BN
1468 && (bidi_it->prev.type_after_w1 == WEAK_CS /* W6/Retaining */
1469 || bidi_it->prev.type_after_w1 == WEAK_ES
1470 || bidi_it->prev.type_after_w1 == WEAK_ET)))
1471 type = NEUTRAL_ON;
1473 /* Store the type we've got so far, before we clobber it with strong
1474 types in W7 and while resolving neutral types. But leave alone
1475 the original types that were recorded above, because we will need
1476 them for the L1 clause. */
1477 if (bidi_it->type_after_w1 == UNKNOWN_BT)
1478 bidi_it->type_after_w1 = type;
1479 bidi_check_type (bidi_it->type_after_w1);
1481 if (type == WEAK_EN) /* W7 */
1483 if ((bidi_it->last_strong.type_after_w1 == STRONG_L)
1484 || (bidi_it->last_strong.type == UNKNOWN_BT && bidi_it->sor == L2R))
1485 type = STRONG_L;
1488 bidi_it->type = type;
1489 bidi_check_type (bidi_it->type);
1490 return type;
1493 bidi_type_t
1494 bidi_resolve_neutral (struct bidi_it *bidi_it)
1496 int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1497 bidi_type_t type = bidi_resolve_weak (bidi_it);
1498 int current_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1500 if (!(type == STRONG_R
1501 || type == STRONG_L
1502 || type == WEAK_BN
1503 || type == WEAK_EN
1504 || type == WEAK_AN
1505 || type == NEUTRAL_B
1506 || type == NEUTRAL_S
1507 || type == NEUTRAL_WS
1508 || type == NEUTRAL_ON))
1509 abort ();
1511 if (bidi_get_category (type) == NEUTRAL
1512 || (type == WEAK_BN && prev_level == current_level))
1514 if (bidi_it->next_for_neutral.type != UNKNOWN_BT)
1515 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1516 bidi_it->next_for_neutral.type,
1517 current_level);
1518 else
1520 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1521 the assumption of batch-style processing; see clauses W4,
1522 W5, and especially N1, which require to look far forward
1523 (as well as back) in the buffer. May the fleas of a
1524 thousand camels infest the armpits of those who design
1525 supposedly general-purpose algorithms by looking at their
1526 own implementations, and fail to consider other possible
1527 implementations! */
1528 struct bidi_it saved_it;
1529 bidi_type_t next_type;
1531 if (bidi_it->scan_dir == -1)
1532 abort ();
1534 bidi_copy_it (&saved_it, bidi_it);
1535 /* Scan the text forward until we find the first non-neutral
1536 character, and then use that to resolve the neutral we
1537 are dealing with now. We also cache the scanned iterator
1538 states, to salvage some of the effort later. */
1539 bidi_cache_iterator_state (bidi_it, 0);
1540 do {
1541 /* Record the info about the previous character, so that
1542 it will be cached below with this state. */
1543 if (bidi_it->type_after_w1 != WEAK_BN /* W1/Retaining */
1544 && bidi_it->type != WEAK_BN)
1545 bidi_remember_char (&bidi_it->prev, bidi_it);
1546 type = bidi_resolve_weak (bidi_it);
1547 /* Paragraph separators have their levels fully resolved
1548 at this point, so cache them as resolved. */
1549 bidi_cache_iterator_state (bidi_it, type == NEUTRAL_B);
1550 /* FIXME: implement L1 here, by testing for a newline and
1551 resetting the level for any sequence of whitespace
1552 characters adjacent to it. */
1553 } while (!(type == NEUTRAL_B
1554 || (type != WEAK_BN
1555 && bidi_get_category (type) != NEUTRAL)
1556 /* This is all per level run, so stop when we
1557 reach the end of this level run. */
1558 || bidi_it->level_stack[bidi_it->stack_idx].level !=
1559 current_level));
1561 bidi_remember_char (&saved_it.next_for_neutral, bidi_it);
1563 switch (type)
1565 case STRONG_L:
1566 case STRONG_R:
1567 case STRONG_AL:
1568 next_type = type;
1569 break;
1570 case WEAK_EN:
1571 case WEAK_AN:
1572 /* N1: ``European and Arabic numbers are treated as
1573 though they were R.'' */
1574 next_type = STRONG_R;
1575 saved_it.next_for_neutral.type = STRONG_R;
1576 break;
1577 case WEAK_BN:
1578 if (!bidi_explicit_dir_char (bidi_it->ch))
1579 abort (); /* can't happen: BNs are skipped */
1580 /* FALLTHROUGH */
1581 case NEUTRAL_B:
1582 /* Marched all the way to the end of this level run.
1583 We need to use the eor type, whose information is
1584 stored by bidi_set_sor_type in the prev_for_neutral
1585 member. */
1586 if (saved_it.type != WEAK_BN
1587 || bidi_get_category (bidi_it->prev.type_after_w1) == NEUTRAL)
1589 next_type = bidi_it->prev_for_neutral.type;
1590 saved_it.next_for_neutral.type = next_type;
1591 bidi_check_type (next_type);
1593 else
1595 /* This is a BN which does not adjoin neutrals.
1596 Leave its type alone. */
1597 bidi_copy_it (bidi_it, &saved_it);
1598 return bidi_it->type;
1600 break;
1601 default:
1602 abort ();
1604 type = bidi_resolve_neutral_1 (saved_it.prev_for_neutral.type,
1605 next_type, current_level);
1606 saved_it.type = type;
1607 bidi_check_type (type);
1608 bidi_copy_it (bidi_it, &saved_it);
1611 return type;
1614 /* Given an iterator state in BIDI_IT, advance one character position
1615 in the buffer to the next character (in the logical order), resolve
1616 the bidi type of that next character, and return that type. */
1617 bidi_type_t
1618 bidi_type_of_next_char (struct bidi_it *bidi_it)
1620 bidi_type_t type;
1622 /* This should always be called during a forward scan. */
1623 if (bidi_it->scan_dir != 1)
1624 abort ();
1626 /* Reset the limit until which to ignore BNs if we step out of the
1627 area where we found only empty levels. */
1628 if ((bidi_it->ignore_bn_limit > 0
1629 && bidi_it->ignore_bn_limit <= bidi_it->charpos)
1630 || (bidi_it->ignore_bn_limit == -1
1631 && !bidi_explicit_dir_char (bidi_it->ch)))
1632 bidi_it->ignore_bn_limit = 0;
1634 type = bidi_resolve_neutral (bidi_it);
1636 return type;
1639 /* Given an iterator state BIDI_IT, advance one character position in
1640 the buffer to the next character (in the logical order), resolve
1641 the embedding and implicit levels of that next character, and
1642 return the resulting level. */
1644 bidi_level_of_next_char (struct bidi_it *bidi_it)
1646 bidi_type_t type;
1647 int level, prev_level = -1;
1648 struct bidi_saved_info next_for_neutral;
1650 if (bidi_it->scan_dir == 1)
1652 /* There's no sense in trying to advance if we hit end of text. */
1653 if (bidi_it->bytepos >= ZV_BYTE)
1654 return bidi_it->resolved_level;
1656 /* Record the info about the previous character. */
1657 if (bidi_it->type_after_w1 != WEAK_BN /* W1/Retaining */
1658 && bidi_it->type != WEAK_BN)
1659 bidi_remember_char (&bidi_it->prev, bidi_it);
1660 if (bidi_it->type_after_w1 == STRONG_R
1661 || bidi_it->type_after_w1 == STRONG_L
1662 || bidi_it->type_after_w1 == STRONG_AL)
1663 bidi_remember_char (&bidi_it->last_strong, bidi_it);
1664 /* FIXME: it sounds like we don't need both prev and
1665 prev_for_neutral members, but I'm leaving them both for now. */
1666 if (bidi_it->type == STRONG_R || bidi_it->type == STRONG_L
1667 || bidi_it->type == WEAK_EN || bidi_it->type == WEAK_AN)
1668 bidi_remember_char (&bidi_it->prev_for_neutral, bidi_it);
1670 /* If we overstepped the characters used for resolving neutrals
1671 and whitespace, invalidate their info in the iterator. */
1672 if (bidi_it->charpos >= bidi_it->next_for_neutral.charpos)
1673 bidi_it->next_for_neutral.type = UNKNOWN_BT;
1674 if (bidi_it->next_en_pos >= 0
1675 && bidi_it->charpos >= bidi_it->next_en_pos)
1676 bidi_it->next_en_pos = -1;
1677 if (bidi_it->next_for_ws.type != UNKNOWN_BT
1678 && bidi_it->charpos >= bidi_it->next_for_ws.charpos)
1679 bidi_it->next_for_ws.type = UNKNOWN_BT;
1681 /* This must be taken before we fill the iterator with the info
1682 about the next char. If we scan backwards, the iterator
1683 state must be already cached, so there's no need to know the
1684 embedding level of the previous character, since we will be
1685 returning to our caller shortly. */
1686 prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
1688 next_for_neutral = bidi_it->next_for_neutral;
1690 /* Perhaps it is already cached. */
1691 type = bidi_cache_find (bidi_it->charpos + bidi_it->scan_dir, -1, bidi_it);
1692 if (type != UNKNOWN_BT)
1694 /* Don't lose the information for resolving neutrals! The
1695 cached states could have been cached before their
1696 next_for_neutral member was computed. If we are on our way
1697 forward, we can simply take the info from the previous
1698 state. */
1699 if (bidi_it->scan_dir == 1
1700 && bidi_it->next_for_neutral.type == UNKNOWN_BT)
1701 bidi_it->next_for_neutral = next_for_neutral;
1703 /* If resolved_level is -1, it means this state was cached
1704 before it was completely resolved, so we cannot return
1705 it. */
1706 if (bidi_it->resolved_level != -1)
1707 return bidi_it->resolved_level;
1709 if (bidi_it->scan_dir == -1)
1710 /* If we are going backwards, the iterator state is already cached
1711 from previous scans, and should be fully resolved. */
1712 abort ();
1714 if (type == UNKNOWN_BT)
1715 type = bidi_type_of_next_char (bidi_it);
1717 if (type == NEUTRAL_B)
1718 return bidi_it->resolved_level;
1720 level = bidi_it->level_stack[bidi_it->stack_idx].level;
1721 if ((bidi_get_category (type) == NEUTRAL /* && type != NEUTRAL_B */)
1722 || (type == WEAK_BN && prev_level == level))
1724 if (bidi_it->next_for_neutral.type == UNKNOWN_BT)
1725 abort ();
1727 /* If the cached state shows a neutral character, it was not
1728 resolved by bidi_resolve_neutral, so do it now. */
1729 type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
1730 bidi_it->next_for_neutral.type,
1731 level);
1734 if (!(type == STRONG_R
1735 || type == STRONG_L
1736 || type == WEAK_BN
1737 || type == WEAK_EN
1738 || type == WEAK_AN))
1739 abort ();
1740 bidi_it->type = type;
1741 bidi_check_type (bidi_it->type);
1743 /* For L1 below, we need to know, for each WS character, whether
1744 it belongs to a sequence of WS characters preceeding a newline
1745 or a TAB or a paragraph separator. */
1746 if (bidi_it->orig_type == NEUTRAL_WS
1747 && bidi_it->next_for_ws.type == UNKNOWN_BT)
1749 int ch;
1750 int clen = bidi_it->ch_len;
1751 EMACS_INT bpos = bidi_it->bytepos;
1752 EMACS_INT cpos = bidi_it->charpos;
1753 bidi_type_t chtype;
1755 do {
1756 /*_fetch_multibyte_char_len = 1;*/
1757 ch = bpos + clen >= ZV_BYTE ? BIDI_EOB : FETCH_CHAR (bpos + clen);
1758 bpos += clen;
1759 cpos++;
1760 clen = (ch == BIDI_EOB ? 1 : CHAR_BYTES (ch));
1761 if (ch == '\n' || ch == BIDI_EOB /* || ch == LINESEP_CHAR */)
1762 chtype = NEUTRAL_B;
1763 else
1764 chtype = bidi_get_type (ch, NEUTRAL_DIR);
1765 } while (chtype == NEUTRAL_WS || chtype == WEAK_BN
1766 || bidi_explicit_dir_char (ch)); /* L1/Retaining */
1767 bidi_it->next_for_ws.type = chtype;
1768 bidi_check_type (bidi_it->next_for_ws.type);
1769 bidi_it->next_for_ws.charpos = cpos;
1770 bidi_it->next_for_ws.bytepos = bpos;
1773 /* Resolve implicit levels, with a twist: PDFs get the embedding
1774 level of the enbedding they terminate. See below for the
1775 reason. */
1776 if (bidi_it->orig_type == PDF
1777 /* Don't do this if this formatting code didn't change the
1778 embedding level due to invalid or empty embeddings. */
1779 && prev_level != level)
1781 /* Don't look in UAX#9 for the reason for this: it's our own
1782 private quirk. The reason is that we want the formatting
1783 codes to be delivered so that they bracket the text of their
1784 embedding. For example, given the text
1786 {RLO}teST{PDF}
1788 we want it to be displayed as
1790 {RLO}STet{PDF}
1792 not as
1794 STet{RLO}{PDF}
1796 which will result because we bump up the embedding level as
1797 soon as we see the RLO and pop it as soon as we see the PDF,
1798 so RLO itself has the same embedding level as "teST", and
1799 thus would be normally delivered last, just before the PDF.
1800 The switch below fiddles with the level of PDF so that this
1801 ugly side effect does not happen.
1803 (This is, of course, only important if the formatting codes
1804 are actually displayed, but Emacs does need to display them
1805 if the user wants to.) */
1806 level = prev_level;
1808 else if (bidi_it->orig_type == NEUTRAL_B /* L1 */
1809 || bidi_it->orig_type == NEUTRAL_S
1810 || bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB
1811 /* || bidi_it->ch == LINESEP_CHAR */
1812 || (bidi_it->orig_type == NEUTRAL_WS
1813 && (bidi_it->next_for_ws.type == NEUTRAL_B
1814 || bidi_it->next_for_ws.type == NEUTRAL_S)))
1815 level = bidi_it->level_stack[0].level;
1816 else if ((level & 1) == 0) /* I1 */
1818 if (type == STRONG_R)
1819 level++;
1820 else if (type == WEAK_EN || type == WEAK_AN)
1821 level += 2;
1823 else /* I2 */
1825 if (type == STRONG_L || type == WEAK_EN || type == WEAK_AN)
1826 level++;
1829 bidi_it->resolved_level = level;
1830 return level;
1833 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
1834 non-zero, we are at the end of a level, and we need to prepare to
1835 resume the scan of the lower level.
1837 If this level's other edge is cached, we simply jump to it, filling
1838 the iterator structure with the iterator state on the other edge.
1839 Otherwise, we walk the buffer until we come back to the same level
1840 as LEVEL.
1842 Note: we are not talking here about a ``level run'' in the UAX#9
1843 sense of the term, but rather about a ``level'' which includes
1844 all the levels higher than it. In other words, given the levels
1845 like this:
1847 11111112222222333333334443343222222111111112223322111
1848 A B C
1850 and assuming we are at point A scanning left to right, this
1851 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
1852 at point B. */
1853 static void
1854 bidi_find_other_level_edge (struct bidi_it *bidi_it, int level, int end_flag)
1856 int dir = end_flag ? -bidi_it->scan_dir : bidi_it->scan_dir;
1857 int idx;
1859 /* Try the cache first. */
1860 if ((idx = bidi_cache_find_level_change (level, dir, end_flag)) >= 0)
1861 bidi_cache_fetch_state (idx, bidi_it);
1862 else
1864 int new_level;
1866 if (end_flag)
1867 abort (); /* if we are at end of level, its edges must be cached */
1869 bidi_cache_iterator_state (bidi_it, 1);
1870 do {
1871 new_level = bidi_level_of_next_char (bidi_it);
1872 bidi_cache_iterator_state (bidi_it, 1);
1873 } while (new_level >= level);
1877 void
1878 bidi_get_next_char_visually (struct bidi_it *bidi_it)
1880 int old_level, new_level, next_level;
1881 struct bidi_it sentinel;
1883 if (bidi_it->scan_dir == 0)
1885 bidi_it->scan_dir = 1; /* default to logical order */
1888 /* If we just passed a newline, initialize for the next line. */
1889 if (!bidi_it->first_elt && bidi_it->orig_type == NEUTRAL_B)
1890 bidi_line_init (bidi_it);
1892 /* Prepare the sentinel iterator state. */
1893 if (bidi_cache_idx == 0)
1895 bidi_copy_it (&sentinel, bidi_it);
1896 if (bidi_it->first_elt)
1898 sentinel.charpos--; /* cached charpos needs to be monotonic */
1899 sentinel.bytepos--;
1900 sentinel.ch = '\n'; /* doesn't matter, but why not? */
1901 sentinel.ch_len = 1;
1905 old_level = bidi_it->resolved_level;
1906 new_level = bidi_level_of_next_char (bidi_it);
1908 /* Reordering of resolved levels (clause L2) is implemented by
1909 jumping to the other edge of the level and flipping direction of
1910 scanning the text whenever we find a level change. */
1911 if (new_level != old_level)
1913 int ascending = new_level > old_level;
1914 int level_to_search = ascending ? old_level + 1 : old_level;
1915 int incr = ascending ? 1 : -1;
1916 int expected_next_level = old_level + incr;
1918 /* If we don't have anything cached yet, we need to cache the
1919 sentinel state, since we'll need it to record where to jump
1920 when the last non-base level is exhausted. */
1921 if (bidi_cache_idx == 0)
1922 bidi_cache_iterator_state (&sentinel, 1);
1923 /* Jump (or walk) to the other edge of this level. */
1924 bidi_find_other_level_edge (bidi_it, level_to_search, !ascending);
1925 /* Switch scan direction and peek at the next character in the
1926 new direction. */
1927 bidi_it->scan_dir = -bidi_it->scan_dir;
1929 /* The following loop handles the case where the resolved level
1930 jumps by more than one. This is typical for numbers inside a
1931 run of text with left-to-right embedding direction, but can
1932 also happen in other situations. In those cases the decision
1933 where to continue after a level change, and in what direction,
1934 is tricky. For example, given a text like below:
1936 abcdefgh
1937 11336622
1939 (where the numbers below the text show the resolved levels),
1940 the result of reordering according to UAX#9 should be this:
1942 efdcghba
1944 This is implemented by the loop below which flips direction
1945 and jumps to the other edge of the level each time it finds
1946 the new level not to be the expected one. The expected level
1947 is always one more or one less than the previous one. */
1948 next_level = bidi_peek_at_next_level (bidi_it);
1949 while (next_level != expected_next_level)
1951 expected_next_level += incr;
1952 level_to_search += incr;
1953 bidi_find_other_level_edge (bidi_it, level_to_search, !ascending);
1954 bidi_it->scan_dir = -bidi_it->scan_dir;
1955 next_level = bidi_peek_at_next_level (bidi_it);
1958 /* Finally, deliver the next character in the new direction. */
1959 next_level = bidi_level_of_next_char (bidi_it);
1962 /* Take note when we have just processed the newline that precedes
1963 the end of the paragraph. The next time we are about to be
1964 called, set_iterator_to_next will automatically reinit the
1965 paragraph direction, if needed. We do this at the newline before
1966 the paragraph separator, because the next character might not be
1967 the first character of the next paragraph, due to the bidi
1968 reordering, whereas we _must_ know the paragraph base direction
1969 _before_ we process the paragraph's text, since the base
1970 direction affects the reordering. */
1971 if (bidi_it->scan_dir == 1
1972 && bidi_it->orig_type == NEUTRAL_B
1973 && bidi_it->bytepos < ZV_BYTE)
1975 EMACS_INT sep_len =
1976 bidi_at_paragraph_end (bidi_it->charpos + 1,
1977 bidi_it->bytepos + bidi_it->ch_len);
1978 if (sep_len >= 0)
1980 bidi_it->new_paragraph = 1;
1981 /* Record the buffer position of the last character of the
1982 paragraph separator. */
1983 bidi_it->separator_limit = bidi_it->charpos + 1 + sep_len;
1987 if (bidi_it->scan_dir == 1 && bidi_cache_idx)
1989 /* If we are at paragraph's base embedding level and beyond the
1990 last cached position, the cache's job is done and we can
1991 discard it. */
1992 if (bidi_it->resolved_level == bidi_it->level_stack[0].level
1993 && bidi_it->charpos > bidi_cache[bidi_cache_idx - 1].charpos)
1994 bidi_cache_reset ();
1995 /* But as long as we are caching during forward scan, we must
1996 cache each state, or else the cache integrity will be
1997 compromised: it assumes cached states correspond to buffer
1998 positions 1:1. */
1999 else
2000 bidi_cache_iterator_state (bidi_it, 1);
2004 /* This is meant to be called from within the debugger, whenever you
2005 wish to examine the cache contents. */
2006 void
2007 bidi_dump_cached_states (void)
2009 int i;
2010 int ndigits = 1;
2012 if (bidi_cache_idx == 0)
2014 fprintf (stderr, "The cache is empty.\n");
2015 return;
2017 fprintf (stderr, "Total of %d state%s in cache:\n",
2018 bidi_cache_idx, bidi_cache_idx == 1 ? "" : "s");
2020 for (i = bidi_cache[bidi_cache_idx - 1].charpos; i > 0; i /= 10)
2021 ndigits++;
2022 fputs ("ch ", stderr);
2023 for (i = 0; i < bidi_cache_idx; i++)
2024 fprintf (stderr, "%*c", ndigits, bidi_cache[i].ch);
2025 fputs ("\n", stderr);
2026 fputs ("lvl ", stderr);
2027 for (i = 0; i < bidi_cache_idx; i++)
2028 fprintf (stderr, "%*d", ndigits, bidi_cache[i].resolved_level);
2029 fputs ("\n", stderr);
2030 fputs ("pos ", stderr);
2031 for (i = 0; i < bidi_cache_idx; i++)
2032 fprintf (stderr, "%*d", ndigits, bidi_cache[i].charpos);
2033 fputs ("\n", stderr);