From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Newsgroups: gmane.emacs.bugs Subject: bug#69709: `sort` interface improvement and universal ordering predicate Date: Sun, 10 Mar 2024 14:28:02 +0100 Message-ID: Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.15\)) Content-Type: multipart/mixed; boundary="Apple-Mail=_851F0DC0-20B0-4A64-958C-2AA810381534" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="19898"; mail-complaints-to="usenet@ciao.gmane.io" To: 69709@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Mar 10 14:28:57 2024 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1rjJEW-00055C-Tf for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 10 Mar 2024 14:28:57 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rjJE8-00082o-J3; Sun, 10 Mar 2024 09:28:32 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rjJE5-00082K-R1 for bug-gnu-emacs@gnu.org; Sun, 10 Mar 2024 09:28:29 -0400 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rjJE5-0004f9-If for bug-gnu-emacs@gnu.org; Sun, 10 Mar 2024 09:28:29 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1rjJEc-0006Pd-CQ for bug-gnu-emacs@gnu.org; Sun, 10 Mar 2024 09:29:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 10 Mar 2024 13:29:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 69709 X-GNU-PR-Package: emacs X-Debbugs-Original-To: Emacs Bug Report Original-Received: via spool by submit@debbugs.gnu.org id=B.171007732524623 (code B ref -1); Sun, 10 Mar 2024 13:29:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 10 Mar 2024 13:28:45 +0000 Original-Received: from localhost ([127.0.0.1]:35771 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rjJEL-0006P4-1e for submit@debbugs.gnu.org; Sun, 10 Mar 2024 09:28:45 -0400 Original-Received: from lists.gnu.org ([209.51.188.17]:60182) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rjJEI-0006Ov-6R for submit@debbugs.gnu.org; Sun, 10 Mar 2024 09:28:43 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rjJDk-0007zn-KC for bug-gnu-emacs@gnu.org; Sun, 10 Mar 2024 09:28:08 -0400 Original-Received: from mail-lj1-x22e.google.com ([2a00:1450:4864:20::22e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rjJDi-0004cQ-SE for bug-gnu-emacs@gnu.org; Sun, 10 Mar 2024 09:28:08 -0400 Original-Received: by mail-lj1-x22e.google.com with SMTP id 38308e7fff4ca-2d3fb16f1a9so45886221fa.0 for ; Sun, 10 Mar 2024 06:28:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710077284; x=1710682084; darn=gnu.org; h=to:date:message-id:subject:mime-version:from:sender:from:to:cc :subject:date:message-id:reply-to; bh=G+zUP0PaYfX56OdRB4bCbjPCrmBsCG9kB90rVyd2nB4=; b=NtcFWA6xJXnY/HEouuiTZXdj7P/NxhdV4eB/2QQQ/v2jW9kwD89ESpmX6sYUwVTcZw EQeuoq7/I4AYQTK9aA7WGBqw3FlOQI2XLq4iisTDEJY6oeXsPpKms3pFuRSiquBSVFRd ED2lMbLyuzVboEeQ+UAxtMyJPrkILNJXSqNbMpU5U7cj0ihheLHCUP/3mH61Ez4InP1p ku+n8fuBcj3JwjakqiLNvlXO28NBFxMM0QGfBZbsXmp9KrW4fOsJqwCt8Z+0eL0yyXXC MkQfEP20sQjRcAtNy08+SWs13oQpmh0X3nRNPInlwzK+fcZCqy2cGvX98L9dZUhDnAUa V3WQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710077284; x=1710682084; h=to:date:message-id:subject:mime-version:from:sender :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=G+zUP0PaYfX56OdRB4bCbjPCrmBsCG9kB90rVyd2nB4=; b=GfcxhJhITop2SFxMo/KSeTm3YusDFyVQV9/RGfU3NMLKVOMrUOQJeopAuFCNM0AE+6 43Pnrhnk04qKogVbW4zejgBG/Ce2z45HDZUmjPyjDnWdveihQkrD/I1O9nHIDQLZoiss k2GQo5BS02tTwYsf9zfGh724/br2amGmVVcCPvqKwPTn3UV7BjCTwj7F0Os4p1XEmjns 7+CXkIJ7riN7cuBesd61+WA8Jpb06pbM67cim/eM5AOlUmQNvsk7VB3NQoEZHtj16Eji V68v7j6RseMpMJ95L8XVQhkYo1so+nM8tw+0pUgj0t+lqKEvaBfOAd3ueLiDc0NdF81e phIw== X-Gm-Message-State: AOJu0Yx8hsZXaH/XKWG3f7Q0PyEzRMr3zTJDbwIjVIo8SHeI0cIUlHri tgV4NBh/Xa1Ztuhdb1UJSoRg3RFVz5NOelNyQpGqHQoG8f4H7MNRBw6FxfoW X-Google-Smtp-Source: AGHT+IH9K6+shuy3g9gVwoImQ0J6EQk1SZUxZm0vI/ZT0Ek8xHUxX7MpAYBl4jCMoFyiw4NsN+sxZg== X-Received: by 2002:a2e:2e06:0:b0:2d4:1302:4657 with SMTP id u6-20020a2e2e06000000b002d413024657mr1673668lju.17.1710077283767; Sun, 10 Mar 2024 06:28:03 -0700 (PDT) Original-Received: from smtpclient.apple (c80-217-1-132.bredband.tele2.se. [80.217.1.132]) by smtp.gmail.com with ESMTPSA id by10-20020a05651c1a0a00b002d2aa0b0d01sm669374ljb.82.2024.03.10.06.28.03 for (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Sun, 10 Mar 2024 06:28:03 -0700 (PDT) X-Mailer: Apple Mail (2.3654.120.0.1.15) Received-SPF: pass client-ip=2a00:1450:4864:20::22e; envelope-from=mattias.engdegard@gmail.com; helo=mail-lj1-x22e.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:281393 Archived-At: --Apple-Mail=_851F0DC0-20B0-4A64-958C-2AA810381534 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii The existing `sort` interface suffers from some usability problems: 1. Writing an ordering predicate is often difficult and error-prone, = even for very basic tasks such as selecting the field to sort on. It's = not uncommon to botch a predicate as simple as (lambda (a b) (< (f a) (f b))) which I've managed to do myself more than once. It gets particularly = messy when sorting on multiple fields. Having to write a custom comparison function for almost every occasion = also means that performance suffers. 2. Mutability by default is a bug magnet as well. To deal with the first problem, we could: * Add a universal ordering predicate that will compare two values of the = same type for many built-in types: numbers, strings, symbols, markers, = lists, vectors, records, and a few more. * Make this ordering the default. * Add a key (accessor) function argument, like that in the recent = `sort-on` interface, but built-in. This is important. These work very well together: the user does not need to write or even = choose an ordering predicate in most cases. Key functions are much less = error-prone to write, and with the lexicographic ordering of lists, = vectors and records, multi-key sorting is made much easier. A key function combined with a standard ordering can also be used to = optimise comparisons since we have all key values up front along with = how they should be compared. The original timsort code that we stole = from Python did this. As a starting point, a patch implementing a universal ordering predicate = is attached below. The proposed sorting function interface would be (new-sort seq &key key lessp destructive) because the keyword interface is easier to read and write than a = lengthening list of optional positional parameters, and can be extended = more gracefully. For example, it could be handy to have a `reversed` (or = `descending`) parameter. The parsing cost is not significant. Instead of inventing a new and rather meaningless function name, I = suggest we re-use `sort` and allow both (sort seq lessp) ; old-style (sort seq &key key lessp destructive) ; new-style since they are easy to distinguish, and let `destructive` default to = false in new-style calls, true in the old style. --Apple-Mail=_851F0DC0-20B0-4A64-958C-2AA810381534 Content-Disposition: attachment; filename=0001-value-less-p.patch Content-Type: application/octet-stream; x-unix-mode=0644; name="0001-value-less-p.patch" Content-Transfer-Encoding: quoted-printable =46rom=206980c8cf54a23eddf97ecf4881e43f9a49a18a55=20Mon=20Sep=2017=20= 00:00:00=202001=0AFrom:=20=3D?UTF-8?q?Mattias=3D20Engdeg=3DC3=3DA5rd?=3D=20= =0ADate:=20Sun,=2010=20Mar=202024=2013:18:22=20+0100=0A= Subject:=20[PATCH]=20value-less-p=0A=0A---=0A=20src/data.c=20=20=20=20=20= =20=20=20=20=20=20=20|=20=20=202=20+=0A=20src/fns.c=20=20=20=20=20=20=20=20= =20=20=20=20=20|=20226=20++++++++++++++++++++++++++++++++++++++++++=0A=20= test/src/fns-tests.el=20|=20122=20+++++++++++++++++++++++=0A=203=20files=20= changed,=20350=20insertions(+)=0A=0Adiff=20--git=20a/src/data.c=20= b/src/data.c=0Aindex=20df08eaf8102..8f3ba6438b9=20100644=0A---=20= a/src/data.c=0A+++=20b/src/data.c=0A@@=20-4039,6=20+4039,7=20@@=20= syms_of_data=20(void)=0A=20=20=20DEFSYM=20(Qminibuffer_quit,=20= "minibuffer-quit");=0A=20=20=20DEFSYM=20(Qwrong_length_argument,=20= "wrong-length-argument");=0A=20=20=20DEFSYM=20(Qwrong_type_argument,=20= "wrong-type-argument");=0A+=20=20DEFSYM=20(Qtype_mismatch,=20= "type-mismatch")=0A=20=20=20DEFSYM=20(Qargs_out_of_range,=20= "args-out-of-range");=0A=20=20=20DEFSYM=20(Qvoid_function,=20= "void-function");=0A=20=20=20DEFSYM=20(Qcyclic_function_indirection,=20= "cyclic-function-indirection");=0A@@=20-4130,6=20+4131,7=20@@=20#define=20= PUT_ERROR(sym,=20tail,=20msg)=09=09=09\=0A=20=20=20PUT_ERROR=20= (Quser_error,=20error_tail,=20"");=0A=20=20=20PUT_ERROR=20= (Qwrong_length_argument,=20error_tail,=20"Wrong=20length=20argument");=0A= =20=20=20PUT_ERROR=20(Qwrong_type_argument,=20error_tail,=20"Wrong=20= type=20argument");=0A+=20=20PUT_ERROR=20(Qtype_mismatch,=20error_tail,=20= "Types=20do=20not=20match");=0A=20=20=20PUT_ERROR=20(Qargs_out_of_range,=20= error_tail,=20"Args=20out=20of=20range");=0A=20=20=20PUT_ERROR=20= (Qvoid_function,=20error_tail,=0A=20=09=20=20=20=20=20"Symbol's=20= function=20definition=20is=20void");=0Adiff=20--git=20a/src/fns.c=20= b/src/fns.c=0Aindex=200a64e515402..cc017839996=20100644=0A---=20= a/src/fns.c=0A+++=20b/src/fns.c=0A@@=20-27,6=20+27,7=20@@=20Copyright=20= (C)=201985-2024=20Free=20Software=20Foundation,=20Inc.=0A=20#include=20= =0A=20#include=20=0A=20#include=20=0A+#include=20= =0A=20=0A=20#include=20"lisp.h"=0A=20#include=20"bignum.h"=0A@@=20= -2908,6=20+2909,230=20@@=20internal_equal=20(Lisp_Object=20o1,=20= Lisp_Object=20o2,=20enum=20equal_kind=20equal_kind,=0A=20=0A=20=20=20= return=20false;=0A=20}=0A+=0A+=0A+/*=20Return=20-1,=200=20or=201=20to=20= indicate=20whether=20ab=20in=20the=20sense=0A+=20=20= =20of=20value-less-p.=0A+=20=20=20In=20particular=200=20does=20not=20= mean=20equality=20in=20the=20sense=20of=20Fequal,=20only=0A+=20=20=20= that=20the=20arguments=20cannot=20be=20ordered=20yet=20they=20can=20be=20= compared=20(same=0A+=20=20=20type).=0A+=0A+=20=20=20If=20lessp_only=20is=20= true,=20then=20we=20may=20return=200=20instead=20of=201=20when=20a>b,=0A= +=20=20=20if=20this=20is=20faster.=20=20*/=0A+static=20int=0A= +value_less_p=20(Lisp_Object=20a,=20Lisp_Object=20b,=20int=20maxdepth,=20= bool=20lessp_only)=0A+{=0A+=20=20if=20(maxdepth=20<=200)=0A+=20=20=20=20= error=20("Maximum=20depth=20exceeded=20in=20comparison");=0A+=0A+=20= tail_recurse:=0A+=20=20/*=20Shortcut=20for=20a=20common=20case.=20=20*/=0A= +=20=20if=20(BASE_EQ=20(a,=20b))=0A+=20=20=20=20return=200;=0A+=0A+=20=20= switch=20(XTYPE=20(a))=0A+=20=20=20=20{=0A+=20=20=20=20case_Lisp_Int:=0A= +=20=20=20=20=20=20{=0A+=09EMACS_INT=20ia=20=3D=20XFIXNUM=20(a);=0A+=09= if=20(FIXNUMP=20(b))=0A+=09=20=20return=20ia=20<=20XFIXNUM=20(b)=20?=20= -1=20:=20ia=20>=20XFIXNUM=20(b);=0A+=09if=20(FLOATP=20(b))=0A+=09=20=20= return=20ia=20<=20XFLOAT_DATA=20(b)=20?=20-1=20:=20ia=20>=20XFLOAT_DATA=20= (b);=0A+=09if=20(BIGNUMP=20(b))=0A+=09=20=20return=20-mpz_sgn=20= (*xbignum_val=20(b));=0A+=20=20=20=20=20=20}=0A+=20=20=20=20=20=20goto=20= type_mismatch;=0A+=0A+=20=20=20=20case=20Lisp_Symbol:=0A+=20=20=20=20=20=20= if=20(BARE_SYMBOL_P=20(b))=0A+=09{=0A+=09=20=20struct=20Lisp_Symbol=20= *sa=20=3D=20XBARE_SYMBOL=20(a);=0A+=09=20=20struct=20Lisp_Symbol=20*sb=20= =3D=20XBARE_SYMBOL=20(b);=0A+=09=20=20if=20(!NILP=20(Fstring_lessp=20= (sa->u.s.name,=20sb->u.s.name)))=0A+=09=20=20=20=20return=20-1;=0A+=09=20= =20if=20(lessp_only)=0A+=09=20=20=20=20return=200;=0A+=09=20=20if=20= (sa->u.s.interned=20=3D=3D=20SYMBOL_INTERNED_IN_INITIAL_OBARRAY=0A+=09=20= =20=20=20=20=20&&=20sb->u.s.interned=20=3D=3D=20= SYMBOL_INTERNED_IN_INITIAL_OBARRAY)=0A+=09=20=20=20=20/*=20Both=20= symbols=20are=20interned=20in=20the=20initial=20obarray,=20so=20cannot=20= have=0A+=09=20=20=20=20=20=20=20equal=20names.=20=20*/=0A+=09=20=20=20=20= return=201;=0A+=09=20=20return=20NILP=20(Fequal=20(sa->u.s.name,=20= sb->u.s.name));=0A+=09}=0A+=20=20=20=20=20=20if=20(CONSP=20(b)=20&&=20= NILP=20(a))=0A+=09return=20-1;=0A+=20=20=20=20=20=20if=20(SYMBOLP=20(b))=0A= +=09{=0A+=09=20=20/*=20Slow-path=20branch=20when=20B=20is=20a=20= symbol-with-pos.=20=20*/=0A+=09=20=20if=20(!NILP=20(Fstring_lessp=20(a,=20= b)))=0A+=09=20=20=20=20return=20-1;=0A+=09=20=20if=20(lessp_only)=0A+=09=20= =20=20=20return=200;=0A+=09=20=20return=20NILP=20(Fequal=20(a,=20b));=0A= +=09}=0A+=20=20=20=20=20=20goto=20type_mismatch;=0A+=0A+=20=20=20=20case=20= Lisp_String:=0A+=20=20=20=20=20=20if=20(STRINGP=20(b))=0A+=09{=0A+=09=20=20= if=20(!NILP=20(Fstring_lessp=20(a,=20b)))=0A+=09=20=20=20=20return=20-1;=0A= +=09=20=20/*=20FIXME:=20We=20would=20go=20even=20faster,=20and=20= wouldn't=20need=20the=0A+=09=20=20=20=20=20lessp_only=20hack,=20if=20we=20= had=20a=20string=20comparison=20with=20-1/0/1=20result.=0A+=09=20=20=20=20= =20Generalise=20the=20code=20in=20Fstring_lessp=20for=20internal=20use?=20= =20*/=0A+=09=20=20if=20(lessp_only)=0A+=09=20=20=20=20return=200;=0A+=09=20= =20return=20NILP=20(Fequal=20(a,=20b));=0A+=09}=0A+=20=20=20=20=20=20= goto=20type_mismatch;=0A+=0A+=20=20=20=20case=20Lisp_Cons:=0A+=20=20=20=20= =20=20while=20(CONSP=20(b))=0A+=09{=0A+=09=20=20int=20cmp=20=3D=20= value_less_p=20(XCAR=20(a),=20XCAR=20(b),=20maxdepth=20-=201,=20false);=0A= +=09=20=20if=20(cmp=20!=3D=200)=0A+=09=20=20=20=20return=20cmp;=0A+=09=20= =20a=20=3D=20XCDR=20(a);=0A+=09=20=20b=20=3D=20XCDR=20(b);=0A+=09=20=20= if=20(!CONSP=20(a))=0A+=09=20=20=20=20break;=0A+=09}=0A+=20=20=20=20=20=20= if=20(CONSP=20(a))=0A+=09{=0A+=09=20=20if=20(NILP=20(b))=0A+=09=20=20=20=20= return=201;=0A+=09=20=20else=0A+=09=20=20=20=20goto=20type_mismatch;=0A+=09= }=0A+=20=20=20=20=20=20goto=20tail_recurse;=0A+=0A+=20=20=20=20case=20= Lisp_Vectorlike:=0A+=20=20=20=20=20=20if=20(VECTORLIKEP=20(b))=0A+=09{=0A= +=09=20=20enum=20pvec_type=20ta=20=3D=20PSEUDOVECTOR_TYPE=20(XVECTOR=20= (a));=0A+=09=20=20enum=20pvec_type=20tb=20=3D=20PSEUDOVECTOR_TYPE=20= (XVECTOR=20(b));=0A+=09=20=20if=20(ta=20=3D=3D=20tb)=0A+=09=20=20=20=20= switch=20(ta)=0A+=09=20=20=20=20=20=20{=0A+=09=20=20=20=20=20=20case=20= PVEC_NORMAL_VECTOR:=0A+=09=20=20=20=20=20=20case=20PVEC_RECORD:=0A+=09=09= {=0A+=09=09=20=20ptrdiff_t=20len_a=20=3D=20ASIZE=20(a);=0A+=09=09=20=20= ptrdiff_t=20len_b=20=3D=20ASIZE=20(b);=0A+=09=09=20=20if=20(ta=20=3D=3D=20= PVEC_RECORD)=0A+=09=09=20=20=20=20{=0A+=09=09=20=20=20=20=20=20len_a=20= &=3D=20PSEUDOVECTOR_SIZE_MASK;=0A+=09=09=20=20=20=20=20=20len_b=20&=3D=20= PSEUDOVECTOR_SIZE_MASK;=0A+=09=09=20=20=20=20}=0A+=09=09=20=20ptrdiff_t=20= len_min=20=3D=20min=20(len_a,=20len_b);=0A+=09=09=20=20for=20(ptrdiff_t=20= i=20=3D=200;=20i=20<=20len_min;=20i++)=0A+=09=09=20=20=20=20{=0A+=09=09=20= =20=20=20=20=20int=20cmp=20=3D=20value_less_p=20(AREF=20(a,=20i),=20AREF=20= (b,=20i),=0A+=09=09=09=09=09=20=20=20=20=20=20maxdepth=20-=201,=20= false);=0A+=09=09=20=20=20=20=20=20if=20(cmp=20!=3D=200)=0A+=09=09=09= return=20cmp;=0A+=09=09=20=20=20=20}=0A+=09=09=20=20return=20len_a=20<=20= len_b=20?=20-1=20:=20len_a=20>=20len_b;=0A+=09=09}=0A+=0A+=09=20=20=20=20= =20=20case=20PVEC_BOOL_VECTOR:=0A+=09=09{=0A+=09=09=20=20ptrdiff_t=20= len_a=20=3D=20bool_vector_size=20(a);=0A+=09=09=20=20ptrdiff_t=20len_b=20= =3D=20bool_vector_size=20(b);=0A+=09=09=20=20ptrdiff_t=20len_min=20=3D=20= min=20(len_a,=20len_b);=0A+=09=09=20=20/*=20FIXME:=20very=20inefficient,=20= we=20could=20compare=20words.=20=20*/=0A+=09=09=20=20for=20(ptrdiff_t=20= i=20=3D=200;=20i=20<=20len_min;=20i++)=0A+=09=09=20=20=20=20{=0A+=09=09=20= =20=20=20=20=20bool=20ai=20=3D=20bool_vector_bitref=20(a,=20i);=0A+=09=09= =20=20=20=20=20=20bool=20bi=20=3D=20bool_vector_bitref=20(b,=20i);=0A+=09= =09=20=20=20=20=20=20if=20(ai=20!=3D=20bi)=0A+=09=09=09return=20bi=20?=20= -1=20:=20ai;=0A+=09=09=20=20=20=20}=0A+=09=09=20=20return=20len_a=20<=20= len_b=20?=20-1=20:=20len_a=20>=20len_b;=0A+=09=09}=0A+=0A+=09=20=20=20=20= =20=20case=20PVEC_MARKER:=0A+=09=09{=0A+=09=09=20=20Lisp_Object=20buf_a=20= =3D=20Fmarker_buffer=20(a);=0A+=09=09=20=20Lisp_Object=20buf_b=20=3D=20= Fmarker_buffer=20(b);=0A+=09=09=20=20if=20(NILP=20(buf_a))=0A+=09=09=20=20= =20=20return=20NILP=20(buf_b)=20?=200=20:=20-1;=0A+=09=09=20=20if=20= (NILP=20(buf_b))=0A+=09=09=20=20=20=20return=201;=0A+=09=09=20=20int=20= cmp=20=3D=20value_less_p=20(buf_a,=20buf_b,=20maxdepth=20-=201,=20= false);=0A+=09=09=20=20if=20(cmp=20!=3D=200)=0A+=09=09=20=20=20=20return=20= cmp;=0A+=09=09=20=20ptrdiff_t=20pa=20=3D=20XMARKER=20(a)->charpos;=0A+=09= =09=20=20ptrdiff_t=20pb=20=3D=20XMARKER=20(b)->charpos;=0A+=09=09=20=20= return=20pa=20<=20pb=20?=20-1=20:=20pa=20>=20pb;=0A+=09=09}=0A+=0A+=09=20= =20=20=20=20=20case=20PVEC_PROCESS:=0A+=09=09return=20value_less_p=20= (Fprocess_name=20(a),=20Fprocess_name=20(b),=0A+=09=09=09=09=20=20=20=20=20= maxdepth=20-=201,=20lessp_only);=0A+=09=20=20=20=20=20=20case=20= PVEC_BUFFER:=0A+=09=09{=0A+=09=09=20=20/*=20Killed=20buffers=20lack=20= names=20and=20sort=20before=20those=20alive.=20=20*/=0A+=09=09=20=20= Lisp_Object=20na=20=3D=20Fbuffer_name=20(a);=0A+=09=09=20=20Lisp_Object=20= nb=20=3D=20Fbuffer_name=20(b);=0A+=09=09=20=20if=20(NILP=20(na))=0A+=09=09= =20=20=20=20return=20NILP=20(nb)=20?=200=20:=20-1;=0A+=09=09=20=20if=20= (NILP=20(nb))=0A+=09=09=20=20=20=20return=201;=0A+=09=09=20=20return=20= value_less_p=20(na,=20nb,=20maxdepth=20-=201,=20lessp_only);=0A+=09=09}=0A= +=0A+=09=20=20=20=20=20=20case=20PVEC_BIGNUM:=0A+=09=09return=20mpz_cmp=20= (*xbignum_val=20(a),=20*xbignum_val=20(b));=0A+=0A+=09=20=20=20=20=20=20= default:=0A+=09=09/*=20Treat=20other=20types=20as=20unordered.=20=20*/=0A= +=09=09return=200;=0A+=09=20=20=20=20=20=20}=0A+=09}=0A+=20=20=20=20=20=20= else=20if=20(BIGNUMP=20(a))=0A+=09return=20-value_less_p=20(b,=20a,=20= maxdepth,=20false);=0A+=20=20=20=20=20=20goto=20type_mismatch;=0A+=0A+=20= =20=20=20case=20Lisp_Float:=0A+=20=20=20=20=20=20{=0A+=09double=20fa=20=3D= =20XFLOAT_DATA=20(a);=0A+=09if=20(FLOATP=20(b))=0A+=09=20=20return=20fa=20= <=20XFLOAT_DATA=20(b)=20?=20-1=20:=20fa=20>=20XFLOAT_DATA=20(b);=0A+=09= if=20(FIXNUMP=20(b))=0A+=09=20=20return=20fa=20<=20XFIXNUM=20(b)=20?=20= -1=20:=20fa=20>=20XFIXNUM=20(b);=0A+=09if=20(BIGNUMP=20(b))=0A+=09=20=20= {=0A+=09=20=20=20=20if=20(isnan=20(fa))=0A+=09=20=20=20=20=20=20return=20= 0;=0A+=09=20=20=20=20return=20-mpz_cmp_d=20(*xbignum_val=20(b),=20fa);=0A= +=09=20=20}=0A+=20=20=20=20=20=20}=0A+=20=20=20=20=20=20goto=20= type_mismatch;=0A+=0A+=20=20=20=20default:=0A+=20=20=20=20=20=20eassume=20= (0);=0A+=20=20=20=20}=0A+=20type_mismatch:=0A+=20=20xsignal2=20= (Qtype_mismatch,=20a,=20b);=0A+}=0A+=0A+DEFUN=20("value-less-p",=20= Fvalue_less_p,=20Svalue_less_p,=202,=202,=200,=0A+=20=20=20=20=20=20=20= doc:=20/*=20Return=20non-nil=20if=20A=20precedes=20B=20in=20standard=20= value=20order.=0A+A=20and=20B=20must=20have=20the=20same=20basic=20type.=0A= +Numbers=20are=20compared=20with=20`<'.=0A+Strings=20and=20symbols=20are=20= compared=20with=20`string-lessp'.=0A+Lists,=20vectors,=20bool-vectors=20= and=20records=20are=20compared=20lexicographically.=0A+Markers=20are=20= compared=20lexicographically=20by=20buffer=20and=20position.=0A+Buffers=20= and=20processes=20are=20compared=20by=20name.=0A+Other=20types=20are=20= considered=20unordered=20and=20the=20return=20value=20will=20be=20`nil'.=20= =20*/)=0A+=20=20(Lisp_Object=20a,=20Lisp_Object=20b)=0A+{=0A+=20=20int=20= maxdepth=20=3D=2020;=09=09=20=20/*=20FIXME:=20arbitrary=20value=20*/=0A+=20= =20return=20value_less_p=20(a,=20b,=20maxdepth,=20true)=20<=200=20?=20Qt=20= :=20Qnil;=0A+}=0A+=0A=20=0C=0A=20=0A=20DEFUN=20("fillarray",=20= Ffillarray,=20Sfillarray,=202,=202,=200,=0A@@=20-6589,6=20+6814,7=20@@=20= syms_of_fns=20(void)=0A=20=20=20defsubr=20(&Seql);=0A=20=20=20defsubr=20= (&Sequal);=0A=20=20=20defsubr=20(&Sequal_including_properties);=0A+=20=20= defsubr=20(&Svalue_less_p);=0A=20=20=20defsubr=20(&Sfillarray);=0A=20=20=20= defsubr=20(&Sclear_string);=0A=20=20=20defsubr=20(&Snconc);=0Adiff=20= --git=20a/test/src/fns-tests.el=20b/test/src/fns-tests.el=0Aindex=20= 7437c07f156..f81b1eadd09=20100644=0A---=20a/test/src/fns-tests.el=0A+++=20= b/test/src/fns-tests.el=0A@@=20-1513,4=20+1513,126=20@@=20= fns--copy-alist=0A=20=20=20(should-error=20(copy-alist=20"abc")=0A=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20=20:type=20'wrong-type-argument))=0A= =20=0A+(ert-deftest=20fns-value-less-p-ordered=20()=0A+=20=20;;=20values=20= (X=20.=20Y)=20where=20X