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

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
mvsfrasson@gmail.com

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

[Michael Heerdegen]

"Miguel V. S. Frasson" <mvsfrasson@gmail.com> 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.

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

[Basil L. Contovounesios]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: 0001-Do-not-use-seq-contains-as-a-predicate-bug-34852.patch --]
[-- Type: text/x-diff, Size: 5920 bytes --]

From afddf78a703b73729ec7b5562747ebeb5077966d Mon Sep 17 00:00:00 2001
From: "Basil L. Contovounesios" <contovob@tcd.ie>
Date: Thu, 14 Mar 2019 12:10:28 +0000
Subject: [PATCH] Do not use seq-contains as a predicate (bug#34852)

* doc/lispref/sequences.texi (Sequence Functions):
* lisp/emacs-lisp/seq.el (seq-contains): Document unsuitability of
seq-contains as a predicate.
(seq-position): Document return value when needle not found.
(seq-set-equal-p, seq-uniq, seq-intersection, seq-difference): Use
seq-position instead of seq-contains as a predicate.
* test/lisp/emacs-lisp/seq-tests.el
(test-seq-contains-should-return-the-elt):
(test-seq-position): Test case when needle is nil.
---
 doc/lispref/sequences.texi        |  7 +++++++
 lisp/emacs-lisp/seq.el            | 21 ++++++++++++---------
 test/lisp/emacs-lisp/seq-tests.el | 14 +++++++++-----
 3 files changed, 28 insertions(+), 14 deletions(-)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 0c3c4e3b28..e33944a2dd 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -787,6 +787,9 @@ Sequence Functions
 @var{elt}.  If the optional argument @var{function} is non-@code{nil},
 it is a function of two arguments to use instead of the default @code{equal}.
 
+Note that this function is not suitable as a predicate since its value
+depends on that of @var{elt}, which may be @code{nil}.
+
 @example
 @group
 (seq-contains '(symbol1 symbol2) 'symbol1)
@@ -796,6 +799,10 @@ Sequence Functions
 (seq-contains '(symbol1 symbol2) 'symbol3)
 @result{} nil
 @end group
+@group
+(seq-contains '(symbol1 nil) nil)
+@result{} nil
+@end group
 @end example
 
 @end defun
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 4a811d7895..de8456eb79 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -357,7 +357,9 @@ seq-sort-by
 
 (cl-defgeneric seq-contains (sequence elt &optional testfn)
   "Return the first element in SEQUENCE that is equal to ELT.
-Equality is defined by TESTFN if non-nil or by `equal' if nil."
+Equality is defined by TESTFN if non-nil or by `equal' if nil.
+Note that this function is not suitable as a predicate since its
+value depends on that of ELT, which may be nil."
   (seq-some (lambda (e)
               (when (funcall (or testfn #'equal) elt e)
                 e))
@@ -366,12 +368,13 @@ seq-sort-by
 (cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)
   "Return non-nil if SEQUENCE1 and SEQUENCE2 contain the same elements, regardless of order.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
-  (and (seq-every-p (lambda (item1) (seq-contains sequence2 item1 testfn)) sequence1)
-       (seq-every-p (lambda (item2) (seq-contains sequence1 item2 testfn)) sequence2)))
+  (and (seq-every-p (lambda (item1) (seq-position sequence2 item1 testfn)) sequence1)
+       (seq-every-p (lambda (item2) (seq-position sequence1 item2 testfn)) sequence2)))
 
 (cl-defgeneric seq-position (sequence elt &optional testfn)
   "Return the index of the first element in SEQUENCE that is equal to ELT.
-Equality is defined by TESTFN if non-nil or by `equal' if nil."
+Return nil if no such element is found.  Equality is defined by
+TESTFN if non-nil or by `equal' if nil."
   (let ((index 0))
     (catch 'seq--break
       (seq-doseq (e sequence)
@@ -385,7 +388,7 @@ seq-sort-by
 TESTFN is used to compare elements, or `equal' if TESTFN is nil."
   (let ((result '()))
     (seq-doseq (elt sequence)
-      (unless (seq-contains result elt testfn)
+      (unless (seq-position result elt testfn)
         (setq result (cons elt result))))
     (nreverse result)))
 
@@ -410,7 +413,7 @@ seq-sort-by
   "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)
+                (if (seq-position sequence2 elt testfn)
                     (cons elt acc)
                   acc))
               (seq-reverse sequence1)
@@ -420,9 +423,9 @@ seq-sort-by
   "Return a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
   (seq-reduce (lambda (acc elt)
-                (if (not (seq-contains sequence2 elt testfn))
-                    (cons elt acc)
-                  acc))
+                (if (seq-position sequence2 elt testfn)
+                    acc
+                  (cons elt acc)))
               (seq-reverse sequence1)
               '()))
 
diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index d8f00cfea4..417606d9d7 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -183,7 +183,9 @@ test-sequences-oddp
 
 (ert-deftest test-seq-contains-should-return-the-elt ()
   (with-test-sequences (seq '(3 4 5 6))
-    (should (= 5 (seq-contains seq 5)))))
+    (should (= 5 (seq-contains seq 5))))
+  (should-not (seq-contains '(1 2 nil) nil))
+  (should-not (seq-contains [1 2 nil] nil)))
 
 (ert-deftest test-seq-every-p ()
   (with-test-sequences (seq '(43 54 22 1))
@@ -384,12 +386,14 @@ test-sequences-oddp
 
 (ert-deftest test-seq-position ()
   (with-test-sequences (seq '(2 4 6))
-    (should (null (seq-position seq 1)))
+    (should-not (seq-position seq 1))
+    (should-not (seq-position seq nil))
     (should (= (seq-position seq 4) 1)))
-  (let ((seq '(a b c)))
-    (should (null (seq-position seq 'd #'eq)))
+  (let ((seq '(a b c nil)))
+    (should-not (seq-position seq 'd #'eq))
     (should (= (seq-position seq 'a #'eq) 0))
-    (should (null (seq-position seq (make-symbol "a") #'eq)))))
+    (should (= (seq-position seq nil #'eq) 3))
+    (should-not (seq-position seq (make-symbol "a") #'eq))))
 
 (ert-deftest test-seq-sort-by ()
   (let ((seq ["x" "xx" "xxx"]))
-- 
2.20.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Return-boolean-instead-of-element-in-seq-contains.patch --]
[-- Type: text/x-diff, Size: 4103 bytes --]

From 7b8d5672db306e3bb52196b04c74eb7098ec32a3 Mon Sep 17 00:00:00 2001
From: "Basil L. Contovounesios" <contovob@tcd.ie>
Date: Thu, 14 Mar 2019 11:19:55 +0000
Subject: [PATCH] Return boolean instead of element in seq-contains

* lisp/emacs-lisp/seq.el: Bump major version.
(seq-contains): Return non-nil instead of needle if it is found in
the sequence. (bug#34852)
* test/lisp/emacs-lisp/seq-tests.el (test-seq-contains): Add check
for nil as an element.
(test-seq-contains-should-return-the-elt): Remove, replacing with...
(test-seq-contains-return-non-nil): ...this new test.
* doc/lispref/sequences.texi (Sequence Functions):
* etc/NEWS: Document change to seq-contains.
---
 doc/lispref/sequences.texi        | 9 +++++----
 etc/NEWS                          | 3 +++
 lisp/emacs-lisp/seq.el            | 7 +++----
 test/lisp/emacs-lisp/seq-tests.el | 9 +++++----
 4 files changed, 16 insertions(+), 12 deletions(-)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 0c3c4e3b28..b0c65fe526 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -783,14 +783,15 @@ Sequence Functions
 
 
 @defun seq-contains sequence elt &optional function
-  This function returns the first element in @var{sequence} that is equal to
-@var{elt}.  If the optional argument @var{function} is non-@code{nil},
-it is a function of two arguments to use instead of the default @code{equal}.
+  This function returns non-@code{nil} if an element in @var{sequence}
+is equal to @var{elt}.  If the optional argument @var{function} is
+non-@code{nil}, it is a function of two arguments to use instead of
+the default @code{equal}.
 
 @example
 @group
 (seq-contains '(symbol1 symbol2) 'symbol1)
-@result{} symbol1
+@result{} t
 @end group
 @group
 (seq-contains '(symbol1 symbol2) 'symbol3)
diff --git a/etc/NEWS b/etc/NEWS
index 410c1821ae..b41ff89613 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -383,6 +383,9 @@ buffers.
 New convenience functions 'seq-first' and 'seq-rest' give easy access
 to respectively the first and all but the first elements of sequences.
 
++++
+*** 'seq-contains' now returns a boolean rather than the element found.
+
 ---
 ** Follow mode
 In the current follow group of windows, "ghost" cursors are no longer
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 4a811d7895..73cb985b85 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -4,7 +4,7 @@
 
 ;; Author: Nicolas Petton <nicolas@petton.fr>
 ;; Keywords: sequences
-;; Version: 2.21
+;; Version: 3.0
 ;; Package: seq
 
 ;; Maintainer: emacs-devel@gnu.org
@@ -356,11 +356,10 @@ seq-sort-by
     count))
 
 (cl-defgeneric seq-contains (sequence elt &optional testfn)
-  "Return the first element in SEQUENCE that is equal to ELT.
+  "Return non-nil if an element in SEQUENCE is equal to ELT.
 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))
+              (funcall (or testfn #'equal) elt e))
             sequence))
 
 (cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)
diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index d8f00cfea4..fee31e7f8f 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -176,14 +176,15 @@ test-sequences-oddp
 (ert-deftest test-seq-contains ()
   (with-test-sequences (seq '(3 4 5 6))
     (should (seq-contains seq 3))
-    (should-not (seq-contains seq 7)))
+    (should-not (seq-contains seq 7))
+    (should-not (seq-contains seq nil)))
   (with-test-sequences (seq '())
     (should-not (seq-contains seq 3))
     (should-not (seq-contains seq nil))))
 
-(ert-deftest test-seq-contains-should-return-the-elt ()
-  (with-test-sequences (seq '(3 4 5 6))
-    (should (= 5 (seq-contains seq 5)))))
+(ert-deftest test-seq-contains-return-non-nil ()
+  (should (seq-contains '(1 2 nil) nil))
+  (should (seq-contains [1 2 nil] nil)))
 
 (ert-deftest test-seq-every-p ()
   (with-test-sequences (seq '(43 54 22 1))
-- 
2.20.1


[-- Attachment #3: Type: text/plain, Size: 1345 bytes --]


"Miguel V. S. Frasson" <mvsfrasson@gmail.com> 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

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
<contovob@tcd.ie> escreveu:
>
>
> "Miguel V. S. Frasson" <mvsfrasson@gmail.com> 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
mvsfrasson@gmail.com

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

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 511 bytes --]

"Basil L. Contovounesios" <contovob@tcd.ie> 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:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-seq-intersection-with-nil.patch --]
[-- Type: text/x-diff, Size: 1397 bytes --]

From c53a80c29e696ab64d4279ca6f495c8e0e1b16b4 Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
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


[-- Attachment #3: Type: text/plain, Size: 166 bytes --]


(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.

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 189 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

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

Yes, I will.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Stefan Monnier]

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

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

[Basil L. Contovounesios]

"Miguel V. S. Frasson" <mvsfrasson@gmail.com> 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

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

[Basil L. Contovounesios]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> "Basil L. Contovounesios" <contovob@tcd.ie> 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 <michael_heerdegen@web.de>
> 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

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

[Basil L. Contovounesios]

Stefan Monnier <monnier@IRO.UMontreal.CA> 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

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

[Michael Heerdegen]

"Basil L. Contovounesios" <contovob@tcd.ie> 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.

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 410 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> 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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Michael Heerdegen]

"Basil L. Contovounesios" <contovob@tcd.ie> 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.

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

[Basil L. Contovounesios]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> "Basil L. Contovounesios" <contovob@tcd.ie> 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

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

[Basil L. Contovounesios]

Nicolas Petton <nicolas@petton.fr> writes:

> Michael Heerdegen <michael_heerdegen@web.de> 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

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

[Basil L. Contovounesios]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> "Basil L. Contovounesios" <contovob@tcd.ie> 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

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

[Basil L. Contovounesios]

[-- Attachment #1: bench.el --]
[-- Type: application/emacs-lisp, Size: 602 bytes --]

[-- Attachment #2: Type: text/plain, Size: 730 bytes --]


"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> Michael Heerdegen <michael_heerdegen@web.de> writes:
>
>> "Basil L. Contovounesios" <contovob@tcd.ie> 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

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

[Miguel V. S. Frasson]

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
<monnier@iro.umontreal.ca> 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
mvsfrasson@gmail.com

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

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
<monnier@iro.umontreal.ca> 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

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

[Stefan Monnier]

> (seq-contains nil '(nil t foo) (lambda (x) t))  ->  nil
> It returns *nil* if testfn fails, or *nil* (ELT) if it succeds.

Just because it sometimes does doesn't mean it always does:

    (seq-contains '(0 3 4) 1 #'<)
    
returns 3


        Stefan

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

[Michael Heerdegen]

"Miguel V. S. Frasson" <mvsfrasson@gmail.com> writes:

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

BTW, another (alternative) alternative would be to make it return
(list ELT).  That would be a bit less backward-compatible, but a
bit more consistent.

Michael.

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

[Miguel V. S. Frasson]

You are right.

Em qui, 14 de mar de 2019 às 20:14, Stefan Monnier
<monnier@iro.umontreal.ca> escreveu:
>
> > (seq-contains nil '(nil t foo) (lambda (x) t))  ->  nil
> > It returns *nil* if testfn fails, or *nil* (ELT) if it succeds.
>
> Just because it sometimes does doesn't mean it always does:
>
>     (seq-contains '(0 3 4) 1 #'<)
>
> returns 3
>
>
>         Stefan



-- 
Miguel Vinicius Santini Frasson
mvsfrasson@gmail.com

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

[Michael Heerdegen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> > (seq-contains nil '(nil t foo) (lambda (x) t))  ->  nil
> > It returns *nil* if testfn fails, or *nil* (ELT) if it succeds.
>
> Just because it sometimes does doesn't mean it always does:
>
>     (seq-contains '(0 3 4) 1 #'<)
>
> returns 3

Maybe it's too late here, but why is that a counterexample for

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

The first element is returned for that the test succeeds, what's special
about it?  < is not symmetrical, though, so it's a weird kind of
equality test.


Michael.

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

[Miguel V. S. Frasson]

[-- Attachment #1: Type: text/plain, Size: 530 bytes --]

Please ignore this e-mail of mine.

Em qui, 14 de mar de 2019 20:08, Miguel V. S. Frasson <mvsfrasson@gmail.com>
escreveu:

> Hi
>
> Em qui, 14 de mar de 2019 18:43, Stefan Monnier
> <monnier@iro.umontreal.ca> 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
>

[-- Attachment #2: Type: text/html, Size: 964 bytes --]

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

[Stefan Monnier]

>> > (seq-contains nil '(nil t foo) (lambda (x) t))  ->  nil
>> > It returns *nil* if testfn fails, or *nil* (ELT) if it succeds.
>> Just because it sometimes does doesn't mean it always does:
>>     (seq-contains '(0 3 4) 1 #'<)
>> returns 3
> Maybe it's too late here, but why is that a counterexample for
>> If ELT=nil, seq-contains currently returns nil anyway;"

Duh, sorry, I lost sight of the goal along the way.

A short real counter example is

    (seq-contains '(1) nil #'list)

but it's admittedly contrived.  A more real counter example is the one
alluded to by Nicolas earlier:

    (seq-contains '((t 1) (nil 2)) nil (lambda (x y) (equal x (car y))))

> The first element is returned for that the test succeeds, what's special
> about it?  < is not symmetrical, though, so it's a weird kind of
> equality test.

The test doesn't need to be an equality test.
IOW seq-contains is very close to seq-find.


        Stefan

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

[Michael Heerdegen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> The test doesn't need to be an equality test.

The doc doesn't specify in which order the args are delivered to the
TESTFN, so the behavior is unspecified.  For asymmetric TESTFNs I would
rather go with `seq-some'.


Michael.

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

[Stefan Monnier]

>> The test doesn't need to be an equality test.
> The doc doesn't specify in which order the args are delivered to the
> TESTFN, so the behavior is unspecified.

Indeed, that's another problem with seq-contains.


        Stefan

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

[Basil L. Contovounesios]

"Miguel V. S. Frasson" <mvsfrasson@gmail.com> writes:

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

Special-casing nil invalidates any benefits of returning the element
found, as it conflates nil and t and is inconsistent with other non-nil
values.  If seq-contains is to be made a proper predicate that continues
returning the element found, then the best proposal so far has been
Michael's[1], namely to return (list ELT).  The alternative is to simply
return a boolean, rather than the element found, but this is lossier
than Michael's suggestion.

[1]: https://debbugs.gnu.org/34852#68

-- 
Basil

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

[Basil L. Contovounesios]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> "Miguel V. S. Frasson" <mvsfrasson@gmail.com> writes:
>
>> 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.
>
> BTW, another (alternative) alternative would be to make it return
> (list ELT).  That would be a bit less backward-compatible, but a
> bit more consistent.

+1, either this or returning a boolean is fine with me.

-- 
Basil

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

[Miguel V. S. Frasson]

[-- Attachment #1: Type: text/plain, Size: 1384 bytes --]

Hi

I was convinced by the discussions here that changing seq-contains is a bad
idea.

I had the false premise that ELT=nil makes seq-contains return nil.

If I could make a suggestion, it would be include an &optional NOT-FOUND to
be the value returned in case of not finding any element matching TESTFN.

Cheers

Miguel

Em sex, 15 de mar de 2019 12:56, Basil L. Contovounesios <contovob@tcd.ie>
escreveu:

> Michael Heerdegen <michael_heerdegen@web.de> writes:
>
> > "Miguel V. S. Frasson" <mvsfrasson@gmail.com> writes:
> >
> >> 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.
> >
> > BTW, another (alternative) alternative would be to make it return
> > (list ELT).  That would be a bit less backward-compatible, but a
> > bit more consistent.
>
> +1, either this or returning a boolean is fine with me.
>
> --
> Basil
>

[-- Attachment #2: Type: text/html, Size: 2329 bytes --]

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

[Miguel V. S. Frasson]

Hi

Maybe this is the same bug, now with seq-difference

(seq-difference '(nil) '(1 nil) #'eq)
-> (nil)

(In my applications, nil is a frequent element of my lists)

Is this fixed by the proposed patches?


Cheers.

Miguel

Em sex, 15 de mar de 2019 às 13:08, Miguel V. S. Frasson
<mvsfrasson@gmail.com> escreveu:
>
> Hi
>
> I was convinced by the discussions here that changing seq-contains is a bad idea.
>
> I had the false premise that ELT=nil makes seq-contains return nil.
>
> If I could make a suggestion, it would be include an &optional NOT-FOUND to be the value returned in case of not finding any element matching TESTFN.
>
> Cheers
>
> Miguel
>
> Em sex, 15 de mar de 2019 12:56, Basil L. Contovounesios <contovob@tcd.ie> escreveu:
>>
>> Michael Heerdegen <michael_heerdegen@web.de> writes:
>>
>> > "Miguel V. S. Frasson" <mvsfrasson@gmail.com> writes:
>> >
>> >> 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.
>> >
>> > BTW, another (alternative) alternative would be to make it return
>> > (list ELT).  That would be a bit less backward-compatible, but a
>> > bit more consistent.
>>
>> +1, either this or returning a boolean is fine with me.
>>
>> --
>> Basil



-- 
Miguel Vinicius Santini Frasson
mvsfrasson@gmail.com

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

[Basil L. Contovounesios]

"Miguel V. S. Frasson" <mvsfrasson@gmail.com> writes:

> Maybe this is the same bug, now with seq-difference
>
> (seq-difference '(nil) '(1 nil) #'eq)
> -> (nil)
>
> (In my applications, nil is a frequent element of my lists)

It is indeed the same bug.

> Is this fixed by the proposed patches?

Yes.

-- 
Basil

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

[Miguel V. S. Frasson]

Thanks, Basil.

Em sáb, 16 de mar de 2019 às 17:49, Basil L. Contovounesios
<contovob@tcd.ie> escreveu:
>
> "Miguel V. S. Frasson" <mvsfrasson@gmail.com> writes:
>
> > Maybe this is the same bug, now with seq-difference
> >
> > (seq-difference '(nil) '(1 nil) #'eq)
> > -> (nil)
> >
> > (In my applications, nil is a frequent element of my lists)
>
> It is indeed the same bug.
>
> > Is this fixed by the proposed patches?
>
> Yes.
>
> --
> Basil



-- 
Miguel Vinicius Santini Frasson
mvsfrasson@gmail.com

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 879 bytes --]

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

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

Yes, will do.

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

Yes, thank you.

I'm now thinking about introducing a proper predicate to be used instead
of seq-contains for such cases, I would name it `seq-includes-p'.  Here
are my reasons:

- seq-some takes a predicate function, but we'd like a function that
  takes an elt to be tested.

- seq-contains returns the element found on purpose, it is not a
  predicate.  I think it has its use-cases, and I don't want to change
  it into a predicate now (I would have to rename it anyway).

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> - seq-contains returns the element found on purpose, it is not a
>   predicate.  I think it has its use-cases, and I don't want to change
>   it into a predicate now (I would have to rename it anyway).

I think most current appearances are using it as a predicate, however.
What do you intend - obsolete seq-contains?  I don't think we should
have an additional function - seq-contains already overlaps with
seq-some.

Why would you have to rename it btw?  To add a -p (I ask because
seq-some also doesn't end with -p)?  Just pondering...


Michael.

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 656 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I think most current appearances are using it as a predicate, however.

You have a point and we also have `seq-find' which returns the element
found.

> What do you intend - obsolete seq-contains?  I don't think we should
> have an additional function - seq-contains already overlaps with
> seq-some.

I didn't think about it, obsoleting `seq-contains' would work as well,
and it can actually make sense.  I would then name the new function
`seq-contains-p'.

> Why would you have to rename it btw?  To add a -p (I ask because
> seq-some also doesn't end with -p)?

Yes, to add a -p suffix.

Nicolas

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Nicolas Petton]

[-- Attachment #1.1: Type: text/plain, Size: 33 bytes --]

Hi,

Here's a patch for master.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: 0001-New-seq-contains-p-predicate-Bug-34852.patch --]
[-- Type: text/x-patch, Size: 6097 bytes --]

From 985aa028f05a418dddfd6394b739f42c32b01345 Mon Sep 17 00:00:00 2001
From: Nicolas Petton <nicolas@petton.fr>
Date: Wed, 20 Mar 2019 21:44:01 +0100
Subject: [PATCH] New seq-contains-p predicate (Bug#34852)

* lisp/emacs-lisp/seq.el (seq-contains-p): New predicate function.  It
is a replacement for seq-contains which cannot be used as a predicate
when a sequence contains nil values as it returns the element found.
(seq-contains): Make obsolete.

* test/lisp/emacs-lisp/seq-tests.el (test-seq-contains-p):
(test-seq-intersection-with-nil, test-seq-set-equal-p-with-nil,
test-difference-with-nil): Add regression tests.

* doc/lispref/sequences.texi (Sequence Functions): Document
seq-contains-p.
---
 doc/lispref/sequences.texi        |  9 +++++----
 lisp/emacs-lisp/seq.el            | 20 +++++++++++++++-----
 test/lisp/emacs-lisp/seq-tests.el | 21 +++++++++++++++++++++
 3 files changed, 41 insertions(+), 9 deletions(-)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 0c3c4e3b28..a7f270c068 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -782,10 +782,11 @@ Sequence Functions
 @end defun
 
 
-@defun seq-contains sequence elt &optional function
-  This function returns the first element in @var{sequence} that is equal to
-@var{elt}.  If the optional argument @var{function} is non-@code{nil},
-it is a function of two arguments to use instead of the default @code{equal}.
+@defun seq-contains-p sequence elt &optional function
+  This function returns non-@code{nil} if at least one element in
+@var{sequence} is equal to @var{elt}.  If the optional argument
+@var{function} is non-@code{nil}, it is a function of two arguments to
+use instead of the default @code{equal}.
 
 @example
 @group
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 4a811d7895..39c93e25ed 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -356,6 +356,7 @@ seq-sort-by
     count))
 
 (cl-defgeneric seq-contains (sequence elt &optional testfn)
+  (declare (obsolete "Use `seq-contains-p' instead." "27.1"))
   "Return the first element in SEQUENCE that is equal to ELT.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
   (seq-some (lambda (e)
@@ -363,11 +364,20 @@ seq-sort-by
                 e))
             sequence))
 
+(cl-defgeneric seq-contains-p (sequence elt &optional testfn)
+  "Return non-nil if SEQUENCE contains an element equal to ELT.
+Equality is defined by TESTFN if non-nil or by `equal' if nil."
+    (catch 'seq--break
+      (seq-doseq (e sequence)
+        (when (funcall (or testfn #'equal) e elt)
+          (throw 'seq--break t)))
+      nil))
+
 (cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)
   "Return non-nil if SEQUENCE1 and SEQUENCE2 contain the same elements, regardless of order.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
-  (and (seq-every-p (lambda (item1) (seq-contains sequence2 item1 testfn)) sequence1)
-       (seq-every-p (lambda (item2) (seq-contains sequence1 item2 testfn)) sequence2)))
+  (and (seq-every-p (lambda (item1) (seq-contains-p sequence2 item1 testfn)) sequence1)
+       (seq-every-p (lambda (item2) (seq-contains-p sequence1 item2 testfn)) sequence2)))
 
 (cl-defgeneric seq-position (sequence elt &optional testfn)
   "Return the index of the first element in SEQUENCE that is equal to ELT.
@@ -385,7 +395,7 @@ seq-sort-by
 TESTFN is used to compare elements, or `equal' if TESTFN is nil."
   (let ((result '()))
     (seq-doseq (elt sequence)
-      (unless (seq-contains result elt testfn)
+      (unless (seq-contains-p result elt testfn)
         (setq result (cons elt result))))
     (nreverse result)))
 
@@ -410,7 +420,7 @@ seq-sort-by
   "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)
+                (if (seq-contains-p sequence2 elt testfn)
                     (cons elt acc)
                   acc))
               (seq-reverse sequence1)
@@ -420,7 +430,7 @@ seq-sort-by
   "Return a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
   (seq-reduce (lambda (acc elt)
-                (if (not (seq-contains sequence2 elt testfn))
+                (if (not (seq-contains-p sequence2 elt testfn))
                     (cons elt acc)
                   acc))
               (seq-reverse sequence1)
diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index d8f00cfea4..6522def423 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -185,6 +185,14 @@ test-sequences-oddp
   (with-test-sequences (seq '(3 4 5 6))
     (should (= 5 (seq-contains seq 5)))))
 
+(ert-deftest test-seq-contains-p ()
+  (with-test-sequences (seq '(3 4 5 6))
+    (should (eq (seq-contains-p seq 3) t))
+    (should-not (seq-contains-p seq 7)))
+  (with-test-sequences (seq '())
+    (should-not (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq nil))))
+
 (ert-deftest test-seq-every-p ()
   (with-test-sequences (seq '(43 54 22 1))
     (should (seq-every-p (lambda (elt) t) seq))
@@ -436,5 +444,18 @@ test-sequences-oddp
     (should (equal (seq-rest lst) '(2 3)))
     (should (equal (seq-rest vec) [2 3]))))
 
+;; Regression tests for bug#34852
+(progn
+  (ert-deftest test-seq-intersection-with-nil ()
+    (should (equal (seq-intersection '(1 2 nil) '(1 nil)) '(1 nil))))
+
+  (ert-deftest test-seq-set-equal-p-with-nil ()
+    (should (seq-set-equal-p '("a" "b" nil)
+                             '(nil "b" "a"))))
+
+  (ert-deftest test-difference-with-nil ()
+    (should (equal (seq-difference '(1 nil) '(2 nil))
+                   '(1)))))
+
 (provide 'seq-tests)
 ;;; seq-tests.el ends here
-- 
2.20.1


[-- Attachment #1.3: Type: text/plain, Size: 6 bytes --]


Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> +(cl-defgeneric seq-contains-p (sequence elt &optional testfn)
> +  "Return non-nil if SEQUENCE contains an element equal to ELT.
> +Equality is defined by TESTFN if non-nil or by `equal' if nil."
> +    (catch 'seq--break
> +      (seq-doseq (e sequence)
> +        (when (funcall (or testfn #'equal) e elt)
> +          (throw 'seq--break t)))
> +      nil))

A detail: could you factor out the result of (or testfn #'equal) so that
`or' is not called repeatedly in the loop?

Michael.

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 230 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> A detail: could you factor out the result of (or testfn #'equal) so that
> `or' is not called repeatedly in the loop?

Yes, and I'll do that elsewhere as well.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Basil L. Contovounesios]

Nicolas Petton <nicolas@petton.fr> writes:

> Here's a patch for master.

Thanks, I have only some minor comments:

> diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
> index 4a811d7895..39c93e25ed 100644
> --- a/lisp/emacs-lisp/seq.el
> +++ b/lisp/emacs-lisp/seq.el
> @@ -356,6 +356,7 @@ seq-sort-by
>      count))
>  
>  (cl-defgeneric seq-contains (sequence elt &optional testfn)
> +  (declare (obsolete "Use `seq-contains-p' instead." "27.1"))

According to make-obsolete, "use instead" strings should not start with
a capital letter, but even better is (obsolete seq-contains-p "27.1"),
which adds a link to seq-contains-p in the *Help* buffer.

> @@ -420,7 +430,7 @@ seq-sort-by
>    "Return a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.
>  Equality is defined by TESTFN if non-nil or by `equal' if nil."
>    (seq-reduce (lambda (acc elt)
> -                (if (not (seq-contains sequence2 elt testfn))
> +                (if (not (seq-contains-p sequence2 elt testfn))
>                      (cons elt acc)
>                    acc))

Is there any harm in inverting this conditional structure, so that it
reads positively?

> diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
> index d8f00cfea4..6522def423 100644
> --- a/test/lisp/emacs-lisp/seq-tests.el
> +++ b/test/lisp/emacs-lisp/seq-tests.el
> @@ -185,6 +185,14 @@ test-sequences-oddp
>    (with-test-sequences (seq '(3 4 5 6))
>      (should (= 5 (seq-contains seq 5)))))
>  
> +(ert-deftest test-seq-contains-p ()
> +  (with-test-sequences (seq '(3 4 5 6))
> +    (should (eq (seq-contains-p seq 3) t))
> +    (should-not (seq-contains-p seq 7)))
> +  (with-test-sequences (seq '())
> +    (should-not (seq-contains-p seq 3))
> +    (should-not (seq-contains-p seq nil))))
> +

I think there should also be an explicit nil membership check:

(should (seq-contains-p  [nil] nil))
(should (seq-contains-p '(nil) nil))

-- 
Basil

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 1538 bytes --]

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> Nicolas Petton <nicolas@petton.fr> writes:
>
>>  (cl-defgeneric seq-contains (sequence elt &optional testfn)
>> +  (declare (obsolete "Use `seq-contains-p' instead." "27.1"))
>
> According to make-obsolete, "use instead" strings should not start with
> a capital letter, but even better is (obsolete seq-contains-p "27.1"),
> which adds a link to seq-contains-p in the *Help* buffer.

Indeed, that's better, thank you.

>> @@ -420,7 +430,7 @@ seq-sort-by
>>    "Return a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.
>>  Equality is defined by TESTFN if non-nil or by `equal' if nil."
>>    (seq-reduce (lambda (acc elt)
>> -                (if (not (seq-contains sequence2 elt testfn))
>> +                (if (not (seq-contains-p sequence2 elt testfn))
>>                      (cons elt acc)
>>                    acc))
>
> Is there any harm in inverting this conditional structure, so that it
> reads positively?

It's not the purpose of this patch, but I can commit it separately.

>> +(ert-deftest test-seq-contains-p ()
>> +  (with-test-sequences (seq '(3 4 5 6))
>> +    (should (eq (seq-contains-p seq 3) t))
>> +    (should-not (seq-contains-p seq 7)))
>> +  (with-test-sequences (seq '())
>> +    (should-not (seq-contains-p seq 3))
>> +    (should-not (seq-contains-p seq nil))))
>> +
>
> I think there should also be an explicit nil membership check:
>
> (should (seq-contains-p  [nil] nil))
> (should (seq-contains-p '(nil) nil))

Good idea!

Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 250 bytes --]

tags 34852 fixed
close 34852 27.1
thanks

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> Nicolas Petton <nicolas@petton.fr> writes:
>
>> Here's a patch for master.

I pushed a revised patch to master, so I'm closing this issue.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]