GNU bug report logs - #57957
29.0.50; Native compilation hangs on cyclic lists

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 57957 in the body.
You can then email your comments to 57957 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Lars Tveito <larstvei <at> ifi.uio.no>
To: "bug-gnu-emacs <at> gnu.org" <bug-gnu-emacs <at> gnu.org>
Subject: 29.0.50; Native compilation hangs on cyclic lists
Date: Tue, 20 Sep 2022 07:55:48 +0000

Evaluating the two following forms results in Emacs hanging:

(defun test-cycle ()
  '#1=(a . #1#))

(native-compile 'test-cycle)

The bug has been reproduced on a system running Debian as well.

- Lars
        

In GNU Emacs 29.0.50 (build 1, aarch64-apple-darwin21.6.0, NS
appkit-2113.60 Version 12.6 (Build 21G115))
Windowing system distributor 'Apple', version 10.3.2113
System Description:  macOS 12.6

Configured using:
'configure
--prefix=/nix/store/wf6wjsvvs3q7k0vf3xlfzi3ik8v3601n-emacs-29.0.50
--disable-build-details --with-modules --with-ns
--disable-ns-self-contained --with-native-compilation'

Configured features:
ACL GLIB GMP GNUTLS JPEG JSON LIBXML2 MODULES NATIVE_COMP NOTIFY KQUEUE
NS PDUMPER PNG RSVG SQLITE3 THREADS TIFF TOOLKIT_SCROLL_BARS ZLIB

Important settings:
  value of $EMACSLOADPATH: /nix/store/87hrwgmnic6hhjl6p7ch30ik90dpw324-emacs-packages-deps/share/emacs/site-lisp:
  value of $EMACSNATIVELOADPATH: /nix/store/87hrwgmnic6hhjl6p7ch30ik90dpw324-emacs-packages-deps/share/emacs/native-lisp::
  value of $LC_CTYPE: UTF-8
  locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  eldoc-mode: t
  show-paren-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  line-number-mode: t
  indent-tabs-mode: t
  transient-mark-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t

Load-path shadows:
/nix/store/87hrwgmnic6hhjl6p7ch30ik90dpw324-emacs-packages-deps/share/emacs/site-lisp/elpa/let-alist-1.0.6/let-alist hides /nix/store/wf6wjsvvs3q7k0vf3xlfzi3ik8v3601n-emacs-29.0.50/share/emacs/29.0.50/lisp/emacs-lisp/let-alist
/nix/store/87hrwgmnic6hhjl6p7ch30ik90dpw324-emacs-packages-deps/share/emacs/site-lisp/elpa/nadvice-0.3/nadvice hides /nix/store/wf6wjsvvs3q7k0vf3xlfzi3ik8v3601n-emacs-29.0.50/share/emacs/29.0.50/lisp/emacs-lisp/nadvice

Features:
(shadow sort mail-extr emacsbug message mailcap yank-media puny dired
dired-loaddefs rfc822 mml mml-sec password-cache epa derived epg rfc6068
epg-config gnus-util text-property-search time-date mm-decode mm-bodies
mm-encode mail-parse rfc2231 mailabbrev gmm-utils mailheader cl-loaddefs
comp comp-cstr warnings icons subr-x rx cl-seq cl-macs gv cl-extra
help-mode bytecomp byte-compile cconv cl-lib sendmail rfc2047 rfc2045
ietf-drums mm-util mail-prsvr mail-utils rmc iso-transl tooltip eldoc
paren electric uniquify ediff-hook vc-hooks lisp-float-type elisp-mode
mwheel term/ns-win ns-win ucs-normalize mule-util term/common-win
tool-bar dnd fontset image regexp-opt fringe tabulated-list replace
newcomment text-mode lisp-mode prog-mode register page tab-bar menu-bar
rfn-eshadow isearch easymenu timer select scroll-bar mouse jit-lock
font-lock syntax font-core term/tty-colors frame minibuffer nadvice seq
simple cl-generic indonesian philippine cham georgian utf-8-lang
misc-lang vietnamese tibetan thai tai-viet lao korean japanese eucjp-ms
cp51932 hebrew greek romanian slovak czech european ethiopic indian
cyrillic chinese composite emoji-zwj charscript charprop case-table
epa-hook jka-cmpr-hook help abbrev obarray oclosure cl-preloaded button
loaddefs faces cus-face macroexp files window text-properties overlay
sha1 md5 base64 format env code-pages mule custom widget keymap
hashtable-print-readable backquote threads kqueue cocoa ns multi-tty
make-network-process native-compile emacs)

Memory information:
((conses 16 78425 6959)
(symbols 48 7029 0)
(strings 32 19124 2018)
(string-bytes 1 599871)
(vectors 16 16700)
(vector-slots 8 325741 9902)
(floats 8 27 31)
(intervals 56 320 0)
(buffers 1000 12))

Message #8 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Lars Tveito <larstvei <at> ifi.uio.no>
Cc: 57957 <at> debbugs.gnu.org, Andrea Corallo <akrl <at> sdf.org>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Tue, 20 Sep 2022 17:33:55 +0200

Lars Tveito <larstvei <at> ifi.uio.no> writes:

> Evaluating the two following forms results in Emacs hanging:
>
> (defun test-cycle ()
>   '#1=(a . #1#))
>
> (native-compile 'test-cycle)

It seems to be inflooping in comp-ssa-rename.  A debug-on-quit backtrace
included below.

I've added Andrea to the CCs; perhaps he has some comments.

Debugger entered--Lisp error: (quit)
  #f(compiled-function (x) #<bytecode -0xadd90b5d8edcf84>)((a . #1))
  cl--nsublis-rec((a . #1))
  cl--nsublis-rec(((a . #2)))
  cl--nsublis-rec((((a . #3))))
  cl-nsublis(((nil . #s(comp-mvar :typeset (t) :valset nil :range nil :
  cl-nsubst-if(#s(comp-mvar :typeset (t) :valset nil :range nil :neg ni
  comp-ssa-rename-insn((setimm #s(comp-mvar :typeset (t) :valset nil :r
  #f(compiled-function (bb in-frame) #<bytecode -0xdf66bba587123ea>)(#s
  #f(compiled-function (bb in-frame) #<bytecode -0xdf66bba587123ea>)(#s
  comp-ssa-rename()
  #<subr F616e6f6e796d6f75732d6c616d626461_anonymous_lambda_112>("F7465
  comp-ssa()
  comp-fwprop(nil)
  funcall(comp-fwprop nil)
  (setq data (funcall pass data))
  (if (memq pass comp-disabled-passes) (progn) (comp-log (format "(%s) 
  (while (progn (setq t0 (current-time)) (consp --cl-var--)) (setq pass
  (let* ((report nil) (t0 nil) (--cl-var-- comp-passes) (pass nil) (--c
...

Message #13 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <akrl <at> sdf.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 57957 <at> debbugs.gnu.org, Lars Tveito <larstvei <at> ifi.uio.no>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Wed, 21 Sep 2022 19:18:55 +0000

Lars Ingebrigtsen <larsi <at> gnus.org> writes:

> Lars Tveito <larstvei <at> ifi.uio.no> writes:
>
>> Evaluating the two following forms results in Emacs hanging:
>>
>> (defun test-cycle ()
>>   '#1=(a . #1#))
>>
>> (native-compile 'test-cycle)
>
> It seems to be inflooping in comp-ssa-rename.  A debug-on-quit backtrace
> included below.
>
> I've added Andrea to the CCs; perhaps he has some comments.

I see nor cl-nsubst-if nor cl-subst-if are robust against cyclic lists.
Is this a bug in cl-lib or is it expected?  In case I'll add an ad-hoc
substitute for this use (if there's no other alternative).

  Andrea

Message #16 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Andrea Corallo <akrl <at> sdf.org>
Cc: 57957 <at> debbugs.gnu.org, Lars Tveito <larstvei <at> ifi.uio.no>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Thu, 22 Sep 2022 13:15:39 +0200

Andrea Corallo <akrl <at> sdf.org> writes:

> I see nor cl-nsubst-if nor cl-subst-if are robust against cyclic lists.
> Is this a bug in cl-lib or is it expected?  In case I'll add an ad-hoc
> substitute for this use (if there's no other alternative).

I'm not sure -- Stefan probably knows; added to the CCs.

Message #19 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 57957 <at> debbugs.gnu.org, Lars Tveito <larstvei <at> ifi.uio.no>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, Andrea Corallo <akrl <at> sdf.org>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Thu, 22 Sep 2022 14:06:27 +0200

Lars Ingebrigtsen <larsi <at> gnus.org> writes:

> Andrea Corallo <akrl <at> sdf.org> writes:
>
>> I see nor cl-nsubst-if nor cl-subst-if are robust against cyclic lists.
>> Is this a bug in cl-lib or is it expected?  In case I'll add an ad-hoc
>> substitute for this use (if there's no other alternative).
>
> I'm not sure -- Stefan probably knows; added to the CCs.

From Common Lisp I can say that these functions expect a "tree",
i.e. not a circular list.

Message #22 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 57957 <at> debbugs.gnu.org, Lars Tveito <larstvei <at> ifi.uio.no>,
 Andrea Corallo <akrl <at> sdf.org>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Thu, 22 Sep 2022 10:25:26 -0400

Lars Ingebrigtsen [2022-09-22 13:15:39] wrote:
> Andrea Corallo <akrl <at> sdf.org> writes:
>> I see nor cl-nsubst-if nor cl-subst-if are robust against cyclic lists.
>> Is this a bug in cl-lib or is it expected?  In case I'll add an ad-hoc
>> substitute for this use (if there's no other alternative).
> I'm not sure -- Stefan probably knows; added to the CCs.

Sorry, but these functions come straight for the `cl.el` lib that was
there before I started using Emacs.


        Stefan

Message #25 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <akrl <at> sdf.org>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, Lars Tveito <larstvei <at> ifi.uio.no>,
 57957 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Thu, 22 Sep 2022 16:07:37 +0000

Gerd Möllmann <gerd.moellmann <at> gmail.com> writes:

> Lars Ingebrigtsen <larsi <at> gnus.org> writes:
>
>> Andrea Corallo <akrl <at> sdf.org> writes:
>>
>>> I see nor cl-nsubst-if nor cl-subst-if are robust against cyclic lists.
>>> Is this a bug in cl-lib or is it expected?  In case I'll add an ad-hoc
>>> substitute for this use (if there's no other alternative).
>>
>> I'm not sure -- Stefan probably knows; added to the CCs.
>
>>From Common Lisp I can say that these functions expect a "tree",
> i.e. not a circular list.

Okay I tried an adhoc substitute but this is not the only place in the
compiler not robust against cyclic lists, so more work will be needed.

  Andrea

Message #28 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Andrea Corallo <akrl <at> sdf.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, Lars Tveito <larstvei <at> ifi.uio.no>,
 57957 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Thu, 22 Sep 2022 18:41:04 +0200

Andrea Corallo <akrl <at> sdf.org> writes:

>>>>From Common Lisp I can say that these functions expect a "tree",
>> i.e. not a circular list.
>
> Okay I tried an adhoc substitute but this is not the only place in the
> compiler not robust against cyclic lists, so more work will be needed.

The question is of course also how much effort circular lists deserve in
the compiler.  From my point of view, not too much because they aren't
very useful, in code at least.  And dealing with them costs runtime.

Maybe some places could use cl-list-length?  That function deals with
circular lists and returns nil then.  We could then refuse to compile.

Message #31 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, Lars Tveito <larstvei <at> ifi.uio.no>,
 57957 <at> debbugs.gnu.org, Andrea Corallo <akrl <at> sdf.org>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Thu, 22 Sep 2022 13:10:09 -0400

> The question is of course also how much effort circular lists deserve in
> the compiler.  From my point of view, not too much because they aren't
> very useful, in code at least.  And dealing with them costs runtime.

Circular data structures are perfectly normal in source code under
a `quote` but the code itself should never be cyclic (so I think it
would be OK to signal an error (and/or to inf-loop) when asked to
compile a chunk of code that has a cycle).  So we *should* handle
circular data structures correctly.

Note: I don't know why we'd need/want to do a `subst-if` inside
a `quote` and haven't looked at this bug or at the `comp.el` code to
know what we're really talking about.


        Stefan

Message #34 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <akrl <at> sdf.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Gerd Möllmann <gerd.moellmann <at> gmail.com>,
 Lars Ingebrigtsen <larsi <at> gnus.org>, Lars Tveito <larstvei <at> ifi.uio.no>,
 57957 <at> debbugs.gnu.org
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Thu, 22 Sep 2022 22:39:22 +0000

Stefan Monnier <monnier <at> iro.umontreal.ca> writes:

>> The question is of course also how much effort circular lists deserve in
>> the compiler.  From my point of view, not too much because they aren't
>> very useful, in code at least.  And dealing with them costs runtime.
>
> Circular data structures are perfectly normal in source code under
> a `quote` but the code itself should never be cyclic (so I think it
> would be OK to signal an error (and/or to inf-loop) when asked to
> compile a chunk of code that has a cycle).  So we *should* handle
> circular data structures correctly.

I agree, Saturday I should have some time to look into this.

  Andrea

Message #37 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: "Basil L. Contovounesios" <contovob <at> tcd.ie>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, Lars Tveito <larstvei <at> ifi.uio.no>,
 57957 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 Andrea Corallo <akrl <at> sdf.org>
Subject: Re: bug#57957: 29.0.50; Native compilation hangs on cyclic lists
Date: Sun, 25 Sep 2022 13:02:27 +0300

Gerd Möllmann [2022-09-22 18:41 +0200] wrote:

> Maybe some places could use cl-list-length?  That function deals with
> circular lists and returns nil then.  We could then refuse to compile.

Since Emacs 27 we also have proper-list-p for this.

-- 
Basil

Message #44 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <acorallo <at> gnu.org>
To: Andrea Corallo <akrl <at> sdf.org>
Cc: Lars Tveito <larstvei <at> ifi.uio.no>, hokomo <hokomo <at> disroot.org>,
 Gerd Möllmann <gerd.moellmann <at> gmail.com>,
 57957 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 69872 <at> debbugs.gnu.org, Lars Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#69872: 29.2; Async native compilation of seq.el test uses
 up resources and hangs
Date: Sun, 24 Mar 2024 07:26:52 -0400

Andrea Corallo <akrl <at> sdf.org> writes:

> Stefan Monnier <monnier <at> iro.umontreal.ca> writes:
>
>>> The question is of course also how much effort circular lists deserve in
>>> the compiler.  From my point of view, not too much because they aren't
>>> very useful, in code at least.  And dealing with them costs runtime.
>>
>> Circular data structures are perfectly normal in source code under
>> a `quote` but the code itself should never be cyclic (so I think it
>> would be OK to signal an error (and/or to inf-loop) when asked to
>> compile a chunk of code that has a cycle).  So we *should* handle
>> circular data structures correctly.
>
> I agree, Saturday I should have some time to look into this.

A little time after... I finally managed to get to it, sorry for the
delay.

I've pushed into master c5de73a95a6, it fixes my reprodurer here and
adds a test for this.

If anyone could confirm this is fixed i'll be (extremely) happy to close
this :)

Thanks

  Andrea

Message #47 received at 57957 <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <acorallo <at> gnu.org>
To: Andrea Corallo <akrl <at> sdf.org>
Cc: Lars Tveito <larstvei <at> ifi.uio.no>, hokomo <hokomo <at> disroot.org>,
 69872-done <at> debbugs.gnu.org,
 Gerd Möllmann <gerd.moellmann <at> gmail.com>,
 57957 <at> debbugs.gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 Lars Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#57957: bug#69872: 29.2; Async native compilation of seq.el
 test uses up resources and hangs
Date: Mon, 01 Apr 2024 16:46:47 -0400

Andrea Corallo <acorallo <at> gnu.org> writes:

> Andrea Corallo <akrl <at> sdf.org> writes:
>
>> Stefan Monnier <monnier <at> iro.umontreal.ca> writes:
>>
>>>> The question is of course also how much effort circular lists deserve in
>>>> the compiler.  From my point of view, not too much because they aren't
>>>> very useful, in code at least.  And dealing with them costs runtime.
>>>
>>> Circular data structures are perfectly normal in source code under
>>> a `quote` but the code itself should never be cyclic (so I think it
>>> would be OK to signal an error (and/or to inf-loop) when asked to
>>> compile a chunk of code that has a cycle).  So we *should* handle
>>> circular data structures correctly.
>>
>> I agree, Saturday I should have some time to look into this.
>
> A little time after... I finally managed to get to it, sorry for the
> delay.
>
> I've pushed into master c5de73a95a6, it fixes my reprodurer here and
> adds a test for this.
>
> If anyone could confirm this is fixed i'll be (extremely) happy to close
> this :)
>
> Thanks
>
>   Andrea

Right I'm closing this as I believe it's fixed, happy to re-open if it's
not the case.

Thanks!

  Andrea

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.