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#54501: Segfault on recursive structure Date: Sat, 26 Mar 2022 16:58:53 +0100 Message-ID: <839D376A-2234-4A2A-AB7E-DCCB3D6CB149@acm.org> References: Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Content-Type: multipart/mixed; boundary="Apple-Mail=_FCB9FD20-DF36-4949-BCD3-A42179DC5FC1" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="27396"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Lars Ingebrigtsen , Andreas Schwab , 54501@debbugs.gnu.org, Stefan Monnier To: Andy Gaynor Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Mar 26 17:00:31 2022 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 1nY8q7-0006u1-6T for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 26 Mar 2022 17:00:31 +0100 Original-Received: from localhost ([::1]:37052 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nY8q4-0001zG-Ol for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 26 Mar 2022 12:00:29 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:53868) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nY8pf-0001uH-Se for bug-gnu-emacs@gnu.org; Sat, 26 Mar 2022 12:00:04 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:60653) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nY8pf-0002C4-EP for bug-gnu-emacs@gnu.org; Sat, 26 Mar 2022 12:00:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1nY8pf-00018O-7R for bug-gnu-emacs@gnu.org; Sat, 26 Mar 2022 12:00:03 -0400 X-Loop: help-debbugs@gnu.org In-Reply-To: Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 26 Mar 2022 16:00:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54501 X-GNU-PR-Package: emacs Original-Received: via spool by 54501-submit@debbugs.gnu.org id=B54501.16483103474256 (code B ref 54501); Sat, 26 Mar 2022 16:00:03 +0000 Original-Received: (at 54501) by debbugs.gnu.org; 26 Mar 2022 15:59:07 +0000 Original-Received: from localhost ([127.0.0.1]:54550 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nY8ol-00016a-6A for submit@debbugs.gnu.org; Sat, 26 Mar 2022 11:59:07 -0400 Original-Received: from mail1468c50.megamailservers.eu ([91.136.14.68]:41834 helo=mail268c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nY8oi-000164-Qz for 54501@debbugs.gnu.org; Sat, 26 Mar 2022 11:59:06 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1648310337; bh=14CPEBjIGTB1J946+gu/D+jmtfYLixt+bCsybwk9qO0=; h=From:Subject:Date:Cc:To:From; b=WqgPJZYzVdazCmPvTKMxqlwcGP30f6TlQUS1rfdM/MXNBA5lAD549Ar22ADSgn4oi CSXlNEvyoqK+ADBEa9ig5dPXmx1zIYy2m2DFn5us7B5RIyh3d8b7XrOCeATBcQCjZ6 hRvYo48Du/o/DbPNv4P3rcPyFNkRLPqiYiWAW1rM= Feedback-ID: mattiase@acm.or Original-Received: from smtpclient.apple (c-b952e353.032-75-73746f71.bbcust.telenor.se [83.227.82.185]) (authenticated bits=0) by mail268c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 22QFwr5u017551; Sat, 26 Mar 2022 15:58:55 +0000 X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F1E.623F3841.0003, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE 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" Xref: news.gmane.io gmane.emacs.bugs:228975 Archived-At: --Apple-Mail=_FCB9FD20-DF36-4949-BCD3-A42179DC5FC1 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii > #0=3D[#1=3D(#0# . #1#)] When the reader encounters an expression in the form #N=3DX, the = following steps take place: 1. Create a placeholder value P which is a fresh (nil . nil) cons pair. 2. Assign the number N to P in the read_objects_map. 3. Read X as the value V, where P is used for any occurrences of #N#. 4. Add V to the read_objects_completed set. This is used for future = substitutions. 5. Traverse V to replace any occurrence of P with V itself, and return V = so modified. So far all good, but there is an optimisation: if X is a cons, then step = 5 is skipped. Instead, since P is already a cons, its CAR and CDR slots = are modified to those of V, and P is returned. That way no potentially = expensive traversal of V is required. The alert (human) reader has now spotted the error in the (lisp) reader: = step 4 added the now defunct value V to read_objects_completed, not the = actually returned value P. The traversal of the outer value, the vector = #0 in the above example, will then enter infinite recursion because = value #1 was never added to read_objects_completed. The simplest solution is to remove the optimisation but I'd say it's = algorithmically valuable and propose the attached patch. The patch fixes the #0=3D#0# nonsense as well since it's a trivial = check. Admittedly it doesn't handle #1=3D#2=3D#1# -- please keep this = bug open if you think it's important. --Apple-Mail=_FCB9FD20-DF36-4949-BCD3-A42179DC5FC1 Content-Disposition: attachment; filename=0001-Fix-reader-infinite-recursion-for-circular-mixed-typ.patch Content-Type: application/octet-stream; x-unix-mode=0644; name="0001-Fix-reader-infinite-recursion-for-circular-mixed-typ.patch" Content-Transfer-Encoding: quoted-printable =46rom=206819b064585470f2bdcb7baf88beba6b2937d811=20Mon=20Sep=2017=20= 00:00:00=202001=0AFrom:=20=3D?UTF-8?q?Mattias=3D20Engdeg=3DC3=3DA5rd?=3D=20= =0ADate:=20Sat,=2026=20Mar=202022=2016:44:18=20+0100=0A= Subject:=20[PATCH]=20Fix=20reader=20infinite=20recursion=20for=20= circular=20mixed-type=20values=0A=0AMake=20sure=20that=20the=20value=20= added=20to=20the=20`read_objects_completed`=20set=20is=0Athe=20one=20we=20= actually=20return;=20previously=20this=20wasn't=20the=20case=20for=20= conses=0Abecause=20of=20an=20optimisation=20(bug#54501).=0A=0AAlso=20add=20= a=20check=20for=20vacuous=20self-references=20such=20as=20#1=3D#1#=20= instead=20of=0Areturning=20a=20nonsense=20value=20from=20thin=20air.=0A=0A= *=20src/lread.c=20(read1):=20Treat=20numbered=20conses=20correctly=20as=20= described=0Aabove.=20=20Detect=20vacuous=20self-references.=0A*=20= test/src/lread-tests.el=20(lread-test-read-and-print)=0A= (lread-test-circle-cases,=20lread-circle):=20Add=20tests.=0A---=0A=20= src/lread.c=20=20=20=20=20=20=20=20=20=20=20=20=20|=2046=20= +++++++++++++++++++++++++++--------------=0A=20test/src/lread-tests.el=20= |=2022=20++++++++++++++++++++=0A=202=20files=20changed,=2052=20= insertions(+),=2016=20deletions(-)=0A=0Adiff=20--git=20a/src/lread.c=20= b/src/lread.c=0Aindex=20d7b56c5087..17d993abd1=20100644=0A---=20= a/src/lread.c=0A+++=20b/src/lread.c=0A@@=20-3480,6=20+3480,29=20@@=20= read1=20(Lisp_Object=20readcharfun,=20int=20*pch,=20bool=20= first_in_list,=20bool=20locate_syms)=0A=20=09=09=20=20=20=20=20=20/*=20= Read=20the=20object=20itself.=20=20*/=0A=20=09=09=20=20=20=20=20=20= Lisp_Object=20tem=20=3D=20read0=20(readcharfun,=20locate_syms);=0A=20=0A= +=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20if=20= (CONSP=20(tem))=0A+=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20{=0A+=09=09=09=20=20if=20(BASE_EQ=20(tem,=20= placeholder))=0A+=09=09=09=20=20=20=20/*=20Catch=20silly=20games=20like=20= #1=3D#1#=20*/=0A+=09=09=09=20=20=20=20invalid_syntax=20("nonsensical=20= self-reference",=0A+=09=09=09=09=09=20=20=20=20readcharfun);=0A+=0A+=09=09= =09=20=20/*=20Optimisation:=20since=20the=20placeholder=20is=20already=0A= +=09=09=09=20=20=20=20=20a=20cons,=20repurpose=20it=20as=20the=20actual=20= value.=0A+=09=09=09=20=20=20=20=20This=20allows=20us=20to=20skip=20the=20= substition=20below,=0A+=09=09=09=20=20=20=20=20since=20the=20placeholder=20= is=20already=20referenced=0A+=09=09=09=20=20=20=20=20inside=20TEM=20at=20= the=20appropriate=20places.=20=20*/=0A+=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20=20Fsetcar=20(placeholder,=20XCAR=20= (tem));=0A+=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20Fsetcdr=20(placeholder,=20XCDR=20(tem));=0A+=0A+=09=09=09=20= =20struct=20Lisp_Hash_Table=20*h2=0A+=09=09=09=20=20=20=20=3D=20= XHASH_TABLE=20(read_objects_completed);=0A+=09=09=09=20=20ptrdiff_t=20i=20= =3D=20hash_lookup=20(h2,=20placeholder,=20&hash);=0A+=09=09=09=20=20= eassert=20(i=20<=200);=0A+=09=09=09=20=20hash_put=20(h2,=20placeholder,=20= Qnil,=20hash);=0A+=09=09=09=20=20return=20placeholder;=0A+=09=09=09}=0A+=0A= =20=09=09=20=20=20=20=20=20/*=20If=20it=20can=20be=20recursive,=20= remember=20it=20for=0A=20=09=09=09=20future=20substitutions.=20=20*/=0A=20= =09=09=20=20=20=20=20=20if=20(!=20SYMBOLP=20(tem)=0A@@=20-3494,24=20= +3517,15=20@@=20read1=20(Lisp_Object=20readcharfun,=20int=20*pch,=20bool=20= first_in_list,=20bool=20locate_syms)=0A=20=09=09=09}=0A=20=0A=20=09=09=20= =20=20=20=20=20/*=20Now=20put=20it=20everywhere=20the=20placeholder=20= was...=20=20*/=0A-=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20if=20(CONSP=20(tem))=0A-=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20=20{=0A-=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20Fsetcar=20(placeholder,=20XCAR=20= (tem));=0A-=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20Fsetcdr=20(placeholder,=20XCDR=20(tem));=0A-=20=20=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20return=20= placeholder;=0A-=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20}=0A-=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20else=0A-=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20{=0A-=09=09=20=20=20=20=20=20=20=20=20=20= Flread__substitute_object_in_subtree=0A-=09=09=09=20=20=20=20(tem,=20= placeholder,=20read_objects_completed);=0A+=09=09=20=20=20=20=20=20= Flread__substitute_object_in_subtree=0A+=09=09=09(tem,=20placeholder,=20= read_objects_completed);=0A=20=0A-=09=09=20=20=20=20=20=20=20=20=20=20/*=20= ...and=20#n#=20will=20use=20the=20real=20value=20from=20now=20on.=20=20= */=0A-=09=09=09=20=20i=20=3D=20hash_lookup=20(h,=20number,=20&hash);=0A-=09= =09=09=20=20eassert=20(i=20>=3D=200);=0A-=09=09=09=20=20= set_hash_value_slot=20(h,=20i,=20tem);=0A+=09=09=20=20=20=20=20=20/*=20= ...and=20#n#=20will=20use=20the=20real=20value=20from=20now=20on.=20=20= */=0A+=09=09=20=20=20=20=20=20i=20=3D=20hash_lookup=20(h,=20number,=20= &hash);=0A+=09=09=20=20=20=20=20=20eassert=20(i=20>=3D=200);=0A+=09=09=20= =20=20=20=20=20set_hash_value_slot=20(h,=20i,=20tem);=0A=20=0A-=09=09=20=20= =20=20=20=20=20=20=20=20return=20tem;=0A-=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20}=0A+=09=09=20=20=20=20=20=20= return=20tem;=0A=20=09=09=20=20=20=20}=0A=20=0A=20=09=09=20=20/*=20#n#=20= returns=20a=20previously=20read=20object.=20=20*/=0Adiff=20--git=20= a/test/src/lread-tests.el=20b/test/src/lread-tests.el=0Aindex=20= 862f6a6595..9ec54c719c=20100644=0A---=20a/test/src/lread-tests.el=0A+++=20= b/test/src/lread-tests.el=0A@@=20-258,5=20+258,27=20@@=20lread-float=0A=20= =20=20(should=20(equal=20(read=20"-0.e-5")=20-0.0))=0A=20=20=20)=0A=20=0A= +(defun=20lread-test-read-and-print=20(str)=0A+=20=20(let*=20= ((read-circle=20t)=0A+=20=20=20=20=20=20=20=20=20(print-circle=20t)=0A+=20= =20=20=20=20=20=20=20=20(val=20(read-from-string=20str)))=0A+=20=20=20=20= (if=20(consp=20val)=0A+=20=20=20=20=20=20=20=20(prin1-to-string=20(car=20= val))=0A+=20=20=20=20=20=20(error=20"reading=20%S=20failed:=20%S"=20str=20= val))))=0A+=0A+(defconst=20lread-test-circle-cases=0A+=20=20'("#1=3D(#1#=20= .=20#1#)"=0A+=20=20=20=20"#1=3D[#1#=20a=20#1#]"=0A+=20=20=20=20= "#1=3D(#2=3D[#1#=20#2#]=20.=20#1#)"=0A+=20=20=20=20"#1=3D(#2=3D[#1#=20= #2#]=20.=20#2#)"=0A+=20=20=20=20"#1=3D[#2=3D(#1#=20.=20#2#)]"=0A+=20=20=20= =20"#1=3D(#2=3D[#3=3D(#1#=20.=20#2#)=20#4=3D(#3#=20.=20#4#)])"=0A+=20=20=20= =20))=0A+=0A+(ert-deftest=20lread-circle=20()=0A+=20=20(dolist=20(str=20= lread-test-circle-cases)=0A+=20=20=20=20(ert-info=20(str=20:prefix=20= "input:=20")=0A+=20=20=20=20=20=20(should=20(equal=20= (lread-test-read-and-print=20str)=20str))))=0A+=20=20(should-error=20= (read-from-string=20"#1=3D#1#")=20:type=20'invalid-read-syntax))=0A=20=0A= =20;;;=20lread-tests.el=20ends=20here=0A--=20=0A2.32.0=20(Apple=20= Git-132)=0A=0A= --Apple-Mail=_FCB9FD20-DF36-4949-BCD3-A42179DC5FC1--