| blob | ad5c8e9170ff0a27e604fef9f6410f988c77bd66 |
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 2, or (at your option)
10 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.
18 You should have received a copy of the GNU General Public License
19 along with GNU Emacs; see the file COPYING. If not, write to
20 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
23 /* Written by Eli Zaretskii <eliz@gnu.org>.
25 A sequential implementation of the Unicode Bidirectional algorithm,
26 as per UAX#9, a part of the Unicode Standard.
28 Unlike the reference and most other implementations, this one is
29 designed to be called once for every character in the buffer.
31 The main entry point is bidi_get_next_char_visually. Each time it
32 is called, it finds the next character in the visual order, and
33 returns its information in a special structure. The caller is then
34 expected to process this character for display or any other
35 purposes, and call bidi_get_next_char_visually for the next
36 character. See the comments in bidi_get_next_char_visually for
37 more details about its algorithm that finds the next visual-order
38 character by resolving their levels on the fly.
40 If you want to understand the code, you will have to read it
41 together with the relevant portions of UAX#9. The comments include
42 references to UAX#9 rules, for that very reason.
44 A note about references to UAX#9 rules: if the reference says
45 something like "X9/Retaining", it means that you need to refer to
46 rule X9 and to its modifications decribed in the "Implementation
47 Notes" section of UAX#9, under "Retaining Format Codes". */
49 #ifdef HAVE_CONFIG_H
50 #include <config.h>
51 #endif
53 #include <stdio.h>
55 #ifdef HAVE_STRING_H
56 #include <string.h>
57 #endif
59 #include <setjmp.h>
70 /* FIXME: Remove these when bidi_explicit_dir_char uses a lookup table. */
71 #define LRM_CHAR 0x200E
72 #define RLM_CHAR 0x200F
73 #define LRE_CHAR 0x202A
74 #define RLE_CHAR 0x202B
75 #define PDF_CHAR 0x202C
76 #define LRO_CHAR 0x202D
77 #define RLO_CHAR 0x202E
79 #define BIDI_EOB -1
82 /* Local data structures. (Look in dispextern.h for the rest.) */
84 /* What we need to know about the current paragraph. */
90 };
92 /* Data type for describing the bidirectional character categories. */
94 UNKNOWN_BC,
95 NEUTRAL,
96 WEAK,
97 STRONG
105 static void
107 {
108 /* FIXME: This should come from the Unicode Database. */
111 bidi_type_t type;
399 fallback_paragraph_start_re =
406 fallback_paragraph_separate_re =
414 }
416 /* Return the bidi type of a character CH, subject to the current
417 directional OVERRIDE. */
418 bidi_type_t
420 {
421 bidi_type_t default_type;
434 {
435 /* Although UAX#9 does not tell, it doesn't make sense to
436 override NEUTRAL_B and LRM/RLM characters. */
446 {
455 else
457 }
458 }
459 }
461 void
463 {
466 }
468 /* Given a bidi TYPE of a character, return its category. */
469 bidi_category_t
471 {
473 {
500 }
501 }
503 /* Return the mirrored character of C, if any.
505 Note: The conditions in UAX#9 clause L4 must be tested by the
506 caller. */
507 /* FIXME: exceedingly temporary! Should consult the Unicode database
508 of character properties. */
509 int
511 {
516 {
520 }
522 }
524 /* Copy the bidi iterator from FROM to TO. To save cycles, this only
525 copies the part of the level stack that is actually in use. */
528 {
531 /* Copy everything except the level stack and beyond. */
534 /* Copy the active part of the level stack. */
538 }
540 /* Caching the bidi iterator states. */
548 {
551 }
555 {
564 }
566 /* Find a cached state with a given CHARPOS and resolved embedding
567 level less or equal to LEVEL. if LEVEL is -1, disregard the
568 resolved levels in cached states. DIR, if non-zero, means search
569 in that direction from the last cache hit. */
572 {
576 {
583 else
584 {
587 }
590 {
591 /* Linear search for now; FIXME! */
596 }
597 else
598 {
603 }
604 }
607 }
609 /* Find a cached state where the resolved level changes to a value
610 that is lower than LEVEL, and return its cache slot index. DIR is
611 the direction to search, starting with the last used cache slot.
612 BEFORE, if non-zero, means return the index of the slot that is
613 ``before'' the level change in the search direction. That is,
614 given the cached levels like this:
616 1122333442211
617 AB C
619 and assuming we are at the position cached at the slot marked with
620 C, searching backwards (DIR = -1) for LEVEL = 2 will return the
621 index of slot B or A, depending whether BEFORE is, respectively,
622 non-zero or zero. */
623 static int
625 {
627 {
637 {
639 {
643 i--;
644 }
645 }
646 else
647 {
649 {
653 i++;
654 }
655 }
656 }
659 }
663 {
666 /* We should never cache on backward scans. */
672 {
674 /* Don't overrun the cache limit. */
677 /* Don't violate cache integrity: character positions should
678 correspond to cache positions 1:1. */
685 }
686 else
687 {
688 /* Copy only the members which could have changed, to avoid
689 costly copying of the entire struct. */
696 else
703 }
708 }
712 {
716 {
721 /* Don't let scan direction from from the cached state override
722 the current scan direction. */
725 }
728 }
732 {
736 }
738 /* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
739 Value is the non-negative length of the paragraph separator
740 following the buffer position, -1 if position is at the beginning
741 of a new paragraph, or -2 if position is neither at beginning nor
742 at end of a paragraph. */
743 EMACS_INT
745 {
750 EMACS_INT val;
759 {
762 else
764 }
767 }
769 /* Determine the start-of-run (sor) directional type given the two
770 embedding levels on either side of the run boundary. Also, update
771 the saved info about previously seen characters, since that info is
772 generally valid for a single level run. */
775 {
778 /* The prev_was_pdf gork is required for when we have several PDFs
779 in a row. In that case, we want to compute the sor type for the
780 next level run only once: when we see the first PDF. That's
781 because the sor type depends only on the higher of the two levels
782 that we find on the two sides of the level boundary (see UAX#9,
783 clause X10), and so we don't need to know the final embedding
784 level to which we descend after processing all the PDFs. */
786 /* FIXME: should the default sor direction be user selectable? */
800 }
802 static void
804 {
817 }
819 /* Find the beginning of this paragraph by looking back in the buffer.
820 Value is the byte position of the paragraph's beginning. */
821 static EMACS_INT
823 {
831 {
834 }
836 }
838 /* Determine the direction, a.k.a. base embedding level, of the
839 paragraph we are about to iterate through. If DIR is either L2R or
840 R2L, just use that. Otherwise, determine the paragraph direction
841 from the first strong character of the paragraph.
843 Note that this gives the paragraph separator the same direction as
844 the preceding paragraph, even though Emacs generally views the
845 separartor as not belonging to any paragraph. */
846 void
848 {
851 /* Special case for an empty buffer. */
854 /* We should never be called at EOB or before BEGV. */
859 {
862 }
864 {
867 }
869 {
871 EMACS_INT pos;
872 bidi_type_t type;
873 EMACS_INT sep_len;
875 /* If we are inside a paragraph separator, we are just waiting
876 for the separator to be exhausted; use the previous paragraph
877 direction. But don't do that if we have been just reseated,
878 because we need to reinitialize below in that case. */
883 /* If we are on a newline, get past it to where the next
884 paragraph might start. But don't do that at BEGV since then
885 we are potentially in a new paragraph that doesn't yet
886 exist. */
889 {
890 bytepos++;
891 pos++;
892 }
894 /* We are either at the beginning of a paragraph or in the
895 middle of it. Find where this paragraph starts. */
898 /* We should always be at the beginning of a new line at this
899 point. */
911 /* NOTE: UAX#9 says to search only for L, AL, or R types of
912 characters, and ignore RLE, RLO, LRE, and LRO. However,
913 I'm not sure it makes sense to omit those 4; should try
914 with and without that to see the effect. */
916 || (bidi_ignore_explicit_marks_for_paragraph_level
920 {
924 {
925 /* Pretend there's a paragraph separator at end of buffer. */
928 }
930 }
935 }
936 else
939 /* Contrary to UAX#9 clause P3, we only default the paragraph
940 direction to L2R if we have no previous usable paragraph
941 direction. */
946 else
950 }
952 /* Do whatever UAX#9 clause X8 says should be done at paragraph's
953 end. */
956 {
961 }
963 /* Initialize the bidi iterator from buffer position CHARPOS. */
964 void
966 {
991 }
993 /* Push the current embedding level and override status; reset the
994 current level to LEVEL and the current override status to OVERRIDE. */
998 {
1004 }
1006 /* Pop the embedding level and directional override status from the
1007 stack, and return the new level. */
1010 {
1011 /* UAX#9 says to ignore invalid PDFs. */
1015 }
1017 /* Record in SAVED_INFO the information about the current character. */
1021 {
1030 }
1032 /* Resolve the type of a neutral character according to the type of
1033 surrounding strong text and the current embedding level. */
1036 {
1037 /* N1: European and Arabic numbers are treated as though they were R. */
1047 else
1049 }
1053 {
1054 /* FIXME: this should be replaced with a lookup table with suitable
1055 bits set, like standard C ctype macros do. */
1058 }
1060 /* A helper function for bidi_resolve_explicit. It advances to the
1061 next character in logical order and determines the new embedding
1062 level and directional override, but does not take into account
1063 empty embeddings. */
1064 static int
1066 {
1068 bidi_type_t type;
1071 bidi_dir_t override;
1075 {
1080 }
1082 {
1087 }
1093 /* in case it is a unibyte character (not yet implemented) */
1094 /* _fetch_multibyte_char_len = 1; */
1096 {
1099 }
1100 else
1101 {
1104 }
1107 /* Don't apply directional override here, as all the types we handle
1108 below will not be affected by the override anyway, and we need
1109 the original type unaltered. The override will be applied in
1110 bidi_resolve_weak. */
1121 {
1128 {
1130 {
1131 /* Compute the least odd embedding level greater than
1132 the current level. */
1136 else
1141 }
1142 else
1143 {
1145 /* See the commentary about invalid_rl_levels below. */
1149 }
1150 }
1161 {
1163 {
1164 /* Compute the least even embedding level greater than
1165 the current level. */
1169 else
1172 }
1173 else
1174 {
1176 /* invalid_rl_levels counts invalid levels encountered
1177 while the embedding level was already too high for
1178 LRE/LRO, but not for RLE/RLO. That is because
1179 there may be exactly one PDF which we should not
1180 ignore even though invalid_levels is non-zero.
1181 invalid_rl_levels helps to know what PDF is
1182 that. */
1185 }
1186 }
1196 {
1198 {
1203 /* else nothing: UAX#9 says to ignore invalid PDFs */
1204 }
1207 else
1208 {
1211 }
1212 }
1218 /* Nothing. */
1220 }
1226 }
1228 /* Given an iterator state in BIDI_IT, advance one character position
1229 in the buffer to the next character (in the logical order), resolve
1230 any explicit embeddings and directional overrides, and return the
1231 embedding level of the character after resolving explicit
1232 directives and ignoring empty embeddings. */
1233 static int
1235 {
1245 {
1246 /* Avoid pushing and popping embedding levels if the level run
1247 is empty, as this breaks level runs where it shouldn't.
1248 UAX#9 removes all the explicit embedding and override codes,
1249 so empty embeddings disappear without a trace. We need to
1250 behave as if we did the same. */
1258 {
1260 }
1269 {
1270 /* We pushed a level, but we shouldn't have. Undo that. */
1272 {
1277 }
1280 else
1281 {
1284 }
1285 }
1286 }
1289 {
1291 /* This is needed by bidi_resolve_weak below, and in L1. */
1294 }
1297 }
1299 /* Advance in the buffer, resolve weak types and return the type of
1300 the next character after weak type resolution. */
1301 bidi_type_t
1303 {
1304 bidi_type_t type;
1305 bidi_dir_t override;
1309 bidi_type_t type_of_next;
1325 {
1326 /* We've got a new embedding level run, compute the directional
1327 type of sor and initialize per-run variables (UAX#9, clause
1328 X10). */
1330 }
1336 /* Level and directional override status are already recorded in
1337 bidi_it, and do not need any change; see X6. */
1342 else
1343 {
1345 {
1346 /* Note that we don't need to consider the case where the
1347 prev character has its type overridden by an RLO or LRO:
1348 such characters are outside the current level run, and
1349 thus not relevant to this NSM. Thus, NSM gets the
1350 orig_type of the previous character. */
1359 }
1372 {
1373 next_char =
1380 {
1384 ;
1387 }
1389 /* If the next character is EN, but the last strong-type
1390 character is AL, that next EN will be changed to AN when
1391 we process it in W2 above. So in that case, this ES
1392 should not be changed into EN. */
1398 {
1401 /* If the next character is EN, but the last
1402 strong-type character is AL, EN will be later
1403 changed to AN when we process it in W2 above.
1404 So in that case, this ES should not be
1405 changed into EN. */
1413 }
1414 }
1417 {
1422 {
1425 next_char =
1433 {
1438 ;
1442 }
1444 {
1445 /* If the last strong character is AL, the EN we've
1446 found will become AN when we get to it (W2). */
1448 {
1450 /* Remember this EN position, to speed up processing
1451 of the next ETs. */
1453 }
1456 }
1457 }
1458 }
1459 }
1468 /* Store the type we've got so far, before we clobber it with strong
1469 types in W7 and while resolving neutral types. But leave alone
1470 the original types that were recorded above, because we will need
1471 them for the L1 clause. */
1477 {
1481 }
1486 }
1488 bidi_type_t
1490 {
1508 {
1512 current_level);
1513 else
1514 {
1515 /* Arrrgh!! The UAX#9 algorithm is too deeply entrenched in
1516 the assumption of batch-style processing; see clauses W4,
1517 W5, and especially N1, which require to look far forward
1518 (as well as back) in the buffer. May the fleas of a
1519 thousand camels infest the armpits of those who design
1520 supposedly general-purpose algorithms by looking at their
1521 own implementations, and fail to consider other possible
1522 implementations! */
1524 bidi_type_t next_type;
1530 /* Scan the text forward until we find the first non-neutral
1531 character, and then use that to resolve the neutral we
1532 are dealing with now. We also cache the scanned iterator
1533 states, to salvage some of the effort later. */
1536 /* Record the info about the previous character, so that
1537 it will be cached below with this state. */
1542 /* Paragraph separators have their levels fully resolved
1543 at this point, so cache them as resolved. */
1545 /* FIXME: implement L1 here, by testing for a newline and
1546 resetting the level for any sequence of whitespace
1547 characters adjacent to it. */
1551 /* This is all per level run, so stop when we
1552 reach the end of this level run. */
1554 current_level));
1559 {
1567 /* N1: ``European and Arabic numbers are treated as
1568 though they were R.'' */
1575 /* FALLTHROUGH */
1577 /* Marched all the way to the end of this level run.
1578 We need to use the eor type, whose information is
1579 stored by bidi_set_sor_type in the prev_for_neutral
1580 member. */
1583 {
1587 }
1588 else
1589 {
1590 /* This is a BN which does not adjoin neutrals.
1591 Leave its type alone. */
1594 }
1598 }
1604 }
1605 }
1607 }
1609 /* Given an iterator state in BIDI_IT, advance one character position
1610 in the buffer to the next character (in the logical order), resolve
1611 the bidi type of that next character, and return that type. */
1612 bidi_type_t
1614 {
1615 bidi_type_t type;
1617 /* This should always be called during a forward scan. */
1621 /* Reset the limit until which to ignore BNs if we step out of the
1622 area where we found only empty levels. */
1632 }
1634 /* Given an iterator state BIDI_IT, advance one character position in
1635 the buffer to the next character (in the logical order), resolve
1636 the embedding and implicit levels of that next character, and
1637 return the resulting level. */
1638 int
1640 {
1641 bidi_type_t type;
1646 {
1647 /* There's no sense in trying to advance if we hit end of text. */
1651 /* Record the info about the previous character. */
1659 /* FIXME: it sounds like we don't need both prev and
1660 prev_for_neutral members, but I'm leaving them both for now. */
1665 /* If we overstepped the characters used for resolving neutrals
1666 and whitespace, invalidate their info in the iterator. */
1676 /* This must be taken before we fill the iterator with the info
1677 about the next char. If we scan backwards, the iterator
1678 state must be already cached, so there's no need to know the
1679 embedding level of the previous character, since we will be
1680 returning to our caller shortly. */
1682 }
1685 /* Perhaps it is already cached. */
1688 {
1689 /* Don't lose the information for resolving neutrals! The
1690 cached states could have been cached before their
1691 next_for_neutral member was computed. If we are on our way
1692 forward, we can simply take the info from the previous
1693 state. */
1698 /* If resolved_level is -1, it means this state was cached
1699 before it was completely resolved, so we cannot return
1700 it. */
1703 }
1705 /* If we are going backwards, the iterator state is already cached
1706 from previous scans, and should be fully resolved. */
1718 {
1722 /* If the cached state shows a neutral character, it was not
1723 resolved by bidi_resolve_neutral, so do it now. */
1726 level);
1727 }
1738 /* For L1 below, we need to know, for each WS character, whether
1739 it belongs to a sequence of WS characters preceeding a newline
1740 or a TAB or a paragraph separator. */
1743 {
1748 bidi_type_t chtype;
1751 /*_fetch_multibyte_char_len = 1;*/
1754 cpos++;
1758 else
1766 }
1768 /* Resolve implicit levels, with a twist: PDFs get the embedding
1769 level of the enbedding they terminate. See below for the
1770 reason. */
1772 /* Don't do this if this formatting code didn't change the
1773 embedding level due to invalid or empty embeddings. */
1775 {
1776 /* Don't look in UAX#9 for the reason for this: it's our own
1777 private quirk. The reason is that we want the formatting
1778 codes to be delivered so that they bracket the text of their
1779 embedding. For example, given the text
1781 {RLO}teST{PDF}
1783 we want it to be displayed as
1785 {RLO}STet{PDF}
1787 not as
1789 STet{RLO}{PDF}
1791 which will result because we bump up the embedding level as
1792 soon as we see the RLO and pop it as soon as we see the PDF,
1793 so RLO itself has the same embedding level as "teST", and
1794 thus would be normally delivered last, just before the PDF.
1795 The switch below fiddles with the level of PDF so that this
1796 ugly side effect does not happen.
1798 (This is, of course, only important if the formatting codes
1799 are actually displayed, but Emacs does need to display them
1800 if the user wants to.) */
1802 }
1806 /* || bidi_it->ch == LINESEP_CHAR */
1812 {
1814 level++;
1817 }
1819 {
1821 level++;
1822 }
1826 }
1828 /* Move to the other edge of a level given by LEVEL. If END_FLAG is
1829 non-zero, we are at the end of a level, and we need to prepare to
1830 resume the scan of the lower level.
1832 If this level's other edge is cached, we simply jump to it, filling
1833 the iterator structure with the iterator state on the other edge.
1834 Otherwise, we walk the buffer until we come back to the same level
1835 as LEVEL.
1837 Note: we are not talking here about a ``level run'' in the UAX#9
1838 sense of the term, but rather about a ``level'' which includes
1839 all the levels higher than it. In other words, given the levels
1840 like this:
1842 11111112222222333333334443343222222111111112223322111
1843 A B C
1845 and assuming we are at point A scanning left to right, this
1846 function moves to point C, whereas the UAX#9 ``level 2 run'' ends
1847 at point B. */
1848 static void
1850 {
1854 /* Try the cache first. */
1857 else
1858 {
1869 }
1870 }
1872 void
1874 {
1879 {
1881 }
1883 /* If we just passed a newline, initialize for the next line. */
1887 /* Prepare the sentinel iterator state. */
1889 {
1892 {
1897 }
1898 }
1903 /* Reordering of resolved levels (clause L2) is implemented by
1904 jumping to the other edge of the level and flipping direction of
1905 scanning the text whenever we find a level change. */
1907 {
1913 /* If we don't have anything cached yet, we need to cache the
1914 sentinel state, since we'll need it to record where to jump
1915 when the last non-base level is exhausted. */
1918 /* Jump (or walk) to the other edge of this level. */
1920 /* Switch scan direction and peek at the next character in the
1921 new direction. */
1924 /* The following loop handles the case where the resolved level
1925 jumps by more than one. This is typical for numbers inside a
1926 run of text with left-to-right embedding direction, but can
1927 also happen in other situations. In those cases the decision
1928 where to continue after a level change, and in what direction,
1929 is tricky. For example, given a text like below:
1931 abcdefgh
1932 11336622
1934 (where the numbers below the text show the resolved levels),
1935 the result of reordering according to UAX#9 should be this:
1937 efdcghba
1939 This is implemented by the loop below which flips direction
1940 and jumps to the other edge of the level each time it finds
1941 the new level not to be the expected one. The expected level
1942 is always one more or one less than the previous one. */
1945 {
1951 }
1953 /* Finally, deliver the next character in the new direction. */
1955 }
1957 /* Take note when we have just processed the newline that precedes
1958 the end of the paragraph. The next time we are about to be
1959 called, set_iterator_to_next will automatically reinit the
1960 paragraph direction, if needed. We do this at the newline before
1961 the paragraph separator, because the next character might not be
1962 the first character of the next paragraph, due to the bidi
1963 reordering, whereas we _must_ know the paragraph base direction
1964 _before_ we process the paragraph's text, since the base
1965 direction affects the reordering. */
1969 {
1970 EMACS_INT sep_len =
1974 {
1976 /* Record the buffer position of the last character of the
1977 paragraph separator. */
1979 }
1980 }
1983 {
1984 /* If we are at paragraph's base embedding level and beyond the
1985 last cached position, the cache's job is done and we can
1986 discard it. */
1990 /* But as long as we are caching during forward scan, we must
1991 cache each state, or else the cache integrity will be
1992 compromised: it assumes cached states correspond to buffer
1993 positions 1:1. */
1994 else
1996 }
1997 }
1999 /* This is meant to be called from within the debugger, whenever you
2000 wish to examine the cache contents. */
2001 void
2003 {
2008 {
2011 }
2016 ndigits++;
2029 }