Fix bidi reordering of bracket characters in isolates.

 src/bidi.c (bidi_cache_find): Rename the argument NEUTRALS_OK to
 RESOLVED_ONLY; when non-zero, return from the cache only fully
 resolved states.  All callers changed.
 (CANONICAL_EQU): New macro.
 (PUSH_BPA_STACK): Use it to push onto the BPA stack the canonical
 equivalent of the paired closing bracket character.
 (bidi_find_bracket_pairs): Set the bracket_pairing_pos member to
 the default non-negative value, to be checked later in
 bidi_resolve_brackets.  Use CANONICAL_EQU to test candidate
 characters against those pushed onto the BPA stack.
 (bidi_record_type_for_neutral): New function.
 (bidi_resolve_brackets): Record next_for_neutral and
 prev_for_neutral when embedding level gets pushed.  Force
 resolution of bracket pairs when entering a level run that was not
 yet BPA-resolved.
 (bidi_resolve_neutral): Add assertions before calling
 bidi_resolve_neutral_1.
 (bidi_level_of_next_char): Remove the code that attempted to
 resolve unresolved neutrals; that is now done by
 bidi_resolve_neutral.

2 files changed, 176 insertions, 108 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index 026ae46299d..66306bd5fb6 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,27 @@
 2014-10-18  Eli Zaretskii  <eliz@gnu.org>
 
+        Fix reordering of bracket characters in isolates.
+        * bidi.c (bidi_cache_find): Rename the argument NEUTRALS_OK to
+        RESOLVED_ONLY; when non-zero, return from the cache only fully
+        resolved states.  All callers changed.
+        (CANONICAL_EQU): New macro.
+        (PUSH_BPA_STACK): Use it to push onto the BPA stack the canonical
+        equivalent of the paired closing bracket character.
+        (bidi_find_bracket_pairs): Set the bracket_pairing_pos member to
+        the default non-negative value, to be checked later in
+        bidi_resolve_brackets.  Use CANONICAL_EQU to test candidate
+        characters against those pushed onto the BPA stack.
+        (bidi_record_type_for_neutral): New function.
+        (bidi_resolve_brackets): Record next_for_neutral and
+        prev_for_neutral when embedding level gets pushed.  Force
+        resolution of bracket pairs when entering a level run that was not
+        yet BPA-resolved.
+        (bidi_resolve_neutral): Add assertions before calling
+        bidi_resolve_neutral_1.
+        (bidi_level_of_next_char): Remove the code that attempted to
+        resolve unresolved neutrals; that is now done by
+        bidi_resolve_neutral.
+
         * w32select.c (owner_callback): Mark with ALIGN_STACK attribute.
 
 2014-10-17  Eli Zaretskii  <eliz@gnu.org>
