1 files changed, 404 insertions, 448 deletions

diff --git a/src/fns.c b/src/fns.c
index 65dc3b61f2b..4673fde28c7 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -39,9 +39,6 @@ along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
 #include "puresize.h"
 #include "gnutls.h"
 
-static void sort_vector_copy (Lisp_Object pred, ptrdiff_t len,
-			      Lisp_Object src[restrict VLA_ELEMS (len)],
-			      Lisp_Object dest[restrict VLA_ELEMS (len)]);
 enum equal_kind { EQUAL_NO_QUIT, EQUAL_PLAIN, EQUAL_INCLUDING_PROPERTIES };
 static bool internal_equal (Lisp_Object, Lisp_Object,
 			    enum equal_kind, int, Lisp_Object);
@@ -55,49 +52,24 @@ DEFUN ("identity", Fidentity, Sidentity, 1, 1, 0,
   return argument;
 }
 
+/* Return a random Lisp fixnum I in the range 0 <= I < LIM,
+   where LIM is taken from a positive fixnum.  */
 static Lisp_Object
-ccall2 (Lisp_Object (f) (ptrdiff_t nargs, Lisp_Object *args),
-        Lisp_Object arg1, Lisp_Object arg2)
+get_random_fixnum (EMACS_INT lim)
 {
-  Lisp_Object args[2] = {arg1, arg2};
-  return f (2, args);
-}
-
-static Lisp_Object
-get_random_bignum (Lisp_Object limit)
-{
-  /* This is a naive transcription into bignums of the fixnum algorithm.
-     I'd be quite surprised if that's anywhere near the best algorithm
-     for it.  */
-  while (true)
+  /* Return the remainder of a random integer R (in range 0..INTMASK)
+     divided by LIM, except reject the rare case where R is so close
+     to INTMASK that the remainder isn't random.  */
+  EMACS_INT difflim = INTMASK - lim + 1, diff, remainder;
+  do
     {
-      Lisp_Object val = make_fixnum (0);
-      Lisp_Object lim = limit;
-      int bits = 0;
-      int bitsperiteration = FIXNUM_BITS - 1;
-      do
-        {
-          /* Shift by one so it is a valid positive fixnum.  */
-          EMACS_INT rand = get_random () >> 1;
-          Lisp_Object lrand = make_fixnum (rand);
-          bits += bitsperiteration;
-          val = ccall2 (Flogior,
-                        Fash (val, make_fixnum (bitsperiteration)),
-                        lrand);
-          lim = Fash (lim, make_fixnum (- bitsperiteration));
-        }
-      while (!EQ (lim, make_fixnum (0)));
-      /* Return the remainder, except reject the rare case where
-	 get_random returns a number so close to INTMASK that the
-	 remainder isn't random.  */
-      Lisp_Object remainder = Frem (val, limit);
-      if (!NILP (ccall2 (Fleq,
-	                 ccall2 (Fminus, val, remainder),
-	                 ccall2 (Fminus,
-	                         Fash (make_fixnum (1), make_fixnum (bits)),
-	                         limit))))
-	return remainder;
+      EMACS_INT r = get_random ();
+      remainder = r % lim;
+      diff = r - remainder;
     }
+  while (difflim < diff);
+
+  return make_fixnum (remainder);
 }
 
 DEFUN ("random", Frandom, Srandom, 0, 1, 0,
@@ -111,32 +83,26 @@ With a string argument, set the seed based on the string's contents.
 See Info node `(elisp)Random Numbers' for more details.  */)
   (Lisp_Object limit)
 {
-  EMACS_INT val;
-
   if (EQ (limit, Qt))
     init_random ();
   else if (STRINGP (limit))
     seed_random (SSDATA (limit), SBYTES (limit));
-  if (BIGNUMP (limit))
+  else if (FIXNUMP (limit))
     {
-      if (0 > mpz_sgn (*xbignum_val (limit)))
-        xsignal2 (Qwrong_type_argument, Qnatnump, limit);
-      return get_random_bignum (limit);
+      EMACS_INT lim = XFIXNUM (limit);
+      if (lim <= 0)
+        xsignal1 (Qargs_out_of_range, limit);
+      return get_random_fixnum (lim);
+    }
+  else if (BIGNUMP (limit))
+    {
+      struct Lisp_Bignum *lim = XBIGNUM (limit);
+      if (mpz_sgn (*bignum_val (lim)) <= 0)
+        xsignal1 (Qargs_out_of_range, limit);
+      return get_random_bignum (lim);
     }
 
-  val = get_random ();
-  if (FIXNUMP (limit) && 0 < XFIXNUM (limit))
-    while (true)
-      {
-	/* Return the remainder, except reject the rare case where
-	   get_random returns a number so close to INTMASK that the
-	   remainder isn't random.  */
-	EMACS_INT remainder = val % XFIXNUM (limit);
-	if (val - remainder <= INTMASK - XFIXNUM (limit) + 1)
-	  return make_fixnum (remainder);
-	val = get_random ();
-      }
-  return make_ufixnum (val);
+  return make_ufixnum (get_random ());
 }
 
 /* Random data-structure functions.  */
@@ -475,15 +441,24 @@ Symbols are also allowed; their print names are used instead.  */)
 {
   if (SYMBOLP (string1))
     string1 = SYMBOL_NAME (string1);
+  else
+    CHECK_STRING (string1);
   if (SYMBOLP (string2))
     string2 = SYMBOL_NAME (string2);
-  CHECK_STRING (string1);
-  CHECK_STRING (string2);
+  else
+    CHECK_STRING (string2);
+
+  ptrdiff_t n = min (SCHARS (string1), SCHARS (string2));
+  if (!STRING_MULTIBYTE (string1) && !STRING_MULTIBYTE (string2))
+    {
+      /* Both arguments are unibyte (hot path).  */
+      int d = memcmp (SSDATA (string1), SSDATA (string2), n);
+      return d < 0 || (d == 0 && n < SCHARS (string2)) ? Qt : Qnil;
+    }
 
   ptrdiff_t i1 = 0, i1_byte = 0, i2 = 0, i2_byte = 0;
-  ptrdiff_t end = min (SCHARS (string1), SCHARS (string2));
 
-  while (i1 < end)
+  while (i1 < n)
     {
       /* When we find a mismatch, we must compare the
 	 characters, not just the bytes.  */
@@ -516,37 +491,9 @@ Symbols are also allowed; their print names are used instead.  */)
     string2 = SYMBOL_NAME (string2);
   CHECK_STRING (string1);
   CHECK_STRING (string2);
-  return string_version_cmp (string1, string2) < 0 ? Qt : Qnil;
-}
-
-/* Return negative, 0, positive if STRING1 is <, =, > STRING2 as per
-   string-version-lessp.  */
-int
-string_version_cmp (Lisp_Object string1, Lisp_Object string2)
-{
-  char *p1 = SSDATA (string1);
-  char *p2 = SSDATA (string2);
-  char *lim1 = p1 + SBYTES (string1);
-  char *lim2 = p2 + SBYTES (string2);
-  int cmp;
-
-  while ((cmp = filevercmp (p1, p2)) == 0)
-    {
-      /* If the strings are identical through their first null bytes,
-	 skip past identical prefixes and try again.  */
-      ptrdiff_t size = strlen (p1) + 1;
-      eassert (size == strlen (p2) + 1);
-      p1 += size;
-      p2 += size;
-      bool more1 = p1 <= lim1;
-      bool more2 = p2 <= lim2;
-      if (!more1)
-	return more2;
-      if (!more2)
-	return -1;
-    }
-
-  return cmp;
+  int cmp = filenvercmp (SSDATA (string1), SBYTES (string1),
+			 SSDATA (string2), SBYTES (string2));
+  return cmp < 0 ? Qt : Qnil;
 }
 
 DEFUN ("string-collate-lessp", Fstring_collate_lessp, Sstring_collate_lessp, 2, 4, 0,
@@ -643,18 +590,19 @@ Do NOT use this function to compare file names for equality.  */)
 }
 
 static Lisp_Object concat (ptrdiff_t nargs, Lisp_Object *args,
-			   enum Lisp_Type target_type, bool last_special);
+			   Lisp_Object last_tail, bool vector_target);
+static Lisp_Object concat_strings (ptrdiff_t nargs, Lisp_Object *args);
 
 Lisp_Object
 concat2 (Lisp_Object s1, Lisp_Object s2)
 {
-  return concat (2, ((Lisp_Object []) {s1, s2}), Lisp_String, 0);
+  return concat_strings (2, ((Lisp_Object []) {s1, s2}));
 }
 
 Lisp_Object
 concat3 (Lisp_Object s1, Lisp_Object s2, Lisp_Object s3)
 {
-  return concat (3, ((Lisp_Object []) {s1, s2, s3}), Lisp_String, 0);
+  return concat_strings (3, ((Lisp_Object []) {s1, s2, s3}));
 }
 
 DEFUN ("append", Fappend, Sappend, 0, MANY, 0,
@@ -665,7 +613,9 @@ The last argument is not copied, just used as the tail of the new list.
 usage: (append &rest SEQUENCES)  */)
   (ptrdiff_t nargs, Lisp_Object *args)
 {
-  return concat (nargs, args, Lisp_Cons, 1);
+  if (nargs == 0)
+    return Qnil;
+  return concat (nargs - 1, args, args[nargs - 1], false);
 }
 
 DEFUN ("concat", Fconcat, Sconcat, 0, MANY, 0,
@@ -678,7 +628,7 @@ to be `eq'.
 usage: (concat &rest SEQUENCES)  */)
   (ptrdiff_t nargs, Lisp_Object *args)
 {
-  return concat (nargs, args, Lisp_String, 0);
+  return concat_strings (nargs, args);
 }
 
 DEFUN ("vconcat", Fvconcat, Svconcat, 0, MANY, 0,
@@ -688,7 +638,7 @@ Each argument may be a list, vector or string.
 usage: (vconcat &rest SEQUENCES)   */)
   (ptrdiff_t nargs, Lisp_Object *args)
 {
-  return concat (nargs, args, Lisp_Vectorlike, 0);
+  return concat (nargs, args, Qnil, true);
 }
 
 
