bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

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

Hello,

The Emacs Lisp native compiler goes into an infinite loop when 
compiling code that contains circular objects.

For example, put the following into a file and use M-x 
emacs-lisp-native-compile; it should hang:

  (defun test1 ()
    '#1=(1 2 3 . #1#))

It seems like this only happens for certain top-level forms, such 
as `defun' (which may be expected behavior, due to the way the 
file compiler processes top-level forms). For example, this 
doesn't hang:

  (lambda ()
    '#1=(1 2 3 . #1#))

Here's a more interesting example, which is how I stumbled upon 
this issue in the first place:

  (defun cycle-pure (list)
    (declare (pure t) (side-effect-free t))
    (let ((newlist (append list ())))
      (nconc newlist newlist)))

  (defun test2 ()
    (cycle-pure '(1 2 3)))

(The definition of `cycle-pure' is copied from the `-cycle' 
function from the dash.el package.)

If `cycle-pure' is not yet defined when compiling, the compiler 
doesn't hang.

However, if `cycle-pure' is defined (e.g. via M-x eval-defun), the 
compiler hangs. This is weird because, unlike `test1' above, 
`test2' doesn't contain a circular list itself; it only builds it 
at run-time.

In contrast, this example doesn't hang, regardless of whether 
`cycle' is defined or not (note the removed declarations):

  (defun cycle (list)
    (let ((newlist (append list ())))
      (nconc newlist newlist)))

  (defun test3 ()
    (cycle '(1 2 3)))

My conjecture is that the `pure' and `side-effect-free' 
declarations within `cycle-pure' (which I assume are picked up 
only once the function definition is loaded) allow the compiler to 
do some constant folding when it sees the expression `(cycle-pure 
'(1 2 3))'. This results in the compiler manipulating a circular 
list at compile-time, just like in `test1', and leads to a hang.

Kind regards,
hokomo

bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

[Andrea Corallo]

hokomo via "Bug reports for GNU Emacs, the Swiss army knife of text
editors" <bug-gnu-emacs@gnu.org> writes:

> Hello,
>
> The Emacs Lisp native compiler goes into an infinite loop when
> compiling code that contains circular objects.
>
> For example, put the following into a file and use M-x
> emacs-lisp-native-compile; it should hang:
>
>  (defun test1 ()
>    '#1=(1 2 3 . #1#))
>
> It seems like this only happens for certain top-level forms, such as
> `defun' (which may be expected behavior, due to the way the file
> compiler processes top-level forms). For example, this doesn't hang:
>
>  (lambda ()
>    '#1=(1 2 3 . #1#))
>
> Here's a more interesting example, which is how I stumbled upon this
> issue in the first place:
>
>  (defun cycle-pure (list)
>    (declare (pure t) (side-effect-free t))
>    (let ((newlist (append list ())))
>      (nconc newlist newlist)))
>
>  (defun test2 ()
>    (cycle-pure '(1 2 3)))
>
> (The definition of `cycle-pure' is copied from the `-cycle' function
> from the dash.el package.)
>
> If `cycle-pure' is not yet defined when compiling, the compiler
> doesn't hang.
>
> However, if `cycle-pure' is defined (e.g. via M-x eval-defun), the
> compiler hangs. This is weird because, unlike `test1' above, `test2'
> doesn't contain a circular list itself; it only builds it at run-time.
>
> In contrast, this example doesn't hang, regardless of whether `cycle'
> is defined or not (note the removed declarations):
>
>  (defun cycle (list)
>    (let ((newlist (append list ())))
>      (nconc newlist newlist)))
>
>  (defun test3 ()
>    (cycle '(1 2 3)))
>
> My conjecture is that the `pure' and `side-effect-free' declarations
> within `cycle-pure' (which I assume are picked up only once the
> function definition is loaded) allow the compiler to do some constant
> folding when it sees the expression `(cycle-pure '(1 2 3))'. This
> results in the compiler manipulating a circular list at compile-time,
> just like in `test1', and leads to a hang.
>
> Kind regards,
> hokomo

I'm pretty sure I've investigated this in the past.  IIRC this is due
some cl- function hanging on a circular list.  Can't find the bug number
ATM.

  Andrea

bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

[Andrea Corallo]

Andrea Corallo <acorallo@gnu.org> writes:

> hokomo via "Bug reports for GNU Emacs, the Swiss army knife of text
> editors" <bug-gnu-emacs@gnu.org> writes:
>
>> Hello,
>>
>> The Emacs Lisp native compiler goes into an infinite loop when
>> compiling code that contains circular objects.
>>
>> For example, put the following into a file and use M-x
>> emacs-lisp-native-compile; it should hang:
>>
>>  (defun test1 ()
>>    '#1=(1 2 3 . #1#))
>>
>> It seems like this only happens for certain top-level forms, such as
>> `defun' (which may be expected behavior, due to the way the file
>> compiler processes top-level forms). For example, this doesn't hang:
>>
>>  (lambda ()
>>    '#1=(1 2 3 . #1#))
>>
>> Here's a more interesting example, which is how I stumbled upon this
>> issue in the first place:
>>
>>  (defun cycle-pure (list)
>>    (declare (pure t) (side-effect-free t))
>>    (let ((newlist (append list ())))
>>      (nconc newlist newlist)))
>>
>>  (defun test2 ()
>>    (cycle-pure '(1 2 3)))
>>
>> (The definition of `cycle-pure' is copied from the `-cycle' function
>> from the dash.el package.)
>>
>> If `cycle-pure' is not yet defined when compiling, the compiler
>> doesn't hang.
>>
>> However, if `cycle-pure' is defined (e.g. via M-x eval-defun), the
>> compiler hangs. This is weird because, unlike `test1' above, `test2'
>> doesn't contain a circular list itself; it only builds it at run-time.
>>
>> In contrast, this example doesn't hang, regardless of whether `cycle'
>> is defined or not (note the removed declarations):
>>
>>  (defun cycle (list)
>>    (let ((newlist (append list ())))
>>      (nconc newlist newlist)))
>>
>>  (defun test3 ()
>>    (cycle '(1 2 3)))
>>
>> My conjecture is that the `pure' and `side-effect-free' declarations
>> within `cycle-pure' (which I assume are picked up only once the
>> function definition is loaded) allow the compiler to do some constant
>> folding when it sees the expression `(cycle-pure '(1 2 3))'. This
>> results in the compiler manipulating a circular list at compile-time,
>> just like in `test1', and leads to a hang.
>>
>> Kind regards,
>> hokomo
>
> I'm pretty sure I've investigated this in the past.  IIRC this is due
> some cl- function hanging on a circular list.  Can't find the bug number
> ATM.
>
>   Andrea

Okay I believe this most likely is a duplicate of bug#57957.

bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

[Stefan Kangas]

Andrea Corallo <acorallo@gnu.org> writes:

> Okay I believe this most likely is a duplicate of bug#57957.

Should the bugs be merged?

bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

[Andrea Corallo]

Stefan Kangas <stefankangas@gmail.com> writes:

> Andrea Corallo <acorallo@gnu.org> writes:
>
>> Okay I believe this most likely is a duplicate of bug#57957.
>
> Should the bugs be merged?

Hi Stefan,

yes I think so.

  Andrea

bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

[Stefan Kangas]

forcemerge 57957 67883
thanks

Andrea Corallo <acorallo@gnu.org> writes:

> Stefan Kangas <stefankangas@gmail.com> writes:
>
>> Andrea Corallo <acorallo@gnu.org> writes:
>>
>>> Okay I believe this most likely is a duplicate of bug#57957.
>>
>> Should the bugs be merged?
>
> Hi Stefan,
>
> yes I think so.
>
>   Andrea

Done.

bug#67883: 29.1.90; Native compiler hangs when compiling code with circular objects

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

Merging the two indeed seems appropriate.

FWIW, I've read the other thread [1] and agree with Stefan's view 
that circular structures should be handled correctly by the 
compiler. I believe the example with `cycle-pure' shows that this 
is both useful and necessary, since circular structures can appear 
even without being directly present in the source code as 
literals, e.g. after compiler optimizations (which seems to be the 
case here, although I haven't confirmed it 100%).

- [1] <https://debbugs.gnu.org/cgi/bugreport.cgi?bug=57957>

Kind regards,
hokomo