diff --git a/src/bidi.c b/src/bidi.c
index bbafc785e7b..59fade3f785 100644
--- a/src/bidi.c
+++ b/src/bidi.c
@@ -800,26 +800,22 @@ bidi_cache_iterator_state (struct bidi_it *bidi_it, bool resolved,
 
 /* Look for a cached iterator state that corresponds to CHARPOS.  If
    found, copy the cached state into BIDI_IT and return the type of
-   the cached entry.  If not found, return UNKNOWN_BT.  NEUTRALS_OK
-   non-zero means it is OK to return cached state for neutral
-   characters that have no valid next_for_neutral member, and
-   therefore cannot be resolved.  This can happen if the state was
-   cached before it was resolved in bidi_resolve_neutral.  */
+   the cached entry.  If not found, return UNKNOWN_BT.  RESOLVED_ONLY
+   zero means it is OK to return cached states tyhat were not fully
+   resolved yet.  This can happen if the state was cached before it
+   was resolved in bidi_resolve_neutral.  */
 static bidi_type_t
-bidi_cache_find (ptrdiff_t charpos, bool neutrals_ok, struct bidi_it *bidi_it)
+bidi_cache_find (ptrdiff_t charpos, bool resolved_only, struct bidi_it *bidi_it)
 {
   ptrdiff_t i = bidi_cache_search (charpos, -1, bidi_it->scan_dir);
 
   if (i >= bidi_cache_start
-      && (neutrals_ok
-          /* Callers that don't want to resolve neutrals (and set
-             neutrals_ok = false) need to be sure that there's enough
-             info in the cached state to resolve the neutrals and
-             isolates, and if not, they don't want the cached state.  */
-          || !(bidi_cache[i].resolved_level == -1
-               && (bidi_get_category (bidi_cache[i].type) == NEUTRAL
-                   || bidi_isolate_fmt_char (bidi_cache[i].type))
-               && bidi_cache[i].next_for_neutral.type == UNKNOWN_BT)))
+      && (!resolved_only
+          /* Callers that want only fully resolved states (and set
+             resolved_only = true) need to be sure that there's enough
+             info in the cached state to return the state as final,
+             and if not, they don't want the cached state.  */
+          || bidi_cache[i].resolved_level >= 0))
     {
       bidi_dir_t current_scan_dir = bidi_it->scan_dir;
 
@@ -2342,6 +2338,41 @@ typedef struct bpa_stack_entry {
    BPA stack, which should be more than enough for actual bidi text.  */
 #define MAX_BPA_STACK (max (MAX_ALLOCA / sizeof (bpa_stack_entry), 1))
 
+/* UAX#9 says to match opening brackets with the matching closing
+   brackets or their canonical equivalents.  As of Unicode 7.0, there
+   are only 2 bracket characters that have canonical equivalence
+   decompositions: u+2329 and u+232A.  So instead of accessing the
+   table in uni-decomposition.el, we just handle these 2 characters
+   with this simple macro.  Note that ASCII characters don't have
+   canonical equivalents by definition.  */
+
+/* To find all the characters that need to be processed by
+   CANONICAL_EQU, first find all the characters which have
+   decompositions in UnicodeData.txt, with this Awk script:
+
+    awk -F ";" " {if ($6 != \"\") print $1, $6}" UnicodeData.txt
+
+   Then produce a list of all the bracket characters in BidiBrackets.txt:
+
+    awk -F "[ ;]" " {if ($1 != \"#\" && $1 != \"\") print $1}" BidiBrackets.txt
+
+   And finally, cross-reference these two:
+
+    fgrep -w -f brackets.txt decompositions.txt
+
+   where "decompositions.txt" was produced by the 1st script, and
+   "brackets.txt" by the 2nd script.  In the output of fgrep, look
+   only for decompositions that don't begin with some compatibility
+   formatting tag, such as "<compat>".  Only decompositions that
+   consist solely of character codepoints are relevant to bidi
+   brackets processing.  */
+
+#define CANONICAL_EQU(c)                                        \
+  ( ASCII_CHAR_P (c) ? c                                        \
+    : (c) == 0x2329 ? 0x3008                                    \
+    : (c) == 0x232a ? 0x3009                                    \
+    : c )
+
 #ifdef ENABLE_CHECKING
 # define STORE_BRACKET_CHARPOS \
    bpa_stack[bpa_sp].open_bracket_pos = bidi_it->charpos
@@ -2351,16 +2382,18 @@ typedef struct bpa_stack_entry {
 
 #define PUSH_BPA_STACK                                                  \
   do {                                                                  \
-   bpa_sp++;                                                            \
-   if (bpa_sp >= MAX_BPA_STACK)                                         \
-     {                                                                  \
-       bpa_sp = MAX_BPA_STACK - 1;                                      \
-       goto bpa_give_up;                                                \
-     }                                                                  \
-   bpa_stack[bpa_sp].close_bracket_char = bidi_mirror_char (bidi_it->ch); \
-   bpa_stack[bpa_sp].open_bracket_idx = bidi_cache_last_idx;            \
-   bpa_stack[bpa_sp].flags = 0;                                         \
-   STORE_BRACKET_CHARPOS;                                               \
+    int ch;                                                             \
+    bpa_sp++;                                                           \
+    if (bpa_sp >= MAX_BPA_STACK)                                        \
+      {                                                                 \
+        bpa_sp = MAX_BPA_STACK - 1;                                     \
+        goto bpa_give_up;                                               \
+      }                                                                 \
+    ch = CANONICAL_EQU (bidi_it->ch);                                   \
+    bpa_stack[bpa_sp].close_bracket_char = bidi_mirror_char (ch);       \
+    bpa_stack[bpa_sp].open_bracket_idx = bidi_cache_last_idx;           \
+    bpa_stack[bpa_sp].flags = 0;                                        \
+    STORE_BRACKET_CHARPOS;                                              \
   } while (0)
 
 
@@ -2405,13 +2438,22 @@ bidi_find_bracket_pairs (struct bidi_it *bidi_it)
           int old_sidx, new_sidx;
           int current_level = bidi_it->level_stack[bidi_it->stack_idx].level;
 
+          /* Mark every opening bracket character we've traversed by
+             putting its own position into bracket_pairing_pos.  This
+             is examined in bidi_resolve_brackets to distinguish
+             brackets that were already resolved to stay NEUTRAL_ON,
+             and those that were not yet processed by this function
+             (because they were skipped when we skip higher embedding
+             levels below).  */
+          if (btype == BIDI_BRACKET_OPEN && bidi_it->bracket_pairing_pos == -1)
+            bidi_it->bracket_pairing_pos = bidi_it->charpos;
           bidi_cache_iterator_state (bidi_it, type == NEUTRAL_B, 0);
           if (btype == BIDI_BRACKET_OPEN)
             PUSH_BPA_STACK;
           else if (btype == BIDI_BRACKET_CLOSE)
             {
               int sp = bpa_sp;
-              int curchar = bidi_it->ch;
+              int curchar = CANONICAL_EQU (bidi_it->ch);
 
               eassert (sp >= 0);
               while (sp >= 0 && bpa_stack[sp].close_bracket_char != curchar)
@@ -2513,13 +2555,35 @@ bidi_find_bracket_pairs (struct bidi_it *bidi_it)
 
       /* Restore bidi_it from the cache, which should have the bracket
          resolution members set as determined by the above loop.  */
-      type = bidi_cache_find (saved_it.charpos, 1, bidi_it);
+      type = bidi_cache_find (saved_it.charpos, 0, bidi_it);
       eassert (type == NEUTRAL_ON);
     }
 
   return retval;
 }
 
+static void
+bidi_record_type_for_neutral (struct bidi_saved_info *info, int level,
+                              bool nextp)
+{
+  int idx;
+
+  for (idx = bidi_cache_last_idx + 1; idx < bidi_cache_idx; idx++)
+    {
+      int lev = bidi_cache[idx].level_stack[bidi_cache[idx].stack_idx].level;
+
+      if (lev <= level)
+        {
+          eassert (lev == level);
+          if (nextp)
+            bidi_cache[idx].next_for_neutral = *info;
+          else
+            bidi_cache[idx].prev_for_neutral = *info;
+          break;
+        }
+    }
+}
+
 static bidi_type_t
 bidi_resolve_brackets (struct bidi_it *bidi_it)
 {
@@ -2527,12 +2591,24 @@ bidi_resolve_brackets (struct bidi_it *bidi_it)
   bool resolve_bracket = false;
   bidi_type_t type = UNKNOWN_BT;
   int ch;
-  struct bidi_saved_info tem_info;
-
-  bidi_remember_char (&tem_info, bidi_it, 1);
+  struct bidi_saved_info prev_for_neutral, next_for_neutral;
+
+  /* Record the prev_for_neutral type either from the previous
+     character, if it was a strong or AN/EN, or from the
+     prev_for_neutral information recorded previously.  */
+  if (bidi_it->type == STRONG_L || bidi_it->type == STRONG_R
+      || bidi_it->type == WEAK_AN || bidi_it->type == WEAK_EN)
+    bidi_remember_char (&prev_for_neutral, bidi_it, 1);
+  else
+    prev_for_neutral = bidi_it->prev_for_neutral;
+  /* Record the next_for_neutral type information.  */
+  if (bidi_it->next_for_neutral.charpos > bidi_it->charpos)
+    next_for_neutral = bidi_it->next_for_neutral;
+  else
+    next_for_neutral.charpos = -1;
   if (!bidi_it->first_elt)
     {
-      type = bidi_cache_find (bidi_it->charpos + bidi_it->nchars, 1, bidi_it);
+      type = bidi_cache_find (bidi_it->charpos + bidi_it->nchars, 0, bidi_it);
       ch = bidi_it->ch;
     }
   if (type == UNKNOWN_BT)
@@ -2543,36 +2619,45 @@ bidi_resolve_brackets (struct bidi_it *bidi_it)
     }
   else
     {
+      eassert (bidi_it->resolved_level == -1);
+      /* If the cached state shows an increase of embedding level due
+         to an isolate initiator, we need to update the 1st cached
+         state of the next run of the current isolating sequence with
+         the prev_for_neutral and next_for_neutral information, so
+         that it will be picked up when we advance to that next run.  */
+      if (bidi_it->level_stack[bidi_it->stack_idx].level > prev_level
+          && bidi_it->level_stack[bidi_it->stack_idx].isolate_status)
+        {
+          bidi_record_type_for_neutral (&prev_for_neutral, prev_level, 0);
+          bidi_record_type_for_neutral (&next_for_neutral, prev_level, 1);
+        }
       if (type == NEUTRAL_ON
           && bidi_paired_bracket_type (ch) == BIDI_BRACKET_OPEN)
         {
-          if (bidi_it->level_stack[bidi_it->stack_idx].level == prev_level)
+          if (bidi_it->bracket_pairing_pos > bidi_it->charpos)
             {
-              if (bidi_it->bracket_pairing_pos > 0)
-                {
-                  /* A cached opening bracket that wasn't completely
-                     resolved yet.  */
-                  resolve_bracket = true;
-                }
+              /* A cached opening bracket that wasn't completely
+                 resolved yet.  */
+              resolve_bracket = true;
             }
-          else
+          else if (bidi_it->bracket_pairing_pos == -1)
             {
               /* Higher levels were not BPA-resolved yet, even if
-                 cached by bidi_find_bracket_pairs.  Lower levels were
-                 probably processed by bidi_find_bracket_pairs, but we
-                 have no easy way of retaining the prev_for_neutral
-                 from the previous level run of the isolating
-                 sequence.  Force application of BPA now.  */
+                 cached by bidi_find_bracket_pairs.  Force application
+                 of BPA to the new level now.  */
               if (bidi_find_bracket_pairs (bidi_it))
                 resolve_bracket = true;
             }
         }
-      /* Keep track of the prev_for_neutral type, needed for resolving
-         brackets below and for resolving neutrals in bidi_resolve_neutral.  */
-      if (bidi_it->level_stack[bidi_it->stack_idx].level == prev_level
-          && (tem_info.type == STRONG_L || tem_info.type == STRONG_R
-              || tem_info.type == WEAK_AN || tem_info.type == WEAK_EN))
-        bidi_it->prev_for_neutral = tem_info;
+      /* Keep track of the prev_for_neutral and next_for_neutral
+         types, needed for resolving brackets below and for resolving
+         neutrals in bidi_resolve_neutral.  */
+      if (bidi_it->level_stack[bidi_it->stack_idx].level == prev_level)
+        {
+          bidi_it->prev_for_neutral = prev_for_neutral;
+          if (next_for_neutral.charpos > 0)
+            bidi_it->next_for_neutral = next_for_neutral;
+        }
     }
 
   /* If needed, resolve the bracket type according to N0.  */
@@ -2657,9 +2742,18 @@ bidi_resolve_neutral (struct bidi_it *bidi_it)
       || (type == WEAK_BN && bidi_explicit_dir_char (bidi_it->ch)))
     {
       if (bidi_it->next_for_neutral.type != UNKNOWN_BT)
-        type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
-                                       bidi_it->next_for_neutral.type,
-                                       current_level);
+        {
+          /* Make sure the data for resolving neutrals we are
+             about to use is valid.  */
+          eassert (bidi_it->next_for_neutral.charpos > bidi_it->charpos
+                   /* PDI defines an eos, so it's OK for it to
+                      serve as its own next_for_neutral.  */
+                   || (bidi_it->next_for_neutral.charpos == bidi_it->charpos
+                       && bidi_it->type == PDI));
+          type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
+                                         bidi_it->next_for_neutral.type,
+                                         current_level);
+        }
       /* The next two "else if" clauses are shortcuts for the
          important special case when we have a long sequence of
          neutral or WEAK_BN characters, such as whitespace or nulls or
@@ -2855,16 +2949,13 @@ bidi_level_of_next_char (struct bidi_it *bidi_it)
         }
     }
 
-  /* Perhaps the character we want is already cached.  If it is, the
-     call to bidi_cache_find below will return a type other than
-     UNKNOWN_BT.  */
+  /* Perhaps the character we want is already cached s fully resolved.
+     If it is, the call to bidi_cache_find below will return a type
+     other than UNKNOWN_BT.  */
   if (bidi_cache_idx > bidi_cache_start && !bidi_it->first_elt)
     {
       int bob = ((bidi_it->string.s || STRINGP (bidi_it->string.lstring))
                  ? 0 : 1);
-      bidi_type_t prev_type = bidi_it->type;
-      bidi_type_t type_for_neutral = bidi_it->next_for_neutral.type;
-      ptrdiff_t pos_for_neutral = bidi_it->next_for_neutral.charpos;
 
       if (bidi_it->scan_dir > 0)
         {
@@ -2879,57 +2970,12 @@ bidi_level_of_next_char (struct bidi_it *bidi_it)
            cached at the beginning of the iteration.  */
         next_char_pos = bidi_it->charpos - 1;
       if (next_char_pos >= bob - 1)
-        type = bidi_cache_find (next_char_pos, 0, bidi_it);
-
-      /* For a sequence of BN and NI, copy the type from the previous
-         character.  This is because the loop in bidi_resolve_neutral
-         that handles such sequences caches the characters it
-         traverses, but does not (and cannot) store the
-         next_for_neutral member for them, because it is only known
-         when the loop ends.  So when we find them in the cache, their
-         type needs to be updated, but we don't have next_for_neutral
-         to do that.  However, whatever type is resolved as result of
-         that loop, it will be the same for all the traversed
-         characters, by virtue of N1 and N2.  */
-      if (type == WEAK_BN && bidi_it->scan_dir > 0
-          && bidi_explicit_dir_char (bidi_it->ch)
-          && type_for_neutral != UNKNOWN_BT
-          && bidi_it->charpos < pos_for_neutral)
-        {
-          type = prev_type;
-          eassert (type != UNKNOWN_BT);
-        }
+        type = bidi_cache_find (next_char_pos, 1, bidi_it);
       if (type != UNKNOWN_BT)
         {
-          /* If resolved_level is -1, it means this state was cached
-             before it was completely resolved, so we cannot return
-             it.  */
-          if (bidi_it->resolved_level != -1)
-            {
-              eassert (bidi_it->resolved_level >= 0);
-              return bidi_it->resolved_level;
-            }
-          else
-            {
-              level = bidi_it->level_stack[bidi_it->stack_idx].level;
-              if (bidi_get_category (type) == NEUTRAL
-                  || bidi_isolate_fmt_char (type))
-                {
-                  /* Make sure the data for resolving neutrals we are
-                     about to use is valid.  */
-                  if (bidi_it->next_for_neutral.charpos < bidi_it->charpos
-                      /* PDI defines an eos, so it's OK for it to
-                         serve as its own next_for_neutral.  */
-                      || (bidi_it->next_for_neutral.charpos == bidi_it->charpos
-                          && bidi_it->type != PDI)
-                      || bidi_it->next_for_neutral.type == UNKNOWN_BT)
-                    emacs_abort ();
-
-                  type = bidi_resolve_neutral_1 (bidi_it->prev_for_neutral.type,
-                                                 bidi_it->next_for_neutral.type,
-                                                 level);
-                }
-            }
+          /* We asked the cache for fully resolved states.  */
+          eassert (bidi_it->resolved_level >= 0);
+          return bidi_it->resolved_level;
         }
     }