@@ -702,16 +652,48 @@ the same empty object instead of its copy.  */)
 {
   if (NILP (arg)) return arg;
 
-  if (RECORDP (arg))
+  if (CONSP (arg))
     {
-      return Frecord (PVSIZE (arg), XVECTOR (arg)->contents);
+      Lisp_Object val = Fcons (XCAR (arg), Qnil);
+      Lisp_Object prev = val;
+      Lisp_Object tail = XCDR (arg);
+      FOR_EACH_TAIL (tail)
+	{
+	  Lisp_Object c = Fcons (XCAR (tail), Qnil);
+	  XSETCDR (prev, c);
+	  prev = c;
+	}
+      CHECK_LIST_END (tail, tail);
+      return val;
     }
 
-  if (CHAR_TABLE_P (arg))
+  if (STRINGP (arg))
     {
-      return copy_char_table (arg);
+      ptrdiff_t bytes = SBYTES (arg);
+      ptrdiff_t chars = SCHARS (arg);
+      Lisp_Object val = STRING_MULTIBYTE (arg)
+	? make_uninit_multibyte_string (chars, bytes)
+	: make_uninit_string (bytes);
+      memcpy (SDATA (val), SDATA (arg), bytes);
+      INTERVAL ivs = string_intervals (arg);
+      if (ivs)
+	{
+	  INTERVAL copy = copy_intervals (ivs, 0, chars);
+	  set_interval_object (copy, val);
+	  set_string_intervals (val, copy);
+	}
+      return val;
     }
 
+  if (VECTORP (arg))
+    return Fvector (ASIZE (arg), XVECTOR (arg)->contents);
+
+  if (RECORDP (arg))
+    return Frecord (PVSIZE (arg), XVECTOR (arg)->contents);
+
+  if (CHAR_TABLE_P (arg))
+    return copy_char_table (arg);
+
   if (BOOL_VECTOR_P (arg))
     {
       EMACS_INT nbits = bool_vector_size (arg);
@@ -721,13 +703,10 @@ the same empty object instead of its copy.  */)
       return val;
     }
 
