GNU bug report logs - #76017
31.0.50; Which args can cl-nintersection and cl-nset-difference mutate?

Previous Next

Full log

View this message in rfc822 format

From: Pip Cet <pipcet <at> protonmail.com>
To: "Basil L. Contovounesios" <basil <at> contovou.net>
Cc: Mattias Engdegård <mattias.engdegard <at> gmail.com>, Stefan Monnier <monnier <at> iro.umontreal.ca>, 76017 <at> debbugs.gnu.org
Subject: bug#76017: 31.0.50; Which args can cl-nintersection and cl-nset-difference mutate?
Date: Sun, 02 Feb 2025 18:30:56 +0000

"Basil L. Contovounesios" <basil <at> contovou.net> writes:

> Since as far back as I can go in emacs.git history, the manual says:
>
>  -- Function: cl-nintersection list1 list2 &key :test :test-not :key
>      This is a destructive version of ‘cl-intersection’.  It tries to
>      reuse storage of LIST1 rather than copying.  It does _not_ reuse
>      the storage of LIST2.

> whereas their docstrings say:
>
>  (cl-nintersection LIST1 LIST2 [KEYWORD VALUE]...)
>  Combine LIST1 and LIST2 using a set-intersection operation.
>  The resulting list contains all items that appear in both LIST1 and LIST2.
>  This is a destructive function; it reuses the storage of LIST1 and LIST2
>  whenever possible.

On the third hand, the implementation is simply:

(defun cl-nintersection (cl-list1 cl-list2 &rest cl-keys)
  "Combine LIST1 and LIST2 using a set-intersection operation.
The resulting list contains all items that appear in both LIST1 and LIST2.
This is a destructive function; it reuses the storage of LIST1 and LIST2
whenever possible.
\nKeywords supported:  :test :test-not :key
\n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
  (and cl-list1 cl-list2 (apply 'cl-intersection cl-list1 cl-list2 cl-keys)))

So no storage is ever reused, right?

So is this about the optimizations that cl-nintersection might in theory
one day perform, but didn't do in 1993 and doesn't do today?

Or am I missing something there?

I think the situation is similar to plist-put: you're taught always to
reassign the return value to the variable you're using, but it only ever
actually changes if the original list was nil.  We reserve the right to
switch to an optimized version but, so far, there was no need to.

> My arguments in favour of the manual:
> - Documented for decades in both Emacs and CL docs.
> - It is the weaker of the two requirements, thus backward-compatible.

"weaker" in the sense that it gives the Lisp hacker more options, and
the Lisp implementor fewer options.  I think we should go for "simpler":
assume both arguments may be mutated, and don't worry about specifying
them in the "right" order.

> - Set difference implementations do not naturally benefit from modifying
>   the second set (though I would love to see a counterexample).

I'm not sure I agree.  If you've got a cheap population count, you start
with the smaller set and throw out unnecessary elements, returning that
set.

> - Callers of cl-nintersection having to ensure both arguments are safe
>   to mutate (e.g. through excessive copying) could diminish any
>   performance benefit it has over cl-intersection.

Which is 0, right?

> If there is agreement, I can follow up with a patch for our docs and
> tests.

Both the "tries to" and "whenever possible" seem simply incorrect to me,
but the byte compiler warning can stay, IMHO.

Pip

Previous Next

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