1 /* Low-level bidirectional buffer-scanning functions for GNU Emacs.
2 Copyright (C) 2000, 2001, 2004, 2005, 2009 Free Software Foundation, Inc.
4 This file is part of GNU Emacs.
6 GNU Emacs is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Emacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 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; see the file COPYING. If not, write to
19 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
22 /* Written by Eli Zaretskii <eliz@gnu.org>.
24 A sequential implementation of the Unicode Bidirectional algorithm,
25 as per UAX#9, a part of the Unicode Standard.
27 Unlike the reference and most other implementations, this one is
28 designed to be called once for every character in the buffer.
30 The main entry point is bidi_get_next_char_visually. Each time it
31 is called, it finds the next character in the visual order, and
32 returns its information in a special structure. The caller is then
33 expected to process this character for display or any other
34 purposes, and call bidi_get_next_char_visually for the next
35 character. See the comments in bidi_get_next_char_visually for
36 more details about its algorithm that finds the next visual-order
37 character by resolving their levels on the fly.
39 If you want to understand the code, you will have to read it
40 together with the relevant portions of UAX#9. The comments include
41 references to UAX#9 rules, for that very reason.
43 A note about references to UAX#9 rules: if the reference says
44 something like "X9/Retaining", it means that you need to refer to
45 rule X9 and to its modifications decribed in the "Implementation
46 Notes" section of UAX#9, under "Retaining Format Codes". */
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
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. */
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
;
105 /* FIXME: This should come from the Unicode Database. */
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
} };
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. */
416 bidi_get_type (int ch
, bidi_dir_t override
)
418 bidi_type_t default_type
;
422 if (ch
< 0 || ch
> MAX_CHAR
)
425 default_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
427 if (override
== NEUTRAL_DIR
)
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. */
448 if (override
== L2R
) /* X6 */
450 else if (override
== R2L
)
453 abort (); /* can't happen: handled above */
459 bidi_check_type (bidi_type_t type
)
461 if (type
< UNKNOWN_BT
|| type
> NEUTRAL_ON
)
465 /* Given a bidi TYPE of a character, return its category. */
467 bidi_get_category (bidi_type_t type
)
481 case PDF
: /* ??? really?? */
500 /* Return the mirrored character of C, if any.
502 Note: The conditions in UAX#9 clause L4 must be tested by the
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
= strchr (mirrored_pairs
, c
);
514 size_t i
= p
- mirrored_pairs
;
517 return mirrored_pairs
[i
+ 1];
519 return mirrored_pairs
[i
- 1];
524 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
525 copies the part of the level stack that is actually in use. */
527 bidi_copy_it (struct bidi_it
*to
, struct bidi_it
*from
)
529 int save_first_elt
= to
->first_elt
;
532 /* Copy everything except the level stack. */
533 memcpy (to
, from
, ((int)&((struct bidi_it
*)0)->level_stack
[0]));
534 to
->first_elt
= save_first_elt
;
535 if (to
->first_elt
!= 0 && to
->first_elt
!= 1)
538 /* Copy the active part of the level stack. */
539 to
->level_stack
[0] = from
->level_stack
[0]; /* level zero is always in use */
540 for (i
= 1; i
<= from
->stack_idx
; i
++)
541 to
->level_stack
[i
] = from
->level_stack
[i
];
544 /* Caching the bidi iterator states. */
546 static struct bidi_it bidi_cache
[1000]; /* FIXME: make this dynamically allocated! */
547 static int bidi_cache_idx
;
548 static int bidi_cache_last_idx
;
551 bidi_cache_reset (void)
554 bidi_cache_last_idx
= -1;
558 bidi_cache_fetch_state (int idx
, struct bidi_it
*bidi_it
)
560 int current_scan_dir
= bidi_it
->scan_dir
;
562 if (idx
< 0 || idx
>= bidi_cache_idx
)
565 bidi_copy_it (bidi_it
, &bidi_cache
[idx
]);
566 bidi_it
->scan_dir
= current_scan_dir
;
567 bidi_cache_last_idx
= idx
;
570 /* Find a cached state with a given CHARPOS and resolved embedding
571 level less or equal to LEVEL. if LEVEL is -1, disregard the
572 resolved levels in cached states. DIR, if non-zero, means search
573 in that direction from the last cache hit. */
575 bidi_cache_search (int charpos
, int level
, int dir
)
581 if (charpos
< bidi_cache
[bidi_cache_last_idx
].charpos
)
583 else if (charpos
> bidi_cache
[bidi_cache_last_idx
].charpos
)
586 i_start
= bidi_cache_last_idx
;
590 i_start
= bidi_cache_idx
- 1;
595 /* Linear search for now; FIXME! */
596 for (i
= i_start
; i
>= 0; i
--)
597 if (bidi_cache
[i
].charpos
== charpos
598 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
603 for (i
= i_start
; i
< bidi_cache_idx
; i
++)
604 if (bidi_cache
[i
].charpos
== charpos
605 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
613 /* Find a cached state where the resolved level changes to a value
614 that is lower than LEVEL, and return its cache slot index. DIR is
615 the direction to search, starting with the last used cache slot.
616 BEFORE, if non-zero, means return the index of the slot that is
617 ``before'' the level change in the search direction. That is,
618 given the cached levels like this:
623 and assuming we are at the position cached at the slot marked with
624 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
625 index of slot B or A, depending whether BEFORE is, respectively,
628 bidi_cache_find_level_change (int level
, int dir
, int before
)
632 int i
= dir
? bidi_cache_last_idx
: bidi_cache_idx
- 1;
633 int incr
= before
? 1 : 0;
644 if (bidi_cache
[i
- incr
].resolved_level
>= 0
645 && bidi_cache
[i
- incr
].resolved_level
< level
)
652 while (i
< bidi_cache_idx
- incr
)
654 if (bidi_cache
[i
+ incr
].resolved_level
>= 0
655 && bidi_cache
[i
+ incr
].resolved_level
< level
)
666 bidi_cache_iterator_state (struct bidi_it
*bidi_it
, int resolved
)
670 /* We should never cache on backward scans. */
671 if (bidi_it
->scan_dir
== -1)
673 idx
= bidi_cache_search (bidi_it
->charpos
, -1, 1);
677 idx
= bidi_cache_idx
;
678 if (idx
> sizeof (bidi_cache
) / sizeof (bidi_cache
[0]) - 1)
680 bidi_copy_it (&bidi_cache
[idx
], bidi_it
);
682 bidi_cache
[idx
].resolved_level
= -1;
686 /* Copy only the members which could have changed, to avoid
687 costly copying of the entire struct. */
688 bidi_cache
[idx
].type
= bidi_it
->type
;
689 bidi_check_type (bidi_it
->type
);
690 bidi_cache
[idx
].type_after_w1
= bidi_it
->type_after_w1
;
691 bidi_check_type (bidi_it
->type_after_w1
);
693 bidi_cache
[idx
].resolved_level
= bidi_it
->resolved_level
;
695 bidi_cache
[idx
].resolved_level
= -1;
696 bidi_cache
[idx
].invalid_levels
= bidi_it
->invalid_levels
;
697 bidi_cache
[idx
].invalid_rl_levels
= bidi_it
->invalid_rl_levels
;
698 bidi_cache
[idx
].next_for_neutral
= bidi_it
->next_for_neutral
;
699 bidi_cache
[idx
].next_for_ws
= bidi_it
->next_for_ws
;
700 bidi_cache
[idx
].ignore_bn_limit
= bidi_it
->ignore_bn_limit
;
703 bidi_cache_last_idx
= idx
;
704 if (idx
>= bidi_cache_idx
)
705 bidi_cache_idx
= idx
+ 1;
708 static inline bidi_type_t
709 bidi_cache_find (int charpos
, int level
, struct bidi_it
*bidi_it
)
711 int i
= bidi_cache_search (charpos
, level
, bidi_it
->scan_dir
);
715 bidi_dir_t current_scan_dir
= bidi_it
->scan_dir
;
717 *bidi_it
= bidi_cache
[i
];
718 bidi_cache_last_idx
= i
;
719 /* Don't let scan direction from from the cached state override
720 the current scan direction. */
721 bidi_it
->scan_dir
= current_scan_dir
;
722 return bidi_it
->type
;
729 bidi_peek_at_next_level (struct bidi_it
*bidi_it
)
731 if (bidi_cache_idx
== 0 || bidi_cache_last_idx
== -1)
733 return bidi_cache
[bidi_cache_last_idx
+ bidi_it
->scan_dir
].resolved_level
;
736 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
737 Value is the non-negative length of the paragraph separator
738 following the buffer position, -1 if position is at the beginning
739 of a new paragraph, or -2 if position is neither at beginning nor
740 at end of a paragraph. */
742 bidi_at_paragraph_end (EMACS_INT charpos
, EMACS_INT bytepos
)
744 Lisp_Object sep_re
= Fbuffer_local_value (Qparagraph_separate
,
746 Lisp_Object start_re
= Fbuffer_local_value (Qparagraph_start
,
750 if (!STRINGP (sep_re
))
751 sep_re
= fallback_paragraph_separate_re
;
752 if (!STRINGP (start_re
))
753 start_re
= fallback_paragraph_start_re
;
755 val
= fast_looking_at (sep_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
);
758 if (fast_looking_at (start_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
) >= 0)
767 /* Determine the start-of-run (sor) directional type given the two
768 embedding levels on either side of the run boundary. Also, update
769 the saved info about previously seen characters, since that info is
770 generally valid for a single level run. */
772 bidi_set_sor_type (struct bidi_it
*bidi_it
, int level_before
, int level_after
)
774 int higher_level
= level_before
> level_after
? level_before
: level_after
;
776 /* The prev_was_pdf gork is required for when we have several PDFs
777 in a row. In that case, we want to compute the sor type for the
778 next level run only once: when we see the first PDF. That's
779 because the sor type depends only on the higher of the two levels
780 that we find on the two sides of the level boundary (see UAX#9,
781 clause X10), and so we don't need to know the final embedding
782 level to which we descend after processing all the PDFs. */
783 if (!bidi_it
->prev_was_pdf
|| level_before
< level_after
)
784 /* FIXME: should the default sor direction be user selectable? */
785 bidi_it
->sor
= (higher_level
& 1) != 0 ? R2L
: L2R
;
786 if (level_before
> level_after
)
787 bidi_it
->prev_was_pdf
= 1;
789 bidi_it
->prev
.type
= UNKNOWN_BT
;
790 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
791 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
792 bidi_it
->prev_for_neutral
.type
= bidi_it
->sor
== R2L
? STRONG_R
: STRONG_L
;
793 bidi_it
->prev_for_neutral
.charpos
= bidi_it
->charpos
;
794 bidi_it
->prev_for_neutral
.bytepos
= bidi_it
->bytepos
;
795 bidi_it
->next_for_neutral
.type
= bidi_it
->next_for_neutral
.type_after_w1
=
796 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
797 bidi_it
->ignore_bn_limit
= 0; /* meaning it's unknown */
801 bidi_line_init (struct bidi_it
*bidi_it
)
803 bidi_it
->scan_dir
= 1; /* FIXME: do we need to have control on this? */
804 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
805 bidi_it
->level_stack
[0].override
= NEUTRAL_DIR
; /* X1 */
806 bidi_it
->invalid_levels
= 0;
807 bidi_it
->invalid_rl_levels
= -1;
808 bidi_it
->next_en_pos
= -1;
809 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
810 bidi_set_sor_type (bidi_it
,
811 bidi_it
->paragraph_dir
== R2L
? 1 : 0,
812 bidi_it
->level_stack
[0].level
); /* X10 */
817 /* Find the beginning of this paragraph by looking back in the buffer.
818 Value is the byte position of the paragraph's beginning. */
820 bidi_find_paragraph_start (EMACS_INT pos
, EMACS_INT pos_byte
)
822 Lisp_Object re
= Fbuffer_local_value (Qparagraph_start
, Fcurrent_buffer ());
823 EMACS_INT limit
= ZV
, limit_byte
= ZV_BYTE
;
826 re
= fallback_paragraph_start_re
;
827 while (pos_byte
> BEGV_BYTE
828 && fast_looking_at (re
, pos
, pos_byte
, limit
, limit_byte
, Qnil
) < 0)
830 pos
= find_next_newline_no_quit (pos
- 1, -1);
831 pos_byte
= CHAR_TO_BYTE (pos
);
836 /* Determine the direction, a.k.a. base embedding level, of the
837 paragraph we are about to iterate through. If DIR is either L2R or
838 R2L, just use that. Otherwise, determine the paragraph direction
839 from the first strong character of the paragraph.
841 Note that this gives the paragraph separator the same direction as
842 the preceding paragraph, even though Emacs generally views the
843 separartor as not belonging to any paragraph. */
845 bidi_paragraph_init (bidi_dir_t dir
, struct bidi_it
*bidi_it
)
847 EMACS_INT bytepos
= bidi_it
->bytepos
;
849 /* We should never be called at EOB or before BEGV. */
850 if (bytepos
>= ZV_BYTE
|| bytepos
< BEGV_BYTE
)
855 bidi_it
->paragraph_dir
= L2R
;
856 bidi_it
->new_paragraph
= 0;
860 bidi_it
->paragraph_dir
= R2L
;
861 bidi_it
->new_paragraph
= 0;
863 else if (dir
== NEUTRAL_DIR
) /* P2 */
870 /* If we are inside a paragraph separator, we are just waiting
871 for the separator to be exhausted; use the previous paragraph
873 if (bidi_it
->charpos
< bidi_it
->separator_limit
)
876 /* If we are on a newline, get past it to where the next
877 paragraph might start. */
878 pos
= bidi_it
->charpos
;
879 if (FETCH_CHAR (bytepos
) == '\n')
885 /* We are either at the beginning of a paragraph or in the
886 middle of it. Find where this paragraph starts. */
887 bytepos
= bidi_find_paragraph_start (pos
, bytepos
);
889 /* We should always be at the beginning of a new line at this
891 if (!(bytepos
== BEGV_BYTE
|| FETCH_CHAR (bytepos
- 1) == '\n'))
894 bidi_it
->separator_limit
= -1;
895 bidi_it
->new_paragraph
= 0;
896 ch
= FETCH_CHAR (bytepos
);
897 ch_len
= CHAR_BYTES (ch
);
898 pos
= BYTE_TO_CHAR (bytepos
);
899 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
901 for (pos
++, bytepos
+= ch_len
;
902 /* NOTE: UAX#9 says to search only for L, AL, or R types of
903 characters, and ignore RLE, RLO, LRE, and LRO. However,
904 I'm not sure it makes sense to omit those 4; should try
905 with and without that to see the effect. */
906 (bidi_get_category (type
) != STRONG
)
907 || (bidi_ignore_explicit_marks_for_paragraph_level
908 && (type
== RLE
|| type
== RLO
909 || type
== LRE
|| type
== LRO
));
910 type
= bidi_get_type (ch
, NEUTRAL_DIR
))
912 if (type
== NEUTRAL_B
&& bidi_at_paragraph_end (pos
, bytepos
) >= -1)
914 FETCH_CHAR_ADVANCE (ch
, pos
, bytepos
);
916 if (type
== STRONG_R
|| type
== STRONG_AL
) /* P3 */
917 bidi_it
->paragraph_dir
= R2L
;
918 else if (type
== STRONG_L
)
919 bidi_it
->paragraph_dir
= L2R
;
924 /* Contrary to UAX#9 clause P3, we only default the paragraph
925 direction to L2R if we have no previous usable paragraph
927 if (bidi_it
->paragraph_dir
== NEUTRAL_DIR
)
928 bidi_it
->paragraph_dir
= L2R
; /* P3 and ``higher protocols'' */
929 if (bidi_it
->paragraph_dir
== R2L
)
930 bidi_it
->level_stack
[0].level
= 1;
932 bidi_it
->level_stack
[0].level
= 0;
934 bidi_line_init (bidi_it
);
937 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
940 bidi_set_paragraph_end (struct bidi_it
*bidi_it
)
942 bidi_it
->invalid_levels
= 0;
943 bidi_it
->invalid_rl_levels
= -1;
944 bidi_it
->stack_idx
= 0;
945 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
948 /* Initialize the bidi iterator from buffer position CHARPOS. */
950 bidi_init_it (EMACS_INT charpos
, EMACS_INT bytepos
, struct bidi_it
*bidi_it
)
952 if (! bidi_initialized
)
954 bidi_it
->charpos
= charpos
;
955 bidi_it
->bytepos
= bytepos
;
956 bidi_it
->first_elt
= 1;
957 bidi_set_paragraph_end (bidi_it
);
958 bidi_it
->new_paragraph
= 1;
959 bidi_it
->separator_limit
= -1;
960 bidi_it
->paragraph_dir
= NEUTRAL_DIR
;
961 bidi_it
->type
= NEUTRAL_B
;
962 bidi_it
->type_after_w1
= UNKNOWN_BT
;
963 bidi_it
->orig_type
= UNKNOWN_BT
;
964 bidi_it
->prev_was_pdf
= 0;
965 bidi_it
->prev
.type
= bidi_it
->prev
.type_after_w1
= UNKNOWN_BT
;
966 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
967 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
968 bidi_it
->next_for_neutral
.charpos
= -1;
969 bidi_it
->next_for_neutral
.type
=
970 bidi_it
->next_for_neutral
.type_after_w1
=
971 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
972 bidi_it
->prev_for_neutral
.charpos
= -1;
973 bidi_it
->prev_for_neutral
.type
=
974 bidi_it
->prev_for_neutral
.type_after_w1
=
975 bidi_it
->prev_for_neutral
.orig_type
= UNKNOWN_BT
;
976 bidi_it
->sor
= L2R
; /* FIXME: should it be user-selectable? */
979 /* Push the current embedding level and override status; reset the
980 current level to LEVEL and the current override status to OVERRIDE. */
982 bidi_push_embedding_level (struct bidi_it
*bidi_it
,
983 int level
, bidi_dir_t override
)
985 bidi_it
->stack_idx
++;
986 if (bidi_it
->stack_idx
>= BIDI_MAXLEVEL
)
988 bidi_it
->level_stack
[bidi_it
->stack_idx
].level
= level
;
989 bidi_it
->level_stack
[bidi_it
->stack_idx
].override
= override
;
992 /* Pop the embedding level and directional override status from the
993 stack, and return the new level. */
995 bidi_pop_embedding_level (struct bidi_it
*bidi_it
)
997 /* UAX#9 says to ignore invalid PDFs. */
998 if (bidi_it
->stack_idx
> 0)
999 bidi_it
->stack_idx
--;
1000 return bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1003 /* Record in SAVED_INFO the information about the current character. */
1005 bidi_remember_char (struct bidi_saved_info
*saved_info
,
1006 struct bidi_it
*bidi_it
)
1008 saved_info
->charpos
= bidi_it
->charpos
;
1009 saved_info
->bytepos
= bidi_it
->bytepos
;
1010 saved_info
->type
= bidi_it
->type
;
1011 bidi_check_type (bidi_it
->type
);
1012 saved_info
->type_after_w1
= bidi_it
->type_after_w1
;
1013 bidi_check_type (bidi_it
->type_after_w1
);
1014 saved_info
->orig_type
= bidi_it
->orig_type
;
1015 bidi_check_type (bidi_it
->orig_type
);
1018 /* Resolve the type of a neutral character according to the type of
1019 surrounding strong text and the current embedding level. */
1020 static inline bidi_type_t
1021 bidi_resolve_neutral_1 (bidi_type_t prev_type
, bidi_type_t next_type
, int lev
)
1023 /* N1: European and Arabic numbers are treated as though they were R. */
1024 if (next_type
== WEAK_EN
|| next_type
== WEAK_AN
)
1025 next_type
= STRONG_R
;
1026 if (prev_type
== WEAK_EN
|| prev_type
== WEAK_AN
)
1027 prev_type
= STRONG_R
;
1029 if (next_type
== prev_type
) /* N1 */
1031 else if ((lev
& 1) == 0) /* N2 */
1038 bidi_explicit_dir_char (int c
)
1040 /* FIXME: this should be replaced with a lookup table with suitable
1041 bits set, like standard C ctype macros do. */
1042 return (c
== LRE_CHAR
|| c
== LRO_CHAR
1043 || c
== RLE_CHAR
|| c
== RLO_CHAR
|| c
== PDF_CHAR
);
1046 /* A helper function for bidi_resolve_explicit. It advances to the
1047 next character in logical order and determines the new embedding
1048 level and directional override, but does not take into account
1049 empty embeddings. */
1051 bidi_resolve_explicit_1 (struct bidi_it
*bidi_it
)
1057 bidi_dir_t override
;
1059 if (bidi_it
->bytepos
< BEGV_BYTE
/* after reseat to BEGV? */
1060 || bidi_it
->first_elt
)
1062 bidi_it
->first_elt
= 0;
1063 if (bidi_it
->charpos
< BEGV
)
1064 bidi_it
->charpos
= BEGV
;
1065 bidi_it
->bytepos
= CHAR_TO_BYTE (bidi_it
->charpos
);
1067 else if (bidi_it
->bytepos
< ZV_BYTE
) /* don't move at ZV */
1070 if (bidi_it
->ch_len
== 0)
1072 bidi_it
->bytepos
+= bidi_it
->ch_len
;
1075 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
; /* X1 */
1076 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1077 new_level
= current_level
;
1079 /* in case it is a unibyte character (not yet implemented) */
1080 /* _fetch_multibyte_char_len = 1; */
1081 if (bidi_it
->bytepos
>= ZV_BYTE
)
1084 bidi_it
->ch_len
= 1;
1088 curchar
= FETCH_CHAR (bidi_it
->bytepos
);
1089 bidi_it
->ch_len
= CHAR_BYTES (curchar
);
1091 bidi_it
->ch
= curchar
;
1093 /* Don't apply directional override here, as all the types we handle
1094 below will not be affected by the override anyway, and we need
1095 the original type unaltered. The override will be applied in
1096 bidi_resolve_weak. */
1097 type
= bidi_get_type (curchar
, NEUTRAL_DIR
);
1098 bidi_it
->orig_type
= type
;
1099 bidi_check_type (bidi_it
->orig_type
);
1102 bidi_it
->prev_was_pdf
= 0;
1104 bidi_it
->type_after_w1
= UNKNOWN_BT
;
1110 bidi_it
->type_after_w1
= type
;
1111 bidi_check_type (bidi_it
->type_after_w1
);
1112 type
= WEAK_BN
; /* X9/Retaining */
1113 if (bidi_it
->ignore_bn_limit
<= 0)
1115 if (current_level
<= BIDI_MAXLEVEL
- 4)
1117 /* Compute the least odd embedding level greater than
1118 the current level. */
1119 new_level
= ((current_level
+ 1) & ~1) + 1;
1120 if (bidi_it
->type_after_w1
== RLE
)
1121 override
= NEUTRAL_DIR
;
1124 if (current_level
== BIDI_MAXLEVEL
- 4)
1125 bidi_it
->invalid_rl_levels
= 0;
1126 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1130 bidi_it
->invalid_levels
++;
1131 /* See the commentary about invalid_rl_levels below. */
1132 if (bidi_it
->invalid_rl_levels
< 0)
1133 bidi_it
->invalid_rl_levels
= 0;
1134 bidi_it
->invalid_rl_levels
++;
1137 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1138 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1143 bidi_it
->type_after_w1
= type
;
1144 bidi_check_type (bidi_it
->type_after_w1
);
1145 type
= WEAK_BN
; /* X9/Retaining */
1146 if (bidi_it
->ignore_bn_limit
<= 0)
1148 if (current_level
<= BIDI_MAXLEVEL
- 5)
1150 /* Compute the least even embedding level greater than
1151 the current level. */
1152 new_level
= ((current_level
+ 2) & ~1);
1153 if (bidi_it
->type_after_w1
== LRE
)
1154 override
= NEUTRAL_DIR
;
1157 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1161 bidi_it
->invalid_levels
++;
1162 /* invalid_rl_levels counts invalid levels encountered
1163 while the embedding level was already too high for
1164 LRE/LRO, but not for RLE/RLO. That is because
1165 there may be exactly one PDF which we should not
1166 ignore even though invalid_levels is non-zero.
1167 invalid_rl_levels helps to know what PDF is
1169 if (bidi_it
->invalid_rl_levels
>= 0)
1170 bidi_it
->invalid_rl_levels
++;
1173 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1174 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1178 bidi_it
->type_after_w1
= type
;
1179 bidi_check_type (bidi_it
->type_after_w1
);
1180 type
= WEAK_BN
; /* X9/Retaining */
1181 if (bidi_it
->ignore_bn_limit
<= 0)
1183 if (!bidi_it
->invalid_rl_levels
)
1185 new_level
= bidi_pop_embedding_level (bidi_it
);
1186 bidi_it
->invalid_rl_levels
= -1;
1187 if (bidi_it
->invalid_levels
)
1188 bidi_it
->invalid_levels
--;
1189 /* else nothing: UAX#9 says to ignore invalid PDFs */
1191 if (!bidi_it
->invalid_levels
)
1192 new_level
= bidi_pop_embedding_level (bidi_it
);
1195 bidi_it
->invalid_levels
--;
1196 bidi_it
->invalid_rl_levels
--;
1199 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1200 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1208 bidi_it
->type
= type
;
1209 bidi_check_type (bidi_it
->type
);
1214 /* Given an iterator state in BIDI_IT, advance one character position
1215 in the buffer to the next character (in the logical order), resolve
1216 any explicit embeddings and directional overrides, and return the
1217 embedding level of the character after resolving explicit
1218 directives and ignoring empty embeddings. */
1220 bidi_resolve_explicit (struct bidi_it
*bidi_it
)
1222 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1223 int new_level
= bidi_resolve_explicit_1 (bidi_it
);
1225 if (prev_level
< new_level
1226 && bidi_it
->type
== WEAK_BN
1227 && bidi_it
->ignore_bn_limit
== 0 /* only if not already known */
1228 && bidi_it
->ch
!= BIDI_EOB
/* not already at EOB */
1229 && bidi_explicit_dir_char (FETCH_CHAR (bidi_it
->bytepos
1230 + bidi_it
->ch_len
)))
1232 /* Avoid pushing and popping embedding levels if the level run
1233 is empty, as this breaks level runs where it shouldn't.
1234 UAX#9 removes all the explicit embedding and override codes,
1235 so empty embeddings disappear without a trace. We need to
1236 behave as if we did the same. */
1237 struct bidi_it saved_it
;
1238 int level
= prev_level
;
1240 bidi_copy_it (&saved_it
, bidi_it
);
1242 while (bidi_explicit_dir_char (FETCH_CHAR (bidi_it
->bytepos
1243 + bidi_it
->ch_len
)))
1245 level
= bidi_resolve_explicit_1 (bidi_it
);
1248 if (level
== prev_level
) /* empty embedding */
1249 saved_it
.ignore_bn_limit
= bidi_it
->charpos
+ 1;
1250 else /* this embedding is non-empty */
1251 saved_it
.ignore_bn_limit
= -1;
1253 bidi_copy_it (bidi_it
, &saved_it
);
1254 if (bidi_it
->ignore_bn_limit
> 0)
1256 /* We pushed a level, but we shouldn't have. Undo that. */
1257 if (!bidi_it
->invalid_rl_levels
)
1259 new_level
= bidi_pop_embedding_level (bidi_it
);
1260 bidi_it
->invalid_rl_levels
= -1;
1261 if (bidi_it
->invalid_levels
)
1262 bidi_it
->invalid_levels
--;
1264 if (!bidi_it
->invalid_levels
)
1265 new_level
= bidi_pop_embedding_level (bidi_it
);
1268 bidi_it
->invalid_levels
--;
1269 bidi_it
->invalid_rl_levels
--;
1274 if (bidi_it
->type
== NEUTRAL_B
) /* X8 */
1276 /* End of buffer does _not_ indicate a new paragraph is coming.
1277 Otherwise, each character inserted at EOB will be processed
1278 as starting a new paragraph. */
1279 if (bidi_it
->bytepos
< ZV_BYTE
)
1280 bidi_set_paragraph_end (bidi_it
);
1281 /* This is needed by bidi_resolve_weak below, and in L1. */
1282 bidi_it
->type_after_w1
= bidi_it
->type
;
1283 bidi_check_type (bidi_it
->type_after_w1
);
1289 /* Advance in the buffer, resolve weak types and return the type of
1290 the next character after weak type resolution. */
1292 bidi_resolve_weak (struct bidi_it
*bidi_it
)
1295 bidi_dir_t override
;
1296 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1297 int new_level
= bidi_resolve_explicit (bidi_it
);
1299 bidi_type_t type_of_next
;
1300 struct bidi_it saved_it
;
1302 type
= bidi_it
->type
;
1303 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1305 if (type
== UNKNOWN_BT
1313 if (new_level
!= prev_level
1314 || bidi_it
->type
== NEUTRAL_B
)
1316 /* We've got a new embedding level run, compute the directional
1317 type of sor and initialize per-run variables (UAX#9, clause
1319 bidi_set_sor_type (bidi_it
, prev_level
, new_level
);
1321 else if (type
== NEUTRAL_S
|| type
== NEUTRAL_WS
1322 || type
== WEAK_BN
|| type
== STRONG_AL
)
1323 bidi_it
->type_after_w1
= type
; /* needed in L1 */
1324 bidi_check_type (bidi_it
->type_after_w1
);
1326 /* Level and directional override status are already recorded in
1327 bidi_it, and do not need any change; see X6. */
1328 if (override
== R2L
) /* X6 */
1330 else if (override
== L2R
)
1332 else if (type
== STRONG_AL
)
1333 type
= STRONG_R
; /* W3 */
1334 else if (type
== WEAK_NSM
) /* W1 */
1336 /* Note that we don't need to consider the case where the prev
1337 character has its type overridden by an RLO or LRO: such
1338 characters are outside the current level run, and thus not
1339 relevant to this NSM. Thus, NSM gets the orig_type of the
1340 previous character. */
1341 if (bidi_it
->prev
.type
!= UNKNOWN_BT
)
1342 type
= bidi_it
->prev
.orig_type
;
1343 else if (bidi_it
->sor
== R2L
)
1345 else if (bidi_it
->sor
== L2R
)
1347 else /* shouldn't happen! */
1349 if (type
== WEAK_EN
/* W2 after W1 */
1350 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1353 else if (type
== WEAK_EN
/* W2 */
1354 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1356 else if ((type
== WEAK_ES
1357 && (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W4 */
1358 && (bidi_it
->prev
.orig_type
== WEAK_EN
1359 || bidi_it
->prev
.orig_type
== WEAK_NSM
))) /* aft W1 */
1361 && ((bidi_it
->prev
.type_after_w1
== WEAK_EN
1362 && (bidi_it
->prev
.orig_type
== WEAK_EN
/* W4 */
1363 || bidi_it
->prev
.orig_type
== WEAK_NSM
)) /* a/W1 */
1364 || bidi_it
->prev
.type_after_w1
== WEAK_AN
))) /* W4 */
1367 bidi_it
->bytepos
+ bidi_it
->ch_len
>= ZV_BYTE
1368 ? BIDI_EOB
: FETCH_CHAR (bidi_it
->bytepos
+ bidi_it
->ch_len
);
1369 type_of_next
= bidi_get_type (next_char
, override
);
1371 if (type_of_next
== WEAK_BN
1372 || bidi_explicit_dir_char (next_char
))
1374 bidi_copy_it (&saved_it
, bidi_it
);
1375 while (bidi_resolve_explicit (bidi_it
) == new_level
1376 && bidi_it
->type
== WEAK_BN
)
1378 type_of_next
= bidi_it
->type
;
1379 bidi_copy_it (bidi_it
, &saved_it
);
1382 /* If the next character is EN, but the last strong-type
1383 character is AL, that next EN will be changed to AN when we
1384 process it in W2 above. So in that case, this ES should not
1385 be changed into EN. */
1387 && type_of_next
== WEAK_EN
1388 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1390 else if (type
== WEAK_CS
)
1392 if (bidi_it
->prev
.type_after_w1
== WEAK_AN
1393 && (type_of_next
== WEAK_AN
1394 /* If the next character is EN, but the last
1395 strong-type character is AL, EN will be later
1396 changed to AN when we process it in W2 above. So
1397 in that case, this ES should not be changed into
1399 || (type_of_next
== WEAK_EN
1400 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)))
1402 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
1403 && type_of_next
== WEAK_EN
1404 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1408 else if (type
== WEAK_ET
/* W5: ET with EN before or after it */
1409 || type
== WEAK_BN
) /* W5/Retaining */
1411 if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* ET/BN with EN before it */
1412 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1414 /* W5: ET with EN after it. */
1417 EMACS_INT en_pos
= bidi_it
->charpos
+ 1;
1420 bidi_it
->bytepos
+ bidi_it
->ch_len
>= ZV_BYTE
1421 ? BIDI_EOB
: FETCH_CHAR (bidi_it
->bytepos
+ bidi_it
->ch_len
);
1422 type_of_next
= bidi_get_type (next_char
, override
);
1424 if (type_of_next
== WEAK_ET
1425 || type_of_next
== WEAK_BN
1426 || bidi_explicit_dir_char (next_char
))
1428 bidi_copy_it (&saved_it
, bidi_it
);
1429 while (bidi_resolve_explicit (bidi_it
) == new_level
1430 && (bidi_it
->type
== WEAK_BN
|| bidi_it
->type
== WEAK_ET
))
1432 type_of_next
= bidi_it
->type
;
1433 en_pos
= bidi_it
->charpos
;
1434 bidi_copy_it (bidi_it
, &saved_it
);
1436 if (type_of_next
== WEAK_EN
)
1438 /* If the last strong character is AL, the EN we've
1439 found will become AN when we get to it (W2). */
1440 if (bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1443 /* Remember this EN position, to speed up processing
1445 bidi_it
->next_en_pos
= en_pos
;
1447 else if (type
== WEAK_BN
)
1448 type
= NEUTRAL_ON
; /* W6/Retaining */
1453 if (type
== WEAK_ES
|| type
== WEAK_ET
|| type
== WEAK_CS
/* W6 */
1455 && (bidi_it
->prev
.type_after_w1
== WEAK_CS
/* W6/Retaining */
1456 || bidi_it
->prev
.type_after_w1
== WEAK_ES
1457 || bidi_it
->prev
.type_after_w1
== WEAK_ET
)))
1460 /* Store the type we've got so far, before we clobber it with strong
1461 types in W7 and while resolving neutral types. But leave alone
1462 the original types that were recorded above, because we will need
1463 them for the L1 clause. */
1464 if (bidi_it
->type_after_w1
== UNKNOWN_BT
)
1465 bidi_it
->type_after_w1
= type
;
1466 bidi_check_type (bidi_it
->type_after_w1
);
1468 if (type
== WEAK_EN
) /* W7 */
1470 if ((bidi_it
->last_strong
.type_after_w1
== STRONG_L
)
1471 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
&& bidi_it
->sor
== L2R
))
1475 bidi_it
->type
= type
;
1476 bidi_check_type (bidi_it
->type
);
1481 bidi_resolve_neutral (struct bidi_it
*bidi_it
)
1483 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1484 bidi_type_t type
= bidi_resolve_weak (bidi_it
);
1485 int current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1487 if (!(type
== STRONG_R
1492 || type
== NEUTRAL_B
1493 || type
== NEUTRAL_S
1494 || type
== NEUTRAL_WS
1495 || type
== NEUTRAL_ON
))
1498 if (bidi_get_category (type
) == NEUTRAL
1499 || (type
== WEAK_BN
&& prev_level
== current_level
))
1501 if (bidi_it
->next_for_neutral
.type
!= UNKNOWN_BT
)
1502 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1503 bidi_it
->next_for_neutral
.type
,
1507 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1508 the assumption of batch-style processing; see clauses W4,
1509 W5, and especially N1, which require to look far forward
1510 (as well as back) in the buffer. May the fleas of a
1511 thousand camels infest the armpits of those who design
1512 supposedly general-purpose algorithms by looking at their
1513 own implementations, and fail to consider other possible
1515 struct bidi_it saved_it
;
1516 bidi_type_t next_type
;
1518 if (bidi_it
->scan_dir
== -1)
1521 bidi_copy_it (&saved_it
, bidi_it
);
1522 /* Scan the text forward until we find the first non-neutral
1523 character, and then use that to resolve the neutral we
1524 are dealing with now. We also cache the scanned iterator
1525 states, to salvage some of the effort later. */
1526 bidi_cache_iterator_state (bidi_it
, 0);
1528 /* Record the info about the previous character, so that
1529 it will be cached below with this state. */
1530 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1531 && bidi_it
->type
!= WEAK_BN
)
1532 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1533 type
= bidi_resolve_weak (bidi_it
);
1534 /* Paragraph separators have their levels fully resolved
1535 at this point, so cache them as resolved. */
1536 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
);
1537 /* FIXME: implement L1 here, by testing for a newline and
1538 resetting the level for any sequence of whitespace
1539 characters adjacent to it. */
1540 } while (!(type
== NEUTRAL_B
1542 && bidi_get_category (type
) != NEUTRAL
)
1543 /* This is all per level run, so stop when we
1544 reach the end of this level run. */
1545 || bidi_it
->level_stack
[bidi_it
->stack_idx
].level
!=
1548 bidi_remember_char (&saved_it
.next_for_neutral
, bidi_it
);
1559 /* N1: ``European and Arabic numbers are treated as
1560 though they were R.'' */
1561 next_type
= STRONG_R
;
1562 saved_it
.next_for_neutral
.type
= STRONG_R
;
1565 if (!bidi_explicit_dir_char (bidi_it
->ch
))
1566 abort (); /* can't happen: BNs are skipped */
1569 /* Marched all the way to the end of this level run.
1570 We need to use the eor type, whose information is
1571 stored by bidi_set_sor_type in the prev_for_neutral
1573 if (saved_it
.type
!= WEAK_BN
1574 || bidi_get_category (bidi_it
->prev
.type_after_w1
) == NEUTRAL
)
1576 next_type
= bidi_it
->prev_for_neutral
.type
;
1577 saved_it
.next_for_neutral
.type
= next_type
;
1578 bidi_check_type (next_type
);
1582 /* This is a BN which does not adjoin neutrals.
1583 Leave its type alone. */
1584 bidi_copy_it (bidi_it
, &saved_it
);
1585 return bidi_it
->type
;
1591 type
= bidi_resolve_neutral_1 (saved_it
.prev_for_neutral
.type
,
1592 next_type
, current_level
);
1593 saved_it
.type
= type
;
1594 bidi_check_type (type
);
1595 bidi_copy_it (bidi_it
, &saved_it
);
1601 /* Given an iterator state in BIDI_IT, advance one character position
1602 in the buffer to the next character (in the logical order), resolve
1603 the bidi type of that next character, and return that type. */
1605 bidi_type_of_next_char (struct bidi_it
*bidi_it
)
1609 /* This should always be called during a forward scan. */
1610 if (bidi_it
->scan_dir
!= 1)
1613 /* Reset the limit until which to ignore BNs if we step out of the
1614 area where we found only empty levels. */
1615 if ((bidi_it
->ignore_bn_limit
> 0
1616 && bidi_it
->ignore_bn_limit
<= bidi_it
->charpos
)
1617 || (bidi_it
->ignore_bn_limit
== -1
1618 && !bidi_explicit_dir_char (bidi_it
->ch
)))
1619 bidi_it
->ignore_bn_limit
= 0;
1621 type
= bidi_resolve_neutral (bidi_it
);
1626 /* Given an iterator state BIDI_IT, advance one character position in
1627 the buffer to the next character (in the logical order), resolve
1628 the embedding and implicit levels of that next character, and
1629 return the resulting level. */
1631 bidi_level_of_next_char (struct bidi_it
*bidi_it
)
1634 int level
, prev_level
= -1;
1635 struct bidi_saved_info next_for_neutral
;
1637 if (bidi_it
->scan_dir
== 1)
1639 /* There's no sense in trying to advance if we hit end of text. */
1640 if (bidi_it
->ch
== BIDI_EOB
)
1641 return bidi_it
->resolved_level
;
1643 /* Record the info about the previous character. */
1644 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1645 && bidi_it
->type
!= WEAK_BN
)
1646 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1647 if (bidi_it
->type_after_w1
== STRONG_R
1648 || bidi_it
->type_after_w1
== STRONG_L
1649 || bidi_it
->type_after_w1
== STRONG_AL
)
1650 bidi_remember_char (&bidi_it
->last_strong
, bidi_it
);
1651 /* FIXME: it sounds like we don't need both prev and
1652 prev_for_neutral members, but I'm leaving them both for now. */
1653 if (bidi_it
->type
== STRONG_R
|| bidi_it
->type
== STRONG_L
1654 || bidi_it
->type
== WEAK_EN
|| bidi_it
->type
== WEAK_AN
)
1655 bidi_remember_char (&bidi_it
->prev_for_neutral
, bidi_it
);
1657 /* If we overstepped the characters used for resolving neutrals
1658 and whitespace, invalidate their info in the iterator. */
1659 if (bidi_it
->charpos
>= bidi_it
->next_for_neutral
.charpos
)
1660 bidi_it
->next_for_neutral
.type
= UNKNOWN_BT
;
1661 if (bidi_it
->next_en_pos
>= 0
1662 && bidi_it
->charpos
>= bidi_it
->next_en_pos
)
1663 bidi_it
->next_en_pos
= -1;
1664 if (bidi_it
->next_for_ws
.type
!= UNKNOWN_BT
1665 && bidi_it
->charpos
>= bidi_it
->next_for_ws
.charpos
)
1666 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
1668 /* This must be taken before we fill the iterator with the info
1669 about the next char. If we scan backwards, the iterator
1670 state must be already cached, so there's no need to know the
1671 embedding level of the previous character, since we will be
1672 returning to our caller shortly. */
1673 prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1675 next_for_neutral
= bidi_it
->next_for_neutral
;
1677 /* Perhaps it is already cached. */
1678 type
= bidi_cache_find (bidi_it
->charpos
+ bidi_it
->scan_dir
, -1, bidi_it
);
1679 if (type
!= UNKNOWN_BT
)
1681 /* Don't lose the information for resolving neutrals! The
1682 cached states could have been cached before their
1683 next_for_neutral member was computed. If we are on our way
1684 forward, we can simply take the info from the previous
1686 if (bidi_it
->scan_dir
== 1
1687 && bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1688 bidi_it
->next_for_neutral
= next_for_neutral
;
1690 /* If resolved_level is -1, it means this state was cached
1691 before it was completely resolved, so we cannot return
1693 if (bidi_it
->resolved_level
!= -1)
1694 return bidi_it
->resolved_level
;
1696 if (bidi_it
->scan_dir
== -1)
1697 /* If we are going backwards, the iterator state is already cached
1698 from previous scans, and should be fully resolved. */
1701 if (type
== UNKNOWN_BT
)
1702 type
= bidi_type_of_next_char (bidi_it
);
1704 if (type
== NEUTRAL_B
)
1705 return bidi_it
->resolved_level
;
1707 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1708 if ((bidi_get_category (type
) == NEUTRAL
/* && type != NEUTRAL_B */)
1709 || (type
== WEAK_BN
&& prev_level
== level
))
1711 if (bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1714 /* If the cached state shows a neutral character, it was not
1715 resolved by bidi_resolve_neutral, so do it now. */
1716 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1717 bidi_it
->next_for_neutral
.type
,
1721 if (!(type
== STRONG_R
1725 || type
== WEAK_AN
))
1727 bidi_it
->type
= type
;
1728 bidi_check_type (bidi_it
->type
);
1730 /* For L1 below, we need to know, for each WS character, whether
1731 it belongs to a sequence of WS characters preceeding a newline
1732 or a TAB or a paragraph separator. */
1733 if (bidi_it
->orig_type
== NEUTRAL_WS
1734 && bidi_it
->next_for_ws
.type
== UNKNOWN_BT
)
1737 int clen
= bidi_it
->ch_len
;
1738 EMACS_INT bpos
= bidi_it
->bytepos
;
1739 EMACS_INT cpos
= bidi_it
->charpos
;
1743 /*_fetch_multibyte_char_len = 1;*/
1744 ch
= bpos
+ clen
>= ZV_BYTE
? BIDI_EOB
: FETCH_CHAR (bpos
+ clen
);
1747 clen
= (ch
== BIDI_EOB
? 1 : CHAR_BYTES (ch
));
1748 if (ch
== '\n' || ch
== BIDI_EOB
/* || ch == LINESEP_CHAR */)
1751 chtype
= bidi_get_type (ch
, NEUTRAL_DIR
);
1752 } while (chtype
== NEUTRAL_WS
|| chtype
== WEAK_BN
1753 || bidi_explicit_dir_char (ch
)); /* L1/Retaining */
1754 bidi_it
->next_for_ws
.type
= chtype
;
1755 bidi_check_type (bidi_it
->next_for_ws
.type
);
1756 bidi_it
->next_for_ws
.charpos
= cpos
;
1757 bidi_it
->next_for_ws
.bytepos
= bpos
;
1760 /* Resolve implicit levels, with a twist: PDFs get the embedding
1761 level of the enbedding they terminate. See below for the
1763 if (bidi_it
->orig_type
== PDF
1764 /* Don't do this if this formatting code didn't change the
1765 embedding level due to invalid or empty embeddings. */
1766 && prev_level
!= level
)
1768 /* Don't look in UAX#9 for the reason for this: it's our own
1769 private quirk. The reason is that we want the formatting
1770 codes to be delivered so that they bracket the text of their
1771 embedding. For example, given the text
1775 we want it to be displayed as
1783 which will result because we bump up the embedding level as
1784 soon as we see the RLO and pop it as soon as we see the PDF,
1785 so RLO itself has the same embedding level as "teST", and
1786 thus would be normally delivered last, just before the PDF.
1787 The switch below fiddles with the level of PDF so that this
1788 ugly side effect does not happen.
1790 (This is, of course, only important if the formatting codes
1791 are actually displayed, but Emacs does need to display them
1792 if the user wants to.) */
1795 else if (bidi_it
->orig_type
== NEUTRAL_B
/* L1 */
1796 || bidi_it
->orig_type
== NEUTRAL_S
1797 || bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
1798 /* || bidi_it->ch == LINESEP_CHAR */
1799 || (bidi_it
->orig_type
== NEUTRAL_WS
1800 && (bidi_it
->next_for_ws
.type
== NEUTRAL_B
1801 || bidi_it
->next_for_ws
.type
== NEUTRAL_S
)))
1802 level
= bidi_it
->level_stack
[0].level
;
1803 else if ((level
& 1) == 0) /* I1 */
1805 if (type
== STRONG_R
)
1807 else if (type
== WEAK_EN
|| type
== WEAK_AN
)
1812 if (type
== STRONG_L
|| type
== WEAK_EN
|| type
== WEAK_AN
)
1816 bidi_it
->resolved_level
= level
;
1820 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
1821 non-zero, we are at the end of a level, and we need to prepare to
1822 resume the scan of the lower level.
1824 If this level's other edge is cached, we simply jump to it, filling
1825 the iterator structure with the iterator state on the other edge.
1826 Otherwise, we walk the buffer until we come back to the same level
1829 Note: we are not talking here about a ``level run'' in the UAX#9
1830 sense of the term, but rather about a ``level'' which includes
1831 all the levels higher than it. In other words, given the levels
1834 11111112222222333333334443343222222111111112223322111
1837 and assuming we are at point A scanning left to right, this
1838 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
1841 bidi_find_other_level_edge (struct bidi_it
*bidi_it
, int level
, int end_flag
)
1843 int dir
= end_flag
? -bidi_it
->scan_dir
: bidi_it
->scan_dir
;
1846 /* Try the cache first. */
1847 if ((idx
= bidi_cache_find_level_change (level
, dir
, end_flag
)) >= 0)
1848 bidi_cache_fetch_state (idx
, bidi_it
);
1854 abort (); /* if we are at end of level, its edges must be cached */
1856 bidi_cache_iterator_state (bidi_it
, 1);
1858 new_level
= bidi_level_of_next_char (bidi_it
);
1859 bidi_cache_iterator_state (bidi_it
, 1);
1860 } while (new_level
>= level
);
1865 bidi_get_next_char_visually (struct bidi_it
*bidi_it
)
1867 int old_level
, new_level
, next_level
;
1868 struct bidi_it sentinel
;
1870 if (bidi_it
->scan_dir
== 0)
1872 bidi_it
->scan_dir
= 1; /* default to logical order */
1875 /* If we just passed a newline, initialize for the next line. */
1876 if (!bidi_it
->first_elt
&& bidi_it
->orig_type
== NEUTRAL_B
)
1877 bidi_line_init (bidi_it
);
1879 /* Prepare the sentinel iterator state. */
1880 if (bidi_cache_idx
== 0)
1882 bidi_copy_it (&sentinel
, bidi_it
);
1883 if (bidi_it
->first_elt
)
1885 sentinel
.charpos
--; /* cached charpos needs to be monotonic */
1887 sentinel
.ch
= '\n'; /* doesn't matter, but why not? */
1888 sentinel
.ch_len
= 1;
1892 old_level
= bidi_it
->resolved_level
;
1893 new_level
= bidi_level_of_next_char (bidi_it
);
1894 if (bidi_it
->ch
== BIDI_EOB
)
1897 /* Reordering of resolved levels (clause L2) is implemented by
1898 jumping to the other edge of the level and flipping direction of
1899 scanning the buffer whenever we find a level change. */
1900 if (new_level
!= old_level
)
1902 int ascending
= new_level
> old_level
;
1903 int level_to_search
= ascending
? old_level
+ 1 : old_level
;
1904 int incr
= ascending
? 1 : -1;
1905 int expected_next_level
= old_level
+ incr
;
1907 /* If we don't have anything cached yet, we need to cache the
1908 sentinel state, since we'll need it to record where to jump
1909 when the last non-base level is exhausted. */
1910 if (bidi_cache_idx
== 0)
1911 bidi_cache_iterator_state (&sentinel
, 1);
1912 /* Jump (or walk) to the other edge of this level. */
1913 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
1914 /* Switch scan direction and peek at the next character in the
1916 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
1918 /* The following loop handles the case where the resolved level
1919 jumps by more than one. This is typical for numbers inside a
1920 run of text with left-to-right embedding direction, but can
1921 also happen in other situations. In those cases the decision
1922 where to continue after a level change, and in what direction,
1923 is tricky. For example, given a text like below:
1928 (where the numbers below the text show the resolved levels),
1929 the result of reordering according to UAX#9 should be this:
1933 This is implemented by the loop below which flips direction
1934 and jumps to the other edge of the level each time it finds
1935 the new level not to be the expected one. The expected level
1936 is always one more or one less than the previous one. */
1937 next_level
= bidi_peek_at_next_level (bidi_it
);
1938 while (next_level
!= expected_next_level
)
1940 expected_next_level
+= incr
;
1941 level_to_search
+= incr
;
1942 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
1943 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
1944 next_level
= bidi_peek_at_next_level (bidi_it
);
1947 /* Finally, deliver the next character in the new direction. */
1948 next_level
= bidi_level_of_next_char (bidi_it
);
1951 /* Take note when we have just processed the newline that precedes
1952 the end of the paragraph. The next time we are about to be
1953 called, set_iterator_to_next will automatically reinit the
1954 paragraph direction, if needed. We do this at the newline before
1955 the paragraph separator, because the next character might not be
1956 the first character of the next paragraph, due to the bidi
1958 if (bidi_it
->scan_dir
== 1
1959 && bidi_it
->orig_type
== NEUTRAL_B
1960 && bidi_it
->bytepos
< ZV_BYTE
)
1963 bidi_at_paragraph_end (bidi_it
->charpos
+ 1,
1964 bidi_it
->bytepos
+ bidi_it
->ch_len
);
1967 bidi_it
->new_paragraph
= 1;
1968 /* Record the buffer position of the last character of the
1969 paragraph separator. */
1970 bidi_it
->separator_limit
= bidi_it
->charpos
+ 1 + sep_len
;
1974 if (bidi_it
->scan_dir
== 1 && bidi_cache_idx
)
1976 /* If we are at paragraph's base embedding level and beyond the
1977 last cached position, the cache's job is done and we can
1979 if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
1980 && bidi_it
->charpos
> bidi_cache
[bidi_cache_idx
- 1].charpos
)
1981 bidi_cache_reset ();
1982 /* But as long as we are caching during forward scan, we must
1983 cache each state, or else the cache integrity will be
1984 compromised: it assumes cached states correspond to buffer
1987 bidi_cache_iterator_state (bidi_it
, 1);
1991 /* This is meant to be called from within the debugger, whenever you
1992 wish to examine the cache contents. */
1994 bidi_dump_cached_states (void)
1999 if (bidi_cache_idx
== 0)
2001 fprintf (stderr
, "The cache is empty.\n");
2004 fprintf (stderr
, "Total of %d state%s in cache:\n",
2005 bidi_cache_idx
, bidi_cache_idx
== 1 ? "" : "s");
2007 for (i
= bidi_cache
[bidi_cache_idx
- 1].charpos
; i
> 0; i
/= 10)
2009 fputs ("ch ", stderr
);
2010 for (i
= 0; i
< bidi_cache_idx
; i
++)
2011 fprintf (stderr
, "%*c", ndigits
, bidi_cache
[i
].ch
);
2012 fputs ("\n", stderr
);
2013 fputs ("lvl ", stderr
);
2014 for (i
= 0; i
< bidi_cache_idx
; i
++)
2015 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].resolved_level
);
2016 fputs ("\n", stderr
);
2017 fputs ("pos ", stderr
);
2018 for (i
= 0; i
< bidi_cache_idx
; i
++)
2019 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].charpos
);
2020 fputs ("\n", stderr
);