bug#63103: 30.0.50; nconc compiler optimization breaks user packages

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Maks]

Hello,

I'm sorry if you received similar emails from me, there were problems
with sending.

Commit e6ca5834a6eab91023e9f968b65683d0a74db1e7 ('Improved nconc and append compiler optimisations') breaks
vertico.el package. After very long debugging time I figured out that this commit affects behavior of
`completion-hilit-commonality` function of minibuffer.el. I don't completely understand how it works buf try
do describe some details.

If I set breakpoint before breaking commit to 'vertico--affixate then I'll get next stacktrace
```
Debugger entered--entering a function:
* vertico--affixate((#("report-emacs-bug" 0 1 (face (completions-first-difference))) #("cd" 0 1 (face (completions-first-difference))) #("5x5" 0 1 (face (completions-first-difference))) #("arp" 0 1 (face (completions-first-difference))) #("dbx" 0 1 (face (completions-first-difference))) #("dig" 0 1 (face (completions-first-difference))) #("erc" 0 1 (face (completions-first-difference))) #("ert" 0 1 (face (completions-first-difference))) #("eww" 0 1 (face (completions-first-difference))) #("ftp" 0 1 (face (completions-first-difference)))))
  vertico--arrange-candidates()
  vertico--exhibit()
  ...
```
buf if I do the same after breaking commit I'll get stacktrace
```
Debugger entered--entering a function:
* vertico--affixate((#("report-emacs-bug" 0 1 (face (completions-first-difference))) #("cd" 0 1 (face (completions-first-difference))) #("5x5" 0 1 (face (completions-first-difference))) #("arp" 0 1 (face (completions-first-difference))) #("dbx" 0 1 (face (completions-first-difference))) #("dig" 0 1 (face (completions-first-difference))) #("erc" 0 1 (face (completions-first-difference))) #("ert" 0 1 (face (completions-first-difference))) #("eww" 0 1 (face (completions-first-difference))) #("ftp" 0 1 (face (completions-first-difference))) . 0))
  vertico--arrange-candidates()
  vertico--exhibit()
  ...
```

As you can see, the difference is in the tail of the list. With the such tail vertico.el package crashed with error:
```
Error in post-command-hook (vertico--exhibit): (wrong-type-argument listp 0)
```

But testing `completion-hilit-commonality` in REPL separetely from vertico.el package
give the same result (with 0 at the end of list).

Before sending this report I have tried a lot of versions of the
vertico.el package and have the same result. So I tend to think that problem is not directly
related to package. 

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Daniel Mendler]

The problem is that `(nconc list nil)` is optimized to `list`. However
improper lists like `(a b c . 0)` should be turned into `(a b c)`.

Daniel

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Philip Kaludercic]

Daniel Mendler <mail@daniel-mendler.de> writes:

> The problem is that `(nconc list nil)` is optimized to `list`. However
> improper lists like `(a b c . 0)` should be turned into `(a b c)`.

Where is this behaviour documented?

> Daniel

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Daniel Mendler]

On 4/27/23 07:44, Philip Kaludercic wrote:
>> The problem is that `(nconc list nil)` is optimized to `list`. However
>> improper lists like `(a b c . 0)` should be turned into `(a b c)`.
> 
> Where is this behaviour documented?

This behavior is not documented explicitly. However the docstring states
that "Only the last argument is not altered, and need not be a list".
Due to symmetry reasons it is not far-fetched to assume that when
`nconc' can be used to turn a proper list into an improper list, that
the inverse works too. Most of the docstrings do not specify functions
on such a detailed and formal level.

Maybe Stefan can give a bit more background regarding the support of
improper list for Elisp functions. The main use case I've observed is
for `completion-all-completions' which uses the last cdr to return the
base position of the completion. Iirc `cl-loop' also handles improper
lists.

Generally I'd be wary about changing the semantics of functions since
this leads to bugs which are hard to debug. One could decide to restrict
`nconc' to proper lists only, not only via the bytecompiler optimization
but also by erroring out if improper lists are passed as argument.

Probably it is easier to explicitly allow the last nil argument in the
bytecode optimizer specially to retain the existing behavior for
improper lists.

Daniel

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Mattias Engdegård]

27 apr. 2023 kl. 08.37 skrev Daniel Mendler <mail@daniel-mendler.de>:

> This behavior is not documented explicitly. However the docstring states
> that "Only the last argument is not altered, and need not be a list".

Indeed. It's clear that this behaviour was never really intended, but also that it was a natural consequence of most Lisp implementations. For instance, Common Lisp specifies this behaviour but only did so after errata.

Although the utility of accepting dotted lists is very slight and requiring proper list for all but the last argument would have made it easier for us, this obviously needs to be a well-reasoned change if made at all. I'll remove the troublesome compiler transform right away.

