| blob | a25976dcc015e36154f4e4846ead7433807e0594 |
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
27 string.
29 The main entry point is bidi_move_to_visually_next. Each time it
30 is called, it finds the next character in the visual order, and
31 returns its information in a special structure. The caller is then
32 expected to process this character for display or any other
33 purposes, and call bidi_move_to_visually_next for the next
34 character. See the comments in bidi_move_to_visually_next for more
35 details about its algorithm that finds the next visual-order
36 character by resolving their levels on the fly.
38 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
41 argument character.
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". */
52 #ifdef HAVE_CONFIG_H
53 #include <config.h>
54 #endif
56 #include <stdio.h>
58 #ifdef HAVE_STRING_H
59 #include <string.h>
60 #endif
62 #include <setjmp.h>
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
82 #define BIDI_EOB -1
85 /* Local data structures. (Look in dispextern.h for the rest.) */
87 /* What we need to know about the current paragraph. */
93 };
95 /* Data type for describing the bidirectional character categories. */
97 UNKNOWN_BC,
98 NEUTRAL,
99 WEAK,
100 STRONG
108 static void
110 {
111 /* FIXME: This should come from the Unicode Database. */
114 bidi_type_t type;
415 }
417 /* Return the bidi type of a character CH, subject to the current
418 directional OVERRIDE. */
419 static INLINE bidi_type_t
421 {
422 bidi_type_t default_type;
435 {
436 /* Although UAX#9 does not tell, it doesn't make sense to
437 override NEUTRAL_B and LRM/RLM characters. */
447 {
456 else
458 }
459 }
460 }
462 void
464 {
467 }
469 /* Given a bidi TYPE of a character, return its category. */
470 static INLINE bidi_category_t
472 {
474 {
501 }
502 }
504 /* Return the mirrored character of C, if any.
506 Note: The conditions in UAX#9 clause L4 must be tested by the
507 caller. */
508 /* FIXME: exceedingly temporary! Should consult the Unicode database
509 of character properties. */
510 int
512 {
517 {
521 }
523 }
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. */
529 {
532 /* Copy everything except the level stack and beyond. */
535 /* Copy the active part of the level stack. */
539 }
541 /* Caching the bidi iterator states. */
543 #define BIDI_CACHE_CHUNK 200
552 {
555 }
559 {
561 {
563 bidi_cache =
565 }
567 }
571 {
580 }
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. */
588 {
592 {
599 else
600 {
603 }
606 {
607 /* Linear search for now; FIXME! */
612 }
613 else
614 {
619 }
620 }
623 }
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:
632 1122333442211
633 AB C
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,
638 non-zero or zero. */
639 static int
641 {
643 {
653 {
655 {
659 i--;
660 }
661 }
662 else
663 {
665 {
669 i++;
670 }
671 }
672 }
675 }
679 {
682 /* We should never cache on backward scans. */
688 {
690 /* Enlarge the cache as needed. */
692 {
694 bidi_cache =
696 }
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. */
703 {
706 }
710 }
711 else
712 {
713 /* Copy only the members which could have changed, to avoid
714 costly copying of the entire struct. */
721 else
728 }
733 }
735 static INLINE bidi_type_t
737 {
741 {
746 /* Don't let scan direction from from the cached state override
747 the current scan direction. */
750 }
753 }
757 {
761 }
763 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
764 Value is the non-negative length of the paragraph separator
765 following the buffer position, -1 if position is at the beginning
766 of a new paragraph, or -2 if position is neither at beginning nor
767 at end of a paragraph. */
768 static EMACS_INT
770 {
771 /* FIXME: Why Fbuffer_local_value rather than just Fsymbol_value? */
772 Lisp_Object sep_re;
773 Lisp_Object start_re;
774 EMACS_INT val;
781 {
784 else
786 }
789 }
791 /* Determine the start-of-run (sor) directional type given the two
792 embedding levels on either side of the run boundary. Also, update
793 the saved info about previously seen characters, since that info is
794 generally valid for a single level run. */
797 {
800 /* The prev_was_pdf gork is required for when we have several PDFs
801 in a row. In that case, we want to compute the sor type for the
802 next level run only once: when we see the first PDF. That's
803 because the sor type depends only on the higher of the two levels
804 that we find on the two sides of the level boundary (see UAX#9,
805 clause X10), and so we don't need to know the final embedding
806 level to which we descend after processing all the PDFs. */
808 /* FIXME: should the default sor direction be user selectable? */
822 }
824 static void
826 {
839 }
841 /* Find the beginning of this paragraph by looking back in the buffer.
842 Value is the byte position of the paragraph's beginning. */
843 static EMACS_INT
845 {
851 {
854 }
856 }
858 /* Determine the direction, a.k.a. base embedding level, of the
859 paragraph we are about to iterate through. If DIR is either L2R or
860 R2L, just use that. Otherwise, determine the paragraph direction
861 from the first strong character of the paragraph.
863 Note that this gives the paragraph separator the same direction as
864 the preceding paragraph, even though Emacs generally views the
865 separartor as not belonging to any paragraph. */
866 void
868 {
871 /* Special case for an empty buffer. */
874 /* We should never be called at EOB or before BEGV. */
879 {
882 }
884 {
887 }
889 {
891 EMACS_INT pos;
892 bidi_type_t type;
897 /* If we are inside a paragraph separator, we are just waiting
898 for the separator to be exhausted; use the previous paragraph
899 direction. But don't do that if we have been just reseated,
900 because we need to reinitialize below in that case. */
905 /* If we are on a newline, get past it to where the next
906 paragraph might start. But don't do that at BEGV since then
907 we are potentially in a new paragraph that doesn't yet
908 exist. */
911 {
912 bytepos++;
913 pos++;
914 }
916 /* We are either at the beginning of a paragraph or in the
917 middle of it. Find where this paragraph starts. */
928 /* NOTE: UAX#9 says to search only for L, AL, or R types of
929 characters, and ignore RLE, RLO, LRE, and LRO. However,
930 I'm not sure it makes sense to omit those 4; should try
931 with and without that to see the effect. */
933 || (bidi_ignore_explicit_marks_for_paragraph_level
937 {
941 {
942 /* Pretend there's a paragraph separator at end of buffer. */
945 }
947 }
952 }
953 else
956 /* Contrary to UAX#9 clause P3, we only default the paragraph
957 direction to L2R if we have no previous usable paragraph
958 direction. */
963 else
967 }
969 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
970 end. */
973 {
978 }
980 /* Initialize the bidi iterator from buffer position CHARPOS. */
981 void
983 {
1010 }
1012 /* Push the current embedding level and override status; reset the
1013 current level to LEVEL and the current override status to OVERRIDE. */
1017 {
1023 }
1025 /* Pop the embedding level and directional override status from the
1026 stack, and return the new level. */
1029 {
1030 /* UAX#9 says to ignore invalid PDFs. */
1034 }
1036 /* Record in SAVED_INFO the information about the current character. */
1040 {
1049 }
1051 /* Resolve the type of a neutral character according to the type of
1052 surrounding strong text and the current embedding level. */
1053 static INLINE bidi_type_t
1055 {
1056 /* N1: European and Arabic numbers are treated as though they were R. */
1066 else
1068 }
1072 {
1073 /* FIXME: this should be replaced with a lookup table with suitable
1074 bits set, like standard C ctype macros do. */
1077 }
1079 /* A helper function for bidi_resolve_explicit. It advances to the
1080 next character in logical order and determines the new embedding
1081 level and directional override, but does not take into account
1082 empty embeddings. */
1083 static int
1085 {
1087 bidi_type_t type;
1090 bidi_dir_t override;
1094 {
1099 }
1101 {
1106 }
1112 /* in case it is a unibyte character (not yet implemented) */
1113 /* _fetch_multibyte_char_len = 1; */
1115 {
1118 }
1119 else
1120 {
1123 }
1126 /* Don't apply directional override here, as all the types we handle
1127 below will not be affected by the override anyway, and we need
1128 the original type unaltered. The override will be applied in
1129 bidi_resolve_weak. */
1140 {
1147 {
1149 {
1150 /* Compute the least odd embedding level greater than
1151 the current level. */
1155 else
1160 }
1161 else
1162 {
1164 /* See the commentary about invalid_rl_levels below. */
1168 }
1169 }
1180 {
1182 {
1183 /* Compute the least even embedding level greater than
1184 the current level. */
1188 else
1191 }
1192 else
1193 {
1195 /* invalid_rl_levels counts invalid levels encountered
1196 while the embedding level was already too high for
1197 LRE/LRO, but not for RLE/RLO. That is because
1198 there may be exactly one PDF which we should not
1199 ignore even though invalid_levels is non-zero.
1200 invalid_rl_levels helps to know what PDF is
1201 that. */
1204 }
1205 }
1215 {
1217 {
1222 /* else nothing: UAX#9 says to ignore invalid PDFs */
1223 }
1226 else
1227 {
1230 }
1231 }
1237 /* Nothing. */
1239 }
1245 }
1247 /* Given an iterator state in BIDI_IT, advance one character position
1248 in the buffer to the next character (in the logical order), resolve
1249 any explicit embeddings and directional overrides, and return the
1250 embedding level of the character after resolving explicit
1251 directives and ignoring empty embeddings. */
1252 static int
1254 {
1264 {
1265 /* Avoid pushing and popping embedding levels if the level run
1266 is empty, as this breaks level runs where it shouldn't.
1267 UAX#9 removes all the explicit embedding and override codes,
1268 so empty embeddings disappear without a trace. We need to
1269 behave as if we did the same. */
1277 {
1279 }
1288 {
1289 /* We pushed a level, but we shouldn't have. Undo that. */
1291 {
1296 }
1299 else
1300 {
1303 }
1304 }
1305 }
1308 {
1310 /* This is needed by bidi_resolve_weak below, and in L1. */
1313 }
1316 }
1318 /* Advance in the buffer, resolve weak types and return the type of
1319 the next character after weak type resolution. */
1320 static bidi_type_t
1322 {
1323 bidi_type_t type;
1324 bidi_dir_t override;
1328 bidi_type_t type_of_next;
1344 {
1345 /* We've got a new embedding level run, compute the directional
1346 type of sor and initialize per-run variables (UAX#9, clause
1347 X10). */
1349 }
1355 /* Level and directional override status are already recorded in
1356 bidi_it, and do not need any change; see X6. */
1361 else
1362 {
1364 {
1365 /* Note that we don't need to consider the case where the
1366 prev character has its type overridden by an RLO or LRO,
1367 because then either the type of this NSM would have been
1368 also overridden, or the previous character is outside the
1369 current level run, and thus not relevant to this NSM.
1370 This is why NSM gets the type_after_w1 of the previous
1371 character. */
1373 /* if type_after_w1 is NEUTRAL_B, this NSM is at sor */
1382 }
1395 {
1396 next_char =
1403 {
1407 ;
1410 }
1412 /* If the next character is EN, but the last strong-type
1413 character is AL, that next EN will be changed to AN when
1414 we process it in W2 above. So in that case, this ES
1415 should not be changed into EN. */
1421 {
1424 /* If the next character is EN, but the last
1425 strong-type character is AL, EN will be later
1426 changed to AN when we process it in W2 above.
1427 So in that case, this ES should not be
1428 changed into EN. */
1436 }
1437 }
1440 {
1445 {
1448 next_char =
1456 {
1461 ;
1465 }
1467 {
1468 /* If the last strong character is AL, the EN we've
1469 found will become AN when we get to it (W2). */
1471 {
1473 /* Remember this EN position, to speed up processing
1474 of the next ETs. */
1476 }
1479 }
1480 }
1481 }
1482 }
1491 /* Store the type we've got so far, before we clobber it with strong
1492 types in W7 and while resolving neutral types. But leave alone
1493 the original types that were recorded above, because we will need
1494 them for the L1 clause. */
1500 {
1504 }
1509 }
1511 static bidi_type_t
1513 {
1531 {
1535 current_level);
1536 else
1537 {
1538 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1539 the assumption of batch-style processing; see clauses W4,
1540 W5, and especially N1, which require to look far forward
1541 (as well as back) in the buffer. May the fleas of a
1542 thousand camels infest the armpits of those who design
1543 supposedly general-purpose algorithms by looking at their
1544 own implementations, and fail to consider other possible
1545 implementations! */
1547 bidi_type_t next_type;
1553 /* Scan the text forward until we find the first non-neutral
1554 character, and then use that to resolve the neutral we
1555 are dealing with now. We also cache the scanned iterator
1556 states, to salvage some of the effort later. */
1559 /* Record the info about the previous character, so that
1560 it will be cached below with this state. */
1565 /* Paragraph separators have their levels fully resolved
1566 at this point, so cache them as resolved. */
1568 /* FIXME: implement L1 here, by testing for a newline and
1569 resetting the level for any sequence of whitespace
1570 characters adjacent to it. */
1574 /* This is all per level run, so stop when we
1575 reach the end of this level run. */
1577 current_level));
1582 {
1590 /* N1: ``European and Arabic numbers are treated as
1591 though they were R.'' */
1598 /* FALLTHROUGH */
1600 /* Marched all the way to the end of this level run.
1601 We need to use the eor type, whose information is
1602 stored by bidi_set_sor_type in the prev_for_neutral
1603 member. */
1606 {
1610 }
1611 else
1612 {
1613 /* This is a BN which does not adjoin neutrals.
1614 Leave its type alone. */
1617 }
1621 }
1627 }
1628 }
1630 }
1632 /* Given an iterator state in BIDI_IT, advance one character position
1633 in the buffer to the next character (in the logical order), resolve
1634 the bidi type of that next character, and return that type. */
1635 static bidi_type_t
1637 {
1638 bidi_type_t type;
1640 /* This should always be called during a forward scan. */
1644 /* Reset the limit until which to ignore BNs if we step out of the
1645 area where we found only empty levels. */
1655 }
1657 /* Given an iterator state BIDI_IT, advance one character position in
1658 the buffer to the next character (in the logical order), resolve
1659 the embedding and implicit levels of that next character, and
1660 return the resulting level. */
1661 static int
1663 {
1664 bidi_type_t type;
1669 {
1670 /* There's no sense in trying to advance if we hit end of text. */
1674 /* Record the info about the previous character. */
1682 /* FIXME: it sounds like we don't need both prev and
1683 prev_for_neutral members, but I'm leaving them both for now. */
1688 /* If we overstepped the characters used for resolving neutrals
1689 and whitespace, invalidate their info in the iterator. */
1699 /* This must be taken before we fill the iterator with the info
1700 about the next char. If we scan backwards, the iterator
1701 state must be already cached, so there's no need to know the
1702 embedding level of the previous character, since we will be
1703 returning to our caller shortly. */
1705 }
1708 /* Perhaps it is already cached. */
1711 {
1712 /* Don't lose the information for resolving neutrals! The
1713 cached states could have been cached before their
1714 next_for_neutral member was computed. If we are on our way
1715 forward, we can simply take the info from the previous
1716 state. */
1721 /* If resolved_level is -1, it means this state was cached
1722 before it was completely resolved, so we cannot return
1723 it. */
1726 }
1728 /* If we are going backwards, the iterator state is already cached
1729 from previous scans, and should be fully resolved. */
1741 {
1745 /* If the cached state shows a neutral character, it was not
1746 resolved by bidi_resolve_neutral, so do it now. */
1749 level);
1750 }
1761 /* For L1 below, we need to know, for each WS character, whether
1762 it belongs to a sequence of WS characters preceeding a newline
1763 or a TAB or a paragraph separator. */
1766 {
1771 bidi_type_t chtype;
1774 /*_fetch_multibyte_char_len = 1;*/
1777 cpos++;
1781 else
1789 }
1791 /* Resolve implicit levels, with a twist: PDFs get the embedding
1792 level of the enbedding they terminate. See below for the
1793 reason. */
1795 /* Don't do this if this formatting code didn't change the
1796 embedding level due to invalid or empty embeddings. */
1798 {
1799 /* Don't look in UAX#9 for the reason for this: it's our own
1800 private quirk. The reason is that we want the formatting
1801 codes to be delivered so that they bracket the text of their
1802 embedding. For example, given the text
1804 {RLO}teST{PDF}
1806 we want it to be displayed as
1808 {RLO}STet{PDF}
1810 not as
1812 STet{RLO}{PDF}
1814 which will result because we bump up the embedding level as
1815 soon as we see the RLO and pop it as soon as we see the PDF,
1816 so RLO itself has the same embedding level as "teST", and
1817 thus would be normally delivered last, just before the PDF.
1818 The switch below fiddles with the level of PDF so that this
1819 ugly side effect does not happen.
1821 (This is, of course, only important if the formatting codes
1822 are actually displayed, but Emacs does need to display them
1823 if the user wants to.) */
1825 }
1829 /* || bidi_it->ch == LINESEP_CHAR */
1835 {
1837 level++;
1840 }
1842 {
1844 level++;
1845 }
1849 }
1851 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
1852 non-zero, we are at the end of a level, and we need to prepare to
1853 resume the scan of the lower level.
1855 If this level's other edge is cached, we simply jump to it, filling
1856 the iterator structure with the iterator state on the other edge.
1857 Otherwise, we walk the buffer until we come back to the same level
1858 as LEVEL.
1860 Note: we are not talking here about a ``level run'' in the UAX#9
1861 sense of the term, but rather about a ``level'' which includes
1862 all the levels higher than it. In other words, given the levels
1863 like this:
1865 11111112222222333333334443343222222111111112223322111
1866 A B C
1868 and assuming we are at point A scanning left to right, this
1869 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
1870 at point B. */
1871 static void
1873 {
1877 /* Try the cache first. */
1880 else
1881 {
1892 }
1893 }
1895 void
1897 {
1902 {
1904 }
1906 /* If we just passed a newline, initialize for the next line. */
1910 /* Prepare the sentinel iterator state, and cache it. When we bump
1911 into it, scanning backwards, we'll know that the last non-base
1912 level is exhausted. */
1914 {
1917 {
1922 }
1924 }
1929 /* Reordering of resolved levels (clause L2) is implemented by
1930 jumping to the other edge of the level and flipping direction of
1931 scanning the text whenever we find a level change. */
1933 {
1939 /* Jump (or walk) to the other edge of this level. */
1941 /* Switch scan direction and peek at the next character in the
1942 new direction. */
1945 /* The following loop handles the case where the resolved level
1946 jumps by more than one. This is typical for numbers inside a
1947 run of text with left-to-right embedding direction, but can
1948 also happen in other situations. In those cases the decision
1949 where to continue after a level change, and in what direction,
1950 is tricky. For example, given a text like below:
1952 abcdefgh
1953 11336622
1955 (where the numbers below the text show the resolved levels),
1956 the result of reordering according to UAX#9 should be this:
1958 efdcghba
1960 This is implemented by the loop below which flips direction
1961 and jumps to the other edge of the level each time it finds
1962 the new level not to be the expected one. The expected level
1963 is always one more or one less than the previous one. */
1966 {
1972 }
1974 /* Finally, deliver the next character in the new direction. */
1976 }
1978 /* Take note when we have just processed the newline that precedes
1979 the end of the paragraph. The next time we are about to be
1980 called, set_iterator_to_next will automatically reinit the
1981 paragraph direction, if needed. We do this at the newline before
1982 the paragraph separator, because the next character might not be
1983 the first character of the next paragraph, due to the bidi
1984 reordering, whereas we _must_ know the paragraph base direction
1985 _before_ we process the paragraph's text, since the base
1986 direction affects the reordering. */
1990 {
1991 EMACS_INT sep_len =
1995 {
1997 /* Record the buffer position of the last character of the
1998 paragraph separator. */
2000 }
2001 }
2004 {
2005 /* If we are at paragraph's base embedding level and beyond the
2006 last cached position, the cache's job is done and we can
2007 discard it. */
2011 /* But as long as we are caching during forward scan, we must
2012 cache each state, or else the cache integrity will be
2013 compromised: it assumes cached states correspond to buffer
2014 positions 1:1. */
2015 else
2017 }
2018 }
2020 /* This is meant to be called from within the debugger, whenever you
2021 wish to examine the cache contents. */
2022 void
2024 {
2029 {
2032 }
2037 ndigits++;
2050 }