-  if (!CONSP (arg) && !VECTORP (arg) && !STRINGP (arg))
-    wrong_type_argument (Qsequencep, arg);
-
-  return concat (1, &arg, XTYPE (arg), 0);
+  wrong_type_argument (Qsequencep, arg);
 }
 
-/* This structure holds information of an argument of `concat' that is
+/* This structure holds information of an argument of `concat_strings' that is
    a string and has text properties to be copied.  */
 struct textprop_rec
 {
@@ -737,278 +716,308 @@ struct textprop_rec
 };
 
 static Lisp_Object
-concat (ptrdiff_t nargs, Lisp_Object *args,
-	enum Lisp_Type target_type, bool last_special)
+concat_strings (ptrdiff_t nargs, Lisp_Object *args)
 {
-  Lisp_Object val;
-  Lisp_Object tail;
-  Lisp_Object this;
-  ptrdiff_t toindex;
-  ptrdiff_t toindex_byte = 0;
-  EMACS_INT result_len;
-  EMACS_INT result_len_byte;
-  ptrdiff_t argnum;
-  Lisp_Object last_tail;
-  Lisp_Object prev;
-  bool some_multibyte;
-  /* When we make a multibyte string, we can't copy text properties
-     while concatenating each string because the length of resulting
-     string can't be decided until we finish the whole concatenation.
-     So, we record strings that have text properties to be copied
-     here, and copy the text properties after the concatenation.  */
-  struct textprop_rec  *textprops = NULL;
-  /* Number of elements in textprops.  */
-  ptrdiff_t num_textprops = 0;
   USE_SAFE_ALLOCA;
 
-  tail = Qnil;
-
-  /* In append, the last arg isn't treated like the others */
-  if (last_special && nargs > 0)
-    {
-      nargs--;
-      last_tail = args[nargs];
-    }
-  else
-    last_tail = Qnil;
-
-  /* Check each argument.  */
-  for (argnum = 0; argnum < nargs; argnum++)
-    {
-      this = args[argnum];
-      if (!(CONSP (this) || NILP (this) || VECTORP (this) || STRINGP (this)
-	    || COMPILEDP (this) || BOOL_VECTOR_P (this)))
-	wrong_type_argument (Qsequencep, this);
-    }
-
-  /* Compute total length in chars of arguments in RESULT_LEN.
-     If desired output is a string, also compute length in bytes
-     in RESULT_LEN_BYTE, and determine in SOME_MULTIBYTE
+  /* Check types and compute total length in chars of arguments in RESULT_LEN,
+     length in bytes in RESULT_LEN_BYTE, and determine in DEST_MULTIBYTE
      whether the result should be a multibyte string.  */
-  result_len_byte = 0;
-  result_len = 0;
-  some_multibyte = 0;
-  for (argnum = 0; argnum < nargs; argnum++)
+  EMACS_INT result_len = 0;
+  EMACS_INT result_len_byte = 0;
+  bool dest_multibyte = false;
+  bool some_unibyte = false;
+  for (ptrdiff_t i = 0; i < nargs; i++)
     {
+      Lisp_Object arg = args[i];
       EMACS_INT len;
-      this = args[argnum];
-      len = XFIXNAT (Flength (this));
-      if (target_type == Lisp_String)
-	{
-	  /* We must count the number of bytes needed in the string
-	     as well as the number of characters.  */
-	  ptrdiff_t i;
-	  Lisp_Object ch;
-	  int c;
-	  ptrdiff_t this_len_byte;
 
-	  if (VECTORP (this) || COMPILEDP (this))
-	    for (i = 0; i < len; i++)
-	      {
-		ch = AREF (this, i);
-		CHECK_CHARACTER (ch);
-		c = XFIXNAT (ch);
-		this_len_byte = CHAR_BYTES (c);
-		if (STRING_BYTES_BOUND - result_len_byte < this_len_byte)
-		  string_overflow ();
-		result_len_byte += this_len_byte;
-		if (! ASCII_CHAR_P (c) && ! CHAR_BYTE8_P (c))
-		  some_multibyte = 1;
-	      }
-	  else if (BOOL_VECTOR_P (this) && bool_vector_size (this) > 0)
-	    wrong_type_argument (Qintegerp, Faref (this, make_fixnum (0)));
-	  else if (CONSP (this))
-	    for (; CONSP (this); this = XCDR (this))
-	      {
-		ch = XCAR (this);
-		CHECK_CHARACTER (ch);
-		c = XFIXNAT (ch);
-		this_len_byte = CHAR_BYTES (c);
-		if (STRING_BYTES_BOUND - result_len_byte < this_len_byte)
-		  string_overflow ();
-		result_len_byte += this_len_byte;
-		if (! ASCII_CHAR_P (c) && ! CHAR_BYTE8_P (c))
-		  some_multibyte = 1;
-	      }
-	  else if (STRINGP (this))
+      /* We must count the number of bytes needed in the string
+	 as well as the number of characters.  */
+
+      if (STRINGP (arg))
+	{
+	  ptrdiff_t arg_len_byte = SBYTES (arg);
+	  len = SCHARS (arg);
+	  if (STRING_MULTIBYTE (arg))
+	    dest_multibyte = true;
+	  else
+	    some_unibyte = true;
+	  if (STRING_BYTES_BOUND - result_len_byte < arg_len_byte)
+	    string_overflow ();
+	  result_len_byte += arg_len_byte;
+	}
+      else if (VECTORP (arg))
+	{
+	  len = ASIZE (arg);
+	  ptrdiff_t arg_len_byte = 0;
+	  for (ptrdiff_t j = 0; j < len; j++)
 	    {
-	      if (STRING_MULTIBYTE (this))
-		{
-		  some_multibyte = 1;
-		  this_len_byte = SBYTES (this);
-		}
-	      else
-		this_len_byte = count_size_as_multibyte (SDATA (this),
-							 SCHARS (this));
-	      if (STRING_BYTES_BOUND - result_len_byte < this_len_byte)
-		string_overflow ();
-	      result_len_byte += this_len_byte;
+	      Lisp_Object ch = AREF (arg, j);
+	      CHECK_CHARACTER (ch);
+	      int c = XFIXNAT (ch);
+	      arg_len_byte += CHAR_BYTES (c);
+	      if (!ASCII_CHAR_P (c) && !CHAR_BYTE8_P (c))
+		dest_multibyte = true;
+	    }
+	  if (STRING_BYTES_BOUND - result_len_byte < arg_len_byte)
+	    string_overflow ();
+	  result_len_byte += arg_len_byte;
+	}
+      else if (NILP (arg))
+	continue;
+      else if (CONSP (arg))
+	{
+	  len = XFIXNAT (Flength (arg));
+	  ptrdiff_t arg_len_byte = 0;
+	  for (; CONSP (arg); arg = XCDR (arg))
+	    {
+	      Lisp_Object ch = XCAR (arg);
+	      CHECK_CHARACTER (ch);
+	      int c = XFIXNAT (ch);
+	      arg_len_byte += CHAR_BYTES (c);
+	      if (!ASCII_CHAR_P (c) && !CHAR_BYTE8_P (c))
+		dest_multibyte = true;
 	    }
+	  if (STRING_BYTES_BOUND - result_len_byte < arg_len_byte)
+	    string_overflow ();
+	  result_len_byte += arg_len_byte;
 	}
+      else
+	wrong_type_argument (Qsequencep, arg);
 
       result_len += len;
       if (MOST_POSITIVE_FIXNUM < result_len)
 	memory_full (SIZE_MAX);
     }
 
-  if (! some_multibyte)
+  if (dest_multibyte && some_unibyte)
+    {
+      /* Non-ASCII characters in unibyte strings take two bytes when
+	 converted to multibyte -- count them and adjust the total.  */
+      for (ptrdiff_t i = 0; i < nargs; i++)
+	{
+	  Lisp_Object arg = args[i];
+	  if (STRINGP (arg) && !STRING_MULTIBYTE (arg))
+	    {
+	      ptrdiff_t bytes = SCHARS (arg);
+	      const unsigned char *s = SDATA (arg);
+	      ptrdiff_t nonascii = 0;
+	      for (ptrdiff_t j = 0; j < bytes; j++)
+		nonascii += s[j] >> 7;
+	      if (STRING_BYTES_BOUND - result_len_byte < nonascii)
+		string_overflow ();
+	      result_len_byte += nonascii;
+	    }
+	}
+    }
+
+  if (!dest_multibyte)
     result_len_byte = result_len;
 
   /* Create the output object.  */
-  if (target_type == Lisp_Cons)
-    val = Fmake_list (make_fixnum (result_len), Qnil);
-  else if (target_type == Lisp_Vectorlike)
-    val = make_nil_vector (result_len);
-  else if (some_multibyte)
-    val = make_uninit_multibyte_string (result_len, result_len_byte);
-  else
-    val = make_uninit_string (result_len);
-
-  /* In `append', if all but last arg are nil, return last arg.  */
-  if (target_type == Lisp_Cons && NILP (val))
-    return last_tail;
+  Lisp_Object result = dest_multibyte
+    ? make_uninit_multibyte_string (result_len, result_len_byte)
+    : make_uninit_string (result_len);
 
   /* Copy the contents of the args into the result.  */
-  if (CONSP (val))
-    tail = val, toindex = -1; /* -1 in toindex is flag we are making a list */
-  else
-    toindex = 0, toindex_byte = 0;
+  ptrdiff_t toindex = 0;
+  ptrdiff_t toindex_byte = 0;
 
-  prev = Qnil;
-  if (STRINGP (val))
-    SAFE_NALLOCA (textprops, 1, nargs);
+  /* When we make a multibyte string, we can't copy text properties
+     while concatenating each string because the length of resulting
+     string can't be decided until we finish the whole concatenation.
+     So, we record strings that have text properties to be copied
+     here, and copy the text properties after the concatenation.  */
+  struct textprop_rec *textprops;
+  /* Number of elements in textprops.  */
+  ptrdiff_t num_textprops = 0;
+  SAFE_NALLOCA (textprops, 1, nargs);
 
-  for (argnum = 0; argnum < nargs; argnum++)
+  for (ptrdiff_t i = 0; i < nargs; i++)
     {
-      Lisp_Object thislen;
-      ptrdiff_t thisleni = 0;
-      ptrdiff_t thisindex = 0;
-      ptrdiff_t thisindex_byte = 0;
-
-      this = args[argnum];
-      if (!CONSP (this))
-	thislen = Flength (this), thisleni = XFIXNUM (thislen);
-
-      /* Between strings of the same kind, copy fast.  */
-      if (STRINGP (this) && STRINGP (val)
-	  && STRING_MULTIBYTE (this) == some_multibyte)
+      Lisp_Object arg = args[i];
+      if (STRINGP (arg))
 	{
-	  ptrdiff_t thislen_byte = SBYTES (this);
-
-	  memcpy (SDATA (val) + toindex_byte, SDATA (this), SBYTES (this));
-	  if (string_intervals (this))
+	  if (string_intervals (arg))
 	    {
-	      textprops[num_textprops].argnum = argnum;
+	      textprops[num_textprops].argnum = i;
 	      textprops[num_textprops].from = 0;
-	      textprops[num_textprops++].to = toindex;
+	      textprops[num_textprops].to = toindex;
+	      num_textprops++;
+	    }
+	  ptrdiff_t nchars = SCHARS (arg);
+	  if (STRING_MULTIBYTE (arg) == dest_multibyte)
+	    {
+	      /* Between strings of the same kind, copy fast.  */
+	      ptrdiff_t arg_len_byte = SBYTES (arg);
+	      memcpy (SDATA (result) + toindex_byte, SDATA (arg), arg_len_byte);
+	      toindex_byte += arg_len_byte;
+	    }
+	  else
+	    {
+	      /* Copy a single-byte string to a multibyte string.  */
+	      toindex_byte += copy_text (SDATA (arg),
+					 SDATA (result) + toindex_byte,
+					 nchars, 0, 1);
 	    }
-	  toindex_byte += thislen_byte;
-	  toindex += thisleni;
+	  toindex += nchars;
 	}
-      /* Copy a single-byte string to a multibyte string.  */
-      else if (STRINGP (this) && STRINGP (val))
+      else if (VECTORP (arg))
 	{
-	  if (string_intervals (this))
+	  ptrdiff_t len = ASIZE (arg);
+	  for (ptrdiff_t j = 0; j < len; j++)
 	    {
-	      textprops[num_textprops].argnum = argnum;
-	      textprops[num_textprops].from = 0;
-	      textprops[num_textprops++].to = toindex;
+	      int c = XFIXNAT (AREF (arg, j));
+	      if (dest_multibyte)
+		toindex_byte += CHAR_STRING (c, SDATA (result) + toindex_byte);
+	      else
+		SSET (result, toindex_byte++, c);
+	      toindex++;
 	    }
-	  toindex_byte += copy_text (SDATA (this),
-				     SDATA (val) + toindex_byte,
-				     SCHARS (this), 0, 1);
-	  toindex += thisleni;
 	}
       else
-	/* Copy element by element.  */
-	while (1)
+	for (Lisp_Object tail = arg; !NILP (tail); tail = XCDR (tail))
 	  {
-	    register Lisp_Object elt;
-
-	    /* Fetch next element of `this' arg into `elt', or break if
-	       `this' is exhausted. */
-	    if (NILP (this)) break;
-	    if (CONSP (this))
-	      elt = XCAR (this), this = XCDR (this);
-	    else if (thisindex >= thisleni)
-	      break;
-	    else if (STRINGP (this))
-	      {
-		int c;
-		if (STRING_MULTIBYTE (this))
-		  c = fetch_string_char_advance_no_check (this, &thisindex,
-							  &thisindex_byte);
-		else
-		  {
-		    c = SREF (this, thisindex); thisindex++;
-		    if (some_multibyte && !ASCII_CHAR_P (c))
-		      c = BYTE8_TO_CHAR (c);
-		  }
-		XSETFASTINT (elt, c);
-	      }
-	    else if (BOOL_VECTOR_P (this))
-	      {
-		elt = bool_vector_ref (this, thisindex);
-		thisindex++;
-	      }
+	    int c = XFIXNAT (XCAR (tail));
+	    if (dest_multibyte)
+	      toindex_byte += CHAR_STRING (c, SDATA (result) + toindex_byte);
 	    else
-	      {
-		elt = AREF (this, thisindex);
-		thisindex++;
-	      }
-
-	    /* Store this element into the result.  */
-	    if (toindex < 0)
-	      {
-		XSETCAR (tail, elt);
-		prev = tail;
-		tail = XCDR (tail);
-	      }
-	    else if (VECTORP (val))
-	      {
-		ASET (val, toindex, elt);
-		toindex++;
-	      }
-	    else
-	      {
-		int c;
-		CHECK_CHARACTER (elt);
-		c = XFIXNAT (elt);
-		if (some_multibyte)
-		  toindex_byte += CHAR_STRING (c, SDATA (val) + toindex_byte);
-		else
-		  SSET (val, toindex_byte++, c);
-		toindex++;
-	      }
+	      SSET (result, toindex_byte++, c);
+	    toindex++;
 	  }
     }
-  if (!NILP (prev))
-    XSETCDR (prev, last_tail);
 
   if (num_textprops > 0)
     {
-      Lisp_Object props;
       ptrdiff_t last_to_end = -1;
-
-      for (argnum = 0; argnum < num_textprops; argnum++)
+      for (ptrdiff_t i = 0; i < num_textprops; i++)
 	{
-	  this = args[textprops[argnum].argnum];
-	  props = text_property_list (this,
-				      make_fixnum (0),
-				      make_fixnum (SCHARS (this)),
-				      Qnil);
+	  Lisp_Object arg = args[textprops[i].argnum];
+	  Lisp_Object props = text_property_list (arg,
+						  make_fixnum (0),
+						  make_fixnum (SCHARS (arg)),
+						  Qnil);
 	  /* If successive arguments have properties, be sure that the
 	     value of `composition' property be the copy.  */
-	  if (last_to_end == textprops[argnum].to)
+	  if (last_to_end == textprops[i].to)
 	    make_composition_value_copy (props);
-	  add_text_properties_from_list (val, props,
-					 make_fixnum (textprops[argnum].to));
-	  last_to_end = textprops[argnum].to + SCHARS (this);
+	  add_text_properties_from_list (result, props,
+					 make_fixnum (textprops[i].to));
+	  last_to_end = textprops[i].to + SCHARS (arg);
 	}
     }
 
   SAFE_FREE ();
-  return val;
+  return result;
+}
+
+/* Concatenate sequences into a list or vector. */
+
+Lisp_Object
+concat (ptrdiff_t nargs, Lisp_Object *args, Lisp_Object last_tail,
+	bool vector_target)
+{
+  /* Check argument types and compute total length of arguments.  */
+  EMACS_INT result_len = 0;
+  for (ptrdiff_t i = 0; i < nargs; i++)
+    {
+      Lisp_Object arg = args[i];
+      if (!(CONSP (arg) || NILP (arg) || VECTORP (arg) || STRINGP (arg)
+	    || COMPILEDP (arg) || BOOL_VECTOR_P (arg)))
+	wrong_type_argument (Qsequencep, arg);
+      EMACS_INT len = XFIXNAT (Flength (arg));
+      result_len += len;
+      if (MOST_POSITIVE_FIXNUM < result_len)
+	memory_full (SIZE_MAX);
+    }
+
+  /* When the target is a list, return the tail directly if all other
+     arguments are empty.  */
+  if (!vector_target && result_len == 0)
+    return last_tail;
+
+  /* Create the output object.  */
+  Lisp_Object result = vector_target
+    ? make_nil_vector (result_len)
+    : Fmake_list (make_fixnum (result_len), Qnil);
+
+  /* Copy the contents of the args into the result.  */
+  Lisp_Object tail = Qnil;
+  ptrdiff_t toindex = 0;
+  if (CONSP (result))
+    {
+      tail = result;
+      toindex = -1;   /* -1 in toindex is flag we are making a list */
+    }
+
+  Lisp_Object prev = Qnil;
+
+  for (ptrdiff_t i = 0; i < nargs; i++)
+    {
+      ptrdiff_t arglen = 0;
+      ptrdiff_t argindex = 0;
+      ptrdiff_t argindex_byte = 0;
+
+      Lisp_Object arg = args[i];
+      if (!CONSP (arg))
+	arglen = XFIXNUM (Flength (arg));
+
+      /* Copy element by element.  */
+      while (1)
+	{
+	  /* Fetch next element of `arg' arg into `elt', or break if
+	     `arg' is exhausted. */
+	  Lisp_Object elt;
+	  if (CONSP (arg))
+	    {
+	      elt = XCAR (arg);
+	      arg = XCDR (arg);
+	    }
+	  else if (NILP (arg) || argindex >= arglen)
+	    break;
+	  else if (STRINGP (arg))
+	    {
+	      int c;
+	      if (STRING_MULTIBYTE (arg))
+		c = fetch_string_char_advance_no_check (arg, &argindex,
+							&argindex_byte);
+	      else
+		{
+		  c = SREF (arg, argindex);
+		  argindex++;
+		}
+	      XSETFASTINT (elt, c);
+	    }
+	  else if (BOOL_VECTOR_P (arg))
+	    {
+	      elt = bool_vector_ref (arg, argindex);
+	      argindex++;
+	    }
+	  else
+	    {
+	      elt = AREF (arg, argindex);
+	      argindex++;
+	    }
+
+	  /* Store this element into the result.  */
+	  if (toindex < 0)
+	    {
+	      XSETCAR (tail, elt);
+	      prev = tail;
+	      tail = XCDR (tail);
+	    }
+	  else
+	    {
+	      ASET (result, toindex, elt);
+	      toindex++;
+	    }
+	}
+    }
+  if (!NILP (prev))
+    XSETCDR (prev, last_tail);
+
+  return result;
 }
 
 static Lisp_Object string_char_byte_cache_string;
@@ -1380,7 +1389,7 @@ Elements of ALIST that are not conses are also shared.  */)
 {
   if (NILP (alist))
     return alist;
-  alist = concat (1, &alist, Lisp_Cons, false);
+  alist = Fcopy_sequence (alist);
   for (Lisp_Object tem = alist; !NILP (tem); tem = XCDR (tem))
     {
       Lisp_Object car = XCAR (tem);
@@ -2104,8 +2113,11 @@ See also the function `nreverse', which is used more often.  */)
   return new;
 }
 
-/* Sort LIST using PREDICATE, preserving original order of elements
-   considered as equal.  */
+
+/* Stably sort LIST ordered by PREDICATE using the TIMSORT
+   algorithm. This converts the list to a vector, sorts the vector,
+   and returns the result converted back to a list.  The input list is
+   destructively reused to hold the sorted result.  */
 
 static Lisp_Object
 sort_list (Lisp_Object list, Lisp_Object predicate)
@@ -2113,112 +2125,43 @@ sort_list (Lisp_Object list, Lisp_Object predicate)
   ptrdiff_t length = list_length (list);
   if (length < 2)
     return list;
-
-  Lisp_Object tem = Fnthcdr (make_fixnum (length / 2 - 1), list);
-  Lisp_Object back = Fcdr (tem);
-  Fsetcdr (tem, Qnil);
-
-  return merge (Fsort (list, predicate), Fsort (back, predicate), predicate);
-}
-
-/* Using PRED to compare, return whether A and B are in order.
-   Compare stably when A appeared before B in the input.  */
-static bool
-inorder (Lisp_Object pred, Lisp_Object a, Lisp_Object b)
-{
-  return NILP (call2 (pred, b, a));
-}
-
-/* Using PRED to compare, merge from ALEN-length A and BLEN-length B
-   into DEST.  Argument arrays must be nonempty and must not overlap,
-   except that B might be the last part of DEST.  */
-static void
-merge_vectors (Lisp_Object pred,
-	       ptrdiff_t alen, Lisp_Object const a[restrict VLA_ELEMS (alen)],
-	       ptrdiff_t blen, Lisp_Object const b[VLA_ELEMS (blen)],
-	       Lisp_Object dest[VLA_ELEMS (alen + blen)])
-{
-  eassume (0 < alen && 0 < blen);
-  Lisp_Object const *alim = a + alen;
-  Lisp_Object const *blim = b + blen;
-
-  while (true)
+  else
     {
-      if (inorder (pred, a[0], b[0]))
+      Lisp_Object *result;
+      USE_SAFE_ALLOCA;
+      SAFE_ALLOCA_LISP (result, length);
+      Lisp_Object tail = list;
+      for (ptrdiff_t i = 0; i < length; i++)
 	{
-	  *dest++ = *a++;
-	  if (a == alim)
-	    {
-	      if (dest != b)
-		memcpy (dest, b, (blim - b) * sizeof *dest);
-	      return;
-	    }
+	  result[i] = Fcar (tail);
+	  tail = XCDR (tail);
 	}
-      else
+      tim_sort (predicate, result, length);
+
+      ptrdiff_t i = 0;
+      tail = list;
+      while (CONSP (tail))
 	{
-	  *dest++ = *b++;
-	  if (b == blim)
-	    {
-	      memcpy (dest, a, (alim - a) * sizeof *dest);
-	      return;
-	    }
+	  XSETCAR (tail, result[i]);
+	  tail = XCDR (tail);
+	  i++;
 	}
+      SAFE_FREE ();
+      return list;
     }
 }
 
-/* Using PRED to compare, sort LEN-length VEC in place, using TMP for
-   temporary storage.  LEN must be at least 2.  */
-static void
-sort_vector_inplace (Lisp_Object pred, ptrdiff_t len,
-		     Lisp_Object vec[restrict VLA_ELEMS (len)],
-		     Lisp_Object tmp[restrict VLA_ELEMS (len >> 1)])
-{
-  eassume (2 <= len);
-  ptrdiff_t halflen = len >> 1;
-  sort_vector_copy (pred, halflen, vec, tmp);
-  if (1 < len - halflen)
-    sort_vector_inplace (pred, len - halflen, vec + halflen, vec);
-  merge_vectors (pred, halflen, tmp, len - halflen, vec + halflen, vec);
-}
-
-/* Using PRED to compare, sort from LEN-length SRC into DST.
-   Len must be positive.  */
-static void
-sort_vector_copy (Lisp_Object pred, ptrdiff_t len,
-		  Lisp_Object src[restrict VLA_ELEMS (len)],
-		  Lisp_Object dest[restrict VLA_ELEMS (len)])
-{
-  eassume (0 < len);
-  ptrdiff_t halflen = len >> 1;
-  if (halflen < 1)
-    dest[0] = src[0];
-  else
-    {
-      if (1 < halflen)
-	sort_vector_inplace (pred, halflen, src, dest);
-      if (1 < len - halflen)
-	sort_vector_inplace (pred, len - halflen, src + halflen, dest);
-      merge_vectors (pred, halflen, src, len - halflen, src + halflen, dest);
-    }
-}
-
-/* Sort VECTOR in place using PREDICATE, preserving original order of
-   elements considered as equal.  */
+/* Stably sort VECTOR ordered by PREDICATE using the TIMSORT
+   algorithm.  */
 
 static void
 sort_vector (Lisp_Object vector, Lisp_Object predicate)
 {
-  ptrdiff_t len = ASIZE (vector);
-  if (len < 2)
+  ptrdiff_t length = ASIZE (vector);
+  if (length < 2)
     return;
-  ptrdiff_t halflen = len >> 1;
-  Lisp_Object *tmp;
-  USE_SAFE_ALLOCA;
-  SAFE_ALLOCA_LISP (tmp, halflen);
-  for (ptrdiff_t i = 0; i < halflen; i++)
-    tmp[i] = make_fixnum (0);
-  sort_vector_inplace (predicate, len, XVECTOR (vector)->contents, tmp);
-  SAFE_FREE ();
+
+  tim_sort (predicate, XVECTOR (vector)->contents, length);
 }
 
 DEFUN ("sort", Fsort, Ssort, 2, 2, 0,
@@ -2264,7 +2207,7 @@ merge (Lisp_Object org_l1, Lisp_Object org_l2, Lisp_Object pred)
 	}
 
       Lisp_Object tem;
-      if (inorder (pred, Fcar (l1), Fcar (l2)))
+      if (!NILP (call2 (pred, Fcar (l1), Fcar (l2))))
 	{
 	  tem = l1;
 	  l1 = Fcdr (l1);
@@ -2569,6 +2512,13 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
 	}
     }
 
+  /* A symbol with position compares the contained symbol, and is
+     `equal' to the corresponding ordinary symbol.  */
+  if (SYMBOL_WITH_POS_P (o1))
+    o1 = SYMBOL_WITH_POS_SYM (o1);
+  if (SYMBOL_WITH_POS_P (o2))
+    o2 = SYMBOL_WITH_POS_SYM (o2);
+
   if (EQ (o1, o2))
     return true;
   if (XTYPE (o1) != XTYPE (o2))
@@ -2855,12 +2805,16 @@ mapcar1 (EMACS_INT leni, Lisp_Object *vals, Lisp_Object fn, Lisp_Object seq)
   return leni;
 }
 
-DEFUN ("mapconcat", Fmapconcat, Smapconcat, 3, 3, 0,
+DEFUN ("mapconcat", Fmapconcat, Smapconcat, 2, 3, 0,
        doc: /* Apply FUNCTION to each element of SEQUENCE, and concat the results as strings.
 In between each pair of results, stick in SEPARATOR.  Thus, " " as
   SEPARATOR results in spaces between the values returned by FUNCTION.
+
 SEQUENCE may be a list, a vector, a bool-vector, or a string.
-SEPARATOR must be a string, a vector, or a list of characters.
+
+Optional argument SEPARATOR must be a string, a vector, or a list of
+characters; nil stands for the empty string.
+
 FUNCTION must be a function of one argument, and must return a value
   that is a sequence of characters: either a string, or a vector or
   list of numbers that are valid character codepoints.  */)
@@ -2961,6 +2915,9 @@ it does up to one space will be removed.
 The user must confirm the answer with RET, and can edit it until it
 has been confirmed.
 
+If the `use-short-answers' variable is non-nil, instead of asking for
+\"yes\" or \"no\", this function will ask for \"y\" or \"n\".
+
 If dialog boxes are supported, a dialog box will be used
 if `last-nonmenu-event' is nil, and `use-dialog-box' is non-nil.  */)
   (Lisp_Object prompt)
@@ -2987,7 +2944,7 @@ if `last-nonmenu-event' is nil, and `use-dialog-box' is non-nil.  */)
   AUTO_STRING (yes_or_no, "(yes or no) ");
   prompt = CALLN (Fconcat, prompt, yes_or_no);
 
-  ptrdiff_t count = SPECPDL_INDEX ();
+  specpdl_ref count = SPECPDL_INDEX ();
   specbind (Qenable_recursive_minibuffers, Qt);
 
   while (1)
@@ -3149,7 +3106,7 @@ FILENAME are suppressed.  */)
 
   if (NILP (tem))
     {
-      ptrdiff_t count = SPECPDL_INDEX ();
+      specpdl_ref count = SPECPDL_INDEX ();
       int nesting = 0;
 
       /* This is to make sure that loadup.el gives a clear picture
@@ -3176,12 +3133,8 @@ FILENAME are suppressed.  */)
       record_unwind_protect (require_unwind, require_nesting_list);
       require_nesting_list = Fcons (feature, require_nesting_list);
 
