[PATCH Elpa: streams.el] Add systematic tests against bogus element generation

[PATCH Elpa: streams.el] Add systematic tests against bogus element generation

[Michael Heerdegen]

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

Hi,

we very often made the error of implementing functions like `seq-map'
for streams so that they unnecessarily generated elements from input
streams (and as you'll see, we are still doing this in some cases...)

But we currently only have one test for `seq-map'.  This patch
implements a new class of tests for all functions where this problem can
potentially occur.  In addition, because this problem is so common (and
it's not so obvious that even the use of `stream-empty-p' is
problematic), I also added a note to the header.

The tests reveal two errors we had not discovered yet.  I'll fix these
in one of the next commits.

Ok, and here is the proposed patch.


Regards,

Michael.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Add-systematic-tests-against-bogus-element-generation.patch --]
[-- Type: text/x-diff, Size: 4393 bytes --]

From 1771087232cb7e8356a5a3d1a338732da12bdd7a Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Fri, 16 Sep 2016 01:20:45 +0200
Subject: [PATCH] Add systematic tests against bogus element generation

Also add a note about this problem in the header and how to avoid it.
---
 packages/stream/stream.el             | 13 +++++++++++-
 packages/stream/tests/stream-tests.el | 38 +++++++++++++++++++++++++++++------
 2 files changed, 44 insertions(+), 7 deletions(-)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 9954fc8..ef19918 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -4,7 +4,7 @@
 
 ;; Author: Nicolas Petton <nicolas@petton.fr>
 ;; Keywords: stream, laziness, sequences
-;; Version: 2.2.1
+;; Version: 2.2.2
 ;; Package-Requires: ((emacs "25"))
 ;; Package: stream
 
@@ -49,6 +49,17 @@
 ;; (defun fib (a b)
 ;;  (stream-cons a (fib b (+ a b))))
 ;; (fib 0 1)
+;;
+;; A note for developers: Please make sure to implement functions that
+;; process streams (build new streams out of given streams) in a way
+;; that no new elements in any argument stream are generated.  This is
+;; most likely an error since it changes the argument stream.  For
+;; example, a common error is to call `stream-empty-p' on an input
+;; stream and build the stream to return depending on the result.
+;; Instead, delay such tests until elements are requested from the
+;; resulting stream.  A way to achieve this is to wrap such tests into
+;; `stream-make' or `stream-delay'.  See the implementations of
+;; `stream-append' or `seq-drop-while' for example.
 
 ;;; Code:
 
diff --git a/packages/stream/tests/stream-tests.el b/packages/stream/tests/stream-tests.el
index 31c3530..e79c3ef 100644
--- a/packages/stream/tests/stream-tests.el
+++ b/packages/stream/tests/stream-tests.el
@@ -234,12 +234,6 @@
   (should (= (seq-length (seq-subseq (stream-range 2 10) 1 3)) 2))
   (should (= (seq-elt (seq-subseq (stream-range 2 10) 1 3) 1) 4)))
 
-(ert-deftest stream-seq-map-should-not-consume-stream-elements ()
-  (let* (consumed
-         (stream (stream-cons (setq consumed t) (stream-empty))))
-    (seq-map #'identity stream)
-    (should-not consumed)))
-
 (ert-deftest stream-pop-test ()
   (let* ((str (stream '(1 2 3)))
          (first (stream-pop str))
@@ -271,5 +265,37 @@
                                  (stream (list 5 6 7 8 9))))))
                  (list 1 2 3 4 5 6 7 8 9))))
 
