SEARCH does not work correctly for some inputs when user-defined sequences are involved

[Jan Moringen]

What I do:
(defclass list-backed-sequence (standard-object sequence)
  ((elements :initarg :elements :type list :accessor %elements)))

(defmethod sequence:make-sequence-like ((sequence list-backed-sequence) length
                                        &rest args &key
                                        initial-element initial-contents)
  (declare (ignore initial-element initial-contents))
  (make-instance 'list-backed-sequence :elements (apply #'sequence:make-sequence-like '() length args)))

(defmethod sequence:length ((sequence list-backed-sequence))
  (length (%elements sequence)))

(defmethod sequence:elt ((sequence list-backed-sequence) index)
  (nth index (%elements sequence)))

(defmethod (setf sequence:elt) (new-value (sequence list-backed-sequence) index)
  (setf (nth index (%elements sequence)) new-value))

(search #(1) (coerce #(1 2 3 2 1) 'list-backed-sequence) :start2 1)

What happens:
0 is returned

What I expected to happen:
4 is returned

$ sbcl --version
SBCL 1.1.5
$ uname -a
Linux ferberit 3.5.0-25-generic #38-Ubuntu SMP Mon Feb 18 23:28:26 UTC 2013 i686 i686 i686 GNU/Linux
$ sbcl --eval '(print *features*)' --quit
(:QUICKLISP :SB-BSD-SOCKETS-ADDRINFO :ASDF2 :ASDF :ASDF-UNICODE
 :ALIEN-CALLBACKS :ANSI-CL :C-STACK-IS-CONTROL-STACK :COMMON-LISP
 :COMPARE-AND-SWAP-VOPS :CYCLE-COUNTER :ELF :GENCGC :IEEE-FLOATING-POINT
 :INLINE-CONSTANTS :LARGEFILE :LINKAGE-TABLE :LINUX :LITTLE-ENDIAN
 :MEMORY-BARRIER-VOPS :MULTIPLY-HIGH-VOPS :OS-PROVIDES-BLKSIZE-T
 :OS-PROVIDES-DLADDR :OS-PROVIDES-DLOPEN :OS-PROVIDES-GETPROTOBY-R
 :OS-PROVIDES-POLL :OS-PROVIDES-PUTWC :OS-PROVIDES-SUSECONDS-T
 :PACKAGE-LOCAL-NICKNAMES :RAW-INSTANCE-INIT-VOPS :SB-CORE-COMPRESSION :SB-DOC
 :SB-EVAL :SB-FUTEX :SB-LDB :SB-PACKAGE-LOCKS :SB-SAFEPOINT
 :SB-SOURCE-LOCATIONS :SB-TEST :SB-THREAD :SB-UNICODE :SBCL
 :STACK-ALLOCATABLE-CLOSURES :STACK-ALLOCATABLE-FIXED-OBJECTS
 :STACK-ALLOCATABLE-LISTS :STACK-ALLOCATABLE-VECTORS
 :STACK-GROWS-DOWNWARD-NOT-UPWARD :UNIX :UNWIND-TO-FRAME-AND-CALL-VOP :X86)

[Jan Moringen (scymtym)]

The attached patch extends some tests in tests/seq.impure.lisp to user-defined sequences. It also contains a new implementation of SEQUENCE:SEARCH which passes the tests and is slightly faster on the inputs in tests/seq.impure.lisp.