bug#34852: 26.1; seq-intersection ignores nil as element

classic Classic list List threaded Threaded
43 messages Options
123
Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Miguel V. S. Frasson
Hi.

seq-intersection skips nil as common element, so returns wrong result.

Reproducing from emacs -Q:

In *scratch* buffer, eval the expressions

(progn
  (require 'seq)
  (seq-intersection '(1 2 nil) '(1 nil) 'eq))

-> (1)

(seq-intersection '(1 2 nil) '(1 nil) 'equal)

-> (1)

Expected result in both cases: (1 nil)

Cheers

Miguel Frasson
--

In GNU Emacs 26.1 (build 1, i686-w64-mingw32)
 of 2018-05-30 built on CIRROCUMULUS
Repository revision: 07f8f9bc5a51f5aa94eb099f3e15fbe0c20ea1ea
Windowing system distributor 'Microsoft Corp.', version 10.0.17134
Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.
seq
Configured using:
 'configure --without-dbus --host=i686-w64-mingw32
 --without-compress-install 'CFLAGS=-O2 -static -g3''

Configured features:
XPM JPEG TIFF GIF PNG RSVG SOUND NOTIFY ACL GNUTLS LIBXML2 ZLIB
TOOLKIT_SCROLL_BARS THREADS LCMS2

Important settings:
  value of $LANG: PTB
  locale-coding-system: cp1252

Major mode: Lisp Interaction

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  eldoc-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
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message rmc puny dired dired-loaddefs
format-spec rfc822 mml easymenu mml-sec password-cache epa derived epg
epg-config gnus-util rmail rmail-loaddefs mm-decode mm-bodies mm-encode
mail-parse rfc2231 mailabbrev gmm-utils mailheader sendmail rfc2047
rfc2045 ietf-drums mm-util mail-prsvr mail-utils seq byte-opt gv
bytecomp byte-compile cconv cl-loaddefs cl-lib elec-pair time-date
mule-util tooltip eldoc electric uniquify ediff-hook vc-hooks
lisp-float-type mwheel dos-w32 ls-lisp disp-table term/w32-win w32-win
w32-vars term/common-win tool-bar dnd fontset image regexp-opt fringe
tabulated-list replace newcomment text-mode elisp-mode lisp-mode
prog-mode register page menu-bar rfn-eshadow isearch timer select
scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame cl-generic 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 charscript charprop case-table epa-hook jka-cmpr-hook
help simple abbrev obarray minibuffer cl-preloaded nadvice loaddefs
button faces cus-face macroexp files text-properties overlay sha1 md5
base64 format env code-pages mule custom widget hashtable-print-readable
backquote w32notify w32 lcms2 multi-tty make-network-process emacs)

Memory information:
((conses 8 96961 9032)
 (symbols 32 20186 1)
 (miscs 32 38 140)
 (strings 16 29656 2096)
 (string-bytes 1 766583)
 (vectors 12 14052)
 (vector-slots 4 507930 10192)
 (floats 8 52 289)
 (intervals 28 263 59)
 (buffers 536 12))


--
Miguel Vinicius Santini Frasson
[hidden email]



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Michael Heerdegen
"Miguel V. S. Frasson" <[hidden email]> writes:

> seq-intersection skips nil as common element, so returns wrong result.
>
> Reproducing from emacs -Q:
>
> In *scratch* buffer, eval the expressions
>
> (progn
>   (require 'seq)
>   (seq-intersection '(1 2 nil) '(1 nil) 'eq))
>
> -> (1)
>
> (seq-intersection '(1 2 nil) '(1 nil) 'equal)
>
> -> (1)
>
> Expected result in both cases: (1 nil)

Indeed.

Nicolas, can you have a look?  We probably can't use `seq-contains' in
the implementation.


Thanks,

Michael.



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Miguel V. S. Frasson

"Miguel V. S. Frasson" <[hidden email]> writes:

> seq-intersection skips nil as common element, so returns wrong result.
>
> Reproducing from emacs -Q:
>
> In *scratch* buffer, eval the expressions
>
> (progn
>   (require 'seq)
>   (seq-intersection '(1 2 nil) '(1 nil) 'eq))
>
> -> (1)
>
> (seq-intersection '(1 2 nil) '(1 nil) 'equal)
>
> -> (1)
>
> Expected result in both cases: (1 nil)
This is actually due to seq-contains returning the element found, rather
than a boolean indicating whether the element was found:

(seq-contains '(nil) nil) ; => nil

The nature of seq-contains as a predicate-ish has been discussed in the
past[1], and Stefan recently fixed a similar problem with
map-contains-key[2].

[1]: https://lists.gnu.org/archive/html/emacs-devel/2016-07/msg01256.html
[2]: * lisp/emacs-lisp/map.el: Make the functions generic
  2018-12-11 17:54:13 -0500
  https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=1691a51094d35ac4b2c311fa407c6b77eea7a105

One solution is to leave seq-contains as it is, and switch to using
seq-position (or some new predicate) as a predicate instead.  Another is
to make seq-contains return a boolean instead of the needle found, which
would be a backward-incompatible change similar to that for
map-contains-key.  I attach a patch for each of these respective
solutions; WDYT?

--
Basil

0001-Do-not-use-seq-contains-as-a-predicate-bug-34852.patch (5K) Download Attachment
0001-Return-boolean-instead-of-element-in-seq-contains.patch (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Miguel V. S. Frasson
Hi.
In https://lists.gnu.org/archive/html/emacs-devel/2016-07/msg01256.html
it is mentioned that:

>    I believe `seq-contains' was introduced for convenience:
>    it is used elsewhere in seq.el and map.el.

so there may be problems in map.el as well if it is used as a
predicate there, or even in more files.

Miguel.

Em qui, 14 de mar de 2019 às 09:22, Basil L. Contovounesios
<[hidden email]> escreveu:

>
>
> "Miguel V. S. Frasson" <[hidden email]> writes:
>
> > seq-intersection skips nil as common element, so returns wrong result.
> >
> > Reproducing from emacs -Q:
> >
> > In *scratch* buffer, eval the expressions
> >
> > (progn
> >   (require 'seq)
> >   (seq-intersection '(1 2 nil) '(1 nil) 'eq))
> >
> > -> (1)
> >
> > (seq-intersection '(1 2 nil) '(1 nil) 'equal)
> >
> > -> (1)
> >
> > Expected result in both cases: (1 nil)
>
> This is actually due to seq-contains returning the element found, rather
> than a boolean indicating whether the element was found:
>
> (seq-contains '(nil) nil) ; => nil
>
> The nature of seq-contains as a predicate-ish has been discussed in the
> past[1], and Stefan recently fixed a similar problem with
> map-contains-key[2].
>
> [1]: https://lists.gnu.org/archive/html/emacs-devel/2016-07/msg01256.html
> [2]: * lisp/emacs-lisp/map.el: Make the functions generic
>   2018-12-11 17:54:13 -0500
>   https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=1691a51094d35ac4b2c311fa407c6b77eea7a105
>
> One solution is to leave seq-contains as it is, and switch to using
> seq-position (or some new predicate) as a predicate instead.  Another is
> to make seq-contains return a boolean instead of the needle found, which
> would be a backward-incompatible change similar to that for
> map-contains-key.  I attach a patch for each of these respective
> solutions; WDYT?
>
> --
> Basil



--
Miguel Vinicius Santini Frasson
[hidden email]



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Michael Heerdegen
In reply to this post by Basil L. Contovounesios
"Basil L. Contovounesios" <[hidden email]> writes:

> One solution is to leave seq-contains as it is, and switch to using
> seq-position (or some new predicate) as a predicate instead.  Another is
> to make seq-contains return a boolean instead of the needle found, which
> would be a backward-incompatible change similar to that for
> map-contains-key.  I attach a patch for each of these respective
> solutions; WDYT?

We also have `seq-some' which can be used as a contain predicate,
e.g. to fix this bug:


From c53a80c29e696ab64d4279ca6f495c8e0e1b16b4 Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <[hidden email]>
Date: Thu, 14 Mar 2019 13:55:41 +0100
Subject: [PATCH] Fix seq-intersection with nil

---
 lisp/emacs-lisp/seq.el | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 4a811d7895..5718343a8f 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -409,12 +409,13 @@ seq-sort-by
 (cl-defgeneric seq-intersection (sequence1 sequence2 &optional testfn)
   "Return a list of the elements that appear in both SEQUENCE1 and SEQUENCE2.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
-  (seq-reduce (lambda (acc elt)
-                (if (seq-contains sequence2 elt testfn)
-                    (cons elt acc)
-                  acc))
-              (seq-reverse sequence1)
-              '()))
+  (let ((testfn (or testfn #'equal)))
+    (seq-reduce (lambda (acc elt)
+                  (if (seq-some (apply-partially testfn elt) sequence2)
+                      (cons elt acc)
+                    acc))
+                (seq-reverse sequence1)
+                '())))

 (cl-defgeneric seq-difference (sequence1 sequence2 &optional testfn)
   "Return a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.
--
2.20.1



(probably needed in more places as you did in one of your patches)

So I think we don't necessarily need something new or a backward
incompatible change.


Michael.
Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Nicolas Petton-2
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

> Indeed.
>
> Nicolas, can you have a look?  We probably can't use `seq-contains' in
> the implementation.

Yes, I will.

Cheers,
Nico

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Stefan Monnier
In reply to this post by Michael Heerdegen
Yet another approach might be to make an exception in seq-contains if
the returned element is nil (and return something else in that case).
E.g.

    diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
    index 4a811d7895..d2398eb588 100644
    --- a/lisp/emacs-lisp/seq.el
    +++ b/lisp/emacs-lisp/seq.el
    @@ -360,7 +360,7 @@ seq-sort-by
     Equality is defined by TESTFN if non-nil or by `equal' if nil."
       (seq-some (lambda (e)
                   (when (funcall (or testfn #'equal) elt e)
    -                e))
    +                (or e t)))
                 sequence))
     
     (cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)


-- Stefan



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Miguel V. S. Frasson
"Miguel V. S. Frasson" <[hidden email]> writes:

> In https://lists.gnu.org/archive/html/emacs-devel/2016-07/msg01256.html
> it is mentioned that:
>
>>    I believe `seq-contains' was introduced for convenience:
>>    it is used elsewhere in seq.el and map.el.
>
> so there may be problems in map.el as well if it is used as a
> predicate there, or even in more files.

All occurences of seq-contains I could find in emacs.git are addressed
in the two patches.

Thanks,

--
Basil



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

> "Basil L. Contovounesios" <[hidden email]> writes:
>
>> One solution is to leave seq-contains as it is, and switch to using
>> seq-position (or some new predicate) as a predicate instead.  Another is
>> to make seq-contains return a boolean instead of the needle found, which
>> would be a backward-incompatible change similar to that for
>> map-contains-key.  I attach a patch for each of these respective
>> solutions; WDYT?
>
> We also have `seq-some' which can be used as a contain predicate,
> e.g. to fix this bug:
>
> From c53a80c29e696ab64d4279ca6f495c8e0e1b16b4 Mon Sep 17 00:00:00 2001
> From: Michael Heerdegen <[hidden email]>
> Date: Thu, 14 Mar 2019 13:55:41 +0100
> Subject: [PATCH] Fix seq-intersection with nil
>
> ---
>  lisp/emacs-lisp/seq.el | 13 +++++++------
>  1 file changed, 7 insertions(+), 6 deletions(-)
>
> diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
> index 4a811d7895..5718343a8f 100644
> --- a/lisp/emacs-lisp/seq.el
> +++ b/lisp/emacs-lisp/seq.el
> @@ -409,12 +409,13 @@ seq-sort-by
>  (cl-defgeneric seq-intersection (sequence1 sequence2 &optional testfn)
>    "Return a list of the elements that appear in both SEQUENCE1 and SEQUENCE2.
>  Equality is defined by TESTFN if non-nil or by `equal' if nil."
> -  (seq-reduce (lambda (acc elt)
> -                (if (seq-contains sequence2 elt testfn)
> -                    (cons elt acc)
> -                  acc))
> -              (seq-reverse sequence1)
> -              '()))
> +  (let ((testfn (or testfn #'equal)))
> +    (seq-reduce (lambda (acc elt)
> +                  (if (seq-some (apply-partially testfn elt) sequence2)
> +                      (cons elt acc)
> +                    acc))
> +                (seq-reverse sequence1)
> +                '())))
>
>  (cl-defgeneric seq-difference (sequence1 sequence2 &optional testfn)
>    "Return a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.
> --
> 2.20.1
>
>
> (probably needed in more places as you did in one of your patches)
>
> So I think we don't necessarily need something new or a backward
> incompatible change.

My first patch makes an analogous backward-compatible change using the
more efficient seq-position in place of seq-some.

Thanks,

--
Basil



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Stefan Monnier
Stefan Monnier <[hidden email]> writes:

> Yet another approach might be to make an exception in seq-contains if
> the returned element is nil (and return something else in that case).
> E.g.
>
>     diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
>     index 4a811d7895..d2398eb588 100644
>     --- a/lisp/emacs-lisp/seq.el
>     +++ b/lisp/emacs-lisp/seq.el
>     @@ -360,7 +360,7 @@ seq-sort-by
>      Equality is defined by TESTFN if non-nil or by `equal' if nil."
>        (seq-some (lambda (e)
>                    (when (funcall (or testfn #'equal) elt e)
>     -                e))
>     +                (or e t)))
>                  sequence))
>      
>      (cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)

This is both backward-incompatible and inconsistent.  If we agree to
make a backward-incompatible change, I would rather turn seq-contains
into a proper predicate, as per my second patch.  Besides, returning the
element found isn't particularly useful to begin with, as the caller
already has access to that value.

Either way, we can install the backward-compatible first patch (which
uses seq-position in place of seq-contains) to fix this bug, and later
discuss any backward-incompatible changes to seq-contains.

Thanks,

--
Basil



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Michael Heerdegen
In reply to this post by Basil L. Contovounesios
"Basil L. Contovounesios" <[hidden email]> writes:

> My first patch makes an analogous backward-compatible change using the
> more efficient seq-position in place of seq-some.

Why is it more efficient?  The implementations are more or less
analogue, with the exception that seq-position additionally increments a
counter.


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Nicolas Petton-2
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

Hi Michael,

> We also have `seq-some' which can be used as a contain predicate,
> e.g. to fix this bug:

Using seq-contains was wrong, and I think seq-some should have been used
instead, so I like your patch better (it's IMO better to use seq-some
used as a predicate than seq-position).

Unless somebody disagrees, I'll install your patch.

Cheers,
Nico

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Michael Heerdegen
In reply to this post by Basil L. Contovounesios
"Basil L. Contovounesios" <[hidden email]> writes:

> Besides, returning the element found isn't particularly useful to
> begin with, as the caller already has access to that value.

Depends on the TESTFN.  You could use seq-contains as a replacement for
alist-get, for example, when you make TESTFN look at the sequence's
car's.  This is more or less the same as using :key in cl-member, so
people might be doing this and there is some change that we break
existing code.


Michael.



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

> "Basil L. Contovounesios" <[hidden email]> writes:
>
>> My first patch makes an analogous backward-compatible change using the
>> more efficient seq-position in place of seq-some.
>
> Why is it more efficient?  The implementations are more or less
> analogue, with the exception that seq-position additionally increments a
> counter.

Because seq-some involves an additional level of function indirection.
This is confirmed by profiling and the attached mini-benchmark, when run
as follows:

emacs -batch -f batch-byte-compile bench.el
emacs -script bench.elc

A call to seq-position is also less verbose than one to seq-some for the
purpose of finding an element of a sequence.

Having said that, the differences are obviously very small.

--
Basil



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Nicolas Petton-2
Nicolas Petton <[hidden email]> writes:

> Michael Heerdegen <[hidden email]> writes:
>
> Hi Michael,
>
>> We also have `seq-some' which can be used as a contain predicate,
>> e.g. to fix this bug:
>
> Using seq-contains was wrong, and I think seq-some should have been used
> instead, so I like your patch better (it's IMO better to use seq-some
> used as a predicate than seq-position).
>
> Unless somebody disagrees, I'll install your patch.

If you go with the seq-some patch then please edit it to avoid using
apply-partially, which is quite inefficient.

The implementations of seq-set-equal-p, seq-uniq, and seq-difference
will also need to be updated, in addition to that of seq-intersection.

--
Basil



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

> "Basil L. Contovounesios" <[hidden email]> writes:
>
>> Besides, returning the element found isn't particularly useful to
>> begin with, as the caller already has access to that value.
>
> Depends on the TESTFN.  You could use seq-contains as a replacement for
> alist-get, for example, when you make TESTFN look at the sequence's
> car's.  This is more or less the same as using :key in cl-member, so
> people might be doing this and there is some change that we break
> existing code.

Fair enough, though I'd be interested to see an example of such logic
that can't be written in a less contrived way.

Thanks,

--
Basil



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Basil L. Contovounesios
In reply to this post by Basil L. Contovounesios

"Basil L. Contovounesios" <[hidden email]> writes:

> Michael Heerdegen <[hidden email]> writes:
>
>> "Basil L. Contovounesios" <[hidden email]> writes:
>>
>>> My first patch makes an analogous backward-compatible change using the
>>> more efficient seq-position in place of seq-some.
>>
>> Why is it more efficient?  The implementations are more or less
>> analogue, with the exception that seq-position additionally increments a
>> counter.
>
> Because seq-some involves an additional level of function indirection.
> This is confirmed by profiling and the attached mini-benchmark, when run
> as follows:
>
> emacs -batch -f batch-byte-compile bench.el
> emacs -script bench.elc
Oops, forgot to attach.

--
Basil

bench.el (602 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Miguel V. S. Frasson
In reply to this post by Stefan Monnier
Hi

In any case, of another implementation for seq-intersection or not, I
think that the solution from Stefan should be implemented anyway
because

* it makes seq-contains provide a useful return value when ELT=nil, so
it is a good exception; If ELT=nil, seq-contains currently returns nil
anyway;

* it makes seq-contains become a real predicate function, making it more useful;

* since seq-contains has been used as predicate before, it is
unpredictable which code uses it out of official repositories, so this
fix potentially fixes other code.

Cheers

Miguel


Em qui, 14 de mar de 2019 às 10:34, Stefan Monnier
<[hidden email]> escreveu:

>
> Yet another approach might be to make an exception in seq-contains if
> the returned element is nil (and return something else in that case).
> E.g.
>
>     diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
>     index 4a811d7895..d2398eb588 100644
>     --- a/lisp/emacs-lisp/seq.el
>     +++ b/lisp/emacs-lisp/seq.el
>     @@ -360,7 +360,7 @@ seq-sort-by
>      Equality is defined by TESTFN if non-nil or by `equal' if nil."
>        (seq-some (lambda (e)
>                    (when (funcall (or testfn #'equal) elt e)
>     -                e))
>     +                (or e t)))
>                  sequence))
>
>      (cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)
>
>
> -- Stefan



--
Miguel Vinicius Santini Frasson
[hidden email]



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Stefan Monnier
> If ELT=nil, seq-contains currently returns nil anyway;

That's true when `testfn` is nil, but not if you provide
your own `testfn`.


        Stefan



Reply | Threaded
Open this post in threaded view
|

bug#34852: 26.1; seq-intersection ignores nil as element

Miguel V. S. Frasson
Hi

Em qui, 14 de mar de 2019 18:43, Stefan Monnier
<[hidden email]> escreveu:
>
> > If ELT=nil, seq-contains currently returns nil anyway;
>
> That's true when `testfn` is nil, but not if you provide
> your own `testfn`.

Not really.

(seq-contains nil '(nil t foo) (lambda (x) t))  ->  nil

It returns *nil* if testfn fails, or *nil* (ELT) if it succeds.

Miguel



123