map-into misuses extended sequences protocol

Bug #1855375 reported by James Kalenius on 2019-12-06
This bug affects 1 person
Affects Status Importance Assigned to Milestone

Bug Description

tl;dr I found a small bug in MAP-INTO on extended sequences. I attached a patch.

Concerning the sequence:iterator-foo functions, the extended sequences paper says

"While implementors of sequence classes may choose to use this CLOS-based iterator protocol (at the potential loss of efficiency through generic function dispatch at each step), users of the iteration protocol (who define functions which perform iterations over sequences) may not assume that the sequence class implementor has done so, and so must call make-sequence-iterator or the operators discussed below."

My reading is that it should be possible to define a sequence class without defining any of the iterator-foo methods, and instead just returning specialized functions from MAKE-SEQUENCE-ITERATOR. Having specialized functions instead of using the generic ones means not doing generic dispatch every iteration, which is nice.

SBCL seems to agree with me everywhere, including places it results in extra consing (like %MAP-FOR-EFFECT), except for when an extended sequence is used as the result-sequence for MAP-INTO. For this case it uses the first two values from MAKE-SEQUENCE-ITERATOR and then the iterator-foo functions. If these have default definitions don't mesh with the iterator objects errors are signaled. This could be done for example by defining a mimic of CL lists:

(defclass my-list (sequence standard-object)
  ((%nilp :initarg :nilp :initform nil :accessor nilp)
   (%kar :initarg :kar :accessor kar)
   (%kdr :initarg :kdr :accessor kdr)))

(defun my-list (&rest elems)
  (if (null elems)
      (load-time-value (make-instance 'my-list :nilp t) t)
      (make-instance 'my-list
        :kar (first elems) :kdr (apply #'my-list (rest elems)))))

(defmethod sequence:make-sequence-iterator
    ((sequence my-list) &key from-end start end)
  (declare (ignore from-end start end))
  (values sequence (my-list) nil
          (lambda (sequence iterator from-end)
            (declare (ignore sequence from-end))
            (kdr iterator))
          (lambda (sequence iterator limit from-end)
            (declare (ignore sequence from-end))
            (eq iterator limit))
          (lambda (sequence iterator)
            (declare (ignore sequence))
            (kar iterator))
          (lambda (new sequence iterator)
            (declare (ignore sequence))
            (setf (kar iterator) new))
          (constantly 0)
          (lambda (sequence iterator)
            (declare (ignore sequence))

(map-into (list 1 2 3) #'identity (my-list 4 5 6)) => (4 5 6)

but (map-into (my-list 1 2 3) #'identity (list 4 5 6)) results in

The value
  #<MY-LIST {100598ED33}>
is not of type
when binding SB-KERNEL::X
   [Condition of type TYPE-ERROR]

because it calls SEQUENCE:ITERATOR-ENDP which is written as if iterators are indices.

This can be fixed by changing MAP-INTO to use more return values from MAKE-SEQUENCE-ITERATOR. Performance-wise this means the MAP-INTO-LAMBDA closes over a few more things but it's probably fine.

Patch is attached.

sbcl --version

uname -a
Linux Syadavaktavyah 5.3.6-arch1-1-ARCH #1 SMP PREEMPT Fri Oct 11 18:28:05 UTC 2019 x86_64 GNU/Linux


James Kalenius (aeshtaer) wrote :
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers

Bug attachments