bug#57957: 29.0.50; Native compilation hangs on cyclic lists

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Lars Tveito]

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))

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Lars Ingebrigtsen]

Lars Tveito <larstvei@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
...

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Andrea Corallo]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Lars Tveito <larstvei@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

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Lars Ingebrigtsen]

Andrea Corallo <akrl@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.

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Gerd Möllmann]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Andrea Corallo <akrl@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.

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Lars Ingebrigtsen [2022-09-22 13:15:39] wrote:
> Andrea Corallo <akrl@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

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Andrea Corallo]

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

> Lars Ingebrigtsen <larsi@gnus.org> writes:
>
>> Andrea Corallo <akrl@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

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Gerd Möllmann]

Andrea Corallo <akrl@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.

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> 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

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Andrea Corallo]

Stefan Monnier <monnier@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

bug#57957: 29.0.50; Native compilation hangs on cyclic lists

[Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#57957: bug#69872: 29.2; Async native compilation of seq.el test uses up resources and hangs

[Andrea Corallo]

Andrea Corallo <akrl@sdf.org> writes:

> Stefan Monnier <monnier@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

bug#57957: bug#69872: 29.2; Async native compilation of seq.el test uses up resources and hangs

[Andrea Corallo]

Andrea Corallo <acorallo@gnu.org> writes:

> Andrea Corallo <akrl@sdf.org> writes:
>
>> Stefan Monnier <monnier@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