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 or
29 The main entry point is bidi_move_to_visually_next. Each time it
30 is called, it finds the next character in the visual order, and
31 returns its information in a special structure. The caller is then
32 expected to process this character for display or any other
33 purposes, and call bidi_move_to_visually_next for the next
34 character. See the comments in bidi_move_to_visually_next for more
35 details about its algorithm that finds the next visual-order
36 character by resolving their levels on the fly.
38 The two other entry points are bidi_paragraph_init and
39 bidi_mirror_char. The first determines the base direction of a
40 paragraph, while the second returns the mirrored version of its
43 If you want to understand the code, you will have to read it
44 together with the relevant portions of UAX#9. The comments include
45 references to UAX#9 rules, for that very reason.
47 A note about references to UAX#9 rules: if the reference says
48 something like "X9/Retaining", it means that you need to refer to
49 rule X9 and to its modifications decribed in the "Implementation
50 Notes" section of UAX#9, under "Retaining Format Codes". */
66 #include "character.h"
67 #include "dispextern.h"
69 static int bidi_initialized
= 0;
71 static Lisp_Object bidi_type_table
;
73 /* FIXME: Remove these when bidi_explicit_dir_char uses a lookup table. */
74 #define LRM_CHAR 0x200E
75 #define RLM_CHAR 0x200F
76 #define LRE_CHAR 0x202A
77 #define RLE_CHAR 0x202B
78 #define PDF_CHAR 0x202C
79 #define LRO_CHAR 0x202D
80 #define RLO_CHAR 0x202E
83 #define BIDI_BOB -2 /* FIXME: Is this needed? */
85 /* Local data structures. (Look in dispextern.h for the rest.) */
87 /* What we need to know about the current paragraph. */
88 struct bidi_paragraph_info
{
89 int start_bytepos
; /* byte position where it begins */
90 int end_bytepos
; /* byte position where it ends */
91 int embedding_level
; /* its basic embedding level */
92 bidi_dir_t base_dir
; /* its base direction */
95 /* Data type for describing the bidirectional character categories. */
103 int bidi_ignore_explicit_marks_for_paragraph_level
= 1;
105 static Lisp_Object paragraph_start_re
, paragraph_separate_re
;
106 static Lisp_Object Qparagraph_start
, Qparagraph_separate
;
111 /* FIXME: This should come from the Unicode Database. */
116 { { 0x0000, 0x0008, WEAK_BN
},
117 { 0x0009, 0x0000, NEUTRAL_S
},
118 { 0x000A, 0x0000, NEUTRAL_B
},
119 { 0x000B, 0x0000, NEUTRAL_S
},
120 { 0x000C, 0x0000, NEUTRAL_WS
},
121 { 0x000D, 0x0000, NEUTRAL_B
},
122 { 0x000E, 0x001B, WEAK_BN
},
123 { 0x001C, 0x001E, NEUTRAL_B
},
124 { 0x001F, 0x0000, NEUTRAL_S
},
125 { 0x0020, 0x0000, NEUTRAL_WS
},
126 { 0x0021, 0x0022, NEUTRAL_ON
},
127 { 0x0023, 0x0025, WEAK_ET
},
128 { 0x0026, 0x002A, NEUTRAL_ON
},
129 { 0x002B, 0x0000, WEAK_ES
},
130 { 0x002C, 0x0000, WEAK_CS
},
131 { 0x002D, 0x0000, WEAK_ES
},
132 { 0x002E, 0x002F, WEAK_CS
},
133 { 0x0030, 0x0039, WEAK_EN
},
134 { 0x003A, 0x0000, WEAK_CS
},
135 { 0x003B, 0x0040, NEUTRAL_ON
},
136 { 0x005B, 0x0060, NEUTRAL_ON
},
137 { 0x007B, 0x007E, NEUTRAL_ON
},
138 { 0x007F, 0x0084, WEAK_BN
},
139 { 0x0085, 0x0000, NEUTRAL_B
},
140 { 0x0086, 0x009F, WEAK_BN
},
141 { 0x00A0, 0x0000, WEAK_CS
},
142 { 0x00A1, 0x0000, NEUTRAL_ON
},
143 { 0x00A2, 0x00A5, WEAK_ET
},
144 { 0x00A6, 0x00A9, NEUTRAL_ON
},
145 { 0x00AB, 0x00AC, NEUTRAL_ON
},
146 { 0x00AD, 0x0000, WEAK_BN
},
147 { 0x00AE, 0x00Af, NEUTRAL_ON
},
148 { 0x00B0, 0x00B1, WEAK_ET
},
149 { 0x00B2, 0x00B3, WEAK_EN
},
150 { 0x00B4, 0x0000, NEUTRAL_ON
},
151 { 0x00B6, 0x00B8, NEUTRAL_ON
},
152 { 0x00B9, 0x0000, WEAK_EN
},
153 { 0x00BB, 0x00BF, NEUTRAL_ON
},
154 { 0x00D7, 0x0000, NEUTRAL_ON
},
155 { 0x00F7, 0x0000, NEUTRAL_ON
},
156 { 0x02B9, 0x02BA, NEUTRAL_ON
},
157 { 0x02C2, 0x02CF, NEUTRAL_ON
},
158 { 0x02D2, 0x02DF, NEUTRAL_ON
},
159 { 0x02E5, 0x02ED, NEUTRAL_ON
},
160 { 0x0300, 0x036F, WEAK_NSM
},
161 { 0x0374, 0x0375, NEUTRAL_ON
},
162 { 0x037E, 0x0385, NEUTRAL_ON
},
163 { 0x0387, 0x0000, NEUTRAL_ON
},
164 { 0x03F6, 0x0000, NEUTRAL_ON
},
165 { 0x0483, 0x0489, WEAK_NSM
},
166 { 0x058A, 0x0000, NEUTRAL_ON
},
167 { 0x0591, 0x05BD, WEAK_NSM
},
168 { 0x05BE, 0x0000, STRONG_R
},
169 { 0x05BF, 0x0000, WEAK_NSM
},
170 { 0x05C0, 0x0000, STRONG_R
},
171 { 0x05C1, 0x05C2, WEAK_NSM
},
172 { 0x05C3, 0x0000, STRONG_R
},
173 { 0x05C4, 0x05C5, WEAK_NSM
},
174 { 0x05C6, 0x0000, STRONG_R
},
175 { 0x05C7, 0x0000, WEAK_NSM
},
176 { 0x05D0, 0x05F4, STRONG_R
},
177 { 0x060C, 0x0000, WEAK_CS
},
178 { 0x061B, 0x064A, STRONG_AL
},
179 { 0x064B, 0x0655, WEAK_NSM
},
180 { 0x0660, 0x0669, WEAK_AN
},
181 { 0x066A, 0x0000, WEAK_ET
},
182 { 0x066B, 0x066C, WEAK_AN
},
183 { 0x066D, 0x066F, STRONG_AL
},
184 { 0x0670, 0x0000, WEAK_NSM
},
185 { 0x0671, 0x06D5, STRONG_AL
},
186 { 0x06D6, 0x06DC, WEAK_NSM
},
187 { 0x06DD, 0x0000, STRONG_AL
},
188 { 0x06DE, 0x06E4, WEAK_NSM
},
189 { 0x06E5, 0x06E6, STRONG_AL
},
190 { 0x06E7, 0x06E8, WEAK_NSM
},
191 { 0x06E9, 0x0000, NEUTRAL_ON
},
192 { 0x06EA, 0x06ED, WEAK_NSM
},
193 { 0x06F0, 0x06F9, WEAK_EN
},
194 { 0x06FA, 0x070D, STRONG_AL
},
195 { 0x070F, 0x0000, WEAK_BN
},
196 { 0x0710, 0x0000, STRONG_AL
},
197 { 0x0711, 0x0000, WEAK_NSM
},
198 { 0x0712, 0x072C, STRONG_AL
},
199 { 0x0730, 0x074A, WEAK_NSM
},
200 { 0x0780, 0x07A5, STRONG_AL
},
201 { 0x07A6, 0x07B0, WEAK_NSM
},
202 { 0x07B1, 0x0000, STRONG_AL
},
203 { 0x0901, 0x0902, WEAK_NSM
},
204 { 0x093C, 0x0000, WEAK_NSM
},
205 { 0x0941, 0x0948, WEAK_NSM
},
206 { 0x094D, 0x0000, WEAK_NSM
},
207 { 0x0951, 0x0954, WEAK_NSM
},
208 { 0x0962, 0x0963, WEAK_NSM
},
209 { 0x0981, 0x0000, WEAK_NSM
},
210 { 0x09BC, 0x0000, WEAK_NSM
},
211 { 0x09C1, 0x09C4, WEAK_NSM
},
212 { 0x09CD, 0x0000, WEAK_NSM
},
213 { 0x09E2, 0x09E3, WEAK_NSM
},
214 { 0x09F2, 0x09F3, WEAK_ET
},
215 { 0x0A02, 0x0000, WEAK_NSM
},
216 { 0x0A3C, 0x0000, WEAK_NSM
},
217 { 0x0A41, 0x0A4D, WEAK_NSM
},
218 { 0x0A70, 0x0A71, WEAK_NSM
},
219 { 0x0A81, 0x0A82, WEAK_NSM
},
220 { 0x0ABC, 0x0000, WEAK_NSM
},
221 { 0x0AC1, 0x0AC8, WEAK_NSM
},
222 { 0x0ACD, 0x0000, WEAK_NSM
},
223 { 0x0B01, 0x0000, WEAK_NSM
},
224 { 0x0B3C, 0x0000, WEAK_NSM
},
225 { 0x0B3F, 0x0000, WEAK_NSM
},
226 { 0x0B41, 0x0B43, WEAK_NSM
},
227 { 0x0B4D, 0x0B56, WEAK_NSM
},
228 { 0x0B82, 0x0000, WEAK_NSM
},
229 { 0x0BC0, 0x0000, WEAK_NSM
},
230 { 0x0BCD, 0x0000, WEAK_NSM
},
231 { 0x0C3E, 0x0C40, WEAK_NSM
},
232 { 0x0C46, 0x0C56, WEAK_NSM
},
233 { 0x0CBF, 0x0000, WEAK_NSM
},
234 { 0x0CC6, 0x0000, WEAK_NSM
},
235 { 0x0CCC, 0x0CCD, WEAK_NSM
},
236 { 0x0D41, 0x0D43, WEAK_NSM
},
237 { 0x0D4D, 0x0000, WEAK_NSM
},
238 { 0x0DCA, 0x0000, WEAK_NSM
},
239 { 0x0DD2, 0x0DD6, WEAK_NSM
},
240 { 0x0E31, 0x0000, WEAK_NSM
},
241 { 0x0E34, 0x0E3A, WEAK_NSM
},
242 { 0x0E3F, 0x0000, WEAK_ET
},
243 { 0x0E47, 0x0E4E, WEAK_NSM
},
244 { 0x0EB1, 0x0000, WEAK_NSM
},
245 { 0x0EB4, 0x0EBC, WEAK_NSM
},
246 { 0x0EC8, 0x0ECD, WEAK_NSM
},
247 { 0x0F18, 0x0F19, WEAK_NSM
},
248 { 0x0F35, 0x0000, WEAK_NSM
},
249 { 0x0F37, 0x0000, WEAK_NSM
},
250 { 0x0F39, 0x0000, WEAK_NSM
},
251 { 0x0F3A, 0x0F3D, NEUTRAL_ON
},
252 { 0x0F71, 0x0F7E, WEAK_NSM
},
253 { 0x0F80, 0x0F84, WEAK_NSM
},
254 { 0x0F86, 0x0F87, WEAK_NSM
},
255 { 0x0F90, 0x0FBC, WEAK_NSM
},
256 { 0x0FC6, 0x0000, WEAK_NSM
},
257 { 0x102D, 0x1030, WEAK_NSM
},
258 { 0x1032, 0x1037, WEAK_NSM
},
259 { 0x1039, 0x0000, WEAK_NSM
},
260 { 0x1058, 0x1059, WEAK_NSM
},
261 { 0x1680, 0x0000, NEUTRAL_WS
},
262 { 0x169B, 0x169C, NEUTRAL_ON
},
263 { 0x1712, 0x1714, WEAK_NSM
},
264 { 0x1732, 0x1734, WEAK_NSM
},
265 { 0x1752, 0x1753, WEAK_NSM
},
266 { 0x1772, 0x1773, WEAK_NSM
},
267 { 0x17B7, 0x17BD, WEAK_NSM
},
268 { 0x17C6, 0x0000, WEAK_NSM
},
269 { 0x17C9, 0x17D3, WEAK_NSM
},
270 { 0x17DB, 0x0000, WEAK_ET
},
271 { 0x1800, 0x180A, NEUTRAL_ON
},
272 { 0x180B, 0x180D, WEAK_NSM
},
273 { 0x180E, 0x0000, WEAK_BN
},
274 { 0x18A9, 0x0000, WEAK_NSM
},
275 { 0x1FBD, 0x0000, NEUTRAL_ON
},
276 { 0x1FBF, 0x1FC1, NEUTRAL_ON
},
277 { 0x1FCD, 0x1FCF, NEUTRAL_ON
},
278 { 0x1FDD, 0x1FDF, NEUTRAL_ON
},
279 { 0x1FED, 0x1FEF, NEUTRAL_ON
},
280 { 0x1FFD, 0x1FFE, NEUTRAL_ON
},
281 { 0x2000, 0x200A, NEUTRAL_WS
},
282 { 0x200B, 0x200D, WEAK_BN
},
283 { 0x200F, 0x0000, STRONG_R
},
284 { 0x2010, 0x2027, NEUTRAL_ON
},
285 { 0x2028, 0x0000, NEUTRAL_WS
},
286 { 0x2029, 0x0000, NEUTRAL_B
},
287 { 0x202A, 0x0000, LRE
},
288 { 0x202B, 0x0000, RLE
},
289 { 0x202C, 0x0000, PDF
},
290 { 0x202D, 0x0000, LRO
},
291 { 0x202E, 0x0000, RLO
},
292 { 0x202F, 0x0000, NEUTRAL_WS
},
293 { 0x2030, 0x2034, WEAK_ET
},
294 { 0x2035, 0x2057, NEUTRAL_ON
},
295 { 0x205F, 0x0000, NEUTRAL_WS
},
296 { 0x2060, 0x206F, WEAK_BN
},
297 { 0x2070, 0x0000, WEAK_EN
},
298 { 0x2074, 0x2079, WEAK_EN
},
299 { 0x207A, 0x207B, WEAK_ET
},
300 { 0x207C, 0x207E, NEUTRAL_ON
},
301 { 0x2080, 0x2089, WEAK_EN
},
302 { 0x208A, 0x208B, WEAK_ET
},
303 { 0x208C, 0x208E, NEUTRAL_ON
},
304 { 0x20A0, 0x20B1, WEAK_ET
},
305 { 0x20D0, 0x20EA, WEAK_NSM
},
306 { 0x2100, 0x2101, NEUTRAL_ON
},
307 { 0x2103, 0x2106, NEUTRAL_ON
},
308 { 0x2108, 0x2109, NEUTRAL_ON
},
309 { 0x2114, 0x0000, NEUTRAL_ON
},
310 { 0x2116, 0x2118, NEUTRAL_ON
},
311 { 0x211E, 0x2123, NEUTRAL_ON
},
312 { 0x2125, 0x0000, NEUTRAL_ON
},
313 { 0x2127, 0x0000, NEUTRAL_ON
},
314 { 0x2129, 0x0000, NEUTRAL_ON
},
315 { 0x212E, 0x0000, WEAK_ET
},
316 { 0x2132, 0x0000, NEUTRAL_ON
},
317 { 0x213A, 0x0000, NEUTRAL_ON
},
318 { 0x2140, 0x2144, NEUTRAL_ON
},
319 { 0x214A, 0x215F, NEUTRAL_ON
},
320 { 0x2190, 0x2211, NEUTRAL_ON
},
321 { 0x2212, 0x2213, WEAK_ET
},
322 { 0x2214, 0x2335, NEUTRAL_ON
},
323 { 0x237B, 0x2394, NEUTRAL_ON
},
324 { 0x2396, 0x244A, NEUTRAL_ON
},
325 { 0x2460, 0x249B, WEAK_EN
},
326 { 0x24EA, 0x0000, WEAK_EN
},
327 { 0x24EB, 0x2FFB, NEUTRAL_ON
},
328 { 0x3000, 0x0000, NEUTRAL_WS
},
329 { 0x3001, 0x3004, NEUTRAL_ON
},
330 { 0x3008, 0x3020, NEUTRAL_ON
},
331 { 0x302A, 0x302F, WEAK_NSM
},
332 { 0x3030, 0x0000, NEUTRAL_ON
},
333 { 0x3036, 0x3037, NEUTRAL_ON
},
334 { 0x303D, 0x303F, NEUTRAL_ON
},
335 { 0x3099, 0x309A, WEAK_NSM
},
336 { 0x309B, 0x309C, NEUTRAL_ON
},
337 { 0x30A0, 0x0000, NEUTRAL_ON
},
338 { 0x30FB, 0x0000, NEUTRAL_ON
},
339 { 0x3251, 0x325F, NEUTRAL_ON
},
340 { 0x32B1, 0x32BF, NEUTRAL_ON
},
341 { 0xA490, 0xA4C6, NEUTRAL_ON
},
342 { 0xFB1D, 0x0000, STRONG_R
},
343 { 0xFB1E, 0x0000, WEAK_NSM
},
344 { 0xFB1F, 0xFB28, STRONG_R
},
345 { 0xFB29, 0x0000, WEAK_ET
},
346 { 0xFB2A, 0xFB4F, STRONG_R
},
347 { 0xFB50, 0xFD3D, STRONG_AL
},
348 { 0xFD3E, 0xFD3F, NEUTRAL_ON
},
349 { 0xFD50, 0xFDFC, STRONG_AL
},
350 { 0xFE00, 0xFE23, WEAK_NSM
},
351 { 0xFE30, 0xFE4F, NEUTRAL_ON
},
352 { 0xFE50, 0x0000, WEAK_CS
},
353 { 0xFE51, 0x0000, NEUTRAL_ON
},
354 { 0xFE52, 0x0000, WEAK_CS
},
355 { 0xFE54, 0x0000, NEUTRAL_ON
},
356 { 0xFE55, 0x0000, WEAK_CS
},
357 { 0xFE56, 0xFE5E, NEUTRAL_ON
},
358 { 0xFE5F, 0x0000, WEAK_ET
},
359 { 0xFE60, 0xFE61, NEUTRAL_ON
},
360 { 0xFE62, 0xFE63, WEAK_ET
},
361 { 0xFE64, 0xFE68, NEUTRAL_ON
},
362 { 0xFE69, 0xFE6A, WEAK_ET
},
363 { 0xFE6B, 0x0000, NEUTRAL_ON
},
364 { 0xFE70, 0xFEFC, STRONG_AL
},
365 { 0xFEFF, 0x0000, WEAK_BN
},
366 { 0xFF01, 0xFF02, NEUTRAL_ON
},
367 { 0xFF03, 0xFF05, WEAK_ET
},
368 { 0xFF06, 0xFF0A, NEUTRAL_ON
},
369 { 0xFF0B, 0x0000, WEAK_ET
},
370 { 0xFF0C, 0x0000, WEAK_CS
},
371 { 0xFF0D, 0x0000, WEAK_ET
},
372 { 0xFF0E, 0x0000, WEAK_CS
},
373 { 0xFF0F, 0x0000, WEAK_ES
},
374 { 0xFF10, 0xFF19, WEAK_EN
},
375 { 0xFF1A, 0x0000, WEAK_CS
},
376 { 0xFF1B, 0xFF20, NEUTRAL_ON
},
377 { 0xFF3B, 0xFF40, NEUTRAL_ON
},
378 { 0xFF5B, 0xFF65, NEUTRAL_ON
},
379 { 0xFFE0, 0xFFE1, WEAK_ET
},
380 { 0xFFE2, 0xFFE4, NEUTRAL_ON
},
381 { 0xFFE5, 0xFFE6, WEAK_ET
},
382 { 0xFFE8, 0xFFEE, NEUTRAL_ON
},
383 { 0xFFF9, 0xFFFB, WEAK_BN
},
384 { 0xFFFC, 0xFFFD, NEUTRAL_ON
},
385 { 0x1D167, 0x1D169, WEAK_NSM
},
386 { 0x1D173, 0x1D17A, WEAK_BN
},
387 { 0x1D17B, 0x1D182, WEAK_NSM
},
388 { 0x1D185, 0x1D18B, WEAK_NSM
},
389 { 0x1D1AA, 0x1D1AD, WEAK_NSM
},
390 { 0x1D7CE, 0x1D7FF, WEAK_EN
},
391 { 0xE0001, 0xE007F, WEAK_BN
} };
394 bidi_type_table
= Fmake_char_table (Qnil
, make_number (STRONG_L
));
395 staticpro (&bidi_type_table
);
397 for (i
= 0; i
< sizeof bidi_type
/ sizeof bidi_type
[0]; i
++)
398 char_table_set_range (bidi_type_table
, bidi_type
[i
].from
,
399 bidi_type
[i
].to
? bidi_type
[i
].to
: bidi_type
[i
].from
,
400 make_number (bidi_type
[i
].type
));
402 Qparagraph_start
= intern ("paragraph-start");
403 staticpro (&Qparagraph_start
);
404 paragraph_start_re
= Fsymbol_value (Qparagraph_start
);
405 if (!STRINGP (paragraph_start_re
))
406 paragraph_start_re
= build_string ("\f\\|[ \t]*$");
407 staticpro (¶graph_start_re
);
408 Qparagraph_separate
= intern ("paragraph-separate");
409 staticpro (&Qparagraph_separate
);
410 paragraph_separate_re
= Fsymbol_value (Qparagraph_separate
);
411 if (!STRINGP (paragraph_separate_re
))
412 paragraph_separate_re
= build_string ("[ \t\f]*$");
413 staticpro (¶graph_separate_re
);
414 bidi_initialized
= 1;
417 /* Return the bidi type of a character CH, subject to the current
418 directional OVERRIDE. */
419 static INLINE bidi_type_t
420 bidi_get_type (int ch
, bidi_dir_t override
)
422 bidi_type_t default_type
;
426 if (ch
< 0 || ch
> MAX_CHAR
)
429 default_type
= (bidi_type_t
) XINT (CHAR_TABLE_REF (bidi_type_table
, ch
));
431 if (override
== NEUTRAL_DIR
)
434 switch (default_type
)
436 /* Although UAX#9 does not tell, it doesn't make sense to
437 override NEUTRAL_B and LRM/RLM characters. */
452 if (override
== L2R
) /* X6 */
454 else if (override
== R2L
)
457 abort (); /* can't happen: handled above */
463 bidi_check_type (bidi_type_t type
)
465 if (type
< UNKNOWN_BT
|| type
> NEUTRAL_ON
)
469 /* Given a bidi TYPE of a character, return its category. */
470 static INLINE bidi_category_t
471 bidi_get_category (bidi_type_t type
)
485 case PDF
: /* ??? really?? */
504 /* Return the mirrored character of C, if any.
506 Note: The conditions in UAX#9 clause L4 must be tested by the
508 /* FIXME: exceedingly temporary! Should consult the Unicode database
509 of character properties. */
511 bidi_mirror_char (int c
)
513 static const char mirrored_pairs
[] = "()<>[]{}";
514 const char *p
= c
> 0 && c
< 128 ? strchr (mirrored_pairs
, c
) : NULL
;
518 size_t i
= p
- mirrored_pairs
;
520 return mirrored_pairs
[(i
^ 1)];
525 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
526 copies the part of the level stack that is actually in use. */
528 bidi_copy_it (struct bidi_it
*to
, struct bidi_it
*from
)
532 /* Copy everything except the level stack and beyond. */
533 memcpy (to
, from
, ((size_t)&((struct bidi_it
*)0)->level_stack
[0]));
535 /* Copy the active part of the level stack. */
536 to
->level_stack
[0] = from
->level_stack
[0]; /* level zero is always in use */
537 for (i
= 1; i
<= from
->stack_idx
; i
++)
538 to
->level_stack
[i
] = from
->level_stack
[i
];
541 /* Caching the bidi iterator states. */
543 #define BIDI_CACHE_CHUNK 200
544 static struct bidi_it
*bidi_cache
;
545 static size_t bidi_cache_size
= 0;
546 static size_t elsz
= sizeof (struct bidi_it
);
547 static int bidi_cache_idx
; /* next unused cache slot */
548 static int bidi_cache_last_idx
; /* slot of last cache hit */
551 bidi_cache_reset (void)
554 bidi_cache_last_idx
= -1;
558 bidi_cache_shrink (void)
560 if (bidi_cache_size
> BIDI_CACHE_CHUNK
)
562 bidi_cache_size
= BIDI_CACHE_CHUNK
;
564 (struct bidi_it
*) xrealloc (bidi_cache
, bidi_cache_size
* elsz
);
570 bidi_cache_fetch_state (int idx
, struct bidi_it
*bidi_it
)
572 int current_scan_dir
= bidi_it
->scan_dir
;
574 if (idx
< 0 || idx
>= bidi_cache_idx
)
577 bidi_copy_it (bidi_it
, &bidi_cache
[idx
]);
578 bidi_it
->scan_dir
= current_scan_dir
;
579 bidi_cache_last_idx
= idx
;
582 /* Find a cached state with a given CHARPOS and resolved embedding
583 level less or equal to LEVEL. if LEVEL is -1, disregard the
584 resolved levels in cached states. DIR, if non-zero, means search
585 in that direction from the last cache hit. */
587 bidi_cache_search (int charpos
, int level
, int dir
)
593 if (charpos
< bidi_cache
[bidi_cache_last_idx
].charpos
)
595 else if (charpos
> bidi_cache
[bidi_cache_last_idx
].charpos
)
598 i_start
= bidi_cache_last_idx
;
602 i_start
= bidi_cache_idx
- 1;
607 /* Linear search for now; FIXME! */
608 for (i
= i_start
; i
>= 0; i
--)
609 if (bidi_cache
[i
].charpos
== charpos
610 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
615 for (i
= i_start
; i
< bidi_cache_idx
; i
++)
616 if (bidi_cache
[i
].charpos
== charpos
617 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
625 /* Find a cached state where the resolved level changes to a value
626 that is lower than LEVEL, and return its cache slot index. DIR is
627 the direction to search, starting with the last used cache slot.
628 BEFORE, if non-zero, means return the index of the slot that is
629 ``before'' the level change in the search direction. That is,
630 given the cached levels like this:
635 and assuming we are at the position cached at the slot marked with
636 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
637 index of slot B or A, depending whether BEFORE is, respectively,
640 bidi_cache_find_level_change (int level
, int dir
, int before
)
644 int i
= dir
? bidi_cache_last_idx
: bidi_cache_idx
- 1;
645 int incr
= before
? 1 : 0;
656 if (bidi_cache
[i
- incr
].resolved_level
>= 0
657 && bidi_cache
[i
- incr
].resolved_level
< level
)
664 while (i
< bidi_cache_idx
- incr
)
666 if (bidi_cache
[i
+ incr
].resolved_level
>= 0
667 && bidi_cache
[i
+ incr
].resolved_level
< level
)
678 bidi_cache_iterator_state (struct bidi_it
*bidi_it
, int resolved
)
682 /* We should never cache on backward scans. */
683 if (bidi_it
->scan_dir
== -1)
685 idx
= bidi_cache_search (bidi_it
->charpos
, -1, 1);
689 idx
= bidi_cache_idx
;
690 /* Enlarge the cache as needed. */
691 if (idx
>= bidi_cache_size
)
693 bidi_cache_size
+= BIDI_CACHE_CHUNK
;
695 (struct bidi_it
*) xrealloc (bidi_cache
, bidi_cache_size
* elsz
);
697 /* Character positions should correspond to cache positions 1:1.
698 If we are outside the range of cached positions, the cache is
699 useless and must be reset. */
701 (bidi_it
->charpos
> bidi_cache
[idx
- 1].charpos
+ 1
702 || bidi_it
->charpos
< bidi_cache
[0].charpos
))
707 bidi_copy_it (&bidi_cache
[idx
], bidi_it
);
709 bidi_cache
[idx
].resolved_level
= -1;
710 bidi_cache
[idx
].new_paragraph
= 0;
714 /* Copy only the members which could have changed, to avoid
715 costly copying of the entire struct. */
716 bidi_cache
[idx
].type
= bidi_it
->type
;
717 bidi_check_type (bidi_it
->type
);
718 bidi_cache
[idx
].type_after_w1
= bidi_it
->type_after_w1
;
719 bidi_check_type (bidi_it
->type_after_w1
);
721 bidi_cache
[idx
].resolved_level
= bidi_it
->resolved_level
;
723 bidi_cache
[idx
].resolved_level
= -1;
724 bidi_cache
[idx
].invalid_levels
= bidi_it
->invalid_levels
;
725 bidi_cache
[idx
].invalid_rl_levels
= bidi_it
->invalid_rl_levels
;
726 bidi_cache
[idx
].next_for_neutral
= bidi_it
->next_for_neutral
;
727 bidi_cache
[idx
].next_for_ws
= bidi_it
->next_for_ws
;
728 bidi_cache
[idx
].ignore_bn_limit
= bidi_it
->ignore_bn_limit
;
731 bidi_cache_last_idx
= idx
;
732 if (idx
>= bidi_cache_idx
)
733 bidi_cache_idx
= idx
+ 1;
736 static INLINE bidi_type_t
737 bidi_cache_find (int charpos
, int level
, struct bidi_it
*bidi_it
)
739 int i
= bidi_cache_search (charpos
, level
, bidi_it
->scan_dir
);
743 bidi_dir_t current_scan_dir
= bidi_it
->scan_dir
;
745 bidi_copy_it (bidi_it
, &bidi_cache
[i
]);
746 bidi_cache_last_idx
= i
;
747 /* Don't let scan direction from from the cached state override
748 the current scan direction. */
749 bidi_it
->scan_dir
= current_scan_dir
;
750 return bidi_it
->type
;
757 bidi_peek_at_next_level (struct bidi_it
*bidi_it
)
759 if (bidi_cache_idx
== 0 || bidi_cache_last_idx
== -1)
761 return bidi_cache
[bidi_cache_last_idx
+ bidi_it
->scan_dir
].resolved_level
;
764 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
765 Value is the non-negative length of the paragraph separator
766 following the buffer position, -1 if position is at the beginning
767 of a new paragraph, or -2 if position is neither at beginning nor
768 at end of a paragraph. */
770 bidi_at_paragraph_end (EMACS_INT charpos
, EMACS_INT bytepos
)
772 /* FIXME: Why Fbuffer_local_value rather than just Fsymbol_value? */
774 Lisp_Object start_re
;
777 sep_re
= paragraph_separate_re
;
778 start_re
= paragraph_start_re
;
780 val
= fast_looking_at (sep_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
);
783 if (fast_looking_at (start_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
) >= 0)
792 /* Determine the start-of-run (sor) directional type given the two
793 embedding levels on either side of the run boundary. Also, update
794 the saved info about previously seen characters, since that info is
795 generally valid for a single level run. */
797 bidi_set_sor_type (struct bidi_it
*bidi_it
, int level_before
, int level_after
)
799 int higher_level
= level_before
> level_after
? level_before
: level_after
;
801 /* The prev_was_pdf gork is required for when we have several PDFs
802 in a row. In that case, we want to compute the sor type for the
803 next level run only once: when we see the first PDF. That's
804 because the sor type depends only on the higher of the two levels
805 that we find on the two sides of the level boundary (see UAX#9,
806 clause X10), and so we don't need to know the final embedding
807 level to which we descend after processing all the PDFs. */
808 if (!bidi_it
->prev_was_pdf
|| level_before
< level_after
)
809 /* FIXME: should the default sor direction be user selectable? */
810 bidi_it
->sor
= (higher_level
& 1) != 0 ? R2L
: L2R
;
811 if (level_before
> level_after
)
812 bidi_it
->prev_was_pdf
= 1;
814 bidi_it
->prev
.type
= UNKNOWN_BT
;
815 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
816 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
817 bidi_it
->prev_for_neutral
.type
= bidi_it
->sor
== R2L
? STRONG_R
: STRONG_L
;
818 bidi_it
->prev_for_neutral
.charpos
= bidi_it
->charpos
;
819 bidi_it
->prev_for_neutral
.bytepos
= bidi_it
->bytepos
;
820 bidi_it
->next_for_neutral
.type
= bidi_it
->next_for_neutral
.type_after_w1
=
821 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
822 bidi_it
->ignore_bn_limit
= 0; /* meaning it's unknown */
826 bidi_line_init (struct bidi_it
*bidi_it
)
828 bidi_it
->scan_dir
= 1; /* FIXME: do we need to have control on this? */
829 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
830 bidi_it
->level_stack
[0].override
= NEUTRAL_DIR
; /* X1 */
831 bidi_it
->invalid_levels
= 0;
832 bidi_it
->invalid_rl_levels
= -1;
833 bidi_it
->next_en_pos
= -1;
834 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
835 bidi_set_sor_type (bidi_it
,
836 bidi_it
->paragraph_dir
== R2L
? 1 : 0,
837 bidi_it
->level_stack
[0].level
); /* X10 */
842 /* Find the beginning of this paragraph by looking back in the buffer.
843 Value is the byte position of the paragraph's beginning. */
845 bidi_find_paragraph_start (EMACS_INT pos
, EMACS_INT pos_byte
)
847 Lisp_Object re
= paragraph_start_re
;
848 EMACS_INT limit
= ZV
, limit_byte
= ZV_BYTE
;
850 while (pos_byte
> BEGV_BYTE
851 && fast_looking_at (re
, pos
, pos_byte
, limit
, limit_byte
, Qnil
) < 0)
853 pos
= find_next_newline_no_quit (pos
- 1, -1);
854 pos_byte
= CHAR_TO_BYTE (pos
);
859 /* Determine the direction, a.k.a. base embedding level, of the
860 paragraph we are about to iterate through. If DIR is either L2R or
861 R2L, just use that. Otherwise, determine the paragraph direction
862 from the first strong character of the paragraph.
864 Note that this gives the paragraph separator the same direction as
865 the preceding paragraph, even though Emacs generally views the
866 separartor as not belonging to any paragraph. */
868 bidi_paragraph_init (bidi_dir_t dir
, struct bidi_it
*bidi_it
)
870 EMACS_INT bytepos
= bidi_it
->bytepos
;
872 /* Special case for an empty buffer. */
873 if (bytepos
== BEGV_BYTE
&& bytepos
== ZV_BYTE
)
875 /* We should never be called at EOB or before BEGV. */
876 else if (bytepos
>= ZV_BYTE
|| bytepos
< BEGV_BYTE
)
881 bidi_it
->paragraph_dir
= L2R
;
882 bidi_it
->new_paragraph
= 0;
886 bidi_it
->paragraph_dir
= R2L
;
887 bidi_it
->new_paragraph
= 0;
889 else if (dir
== NEUTRAL_DIR
) /* P2 */
895 if (!bidi_initialized
)
898 /* If we are inside a paragraph separator, we are just waiting
899 for the separator to be exhausted; use the previous paragraph
900 direction. But don't do that if we have been just reseated,
901 because we need to reinitialize below in that case. */
902 if (!bidi_it
->first_elt
903 && bidi_it
->charpos
< bidi_it
->separator_limit
)
906 /* If we are on a newline, get past it to where the next
907 paragraph might start. But don't do that at BEGV since then
908 we are potentially in a new paragraph that doesn't yet
910 pos
= bidi_it
->charpos
;
911 if (bytepos
> BEGV_BYTE
&& FETCH_CHAR (bytepos
) == '\n')
917 /* We are either at the beginning of a paragraph or in the
918 middle of it. Find where this paragraph starts. */
919 bytepos
= bidi_find_paragraph_start (pos
, bytepos
);
921 bidi_it
->separator_limit
= -1;
922 bidi_it
->new_paragraph
= 0;
923 ch
= FETCH_CHAR (bytepos
);
924 ch_len
= CHAR_BYTES (ch
);
925 pos
= BYTE_TO_CHAR (bytepos
);
926 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
928 for (pos
++, bytepos
+= ch_len
;
929 /* NOTE: UAX#9 says to search only for L, AL, or R types of
930 characters, and ignore RLE, RLO, LRE, and LRO. However,
931 I'm not sure it makes sense to omit those 4; should try
932 with and without that to see the effect. */
933 (bidi_get_category (type
) != STRONG
)
934 || (bidi_ignore_explicit_marks_for_paragraph_level
935 && (type
== RLE
|| type
== RLO
936 || type
== LRE
|| type
== LRO
));
937 type
= bidi_get_type (ch
, NEUTRAL_DIR
))
939 if (type
== NEUTRAL_B
&& bidi_at_paragraph_end (pos
, bytepos
) >= -1)
941 if (bytepos
>= ZV_BYTE
)
943 /* Pretend there's a paragraph separator at end of buffer. */
947 FETCH_CHAR_ADVANCE (ch
, pos
, bytepos
);
949 if (type
== STRONG_R
|| type
== STRONG_AL
) /* P3 */
950 bidi_it
->paragraph_dir
= R2L
;
951 else if (type
== STRONG_L
)
952 bidi_it
->paragraph_dir
= L2R
;
957 /* Contrary to UAX#9 clause P3, we only default the paragraph
958 direction to L2R if we have no previous usable paragraph
960 if (bidi_it
->paragraph_dir
!= L2R
&& bidi_it
->paragraph_dir
!= R2L
)
961 bidi_it
->paragraph_dir
= L2R
; /* P3 and ``higher protocols'' */
962 if (bidi_it
->paragraph_dir
== R2L
)
963 bidi_it
->level_stack
[0].level
= 1;
965 bidi_it
->level_stack
[0].level
= 0;
967 bidi_line_init (bidi_it
);
970 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
973 bidi_set_paragraph_end (struct bidi_it
*bidi_it
)
975 bidi_it
->invalid_levels
= 0;
976 bidi_it
->invalid_rl_levels
= -1;
977 bidi_it
->stack_idx
= 0;
978 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
981 /* Initialize the bidi iterator from buffer position CHARPOS. */
983 bidi_init_it (EMACS_INT charpos
, EMACS_INT bytepos
, struct bidi_it
*bidi_it
)
985 if (! bidi_initialized
)
987 bidi_it
->charpos
= charpos
;
988 bidi_it
->bytepos
= bytepos
;
989 bidi_it
->first_elt
= 1;
990 bidi_set_paragraph_end (bidi_it
);
991 bidi_it
->new_paragraph
= 1;
992 bidi_it
->separator_limit
= -1;
993 bidi_it
->type
= NEUTRAL_B
;
994 bidi_it
->type_after_w1
= NEUTRAL_B
;
995 bidi_it
->orig_type
= NEUTRAL_B
;
996 bidi_it
->prev_was_pdf
= 0;
997 bidi_it
->prev
.type
= bidi_it
->prev
.type_after_w1
=
998 bidi_it
->prev
.orig_type
= UNKNOWN_BT
;
999 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
1000 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
1001 bidi_it
->next_for_neutral
.charpos
= -1;
1002 bidi_it
->next_for_neutral
.type
=
1003 bidi_it
->next_for_neutral
.type_after_w1
=
1004 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
1005 bidi_it
->prev_for_neutral
.charpos
= -1;
1006 bidi_it
->prev_for_neutral
.type
=
1007 bidi_it
->prev_for_neutral
.type_after_w1
=
1008 bidi_it
->prev_for_neutral
.orig_type
= UNKNOWN_BT
;
1009 bidi_it
->sor
= L2R
; /* FIXME: should it be user-selectable? */
1010 bidi_cache_shrink ();
1013 /* Push the current embedding level and override status; reset the
1014 current level to LEVEL and the current override status to OVERRIDE. */
1016 bidi_push_embedding_level (struct bidi_it
*bidi_it
,
1017 int level
, bidi_dir_t override
)
1019 bidi_it
->stack_idx
++;
1020 if (bidi_it
->stack_idx
>= BIDI_MAXLEVEL
)
1022 bidi_it
->level_stack
[bidi_it
->stack_idx
].level
= level
;
1023 bidi_it
->level_stack
[bidi_it
->stack_idx
].override
= override
;
1026 /* Pop the embedding level and directional override status from the
1027 stack, and return the new level. */
1029 bidi_pop_embedding_level (struct bidi_it
*bidi_it
)
1031 /* UAX#9 says to ignore invalid PDFs. */
1032 if (bidi_it
->stack_idx
> 0)
1033 bidi_it
->stack_idx
--;
1034 return bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1037 /* Record in SAVED_INFO the information about the current character. */
1039 bidi_remember_char (struct bidi_saved_info
*saved_info
,
1040 struct bidi_it
*bidi_it
)
1042 saved_info
->charpos
= bidi_it
->charpos
;
1043 saved_info
->bytepos
= bidi_it
->bytepos
;
1044 saved_info
->type
= bidi_it
->type
;
1045 bidi_check_type (bidi_it
->type
);
1046 saved_info
->type_after_w1
= bidi_it
->type_after_w1
;
1047 bidi_check_type (bidi_it
->type_after_w1
);
1048 saved_info
->orig_type
= bidi_it
->orig_type
;
1049 bidi_check_type (bidi_it
->orig_type
);
1052 /* Resolve the type of a neutral character according to the type of
1053 surrounding strong text and the current embedding level. */
1054 static INLINE bidi_type_t
1055 bidi_resolve_neutral_1 (bidi_type_t prev_type
, bidi_type_t next_type
, int lev
)
1057 /* N1: European and Arabic numbers are treated as though they were R. */
1058 if (next_type
== WEAK_EN
|| next_type
== WEAK_AN
)
1059 next_type
= STRONG_R
;
1060 if (prev_type
== WEAK_EN
|| prev_type
== WEAK_AN
)
1061 prev_type
= STRONG_R
;
1063 if (next_type
== prev_type
) /* N1 */
1065 else if ((lev
& 1) == 0) /* N2 */
1072 bidi_explicit_dir_char (int c
)
1074 /* FIXME: this should be replaced with a lookup table with suitable
1075 bits set, like standard C ctype macros do. */
1076 return (c
== LRE_CHAR
|| c
== LRO_CHAR
1077 || c
== RLE_CHAR
|| c
== RLO_CHAR
|| c
== PDF_CHAR
);
1080 /* A helper function for bidi_resolve_explicit. It advances to the
1081 next character in logical order and determines the new embedding
1082 level and directional override, but does not take into account
1083 empty embeddings. */
1085 bidi_resolve_explicit_1 (struct bidi_it
*bidi_it
)
1091 bidi_dir_t override
;
1093 if (bidi_it
->bytepos
< BEGV_BYTE
/* after reseat to BEGV? */
1094 || bidi_it
->first_elt
)
1096 bidi_it
->first_elt
= 0;
1097 if (bidi_it
->charpos
< BEGV
)
1098 bidi_it
->charpos
= BEGV
;
1099 bidi_it
->bytepos
= CHAR_TO_BYTE (bidi_it
->charpos
);
1101 else if (bidi_it
->bytepos
< ZV_BYTE
) /* don't move at ZV */
1104 if (bidi_it
->ch_len
== 0)
1106 bidi_it
->bytepos
+= bidi_it
->ch_len
;
1109 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
; /* X1 */
1110 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1111 new_level
= current_level
;
1113 /* in case it is a unibyte character (not yet implemented) */
1114 /* _fetch_multibyte_char_len = 1; */
1115 if (bidi_it
->bytepos
>= ZV_BYTE
)
1118 bidi_it
->ch_len
= 1;
1122 curchar
= FETCH_CHAR (bidi_it
->bytepos
);
1123 bidi_it
->ch_len
= CHAR_BYTES (curchar
);
1125 bidi_it
->ch
= curchar
;
1127 /* Don't apply directional override here, as all the types we handle
1128 below will not be affected by the override anyway, and we need
1129 the original type unaltered. The override will be applied in
1130 bidi_resolve_weak. */
1131 type
= bidi_get_type (curchar
, NEUTRAL_DIR
);
1132 bidi_it
->orig_type
= type
;
1133 bidi_check_type (bidi_it
->orig_type
);
1136 bidi_it
->prev_was_pdf
= 0;
1138 bidi_it
->type_after_w1
= UNKNOWN_BT
;
1144 bidi_it
->type_after_w1
= type
;
1145 bidi_check_type (bidi_it
->type_after_w1
);
1146 type
= WEAK_BN
; /* X9/Retaining */
1147 if (bidi_it
->ignore_bn_limit
<= 0)
1149 if (current_level
<= BIDI_MAXLEVEL
- 4)
1151 /* Compute the least odd embedding level greater than
1152 the current level. */
1153 new_level
= ((current_level
+ 1) & ~1) + 1;
1154 if (bidi_it
->type_after_w1
== RLE
)
1155 override
= NEUTRAL_DIR
;
1158 if (current_level
== BIDI_MAXLEVEL
- 4)
1159 bidi_it
->invalid_rl_levels
= 0;
1160 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1164 bidi_it
->invalid_levels
++;
1165 /* See the commentary about invalid_rl_levels below. */
1166 if (bidi_it
->invalid_rl_levels
< 0)
1167 bidi_it
->invalid_rl_levels
= 0;
1168 bidi_it
->invalid_rl_levels
++;
1171 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1172 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1177 bidi_it
->type_after_w1
= type
;
1178 bidi_check_type (bidi_it
->type_after_w1
);
1179 type
= WEAK_BN
; /* X9/Retaining */
1180 if (bidi_it
->ignore_bn_limit
<= 0)
1182 if (current_level
<= BIDI_MAXLEVEL
- 5)
1184 /* Compute the least even embedding level greater than
1185 the current level. */
1186 new_level
= ((current_level
+ 2) & ~1);
1187 if (bidi_it
->type_after_w1
== LRE
)
1188 override
= NEUTRAL_DIR
;
1191 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1195 bidi_it
->invalid_levels
++;
1196 /* invalid_rl_levels counts invalid levels encountered
1197 while the embedding level was already too high for
1198 LRE/LRO, but not for RLE/RLO. That is because
1199 there may be exactly one PDF which we should not
1200 ignore even though invalid_levels is non-zero.
1201 invalid_rl_levels helps to know what PDF is
1203 if (bidi_it
->invalid_rl_levels
>= 0)
1204 bidi_it
->invalid_rl_levels
++;
1207 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1208 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1212 bidi_it
->type_after_w1
= type
;
1213 bidi_check_type (bidi_it
->type_after_w1
);
1214 type
= WEAK_BN
; /* X9/Retaining */
1215 if (bidi_it
->ignore_bn_limit
<= 0)
1217 if (!bidi_it
->invalid_rl_levels
)
1219 new_level
= bidi_pop_embedding_level (bidi_it
);
1220 bidi_it
->invalid_rl_levels
= -1;
1221 if (bidi_it
->invalid_levels
)
1222 bidi_it
->invalid_levels
--;
1223 /* else nothing: UAX#9 says to ignore invalid PDFs */
1225 if (!bidi_it
->invalid_levels
)
1226 new_level
= bidi_pop_embedding_level (bidi_it
);
1229 bidi_it
->invalid_levels
--;
1230 bidi_it
->invalid_rl_levels
--;
1233 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1234 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1242 bidi_it
->type
= type
;
1243 bidi_check_type (bidi_it
->type
);
1248 /* Given an iterator state in BIDI_IT, advance one character position
1249 in the buffer to the next character (in the logical order), resolve
1250 any explicit embeddings and directional overrides, and return the
1251 embedding level of the character after resolving explicit
1252 directives and ignoring empty embeddings. */
1254 bidi_resolve_explicit (struct bidi_it
*bidi_it
)
1256 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1257 int new_level
= bidi_resolve_explicit_1 (bidi_it
);
1259 if (prev_level
< new_level
1260 && bidi_it
->type
== WEAK_BN
1261 && bidi_it
->ignore_bn_limit
== 0 /* only if not already known */
1262 && bidi_it
->bytepos
< ZV_BYTE
/* not already at EOB */
1263 && bidi_explicit_dir_char (FETCH_CHAR (bidi_it
->bytepos
1264 + bidi_it
->ch_len
)))
1266 /* Avoid pushing and popping embedding levels if the level run
1267 is empty, as this breaks level runs where it shouldn't.
1268 UAX#9 removes all the explicit embedding and override codes,
1269 so empty embeddings disappear without a trace. We need to
1270 behave as if we did the same. */
1271 struct bidi_it saved_it
;
1272 int level
= prev_level
;
1274 bidi_copy_it (&saved_it
, bidi_it
);
1276 while (bidi_explicit_dir_char (FETCH_CHAR (bidi_it
->bytepos
1277 + bidi_it
->ch_len
)))
1279 level
= bidi_resolve_explicit_1 (bidi_it
);
1282 if (level
== prev_level
) /* empty embedding */
1283 saved_it
.ignore_bn_limit
= bidi_it
->charpos
+ 1;
1284 else /* this embedding is non-empty */
1285 saved_it
.ignore_bn_limit
= -1;
1287 bidi_copy_it (bidi_it
, &saved_it
);
1288 if (bidi_it
->ignore_bn_limit
> 0)
1290 /* We pushed a level, but we shouldn't have. Undo that. */
1291 if (!bidi_it
->invalid_rl_levels
)
1293 new_level
= bidi_pop_embedding_level (bidi_it
);
1294 bidi_it
->invalid_rl_levels
= -1;
1295 if (bidi_it
->invalid_levels
)
1296 bidi_it
->invalid_levels
--;
1298 if (!bidi_it
->invalid_levels
)
1299 new_level
= bidi_pop_embedding_level (bidi_it
);
1302 bidi_it
->invalid_levels
--;
1303 bidi_it
->invalid_rl_levels
--;
1308 if (bidi_it
->type
== NEUTRAL_B
) /* X8 */
1310 bidi_set_paragraph_end (bidi_it
);
1311 /* This is needed by bidi_resolve_weak below, and in L1. */
1312 bidi_it
->type_after_w1
= bidi_it
->type
;
1313 bidi_check_type (bidi_it
->type_after_w1
);
1319 /* Advance in the buffer, resolve weak types and return the type of
1320 the next character after weak type resolution. */
1322 bidi_resolve_weak (struct bidi_it
*bidi_it
)
1325 bidi_dir_t override
;
1326 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1327 int new_level
= bidi_resolve_explicit (bidi_it
);
1329 bidi_type_t type_of_next
;
1330 struct bidi_it saved_it
;
1332 type
= bidi_it
->type
;
1333 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1335 if (type
== UNKNOWN_BT
1343 if (new_level
!= prev_level
1344 || bidi_it
->type
== NEUTRAL_B
)
1346 /* We've got a new embedding level run, compute the directional
1347 type of sor and initialize per-run variables (UAX#9, clause
1349 bidi_set_sor_type (bidi_it
, prev_level
, new_level
);
1351 else if (type
== NEUTRAL_S
|| type
== NEUTRAL_WS
1352 || type
== WEAK_BN
|| type
== STRONG_AL
)
1353 bidi_it
->type_after_w1
= type
; /* needed in L1 */
1354 bidi_check_type (bidi_it
->type_after_w1
);
1356 /* Level and directional override status are already recorded in
1357 bidi_it, and do not need any change; see X6. */
1358 if (override
== R2L
) /* X6 */
1360 else if (override
== L2R
)
1364 if (type
== WEAK_NSM
) /* W1 */
1366 /* Note that we don't need to consider the case where the
1367 prev character has its type overridden by an RLO or LRO,
1368 because then either the type of this NSM would have been
1369 also overridden, or the previous character is outside the
1370 current level run, and thus not relevant to this NSM.
1371 This is why NSM gets the type_after_w1 of the previous
1373 if (bidi_it
->prev
.type_after_w1
!= UNKNOWN_BT
1374 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1375 && bidi_it
->prev
.type_after_w1
!= NEUTRAL_B
)
1376 type
= bidi_it
->prev
.type_after_w1
;
1377 else if (bidi_it
->sor
== R2L
)
1379 else if (bidi_it
->sor
== L2R
)
1381 else /* shouldn't happen! */
1384 if (type
== WEAK_EN
/* W2 */
1385 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1387 else if (type
== STRONG_AL
) /* W3 */
1389 else if ((type
== WEAK_ES
/* W4 */
1390 && bidi_it
->prev
.type_after_w1
== WEAK_EN
1391 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1393 && ((bidi_it
->prev
.type_after_w1
== WEAK_EN
1394 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1395 || bidi_it
->prev
.type_after_w1
== WEAK_AN
)))
1398 bidi_it
->bytepos
+ bidi_it
->ch_len
>= ZV_BYTE
1399 ? BIDI_EOB
: FETCH_CHAR (bidi_it
->bytepos
+ bidi_it
->ch_len
);
1400 type_of_next
= bidi_get_type (next_char
, override
);
1402 if (type_of_next
== WEAK_BN
1403 || bidi_explicit_dir_char (next_char
))
1405 bidi_copy_it (&saved_it
, bidi_it
);
1406 while (bidi_resolve_explicit (bidi_it
) == new_level
1407 && bidi_it
->type
== WEAK_BN
)
1409 type_of_next
= bidi_it
->type
;
1410 bidi_copy_it (bidi_it
, &saved_it
);
1413 /* If the next character is EN, but the last strong-type
1414 character is AL, that next EN will be changed to AN when
1415 we process it in W2 above. So in that case, this ES
1416 should not be changed into EN. */
1418 && type_of_next
== WEAK_EN
1419 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1421 else if (type
== WEAK_CS
)
1423 if (bidi_it
->prev
.type_after_w1
== WEAK_AN
1424 && (type_of_next
== WEAK_AN
1425 /* If the next character is EN, but the last
1426 strong-type character is AL, EN will be later
1427 changed to AN when we process it in W2 above.
1428 So in that case, this ES should not be
1430 || (type_of_next
== WEAK_EN
1431 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)))
1433 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
1434 && type_of_next
== WEAK_EN
1435 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1439 else if (type
== WEAK_ET
/* W5: ET with EN before or after it */
1440 || type
== WEAK_BN
) /* W5/Retaining */
1442 if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* ET/BN w/EN before it */
1443 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1445 else /* W5: ET/BN with EN after it. */
1447 EMACS_INT en_pos
= bidi_it
->charpos
+ 1;
1450 bidi_it
->bytepos
+ bidi_it
->ch_len
>= ZV_BYTE
1451 ? BIDI_EOB
: FETCH_CHAR (bidi_it
->bytepos
+ bidi_it
->ch_len
);
1452 type_of_next
= bidi_get_type (next_char
, override
);
1454 if (type_of_next
== WEAK_ET
1455 || type_of_next
== WEAK_BN
1456 || bidi_explicit_dir_char (next_char
))
1458 bidi_copy_it (&saved_it
, bidi_it
);
1459 while (bidi_resolve_explicit (bidi_it
) == new_level
1460 && (bidi_it
->type
== WEAK_BN
1461 || bidi_it
->type
== WEAK_ET
))
1463 type_of_next
= bidi_it
->type
;
1464 en_pos
= bidi_it
->charpos
;
1465 bidi_copy_it (bidi_it
, &saved_it
);
1467 if (type_of_next
== WEAK_EN
)
1469 /* If the last strong character is AL, the EN we've
1470 found will become AN when we get to it (W2). */
1471 if (bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1474 /* Remember this EN position, to speed up processing
1476 bidi_it
->next_en_pos
= en_pos
;
1478 else if (type
== WEAK_BN
)
1479 type
= NEUTRAL_ON
; /* W6/Retaining */
1485 if (type
== WEAK_ES
|| type
== WEAK_ET
|| type
== WEAK_CS
/* W6 */
1487 && (bidi_it
->prev
.type_after_w1
== WEAK_CS
/* W6/Retaining */
1488 || bidi_it
->prev
.type_after_w1
== WEAK_ES
1489 || bidi_it
->prev
.type_after_w1
== WEAK_ET
)))
1492 /* Store the type we've got so far, before we clobber it with strong
1493 types in W7 and while resolving neutral types. But leave alone
1494 the original types that were recorded above, because we will need
1495 them for the L1 clause. */
1496 if (bidi_it
->type_after_w1
== UNKNOWN_BT
)
1497 bidi_it
->type_after_w1
= type
;
1498 bidi_check_type (bidi_it
->type_after_w1
);
1500 if (type
== WEAK_EN
) /* W7 */
1502 if ((bidi_it
->last_strong
.type_after_w1
== STRONG_L
)
1503 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
&& bidi_it
->sor
== L2R
))
1507 bidi_it
->type
= type
;
1508 bidi_check_type (bidi_it
->type
);
1513 bidi_resolve_neutral (struct bidi_it
*bidi_it
)
1515 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1516 bidi_type_t type
= bidi_resolve_weak (bidi_it
);
1517 int current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1519 if (!(type
== STRONG_R
1524 || type
== NEUTRAL_B
1525 || type
== NEUTRAL_S
1526 || type
== NEUTRAL_WS
1527 || type
== NEUTRAL_ON
))
1530 if (bidi_get_category (type
) == NEUTRAL
1531 || (type
== WEAK_BN
&& prev_level
== current_level
))
1533 if (bidi_it
->next_for_neutral
.type
!= UNKNOWN_BT
)
1534 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1535 bidi_it
->next_for_neutral
.type
,
1539 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1540 the assumption of batch-style processing; see clauses W4,
1541 W5, and especially N1, which require to look far forward
1542 (as well as back) in the buffer. May the fleas of a
1543 thousand camels infest the armpits of those who design
1544 supposedly general-purpose algorithms by looking at their
1545 own implementations, and fail to consider other possible
1547 struct bidi_it saved_it
;
1548 bidi_type_t next_type
;
1550 if (bidi_it
->scan_dir
== -1)
1553 bidi_copy_it (&saved_it
, bidi_it
);
1554 /* Scan the text forward until we find the first non-neutral
1555 character, and then use that to resolve the neutral we
1556 are dealing with now. We also cache the scanned iterator
1557 states, to salvage some of the effort later. */
1558 bidi_cache_iterator_state (bidi_it
, 0);
1560 /* Record the info about the previous character, so that
1561 it will be cached below with this state. */
1562 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1563 && bidi_it
->type
!= WEAK_BN
)
1564 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1565 type
= bidi_resolve_weak (bidi_it
);
1566 /* Paragraph separators have their levels fully resolved
1567 at this point, so cache them as resolved. */
1568 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
);
1569 /* FIXME: implement L1 here, by testing for a newline and
1570 resetting the level for any sequence of whitespace
1571 characters adjacent to it. */
1572 } while (!(type
== NEUTRAL_B
1574 && bidi_get_category (type
) != NEUTRAL
)
1575 /* This is all per level run, so stop when we
1576 reach the end of this level run. */
1577 || bidi_it
->level_stack
[bidi_it
->stack_idx
].level
!=
1580 bidi_remember_char (&saved_it
.next_for_neutral
, bidi_it
);
1591 /* N1: ``European and Arabic numbers are treated as
1592 though they were R.'' */
1593 next_type
= STRONG_R
;
1594 saved_it
.next_for_neutral
.type
= STRONG_R
;
1597 if (!bidi_explicit_dir_char (bidi_it
->ch
))
1598 abort (); /* can't happen: BNs are skipped */
1601 /* Marched all the way to the end of this level run.
1602 We need to use the eor type, whose information is
1603 stored by bidi_set_sor_type in the prev_for_neutral
1605 if (saved_it
.type
!= WEAK_BN
1606 || bidi_get_category (bidi_it
->prev
.type_after_w1
) == NEUTRAL
)
1608 next_type
= bidi_it
->prev_for_neutral
.type
;
1609 saved_it
.next_for_neutral
.type
= next_type
;
1610 bidi_check_type (next_type
);
1614 /* This is a BN which does not adjoin neutrals.
1615 Leave its type alone. */
1616 bidi_copy_it (bidi_it
, &saved_it
);
1617 return bidi_it
->type
;
1623 type
= bidi_resolve_neutral_1 (saved_it
.prev_for_neutral
.type
,
1624 next_type
, current_level
);
1625 saved_it
.type
= type
;
1626 bidi_check_type (type
);
1627 bidi_copy_it (bidi_it
, &saved_it
);
1633 /* Given an iterator state in BIDI_IT, advance one character position
1634 in the buffer to the next character (in the logical order), resolve
1635 the bidi type of that next character, and return that type. */
1637 bidi_type_of_next_char (struct bidi_it
*bidi_it
)
1641 /* This should always be called during a forward scan. */
1642 if (bidi_it
->scan_dir
!= 1)
1645 /* Reset the limit until which to ignore BNs if we step out of the
1646 area where we found only empty levels. */
1647 if ((bidi_it
->ignore_bn_limit
> 0
1648 && bidi_it
->ignore_bn_limit
<= bidi_it
->charpos
)
1649 || (bidi_it
->ignore_bn_limit
== -1
1650 && !bidi_explicit_dir_char (bidi_it
->ch
)))
1651 bidi_it
->ignore_bn_limit
= 0;
1653 type
= bidi_resolve_neutral (bidi_it
);
1658 /* Given an iterator state BIDI_IT, advance one character position in
1659 the buffer to the next character (in the logical order), resolve
1660 the embedding and implicit levels of that next character, and
1661 return the resulting level. */
1663 bidi_level_of_next_char (struct bidi_it
*bidi_it
)
1666 int level
, prev_level
= -1;
1667 struct bidi_saved_info next_for_neutral
;
1669 if (bidi_it
->scan_dir
== 1)
1671 /* There's no sense in trying to advance if we hit end of text. */
1672 if (bidi_it
->bytepos
>= ZV_BYTE
)
1673 return bidi_it
->resolved_level
;
1675 /* Record the info about the previous character. */
1676 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1677 && bidi_it
->type
!= WEAK_BN
)
1678 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1679 if (bidi_it
->type_after_w1
== STRONG_R
1680 || bidi_it
->type_after_w1
== STRONG_L
1681 || bidi_it
->type_after_w1
== STRONG_AL
)
1682 bidi_remember_char (&bidi_it
->last_strong
, bidi_it
);
1683 /* FIXME: it sounds like we don't need both prev and
1684 prev_for_neutral members, but I'm leaving them both for now. */
1685 if (bidi_it
->type
== STRONG_R
|| bidi_it
->type
== STRONG_L
1686 || bidi_it
->type
== WEAK_EN
|| bidi_it
->type
== WEAK_AN
)
1687 bidi_remember_char (&bidi_it
->prev_for_neutral
, bidi_it
);
1689 /* If we overstepped the characters used for resolving neutrals
1690 and whitespace, invalidate their info in the iterator. */
1691 if (bidi_it
->charpos
>= bidi_it
->next_for_neutral
.charpos
)
1692 bidi_it
->next_for_neutral
.type
= UNKNOWN_BT
;
1693 if (bidi_it
->next_en_pos
>= 0
1694 && bidi_it
->charpos
>= bidi_it
->next_en_pos
)
1695 bidi_it
->next_en_pos
= -1;
1696 if (bidi_it
->next_for_ws
.type
!= UNKNOWN_BT
1697 && bidi_it
->charpos
>= bidi_it
->next_for_ws
.charpos
)
1698 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
1700 /* This must be taken before we fill the iterator with the info
1701 about the next char. If we scan backwards, the iterator
1702 state must be already cached, so there's no need to know the
1703 embedding level of the previous character, since we will be
1704 returning to our caller shortly. */
1705 prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1707 next_for_neutral
= bidi_it
->next_for_neutral
;
1709 /* Perhaps it is already cached. */
1710 type
= bidi_cache_find (bidi_it
->charpos
+ bidi_it
->scan_dir
, -1, bidi_it
);
1711 if (type
!= UNKNOWN_BT
)
1713 /* Don't lose the information for resolving neutrals! The
1714 cached states could have been cached before their
1715 next_for_neutral member was computed. If we are on our way
1716 forward, we can simply take the info from the previous
1718 if (bidi_it
->scan_dir
== 1
1719 && bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1720 bidi_it
->next_for_neutral
= next_for_neutral
;
1722 /* If resolved_level is -1, it means this state was cached
1723 before it was completely resolved, so we cannot return
1725 if (bidi_it
->resolved_level
!= -1)
1726 return bidi_it
->resolved_level
;
1728 if (bidi_it
->scan_dir
== -1)
1729 /* If we are going backwards, the iterator state is already cached
1730 from previous scans, and should be fully resolved. */
1733 if (type
== UNKNOWN_BT
)
1734 type
= bidi_type_of_next_char (bidi_it
);
1736 if (type
== NEUTRAL_B
)
1737 return bidi_it
->resolved_level
;
1739 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1740 if ((bidi_get_category (type
) == NEUTRAL
/* && type != NEUTRAL_B */)
1741 || (type
== WEAK_BN
&& prev_level
== level
))
1743 if (bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1746 /* If the cached state shows a neutral character, it was not
1747 resolved by bidi_resolve_neutral, so do it now. */
1748 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1749 bidi_it
->next_for_neutral
.type
,
1753 if (!(type
== STRONG_R
1757 || type
== WEAK_AN
))
1759 bidi_it
->type
= type
;
1760 bidi_check_type (bidi_it
->type
);
1762 /* For L1 below, we need to know, for each WS character, whether
1763 it belongs to a sequence of WS characters preceeding a newline
1764 or a TAB or a paragraph separator. */
1765 if (bidi_it
->orig_type
== NEUTRAL_WS
1766 && bidi_it
->next_for_ws
.type
== UNKNOWN_BT
)
1769 int clen
= bidi_it
->ch_len
;
1770 EMACS_INT bpos
= bidi_it
->bytepos
;
1771 EMACS_INT cpos
= bidi_it
->charpos
;
1775 /*_fetch_multibyte_char_len = 1;*/
1776 ch
= bpos
+ clen
>= ZV_BYTE
? BIDI_EOB
: FETCH_CHAR (bpos
+ clen
);
1779 clen
= (ch
== BIDI_EOB
? 1 : CHAR_BYTES (ch
));
1780 if (ch
== '\n' || ch
== BIDI_EOB
/* || ch == LINESEP_CHAR */)
1783 chtype
= bidi_get_type (ch
, NEUTRAL_DIR
);
1784 } while (chtype
== NEUTRAL_WS
|| chtype
== WEAK_BN
1785 || bidi_explicit_dir_char (ch
)); /* L1/Retaining */
1786 bidi_it
->next_for_ws
.type
= chtype
;
1787 bidi_check_type (bidi_it
->next_for_ws
.type
);
1788 bidi_it
->next_for_ws
.charpos
= cpos
;
1789 bidi_it
->next_for_ws
.bytepos
= bpos
;
1792 /* Resolve implicit levels, with a twist: PDFs get the embedding
1793 level of the enbedding they terminate. See below for the
1795 if (bidi_it
->orig_type
== PDF
1796 /* Don't do this if this formatting code didn't change the
1797 embedding level due to invalid or empty embeddings. */
1798 && prev_level
!= level
)
1800 /* Don't look in UAX#9 for the reason for this: it's our own
1801 private quirk. The reason is that we want the formatting
1802 codes to be delivered so that they bracket the text of their
1803 embedding. For example, given the text
1807 we want it to be displayed as
1815 which will result because we bump up the embedding level as
1816 soon as we see the RLO and pop it as soon as we see the PDF,
1817 so RLO itself has the same embedding level as "teST", and
1818 thus would be normally delivered last, just before the PDF.
1819 The switch below fiddles with the level of PDF so that this
1820 ugly side effect does not happen.
1822 (This is, of course, only important if the formatting codes
1823 are actually displayed, but Emacs does need to display them
1824 if the user wants to.) */
1827 else if (bidi_it
->orig_type
== NEUTRAL_B
/* L1 */
1828 || bidi_it
->orig_type
== NEUTRAL_S
1829 || bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
1830 /* || bidi_it->ch == LINESEP_CHAR */
1831 || (bidi_it
->orig_type
== NEUTRAL_WS
1832 && (bidi_it
->next_for_ws
.type
== NEUTRAL_B
1833 || bidi_it
->next_for_ws
.type
== NEUTRAL_S
)))
1834 level
= bidi_it
->level_stack
[0].level
;
1835 else if ((level
& 1) == 0) /* I1 */
1837 if (type
== STRONG_R
)
1839 else if (type
== WEAK_EN
|| type
== WEAK_AN
)
1844 if (type
== STRONG_L
|| type
== WEAK_EN
|| type
== WEAK_AN
)
1848 bidi_it
->resolved_level
= level
;
1852 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
1853 non-zero, we are at the end of a level, and we need to prepare to
1854 resume the scan of the lower level.
1856 If this level's other edge is cached, we simply jump to it, filling
1857 the iterator structure with the iterator state on the other edge.
1858 Otherwise, we walk the buffer until we come back to the same level
1861 Note: we are not talking here about a ``level run'' in the UAX#9
1862 sense of the term, but rather about a ``level'' which includes
1863 all the levels higher than it. In other words, given the levels
1866 11111112222222333333334443343222222111111112223322111
1869 and assuming we are at point A scanning left to right, this
1870 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
1873 bidi_find_other_level_edge (struct bidi_it
*bidi_it
, int level
, int end_flag
)
1875 int dir
= end_flag
? -bidi_it
->scan_dir
: bidi_it
->scan_dir
;
1878 /* Try the cache first. */
1879 if ((idx
= bidi_cache_find_level_change (level
, dir
, end_flag
)) >= 0)
1880 bidi_cache_fetch_state (idx
, bidi_it
);
1886 abort (); /* if we are at end of level, its edges must be cached */
1888 bidi_cache_iterator_state (bidi_it
, 1);
1890 new_level
= bidi_level_of_next_char (bidi_it
);
1891 bidi_cache_iterator_state (bidi_it
, 1);
1892 } while (new_level
>= level
);
1897 bidi_move_to_visually_next (struct bidi_it
*bidi_it
)
1899 int old_level
, new_level
, next_level
;
1900 struct bidi_it sentinel
;
1902 if (bidi_it
->scan_dir
== 0)
1904 bidi_it
->scan_dir
= 1; /* default to logical order */
1907 /* If we just passed a newline, initialize for the next line. */
1908 if (!bidi_it
->first_elt
&& bidi_it
->orig_type
== NEUTRAL_B
)
1909 bidi_line_init (bidi_it
);
1911 /* Prepare the sentinel iterator state. */
1912 if (bidi_cache_idx
== 0)
1914 bidi_copy_it (&sentinel
, bidi_it
);
1915 if (bidi_it
->first_elt
)
1917 sentinel
.charpos
--; /* cached charpos needs to be monotonic */
1919 sentinel
.ch
= '\n'; /* doesn't matter, but why not? */
1920 sentinel
.ch_len
= 1;
1924 old_level
= bidi_it
->resolved_level
;
1925 new_level
= bidi_level_of_next_char (bidi_it
);
1927 /* Reordering of resolved levels (clause L2) is implemented by
1928 jumping to the other edge of the level and flipping direction of
1929 scanning the text whenever we find a level change. */
1930 if (new_level
!= old_level
)
1932 int ascending
= new_level
> old_level
;
1933 int level_to_search
= ascending
? old_level
+ 1 : old_level
;
1934 int incr
= ascending
? 1 : -1;
1935 int expected_next_level
= old_level
+ incr
;
1937 /* If we don't have anything cached yet, we need to cache the
1938 sentinel state, since we'll need it to record where to jump
1939 when the last non-base level is exhausted. */
1940 if (bidi_cache_idx
== 0)
1941 bidi_cache_iterator_state (&sentinel
, 1);
1942 /* Jump (or walk) to the other edge of this level. */
1943 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
1944 /* Switch scan direction and peek at the next character in the
1946 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
1948 /* The following loop handles the case where the resolved level
1949 jumps by more than one. This is typical for numbers inside a
1950 run of text with left-to-right embedding direction, but can
1951 also happen in other situations. In those cases the decision
1952 where to continue after a level change, and in what direction,
1953 is tricky. For example, given a text like below:
1958 (where the numbers below the text show the resolved levels),
1959 the result of reordering according to UAX#9 should be this:
1963 This is implemented by the loop below which flips direction
1964 and jumps to the other edge of the level each time it finds
1965 the new level not to be the expected one. The expected level
1966 is always one more or one less than the previous one. */
1967 next_level
= bidi_peek_at_next_level (bidi_it
);
1968 while (next_level
!= expected_next_level
)
1970 expected_next_level
+= incr
;
1971 level_to_search
+= incr
;
1972 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
1973 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
1974 next_level
= bidi_peek_at_next_level (bidi_it
);
1977 /* Finally, deliver the next character in the new direction. */
1978 next_level
= bidi_level_of_next_char (bidi_it
);
1981 /* Take note when we have just processed the newline that precedes
1982 the end of the paragraph. The next time we are about to be
1983 called, set_iterator_to_next will automatically reinit the
1984 paragraph direction, if needed. We do this at the newline before
1985 the paragraph separator, because the next character might not be
1986 the first character of the next paragraph, due to the bidi
1987 reordering, whereas we _must_ know the paragraph base direction
1988 _before_ we process the paragraph's text, since the base
1989 direction affects the reordering. */
1990 if (bidi_it
->scan_dir
== 1
1991 && bidi_it
->orig_type
== NEUTRAL_B
1992 && bidi_it
->bytepos
< ZV_BYTE
)
1995 bidi_at_paragraph_end (bidi_it
->charpos
+ 1,
1996 bidi_it
->bytepos
+ bidi_it
->ch_len
);
1999 bidi_it
->new_paragraph
= 1;
2000 /* Record the buffer position of the last character of the
2001 paragraph separator. */
2002 bidi_it
->separator_limit
= bidi_it
->charpos
+ 1 + sep_len
;
2006 if (bidi_it
->scan_dir
== 1 && bidi_cache_idx
)
2008 /* If we are at paragraph's base embedding level and beyond the
2009 last cached position, the cache's job is done and we can
2011 if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
2012 && bidi_it
->charpos
> bidi_cache
[bidi_cache_idx
- 1].charpos
)
2013 bidi_cache_reset ();
2014 /* But as long as we are caching during forward scan, we must
2015 cache each state, or else the cache integrity will be
2016 compromised: it assumes cached states correspond to buffer
2019 bidi_cache_iterator_state (bidi_it
, 1);
2023 /* This is meant to be called from within the debugger, whenever you
2024 wish to examine the cache contents. */
2026 bidi_dump_cached_states (void)
2031 if (bidi_cache_idx
== 0)
2033 fprintf (stderr
, "The cache is empty.\n");
2036 fprintf (stderr
, "Total of %d state%s in cache:\n",
2037 bidi_cache_idx
, bidi_cache_idx
== 1 ? "" : "s");
2039 for (i
= bidi_cache
[bidi_cache_idx
- 1].charpos
; i
> 0; i
/= 10)
2041 fputs ("ch ", stderr
);
2042 for (i
= 0; i
< bidi_cache_idx
; i
++)
2043 fprintf (stderr
, "%*c", ndigits
, bidi_cache
[i
].ch
);
2044 fputs ("\n", stderr
);
2045 fputs ("lvl ", stderr
);
2046 for (i
= 0; i
< bidi_cache_idx
; i
++)
2047 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].resolved_level
);
2048 fputs ("\n", stderr
);
2049 fputs ("pos ", stderr
);
2050 for (i
= 0; i
< bidi_cache_idx
; i
++)
2051 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].charpos
);
2052 fputs ("\n", stderr
);