Subject: Re: bug#16581: suggested code simplification in dfa.c

From: Paul Eggert <[email-masked]>
Date: Tue, 28 Jan 2014 22:48:16 -0800

Aharon Robbins wrote:
> that exclusive-ORing looks a little scary to me.

It is derived from a coding hack that I picked up from Dijkstra back in 
the 1970s.  He gave the most boring computer-science lecture I have ever 
attended -- so boring that Kit Fine walked out a few minutes into it -- 
but I stubbornly stayed through to the end and I've never forgotten the 
hack.

The hack works everywhere, including platforms that use EBCDIC, 
shift-JIS, DBCS, etc., because it doesn't rely on the encoding scheme at 
all.  Attached is a revised patch that adds some commentary and breaks 
the hack into some functions that I hope help explain things.  Sorry, I 
don't know how to break this into smaller patches that would be easier 
to understand.
>From 859b9496860e67d01e32a58e9f2a098410775a22 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 28 Jan 2014 13:47:47 -0800
Subject: [PATCH] Simplify handling of letter case.

* src/dfa.c (setbit_wc, setbit_case_fold_c, atom): Simplify.
(xor_other, xor_wother, to_other, to_wother): New functions.
(setbit_case_fold_c, parse_bracket_exp, lex, atom): Use them
to invoke tolower and toupper instead of isalpha followed by one or
the other, and similarly for towlower, towupper, iswalpha.  This should
lead to more-efficient handling of caseless letters, and it simplifies
the code.
---
 src/dfa.c | 130 +++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 81 insertions(+), 49 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index b79c604..af830a8 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -662,6 +662,42 @@ wchar_context (wint_t wc)
   return CTX_NONE;
 }
 
+/* The following functions exploit the commutativity and associativity of ^,
+   and the fact that X ^ X is zero.  POSIX requires that C equals
+   either tolower (C) or toupper (C); if the former, then C ^ tolower (C)
+   is zero so C ^ xor_other (C) equals toupper (C), and similarly
+   for the latter.  */
+
+/* Return the exclusive-OR of C and C's other case, or zero if C is
+   not a letter that changes case.  */
+
+static int
+xor_other (int c)
+{
+  return tolower (c) ^ toupper (c);
+}
+
+static wint_t
+xor_wother (wint_t c)
+{
+  return towlower (c) ^ towupper (c);
+}
+
+/* If C is a lowercase letter, return its uppercase version, and vice versa.
+   Return C if it's not a letter that changes case.  */
+
+static int
+to_other (int c)
+{
+  return c ^ xor_other (c);
+}
+
+static wint_t
+to_wother (wint_t c)
+{
+  return c ^ xor_wother (c);
+}
+
 /* Entry point to set syntax options.  */
 void
 dfasyntax (reg_syntax_t bits, int fold, unsigned char eol)
@@ -693,39 +729,24 @@ dfasyntax (reg_syntax_t bits, int fold, unsigned char eol)
    this may happen when folding case in weird Turkish locales where
    dotless i/dotted I are not included in the chosen character set.
    Return whether a bit was set in the charclass.  */
-#if MBS_SUPPORT
 static bool
 setbit_wc (wint_t wc, charclass c)
 {
+#if MBS_SUPPORT
   int b = wctob (wc);
   if (b == EOF)
     return false;
 
   setbit (b, c);
   return true;
-}
-
-/* Set a bit in the charclass for the given single byte character,
-   if it is valid in the current character set.  */
-static void
-setbit_c (int b, charclass c)
-{
-  /* Do nothing if b is invalid in this character set.  */
-  if (MB_CUR_MAX > 1 && btowc (b) == WEOF)
-    return;
-  setbit (b, c);
-}
 #else
-# define setbit_c setbit
-static inline bool
-setbit_wc (wint_t wc, charclass c)
-{
   abort ();
    /*NOTREACHED*/ return false;
-}
 #endif
+}
 
-/* Like setbit_c, but if case is folded, set both cases of a letter.  For
+/* Like setbit_wc but for a single-byte character B; and if case is
+   folded, set both cases of a letter.  For
    MB_CUR_MAX > 1, the resulting charset is only used as an optimization,
    and the caller takes care of setting the appropriate field of struct
    mb_char_classes.  */
@@ -737,16 +758,16 @@ setbit_case_fold_c (int b, charclass c)
       wint_t wc = btowc (b);
       if (wc == WEOF)
         return;
