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 int bidi_cache_idx
; /* next unused cache slot */
547 static int bidi_cache_last_idx
; /* slot of last cache hit */
550 bidi_cache_reset (void)
553 bidi_cache_last_idx
= -1;
557 bidi_cache_shrink (void)
559 if (bidi_cache_size
> BIDI_CACHE_CHUNK
)
561 bidi_cache_size
= BIDI_CACHE_CHUNK
* sizeof (struct bidi_it
);
562 bidi_cache
= (struct bidi_it
*) xrealloc (bidi_cache
, bidi_cache_size
);
568 bidi_cache_fetch_state (int idx
, struct bidi_it
*bidi_it
)
570 int current_scan_dir
= bidi_it
->scan_dir
;
572 if (idx
< 0 || idx
>= bidi_cache_idx
)
575 bidi_copy_it (bidi_it
, &bidi_cache
[idx
]);
576 bidi_it
->scan_dir
= current_scan_dir
;
577 bidi_cache_last_idx
= idx
;
580 /* Find a cached state with a given CHARPOS and resolved embedding
581 level less or equal to LEVEL. if LEVEL is -1, disregard the
582 resolved levels in cached states. DIR, if non-zero, means search
583 in that direction from the last cache hit. */
585 bidi_cache_search (int charpos
, int level
, int dir
)
591 if (charpos
< bidi_cache
[bidi_cache_last_idx
].charpos
)
593 else if (charpos
> bidi_cache
[bidi_cache_last_idx
].charpos
)
596 i_start
= bidi_cache_last_idx
;
600 i_start
= bidi_cache_idx
- 1;
605 /* Linear search for now; FIXME! */
606 for (i
= i_start
; i
>= 0; i
--)
607 if (bidi_cache
[i
].charpos
== charpos
608 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
613 for (i
= i_start
; i
< bidi_cache_idx
; i
++)
614 if (bidi_cache
[i
].charpos
== charpos
615 && (level
== -1 || bidi_cache
[i
].resolved_level
<= level
))
623 /* Find a cached state where the resolved level changes to a value
624 that is lower than LEVEL, and return its cache slot index. DIR is
625 the direction to search, starting with the last used cache slot.
626 BEFORE, if non-zero, means return the index of the slot that is
627 ``before'' the level change in the search direction. That is,
628 given the cached levels like this:
633 and assuming we are at the position cached at the slot marked with
634 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
635 index of slot B or A, depending whether BEFORE is, respectively,
638 bidi_cache_find_level_change (int level
, int dir
, int before
)
642 int i
= dir
? bidi_cache_last_idx
: bidi_cache_idx
- 1;
643 int incr
= before
? 1 : 0;
654 if (bidi_cache
[i
- incr
].resolved_level
>= 0
655 && bidi_cache
[i
- incr
].resolved_level
< level
)
662 while (i
< bidi_cache_idx
- incr
)
664 if (bidi_cache
[i
+ incr
].resolved_level
>= 0
665 && bidi_cache
[i
+ incr
].resolved_level
< level
)
676 bidi_cache_iterator_state (struct bidi_it
*bidi_it
, int resolved
)
680 /* We should never cache on backward scans. */
681 if (bidi_it
->scan_dir
== -1)
683 idx
= bidi_cache_search (bidi_it
->charpos
, -1, 1);
687 idx
= bidi_cache_idx
;
688 /* Enlarge the cache as needed. */
689 if (idx
>= bidi_cache_size
)
691 bidi_cache_size
+= BIDI_CACHE_CHUNK
* sizeof (struct bidi_it
);
693 (struct bidi_it
*) xrealloc (bidi_cache
, bidi_cache_size
);
695 /* Character positions should correspond to cache positions 1:1.
696 If we are outside the range of cached positions, the cache is
697 useless and must be reset. */
699 (bidi_it
->charpos
> bidi_cache
[idx
- 1].charpos
+ 1
700 || bidi_it
->charpos
< bidi_cache
[0].charpos
))
705 bidi_copy_it (&bidi_cache
[idx
], bidi_it
);
707 bidi_cache
[idx
].resolved_level
= -1;
708 bidi_cache
[idx
].new_paragraph
= 0;
712 /* Copy only the members which could have changed, to avoid
713 costly copying of the entire struct. */
714 bidi_cache
[idx
].type
= bidi_it
->type
;
715 bidi_check_type (bidi_it
->type
);
716 bidi_cache
[idx
].type_after_w1
= bidi_it
->type_after_w1
;
717 bidi_check_type (bidi_it
->type_after_w1
);
719 bidi_cache
[idx
].resolved_level
= bidi_it
->resolved_level
;
721 bidi_cache
[idx
].resolved_level
= -1;
722 bidi_cache
[idx
].invalid_levels
= bidi_it
->invalid_levels
;
723 bidi_cache
[idx
].invalid_rl_levels
= bidi_it
->invalid_rl_levels
;
724 bidi_cache
[idx
].next_for_neutral
= bidi_it
->next_for_neutral
;
725 bidi_cache
[idx
].next_for_ws
= bidi_it
->next_for_ws
;
726 bidi_cache
[idx
].ignore_bn_limit
= bidi_it
->ignore_bn_limit
;
729 bidi_cache_last_idx
= idx
;
730 if (idx
>= bidi_cache_idx
)
731 bidi_cache_idx
= idx
+ 1;
734 static INLINE bidi_type_t
735 bidi_cache_find (int charpos
, int level
, struct bidi_it
*bidi_it
)
737 int i
= bidi_cache_search (charpos
, level
, bidi_it
->scan_dir
);
741 bidi_dir_t current_scan_dir
= bidi_it
->scan_dir
;
743 bidi_copy_it (bidi_it
, &bidi_cache
[i
]);
744 bidi_cache_last_idx
= i
;
745 /* Don't let scan direction from from the cached state override
746 the current scan direction. */
747 bidi_it
->scan_dir
= current_scan_dir
;
748 return bidi_it
->type
;
755 bidi_peek_at_next_level (struct bidi_it
*bidi_it
)
757 if (bidi_cache_idx
== 0 || bidi_cache_last_idx
== -1)
759 return bidi_cache
[bidi_cache_last_idx
+ bidi_it
->scan_dir
].resolved_level
;
762 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
763 Value is the non-negative length of the paragraph separator
764 following the buffer position, -1 if position is at the beginning
765 of a new paragraph, or -2 if position is neither at beginning nor
766 at end of a paragraph. */
768 bidi_at_paragraph_end (EMACS_INT charpos
, EMACS_INT bytepos
)
770 /* FIXME: Why Fbuffer_local_value rather than just Fsymbol_value? */
772 Lisp_Object start_re
;
775 sep_re
= paragraph_separate_re
;
776 start_re
= paragraph_start_re
;
778 val
= fast_looking_at (sep_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
);
781 if (fast_looking_at (start_re
, charpos
, bytepos
, ZV
, ZV_BYTE
, Qnil
) >= 0)
790 /* Determine the start-of-run (sor) directional type given the two
791 embedding levels on either side of the run boundary. Also, update
792 the saved info about previously seen characters, since that info is
793 generally valid for a single level run. */
795 bidi_set_sor_type (struct bidi_it
*bidi_it
, int level_before
, int level_after
)
797 int higher_level
= level_before
> level_after
? level_before
: level_after
;
799 /* The prev_was_pdf gork is required for when we have several PDFs
800 in a row. In that case, we want to compute the sor type for the
801 next level run only once: when we see the first PDF. That's
802 because the sor type depends only on the higher of the two levels
803 that we find on the two sides of the level boundary (see UAX#9,
804 clause X10), and so we don't need to know the final embedding
805 level to which we descend after processing all the PDFs. */
806 if (!bidi_it
->prev_was_pdf
|| level_before
< level_after
)
807 /* FIXME: should the default sor direction be user selectable? */
808 bidi_it
->sor
= (higher_level
& 1) != 0 ? R2L
: L2R
;
809 if (level_before
> level_after
)
810 bidi_it
->prev_was_pdf
= 1;
812 bidi_it
->prev
.type
= UNKNOWN_BT
;
813 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
814 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
815 bidi_it
->prev_for_neutral
.type
= bidi_it
->sor
== R2L
? STRONG_R
: STRONG_L
;
816 bidi_it
->prev_for_neutral
.charpos
= bidi_it
->charpos
;
817 bidi_it
->prev_for_neutral
.bytepos
= bidi_it
->bytepos
;
818 bidi_it
->next_for_neutral
.type
= bidi_it
->next_for_neutral
.type_after_w1
=
819 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
820 bidi_it
->ignore_bn_limit
= 0; /* meaning it's unknown */
824 bidi_line_init (struct bidi_it
*bidi_it
)
826 bidi_it
->scan_dir
= 1; /* FIXME: do we need to have control on this? */
827 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
828 bidi_it
->level_stack
[0].override
= NEUTRAL_DIR
; /* X1 */
829 bidi_it
->invalid_levels
= 0;
830 bidi_it
->invalid_rl_levels
= -1;
831 bidi_it
->next_en_pos
= -1;
832 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
833 bidi_set_sor_type (bidi_it
,
834 bidi_it
->paragraph_dir
== R2L
? 1 : 0,
835 bidi_it
->level_stack
[0].level
); /* X10 */
840 /* Find the beginning of this paragraph by looking back in the buffer.
841 Value is the byte position of the paragraph's beginning. */
843 bidi_find_paragraph_start (EMACS_INT pos
, EMACS_INT pos_byte
)
845 Lisp_Object re
= paragraph_start_re
;
846 EMACS_INT limit
= ZV
, limit_byte
= ZV_BYTE
;
848 while (pos_byte
> BEGV_BYTE
849 && fast_looking_at (re
, pos
, pos_byte
, limit
, limit_byte
, Qnil
) < 0)
851 pos
= find_next_newline_no_quit (pos
- 1, -1);
852 pos_byte
= CHAR_TO_BYTE (pos
);
857 /* Determine the direction, a.k.a. base embedding level, of the
858 paragraph we are about to iterate through. If DIR is either L2R or
859 R2L, just use that. Otherwise, determine the paragraph direction
860 from the first strong character of the paragraph.
862 Note that this gives the paragraph separator the same direction as
863 the preceding paragraph, even though Emacs generally views the
864 separartor as not belonging to any paragraph. */
866 bidi_paragraph_init (bidi_dir_t dir
, struct bidi_it
*bidi_it
)
868 EMACS_INT bytepos
= bidi_it
->bytepos
;
870 /* Special case for an empty buffer. */
871 if (bytepos
== BEGV_BYTE
&& bytepos
== ZV_BYTE
)
873 /* We should never be called at EOB or before BEGV. */
874 else if (bytepos
>= ZV_BYTE
|| bytepos
< BEGV_BYTE
)
879 bidi_it
->paragraph_dir
= L2R
;
880 bidi_it
->new_paragraph
= 0;
884 bidi_it
->paragraph_dir
= R2L
;
885 bidi_it
->new_paragraph
= 0;
887 else if (dir
== NEUTRAL_DIR
) /* P2 */
893 if (!bidi_initialized
)
896 /* If we are inside a paragraph separator, we are just waiting
897 for the separator to be exhausted; use the previous paragraph
898 direction. But don't do that if we have been just reseated,
899 because we need to reinitialize below in that case. */
900 if (!bidi_it
->first_elt
901 && bidi_it
->charpos
< bidi_it
->separator_limit
)
904 /* If we are on a newline, get past it to where the next
905 paragraph might start. But don't do that at BEGV since then
906 we are potentially in a new paragraph that doesn't yet
908 pos
= bidi_it
->charpos
;
909 if (bytepos
> BEGV_BYTE
&& FETCH_CHAR (bytepos
) == '\n')
915 /* We are either at the beginning of a paragraph or in the
916 middle of it. Find where this paragraph starts. */
917 bytepos
= bidi_find_paragraph_start (pos
, bytepos
);
919 /* We should always be at the beginning of a new line at this
921 if (!(bytepos
== BEGV_BYTE
|| FETCH_CHAR (bytepos
- 1) == '\n'))
924 bidi_it
->separator_limit
= -1;
925 bidi_it
->new_paragraph
= 0;
926 ch
= FETCH_CHAR (bytepos
);
927 ch_len
= CHAR_BYTES (ch
);
928 pos
= BYTE_TO_CHAR (bytepos
);
929 type
= bidi_get_type (ch
, NEUTRAL_DIR
);
931 for (pos
++, bytepos
+= ch_len
;
932 /* NOTE: UAX#9 says to search only for L, AL, or R types of
933 characters, and ignore RLE, RLO, LRE, and LRO. However,
934 I'm not sure it makes sense to omit those 4; should try
935 with and without that to see the effect. */
936 (bidi_get_category (type
) != STRONG
)
937 || (bidi_ignore_explicit_marks_for_paragraph_level
938 && (type
== RLE
|| type
== RLO
939 || type
== LRE
|| type
== LRO
));
940 type
= bidi_get_type (ch
, NEUTRAL_DIR
))
942 if (type
== NEUTRAL_B
&& bidi_at_paragraph_end (pos
, bytepos
) >= -1)
944 if (bytepos
>= ZV_BYTE
)
946 /* Pretend there's a paragraph separator at end of buffer. */
950 FETCH_CHAR_ADVANCE (ch
, pos
, bytepos
);
952 if (type
== STRONG_R
|| type
== STRONG_AL
) /* P3 */
953 bidi_it
->paragraph_dir
= R2L
;
954 else if (type
== STRONG_L
)
955 bidi_it
->paragraph_dir
= L2R
;
960 /* Contrary to UAX#9 clause P3, we only default the paragraph
961 direction to L2R if we have no previous usable paragraph
963 if (bidi_it
->paragraph_dir
!= L2R
&& bidi_it
->paragraph_dir
!= R2L
)
964 bidi_it
->paragraph_dir
= L2R
; /* P3 and ``higher protocols'' */
965 if (bidi_it
->paragraph_dir
== R2L
)
966 bidi_it
->level_stack
[0].level
= 1;
968 bidi_it
->level_stack
[0].level
= 0;
970 bidi_line_init (bidi_it
);
973 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
976 bidi_set_paragraph_end (struct bidi_it
*bidi_it
)
978 bidi_it
->invalid_levels
= 0;
979 bidi_it
->invalid_rl_levels
= -1;
980 bidi_it
->stack_idx
= 0;
981 bidi_it
->resolved_level
= bidi_it
->level_stack
[0].level
;
984 /* Initialize the bidi iterator from buffer position CHARPOS. */
986 bidi_init_it (EMACS_INT charpos
, EMACS_INT bytepos
, struct bidi_it
*bidi_it
)
988 if (! bidi_initialized
)
990 bidi_it
->charpos
= charpos
;
991 bidi_it
->bytepos
= bytepos
;
992 bidi_it
->first_elt
= 1;
993 bidi_set_paragraph_end (bidi_it
);
994 bidi_it
->new_paragraph
= 1;
995 bidi_it
->separator_limit
= -1;
996 bidi_it
->type
= NEUTRAL_B
;
997 bidi_it
->type_after_w1
= NEUTRAL_B
;
998 bidi_it
->orig_type
= NEUTRAL_B
;
999 bidi_it
->prev_was_pdf
= 0;
1000 bidi_it
->prev
.type
= bidi_it
->prev
.type_after_w1
=
1001 bidi_it
->prev
.orig_type
= UNKNOWN_BT
;
1002 bidi_it
->last_strong
.type
= bidi_it
->last_strong
.type_after_w1
=
1003 bidi_it
->last_strong
.orig_type
= UNKNOWN_BT
;
1004 bidi_it
->next_for_neutral
.charpos
= -1;
1005 bidi_it
->next_for_neutral
.type
=
1006 bidi_it
->next_for_neutral
.type_after_w1
=
1007 bidi_it
->next_for_neutral
.orig_type
= UNKNOWN_BT
;
1008 bidi_it
->prev_for_neutral
.charpos
= -1;
1009 bidi_it
->prev_for_neutral
.type
=
1010 bidi_it
->prev_for_neutral
.type_after_w1
=
1011 bidi_it
->prev_for_neutral
.orig_type
= UNKNOWN_BT
;
1012 bidi_it
->sor
= L2R
; /* FIXME: should it be user-selectable? */
1013 bidi_cache_shrink ();
1016 /* Push the current embedding level and override status; reset the
1017 current level to LEVEL and the current override status to OVERRIDE. */
1019 bidi_push_embedding_level (struct bidi_it
*bidi_it
,
1020 int level
, bidi_dir_t override
)
1022 bidi_it
->stack_idx
++;
1023 if (bidi_it
->stack_idx
>= BIDI_MAXLEVEL
)
1025 bidi_it
->level_stack
[bidi_it
->stack_idx
].level
= level
;
1026 bidi_it
->level_stack
[bidi_it
->stack_idx
].override
= override
;
1029 /* Pop the embedding level and directional override status from the
1030 stack, and return the new level. */
1032 bidi_pop_embedding_level (struct bidi_it
*bidi_it
)
1034 /* UAX#9 says to ignore invalid PDFs. */
1035 if (bidi_it
->stack_idx
> 0)
1036 bidi_it
->stack_idx
--;
1037 return bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1040 /* Record in SAVED_INFO the information about the current character. */
1042 bidi_remember_char (struct bidi_saved_info
*saved_info
,
1043 struct bidi_it
*bidi_it
)
1045 saved_info
->charpos
= bidi_it
->charpos
;
1046 saved_info
->bytepos
= bidi_it
->bytepos
;
1047 saved_info
->type
= bidi_it
->type
;
1048 bidi_check_type (bidi_it
->type
);
1049 saved_info
->type_after_w1
= bidi_it
->type_after_w1
;
1050 bidi_check_type (bidi_it
->type_after_w1
);
1051 saved_info
->orig_type
= bidi_it
->orig_type
;
1052 bidi_check_type (bidi_it
->orig_type
);
1055 /* Resolve the type of a neutral character according to the type of
1056 surrounding strong text and the current embedding level. */
1057 static INLINE bidi_type_t
1058 bidi_resolve_neutral_1 (bidi_type_t prev_type
, bidi_type_t next_type
, int lev
)
1060 /* N1: European and Arabic numbers are treated as though they were R. */
1061 if (next_type
== WEAK_EN
|| next_type
== WEAK_AN
)
1062 next_type
= STRONG_R
;
1063 if (prev_type
== WEAK_EN
|| prev_type
== WEAK_AN
)
1064 prev_type
= STRONG_R
;
1066 if (next_type
== prev_type
) /* N1 */
1068 else if ((lev
& 1) == 0) /* N2 */
1075 bidi_explicit_dir_char (int c
)
1077 /* FIXME: this should be replaced with a lookup table with suitable
1078 bits set, like standard C ctype macros do. */
1079 return (c
== LRE_CHAR
|| c
== LRO_CHAR
1080 || c
== RLE_CHAR
|| c
== RLO_CHAR
|| c
== PDF_CHAR
);
1083 /* A helper function for bidi_resolve_explicit. It advances to the
1084 next character in logical order and determines the new embedding
1085 level and directional override, but does not take into account
1086 empty embeddings. */
1088 bidi_resolve_explicit_1 (struct bidi_it
*bidi_it
)
1094 bidi_dir_t override
;
1096 if (bidi_it
->bytepos
< BEGV_BYTE
/* after reseat to BEGV? */
1097 || bidi_it
->first_elt
)
1099 bidi_it
->first_elt
= 0;
1100 if (bidi_it
->charpos
< BEGV
)
1101 bidi_it
->charpos
= BEGV
;
1102 bidi_it
->bytepos
= CHAR_TO_BYTE (bidi_it
->charpos
);
1104 else if (bidi_it
->bytepos
< ZV_BYTE
) /* don't move at ZV */
1107 if (bidi_it
->ch_len
== 0)
1109 bidi_it
->bytepos
+= bidi_it
->ch_len
;
1112 current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
; /* X1 */
1113 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1114 new_level
= current_level
;
1116 /* in case it is a unibyte character (not yet implemented) */
1117 /* _fetch_multibyte_char_len = 1; */
1118 if (bidi_it
->bytepos
>= ZV_BYTE
)
1121 bidi_it
->ch_len
= 1;
1125 curchar
= FETCH_CHAR (bidi_it
->bytepos
);
1126 bidi_it
->ch_len
= CHAR_BYTES (curchar
);
1128 bidi_it
->ch
= curchar
;
1130 /* Don't apply directional override here, as all the types we handle
1131 below will not be affected by the override anyway, and we need
1132 the original type unaltered. The override will be applied in
1133 bidi_resolve_weak. */
1134 type
= bidi_get_type (curchar
, NEUTRAL_DIR
);
1135 bidi_it
->orig_type
= type
;
1136 bidi_check_type (bidi_it
->orig_type
);
1139 bidi_it
->prev_was_pdf
= 0;
1141 bidi_it
->type_after_w1
= UNKNOWN_BT
;
1147 bidi_it
->type_after_w1
= type
;
1148 bidi_check_type (bidi_it
->type_after_w1
);
1149 type
= WEAK_BN
; /* X9/Retaining */
1150 if (bidi_it
->ignore_bn_limit
<= 0)
1152 if (current_level
<= BIDI_MAXLEVEL
- 4)
1154 /* Compute the least odd embedding level greater than
1155 the current level. */
1156 new_level
= ((current_level
+ 1) & ~1) + 1;
1157 if (bidi_it
->type_after_w1
== RLE
)
1158 override
= NEUTRAL_DIR
;
1161 if (current_level
== BIDI_MAXLEVEL
- 4)
1162 bidi_it
->invalid_rl_levels
= 0;
1163 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1167 bidi_it
->invalid_levels
++;
1168 /* See the commentary about invalid_rl_levels below. */
1169 if (bidi_it
->invalid_rl_levels
< 0)
1170 bidi_it
->invalid_rl_levels
= 0;
1171 bidi_it
->invalid_rl_levels
++;
1174 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1175 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1180 bidi_it
->type_after_w1
= type
;
1181 bidi_check_type (bidi_it
->type_after_w1
);
1182 type
= WEAK_BN
; /* X9/Retaining */
1183 if (bidi_it
->ignore_bn_limit
<= 0)
1185 if (current_level
<= BIDI_MAXLEVEL
- 5)
1187 /* Compute the least even embedding level greater than
1188 the current level. */
1189 new_level
= ((current_level
+ 2) & ~1);
1190 if (bidi_it
->type_after_w1
== LRE
)
1191 override
= NEUTRAL_DIR
;
1194 bidi_push_embedding_level (bidi_it
, new_level
, override
);
1198 bidi_it
->invalid_levels
++;
1199 /* invalid_rl_levels counts invalid levels encountered
1200 while the embedding level was already too high for
1201 LRE/LRO, but not for RLE/RLO. That is because
1202 there may be exactly one PDF which we should not
1203 ignore even though invalid_levels is non-zero.
1204 invalid_rl_levels helps to know what PDF is
1206 if (bidi_it
->invalid_rl_levels
>= 0)
1207 bidi_it
->invalid_rl_levels
++;
1210 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1211 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1215 bidi_it
->type_after_w1
= type
;
1216 bidi_check_type (bidi_it
->type_after_w1
);
1217 type
= WEAK_BN
; /* X9/Retaining */
1218 if (bidi_it
->ignore_bn_limit
<= 0)
1220 if (!bidi_it
->invalid_rl_levels
)
1222 new_level
= bidi_pop_embedding_level (bidi_it
);
1223 bidi_it
->invalid_rl_levels
= -1;
1224 if (bidi_it
->invalid_levels
)
1225 bidi_it
->invalid_levels
--;
1226 /* else nothing: UAX#9 says to ignore invalid PDFs */
1228 if (!bidi_it
->invalid_levels
)
1229 new_level
= bidi_pop_embedding_level (bidi_it
);
1232 bidi_it
->invalid_levels
--;
1233 bidi_it
->invalid_rl_levels
--;
1236 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* W5/Retaining */
1237 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1245 bidi_it
->type
= type
;
1246 bidi_check_type (bidi_it
->type
);
1251 /* Given an iterator state in BIDI_IT, advance one character position
1252 in the buffer to the next character (in the logical order), resolve
1253 any explicit embeddings and directional overrides, and return the
1254 embedding level of the character after resolving explicit
1255 directives and ignoring empty embeddings. */
1257 bidi_resolve_explicit (struct bidi_it
*bidi_it
)
1259 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1260 int new_level
= bidi_resolve_explicit_1 (bidi_it
);
1262 if (prev_level
< new_level
1263 && bidi_it
->type
== WEAK_BN
1264 && bidi_it
->ignore_bn_limit
== 0 /* only if not already known */
1265 && bidi_it
->bytepos
< ZV_BYTE
/* not already at EOB */
1266 && bidi_explicit_dir_char (FETCH_CHAR (bidi_it
->bytepos
1267 + bidi_it
->ch_len
)))
1269 /* Avoid pushing and popping embedding levels if the level run
1270 is empty, as this breaks level runs where it shouldn't.
1271 UAX#9 removes all the explicit embedding and override codes,
1272 so empty embeddings disappear without a trace. We need to
1273 behave as if we did the same. */
1274 struct bidi_it saved_it
;
1275 int level
= prev_level
;
1277 bidi_copy_it (&saved_it
, bidi_it
);
1279 while (bidi_explicit_dir_char (FETCH_CHAR (bidi_it
->bytepos
1280 + bidi_it
->ch_len
)))
1282 level
= bidi_resolve_explicit_1 (bidi_it
);
1285 if (level
== prev_level
) /* empty embedding */
1286 saved_it
.ignore_bn_limit
= bidi_it
->charpos
+ 1;
1287 else /* this embedding is non-empty */
1288 saved_it
.ignore_bn_limit
= -1;
1290 bidi_copy_it (bidi_it
, &saved_it
);
1291 if (bidi_it
->ignore_bn_limit
> 0)
1293 /* We pushed a level, but we shouldn't have. Undo that. */
1294 if (!bidi_it
->invalid_rl_levels
)
1296 new_level
= bidi_pop_embedding_level (bidi_it
);
1297 bidi_it
->invalid_rl_levels
= -1;
1298 if (bidi_it
->invalid_levels
)
1299 bidi_it
->invalid_levels
--;
1301 if (!bidi_it
->invalid_levels
)
1302 new_level
= bidi_pop_embedding_level (bidi_it
);
1305 bidi_it
->invalid_levels
--;
1306 bidi_it
->invalid_rl_levels
--;
1311 if (bidi_it
->type
== NEUTRAL_B
) /* X8 */
1313 bidi_set_paragraph_end (bidi_it
);
1314 /* This is needed by bidi_resolve_weak below, and in L1. */
1315 bidi_it
->type_after_w1
= bidi_it
->type
;
1316 bidi_check_type (bidi_it
->type_after_w1
);
1322 /* Advance in the buffer, resolve weak types and return the type of
1323 the next character after weak type resolution. */
1325 bidi_resolve_weak (struct bidi_it
*bidi_it
)
1328 bidi_dir_t override
;
1329 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1330 int new_level
= bidi_resolve_explicit (bidi_it
);
1332 bidi_type_t type_of_next
;
1333 struct bidi_it saved_it
;
1335 type
= bidi_it
->type
;
1336 override
= bidi_it
->level_stack
[bidi_it
->stack_idx
].override
;
1338 if (type
== UNKNOWN_BT
1346 if (new_level
!= prev_level
1347 || bidi_it
->type
== NEUTRAL_B
)
1349 /* We've got a new embedding level run, compute the directional
1350 type of sor and initialize per-run variables (UAX#9, clause
1352 bidi_set_sor_type (bidi_it
, prev_level
, new_level
);
1354 else if (type
== NEUTRAL_S
|| type
== NEUTRAL_WS
1355 || type
== WEAK_BN
|| type
== STRONG_AL
)
1356 bidi_it
->type_after_w1
= type
; /* needed in L1 */
1357 bidi_check_type (bidi_it
->type_after_w1
);
1359 /* Level and directional override status are already recorded in
1360 bidi_it, and do not need any change; see X6. */
1361 if (override
== R2L
) /* X6 */
1363 else if (override
== L2R
)
1367 if (type
== WEAK_NSM
) /* W1 */
1369 /* Note that we don't need to consider the case where the
1370 prev character has its type overridden by an RLO or LRO,
1371 because then either the type of this NSM would have been
1372 also overridden, or the previous character is outside the
1373 current level run, and thus not relevant to this NSM.
1374 This is why NSM gets the type_after_w1 of the previous
1376 if (bidi_it
->prev
.type_after_w1
!= UNKNOWN_BT
1377 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1378 && bidi_it
->prev
.type_after_w1
!= NEUTRAL_B
)
1379 type
= bidi_it
->prev
.type_after_w1
;
1380 else if (bidi_it
->sor
== R2L
)
1382 else if (bidi_it
->sor
== L2R
)
1384 else /* shouldn't happen! */
1387 if (type
== WEAK_EN
/* W2 */
1388 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)
1390 else if (type
== STRONG_AL
) /* W3 */
1392 else if ((type
== WEAK_ES
/* W4 */
1393 && bidi_it
->prev
.type_after_w1
== WEAK_EN
1394 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1396 && ((bidi_it
->prev
.type_after_w1
== WEAK_EN
1397 && bidi_it
->prev
.orig_type
== WEAK_EN
)
1398 || bidi_it
->prev
.type_after_w1
== WEAK_AN
)))
1401 bidi_it
->bytepos
+ bidi_it
->ch_len
>= ZV_BYTE
1402 ? BIDI_EOB
: FETCH_CHAR (bidi_it
->bytepos
+ bidi_it
->ch_len
);
1403 type_of_next
= bidi_get_type (next_char
, override
);
1405 if (type_of_next
== WEAK_BN
1406 || bidi_explicit_dir_char (next_char
))
1408 bidi_copy_it (&saved_it
, bidi_it
);
1409 while (bidi_resolve_explicit (bidi_it
) == new_level
1410 && bidi_it
->type
== WEAK_BN
)
1412 type_of_next
= bidi_it
->type
;
1413 bidi_copy_it (bidi_it
, &saved_it
);
1416 /* If the next character is EN, but the last strong-type
1417 character is AL, that next EN will be changed to AN when
1418 we process it in W2 above. So in that case, this ES
1419 should not be changed into EN. */
1421 && type_of_next
== WEAK_EN
1422 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1424 else if (type
== WEAK_CS
)
1426 if (bidi_it
->prev
.type_after_w1
== WEAK_AN
1427 && (type_of_next
== WEAK_AN
1428 /* If the next character is EN, but the last
1429 strong-type character is AL, EN will be later
1430 changed to AN when we process it in W2 above.
1431 So in that case, this ES should not be
1433 || (type_of_next
== WEAK_EN
1434 && bidi_it
->last_strong
.type_after_w1
== STRONG_AL
)))
1436 else if (bidi_it
->prev
.type_after_w1
== WEAK_EN
1437 && type_of_next
== WEAK_EN
1438 && bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1442 else if (type
== WEAK_ET
/* W5: ET with EN before or after it */
1443 || type
== WEAK_BN
) /* W5/Retaining */
1445 if (bidi_it
->prev
.type_after_w1
== WEAK_EN
/* ET/BN w/EN before it */
1446 || bidi_it
->next_en_pos
> bidi_it
->charpos
)
1448 else /* W5: ET/BN with EN after it. */
1450 EMACS_INT en_pos
= bidi_it
->charpos
+ 1;
1453 bidi_it
->bytepos
+ bidi_it
->ch_len
>= ZV_BYTE
1454 ? BIDI_EOB
: FETCH_CHAR (bidi_it
->bytepos
+ bidi_it
->ch_len
);
1455 type_of_next
= bidi_get_type (next_char
, override
);
1457 if (type_of_next
== WEAK_ET
1458 || type_of_next
== WEAK_BN
1459 || bidi_explicit_dir_char (next_char
))
1461 bidi_copy_it (&saved_it
, bidi_it
);
1462 while (bidi_resolve_explicit (bidi_it
) == new_level
1463 && (bidi_it
->type
== WEAK_BN
1464 || bidi_it
->type
== WEAK_ET
))
1466 type_of_next
= bidi_it
->type
;
1467 en_pos
= bidi_it
->charpos
;
1468 bidi_copy_it (bidi_it
, &saved_it
);
1470 if (type_of_next
== WEAK_EN
)
1472 /* If the last strong character is AL, the EN we've
1473 found will become AN when we get to it (W2). */
1474 if (bidi_it
->last_strong
.type_after_w1
!= STRONG_AL
)
1477 /* Remember this EN position, to speed up processing
1479 bidi_it
->next_en_pos
= en_pos
;
1481 else if (type
== WEAK_BN
)
1482 type
= NEUTRAL_ON
; /* W6/Retaining */
1488 if (type
== WEAK_ES
|| type
== WEAK_ET
|| type
== WEAK_CS
/* W6 */
1490 && (bidi_it
->prev
.type_after_w1
== WEAK_CS
/* W6/Retaining */
1491 || bidi_it
->prev
.type_after_w1
== WEAK_ES
1492 || bidi_it
->prev
.type_after_w1
== WEAK_ET
)))
1495 /* Store the type we've got so far, before we clobber it with strong
1496 types in W7 and while resolving neutral types. But leave alone
1497 the original types that were recorded above, because we will need
1498 them for the L1 clause. */
1499 if (bidi_it
->type_after_w1
== UNKNOWN_BT
)
1500 bidi_it
->type_after_w1
= type
;
1501 bidi_check_type (bidi_it
->type_after_w1
);
1503 if (type
== WEAK_EN
) /* W7 */
1505 if ((bidi_it
->last_strong
.type_after_w1
== STRONG_L
)
1506 || (bidi_it
->last_strong
.type
== UNKNOWN_BT
&& bidi_it
->sor
== L2R
))
1510 bidi_it
->type
= type
;
1511 bidi_check_type (bidi_it
->type
);
1516 bidi_resolve_neutral (struct bidi_it
*bidi_it
)
1518 int prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1519 bidi_type_t type
= bidi_resolve_weak (bidi_it
);
1520 int current_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1522 if (!(type
== STRONG_R
1527 || type
== NEUTRAL_B
1528 || type
== NEUTRAL_S
1529 || type
== NEUTRAL_WS
1530 || type
== NEUTRAL_ON
))
1533 if (bidi_get_category (type
) == NEUTRAL
1534 || (type
== WEAK_BN
&& prev_level
== current_level
))
1536 if (bidi_it
->next_for_neutral
.type
!= UNKNOWN_BT
)
1537 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1538 bidi_it
->next_for_neutral
.type
,
1542 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1543 the assumption of batch-style processing; see clauses W4,
1544 W5, and especially N1, which require to look far forward
1545 (as well as back) in the buffer. May the fleas of a
1546 thousand camels infest the armpits of those who design
1547 supposedly general-purpose algorithms by looking at their
1548 own implementations, and fail to consider other possible
1550 struct bidi_it saved_it
;
1551 bidi_type_t next_type
;
1553 if (bidi_it
->scan_dir
== -1)
1556 bidi_copy_it (&saved_it
, bidi_it
);
1557 /* Scan the text forward until we find the first non-neutral
1558 character, and then use that to resolve the neutral we
1559 are dealing with now. We also cache the scanned iterator
1560 states, to salvage some of the effort later. */
1561 bidi_cache_iterator_state (bidi_it
, 0);
1563 /* Record the info about the previous character, so that
1564 it will be cached below with this state. */
1565 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1566 && bidi_it
->type
!= WEAK_BN
)
1567 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1568 type
= bidi_resolve_weak (bidi_it
);
1569 /* Paragraph separators have their levels fully resolved
1570 at this point, so cache them as resolved. */
1571 bidi_cache_iterator_state (bidi_it
, type
== NEUTRAL_B
);
1572 /* FIXME: implement L1 here, by testing for a newline and
1573 resetting the level for any sequence of whitespace
1574 characters adjacent to it. */
1575 } while (!(type
== NEUTRAL_B
1577 && bidi_get_category (type
) != NEUTRAL
)
1578 /* This is all per level run, so stop when we
1579 reach the end of this level run. */
1580 || bidi_it
->level_stack
[bidi_it
->stack_idx
].level
!=
1583 bidi_remember_char (&saved_it
.next_for_neutral
, bidi_it
);
1594 /* N1: ``European and Arabic numbers are treated as
1595 though they were R.'' */
1596 next_type
= STRONG_R
;
1597 saved_it
.next_for_neutral
.type
= STRONG_R
;
1600 if (!bidi_explicit_dir_char (bidi_it
->ch
))
1601 abort (); /* can't happen: BNs are skipped */
1604 /* Marched all the way to the end of this level run.
1605 We need to use the eor type, whose information is
1606 stored by bidi_set_sor_type in the prev_for_neutral
1608 if (saved_it
.type
!= WEAK_BN
1609 || bidi_get_category (bidi_it
->prev
.type_after_w1
) == NEUTRAL
)
1611 next_type
= bidi_it
->prev_for_neutral
.type
;
1612 saved_it
.next_for_neutral
.type
= next_type
;
1613 bidi_check_type (next_type
);
1617 /* This is a BN which does not adjoin neutrals.
1618 Leave its type alone. */
1619 bidi_copy_it (bidi_it
, &saved_it
);
1620 return bidi_it
->type
;
1626 type
= bidi_resolve_neutral_1 (saved_it
.prev_for_neutral
.type
,
1627 next_type
, current_level
);
1628 saved_it
.type
= type
;
1629 bidi_check_type (type
);
1630 bidi_copy_it (bidi_it
, &saved_it
);
1636 /* Given an iterator state in BIDI_IT, advance one character position
1637 in the buffer to the next character (in the logical order), resolve
1638 the bidi type of that next character, and return that type. */
1640 bidi_type_of_next_char (struct bidi_it
*bidi_it
)
1644 /* This should always be called during a forward scan. */
1645 if (bidi_it
->scan_dir
!= 1)
1648 /* Reset the limit until which to ignore BNs if we step out of the
1649 area where we found only empty levels. */
1650 if ((bidi_it
->ignore_bn_limit
> 0
1651 && bidi_it
->ignore_bn_limit
<= bidi_it
->charpos
)
1652 || (bidi_it
->ignore_bn_limit
== -1
1653 && !bidi_explicit_dir_char (bidi_it
->ch
)))
1654 bidi_it
->ignore_bn_limit
= 0;
1656 type
= bidi_resolve_neutral (bidi_it
);
1661 /* Given an iterator state BIDI_IT, advance one character position in
1662 the buffer to the next character (in the logical order), resolve
1663 the embedding and implicit levels of that next character, and
1664 return the resulting level. */
1666 bidi_level_of_next_char (struct bidi_it
*bidi_it
)
1669 int level
, prev_level
= -1;
1670 struct bidi_saved_info next_for_neutral
;
1672 if (bidi_it
->scan_dir
== 1)
1674 /* There's no sense in trying to advance if we hit end of text. */
1675 if (bidi_it
->bytepos
>= ZV_BYTE
)
1676 return bidi_it
->resolved_level
;
1678 /* Record the info about the previous character. */
1679 if (bidi_it
->type_after_w1
!= WEAK_BN
/* W1/Retaining */
1680 && bidi_it
->type
!= WEAK_BN
)
1681 bidi_remember_char (&bidi_it
->prev
, bidi_it
);
1682 if (bidi_it
->type_after_w1
== STRONG_R
1683 || bidi_it
->type_after_w1
== STRONG_L
1684 || bidi_it
->type_after_w1
== STRONG_AL
)
1685 bidi_remember_char (&bidi_it
->last_strong
, bidi_it
);
1686 /* FIXME: it sounds like we don't need both prev and
1687 prev_for_neutral members, but I'm leaving them both for now. */
1688 if (bidi_it
->type
== STRONG_R
|| bidi_it
->type
== STRONG_L
1689 || bidi_it
->type
== WEAK_EN
|| bidi_it
->type
== WEAK_AN
)
1690 bidi_remember_char (&bidi_it
->prev_for_neutral
, bidi_it
);
1692 /* If we overstepped the characters used for resolving neutrals
1693 and whitespace, invalidate their info in the iterator. */
1694 if (bidi_it
->charpos
>= bidi_it
->next_for_neutral
.charpos
)
1695 bidi_it
->next_for_neutral
.type
= UNKNOWN_BT
;
1696 if (bidi_it
->next_en_pos
>= 0
1697 && bidi_it
->charpos
>= bidi_it
->next_en_pos
)
1698 bidi_it
->next_en_pos
= -1;
1699 if (bidi_it
->next_for_ws
.type
!= UNKNOWN_BT
1700 && bidi_it
->charpos
>= bidi_it
->next_for_ws
.charpos
)
1701 bidi_it
->next_for_ws
.type
= UNKNOWN_BT
;
1703 /* This must be taken before we fill the iterator with the info
1704 about the next char. If we scan backwards, the iterator
1705 state must be already cached, so there's no need to know the
1706 embedding level of the previous character, since we will be
1707 returning to our caller shortly. */
1708 prev_level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1710 next_for_neutral
= bidi_it
->next_for_neutral
;
1712 /* Perhaps it is already cached. */
1713 type
= bidi_cache_find (bidi_it
->charpos
+ bidi_it
->scan_dir
, -1, bidi_it
);
1714 if (type
!= UNKNOWN_BT
)
1716 /* Don't lose the information for resolving neutrals! The
1717 cached states could have been cached before their
1718 next_for_neutral member was computed. If we are on our way
1719 forward, we can simply take the info from the previous
1721 if (bidi_it
->scan_dir
== 1
1722 && bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1723 bidi_it
->next_for_neutral
= next_for_neutral
;
1725 /* If resolved_level is -1, it means this state was cached
1726 before it was completely resolved, so we cannot return
1728 if (bidi_it
->resolved_level
!= -1)
1729 return bidi_it
->resolved_level
;
1731 if (bidi_it
->scan_dir
== -1)
1732 /* If we are going backwards, the iterator state is already cached
1733 from previous scans, and should be fully resolved. */
1736 if (type
== UNKNOWN_BT
)
1737 type
= bidi_type_of_next_char (bidi_it
);
1739 if (type
== NEUTRAL_B
)
1740 return bidi_it
->resolved_level
;
1742 level
= bidi_it
->level_stack
[bidi_it
->stack_idx
].level
;
1743 if ((bidi_get_category (type
) == NEUTRAL
/* && type != NEUTRAL_B */)
1744 || (type
== WEAK_BN
&& prev_level
== level
))
1746 if (bidi_it
->next_for_neutral
.type
== UNKNOWN_BT
)
1749 /* If the cached state shows a neutral character, it was not
1750 resolved by bidi_resolve_neutral, so do it now. */
1751 type
= bidi_resolve_neutral_1 (bidi_it
->prev_for_neutral
.type
,
1752 bidi_it
->next_for_neutral
.type
,
1756 if (!(type
== STRONG_R
1760 || type
== WEAK_AN
))
1762 bidi_it
->type
= type
;
1763 bidi_check_type (bidi_it
->type
);
1765 /* For L1 below, we need to know, for each WS character, whether
1766 it belongs to a sequence of WS characters preceeding a newline
1767 or a TAB or a paragraph separator. */
1768 if (bidi_it
->orig_type
== NEUTRAL_WS
1769 && bidi_it
->next_for_ws
.type
== UNKNOWN_BT
)
1772 int clen
= bidi_it
->ch_len
;
1773 EMACS_INT bpos
= bidi_it
->bytepos
;
1774 EMACS_INT cpos
= bidi_it
->charpos
;
1778 /*_fetch_multibyte_char_len = 1;*/
1779 ch
= bpos
+ clen
>= ZV_BYTE
? BIDI_EOB
: FETCH_CHAR (bpos
+ clen
);
1782 clen
= (ch
== BIDI_EOB
? 1 : CHAR_BYTES (ch
));
1783 if (ch
== '\n' || ch
== BIDI_EOB
/* || ch == LINESEP_CHAR */)
1786 chtype
= bidi_get_type (ch
, NEUTRAL_DIR
);
1787 } while (chtype
== NEUTRAL_WS
|| chtype
== WEAK_BN
1788 || bidi_explicit_dir_char (ch
)); /* L1/Retaining */
1789 bidi_it
->next_for_ws
.type
= chtype
;
1790 bidi_check_type (bidi_it
->next_for_ws
.type
);
1791 bidi_it
->next_for_ws
.charpos
= cpos
;
1792 bidi_it
->next_for_ws
.bytepos
= bpos
;
1795 /* Resolve implicit levels, with a twist: PDFs get the embedding
1796 level of the enbedding they terminate. See below for the
1798 if (bidi_it
->orig_type
== PDF
1799 /* Don't do this if this formatting code didn't change the
1800 embedding level due to invalid or empty embeddings. */
1801 && prev_level
!= level
)
1803 /* Don't look in UAX#9 for the reason for this: it's our own
1804 private quirk. The reason is that we want the formatting
1805 codes to be delivered so that they bracket the text of their
1806 embedding. For example, given the text
1810 we want it to be displayed as
1818 which will result because we bump up the embedding level as
1819 soon as we see the RLO and pop it as soon as we see the PDF,
1820 so RLO itself has the same embedding level as "teST", and
1821 thus would be normally delivered last, just before the PDF.
1822 The switch below fiddles with the level of PDF so that this
1823 ugly side effect does not happen.
1825 (This is, of course, only important if the formatting codes
1826 are actually displayed, but Emacs does need to display them
1827 if the user wants to.) */
1830 else if (bidi_it
->orig_type
== NEUTRAL_B
/* L1 */
1831 || bidi_it
->orig_type
== NEUTRAL_S
1832 || bidi_it
->ch
== '\n' || bidi_it
->ch
== BIDI_EOB
1833 /* || bidi_it->ch == LINESEP_CHAR */
1834 || (bidi_it
->orig_type
== NEUTRAL_WS
1835 && (bidi_it
->next_for_ws
.type
== NEUTRAL_B
1836 || bidi_it
->next_for_ws
.type
== NEUTRAL_S
)))
1837 level
= bidi_it
->level_stack
[0].level
;
1838 else if ((level
& 1) == 0) /* I1 */
1840 if (type
== STRONG_R
)
1842 else if (type
== WEAK_EN
|| type
== WEAK_AN
)
1847 if (type
== STRONG_L
|| type
== WEAK_EN
|| type
== WEAK_AN
)
1851 bidi_it
->resolved_level
= level
;
1855 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
1856 non-zero, we are at the end of a level, and we need to prepare to
1857 resume the scan of the lower level.
1859 If this level's other edge is cached, we simply jump to it, filling
1860 the iterator structure with the iterator state on the other edge.
1861 Otherwise, we walk the buffer until we come back to the same level
1864 Note: we are not talking here about a ``level run'' in the UAX#9
1865 sense of the term, but rather about a ``level'' which includes
1866 all the levels higher than it. In other words, given the levels
1869 11111112222222333333334443343222222111111112223322111
1872 and assuming we are at point A scanning left to right, this
1873 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
1876 bidi_find_other_level_edge (struct bidi_it
*bidi_it
, int level
, int end_flag
)
1878 int dir
= end_flag
? -bidi_it
->scan_dir
: bidi_it
->scan_dir
;
1881 /* Try the cache first. */
1882 if ((idx
= bidi_cache_find_level_change (level
, dir
, end_flag
)) >= 0)
1883 bidi_cache_fetch_state (idx
, bidi_it
);
1889 abort (); /* if we are at end of level, its edges must be cached */
1891 bidi_cache_iterator_state (bidi_it
, 1);
1893 new_level
= bidi_level_of_next_char (bidi_it
);
1894 bidi_cache_iterator_state (bidi_it
, 1);
1895 } while (new_level
>= level
);
1900 bidi_move_to_visually_next (struct bidi_it
*bidi_it
)
1902 int old_level
, new_level
, next_level
;
1903 struct bidi_it sentinel
;
1905 if (bidi_it
->scan_dir
== 0)
1907 bidi_it
->scan_dir
= 1; /* default to logical order */
1910 /* If we just passed a newline, initialize for the next line. */
1911 if (!bidi_it
->first_elt
&& bidi_it
->orig_type
== NEUTRAL_B
)
1912 bidi_line_init (bidi_it
);
1914 /* Prepare the sentinel iterator state. */
1915 if (bidi_cache_idx
== 0)
1917 bidi_copy_it (&sentinel
, bidi_it
);
1918 if (bidi_it
->first_elt
)
1920 sentinel
.charpos
--; /* cached charpos needs to be monotonic */
1922 sentinel
.ch
= '\n'; /* doesn't matter, but why not? */
1923 sentinel
.ch_len
= 1;
1927 old_level
= bidi_it
->resolved_level
;
1928 new_level
= bidi_level_of_next_char (bidi_it
);
1930 /* Reordering of resolved levels (clause L2) is implemented by
1931 jumping to the other edge of the level and flipping direction of
1932 scanning the text whenever we find a level change. */
1933 if (new_level
!= old_level
)
1935 int ascending
= new_level
> old_level
;
1936 int level_to_search
= ascending
? old_level
+ 1 : old_level
;
1937 int incr
= ascending
? 1 : -1;
1938 int expected_next_level
= old_level
+ incr
;
1940 /* If we don't have anything cached yet, we need to cache the
1941 sentinel state, since we'll need it to record where to jump
1942 when the last non-base level is exhausted. */
1943 if (bidi_cache_idx
== 0)
1944 bidi_cache_iterator_state (&sentinel
, 1);
1945 /* Jump (or walk) to the other edge of this level. */
1946 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
1947 /* Switch scan direction and peek at the next character in the
1949 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
1951 /* The following loop handles the case where the resolved level
1952 jumps by more than one. This is typical for numbers inside a
1953 run of text with left-to-right embedding direction, but can
1954 also happen in other situations. In those cases the decision
1955 where to continue after a level change, and in what direction,
1956 is tricky. For example, given a text like below:
1961 (where the numbers below the text show the resolved levels),
1962 the result of reordering according to UAX#9 should be this:
1966 This is implemented by the loop below which flips direction
1967 and jumps to the other edge of the level each time it finds
1968 the new level not to be the expected one. The expected level
1969 is always one more or one less than the previous one. */
1970 next_level
= bidi_peek_at_next_level (bidi_it
);
1971 while (next_level
!= expected_next_level
)
1973 expected_next_level
+= incr
;
1974 level_to_search
+= incr
;
1975 bidi_find_other_level_edge (bidi_it
, level_to_search
, !ascending
);
1976 bidi_it
->scan_dir
= -bidi_it
->scan_dir
;
1977 next_level
= bidi_peek_at_next_level (bidi_it
);
1980 /* Finally, deliver the next character in the new direction. */
1981 next_level
= bidi_level_of_next_char (bidi_it
);
1984 /* Take note when we have just processed the newline that precedes
1985 the end of the paragraph. The next time we are about to be
1986 called, set_iterator_to_next will automatically reinit the
1987 paragraph direction, if needed. We do this at the newline before
1988 the paragraph separator, because the next character might not be
1989 the first character of the next paragraph, due to the bidi
1990 reordering, whereas we _must_ know the paragraph base direction
1991 _before_ we process the paragraph's text, since the base
1992 direction affects the reordering. */
1993 if (bidi_it
->scan_dir
== 1
1994 && bidi_it
->orig_type
== NEUTRAL_B
1995 && bidi_it
->bytepos
< ZV_BYTE
)
1998 bidi_at_paragraph_end (bidi_it
->charpos
+ 1,
1999 bidi_it
->bytepos
+ bidi_it
->ch_len
);
2002 bidi_it
->new_paragraph
= 1;
2003 /* Record the buffer position of the last character of the
2004 paragraph separator. */
2005 bidi_it
->separator_limit
= bidi_it
->charpos
+ 1 + sep_len
;
2009 if (bidi_it
->scan_dir
== 1 && bidi_cache_idx
)
2011 /* If we are at paragraph's base embedding level and beyond the
2012 last cached position, the cache's job is done and we can
2014 if (bidi_it
->resolved_level
== bidi_it
->level_stack
[0].level
2015 && bidi_it
->charpos
> bidi_cache
[bidi_cache_idx
- 1].charpos
)
2016 bidi_cache_reset ();
2017 /* But as long as we are caching during forward scan, we must
2018 cache each state, or else the cache integrity will be
2019 compromised: it assumes cached states correspond to buffer
2022 bidi_cache_iterator_state (bidi_it
, 1);
2026 /* This is meant to be called from within the debugger, whenever you
2027 wish to examine the cache contents. */
2029 bidi_dump_cached_states (void)
2034 if (bidi_cache_idx
== 0)
2036 fprintf (stderr
, "The cache is empty.\n");
2039 fprintf (stderr
, "Total of %d state%s in cache:\n",
2040 bidi_cache_idx
, bidi_cache_idx
== 1 ? "" : "s");
2042 for (i
= bidi_cache
[bidi_cache_idx
- 1].charpos
; i
> 0; i
/= 10)
2044 fputs ("ch ", stderr
);
2045 for (i
= 0; i
< bidi_cache_idx
; i
++)
2046 fprintf (stderr
, "%*c", ndigits
, bidi_cache
[i
].ch
);
2047 fputs ("\n", stderr
);
2048 fputs ("lvl ", stderr
);
2049 for (i
= 0; i
< bidi_cache_idx
; i
++)
2050 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].resolved_level
);
2051 fputs ("\n", stderr
);
2052 fputs ("pos ", stderr
);
2053 for (i
= 0; i
< bidi_cache_idx
; i
++)
2054 fprintf (stderr
, "%*d", ndigits
, bidi_cache
[i
].charpos
);
2055 fputs ("\n", stderr
);