-      /* Value saved here is to be restored into Vautoload_queue */
-      record_unwind_protect (un_autoload, Vautoload_queue);
-      Vautoload_queue = Qt;
-
       /* Load the file.  */
-      tem = save_match_data_load
+      tem = load_with_autoload_queue
 	(NILP (filename) ? Fsymbol_name (feature) : filename,
 	 noerror, Qt, Qnil, (NILP (filename) ? Qt : Qnil));
 
@@ -3203,8 +3156,6 @@ FILENAME are suppressed.  */)
                    SDATA (tem3), tem2);
         }
 
-      /* Once loading finishes, don't undo it.  */
-      Vautoload_queue = Qt;
       feature = unbind_to (count, feature);
     }
 
@@ -3649,7 +3600,7 @@ base64_encode_1 (const char *from, char *to, ptrdiff_t length,
 	  c = string_char_and_length ((unsigned char *) from + i, &bytes);
 	  if (CHAR_BYTE8_P (c))
 	    c = CHAR_TO_BYTE8 (c);
-	  else if (c >= 256)
+	  else if (c >= 128)
 	    return -1;
 	  i += bytes;
 	}
@@ -3692,7 +3643,7 @@ base64_encode_1 (const char *from, char *to, ptrdiff_t length,
 	  c = string_char_and_length ((unsigned char *) from + i, &bytes);
 	  if (CHAR_BYTE8_P (c))
 	    c = CHAR_TO_BYTE8 (c);
-	  else if (c >= 256)
+	  else if (c >= 128)
 	    return -1;
 	  i += bytes;
 	}
