Subject: bug#30626: 26.0.91; Crash when traversing a `stream-of-directory-files'

From: Noam Postavsky <[email-masked]>
Date: Wed, 24 Apr 2019 23:20:44 -0400

Michael Heerdegen <[email-masked]> writes:

>> I don't have a quick answer for the general case, but I think it's a bug
>> in stream.el that it's creating such large structures in the first
>> place.  As far as I understand it, the point of streams is to handle
>> long lists by encoding them as
>>
>>     (FIRST-VALUE . FUNCTION-TO-PRODUCE-REST-OF-LIST)
>
> Yes, that's exactly how it's implemented.  When requesting more elements
> from the stream, that becomes
>
>       (FIRST-VALUE .
>         (SECOND-VALUE . FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST))
>
> When we loop over the string, the cons whose car is the FIRST-VALUE,
> let's call it cons1, is immediately thrown away, and we continue with
>
>       (SECOND-VALUE . FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST)

Coming back to this again.  I think I got lost in the weeds of the
byte-code function objects before.  The core problem is that streams are
not exactly encoded like the above, because even after forcing it you
don't have just a plain SECOND-VALUE stored in the stream.  The original
FUNCTION-TO-PRODUCE-MORE-REST-OF-LIST stays around and keeps referencing
all the code and all the following elements.  So a possible solution is
change the stream to get rid of the lambda part and just leave the
computed value after it's forced.  With the following patch
(stream-flush (stream-range 1 1000000)) succeeds:

>From 5e7139618f1b4cebbe9785ea5a9303b80d1b2c92 Mon Sep 17 00:00:00 2001
From: Noam Postavsky <[email-masked]>
Date: Wed, 24 Apr 2019 22:51:19 -0400
Subject: [PATCH] [WIP] Drop forced lambda's from stream (Bug#30626)

Let the stream id distinguish between forced and unforced stream
values, replacing (think-delay BODY) with just (lambda () BODY).  When
the value is forced, replace the lambda with its result.
---
 packages/stream/stream.el | 30 +++++++++++++++++++++---------
 1 file changed, 21 insertions(+), 9 deletions(-)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 3f6bc4b5b..fa7a3b520 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -65,18 +65,28 @@
 
 (eval-when-compile (require 'cl-lib))
 (require 'seq)
-(require 'thunk)
 
 (eval-and-compile
-  (defconst stream--identifier '--stream--
-    "Symbol internally used to identify streams."))
+  (defconst stream--fresh-identifier '--stream-fresh--
+    "Symbol internally used to streams whose head was not evaluated.")
+  (defconst stream--evald-identifier '--stream-evald--
+    "Symbol internally used to streams whose head was evaluated."))
 
 (defmacro stream-make (&rest body)
   "Return a stream built from BODY.
 BODY must return nil or a cons cell whose cdr is itself a
 stream."
   (declare (debug t))
-  `(list ',stream--identifier (thunk-delay ,@body)))
+  `(list ',stream--fresh-identifier (lambda () ,@body)))
+
+(defun stream-force (stream)
+  (cond
+   ((eq (car-safe stream) stream--evald-identifier)
+    (cadr stream))
+   ((eq (car-safe stream) stream--fresh-identifier)
+    (setf (car stream) stream--evald-identifier)
+    (setf (cadr stream) (funcall (cadr stream))))
+   (t (signal 'wrong-type-argument (list 'streamp stream)))))
 
 (defmacro stream-cons (first rest)
   "Return a stream built from the cons of FIRST and REST.
@@ -159,24 +169,26 @@ (defun stream-range (&optional start end step)
 
 (defun streamp (stream)
   "Return non-nil if STREAM is a stream, nil otherwise."
-  (eq (car-safe stream) stream--identifier))
+  (let ((car (car-safe stream)))
+    (or (eq car stream--fresh-identifier)
+        (eq car stream--evald-identifier))))
 
 (defun stream-empty ()
   "Return a new empty stream."
-  (list stream--identifier (thunk-delay nil)))
+  (list stream--evald-identifier nil))
 
 (defun stream-empty-p (stream)
   "Return non-nil if STREAM is empty, nil otherwise."
-  (null (thunk-force (cadr stream))))
+  (null (cadr (stream-force stream))))
 
 (defun stream-first (stream)
   "Return the first element of STREAM.
 Return nil if STREAM is empty."
-  (car (thunk-force (cadr stream))))
+  (car (stream-force stream)))
 
 (defun stream-rest (stream)
   "Return a stream of all but the first element of STREAM."
-  (or (cdr (thunk-force (cadr stream)))
+  (or (cdr (stream-force stream))
       (stream-empty)))
 
 (defun stream-append (&rest streams)
-- 
2.11.0

The reason I didn't do this in thunk.el is that thunks are just bare
lambdas, so there is no way to get rid it "from the inside", as it were.
Whereas for streams, it's just a matter of list editing.

Some additional things that I thought of changing, but I didn't yet:

- stream--identifier vs just using '--stream-- directly, I don't see
  what's the benefit of indirection here.

- stream-make should use cons instead of list (or maybe a struct?).

- stream-empty should just be a constant.