Fix substitute-command-keys unibyte, alloc bugs

* src/doc.c (Fsubstitute_command_keys): Fix some problems with
unibyte strings and with buffer allocation.  Make strings
multibyte, to avoid problems with unibyte strings that are not
valid UTF-8 (Bug#24206).  Redo buffer allocation so that it is
O(N), not O(N**2).  Avoid going past the end of the input string
when given invalid input.  Avoid some unlikely problems in
accessing the wrong storage after a GC.

1 files changed, 77 insertions, 92 deletions

diff --git a/src/doc.c b/src/doc.c
index 6ffdad10f03..e591ffca172 100644
--- a/src/doc.c
+++ b/src/doc.c
@@ -738,20 +738,18 @@ Otherwise, return a new string.  */)
   unsigned char const *start;
   ptrdiff_t length, length_byte;
   Lisp_Object name;
-  bool multibyte;
   ptrdiff_t nchars;
 
   if (NILP (string))
     return Qnil;
 
-  CHECK_STRING (string);
+  Lisp_Object str = Fstring_make_multibyte (string);
   tem = Qnil;
   keymap = Qnil;
   name = Qnil;
 
   enum text_quoting_style quoting_style = text_quoting_style ();
 
-  multibyte = STRING_MULTIBYTE (string);
   nchars = 0;
 
   /* KEYMAP is either nil (which means search all the active keymaps)
@@ -760,59 +758,53 @@ Otherwise, return a new string.  */)
      or from a \\<mapname> construct in STRING itself..  */
   keymap = Voverriding_local_map;
 
-  bsize = SBYTES (string);
+  ptrdiff_t strbytes = SBYTES (str);
+  bsize = strbytes;
 
-  /* Add some room for expansion due to quote replacement.  */
-  enum { EXTRA_ROOM = 20 };
-  if (bsize <= STRING_BYTES_BOUND - EXTRA_ROOM)
-    bsize += EXTRA_ROOM;
+  /* Fixed-size stack buffer.  */
+  char sbuf[MAX_ALLOCA];
 
-  bufp = buf = xmalloc (bsize);
+  /* Heap-allocated buffer, if any.  */
+  char *abuf;
 
-  strp = SDATA (string);
-  while (strp < SDATA (string) + SBYTES (string))
+  /* Extra room for expansion due to replacing ‘\[]’ with ‘M-x ’.  */
+  enum { EXTRA_ROOM = sizeof "M-x " - sizeof "\\[]" };
+
+  if (bsize <= sizeof sbuf - EXTRA_ROOM)
     {
-      if (strp[0] == '\\' && strp[1] == '=')
+      abuf = NULL;
+      buf = sbuf;
+      bsize = sizeof sbuf;
+    }
+  else
+    buf = abuf = xpalloc (NULL, &bsize, EXTRA_ROOM, STRING_BYTES_BOUND, 1);
+  bufp = buf;
+
+  strp = SDATA (str);
+  while (strp < SDATA (str) + strbytes)
+    {
+      unsigned char *close_bracket;
+
+      if (strp[0] == '\\' && strp[1] == '='
+          && strp + 2 < SDATA (str) + strbytes)
         {
           /* \= quotes the next character;
              thus, to put in \[ without its special meaning, use \=\[.  */
           changed = nonquotes_changed = true;
           strp += 2;
-          if (multibyte)
-            {
-              int len;
-
-              STRING_CHAR_AND_LENGTH (strp, len);
-              if (len == 1)
-                *bufp = *strp;
-              else
-                memcpy (bufp, strp, len);
-              strp += len;
-              bufp += len;
-              nchars++;
-            }
-          else
-            *bufp++ = *strp++, nchars++;
+          /* Fall through to copy one char.  */
         }
-      else if (strp[0] == '\\' && strp[1] == '[')
+      else if (strp[0] == '\\' && strp[1] == '['
+               && (close_bracket
+                   = memchr (strp + 2, ']',
+                             SDATA (str) + strbytes - (strp + 2))))
         {
-          ptrdiff_t start_idx;
           bool follow_remap = 1;
 
-          strp += 2;            /* skip \[ */
-          start = strp;
-          start_idx = start - SDATA (string);
-
-          while ((strp - SDATA (string)
-                  < SBYTES (string))
-                 && *strp != ']')
-            strp++;
-          length_byte = strp - start;
-
-          strp++;               /* skip ] */
+          start = strp + 2;
+          length_byte = close_bracket - start;
+          idx = close_bracket + 1 - SDATA (str);
 
-          /* Save STRP in IDX.  */
-          idx = strp - SDATA (string);
           name = Fintern (make_string ((char *) start, length_byte), Qnil);
 
         do_remap:
@@ -827,25 +819,16 @@ Otherwise, return a new string.  */)
               goto do_remap;
             }
 
-          /* Note the Fwhere_is_internal can GC, so we have to take
-             relocation of string contents into account.  */
-          strp = SDATA (string) + idx;
-          start = SDATA (string) + start_idx;
+          /* Take relocation of string contents into account.  */
+          strp = SDATA (str) + idx;
+          start = strp - length_byte - 1;
 
           if (NILP (tem))       /* but not on any keys */
             {
-              ptrdiff_t offset = bufp - buf;
-              if (STRING_BYTES_BOUND - 4 < bsize)
-                string_overflow ();
-              buf = xrealloc (buf, bsize += 4);
-              bufp = buf + offset;
               memcpy (bufp, "M-x ", 4);
               bufp += 4;
               nchars += 4;
-              if (multibyte)
-                length = multibyte_chars_in_text (start, length_byte);
-              else
-                length = length_byte;
+              length = multibyte_chars_in_text (start, length_byte);
               goto subst;
             }
           else