> Due to symmetry reasons it is not far-fetched to assume that when
> `nconc' can be used to turn a proper list into an improper list, that
> the inverse works too.

I don't think that's a valid assumption -- when the documentation says that arguments are lists, then they should be proper lists. The behaviour for improper lists needs to be specified explicitly, in particular in this case when the function actually overwrites arbitrary information in the input, not just a terminating nil.

Thank you very much for finding this bug!

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Daniel Mendler]

On 4/27/23 11:47, Mattias Engdegård wrote:
> Although the utility of accepting dotted lists is very slight and requiring proper list for all but the last argument would have made it easier for us, this obviously needs to be a well-reasoned change if made at all. I'll remove the troublesome compiler transform right away.

Thanks for fixing the issue! I agree that improper lists are of limited
utility. It wasn't the best idea to use them for the
`completion-all-completions' API since this makes manipulation of the
result for API users less convenient from my experience.

>> Due to symmetry reasons it is not far-fetched to assume that when
>> `nconc' can be used to turn a proper list into an improper list, that
>> the inverse works too.
> 
> I don't think that's a valid assumption -- when the documentation says that arguments are lists, then they should be proper lists. The behaviour for improper lists needs to be specified explicitly, in particular in this case when the function actually overwrites arbitrary information in the input, not just a terminating nil.

Well, my assumption didn't completely stand on its own. Given that the
last argument can be a non-list suggests that the last argument is not
inspected or mutated, but just overwrites the cdr of the second to last
argument. This then implies that the second to last argument could also
be an improper list. Given that CL and Elisp have behaved like this for
a long time, it seems better to preserve this property. I think it is
kind of nice that `nconc' can be used as a tool to turn a proper list
into an improper list and vice versa. It may be good to document this in
the `nconc' docstring and the Elisp manual.

Daniel

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Mattias Engdegård]

27 apr. 2023 kl. 12.42 skrev Daniel Mendler <mail@daniel-mendler.de>:

> I think it is
> kind of nice that `nconc' can be used as a tool to turn a proper list
> into an improper list and vice versa.

It's a bit obscure, though --

  (setcdr (last X) nil)

is a lot clearer than

  (nconc X nil)

and when the latter is preferred for performance, a comment might be polite to the reader.

Anyway, a fix has been pushed to master, and the manual entry for `nconc` got an extra example.

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Daniel Mendler]

On 4/27/23 14:28, Mattias Engdegård wrote:
> 27 apr. 2023 kl. 12.42 skrev Daniel Mendler <mail@daniel-mendler.de>:
> 
>> I think it is
>> kind of nice that `nconc' can be used as a tool to turn a proper list
>> into an improper list and vice versa.
> 
> It's a bit obscure, though --

Probably. I am not sure if I came up with this pattern independently. It
is likely that I've seen it in some other packages. So it is good that
this is fixed.

>   (setcdr (last X) nil)
> 
> is a lot clearer than
> 
>   (nconc X nil)
> 
> and when the latter is preferred for performance, a comment might be polite to the reader.

The problem is that `setcdr' of `last' is not correct for the empty
list. The two lines are not equivalent.

> Anyway, a fix has been pushed to master, and the manual entry for `nconc` got an extra example.

Thanks.

Daniel

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Maks]

Thanks for the fix, it works!

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Drew Adams]

> The behaviour
> for improper lists needs to be specified explicitly, in particular in
> this case when the function actually overwrites arbitrary information in
> the input, not just a terminating nil.

Yes, the use of a dotted list (a term that's clearer
and more sympathetic than "improper list") for all
but the last arg needs to be documented.

(Note: *ALL* but the last.)

> Well, my assumption didn't completely stand on its own. Given that the
> last argument can be a non-list suggests that the last argument is not
> inspected or mutated, but just overwrites the cdr of the second to last
> argument. This then implies that the second to last argument could also
> be an improper list. Given that CL and Elisp have behaved like this for
> a long time, it seems better to preserve this property. I think it is
> kind of nice that `nconc' can be used as a tool to turn a proper list
> into an improper list and vice versa. It may be good to document this in
> the `nconc' docstring and the Elisp manual.

+1.

You both agree that this behavior (1) shouldn't be
lost and (2) should be documented.  That's exactly
the position taken by Common Lisp.

Please document this behavior as part of the bug
fix, if you haven't already.

bug#63103: 30.0.50; nconc compiler optimization breaks user packages

[Daniel Mendler]

On 4/27/23 15:54, Drew Adams wrote:
>> Well, my assumption didn't completely stand on its own. Given that the
>> last argument can be a non-list suggests that the last argument is not
>> inspected or mutated, but just overwrites the cdr of the second to last
>> argument. This then implies that the second to last argument could also
>> be an improper list. Given that CL and Elisp have behaved like this for
>> a long time, it seems better to preserve this property. I think it is
>> kind of nice that `nconc' can be used as a tool to turn a proper list
>> into an improper list and vice versa. It may be good to document this in
>> the `nconc' docstring and the Elisp manual.
> 
> +1.
> 
> You both agree that this behavior (1) shouldn't be
> lost and (2) should be documented.  That's exactly
> the position taken by Common Lisp.
> 
> Please document this behavior as part of the bug
> fix, if you haven't already.

Mattias already documented the behavior for dotted lists in the Elisp
manual and added a regression test. See commit
5ead8c5f69b0a69bac4641d5003ee422d6b67038.

Daniel