@@ -3717,7 +3668,7 @@ base64_encode_1 (const char *from, char *to, ptrdiff_t length,
 	  c = string_char_and_length ((unsigned char *) from + i, &bytes);
 	  if (CHAR_BYTE8_P (c))
 	    c = CHAR_TO_BYTE8 (c);
-	  else if (c >= 256)
+	  else if (c >= 128)
 	    return -1;
 	  i += bytes;
 	}
@@ -4156,7 +4107,7 @@ hash_table_user_defined_call (ptrdiff_t nargs, Lisp_Object *args,
 {
   if (!h->mutable)
     return Ffuncall (nargs, args);
-  ptrdiff_t count = inhibit_garbage_collection ();
+  specpdl_ref count = inhibit_garbage_collection ();
   record_unwind_protect_ptr (restore_mutability, h);
   h->mutable = false;
   return unbind_to (count, Ffuncall (nargs, args));
@@ -4198,13 +4149,15 @@ cmpfn_user_defined (Lisp_Object key1, Lisp_Object key2,
 static Lisp_Object
 hashfn_eq (Lisp_Object key, struct Lisp_Hash_Table *h)
 {
+  if (symbols_with_pos_enabled && SYMBOL_WITH_POS_P (key))
+    key = SYMBOL_WITH_POS_SYM (key);
   return make_ufixnum (XHASH (key) ^ XTYPE (key));
 }
 
 /* Ignore HT and return a hash code for KEY which uses 'equal' to compare keys.
    The hash code is at most INTMASK.  */
 
-Lisp_Object
+static Lisp_Object
 hashfn_equal (Lisp_Object key, struct Lisp_Hash_Table *h)
 {
   return make_ufixnum (sxhash (key));
@@ -4213,7 +4166,7 @@ hashfn_equal (Lisp_Object key, struct Lisp_Hash_Table *h)
 /* Ignore HT and return a hash code for KEY which uses 'eql' to compare keys.
    The hash code is at most INTMASK.  */
 
-Lisp_Object
+static Lisp_Object
 hashfn_eql (Lisp_Object key, struct Lisp_Hash_Table *h)
 {
   return (FLOATP (key) || BIGNUMP (key) ? hashfn_equal : hashfn_eq) (key, h);
@@ -4475,7 +4428,8 @@ hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object *hash)
 {
   ptrdiff_t start_of_bucket, i;
 
-  Lisp_Object hash_code = h->test.hashfn (key, h);
+  Lisp_Object hash_code;
+  hash_code = h->test.hashfn (key, h);
   if (hash)
     *hash = hash_code;
 
@@ -4912,6 +4866,8 @@ sxhash_obj (Lisp_Object obj, int depth)
 	    hash = sxhash_combine (hash, sxhash_obj (XOVERLAY (obj)->plist, depth));
 	    return SXHASH_REDUCE (hash);
 	  }
+	else if (symbols_with_pos_enabled && pvec_type == PVEC_SYMBOL_WITH_POS)
+	  return sxhash_obj (XSYMBOL_WITH_POS (obj)->sym, depth + 1);
 	else
 	  /* Others are 'equal' if they are 'eq', so take their
 	     address as hash.  */