@@ -856,26 +839,20 @@ Otherwise, return a new string.  */)
         }
       /* \{foo} is replaced with a summary of the keymap (symbol-value foo).
          \<foo> just sets the keymap used for \[cmd].  */
-      else if (strp[0] == '\\' && (strp[1] == '{' || strp[1] == '<'))
+      else if (strp[0] == '\\' && (strp[1] == '{' || strp[1] == '<')
+               && (close_bracket
+                   = memchr (strp + 2, strp[1] == '{' ? '}' : '>',
+                             SDATA (str) + strbytes - (strp + 2))))
         {
          {
+          bool generate_summary = strp[1] == '{';
           /* This is for computing the SHADOWS arg for describe_map_tree.  */
           Lisp_Object active_maps = Fcurrent_active_maps (Qnil, Qnil);
           ptrdiff_t count = SPECPDL_INDEX ();
 
-          strp += 2;            /* skip \{ or \< */
-          start = strp;
-          ptrdiff_t start_idx = start - SDATA (string);
-
-          while ((strp - SDATA (string) < SBYTES (string))
-                 && *strp != '}' && *strp != '>')
-            strp++;
-
-          length_byte = strp - start;
-          strp++;                       /* skip } or > */
-
-          /* Save STRP in IDX.  */
-          idx = strp - SDATA (string);
+          start = strp + 2;
+          length_byte = close_bracket - start;
+          idx = close_bracket + 1 - SDATA (str);
 
           /* Get the value of the keymap in TEM, or nil if undefined.
              Do this while still in the user's current buffer
@@ -886,12 +863,7 @@ Otherwise, return a new string.  */)
             {
               tem = Fsymbol_value (name);
               if (! NILP (tem))
-                {
-                  tem = get_keymap (tem, 0, 1);
-                  /* Note that get_keymap can GC.  */
-                  strp = SDATA (string) + idx;
-                  start = SDATA (string) + start_idx;
-                }
+                tem = get_keymap (tem, 0, 1);
             }
 
           /* Now switch to a temp buffer.  */
@@ -912,9 +884,10 @@ Otherwise, return a new string.  */)
                                   SBYTES (name), 1);
               AUTO_STRING (msg_suffix, "', which is not currently defined.\n");
               insert1 (Fsubstitute_command_keys (msg_suffix));
-              if (start[-1] == '<') keymap = Qnil;
+              if (!generate_summary)
+                keymap = Qnil;
             }
-          else if (start[-1] == '<')
+          else if (!generate_summary)
             keymap = tem;
           else
             {
@@ -932,6 +905,7 @@ Otherwise, return a new string.  */)
          }
 
         subst_string:
+          tem = Fstring_make_multibyte (tem);
           start = SDATA (tem);
           length = SCHARS (tem);
           length_byte = SBYTES (tem);
@@ -941,15 +915,27 @@ Otherwise, return a new string.  */)
           changed = true;
           {
             ptrdiff_t offset = bufp - buf;
-            if (STRING_BYTES_BOUND - length_byte < bsize)
+            ptrdiff_t avail = bsize - offset;
+            ptrdiff_t need = strbytes - idx;
+            if (INT_ADD_WRAPV (need, length_byte + EXTRA_ROOM, &need))
               string_overflow ();
-            buf = xrealloc (buf, bsize += length_byte);
-            bufp = buf + offset;
+            if (avail < need)
+              {
+                abuf = xpalloc (abuf, &bsize, need - avail,
+                                STRING_BYTES_BOUND, 1);
+                if (buf == sbuf)
+                  memcpy (abuf, sbuf, offset);
+                buf = abuf;
+                bufp = buf + offset;
+              }
             memcpy (bufp, start, length_byte);
             bufp += length_byte;
             nchars += length;
-            /* Check STRING again in case gc relocated it.  */
-            strp = SDATA (string) + idx;
+
+            /* Take relocation of string contents into account.  */
+            strp = SDATA (str) + idx;
+
+            continue;
           }
         }
       else if ((strp[0] == '`' || strp[0] == '\'')
@@ -958,7 +944,7 @@ Otherwise, return a new string.  */)
           start = (unsigned char const *) (strp[0] == '`' ? uLSQM : uRSQM);
           length = 1;
           length_byte = sizeof uLSQM - 1;
-          idx = strp - SDATA (string) + 1;
+          idx = strp - SDATA (str) + 1;
           goto subst_quote;
         }
       else if (strp[0] == '`' && quoting_style == STRAIGHT_QUOTING_STYLE)
@@ -967,15 +953,14 @@ Otherwise, return a new string.  */)
           strp++;
           nchars++;
           changed = true;
+          continue;
         }
-      else
-        {
-          *bufp++ = *strp++;
-          if (multibyte)
-            while (! CHAR_HEAD_P (*strp))
-              *bufp++ = *strp++;
-          nchars++;
-        }
+
+      /* Copy one char.  */
+      do
+        *bufp++ = *strp++;
+      while (! CHAR_HEAD_P (*strp));
+      nchars++;
     }
 
   if (changed)                  /* don't bother if nothing substituted */
@@ -997,7 +982,7 @@ Otherwise, return a new string.  */)
     }
   else
     tem = string;
-  xfree (buf);
+  xfree (abuf);
   return tem;
 }