-      setbit (b, c);
-      if (case_fold && iswalpha (wc))
-        setbit_wc (iswupper (wc) ? towlower (wc) : towupper (wc), c);
+      if (case_fold)
+        setbit_wc (to_wother (wc), c);
     }
   else
     {
-      setbit (b, c);
-      if (case_fold && isalpha (b))
-        setbit_c (isupper (b) ? tolower (b) : toupper (b), c);
+      if (case_fold)
+        setbit (to_other (b), c);
     }
+
+  setbit (b, c);
 }

@@ -1085,23 +1106,30 @@ parse_bracket_exp (void)
             {
               /* When case folding map a range, say [m-z] (or even [M-z])
                  to the pair of ranges, [m-z] [M-Z].  */
+              wchar_t lo1 = wc, hi1 = wc2, lo2 = wc, hi2 = wc2;
+              if (case_fold)
+                {
+                  lo1 = towlower (lo1);
+                  hi1 = towlower (hi1);
+                  lo2 = towupper (lo2);
+                  hi2 = towupper (hi2);
+                }
+
               REALLOC_IF_NECESSARY (work_mbc->range_sts,
                                     range_sts_al, work_mbc->nranges + 1);
               REALLOC_IF_NECESSARY (work_mbc->range_ends,
                                     range_ends_al, work_mbc->nranges + 1);
-              work_mbc->range_sts[work_mbc->nranges] =
-                case_fold ? towlower (wc) : (wchar_t) wc;
-              work_mbc->range_ends[work_mbc->nranges++] =
-                case_fold ? towlower (wc2) : (wchar_t) wc2;
+              work_mbc->range_sts[work_mbc->nranges] = lo1;
+              work_mbc->range_ends[work_mbc->nranges++] = hi1;
 
-              if (case_fold && (iswalpha (wc) || iswalpha (wc2)))
+              if (lo1 != lo2 || hi1 != hi2)
                 {
                   REALLOC_IF_NECESSARY (work_mbc->range_sts,
                                         range_sts_al, work_mbc->nranges + 1);
-                  work_mbc->range_sts[work_mbc->nranges] = towupper (wc);
+                  work_mbc->range_sts[work_mbc->nranges] = lo2;
                   REALLOC_IF_NECESSARY (work_mbc->range_ends,
                                         range_ends_al, work_mbc->nranges + 1);
-                  work_mbc->range_ends[work_mbc->nranges++] = towupper (wc2);
+                  work_mbc->range_ends[work_mbc->nranges++] = hi2;
                 }
             }
           else
@@ -1129,16 +1157,19 @@ parse_bracket_exp (void)
           continue;
         }
 
-      if (case_fold && iswalpha (wc))
+      if (case_fold)
         {
-          wc = towlower (wc);
-          if (!setbit_wc (wc, ccl))
+          wchar_t xor = xor_wother (wc);
+          if (xor)
             {
-              REALLOC_IF_NECESSARY (work_mbc->chars, chars_al,
-                                    work_mbc->nchars + 1);
-              work_mbc->chars[work_mbc->nchars++] = wc;
+              wchar_t other = wc ^ xor;
+              if (!setbit_wc (other, ccl))
+                {
+                  REALLOC_IF_NECESSARY (work_mbc->chars, chars_al,
+                                        work_mbc->nchars + 1);
+                  work_mbc->chars[work_mbc->nchars++] = other;
+                }
             }
-          wc = towupper (wc);
         }
       if (!setbit_wc (wc, ccl))
         {
@@ -1481,7 +1512,7 @@ lex (void)
           if (MB_CUR_MAX > 1)
             return lasttok = WCHAR;
 
-          if (case_fold && isalpha (c))
+          if (case_fold && tolower (c) != toupper (c))
             {
               zeroset (ccl);
               setbit_case_fold_c (c, ccl);
@@ -1725,17 +1756,18 @@ add_utf8_anychar (void)
 static void
 atom (void)
 {
-  if (0)
-    {
-      /* empty */
-    }
-  else if (MBS_SUPPORT && tok == WCHAR)
+  if (MBS_SUPPORT && tok == WCHAR)
     {
-      addtok_wc (case_fold ? towlower (wctok) : wctok);
-      if (case_fold && iswalpha (wctok))
+      wchar_t wc = wctok;
+      addtok_wc (wc);
+      if (case_fold)
         {
-          addtok_wc (towupper (wctok));
-          addtok (OR);
+          wchar_t xor = xor_wother (wc);
+          if (xor)
+            {
+              addtok_wc (wc ^ xor);
+              addtok (OR);
+            }
         }
 
       tok = lex ();
-- 
1.8.5.3