+;; Tests whether calling stream processing functions ("transducers")
+;; doesn't generate elements from argument streams
+
+(defvar this-delayed-stream-function nil)
+
+(defun make-delayed-test-stream ()
+  (stream-make
+   (cons (prog1 1 (error "`%s' not completely delayed" this-delayed-stream-function))
+         (make-delayed-test-stream))))
+
+(defmacro deftest-for-delayed-evaluation (call)
+  (let ((function (car call)))
+    `(ert-deftest ,(intern (concat (symbol-name function) "-delayed-test")) ()
+       (let ((this-delayed-stream-function ',function))
+         (should (prog1 t ,call))))))
+
+(deftest-for-delayed-evaluation (streamp        (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seqp           (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (stream-append  (make-delayed-test-stream) (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-take (make-delayed-test-stream) 2))
+(deftest-for-delayed-evaluation (seq-drop (make-delayed-test-stream) 2))
+(deftest-for-delayed-evaluation (seq-take-while #'numberp (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-take-until #'numberp (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-map #'identity (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-filter #'cl-evenp (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (stream-delay (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-copy (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-subseq (make-delayed-test-stream) 2))
+(deftest-for-delayed-evaluation (stream-scan #'* 1 (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (stream-concatenate (stream (list (make-delayed-test-stream)
+                                                                  (make-delayed-test-stream)))))
+
 (provide 'stream-tests)
 ;;; stream-tests.el ends here
-- 
2.9.3

Re: [PATCH Elpa: streams.el] Add systematic tests against bogus element generation

[Nicolas Petton]

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

Michael Heerdegen <michael_heerdegen@web.de> writes:

Hi Michael,


> +;; A note for developers: Please make sure to implement functions that
> +;; process streams (build new streams out of given streams) in a way
> +;; that no new elements in any argument stream are generated.  This is
> +;; most likely an error since it changes the argument stream.  For
> +;; example, a common error is to call `stream-empty-p' on an input
> +;; stream and build the stream to return depending on the result.
> +;; Instead, delay such tests until elements are requested from the
> +;; resulting stream.  A way to achieve this is to wrap such tests into
> +;; `stream-make' or `stream-delay'.  See the implementations of
> +;; `stream-append' or `seq-drop-while' for example.

Very good, thank you!

Feel free to push this patch.

Cheers,
Nico

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

Re: [PATCH Elpa: streams.el] Add systematic tests against bogus element generation

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> Feel free to push this patch.

Ok, done!

The patch fixing the detected errors will come soon.


Regards,

Michael.

[PATCH Elpa] Fix errors detected by tests added in last commit (was: [PATCH Elpa: streams.el] Add systematic tests against bogus element generation)

[Michael Heerdegen]

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

I <michael_heerdegen@web.de> wrote:

> The patch fixing the detected errors will come soon.

Ok, here is the (quite trivial) fix.


Regards,

Michael.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-errors-detected-by-tests-added-in-last-commit.patch --]
[-- Type: text/x-diff, Size: 2291 bytes --]

From e41db042aadec660fbc0736f416a6f0aabfd1602 Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Sat, 17 Sep 2016 15:42:45 +0200
Subject: [PATCH] Fix errors detected by tests added in last commit

---
 packages/stream/stream.el | 33 ++++++++++++++++-----------------
 1 file changed, 16 insertions(+), 17 deletions(-)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index ef19918..9a7f664 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -4,7 +4,7 @@
 
 ;; Author: Nicolas Petton <nicolas@petton.fr>
 ;; Keywords: stream, laziness, sequences
-;; Version: 2.2.2
+;; Version: 2.2.3
 ;; Package-Requires: ((emacs "25"))
 ;; Package: stream
 
@@ -273,12 +273,13 @@ stream will simply be accordingly shorter, or even empty)."
 
 (cl-defmethod seq-take ((stream stream) n)
   "Return a stream of the first N elements of STREAM."
-  (if (or (zerop n)
-          (stream-empty-p stream))
-      (stream-empty)
-    (stream-cons
-     (stream-first stream)
-     (seq-take (stream-rest stream) (1- n)))))
+  (stream-make
+   (if (or (zerop n)
+           (stream-empty-p stream))
+       nil
+     (cons
+      (stream-first stream)
+      (seq-take (stream-rest stream) (1- n))))))
 
 (cl-defmethod seq-drop ((stream stream) n)
   "Return a stream of STREAM without its first N elements."
@@ -327,16 +328,14 @@ kind of nonlocal exit."
 
 (cl-defmethod seq-filter (pred (stream stream))
   "Return a stream of the elements for which (PRED element) is non-nil in STREAM."
-  (if (stream-empty-p stream)
-      stream
-    (stream-make
-     (while (not (or (stream-empty-p stream)
-                     (funcall pred (stream-first stream))))
-       (setq stream (stream-rest stream)))
-     (if (stream-empty-p stream)
-         nil
-       (cons (stream-first stream)
-             (seq-filter pred (stream-rest stream)))))))
+  (stream-make
+   (while (not (or (stream-empty-p stream)
+                   (funcall pred (stream-first stream))))
+     (setq stream (stream-rest stream)))
+   (if (stream-empty-p stream)
+       nil
+     (cons (stream-first stream)
+           (seq-filter pred (stream-rest stream))))))
 
 (defmacro stream-delay (expr)
   "Return a new stream to be obtained by evaluating EXPR.
-- 
2.9.3

Re: [PATCH Elpa] Fix errors detected by tests added in last commit (was: [PATCH Elpa: streams.el] Add systematic tests against bogus element generation)

[Nicolas Petton]

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

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I <michael_heerdegen@web.de> wrote:
>
>> The patch fixing the detected errors will come soon.
>
> Ok, here is the (quite trivial) fix.

Great, thanks! Feel free to push.

Cheers,
Nico

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

Re: [PATCH Elpa] Fix errors detected by tests added in last commit

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> > Ok, here is the (quite trivial) fix.
>
> Great, thanks! Feel free to push.

Done.


Michael.